Minimum Assignment of Test Links for Hypercubes with Lower Fault Bounds

✍ Scribed by Dajin Wang; Zhongxian Wang

• Book ID: 102603653
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 406 KB
• Volume: 40
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.1279

✦ Synopsis

In an n-dimensional hypercube multiprocessor system, to correctly diagnose faulty processors among themselves, the maximum allowed number of faulty processors is n under the well-known PMC diagnostic model. When the n fault bound is adopted, all links between processors will be used in the diagnosis. However, if the fault bound is lower than n, many links can be freed from the task of performing diagnosis. In this paper, we show that each drop of the fault bound by 1 will free 2 n-1 links from diagnosis. We will present an algorithm that selects, in a symmetric manner, the to-be-freed links, so that only a minimum number of links will be used to perform diagnosis. A rigorous proof for the algorithm's correctness is given. The freed links will never be used for the purpose of diagnosis, so that the diagnosis and some conventional computations may be carried out simultaneously, improving the performance of the system as a whole.