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

• Автор: Уваров, Сергей Сергеевич
• Шифр специальности: 05.13.15
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 164 с. : ил.

СОДЕРЖАНИЕ

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

ВВЕДЕНИЕ.
ГЛАВА 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. Программная реализация алгоритмов упаковки.
Выводы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Согласно первому алгоритму разбиения требуется резервная область, равная по размерам наименьшему блоку. Приводится второй алгоритм, показывающий, что размер резервной области может быть сколь-угодно меньше любого блока по площади. Доказывается, что линейные размеры резервной области не могут быть меньше наименьших линейных размеров блоков (то, что резервная область может быть меньше но площади любого блока, достигается за счет того, что минимальными линейными размерами по высоте и ширине обладают разные блоки). Оба алгоритма декомпозиции сопровождаются алгоритмами реконфигурации, позволяющими находить размещение блоков для произвольного расположения отказов. Алгоритмы реконфигурации обладают низкой вычислительной трудоемкостью (которая линейно зависит от числа блоков), что может быть рассмотрено, как переход от общего случая ЫР-полной задачи упаковки к частному случаю, для которого вычислительная трудоемкость линейна. В четвертой главе предлагается методика создания систем, способных парировать множественные отказы (/^-отказоустойчивых систем). Предлагаемые в главе алгоритмы являются естественным продолжением приведенных в третьей главе алгоритмов. Для определения максимально возможных размеров блоков применен принцип Дирихле. Если в системе предполагается К отказов и система декомпозирована на К +1 подсистему, то следует полагать, что при любом расположении отказов будет существовать хотя бы одна подсистема, не содержащая отказов». Здесь подразумевается, что в случае возникновения в какой-либо подсистеме большего числа отказов, чем она способна парировать, найдется подсистема, способная парировать данное число отказов, и в результате реконфигурации эти две подсистемы поменяются местами. Предлагается алгоритм декомпозиции, ограничивающий размеры формируемых блоков таким образом, что подобная замена всегда возможна. Дается вычислительно эффективный алгоритм реконфигурации. Дается оценка избыточности /^-отказоустойчивых систем, аналогичная той, которая давалась в третьей главе для 1-отказоустойчивых систем. В пятой главе рассматривается более сложная задача проектирования отказоустойчивой системы с использованием 1Р-ядср, недоступных для какой-либо модификации. Показано, что эта задача сводится к общему случаю задачи двумерной упаковки. Данная задача является ЫР-полной. Рассматриваются различные методы оптимального решения задач такого типа. Рассматриваются алгоритмы предсказания тупиков в ветвях дерева поиска. Данные алгоритмы являются частным случаем метода ветвей и границ. Предсказание тупиков основано на вычислении «бесполезной площади» т. Согласно этим азгоритмам, переход на какую либо ветвь не даст решения, если сумма площадей всех блоков и бесполезной площади превышают площадь области упаковки для данной ветви. Рассмотрены более совершенные методы предсказания тупиков, основанные на оценке снизу величины бесполезной площади. ГЛАВА I. Предлагается использовать введенную в обзорной работе [] классификацию направлений исследований, связанных с надежностью ПЛИС. В [] делается особый акцент на необходимости различия первого и второго направлений. Под обнаружением отказов (fault detection) подразумевается тестирование, которое дает ответ на вопрос, «все ли ресурсы ПЛИС работоспособны? ПЛИС? Такие тесты применяются в первую очередь производителем для контроля качества выпускаемой продукции. В случае обнаружения неисправностей ПЛИС отбраковывается. Важно отметить, что при этом не производится поиск отказавшего элемента ПЛИС. Отсутствие необходимости локализации отказа позволяет создавать эффективные с точки зрения времени выполнения тесты. В случае если при определенных отказах ПЛИС не отбраковывается, а предпринимаются попытки устранить или маскировать отказ, возникает необходимость в диагностировании и локализации отказов. Очевидно, что диагностирование отказов требует большего времени, чем их обнаружение. Однако, в [] на основе рассмотренной литературы делается вывод, что обе эти задачи решаются примерно одними и теми же методами.