A two-stage solution approach to multidimensional periodic scheduling

W.F.J. Verhaegh, E.H.L. Aarts, P.C.N. Gorp van, P.E.R. Lippens

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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
Original languageEnglish
Pages (from-to)1185-1199
Number of pages15
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume20
Issue number10
DOIs
Publication statusPublished - 2001
Externally publishedYes

Fingerprint

Linear programming
Scheduling
Subroutines
Digital signal processors
Processing
Throughput
Costs

Cite this

@article{b9f836f2971a4b24b5c89b6063bbdc3f,
title = "A two-stage solution approach to multidimensional periodic scheduling",
abstract = "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",
author = "W.F.J. Verhaegh and E.H.L. Aarts and {Gorp van}, P.C.N. and P.E.R. Lippens",
year = "2001",
doi = "10.1109/43.952736",
language = "English",
volume = "20",
pages = "1185--1199",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "10",

}

A two-stage solution approach to multidimensional periodic scheduling. / Verhaegh, W.F.J.; Aarts, E.H.L.; Gorp van, P.C.N.; Lippens, P.E.R.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 10, 2001, p. 1185-1199.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A two-stage solution approach to multidimensional periodic scheduling

AU - Verhaegh, W.F.J.

AU - Aarts, E.H.L.

AU - Gorp van, P.C.N.

AU - Lippens, P.E.R.

PY - 2001

Y1 - 2001

N2 - 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

AB - 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

U2 - 10.1109/43.952736

DO - 10.1109/43.952736

M3 - Article

VL - 20

SP - 1185

EP - 1199

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 10

ER -