Содержание к диссертации
Введение
1. Модели реконфигурации мультипроцессорных систем 12
1.1. Подходы к реконфигурации многопроцессорных систем 12
1.2. Концептуальная модель клеточной реконфигурации 20
1.2.1. Характеристика объекта исследования 20
1.2.2. Клеточно-автоматная модель вычислений 22
1.3. Модель надежности самореконфигурируемой системы 27
1.4. Анализ клеточных алгоритмов реконфигурации и основные задачи исследований 30
1.5. Выводы к главе 39
2. Континуальная модель самореконфигурации 40
2.1. Подход к построению континуальной модели 40
2.2. Естественно-подобная клеточная модель 50
2.3. Клеточный алгоритм определения характеристик среды реконфигурации 55
2.4. Выводы к главе 65
3. Клеточные алгоритмы автоматов среды реконфигурации 66
3.1 Стратегии клеточного поиска маршрутов реконфигурации 66
3.2. Клеточный алгоритм асинхронного поиска маршрутов 72
3.3. Клеточный алгоритм синхронного поиска маршрутов 82
3.4. Клеточный алгоритм управления реконфигурацией 90
3.5. Выводы к главе 101
4 Исследование клеточных алгоритмов 103
4.1. Характеристика среды моделирования 103
4.2. Моделирование самореконфигурации МПС при накоплении отказов 108
4.3. Исследование и анализ клеточных алгоритмов реконфигурации 116
4.4. Выводы к главе 129
Заключение 130
Список использованных источников 132
- Концептуальная модель клеточной реконфигурации
- Естественно-подобная клеточная модель
- Клеточный алгоритм асинхронного поиска маршрутов
- Исследование и анализ клеточных алгоритмов реконфигурации
Концептуальная модель клеточной реконфигурации
Базовыми требованиями к отказоустойчивым многопроцессорным системам является обеспечение их длительного функционирования без прерывания вычислений в условиях отказов процессорных элементов с применением механизмов автономной реконфигурации, сохраняющих не только логическую структуру задачи, но и масштабируемость системы независимо от ее размеров, числа и расположения отказавших и резервных элементов [2, 9, 10, 12].
Поясним понятия, используемые при формулировании требований к отказоустойчивым МПС. Отказоустойчивость – свойство системы сохранять свою логическую структуру несмотря на отказы отдельных элементов, которое достигается за счет использования избыточных ресурсов аппаратуры, программного обеспечения и времени [2, 10]. Отказ элемента – событие, состоящее в нарушении его работоспособности и невозможности выполнять заданные функции. Логический адрес (ЛА)- номер предусмотренной задачей функции, допустимой к исполнению отдельным ПЭ. Физический адрес элемента (ФА) – координаты расположения элемента в структуре МПС с фиксированной топологией. Логический адрес элемента - номер исполняемой данным элементом функции, т.е. отображение логического адреса на физический адрес элемента. Логическая структура задачи – отображение множества логических адресов на множество физических адресов элементов. При первоначальной загрузке системы физический и логический адреса ПЭ совпадают.
Реконфигурация – восстановление работоспособности МПС при отказах отдельных компонент путем переотображения множества логических адресов на множество физических адресов работоспособных элементов.
В результате реконфигурации соответствие между логическими и физическими адресами нарушается, но возможность обмена данными между элементами в реконфигурированной структуре должна сохраняться.
Масштабируемость МПС – способность наращивания и сокращения числа процессорных элементов в МПС без изменения мощности и структуры межпроцессорных связей и топологии системы в целом [2].
Автономная реконфигурация – независимость восстановления логической структуры задачи от системного и прикладного программного обеспечения.
Самореконфигурация – способность многопроцессорной системы к автономной реконфигурации без привлечения дополнительных по отношению к МПС внешних устройств с сохранением свойств масштабируемости и способности к дальнейшей реконфигурации. d–отказоустойчивость – способность системы сохранять логическую структуру задачи при числе отказавших элементов, меньшем, или равном d [10, 11].
Корректирующая способность алгоритма реконфигурации - относи тельная доля исправляемых комбинаций отказов для отказавших эле ментов из общего их числа : . Значение показателя позволяет оценить способность алгоритма ре конфигурации использовать резерв для восстановления при накоплении отказов элементов до максимально допустимого (равного мощности множества резервных элементов).
Проанализируем подходы к реконфигурации в известных методах построения отказоустойчивых и высоконадежных систем с точки зрения сфор-13 мулированных требований.
Методы обеспечения отказоустойчивости основаны на применении статического (пассивного) и динамического (активного) резервирования [58-61 ]. Целью при разработке метода обеспечения отказоустойчивости является минимизация избыточности (аппаратурной, программной и временной) системы.
Статическое поэлементное или общее резервирование предполагает параллельное функционирование не менее двух копий основного элемента или системы в целом (троированное, мажоритарное резервирование), что ведет к значительным аппаратурным затратам.
При динамическом резервировании резервные элементы заменяют основные элементы в случае их отказов. При этом число k резервных элементов может варьироваться в зависимости от требований к d-отказоустойчивости. Очевидно, что применение динамического резервирования позволяет получить минимальную избыточность для обеспечения отказоустойчивости.
Методы обеспечения отказоустойчивости, основанные на применении динамического резервирования, можно разделить на 3 группы, исходя из характера связей структуры системы (типовая топология - решетка, тор, куб, гиперкуб или полученная в результате резервирования) и логической структуры задачи (произвольные или регулярные связи). Каждая из трех групп реализует свою стратегию восстановления: Первая группа - восстанавливает произвольную логическую структуру задачи в объемлющей ее d-отказоустойчивой структуре системы. Вторая группа - восстанавливает логическую структуру с типовой топологией в охватывающей ее резервированной типовой структуре. Третья группа - восстанавливает логическую структуру с произвольными связями в избыточной системе с типовой топологией.
В первой группе логическая структура задачи с произвольной топологи ей связей выделяется из d-отказоустойчивого графа, построенного путем ввода d резервных элементов и дополнительных связей. В расширенном графе отказавшие вершины заменяются резервными, исключаются связи отказавших вершин с работоспособными и выполняется поиск графа, изоморфного исходной логической структуре. Это означает, что в объемлющем графе должен существовать граф, изоморфный исходному графу задачи, несмотря на выбрасывание любых d вершин и их связей. В объемлющем графе требуется такая структура связей, чтобы время исполнения функций на любом процессоре сохранялось неизменным. Основная черта рассмотренного подхода к реконфигурации - это фиксация нового распределения логических адресов путем замены адресных таблиц, интерпретируемых на схемном уровне. При этом не требуется перекомпиляции всех логических адресов, а корректировка таблиц выполняется операционной системой или специальным монитором.
Построение избыточного графа основывается на инвариантно-групповом анализе, а поиск «новой» конфигурации, изоморфной исходной в объемлющем графе, сводится к простому групповому преобразованию - автоморфизму [2,10,11,62,63]. Получение d-отказоустойчивых графов для приводит к увеличению числа резервных вершин существенному росту связей. Рост сложности графа задачи также существенно повышает коммуникационную сложность d-отказоустойчивой системы.
При реализации реконфигурации выбор варианта изоморфизма выполняется в централизованном реконфигураторе после сбора данных о состянии (работоспособность/отказ) всех процессоров МПС. По результатам полученного решения выполняется замена таблиц соответствия ФА и ЛА в каждом ПЭ и осуществляется перезагрузка программ исполняемых функций задачи по новым логическим адресам.
Естественно-подобная клеточная модель
Клеточный подход к решению задачи автономного восстановления многопроцессорных систем [42-47], рассмотренный в разделе 1.1, обеспечивает поиск решения по реконфигурированию с помощью специализированной среды перенастройки процессорных элементов при различных вариантах размещения резервных элементов. Данный подход обеспечивает выполнение требований по автономности и масштабируемости отказоустойчивой МПС, но для предложенных вариантов клеточных алгоритмов реконфигурации характерно недостаточно полное использование резерва для устранения последствий отказов. Способность среды реконфигурации к восстановлению работоспособности системы снижается с ростом числа отказавших элементов даже при наличии неиспользованного резерва.
Выполним анализ особенностей известного подхода к распределенной реконфигурации с целью выявления причин потери способности к восстановлению при числе отказов, близком к предельному (реконфигурация выполняется при числе отказавших узлов, не превышающем количества резервных элементов).
Клеточные алгоритмы самоорганизации реализуют универсальный подход к поиску решений путем построения кратчайших путей реконфигурации: маршрутов виртуальной передачи логических адресов от отказавших элементов к резервным элементам. Особенностью исследуемых алгоритмов является параллельное построение маршрутов реконфигурации для произвольных конфигураций отказов.
Разновидности клеточных алгоритмов построения путей реконфигурации зависят от варианта размещения резервных элементов. Резерв может быть сгруппирован в виде строк и/или столбцов по границам или плоскости решетки МПС (рис.1.7,а,б), либо равномерно размещаться в отдельных позициях решетки (рис.1.7,в). При размещении резерва в виде линеек (строк/столбцов) для любого узла известно приоритетное направление движения к резерву. В этом случае правила оптимального перемещения до ближайшего резервного узла описываются логическими функциями. Для распределённого резерва функции достижимости вычисляют дискретные характеристики качества маршрутов. Дискретные переменные являются целыми числами, расположенными в возрастающей последовательности с шагом d или 1, если d = 1. В соответствии с типом используемых переменных клеточный алгоритм с алфавитом клетки из булевых переменных назовем логическим. При использовании в алфавите клетки целых или комбинации целых и логических переменных клеточный алгоритм - дискретный. Если алфавит клетки включает и вещественные переменные, клеточный алгоритм называется континуальным.
Варианты размещения резерва Анализ известных логических и дискретных алгоритмов реконфигурации [43, 45,46] показал, что все известные модификации алгоритмов выполняют поиск решения при итерационном выполнении трех базовых клеточных функций: 1. Вычисления значений характеристик достижимости резерва. 2. Поиска непересекающихся маршрутов реконфигурации. 3. Корректировки характеристик достижимости при пересечении маршрутов. Ниже представлены примеры клеточного вычисления характеристик достижимости на имитационной модели логического и дискретного алгоритмов реконфигурации [42,43] для логической и дискретной клетки реконфигурации (рис.1.8).
Полученные значения характеристик достижимости являются основой для поиска маршрутов реконфигурации. Обязательным условием поиска является соблюдение принципа минимальности маршрута, что устраняет неопределенность выбора направлений и обеспечивает сокращение времени поиска решения (числа итераций клеточного алгоритма до достижения устойчивого состояния клетки). В то же время допускается несоблюдение указанного принципа при устранении пересечений маршрутов. Устранение пересечений предполагает запрет конфликтных направлений и выбор менее приоритетных направлений в пределах одного шага. Примеры реконфигурации логической структуры МПС на основе непересекающихся маршрутов иллюстрирует рис.1.9. Узлы решеток взвешены логическими адресами после реконфигурации. Веса (10) и (01) соответствуют отказавшим и свободным резервным вершинам. Дуги взвешены значениями маршрутной переменной, которая при отсутствии маршрута имеет нулевое значение. При наличии маршрута маршрутная переменная имеет единичное значение для логических алгоритмов, а для дискретных алгоритмов соответствует числу шагов от места отказа до текущего узла. Примеры реконфигурации для логического (а) и дискретного (б) алгоритмов
Неизбежным следствием одновременного выбора рациональных направлений для всех узлов маршрутов является появление столкновений нескольких дуг в одной вершине. Клеточные алгоритмы реконфигурации в процессе параллельного построения маршрутов обеспечивают коррекцию пересекающихся маршрутов путем выбора одного предшественника для узла и блокировкой остальных входных направлений. Блокируемые направления во избежание зацикливаний запоминаются до окончания процесса реконфи-33 гурации. При нескольких входных дугах маршрутов предшественник для уз ла может выбираться по различным критериям: - приоритету входящих дуг маршрутов; - длине маршрута от места отказа до текущего узла (максимальной или минимальной); - числу разрешенных направлений достижимости резерва для узла Выбор того или иного показателя качества маршрута порождает раз личные правила устранения конфликтов столкновения маршрутов и алгорит мы реконфигурации [44,46,47]. Получаемые при этом решения различаются по суммарной длине маршрутов и числу их пересечений. На рис.1.10 приве дены примеры построения маршрутов с устранением пересечений, из кото рых видно, что число пересечений при фиксированном варианте размещения резерва зависит от конфигурации отказов (отказавшие вершины – красный цвет, резервные - синий).
Клеточный алгоритм асинхронного поиска маршрутов
Асинхронная стратегия предполагает итерационный выбор последова телей только для подмножества узлов клеточного пространства, имеющих предшественников. Маршруты фиксируются итерационным формированием значений маршрутной переменной в от отказавших узлов в направле нии ближайших резервных узлов. Маршруты строятся пошагово до достиже ния резервных узлов (маршрут построен) или узлов пересечения нескольких маршрутов (конфликт). При конфликтах пересечений повторно запус кает композицию . Число инициаций работы определяется числом выявленных конфликтов. При отсутствии конфликтов число итераций определяется теку щим состоянием , отражающим взаимное расположение отказавших и резервных узлов.
Устранение конфликтов пересечений маршрутов выполняется по мере их появления путем разрыва лишних входных связей. При этом выбирается только одно входное ребро маршрута, остальные маршруты блокируются разрывом соответствующих связей. Информация о разрывах связей накапли вается и сохраняется до получения итогового решения в . При корректировках связей автомат повторяет глобальный цикл итерационного построения маршрутов при новом исходном состоянии про странства. На рис.3.2 приведены этапы асинхронного построения маршрутов композицией . Число итераций автомата , вычисляющего характеристики среды реконфигурации, для обеих стратегий совпадает. Число запусков для асинхронной и синхронной стратегий различается.
Этапы асинхронного построения маршрутов реконфигурации Количество запусков в асинхронном режиме определяется числом конфликтов при появлении пересечений маршрутов. В синхронном режиме вычисляет новые значения характеристик среды реконфигурации по мере изоляции отказавших узлов от резервных элементов. Таким образом, в обоих режимах число запусков зависит от конфигурации отказов и резервных узлов и стратегии обработки параметров состояния среды.
В асинхронном режиме для фиксации формируемого маршрута требуется специальная маршрутная переменная, в синхронном режиме роль маршрутной переменной может выполнять переменная тока, что дает более экономные межклеточные связи. В двух следующих разделах рассмотрены варианты клеточной реали зации для предложенных стратегий. 3.2. Клеточный алгоритм асинхронного поиска маршрутов Рассмотрим проектирование клеточного автомата , базовыми функциями которого являются: Формирование непересекающихся маршрутов реконфигурации. Коррекция связей в ТПР при устранении конфликтов пересечений маршрутов. Для стратегии асинхронного поиска маршрута введем специальную маршрутную переменную , отмечающую направление следования маршрута из узла (ij).
Клеточный асинхронный алгоритм реконфигурации представляется системой параллельных клеточных операций, где операция обеспечивает выбор направления маршрута, операция управляет состоянием ключей токопроводящей решетки при столкновениях маршрутов.
Алфавит слова состояния клетки определим множеством перемен ных [х j где: работоспособность узла (у); - резервный/основной элемент; - значение потенциала узла (у); состояния ключей (замкнут - 1, разомкнут - 0) по каждому из направлений ТЛ
Значения переменных токов и потенциалов описывают состояние токо-проводящей среды, на базе которой вычисляются минимальные маршруты от мест отказов до ближайших резервных узлов с обходом отказавших элементов.
Операция определения направления исходящей из узла (у) дуги марш рута ( ) к ближайшему резервному элементу имеет вид: J т (У ) (3.1) В соответствии с узел (у) может быть начальным пунктом маршру та (при ), промежуточным пунктом маршрута (при наличии хотя бы одного входного маршрута: ), либо не принадлежать маршруту. Направление следования маршрута ( ) выбирается по максимальному исходящему току.
При появлении столкновений маршрутов (наличии в узле более одного входного направления с сохранятся только один из них, остальные запрещаются. Устранение конфликтов столкновений обеспечивается корректировкой состояний (размыканием) ключей токопроводящей среды. В качестве критерия выбора одного из нескольких входных маршрутов использует ся минимум длины маршрута (отрицательный минимальный ток ), при равноценных вариантах выбирается направление с наибольшим номером (значением переменной k):
Разомкнутое состояние ключей во избежание многократных повторений столкновений сохраняется до окончания процесса реконфигурации. В результате корректировок связей в токопроводящей среде формируются непересекающиеся минимальные маршруты от мест отказов к ближайшим резервным узлам.
Асинхронный алгоритм поиска маршрутов при однократном запуске композиции ( ) включает этапы: 1. Запуск композиции ( ) по сигналу от . 2. Вычисление характеристик среды (операции ). 3. Вычисление значений переменных маршрутов (операция ). 4. Вычисление значений переменных управления ключами (операция ) . 5. Запуск 6. Конец. Размыкание ключей ( ) вызывает необходимость продолжения поиска маршрутов для запрещенных путей. Определение завершенности маршру тов, полученных композицией ( ), и инициацию процесса про должения поиска маршрутов выполняет автомат . Повторный запуск композиции ( ) после корректировки свя зей обеспечивает обновление значений характеристик среды (автомат ) и формирование непересекающиеся маршрутов по новым направлениям (ав томат ). При этом клеточные вычисления по правилам использу ют только локальные данные о состоянии соседних узлов, не располагая гло бальными данными о количестве и расположении отказавших и резервных элементов в решетке.
Текущее состояние клеточного массива асинхронного будем представлять графом маршрутов .
Определение 3.1. Графом маршрутов называется неориентированная графовая решетка с замкнутыми границами, каждая вершина (i=l,2,...,m; j=l,2,...,n) которой взвешена весом ( , а каждое ребро в смежном направлении к имеет вес, где принадлежность ребра маршруту, - состояние связи в направлении kє{1,2,3,4}. Рассмотрим примеры моделирования полученных клеточных операций для асинхронного автомата . Рис. 3.3 иллюстрирует смену состояния решетки при итера ционном запуске композиции ( ). На рисунках вершины, взве шенные значениями , , выделены соответственно крас ным, зеленым и синим цветом. На инцидентных ребрах каждой вершины указаны пары значений.
Исследование и анализ клеточных алгоритмов реконфигурации
Оценка корректирующей способности клеточных алгоритмов В работе исследовалась корректирующая способность (относи тельной доли исправляемых комбинаций из t отказавших элементов относительно общего числа экспериментов) разработанных континуальных алгоритмов реконфигурации, трех модификаций известных дискретных алгоритмов и логического алгоритма реконфигурации. Величина t изменялась от 1 до предельно допустимой (равной числу резервных элементов). Моделирование выполнялось при варьировании: размерности решеток; числа резервных узлов – Nr; вариантов размещения резервных узлов; числа испытаний для фиксированного количества t отказов.
Для сравнения разработанных алгоритмов с известными решениями выполнен отбор наилучшего базового варианта (по средним значениям ) среди известных модификаций дискретных и логических алгоритмов реконфигурации: - логического алгоритма с фиксированным размещением столбца резервных элементов на границе решетки ( ); - логического алгоритма с гибким размещением столбца резервных элементов («плавающий» резервный столбец) ( ); - дискретного алгоритма с устранением конфликтов по максимуму длины ( ); - дискретного алгоритма с устранением конфликтов по минимуму длины ( ); - дискретного алгоритма с устранением конфликтов по числу разрешенных направлений маршрутов ( ).
Для решетки 6х6 с заданными вариантами распределения резерва (рис.4.11) полученные при моделировании известных алгоритмов значения представлены на рис. 4.12. По результатам сравнительного анализа среди известных алгоритмов был выбран дискретный алгоритм .
Преимущество континуальных алгоритмов реконфигурации относительно дискретного алгоритма при числе отказов, близком к предельному значению, объясняется разницей в числе столкновений маршрутов. При появлении сгруппированных комбинаций отказов в дискретных алгоритмах кратчайшие маршруты от нескольких отказавших вершин на разных глобальных итерациях поиска ведут к одному и тому же ближайшему резервному узлу, что неизбежно порождает пересечения маршрутов, а иногда приводит к фатальным ситуациям.
Использование в континуальной модели вместо абсолютных кратчайших расстояний (характеристика достижимости) условных средних удален-ностей от резерва позволило уменьшить число конфликтов примерно в 2-3 раза и, как следствие, сократить число фатальных комбинаций отказов и существенно снизить вероятность появления фатальных ситуаций в 8-10 раз.
Примеры потери способности к реконфигурации для дискретных алгоритмов и успешного устранения фатальных комбинаций континуальным асинхронным и синхронным алгоритмами приведены на рис.4.15.
Результаты моделирования показали, что различные фатальные комбинации отказавших узлов проявляются для фиксированного варианта размещения резерва (см. примеры 1,2 на рис.4.15), одна и та же фатальная комбинация отказов может проявиться при различных вариантах распределения резервных элементов (см. примеры 2,3 на рис.4.15)
Примеры устранения фатальных комбинаций отказов Оценка коммуникационной сложности клеточных алгоритмов Сопоставим коммуникационную сложность реализации синхронного и асинхронного алгоритмов. В асинхронных клеточных алгоритмах вычисле ние значений переменных выполняется с использованием маршрутных переменных соседних узлов. Число внешних связей узла (i,j) для асинхронного алгоритма определяется мощностью множеств переменных исходящих токов исходящих и входящих маршрутов: \Ц \МЦ \\
Для синхронного алгоритма управление состоянием ключей выполня ется по значению исходящих из узлов токов ( ) при этом число внешних связей клетки становится минимальным: \\ Таким образом, коммуникационная сложность клетки для варианта синхронного алгоритма уменьшается в три раза по сравнению асинхронным вариантом. В соответствии с клеточными правилами дискретных алгоритмов ре конфигурации число внешних связей клетки определяется исходя из мощности выходных и входных переменных достижимости
Коммуникационная сложность континуальной клетки среды реконфигурации по сравнению с известными дискретными вариантами клетки уменьшается для синхронного варианта в 4 раза и для асинхронного в 1,3 раза. Оценка времени поиска решения На основе анализа клеточных операций и особенностей взаимодей ствия подавтоматов клетки ( , ( )) (см. разделы 3.2, 3.3, 3.4) получим выражения для оценки предельного времени получения решения для синхронного ( ) и асинхронного ( ) вариантов клетки среды реконфи
Из полученных зависимостей видно, что время поиска решения в континуальных клеточных автоматах зависит от числа отказов для синхронного варианта и количества устраняемых конфликтов (а, значит и числа глобальных итераций) для асинхронного варианта поиска маршрутов. Для синхронного варианта число глобальных итераций не превышает числа отказов независимо от взаимного расположения отказавших узлов.
Известные дискретные алгоритмы реконфигурации реализуют асинхронный подход к поиску решения, но специфика обработки дискретных характеристик среды реконфигурации порождает значительно большее число конфликтов для итоговых решений по сравнению с асинхронным континуальным алгоритмом.
Исследования показали, что число столкновений маршрутов при успешной реконфигурации для одного и того же размещения отказавших элементов у дискретного алгоритма существенно выше (в 2-4 раза), чем у континуального асинхронного алгоритма, что требует большего числа глобальных итераций для поиска решения.
