Программные продукты и системы

Статьи из выпуска № 3 за 2020 год.

Упорядочить результаты по: Дате публикации | Заголовку статьи | Авторам

21. Экспериментальное сравнение эффективности алгоритмов оптимизации BDD-представлений систем булевых функций [№3 за 2020 год]
Авторы: Бибило П.Н., Ланкевич Ю.Ю.
Просмотров: 5633
В статье описываются результаты экспериментального сравнения программ технологически независимой минимизации сложности многоуровневых представлений систем полностью определенных функций на основе разложения Шеннона. Графической формой таких представлений являются Binary Decision Diagrams (BDD) – диаграммы двоичного выбора. Порядок переменных, по которым ведется разложение Шеннона, влияет на размер BDD, поэтому задача минимизации сложности формы представления сводится к поиску оптимального порядка переменных разложения, при котором количество вершин графа BDD будет минимальным. Для поиска оптимального порядка переменных разложения используются эвристические алгоритмы, поскольку полный перебор для задач большой размерности сложно либо невозможно осуществить за приемлемое время с использованием современных вычислительных средств. Сравниваются результаты, полученные с помощью новых и ранее предложенных эвристик. После получения минимизированных по числу вершин графов BDD, заданных в виде совокупности взаимосвязанных формул разложения Шеннона, выполняется синтез логических схем в одной и той же библиотеке проектирования заказных цифровых КМОП сверхбольших интегральных схем, результаты сравниваются по площади кристалла и по быстродействию (временной задержке). Дополнительного сокращения сложности логических описаний и улучшения результатов синтеза схем во многих случаях можно добиться, выполняя дополнительную логическую минимизацию на основе булевых сетей. Критерием оптимизации в данном случае является число вершин булевой сети без учета инверсий булевых переменных, что хорошо согласуется с критерием «число литералов» при оптимизации многоуровневых логических схем.

◄ ← Предыдущая | 1 | 2 | 3