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

На правах рукописи

ГОНЧАРОВ ДЕНИС АЛЕКСАНДРОВИЧ

РАЗРАБОТКА МЕТОДОВ ПРОЕКТИРОВАНИЯ ЦИФРОВЫХ УСТРОЙСТВ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМАХ

05.13.12 - Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2004

Работа выполнена на кафедре вычислительной техники Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО).

Научный руководитель:

кандидат технических наук, доцент Скорубский Владимир Иванович

Официальные оппоненты:

доктор технических наук, профессор Шалыто Анатолий Абрамович

кандидат технических наук, доцент Филиппов Алексей Семенович

Ведущая организация:

Федеральное государственное унитарное предприятие центральный научно-исследовательский институт "ГРАНИТ".

Защита диссертации состоится "_2<_" сеигп* сГрЛ 2004 года в \S-so часов на заседании диссертационного совета Д.212.227.05 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики, 197101, г. Санкт-Петербург, ул. Саблинская 14, СПб ГУ ИТМО.

С диссертацией можно ознакомиться в библиотеке СПб ГУ ИТМО. Автореферат разослан 2004г.

Ученый секрета у [ и д а т технических наук, доцент

диссертационного Поляков Владимир Иванович

совета Д.212.227.05

ОБШДЯ ХАРАКТЕРИСТИКА РАБОТЫ

АКТУАЛЬНОСТЬ ТЕМЫ

Развитие технологии производства средств вычислительной техники влияют на развитие и совершенствование средств проектирования.

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

Если сопоставить сроки разработки и создания реального проекта с уровнем сложности 105 логических ячеек и/или Кбайт в 90-е годы и в начале 2000-х годов, то различие составляет два порядка: несколько лет в начале 90-х годов и два-три месяца в 2000 году.

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

За последнее десятилетие опробованы различные технологии. Весь накопленный опыт суммируется в современных интегрированных технологиях фирм ALTERA, X1LINX, ACTEL, ATMEL, CYPRESS и еще десятка фирм, создающих системы на кристалле.

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

Все эти ожидания и значительный прогресс в создании информационных

»

РОС 11ЛЦ БИБЛ С.Пе ОЭ

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

Практическое применение САПР MAX+PLUSII, FOUNDATION и LIBERO выявило следующие проблемы.

1. Методы синтеза регулярных схем.

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

2. Реализация схем конечных автоматов в ПЛИС.

Канонические методы синтеза схем конечных автоматов (Лазарев В.Г., Баранов СИ., Варшавский В.И., Соловьев В.В.. и. др.) разработаны преимущественно для дискретной элементной базы и заказных матричных БИС. Применение канонических методов в ПЛИС не дает оптимальных решений, так как эти методы не учитывают структуру ячеек и матрицы соединений.

3. Алгоритм размещения и трассировки.

Исследования показали, что на этапе размещения и трассировки с высокой вероятностью возникают отказы вследствие ограничений используемых в САПР алгоритмов.

Таким образом, работа, посвященная разработке методов проектирования цифровых устройств на ПЛИС, АКТУАЛЬНА и представляет научный и практический интерес.

ПРЕДМЕТОМ ИССЛЕДОВАНИЯ диссертационной работы являются математические методы, алгоритмы и их применение при проектировании распределенных информационных систем на ПЛИС фирмы ALTERA с использованием САПР MAX+PLUS II.

ЦЕЛЬ РАБОТЫ. Целью диссертационной работы является разработка методов проектирования цифровых устройств на ПЛИС. Для достижения этой цели решались следующие задачи.

1. Разработка методов для этапа логического проектирования на ПЛИС:

- разработка методов синтеза регулярных схем;

- разработка методов синтеза и преобразований конечных автоматов.

2. Разработка методов для этапа конструкторского проектирования на ПЛИС:

- разработка методов размещения функций по логическим ячейкам ПЛИС;

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

- разработка методов трассировки соединений.

МЕТОДЫ ИССЛЕДОВАНИЯ. Методами исследования являются теория регулярных языков, теория алгоритмов, теория графов, комбинаторика и теория множеств, теория конечных автоматов, теория сетей Петри и теория программирования.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем.

1. Разработаны методы для этапа логического проектирования на ПЛИС:

- методы синтеза регулярных схем в ПЛИС, которые позволяют улучшить параметры схемы;

- метод алгоритмического описания ячейки ПЛИС на основе регулярных языков, который может использоваться на этапе логического синтеза;

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

- метод синтеза конечных автоматов, направленный на минимизацию количества функций и применение параметризируемых модулей.

2. Разработаны методы для этапа конструкторского проектирования на ПЛИС:

- математическая модель матрицы межсоединений на основе графов связности;

— алгоритм выбора соединений на основе системы различных представителей;

- алгоритм распределения контактов, основанный на решении задачи о назначении.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ представляет:

1. Прикладная библиотека параметризируемых модулей, созданная на основе разработанных методов синтеза регулярных схем.

2. Программа, предназначенная для расчета параметров заданной регулярной схемы и выбора метода синтеза в зависимости от заданного вектора оценок.

3. Программа, выполняющая трассировку соединений на основе разработанного точного метода выбора соединений.

4. Разработанные методы и алгоритмы применялась при проектировании авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов.

ПУБЛИКАЦИИ. По материалам диссертации опубликовано восемь печатных работ.

АПРОБАЦИЯ РАБОТЫ. Обсуждение материалов работы производилось на XXXI научной и учебно-методической конференции Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО), XXXII научной и учебно-методической конференции СПб ГУ ИТМО, Шестой межведомственной научно-технической конференции в филиале Военно-космической Краснознаменной Академии (г. Пушкин).

ЭФФЕКТ ОТ ИСПОЛЬЗОВАНИЯ результатов данной работы заключается в улучшении значений основных параметров ПЛИС (число ячеек, максимальная задержка) на 20-30% при разработке распределенных информационных систем.

ОСНОВНЫЕ ПОЛОЖЕНИЯ. ВЫНОСИМЫЕ НА ЗАЩИТУ:

1. Методы синтеза регулярных схем в ПЛИС.

2. Метод алгоритмического описания ячейки ПЛИС.

3. Метод преобразования конечных автоматов в ПЛИС.

4. Алгоритм выбора соединений.

5. Алгоритм распределения контактов.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ

Диссертация состоит из введения, пяти глав, заключения и списка литературы (53 наименования). Материал изложен на 139 страницах машинописного текста и содержит 112 рисунков и 23 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Для распределенных информационных систем наиболее актуально

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

Традиционное проектирование на ПЛИС разделяется на этапы, показанные на рис. 1.

Спецификации Анализ функционирования

Этап описания проекта

САПР

^ ^¿югияемсопгй. проектирования^ ^конструкторского' ^ проектирования ~ ¿-Г**"-

- -

Этап моделирования

Логическая структура

Файл размещения и трассировки

Файл программирования

Рис.1. Структура традиционного проектирования на ПЛИС

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

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

использованием доступных в САПР средств.

Во второй главе рассматриваются методы синтеза регулярных схем и метод алгоритмического описания ячейки.

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

Для структурного описания принципа работы логический ячейки можно использовать язык регулярных выражений. После упрощений и замены конкретных наименований сигналов символами алфавита £={f, q, g, с, s, г, е, МХ, v, &} регистр можно представить следующим регулярным выражением (1) на языке

(1)

где f - функция данных, q — быстрый вход, g — глобальный синхросигнал, с — сигнал синхронизации/разрешения, s — асинхрошгая установка, г — асинхронный сброс, е-глобальный сигнал сброса, МХ(х, у) - операция мультиплексирования.

Алгоритм идентификации этих функций может быть построен по методу Макнотона-Ямады.

Логическую ячейку можно описать как множество термов L = (Т, Е}. Множество Т = {a,b,c,d} иЕ = {е}. Т — это термы общего назначения, а Е -расширитель. Для сравнения методов синтеза используется экспертная оценка а в виде вектора параметров, которые размещаются в порядке убывания значимости (2):

a = (Nbt,NT,NE), (2)

где NL - число занятых ячеек, NT - число занятых термов, NE - число занятых расширителей, t - задержка сигнала.

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

модулях с использованием различных методов.

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

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

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

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

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

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

Порядок выбора зависит от значимости оценок в каждом конкретном проекте. Предложен алгоритм и программа ограниченного перебора для выбора метода с лучшими параметрами.

В третьей главе разрабатываются усовершенствованные и адаптированные к применению в ПЛИС методы синтеза схем конечных автоматов (КА).

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

Из известных формальных методов описания алгоритмов для синтеза в ПЛИС наиболее приемлемыми представляются регулярные языки, языки моделирования аппаратуры и языки описания дискретных систем. Соответствующие алгоритмы при реализации в ПЛИС преобразуются каноническими методами в КА.

Предлагается два метода синтеза КА.

1. Метод выделения регулярной памяти.

В ПЛИС могут быть использованы следующие возможности упрощения:

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

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

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

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

Метод позволяет минимизировать нерегулярную часть, реализовать функции F10/01 и Р00/11 в дискретной логики и расширить регулярную часть на основе параметризированного модуля.

2. Метод преобразований конечных автоматов в систему эквивалентных параллельно работающих конечных автоматов.

Определение. Конечный автомат Мура А, с унитарным выходом у, -включает множество состояний, в каждом из которых формируется или отсутствует выходной сигнал у,.

Определение. Множество входов Т={11, ^ ...} конечного автомата строго

различимы, если события, связанные с одновременным появлением любых сигналов из Т, не совместимы.

Определение. Входная последовательность не детерминирована, если в любом состоянии КА возможен любой из входных сигналов ^ e Т. В детерминированной входной последовательности все сигналы на входе в каждом состоянии предопределены.

Теорема. Для любого конечного автомата А, с унитарным выходом, строго различимыми входами и детерминированными входными последовательностями существует эквивалентный автомат Bi с двумя состояниями 0/- и 1/уг

Доказательство. Множество состояний КА может быть разделено на два подмножества Q0, Q1 - в каждом из которых формируется, либо не формируется выход у, и подмножества T00, Т01, Т10, Т11, соответствующие переходам в В,.

Пусть в некотором начальном состоянии q0 e Q на входе КА формируется последовательность входов .... t1n. Каждому входу соответствует

единственный выход, определяемый разбиением Q1) и (^,0, T01, Tl0, Т11), для КА со строго различимыми входами.

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

По определению (Миллер) состояния q1, q1 эквивалентны, если формируют одинаковые выходные последовательности для одинаковых входных последовательностей. Таким образом, любые два состояния из А, и В1 в которых совпадают выходы, эквивалентны, и два автомата эквивалентны при условии, что начальные состояния эквивалентны.

Следствие. Если некоторый КА формирует вектор выходов {у1, у2, ..., уп}, имеет строго различимые входы, то КА может быть представлен системой параллельных автоматов S={B,} с общими входами и унитарными выходами

Каждый из этих автоматов в соответствии с теоремой может быть представлен эквивалентным КА с двумя состояниями В,. Исходный конечный автомат заменяет эквивалентная система параллельных конечных автомат {В,}Л=1,п.

Для применения следствия в общем случае необходимо привести произвольную систему входов 1={1|,..лш} к строго различимой при совместной работе {В,} и обеспечить детерминированость входных последовательностей сигналов.

Подобные преобразования не всегда допустимы, но возможны в некоторых классах графов операций, реализованных на сетях Петри. Если условия преобразования КА в систему В, выполняются, то упрощается реализация КА в ПЛИС на основе В,. Каждый КА соответствует одной логической ячейки ПЛИС.

В четвертой главе рассматривается задача трассировки соединений в ПЛИС.

Реализация логического массива в ПЛИС после распределения логических функций по ячейкам зависит от выбора соединений в матрице межсоединений. Опыт работ и эксперименты показали, что на этапе выбора соединений с высокой вероятностью возникают отказы, вследствие ограничений используемых в САПР алгоритмов. Проведены эксперименты в САПР МАХ+РШЗП и на основании результатов сформирована математическая модель матрицы межсоединений на основе графов связности, позволяющая визуально найти допустимые соединения последовательным выбором вершин.

Метод выбора соединений на основе алгоритма выбора системы различных представителей (СРП) имеет следующую общую постановку.

1. Задано множество вертикальных линий О и горизонтальных Р.

2. Пусть множество ребер 8, е О смежны с каждой вершиной 1 е Р (1=0...Инд-1) в двудольном графе.

3. Требуется выбрать Р различных вершин из 81, по одному из каждого подмножества 81. Выбранные вершины представляют подмножества 8, и

совокупность из N вершин, выбранных для представления всех N подмножеств, является системой различных представителей для S.

Для графа на рис.2 приведена табл.1, содержащая множества S, и демонстрирующая порядок выбора элементов в СРП при свободной схеме соединений. Если выбор на данном шаге невозможен и S8), то

соответствующие элементы этого множества являются ключами для поиска возможной замены в ранее рассмотренных множествах Sj, где ] < 1.

О-Мр

(1) (7)

Рйс.2. Граф связности Таблица I. Порядок выбора элементов СРП

8, I СРП СРП СРП СРП

1 2.4 2 2 2 2

2 1.6 1 1 1 1

3 3.7 3 3=>7 7 7

4 0.5 0 0 0=>5 5

5 2.6 6 6 6 6

6 4.7 4 4 4 4

7 1.3 - 3 3 3

8 0,2 - - 0 0

Трассы в ПЛИС реализованы на основе матрицы межсоединений и зависят от алгоритмов размещения логических ячеек и внешних выводов. При этом расположение внешних выводов зависит от печатной платы, в состав которой входит ПЛИС.

Все соединения разделены на подмножества ^разрядных шин, и выбираются пары контактов с минимальным расстоянием. Пусть множество контактов ПЛИС Р={р1, ..., РЭД- Множество контактов других элементов,

размещенных на плате, D={d1, ..., dN}. Формулируется традиционная "задача о назначении" Р "товаров" на D "мест", минимизирующая целевую функцию (3):

Ш1п(1Су), (3)

где ^ - это функция расстояния между i и j контактов,! е Р, j € Б.

Расстояния при решении задачи размещения контактов рассчитывается с учетом координат (4):

С.^х.-^Му.-УЛ, (4)

где х и у координаты контактов i и j.

В пятой главе рассматривается применение технологии ПЛИС при проектировании авиационных распределенных информационных систем с использованием разработанных методов. Использование разработанных методов при проектировании показано на рис. 3.

На этапе логического проектирования применяются методы синтеза КА и методы синтеза регулярных схем. Методы синтеза регулярных схем применяются при разработке библиотеки параметризированных модулей, которая включена в САПР.

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

Рис.3. Структура проектирования с применением разработанных методов

Методы использовались при проектировании интерфейсных модулей в распределенных информационных системах бортовых авиакосмических объектов.

В табл. 2 приведен результат проектирования шести интерфейсных модулей с применением технологии ПЛИС. Из таблицы следует, что применение разработанных методов и алгоритмов дает выигрыш в 20-30% по основным параметрам — числу логических ячеек и максимальной задержки

Таблица 2. Сравнение результатов проектирования интерфейсных модулей

.. Модуль С применением традиционного проектирования С применением разработанных методов и алгоритмов

М!.С 1, НС г, не

А429-3-24 300 50 210 40

АВВ 250 60 200 50

АКО 480 40 380 30

МКЗ-2 700 60 590 45

мпиз 250 50 180 30

АВВЗ 450 70 350 50

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ.

В работе получены следующие результаты:

1. Разработаны методы и алгоритмы для этапов проектирования цифровых устройств на ПЛИС:

- методы синтеза регулярных схем;

- методы синтеза и преобразований конечных автоматов;

- алгоритм выбора соединений;

- алгоритм распределения контактов.

2. Предложен метод алгоритмического описания структуры ПЛИС на основе регулярных языков, который используется на этапе логического синтеза.

3. Разработана математическая модель матрицы межсоединений на основе графов связности.

4. На основе разработанных методов синтеза регулярных схем- создана прикладная библиотека параметризируемых модулей, которая применялась при проектировании авиационных интерфейсных модулей.

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

6. На основе разработанного точного метода выбора соединений написана программа, выполняющая трассировку соединений.

7. Методы и алгоритмы применялись при разработке авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ:

1. Гончаров ДА Микросхемы программируемой логики // Изв. вузов. Приборостроение. 2003. Т.46, № 2. С.24-28.

2. Гончаров Д.А., Скорубский В.И. Расчет размещения схем в логических матрицах // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО). Вып. 6. Информационные, вычислительные и управляющие системы. 2002. С. 122-126.

3. Гончаров Д.А., Скорубский В.И. Стратегия частичных расширителей // Современные технологии. Сборник научных статей. СПб.: СПб ГУ ИТМО, 2003. С. 146-152.

4. Гончаров Д.А., Скорубский В.И. Алгоритмы выбора соединений в ПЛИС // Научно-технический вестник СПб ГУ ИТМО. Вып. 10. Информация и управление в технических системах. 2003. С.39-49.

5. Гончаров. ДА, Скорубский В.И. Стандартные библиотечные модули // Тематический научно-технический сборник №23. Проблемные вопросы сбора, обработки и передачи информации в сложных радиотехнических системах. Пушкинский # Ордена Красной Звезды филиал Военно-космической Краснознаменной Академии. 2003. С.63-69.

6. Гончаров ДА,, Скорубский В.И. Эффективность реализации регулярных схем в ПЛИС // Шестая межведомственная научно-техническая конференция. Тезисы докладов. Филиал Военно-космической Краснознаменной Академии им. А.Ф. Можайского. 2003. С. 163-164.

7. Глушкин Е.З., Рубин ГС, Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. Свидетельство на полезную модель № 24296 от 21.01.2002.

8. Глушкин Е.З., Рубин ГС, Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. ПАТЕНТ на изобретение № 2221267 от 10.01.2004.

»14281

Тиражирование и брошюровка выполнены в Центре "Университетские Телекоммуникации". Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233-46-69. Лицензия ЦДЛ № 69-182 от 26.11.96 Тираж 100 Э13.

ВВЕДЕНИЕ.

1. Управление проектированием в технологии программируемых логических интегральных схем (ПЛИС).

1.1. Роль ПЛИС в проектировании устройств.

1.2. Обзор архитектур и классификация ПЛИС.

1.2.1. Программируемые логические матрицы.

1.2.2. Программируемая матричная логика.

1.2.3. Программируемые коммутируемые матричные блоки.

1.2.4. Программируемые вентильные матрицы.

1.3. Управление проектированием в инструментальной среде MAX+PLUS II.

Выводы.

2. Алгоритмы логического синтеза.

2.1. Программируемые регулярные схемы.

2.2. Описание структуры логической ячейки.

2.3. Синтез логических функций общего назначения в ПЛИС.

2.4. Методы синтеза.

2.5. Синтез библиотечных модулей (макрофункций и мегафункций).

2.5.1. Счетчики.

2.5.2. Компараторы.

2.5.3. Мультиплексоры.

2.5.4. Комбинированная схема.

Выводы.

3. Реализация алгоритмов в ПЛИС.

3.1. Алгоритмы и их применение на этапе аппаратной реализации.

3.2. Синтез схем конечных автоматов (КА) с памятью.

3.3. Параллельное преобразование КА в ПЛИС.

3.3.1. Параллельное преобразование КА, полученных на сетевых моделях алгоритмов.

3.3.2. Параллельное преобразование КА для микропрограммных автоматов.

Выводы.

4. Выбор соединений в ПЛИС.

4.1. Предпосылки к разработке точного алгоритма выбора соединений.

4.2. Структура соединений.

4.3. Математическая модель массива межсоединений.

4.4. Последовательный комбинаторный метод выбора соединений.

4.5. Проблемы при размещении.

4.6. Метод выбора соединений на основе алгоритма системы различных представителей.

4.7. Алгоритм трассировки соединений в ПЛИС.

Выводы.

5. Применение технологии ПЛИС при проектировании авиационных распределенных информационных систем (РИС).

5.1. Архитектура авиационных РИС.

5.2. Интерфейсные модули.

5.3. Применение методов проектирования схем в ПЛИС.

5.3.1. Модуль А429-3-24.

5.3.2. Модуль ABB.

5.3.3. Модуль АКО.

Выводы.

АКТУАЛЬНОСТЬ ТЕМЫ

Развитие технологии производства средств вычислительной техники влияют на развитие и совершенствование средств проектирования.

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

Если сопоставить сроки разработки и создания реального проекта с уровнем: сложности 105 логических ячеек и/или Кбайт в 90-е годы и в начале 2000-х годов, то различие составляет два порядка: несколько лет в начале 90-х годов и два-три месяца в 2000 году.

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

За последнее десятилетие опробованы различные технологии. Весь накопленный опыт суммируется в современных интегрированных технологиях фирм ALTERA, XILINX, ACTEL, ATMEL, CYPRESS и еще десятка фирм, создающих системы на кристалле.

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

Все эти ожидания и значительный прогресс в создании информационных систем относится к интегральным технологиям создания встроенной и распределенной аппаратуры на основе программируемых логических интегральных схем (ПЛИС).

Практическое применение САПР MAX+PLUS II, FOUNDATION и LIBERO выявило проблемы в следующих областях.

1. Методы синтеза регулярных схем.

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

2. Реализация схем конечных автоматов в ПЛИС.

Канонические методы синтеза схем конечных автоматов (Лазарев В.Г.,

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

3. Алгоритм размещения и трассировки.

Исследования показали, что на этапе размещения и трассировки с высокой вероятностью возникают отказы вследствие ограничений используемых в САПР алгоритмов. ф Таким образом, работа, посвященная разработке методов проектирования цифровых устройств на ПЛИС, АКТУАЛЬНА и представляет научный и практический интерес.

ПРЕДМЕТОМ ИССЛЕДОВАНИЯ диссертационной работы являются математические методы, алгоритмы и их применение при проектировании распределенных информационных систем на ПЛИС фирмы ALTERA с использованием САПР MAX+PLUS II.

ЦЕЛЬ РАБОТЫ. Целью диссертационной работы является разработка методов проектирования цифровых устройств на ПЛИС.

Для достижения этой цели решались следующие задачи. 1. Разработка методов для этапа логического проектирования на ПЛИС:

- разработка методов синтеза регулярных схем;

- разработка методов синтеза и преобразований конечных автоматов.

2. Разработка методов для этапа конструкторского проектирования на ПЛИС:

- разработка методов размещения функций по логическим ячейкам ПЛИС;

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

- разработка методов трассировки соединений.

МЕТОДЫ ИССЛЕДОВАНИЯ. Методами исследования являются теория регулярных языков, теория алгоритмов, теория графов, комбинаторика и теория множеств, теория конечных автоматов, теория сетей Петри и теория программирования.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем.

1. Разработаны методы для этапа логического проектирования на ПЛИС:

- методы синтеза регулярных схем в ПЛИС, которые позволяют улучшить параметры схемы;

- метод алгоритмического описания ячейки ПЛИС на основе регулярных языков, который может использоваться на этапе логического синтеза;

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

- метод синтеза конечных автоматов, направленный на минимизацию количества функций и применение параметризируемых модулей.

2. Разработаны методы для этапа конструкторского проектирования на ПЛИС:

- математическая модель матрицы межсоединений на основе графов связности;

- алгоритм выбора соединений на основе системы различных представителей;

- алгоритм распределения контактов, основанный на решении задачи о назначении.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ представляют:

1. Прикладная библиотека параметризируемых модулей, созданная на основе разработанных методов синтеза регулярных схем.

2. Программа, предназначенная для расчета параметров заданной регулярной схемы и выбора метода синтеза в зависимости от заданного вектора параметров.

3. Программа, выполняющая трассировку соединений на основе разработанного точного метода выбора соединений.

4. Разработанные методы и алгоритмы применялась при проектировании авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов, что подтверждается актом внедрения.

ПУБЛИКАЦИИ. По материалам диссертации опубликовано восемь печатных работ.

• АПРОБАЦИЯ РАБОТЫ. Обсуждение материалов работы производилось на

XXXI научной и учебно-методической конференции Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО), XXXII научной и учебно-методической конференции СПб ГУ ИТМО и Шестой межведомственной научно-технической конференции в филиале Военно-космической Краснознаменной Академии (г. Пушкин).

ЭФФЕКТ ОТ ИСПОЛЬЗОВАНИЯ результатов данной работы заключается в сокращении числа ячеек и максимальной задержки в ПЛИС при разработке распределенных информационных систем на 20-30% по сравнению с методами, ^ использующимися в САПР стандартной поставки.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ.

1. Методы синтеза регулярных схем в ПЛИС.

2. Метод алгоритмического описания ячейки ПЛИС.

3. Метод преобразования конечных автоматов в ПЛИС.

4. Алгоритм выбора соединений.

5. Алгоритм распределения контактов. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ

Диссертация состоит из введения, , пяти глав, заключения и списка литературы (53 наименования). Материал изложен на 139 страницах машинописного текста и содержит 112 рисунков и 23 таблицы.

Выводы

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

2. Приведена обобщенная структура интерфейсного модуля.

3. Приведены примеры применения разработанных методов проектирования в технологии ПЛИС для реализации авиационных интерфейсов. Показано, что применение методов дает существенное улучшение параметров (20-30%) ПЛИС.

ЗАКЛЮЧЕНИЕ

В работе получены следующие результаты.

1. Разработаны методы и алгоритмы для этапов проектирования цифровых устройств на ПЛИС:

- методы синтеза регулярных схем;

- методы синтеза и преобразований конечных автоматов;

- алгоритм выбора соединений;

- алгоритм распределения контактов.

2. Предложен метод алгоритмического описания структуры ПЛИС на основе регулярных языков, который используется на этапе логического синтеза.

3. Разработана математическая модель матрицы межсоединений на основе графов связности.

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

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

6. На основе разработанного точного метода выбора соединений написана программа, выполняющая трассировку соединений.

7. Методы и алгоритмы применялись при разработке авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов, что подтверждается актом внедрения.

1. Грушвицкий Р. И., Мурсаев А. X., Угрюмов Е. П. Проектирование систем на микросхемах программируемой логики. - СПб.: БХВ-Петербург, 2002. - 608 с.

2. Соловьев В.В., Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия-Телеком, 2001. - 636 с.

3. МАХ7000. Programmable Logic Device Family. ALTERA, 2003. - 85 с.

4. FLEX 1 OK. Embedded Programmable Logic Device Family. ALTERA, 2003. -128 c.

5. APEX 20K. Programmable Logic Device Family. ALTERA, 2004. - 117 c.

6. Антонов А.П., Мелехин В.Ф., Филлипов A.C. Обзор элементной базы фирмы "ALTERA". СПб.: "ЭФО", 1997. - 110 с.

7. XILINX Data Book. XILINX, 2003. - 210 с.

8. Мальцев П.П., Гарбузов Н.И. Программируемые логические ИМС на КМОП-структурах и их применение. -М.: Энергоатомиздат, 1998. — 160 с.

9. ACTEL Data Book. ACTEL, 2003. - 320 с.

10. ATMEL Data Book. ATMEL, 2003. - 126 c.1 l.CYPRESS Data Book. CYPRESS, 2003. -212 c.

11. Комолов Д.А., Мяльк P. А., Зобенко А. А., Филиппов A.C. Системы автоматизированного проектирования фирмы ALTERA MAX+PLUS II и Quartus II. M.: Радиософт, 2002. - 352 с.

12. З.Антонов А.П. Язык описания цифровых устройств AHDL. М.: РадиоСофт, 2002.- 224 с.

13. Бибило П.Н. Основы языка VHDL. М.: Солон-Р, 2000. - 200 с.

14. VHDL для моделирования, синтеза и формальной верификации аппаратуры / пер с англ. М.: Радио и связь, 1995. - 256 с.1 б.Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. -250 с.

15. Холл М. Комбинаторика. М.: Мир, 1970. - 424 с.

16. Рыбников К.А. Введение в комбинаторный анализ. М.: Московский университет, 1972. -254 с.

17. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476 с.

18. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. -264 с.

19. Шалыто А.А. SWITH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. - 628 с.

20. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.

21. Юдицкий С.А., Мачергут В.З. Логическое управление дискретными процессами. М.: Машиностроение, 1980 — 300 е.

22. Luciano Lavagno. Models of Computation for Embedded System Design, 1998. www.polito.it.

23. System C, 2002. www.systemc.org.

24. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1979. — 348 с.

25. Варшавский В.И. и др. Апериодические автоматы. М.: Наука, 1976. — 420 с.

26. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. -М.: Энергия, 1989. 326 с.

27. Девятков В.В. Программная реализация управляющих алгоритмов. — М.: Наука, 1980.-210 с.

28. Вавилов Е.М., Портной Т.П. Синтез схем ЭЦМ. М.: Советское радио, 1963. -430 с.

29. Чу Я. Организация ЭВМ и микропрограммирование. М.: Мир, 1975. - 592 с.

30. Ахо А., Ульман Дж. Д. Вычислительные аспекты СБИС. М.: Радио и связь, 1990.-306 с.

31. Ахо А., Ульман Дж. Д. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.-200 с.

32. Миллер Р. Теория переключательных схем. Т.2. М.: 1971. - 304 с.

33. Ахо А., Ульман Дж. Д. Теория синтаксического анализа, перевода икомпиляции. М. Мир, 1972. - 612 с.

34. Шило В.JI. Популярные микросхемы ТТЛ. М. Аргус, 1993. - 64 с.

35. Фридман А., Менон П. Теория и проектирование переключательных схем. -М.: Мир, 1978.-350 с.

36. ГОСТ 18977-79. Комплексы бортового оборудования:самолетов и вертолетов. Типы функциональных связей. Виды и уровни электрических сигналов. М.: Издательство стандартов, 1979. — 10 с.

37. РТМ 1495-75. Обмен информацией двуполярным кодом в оборудовании летательных аппаратов, 1975. 124 с.

38. ГОСТ 26765.51-86. Интерфейс магистральный параллельный МПИ. Системы электронных модулей. М.: Издательство стандартов, 1986. - 30 с.

39. ГОСТ 26765.52-87. Интерфейс магистральный последовательный. Системы электронных модулей. М.: Издательство стандартов, 1987. - 30 с.

40. Мячев А.А. Интерфейсы средств вычислительной техники. М.: Радио связь, 1993.-354 с.

41. Скорубский В.И., Кордонов Г.Н. Синтез схем МПА на основе счетчиков и сдвигателей. СПб.: Полиграфический институт, 2003.

42. Гончаров Д. А. Микросхемы программируемой логики // Изв. вузов. Приборостроение. 2003. Т.46, № 2. С.24-28.

43. Гончаров Д.А., Скорубский В.И. Стратегия частичных расширителей // Современные технологии. Сборник научных статей. СПб.: СПб ГУ ИТМО, 2003. С.146-152.

44. Гончаров Д.А., Скорубский В.И. Алгоритмы выбора соединений в ПЛИС // Научно-технический вестник СПб ГУ ИТМО. Вып. 10. Информация и управлениев технических системах. 2003. С.39-49.

45. Гончаров Д.А., Скорубский В.И, Жвариков В.А. Алгоритмы выбора соединений в ПЛИС. СПб.: Санкт-Петербургский государственный политехнический университет, 2003 (в печати).

46. Гончаров Д.А., Скорубский В.И. Эффективность реализации регулярных схем в ПЛИС // Шестая межведомственная научно-техническая конференция. Тезисы докладов. Филиал Военно-космической Краснознаменной Академии им. А.Ф. Можайского. 2003. С. 163-164.

47. Гончаров Д.А., Скорубский В.И. Стандартные библиотечные модули // Изв. вузов. Приборостроение. 2004 (в печати).

48. Глушкин Е.З., Рубин Г.С., Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. Свидетельство на полезную модель № 24296 от 21.01.2002.

49. Глушкин Е.З., Рубин Г.С., Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. ПАТЕНТ на изобретение № 2221267 от 10.01.2004.1. Текст программы CORE.

50. SRD14. .0. = srd.q[15. . 1] ; SRD15 = DIN Sc chin;

51. CTB1F = (ctb.q4 Sc ctb.q3 Sc ctb.q2 Sc ctb.ql & ctb.qO);ctp.data . = DORAM[9. . 8] ;ctp.clock = CLK;1. Ctp.sload = RDRS;ctp.cnten = WRRD Sc 'start;ctp.sclr = WRRD Sc start Sc chin;ctp.aclr = RESET;

52. DORAM13 & RDRS; rdy.clock = CLK; rdy.enable = RDRS #

53. WRRD & ENACHG & Ictp.qO & ctp.ql & Irdy.qO & chin #

54. VRDY3.0. = vrdy.q[3. .0] ; VRDY[13.4] = GND; VRDY14 = GND; VRDY15 = GND;--Vrdyena;• NCH 4 . . 0. = vrdy.q[4. .0] ;

55. RSRAM5.0. RSRAM[7.6] RSRAM [9 . .8] RSRAM10 RSRAM11 RSRAM12 RS RAM13ctb.q . ; = GND; = ctp.q [] ; = par.q [] ; = nbl .q [] ; = enatr .q [] ; = rdy.q [] ;

56. RSRAM 15 . . 14. = GND; END;

57. PUT; INPUT; INPUT; INPUT; INPUT; INPUT; OUTPUT;1. VARIABLE

58. EQ00(WIDTH-1).0. : NODE; upeq[(WIDTH).0] : NODE; BEGINupeq0. = VCC;

59. FOR i IN 0 TO WIDTH-1 GENERATEout1. = TFFE( EQ00i. $ GND, GLOBAL( CLK), GLOBAL( RESET), EQ00 [i] = ! CLR & LOAD & IN[i] Sc !out[i] --(sload)

60. CLR Sc 'LOAD & COUNT Sc upeq1. --(up)

61. CLR & out i. ; --(sclr) upeq[i + l] = upeq1. & out [i];1. END GENERATE; END;1. VCC, VCC);1. Текст программы AVTPETRI.

62. CLUDE "lpmdf f.inc"; INCLUDE "cntmod.inc"; INCLUDE "cmpalb";1. SUBDESIGN cpwm (1. D15.0. WRT[7.0] WE1.PUT INPUT INPUT1. CLK : INPUT;1. RESET : INPUT;1. PWMOUT7.0. : OUTPUT;

63. PWMOUT. = cmpl [] & RESET; END;cntnod with (LPMWIDTH=10); lpmdff with (LPMWIDTH=10); lpmdff with (LPMWIDTH=10); cmpalb with (WIDTH=10);

64. Ниже приведен текст модуля CNTMOD из разработанной библиотеки. Выражение строится таким образом, что число термов не зависит отразрядности счетчика.mod) терм для сброса триггера при достижении заданного значения; (up) - терм для инкремента.

65. CLUDE "lpmcounter"; PARAMETERS1. WIDTH = 15,

66. MODUL = B"0110000000000001";считать будет от 0 до MODUL-1)1. SUBDESIGN cntmod (1. CLK RESET1. OUT(WIDTH-1).0.1. VARIABLE

67. EQOO{WIDTH-1) mdl[WIDTH.0. M [WIDTH.0] MO[WIDTH.0] T[WIDTH.0] pmod[WIDTH.0] BEGIN1.PUT; INPUT; OUTPUT;0. : NODE; NODE ;

68. NODE; -- M= out2 & outl & loutO; (б) до какого считать NODE; — MO до какого считать начиная со старших разрядов NODE; -- Т - произведение для инкремента cnt2 = cntl & cntO; : NODE;

69. ASSERT (MODUL>2A(WIDTH-1))

70. REPORT "Значение MODUL должно быть больше 2Л(WIDTH-1)!" SEVERITY INFO;mdl . = MODUL-1;

71. M0. = VCC; pmod[0] = VCC; T[0] = VCC;

72. FOR i IN 0 TO WIDTH-1 GENERATE

73. M i + 1. = M1. & {out[i] & mdl[i] # !out[i] & !mdl[i]); T [i + 1] = T [i] & out [i] ; pmod[i+l] = pmodti] & mdl [i]; END GENERATE;-- обратное произведение модуля MO1. MOWIDTH. = VCC;

74. FOR i IN WIDTH-1 TO 0 GENERATE

75. MO 1. = MO i + 1. & (out [i] & mdl [i] # !out[i] & !mdl[i]); END GENERATE;out 0. = TFFE( EQ00[0] $ GND, GLOBAL( CLK), GLOBAL( RESET), VCC, VCC) ; if mdl[0] then EQ00[0] = VCC;else EQ000. = !(M[WIDTH]);end if;

76. FOR i IN 1 TO WIDTH-1 GENERATEout1. » TFFE( EQ00i. $ GND, GLOBAL( CLK), GLOBAL( RESET), VCC, VCC) if mdl[i] then EQ00[i] = T[i] # M[WIDTH];elsif pmod1. then EQ00i. = T[i] & !(MO[i]); else EQ00[i] = T[i] ;end if;1. END GENERATE;1. END;

77. Ниже приведен текст модуля CMPALB из разработанной библиотеки. Компаратор предназначен для сравнения двух двоичных кодов и выдачи сигнала "меньше".1. PARAMETERS (1. WIDTH = 5;1. SUBDESIGN cmpalb (