СОВРЕМЕННАЯ ЭЛЕКТРОНИКА №1/2015

ПРОЕКТИРОВАНИЕ И МОДЕЛИРОВАНИЕ 61 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА ◆ № 1 2015 мы на 10%, задержка исходной схемы снижалась примерно на 18%, при этом минимальное уменьшение задержки составляло 2%, а максимальное – 40%. Следует отметить, что требование получения схемы с малой задержкой при проектировании в целевой библи- отеке заказных СБИС часто вообще не может быть выполнено – схемные реа- лизации с требуемыми характеристика- ми задержек просто не существуют, поэ- тому никакие ухищрения и варьирова- ние параметров синтеза не помогают. Эксперимент 3 был посвящён срав- нению двух форм представления систем логических функций: дизъ- юнктивных нормальных форм (ДНФ) и бинарных диаграмм решений (Binary Decision Diagram, BDD) [6]. На потоке из 62 практических примеров было уста- новлено, что наиболее эффективной формой представления систем функ- ций при синтезе схем из библиотечных элементов являются логические урав- нения, соответствующие представлени- ям систем функций в виде BDD. Диаграммы решений строятся на основе разложения Шеннона. Разло- жением Шеннона полностью опреде- лённой булевой (логической) функции f ( x 1 ,..., x n ) по переменной x i называется представление f ( x 1 ,..., x n ) в виде: f ( x 1 ,..., x n ) = x _ i f ( x 1 ,..., x i – 1 , 0, x i + 1 ,..., x n ) ∨ ∨ x i f ( x 1 ,..., x i – 1 , 1, x i + 1 ,..., x n ). (1) Функции f ( x 1 ,..., x i – 1 , 0, x i + 1 ,..., x n ) и f ( x 1 ,..., x i – 1 , 1, x i + 1 ,..., x n ) в (1) являются коэффициентами разложения, они получаются из функции f ( x 1 ,..., x n ) под- становкой вместо переменной x i кон- станты 0 или 1, соответственно. Диа- грамма задаёт в виде графа последо- вательность разложений Шеннона исходнойфункции и получаемых коэф- фициентов разложения. Минимиза- ция сложности BDD основана на том, что в процессе разложения системы функций могут появляться одинаковые коэффициенты разложения не только у одной, но и у нескольких (либо даже у всех) функций, входящих в систему. Выделение одинаковых подфункций (коэффициентов разложения) приво- дит к сокращению аппаратной слож- ности и, соответственно, площади схе- мы. Минимизация BDD осуществлялась с помощью программы TIE_BDD [7]. Приведём пример многоуровневого разложения, соответствующего BDD. Обозначим через < x 1 , x 2 , x 3 , x 4 , x 5 , x 6 > первую из n ! перестановок перемен- ных, по которой проведём разложение Шеннона для системы ДНФ функций: f 1 = x 1 x 2 x _ 4 x 5 x _ 6 ∨ x _ 1 x 4 x _ 5 x 6 ∨ x 2 x _ 3 x 5 ; f 2 = x _ 1 x _ 4 x 5 x 6 ∨ x _ 1 x _ 3 x 5 ∨ x 1 x 2 x 3 x 5 x _ 6 ∨ ∨ x 1 x _ 2 x 4 x _ 5 x 6 ; f 3 = x 1 x _ 2 x _ 3 x 6 ∨ x 1 x _ 2 x 4 x 6 ∨ x 1 x _ 3 x 4 x 6 ∨ ∨ x _ 1 x 2 x _ 4 x 5 x _ 6 ∨ x 1 x _ 2 x 5 ∨ x 2 x _ 3 x 5 . Построенные для данной системы функций коэффициенты разложения Шеннона дают следующее многоуров- невое представление системыфункций: f 1 = x _ 1 ψ 1 ∨ x 1 ψ 2 ; f 2 = x _ 1 ϕ 2 ∨ x 1 ψ 3 ; f 3 = x _ 1 ψ 2 ∨ x 1 ψ 4 ; ψ 1 = x _ 2 ϕ 1 ∨ x 2 ϕ 1 ; ψ 2 = x 2 ϕ 2 ; ψ 3 = x _ 2 s 1 ∨ x 2 ϕ 3 ; ψ 4 = x _ 2 ϕ 4 ∨ x 2 ϕ 5 ; ϕ 1 = x _ 3 s 2 ∨ x 3 s 1 ; ϕ 2 = x _ 3 λ 3 ∨ x 3 s 3 ; ϕ 3 = x 3 λ 4 ; ϕ 4 = x _ 3 λ 2 ∨ x 3 s 2 ; ϕ 5 = x _ 3 s 2 ; s 1 = x 4 λ 1 ; s 2 = x _ 4 λ 3 ∨ x 4 λ 2 ; s 3 = x _ 4 λ 4 ; λ 1 = x 5 ω 1 ; λ 2 = x _ 5 ω 1 ∨ x 5 ; λ 3 = x 5 ; λ 4 = x 5 ω 2 ; ω 1 = x 6 ; ω 2 = x _ 6 . Основной проблемой при построе- нии многоуровневых представлений меньшей сложности является выбор перестановки переменных, которая приводит к возможно меньшему чис- лу логических выражений приведён- ного выше вида. В экспериментах про- грамма TIE_BDD строила BDD по 5000 случайно выбираемым перестановкам переменных и выбирала из рассмотрен- ных вариантов диаграммы наименьшей сложности. Эксперименты на практических при- мерах [2] комбинационных схем пока- зали, что в подавляющем большинстве случаев (41 пример из 62) использо- вание многоуровневых представле- ний вместо ДНФ позволяло синтези- ровать в версии L2011 схемы меньшей площади, чем по исходным описани- ям функций, соответствующих ДНФ. Напомним, что при синтезе функцио- нальные описания комбинационных схем в виде ДНФ и в виде разложений Шеннона были представлены на язы- ке VHDL. Некоторая информация об алгоритмах оптимизации, применяе- мых синтезатором LeonardoSpectrum, содержится в [5, с. 122]. Таким обра- зом, судя по результатам эксперимен- та 3, комбинационные схемы в библи- отечном базисе лучше синтезировать по минимизированным BDD, а не по минимизированным системам ДНФ, представляющим логические функции. Возможность уменьшения площади комбинационных схем имеется и при повторном синтезе описания, получен- ного с помощью команды unmap . Такие эксперименты с повторным синтезом, выполнением команды unmap и сме- ной целевых библиотек синтеза описа- ны в [8]. Стили кодирования (Encoding Style) не имеют значения для комби- национной логики, однако для схем с триггерами они позволяют варьиро- вать параметры площади и быстродей- ствия. С другими управляющими пара- метрами синтеза LeonardoSpectrum можно ознакомиться в [1]. В ЫВОДЫ На испытанном потоке проектов схем наилучшие решения по площа- ди давала версия L2003, по задержке – версия L2006. Новые версии програм- мы L2011 ориентированы на уменьше- ние площади схем, при этом задержки, естественно, увеличиваются. В верси- ях L2003 и L2006 установка критерия оптимизации «Delay» приводила к схе- мам с минимальной задержкой, однако для более поздних версий L2011 уста- новка критерия «Delay» практически не влияла на получение схемы с меньшей задержкой; минимум задержки прихо- дился на другие режимы, в основном, <Area, Standard>. При общем совершенствовании про- граммы LeonardoSpectrum в старых вер- сиях синтезатора можно реализовать лучшие решения. Поэтому в ответствен- ных случаях целесообразно выполнять синтез как в новых, так и в старых вер- сиях программы, и выбирать лучшие решения по тому или иному критерию. Л ИТЕРАТУРА 1. Бибило П.Н. Системы проектирования интегральных схем на основе языка VHDL. StateCAD, ModelSim, LeonardoSpectrum. СОЛОН-Пресс. 2005. 2. http://www1.cs.columbia.edu/~cs4861/sis/ espresso-examples/ex. 3. http://opencores.org/project ,8b10b_ encdec,overview. 4. Бибило П.Н., Кириенко Н.А. Оценка энерго- потребления логических КМОП-схем по их переключательной активности. Микро- электроника. № 1. 2012. С. 65–77. 5. LeonardoSpectrumUser’s Manual, Software Release 2011a. May 2011. 6. Кнут Д.Э. Искусство программирования. Том 4. А. Комбинаторные алгоритмы. Часть 1. ИД Вильямс. 2013. 7. Бибило П.Н., Леончик П.В. Алгоритм постро- ения диаграммы двоичного выбора для системы полностью определённых буле- вых функций. Управляющие системы и машины. № 6. 2009. С. 42–49. 8. Бибило П.Н., Романов В.И. Логическое проектирование дискретных устройств с использованием продукционно-фрей- мовой модели представления знаний. Ленанд. 2014.