Недоліки:

• Проблема обміну даними: обмін даними в таких системах зазвичай йде надто повільно порівняно зі швидкістю обчислень (і з великими затримками). Тому завдання, що потребують інтенсивного обміну, неможливо вирішити на таких системах ефективно.

• Складне програмування: програміст повинен продумати обмін даними, який буде присутній в системі, повинен сам запрограмувати цей обмін (наприклад, за допомогою MPI). При неправильному програмуванні велика ймовірність взаємних блокувань: коли, наприклад, два процесори чекають даних один від одного. Проблема блокувань є і в системах із загальною пам'яттю, але тут вона виявляє себе набагато частіше. Автоматична організація обміну даними можлива лише для деяких окремих випадків.

• Великий розмір систем і велике енергоспоживання: кластерні системи займають цілі кімнати і навіть будівлі.

Гібридні системи

Багато сучасних систем являють собою ієрархію описаних вище систем. Наприклад, сучасні процесори є конвеєрними процесорами, і мають набір векторних інструкцій (MMX, SSE і т.п.), що дозволяють виконувати одночасні обчислення з різними даними. Крім того, процесор може мати два ядра, або може бути кілька процесорів в комп'ютері. Таким чином, на цьому рівні система являє собою систему із загальною пам'яттю. Потім можна з'єднати кілька таких комп'ютерів в кластер, утворивши новий рівень ієрархії: систему з розподіленою пам'яттю.

Властивості паралельних алгоритмів

Щоб прискорити вирішення завдання, не достатньо мати паралельну обчислювальну систему. Крім цього, потрібно ще створити для такої системи спеціальну (паралельну) програму. Для того, щоб алгоритм міг бути ефективно реалізований у вигляді паралельної програми, він повинен володіти внутрішнім паралелізмом.

Граф обчислювального алгоритму

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

Розглянемо, наприклад, алгоритм обчислення виразу:

(1)

Спочатку потрібно обчислити добуток і , потім взяти корінь, і, нарешті, виконати додавання. Ми не можемо виконати додавання, поки не обчислені обидва його аргументу. Описаний алгоритм можна зобразити таким чином:

Рисунок 1. - Схема обчислення виразу (1)

Видно, що процес обробки даних може бути виражений у вигляді одно направленого графа. Такий граф можна зобразити на площині, причому кожну арифметичну операцію розташовувати максимально високо (якщо вісь часу спрямована вниз), але не вище тих операцій, результат яких потрібен для її обчислення. У такому випадку висота графа буде рівна мінімальному часу (числу кроків / етапів) рішення цього завдання на ідеальній паралельній обчислювальній системі з необмеженим числом обчислювачів.

Ступінь паралелізму

Ступенем паралелізму етапу чисельного алгоритму називається число операцій, які на даному етапі можна виконувати паралельно (ширина графа, побудованого описаним више способом). Проілюструємо це визначення декількома прикладами. Почнемо з задачі додавання двох векторів і розмірності n. Додавання незалежні і можуть виконуватися паралельно:

Рисунок 2 - Схема додавання векторів

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

Розглянемо тепер задачу складання n чисел . Звичайний послідовний алгоритм

(2)

непридатний для паралельних обчислень. Однак завдання може бути вирішена іншим методом. На рисунку показано, як можна здійснити додавання восьми чисел в три етапи за допомогою алгоритму здвоювання:

Рисунок 3 - Схема алгоритму здвоювання

Завдання додавання розділено на менші підзадачі, які можуть вирішуватися незалежно.

Для чисел алгоритм здвоювання складається з етапів; на першому етапі виконується додавань, на другому — , і так далі, поки на останньому етапі не буде виконано останнє додавання. Загальне число операцій додавання дорівнює : таке ж, як і в послідовному алгоритмі (2).

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

Додавання за допомогою алгоритму здвоювання має ще одну перевагу перед послідовним додаванням: він забезпечує кращу (в середньому) точність підсумовування при використанні чисел з плаваючою крапкою.

Середнім ступенем паралелізму чисельного алгоритму називається відношення загального числа операцій алгоритму до його етапів. Очевидно, для алгоритму здвоювання середня ступінь паралелізму дорівнює:

(3)

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