Автоматика и телемеханика, Л- 9, 2007
РАС Б 01.40.gf
© 2007 г. С.С. УВАРОВ (Институт проблем управления им. В. А. Трапезникова РАН, Москва)
ПРОЕКТИРОВАНИЕ РЕКОНФИГУРИРУЕМЫХ ОТКАЗОУСТОЙЧИВЫХ СИСТЕМ НА ПЛИС С РЕЗЕРВИРОВАНИЕМ НА УРОВНЕ ЯЧЕЕК1
Предложена методика создания рекопфигурируемых систем, способных восстанавливать работоспособность в случае отказа произвольной ячейки или связи ПЛИС. Важнейшим свойством методики является сохранение задержек распространения сигналов, гарантирующее работоспособность системы после реконфигурации. Также очень важна малая избыточность отказоустойчивой системы. которая в пределе может соответствовать всего лишь одной резервной ячейке. Применение методов упаковки позволяет создавать отказоустойчивые системы па базе закрытых интеллектуальных ядер, по требуя их модернизации. Дана оценка эффективности предложенной методики и рассмотрены возможные ограничения ее применения.
1. Введение
Стремительное развитие программируемых логических интегральных схем (ПЛИС) в последние десять лет привело к тому, что в настоящее время ПЛИС успешно конкурируют с процессорами и специализированными микросхемами в области управления и высокоскоростной обработки данных. Основу ПЛИС составляют конфигурируемые логические блоки (которые далее для краткости будут называться «ячейками»). Связи между ячейками могут достаточно гибко изменяться.
Одно из основных применений в настоящее время ПЛИС находят в аппаратуре высокоскоростной связи и обработки широкополосных сигналов в реальном масштабе времени. К аппаратуре такого рода предъявляются самые жесткие требования надежности. Одним из основных методов повышения надежности является создание систем, которые при отказах элементов способы сохранять свою работоспособность или восстанавливать ее в течение заданного отрезка времени. Для создания отказоустойчивой системы всегда необходимо введение в систему некоторых избыточных (резервных) элементов, которые в случае отказа способны заменить отказавшие элементы системы.
Обычно применяется резервирование на уровне системы в целом, например дублирование. т.е. введение запасной системы. Для больших систем может применяться резервирование на уровне крупных элементов (например, введение резервных процессоров в многопроцессорную систему) [1. 2]. Резервирование на уровне мелких элементов, таких как логические элементы, счетчики и т.п.. как правило, оказывается неэффективным, поскольку при одинаковой надежности стоимость такой системы оказывается намного выше, чем стоимость системы с резервированием на более
1 Работа выполнена ири поддержке Российского фонда фундаментальных исследований, грант № 05-08-01388.
крупном уровне. Это объясняется том. что суммарная стоимость восстанавливающих блоков (кросскоммутаторов. мажоритарных блоков и т.д.) намного превышает стоимость введения целой резервной системы и одного восстанавливающего блока.
Появление высокопроизводительных ПЛИС способно изменить ситуацию. Для резервирования на низком уровне не требуется введения в ПЛИС дополнительных кросскомутаторов. поскольку ПЛИС их уже содержит. Вместо введения резервных элементов для ПЛИС требуется лишь оставить некоторое количество незадейство-ванных ячеек, которые в случае отказа путем перепрограммирования связей заменят отказавшие ячейки. Таким образом. ПЛИС представляет собой почти идеальную аппаратную базу для создания отказоустойчивой системы на кристалле. В последние годы вышло немало статей, посвященных проектированию отказоустойчивых систем на ПЛИС с резервированием на уровне ячеек. Однако можно утверждать, что задача создания методики проектирования отказоустойчивых систем на ПЛИС к настоящему моменту далеко не исчерпана. В [3 5] связи между ячейками рассматриваются исключительно как логические связи (обеспечивающие инцидентность входов и выходов ячеек как вершин графа). Такое представление о связях но является корректным упрощением, поскольку по учитывается конечное время распространения электрического сигнала, зависящее от длины связи и определяющее верхнюю границу допустимых тактовых частот. Также полагается, что любая ячейка всегда может быть связана с любой другой ячейкой, что означает негласное предположение о системе как о полносвязном графе и явно не соответствует действительности. В [3. 4] не рассматривается возможность отказа связей и коммутационных матриц, что. по-видимому, также не вполне правильно, если учесть, что трассировочные ресурсы занимают во много раз больший объем в кристалле ПЛИС по сравнению с логическими ячейками.
В данной работе предлагается методика создания отказоустойчивых реконфи-гурируемых систем на ПЛИС. Отличительными характеристиками методики являются сохранение задержек распространения сигналов после реконфигурации системы. минимизация числа резервных ячеек, рассмотрение возможности отказа связей и коммутационных матриц, а также возможность применения методики к дополнительным ресурсам ПЛИС (блоки памяти, умножители и т.д.). Учет очевидных аспектов, возникающих при решении задачи проектирования отказоустойчивых систем на ПЛИС, приводит к тому, что предлагаемая методика выглядит более сложной и трудоемкой по сравнению с методиками, в которых эти аспекты игнорируются.
В основе предлагаемой методики лежит предположение о том. что при групповом перемещении ячеек с сохранением относительного расположения ячеек в группе связи между этими ячейками по изменяют свою длину. Это предположение справедливо. например, для ПЛИС XILINX семейства VIRTEX и SPARTAN.
Задача локализации отказов выходит за рамки данной работы. Методики тестирования и локализации отказов рассмотрены, например, в [6. 7]. Далее предполагается. что расположение отказа известно. Рассматриваются только единичные отказы на уровне ячеек и связей.
2. Основные принципы проектирования
Рассматриваются отказы ячеек и связей. Под «реконфигурацией» подразумевается изменение размещения элементов схемы по ячейкам ПЛИС, ведущее также и к изменению трассировки связей между ячейками. Целыо реконфигурации является исключение отказавшей ячейки (связи) из множества ячеек (связей), задействованных для реализации схемы. Предполагается, что сохранение длин связей в комбинационных схемах является необходимым и достаточным условием сохранения работоспособности схемы. Для сохранения длин связей комбинационные схемы
помещаются в блоки, входы и выходы блоков делаются синхронными (посредством Б-триггоров). В случае отказа блоки перемещаются относительно матрицы ПЛИС, при этом относительное размещение и трассировка внутри каждого блока сохраняются. Перемещение блоков приводит лишь к изменению внешних связей между блоками. Но изменение длин внешних связей в широком диапазоне 0, ~ Т) не влияет на работу схемы, поскольку источником и приемником сигнала на внешней
Т
сигнала. Для того чтобы при отказе любой ячейки (связи) была возможна реконфигурация (т.е. перестановка блоков), необходимо, чтобы эти блоки имели вполне определенные размеры. Далее предлагается алгоритм, позволяющий достаточно гибко задавать размеры блоков и при этом гарантированно получать отказоустойчивую систему, т.е. систему, которая способна парировать отказ произвольной ячейки (связи) путем перестановки блоков.
3. Алгоритм разбиения матрицы ПЛИС на блоки
Прежде чем перейти к описанию алгоритма разбиения, задающего размеры блоков. дадим упрощенный вариант разбиения, который, как далее станет очевидно, является частным случаем общего алгоритма разбиения. Упрощенное разбиение представляет собой пошаговое разбиение матрицы ПЛИС на блоки, при котором размер каждого последующего блока равен половине имеющегося свободного места на данном шаге и при этом на каждом шаге делается сечение только по одному направлению (вертикаль/горизонталь). Рисунок 1 иллюстрирует упрощенный алгоритм разбиения. Градациями серого показаны сформированные блоки, а белым резервные ячейки.
Нетрудно убедиться, что такой способ разбиения позволяет путем перестановки блоков сделать любую отказавшую ячейку незадействованной. При этом упрощенный алгоритм разбиения обладает существенными недостатками, а именно: размеры блоков жестко фиксированы и подразумевается, что линейные размеры матрицы равны некоторой степени двойки. Далее предлагается обобщенный алгоритм разбиения. который избавлен от указанных недостатков.
Введем необходимые в дальнейшем обозначения:
Х\, Х2 - оси системы координат,
- ячейка матрицы ПЛИС, матрица ПЛИС,
- к-й блок.
С э М -
вк
в
к
вк в!
к
Ь (С
С (С
вектор, определяющий расположение ячеики,
га
Рис. 1. Упрощенное разбиение.
1
2
X,
0
X,
Рис. 2. Условные обозначения.
ь в
Ь В) Ь В)
вектор, определяющий расположение к-го блока.
Под расположением к-го блока подразумевается расположение ячейки С1 € Вк такой, что ее координаты являются наименьшими среди всех ячеек С € Вк, т.е. Ь (Вк) = Ь (С1), где С1 такая, что для любой Ск € Вк верно Ь (С1) < Ь (Ск) (см. рис. 2).
Введем номера координат г € {1, 2} и у € {1, 2}. Такое обозначение будет удобно в том случае, если требуется описать какую-либо из координат, не конкретизируя.
1
где г €
вк и в
к 2 Вк'
какая именно это координата. Например, запись «В?
€ {1, 2} у €{1, 2} и г = у» следует читать так: «размеры то-го и к-го блоков равны по одной (какой-либо) координате, а по другой координате то-й блок вдвое мень-к
Обозначим через N общее количество блоков, полученное при разбиении матрицы ПЛИС И.
Введем понятие остаточного множества ячеек Бк, которое есть множество всех ячеек, те принадлежащих ни одному из блоков с номерами от 1 до к, т.е. Бк = = {С}) такое что для любой С€ Бк верно, что € Вг при любом г, таком, что 1 < г < к. Как в дальнейшем станет очевидно, ячейки, принадлежащие Бк, всегда будут образовывать прямоугольную область в матрице И, поэтому будет корректно
ввести обозначения размеров Бк через вектор 8к
Бк Бк
и расположения через
вектор Ь (Бк).
Можно утверждать, что множество В = {Вк,к = 1,^} однозначно определяет разбиение матрицы И на блоки, а множество Л = {Ьк,к = 1^} однозначно опре-
И
В
рации есть алгоритм нахо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.