, д-р техн. наук
Кемеровский технологический институт
(Россия, Кемерово, б-р. Строителей, 47
Тел.(38, E-mail: *****@***ru)
, к-т техн. наук
Ин-т физики полупроводников СО РАН
(Россия, Новосибирск, пр. Лаврентьева, 13
Тел.(3, E-mail: *****@)
ОЦЕНКИ ПОКАЗАТЕЛЕЙ ОСУЩЕСТВИМОСТИ РЕШЕНИЯ ЗАДАЧ НАБОРА НА РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ*
Аннотация. Предлагается подход к расчету показателей осуществимости решения задач наборов. Предложены расчеты моментов не только первого, но и второго порядка. Полученные формулы обладают наглядностью и могут быть использованы при ручном счете.
Введение. Высокопроизводительные вычислительные системы (ВС) активно используются при решении задач различных областей, в частности, геофизики. Среди основных режимов функционирования ВС выделяется режим обработки задач наборов.
При анализе эффективности функционирования вычислительных систем (ВС) (как сосредоточенных, так и распределенных) используются показатели осуществимости решения задач [1,2].
В работе предлагается подход к расчету математических ожиданий и дисперсий показателей осуществимости решения задач набора.
Расчет показателей осуществимости решения задач на ВС. Рассмотрим решение набора 
(>0) сложных задач на ВС. Сложная задача (представлена параллельной программой [2]) решается на всем выделенном ресурсе.
Пусть выделенный ресурс составляет n ЭМ, тогда интенсивность решения задачи будем считать равной 
, где b - интенсивность решения задачи на одной ЭМ (оцениваются потенциальные возможности ВС [1, 2]).
Так как задачи сложные, то они решаются последовательно.
Требуется вычислить математическое ожидание Ai(t) - числа задач, находящихся в системе [2], и соответствующую дисперсию Di (t) в момент времени tÎ[0, ¥) при начальных условиях:
, 
, 
. (1)
Обозначим через 
- вероятность того, что к моменту времени t в ВС находится k задач (включая обслуженную), 
.
В такой постановке имеем систему, представленной в виде
(2)
с начальными условиями
, 
, 
.
Условие нормировки, являющееся следствием системы уравнений, имеет вид
, 
.
Вводя производящую функцию [4]
,
имеем
, 
, (3)
Систему (2) приводим к уравнению
, 
, (4)
из которого, после необходимых преобразований, получаем, с учетом (3), систему
(5)
с начальными условиями (1).
Вероятность 
неизвестна, однако, если число i задач велико, то полагая 
, 
, 
, получаем приближенное решение системы (5)
(6)
Из (4) следует, что среднее время, необходимое для решения i сложных задач набора, tср = i / (n b) при стандартном отклонении 
. Например, при выделенном ресурсе n=100 ЭМ, время необходимое для решения набора из 400 задач, при b=0,1 1/ч составит tср = 400 / (100 × 0,1)=40 ч. С учетом отклонения, 
, получаем tср = 20 / (100 × 0,1)=2 ч. Таким образом, для среднего времени решения набора задач с учетом стандартного отклонения имеем: 
ч.
Замечание. Точное решение системы (5) слишком громоздко. Именно поэтому решение (6), при указанных упрощениях, оправдано.
Приведем точное решение системы (2). Применяя преобразование Лапласа (
, где 
- функция ограниченного изменения [3]) к уравнению (4), получим
, 
(7)
или
. (8)
Так как нуль в знаменателе существует внутри круга 
, то приравнивая к нулю числитель и учитывая нуль знаменателя, относительно z, с необходимостью, имеем
. (9)
Подставляя правую часть формулы (9) в (8) и разделив полученный числитель на знаменатель, будем иметь
. (10)
Взяв обратное преобразование Лапласа, предварительно разложив правую часть (10) на простейшие рациональные дроби, получим
.
Учитывая, что
,
находим искомое решение
, 
, 
. (11)
Таким образом
Погрешность приближенного решения (6) для 
находится по формуле
.
Заметим, что является распределением Эрланга порядка i, для которого
, 
,
где x - полное время нахождения последней обслуженной задачи набора в ВС.
Заключение. Таким образом, предложенный подход позволяет существенно повысить качество анализа функционирования большемасштабных распределенных вычислительных систем.
Список литературы
1. , Однородные вычислительные системы. Новосибирск: Наука, 1978.
2. Архитектура вычислительных систем. М.: МГТУ им. Баумана, 2005, 512с.
3. , , Вычисление показателей живучести распределенных вычислительных систем и осуществимости решения задач // Искусственный интеллект. 2006. №4. С. 28–34.
4. Введение в теорию вероятностей и ее приложений. Т.1: - М. Мир. 1984гс.
*) Работа выполнена при поддержке РФФИ (гранты №, №,) и Совета по грантам Президента РФ (грант №НШ-2121.2008.9)
