We discuss the multidimensional periodic scheduling problem, which originates from the design of high-throughput real-time digital signal processing systems. We introduce the concept of multidimensional periodic operations in order to cope with problems originating from loop hierarchies and explicit timing requirements. We present a model of the multidimensional periodic scheduling problem and show that this problem and two related sub-problems are NP-hard. Furthermore, we identify several special cases induced by practical situations. Some of these special cases are proven to be well-solvable. Finally, we present a sketch of a solution approach.
|Title of host publication||Euro-Par'96 Parallel Processing (Proceedings, Lyon, France, August 26-29, 1996)|
|Editors||L. Bougé, P. Fraigniaud, A. Mignotte, Y. Robert|
|Place of Publication||Berlin|
|Publication status||Published - 1996|
|Name||Lecture Notes in Computer Science|