并行移除阵列中的元素

Question

我正在尝试执行并行版本STL remove_if。我所做的是在全局内存中创建一个计数器，并让每个线程在一个元素上工作。如果该元素不等于该键，那么它将被复制到结果数组中，其索引由计数器通过原子添加确定。有没有更好的选择来避免频繁的原子操作？

我发现，推力库还具有的remove_if，但我觉得对位于源代码“推力\详细\后端\ CPP \ remove.h”目录很困惑：

template<typename ForwardIterator, 
    typename InputIterator, 
    typename Predicate> 
ForwardIterator remove_if(ForwardIterator first, 
         ForwardIterator last, 
         InputIterator stencil, 
         Predicate pred) 
{ 
// advance iterators until pred(*stencil) is true or we reach the end of input 
while(first != last && !bool(pred(*stencil))) 
{ 
    ++first; 
    ++stencil; 
} 

if(first == last) 
    return first; 

// result always trails first 
ForwardIterator result = first; 

++first; 
++stencil; 

while(first != last) 
{ 
    if(!bool(pred(*stencil))) 
    { 
     *result = *first; 
     ++result; 
    } 
    ++first; 
    ++stencil; 
} 

return result; 
} 

这不是按顺序执行元素删除吗？

感谢您的任何建议！

Answer 1

除非您有充足的理由推出自己的实现，否则我建议您只使用Thrust remove_if（）。 Thrust模仿STL，如果你对通用性的要求是相似的，那么你最终会写出与Thrust源代码非常相似的代码。

如果Thrust的性能不理想，Thrust社区（包括主要作者）可能会对如何制定代码以获得更好的性能提供很好的建议。

失败 - 如果您有一个垂直应用程序且Thrust速度不够快 - 请将基于扫描的实施作为最后的手段进行滚动。该算法的单行摘要是对谓词的反向执行并行前缀和（“scan”） - 然后，您要保留的元素的输出索引由扫描的相应元素指定。