Abstract | ||
---|---|---|
Parallel loops account for the greatest percentage of program parallelism. The degree to which parallelism can be exploited and the amount of overhead involved during parallel execution of a nested loop directly depend on partitioning, i.e., the way the different iterations of a parallel loop are distributed across different processors. Thus, partitioning of parallel loops is of key importance for high performance and efficient use of multiprocessor systems. Although a significant amount of work has been done in partitioning and scheduling of rectangular iteration spaces, the problem of partitioning of non-rectangular iteration spaces – e.g. triangular, trapezoidal iteration spaces – has not been given enough attention so far. In this paper, we present a geometric approach for partitioning N-dimensional non-rectangular iteration spaces for optimizing performance on parallel processor systems. Speedup measurements for kernels (loop nests) of linear algebra packages are presented. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/11532378_9 | LCPC |
Keywords | Field | DocType |
different iteration,parallel loop,trapezoidal iteration space,parallel execution,rectangular iteration space,nested loop,loop nest,geometric approach,n-dimensional non-rectangular iteration space,parallel processor system,partitioning n-dimensional non-rectangular iteration,non-rectangular iteration space,linear algebra,nested loops | Linear algebra,Parallel algorithm,CPU cache,Computer science,Scheduling (computing),Parallel computing,Multiprocessing,Convex polytope,Nested loop join,Distributed computing,Speedup | Conference |
Volume | ISSN | ISBN |
3602 | 0302-9743 | 3-540-28009-X |
Citations | PageRank | References |
8 | 0.53 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arun Kejariwal | 1 | 281 | 26.23 |
Paolo D'Alberto | 2 | 136 | 11.24 |
Alexandru Nicolau | 3 | 2265 | 307.74 |
Constantine D. Polychronopoulos | 4 | 893 | 129.02 |