Як визначається час виконання паралельного алгоритму?

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

- безліч вершин графа, що представляють виконувані операції алгоритму

R - безліч дуг графа; дуга r(i,j) належить графові тільки якщо операція j використовує результат виконання операції i

Вершини без вхідних дуг можуть використовуватися для завдання операцій введення, а вершини без вихідних дуг – для операцій висновку.

V – безліч вершин графа без вершин введення,

D(G) – діаметр графа (давжина максимального шляху)

Модель паралельного алгоритму:

Час виконання паралельного алгоритму з заданим порядком:

Час виконання параллельного алгоритму з оптимальним порядком:

Мінімально можливий час розвязку задачі при заданій кількості процесів:

Оцінка найбільш швидкого виконання алгоритму:

час виконання послідовного алгоритму для заданої розрахункової схеми:

Час виконання послідовного алгоритму:

Час послідовного розрахунку задачі:

Рекомендації

–при виборі обчислювальної схеми алгоритму повинен використовуватися граф з мінімально можливим діаметром

–для паралельного виконання доцільна кількість процесорів визначається величиною p~T1/T∞

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

При зменшенні числа використовуваних процесорів час виконання алгоритму збільшується пропорційно величині зменшення кількості процесорів, тобто:

при виборі обчислювальної схеми алгоритму повинен використовуватися граф з мінімально можливим діаметром

Приклад: граф алгоритму обчислення площі прямокутника, заданого координатами двох кутів, що протилежать

Дата добавления: 2015-08-18