Title :
(t; k)-Diagnosis for matching composition networks
Author :
Guey-Yun Chang ; Chen, Gen-Huey ; Chang, Guey-Yun
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t ≥k This paper proposes a (t,k) diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that matching composition networks of n dimensions are (Ω(2n·logn/n),n)-diagnosable, where n > 5.
Keywords :
fault diagnosis; multiprocessing systems; multiprocessor interconnection networks; (t,k)-diagnosis algorithm; Mobius cubes; composition network matching; crossed cubes; faulty processors; hypercubes; interconnection network; multiprocessor system; sequential diagnosis; twisted cubes; Communication channels; Fault diagnosis; Hypercubes; Multiprocessing systems; Multiprocessor interconnection networks; Sequential diagnosis; System testing; Topology; Tree graphs; (t; Index Terms- Diagnosability; PMC model; k){hbox{-}}{rm diagnosis}.; matching composition network; multiprocessor system; precise diagnosis strategy; sequential diagnosis;
Journal_Title :
Computers, IEEE Transactions on
