ВУЗ:
Составители:
Рубрика:
- 77 -
На основе этих данных строится описание параллельного выполнения алго-
ритма, один из вариантов построения которого приведен в книге (
**
) и рабо-
те [3]).
Неравномерность загрузки процессоров снижает эффективность использо-
вания МВС, поэтому проблема балансировки (равномерности загрузки про-
цессоров) относится к числу важных задач параллельного программирования.
Один из действенных подходов к обеспечению равномерности загрузки
процессоров состоит в организации всех готовых к выполнению в системе
вычислительных действий в виде очереди заданий.
При вычислениях любой
освободившийся процессор запрашивает для себя работу из этой очереди;
появляющиеся по мере обработки данных дополнительные задания допол-
няют очередь. Эта схема балансировки вычислительной нагрузки между
процессорами проста, наглядна и эффективна, что позволяет говорить об ис-
пользовании очереди заданий как об общей модели организации параллель-
ных вычислений для
систем с общей памятью [3].
При теоретическом анализе применяется также понятие стоимости парал-
лельного алгоритма (произведение сложности алгоритма на число исполь-
зуемых процессоров). Известно, например, что оптимальный алгоритм сор-
тировки требует O(n
×
log n) операций (n – число сортируемых записей, см.
(
***
)), тогда для параллельного алгоритма со сложностью O(n) коэффициент
ускорения составит O(log n), а стоимость параллельного алгоритма на p про-
цессорах равна O(n
×
p). Т.к. стоимость алгоритма последовательной сорти-
ровки на одном процессоре совпадает с его сложностью и равна O(n
×
log n),
алгоритм параллельной сортировки обходится дороже параллельной при
1
>=
×
×
nlog
p
nlogn
pn
(т.е. p>log n) и дешевле в противоположном случае (при
p<log n). В случае p=n стоимость параллельной сортировки всегда выше по-
следовательной (n всегда больше log n).
3.2 Потенциал распараллеливания циклов. Циклы ParDO
Практика программирования (особенно научно-технических задач – в пер-
вую очередь для сеточных методов) показывает, что наибольший ресурс па-
раллелизма сосредоточен в циклах, поэтому распространенным способом
распараллеливания является распределение итераций циклов (если между
итерациями не существует информационных зависимостей, то итерации
**
Dimitri P.Bertsekas, John N.Tsitsiklis. Parallel and distributed Computation. Numerical
Methods. - Prentice Hall, Englewood Cliffs, New Jersey, 1989.
***
Макконел Дж. Основы современных алгоритмов. –М.: Техносфера, 2004, -368 с.
- 77 - На основе этих данных строится описание параллельного выполнения алго- ритма, один из вариантов построения которого приведен в книге (**) и рабо- те [3]). Неравномерность загрузки процессоров снижает эффективность использо- вания МВС, поэтому проблема балансировки (равномерности загрузки про- цессоров) относится к числу важных задач параллельного программирования. Один из действенных подходов к обеспечению равномерности загрузки процессоров состоит в организации всех готовых к выполнению в системе вычислительных действий в виде очереди заданий. При вычислениях любой освободившийся процессор запрашивает для себя работу из этой очереди; появляющиеся по мере обработки данных дополнительные задания допол- няют очередь. Эта схема балансировки вычислительной нагрузки между процессорами проста, наглядна и эффективна, что позволяет говорить об ис- пользовании очереди заданий как об общей модели организации параллель- ных вычислений для систем с общей памятью [3]. При теоретическом анализе применяется также понятие стоимости парал- лельного алгоритма (произведение сложности алгоритма на число исполь- зуемых процессоров). Известно, например, что оптимальный алгоритм сор- тировки требует O(n × log n) операций (n – число сортируемых записей, см. (***)), тогда для параллельного алгоритма со сложностью O(n) коэффициент ускорения составит O(log n), а стоимость параллельного алгоритма на p про- цессорах равна O(n × p). Т.к. стоимость алгоритма последовательной сорти- ровки на одном процессоре совпадает с его сложностью и равна O(n × log n), алгоритм параллельной сортировки обходится дороже параллельной при n× p p = >1 (т.е. p>log n) и дешевле в противоположном случае (при n × log n log n p
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »