Method of synchronous dataflow scheduling
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2016.1.06Abstract
The scheduling problem for the synchronous dataflow graph (SDF) is considered. A method of the SDF scheduling is proposed which is based on transforming SDF into spatial SDF. The circular schedule has the period of L cycles. Each spatial SDF node has the coordinates of space and time of an event, where and when the respective algorithm steps were performed. A set of restrictions, which the SDF nodes have, helps to derive the circular schedule with the optimum load balancing. So, the nodes, which are mapped into a single resource, must not have the same clock cycles modulo L, and the number of such nodes has to approach L. The resulting schedule is implemented in the pipelined datapath. The algorithm for computing the suboptimal schedule is proposed based on the spatial SDF.References
Sergienko A.M. Algoritmicheskie modeli obrabotki potokov dannyh / A.M. Sergienko, V.P. Simonenko // Elektronnoe modelirovanie. — 2008. — T. 30. — № 6. — S. 49-60.
Lee E.A. Synchronous Datafow / E.A. Lee, D.G. Messerschmitt // Proc. IEEE. — 1987. — V. 75. — N 9. — P. 1235–1245.
Edwards S. Design of Embedded Systems: Formal Models, Validation, and Synthesis / S. Edwards, L. Lavagno, E.A. Lee, A. Sangiovanny-Vincentelli // Proc. IEEE. — 1997. — V. 85. — N 3. — P. 366-390.
Lee E.A. Static scheduling of synchronous data flow programs for digital signal processing / E.A. Lee, D.G. Messerschmitt // IEEE Trans. on Computers. — 1987. — V. 36. — N 1. — P. 24-35.
O’Neil T.W. Retiming synchronous data-flow graphs to reduce execution time / T.W. O’Neil, E.H.M. Sha // IEEE Trans. on Signal Processing. — 2001. — 49, N 10. — P.2397–2407.
Paulin P. G. HAL: A multi-paradigm approach to automatic data path synthesis / P.G. Paulin, J.P. Knight, E.F. Girczyc // Proc. 23-rd IEEE Design Automation Conf, Las Vegas, NV, July 1986. — 1986. — P. 263-270.
Chao L. Rotation scheduling: A loop pipelining algorithm / L. Chao, A. LaPaugh, E. Sha // Proc 30-th Design Automation Conf., DAC’93, June 1993. — 1993. — P. 566–572.
The Systhesis Approach to Digital System Design / Editors P. Micheli, U.Lauther, P. Duzy. — Kluwer Academic Pub, 1992. — 415 p.
EVM i teorija raspisanij / Pod red. I.G. Kofmana. — M.: Mir, 1979. — 460 s.
Paulin P.G. Force – Directed Scheduling for the Behavioral Synthesis of ASICs / P.G. Paulin, J.P. Knight // IEEE Trans. CAD. —1988. — 7, N 3. — P. 356–370.
Park N. Module Assignment and Interconnect Sharing in Register-Transfer Synthesis of Pipelined Data Paths / N. Park, F.J. Kurdahi // Proc. IEEE Int. Conf. on Computer Aided Design. — Santa Clara, Calif. — 1989. — P. 16?19.
Hwang K. S. Scheduling and hardware sharing in pipelined data paths / K.S. Hwang, A.E. Casavant, C.T. Chang, M.A. d’Abreu // Proc. Int’l Conf. on Computer Aided Design. — 1989. — P. 24–27.
Catthoor F. Application-specific architectural methodologies for high-throughput digital signal and image processing / F. Catthoor, H. De Man // IEEE Trans. on Acoustics, Speech and Signal Processing. — 1990. — 38, N 2. — P. 339?349.
Tseng C. Automated Synthesis of Data Paths in Digital Systems / C. Tseng, D. Siewiorek // IEEE Trans. on Computer-Aided Design. — 1986. — N 7. — P. 379?395.
Kurrdahi F.J. REAL: A Program for Register Allocation / F.J. Kurrdahi, A.C. Parker // Proc. 24-th ACM/ IEEE Design Automation Conf. DAC-87. — 1987. — P. 210?215.
Tucker A. Coloring a family of circular arcs / A. Tucker // SIAM J. Appl. Math. — 1975. — 29, N 3. — P. 493?502.
Springer D.L. Exploiting the Special Structure of Conflict and Compatibility Graphs in High-Level Synthesis / D.L. Springer, D.E. Thomas // Proc. Int. Conf. Computer Aided Design (ICCAD). — 1990. — P. 254-257.
Robert Y. Introduction to Scheduling / Y. Robert, F. Vivien ? Ed-s. CRC Press, Taylor and Francis Group. — 2010. — 310 p.
Lee E.A. Static scheduling of synchronous data flow programs for digital signal processing / E.A. Lee, D.G. Messerschmitt // IEEE Trans. on Computers. — 1987. — 36, N 1. — P. 24-35.
Voevodin V.V. Matematicheskie modeli i metody v parallel'nyh protsesah / V.V. Voevodin. — M: Nauka. — 1986. — 296 s.
Sergienko A.M. Otobrazhenie periodicheskih algoritmov v programmiruemye logicheskie integral'nye shemy / A.M. Sergienko, V.P. Simonenko // Elektronnoe modelirovanie. — 2007. — 29, № 2. — S. 49-61.
Evstigneev V.A. Primenenie teorii grafov v programmirovanii / V.A. Evstigneev; pod red. A.P. Ershova. — M: Nauka, 1985. — 352 s.
Serhiyenko A.M. Doskonalyj kistjak hrafe alhorytmu / A.M. Serhiyenko // Informatyka i obchysljuval'na tekhnika: zb. nauk. prats'. — 2007. — № 46. — S. 62-67.
Sergienko A.M. VHDL dlja proektirovanija vychislitel'nyh ustrojstv / A.M. Sergienko. — K.: DiaSoft, 2003. — 210 s.
Haroun B.S. SPAID: An Architectural Synthesis Tool for DSP Custom Applications / B.S. Haroun, M.I. Elmasry // Proc. IEEE Custom Integrated Circuits Conf. — Rochester, N.Y. — May 16–19. — 1988. — P. 14.4/1-14.4/5.
Sergiyenko A. Low-Pass IIR Filter / A. Sergiyenko, O. Uzenkov. — 2010. — Available at http://opencores.org/project,lp_iir_filter.
