DocumentCode :
3243865
Title :
A heuristic approach for finding a solution to the constant-degree parallelism alignment problem
Author :
Diderich, Claude G. ; Gengler, Marc
Author_Institution :
Dept. of Comput. Sci., Swiss Federal Inst. of Technol., Lausanne, Switzerland
fYear :
1996
fDate :
35339
Firstpage :
127
Lastpage :
132
Abstract :
Two important aspects have to be addressed when automatically parallelizing loop nests for massively parallel distributed memory computers, namely maximizing parallelism and minimizing communication overhead due to non-local data accesses. This paper studies the problem of finding a computation mapping and data distributions that minimize the number of remote data accesses for a given degree of parallelism. This problem is called the constant-degree parallelism alignment problem. The heuristic presented uses a linear algebra framework and assumes affine data access functions. It proceeds by incrementally building a basis of the set of vectors representing the alignments between computation and data accesses that should be satisfied. The heuristic algorithm is applied to benchmark programs and shown superior to more basic mappings
Keywords :
distributed memory systems; linear algebra; minimisation; parallel machines; parallel programming; parallelising compilers; program control structures; affine data access functions; benchmark programs; communication overhead minimization; computation mapping; constant-degree parallelism alignment problem; data distributions; heuristic approach; linear algebra; loop nests; massively parallel distributed memory computers; nonlocal data access; parallelism maximisation; remote data access; vectors; Computer architecture; Computer science; Concurrent computing; Costs; Distributed computing; Heuristic algorithms; Linear algebra; Message passing; Parallel processing; Vectors;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Architectures and Compilation Techniques, 1996., Proceedings of the 1996 Conference on
Conference_Location :
Boston, MA
ISSN :
1089-795X
Print_ISBN :
0-8186-7633-7
Type :
conf
DOI :
10.1109/PACT.1996.552656
Filename :
552656
Link To Document :
بازگشت