Title :
Parallel computing dominators on hypercube multiprocessors
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Inst. of Technol., Taipei, Taiwan
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;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315371
