Syn*_*ose 6 c++ algorithm parallel-processing c++11
我目前正在制定一个开放式的提议,为我正在开发的项目带来并行功能,但我遇到了一个障碍find_end.
现在find_end可以描述为:
一种算法,用于搜索[first,last]范围内元素[s_first,s_last]的最后一个子序列.第一个版本使用operator ==来比较元素,第二个版本使用给定的二元谓词p.
它的要求由cppreference列出.现在我没有问题并行find/ findif/ findifnot等等.这些可以很容易地分成异步执行的单独分区,我没有遇到任何麻烦.问题find_end是将算法拆分成块不是解决方案,因为如果我们说一个向量:
1 2 3 4 5 1 2 3 8
我们想要搜索1 2.
好的,首先我将矢量异步分隔成块,然后只搜索每个块中的范围吧？看起来很容易,但是如果由于某种原因只有3个可用内核会发生什么,所以向量分为3个块:
1 2 3| 4 5 1|2 3 8
现在我遇到了问题,第二个1 2范围被分成不同的分区.这将导致许多无效结果,因为有些x核心最终会将搜索结果拆分为y不同的分区.我想我会search chunks -> merge y chunks into y/2 chunks -> search ->在递归样式搜索中做某种事情,但这看起来效率很低,这个算法的重点是提高效率.我也许会过度思考这种折磨
tl; dr,有没有办法以find_end我不想的方式并行化？
是的,有一种方法.
我们N是你正在寻找的范围的大小.
一旦你将矢量分成3个块(3个独立的工作线程):
1 2 3|4 5 1|2 3 8
您可以允许每个线程在其右侧相邻块(如果有)上运行N-1个元素(因为序列只涉及读取操作,这非常好并且是线程安全的).
在这种情况下:(N = 2)
核心1继续运行 1 2 3 4
核心2继续运行 4 5 1 2
核心3继续运行 2 3 8