前回は,GHCで並列プログラミングを行うための機能について説明しました。今回はそれらを使った並列プログラミングの具体的な方法について,もう少し詳しく説明していきたいと思います。

前回の補足

 GHCのサイトでは,GHC6.6.1のWindows用のバイナリ・パッケージがWindows Vistaに対応していると書かれています。しかし実際には,設定上の問題がまだ残っているようです。GHCをWindows Vistaで使用するには,あらかじめ環境変数PATHをghc\ghc-<version>\gcc-libディレクトリに対して設定する必要があります(参考リンク1参考リンク2)。

 また,GHC6.8に向けて,GHCの開発版ではbaseパッケージが大きく再編成されています。その結果,前回扱ったControl.Parallelモジュールや今回説明するControl.Parallel.Strategiesモジュールはparallelパッケージに,第5回で説明したSystem.Processモジュールはprocessパッケージに移されました。これらは,GHC6.8以降ではbaseパッケージから利用できなくなるので注意してください。

 なお,他にもいくつかのモジュールが独立したパッケージへと移されているようです(参考リンク1参考リンク2)。

コントロール並列とデータ並列

 前回,並列Haskellとデータ並列Haskellが,それぞれコントロール並列とデータ並列をサポートする機能であると説明しました。ですが,この説明は間違ってはいないものの,完全に正確なわけではありません。

 まずは,map関数の並列版を定義してみましょう。

parallelMap :: (a -> b) -> [a] -> [b]
parallelMap f [] = []
parallelMap f (x:xs) = fx `par` fxs `pseq` (fx:fxs)
                        where
                          fx = f x
                          fxs = parallelMap f xs

 並列化させやすいようにfxやfxsという名前を導入していますが,本質的な定義は第4回で示したものと何ら変わりありません。

 次に,parallelMapの並列性を示している部分について見てみましょう。par関数が,関数fの適用を他の式の評価と並列に行わせようとしているのはすぐにわかると思います。しかし,この式はfx `par` (fxs `pseq` (fx:fxs))と解釈するべきなのでしょうか? それとも(fx `par` fxs) `pseq` (fx:fxs)と解釈するべきなのでしょうか? それを理解するためには,関数の「結合性(fixity,またはassociativity)」について知る必要があります。

 GHCでは,関数を定義しているモジュールで:infoコマンドを使うことで,関数の型のほかに,中置演算子として使った場合の結合性や「優先順位(precedence)」を確かめることができます。優先順位の数字が高ければ高いほど,演算子が先に適用されることになります(プロンプトの出力では,関数を中置演算子として使うための` `が省略されている点に注意してください)。

Prelude GHC.Conc> :i par
par :: a -> b -> b      -- Defined in GHC.Conc
infixr 0 par
Prelude GHC.Conc> :i pseq
pseq :: a -> b -> b     -- Defined in GHC.Conc
infixr 0 pseq

 parとpseqの優先順位は同じなので,結合性だけがparallelMapの定義を解釈する手がかりであることがわかると思います。

 結合性には,非結合(non-associativity),左結合(left-associativity),右結合(right-associativity)の3種類があり,それぞれinfix,infixl,infixrと表されます(参考リンク)。非結合は,文字通り,結合しないことを示すものです。

 左結合や右結合はともかく,非結合は何のために存在するのでしょうか? <=演算子を例に考えてみましょう。例えば,4<=n<=12という式に対しては,数学の表記と同じようにnが4以上12以下であるという意味を持つことを期待すると思います。ところが,<=演算子の型は(Ord a) => a -> a -> Boolであるため,右側あるいは左側は<=演算子の返すBool型の値でなければなりません。この段階になって初めて型エラーを出すよりは,結合できないことをエラーとして示し,4<=n&&n<=12のように分けて書くようユーザーにうながしたほうがよいでしょう。

 なお,結合性宣言を持たない演算子は,infixl 9と宣言されているものとみなされます。また,関数適用は左結合性を持ちます(参考リンク)。これによりg :: a -> b -> cを使った関数適用を,(g x) yではなくg x yという2引数を取る関数の形で書くことが可能になっています。普段なにげなく使っていた式は,実は結合性を基盤に成り立っていたのです。

 さて,parallelMapの定義に戻りましょう。parとpseqはinfixrと宣言されているので右結合です。なので,parallelMapの本体の定義はfx `par` (fxs `pseq` (fx:fxs))と解釈されることになります。したがって,fxとfxsを同時に評価してからfx:fxsを評価するのではなく,fxsを正格評価してからfx:fxsを評価する再帰的な流れによって,fx' `par`という式に簡約された状態での式の評価をうながしている,と考えるとよいでしょう。その結果,リストのそれぞれの要素に対する関数fの適用がほぼ並列に行われることになります。

 この「リストのそれぞれに要素に対して関数fの適用を並列に行う」というparallelMapの定義は,データ並列Haskellを使った以下の式とほぼ同じものです。

parallelMap' = [:f x | x <- xs:]

 このことから,mapの並列版であるparallelMapを定義することは,「リストというデータ構造に対する演算を並列化させる」というデータ並列の実現であったことがわかるでしょう。

 逆に,コントロール並列的な意図を,データ並列Haskellを使って表現することもできます。

[:f a | f <- [:foo, bar, baz:] :]

 foo,bar,bazという三つの関数を並列的にaに適用し,その結果の並列配列を得るという式になっているのがわかりますね(ただし,コントロール並列化機能とは違い,これが即それぞれの関数を別々のスレッドで動作させるということを意味するわけではありません。どのように並列化されるかは,この式を含め全体を平坦化する,データ並列化機能に委ねられることになります。データ並列化機能によって表現したコントロール並列が,コントロール並列化機能によって作られたコントロール並列と1対1に対応する,と考えてしまうのは早計です)。

 このように,十分に抽象化された基盤の上でなら,コントロール並列化のために用意されている機能でデータ並列を実現したり,逆にデータ並列化の機能でコントロール並列を実現したりすることが可能です。コントロール並列とデータ並列の違いは,「並列化のための制御を中心とするか」「並列化されるデータを中心とするか」という考え方の違いでしかないからです。

 ただし,違う考え方によって成り立った機能である以上,細部にはそれぞれの性格の違いが現れます。例えば,コントロール並列化機能を使う場合には,どのように簡約・並列化していくかというプロセサごとの仕事の割り振りを手動で調整していくことができます。逆にデータ並列化機能を使う場合には,そうした部分はライブラリや処理系実装に委ねることになります。

 こう書くと,データ並列化機能は「並列化の粒度の調整能力」のない分,コントロール並列化機能に対して最適化の面で劣るように思えるかもしれません。しかし,実際にはそうではありません。確かに,手動による並列化の制御は,プログラムのあらゆる部分に行き届きます。しかし,それは処理系などによる自動的な並列化に比べて,より細かく並列化の戦略を制御できる能力がある,ということに過ぎません。

 並列化の粒度を調整できるということは,逆にいえば「並列化の粒度を意識してプログラムを書かなければならない」ということでもあります。例えば,上で示したparallelMapの定義は,値に適用する関数が大きな計算をするものであったり,対象となるデータが大きく大規模な処理が必要場合には,並列化の粒度が粗くなると期待できます。しかし,もしそうでないもの――適用する関数が小さかったり、対象のデータが小さいもの――に対して使うなら「リストの要素一つ一つに対して関数を並列に適用する」という処理は,プロセサ・レベルの並列化を行うには粒度が細かすぎるでしょう。手動で並列化を行う場合,こうした点に気をつけて並列化するのはすべてユーザー側の責任です。

 これに対し,同じことをデータ並列化機能を用いて行った場合には,機能の側でプロセサ・レベルでの並列化に適した単位でデータを分割して処理してくれると期待できます。また,命令レベルでの最適化を行うようデータ並列のベクトル化機能がきちんと実装されていれば,並列に行う処理をSIMD(Single Instruction Multiple Data)のようなベクトル演算にまで落とし込むこともできます(参考リンク1参考リンク2)。つまり,単なる複数プロセサ間での並列化にとどまらず,プロセサ内部での細粒度(fine graine)の並列化を行う能力をも持ち得るのです(前回説明したように,現在のデータ並列Haskellは,まだ複数プロセサ間での並列化機能を開発している段階に過ぎませんが,将来的にはSIMDやGPUなどを利用できるように拡張することが検討されているようです,参考リンク)。

 もちろん,現在ではGCCなどの一般的なコンパイラにも自動ベクトル化機能が備わっているきているように,コントロール並列化機能を使う場合でも自動ベクトル化の恩恵を受けられないわけではありません。例えば,前回触れた-fvia-Cオプションを使って一度Cコードに落とす場合には,Cコンパイラに渡すオプションを-optc-<option>オプションを使って指定することで,並列Haskellかデータ並列Haskellにかかわらず,gccの自動ベクトル化機能を利用できます(参考リンク)。ただし,そのような間接的な形でのベクトル化が,データ並列化機能でのベクトル化と同等の性能を発揮する保障はありません。

 データ並列化機能を使ってベクトル化する場合には,何を並列化すればよいのかという情報があらかじめわかっている分,賢いベクトル化と共存する形での最適化がやりやすいはずです。例えば,まずCPUのキャッシュに乗り切る単位にうまく分割したベクトル化を行い,それからベクトル化された処理を(負荷が大きくならないよう程々に)プロセサ・レベルで並列化して計算させる,といった手順で最適化を行わせることができるでしょう。

 一方,コントロール並列化機能を使って並列化した後にベクトル化する場合には,ベクトル化されるデータにムラが出るか,ムラを防ぐために出力されるコードを意識した不自然なプログラミングを強いられることになるでしょう。また,自動ベクトル化を生かせるプログラムは自然にデータ並列の形となっているものです。であれば,わざわざ苦労してデータ並列化機能と張り合うよりも,データ並列化機能に最適化を委ねたほうがよいのではないでしょうか?

 結局のところ,データ並列化するのに「『コントロール並列化機能による手動の並列化』と『データ並列化機能による自動的な並列化』のどちらが最適化能力の面で優れているか」という問いは,「処理系やライブラリによる最適化を信じるか否か」という問いと同じです。結論は「データ並列化機能による自動並列化のほうが優れている」ということになると思います。たいていは,コントロール並列化機能を使ってむやみに手動で行うデータ並列化より,データ並列化機能による自動並列化のほうが賢いからです。

 よって,コントロール並列化とデータ並列化の両方の機能が利用できる場合には,問題の性質に従って使い分けるのが望ましいでしょう。例えば,次に説明するControl.Parallel.Strategiesモジュールは,前回紹介したGPH(Glasgow Parallel Haskell)由来ということもあって,並列Haskellでデータ並列を表現したほうが他の並列化手法と組み合わせたプログラムを書きやすくなるような形で定義されています。

 また前回説明した通り,並列Haskell,データ並列Haskellともに,基本的に使うCPUの数を実行時システムの-N<x>オプションから取得するようになっています。そのため複数の手法を織り交ぜるような場合には,暗黙的に複数のCPUをすべて使用しようとするデータ並列化機能よりも,コントロール並列化機能を使ってデータ並列を行ったほうがいろいろと調整が効くので都合がよいかもしれません。逆に,データ全体に対してある処理を行うフィルタ(filter)のような計算であることがわかっている場合には,データ並列Haskellを使ってコントロール並列の意図を表したほうが細粒度での最適化が効く分,有利だと思われます。