کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
471513 | 698638 | 2007 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM∗ model A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM∗ model](/preview/png/471513.png)
Comparison-based diagnosis is a practical approach to the system-level fault diagnosis of multiprocessors. The locally twisted cube is a newly introduced hypercube variant, which not only possesses lower diameter and better graph embedding capability as compared with a hypercube of the same size, but retains some nice properties of hypercubes. This paper addresses the fault diagnosis of locally twisted cubes under the MM∗ comparison model. By utilizing the existence of abundant cycles within a locally twisted cube, we present a new diagnosis algorithm. With elaborately organized data, this algorithm can run in O(Nlog22N) time, where NN stands for the total number of nodes. In comparison, the classical Sengupta–Dahbura diagnosis algorithm takes as much as O(N5)O(N5) time to achieve the same goal. As a consequence, the proposed algorithm is remarkably superior to the Sengupta–Dahbura algorithm in terms of the time overhead.
Journal: Computers & Mathematics with Applications - Volume 53, Issue 6, March 2007, Pages 918–926