VLIWプロセッサのためのデュアルパス投機実行手法の性能評価
6
0
0
全文
(2) 2. DB. 1. る後続パスの つのパスに対して，投機実行を 手法は，広域スケジューリング手法の 種 手法では，一方のパスの 命令 であるブースティング手法を動的に行う手法で 行う． 命令の代わりに，他方のパス あり，通常の投機実行手法に比べて効率良くプ に含まれる 命令内の有効な命令を埋め込み， つ ログラムを実行することができる ． の 命令にまとめる．なお，この つのパ の ハードウェアコストを抑えることを重視して 命令を つの 命令にまとめ いる スの 手法は，投機実行の処理を簡略化して 命 いるため， る処理を合成と呼ぶ．この合成された や 手法ほどの性能向上を 令を実行することによって，同時に分岐先パス 望むことはできない．しかし 手法は，プロ と後続パスを投機的に実行する．このように ，命令キュー の 重 グラムカウンタ 手法では，分岐命令後方の つのパスを同時に 化および 命令を合成する機構を実装する 投機実行するため，動的に分岐予測を行う必要 だけで実現することができるため，複雑な分岐 がなく，分岐予測機構を省略することができる． 予測機構を実装する や 手法に比べて. DP. VLIW VLIW VLIW. VLIW. NOP. 1. 2. VLIW. 1. [9]. DP. VLIW. DP. 2. GIFT DB. VLIW. (PC). DP. (IQ) 2. GIFT DB. 本稿では，実行ユニットの構成やパイプライ ハードウェアコストの面において非常に有利で プロセッサに対し あると考えられる． ン段数の異なる様々な 一方，プレデ ィケートと比較した場合，プレ 手法を適用し，その性能を比較すること て 手法の有効性を検証する． 以降 2 デ ィケートはループの先頭方向に戻る分岐命令 によって 手法は では， プロセッサの投機実行手法に関す などには適用できないのに対して， 手法の実 分岐命令の分岐先に関係なく適用することがで る研究について述べる．3 では， 手法は，3.1でも述べるように， 手法を実現する機構を示す．続いて きる．逆に 行例と 連続して現れる分岐命令には適用できないのに 4 では， 手法を プロセッサに適用し， 対して，プレデ ィケートは，そのような分岐命 その有効性について検討する． 令にも適用することが可能である．このことか ら両手法を併用することにより，さらなる性能 2 関連研究 向上を実現できると考えられる．またプレデ ィ 手法と同様に少ないハード ウェ ケートは， これまでに， プロセッサのための投機 アコストで実現できるため，両手法を併用した 実行手法がいくつか提案されている．ここでは， 場合でもハード ウェアコストを抑えることがで プロセッサの投機実行手法に関する研究 きる．なお，プレディケートとの併用に関する ，ダ イナミッ 検討は，本稿では割愛する． として，プレディケートと 手法 につい クブースティング手法 以降， ． て述べる. DP. VLIW. DP VLIW DP DP. DP. DP. DP. VLIW. DP. VLIW. VLIW. [6{9]. (. GIFT DB. ). プレディケートは，コンパイル時に分岐命令 を削減する手法であり，実行する全ての命令に 条件を付加し，異なるパスを つのパスにまと めることによって分岐命令を削減することがで ． きる. 1. [6, 7] GIFT は，プレデ ィケートと通常の投機実行 手法を併用した VLIW プロセッサであり，分岐. 予測が難しい分岐命令にはプレディケートを適 用し，分岐予測が簡単な命令に対しては通常の 投機実行手法を適用している．これにより，単 純な分岐予測機構でも高い予測成功率を得るこ とができる ．. [8]. 3 デュアルパス投機実行手法. デュアルパス投機実行手法の実行例. 3.1. DP VLIW. DP 1 (a) 1 (b) VLIW 4. まず 手法の実行例を示す． 手法を適用 プロセッサ上で，図 に示すサ した に示す． ンプルコードを実行した様子を図 命令で つの命 なお実行例では， つの 令を指定でき，分岐命令の分岐先が確定するま でに サイクルを要するものとしている．また， つの 命令には，分岐命令は つまでし か指定できないとしている．さらに，コンパイ. 1. 1. −98−. 3. VLIW. 1.
(3) (a) Sample Code 図. (b) Proposed Method. 1: デュアルパス投機実行の実行例 1. ). ( 1. ). ル時に静的分岐予測を行い，後続パスに分岐命 では， サイクルのペナルティ ．分岐命令の分 令の予測先が偏るようにスケジューリングされ 岐先が確定した後は，プログラムの実行結果に 矛盾が生じるのを防ぐために，分岐しなかった ているものとする． パス 図 の例では，後続パス の実行結果を無 効化する．また，投機実行中に新たな分岐命令 が現れた場合には，現在実行中の分岐命令の分 命令を挿入し，分岐 岐先が確定するまで 先が確定した後に投機実行を行う．. NOP. 3.2. デュアルパス投機実行機構. DP. ここでは， 手法を実現するための機構に ついて述べる．図 に示すように，デュアルパ ス投機実行機構は命令フェッチユニット 図 手法を適用した の構成 内に実装する．デュアルパス投機実行機構の各 ユニットは以下に示す 1. 5. の処理を行うこと 手法を実現する． に示すように 手法では，後続パス によって，3.1 で示した 図 命令を合成し，後続パス 1. 分岐命令の検出 と分岐先パスの 命令の と分岐先パスを同時に実行する． は，フェッチし 分岐命令検出ユニット 合成の際には，コンパイル時の静的分岐予測の 命令を常に監視し，分岐命令の検 てきた 命令 結果を利用するために，後続パスの 出を行う． が優先的に実行されるように合成する．そのた 命令が実行されるのは， 2. 後続パスと分岐先パスのフェッチ め，分岐先パスの. 2: DP. 1 (b). IFU. VLIW. 2. (IFU). . DP. DP. VLIW. VLIW. VLIW. VLIW 後続パスの VLIW 命令内に NOP 命令が含まれ ている場合に限られる．なお DP 手法において. (BAU). VLIW. 投機実行中に後続パスと分岐先パスの 命令をフェッチするために，プログラムカウン と命令キュー をそれぞれ 重化 ミスペナルティが発生するのは，分岐命令の分 タ 岐先が分岐先パスに確定し，かつ，分岐先パス する．なお投機実行を行っていない時は， 組 と のみが使用される． の実行が遅れた場合のみに限られる 図 の例 の. ( 1. (PC). PC IQ. −99−. (IQ). 2. 1.
(4) 分岐先アドレスの計算. 1. 4 VLIW. 処理ユニットを つ，合計 つの実行ユニット 命令で， は，分岐 を実装するモデル． つの 分岐先アドレス計算ユニット と分岐命令フィール 系の命令を つ，ロード・ストア命令，分岐命 命令の有無に関わらず， ドの即値から分岐先アドレスの計算を行う．ま 令をそれぞれ つずつ指定することができる． は，分岐命令が検出された場合にのみ， た プロセッサ に， とロー プロセッサ C に分岐先 その時点で使用されていない方の ド ・ストアユニットをそれぞれ つずつ追加し アドレスを格納する．これにより，分岐命令を 命令で指定できる命令はプロ たモデル． 検出した次のサイクルから分岐先パスの セッサ と同じ． 命令をフェッチすることができる． 評価はソフトウェアシミュレーションによって 4. VLIW 命令の合成 手法を適用した場合と 行い，各プロセッサに は，投機実行中に 命令合成ユニット 適用しない場合の 命令の合成を行 後続パスと分岐先パスの を比較した．評価には， ベンチマーク 命令 う．なお合成の際に，分岐先パスの を用いた．各ベンチマークプログラムは は分岐先パス を合成しきれなかった場合， の を用いてコンパイルし，その結果 命令を保持している に対して，残 の をリストスケジューリングによって，各プロセッ りの命令を保持するように制御信号を出力する． サの実行ユニットの構成に合わせてスケジュー リングしたものを使用した． 5. 分岐先確定後の無効化処理 3.. PC. (BAU). BAU. 2. PC. VLIW. (IMU) VLIW. VLIW. IMU IQ. VLIW. 1. 1. B. VLIW. B. 1. ALU. ALU. DP IPC (Instruction Per Cycle) SPEC95 GNU. GCC 2.6.3. (CU). は，分岐命令の分岐先 無効化ユニット が確定した後に，分岐しなかった方のパスを保 と ，実行結果を保持している 持している パイプラインレジスタの初期化を行う．. IQ PC. 4. 性能評価. ここではまず，評価に用いたプロセッサモデ ルと評価方法について説明する．今回，評価の ために つのプロセッサモデルを用意した．各 TMをベースに 社の プロセッサは， しており，パイプライン段数を 段とした．ま 命令に最大 つの の た， つの 命令を指定できるものとした．以下に，各プロ セッサの実行ユニットの構成を示す．. 3. 1. MIPS. VLIW. R3000 5 4. 3. IPC. R3000. DP. 図 に各プロセッサの を示す．なお， 手法を適用していない場合は，分岐命令を遅延 分岐によって処理しており，各プロセッサとも サイクルの遅延スロットを挿入した．また， 手法の投機実行サイクル数も サイクルとした．. 1. 3. プロセッサモデルと評価方法. 4.1. 評価結果. 4.2. 1 DP. IPC. に 図 より，遅延分岐を適用した場合の 手法を適用した場合の が約 比べて ほど高いことがわかる． 手法を適用 ，プ した場合，プロセッサ と は平均 ほど が向上してい ロセッサ は平均 る．これは，プロセッサ は実行ユニットの数 命令が合成し が少なく，投機実行の際に きれず，多くのペナルティが発生したためだと 考えられる．. 30%. DP. IPC 11 DP A C 18% 10% IPC B VLIW. B. DP. R3000. 手法では投機 また 3.1でも述べたように， 実行ユニットとして の プロセッサ A 実行中に分岐命令が現れた場合には，分岐が確 コアを つ実装し， 命令内に指定で を挿入しなければならず，投 定するまで きる命令の組み合わせに制限がないモデル．た 機実行を行うことができない．また，ジャンプ 手法を適用するために， つの だし， 手法を適用できない命令も存 命令のように 命令には分岐命令は つまでしか指定できない． 手 在する．図 に，各プログラムにおける 実行ユニットとして を 法を適用可能な分岐命令の割合を示す．図 プロセッサ B つ，ロード・ストアユニットを つ，分岐命令 より， 手法の効果が大きい gcc, m88ksim,. CPU. 4. DP. VLIW. 1. 1. 1. NOP. VLIW. ALU 2. −100−. 4. DP. DP. DP 3,4.
(5) 3:. IPC 5 ). (. 図. (. 4: DP 手法を適用可能な分岐命令の割合 (パイプライン段数 5 段) DP DP. 5:. IPC 6 ). 6:. IPC 7 ). 図 各プロセッサの パイプライン段数 段. 図 各プロセッサの パイプライン段数 段. 図 各プロセッサの パイプライン段数 段. (. 7. 2. 3 7. では， 手法を適用できる分岐命令の サイクル，段数 段では サイクルとした．こ 割合が多く， 手法の効果が小さい compress の他，パイプライン段数を 段とした場合の や ijpeg, li では， 手法を適用できる分岐命 手法を適用可能な分岐命令の割合を図 に示す． 令の割合が少ないことがわかる． からもわかるように，パイプライン段 図 が低下していること 数が増えるに従って， 4.3 パイプライン段数の影響 がわかる．段数が 段の場合と比較して，段数 段では平均して ，段数 段では平均し ここでは，パイプライン段数が 手法に及 ， が低下している．また図 より， ぼす影響について検討する．通常，パイプライ て 手法を適用できる分岐命令の割合も大幅に ン段数が多い場合，投機実行に要するサイクル 低下していることがわかる．この理由は，投機 数も多いと考えられる．そこで，前に示した各 プロセッサのパイプライン段数を増加した場合 実行のサイクル数が増えたことによって，ペナ を比較した．図 はそれぞれ，各プ ルティの発生する割合やペナルティサイクル数 の ロセッサのパイプライン段数を 段と 段に増 が増えたためだとと考えられる． vortex. DP. 5,6. IPC. 5,6. IPC. 6. 25% IPC DP. 7. 7. IPC. 6. DP. DP. DP. 5 15 %. 7. 7. を示している．なお，投機実 手法を適用した場合のペナルティ やした場合の 続いて， 行のサイクル数と挿入する遅延スロットの数は， 削減率を求めた．各プロセッサのペナルティ削 パイプライン段数の増加に伴い，段数 段では 減率を図 に示す．なお，ペナルティ削減率と. 6. 8. −101−.
(6) ソフトウェアシミュレーションによる評価では， 手法を適用することによってプロセッサの を最大で約 ，実行ユニットの数が少 プロセッサでも約 向上できる ない ことを示した． 手法を適用できない分 今後の課題として， 岐命令が多いプログラムでも高い性能向上を実 現するために，プレディケートなど他の投機実 手法の併用を検討する予定である． 行手法と 手法の効果を向上させるために， 手 また 法に適したスケジューリング方法についても検 討する予定である．. DP IPC. VLIW. 18%. 11%. DP. 図. DP. 7: DP 手法を適用可能な分岐命令の割合 (パイプライン段数 7 段). DP. DP. 参考文献 [1] 中澤喜三郎，\計算機アーキテクチャと構成方 式，" 朝倉書店, 1995. [2] 富田眞治，\第 2 版 コンピュータアーキテク チャ， " 丸善, 2000. [3] 片山清和，安藤秀樹，島田俊夫，\両パス実行 の性能評価と実行判定精度の改善，" 情報処 理，Vol. 42, No. 8, pp. 106{118, 2001. [4] Pritpal S. Ahuja, Kevin Skadron, Margaret Martonosi and Douglas W. Clark,\Multipath Execution : Opportunities and Limits,"Proc. the 1998 International Conference on Supercomputing, pp. 101{108, 1998.. パイプライン段数. 図. 8: ペナルティ削減率. DP. 手法を適用した場合，遅延分岐のみを は， 適用した場合に発生するペナルティをどれだけ 削減できたかを示している．図 に示すように， プロセッサ のペナルティ削減率が最も低く， プロセッサ と はほぼ同じ値となっているこ とがわかる．またプロセッサ と は，パイプ ライン段数の増加に伴ってペナルティ削減率が 低下していることもわかる．. 8. B A C. A C. 5 むすび 今回，デュアルパス投機実行手法を，実行ユ ニットの構成やパイプライン段数が異なる つ プロセッサに適用し，その性能比較を の 手法の有効性を検証した． 行うことによって. VLIW. 3. DP. [5] 島尻寛之，吉田たけお，\VLIW プロセッサ のための複数パス投機実行機構，" 信学技報， CPSY2000-40. [6] 安藤秀樹，中西知嘉子，原哲也，中屋雅夫，\プ レディケーティング：VLIW マシンにおける投 機的実行のためのアーキテクチャ上の支援，" 情報処理，Vol. 37, No. 11, pp. 2039{2055, 1996. [7] 小沢年弘，新井正樹，細井聡，木村康則，\分 岐予測と条件付実行" 計算機アーキテクチャ研 究会報告，ARC-134-19, pp. 109{114, 1999. [8] 古関聰，小松秀昭，深澤良彰，\拡張 VLIW プ ロセッサ GIFT におけるブランチハンド リン グ機構．" 情報処理，Vol. 38, No. 12, pp. 2576{2587, 1997. [9] 阿部孝之，仲池卓也，小林広明，中村維男， \VLIW アーキテ クチャのためのダ イナ ミ ックブ ースティング 機構，" 信学論 (D-I)， Vol. J83-D-I, No. 1, pp. 171{183, 2000.. −102−.
(7)
図
関連したドキュメント
“We’d like not just text or diagram, but both!”.
The fusion method proposed in this paper comprises a fusion transformation called alge- braic fusion and a strategy called improvement which is useful for refining and reasoning
In this paper according to these studies we will prove Kakutani’s fixed point theorem in an n-dimensional simplex for multi-functions which have uniformly closed graph and
In this paper, we have proposed a modified Tikhonov regularization method to identify an unknown source term and unknown initial condition in a class of inverse boundary value
We formalize and extend this remark in Theorem 7.4 below which shows that the spectral flow of the odd signature operator coupled to a path of flat connections on a manifold
In this paper, we study the chains of paths from a given arbitrary (binary) path P to the maximum path having only small intervals.. More precisely, we obtain and use several
The reason for not using the perhaps more familiar high peak statistics in the definition of the main production matrix is that the joint distribution of number of high peaks and
はじめに
