Лекции по параллельным вычислениям. Гергель В.П - 61 стр.

UptoLike

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

Рубрика:

Лекция 5

Построение параллельных алгоритмов:

инженерный подход

5.1 Постановка задачи

Известно, что перенос последовательной программы на параллельную

ЭВМ без ее существенной переработки, как правило, не приводит к ускорению

вычислений. Усилия, затрачиваемые на эту переработку, в значительной степе-

ни зависят от типа решаемой задачи. Для того чтобы построить эффективный

параллельный алгоритм, строго говоря, следует провести анализ графа алго-

ритма и решить задачу отображения так, как это сформулировано в разделе 3.2.

Решение такой задачи оптимизации на графах требует значительных усилий и

высокой квалификации.

На практике разработку параллельного алгоритма обычно осуществляет

специалист, работающий в некоторой предметной области, не всегда владею-

щий методами дискретной оптимизации. С другой стороны, строгое решение

этой задачи требуется далеко не всегда. Обычно ограничения, связанные с ти-

повым набором доступных архитектур, все равно вынуждают исследователя

находить некоторое приемлемое для него решение, руководствуясь не вполне

строгими, но проверенными на практике приемами и правилами.

В частности, если в конкретной задаче элементы некоторого массива ис-

ходных данных могут обрабатываться независимо друг от друга, то эти правила

обычно очевидны и позволяют строить весьма эффективные параллельные ал-

горитмы. В этом случае задача переработки может свестись к разбиению мас-

сива исходных данных на фрагменты, обработка которых ведется независимо

на различных процессорах. Ясно, что при этом должна обеспечиваться равно-

мерная загрузка процессоров, с учетом их, возможно, различной производи-

тельности.