In microprocessor-based systems, such as the cloud computing infrastructure, high reliability is essential. As multiprocessor systems become more widespread and increasingly complex, system-level diagnosis will increasingly be adopted to determine their robustness. In this paper, we consider a pessimistic diagnostic strategy for hypermesh multiprocessor systems under the PMC model. The pessimistic strategy is a diagnostic process whereby all faulty processors are correctly identified and at most one fault-free processor may be misjudged to be a faulty processor. We first determine the pessimistic diagnosability of a hypermesh to be${2}{{n}}({{k}} - {1}) - {{k}}$. We then propose an efficient pessimistic diagnostic algorithm to identify at most${ 2}{{n}}({{k}} - { 1}) - {{k}}$faults in${{O}}({{N}})$time, where${\mbi{k}}$is the radix,${\mbi{n}}$is the number of dimensions, and${{N}} = {{k^n}}$is the total number of processors. This result is superior to the best precise diagnostic algorithm, which runs in${{O}}({{N}}{\log _{{k}}}{{N}})$time. Furthermore, the Cartesian product network, a subgraph of the hypermesh and the proposed algorithm can be employed to determine faults in the product network.

A new fast approach to the nearest codeword search using a single kick-out condition is proposed. The nearest codeword found by the proposed approach is identical to the one found by the full search, although the processing time is much shorter. The principle is to bypass those codewords which satisfy the proposed kick-out condition without the actual (and time-consuming) computation of the distortions from the bypassed codewords to the query vector. Due to the efficiency and simplicity of the proposed condition, a considerable saving of the central processing unit time needed to encode a data set (using a given codebook) can be achieved. Moreover, the memory requirement is low. Comparisons with some previous works are included to show these two benefits.