Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Організація паралельних обчислень
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2007
Тип роботи:
Навчальний посібник
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Організація паралельних обчислень
Навчальний посібник
з дисципліни “Паралельні та розподілені обчислення”
для студентів базового напряму 6.0915 - “Комп’ютерна інженерія”
Затверджено на засіданні кафедри ”Електронні обчислювальні машини” Протокол № 8 від07.02.2007 року
Львів - 2007
Організація паралельних обчислень :
Навчальний посібник з дисципліни “Паралельні та розподілені обчислення” для студентів базового напрямку 6.0915 "Комп'ютерна інженерія" / Укладачі: Є. Ваврук, О. Лашко – Львів: Національний університет “Львівська політехніка”, 2007, 83 с.
Укладачі: Є. Ваврук, к.т.н., доцент
О. Лашко, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
Рецензенти: Дунець Р.Б., д. т. н, доцент
Галембо В.А., к. т. н, доцент
Анотація
Даний навчальний посібник укладений відповідно до навчальної програми з дисципліни "Паралельні та розподілені обчислення". В ньому розглянуті основні питання організації паралельних обчислень, вивчення яких допоможе студенту базового напряму 6.0915 - “Комп’ютерна інженерія” здобути початкові навички аналізу і проектування паралельних алгоритмів та структур.
ЗМІСТ
Вступ
6
Тема 1: Основні поняття про паралельні обчислення
7
1. Поняття про паралельні та розподілені обчислення
7
2. Області застосування і задачі паралельної обробки
7
3. Конвеєризація і паралелізм
8
4. Засоби для проведення паралельних обчислень
8
5. Рівні розпаралелення
8
6. Паралельні операції
10
7. Основні принципи паралелізму (розпаралелення)
11
8. Класифікація структур паралельної обробки
12
Вправи і завдання до теми №1
15
Додаток А до теми №1. Класифікація М. Флінна
16
Додаток Б до теми №1. Паралельні обчислювальні системи в класифікації Базу
16
Тема 2: Методи оцінки продуктивності паралельних алгоритмів і систем
17
1. Загальні зауваження стосовно оцінки продуктивності паралельних алгоритмів та систем
17
2. Фактори, які необхідно враховувати при оцінці продуктивності
19
3. Методи оцінки продуктивності паралельних систем
19
4. Характеристики продуктивності паралельних алгоритмів
20
5. Порівняння MIMD i SIMD структур за продуктивністю
23
Вправи і завдання до теми №2
26
Додаток до теми №2. Характеристики базових тестів
27
Тема 3: Організація мереж Петрі
30
1. Поняття про мережі Петрі
30
2. Прості мережі Петрі
30
3. Розширені мережі Петрі
33
4. Приклади реалізації мереж Петрі
34
Вправи і завдання до теми №3
37
Тема 4: Розробка паралельного алгоритму
38
1. Паралелізм даних
38
2. Паралелізм задач
38
3. Етапи розробки паралельного алгоритму:
39
- декомпозиція
40
- планування комунікацій
41
- укрупнення
42
- планування обчислень
43
Вправи і завдання до теми №4
43
Тема 5: Структури зв’язку між процесорами
44
1. Основні положення
44
2. Шинні сітки
44
3. Сітки з комутаторами
45
4. Структури, що забезпечують зв’язок типу “пункт-пункт
48
5. Методи комутацій
52
Вправи і завдання до теми №5
53
Тема 6: Основні класи паралельних комп’ютерів
54
Вступ
54
1. Масивно-паралельні системи (МРР)
54
2. Симетричні мультипроцесорні системи (SMP)
54
3. Системи з неоднорідним доступом до пам’яті (NUMA)
55
4. Паралельні векторні процесори (PVP)
59
5. Кластерні системи
57
Вправи і завдання до теми №6
57
Тема 7: Схеми паралельних алгоритмів задач
58
1. Класи алгоритмів задач
58
2. Алгоритми перемноження матриці на матрицю і їх реалізація на структурах типу: кільцева, 2D, 3D
59
Вправи і завдання до теми №7
63
Додаток до теми №7. Задача Діріхле. Явна різницева схема для рівняння Пуасона
63
Тема 8: Мови паралельного програмування
68
1. Загальні зауваження
68
2. Класифікація мов і систем паралельного програмування
68
3. Особливості організації паралельної програми
69
4. Технології паралельного програмування Message Passing Interface (MPI)
71
5. Операції обміну повідомленнями
71
Вправи і завдання до теми №8
73
Висновки
74
Література
75
Додатки
Додаток А. Ресурси Інтернет стосовно паралельних обчислень
76
Додаток Б. Концепції паралельної обробки
76
Додаток В. Проблеми асинхронної паралельності
79
Додаток Г. Проблеми синхронної паралельності
83
ВСТУП
Для розв’язання багатьох задач (прогноз погоди, задачі гідро- і газодинаміки, квантової хімії, астрономії, спектроскопії, біології, ядерної фізики) необхідна висока продуктивність та висока швидкість передачі інформації по каналах зв’язку, великі об’єми оперативної і постійної пам’яті, які не можуть забезпечити типові обчислювальні засоби. Одним з шляхів забезпечення таких вимог є організація паралельних та розподілених обчислень і відповідних технічних засобів їх реалізації.
Причому, ефективність паралельної обробки залежить як від продуктивності комп’ютерів, так і від розмірів і структури пам’яті, пропускної здатності каналів зв’язку, використаних мов програмування, компіляторів, операційних систем, чисельних методів та інших математичних досліджень. Такий широкий обсяг параметрів вимагає проведення досліджень на різних рівнях: на рівні розпаралелення алгоритмів, створення спеціальних мов програмування, компіляторів, багатопроцесорних систем, неоднорідних систем, кластерів і систем, що розподілені на великих територіях.
Великий спектр задач не дозволяє охопити в навчальному посібнику всі проблеми організації паралельних та розподілених обчислень.
Для тих, хто хоче краще орієнтуватися в перспективних напрямках розвитку обчислювальної техніки і краще розуміти специфіку паралельних та розподілених обчислень радимо, насамперед, скористатись матеріалами сайту www.parallel.ru
Метою вивчення дисципліни є засвоєння основних методів та алгоритмів організації паралельних та розподілених обчислень, принципів побудови відповідних структур, набуття початкових практичних навиків проектування таких засобів.
В результаті вивчення курсу студент повинен знати основні методи, алгоритми і засоби паралельної та розподіленої обробки інформації, засоби програмування на паралельних та розподілених структурах, склад апаратних засобів та програмного забезпечення обчислювальних систем з елементами паралельної та розподіленої обробки і класи мов програмування високого рівня для них; вміти виконувати елементарні вправи з розпаралелення задач та алгоритмів, проводити розрахунки параметрів процесорів, проектувати окремі вузли.
В розділі курсу “Організація паралельних обчислень” розглядаються такі основні питання:
- основні поняття про паралельні обчислення;
- методи оцінки продуктивності паралельних алгоритмів;
- організація мереж Петрі;
- розробка паралельного алгоритму;
- структури зв’язку між процесорами;
- основні класи паралельних комп’ютерів;
- схеми паралельних алгоритмів задач;
- мови паралельного програмування.
Тема №1: Основні поняття про паралельні обчислення
Питання:
Поняття про паралельні та розподілені обчислення
Області застосування і задачі паралельної обробки
Конвеєризація і паралелізм
Засоби для проведення паралельних обчислень
Рівні розпаралелення
Паралельні операції
Основні принципи паралелізму (розпаралелення)
Класифікація структур паралельної обробки
Вправи і завдання до лекції №1
Поняття про паралельні та розподілені обчислення
В залежності від предметної області застосування є багато визначень термінів, які характеризують паралельні та розподілені обчислення. На основі аналізу літературних джерел і варіантів практичної реалізації можна так визначити ці терміни:
Паралельні обчислення – обчислення, що підтримуються на математичному, алгоритмічному, програмному чи апаратному рівні (на всіх або декількох) і забезпечують можливість паралельного виконання задачі.
В [1] під терміном “паралельні обчислення” розуміється сукупність питань, які відносяться до створення ресурсів паралелізму в процесах розв’язання задач і гнучкому керуванню реалізацій цього паралелізму з метою досягнення найбільшої ефективності обчислювальної техніки.
Розподілені обчислення – обчислення, які підтримуються стандартними чи закритими протоколами обміну та незалежними апаратними засобами (комп’ютери, сервери), що представляються користувачу єдиним обчислювачем, придатним для вирішення складної задачі.
Стосовно використаних ресурсів можна стверджувати: здебільшого паралельні структури реалізовуються на спеціалізованих процесорах, розподілені структури – на універсальних (стандартних) комп’ютерах (серверах), які об’єднані в мережі різного типу.
Області застосування і задачі паралельної обробки
Є коло обчислювальних задач, для розв’язку яких необхідні потужніші обчислювальні ресурси, ніж ті, які можуть забезпечити типові комп’ютери чи системи. В таких задачах необхідно забезпечити: надвисоку швидкодію, великий об’єм оперативної пам’яті, велику кількість інформації, що передається, обробку і зберігання великого об’єму інформації. При наявності хоча б однієї з наведених вимог використання паралельної обробки оправдано.
Приклади:
Складні, багатовимірні задачі, які необхідно розв’язати на протязі досить обмеженого часу, вимагають забезпечення надвисокої швидкодії, наприклад - задачі прогнозу погоди. Область розв’язку (атмосфера) розбивається на окремі просторові зони. Причому, для забезпечення прогнозу на певному періоді часу, обчислення в кожній зоні повторюється багато разів. Якщо об’єм зони рівний 1 км3, то для моделювання 10 км атмосфери необхідно 5х108 таких зон. Припустимо, що обчислення в кожній зоні вимагає 200 операцій з рухомою крапкою, тоді за один часовий крок необхідно виконати 1011 операцій з рухомою крапкою. Для того, щоб зпрогнозувати погоду з передбачуванністю 10 днів з 10-ти хвилинним кроком комп’ютеру з продуктивністю 100 Mflops (108 операцій з рухомою крапкою за секунду) необхідно 107 секунд чи понад 100 днів. Для того, щоб провести розрахунок за 10 хв., необхідний комп’ютер продуктивністю 1.7 Tflops (1.7X1012 операцій з рухомою крапкою за секунду).
До категорії задач, що вимагають великого об’єму оперативної пам’яті, відносяться, наприклад, задачі гідро- і газодинаміки з розрахунку течій з врахуванням різних фізичних і хімічних процесів. Такі задачі є, як правило, багатовимірними, і розрахунок по кожному з напрямків вимагає оперативної пам’яті понад 10 Гбайт. В квантовій хімії неемпіричні розрахунки електронної структури молекул вимагають обчислювальних затрат, пропорційних N4 чи N5, де N умовно характеризує кількість молекул.
Вимога забезпечення великої кількості інформації, що передається характерна для задач гідро- і газодинаміки з змінюючими граничними умовами, коли обчислювальний алгоритм постійно вимагає підведення нової інформації, і задач економічної оптимізації, що описують поведінку системи, яка занурена в середовище з неперервно змінюючими властивостями, від яких залежить стан системи.
Проблема обробки і зберігання великого об’єму інформації характерна для задач астрономії, спектроскопії, біології, ядерної фізики.
3. Конвеєризація і паралелізм
Конвеєризація – метод, що забезпечує сукупність різних дій за рахунок їх розбиття на підфункції з зміщенням в часі виконанням. Конвеєрний пристрій розробляють з окремих ступенів, час спрацювання яких в ідеальному випадку повинен бути однаковим.
Паралелізм – метод, що забезпечує виконання різних функцій шляхом їх розбиття на підфункції з одночасним виконанням в часі.
Приклад:
Варіант структурної схем виконання виразу при паралельній обробці наведений на рис.1.1.
4. Засоби для проведення паралельних обчислень
1. Апаратні засоби:
- засоби для проведення обчислень (обчислювальна техніка):
- обчислювальна техніка, зібрана з стандартних комплектуючих;
- обчислювальна техніка, зібрана з спеціальних комплектуючих;
- засоби візуалізації;
- засоби для зберігання і обробки даних.
2. Програмні засоби:
- програмні засоби загального призначення (операційні системи: стандартні бібліотеки, мови програмування, компілятори, профайлери, відлагоджувачі і т.п.);
- спеціальні програмні засоби: бібліотеки (PVM, MPI); засоби об’єднання ресурсів (Dynamite, Globus і ін.)
5. Рівні розпаралелювання
Класифікація паралельності за рівнями, що відрізняються показниками абстрактності розпаралелення задач наведена в табл.1.1. Чим "нижчий" рівень паралельності, тим детальнішим, малоелементнішим буде розпаралелення, що торкається елементів програми (інструкція, елементи інструкції тощо).
Таблиця 1.1 Рівні паралельності
Зернистість
Рівні
Об’єкт обробки
Приклад системи
Великоблокова
Програмний
Робота/Задача
Мультизадачна ОС
Процедурний
Процес
MIMD-система
Дрібноблокова
Рівень формул
Інструкція
SIMD-система
Біт-рівень
В межах інструкції
Машина фон Ноймана
Методи i конструктиви даного рівня обмежуються тільки цим рівнем i не можуть бути поширені на інші рівні.
Програмний рівень
На цьому рівні одночасно (або щонайменше з часовим розподілом) виконуються комплексні програми (рис.1.2). Комп’ютер, що виконує ці програми не обов’язково повинен мати паралельну структуру, достатньо, щоб на ньому була встановлена багатозадачна операційна система (наприклад, реалізована як система розподілу часу). В цій системі кожному користувачеві, відповідно до його пріоритету, планувальник (Scheduler} виділяє відрізок часу різної тривалості. Користувач одержує ресурси центрального процесорного блоку тільки впродовж короткого часу, а потім стає в чергу на обслуговування.
У тому випадку, коли в системі недостатня кількість процесорів для всіх користувачів (або процесів), що, як правило, найбільш імовірно, в системі моделюється паралельне обслуговування користувачів за допомогою "квазіпаралельних" процесів.
Рівень процедур
На цьому рівні різні частини ("процеси") однієї і тієї ж програми виконуються паралельно; кількість операцій обміну даними між процесами повинна бути мінмальною.
Основне застосування процедурного рівня розпаралелення - загальне паралельне оброблення інформації, де застосовується ділення вирішуваної проблеми на паралельні задачі - частини, які вирішуються багатьма процесорами з метою підвищення обчислювальної продуктивності (приклад - рис.1.3.).
Рівень формул (арифметичних виразів)
Арифметичні вирази виконуються паралельно покомпонентно, причому в суттєво простіших синхронних методах. Якщо, наприклад, йдеться про додавання матриць (рис.1.4.), то операція синхронно розпаралелюється просто тому, що на кожному процесорові обчислюється один (чи кілька) елемент матриці.
При застосуванні n*n процесорних елементів можна одержати суму двох матриць розмірністю n*n за час виконання однієї операції додавання (за винятком часу, потрібного на виконання операцій читання та запису даних). Цьому рівню притаманні засоби векторизації так званої паралельності даних. Майже кожному елементу даних тут підпорядковується свій процесор, завдяки чому ті дані, що в машині фон Ноймана були пасивними. перетворюються на “активні обчислювальні пристрої”.
Біт – рівень
На цьому piвні відбувається паралельне виконання бітових операцій в межах одного інформаційного слова (рис.1.5). Паралельність на рівні бітів можна знайти в будь-якому працюючому мікропроцесорі. Наприклад, у 8-розрядному арифметико-логічному пристрої побітова обробка виконується паралельними апаратними засобами.
6. Паралельні операції
Інший вид паралельності виникає з аналізу математичних операцій над окремими елементами даних або над групами даних. Розрізняють скалярні дані, операції над якими виконуються послідовно, i векторні дані, операції над якими виконуються паралельно.
Прості операції над векторами, наприклад додавання двох векторів, можуть виконуватись синхронно i паралельно. У цьому випадку кожному елементу вектора підпорядковується один процесор. При складніших операціях, таких як формування часткових сум, побудова ефективного паралельного алгоритму є складнішою. Розрізняють одномісцеві (монадні) та двомісцеві (діадні) операції, характерні приклади для яких наведено нижче.
Одномісцеві операції
а). Скаляр –> скаляр Послідовне виконання
Приклад 9 >3 "Корінь"
б). Скаляр > вектор Розмноження числової величини
Приклад 9 >(9,9,9,9) "Broadcast"
в). Вектор > скаляр Редукція вектора в скаляр
Приклад (1,2,3,4) >10 "Складання"
(із припущенням, що довжина вектора не змінюється)
г-1) Локальна векторна покомпонентна операція.
Приклад: (1,4,9,16) > (1,2,3,4) "Корінь"
г-2) Глобальна векторна операція з перестановками.
Приклад: (1,2,3,4) > (2,4,3,1) "Заміна місць компонент вектора"
г-3) Глобальна векторна операція (часто складається з простих операцій)
Приклад: (1,2,3,4) > (1,3,6,10) "Часткові суми"
Двомісцеві операції
д) (скаляр, скаляр) > вектор Послідовне виконання
Приклад: (1,2) >3 "Скалярне додавання"
е) (скаляр, вектор) >вектор Покомпонентне застосування операцій над скаляром i вектором
Приклад: (3,(1,2,3,4)) >(4,5,6,7) "Додавання скаляра з вектором"
Операція виконується як послідовність операцій б) та є)
додавання векторів:
(3,3,3,3)
+
(1,2,3,4)
(4,5,6,7)
є) (вектор, вектор) > вектор Покомпонентне застосування операції над двома векторами
Приклад: ((1,2,3,4),(0,1,,3,2)) > (1,3,6,6) "Додавання векторів"
7. Основні принципи паралелізму (розпаралелення)
Розпаралелити кожну задачу можна не єдиним способом. Тому доцільно розглянути алгоритми можливого розпаралелення типових задач незалежно від конкретної програмної і платформенної реалізації. В загальному випадку процедура розпаралелення розіб’ється на 3 етапи:
- розбиття задачі на незалежні під задачі;
- призначення конкретних процесорів для виконання кожної під задачі;
- збирання результатів роботи окремих процесорів.
8. Класифікація структур паралельної обробки
Є різні системи класифікації паралельних систем, які базуються на різнотипних головних ознаках до класифікації. Багато з них базується на класифікації М. Флінна (1966 р.), де паралельна обробка виконується на SIMD і MIMD архітектурах.
В сучасних класифікаційних системах архітектури, які попадають в один клас, відрізняються за кількістю процесорів, природі і топології зв'язку між ними, за способом організації пам'яті, за технологією програмування та іншими ознаками.
Наприклад, А.Базу (A.Basu) вважає, що будь-яку паралельну обчислювальну систему можна однозначно описати послідовністю рішень, прийнятих на етапі її проектування, а сам процес проектування представити у виді дерева. Класифікація за Базу наведена на рис.1.6.
Рис.1.6. Класифікація за Базу
Р.Дункан визначає такий набір вимог на який може спиратися класифікація (див.рис.1.7):
З класу паралельних машин повинні бути виключені ті, у яких паралелізм закладений лише на найнижчому рівні, включаючи:
- конвеєризацію на етапі підготовки і виконання команди (instruction pipelining), тобто часткове перекриття таких етапів, як дешифрація команди, обчислення адрес операндів, вибірка операндів, виконання команди і збереження результату;
- наявність в архітектурі декількох функціональних пристроїв, що працюють незалежно, зокрема, можливість паралельного виконання логічних і арифметичних операцій;
- наявність окремих процесорів вводу/виводу, що працюють незалежно і паралельно з основними процесорами.
Дункан дає неформальне визначення паралельної архітектури, а саме: паралельна архітектура - це такий спосіб організації обчислювальної системи, при якому допускається, щоб безліч процесорів (простих або складних) може працювати одночасно, взаємодіючи в міру потреби один з одним.
Розглянемо три види архітектур, в яких використовують нетрадиційні моделі обчислень.
Dataflow - використовують модель, у якій команда може виконаються відразу ж, як тільки обчислені необхідні операнди. Таким чином, послідовність виконання команд визначається залежністю за даними, що може бути виражена, наприклад, у формі графа.
Модель обчислень, застосовувана в reduction машинах полягає в наступному: команда стає доступною для виконання тоді і тільки тоді, коли результат її роботи потрібно іншій, доступній для виконання, команді як операнд.
Wavefront array архітектура поєднує в собі ідею систолічної обробки даних і модель обчислень, що використовується в dataflow. У даній архітектурі процесори об’єднуються в модулі і фіксуються зв'язки, по яких процесори можуть взаємодіяти один з одним. Однак, на противагу ритмічній роботі систоличних масивів, дана архітектура використовує асинхронний механізм зв'язку з підтвердженням (handshaking), через що "фронт хвилі" обчислень може змінювати свою форму в міру проходження по всіх процесорах.
Е.Кришнамарфі для класифікації паралельних обчислювальних систем пропонує використовувати чотири характеристики, які подібні до характеристик класифікації А.Базу: ступінь гранулярності, спосіб реалізації паралелізму, топологія і природа зв'язку, спосіб керування процесорами.
На основі виділених чотирьох характеристик можна визначити місце найбільш відомих класів архітектур у даній класифікації (див. табл.1.2).
Таблиця 1.2
Тип архітектури
Гранулярність
Реалізація паралелізму
Зв'язок процесорів
Спосіб керування
Векторно-конвеєрні комп'ютери
На рівні даних
Апаратна
Проста топологія із середньою зв’язністю
Синхронний
Класичні мультипроцесори
На рівні задач
Комбінована
Проста топологія зі слабкою зв’язністю
Асинхронний
Матриці процесорів
На рівні даних
Апаратна
Двовимірні масиви із сильною зв’язністю
Синхронний
Систолічні масиви
На рівні даних
Апаратна
Складна топологія із сильною зв’язністю
Незважаючи на те, що класифікація Е. Кришнамарфі побудована лише на чотирьох ознаках, вона дозволяє виділити і описати такі "нетрадиційні" паралельні системи, як систоличні масиви, машини типу dataflow і wavefront.
Заслуговують на увагу класифікації Хандлера (ерлангерська схема) [8], Р. Хокні [1].
Вправи і завдання до теми №1
Як співвідносяться між собою класифікації Хендлера і Флінна?
Які параметри архітектури паралельного комп’ютера треба знати користувачу для створення ефективних програм? Запропонуйте класифікацію комп’ютерів, яка спирається на виділені параметри.
Чи можна організувати паралельні обчислення для розв’язання задачі знаходження найменшого числа з трьох чисел?, з чотирьох чисел? Якщо можна, то яким чином?
Наведіть приклад застосування паралельного опрацювання для будь-якої галузі науки і техніки. Які з вимог паралельної обробки там використовуються?
Чи є принтер засобом для організації паралельної обробки?
Необхідно перемножити матрицю А (n1*n2) на матрицю В (n2*n3). Розробіть функціональну схему пристрою, який забезпечить найшвидше виконання даної операції.
Чому в конвеєрних пристроях тривалість спрацювань окремих ступенів роблять однаковими?
Один робітник може вирити яму розміром 1х1х1 м3 за годину. За скільки часу бригада з 5, 10, 20 робітників вириють яму розміром 2х2 м2 і глибиною 1м, якщо продуктивність всіх робітників однакова?
Побудуйте графік залежності виконання роботи від кількості робітників в бригаді.
Тема №2 “Методи оцінки продуктивності паралельних алгоритмів і систем”
Питання:
Загальні зауваження стосовно оцінки продуктивності паралельних систем
Фактори, що необхідно враховувати при оцінці продуктивності
Методи оцінки продуктивності паралельних систем
4. Характеристики продуктивності паралельних алгоритмів
5. Порівняння MIMD i SIMD структур за продуктивністю
Вправи і завдання до лекції №2
1. Загальні зауваження стосовно оцінки продуктивності паралельних систем
Паралельні системи характеризуються: різноплановістю задач, типом опрацювання (векторне, скалярне), різними операційними системами, різними конфігураціями систем, одночасністю виконання операцій, складністю взаємодії між елементами системи, що не дозволяє використовувати стандартні підходи до визначення їх продуктивності.
А продуктивність окремого процесора залежить від: частоти синхронізації, середньої кількості тактів на команду, кількості команд, що виконується.
Тому час виконання деякої програми в процесорі може бути виражений двома способами: кількістю тактів синхронізації для даної програми, які перемножуються на тривалість такту синхронізації, або кількістю тактів синхронізації для даної програми поділеними на частоту синхронізації.
В процесі пошуку стандартної одиниці вимірювання продуктивності комп’ютерів було прийнято декілька популярних одиниць вимірювання, а для оцінки продуктивності паралельних вузлів деякі терміни були штучно вирвані з їх контексту і використані там, для чого вони ніколи не призначалися. Насправді єдиною і надійною одиницею вимірювання продуктивності є час виконання реальних програм, і всі пропоновані заміни цього часу як одиниці вимірювання або заміни реальних програм як об’єктів вимірювання на синтетичні програми тільки вводять в оману.
Небезпеки використання популярних альтернативних одиниць вимірювання (MIPS і MFLOPS) для оцінки продуктивності паралельних систем.
MIPS . Один з способів вимірювання продуктивності процесора (по відношенню до часу виконання) є MIPS (мільйон команд за секунду). Термін має декілька різних варіантів інтерпретації визначення.
Визначення 1. MIPS - швидкість виконання операцій за одиницю часу, тобто для будь-якої програми, MIPS це - відношення кількості команд в програмі до часу її виконання.
Позитивний бік – наглядність.
Проблеми:
MIPS залежить від набору команд процесора, що затруднює порівняння за показниками MIPS комп’ютерів, що мають різні системи команд.
MIPS навіть на тому ж комп’ютері змінюється від програми до програми.
MIPS може змінюватися по відношенню до продуктивності в протилежний бік (при більшому значенні MIPS реальна продуктивність менша).
Приклад для останнього випадку.
До складу комп’ютера входить співпроцесор з рухомою крапкою. На виконання кожної команди з рухомою крапкою потрібна більша кількість тактів синхронізації, ніж на виконання цілочисельної команди. Програми, що працюють в структурі з співпроцесором з рухомою крапкою виконуються за менший час, але мають менший рейтинг MIPS. За відсутності співпроцесора, операції над числами з рухомою крапкою реалізуються за допомогою підпрограм, що використовують простіші команди цілочисельної арифметики. Як наслідок, такі машини мають більш високий рейтинг MIPS, але виконують більшу кількість команд, що приводить до збільшення часу виконання програми.
Визначення 2 пов'язане з дуже популярним колись комп'ютером VAX 11/780 компанії DEC. Саме цей комп'ютер був прийнятий як еталон для порівняння продуктивності різних машин. Вважалося, що продуктивність VAX 11/780 рівна 1 MIPS (один мільйон команд за секунду) при використанні синтетичного тесту Dhrystone (в даний час практично не використовується), який дозволяв оцінювати ефективність процесорів і компіляторів з мови С для програм нечислової обробки. Він був тестовою сумішшю, 53% якої складали оператори присвоєння, 32% - оператори управління і 15% - виклики функцій. Це був дуже короткий тест: загальна кількість команд дорівнювала 100. Швидкість виконання програми з цих 100 команд вимірювалася в Dhrystone в секунду. Швидкодія VAX 11/780 на цьому синтетичному тесті складала 1757Dhrystone в секунду. Таким чином 1MIPS рівний 1757 Dhrystone в секунду.
Визначення 3 пов’язане з IBM RS/6000 MIPS. Це пояснюється тим, що ряд виробників і користувачів (послідовників фірми IBM) віддають перевагу порівнянням продуктивності своїх комп’ютерів з продуктивністю комп’ютерів IBM, а не із старою машиною компанії DEC. Співвідношення між VAX MIPS і RS/6000 MIPS ніколи широко не публікувалися, але 1 RS/6000 MIPS приблизно рівний 1.6 VAX 11/780 MIPS.
MFLOPS - мільйон операцій з рухомою крапкою за секунду. Як одиниця вимірювання, MFLOPS, призначена для оцінки продуктивності тільки операцій з рухомою крапкою, і тому не застосовується поза цією обмеженою областю.
Наприклад, програми компіляторів мають рейтинг MFLOPS близький до нуля не залежно від того, наскільки швидка машина, оскільки компілятори рідко використовують арифметику з рухомою крапкою.
Зрозуміло, що рейтинг MFLOPS залежить і від характеристик машини і від програми, і є більш об’єктивнішим ніж параметр MIPS. Він базується на кількості виконаних операцій, а не на кількості виконаних команд. На думку багатьох програмістів, одна і та ж програма, що працює на різних комп'ютерах, буде виконувати різну кількість команд, але одну і ту ж кількість операцій з рухомою крапкою. Саме тому рейтинг MFLOPS призначався для справедливого порівняння різних машин між собою.
Проте і з MFLOPS не все йде так безхмарно. Перш за все, це пов'язане з тим, що набори операцій з рухомою точкою не сумісні на різних комп'ютерах. Наприклад, в суперкомп'ютерах фірми Cray Research відсутня команда ділення (є, правда, операція обчислення оберненої величини числа з рухомою крапкою, а операція ділення може бути реалізована за допомогою множення діленого на зворотну величину дільника). В той же час сучасні мікропроцесори мають команди ділення, обчислення квадратного кореня, синуса і косинуса, тощо.
Інша проблема полягає в тому, що рейтинг MFLOPS міняється не тільки на суміші цілочисельних операцій і операцій з рухомою крапкою, але і на суміші швидких і повільних операцій з рухомою крапкою. Наприклад, програма з 100% операцій додавання матиме вищий рейтинг, ніж програма з 100% операцій ділення.
Для усунення цих недоліків використовується "нормалізоване" число операцій з рухомою крапкою, за тестовим пакетом "Ліверморські цикли" (див. табл.2.1.).
Таблиця 2.1. Співвідношення між реальними і нормалізованими операціями з рухомою крапкою
Реальні операції з рухомою крапкою
Нормалізовані операції з рухомою крапкою
“(” “(” “х” “порівняння”
1
“ділення” “(”
4
“exp” “sin”
8
Поява векторних і паралельних машин, не зменшила важливості Ліверморських циклів, проте змінилися значення продуктивності і величини розкиду між різними циклами. На векторній машині продуктивність залежить не тільки від елементної бази, але і від характеру самого алгоритму, тобто коефіцієнта векторизації. Серед Ліверморських циклів коефіцієнт векторизації коливається від 0 до 100%, що ще раз підтверджує їх цінність для оцінки продуктивності векторних архітектури. На коефіцієнт векторизації впливає і якість векторизатора, вбудованого в компілятор.
На паралельній машині продуктивність істотно залежить від відповідності між структурою апаратних засобів і структурою обчислень в алгоритмі. Важливо, щоб тестовий пакет представляв алгоритми різних структур. Тому в Ліверморських циклах зустрічаються послідовні, сіткові, конвеєрні, хвильові обчислювальні алгоритми, що підтверджує їх придатність і для паралельних машин. Проте узагальнення результатів вимірювання продуктивності, отриманої для однієї паралельної машини, на інші паралельні машини або хоча б деякий підклас паралельних машин, може дати неправильний результат, - структури апаратних зв'язків в таких машинах набагато більш різноманітніші, ніж, скажімо, у векторних машинах.
2. Фактори, що необхідно враховувати при оцінці продуктивності
При оцінці продуктивності необхідно враховувати: тип алгоритму, тип програмного забезпечення, протокол каналів передач, структуру окремого процесора.
Тип алгоритму. Алгоритм, що ідеально пристосований для роботи на одній архітектурі, на іншій (з цією ж кількістю процесорів) може працювати набагато гірше. Для масивно-паралельних систем необхідний масштабований алгоритм (для “оптимального” завантаження всіх процесорів). Виграш дає оптимальне поєднання “структура - алгоритм”. Тобто, на паралельній машині продуктивність залежить від відповідності між структурою апаратних елементів і структурою обчислень в алгоритмі. Не можна переносити результат з однієї на іншу систему.
Тип програмного забезпечення. Програмне забезпечення (ПЗ) паралельних структур має певні особливості, а саме: вартість програм є високою, при перенесенні програми з однієї машини на іншу необхідна доробка програми, всі системи відлагодження програми впливають на її поведінку (наприклад, покрокове відлагодження для паралельних систем неефективне). Крім того, програмісту важко навчитися мислити паралельними категоріями.
До складу ПЗ необхідно включати процедури маршрутизації. Для оцінки продуктивності розподіленої системи необхідно знати: топологію зв’язків, швидкість виконання арифметичних операцій, час ініціалізації каналу зв’язку, час передачі одиниці інформації.
Крім того, потрібно пам’ятати, що ріст продуктивності процесорів випереджає ріст швидкості комутаційних каналів.
Протокол каналів передачі. Для паралельних машин доцільно визначити бібліотеку передачі повідомлень, яка враховує особливості машини. В 1994 році прийнятий стандартний інтерфейс передачі повідомлень МРІ (Message Passing Interface Standart) – процедурний інтерфейс для мов С і Fortran). Інтерфейс визначає всі функції, необхідні для передачі повідомлень “точка-точка”. Для колективних повідомлень вводяться поняття групи процесорів (з якими можна оперувати як з кінцевими множинами), комунікатора (реалізують контекст для передачі повідомлень). Забезпечує трансляцію повідомлень з форми одного процесора у вид, який необхідний іншому процесорові. Не вирішена проблема динамічного балансування.
3. Методи оцінки продуктивності паралельних систем
Розрізняють такі методи оцінки паралельних систем: метод обчислення продуктивності складових частин, метод експертних оцінок, розрахунковий метод, практичний метод.
Метод обчислення продуктивності складових частин. Для паралельних систем неефективний.
Метод експертних оцінок. Найскладніший і найзаперечливіший з усіх методів. Розроблений консорціумом стандартизації методів всесторонніх оцінок системи (PC Bench Concortium). Особлива увага приділена апаратному підходу (стараються наслідувати ідеалізовану тестову модель – виключити вплив сторонніх систем, які в даний момент не тестуються).
Використовується дві групи тестів:
синтетичні (вимірюють швидкість роботи і базуються на хронометражі роботи реальних застосувань; легко ізолюють процесор від решти компонентів системи. До реальної задачі можна віднести з натяжкою);
виключно процесорні тести (для процесорів окремо).
Відомі такі тести:
тести SPEC. Базуються на реальних прикладних програмах широкого кола користувачів і забезпечують ефективну оцінку продуктивності процесорів. Основним результатом роботи SPEC є набори тестів, які розробляються з використанням кодів, що надходять з різних джерел.
- тести TPC (TPC-A, ТРС-В,ТРС-С). TPC визначає і керує форматом декількох тестів для оцінки продуктивності OLTP (On-Line Transaction Processing), включаючи тести TPC-A, TPC-B і TPC-C. TPC вимагає, щоб при створенні оцінювального тесту виконувалися визначені умови..
- тести AIM. Компанія розробляє і поставляє програмне забезпечення для виміру продуктивності систем, а також робить послуги по тестуванню систем кінцевим користувачам і постачальникам обчислювальних систем і мереж, що використовують промислові стандартні операційні системи, такі як UNIX і OS/2.
Розрахунковий метод. Базується на обчисленні продуктивності. Є трудомістким і недосконалим.
Практичний метод. Розв’язання конкретної задачі на конкретній структурі. Дає об’єктивну оцінку продуктивності. Недолік – продуктивність можна оцінити тільки після виготовлення системи. При негативному результаті – висока ціна помилки.
Характерні особливості тестів наведені в Додатку до лекції №2.
4. Характеристики продуктивності паралельних алгоритмів.
Характеристиками продуктивності паралельних алгоритмів є: фактор прискорення, максимальне прискорення (закон Амдала), ефективність паралельного алгоритму, ціна, масштабність, загальний час виконання паралельного алгоритму, повний час виконання паралельного алгоритму, теоретичний час комунікацій.
Оцінюючи продуктивність безпосередньо на паралельних системах, відзначають позитивний ефект від розпаралелювання (Speedup- прискорення) і вигоди від збільшення масштабності розв'язаних задач (Scaleup), які можна одержати від працюючої паралельної програми.
Показник Speedup визначає, у скільки разів швидше може бути вирішена одна й та ж задача на N процесорах порівняно з її вирішенням на одному процесорі.
Показник Scaleup визначає, у скільки разів більшу за розмірами проблему можна вирішити за той же час N процесорами порівняно з проблемою, що вирішується одним процесором.
Амдал проаналізував продуктивність паралельних обчислювальних систем і сформулював "закон Амдала", де єдиним параметром є поділ програми на послідовну і паралельну частини; масштаб вирішуваної задачі залишається постійним. Розгляньмо дещо спрощену формулу цього закону.
Фактор прискорення. Прискоренням (speedup factor) паралельного алгоритму в N – процесорній системі називається величина S(N) = Т1/ТN, де
- Т1 – час виконання алгоритму на одному процесорі однопроцесорної системи;
- ТN – час виконання алгоритму на багатопроцесорній системі з N - процесорами.
Закон Амдала. Позначимо:
- Рс- максимальний ступінь розпаралелення (досягається програмою А з моделлю паралельності С): це максимальна кількість процесорів, які можуть бути включені в роботу паралельно в будь-який момент часу в період виконання програми А. Тут вирішальне значення має також застосовувана модель паралельності (наприклад, MIMD або SIMD);
- Tk- тривалість виконання програм А з максимальним показником розпаралелення на системі з k процесорами;
- N - кількість процесорів у паралельній обчислю вальній системі;
- f - послідовна частина програми (у програмі А з моделлю паралельності С); процентна частка операцій, які не можуть бути виконані паралельно на N процесорах, а виконуються тільки послідовно.
У спрощеному розгляді будемо використовувати тільки показники розпаралелення 1 або N. без проміжних значень.
Тривалість виконання програми на паралельній системі з N процесорами оцінюється формулою:
,
звідки дістанемо показник прискорення (Speedup) в системі з N процесорами
.
У зв'язку з тим що 0< f < 1, справедливе таке співвідношення:
,
тобто показник прискорення не може бути більшим ніж кількість процесорів N.
Як міра досягнутого прискорення, відносно максимального визначається ефективність системи з N процесорами
Область межі ефективності :
На практиці використовують значення у відсотках. При = 0,9. наприклад, могла б бути досягнута ефективність, що дорівнює 90% максимально можливої.
Приклади застосування закону Амдала
1. Система має N=1000 процесорів
• Програма має максимальний показник розпаралелювання 1000
• 0,1% програми має виконуватися послідовно (наприклад, операції вводу-виводу), тобто f=0,001 Обчислення показника прискорення (Speedup) дають:
8
Таким чином, незважаючи на суттєво малу послідовну частину програми, у цьому випадку досягається тільки половина максимально можливого прискорення, тобто Ефективність буде .
2. Система має N=1000 процесорів
• Програма має максимальний показник розпаралелювання 1000.
• 1% програми має виконуватися послідовно, тобто f=0,01
Показник прискорення (Speedup)
Ефективність E1000 = 9,1%. тобто використовується тільки 9,1% загальної потужності процесорів і це при малій, на перший погляд, послідовній частині програми!
З збільшенням послідовної частини програми падає завантаження процесорів, а з ним і показник прискорення порівняно з послідовною обчислювальною системою. Для кожної послідовної частини програми може бути обчислений максимально можливий показник прискорення незалежно від кількості застосовуваних процесорів:
Це означає, що програма із скалярною частиною, яка становить 1%, ніколи не зможе досягти показника прискорення (Speedup), що був би більшим 100 - незалежно від того, застосов...
14.03.2012 17:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора