Estimation of realizability parameters of solving problems ondistributed computer systems .pdf При анализе эффективности функционирования вычислительных систем (ВС), как сосредоточенных, так и распределенных, используются показатели осуществимости [1, 2]. В зависимости от сложности задач и характера их поступления выделяют следующие режимы работы ВС: решение сложной задачи; обработка набора задач; обслуживание потока задач.В работе предлагается подход к нахождению математических ожиданий и дисперсий, используемых в расчетах показателей осуществимости решения задач потока и набора.2. Расчет показателей осуществимости решения задач на ВСРассмотрим абсолютно надежную распределенную ВС, состоящую из потенциально неограниченного числа элементарных машин (ЭМ) [2], на которую поступает поток простых задач интенсивностью а и интенсивностью ß решения. (Простая задача представляется последовательной программой [2].)Предполагается, что потоки поступлений и решения задач пуассоновские с параметрами а и ß соответственно.Требуется вычислить математическое ожидание Alf) числа задач, находящихся в системе [2], и соответствующую дисперсию Д{?) в момент времени ?е[0, да) при начальных условияхA (0) = i, Di (0) ss 0, i e E0°° = {0,1,2,...} .(1)Пусть Pk(t) - вероятность того, что в момент времени te [0, да) в ВС k задач находится на обслуживании, k е £0°. Тогда система дифференциальных уравнений, в системе массового обслуживания M/M/да [4] имеет вид4Pk (t) = -(^k + Иk) (t) + Ьk-1 Pk-1 (t) + Иk+1 Pk+1 (t) ,(2) dt^k ^ 0 , Hk > 0 , Ио = 0 , k е £0°. Pr(t) = 0, r ё Elf .Случай 1. Пусть ВС - высокопроизводительная, следовательно, можно считать, что каждая задача, поступившая в систему, сразу начинает обслуживаться. Полагая в системе (2)^k = а, Ик = k ß, получаем систему уравнений [3, 4]dP^(t) = -(а + kß) Pk(t) + Pk-1 (t) + (k + 1)-ß-Pk+1 (t) .(3) dtВведем производящую функциюF(z, t) = X zk ■ Pk (t) .(4)k=0Система (3) сводится к следующему уравнению в частных производных:^ + ß'(z-1)^ = a(z-1)F(z,t) .(5) dt dzПри начальных условиях (с учетом (1))f(z,0) = z;.Из (4) имеемA(t) = -°F(1,t), Dt(t) =^F(1,t) + AF(1,t)-(AF(1,t)Y .(6)oz 5z2 dz \dz )Преобразование уравнения (5), с учетом (6), приводит к системе обыкновенных дифференциальных уравнений [3]:^-4 (t) + ß- Ai (t) = a, , dt (7)- [Di (t) + Ai2 (t) - A (t)] + 2ß [Di (t) + Ai2 (t) - A (t)] = 2a A (t)с начальными условиями (1).Решение системы (7) записывается в видеA (t) = a (1 _ e-ßt) + i. e-ßt,/\ (8) D (t) = (1 _ e-ßt) [в + i. e-ßt j.Характер вхождения вычислительной системы в стационарный режим работы при обслуживании потока задач иллюстрируют рис. 1 и 2.На рис. 1 приведены графики функций Aj(f) (тонкие линии) и Aj(f) + cr(t) (жирные линии) для а = 10 ч-1, ß = 0,1 ч-1, i = 0, 50, 90; c(t) = ^jD; (t). Стационарный режим функционирования ВС достигается практически через t = 40 ч; учет дисперсии существенен, так как max cr(t) = 10.Для практических расчетов можно пользоваться формулами A ±4Ъ = lim [Д. (t) ±у/ D (t)] = а / ß±Va~7ß.В ситуации, представленной на рис. 1, имеем A ±\f~D = 100 ± 10. На рис. 2 при а = 10 ч-1, ß = 0,2 ч-1 и различных начальных условиях стационарный режим функционирования ВС достигается через t 35 ч, max c(t) = 10.Ai(t)60Рис. 2Случай 2. Изучим функционирование ВС невысокой производительности в режиме обработки пакета, состоящего из i простых задач. Выделенный ресурс составляет i ЭМ. В этом случае, полагая а = 0, получаем вместо уравнения (5) следующее:5^ + p.(z-1).afW) = о , F(z,0) = i .(9) dt dzИз (9), с учетом (6), после необходимых преобразований получим системуГ d_-4 (t) + ß-A- (t) = 0,d_l dtРешение системы (10) при начальных условиях (1) имеет видA(t) = i exp(-ß t), D(t) = i exp(-ßt)[1 - exp(-ßt)]. (11) Вычислим, например, время, через которое от начального набора i задач в ВС останется их половина. Из (11) имеемi/2 = i exp(-ß t), тогда t = ln 2/ß, дисперсия D;(t) = i/4, a = 4i /2.На рис. 3 представлена зависимость числа решенных простых задач от времени t, если начальный набор состоял из i=10 задач, выделенный ресурс состоит из 10 ЭМ, ß = 1 ч-1. Время, необходимое для решения половины задач, находящихся в системе, t = ln 2 0,69 ч, c 1,6. Следовательно, за 42 мин будет решено от 3,4 до 6,6 задач из 10, при суммарной интенсивности решения iß = 10 ч-1.Случай 3. Рассмотрим решение набора i (>0) сложных задач на ВС. Сложная задача (представлена параллельной программой [2]) решается на всем выделенном ресурсе.Пусть выделенный ресурс составляет n ЭМ, тогда интенсивность решения задачи будем считать равной n -ß , где ß - интенсивность решения задачи на одной ЭМ (оцениваются потенциальные возможности ВС [1, 2]).Так как задачи сложные, то они решаются последовательно. Обозначим через Pk (t) вероятность того, что к моменту времени t в ВС находится k задач (включая обслуженную), k е E0.В такой постановке система (2) записывается в виде\Рк '(t) = -n -ß-Pk(t) + n-ß-Pk+1 (t), k e El-1, (12) [P0 '(t) = n-ß-Pi(t); P '(t) = -n-ß-p(t),с начальными условиямиP (0) = 1, Pk (0) = 0 , k * i. Условие нормировки, являющееся следствием системы уравнений, имеет вид£ Pk {t) = 1, t е [0, да).k=0Вводя производящую функциюF(z, t) = £ zk Pk (t),k=0систему (12) приводим к уравнениюz.^iM = „.ß.(1 -z) (F(z,t)-P0(t)), F(z,0) = Z ,(13) из которого, после необходимых преобразований, получаем, с учетом (6), системуf jL1 - (14)I dt1с начальными условиями (1).Для нахождения P0 (г) вернемся к системе (12). Приведем точное решение.Применяя преобразование Лапласа (f (s) = je~s'' ■ f (t)dt, где f (t) - функция ог-0раниченного изменения [3]) к уравнению (13), получимz (s F(z,s)-z;) = n-ß.(1 -z) (F(z,s)-P0(s)), Re(s) > 0 ,(15)или F(z,s) =£!+^Ì^ад .(166s ■ z - n ß (1 - z)Так как нуль в знаменателе существует внутри круга | z |= \п ■ ß /(s + n ■ ß)| < 1, то с необходимостью в числителе имеемPo(s) = s-1 -[и-ß/(s + n■№ .(17)Подставляя правую часть формулы (17) в (16) и разделив полученный числитель на знаменатель, будем иметьF(z, s) = s-1 [n ß /(s + n ß)]' + X z'-k [n ß /(s + n ß)]k .(18)k=0Взяв обратное преобразование Лапласа, предварительно разложив правую часть (18) на простейшие рациональные дроби, получимF(z,t) = 1 -exp(-n ß-t) £ (n ß tУ-k /(i-k)!+ exp(-n ß-t) §J zi-i (n ß t)k /k!i=l k=0Учитывая, чтоn)=f (o, > >,находим искомое решениеPo(t) = 1 -exp(-n-ß-t)-1 ,Pk(t) = (Я'ß'!■ exp(-n-ß-t), k e E1 .(199(i - k)!Таким образом, решение системы (14) имеет вид' (П ß-t)'"kA(t) = exp(-n-ß-t)-1 k-(П ß j\ ,Di(t) = exp(-n-ß-t)- £ k2 -(n-ß-t{* -(Ai(t))2.k=i (i - k)!(20)Обратимся к системе (14). Если число i задач велико, то можно считать, что i - да, тогда P0 (t) - 0 , V? е [0, да). При P0 (t) = 0 система (14) имеет очевидное решениеU {t) = i-пß-1, (21) {Di(t) = n-ß-1, t < i/n-ß, ()в котором n ß -1, при i - да, есть параметр случайного процесса Пуассона. Погрешность приближенного решения (21) для Д (t) находится по формулеAi(t) = exp(-n-ß.t) I (i-k)( ß. ) .k=i+i k!Формула (21) может быть использована при экспресс-анализе функционирования ВС.Из (21) следует, что среднее время, необходимое для решения i сложных задачнабора, tcp = i / (n ß) при стандартном отклонении a = 4i . Например, при выделенном ресурсе n = 100 ЭМ время, необходимое для решения набора из 400 задач при ß = 0,1 ч-1, составит tcp = 400 / (100 0,1) = 40 ч. С учетом отклонения, о = у!400 = 20 ч, для среднего времени решения набора задач имеем оценку: L, = 40 ± 20 ч.Учитывая, что P0 (t) является распределением Эрланга порядка i [4], для которогоM £ = i /(n -ß), D^ = i /(n -ß)2- полное время нахождения последней обслуженной задачи набора в ВС), получаем более точную оценку 7 = 40 ± 2 ч.3. Условие осуществимости решения сложной задачи на живучей ВСПри построении моделей функционирования ВС, в которых число элементарных машин было невелико и решаемые задачи простые, влияние надежности на организацию процесса решения задач (в целях упрощения математических моделей) можно было считать несущественным [4].Для большемасштабных ВС такие упрощения привели бы к ошибкам принципиального характера. В связи со сказанным, вывод условия, позволяющего оценить осуществимость решения сложных задач на большемасштабных ВС с учетом их надежности, практически необходим. В самом деле, выход из строя ЭМ приводит к реконфигурации ВС тем чаще, чем больше число N ЭМ в системе; кроме того, с увеличением N время реконфигурации ВС увеличивается.Обозначим через X интенсивность отказов одной ЭМ, а через р - интенсивность восстановлений отказавшей ЭМ одним восстанавливающим устройством.Рассмотрим вычислительные системы со структурной избыточностью [2, 3]. Они представляют программно настроенную конфигурацию [2], в которой:а) выделена основная подсистема из n ЭМ и подсистема из (N - n) ЭМ, подчиненная основной и составляющая структурную избыточность;б) основная подсистема предназначена для решения сложных задач, представленных параллельными программами из n ветвей, а подчиненная система - для решения фоновых задач;в) функции отказавшей ЭМ основной подсистемы берет на себя любая исправная ЭМ структурной избыточности.Под восстановлением будем понимать комплекс мер, связанных с бесперебойной работой ВС (контроль, (само)диагностика, реконфигурация, избыточность и др. [2]). Время, необходимое для реализации этих мер, учтено в параметре р.Если восстанавливающая система является высокопроизводительной, то условие осуществимости решения задач на ВС можно записать в виде(N - n)p / (n-X) > 1. (22)Физический смысл неравенства состоит в том, что суммарное время восстановления всегда должно быть больше, чем суммарное время отказов ЭМ.Если задача сложная (т.е. решается на всех элементарных машинах), n -да , и реконфигурация ВС происходит со всеми оставшимися работоспособными ЭМ, то неравенство (11), в конце концов, нарушается (то есть система перестает самовосстанавливаться). Для его выполнения необходимо, чтобы реконфигурация осуществлялась на ограниченной подсистеме (объем которой сводил бы к минимуму межмашинные взаимодействия). Один из таких вариантов реконфигурации обеспечивает крупноблочное распараллеливание сложных задач [2].Условие осуществимости (22) в большей мере имеет методологическое значение, хотя оно может использоваться и для практических оценок.В самом деле, пусть сложная задача решается на ВС со структурной избыточностью. Поскольку условие (22) получено из вероятностной модели, то его выполнение зависит от вида случайного процесса, которому принадлежат параметры модели; в рассматриваемом случае процесс описывается схемой Бернулли (соответствующие формулы в переходном режиме получены в [3]).Из (22) имеем(N - n) > NX / (X + р).Пусть N - n - случайная величина, характеризующая число ЭМ структурнойизбыточности. Зададим Х = 10-4 ч-1, р = 10 ч-1, а) N = 104, б) N = 105, в) N = 106, тогда решение осуществимо с вероятностьюа) P{0 < N - n < 1} = (р (Х + р)N + N -Х- рN-1 /(Х + р)N) * 0.99 ;б) P{0 < N - n < 5} * 0.98 ;в) P{0 0.99 .Для нахождения x, числа ЭМ структурной избыточности (при x > 10), для оценки можно воспользоваться интегральной теоремой Муавра - Лапласа [4]. Зададим доверительную вероятность у = 0.99, тогда P{0 < N - n < x} = у . Используя указанную теорему, имеемФ ((x - N ■ р)1у}N ■ p ■ (1 - p)) - Ф ((0 - N ■ р)ЦN ■ p ■ (1 - р)) ~ 0.9935 ,(23)где p = Х /(Х + р), Ф(у) - нормированная нормальная функция распределения. Решая трансцендентное уравнение (23), находим x = 18 .Следовательно, число ЭМ структурной избыточности определяется практическими соображениями и подтверждается вероятностями, значения которых должны быть близкими к единице. Обратно, если задать вероятность (назовем ее доверительной), то можно оценить число ЭМ структурной избыточности.Замечание. Условие осуществимости основано на модели, описывающей состояния системы в текущий момент времени, что может вызвать сомнения в правомерности ее использования, поскольку модель не учитывает продолжительности решения задачи. Мы считаем, что было бы неразумным отвергать этот подход, так как с вероятностью сколь угодно близкой к единице он дает простой алгоритм поддержки необходимой производительности ВС в любой момент времени, что и определяет осуществимость решения задачи.ЗаключениеПоказано, что полученные аналитические формулы можно использовать при анализе эффективности функционирования ВС. Предложенный подход позволяет с единых методологических позиций вычислять моменты (центральные и начальные) не менее второго порядка, не вычисляя вероятности состояний системы, что особенно важно для анализа функционирования многомашинных ВС.

Скачать электронную версию публикации