読者です 読者をやめる 読者になる 読者になる

uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかFregeとかJavaとか -

細粒度並列処理について

java groovy gpars jsr166y

JSR-166yはJava 7で導入が予定されている、細粒度並列処理を効率よく行うことができるようにするためのライブラリ群です。Java7でjava.util.concurrent.forkjoinパッケージで提供される予定ですが、実は今でもダウンロードして利用できます。本記事ではこれが何のためのものでJava開発にどのようにかかわってくるか、を概要として解説します。JSR-166yの詳細およびfolk/joinアルゴリズムそのものについては解説しません。それらについては末尾の参考リンク先をどうぞ。

細粒度並行処理とは何か

new Thread()とかExecutorServiceでいちいち、どっこいしょ、と処理を始める(往々にしてその処理はプログラムが終了するまで続く)というのを祖粒度並行処理と呼びます。そうではなく、1回のソート処理を複数スレッドで実行するとか(並行ソート)、forループの繰り返し処理を1つのスレッドで逐次処理していくのではなく、繰り返しのそれぞれの段階を複数のスレッドで手分けして実行するとか、「一つの処理」の中で複数のスレッドをこまめに使いこなすというような処理です。たとえばgparsでいうと、

     final List result = [1, 2, 3, 4, 5].collectAsync {it * 2}
     // result == [2, 4, 6, 8, 10]

こんなかんじで、collectAsyncのところは非同期で複数のスレッドに分割されて実行されます。「息を吐くかのようにごく自然に並列処理」というわけです。

細粒度並行処理の意義

サーバ処理でスループットをあげるにはCPUを増やせばよいでしょう。ただし、この方法では個々のリクエストのレスポンスが短縮されるわけではありません。1度にたくさんのリクエストを処理できるようになるだけであり、個々のタスクの処理速度は向上しません(タスクが大量にあり、CPUが空きがなく、CPU空きの待ちが生じている場合には、CPUを追加することで待ち時間が減ることで処理時間が減りますが、いったん待ちが解消されたレベルでは、いくらCPUを増やしても処理時間がさらに向上することはありません)。

マルチコアのCPUでも同じことが言えます。アプリケーションやOSが適切にスレッドに分割配分されていなければ、コアがいくつ増えても無駄です。 CPUやコアを増やしても、同時に動作可能なタスク数が十分でなければ、コアが増えてもレスポンスはそれ以上は向上しません。簡略化した例で言うと、たとえばOSが1つ、アプリ1、アプリ2がそれぞれ1スレッドを使用しているとき、コアは3つまで増やせばレスポンスが向上しますが、あとは4つでも8つでも速度は同じです。

まとめると、コアやCPUが十分以上に利用できる環境では、それらを有効活用するために、いままで1リクエストのタスクで行っていた処理や、1スレッドでやっていた処理を、なんとかしてさらに細かいスレッドに分割して並列実行するようにする必要があります。性能向上という意味だけではなく、今まで必要だったマシン数が不要になり、無駄を省くことができるというケースもあるかもしれません。

背景として、現在の主力CPU開発では、1個1個のCPU自体の高速化(クロック向上とか)はいろいろな理由で頭打ち傾向なので、CPUメーカーはマルチコア化に力を注いでいるということが挙げられます。今後のCPUの性能向上を享受するためには、マルチコア(あるいはメニーコア)の活用を考える必要があります。

(追記:Tilera、100コアのCPUを発表という記事がありました)

並列化のチャンス

並列化を行う場所は、いくつか選択肢があります。

  • OSレベル
  • ライブラリ・データ構造レベル
  • フレームワークレベル
  • プログラミングレベル

細粒度並列化の場合、ライブラリ以下の部分になると思います。
JSR-166yはJavaプログラミングレベルでの解決策であり、比較的原始的なものです。これをつかって、細粒度並行処理を支援するフレームワークやライブラリ、データ構造を作っていくことは重要だし、実際にそのようにも使われていくと思われます。

ちなみに、 OSやフレームワークで、うまく並列化をするように隠蔽すれば、ユーザレベルのプログラミングでは並列化を意識しないでよい、という意見もあるかもしれませんし、それはそれでなされていくでしょう。実際、OSレベルとかはすでに結構並列化されています。「Giant Lock」とかで検索してみると良いでしょう。

ただ、並列化はそれなりにオーバーヘッドコストのかかる処理ですし、選択的に、意図を持って並列実行を指定できた方が効率が良い場合があります。また、ユーザコードが「ボトルネック」になっているならそこを解消しない限り全体のスケールも望めません。

それらのケースが、われわれが直接JSR-166yを使ってプログラミングすることになる動機です。しかし、JSR-166yはかなりプリミティブなレベルな部品なので、記述が煩雑になる可能性が高いです。Groovyではクロージャを使うことでその問題を改善できます。さらにGparallelizer改めgpars(Groovy Parallel System)は、並行処理のための高抽象レイヤ(データフロー、アクターモデル、並列コレクション処理)をGroovy DSLを駆使して提供するものであり、jsr166yライブラリを背後で使用しているものですが、これを使うことで記述が煩雑になることを抑えつつ、細粒度処理による性能向上を図ることができるでしょう。gparsについては別途語ることとします。

JSR-166yと従来のjava.util.concurrent.ExecutorServiceの違い

いずれも、スレッドプールを用いてスレッドを使いまわします。両者の違いは、JSR-166yはスレッドの切り替えに関して、細粒度タスク向けに最適化されていて、ExecutorServiceでは発生しうる待ち状態が極力発生しないようになっていて効率が優れています(「ワークスティーリング」と呼ばれる技法が用いられている)。また、JSR-166yはforkjoinという分割統治方による並列化サポートのアルゴリズムライブラリや、並列クエリ・集計を可能とするコレクションライブラリ「Paralell Array」などの機能を持っています。

なお、JSR-166yは細粒度タスクを効率よく実現する1ライブラリであり、これだけが細粒度タスクの実現方法ということではありません。

その他

関数型言語が注目を集めてるのも同じ背景ですね。関数型言語は並列実行に実に都合が良い性質があるからです。

広告を非表示にする