K.Sasada's Home Page

こめんとのついか

こめんとこめんと!

message

please add long comment :).

_13(Wed)

CAS (compare-and-swap) と LL/SC (load-linked/store-conditional) 、どっちが実装しやすい、ハードウェア的に有利なんだろう。

論文を探してるんだけど見つからない。


lock-free algorithm でいう LL/SC 命令は、プロセッサに載ってる LL/SC 命令よりも強い命令だったのだなぁ。知らなかった。(後者を restrected-LL/SC -> RLL/RSC と称しているらしい)。

rll/rsc 命令は (i) ll/sc が成功していても失敗するかもしんない(プロセッサの都合) (ii) ll/sc 命令の間に(共有)メモリアクセス禁止 という制限がある。

プロセッサのつくりを簡単にするためには、まぁ、そうだなとは思うけれど。


RLL/RSC 命令にはレベルがあるのか。

  1. ll bit を持っている
  2. ll bit と ll addr を持っている

前者は ll addr を持たないため、どんなキャッシュ一貫性制御が働いても rsc は失敗する。後者はその ll addr へのなんらかの一貫性制御が働いたら rsc は失敗する。

その辺を記述した論文が見つからん・・・。


CAS の実装ってどうなってるのかなぁ。load と store を一緒にしないといけない(かもしれない)から、複雑になるような気がするんだけど。Sparc や Itanium は CAS 使ってるらしいし。


ll addr は、なんか微妙に考えてるのと違うかも。。。


どうにも、探しても compare-and-swap と ll/sc は同等の記述力(意味)を持つ、くらいしか書いてない。ハードウェアに実装する視点からこれら二つを比べたものは無いものか。


compare-and-swap って、どうやって load/store 間の一貫性を保証してるんだろうか。データバスをロックしてしまう?


sparc のアーキテクチャマニュアルに載っている fetch-and-add の例。

FetchAndAddCAS(address => %i0, increment => %i1)
retry:
  ld   [%i0], %l0   #=> %l0 = *%i0
  add  l0, %i1, %l1 #=> l1 = l0 + %i1
  cas  [%i0], %l0, %l1
  cmp  %l0, %l1
  bne  retry

ll/sc でやってみる。MIPS。

FetchAndAddLLSC(address => t1, increment => t2)
retry:
  ll   t3, (t1)
  add  t4, t3, t2 
  sc   t4, (t1)
  beqz t4, retry

うーん。ll/sc のほうがいろいろと有利な気がするんだけどなぁ。


Acquire 命令は、load/store を 1 命令で行うんだが、それは CAS でも同様。ならば、CAS を行う回路で、compare and sleep に変更するだけで実装可能なんだろうか。なんか、CAS が十分軽量に出来るのであれば、それはそれで非常にリーズナブルな気がしてきた。

うーん。どうしよう。

「Acquire は load/store を 1 命令で行うため、ll2/sc2 はいいものだ!」という主張が崩れる。どうしよう。

まぁ、命令の使いやすさは ll2/sc2 のほうがいいから、別に優位性は変わらないのだが。論文の書き方が変わってしまう。

どうしよう。


うーん。MIPS (か PowerPC)と Sparc (とか Intel 系)を同時に作ってる人に聞けば、そのよしあしがわかるね! って、そんな人いるのか。

キャッシュのコヒーレント制御プロトコルや、バスの設計にも依存する話だしな。どうしたもんだか。困った。

探しても探しても、CAS やら ll/sc を利用したアルゴリズムの話ばかり出てくる。


下位互換のために CAS にしてるのかなぁ。でも、Itanium の説明になってないな。

LL/SC から CAS はできるけど、CAS から LL/SC はできない。CAS が十分コストが少なければ問題ないんだけれど。はて。


IBM dW : Java technology : Javaの理論と実践: アトミックで行く - Japan

CASのような命令を使うと、もし他のスレッドが変数を変更するとCASがそれを検出(または失敗)し、アルゴリズムがその操作を繰り返すことができるので、他のスレッドが途中で変数を変更してしまう、という心配をせずにread-modify-writeシーケンスを実行するアルゴリズムが可能になります。リスト3はCAS操作の振る舞いを示しています(パフォーマンス特性は示していません)。しかしCASの真価は、ハードウェアで実装でき、しかも(大部分のプロセッサーでは)非常に軽量だということです。

非常に軽量なのかぁ・・・。


ll/sc の初出が A New Approach to Exclusive Data Access in Shared Memory Multiprocessors らしい。


きちんと「CAS などよりも latency とかの問題で優れてるし、RISC っぽくパイプラインシンプルになるぜ」って書いてある。

しかし、87年の論文の記述。さて、これを信用することができるのか。


cas の実装方法がどっかに載っていないものか。

cas で実装しか見つからない。


The dragon processor (ACM SIGARCH Volume 15 , Issue 5 (October 1987)) より。

CST: Conditonal Store

The implementation of CST is primarily in the cache; the IFU presents the cache with the ptr, old, and new words, issues a CST command, and receives the sample result word. Synchronization with other processors is not necessary unless the addressed cache line is shared and old equals sample.

キャッシュで追い出し禁止にしておけば済むから、バスは押さえなくてもいいってことか。

しかし、古い。

あとは、ll/sc と cas との比較が見つかればいいんだけれど(A New Approach to Exclusive Data Access in Shared Memory Multiprocessorsには載っているが、できれば最新の技術の元での比較)。


まだまだ Rubyist Magazine が Ruby Magazine だと思われている。まぁ、しょうがないか。


愛が冷めたのか知らん。


うーむ。CAS が十分速いプロセッサなら、SMT-block が簡単に適用できるような気がしてきたな。要するに、Acquire 命令にエラー処理加えるだけだから。そうなると、提案手法の意義が・・・。

まずいなー。

ロック獲得予約を前面に出せば、大丈夫だろうか。


QOLB ってなんだー。


コルビー


あー、今日はたくさん論文刷った。


むぅ、セーターの下が気になる。


Ruby と Smalltalk ってそんなに離れてないんだろうか。いろいろと大変そうだなぁというところは思いつくけど。別に否定はしませんが。楽しみではあります。


なんかえらそうだな、俺。

きっと俺より凄いので是非勉強させてください。

最近停滞中。


好きなだけ長いコメントをどうぞ。

お名前


back

tton 記述が使えます。YukiWikiな記述してりゃ問題ありません。

「行頭に#code」 と、「行頭に#end」 で挟むと、その間の行は pre で囲まれます。プログラムのソースを書くときに使ってください。

例:

#code

(なんかプログラム書く)

#end

リンクは

[[なまえ|http://www.example.org]]

とか

[[http://www.example.org]]

で貼れます。

$Date: 2003/04/28 10:27:51 $