увеличение числа потоков на xcode увеличивает время программы

Question

Я новичок в openmp и в настоящее время пытаюсь распараллелить умножение матриц в xcode на mac.

Результат, который я получаю, странный, потому что он увеличивает время моей программы, а не уменьшает его.Я предполагаю, что это происходит потому, что он использует только одно ядро ​​и не использует другие ядра, вот мой код:

omp_set_num_threads(4);
#pragma omp parallel for private(i,j,k)
for (i=0; i<n; ++i) {
        for (j=0; j<n; ++j) {
               for (k=0; k<n; ++k) {
                    c[i][j] += a[i][k] * b[k][j];
               }
        } 
}

на двух матрицах 400 * 400 с 1 потоком, я получаю 551 мс, с 2 потоками421 и с 3 потоками 678, и это увеличивается, поскольку я увеличиваю свои темы.

есть идеи, что я делаю неправильно или что я должен делать?!

Answer 1

Вы используете плохой метод для умножения ваших матриц. Алгоритм ijk генерирует много ошибок кэша. Посмотри на свою внутреннюю петлю. Всякий раз, когда ваш индекс k изменяется, вы переходите на новые строки матрицы b вместо того, чтобы использовать дружественный кешу обход по строке. И это большое количество пропусков кеша снижает вашу производительность и более неприятно для параллельного кода из-за алгоритмов когерентности кеша. Алгоритм ikj (см. Код ниже) намного лучше. Все матрицы проходят через главную строку и не генерируют пропуски в кеше.

Я пытался поэкспериментировать с вашим кодом.

Чтобы иметь постоянную синхронизацию, я делаю 10 циклов умножения матриц, и я делаю это 10 раз, и я держу самое низкое время.

В зависимости от определений можно выбрать ijk или ikj и управлять параллелизмом.

Другое определение выберите параллельную или последовательную версию.

#include <stdio.h>
#include <omp.h>
#include <stdlib.h>

int main() {
    double a[400][400], b[400][400], c[400][400] = { { 0.0 } };
    int i, j, k, n = 400;

    double t1, t2,t;

    srand(100); // better be deterministic when benchmarking
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            a[i][j] = rand() / (double) RAND_MAX;
            b[i][j] = rand() / (double) RAND_MAX;
        }
    }

    t=1E100;
    for(int ll=0;ll<10;ll++){      
      t1 = omp_get_wtime();
      for(int mm=0;mm<10;mm++){
#if THREADS>1
#pragma omp parallel for private(i,j,k) num_threads(THREADS)
#endif
#ifdef ijk
        for (i=0; i<n; ++i) {
          for (j=0; j<n; ++j) {
            for (k=0; k<n; ++k) {
              c[i][j] += a[i][k] * b[k][j];
            }
          } 
        }
#else // ikj matrix multiplication
        for (i=0; i<n; ++i) {
          for (k=0; k<n; ++k) {
            double r=a[i][k];
            for (j=0; j<n; ++j) {
              c[i][j] += r * b[k][j];
            }
          } 
        }
#endif      
      }
      t2 = omp_get_wtime();
      if (t>t2-t1) t=t2-t1;
    }

    printf("%g\n",t);

    // to fool these smart optimizers, do something with c
    FILE* devnull=fopen("/dev/null","w");
    fprintf(devnull,"%g\n",c[0][0]);
    return EXIT_SUCCESS;
}

Теперь эксперименты:

Сначала с ijk

am@Mandel$ cc -fopenmp -O3 -march=native -DTHREADS=0 -Dijk omp2.c; ./a.out
0.196313
am@Mandel$ cc -fopenmp -O3 -march=native -DTHREADS=4 -Dijk omp2.c; ./a.out
0.293023

И мы видим, что параллельная версия на 50% медленнее.

Теперь переключаемся на ikj

am@Mandel$ cc -fopenmp -O3 -march=native -DTHREADS=0 -Uijk omp2.c; ./a.out
0.114659
am@Mandel$ cc -fopenmp -O3 -march=native -DTHREADS=4 -Uijk omp2.c; ./a.out
0.06113

Теперь последовательный код в два раза быстрее, а параллельная версия в два раза быстрее последовательного.

Вероятно, с помощью больших матриц вы можете повысить эффективность параллельного кода.

Answer 2

Ваша большая ошибка - попытаться распараллелить умножение матриц. Не потому, что это невозможно, а потому, что это уже было сделано (наряду с другими важными оптимизациями, такими как блокировка кэша и векторизация, с которыми вам, вероятно, не обойтись).

Запомните ключевую фразу: «Лучший код - это код, который мне не нужно писать»: -)

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

( Intel MKL хорош и бесплатен для всех, так что это разумный выбор, но есть много других вариантов, которые Google может найти для вас).

Полное раскрытие: я работаю на Intel, но не на MKL.

Answer 3

есть идеи, что я делаю неправильно или что я должен делать?!

Не похоже, что вы делаете что-то особенно неправильное в том, что касается вашего кода. Однако многопоточность несет накладные расходы как на уровне программного обеспечения, так и на уровне оборудования. В результате применение большего количества потоков к проблеме не всегда ускоряет общее вычисление и может замедлить его. То, как это влияет на конкретную задачу, зависит от деталей этой задачи, а также от архитектуры хоста и среды.

Тем не менее, рассмотрим эту полную тестовую программу, построенную на вашем примере кода:

#include <stdlib.h>

int main() {
    double a[400][400], b[400][400], c[400][400] = { { 0.0 } };
    int i, j, k, n = 400;

    srand(time(NULL));
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            a[i][j] = rand() / (double) RAND_MAX;
            b[i][j] = rand() / (double) RAND_MAX;
        }
    }

    #pragma omp parallel for private(i,j,k) num_threads(4)
    for (i=0; i<n; ++i) {
        for (j=0; j<n; ++j) {
           for (k=0; k<n; ++k) {
               c[i][j] += a[i][k] * b[k][j];
           }
        } 
    }

    return EXIT_SUCCESS;
}

Я использую предложение num_threads для конструкции parallel for вместо вызова omp_set_numThreads() для установки запрошенного числа потоков, но в остальном область OMP идентична вашей. Скорее всего, с помощью команды time в моей собственной системе Linux я вижу, что истекшее время уменьшается с числом потоков, демонстрирующих почти линейное ускорение, до примерно четырех потоков. После этого с пятым потоком происходит небольшое ускорение, а истекшее время и суммарное время ЦП начинают увеличиваться в шести потоках.

Эти результаты, вероятно, связаны с тем фактом, что на моей машине установлено шесть физических ядер ЦП, а ОС и различные фоновые процессы постоянно потребляют определенное количество ресурсов ЦП. То, что ваши результаты не соответствуют той же схеме, может быть связано с остальной частью вашей программы, или с вашей средой, или с вашей конкретной реализацией OpenMP. Это может даже быть связано с тем, как вы проводите свои временные испытания. Это не потому, что регион OpenMP, который вы представили, имеет недостатки.