- •5. Паралельні і розподілені обчислення
- •1. Розширені мережі Петрі. Типи розширень. Модифіковані правила активізації і ввімкнення переходів.
- •2. Конвеєрна обробка. Пікова та реальна продуктивність. Графік залежності продуктивності конвеєрного пристрою від довжини вхідного набору даних.
- •3. Ступінь деталізації декомпозиції, ступінь паралелізму паралельного алгоритму. Граф залежності задач.
- •4. Взаємодія задач при паралельній обробці. Граф взаємодії задач.
- •5. Вартість операції, завантаженість пристрою, прискорення системи. 1-й закон Амдала.
- •6. Другий та третій закони Амдала.
- •7. Потоки і багатозадачність. Потік, процес, програма, багатопотоковість. Типи потоків, види багатозадачності. Правила використання потоків.
- •8. Організація обчислень в машинах потоків даних.
- •Правила використання потоків
- •Обчислення в мпд
- •9. Декомпозиція задач за вхідними даними.
- •10. Декомпозиція задач за вихідними даними.
- •11. Дослідницька декомпозиція задач.
- •12. Декомпозиція задач за проміжними даними.
- •13. Граф машин потоків даних (мпд) і його основні елементи.
- •14. Способи взаємодії ниток при багато потоковому програмуванні: семафори, події, взаємне виключення.
- •15. Рекурсивна декомпозиція. Приклад швидкого сортування масиву чисел.
15. Рекурсивна декомпозиція. Приклад швидкого сортування масиву чисел.
Процес розподілу обчислень на менші частини, деякі або всі з яких можуть бути виконані паралельно, називається декомпозицією.
При цьому способі основне завдання розподіляється певним способом на невелику кількість незалежних задач. На наступному кроці отримані задачі знову декомпозуються, рекурсивно застосовуючи вищезазначений спосіб і т.д.
Цей спосіб призводить до виявлення природного паралелізму системи.
Приклад. Швидке сортування набору чисел: {7,3,10,6,8,1,2,9}.
Вибирається основний елемент Х і основна послідовність А розбивається на дві послідовності А0 і А1, такі що всі елементи послідовності А0 є меншими за Х, а всі елементи А1 є більшими за Х і т.д.
7 3 10 6 8 1 2 9
3 6 1 2
3 1
1