автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Метод, алгоритмы и аппаратные средства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах

правах рукописи

Борисенко Юлия Васильевна

Метод, алгоритмы и аппаратные средства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

5 !<:Ш! ¿014

Курск-2014

005549702

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Юго-Западный государственный университет».

доктор технических наук, профессор, Сизов Александр Семенович

Фисун Александр Павлович

доктор технических наук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Государственный университет — учебно-научно-производственный комплекс» (г.Орёл), профессор кафедры «Электроники, вычислительной техники и информационной безопасности»

Дюбрюкс Сергей Александрович

кандидат технических наук, отдельное хозрасчётное предприятие «Опытно-конструкторское бюро «Авиаавтоматика» Курского открытого акционерного общества «Прибор», инженер-конструктор 2-й категории (г. Курск)

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Тульский государственный университет» (г.Тула)

Защита диссертации состоится «03» июля 2014 г. в 10:00 часов на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал). С диссертацией можно ознакомиться в библиотеке Юго-западного государственного университета.

С диссертацией можно ознакомиться в библиотеке и на сайте Юго-Западного государственного университета, адрес сайта http://www.swsu.ru/ds/diss-swsii/.

Автореферат разослан «30» мая 2014 г.

Научный руководитель: Официальные оппоненты:

Ученый секретарь диссертационного совета

Титенко Евгений Анатольевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Отказоустойчивые мультикомпьютерные системы (ОМС) — одно из перспективных направлений развития параллельной вычислительной техники. ОМС способны непрерывно функционировать в условиях отказа отдельных узлов и каналов связи без необходимости проведения восстановительного ремонта за счет наличия в их архитектуре специальных аппаратно-алгоритмических средств, позволяющих автоматически обнаруживать отказы, выполнять их изолирование (и замещение резервными ресурсами) и обеспечивать восстановление логической целостности коммуникационной среды. Благодаря этим свойствам ОМС могут успешно применяться в качестве основы для создания критических важных объектов (критических систем, а именно: бортовые системы управления, системы управления опасными производствами и технологическими процессами и т.п.).

Теория отказоустойчивой организации мультикомпьютерных систем достаточно хорошо разработана. Большой вклад в эту область внесли работы отечественных ученых: С.И. Баранова, Вл.В. Воеводина, В.В. Воеводина, Ю.Ю. Громова, A.B. Каляева, И.А. Каляева, И.И. Левина, В.Г. Хорошевского, И.В. Зотова, а также зарубежных ученых: М. Флинна, К. Ванга, Р. Лонгботгома, Д. Скилликорна и др. Однако вопросы, связанные с распределением резервных ресурсов в структуре системы, локализации отказов модулей и связей, а также перераспределения множества выполняемых подпрограмм в поле работоспособных модулей в этих работах рассмотрены недостаточно.

Отказы процессорных модулей и связей ОМС приводят к появлению неодно-родностей в ее физической структуре. В результате уменьшается количество возможных маршрутов передачи данных, при этом возрастает их средняя длина, что усложняет маршрутизацию данных между работоспособными модулями после реконфигурации системы. Как следствие, увеличивается среднее время межпроцессорного обмена и снижается реальная производительность системы. Одним из путей преодоления указанных последствий отказов является переразмещение выполняемых системой программ на множестве работоспособных модулей с минимизацией времени межпроцессорного обмена. Переразмещение должно осуществляться за минимально возможное время с тем, чтобы сохранялась оперативность восстановления системы после возникновения отказов.

Задача переразмещения имеет высокую вычислительную сложность из-за ее комбинаторного характера, поэтому, учитывая жесткие временные ограничения, целесообразно полностью перенести ее решение на аппаратный уровень. Аппаратные решения аналогичных комбинаторных задач хорошо известны, однако они не позволяют минимизировать время межпроцессорного обмена в условиях неоднородности и изменяемости физической структуры ОМС под воздействием локальных отказов после выполнения реконфигурации с включением резервных модулей.

Таким образом, существует противоречие между объективной необходимостью повышения отказоустойчивости мультикомпьютерных систем и недостаточными возможностями существующих средств по обеспечению оперативной реакции на отказ с сохранением высокой реальной производительности системы. ■

В соответствии с вышеизложенным актуальной является Научная задача разработки методов и аппаратных средств оперативного переразмещения выполняемых

системой программ на множестве работоспособных модулей (с учетом резерва), обеспечивающих минимизацию времени межпроцессорного обмена данными после ликвидации последствий отказа.

Цель диссертации: снижение времени восстановления структуры мультиком-пьютерной системы после возникновения отказов путем разработки метода и аппаратных средств оперативного переразмещения выполняемых программ на основе целенаправленной пошаговой минимизации отклонения времени межпроцессорного обмена данными от теоретической нижней оценки этого времени.

Объект исследования: отказоустойчивые мультикомпьютерные системы.

Предмет исследования: методы, алгоритмы и аппаратные средства размещения программ в отказоустойчивых мультикомпьютерных системах.

Работа выполнена по плану инициативных НИР 2009-2013 г.г. кафедры информационных систем и технологий Юго-Западного государственного университета.

Задачи исследований:

1. Анализ методов и аппаратных средств обеспечения отказоустойчивости мультикомпьютерных систем, реконфигураций структуры ОМС при отказах, размещения программ на множестве процессорных модулей. Обоснование направлений исследований.

2. Разработка метода оперативного переразмещения программ в мультикомпьютерных системах, обеспечивающего минимизацию времени межпроцессорного обмена данными с учетом текущего распределения отказовых неоднородностей физической структуры системы.

3. Создание аппаратно-ориентированного алгоритма оперативного переразмещения программ в ОМС, реализующего разработанный метод, а также программной модели указанного алгоритма, позволяющей исследовать его функционирование при различных комбинациях отказов.

4. Разработка структурно-функциональной организации специализированного устройства оперативного переразмещения программ после возникновения отказов в ОМС, оценка аппаратной сложности устройства, сравнительный анализ временных затрат на переразмещение программ в ОМС на аппаратном и программном уровнях.

Результаты, выносимые на защиту, и их научная новизна:

1. Метод оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, основанный на диагональном распределении множества резервных модулей (скользящего резерва) непосредственно в матрице процессоров, новизна которого заключается в минимизации времени межпроцессорного обмена данными путем целенаправленного пошагового снижения отклонения указанного времени от нижней оценки наибольшей частной коммуникационной задержки, вычисляемой по длине множества статических маршрутов передачи данных с учетом текущей неоднородности физической структуры системы.

2. Аппаратно-ориенгированный алгоритм оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, отличающийся реализацией поиска резервного модуля для замещения отказавшего процессора на множестве ближайших к отказу резервных модулей.

3. Структурно-функциональная организация специализированного устройства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, отличающаяся наличием блоков переразмещения отказавших процессорных модулей и поиска кратчайшего маршрута обхода, позволяющих осуществлять быстрый поиск резервного модуля для замещения отказавшего процессора и корректировать маршруты обмена данными с учетом распределения отказовых неодно-

родностей в матрице ОМС.

Достоверность результатов диссертационной работы обеспечивается корректным и обоснованным применением аппарата математической логики, положений и методов теории множеств, графов, теории вероятностей и математической статистики, теории параллельных вычислительных систем, теории надежности, а также подтверждается имитационным моделированием с использованием зарегистрированных программных средств.

Практическая ценность результатов исследований:

1. Благодаря диагональному распределению множества резервных модулей непосредственно в матрице процессоров ОМС, созданный метод оперативного переразмещения программ позволяет значительно снизить время замещения отказавших модулей резервными (время перестройки) по сравнению с методами, основанными на введении отдельных резервных строк/столбцов (свободный захват, комбинированный захват, диагональный захват и т.п.). При этом более высокая аппаратная избыточность системы и несколько сниженный коэффициент использования резерва не являются критическими, поскольку последствия недостаточно оперативной реакции на отказ в системах рассматриваемого класса могут иметь катастрофический характер.

2. Разработанный аппаратно-ориентированный алгоритм оперативного переразмещения программ в ОМС и устройство на его основе позволяют на 2-3 порядка снизить время поиска нового варианта размещения программ в системе после возникновения отказа по сравнению с известными аналогами (реализуемыми программно), что способствует повышению оперативности реакции на отказ и, как следствие, увеличивает коэффициент готовности ОМС. При этом созданный алгоритм и аппаратные средства учитывают не только отказы процессорных модулей ОМС, но и отказы отдельных каналов связи, что существенно расширяет область их применения.

3. Аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных вентилей (ЭВ), что позволяет использовать его как в существующих, так и в перспективных мультикомпьютерных системах, содержащих десятки-сотни тысяч процессорных модулей (Titan Cray ХК7, 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 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность, сформулированы цель и задачи исследования, приведены результаты, выносимые на защиту, показана их научная новизна и практическая ценность.

В первой главе дана классификация существующих методов обеспечения отказоустойчивости мультикомпьютерных систем. Показано, что в настоящее время существует три подхода к обеспечению повышенной надежности ОМС, основанные на применении пассивной, активной и комбинированной (гибридной) отказоустойчивости на уровне отдельных процессорных модулей. Отмечено, что пассивная отказоустойчивость реализуется статическим резервированием, которое отличается

постоянной работой резерва вместе с основным модулем и не предполагает реконфигурации структуры системы при возникновении отказа (примером статического резервирования является мажорирование). Активная отказоустойчивость базируется на принципе динамического резервирования, предусматривающего замещение отказавшего модуля резервом с перекоммутацией межмодульных связей. Показано, что методы статического резервирования малоэффективны применительно к параллельным многопроцессорным архитектурам, так как не изолируют, а лишь маскируют отказы и требуют необоснованно высокой аппаратурной избыточности. Динамическое резервирование более эффективно реализуется в ОМС, однако из-за жестких ограничений на выбор резерва для замещения отказавшего модуля не дает ожидаемого повышения уровня надежности системы.

Отмечено, что наиболее перспективный подход к повышению надежности ОМС состоит в применении скользящего резервирования, являющегося разновидностью динамического резервирования. В отличие от последнего скользящее резервирование обладает значительно менее жесткими ограничениями на выбор резерва для замещения отказавшего модуля. Теоретически любой резервный модуль может заменить любой из отказавших. На практике возможность использования конкретного резервного модуля зависит от способа распределения множества резервных модулей в структуре системы, особенностей алгоритма управления реконфигурацией и аппаратных ограничений, возникающих при реализации этого алгоритма. Коэффициент использования резерва обычно оказывается значительно меньше единицы и восстановление системы при определенных комбинациях отказов становится невозможным даже несмотря на наличие неиспользованных резервных модулей.

Показано, что актуальными задачами обеспечения отказоустойчивости ОМС являются организация хранения выполняемых программ в системе и доступа к ним, а также переразмещение программ среди работоспособных процессорных модулей при возникновении отказов. Набор выполняемых программ обычно хранится в общей памяти, организационно относящейся к системе верхнего уровня (хост-компьютеру), при этом программы передаются в нужные модули ОМС всякий раз, когда происходят отказы и последующая реконфигурация. Однако такая организация требует принятия особых мер к повышению надежности хост-компьютера, общей памяти и их интерфейса с ОМС. Альтернативным вариантом является размещение избыточного множества программ в каждом из модулей, включая резервные. В этом случае смена программ после реконфигурации и переразмещения сводится к переключению процессоров на другие программы (уже загруженные в их локальную память) либо к пересылке программ между процессорными модулями. С точки зрения обеспечения надежности такой вариант более предпочтителен.

Размещение программ в ОМС осуществляется не тривиально, поскольку каждая из программ, как правило, включает совокупность подпрограмм, связанных друг с другом по данным и/или по управлению и выполняемых последовательно или параллельно. Таким образом, размещение фактически сводится к распределению множества подпрограмм по процессорам, при этом связность подпрограмм, назначенных на разные процессоры, порождает межпроцессорный обмен данными и управляющими сообщениями. Время межпроцессорного обмена (называемое также коммуникационной задержкой) вносит значительный вклад во время выполнения про-

грамм, являясь одним из источников снижения реальной производительности системы. В связи с этим размещение программ должно осуществляться с минимизацией указанного времени. При статической маршрутизации, когда заранее известны все маршруты передачи данных, время межпроцессорного обмена может быть минимизировано путем синтеза оптимальной сети маршрутов до запуска программ на выполнение. При динамической маршрутизации, когда маршруты передачи данных формируются в процессе доставки сообщений (пакетов), снижение указанного времени возможно на основе перебора различных вариантов размещения и имитационного моделирования работы системы при их использовании.

4. Отказы процессорных модулей и связей мультикомпьютерной системы обусловливают необходимость повторного размещения (переразмещения) программ на множестве работоспособных модулей, причем в случае статической маршрутизации требуется также формирование новой сети маршрутов. Задача переразмещения отличается от исходной задачи размещения программ необходимостью учета наличия неоднородностей, обусловленных отказами в структуре системы, что несколько усложняет ее решение. Переразмещение при этом должно осуществляться за минимально возможное время с тем, чтобы сохранялась оперативность восстановления системы после возникновения отказов и реконфигурации.

Анализ показал, что задача размещения программ в вычислительных системах в настоящее время решается на программном уровне, что обусловливает значительное время решения, препятствующее организации оперативного восстановления работоспособности систем рассматриваемого класса. В то же время хорошо известны аппаратные решения аналогичных комбинаторных задач, однако они не позволяют минимизировать время межпроцессорного обмена в условиях неоднородности и изменяемости физической струюуры ОМС под воздействием локальных отказов после выполнения реконфигурации с включением резервных модулей. Таким образом, исходя из изложенного, следует необходимость разработки аппаратно реализуемых методов и средств оперативного переразмещения выполняемых системой программ на множестве работоспособных модулей (с учетом резерва), обеспечивающих минимизацию времени межпроцессорного обмена данными после ликвидации отказа.

Во второй главе разработан аппаратно-реализуемый метод оперативного переразмещения программ в отказоустойчивых мультикомпыогерных системах, позволяющий минимизировать время межпроцессорного обмена данными с учетом наличия отказовых неоднородностей физической структуры системы. На базе разработанного метода создан алгоритм оперативного переразмещения программ.

В основе созданного метода и алгоритма переразмещения программ лежат следующие определения и теоретические попложения.

Каждая из реализуемых системой программ представляется множеством взаимосвязанных подпрограмм. Множество подпрограмм каждой программы описывается графом взаимодействия задач:

Ф = (*,£>, (1)

где ^ = - множество вершин, которые соответствуют отдельным подпрограммам, Е = |е(у| - множество дуг, отражающих связи между подпрограммами. Граф Ф

представляется матрицей смежности вершин: АМ = ||т(>||^, где // = 1x1. Значение элемента ту определяется числом сообщений (объемом данных), передаваемых между подпрограммами х, и х].

Топология мультикомпьютера задается графом Н = (Р1,У), где множество вершин Р1 соответствует процессорным модулям, а множество дуг V — межмодульным связям. Множество Р1 разбивается на два непересекающихся подмножества Р, = РиI, где Р = - множество основных процессоров, £ = - множество

резервных процессоров, причем фиксируется |/>| = |1| = л2, /7 = 2,3,4.....Упорядочим

множества процессоров Р и I, в виде матриц Ц/^Ц^ и соответственно. Множе-

ство Р1 представим объединением указанных матриц «через столбец» следующим образом:

' Р1\1\хР1г1ч—Р\Л„—Р\Л*

Ргл кл Ргг кг ■ ■ -Рг.о ко--Рг» к„

Р„л клР. А-1 ■ ■ -Рп ико-■ -А.. К ».

Размещение множества взаимосвязанных подпрограмм, описываемого графом Ф, в мультикомпьютере задается отображением

Р:Х->Р{, (3)

которое ставит в соответствие каждой подпрограмме один из процессоров (основной либо резервный).

Между каждой парой процессоров матрицы (2) в общем случае существует множество маршрутов передачи сообщений, которые обеспечивают разное время доставки данных между соответствующими подпрограммами. В рамках решаемой задачи интерес представляют кратчайшие маршруты, гарантирующие минимум указанного времени. Для описания множества таких маршрутов вводится матрица длин ЬМ = |Ш| , элемент ¿1,, которой численно равен длине кратчайшего маршрута

II У Нл'-л' У

между процессорами, в которых размещены подпрограммы х1 и х}.

Пусть Т - множество всевозможных отображений вида (3). Тогда задача размещения программ в мультикомпьютере будет заключаться в выборе такого отображения Рг е Т, которое соответствует следующему критерию:

(4)

где максимум в фигурных скобках представляет собой наибольшую частную коммуникационную задержку для заданного отображения /?.

Сущность созданного метода заключается в двухэтапном решении задачи переразмещения. На первом этапе вычисляется теоретически минимальная наибольшая частная коммуникационная задержка из предположения, что граф Ф размещает-

ся в мультикомпьютере без учета ограничений связности подпрограмм (дуги графа Ф «укладываются» наилучшим образом, т.е. так, что более высоким значениям ти соответствуют меньшие длины маршрутов На втором этапе определяется вариант размещения Д, который минимизирует отклонение и, таким образом, находится локальный минимум наибольшей коммуникационной задержки.

В случае наличия в мультикомпьютере отказавших процессоров размещение вычисления по формуле (4) для различных отображений вида (3) проводятся с учетом неоднородности топологической структуры. Например, при отказе процессора />, 2 выполняется перебор отображений вида:

Ри 1^Ри1г1---РгЛ„---Р1,12, Р,л 1,л Р,г1,1-■ -Р,., К»---Р,.1, Р.л'пЛ

(5)

где ^ показывает ситуацию отказа процессора р12

В этом случае учитывается, что отказавший процессор замещается резервным, например, процессором /, 2 и изменяется множество допустимых маршрутов передачи данных.

Процедура замещения отказавшего процессорного модуля резервным формализуется следующим образом.

Состояние основных процессоров р^еР описывается матрицей X -Щ- |

Г1, еслиру неисправен; ч |0, если ру исправен.

Состояние резервных процессоров 1Ц е I описывается матрицей 0 = ||^, |яхл:

(1,если/,.,, неисправен;

0 _ У У

У (0, если исправен. Матрица = содержит признаки доступности ближайшего резервного модуля к процессору ри е Р для замены:

. (1, если /■ недоступен; к. = { 7 у ^0, если 1у доступен.

Тогда с учетом введенных обозначений процедура замещения отказавшего процессорного модуля резервным будет состоять из следующих шагов: ЗАГРУЗИТЬ матрицы АМ и ЬМ; УСТАНОВИТЬ = вд = к0.= 0,1 = ЬЙ,} = ;

ЦИКЛ по всем процессорам рц е Р

ЕСЛИ Эр, еР::|?=1, то найти в матрице 0 элемент =0 такой, что

(М^МЬ'-'И;

ЕСЛИ такой вя найден, то принять <?„ =1, /„ = р1} (замещение успешно),

иначе необходим останов системы;

КОНЕЦ ЦИКЛА

Особенностью этой процедуры является то, что поиск резервного модуля для замещения отказа ограничивается ближайшими соседями (порядок их перебора не

является существенным).

В случае отказа отдельного канала связи между процессорами нарушаются маршруты транзитной передачи данных и необходимо найти новые кратчайшие маршруты обхода отказавшего канала. Для этого случая обоснована целесообразность использования алгоритма Дейкстры.

Важным этапом созданного метода переразмещения является определение теоретической нижней оценки наибольшей частной коммуникационной задержки ц ., относительно которой осуществляется минимизация времени межпроцессорного обмена при выборе варианта размещения программ согласно постановке задачи (4). Для вычисления указанной оценки используется следующий алгоритм.

1. Переписать все значения (1Ы из матрицы ЬМ в вектор ЬМ' в соответствии с условием: Уг, Фг2: < <=> > г2, где -г,,22 - порядковые номера значений с1уп(1кГ в векторе ЬМ'.

2. Переписать все значения тц * 0 из матрицы АМ в вектор АМ' в соответствии с условием: V*, Ф2г: тгУ > т]}. ог,>г2, где г„г2 - порядковые номера

значений т...,т. ■ в векторе АМ'.

3. По векторам ЬМ' и АМ* вычислить оценку ^тштах, используя формулу:

где т)р<1ги - элементы векторов АМ1 и ЬМ', расположенные в одинаковых позициях.

В дальнейшем переразмещение сводится к выполнению серии перестановок столбцов и строк матрицы АМ с целью достижения наибольшего приближения к оценке ^птах- После каждой перестановки вычисляется значение тах{т:] •<я,,у}. Если найденное значение больше предыдущего, то перестановки продолжаются от предыдущего варианта, иначе далее рассматривается текущий вариант.

С учетом изложенного алгоритм отказоустойчивого переразмещения программ в мультикомпьютерных системах будет состоять из следующих шагов:

1. Загрузить матрицы АМ и ЬМ;

2. Создать дополнительные матрицы Мх, М2, М3 размера МхЫ для хранения новых вариантов размещения после перестановок строк и столбцов матрицы АМ:

М1 - матрица, где фиксируются проверенные элементы матрицы М2, а М3 - это промежуточные матрицы.

3. Сформировать векторы АМ' и ЬМ' по матрицам АМ и ЬМ соответственно.

4. Найти оценку по формуле (6).

5. Вычислить коммуникационную задержку цй= Л1ах_{</,-тЛ для первоначального варианта размещения Д,, определяемого матрицами АМ и ЬМ.

6. Рассчитать отношение щ= , если % <Щ (где г}> 1 - пороговое зна-

/Ашптах

чение, определяющее точность решения задачи), то останов.

7. Принять // = //0иМ2 = АМ.

8. Осуществить просмотр элементов вектора АМ', начиная с элемента к = 1.

9. Пусть к-м элементом вектора АМ' является тар. Найти элемент тар в матрице М2, определяя его положение по индексам а,р.

10. Найти соответствующую элементу тар длину маршрута (1ар в матрице ЬМ.

11.Если <1а(,=\, то (так как улучшить размещение нельзя) зафиксировать текущий элемент в М2 как просмотренный, приняв М2ар=-1. Принять к = к +1 и если вектор АМ' не просмотрен до конца, вернуться к п.9, иначе перейти к п.12.

12. Начать просмотр строки ¿а матрицы ЬМ, с элемента j = l.

13. Если у" > N, строка просмотрена, перейти к п.24.

14.Если (Ыа]<(1сф} л{йа} * 0), то перейти к п. 15, иначе принять у = у" +1 и вернуться к п.13.

15. Выполнить парную перестановку столбцов/строк /<->•/? в матрице АМ и сформировать новую матрицу М1.

16.Вычислить по матрице М1 значение да-/и^}. Если то перейти к п. 17, иначе принять ] = ] +1 и вернуться к п.12.

17. Рассчитать отношение 77 = и если 77 < 77, то останов.

18. Переписать матрицу М1 в АМ.

19. Принять /4, = .

20. Зафиксировать текущий элемент тар в Мг как просмотренный: М2оф =-1.

21. Выполнить парную перестановку строк/столбцов / <->/9 в М2 и сформировать новую матрицу М}.

22. Переписать матрицу Мъ в М2.

23.Принять к = к +1 и если вектор АМ' не просмотрен до конца, вернуться к п.9, иначе считать, что все элементы проверены (останов).

24. Зафиксировать текущий элемент в М2 как просмотренный (М1ар = -1), принять к = к + 1. Если вектор АМ' не просмотрен до конца, перейш к п.9. Иначе считать, что все элементы проверены (останов).

В третьей главе разработана структурно-функциональная организация устройства оперативного переразмещения программ после возникновения отказов в ОМС на основе созданного алгоритма, выполнена оценка аппаратной сложности устройства, проведен сравнительный анализ временных затрат на переразмещение программ в ОМС на аппаратном и программном уровнях.

На рис.1 приведена структурная схема разработанного устройства переразмещения программ.

Рисунок 1 — Структурная организация акселератора отказоустойчивого переразмещения

На рис.1 приняты следующие обозначения блоков и узлов: АПРП — акселератор планирования размещения программ; МП — микропроцессор; ОП — оперативная память; КПДП — контроллер прямого доступа в память; Ппорт — последовательный порт; Прпорт — параллельный порт; УУ - устройство управления; БПОПМ — блок переразмещения отказавших процессорных модулей; БПКМ — блок поиска кратчайшего маршрута; МО - микрооперации; А - адрес.

МП контроллера работает в соответствии с программой, записанной в ОП и отслеживает работу мультикомпьютерной системы. В случае поступления через последовательный порт с управляющей ЭВМ сигнала об отказе процессорного модуля либо межпроцессорной связи соответствующий сигнал подается в контроллер и далее в соответствии с записанной в МП программой через параллельный порт поступает в специализированный мультиплексор MUX. MUX в зависимости от ситуации

отказа (отказал процессорный модуль либо межпроцессорная связь) передает необходимые для оперативной реакции данные либо в БППОМ либо в БПКМ

БПОПМ является основным блоком устройства и реализует разработанный алгоритм переразмещения программ. Функциональная схема его ядра представлена на рис.2. На этом рисунке блок 15 Р1 моделирует мультикомпьютер с основными процессорами Р и резервными процессорами Ь, блок г- матрицу исправных процессоров, а блок 17 - матрицу тэгов 0, показывающих исправность резервных процессоров. Остальные элементы и блоки служат для организации функционирования алгоритма замены отказавшего процессорного модуля резервным. Назначение этих блоков и функционирование устройства рассмотрены в диссертационной работе.

Рисунок 2 - Функциональная схема устройства оперативной замены отказавшего

процессорного модуля

В результате аналитических расчетов была получена зависимость роста аппаратной сложности разработанного устройства от размерности системы я х п, представленная в таблице 1 (выражена в эквивалентных вентилях).

Таблица 1

Размер системы п х п Аппаратная сложность, эл. И

2x2 284

3x3 1295

5x5 1388

7x7 ■ 2540

9x9 ' 4076

10x10 ■ 4988

•• 15x15 10988

50x50 40178

150x150 360178

300x300 1440178

500x500 4000178

Из приведенной таблицы следует, что даже в случае мультикомпьютерных систем высокой размерности (50 х 50 и выше) аппаратная сложность устройства не превышает возможностей современной микроэлектронной элементной базы в плане требований степени интеграции (1 млн. вентилей на одном кристалле) и устройство фактически может быть реализовано на одной микросхеме (или на отдельной печатной плате небольших размеров).

Разработанное устройство позволяет существенно снизить время, затрачиваемое на переразмещение программ, включая временные затраты на замещение отказавших процессоров и формирование новых маршрутов в обход отказавших связей, что обеспечивает повышение оперативности реакции на отказ и, как следствие, увеличение коэффициента готовности ОМС. Оценка указанного времени проводилась на основе имитационного моделирования работы устройства в специально разработанной программной среде, при этом результаты сопоставлялись с программным решением поставленной задачи. Созданная программная модель позволила имитировать работу устройства переразмещения при различных комбинациях отказов процессорных модулей и каналов связи с варьированием тактовых частот процессоров, количества модулей системы, вероятностей отказа процессоров и межпроцессорных связей.

В четвертой главе изложены результаты экспериментального исследования разработанного устройства переразмещения программ в отказоустойчивых мультикомпьютерных системах, приведённые на базе созданной программной модели, позволившие определить основные составляющие времени восстановления структуры мультикомпьютерной системы при отказе, а именно: время замены отказавшего процессора резервным; поиска кратчайшего маршрута обхода отказавшей межпроцессорной связи; выбора нового варианта размещения программ.

На рис.3 приведены графики зависимостей времени переразмещения программ от числа модулей системы, полученные в результате эксперимента для разработанного устройства и при программной реализации размещения.

I

900 ■ 800 -700 ■ 600 ■ 1 500 -

300 200 100 0

4x4 5x5 6x 6 7x7

Матрица процессоров

Рисунок 3. Зависимости времени переразмещения программ от размерности матрицы процессоров: 1 — программная реализация; 2 — аппаратная реализация

ЩШ яи .-V

88 Щ 1§НМ ФШ

Ш " I Л|р у

: щШШШщш у н

щщ --359"-.....*...... ' 390.,!

- ¡-азет шм ■тт |

• ' -- 1 йшн

Анализ зависимостей, представленных на рис.3, позволяет сделать следующие выводы. Во-первых, время переразмещения программ при использовании разработанного устройства при относительно малых размерностях мультипроцессорной системы (менее 6 х 6 ) не дает выигрыша по сравнению с программной реализацией. Во-вторых, экстраполяция полученных зависимостей показывает, что для систем большой размерности (50x50 и выше) преимущество имеет аппаратная реализация в связи со значительным увеличением вариантов перебора в матрице процессоров, что указывает на перспективность предложенного подхода для мультикомпьютеров следующих поколений, содержащих от сотен тысяч до миллионов процессорных модулей.

Данные сравнительного анализа требуемого количества эквивалентных вентилей (ЭВ), необходимых для реализации предлагаемого устройства и устройства размещения шагов обхода представлены в таблице 2.

Таблица 2

Сравнительный анализ аппаратной реализации устройства с аналогом

Количество процессоров Устройство размещения шагов обхода, ЭВ Разработанное устройство переразмещения, ЭВ

2 16129 284

3 16774,8 1295

5 17588,41 1388

7 18124,32 2540

9 18524,6 4076

10 18692,41 4988

15 19338,21 10988

Из анализа таблицы 2 следует вывод, что разработанное устройство обладает для реализации гораздо меньшим числом ЭВ, что подтверждает возможность аппаратной реализации устройства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах.

В заключении сформулированы основные результаты диссертационной работы.

В приложениях представлены листинги программных средств моделирования алгоритма переразмещения программ в отказоустойчивых мультипроцессорных системах, а также акты о внедрении результатов диссертационной работы.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

Диссертационная работа посвящена решению научной задачи, состоящей в разработке методов и аппаратных средств оперативного переразмещения выполняемых системой программ на множестве работоспособных модулей (с учетом резерва), обеспечивающих минимизацию времени межпроцессорного обмена данными после ликвидации последствий отказа.

В ходе решения этой задачи получены следующие основные результаты.

1. Создан метод оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах, использующий диагональное распределение скользящего резерва непосредственно в матрице процессоров, позволяющий минимизи-

ровать время межпроцессорного обмена данными путем целенаправленного пошагового снижения отклонения указанного времени от нижней оценки наибольшей частной коммуникационной задержки, определяемой исходя из длин заранее формируемых (статических) маршрутов передачи данных в присутствии неоднородностей, обусловленных отказами физической структуры системы.

2. На базе созданного метода разработан аппаратно-ориенгированный алгоритм оперативного переразмещения программ в отказоустойчивых мультикомпью-терных системах, состоящий в поиске резервного модуля для замещения отказавшего процессора на множестве ближайших к отказу резервных модулей и позволяющий снизить время поиска нового варианта размещенйя программ в системе после возникновения отказа.

- 3. Разработана структурно-функциональная организация специализированного устройства оперативного переразмещения программ в отказоустойчивых мульти-компьютерных системах, позволяющего осуществлять оперативный поиск резервного модуля для замещения отказавшего процессора, перераспределять подпрограммы на множестве работоспособных процессоров и корректировать маршруты обмена данными с учетом распределения неоднородностей, обусловленных отказами в матрице ОМС на основе аппаратно реализуемых матричных операций.

4. На основе имитационного моделирования установлено, что разработанный алгоритм оперативного переразмещения программ в ОМС и устройство на его основе позволяют на 2-3 порядка снизить время поиска нового варианта размещения программ в системе после возникновения отказа по сравнению с известными программно реализуемыми аналогами, что обеспечивает повышение оперативности реакции на отказ и, как следствие, увеличение коэффициента готовности ОМС.

5. Показано, что аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных вентилей (ЭВ), что меньше по сравнению с аналогичным устройством примерно на 104 ЭВ и позволяет использовать его как в существующих, так и в перспективных мультикомпьютерных системах, содержащих от десятка до сотен тысяч процессорных модулей.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ в рецензируемых научных журналах и изданиях

1. Соколова, Ю.В. Переразмещение подпрограмм в отказоустойчивых мультипроцессорных системах [Текст] / Ю.В. Соколова, Д.Б. Борзов, В.В. Минайлов // Известия вузов. Приборостроение. — Санкт-Петербург, — 2013, — №6, С. 39-44.

2. Борисенко, Ю.В. Метод и аппаратно-ориентированный алгоритм переразмещения подпрограмм в мультикомпыотерах при отказе процессоров и связей между ними [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.C. Сизов // Телекоммуникации. — Ежемесячный научно-технический, информационно—аналитический и учебно-методический журнал. — 2013, —№11. С.45-48.

3. Борисенко, Ю.В. Метод оперативного переразмещения подпрограмм в муль-тиконтроллерах с учетам отказов линков [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.C. Сизов // Известия ЮЗГУ, -2012, -№6(45), С. 50-54.

4. Борисенко, Ю.В. Акселератор переразмещения подпрограмм в отказоустойчивых мультикомпыотерах [Текст] / Ю.В. Борисенко // Интернет-журнал «Науковедение», - 2013, - №5, С. 1-9.

Патенты на изобретение

4. Патент №2447485 Российская Федерация G06F7/76, G06F17/10. Устройство поиска нижней оценки размещения в матричных системах при двунаправленной передачи информации [Текст] / Ю.В. Соколова, Д.Б. Борзов, заявл. 11.09.2009- опубл 10.04.2012, БИ №10, 2012. '

5. Патент №2451334 Российская Федерация G06F17/50. Устройство для оценки степени загрузки каналов в системах с древовидной топологической организацией при направленной передаче информации [Текст] / Ю.В. Соколова и др заявл 15.03.2011; опубл. 20.05.2012, БИ№14, 2012.

6. Патент №2470357 Российская Федерация. Устройство поиска нижней оценки размещения в полносвязных матричных системах при однонаправленной передаче информации [Текст] / Ю.В. Соколова, Д.Б. Борзов // заявл. 27.12.2010; опубл 20.12.2012, Бюл.№3.

Другие публикации

7. Соколова, Ю.В. Алгоритм переразмещения подпрограмм в отказоустойчивых мультикомпьютерах [Текст] / Ю.В. Соколова, Д.Б. Борзов, И.И. Масюков // Сборник трудов XVIII Международной научно-технической конференции «Машиностроение и техносфера XXI века. Т1». - Донецк, 2012. - С. 101-103.

8. Соколова, Ю.В. Методика пеперазмещения подпрограмм в отказоустойчивых мультикомпьютерах [Текст] / Ю.В. Соколова, Д.Б. Борзов // Сборник трудов XVEH Международной научно-технической конференции «Машиностроение и техносфера XXI века. Т1». - Донецк, 2011. - С. 86-89.

9. Соколова, Ю.В. Организация акселератора вычисления минимального значения коммуникационной задержки в полносвязных матричных мультиконтролле-рах [Текст] / Ю.В. Соколова, Д.Б. Борзов, В.В. Минайлов, A.A. Родин // Сборник материалов XVII Российской научно-технической конференции с международным участием «Материалы и упрочняющие технологии-2010». Часть 2 / Курск гос тех ун-т. Курск, 2010. С. 195-199.

10. Соколова, Ю.В. Переразмещение подпрограмм в отказоустойчивых мультикомпьютерах при отказе связей [Текст] / Ю.В. Соколова, Д.Б. Борзов // Сборник материалов X Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации». - Курск, 2012,- С. 238-240.

11. Соколова, Ю.В. Подход к обеспечению отказоустойчивости в мультиком-пьютерных системах [Текст] / Ю.В. Соколова, Д.Б. Борзов // 1нженер. Студенгсь-кий науково-техшчний журнал. - Донецьк: ДонНТУ, 2012. - № 13. - 177 с - С 84 -86. '

12. Борисенко, Ю.В. Алгоритм оперативного переразмещения подпрограмм в системах логического управления [Текст] / Ю.В. Борисенко // Сборник материалов XI Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации». - Курск, 2012-С. 228-230.

13. Соколова, Ю.В. Подход к задаче отказоустойчивого размещения процессоров в мультипроцессорной системе [Текст] / Ю.В. Соколова // тезисы докладов

Научно-технической международной молодёжной конференции «Системы, методы, техника и технологии обработки медиаконтента». — Москва, 2011. С. 93.

Свидетельства об официальной регистрации программ для ЭВМ

14. Борисенко, Ю.В. Программа для отказоустойчивого переразмещения подпрограмм в мультикомпьютерах [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.A. Поляков // Свидетельство о регистрации программы для ЭВМ №2013612984. заявл. 6.02.2013, опубл. 20.03.2013.

15. Борисенко, Ю.В. Программа для отказоустойчивого переразмещения подпрограмм с учетом отказов межпроцессорных связей [Текст] / Ю.В. Борисенко, Д.Б. Борзов, A.A. Поляков // Свидетельство о регистрации программы для ЭВМ №2013612983. заявл. 6.02.2013, опубл. 20.03.2013.

Подписано в печать_Формат 60x84 1/16.

Печ. л. 1.0. Тираж 1Чо экз. Заказ 2£ Юго-западный государственный университет.

Издательско-полиграфический центр Юго-западный государственный университет 305040, г. Курск, ул. 50 лет Октября, 94

ЮГО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Метод, алгоритмы и аппаратные средства оперативного переразмещения программ в отказоустойчивых мультикомпьютерных системах

Специальность 05.13.05 - Элементы и устройства вычислительной техники и

систем управления

На/правах рукописи

Борисенко Юлия Васильевна

04201459702

Диссертация на соискание ученой степени кандидата технических наук

Курск-2014

СОДЕРЖАНИЕ

Введение...................................................................................................................4

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

Приложение 1......................................................................................................101

Введение

Актуальность темы. Отказоустойчивые мультикомпыотерные системы (ОМС) - одно из перспективных направлений развития параллельной вычислительной техники. ОМС способны непрерывно функционировать в условиях отказа отдельных узлов и каналов связи без необходимости проведения восстановительного ремонта за счет наличия в их архитектуре специальных аппаратно-алгоритмических средств, позволяющих автоматически обнаруживать отказы, выполнять их изолирование (и замещение резервными ресурсами) и обеспечивать восстановление логической целостности коммуникационной среды. Благодаря этим свойствам ОМС могут успешно применяться в качестве основы для создания критических важных объектов (критических систем, а именно: бортовые системы управления, системы управления опасными производствами и технологическими процессами и т.п.).

Теория отказоустойчивой организации мультикомпьютерных систем достаточно хорошо разработана. Большой вклад в эту область внесли работы отечественных ученых: С.И. Баранова, Вл.В. Воеводина, В.В. Воеводина, Ю.Ю. Громова, A.B. Каляева, И.А. Каляева, И.И. Левина, В.Г. Хорошевского, И.В. Зотова, а также зарубежных ученых: М. Флинна, К. Ванга, Р. Лонг-боттома, Д. Скилликорна и др. Однако вопросы, связанные с распределением резервных ресурсов в структуре системы, локализации отказов модулей и связей, а также перераспределения множества выполняемых подпрограмм в поле работоспособных модулей в этих работах рассмотрены недостаточно.

Отказы процессорных модулей и связей ОМС приводят к появлению не-однородностей в ее физической структуре. В результате уменьшается количество возможных маршрутов передачи данных, при этом возрастает их средняя длина, что усложняет маршрутизацию данных между работоспособными модулями после реконфигурации системы. Как следствие, увеличивается среднее время межпроцессорного обмена и снижается реальная производительность системы. Одним из путей преодоления указанных послед-

ствий отказов является переразмещение выполняемых системой программ на множестве работоспособных модулей с минимизацией времени межпроцессорного обмена. Переразмещение должно осуществляться за минимально возможное время с тем, чтобы сохранялась оперативность восстановления системы после возникновения отказов.

Задача переразмещения имеет высокую вычислительную сложность из-за ее комбинаторного характера, поэтому, учитывая жесткие временные ограничения, целесообразно полностью перенести ее решение на аппаратный уровень. Аппаратные решения аналогичных комбинаторных задач хорошо известны, однако они не позволяют минимизировать время межпроцессорного обмена в условиях неоднородности и изменяемости физической структуры ОМС под воздействием локальных отказов после выполнения реконфигурации с включением резервных модулей.

Таким образом, существует противоречие между объективной необходимостью повышения отказоустойчивости мультикомпыотерных систем и недостаточными возможностями существующих средств по обеспечению оперативной реакции на отказ с сохранением высокой реальной производительности системы.

В соответствии с вышеизложенным актуальной является научная задача разработки методов и аппаратных средств оперативного переразмещения выполняемых системой программ на множестве работоспособных модулей (с учетом резерва), обеспечивающих минимизацию времени межпроцессорного обмена данными после ликвидации последствий отказа.

Цель диссертации: снижение времени восстановления структуры муль-тикомпьютерной системы после возникновения отказов путем разработки метода и аппаратных средств оперативного переразмещения выполняемых программ на основе целенаправленной пошаговой минимизации отклонения времени межпроцессорного обмена данными от теоретической нижней оценки этого времени.

Объект исследования: отказоустойчивые мультикомпыотерные системы.

Предмет исследования: методы, алгоритмы и аппаратные средства размещения программ в отказоустойчивых мультикомпыотерных системах.

Работа выполнена по плану инициативных НИР 2009-2013 г.г. кафедры информационных систем и технологий Юго-Западного государственного университета.

Задачи исследований:

1. Анализ методов и аппаратных средств обеспечения отказоустойчивости мультикомпыотерных систем, реконфигураций структуры ОМС при отказах, размещения программ на множестве процессорных модулей. Обоснование направления исследований.

2. Разработка метода оперативного переразмещепия программ в мультикомпыотерных системах, обеспечивающего минимизацию времени межпроцессорного обмена данными с учетом текущего распределения отказовых неоднородностей физической структуры системы.

3. Создание аппаратно-ориентированного алгоритма оперативного переразмещения программ в ОМП, реализующего разработанный метод, а также программной модели указанного алгоритма, позволяющей исследовать его функционирование при различных комбинациях отказов.

4. Разработка структурно-функциональной организации специализированного устройства оперативного переразмещения программ после возникновения отказов в ОМС, оценка аппаратной сложности устройства, сравнительный анализ временных затрат на переразмещение программ в ОМС на аппаратном и программном уровнях.

Результаты, выносимые на защиту, и их научная новизна:

1. Метод оперативного переразмещения программ в отказоустойчивых мультикомпыотерных системах, основанный на диагональном распределении множества резервных модулей (скользящего резерва) непосредственно в

матрице процессоров, новизна которого заключается в минимизации времени межпроцессорного обмена данными путем целенаправленного пошагового снижения отклонения указанного времени от нижней оценки наибольшей частной коммуникационной задержки, вычисляемой по длине множества статических маршрутов передачи данных с учетом текущей неоднородности физической структуры системы.

2. Аппаратно-ориентированный алгоритм оперативного переразмещения программ в отказоустойчивых мультикомпыотерных системах, отличающийся реализацией поиска резервного модуля для замещения отказавшего процессора на множестве ближайших к отказу резервных модулей.

3. Структурно-функциональная организация специализированного устройства оперативного переразмещения программ в отказоустойчивых мультикомпыотерных системах, отличающаяся наличием блоков переразмещения отказавших процессорных модулей и поиска кратчайшего маршрута обхода, позволяющих осуществлять быстрый поиск резервного модуля для замещения отказавшего процессора и корректировать маршруты обмена данными с учетом распределения отказовых неоднородностей в матрице ОМС.

Достоверность результатов диссертационной работы обеспечивается корректным и обоснованным применением аппарата математической логики, положений и методов теории множеств, графов, теории вероятностей и математической статистики, теории параллельных вычислительных систем, теории надежности, а также подтверждается имитационным моделированием с использованием зарегистрированных программных средств.

Практическая ценность результатов исследований:

1. Благодаря диагональному распределению множества резервных модулей непосредственно в матрице процессоров ОМС, созданный метод оперативного переразмещения программ позволяет значительно снизить время замещения отказавших модулей резервными (время перестройки) по сравнению с методами, основанными на введении отдельных резервных

строк/столбцов (свободный захват, комбинированный захват, диагональный захват и т.п.). При этом более высокая аппаратная избыточность системы и несколько сниженный коэффициент использования резерва не являются критическими, поскольку последствия недостаточно оперативной реакции на отказ в системах рассматриваемого класса могут иметь катастрофический характер.

2. Разработанный аппаратно-ориентированный алгоритм оперативного переразмещения программ в ОМС и устройство на его основе позволяют на 2-3 порядка снизить время поиска нового варианта размещения программ в системе после возникновения отказа по сравнению с известными аналогами (реализуемыми программно), что способствует повышению оперативности реакции на отказ и, как следствие, увеличивает коэффициент готовности ОМС. При этом созданный алгоритм и аппаратные средства учитывают не только отказы процессорных модулей ОМС, но и отказы отдельных каналов связи, что существенно расширяет область их применения.

3. Аппаратная сложность разработанного устройства для всех практически значимых случаев не превышает 106 эквивалентных вентилей (ЭВ), что позволяет использовать его как в существующих, так и в перспективных мультикомпьютерных системах, содержащих десятки-сотни тысяч процессорных модулей (Titan Cray ХК7, IBM BlueGene/Q и т.п.).

1 Анализ методов и средств обеспечения отказоустойчивости мультикомпыотерных систем

В главе рассмотрена классификация методов обеспечения отказоустойчивости мультикомпыотерных систем, структурные модели отказоустойчивых мультикомпыотеров, проведён анализ методов размещения задач в параллельных системах.

1.1 Методы, модели и алгоритмы обеспечения отказоустойчивости в

мультикомпютерных системах

Применение программируемых логических мультиконтроллеров в устройствах группового управления критических важных объектов (критических систем), нарушение работоспособности которых в результате отказа вызывает большие материальные издержки, возможно только в том случае, если будет обеспечиваться непрерывное управление, толерантное к отказам элемента устройства, то есть если устройства будут обладать свойством отказоустойчивости.

В рамках работы [1] под отказоустойчивостью понимается свойство устройства выполнять возложенные на него функции при отказах его элементов.

Под с1-отказоустойчивым устройством понимается устройство, которое способно противостоять (парировать) отказам с! элементов.

В работе [2] для обеспечения отказоустойчивости использовалась структурная и информационная избыточность.

В результате развития теории надежности были сформулированы три подхода к построению отказоустойчивых устройств, а именно: подход, основанный на использовании активной отказоустойчивости; подход, основанный на пассивной отказоустойчивости; подход, учитывающий или сочетающий активную и пассивную отказоустойчивость. Подход, основанный на активной отказоустойчивости, использует динамическое резервирование с контро-

лем функционирования работающих устройств. Пассивная отказоустойчивость обеспечивается пассивным резервированием устройства (например, мажорированием).

Проведенные исследования, представленные в [3-6] показали эффективность скользящего резервирования со сдвигом для структурной самоорганизации матричных структур. В отличие от общего скользящего резервирования оно упрощает построение коммутаторов и сохраняет однородность структуры и локальность связей элементов.

Статические методы обеспечения отказоустойчивости малоэффективны для применения в параллельных многопроцессорных архитектурах, поскольку они маскируют отказы и требуют значительной аппаратурной избыточности. Так, для трехканальной мажоритарной структуры требуются дополнительные аппаратурные затраты, превышающие более чем вдвое основное оборудование.

Динамические методы обеспечения отказоустойчивости эффективно реализуются в однородных структурах при незначительных аппаратных затратах. Скользящее резервирование, являющееся лучшим инструментом повышения надежности устройств из однотипных элементов, дает наибольший выигрыш в надежности. Введение резервной строки или столбца элементов позволяет обеспечить более высокую надежность в сравнении с мажоритарными трёхканальными структурами. Исключение отказавших процессорных элементов и подключение резервных осуществляется с помощью алгоритмов реконфигурации. Под восстановлением исходной логической структуры связей распределенными средствами управления понимается структурная самоорганизация многопроцессорного устройства. При этом структурная самоорганизация достигается с помощью дополнительного встраиваемого в структуру мультипроцессора коммутатора, обеспечивающего коммутацию каналов между исправными процессорными элементами логической структуры. При разработке топологии мультипроцессорной системы этап структурной само-

организации сводится к выбору топологии отказоустойчивого устройства с требуемой отказоустойчивостью, в которой возможно размещение исходной логической структуры.

Согласно [45] организация хранения и доступ к распределенным программным модулям задач могут быть осуществлены несколькими способами: хранением программных модулей в общей памяти для устройства и их перем