Проектирование реконфигурируемых отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Уваров, Сергей Сергеевич

• Уваров, Сергей Сергеевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Уваров, Сергей Сергеевич

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

ВВЕДЕНИЕ.

ГЛАВА 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

Список литературы диссертационного исследования кандидат технических наук Уваров, Сергей Сергеевич, 2007 год

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