ANALYSIS OF PROBABILISTIC AND INTERIM CHARACTERISTICS OF FAULT TOLERANT SOFTWARE OF DISTRIBUTED COMPUTING SYSTEMS

全文:

На сегодняшний день распределенные вычислительные системы все чаще используются для решения управленческих, исследовательских и производственных задач. Одним из видов таких систем являются гетерогенные вычислительные системы высокой надежности для высокопроизводительных вычислений (системы обработки высокой пропускной способности), объединящие в единую вычислительную среду гетерогенные вычислительные ресурсы (суперкомпьютеры, серверы, рабочие станции, локальные и глобальные сети с различной пропускной способностью, хранилища данных и пр.), благодаря чему создается единая среда обработки информации и распределенных вычислений. Большинство исследовательских задач, решаемых в сфере гетерогенных вычислений, направлено на разработку системы поддержки параллельных или распределенных вычислений, стремящихся приблизить практическую продолжительность работы (производительность, коэффициент ускорения) к теоретически возможной для данного кластера. Постановка задачи. Использование суперкомпьютера или специализированного кластера невозможно или малоэффективно в таких случаях, когда алгоритм программы нельзя эффективно преобразовать из последовательного в параллельный, время выполнения задачи сравнимо со временем создания параллельного алгоритма [1] или требуется решать множество одинаковых задач с различными входными данными, при этом время выполнения каждой задачи в отдельности невелико (не превышает нескольких часов). Для таких задач возможна разработка гетерогенной распределенной вычислительной системы (РВС), использующей узлы с высокой надежностью и отказоустойчивостью. Эффективное использование подобных РВС связано: - с разработкой моделей и методов анализа вероятностно-временных характеристик распределенных вычислительных систем с недетерминированным поведением ее вычислительных узлов; - подготовкой рекомендации по эксплуатации распределенных гетерогенных вычислительных систем для обеспечения эффективного выполнения приоритетных задач обработки информации. Среда проведения анализа вероятностновременных характеристик отказоустойчивого программного обеспечения распределенных вычислительных систем. Для решения поставленных задач была разработана среда проведения анализа вероятностно-временных характеристик отказоустойчивого программного обеспечения распределенных вычислительных систем MGNetwork, созданная в среде разработки Delphi 6.0 с использованием следующих дополнительных библиотек: - SimpleXML версии 1.0.1 (для работы с XML-документами); - FatExpression версии 1.03 (для расчета произвольных математических выражений). Среда MGNetwork на основе ГЕРТ-сети, описывающей отказоустойчивое программное обеспечение распределенных вычислительных систем и оформленной в XML-документе специального вида, позволяет: - оценить характеристики и вещественные параметры ГЕРТ-сети [2]: вероятность выполнения стока сети, математическое ожидание и дисперсию времени выполнения всей сети или стока сети и т. д.; - оценить агрегатные и стохастические параметры вещественных переменных оцениваемой системы: сумму, среднее, минимум, максимум, математическое ожидание и дисперсию; - построить графики функций распределения и плотности распределения случайных величин (параметров оцениваемой системы); - построить графики функций распределения и плотности распределения стохастических параметров ГЕРТ-сети; - исследовать каждую реализацию отказоустойчивого программного обеспечения распределенных вычислительных систем и маршруты активации узлов; - оценить параметры каждого узла: вероятность активации узла, математическое ожидание, дисперсию, распределения и плотности распределения стохастических параметров [3; 4]. Для использования продолжительности выполнения работ, заданных случайными величинами в сетях для метода критического пути (МКП) или ПЕРТ-сетях, был разработан и реализован алгоритм преобразования произвольной МКП-сети или ПЕРТ-сети в ГЕРТ-сеть. Экспериментальная часть. Выполним сравнение результатов для работы двух узлов распределенной вычислительной системы Condor [5], полученных при помощи построенных моделей: узла 1 - компьютера, размещенного в классе общего доступа; узла 2 - компьютера, размещенного в лаборантском кабинете класса (рис. 1-4, табл. 1). 500 1 000 1 500 2 000 Рис. 1. Функция распределения времени доступности узла 1 [Image] 600 620 640 660 660 700 720 740 Рис. 2. Функция распределения времени недоступности узла 1 [Image] О 1 ООО 2 000 3 000 4 0 Рис. 3. Функция распределения времени доступности узла 2 Результаты моделирования представлены в табл. 2 и на рис. 5-8, где использованы следующие обозначения: T_Z - время выполнения задачи, ч, на узле без сбоев и резервного копирования; TR - интервал времени, ч, между выполнением резервных копий состояния задачи; T (результат моделирования работы узла) - случайная величина времени выполнения задачи на соответствующем узле при данной периодичности выполнения РК состояния задачи; M(T), g(T) - математическое ожидание и среднеквадратичное отклонение времени выполнения задачи на узле; M(T) / T_Z - обратная величина ожидаемого коэффициента ускорения (коэффициента замедления). Кривая 1 соответствует режиму запуска задачи без использования функции резервного копирования, кривые 2, 3 и 4 - режиму запуска задачи с выполнением резервных копий состояния системы каждые 2, 4 и 6 ч. [Image] Рис. 4. Функция распределения времени недоступности узла 2 Протокол экспериментов приведен в табл. 3. Экс-данных задачах с продолжительностью выполнения 6 периментальная проверка проводилась не для всех и 12 ч. Задачи запускались в режимах без резервного режимов запуска задач, поскольку тогда общая прокопирования (РК) и с резервным копированием каж- должительность эксперимента составляла бы более дые 2, 4 и 6 ч. трех месяцев. Эксперименты проводились на специально соз- Таблица 1 Параметры моделей функционирования узлов распределенной вычислительной системы Параметр Узел 1 Узел 2 Время миграции задачи, мин 10 10 Вероятность доступности узла в начале вычислений 0,583 6 0,778 2 Вероятность успешной миграции задачи с узла при необходимости 0,62 0,86 Таблица 2 Результаты оценки времени выполнения задачи на узлах распределенной вычислительной системы TZ, ч Узел T R, ч M(T), ч ct(T), ч M(T)/T_Z 12 1 Без РК 48,689 05 36,203 350 4,057 421 12 1 2 27,320 15 4,320 533 2,276 679 12 1 4 27,053 92 5,215 10 2,254 493 12 1 6 27,862 77 7,435 95 2,321 897 12 2 Без РК 15,292 17 6,736 75 1,274 347 12 2 2 27,544 32 7,524 95 2,295 360 12 2 4 22,549 13 7,144 30 1,879 094 12 2 6 21,881 88 7,573 25 1,823 490 6 1 Без РК 15,292 17 6,736 75 2,548 694 6 1 2 15,456 65 4,184 433 2,576 108 6 1 4 15,235 48 4,260 417 2,539 247 6 2 Без РК 10,877 53 6,331 567 1,812 922 6 2 2 14,593 75 5,620 233 2,432 292 6 2 4 13,493 50 5,581 150 2,248 917 * Обозначения см. в тексте. з-*1! . І-1 1 -Ж 2 ПІ j 860 1360 1360 2360 360 0,9 0,8 0,7 0,6 f 0,5 0,4 0,3 0,2 0,1 t, мин {время выполнения задачи на узле РГСОИ) Рис. 5. Функции распределения времени выполнения задачи (T_Z = 6 ч) на узле 1 (обозначения см. в тексте) 0,8 0,6 0,2 0,1 0.9 0,7 Зг 0.5 0,4 0,3 і - -2 X /^~ 3 // / /, / J // г // // // 360 860 1360 1860 2360 t, мин (время выполнения задачи на узле РГСОИ) Рис. 6. Функции распределения времени выполнения задачи (T Z = 6 ч) на узле 2 (обозначения см. в тексте) 0,9 0,8 0,7 0,6 П,Ч 0,4 0,3 0,2 0,1 0 2 з - -И / 1 J— J -L J- ' і 720 1220 1720 2220 2720 3220 3720 t, мин (время выполнения івдачи науїле РГСОИ) Рис. 7. Функции распределения времени выполнения задачи (T_Z = 12 ч) на узле 1 (обозначения см. в тексте) 1 0,9 0,8 0,7 0,6 І 0,5 0,4 0,3 0,2 0,1 о [Image] 720 1220 1720 2220 2720 3220 3720 t, мин (время выполнения ..ідичи на vine РГСОИ) Рис. 8. Функции распределения времени выполнения задачи (T_Z = 12 ч) на узле 2 (обозначения см. в тексте) Таблица 3 Протокол выполнения задач на распределенной вычислительной системе Condor TZ, ч Узел T R, ч № эксперимента T, ч 1 31,03 12 1 4 2 33,53 3 29,53 1 22,97 12 2 4 2 31,98 3 29,07 1 12,07 6 1 Без РК 2 23,72 3 11,50 1 12,10 6 1 2 2 19,87 3 20,03 1 18,83 6 1 4 2 12,68 3 14,30 1 8,55 6 2 Без РК 2 13,53 3 17,15 1 13,07 6 2 2 2 20,17 3 9,37 1 15,27 6 2 4 2 20,88 3 22,12 Полученные результаты не противоречат результатам моделирования. Однако небольшой объем выборки не позволяет использовать статистические методы проверки гипотезы ее соответствия аналитически построенному распределению. Проведем анализ построенных функций распределения времени выполнения задач на узлах 1 и 2: - для каждых узла и задачи существует такое значение периода выполнения резервного копирования, при котором среднеквадратичное отклонение времени выполнения задачи наименьшее; - частое резервное копирование ведет к большим накладным расходам [6]; - желательно, чтобы математическое ожидание времени доступности узла было в два и более раз больше, чем периодичность выполнения резервного копирования; - вероятность успешной миграции задачи с узла существенно повышает эффективность его работы. Увеличение этого параметра зависит от отказоустойчивости узла и сети передачи данных, объема передаваемых данных и поведения пользователя узла. На основании графиков функций распределения времени выполнения задач на узле распределенной вычислительной системы (см. рис. 5-8) можно сделать следующие выводы: - узел 2 не нуждается в частом резервном копировании при данной продолжительности решения задачи, тогда как узел 1 требует выполнения периодических резервных копий; узлу 1, TZ = 6 ч, резервное копирование с интервалом 4 ч. - для узов 1 и 2 выполнение резервного копирования каждые 2 ч значительно увеличивает общую продолжительность решения задачи; - уменьшение интервала резервного копирования для узлов уменьшает дисперсию времени выполнения задачи. Построенные функции распределения времени выполнения задачи позволяют: - прогнозировать время выполнения задачи для разных узлов РВС с допустимой вероятностью; - ранжировать узлы по вероятности завершения выполнения задачи за определенное время; - выбрать оптимальный интервал времени выполнения резервных копий; - формировать рекомендации по написанию заявки на ресурсы РВС. Используя эти функции, можно рассчитать величину, обратную коэффициенту ускорения для узла системы: K = Kt Ke = N Kt = T- T к (1) где T1 - время, необходимое для расчета задачи без использования РВС; TK - время расчета задачи с использованием РВС; N - количество узлов системы обработки информации. Функция распределения F(y) случайной величины y = Kt имеет вид 0 ад ад yt1 F(y) = j ЛЮ j f2(t2)dt2dt1 + j Mb') j f2(t2)dt2dt1 = -ад yt1 0 -ад 0 ад = j ^ )(1 - F2 (yt1 ))dt1 + j ^)F2 (yt1)dt1, (2) -ад 0 где f1, f2 - функции плотности распределения случайных величин Tk и T1; F1, F2 - функции распределения случайных величин Tk и T1. Для представленных выше моделей T1 = TZ - положительная константа, а Tk задано функцией распределения F1(t), y = Kt строго больше нуля. Тогда mm(0,r1/ y ) ад F (y) = j /(Ad + j /(Ad = -ад max(0,7\/ y ) = F1 (min(o, T / y)) + (1 - F1 (max(0, T / y))) = (3) = ^(0) +1 - FX(TX/ y) = 1 + ^(0) - FX(T _ Z / Kt). Пример функций распределения величины, обратной коэффициенту ускорения, приведен на рис. 9, где кривая 1 соответствует узлу 2, TZ = 6 ч, без резервного копирования; кривая 2 - узлу 2, T Z = 12 ч, без резервного копирования; кривая 3 - узлу 1, T Z = 12 ч, резервное копирование с интервалом 4 ч; кривая 4 - [Image] Рис. 9. Функция распределения случайной величины, обратной коэффициенту ускорения (обозначения см. в тексте) Полученная функция распределения коэффициента F(Kt), в отличие от F1(t), является относительной величиной, нормированной по времени выполнения задачи, которая при достаточно большом времени TZ характеризует стохастическую эффективность работы системы. Функции распределения коэффициента ускорения Ke и Kt совпадают, поскольку для данной архитектуры РВС N = 1. Эти функции позволяют проводить группировку узлов по фактической производительности и выполнять приоритетные задачи с приемлемой вероятностью получения результата к требуемому моменту времени. Предложенный подход к анализу вероятностновременных характеристик отказоустойчивого программного обеспечения распределенных вычислительных систем основан на использовании инструментальных средств в виде программной реализации моделей и методов анализа вероятностно-временных характеристик РВС с недетерминированным поведением вычислительных узлов. Среда для проведения анализа вероятностновременных характеристик отказоустойчивого программного обеспечения распределенных вычислительных систем позволяет выполнять расчеты ГЕРТ-сетей, используя прямой и обратный алгоритмы ГЕРТ-сети [7], прямую свертку; имеет открытый формат XML-документа, описывающий структуру сети, что дает возможность ее задания в любом текстовом редакторе и дальнейшего создания специализированного программного обеспечения согласно визуальному построению ГЕРТ-сети. Еще одним достоинством этой среды является трассировка реализаций отказоустойчивого программного обеспечения РВС и анализа результатов этой трассировки.

作者简介

R. Tsarev

Siberian state aerospace university named after academician M. F. Reshetnev

Email: rahatamatahata@mail.ru
Candidate of Science (Engineering), associate professor of the chair of system analysis and research of operations of the Siberian state aerospace university named after academician M. F. Reshetnev. Graduated from Krasnoyarsk state technical university in 1999. Area of scientific interests - information technologies, multi-version software, multiattributive methods of decision-making, space systems.

A. Shtarik

Siberian federal university

Email: shtarik@mail.ru
graduate student of the chair of informatics of the Siberian federal university. Graduated from the Siberian federal university in 2010. Area of scientific interests - system analysis, software, reliability, space systems

E. Shtarik

Siberian federal university

Email: zozylia.elena@gmail.com
graduate student of the chair of informatics of the Siberian federal university. Graduated from the Siberian federal university in 2010. Area of scientific interests - information technologies, software, reliability, space systems

M. Kochergina

T. Panfilova

Siberian state aerospace university named after academician M. F. Reshetnev

Email: panfilova@sibsau.ru
engineer of the department of advanced training of the Siberian state aerospace university named after academician M. F. Reshetnev. Graduated from the Siberian state technological university in 2006. Area of scientific interests - mathematical modeling, optimization, indistinct logic.

参考

补充文件