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

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

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

Анализ ОГМ последовательных программ

на основе аппарата поглощающих цепей Маркова

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

Группа: 1382

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

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

2006

1. Задание

Для полученного графа построить соответствующую ему поглощающую цепь Маркова (ПЦМ), определить ее фундаментальную матрицу(ФМ) и вектор нагрузочных парметров L. Вычислить оценки средних времен, дисперсии и СКО времен выполнения как всей программы, так и ее основных фрагментов, на которые она может быть разбита (при затруднении с выбором – согласовать с преподавателем). Определение ФМ ПЦМ требуется выполнить двумя способами:

1. путем непосредственного обращения матрицы (I-Q), полученной по переходной матрице ПЦМ, соответствующей графу всей программы;

2. путем структурной детализации фундаментальных матриц, соответствующих подграфам элементарных вычислительных процессов.

При выполнении расчетов следует использовать программу FM.EXE, способы использования которой для анализа характеристик программ описаны выше.

Оценки времен выполнения следует определить как в тактах, так и в абсолютных единицах времени (сек, мсек или мксек). Результаты расчетов представить в виде таблиц как для всей программы, так и для ее фрагментов.

2. Операционная графовая модель

Рис.1: Граф с нагруженными вершинами, полученный в лабораторной работе №1

Времена выполнения фрагментов программы в мкс:

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
Рис. 2: Граф, преобразованный к структурированному виду

Для возможности вычисления фундаментальной матрицы методом поуровневой детализации, граф, полученный в лабораторной работе №1 (Рис.1) необходимо преобразовать к структурированному виду:

• граф должен представлять суперпозицию базовых конструкций: следование, ветвление, цикл с предусловием;

• каждая конструкция должна состоять ровно из четырех вершин;

• детализировать можно только определенные вершины: для следования – две внутренние вершины, для ветвления – прямая и обратная ветви, для цикла – тело цикла.

Преобразованный граф изображен на рис.2. Пунктирные прямоугольники показывают базовые конструкции. При преобразовании графа цикл с постусловием был приведен к циклу с предусловием, а также введены фиктивные вершины с нулевым потреблением ресурсов.

3. Фундаментальная матрица

Фундаментальная матрица, а также среднее время и дисперсия времени выполнения программы найдены с помощью программы FM.exe. Фундаментальная матрица вычислена как алгебраическим способом, так и методом поуровневой детализации.

Протокол работы:

Вызвано распознавание шаблона для подграфа @ROOT:

начальная вершина S1, конечная вершина S22

Конструкция СЛЕДОВАНИЕ

Начало первого оператора: S2

Окончание первого оператора: S8

Начало второго оператора: S9

Окончание второго оператора: S21

Матрица для подстановки:

**********************************************************

S1 ║ 1 1 1 1 ║

@TMP0 ║ 0 1 1 1 ║

@TMP1 ║ 0 0 1 1 ║

S22 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP0:

начальная вершина S2, конечная вершина S8

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

S2 ║ 1 1 5e-009 1 ║

@TMP2 ║ 0 1 0 1 ║

@TMP3 ║ 0 0 1 1 ║

S8 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP2:

начальная вершина S3, конечная вершина S3

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP3:

начальная вершина S4, конечная вершина S7

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

S4 ║ 1 0.5 0.5 1 ║

@TMP4 ║ 0 1 0 1 ║

@TMP5 ║ 0 0 1 1 ║

S7 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP4:

начальная вершина S6, конечная вершина S6

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP5:

начальная вершина S5, конечная вершина S5

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP1:

начальная вершина S9, конечная вершина S21

Конструкция ЦИКЛ

Вершина проверки условия: S10

Дуга, входящая в тело цикла: S10->S11

Дуга, выходящая из тела цикла: S20->S10

Вероятность повторения тела цикла: 0.9

Вероятность выхода из цикла: 0.1

Матрица для подстановки:

**********************************************************

S9 ║ 1 10 9 1 ║

S10 ║ 0 10 9 1 ║

@TMP6 ║ 0 10 10 1 ║

S21 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP6:

начальная вершина S11, конечная вершина S20

Конструкция СЛЕДОВАНИЕ

Начало первого оператора: S12

Окончание первого оператора: S18

Начало второго оператора: S19

Окончание второго оператора: S19

Матрица для подстановки:

**********************************************************

S11 ║ 1 1 1 1 ║

@TMP7 ║ 0 1 1 1 ║

@TMP8 ║ 0 0 1 1 ║

S20 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP7:

начальная вершина S12, конечная вершина S18

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

S12 ║ 1 5e-009 1 1 ║

@TMP9 ║ 0 1 0 1 ║

@TMP10 ║ 0 0 1 1 ║

S18 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP9:

начальная вершина S14, конечная вершина S17

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

S14 ║ 1 0.5 0.5 1 ║

@TMP11 ║ 0 1 0 1 ║

@TMP12 ║ 0 0 1 1 ║

S17 ║ 0 0 0 1 ║

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP11:

начальная вершина S16, конечная вершина S16

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP12:

начальная вершина S15, конечная вершина S15

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP10:

начальная вершина S13, конечная вершина S13

Шаблон распознан как атомарная операция

Вызвано распознавание шаблона для подграфа @TMP8:

начальная вершина S19, конечная вершина S19

Шаблон распознан как атомарная операция

Фундаментальная матрица (три первые строки):

(S1,S1) = 1 (S1,S2) = 1 (S1,S3) = 1 (S1,S4) = 5e-009 (S1,S6) = 2.5e-009 (S1,S5) = 2.5e-009 (S1,S7) = 5e-009 (S1,S8) = 1 (S1,S9) = 1 (S1,S10) = 10 (S1,S11) = 9 (S1,S12) = 9 (S1,S14) = 4.5e-008 (S1,S16) = 2.25e-008 (S1,S15) = 2.25e-008 (S1,S17) = 4.5e-008 (S1,S13) = 9 (S1,S18) = 9 (S1,S19) = 9 (S1,S20) = 9 (S1,S21) = 1 (S1,S22) = 1

(S2,S1) = 0 (S2,S2) = 1 (S2,S3) = 1 (S2,S4) = 5e-009 (S2,S6) = 2.5e-009 (S2,S5) = 2.5e-009 (S2,S7) = 5e-009 (S2,S8) = 1 (S2,S9) = 1 (S2,S10) = 10 (S2,S11) = 9 (S2,S12) = 9 (S2,S14) = 4.5e-008 (S2,S16) = 2.25e-008 (S2,S15) = 2.25e-008 (S2,S17) = 4.5e-008 (S2,S13) = 9 (S2,S18) = 9 (S2,S19) = 9 (S2,S20) = 9 (S2,S21) = 1 (S2,S22) = 1

(S3,S1) = 0 (S3,S2) = 0 (S3,S3) = 1 (S3,S4) = 0 (S3,S6) = 0 (S3,S5) = 0 (S3,S7) = 0 (S3,S8) = 1 (S3,S9) = 1 (S3,S10) = 10 (S3,S11) = 9 (S3,S12) = 9 (S3,S14) = 4.5e-008 (S3,S16) = 2.25e-008 (S3,S15) = 2.25e-008 (S3,S17) = 4.5e-008 (S3,S13) = 9 (S3,S18) = 9 (S3,S19) = 9 (S3,S20) = 9 (S3,S21) = 1 (S3,S22) = 1