-
Операционная графовая модель
Построенная ОГМ представлена в виде графа с нагруженными вершинами. Фрагменты программы, соответствующие вершинам указаны на графе и в таблице 2. В графе имеется три ветвления, в вершинах 3, 4 и 8. Оценивание вероятностей выбора ветви представлено в таблице 1.
Таблица 1. Оценивание вероятностей выбора ветвей
|
Вершина |
Вероятности выбора ветвей |
Обоснование |
|
3 |
и
|
В данном блоке принятия
решения исход события зависит от
входных данных. Проверяемое условие
истинно только тогда, когда входное
значение
|
|
4 |
0,5 и 0,5 |
Исход события зависит
от того, является ли входное значение
x (которое удовлетворяет
|
|
8 |
0,9 и 0,1 |
Данное ветвление
соответствует проверке выхода из
цикла. Если считать, что среднее
количество повторений тела цикла
равно
|
.
Если
(точность нахождения корня) и величина
x распределена равномерно
на отрезке [‑100,100], то вероятность
.
)
положительным или отрицательным. Так
как величина x распределена
равномерно на отрезке [‑100,100], то
вероятность p=0,5.
,
то вероятность выхода из цикла равна
(цикл с постусловием), а вероятность
продолжения цикла
Для оценки среднего количества повторений тела цикла, программа многократно запускалась с различными входными данными. Входное значение x менялось в диапазоне [-100; 100] с шагом 0,01. Среднее арифметическое количества повторений получилось равным 9,03295 ≈ 9. Наименьшее значение равно 1 (когда x = 1,414214), наибольшее равно 26 (когда x = 0 или близко к 0). При x = 100, количество повторений равно 11.
В качестве параметров, характеризующих потребление ресурсов используются времена выполнения соответствующих участков программы. Оценка этих времен произведена как прямым подсчетом по тексту программы, так и измерительным способом с помощью монитора Sampler.
Таблица 2. Оценка времени выполнения фрагментов программы прямым подсчетом по тексту программы (для компьютера i486)
|
№ вершины |
Фрагмент программы |
Время выполнения в тактах |
||
|
Pascal |
assembler |
|||
|
1 |
tol := 10-6 x := 2 |
mov dword ptr [bp-4],large 0358637BDh |
1 |
2 |
|
mov |
1 |
|||
|
2 |
x1 := x; |
mov eax,dword ptr [bp+6] |
1 |
54 |
|
|
mov dword ptr [bp-8],eax |
1 |
||
|
fx := x*x-2 |
fld dword ptr [bp+6] |
3 |
||
|
|
fmul dword ptr [bp+6] |
11 |
||
|
|
fsub dword ptr DGROUP:s@ |
7 |
||
|
|
fstp dword ptr [si] |
7 |
||
|
dfx := 2*x |
fld dword ptr [bp+6] |
3 |
||
|
|
fmul dword ptr DGROUP:s@ |
11 |
||
|
|
fstp dword ptr [di] |
7 |
||
|
|
fwait |
3 |
||
|
3 |
if (abs(dfx) < tol) |
fld dword ptr [bp-16] |
3 |
49 |
|
|
sub sp,8 |
1 |
||
|
|
fstp qword ptr [bp-40] |
8 |
||
|
|
fwait |
3 |
||
|
|
call far ptr _fabs |
17 |
||
|
|
add sp,8 |
1 |
||
|
|
fcomp dword ptr [bp-4] |
4 |
||
|
|
fstsw word ptr [bp-22] |
3 |
||
|
|
fwait |
3 |
||
|
|
mov ax,word ptr [bp-22] |
1 |
||
|
|
sahf |
2 |
||
|
|
jae short @2@170 |
3 |
||
|
4 |
if (dfx >= 0) |
fld dword ptr [bp-16] |
3 |
24 |
|
|
fldz |
4 |
||
|
|
fcompp |
5 |
||
|
|
fstsw word ptr [bp-22] |
3 |
||
|
|
fwait |
3 |
||
|
|
mov ax,word ptr [bp-22] |
1 |
||
|
|
sahf |
2 |
||
|
|
ja short @2@142 |
3 |
||
|
5 |
dfx := tol |
mov eax,dword ptr [bp-4] |
1 |
5 |
|
|
mov dword ptr [bp-16],eax |
1 |
||
|
|
jmp short @2@170 |
3 |
||
|
6 |
dfx := -tol |
fld dword ptr [bp-4] |
3 |
19 |
|
|
fchs |
6 |
||
|
|
fstp dword ptr [bp-16] |
7 |
||
|
|
fwait |
3 |
||
|
7 |
dx := fx/dfx |
fld dword ptr [bp-12] |
3 |
100 |
|
|
fdiv dword ptr [bp-16] |
73 |
||
|
|
fstp dword ptr [bp-20] |
7 |
||
|
x := x1 - dx |
fld dword ptr [bp-8] |
3 |
||
|
|
fsub dword ptr [bp-20] |
7 |
||
|
|
fstp dword ptr [bp+6] |
7 |
||
|
8 |
abs(dx)<=abs(tol*x) |
fld dword ptr [bp-20] |
3 |
109 |
|
|
sub sp,8 |
1 |
||
|
|
fstp qword ptr [bp-40] |
8 |
||
|
|
fwait |
3 |
||
|
|
call far ptr _fabs |
17 |
||
|
|
add sp,8 |
1 |
||
|
|
fstp tbyte ptr [bp-32] |
6 |
||
|
|
fld dword ptr [bp-4] |
3 |
||
|
|
fmul dword ptr [bp+6] |
11 |
||
|
|
sub sp,8 |
1 |
||
|
|
fstp qword ptr [bp-40] |
8 |
||
|
|
fwait |
3 |
||
|
|
call far ptr _fabs |
17 |
||
|
|
add sp,8 |
1 |
||
|
|
fld tbyte ptr [bp-32] |
6 |
||
|
|
fcompp |
5 |
||
|
|
fstsw word ptr [bp-22] |
3 |
||
|
|
fwait |
3 |
||
|
|
mov ax,word ptr [bp-22] |
1 |
||
|
|
sahf |
2 |
||
|
|
jbe short @@1 |
3 |
||
|
|
jmp @2@58 |
3 |
||
Текст программы с контрольными точками
uses sampler;
const PName : string[10] = 'Newton.pas';
var x_input : real;
alldone : boolean;
procedure newton(var x_input: real);
var fx,dfx,dx,tol,x,x1,x2 : real;
i : longint;
begin { newton }
for i:=1 to 1000 do
begin
Sample(PName,1);
Sample(PName,2);
x:=x_input;
tol:=1.0E-6;
repeat
Sample(PName,3);
x1:=x;
fx:=x*x-2.0;
dfx:=2.0*x;
Sample(PName,4);
if(abs(dfx)<tol)
then begin
Sample(PName,5);
if(dfx>=0.0)
then begin
Sample(PName,6);
dfx:=tol;
Sample(PName,7);
end
else begin
Sample(PName,8);
dfx := -tol;
Sample(PName,9);
end;
Sample(PName,10);
end;
Sample(PName,11);
dx:=fx/dfx;
x:=x1-dx;
{writeln('x=',x1,',fx=',fx,',dfx=',dfx);}
Sample(PName,12);
until abs(dx)<=abs(tol*x);
Sample(PName,13);
end;{for}
x_input:=x;
end; { newton }
begin { main program }
alldone:=false;
repeat
writeln;
write('First guess (999. to exit): '); { first guess }
readln(x_input);
if x_input=999. then alldone:=true
else
begin
newton(x_input);
writeln;
writeln('The solution is ',x_input);
writeln;
end
until alldone
end.
Таблица 3. Результаты измерений при выполнении программы 1000 раз для x=10-7
----------------------------------------------------------------------
Исх.Поз. Прием.Поз. Общее время(мкс) Кол-во прох. Среднее время(мкс)
----------------------------------------------------------------------
1 : 1 1 : 2 31.36 1000 0.03
----------------------------------------------------------------------
1 : 2 1 : 3 51.47 1000 0.05
----------------------------------------------------------------------
1 : 3 1 : 4 16950.94 26000 0.65
----------------------------------------------------------------------
1 : 4 1 : 5 135.20 1000 0.14
1 : 4 1 : 11 2961.54 25000 0.12
----------------------------------------------------------------------
1 : 5 1 : 6 151.97 1000 0.15
----------------------------------------------------------------------
1 : 6 1 : 7 28.78 1000 0.03
----------------------------------------------------------------------
1 : 7 1 : 10 82.01 1000 0.08
----------------------------------------------------------------------
1 : 10 1 : 11 49.55 1000 0.05
----------------------------------------------------------------------
1 : 11 1 : 12 29273.30 26000 1.13
----------------------------------------------------------------------
1 : 12 1 : 3 8213.25 25000 0.33
1 : 12 1 : 13 340.54 1000 0.34
----------------------------------------------------------------------
1 : 13 1 : 1 56.18 999 0.06
----------------------------------------------------------------------
Измерения проведены с помощью монитора Sampler версии 1999.
Режим измерения времени: счетчик TSC.
Время коррекции: 568 минитиков.
Таблица 4. Измерение времени выполнения фрагментов программы в мкс
(указаны средние значения при выполнении программы 1000 раз)
|
№ вершины |
Входное значение x |
|||||
|
2 |
3 |
-10-7 |
10-7 |
-10-7 |
10-7 |
|
|
1 |
0,08 |
0,06 |
0,05 |
0,05 |
0,07 |
0,09 |
|
2 |
0,70 |
0,65 |
0,64 |
0,65 |
0,69 |
0,66 |
|
3 |
0,11 |
0,11 |
0,12 |
0,12 |
0,12 |
0,11 |
|
4 |
- |
- |
0,19 |
0,15 |
0,13 |
0,12 |
|
5 |
- |
- |
- |
0,03 |
- |
0,04 |
|
6 |
- |
- |
0,04 |
- |
0,06 |
- |
|
7 |
1,05 |
1,13 |
1,10 |
1,13 |
1,12 |
1,12 |
|
8 |
0,32 |
0,32 |
0,36 |
0,33 |
0,37 |
0,35 |
Таблица 5. Оценка времени выполнения фрагментов программы
|
№ вершины |
Оценка времени выполнения |
|
|
прямым подсчетом в тактах |
измерением в мкс |
|
|
1 |
2 |
0,07 |
|
2 |
54 |
0,67 |
|
3 |
49 |
0,11 |
|
4 |
24 |
0,16 |
|
5 |
5 |
0,04 |
|
6 |
19 |
0,05 |
|
7 |
100 |
1,10 |
|
8 |
109 |
0,35 |
Несоответствия между подсчитанным и измеренным временем выполнения фрагментов программы можно объяснить различием компьютеров, для которых эти оценки производились.
Подсчет для компьютера: i486.
Измерение на компьютере: Celeron 850MHz.
В ОГМ в качестве времени выполнения фрагментов программы использованы оценки, полученные с помощью измерений.