Resource-constrained Scheduling of Partitioned Algorithms on Processor Array. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1994

Resource-constrained Scheduling of Partitioned Algorithms on Processor Array.

Résumé

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.
Nous étudions dans ce rapport le partitionnement et le placement de nids de boucles uniformes sur des tableaux de processeurs. les contraintes liées aux ressources sont prises en compte : non seulement nous supposons disposer d'un nombre fini de processeurs, mais également que les capacités de communication des processeurs sont limitées ( en particulier, le nombre de liens de communications dans chaque direction est bornée). les récentes travaux de Chou et Kung et de Thiele sont à l'origine de ce travail. Nos principales contributions résident dans la reformulation d'une problème complexe d'optimisation en un problème de programmation linéaire, ainsi que dans des algorithmes d'ordonnancement et des résultats de complexité dans le cas de tableaux linéaires de processeurs
Fichier principal
Vignette du fichier
RR1994-19.pdf (356.34 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101776 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101776 , version 1

Citer

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⟩
42 Consultations
64 Téléchargements

Partager

Gmail Facebook X LinkedIn More