Lambdaカクテル

Common Lispと自宅サーバにWebエンジニアリングの香りを載せて

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

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

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

lparallel.org

この記事ではpmappreduceについて紹介する.

例: 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の使い方は、基本的に

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

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

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

例: preduce: 並列なreduce

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

  1. コレクションを分割し,個々にreduce適用を並列して行う.コレクションはそれぞれ値に変換され,値のコレクションができる.
  2. 値のコレクションに対して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ができるように,preduceschemeにおける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

ちなみに:recurseオプションをtにすると,第2ステップのreduce適用がpreduceに変わり,一貫してpreduceを使うようになる.

まとめ

今回はpmap/preduceを紹介した.lparallelにはこれらに限らずpromiseやptreeなどの便利な機能が用意されているので,また利用機会があればメモを残そうと思う.