A two-stage solution approach to multidimensional periodic scheduling

We present a two-stage solution approach to the multidimensional periodic s cheduling (MPS) problem. This problem originates from the design of high-th roughput digital-signal-processor systems, where highly parallel execution of loops is of utmost importance. We introduce the concept of multidimensio nal periodic operations in order to cope with problems originating from loo p hierarchies and explicit timing requirements. In the first stage of the a pproach, we assign periods to the multidimensional periodic operations such that storage costs are minimized. This is done by means of branch-and-boun d, based on a linear programming and constraint-generation technique. In th e second stage, we assign start times to the operations and determine on wh ich processing units (PUs) they are executed. This is done by means of an i terative approach. The two major subproblems of MPS concerning checking dat a dependency constraints and PU constraints are solved by means of an all-i nteger integer-linear-programming technique. This technique is used as a su broutine in the above two stages. The effectiveness and efficiency of the a pproach are good, which is illustrated by means of some practical examples.