我正在做的基本概念
完成联盟结构形成问题/组合拍卖。
给定一组N个代理,其中该代理集的不相交子集产生最佳结果。
例如, Agents = {a,b}
及其值
在这种情况下, {{a},{b}} = 5
的联盟将给出最佳结果,其中它是{a,b}
的成对不相交子集。
因此,简而言之,问题在于拆分集合并检查任何拆分总和是否大于原始集合。 (这部分与生成分裂以及如何表示数据一样好。)
我如何表示数据基本上是一个值数组,其中索引是设置配置(一个集合表示为整数)。
对于上面的例子:
int val[4] = {0,2,3,4}
其中set
因此该集合充当值数组中的索引。
问题在于,这给出了随机存储器访问,给定了大量需要考虑2^n
值的代理。
跳过这里的记忆访问问题
例如,在20个代理的环境中,给定两个元素10000000000000000001
的集合,元素10000000000000000001
的值是远离00000000000000000001
的1048575个索引,其在内存中是4194300个字节,其表示32767个128字节距离的cachlines。 因此,可怕的访问模式。
我试过寻找的解决方案涉及按基数/汉明重量排序索引:
基于汉明重量的索引
确定两个整数之间的字典距离
遭受算术开销,我的计算将掩盖随机访问的惩罚。 特别是基于汉明重量的索引,因为它使用许多依赖计算,这些计算得到了加强并阻塞了线程。
作为最后的手段,我在这里再次提出,是否有任何方法(我知道合并,这对于这个问题很难做到),以改善您的解决方案在随机访问时不感兴趣的访问时间,还是无助状态?
目前我大约有45%的指令重放开销,并且更改块大小没有给出显着的结果。 是的,我尝试通过计算每个线程的几个联盟来隐藏延迟,这在某种程度上起作用。
以上就是c/c++开发分享需要随机访问时改善随机存储器访问相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562717.html