DOI: 10.17587/prin.15.176-189

УДК: 519.714.5

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

П. Н. Бибило, д-р техн. наук, проф., зав. лаб., bibilo@newman.bas-net.by, Н. А. Кириенко, канд. техн. наук, доц., ст. науч. сотр., kir@newman.bas-net.by, В. И. Романов, канд. техн. наук, доц., вед. науч. сотр., rom@newman.bas-net.by, Объединенный институт проблем информатики Национальной академии наук Беларуси, Минск

Описаны результаты экспериментального сравнения программ технологически независимой минимизации сложности многоуровневых представлений систем полностью определенных функций на основе разложения Шеннона. Основное внимание уделено эффективности применения при синтезе логических схем программы, реализующей алгоритм решения задачи выделения из системы функций таких подсистем, для которых целесообразно проводить совместные минимизации многоуровневых представлений подсистем функций в виде бинарных диаграмм решений (BDD — Binary Decision Diagram), названных BDD-представлениями, и в виде булевых сетей. После выделения подсистем и их совместной минимизации выполняется синтез логических схем в библиотеке проектирования заказных цифровых сверхбольших интегральных схем, результаты сравниваются по площади кристалла и по быстродействию (временной задержке) на потоке из 39 промышленных примеров схем. Установлено, что для 20 примеров алгоритм выделения подсистем позволяет получить лучшие решения, чем совместная либо раздельная минимизация многоуровневых представлений на основе разложения Шеннона (13 примеров). Три лучших решения получены в результате применения известной программы Espresso минимизации функций в классе ДНФ (дизъюнктивных нормальных форм), а три лучших решения получает синтезатор LeonardoSpectrum по исходным (неоптимизированным) матричным представлениям систем ДНФ булевых функций.

Ключевые слова: система булевых функций, дизъюнктивная нормальная форма (ДНФ), Binary Decision Diagram (BDD), булева сеть, синтез логической схемы, VHDL, СБИС, КМОП-технология

Стр. 176–189

Ссылка для цитирования:
Бибило П. Н., Кириенко Н. А., Романов В. И. Экспериментальное исследование алгоритма выделения подсистем булевых функций для совместной многоуровневой оптимизации // Программная инженерия. 2024. Том 15, № 4. С. 176—189. DOI: 10.17587/prin.15.176-189.