Алгоритмы выделения из многоуровневого представления системы булевых функций подсистем для совместной минимизации

Цели. Целью экспериментальных исследований является выяснение эффективности новых алгоритмов выделения из формульных описаний исходной системы булевых функций так называемых связанных подсистем. При этом каждая из выделенных подсистем впоследствии минимизируется независимо от других, однако функции, составляющие каждую связанную подсистему, минимизируются совместно.

Методы. Минимизация подсистем выполняется в классе многоуровневых BDD-представлений (BDD – Binary Decision Diagram – бинарная диаграмма решений) либо булевых сетей. После получения минимизированных описаний схем, заданных в виде совокупности взаимосвязанных формул разложения Шеннона, которые соответствуют BDD, либо в виде двухоперандных логических уравнений, соответствующих булевым сетям, выполняется синтез логических схем в библиотеке проектирования заказных цифровых КМОП СБИС (сверхбольших интегральных схем, выполненных по комплементарной технологии металл-оксид-полупроводник). В булевых сетях функциями вершин могут быть логические операции «конъюнкция» либо «дизъюнкция» над литералами булевых переменных. Литерал – это булева переменная либо ее инверсия. Минимизация BDD-представлений осуществляется по числу формул разложения Шеннона, минимизация булевых сетей – по числу литералов в формулах, задающих сети.

Результаты. Полученные логические схемы сравнены по площади кристалла и быстродействию (временной задержке). Эксперименты проведены на 39 промышленных примерах схем. Показано преимущество (в 29 случаях) применения предлагаемых алгоритмов выделения подсистем по сравнению с совместной либо раздельной минимизацией исходной системы булевых функций, которая обычно выполняется в качестве первого этапа синтеза логических схем.

Заключение. Предложенные в работе новые алгоритмы выделения подсистем доказали свою эффективность при выполнении различных программ оптимизации многоуровневых представлений систем булевых функций. Разработанный комплекс программ позволяет улучшать результаты технологически независимой оптимизации, применяемой при реализации проектов цифровых систем в заказных цифровых КМОП СБИС.

1. Закревский, А. Д. Логический синтез каскадных схем / А. Д. Закревский. - М. : Наука, 1981. - 416 c.

2. Logic Minimization Algorithm for VLSI Synthesis / K. R. Brayton, G. D. Hachtel, C. McMullen, A. L. Sangiovanni-Vincentelli. - Boston : Kluwer Academic Publishers, 1984. - 193 p.

3. Sasao, T. Input variable assignment and output phase optimization of PLA's / T. Sasao // IEEE Transactions on Computers. - 1984. - Vol. C-33, no. 10. - P. 879-894.

4. Wey, C. L. An efficient output assignment for PLA minimization / C. L. Wey, T. Y. Chang // IEEE Transactions on Computer-Aided Design. - 1990. - Vol. 9. - P. 1-7.

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

6. Кнут, Д. Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 : пер. с англ. / Д. Э. Кнут. - М. : Вильямс, 2013. - 960 с.

7. Бибило, П. Н. Бинарные диаграммы решений в логическом проектировании / П. Н. Бибило. - М. : Ленанд, 2024. - 560 с.

8. Брейтон, Р. К. Синтез многоуровневых комбинационных логических схем / Р. К. Брейтон, Г. Д. Хэчтел, А. Л. Санджованни-Винчентелли // Труды Института инженеров по электротехнике и радиоэлектронике. - 1990. - Т. 78, № 2. - С. 38-83.

9. Синтез асинхронных автоматов на ЭВМ / под ред. А. Д. Закревского. - Минск : Наука и техника, 1975. - 184 с.

10. MIS: A multiple-level logic optimization systems / R. K. Brayton, R. Rudell, A. L. Sangiovanni-Vincentelli, A. R. Wang // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 1987. - Vol. CAD-6, no. 6. - P. 1062-1081.

11. Brayton, K. R. Factoring logic functions / K. R. Brayton // IBM Journal of Research and Development. - 1987. - Vol. 31, no 2. - P. 187-198.

12. Amaru, L. G. New Data Structures and Algorithms for Logic Synthesis and Verification / L. G. Amaru. - Springer, 2017. - 156 p.

13. О сложности инверсных графов, реализующих булевы функции от малого числа переменных / С. А. Ложкин, В. С. Зизов, М. С. Шуплецов [и др.] // Проблемы разработки перспективных микро и наноэлектронных систем : сб. тр. / под общ. ред. А. Л. Стемпковского. - 2020. - Вып. 4. - С. 95-102. - https://doi.org/10.31114/2078-7707-2020-4-95-102.

14. Optimizing majority-inverter graphs with functional hashing / M. Soeken, L. G. Amaru, P. Gaillardon, G. De Micheli // Proc. of the 2016 Design, Automation & Test in Europe Conf. & Exhibition (DATE), Dresden, Germany, 14-18 March 2016. - Dresden, 2016. - P. 1030-1035.

15. Exact synthesis of majority-inverter graphs and its applications / M. Soeken, L. Amaru, P.-E. Gaillardon, G. De Micheli // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. - 2017. - Vol. 36, no. 11. - P. 1842-1855.

16. Бибило, П. Н. Выделение из многоуровневого представления системы булевых функций подсистем для совместной логической минимизации / П. Н. Бибило, Н. А. Кириенко, В. И. Романов // Программные продукты и системы. - 2023. - Т. 36, № 4. - С. 509-522. - https://doi.org/10.15827/0236-235X.142.509-522.

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

18. Бибило, П. Н. Система логической оптимизации функционально-структурных описаний цифровых устройств на основе продукционно-фреймовой модели представления знаний / П. Н. Бибило, В. И. Романов // Проблемы разработки перспективных микро- и наноэлектронных систем. - 2020. - Вып. 4. - С. 9-16. - https://doi.org/10.31114/2078-7707-2020-4-9-16.

19. Бибило, П. Н. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-пред ставлений систем булевых функций / П. Н. Бибило, Ю. Ю. Ланкевич // Программные продукты и системы. - 2020. - Т. 33, № 3. - С. 449-463. - https://doi.org/10.15827/0236-235X.131.449-463.

20. Ashenden, P. J. VHDL-2008. Just the New Stuff / P. J. Ashenden, J. Lewis. - Burlington, MA, USA : Morgan Kaufman Publishers, 2008. - 909 p.