Title :
Designing parallel algorithms from forests and multistage graphs
Author :
Chen, G.H. ; Chern, Maw-Sheng
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
The data dependence graph (DDG) is a tool for parallelism detection, which is essential to parallel algorithm design. The authors consider a three-stage procedure for designing parallel algorithms for a given problem: finding a solution method for the given problem; constructing a DDG for the solution method; and designing parallel algorithms from the DDG. They propose some design approaches for two classes of DDGs: the forest and the multistage graph.<>
Keywords :
graph theory; graphs; parallel algorithms; systems analysis; DDG; data dependence graph; design approaches; forest; graph-theoretic algorithm design procedure; multistage graph; parallel algorithm design; parallelism detection; programming tool; solution method; Algorithm design and analysis; Computer science; Concurrent computing; Data engineering; Design engineering; Design methodology; Difference equations; Parallel algorithms; Parallel processing; Signal design;
Conference_Titel :
Computer Software and Applications Conference, 1988. COMPSAC 88. Proceedings., Twelfth International
Conference_Location :
Chicago, IL, USA
Print_ISBN :
0-8186-0873-0
DOI :
10.1109/CMPSAC.1988.17188
