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

ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ РАН

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

ДЕНИСОВ Сергей Геннадьевич

уда 681.3.06

РАЗРАБОТКА МЕТОДОВ ОБЕСПЕЧЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ПЕРЕРАСПРЕДЕЛЕНИЯ ЗАДАЧ

Специальность: 05.13.01 - Управление в технических, системах 05.13.13 - Вычислительные машины, комплексы, системы и сети.

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

Москва - 1992

Работа выполнена в Институте проблем породами информации РАН.

Научный руководитель: ' .

доктор технических наук, профессор В.Г.Лазаров .. -•■-.

I

Официальные оппоненты: доктор технических наук, профессор Э.В.Евреинов, кандидат технических наук, ст. н. с. Ф.И.Пепинов

Ведущая организация: Институт проблем управления РАН.

Защита состоится "//" &1992 г. в ¿0 часов з заседании специализированного Совета Д.003.29.01 при Институ-проблем передачи информации РАН по адресу: 101447, Моею ГСП-4, ул.Ермоловой, 19.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН

Автореферат разослан "/О" СМ^Хл? 1992.

Ученый секретарь ; специализированного Совета •

д.т.н. С.Н.Степанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Проблемой повышения надеиюсти многопроцессорных вычислительных систем (МПВС) занимались многие отечественные зарубежные ученые, в том числе С.М.Доманицкий, М.А.Гаврилов, Э.В.Евреинов, Я.А.Хетагуров, Р.Кэмпбел, Д.Рассол, Д.Риннолс.

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

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

Идея работы заключается в использовании модели параллелизма CSP (Communicating Sequential Processes - взаимосвязанных последовательных процессов) для формального описания исследуемых заданий и обеспечения их отказоустойчивого выполнения путем восстановления после отказов при сокращающемся числе процессорных модулей.

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

последовательных процессов.

Розультати. выносимые на защиту состоят в ело дующем:

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

формализация отказоустойчивого размещения задач по процессорным модулям в распределенной вычислительной системе к метод построения размещения задач;

- теоретическое обоснование стратег™ расстановки контрольных точек во время функционирования программных комплексов, реализованных в соответствии с.моделью параллелизма СБР;

- метод восстановления функционирования программных комплексов в (ШВС при отказах процессорных модулей.

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

Практическая ценность работы состоит в следующем:

- разработаны и программно реализованы алгоритмы построения расписаний и отказоустойчивых размещений задач;

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

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

• Апробация работы. Основные положения и- результаты диссертационной работы докладывались и обсуждались на 1-м

А

бсосоюоном семинаре "Логические метода построения однородных и систолических структур" (Москва, 1988), V Королевских чтениях 11-ой республиканской конференции "Фундаментальные и прикладное проблемы космонавтики" (г.Киов,1990), Всесоюзном совещании-семинаре "Микропроцессорные систеш управления технологическими процессами в ГПС" (Одесса,1990), VIII и X советско-итальянских семинарах "Сети пакетной коммутации ЭВМ" (Москва,1989 и 1991), 1-ой международной конференции советской транспьютерной ассоциации (Звенигород 1991), а также на научных семинарах Института проблем передачи информации РАН.

Структура и объем работы. Диссертация состоит из введения, • четырех глав, заключения, списка литературы из 10? наименований и приложения, (основной текст работы занимает 150 машинописных стрэниц, включая 37 рисунков и 11 таблиц.

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

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

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

1) обнаружение отказов и идентификация отказавших мод:,'лей аппаратуры, например процессорных модулей;

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

3) перезапуск вычислительного процесса.

Методы восстановления могут быть классифицированы по

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

При описании и проектировании параллолышх алгоритмов, предназначенных доя шогопроцоссорлшх систем с распределенной памятью, предлагается использовать модель параллелизма CSP (Communicating Sequential Processes - взаимодейству:ощих последовательных процессов), которая позволяет снять ряд проблем (например, проблемы синхронизации и разделешш общих ресурсов),- характерных для систем параллельной обработки.

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

Таким образом, основным критерием отказоустойчивости выполнения глобального задания 0=--(Р{) (i=1,u), реализующего общий алгоритм, является выполнение следующих двух условий:

1) выполнение всех частных алгоритмов, реализуемых процессами

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

Т(П>*Тзад. (1)

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

1) находятся расписания Rm~d(Q),Em'd+1(П),...,^(П) выполнения глобального задания П=(Р^} (t=l,n) для системы, включающей к (k=m-d,m) работоспособных ПМ.

2) определяется размощоние процессов по ПМ, которое двя любого числа k (m-cWi&n) Ш обеспечивает выполнение расписания . без дополштольной загрузга ГОЛ.

3) определяется механизм переключения функционирования системы

б

с расписания П/г(0) на расписагаю (П) при m-d<kGi, который обосиочивал критерий отказоустойчивости.

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

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

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

Для того (чтобы после отказа одного из ГИЛ, вычислительная

система могла перейти с работы по расписанию .....Fi^}

на работу по расписанию Rm_1={R^~1,...T§Z]} ■ (R^ -расписагаю работы к-го ПМ в соответствии с расписанием яЬ, необходимо установить взаимнооднозначное соответствие кавдого из ноотказавших Ш со строками расписания Rm~1. Это соответствие мокет быть задано жиприцей разлещегтя Х={х^j}, где

xl.J

1,если процессы размещенные в J-м Ш, включают все процессы, поречислешше в . О,в противном случае

/

с

( ^ТТгГТ , ]=~Т7т !1и>юрол Н^Ш матрицы X будем называть квадратней матрицу,' получештую из X вычеркиванием J-vo столбца. Б:/де?4 говорить, что матрица К обладает свойством отказоустойчивости, осла для каадого минора М^Ш, J-'\ ,ш можно выделить совокупность элементов {ху и>, называемую системой различных представителей, состояшую из ш-1 элемента, каждый из которых равен единице, причем в каждом столбце и каждой строке М"ЧХ] находится ровно по одному элементу ця этой совокупности.

Наличие системы различных представителей в миноре М^Ш выражается условием (2), т.е. неравенством перланетт (сумд; всех диагональных элементов матрицы) этого минора нулю

Рег(М^СХ])>0 ( (2)

Предлагается алгоритм нахождения матрицы размещения X, удовлетворяющей условию (2). Этот алгоритм основан на теоре:.:з Фробониуса-Конига, согласно которой перманента квадратной матрицы й-го порядка равняется нулю тогда и только тогда, когда в исходной матрица, имеется нулевая подматрица размером зхг, причем з+1>й.

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

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

нэ позволяют использовать этот метод в чистом виде. К этим

-----

особенностям в первую очередь относятся:

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

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

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

Выполнение каждого процесса Р^ может быть представлено цепочкой сменяющих друг друга состояний:

ж0 __ Ж1 хг

геТ, (3)

{ ' "I ' £ ---- ' л£

где каидое состояние щ определяется содержимым паямятн и значениями регистров Ш, в котором данный процесс выполняется. Будем говорить, что состояние ае" старше состояния зе^ и обозначать ге">згУ, если в цепочке (3) состояние гс'у находится правее, чем ге^.

Набор состояний всех процессов, соответствующих заданию Я, на произвольном шаге г расписания определяет состояние задания для данного шага этого расписания, т.е. БШ.И^.г).

Пусть для произвольных шагов и и ю соответственно расписаний В^ и И771-1 имеем:

ЗШ.^иЫ^аЛу).....гЫнР.и).....эе^СН^.у)};

Б (О.^-1 ,ю)={ае1 (И^-1 ,ю),I.. ,ге£ (Нт~1 ,.,ю)). где ге^Р^.у), ге((Нт~1.ш) е (зес).

Будем говорить, что состояние Б(П,Ят,и) старше состояния Б(П,Нт_1,ш), т.е. 8(П,Ет,у)^3(П,Кт~1,и), если для любого процесса^Р, ,п, справедливо

эг^тР.и) > эг{(Ет_1,ш), где знак ">" обозначает отношешнэ старшинства, введенное выше и определяемое на основе .известной для процесса Р, последовательности (3), а знак "=" - совпадение соответствующих состояний.

Сформулирован критерий выбора точки восстановления для

СЗД^Н!!'1?. У."НТрОЛЬПОЙ тпччм:

Шаг w расписания Rm~1 является точкой восстановления, соответствующей шагу v расгшсания Пгл о ели

SCn.R^.yXSin.R^.iyH ).

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

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

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

ЗАКЛЮЧЕНИЕ '

В диссертации дано решение актуальной задачи -разработано математическое и программное обеспечение средств отказоустойчивого функционирования процессов в

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

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

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

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

ю

3. Исследованы различные» отношв1шя между процосс&ми. допускаемые моделью параллелизма CSP и выявлонн с луча недетерминизма выполнения процессов, включающих параллельны команда и команда ввода-вывода. •

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

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

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

7. Предложенные в работе алгоритмы реализованы в вид; комплекса программ на персональном компьютере IBM PC AT. Сбщй объем разработанных программ составил более 5000 оператороз языка С.

8. Разработаны основные принципы операционной системы, реализующей "данный метод отказоустойчивости, которые бит эксперменталЬно реализованы на сети транспьютеров.

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

1. Денисов С.Г. Метод реализации модели параллелизма Оккама -а многопроцессорной вычислительной системе. /Всесоюзный семинат "Микропроцессорные системы управления технологическими процессами в ГПС", Одесса,.1990, с.54-55.

2. Денисов С.Г. Мотода роализации алгоритма имитационной модолл реального вромсни в многопроцессорной вычислительной снстомо. /V Королевские чтения II республиканской конфоронции "Фундаментальные основы космонавтики", Киев, 1990, с.29-30.

3. Денисов С.Г. Организация отказоустойчивых вычпслешгй в многопроцессорной вычислительной системе при наличии ограничений на объем локальной памяти процессорных модулей./Управление в распределенных интегральных сетях, Москва. "Наука", 1991, с. 65-74.

4. Денисов С.Г., Турута E.H. Восстановление вычислительных процессов в многопроцессорной вычислительной системе на основе их реактивизации./Управление ресурсами в интегральных сетях, Москва, "Наука", 1991, сс.117-129.

5. Денисов С.Г., Обеспечение отказоустойчивости

вычислительной системы системы методом частичного дублирования процессов./ Межвузовский сборник "Анализ и проектирование программного обеспечения и аппаратных средств 'вычислительных систем и сетей ЭВМ для САПР, ГАП и АСУ",М.: МИЭМ, 1991, с.27-31.

6. Денисов С.Г., Турута E.H. Отказоустойчивое статическое размещение' процессов при решении задач имитационного моделирования в многотранспьютерной системе. /XIV Всесоюзный симпозиум . "Логическое управление с использованием ЭВМ". Феодосия, 1991, с.186-190.

7. Панфилов П.Б. Денисов С.Г. Реализация алгоритмов имитационного моделирования , в многотранспьютерной вычислительной системе. /1-ая международная конференция соетской транспьютерной ассоциации, Звенигород, 1991,с.66-67.

8. Турута E.H., Денисов С.Г. Размещение точек восстановления отказоустойчивых вычислений в однородной системе. //Логические методы построения однородных систолических структур. Труды I всесоюзного семинара, М. 1988, с.152-154.

9. Турута E.H. Денисов С.Г. Обеспечение отказоустойчивости многтранспьютерных систем на основе перераспределения задач. /1-ая международная конференция ' советской транспьютерной ассоциации, Звенигород, 1991, с. 47.