Как распараллелить вложенные циклы с pthreads?

Question

Я хочу распараллелить вложенные циклы (у меня четыре ядра) в C с помощью pthreads. Внутри циклов я просто присваиваю одно значение каждому индексу двумерного массива.

Когда я пытался распараллелить его с четырьмя потоками, это фактически замедляет мою программу в 3 раза. Я думаю, это потому, что потоки каким-то образом блокируют друг друга.

Это цикл для распараллеливания.

for ( i = 0; i < 1000; i++ ) 
      {
        for ( j = 0; j < 1000; j++ )
        {
          x[i][j] = 5.432;
        }
      }

Я пытался распараллелить это следующим образом.

void* assignFirstPart(void *val) {
     for ( i = 1; i < 500; i++ )
    {
      for ( j = 1; j < 500; j++ )
      {              

        w[i][j] = 5.432;

      }
    }
}

void* assignSecondPart(void *val) {
     for ( ia = 500; ia < 1000; ia++ )
    {
      for ( ja = 500; ja < 1000; ja++ )
      {             

        w[ia][ja] = 5.432;


      }
    }
}

void* assignThirdPart(void *val) {
     for ( ib = 1; ib < 1000; ib++ )
    {
      for ( jb = 500; jb < 1000; jb++ )
      {            

        w[ib][jb] = 5.432;


      }
    }
}

void* assignFourthPart(void *val) {

     for ( ic = 500; ic < 1000; ic++ )
    {
      for ( jc = 500; jc < 1000; jc++ )
      {              

        w[ic][jc] = 5.432;                 

      }
    }
}

success = pthread_create( &thread5, NULL, &assignFirstPart, NULL );
    if( success != 0 ) {
        printf("Couldn't create thread 1\n");
        return EXIT_FAILURE;
    }

success = pthread_create( &thread6, NULL, &assignSecondPart, NULL );
    if( success != 0 ) {
        printf("Couldn't create thread 2\n");
        return EXIT_FAILURE;
    }

    success = pthread_create( &thread7, NULL, &assignThirdPart, NULL );
    if( success != 0 ) {
        printf("Couldn't create thread 3\n");
        return EXIT_FAILURE;
    }

success = pthread_create( &thread8, NULL, &assignFourthPart, NULL );
    if( success != 0 ) {
        printf("Couldn't create thread 4\n");
        return EXIT_FAILURE;
    }

pthread_join( thread5, NULL );
pthread_join( thread6, NULL );
pthread_join( thread7, NULL );
pthread_join( thread8, NULL );

Итак, как я уже сказал, параллелизация этого кода сильно замедляет мою программу, поэтому я, вероятно, делаю что-то совершенно не так. Я благодарен за любой совет.

Answer 1

assignThirdPart перекрывается с индексами двух предыдущих обратных вызовов. Ваши условия цикла не имеют большого смысла, вы должны разделить 1000 итераций самого внешнего цикла в 3, например:

for ( i = 0; i < 333; i++ ) // thread 1
...
for ( i = 333; i < 666; i++ ) // thread 2
..
for ( i = 666; i < 1000; i++ ) // thread 3
...

Также i = 1 не эквивалентно i = 0.

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

Что вы делаете, когда вмешиваетесь во внутренний итератор во время распараллеливания, так это то, что вы сегментируете всю область для копирования - вместо того, чтобы делать это линейно, у вас есть один поток, который копирует немного здесь, а другой немного там, что приводит к кешу кеширования полностью. Пожалуйста, прочитайте Почему порядок циклов влияет на производительность при итерации по двумерному массиву?

И, конечно же, есть накладные расходы на создание потоков, которые также следует учитывать при тестировании производительности.

Даже если все это сделано правильно, это не обязательно быстрее с 3 потоками. Многопоточность - это не какой-то волшебный порошок «всегда лучшая производительность», который вы можете посыпать любым произвольным кодом, чтобы ускорить его. Жевание 1000 выровненных фрагментов данных - это то, что высокопроизводительный процессор делает очень эффективно однопоточным.