Логическая оптимизация комбинационных логических схем (Логическая оптимизация комбинационных логических схем.pdf)

Математические модели и методылогического синтеза СБИСОсень 2015Лекция 4План лекции• Логическая оптимизация комбинационныхлогических схем– Различные способы представления функций алгебрылогики (ФАЛ) (таблицы истинности, формулы,двоичные решающие диаграммы, схемы изфункциональных элементов). Сравнение указанныхпредставлений и их ограничения.– Комбинационные логические сети (КЛС). Задачаоптимизации КЛС (различные постановки задач,функционалы качества при оптимизации КЛС).Основные типы преобразований КЛС: исключение,разложение, экстракция, упрощение и подстановка.Способы представленияфункций алгебры логикиЛекция 4Способы представления функций алгебрылогики• Таблица истинности = (01101001)• Дизъюнктивная нормальная форма (ДНФ) = 1 ∨ 2 • Формула в заданном базисе = 1 |2 ∼ • Схема из функциональных элементов (СФЭ) в заданномбазисе1&∨2&Способы представления функций алгебрылогики• Двоичные решающиедиаграммы• Комбинационныелогические сетиF(A, B, C)A2BBCC01A>B>C1 = 2 ∨ 33 = 1 ∨ Сравнение различных представленийфункций алгебры логикиТаблицаистинностиДНФФормулаСФЭBDDКЛСДопустимоечислопеременныхМалоеСреднееБольшоеБольшоеБольшоеБольшоеУникальностьпредставления+---+-Зависимостьот базиса--++--СложностьпредставленияЛинейнаяотносительночисла входныхнаборовЗависит отФАЛЗависит отФАЛ ибазисаЗависит отФАЛ ибазисаЗависит отФАЛ ипорядкаследованияпеременныхЗависит отструктурыКЛСКомбинационные логическиесетиЛекция 4Структура комбинационныхлогических сетей• Комбинационная логическая сеть (КЛС) –ациклический ориентированныйпомеченный граф Σ = (, ) специальнойструктуры• Множество вершин = , , Σобразуют разбиение:– - множество основных входов– - множество основных выходов– Σ - множество внутренних вершин = (… )Внутренние вершиныкомбинационных логических сетей• Каждой внутренней вершине КЛС приписаны:– внутренняя переменная ∈ – ФАЛ , зависящая от переменных из множества ⊆ × , и соответствующая этой ФАЛпредставление в некоторой модели = (01101001)Таблица истинности = 1 ∨ 2 ДНФ = 1 |2 ∼ Формула :12 :&&1 :2∨0СФЭ и AIG1BDD1 = 2 ∨ 3 = 1 ∨ 3КЛСДуги комбинационных логическихсетей• Основные входы являются истоками• Основные выходы являются стоками• Дуга = , ∈ существует в КЛС Σ = , ,если ФАЛ, реализуемая в зависит от ФАЛ,реализуемой в = (… ) = (… , , … ) = (… , , … )Функционированиекомбинационных логических сетей• Основные входы реализуют тождественныеФАЛ• Так как граф КЛС является ациклическим, тоФАЛ (как функции основных входов),определяются последовательно на основетопологического порядка внутренних вершин = (… , (… ), … ) = (… )<Комбинационная логическая сеть пример121 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 512 = 1 ∨ 2 ∨ 3 5 ∨ 4 523 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 534 = 1 ∨ 2 ∨ 34345Комбинационная логическая сеть пример111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Оптимизация комбинационныхлогических сетей• Преобразование КЛС за счет специальныхопераций• Все операции должны сохранятьэквивалентность исходной и преобразованнойсхемы с точки зрения реализуемых выходныхфункций• Преобразования можно разделить на двакласса:– преобразования вершин (локальные)– преобразования структуры схемы (глобальные)Функционалы качества при оптимизациякомбинационных логических сетей• Сначала определяются функционалы качествадля внутренних вершин КЛС, а потом на ихоснове определяются функционалы качествадля КЛС в целом• Функционалы качества во внутреннейвершине определяется на основепредставления, которое используется длязадания ФАЛ, реализуемой в этой вершине• Для иерархических КЛС функционалы качестваопределяются рекурсивноФункционалы качества комбинационныхлогических сетей• Для ДНФ – Длина (A) – число элементарных конъюнкций в – Сложность(ранг) - число букв в • Для формулы – Ранг - число букв в – Сложность () – число операций в – Глубина - глубина корня формулы • Для СФЭ Σ– Сложность () – число функциональныхэлементов в Σ– Глубина - максимальная длина пути от входовдо выходов СФЭ Σ = 1 ∨ 2 ДНФ = 1 |2 ∼ Формула :12&&∨СФЭ и AIGФункционалы качества комбинационныхлогических сетей• Для BDD :– Сложность - числонетерминальных вершин в BDD – Глубина - глубина корня BDD 1ДНФ01BDD• Для КЛС Σ– Сложность () – сумма сложностейво всех внутренних вершинах КЛС Σ– Глубина - максимальнаявзвешенная глубина пути от входов довыходов КЛС Σ :21 = 2 ∨ 3 = 1 ∨ 3КЛСЗадача оптимизации комбинационныхлогических сетей• Построение КЛС для заданной системыФАЛ с наилучшими значения выбранныхфункционалов качества• Многокритериальная задача оптимизациивыбранных функционалов качества• Однокритериальная задача оптимизациивыбранного функционала качества сдополнительными ограничениями надругие функционалы качестваПространство решений задачи оптимизациикомбинационных логических сетей(Σ)21 = 2 ∨ 33 = 1 ∨ Решение с заданнымизначениями Σ и (Σ)Пространство решений (Design space)(Σ)Пространство решений задачи оптимизациикомбинационных логических сетей(Σ)21 = 2 ∨ 33 = 1 ∨ Не улучшаемое решениепо параметрам Σ и (Σ)Пространство решений (Design space)(Σ)Парето оптимальная кривая решениймногокритериальной задачи оптимизации(Σ)ПаретооптимальнаякриваяПространство решений (Design space)(Σ)Однокритериальная задача оптимизации сдополнительными ограничениями(Σ) Σ < ∗Оптимальноерешение призаданныхограничениях наглубинуПространство решений (Design space)(Σ)Преобразования комбинационныхлогических сетей• Исключение (ELIMINATION) – удаление внутренней вершиныКЛС и соответствующая подстановка ФАЛ, реализуемой этойвершиной в другие вершины• Разложение (DECOMPOSITION) – замена внутренней вершинынесколькими вершинами, которые формируют подсеть,реализующую такую же ФАЛ, что и исходная вершина• Извлечение (EXTRACTION) – добавление новой внутреннейвершины, которая реализует ФАЛ, являющейся подфункциейдля нескольких других внутренних вершин, и соответствующаяподстановка символа новой вершины в указанные вершины• Упрощение (SIMPLIFICATION) – оптимизация представленияФАЛ, реализуемой во внутренней вершине• Подстановка (SUBSTITUTION) – упрощение представления ФАЛ,реализуемой в вершине за счет увеличения числапеременных, от которых зависит указанная ФАЛПример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример исключения (ELIMINATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2454 = ∨ ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33-3+2=32, Глубина: 3-1=2.Пример разложения(DECOMPOSITION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример разложения(DECOMPOSITION)111 = ( ∨ ∨ ) ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример разложения(DECOMPOSITION)1 = ∨ ∨ 22 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2451 = 4 ∨ 1 53 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 312Сложность: 33-8+3+4=32, Глубина: 3.Пример извлечения (EXTRACTION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример извлечения (EXTRACTION)1234511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 52 = ( ∨ )53 = 2 ∨ 14 = 3 ∨ 235 = ( ∨ )(1 ∨ 2 ) ∨ 56 = 1 ∨ 227 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33, Глубина: 3.Пример извлечения (EXTRACTION)122 = 53 = ( ∨ )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = ∨ ∨ 33 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33-4-9+2+2+5=29, Глубина: 3.Пример упрощения (SIMPLIFICATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Сложность: 33, Глубина: 3.Пример упрощения (SIMPLIFICATION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 2453 = 2 ∨ 14 = 3 ∨ 27 = ∨ 2Сложность: 33-6+2=29, Глубина: 3.Пример подстановки(SUBSTITUTION)111 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 522 = 3 5 ∨ 4 535 = 1 3 ∨ 1 4 ∨ 2 3 ∨ 2 4 ∨ 5346 = 1 ∨ 243 = 2 ∨ 14 = 3 ∨ 27 = 6 3 ∨ 6 3 ∨ 6 32Произведем экстракцию 3 ∨ 4 в вершинах 2 и 55Сложность: 33, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 53 = ( ∨ )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = ∨ ∨ 33 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 33-4=29, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 9 539 = (3 ∨ 4 )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 54 = 3 ∨ 225 = 9 ( ∨ ) ∨ 533 = 2 ∨ 17 = 6 3 ∨ 6 3 ∨ 6 34Сложность: 29, Глубина: 3.Пример подстановки(SUBSTITUTION)122 = 9 539 = (3 ∨ 4 )46 = 1 ∨ 2511 = 1 4 ∨ 2 4 ∨ 3 4 ∨ 1 53 = 2 ∨ 14 = 3 ∨ 25 = 9 ∨ 57 = 6 3 ∨ 6 3 ∨ 6 3234Сложность: 29-4+2=27, Глубина: 3..