Direct and inverse algorithms of stochastic network calculation

详细

The paper presents direct and inverse algorithms of modified GERT-network calculation used for analysis of probabilistic-time characteristics of stochastic networks.

全文:

Один из подходов к организации процесса интенсивной обработки информации - это использование в качестве узлов обработки информации компьютеров пользователей в свободное от использования времени. Такие проекты, как SETI, Climate Predictions, Legion или Condor, получают все большее распространение и весьма эффективны для некоторых задач [1; 2]. В случае когда для некоторого узла известна вероятность бесперебойной работы в течение времени, необходимого для расчета задачи, то рассчитать функцию распределения времени выполнения задачи можно, используя ГЕРТ-сети [3]. В процессе исследования стала очевидной возможность модификации математической модели ГЕРТ-сетей. Полученная модифицированная модель позволяет оценить время одновременного выполнения задачи на нескольких узлах (рабочих станциях) гетерогенной распределенной системы обработки информации. Математическая модель модифицированных ГЕРТ-сетей. Для того чтобы дать определение математической модели модифицированной ГЕРТ-сети, введем следующие обозначения [4] : pi - вероятность активации узла i; pij - функция условной вероятности активации узла j, при условии активации узла i, pj = 1, если узел і имеет детерминированный выход или <i, j> - единственная дуга стохастического выхода; pjn - вероятность выполнения начала дуги <i, j> при условии, что узел, из которого она входит, активирован; pÿK - вероятность выполнения конца дуги <i, j> при условии, что узел, в который она входит, активирован; Fi(t) - функция распределения времени выполнения узла i в момент его активации; Fij(t) - функция условной вероятности распределения времени выполнения работы <i, j>; Fij„(t) - функция распределения времени выполнения tі в начале дуги <i, j> при условии, что узел, из которого она входит, активирован; FjK(t) - функция распределения времени выполнения tj на конце дуги <i, j> при условии, что узел, в который она входит, активирован. Также для модифицированных ГЕРТ-сетей (МГ-сетей) справедливы следующие ограничения [4; 5]: Ограничение 1’ (О1’): в течение каждого выполнения проекта для каждого стока активируется не более одного источника, из которого данный сток достижим. Ограничение 2’ (О2’): для каждого узла і МГ-сети, если узел i активирован, то параметры всех выходящих из него дуг вычислимы. Ограничение 3’ (О3’): для каждого узла k произвольной циклической структуры C существует путь из k к узлу вне C такой, что pj > 0 для каждой дуги <i, j> данного пути. Иными словами, есть из каждого цикла есть выход с положительной вероятностью. Ограничение 4’ (О4’): для всякого узла і ГЕРТ-сети G, имеющего IOR- или AND-вход, для любых j, k є P(i), Pr(i, j, k) = {!}, причем l - единственный узел и l имеет детерминированный выход. Ограничение 5’ (О5’): для всякого узла і ГЕРТ-сети G, имеющего детерминированный вход, для любых j, k є S(i), Sc(i, j, k) = {!}, причем l - единственный узел и l имеет AND- или IOR-вход. Ограничение 6’ (О6’): реализация сети является допустимой, если в процессе выполнения узел i активируется с вероятностью, большей maxP, > 0 и не более, чем max^ > 1 раз; узел і имеет EOR-вход, если в узел i циклической структуры C входит более одной дуги и хотя бы одна дуга не принадлежит циклу C; узел i имеет стохастический выход, если из узла i циклической структуры C выходит более одной дуги и хотя бы одна дуга не принадлежит циклу C; узел j с детерминированной выходной функцией, являющийся стохастическим началом узла i, принадлежит циклу, если узел і с IOR- или AND-входом принадлежит данному циклу. Будем называть ГЕРТ-сеть G (V - множество вершин, E - множество направленных ребер) МГ-сетью, если: 1) G имеет единственный источник и, по крайней мере, один сток; 2) сеть G удовлетворяет ограничениям О1’-О4’; 3) задано множество параметров для каждого узла сети (по крайней мере, вероятность активации); 4) для каждой дуги указаны функции преобразования параметров узлов; 5) источник активируется в момент времени 0 (если параметр, отвечающий за время, определен). Математическая модель модифицированных ГЕРТ-сетей изначально создавалась таким образом, чтобы всякая МГ-сеть, удовлетворяющая О1’-О4’ и для которой заданы дополнительные ограничения О6’, была бы выгчислима при помощи некоторого алгоритма. По своей сути О1’-О4’ гарантируют однозначность построения и расчета графа реализации, а О6’ - конечность количества этих реализаций. Рассмотрим МГ-сеть с вектором веса дуг [p, Fj] [6], тогда ptjK и FÿK (t) для дуги <i, j> имеют вид pyK = pvn - py ; +ад FÿK (t) = j Fÿn (s) - Fÿ '(t - s)ds = Fÿн © Fj. (1) -ад Если считать, что случайная величина t > 0, то пределы интегрирования можно заменить на 0 и t соответственно. Для EOR-входа pj и Fj (t ) имеют вид pj = pj.; fj (t ) = Fw(t ). (2) 92 Математика, механика, информатика где j - вычисляемый EOR-вход, имеющий начало в узле i. Для AND-входа pj и Fj (t) имеют вид pj = pl1,m^ ■ pl2,m2к X ... X pIn,mNк / pi ; Fj (t) = max(tl1,m1к , tl2,m2к , ..., tlN,m^ ) = = Fl1,m1к (t) ■ Fl2,m2к (t) X ... X FN,mNк (t), (3) где j - вычисляемый AND-вход, имеющий стохастическое начало в узле i; {l1 - m1}, {l2 - m2}, ..., {lN - mN} - N непересекающихся подсетей. Для IOR-входа pj и Fj (t ) имеют вид p,j = pi ■ [1 - (1 - pu,m^ )(1 - pi2,m2к ) X ... X (1 - pN,mNк ) ]; Fj (t) = min(tl1,m1к , tl2,m2к , ..., ^,mNк ) = = 1 - (1 - Fl1,m1к (t))(1 - Ъ2м2к (t)) X ... X (1 - FlN mNK (t)), (4) где j - вычисляемый IOR-вход, имеющий стохастическое начало в узле i. Формулы (1)-(4) позволяют рассчитать любой граф реализации, удовлетворяющий ограничениям О1’-О4’. Результатом расчета сети будет множество реализаций Wr, сгруппированное по стокам ir. Для стока в каждой реализации будет рассчитана вероятность наступления события (вероятность возникновения реализации), функция распределения времени выполнения данной реализации и т. д. Пусть r - элемент множества реализаций со стоком i. Вероятность активации стока i: Р = S pr. (5) r Вероятность активации стока i ко времени t в реализации r: P,r (t) = pr ■ Ff (t). (6) Вероятность активации стока i ко времени t: P (t) = £ pr ■ Ff (t). (7) r Математическое ожидание времени активации стока i: £[pr ■ J t ■ dFf (t)] E (ti ) =- S pr (8) Математическое ожидание времени выполнения всей сети: E (t ) = ££[ pr ■ J t ■ dFf (t )] i r_-ад_ Sp . (9) Дисперсия времени активации стока i: S[ pr ■ ( J (t - E (ti ))2 ■ dFf (t ))] D(ti ) = ---” r-. (10) S pr Дисперсия времени выполнения всей сети: ад SS[ pr ■ ( J (t - E (ti ))2 ■ dFf (t ))] D(t) = ~^r--. (11) S pir i Принятые обозначения, используемые для записи алгоритмов. Для записи узлов, дуг и относящихся к ним величин и функций используем обозначения, принятые для структур вида «[структу-ра].[параметр]». Пусть Prs и DFs - множества вещественных и стохастических параметров соответственно. Каждый узел графа реализации будет обладать данными параметрами. Параметр p (вероятность активации узла) является одним из элементов множества Prs (p є Prs). Для узла v є V графа МГ-сети G = <E, V>: v.a - количество активаций узла v в процессе построения реализации; v.In - тип входной функции узла (EOR, IOR или AND); v.Out - тип выходной функции узла (STOCH или DET); v.InF(F) - тип входной функции узла для стохастических переменных с функцией распределения F (AND, IOR, MIN, MAX, EQUAL) (только для узлов с IOR- или AND-входом); v.P - множество узлов, являющихся предками узла v; v.S - множество узлов, являющихся потомками узла v; v.MaxA - максимально допустимое количество активаций узла v в графе реализации; v.MaxP - минимально допустимая вероятность события «узел v активирован»; v.dR - узел, являющийся детерминированным источником узла v; v.dS - узел, являющийся детерминированным стоком узла v (только для прямого алгоритма расчета МГ-сети). Для дуги e є E графа МГ-сети G = <E, V> (e = <vb v2>): e.v1 - узел-начало дуги; e.v2 - узел-конец дуги; e.F Pr(Pr) - функция преобразования параметра Prі є Prs, зависящая от параметров Prs и DFs; e.F_DF(Fi) и e.F DF op(F) - функция распределения для стохастической переменной, заданной функцией распределения F, и операция для нее («+», «-» или «=») соответственно. Для графа реализации w: W = {w,} - множество графов реализации; w.H - начальный узел графа реализации w; w.T - конечный узел графа реализации w: x - узел графа реализации, где x є w; x.v - узел МГ-сети, которому соответствует узел графа реализации (x.v є V); x.Prs - значения вещественных параметров узла графа реализации; x.DFs - значения стохастических параметров узла графа реализации; r r r 93 Вестник СибГАУ. № 1(47). 2013 w = {x} - граф реализации, состоящий из единственного узла x. Тогда w.H = w.T = x. Введем операции построения графа реализации: w = M(w1, w2) - новый граф реализации сети, являющийся объединением графов w1 и w2 дугой из w2.H в w1.T. Частным случаем данной операции будем считать M(x, w) = M({x}, w) и M(w, x) = M(w, {x}). w = M(w1, W, w2) - новый граф реализации сети, являющийся объединением дугами конечного узла w1.T со всеми начальными узлами w,.H (wг є W) и объединением дугами конечных узлов wi.T с начальным узлом w2.H. Обратный алгоритм расчета модифицированных ГЕРТ-сетей. Общая идея обратного алгоритма расчета МГ-сети [7]: - обход графа МГ-сети ведется от выбранного стока к источнику; - обход ведется с помощью рекурсивного алгоритма; - для каждого узла, имеющего EOR-вход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг входит в данный узел; - для каждого узла і, имеющего IOR- или AND-вход, запускается рекурсивный вызов процедуры расчета узла j, являющегося детерминированным источником узла i, затем рассчитываются все пути от j к i и, используя найденные пути, строятся все реализации, завершаемые узлом i; - расчет вещественных и стохастических переменных производится при «выходе» алгоритма из рекурсии; - результатом работы главной процедуры «ОРас-читатьСеть» являются множества реализаций для каждого из стоков. Процедура «ОРассчитатьСеть» для обратного алгоритма расчета модифицированной ГЕРТ-сети Шаг 1. Для каждой вершины vi из множества вершин V задать число активаций v.a равное 0 и объявить пустое множество возможных реализаций ( W = {}). Шаг 2. Для каждого стока vsi из множества стоков S выполнить процедуру «ОПостроитьРеализацию». Шаг 3. Объединить полученные реализации Wi в результате шага 2 в результирующее множество W. Шаг 4. Конец процедуры. Процедура «ОПостроитьРеализацию» для обратного алгоритма расчета МГ-сети Шаг 1. Если число активаций текущего узла больше максимально допустимого количества активаций vc.a > vc.MaxA, то перейти к шагу 18, иначе -шаг 2. Шаг 2. Если текущий узел vc указывает на узел источника подсети vs, то перейти к шагу 3, иначе -шаг 4. Шаг 3. К множеству реализаций W добавим узел графа реализации x, для которого: x.v = vs, x.Prs = vs.Prs, x.DFs = vs.DFs. Перейти к шагу 18. Шаг 4. Увеличить vc.a на 1. Шаг 5. Если типом входной функции текущего узла vc.In является входная функция типа EOR, то перейти к шагу 6, иначе - шаг 12. Шаг 6. Для множества узлов, являющихся предками текущего узла vс, выполнить процедуру «ОПо-строитьРеализацию». Шаг 7. Объединить полученные в результате шага 6 множества графов реализаций Wtг во множество W1. Шаг 8. Для каждого узла графа реализации W1 x.v = vs. Шаг 9. Для пар узел графа реализации W1 x и vs выполнить процедуру «Рассчитать дугу». Шаг 10. Попарно объединить графы реализаций W1 c M(wt, x) во множество W2, где і от 1 до |W1|, перейти к шагу 17. Шаг 11. Для детерминированного источника текущего узла vc.dR выполнить процедуру «ОПостро-итьРеализацию». Шаг 12. Для каждого узла xsг графа реализации Ws, полученного в результате выполнения шага 11, выполнить процедуру «ОПостроитьРеализацию». Шаг 13. Для каждого графа реализации w2i из множества графов реализаций Ws2, полученных в результате выполнения шага 12, удалить первый узел. Шаг 14. Для всех возможных пар узлов из Ws2 выполнить процедуру «Рассчитать дугу». Шаг 15. Для каждого узла x множества графов реализаций Ws2: x.v = vc - определить параметры узла графа реализации x.Prs и x.DFs по множеству {ws2,}, используя формулы (1)-(4), (8), (10). Шаг 16. Попарно объединить графы реализаций Ws2 c M(ws2i, xs2i) во множество W2, где і от 1 до |Ws2|. Шаг 17. Уменьшить vc.a на 1. Шаг 18. Конец процедуры. Процедура «Рассчитать дугу» расчета МГ-сети Шаг 1. e = <v1, v2>, Prs2(p) = Prs1(p) * e.F Pr(p), где v1, v2 - узлы, являющиеся началом и концом дуги; Prs 1, Prs2 - множества вещественных параметров начала и конца дуги соответственно; DFs 1, DFs2 -множества стохастических параметров начала и конца дуги соответственно. Шаг 2. Для каждого Prг из Prs 1, при Prг ^ p выполнить: Prs2(Pr) = e.F_Pr(Pr)(Prs1, DFs1). Шаг 3. Для каждого Fг из DFs1 рассчитать DFs2(F) по формулам (1)-(11), используя значения Prs 1, DFs1, e.F_DF(F), e.F DF op(F). Шаг 4. Конец процедуры. Прямой алгоритм расчета модифицированных ГЕРТ-сетей. Общая идея прямого алгоритма расчета МГ-сети: - обход графа МГ-сети ведется от источника к стокам; - обход ведется с помощью рекурсивного алгоритма; - для каждого узла, имеющего стохастический выход, запускается столько же рекурсивных вызовов процедур (ветвей обхода), сколько дуг выходит из данного узла; - для каждого узла i, имеющего детерминированный выход, рассчитываются все пути от i к j, и, используя найденные пути, строятся все реализации, 94 Математика, механика, информатика завершаемые узлом j, где j - детерминированный сток узла i; - расчет вещественных и стохастических переменных производится при «углублении» алгоритма рекурсии; - результатом работы главной процедуры «ПРас-читатьСеть» являяются множества реализаций. Следует отметить, что для использования прямого алгоритма расчета МГ-сети необходимо выполнение ограничения О5’. Процедура «ПРассчитатьСеть» для прямого алгоритма расчета модифицированной ГЕРТ-сети Шаг 1. Для каждой вершины vi из множества вершин V задать число активаций v.a, равное 0, и объявить множество возможных реализаций Wt = {x}, где x.v = vr, x.Prs = iPrs, x.DFs = iDfs (vr - узел-источник МГ-сети; iPrs и iDfs - начальные значения параметров в узле-источнике). Шаг 2. Для каждого стока vsг из множества стоков S, используя множество реализаций Wt, выполнить процедуру «ППостроитьРеализацию». Шаг 3. Объединить полученные реализации Wti в результате шага 2 в результирующее множество W. Шаг 4. Конец процедуры. Процедура «ППостроитьРеализацию» для прямого алгоритма расчета МГ-сети Шаг 1. Если Wc (множество реализаций, построенное от источника до узла vc) пустое множеств, то перейти к шагу 23, иначе - шаг 2. Шаг 2. Если число активаций текущего узла больше максимально допустимого количества активаций vc.a > vc.MaxA, то перейти к шагу 3, иначе -шаг 4. Шаг 3. Wc = {}, перейти к шагу 23. Шаг 4. Если vc указывает на узел источник подсети vs, то перейти к шагу 5, иначе - шаг 6. Шаг 5. Объединить результирующее множество реализаций сети W с множеством Ws, Ws = {}, перейти к шагу 23. Шаг 6. Увеличить vc.a на 1. Шаг 7. Если тип выходной функции текущего узла - стохастическая функция (vc.Out = Stoch), то перейти к шагу 8, иначе - шаг 13. Шаг 8. Объявить пустые множества реализаций Wt и Wt1. Шаг 9. Для пар текущий узел (vc) и сток текущего узла (v, из vc.S) выполнить процедуру «Рассчитать дугу». Шаг 10. Объединить множества M(wk, x) в Wt, где wk - графы реализации из множества Wc и x - стоки текущего узла (x.v = v, из vc.S) Шаг 11. Для каждого стока текущего узла (v, из vc.S), используя множество реализаций Wt, полученное на предыдущем шаге, выполнить процедуру «ППостроитьРеализацию». Шаг 12. Объединить полученные множества реализаций Wt1 в результате шага 11 с результирующим множеством W, перейти к шагу 22. Шаг 13. Объявить пустое множество реализаций Wt2. Шаг 14. Для пар текущий узел (vc) и сток текущего узла (v, из vc.S) выполнить процедуру «Рассчитать дугу». Шаг 15. Объявить множество реализаций Wt = {x}, где x - стоки текущего узла (x.v = v, из vc.S). Шаг 16. Для каждого стока текущего узла (v, из vc.S), используя множество реализаций Wt, полученное на предыдущем шаге, выполнить процедуру «ППостроитьРеализацию». Шаг 17. Для каждого графа реализации w2, из множества графов реализации W2, полученных в результате выполнения шага 16, удалить последний узел. Шаг 18. Для всех возможных пар узлов из W2 выполнить процедуру «Рассчитать дугу». Шаг 19. Для узла vс.dS, являющегося детерминированным стоком текущего узла vс, определить параметры узла графа реализации x.Prs и x.DFs по множеству графов {w2,}, используя формулы (1)-(4), (8), (10). Шаг 20. Объединить множества M(wk, {w2,}, x) в Wt2, где wk - графы реализации из множества Wc, w2г графы реализаций из множества W2 и x - стоки текущего узла (x.v = v, из vc.S). Шаг 21. Для узла vс.dS, являющегося детерминированным стоком текущего узла vс, используя множество реализаций Wt2, полученное на предыщущем шаге, выполнить процедуру «ППостроитьРеализацию». Шаг 22. Уменьшить vc.a на 1. Шаг 23. Конец процедуры. Сравнение производительности прямого и обратного алгоритмов расчета модифицированной ГЕРТ-сети. Приведем качественное сравнение производительности прямого и обратного алгоритмов расчета стохастической сети. Выполнить количественную оценку производительности алгоритмов для произвольной сети не представляется возможным. Время работы программ, использующих прямой и обратный алгоритмы обхода МГ-сети, в основном формируется из времени выполнения трех операций: обхода графа сети, дублирования множества реализаций и расчета параметров узлов графа реализаций. Время выполнения алгоритма обхода графа МГ-сети примерно одинаково для прямого и обратного алгоритмов. В ходе практических испытаний над различными сетями произвольного вида выявлено, что алгоритм на базе прямого обхода графа всегда не медленнее по производительности алгоритма на базе обратного обхода графа. Однако, как уже отмечалось выше, область его применения уже (требует выполнения О5’). Один из способов повышения точности расчетов интегральной свертки при анализе вероятностновременных характеристик стохастических сетей заключается в том, чтобы дать возможность использовать аналитически заданные функции распределения в качестве стохастических параметров (весов) дуг сети. Предложенный способ представления функций распределения стохастических параметров при анали 95 Вестник СибГАУ. № 1(47). 2013 зе вероятностно-временных характеристик стохастических сетей и численные методы расчета параметров дуг позволяют создать универсальный программный модуль расчета произвольной стохастической сети. Прямой алгоритм расчета стохастической сети занимает время выполнения меньшее или равное времени выполнения обратного алгоритма. Однако прямой алгоритм может быть использован только при выполнении ограничения О5’. Проверка выполнения данного ограничения может выполняться как исследователем, так и программным путем. Прямой алгоритм дает выигрыш в быстродействии, если сеть имеет хотя бы один цикл.