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
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101991
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:11:30 AM
Last modification on : Wednesday, November 20, 2019 - 7:24:07 AM

File

RR1998-11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101991, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

5

Files downloads

14