 |
Аналіз алгоритмічних структур. Методи підвищення продуктивності.
|
|
|
|
Аналіз алгоритмічних структур. Методи підвищення продуктивності.
Типи алгоритмічних структур:
1. Послідовна
2. Послідовно-групова
3. Сильно пов’язані алгоритмічні структури
4. Слабо пов’язані алгоритмічні структури
5. Паралельні структури загального типу
Загальною характеристикою наведених структур є покажчик готовності операндів до включення в операцію. Цей покажчик формується відповідно до попереднього кроку виконання, тобто є результатом. У послідовних алгоритмічних структурах кожна операція перетворює один чи два операнди, які були сформовані попередньою операцією – покажчик готовності 1. В послідовно групових алгоритмічних структурах є вершини які мають однакові покажчики готовності(Q) і однаковий час виконання(T), тому тут можливе прискорення виконання групових операцій. Для сильно пов’язаних алгоритмічних структур покажчики готовності можуть бути більше одиниці і при аналізі {T, Q} можна визначити оператори які можуть бути виконання одночасно. Для слабо пов’язаних алгоритмічних структур Q> > 1. У паралельних структурах загального типу гілки алгоритму не перетинаються Q> > > 1 і можливе виконання паралельних гілок.
14. 10. 11
Аналіз алгоритмічних структур підтверджує, що залежність по даних та керуванню впливають на рівень продуктивності комп’ютерного середовища.
Іншими чинниками є особливості структури алгоритму та структури реалізації архітектури ЕОМ. Якщо варіанти нових структур з’являлися дуже нові, удосконалення ПЗ в тому числі нових алгоритмів обробки виконувались набагато швидше. Головна мета – розробка таких алгоритмів, які б мали найменшу арифметичну складність(кількість кроків виконання). Розглянемо приклад застосування апарату Фур’є та вдосконалення алгоритмів, які його реалізують. Гармонічний аналіз, який є основою цифрової обробки сигналів та зображень, реалізується за допомогою алгоритму дискретного перетворення Фур’є(ДПФ). Якщо розглядати, що такий алгоритм реалізовано архітектурою фон Неймана, то його складність приблизно n2 (n – кількість відліків сигналу). З операційної точки зору, ДПФ - обчислення операторів суми пар добутків. Якщо машина фон Неймана буде реалізовувати ДПФ, це буде займати багато часу і не буде можливості реалізувати обробку в реальному часі. Швидке перетворення Фур’є (ШПФ), складність якого (log2n), майже 30 років був головним засобом цифрової обробки сигналів. Коли з’явилися паралельні структури ДПФ, було забезпечено складність n*log2(n/2). ШПФ має ітеративний характер і прискорити його неможливо. З цього прикладу виникає теза про, що досягнення нових рівнів продуктивності залежить від відповідності структури алгоритму структурі комп’ютерних засобів. Таке досягнення у пошуку засобів підвищення продуктивності мало приклади при застосуванні принципів спеціалізації в організації обчислювального процесу в багатьох розв’язаннях для прикладних проблем.
|
|
|
Спеціалізація, як форма організації обчислювального процесу.
Кожні комп’ютерні засоби будуються на наступному принципі:
1) Вузькоспеціалізовані засоби
2) Спеціалізовані засоби
3) Проблемно-орієнтовані засоби
4) Універсальні
Принцип спеціалізації є основою побудови не тільки комп’ютерів, а є загальним принципом в машинобудуванні.
Спеціалізація буває двох типів: предметна та технологічна.
Предметна спеціалізація означає, що засоби реалізації та їх організація складає єдине ціле для отримання кінцевого продукту, при цьому зв’язки між складовими частинами та набір складових частин є постійними. Прикладом може бути промисловий конвеєр: на вході є напівфабрикати, на виході – готовий продукт.
|
|
|
Технологічна спеціалізація передбачає набір необхідних операцій, порядок застосування яких є гнучким. Загальний принцип спеціалізації передбачає, що, якщо можливий розподіл фази виконання обробки, як складові, то така організація забезпечується структурною підтримкою і вважається найбільш продуктивною. Розглянемо модель виконання команди, яка розподілена на складові:
1) Зчитування команди.
2) Дешифрація типу.
3) Визначення першого операнду.
4) Визначення другого операнду.
5) Виконання команди.
6) Запис результату.
7) Визначення адресси наступної команди.
Якщо розглядати в цілому, то маємо 7 окремих ланок виконання, кожна з яких може бути підтримана апаратно. Фаза виконання команди спеціалізується на 7 етапів, і якщо ми хочемо підвищити продуктивність, то такі апаратні слоти мають працювати безперервно – вже на другому етапі виконання маємо можливість реалізувати обробку іншої команди. На виході спеціалізованого вузла в кожному такті його роботи маємо результат і маємо підвищення продуктивності комп. засоба в цілому. Кожен спеціалізований вузол працює швидше, ніж універсальний, за рахунок виключення загальної структури рішень та зайвих комутацій; також можлива відсутність слотів по дешифрації та налагодження функції виконання, всі функції виконання визначаються апріорі. Керування процесом перетворення тільки апаратне.
Слід зазначити - спеціалізовані структури завжди поступаються універсальним по типам обробки. Аналіз нових структурних розв’язань в сучасних комп’ютерах підтверджує тезу про те, що спеціалізація застосовується на більш доступних рівнях в організації обчислювального процесу. Спеціалізація охоплює не тільки структуру рішення, а й всі доступні рівні, де є теорія, методи та засоби застосування спеціалізованих рішень. Якщо виконуються тільки операції множення, то така форма є найбільш продуктивною. Теорія алгоритмів передбачає отримання значень алгоритму над початковими та вихідними даними. У комп’ютерних засобах є перетворення форми сигналу, які передбачають логарифмічний вихід. Тобто ЦАП має декілька виходів: двійкові дання, логарифмічні данні. Так само розробляються спеціальні системи числення, які забезпечують розв’язвння проблем захисту інформації, асоціативно-пошукових операцій, спеціальної форми відображення та ін. Якщо дослідити еволюцію машини фон Неймана, яка мала 5 основних блоків, то вже наступним кроком реалізації спеціалізації була поява в арифметичному пристрої своєї памяті, пристроїв адрес, які сформували структуру процесора сучасних комп’ютерів. Тому до 3 чинників, які впливають на продуктивність, треба додати ступінь спеціалізації архітектури.
|
|
|
|
|
|
