내 haskell 병렬 코드의 모든 병렬 처리를 악용하는 방법은 무엇입니까?

Question

저는 GHC 6.12와의 haskell semi-explicit 병렬 처리에 대해 언급 한 바 있습니다. 필자는 다음과 같은 haskell 코드를 작성하여 fibonnaci 함수의 맵을 목록의 4 개 요소에 대해 계산하고 동시에 두 개의 요소에 sumEuler 함수의 맵을 계산했습니다.

import Control.Parallel 
import Control.Parallel.Strategies 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

mkList :: Int -> [Int] 
mkList n = [1..n-1] 

relprime :: Int -> Int -> Bool 
relprime x y = gcd x y == 1 

euler :: Int -> Int 
euler n = length (filter (relprime n) (mkList n)) 

sumEuler :: Int -> Int 
sumEuler = sum . (map euler) . mkList 

-- parallel initiation of list walk                                  
mapFib :: [Int] 
mapFib = map fib [37, 38, 39, 40] 

mapEuler :: [Int] 
mapEuler = map sumEuler [7600, 7600] 

parMapFibEuler :: Int 
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler)) 

-- how to evaluate in whnf form by forcing                                 
forceList :: [a] ->() 
forceList [] =() 
forceList (x:xs) = x `pseq` (forceList xs) 


main = do putStrLn (" sum : " ++ show parMapFibEuler) 

내가 파 및 pseq 및 whnf 평가를 강제로 강제 기능을 다시 썼다 병렬로 내 프로그램을 향상시킬 수 있습니다. 내 문제는 그것이 모든 병렬 처리를 얻지 못했을 것으로 나타납니다 threadscope에서 찾고 있습니다. 내가 어떤 속도 향상도 얻지 못했기 때문에 상황이 더 나 빠졌다.

나는 이유는 두 가지 질문

을 논제 그건

질문 1 어떻게 어떤 병렬 처리를 이용하려면 코드를 수정할 수?

질문 2 전략 (parMap, parList, rdeepseq 등 ...)을 사용하려면 어떻게 프로그램을 작성할 수 있습니까? 그의 기여 상당한 속도 향상

Answer 1

귀하의 병렬 처리는 너무 많은 유익한 효과를 가질 물론 그레인입니다. 효율적으로 병렬로 수행 할 수있는 가장 큰 작업은 sumEuler이므로 par 주석을 추가해야합니다. 에 sumEuler을 변경해보십시오 :

sumEuler :: Int -> Int 
sumEuler = sum . (parMap rseq euler) . mkList 

parMap이 Control.Parallel.Strategies에서이다; 병렬로 수행 할 수있는 맵을 표현합니다. 첫 번째 인수 인 rseq은 유형이 이고 계산을 특정 지점으로 강제 실행합니다. 그렇지 않으면 게으름으로 인해 작업이 수행되지 않습니다. rseq은 대부분의 숫자 유형에 적합합니다.

여기서 fib에 병렬을 추가하는 것은 유용하지 않습니다. 아래의 약 fib 40은 가치가있는 작업이 충분하지 않습니다.

threadscope 외에도 -s 플래그로 프로그램을 실행하는 것이 좋습니다. 다음과 같은 행을 찾으십시오.

SPARKS: 15202 (15195 converted, 0 pruned) 

출력 각 스파크는 작업 대기열의 항목으로 병렬로 수행 될 수 있습니다. 변환 된 스파크는 실제로 병렬로 수행되는 반면, 정리 된 스파크는 작업자 스레드가 그렇게 할 기회를 갖기 전에 주 스레드가이 스레드에 도달했음을 의미합니다. 프 i 된 숫자가 높으면 병렬 표현식이 너무 세밀 함을 의미합니다. 스파크의 총수가 낮 으면, 당신은 충분히 병렬로 노력하지 않습니다.

마지막으로, 나는 parMapFibEuler이 더 잘 작성된 것입니다 생각 :

parMapFibEuler :: Int 
parMapFibEuler = sum (mapFib `using` parList rseq) + sum mapEuler 

mapEuler 단순히 euler가 이미 병렬로 수행되고 특히, 어떤 병렬 유용하게 여기 표현이 너무 짧습니다. 나는 mapFib에 대해서도 상당한 차이가 있는지 의심 스럽다. 목록 mapFib과 mapEuler이 길면 병렬 처리가 더 유용 할 것입니다. parList 대신 parBuffer을 사용할 수 있는데 이는 목록 소비자에게 적합합니다.

GHC 7.0.2를 사용하여이 두 가지 변경 사항을 적용하면 런타임이 12 초에서 8 초로 단축되었습니다.

Answer 2

음을 가질 정도로

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where 
    s = parTuple2 (seqList rseq) (seqList rseq) 

병렬 처리가 threadscope에 나타납니다하지만에 따라 전략

와

먼저 개선. .. 아마도?

((forceList mapFib) `par` (forceList mapEuler)) `pseq` (sum mapFib + sum mapEuler) 

.l.e. 백그라운드에서 mapFib을 알리고 mapEuler을 계산하고 그 다음에야 (mapEuler) (+)을 계산하십시오. 내가 전략을 아시는 바와 같이 -은 "전략"par 및 seq 사람들과 데이터 구조를 결합하는 것입니다 : Q2에 대해

parMapFibEuler = a `par` b `pseq` (a+b) where 
    a = sum mapFib 
    b = sum mapEuler 

: 사실 난 당신이 뭔가를 할 수있는 것 같아요.
당신은 당신과 같은 코드를 작성할 수 있습니다뿐만 아니라 당신의 forceList = withStrategy (seqList rseq)
을 작성할 수 있습니다

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where 
    s = parTuple2 (seqList rseq) (seqList rseq) 

을 즉 두 목록의 튜플에 적용된 전략은 병렬로 결과를 추출하지만 각 목록은 순차적으로 평가해야합니다.

Answer 3

먼저, fib 정의가 끔찍하다는 것을 알고 있다고 가정합니다. 병렬 패키지로 재생하려면이 작업을 수행하는 것뿐입니다.

잘못된 수준에서 병렬 처리를 수행하는 것 같습니다. mapFib을 병렬 처리하면 mapFib을 계산하는 작업이 더 많으므로 속도가 향상되지 않습니다.당신이해야 할 것은 약간의 미세한 입자 인 병렬이 매우 비싼 요소의 각을 계산이다하지만 지나치게 너무 : 또한

mapFib :: [Int] 
mapFib = parMap rdeepseq fib [37, 38, 39, 40] 

mapEuler :: [Int] 
mapEuler = parMap rdeepseq sumEuler [7600, 7600, 7600,7600] 

parMapFibEuler :: Int 
parMapFibEuler = sum a + sum b 
    where 
    a = mapFib 
    b = mapEuler 

, 나는 원래 Control.Parallel 이상 Control.Parallel.Strategies를 사용하여 싸웠다하지만 온 더 읽기 쉽고 자신이 좋아하는 것과 같은 문제를 피할 수 있기 때문에 좋아합니다. 평행성을 기대하고 왜 그것을 얻지 못하는지 알아 내려고합니다.

마지막으로 항상 컴파일 방법과 병렬 처리 할 코드를 실행하는 방법을 게시해야합니다.

$ ghc --make -rtsopts -O2 -threaded so.hs -eventlog -fforce-recomp 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
$ ./so +RTS -ls -N2 
sum : 299045675 

수익률 : 예를 들어

Answer 4

여기에서 병렬 처리가 표시되지 않는 이유는 스파크가 가비지 수집 되었기 때문입니다.

SPARKS: 1 (0 converted, 1 pruned) 

가 스파크가 "비우기"한 가비지 수집기 제거 수단이 라인 +RTS -s으로 프로그램을 실행하고 있습니다. GHC 7에서는 스파크의 의미에 변화를주었습니다. 프로그램의 나머지 부분에서 스파크가 참조되지 않으면 스파크가 이제 가비지 수집됩니다 (GC'd). 자세한 내용은 the "Seq no more" paper입니다.

왜 귀하의 경우에 스파크 GC가 실행됩니까? 코드를 살펴 :

parMapFibEuler :: Int 
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler)) 

여기 스파크는 표현 forkList mapFib입니다. 이 표현식의 값은 나머지 프로그램에서는 필요하지 않습니다. par의 인수로만 나타납니다. GHC는 그것이 필수적이지 않다는 것을 알고 있으므로 가비지 수집됩니다.

parallel 패키지의 최근 변경 사항의 요점은이 베어 트랩을 쉽게 피할 수있게하는 것이 었습니다. Thumb의 좋은 규칙은 par 및 pseq 대신 Control.Parallel.Strategies을 직접 사용하는 것입니다. 이 작성하는 내 선호하는 방법은

parMapFibEuler :: Int 
parMapFibEuler = runEval $ do 
    a <- rpar $ sum mapFib 
    b <- rseq $ sum mapEuler 
    return (a+b) 

될하지만 스파크 sum mapFib 정적 표현 (카페)로 밖으로 부유하기 때문에 슬프게도이, GHC 7.0.2 작동하지 않으며, 런타임하지 않습니다 정적 표현을 가리키는 불꽃은 생각할 가치가 있다고 생각합니다. (저는 이것을 고칩니다). 물론 이것은 실제 프로그램에서 발생하지 않습니다! 그래서이 프로그램이 좀 더 현실적인 할 수 있도록하고, CAF 최적화 패배 :

parMapFibEuler :: Int -> Int 
parMapFibEuler n = runEval $ do 
    a <- rpar $ sum (take n mapFib) 
    b <- rseq $ sum (take n mapEuler) 
    return (a+b) 

main = do [n] <- fmap (fmap read) getArgs 
      putStrLn (" sum : " ++ show (parMapFibEuler n)) 

가 지금은 GHC 7.0.2로 좋은 병렬 처리를 얻을 수 있습니다. 그러나 @ John의 주석도 적용됩니다. 일반적으로 GHC가 모든 프로세서를 사용할 수 있도록보다 세분화 된 병렬 처리를 원합니다.