Содержание к диссертации
Введение
Глава 1. Применение спектров Уолша в логическом синтезе 21
Глава 2. Анализ сложности булевых функций 36
2.1. Вычислительная сложность задач и методы ее уменьшения 36
2.1.1 Вычислительный аспект сложности дискретных задач 36
2.1.2 Методы решения труднорешаемых задач 39
2.2. Сложность булевых функций. Критерии сложности 40
2.3. Анализ БФ с использованием спектров 44
Глава 3. Линеаризация функций 50
Глава 4. Логический синтез для программируемых пользователем вентильных матриц (ППВМ) 61
4.1. Архитектура ППВМ 61
4.2. Особенности задачи синтеза для ППВМ 75
Глава 5. Генерация и визуализация функций 86
5.1 Методика генерации функций 86
5.2 Методика визуализации функций 92
Глава 6. Экспериментальная часть 96
6.1 Основные проблемы и пути их решения 96
6.2 Реализация методики генерации функций 98
6.3 Структура программы и особенности ее реализации 100
6.4 Проверка правильности положений о визуализации функций 104
6.5 Примеры практического применения 105
Заключение 110
Библиография 111
Приложение 1 124
Приложение 2 142
- Применение спектров Уолша в логическом синтезе
- Вычислительный аспект сложности дискретных задач
- Особенности задачи синтеза для ППВМ
- Реализация методики генерации функций
Введение к работе
Научно-технический прогресе в области создания новых типов ЭВА в значительной мере зависит от успешного решения проблемы автоматизированного проектирования. Автоматизированное проектирование позволяет не только сократить время разработки продукта, но и сроки его выхода на рынок. В условиях формирующегося рынка это часто является фактором, определяющим успех. Кроме того, автоматизация позволяет уменьшить стоимость проектирования и увеличить качество, уменьшить количество ошибок на каждом из этапов проектирования. Увеличение степени интеграции приводит к существенному росту функциональной сложности объектов проектирования. А из того факта, что время, затрачиваемое на этап конструирования составляет 80% общего времени разработки СБИС [114], следует, что одним из наиболее актуальных являются вопрос автоматизации проектирования.
Значительный вклад в развитие теории и практики автоматизации проектирования (в частности синтеза схем) внесли В.М. Глушков, Л.Б. Абрайтис, В.М. Курейчик, Д.А. Поспелов, В.А. Горбатов, И.П. Норенков, О.Б Лупанов, Р.Г. Нигматуллин, СВ. Яблонский, М.П Карповский, Л.А. Шоломов, Е.А. Бутаков, А.Я. Тетельбаум, Э.И. Нечипорук, А.Д. Закревский, В.И. Варшавский и многие другие. Из западных ученых необходимо отметить фамилии R.K. Brayton, R. Murgai, A. Sangivanni-Vincentelli, К. Keutzer, R. Lechner, A. Moezzi, C. Moraga, M.G. Karpovsky, J.C. Muzio, S.L. Hurst, E. Stabler, G.D. Hatchel, R. Rudell, H. Curtis и другие.
В электронной промышленности в настоящее время наблюдается значительный рост интереса к средствам автоматического ЛС. По существу, любой из видов синтеза обеспечивает связь между различными уровнями абстрактных описаний объекта. Помимо преимуществ, возникающих при создании схем на базе описаний более высокого уровня абстракции, существуют и другие преимущества ЛС, в том числе:
• повышается производительность труда специалистов;
• сочетание возможности быстрого исследования альтернативных вариантов и автоматической оптимизации проектных решений позволяет получать конечные результаты более высокого качества;
• схемные проекты становятся менее зависимыми от технологии, используемых библиотек и т.д.;
• вследствие малой зависимости от элементной базы проекты допускают
повторное использование.
Проектирование любой БИС, состоит из следующих этапов:
• проектирование системного уровня (высокоуровневый синтез);
• проектирование логического уровня (логический синтез);
• проектирование физического уровня (физический синтез); Проектирование логического уровня состоит из следующих этапов:
• Синтез дискретных автоматов с памятью.
• Комбинационный ЛС.
В свою очередь, процесс ЛС, условно, можно разделить на следующие этапы [9]:
• технологически независимый - (инвариантный к технологии) - этап логической оптимизации;
• технологически зависимый (technology mapping) этап, являющийся отображением проекта на конкретную элементную базу.
К критериям оптимизации в задачах ЛС можно отнести:
• минимизация задержки схемы. Для решения этой задачи используются различные модели задержек, в том числе модели задержки устройства [1], [2], [3], [4], номинальной [5], [6] и некоторых других [7], [8], [12];
• минимизация площади кристалла, необходимой для реализации логической сети [12], [115], [117];
• оптимизация трассировки [38], [132];
• некоторая комбинация этих критериев в зависимости от целевой функции проектирования [12], [115], [117].
Как правило, задача синтеза минимальных логических схем математически формулируется как задача многокритериальной оптимизации. Эти задачи имеют значительную вычислительную сложность и при решении образуют Парето-оптималъное множество [116]. Это предопределяет большой интерес к автоматизации ЛС.
Алгоритмы логического синтеза, как правило, используют два типа информации - структурную и функциональную [10]. Структурная информация дает необходимые данные о связях. Как правило, структурная информация о схеме представляется в виде ацикличного ориентированного графа (DAG - direct acyclic graph), узлами которого являются логические узлы и/или первичные входы/выходы, а ребрами - связи между соответствующими узлами и входам и -выходами. Для представления функциональной информации каждый узел сети
рассматривается как БФ. Если вопросы размещения и трассировки не важны, то
функциональное представление может являться более предпочтительным, так как:
- более эффективно представимо в памяти;
- лучше отражает сложность конечной реализации;
- более удобно для дальнейших манипуляций.
Для технологически независимых этапов представляется целесообразным выделить три типа узлов [9]:
- общий: каждый узел - произвольная логическая функция;
- характерный: все узлы сети одинаковы;
- дискретный: каждый узел сети является одной из простейших логических функций (NAND, AND, OR, NOT, ADD и т.д.). Обычно, дискретный тип используется в системах ЛС, основанных на системах продукций (Jfhen-Else).
Системы автоматизированного ЛС обычно используют следующие формы представления БФ:
1. Таблица истинности.
2. ДНФ.
3. Факторизированная форма представления (F = ас + ad + be + bd + є может быть представлена как F = (a+b)(c+d) + е). [117], [118].
4. Покрытие куба.
5. Дерево двоичных диаграмм (или диаграммы двоичных решений - Binary Decision Diagram - (BDD), предложенное Акерсом [11]). BDD представляет собой некоторое обобщение DAG, используемое для представления логических функций. Брайантом было показано [13], что время выполнения большинства логических операций над BDD есть линейная или логарифмическая функция от числа узлов в BDD.
6. Представление функции через систему продукций (Ifhen-Else), предложенное в [16], является другим обобщением представления DAG.
7. Несколько особняком стоит обобщение BDD для метода транедукции на многозначные диаграммы решения [14], [15].
Применение спектров Уолша в логическом синтезе
Множество функций Уолша обычно подразделяется на три группы, отличающиеся порядком расположения отдельных функций в системе. Общеприняты следующие упорядочения: упорядочение по частости (частость -дискретный аналог понятия частоты) (по Уолшу); диадическое упорядочивание (по Пэли); естественное упорядочивание (по Адам ару). Иногда проводят аналогию между дискретным преобразованием Уолша, упорядоченным по Пэли с помощью кода Грея, и непрерывным преобразованием Фурье (гармоники в точности огибают кусочно-постоянную функцию) [137], что и проиллюстрировано на Рис.1-1. Отметим, что функции sal(x,t) и cal(x,t) — дискретные аналоги синуса и косинуса, соответственно, a wal(0,t) - функция Уолша с нулевым индексом.
ЭТОТ изоморфизм между группой функций Уолша и линейными БФ позволяет решать некоторые задачи, связанные с линеаризацией БФ и линейными БФ на языке функций Уолша и, наоборот. Разложение по функциям Уолша можно рассматривать как разложение по линейным БФ. Эти результаты будут использоваться в дальнейшем для введения процедуры линейной декомпозиции.
В работе [147J автор обобщил операции над спектрами путем использования различных схем кодирования БФ (заменой 0 и 1 в области значения на некие целые ао и Li). Точный выбор схемы кодирования зависит, главным образом, от результирующего выражения и необходимого базиса. Так, очевидно, что реализация "И-ИЛИ" будет простейшей, если или ал, или aj будут равны 0, в то время как реализация метода, интенсивно использующего сложение по модулю 2, наиболее эффективна, если арифметическая сумма ао и aj равна нулю.
Введем некоторые обозначения: і = f(xb...,xn). Функция f, перекодированная по схеме ао, щ - F. Обозначим через f дополнение функции f(xi,...,xn), с кодовыми представлениями Г и F\ соответственно.
Эти результаты были использованы в Главе 6 для более простых способов вычисления спектров сложных функций при реализации алгоритмов, а также в подзадачах задачи синтеза. Рассмотрим алгоритм построения спектра по Уолшу и оценим сложность этого алгоритма. Этот алгоритм аналогичен быстрым дискретным мультипликативным преобразованиям, использующим в качестве базиса тригонометрические функции (БПФ). Вопросы обобщения дискретных мультипликативных преобразований над конечными полями достаточно подробно рассмотрены в [138].
Вопросы аппаратной реализации дискретных мультипликативных преобразований постоянно находятся в центре внимания специалистов из-за своей широкой применимости в различных областях науки и техники. Классический подход к решению задачи достаточно подробно рассмотрен в [137], а более современные методы, основанные на теории систолических и волновых процессоров, рассмотрены в монографии [84]. Применение их отражено в сборнике статей [141].
Из теоремы (1-9) следует инвариантность корреляционных характеристик к сдвигу аргумента оригинала. Справедливо и обратное утверждение, что по автокорреляционной функции исходная функция может быть восстановлена с точностью до сдвига аргумента.
Для БФ сдвиг аргумента на а эквивалентен инвертированию тех аргументов, которым соответствуют ненулевые компоненты двоичного разложения числа а. Поэтому сложность схемы, реализующей БФ в любом базисе, полностью определяется ее автокорреляционной функцией B2(f,f) (т) с точностью до m элементов инверсии, где m - число аргументов БФ. Это дает возможность решать все задачи, связанные с минимизацией сложности схем, реализующих системы БФ, на языке корреляционных характеристик, что и делается работе (см. Гл, 4 п.п. 4.2).
Вычислительный аспект сложности дискретных задач
Рассматривая различные аспекты сложности задач, можно выделить следующие основные типы сложности: 1. Субъективная сложность (сложность восприятия конкретным индивидуумом). 2. Сложность алгоритмическая (по Колмогорову); сложность описания объекта; длина алгоритма. Самый сложный объект - таблица случайных чисел, так как ее описание равнозначно ей самой. 3. Вычислительная сложность - сложность с позиции поиска; число и глубина тупиковых ветвей дерева поиска.
Полиномиальным алгоритмом (алгоритмом полиномиальной временной сложности) называется алгоритм, временная сложность которого оценивается сверху как 0(р(п)), где р(п) - некоторая полиномиальная функция, an- число аргументов алгоритма. Алгоритмы, временная сложность которых не поддается подобной оценке, называются "экспоненциальными". Задача называется труднорешаемой, если для ее решения неизвестен полиномиальный алгоритм. Индивидуальной называется задача, получающаяся подстановкой в нее конкретных числовых значений. В Таблице 2-1 ([151]) приведено сравнение нескольких полиномиальных и экспоненциальных функций временной сложности, где по вертикали отображен тип алгоритма (полиномиальный или экспоненциальный), а по горизонтали размерность задачи (по количеству переменных). В Таблице 2-2 ([151]) отражено влияние технического совершенствования ЭВМ на полиномиальные и экспоненциальные алгоритмы. По вертикали отображен тип алгоритма (полиномиальный или экспоненциальный), а по горизонтали - размерность задачи которую можно решить на современных ЭВМ за единицу времени, а также на гипотетических ЭВМ, работающих, соответственно, в 100 и 1000 раз быстрее.
Как видно из Табл. 2-2, для увеличения скорости решения полиномиальных задач рационально строить специальные процессоры-акселераторы, а для экспоненциальных алгоритмов принципиально (на современном уровне развития науки) не может существовать общих, годных на все случаи жизни, способов решения. Понятно, что полиномиальные алгоритмы с высокими показателями также практически не разрешимы, но как показывает опыт [51], сложность таких алгоритмов почти всегда можно уменьшить до показателя степени, не превосходящего 2-4. Назовем задачей распознавания задачу, имеющую два возможных решения "да" и "нет". К задаче распознавания сводится и любая задача оптимизации. Для того, чтобы формализовать понятие "алгоритм", необходимо зафиксировать модель вычислений. Введем несколько определений: ДМТ - детерминированная машина Тьюринга, определяемая своим алфавитом - множеством символов, множеством начальных и конечных состояний и функцией перехода, НДМТ - недетерминированная машина Тьюринга (машина Тьюринга с оракулом); работает в двух режимах: угадывание (оракул) и проверка (ДМТ). Р класс - класс задач, разрешимых на ДМТ за полиномиальное время. NP класс - класс переборных задач; класс задач, которые могут быть решены недетерминированными алгоритмами за полиномиальное время (полиномиально проверяемые алгоритмы). Этот понятие впервые ввел Карп в статье [154]. Так, индивидуальная задача о коммивояжере может быть проверена за полиномиальное время.
Соотношение Р NP является одним из наиболее животрепещущих соотношений не только теории сложности, но и математики в целом. Если удастся доказать, что P=NP, то таким образом удастся свести методы решения не полиномиальных задач к методам решения полиномиальных. Правда, существуют обоснованные предположения [155], что это невозможно. PeNP, так как любой детерминированный алгоритм можно использовать для проверки соответствующего недетерминированного алгоритма. В другую сторону : если ПеР и А - произвольный детерминированный полиномиальный алгоритм решения П, то полиномиальный недетерминированный алгоритм для П получается, если воспользоваться А в качестве стадии проверки и игнорировать стадию угадывания. Т.о., если ПєР = IleNP. Полиномиальные недетерминированные алгоритмы оказываются более мощными, чем детерминированные, и неизвестны общие методы сведения их к детерминированным. Самый сильный из известных в настоящее время результатов заключается в следующем: если Пє NP, то существует такой полином р, что П может быть решена детерминированным алгоритмом с временной сложностью 0(2Р П)). Задача может быть решена за полиномиальное время параллельной машиной с неограниченным количеством аппаратуры, когда она может быть решена последовательной машиной в полиномиальном пространстве с неограниченным временем (что можно проиллюстрировать на примере множества Парето). Задача Пі сводится (к) к задаче П2, если метод решения задачи П2 можно преобразовать в метод решения задачи П}. Если это происходит за полиномиальное время, то задачи называются полиномиально сводимыми. Задача П называется NP - полной, если: 1) ПеЫР 2) Любая другая задача nieNP сводится к П, или какая-то известная NP -полная задача П осП, причем делает это за полиномиальное время. Отправной точкой теории сложности является фундаментальная теорема Кука [156], доказывающая существование, по крайней мере, одной NP-полной задачи. Процесс доказательства NP полноты задачи П состоит из: 1. Доказательства, что П є NP. 2. Выбора известной задачи ITeNP - полной 3. Построение функционального преобразования f, сводящей П к П 4. Доказательство, что f осуществляет полиномиальное сведение.
Можно показать [153], что "полиномиальность" задач является отношением эквивалентности, а полиномиальная сводимость определяет частичное упорядочивание возникающих классов эквивалентных задач. При этом класс Р полиномиальных задач - "наименьший" относительно этого частичного порядка класс эквивалентности и с вычислительной точки зрения его можно рассматривать как класс "самых легких" задач. Класс NP-полных задач дает другой класс эквивалентности, который характеризуется тем, что содержит "самые трудные" задачи из NP.
Особенности задачи синтеза для ППВМ
Как следует из п.4.1 проблема синтеза в базисе ППВМ состоит в минимизации числа используемых логических блоков и уменьшении сложности трассировки.
Для иллюстрации особенностей задачи ЛС в базисе ППВМ рассмотрим пример. Пусть число входов - m=5, f]= abcdeg и fj— abc+bde+ae+cd. Функции ї\ и f2 в своей реализации имеют 6 и 10 литералов соответственно.
Функция fj требует для своей оптимальной реализации 2 CLB, в то время как І2 требует только одного (так как f2 - функция 5 переменных).
Используя общепринятые соглашения, опишем более подробно математические задачи, возникающие при синтезе в базисе ППВМ, а также возможные и предлагаемые способы их решения. Следуя описанным особенностям элементной базы, автором используются методы, базирующиеся на четырех основных математических задачах: 1. Декомпозиции. 2. Разделения. 3. Покрытия. 4. Слияния. Введем первоначально несколько определений: Опр.1: выражение представляет собой свободный куб, если не существует другого куба, делящегося на это выражение точно: т.е. ab+c - является свободным кубом, а аЪ+ас - нет. Опр.2: основной делитель выражения f - множество выражений вида D(f) = {f/C IС -свободный куб} Опр.З: ядром выражения f является множество выражений вида K(f) = {gig є D(f) и g - свободный куб} Опр.4: остаток, связанный с ядром К функции есть выражение для f с новой переменной, замененной для всех вхождений К в f. Опр.5: основа функции f, обозначающейся как sup (f), есть множество переменных, от которых она зависит. sup (f) находит обратную функцию. Опр.б: функция называется выполнимой если sup (f)l m, т.е. выполнимая функция м.б. реализована на одном CLB. Опр.7: булева сеть реализуема, если каждый промежуточный узел реализует выполнимую функцию.
Число промежуточных узлов реализуемой булевой сети дает верхнюю границу числа CLB, необходимых для ее реализации. Таким образом, достаточно очевидным выглядит вывод ([86]), что алгоритм синтеза может быть разбит на два больших этапа - построение реализуемой сети и минимизация числа узлов. Первый этап обычно подразумевает использование процедур декомпозиции и разделения, а второй - покрытия и слияния.
Под декомпозицией в данном случае подразумевается процедура, преобразующая невыполнимые функции в выполнимые.
Операция разделения (Partitioning), похожая на процедуру декомпозиции, гарантирует нам, что функция f, связанная с узлом і, - реализуема. Т.е. различие между этими двумя операциями состоит в том, что декомпозиция - более мелкая иерархическая процедура, работающая на уровне узлов, в то время как разделение, кроме того, что осуществляет декомпозицию, пытается также уменьшить общее число узлов реализуемой сети и, соответственно, ресурсы межсоединений в окончательной реализации. Или, несколько видоизменив формулировку, можно сказать, что разделение кроме функциональной информации использует еще и структурную.
Третья математическая задача, задача покрытия, формулируется следующим образом. Дана реализуемая булева сеть. В каком порядке надо "отщеплять" от сети узлы таким образом, чтобы получившаяся сеть тоже была реализуема, и число узлов при этом было минимальным.
Эти проблемы достаточно общие для любой архитектуры (технологически независимые), и некоторые их аспекты с позиций спектральной обработки были рассмотрены в работах [130], [147]. Именно эти работы показали перспективность использования обработки спектров для решения задачи синтеза. Эти методы дают результаты, подобные результатам работы других методов при достаточно небольших наборах входных переменных, а за счет предложенных эвристик могут на больших входных наборах давать даже лучшие результаты. Необходимо только ввести ограничения, свойственные архитектуре ППВМ. Основными отличиями архитектуры ППВМ, влияющими на процесс синтеза, как уже отмечалось, являются ограничения на количество входов-выходов CLB, и отсутствие каких-либо ограничений на тип реализуемой функции. Эти задачи достаточно близки к такой очень актуальной, но, к сожалению, выходящей за рамки данной работы, темы, как синтез схемы в элементной базе по ее высокоуровнему описанию на языке VHDL (стандарт IEEE 1076-85). Можно лишь с сожалением повторить, что современные западные промышленные системы, реализующие такой синтез, из-за своей очень высокой стоимости практически недоступны современному массовому российскому пользователю.
Реализация методики генерации функций
Ввиду того, что при реально интересующих пользователя размерностях объем вычислений в представленных алгоритмах достаточно велик, введена процедура вывода на экран состояния процесса. В нее передаются наименование выполняемого действия (построение автокорреляционной функции, минимизация функции по Блейку-Порецкому и т.д.) и выраженное в процентах состояние процесса вычисления. Также осуществляется вывод контрольных показаний всей системы в целом на данный момент: времени с начала запуска программы; размера свободной, для динамического выделения, оперативной памяти. FUN.H - файл описания внешних функций и переменных для модуля FUN.CPP. Для реализации подсистемы, отвечающей за генерирование функций, соответствующих закону Рента, используется следующий набор программ. Программа SCHEMA.CPP осуществляет генерацию логических схем. Входными данными при этом являются имя входного файла, содержащего входные данные и имя выходного файла, в который будет записано описание схемы во внутреннем формате.
Программа может также генерировать одновременно и несколько схем, если вызвать ее с ключом /s после имен файлов и во входном файле задать не конкретные значения параметров, а их интервалы (сначала нижняя граница, затем верхняя, затем шаг). Параметры, которые можно задавать таким образом, отмечены звездочкой в описании формата входного файла, предназначенного для генерирования функций (см.п.6.2).
Программа F_CALC.CPP предназначена для расчета вектор-функции выходов схемы. Входными данными являются имя входного файла, содержащего описание схемы во внутреннем формате (выходной файл программы schema.exe), и имя выходного файла, которое будет использоваться как шаблон для образования имен файлов, содержащих вектор-функции выходов (в двоичном формате), например - out.txt - outl.txt, out2.txt и т.п.
Программа FORM.CPP преобразует двоичный файл вектор-функции в текстовый файл. Входные данные - имя двоичного файла, содержащего вектор-функцию, имя выходного текстового файла.
Программа TXT_ESPR.CPP создает описание схемы в формате ESPRESSO-MV Университета Беркли (Калифорния) - одного из форматов, использующегося в библиотечных наборах MCNC benchmarks сравнения алгоритмов логического синтеза и оптимизации для возможного будущего сравнения с их результатами. Входные данные - имя файла, содержащего описание схемы во внутреннем формате (выходной файл программы schema.exe), имя выходного файла с расширением .esp.
Программа TXT_PDF.CPP создает описание схемы в формате САПР электронных схем PCAD - pdf. Входные данные - имя файла, содержащего описание схемы во внутреннем формате (выходной файл программы schema.exe), имя выходного файла с расширением .pdf. Программа создает также файлы типа 0s.pdf, ls.pdf, содержащие описания элементов соответствующих типов. Для преобразования .pdf-файлов во внутренний формат PCAD необходимо: 1) Преобразовать все файлы описаний элементов: pdifin.exe Os.pdf Os.sym pdifin.exe ls.pdf ls.sym и т.д. 2) Преобразовать файл описания схемы : pdifin.exe file_in.pdf filein.sch Файл с расширением .sen можно посмотреть программой pccaps.exe, входящей в состав системы PCAD. SCHEMA.H - файл описания внешних функций и переменных для модуля SCHEMA. СРР. Общий объем программного кода составляет более 10000 операторов.
В качестве объекта для эксперимента программой SCHEMA.CPP произвольно генерировались функции с ключом /s и проверялись на соответствие закону Рента. Всего было сгенерировано 2К функций, которые и исследовались в дальнейшем. Из-за отсутствия обобщенных критериев применения методов линейной декомпозиции и недостаточной изученности предложенного генератора тестовых функций не все из полученных функций хорошо поддавались процедуре линейной декомпозиции. Общие результаты достаточно хорошо согласуются со статистическими свойствами БФ и местом линейных функций во всем множестве функций алгебры логики. В среднем, по всей выборке, результат был скорее даже отрицательным (было ухудшение, как по термам, так и по литералам), что, в принципе, может служить некоторым доказательством репрезентативности выборки.
