Scalable and Modular Scheduling

Paul Feautrier 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Scheduling a program (i.e. constructing a timetable for the execution of its operations) is one of the most powerful methods for automatic parallelization. A schedule gives a blueprint for constructing a synchronous program, suitable for an ASIC or VLIW processor. However, constructing a schedule entails solving a large linear program. Even if one accept the (experimental) fact that the Simplex is almost always polynomial, the scheduling time is of the order of a large power of the program size. Hence, the method does not scale well. The present paper proposes two methods for improving the situation. Firstly, a big program can be divided in smaller units (processes) which can be scheduled separately. This is modular scheduling Second, one can use projection methods for solving linear programs incrementatly. This is specially efficient if the dependence graph is sparse.
Document type :
Reports
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071408
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:18:55 PM
Last modification on : Wednesday, November 20, 2019 - 3:05:19 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:11:08 PM

Identifiers

  • HAL Id : inria-00071408, version 1

Collections

Citation

Paul Feautrier. Scalable and Modular Scheduling. RR-5180, INRIA. 2004. ⟨inria-00071408⟩

Share

Metrics

Record views

211

Files downloads

307