Текст задания
Требуется разработать стохастические сети Петри, моделирующие выполнение программы, рассматривавшейся в лабораторных работах №1-3, в последовательном и параллельном вариантах.
Сравнить результаты анализа, полученные для последовательного и параллельного вариантов между собой, а также с результатами, полученными в лабораторных работах 2 и 3.
Посторенние ССП для последовательного случая.
Для построения ССП необходимо:
- построить ПМЦ с ДВ
- преобразовать ее к ЭМЦ с НВ
- преобразовать полученную ЭМЦ в ССП
Граф с нагруженными дугами был построен и нагружен вероятностями ветвлений и временами выполнения в ходе первой лабораторной работы. Используем полученный результат в качестве исходного:
ПМЦ с ДВ
Описание модели в XML
name = "t0-->t2" probability = "1.0" intensity = "1.62" deviation = "0.0"
name = "t2-->t4" probability = "1.0" intensity = "0.25" deviation = "0.0"
name = "t5-->t4" probability = "0.5073891625616" intensity = "0.48" deviation = "0.0"
name = "t5-->t3" probability = "0.4926108374384" intensity = "0.49" deviation = "0.0"
name = "t4-->t6" probability = "1.0" intensity = "0.64" deviation = "0.0"
name = "t7-->t5" probability = "1.0" intensity = "0.38" deviation = "0.0"
name = "t6-->t8" probability = "1.0" intensity = "0.27" deviation = "0.0"
name = "t8-->t9" probability = "0.9892244811296" intensity = "0.31" deviation = "0.0"
name = "t9-->t10" probability = "1.0" intensity = "0.55" deviation = "0.0"
name = "t10-->t8" probability = "1.0" intensity = "0.29" deviation = "0.0"
name = "t8-->t7" probability = "0.01077551887043" intensity = "0.28" deviation = "0.0"
Часто для первоначального описания модели Программы потребление ресурсов даже для модели с НВ удобнее задавать в традиционной форме в виде вероятности {pij и mij}. Затем требуется этап преобразования ПМЦДВ в ЭМЦНВ, т.е. от {pij и mij} к {ij} – переход не всегда является простым.
Примеры преобразования для типовых процессов:
-
Л инейный процесс
-
В етвление
i' i'' = 1 / m1i
1i' = p1i'*гран
1j' = p1j'*гран
(гран>>{1/m1i ; 1/m1j})
ЭМЦ с НВ
name = "p0-->p2" intensity = "0.6173" source = "p0" dest = "p2"
name = "p2-->p4" intensity = "4" source = "p2" dest = "p4"
name = "p4-->p6" intensity = "1.5625" source = "p4" dest = "p6"
name = "p7-->p5" intensity = "2.6316" source = "p7" dest = "p5"
name = "p6-->p8" intensity = "3.7037" source = "p6" dest = "p8"
name = "p9-->p10" intensity = "1.8182" source = "p9" dest = "p10"
name = "p8-->p09" intensity = "9892.24" source = "p8" dest = "p09"
name = "p09-->p9" intensity = "3.2258" source = "p09" dest = "p9"
name = "p8-->p07" intensity = "107.76" source = "p8" dest = "p07"
name = "p07-->p7" intensity = "3.5714" source = "p07" dest = "p7"
name = "p10-->p8" intensity = "3.4483" source = "p10" dest = "p8"
name = "p5-->p03" intensity = "4926.11" source = "p5" dest = "p03"
name = "p5-->p04" intensity = "5073.89" source = "p5" dest = "p04"
name = "p04-->p4" intensity = "2.0833" source = "p04" dest = "p4"
name = "p03-->p3" intensity = "2.0408" source = "p03" dest = "p3"
name = "p3-->p0" intensity = "10000.0" source = "p3" dest = "p0"
Теперь на основе ЭМЦ построим ССП. Они будут изоморфны, поскольку цепь ССП описывает последовательный случай, маркер только один и в сети нет операций fork, а значит, каждая доступная маркировка будет включать только один маркер.
ССП
"t0" intensity = "0.6173"
"t1" intensity = "4"
"t2" intensity = "1.5625"
"t3" intensity = "3.7037"
"t4" intensity = "9892.24"
"t5" intensity = "3.2258"
"t6" intensity = "1.8182"
"t7" intensity = "3.4483"
"t8" intensity = "107.76"
"t9" intensity = "3.5714"
"t10" intensity = "2.6316"
"t11" intensity = "5073.89"
"t12" intensity = "2.0833"
"t13" intensity = "4926.11"
"t14" intensity = "2.0408"
"t15" intensity = "10000.0"
Результат 4 л\р
Результат 1 л\р
Посторенние ссп для параллельного случая.
Для примера распараллелим самое внутреннее ветвление с использование следующего правила:
Последовательный:
Параллельный:
До распараллеливания:
"t4" intensity = "9892.24" = 104*p вход
"t8" intensity = "107.76" = 104*(1-p) выход
После распараллеливания:
"t8" intensity = "215,52" = 2*104*(1-p) выход
"t4" intensity = "9784,48" = 104 - 215,52 вход
Вероятность выхода удвоилась, так как число входов в цикл уменьшилось вдвое.
Пар ССП
ЭМЦ на основе пар. ССП
XML
"p0(1)-->p2(1)" intensity = "0.6173" source = "p0(1)" dest = "p2(1)"
"p2(1)-->p4(1)" intensity = "4" source = "p2(1)" dest = "p4(1)"
"p4(1)-->p6(1)" intensity = "1.5625" source = "p4(1)" dest = "p6(1)"
"p6(1)-->p8(1)" intensity = "3.7037" source = "p6(1)" dest = "p8(1)"
"p8(1)-->p09(1)p14(1)" intensity = "9784.48" source = "p8(1)" dest = "p09(1)p14(1)"
"p09(1)p14(1)-->p9(1)p14(1)" intensity = "3.2258" source = "p09(1)p14(1)" dest = "p9(1)p14(1)"
"p9(1)p14(1)-->p10(1)p14(1)" intensity = "1.8182" source = "p9(1)p14(1)" dest = "p10(1)p14(1)"
"p10(1)p14(1)-->p10(1)p15(1)" intensity = "3.2258" source = "p10(1)p14(1)" dest = "p10(1)p15(1)"
"p10(1)p15(1)-->p10(1)p16(1)" intensity = "1.8182" source = "p10(1)p15(1)" dest = "p10(1)p16(1)"
"p10(1)p16(1)-->p8(1)" intensity = "3.4483" source = "p10(1)p16(1)" dest = "p8(1)"
"p9(1)p14(1)-->p9(1)p15(1)" intensity = "3.2258" source = "p9(1)p14(1)" dest = "p9(1)p15(1)"
"p9(1)p15(1)-->p10(1)p15(1)" intensity = "1.8182" source = "p9(1)p15(1)" dest = "p10(1)p15(1)"
"p9(1)p15(1)-->p9(1)p16(1)" intensity = "1.8182" source = "p9(1)p15(1)" dest = "p9(1)p16(1)"
"p9(1)p16(1)-->p10(1)p16(1)" intensity = "1.8182" source = "p9(1)p16(1)" dest = "p10(1)p16(1)"
"p09(1)p14(1)-->p09(1)p15(1)" intensity = "3.2258" source = "p09(1)p14(1)" dest = "p09(1)p15(1)"
"p09(1)p15(1)-->p9(1)p15(1)" intensity = "3.2258" source = "p09(1)p15(1)" dest = "p9(1)p15(1)"
"p09(1)p15(1)-->p09(1)p16(1)" intensity = "1.8182" source = "p09(1)p15(1)" dest = "p09(1)p16(1)"
"p09(1)p16(1)-->p9(1)p16(1)" intensity = "3.2258" source = "p09(1)p16(1)" dest = "p9(1)p16(1)"
"p8(1)-->p07(1)" intensity = "215.52" source = "p8(1)" dest = "p07(1)"
"p07(1)-->p7(1)" intensity = "3.5714" source = "p07(1)" dest = "p7(1)"
"p7(1)-->p5(1)" intensity = "2.6316" source = "p7(1)" dest = "p5(1)"
"p5(1)-->p04(1)" intensity = "5073.89" source = "p5(1)" dest = "p04(1)"
"p04(1)-->p4(1)" intensity = "2.0833" source = "p04(1)" dest = "p4(1)"
"p5(1)-->p03(1)" intensity = "4926.11" source = "p5(1)" dest = "p03(1)"
"p03(1)-->p3(1)" intensity = "2.0408" source = "p03(1)" dest = "p3(1)"
"p3(1)-->p0(1)" intensity = "10000.0" source = "p3(1)" dest = "p0(1)"
ПМЦ на основе пар. ССП
(XML)
"p0(1)-->p2(1)" probability = "1.0" intensity = "1.61995788109509" deviation = "0.0"
"p2(1)-->p4(1)" probability = "1.0" intensity = "0.25" deviation = "0.0"
"p4(1)-->p6(1)" probability = "1.0" intensity = "0.64" deviation = "0.0"
"p6(1)-->p8(1)" probability = "1.0" intensity = "0.27000027000027" deviation = "0.0"
"p8(1)-->p09(1)p14(1)" probability = "0.978448" intensity = "0.0001" deviation = "0.0"
"p8(1)-->p07(1)" probability = "0.021552" intensity = "0.0001" deviation = "0.0"
"p09(1)p14(1)-->p9(1)p14(1)" probability = "0.5" intensity = "0.15500031000062" deviation = "0.0"
"p09(1)p14(1)-->p09(1)p15(1)" probability = "0.5" intensity = "0.15500031000062" deviation = "0.0"
"p9(1)p14(1)-->p10(1)p14(1)" probability = "0.360467882632831" intensity = "0.198255352894528" deviation = "0.0"
"p9(1)p14(1)-->p9(1)p15(1)" probability = "0.639532117367169" intensity = "0.198255352894528" deviation = "0.0"
"p10(1)p14(1)-->p10(1)p15(1)" probability = "1.0" intensity = "0.31000062000124" deviation = "0.0"
"p10(1)p15(1)-->p10(1)p16(1)" probability = "1.0" intensity = "0.549994500054999" deviation = "0.0"
"p10(1)p16(1)-->p8(1)" probability = "1.0" intensity = "0.28999797001421" deviation = "0.0"
"p9(1)p15(1)-->p10(1)p15(1)" probability = "0.5" intensity = "0.2749972500275" deviation = "0.0"
"p9(1)p15(1)-->p9(1)p16(1)" probability = "0.5" intensity = "0.2749972500275" deviation = "0.0"
"p9(1)p16(1)-->p10(1)p16(1)" probability = "1.0" intensity = "0.549994500054999" deviation = "0.0"
"p09(1)p15(1)-->p9(1)p15(1)" probability = "0.639532117367169" intensity = "0.198255352894528" deviation = "0.0"
"p09(1)p15(1)-->p09(1)p16(1)" probability = "0.360467882632831" intensity = "0.198255352894528" deviation = "0.0"
"p09(1)p16(1)-->p9(1)p16(1)" probability = "1.0" intensity = "0.31000062000124" deviation = "0.0"
"p07(1)-->p7(1)" probability = "1.0" intensity = "0.28000224001792" deviation = "0.0"
"p7(1)-->p5(1)" probability = "1.0" intensity = "0.37999696002432" deviation = "0.0"
"p5(1)-->p04(1)" probability = "0.507389" intensity = "0.0001" deviation = "0.0"
"p5(1)-->p03(1)" probability = "0.492611" intensity = "0.0001" deviation = "0.0"
"p04(1)-->p4(1)" probability = "1.0" intensity = "0.480007680122882" deviation = "0.0"
"p03(1)-->p3(1)" probability = "1.0" intensity = "0.49000392003136" deviation = "0.0"
"p3(1)-->absorb" probability = "1.0" intensity = "0.0001" deviation = "0.0"
"absorb-->absorb" probability = "1.0" intensity = "0.0" deviation = "0.0"