Как распараллелить увеличение размера для цикла

Question

Вот наш фрагмент кода C ++, который мы хотим распараллелить на GPU:

#include <array>
#include <vector>
#include <bitset>

#include <cstdint>
#include <iostream>

#define NW 8 // use bitvectors of d=NW*32 bits, example NW=8

using namespace std;

using std::uint32_t; // 32-bit unsigned integer used inside bitvector
using std::size_t;   // unsigned integer for indices

// type for bitvector
typedef array<uint32_t, NW> bitvec_t;
typedef vector<bitvec_t> list_t;


void substract_list(const list_t& L)  {
// go over all unique pairs 0 <= j < i < L.size()
for (size_t i = 1; i < L.size(); ++i) {
    for (size_t j = 0; j < i; ++j) {
        size_t w = 0;

        for (size_t k = 0; k < NW; ++k) {
            w += an_array[i][k] - an_array[j][k];
        }
        cout << w;
    }
}

Наша цель - оптимизировать этот код и заставить его работать на GPU.В настоящее время мы не знаем, как это сделать, как распараллелить второй цикл for, поскольку этот цикл for увеличивается в размере, и это приведет к увеличению количества потоков, что не является оптимальным для программирования cuda.Итак, наш вопрос, возможно ли распараллелить увеличение цикла for, и если да, у вас, ребята, есть советы, как это сделать?

edit: добавлен дополнительный код.

Answer 1

Цикл может быть разложен на

// the first addition part
for (size_t i = 1; i < L.size(); ++i)
{
    for( size_t k = 0; k < NW; ++k )
    {
        w += i * an_array[i][k];
    }
}

// the second subtraction part
for (size_t i = 0; i < L.size(); ++i)
{
    for( size_t k = 0; k < NW; ++k )
    {
        w -= (size-1-i) * an_array[i][k];
    }
}

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

for (size_t i = 1; i < L.size(); ++i) 
{
    for (size_t j = 0; j < L.size(); ++j)
    {
        size_t w = 0;

        for (size_t k = 0; k < NW; ++k)
        {
             w += an_array[i][k] - an_array[j][k] * (threadIdx.x < i);
        }
    }
}