メモリアクセス機構 MAU

スタ番号の一覧を示すwait bit maskを用意する．wait bit maskはレジスタの個数 分の長さのビット列であり，LSBが0番レジスタに対応する．wait bit maskにお いて1であるビットに対応するレジスタを使用する命令を読み込んだ場合，命令 の実行を一時中断し，先行スレッドからレジスタの値が送信されるのを待つ．投 機スレッドコードの実行においては，同一レジスタのデータは一度しか送信され ないため，データを受信した際には対応するwait bit maskの値を0にする．

図3.12にforward bitとwait bit maskの関係を示す．図中では，TU#0が先行 して投機スレッドを実行しており，TU#1がそれに続いて投機スレッドを実行し ている．この投機スレッドコードでは，4番レジスタと2番レジスタのデータが 送信されるものとする．TUが32個のレジスタを持つ場合，wait bit maskの値は 0000 0000 0000 0000 0000 0000 0000 0000 0001 0100 となる (LSBが0番 レジスタに対応する)．

TU#1が実行するaddu命令は，2番レジスタに1を加算して3番レジスタに格 納する命令である．ここで，TU#1はwait bit maskの2番レジスタに対応する ビットを確認する．当該ビットは1になっているため，TU#1は2番レジスタの データが先行する投機スレッドから送信されるまで同期待ちを行う．

図中ではTU#0が実行している投機スレッドコードにおいて，2番レジスタの データを更新するaddu命令，および，4番レジスタのデータを更新するmove命令

にforward bitを付加している．TU#0はこれらの命令を実行した後，更新したレ

ジスタのデータをTU#1に送信する．データを受信したTU#1は，対応するwait

bit maskのビットを0にする．2番レジスタのデータを受信した場合，TU#1の

wait bit maskの下位8ビットは，0001 0000となる．そして，受信したデータを 使って命令の実行を再開する．

以上の方法により，レジスタにおけるデータの依存違反を発生させずにレジス タ間通信を実現することができる．投機スレッドコード作成時にforward bitが付 加されている命令を出来る限りコードの前方へ移動するスケジューリングを行う ことで，同期待ち時間の低減が期待できる．

addu/.fwd

$L_no1path:

$2, $4, 1 TU #0

wait bit mask register

0000 0000 0000 0000 0000 0000 0001 0100

addu

$L_no1path:

TU #1

$3, $2, 1

data transfer

waiting time for synchronization

thread code thread code

addu $4, $2, 1

MSB (=$31) LSB (=$0)

execute instruction

図 3.12: forward bitとwait bit mask registerを用いたTU間のレジスタデータ 転送

とMBの補助的役割を担うLoad Shelter (LS) によりMAUを構成する．

MBによるスレッド間通信のサポート

3.2.6節で述べたスレッド間通信をサポートするため，PALSでは隣接するMB

間での投機的なメモリデータの通信を実現する (以下，MB間通信)．このためMB では，TUから渡されるアドレスとデータの対に，複数の制御ビットを付加した ものを1つのエントリとして扱う．アドレスとデータの対を記憶することにより，

MB内に要求されたアドレスのエントリが存在するか否かを判定することができる．

制御ビットは，(1) エントリが有効であることを示すvalid bit，(2) 自身と接続 しているTU (自TU)によるストアデータであることを示すspeculative write bit，(3) 後続スレッドのMB (後続MB) によって読み出されたデータであること を示すspeculative read bit，(4) 先行スレッドのMB (先行MB) またはキャッ シュに対するデータの要求が自身から発行されたエントリであることを示すself query bit，(5) 先行MBまたはキャッシュに対するデータの要求が後続MBから 発行されたエントリであることを示すother query bitの5つのビットにより構 成する．

メモリ依存違反への対応

MB間通信では同期制御を行わず，FranklinらのARB[26]と同様の方法で依存 違反を検出することで投機メモリデータの整合性を保つ．MBは，後続MBから 読み込まれたアドレスを記録し，自TUからの当該アドレスへの新たなストアが 行われた場合に，メモリ依存違反検出として後続スレッドを破棄する．

図3.13にメモリ依存違反を検出するときの実行の様子を示す．先頭スレッドは アドレスXのデータをL1データキャッシュからロードし，後続スレッドは同命 令を実行した際にアドレスXに対するデータ要求を先行スレッドへ送る．データ 要求を受け取った先頭スレッドのMBは，アドレスXを格納しているエントリの speculative read bitを1にすることで，後続スレッドから読み出されたことを 記録する．

その後，先頭スレッドがアドレスXに対してストアを行った場合，後続スレッ ドに送った投機メモリデータは誤りであり，メモリ依存違反となるため後続スレッ ドの実行を破棄する．先行スレッドのパス予測失敗により投機スレッドが破棄さ れた場合は，パス履歴が変化しているため再度パス予測を行う必要があるが，先 行スレッドのメモリ依存違反検出により破棄される場合は，投機スレッド実行の タイミングが原因でありパス予測の成否とは関係がない．このため，メモリ依存 違反により投機スレッドが破棄された場合は，回復処理を行った後，それまで実 行していたパスを再度実行する．

エントリ枯渇への対応

MBでは，後続のMBから要求されたアドレスのエントリをスレッドの終了ま で保持することで，当該アドレスに新たなストアが行われた場合のデータの依存 違反の検出を実現している．このエントリのため，MBのエントリが全て消費さ れ枯渇する可能性がある．特に，先頭スレッドにおいてエントリが枯渇してしまっ た場合，自スレッドのTUからの投機的なストアデータを格納することができず，

プログラムの実行を続けることができなくなる．

この問題に対して，後続のMBによって作成されたエントリを待避させるため のメモリとしてLSを用意する．PALSでは，先頭スレッドの実行は後続スレッド の実行に大きく影響し，先頭スレッドの停止はプログラム全体の停止となるため，

time ^TMU

data request

data reply load X

store X

load X

detection of memory dependence violation

squash

squash load X

#1-path code #2-path code recovery

generate speculative thread

waiting tine

図 3.13: メモリ依存違反検出時の実行の様子

先頭スレッドのみがLSを使用する．エントリの枯渇が起きた場合，後続スレッド の要求により作成されたエントリからひとつを選び，当該エントリに格納されて いるアドレスをLSに待避させることで，MBに空きエントリを作る．LSにより，

TUからのストアデータを空きエントリへ確実に格納することができる．

図3.14にMAUおよびMAUと接続されるハードウェア機構の構成図を示す．ま た，図3.15にMBおよびLSのエントリの構成を示す．MBのエントリは，制御 ビット，アドレス，データにより構成される．LSのエントリは，制御ビットとア ドレスにより構成される．LSを使用するのは先頭スレッドのMBのみであるため，

各MBとLSはバス接続とすることで資源量を抑えることができる．

図3.15に示すように，MBでは1エントリに69ビットが必要となる．PISAに おけるメモリアクセス命令において，メモリアクセスを行うときのデータサイズ には，バイト (8ビット)，ハーフワード(16ビット)，ワード (32ビット)，ダブル ワード (64ビット)といった種類があるが，MBではデータを4バイト (32ビット) のワード単位で管理する．すなわち，バイト・ハーフワードのデータを格納する 際にも1ワード分のメモリ領域を使用し，ダブルワードのデータを格納する際に はエントリを2つ使用することになる．

Thread Unit

TU (TU) TU

Memory Buffer

(MB) MB

MB

Load Shelter (LS)

data cache

communication hardware

図 3.14: MAUのハードウェア接続関係

MBにおいて自TUあるいは後続スレッドのMBが発行したデータ要求のため のエントリ (speculative read bitが1であるエントリ) によって，自TUから のストアデータを格納するためのエントリが不足する場合には，LSにデータ要求 のエントリを退避させる．このため，LSのエントリはストアに関する制御ビット であるspeculative write bit，およびデータ格納のための32ビットを必要と せず，4(制御ビット) + 32(アドレス)の36ビットが必要となる．