Існує кілька способів, як домогтися від програмістів великої швидкості розвʼязання поставлених задач із мінімальною кількістю помилок.
Перший спосіб — використання мов високого рівня, наприклад, C++. Обʼєктно-орієнтоване програмування дає змогу створювати в коді сутності різної природи, а також визначати операції над ними. У результаті ми отримуємо в розпорядження набір якихось обʼєктів, які відповідають обʼєктам із предметної області розвʼязуваної задачі, з високорівневими властивостями та методами. Деталі реалізації приховуються за цими високорівневими методами, що дає програмісту змогу зосередитися на розвʼязанні задачі.
Другий спосіб — використання сучасних інструментальних засобів: компіляторів, генераторів тестів, формальних верифікаторів, профайлерів. Компілятори використовують внутрішні оптимізації для отримання кращих часових характеристик і мінімальних витрат памʼяті. Прикладом таких оптимізацій може бути автоматична конвеєризація, розгортання (згортання) або розпаралелювання циклів, за якого отримується швидша реалізація програми. У цьому разі розвʼязанням рутинних задач програмування займається компілятор, який, як відомо, працює набагато швидше і помиляється рідше, ніж програміст.
Третій спосіб — використання методичного забезпечення. Розроблено багато методів проєктування і т. зв. патернів — підходів до розвʼязання тієї чи іншої задачі в певному контексті. Видано багато книг і посібників, присвячених як програмуванню самому по собі, розвʼязанню абстрактних задач, так і застосуванню в конкретних задачах народного господарства.
Четвертий спосіб — використання бібліотек, які містять готові протестовані рішення: алгоритми і структури даних. Використовуючи бібліотечні компоненти, по-перше, скорочується час на розробку, а по-друге, скорочується час на тестування проєкту, тому що бібліотечні компоненти протестовані заздалегідь і неодноразово були впроваджені в промислових проєктах. Таким чином, обсяг бібліотечного коду може істотно перевищувати обсяг коду, написаного програмістом.
Зробимо короткий огляд технологій, які підвищують продуктивність програмістів, що розробляють паралельні застосунки. Багато років найдоступнішим способом багатопотокового програмування було використання бібліотеки Windows API або POSIX Threads. Програмісту доводилося розвʼязувати поставлені задачі на дуже низькому рівні. Наприклад, програмісту необхідно:
-
самостійно створювати і видаляти потоки;
-
визначати ті функції, які мають виконуватися в потоці;
-
передавати в потік потрібні параметри;
-
використовувати різні функції для синхронізації потоків;
-
забезпечити рівномірне завантаження потоків обчисленнями;
-
подбати про масштабованість отриманого рішення.
Очевидно, що недолік такого підходу полягає в тому, що перетворення послідовної програми на паралельну може зайняти багато часу. Також отримане рішення буде схильне до багатьох помилок.
Частину цих проблем було успішно розвʼязано в бібліотеці OpenMP. Ця бібліотека реалізована у вигляді набору функцій і директив — спеціальних розширень до компілятора. Програміст у потрібному місці застосовує ту чи іншу директиву, а компілятор у вказаному місці підставляє виклики системних функцій. Наприклад, розпаралелювання циклу здійснюється єдиною директивою компілятору. При цьому компілятор подбає про створення і синхронізацію потоків, розподіл ітерацій між потоками, а також добрий баланс завантаження. Такий підхід дає змогу розвʼязати обмежений клас задач практично без помилок і за короткий строк.
Але бібліотека OpenMP має низку обмежень і недоліків. Укажемо лише деякі з них.
-
Цикли з невідомою кількістю ітерацій не можуть бути розпаралелені.
-
Істотні обмеження на параметри циклу.
-
Обмежені можливості з розподілу роботи між потоками.
-
Операція reduction обмежена вісьмома елементарними операціями.
-
Відсутність складніших шаблонів, ніж паралельний цикл або паралельна секція.
Intel Threading Building Blocks (далі ТББ) — нова бібліотека для багатопотокового програмування, розроблена фірмою Інтел. Бібліотека має низку функцій і класів для розвʼязання поширених задач паралельного програмування:
-
функція parallel_for для організації паралельного циклу;
-
функція parallel_reduce для паралельного циклу з подальшою комбінацією часткових результатів;
-
клас parallel_while для створення паралельного циклу з невідомою кількістю ітерацій;
-
клас pipeline для організації конвеєрних обчислень;
-
контейнери з можливістю паралельного доступу: concurrent_vector, concurrent_queue, concurrent_hash_map.
У ТББ введено концепцію обʼєкта-задачі — класу C++, у якому визначено оператор (), що виконує поставлену задачу (див. лістинг нижче). Залежно від алгоритму, в якому використовується обʼєкт-задача, цей оператор, наприклад, може приймати як параметр діапазон ітерацій (parallel_for, parallel_reduce) або черговий елемент для обробки (parallel_while, pipeline).
`// Класс-задача class Body { public: // Оператор-обработчик void operator() () { // Здесь расположены вычисления } };
* This source code was highlighted with Source Code Highlighter.`
Тут видно відмінність від програмування звичайних потоків: програміст створює задачі, а не потоки. Бібліотека ТББ під час ініціалізації створює необхідну кількість потоків, а вбудований планувальник призначає задачі на ці потоки під час роботи програми.
Функції-шаблони parallel_for і parallel_reduce працюють із діапазонами (просторами ітерацій). Бібліотека ТББ надає для цього два класи: blocked_range і bloced_range2d, одновимірний і багатовимірний простір відповідно. ТББ рекурсивно ділить вихідний діапазон на безліч блоків, які передаються як параметри для оператора-обробника. Таким чином, кожен обʼєкт-задача виконує обчислення над власною порцією ітерацій. Наведемо приклад використання одновимірного діапазону.
<span style="font-family:Courier New;font-size:85%;color:black;">blocked_range<<span style="color:#0000ff;">int</span>>(begin, end, grainsize)</span>
Тут параметр шаблону — це тип елементів діапазону, begin — початкова точка, end — кінцева точка. Пара begin і end описує напіввідкритий інтервал [begin, end), наприклад, цикл for (int i = 2; i < 5; i++) відповідає інтервалу [2; 5) і включає в себе ітерації 2, 3, 4. Параметр grainsize визначає розмір неподільного блока ітерацій. У тому разі, якщо на черговому етапі поділу вихідного діапазону трапиться блок, менший за grainsize, то він вважатиметься неподільним. На рисунку нижче показано приклад рекурсивного поділу діапазону blocked_range
На завершення статті наведемо приклад розпаралелювання циклу for.
`#include «tbb/blocked_range.h»
include «tbb/parallel_for.h»
include «tbb/task_scheduler_init.h»
using namespace tbb;
///////////////////////////////////////////////////////////////////////////////
// Класс-задача class MyTask { public: // Метод-обработчик выполняет функцию Calculate для каждого элемента // блока итераций. void operator() (const blocked_range<int>& r) const { for (int i = r.begin(); i != r.end(); i++) Calculate(i); } };
///////////////////////////////////////////////////////////////////////////////
int main() { // Инициализация библиотеки ТББ task_scheduler_init init;
// Запуск шаблона parallel_for, который принимает два параметра: // * объект диапазона итераций [0, 1000000) // * объект-задачу parallel_for(blocked_range<int>(0, 1000000, 10000), MyTask);
return 0; }
///////////////////////////////////////////////////////////////////////////////
* This source code was highlighted with Source Code Highlighter.`