Common Lispライブラリ紹介: lparallel(並列化コレクションほか)

巨大なベクタやリストのmapなどはシングルコアで動作させるにはもったいないが、手動で並列化を行うのは骨が折れる作業だ。速度面でのボトルネックになっている部分を高速化できれば，効率的に処理を行うことができる．

lparallelは並列・並行処理に関する関数やマクロを提供する。

この記事ではpmapとpreduceについて紹介する．

例: `pmap`: 並列な`map`

pmapは、コレクションをいくつかに分割し、各ワーカが並列にmapを行った後で、それらのコレクションが元の順序に結合される。

(ql:quickload :lparallel)
(setf lparallel:*kernel* (lparallel:make-kernel 2)) ; ワーカを2並列で初期化する
(map   'list #'(lambda (x) (* 2 x)) '(1 2 3 4 5 6 7 8 9)) ; 通常のmap
(pmap 'list #'(lambda (x) (* 2 x)) '(1 2 3 4 5 6 7 8 9)) ; 並列map

lparallelの使い方は、基本的に

kernelの初期化を行う
lparallelに含まれる関数を呼び出す

となる。kernelの初期化を行わずに並列操作関数を呼び出すと、デバッガに落ちてkernelを対話的に初期化できる。

他にもpreduceやdefpunなどの並列な関数が用意されている。

例: `preduce`: 並列な`reduce`

preduceは，reduceを並列化したものだ．これは2つの段階に分けて計算される．

コレクションを分割し，個々にreduce適用を並列して行う．コレクションはそれぞれ値に変換され，値のコレクションができる．
値のコレクションに対してreduce適用が行われ，最終的な値が定まる．

したがって，preduceは二項演算が適用される順序がreduceとは違うので，preduceには結合的(associative)な関数を渡す必要がある． #'+は結合的なのでpreduceでもreduceと同じように動くが，#'-は結合的ではないから同じように動作しない．

CL-USER> (reduce #'+ '(1 2 3 4 5 6 7 8 9 10))
55
CL-USER> (lparallel:preduce #'+ '(1 2 3 4 5 6 7 8 9 10))
55
CL-USER> (reduce #'- '(1 2 3 4 5 6 7 8 9 10))
-53
CL-USER> (lparallel:preduce #'- '(1 2 3 4 5 6 7 8 9 10))
11

+は結果が同じだが-は異なる結果を返す．

標準のreduceができるように，preduceもschemeにおけるfold相当の操作を:initial-valueで行うことができる．ただし，この値が使用されるのは最初のステップでコレクションを分割したときであり，部分ごとに使われるということに注意しなければならない．

CL-USER> (lparallel:preduce #'* '(1 2 3 4) :parts 1 :initial-value 10) ; '((10 1 2 3 4))
240
CL-USER> (lparallel:preduce #'* '(1 2 3 4) :parts 2 :initial-value 10) ; '((10 1 2) (10 3 4))
2400
CL-USER> (lparallel:preduce #'* '(1 2 3 4) :parts 3 :initial-value 10) ; '((10 1) (10 2) (10 3 4))
24000
CL-USER> (lparallel:preduce #'* '(1 2 3 4) :parts 4 :initial-value 10) ; '((10 1) (10 2) (10 3) (10 4))
240000