Лабораторная работа 31 / Lab3
.docСанкт-Петербургский государственный
электротехнический университет
Кафедра МОЭВМ
Лабораторная работа №3
Анализ операционных графовых моделей последовательных
программ методом эквивалентных преобразований
Выполнил: Виноградов М.Н.
Группа: 1382
Преподаватель: Кирьянчиков В.А.
Санкт-Петербург
2006
-
Задание
Для задачи обработки данных, рассматривавшейся в лабораторных работах 1-2, построить управляющий граф программы с нагруженными дугами, эквивалентный графу с нагруженными вершинами, полученному в лабораторной работе 1.
В качестве параметров, характеризующих потребление ресурсов на дуге ij, использовать тройку Pij,Mij,Dij , где: Pij - вероятность выполнения процесса для дуги ij,
Mij - мат.ожидание потребления ресурса процессом для дуги ij,
Dij - дисперсия потребления ресурса процессом для дуги ij.
В качестве потребляемого ресурса в данной работе рассматривается время процессора, а оценками мат.ожиданий времен для дуг исходного графа следует принять времена выполнения операторов ( команд ) соответствующих этим дугам участков программы. Дисперсиям исходных дуг следует присвоить нулевые значения.
Составить описание полученного графа на входном языке пакета CSA (см. файл csa_lang.txt, содержащий описание входного языка пакета) по примеру приведенному ниже для графа, соответствующего конструкции "Ветвление":
Tops s1,s2,s3,s4 ; Множество вершин графа, где s4 - поглощающая вершина
Arcs ; Начало описания множества дуг
;
s1->s2 1.0,4, ; Нулевая дисперсия Dij может опускаться
s2->s3 0.25,0,0, ;
s2->s4 0.75,8, ;
s3->s4 1,16, ;
s4->s4 1 ; Дуга, соответствующая поглощающей
; вершине, ресурсов не потребляет
и сохранить его в каталоге CSA\EXAMPLES\ под именем ???.csa, выбираемым по усмотрению пользователя.
Запустить программу ???.csa на трансляцию и обработку. С помощью предоставляемых пакетом CSA в виде меню действий по редактированию и анализу графа (см. файл csa_help.txt, содержащий краткое руководство пользователя пакетом CSA) вычислить среднее время и дисперсию времени выполнения всей программы, а также ее фрагментов, рассматривавшихся в лабораторной работе №2. Сравнить полученные результаты с результатами расчета аналогичных характеристик через фундаментальную матрицу ПЦМ, полученными в лабораторной работе N2 и объяснить расхождения, если они обнаружатся.
-
Операционная графовая модель
|
Рис.1: Граф с нагруженными вершинами, полученный в лабораторной работе №1 |
|
Рис.2: Граф с нагруженными дугами |
Времена выполнения фрагментов программы в мкс:
R1 = 0,07 R2 = 0,67 R3 = 0,11 R4 = 0,16 R5 = 0,04 |
R6 = 0,05 R7 = 1,10 R8 = 0,35 R9 = 0 |
-
Анализ модели методом эквивалентных преобразований
-
Старый CSA
Файл с исходными данными
name=Newton
type=amc
tops
{ t1, t2, t3, t4, t5, t6, t7, t8, t9 }
links
{ t1->t2 = (1.0, 0.07, 0.0)
t2->t3 = (1.0, 0.67, 0.0)
t3->t4 = (0.000000005, 0.11, 0.0)
t3->t7 = (0.999999995, 0.11, 0.0)
t4->t5 = (0.5, 0.16, 0.0)
t4->t6 = (0.5, 0.16, 0.0)
t5->t7 = (1.0, 0.04, 0.0)
t6->t7 = (1.0, 0.05, 0.0)
t7->t8 = (1.0, 1.1, 0.0)
t8->t2 = (0.9, 0.35, 0.0)
t8->t9 = (0.1, 0.35, 0.0)
t9->t9 = (1)
}
Протокол работы
ѕѕѕ Начальное состояние [ 0.00 Ok] ѕѕѕ
Поглощающая Марковская цепь Newton
Нет информации пользователя
Вершина t1 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t2 1.000000 0.070000 0.000000 |
Вершина t2 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t3 1.000000 0.670000 0.000000 |
Вершина t3 : выходящих дуг - 2
Дуга к вершине Параметры (p,m,d) |
t4 0.000000 0.110000 0.000000 t7 1.000000 0.110000 0.000000 |
Вершина t4 : выходящих дуг - 2
Дуга к вершине Параметры (p,m,d) |
t5 0.500000 0.160000 0.000000 t6 0.500000 0.160000 0.000000 |
Вершина t5 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t7 1.000000 0.040000 0.000000 |
Вершина t6 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t7 1.000000 0.050000 0.000000 |
Вершина t7 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t8 1.000000 1.100000 0.000000 |
Вершина t8 : выходящих дуг - 2
Дуга к вершине Параметры (p,m,d) |
t2 0.900000 0.350000 0.000000 t9 0.100000 0.350000 0.000000 |
Вершина t9 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t9 1.000000 0.000000 0.000000 |
ѕѕѕ Удалена вершина t6 [ 11.76 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t5 [ 23.53 Ok] ѕѕѕ
ѕѕѕ Склеены параллельные дуги у вершины t4 [ 29.41 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t4 [ 41.18 Ok] ѕѕѕ
ѕѕѕ Склеены параллельные дуги у вершины t3 [ 47.06 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t3 [ 58.82 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t7 [ 70.59 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t2 [ 82.35 Ok] ѕѕѕ
ѕѕѕ Удалены циклические дуги у вершины t8 [ 88.24 Ok] ѕѕѕ
ѕѕѕ Удалена вершина t8 [100.00 Ok] ѕѕѕ
ѕѕѕ Заключительное состояние [100.00 Ok] ѕѕѕ
Поглощающая Марковская цепь Newton
Нет информации пользователя
Вершина t1 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t9 1.000000 22.370000 447.561000 |
Вершина t9 : выходящих дуг - 1
Дуга к вершине Параметры (p,m,d) |
t9 1.000000 0.000000 0.000000 |
-
Н овый CSA
Таблица 1: Оценка времени выполнения программы в мкс
|
На основе фундаментальной матрицы |
Методом эквивалентных преобразований |
Sampler |
|
Старый CSA |
Новый CSA |
|||
Математическое ожидание |
22.37 |
22.37 |
22.37 |
20.12 |
Дисперсия |
447.6 |
447.56 |
447.56 |
|