A Linear Time Pessimistic Diagnosis Algorithm for Hypermesh Multiprocessor Systems under the PMC Model

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 2n(k - 1) - k. We then propose an efficient pessimistic diagnostic algorithm to identify at most 2n(k - 1) - k faults in O(N) time, where mbik is the radix, mbin is the number of dimensions, and N = kⁿ is the total number of processors. This result is superior to the best precise diagnostic algorithm, which runs in O(NlogkN) 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.