Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Task Ordering in Linear Tiles.

Abstract : In this report we address the issue of loop tiling to minimize the completion time of the loop when executed on multicomputers. We remove the restriction of atomicity of tiles and internal parallelism within tiles is exploited by overlapping computation with communication. The effectiveness of tiling is then critically dependent on the execution order of tasks within a tile. In this paper we present a theoretical framework based on equivalence classes that provides an optimal task ordering under assumptions of constant and different permutations of tasks in individual tiles. Our framework is able to handle constant but compile-time unknown dependences by generating optimal task permutations at run-time and results in significantly lower loop completion times. Our solution is an improvement over previous approaches and is optimal for all problem instances. We also propose efficient algorithms that provide the optimal solution. The framework has been implemented as an optimization pass in the SUIF compiler and has been tested on distributed and shared memory systems using a message passing model. We show that the performance improvement over previous results is substantial.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:11:30 AM
Last modification on : Wednesday, October 26, 2022 - 8:14:45 AM


Files produced by the author(s)


  • HAL Id : hal-02101991, version 1



Fabrice Rastello, Amit Rao, Santosh Pande. Task Ordering in Linear Tiles.. [Research Report] LIP RR-1998-11, Laboratoire de l'informatique du parallélisme. 1998, 2+20p. ⟨hal-02101991⟩



Record views


Files downloads