Закон Амдаля: умножение матрицы

Question

Я пытаюсь рассчитать долю P моего кода, которая может быть распараллелена, применить закон Амдаля и соблюдать теоретическое максимальное ускорение.

Мой код проводит большую часть времени на умножении матриц (используя библиотеку Eigen). Должен ли я считать эту часть полностью параллелизуемой?

Answer 1

Если ваши матрицы достаточно велики, скажем, более 60, то вы можете скомпилировать с включенным OpenMP (например, -fopenmp с gcc), и продукты будут распараллелены для вас. Однако часто лучше распараллеливать на самом высоком уровне, особенно если матрицы не очень велики. Тогда это зависит от того, можете ли вы идентифицировать независимые задачи в своем алгоритме.

Answer 2

Во-первых, было бы уместно рассмотреть, как библиотека Eigen обрабатывает матричное умножение.

Тогда матрица (MXN) -векторных (nx1) умножение без Эйгена может быть записана следующим образом:

1 void mxv(int m, int n, double* a, double* b, double* c) 
2 { //a=bxc 
3 int i, j; 
4 
5 for (i=0; i<m; i++) 
6 { 
7  a[i] = 0.0; 
8  for (j=0; j<n; j++) 
9  a[i] += b[i*n+j]*c[j]; 
10 } 
11 } 

Как вы можете видеть, поскольку никаких два продукта не вычислить тот же элемент результирующего вектора а [] и поскольку порядок, в котором вычисляются значения для элементов a [i] при i = 0 ... m, не влияет на правильность ответа, эти вычисления могут выполняться независимо по значению индекса i.

Тогда петля, подобная предыдущей, полностью параллелизуема. Было бы относительно просто использовать OpenMP для целей параллельной реализации на таких циклах.