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

Список используемых сокращений.

I. Введение.

Глава 1. Применение спектров Уолша в логическом синтезе.

Глава 2. Анализ сложности булевых функций.

2.1. Вычислительная сложность задач и методы ее уменьшения.

2.1.1 Вычислительный аспект сложности дискретных задач.

2.1.2 Методы решения труднорешаемых задач.

2.2. Сложность булевых функций. Критерии сложности.

2.3. Анализ БФ с использованием спектров.

Глава 3. Линеаризация функций.

Глава 4. Логический синтез для программируемых пользователем вентильных матриц (ППВМ).

4.1. Архитектура ППВМ.

4.2. Особенности задачи синтеза для ППВМ.

Глава 5. Генерация и визуализация функций.

5.1 Методика генерации функций.

5.2 Методика визуализации функций.

Глава 6. Экспериментальная часть.

6.1 Основные проблемы и пути их решения.

6.2 Реализация методики генерации функций.

6.3 Структура программы и особенности ее реализации.

6.4 Проверка правильности положений о визуализации функций.

6.5 Примеры практического применения.

Научно-технический прогресс в области создания новых типов ЭВА в значительной мере зависит от успешного решения проблемы автоматизированного проектирования. Автоматизированное проектирование позволяет не только сократить время разработки продукта, но и сроки его выхода на рынок. В условиях формирующегося рынка это часто является фактором, определяющим успех. Кроме того, автоматизация позволяет уменьшить стоимость проектирования и увеличить качество, уменьшить количество ошибок на каждом из этапов проектирования. Увеличение степени интеграции приводит к существенному росту функциональной сложности объектов проектирования. А из того факта, что время, затрачиваемое на этап конструирования составляет 80% общего времени разработки СБИС [114], следует, что одним из наиболее актуальных являются вопрос автоматизации проектирования.

Значительный вклад в развитие теории и практики автоматизации проектирования (в частности синтеза схем) внесли В.М. Глушков, Л.Б. Абрайтис, В.М. Курейчик, Д.А. Поспелов, В.А. Горбатов, И.П. Норенков, О.Б Лупанов, Р.Г. Нигматуллин, C.B. Яблонский, М.Г. Карповский, Л.А. Шоломов, Е.А. Бутаков, А.Я. Тетельбаум, Э.И. Нечипорук, А.Д. Закревский, В.И. Варшавский и многие другие. Из западных ученых необходимо отметить фамилии 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 и другие.

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

• повышается производительность труда специалистов;

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

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

• вследствие малой зависимости от элементной базы проекты допускают повторное использование.

Проектирование любой БИС, состоит из следующих этапов:

• проектирование системного уровня (высокоуровневый синтез);

• проектирование логического уровня (логический синтез);

• проектирование физического уровня (физический синтез);

Проектирование логического уровня состоит из следующих этапов:

• Синтез дискретных автоматов с памятью.

• Комбинационный JIC.

В свою очередь, процесс JIC, условно, можно разделить на следующие этапы [9]:

• технологически независимый - (инвариантный к технологии) - этап логической оптимизации;

• технологически зависимый (technology mapping) этап, являющийся отображением проекта на конкретную элементную базу.

К критериям оптимизации в задачах JIC можно отнести:

• минимизация задержки схемы. Для решения этой задачи используются различные модели задержек, в том числе модели задержки устройства [1], [2], [3], [4], номинальной [5], [6] и некоторых других [7], [8], [12];

• минимизация площади кристалла, необходимой для реализации логической сети [12], [115], [117];

• оптимизация трассировки [38], [132];

• некоторая комбинация этих критериев в зависимости от целевой функции проектирования [12], [115], [117].

Как правило, задача синтеза минимальных логических схем математически формулируется как задача многокритериальной оптимизации. Эти задачи имеют значительную вычислительную сложность и при решении образуют Парето-оптимальное множество [116]. Это предопределяет большой интерес к автоматизации J1C.

Алгоритмы логического синтеза, как правило, используют два типа информации - структурную и функциональную [10]. Структурная информация дает необходимые данные о связях. Как правило, структурная информация о схеме представляется в виде ацикличного ориентированного графа (DAG - direct acyclic graph), узлами которого являются логические узлы и/или первичные входы/выходы, а ребрами - связи между соответствующими узлами и входами-выходами.

Для представления функциональной информации каждый узел сети рассматривается как БФ. Если вопросы размещения и трассировки не важны, то функциональное представление может являться более предпочтительным, так как:

- более эффективно представимо в памяти;

- лучше отражает сложность конечной реализации;

- более удобно для дальнейших манипуляций.

Для технологически независимых этапов представляется целесообразным выделить три типа узлов [9]:

- общий: каждый узел - произвольная логическая функция;

- характерный: все узлы сети одинаковы;

- дискретный: каждый узел сети является одной из простейших логических функций (NAND, AND, OR, NOT, ADD и т.д.). Обычно, дискретный тип используется в системах JIC, основанных на системах продукций (If-Then-Else).

Системы автоматизированного JIC обычно используют следующие формы представления БФ:

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. Представление функции через систему продукций (If-Then-Else), предложенное в [16], является другим обобщением представления DAG.

7. Несколько особняком стоит обобщение BDD для метода транедукции на многозначные диаграммы решения [14], [15].

На Рис.1 изображены некоторые виды представления функции: а) -двумерная таблица истинности; б) СДНФ; в) покрытие куба; г) два BDD с различным порядком следования переменных; д) представление через систему продукций (If-Then-Else). yz WX 00 01 10 11

00 1 1 1 0

01 1 0 0 1

10 1 0 0 1

11 1 0 0 1 a) f = wxyz v wxyz v wxyz v wxyz v wxyz v wxyz V wxyz v wxyz V wxyz

6) о 3 то сг W У X л < W О

X W

А ►

Z Z

А-* ▼ О f = wxy V wxz v wyz v xyz v yz

B)

Д)

Рис. 1 Виды представления БФ

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

Если представленные цифровые схемы не эквивалентны, необходимо показать, где именно они различаются. Для этого наиболее широкое распространение получили следующие методы [122].

Первый метод - представление каноническим деревом (Canonical Tree Representation - CTR, впоследствии обобщенное до BDD). В работе [119] был описан метод представления произвольной булевой функции в канонической форме в виде дерева и доказано, что две схемы функционально эквивалентны тогда и только тогда, когда канонические деревья этих двух функций изоморфны.

Второй метод - булево сравнение моделированием (BCS). В [120] была использована абстрактная форма моделирования для сравнения двух схем напрямую. Суть метода заключается в моделировании с использованием трехзначной логики везде, где функция принимает значение равное 1. Если значение функции действительно равно единице, то функции эквивалентны на всех точках покрытия текущего входа; если нулю, то функции неэквивалентны; если значение не определено, то требуется дополнительная проверка. ▼

Третий метод - дифференциальный анализ БФ (DBA). В [121] описан метод DBA для тестирования алгебраических формул. Метод использует обычное деление и идеологию "разделяй и властвуй". Для каждого выхода схемы генерируется своя булева формула. Процесс DBA начинается прямым сравнением исходных формул. Если они идентичны - проблема решена. Если нет, то каждая формула редуцируется подстановкой нулей и единиц и последующим упрощением. Оригинальная пара формул эквивалентна тогда и только тогда, когда обе части приведенных формул эквивалентны.

Очень важным аспектом JIC является тот, что большинство алгоритмов JIC являются исключительно сложными в вычислительном плане. Задача синтеза минимальной схемы заключается в построении для произвольной функции f(xj.xn) минимальной схемы, ее реализующей [157]. Поскольку, каждая функция имеет конечную сложность, эта задача допускает тривиальное решение: достаточно перебирать схемы в порядке возрастания сложности, пока не встретится схема, реализующая функцию f, которая, очевидно, и будет являться решением. Однако, уже при незначительном числе аргументов (не больше восьми), найти решение практически не представляется возможным. Это обстоятельство, являющееся чрезвычайно характерным для дискретных экстремальных задач, показывает, что понятие алгоритма неадекватно понятию реальной вычислимости. Поэтому автором были рассмотрены некоторые общие вопросы теории вычислительной сложности алгоритмов в их применении для JIC.

Если для увеличения скорости решения полиномиальных задач рационально строить специальные процессоры-акселераторы, то для экспоненциальных алгоритмов принципиально (на современном уровне развития науки) не может существовать общих, годных на все случаи жизни, способов решения. Понятно, что полиномиальные алгоритмы с высокими показателями также практически не разрешимы, но как показывает опыт [51], сложность таких алгоритмов почти всегда можно уменьшить до показателя степени, не превосходящего 2-4.

Методы, базирующиеся на манипуляциях с БФ, могут иметь очень высокую вычислительную сложность, но, в принципе, позволяют достичь оптимального результата. Однако, для реально используемых функций применять точные булевы методы практически невозможно. С другой стороны, приближенные (алгебраические) методы могут давать хорошие результаты значительно быстрее. Одна из проблем J1C заключается в выявлении, на каком из этапов синтеза и как рационально использовать каждый из методов, ориентируясь на требования к качеству решения и времени его получения. Большинство работающих на сегодня систем используют следующие парадигмы JIC (для используемых в формулах алгебраических выражений) [17, 18, 19, 129]:

• минимизация каждой логической функции, входящей в алгебраическое выражение;

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

• оптимизация двух предыдущих шагов.

В числе основных методов, использующихся на алгебраических этапах, необходимо отметить следующие:

1. Метод алгебраического деления (Weak Division) [20], [21]. Идея метода состоит в том, что для двух и более исходных логических функций выбираются общие и пересекающиеся подвыражения, которые могут быть использованы в качестве промежуточных термов. Цель процесса - исключить повторение одних и тех же схемных компонентов.

Даны два выражения /и р. Для них: генерируется q и г, такие, что pq образуют алгебраическое выражение; г (остаток) - минимальное выражение (покрывает минимальное количество кубов); pq v г и / - эквивалентны (или имеют одинаковый набор покрывающих кубов).

В результате работы этого алгоритма экономится площадь кристалла, правда, за счет уменьшения быстродействия. В работе [22] описана модификация этого алгоритма, использующаяся как часть программного обеспечения логического синтеза фирмы LSI. Глобальная оптимизация осуществляется путем моделирования стохастического отжига. Приведенные авторами результаты оптимизации показывают, что моделирование отжига дает выигрыш в скорости на 30% и выигрыш по площади в 20% по сравнению со стандартным методом слабого деления.

2. Метод вычисления общего и пересекающихся ядер алгебраических выражений, базирующийся на фундаментальной теореме о том, что если ядра двух выражений имеют общим только один терм, то эти выражения не имеют общего простого делителя [20, 23].

3. Методы различного рода подстановок, факторизаций и т.д. [20, 24, 25, 27, 18, 28, 29]. В работе [26] на основе анализа некоторых из этих методов приводится гипотеза о том, что синтез может основываться на формальных преобразованиях системы базовых логических функций в соответствии с некоторым набором правил (для данного конкретного класса синтезируемых логических схем). Результатом синтеза является список межсоединений совокупности базовых логических элементов. Метод гарантирует корректность проектирования метафункций. Сформулирован набор правил вывода метафункций для арифметических устройств. К сожалению, вопрос о построении правил вывода для логических устройств общего характера остается открытым. Кроме того, к работам, основанным на эквивалентных преобразованиях, можно отнести и работы отечественных авторов [123, 124, 125].

4. Методы, основанные на спектральных преобразованиях. Эта группа методов более подробно рассматривается в Главах 3 и 4 предлагаемой работе. В Главе 3 приведен и список литературы.

Серьезным вопросом JIC является логическая минимизация и оптимизация при наличии влияния неважных (don't care) входных комбинаций (частично определенные БФ - ЧОБФ). В предлагаемой работе данный вопрос практически не рассматривался. Автор ограничился лишь кратким перечислением существующих методов, так как J1C для ЧОБФ является очень большим самостоятельным исследованием, выходящим за рамки данной работы. В работах [30, 31, 32, 33, 34, 112, 113] рассматриваются вопросы доопределения ЧОБФ для улучшения их минимизируемости и получения более оптимального решения.

Большинство современных алгоритмов используют в JIC минимизацию числа узлов. Одним из возможных подходов является подход, базирующийся на тавтологии [16, 35, 36, 37]. Другим возможным подходом является использование дифференциального булевого анализа (DBA) [121]. Еще один метод [39] основывается на доопределении ЧОБФ по определенным правилам. Другая идея -некая фильтрация "неважных" значений, основанная на топологии многоуровневой схемы и преобразования из матричной формы в кубическую (cube - matrix form) [40]. Кроме этого можно выделить следующие методы:

1. Трансдукции (трансформация + редукция) [41, 42, 14], основанном на:

- устранении избыточности схемы;

- добавлении и удалении связей;

- установке связи между подстановками;

- подстановке в вентили;

- объединении вентилей;

2. Глобального потока, где алгоритм пытается минимизировать коэффициент разветвления по выходу (fan-out) в выбранном вентиле, используя более глобальный взгляд на полученный граф [43, 30, 44, 45].

3. Группа алгоритмов, базирующаяся на основе инвариантности узлов [46, 18, 47].

4. Группа алгоритмов, основывающаяся на иерархии сетей узлов [48, 49, 50].

В данной работе автор исходит из гипотезы, что переход от дискретных (логических) операций к непрерывным (арифметическим) может привести к достижению хороших результатов. Причинами являются как большая историческая проработанность непрерывных задач, по сравнению с дискретными, так и психологическая особенность человека выявлять весьма сложные зависимости именно в непрерывных категориях. Эту гипотезу можно проиллюстрировать на примере апорий Зенона, или на примерах алгоритмов многокритериальной оптимизации, таких как градиентный и стохастического отжига. В каждом из этих алгоритмов используется попытка уйти от ограничений, связанных с переборностью оптимизационных задач. Отметим, что каждый из этих алгоритмов является приближенным, т.е. не гарантирует получения абсолютно лучшего результата. С другой стороны было доказано [164], что, например, для задач на покрытие дизъюнктивных нормальных форм градиентный алгоритм дает результат, в худшем случае отличающийся от оптимального в (1+п1п2) раза, хотя в абсолютном большинстве случаев это различие еще меньше и не превосходит loglogn.

В качестве элементной базы автор выбрал ППВМ (Field Programmable Gâte Array - FPGA) - программируемые пользователем вентильные матрицы. Обоснованием актуальности этого выбора послужили следующие соображения. Эта элементная база была впервые предложена в 1985 году американской фирмой "Xilinx". Это событие произвело существенные изменения в методологии проектирования вычислительных систем и по своему значению приравнивается специалистами к появлению микропроцессоров (МП). По исследованиям фирмы Dataquest Inc, специализирующейся на изучении рынков, ППВМ является наиболее динамично развивающимся сегментом рынка цифровых ИС в 90-х годах, обгоняя в этом отношении даже МП [127].

Со времени своего введения только фирмой Xilinx было продано более 10 миллионов корпусов ППВМ, использующихся в более чем в 5500 промышленно производимых системах. Число приложений и, соответственно, число используемых микросхем постоянно растет, и фирма является одним из законодателей мод, контролируя более 60% [126] этого сегмента рынка.

FPGA является одним из последних изобретений в области ИС, сочетающее в себе преимущества стандартного продукта с высокой степенью логической интеграции, гибкости и характеристик заказных СБИС (ASIC) и вентильных матриц (gate array) с удобством проектирования, свойственным устройствам, программируемым пользователем. Технологической основой ППВМ является статическая память (SRAM), которая может программироваться для реализации широкого набора логических элементов и межсоединений. Так как содержимое SRAM может быть изменено, то базирующиеся на технологии статической памяти ППВМ могут быть перепрограммируемы пользователем. Наиболее общий подход к построению базового логического элемента для такого рода ППВМ заключается в использовании 2к-битной ячейки памяти, которая реализует любую А'-входовую одновыходную функцию БФ, путем загрузки в ячейку статической памяти таблицы истинности этой функции. Этот тип архитектуры получил название Table Look-Up (TLU) или Look-Up Table (LUT). Такие продукты предлагают на рынок многие поставщики, например Altera [53], AT&T [54], Xilinx [52] и другие. Общие вопросы архитектуры ППВМ рассмотрены в [181, 182, 183].

В данной работе мы, без ограничения общности, будем использовать главным образом архитектуру LCA (Logic Cell Array) типа Table Look-Up (TLU) фирмы Xilinx, базовым логическим элементом которой является конфигурируемый логический блок - Configurable Logic Block - CLB. Логические функции и межсоединения определяются конфигурационной программой, хранимой во внутренних ячейках статической памяти кристалла.

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

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

1. Декомпозиции.

2. Разделения.

3. Покрытия.

4. Слияния.

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

Операция разделения (Partitioning), похожая на процедуру декомпозиции, гарантирует нам, что функция f, связанная с узлом i, - реализуема. Т.е. различие между этими двумя операциями состоит в том, что декомпозиция - более мелкая иерархическая процедура, работающая на уровне узлов, в то время как разделение, кроме того, что осуществляет декомпозицию, пытается также уменьшить общее число узлов реализуемой сети и, соответственно, ресурсы межсоединений в окончательной реализации. Или, несколько видоизменив формулировку, можно сказать, что разделение кроме функциональной информации использует еще и структурную.

Третья математическая задача, задача покрытия (Covering), формулируется следующим образом. Дана реализуемая булева сеть. В каком порядке надо "отщеплять" от сети узлы таким образом, чтобы получившаяся сеть тоже была реализуема, а число узлов при этом было минимальным.

Четвертая проблема - проблема слияния (Merging) - является особенностью архитектуры ППВМ. Так, любой базовый блок может реализовывать любую функцию пяти переменных. Но вместо этого он может реализовывать и две функции f и g, если они удовлетворяют следующим трем условиям:

- каждая из них имеет самое большое четыре входа;

- число их общих входов не превосходит трех;

- суммарное число их входов не больше пяти.

Задача слияния как раз и состоит в поиске пар функций, отвечающих этим требованиям.

В большинстве случаев задачу JIC для ППВМ формулируют следующим образом: дана многоярусная сеть произвольных узлов. Ее необходимо трансформировать в сеть, каждый узел которой подходит для реализации TLU (т.е. имеет к входов и один выход). Автор использует предложенную в [10] классификацию типов декомпозиций узлов:

• Структурная декомпозиция, основывающаяся на структурной информации о реализуемой схеме. Для простых функций (И, ИЛИ, © и их отрицаний) выполняются коммутативные и ассоциативные законы, которые позволяют произвольно группировать входы при декомпозиции. В результате, знание специфической информации о функции не требуется, и декомпозиция становится чисто комбинаторной операцией. В этом случае декомпозиция превращает такую простую функцию в дерево с входным размером каждого узла не превышающим размера ТШ. К таким методам относятся различные алгоритмы декомпозиции деревьев [55-57, 30] и ряд других [58-60].

• Символическая декомпозиция, основывающаяся на символических преобразованиях над заданной формой функционального представления узлов. В случае, когда узел реализует сложную функцию, для его декомпозиции часто необходимо использовать его функциональное наполнение. Одним из относительно наиболее простых способов манипуляции над функциями являются манипуляции с их символическим представлением. К таким методам относятся, кроме перечисленных различных методов экстракции и факторизации, И-ИЛИ декомпозиция [55] и некоторые другие [61-69].

• Булева декомпозиция, основывающаяся на общих правилах функционирования узлов. При символической декомпозиции пространство решений ограничено данным представлением функции. Это уменьшает вычислительную сложность, но может ограничивать эффективность декомпозиции. Методы булевой декомпозиции выходят за пределы заданного представления функции, что с одной стороны может увеличить эффективность, а с другой - увеличивает вычислительную сложность метода. Часто употребляется метод, основанный на теореме Шеннона о декомпозиции при подстановке значений функции отдельно на нулевых и единичных наборах. Развитием этого метода стали методы функциональной декомпозиции для разного рода функций, такие как методы, использующие теоремы Ашенхерста и Кертиса о существовании простой и кратной декомпозиций функций [71], [72], метод линейной декомпозиции Карповского [73], метод ЛоШ-Кагр^ [74], методы на основе декомпозиции ЕЮО [75, 69, 7, 77], основанные на раскраске графа [76] и некоторые другие методы [70, 78-81].

Кроме того, можно отметить эвристические алгоритмы работы с графами (деревьями) (например, основанные на видимости узлов [82] или изоморфизме подграфов [83]), построение целевых (стоимостных) функций и поиск экстремума функционала этих функций. Для поиска глобальных экстремумов обычным является использование моделей стохастического отжига [22, 84, 88]. Проблема слияния в большинстве проанализированных работ либо вообще не рассматривалась, либо не выделялась в отдельную задачу и решалась на базовом уровне стандартными средствами.

Так как большинство работающих систем ЛС для технологического базиса ППВМ используют более чем один тип техники оптимизации, их сложно классифицировать по методам. Поэтому автор просто перечислит их, а подробности можно найти в соответствующих библиографических ссылках. Для желающих подробнее ознакомиться с существующими методами, можно порекомендовать обзоры [10], [184].

1. Группа алгоритмов Chortle, предложенная Francis [85] и его модификации Chortle-crf и Chortle-d ([59], [58]).

2. Группа алгоритмов MIS-pga, являющаяся расширением известной системы J1C MIS-II университета Беркли [62, 86, 87, 128, 89].

3. Алгоритмы семейства TechMap [90, 91].

4. Алгоритмы семейства FlowMap [1, 56, 60, 7, 92-97].

5. Алгоритмы MILP [98], Level-Map [99], VisMap [82], Factor-Map [100], Xmap [101], GAFPGA [102], BDD-Syn [69], Trade [76], FGMap [103], Edge-Map [8], и другие.

Вопросы сравнения функционирования предлагаемых алгоритмов с описываемыми в литературе исключительно сложны. Алгоритмы, разработанные западными учеными, как правило, основываются на базе промышленных или полупромышленных (университетских) систем типа MIS, Espresso, LSI и т.д., или являются надстройкой над ними [17, 18, 19, 104, 133]. Эти системы разрабатывались в течение десятков лет сотнями людей, и с ними очень трудно конкурировать. Именно эти системы берут на себя большую часть рутинной работы по подготовке исходных данных и их преобразованию: общий подсчет количества литералов, механистический подсчет сложности конкретных функций до и после преобразования, минимизация БФ и т.д. Как показывает опыт автора, максимальные затраты времени работы программы тратятся именно на это. Отечественный разработчик находится в совершенно иных условиях. Он либо вынужден писать всю систему целиком, либо ограничиться только описанием алгоритма, практически без его сравнения с западными аналогами. Трудоемкость создания системы JIC составляет десятки и сотни человеко-лет. Предлагаемый автором набор программ и так уже превысил значение в десять тысяч строк отлаженного программного кода, не реализуя некоторых функций, без которых система JIC работать не может. Большинство численных результатов работы получено не в виде итога работы некой системы, а в виде некоторого набора алгоритмов, переход между которыми осуществляется вручную: на одном этапе строится спектр БФ, на другом - функция автокорреляции, на третьем происходит синтез и т.д. Поэтому, невозможно говорить о скорости работы всего алгоритма в сравнении с результатами работы алгоритмов синтеза приводимыми в литературе.

Вследствие этого, если это отдельно не оговорено, предложенные в работе алгоритмы оцениваются по количеству использованных С1В блоков, или другим столь же объективным критериям, таким как уменьшение числа литералов, уменьшение сложности функции и т.д. С другой стороны, как уже отмечалось ранее, большинство подзадач задачи синтеза являются ^-полными, и любые алгоритмы, позволяющие за приемлемое время получать достаточно хорошие результаты, имеют право на существование. Поэтому еще долго будет сохраняться актуальность решения разного рода задач, связанных с применением в схемотехнике новых математических методов автоматического синтеза экономичных по затратам схем. Алгоритмы, реализующие математические задачи, характерные для ЛС в базисе ППВМ на основе линейной декомпозиции, были воплощены автором на языках С и С++ в виде комплекса программ. В реализации были предусмотрены различные форматы входных данных (СДНФ, троичная матрица и т.д.), что позволяет использовать различные промышленные системы на этапе ввода проекта.

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

• Не быть типовыми, широко распространенными и хорошо исследованными, в какой-то мере регулярными. В этом случае работают подходы Карцева, Брика, различные систолические архитектуры [105, 106, 107, 84]. Структуры такого рода реализуют, находя оптимальный для композиции (процедура, обратная декомпозиции) фрагмент схемы и затем этот фрагмент тиражируют в соответствии со структурой ( например регулярно).

• Если в базисе ПЛМ практически нецелесообразно реализовывать арифметические функции, т.е. не реализовывать функции, имеющие комбинацию входных аргументов типа "все со всеми" (определенные на всем пространстве решений п -> 2П), то с точки зрения особенностей архитектуры кристалла ничто, кроме, возможно, экономических предпосылок в недалеком прошлом, не мешает реализовывать арифметические функции на ППВМ. Но, с ростом экономических показателей производства ППВМ, таких как расширение номенклатуры изделий, увеличения объемов продаж и некоторых других, фирмы-производители пытаются заинтересовать сторонних разработчиков в еще большем увеличении использования данной архитектуры. Для этого в архитектуру кристалла вносятся некоторые особенности, направленные на улучшение реализации арифметических функций, такие как высокоскоростная реализация функции быстрого переноса, возможность организации арифметических конвейеров и некоторые другие. Кроме технических, существуют еще и различные организационные (маркетинговые) методы решения проблемы. К ним можно отнести внесение большого количества таких элементов в библиотеку готовых компонентов. Так, в библиотеке макросов для 4000 серии находятся двенадцать сумматоров/вычитателей, тридцать пять видов счетчиков и т.д. При добавлении некоторых функций пользователь незначительно теряет на цене кристалла, но значительно выигрывает на унификации и дешевизне проектирования.

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

Кроме других к таким функциям относятся довольно многочисленные классы функций управления, корректирования ошибок и т.д. К особенностям этих классов можно отнести то, что для каждого конкретного случая они разные, и это затрудняет проблему формализации их построения. Отсюда возникла задача генерации тестовых наборов функций. Использование случайных функций является не вполне адекватным, потому, что человек пользуется своей, вполне понятной ему и окружающим систематикой функций, охватывающей только то, что он в состоянии осознать. В результате, часть работы, посвященная методике генерации тестовых функций, превратилась в самостоятельный раздел. Автором предлагается новая методика генерации тестовых наборов функций для проверки работоспособности алгоритмов анализа и синтеза логических схем, основанная на соотношении Рента. Соотношение Рента определяет зависимость между числом внешних связей и числом логических элементов случайно выбранного участка схемы [108]. Это соотношение подтверждается экспериментами на протяжении длительного периода развития вычислительной техники. Полученная методика была реализована на языке С++ в комплексе программ Schema. В реализации были предусмотрены средства для конвертации полученной схемы в формат PCAD, что позволяет просматривать полученную схему средствами, более естественными для разработчика. Кроме того, были реализованы конвертеры в некоторые форматы MCNC benchmarks [109], используемые для сравнения алгоритмов ЛС и оптимизации.

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

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

Так как результаты требуют осмысления на понятийном уровне, то для более наглядного представления данных была использована технология визуализации, а для изучения данных - технология их анализа на базе методов прикладной статистики. Для осуществления визуализации результатов предложенного автором генератора функций была использована идеология и базовые средства системы научной визуализации DATA EXPLORER [110, 111].

Актуальность работы

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

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

Научная новизна работы заключается в следующем:

• предложены алгоритмы для каждого из этапов процедуры логического синтеза: - декомпозиции, разделения, покрытия и слияния, основанные на спектральном представлении булевых функций и ориентированные на применение для программируемых пользователем вентильных матриц;

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

• предлагается новая методология исследования функций, базирующаяся на методах визуализации и методах прикладной статистики.

Практическая ценность работы заключается в следующем:

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

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

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

Структура и объем работы.

Предлагаемая работа состоит из введения, шести глав, выводов по каждому разделу, заключения, списка литературы из 191 наименований и двух приложений. Общий объем основного текста составил 110 машинописных страниц, включая 30 рисунков и 13 таблиц.

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

В I главе описываются функции Уолша, вводятся понятия спектра функции по Уолшу и автокорреляционных функций, их свойства и интерпретация. Кроме того, вводятся операции над спектрами и систематика БФ, основанная на этих операциях, алгоритмы вычисления спектров и автокорреляционных характеристик функций. Приводится доказательство изоморфизма между функциями Уолша и линейными функциями, что позволяет решить часть вопросов, связанных с линеаризацией БФ на языке функций Уолша.

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

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

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

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

В VI главе (экспериментальной части) описываются и анализируются численные результаты работы предложенных и исследованных автором алгоритмов.

В заключении формулируются основные результаты, полученные автором.

В Приложении 1 приведены примеры некоторых программ.

В Приложении 2 приведены акты внедрения.

Апробация работы.

По тематике работы сделаны доклады на конференциях и форумах Международной Академии Информатизации и опубликованы тезисы докладов:

1. Потемкин И.С., Евсиков И.А. "Оценки сложности некоторых алгоритмов логического синтеза."// "Информационные средства и технологии" МФИ-93, тез. докл. -М., МЭИ(ТУ), стр.64-65

2. Потемкин И.С., Евсиков И.А. "Использование декомпозиции в спектральных методах логического синтеза" // "Информационные средства и технологии" МФИ-94, тез. докл. —М., МЭИ(ТУ), стр. 46-47

3. Балашев К.В., Евсиков И.А. "Использование параллельной декомпозиции, реализованной на систолических структурах в спектральных методах логического синтеза"// "Повышение интеллектуализации САПР", материалы научного семинара. Судак, 1995г., М. Изд-во МГИЭМ, 1995 г., стр. 4346

4. Потемкин И.С., Евсиков И.А. "Некоторые особенности решения задачи расщепляющей декомпозиции." // "Информационные средства и технологии" МФИ-95, тез. докл. —М., МЭИ(ТУ), стр. 33-34.

5. Потемкин И.С., Евсиков И.А. "Некоторые особенности аппаратной реализации алгоритмов спектрального анализа." // "Информационные средства и технологии" МФИ-95, тез. докл. —М., МЭИ(ТУ), стр. 35-36.

6. Потемкин И.С., Евсиков И.А., Казарицкая Е.С. "Новая методика генерации тестовых функций для современной элементной базы." // "Информационные средства и технологии" МФИ-96, тез. докл. —М., МЭИ(ТУ), стр. 95-100.

7. Потемкин И.С., Евсиков И.А., Тимофеев И.Ю. "Методика визуализации булевых функций"// "Информационные средства и технологии" МФИ-97, тез. докл. -М., МЭИ(ТУ), стр. 64-69.

Выводы по главе:

• полученные результаты по построению спектра показывают, что при реализации такого рода алгоритмов целесообразно использовать и буферизацию и кэширование;

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

• численные результаты реализации алгоритмов показывают, что улучшение результатов синтеза составляет около 30%;

Заключение.

Основными результатами предлагаемой работы являются следующие:

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

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

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

1., Ding Y. "An optimal technology mapping algorithm for delay optimization 1. lookup-table based FPGA designs" In Proc. of the IEEE Int. Conf. on Computer-Aided Design (Santa Clara, CA, Nov.), 48-53. 1992

2. Cong J., Ding Y., Kahng А. В., Trajmar P., Chen K.-C. "An improved graph-based FPGA technology mapping for delay optimization" In Proc. of the IEEE Int. Conf. on Computer Design (Cambridge, MA, Oct.), 154-158. 1992

3. Francis R. J. "A tutorial on logic synthesis for lookup-table based FPGAs" In Proc. of the IEEE Int. Conf. on Computer-Aided Design (Santa Clara, CA, Nov.), 40— 47. 1992.

4. Shin H., Kim C. "Performance-oriented technology mapping for LUT-based FPGAs" IEEE Trans. VLSI Syst. 3, 2, 323-327. 1995.

5. Cong J., Ding Y. "On nominal delay minimization In LUT-based FPGA technology mapping" Integration—У LSI J. 18, 73-94. 1994.

6. Cong J., Ding Y. "Beyond the combinatorial limit In depth minimization for LUT-based FPGA designs" In Proc. of the IEEE Int. Conf. on Computer-Aided Design (Santa Clara, CA, Nov.), 110-114. 1993

7. Yang H., Wong D. F. "Edge-map: Optimal performance driven technology mapping for iterative LUT based FPGA designs" In Proc. of the IEEE Int. Conf. on Computer-Aided Design (San Jose, CA, Nov.), 150-155, 1995

8. Brayton R.K., Hatchel G.D., Sangiovanni-Vlncentelli A.L. "Multilevel Logic Synthesis" In Proc. of the IEEE, vol. 78, No. 2, February 1990

9. Cong J., Ding Y. "Combinational Logic Synthesis for LUT Based Field Programmable Gate Arrays" ACM Transactions on Design Autom. of Electronic Systems, Vol. 1., No. 2, April 1996, pp. 145-204

10. Akers S.B. "Binary Decision diagrams" IEEE Trans. Comput., 27, 6, pp. 509-516, 1978

11. Rudell R. "Logic synthesis for VLSI design" Ph.D. thesis, University of California, Berkeley, 1989.

12. Bryant R. E. "Symbolic manipulation of Boolean functions using a graphical14