Exhaustive scheduling and retiming of digital signal processing systems

Tracy C. Denk, Keshab K Parhi

Research output: Contribution to journalArticle

24 Citations (Scopus)

Abstract

Scheduling and retiming are important techniques used in the design of hardware and software implementations of digital signal processing algorithms. In this paper, techniques are developed for generating all scheduling and retiming solutions for a strongly connected data-flow graph, allowing a designer to explore the space of possible implementations. Formulations are developed for two scheduling problems. The first scheduling problem assumes a bit-parallel target architecture. The formulation for this problem is general because it considers retiming the data-flow graph as part of scheduling, and this formulation reduces to the retiming formulation as a special case. The second scheduling problem assumes a bit-serial target architecture. Based on these formulations, the conditions for a legal scheduling solution are derived, and a systematic technique is presented for exhaustively generating all legal scheduling solutions for a strongly connected data-flow graph. Since retiming is a special case of scheduling, this systematic technique can also be used for exhaustively generating all legal retiming solutions. A technique is also developed for exhaustively generating only those bit-parallel schedules which satisfy a given set of resource constraints. The techniques for exhaustively generating scheduling and retiming solutions are demonstrated for several filters. For example, we show that a simple filter such as the biquad has 224 possible retiming solutions for a latency of one time unit. We also show that a fifth-order wave digital elliptic filter has 4.7 million and 580 million scheduling solutions for iteration periods of 17 and 18, respectively.

Original languageEnglish (US)
Pages (from-to)821-838
Number of pages18
JournalIEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing
Volume45
Issue number7
DOIs
StatePublished - Dec 1 1998

Fingerprint

Digital signal processing
Scheduling
Data flow graphs
Elliptic filters
Digital filters
Hardware

Keywords

  • Data flow graphs
  • High-level synthesis
  • Parallel architectures
  • Retiming
  • Scheduling
  • Signal processing
  • Very large scale integration

Cite this

Exhaustive scheduling and retiming of digital signal processing systems. / Denk, Tracy C.; Parhi, Keshab K.

In: IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, Vol. 45, No. 7, 01.12.1998, p. 821-838.

Research output: Contribution to journalArticle

@article{10bd1f865c2244c599eac4d2785191c3,
title = "Exhaustive scheduling and retiming of digital signal processing systems",
abstract = "Scheduling and retiming are important techniques used in the design of hardware and software implementations of digital signal processing algorithms. In this paper, techniques are developed for generating all scheduling and retiming solutions for a strongly connected data-flow graph, allowing a designer to explore the space of possible implementations. Formulations are developed for two scheduling problems. The first scheduling problem assumes a bit-parallel target architecture. The formulation for this problem is general because it considers retiming the data-flow graph as part of scheduling, and this formulation reduces to the retiming formulation as a special case. The second scheduling problem assumes a bit-serial target architecture. Based on these formulations, the conditions for a legal scheduling solution are derived, and a systematic technique is presented for exhaustively generating all legal scheduling solutions for a strongly connected data-flow graph. Since retiming is a special case of scheduling, this systematic technique can also be used for exhaustively generating all legal retiming solutions. A technique is also developed for exhaustively generating only those bit-parallel schedules which satisfy a given set of resource constraints. The techniques for exhaustively generating scheduling and retiming solutions are demonstrated for several filters. For example, we show that a simple filter such as the biquad has 224 possible retiming solutions for a latency of one time unit. We also show that a fifth-order wave digital elliptic filter has 4.7 million and 580 million scheduling solutions for iteration periods of 17 and 18, respectively.",
keywords = "Data flow graphs, High-level synthesis, Parallel architectures, Retiming, Scheduling, Signal processing, Very large scale integration",
author = "Denk, {Tracy C.} and Parhi, {Keshab K}",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/82.700929",
language = "English (US)",
volume = "45",
pages = "821--838",
journal = "IEEE Transactions on Circuits and Systems II: Express Briefs",
issn = "1549-8328",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - Exhaustive scheduling and retiming of digital signal processing systems

AU - Denk, Tracy C.

AU - Parhi, Keshab K

PY - 1998/12/1

Y1 - 1998/12/1

N2 - Scheduling and retiming are important techniques used in the design of hardware and software implementations of digital signal processing algorithms. In this paper, techniques are developed for generating all scheduling and retiming solutions for a strongly connected data-flow graph, allowing a designer to explore the space of possible implementations. Formulations are developed for two scheduling problems. The first scheduling problem assumes a bit-parallel target architecture. The formulation for this problem is general because it considers retiming the data-flow graph as part of scheduling, and this formulation reduces to the retiming formulation as a special case. The second scheduling problem assumes a bit-serial target architecture. Based on these formulations, the conditions for a legal scheduling solution are derived, and a systematic technique is presented for exhaustively generating all legal scheduling solutions for a strongly connected data-flow graph. Since retiming is a special case of scheduling, this systematic technique can also be used for exhaustively generating all legal retiming solutions. A technique is also developed for exhaustively generating only those bit-parallel schedules which satisfy a given set of resource constraints. The techniques for exhaustively generating scheduling and retiming solutions are demonstrated for several filters. For example, we show that a simple filter such as the biquad has 224 possible retiming solutions for a latency of one time unit. We also show that a fifth-order wave digital elliptic filter has 4.7 million and 580 million scheduling solutions for iteration periods of 17 and 18, respectively.

AB - Scheduling and retiming are important techniques used in the design of hardware and software implementations of digital signal processing algorithms. In this paper, techniques are developed for generating all scheduling and retiming solutions for a strongly connected data-flow graph, allowing a designer to explore the space of possible implementations. Formulations are developed for two scheduling problems. The first scheduling problem assumes a bit-parallel target architecture. The formulation for this problem is general because it considers retiming the data-flow graph as part of scheduling, and this formulation reduces to the retiming formulation as a special case. The second scheduling problem assumes a bit-serial target architecture. Based on these formulations, the conditions for a legal scheduling solution are derived, and a systematic technique is presented for exhaustively generating all legal scheduling solutions for a strongly connected data-flow graph. Since retiming is a special case of scheduling, this systematic technique can also be used for exhaustively generating all legal retiming solutions. A technique is also developed for exhaustively generating only those bit-parallel schedules which satisfy a given set of resource constraints. The techniques for exhaustively generating scheduling and retiming solutions are demonstrated for several filters. For example, we show that a simple filter such as the biquad has 224 possible retiming solutions for a latency of one time unit. We also show that a fifth-order wave digital elliptic filter has 4.7 million and 580 million scheduling solutions for iteration periods of 17 and 18, respectively.

KW - Data flow graphs

KW - High-level synthesis

KW - Parallel architectures

KW - Retiming

KW - Scheduling

KW - Signal processing

KW - Very large scale integration

UR - http://www.scopus.com/inward/record.url?scp=0032117669&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032117669&partnerID=8YFLogxK

U2 - 10.1109/82.700929

DO - 10.1109/82.700929

M3 - Article

VL - 45

SP - 821

EP - 838

JO - IEEE Transactions on Circuits and Systems II: Express Briefs

JF - IEEE Transactions on Circuits and Systems II: Express Briefs

SN - 1549-8328

IS - 7

ER -