アカウント名:
パスワード:
この研究は，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 の選択オプションが追加されることになると思います．
多分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をつかうらしい。
メモリアクセスがin-orderになるアルゴリズムとout-of-orderになるアルゴリズムの比較の話ですか。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
※ただしPHPを除く -- あるAdmin
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になるアルゴリズムの比較の話ですか。