|
In parallel processing, prefix computation, sorting, and embeddings are three of the most important and kernel research issues. Based on the concept of the light-occupied dimension (LOD) [60, 62], this thesis first proposes some new partition schemes to partition a hypercube into subcubes. According to the proposed schemes and the derived properties, this thesis presents two algorithms for prefix computation and sorting on faulty hypercubes. Without using the LOD concept, we present some embedding methods to map complete binary trees into faulty hypercubes. Given 2n = N operands and an n-dimensional hypercube Hn with [3n/2] - 1 faulty nodes, employing a newly proposed delay-update technique, the proposed algorithm for prefix computation takes n + 5logn + 7 steps and it tolerates more [n/2] faulty nodes than Raghavendra and Sridhar''s algorithm [46], although 11 extra steps are needed. Consider M unsorted elements and the same faulty Hn, where M ≧ N. With O((M/N) log(M/N) + (M/N) log2 N) time as in Sheu et al.'' algorithm [53], the proposed sorting algorithm tolerates more [n/2] faulty nodes than Sheu et al.''s algorithm [53]. Finally, we present some embedding methods to map complete binary trees (CBTs) into hypercubes. With dilation 1 and expansion 1, we first present an embedding algorithm to map two (n-1)-CBTs, where each is a CBT with n-1 levels and 2n-1 nodes, (one (n-1) -CBT and two (n-2)-CBTs) into Hn tolerating two (three) connected faulty nodes. With dilation 1 and expansion 2, the proposed fault-tolerant embedding algorithm maps an (n - 1)-CBT into an Hn with 2n - 2[log2 (n-2)]-5 faulty nodes distributed on a half of the Hn. Under the same dilation, expansion, and distribution of faulty nodes, our result has twice the capacity of fault tolerance of the previous known result [9] asymtotically.
|