如何并行化增加循环的大小

Question

这是我们想要在GPU上并行化的一段C ++代码：

#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 循环，如果是这样，你们有关于如何做到这一点的提示吗？

编辑： 添加了额外的代码。

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-loop 这样的循环，你可以将 if 语句乘以这些计算。在 GPU 上，这种方法比 if 更快。这可能看起来像

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);
}
}
}