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

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

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

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

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

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

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

(1)

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

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

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

Дата добавления: 2014-01-07