Содержание к диссертации
Введение
1. Различные подходы к анализу временных характеристик функционирования узловгетерогенных систем обработки информаци 8
1.1. Составление расписания загрузки узлов системы с использованием методов теории оптимизации 10
1.2. Моделирование функционирования распределенной системы обработки информации при помощи сетей Петри и их расширений 11
1.3. Марковские цепи и стохастические сети 12
1.4. Конвейерные модели 14
1.5. Методы разработки и адоптации программ для выполнения в распределенной системе обработки информации 14
1.6. Проблемы оценки временных характеристик распределенных гетерогенных систем обработки информации 16
1.6.1. rPHfl(GRID) 17
1.6.2. Распределенная гетерогенная система обработки информации, использующая в качестве вычислительных узлов персональные компьютеры пользователей во время простоя 18
1.7. Выводы 22
2 Математическая модели стохастической ГЕРТ-сети и МГ-сети 23
2.1 Математическая модель ГЕРТ-сети 23
2.2 Математическая модель модифицированной ГЕРТ-сети 37
2.3 Выводы 53
3 Алгоритмы расчета МГ-сети 55
3.1 Принятые обозначения 55
3.2 Обратный алгоритм расчета МГ-сети 57
3.3 Прямой алгоритм расчета МГ-сети 58
3.4 Численные методы, используемые для расчета и обработки результатов МГ-сети ...59
3.5 Сравнение производительности прямого и обратного алгоритмов расчета МГ-сети 65
3.6 Выводы 67
4 Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей с использованием среды проведения исследований MGNetwork 68
4.1 Среда проведения исследований MGNetwork 68
4.2 Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей 71
4.3 Выводы 91
Заключение 93
Список использованной литературы 94
- Марковские цепи и стохастические сети
- Распределенная гетерогенная система обработки информации, использующая в качестве вычислительных узлов персональные компьютеры пользователей во время простоя
- Математическая модель модифицированной ГЕРТ-сети
- Численные методы, используемые для расчета и обработки результатов МГ-сети
Введение к работе
Результат во многих исследовательских и производственных задачах часто напрямую связан с доступностью высокопроизводительных систем обработки информации. Причем большинство задач решается на универсальных системах обработки информации. Использование данных систем позволяет снизить как стоимость создания, так и стоимость эксплуатации, а также обеспечить приемлемую загрузку всей системы.
В современной научно-технической литературе под термином
«высокопроизводительная система обработки информации»
подразумеваются суперкомпьютеры или кластеры, управляемые специализированным программным обеспечением параллельной обработки информации. Такие системы требуют разработки программного обеспечения обработки информации, учитывающего архитектурные особенности среды выполнения. Однако для многих задач алгоритмы программ не могут быть эффективно адаптированы для данных систем, или время адаптации сравнимо со сроком полезного использования задачи.
Для большого класса задач не требуется высокая производительность обработки одного набора данных. Гораздо важнее возможность использования надежной системы обработки информации с приемлемой производительностью и возможностью одновременной обработки нескольких наборов данных.
Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений (системы обработки высокой пропускной способности, high throughput computing), такие как Х-СОМ, Legion или Condor. Такие системы объединяют в единую вычислительную среду распределенные гетерогенные вычислительные ресурсы, причем в качестве узлов, обрабатывающих информацию, могут выступать персональные компьютеры пользователей во время простоя.
Объем доступных ресурсов для такой системы обработки информации изменяется во времени, поэтому применение методов планирования загрузки системы (составления расписаний) или прогнозирования времени завершения задачи, основанных на статических или детерминированных моделях систем или программ, невозможно. Это обстоятельство представляется научной проблемой, выражающейся в необходимости поиска новых подходов к анализу временных характеристик работы узлов системы и обеспечения методов управления вычислением приоритетных задач обработки информации.
Объектом исследования являются высокопроизводительные распределенные гетерогенные системы обработки информации, использующие в качестве узлов персональные компьютеры пользователей.
Предметом исследования являются временные характеристики работы вычислительных узлов системы обработки информации.
Цель исследования: разработка системы анализа временных характеристик работы узлов распределенной гетерогенной системы обработки информации и подходов к распределению ресурсов системы при управлении выполнением приоритетных задач обработки информации.
Задачи исследования:
выработать требования к механизму сбора информации о работе узлов системы и создание блока статистической обработки полученной информации;
разработать модели и методы анализа временных характеристик работы узлов гетерогенной распределенной системы обработки информации с недетерминированным поведением ее вычислительных узлов;
подготовить рекомендаций по эксплуатации распределенных гетерогенных систем обработки информации для обеспечения эффективного выполнения приоритетных задач обработки информации.
Методы исследования. При выполнении работы использовались методы системного анализа, теория вероятностей и математической статистики и теория стохастических сетей.
Научная новизна работы.
Модифицирован математический аппарат стохастических ГЕРТ-сетей. Полученная модификация позволяет: проводить расчет стохастической ГЕРТ-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической ГЕРТ-сети; причем, условная вероятность выполнения исходящей дуги узла задана произвольной функцией, вычислимой в момент активации узла.
Разработаны прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей. Произведено аналитическое сравнение их производительности.
Предложены модели модифицированной ГЕРТ-сети, позволяющие выполнять оценку времени выполнения задачи на узле распределенной гетерогенной системы обработки информации с использованием резервного копирования состояния задачи и без него.
Предложены рекомендации по распределению ресурсов системы обработки информации для обеспечения эффективного управления выполнением приоритетных задач.
Значение для теории. Созданная модифицированная ГЕРТ-сеть позволяет проводить оценки временных характеристик (или иных аддитивных параметров) систем, представимых в виде стохастической ГЕРТ-сети типа «работа на дуге», где продолжительность выполнения «работы» задана вещественной случайной величиной.
Результаты, полученные при выполнении диссертационной работы, создают теоретическую основу для исследования с помощью стохастических сетей временных характеристик распределенных гетерогенных систем обработки информации.
Значение для практики. Предложенные в работе процедуры анализа временных характеристик работы узлов распределенной системы обработки информации позволяют:
проводить оценку оптимальности выбора интервала выполнения резервного копирования состояния задачи для конкретных узлов распределенной гетерогенной системы обработки информации;
проводить оценку производительности и доступности узлов системы, принимать решения о мерах по повышению производительности узлов системы;
проводить управление распределением ресурсов системы для приоритетных задач обработки информации.
Создана среда проведения исследований, позволяющая выполнять расчет временных характеристик модифицированных ГЕРТ-сетей с использованием прямого и обратного алгоритмов.
Достоверность полученных результатов подтверждается тестированием и оценкой результатов применения разработанной среды проведения исследований и модифицированных ГЕРТ-сетей, а также согласованностью расчетных и экспериментальных данных.
Реализация результатов работы. Разработанная среда проведения исследований и модуль расчета модифицированных ГЕРТ-сетей зарегистрированы в Отраслевом фонде алгоритмов и программ (Per. № 5068, код по ЕСПД 03524577.01083-01), что делает ее доступной для широкого круга специалистов по методам анализа стохастических сетей.
Созданная система расчета функции распределения случайной величины времени выполнения задачи использовалась при работе с распределенной гетерогенной системой обработки информации Condor.
На защиту выносятся:
математический аппарат модифицированных ГЕРТ-сетей;
прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей;
модели и методы оценки времени выполнения задачи на узле распределенной гетерогенной системы обработки информации с использованием резервного копирования и без него;
подходы к организации управления распределением ресурсов системы обработки информации для обеспечения эффективного выполнения приоритетных задач обработки информации.
Апробация работы. Основные положения и результаты работы прошли всестороннюю апробацию на всероссийских научно-практических конференциях. В том числе на ежегодной Всероссийской III конференции «Технические науки и современное производство» (2005 г., Лутраки, Греция), Всероссийской заочной электронной конференции Российской академии естествознания «Современные телекоммуникационные и информационные технологии» (2005 г.), Всероссийской VI научной конференции «Успехи современного естествознания» (2005 г. Сочи), Всеросийской III научной конференции с международным участием «Приоритетные направления развития науки, технологий и техники» (2005 г., Хургада, Египет), Всероссийской заочной электронной конференции Российской академии естествознания «Новые информационные технологии и системы» (2005 г.).
Публикации. По теме диссертации опубликовано 11 печатных работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы общим объемом 108 с. и семи приложений объемом 15 с. Список использованной литературы содержит 98 наименований.
Марковские цепи и стохастические сети
Цепи Маркова используются для моделирования поведения системы обработки информации с учетом не гарантированной надежности используемых компонентов. В таких моделях для каждого компонента считаются определенными вероятность выхода из строя и время бесперебойного функционирования (чаще ожидаемое время бесперебойного функционирования). Цепи Маркова позволяют оценить среднее время жизни узла в составе системы или всей системы в целом, среднюю продолжительность выполнения задачи для узла [27], определить узкие места системы обработки информации при моделировании потока запросов к ней[35; 73].
В качестве альтернативы Марковским цепям может использоваться вероятностная модель. В такой модели строится сеть, узлами которой являются состояния системы, а дугами - возможные переходы между ними. Время учитывается как такты переключения состояния системы. Исследуя определенные траектории функционирования системы, можно получить оценки надежности и времени работы системы. Например, в [68] проведено исследование стратегий выполнения резервного копирования данных в параллельных интерпорабельных вычислительных системах с динамически изменяемой конфигурацией.
Графический метод оценки и пересмотра планов (ГЕРТ) Один из подходов к организации процесса интенсивной обработки информации - это использование в качестве узлов обработки информации компьютеров пользователей в свободное от использования времени. Такие проекты как SETI, Climate Predictions, Legion или Condor получают все большее распространении и весьма эффективны для некоторых задач. В случае, если для некоторого узла известна вероятность бесперебойной работы в течение времени, необходимого для расчета задачи, то рассчитать функцию распределения времени выполнения задачи можно используя ГЕРТ-сети [90; 24; 54; 58; 74; 76]. Вероятность бесперебойной работы узла может быть получена из статистики его работы.
В результате слияния ГЕРТ-сетей с методами сетевого планирования разработан математический аппарат альтернативных циклических обобщенных сетей, позволяющий рассчитывать сеть, в состав которой входят как детерминированные, так и ГЕРТ подсети [1; 2; 16; 17; 18; 19]. Такой подход позволяет строить сети оценки времени одновременного выполнения частей задачи на нескольких узлах (рабочих станциях) гетерогенной распределенной системы обработки информации.
Для задач, алгоритмы которых устроены таким образом, что данные проходят «этапы обработки», причем выходные данные на одном из «этапов», являются входными для следующего, применяются конвейерные модели. Как правило, такие алгоритмы разрабатываются для систем обработки информации со специализированными узлами. Примером такой системы является современный компьютер, центральный процессор которого перекладывает часть операций по расчету изображения на графический процессор. Методы минимизации времени выполнения задачи и минимизации среднего времени потока представлены в следующих работах[28; 37; 48; 65]. выполнения в распределенной системе обработки информации Как уже было сказано ранее, эффективность выполнения задачи во многом зависит от адаптированности ее алгоритма к характеристикам системы обработки информации. Основная работа сосредоточена в трех направлениях: - создание алгоритмов, способных адаптироваться под характеристики системы обработки информации; - создание специальных языков программирования, способных достаточно хорошо адаптировать программу под характеристики системы; - для языков высокого уровня (как правило, математических) замена используемых функций на функции, приспособленные для работы с системами обработки информации; - использование алгоритмов анализа программного кода с целью выдачи рекомендаций по его улучшению или автоматического изменения программного кода. Рассмотрим часть из них подробнее. 14 Автоматная модель параллельных вычислений может быть использована как альтернатива сетям Петри. Задача для системы обработки информации представляется в виде конечных автоматов [51]. Такое представление дает серию преимуществ: - позволяет использовать стандартные библиотеки автоматов; - позволяет легко преобразовывать алгоритмы, представленные в форме конечных автоматов к стандартным блок-схемам; - порождает строгое разделение алгоритма программы от средств ее управления; - предоставляет дополнительные средства отладки программного кода каждого автомата и всего алгоритма; - позволяет использовать имитационные модели оценки времени выполнения программы. Один из эффективных способов создания параллельных программ заключается в использовании специализированных языков программирования или их расширений. Программы, разработанные с применением таких языков, параллельны уже на этапе кодирования [61]. К сожалению, автору не удалось найти промышленно используемый язык программирования. Все найденные языки используются в научно-исследовательских целях. Специализированность языка позволяет встраивать средства отладки и оценки производительности как программ целиком, так и их частей в среду разработки языка. Наиболее простой метод оценки времени выполнения такой программы - это обработка результатов пробных запусков программы с последующей оценкой результата для реальной задачи и реальной системы обработки информации.
Распределенная гетерогенная система обработки информации, использующая в качестве вычислительных узлов персональные компьютеры пользователей во время простоя
Данный алгоритм был применен в задачах оценки времени выполнения операции на сложном конвейере, допускающем отбраковку, возврат детали на доработку [25] и т.п. Например, их применяют при оценке времени переработки сырья в производстве полупроводников, в производстве электроники и ремонте АУ электровоза [37; 75] и при управлении производственным процессом [6; 23; 26; 72]. Также позволяют получить качественно новые результаты при оценке времени выполнения распараллеленной задачи на неспециализированном вычислительном кластере Condor [24; 36; 60].
Указанный выше алгоритм был модифицирован группой сотрудников Рязанской государственной радиотехнической академии [41; 76]. Для того чтобы получить численное значение закона распределения выходной величины ГЕРТ-сети, производится преобразование W-функций в соответствующие им характеристические функции. Полученные функции интерполируются многочленом Лагранжа второй степени с равностоящими узлами. Полученное выражение позволяет рассчитать на ЭВМ значение закона распределения времени выполнения ГЕРТ-сети в точке. Порядок вычислительных затрат равен 0(пь n2) + O(q) + 0(п3), где Пі - число дуг ГЕРТ-сети, п2 - число узлов интерполяции, q - число определяемых значений плотности вероятности, п3- суммарное число петель порядков г, г=1, 2,..., п.
Математическая модель модифицированной ГЕРТ-сети ГЕРТ-сети были использованы автором для оценки времени выполнения расчетов на кластере с параллельной и последовательной архитектурой обмена данными [36; 60], анализа времени выполнения задачи на неспециализированном гетерогенном кластере Condor [24] и анализа времени изготовления деталей на конвейере, допускающем некоторый процент брака [25]. В процессе применения были выявлены следующие недостатки ГЕРТ-сетей: - трудоемкость аналитического расчета средних и крупных сетей, отсутствие универсальных программных средств расчета ГЕРТ-сетей; - детерминированность всех параметров ГЕРТ-сети (в силу 02 (2.14)); - отсутствие методов выявления факторов, оказывающих наибольшее влияние на результат; - наличие только двух параметров дуг (вероятность активации узла и функция распределения времени его выполнения), отсутствие «дополнительных переменных» и операций над ними. Результатом работы по изменению математической модели ГЕРТ-сети стала сеть, получившая название «модифицированная ГЕРТ-сеть» или МГ-сеть. При описании полученной модели сети, где это возможно, мы будем ссылаться на соответствующие утверждения и определения из математической модели ГЕРТ-сети. Все определения и термины, введенные в параграфе 2.1.1, а также с номерами (2.1)-(2.8) относятся и к МГ-сетям. Для наглядности будем обозначать ограничения МГ-сети ON (буква «О» номер штрих). Ограничения 1 и 3, введенные в параграфе 2.1.3 переносятся в модель МГ-сети без изменений (ОГ и 03 ). В силу ограничения 1 (ОГ), далее мы будем рассматривать только МГ-сети с одним источником. Математическая модель МГ-сети изначально создавалась с учетом того, что следующим этапом будет разработка программного обеспеченья для расчета таких сетей. В основе модели лежит идея «трассировки» реализаций с отбором наиболее вероятных из них. Данный подход позволяет заменить требование детерминированности структуры сети и параметров ее дуг (02) на требование детерминированности структуры сети и вычислимости параметров выходящих дуг после активации узла, из которого они выходят. Ограничение V (02 ). (2.30) Для каждого узла і МГ-сети, если узел і активирован, то параметры всех выходящих из него дуг вычислимы. Алгоритм расчета МГ-сети допускает использования всех шести типов узлов. Для расчета параметров узлов с AND- и IOR-входами требуется предварительно не только рассчитать параметры всех входящих дуг, но и знать параметры узла, «породившего» процесс параллельного выполнения событий. Пусть узел і є V ГЕРТ-сети G(V, Е) имеет более одного предка (Р(і) 1), тогда для любых j, к є Р(і) введем функцию Pr(i, j, k) - множество узлов, являющихся ближайшими общими предками для узла і и путей, заканчивающихся дугами j, i , k, i :
Математическая модель модифицированной ГЕРТ-сети
Математическая модель МГ-сети изначально создавалась таким образом, чтобы всякая МГ-сеть, удовлетворяющая ОГ-04 и для которой заданы дополнительные ограничения Об , будет вычислима при помощи некоторого алгоритма. По своей сути ОГ-04 гарантируют однозначность построения и расчета графа реализации, а Об - конечность количества этих реализаций. Задача расчета МГ-сети делится на три подзадачи: построение множества графов реализаций МГ-сети, расчет графа реализации и обработка результатов. Первую и вторую задачу мы можем разделить только условно, поскольку построение множества графов реализации неразрывно связано с текущим состоянием параметров его узлов.
Во втором, третьем и пятом параграфах данной главы будут представлены обратный и прямой алгоритм построения реализаций МГ-сети (названия даны по названиям алгоритмов обхода графа), а также проведено сравнение их производительности. В четвертом параграфе будут рассмотрены численные методы расчета функций распределения случайных величин, распределений суммы, разности, минимума, максимума случайных величин и дано обоснование их выбора. Также в четвертом параграфе будут представлены формулы обработки результатов.
Введем обозначения, используемые для записи алгоритма. Для записи узлов, дуг и относящихся к ним величинам и функциям будем использовать обозначения, принятые для структур вида «[структура]. [параметр]». Будем обозначать Prs и DFs - множества вещественных и стохастических параметров соответственно. Каждый узел графа реализации будет обладать данными параметрами. Параметр р (вероятность активации узла) является одним из элементов множества Prs (р є Prs). Для узла v є V графа МГ-сети G = Е, V : v.a - количество активаций узла v в процессе построения реализации; v.In - тип входной функции узла (EOR, IOR или AND); v.Out - тип выходной функции узла (STOCH или DET); v.InF(F) - тип входной функции узла для стохастических переменных с функцией распределения F (AND, IOR, MIN, MAX, EQUAL) (только для узлов с IOR- или AND-входом); v.P - множество узлов, являющихся предками узла v; v.S - множество узлов, являющихся потомками узла v; v.MaxA - максимально допустимое количество активаций узла v в графе реализации; v.MaxP - минимально допустимая вероятность события «узел v активирован»; v.dR - узел, являющийся детерминированным источником узла v; v.dS - узел, являющийся детерминированным стоком узла v (только для прямого алгоритма расчета МГ-сети). Для узла є є Е графа МГ-сети G = Е, V (e= vb v2 ): e.vj - узел-начало дуги; e.v2- узел-конец дуги; e.F_Pr(Prj) - функция преобразования параметра Рп є Prs, зависящая от параметров Prs и DFs; e.F_DF(Fj) и e.F_DF_op(Fj) - функция распределения для стохастической переменной, заданной функцией распределения Fj и операция для нее («+», «-» или «=») соответственно. Будем обозначать граф реализации буквой «w». Множество графов реализации обозначим W={\Vj}. Важной особенностью алгоритма построения графа реализации является то, что для каждого непустого графа реализации w всегда определены и единственны начальный и конечный узлы. Обозначим их w.H и w.T соответственно. Узел графа реализации будем обозначать буквой «х» (х є w). x.v - узел МГ-сети, которому соответствует узел графа реализации (x.v є V). x.Prs, x.DFs - значения вещественных и стохастических параметров узла графа реализации. Будем обозначать w={x} - граф реализации, состоящий из единственного узла х. Тогда w.H = w.T = х. Введем операции построения графа реализации: w = M(wj, w2) — новый граф реализации сети, являющийся объединением графов wj и w2 дугой из w2.H в Wj.T. Частным случаем данной операции будем считать М(х, w) = М({х}, w) и M(w, х) = M(w, {х}). w = M(wb W, w2) - новый граф реализации сети, являющийся объединением дугами конечного узла W].T со всеми начальными узлами Wj.H (WJ є W) и объединением дугами конечных узлов Wj.T с начальным узлом w2.H. В блок-схемах, представленных в Приложениях 1-5, индексы переменных будем отображать в квадратных скобках, т.к. MS Visio не позволяет использовать надстрочные и подстрочные индексы. 3.2 Обратный алгоритм расчета МГ-сети Общая идея обратного алгоритма расчета МГ-сети заключается в следующем: - обход графа МГ-сети ведется от выбранного стока к источнику; - обход ведется с помощью рекурсивного алгоритма; - для каждого узла, имеющего EOR-вход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг входит в данный узел; - для каждого узла і, имеющего IOR- или AND-вход, запускается рекурсивный вызовов процедуры расчета узла j, являющегося детерминированным источником узла і, затем рассчитываются все пути от j к і и, используя найденные пути, строятся все реализации, завершаемые узлом і; - расчет вещественных и стохастических переменных производится при «выходе» алгоритма из рекурсии. Блок-схема алгоритма представлена в Приложениях 1 -3. Результатом работы главной процедуры «ОРасчитатьСеть» являются множества реализаций для каждого из стоков, обработка которых будет представлена в пятом параграфе. 3.3 Прямой алгоритм расчета МГ-сети Общая идея прямого алгоритма расчета МГ-сети заключается в следующем: - обход графа МГ-сети ведется от источника к стокам; - обход ведется с помощью рекурсивного алгоритма; - для каждого узла, имеющего стохастический выход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг выходит из данного узла; - для каждого узла і, имеющего детерминированный выход, рассчитываются все пути от і к j, и, используя найденные пути, строятся все реализации, завершаемые узлом j, где j -детерминированный сток узла і; - расчет вещественных и стохастических переменных производится при «углублении» алгоритма рекурсии. Блок-схема алгоритма представлена в Приложениях 3-5. Результатом работы главной процедуры «ПРасчитатьСеть» являяются множества реализаций, обработка которых будет представлена в четвертом параграфе. Следует отметить, что для использования прямого алгоритма расчета МГ-сети необходимо выполнение 05 .
Численные методы, используемые для расчета и обработки результатов МГ-сети
Производительность современных компьютеров стремительно растет, при этом цена «мегагерца» падает. Однако вычислительные потребности в таких областях как моделирование, методы численного анализа, обработка больших массивов информации растут еще быстрее.
При обработке больших объемов данных проблема ограниченности ресурсов персональных компьютеров решается использованием специализированных систем (например, суперкомпьютеров) или созданием механизма распределения задач между различными вычислительными системами (например, кластеров).
Существует несколько основных направлений организации параллельных вычислений, разделяемых по отраслям применения, используемому оборудованию и программному обеспечению [91; 9; 77; 78]. При этом всегда встает вопрос доступности (в частности, стоимости) вычислительных мощностей для конечного потребителя. Наиболее доступными вычислительными системами сейчас являются кластеры. Под кластером будем понимать связанный набор полноценных компьютеров, используемый в качестве единого ресурса. Под словосочетанием "полноценный компьютер" понимается завершенная компьютерная система, обладающая всем, что требуется для ее функционирования, включая процессоры, память, подсистему ввода/вывода, а также операционную систему, подсистемы, приложения и т.д. Словосочетание "единый ресурс" означает наличие программного обеспечения, дающего возможность пользователям, администраторам и даже приложениям считать, что имеется только одна сущность - кластер [91]. Наиболее популярными для специализированных (выделенных) кластеров сейчас считаются библиотеки MPI или PVM.
Библиотеки MPI и PVM разработаны для высокопроизводительных вычислений на специализированных кластерных системах обработки информации. Для их использования требуется адаптация программного кода. Кластеры, работающие под управлением этих библиотек, оптимизированы для высокопроизводительных вычислений и не устойчивы к отказам оборудования, не имеют стандартных средств выполнения «срезов состояния».
Для большого числа инженерных или исследовательских задач использование суперкомпьютера или специализированного кластера невозможно или малоэффективно. Например, алгоритм программы невозможно эффективно преобразовать из последовательного в параллельный или время выполнения задачи сравнимо со временем создания параллельного алгоритма. Также часто требуется выполнять множество одинаковых задач с различными входными данными, при этом время выполнения каждой задачи в отдельности невелико (несколько часов). Для таких задач возможно создать гетерогенную распределенную систему обработки информации, использующую узлы с невысокой надежностью и отказоустойчивостью (например, свободные компьютеры пользователей (рис. 4.3)). Такие системы могут быть построены при помощи библиотек X-СОМ (http://x-com.parallel.ru), Legion (http://www.cs.virginia.edu/ legion) или Condor (http://www.cs.wisc.edu/condor). В частности, Х-СОМ и Condor позволяют использовать в составе единого кластера узлы, не только различающиеся в аппаратной части, но и работающие под разными операционными системами. Они позволяют использовать для вычислений существующую компьютерную технику и уже имеющиеся коммуникации, тем самым существенно удешевляя стоимость создания кластера [83; 95; 15]. Проект Condor старше по возрасту, чем другие подобные проекты, имеет больше последователей, лучшую документацию и используется значительно шире, чем проект Х-СОМ. Поэтому для моделирования будем использовать именно его.
Condor имеет несколько режимов запуска вычислительных задач: Standard, Vanilla, PVM, MPI, Globus, Java. Режимы PVM, MPI, Globus и Java - это поддержка совместимости для программ, написанных с использованием данных библиотек, поэтому мы не будем их рассматривать. Наиболее интересными являются режимы Standard и Vanilla.
Первый накладывает некоторые ограничения на программы, но обеспечивает надежность и миграцию задачи. В режиме «Standard» Condor делает контрольные точки с заданным интервалом. Контрольная точка - это «снимок» текущего состояния задачи. Если необходима миграция задачи (например, пользователь начал использование компьютера), то Condor создает образ контрольной точки, перемещает его на другую машину и возобновляет вычисления с места, где он остановился. Если вычисляющий узел завершил работу аварийно или нарушилась связь с узлом, то Condor размещает на другом узле последний сохраненный образ контрольной точки задачи и возобновляет вычисления. Таким образом, задача может непрерывно вычисляться в течение длительного периода времени. Данный режим соответствует режиму выполнения задачи с периодическим выполнением резервного копирования ее состояния.
Режим Vanilla позволяет запускать произвольное консольное приложение, но не позволяет осуществить миграцию и резервное копирование задачи. Condor собирает информацию об узлах, входящих в пул. Для каждой задачи, размещаемой в очереди пула, исследователь формирует «запрос соответствия», в котором указывает требования и предпочтения к вычислительному узлу для его задачи. Постановка задачи: - выработать требования к механизму сбора информации о работе узлов системы и создать блок ее статистической обработки; - разработать модели и методы анализа временных характеристик узлов гетерогенной распределенной системы обработки информации с недетерминированным поведением ее вычислительных узлов; - подготовить рекомендации по эксплуатации распределенных гетерогенных систем обработки информации для обеспечения эффективного выполнения приоритетных задач обработки информации.
