Scalable and Structured Scheduling |
| |
Authors: | Paul Feautrier |
| |
Affiliation: | (1) LIP, project Compsys, Ecole Normale Supérrieure de Lyon, INRIA, Université Lyon I, Lyon, France |
| |
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 accepts 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. First, a large
program can be divided into smaller units (processes), which can be scheduled separately. This is structured scheduling. Second, one can use projection methods for solving linear programs incrementally. This is specially efficient if the dependence
graph is sparse. |
| |
Keywords: | Structured scheduling automatic parallelization scalability |
本文献已被 SpringerLink 等数据库收录! |
|