%0 Journal Article %1 Feautrier1992-qk %A Feautrier, Paul %D 1992 %I Kluwer Academic Publishers-Plenum Publishers %J Int. J. Parallel Program. %K Expose Polyhedral_transformations %N 5 %P 313--347 %T Some efficient solutions to the affine scheduling problem. I. One-dimensional time %V 21 %X Programs and systems of recurrence equations may be represented as sets of actions which are to be executed subject to precedence constraints. In may cases, actions may be labelled by integral vectors in some iterations domains, and precedence constraints may be described by affine relations. A schedule for such a program is a function which assigns an execution data to each action. Knowledge of such a schedule allows one to estimate the intrinsic degree of parallelism of the program and to compile a parallel version for multiprocessor architectures or systolic arrays. This paper deals with the problem of finding closed form schedules as affine or piecewise affine functions of the iteration vector. An algorithm is presented which reduces the scheduling problem to a parametric linear program of small size, which can be readily solved by an efficient algorithm.

@article{Feautrier1992-qk, abstract = {Programs and systems of recurrence equations may be represented as sets of actions which are to be executed subject to precedence constraints. In may cases, actions may be labelled by integral vectors in some iterations domains, and precedence constraints may be described by affine relations. A schedule for such a program is a function which assigns an execution data to each action. Knowledge of such a schedule allows one to estimate the intrinsic degree of parallelism of the program and to compile a parallel version for multiprocessor architectures or systolic arrays. This paper deals with the problem of finding closed form schedules as affine or piecewise affine functions of the iteration vector. An algorithm is presented which reduces the scheduling problem to a parametric linear program of small size, which can be readily solved by an efficient algorithm.}, added-at = {2015-04-15T09:45:31.000+0200}, author = {Feautrier, Paul}, biburl = {https://www.bibsonomy.org/bibtex/278aec1b843dd3ca23638c6a7848877b0/christophv}, interhash = {9291bef9681777bc30a61447a369e891}, intrahash = {78aec1b843dd3ca23638c6a7848877b0}, journal = {Int. J. Parallel Program.}, keywords = {Expose Polyhedral_transformations}, number = 5, pages = {313--347}, publisher = {Kluwer Academic Publishers-Plenum Publishers}, timestamp = {2016-01-04T14:22:08.000+0100}, title = {Some efficient solutions to the affine scheduling problem. I. One-dimensional time}, volume = 21, year = 1992 }