Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Файлы

Письман Д.М. Слободин М.Ю.

Статья в формате PDF

138 KB

Однако, гетерогенный и неспециализированный кластер имеет нестабильную производительность, что влечет трудность прогнозирования времени выполнения вычислительной задачи. ГЕРТ-сети позволяют получить оценки времени выполнения и вероятности успешного завершения задач при отсутствии дополнительных ограничений. [2, 3]

Подробное описание ГЕРТ-сетей можно посмотреть в книге K. Neumann [4] и Д. Филлипс, А. Гарсиа-Диас [5].

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

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

Сеть G (N, A) называется МГ-сетью (модифицированной ГЕРТ-сетью), если:

1. она представлена ориентированной связанной сетью;
2. она обладает, по крайней мере, одним источником и одним стоком;
3. каждый узел из N достижим, по крайней мере, из одного источника и из каждого узла достижим, по крайней мере, один сток;
4. заданы типы входящих и выходящих функций узлов;
5. задано начальное распределение вероятности выполнения источников q_sub, где sub ⊆ R;
6. в течение каждого выполнения проекта для каждого стока активируется не более одного источника, из которого данных сток достижим;
7. 7. задан набор параметров, которыми обладает каждый активированный узел (по крайней мере, вероятность активации);
8. 8. для каждой дуги указаны функции преобразования параметров активированного узла, вычислимые в момент его активации;
9. 9. хотя бы один источник активируется в момент времени 0 (если параметр, отвечающий за время, определен).

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

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

Таким образом, реализация сети является допустимой, если в процессе выполнения каждый из активированных узлов сети активируется не более, чем maxA>=1 раз, или он активируется с вероятностью, большей minP>0.

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

Рассмотрим модель вычислительного процесса задачи на кластере.

Для этого введем следующие параметры узлов: p_i - вероятность активации узла, F_i(t) - функция распределения времени вычисления задачи, Ft_i(t) - функция распределения допустимого резерва времени вычисления. Для каждого действия задается функция распределения времени его выполнения F_ij(t) или 1(0), если время нулевое. В данной задаче функции F_ij(t) и Ft_ij(t) описывают поведение обратных случайных величин t и (-t) соответственно. Все узлы имеют EOR-вход и стохастический выход.

Действия:

<0, 1> Ожидание в очереди момента получения данных. p_ij=1;

<1, 2> Получения данных с управляющего узла кластера. p_ij=1;

<2, 4> Выполнение вычислений, завершившихся успехом. p_ij=1-p_у;

<4, 5> Возврат данных. p_ij=1;

<2, 3> Ошибка в ходе выполнения вычислений, перенос задачи допустим. p_ij=(p_у)*(FtÅFt₂₃)(0);

<2, 6> Ошибка в ходе выполнения вычислений, перенос задачи недопустим. p_ij=(p_у)*(1-(FtÅFt₂₃)(0));

<3, 1> Перенос задачи на другой узел. p_ij=1.

Где F1  F2 - свертка функций F1 и dF2, p_у - вероятность доступности узла.

Начальные значения источника: p₁ = 1, F₁(t) = 1(0), Ft₁ = 1(Tmax).

Вероятность успешного завершения вычислений (узел 5) равна , где r - номер реализации МГ-сети.

СПИСОК ЛИТЕРАТУРЫ

1. Douglas Thain, Todd Tannenbaum, and Miron Livny. Distributed Computing in Practice: The Condor Experience. Computer Sciences Department, University of Wisconsin-Madison. 2004.
2. Дегтерев А.С., Письман Д.М. GERT-сетевой анализ времени выполнения задачи на неспециализированном гетерогенном кластере. Фундаментальные Исследования. № 4. 2005. Стр. 79-80.
3. Письман Д.М. Модели оценки времени выполнения задачи на кластере с последовательной и параллельной архитектурой обмена данными. Вестник университетского комплекса: Сб. научн. Трудов / Под общей ред. Профессора Н.В. Василенко; Красноярск: ВСФ РГУИТП, НИИ СУВПТ. - 2005. Вып. 3 (17). Стр. 161-175.
4. K. Neumann. Stochastic Project Networks. Temporal Analysis, Scheduling and Cost Minimization. Springer-Verlag.
5. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей.-М.: Мир, 1984. стр. 387-411.

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