%0 Journal Article %1 Feautrier1992-vq %A Feautrier, Paul %D 1992 %I Kluwer Academic Publishers-Plenum Publishers %J Int. J. Parallel Program. %K Expose Polyhedral_transformations %N 6 %P 389--420 %T Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time %V 21 %X This paper extends the algorithms which were developed in Part I to cases in which there is no affine schedule, i.e. to problems whose parallel complexity is polynomial but not linear. The natural generalization is to multidimensional schedules with lexicographic ordering as temporal succession. Multidimensional affine schedules, are, in a sense, equivalent to polynomial schedules, and are much easier to handle automatically. Furthermore, there is a strong connection between multidimensional schedules and loop nests, which allows one to prove that a static control program always has a multidimensional schedule. Roughly, a larger dimension indicates less parallelism. In the algorithm which is presented here, this dimension is computed dynamically, and is just sufficient for scheduling the source program. The algorithm lends itself to a ``divide and conquer'' strategy. The paper gives some experimental evidence for the applicability, performances and limitations of the algorithm.

@article{Feautrier1992-vq, abstract = {This paper extends the algorithms which were developed in Part I to cases in which there is no affine schedule, i.e. to problems whose parallel complexity is polynomial but not linear. The natural generalization is to multidimensional schedules with lexicographic ordering as temporal succession. Multidimensional affine schedules, are, in a sense, equivalent to polynomial schedules, and are much easier to handle automatically. Furthermore, there is a strong connection between multidimensional schedules and loop nests, which allows one to prove that a static control program always has a multidimensional schedule. Roughly, a larger dimension indicates less parallelism. In the algorithm which is presented here, this dimension is computed dynamically, and is just sufficient for scheduling the source program. The algorithm lends itself to a ``divide and conquer'' strategy. The paper gives some experimental evidence for the applicability, performances and limitations of the algorithm.}, added-at = {2015-04-15T09:45:31.000+0200}, author = {Feautrier, Paul}, biburl = {https://www.bibsonomy.org/bibtex/27d9f6991629fefb9ec5112f8109ec392/christophv}, interhash = {e1891f3ee4a66b1d5606856310d90a2f}, intrahash = {7d9f6991629fefb9ec5112f8109ec392}, journal = {Int. J. Parallel Program.}, keywords = {Expose Polyhedral_transformations}, number = 6, pages = {389--420}, publisher = {Kluwer Academic Publishers-Plenum Publishers}, timestamp = {2016-01-04T14:22:08.000+0100}, title = {Some efficient solutions to the affine scheduling problem. Part {II}. Multidimensional time}, volume = 21, year = 1992 }