Содержание к диссертации
Введение
ГЛАВА I. Основные направления исследований, связанных с проблемой создания отказоустойчивых и дефектоустоичивых систем на ПЛИС
1.1. Классификация направлений исследований
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. Оценка избыточности
Выводы 8
ГЛАВА V Создание отказоустойчивых систем из интеллектуальных блоков произвольно заданного размера
Введение
5.1. Основные подходы к решению задачи упаковки
5.2. Алгоритм упаковки
5.3. Предсказание тупиков (метод ветвей и границ)
5.4. Программная реализация алгоритмов упаковки
Пример 10
Выводы 10
Заключение 10
Литература 11
- Основные требования к методике проектирования
- Резервирование ресурсов для обеспечения связи блоков после реконфигурации
- Алгоритм реконфигурации
- Предсказание тупиков (метод ветвей и границ)
Введение к работе
ГЛАВА I. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ, СВЯЗАННЫХ С ПРОБЛЕМОЙ СОЗДАНИЯ ОТКАЗОУСТОЙЧИВЫХ И ДЕФЕКТОУСТОИЧИВЫХ
СИСТЕМ НА ПЛИС 1
1.2. Классификация направлений исследований 1
1.2. Обзор литературы 1
Выводы 2
Основные требования к методике проектирования
Структура и объем работы. Работа состоит из введения, пяти глав заключения списка литературы и приложений. Основной текст изложен на 116 страницах и содержит 29 рисунков и 2 таблицы. Список литературы содержит 64 библиографических наименования.
В первой главе приводится классификация направлений исследований, связанных с проблемой надежности систем на ПЛИС. Дается обзор литературы посвященной надежности и отказоустойчивым системам на ПЛИС. Дается критическая оценка каждой рассмотренной методики проектирования, показываются ее преимущества и недостатки.
Во второй главе формулируются принципы проектирования отказоустойчивых систем на ПЛИС, принятые за основу в данном исследовании. Задается модель ПЛИС и модели отказов. Предложенные основные принципы проектирования позволяют свести задачу создания отказоустойчивой системы и задачу реконфигурации к особому случаю задачи упаковки. Формулируется «задача отказоустойчивой упаковки».
В третьей главе предлагаются алгоритмы декомпозиции и реконфигурации для отказоустойчивой системы на ПЛИС. Дается оценка избыточности системы, соответствующей предлагаемым алгоритмам. Отмечено, что предлагаемая методика позволяет получить малую степень избыточности (коэффициент заполнения ячеек, близкий к единице) при малом числе блоков. Отмечается, что не требуется резервирование на уровне блоков. Согласно первому алгоритму разбиения требуется резервная область, равная по размерам наименьшему блоку. Приводится второй алгоритм, показывающий, что размер резервной области может быть сколь-угодно меньше любого блока по площади. Доказывается, что линейные размеры резервной области не могут быть меньше наименьших линейных размеров блоков (то, что резервная область может быть меньше по площади любого блока, достигается за счет того, что минимальными линейными размерами по высоте и ширине обладают разные блоки). Оба алгоритма декомпозиции сопровождаются алгоритмами реконфигурации, позволяющими находить размещение блоков для произвольного расположения отказов. Алгоритмы реконфигурации обладают низкой вычислительной трудоемкостью (которая линейно зависит от числа блоков), что может быть рассмотрено, как переход от общего случая NP-полной задачи упаковки к частному случаю, для которого вычислительная трудоемкость линейна.
В четвертой главе предлагается методика создания систем, способных парировать множественные отказы (АТ-отказоустойчивых систем). Предлагаемые в главе алгоритмы являются естественным продолжением приведенных в третьей главе алгоритмов. Для определения максимально возможных размеров блоков применен принцип Дирихле. Применительно к рассматриваемому случаю принцип Дирихле можно сформулировать следующим образом: «Если в системе предполагается К отказов и система декомпозирована на К +1 подсистему, то следует полагать, что при любом расположении отказов будет существовать хотя бы одна подсистема, не содержащая отказов». На основании принципа Дирихле утверждается, что ЛГ-отказоустойчивая система может ближайшее целое число, не большее х). Здесь подразумевается, что в случае возникновения в какой-либо подсистеме большего числа отказов, чем она способна парировать, найдется подсистема, способная парировать данное число отказов, и в результате реконфигурации эти две подсистемы поменяются местами. Предлагается алгоритм декомпозиции, ограничивающий размеры формируемых блоков таким образом, что подобная замена всегда возможна. Дается вычислительно эффективный алгоритм реконфигурации. Дается оценка избыточности -отказоустойчивых систем, аналогичная той, которая давалась в третьей главе для 1-отказоустойчивых систем.
В пятой главе рассматривается более сложная задача проектирования отказоустойчивой системы с использованием IP-ядер, недоступных для какой-либо модификации. Показано, что эта задача сводится к общему случаю задачи двумерной упаковки. Данная задача является NP-полной. Рассматриваются различные методы оптимального решения задач такого типа. Рассматриваются алгоритмы предсказания тупиков в ветвях дерева поиска. Данные алгоритмы являются частным случаем метода ветвей и границ. Предсказание тупиков основано на вычислении «бесполезной площади» т.е. площади малых областей, в которые не может быть помещении ни один блок. Согласно этим алгоритмам, переход на какую либо ветвь не даст решения, если сумма площадей всех блоков и бесполезной площади превышают площадь области упаковки для данной ветви. Рассмотрены более совершенные методы предсказания тупиков, основанные на оценке снизу величины бесполезной площади. Прелагается новый эффективный метод такой оценки, позволяющий существенно сократить число возвращений по дереву поиска.
Резервирование ресурсов для обеспечения связи блоков после реконфигурации
Задача упаковки является модельным представлением широкого спектра прикладных задач. Наиболее простым и очевидным примером задачи упаковки является размещение различного рода объектов, например, функциональных блоков в кристалле СБИС [23], элементов на печатной плате. К задачам трехмерной упаковки можно отнести размещение коробок и контейнеров в складских помещениях и т.д. Так же, к задачам упаковки можно отнести задачу раскроя листового материала. Важнейшее применение методы упаковки находят в задачах составления расписания. Задача составления расписания превращается в задачу упаковки в том случае, если дан набор работ, и выполнение каждой г -й работы требует задействовать щ обслуживающих устройств (процессоров, станков, рабочих и т.п.) в течение времени tt . И при этом существуют ограничения на общее количество узлов обслуживания N и общее время выполнения работы Т. Задачи упаковки можно разделить на два типа: 1. Задачи с неориентированными блоками. 2. Задачи с ориентированными блоками. Задачи с неориентированными блоками подразумевают возможность поворотов блоков на 90. К такого типа задачам можно отнести размещение коробок в контейнере, где не имеет значения, как «повернута» каждая коробка. Задачи упаковки ориентированных блоков подразумевают неоднородность координат, и поэтому, в таких задачах не допускаются повороты блоков. Типичным примером такого типа задач является составление расписаний, где одна координата соответствует номерам узлов обслуживания, а другая - времени, и эти координаты нельзя менять местами (т.е. («,,/,) (/,, и,)). К задачам такого типа можно отнести и задачи раскроя материала, имеющего различные свойства по двум ортогональным направлениям (например, древесина вдоль волокон намного более хрупкая, чем поперек волокон).
В задаче упаковки блоков в ПЛИС блоки считаются ориентированными, поскольку трассировочные ресурсы ПЛИС не одинаковы по вертикальным и горизонтальным направлениям. В-частности, почти все современные ПЛИС содержат цепи быстрого переноса, предназначенные для реализации арифметических функций (сложения, умножения, сравнения и т.п.). Эти цепи расположены только вдоль одного направления (в документации XILINX [57-63] и ALTERA [14, 16-18] эти цепи изображены проходящими по вертикали).
В литературе редко встречается термин задача упаковки, а почти всегда применяется термин задача оптимальной упаковки. Это связано с тем, что во многих задачах упаковки конечной целью является получение некой оптимальной по какому либо критерию упаковки. Такими критериями могут быть минимальность занимаемой области по какой-либо одной координате, например, задача составления расписания минимальной длины при заданном количестве узлов обслуживания, или задача составления расписания, требующего минимального количества узлов обслуживания, при ограничении на общее время выполнения работ. Либо минимизация занимаемой площади - задача составления расписания минимальной стоимости (например, если обслуживающими устройствами являются рабочие с повременной оплатой, которая не зависит от того, работают они, или простаивают). Задача оптимальной упаковки всегда сводится к решению задачи упаковки [38, 39, 49, 64]. Оптимальное решение находится путем перебора частных решений, а в каждом частном решении применяются методы упаковки. Рассматриваемая далее задача упаковки подразумевает только лишь поиск размещения набора блоков в контейнер строго заданного размера (матрицу ПЛИС), и по-видимому, не может называться оптимальной, однако методы ее решения те же, что и для задачи оптимальной упаковки. 2.6. Задача отказоустойчивой упаковки
Рассматриваемая задача отличается от классической задачи упаковки дополнительным ограничением, которое заключается в том, что при любом расположении отказа должно существовать размещение блоков, при котором отказавшая ячейка не покрыта ни одним из размещенных блоков. Алгоритм реконфигурации должен представлять собой алгоритм упаковки с ограничением, заданным размещением отказа. Предлагается называть «отказоустойчивой упаковкой» следующую задачу, состоящую из двух подзадач: 1. Определение как можно менее жестких ограничений, накладываемых на допустимые линейные размеры блоков, таких чтобы при любом расположении отказа существовало размещение блоков, в котором область отказа не покрыта ни одним из блоков. 2. Нахождение размещения заданного набора блоков, для произвольного расположения отказа, при котором область отказа не покрыта ни одним из блоков. Набор блоков, соответствующий указанным требованиям предлагается называть «отказоустойчивым набором (системой)». Общий случай задачи упаковки представляет собой NP-полную задачу. Далее в главах 3,4 рассматриваются алгоритмы формирования размеров блоков, позволяющие свести общий случай NP-полной задачи к частному случаю для которого трудоемкость линейно зависит от размерности (числа блоков). В главе 5 рассматриваются методы решения общего случая задачи упаковки. Представление задачи создания отказоустойчивого набора блоков и парирования отказов как специального случая задачи упаковки дает теоретическую основу для создания универсальной методики проектирования отказоустойчивых систем на ПЛИС. Задача отказоустойчивой упаковки может считаться модельным представлением целого ряда практических задач: 1. Применение листового материала, в котором допускается некоторое определенное количество произвольно расположенных дефектов для изготовления набора заготовок, не содержащих дефектов. 2. Составление расписания для системы содержащей большое число узлов обслуживания, когда заранее известно, что одно из обслуживающих устройств будет неработоспособно, начиная с некоторого момента в течение определенного отрезка времени. 3. Размещение нескольких задач для (параллельной обработки) в многопроцессорной системе, имеющей архитектуру решетки, при условии, что один или несколько произвольных процессоров могут быть неработоспособны. В качестве примера задачи 1 можно привести следующую задачу. Мебельная фабрика производит некоторые изделия из стандартных листов фанеры. Каждый лист фанеры разрезается на несколько заготовок разного размера. Существует несколько классов качества фанеры в зависимости от числа сучков и др. локальных дефектов (чем меньше дефектов, тем выше цена). Набор заготовок покрывает не всю площадь листа. Какого качества листы нужно применять, чтобы при любом размещении дефектов всегда можно было изготовить заданный набор заготовок, и затраты на материал были бы минимальными?
Алгоритм реконфигурации
Предлагаемая методика позволяет создавать на базе ПЛИС системы, устойчивые к отказу одной произвольной ячейки, связи (как проводящей линии, так и коммутационной матрицы), умножителя, блока памяти и, возможно, других функциональных узлов ПЛИС. Методика гарантирует сохранение всех длин связей в комбинационных схемах и других узлах, помещенных внутрь блоков, и это дает уверенность в том, что после реконфигурации система сохранит свою работоспособность. Оценка эффективности алгоритма разбиения показывает, что уже при трех блоках может быть получен коэффициент заполнения ПЛИС 87,5%, а для семи блоков теоретически может быть получен коэффициент заполнения 99,2%, что, фактически, можно считать предельным заполнением даже для обычной (не отказоустойчивой системы на ПЛИС).
На современном этапе развития средств проектирования ПЛИС, по-видимому, нет возможности динамически изменять конфигурационный файл ПЛИС с помощью какой-либо программы пользователя (например, реализующей алгоритм реконфигурации), поскольку конечный конфигурационный файл представлен в недоступном для понимания пользователя формате. В связи с этим предполагается, что весь необходимый набор конфигураций должен быть заранее спроектирован, а реконфигурация системы должна производиться путем замены конфигурационного файла другим, заранее подготовленным файлом. Конфигурационные файлы, соответствующие полному набору реконфигураций, должны храниться во внешнем запоминающем устройстве.
В данной работе не рассматриваются методики поиска отказов в ПЛИС. Эти методики считаются известными, некоторые из них описаны, например в [1, 24]. Следует отметить, что для задачи восстановления работоспособности системы путем поиска отказавшей ячейки и загрузки соответствующей конфигурации, не использующей отказавшую ячейку, существует «двойственная» задача нахождения работоспособной конфигурации и определения отказавшей ячейки (либо набора ячеек, среди которых имеется отказавшая). То есть, можно пытаться восстановить систему непосредственно путем перебора (и проверки работоспособности) всех возможных конфигураций. Такая методика может считаться оправданной, например, если время проведения набора тестов, определяющих работоспособность системы, умноженное на количество конфигураций, меньше времени поиска отказавшего узла ПЛИС.
Предложенная методика может рассматриваться и как способ создания ремонтопригодных систем, не требующих замены ПЛИС в случае возникновения вышерассмотренных отказов.
Данная методика позволит использовать кристаллы с определенными заводскими дефектами для создания обычных (не отказоустойчивых систем).
В настоящей главе рассматриваются принципы создания систем, устойчивых к множественным одновременным и произвольно размещенным отказам. Систему, устойчивую к К отказам, принято для краткости называть АГ-отказоустойчивой системой. Если в системе, устойчивой к отказу одного элемента, событием, приводящим к выходу из строя системы, является одновременный отказ двух и более элементов, то для -отказоустойчивой системы таким событием является одновременный отказ К + \ и более элементов. Полагая отказы различных элементов системы независимыми событиями, и считая вероятности отказа элементов одинаковыми и равными рЭ1, где рЭ1 «1, можно утверждать, что вероятность выхода из строя обычной системы с последовательным (в смысле надежности) включением элементов, есть: 1-отказоустойчивой: Pi-oyc Npl,; АГ-отказоустойчивой: Поэтому увеличение К позволяет существенно повысить надежность системы. Общие подходы к созданию АГ-отказоустойчивых систем остаются теми же, что и для 1-отказоустойчивых. Алгоритм декомпозиции для -отказоустойчивой системы несколько сложнее, чем для 1-отказоустойчивой. Этот алгоритм строится на основе предложенного в главе III алгоритма декомпозиции. Как ранее отмечалось, очень важно уметь декомпозировать систему на минимальное число блоков. Так же важным является и получение блоков как можно большего размера. Обе эти цели достигаются с помощью вполне определенного алгоритма разбиения. Рассмотрим возможность одновременного отказа двух различных ячеек. Разобьем матрицу ПЛИС на три равные части. Очевидно, что при любом расположении отказов одна из этих частей не будет содержать отказов. Отсюда следует, что максимальный размер блока не должен превосходить трети матрицы ПЛИС. Таким образом, можно полагать, что в одной из трех частей отказы возникать не могут. В эту часть можно разместить первый блок. Теперь рассмотрим две оставшиеся части. Отказы в них могут быть распределены следующим образом: либо по одному отказу в каждой части, либо в одной части два отказа, а в другой ни одного. Поскольку распределение отказов не известно, для того чтобы учесть любое распределение отказов будем считать, что одна из частей должна «уметь» парировать один отказ, а другая два.
Предсказание тупиков (метод ветвей и границ)
Как правило, ни одна крупная система на ПЛИС не создается целиком «с нуля», а строится на основе ранее разработанных интеллектуальных ядер (IP-core). Эти ядра могут покупаться у сторонних фирм разработчиков и представлять собой некий «черный ящик с входами и выходами». Такое ядро, как правило, имеет оптимизированное расположение в матрице ПЛИС. Отсюда возникает несколько иная постановка задачи: «имея набор блоков строго заданного размера, построить отказоустойчивую систему (в вышеупомянутом смысле) либо доказать, что с заданным набором блоков (ядер) и в ПЛИС заданного размера задача не решается». Очевидно, что ранее предложенные алгоритмы разбиения при такой постановке задачу не решают.
Если задан набор блоков определенного размера и матрица ПЛИС определенного размера, то прежде чем приступить к созданию отказоустойчивой системы, необходимо определить, могут ли быть размещены все блоки (совместно) в заданной матрице. Если не удается найти требуемое размещение, то необходимо показать, что такого размещения действительно не существует.
Если набор блоков может быть размещен в кристалле ПЛИС заданного размера, то далее необходимо определить, можно ли построить при заданных условиях отказоустойчивую систему, т.е. систему, в которой при любом расположении отказа существует такое размещение блоков, что отказавшая ячейка «не покрыта» ни одним блоком. Предлагается следующее очевидное решение данной задачи: ввести особый блок размером в одну ячейку (имитирующий отказ) и, жестко закрепляя его поочередно в каждой ячейке, искать размещения для заданного набора блоков. Если для любого размещения блока, имитирующего отказ, существует размещение заданного набора блоков, то система является отказоустойчивой, иначе - нет.
Один из наиболее эффективных подходов к решению задачи упаковки предложен в [38, 39, 49]. В [38, 39, 49] говорится о применении «алгоритм с возвратами» (backtracking algorithm) для организации перебора возможных размещений блоков. В [38, 39, 49] не раскрывается суть этого алгоритма (видимо, авторы считают его очевидным). По-видимому, подразумевается алгоритм, аналогичный предложенному в 5.2. Принцип действия такого алгоритма заключается в последовательном размещении блоков до тех пор, пока не возникнет ситуация, когда следующий блок разместить невозможно. В такой ситуации делается возврат на шаг назад, и предыдущий блок размещается в другом месте, и т.д. (подробное описание см. в 5.2). В [38, 39] предлагается размещать блоки в порядке уменьшения их размеров, что позволяет более быстро найти решение, если таковое существует. Процесс поиска размещения блоков может быть представлен в виде графа-дерева, в котором каждая вершина представляет собой одно из возможных размещений блока. Число ветвей, исходящих из данной вершины соответствует числу возможных размещений следующего блока, при условии, что текущий блок размещен именно в данном месте. Задача поиска решения сводится к задаче поиска по дереву. Большинство ветвей дерева заканчивается тупиками (dead end), которым соответствует ситуация, когда при заданных размещениях п первых блоков последующий (и + і)-й блок размещен быть не может. В [38, 39] предлагается методика предсказания тупиков («branch pruning», отсекания ветвей), позволяющая на ранних стадиях ветвления отсечь большое количество ветвей, оканчивающихся тупиками, что позволяет в десятки раз сократить время поиска решения (а в случае отсутствия такового - ускорить «доказательство» того, что решения не существует). Эта методика основана на подсчете так называемой «бесполезной площади» («wasted space» - дословно «убитое (растраченное) пространство»). Бесполезная площадь есть незанятая блоками площадь, в которую из-за ее малых размеров не может быть помещен ни один блок из заданного набора. Бесполезная площадь возникает в промежутках между блоками и между блоками и границами области размещения. Предсказание тупиков делается следующим образом: если сумма площадей всех блоков и бесполезной площади на каком-то шаге превосходит площадь контейнера, то решения на данной ветви существовать не может. В [38, 39] предлагается способ оценки нижней грани бесполезной площади, позволяющий предсказывать тупики раньше, чем с помощью простого подсчета площади промежутков, в которые нельзя разместить ни один блок. Для такой оценки предлагается сделать переход от двумерной задачи упаковки к одномерной. Такой переход делается путем рассечения свободного пространства контейнера на полосы единичной высоты. Аналогичное рассечение делается и с неразмещенными блоками. Рассматривается задача упаковки отрезков, соответствующих рассеченным блокам в отрезки, соответствующие рассеченному свободному пространству. Такая одномерная задача содержит меньше ограничений, чем двумерная, и поэтому, если одномерная задача не имеет решения, то и двумерная задача так же не имеет решения. При этом, если одномерная задача решается, то это еще не означает, что существует решение двумерной задачи. Подобная одномерная задача так же является NP-полной, и, следовательно, вычислительно трудоемкой. Поэтому предлагается следующий алгоритм оценки нижней грани бесполезной площади. Далее для краткости будем называть отрезки соответствующие рассеченному свободному пространству, бинами, а отрезки, соответствующие рассеченным неразмещенным блокам - элементами.
