2

我在做什么的基本概念

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

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

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

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

在这种情况下， 的联合会{{a},{b}} = 5给出最好的结果，它是 的成对不相交子集{a,b}。

所以简而言之，问题是关于拆分一个集合并检查是否有任何拆分总和大于原始集合。（这部分在生成拆分和我如何表示我的数据方面做得很好。）

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

对于上面的例子：

int val[4] = {0,2,3,4}在哪里设置

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

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

问题是这提供了随机内存访问，给定大量2^n需要考虑值的代理。

跳过内存访问问题

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

我尝试寻找的解决方案涉及根据基数/汉明权重对索引进行排序：

基于汉明权重的索引

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

遭受算术开销，我的计算将掩盖随机访问的惩罚。特别是基于 Hamming 权重的索引，因为它使用许多相关计算，这些计算会被序列化并阻塞线程。

作为最后的手段，我再次在这里问，当您的解决方案依赖于随机访问或者它是一种无助的状态时，是否有任何方法（我知道合并，这对于这个问题很难做到）来改善访问时间？

目前，我的指令重播开销约为 45%，因此更改块大小不会产生显着的结果。是的，我尝试通过计算每个线程的多个联盟来隐藏延迟，这在一定程度上起作用。

4

0 回答 0