Логическая минимизация при синтезе комбинационных структур в FPGA

Описываются результаты исследования эффективности применения программ минимизации функциональных описаний блоков комбинационной логики, входящих в проекты цифровых устройств, реализуемых в FPGA (Field-Programmable Gate Array). Программы предназначены для раздельной и совместной минимизации функций в классе ДНФ (дизъюнктивных нормальных форм) и минимизации многоуровневых представлений систем полностью определенных булевых функций на основе разложения Шеннона с нахождением как равных, так инверсных коэффициентов (кофакторов) разложения. Графические формы таких представлений широко известны в литературе как BDD (Binary Decision Diagrams). Для технологического отображения применялась программа «укрупнения» полученных формул разложения Шеннона (логических уравнений), так, чтобы  каждое из них зависело от ограниченного числа k входных переменных и могло быть реализовано на одном LUT-k ‑ программируемом элементе  FPGA, имеющем k входных переменных (LUT ‑ Look-Up Table) . Показано, что предварительная логическая минимизация , выполняемая с помощью отечественных программ, позволяет улучшать результаты проектирования в зарубежных САПР (системах автоматизированного проектирования), таких как LeonardoSpectrum (ф. Mentor Graphics)  и ISE (ф. Xilinx). Эксперименты проводились для семейств FPGA Virtex-II PRO и Virtex-5 (ф. Xilinx) на потоках стандартных промышленных примеров, задающих как системы дизъюнктивных нормальных форм булевых функций, так системы булевых функций в виде взаимосвязанных логических уравнений.

1. Зотов, Ю. В. Проектирование цифровых устройств на основе ПЛИС фирмы XILINX в САПР WebPack ISE / Ю. В. Зотов. - М. : Горячая линия - Телеком, 2003. - 624 с.

2. Designing with Xilinx® FPGAs: Using Vivado / ed. S. Churiwala. - Springer, 2017. - 260 p.

3. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев [и др.] ; под общ. ред. И. А. Каляева. - Ростов н/Д : Изд-во ЮНЦ РАН, 2008. - 320 с.

4. Nakahara, H. A deep convolutional neural network based on nested residue number system / H. Nakahara, T. Sasao // 25th Intern. Conf. on Field Programmable Logic and Applications (FPL), Lausanne, 2-4 September 2015. - Lausanne, 2015. - P. 1-6.

5. Петровский, Ал. А. Быстрое проектирование систем мультимедиа от прототипа / Ал. А. Петровский, А. В. Станкевич, А. А. Петровский. - Минск : Бестпринт, 2011. - 410 с.

6. Соловьев, В. В. Архитектуры ПЛИС фирмы Xilinx: FPGA и CPLD 7-й серии / В. В. Соловьев. - М. : Горячая линия - Телеком, 2016. - 392 с.

7. Бибило, П. Н. Синтез комбинационных схем методами функциональной декомпозиции / П. Н. Бибило, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.

8. Sasao, T. FPGA design by generalized functional decomposition / T. Sasao // Representations of Discrete Functions / eds.: T. Sasao, M. Fujita. - Kluwer Academic Publishers, 1996. - P. 233-258.

9. Sasao, T. Memory-Based Logic Synthesis / T. Sasao. - N. Y. : Springer, 2011. - 189 p.

10. Бибило, П. Н. Cистемы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum / П. Н. Бибило. - М. : СОЛОН-Пресс, 2005. - 384 с.

11. MIS: a multiple-level logic optimization systems / R. K. Brayton [et al.] // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. - 1987. - Vol. 6, iss. 6.- P. 1062-1081.

12. Chang, S.-C. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams / S.-C. Chang, M. Marek-Sadowska, T. Hwang // IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems. - 1996. - Vol. 15, no. 10. - P. 1226-1235.

13. Meinel, C. Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications / C. Meinel, T. Theobald. - Berlin, Heidelberg : Springer-Verlag, 1998. - 267 p.

14. Ebendt, R. Advanced BDD Optimization / R. Ebendt, G. Fey, R. Drechsler. - Springer, 2005. - 222 p.

15. Scholl, C. Functional Decomposition with Applications to FPGA Synthesis / C. Scholl. - Boston : Kluwer Academic Publishers, 2001. - 288 p.

16. Chen, D. FPGA design automation: a survey / D. Chen, J. Cong, P. Pan // Foundations and Trends in Electronic Design Automation. - 2006. - Vol. 1, no. 3. - P. 195-330.

17. Kubica, M. SMTBDD: New form of BDD for logic synthesis / M. Kubica, D. Kania // Intern. J. of Electronics and Telecommunications. - 2016. - Vol. 62, no. 1. - P. 33-41.

18. Kubica, M. Decomposition of multi-output functions oriented to configurability of logic blocks / M. Kubica, D. Kania // Bulletin of the Polish Academy of Sciences. Technical Sciences. - 2017. - Vol. 65, no. 3. - P. 317-331.

19. Vemuri, N. BDD-based logic synthesis for LUT-6-based FPGAs / N. Vemuri, P. Kalla, R. Tessier // ACM Transactions on Design Automation of Electronic Systems. - 2002. - Vol. 7, no. 4. - P. 501-525.

20. Yang, S. BDS: a BDD-based logic optimization system / S. Yang, M. Ciesielski // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2002. - Vol. 21, no. 7. - P. 866-876.

21. Lin, H.-P. Ashenhurst decomposition using SAT and interpolation / H.-P. Lin, J.-H. R. Jiang, R.-R. Lee ; eds.: S. P. Khatri, K. Gulati // Advanced Techniques in Logic Synthesis, Optimizations and Applications. - Springer, 2010. - P. 67-85.

22. Ashenhurst, R. L. The decomposition of switching functions / R. L. Ashenhurst // Annals of Computation Laboratory of Harvard University. - Cambrige, Mass., 1959. - Vol. 29. - P. 74-116.

23. Handbook of Satisfiability / ed. A. Biere [et al.]. - IOS Press, 2009. - 980 p.

24. Бибило, П. Н. Логическое проектирование дискретных устройств с использованием продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов. - Минск : Беларус. навука, 2011. - 279 с.

25. Авдеев, Н. А. Эффективность логической оптимизации при синтезе комбинационных схем из библиотечных элементов / Н. А. Авдеев, П. Н. Бибило // Микроэлектроника. - 2015. - Т. 44, № 5. - С. 383-399.

26. Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. - Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. - Вып. 4. - С. 4-19.

27. Бибило, П. Н. Использование полиномов Жегалкина при минимизации многоуровневых представлений систем булевых функций на основе разложения Шеннона / П. Н. Бибило, Ю. Ю. Ланкевич // Программная инженерия. - 2017. - № 8. - С. 369-384.

28. Бибило, П. Н. Оптимизация многоуровневых представлений систем булевых функций при перепроектировании логических схем / П. Н. Бибило, В. И. Романов // Управляющие системы и машины. - 2006. - № 5. - С. 20-29.

29. Черемисинов, Д. И. Анализ и преобразование структурных описаний СБИС / Д. И. Черемисинов. - Минск : Белорус. наука, 2006. - 275 с.

30. Кузелин, О. М. Современные семейства ПЛИС фирмы Xilinx : справ. пособие / О. М. Кузелин, Д. А. Кнышев, Ю. В. Зотов. - М. : Горячая линия - Телеком, 2004. - 440 с.

31. Jeong, C. Computer-aided design of digital systems / C. Jeong // Department of Computer Science [Electronic resource]. - Mode of access: http://www1.cs.columbia.edu/~cs6861/sis/espresso-examples/ex. - Date of access: 20.03.2018.

32. Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton [et al.]. - Boston : Kluwer Academic Publishers, 1984. - 193 p.

33. Тарасов, И. Е. ПЛИС Xilinx. Языки описания аппаратуры VHDL и Verilog, САПР, приемы проектирования / И. Е. Тарасов. - М. : Горячая линия - Телеком, 2020. - 538 с.

34. Авдеев, Н. А. Эффективность проектирования заказных схем в синтезаторе LeonardoSpectrum / Н. А. Авдеев, П. Н. Бибило // Современная электроника. - 2015. - № 1. - С. 58-61.