Умножение матриц с использованием OpenMP (C) - свертывание всех циклов - PullRequest
Новая
       46

Умножение матриц с использованием OpenMP (C) - свертывание всех циклов

1 голос
/ 23 февраля 2020

Итак, я узнал об основах OpenMP в C и конструкциях разделения работы, особенно для l oop. Один из самых известных примеров, используемых во всех уроках, - это умножение матриц, но все они просто распараллеливают внешний l oop или два внешних цикла. Мне было интересно, почему мы не распараллеливаем и не сворачиваем все 3 цикла (используя atomi c), как я сделал здесь: 

    for(int i=0;i<100;i++){
        //Initialize the arrays
        for(int j=0;j<100;j++){
            A[i][j] = i;
            B[i][j] = j;
            C[i][j] = 0;       
        }       
    }

    //Starting the matrix multiplication
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for collapse(3)
        for(int i=0;i<100;i++){
            for(int j=0;j<100;j++){
                for(int k=0;k<100;k++){
                        #pragma omp atomic
                        C[i][j] = C[i][j]+ (A[i][k]*B[k][j]);
                }       
            }       
        }   
    }

Можете ли вы сказать мне, что мне здесь не хватает или почему это не так? плохое решение?

Ответы [ 3 ]

1 голос
/ 23 февраля 2020

Свертывание циклов требует, чтобы вы знали, что вы делаете, так как это может привести к очень недружественному кешированию пространства итерации или ввести зависимости данных в зависимости от того, как произведение значений l oop связано с количеством потоков.

Представьте себе следующий построенный пример, который на самом деле не так уж редок (число l oop мало для иллюстрации точки): 

for (int i = 0; i < 7; i++)
  for (int j = 0; j < 3; j++)
     a[i] += b[i][j];

Если вы распараллелите внешний l oop, три потока получают две итерации и один поток получает только одну, но все они выполняют все итерации внутренней l oop: 

---0-- ---1-- ---2-- -3- (thread number)
000111 222333 444555 666 (values of i)
012012 012012 012012 012 (values of j)

Каждая a[i] обрабатывается только одним потоком , Умные компиляторы могут реализовать внутренний l oop, используя оптимизацию регистра, сначала накапливая значения в регистре и назначая только a[i] в самом конце, и он будет работать очень быстро.

Если вы свернете две петли, вы попадаете в совершенно другую ситуацию. Поскольку в настоящее время общее число итераций составляет 7x3 = 21, разделение по умолчанию будет (в зависимости от компилятора и среды выполнения OpenMP, но большинство из них делает это) пять итераций на поток, а одна получает шесть итераций: 

--0-- --1-- --2-- ---3-- (thread number)
00011 12223 33444 555666 (values of i)
01201 20120 12012 012012 (values of j)

Как видите, теперь a[1] обрабатывается как потоком 0, так и потоком 1. Аналогично, a[3] обрабатывается как потоком 1, так и потоком 2. И у вас это есть - вы только что ввели зависимость данных, которая не было в предыдущем случае, так что теперь вы должны использовать atomic, чтобы предотвратить скачки данных. Цена, которую вы платите за синхронизацию, намного выше, чем выполнение одной итерации более или менее! В вашем случае, если вы свернете только два внешних цикла, вам вообще не нужно будет использовать atomic (хотя, в вашем конкретном случае, 4 делит 100, и даже при сворачивании всех циклов вам не нужно atomic, но вам это нужно в общем случае).

Другая проблема заключается в том, что после свертывания циклов существует один индекс l oop и оба индекса i и j имеют быть восстановленным из этого нового индекса с использованием операций деления и по модулю. Для простых тел l oop, подобных вашему, накладные расходы на восстановление индексов могут быть просто слишком высокими.

1 голос
/ 06 марта 2020

Очень мало веских причин не использовать библиотеку для умножения матрицы на матрицу, поэтому, как уже предлагалось, пожалуйста, позвоните в BLAS вместо того, чтобы писать это самостоятельно. Тем не менее, задаваемые вами вопросы не относятся c к умножению матрицы на матрицу, поэтому они заслуживают ответа в любом случае.

Здесь есть несколько вещей, которые можно улучшить:

  1. Используйте непрерывную память.
  2. Если K - самый внутренний l oop, вы создаете точечные продукты, которые сложнее векторизовать. Например, IKJ порядка l oop будет векторизоваться лучше.
  3. Если вы хотите распараллелить точечное произведение с OpenMP, используйте сокращение вместо многих атомик.

У меня есть каждый из этих методов проиллюстрирован ниже.

Непрерывная память 

int n = 100;
double * C = malloc(n*n*sizeof(double));
for(int i=0;i<n;i++){
  for(int j=0;j<n;j++){
    C[i*n+j] = 0.0;
  }       
}

IKJ l oop упорядочение 

for(int i=0;i<100;i++){
  for(int k=0;k<100;k++){
    for(int j=0;j<100;j++){
      C[i][j] = C[i][j]+ (A[i][k]*B[k][j]);
    }
  }
}

Параллельное скалярное произведение 

double x = 0;
#pragma omp parallel for reduction(+:x)
for(int k=0;k<100;k++){
  x += (A[i][k]*B[k][j]);
}
C[i][j] += x;

Внешние ресурсы

Как быстро написать числовой код: Небольшое введение охватывает эти темы гораздо более подробно.

BLISlab является превосходное руководство по c умножению матриц на матрицы, которое научит вас, как эксперты пишут вызов библиотеки BLAS.

1 голос
/ 23 февраля 2020
Операции

Atomi c на большинстве архитектур обходятся очень дорого по сравнению с операциями не-Atomi c (см. здесь , чтобы понять почему, или здесь для более подробного анализа). Это особенно верно, когда многие потоки осуществляют одновременный доступ к одной и той же области общей памяти. Проще говоря, одна из причин состоит в том, что потоки, выполняющие операции atomi c, не могут полностью работать параллельно, не ожидая других на большинстве аппаратных средств из-за неявной синхронизации и обмена данными, поступающими из протокола когерентности кэша. Другим источником замедлений является высокая задержка операций atomi c (опять-таки из-за иерархии кэша).

Если вы хотите писать хорошо масштабируемый код, вам нужно минимизировать синхронизацию и обмен данными (включая атомы). c операции). В результате использование collapse(2) намного лучше, чем collapse(3). Но это не единственная проблема - ваш код. Действительно, чтобы быть эффективными, вы должны выполнять постоянный доступ к памяти и хранить данные в кэшах как можно больше.

Например, поменяйте местами l oop, повторяющийся по i, и тот, что повторяется по k (который не работает с collapse(2)) в большинстве систем в несколько раз быстрее из-за более непрерывного доступа к памяти (примерно в 8 раз на моем P C): 

    for(int i=0;i<100;i++){
        //Initialize the arrays
        for(int j=0;j<100;j++){
            A[i][j] = i;
            B[i][j] = j;
            C[i][j] = 0;       
        }       
    }

    //Starting the matrix multiplication
    #pragma omp parallel num_threads(4)
    {
        #pragma omp for
        for(int i=0;i<100;i++){
            for(int k=0;k<100;k++){
                for(int j=0;j<100;j++){
                    C[i][j] = C[i][j] + (A[i][k]*B[k][j]);
                }
            }
        }
    }

Писать код быстрого умножения матриц нелегко. Попробуйте использовать библиотеки BLAS , такие как OpenBLAS , ATLAS , Eigen или Intel MKL , вместо написания собственного кода если ваша цель - использовать это в рабочем коде. Действительно, такие библиотеки очень оптимизированы и часто хорошо масштабируются на многих ядрах. Если ваша цель - понять, как писать эффективные коды умножения матриц, хорошей отправной точкой может стать чтение этого урока .

...