並列パターン (Parallel Patterns)

このページでは並列パターン(別名algorithmic skeletons)の研究について紹介する.

並列パターン自体の説明は,良く書かれているWikipediaの記事に譲りたいところだが,日本語版が無い上に,survey論文よろしく大量のライブラリが紹介・比較されているため,大半の読者は思わずページを閉じてしまうことだろう.なのでまずは筆者の視点で,単純だが重要な並列パターンを,簡単な例を通して紹介する.

尚,このページでは,Pythonの構文と組み込み関数について,読者に多少の知識があることを仮定する.

自乗和を例に

数値のリストxsの自乗和sqsumを計算することを考える.素直にPythonで書くなら,次のようになるだろう.

   1 sqsum = 0
   2 for x in xs:
   3    sqsum += x*x

もしくは,Pythonに慣れた人なら,次のように1行で書くだろう.

   1 sqsum = sum(x*x for x in xs)

実はこの記述は,並列パターンを既に利用した例だと解釈できる. 何故なら,この内包表現とsum関数は,それぞれ,高階関数mapとreduceを次のように利用することと等価だからである.

   1 add = lambda x,y: x + y
   2 sqr = lambda x: x*x
   3 sqsum = reduce(add, map(sqr, xs))

このmapとreduceが,並列パターンの代表例である.

Pythonに詳しい人なら,上記のプログラムが逐次的に実行されることを知っているだろう. 何が並列なんだと思うことだろう.

ここで重要なのは,mapやreduceが,引数として与えらるsqrとaddが純粋な関数であるとき1,並列に計算できることを保証2する計算パターンだということである. 純粋な関数というのは,引数のみを使って計算する関数である. したがって,異なる値に対してsqrとaddを適用することは独立に並列に実行できる. その意味で,このmapとreduceは,並列に計算できる性質(並列性と呼ぶ)を表現している計算パターンなのである.

しかし,この例だけではmapとreduceのご利益はあまり感じられないだろう. mapとreduceがその真価を発揮するのは,入力リストxsが,複数の計算機に分散している,分散リストである場合である.

ここでP個のプロセッサがあるとして,i番目のプロセッサが保持するxsの部分リストをxsiと書くことにする. mapとreduceの並列性から,xsiについてmapとreduceを独立に適用し,通信や同期無しでsqsumの部分和sqsumiを計算できる. 後は,sqsumiをP個プロセッサで協調して和を取れば,sqsumが求まる. これはO(log P)並列ステップで実装可能である.

このような,複数の計算機の上で分散したデータに対する並列計算を,mapとreduceの内部実装として隠蔽できることが,重要な点である. 隠蔽されたことで,mapとreduceの利用者は,分散データに対する並列計算を行っていると気にすることなく,あたかも逐次計算と同じような気持ちで計算を記述できる.これがmapとreduceの具体的なご利益である.

専門的な言い方では,このことを,mapとreduceが分散データに対する効率的な並列計算の高水準抽象化となっている,と表現する. ここでの「抽象化」は,実装を隠蔽していることに対応し,「高水準」というのは,並列計算を気にしなくてすむ程度に,ということに対応する用語である.

Googleが2004年に発表し,後にApache Hadoopとしてオープンソース実装が公開されたMapReduceも,mapとreduceと同様に並列パータンである. MapReduceは,クラスタ上に分散した大規模ファイルデータを,暗黙的に並列分散処理できる高水準抽象化であったために,ビッグデータ処理の基盤として重宝され普及した.

じゃあ他の例は?

リストの自乗和だけではつまらないので,もう少し別の例も考えてみることにする. 例えば,次のループを考える.

   1 for i in range(len(a) - 1):
   2   b[i] = (a[i-1] + a[i] + a[i+1])/3 

ここで,aとbは,同じ長さの数値のリストだとする.このループは単純だが,科学技術計算に頻出し,一般にステンシルコードと呼ばれる応用上重要な計算である.

さてここで問題,この計算をmapとreduceで表現できるだろうか.

...

出来ると思った人.おそらくそれは間違っていない. 表現することだけなら,何らかの意味で出来るであろう. 問題は,そのコードが妥当かどうかである. 具体的に言えば,効率的で分かりやすいかどうか.

...

残念ながら,筆者の知る限り,単なるmapとreduceの組合せでは,元のループと同程度に効率的な実装を与えられる高水準抽象化は実現できない.

こんな単純なループ1つとっても,基本となるmapとreduceだけで,まともに記述できない. そんなんで実用的な価値があると言えるだろうか.大変怪しい.

ステンシルコードは重要だから,mapとreduceに拘らず,専用の並列パターンを設計すればよいのではないか.

これは,筋としては正しい.例えば,前述のループ本体を引数関数で抽象化することで,次のように抽象化できる.

   1 def stencil(f, a):
   2   b = [None] * len(a)
   3   for i in range(len(a) - 1):
   4     b[i] = f(a[i-1],a[i],a[i+1]) 
   5   return b

さて,このパターンの一般性がどれだけあるだろうか. このstencilパターンは,aへの添字アクセスがi-1,i,i+1の3つであるときにしか使えないが,実際のステンシルコードは,もっとバリエーションがある. ステンシルコードの高水準抽象化を名乗るなら,様々なステンシルのバリエーションを簡潔に効率的に統一的に表現できるべきだが,これはなかなか難しい.

どれくらい難しいかというと,実は2018年現在においても未だに研究されている程度にはresearch issueである.

筆者の知る最新の研究成果は,Hagedorn et al.によるLIFTという言語処理系(コンパイラ)である. LIFTは,多次元配列に対するmapとreduceに,多次元配列をスライドさせる並列パターンを加える. これによって,多次元配列上の添字による近傍アクセスを高水準に抽象化する. しかし,単に並列パターンを組み合わて記述したものを直接実行すると,全く効率的ではない. そこで,LIFTは,コンパイラという形をを取って,並列パターンの組み合わせて記述されたプログラムに対して,特別な最適化を適用してコード生成する.結果として,並列パターンによる高水準抽象化と,手動チューニングしたものより高い実行時性能を両立する.

特定領域の計算(例えばステンシルコード)の記述に特化した言語のことを,ドメイン特化言語(Domain-specific language, DSL)と呼ぶ.並列パターン1つ1つは,単なる高階関数だが,上手く構成された並列パターンのセットは,DSLの一種と解釈することができる. そして,DSLを―そのDSLに特化した最適化と共に―コンパイルするものをドメイン特化コンパイラと呼ぶ.LIFTはまさにこの例である.

これが最近の研究のトレンドである.

このように,有用な並列パータン・ドメイン特化言語・ドメイン特化コンパイラを設計して初めて,特定領域の計算に対して,妥当な高水準抽象化が与えられるようになる.mapとreduceは依然として重要だが,それだけでは全く足りない.

だから難しく,大変で,未だに研究されてる.


  1. 実は,addが結合的な2項演算,つまり add(x,add(y,z)) == add(add(x,y),z) を満たすことも求める. (1)

  2. Python言語としては保証されていない.しかし,sqrとaddが純粋でないようなコードは,一般にお行儀が悪い. (2)

Taura Laboratory: Research/ParallelPattern (last edited 2018-12-30 20:52:08 by sato)