Комбинации целых чисел в OpenCL

Question

У меня есть куча векторов (~ 500). Мне нужно найти тройные продукты всех комбинаций векторов в OpenCL. В C++ есть много combination algorithms (r из n вещей), но я еще не нашел каких-либо реализованных для GPU. Я видел довольно много parallel permutation algorithms в Cuda, но я просто хочу знать, существуют ли какие-либо жизнеспособные алгоритмы комбинации?

Answer 1

Мне нужно угадать немного здесь и там, чтобы ответить на ваш вопрос.

Я полагаю, у вас есть массив V из векторов n (~ 500). Эти векторы имеют одинаковую размерность m (вероятно, m = 3).

То, что вы хотите, это компонент, мудрая продукт каждые 3 векторов v _я, v _J, v _к, где я, J, K в {0, .., п-1}.

Простой 3-мерный пример:

result[idx].x = V[i].x * V[j].x * V[k].x; 
result[idx].y = V[i].y * V[j].y * V[k].y; 
result[idx].z = V[i].z * V[j].z * V[k].z; 

Теперь, возможно, ваши векторы не 3-мерные и, возможно, вы не хотите, чтобы компонент мудрого продукт, но сумма его (как в скалярном произведении), но Я уверен, что вы можете соответствующим образом изменить код.

Настоящий вопрос заключается в том, как вычислить все возможные i, j, k и idx. Верный?

Теперь с CUDA вы находитесь в очень удачном положении. Вы можете просто запустить n * n * n потоков в сетке и, следовательно, бесплатно получить i, j, k, не задумываясь о способах вычисления комбинаций или перестановок вообще. Просто выполните следующие действия:

dim3 grid, block; 
block.x = n; 
block.y = 1; 
block z = 1; 
grid.x = n; 
grid.y = n; 
grid.z = 1; 

compute_product_kernel<<<grid, block>>>(V, result); 

Таким образом вы запустите n * n блоков из n потоков. Вычислительный я, J, K становится тривиальным, вычисление IDX легко:

__device__ void compute_product_kernel(myVector* V, myVector* result) 
{ 
    int i = blockIdx.x; 
    int j = blockIdx.y; 
    int k = threadIdx.x; 
    int idx = i * gridDim.y * blockDim.x + j * blockDim.x + k; 
    ... 
} 

Конечно все это работает только потому, что ваш п находится в пределах блока и сетки диапазона CUDA в. больше

Две вещей, хотя:

1. Может быть, вы хотите перестановки вместо комбинаций. Вы можете сделать это, пропустив каждую комбинацию, где любые два из i, j, k будут одинаковыми. Но я бы порекомендовал держать их в любом случае, потому что вычисление, когда пропустить, вероятно, дороже, чем выполнение реальной работы. Также я бы посоветовал использовать перестановку для сохранения памяти для result, потому что это спасло бы вас менее 1% и сделало бы вычисления более сложными.
2. Уверены, у вас достаточно памяти, чтобы на самом деле это сделать? Для сохранения результата требуются байты n * n * n * m * sizeof (float). При n = 500 и m = 3, которые уже были бы 1,5 ГБ. Это действительно то, что вы ищете? Возможно, следующий шаг вашей обработки можно объединить в расчет, чтобы не сохранять промежуточный результат.