如何在块中生成组合

Question

我有算法,它对输入元素的每个组合执行计算,例如,对于100个元素集中的每个5元素子集.我将它移植到GPU,现在我准备好它的初始版本.为了加快速度,我想从本地内存加载数据,这是有限的(例如32KB)并且可以容纳20个输入元素中的100个.因此我必须以某种方式对我的工作进行分区并以块的形式生成组合.现在这是困难的部分,如何做到这一点.最有可能的是,我必须先为20个元素加载数据,然后对这20个元素的5个元素子集进行计算.在此之后,我将不得不用新的替换它们中的一些(或全部)并对它们进行计算,然后冲洗并重复.你能告诉我如何在本地内存中选择替换元素,以避免重复工作？到目前为止,我得出的结论是,我必须立即更换至少16个,以避免重复的工作问题.

编辑:这里是从5个元素中生成2元素组合的示例.以下是所有可能案例的完整列表:

1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5
3, 4
3, 5
4, 5

GPU上的本地内存有限 - 假设它只能容纳3个元素.因此,我必须以某种方式将我的问题分成3个元素中的2个元素的组合.我必须重复多次,直到我从上面的列表中获得所有组合.作为第一步,我可以将元素1,2,3加载到本地内存中,因此我将得到以下组合:

1, 2
1, 3
2, 3

现在我必须加载另一组元素并为它们计算组合.它可以是1,4,5.它将产生以下组合:

1, 4
1, 5
4, 5

另一方面,设置1,2,4无效 - 这将导致重复组合:

1, 2 // duplicate
1, 4 // ok, new
2, 4 // ok, new

在此步骤之后,还有4个要生成的组合(列表如下).算法必须能够从3个元素中生成另一个2元素组合,并以某种方式处理最后(第10个)组合.

2, 4
2, 5
3, 4
3, 5

通过以这种方式分割工作,我将能够使用有限的本地存储器处理原始输入集的所有组合,该存储器只能容纳其中的一部分.