投機実行モデル

投機的並列実行においては，投機実行したパスが誤りであった場合(以下，投機 失敗と呼ぶ) に，投機を諦めプログラムのオリジナルコードを逐次実行する方法 と，異なるパスを再度投機実行する方法の2つの選択肢が考えられる．文献[9]で は，1度のみ投機実行するSingle Speculation方式と，投機失敗時に投機対象とし た2本のパスのうち，投機実行していないもう一方のパスも投機実行するDouble Speculation方式の性能を比較した．その結果，Double Speculation方式が高い性 能を示すことを明らかにした．これは，投機スレッドコード中に含まれるassert 命令によって，投機実行開始後の早期に投機失敗を判定できたことによる．

図3.7に，Double Speculation方式である2パス限定投機方式の実行を示す．図

3.7 (a) は，3つのプロセッサコアに対して，3つの投機スレッドを割り当て，それ

らのすべてのスレッドが投機成功した場合の実行である．また，図3.7 (b) は，2 スレッド目において投機失敗，すなわちassert命令の結果が偽となった場合の実 行であり，図3.7 (c) は，2スレッド目において投機失敗が二度起こった場合の実 行である．

図では，上から下へ時間が経過するものとしている．図中の四角はプロセッサコ ア上での処理を表しており，縦につながっているものは同一のプロセッサコアで実 行されることを意味する．(a) におけるsequential executionは，単独のプロセッサ コアによる逐次実行を示しており，speculative multithread executionは，マルチコ アプロセッサによる2パス限定投機方式の投機的並列実行を示している．#1-path

code，#2-path codeは，投機対象としたループから抽出した2本のパスの投機ス

レッドコードであり，各プロセッサコアに割り当てられ，並列に投機実行される．

original loop codeは，投機が失敗したときに実行するスレッドコードであり，元々

のループのコードそのものである．recoveryは，あるスレッドで投機失敗が起こっ た場合に，当該スレッドの実行前の状態にプロセッサコアを戻すための回復処理 である．具体的には，レジスタやメモリの内容を，投機実行開始時に保存した内 容へロールバックする処理が行われる．図中の実線矢印は，投機スレッド生成の 指示を表している．投機スレッド生成の指示によりスレッドを割り当てられたプ ロセッサコアは，投機スレッドを割り当てられていない別のプロセッサコアに対 して，次の投機スレッドの生成を指示する．図中の破線矢印は，あるスレッドに おいて投機が失敗した際に，当該スレッド以降のスレッドを破棄する流れを表し ている．投機スレッド生成と同様に，投機スレッド破棄を指示されたスレッドは，

次のスレッドに対して破棄を指示する．

図3.7 (a)では，3イタレーションを逐次実行した場合と，すべてのスレッドが

投機成功した場合を比較している．この場合，理想的には2回分の投機スレッド 生成の指示にかかる時間と，3イタレーション目のパスの実行にかかる時間の合計 が実行時間となる．このため，逐次実行に比べて大幅な速度向上を達成すること ができる．実際には，イタレーション間 (スレッド間)に存在する依存関係により 生じる同期待ち時間により，実行時間が増大する可能性がある．

図3.7 (b) および (c) は，2つ目のプロセッサコア上での投機スレッド実行が1

度または2度の投機失敗を起こした場合の状況を示している．2イタレーション目 は実際とは異なる#1パスが投機実行されていたため，投機スレッドコード内に含

まれるassert命令によりパスの予測失敗が検出される．当該スレッドを実行して

いるプロセッサコアは，後続スレッドを実行しているプロセッサコアに投機スレッ ドの破棄を指示し，自身は回復処理を行い投機スレッド実行前の状態に戻る．そ して，もう一方のパス (図の場合は#1パスコード) の投機実行を開始する．後続

スレッドを投機実行していたプロセッサコアは，あらためてパスの予測結果に基 づいて投機実行を開始することとなる．

図3.7 (c) は，2イタレーション目で実際に#1パスと#2パスのどちらでもない

パスが実行される場合の状況を示している．2イタレーション目を実行しているプ ロセッサコアは，まずパスの予測結果にもとづいて1度目の投機実行を開始する (図の場合は#2パスコード)．その後，assert命令よりパスの予測失敗が検出さ れ，(b) の場合と同様に自身およびその後続の投機スレッド実行を破棄し，回復処 理を行う．そして，次はもう一方の投機スレッドコード (図の場合は#1パスコー ド)を実行するが，再びassert命令によりパスの予測失敗を検出され，自身およ びその後続の投機スレッドの破棄と回復処理を行う．2度目の投機失敗となった場 合は，オリジナルのループコードを実行する．これにより，プロセッサコアは逐 次実行することで正しい実行結果を得る．

time time

time

recovery

generate speculative thread

#1-path code

#2-path code original loop code

squash next thread performance

improvement sequential

execution

speculative parallel execution

iter.

1

iter.

2

iter.

3

iter.

1 iter.

2 iter.

3

(b) 1 !"#$%&'()*+,!-. (c) 2 !"#$%&'()*+,!-.

assert failure

(a) !"#$%&'()*+

図 3.7: Double Speculation方式の2パス限定投機方式による実行