Fault- Tolerant Prefix Computation on Hypercubes

高次元立方體上的容錯前置計算

毛志文(Jyh-Wen Mao) ； 楊昌彪(Chang-Biau Yang)

《馬偕護理專科學校學報》 1期 (2001/05) Pp. 25-36

摘要

由於在一個平行架構的計算機系統具有多個處理器協同合作，因此容錯機制已經是容易達成的功能。在解決平行前置計算時並不需要一直使用所有的處理器。所以我們提出一個在高次元立方體架構下，某些處理器故障時解決前置計算的容錯策略。如果此高次元立方體架構有一個正常的完整次架構且包含半數的處理器數目，則我們的前置計算可在0（log n）的時間下完成，而最差的情況需要0（log2n）的時間。

關鍵字

容錯 ； 高次元立方體 ； 多處理器系統 ； 前置計算

並列摘要

In a parallel computer system, fault-tolerance is more obtainable since there are than one processor cooperated in the system. And, for solving parallel prefix computation, we need not use all processors all the time. Thus, we shall propose a fault-tolerant mechanism when we solve the prefix computation problem on faulty hypercube computers. By our mechanism, prefix computation can be down in O(log n) time on a faulty hypercube computer if there exists a fault-free subcube with size being at least a half of the hypercube, and in O(log2n) time in the worst case.

並列關鍵字

fault-tolerant ； hypercube ； multiprocessor system ； prefix computation