Цією статтею ми починаємо цикл публікацій «Паралельне програмування для найменших». Очікувана аудиторія проєкту: школярі, а також студенти, які починають вивчати паралельне програмування.
Перевага багатопотокового застосунку перед послідовним полягає в тому, що кілька потоків виконують той самий обсяг роботи в кілька разів швидше. Одиницею роботи в окремому випадку може бути одна ітерація циклу. Студенти припускаються типової помилки під час паралельного програмування: створюють кілька потоків, кожен із яких виконує той самий обсяг роботи, що й послідовна програма. Це не приводить до бажаного прискорення, а навіть іноді уповільнює роботу застосунку. Тут працює дуже просте правило: кожен потік у паралельному застосунку має виконувати в N разів менше роботи, ніж послідовна програма, де N — кількість запущених потоків.
Розглянемо простий спосіб статичного поділу ітерацій одновимірного циклу між кількома потоками. На рисунку показано простий цикл, що складається з 10 ітерацій. Простір ітерацій описується інтервалом [0; 10). У послідовній програмі початкове значення лічильника ітерацій дорівнює нулю, інкремент циклу дорівнює одиниці, тобто тіло циклу виконується для кожної ітерації.
Як було сказано вище, помилковим є запуск двох і більше потоків, які виконували б той самий код, показаний на рисунку. У цьому разі обсяг роботи для одного потоку залишиться таким самим, а для всієї програми зросте в кілька разів. Необхідно поділити роботу — ітерації циклу — між потоками. На рисунку нижче схематично показано статичний почерговий розподіл для двох потоків.
Нескладно помітити, що потік номер 0 починає свою роботу з нульової ітерації і виконує лише парні ітерації (інкремент дорівнює 2): 0, 2, 4, 6, 8, а потік номер 1 починає з ітерації 1 і виконує непарні: 1, 3, 5, 7, 9. Таким чином, кожен потік виконує вдвічі менше роботи, ніж послідовна програма. Теоретичне прискорення дорівнює двом. Розглянемо варіант поділу роботи на три потоки (див. рис. нижче).
Тут потік номер 0 також починає з нульової ітерації, але обробляє кожну третю ітерацію: 0, 3, 6, 9. Потік номер 1 починає з ітерації 1, а потік номер два починає з ітерації 2. У всіх потоків інкремент лічильника циклу дорівнює трьом. Теоретичне прискорення дорівнює 3. У конкретному випадку баланс завантаження порушено, і фактичне прискорення дорівнює 10/4 = 2,5. Слід зазначити, що зі зростанням кількості ітерацій дисбаланс нівелюватиметься і наближатиметься до теоретичного прискорення.
Можна простежити закономірність, що кожен потік починає виконувати ітерацію, номер якої збігається з номером потоку, а інкремент дорівнює кількості потоків. Таким чином, можна записати загальний випадок для довільної кількості потоків (див. рис. нижче).
Переваги статичного почергового розподілу ітерацій полягають у: а) простоті програмної реалізації; б) відсутності накладних витрат на планування ітерацій; в) доброму балансі завантаження за великої кількості ітерацій і однакового часу виконання тіла циклу для різних ітерацій. Недолік підходу полягає у відсутності можливості балансувати навантаження, якщо для різних ітерацій тіло циклу виконується різний час.
Цей недолік було виправлено в бібліотеці OpenMP. Для статичного почергового поділу ітерацій циклу може бути використана директива, показана на рисунку нижче.
Для погано збалансованих обсягів роботи, коли тіло циклу виконується різний час для різних ітерацій, може бути використаний динамічний алгоритм балансування навантаження.
До недоліків OpenMP можна віднести обмеження на тип змінної ітерації циклу. Бібліотека OpenMP версії 2.5 підтримує лише signed int.