ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ НЕКОТОРЫХ ВИДОВ РЕКУРСИВНЫХ НЕЛИНЕЙНЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР ДЛЯ ЭФФЕКТИВНОЙ РЕАЛИЗАЦИИ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
Аннотация
Рассматриваются методы информационно-эквивалентных преобразований некото-
рых видов нелинейных вычислительных структур с обратными связями: квадратичных,
дробных и условных. Наличие обратных связей в конвейерной вычислительной структуре,
решаемых на реконфигурируемых вычислительных системах прикладных задач, приводит к
замедлению скорости формирования данных, так как для вычисления очередного значения
требуется дождаться результата по обратной связи. При этом замедление происходит
не только на участке с обратной связью, но и во всей вычислительной структуре, что
приводит к увеличению времени, за которое данная задача может быть решена. Преды-
дущие фрагменты вынуждены задерживать свои данные перед подачей в обратную связь,
а последующие вынуждены простаивать, ожидая данные на выходе обратной связи. На
сегодняшний день не существует средств автоматического проектирования прикладных
задач для реконфигурируемых вычислительных систем, которые оптимизировали бы та-
кие вычислительные структуры в автоматическом режиме. Поэтому пользователь вы-
нужден самостоятельно изучать текст исходной программы и искать в нем выражения,
содержащие обратные связи, а затем оптимизировать их. Это приводит к увеличению
времени, требующегося для создания эффективных прикладных программ. Предложенные
методы преобразований позволяют сократить интервал обработки данных (в лучшем
случае до единицы) при решении прикладных задач на реконфигурируемых вычислительных
системах. Для реализации информационно-эквивалентных преобразований необходимо,
чтобы в вычислительной системе имелся дополнительный аппаратный ресурс. Реализация
данных преобразований в оптимизирующем синтезаторе схемотехнических решений по-
зволяет проводить оптимизацию вычислительной структуры с обратными связями авто-
матически. Это позволяет сократить время разработки эффективных прикладных про-
грамм, содержащих обратные связи, с нескольких дней до нескольких минут.
Литература
[Reconfigurable computer systems: a tutorial], under the general ed. I.A. Kalyaeva, Rostov-on-
Don: Izd-vo YuFU, 2016, 472 p. ISBN 978-5-9275-1980-7.
2. Compton K. Reconfigurable Computing: A Survey of Systems and Software, ACM Computing
Surveys, 2002, Vol. 34, No. 2, pp. 171-210.
3. Popov A.Yu. Proektirovanie tsifrovykh ustroystv s ispol'zovaniem PLIS: ucheb. posobie [Designing
digital devices using FPGAs: a tutorial]. Moscow: Izd-vo MGTU im. N.E. Baumana,
2009, 80 p.
4. Krishna G, Sahadev R. Fundamentals of FPGA Architecture, Advanced Engineering Technical
and Scientific Publisher, 2017, Part 2, pp. 12-30.
5. Kalyaev A.V. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-scalable multiprocessor systems with structural
and procedural organization of calculations]. Moscow: Yanus-K, 2003, 380 p.
6. Intel® Quartus® Prime Standard Edition User Guide 18.1. Getting Started. UG-20173
2018.09.24, pp. 44-47. Available at: https://www.intel.com/content/dam/www/programmable/
us/ en/pdfs/literature/ug/archives/ug-qps-getting-started-18-1.pdf (accessed 01 October 2020).
7. Xilinx Vivado Design Suite. User Guide. Synthesis. UG901 (v2017.1) April 19, 2017. – P. 7-
38. Available at: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2017_1/
ug901-vivado-synthesis.pdf (accessed 25 September 2020).
8. Synopsys Identify Microsemi Edition Instrumentor User Guide, January 2018. – P. 50-51. Available
at: https://www.microsemi.com/document-portal/doc_download/136672-synopsys-identifyrtl-
l2016-09m-2-debugger-instrumentor-for-libero-soc-v11-8 (accessed 28 September 2020).
9. Dudko S.A. Metod preobrazovaniya rekurrentnykh vyrazheniy v informatsionnom grafe
[Transforming method of recursive expressions in an information graph], XVI Ezhegodnaya
molodezhnaya nauchnaya konferentsiya «Yug Rossii: vyzovy vremeni, otkrytiya, perspektivy»:
materialy konferentsii (g. Rostov-na-Donu, 13–28 aprelya 2020 g.) [XVI Annual Youth Scientific
Conference "South of Russia: Challenges of Time, Discoveries, Prospects": conference
proceedings (Rostov-on-Don, April 13-28, 2020)]. Rostov-on-Don: Izd-vo YuNTS RAN,
2020, 168 p.
10. Agapova E.G. Vychislitel'naya matematika: ucheb. posobie [Computational mathematics: a
tutorial], ed. by T.M. Popova. 2017. Khabarovsk: Izd-vo Tikhookean. gos. un-ta, 2017, 92 p.
11. Lindenhovius B., Mislove M., Zamdzhiev V. Mixed linear and non-linear recursive types, Proceedings
of the ACM on Programming Languages, 2019, Vol. 3, Article 111.
12. Vasil'ev A.V., Mazurov V.D. Vysshaya algebra: V 2 ch. [Abstract Algebra: In 2 parts],
Konspekt lektsiy [Lecture notes]. Novosibirsk: Izd-vo Novosib. gos. un-t., 2010, Part 1, 143 p.
13. Aditya R., Zulfikar M.T., Manik N.I. Testing Division Rings and Fields Using a Computer
Program, Procedia Computer Science, 2015, Vol. 59, pp. 540-549.
14. Tyugashev A.A. Osnovy programmirovaniya [Basics of programming]. Part I. Saint Petersburg:
Universitet ITMO, 2016, 160 p.
15. Nielsen F. A Concise and Practical Introduction to Programming Algorithms in Java, Undergraduate
Topics in Computer Science. Springer-Verlag London Limited, 2009.
16. Akchurin A.D., Yusupov K.M. Programmirovanie na yazyke Verilog: ucheb. posobie [Verilog
Programming: a tutorial]. Kazan', 2016, 90 p.
17. Nabulsi M., Al-Husainy M. Using Combinational Circuits for Control Purposes, Journal of
Computer Science, 2009, No. 5 (7), pp. 507-510.
18. Wang X. Estimation of Number of Bits in Binary Representation of an Integer, International
Journal of Research Studies in Computer Science and Engineering, 2015, Vol. 2, pp. 28-31.
19. Kharris D.M., Kharris S.L. Tsifrovaya skhemotekhnika i arkhitektura komp'yutera [Digital
Design and Computer Architecture]. 2nd ed., DMK-Press, 2018, 792 p.
20. Voevodin V.V. Lineynaya algebra [Linear Algebra]. 2nd ed. Moscow: Glavnaya redaktsiya
fiziko-matematicheskoy literatury, 1980.
