Применение спектральных методов линейной декомпозиции для синтеза на современной элементной базе

• Автор: Евсиков, Игорь Алексеевич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 144 с. : ил.

Оглавление

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

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 Примеры практического применения
Заключение
Библиография


Глобального потока, где алгоритм пытается минимизировать коэффициент разветвления по выходу (fan-out) в выбранном вентиле, используя более глобальный взгляд на полученный граф [, , , |. Группа алгоритмов, базирующаяся на основе инвариантности узлов [, , ). Группа алгоритмов, основывающаяся на иерархии сетей узлов [, , ]. В данной работе автор исходит из гипотезы, что переход от дискретных (логических) операций к непрерывным (арифметическим) может привести к достижению хороших результатов. Причинами являются как большая историческая проработанность непрерывных задач, по сравнению с дискретными, так и психологическая особенность человека выявлять весьма сложные зависимости именно в непрерывных категориях. Эту гипотезу можно проиллюстрировать на примере апорий Зенона, или на примерах алгоритмов многокритериальной оптимизации, таких как градиентный и стохастического отжига. В каждом из этих алгоритмов используется попытка уйти от ограничений, связанных с переборностью оптимизационных задач. Отметим, что каждый из этих алгоритмов является приближенным, т. С другой стороны было доказано [4], что, например, для задач на покрытие дизъюнктивных нормальных форм градиентный алгоритм даст результат, в худшем случае отличающийся от оптимального в (1+п1п2) раза, хотя в абсолютном большинстве случаев это рахтичие еще меньше и не превосходит loglogn. В качестве элементной базы автор выбрал ППВМ (Field Programmable Gate Array - FPGA) - программируемые пользователем вентильные матрицы. Обоснованием актуальности этого выбора послужили следующие соображения. Эта элементная база была впервые предложена в году американской фирмой "Xilinx". Это событие произвело существенные изменения в методологии проектирования вычислительных систем и по своему значению приравнивается специалистами к появлению микропроцессоров (МП). По исследованиям фирмы Dataquest Inc, специализирующейся на изучении рынков, ППВМ является наиболее динамично развивающимся сегментом рынка цифровых ИС в -х годах, обгоняя в этом отношении даже МП [7]. Число приложений и, соответственно, число используемых микросхем постоянно растет, и фирма является одним из законодателей мод, контролируя более % [6] этого сегмента рынка. FPGA является одним из последних изобретений в области ИС, сочетающее в себе преимущества стандартного продукта с высокой степенью логической интеграции, гибкости и характеристик заказных СБИС (ASIC) и вентильных матриц (gate array) с удобством проектирования, свойственным устройствам, программируемым пользователем. Технологической основой ППВМ является статическая память (SRAM), которая может программироваться для реализации широкого набора логических элементов и межсоединений. Так как содержимое SRAM может быть изменено, то базирующиеся на технологии статической памяти ППВМ могут быть перепрограммируемы пользователем. Наиболее общий подход к построению базового логического элемента для такого рода ППВМ заключается в использовании 2к-битной ячейки памяти, которая реализует любую АГ-входовую одновыходную функцию БФ, путем загрузки в ячейку статической памяти таблицы истинности этой функции. Этот тип архитектуры получил название Table Look-Up (7X или Look-Up Table (LUT). Такие продукты предлагают на рынок многие поставщики, например Altera [], AT&T [], Xilinx |] и другие. Общие вопросы архитектуры ППВМ рассмотрены в [1, 2, 3]. В данной работе мы, без ограничения общности, будем использовать главным образом архитектуру LCA (Logic Cell Array) типа Table Look-Up (TLU) фирмы Xilinx, базовым логическим элементом которой является конфигурируемый логический блок - Configurable Logic Block - CLB. Логические функции и межсоединения определяются конфигурационной программой, хранимой во внутренних ячейках статической памяти кристалла. Особенностью логического синтеза в технологическом базисе FPGA является возможность реализации любой функции. Определяющим является только число входных переменных. В работе предлагается обзор математических задач, возникающих при синтезе в базисе ППВМ, а также используемые и предлагаемые автором способы их решения. Декомпозиции. Разделения. Покрытия. Слияния.