Tag Archive for 'grand_central_dispatch'

Grand Central Dispatch をためす (2)

Published on September 2, 2009 in default. Comments Tags: , .

その1では、man ページしかドキュメントのない状態で手探りで GCD をさわってみる、ということをしていました。

で、その1を書いた数時間後に全世界で Snow Leopard の発売開始が完了したためか、 ADC で Snow Leopard の開発資料すべてに、ヒラ会員でもアクセスできるようになっていました。すばらしい。

でもそのあたりはロクに読まないまま、今回も man ページを頼りに遊んでみます。

dispatch_apply

man ページによれば、データ並列を実現するもののようですね。与えられた Block を、指定された回数だけ並列実行して回す、という並列プログラミングパターン。

たとえばこんな感じになる。

実行結果:

% ./apply_dispatch
1
0
3
4
5
6
2
8
9
7

ちゃんと非決定的に、突っ込まれた順序でなく Block が実行されている様子が見てとれます。

とはいえ、 dispatch_apply はそのままだと、ループが終わるまで処理をブロックしてしまうので、それがイヤなら dispatch_apply そのものを dispatch_async でくるむといいよ、とか書いてます。

(さいしょ、iteration の各 Block が並列に実行されないのかと勘違いしていて、なんだよそれじゃ意味ないじゃんと思って実験してみたら、ちゃんと個々の Block が並列に実行されてるのを見て感心してました)

こんな感じになる。

実行結果は前のと同じ傾向になります。 違いは、 dispatch_apply の終了を待たずに main が終わりそうになるというところ。 (なので sleep で適当に待っている)

ローカル変数はどうなるの

Block の中から、外のスコープにある変数を参照するとどうなるでしょうか。

タイミング的には、

  • x=3 in 外のスコープ
  • Block を評価
  • x=7 in 外のスコープ
  • Block が実行される

となるように仕組んでいるわけです。

実行してみましょう。

% ./dispatch_local_var
x in outside block : 7
x in async block : 3

おおっと、 Block から参照する、外のスコープにある変数は、 Block が評価された時点の値になるようですね。

クロージャ

それってなんてクロージャ、という。

Apple が GC と Block をC1X に提案している中で (APPLE’S EXTENSIONS TO C March 10, 2009)、Block はクロージャを C に導入する、といった文脈で提案されています。コールバック関数を実装する際に、いちいち関数にコンテキストを引数で渡すのはめんどうだし、コンテキストはレキシカルスコープにある情報そのものでしょうよ、という。

並列プログラミングするときに問題になるのがレースコンディションといった共有変数への競合アクセスですが、クロージャを使うことで評価時に値を束縛してしまうので、 Block が実行されるときの変数の値が決定的になる、ということでしょうか。

並列プログラミングとクロージャの関係についてはもうちょっと考えてみないと。

まとめ

dispatch_apply は、parallel_for のようなデータ並列モデルを提供するものです。また、 Block は C でクロージャを記述できるようにする構文拡張でした。

次は、上でさらっと流した変数を Block 間で共有するあたりの話を掘り下げてみたいと思います。あとイベントとかもセマフォとかも。 Queue でタスク間の依存関係の制御をするあたりも。おわらない…

参考

いま MacBook Pro を買うと Snow Leopard が入ってて Grand Central Dispatch で遊べるし NVIDIA GPU が載ってるので OpenCL でバリバリと次世代並列プログラミングができてよいんじゃないでしょうか。

Grand Central Dispatch をためす (1)

Published on August 29, 2009 in default. Comments Tags: , , , .

Snow Leopard がでましたね!

OpenCL と Grand Central Dispatch がおもしろそうなので、そのへんのことを書いていくシリーズです。まずは Grand Central Dispatch について、手がかりのない状態からかるく使ってみるまで。

0. Grand Central Dispatch について

前に少し書いたように、Snow Leopard から入る並列実行基盤ですね。

1. Xcode でドキュメント探し

Xcode のドキュメントビューア (えらくインターフェイスがかわった) から、 Grand Central とか Dispatch とかをキーワードにして検索すると、それらしいタイトルがひっかかります。しかし、内容をみることはまだできないみたい。 ADC の上級メンバーならよいのでしょうが、ヒラ会員の我々は無理なの?

2. カンをつかう

mdfind dispatch とかしてみるわけです。すると

/usr/share/man/man3/dispatch.3

とかひっかかる。これはあやしい。 というわけで man 3 dispatch → man 3 dispatch_async としていくと、概念を紹介するためのサンプルコードが書かれている man ページにあたります。ビンゴですね。

3. 書いてみる

6-9 行がミソですね。 global queue に、ブロックないの処理を非同期で実行するようつっこんでるわけです。

4. 実行してみる

% ./a.out
hoge
... (寝てる)
%

ちゃんと非同期で実行されてます。

5. 確かめてみる

gdb であそんでみましょう。

% gdb a.out
(gdb) b 7           # ブロック内で break
(gdb run
Starting program: /Users/mootoh/gcd_sandbox
[Switching to process 10433]

Breakpoint 1, __main_block_invoke_1 (.block_descriptor=0x100001080) at gcd_sandbox.c:7
7               printf("hoge\n");

とまりました。　switching to process とかでてますね。スレッド切り替えがおこったのでしょう。

(gdb) bt
#0  __main_block_invoke_1 (.block_descriptor=0x100001080) at gcd_sandbox.c:7
#1  0x00007fff85bc2dc7 in _dispatch_call_block_and_release ()
#2  0x00007fff85ba1341 in _dispatch_worker_thread2 ()
#3  0x00007fff85ba0c80 in _pthread_wqthread ()
#4  0x00007fff85ba0b1d in start_wqthread ()

wqthread とな。 Worker Queue thread とかかな? スレッド全体をみてみましょう。

(gdb) info threads
* 2 port# 0x417 __main_block_invoke_1 (.block_descriptor=0x100001080) at gcd_sandbox.c:7
  1 port# 0x903 0x00007fff85bc1ace in __semwait_signal ()
(gdb) thread 1
(gdb) bt
#0  0x00007fff85bc1ace in __semwait_signal ()
#1  0x00007fff85bc195d in nanosleep ()
#2  0x00007fff85c0f320 in sleep ()
#3  0x0000000100000e94 in main (argc=1, argv=0x7fff5fbfe9b0) at gcd_sandbox.c:10

ちゃんと元スレッドがいますね。

6. その他

そういえば、 gcc に何のオプションも指定することなく、ふつうに Grand Central Dispatch のブロック構文が使えていました。また、特になにかライブラリをリンクすることもなく、ただ gcc -g gcd_sandbox.c これだけでビルドできて並列実行できるバイナリが生成されますね。うむむ。

7. まとめ

ADC ヒラ会員なので、まとまったドキュメントとして man 3 dispatch 周りだけをたよりに Grand Central Dispatch を覗いてみました。ブロック構文がちゃんと使えることをまず確認し、 gdb からもちゃんとマルチスレッドの動作が見える、というところまでを追いました。

あと気になるのは、ハイレベル API がどういうものなのか、というところです。 Cocoa 的なのがあるとすれば、 .framework にまとまってるだろうと思うのですけれど、それらしきものはまだ見つけられていません。

次回はもう少し掘り下げてみたいとおもいます。それまでにドキュメント手に入るようにならないかなぁ…

20009-09-02 21:13 JST 追記

その2 を書きました。

Grand Central Dispatch

Published on June 11, 2009 in default. Comments Tags: , .

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 リリースを待ちます。

参考