loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
3rd Euromicro Workshop on Parallel and Distributed Processing
Resource-constrained scheduling of partitioned algorithms on processor arrays
San Remo, Italy
January 25-January 27
ISBN: 0-8186-7031-2
M. Dion, Lab. LIP-IMAG, Ecole Normale Superieure de Lyon, France
T. Risset, Lab. LIP-IMAG, Ecole Normale Superieure de Lyon, France
Y. Robert, Lab. LIP-IMAG, Ecole Normale Superieure de Lyon, France
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.
Index Terms:
scheduling; linear programming; optimisation; computational complexity; resource-constrained scheduling; partitioned algorithms; processor arrays; mapping; physical processor arrays; communication capabilities; communication links; complex optimization problem; single integer linear programming problem; optimal scheduling algorithms; complexity; linear processor arrays
Citation:
M. Dion, T. Risset, Y. Robert, "Resource-constrained scheduling of partitioned algorithms on processor arrays," pdp, pp.571, 3rd Euromicro Workshop on Parallel and Distributed Processing, 1995
Usage of this product signifies your acceptance of the Terms of Use.