Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|
High Performance Computing | ||||||||
Changed: | ||||||||
< < |
Parallel SystemsThe main objective of this activity is to combine the advantages of distributed memory architectures (scalability) and the advantages of the shared memory programming paradigm (easy and secure programming). Other relevant activities are the automatic extraction of parallelism and the subsequent mapping of algorithms onto different types of parallel architectures. In this context, our research has focused on applying transformations to nested for-loops, in order to efficiently execute them in Non-Uniform Memory Access (NUMA) machines, such as the SCI-Clusters of the laboratory. In particular, we apply a transformation called tiling, or supernode transformation in order to minimize the communication latency effect on the total parallel execution time of the algorithms. Tiling method groups neighboring computation points of the nested loop into blocks called tiles or supernodes thus increasing the computation grain and decreasing both the communication volume and frequence. Applying the tiling techniques, we have developped a tool, which accepts C-like nested loops and partitions them into groups/tiles with small inter-communication requirements. The tool automatically generates efficient message passing code (using MPI) to be executed on SMPs or clusters. Future work contains comprarisons of certain variations of tiling (shape, size, etc) and code generation tecniques based on experimental results taken from the application of the tool on an SCI-cluster. In addition, we explore several methods such as overlapping of communication and computations, in order to further reduce the total execution time of the transformed code. The targeted communication platforms include SCI, GM message passing over Myrinet interconnect, etc. | |||||||
> > | The main objective of our group in this research area is to optimize critical software (mainly computationally or memory intensive applications) executing on high performance computing platforms. To achieve this intricate goal we need to delve as deeply as possible into the core characteristics of the applications and the underlying architecture. We focus on stencil computations, Sparse Matrix-Vector Multiplication SPMV, PDE solvers, graph algorithms and others. As far as the computing platforms are concerned, we work on PC clusters, multicore and multithreaded (SMT) microprocessors, and emerging architectures like GPGPUs and the CELL B/E. | |||||||
Publications | ||||||||
Changed: | ||||||||
< < |
This paper proposes a new method for the problem of
minimizing the execution time of nested for-loops using a
tiling transformation. In our approach, we are interested
not only in tile size and shape according to the required
communication to computation ratio, but also in overall
completion time. We select a time hyperplane to execute
different tiles much more efficiently by exploiting the inherent
overlapping between communication and computation
phases among successive, atomic tile executions. We assign
tiles to processors according to the tile space boundaries,
thus considering the iteration space bounds. Our schedule
considerably reduces overall completion time under the assumption
that some part from every communication phase
can be efficiently overlapped with atomic, pure tile computations.
The overall schedule resembles a pipelined datapath
where computations are not anymore interleaved with
sends and receives to non-local processors. Experimental
results in a cluster of Pentiums by using various MPI send
primitives show that the total completion time is significantly
reduced.
| |||||||
> > |
|
Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|
Deleted: | ||||||||
< < |
| |||||||
High Performance ComputingParallel Systems |
Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|
High Performance Computing | ||||||||
Line: 40 to 40 | ||||||||
| ||||||||
Deleted: | ||||||||
< < | -- ArisSotiropoulos - 06 Mar 2008 |
Line: 1 to 1 | ||||||||
---|---|---|---|---|---|---|---|---|
Added: | ||||||||
> > |
High Performance ComputingParallel SystemsThe main objective of this activity is to combine the advantages of distributed memory architectures (scalability) and the advantages of the shared memory programming paradigm (easy and secure programming). Other relevant activities are the automatic extraction of parallelism and the subsequent mapping of algorithms onto different types of parallel architectures. In this context, our research has focused on applying transformations to nested for-loops, in order to efficiently execute them in Non-Uniform Memory Access (NUMA) machines, such as the SCI-Clusters of the laboratory. In particular, we apply a transformation called tiling, or supernode transformation in order to minimize the communication latency effect on the total parallel execution time of the algorithms. Tiling method groups neighboring computation points of the nested loop into blocks called tiles or supernodes thus increasing the computation grain and decreasing both the communication volume and frequence. Applying the tiling techniques, we have developped a tool, which accepts C-like nested loops and partitions them into groups/tiles with small inter-communication requirements. The tool automatically generates efficient message passing code (using MPI) to be executed on SMPs or clusters. Future work contains comprarisons of certain variations of tiling (shape, size, etc) and code generation tecniques based on experimental results taken from the application of the tool on an SCI-cluster. In addition, we explore several methods such as overlapping of communication and computations, in order to further reduce the total execution time of the transformed code. The targeted communication platforms include SCI, GM message passing over Myrinet interconnect, etc.Publications
This paper proposes a new method for the problem of
minimizing the execution time of nested for-loops using a
tiling transformation. In our approach, we are interested
not only in tile size and shape according to the required
communication to computation ratio, but also in overall
completion time. We select a time hyperplane to execute
different tiles much more efficiently by exploiting the inherent
overlapping between communication and computation
phases among successive, atomic tile executions. We assign
tiles to processors according to the tile space boundaries,
thus considering the iteration space bounds. Our schedule
considerably reduces overall completion time under the assumption
that some part from every communication phase
can be efficiently overlapped with atomic, pure tile computations.
The overall schedule resembles a pipelined datapath
where computations are not anymore interleaved with
sends and receives to non-local processors. Experimental
results in a cluster of Pentiums by using various MPI send
primitives show that the total completion time is significantly
reduced.
|