We present a two-stage solution approach to the multidimensional periodic scheduling (MPS) problem. This problem originates from the design of high-throughput digital-signal-processor systems, where highly parallel execution of loops is of utmost importance. We introduce the concept of multidimensional periodic operations in order to cope with problems originating from loop hierarchies and explicit timing requirements. In the first stage of the approach, we assign periods to the multidimensional periodic operations such that storage costs are minimized. This is done by means of branch-and-bound, based on a linear programming and constraint-generation technique. In the second stage, we assign start times to the operations and determine on which processing units (PUs) they are executed. This is done by means of an iterative approach. The two major subproblems of MPS concerning checking data dependency constraints and PU constraints are solved by means of an all-integer integer-linear-programming technique. This technique is used as a subroutine in the above two stages. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical examples.

Article Period assignment in multidimensional periodic scheduling Share on Authors: Wim F. J. Verhaegh Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The NetherlandsView Profile , Emile H. L. Aarts Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands, and Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Philips Research Laboratories, Prof. Holstlaan 4, 5656 AA Eindhoven, The Netherlands, and Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile , Paul C. N. van Gorp Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The NetherlandsView Profile Authors Info & Claims ICCAD '98: Proceedings of the 1998 IEEE/ACM international conference on Computer-aided designNovember 1998 Pages 585–592https://doi.org/10.1145/288548.289090Published:01 November 1998 2citation134DownloadsMetricsTotal Citations2Total Downloads134Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access