Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

Personal portfolio

Для расчета в гетерогенных кластерных системах, а так же в кластерах, использующих узлы с невысокой надежностью и отказоустойчивостью используются библиотеки типа Condor (http://www.cs.wisc.edu/condor/). В частности, Condor позволяет использовать в составе единого кластера узлы не только различающиеся в аппаратной части, но и работающие под разными операционными системами. Библиотека Condor позволяет использовать для вычислений существующую компьютерную технику и уже имеющиеся коммуникации, тем самым существенно удешевляя стоимость создания кластера. [1]

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

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

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

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

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

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

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

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

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

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

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

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

Действия:

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

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

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

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

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

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

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

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

Начальные значения источника: p1 = 1, F1(t) = 1(0), Ft1 = 1(Tmax).

Вероятность успешного завершения вычислений (узел 5) равна f, где 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.