: receiver
B: broadcast node
level 2: 100 level 1: 011 level 0: 100
s d d
100 011
B
100s d d
level 2: 110 level 1: 011 level 0: 100 100
011 110 110
(a) SM
(b) LARP
図4.2:ディレクトリ縮約方式
4 MINC 4.3. 枝苅りキャッシュ
4.3 枝苅りキャッシュ
縮約方式は大きな利点を持つ一方， 送る必要のないプロセッサにもパケットが届いてし まう問題がある．このメッセージは届いたプロセッサのキャッシュコントローラで捨ててし まえばよいのでプロトコル上の実害はないが，ラインを共有するプロセッサ数が増えると，
無駄なパケットによるBackward MINの混雑が性能低下の原因となってくる［KYN+95］．
そこで，Backward MIN上の特定の階層のスイッチに，枝苅りキャッシュと呼ばれるチッ
プ内部に実装できる程度の小容量のビットマップキャッシュを設ける．図4.3は，LARP型 の縮約方式に枝苅りキャッシュを適応させたものである． 枝苅りキャッシュは以下のよう に動作する．
• 読み出したラインをBackward MINを通して要求元のプロセッサに転送する際，通 過する枝苅りキャッシュ上にラインアドレス，対応するビットマップを登録する．既 にエントリが存在した場合は，ビットマップの変更を行う．
• Backward MINを通して更新データあるいは無効化パケットを送る時，枝苅りキャッ
シュが参照され， アドレスが一致したら枝苅りキャッシュのビットマップが利用され 必要な出力に対してのみパケットを送る．無効化型プロトコルを用いた場合は，枝 苅りキャッシュ上のエントリは，無効化パケットを送った時点で削除する．
5 Broadcast
Source Destination
001 000 000 000
000 010
000 101
Useless Traffic 1
011 011
110 Pruning Buffer
Stage
図4.3:枝苅りキャッシュ
枝苅りキャッシュは高速なアクセスが要求されるため，スイッチ内に実装することが必 要であるため，大容量のメモリを利用することができない．したがって，枝苅りキャッシュ の領域がなくなる場合が頻繁に起きると考えられる．そこで，枝苅キャッシュにエントリ する時に，既に枝苅キャッシュが埋まっていてエントリできない場合，エントリを諦める．
しかし，エントリが失われた後に，再びエントリが行なわれると，掃き出された枝苅キャッ シュに対応するビットがセットされていないのに，その枝苅キャッシュの管理下にあるプ ロセッサがラインを持っていることがあり得る．この場合，枝苅キャッシュと共有メモリに あるディレクトリの間で情報の不整合が生じ，パケットを正しい宛先に転送できなくなる．
4 MINC 4.3. 枝苅りキャッシュ 情報の不整合の発生について，枝苅キャッシュのエントリを諦めた場合の例を図4.4に 示す．プロセッサAが共有メモリのデータを読んだ時に，キャッシュラインはデータ転送 用のネットワークを通ってプロセッサに送られるが，枝苅キャッシュが埋まっているとエ ントリできない(図4.4上)．その後，書き込みの発生などで枝苅キャッシュに空きができ た後，先ほどとは別のプロセッサBが，同じキャッシュラインのデータを読んだ時，枝苅 キャッシュにはプロセッサBのみが登録される．従って，実際にキャッシュラインのコピー を持つプロセッサはAとBだが，枝苅キャッシュの指し示す情報はプロセッサBのみと なり，不整合が生じる(図4.4下)．このままマルチキャストを行なうと，枝苅キャッシュ でパケットの宛先を指定した結果，プロセッサAにはパケットが届かない．
そこで，マルチキャストパケットが正しく届くことを保証するために，枝苅キャッシュ が埋まっていた時の動作として，枝苅キャッシュへの登録を諦め，共有メモリに対してエ ントリに失敗したことを知らせる方式を採用している．
4.3.1 アクノリッジ信号線のパケット化
キャッシュ一致制御のパケットをBackward-MIN上でマルチキャストした時，転送の途 中でパケットが衝突し，目的のプロセッサのうちの一部のプロセッサにのみパケットが届 いて，残りの一部には届かないことがあり得る．
図4.5にマルチキャストパケットが衝突する例を示す．図では，メモリモジュールaか ら プロセッサA, B, C, Dにマルチキャストを行ない，同時に メモリモジュールbから プ ロセッサBにパケットを転送する．ここで，メモリモジュールbから送られたパケットが，
メモリモジュールaから送られるマルチキャストパケットよりも優先度が高く，ステージ 2のスイッチで図のように衝突した場合，マルチキャストパケットは，プロセッサBにの み届かない．この場合，届かなかったプロセッサに対して再送する必要があるが，単純に アクノリッジ信号のANDをとると，全ての宛先に届くようになるまで，アクノリッジが 返らなくなる．また，宛先を完全に特定するためには，アクノリッジを宛先毎に収集して，
共有メモリ側でビットマップを再構成しなくてはならない．
4 MINC 4.3. 枝苅りキャッシュ
1. Read
0101
Memory Side
PU Side Miss!!
2. Entry
− Bitmap − 0001 0010
Memory Side
PU Side 1st 2nd
− Bitmap − 0001