Title :
Fault-tolerant sorting in SIMD hypercubes
Author :
Mishra, Amitabh ; Chang, Y. ; Bhuyan, L. ; Lombardi, F.
Author_Institution :
Dept. of Comput. Sci., Texas A&M Univ., College Station, TX, USA
Abstract :
This paper considers sorting in SIMD hypercube multiprocessors in the presence of node failures. The proposed algorithm correctly sorts up to 2n=N keys in a faulty SIMD hypercube of dimension n containing up to n-1 faulty nodes. The proposed fault-tolerant algorithm employs radix sort. We use a pair of flood dimensions which helps to route data around the faulty processors during the movement of data. If all the key values to be sorted belong to the range 0 to M-1, sorting can be accomplished efficiently in O(log M*log N)+O(log2N) time
Keywords :
fault tolerant computing; hypercube networks; multiprocessing systems; sorting; SIMD hypercubes; fault-tolerant sorting; multiprocessors; node failures; radix sort; Computer networks; Computer science; Concurrent computing; Distributed computing; Fault tolerance; Floods; Hafnium; High performance computing; Hypercubes; Sorting;
Conference_Titel :
Parallel Processing Symposium, 1995. Proceedings., 9th International
Conference_Location :
Santa Barbara, CA
Print_ISBN :
0-8186-7074-6
DOI :
10.1109/IPPS.1995.395950
