MIT、大規模マルチコアCPUの効率を向上させるデータ構造を開発 6
ストーリー by hylom
ソフトの工夫も大事な時代 部門より
ソフトの工夫も大事な時代 部門より
taraiok 曰く、
マサチューセッツ工科大学の研究者が、大規模マルチコアプロセッサの効率を向上させるというデータ構造を開発したそうだ。現在のプライオリティキューを使用するアルゴリズムでは、8コアを超えるコアを追加するとパフォーマンスが急落する。複数のコアが同時に優先キューの先頭にアクセスしようとすると競合が生じためだ。新たに開発された「SprayListアルゴリズム」では、各コアがキューに最初の項目にアクセスする必要要件を緩和し、ランダムにタスクを割り当てることにしたという（ITWORLD、MITNews、Slashdot）。
こうしたランダムにタスクを割り当てる方式は過去にも考えられたことがあるが、キャッシュの効率が落ちると批判され使われてこなかった。しかし、コア数が増加した場合はメリットがデメリットを上回る状態になるようだ。80コアプロセッサをシミュレートした環境で実験したところ、コア数が増えるごとに直線的な性能向上が見られたとしている。
In-order vs. Out-of-order Execution (スコア:3, 参考になる)
この研究は，in-order実行とout-of-order実行のどちらが効率が良いか？という点を議論しているのだと思います．
一般論として
- アルゴリズムの違いという点では，in-order実行の方が，計算や実装が単純なので，OSのスケジューラは高速に稼働します．
- ハードウェアの利用効率という点では，out-of-order実行の方が，スケールしやすいので，CPUなどを有効活用（＝酷使）できます．
このような性質があるため， in-orderとout-of-orderは一長一短で，トレードオフの関係が生じてます
トレードオフがあるため，OSをチューニングするときは，
対象とするハードウェアのアーキテクチャに合わせた in-orderかout-of-orderの選択が必須となります
その結果，
- 現在主流のシングルコア・マルチコアな環境では，従来のスケジューラ，つまり in-order の方が都合がよく，性能が高かったが，
- 今後の主流になるであろうメニーコアな環境では， 今回の新しいスケジューラ， つまり out-of-orderの方が都合がよく，性能も高くなる
ことを示したのが，彼らの研究成果だと思います．
これは実に順当な結果です．たとえばOSではなく，CPUの実装でも似た話がたくさんあります．
すぐに思いつくのは，少々古い話になりますが，たとえば interlのCPUで PentiumIII(Cuppermine)とZ520(Silverthorne)を比べると
クロックはどちらも1GHz程度ですが
前者はout-of-order実行で，後者はin-order実行であり，
ベンチマークとか消費電力を比べると，条件によって性能差・得意不得意がありました．
このように，トレードオフの関係がある以上，チューニング時には In-order vs. Out-of-order のどちらかの選択が必須です．
たとえば，今のLinuxカーネルは，コンパイル時のオプションでスケジューラの挙動をある程度チューニングできるようになっていますが
今後は，このチューニングパラメータに in-order か out-of-order の選択オプションが追加されることになると思います．
Re:In-order vs. Out-of-order Execution (スコア:2)
多分SkipList [wikipedia.org]でマルチコアでもキャッシュ衝突の起こりにくい優先度付きキューを実装したって話、
データ構造に関係するのはアーキテクチャのメモリモデルだから、プロセッサがIn-order実行かOut-of-order実行かは無関係、
x86はOut-of-order実行でも基本的に機械語のメモリアクセス順が守られるが。armはIn-order実行でも守られるかは保障されない。
x86やArmやら普及しているアーキテクチャの大半は、レジスタサイズのメモリの読み書きは、未定義の値を読まないことが保障されている。
あるアドレスが指す領域が常に複数スレッドによって書き換えられていても、必ずいずれかのスレッドが書き込んだ値か初期値か、いずれかの時点でのメモリの値が読み込まれる。
これは、あるスレッドで値を更新して、他のスレッドで読み込むみたいな用途には使えないこともないけど、同時に追加、削除を行う様なデータ構造には不足
この場合、メモリバリアやCompare-and-Swap命令を使ってアトミックな書き換えを保障する。c++ならstd::atomicが提供してる。
大体レジスタサイズ≒ポインタサイズなので、動的確保したメモリのポインタならアトミックに更新できる。
ノードの参照関係で構築できるリンクリストや木構造は(色々制限はあっても)実装できることになる。
ただアトミック命令というのは、
書き込みが成功した場合、それ以後に実行されるどのスレッドからの読み込み命令でも必ず書き込んだ値が読み込めることを保障する命令なので。
近いメモリ領域を複数のスレッドが更新する場合、コア間のキャッシュ整合性を保障する処理が律速になりスケールしない、
マルチコアならL3キャッシュで処理できるけど、マルチCPUの場合、CPU間でメモリへの書き込み内容を共有する必要があるので性能的に厳しい
８コアから性能が劣化する云々は、ココらへんが原因のはず。
優先度付きキューの場合、追加は優先度が違えばキャッシュ衝突しない、
取り出しは最優先の要素を複数のスレッドが取り合うので頻繁にキャッシュ衝突が起こる。
これを解決するのに。SkipListをベースにしたSprayListをつかうらしい。
Re: (スコア:0)
メモリアクセスがin-orderになるアルゴリズムとout-of-orderになるアルゴリズムの比較の話ですか。
スケジューラがんばれ (スコア:1)
Re: (スコア:0)
1つのスケジューラサーバと多数の計算ノードというように考えているんだと思いますが、そううまく行きません。
なぜかというと、1つのスケジューラが計算ノードXにジョブに関する通信・計算をしている間は、
別のノードYは待たないといけないので、
1つのmutex lockのみを用る素朴な共有priority queue と同じになるからです。
素朴な共有priority queueでは並列性が下がり、多コアの時にスケールしません。
アムダールの法則も参照。
モンテカルロ法？ (スコア:0)
Ah!SKIで見た