トップスポーツチームの監督に教わる秘訣
この論文では、氏が発見した原則を要約し、その原則をいかにしてソフトウェア開発に応用するかを説明します。
News
JavaOne：Cliff Click氏がスケーラブルな非ブロッキングコーディングスタイルを語る
作者 Charles Humble, 翻訳者 編集部 投稿日 2008年6月1日 午後6時32分
1967年Gene Amdahl氏が指摘したのは、基本であると思われることが並行コードを作成する速度を制限するというものであった。プログラム処理のわずかな部分のみ が、完全に並行して実行することができ、より多くのプロセッサーコアを備えたマシン上で直接拡大縮小することができる。残りのプログラム処理は、シーケン シャルである。アムダールの法則が強調している主な問題は、ロック競合であり、プロセッサーコア数が増加するにつれてこの問題は深刻になる。たいていの大 規模なCPU共有メモリハードウェアシステムは非常にに高速な並行読み取りをサポートするが、その速度は「書き込みにつき1回のキャッシュミス」または 「書き込みにつき1回のメモリーバスのアップデート」に制限されているので、同一のロケーションに書き込みをしているすべてのCPUを回避することが重要 である。リーダーライターロックでさえ、50から100CPU範囲以上を拡張縮小することは不可能である。マルチコア処理は、ますます業界のトレンドに なってきており、ほとんどすべてのハードウェア製造業者は、この将来性について見極めている。Azulは768コアのハードウェアを製造し、Sunの Rockはおよそ64コアそしてx86ベースのハードウェアでさえ、使用するコア数を拡大している。このように、パフォーマンスコードを書き込むことを検 討しているデベロッパにとって、ロック競合の問題は急務の問題になっている。Azul Systemsの著名なエンジニアであるCliff Click氏が、今年のJavaOneで 講演をおこなった(スライドはこちら)(PDF・英語)。氏は、Javaでのスケーラブル、非ブロッキングコーディングスタイルに向けて大きく前進することを可能にした一 連の技法について説明した。広い意味では、氏のアプローチはある特定のスレッドをやめることは、全体的な進展を妨げないといった、非ブロッキングアルゴリ ズムを実装する。
Click氏による主なコンポーネントは、以下のとおりである。
- 大規模で高速な配列で、データの迅速な並行読み取りを可能にし、並行、増分、同時コピーを可能にするすべてのデータを保持する。
- これらの配列文字のアトミックアップデート(java.util.concurrent.Atomic.*を使用)。アトミックアップデートは、 Compare and Swap (CAS) (プロセッサーがAzul、Sparcまたはx86の場合) もしくはIBMプラットフォーム上ではLoad Linked/Store-conditional (LL/SC)を使用する。
- アトミックアップデートでビルドされ、論理的に配列文字ごとに複製されたFinite State Machine (FSM)。FSMは配列のサイズ変更をサポートし、書き込みの制御に使用される。
このような基本的なエレメントが整っているので、Click氏はロックがない多くのFSMステップからアルゴリズムを構築する。すなわちそれぞれのCAS が進展する。CASの成功はローカルな成功である一方、CASの失敗は別のCASの成功を意味する。CASがうまくいけば状態マシンが前進するが、失敗し たCASは再試行する。
Click氏は、SourceForgeで 利用可能なコード(source)で2つの例(ビットベクトルおよびハッシュテーブル)を実装した。そして、3つ目(FIFOキュー)に取り組んでいる。一例を少し詳しく みると、ハッシュテーブルは偶数スロットにキーが、奇数スロットに値があるKey Valueのペアの配列である。それぞれの文字は別個に比較され交換されるが、状態マシンは両方の文字に及び、コピー時は両方の配列からの文字を含む。 ハッシュテーブルの実装は、並行挿入、テストの除去、サイズ変更およびConcurrentHashMap向けのJava Compatibility Kit (JCK)を渡す。Azulのハードウェアでは、768CPUまでリニアスケーリングを実現し、1秒につき10億以上の読み出しと同時に1秒につき1000万以上のアップデートが可能。
InfoQは、Click氏に自身の研究について詳細を尋ねた。JavaOneで の講演で、Javaにおけるハッシュテーブルの実装の記述に関わる問題のいくつかを強調した。そこで、この種の作業にJavaがどれほど適しているのかを 尋ねた。「実際、かなり適している。理解に優れたメモリーモデルがある(そして実装もうまくされている)。微調整の問題が不足している。多少パフォーマン スを犠牲するにつれ、無視することができる。この微調整の欠如(すなわち、direct ASM access)がたとえば、OS設計やデバイスドライバーなどの問題となる可能性があるが、パフォーマンスデータ構造の問題とはならない」。
また、データ構造の1つを使用するのは、いつが良いのかを尋ねた。氏のアドバイスは、「試行および真の」代替が遅すぎて有用でないときに使用すること、というものであった。
「1つのデータ構造が競合している場合、すでに java.util.concurrent.ConcurrentHashMapなどを試した。一般的にスタッフは、ロードがなければやや早い(であるから、それを使用する正当な理由がない)、そして非常によく作業する。
- 32以上のCPUの競合、または
- 書き込み対読み取りの高確率
当然ながら、メリットが変わる場合があるので、使用前にテストをする」。
現在、Javaでは並行性にまつわる活動が活発であり、Click氏はJava 7で検討されているフォーク/ジョインフレームワーク(参考記事・英語)と同様の問題に取り組んでいる。エキスパート集団の一員ではないが、定期的にClick氏は相談を受ける。
原文はこちらです：
関連情報
12/16 ～野村総合研究所が提案～ 「不況を乗り切る！効果的なIT投資を考えるセミナー」
InfoQ Japanはコンポーネントスクエアが運営しています
12/5 CSQ会員限定技術情報交換会にてJCP議長が標準化について語る
No comments
返信