需要随机访问时改善随机存储器访问

我正在做的基本概念

完成联盟结构形成问题/组合拍卖。

给定一组N个代理，其中该代理集的不相交子集产生最佳结果。

例如， Agents = {a,b}及其值

• {a} = 2
• {b} = 3
• {a,b} = 4

在这种情况下， {{a},{b}} = 5的联盟将给出最佳结果，其中它是{a,b}的成对不相交子集。

因此，简而言之，问题在于拆分集合并检查任何拆分总和是否大于原始集合。 （这部分与生成分裂以及如何表示数据一样好。）

我如何表示数据基本上是一个值数组，其中索引是设置配置（一个集合表示为整数）。

对于上面的例子：

int val[4] = {0,2,3,4}其中set

• {a} = 01 = index 1
• {b} = 10 = index 2
• {a,b} = 11 = index 3

因此该集合充当值数组中的索引。

问题在于，这给出了随机存储器访问，给定了大量需要考虑2^n值的代理。

跳过这里的记忆访问问题

例如，在20个代理的环境中，给定两个元素10000000000000000001的集合，元素10000000000000000001的值是远离00000000000000000001的1048575个索引，其在内存中是4194300个字节，其表示32767个128字节距离的cachlines。 因此，可怕的访问模式。

我试过寻找的解决方案涉及按基数/汉明重量排序索引：

基于汉明重量的索引

确定两个整数之间的字典距离

遭受算术开销，我的计算将掩盖随机访问的惩罚。 特别是基于汉明重量的索引，因为它使用许多依赖计算，这些计算得到了加强并阻塞了线程。

作为最后的手段，我在这里再次提出，是否有任何方法（我知道合并，这对于这个问题很难做到），以改善您的解决方案在随机访问时不感兴趣的访问时间，还是无助状态？

目前我大约有45％的指令重放开销，并且更改块大小没有给出显着的结果。 是的，我尝试通过计算每个线程的几个联盟来隐藏延迟，这在某种程度上起作用。