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就无法编译的代码不太干净，而且它不会动态平衡线程之间的工作——它们都是在开始时静态分配的。

4

2 回答 2

4

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

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一个足够大的值来掩盖与任务创建相关的开销。

于 2013-06-11T17:27:59.917 回答
2

减速意味着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 缺少一种更简单的方法来声明指针数组。

同样也可以通过将chunksizeMassimiliano 的解设置为来实现numphonons / omp_get_num_threads()。

于 2013-06-11T19:05:55.503 回答