Содержание к диссертации
Введение
1 Анализ методов и средств обеспечения отказоустойчивости мультикомпьютерных систем 9
1.1 Методы, модели и алгоритмы обеспечения отказоустойчивости в мультикомпютерных системах 9
1.2 Модели отказоустойчивых мультикомпьютеров 12
1.3 Методы и алгоритмы размещение задач в параллельных системах 24
1.3.1 Постановка задачи размещения в мультипроцессорных системах 24
1.3.2 Методы и алгоритмы размещения подпрограмм в мультипроцессорных системах 28
1.4 Анализ путей аппаратной реализации размещения подпрограмм в мультикомпьютерных системах 35
1.5 Выводы 37
2 Метод оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах 39
2.1 Обобщенная постановка задачи переразмещения подпрограмм в отказоустойчивых мультикомпьютерах 39
2.2 Математическая постановка задачи переразмещения подпрограмм в отказоустойчивых мультикомпьютерах 41
2.3 Алгоритмы переразмещения подпрограмм с учётом отказов процессоров и межпроцессорных связей 45
2.3.1 Алгоритм замены отказавшего процессора резервным 45
2.3.2 Алгоритм переразмещения с учётом отказа процессора 45
2.4 Выводы 49
3 Устройство оперативного переразмещения подпрограмм в отказоустойчивых мультипроцессорных системах 51
3.1 Принцип аппаратной реализации переразмещения подпрограмм в отказоустойчивых мультикомпьютерах 51
3.2 Структурная организация акселератора переразмещения 52
3.3 Алгоритмы функционирования акселератора 54
3.4 Устройство замены отказавшего модуля резервным 57
3.5 Оценка производительности и быстродействия акселератора 63
3.6 Устройство поиска кратчайшего пути обхода межпроцессорной связи 67
3.7 Оценка аппаратной и временной сложности устройства поиска кратчайшего пути обхода отказавшей межпроцессорной связи 73
3.8 Выводы 79
4 Моделирование алгоритмов оперативного переразмещения в отказоустойчивых мультипроцессорных системах 80
4.1 Программная модель процедур переразмещения с учётом отказа процессора и/или отказа линка 80
4.2 Результаты исследования эффективности алгоритма планирования размещения 81
4.3 Результаты исследования эффективности алгоритма переразмещения с учётом отказа процессора и/или отказа линка 87
4.4 Выводы 89
Заключение 90
Библиографический список 92
- Методы и алгоритмы размещение задач в параллельных системах
- Математическая постановка задачи переразмещения подпрограмм в отказоустойчивых мультикомпьютерах
- Устройство замены отказавшего модуля резервным
- Результаты исследования эффективности алгоритма планирования размещения
Введение к работе
Актуальность темы. Отказоустойчивые мультикомпьютерные системы (ОМС) – одно из перспективных направлений развития параллельной вычислительной техники. ОМС способны непрерывно функционировать в условиях отказа отдельных узлов и каналов связи без необходимости проведения восстановительного ремонта за счет наличия в их архитектуре специальных аппаратно-алгоритмических средств, позволяющих автоматически обнаруживать отказы, выполнять их изолирование (и замещение резервными ресурсами) и обеспечивать восстановление логической целостности коммуникационной среды. Благодаря этим свойствам ОМС могут успешно применяться в качестве основы для создания критических важных объектов (критических систем, а именно: бортовые системы управления, системы управления опасными производствами и технологическими процессами и т.п.).
Теория отказоустойчивой организации мультикомпьютерных систем достаточно хорошо разработана. Большой вклад в эту область внесли работы отечественных ученых: С.И. Баранова, Вл.В. Воеводина, В.В. Воеводина, Ю.Ю. Громова, А.В. Каляева, И.А. Каляева, И.И. Левина, В.Г. Хорошевского, И.В. Зотова, а также зарубежных ученых: М. Флинна, К. Ванга, Р. Лонгботтома, Д. Скилликорна и др. Однако вопросы, связанные с распределением резервных ресурсов в структуре системы, локализации отказов модулей и связей, а также перераспределения множества выполняемых подпрограмм в поле работоспособных модулей в этих работах рассмотрены недостаточно.
Отказы процессорных модулей и связей ОМС приводят к появлению неодно-родностей в ее физической структуре. В результате уменьшается количество возможных маршрутов передачи данных, при этом возрастает их средняя длина, что усложняет маршрутизацию данных между работоспособными модулями после реконфигурации системы. Как следствие, увеличивается среднее время межпроцессорного обмена и снижается реальная производительность системы. Одним из путей преодоления указанных последствий отказов является переразмещение выполняемых системой программ на множестве работоспособных модулей с минимизацией времени межпроцессорного обмена. Переразмещение должно осуществляться за минимально возможное время с тем, чтобы сохранялась оперативность восстановления системы после возникновения отказов.
Задача переразмещения имеет высокую вычислительную сложность из-за ее комбинаторного характера, поэтому, учитывая жесткие временные ограничения, целесообразно полностью перенести ее решение на аппаратный уровень. Аппаратные решения аналогичных комбинаторных задач хорошо известны, однако они не позволяют минимизировать время межпроцессорного обмена в условиях неоднородности и изменяемости физической структуры ОМС под воздействием локальных отказов после выполнения реконфигурации с включением резервных модулей.
Таким образом, существует противоречие между объективной необходимостью повышения отказоустойчивости мультикомпьютерных систем и недостаточными возможностями существующих средств по обеспечению оперативной реакции на отказ с сохранением высокой реальной производительности системы.
В соответствии с вышеизложенным актуальной является научная задача разработки методов и аппаратных средств оперативного переразмещения выполняемых
системой программ на множестве работоспособных модулей (с учетом резерва), обеспечивающих минимизацию времени межпроцессорного обмена данными после ликвидации последствий отказа.
Цель диссертации: снижение времени восстановления структуры мультиком-пьютерной системы после возникновения отказов путем разработки метода и аппаратных средств оперативного переразмещения выполняемых программ на основе целенаправленной пошаговой минимизации отклонения времени межпроцессорного обмена данными от теоретической нижней оценки этого времени.
Объект исследования: отказоустойчивые мультикомпьютерные системы.
Предмет исследования: методы, алгоритмы и аппаратные средства размещения программ в отказоустойчивых мультикомпьютерных системах.
Работа выполнена по плану инициативных НИР 2009–2013 г.г. кафедры информационных систем и технологий Юго-Западного государственного университета.
Задачи исследований:
-
Анализ методов и аппаратных средств обеспечения отказоустойчивости мультикомпьютерных систем, реконфигураций структуры ОМС при отказах, размещения программ на множестве процессорных модулей. Обоснование направлений исследований.
-
Разработка метода оперативного переразмещения программ в мультикомпь-ютерных системах, обеспечивающего минимизацию времени межпроцессорного обмена данными с учетом текущего распределения отказовых неоднородностей физической структуры системы.
-
Создание аппаратно-ориентированного алгоритма оперативного переразмещения программ в ОМС, реализующего разработанный метод, а также программной модели указанного алгоритма, позволяющей исследовать его функционирование при различных комбинациях отказов.
-
Разработка структурно-функциональной организации специализированного устройства оперативного переразмещения программ после возникновения отказов в ОМС, оценка аппаратной сложности устройства, сравнительный анализ временных затрат на переразмещение программ в ОМС на аппаратном и программном уровнях.
Результаты, выносимые на защиту, и их научная новизна:
-
Метод оперативного переразмещения программ в отказоустойчивых мульти-компьютерных системах, основанный на диагональном распределении множества резервных модулей (скользящего резерва) непосредственно в матрице процессоров, новизна которого заключается в минимизации времени межпроцессорного обмена данными путем целенаправленного пошагового снижения отклонения указанного времени от нижней оценки наибольшей частной коммуникационной задержки, вычисляемой по длине множества статических маршрутов передачи данных с учетом текущей неоднородности физической структуры системы.
-
Аппаратно-ориентированный алгоритм оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, отличающийся реализацией поиска резервного модуля для замещения отказавшего процессора на множестве ближайших к отказу резервных модулей.
3. Структурно-функциональная организация специализированного устройства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, отличающаяся наличием блоков переразмещения отказавших процессорных модулей и поиска кратчайшего маршрута обхода, позволяющих осуществлять быстрый поиск резервного модуля для замещения отказавшего процессора и корректировать маршруты обмена данными с учетом распределения отказовых неодно-родностей в матрице ОМС.
Достоверность результатов диссертационной работы обеспечивается корректным и обоснованным применением аппарата математической логики, положений и методов теории множеств, графов, теории вероятностей и математической статистики, теории параллельных вычислительных систем, теории надежности, а также подтверждается имитационным моделированием с использованием зарегистрированных программных средств.
Практическая ценность результатов исследований:
-
Благодаря диагональному распределению множества резервных модулей непосредственно в матрице процессоров ОМС, созданный метод оперативного переразмещения программ позволяет значительно снизить время замещения отказавших модулей резервными (время перестройки) по сравнению с методами, основанными на введении отдельных резервных строк/столбцов (свободный захват, комбинированный захват, диагональный захват и т.п.). При этом более высокая аппаратная избыточность системы и несколько сниженный коэффициент использования резерва не являются критическими, поскольку последствия недостаточно оперативной реакции на отказ в системах рассматриваемого класса могут иметь катастрофический характер.
-
Разработанный аппаратно-ориентированный алгоритм оперативного переразмещения программ в ОМС и устройство на его основе позволяют на 2-3 порядка снизить время поиска нового варианта размещения программ в системе после возникновения отказа по сравнению с известными аналогами (реализуемыми программно), что способствует повышению оперативности реакции на отказ и, как следствие, увеличивает коэффициент готовности ОМС. При этом созданный алгоритм и аппаратные средства учитывают не только отказы процессорных модулей ОМС, но и отказы отдельных каналов связи, что существенно расширяет область их применения.
-
Аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных вентилей (ЭВ), что позволяет использовать его как в существующих, так и в перспективных мультикомпьютерных системах, содержащих десятки-сотни тысяч процессорных модулей (Titan Cray XK7, IBM BlueGene/Q и т.п.).
Реализация и внедрение. Основные результаты теоретических и экспериментальных исследований, полученные в работе, были внедрены в практическую деятельность ООО «Пробизнес» (г. Курск), ООО ПП «Микрокод» (г. Курск) и используются в учебном процессе на кафедре информационных систем и технологий Юго-Западного государственного университета при изучении дисциплины «Вычислительные системы, сети и телекоммуникации», «Аппаратное обеспечение информационных систем», «Архитектура вычислительных систем и компьютерных сетей».
Практическое применение результатов исследования подтверждается актами внедрения.
Соответствие паспорту специальности. Согласно паспорту специальности 05.13.05 – Элементы и устройства вычислительной техники и систем управления, научная задача решенная в диссертации, соответствует пунктам 1 и 2 паспорта, поскольку в ней разработаны принципы функционирования устройства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, представляющих собой один из подклассов современной вычислительной техники, а также выполнен теоретический анализ и экспериментальное исследование функционирования разработанного устройства в нормальных условиях и при наличии отказов процессорных модулей и каналов связи системы с целью улучшения ее технико-экономических и эксплуатационных характеристик.
Апробация работы. Основные положения и результаты диссертации обсуждались и получили положительную оценку на следующих конференциях и семинарах: на X и XI Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск), на XIV и XVIII Международной научно-технической конференции «Машиностроение и техносфера XXI века» (г. Донецк), на XVII Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2010» (г. Курск), а также на научных семинарах кафедры Информационных систем и технологий ЮЗГУ с 2009 по 2013 г.
Публикации. Содержание диссертации опубликовано в 15 научных работах, среди которых имеются 4 статьи в рецензируемых научных журналах и изданиях, рекомендуемых ВАК Минобрнауки РФ, 3 патента РФ на изобретение и 2 свидетельства о регистрации программы для ЭВМ.
Личный вклад соискателя. В работах по теме диссертации, опубликованных в соавторстве личный вклад соискателя сводится к следующему: в [2,3,8,9] разработаны алгоритм и методика поиска размещения, в [4,5,6,8] сформулированы принципы построения аппаратной части устройства переразмещения, в [1,4,10-13] определен критерий оценки качества размещения, в [3,14,15] предложена методика тестирования программы моделирования разработанного устройства.
Структура и объем работы. Диссертация включает введение, четыре главы, заключение, список литературы из 80 наименований, приложения. Основная часть диссертации изложена на 100 страницах машинописного текста, содержит 37 рисунков и 9 таблиц.
Методы и алгоритмы размещение задач в параллельных системах
В настоящее время предложен метод скользящего резервирования со сдвигом, позволяющий с некоторой потерей эффективности при распределении программных модулей, но со значительным снижением аппаратурных затрат на построение каждого элемента устройства и СОО реализовать отказоустойчивый МК. Структура избыточного МК для построения отказоустойчивого устройства указанным методом представляет исходную решетку элементов, дополненную столбцом и/или строкой дополнительных элементов. Модель скользящего резервирования со сдвигом заключается в следующем. Для каждого элемента устройства имеются элементы замены, являющегося его соседями. Так, элементами замены для каждого основного элемента могут быть элементы, расположенные справа, вверху и по диагонали вправо (рис. 1.7). Для каждого соседнего элемента аналогичное расположение элементов замены. Граничными элементами замены являются резервные.
При отказе каких-либо элементов устройства в соответствии с правилами самоорганизации [45] выполняется замена и восстановление структуры (рис. 1.8). окружностями показаны программные модули, выполняемые элементами. Двойными прямоугольниками изображены резервные элементы. Процесс самоорганизации сводится к образованию путей замены отказавших элементов работоспособными, заканчивающихся в резервном элементе. 4. Заменившие элементы выполняют программные модули, ранее выполнявшиеся в этих позициях. В результате проводимых замен запас резерва исчерпывается. Для организации скользящего резервирования со сдвигом каждый элемент хранит не все множество ПМ, а только соседних элементов. Самоорганизующая оболочка реализует существенно более простой алгоритм, нежели в методе с взаимным скользящим резервированием. Это объясняется тем, что для каждого заменяемого элемента анализируется возможность «захвата» элемента для выполнения его ПМ только из множества соседних элементов, а не всех элементов решетки.
Идентичность правил выбора «захватываемого» элемента для всех элементов устройства позволила построить самоорганизующую оболочку, представляющую распределенную сеть элементов самоорганизации. Указанное обстоятельство обеспечило возможность существенно повысить гибкость отказоустойчивого устройства, реализующего метод скользящего резервирования со сдвигом. Анализ известных алгоритмов самоорганизации элемента оболочки показал, что сигнал «захвата» зависит от состояний «работоспособность/отказ» соседних элементов, а также состояния «захват резерва/отказ от захвата» при сдвиге заменяемых элементов в горизонтальном направлении. Ситуация отказа от захвата характеризует событие захвата работоспособным элементом отказавшего на пути замены (1.9). Рис. 1.9 Схема возникновения отказа от захвата резервного элемента
Указанное событие фиксируется в случае появления пары расположенных друг над другом отказавших элементов или захваченного элемента и отказавшего. Сообщение об указанной ситуации передается всем элементам, расположенным левее такой пары. Для обхода критичной пары отказавший элемент, расположенный левее, захватывает элемент, находящийся сверху по вертикали или диагонали в зависимости от состояния «работоспособен/отказ» и приоритетности направления замены. Выбираемые направления замены обведены на рис. 1.10. Рис. 1.10 Схема отказоустойчивого мультиконтроллера, реализующий скользящее резервирование со сдвигом
В результате в самоорганизующем слое (рис. 1.10) каждый его элемент связан с соседним сигналами «захвата», «захвата резерва» (жирные линии). Каждый элемент самоорганизации анализирует состояние «своего» и соседних микроконтроллеров и посылает сигнал настройки в «свой» МК.
На рисунке 1.10 элементы самоорганизации показаны кружками, микроконтроллеры – прямоугольниками. Массовые параллельные вычисления настроек МК в сети элементов СОО позволяют минимизировать время самоорганизации. Недостаток такой структуры – сложность и неоднородность связей самоорганизующий оболочки с микроконтроллерами и элементов самоорганизации между собой.
Структура отказоустойчивого мультиконтроллера с самоорганизующим слоем, реализующим эффективный алгоритм замены микроконтроллеров, приведена на рис. 1.11. Рис. 1.11. Структура отказоустойчивого мультиконтроллера с самоорганизующим слоем, реализующим эффективный алгоритм замены микроконтроллеров
Особенностью рассматриваемого метода является его программонезависимостъ, являющаяся неотъемлемым свойством отказоустойчивых систем с непрерывным функционированием, а значит невозможностью применения в критических важных объектах (критических системах), где причина и тип отказа непредсказуемы, а реакция на отказ во времени должна быть как можно меньше.
В случае возникновения сбойной ситуации в рассматриваемых системах необходима оперативная замена отказавшего модуля резервным в соответствии с выбранной отказоустойчивой организацией. Однако будет показано ниже, при возникновении сбоя изменяется топология системы, что неизбежно приведет к сбою ее работы. В этом случае необходимо оперативное переразмещение ранее назначенных задач (программ, подпрограмм и т.д.) на новую топологию многопроцессорной системы. Поэтому на следующем этапе необходимо рассмотреть существующие виды топологий многопроцессорных систем и существующий методы и алгоритмы размещения задач (программ, подпрограмм и т.д.) в многопроцессорных системах.
Планирование оптимального размещения задач по множеству обрабатывающих процессоров – важный этап в процедурах подготовки комплекса взаимодействующих программ к параллельной обработке в мультикомпьютерах и кластерных системах. Оно выполняется с целью минимизации величин коммуникационных задержек, обусловленных способом обмена данными между задачами в ходе их обработки путем передачи сообщений между процессорами. Неудачное распределение задач между процессорами может привести к появлению длинных составных и перекрывающихся маршрутов транзитной передачи данных, возрастанию коммуникационных задержек и существенному снижению степени ускорения обработки, ожидаемой от распараллеливания.
Быстрое восстановление правильности функционирования системы путем реконфигурации ее структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров, приводит к существенному изменению конфигурации связей между ними и образованию длинных и перекрывающихся маршрутов передачи данных. Они могут быть уменьшены и разнесены путем оперативного переразмещения задач. В то же время процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут привести к существенному увеличению времени восстановления и снижению коэффициента готовности системы.
Математическая постановка задачи переразмещения подпрограмм в отказоустойчивых мультикомпьютерах
В матрице 16 хранятся нулевые коды, свидетельствующие о полной начальной работоспособности мультикомпьютера. В матрице 17 Q также хранятся коды нулей, свидетельствующие о наличие и полной начальной ра-ботоспособности резервных процессоров. В регистре 18 хранится код нуля («0…00»), в счетчике 26 содержится код нуля («0…00»), а значит, на выходе дешифратора 21 не появляется единичного импульса. Триггер 36 находится в высокоимпедансном состоянии.
Работа устройства состоит в следующем. В случае появления на входах j и i двоичных кодов происходит внештатная ситуация в системе логического управления (СЛУ), вызванная сбоем процессора. В этом случае, необходима оперативная реакция системы на отказ, связанная с применением аппаратных средств, предлагаемых в данной работе. При этом данные коды с входов по-даются на адресный вход А1 ОЗУ16 и ОЗУ 15, на установочный s-вход ОЗУ 24 и 23. В результате в счетчике 23 и 24 устанавливается код строки i матри-цы процессоров, в которой отказал процессор, в счетчиках 22 и 25 – код столбца матрицы процессоров, к которой отказал данный процессор. В то же время на адресный вход А1 ОЗУ 16 поступает код столбца, в которой про-изошел отказ. Одновременно и со входа 30 код строки j подается на адресный вход А2. Одновременно с этим эти же коды поступают на установочные s-входы счетчиков 23 и 24, устанавливая в них начальные значения, которые фактически являются координатами отказавшего процессора, необходимые для дальнейшего переназначения на резервный процессор. Тем не менее, из-менений в ОЗУ 15 не происходит из-за отсутствия единичного импульса на вход we разрешения записи.
Первый тактовый импульс с выхода генератора 14 импульсов поступает на вход разрешения выдачи oe ОЗУ 16, а так как на адресных входах А1 и А2 присутствуют соответствующие коды, то значение с выхода ОЗУ 16 подается на первый вход элемента 19 сравнения, на втором входе которого присутст-вует код нуля с выхода регистра 18. В результате сравнения происходит оп-ределение исправленности процессора. В случае если результат сравнения положительный, то есть он исправен, процессор должен быть отмечен как неисправный, поэтому единичный импульс со второго выхода элемента сравнения 19 подается на вход we разрешения записи ОЗУ 16. Поэтому еди-ница с выхода регистра 34 поступает на вход данных D ОЗУ 16 и заносит ту-да код единицы, как признак неисправности данного процессора.
Одновременно с этим единичный потенциал с выхода элемента сравне-ния 19 подается на второй вход элемента 27 ИЛИ и счетный вход счетчика 23. Единица проходит через элемент 27 ИЛИ и поступает на вход we разре-шения записи ОЗУ 15, чем разрешает запись нулевого кода с выхода регистра 16, что означает признак неисправности процессора с данным адресом в мат-рице P1. Далее необходима замена неисправного процессора резервным, что про-исходит следующим образом.
Так как потенциальный отказавший процессор окружает минимум 4 ре-зервных процессора, то в предлагаемом устройстве предлагается использо-вать четыре счетчика: счетчик 23 отвечает за резервный процессор, который находится справа на один от отказавшего; счетчик 22 – за резервный процес-сор, располагающийся выше на один от отказавшего; счетчик 25 отвечает за строку, которая находится ниже на один от отказавшего; счетчик 24 – за столбец левее на один от отказавшего.
В результате при появлении единичного потенциала на выходе элемента 19 сравнения, он поступает на счетный вход счетчика 24 и увеличивает его значение по переднему фронту на единицу. Этот код поступает через элемент 29 ИЛИ на адресный вход А2 ОЗУ 17. Соответствующий код с выхода ОЗУ 17 подается на второй вход элемента 20 сравнения для сравнения с кодом ну-ля, поступающим с выхода регистра 18. В результате сравнения, если резерв-ный процессор не занят, то единичный потенциал со второго выхода элемен-та 20 сравнения поступает на we вход ОЗУ 17 для единичного кода, озна-чающего его занятость, в результате замены на отказавший процессор. В тоже время единица с выхода элемента 19 сравнения также подается на вход е разрешения работы триггера 36. В результате этого, триггер уста-навливается в начальное единичное состояние. Это означает, что на прямом выходе у него устанавливается единичный потенциал, поступающий на раз-решающий е вход счетчика 22. На инверсном выходе триггера 36 устанавли-вается нулевой потенциал, запрещающий работу счетчика 25.
В случае, если результат сравнения в элемента сравнения 20 окажется отрицательным, то соответствующий потенциал с первого его выхода посту-пит на счетный вход счетчика 26 и по переднему фронту увеличит его со-держимое на единицу до кода один, который поступит на вход дешифратора 21. Этот код возбудит единичный импульс на первом выходе дешифратора 21, который поступит на счетный вход счетчика 22. Так как на входе е раз-решения присутствует единичный потенциал, то его содержимое по перед-нему фронту увеличится на единицу. В результате этого код поступит через элемент 28 ИЛИ на адресный А1 вход ОЗУ 17. Одновременно единичный по-тенциал с выхода счетчика 22 поступает на R-вход триггера 36, сбрасывая его в нулевое состояние. В результате на прямом входе появляется нулевой потенциал, который запрещает работу счетчика 22, а на инверсном – единич-ный, разрешающий работу счетчика 25. Значение с выхода ОЗУ 17 поступит на второй вход элемента 20 сравнения. Далее процесс протекает аналогично.
Если результат сравнения окажется отрицательным (резервный процес-сор занят), то соответствующий импульс с первого выхода элемента 20 срав-нения снова поступит на счетный вход счетчика 26.
Очередной код с выхода счетчика 26 подается на вход дешифратора 21. В результате код с его второго выхода поступает на вычитающий вход счет-чика 25 и по переднему фронту уменьшает его содержимое на единицу. Од-новременно единичный потенциал с выхода счетчика 25 сбрасывает триггер 36 в высокоимпедансное состояние. Далее содержимое счетчика 25 анало-гично проходит через элемент 28 ИЛИ и процесс повторяется аналогично описанному выше принципу.
В случае если результат сравнения в элементе сравнения 20 сравнения снова окажется отрицательным, соответствующий импульс с первого выхода заново подается на счетный вход счетчика 26. Третий выход с дешифратора 21 поступает на вход счетчика 24 и далее на адресный А2 вход ОЗУ 17.
В случае повторной неудачи процесс повторяется заново до появления сигнала переполнения на выходе переполнения счетчика 34, что означает не-обходимость полной замены матрицы процессоров.
Устройство замены отказавшего модуля резервным
Первый тактовый импульс с выхода генератора 14 импульсов поступает на счетные входы счетчиков 23 и 26, но так как на разрешающем е-входе счетчика 26 не присутствует единичного потенциала, увеличение хранящего-ся в нем кода не происходит. В счетчике 22 и 23 установлен код адреса, хра-нящийся в ОЗУ 15, что фактически является координатами отказавшей меж-процессорной связи. Поэтому, хранящееся в счетчике 23 значение по перед-нему фронту увеличивается на единицу. Так как на адресных А1 и А2 входах присутствуют коды отказавшей процессорной связи, а на входе ое разрешения выдачи присутствует единич-ный сигнал, то соответствующий код из ОЗУ 15 поступает на второй вход сумматора 19 и на второй вход блока нахождения минимума 20. В результа-те, в сумматоре 19 находится сумма кодов, поступивших значений с выходов регистра 18 и ОЗУ 15, которая поступает на первый вход блока нахождения минимума 20. В результате, полученное минимальное значение поступает на D-вход ОЗУ 16. В это время с разрешающего rd выхода блока нахождения минимума 20 поступил единичный импульс на счетный вход счетчика 25 и по переднему фронту увеличил его содержимое до кода единицы («0…01»), который через элемент ИЛИ 30 поступил на адресный А вход ОЗУ 16. В ре-зультате, в ОЗУ 16 сохранилось временное значение, которое поступает на первый вход блока нахождения минимума 21. В это время на втором его вхо-де присутствует код FFFF. В результате сравнения минимальный на данный момент код заносится во временный регистр 27, который поступает на D-вход ОЗУ 17, но не заносится туда, так как на его адресном входе не присут-ствует соответствующего адреса.
Следующий тактовый импульс аналогично поступает на счетный вход счетчика 23 и увеличивает его содержимое по переднему фронту на единицу. Этот код поступает на адресный А2 вход ОЗУ 15 и в результате выбранное значение подается на вторые входы сумматора 19 и блока нахождения мини-мума 20. В результате суммирования результат подается на первый вход бло-ка нахождения минимума 20. В результате появления единичного импульса на выходе блока с разрешающего rd выхода блока нахождения минимума 20 результат поиска минимума поступает для записи в ОЗУ 16, на адресном А входе которого присутствует адрес с выхода счетчика 26.
Так продолжается до тех пор, пока на выходе of переполнения счетчика 23 не появится единичный сигнал, что означает, что все столбцы выбранной строки в ОЗУ 15 проанализированы и следует переходить к следующей стро-ке. В результате, единичный импульс поступает на R-вход сброса триггера 29, в результате чего на прямом выходе появляется единый потенциал, кото-рый разрешает работу счетчика 26 и выдачу данных из ОЗУ 16. В тоже время нулевого потенциала на обратном выходе триггера 29 работа ОЗУ 15 запре-щена.
Очередной тактовый импульс поступает на счетный вход счетчика 26 и по переднему фронту увеличивает его содержимое на единицу до кода еди-ницы («0…01»). Этот код поступает на второй вход элемента 30 ИЛИ и далее на адресный А вход ОЗУ 16, а также на вход регистра 28 для запоминания номера адреса, поступившего на адресный А вход ОЗУ 16. Так как OE-выходе ОЗУ 16 присутствует единичный потенциал, то код из первой ячейки поступает с его выхода на первый вход элемента 21 сравнения, на втором входе присутствует код с выхода регистра 27. В результате сравнения, если выбранный из ОЗУ 21 код окажется меньше, то этот код записывается в ре-гистр 28.
Следующий тактовый импульс поступает на счетный вход счетчика 26 и по переднему фронту увеличивает его содержимое до кода двойки («0…010»). Этот код подается на второй вход элемента 30 ИЛИ и далее на адресный А вход ОЗУ 21, а также на вход регистра 28 для записи. Если ре-зультат сравнения в элементе 21 сравнения окажется положительным, то код с выхода элемента 21 сравнения запишется в регистр 27. Запись в регистр 28 не происходит потому что ОЗУ 15 закрыта из-за отсутствия единичного им-пульса на его ое-входе.
Так продолжается до тех пор, пока на выходе переполнения счетчика 26 не появится сигнала переполнения, означающий, что первый цикл поиска кратчайшего пути закончен, и полученный результат необходимо сохранить в ОЗУ 17, как первое «звено» в искомом кратчайшем пути.
Единичный импульс с выхода переполнения счетчика 26 подается на счетный вход счетчика 24 и S-вход триггера 29. В результате, по переднему фронту код в счетчике 24 увеличивается до кода единицы, который с его вы-хода подается на адресный А вход ОЗУ 17 на D-вход данных которого по-ступает и записывает значение с выхода регистра 27. Поступивший единич-ный импульс на S-вход триггера 29, в результате чего работа ОЗУ 16 запре-щается из-за присутствия нулевого потенциала на его ое–входе. В тоже время работа ОЗУ 15 вновь разрешена. Одновременно, на установочный s-вход ОЗУ 22 подается адрес минимального выбранного на данном шаге значения, как адреса строки в матрице смежности для следующего шага. Код в счетчи-ке 23 сбрасывается в ноль. Новый тактовый импульс поступает на счетный вход счетчика 23 и уве-личивает его содержимое по переднему фронту до кода единицы как адрес А1 столбца матрицы смежности. Адрес А1 строки поступает из счетчика 22. Далее работа схемы аналогично описанному выше принципу.
Так продолжается до тех пор, пока на выходе переполнения счетчика 22 не появится единичный импульс, который означает, что все коды в ОЗУ 15 исследованы и в ОЗУ 17 записаны все кратчайшие пути для исходного графа G. Соответственно, коды длин кратчайших путей могут быть поданы на ВУУ для анализа через D-выход ОЗУ 17.
Таким образом, в заданном параграфе рассмотрено устройство поиска кратчайшего пути обхода межпроцессорной связи, позволяющего оперативно найти кратчайшие пути обхода в случпе отказа в критических системах, где маршрут должен быть найден как можно более в короткое время.
Оценка аппаратной и временной сложности устройства поиска кратчайшего пути обхода отказавшей межпроцессорной связи
Анализ производительности предложенного акселератора проводился на 1533 серии интегральных микросхем. При этом при подсчете быстродействия и производительности учитывались временные характеристики отдельных внутренних элементов предложенного устройства (таблица 3.4) согласно се-рии микросхем ТТЛ 1533 [76-78].
Результаты исследования эффективности алгоритма планирования размещения
На основе анализа графика, приведенного на рис. 3.9 можно сделать следующие выводы. Рост графика имеет экспоненциальный характер, причем резкий скачек наблюдается при сильном скачке размеренности матрицы про-цессоров. Причем увеличение размерности матрицы процессоров всего на одну величину, например на рис. 3.9 с до увеличивает время пере-стройки почти на 450 нс в связи с резким увеличением вариантов перебора при перестройке. Кроме того, так как реальная размерность критических важных объек-тов не менее двух порядков и более ( и выше) можно ожидать резкое увеличение времени перестройки либо поиска кратчайшего пути обхода от-казавшей связи. Очевидно, что применение для этих целей программных средств неприемлемо. В связи с этим, необходимо использование специали-зированных аппаратных средств для оперативного устранения отказа процес-сорного модуля многопроцессорной системы или межпроцессорного линка с последующим переразмещением ранее назначенных подпрограмм видоизме-ненной топологии системы вследствие изменения топологической организа-ции СЛУ.
1. Выполнены программное моделирование и статистические исследо-вания на ЭВМ алгоритма, реализующего разработанный метод отказоустой-чивого переразмещения.
2. Для повышения отказоустойчивости критических важных объектов разработан алгоритм, позволяющий независимо реагировать на внештатные ситуации отказа либо процессорных модулей, либо на отказы межпроцессор-ных связей и независимо друг от друга реагировать на эти события.
3. В результате программного моделирования показано, что увеличе-ние размерности матрицы процессоров приводит к существенному возраста-нию вариантов переназначения отказавших процессорных модулей на сво-бодные резервные процессорные модули и/или вариантов поиска кратчайших маршрутов в результате отказа межпроцессорной связи.
4. Разработанные метод ускорения поиска варианта размещения, по-зволяющий при увеличении размерности матрицы процессоров на одну ве-личину, увеличить время перестройки на 450 нс не смотря на резкое увели-чение вариантов перебора при перестройках и алгоритм отказоустойчивого переразмещения с учетом отказов процессоров и/или межпроцессорных свя-зей позволяет не только оперативно реагировать на отказ процессора или межпроцессорной связи, но и повысить коэффициент готовности системы.
5. Анализ результатов, полученных в диссертационной работе позво-ляет сделать вывод о целесообразности применения аппаратных средств в критических системах и результативности предложенных подходов для пер-спективных мультикомпютерных систем. Заключение
Диссертационная работа посвящена решению научной задачи, состоя-щей в разработке методов и аппаратных средств оперативного переразмеще-ния выполняемых системой программ на множестве работоспособных моду-лей (с учётом резерва), обеспечивающих минимизацию времени межпроцес-сорного обмена данными после ликвидации последствий отказа.
В ходе решения этой задачи получены следующие основные результаты.
1. Создан метод оперативного переразмещения программ в отказо-устойчивых мультикомпьютерных системах, использующий диагональное распределение скользящего резерва непосредственно в матрице процессоров, позволяющий минимизировать время межпроцессорного обмена данными путем целенаправленного пошагового снижения отклонения указанного вре-мени от нижней оценки наибольшей частной коммуникационной задержки, определяемой исходя из длин заранее формируемых (статических) маршру-тов передачи данных в присутствии неоднородностей, обусловленных отка-зами физической структуры системы.
2. На базе созданного метода разработан аппаратно-ориентированный алгоритм оперативного переразмещения программ в отказоустойчивых муль-тикомпьютерных системах, состоящий в поиске резервного модуля для за-мещения отказавшего процессора на множестве ближайших к отказу резерв-ных модулей и позволяющий снизить время поиска нового варианта разме-щения программ в системе после возникновения отказа.
3. Разработана структурно-функциональная организация специализиро-ванного устройства оперативного переразмещения программ в отказоустой-чивых мультикомпьютерных системах, позволяющего осуществлять опера-тивный поиск резервного модуля для замещения отказавшего процессора, перераспределять подпрограммы на множестве работоспособных процессо-ров и корректировать маршруты обмена данными с учетом распределения неоднородностей, обусловленных отказами в матрице ОМС на основе аппа-ратно реализуемых матричных операций. 4. На основе имитационного моделирования установлено, что разрабо-танный алгоритм оперативного переразмещения программ в ОМС и устрой-ство на его основе позволяют на 2-3 порядка снизить время поиска нового варианта размещения программ в системе после возникновения отказа по сравнению с известными программно реализуемыми аналогами, что обеспе-чивает повышение оперативности реакции на отказ и, как следствие, увели-чение коэффициента готовности ОМС.
5. Показано, что аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных венти-лей (ЭВ), что меньше по сравнению с аналогичным устройством примерно на 104 ЭВ, и позволяет использовать его как в существующих, так и в перспек-тивных мультикомпьютерных системах, содержащих от десятка до сотен ты-сяч процессорных модулей.
