• DocumentCode
    1988237
  • Title

    Parallel computing dominators on hypercube multiprocessors

  • Author

    Horng, S.J.

  • Author_Institution
    Dept. of Electr. Eng., Nat. Taiwan Inst. of Technol., Taipei, Taiwan
  • fYear
    1993
  • fDate
    27-29 May 1993
  • Firstpage
    240
  • Lastpage
    243
  • Abstract
    Two O(log2 n) time algorithms are proposed for computing the dominators and constructing the dominator tree of a directed acyclic graph, G=(V, E), |V|=n, |E|=m. The parallel computation used is a practical SIMD hypercube multiprocessor with n3 processing elements. The algorithms developed in this paper achieve the same time complexity as those developed on PRAM model (S. Pawagi, 1987), (C. Savage, 1977) but are more practical
  • Keywords
    computational complexity; directed graphs; hypercube networks; parallel algorithms; trees (mathematics); PRAM model; SIMD; directed acyclic graph; dominator tree; hypercube multiprocessor; hypercube multiprocessors; parallel algorithm; parallel computation; parallel computing dominators; time complexity; Algorithm design and analysis; Computational modeling; Concurrent computing; Design optimization; Hypercubes; Optimizing compilers; Parallel processing; Phase change random access memory; Registers; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
  • Conference_Location
    Sudbury, Ont.
  • Print_ISBN
    0-8186-4212-2
  • Type

    conf

  • DOI
    10.1109/ICCI.1993.315371
  • Filename
    315371
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1988237