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

Бибило П. Н.; Ланкевич Ю. Ю.; Романов В. И.

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

Бибило П. Н., Ланкевич Ю. Ю., Романов В. И.

2021

https://doi.org/10.37661/1816-0301-2021-18-1-7-24

Описываются результаты исследования эффективности применения программ минимизации функциональных описаний блоков комбинационной логики, входящих в проекты цифровых устройств, реализуемых в 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) на потоках стандартных промышленных примеров, задающих как системы дизъюнктивных нормальных форм булевых функций, так системы булевых функций в виде взаимосвязанных логических уравнений.

Бибило П. Н., Ланкевич Ю. Ю., Романов В. И. Логическая минимизация при синтезе комбинационных структур в FPGA. Информатика. 2021;18(1):7-24. https://doi.org/10.37661/1816-0301-2021-18-1-7-24

Цитирование

Список литературы

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.

Источник

Информация

Автор

Бибило П. Н. Объединенный институт проблем информатики Национальной академии наук Беларуси
Ланкевич Ю. Ю. Объединенный институт проблем информатики Национальной академии наук Беларуси
Романов В. И. Объединенный институт проблем информатики Национальной академии наук Беларуси

Страницы

7-24

Год издания

2021

Ключевые слова

Коллекции

Информатика