• DocumentCode
    1830472
  • Title

    Total exchange in faulty SIMD hypercubes

  • Author

    Sengupta, Amit ; Raghavendra, C.S.

  • Author_Institution
    Sch. of Electr. Eng. & Comput. Sci., Washington State Univ., Pullman, WA, USA
  • fYear
    1994
  • fDate
    26-29 Apr 1994
  • Firstpage
    853
  • Lastpage
    857
  • Abstract
    We develop algorithms for performing total exchange (all-to-all broadcast) in an n-dimensional faulty SIMD hypercube, Qn, with up to n-1 node faults. In an SIMD hypercube, during a communication step, nodes can exchange information with their neighbors only across a specific dimension. We describe a sequence of algorithms which take N log N, N log n, 3N-7, 2.5N-7 steps for this problem. By carefully analyzing these algorithms and a property of certain ordering of dimensions, we obtain an improved algorithm which takes 2N steps
  • Keywords
    hypercube networks; performance evaluation; all-to-all broadcast; faulty SIMD hypercubes; total exchange; Algorithm design and analysis; Broadcasting; Change detection algorithms; Computer science; Electronic mail; Fault detection; Fault tolerance; High performance computing; Hypercubes; Robustness;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1994. Proceedings., Eighth International
  • Conference_Location
    Cancun
  • Print_ISBN
    0-8186-5602-6
  • Type

    conf

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