如何高效地使用OpenMP並行化鏈表（使用任務？）

這是一個很長的文章 - 很多背景之前的問題。快速版本是我嘗試在鏈接列表的元素上使用OpenMP - 以我在別處看到的方式使用OpenMP任務，但這會導致顯着的放緩。但是，如果我將事情分開的方式不同，我可以獲得顯着的加速，但是我想知道是否有辦法獲得第一種工作方式，因爲它更簡潔，並且（我認爲）它可以在線程間動態平衡工作。我有一個相當長的鏈表（可以是幾百萬個元素）的Fortran類型（C結構）和 - 幾次 - 我必須遍歷列表並對每個元素。所以，我有一個子程序（eachPhonon），其採用的子程序作爲參數（SRT）和運作，該列表中的每個元素：如何高效地使用OpenMP並行化鏈表（使用任務？）

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的情況下編譯，並且不會在線程間動態平衡工作 - 它在開始時都是靜態分配的。

來源

2013-06-11 lnmaurer

如果你並行的粒度太細，您可以嘗試在更大尺寸的大塊工作：

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-11 17:27:59 Massimiliano

謝謝，這聽起來像個好主意。 – lnmaurer

減速意味着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()來實現。

來源

2013-06-11 19:05:55

如何高效地使用OpenMP並行化鏈表（使用任務？）

回答

相關問題