concurrency :: 0xDEADBEAF

HotPar ’10

September 7th, 2010 | Published in CS

6月のことですが、 HotPar ’10 というワークショップに参加していました。

ポイント:

逃げ場がないことのは大事
ライブ感

HotPar とは

HotPar そのものについて。 Hot topics in Parallelism というテーマで、 2009 年からはじまった国際ワークショップです。いまのところ、2年連続でバークレーにて開催されています。で有名なパターソンさんが取りまとめてる。

面白いのは、 参加するなら論文書いてこい というところでしょうか。手ぶらの参加はなしです。これは、コミュニケーションの始めやすさにつながっていてナイスだと思いました。採択率は、論文で 16/68、ポスターで 20/52。1st author 以外も来ていたので、けっきょく50-60人くらいが参加していた。

企業からと学生とが半々くらいで、学生の人たちはたいていどこかの会社 (Intel, Microsoft, EA, …) にインターンに行っていた。日本からはぼくだけ。

やるしかない

自分は、2009年の初回にふつうの聴講者として参加していて、今回はポスター発表するという位置づけ。2009年のときは聴くだけの立場でしかなくて、透明人間になったような辛さがあった。自分がどんなものを持っているのか、誰にでも分かるかたちで見せることができないとダメだと思ったものです。今年はそのリベンジ。世界で動けるように。

そういうわけで、論文を出し、けっきょくポスターとして通った。初日の最後に LT みたいにしてポスター発表者全員が30秒でポスター紹介をプレゼンする、という時間があり、短いながらも初めての英語スピーチをした。すごくあたふたする… いろいろ準備を考えるんだけど、けっきょくしゃべりだしたら思ってたことの3割くらいしか言えないものです。

そんな中で思ったのは、 逃げ場がない ということが大事なんだということ。ネットがつながらないから、心地良い外の世界に逃避できないし、自分しか日本語話者がいないから英語でしゃべらざるを得ないし、他にごはんの手段がないのでテーブルにつかざるを得ない。テーブルについたら、こちらから何もしゃべらないと1,2時間そのまま、というとてもしんどい状態になるので、なんとかして絡んでいくようになる。まぁそうはいっても雑談はむずいわ…

最初に話さないと、ずっと話さない。まず当たっていくことを心がけようとか。軽い話題 (いつから来た、どこから来た) から入って、専門分野の話 (何やってるの、何がいちばん難しい問題なの?) にもって行く、というパターンを覚えたりとか。

そもそも、自分はカンファレンスや勉強会に参加してもロクにしゃべることがなかったんだけど、ここ 2,3年の積み重ねでだいぶコミュ力が培われてきたんだなーという実感。

とはいえ、英語圏のパーティはやはりノリが違うし、まだまだむずいですね… 雑談力を身につけたい。と同時に、自分の中に、じっくりと考えぬいたものがないと、けっきょくただのおしゃべりにしかならない。深みが魅力になる。やるべきことはまだまだ、まだまだある。

よかったこと

ポスターセッションは、一杯ひっかけながらポスターについてああだこうだと議論する、というスタイルだったこともあり、よく話せた。あまり考えずにしゃべるようになるというか、勢いづくというか。コミュニケーションツールとしてのワインとポスターというのがある。

あと、わりとアジア圏の研究者とはよく話したな。似たもの同士感があるんだろうか? 英語ラクじゃないよね、とか学校でたあとは国に帰るの? (No) とか、そういう話を夜遅くまでしていた。

チャレンジすること

話したものの、その場で終わりになってしまいがちなので、ネットワークを広げたい。たとえば、これに参加したあと、続けて ISCA ’10 というカンファレンスにも出席したんだけど、そこで「ああ、 HotPar でもいたよね、ひさしぶり」といった風に会話が始まることが2,3度あった。コミュニティによく出入りして、アウトプットを出し続けることだな。

あとは考える深さとスピード、雑談力, …

おもしろかったところ

その場でのコミュニケーション、によく気が配られていた。

ランチのときに、各テーブルにトピックがあって (並列デバッグどうやる? アプリはどんなのがある? どう教育する? などなど)、参加者はめいめい好きなトピックを選んで座る。で、ごはんを食べながら 1.5 時間くらいそのトピックについてしゃべる。このスタイルは、学会とか勉強会などで有効なんじゃないかな。初対面の者どうしが同席して話し始めるきっかけとして。コミュニケーションツールとしてのランチディスカッション。

あと、会場ではインターネットが使えない。 Wifi も電源も提供されていない。パターソン曰く「Wifi はここにはないよ。数百ドルも出して参加するカンファレンスで、席に座ってやっていることといったら話も聞かずメールチェック、ではなんとももったいないじゃないか。ディスカッションに参加しよう」。まったくだなー、と。ライブ感、参加している場にある価値といったものが、ネットで損なわれてしまいがちなんだ。

会場はちょっとダウンタウンから離れてるし、近くに店もなく、合宿みたいなノリだった。泊まった部屋もルームシェアリングになっていて、とにかくコミュニケーションが促進された2日間だったな。

ああ、ぜんぜん技術的なことを書いていなかった。主流は、 性能よりも生産性を というところにあったと思う。 100% カリカリに並列プログラムをチューニングするのはコストがかかりすぎるし、人にまるでやさしくない。 80% の性能しか出ないけど、人が考えやすいモデル、というのが今の方向性なんだろう。

出て行って交わると、自分の研究者としての能力がどれくらいか、というのがよく分かる。井の中の蛙にならないように、あっちこっちでアウトプットしないとだな。

Tags: concurrency, Event

LL Tiger

August 28th, 2010 | Published in CS

さんに誘われ、というセッションに登壇させていただきました。

スライドはこちら:

View more from .

ビデオはこちら:

~~まとめテキストなどは、9月になったら…~~

2010-09-01 23:45 追記:

スライドと映像とでほとんどのところは言い尽くしているので、大事なところと端折ったところだけ。

メッセージはなんだったか

マルチコア時代は、 JVM ベースの処理系が流行るだろう
メニーコア時代は、メッセージパッシングが流行るだろう
スレッドを生で使うのはない

順に見ていきます。

マルチコア時代は、 JVM ベースの処理系が流行るだろう

この先5年くらいは、まだマルチコアの時代のはず。メモリを共有するいくつかのコアがいる。そこで重要なのはマルチスレッドでの性能であり、そのあたりをきちんと面倒見てくれる JVM を土台とした言語処理系が流行ると見ています。 Scala, JRuby, Jython, Clojure, Mirah などなど。特に、なんでもあり過渡期言語としての Scala に期待があります。

メニーコア時代は、メッセージパッシングが流行るだろう

その先のメニーコア時代になると、 Memory Wall を崩せなくて、ソフトウェアはメッセージパッシングをベースにすることになると予想しています。 Scala や Erlang といったアクターモデルの並列プログラミングができる LL とか。 MPI は Fortran のごとくしぶとく生き残っていそう… とはいえ、これまでの考え方からのギャップがわりと大きいので、現実的にやるとすれば、いま使っているプログラミングモデルはそのままで、下ではメッセージパッシングで処理系ががんばって動く、という方向だろう。

スレッドを生で使うのはない

でまぁ、しばらくはマルチスレッドでプログラムは並列に動くことになるんだけど、スレッドを生で使い続けることはないだろう。これまで十数年とマルチスレッドプログラミングがなされてきたけれど、いまだに難しいとされている。これはつまり、人間には難しすぎるということだ。学会に行っても、けっきょく未解決問題として扱われているわけで、「難しい問題なら、解かずにおこう (そして研究のネタとして生かし続けよう)」というジョークがあるくらいだ。天才にすら難しいマルチスレッドプログラミングが、エンドユーザプログラミングの時代になんとかなるはずがない。スレッドはアセンブリのようなものなのだ。

そんなわけで、いろんな抽象が考えられている。 Grand Central Dispatch とか、まぁいろいろ。その中でも、メッセージパッシングが重要となるだろう。そもそも状態を共有するからマルチスレッドプログラミングは難しいわけで、状態を共有せず、逐一お互いの状態を問い合わせるようにするメッセージパッシングは、いまはまだ主流じゃないかもしれないけれど、この先はわからんものです。

いまがチャンス

並列コンピューティングが常識になった時代に、さすがに C でプログラミングし続けるのはないだろう。もはやパラダイムが変わってしまっているのだ。「過去の資産を活かしたい」とかよく聞くけれど、それはもはや負の遺産だったりしない? ごついふつうの C プログラムを、多大なリソースをかけて並列化するのは、なんともしんどいし、最初から並列に書いてしまう方がすっきりするよね。これから現れる21世紀プログラマは、さいしょから並列プログラミングしててもおかしくないし、むしろそうなってるべき。そんなプログラミングの世界を切り拓いていきたいものです。

新しいパラダイムには、新しいプログラミングモデルがあってしかるべきで、それはたぶん C じゃない。 C はアセンブリ的なものとして残るかもしれないけれど、並列に書くところは別の言語になるだろう。つまり、ついに C からの脱却がありそうなのだ。そして、まだ決定打はどこも出せていない。今がチャンス! なのです。デファクトをとって勝つる!

Tags: concurrency, Event

Ruby GIL test

July 29th, 2010 | Published in CS

ruby 1.9 で、スレッドはネイティブスレッドを使うようになったけど、 GIL があるためにけっきょく実行は serialize されてしまう、マルチコアを活かせないよというのは、まぁ聞いて知ってたんだけど、ほんとにそうなのか試した。

ruby 1.9.2dev on Core 2 Duo な Mac OS X 10.6.2 で動かして ActivityMonitor.app で眺めていたところ、たしかに CPU 使用率は 99% くらい。1つのコアでがんばってなさる。

ちなみに GIL がないという MacRuby 0.6 リリース版で試したところ、以下のような assertion にひっかかっていた。 GCD かな? ソース追ってみないと。

Assertion failed: ((b->flags & flags) == flags), function rb_vm_prepare_block, file dispatcher.cpp, line 1773.

さしあたり、 ticket きっておいた。

追記 2010-07-30 09:24 JST

最新版では治ってるよということで ticket が瞬殺されていた。じっさい latest nightly build で試すと、ちゃんと 2 コアを使って計算が行われいるのを確認できた。

M=10000 で、 time $RUBY_VM gil_test.rb として計測した結果:

ruby 1.8.7 : 100%, 69.3s
ruby 1.9.2dev : 100%, 22.6s
MacRuby 0.7 : 191%, 6.85s
JRuby 1.5.1 : 178%, 21.9s

MacRuby が圧倒的な速度である。まあほんとうは VM の起動時間とかを含めないように、 time じゃなくて benchmark.rb とか使うべきなのかもだけれど、ユーザの体感時間という意味で。

Tags: concurrency, Ruby

let GCD deadlock

July 28th, 2010 | Published in CS

夏だし、 Grand Central Dispatch (GCD) をデッドロックさせてみたい。

さらっとぐぐって見つけた、デッドロックさせるコードはこんなかんじ:

  void deadlock_1()
  {
     dispatch_queue_t q = dispatch_queue_create("org.deadbeaf.gcd3", NULL);
     dispatch_sync(q, ^{
        printf("in 1\n");
        dispatch_sync(q, ^{
           printf("in 2\n");
        });
     });
  }

で、まぁたしかに処理がすすまなくなる。

でもこのコードからはなんだか、デッドロックというか自分を追い越せないだけな感じを受ける。ひとつのキューがあって、そこにつっこまれた人が、自分が終わる前に他のものをつっこんでいて、無限に待つという。

デッドロックというのは、2つ以上の共有資源があるときに、かたっぽ (A) を自分 (α) のものにしていながら、もうかたっぽのもの (B) をとろうとして、でも B はだれか (β) さんがロックしていて、で β さんは A がほしくて、というすくみの状況を言うんじゃなかったっけか。

というのを踏まえて、以下のように書いてみた。共有資源は 2 つ、 GCD の serial queue は、リソースを占有したいときに使うはずなので、 queue もそれぞれ用に 2 つ。

  void deadlock_2()
  {
     __block int shared_resource_1 = 0;
     __block int shared_resource_2 = 0;

     dispatch_queue_t q1 = dispatch_queue_create("org.deadbeaf.gcd1", NULL);
     dispatch_queue_t q2 = dispatch_queue_create("org.deadbeaf.gcd2", NULL);

     dispatch_group_t group = dispatch_group_create();
     dispatch_queue_t the_q = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

     dispatch_group_async(group, the_q, ^{
        dispatch_sync(q1, ^{
           printf("in q1\n");
           dispatch_sync(q2, ^{
              printf("hello from q1->q2\n");
              shared_resource_2 = 3;
           });
           shared_resource_1 = 5;
        });

     });

     dispatch_group_async(group, the_q, ^{
        dispatch_sync(q2, ^{
           printf("in q2\n");
           dispatch_sync(q1, ^{
              printf("hello from q2->q1\n");
           shared_resource_1 = 11;
           });
           shared_resource_2 = 7;
        });
     });

     dispatch_group_wait(group, DISPATCH_TIME_FOREVER);
     dispatch_release(group);
     dispatch_release(q1);
     dispatch_release(q2);
  }

これだと、うまくいくときは


%  ./gcd_deadlock
in q1
hello from q1->q2
in q2
hello from q2->q1

となるんだけど、タイミングによっては


./gcd_deadlock
in q1
in q2
....

と無限に待つ。デッドロックが起きているのだ。

まとめると、 GCD でもデッドロックはわりと容易に起こりうるなぁと。で、それがかんたんに検出できるんだったらいいんだけど、そこは pthread mutex における検出のむずかしさとあまり変わらないんじゃないかなぁというところ。

Tags: concurrency, grand_central_dispatch

Perl, Concurrency

July 28th, 2010 | Published in CS

Perl をつかった並行プログラミングをしらべていた。 Perl はずぶの素人なのでつっこみ希望です。

歴史

5.005-5.6 までは thread パッケージをつかっていた。 green | native ?
5.6 から ithread (interpreter thread) が入り、 thread ごとに VM が割り当てられるように。 native thread で、共有変数は明示的に shared とつけないといけない。 default で shared nothing.
6.0 から STM が入るらしい。 atomic 構文。他に、 async block という構文ができて、どこかのスレッドで非同期実行させることができる (これは 5.10 でも use Thread qw(async) とすれば使えるな..)。 hyper, cross, reduction operator はデータ並列として扱えるようになっていて、コンパイラが並列実行するコードを出力できる
最近の流行りは、サーバサイドでたくさんのリクエストを高速にさばくための非同期 I/O で、イベントを処理する POE, AnyEvent, Coro といったライブラリ/フレームワークがある

5.005-5.6 ではスレッドが並行処理の道具としてあった。5.6 で入った ithread は shared nothing なのがグー。 6.0 からは野心的な構文ががが。ライブラリ方面では、非同期 I/O まわりがホット、といったところでしょうか。

印象

ithread の multi VM のつくりは、 Ruby でいう GIL, Python でいう GVL がないそうでスケールしそう。 VM をまたいだやりとりは shared な変数を使うんではなくてメッセージパッシングでやるのがいいんじゃないかなぁとか。アクター、アクター。

情報元

Tags: concurrency, perl

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 問題はどのようにして書けばいいのか。仮説として、次のものを思いつきました。

静的解析をやってしまう : Block 間の依存関係を、コンパイル時にすべてしらべあげてしまうとか
書けないようにする : 共有データを 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 リリースを待ちます。

参考

Intel: Concurrent Collection for C/C++, Threading Building Blocks, Ct
OpenMP