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

Л

Российская Академия Наук Институт Проблем Управления

На правах рукописи УДК 681.324

Тепляков Александр Владимирович

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

Специальность 05.13.13 - Вычислительные машшы, комплексы,

системы и сети 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Москва 1992

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

Научный руководитель - доктор технических наук, профессор

Игнатущенко В.В. Официальные оппоненты: доктор технических наук, профессор

Барский А.Б.

кандидат технических наук, с.н.с. Максимов В.И.

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

Защита состоится "_" "_" 1992 г. в _ час.

на заседании специализированного совета Д OCS.68.OI Института проблем управления по адресу:

117312, г. Москва, Профсоюзная, 65. Телефон совета: 331-93-29.

С диссертацией можно ознакомится в библиотеке Института проблем управления.

Автореферат разослан "_" "_н 1992т.

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

к.т.н. Юркевич Е.В.

Л' 1

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

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

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

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

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

Разработка достаточно точных математических моделей и 1лгоритмсв для анализа функционирования параллельных ВС на задаваемых пользователем комплексах взаимосвязанных работ (КВР) :-с случайным временем выполнения каждой работы (процесса) в

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

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

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

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

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

Практическая ценность результатов работы состоит в том что они позволяют прогнозировать время выполнения конкретны; комплексов взаимосвязанных работ на параллельных вычислительны; ресурсах в условиях их сбоев и отказов априорно, на этап! проектирования, выбора структуры и конфигурации параллельно! вычислительной системы, а также оценить эффективное:

использования структурного резервирования процессоров ВС илм временного резервирования работ каждого конкретного КВР.

Практическая реализация. Разработанные к программно реализованнные математические модели использовались для оценки времени выполнения комплекса задач верхнего уровня АСУ ТП атшных электростанций и задач управления сложными подвижными объектам! на многопроцессорных вычислительных системах серии ПС при различных методах резервирования их вычислительных ресурсов и процессов.

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

Публикации. Основное содержание диссертационной работы изложено в 4 опубликованных научных работах.

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 103 стр., содержит список литературы из 58 наименований, включает 15 рис.

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

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

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

- графовой модели заданного комплекса' взаимосвязанных забот (КВР), характеризуемого специальными, нетрадиционными тараметрами параллелизма ;

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

Комплекс взаимосвязанных работ , который требуется

вьщолнить на параллельной ВС, задается в виде простого ориентированного графа С(А,Г) с конечным числом N вершин, где

вершина а^А соответствует J-й работе (J=1.2.....И), а

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

Работа а^ считается работой-предшественником по отношению к а,., если имеется дуга (а^.ац)€Г; в этом случае а0 является

^ J ь 5

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

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

Полагаем, что выполнение работы на процессоре завершается событием Cj, если во фронт F поступает i работ. Для определенности и уменьшения размерности рассматриваемых моделей вводится следующее ограничение: число работ-преемников любой работы а^ не превышает трех, т.е. OsísS.

Событиям Cj приписываются вероятности их появления «j, которые и яЗляшся паролешроли. параллелизм КВР; значения определяются по графу G еле душим образом:

* N

з

4 х о^з; j = гл ; 2 «. = 1;

К 1=о

где » если после выполнения работы с номером з

наступает событие Cj, и M1;J=0 в противнем случае.

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

0*aQ+1 *«l+2*a2+3*«-j=1;

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

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

-во-первых, предполагается, что события сбоев и отказов являются гораздо более редкими, чем случаи "нормального" выполнения КВР, при котором временное резервирование работ может дать существенное уменьшение TD.,„;

БЫЛ

-во-вторых, заранее неизвестно, насколько это уменьшение Твып "Р11 вРеменном резервировании работ будет больше или меньше возможного увеличения времени выполнения КВР за счет перезапусков большего количества работ. Этот эффект зависит от степени параллелизма КВР, объема вычислительных ресурсов параллельной ВС и даже от того, на какой именно работе произошло событие сбоя или отказа процессора.

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

При структурном резервировании, использование одного дублированного или троированного вычислительного комплекса для выполнения любого заданного параллельного КВР приводит к последовательной реализации этого КВР и может бить исследовано на рассмотренной в главе I базовой математической модели с числом обслуживающих приборов (ОП) d=^=I, где m-общее число процессоров, K-кратность резервирования. Если же т>К (а число m выбирается обычно кратным К), то базовая математическая модель интерпретирует параллельное выполнение КВР из N работ на d=^>I

обслужи ваших приборах, если выполнение KBF произошло без «5оев или отказов.

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

а) назначаем в КВР конкретную работу а,, при выполнении которой (или ее копии) с верпашосшю "7"" происходит сбой (отказ) процессора, обслуживающего эту работу;

б) на основе разработанных математических моделей определяется среднее время Tq . выполнения фрагмента. КВР от начальной работы до работы 'а^ включительно (лс завершению которой "обнаружен" сбой или отказ);

в) на основе тех же математических моделей определяется среднее время 1j ^ выполнения фрагмента КВР от работы а j до работы aN включительно; при моделировании события отказа предусматривается, что для определения 'Г, ^ число ОП в математических моделях должно быть уменьшено на единицу;

г) сумияру я Tq j Tj голу чаем среднее время выполнения . КВР с учетом выполнения дополнительных работ, связанных с

обнаружением сбоя или локализацией отказа.

Разумеется, в качестве работы аj, на которой "обнаружен" сбой или отказ, может рассматриваться любая из работ модели КВР, т.е. изложенный прием может быть повторен на тех же салиъ математических моделях ?! раз (по числу работ в КВР). В результате может быть получено множество из N значений времени Твып, которые зависят не только от структуры КВР, параметров его параллелизма, объема вычислительных ресурсов ВС, но и детализированно характеризуют влияние сбоя/отказа на общее время выполнения данного КВР.

Такая детализация имеет принципиальное значение для оценки Твып ПРИ временном ]>езервироьании работ, где сбои или отказы могут быть обнаружены с запаздыванием; в результате этого может

потребоваться перезапуск большего количества работ, чем при структурно» резервировании устройств и процессов.

Этот асе подход может бкть попользован для вычисления Твнп яри нескольких событиях сбоев/отказов: если это событие зафиксировано по заверц'ешт некоторой последу melt рабе ты af, то в этом случае:

г№ в Tjif и Tf(N учитываются дополнительные временные затраты на обнаружение и локализацию ебоев/откасюв.

Принципиальная особенность вычислений ?0> j и Гj заключается в том, .что в момент завершения некоторой работы а^ система может находиться в одном из мс.колъкш. состоятся, которые необходимо определить и уштавзть при расчете как так к Tj н. -Это означает, что в отличие от базовой математической модели с единственным начальным состоянием (выполнение "начальной" работы а,) и единственным поглощающим состоянием (завершение выполнения "коночной" работа я^), эассматриваемая методика вычисления времени' выполнения НВР в условиях сбоев и отказов вычислительных ресурсов ВС должна зключагь в себя:

' -определение вектора возможных состояний системы в момент завершения любой работы вычисление TQ j по базовой

1атематической меде ни с учетом множества этих состояний;

-использование указанного множества состояний и «роятностей пребывания в них в качеств« начального вектора ¡сстояний базовой математической модели для расчета TjtNc ювыми значеы?.™? параметров модели, в частности- с измененным юличеством ^служивавдих приборов (чгс имеет место при юбытиях отказов процессорных модулей).

Подход, описанный в диссертации, является частным случаем 1етода сопряжения математических полелей обры ваших ся арковских процессов, разработанного С.Матвиенко (Российский ДН).

Обозначим базовую математическую модель (БММ) выполнения BP на параллельной ВС следущим образом: S(mJI,n,ai),где

m - число процессоров ВС; ;

N - количество работ KBP; 1<Н<«

и - интенсивность обслуживания работ; 0<ц<1

параметры параллелизма КВР, 1=Т73.

Обозначим событие сбоя или отказа на ;-ой работе КВР (UJíll) через где при событии сбоя и при событии

отказа; БММ с однократным событием сбоя_ или отказа при выполнении КВР обозначим следующим образом: БШ.И,^,«^ЛЮ).

Введены интервалы постоянства- интервалы времени, в течение которых алгоритмы и/или параметры функционирования БММ не изменяются:

-1г0»г ^1- интервал обслуживания первых } работ КВР, включая работу, на которой зарегистрирован сбой/отказ;

'V" интервал обслуживания остальных работ КВР, включая повторное выполнение ,7-ой работы, на которой зарегистрирован сбой/отказ.

Функционирование БММ БОп.Н.ц,«^) описывается однородным обрывающимся марковским процессом (МП) ХШ, задаваемым вектором вероятностей начальных состояний этого процесса (начальным вектором) и матрицей А интенсивностей переходов.

Введено понятие макросостояния МП. Макросостояние Хз МП ХШ объединяет все состояния МП, в которых может находиться система к рассматриваемому любому моменту времени I после выполнения ровно в работ,

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

Вектор *0- начального распределения рассматриваемого МП ХШ содержит число элементов, равное числу

макросостояний и имеет следующий вид- *£=(0,...,0,?^ о),

где вектор о=(0,0,..^,0,1) содержит элементы по числу' состояний БШ в макросостоянии Х0. ^

МП ХШ, описывающий модель 5(т,Н,ц,а1,*3(к)) исследуется на основе того же метода анализа, что и система БСт.Н.ц,^). Для этого формируем из множества макросостояний (Х0,...,ХЫ1) системы Б два подмножества: .....X.) и

. ( • ) О Л

время выполнения комплекса работ (в нашем случае- из КН работ) будет тем меньше, чем меньше время простоев процессоров параллельной ВС, т.е. чем "полнее" будет загружена система в каждый момент времени.

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

-во-первых, предполагается, что события сбоев и отказов являются гораздо более редкими, чем случаи "нормального" выполнения КВР, при котором временное резервирование работ может дать существенное уменьшение Т„11тт;

хзЬШ

-во-вторых, заранее неизвестно, насколько это уменьшение Твып 1ТРИ временном резервировании работ будет больше или меньше возможного увеличения времени выполнения КВР за счет перезапусков большего количества работ. Этот эффект зависит от степени параллелизма КВР, объема вычислительных ресурсов параллельной ВС и даже от того, на какой именно работе произошло событие сбоя или отказа процессора.

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

При структурном резервировании, использование одного дублированного или троированного вычислительного комплекса для выполнения любого заданного параллельного КВР приводит к последовательной реализации этого КВР и может быть исследовано на рассмотренной в главе I базовой математической модели с числом обслуживающих приборов (ОП) <3=^=1, Где ш-общее число процессоров, К-кратность резервирования. Если же т>К (а число т выбирается обычно кратным К), то базовая математическая модель интерпретирует параллельное выполнение КВР из N работ на

обслуживающих приборах, если выполнение КВГ произошло без сбоев или отказов.

Традиционный путь для учета влияния событий сбоя/отказа н& время выполнения КВР- введение в математическую модель вероятности этих событий для каждого из процессоров на любой работе КВР- приводи? к существенному увеличению размерности стохастической матрицы, с одной стороны, а с другой - дает весьма "размытую" (с большой дисперсией) оценку времени выполнения КВР. В альтернативу этому традиционному подходу впервые предлагается следующий алгоритмический подход:

а) назначаем в КВР конкретную работу а,, при выполнении которой (или ее копии) с бергш/ностьп "7"" происходит сбой (отказ) процессора, обслуживающего эту работу;

б) на основе разработанных математических моделей определяется среднее время Т0 . выполнения фрагмента КВР от начальной работы до работы'а^ включительно (по завершешю которой "обнаружен" сбой или отказ);

в) на основе тех же математических моделей определяется среднее время Т^ ¡, выполнения фрагмента КВР от работы а^ до работы а^ включительно; при моделировании события отказа предусматривается, что для определения Т^ ^ число ОП в математических моделях должно быть уменьшено на единицу;

г) суммируя 'Гс J ТJ■ у, получаем среднее время выполнения КВР с учетом выполнения дополнительных работ, связанных с обнаружением сбоя или локализацией отказа.

Разумеется, в качестве работы а^ на которой "обнаружен" сбой или отказ, может рассматриваться любая из работ модели КВР, т.е. изложенный прием может быть повторен на тех же самих математических моделях Н раз (по числу работ в КВР). В результате может быть получено множество из N значений времени Твып, которые зависят не только от структуры КВР, параметров его параллелизма, объема вычислительных ресурсов ВС, но и детализирование характеризуют влияние сбся/отказа на общее время выполнения данного КВР.

Такая детализация имеет принципиальное значение для оценки Твып ПРИ временном ^зервирсвании работ, где сбои или отказы могут быть обнаружены с запаздыванием; в результате этого может

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

Этот же под/од может быть использован для вычисления :ТВЩ1 яри нескольких событиях сбоев/отказов: если это событие зафиксировано по завершению некоторой последу оде]! ¡».беты то в этом случае:

твшгт6,/т,5. Л Л гдл в и учитываются дополнительные временные

затраты на обнаружение и локализацию обоев/откасюв.

Принципиальная особенность вычислений и

Т^ заключается в том, чуо в момент заверивши некоторой работы

а^ система может находиться в одном из нссколышт. состояний,

которые необходимо определить я учитывать при расчете как Т0

так и Т^ н. Это означает, что в отличие от базовой

математической модели с единственным начальным состоянием

(выполнение "начальной" работа а,) и единственным пеглощаадим

состоянием (завершение выполнения "конечной" работа а^,),

рассматриваемая методика вычисления времени выпотеют КВР в

условиях сбоев и отказов вычислительных ресурсов ВС должна

зключать в себя:

-определение вектора возможных состояний системы в момент

завершения любой работы а^, вычисление Т0 ^ по базовой

математической надета с учетом множества этих состояний;

-использование указанного множества состояний и

вероятностей пребывания в них в качеств?, начального вектора

;сстояний базовой математической модели для расчета Т^ нс

ювыми значениями параметров модели, в частности- о измененным

:оличеством обслуживающих приборов (что имеет место при

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

Подход, описанный в диссертации, является частным случаем

ютода сопряжения математических моделей эбрыващихся

¡арксвоких процессов, разработанного С.Матгаенко (Российский

ЯН).

Обозьачим базовую математическую модель (БММ) выполнения ВР на параллельной ВС следующим образом: 3(шЛ1,г1.а1) ,где т - число процессоров ВО; гш»1; N - количество работ КВР; 1«Н<»

и - интенсивность обслуживания работ; 0<ц<1

параметры параллелизма КВР, 1=ТТЗ.

Обозначим событие сбоя или отказа на J-ой работе КВР n«J*Nj через J(kJ, где к=0 при событии сбоя и при событии отказа; ШМ с однократным событием сбоя_ или отказа при выполнении КВР обозначим следующим образом: S(m,N,n,a1.J(k)).

Введены интервалы постоянства- интервалы времени, в течение которых алгоритмы и/или параметры функционирования БММ не изменяются:

-[t0,tj]- интервал обслуживания первых J работ КВР, включая J-ю работу, на которой зарегистрирован сбой/отказ;

-it^.tjj]- интервал обслуживания остальных работ КВР, включая повторное выполнение J-ой работы, на которой зарегистрирован сбой/отказ.

Функционирование БММ БОп.Н.ц.«^) описывается однородным обрывающимся марковским процессом (МП) X(t), задаваемым вектором вероятностей начальных состояний этого процесса (начальным вектором) и матрицей А интенсивностей переходов.

Введено понятие макросостояния МП. Макросостояние Хз ЛИ X(t) объединяет все состояния МП, в которых может находиться система к рассматриваемому любому моменту времени t после выполнения ровно s работ, Oas<N.

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

Вектор ?0- начального распределения рассматриваемого МП X(t) содержит число элементов, равное числу

макросостояний и имеет следующий вид- t^=(0.....0,1^ Q),

где вектор t^ о=(0,0,.. .#,0,1) содержит элементы по числу' состояний Ш.1 в макросостоянии Х„.

0 rw k п* ,

МП X(t), описывающий модель S(m,H,n,a1,3(k)) исследуется

на основе того же метода анализа, что и система SOn.N.^,^).

Для этого (формируем из множества макросостояний (Х0,... ,XN ))

системы S два подмножества: х,. .=(Х„.....XJ и

. ( 1 ) о о

х(2)=СХ;1_1 ,Х3.....^^н-!5» соответствующие выполнению КВР до

сбоя/отказа на ,/-ой работе и после него до завершения КВР.

На первом интервале постоянства поведение модели

5(т,Н,ц,а1>,)(к)) совпадает с поведением БММ 8(т,Н,ц,а1) на множестве макросостояний £(1), а на втором интервале [^1Ды1-с поведением БММ, в которой изменены параметры функционирования (число обслуживающих приборов, в случае отказа, и число выполняемых работ), то есть с поведением системы 5(т-к,1К}+-1 ,(1,«1) на подмножестве макрссостояний х(г).

Случайный процесс ХШ, описывающий функционирование модели 5(ш,Н,(1,в1,3(к)), представляется в виде последовательности из обрывающихся марковских процессов Х(1)(1;) и Х(г)а), первый из которых описывает, функционирование БШ 5(т,Н,(1.а1) над множеством макросостояний на интервале

[г,,^, а второй- описывает БММ с измененными парадетрами 5(т-к,И-Л+1,1л,а1) над множеством макросостояний х{Г>) на интервале при этом начальный вектор *т(1)~ аля МП

Х( Г) Ц) определяется как а начальный вектор для МП

Х(г)Ш вычисляется по выражению

а~(э-1,э)-ый блок матрицы А, МП Х(1)(г).

С помощью данного метода производится оценка времени выполнения КВР при структурном резервировании процессоров ВС в условиях сбоев/отказов.

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

а) параметрами параллелизма КВР;

б) количеством работ КВР, оставшихся для выполнения на ВС после события отказа.

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

- т

их параллелизма что приводит к нарушению упомянутой вше "пропорциональности" Тп и <3: уменьшение ресурсов ВС на 1/й отнюдь не всегда приводит к соответствующему увеличению Твьш.

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

Влияние обоих факторов (а) и (б) на т количественнс оценивается на основе изложенного выше подхода с сопрягаемыми математическими моделями функционирования ВС для любого заданного КВР.

Например численные расчеты для КВР с N=23 (<>о=0.331, а,=0.391, ао=0.044, а3-0.1?л>, используемого в диссертации для иллюстрации разработанных методов и моделей, показывают следующее: при выполнении КВР на исходных ОП (при кратности резервирования К=2, т.е. т=6), в случае отказа одного из ОП твып Увелич1*аается на величину от 4% до 18%,- в зависимости от того, на какой из работ зафиксирован отказ (а2а и а, соответственно); во всех случаях зто уменьшение меньше ^=1.

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

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

Модель представляет собой однофазную систему массового обслуживания без потерь, содержащую пул из КН работ заданного КВР и их копий, буфер работ-оригиналов БО и буфер работ-копий БК (в дальнейшем для краткости мы будем называть работы оригиналами и копиями) с максимальным объемом на N работ каждый, <1=т обслуживающих приборов (ОП); для простоты и удобства иллюстрации работы модели принято сИп=3, кратность

резервирования работ К-2.

Модель функционирует еле душим образен: "начальная" работа-оригинал а, заданного КВР из пула 2Л1 через БО немеченые пе^дается на выполнение в любой СП, а на лябей другой свободный ОП из того же пула через БК передается копия а*; число заявок в пуле уменьшается, тагам образом, на две

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

Обслуживание оригиналов на СП завершается событиями С^ с вероятностями а1, 0< 1<3, т.е. в БО (в текущий фронт работ Г) из пула поступает 1 новну. оригиналов, а в БК (в текущий фронт Г*)-соответственно 1 новых копий, при этом число работ в пуле уменьшается на 21; обслуженный оригинал покидает систему.

В отличие от обслуживания оригиналов, завершение выполнения копии не приводит к инициации новых работ из пула в систему БО-БК-ОП; обслуженная копия просто покидает систему.

Оригиналы из БО имеют относительный приоритет перед копиями из БК: на незанятый или освобождающийся СП сначала выбираются работы из БО, и лишь после того, как число готовых к выполнению оригиналов в Г станет равным "нулю", на свободные ОП выбираются копии из фронта Р* (БК).

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

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

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

X=([n,l.k,k 1: n=0,2N;l=0,N-l;k=0,N-l,k =Ô7d> (3.1)

\j О

где n - число работ в пуле;

1 - число работ-оригиналов, находящихся в БО

и выполняемых на ОП; к - число копий,находящихся в буфере копий (БК); к - число копий, выполняемых на ОП; d - количество обслуживающих приборов (ОП). Начальным состоянием системы является состояние х[2Н,0,0,0], из которого она с вероятностью "I" переходит в состояние х[2Н-2,1,0,11.

Для предлагаемой модели остаются справедливы;-™ ограничения и допущения, использованные в базовой математической модели и исходящие из физического содержания рассматриваемых процессов: до завершения последней "конечной" работы КВР система не может опустошиться в силу связности любой другой вершины графа G (соответствующего заданному КВР) по ее выходным дугам.

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

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

Марковский процесс, которым списывается система, считается заданным, если {»азработчиком задан или определен из морфологического описания сиг,темы (эвристически или путем перебора) вектор упорядоченных состояний X, а также заданы:

-хотя бы одно состояние,- например, начальное состояние

г(2)=(Хл-1 .....соответствующие выполнению КВР до

сбоя/отказа на ,?-ой работе и после него до завершения КВР.

На первом интервале постоянства поведение модели

В(ш,Н,ц,а1,,](к)) совпадает с поведением БММ 5(ш,Н,ц,а±) на множестве макросостояний х((), а на втором интервале Лн1-з поведением БММ, в которой изменены параметры функционирования (число обслуживающих приборов, в случае отказа, и число ¡выполняемых работ), то есть с поведением системы 1ц,<«1) на подмножестве макросостояний х(г).

Случайный процесс ХД), описывающий функционирование модели 5(ш,М,ц,о1,^(к)), представляется в виде тоследователыюсти из обрывающихся марковских процессов X(1)(t) 1 X 2 Ш, первый из которых описывает функционирование БММ Ит,М,ц,«1) над множеством макросостояний на интервале

а второй- описывает БММ с изменениими параметрами над множеством макросостояний х(2 ) на штервале Г1;.; при этом начальный вектор *Г(])- для МП <(|)(1;) определяется как а начальный вектор для МП

*(£)Ш вычисляется по выражению

1 (2 ), 3-1=*о,оР0,1Р1 .2" ,Р1-2,1-1 ' ГДе

Р , =-А1 . (А1 )"', 3=1714";

д-(з-1,з)-ый блок матрицы А, МП Х(1)(г).

С помощью данного метода производится оценка времени зыполнения КВР при структурном резервировании процессоров 5С в условиях сбоев/отказов.

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

а) параметрами параллелизма КВР;

б) количеством работ КВР, оставшихся для выполнения на ВС юсле события отказа.

Рассмотрим фактор (а). Уменьшение числа процессоров ВС [з-за отказа (например, одного из них) традиционно связывают с [ропорциснальннм уменьшением производительности ВС. Однако, для :снк{>етннх программных комплексов (в наших моделях-КВР) время [х выполнения Твып существенно зависит от значений параметров

их параллелизма «lt что приводит к нарушению упомянутой вше "пропорциональности" Тв и <3: уменьшение ресурсов ВС на 1/d отнюдь не всегда приводит к соответствующему увеличению Т .

Что же касается фактора (б), то представляется очевидной

зависимость Т от того, какие части КВР выполняются иг; вьш

исходном, а какие- на уменьшенном числе процессоров.

Влияние обоих факторов (а) и (б) на Т количественно оценивается на основе изложенного выше подхода с сопрягаемыми математическими моделями функционирования ВС для любого заданного КВР.

Например численные расчеты для КВР с N=23 («О=0.391, а, =0.39?, «.,=0.044, «з=0.174), используемого в диссертации для иллюстрации разработанных методов и моделей, показывают следующее: при выполнении КВР на исходных d=3 ОП (при кратности резервирования К=2, т.е. т=6), в случае отказа одного из ОП Т увеличивается на величину от 4% до 18«,- в зависимости от того, на какой из работ зафиксирован отказ (а2„ и а, соответственно); во всех случаях зто уменьшение меньше

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

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

Модель представляет собой однофазную систему массового обслуживания без потерь, содержащую пул из КН работ заданного ¡СВР и их копий, буфер работ-оригиналов БО и буфер работ-копий БК (в дальнейшем для краткости мы будем называть работа оригиналами и копиями) с максимальным объемом на N работ каждый, d=m обслуживающих приборов (ОН); для простоты и удобства иллюстрации работы модели принято d=m=3, кратность

резервирования работ К--2.

Модель функционирует следующим образом: "начальная" работа-оригинал а1 заданного КВР из пула через БО немедленно передается на выполнение в любой СП, а на либей другой свободный ОП из того же пула через БК передается копия а*; число заявок в пуле уменьшается, таким образом, на две

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

Обслуживание- оригиналов на СП завершается событиями С^ с вероятностями - 0<1<3, т.е. в БО (в текущий фронт работ Р) из пула поступает 1 новых оригиналов, а в БК (в текущий фронт Г*)-соответственно 1 новых копий, при этом число работ в пуле уменьшается на 21; обслуженный оригинал покидает систему.

В отличие от обслуживания оригиналов, завершение выполнения копии не приводит к инициации новых работ из пула в систему БО-БК-ОП; обслуженная копия просто покидает систему.

Оригиналы из БО имеют относительный приоритет перед копиями из БК: на незанятый или освобождающийся ОП сначала выбираются работы из БО, и лишь после того, как число готовых к выполнению оригиналов в Р станет равным "нулю", на свободные ОП выбираются копии из фронта Р* (Ш). .

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

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

Рассматриваемая СМО описывается дискретным (в смысле числа состояний) марковским процессом с непрерывным временем, состояния которого образуют множество

Х={[п,1,к,к ]: п=07Ш;1=0,N-1;к=0,N-1,к =о75} (3.1)

О О

где п - число работ в пуле;

1 - число работ-оригиналов, находящихся в БО и выполняемых на ОП;

к - число копий,находящихся в буфере копий (БК);

к - число копий., выполняемых на ОП;

(3 - количество обслуживающих приборов (ОП).

Начальным состоянием системы является состояние х[2Ы,0,0,0], из которого она с вероятностью "I" переходит в состояние х[2Н-2,1,0.11.

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

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

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

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

-хотя бы одно состояние,- например, начальное состояние

На первых шагах работы алгоритма вектор состояний Х(Х) состоит из единственного состояния, которое является начальным состоянием системы, поэтому следуют присваивания:

1. г,:=1.

2.

3. 1:=1.

4. Описываются условия для координат вектора состояния, при выполнении которых возможно событие Е^, вследствие которого система переходит из данного состояния в соседнее (оператор Б).

5. Анализируется: нужна ли дополнительная проверка условий для изменения координат вектора состояния для события Е1? Если нет- перейти к п.7.

6. Описываются дополнительные условия для изменения координат вектора состояния (оператор КЗ).

7. Описываются изменения координат вектора состояния системы для события Е1 (оператор К).

8. Проверяется: описаны ли все дополнительные условия для изменения координат вектора состояния для события Е1? Если нет-перейти к п.5.

9. Вновь полученная координата вектора состояний Х(Ъ) проверяется на ее наличие в векторе состояний.

10. Проверяется: данной координаты в векторе состояний ХШ нет ?

Если да- вписать данную координату в вектор ХД), присвоить э:=5+1.

11. Проверяется: нужны ли дополнительные условия для определения интенсивности перехода Р для события Е^? Если нет-перейти к п.13.

12. Описание дополнительных условий для интенсивности перехода для события Е^(оператор 1Б).

13. Определение интенсивности перехода Р для события Е^ (оператор I).

14. Описаны ли все дополнительные условия для определения интенсивности перехода Р для события Е1? Если нет- перейти к п.II.

15. 1='« ? Если да- пс{>ехсд к п.19.

16. 1:=1+1. Переход к п.4.

17. ? Если да- переход к п.19.

18. .

19. Конец описания событий.

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

Численный анализ времени выполнения КВР при временном резервировании работ, осуществленный с помощью разработанных алгоритмов и моделей, позволяет сделать следующие принципиальные выводы:

I. Использование временного резервирования работ КВР в параллельных ВС с т>2 процессорами обеспечивает ленъшее вреля выполнения КВР, чем в ВС со структурным резервированием процессоров с той же кратностью резервирования К; этот эффект имеет место как при нормальном, "штатном" выполнении КВР, так и при событиях отказов вычислительных ресурсов ВС.

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

Для примера КВР, используемого в диссертации, Тв уменьшается на величину 14-33 г по сравнению с т ,1ГТ того же КВР

ВЫИ

со структурным резервированием процессоров при той же кратности К=2.

3. Эффективность использования временного резервирования работ КВР существенно зависит от порога г- максимально допустимого запаздывания выполнения работ-копий по отношению к выполнению соответствующих работ-оригиналов. Значения порога г

целесообразно выбирать в диапазоне г-4*8; при выборе меньших значений г может наблюдаться существенное увеличение Тв (при г=0 временное резервирование работ КВР соответствует структурному резервированию процессров ВС при той же кратности резервирования К) ; при больших значениях г эффект уменьшения Тв>р> практически не наблюдается.

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

В частности, разработаны следующие программные модули:

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

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

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

Все модули реализованы на языке Turbo-Pascal 6.0.

ВЫВОДИ, ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ

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

2. Разработан новый алгоритмический подход к анализу выполнения КВР в условиях сбоев и отказов вычислительных ресурсов параллельной ВС как при структурном, так и при временном резервировании ресурсов и работ КВР. Подход базируется на сопряжении математических моделей функционирования ВС в'различных режимах (нормальном, при сбоях, при отказах) на различных фрагментах одного и того, же КВР и обеспечивает более точные, детализированные количественные

сценки Твып по сравнению с традиционно используемыми стохастическими оценками Т0„_.

оЫП

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

4. Результаты численного расчета математической модели по п.З позволили обосновать и количественно оценить следующий качественно новый эффект: использование временного резервирования работ реальных КВР в параллельных ВС с т>2 процессорами обеспечивает лечыиее бреля выполнения КВР, чем при структурном резервировании процессоров (с той же кратностью резервирования К>2>.

5. Указанный эффект уменьшения Твып имеет место как при нормальном, "штатном'" выполнении КВР, так и при отказах параллельных вычислительных гесурсов ВС, и может достигать величины от единиц до нескольких десятков процентов- в зависимости от параметров параллелизма конкретного КВР, а также от состояния КВР, при -котором зафиксирован отказ какого-либо из процессоров ВС.

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

7. Все разработанные математические модели и алгоритмы запрограммированы на языке Turbo-Pascal 6.0 и реализованы на ЭВМ IBM PC/AT.

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

1. Тепляков A.B., Маргалиташвили A.A., Амбарцумян A.A., Прейдунов Ю.В. Графовые модели комплексов взаимосвязанных работ. 7/ Деп. ВИНИТИ. № 587-В90.

2. Игнатущенко В.В., Маргалиташвили A.A.,'Тепляков A.B. Математические модели для анализа отказоустойчивости и

кивучести параллельных вычислительных систем в контурах АСУ // Гезисы докл. XI Всесоюзного совещания по проблемам управления. Ташкент. 1989.

3. Тепляков A.B. Математические модели для анализа кивучести параллельных систем на комплексах взаимосвязанных забот.// Труда международной конференции "Высокопроизводительные вычислительные системы в управлении и тучных исследованиях". Алма-Ата, 1991г.

4. Игнатущенко В.В., Тепляков A.B. Прогнозирование заполнения комплексов взаимосвязанных работ на распределенных вычислительных системах при сбоях и отказах их компонент.// Груды V Совещания по распределенным вычислительным системам (CDS-92). Калининград, 1992г.

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

По работам, опубликованным в соавторстве, личный жладциссертанта состоит в следующем: в Ш выведены >граничегая для"параметров параллелизма КВР; в (21 разработана математическая модель для функционирования КВР при структурном эезервировании процессоров ВС; в 141 диссертанту принадлежат юе аналитические исследования.

Заказ 406. Тираж 100. 117806, Москва, ГСП-7, Профсоюзная, 65 Институт проблем управления