[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.167-190 (March 1998)
Determining the Idle Time of a Tiling: New Results *

FrJISEdJISEric Desprez, Jack Dongarra#, +, Fabrice Rastello and Yves Robert#
 LIP, Ecole Normale Superieure de Lyon
69364 Lyon Cedex 07, France
# Department of Computer Science
University of Tennessee
Knoxville, TN 37996-1301, U.S.A.
+ Mathematical Sciences Section
Oak Ridge National Laboratory
Oak Ridge, TN 37831, U.S.A.

In the framework of fully permutable loops, tiling has been studied extensively as a source-to-source program transformation. We build upon recent results by Hsted, Carter, and Ferrante [12], who aimed at determining the cumulated idle time spent by all processors while executing the partitioned (tiled) computation domain. We propose new, much shorter proofs of all their results and extend these in several important directions. More precisely, we provide an accurate solution for all values of the rise parameter that relates the shape of the iteration space to that of the tiles, and for all possible distributions of the tiles to processors. In contrast, the authors in [12] dealt only with a limited number of cases and provided upper bounds rather than exact formulas.

Keywords: distributed arrays, redistribution, block-cyclic distribution, scheduling, MPI (Message Passing Interface), HFP (High Performance Fortran)

Received May 1, 1997; revised October 31, 1997.
Communicated by Chau-Huang Huang
*

  • This work was supported in part by the National Science Foundation under Grant No. ASC-9005933.
  • This work was supported in part by the Defense Advanced Research Projects Agency under contract DAAH04-95-1-0077, administered by the Army Research Office.
  • This work was supported in part by the Office of Scientific Computing, U.S. Department of Energy, under Contract DE-AC05-96OR22464.
  • This work was supported in part by the National Science Foundation Science and Technology Center under Cooperative Agreement No. CCR-8809615.
  • This work was supported in part by the CNRS-ENS Lyon-INRIA project ReMaP.
  • This work was supported in part by the Eureka Project Euro TOPS.
  • This work was done while Yves Robert was on leave from Ecole Normale Superieure de Lyon and partly supported by DRET/DGA under contract ERE 96-1104/A000/DRET/DS/SR.