Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis

Lori E. Lucke, Keshab K Parhi

Research output: Contribution to journalArticle

20 Citations (Scopus)

Abstract

Iterative, deterministic, digital signal processing algorithms can be represented by synchronous data-flow graphs. Data-flow graphs are used for scheduling and resource allocation during high-level VLSI synthesis. Every data-flow graph has an associated critical path time which limits the achievable iteration period in critical-path-based scheduling techniques. Unfolding, retiming, and pipelining transformations unravel hidden concurrency within data-flow graphs to reduce their critical path times. The objective of this paper is to determine the minimum unfolding factor necessary to reduce the critical path time of the data-Row graph to less than or equal to the requirediteration period of the associated algorithm. Minimizingthe unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. We present a new iterative unfolding algorithm which calculates the minimum unfolding factor necessaryto achieve a given sample rate. We can further reduce the unfolding factor necessary to achieve a given sample rate. We can further reduce the unfolding factor in many cases with the use of retiming. Our algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.

Original languageEnglish (US)
Pages (from-to)1063-1068
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume12
Issue number7
DOIs
StatePublished - Jan 1 1993

Fingerprint

Data flow graphs
Scheduling
Digital signal processing
Resource allocation

Cite this

@article{6878454fb60142a6a6257f3340b0ab73,
title = "Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis",
abstract = "Iterative, deterministic, digital signal processing algorithms can be represented by synchronous data-flow graphs. Data-flow graphs are used for scheduling and resource allocation during high-level VLSI synthesis. Every data-flow graph has an associated critical path time which limits the achievable iteration period in critical-path-based scheduling techniques. Unfolding, retiming, and pipelining transformations unravel hidden concurrency within data-flow graphs to reduce their critical path times. The objective of this paper is to determine the minimum unfolding factor necessary to reduce the critical path time of the data-Row graph to less than or equal to the requirediteration period of the associated algorithm. Minimizingthe unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. We present a new iterative unfolding algorithm which calculates the minimum unfolding factor necessaryto achieve a given sample rate. We can further reduce the unfolding factor necessary to achieve a given sample rate. We can further reduce the unfolding factor in many cases with the use of retiming. Our algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.",
author = "Lucke, {Lori E.} and Parhi, {Keshab K}",
year = "1993",
month = "1",
day = "1",
doi = "10.1109/43.238043",
language = "English (US)",
volume = "12",
pages = "1063--1068",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis

AU - Lucke, Lori E.

AU - Parhi, Keshab K

PY - 1993/1/1

Y1 - 1993/1/1

N2 - Iterative, deterministic, digital signal processing algorithms can be represented by synchronous data-flow graphs. Data-flow graphs are used for scheduling and resource allocation during high-level VLSI synthesis. Every data-flow graph has an associated critical path time which limits the achievable iteration period in critical-path-based scheduling techniques. Unfolding, retiming, and pipelining transformations unravel hidden concurrency within data-flow graphs to reduce their critical path times. The objective of this paper is to determine the minimum unfolding factor necessary to reduce the critical path time of the data-Row graph to less than or equal to the requirediteration period of the associated algorithm. Minimizingthe unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. We present a new iterative unfolding algorithm which calculates the minimum unfolding factor necessaryto achieve a given sample rate. We can further reduce the unfolding factor necessary to achieve a given sample rate. We can further reduce the unfolding factor in many cases with the use of retiming. Our algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.

AB - Iterative, deterministic, digital signal processing algorithms can be represented by synchronous data-flow graphs. Data-flow graphs are used for scheduling and resource allocation during high-level VLSI synthesis. Every data-flow graph has an associated critical path time which limits the achievable iteration period in critical-path-based scheduling techniques. Unfolding, retiming, and pipelining transformations unravel hidden concurrency within data-flow graphs to reduce their critical path times. The objective of this paper is to determine the minimum unfolding factor necessary to reduce the critical path time of the data-Row graph to less than or equal to the requirediteration period of the associated algorithm. Minimizingthe unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. We present a new iterative unfolding algorithm which calculates the minimum unfolding factor necessaryto achieve a given sample rate. We can further reduce the unfolding factor necessary to achieve a given sample rate. We can further reduce the unfolding factor in many cases with the use of retiming. Our algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.

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

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

U2 - 10.1109/43.238043

DO - 10.1109/43.238043

M3 - Article

VL - 12

SP - 1063

EP - 1068

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

ER -