research-article

Scheduling Data-Flow Graphs via Retiming and Unfolding

Authors:

Liang-Fang Chao,

Edwin Hsing-Mean ShaAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 8, Issue 12

Pages 1259 - 1267

https://doi.org/10.1109/71.640018

Published: 01 December 1997 Publication History

Publisher Site

Abstract

Loop scheduling is an important problem in parallel processing. The retiming technique reorganizes an iteration; the unfolding technique schedules several iterations together. We combine these two techniques to obtain a static schedule with a reduced average computation time per iteration. We first prove that the order of retiming and unfolding is immaterial for scheduling a data-flow graph (DFG). From this nice property, we present a polynomial-time algorithm on the original DFG, before unfolding, to find the minimum-rate static schedule for a given unfolding factor. For the case of a unit-time DFG, efficient checking and retiming algorithms are presented.

References

[1]

C.E. Leiserson and J.B. Saxe, "Retiming Synchronous Circuitry," Algorithmica, vol. 6, pp. 5-35, 1991.

Digital Library

Google Scholar

[2]

L.-F. Chao and E. H.-M. Sha, "Retiming and Unfolding Data-Flow Graphs," Proc. Int'l Conf. Parallel Processing, pp. 33-40, St. Charles, Ill., Aug. 1992.

Google Scholar

[3]

A.L. Davis and R.M. Keller, "Data Flow Program Graphs," Computer, vol. 15, no. 2, pp. 26-41, Feb. 1982.

Digital Library

Google Scholar

[4]

K.K. Parhi and D.G. Messerschmitt, "Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding," IEEE Trans. Computers, vol. 40, no. 2, pp. 178-195, Feb. 1991.

Digital Library

Google Scholar

[5]

L.-F. Chao and E. H.-M. Sha, "Unfolding and Retiming Data-Flow DSP Programs for RISC Multiprocessor Scheduling," Proc. IEEE Int'l Conf. Acoustics, Speech, and Signal Processing, pp. V565-V568, San Francisco, Mar. 1992.

Google Scholar

[6]

L.E. Lucke A.P. Brown and K.K. Parhi, "Unfolding and Retiming for High-Level DSP Synthesis," Proc. Int'l Symp. Circuits and Systems, pp. 2,351-2,354, 1991.

Google Scholar

[7]

K.K. Parhi, "A Systematic Approach for Design of Digital-Serial Signal Processing Architectures," IEEE Trans. Circuits and Systems, vol. 38, pp. 358-375, Apr. 1991.

Crossref

Google Scholar

[8]

L.-F. Chao and E. H.-M. Sha, "Static Scheduling for Synthesis of DSP Algorithms on Various Models," J. VLSI Signal Processing, vol. 13, no. 1, pp. 37-56, Aug. 1996.

Digital Library

Google Scholar

[9]

L.-F. Chao and E. H.-M. Sha, "Scheduling Data-Flow Graphs Via Retiming and Unfolding," Technical Report CS-TR-396-92, Dept. of Computer Science, Princeton Univ., Oct. 1992.

Google Scholar

[10]

L.-F. Chao, "Scheduling and Behavioral Transformations for Parallel Systems," PhD thesis, Technical Report CS-TR-430-93, Dept. of Computer Science, Princeton Univ., July 1993.

Digital Library

Google Scholar

[11]

M. Renfors and Y. Neuvo, "The Maximum Sampling Rate of Digital Filters under Hardware Speed Constraints," IEEE Trans. Circuits and Systems, vol. 28, pp. 196-202, Mar. 1981.

Crossref

Google Scholar

[12]

R.E. Tarjan, Data Structures and Network Algorithms. Philadelphia: SIAM, 1983.

Digital Library

Google Scholar

[13]

E.L. Lawler, Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart, and Winston, 1976.

Google Scholar

[14]

L.-F. Chao A. LaPaugh and E. H.-M. Sha, "Rotation Scheduling: A Loop Pipelining Algorithm," Proc. ACM/IEEE Design Automation Conf., pp. 566-572, June 1993. revision in IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, vol. 16, no. 3, pp. 229-239, Mar. 1997.

Digital Library

Google Scholar

Cited By

View all

Ma MHou JXiang DLin WDing Z(2024)Efficient Pipelining of Synchronous Dataflow Graphs Via Graph ConversionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335519043:6(1704-1714)Online publication date: 18-Jan-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3355190
Zhang YZhang NZhao TVilim MShahbaz MOlukotun KMartínez JDuato JJohn L(2021)SARAProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00085(1041-1054)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00085
Zhu XShrivastava APasricha S(2018)Equivalence of transformations of synchronous data flow graphsProceedings of the International Conference on Hardware/Software Codesign and System Synthesis10.5555/3283568.3283579(1-2)Online publication date: 30-Sep-2018
https://dl.acm.org/doi/10.5555/3283568.3283579
Show More Cited By

Index Terms

Scheduling Data-Flow Graphs via Retiming and Unfolding

Recommendations

Iterational retiming: maximize iteration-level parallelism for nested loops
CODES+ISSS '05: Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

Nested loops are the most critical sections in many scientific and Digital Signal Processing (DSP)applications.It is important to study effective and efficient transformation techniques to increase parallelism for nested loops.In this paper, we propose ...
Combining extended retiming and unfolding for rate-optimal graph transformation

Many computation-intensive iterative or recursive applications commonly found in digital signal processing and image processing applications can be represented by data-flow graphs (DFGs). The execution of all tasks of a DFG is called an iteration, with ...
Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding

Rate-optimal compile-time multiprocessor scheduling of iterative dataflow programs suitable for real-time signal processing applications is discussed. It is shown that recursions or loops in the programs lead to an inherent lower bound on the achievable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 8, Issue 12

December 1997

128 pages

ISSN:1045-9219

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 1997

Author Tag

Data-flow graphs, loop parallelization, parallel processing, retiming, scheduling, unfolding.

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ma MHou JXiang DLin WDing Z(2024)Efficient Pipelining of Synchronous Dataflow Graphs Via Graph ConversionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335519043:6(1704-1714)Online publication date: 18-Jan-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3355190
Zhang YZhang NZhao TVilim MShahbaz MOlukotun KMartínez JDuato JJohn L(2021)SARAProceedings of the 48th Annual International Symposium on Computer Architecture10.1109/ISCA52012.2021.00085(1041-1054)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1109/ISCA52012.2021.00085
Zhu XShrivastava APasricha S(2018)Equivalence of transformations of synchronous data flow graphsProceedings of the International Conference on Hardware/Software Codesign and System Synthesis10.5555/3283568.3283579(1-2)Online publication date: 30-Sep-2018
https://dl.acm.org/doi/10.5555/3283568.3283579
Hautala IBoutellier JNyländen TSilvén O(2018)Toward Efficient Execution of RVC-CAL Dataflow Programs on Multicore PlatformsJournal of Signal Processing Systems10.1007/s11265-018-1339-x90:11(1507-1517)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s11265-018-1339-x
Jiang WSha EZhuge QDong HChen X(2017)Optimal functional unit assignment and voltage selection for pipelined MPSoC with guaranteed probability on time performanceACM SIGPLAN Notices10.1145/3140582.308103652:5(41-50)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3140582.3081036
Jiang WSha EZhuge QDong HChen XNagarajan VShao Z(2017)Optimal functional unit assignment and voltage selection for pipelined MPSoC with guaranteed probability on time performanceProceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3078633.3081036(41-50)Online publication date: 21-Jun-2017
https://dl.acm.org/doi/10.1145/3078633.3081036
Jiang WSha EChen XYang LZhou LZhuge Q(2017)Optimal Functional-Unit Assignment for Heterogeneous Systems Under Timing ConstraintIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.267676428:9(2567-2580)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1109/TPDS.2017.2676764
Liu XQiu MWang XLiu WCai K(2017)Energy Efficiency Optimization for Communication of Air-Based Information Network with Guaranteed Timing ConstraintsJournal of Signal Processing Systems10.1007/s11265-016-1125-686:2-3(299-312)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11265-016-1125-6
Jiang WSha EZhuge QChen X(2016)Optimal functional-unit assignment and buffer placement for probabilistic pipelinesProceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis10.1145/2968456.2968467(1-10)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1145/2968456.2968467
Qiu KZhang WWu XZhu XWang JXu YXue COssowski S(2016)Balanced loop retiming to effectively architect STT-RAM-based hybrid cache for VLIW processorsProceedings of the 31st Annual ACM Symposium on Applied Computing10.1145/2851613.2851670(1710-1716)Online publication date: 4-Apr-2016
https://dl.acm.org/doi/10.1145/2851613.2851670
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Iterational retiming: maximize iteration-level parallelism for nested loops

Combining extended retiming and unfolding for rate-optimal graph transformation

Static Rate-Optimal Scheduling of Iterative Data-Flow Programs Via Optimum Unfolding

Comments

Information

Published In

Publisher

Publication History

Author Tag

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations