Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

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

Цепкова М.И. 1, 2 Ступина А.А. 1, 2 Корпачева Л.Н. 1 Федорова А.В. 1 Джиоева Н.Н. 1
1 ФГАОУ ВПО «Сибирский федеральный университет»
2 ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнёва»
Для большого класса задач важным является возможность использования надежной системы обработки информации с приемлемой производительностью и возможностью одновременной обработки нескольких наборов данных. Одним из видов таких систем являются распределенные гетерогенные вычислительные отказоустойчивые системы для высокопроизводительных вычислений. В статье приведен аналитический обзор распределенных гетерогенных вычислительных отказоустойчивых систем для высокопроизводительных вычислений, представлен математический аппарат модифицированных GERT-сетей для анализа временных характеристик работы узлов распределенной гетерогенной системы обработки, позволяющий проводить расчет стохастической GERT-сети с использованием произвольного числа дополнительных вещественных и стохастических параметров узла стохастической GERT-сети, предложены прямой и обратный алгоритмы их расчета. Произведено аналитическое сравнение их производительности.
GERT-сеть
распределенная гетерогенная система обработки
высокопроизводительных вычисления
1. Гергель, А.В., Виноградов, Р.В. Оценка сложности коммуникационных операций в кластерных вычислительных системах // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы второго Международного научно-практического семинара / под ред. проф. Р.Г. Стронгина. – Нижний Новгород: Изд-во Нижегородского госун-та. – 2002. – С. 73-77.
2. Мирошник, М.А. Синтез распределенных вычислительных сред на базе компьютерных сетей // Системы обработки информации. – 2013. – № 7 (114). – С. 86-89.
3. Письман, Д.М. Анализ временных параметров сетевых моделей на базе модифицированной ГЕРТ-сети. // Проблемы машиностроения и автоматизации. – 2006. – № 1. – С. 18-26.
4. Письман, Д.М. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. // Фундаментальные исследования. – 2006. – № 2. – С. 45-47.
5. Ступина, А.А. Планирование задач в распределенных гетерогенных информационных системах // Современные проблемы науки и образования. – 2013. – № 5.

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

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

На сегодняшний день системы обработки информации все чаще используются для решения управленческих, исследовательских и производственных задач. Одним из видов таких систем являются гетерогенные вычислительные системы высокой надежности для высокопроизводительных вычислений (системы обработки высокой пропускной способности). Наиболее известные технологии: 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-сети с шестью типами узлов может быть рассчитана на ЭВМ.

Рецензенты:

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

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


Библиографическая ссылка

Цепкова М.И., Ступина А.А., Корпачева Л.Н., Федорова А.В., Джиоева Н.Н., Цепкова М.И., Ступина А.А. АНАЛИЗ РАБОТЫ УЗЛОВ РАСПРЕДЕЛЕННЫХ СИСТЕМ ОБРАБОТКИ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ GERT-СЕТЕЙ // Современные проблемы науки и образования. – 2015. – № 2-2. ;
URL: https://science-education.ru/ru/article/view?id=21953 (дата обращения: 28.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674