Логическая минимизация при синтезе комбинационных структур в 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.