Применение GERT-сетей для анализа распределенных систем обработки информации

Размещено на http://www.allbest.ru/

Сибирский федеральный университет

Применение Gert-сетей для анализа распределенных систем обработки информации

Цепкова М.И.

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

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

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

Apples PST, Netsolve, Punch, XTRemweb и т.д. используют простые схемы распределения, когда центральный компьютер, отвечающий за распределение, решает, какие задачи должны быть выполнены на каком ресурсе, используя функции стоимости, задаваемые системными параметрами. Они не рассматривают цену использования каждого ресурса, а это означает, что значимость выполнения всех приложений в любое время одинакова, что в реальности далеко не так. Значимость должна возрастать с приближением срока выполнения прикладной задачи.

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

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

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

Некоторые из рассматриваемых средств реализуют методы распределения нагрузки, что снижает трудоемкость разработки приложений при использовании этих средств. Но данные методы не обеспечивают рационального использования ресурсов сети, т.к. не исключают простоя компьютеров. Так, например, в ADM (Application Data Movement) точность распределения зависит от некоторой функции, которую должен написать разработчик. Метакомпьютинг Condor требует описания ресурсов от разработчика и распределение нагрузки производит на основании этого описания. При этом не учитывается реальная загрузка компьютеров, которая может меняться во время вычисления. Метакомпьютинг Piranha просто выбирает один из свободных компьютеров случайным образом, не учитывая тем самым реальных возможностей компьютеров и требуемых ресурсов для задачи. Sun Grid Engine и Netsolve распределение нагрузки производят на основании данных мониторинга сети, где собирают информацию о загруженности вычислительных узлов в текущий момент времени и соответственно с этим отправляют задачу на наименее загруженный компьютер. Подобный подход обеспечивает более точное распределение нагрузки, не требующее от разработчика каких-либо данных или действий, но при этом возникают дополнительные накладные расходы на осуществление мониторинга.

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

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

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

При анализе временных характеристик работы узлов распределенной гетерогенной системы обработки, использующей в качестве узлов персональные компьютеры пользователей во время их «простоя», данные методы становятся неприменимы. Такие системы не статичны во времени. Для их узлов важными характеристиками являются «доступность» и «отказоустойчивость» [2].

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

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

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

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

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

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

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

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

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

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

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

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

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

GERT-сеть - это сеть с источниками и стоками вида «работа на дуге», в которой каждый узел принадлежит одному из шести типов узлов, для каждой дуги (, ) определен вес вида [ , ] с вышеуказанным значением и задано начальное распределение источников сети.

Введем обозначения:

)= ?| ,)? ;

)= ?| ,)? ;

)={множество узлов достижимых из узла (включая )}; )={множество узлов из которых узел достижим (включая )}.

Обозначим ), где ? - подсеть сети , построенная на множестве вершин).

Обозначим множество последовательностей активации сети.

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

MG-сетью называется GERT-сеть , ) если:

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

2. Cеть G удовлетворяет ограничениям:

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

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

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

Пусть узел ? GERT-сети , ) имеет более одного предка | )|>1), тогда для любых , ? ) введем функцию ! , , ) - множество узлов, являющихся ближайшими общими предками для узла и путей, заканчивающихся дугами ,), , ):

Pr , , )= $|$? )? ), $)? )? )=? .

Аналогичным образом для узла i?V GERT-сети G V,E), имеющего более одного потомка |S i)|>1), для любых j,k?S i) введем функцию Sc i,j,k) - множество узлов, являющихся ближайшими общими потомками для узла i и путей, начинающихся дугами i,j), i,k):

Sc i,j,k)= l?V|l?R j)?R k),P l)?R j)?R k)=? .

в. Для каждого узла k произвольной циклической структуры 1

существует путь из к узлу вне 1, такой, что >0 для каждой дуги ,) данного пути.

г. Для всякого узла GERT-сети , имеющего IOR- или AND-вход, для любых , ? ), ! , , ) = {1}, причем 1 - единственный узел и 1 имеет детерминированный выход.

д. Для всякого узла GERT-сети , имеющего детерминированный вход, для любых , ? ), 4 , , ) = {1}, причем 1 - единственный узел и 1 имеет AND- или IOR- вход.

е. Реализация сети является допустимой, если в процессе выполнения каждый из активированных узлов сети активируется не более, чем 1 раз; реализация сети является допустимой, если в процессе выполнения каждый из активированных узлов сети активируется с вероятностью, большей 567 > 0; если в узел циклической структуры 1 входит более одной дуги и хотя бы одна дуга не принадлежит циклу 1, то узел имеет EOR-вход; если из узла циклической структуры 1 выходит более одной дуги и хотя бы одна дуга не принадлежит циклу 1, то узел имеет стохастический выход; если узел с IOR- или AND-входом принадлежит циклу, то узел с детерминированным выходом, являющийся стохастическим началом узла , принадлежит данному циклу. Данноегарантирует, что для любой сети количество реализаций конечно, следовательно, сеть вычислима с использованием ЭВМ.

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

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

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

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

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

Вероятность активации стока !9: 89 =?8 8.

Вероятность активации стока !9 ко времени ; при условии активации стока !9 (функция распределения времени выполнения стока !9): 89 ;)=

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

»,«=» (присвоить) [3].

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

Общее описание обратного алгоритма расчета MG-сети:

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

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

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

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

Общее описание прямого алгоритма расчета MG-сети:

- обход графа MG-сети ведется от источника к стокам;

- обход ведется с помощью рекурсивного алгоритма;

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

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

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

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

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

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

Список литературы

1. Мирошник М.А. Синтез распределенных вычислительных сред на базе компьютерных сетей // Системы обработки информации. - 2013. - № 7 (114). - С. 86-89.

2. Гергель, А.В., Виноградов, Р.В. Оценка сложности коммуникационных операций в кластерных вычислительных системах // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы второго Международного научно-практического семинара / Под ред. проф. Р.Г. Стронгина. Нижний Новгород: Изд-во Нижегородского госуниверситета. - 2002. - С. 73-77.

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

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

5. Ступина А.А. Планирование задач в распределенных гетерогенных информационных системах // Современные проблемы науки и образования. - 2013. - № 5.

Размещено на Allbest.ru