ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2347
Скачиваний: 1
46
алгоритмами і відмінність в часах виконання елементарних операцій на
реальному процесорі.
Таким чином, виникає задача переходу від функції трудомісткості до
оцінки часу роботи алгоритму на конкретному процесорі:
Дано: F
A
(D
A
) –
трудомісткість алгоритму. Потрібно визначити час
роботи програмної реалізації алгоритму – T
A
(D
A
).
На шляху побудови часових оцінок стикаються з цілим набором різних
проблем, пофакторний облік яких викликає суттєві труднощі.
Зазначимо основні з цих проблем:
•
неадекватність формальної системи запису алгоритму і реальної
системи команд процесора;
•
наявність архітектурних особливостей процесора істотно впливають на
час виконання програми, таких як конвеєр, кешування пам'яті,
предвибірки команд і даних тощо;
•
різні часи виконання реальних машинних команд;
•
відмінність у часі виконання однієї команди, залежно від значень
операндів;
•
різні часи реального виконання однорідних команд в залежності від
типів даних;
•
неоднозначності компіляції вхідного тексту, зумовлені як компілятором,
так і його налаштуванням.
Спроби різного підходу до обліку цих факторів призвели до появи
різноманітних методик переходу до тимчасових оцінками.
1)
Поопераційний аналіз
Ідея поопераційного аналізу полягає в отриманні поопераційної функції
трудомісткості для кожної з використовуваних алгоритмом елементарних
операцій з урахуванням типів даних.
Наступним кроком є експериментальне визначення середнього часу
виконання цієї елементарної операції на конкретній обчислювальній машині.
Очікуваний час виконання розраховується як сума добутків поопераційної
трудомісткості на середні часи операцій:
T
A
(N) =
∑
F
А опер
(N) *
t
опер
,
де
t
опер
–
час виконання елементарної операції.
47
2)
Метод Гіббсона
Метод передбачає проведення сукупного аналізу за трудомісткістю і
перехід до часових оцінок з урахуванням належності розв'язуваної задачі до
одного з наступних типів:
•
задачі
науково-технічного
характеру,
в
яких
переважно
використовуються операції з операндами дійсного типу;
•
задачі дискретної математики з переважанням операцій з операндами
цілого типу;
•
задачі баз даних з переважанням операцій з операндами рядкового
типу.
Далі на основі аналізу великої кількості реальних програм для
вирішення відповідних типів задач визначається частотна використання
операцій (рис 5.1). Створюються відповідні тестові програми, і визначається
середній час на операцію в даному типі задач –t
тип задачі
.
Рис 5.1. Можливий вид частоти використання операцій
На основі отриманої інформації оцінюється загальний час роботи
алгоритму у виді:
T
A
(N) = F
A
(N) *
t
тип задачи
3) Метод прямого визначення середнього часу
У цьому методі так само проводиться сукупний аналіз за трудомісткістю
–
визначається F
A
(N)
. Після цього на основі прямого експерименту для
різних значень N
е
визначається середній час роботи даної програми T
е
і за
допомогою відомої функції трудомісткості розраховується середній час на
+
/
-
div
*
mod
P
48
узагальнену елементарну операцію, що породжується даним алгоритмом,
компілятором і комп'ютером –
t
а
.
Ці дані можна (у припущенні про стійкість середнього часу по N)
інтерполювати або екстраполювати на інші значення розмірності задачі таким
чином:
t
а
= T
э
(N
э
) / F
A
(N
А
), T(N) =
t
а
* F
A
(N).
5.4 Приклад поопераційного часового аналізу
У ряді випадків саме поопераційний аналіз дозволяє виявити особливі
аспекти раціонального застосування того чи іншого алгоритму розв'язання
задачі.
Як приклад розглянемо задачу множення двох комплексних чисел:
(a+bi)*(c+di)=(ac – bd) + i(ad + bc)=e + if
1.
Алгоритм А1 (пряме обчислення e, f – чотири множення)
MultComplex1 (a, b, c, d; e, f)
e
←
a*c – b*d
ƒ←
a*d + b*c
Return (e,
ƒ
)
End.
2.
Алгоритм А2 (обчислення e, f за три множення)
MultComplex2 (a, b, c, d; e, f)
z1
←
c*(a + b)
z2
←
b*(d + c)
z3
←
a*(d – c)
e
←
z1 – z2
ƒ←
z1 + z3
Return (e,
ƒ
)
End.
ƒ
*
=4 операцій
ƒ
±
=2 операцій
ƒ
←
=2 операцій
ƒ
A1
=8 операцій
ƒ
*
=3 операцій
ƒ
±
=5 операцій
ƒ
←
=5 операцій
ƒ
A2
=13 операцій
49
Поопераційний аналіз цих двох алгоритмів не є важким (його результати
наведені праворуч від запису відповідних алгоритмів).
За сукупною кількістю елементарних операцій алгоритм А2
поступається алгоритму А1, проте в реальних комп'ютерах операція
множення вимагає більшого часу, ніж операція додавання.
Чи можна шляхом поопераційного аналізу відповісти на питання: за яких
умов алгоритм А2 переважніше алгоритму А1?
Введемо параметри q і r, що встановлюють співвідношення між часом
виконання операції множення, додавання і присвоювання для операндів
дійсного типу.
Тоді можна привести часові оцінки двох алгоритмів за часом виконання
операції складання/віднімання – t +:
t
*
= q*t
+
, q>1;
t
←
=r*t
+
, r<1.
Тоді приведені до t
+
часові оцінки мають вид:
Т
A1
= 4*q*t
+
+2*t
+
+2*r*t
+
=t
+
*(4*q+2+2*r);
Т
A2
= 3*q*t
+
+5*t
+
+5*r*t
+
=t
+
*(3*q+5+5*r).
Рівняння часів буде досягнуто при умові:
4*q+2+2*r = 3*q+5+5*r,
звідси:
q = 3 + 3*r
і відповідно при q > 3 + 3*r алгоритм А2 буде працювати більш ефективно.
Таким чином, якщо середовище реалізації алгоритмів А1 і А2 – мова
програмування, обслуговуючий його компілятор і комп'ютер, на якому
реалізується завдання, є такими, що час виконання операції множення двох
дійсних чисел більш ніж втричі перевищує час складання двох дійсних чисел,
(в припущенні, що r <<1, а це реальне співвідношення), то для реалізації
більш кращий алгоритм А2.
Звичайно, виграш у часі дуже малий, якщо ми перемножуємо тільки два
комплексних числа, проте, якщо цей алгоритм є частиною складної
50
обчислювальної задачі з комплексними числами, що вимагає суттєво
значимого за часом кількості множень, то виграш у часі може бути відчутний.
Оцінка такого виграшу на одне множення комплексних чисел випливає з
щойно проведеного аналізу:
∆ T = (q – 3 – 3 * r) * t +
5.5
Питання для самоконтролю
1)
Елементарні операції в псевдомові високого рівня.
2)
Аналіз трудомісткості основних алгоритмічних конструкцій.
3)
Побудова функції трудомісткості для підсумовування матриці.
4)
Побудова функції трудомісткості для задачі пошуку максимуму.
5)
Проблеми при переході від трудомісткості до часових оцінками.
6)
Методики переходу від функції трудомісткості до часових оцінок.
7) Можливості поопераційного аналізу алгоритмів на прикладі задачі
множення комплексних чисел.