Содержание к диссертации
Введение
1. Распределенная реконфигурация однородных отказоустойчивых многопроцессорных систем 11
1.1. Реконфигурирование мультипроцессоров с сетями прямых связей 12
1.2. Реконфигурирование мультипроцессоров с сетями косвенных связей 16
1.3. Анализ способности систем к реконфигурированию и основные задачи исследований 25
1.4. Выводы к главе 41
2. Алгоритм адаптивной реструктуризации отказоустойчивых мультиконтроллеров 43
2.1. Принципы адаптивной реструктуризации мультиконтроллеров 43
2.2. Алгоритм адаптивной реструктуризации мультиконтроллера 47
2.3. Примеры реализации алгоритма 51
2.4. Выводы к главе 64
3. Реструктуризация процессорных матриц методом слияния сегментов 65
3.1. Принципы адаптивной реструктуризации методом слияния сегментов 65
3.2. Определение базовой линейки ресегментации 67
3.3. Алгоритм ресегментации методом слияния сегментов 71
3.4. Примеры реализации алгоритма 79
3.4. Выводы к главе 88
4. Реструктуризация процессорных матриц методом перемещения резерва 89
4.1. Характеристика метода перемещения резервных линеек... 89
4.2. Алгоритм адаптивной реструктуризации 95
4.3. Аппаратная реализация среды реструктуризации 108
4.4. Выводы к главе 113
5. Исследование алгоритмов адаптивной реструктуризации 117
5.1. Среда моделирования алгоритмов управления реструктуризацией 117
5.2. Исследование алгоритмов реструктуризации
матричных процессоров и мультиконтроллеров 125
5.3. Выводы к главе 142
Заключение 144
Список использованных источников 146
- Анализ способности систем к реконфигурированию и основные задачи исследований
- Примеры реализации алгоритма
- Определение базовой линейки ресегментации
- Аппаратная реализация среды реструктуризации
Введение к работе
Актуальность работы. К качественно .новым требованиям, предъявляемым к функциональным характеристикам приводной техники для технологических машин, относятся: способность системы к реконфигурации в зависимости от выполняемой конкретной задачи или операции и обеспечение высокой надежности и безопасности функционирования. Встроенные интеллектуальные устройства, реализованные на новой элементной базе, позволяют получить компактные и надежные мехатронные узлы и строить на их основе многокоординатные мехатронные системы с децентрализованным управлением [1,2]. Интеллектуальные распределенные системы управления могут обеспечить не только выполнение сложных движений, но и приспособиться к возникающим при эксплуатации внутренним нарушениям, и перестроиться при фатальных ситуациях для продолжения работы.
Быстрое ускорение в снижении геометрических размеров устройств на кристалле (увеличение числа транзисторов на кристалле СБИС) и большие затраты на развитие систем высокой плотности ( внедрение систем на кристалле - System on Chip ( SoC ) ) повышает важность задач обеспечения де-фектоустойчивости и отказоустойчивости управляющих и вычислительных систем технологических машин. Растет цена риска отказа или дефекта элемента из-за существенного увеличения сложности системы, размещаемой на кристалле.
В настоящее время заметна тенденция быстрого роста производства многопроцессорных SoC (MPSoC), использующих для коммуникаций сетевые структуры. Применение при этом конфигурируемых процессоров позволяет адаптировать вычислительные ресурсы не только к различным приложениям, но и открывает новые возможности в решении задачи обеспечения отказо-дефектоустойчивости.
Управление дефектоустойчивостью систем достигается за счет переотображения физического массива (переразмещения элементов на кристалле с дефектами), а управление отказоустойчивостью обеспечивается с помощью алгоритмов реконфигурации/репродуцирования логической структуры в перестраиваемой системе. Применение алгоритмов реконфигурации или репродуцирования зависит от типа сетей коммуникационных связей системы, которые разделяются на сети с прямыми и косвенными связями [3-9].
В сетях с косвенными связями реконфигурация систем достигается с помощью адаптивных правил управления настройкой коммутационных элементов. Куном С, Авиженисом А., Сами М, Стефанелли Р., Харитой Т., Та-канами И. и другими авторами рассмотрены различные варианты методов и алгоритмов реконфигурации. Результаты исследований показывают, что при допустимой сложности средств реконфигурации существует множество фатальных ситуаций, не и справляемых даже при наличии неиспользованного резерва.
В сетях с прямыми связями репродуцирование функций при отказах обеспечивается переотображением программных модулей системы. Применение надежных и несложных сред репродуцирования также приводит к появлению фатальных конфигураций отказов.
Существует путь устранения фатальных ситуаций и сохранения работоспособности систем в процессе эксплуатации, основанный на совместном использовании алгоритмов переотображения физического массива систем и реконфигурации/репродуцирования логической структуры. В настоящее время отсутствует единый подход к решению данной задачи.
Цель диссертационной работы состоит в разработке адаптивного управления реструктуризацией однородных мультипроцессорных систем с прямыми и косвенными связями, позволяющего повысить вероятность сохранения работоспособности систем при неизменных механизмах реконфигурации структуры и репродуцирования функций.
Для достижения поставленной цели в диссертационной работе решались следующие задачи:
Разработка методологии реструктуризации реконфигурируемых систем с прямыми и косвенными сетями связи, обеспечивающих адаптивную перестройку структуры в зависимости от конфигурации фатальных отказов.
Разработка алгоритмов управления реструктуризацией самоорганизующихся систем с прямыми связями, сокращающих время простоя за счет минимизации времени перепрограммирования при сохранении функций репродуцирования.
Разработка алгоритмов управления ресегментацией реконфигурируемых систем с косвенными связями, обеспечивающими восстановление Работоспособности систем при сохранении свойств реконфигурируемости.
Разработка моделей реструктуризации для исследования алгоритмов и выполнение исследований по оценке предельных возможностей по сохранению работоспособности мультипроцессорных систем.
Методы исследования основаны на использовании математического аппарата и методов теории графов, теории конечных автоматов теории клеточных автоматов, теории надежности технических систем, теории параллельных алгоритмов.
Научная новизна результатов, полученных в диссертационной работе, заключается в следующем:
Принципы адаптивной реструктуризации систем с прямыми и косвенными связями, основанные на совместном использовании переоботоб-ражения фрагментов физических массивов системы и репродуцирова-ния/реконфигурирования ее логической структуры, что позволяет за минимальное время устранять фатальные ситуации при сохранении способности системы к восстановлению.
Алгоритм адаптивного переотображения фрагментов физического массива мультиконтроллеров, переводящий фатальные конфигурации в область исправляемых отказов при минимальном числе перезагружаемых
7 модулей путем построения кратчайших маршрутов от отказавших к резервным элементам.
Алгоритм адаптивного перепланирования размерности сегментов и переотображения фрагментов физического массива мультпроцессоров, основанный на перемещении резерва в области отказов, что позволяет разрушать фатальные конфигурации при сохранении резерва системы.
Алгоритм адаптивного слияния сегментов и переотображения фрагментов физического массива мультипроцессоров, основанный на исключении столбца (строки) из области отказов, что обеспечивает устранение фатальных комбинаций отказов и максимальное повышение вероятности сохранения работоспособности системы.
Практическая ценность диссертационной работы состоит в структурно-функциональной организации коммутационной среды, позволяющей реализовать разработанные алгоритмы адаптивной реструктуризации, а также в созданных программных моделях для исследования алгоритмов реструктуризации и результатах сравнительного анализа алгоритмов на ее основе.
Реализация и внедрение результатов в диссертационной работе.
Результаты работы внедрены в учебном процессе Курского государственного технического университета по дисциплинам "Информационные технологии в проектировании многопроцессорных систем", «Моделирование систем».
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях: III Международной научно-технической конференции «Материалы и технологии XXI века» (г.Пенза, 2005 г.), Международной молодежной научной конференции «XXXI Гагаринские чтения» (г. Москва, 2005 г.), Международных научно-технических конференциях «Медико-экологические информационные технологии» (Курск, 2004, 2005), Научно-технической конференции "Материалы и упрочняющие технологии" (г, Курск, 2004 г.), 12-ой Всероссийской межву-
8 зовской научно-технической конференции студентов и аспирантов «Микроэлектроника и информатика - 2005» (г. Зеленоград, 2005 г.), III Межвузовской конференции по научному программному обеспечению «Практика применения научного программного обеспечения в образовании и научных исследованиях» (Санкт-Петербург, 2005).
Публикации. Основные результаты диссертационной работы опубликованы в 13 работах, в том числе в 8 статьях, в 3 тезисах докладов, в 2 материалах конференций.
Основные научные положения, выносимые на защиту:
Принципы сохранения работоспособности систем с прямыми и косвенными связями при фатальных отказах, основанные на совместном использовании реструктуризации и реконфигурации/репродуцирования.
Алгоритм реструктуризации отказоустойчивых мультиконтроллеров, обеспечивающий сохранение работоспособности при минимальной области перезагрузки системы.
Алгоритмы реструктуризации реконфигурируемых матричных процессоров, основанные на слиянии/перепланировании сегментов и обеспечивающие сохранение работоспособности при фатальных отказах.
4. Результаты исследований на программной модели алгоритмов реструк туризации, позволившие оценить их предельные возможности. Объем и структура работы. Диссертационная работа состоит из вве дения, пяти глав, заключения, списка использованных источников. Общий объем диссертации составляет 000 страниц, содержащих 00 рисунков и гра фиков, и 0 таблиц, 00 страниц ~ список использованных источников,
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении к диссертации обоснована ее актуальность, сформулированы цель и задача исследований, научная новизна, практическая ценность, основные научные положения, выносимые на защиту, и приведено краткое содержание каждой из глав.
9 В первой главе дан сравнительный анализ методов обеспечения отказоустойчивости многопроцессорных устройств, рассмотрены особенности алгоритмов самоорганизации мультиконтроллеров (системы с прямыми связями) и алгоритмов реконфигурации матричных процессоров (системы с косвенными связями). На основании выполненного анализа способности однородных многопроцессорных систем к восстановлению и выявленных формальных признаках фатальных конфигураций отказов были сформулированы задачи исследований по разработке адаптивного управления реструктуризацией однородных мультипроцессорных систем с прямыми и косвенными связями, позволяющего повысить вероятность сохранения работоспособности систем при неизменных механизмах реконфигурации структуры и репродуцирования функций.
Вторая глава посвящена разработке подхода и алгоритма адаптивной реструктуризации отказоустойчивых мультиконтроллеров, обеспечивающих перевод фатальных конфигураций в область исправляемых отказов при минимальном числе перезагружаемых модулей и сохранении способности системы к восстановлению. Рассмотрена методология восстановления целостности физического массива мультиконтроллера и его способности к самоорганизации при фатальных отказах, основанная на определении минимального состава перезагружаемых программных модулей. Представлено решение задачи поиска минимизированной схемы адаптивной перезагрузки, которая базируется на существующих принципах самоорганизации и состоит в определении рационального варианта освобождения фатально отказавших узлов от своих функций.
В третьей главе рассмотрены результаты разработки подхода к адаптивной реструктуризации сегментированных матриц, основанного на объединении сегментов путем исключения столбца (строки) из фатальной области, и представлен алгоритм управления реструктуризацией. Сформулированы и доказаны утверждения, выполнение которых обеспечивает успешное перепрограммирование структуры сегментов и снижение затрат на построе-
10 ниє коммутационной среды. Представлен алгоритм адаптивной реструктуризации, выполняющий поиск координат исключаемых при объединении сегментов строк/столбцов, проверку условий допустимости слияния сегментов и определение областей переотображения сегментов при горизонтальной / вертикальной ресегментации.
Четвертая глава посвящена разработке алгоритма управления реструктуризацией реконфигурируемых матричных процессоров, позволяющего перепланировать размерность сегментов путем перемещения резерва и восстанавливать работоспособность системы при сохранении всех резервных элементов. Представлена методология разрушения фатальных конфигураций основанная на перемещении резервной линейки (столбца/строки) в фатальную область сегмента, приведены формулировки и доказательства утверждений, определяющих для каждого из методов реконфигурации допустимые области перемещения резервных строк/столбцов, а также условия допустимости повторной реструктуризации сегментов.
В пятой главе описаны разработанные в рамках диссертационной работы инструментальные средства моделирования и исследования алгоритмов реструктуризации мультиконтроллеров и матричных процессоров, а также результаты сравнительного анализа разработанных алгоритмов по адаптации к фатальным отказам.
В заключении приведены основные результаты, полученные в диссертационной работе.
Области возможного использования. Результаты диссертационной работы могут найти применение при построении устройств группового логического управления, к которым предъявляются повышенные требования по надежности и непрерывности функционирования в условиях отказов элементов.
Анализ способности систем к реконфигурированию и основные задачи исследований
С целью анализа возможностей клеточных алгоритмов репродуцирования самоорганизующихся ММК, относящихся к классу систем с прямыми связями, рассмотрим клеточную интерпретацию алгоритма маршрутизации, используя обозначения весов вершин и дуг графа ММК, принятые в [33,34], и представленные на рис. 1.11, 1.12. На рис. 1.11 дан пример именования дуг в тороидальной структуре на этапе определения достижимости резерва от фатально отказавших узлов.
Результатом выполнения клеточного алгоритма является присваивание
весам Wy — (Wljj, w j2, w j3, w j4) значений из алфавита {0,1}, где LX соот 26 ветствует запрету перемещения в соответствующем направлении, m LX разрешение построения маршрута с минимальной длиной m шагов решетки. иллюстрирует порядок расстановки весов в решетке на этапе построения минимизированных маршрутов от фатально отказавших до ближайших резервных узлов. При выполнении клеточного алгоритма маршрути зации дуги графа ММК из множества WJ (w2j w22 w23 w l4 ) соответствующие маршрутам в направлении от фатально отказавших узлов к резервным элементам, взвешиваются единичными значениями весов. Ниже приведена запись клеточного алгоритма параллельной маршрутизации ММК, реализующего механизм самоорганизации, графовой решетки при наличии отказавших и свободных узлов [22].
Анализ результатов статистического моделирования показал, что для каждого из известных алгоритмов репродуцирования характерно наличие фатальных комбинаций отказов. Несмотря на достаточно высокие показатели корректирующей способности для вариантов тороидальных структур ММК с гибким распределением резерва, остаются комбинации, которые не могут быть устранены традиционными средствами репродуцирования. В качестве мер повышения отказоустойчивости ММК, мультикомпьютеров и процессорных матриц обычно используют усложнение алгоритмов и средств реконфигурации, а также увеличение процента резервных элементов [].
Не все ресурсы мультипроцессорных систем оказываются исчерпанными к моменту появления фатальных конфигурации, что иллюстрируют рис.1.17, 1.18 .
Пример неисправляемой комбинации отказов статистического моделирования алгоритмов самоорганизации ММК показал, что фатальные комбинации отказов проявляются при числе отказавших узлов 5, а характерным признаком такой конфигурации является наличие хотя бы одного отказавшего узла, окруженного со всех сторон отказами. Таким образом, из правил самоорганизации ММК [22,34] следует, что успешное репродуцирование функций выполняется в направлении к дуги с минимальным значением веса wj 0 (Vk — 1,4) от отказавшего к резервному элементу. В тех случаях, когда из отказавшего элемента нет ни одного разрешенного исхода wj = LX ( \fk — 1,4), самоорганизация невозможна. Причем число таких комбинаций в решетках может быть достаточно большим.
Определение І.І. Вершина v- є К графа G (V, U), для которой w f, = LX \/k = 1,4 называется фатально отказавшей.
Причем число таких комбинаций отказов в решетках, содержащих фатально отказавшие вершины, может быть достаточно большим. На рис. 1.19 приведены фрагменты решеток с примерами фатальных комбинаций отказов, содержащих один или несколько фатально отказавших узлов. Очевидно, что подобное «запирание» со всех сторон хотя бы одного отказа влечет за собой отказ всего ММК независимо от числа свободных элементов в решетке, т.к. фатально отказавший элемент не способен репродуцировать свою функцию.
Примеры реализации алгоритма
Ниже представлен пример переотображения физического массива для решетки с комбинацией отказов, содержащей фатально отказавший элемент 3.2 (рис. 2.4). На рис.2.5 приведены результаты построения маршрута реструктуризации от узла 3.2. Схема переотображения ПОМ:{1.1, 2.1, 2.2} = {2.1, 2.2, 3.2}, для копий ПМ после замены основных ПМ схема переотображения ПКМ представлена в таблице 2.2.
Рис.2.4 иллюстрирует результаты успешной реконфигурации отказов в решетке с переотображенным физическим массивом ПМ. Объем перезагруженных ПМ составил для рассмотренного примера составил 6% от общего числа ПМ избыточного ММК, что минимизирует время адаптации при сохранении способности системы к самоорганизации. 01
Рис.2.4. Результат самоорганизации переотображенного ММК На рис.2.5 представлен вариант фатальной реконфигурации отказов, содержащих два фатально отказавших узла: 1.6 и 2.6.
В соответствии с п.4 алгоритма построено два минимальных маршрута реструктуризации: (1.6, 1.5, 1.4) и (2.6, 3.6, 3.1) (рис.2.6), на основе которых получена схема переотображения ПОМ: (3.1, 3.6}= {3.6, 2.6} и {1.4, 1.5}= {1.5, 1.6}. Для работоспособных элементов, являющихся соседями переотображенных элементов маршрутов, получена схема переотображения ПКМ(табл.2.3).
После установки значений xlj. — 1 для фатально отказавших узлов (см. п.9 алгоритма) система возвращается в рабочее состояние, и под управлением средств самоорганизации выполняется репродуцирование функций в адаптированной к фатальному отказу решетке (рис.2.7). В результате репродуцирования восстановлены все ПМ, предусмотренные первоначальной загрузкой системы.
Результат самоорганизации переотображенного ММК
Далее представлено еще несколько характерных примеров имитационного моделирования алгоритмов адаптивной реструктуризации и самоорганизации структуры ММК, иллюстрирующих функциональные возможности разработанного метода.
На рис.2.8,а 2.9,а приведены примеры неисправляемых комбинаций отказов с двумя фатальными областями и парами фатально отказавших вершин: (3.6) и (5.6) (рис. 2.8,а), (3.1) и (4.6) (рис. 2.9,а).
Определение базовой линейки ресегментации
Будем называть линейку (строку/столбец) фатального сегмента, соответствующую удаляемой компоненте базовой линейкой ресегментации.
Рассмотрим принципы определения координат базовых линеек для различных методов реконфигурации и реструктуризации методом слияния сегментов.
Метод непосредственной перестройки.
Утверждение 3.1. Для строки сегмента с признаками фатальной комбинации (— ,— ) исключение позиции (ijl) или (ij2) всегда ведет к устранению фатальной комбинации, где (ijl), (ij2)- позиции левого и правого горизонтальных отказов.
Доказательство.
Справедливость утверждения следует из анализа признаков фатальной конфигурации отказов данного метода. Если в строке с признаками (— ,—») правый или левый горизонтальный (рис. 3.3,а) отказ удалить путем исключения соответствующей линейки (/-ой строки либо jl-го или /2-го столбца), то фатальная конфигурация гарантированно корректируется (рис.3.3,б,в).
Следствие, Координаты базовой линейки реструктуризации для метода непосредственной перестройки при вертикальной ресегментациы совпадают с номером строки і со статусом (— ,— ), при горизонтальной ресегментациы совпадают с позициями jl или j2, где (i,jl),(iJ2) -координаты левого и правого горизонтальных отказов.
Методы ограниченного ы свободного захватов. Для алгоритмов реконфигурации методом захвата характерны два признака фатальных конфигураций: (BCT)v(OHT). Утверждение 3.2. Для 1-ой строки сегмента с признаками фатальной комбинации (BCt)v(OHt) исключение позиции (i,j2) со статусом (ФНТ) всегда ведет к устранению фатальной комбинации, где (ijl),(i,j2)- позиции левой и правой фатальных пар Доказательство Из анализа взаимного расположения двух произвольных фатальных пар, являющихся источником неисправляемых комбинаций отказов для методов захвата (рис.3.4,а), очевидно, что исключение любой фатальной пары (в позиции uimj2) устраняет признак (ФНТ ) (рис.3.4,6, в). Следствие. Координаты базовой линейки реструктуризации для методов захвата совпадают с позициями (ijl) или (ij2) отказавших элементов фатальных пар. Данные о координатах базовых линеек реструктуризации для разных методов реконфигурации используются при разработке алгоритмов ресегментации. 1\
Сегментом процессорной матрицы будем называть выпуклую сплошную прямоугольную область из активных элементов решетки с расположенными по границам области строками и (или) столбцами резервных элементов. Структуру исходной сегментированной процессорной матрицы будем представлять решеткой с разомкнутыми границами ИщХп , где т,п — количество процессорных элементов вдоль строк и столбцов решетки, разбитой на одинаковые или различающиеся по размерам сегменты. Произвольный сегмент tk є R тУ_п обозначим в виде пары координат левого нижнего iljl и правого верхнего i2J2 элементов подобласти: / =
Для сегментированной матрицы Rt2xn (рис.3.5) объединение всех сегментов даст исходную матрицу:
Аппаратная реализация среды реструктуризации
Функцией среды ресегментации является сохранение целостности матрицы путем перемещения физического массива от удаляемой до резервной линейки элементов (для метода слияния сегментов), а также от перемещенного до удаленного резерва (для метода перемещения резерва). Механизм поглощения резерва переводом его в активное состояние и деактивизации линеек с отказавшими элементами (столбцов или строк) переводом их в пассивное или резервное состояние реализуется контролируемым управлением распределенной коммутационной средой ресегментации матрицы. Ресегментация выполняется в режиме прерывания под управлением централизованных программных средств.
Если реконфигурация при фиксации очередного отказа охватывает глобальной перестройкой все подматрицы, то ресегментация инициируется только при появлении в каком-либо сегменте неисправляемой комбинации отказов, а результаты очередного удаления линейных компонент из такого сегмента сохраняются до полного исчерпания ресурсов пересегментации.
Коммутационная среда в матричных структурах формируется из окружающих каждый процессорный элемент вертикальных и горизонтальных коммутаторов, либо переключателей и информационных шин.
В данной работе рассматриваются матричные процессоры, в которых функция А-переключателей и схем реконфигурирования реализована распределенной средой на базе коммутаторов, управляемых схемами перестройки (рис.4.10). Схемы управления перестройкой формируют сигналы горизонтальной и вертикальной реконфигурации в соответствии с алгоритмами реконфигурации, отличающимися сложностью и способностью к реконфигурированию.
Коммутационная распределенная среда ресегментации состоит из вертикальных и горизонтальных переключателей, встраиваемых на входах и выходах каждого процессорного элемента. Функциями переключателей являются:
«сохранение» - сохранение исходных связей между ПЭ при отсутствии изменений физического массива в сегменте;
«перемещение» - перекоммутация связей для сохранения целостности физического массива при исключении из него столбца/строки.
В режиме «сохранение» входные переключатели выполняют передачу данных на входы ПЭ непосредственно от его физических соседей. В режиме «перемещение» обеспечивается обход ПЭ и передача данных на входной переключатель соседнего элемента.
Рис.4.11 иллюстрирует перекоммутацию входных связей процессорных элементов для обеспечения горизонтальной ресегментации при исключении столбца. Горизонтальные (г22, г23, г32, гЗЗ) и вертикальные (е22, в23, в32, вЗЗ) входные переключатели, начиная от элементов отключаемого столбца (элементы с физическими адресами 2,2 , 3,2 ), переводятся в режим «перемещение». Это позволяет связать элементы, получившие физические адреса 2,2 и 3,2 , с истинными физическими соседями.
Вертикальные и горизонтальные выходные переключатели возвращают результирующие данные от ПЭ с перемещенным физическим адресом на выход элемента, который обладал этим адресом в начальном состоянии физического массива. Это позволяет сохранить исходные физические связи выходов ПЭ с физическими соседями и обеспечить тем самым корректную работу распределенных средств реконфигурации.
Вертикальные и горизонтальные выходные переключатели возвращают результирующие данные от ПЭ с перемещенным физическим адресом на выход элемента, который обладал этим адресом в начальном состоянии физического массива. Это позволяет сохранить исходные физические связи выходов ПЭ с физическими соседями и обеспечить тем самым корректную работу распределенных средств реконфигурации.
