Санкт-Петербургский государственный электротехнический университет
Кафедра МОЭВМ
Анализ производительности вычислительных систем.
Отчет по лабораторным работам №1 и№2
Выполнил:
Студент гр.3351
Сергеев М.В.
Санкт-Петербург
2007г.
-
Постановка задачи
Задание 1
Для рассматривавшегося в лабораторных работах курса «Метрология программного обеспечения» (или курса "Качество и надежность программного обеспечения") индивидуального задания разработать операционную модель управляющего графа программы на основе схемы алгоритма и ассемблерного представления программы. При выполнении работы рекомендуется для упрощения обработки графа и ПЦМ исключить диалог при выполнении операций ввода-вывода данных, а также привести программу к структурированному виду.
Выбрать вариант графа с нагруженными вершинами, каждая из которых должна представлять фрагмент программы, соответствующий линейному участку или ветвлению. При расчете вероятностей ветвлений, зависящих от распределения данных, принять равномерное распределение обрабатываемых данных в ограниченном диапазоне (например, [0,100] - для положительных чисел или [-100,100] - для произвольных чисел). В случае ветвлений, вызванных проверкой выхода из цикла, вероятности рассчитываются исходя априорных сведений о числе повторений цикла. Сложные случаи оценки вероятностей ветвлений согласовать с преподавателем.
В качестве параметров, характеризующих потребление ресурсов, использовать времена выполнения команд соответствующих участков программы, задаваемые в тактах процессора. Выполнить оценку времен выполнения каждого линейного участка и каждого ветвления в графе программы. Оценку времен выполнения участков производить либо с использованием монитора (например, Sampler или Vtune), либо прямым подсчетом по тексту программы. В последнем случае времена исполнения команд процессора (в тактах) следует выбирать из файла InstrX86.tim в соответствии с типом и параметрами компьютера, выбираемыми по номеру в списке группы.
Задание 2
Для полученного графа построить соответствующую ему поглощающую цепь Маркова (ПЦМ), определить ее фундаментальную матрицу(ФМ) и вектор нагрузочных парметров L. Вычислить оценки средних времен, дисперсии и СКО времен выполнения как всей программы, так и ее основных фрагментов, на которые она может быть разбита (при затруднении с выбором – согласовать с преподавателем). Определение ФМ ПЦМ требуется выполнить двумя способами:
путем непосредственного обращения матрицы (I-Q), полученной по переходной матрице ПЦМ, соответствующей графу всей программы;
путем структурной детализации фундаментальных матриц, соответствующих подграфам элементарных вычислительных процессов.
При выполнении расчетов следует использовать программу FM.EXE, способы использования которой для анализа характеристик программ описаны выше.
Оценки времен выполнения следует определить как в тактах, так и в абсолютных единицах времени (сек, мсек или мксек). Результаты расчетов представить в виде таблиц как для всей программы, так и для ее фрагментов.
-
Текст программы
|
Source |
Время мс |
Количество проходов |
№ вершины |
|
|
void quicksort(float x[], int n) |
|
|
|
|
|
{ |
234 |
241
|
100 |
1 |
|
int left[20], right[20]; |
|
|||
|
int i,j,sp,mid; |
|
|||
|
float pivot; |
|
|||
|
|
|
|||
|
left[1] = 1; |
6 |
|||
|
right[1] = n; |
|
|||
|
sp = 1; |
1 |
|||
|
|
|
|
|
|
|
while (sp>0) |
29 |
29 |
|
2 |
|
{ |
|
|
|
|
|
if (left[sp] >= right[sp]) |
57 |
57 |
6928 |
3 |
|
{ sp = sp-1; } |
24 |
24 |
3514 |
4 |
|
else |
1 |
94 |
3414 |
5 |
|
{ |
|
|||
|
i = left[sp]; |
35 |
|||
|
j = right[sp]; |
9 |
|||
|
pivot = x[j]; |
28 |
|||
|
mid = (i+j) % 2; |
21 |
|||
|
if ((j-i)>5) |
5 |
5 |
3414 |
6 |
|
if (((x[mid]<pivot) && (x[mid]>x[i])) || ((x[mid]>pivot) && (x[mid]<x[i]))) |
35 |
55 |
1248 |
8 |
|
swap(x[mid],x[j]); |
|
0 |
||
|
else |
|
|
||
|
if (((x[i]<x[mid]) && (x[i]>pivot)) || ((x[i]>x[mid]) && (x[i]<pivot))) |
14 |
1248 |
||
|
swap(x[i],x[j]); |
6 |
537 |
||
|
pivot = x[j]; |
20 |
20 |
3414 |
10 |
|
while (i<j) |
5 |
5 |
12 |
|
|
{ |
|
|
|
|
|
while (x[i]<pivot) |
113 |
311 |
7854 |
13 |
|
{ i = i+1; } |
36 |
|||
|
j = j-1; |
46 |
|||
|
while ((i<j) && (pivot<x[j])) |
74 |
|||
|
{ j = j-1; } |
6 |
|||
|
if (i<j) |
29 |
|||
|
{ swap(x[i],x[j]); } |
3 |
|||
|
} // while |
4 |
|||
|
j = right[sp]; // pivot to i |
18 |
54 |
3414 |
14 |
|
swap(x[i],x[j]); |
36 |
|||
|
if (i-left[sp]>=right[sp]-i) |
20 |
20 |
15 |
|
|
{ // put shorter part first |
|
|
|
|
|
left[sp+1] = left[sp]; |
5 |
27 |
1482 |
16 |
|
right[sp+1] = i-1; |
14 |
|||
|
left[sp] = i+1; |
8 |
|||
|
} |
|
|
|
|
|
else |
|
|
|
|
|
{ |
|
|
|
|
|
left[sp+1] = i+1; |
|
13 |
1932 |
17 |
|
right[sp+1] = right[sp]; |
7 |
|||
|
right[sp] = i-1; |
6 |
|||
|
} |
|
|
|
|
|
sp = sp+1; // push stack |
8 |
8 |
|
19 |
|
} // if |
|
|
|
|
|
} // while |
6 |
6 |
|
21 |
|
} |
5 |
5 |
|
22 |
Программа сортирует массив методом быстрой сортировки. Время выполнения по строкам рассчитано с помощью профилировщика VTune. При построении ОГМ алгоритм программы слегка обобщался для того, чтобы избежать излишней загруженности графа.
Участок с вершинами 6, 7, 8 детально выглядит так
Но как видно из таблицы:
|
if ((j-i)>5) |
5 |
5 |
3414 |
6 |
|
if (((x[mid]<pivot) && (x[mid]>x[i])) || ((x[mid]>pivot) && (x[mid]<x[i]))) |
35 |
55 |
1248 |
8 |
|
swap(x[mid],x[j]); |
|
0 |
81 |
|
|
else |
|
|
|
|
|
if (((x[i]<x[mid]) && (x[i]>pivot)) || ((x[i]>x[mid]) && (x[i]<pivot))) |
14 |
1248 |
82 |
|
|
swap(x[i],x[j]); |
6 |
537 |
участок 81 никогда не используется в алгоритме. Поэтому без потери информации о структуре можно упростить этот участок до:
При этом нагрузку вершин 8 и 82 объединить в вершине 8.