Підсумки

Висновки

Паралелізм існує на рівнях бітів, інструкцій, даних, потоків, процесів і завдань; що дорожча взаємодія на рівні, то крупнішими мають бути паралельні частини. Моделі дозволяють оцінити алгоритм до програмування: граф залежностей і модель роботи й проміжку дають межу прискорення $T_1/T_{\mathrm{\infty }}$ і теорему Брента, PRAM – власний паралелізм алгоритму, BSP і LogP – вартість обмінів і синхронізацій. Грід об’єднує ресурси багатьох організацій у віртуальні організації за допомогою проміжного ПЗ (ARC, HTCondor) і підходить для великої кількості незалежних завдань (EGI, WLCG, BOINC, УНГ). Методологія PCAM проводить від найдрібнішого розбиття через аналіз обмінів до укрупнення й відображення на процесори; за нерівномірної роботи потрібне динамічне балансування. Вектори розподіляють блочно, циклічно чи блочно-циклічно, матриці – смугами чи блоками; для кластерів шахова схема та алгоритми Фокса й Кеннона зменшують обміни. Чисельні методи дають усі типи паралелізму: редукції (інтегрування, скалярні добутки CG), рекурсивні задачі (адаптивне інтегрування), незалежні задачі (корені, траєкторії ОДУ). Прогноз за моделлю часу з виміряними параметрами пояснює результати вимірювань, а функція ізоефективності показує, як має зростати задача зі збільшенням кількості процесорів.

Питання для самоперевірки

1. Назвіть рівні паралелізму. Які з них неявні для програміста?
2. Що таке зернистість? Як вона пов’язана з вартістю взаємодії на кожному рівні?
3. Що таке граф залежностей і критичний шлях? Чому послідовний цикл суми не має паралелізму?
4. Чим відрізняються моделі EREW, CREW і CRCW PRAM? Чому PRAM оптимістична?
5. Що таке робота, проміжок і паралелізм алгоритму? Сформулюйте теорему Брента.
6. З яких фаз складається суперкрок BSP? Як обчислити його вартість?
7. Які параметри має модель LogP і чим вона відрізняється від BSP?
8. Чим «обмін» на спільній пам’яті відрізняється від обміну на розподіленій?
9. Що таке грід і віртуальна організація? Назвіть три ознаки гріду за Фостером.
10. Яке проміжне ПЗ використовують у гріді? Для чого потрібен HTCondor?
11. Що таке EGI, WLCG, BOINC і Український національний грід?
12. Чим відрізняються кластер, грід і хмара? Які задачі підходять для гріду?
13. Опишіть етапи методології PCAM.
14. Чим статичне балансування навантаження відрізняється від динамічного? Що таке крадіжка роботи?
15. Опишіть блочний, циклічний і блочно-циклічний розподіли вектора. Коли кожен вигідний?
16. Чому паралельна сума дійсних чисел може бути недетермінованою? Як зробити її відтворюваною?
17. Порівняйте схеми множення матриці на вектор за обчисленнями й обмінами.
18. Як працюють алгоритми Фокса й Кеннона? Чим вони кращі за стрічковий алгоритм?
19. Як розпаралелити обчислення інтеграла? Що таке правило Рунге?
20. Чому адаптивне інтегрування потребує динамічного балансування? Навіщо поріг рекурсії?
21. Як паралельно знайти всі корені рівняння на відрізку? Коли корені можна пропустити?
22. Які операції ітерації методу спряжених градієнтів паралельні й що обмежує масштабованість?
23. Які способи розпаралелювання мають системи ОДУ?
24. Як скласти модель часу паралельної програми? Що таке функція ізоефективності?

Корисні посилання

• Паралельне програмування в .NET: https://learn.microsoft.com/dotnet/standard/parallel-programming/
• Клас Barrier: https://learn.microsoft.com/dotnet/standard/threading/barrier
• I. Foster. Designing and Building Parallel Programs: https://www.mcs.anl.gov/~itf/dbpp/
• EGI: https://www.egi.eu/
• WLCG: https://wlcg.web.cern.ch/
• Грід у ЦЕРН: https://home.cern/science/computing/grid
• BOINC: https://boinc.berkeley.edu/
• HTCondor: https://htcondor.org/
• NorduGrid ARC: https://www.nordugrid.org/arc/
• Український національний грід: http://ung.bitp.kiev.ua/ua/
• Налагодження багатопотокових програм у Rider: https://www.jetbrains.com/help/rider/Debugging_Multithreaded_Applications.html