題名: | Three Methods for Subcube determination in Faulty Hypercubes |
作者: | Yeh, Yao-ming Chang, Yao-ming |
關鍵字: | Hypercube System Parallel Processing Fault-Tolerance |
期刊名/會議名稱: | 2002 ICS會議 |
摘要: | For a large hypercube system, the probability of fault occurrence can be high. It is often desired to reconfigure the faulty hypercube that operates in a gracefully degraded manner as to retain as many nonfaulty nodes and links as possible. Therefore the subcube determination problem is essential that the time for executing a parallel algorithm trends to depend on the dimension of the assigned subcube. Here, we present three different methods to determine prime subcubes which are hypercube function method, Q-map method , and synchronized message passing (SMP) method. The basic ideas of these three methods are from the similarities between Boolean algebra and hypercube topology. A faulty hypercube system can be described by a hypercube function. The hypercube function is similar to the logic function of a switching circuit. The nonfaulty subcubes in the system can be obtained from the complement of set of faulty nodes by DeMorgan’s law easily. We propose the Q-map method which improved from the K-map method of logic circuit to provide a easy method for finding subcubes in a small faulty hypercube system. The proposed SMP method is a parallel algorithm, which exhibits polynomial time complexity with respect to the system’s dimension. This method can deal with node failures and link failures. |
日期: | 2006-10-16T01:46:50Z |
分類: | 2002年 ICS 國際計算機會議 |
文件中的檔案:
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ce07ics002002000015.PDF | 142.24 kB | Adobe PDF | 檢視/開啟 |
在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。