Multidimensional periodic scheduling model and complexity

W.F.J. Verhaegh, P.E.R. Lippens, E.H.L. Aarts, J. Meerbergen, van, A. Werf, van der

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationEuro-Par'96 Parallel Processing (Proceedings, Lyon, France, August 26-29, 1996)
EditorsL. Bougé, P. Fraigniaud, A. Mignotte, Y. Robert
Place of PublicationBerlin
PublisherSpringer
Pages226-235
Volume2
ISBN (Print)3-540-61627-6
DOIs
Publication statusPublished - 1996

Publication series

NameLecture Notes in Computer Science
Volume1124
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Multidimensional periodic scheduling model and complexity'. Together they form a unique fingerprint.

Cite this