• DocumentCode
    2634430
  • 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
  • fYear
    1995
  • fDate
    25-28 Apr 1995
  • Firstpage
    312
  • Lastpage
    318
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1995. Proceedings., 9th International
  • Conference_Location
    Santa Barbara, CA
  • Print_ISBN
    0-8186-7074-6
  • Type

    conf

  • DOI
    10.1109/IPPS.1995.395950
  • Filename
    395950
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2634430