Grand Central Dispatch

June 11th, 2009  |  Published in Uncategorized

WWDC 2009 が始まり、 Mac OS X Snow Leopard の技術が少しずつ公開されてきています。 下位レイヤ屋にとって興味深いのは Grand Central Dispatch (GCD) と OpenCL ですが、ここでは Grand Central Dispatch Technology Brief (PDF) をもとに、 GCD について書いてみます。PDF を参照しながら読んでいただければ。突っ込み歓迎。

かんたんなまとめ: Block という構文をつかうことで、マルチコアの性能を引き出す並列プログラムをかんたんに書くことができるようになるよ (きっと)

おさらい

GCD の話の前に、背景をかんたんにおさらいします。

これまでムーアの法則にしたがって上がってきていたCPUのクロックは、発熱とか消費電力とかのために頭打ちになってきている。 そこで、クロックを上げずにプロセッサをパワーアップさせる方法として、1つのチップ内に複数のCPU (コア) をのせて並列処理をしましょう、というのがマルチコア化の流れ。

そうしたマルチコアを活かしてプログラムを速くするためには、プログラムを並列で書かないといけないわけです。 ところが、並列プログラミングというのはむずかしい。デッドロックとかレースコンディションとか非決定性のためにデバッグしづらいとか、泣けるポイントだらけなのです。

つまり、これまではプログラムの性能が足りなくても、お金を出すか待っていれば速いプロセッサがソフトウェアをそのまま速くしてくれたんだけれど、これからはそうはいかないよ、ということ。 そんな哀れなプログラマを救うべく、世界中の研究機関や企業がこぞって研究開発をしているのですが、そんな中 Apple が GCD をさらっと出してきたのでした。

Grand Central Dispatch とは何か

Mac OS X Snow Leopard で導入される、 マルチコア時代の並列実行基盤 です。 これまでの OS でいうところのプロセス/スレッドスケジューラのレイヤにありつつも、プログラマが直接たたける API を提供しているフレームワークでもある。

特徴は以下の3つ。

  • Block という単位で、かんたんに並列プログラムが書ける (らしい)
  • Mac OS X の洗練された開発ツールと統合されている
  • 軽い

Block

GCD の核となるのは、Block と Queue 、そしてそれらを動かすランタイムシステムです。

Block は並列実行の単位です。これまでのモデルだとスレッドに近い。Ruby だと Proc のイメージでしょうか。 Technology Brief の例によると、 Block は以下のようにして書きます。

x = ^{ printf("hello world\n"); }

ふつうの C/C++/Objective-C のブロック {} の先頭に ^ をつけたものですね。そうして定義した Block を変数に代入しています。 関数型っぽい。Block の中は、並列に実行する段になってはじめて評価される (遅延評価) のではないでしょうか。

Technology Brief によると、 Block には引数を渡すこともできるそうです。引数によって、処理の依存関係を表現するんでしょう。 Block の中で Block を呼び出すことで、 Nested Parallel のようなこともできそうです。

たとえば、依存関係のない配列の要素を並列で計算するのであれば、次のようなコードになるのかな ( [ ] で、ブロックに引数を渡すと勝手に仮定)。

   square = ^[int x]{ x * x; }


int results[1024];
   for (int i(0); i<1024; i++) {
      results[i] = square(i);
   }

いかにもなデータ並列ですね。

定義した Block は Queue にどんどん放り込まれます。あとは、システムの方で自動的に依存関係を解析して、動ける Block をかたっぱしから並列実行していく。 Queue はスレッドプールをもっていて、Block の実行にはスレッドプールから空きスレッドを割り当てるというしくみ。 スレッドプールを使うことにより、スレッド生成/後始末のコストを小さなものにしています。

run queueにタスクをつっこんでいく、というのは Linux のプロセススケジューリングなどを想起させられます。 異なるのは、 GCD のキューは並列で動く Block 間の依存関係を解きながら並列実行をすすめる、というところでしょう。 ここに GCD のキモがあるとおもいます。どうやってるんだろう… プロセススケジューラが、 I/O が発生した段階でタスクを run queue から外すように、別 Block と通信が必要になったときには Queue から別の Block を取り出す、とかやりそう。

開発環境

Instruments で、 Block の実行状態を把握することができるそうです。 あのインターフェイスで並列プログラムを解析することができるのは魅力的ですね。 Apple のすごいところは、こういう統合されたインターフェイスがあるところだなあと。

軽い

スレッドプールをつかってるから、というのもありますが、 Block を Queue につっこむのに 15 命令しかつかわないよ、と。 ふつうのスレッドプログラミングでのスレッドのセットアップをするのに比べて 50 倍は速いんだぜ、と。

謎: 共有データ

Technology Brief を読んだだけでは、共有データをどのようにして排他するかという、並列プログラミングで一番問題になるところをどのようにして解決しているのかが分かりません。 lock する必要がなくなるよ! とは書いてあるのですが…

GCD では、プログラマはプログラムを Block にわけ、データ/処理の依存関係を Block の引数にするか、 Block を Queue に入れる順番で表現することになります。 そうしたときに、たとえば Producer/Consumer 問題はどのようにして書けばいいのか。仮説として、次のものを思いつきました。

  1. 静的解析をやってしまう : Block 間の依存関係を、コンパイル時にすべてしらべあげてしまうとか
  2. 書けないようにする : 共有データを Block 内に書くことができないようにする。共有するデータは引数として受け渡しするのみ

1 かなー…

考察

  • 一読したときには、単にスレッドプールがあって、ちょっとヘンな構文でスレッドを記述するだけのもの、と見なしていました。でも、 Block の依存関係を自動的に解消して並列実行する Queue というものは、実はすごいものである可能性があります。
  • GCD はタスク並列と粒度の大きなデータ並列を扱い、 OpenCL が細粒度のデータ並列を受け持つという両輪を標準で備えたことにより、Mac OS X は並列処理において他のプラットフォームをだいぶ引き離しますね。
  • あと、C/C++/Objective-C の構文拡張をしているわけですが、そうなると GCC に手を入れているか、別の技術 (LLVM, clang) をつかっているのかなーとか。

懸念

  • まずデバッグをどうするんだろう、というのがあります。並列で動いている Block をどうつかまえて、トレースするのか。 Apple がどのように Xcode で見せてくるのかとても興味あります。
  • また、 GCD がいくらすごい技術だったとしても、 Mac OS X でしか使えないのだったら魅力が半減してしまいます。

まとめ

Technology Brief にある GCD の概念はわかりやすいものです。 しかし、ふつうのプログラマがばしばし使うようになるかどうかは、共有データを複数の Block からアクセスするときのモデルと考え方が、いかに分かりやすくカンタンであるかにかかっています。 続報に期待ですね。

GCD によって、スレッドに代わる新しい並列プログラミングモデルの世界が実現するかどうかワクワクしながら、9月の Snow Leopard リリースを待ちます。

参考


Tags: ,