データ並列Haskell
GHCで並列プログラミングを行う最後の方法は，並列化されたデータ構造を使うことです。データ構造やそのデータ構造に対する演算が並列化されていれば，データ構造を利用するプログラムも自動的に並列化されるはずです。並列化されたデータ構造を使ったこのような暗黙的な並列化手法を「データ並列（data parallel）」と呼びます。そして，GHCで提供するデータ並列をサポートする拡張機能（およびその周辺ライブラリ）を「データ並列Haskell（Data Parallel Haskell）」と呼びます。
データ並列Haskellでは拡張機能として，[::]という形で表される「並列配列（parallel arrays）」を用意しています。この機能を使うことで，Fortranやその後継として米Sun Microsystemsが開発しているFortressと同様に，処理系が自動的に計算するデータを分割して並列化を行ってくれます（参考リンク）。
並列配列はほとんどリストと同じ感覚で使えますが，並列化を行うこと以外にも何点か違いがあります。
- 効率化のため，正格なものとして定義されている（非正格にした場合には，例えば今回説明したquicksortの例のように，WHNFまでにしか簡約されないといった問題がある）
- リストとは違い再帰的なデータ型として定義されていないため，x:xsのような型構成子に照合するパターンが使えない
- 名前の衝突を回避するため，（型クラスのメソッドを除き）関数名が異なっている
- 使用するには，-fparrオプションとGHC.PArrモジュールを使う必要がある
これらの違いに気をつければ，並列配列を使った並列プログラミングはそれほど難しいものではありません。以下にクイックソートの例を示します。
qsort :: (Ord a) => [:a:] -> [:a:]
qsort [::] = [::]
qsort xs =
let m = xs !: (lengthP xs `div ` 2)
ls = [:s| s <- xs, s < m:]
ms = [:s| s <- xs, s == m:]
hs = [:s| s <- xs, s > m:]
sorted = [:qsort xs' | xs' <- [:ls, hs:]:]
in (sorted !: 0) +:+ ms +:+ (sorted !: 1)qsort ls +:+ ms +:+ qsort hsではなく，途中でsortedという関数を定義してそれを使うようにしているのは，qsort lsと qsort hsに相当する評価を並列に行わせるためです。GHCのデータ並列化機能は，多次元配列などの入れ子になったデータ型を平坦（flat，フラット）な構造に変換する「ベクトル化（vectorisation）」または「平坦化（flattening，フラット化）」と呼ばれる機能を持つ「入れ子型データ並列（nested data parallelism）」なので，このように多重化した並列配列も問題なく扱えます。
では試してみましょう。ParallelTest.hsにqsortの定義を記述し，main関数の周辺を以下のように書き換えます。
import Parallel import GHC.PArr main = print $ qsort [:0..10000:]
結果は，以下のようになります。
$ ghc -threaded --make ParallelTest.hs -cpp -fparr -O
[2 of 2] Compiling Main ( ParallelTest.hs, ParallelTest.o )
Linking ParallelTest.exe ...
$ ParallelTest +RTS -N2 -sstderr
ParallelTest +RTS -N2 -sstderr
[:0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,2
～ 略 ～
7,9998,9999,10000:]
380,262,492 bytes allocated in the heap
161,567,028 bytes copied during GC (scavenged)
6,668,280 bytes copied during GC (not scavenged)
25,845,884 bytes maximum residency (13 sample(s))
712 collections in generation 0 ( 0.27s)
13 collections in generation 1 ( 0.17s)
53 Mb total memory in use
Task 0 (worker) : MUT time: 0.00s ( 0.00s elapsed)
GC time: 0.00s ( 0.00s elapsed)
Task 1 (worker) : MUT time: 0.00s ( 0.34s elapsed)
GC time: 0.00s ( 0.00s elapsed)
Task 2 (worker) : MUT time: 0.27s ( 0.34s elapsed)
GC time: 0.44s ( 0.45s elapsed)
Task 3 (worker) : MUT time: 0.00s ( 0.34s elapsed)
GC time: 0.00s ( 0.00s elapsed)
INIT time 0.02s ( 0.00s elapsed)
MUT time 0.27s ( 0.34s elapsed)
GC time 0.44s ( 0.45s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.72s ( 0.80s elapsed)
%GC time 60.9% (56.9% elapsed)
Alloc rate 1,352,044,416 bytes per MUT second
Productivity 37.0% of total user, 33.3% of total elapsedquicksort'関数に比べて大幅に処理速度が向上しているのは，定義が本質的に異なるからです。qsortではリストの中央の要素を比較に使っているのに対し，quicksort'ではリストの先頭の要素を比較に使用しているため，[0..10000]のような整列済みの要素を持つリストに対してはとても非効率になってしまいます。なので，ランダムな要素を持つものに対して使った場合には，逆にquicksort'関数のほうが速くなります。
ndpパッケージ
上の結果を見てもう一つ気になるのが，並列に動作しているように見えないことです。Task 2だけが動いていて，Task 0，Task 1，Task 3はほとんど動いていません。実はGHCのデータ並列の機能はまだ作りかけなのです。GHC 6.6.xでは並列化のためのバックエンド（back-end）やベクトル化をはじめとした多くの機能がまだ実装されていません（参考リンク1，参考リンク2）。
現段階で，並列配列による並列化とほぼ同等の処理を行うには，データ並列化機能のバックエンドとして開発されているndpパッケージをインストールし，並列配列の代わりに使用する必要があります。ただし，ndpパッケージは，並列配列のバックエンドを直接使用するものなので，並列配列のように「並列に評価される多次元配列や木，グラフなどのデータ構造をリストと全く同じ形で表現」したり，内包表記を使用するといった，糖衣構文の恩恵を受けることはできません。
ndpはCabalでパッケージ化されているので，第2回のコラムで説明したData.ByteStringのインストール方法を参考にインストールしてください。ただし，ndp.cabalには-haddockというGHC 6.6.xでは使用できないオプションが記述されているので，この部分を削除する必要があります。パッケージはHaskell.orgのndpの使い方を開設しているページからndp-0.1 tarをダウンロードするか，またはバージョン管理システムのdarcsを使ってhttp://darcs.haskell.org/packages/ndp/から取得します。
ndpを利用するには，ParallelTest.hsを以下のように書き換えます。qsort関数の定義を削除して，代わりにqsort'関数を定義します。
import Data.Array.Parallel.Unlifted
import Data.Array.Parallel.Unlifted.Parallel
import Data.Array.Parallel.Unlifted.Distributed
main = do
setGang 2
print $ qsort' $ enumFromToUP 0 (10000::Int) -- toU ([0..10000]::[Int])
qsort' :: (Ord a, UA a) => UArr a -> UArr a
qsort' xs
| nullU xs = xs
| otherwise =
let m = xs !: (lengthU xs `div ` 2)
ls = filterUP (< m) xs
ms = filterUP (== m) xs
hs = filterUP (> m) xs
in qsort' ls +:+ ms +:+ qsort' hsqsort'関数の型宣言のUAクラスとUArr型は，「Unlifted Array」を表しています。並列配列に持ち上げられていない（liftされていない）内部表現であるため，こうした名前が付けられたのでしょう。UAとUArrが同じ名前の略称であることから，UArr型の操作関数の一部はUAクラスのメソッドとして定義されているのがわかると思います。したがって，qsort'の文脈からUAクラスを消すと，以下のようなエラーが出ます。
$ ghc -threaded --make ParallelTest.hs -cpp
[2 of 2] Compiling Main ( ParallelTest.hs, ParallelTest.o )
ParallelTest.hs:45:7:
Could not deduce (UA a) from the context (Ord a)
arising from use of `+:+' at ParallelTest.hs:45:7-36
Possible fix: add (UA a) to the type signature(s) for `qsort''
In the expression:
let
m = xs !: ((lengthU xs) `div` 2)
ls = filterUP ((< m)) xs
ms = filterUP ((== m)) xs
hs = filterUP ((> m)) xs
in (qsort' ls) +:+ (ms +:+ (qsort' hs))
In the definition of `qsort'':
qsort' xs
| nullU xs = xs
| otherwise
= let
m = xs !: ((lengthU xs) `div` 2)
ls = filterUP ((< m)) xs
ms = filterUP ((== m)) xs
hs = filterUP ((> m)) xs
in (qsort' ls) +:+ (ms +:+ (qsort' hs))qsort'の定義はqsortとほぼ等価なので，両者を見比べれば定義やそこで使われている関数などの意味を理解するのは難しくないでしょう。先に説明したように，UArr型は処理系によって平坦化されるのが前提の型であるため，平坦な配列しか扱えません。そこでqsort'本体の定義はqsort' ls +:+ ms +:+ qsort' hsという少し効率の悪いものに書き換えてあります。なお，ほとんどの関数はData.Array.Parallel.Unliftedモジュールからインポートしていますが，enumFromUの並列版であるenumFromUPとfilterUの並列版であるfilterUPは，Data.Array.Parallel.Unlifted.Parallelモジュールからインポートしています。
qsortに対する変化以外で目につくのは，まず，Data.Array.Parallel.Unlifted.DistributedモジュールのsetGang関数で同時に動かすスレッドの数を指定しているところでしょう。-N<x>オプションで指定したプロセサの数を取得できないためです。次に，[:0..10000:]という構文で直接配列を作ることができないため，enumFromToUP e1 e2と書き下しています。
数字リテラルにIntなどの型注釈を付けているのは，それぞれの関数で要求する文脈に従う型aが複数存在し，処理系の側からはそのようなあいまいな制約に従う型aを一意に決定できないためです。型注釈を付けなければ，以下のエラーが表示されることになります。
$ ghc -threaded --make ParallelTest.hs -cpp
[2 of 2] Compiling Main ( ParallelTest.hs, ParallelTest.o )
ParallelTest.hs:11:20:
Ambiguous type variable `a' in the constraints:
`Enum a'
arising from use of `enumFromToUP' at ParallelTest.hs:11:20-41
`Ord a' arising from use of `qsort'' at ParallelTest.hs:11:12-16
`UA a' arising from use of `print' at ParallelTest.hs:11:4-8
`Num a'
arising from the literal `10000' at ParallelTest.hs:11:36-40
Probable fix: add a type signature that fixes these type variable(s)標準Haskellや処理系で用意されている型クラスでは，このようなあいまい性を回避するために，default宣言によって型の優先順位を定義できます。しかし，UAクラスではdefault宣言を利用できません（参考リンク）。
したがって，Intのようにそれぞれの制約に従う型を直接記述するか，あるいは何らかの方法でaの型を推論させる必要があります。こうしたときに便利なのが，PreludeのasTypeOf関数です。asTypeOfは第1引数の型を第2引数と同じものに決定し，そのまま第1引数を返します。さいわい，setGang関数で使用する型はIntに決まっているので，型注釈を置かずにasTypeOf関数を使って数字リテラルの型を決定できます（参考リンク）。
Prelude Data.Array.Parallel.Unlifted.Distributed> :t asTypeOf asTypeOf :: a -> a -> a Prelude Data.Array.Parallel.Unlifted.Distributed> :t setGang setGang :: Int -> IO ()
main = do
let a = 2
setGang a
print $ qsort $ enumFromToUP 0 $ 10000 `asTypeOf` a それでは実行してみましょう。
$ ghc -threaded --make ParallelTest.hs -cpp -fparr -O
[2 of 2] Compiling Main ( ParallelTest.hs, ParallelTest.o )
Linking ParallelTest.exe ...
$ ParallelTest +RTS -N2 -sstderr
ParallelTest +RTS -N2 -sstderr
toU [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,2
～ 略 ～
9997,9998,9999,10000]
82,457,116 bytes allocated in the heap
626,484 bytes copied during GC (scavenged)
473,720 bytes copied during GC (not scavenged)
97,956 bytes maximum residency (1 sample(s))
112 collections in generation 0 ( 0.00s)
1 collections in generation 1 ( 0.00s)
3 Mb total memory in use
Task 0 (worker) : MUT time: 0.06s ( 0.72s elapsed)
GC time: 0.00s ( 0.00s elapsed)
Task 1 (worker) : MUT time: 0.13s ( 0.72s elapsed)
GC time: 0.00s ( 0.00s elapsed)
Task 2 (worker) : MUT time: 0.23s ( 0.72s elapsed)
GC time: 0.00s ( 0.00s elapsed)
Task 3 (worker) : MUT time: 0.00s ( 0.72s elapsed)
GC time: 0.00s ( 0.00s elapsed)
INIT time 0.03s ( 0.00s elapsed)
MUT time 0.45s ( 0.72s elapsed)
GC time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 0.48s ( 0.72s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 170,234,045 bytes per MUT second
Productivity 93.5% of total user, 63.0% of total elapsed今度はプログラムが並列に動作しているのがわかりますね。ただ，並列化しても，それほど性能が劇的に向上しているわけではありません。並列化されていないqsortは，演算のトータル時間が0.72秒，すべての処理にかかった実時間が0.80秒でした。これに対し，並列化したqsort'は，演算のトータル時間が0.48秒とそれなりに高速化していますが，実時間は0.72秒でそれほど速くなっているわけではありません。
実時間にそれほど差が出ない理由は，数字を整列させるという問題自体，粒度（grain，granularity）が細かすぎて，スレッドの起動などの負荷がそのまま反映されるからではないかと考えられます。実は，このプログラムの場合，-threadedオプションなしでコンパイルしたほうが速く動作します。このように，ある計算を並列化させる場合には，問題の粒度について気を配る必要があります。
とはいえ，Haskellは遅延評価を採用しているため，プログラムを見ただけでは処理の粒度を判断できないこともよくあります。並列プログラミングを行う場合も，他の最適化手法と同じく，実際に実行してみて性能を測定（profile，プロファイル）することが重要であるのはいうまでもありません。
|
--makeオプション 今回の記事では--makeオプションを付けてコンパイルするよう指示しています。--makeオプションは，ソースコードの構造が単純な場合にいちいちMakefileを書かなくて済むように用意されたものです。このオプションを使えば，GHCiを使った場合と同様に，ghcがある程度の依存性を自動的に解析してくれます（参考リンク）。逆にいえば，--makeオプションを付けないと「ParallelTest.hsをコンパイルするにはParallel.hsのコンパイルが必要である」といった依存性を解析してくれません。ghcが以下のようなエラー・メッセージを出します。 $ ghc -threaded ParallelTest.hs -cpp
ParallelTest.hs:1:0:
Failed to load interface for `Parallel':
Use -v to see a list of the files searched for.出力にあるinterafaceは，Haskellのソース・ファイルをコンパイルしたときにオブジェクト・ファイルと一緒に生成される拡張子hiのファイルのことです。 したがって，--makeオプションを付けない場合には，まずParallel.hsをコンパイルして，次にParallelTest.hsをコンパイルする必要があります。 $ ghc -threaded Parallel.hs -cpp C:/home/ghc-6.6.20070415/ghc-6.6.20070415/libHSrts_thr.a(Main.thr_o)(.text+0x1b) :Main.c: undefined reference to `__stginit_ZCMain' C:/home/ghc-6.6.20070415/ghc-6.6.20070415/libHSrts_thr.a(Main.thr_o)(.text+0x3f) :Main.c: undefined reference to `ZCMain_main_closure' collect2: ld returned 1 exit status $ ghc -threaded ParallelTest.hs -cpp Parallel.hsをコンパイルしたときに参照エラーを示すメッセージがいくつか出ています。これはghcコマンドが，デフォルトでは与えられたソース・ファイルをもとに実行ファイルを生成しようとした結果，生じたものです。Parallel.hsで定義しているのはParallelモジュールでありMainモジュールではないので，当然ながらMainモジュールのmain関数を探し出すことはできません。というわけで，このエラー・メッセージは特に気にする必要はありません。 ここでは依存するソース・ファイルを探し出すために--makeオプションを使いましたが，依存するファイルを探すといっても，無制限にディスク上のすべてのファイルを調べるわけではありません。インポートするファイルと同じ名前が付いたソース・ファイルから検索されます。ただし，Control.Parallel.Strategiesのようにモジュール名が階層化されている場合には，最後の(.)より前をディレクトリとみなし，Control/Parallelディレクトリ配下のStrategies.hs(またはlhs)ファイルを探します。 また，--makeオプションがファイルを探すのは，現在のディレクトリか-iオプションで指定したディレクトリに限られます（参考リンク）。本文中でParallel.hsやParallelTest.hsを同じディレクトリに置き，そのディレクトリに移動するよう指示したのはこのためです。 ところで，ndpパッケージを使用したqsort'をコンパイルしようとした場合，上で説明した「Parallel.hsをコンパイルして，次にParallelTest.hsをコンパイルする」という方法では，実行可能ファイルを生成することはできません。 以下のような参照エラーを示すメッセージが出てくるだけです。 $ ghc -threaded Parallel.hs -cpp $ ghc -threaded ParallelTest.hs -cpp ParallelTest.o(.text+0xde):fake: undefined reference to `ndpzm0zi1_DataziArrayzi ParallelziUnliftedziFlatziText_zdf2_closure' ～ 略 ～ ParallelTest.o(.rodata+0x48):fake: undefined reference to `ndpzm0zi1_DataziArray ziParallelziUnliftedziDistributedziTheGang_setGang_closure' collect2: ld returned 1 exit status どうして，上の場合には--makeオプションを使わなくてもよいのに，この場合にはダメなのでしょうか？ これにはパッケージという概念がかかわっています。これまで何度か見てきたように，Haskellのライブラリは複数のモジュールを一まとまりにしたパッケージという概念を使って管理されています。パッケージには，オブジェクトファイルから作ったライブラリ・ファイルが存在する場所など，実行ファイルを生成するうえで必要不可欠な依存情報が書かれています。 GHCは，基本的なモジュールが用意されているbaseパッケージを除き，デフォルトではパッケージの定義を参照しません。この結果，base以外のパッケージを使用した場合には実行ファイルを生成できなくなってしまうのです。 この問題を解決するには，-packageオプションを使って明示的に使用するパッケージを指定するか，--makeオプションを使って暗黙的にパッケージの依存関係を調べるようghcの挙動を変更する必要があります（参考リンク）。 $ ghc -threaded Parallel.hs -cpp -package ndp なお，GHCiでも暗黙的にパッケージの依存関係を調べて，依存するライブラリ・ファイルをロードしてくれます。第6回でmtlパッケージを使ったときに，エラーが生じることなく普通に使用できたのはこのためです。 |
|
著者紹介 shelarcy 並列プログラミングにあまりなじみのない読者にとって，今回紹介した機能は新機軸のように見えるかもしれません。ですが，1990年代にはすでに現在の形に近い高レベルの並列化機能が登場していました（参考リンク）。Haskellでも，本文中で述べたデータ並列Haskellの原型やGPHなどの「並列プログラミングのための拡張機能」が登場したのは，ちょうどその頃でした（参考リンク1，参考リンク2）。 過去から離れて現在に目を投じると，米Intelや米MicrosoftがC/C++の拡張機能や .NETの将来の機能としてデータ並列をサポートすることを考えています（参考リンク）。 もしからしたら私たちが思っている以上に，並列プログラミングを直接サポートする言語の時代は，すぐそこまで迫って来ているのかもしれません。 |
