Отчёт о лабораторной работе №2 «Анализ огм последовательных программ на основе аппарата поглощающих цепей Маркова» Преподаватель: Кирьянчиков В. А




Скачать 110.83 Kb.
НазваниеОтчёт о лабораторной работе №2 «Анализ огм последовательных программ на основе аппарата поглощающих цепей Маркова» Преподаватель: Кирьянчиков В. А
Дата публикации17.06.2013
Размер110.83 Kb.
ТипОтчет
odtdocs.ru > География > Отчет
Министерство Образования Российской Федерации

Санкт-Петербургский Государственный Электротехнический Университет «ЛЭТИ»

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


Отчёт о лабораторной работе №2

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

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

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

Выполнил: студент гр. 3351

Ерёменок А.В.

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

2007
  1. Постановка задачи


    1. Для полученного графа построить соответствующую ему поглощающую цепь Маркова (ПЦМ), определить ее фундаментальную матрицу(ФМ) и вектор нагрузочных парметров L.

    2. Вычислить оценки средних времен, дисперсии и СКО времен выполнения как всей программы, так и ее основных фрагментов, на которые она может быть разбита.

    3. Определение ФМ ПЦМ требуется выполнить двумя способами:

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

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

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

    Выполнение

    1. Граф ПЦМ, соответствующей программе из лабораторной работы 1





    1. ^

      Вектор затрат:


      С учетом результатов, полученных в л/р1:

  • в тактах:

Вершина

1

2

3

4

5

6

7

8

9

10

Вес

1

1

14

14

16

5

21

2

10

1



  • в микросекундах:

Вершина

1

2

3

4

5

6

7

8

9

10

Вес

0,63

0,60

11,64

11,87

13,23

3,84

17,64

1,23

8,64

0,65


    1. ^

      Структурирование графа для метода поуровневой детализации:


  • чтобы воспользоваться fm.exe, граф нужно разбить на подграфы следующим образом:


    где CC3, C10, BB9, LL91, LL92 — фиктивные вершины.

  • Эти подграфы будут иметь следующие фундаментальные матрицы:

    • S0

1

1

1

1

0

1

1

1

0

0

1

1

0

0

0

1



    • S1

1

1/(1-q)

q/(1-q)

1

0

1/(1-q)

q/(1-q)

1

0

1/(1-q)

1/(1-q)

1

0

0

0

1

      q = 0,9942; 1-q = 0,0057

      1/(1-q) = 175; q/(1-q) = 174

1

175

174

1

0

175

174

1

0

175

175

1

0

0

0

1



    • S2

      1

      1

      1

      1

      0

      1

      1

      1

      0

      0

      1

      1

      0

      0

      0

      1

    • S3 и S4

1

p

1-p

1

0

1

0

1

0

0

1

1

0

0

0

1

      p = 0,9942; 1-p = 0,0057

1

0,9942

0,0058

1

0

1

0

1

0

0

1

1

0

0

0

1


    1. ^

      Результаты вычисления матриц при помощи fm.exe

      1. На входе


tops {

L1(1), L2(1), L10(1),

CC3(0), C3(14), C10(0),

LL4(14), LL91(0), LL92(10),

B5(16), B51(0), B9(0),

BB6(5), BB7(21), BB8(2), BB9(0)

}

links {

L1->L2(1), L2->CC3(1),

CC3->C3(1),

C3->C10(0.0058),

C3->LL4(0.9942),

LL4->B5(1),

B5->BB6(0.9942),

BB6->BB7(0.9942),

BB7->BB9(1),

BB6->BB8(0.0058),

BB8->BB9(1),

BB9->B9(1),

B5->B51(0.0058),

B51->B9(1),

B9->LL91(1), LL91->LL92(1),

LL92->C3(1),

C10->L10(1)

}
      1. ^

        Поуровневая детализация


        Первая строка фундаментальной матрицы выглядит так:

(L1,L1) = 1

(L1,L2) = 1

(L1,CC3) = 1

(L1,C3) = 172.414

(L1,LL4) = 171.414

(L1,B5) = 171.414

(L1,B51) = 0.9942

(L1,BB6) = 170.42

(L1,BB8) = 0.988434

(L1,BB7) = 169.431

(L1,BB9) = 170.42

(L1,B9) = 171.414

(L1,LL91) = 171.414

(L1,LL92) = 171.414

(L1,C10) = 1

(L1,L10) = 1
      1. ^

        Алгебраический метод


        Первая строка фундаментальной матрицы выглядит так:

(L1,L1) = 1

(L1,L2) = 1

(L1,CC3) = 1

(L1,C3) = 172.414

(L1,LL4) = 171.414

(L1,B5) = 171.414

(L1,B51) = 0.9942

(L1,BB6) = 170.42

(L1,BB8) = 0.988434

(L1,BB7) = 169.431

(L1,BB9) = 170.42

(L1,B9) = 171.414

(L1,LL91) = 171.414

(L1,LL92) = 171.414

(L1,C10) = 1

(L1,L10) = 1
      1. ^

        Параметры потребления ресурсов


      • в тактах

Потребление ресурсов:

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

L1 ¦ 1 ¦

L2 ¦ 1 ¦

CC3 ¦ 0 ¦

C3 ¦ 14 ¦

LL4 ¦ 14 ¦

B5 ¦ 16 ¦

B51 ¦ 0 ¦

BB6 ¦ 5 ¦

BB8 ¦ 2 ¦

BB7 ¦ 21 ¦

BB9 ¦ 0 ¦

B9 ¦ 0 ¦

LL91 ¦ 0 ¦

LL92 ¦ 10 ¦

C10 ¦ 0 ¦

L10 ¦ 1 ¦

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

Средние значения потребления ресурсов:

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

L1 ¦ 1.369e+004 ¦

L2 ¦ 1.368e+004 ¦

CC3 ¦ 1.368e+004 ¦

C3 ¦ 1.368e+004 ¦

LL4 ¦ 1.375e+004 ¦

B5 ¦ 1.374e+004 ¦

B51 ¦ 1.369e+004 ¦

BB6 ¦ 1.372e+004 ¦

BB8 ¦ 1.37e+004 ¦

BB7 ¦ 1.371e+004 ¦

BB9 ¦ 1.369e+004 ¦

B9 ¦ 1.369e+004 ¦

LL91 ¦ 1.369e+004 ¦

LL92 ¦ 1.369e+004 ¦

C10 ¦ 1 ¦

L10 ¦ 1 ¦

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

Дисперсии потребления ресурсов:

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

L1 ¦ 1.879e+008 ¦

L2 ¦ 1.879e+008 ¦

CC3 ¦ 1.879e+008 ¦

C3 ¦ 1.879e+008 ¦

LL4 ¦ 1.879e+008 ¦

B5 ¦ 1.879e+008 ¦

B51 ¦ 1.879e+008 ¦

BB6 ¦ 1.879e+008 ¦

BB8 ¦ 1.879e+008 ¦

BB7 ¦ 1.879e+008 ¦

BB9 ¦ 1.879e+008 ¦

B9 ¦ 1.879e+008 ¦

LL91 ¦ 1.879e+008 ¦

LL92 ¦ 1.879e+008 ¦

C10 ¦ 0 ¦

L10 ¦ 0 ¦

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

      • в микросекундах

Потребление ресурсов:

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

L1 ¦ 0.63 ¦

L2 ¦ 0.6 ¦

CC3 ¦ 0 ¦

C3 ¦ 11.64 ¦

LL4 ¦ 11.87 ¦

B5 ¦ 13.23 ¦

B51 ¦ 0 ¦

BB6 ¦ 3.84 ¦

BB8 ¦ 1.23 ¦

BB7 ¦ 17.64 ¦

BB9 ¦ 0 ¦

B9 ¦ 0 ¦

LL91 ¦ 0 ¦

LL92 ¦ 8.64 ¦

C10 ¦ 0 ¦

L10 ¦ 0.65 ¦

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

Средние значения потребления ресурсов:

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

L1 ¦ 1.144e+004 ¦

L2 ¦ 1.144e+004 ¦

CC3 ¦ 1.144e+004 ¦

C3 ¦ 1.144e+004 ¦

LL4 ¦ 1.149e+004 ¦

B5 ¦ 1.148e+004 ¦

B51 ¦ 1.144e+004 ¦

BB6 ¦ 1.147e+004 ¦

BB8 ¦ 1.145e+004 ¦

BB7 ¦ 1.146e+004 ¦

BB9 ¦ 1.144e+004 ¦

B9 ¦ 1.144e+004 ¦

LL91 ¦ 1.144e+004 ¦

LL92 ¦ 1.144e+004 ¦

C10 ¦ 0.65 ¦

L10 ¦ 0.65 ¦

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

Дисперсии потребления ресурсов:

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

L1 ¦ 1.313e+008 ¦

L2 ¦ 1.313e+008 ¦

CC3 ¦ 1.313e+008 ¦

C3 ¦ 1.313e+008 ¦

LL4 ¦ 1.313e+008 ¦

B5 ¦ 1.313e+008 ¦

B51 ¦ 1.313e+008 ¦

BB6 ¦ 1.313e+008 ¦

BB8 ¦ 1.313e+008 ¦

BB7 ¦ 1.313e+008 ¦

BB9 ¦ 1.313e+008 ¦

B9 ¦ 1.313e+008 ¦

LL91 ¦ 1.313e+008 ¦

LL92 ¦ 1.313e+008 ¦

C10 ¦ 0 ¦

L10 ¦ 0 ¦

*****************************
    1. ^

      Исследование фрагмента графа программы

      1. Рассмотрим следующий фрагмент программы:






        где место фиктивной вершины BB9 займет L10.
      1. ^

        Вычислим его характеристики при помощи fm.exe:


        1. На входе

tops {

BB6(3.84), BB7(17.64), BB8(1.23), BB9(0.65)

}

links {

BB6->BB7(0.9942),

BB7->BB9(1),

BB6->BB8(0.0058),

BB8->BB9(1)

}

        1. Поуровневая детализация

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

BB6 ¦ 1 0.9942 0.0058 1 ¦

BB7 ¦ 0 1 0 1 ¦

BB8 ¦ 0 0 1 1 ¦

BB9 ¦ 0 0 0 1 ¦

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

        1. Алгебраический метод

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

BB6 ¦ 1 0.9942 0.0058 1 ¦

BB7 ¦ 0 1 0 1 ¦

BB8 ¦ 0 0 1 1 ¦

BB9 ¦ 0 0 0 1 ¦

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

        1. Потребление ресурсов

Потребление ресурсов:

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

BB6 ¦ 3.84 ¦

BB7 ¦ 17.64 ¦

BB8 ¦ 1.23 ¦

BB9 ¦ 0.65 ¦

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

Средние значения потребления ресурсов:

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

BB6 ¦ 22.03 ¦

BB7 ¦ 18.29 ¦

BB8 ¦ 1.88 ¦

BB9 ¦ 0.65 ¦

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

Дисперсии потребления ресурсов:

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

BB6 ¦ 1.553 ¦

BB7 ¦ 5.684e-014 ¦

BB8 ¦ -4.441e-016 ¦

BB9 ¦ 0 ¦

*****************************
  1. Вывод


В ходе лабораторной работы при помощи ПС fm.exe построена фундаментальная матрица для заданной программы — двумя способами: алгебраическим(преобразованием матрицы переходов и обращением результата) и методом поуровневой детализации. Вычислены средние знания потребления процессорного времени операциями программы в тактах и микросекундах.

Высокие временные затраты можно объяснить рассмотрением худшего случая при вычислении характеристик потребления ресурсов в л/р1 с использованием ПС Sampler.

Добавить документ в свой блог или на сайт

Похожие:

Отчёт о лабораторной работе №2 «Анализ огм последовательных программ...
Для полученного графа построить соответствующую ему поглощающую цепь Маркова (пцм), определить ее фундаментальную матрицу(ФМ) и вектор...

Отчёт о лабораторной работе №3 «Анализ операционных графовых моделей...
Для задачи обработки данных, рассматривавшейся в лабораторных работах 1-2, построить управляющий граф программы с нагруженными дугами,...

Отчёт о лабораторной работе №13 «исследование разветвленных цепей...
Цель: экспериментальная проверка напряжений и токов в цепях с полупроводниковым диодом, рассчитанных с использованием метода кусочно-линейной...

Отчёт о лабораторной работе №13 «исследование разветвленных цепей...
Цель: экспериментальная проверка напряжений и токов в цепях с полупроводниковым диодом, рассчитанных с использованием метода кусочно-линейной...

Отчёт о лабораторной работе №2 «Изучение понятия сопроцессов и виртуальных...
Написать программу, устанавливающую виртуальные связи между тремя сопроцессами на одном процессоре

Отчёт по лабораторной работе на тему «3d графика»
В данной лабораторной работе использовалась программа Autodesk 3ds Max 2009 и Adobe Photoshop cs4

Отчет по лабораторной работе №9 по курсу «компьютерная графика» Студент...
Вариант 28**: Забить пробный гвоздь в тестовую доску (прямоугольную в поперечном сечении)

Отчёт о лабораторной работе №3 «Применение протоколов связи приложений...
На Visual Basic for Application написать макрос, который с помощью dde создает новую группу на рабочем столе и в ней новый программный...

Отчёт о лабораторной работе №2 «Разработка приложений с использованием...
Освоить приемы создания приложений типа Model-View-Controller при помощи библиотеки mfc

Отчёт о лабораторной работе №2 «Исследование системы массового обслуживания...
Используя пакет gpss составить программу и провести моделирование простейшей системы массового обслуживания (смо)

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
odtdocs.ru
Главная страница