Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,813

ANALYSIS OF WORK UNITS OF THE DISTRIBUTED INFORMATION PROCESSING SYSTEM USING GERT-NETWORKS

Tsepkova M.I. 1, 2 Stupina A.A. 1, 2 Korpacheva L.N. 1 Fedorova A.V. 1 Dzhioeva N.N. 1
1 Siberial federal university
2 Siberian State Aerospace University named after M.F. Reshetnev
Для большого класса задач важным является возможность использования надежной системы обработки информации с приемлемой производительностью и возможностью одновременной обработки нескольких наборов данных. Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений. В статье приведен аналитический обзор распределенных гетерогенных вычислительных отказоустойчивых систем для высокопроизводительных вычислений, представлен математический аппарат модифицированных GERT-сетей для анализа временных характеристик работы узлов распределенной гетерогенной системы обработки, позволяющий проводить расчет стохастической GERT-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической GERT-сети, предложены прямой и обратный алгоритмы их расчета. Произведено аналитическое сравнение их производительности.
It is important to the use the reliable information processing system with the acceptable performance and the ability to process multiple data sets for a large class of problems. One type of such systems is fail-safe distributed heterogeneous computing systems for high performance computing. The article considers an analytical overview of the distributed heterogeneous computing fault-tolerant systems for high performance computing, presented the mathematical apparatus modified GERT-network for the analysis of the temporal characteristics of the work units of the distributed heterogeneous processing system, that allows to estimate stochastic GERT-network using an arbitrary number of additional real and stochastic parameters of the node stochastic GERT-network offered direct and inverse algorithms for their estimation. The analytical comparison of their performance is given.
GERT-network
distributed heterogeneous processing system
high performance computing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

;

;

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

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

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

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

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

Пусть – время выполнения в -ый раз дуги (.

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

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

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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

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

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

Вероятность активации стока : .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рецензенты:

Антамошкин А.Н., д.т.н., профессор, профессор кафедры экономики и информационных технологий менеджмента института управления бизнес-процессами и экономики ФГАОУ ВПО «Сибирский федеральный университет» (Министерство образования и науки РФ), г. Красноярск;

Попов А.М., д.ф.-м.н., профессор, директор института информатики и телекоммуникаций ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева» (Министерство образования и науки РФ), г. Красноярск.