### 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 language | English (US) |
---|---|

Pages (from-to) | 1063-1068 |

Number of pages | 6 |

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

Volume | 12 |

Issue number | 7 |

DOIs | |

State | Published - Jan 1 1993 |

### Fingerprint

### Cite this

**Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis.** / Lucke, Lori E.; Parhi, Keshab K.

Research output: Contribution to journal › Article

*IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 12, no. 7, pp. 1063-1068. https://doi.org/10.1109/43.238043

}

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 -