Haskellerへの道 #26 - 並列処理

この記事では、Haskell におけるsparkを使った並列処理の実装方法を紹介します。

並列処理と決定性

これまで、手動でスレッドを作成してきましたが、それらはHaskell Execution Context (HEC) によって非決定的な順序で実行されます。この非決定的な並列処理のため、ミューテックスやチャネル、セマフォ、STM（ソフトウェアトランザクショナルメモリ）を使って通信と同期を設定し、どのシステムや順序でも競合が発生しないようにする必要がありました。しかし、プログラムが複雑になるにつれて、変数の数は急速に増加してしまいます。

代わりに、プログラムの実行順序を指定し、適切なスレッドを指定された順序で作成するタスクをランタイムシステム (RTS) に委任することで、決定性のある並列処理を使用することができ、通信や同期を使わずに競合を回避できます。RTS にスレッドへ変換してもらいたい計算単位を「スパーク」と呼び、Haskell コード内でスパークをどのように生成するかの戦略をプログラムだけで、RTSが並列処理を簡単に行なってくれます。

戦略

Haskellモジュール Control.Parallel.Strategies では、スパークを生成するための戦略は Strategy を使って表現されます。これは、スパークaを変換した後に評価を含む Eval モナドEval aに変換するモナディック関数です。

-- モジュールは以下のコマンドをコマンドラインで使用してインストールします：
-- cabal install parallel
import Control.Parallel.Strategies
 
type Strategy a = a -> Eval a

Strategy はモナディック関数として構築されているため、小さな戦略を組み合わせて戦略を構築できたり、STM のように IO などの副作用を明確に分離したりすることができます。戦略によって、a を Eval a に変換する方法は異なります。以下はモジュール内で利用可能な戦略です。

-- 並列で評価可能なスパークを生成する
rpar :: Strategy a
 
-- 次のスパークが生成される前に WHNF まで評価される必要があるスパークを生成する
rseq :: Strategy a
 
-- 次のスパークが生成される前に NF まで評価される必要があるスパークを生成する
rdeepseq :: Strategy a
 
-- Evalから評価を取得する
runEval :: Eval a -> a
 
-- 使用例
runEval $ do
    a <- rpar (f a) -- 並列で評価可能
    b <- rseq (f b) -- WHNF まで評価された後に進む必要がある
    return (a, b)

rpar（run in parallel, 並列実行）は f a スパークの評価を他のスパークと並列で実行できるようにし、 rseq（run sequentially, 順次実行）は f b スパークの評価を WHNF に強制し、順次実行されます。これにより、return (a, b) は b が評価された後にのみ実行されますが、a が評価される必要はありません。競合が発生する可能性がある場合、rseq や rdeepseq を使用して評価を取得して順序を指定することができます。戦略を使用することで、決定性のある並列処理を用いることができ、f 内で通信や同期の設定をしなくても済んでいることが伺えます。

例

スパークの生成に関する戦略を理解するために、いくつかの例を見てみましょう。

rparPair :: Strategy (a, b)
rparPair (a, b) = do
    a' <- rpar a
    b' <- rpar b
    return (a', b')
 
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
 
main :: IO ()
main = do
    let (a, b) = runEval . rparPair $ (fib 20, fib 30)
    putStrLn $ "Tuple: " ++ show (a, b)

この例は、事前定義された戦略を使用してタプルの新しい戦略を作成する方法を示しています。任意のペア戦略を受け取り、それを適用する高階戦略も作成できます。

evalPair :: Strategy a -> Strategy b -> Strategy (a, b)
rparPair sa sb (a, b) = do
    a' <- sa a
    b' <- sa b
    return (a', b')
 
main :: IO ()
main = do
    let (a, b) = runEval . evalPair $ rseq rseq (fib 20, fib 30)
    putStrLn $ "Tuple: " ++ show (a, b)

次のように、using 構文を使って、より読みやすくすることができます。これは runEval (s x) に相当します。

-- using :: a -> Strategy a -> a
-- x `using` s = runEval (s x)
 
main :: IO ()
main = do
    let (a, b) = (fib 20, fib 30) `using` evalPair rseq rseq 
    putStrLn $ "Tuple: " ++ show (a, b)

リストを扱う際には、map を使用して関数をリストに適用し、新しいリストを作成することがよくあります。デフォルトでは、一つずつ順番に関数が適用され、バッファに順次プッシュされます。しかし、parBuffer を使用すると、 n 個の要素を並列で評価し、それをバッファにプッシュすることができます。

parBuffer :: Int -> Strategy a -> Strategy [a]
 
doubleList :: Num a => [a] -> [a]
doubleList xs = map (\x -> 2*x) xs `using` parBuffer 100 rseq
-- 各要素をWHNFで評価するためにrseqを使用
-- 並列化は `using parBuffer 100 rseq` のみ!!
 
main :: IO ()
main = do
    let xs = doubleList [1..1000]
    let sum = foldl' (+) xs
    putStrLn $ "Sum: " ++ show sum

モジュール内には、戦略に関する他の多くの関数があるので、興味がある場合は公式ドキュメントをチェックすることをお勧めします。最初は直感的ではないかもしれませんが、実験を続けるうちに概念を理解し、戦略を使用した並列処理のシンプルさに気付くでしょう。

Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #33 - Parallelism. YouTube.

並列処理と決定性

戦略

例

スパークのライフサイクル

スパークのデメリット

クイズ

リソース