Содержание к диссертации
Введение
1. Управление проектированием в технологии программируемых логических интегральных схем (ПЛИС) 8
1.1. Роль ПЛИС в проектировании устройств 8
1.2. Обзор архитектур и классификация ПЛИС 12
1.2.1. Программируемые логические матрицы 13
1.2.2. Программируемая матричная логика 14
1.2.3. Программируемые коммутируемые матричные блоки 15
1.2.4. Программируемые вентильные матрицы 17
1.3. Управление проектированием в инструментальной среде MAX+PLUSII 21
Выводы 26
2. Алгоритмы логического синтеза 27
2.1. Программируемые регулярные схемы 27
2.2. Описание структуры логической ячейки 32
2.3. Синтез логических функций общего назначения в ПЛИС 35
2.4. Методы синтеза 40
2.5. Синтез библиотечных модулей (макрофункций и мегафункций) 48
2.5.1. Счетчики 49
2.5.2. Компараторы 57
2.5.3. Мультиплексоры 63
2.5.4. Комбинированная схема 66
Выводы 67
3. Реализация алгоритмов в ПЛИС 68
3.1. Алгоритмы и их применение на этапе аппаратной реализации 68
3.2. Синтез схем конечных автоматов (КА) с памятью 72
3.3. Параллельное преобразование КА в ПЛИС 78
3.3.1. Параллельное преобразование КА, полученных на сетевых моделях алгоритмов 81
3.3.2. Параллельное преобразование КА для микропрограммных автоматов 88
Выводы 91
4. Выбор соединений в ПЛИС 92
4.1. Предпосылки к разработке точного алгоритма выбора соединений...92
4.2. Структура соединений 92
4.3. Математическая модель массива межсоединений 95
4.4. Последовательный комбинаторный метод выбора соединений 97
4.5. Проблемы при размещении 101
4.6. Метод выбора соединений на основе алгоритма системы различных представителей 106
4.7. Алгоритм трассировки соединений в ПЛИС 111
Выводы 116
5. Применение технологии ПЛИС при проектировании авиационных распределенных информационных систем (РИС) 117
5.1. Архитектура авиационных РИС 117
5.2. Интерфейсные модули 125
5.3. Применение методов проектирования схем в ПЛИС 127
5.3.1. Модуль А429-3-24 127
5.3.2. Модуль ABB 129
5.3.3. Модуль АКО 131
Выводы 134
Заключение 135
Литература 136
Приложение
- Управление проектированием в инструментальной среде MAX+PLUSII
- Синтез логических функций общего назначения в ПЛИС
- Параллельное преобразование КА, полученных на сетевых моделях алгоритмов
- Последовательный комбинаторный метод выбора соединений
Введение к работе
АКТУАЛЬНОСТЬ ТЕМЫ
Развитие технологии производства средств вычислительной техники влияют на развитие и совершенствование средств проектирования.
В 80-е годы технологии дискретной схемотехники допускали активное участие коллектива; разработчиков и разделение труда в процессе проектирования схем, в отладке и изготовлении на любой стадии процесса создания систем; Современные условия создания систем в принципе изменились и характеризуются высокой степенью интеграции процесса проектирования и изготовления, представляющего собой, по существу, интегрированный технологический процесс создания систем.
Если сопоставить сроки разработки и создания реального проекта с уровнем сложности 105 логических ячеек и/или Кбайт в 90-е годы ив начале 2000-х годов, то различие составляет два порядка: несколько лет в начале 90-х годов и два-три месяца в 2000 году.
В связи с ожидаемым ростом этих показателей; активизировались работы в области создания методологий проектирования систем;на кристалле. В рамках: этих систем необходимо решать как системные задачи из области "архитектуры", так и конкретные задачи проектирования, опирающиеся на существующую элементную базу.
За последнее десятилетие опробованы различные технологии. Весь накопленный опыт суммируется в современных интегрированных технологиях фирм ALTERA, XILINX, ACTEL, ATMEL, CYPRESS и еще десятка фирм, создающих системы на кристалле.
Еще одна заметная тенденция - это соединение на кристалле аналоговой и цифровой технологий. Здесь находится неограниченный резерв расширения? функциональных возможностей и интеграции специальной периферии.
Все эти ожидания и, значительный прогресс в создании информационных систем относится к интегральным технологиям создания встроенной и распределенной аппаратуры на основе программируемых логических
интегральных схем (ПЛИС).
Практическое применение САПР MAX+PLUS II; FOUNDATION и LIBERO выявило проблемы в следующих областях.
1. Методы синтеза регулярных схем.
Исследования показали, что результат применения стандартных методов и существующей библиотеки параметризированных модулей может быть улучшен - сокращением числа логических ячеек, задержек и улучшением других параметров схем в ПЛИС.
2. Реализация схем конечных автоматов в ПЛИС.
Канонические методы синтеза схем конечных автоматов (Лазарев B.F., Баранов СИ., Варшавский В.И., Соловьев В.В. и др.) разработаны преимущественно для дискретной элементной базы и заказных матричных БИС. Применение канонических методов в ПЛИС не дает оптимальных решений, так как эти методы не учитывают структуру ячеек и матрицы соединений.
3. Алгоритм размещения и трассировки.
Исследования показали, что на этапе размещения и трассировки с высокой вероятностью возникают отказы вследствие ограничений используемых в САПР алгоритмов.
Таким образом, работа, посвященная разработке методов проектирования цифровых устройств на ПЛИС, АКТУАЛЬНА и представляет научный и практический интерес,
ПРЕДМЕТОМ ИССЛЕДОВАНИЯ диссертационной работы являются математические методы, алгоритмы и их применение при проектировании! распределенных информационных систем на ПЛИС фирмы ALTERA с использованием САПР MAX+PLUS II...
ЦЕЛЬ РАБОТЫ. Целью диссертационной работы является разработка методов проектирования цифровых устройств на ПЛИС.
Для достижения этой цели решались следующие задачи. 1. Разработка методов для этапа логического проектирования на ПЛИС:
разработка методов синтеза регулярных схем;
разработка методов синтеза и преобразований конечных автоматов.
2. Разработка методов для этапа конструкторского проектирования на ПЛИС:
разработка методов размещения функций по логическим ячейкам ПЛИС;
разработка методов распределения контактов;
разработка методов трассировки соединений.
МЕТОДЫ ИССЛЕДОВАНИЯ. Методами исследования являются теория регулярных языков, теория алгоритмов, теория графов, комбинаторика и теория множеств, теория конечных автоматов, теория сетей Петри и теория программирования.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем.
1. Разработаны методы для этапа логического проектирования на ПЛИС:
методы синтеза регулярных схем в ПЛИС, которые позволяют улучшить параметры схемы;
метод алгоритмического описания ячейки ПЛИС на основе регулярных языков, который может использоваться на этапе логического синтеза;
метод преобразования конечных автоматов в систему эквивалентных параллельно работающих конечных автоматов;
метод синтеза конечных автоматов, направленный на минимизацию количества функций и применение параметризируемых модулей.
2. Разработаны методы для этапа конструкторского проектирования на ПЛИС:
математическая модель матрицы межсоединений на основе графов связности;
алгоритм выбора соединений на основе системы различных представителей;
алгоритм распределения контактов, основанный на решении задачи о назначении.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ представляют:
Прикладная библиотека параметризируемых модулей, созданная на основе разработанных методов синтеза регулярных схем.
Программа, предназначенная для расчета параметров заданной регулярной
схемы и выбора метода синтеза в зависимости от заданного вектора параметров.
Программа, выполняющая трассировку соединений на основе разработанного точного метода выбора соединений.
Разработанные методы и алгоритмы- применялась: при проектировании авиационных интерфейсных модулей^ в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76; БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов, что подтверждается актом внедрения.
ПУБЛИКАЦИИ. По материалам диссертаци и опубликовано восемь печатных работ.
АПРОБАЦИЯ РАБОТЫ; Обсуждение материалов работы производилось на XXXI научной и учебно-методической; конференции Санкт-Петербургского: государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО), ХХХІІІ научной и учебно-методической конференции СПб ГУ ИТМО и Шестой межведомственной научно-технической конференции в филиале Военно-космической Краснознаменной Академии (г. Пушкин).
ЭФФЕКТ ОТ ИСПОЛЬЗОВАНИЯ результатов данной; работы заключается в сокращении; числа; ячеек и максимальной задержки в ПЛИС при разработке распределенных информационных систем на 20-3 0% по сравнению - с методами, использующимися в САПР стандартной поставки.
ОСНОВНЫЕ ПОЛОЖЕНИЯ. ВЫНОСИМЫЕ НА ЗАЩИТУ.
Методы синтеза регулярных схем в ПЛИС.
Метод алгоритмического описания ячейки ПЛИС.
Метод преобразования конечных автоматов в ПЛИС.
Алгоритм выбора соединений.
5; Алгоритм распределения контактов.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ
Диссертация состоит из введения, пяти глав, заключения и списка литературы (53 наименования). Материал изложен на 139 страницах машинописного текста и содержит 112 рисунков и 23 таблицы.
Управление проектированием в инструментальной среде MAX+PLUSII
Система проектирования MAX+PLUS II представляет собой архитектурно-независимую среду проектирования [12]. Проектирование разделяется на этапы, которые поддерживаются разносторонними средствами автоматизации.
Независимо от реализации в конкретной ПЛИС семейства МАХ7000, технология позволяет создать и отладить корректное описание в графической и текстовой форме на основе языков описания схем (AHDL, VHDL, VERILOG) [13 -15].
Временные параметры и оценки сложности привязаны к. конкретным структурам ПЛИС, вместе с тем с определенной точностью (не менее 10%) параметры полученные при реализации схем могут совпадать с параметрами получаемыми ив других системах поддержки. Архитектуру технологии MAX+PLUS II можно показать в виде рис. 1.13.
Выделяются следующие стадии в технологии проектирования ПЛИС. 1. Перед началом проектирования, необходимо построить математическую модель. Она формируется из различных спецификаций, В частности, в качестве спецификаций используются сети Петри [23], регулярные выражения [35], микропрограммные конечные автоматы [26, 27], регулярные конечные автоматы [19] и т.д.
Основу систем проектирования составляет библиотека модулей, которые реализуют типовые схемные решения. В MAX+PLUS ІГ существует четыре типа [6, 12]: базовые элементы представляют собой простые функциональные блоки, такие как стандартная логика (AND, OR, ...) и интерфейсные примитивы (INPUT, OUTPUT,...); использование макрофункций серии 74хххх, широко распространенных в проектировании цифровых устройств. Макрофункции микросхем серий 74хххх являются прототипами стандартной серии 155, 531 и др., могут использоваться вместе с базовыми элементами и другими модулями. Достоинство их применения заключается в том, что легко осуществляется перенос существующих схем в ПЛИС для улучшения таких технических параметров как габариты и потребляемая мощность. Одним из недостатков их применения является ограниченная масштабируемость, так как увеличение разрядности должно быть кратно четырем. Анализ показывает, что, сохраняя функциональные возможности этой схемы, фирма копирует схемы, разработанные в ТТЛ технологиях 70-х годов; использование библиотеки параметризированных модулей LPM (Library of Parameterized Modules). В отличие от макрофункций специально разработанные для ПЛИС универсальные модули LPM легко масштабируются для любой разрядности и обладают свойством параметризации, которое применяется при специализации LPM в конкретных применениях; в работе исследуется подход к созданию прикладной библиотеки параметризированных модулей. Опираясь на средства, используемые в МАХ+PLUS II для реализации универсальных модулей LPM, можно создать специализированную библиотеку параметризированных модулей, обеспечивающих более эффективные схемные решения.
Базовые элементы, макрофункции и параметризированные модули входят в стандартную библиотеку, а специализированная библиотека относится к пользовательским:
Кроме библиотечных элементов, САПР предоставляет возможность описания управляющих автоматов и синтезирует управляющие классические модели автоматов Мили и Мура.
С помощью библиотек и управляющих автоматов строится описание проекта. В него могут входить схемы управления, память данных, регистры и интерфейсные схемы, описанные на языке САПР. 2. Построенная математическая модель проекта подвергается логическому синтезу, вследствие чего логика преобразуется в элементы ПЛИС, такие как макроячейки, расширители, память и т.д. По результатам синтеза строится логическая модель, и разработчик может произвести анализ полученных выражений и в случае необходимости произвести их корректировку. 3. После получения логической модели она размещается в конкретную ПЛИС, получая таким образом, модель размещения. Этот этап выполняется с помощью алгоритмов размещения. Если это не удается, то выдается ошибка размещения. Разработчик должен проанализировать модель и принять экспертное решение по устранению этой проблемы. 4. После удачного размещения, происходит трассировка проекта и построение модели трассировки. Здесь также может быть выдано сообщение об ошибке. Недостатком инструмента САПР является отсутствие полезной информации для устранения ошибок трассировки и размещения. По существу, САПР сообщает, что не может выполнить размещение или трассировку. 5. Если трассировка и размещение прошли успешно, то выполняется моделирование проекта. Существует три типа моделирования: временное (рассчитываются временные задержки); функциональное (проверяется правильность функционирования); работа в реальной среде (проект загружается в реальное устройство) или JTAG-тестирование.
По результатам моделирования можно сделать вывод о соответствии модели проекта ПЛИС исходной математической модели.
В случае ошибочной верификации, разработчику необходимо скорректировать модель проекта ПЛИС.
Таким образом, в Интегрированной Технологии Проектирования параллельно существуют три процесса: проектирование при участии разработчика (спецификации, модели, алгоритмы, оценка результата и коррекция); работа инструментальной системы САПР (формирование математических описаний, конструкторских и технологических документов); реализация и отладка (согласование документов, загрузка ПЛИС и ее отладка с имитатором внешней среды).
Синтез логических функций общего назначения в ПЛИС
Функциями общего назначения будем называть произвольные логические выражения, реализуемые комбинационными схемами. Основная проблема при формировании функций для логических ячеек — ограниченное число конъюнктивных термов. Для реализации логики проекта цифровой схемы в ПЛИС все функции приводятся к системе логических выражений в дизъюнктивной нормальной форме (ДНФ). Реализация логических выражений в ПЛИС семейства МАХ происходит в матрице распределения термов. Для объединения термов формируются функции управления логической ячейки. Локальный логический массив в ячейке содержит не более NKT термов. Для расширения числа термов формируются параллельные (РЕ) и последовательные расширители (SE) из конъюнктивных термов (СТ). Параллельные расширители образуют цепочку из двух, трех или четырех последовательных ячеек (рис. 2.9). На рис. 2.10 показана структурная схема одной ячейки (LCELL). Логическая ячейка может быть комбинационной или регистровой с памятью. Если ячейка комбинационная, то матрица распределения термов формирует только функцию данных (F).
Для ее формирования можно использовать NKT конъюнктивных термов (СТ). Для семейства МАХ7000 NKT=5. Например, задано, выражение: глобальным сигналом. Если же используется не глобальный сигнал для синхронизации, то необходима функция CLK_ENA, которая займет один терм СТ. Для реализации функции F останется только четыре терма. Число термов для функции F может стать меньше, если необходимы функции PRN и CLR. В самом худшем варианте может остаться всего 2 терма. Предлагается описание всего множества функций, реализуемых ПЛИС, содержащей N логических ячеек в связанных матрицах LA и PTSM [45]. Программируемые функции управления ячейками могут быть записаны в виде системы уравнений (5): функция синхронизации/разрешения, F - функция данных, Sk = {Т ь Т 2, Т 3, Т 4} - множество конъюнктивных термов, Sq = {Т з, Т2 ..., TN5} - множество конъюнктивных термов расширения, к 1, N - число логических ячеек в блоке, Т - конъюнктивный терм входных сигналов из массива межсоединений (6). При этом: где " " обозначает прямое или инверсное значение переменной, М - число сигналов, поступающих в блок из массива межсоединений, т обозначает jeSq последовательное применение расширителей с инверсией, Так, при Г, & Тг используется один расширитель, при Тх & Тг & Г3 - два расширителя, при Тх & Т2 & Тъ & Г4 - три расширителя и т.д. Расширители позволяет сократить число термов, используемых для реализации функций. Например (7): где D - дизъюнктивный терм. Если не использовать расширители, то для реализации соответствующей функции необходимо п термов вместо одного. Количество термов расширения в ПЛИС не более N. Можно привести все выражения подобного вида к формуле, содержащей только символы TVLD. Система выражений, заменяющих формулы расширителей с инверсиями, имеет вид:
Таким образом, расширители позволяют выполнить в ПЛИС сложные скобочные формулы с расширением как по И, так и по ИЛИ. Систему уравнений функций управления можно привести к следующим рекуррентным регулярным выражениям (8): Здесь под знаком выбираются п-\ термов Т из общего их числа и, F — рекуррентная функция, причем уровень рекурсии зависит от уровня расширителя (9). Сформулированные регулярные выражения в языке с алфавитом 2={Т, D, v} определяют правила построения правильных формул, реализуемых ПЛИС. Все эти формулы назовем регулярным классом. Возможность реализации всякой формулы проверяется распознавателем выражений в языке L. Распознаватель слов языка регулярных выражений может быть построен в виде конечного автомата [32 - 34], для которого существует эффективная программа, что позволяет автоматизировать процесс распознавания. Автомат распознавания регулярного выражения w показан на рис. 2.11. В процессе распознавания фиксируются состояния автомата, и соответствующие ячейки загружаются термами. После того как очередная формула выполнена, корректируется система регулярных выражений. Таким образом, последовательно заполняются и контролируются ресурсы ПЛИС. Конечный результат реализации системы функций не зависит от их последовательности и ограничивается только ресурсами ПЛИС: максимальным количеством расширителей, суммарным количеством переменных в термах, количеством запоминающих ячеек, шириной коммутационных каналов. Рассмотрим следующие методы синтеза комбинационных выражений [46]: 1. Метод дополнительных ячеек (МДЯ). 2. Метод расширителей (MP). 3. Метод "исключающего ИЛИ" (МИИ). 4. Метод параллельных расширителей (МИР). 5. Метод частичных расширителей (МЧР).
Логическую ячейку можно описать как множество термов L = {Т, Е}. Множество Т = {a,b,c,d} и Е = {е}. Т - это термы общего назначения, а Е -расширитель. Если для оценки сложности взять блок из 16 логических ячеек, то полное множество будет иметь следующий вид: L = {64,16}, а Т={16,16,16,16}. Вводится оценка а в виде вектора параметров, которые размещаются в порядке где NL - число занятых ячеек, NT - число занятых термов, NE - число занятых расширителей, t — задержка сигнала. Эти параметры можно получить путем компиляции заданного выражения. Для исследования методов выбирается выражение (И), записанное на языке компилятора MAX+PLUS II и содержащее 6 термов, что превосходит возможности одной ячейки [46].
Параллельное преобразование КА, полученных на сетевых моделях алгоритмов
Применение ПЛИС с увеличением степени интеграции и повышением быстродействия рассматривается как один из альтернативных способов реализации алгоритмов в технологии сопряженного проектирования проблемно-ориентированных цифровых систем. В распределенных информационных системах алгоритмы управления интерфейсами и первичной обработки данных измерений также вносятся в ПЛИС.
Наиболее, популярным является применение ПЛИС для реализации: регулярных (с высокой степенью однородности) алгоритмов цифровой обработки сигналов, где ПЛИС конкурируют с программным исполнением в процессорах цифровой обработки сигналов.
Отношения цена/производительность, габариты и потребляемая мощность превосходят соответствующие показатели для микропроцессоров, однако применение ПЛИС оправдано более высокой скоростью параллельной обработкой данных.
Опираясь на тенденцию дальнейшего повышения степени интеграции и снижения отношения; цена/производительность, можно прогнозировать экономически оправданное применение ПЛИС и при реализации других классов алгоритмов. В- частности, алгоритмы управления и: обработки данных выполняются независимо ив комплексе с микропроцессорными средствами общего назначения, обеспечивающими, главным образом, управление памятью данных и сопряжение со стандартными интерфейсами.
Рассматривая конкретные задачи реализации алгоритмов в ПЛИС на уровне практического применения в РИС на сегодняшний день (разд. 1), видим, что алгоритмы в основном относятся, к согласованию интерфейсов и управлению быстрой памятью. Таким образом, задачи не столь глобальны как в System С [25], которая предполагает реализацию в ПЛИС алгоритмов широкого класса непосредственно с языка C++, или в обзоре моделей для встроенных систем [24].
При этом можно отказаться от столь же глобальных методов перехода к схемам и остановиться на применении конечных автоматов (КА). Достаточно широкий обзор приложений КА к реализации управляющих алгоритмов на программном уровне (Switch-технология) приведен в [21], Аппаратные реализации рассматривались, главным образом, применительно к схемам на дискретных элементах [26 - 28] или к ПЛИС низкой степени интеграции [2]. Основные результаты получены для специального класса — управляющих микропрограммных алгоритмов. В разд. 2 настоящей работы, показаны новые возможности применения КА для реализации алгоритмов [2, 26], определяемых регулярными языками при синтезе регулярных схем в ПЛИС. Ниже приведена диаграмма (рис. 3.1), в которой объединены рассмотренные в обзорах [2, 20, 21, 25, 26] приложения алгоритмов при реализации в ПЛИС.
Исходные формализованные описания алгоритмов опираются на формальные языки, для которых существуют программные реализации, что позволяет получить необходимую надежность спецификации алгоритмов для ПЛИС.
Языки позволяют также привести условную классификацию алгоритмов, в которых они применяются.
Приведем краткую характеристику представления, алгоритмов при их реализации. 1. Языки моделирования аппаратуры предназначены для описания принципа работы цифровых схем с микропрограммным управлением, например, язык DDL [ЗІ]. Языки VHDL, VERILOG и AHDL [13, 14, 15] используются в проектировании схем цифровых схем. Языки этого класса включают средства описания регулярных схем и алгоритмов конечными автоматами. 2. Расширенный язык С для микроконтроллеров, включает средства для работы с битами данных, позволяет эффективно выполнять алгоритмы логического управления. 3. Регулярные языки используются для определения и реализации алгоритмов редактирования и преобразования текстов в виде программных моделей КА. Эти языки использовались в работах Глушкова В.М. [19] и Портнова Д. [29] для описания и синтеза алгоритмов, в комбинационных схемах. В настоящее время применение этих методов не актуально в связи с унификацией элементной базы и применением стандартных библиотек: программируемых управляемых регулярных схем в ПЛИС (разд. 2). 4. Языки описания работы дискретных систем позволяют описывать последовательные, конвейерные и параллельные алгоритмы. Математическими: моделями сложных процессов управления дискретными промышленными системами обычно являются сети Петри [20, 21, 22]. Наиболее продвинутые методы программной реализации рассмотрены в работах Юдицкого С.А.[23] и Шалыто А.А.[21]. В них рассматривается интерпретация сетей Петри конечными автоматами, полученными преобразованиями сетей в граф операций. Предлагались проблемно-ориентированные языки описания процессов, основанные на этих моделях - ЯРУС, ЯУП и др. [23] В настоящее время в промышленный стандарт языков описания работы дискретных систем ШЕЕ 1131 входит язык "ГРАФСЕТ" (de Graphe de Commande des Etapes et Transitions), использующий эту модель.
Последовательный комбинаторный метод выбора соединений
Теорема Холла [17] содержит необходимые и достаточные условия существования СРП.
Пусть I конечное множество индексов, 1={1, 2, ..., п}, и S; для каждого ї є I — подмножество некоторого множества S. Необходимым и достаточным условием существования различных представителей х,, і = 1, ..., п, х, є S;, х, Xj при і j, является условие С: для каждого к=1, ..., пи каждой последовательности к различных индексов і, ..., ik в совокупности всех элементов подмножеств Sjb -..., Sjk содержится не менее к различных элементов.
Алгоритм выбора СРП, сформулированный Холлом, в виде доказательства теоремы в теоретико-множественной интерпретации, не приспособлен для машинных вычислений. Алгоритмические методы решения этой задачи, связанные с более общей задачей о назначениях, рассматриваются в [17, 18] и включают значительный перебор.
Ниже предлагается эффективная процедура поиска возможной замены элементов в случае, если на очередном шаге все элементы подмножества оказались в СРП.
Все элементы этого множества, образуют Fo фронт волны. Следующий Ft фронт, состоит из всех элементов, достигаемых заменой соответствующих элементов СРП элементами подмножеств Si. Если не найдется ни одного нового элемента, не входящего в СРП, то строится следующий фронт F2 и т.д.
Пусть на К-ом шаге найден свободный для замены элемент, тогда трасса, проходящая через все К-1, К-2, ..., 0-фронты, определяет допустимую последовательную замену элементов в СРП. Для выбора этой трассы строится матрица, в которой отмечаются элементы множеств Si, входящие в соответствующие фронты Fj, где j=k,..0.
В рассмотренной выше таблице для S? F0={1,3}, F={6,7}, на последнем шаге найдены свободные для замены элементы и, начиная с любого из них, строится трасса.
Метод эффективен, так как используются конкретные шаги, в которых учитывается распределение соединений в ограниченном поле коммутации. Выбор всегда завершается за конечное число шагов — при достижении конечной точки, либо подтверждает факт отсутствия какой-либо трассы, соединяющей указанные точки.
Предположим, что не существует перестановок номеррв элементов, тогда не существует и пути, соединений парных: перестановок (строка-столбец), образующих цепочку, соединяющую К-ый не выбранный элемент и 1 ый элемент, который может быть использован для выбора S. Тогда не существует и подмножеств, образующих последовательность не пустых фронтов.
В соответствии с этим методом предлагается универсальный машинно-ориентированный алгоритм выбора (рис. 4.19).
Исходные данные представлены в виде массива М. Где строки; это представители, а столбцы —возможные места размещения. Массив состоит из 0, 1 и -1. Единица говорит о том, что представитель (строка) может размещаться на данном месте (столбце). Ноль - не может. Минус единица (-1) - столбец занят.
Поиск осуществляется последовательно для каждой строки. После выбора строки проверяется, есть, ли для этого представителя место. Место ищется из множества столбцов, помеченных 1 и не занятых другими представителями. Если такой столбец найден, то он помечается занятым. При этом ему присваивается минус единица (-1). После этого переходим к следующему представителю.
Если место не найдено, то все возможные варианты-столбцы заняты, то происходит дальнейший поиск. Для этого используется вспомогательный массив Ml. В него копируется текущая строка, а в массив координат XY заносятся координаты (строка-столбец) единиц строки. Переменной Index присваивается значение I. Эта переменная показывает уровень вложенности поиска.
Далее осуществляется поиск по каждому столбцу из XY значения (-1) в массиве М. Найденной координате в массиве Ml присваивается значение следующего уровня вложенности. Эти координаты тоже заносятся в массив координат.
После этого идет поиск по строкам массива М значений 1. Найденным координатам присваиваются значения следующего уровня вложенности.
На текущем уровне вложенности проверяются, заняты ли найденные столбцы. Если столбец занят, то поиск перестановки номеров (столбец-колонка) продолжается. Если столбец свободен, то данная координата помечается занятой (-1) и происходит обратный проход по уровням вложенности, до нулевого уровня, с соответствующими заменами 1 на (—1) и наоборот.
Пример работы алгоритма PIA для ПЛИС EPM7032LC44 можно рассматривать как простейший случай одномерной коммутации, где ячейки и МЧК лежат в одной плоскости и рассматриваются только параллельные схемы соединений.
В случае двух и трехмерной коммутации рассматриваются несколько последовательно соединенных МЧК (например, PIA ПЛИС FLEX10K обеспечивают двумерную коммутацию, которую можно представить в следующем упрощенном виде на рис. 4.20).
Контакты X ячеек одного слоя коммутируются через МЧК с множеством промежуточных контактов Y, которые через другую, последовательную МЧК переключаются на контакты Z и подключаются к ячейкам другого слоя.
Коммутация в этом случае сводится к построению двух связанных по входам-выходам двудольных графов и построением СРП для графов (X,Y) и (Y,Z).
