어떻게 하스켈에서이 트리를 병렬로 줄일 수 있습니까?

Question

나는 리프에 일련의 값을 저장하는 간단한 트리와 테스트를 용이하게하는 몇 가지 간단한 함수를 가지고있다.

제한된 수의 프로세서가 있고 트리 균형이 잡히면 대수 결합 연산 (+, *, min, lcm)을 대수적으로 사용하여 트리를 줄일 수 있어야합니다.

Tree를 Foldable의 인스턴스로 만들면 기본 제공 함수를 사용하여 트리를 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로 순차적으로 줄일 수 있지만 선형 시간이 걸립니다.

하스켈을 사용하여 이와 같은 트리를 병렬로 줄이려면 어떻게해야합니까?

parCata fLeaf fNode = go where 
    go (Leaf z) = fLeaf z 
    go (Node l r) = gol `par` gor `pseq` fNode gol gor where 
     gol = go l 
     gor = go r 

그러나 심지어 cata의 관점에서 기록 될 수있다 :

cata fLeaf fNode = go where 
    go (Leaf z) = fLeaf z 
    go (Node l r) = fNode (go l) (go r) 

내가 평행 한 꽤 간단하게 적용 할 것입니다 가정 :

{-# LANGUAGE DeriveFoldable #-} 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
      deriving (Show, Foldable) 

toList :: Tree a -> [a] 
toList = foldr (:) [] 

range :: Int -> Int -> Tree Int 
range x y 
    | x < y  = Node (range x y') (range x' y) 
    | otherwise = Leaf x 
    where 
    y' = quot (x + y) 2 
    x' = y' + 1 

Answer 1

순진 배 이런 식으로 작성된 것입니다 :

parCata fLeaf fNode = cata fLeaf (\l r -> l `par` r `pseq` fNode l r) 

Answer 2

업데이트

원래 저감 작업이 비용이 많이 들지 않는다는 가정하에 질문에 답했습니다. 다음은 청크의 연관 감소를 n 요소로 수행하는 대답입니다. 병렬 평가를 할 수 있습니다

(op (op 1 2) (op 3 4)) (op 5 6) 

:이다

이 op가 연관 이항 연산이다 생각하고 foldr1 op [1..6]를 계산하려면, 여기로 평가하는 코드입니다. 당신이 연관 작업을 가지고 있기 때문에

import Control.Parallel.Strategies 
import System.TimeIt 
import Data.List.Split 
import Debug.Trace 

recChunk :: ([a] -> a) -> Int -> [a] -> a 
recChunk op n xs = 
    case chunksOf n xs of 
    [a] -> op a 
    cs -> recChunk op n $ parMap rseq op cs 

data N = N Int | Op [N] 
    deriving (Show) 

test1 = recChunk Op 2 $ map N [1..10] 
test2 = recChunk Op 3 $ map N [1..10] 

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

fib' n | trace msg False = undefined 
    where msg = "fib called with " ++ show n 
fib' n = fib n 

sumFib :: [Int] -> Int 
sumFib xs | trace msg False = undefined 
    where msg = "sumFib: " ++ show xs 
sumFib xs = seq s (s + (mod (fib' (40 + mod s 2)) 1)) 
    where s = sum xs 

main = do 
    timeIt $ print $ recChunk sumFib 2 [1..20] 

원래 대답

, 당신은 당신의 toList 기능을 사용하고 parMap 또는 parList과 병렬의 목록을 평가할 수 있습니다.

다음은 각 리프의 뼈대를 더하는 데모 코드입니다. 너무 많은 불꽃을 피하기 위해 parBuffer을 사용합니다. 나무가 작 으면 불꽃이 필요하지 않습니다.

-O2와 함께 GHC가 내 테스트 트리에서 일반적인 하위 표현식을 감지하고있는 것처럼 보였으므로 파일에서 트리를로드하고 있습니다.

또한 rseq을 필요에 맞게 조정하십시오. 누적되는 내용에 따라 rdeepseq이 필요할 수 있습니다.

{-# LANGUAGE DeriveFoldable #-} 

import Control.Parallel.Strategies 
import System.Environment 
import Control.DeepSeq 
import System.TimeIt 
import Debug.Trace 

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

fib' n | trace msg False = undefined 
    where msg = "fib called with " ++ show n 
fib' n = fib n 

data Tree a = Leaf a | Node (Tree a) (Tree a) 
      deriving (Show, Read, Foldable) 

toList :: Tree a -> [a] 
toList = foldr (:) [] 

computeSum :: Int -> Tree Int -> Int 
computeSum k t = sum $ runEval $ parBuffer k rseq $ map fib' $ toList t 

main = do 
    tree <- fmap read $ readFile "tree.in" 
    timeIt $ print $ computeSum 4 tree 
    return()