Паралельний алгоритм
Парале́льний алгори́тм в інформатиці (також конкурентний алгоритм), на відміну від традиційного послідовного, це алгоритм, який одночасно може виконуватися на багатьох обчислювальних приладах, з наступним об'єднанням отриманих результатів для отримання вірного загального результату.
Деякі алгоритми легко піддаються розбиттю на подібні частини. Наприклад, розбиття роботи з перевірки всіх чисел від одного до ста тисяч на простоту може бути зроблено шляхом призначення кожному доступному процесору певної підмножини чисел, з наступним об'єднанням отриманих результатів в один список (схожим чином реалізовано, наприклад, проект GIMPS).
З іншого боку, більшість відомих алгоритмів обчислення значення числа пі не дозволяє розбиття на частини, що виконуються окремо, через те, що для кожної ітерації алгоритму потрібен результат попередньої. Ітеративні чисельні методи, такі як метод Ньютона або задача трьох тіл, також є алгоритмами, яким властива послідовність. Деякі приклади рекурсивних алгоритмів досить складно піддаються одночасному виконанню. Одним з таких прикладів є пошук в глибину на графах.
Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора натрапляє на фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах.
Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Паралельні алгоритми вимагають використання ще одного ресурсу: підсистеми зв'язків між різними процесорами. Існує два способи обміну даними між процесорами: використання спільної пам'яті та система передачі повідомлень.
Системи зі спільною пам'яттю вимагають введення додаткових блокувань для даних, що обробляються, і накладають певні обмеження під час використання додаткових процесорів.
Системи передачі повідомлень використовують поняття каналів і блоків повідомлень, що створює додатковий трафік на шині та вимагає додаткових витрат пам'яті для організації черги повідомлень. У проектуванні сучасних процесорів використовують особливі шини схожі на поперечини , що робить витрати на зв'язок малими і надає змогу програмісту самому вирішувати наскільки великий обмін даними у паралельному алгоритмі потрібен.
Ще однією проблемою використання паралельних алгоритмів є балансування навантаження. Наприклад, пошук простих чисел в діапазоні від одного до мільйона легко розподілити між наявними процесорами, однак деякі з них можуть отримати менший обсяг роботи і будуть простоювати. Балансування навантаження становить проблему, яка може бути предметом окремих досліджень[1]. У гетерогенних обчислювальних середовищах, де обчислювальні елементи істотно відрізняються за продуктивністю і доступністю (наприклад, у грід-системах) вона набуває особливої важливості.
Різновид паралельних алгоритмів під назвою розподілені алгоритми окремо розроблявся з метою застосування на кластерах і в середовищах розподілених обчислень з урахуванням властивостей подібної обробки.
Примітки[ред. | ред. код]
- ↑ Тютюнник Марія (25 травня 2010). Паралельні алгоритми та засоби для розв’язання деяких задач масових обчислень (PDF). Архів оригіналу (PDF) за 8 липня 2013. Процитовано 25 вересня 2010.