Розпаралелювання програм

Розпарале́лювання програ́м — процес адаптації алгоритмів, записаних у вигляді програм, для їх ефективного виконання на обчислювальній системі паралельної архітектури (останнім часом, як правило, на багатопроцесорній обчислювальній системі). Полягає або в переписуванні програм на спеціальну мову, яка описує паралелізм і яку розуміють транслятори цільової обчислювальної системи, або до вставки спеціальної розмітки (наприклад, інструкцій MPI або OpenMP).

Розпаралелювання може бути ручним, автоматизованим або напівавтоматизованим. Щоб оцінити його якість застосовують наступні критерії:

• Прискорення ${\displaystyle S_{p}=T_{1}/T_{p}}$, де ${\displaystyle T_{p}}$ — час виконання розпаралеленої програми на ${\displaystyle p}$ процесорах, ${\displaystyle T_{1}}$ — час виконання вхідної програми. В ідеальному випадку (відсутність накладних витрат на організацію паралелізму) дорівнює ${\displaystyle p}$.
• Завантаженість ${\displaystyle S_{p}/p=T_{1}/pT_{p}}$, яка показує долю використання процесорів. В ідеальному випадку дорівнює 1, або 100 %. Ця величина, як правило, значно наочніше характеризує ефективність паралелізму в серії випробувань при різних ${\displaystyle p}$, ніж ${\displaystyle S_{p}}$, особливо на графіках.

При розпаралелюванні важливо брати до уваги не лише формальний паралелізм структури алгоритму, але й те, що обмінні операції в паралельних комп'ютерах є, як правило, набагато повільнішими від арифметичних. З цим пов'язане існування левової частки накладних витрат на організацію паралелізму.