文章/答案/技术大牛

发布

社区首页 >问答首页 >如何使用OpenMP有效地并行化链表(使用任务？)

问如何使用OpenMP有效地并行化链表(使用任务？)
EN

Stack Overflow用户

提问于 2013-06-12 00:34:22

回答 2查看 2.1K关注 0票数 4

这是一个很长的帖子--在这个问题之前有很多背景知识。简而言之，我尝试在链表的元素上使用OpenMP --以我在其他地方见过的方式使用OpenMP任务，但这会导致明显的减慢。然而，如果我以不同的方式进行划分，我可以获得显着的加速，但我想知道是否有一种方法可以让第一种方法工作，因为它更干净/更简单，(我认为)它可以动态地平衡跨线程的工作。

我有一个相当长的Fortran类型(C结构)的链表(可以是几百万个元素)，并且--好几次--我必须遍历这个链表并对每个元素进行操作。所以，我有一个子例程(eachPhonon)，它将一个子例程作为参数(srt)，并对列表中的每个元素进行操作：

subroutine eachPhonon(srt)
  external :: srt
  type(phonon), pointer :: tptr

  tptr => head

  do while(associated(tptr))
    call srt(tptr)
    tptr => tptr%next
  enddo
endsubroutine

这似乎是一个并行加速的好地方，因为srt的每个调用都可以独立于其他调用完成。如果我有一个Fortran do (C for)循环，使用openmp就会非常简单。但是，我在stackoverflow和intel上都看到了如何使用链表完成此操作的方法。基本上，它使每个对srt的调用都有自己的任务--类似于：

subroutine eachPhonon(srt)
  external :: srt
  type(phonon), pointer :: tptr

  tptr => head

  !$OMP PARALLEL
  !$OMP SINGLE    
    do while(associated(tptr))
      !$OMP TASK FIRSTPRIVATE(tptr)
        call srt(tptr)
      !$OMP END TASK
      tptr => tptr%next
    enddo
  !$OMP END SINGLE
  !$OMP END PARALLEL
endsubroutine

这似乎是可行的，但它比只使用一个线程要慢得多。

我重写了一些东西，假设有4个线程，一个线程将在元素1，5，9上操作，另一个线程将在元素2,6,10...上操作，等等：

subroutine everyNth(srt, tp, n)
  external :: srt

  type(phonon), pointer :: tp
  integer :: n, j

  do while(associated(tp))
    call srt(tp)

    do j=1,n
      if(associated(tp)) tp => tp%next
    enddo
  enddo
endsubroutine

subroutine eachPhononParallel(srt)
  use omp_lib
  external :: srt

  type(phonon), pointer :: tp
  integer :: j, nthreads

  !$OMP PARALLEL
  !$OMP SINGLE
    nthreads = OMP_GET_NUM_THREADS()
    tp => head
    do j=1,nthreads
      !$OMP TASK FIRSTPRIVATE(tp)
        call everyNth(srt, tp, nthreads)
      !$OMP END TASK
      tp => tp%next
    enddo
  !$OMP END SINGLE
  !$OMP END PARALLEL
endsubroutine

这可能会导致显著的加速。

有没有办法让第一种方法变得高效？

我刚接触并行处理，但是我的理解是第一个方法有太多的开销，因为它试图为每个元素创建一个任务。第二种方法只为每个线程创建一个任务，并避免了该开销。缺点是不能在没有openmp的情况下编译的不那么干净的代码，并且它不会动态地平衡线程之间的工作--它在开始时都是静态分配的。

fortran

openmp

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-06-12 01:28:00

如果你的并行粒度太细，你可以尝试对更大的块进行操作：

subroutine eachPhonon(srt,chunksize)
  external            :: srt
  integer, intent(in) :: chunksize

  type(phonon), pointer :: tptr

  tptr => head

  !$OMP PARALLEL
  !$OMP SINGLE    
    do while(associated(tptr))
      !$OMP TASK FIRSTPRIVATE(tptr)
        ! Applies srt(tptr) chunksize times or until 
        ! associated(tptr)
        call chunk_srt(tptr,chunksize) 
      !$OMP END TASK
      ! Advance tptr chunksize times if associated(tptr)
      advance(tprt,chunksize) 
    enddo
  !$OMP END SINGLE
  !$OMP END PARALLEL
endsubroutine

这个想法是将chunksize设置为一个足够大的值，以掩盖与任务创建相关的开销。

票数 4

Stack Overflow用户

发布于 2013-06-12 03:05:56

速度减慢意味着srt()执行所需的时间太少，因此开销淹没了可能的并行加速。除了Massimiliano的解决方案之外，您还可以将链表转换为指针数组，然后对结果结构使用PARALLEL DO：

type phononptr
  type(phonon), pointer :: p
endtype phononptr

...

subroutine eachPhonon(srt)
  external :: srt
  type(phonon), pointer :: tptr
  type(phononptr), dimension(:), allocatable :: ptrs
  integer :: i

  allocate(ptrs(numphonons))

  tptr => head
  i = 1

  do while(associated(tptr))
    ptrs(i)%p => tptr
    i = i + 1
    tptr => tptr%next
  enddo

  !$OMP PARALLEL DO SCHEDULE(STATIC)
  do i = 1, numphonons
    call srt(ptrs(i)%p)
  enddo
  !$OMP END PARALLEL DO

endsubroutine

如果不在单独的变量(本例中为numphonons)中显式地保存列表项的数量，则必须遍历列表两次。phononptr类型是必需的，因为Fortran缺少一种更简单的方法来声明指针数组。

通过将Massimiliano的解决方案中的chunksize设置为numphonons / omp_get_num_threads()，也可以实现相同的目的。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/17049300

复制

相似问题

问如何使用OpenMP有效地并行化链表(使用任务？)
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用OpenMP有效地并行化链表(使用任务？)EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何使用OpenMP有效地并行化链表(使用任务？)
EN