Алгоритмы паралелльного вычисления

Лабараторная работа 1

Тема: Алгоритмы паралелльного вычисления
Задачи: Матричные вычисления (Сложение матриц)

Пусть заданы 2 матрицы А и В размерностью m∗n (m строк, n столбцов). В результате сложения получим матрицу

С размерностью m∗n:


C[i][j]=A[i][j]+B[i][j],(i=0..m,j=0..n). (13)


Последовательное вычисление:


1 for (i = 0; i < m; ++i)
2 for (j = 0; j < n; ++j)
3 C[i][j] = A[i][j] + B[i][j];
При последовательных вычислениях требуется n∗m операций сложения.


Циклы независимы.

Чтобы упростить параллельное выполнение вложенных циклов, преобразуем фрагмент программы, приведенный выше, в эквивалентный фрагмент программы:

1 for (k = 0; k < m * n; ++k)
2 {
3 i=k/n;j=k%n;
4 C[i][j] = A[i][j] + B[i][j];
5 }

Если строки матриц расположены непосредственно друг за другом, то последний фрагмент программы может быть преобразован так:

1 for (k = 0;k
2 {
3 С[k] = А[k] + B[k];
4 }

Для неограниченного параллелизма все операции можно выполнять параллельно и ускорение составляет m∗n.

Если есть процессор, содержащий р ядер, то для выполнения цикла потребуется (m∗n+p–1)/p операций.

Если предположить, что m∗n кратно числу ядер p, то ускорение равно p, а эффективность равна 1.

Заключения


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