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)
|L. Bougé, P. Fraigniaud, A. Mignotte, Y. Robert
|Place of Publication
|Published - 1996
|Lecture Notes in Computer Science