Распараллеливание с потоками и блоками в CUDA - PullRequest
Новая
       24

Распараллеливание с потоками и блоками в CUDA

0 голосов
/ 12 декабря 2018

У меня есть следующие простые вложенные циклы 

float a[1024][1024], b[1024]

for(i=1; i < 1024; i++){
    for(j = 1; j < 1024 - i; j++){
        b[i + j] += a[i][j];    
    }
}

И я пытаюсь понять, как разделить эту проблему, используя потоки CUDA и блоки потоков для параллелизации с графическим процессором.До сих пор я считаю, что у меня в общей сложности N = 522753 вычислений.Я не совсем уверен, как действовать дальше: я знаю, что число потоков в каждом блоке должно быть кратно 32. Так, например, если число потоков в блоке равно 1024, то мне нужно по крайней мере 511 блоков, где каждый потокпринимает вычисление от 1 до> N. Может ли кто-нибудь объяснить, как выбрать лучшее число потоков в блоке и как на самом деле реализовать это параллельно.

1 Ответ

0 голосов
/ 12 декабря 2018

Длинный комментарий:

Редактировать: матрица c должна быть главной по столбцу, а не основной строкой, а сортировка должна быть по столбцам вместо строк, но я оставил ее в качестве основной строки здесь для удобства чтения.

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

c[0] = {1, &a[1][1],                   &b[2]}; // b[2]
c[1] = {2, &a[1][2],&a[2][1],          &b[3]}; // b[3]
c[2] = {3, &a[1][3],&a[2][2],&a[3][1], &b[4]}; // b[4]
..

, а затем отсортировать их (за один раз) по их числу индексов / размеру подмассива, чтобы они стали 

   c[0]    = {1, &a[1][1],         &b[2]}    //  b[2]
   c[1]    = {1, &a[1022][1],      &b[1023]} // b[1023]
   ..
   c[k]    = {5, x1,y1,z1,t1,w1,   &b[m]} // b[m]
   c[k+1]  = {5, x2,y2,z2,t2,w2,   &b[n]} // b[n]

сбалансированными по объему работы между потоками cuda основы / блока.

Затем перейдите к матрице c (1cuda thread на строку), чтобы узнать, какие элементы нужно сложить в простой цикл for для рабочего элемента. 

   const int length = (int)c[workitemId][0];
   for(int i=1;i<length+1;i++)
      resultOfWorkitem += *(c[workitemId][i]);
   *(c[workitemId][length+1])=resultOfWorkitem;

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

Если адрес произвольной записи становится проблемой с производительностью, вы можете отсортировать массив c по адресу последнего элемента (смежные индексы b), но это уменьшит баланс работы между соседними потоками cuda.Может быть, это быстрее, не проверял.Возможно, сортировка c по второму значению индекса a ускоряет его, уменьшая количество операций чтения, особенно когда вы сортируете элементы каждой строки между собой так, что они становятся непрерывными при чтениях соседних потоков, аналогично первой части 

 c[0] = {1, &a[1][1] // address x    \
 c[1] = {2, &a[1][2] // address x+1   > less than L1 cache line size 128byte?
 c[2] = {3, &a[1][3] // address x+2  /

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

...