DOI: https://doi.org/10.20535/SRIT.2308-8893.2016.1.06

Складання розкладу для графів синхронних потоків даних

А. M. Sergiyenko, V. P. Simonenko

Анотація


Розглянуто задачу складання розкладу для алгоритму, який заданий графом синхронних потоків даних (ГСПД). Запропоновано метод складання періодичного розкладу ГСПД з періодом L тактів, оснований на перетворенні його у просторовий ГСПД, вершини якого мають координати місця та моменту виконання відповідних операторів алгоритму. На координати просторового ГСПД накладено обмеження: оператори, які виконуються в одному процесорному елементі, не повинні мати однакові такти свого виконання, які взято за модулем L. Завдяки цьому ГСПД відображається у спеціалізований обчислювач, який виконує алгоритм у конвеєрному режимі з оптимізованою завантаженністю ресурсів. Показано алгоритм пошуку субоптимального розкладу на основі просторового ГСПД.

Повний текст:

PDF

Посилання


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.


Пристатейна бібліографія ГОСТ


1. Сергиенко А.М. Алгоритмические модели обработки потоков данных / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2008. — Т. 30. — № 6. — С. 49−60.

 

2. Lee E.A. Synchronous Datafow / E.A. Lee, D.G. Messerschmitt // Proc. IEEE. — 1987. — V. 75. — N 9. — P. 1235–1245.

 


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

 

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

 

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

 

 

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

 


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

 


8. The Systhesis Approach to Digital System Design / Editors P. Micheli, U.Lauther, P. Duzy. — Kluwer Academic Pub, 1992. — 415 p.

 


9. ЭВМ и теория расписаний / Под ред. И.Г. Кофмана. — М.: Мир, 1979. — 460 с.

 

 

10. Paulin P.G. Force – Directed Sheduling for the Behavioral Synthesis of ASICs / P.G. Paulin, J.P. Knight // IEEE Trans. CAD. —1988. — 7, N 3. — P. 356–370.

 

 

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

 

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

 

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

 

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

 

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

 

16. Tucker A. Coloring a family of circular arcs / A. Tucker // SIAM J. Appl. Math. — 1975. — 29, N 3. — P. 493−502.

 

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

 

18. Robert Y. Introduction to Scheduling / Y. Robert, F. Vivien − Ed-s. CRC Press, Taylor and Francis Group. — 2010. — 310 p.

 

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

 

20. Воеводин В.В. Математические модели и методы в параллельных процесах / В.В. Воеводин. — М: Наука. — 1986. — 296 с.

 

21. Сергиенко А.М. Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2007. — 29, № 2. — С. 49−61.

 

22. Евстигнеев В.А. Применение теории графов в программировании /
В.А. Евстигнеев; под ред. А.П. Ершова. — М: Наука, 1985. — 352 с.

 

23. Сергієнко А.М. Досконалий кістяк графe алгоритму / А.М. Сергієнко // Інформатика і обчислювальна техніка: зб. наук. праць. — 2007. — № 46. — С. 62−67.

 

24. Сергиенко А.М. VHDL для проектирования вычислительных устройств / А.М. Сергиенко. — К.: ДиаСофт, 2003. — 210 с.

 

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

 

26. Sergiyenko A. Low-Pass IIR Filter / A. Sergiyenko, O. Uzenkov. — 2010. — Available at http://opencores.org/project,lp_iir_filter