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

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

Письман Дмитрий Михайлович

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

05.13.01 — Системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2006

Работа выполнена в Научно-исследовательском институте систем управления волновых процессов и технологий.

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

доктор технических наук,

профессор Ковалев Игорь Владимирович

Официальные оппоненты

доктор технических наук, профессор Доррер Георгий Алексеевич

кандидат технических наук, доцент Царев Роман Юрьевич

Ведущая организация: Научно исследовательский институт автоматики и электромеханики при Томском государственном университете систем управления и радиоэлектроники.

Защита состоится «18» мая 2006 года в 13:00 на заседании диссертационного совета Д 212.249.02 при Сибирском государственном аэрокосмическом университете им. академика М.Ф. Решетнева по адресу: пр. Красноярский рабочий, 31, Красноярск, 660014.

С диссертацией можно ознакомиться в библиотеке Сибирского государственного аэрокосмического университета.

Автореферат разослан «17» апреля 2006 г.

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

И.В. Ковалев

АООб/t

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

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

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

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

Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений (системы обработки высокой пропускной способности, high throughput computing), такие как Х-СОМ. Legion или Condor. Такие системы объединяют в единую вычислительную среду распределенные гетерогенные вычислительные ресурсы, причем в качестве узлов, обрабатывающих информацию, могут выступать персональные компьютеры пользователей во время простоя.

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

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

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

Цель исследования: разработка системы анализа временных

информации и подходов к распределению ресурсов системы при управлении выполнением приоритетных задач обработки информации. Задачи исследования:

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

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

- подготовить рекомендации по эксплуатации распределенных гетерогенных систем обработки информации для обеспечения эффективного выполнения приоритетных задач обработки информации. Методы исследования. При выполнении работы использовались методы

системного анализа, теория вероятностей и математической статистики и теория стохастических сетей.

Научная новизна работы

1. Модифицирован математический аппарат стохастических ГЕРТ-сетей. Полученная модификация позволяет проводить расчет стохастической ГЕРТ-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической ГЕРТ-сети. Причем условная вероятность выполнения исходящей дуги узла задана произвольной функцией, вычислимой в момент активации узла.

2. Разработаны прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей. Произведено аналитическое сравнение их производительности.

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

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

Значение для теории. Созданная модифицированная ГЕРТ-сеаь позволяет проводить оценки временных характеристик (или иных аддитивных параметров) систем, представленных в виде стохастической ГЕРТ-сети типа «работа на дуге», где продолжительность выполнения «работы» задана вещественной случайной величиной.

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

Значение для практики. Предложенные в работе процедуры анализа временных характеристик работы узлов распределенной системы обработки информации позволяют:

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

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

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

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

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

Реализация результатов работы. Разработанная среда проведения исследований и модуль расчета модифицированных ГЕРТ-сетей зарегистрированы в Отраслевом фонде алгоритмов и программ (Per. № 5068, код по ЕСПД 03524577.01083-01), что делает ее доступной для широкого круга специалистов по методам анализа стохастических сетей.

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

- математический аппарат модифицированных ГЕРТ-сетей;

- прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей;

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

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

Апробация работы. Основные положения и результаты работы прошли всестороннюю апробацию на всероссийских научно-практических конференциях. В том числе на ежегодной Всероссийской 1П конференции «Технические науки и современное производство» (2005 г., Лутраки, Греция), Всероссийской заочной электронной конференции Российской академии естествознания «Современные телекоммуникационные и информационные технологии» (2005 г.), Всероссийской VI научной конференции «Успехи современного естествознания» (2005 г. Сочи), Всеросийской III научной конференции с международным участием «Приоритетные направления развития науки, технологий и техники» (2005 г., Хургада, Египет), Всероссийской заочной электронной конференции Российской академии естествознания «Новые информационные технологии и системы» (2005 г.),

еженедельных межвузовских семинарах Сибирского государственного технологического университета (Красноярск, 2006).

Диссертационная работа в целом обсуждалась на научно-технических семинарах Научно-исследовательского института систем управления волновых процессов и технологий (2003-2006).

Публикации. По теме диссертации опубликовано 11 печатных работ. Полный список публикаций представлен в конце автореферата.

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

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

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

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

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

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

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

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

При анализе временных характеристик работы узлов распределенной гетерогенной системы обработки информации (далее РГСОИ), использующей в качестве узлов персональные компьютеры пользователей во время их «простоя», данные методы становятся неприменимы. Такие системы не статичны во времени. Для их узлов важными характеристиками являются «доступность» и «отказоустойчивость».

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

Во втором разделе представлен математический аппарат классических ГЕРТ-сетей и его модификация.

Для описания математического аппарата ГЕРТ-сетей введем некоторые определения.

Пусть направленный граф в состоит из непустого множества Б направленных ребер (дуг) и непустого множества V вершин (узлов). В дальнейшем пары слов «ребро» и «дуга», «вершина» и «узел» будем считать синонимами. Пусть каждое ребро однозначно определяется по его начальному и конечному узлам (ребро <\, }> определено начальным узлом г и конечным Х).

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

Определение. Направленный взвешенный связанный граф будем называть сетью.

Каждый узел сети активируется с некоторой вероятностью.

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

Для стохастической ГЕРТ-сети весом дуги <1, ^ является вектор [ру, Ри], где Рц - условная вероятность выполнения дуги <1, при условии активации узла I (для краткости будем говорить вероятность выполнения дуги (работы) <3, ]>), а Бц - условная функция распределения времени выполнения дуги <\, при условии, что _(> выполняется.

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

Виды входных функций.

1. А№)-функция - узел активируется, если выполнены все дуги,

входящие в него.

2. ГОЛ-функция - узел активируется, если выполнена любая дуга, входящая в него.

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

Виды выходных <Ьшкиий.

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

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

На схемах будем обозначать:

^ - БОЯ-вход, - ГОЯ-вход, - АЫО-вход,

^ - стохастический выход, ^ - детерминированный выход.

Рисунок 1. Графическое обозначение входных и выходных функций ГЕРТ-сети

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

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

Определение. ГЕРТ-сеть - это сеть с источниками Я и стоками Б вида «работа на дуге», в которой каждый узел принадлежит одному из шести типов узлов, для каждой дуги ^ определен вес вида [рц, Р'и] с вышеуказанным значением и задано начальное распределение источников сети. Введем обозначения: Р(1) = {]ВУ\<]Л><ЕЕ};

50) = {]еУ\<1,]>еЕ};

Я(I) - {множество узлов, достижимых из узлавключая!)}; Щ г) = { множество узлов, из которых узел г достижим ( включая 1')} Обозначим вО), где 1е11 - подсеть сети О, построенная на множестве вершин 11(1).

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

исключая случай, если они используют один и тот же детерминированный начальный узел и могут использовать один и тот же конечный узел. Пусть £)" - время выполнения в а-й раз дуги <5, ]>.

Для стохастического узла i, пусть Bf - дуга с начальным узлом i, которая выполняется тогда, когда i будет активирован в |3-й раз.

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

Ограничение 2. Для каждого допустимого подмножества R' множества R и для всех i, j eR', i Ф j развитие части сети, соответствующей G(i), не влияет на развитие сети, соответствующей G(j). G(i) и G(j) - независимы.

Для каждого допустимого множества и для любых Wi, W2 е VP, Wi Ф W2 развитие пути, соответствующего Wb не влияет на развитие пути W2. Wi и W2 - независимы.

Для любой дуги <i, j> и вещественного t > О P(D," ^ 11 <i,j> выполняется а-й раз) не зависит от а и

Р(В\3 = <i,j> | i активируется вр-йраз) не зависит от 0. Для любого t>0 развитие проекта, начиная с времени t, условно независимо от времени до t (истории развития проекта) при условии, что состояние проекта во время t известно (свойство Маркова ГЕРТ-сети).

Ограничение 3. Для каждого узла к произвольной циклической структуры С существует путь из к к узлу вне С, такой, что рч > 0 для каждой дуги <i, j> данного пути.

Ограничение 4. Каждый узел, принадлежащий циклу, - STEOR узел.

Ограничение 5. Каждый узел, имеющий более одного предка и не принадлежащий ни одному циклу, имеет AND- или IOR-вход.

Ограничение б. В течение всего времени выполнения ГЕРТ-сети, по крайней мере, одна входная дуга каждой циклической структуры выполняется.

Ограничения 1-6 для краткости будем записывать 01-06. 01-03 -необходимые условия непротиворечивости и однозначности процесса выполнения ГЕРТ-сети.

Определение. ГЕРТ-сеть называется слабо допустимой, если выполняются 01-04.

Определение. ГЕРТ-сеть называется допустимой, если выполняются 0106.

Определение. Будем говорить, что ГЕРТ-сеть рассчитана, если для каждого стока сети определена вероятность активации и условная функция распределения времени активации.

Особо выделим два типа ГЕРТ-сетей:

STEOR-сеть - это ГЕРТ-сеть, состоящая только из узлов с E0R-

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

EOR-сеть - это ГЕРТ-сеть, состоящая только из узлов с EOR-

входом.

Алгоритмов для расчета ГЕРТ-сети в общем случае не существует.

Для всякой допустимой STEOR-сети можно построить эквивалентный полумарковский процесс восстановления. Соответственно, для STEOR-сети

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

Для допустимых EOR-сетей с одним источником разработан аналитический метод решения, построенный па базе эквивалентного преобразования весов [ру, Fy] к специальной W функции и последующего решения топологического уравнения Мейсона для потоковых графов.

Классические ГЕРТ-сети не позволяют провести оценку времени выполнения задачи на узле РГСОИ. В отличие от классических, модифицироваиные ГЕРТ-сети позволяют:

использовать все шесть типов узлов;

проводить оценку временных характеристик стохастической ГЕРТ-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической ГЕРТ-сети;

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

Для описания модификации ГЕР'Г-сетей (далее МГ-сетей) введем новые ограничения (будем указывать со штрихом).

Ограничение 1 и 3 совпадают для МГ-сетей (далее 01' и ОЗ').

Ограничение 2' Ю2'). Для каждого узла i МГ-сети, если узел i активирован, то параметры всех выходящих из него дуг вычислимы.

Для расчета параметров узлов с AND- и IOR-входами требуется не только рассчитать параметры всех входящих дуг, но и знать вероятность активации узла, «породившего» процесс одновременного выполнения событий.

Пусть узел i е V ГЕРТ-сети G(V, Е) имеет более одного предка (|P(i)|>l), тогда для любых j, k е P(i) введем функцию Pr(i, j, k) - множество узлов, являющихся ближайшими общими предками для узла i и путей, заканчивающихся дугами <j, i>, <k, i>:

Pr(i,j,k) = {l\le R(j)nR(k),S(l) n R(j) n R(k) = 0).

Аналогичным образом для узла i е V ГЕРТ-сети G(V, Е), имеющего более одного потомка (|S(i)|>l), для любых j, k е S(i) введем функцию Sc(i, j, k) -множество узлов, являющихся ближайшими общими потомками для узла i и путей, начинающихся дугами <i, j>, <i, k>:

Sc(i,j.k) = {leV\IeR(j)nR(k),P(I)r\R(j)r\R(k) = 0}.

Ограничение 4' Ю4'). Для всякого узла i ГЕРТ-сети G, имеющего IOR-шш AND-вход, для любых j, k е P(i), Pr(i, j, к) = {1}, причем 1 - единственный узел и 1 имеет детерминированный выход.

Ограничение 5' (05'). Для всякого узла i ГЕРТ-сети G, имеющего детерминированный вход, для любых j, k е S(i), Sc(i, j, к) = {1}, причем 1 единственный узел и 1 имеет AND- или IOR- вход.

Ограничение 6' (Об').

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

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

Ртах>0;

3. если в узел \ циклической структуры С входит более одной дуги и хотя бы одна дуга не принадлежит циклу С, то узел 1 имеет ЕСЖ-вход;

4. если из узла \ циклической структуры С выходит более одной дуги и хотя бы одна дуга не принадлежит циклу С, то узел ) имеет стохастический выход;

5. если узел 1 с Г(Ж- или АМН-входом принадлежит циклу, то узел j с детерминированным выходом, являющийся стохастическим началом узла ¡, принадлежит данному циклу.

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

Определение: Будем называть ГЕРТ-сеть 0(У, Е) МГ-сетью, если:

1. в имеет единственный источник и, по крайней мере, один сток;

2. сеть в удовлетворяет ограничениям 01 '-04', Об';

3. задано множество параметров, для каждого узла сети (по крайней мере, вероятность активации);

4. для каждой дуги указаны функции преобразования параметров узлов сети;

5. источник активируется в момент времени 0.

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

1-ш

Ч_г

Рисунок 2. Произвольная МГ-подсеть с начальным узлом 1 и конечным узлом т

Рассмотрим МГ-сеть с вектором веса дуг [ри, Бу]. Обозначения:

р, - вероятность активации узла ц

ру - функция условной вероятности активации узла j при условии активации узла 1, ру = 1, если узел 1 имеет детерминированный выход или <4, ]> — единственная дуга стохастического выхода;

Рун - вероятность выполнения начала дуги <3, )> при условии, что узел, из которого она входит, активирован;

РуК - вероятность выполнения конца дуги <1,]> при условии, что узел, в который она входит, активирован;

Р,(1) - функция распределения времени выполнения узла 1 в момент его активации;

Бу^) - функция условной вероятности распределения времени выполнения Дуги<У>;

FijiXt) - функция распределения времени выполнения t, в начале дуги <i, j> при условии, что узел, из которого она входит, активирован; F,JK(t) - функция распределения времени выполнения tj на конце дуги <i, j> при условии, что узел, в который она входит, активирован. Рассмотрим законы изменения параметров р и F(t). Формулы, приведенные ниже, предназначены для расчета реализации сети. Выполнение дуги <i.i>.

Рщ = Рт *P,i> W = ¡FljK(s)*FIJ'(t~s)ds.

EOR-вход.

Pi = Pi»' Fj(t) = F,jK(t). AND-вход.

J 1,-m,

ч

• • •

j 1

Ч г

Рисунок 3. АЫО-вход

] - вычисляемый АМ)-вход, имеющий стохастическое начало в узле 1. {1] - ш,}, {12- т2},..., {Ы- -И непересекающихся подсетей.

/рГ;

Р1 (0 = пмх^, ..., ) = ^ (?) * (Г) * * ^ (О 1(Ж-вход.

] - вычисляемый 1(Ж-вход, имеющий стохастическое начало в узле I {1] - Ш]}, {12- т2}, ..., {1м - ты} - К непересекающихся подсетей.

= тЬС/.л«.'/„„,«.....) =

= 1 - (1 - Р^ЛО) * 0 - (0) * - * 0 - (0).

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

Вероятность активации стока гк: Ргк = ^рг ■

г

Вероятность активации стока гк ко времени I при условии активации стока гк (функция распределения времени выполнения стока гк):

г

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

содержит функцию преобразования значения переменной. Для каждой стохастической переменной определено ее начальное распределение в источнике сети, и каждая дуга содержит условную функцию распределения некоторой случайной величины и указание на одну из операций: «+», «-», «=» (присвоить).

В третьем разделе представлены прямой и обратные алгоритмы расчета МГ-сети, проведено сравнение их производительности. По результатам аналитического сравнения, прямой алгоритм работает не медленнее обратного, однако требует выполнения ограничения 05'.

Результатом работы прямого и обратного алгоритмов расчета МГ-сети является множество реализаций, удовлетворяющих ограничению 06'. Общее описание обратного алгоритма расчета МГ-сети •

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

если узел 1 имеет ЮЛ- или А"ЫТ>-вход, то запускается рекурсивный вызовов процедуры расчета узла являющегося детерминированным источником узла затем рассчитываются все пути от ] к 1 и, используя найденные пути, строятся все реализации, завершаемые узлом ¡;

расчет вещественных и стохастических параметров производится при «выходе» алгоритма из рекурсии. Общее описание прямого алгоритма расчета МГ-сети ■

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

если узел 1 имеет детерминированный выход, то рассчитываются все пути от \ к }, и, используя найденные пути, строятся все реализации, завершаемые узлом), где] - детерминированный сток узла ¡;

расчет вещественных и стохастических параметров производи гея при «углублении» алгоритма рекурсии.

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

Таким образом, произвольная математическая модель МГ-сети с шестью типами узлов может быть рассчитана на ЭВМ.

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

Среда проведения исследований MGNetwork создана в среде разработки Delphi 6.0. МГ-сеть представлена XML документом специального вида.

Среда проведения исследований MGNetwork имеет два основных режима работы: режим обработки результатов расчета МГ-сети и режим анализа реализаций МГ-сети.

Режим обработки результатов расчета МГ-сети

JF

j По»** I £|*мвгм м

F ■гтаг

-за

UMnflir tu Л'^ижал DwMKnrfF 1 ютятгм ^«JMMeeiAptnmdr ЮЖПСХШГ

||«|мг|»1»|»ч| Г | t ! II !

Рис. 4. Режим обработки результатов расчета МГ-сети Режим обработки результатов расчета МГ-сети предназначен для:

расчета характеристик МГ-сети: вероятность выполнения стока сети, функции распределения времени (или иных параметров) выполнения стока сети, математическое ожидание и дисперсия времени выполнения (или других параметров) всей сети или стока сети;

отображения вещественных параметров МГ-сети; расчета агрегатных функций, математического ожидания и дисперсии от вещественных переменных;

построения графика функций распределения и плотности распределения случайных величин (параметров);

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

Режим анализа реализаций МГ-сети

&»ига|«*а1<ЬР№»'4Г «4 332782*1567

Г.1Р

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

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

Рис. 6. Концептуальная схема системы

РГСОИ состоит из узлов-вычислителей (ВУ) и главного управляющего узла, функциями которого являются:

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

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

управление периодическим резервным копированием (checkpoint) состояния задачи с вычислительного узла;

управление миграцией задач и возобновлением выполнения задачи после сбоя;

периодическое тестирование производительности вычислительных

узлов.

Приоритет задачи, как правило, назначается либо директивно, либо с использованием экономических моделей.

Функциями узла-вычислителя являются:

прием задач на выполнение (если узел доступен); извещение управляющего узла о своем состоянии; предоставление механизма периодического резервного копирования (checkpoint) состояния задачи;

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

Поскольку «доступность» узла РГСОИ не управляемый параметр, моделирование работы узла и оценку времени выполнения задачи провести детерминированными моделями нельзя. Однако собираемая информация о состоянии вычислительных узлов позволяет построить статистический портрет узла и, используя МГ-сети, рассчитать функцию распределения времени выполнения задачи на каждом узле. Полученные результаты позволяют:

прогнозировать время выполнения задачи для разных узлов РГСОИ с допустимой вероятностью;

ранжировать узлы по вероятности завершения выполнения задачи за определенное время;

выбрать оптимальный интервал времени выполнения резервных

копий;

формировать рекомендации по написанию заявки на ресурсы РГСОИ.

МГ-сеть оценки времени выполнения задачи на узле РГСОИ с периодическим резервным копированием состояния задачи

резервным копированием состояния задачи.

Параметры модели оценки времени выполнения задачи на узле РГСОИ

р_п - вероятность успешного освобождения вычислительного узла по требованию системы или пользователя.

p_sd - вероятность доступности узла в момент начала вычислений. F1_DU, F1_NU - функции распределения случайных величин (ф. р. с. в.) времени доступности и недоступности вычислительного узла соответственно и вспомогательные параметры F1_DU2 и F1_NU2 - ф. р. с. в., равные половине с. в. времени доступности и недоступности узла соответственно.

FI S, F1_F и F1_M - ф. р. с. в. времени, необходимого для начала, завершения и миграции задачи соответственно на данном узле.

FI_Z - ф. р. с. в. времени непрерывного выполнения задачи на данном

узле.

F1_R - ф. р. с. в. интервала выполнения резервного копирования состояния задачи с вычисляющего узла.

Параметры узла МГ-сети

Имя Тип параметра Начальное значение (в источнике) Описание

Р Вещественный 1 Вероятность активации узла

F Стохастический 1(х) Функция распределения времени выполнения задачи на узле системы

F_Z Стохастический F1_Z Функция распределения оставшегося времени выполнения задачи на узле

системы при непрерывном вычислении

F Т Стохастический Вспомогательный параметр

F TD Стохастический Вспомогательный параметр

В представленной МГ-сети узлы 0-2, 4-6, 8, 9, 11-21 - ЯТЕСЖ узлы, узлы 3 и 7 имеют детерминированные выходы, узел 7 имеет 1(Ж-вход по функции распределения Р_Т, узел 10 имеет А№)-вход по функции распределения Введем дополнительную функцию БСгЛ

Пусть \|/и(р - независимые случайные величины, заданные функциями распределения Р1(Х) и Р'2(Т) и функциями плотности распределения Я(1) и f2(t). Тогда вероятность того, что \|/ < 1 и И < з1*\|/ + в2*ф < Х2 равна

0(1, *,, Хг,5,,52 ) = РЦц/ < Г) Л (Г, 55 5+ згср г2)) =

F2 (max(

-S{y/ t2 -Stf

dy/,

где в2 е {-1; 1}.

Тогда вероятность того, что М < я1 *ц/ + в2*ф < & равна

Функция распределения случайной величины, удовлетворяющей условиям у < I при условии, что и й *\|/ + в2*ф < 12, имеет вид:

Функция РСШ(Р1, Р2, з2,11, И) - р(И, \2, 82), причем возвращаемое значение параметра равно Р(3(1, 11, И, Э1, в2) для случайных величин, заданных функциями распределения и ¥2.

Для обозначения операций увеличения, уменьшения или присвоения случайной величины 11 на \2, заданных соответствующими функциями распределения и Р2, используются конструкции Р1=+Р2, Р1=-Р2 или Р1=Р2 соответственно.

Дуги стохастической МГ-сети

Дуга Р Операции с параметрами узла Описание

<0, 20> 1 Р=+П в Постановка задачи в очередь.

<20, 21>, <21, 2> psd Р то-+Р1 ош Время доступности узла в начале вычислений при условии доступности узла

<20,2> 1 -p_sd Р то= +н ии, Р= +Р1 N112 Время недоступности узла в начале вычислений при условии недоступности узла

<1, 2> 1 Р=+Р1 к и, V ТО==Р1 ои Ожидание задачи в очереди системы

<2, 3> 1 Р=+Р1 м, Р ТП=-Р1 м Перенос задачи из очереди па вычислительный узел системы.

<3, 4>, <4, 7> 1 р Т=Р то Определение минимума случайных величин из разных входящих дуг узла 7, заданных функциями распределения П.

<3, 5>, <5, 7> 1 Р Т==Р к

<3, б>, <6, 7> 1 Р Т=Р ъ

<7, 8>, <8,10> 1 Определение максимума случайных величин из разных входящих дуг узла 10, заданных функциями распределения Р Т (отсечение

<7, 9>, <9,10> 1 Р_Т=Р10

отрицательных значений).

<10,11>, <11, 13> РСШ(Т Т; -1; И ТО; 1;0;+ШР) Р=+Р Т, Р_ТО=-Р_Т Расчет вероятности того, что узел доступен Уменьшение величины доступности узла и увеличение времени выполнения задачи.

<13,15> РСш(Р Т; -1;Р Ъ, 1; -ШБ; 0) Расчет вероятности успешного выполнения задания.

<15, 16> 1 р_г--р_т Уменьшение величины времени выполнения задачи. Задача рассчитана.

<13, 17>, <17, 3> РСт(Р Т; -1;Р г -, 1; 0;+ЮТ) Р !=-¥ Т, Р ТТ)=-Р1 м, Р=+Р1_М Расчет вероятности того, что произошло выполнение резервного копирования состояния задачи. Уменьшение величины времени, необходимого для расчета задачи, и выполнение резервного копирования

<10, 12>, <12, 14> РСш(Р Т; -1; Р ТБ; 1; -ЮТ; 0) Р-+РТ, Р_то--Р_т Расчет вероятности того, что узел перестал быть доступным. Уменьшение доступности узла и увеличение времени выполнения задачи.

<14, 18> Р_п Узел требует освобождения. Миграция или завершение вычислений выполняется успешно.

<14,1> 1-р_п Узел гребует освобождения. Миграция или завершение вычислений не выполнились.

<18, 15> РСш(Р Т; -Ъ\ 1;-ЮТ; 0) Расчет вероятности успешного выполнения задания.

<18,19>, <19, 1> РСиг(Р Т; -1; Р Ъ\ 1; 0; +1№) р_г=-р_т Миграция задачи прошла успешно. Уменьшение времени, необходимого для расчета задачи, и освобождение вычислительного узла.

МГ-сеть оценки времени выполнения задачи на узле РГСОИ без резервного копирования состояния задачи

копирования состояния задачи.

Параметры модели оценки времени выполнения задачи на узле РГСОИ р sd - вероятность доступности узла в момент начала вычислений. F1_DU, F1JNU - функции распределения случайных величин (ф. р. с. в.) времени доступности и недоступности вычислительного узла соответственно и вспомогательные параметры FI DU2 и F1_NU2 - ф. р. с. в. равные половине с. в. времени доступности и недоступности узла соответственно.

FI S и F1JF - ф. р. с. в. времени, необходимого для начала и завершения задачи соответственно на данном узле.

F1Z - ф. р. с. в. времени непрерывного выполнения задачи на данном

узле.

Параметры узла МГ-сети

Имя Тип параметра Начальное значение (в источнике) Описание

Р Вещественный 1 Вероятность активации узла

F Стохастический 1(х) Функция распределения времени выполнения задачи на узле системы

F_Z Стохастический F17, Функция распределения оставшегося времени выполнения задачи на узле системы при непрерывном вьгшелении

F Т Стохастический Вспомогательный параметр

F TD Стохастический Вспомогательный параметр

В представленной МГ-сети узлы 0-3, 5, 6, 8, 9, 11-16 - вТЕСЖ узлы, узлы 4 и 7 имеют детерминированные выходы, узел 7 имеет 1(Ж-вход по функции распределения Р_Т, узел 10 имеет А№)-вход по функции распределения Р_Т. Дуги стохастической МГ-сети

Дуга Р Операции с параметрами узла Описание

<0, 1> 1 F TD=-F S, F T—F S Инициализация вспомогательных параметров МГ-сеш.

<1,15> 1 F TD=-F F, F T=-F F

<15,16>, <16, 3> p_sd Узел доступен в начале вычислений.

<15, 3> l-p_sd F=+F1 NU2, F T—F TD Узел не доступен в начале вычислений.

<2, 3> 1 F=+F1 NU, F Z=F1 Z Постановка задачи в очередь системы

<3, 4> 1 F-IF1_S Перенос задачи на вычислительный узел и начало вычислений

<4, 5>, <5, 7> 1 F_T—F TD Входная функция узла 7 - определение минимума случайных величин из разных входящих дуг, заданных функциями распределения Р_Т.

<4, 6>, <6, 7> 1 F_T=F_Z

<7, 8>, <8, 10 1 Входная функция узла 10 - определение максимума случайных величин из разных входящих дуг, заданных функциями

<7, 9>, <9, 1 F T=F10

10> распределения Р Т

<10, 11>, <11, 12>, FCut(F Т; -1; F Z; +1; -INF; 0) F=+F Т, F_Z=-F_T Расчет вероятности успешного выполнения задачи. Увеличение величины времени выполнения задачи.

<12, 13> 1 F=+F1_F Успешное завершение задачи. Перенос результатов вычисления.

<10, 14>, <14, 2> FCut(F Т; -1; F Z; +1; 0; +INF) F="+F_T" Расчет вероятности того, что задача не завершила свое выполнение. Увеличение общего времени выполнения задачи Постановка задачи в очередь системы.

Построенные модели оценки времени выполнения задачи применялись при работе с РГСОИ Condor (http://www.cs.wisc.edu/condor/), которая представляет собой надежную, масштабируемую и реально распределенную систему с многолетним опытом функционирования. Она управляет процессом обработки информации с использованием вычислительных систем различных владельцев, с участием множества пользователей и без какой-либо централизованной структуры управления.

Полученные результаты оценок времени выполнения задач продолжительностью 6 и 12 часов на узлах 1 и 2 (рис.9, 10, 11 и 12) соответствуют результатам тестовых запусков на РГСОИ Condor.

Узел 1 - это компьютер, размещенный в классе общего доступа, узел 2 -это компьютер, размещенный в кабинете.

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

аео 1360 toso гэвв t мнн (время »ылолмиия «адачм на у*л* РГСОИ I

Рис. 9 Функции распределения времени выполнения задачи (T_Z=6 часов) на узле 1

07 06 £35 IM D3 D.2 0,1

-3

-з

f у

/ /i /

J //

//

//

//

Г

ЭЮ 860 !ЭЮ 10ЯЗ 2360

1. мнн ЦР«НН »ЫПМ1И4ННЯ (адачн на у>л» РГСОИ)

Рис. 10. Функции распределения времени выполнения задачи (Т_7=6 часов) на узле 2

~1Г.

Г

/ ✓

Г J

Чг 1

1

Г 1Г

У Ч

У

0,7 0,6 8 05 0,4 03

0,1

о

3 - -4

А /

/

720 1220 1720 2220 2730 3220 Я730 ■.им(цнш вимямим цц«науш СГС1Ж)

Рис. 11 Функции распределения времени выполнения задачи (Т_7.=12 часов) на узле 1.

720 1220 1720 2220 2720 3220 3720 I. мнн (время выполнения сдачи ил узле РГСОМ)

Рис, 12. Функции распределения времени выполнения задачи (Г_2~12 часов) на узле 2

Из полученных результатов следует:

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

- для узла 1 и 2 выполнение резервного копирования каждые 2 часа значительно увеличивает общую продолжительность выполнения задачи,

- уменьшение интервала резервного копирования для узлов уменьшает дисперсию времени выполнения задачи.

Полученные функции распределения позволяют рассчитать величину,

Т

обратную коэффициенту ускорения для узла системы (у = Ю, К1 = —)

тк

Р(у) = 1 + Ь\(0) - /К,),

где - время выполнения задачи, И] (0 - функция распределения времени выполнения задачи на узле РГСОИ.

Пример функций распределения величин, обратных коэффициенту ускорения, приведен на рис. 13, где кривая 1 соответствует узлу 2, T_Z=6 часов, без резервного копирования; кривая 2 - узлу 2, 1^=12 часов, без резервного копирования; 3 - узлу 1, Т_г=12 часов, резервное копирование с интервалом в 4 часа, 4 - узлу 1 ; Т_Х=6 часов, резервное копирование с интервалом в 4 часа.

0 1 2 3 4 5 6 7 1/к, к кваффицмвнт ускорения выполнения гадания

Рис. 13. Функция распределения величины обратной коэффициенту ускорения

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ В диссертации представлен математический аппарат модифицированных ГЕРТ-сетей, предложены прямой и обратный алгоритмы их расчета, рассмотрены методы анализа временных характеристик узлов распределенной гетерогенной системы обработки информации, построенные на базе модифицированных ГЕРТ-сетей, и предложены подходы к обеспечению эффективной обработки информации для приоритетных задач.

Дальнейшая работа может проводиться в следующих направлениях: ослабление ограничений, вводимых для модифицированных ГЕРТ-сетей, и создание соответствующих алгоритмов их расчета;

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

Практическим результатом работы является среда проведения исследований, позволяющая рассчитывать модифицированные ГЕРТ-сети и проводить дальнейшую обработку результатов.

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

1. Письман, Д.М. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными / И В Ковалев, Д.М. Письман, М.Ю. Слободин // Системы управления и информационные технологии. № 3 (20), 2005. с. 58-62.

2. Письман, Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-ссти / Д.М. Письман // Проблемы машиностроения и автоматизации. № 1, 2006. с. 18-26.

3. Письман, Д.М. Два метода оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными : сб. научн. тр. / Под общей ред. профессора Н.В. Василенко / Д.М. Письман // Вестник университетского комплекса. Красноярск: ВСФ РГУИТП, НИИ СУВПТ. - Вып. 3 (17), 2005. с. 161-175.

4. Письман, Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере / A.C. Дегтерев, Д.М. Письман // Фундаментальные исследования. 2005, № 4. с. 79-80.

5. Письман, Д.М. Оценка времени изготовления деталей на конвейере, допускающем устранение брака в процессе производства при помощи модифицированной ГЕРТ-сети / A.C. Дегтерев, Д.М. Письман // Современные наукоёмкие технологии. 2005, № 7. с. 87-89.

6. Письман, Д.М. Оценка вероятности завершения расчетов задачи в условиях ограниченности времени для вычислительного кластера Condor при

помощи модифицированной ГЕРТ-сети / Д.М. Письман, М.Ю. Слободин // Современные наукоёмкие технологии. 2005, № 8. с. 30-31.

7. Письман, Д.М. Алгоритм расчета модифицированной ГЕРТ-сети / Д.М. Письман, С.А. Шабалин // Успехи современного естествознания. №11, 2005. с. 36-37.

8. Письмап, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети / Д.М. Письман // Компьютерные учебные программы и инновации. № 6(7), 2005. с. 15.

9. Письман, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети / Д.М. Письман,— М.: ВНТИЦ, 2005.— №.03524577.01083-01, Per. № ОФАП 5068.

10. Письман, Д.М. Использование стохастически заданного параметра времени выполнения работ в МКП и ПЕРТ и расчет данных сетей при помощи модифицированных ГЕРТ-сетей / Д.М. Письман // Фундаментальные исследования. № 2, 2006. с. 44-45.

11. Письман, Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети / Д.М. Письман // Фундаментальные исследования. № 2, 2006. с. 45-47.

»

I \

Подл, в печать 17.01.2006. Формат 60x84/16. Бумага тип. № 1. Офсетная печать.

Усл. печ. л. 1,5. Тираж 100 экз. Заказ № 184.

Отпечатано в ООО "Арагон": 660012, Красноярск, ул. Гладкова, 4.

Введение.

1. Различные подходы к анализу временных характеристик функционирования узлов гетерогенных систем обработки информации.

1.1. Составление расписания загрузки узлов системы с использованием методов теории оптимизации.

1.2. Моделирование функционирования распределенной системы обработки информации при помощи сетей Петри и их расширений.

1.3. Марковские цепи и стохастические сети.

1.4. Конвейерные модели.

1.5. Методы разработки и адоптации программ для выполнения в распределенной системе обработки информации.

1.6. Проблемы оценки временных характеристик распределенных гетерогенных систем обработки информации.

1.6.1. ГРИД (GRID).

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

1.7. Выводы.

2 Математическая модели стохастической ГЕРТ-сети и МГ-сети.

2.1 Математическая модель ГЕРТ-сети.

2.2 Математическая модель модифицированной ГЕРТ-сети.

2.3 Выводы.

3 Алгоритмы расчета МГ-сети.

3.1 Принятые обозначения.

3.2 Обратный алгоритм расчета МГ-сети.

3.3 Прямой алгоритм расчета МГ-сети.

3.4 Численные методы, используемые для расчета и обработки результатов МГ-сети.

3.5 Сравнение производительности прямого и обратного алгоритмов расчета МГ-сети

3.6 Выводы.

4 Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей с использованием среды проведения исследований MGNetwork.

4.1 Среда проведения исследований MGNetwork.

4.2 Анализ временных характеристик работы узлов распределенной системы обработки информации при помощи МГ-сетей.

4.3 Выводы.

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

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

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

Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений (системы обработки высокой пропускной способности, high throughput computing), такие как Х-СОМ, Legion или Condor. Такие системы объединяют в единую вычислительную среду распределенные гетерогенные вычислительные ресурсы, причем в качестве узлов, обрабатывающих информацию, могут выступать персональные компьютеры пользователей во время простоя.

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

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

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

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

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

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

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

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

1. Модифицирован математический аппарат стохастических ГЕРТ-сетей. Полученная модификация позволяет: проводить расчет стохастической ГЕРТ-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической ГЕРТ-сети; причем, условная вероятность выполнения исходящей дуги узла задана произвольной функцией, вычислимой в момент активации узла.

2. Разработаны прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей. Произведено аналитическое сравнение их производительности.

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

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

Значение для теории. Созданная модифицированная ГЕРТ-сеть позволяет проводить оценки временных характеристик (или иных аддитивных параметров) систем, представимых в виде стохастической ГЕРТ-сети типа «работа на дуге», где продолжительность выполнения «работы» задана вещественной случайной величиной.

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

Значение для практики. Предложенные в работе процедуры анализа временных характеристик работы узлов распределенной системы обработки информации позволяют:

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

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

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

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

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

Реализация результатов работы. Разработанная среда проведения исследований и модуль расчета модифицированных ГЕРТ-сетей зарегистрированы в Отраслевом фонде алгоритмов и программ (Per. № 5068, код по ЕСПД 03524577.01083-01), что делает ее доступной для широкого круга специалистов по методам анализа стохастических сетей.

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

- математический аппарат модифицированных ГЕРТ-сетей;

- прямой и обратный алгоритмы расчета модифицированных ГЕРТ-сетей;

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

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

Апробация работы. Основные положения и результаты работы прошли всестороннюю апробацию на всероссийских научно-практических конференциях. В том числе на ежегодной Всероссийской III конференции «Технические науки и современное производство» (2005 г., Лутраки, Греция), Всероссийской заочной электронной конференции Российской академии естествознания «Современные телекоммуникационные и информационные технологии» (2005 г.), Всероссийской VI научной конференции «Успехи современного естествознания» (2005 г. Сочи), Всеросийской III научной конференции с международным участием «Приоритетные направления развития науки, технологий и техники» (2005 г., Хургада, Египет), Всероссийской заочной электронной конференции Российской академии естествознания «Новые информационные технологии и системы» (2005 г.).

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

4.3 Выводы

1. Среда проведения исследований MGNetwork:

- позволяет проводить расчеты МГ-сетей, используя прямой и обратный алгоритмы МГ-сети, прямую свертку или свертку, используя БПФ;

- открытый формат XML документа, описывающий структуру сети, может быть создан в любом текстовом редакторе и позволяет в дальнейшем создать специализированное программное обеспечение визуальному построению МГ-сети; / J—з

I/ -4

1 i

2 7 /

J

-г

- возможность экспорта полученных результатов и их последующего анализа при помощи другого ПО;

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

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

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

Заключение

В диссертации представлен математический аппарат модифицированных ГЕРТ-сетей, предложены прямой и обратный алгоритмы их расчета, рассмотрены методы анализа временных характеристик узлов распределенной гетерогенной обработки информации, построенные на базе модифицированных ГЕРТ-сетей, и предложены подходы к обеспечению эффективной обработки информации приоритетных задач.

Дальнейшая работа может проводиться в следующих направлениях:

- ослабление ограничений, вводимых для модифицированных ГЕРТ-сетей, и создание соответствующих алгоритмов их расчета;

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

Практическим результатом работы является среда проведения исследований, позволяющая рассчитывать модифицированные ГЕРТ-сети и производить дальнейшую обработку результатов.

1. Авербах, Л.И., Воропаев, В.И., Гельруд Я.Д. Планирование работ проекта с учетом приведенной стоимости. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2001.— Режим доступа: http://www.sovnet.ru/pages/casm5.rar

2. Аврамчук, Е.Ф., Вавилов, А.А., Емельянов, С.В. и др. Технология системного моделирования.—М.: Машиностроение; Берлин: Техник, 1988.— ISBN 5-217-00150-Х.

3. Андреев, А.Н., Воеводин, В.В. Методика измерения основных характеристик программно-аппаратной среды. / ВВС ДВО РАН. — Режим доступа: http://www.dvo.ru/bbc/benchmarks.html

4. Антамошкина Е.А., Дегтерев А.С., Ерыгин Ю.В. GERT-сетевой анализ производственных процессов Электронный ресурс. / Электронный журнал «ИССЛЕДОВАНО В РОССИИ», 2004, с. 2571-2576.— Режим доступа: http://zhurnal.ape.relarn.ru/articles/2004/240.pdf.

5. Бахвалов, Н.С., Жидков, Н.П., Кобельков Г.М. Численные методы. — 3-е изд. — М.: Бином. Лаборатория знаний, 2004. — ISBN 5-94774-175-Х. — 636 с.

6. МГУ им. М.В. Ломоносова, 2005. с. 330-336. — ISBN 5-89407-230-1. — Режим доступа: http://lvk.cs.msu.su/mco/mso2005-full.doc

7. Букатов, А.А., Дацюк, В.Н., Жегуло, А.И. Программирование многопроцессорных вычислительных систем. — Ростов-на-Дону: ЦВВР, 2003. ISBN 5-94153-062-5.

8. Вентцель Е.С. Теория вероятностей.— 8-е изд., стер.— М.: Высш. шк., 2002. — 575 с.

9. Вентцель Е.С., Овчаров Л.А. Теория вероятностей и ее инженерные приложения. Учеб. пособие для втузов. — 2-е изд., стер. — М.: Высш. шк., 2000. —480 с.

10. Воеводин, В., Филамофитский, М. Суперкомпьютер на выходные. Электронный ресурс. // Открытые системы, № 05, 2003.— Режим доступа: http://www.osp.ru/os/2003/05/043.htm

11. Воропаев, В.И., Гельруд, Я.Д. Использование ЦАСМ при управлении проектами. Электронный ресурс. / Публикации Российской Ассоциации Управления Проектами "СОВНЕТ", 2001.— Режим доступа: http://www.sovnet.ru/pages/casm4.rar

12. Давыдов, И.Н. Оптимизационные сетевые модели формирования циклических технологических процессов: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, САА, 2000.

13. Дегтерев А.С., Письман Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере. // Фундаментальные исследования. 2005, № 4. с. 79-80.

14. Дегтерев А.С., Письман Д.М. Оценка времени изготовления деталей на конвейере, допускающем устранение брака в процессе производства при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 7. с. 87-89.

15. Джиоева, Н.Н. Многокомпонентная сетевая модель формирования алгоритмов распределенной обработки и управления в АСУ: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2004.

16. Доррер, Г.А. Методы анализа вычислительных систем: Учеб. пособие для студентов направления 552800 и специальности 220400 всех форм обучения. — Красноярск, СибГТУ, 2000 г.

17. Зализняк, В.Е. Основы научных вычислений. Введение в численные методы для физиков: Учеб. пособие для студентов естественно-научных и технических специальностей высших учебных заведений. — М.: Едиториал УРСС, 2002. — 296 с.: ил. — ISBN 5-354-00138-2.

18. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2001. с. 80-83.— Режим доступа:http://www.software.unn.ac.ru/ccam/files/Seminar/Seminarl.pdf

19. Кпиманов В.П., Сутягин М.В., Быстрикова В.А. Кластеризация вычислительных систем и вопросы их катастрофоустойчивости // Автоматизация и управление в машиностроении. № 18, 2002.

20. Ковалев, И.В., Письман, Д.М., Слободин, М.Ю. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными. // Системы управления и информационные технологии. № 3 (20), 2005. с. 58-62.

21. Ковалев, И.В., Царев, Р.Ю. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах : учеб. пособие. Красноярск: ИПЦ КГТУ, 2003. — 111 с.

22. Коваленко, В.Н., Корягин, Д. А. Организация ресурсов ГРИД. Электронный ресурс. — М., 2004. — Режим доступа: http://www.gridclub.ru/library/publication.2004-ll-29.9287628406/view.

23. Королюк, B.C., Турбин, А.Ф. Полумарковские процессы и их приложения. — Киев: Наукова думка, 1975. — 184 с.

24. Корячко, В. П., Шибанов, А. П., Шибанов, В. А. Численный метод нахождения закона распределения выходной величины GERT-сети. // Информационные технологии. 2001. № 7 — М.: Машиностроение, с. 16-21.

25. Котов В.Е. Сети Петри.— М.: Наука. Главная редакция физико-математической литературы, 1984.

26. В.А. Сойфера. Самара, 2004.С.151-159.— Режим доступа: http://www.ipsi.smr.ru/hpc-2004/tezisy.pdf

27. Ларионов, А. М., Майоров, С.А., Новиков, Г. И. Вычислительные комплексы, системы и сети. Л.: ЭНЕРГОАТОМИЗДАТ, 1987.

28. Письман Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации. 2006,№ I.e. 18-26.

29. Письман Д.М. Использование стохастически заданного параметра времени выполнения работ в МКП и ПЕРТ и расчет данных сетей при помощи модифицированных ГЕРТ-сетей. // Фундаментальные исследования. 2006, № 2. с. 44-45.

30. Письман Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. // Фундаментальные исследования. 2006, № 2. с. 45-47.

31. Письман Д.М., Слободин М.Ю. Оценка вероятности завершения расчетов задачи в условиях ограниченности времени для вычислительного кластера Condor при помощи модифицированной ГЕРТ-сети. // Современные наукоёмкие технологии. 2005, № 8. с. 30-31.

32. Письман Д.М., Шабалин С.А. Алгоритм расчета модифицированной ГЕРТ-сети. // Успехи современного естествознания. 2005, № 11. с. 36-37.

33. Письман, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. // Компьютерные учебные программы и инновации. № 6(7), 2005. с. 15.

34. Письман, Д.М. Библиотека для расчета модифицированной ГЕРТ-сети. — М.: ВНТИЦ, 2005. — № .03524577.01083-01, Per. № ОФАП 5068.

35. Предсказатель производительности DVM-программ (Предиктор). Руководство пользователя. Июнь, 2000 г. Электронный ресурс. — Режим доступа: http://www.kiam.ru/dvm/dvmhtm 1107/rus/usr/predictor/predUGr.html

36. Родин, А.В., Бурцев, В.Л. Классификации распределенных систем? Электронный ресурс. / Московский инженерно-физический институт (государственный университет). — Режим доступа: http://www.gridclub.ru/library/publication.2006-02-07.3586958006/view

37. Самарский, А.А., Гулин, А.В. Численные методы: Учеб. пособие для вузов. — М.: Наука, 1989. —432 с. — ISBN 5-02-013996-3.

38. Трохов, Н.Н. Оптимизация технологи управления опасными производствами: Автореф. диссертации на соискание ученой степени кандидата технических наук. Красноярск, НИИ СУВПТ, 2002.

39. Филлипс, Д., Гарсиа-Диас, А. Методы анализа сетей. М.: Мир, 1984.

40. Царев, Р.Ю. Семенько Т.И., Гаврилов Е.С. Модели формирования и алгоритмы распределенной обработки информации и управления : учеб. пособие. Красноярск: ИПЦ КГТУ, 2005. 240 с.

41. Шибанов, А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности. // Информационные технологии. 2002. № 1 — М.: Машиностроение.

42. Шнитман, В. Современные высокопроизводительные компьютеры. Электронный ресурс. / Информационно-аналитические материалы Центра Информационных Технологий, 1996. — Режим доступа: http://www.citforum.ru/hardware/svk/contents.shtml.

43. Шпаковкий, Г.И., Серикова, Н.В., Программирование для многопроцессорных систем в стандарте MPI — Минск: БГУ, 2002.

44. Modelling and Evaluation of Computer and Communication Systems (MMB & PGTS 04 Dresden September 2004). 2004.

45. Condor Version 6.6.10 Manual / Condor Team, University of Wisconsin-Madison. — Режим доступа: http://www.cs.wisc.edu/condor/manual/v6.6/

46. Foster, Ian. What is the Grid? A Three Point Checklist. Электронный ресурс. / Argonne National Laboratory & University of Chicago. July 20, 2002. — Режим доступа: http://www-fp.mcs.anl.gov/~foster/Articles/WhatIsTheGrid.pdf.

47. German, Reinhard. Non-Markovian Analysis. Lectures on Formal Methods and Performance Analysis, First EEF/Summer School on Trends in Computer Science. Heidelberg : Springer, 2001, (LNCS Bd. 2090), S. 156-182.

48. Litzkow, M., Livny, M., Mutka, M., Condor A Hunter of Idle Workstations, Proceedings of the 8th International Conference of Distributed Computing Systems, June 1988. — Режим доступа: http://www.cs.wisc.edu/condor/doc/icdcsl988.pdf

49. Neumann, К. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization : Lecture Notes in Economics and Mathematical Systems. Berlin : Springer-Verlag, 1990. - ISBN 3-540-52664-1.

50. Pfister G. Sizing Up Parallel Architectures. DataBase Programming & Design OnLine. Электронный ресурс. May 1998.— Режим доступа: http://www.dbpd.com/vault/9805feat.htm, http://www.citforum.ru/hardware/articles/art5.shtml.

51. Thompson, W.J. Computing for scientists and engineers. — NY: John Wiley & Sons, Inc., 1992. — ISBN 0-471-54718-2.

52. Yuan, Shi. Reevaluating Amdahl's Law and Gustafson's Law (ABSTRACT). Электронный ресурс. / Temple University. Computer and Information Sciences

53. Department.— Philadelphia, 1996.— Режим доступа:http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.htm.

54. Процедура ОРассчитатьСеть(\Л/)

55. Выходной переметр W множество реализаций МГ-сетиначало процедуры

56. Для v1. из V, i от 1 до |V|Лг

57. Для vs1. из S, i от 1 до |S|

58. ОПостроитьРеализации (vr, vs1., iPrs, iDFs, Wt)

59. S множество стоков МГ-сетиvr узел-источник МГ-сети, iPrs, iDFs - начальные значения параметров в узле-источнике1. W = W + Wtтар.,'конец процедуры^

60. Процедура ОПостроитьРеализации(уз, vc, Prs, DFs, W).

61. Входные параметры: vs узел-источник подсети; vc - текущий узел;

62. Prs, DFs параметры узла-источника сети. Выходные параметры: W - множество графов реализации сети.начало процедуры1. W=0r-дада—►x.v = vs, x.Prs = Prs, x.DFs = DFs, W = {{x}}нет-И 2

63. Для vj. из VC.P, j от 1 до |VC.P|

64. ОПостроитьРеализации (vs, vj., Prs, DFs, Wt)1. W1 =W1 +wt1 rvd.j5 110; \ Для w1. из W1, i от 1 до |W111. X1.\ f=Vs

65. РассчитатьДугу (w1.T.v, vs, wi.T.Prs, w[i].T.DFs, x[i].Prs, x[i].DFs)1 1. W = W + M(w1., xi.) w1., iо

66. Для каждого выбора w21. из W2K1. Ч.i от 1 до |vc.P| (выбор всех возможных вариантов множества w2 из множества множеств W2)

67. РассчитатьДугу (w21.T.v, vc, w2i.T.Prs, w2[i].T.DFs, Prep], DFs[i])x.v = vc

68. Расчитать параметры узла графа реализацииx.Prs и x.DFs по множеству графов {w21.} и графу wk., используя формулы (2.39), (2.40) и (2.48)vc.a = vc.a -1