More Web Proxy on the site http://driver.im/

article

Static scheduling for synthesis of DSP algorithms on various models

Authors:

Liang-Fang Chao,

Edwin Hsing-Mean ShaAuthors Info & Claims

Journal of VLSI Signal Processing Systems, Volume 10, Issue 3

Pages 207 - 223

Published: 15 August 1995 Publication History

Abstract

Given a behavioral description of a DSP algorithm represented by a data-flow graph, we show how to obtain a rate-optimal static schedule with the minimum unfolding factor under two models, integral grid model and fractional grid model, and two kinds of implementations for each model, pipelined implementation and non-pipelined implementation. We present a simple and unified approach to deal with the four possible combinations. A unified polynomial-time scheduling algorithm is presented, which works on the original data-flow graphs without really unfolding. The values of the minimum rate-optimal unfolding factors and the general properties for all the four combinations are proved.

References

[1]

L.-F. Chao and E.H.-M. Sha, "Retiming and unfolding data-flow graphs,"Proceedings of the International Conference on Parallel Processing, St. Charles, IL, Aug. 1992, pp. II 33---40.

[2]

A. Zaky and P. Sadayappan, "Optimal static scheduling of sequential loops on multiprocessors,"Proceedings of the International Conference on Parallel Processing, pp. III 130---137, 1989.

[3]

E.A. Lee and D.G. Messerschmitt, "Static scheduling of synchronous data flow programs fordigital signal processing,"IEEE Transactions on Computers, Vol. 36, pp. 24---35, 1987.

Digital Library

[4]

S. Shukla, B. Little, and A. Zaky, "A compile-time technique for controlling real-time execution of task-level data-flow graphs,"Proceedings of the International Conference on Parallel Processing, Naval Postgraduate School, pp. II 49---56, Aug. 1992.

[5]

M. Renfors and Y. Neuvo, "The maximum sampling rate of digital filters under hardware speed constraints,"IEEE Transactions on Circuits and Systems, Vol. CAS-28, pp. 196---202, 1981.

[6]

L.-F. Chao and E.H.-M. Sha, "Unfolding and retiming data-flow DSP programs for RISC multiprocessor scheduling,"Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal Processing, San Francisco, CA, Mar. 1992, pp. V565---V568.

[7]

L.-G. Jeng and L.-G. Chen, "A globally static rate optimal scheduling for recursive DSP algorithms,"Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal Processing, pp. 1005---1008, May 1991.

[8]

L.-G. Jeng and L.-G. Chen, "Synthesis of rate-optimal DSP algorithms by pipeline and minimum unfolding,"Proceedings of the ACM/IEEE International Workshop on High-Level Synthesis, pp. 159---168, Nov. 1992.

[9]

L.E. Lucke, A.P. Brown, and K.K. Parhi, "Unfolding and retiming for high-level DSP synthesis,"Proceedings of the International Symposium on Circuits and Systems, pp. 2351---2354, 1991.

[10]

K.K. Parhi and D.G. Messerschmitt, "Static rate-optimal scheduling of iterative data-flow programs via optimum unfolding,"IEEE Transactions on Computers, Vol. 40, pp. 178---195, 1991.

Digital Library

[11]

D.J. Wang and Y.H. Hu, "Optimal scheduling of linear recurrence equations on a multi-processor array,"Proceedings of the IEEE International Conference on Acoustic, Speech, and Signal Processing, Toronto, May 1991, pp. 1581---1584.

[12]

D.J. Wang and Y.H. Hu, "Fully static multiprocessor realization for real-time recursive DSP algorithms,"International Conference on Application-Specific Array Processors, Aug. 1992, pp. 664---678.

[13]

A. Aiken and A. Nicolau, "Optimal loop parallelization,"Proceedings of the ACM SIGPLAN Conference on Programming Languages Design and Implementation, pp. 308---317, June 1988.

[14]

G.R. Gao, Y.-B. Wong, and Q. Ning, "A timed petri-net model for fine-grain loop scheduling,"Proceedings of the ACM SIGPLAN Conference on Programming Languages Design and Implementation, pp. 204---218, June 1991.

[15]

L.-F. Chao and E.H.-M. Sha, "Efficient retiming and unfolding,"Proceedings of the IEEE International Conference on Acoustic,Speech, and Signal Processing, pp. I 421---424, Apr. 1993.

[16]

L.E. Lucke and K.K. Parhi, "Generalized ILP scheduling and allocation for high-level DSP synthesis,"Proceedings of the IEEE Custom Integrated Circuits Conference, pp. 5.4.1---5.4.4, May 1993.

[17]

L.-F. Chao, "Scheduling and behavioral transformations for parallel systems," Ph.D. Thesis, Tech. Rep. CS-TR-430-93, Department of Computer Science, Princeton University, July 1993.

[18]

M. Lam, "Software pipelining: An effective scheduling technique for VLIW machines,"Proceedings of the ACM SIGPLAN Conference on Programming Languages Design and Implementation, Atlanta, GA, June 1988, pp. 318---328.

[19]

L.-F. Chao and E.H.-M. Sha, "Rate-optimal static scheduling for DSP data-flow programs,"Proceedings of the Great Lakes Symposium on VLSI, Kalamazoo, Michigan, Mar. 1993, pp. 80---84.

[20]

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

[21]

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

[22]

L.B. Jackson,Digital Filters and Signal Processing, pp. 47---53, Kluwer Academic Publishers, 1986.

[23]

J.-G. Chung and K. Parhi, "Design of pipelined lattice IIR digital filters,"Proceedings of the Asilomar Conference on Signals, Systems, and Computers, pp. 1021---1025, Nov. 1991.

[24]

R. Camposano and W. Wolf (Eds.),High-Level Synthesis, Boston: Kluwer Academic Publishers, 1991.

[25]

G. Goossens, F. Catthoor, D. Lanneer, and H.D. Man, "Integration of signal processing systems on heterogeneous IC architectures,"Proceedings of the ACM/IEEE International Workshop on High-Level Synthesis, Nov. 1992.

[26]

K. Iwano and S. Yeh, "An efficient algorithm for optimal loop parallelization,"Proceedings of The First International Symposium of Algorithms, Dec. 1990.

[27]

P.R. Gelabert and T.P. Bamwell, "Optimal automatic periodic multiprocessor scheduler for fully specified flow graphs,"IEEE Transactions on Signal Processing, Vol. 41, pp. 858---888, 1993.

[28]

N. Passos, E.H.-M. Sha, and S.C. Bass, "Partitioning and retiming of multi-dimensional systems,"Proceedings of the International Symposium on Circuits and Systems, 1994.

[29]

N. Passos and E.H.-M. Sha, "Full parallelism in uniform nested loops using multi-dimensional retiming,"Proceedings of the International Conference on Parallel Processing, Aug. 1994.

Cited By

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
Zhu XGeilen MBasten TStuijk S(2016)Multiconstraint Static Scheduling of Synchronous Dataflow Graphs Via Retiming and UnfoldingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.249516735:6(905-918)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1109/TCAD.2015.2495167
Geilen M(2011)Synchronous dataflow scenariosACM Transactions on Embedded Computing Systems10.1145/1880050.188005210:2(1-31)Online publication date: 7-Jan-2011
https://dl.acm.org/doi/10.1145/1880050.1880052
Show More Cited By

Index Terms

Recommendations

Unified Static Scheduling on Various Models
ICPP '93: Proceedings of the 1993 International Conference on Parallel Processing - Volume 02

Given a behavioral description of an algorithm represented by a data-flow graph, we show how to obtain a rote-optimal static schedule with the minimum unfolding factor under two timing models, integral grid model and fractional grid model, and two ...
Parallel job scheduling algorithms
A globally static rate optimal scheduling for recursive DSP algorithms
ICASSP '91: Proceedings of the Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference

A set of techniques for rate-optimal scheduling of recursive DSP algorithms is presented. The underlying microprocessor system is based on the RISC architecture. The retiming process evenly distributes the delays and optimizes the scheduling time of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of VLSI Signal Processing Systems

Journal of VLSI Signal Processing Systems Volume 10, Issue 3

Aug. 1995

101 pages

ISSN:0922-5773

Editors:
Earl E. Swartzlander
Univ. of Texas, Austin
,
S. Y. Kung
Princeton Univ., Princeton, NJ

Issue’s Table of Contents

Copyright © Copyright © 1995 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 15 August 1995

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Zhu XGeilen MBasten TStuijk S(2016)Multiconstraint Static Scheduling of Synchronous Dataflow Graphs Via Retiming and UnfoldingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.249516735:6(905-918)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1109/TCAD.2015.2495167
Geilen M(2011)Synchronous dataflow scenariosACM Transactions on Embedded Computing Systems10.1145/1880050.188005210:2(1-31)Online publication date: 7-Jan-2011
https://dl.acm.org/doi/10.1145/1880050.1880052
Qiu MSha E(2009)Cost minimization while satisfying hard/soft timing constraints for heterogeneous embedded systemsACM Transactions on Design Automation of Electronic Systems10.1145/1497561.149756814:2(1-30)Online publication date: 7-Apr-2009
https://dl.acm.org/doi/10.1145/1497561.1497568
Qiu MSha ELiu MLin MHua SYang L(2008)Energy minimization with loop fusion and multi-functional-unit scheduling for multidimensional DSPJournal of Parallel and Distributed Computing10.1016/j.jpdc.2007.06.01468:4(443-455)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1016/j.jpdc.2007.06.014
Qiu MJia ZXue CShao ZSha E(2007)Voltage Assignment with Guaranteed Probability Satisfying Timing Constraint for Real-time Multiproceesor DSPJournal of VLSI Signal Processing Systems10.1007/s11265-006-0002-046:1(55-73)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1007/s11265-006-0002-0
O'Neil TSha E(2006)Time-constrained loop scheduling with minimal resourcesJournal of Embedded Computing10.5555/1370986.13709962:1(103-117)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.5555/1370986.1370996
Shao ZZhuge QXue CSha E(2005)Efficient Assignment and Scheduling for Heterogeneous DSP SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2005.7116:6(516-525)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1109/TPDS.2005.71
O'Neil TSha E(2005)Combining extended retiming and unfolding for rate-optimal graph transformationJournal of VLSI Signal Processing Systems10.1007/s11265-005-4845-639:3(273-293)Online publication date: 1-Mar-2005
https://dl.acm.org/doi/10.1007/s11265-005-4845-6
Zhuge QXiao BSha E(2003)Code size reduction technique and implementation for software-pipelined DSP applicationsACM Transactions on Embedded Computing Systems10.1145/950162.9501682:4(590-613)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1145/950162.950168
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents