Методы и алгоритмы линейных и аффинных преобразований для модели бинарных диаграмм решений

Состояние проблемы:

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

Интерес к диаграммам решений возрос после публикации [1], причем как к оригинальным диаграммам решений для функций-триггеров, где большинство исследователей ссылались на [2] и [3], так и для функций с несколькими выходами на [4]. ДР стали структурой данных, полученной сокращением деревьев решений (бинарных деревьев), с помощью использования общих изоморфных поддеревьев и удаления избыточной информации из деревьев решений для данной функции. Бинарные деревья были впервые представлены в диссертации [5] о некоторых проблемах в теории дискретных множеств, защищенной в 1935 году в Сорбонне. Разложение Шеннона имеет вид: / = vxjx-, (1 </'<�")•.

Рассмотрим бинарное дерево (рисунок 1), где на каждом узле применяется разложение Шеннона по одной из переменных. Таким образом, функция разбивается на несколько подфункций, а дерево соответственно на несколько поддеревьев.

Пунктиром обозначается нулевое значение переменной, а сплошной линией — единичное. На каждом уровне присутствует только одна переменная, по которой и выполняется разложение функции (рисунок 1).

• • ¦

Рис. 1. Бинарное дерево.

Для определения значения функции, заданной бинарным деревом для конкретного набора переменных, проходится путь от корня к оконечной вершине, следуя значениям соответствующей переменной. Бинарное дерево является достаточно громоздким средством графического представления булевой функции, обладая при этом некоторой избыточностью. Для уменьшения количества узлов применяются следующие сокращения. В исходном бинарном дереве отождествляются изоморфные подграфы, эта процедура показана на рисунке 2.

Рис. 2. Удаление изоморфности из бинарного дерева.

Если после отождествления изоморфностей сократить узлы, которые указывают на один узел (таким образом, как показано на рисунке 3),.

Рис. 3. Сокращение узлов, оба выхода которых указывают на один и тот же узел. в результате получится бинарная диаграмма решений (БДР).

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

Основной недостаток приложений, базирующихся на бинарных диаграммах решений, — это то, что структуры данных являются зависимыми от порядка переменных, а также что для некоторых функций не существует эффективного представления, например для булевских ^ умножений. Для решения проблемы оптимального порядка переменных были написаны специальные алгоритмы, частично сокращающие перебор полного множества вариантов. Для решения проблемы представления умножения и для повышения общей компактности были предложены несколько расширений базовой структуры двоичных диаграмм решенийнапример диаграммы с подавлением нуля (ZBDD)[89]. При этом продолжается также поиск других путей сокращения размера бинарных диаграмм решений. Линейные преобразования были очень обнадеживающей концепцией, так как непосредственно структуры данных остаются неизменными, а изменяются (перекодируются) только входные переменные, причем для сохранения результирующих значений изменяется и сама функция. Также следует отметить, что даже такая значительно более простая задача, как нахождение оптимального порядка переменных, является NP-полной [12]. В случае с линейными преобразованиями ситуация осложняется тем, что количество вариантов линейных преобразований по сравнению с перестановками входящих переменных существенно больше. В работе «Линейные преобразования и точная минимизация BDD» Wolfgang Gunter и Rolf Drechsler (1998) [7] применили расширение метода перестановок (permutations) линейными преобразованиями и получили более хорошие результаты минимизации бинарных диаграмм решений. Однако, несмотря на высокую эффективность, алгоритм имеет очень большую сложность. Идея заключается в том, чтобы найти такое линейное преобразование, при котором сложность реализации преобразования и видоизмененной функции будет меньше, чем исходной. Тогда для нахождения оптимального линейного преобразования вместо преобразований над таблицей функции, что обычно и делается в спектральных методах, преобразуются только входные переменные.

То есть если рассмотреть исходный вектор переменных X, линейное преобразование Z, то в результате получим схему преобразования, показанную на рисунке 4. s L.

X) Y.

Рис. 4. Иллюстрация преобразования переменных и изменения функции.

Таким образом, имеем: АХ = Y, где Yэто преобразованный вектор переменных, а, А — матрица, задающая линейное преобразование L. Если исходная функция была /, то формула fY) = A (f (X)) будет задавать измененную функцию.

Для реальной практической ценности этого метода минимизации в результате сложность представления измененной функции и матрицы преобразования должны быть меньше сложности представления исходной функции.

Смысл минимизации линейными преобразованиями заключается в поиске наименьшего или приемлемого по размеру (в смысле количества узлов) в бинарной диаграмме решений преобразованной функции по сравнению с исходной БДР. Для получения исходной функции из преобразованной применяется схема, показанная на рисунке 5.

Для задания линейных преобразований используются матрицы размерности их л вместо матриц размером 2″ х2и применяемых в спектральных методах, где п — число входящих переменных. Для некоторых функций при использовании линейных преобразований может быть получено экспоненциальное уменьшение количества узлов в результирующей бинарной диаграмме решений.

Рис. 5. Схема получения исходной функции из преобразованной.

Этот подход к минимизации интересен простой реализацией результатов вычислений: достаточно преобразовать входящие переменные умножением на матрицу размерности пхп и получается значительно упрощенная схема. Но NP-полнота точных алгоритмов и огромное п-1 количество вариантов ]~[(2Л-2') [7] линейных преобразований позволяет 0 осуществлять линейное преобразование для получения минимально возможной функции (точную оптимизацию) только на функциях с очень небольшим количеством переменных. Поэтому в настоящее время производятся поиски различных эвристических алгоритмов, которые давали бы вполне приемлемые результаты, но имели бы значительно меньшие требования как по времени вычислений, так и по другим требуемым ресурсам.

Для преодоления проблем, связанных с большой размерностью БДР при реализации булевских умножений, и для более компактного представления функций были предложены расширения структуры БДР. Этой области посвящено достаточно много современных работ. Расширениями БДР (ЕЮО) являются KDD (Kronecker Decision Diagrams).

6], PKDD (Pseudo-Kronecker Decision Diagrams) [6], ZBDD[89]. Различия заключаются в следующем:

В бинарной диаграмме на каждом узле применяется разложение Шеннона. При этом кроме объединения изоморфных ветвей применяется удаление узла, если его исходящие ветви указывают на один узел. Другие виды диаграмм решений. используют различные комбинации типа разложения и метода сокращения «вырожденных» узлов, как например, ZBDD (Zero suppressed Binary Decision Diagram — Бинарные диаграммы решений с подавлением нуля). В ZBDD — вместо удаления вершины, у которой исходящие ветви указывают на один узел, применяется удаление узлов, если единичный выход указывает на 0. Этот метод в общем случае хуже, чем в бинарной диаграмме решений (BDD), но значительно лучше в некоторых специальных случаях, например при реализации булевских умножений.

Диаграммы решений Кронекера (KDD) являются расширением BDD путем использования разложений positive Davio Expansion и Negative Davio Expansion. В этом случае на каждом уровне применяется либо разложение Шеннона, либо Davio Expansion, либо Negative Davio Expansion.

Псевдо-Кронекеровские диаграммы решений (PKDD) — расширение KDD, но в этом случае на одном уровне можно использовать разложения positive Davio Expansion и Negative Davio Expansion, либо разложение Шеннона.

В работе [6] описываются преимущества PKDD над BDD, но при этом опять возникает проблема построения оптимального PKDD. Процесс построения оптимальной псевдо-кронекеровской диаграммы решений сам по себе является процессом оптимизации и для этого требуются большие вычислительные ресурсы. Поэтому при построении PKDD также применяются эвристические алгоритмы. При этом по проведенным исследованиям на случайных функциях от 15 переменных, размер PKDD составляет около 65% от базовой функции.

В работе [7] описан метод точной минимизации BDD, с использованием линейных преобразований над входящими переменными. Метод является расширением линейными преобразованиями метода перестановок, и имеет сложность N1, где N = 2″ - количество значений функции. Значение N1 является слишком большой величиной, и поэтому применение метода возможно только для функций от небольшого количества переменных (не более 6).

Несмотря на то, что были созданы достаточно эффективные алгоритмы для сокращения размера BDD, они базируются на различных переборах, — осталась открытой проблема построения эвристического логического метода, не базирующегося на различном переборе возможных вариантов. Дело в том, что созданные алгоритмы базируются на методах перестановки и поиска линейных преобразований, но ограничивают их различными способами, чтобы получить сложность алгоритма, приемлемую для вычислений. То есть, например, в качестве ограничения используется перебор не по всем переменным, а только по нескольким соседним и тому подобное. Но ключевым фактором остается перебор. В данной же работе производится поиск критерия, который позволит уменьшить сложность BDD путем поиска преобразований над соседними переменными. Это приведет к полиномиальной сложности алгоритма относительно размера таблицы значений функции (2″). Для обеспечения возможности полного перебора всех возможных значений для нахождения характерных случаев неоптимальности, исследования при построении критериев производились на функциях небольшого размера (до 4-х переменных).

Актуальность проблемы:

Бинарные диаграммы решений (БДР или ROBDD в англоязычной литературе) являются одной из моделей представления булевых функций в виде направленного нецикличного графа и имеют связь с топологией реальных схем.

На практике бинарные диаграммы решений можно реализовать с помощью элементарных мультиплексоров, то есть БДР напрямую отображается в архитектуру аппаратных средства, например программируемые логические устройства и используется на стадии синтеза таких устройств (рисунок 6).

Функция (схема) /-к.

— V.

Модель в виде бинарной диаграммы решений л V.

Л У.

Реализация.

Рис. 6. Схема связи функции, модели БДР и реализации.

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

Бинарные диаграммы решений являются эффективным способом манипуляции большими структурами данных. Бинарные диаграммы решений широко применяются в верификации для задания различных характеристических функций.

Необходимость в исследованиях, направленных на поиск алгоритмов для сокращения размера БДР, обусловлена отсутствием приемлемых по сложности точных методов для нахождения минимально возможной диаграммы. Это связано с тем, что точные алгоритмы для нахождения минимальной диаграммы, известные на сегодняшний день, использующие различные фиксированные классы преобразований, очень близки к полному перебору и не удовлетворяют по сложности возможностям вычислительной техники для их эффективного использования. Поэтому производятся поиски эвристических алгоритмов для сокращения размера бинарных диаграмм решений, которые дают приемлемые по критерию соотношения сложности к эффективности результаты. В связи с этим актуальной задачей является построение таких эвристических алгоритмов. Преобразования над входящими переменными интересны тем, что преобразования в результате производятся не над таблицей функции, а только над входящими переменными. При этом преобразование является линейным и задается матрицей размером пхп, вместо матриц размерности 2″ х2″ 5 которыми описываются преобразования над таблицей функции, где пчисло входящих переменных. Идея линейного преобразования входных переменных в задаче уменьшения размера схем заключается в том, что вычисление исходной выходной функции разбивается на два этапа. Сначала производится линейное преобразование переменных, после чего вместо исходной выходной функции схема вычисляет «измененную» функцию, чтобы получить «правильное» выходное значение. Таким образом /(*".,*") = z (/(x".,*")).

В процессе сокращения бинарной диаграммы решений с помощью линейных преобразований получается линейное преобразование L и измененная функция /, которая имеет БДР меньшей сложности чем /. Под сложностью при этом понимается количество узлов в БДР.

На практике использование линейного преобразования имеет смысл в том случае, если линейное преобразование L и функция / реализуются проще, чем исходная функция /. Если эффективная реализация линейного преобразования на основе двоичных сумматоров имеет удовлетворительное решение, то точная минимизация схем общего вида на основе линейных преобразований затруднена из-за огромного количества преобразований, которое быстро растет с увеличением размера схем.

Бинарные диаграммы решений были использованы разработчиками CAD (САПР СБИС) при построении схем для ПЛИСов в основном на стадии логической декомпозиции функций. Сейчас декомпозиция функций, основанная на бинарных диаграммах решений, называется BDS — что расшифровывается как BDD-based Decomposition System [33]. Также показано, что этот подход может эффективно использоваться как для алгебраических, так и для булевых (а также AND-OR и AND-XOR) декомпозиций. При этом используются бинарные диаграммы решений для представления и манипуляций булевыми функциями и выполнения логической декомпозиции.

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

Теперь рассмотрим некоторые статьи, имеющие отношение к преобразованию бинарных диаграмм решений с целью уменьшения их размера. Эта задача является актуальной, так как размер БДР непосредственно влияет на размер схем, например при построении ПЛИС.

В статье [12] «Использование нижних оценок в процессе динамической минимизации бинарных диаграмм» приводится описание метода нижних оценок для упрощения при оптимизации размера бинарных диаграмм путем поиска оптимального преобразования. В статье приводится сложность поиска оптимальной последовательности переменных. Она составляет 0(п2*3″), где п — количество входящих переменных. Применение этого метода в среднем на 50% сокращает время поиска оптимального результата. Но с точки зрения сложности 0(3″) является очень большой величиной, также следует учитывать, что в данном виде оптимизации применяются только перестановки переменных, без линейных преобразований. Этот критерий может быть использован только для сокращения перебора. Если рассматривать оптимизацию как приведение функции к определенному виду, данный метод не подходит.

В работе [7] «Линейные преобразования и точная минимизация BDD» представлен алгоритм нахождения оптимального линейного преобразования переменных булевой функции для минимизации соответствующей двоичной диаграммы решений. В результатах показано, что бинарные диаграммы могут быть существенно сокращены при использовании линейных преобразований. Так как перестановка входит в подмножество линейных преобразований, то их применение для минимизации бинарных диаграмм увеличивает возможности. Всего п— линейных преобразований J~[(2″ -2'), что меньше чем 2й!, но существенно i-0 больше, чем и! (количества перестановок переменных). При этом используется разложение конечного преобразования на более простые, или это можно рассматривать как произведение более простых матриц, каждая из которых соответствует простому преобразованию. Из-за большой сложности вычислений данный алгоритм подходит только для функций, имеющих не более 6 входящих переменных.

В работе [20] «Диаграммы решений в синтезе. Алгоритмы, расширения и приложения» дан обзор различным видам диаграмм решений. Наиболее популярными являются бинарные диаграммы решений. Но они имеют ряд недостатков, один из которых — это экспоненциальный размер относительно некоторых функций, например умножителей. Поэтому для решения данной проблемы применяются некоторые другие виды диаграмм решений. В работе описаны различные типы применяемых разложений и редукций, и в зависимости от этого получается определенный тип диаграммы решений. Кроме этого, описываются различные методы минимизации для диаграмм решений, а также понятие World level DD и смешанных диаграмм решений.

Генетический алгоритм для получения оптимального порядка переменных" [22] - представлен алгоритм нахождения оптимального порядка переменных для минимизации бинарных диаграмм решений. Это альтернатива точному алгоритму нахождения оптимального порядка переменных. При аналогичных результатах с точным алгоритмом на приведенных тестах он позволяет сократить время поиска в среднем на 50%. Но подход к минимизации двоичных диаграмм решений путем поиска оптимального порядка переменных уже достаточно хорошо изучен и из-за меньшего количества вариантов дает менее хорошие результаты, чем использование линейных преобразований.

EXOR преобразования входящих переменных, для разработки эффективных двухуровневых AND/EXOR сумматоров" [40]. В работе показано результатами и доказано, что сумматоры, которые имеют экспоненциальное представление в виде бинарных диаграмм, можно после линейных преобразований представить в виде бинарных диаграмм, сложностью 0(пг).

Минимизация размера ROBDD неполностью заданных булевых функций используя строгую симметрию" [39]. Идея работы заключается в том, что симметричные блоки фиксируются, а на остальную часть применяются обычные перестановки. Метод является достаточно эффективным, но было доказано, что результаты будут хуже, чем при обычных перестановках. Но при этом уменьшается время обработки.

В работе S. Minato [89] представлены бинарные диаграммы решений с подавлением нуля (ZBDD), которые были разработаны как альтернатива классическим двоичным диаграммам решений для случаев, когда бинарные диаграммы оказываются неэффективными. Отличаются от БДР методом применяемой редукции. В бинарных диаграммах узел удаляется, если оба его выхода указывают на одну вершину, а для ZBDD — если единичная ветвь указывает на 0.

Минимизация бинарных диаграмм, используя линейные преобразования, основываясь на эволюционной технике" [18] Алгоритм работает следующим образом:

1. Случайно выбираются две переменные и одна из них заменяется на их сумму по модулю два.

2. Повторение пункта 1 дважды.

3. Перестановка двух переменных.

4. Линейный сдвиг.

5. Инверсия: в случайно выбранном окне из 8-ми переменных инвертировать порядок переменных в окне.

6. Удаление линейного преобразования переменных.

7. Точная минимизация: выбор трех переменных и нахождение оптимального линейного преобразования с использованием точного алгоритма.

Согласно тестам, алгоритм показывает неплохие результаты за приемлемое время. Но остается подход упрощенного перебора.

Представление неполностью заданных функций, используя диаграммы решений Псевдо-Кроннекера" [6]. В этой статье дается определение BDD (бинарных диаграмм решений), KDD и PKDD. В PKDD в узлах применяется одно из 3 разложений (S, pD, nD (Формулы 1.1−1.3)). Всего вариантов для задания PKDD З2″ «1 и, выбирая для каждого узла одно из разложений, можно упростить PKDD. В статье рассмотрен эвристический алгоритм для минимизации PKDD для неполностью заданных функций. Метод заключается в минимизации функции, последовательно используется сначала неполное задание функции, затем производится минимизация построением KDD, затем PKDD.

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

Цель и задачи исследования

:

Целью диссертации является исследование возможностей уменьшения размера БДР путем преобразования ее к некоторому виду на основе разработанных критериев. Для достижения этой цели было произведено следующее:

• Выделение «базисных» преобразований и изучение влияния этих преобразований на функцию. Исследование возможностей преобразования булевой функции с использованием базисных преобразований.

• Разработка критериев, обеспечивающих сокращение размера бинарных диаграмм решений.

• Разработка алгоритмов на базе полученных критериев.

• Экспериментальная проверка влияния алгоритмов на размер бинарных диаграмм решений.

• Обоснование верхней оценки для сложности алгоритма.

• Исследование возможностей улучшения критериев и алгоритмов для получения лучших результатов.

Научная новизна:

В диссертации получены следующие результаты, которые выносятся на защиту и характеризуются научной новизной.

• Предложен новый подход к сокращению размера бинарных диаграмм решений.

• Получены результаты влияния линейных и аффинных преобразований на бинарные диаграммы решений.

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

• Создан комплекс программ, реализующий разработанные критерии и алгоритмы.

• Найдена верхняя оценка для числа шагов алгоритма. Практическая ценность и реализация результатов работы:

В диссертации построены новые алгоритмы для сокращения размера бинарных диаграмм решений (БДР). Показано, что можно уменьшить размер бинарной диаграммы решений путем приведения булевой функции к виду, удовлетворяющему некоторому критерию, используя линейные и аффинные преобразования над входными переменными. В ходе построения результирующего преобразования используются преобразования только над соседними переменными, что уменьшает число шагов алгоритма. Разработанные алгоритмы можно использовать для выделения подклассов базовых функций, с помощью которых можно задать любую другую булеву функцию, зависящую от соответствующего количества входящих переменных. Разработан комплекс программ для реализации алгоритмов, работающий под операционной системой Windows с использованием средства разработки Microsoft Visual С++. Разработанный программный комплекс используется в учебном процессе на факультете ВМК КГУ при выполнении курсовых и дипломных работ студентов. Результаты также использованы при моделировании цифровых систем в Институте проблем информатики Академии наук Татарстана и в предприятии Сканер. Имеются соответствующие справки о внедрении.. Работа поддержана грантом № 05−5.2−234 из средств Фонда НИОКР Татарстана. Апробация:

Основные положения диссертационной работы докладывались и обсуждались:

1. Fifth International Workshop on Applications if Reed-Muller Expansions in Circuit Design, August 10−11., Mississippi State University.- 2001.

2. Четвертая международная конференция «Автоматизация проектирования дискретных схем», 14−16 ноября, Минск.- 2001.

3. XXVIII International conference (Information Technologies in Science, Education, Telecommunication, Business, autumn session) IT+SE'2001, Yalta, Ukraina.- 2001.

4. XIII Международная Конференция «Проблемы теоретической кибернетики» Казань, 27−31 мая.- 2002.

5. На семинарах на кафедрах прикладной математики КГУ, теоретической кибернетики КГУ, компьютерных систем и информационной безопасности КГТУ им. Туполева.

Публикации:

По теме диссертации опубликованы 5 работ, из них 4 статьи и 1 тезисы. Работы приведены в списке литературы. Структура и объем работы:

Диссертационная работа состоит из введения, четырех глав, заключения и приложения, изложенных на 139 страницах, содержит 26 рисунков, 1 таблицу, список литературы из 102 наименований. Диссертация состоит из четырех глав.

Основные результаты работы:

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

2. Предложена модель сокращения размера БДР с помощью линейных и аффинных преобразований входящих переменных.

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

4. Доказана теорема о том что любое преобразование можно задать, пользуясь композицией преобразований над соседними переменными.

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

6. Доказана теорема о том что алгоритм однородности конечен и отрабатывает за число шагов не более чем O (NlogN), где N = 2″ размер таблицы истинности функции.

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

Заключение

.