3Лабораторная работа №3 " Алгоритмы параллельных вычислений "

Цель работы – приобретение практических навыков построения и применения алгоритмов параллельных вычислений.

Основные теоретические сведения Параллельные формы алгоритмов

Обработка информации в параллельных и распределенных вычислительных системах осуществляется одновременно на многих параллельных вычислительных машинах (ПВМ). Для реализации алгоритма вычислений на ПВМ необходимо представить его в виде последовательности групп операций. Все операции одной группы должны быть независимыми и обладать возможностью быть выполненными одновременно (параллельно) на имеющихся функциональных устройствах ПВМ.

Представление алгоритма решения задачи в виде упорядоченных групп вычислительных операций, выполняемых в определенной последовательности, называется параллельной формой алгоритма (ПФ). Параллельность в алгоритме характеризуется числом операций в группе, которые могут выполняться одновременно.

Каждая группа операций называется ярусом ПФ (шагом алгоритма), число групп – высотой ПФ, максимальное число операций в ярусе – шириной ПФ. Высота определяет число шагов алгоритма, а ширина – число процессоров ПВМ, необходимых для решения задачи. Один и тот же алгоритм может иметь несколько ПФ, отличающихся как высотой, так и шириной.

Пусть, например, требуется вычислить выражение

x = ( а₁а₂ + а₃а₄ ) ( а₅а₆ + а₇а₈ )

на ПВМ, имеющей четыре процессора, способных выполнять операции сложения и умножения. Сначала выполняются четыре операции умножения (ярус 1), затем две операции сложения (ярус 2) и операция умножения (ярус 3) (табл.3.1).

Табл.3.1. Параллельная форма алгоритма

Ярусы (шаги)	Операции
	1	2	3	4
1	а1а2 = b1	а3а4 = b2	а5а6 = b3	а7а8 = b4
2	b1+ b2 = c1	b3+ b4 = c2
3	c1c2 = x

Высота ПФ равна трем, ширина – четырем.

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

Основными характеристиками параллельных алгоритмов являются следующие.

1) Ускорение S_p алгоритма показывает, во сколько раз быстрее он решает задачу по сравнению с лучшим из последовательных алгоритмов решения той же задачи на однопроцессорной вычислительной машине (ВМ), и определяется соотношением:

S_p = T₁ / T_p , 1 ≤ S_p ≤ p,

где: T₁ – число операций, необходимое для решения задачи на однопроцессорной ВМ;

T_p – то же – на ПВМ с p процессорами.

В примере ПФ алгоритма табл.3.1 число операций, необходимое для решения задачи на однопроцессорной ВМ, равно Т₁= 7, а на 4-процессорной ПВМ - T_{p =} 4. Таким образом, ускорение S_p = T₁ / T_p = 7 / 3 = 2.33,

2) Эффективность алгоритма представляет собой ускорение алгоритма, достигнутое по отношению к одному процессору:

E_p = S_p / p, 1/p ≤ E_p ≤ 1.

В примере ПФ табл.3.1 эффективность алгоритма E_p = S_p / p = 2.33 / 4 = 0.58.

3) Высота алгоритма h отражает время выполнения алгоритма.

В примере ПФ табл.3.1 высота алгоритма h =3.

Если исходная задача определяется n входными переменными, то высота ПФ определяется соотношением:

h  log₂n.

4) Загруженность процессоров Z характеризуется отношением числа выполненных алгоритмом операций к числу возможных операций, которые можно выполнить за то же время.

В примере ПФ алгоритма табл.3.1 загруженность процессоров Z равна:

Z = (7 / 12) 100% = 58.3%.

5) Устойчивость алгоритма к ошибкам округления. В процессе решения задачи на каждом шаге осуществляется округление промежуточных данных, связанное с ограниченностью разрядной сетки ПВМ. В задачах большой размерности (порядка тысяч ограничений и переменных) по мере увеличения высоты ПФ ошибки округления могут приводить к неустойчивости алгоритма и получению неправильного результата решения задачи. Во избежание этого явления применяются специальные методы повышения устойчивости алгоритма к ошибкам округления, рассматриваеме, в частности, в курсе линейной алгебры.

6) Конфликтность алгоритма определяет состояние, когда несколько процессоров в процессе вычислений выбирают в памяти одну и ту же информацию, т.е. возникает конфликтная ситуация. Конфликтность алгоритма можно устранить путем увеличения его высоты, устанавливая для процессоров очередность доступа к информации.