スレッド実行機構 TU

start

non-loop sequence

non-loop sequence speculative parallel execution (loop)

speculative parallel execution (loop)

single thread execution mode

multi thread execution mode

single thread execution mode

multi thread execution mode

end

non-loop sequence single thread execution mode

図 3.11: PALSにおけるプログラム実行の概念図

図3.11にPALSにおけるプログラム実行の概念図を示す．まず対象プログラム に対してパスプロファイリングを行うことにより，ループ中から#1パスおよび#2 パスを抽出し，パス部分のコードをもとに投機スレッドコードを作成する．

PALSでは，投機の対象であるループ以外の逐次処理は，従来のプロセッサと同 様の動作であるシングルスレッド実行モードとしてTU1台で実行する．そして，

ループの直前に挿入したstart2path命令を実行するとPALSはマルチスレッド実 行モードとなり，複数台のTUで投機スレッドコードを並列に実行する．投機ス レッドコードにはループの終了判定を行う部分にstop2path命令を挿入しておき，

これを実行するとシングルスレッド実行モードに戻る．PALSは，プログラムが終 了するまでこれらの実行モードを切り替えながら実行する．

スレッド間通信による同期待ち時間

マルチスレッド実行時において，スレッド間の同期を取りプログラムの整合性 を保つために，スレッド間通信を行う必要がある．スレッドの並列性を低下させ ないためには，高速かつ低オーバヘッドなスレッド間通信が求められる．

スレッド間通信をする際の手段として，TUが持つレジスタの値を直接次のス レッドを実行しているプロセッサに送るレジスタ間通信と，TUが利用するMBを 介してデータを送るメモリ間通信が挙げられる．メモリ間通信については3.2.7節 で述べ，ここではレジスタ間通信について述べる．

2パス限定投機方式では，イタレーションを対象とした投機実行を行うため，ルー プ依存の変数の通信が頻繁に行われると考えられる．ループ依存の変数は，直前 のイタレーションで計算された値を自スレッドの計算に用いることが多い．例と して，ループの実行イタレーションを計数するループカウンタや，配列や構造体 のメンバに順にアクセスするために用いるメモリアドレス等が挙げられる．

したがって，投機スレッドで計算したデータをレジスタに格納すると同時に，当 該レジスタのデータを直接後続の投機スレッドに送信することが効率的であると 考えられる．また，レジスタに関する依存関係は全て静的に解析可能であるため，

投機スレッドコード中に静的なデータ依存がある場合，スレッド間でレジスタの 同期を行うことによりデータの依存違反の発生を防ぐことができる．

そこで，投機スレッドコードを作成する際に静的データ依存を解析し，投機ス レッドコードにおいて最後にレジスタの値を更新する命令に対して，制御ビット としてforward bitを付加する．forward bitが付加された命令を実行したTUは，

後続スレッドのTUに更新したレジスタのデータを送信する．

一方，後続スレッドのTUは，同期を取るため送信されてくるレジスタのデー タを受信するまでは，当該レジスタを使用した命令を実行してはならない．デー タの受信より先にレジスタを使用してしまった場合，レジスタデータ依存違反と なりプログラムの整合性がとれなくなってしまう．しかしながら，先行するスレッ ドから送られるすべてのデータを受信するまでスレッドの実行を開始しない場合 には，送られてくるデータに依存しない命令の実行ができなくなり無駄な待ち時 間が生じる可能性がある．

そこで，スレッド間での依存関係となるレジスタのデータを確実に受信しつつ，

そのデータに依存しない命令の実行は進められるように，PALSでは送信するレジ

スタ番号の一覧を示す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が付 加されている命令を出来る限りコードの前方へ移動するスケジューリングを行う ことで，同期待ち時間の低減が期待できる．