МЕТОДЫ ПРЕОБРАЗОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР С ОБРАТНЫМИ СВЯЗЯМИ ДЛЯ ЭФФЕКТИВНОЙ РЕАЛИЗАЦИИ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
Аннотация
В настоящее время для решения задач на реконфигурируемых вычислительных системах
используются различные системы автоматизированного проектирования. В большинстве слу-
чаев они состоят из двух основных компонент: компилятора (транслятора), переводящего
текст исходной программы в графовую информационно-вычислительную структуру, и синте-
затора, размещающего ее в архитектуре программируемых логических интегральных схем.
Существующие синтезаторы, как правило, обрабатывают информационно-вычислительную
структуру без комплексной оптимизации. Поэтому полученное решение прикладной задачи
может содержать неэффективные фрагменты, снижающие быстродействие прикладной
программы. Наиболее распространёнными примерами неэффективных вычислительных
структур являются фрагменты, реализующие рекурсивные выражения, так как они снижают
быстродействие прикладной программы. В статье предложены методы преобразования ре-
курсивных выражений (фрагментов с обратными связями), которые позволяют в автоматиче-
ском режиме сократить интервал обработки данных при решении прикладных задач на рекон-
фигурируемых вычислительных системах. В основе методов лежат информационно-
эквивалентные преобразования информационно-вычислительной структуры исходной задачи.
Для каждого преобразования определен набор правил, которым должны удовлетворять опера-
ционные вершины вычислительной структуры. Применение правил позволяет выполнять экви-
валентные преобразования не только над простыми структурами данных, такими как числа,
но также и над более сложными структурами (матрицами, векторами, тензорами и т.п.).
По результатам моделирования разработанные методы преобразования информационно-
вычислительных структур с обратными связями позволяют сократить время решения при-
кладных задач примерно в 2–5 раз, за счет сокращения интервала обработки данных. Предло-
женные методы реализованы в прототипе оптимизирующего синтезатора информационно-
вычислительных структур.
Литература
posobie [Reconfigurable computing systems: a textbook], ed. by I.A. Kalyaeva. Rostov-on-
Don: Izd-vo YuFU, 2016, 472 p.
2. Compton K. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing
Surveys, June 2002, Vol. 34, No. 2, pp. 171-210.
3. Levin I.I., Dordopulo A.I., Kalyaev I.A., Doronchenko Yu.I., Raskladkin M.K. Sovremennye i
perspektivnye vysokoproizvoditel'nye vychislitel'nye sistemy s rekonfiguriruemoy
arkhitekturoy [Modern and promising high-performance computing systems with reconfigurable
architecture], Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya:
Vychislitel'naya matematika i informatika [Bulletin of the South Ural State University. Series:
Computational Mathematics and Computer Science], 2015, Vol. 4, No. 3, pp. 24-39.
4. Muslim F.B., Ma L., Roozmeh M. and Lavagno L. Efficient FPGA Implementation of OpenCL
High-Performance Computing Applications via High-Level Synthesis, In IEEE Access, 2017,
Vol. 5, pp. 2747-2762. DOI: 10.1109/ACCESS.2017.2671881.
5. Bibilo P.N., Romanov V.I. Integratsiya SAPR dlya sinteza logicheskikh skhem s
ispol'zovaniem global'noy optimizatsii [Integration of CAD for synthesis of logic circuits using
global optimization], Programmnye produkty i sistemy [Software products and systems], 2019,
No. 1, pp. 26-33.
6. Intel® Quartus® Prime Standard Edition User Guide 18.1. Getting Started. UG-20173 |
2019.12.16.
7. Xilinx Vivado Design Suite. User Guide. Synthesis. UG901 (v2019.1) June 12, 2019.
8. Synopsys Synplify Pro for Microsemi Edition User Guide November 2016.
9. Rene Mueller, Jens Teubner, and Gustavo Alonso. Data processing on FPGAs. PVLDB, 2(1),
August 2009.
10. Vereshchagin N.K., Shen' A. Lektsii po matematicheskoy logike i teorii algoritmov. Ch. 1.
Nachala teorii mnozhestv [Lectures on mathematical logic and the theory of algorithms. Part 1.
The beginnings of set theory]. 4th ed. Moscow: MTSNMO, 2012, 112 p.
11. Kolyada V.I., Korenovskiy A.A. Kurs lektsiy po matematicheskomu analizu [A course of lectures
on mathematical analysis]: In 2 part. Part 1. Odessa: Astroprint, 2009, XXVII, 369 p.
12. Novikov F.A. Diskretnaya matematika dlya programmistov: uchebnik dlya vuzov [Discrete mathematics
for programmers: textbook for universities]. 3rd ed. Saint Petersburg: Piter, 2009, 384 p.
13. Voevodin V.V. Lineynaya algebra [Linear algebra]. 2nd ed. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury, 1980.
14. Kuck D. The structure of computers and computations. John Wiley and Sons. Inc., New York,
NY, 1978.
15. Samofalov K.G., Lutskiy G.M. Osnovy teorii mnogourovnevykh konveyernykh vychislitel'nykh
system [Fundamentals of the theory of multilevel conveyor computing systems].
Moscow: Radio i svyaz', 1989, 272 p.
16. Vasil'ev A.V., Mazurov V.D. Vysshaya algebra: Konspekt lektsiy. V 2 ch. [Higher Algebra:
Lecture Notes. In 2 part]. Novosibirsk: Novosib. gos. un-t, 2010, Part 1, 143 p.
17. Ricky Aditya, Muhammad Taufiq Zulfikar, Ngarap Imanuel Manik. Testing Division Rings and
Fields Using a Computer Program, Procedia Computer Science, 2015, Vol. 59, pp. 540-549.
18. Doronchenko Yu.I. Metod operatsionno-grafovogo opisaniya odnovremennykh vychisleniy
dlya mnogoprotsessornykh sistem [Method of operational graph description of simultaneous
computations for multiprocessor systems], Mater. Mezhdunar. nauch.-tekhn. konf.
“Mnogoprotsessornye vychisl. i upravlyayushchie sistemy – 2007” [Materials of the International
Scientific and Technical Conference "Multiprocessor computing and Control systems -
2007"]. Taganrog: TTI YuFU, 2007, Vol. 1, pp. 11-17.
19. Stanishevskiy O.B. Effektivnost' arifmeticheskoy obrabotki pri konveyernykh i
neyrokonveyernykh vychisleniyakh [The efficiency of arithmetic processing in conveyor and
neuroconveyor calculations], Konveyernye vychislitel'nye sistemy: Tezisy dokladov [Conveyor
computing systems: Abstracts]. Kishinev, 1988.
20. Dudko S.A. Ekvivalentnye preobrazovaniya rekurrentnykh vyrazheniy v rekonfiguriruemykh
vychislitel'nykh sistemakh [Equivalent transformations of recurrent expressions in reconfigurable
computing systems], Superkomp'yuternye tekhnologii (SKT-2020): Mater. 6-y
Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Supercomputer Technologies (SKT-2020):
Materials of the 6th All-Russian Scientific and Technical Conference]. Rostov-on-Don, Taganrog:
Izd-vo YuFU, 2020, Vol. 1, pp. 181-183.
