Скачиваний:
15
Добавлен:
01.05.2014
Размер:
115.71 Кб
Скачать

Санкт-Петербургский государственный

электротехнический университет

Кафедра МОЭВМ

Лабораторная работа №3

Анализ операционных графовых моделей последовательных

программ методом эквивалентных преобразований

Выполнил: Виноградов М.Н.

Группа: 1382

Преподаватель: Кирьянчиков В.А.

Санкт-Петербург

2006

  1. Задание

Для задачи обработки данных, рассматривавшейся в лаборатор­ных работах 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: Граф с нагруженными вершинами, полученный в лабораторной работе №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

  1. Анализ модели методом эквивалентных преобразований

    1. Старый 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

    1. Н овый CSA

Таблица 1: Оценка времени выполнения программы в мкс

На основе фундаментальной матрицы

Методом эквивалентных преобразований

Sampler

Старый CSA

Новый CSA

Математическое ожидание

22.37

22.37

22.37

20.12

Дисперсия

447.6

447.56

447.56

7