StencilComputations < CSLab

CSLab Web>ActivitiesProjects>StencilComputations (2008-03-11, VangelisKoukis) (raw view)
---++ Stencil Computations

The main objective of this activity is to optimize stencil computations for Cluster platforms with commodity (e.g. Gbit Ethernet) or sophisticated (e.g. SCI, Myrinet) interconnects. In this context, our research has focused on applying the tiling (or supernode) loop transformation to stencils 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. Within the domain of stencil computations, nested loops and tiling transformation, our group has coped with several problems. Efficient scheduling techniques of tiled stencil applications that enable communication to computation overlap have been investigated, presented and awarded as one of the four best papers in [[http://www.ipdps.org/ipdps2001/][IPDPS'01]]  ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/ipdps2001.pdf][pdf]]). Automatic parallelization and efficient code generation methods have been proposed in [[http://www.computer.org/tpds/][TPDS]]  ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/tpds2003.pdf][pdf]]) and [[http://www.elsevier.com/wps/locate/parco/][Parallel Computing]]  ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/parco2006.pdf][pdf]]). Hybrid (MPI + !OpenMP)  parallel implementations of tiled stencil computations have been presented in [[http://www.inderscience.com/ijcse/][IJCSE]]  ([[http://www.cslab.ece.ntua.gr/~ndros/publications/ijcse2007.pdf][pdf]]). 


---++ Publications 
   * G. Goumas, A. Sotiropoulos, N. Koziris, &ldquo;Minimizing Completion Time for Loop Tiling with Computation and Communication Overlapping,&rdquo; Proceedings of the 2001 International Parallel and Distributed Processing Symposium (IPDPS2001), IEEE Press, San Francisco, California, April  2001 (*Best paper award*) ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/ipdps01.pdf][pdf]])
<i><div style="margin-left: 80px; margin-right: 80px; text-align: justify;">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.</div></i>

   * N. Drosinos and N. Koziris, &ldquo;Efficient Hybrid Parallelization of Tiled Algorithms on SMP Clusters,&rdquo; International Journal of Computational Science and Engineering,  2007 ([[http://www.cslab.ece.ntua.gr/~ndros/publications/ijcse2007.pdf][pdf]])
   * G. Goumas, N. Drosinos, M. Athanasaki and N. Koziris, &ldquo;Message-Passing Code Generation for Non-rectangular Tiling Transformations,&rdquo; Journal of Parallel Computing, pp. 711--732, 32(10), November 2006 ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/parco2006.pdf][pdf]])
   * N. Drosinos, G. Goumas and N. Koziris, &ldquo;Selecting the Tile Shape to Reduce the Total Communication Volume,&rdquo; Proceedings of the 2006 International Parallel and Distributed Processing Symposium (IPDPS2006), Rhodes Island, Greece, 25-29 April, 2006 ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/ipdps2006.pdf][pdf]])
   * M. Athanasaki, A. Sotiropoulos, G. Tsoukalas, N. Koziris, P. Tsanakas, &ldquo;Hyperplane Grouping and Pipelined Schedules: How to Execute Tiled Loops Fast on Clusters of SMPs,&rdquo; The Journal of Supercomputing, Volume 33, Issue 3, September 2005, pp. 197 - 226 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/jsc2005.pdf][pdf]])
   * N. Drosinos and N. Koziris, &ldquo;Performance Comparison of Pure MPI vs Hybrid MPI-OpenMP Parallelization Models on SMP Clusters,&rdquo; Proceedings of the 18th International Parallel & Distributed Processing Symposium (IPDPS 2004), p. 15a (CD-ROM), Santa Fe, New Mexico, April 2004 ([[http://www.cslab.ece.ntua.gr/~ndros/publications/ipdps2004.pdf][pdf]])
   * M. Athanasaki, E. Koukis, N. Koziris, &ldquo;Scheduling of Tiled Nested Loops onto a Cluster with a Fixed Number of SMP Nodes,&rdquo; 12th Euromicro Conference on Parallel, Distributed and Network based Processing (PDP '04), pp.424-433, A Coruna, Spain, February 11-13, 2004 ([[http://www.cslab.ece.ntua.gr/~vkoukis/papers/01271475.pdf][pdf]])
   * N. Koziris, A. Sotiropoulos, G. Goumas, &ldquo;A Pipelined Schedule to Minimize Comple-tion Time for Loop Tiling with Computation and Communication Overlapping,&rdquo; Journal of Parallel and Distributed Computing, Volume 63, Issue 11, November 2003, pp. 1138-1151 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/jpdc2003.pdf][pdf]])
   * M. Athanasaki, E. Koukis, N. Koziris, &ldquo;Efficient Scheduling of Tiled Iteration Spaces onto a Fixed Size Parallel Architecture,&rdquo; 9th Panhellenic Conference in Informatics, pp.178-192, Thessaloniki, Greece, November 21-23, 2003 ([[http://www.cslab.ece.ntua.gr/~vkoukis/papers/epy2003.pdf][pdf]])
   * G. Goumas, M. Athanasaki and N. Koziris, &ldquo;An Efficient Code Generation Technique for Tiled Iteration Spaces,&rdquo; IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No 10, October 2003 ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/tpds2003.pdf][pdf]])
   * A. Sotiropoulos, G. Tsoukalas, N. Koziris, &ldquo;Efficient Utilization of Memory Mapped NICs onto Clusters using Pipelined Schedules,&rdquo; Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, Berlin, Germany, May 2002 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/ccgrid2002.pdf][pdf]])
   * A. Sotiropoulos, G. Tsoukalas, N. Koziris, &ldquo;Enhancing the Performance of Tiled Loop Execution onto Clusters using Memory Mapped Interfaces and Pipelined Schedules,&rdquo; Proceedings of the 2002 Workshop on Communication Architecture for Clusters (CAC2002) held in conjunction with Int'l Parallel and Distributed Processing Symposium (IPDPS2002), Fort Lauderdale, Florida, April 2002 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/cac2002.pdf][pdf]])
   * M. Athanasaki, A. Sotiropoulos, G. Tsoukalas, N. Koziris, &ldquo;Pipelined Scheduling of Tiled Nested Loops onto Clusters of SMPs using Memory Mapped Network Interfaces,&rdquo; Proceedings of the ACM/IEEE Supercomputing 2002: High Performance Networking and Computing Conference (SC2002), Baltimore, Maryland, November 2002 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/sc2002.pdf][pdf]])
   * M. Athanasaki, A. Sotiropoulos, G. Tsoukalas, N. Koziris, &ldquo;A Pipelined Execution of Tiled Nested Loops on SMPs with Computation and Communication Overlapping,&rdquo; Proceedings of the Workshop on Compile/Runtime Techniques for Parallel Computing, held in conjunction with 2002 International Conference on Parallel Processing (ICPP-2002), Vancouver, Canada, August 2002 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/icpp2002.pdf][pdf]])
   * A. Sotiropoulos, G. Tsoukalas, N. Koziris, &ldquo;A Pipelined Execution of Tiled Nested Loops onto a Cluster of PCs using PCI-SCI NICs,&rdquo; Proceedings of the 2001 SCI-Europe Conference, Dublin, Ireland, October 2001 ([[http://www.cslab.ece.ntua.gr/~sotirop/papers/sci-europe2001.ps][ps]])
Topic revision: r5 - 2008-03-11 - VangelisKoukis
CSLab
Research

Courses

CSLab

Home
People
No permission to view TWiki.WebLeftBarWebsList
No permission to view TWiki.WebTopBar
No permission to view TWiki.WebBottomBar