Как объявить массивы в omp pragma

Question

Я изменяю существующую библиотеку из одного потока в многопоточность. У меня есть код, как показано ниже. Я не могу понять, как объявлять массивы x, y, array1, array2. Какой из них я должен объявить как share или threadprivate. Нужно ли использовать флеш. Если да, то в этом случае?

//global variables 
static int array1[100000]; 
static int array2[100000]; 

//part of program code from one of function. 
int i 
int x[1000000]; 
int y[1000000]; 

#pragma omp parallel for 
for(i=0, i<100; i++) 
{ 
    y[i] = i*i-3*i-10*random(); 
    x[i] = myfunc(i, y[i]) 
} 

//additional function 
int myfunc(j, z) 
int j, 
int z[] 
{ 
    array1[array2[j]] += z[j]+j; 
    return array1[j]; 
} 

Answer 1

Проблема, которую я вижу в вашем коде в этой строке

array1[array2[j]] += z[j]+j; 

Это означает, что array1 потенциально могут быть изменены по какой бы ни j индекса. И j в контексте функции myfunc() соответствует индексу i на верхнем уровне. Беда в том, что i - это индекс, на котором цикл распараллелен, поэтому это означает, что array1 может быть изменен одновременно в любой момент любым потоком.

Ключевой вопрос сейчас, чтобы знать, если array2 может иметь такое же значение для различных индексов:

• Если вы уверены, что для любой j1 != j2 у вас есть array2[j1] != array2[j2], то ваш код тривиальные параллелизуем.
• Если есть значения j1 != j2, для которых у вас есть array[j1] == array[j2], то у вас есть зависимости между итерациями для array1, и код больше не является (просто и/или эффективно) параллелизуемым.

Итак, давайте предположим, что мы находимся в первом случае, то директивы OpenMP вы уже в коде являются достаточно:

• i потребности быть private, но неявно уже так, как это индекс параллельного цикла;
• x и y должно быть shared (что они по умолчанию), поскольку их индекс доступа является распределенным параллельно (а именно i), поэтому их параллельные обновления не перекрываются;
• array2 доступен только в режиме чтения, так что это не проблема shared (что по умолчанию снова);
• array1 читается и записывается, но из-за нашего первоначального предположения нет возможных столкновений между потоками, поскольку их наборы индексов для доступа к нему расходятся. Поэтому по умолчанию shared квалификатор работает нормально.

Но теперь, если мы находимся в том случае, когда array2 позволяет без разъединять наборы индексов для доступа к array1, мы должны сохранять порядок этих заходов/обновления array1. Это можно сделать с помощью инструкции/директивы ordered. И поскольку мы все еще хотим, чтобы параллелизация была (в некоторой степени) эффективной, нам придется добавить пункт schedule(static,1) в директиву parallel. Для получения дополнительной информации об этом, пожалуйста, обратитесь к this great answer.Ваш код будет выглядеть следующим образом:

//global variables 
static int array1[100000]; 
static int array2[100000]; 

//part of program code from one of function. 
int i 
int x[1000000]; 
int y[1000000]; 

#pragma omp parallel for schedule(static,1) ordered 
for(i=0; i<100; i++) 
{ 
    y[i] = i*i-3*i-10*random(); 
    x[i] = myfunc(i, y[i]) 
} 

//additional function 
int myfunc(j, z) 
int j, 
int z[] 
{ 
    int tmp = z[j]+j; 
    #pragma omp ordered 
    array1[array2[j]] += tmp; 
    return array1[j]; 
} 

Это было бы (я думаю) работы и быть в перспективе параллельности не так уж плохо (для ограниченного числа потоков), но это имеет большой (огромный) недостаток: он генерирует тонны false sharing при обновлении x и y. Поэтому было бы выгоднее использовать некоторые потоковые копии этих файлов и только обновлять глобальные массивы в конце. Центральная часть фрагмента кода будет выглядеть примерно так (не проверено на всех):

#pragma omp parallel 
#pragma omp single  
int nbth = omp_get_num_threads(); 

int *xm = malloc(1000000*nbth*sizeof(int)); 
int *ym = malloc(1000000*nbth*sizeof(int)); 
#pragma omp parallel 
{ 
    int tid = omp_get_thread_num(); 
    int *xx = xm+1000000*tid; 
    int *yy = ym+1000000*tid; 
    #pragma omp for schedule(static,1) ordered 
    for(i=0; i<100; i++) 
    { 
     yy[i] = i*i-3*i-10*random(); 
     xx[i] = myfunc(i, y[i]) 
    } 
    #pragma omp for 
    for (i=0; i<100; i++) 
    { 
     int j; 
     x[i] = 0; 
     y[i] = 0; 
     for (j=0; j<nbth; j++) 
     { 
      x[i] += xm[j*1000000+i]; 
      y[i] += ym[j*1000000+i]; 
     } 
    } 
} 
free(xm); 
free(ym); 

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

BTW, факт, что i только петли до 100 выглядит подозрительно для меня, когда соответствующие массивы объявляются 1000000 длинными. Если 100 действительно правильный размер петли, то, вероятно, параллелизм не стоит в любом случае ...

---

EDIT:

Как Джим Cownie указал на это в комментариях, я пропустил вызов random() как источник зависимости между итерациями, предотвращая правильную параллелизацию. Я не уверен, насколько это актуально в контексте вашего фактического кода (я сомневаюсь, что вы действительно заполнили свой массив y случайными данными), но в случае, если вы это сделаете, вам придется изменить эту часть, чтобы сделать это параллельно (в противном случае сериализация, необходимая для генерации последовательности случайных чисел, просто убьет любое усиление от параллелизации). Но генерировать некоррелированные псевдослучайные ряды параллельно не так просто, как кажется. Вы можете использовать rand_r() вместо random() как альтернативу потоковой безопасности для RNG и инициализировать ее семена по потоку для разных значений. Тем не менее, вы не уверены, что серия одного потока не столкнется с другим потоком слишком рано (с потоком, который начинает генерировать ту же самую серию, что и другой, через некоторое время, испортив ожидаемое асимптотическое поведение).

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

Случай, когда никаких проблем не возникает из array2 (разъединять наборов индексов), код стал бы:

// global variable 
unsigned int seed; 
#pragma omp threadprivate(seed) 

// done just once somewhere 
#pragma omp parallel 
seed = omp_get_thread_num(); //or something else, but different for each thread 

// then the parallelised loop 
#pragma omp parallel for 
for(i=0; i<100; i++) 
{ 
    y[i] = i*i-3*i-10*rand_r(&seed); 
    x[i] = myfunc(i, y[i]) 
} 

Тогда в другом случае придется использовать тот же трюк, в дополнение к тому, что уже было описано , Но опять же, имейте в виду, что это недостаточно для серьезных вычислений на основе RNG (таких как методы Монте-Карло). Его выполняет задание, если все, что вам нужно, генерирует некоторые значения для целей тестирования, но не будет проходить серьезный статистический тест качества.