하스켈의 투기적인 병렬 실행

Question

나는 해결하려고하는 한 가지 문제에 대해 병렬성을 이용하려고 생각하고있다. 문제는 대략 다음과 같습니다. 주어진 입력 (점의 순서)은 최상의 결과를 찾습니다 (가장 큰 삼각형은이 점들, 가장 긴 선들로 구성됩니다). 3 가지 '형태'가 포인트 시퀀스에서 발견되지만 '최고의 점수'(보통 '길이'시간 계수의 몇 가지 형태)가있는 것에 만 관심이 있습니다. S1, S2, S3 모양을 부르 자.

가 나는 S1 해결을위한 2 개의 다른 알고리즘이 - 'S1A가'O에 (N ²이), 'S1B는'대부분 잘 동작하지만 최악의 경우 O에 관한 것입니다 (N ⁴).

첫 번째 질문 : S1a와 S1b를 병렬로 실행하는 간단한 방법이 있습니까? 먼저 완료 한 것을 사용하고 다른 것을 중지하십시오. 지금까지 내가 문서를 읽는 동안, 이것은 몇 가지 forkIO를 사용하여 프로그래밍 할 수 있었고 결과가 얻어지면 쓰레드를 죽일 수있었습니다 - 더 간단한 것이 있는지 물어 보았습니까?

두 번째 질문 - 훨씬 강하다 : 나는 최적화 기능이 방법을 호출 오전 :

optimize valueOfSx input 

valueOfSx 모든 형태에 대한 구체적인이며, '점수'(또는 점수의 추측) 가능한 해결책을 반환합니다. 최적화는 최상의 솔루션을 찾기 위해이 함수를 호출합니다. 내가에 관심 것은 :

s1 = optimize valueOfS1 input 
s2 = optimize valueOfS2 input 
s3 = optimize valueOfS3 input 
<- maximum [s1,s2,s3] 

그러나, 나는 S1의 결과를 알고있는 경우에 더 좋은 솔루션 (또는 적어도 던져 존재하지 않는 경우, 나는 빠른 수렴을 따라서 S2 및 S3 만드는 작은 모든 솔루션을 삭제할 수 있습니다 멀리 떨어진 최악의 솔루션과 따라서 더 많은 공간을 효율적으로). 지금 내가하고있는 일은 다음과 같습니다.

zeroOn threshold f = decide .f 
    where decide x = if (x < threshold) then 0 else x 
s1 = optimize valueOfS1 input 
s2 = optimize (zeroOn s1 valueOfS2) input 
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input 

질문은 : S2와 S3을 병렬로 사용하면 다른 스레드에서 실행중인 스코어 함수의 'threshold'매개 변수를 먼저 업데이트하는 것이 좋습니다. 의 의미에서 뭔가 : 첫 번째 질문에 대한

threshold = 0 
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3)) 
update threshold from firstSolution 
wait for second solution 

Answer 1

궁극적으로 모든 솔루션은 여러 트랜잭션에서 발생하는 원하기 때문에 후드 ForkIO를 사용하여 바람합니다 평행. Conal의 조상조차도 이런 식으로 일합니다.

후자의 경우 단조롭게 게시 된 향상된 값을 위해 MVar를 확인하기 전에 일괄 처리 및 실행되는 좀 더 복잡한 모나드를 원하지만, 인터리브에 대한 가장 간단한 대답은 (한 스레드 내에서) 부분 모나드. 적절한 MonadFix 인스턴스와

data Partial a = Return a | Partial (Partial a) 

instance Monad Partial where 
    return = Return 
    Return a >>= f = f a 
    Partial m >>= f = Partial (m >>= k) 


run :: Partial a -> a 
run (Partial m) = run m 
run (Return a) = a 

race :: Partial a -> Partial a -> Partial a 
race (Return a) _ = a 
race _ (Return b) = b 
race (Partial m) (Partial n) = race m n 

yield :: Partial() 
yield = Partial (Return()) 

, 당신이 부분 모나드에서 두 가지 작업을 수행하고 결정적인 결과를 얻기 위해 그들을 경쟁 할 수 호출 재귀 또는 자유롭게 뿌려 '항복'을 처리합니다.

그러나 실제로는 병렬 처리의 이점을 최대한 활용하려면 MVar를 일종의 '개선'하고 주기적으로 확인해야합니다.

무언가 같이 (커프스에서, 죄송합니다, 편리한 컴파일러가 아닙니다!) :

import Control.Concurrent.MVar (newMVar, readMVar) 
import Control.Parallel.Strategies (using, parList) 
import GHC.IOBase (unsafeDupablePerformIO, unsafePerformIO) 

diag x = (x,x) 

parMax :: (Bounded a, Ord a) => [a] -> a 
parMax xs = unsafePerformIO $ do 
    threshold <- newMVar minBound 
    let optimize x = unsafeDupablePerformIO $ 
     x `seq` modifyMVar threshold (return . diag . max x) 
    return . maximum $ map optimize xs `using` parList 

당연히, 그것은 max가 아닌 모든 멱수가 변하지 않는 monoid를 지원하도록 다시 써야합니다.

Answer 2

는 확인 Conal 엘리엇의 unamb : http://hackage.haskell.org/package/unamb