Tiling with limited resources

Pierre-Yves Calland, Jack Dongarra and Yves Robert

 LIP, Ecole Normale Supérieure de Lyon, 69364 Lyon Cedex 07, France
 Department of Computer Science, University of Tennessee, Knoxville, TN 37996-1301, USA
 Mathematical Sciences Section, Oak Ridge National Laboratory, Oak Ridge, TN 37831, USA
e-mail: pycallan@lip.ens-lyon.fr
e-mail: [dongarra, yrobert]@cs.utk.edu

February 1997

Abstract:

In the framework of perfect loop nests with uniform dependences, tiling has been extensively studied as a source-to-source program transformation. Little work has been devoted to the mapping and scheduling of the tiles on to physical processors. We present several new results in the context of limited computational resources, and assuming communication-computation overlap. In particular, under some reasonable assumptions, we derive the optimal mapping and scheduling of tiles to physical processors.

 
• Introduction
• Literature overview
  • Tiling as a loop transformation technique
  • Tiling with resource constraints
  • Discussion
• Allowing for communication-computation overlap
  • On the model
  • Determining the total execution time
  • Optimizing the tile size
  • Optimizing the number of processors
  • Optimal mapping and scheduling
• Conclusion
• References
• About this document ...