并行化具有许多退出点的算法？

Question

我面临并行化算法,该算法在其串行实现中检查更大的三维数组中的一组数组位置的六个面.(也就是说,选择一个数组元素,然后在x,y和z之间的元素'n'元素周围定义一个立方体或长方体,由数组的边界限定.

每个工作单元看起来像这样(Fortran伪代码;串行算法在Fortran中):

do n1=nlo,nhi
  do o1=olo,ohi          
    if (somecondition(n1,o1) .eq. .TRUE.) then
       retval =.TRUE.
       RETURN
    endif    
  end do 
end do 

或C伪代码:

for (n1=nlo,n1<=nhi,n++) {
  for (o1=olo,o1<=ohi,o++) {
    if(somecondition(n1,o1)!=0) {
      return (bool)true;
    }
  }
}

在总算法中有六个这样的工作单元,其中'lo'和'hi'值通常在10到300之间.

我认为最好的方法是安排六个或更多的执行线程,如果没有那么多的CPU核心进行循环,理想情况是并行执行循环,其目标与串行算法相同:somecondition()成为True,所有线程之间的执行必须立即停止,并True在共享位置设置一个值.

Windows编译器中有哪些技术可以方便地并行化这样的任务？显然,我需要一个等待信号量或工作线程完成的主线程,因此需要嵌套和信令,但我对OpenMP的经验是在这一点上的介绍.

在OpenMP中是否有消息传递机制？

编辑:如果"nlo"和"nhi"或"olo"和"ohi"之间的最大差异为8到10,则表示此嵌套循环不超过64到100次迭代,并且不超过384到600次迭代六个工作单位在一起.基于此,是否值得并行化？

Answer 1

一种可能性是使用 OpenMP 并行化 6 个循环 - 声明logical :: array(6)，允许每个循环运行完成，然后retval = any(array)。然后您可以检查该值并返回并行循环之外。schedule(dynamic)如果这样做，请在并行 do 语句中添加一个。或者，单独放置一个!$omp parallel，然后将!$omp do schedule(dynamic)...放在!$omp end do nowait6 个循环中的每个循环周围。

或者，您可以遵循 @MSB 的好建议，并行化整个数组的最外层循环。这里的问题是你不能有一个RETURN并行循环的内部 - 所以标记第二个最外面的循环（并行部分中最大的一个），以及EXIT那个循环 - 类似

retval = .FALSE.
!$omp parallel do default(private) shared(BIGARRAY,retval) schedule(dynamic,1)
do k=1,NN
   if(.not. retval) then
      outer2: do j=1,NN
         do i=1,NN
            ! --- your loop #1
            do n1=nlo,nhi
               do o1=olo,ohi
                  if (somecondition(BIGARRAY(i,j,k),n1,o1)) then
                     retval =.TRUE.
                     exit outer2
                  endif
               end do
            end do
            ! --- your loops #2 ... #6 go here
         end do
      end do outer2
   end if
end do 
!$omp end parallel do

[编辑：该if语句假设您需要找出大数组中是否至少存在一个类似的元素。如果您需要计算每个元素的条件，您可以类似地添加虚拟循环退出或转到，跳过该元素的其余处理。再次，使用时间表（动态）或时间表（引导）。]

作为一个单独的点，您可能还想检查通过一些更大的步骤（取决于浮点数大小）遍历最内层循环是否是个好主意，在每次迭代上计算逻辑向量，然后聚合结果，例如。诸如此类if(count(somecondition(x(o1:o1+step,n1,k)))>0)；在这种情况下，编译器可能能够向量化somecondition.