A fast pessimistic one-step diagnosis algorithm for hypercube multicomputer systems |
| |
Affiliation: | 1. School of Mathematics and Information Science, Henan Normal University, Xinxiang, Henan 453007, PR China;2. Henan Engineering Laboratory for Big Data and Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, Henan 453007, PR China;1. School of Mathematics and Information Sciences, Henan Normal University, Xinxiang, Henan 453007, PR China;2. School of Applied Science, Taiyuan University of Science and Technology, Taiyuan, Shanxi 030024, PR China;1. Dipartimento di Chimica, Fisica e Ambiente, via Cotonificio 108, Università di Udine, Udine 33100, Italy;2. Institut de Tècniques Energètiques and Centre for Research in Nanoengineering, Universitat Politècnica de Catalunya, Barcelona 08028, Spain;1. Institute of Information and Decision Sciences, National Taipei University of Business, Taipei, Taiwan, ROC;2. Department of Information Management, National Taipei University of Business, Taipei, Taiwan, ROC;3. Department of Industrial Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan, ROC |
| |
Abstract: | This paper describes a system-level diagnosis algorithm for hypercube multicomputer systems. The algorithm is based on the PMC model and can isolate all faulty processors to within a set that contains at most one fault-free processor. If we denote by N the total number of processors in a hypercube system to be diagnosed, then, based on the judiciously designed data structures, the algorithm can run in O(Nlog2N) time; whereas the best-known diagnosis algorithm, the YML algorithm, runs in O(N2.5) time. Consequently, the new algorithm is remarkably superior to the YML algorithm in terms of the time cost. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|