当循环迭代不独立时使用OpenMP并行化循环

我有一个数字bessel过滤器的实现，这是我的程序的性能瓶颈。我想用OpenMP并行化主循环。当循环迭代不独立时使用OpenMP并行化循环

该函数获取输入数组paddedsignal和滤波器系数数组dcof和ccof，并生成一个临时数组temp，该数组被过滤。这个过程的主循环是这样的：

for (i=order; i<end; i++) 
    { 
     temp[i] = ccof[0]*paddedsignal[i]; 
     for (p=1; p<=order; p++) 
     { 
      temp[i] += ccof[p]*paddedsignal[i-p] - dcof[p]*temp[i-p]; 
     } 
    }

尤其注意，temp[i]价值取决于temp[i-p]以前的值。这混淆了一个简单的#pragma omp for指令，因为靠近数组各部分之间的边界的temp[i]值将由不同线程处理，其竞争条件问题。基本上，如果线程1的索引在0-99之间，线程2的线程需要100-199，那么100的值将会是错误的，因为它将在它所依赖的值99之前计算。

有没有办法挽救这种情况？由于过滤值依赖于相邻值这一事实使得它本身就是一个串行计算，所以我很遗憾我能做些什么来平行化。有没有办法解决？

来源

2017-02-10 KBriggs

这是一个序列计算。让速度更快的唯一方法是获得更快的CPU。另一种可能是使用更适合并行执行的不同类型的过滤器。或者，如果要过滤的数据可以以某种方式进行批处理，则可以通过不同的线程筛选不同的批次。 – bazza

我认为批处理过滤将是要走的路 – KBriggs

内循环可能像[前缀总和问题]（http://stackoverflow.com/a/35840595/2542702）？ –

由于您正确识别的依赖关系，您基本上无法并行化外部循环。

您可以通过减少来并行化内部循环。但是，这只对大order有帮助，甚至可能只是导致错误的共享，因为数据混乱了。人们可能会想出一个复杂的数据流，以便在线程间插入signal和temp，这需要分类 - 手动工作共享结构。无论如何，我怀疑它是否值得，因为减少会增加管理费用。

如果这是您的替代方案，那么对具有有限脉冲响应的滤波器进行并行化更容易。您也可以将整个信号分成稍微重叠的部分并独立计算滤波器，但在这些部分的边界处会出现一些计算错误。

来源

2017-02-10 22:51:21 Zulan

这或多或少是我的结论。我将不得不在其他地方寻找更加自然的地方进行并行化。代码已经实现了一个包装这个函数的块过滤策略，所以这可能是一个更自然的做法。 – KBriggs

也许您在寻找#pragma omp for 订购。它执行它会按顺序执行

但请记住以相同的顺序代码：

只能在的动态范围可用于指示
很“昂贵”（它可能是您的增速也不会如你想象的）

欲了解更多信息，请参阅： omp ordered

来源

2017-02-10 21:15:54 QuickSort

以多线程的方式强制执行串行操作有什么意义？加速从何而来？ – KBriggs

说实话，我从来没有使用过这个指令，因为我使用多线程只有当我有独立工作要做（不像你的例子）。但我可以记得，在某些情况下，合作伙伴项目的顺序I/O是有用的。如果你想了解更多有关订购条款的信息：http://stackoverflow.com/questions/13224155/how-does-the-omp-ordered-clause-work – QuickSort

'ordered'只有在你有重要的部分没有排序的迭代。对于这个过滤器，你将不得不几乎整个循环体，几乎连续化所有的东西。 – Zulan

当循环迭代不独立时使用OpenMP并行化循环

回答

相关问题