Resource-constrained Scheduling of Partitioned Algorithms on Processor Array.

Abstract : We deal with the problem of partitioning and mapping uniform loop nests onto physical processor arrays. Resource constraints are taken into account: not only we assume a limited number of available processors, but we also assume that the communication capabilities of the physical processors are restricted (in particular, the number of communication links in each direction is bounded). This paper is motivated by the recent work of Chou and Kung and of Thiele. Our main contributions are a new formulation of the complex optimization problem to be solved in terms of a single integer linear programming problem, as well as optimal scheduling algorithms and complexity results in the case of linear processor arrays.
Document type :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101776
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:05:59 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:14 AM

File

RR1994-19.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101776, version 1

Collections

Citation

Michèle Dion, Tanguy Risset, Yves Robert. Resource-constrained Scheduling of Partitioned Algorithms on Processor Array.. [Research Report] LIP RR-1994-19, Laboratoire de l'informatique du parallélisme. 1994, 2+29p. ⟨hal-02101776⟩

Share

Metrics

Record views

29

Files downloads

17