アカウント名:
パスワード:
この研究は，in-order実行とout-of-order実行のどちらが効率が良いか？という点を議論しているのだと思います．
一般論として- アルゴリズムの違いという点では，in-order実行の方が，計算や実装が単純なので，OSのスケジューラは高速に稼働します．- ハードウェアの利用効率という点では，out-of-order実行の方が，スケールしやすいので，CPUなどを有効活用（＝酷使）できます．
このような性質があるため， in-orderとout-of-orderは一長一短で，トレードオフの関係が生じてます
トレードオフがあるため，OSをチューニングするときは，対象とするハードウェアのアーキテクチャに合
多分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をつかうらしい。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
Stableって古いって意味だっけ？ -- Debian初級
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をチューニングするときは，
対象とするハードウェアのアーキテクチャに合
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をつかうらしい。