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

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления им. В. А. Трапезникова

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

УВАРОВ Сергей Сергеевич

ПРОЕКТИРОВАНИЕ РЕКОНФИГУРИРУЕМЫХ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ НА ШШС С РЕЗЕРВИРОВАНИЕМ НА УРОВНЕ ЯЧЕЕК

Специальность 05 13.15 -Вычислительные машины и системы

АВТОРЕФЕРАТ

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

ООЗ 173482

Москва - 2007

003173482

Работа выполнена в Институте проблем управления.

Научный руководитель - д т. н. Каравай М. Ф.

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

д т. н. Лобанов А. В. д т. н. Ведешенков В А.

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

ФГУПНИИТП (Научно-исследовательский институт точных приборов

г Москва)

Защита состоится «¡Л » . 2007 г. в II. час на

заседании Диссертационного совета Д 002 226 03 Института проблем управления им. В А Трапезникова РАН, Москва, ул. Профсоюзная, 65 Телефон совета1 334-93-29

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разослан « ».....2007 г

Ученый секретарь Диссертационного совета д. т. н.

Юркевич

Евгений

Владимирович

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

Актуальность_проблемы Стремительное развитие

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

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

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

(

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

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

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

' Основу ПЛИС составляют конфигурируемые логические блоки (которые далее для краткости будут называться «ячейками») Связи между ячейками могут достаточно гибко изменяться

алгоритма поиска. При построении алгоритма декомпозиции К— отказоустойчивой системы применен принцип Дирихле, что позволило задавать максимально возможные размеры блоков Применение САПР ХИШХ /БЕ 91 показало возможность практической реализации отказоустойчивых систем, соответствующих предлагаемой методике

Научная новизна работы. В работе предложен новый подход к проектированию отказоустойчивых систем на ПЛИС, основанный на представлении задачи декомпозиции системы и парирования отказов как специального случая задачи упаковки Подобный подход к решению задачи отказоустойчивости стал возможным благодаря применению конвейеризации, которая в данном случае позволяет решить проблему изменения задержек распространения сигналов при реконфигурации системы Применение конвейеризации так же может считаться новым подходом к проектированию отказоустойчивых систем на ПЛИС Предложены алгоритмы, накладывающие ограничения на размеры блоков, таким образом, что для произвольного набора блоков, соответствующего алгоритмам, ЫР-полная задача упаковки сводится к задаче, трудоемкость которой линейно зависит от числа блоков Данные алгоритмы позволяют декомпозировать систему на минимальное число блоков Предложенные алгоритмы так же позволяют создать отказоустойчивую систему с минимальной избыточностью Для общего случая ЫР-полной задачи упаковки предложены алгоритмы, позволяющие существенно сократить трудоемкость ее решения Сформулирована новая подзадача упаковки — «отказоустойчивая упаковка», которая может считаться модельным представлением целого ряда практически актуальных задач Применен принцип Дирихле для определения максимально возможных размеров блоков для /^-отказоустойчивой системы

Обоснованность научных результатов, выводов и рекомендаций

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

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

1 сохранение длин критических связей при реконфигурации,

2 минимальная избыточность системы,

3. минимальное число блоков для данного коэффициента заполнения ПЛИС,

4 возможность создания системы, устойчивой к множественным отказам,

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

6 рассмотрение отказов в функциональных блоках, отличных от обычных ячеек (CLB)

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

Положения выносимые на защиту:

1 Сформулированы основные принципы проектирования отказоустойчивых систем на ПЛИС.

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

3. Задача создания отказоустойчивой системы на ПЛИС сформулирована как особый случай задачи упаковки

4 Предложены алгоритмы формирования размеров блоков, позволяющие свести NP-полную задачу двумерной упаковки к частному случаю, трудоемкость которого линейно зависит от размерности задачи (числа блоков)

5 Предложены алгоритмы, позволяющие формировать блоки максимального размера для 1-й К-отказоустойчивых систем

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

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

Реализация результатов работы подтверждена соответствующим актом о внедрении

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

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

Апробация работы. Результаты работы докладывались на

1. Международной научно-технической конференции «Dependable Systems, Services and Technologies» («DeSSerT») в 2007 (г Кировоград, Украина)

По смежным проблемам проектирования систем на ПЛИС делались доклады на

2. Международной научно-технической конференции «Digital Signal

Processing and Applications» («DSPА») в 2007 (г Москва) 3 Международной научно-технической конференции «Digital Signal Processing and Applications» («DSPA») в 2006 (г Москва) Публикации. По материалам диссертационной работы имеется две публикации Дополнительно имеется две публикации, посвященные смежным проблемам проектирования систем на ПЛИС

Структура и объем работы. Работа состоит из введения, пяти глав, заключения, списка литературы и приложений Основной текст изложен на 116 страницах и содержит 29 рисунков и 2 таблицы Список литературы содержит 64 библиографических наименования

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

Во введении обосновывается актуальность и формулируется цель диссертационной работы

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

1. Большая избыточность (для парирования отказа одной ячейки требуется резервирование большого числа ячеек)

2. Не распространение отказоустойчивости на трассировочные ресурсы ПЛИС

3. Негарантированное восстановление системы даже при наличии резервных ресурсов

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

5 Отсутствие общего универсального подхода к решению задачи отказоустойчивости

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

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

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

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

1. Задержки распространения сигналов в комбинационных схемах не должны изменяться в результате реконфигурации.

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

3 Число резервных ячеек должно быть по возможности минимальным

4 Алгоритм реконфигурации не должен быть вычислительно трудоемким

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

6 Методика должна быть гибкой и масштабируемой

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

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

На основании приведенных требований к методике проектирования в рамках рассматриваемой модели формулируются следующие основные

принципы проектирования отказоустойчивых систем на ПЛИС, принятые за основу в данном исследовании*

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

2 Для того чтобы изменение связей между блоками в результате реконфигурации не влияло на работоспособность системы, сигнальные входы и выходы блоков должны быть синхронными, т е, представлять собой входы и выходы Б-триггеров, работающих по одному фронту Это позволит допустить изменения задержек на внешних связях в интервале (»О,« Т), где Т - период тактового сигнала

3 Размеры блоков должны быть такими, чтобы при отказе произвольной ячейки или связи существовало размещение блоков, при котором отказавший ресурс не будет задействован

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

5 Размеры блоков должны быть как можно больше, чтобы можно было наиболее эффективно использовать трассировочные ресурсы ПЛИС и создавать крупные монолитные элементы системы

6 Размер резервной области (количество незадействованных ячеек) должен быть как можно меньше.

7 Размеры блоков должны задаваться гибко, для того чтобы наиболее точно соответствовать размерам комбинационных схем и размерам матрицы ПЛИС для каждой конкретной системы

Основные принципы проектирования, позволяют рассматривать задачу формирования набора блоков и задачу парирования отказов как задачи раскроя и упаковки Рассматриваемая задача упаковки (раскроя) отличается от классической задачи упаковки тем, что при любом размещении отказа должно существовать размещение блоков, при котором отказавшая ячейка не покрыта ни одним из размещенных блоков Алгоритм реконфигурации должен представлять собой алгоритм упаковки с ограничением, заданным размещением отказа Формулируется задача «отказоустойчивой упаковки», состоящая из двух подзадач

1 Определение как можно менее жестких ограничений, накладываемых на допустимые линейные размеры блоков, таких чтобы при любом расположении отказа существовало размещение блоков, в котором область отказа не покрыта ни одним из блоков

2 Нахождение размещения заданного набора блоков, для произвольного расположения отказа, при котором область отказа не покрыта ни одним из блоков

Набор блоков, соответствующий указанным требованиям, предложено называть «отказоустойчивым набором (системой)» Общий случай задачи упаковки представляет собой МР-полную задачу. Далее в главах 3,4 рассматриваются алгоритмы формирования размеров блоков, позволяющие свести общий случай №>-полной задачи к частному случаю, для которого трудоемкость линейно зависит от размерности (числа блоков) В главе 5 рассматриваются методы оптимального решения общего случая задачи упаковки и отказоустойчивой упаковки

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

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

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

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

3 Размещение нескольких задач для (параллельной обработки) в многопроцессорной системе, имеющей архитектуру решетки, при условии, что один или несколько произвольных процессоров могут быть неработоспособны В качестве примера задачи 2 приводится следующая проблема. Предприятие «А» эксплуатирует некоторое количество однотипных устройств обслуживания (например, станков) Многократно выполняется цикл, состоящий из N различных работ, каждая из которых требует непрерывного использования некоторого количества устройств обслуживания в течение некоторого времени. Цикл работ должен выполняться за время Т После каждого цикла выполняется плановая проверка состояния устройств обслуживания, при которой часто обнаруживается, что одно из них требует проведения сервисных работ в ближайшее время Т. Сервис осуществляет организация «Б», которая обязуется по требованию «А» назначить и провести сервисные работы не позднее времени Т (при этом само время выполнения сервисных работ, в течении которого устройство не эксплуатируется, намного меньше Т, а время начала работ «Б» сообщает заранее) Таким образом, перед началом цикла «А» должно решать задачу составления расписания, имея дополнительное ограничение, которое заключается в том, что одно из

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

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

2 На основании приведенных требований сформулированы основные принципы проектирования

3 Задача проектирования реконфигурируемых отказоустойчивых систем на ПЛИС представлена как особый случай задачи упаковки

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

В третьей главе рассматриваются одиночные отказы ячеек Предлагается решение задачи создания отказоустойчивой системы путем разбиения матрицы ячеек на блоки прямоугольной формы Реконфигурация системы представляет собой переразмещение блоков в матрице ПЛИС с учетом отказавшей ячейки Для того чтобы набор блоков задавал отказоустойчивую систему, блоки должны иметь вполне определенные размеры Так же очевидно, что для эффективной декомпозиции и размещения по блокам различных систем размеры блоков должны задаваться гибко Наиболее жесткие требования к размерам блоков возникают в связи с реализацией таких элементов, как счетчики, умножители и т п, поскольку эти элементы требуют фиксированного относительного размещения ячеек, в которых они реализованы (ячейки должны быть выстроены «в колонку»)

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

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

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

2 Выбирается (произвольно) направление сечения (вертикаль/горизонталь)

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

не должен превышать половины линейного размера резервной области

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

5 Размерам новой резервной области присваиваются значения, соответствующие размерам области, не содержащей блоков, и к новой резервной области применяется последовательность действий, начиная с 2 Новые блоки формируются до тех пор, пока не будет получен набор блоков, в которые можно поместить все элементы системы

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

Важными свойствами предложенного алгоритма являются

1 возможность на каждом шаге формировать блоки максимального размера,

2 при малом числе блоков, суммарное количество ячеек всех блоков близко к общему числу ячеек матрицы ПЛИС;

3 размер резервной области определяется размером наименьшего блока

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

ячеек Р N = , где |У| - ближайшее целое число, не меньшее х

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

а

6

Рис. 1.

Пример разбиение матрицы ПЛИС на блоки а - обычная система, содержащая произвольно расположенные незадействованные ячейки б - отказоустойчивая система (серым цветом обозначены свободные ячейки)

1. Определение номера блока, содержащего отказ.

2. Перестановка данного блока с областью, содержащей резервную область и все остальные блоки с большими номерами.

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

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

координатам могут обладать два различных блока (например, на Рис 3 блок 1 имеет наименьшую высоту, а блок 2 - наименьшую ширину) Принцип действия обобщенного алгоритма разбиения заключается в том, что на каждом шаге разбиения при определении максимального линейного размера блока учитываются перестановки не только с резервной областью (и блоками с большими номерами, которые могут быть сформированы в резервной области на последующих шагах), но и с ранее сформированными блоками

На Рис 3 приведен пример обобщенного разбиения, и показаны размещения набора блоков для четырех различных расположений отказавшей ячейки

р Р(%) N Количество

(число реконфигу-

блоков) раций

1/2 50% 1 1

3/4 75% 2 4

7/8 87,5% 3 8

15/16 93,8% 4 16

31/32 96,9% 5 32

63/64 98,4% 6 64

127/128 99,2% 7 128

Таблица I

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

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

1. Для каждого нового блока определяются все блоки, с которыми возможна перестановка по каждой координате.

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

■ в3 Шаг 1 В3 ■

в4 В4 в2

В1 5'

в1 ...•:,. .г.;

Шаг 2

в4 ■ 1

в1 Шаг 3 В4 В2

в1 в3 В' В3

Рис.2.

Пример поиска работоспособной конфигурации (черным цветом обозначена отказавшая ячейка, серым - резервная область)

3. Для каждой такой задачи делается перенумерация отрезков в

порядке убывания длины.

4. Показано, что для «одномерной отказоустойчивости» достаточно, чтобы для каждого отрезка выполнялось условие: 1 к

(*) 1к+] <— где /'— длина /-го отрезка (нумерация в

2 ¡=1

порядке убывания длины), а Ь - линейный размер матрицы. Таким образом, задача определения максимального линейного размера по каждой координате сводится к определению наименьшего допустимого (в соответствии с (*)) индекса /-для вновь формируемого блока (само ограничение определяется из условия (*))•

4 5

" 5

6 7

Рис. 3.

Пример обобщенного разбиения (черным цветом обозначена отказавшая ячейка)

Сформулирован простой алгоритм «одномерной реконфигурации». Обобщенный алгоритм реконфигурации состоит из следующих процедур:

3

л 5

6 7 ■

ч 3

(и

1 Определение одномерного размещения отрезков с учетом расположения отказа по (каждой координате отдельно).

2 Цикл перестановок блоков по координате X, если их размещение по этой координате не соответствует найденному размещению отрезков.

3. Цикл перестановок блоков по координате У, если их размещение по этой координате не соответствует найденному размещению отрезков

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

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

На рис 4 показан полный набор реконфигураций для двух различных разбиений системы на 3 блока Этот рисунок показывает изменения связей при всевозможных перестановках блоков

Блокам присваиваются номера, начиная с «1» в порядке уменьшения их размера Для общности полагается, что все буферы ввода/вывода виртуально относятся к блоку с номером «1» Вводится понятие длины связи Ь, между двумя блоками с номерами к, и к2, которая определяется следующим образом-Ь = \к,-к2\

Например, блоки 1 и 2 соединены связями длиной 1, блоки 2 и 4 -связями длиной 2 и тд, блок 1 соединяется с буферами ввода/вывода связями длины 0, блок 2 с буферами соединяется связями дины 1 и т д На Рис 4 видно, что блок 1 имеет два возможных расположения в матрице ПЛИС, блок 2 - четыре и т д

Из рис 4 так же понятно, что блоки с номерами, отличающимися на 1, могут иметь 4 различных взаимных расположения (один относительно другого) Каждое взаимное расположение порождает соответствующую трассировку логических связей Таким образом, для всех возможных реконфигураций логическая связь длиньГ 1 требует резервирования 4 различных маршрутов, для связей длиной 2 требуется 8 резервных маршрутов, для связей длиной 3-16 резервных маршрутов. Показано, что для связи длины Ь требуется резервирование 2</+1) маршрутов Те же рассуждения применимы и к связям блоков с буферами ввода/вывода Под

связью длины «О» подразумевается только лишь связь между блоком 1 и буферами ввода/вывода (к внутренним связям блоков введенное выше понятие длины не применяется)

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

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

В конце 3-й главы на основании приведенных результатов делаются следующие выводы

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

2 Число блоков в системе должно быть минимальным для минимизации числа резервных маршрутов связей между блоками и минимизации полного набора реконфигураций (различных вариантов размещения блоков).

3 Предложенная методика может быть обобщена на дополнительные функциональные узлы ПЛИС.

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

В четвертой главе вначале предлагается алгоритм разбиения матрицы ячеек на блоки, позволяющий создать систему, устойчивую к двум отказам. Алгоритм основан на том, что если разделить матрицу на 3 равные области, то при любом расположении двух отказов хотя бы одна область не будет содержать ни одного отказа Можно полагать, что первая из трех областей никогда не будет содержать отказов, вторая может содержать не более одного отказа, а третья - не более двух отказов Таким образом, первая область представляет собой обычный блок, вторая — 1-отказоустойчивую подсистему, а третья - 2-отказоустойчивую подсистему В случае если расположение отказов не соответствует предполагаемому,

б)

Рис. 4. Полный набор реконфигураций для трех блоков

а) разбиение по одной координате

б) разбиение по двум координатам (черным цветом обозначены ячейки, связанные с

ячейками других блоков, штриховкой -резервная область)

области меняются местами. 1-отказоустойчивая подсистема может быть создана на основании применения алгоритма разбиения гл. 3. 2-отказоустойчивая подсистема создается путем применения только что приведенных рассуждений к соответствующей области матрицы ячеек. Пример 2-отказоустойчивой системы приведен на Рис. 5. Поскольку при дальнейшем разбиении возникает несколько свободных областей, в которых можно формировать новый блок, предлагается простое разрешающее правило, которое заключается в том, что выбирается область, в которой может быть сформирован блок наибольшего размера.

Для определения максимально допустимых размеров блоков для К-отказоустойчивых систем применяется принцип Дирихле, который в

данном контексте можно сформулировать следующим образом «Если в системе предполагается не более К отказов и система декомпозирована на К +1 подсистему, то следует полагать, что при любом расположении отказов будет существовать хотя бы одна подсистема, не содержащая отказов» На основании принципа Дирихле утверждается, что К—

¿г

отказоустойчивая система может содержать не боле А = — подсистем

п _

способных парировать п<К отказов ([*] - ближайшее целое число, не большее х) Здесь подразумевается, что в случае возникновения в какой-либо подсистеме большего числа отказов, чем она способна парировать, найдется подсистема, способная парировать данное число отказов, и в результате реконфигурации эти две подсистемы поменяются местами Например, если необходимо создать 10-отказоустойчивую систему, то на основании данного утверждения получаем, что достаточно декомпозировать систему на одиннадцать подсистем, степени отказоустойчивости которых в порядке убывания 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 0

При получении данного ряда степеней отказоустойчивости подсистем подразумевается, что «-отказоустойчивыми подсистемами являются все подсистемы, способные парировать п и более отказов Следует отметить, что любая «-отказоустойчивая подсистема в данном случае может быть заменена резервной областью (те., например, 10-отказоустойчивой подсистемы может не быть, а вместо этого, соответствующая область может быть резервной)

Требование равенства линейных размеров областей размещения подсистем для каждого шага разбиения обобщается на требование того, чтобы область, содержащая подсистему с большей степенью отказоустойчивости, имела не меньшие линейные размеры, чем область размещения подсистемы с меньшей степенью отказоустойчивости Доказывается, что любая система, удовлетворяющая сформулированным требованиям, является /¿-отказоустойчивой (т е. при произвольном расположении К отказов существует такое размещение подсистем, при котором число отказов в каждой подсистеме не превосходит ее степени отказоустойчивости)

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

1 При инициализации вся матрица ячеек считается областью размещения /¿-отказоустойчивой подсистемы.

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

определяется как отношение площади области размещения подсистемы к степени отказоустойчивости подсистемы + I.

О отказов 1 отказ 2 отказа

I I

I I

Рис. 5.

Пример 2-птказоустойчшой подсистемы

О отказов

I отказ

О отказов

2 отказа

3. Делается разбиение выбранной области. Формируется новый блок и новые области размещения подсистем.

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

5. Если суммарная площадь блоков меньше требуемой для размещения системы площади (числа ячеек), то применительно к новому множеству областей размещения подсистем выполняется последовательность действий, начиная с 2.

Приводится вычислительно эффективный алгоритм реконфигурации для ЛГ—отказоустойчивых систем. Алгоритм реконфигурации К— отказоустойчивых систем строится на основе вспомогательного алгоритма одномерной реконфигурации Вспомогательный алгоритм реконфигурации представляет собой перестановку отрезков, соответствующих линейным размерам подсистем, размещенных в областях, полученных на некотором шаге разбиения. Принцип действия вспомогательного алгоритма заключается в последовательной перестановке отрезков, начиная с отрезков, соответствующих подсистемам с наименьшей степенью отказоустойчивости В результате перестановок достигается то, что число отказов в каждой подсистеме (отрезке) не превосходит степени ее отказоустойчивости Алгоритм реконфигурации ^-отказоустойчивых систем представляет собой последовательное применение

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

В виде трехмерного графика приводится оценка зависимости коэффициента заполнения Р от числа блоков N от степени отказоустойчивости К системы (Рис 6).

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

1 Предложенные алгоритмы являются обобщением алгоритмов разбиения и реконфигурации для 1-отказоустойчивой системы

2 Возможность такого обобщения свидетельствует о правильности основных принципов проектирования, предложенных во второй главе

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

4 Оценка взаимозависимости числа блоков, степени отказоустойчивости и коэффициента заполнения системы показывает, что система со слишком высокой степенью отказоустойчивости оказывается малоэффективной. Это вполне естественно и не может считаться недостатком, поскольку большое значение К свидетельствует о том, что ожидается очень интенсивный поток отказов, что в свою очередь является признаком общесистемной ошибки, допущенной при проектировании устройства

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

сводится к многократному решению общего случая задачи двумерной упаковки Отказавшая ячейка моделируется жестко размещенным блоком единичного размера, и для каждого размещения такого блока ищется размещение набора блоков. Данная задача является NP-полной Рассматриваются методы решения таких задач Основой решения задач такого типа является алгоритм с возвратами (backtracking algorithm) Принцип работы одного из таких алгоритмов заключается в том, что делается попытка последовательно упаковать все блоки, начиная с больших Вначале берется первый блок, и предпринимается попытка расположить его в первую попавшуюся ячейку при этом перебор делается по строкам (те сперва проверяются все ячейки первой строки, затем второй строки и т.д., а под «расположением блока в ячейку» подразумевается такое размещение блока, при котором его верхний левый угол накладывается на данную ячейку) После того как первый блок был размещен, предпринимается попытка размещения второго блока При этом второй блок не может накладываться на первый размещенный блок. Аналогичным образом размещаются и все остальные блоки Если j-й блок разместить не удается, то (|"1)-й предыдущий размещенный блок передвигается на следующее возможное место расположения После чего повторяется попытка разместить j-й блок Если ни для какого из возможных расположений (j-l)-ro блока не удалось разместить j-й блок, то (j-1 )-й блок остается не размещенным, перемещается (j-2)-ft блок, и повторяется попытка расположить (]-1)-й и j-й блоки Если j-й блок никак не удается расположить, то перемещается (j-3)-h и делается попытка вновь расположить последующие блоки Аналогичным образом можно производить перемещения вплоть до самого первого размещенного блока Таким образом, если в итоге так и не удалось расположить j-й блок, то это означает, что по алгоритму были перебраны все возможные сочетания размещений блоков от 1 до (j-1) Если задача размещения решается, то решение обязательно будет найдено. Если решение не найдено, то это означает, что были рассмотрены все возможные варианты и, следовательно, решения действительно не существует

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

Рассматриваются методы предсказания тупиков в ветвях дерева поиска

Рис. 6.

Зависимость коэффициента заполнения от степени отказоустойчивости и числа блоков

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

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

значение высоты записывается во все ячейки столбца. Второе сканирование делается по горизонтали, при этом аналогичным образом определяются длины всех свободных строк. В процессе сканирования ячеек строки считываются значения высот столбцов, которые пересекает данная строка, и определяется минимальная высота. Значения длины и минимальной высоты определяют размер свободной области, к которой относится данная строка (см. Рис. 7а). Затем делается аналогичное сканирование по вертикали, при котором определяется минимальная длина пересекаемой строки, и определяются размеры свободной области, к которой относится данный свободный столбец (рис. Рис. 76). Описанный способ определяет размеры свободных областей специфическим образом: все ячейки, принадлежащие области 1 Рис. 7а считаются принадлежащими области, длина которой соответствует длине области 1 Рис. 7а, а высота -высоте области 6 Рис. 76. Ячейки, принадлежащие области 2 рис. 7а считаются принадлежащими области, длина которой соответствует длине области 2 рис. 7а, а высота - высоте области 3 Рис. 76, и т.д.

Аналогичное свойство имеет место и для длин областей Рис. 76. Таким образом, формируются два различных представления линейных размеров свободных областей. Для представления, соответствующего Рис. 7а, делается сортировка областей по длине, а для представления, соответствующего Рис. 76 - по высоте. Рассматривается «упрощенная упаковка» блоков в области для каждого из представлений. Для представления а) блоки сортируются в порядке возрастания длины. Для представления а) блок может быть упакован в соответствующую область, если ее длина и высота не меньше соответствующих размеров блока.

■ Мш 1

2

3

4 ш 5

6

а)

Рис

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

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

Подготовка: IV = О, С = 0, и-пустое множество

Цикл по длине областей (от меньшей к большей): {

1. Рассматриваются блоки, длина которых равна длине данной области

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

Иначе блок может быть помещен в данную область

2. Рассматриваются блоки из множества неразмещенных блоков

и.

Если блок длина и высота блока не превосходят размеры данной области, то блок может быть размещен в данную область

Иначе Если существует пересечение данной области с областью представления б) и длина и высота последней не меньше размеров блока, то блок может быть размещен в данной области

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

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

В - количество ячеек, принадлежащих данной области, XV - оценка бесполезной площади, С - величина переноса из областей с меньшей длиной

1) Если в > Е + С, IV = В - Е-С, С = О

2) Если В = Е + С, № = (), С = 0

3) Если В < Е + С, ¡У = 0 , С=Е+С-Ш }

Показано, что при малой размерности задачи (приблизительно до 16 блоков при любой плотности заполнения) задача решается за приемлемое время (менее 10 секунд)

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

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

задачи двумерной упаковки Алгоритм, ограничивающий размеры блоков, заменен алгоритмом, непосредственно проверяющим возможность упаковки блоков при каждом возможном расположении отказа 2. Учет симметрии позволяет уменьшить трудоемкость алгоритма в 4 раза за счет рассмотрения отказов только в одном квадранте матрицы

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

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

В приложении А приведены фрагменты программной реализации на языке С++ алгоритмов упаковки Приведен программный код следующих основных функций

1 Алгоритм упаковки с возвратом, осуществляющий перебор всех

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

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

В приложении В приводится код программы, написанной в МАТЬАВ 7, реализующей оценку взаимозависимости числа блоков, коэффициента заполнения и степени отказоустойчивости, приведенную в четвертой главе (Рис 6) Для оценки избыточности применяется модификация алгоритма разбиения ^-отказоустойчивой системы, которая заключается в том что, вместо «дискретного» разбиения матрицы ячеек рассматривается «континуальное» разбиение прямоугольника Такой переход позволяет абстрагироваться от конкретных размеров матрицы

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

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

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

В приложении Д приводится упрощенный пример технической реализации отказоустойчивой системы на ПЛИС Рассматривается параллельная реализация комплексного умножения на ПЛИС Х1ЫКХ семейства УЖТЕХ-П ХС2У40С8144.

На основании приведенного примера делаются следующие выводы

1 Приведен упрощенный пример отказоустойчивой системы

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

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

4 Необходимо расширение функциональности САПР для управления процессом автоматической трассировки (обеспечения возможности запрещения использования определенных коммутационных матриц для трассировки)

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

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

1 Сформулированы основные принципы проектирования отказоустойчивых систем на ПЛИС.

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

3 Задача создания отказоустойчивой системы на ПЛИС сформулирована как особый случай задачи упаковки

4 Предложены алгоритмы формирования размеров блоков, позволяющие свести NP-полную задачу двумерной упаковки к частному случаю, трудоемкость которого линейно зависит от размерности задачи (числа блоков)

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

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

7 Предложены новые эффективные алгоритмы решения общей задачи двумерной упаковки.

Основное содержание работы отражено в следующих опубликованных работах:

1 Уваров С С Проектирование реконфигурируемых отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек // Автоматика и телемеханика 2007. № 9. С. 176-189

2. Уваров С. С. Основные принципы создания отказоустойчивых систем на ПЛИС // Радюелектрош i комп'ютерш системи / 2007, № 6, Харив, XAI

По смежным проблемам проектирования систем на ПЛИС имеются следующие публикации

1. Уваров С С. Методы повышения быстродействия аппаратуры, реализующей рекурсивные алгоритмы цифровой обработки сигналов Труды Российского научно-технического общества радиотехники, электроники и связи имени А С Попова Серия Цифровая обработка сигналов и ее применение Выпуск- IX - 2 Москва - 2007 стр. 472474 (Доклады 9-й Международной конференции Цифровая обработка сигналов и ее применение)

2 Уваров С. С Построение высокоскоростных демодуляторов ЧМ, ФМ2 и ФМ4 на ПЛИС Труды Российского научно-технического общества радиотехники, электроники и связи имени А С Попова Серия Цифровая обработка сигналов и ее применение Выпуск VIII - 2 Москва - 2006 стр 579-581 (Доклады 9-й Международной конференции Цифровая обработка сигналов и ее применение)

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

Зак 65 Тир 100 ИЛУ РАН

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

ВВЕДЕНИЕ.

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

СИСТЕМ НА ПЛИС.

§ 1.2. Классификация направлений исследований.

§ 1.2. Обзор литературы.

Выводы.

ГЛАВА II ОСНОВНЫЕ ПРИНЦИПЫ ПРОЕКТИРОВАНИЯ ОТКАЗОУСТОЙЧИВЫХ

СИСТЕМ НА ПЛИС.

Введение.

§2.1. Основные требования к методике проектирования.

§ 2.2. Модель ПЛИС.

§ 2.3. Модели отказов.

§ 2.4. Основные принципы проектирования.

§ 2.5. Задача упаковки.

§ 2.6. Задача отказоустойчивой упаковки.

Выводы.

ГЛАВА III СОЗДАНИЕ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ НА ПЛИС ПОСРЕДСТВОМ

ДЕКОМПОЗИЦИИ МАТРИЦЫ ЯЧЕЕК НА БЛОКИ.

Введение.

§ 3.1. Упрощенный алгоритм декомпозиции.

§ 3.2. Алгоритм декомпозиции.

§ 3.3. Алгоритм реконфигурации.

§ 3.4. Обобщенный алгоритм декомпозиции.

§ 3.5. Алгоритм реконфигурации.

§ 3.6. Резервирование ресурсов для обеспечения связи блоков после реконфигурации.

§ 3.7. Оценка избыточности.

§ 3.8. Обобщение на дополнительные функциональные ячейки.

Выводы.

ГЛАВА IV СОЗДАНИЕ К-ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ НА ПЛИС.

Введение.

§ 4.1. 2-отказоустойчивые системы.

§ 4.2. Алгоритм реконфигурации.

§ 4.3. К-отказоустойчивые системы.

§ 4.4. Алгоритм реконфигурации.

§ 4.5. Оценка избыточности.

Выводы.

ГЛАВА V СОЗДАНИЕ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ ИЗ ИНТЕЛЛЕКТУАЛЬНЫХ

БЛОКОВ ПРОИЗВОЛЬНО ЗАДАННОГО РАЗМЕРА.

Введение.

§ 5.1. Основные подходы к решению задачи упаковки.

§ 5.2. Алгоритм упаковки.

§ 5.3. Предсказание тупиков (метод ветвей и границ).

§ 5.4. Программная реализация алгоритмов упаковки.

Пример.

Выводы.

Актуальность проблемы. Стремительное развитие программируемых логических интегральных схем (ПЛИС) в последние десять лет привело к тому, что в настоящее время ПЛИС стали одним из основных элементов специализированных вычислительных систем. ПЛИС позволяют наиболее эффективно реализовать достаточно простые алгоритмы, требующие высокой вычислительной производительности [9-11]. К алгоритмам такого типа в первую очередь следует отнести быстрое преобразование Фурье, цифровую свертку, корреляцию и фильтрацию. Так же ПЛИС позволяют более надежно (по сравнению с микропроцессорами) реализовать системы управления ответственного применения, поскольку реализация в ПЛИС по-сути является аппаратной. Применение ПЛИС оказывается экономически более эффективным для мелких и средних партий аппаратуры по сравнению с разработкой специализированных микросхем. Это обусловлено более коротким циклом разработки и более низкой стоимостью разработки проекта на ПЛИС.

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

Обычно применяется резервирование на уровне системы в целом, например дублирование, т. е. введение запасной системы. Для больших систем может применяться резервирование на уровне крупных элементов (например, введение резервных процессоров в многопроцессорную систему [3, 4]). Резервирование на уровне мелких элементов, таких как логические элементы, счетчики и т.п., как правило, оказывается неэффективным, поскольку при одинаковой надежности стоимость такой системы оказывается намного выше, чем стоимость системы с резервированием на более крупном уровне. Это объясняется тем, что суммарная стоимость восстанавливающих блоков (кросскоммутаторов, мажоритарных блоков и т.д.) намного превышает стоимость введения целой резервной системы и одного восстанавливающего блока.

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

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

Методы исследования. Представление декомпозиции системы и парирования отказов как задачи упаковки позволило в проведенном исследовании применить методы комбинаторной оптимизации. Общий случай упаковки представляет собой NР-полную задачу. В работе предложены методы, позволяющие перейти от ^-полной задачи

1 Основу ПЛИС составляют конфигурируемые логические блоки (которые далее для краткости будут называться «ячейками»). Связи между ячейками могут достаточно гибко изменяться. двумерной упаковки к частному случаю двумерной упаковки, для которого трудоемкость решения линейно зависит от размерности задачи. Рассмотрены и применены алгоритмы решения общего случая двумерной задачи упаковки. Рассмотрены и применены методы снижения трудоемкости решения ЫР-полной задачи, основанные на предсказании тупиков в ветвях дерева поиска. Предложен новый эффективный метод предсказания тупиков. Данные методы являются частным случаем метода ветвей и границ. При описании алгоритмов применены методы теории графов. Алгоритмы упаковки реализованы программно, что позволило провести компьютерное моделирование, верификацию. Для верификации алгоритмов упаковки разработана и применена соответствующая методика, позволяющая выявить возможные ошибки, и провести статистические исследования влияния различных алгоритмов предсказания тупиков на время поиска решения и количество возвратов алгоритма поиска. При построении алгоритма декомпозиции К-отказоустойчивой системы применен принцип Дирихле, что позволило задавать максимально возможные размеры блоков.

Научная новизна. В работе предложен новый подход к проектированию отказоустойчивых систем, основанный на представлении задачи декомпозиции системы и парирования отказов как специального случая задачи упаковки. Подобный подход к задаче отказоустойчивости стал возможным благодаря применению конвейеризации, которая в данном случае позволяет решить проблему изменения задержек распространения сигналов при реконфигурации системы. Применение конвейеризации так же может считаться новым походом к проектированию отказоустойчивых систем на ПЛИС. Предложены алгоритмы, накладывающие ограничения на размеры блоков, таким образом, что для произвольного набора блоков, соответствующего алгоритмам, ЫР-полная задача упаковки сводится к задаче, трудоемкость которой линейно зависит от числа блоков. Данные алгоритмы позволяют декомпозировать систему на минимальное число блоков. Предложенные алгоритмы так же позволяют создать отказоустойчивую систему с минимальной избыточностью. Для общего случая №-полной задачи упаковки предложены алгоритмы, позволяющие существенно сократить трудоемкость ее решения. Сформулирована новая подзадача упаковки - «отказоустойчивая упаковка», которая может считаться модельным представлением целого ряда практически актуальных задач. Применен принцип Дирихле для определения максимально возможных размеров блоков для ^--отказоустойчивой системы.

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

1. сохранение длин связей при реконфигурации;

2. минимальная избыточность системы;

3. минимальное число блоков для данного коэффициента заполнения ПЛИС;

4. возможность создания системы, устойчивой к множественным отказам;

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

6. рассмотрение отказов в функциональных блоках, отличных от обычных ячеек (СЬВ).

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

Реализация результатов подтверждается соответствующим актом о внедрении.

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

Апробация работы. Результаты работы докладывались на:

1. Международной научно-технической конференции «Dependable Systems, Services and Technologies» («DeSSerT») в 2007 г., (г. Кировоград, Украина). По смежным проблемам проектирования систем на ПЛИС делались доклады на:

2. Международной научно-технической конференции «Digital Signal Processing and Applications» («DSPA») в 2007 г,, (г. Москва).

3. Международной научно-технической конференции «Digital Signal Processing and Applications» («DSPA») в 2006 г.(г. Москва).

Публикации. По материалам диссертационной работы имеется две публикации [7, 8]. Дополнительно имеется две публикации, посвященные смежным проблемам проектирования систем на ПЛИС [9,10].

Структура и объем работы. Работа состоит из введения, пяти глав заключения списка литературы и приложений. Основной текст изложен на 116 страницах и содержит 29 рисунков и 2 таблицы. Список литературы содержит 64 библиографических наименования.

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

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

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

В четвертой главе предлагается методика создания систем, способных парировать множественные отказы (АГ-отказоустойчивых систем). Предлагаемые в главе алгоритмы являются естественным продолжением приведенных в третьей главе алгоритмов. Для определения максимально возможных размеров блоков применен принцип Дирихле. Применительно к рассматриваемому случаю принцип Дирихле можно сформулировать следующим образом: «Если в системе предполагается К отказов и система декомпозирована на К +1 подсистему, то следует полагать, что при любом расположении отказов будет существовать хотя бы одна подсистема, не содержащая отказов». На основании принципа Дирихле утверждается, что ^-отказоустойчивая система может содержать не боле Ьп =

К п подсистем, способных парировать п<К отказов ([*] ближайшее целое число, не большее х). Здесь подразумевается, что в случае возникновения в какой-либо подсистеме большего числа отказов, чем она способна парировать, найдется подсистема, способная парировать данное число отказов, и в результате реконфигурации эти две подсистемы поменяются местами. Предлагается алгоритм декомпозиции, ограничивающий размеры формируемых блоков таким образом, что подобная замена всегда возможна. Дается вычислительно эффективный алгоритм реконфигурации. Дается оценка избыточности ^-отказоустойчивых систем, аналогичная той, которая давалась в третьей главе для 1-отказоустойчивых систем.

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

Выводы

Предложенный в Главе V подход к решению общего случая задачи отказоустойчивой упаковки фактически сводится к многократному решению задачи упаковки прямоугольных блоков в контейнер. Определение ограничений линейных размеров блоков заменено непосредственной проверкой того, что для каждого расположения отказа существует соответствующее размещение блоков. Учет симметрии позволяет сократить трудоемкость задачи в 4 раза (располагать отказ только, например, в нижнем левом квадранте матрицы). В-остальном, можно утверждать, что эффективность алгоритмов отказоустойчивой упаковки определяется эффективность алгоритмов двумерной упаковки. Рассмотрен один из таких алгоритмов. Рассмотрен метод предсказания тупиков в ветвях дерева поиска, основанный на вычислении оценки снизу бесполезной площади. Предложен новый эффективный метод оценки бесполезной площади, который позволяет существенно сократить число возвратов.

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

ЗАКЛЮЧЕНИЕ

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

1. Сформулированы основные принципы проектирования отказоустойчивых систем на ПЛИС.

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

3. Задача создания отказоустойчивой системы на ПЛИС сформулирована как особый случай задачи упаковки.

4. Предложены алгоритмы формирования размеров блоков, позволяющие свести ЫР-полную задачу двумерной упаковки к частному случаю, трудоемкость которого линейно зависит от размерности задачи (числа блоков).

5. Предложены алгоритмы, позволяющие формировать блоки максимального размера для 1- и /("-отказоустойчивых систем.

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

7. Предложены новый эффективный алгоритм решения общей задачи двумерной упаковки.

110

1. Аксенова ГЛ., Халчев В.Ф. Метод параллельно-последовательного самотестирования в интегральных схемах типа РРвА // АиТ. 2007. №1. С. 163-174.

2. Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов «Мир»1989.

3. Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурации при отказах. Часть I. 1-отказоустойчивые структуры // АиТ. 2004. № 12. С. 174-189.

4. Каравай М. Ф. Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурации при отказах. Часть II. Решетки и ^-отказоустойчивость // АиТ. 2005. № 2. С. 175-189.

5. Д. Кнут Искусство программирования для ЭВМ. 3-й том Сортировка и поиск. «Мир» 1978.

6. Потемкин И. С. Потемкин Функциональные узлы цифровой автоматики Энергоатомиздат 1988.

7. Уваров С. С. Проектирование реконфигурируемых отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек // Автоматика и телемеханика 2007. № 9. С. 176-189.

8. Уваров С. С. Основные принципы создания отказоустойчивых систем на ПЛИС // Радюелектрош \ комп'ютерш системи / 2007, № 6, Харю в, ХА1.

9. Угрюмов Е. П. Цифровая схемотехника 2-е издание «БХВ-Петербург» Санкт-Петербург 2007.

10. Г. Шилдт Полный справочник по С. 4-е издание. «Вильяме» Москва, Санкт-Петербург, Киев 2005.

11. Alfke P., Padovani R. Radiation Tolerance of High-Density FPGAs // Xilinx inc., San Jose, CA 95124-3450 www.xilinx.com

12. ALTERA corp. Stratix GX Device Handbook. ALTERA corp. Feb. 2005 www.altera.com

13. ALTERA corp.: Reliability Report 45 Q2 2007 www.altera.com

14. ALTERA corp. Stratix Device Handbook. ALTERA corp. Jan. 2006 www.altera.com

15. ALTERA corp. Stratix II Device Handbook. ALTERA corp. May 2007 www.altera.com

16. ALTERA corp. Stratix II GX Device Handbook. ALTERA corp. Aug. 2007 www.altera.com

17. Bansal N., Correa J. R., Kenyon C., Sviridenko M. Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes // Mathematics of Operations Research Vol. 31, No. 1, February 2006, pp. 31-49.

18. Berman P., DasGupta В., Muthukrishnan S., Ramaswami S. Improved Approximation Algorithms for Rectangle Tiling and Packing www.cs.uic.edu/~dasgupta/resume/publ/papers/tiling.new.pdf

19. Caffrey M., Graham P., Jonson E., Wirthlin M., Carmichael C. Single-Event upsets in SRAM FPGAs // Military and Aerospace Programmable Logic Devices (MAPLD) Laurel MD, USA September 2002

20. Callaghan A. R., Lewis K. E., Nair A. R. An Extension of the Orthogonal Packing Problem though Dimensional Flexibility. 1999 //ASME Design Engineering Technical Conference, September 12-15, 1999, Las Vegas, Nevada.

21. Chan H. H., Adya S. N., Markov I. L. Are Floorplan Representations Important In Digital Design? // The University of Michigan www.eecs.umich.edu/~imarkov/pubs/conf/ispd05-fp.pdf

22. Doumar A., Ito H. Detecting, Diagnosing and Tolerating Faults in SRAM-Based Field Programmable Gate Arrays: A Survey // IEEE Transactions on Very Large Scale Integration (VLSI) Systems // Vol. 11, No. 3, June 2003.

23. Emmert J. M., Bhatia D., Partial reconfiguration of FPGA mapped designs with applications to fault tolerance and yield enhancement // Springer Lecture Notes. New York: Springer-Verlag, 1997, pp. 141-150.

24. Fukunaga A. S., Korf R. E. Bin Completion Algorithms for Multicontainer Packing, Knapsack, and Covering Problems // Journal of Artificial Intelligence Research 28 (2007) 393-429

25. Graham P., Caffrey M., Zimmerman J., Jonson D. E. Consequences and Categories of SRSM FPGA Configuration SEUs // Military and Aerospace Programmable Logic Devices International Conference, Washington DC 9/9-9/11/2003.

26. Hanchek F., Dutt S., Methodologies for tolerating cell and interconnect faults in FPGAs // IEEE Trans. Comput., vol. 47, pp. 15-33, Jan. 1998.

27. Hastie N., Cliff R., The implementation of hardware subroutines on field programmable gate arrays," // in Proc. IEEE Custom Integ. Circuits Conf., 1990, pp. 31.4.1-31.4.4.

28. Haung J., Tahoori M. B., Lombardi F., Routability and Fault Tolerance of FPGA Interconnect Architectures // Dept. of Electrical and Computer Engineering Northeastern University Boston / MA 02115 www.itcprogramdev.org/itc2004proc/Papers/PDFs/0016 3.pdf

29. Haung J., Tahoori M. B., Lombardi F. Probabilistic Analysis of Fault Tolerance of FPGA Switch Block Array // Dept. of Electrical and Computer Engineering Northeastern University Boston www.ece.neu.edu/groups/trg/index files/papers/fpga/raw 030.pdf

30. Howard N. J., Tyrrell A. M., Allinson N. M., The yield enhancement of field-programmable gate arrays // IEEE Trans. VLSI Syst., vol. 2, pp. 115-123, Feb. 1994.

31. Huang W. K., Meyer F. J., Lombardi F., Testing configurable LUT-based FPGAs // IEEE Trans. VLSI Syst., vol. 6, pp. 276-283, June 1998.

32. Huang W. K., Meyer F. J., and Lombardi F., Multiple fault detection in logic resources of FPGAs // in Proc. Defect and Fault Tolerance in Very Large Scale Integration (VLSI) Systems, 1997, pp. 186-194.

33. Inoue T., Fujiwara H., Michinishi H., Yokohira T., Okamoto T., Universal test complexity of field-programmable gate arrays // in Proc. 4th IEEE Asian Test Symp., Nov. 1995, pp. 259-265.

34. Jain A. Rajski J., Probabilistic analysis of yield and area utilization of reconfigurable rectangular processor arrays, // Defect and Fault Tolerance in Very Large Scale Integration (VLSI) Systems, I, Koren,Ed. New York: Plenum, 1989, pp. 269-280.

35. Karp R. M. Reducibility Among Combinatorial Problems // Complexity of Computer Computations (Plenum Press, 1972)

36. Korf R. E. Optimal Rectangle Packing: New results // Computer Science Department University of California, Los Angeles 2004 www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

37. Korf R. E. Optimal Rectangle Packing: Initial results // Computer Science Department University of California, Los Angeles 2003 www-rcf.usc.edu/~skoenig/icaps/icapsQ4/icapspapers/ICAPS03KorfR.pdf

38. Lach J. J., Mangione-Smith W. H., Potkonjak M., Algorithm for efficient runtime fault recovery on diverse FPGA architectures // in Proc. Defect and Fault Tolerance in VLSI Syst., Nov. 1999, pp. 386-394.

39. Lach J., Mangione-Smith W. H., Potkonjak M. Efficiently Supported Fault-Tolerance in FPGA // Presented at FPGA'98 / Monterey CA, February 22-24,1998

40. Lach J. J., Mangione-Smith W. H., Potkonjak M. Low Overhead Fault-Tolerant FPGA Systems. // IEEE Transactions on Very Large Scale Integration (VLSI) Systems / Vol. 6, No. 2, June 1998

41. Lakamraju V., Tessier R. Tolerating Operational Faults in Cluster-based FPGAs // Dept. of Electrical and Computer Engineering University of Massachusetts Amherst, / MA 01003 www.ecs.umass.edu/ece/tessier/fpgaOO ,pd f

42. Lesh N., Marks J., McMahon A., Mitzenmacher M. Exhaustive approaches to 2D rectangular perfect packing // Information Processing Letters 90 (2004) 7-14 // www.ElsevierComputerScience.com

43. Lesh N., Marks J., McMahon A., Mitzenmacher M. New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing // Mitsubishi Electric Research Laboratories httn://www.merl.com TR2005-113 December 2005

44. Metra C., Mojoli G., Pastore S., Salvi D., Sechi G., Novel technique for testing FPGAs // Proc. IEEE Design Automation and Test in Europe, pp. 89-94,1998.

45. Meyer F. Paradham D. K., Modeling defect spacial distribution // IEEE Trans. Comput., vol. 38, pp. 538-546, Apr. 1989.

46. Moffitt M. D., Pollack M. E. Optimal Rectangle Packing: A Meta-CSP Approach // Department of Electrical Engineering and Computer Science University of Michigan 2006. www.cecs.umich.edu/~mmoffitt/papers/moffitt icaps2006.pdf

47. Murata H., Fujiyoshi K., Nakatake S., Kajitani Y. VLSI Module Placement Based on Rectangular-Packing by the Sequence-Pair // IEEE Transactions on Computer-Aided Design of Circuits and Systems, Vol. 15, No. 12, Dec. 1996.

48. Ohlsson M., Dyreklev P., Johansson K. Neutron Single Event Upsets in SRAM-based FPGAs www.ee.vt.edu/~hokiesat/docs/Xilinx-SRAM FPGAs.pdf

49. Renovell M., Portal J. M., Figueras J., Zorian Y., Testing the interconnect of ram-based FPGAs // IEEE Des. Test Comput., pp. 45-50,1998.

50. Stoud C., Wijesuriya S., Hamilton C., Abramovici M., Built-in self-test of FPGA interconnect, // Proc. Int. Test Conf., pp. 404-411, 998.

51. Stroud C., Chen P., Konala S., Abramovici M., Evaluation of FPGAs resources for built-in self-test of programmable logic blocks, // in Proc. 1996 ACM/SIGDA Int. Symp. on FPGAs, Feb. 1996, pp. 107-113.

52. XILINX corp. Constraints Guide ISE 8.1 i www.xilinx.com

53. XILINX corp. Device Reliability Report Second Qurter 2007 UG116 (v4.1.1) September 18,2007 www.xilinx.com

54. XILINX corp. Virtex-5 User Guide UG190 (v3.1) September 11, 2007 www.xilinx.com

55. XILINX corp. Virtex-4 User Guide UG070 (vl.4) September 12, 2005 www.xilinx.com

56. XILINX corp. Virtex-II Platform FPGAs: Complete Data Sheet DS031 (v3.4) March 1, 2005 www.xilinx.com

57. XILINX corp. Virtex-4 Platform FPGA Handbook August 2, 2004 www.xilinx.com

58. XILINX corp. Spartan-II FPGA Family: Complete Data Sheet DS001 August 2, 2004 www.xilinx.com

59. XILINX corp. Spartan-3 Platform FPGA Handbook July 11, 2003 www.xilinx.com 1800-255-7778

60. XILINX corp. Virtex Field Programmable Gate Arrays DS003-1 (v2.5) April 2, 2001 www.xilinx.com

61. Yagiura M., Nagamochi H. Exact Algorithms for the 2-Dimensional Strip Packing with and without Rotations. // Technical report 2007-005, Jan. 30 2007. www-or.amp.i.kyoto-u.ac.jp/members/nag/Technical report/TR2007-005.pdf1