設計方針

2パス限定投機方式は，ループにおける1イタレーション(ループ1周分の実行) を1つのスレッドとして投機的にマルチスレッド実行することを基本としている．

同方式において，投機的並列実行を実現するために必要な機能として，以下のも のが考えられる．

• 投機対象とする2本のパスのどちらが実行されるかを予測する機構

• 投機実行の成否を判断する機構

• 投機失敗時にプログラムの整合性を保証する回復処理を行う機構

予測機構として，文献[9]におけるパス予測機構である，2レベル分岐予測をベー スとしたパス予測器をハードウェアとして実装する．プロセッサコアはパス予測 器から受け取った予測結果に従い，投機スレッドコードを実行することとなる．投 機スレッドを割り当てる方法としては，(1) 静的に割り当てる方法，(2) 動的に割 り当てる方法といった2つの方法が考えられる．(1) は，隣り合うプロセッサコア に対して順番にスレッドを割り当てていく方法であり，(2) はプロセッサコアの位 置関係は考慮せず，スレッドの実行が終わった順に新しいスレッドを割り当てる 方法である．3.1.5節で示した2パス限定投機方式を実現するためには，隣り合う プロセッサコアに対して順番にスレッドを割り当てる構造となる (1) の方法が自 然である．一般に，ループではループの実行回数を示すループカウンタを始めと して，イタレーション間において変数の依存関係が存在する．連続して実行され るループイタレーションを投機スレッドとして順番にプロセッサコアに割り当て ることにより，プロセッサコア間の接続関係が静的に決まりネットワークを単純 化できるため，プロセッサコア間のデータ通信の制御が簡単化できる．

2パス限定投機方式では，すべてのスレッドは投機実行されるため，先頭スレッ ドを実行するプロセッサコアにおいても投機失敗が起こりうる．投機が失敗した スレッドによって後続のスレッドに通信されたデータは誤りである可能性があり，

その誤ったデータを計算に使用した後続スレッドの実行もまた誤りとなる．従っ て，投機が失敗した場合，投機失敗となったスレッドおよび，その後続のすべて のスレッドの実行を破棄し，回復処理を行うことでプログラム実行の整合性を保 証することができる．この場合，破棄された後続スレッドに対しては，予測情報 を更新した後，再度予測を行いスレッドを起動する．これは，投機失敗となった スレッドによって，後続スレッドのパスの予測に用いた履歴レジスタの内容が更

新されるためである．このため，スレッドの生成や破棄，また，投機失敗時の回 復処理にかかる時間の増大は，並列実行性能に大きく影響する．そこで，PALS (2 パス限定投機システム)の第一の設計方針として，これらのオーバヘッドを出来る 限り小さくできるようなハードウェア実装を考える．

また，本論文では，複雑な制御構造を持つループを多く含む非数値処理系プログ ラムを特に並列化の対象としている．複雑な制御構造を持つループとしては，ルー プイタレーションにおける実行パスが複数存在することや，ループイタレーション 間におけるデータ依存関係が多く存在することが考えられる．投機的並列実行に よりループを並列実行する際には，プログラムの整合性を保つために正しいタイ ミングで依存関係にあるデータの同期を取る必要があるが，この同期待ち時間に よってもマルチスレッド実行の並列性が失われることが考えられる．そこでPALS の第二の設計方針として，依存関係にあるデータの同期待ち時間を低減すること を考える．

以下に，考慮すべきオーバヘッドおよび同期待ちについてまとめる．

• オーバヘッド

– 投機するパスの予測時間

– 投機的マルチスレッド実行の全体の制御(スレッドの起動，終了および 破棄)

– 投機失敗時の回復処理

• 同期待ち

– ループイタレーション間において依存関係にある変数の同期時間

3.2.2 投機的並列実行制御にかかるオーバヘッド

2パス限定投機方式では，ループイタレーションを投機スレッドの単位としてい る．このため，PALSでは，ループイタレーションごとにパスの予測を行い，投機 スレッドを起動する必要がある．また，投機失敗が起こった場合，当該スレッド および，当該スレッド以降のすべてのスレッド (後続スレッド) を破棄する必要が ある．

投機失敗となったスレッドにおいては，実行していないもう一方のパス(#1パ スが投機失敗となった場合は#2パス，#2パスが投機失敗となった場合は#1パ ス)を実行するか，2回の投機失敗時においてはオリジナルループコードを実行す ることになり，再度の予測を必要としない．しかし，破棄された後続スレッドに おいては，それまでのパスの実行履歴が変更されることとなるため，予測をやり 直す必要がある．このため，特に予測が困難であるプログラムにおいては，実際 のループイタレーション数に対して，非常に多くの投機スレッドが生成される可 能性が高い．よって，投機スレッドの生成を高速に行うことはシステムの実現に おいて非常に重要である．

投機スレッドの生成の制御方法として，ソフトウェアによる方法とハードウェア による方法が考えられる．ソフトウェアによって投機スレッドの生成を行う場合，

(1) 投機実行開始を指示する命令の実行，(2)実行パス履歴情報の参照，(3) 投機対 象パスの決定，といった処理をプロセッサコア上で行う必要がある．一方，ハード ウェアによって投機スレッドの生成を行う場合，予測を行うためのハードウェア が必要になる．このハードウェア上に実行パス履歴情報を記録するレジスタ等を 実装しておくことにより，投機対象パスの決定を最小クロックで行うことができ る．また，プロセッサコアでは予測に関する処理を行う必要がないため，元々の プログラムコードに予測のための追加命令を挿入することなく，予測を実現する ことができる．このため，PALSでは投機スレッド起動を行うため，ハードウェア パス予測機構を用意する．

ハードウェアパス予測機構の実現方法として，図3.8に示す二通りの実装が考え られる．図中におけるパス予測器はハードウェアパス予測機構を示しており，プ ロセッサはパス予測器から予測結果を受け取り，投機スレッドの実行を開始する．

図3.8 (a) は，各プロセッサコアにハードウェアパス予測機構を実装する分散方式

である．一方，図3.8 (b) は，中央に実装した1つのハードウェアパス予測機構に よって，すべてのプロセッサコアに対する投機スレッドの生成を行う集中方式で ある．プロセッサコアとハードウェアパス予測機構の間で行う通信内容としては，

(1) #1パスと#2パスのどちらを実行するか，(2) 投機実行が成功したか，といっ

た情報のみであるため，大きな通信帯域を必要としない．

2パス限定投機方式では，過去のパスの実行履歴情報をもとに，次の投機スレッ ドのための予測を行う．投機スレッドが割り当てられていないプロセッサコアが

複数存在する場合，出来る限り早く複数の投機スレッドを起動することが並列性 を高めるために重要となる．

分散方式では，各プログラムコアに対してハードウェアパス予測機構を用意す る方式であり，プロセッサコア数倍のハードウェア資源量が必要となる．パス予 測機構においては，履歴レジスタ長を長くすることで予測性能が向上する[9]．し かしながら，履歴レジスタ長を長くすることでパターン履歴テーブルに必要な記 憶資源量は指数関数的に増えるため，分散方式では膨大なハードウェア資源量が 必要となる．また，分散方式では，各プロセッサコアにおけるハードウェアパス 予測機構の間で実行履歴情報の同期を行う必要がある．同期を行わずに予測を行 う場合，通信時間を考慮する必要がないため各プロセッサコアにおけるパス予測 時間を最短にすることができるが，連続したループイタレーションにおけるパス 実行履歴の情報が失われてしまう．同期を行う場合，隣接するプロセッサコアか らの実行履歴情報の受信を行った後，プロセッサコア内に記録した実行履歴情報 の更新を行った上で，はじめて投機対象パスの予測が可能となる．先頭スレッド，

あるいは先頭スレッドに近いスレッドにおいて投機失敗となった場合，多くの後 続スレッドが破棄されることになるため，同期が必要な分散方式では予測に非常 に多くの時間がかかることが予想される．

集中方式では，必要なハードウェア資源量は分散方式に比べて少ない．また，各 プロセッサコアに対して順番に投機スレッドを割り当てる必要があり，また，投 機スレッドの成否判定情報を各プロセッサコアから受け取り，パスの実行履歴情 報を更新する必要がある．PALSでは，投機スレッドの割り当ては静的に決められ た順番で行うため，その順序関係を遵守することにより，集中的に実行履歴を管 理する場合でもその処理が複雑になることはない．一方，集中方式ではパス予測 機構と各プロセッサコア間との物理的な距離が遠くなるため，予測結果の伝達が 分散方式に比べて遅くなる可能性がある．

以上のことから，分散方式は予測結果の通知をプロセッサコアに高速に送るこ とのできるメリットに対して，必要なハードウェア資源量が膨大となるといった 大きな問題がある．そこでPALSでは，投機スレッド起動をはじめとした投機的 並列実行の制御は，集中方式によって実現する．PALSでは，ハードウェアによる パス予測をはじめとしたマルチスレッド制御を集中的に行うハードウェア機構を

実装する[20]．このハードウェア機構を，マルチスレッド制御機構TMU (Thread