Параллельные вычисления. Баканов В.М. - 77 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 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

Страницы