JPH03102523A - 情報処理装置における分岐制御方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 パイプライン制御の情報処理装置における任意の時点で
実行可能な分岐制御命令ＩＢの分岐制御方弐に関し 分岐命令によるパイプラインの乱れの発生を解消するこ
とを目的とし 分岐元アドレスと分岐先アドレスの両方をオペランドと
して．分岐先アドレスに先行する任意の時点で実行でき
る分岐制御命令ＩＢを設け，さらに命令フエツチ機構部
で早期にその分岐を実現し切れ目なく命令フェッチを行
うことにより，分岐命令によるパイプラインの乱れを解
消するように構威した。

〔産業上の利用分野〕

本発明は，パイプライン制御の情報処理装置における任
意の時点で実行可能な分岐制御命令Ｉ　Ｂ〔従来技術〕 パイプライン制御では．理想的な制御が行われる場合，
第８図の様な手順で毎ザイクルに命令を連続実行可能と
なるが５実際には （１）分岐命令による処理径路の変化 （２）レジスタ衝突による待ち合わせ （３）各ステージの処理時間の相違乙こよる同期の乱れ （４）ストア命令による先行命令の書換え（５）割込み などの要因によりパイプラインに第９図に例示されるよ
うな乱れが生しるため．このような理想状態を常に保つ
ことは不可能となる。そのため従来このようなバイブラ
イン制御を採用する計算機システムでは，上記要因のそ
れぞれ↓こ対して，各ステージの実行が空にならないよ
うに１多様な努力が払われてきた。

特に，（１）の分岐命令に関しては，第９図に示すよう
に分岐先（ターゲット）の命令をフェッヂするための処
理でバイブラインの乱れが大きくなり更に分岐命令の頻
度が非常に大きいことも相俟って５バイブライン方式上
重要な解決課題となっている。

従来，この間瑚に対ずる制御方式として，前回の分岐成
功時に分岐先アドレスを記録した履歴テーブルを用いて
，同一のケースについて行う先行フェッチや，条件分岐
命令の場合に条件確定までに時間がかかるためその間に
他の命令のフローを挿入して効率化する遅延分岐（Ｄｅ
ｌａｙｅｄ　Ｂｒａｎｃｈ）といった種々の方式が提案
されている。

しかしながら，履歴テーブルを用いる方式では二度目の
実行にしか効果が無い上．ある程度大きなテーブルが必
要であるためテーブル管理が複雑になり，また遅延分岐
では条件分岐命令の対の命令を開始する前に割り込みが
入ると複雑な制御が必要となるうえ．完全にはパイプラ
インの乱れを吸収することはできない。これ以外の方式
も，機構目体が大規模であったり．制御が複雑になる等
実現−１二問題とｔζる部分が多かった。

（発明が解決しようとする課題〕 本発明は，分岐命令によるパイプラインの乱れの発生を
解消することを目的としている。

（課題を解決するための手段〕 本発明は．分岐元アドレスと分岐先アドレスの両方をオ
ベラン１−として．分峡先アドレスに先行する任意の時
点で実行できる分岐制御命令ＩＢを設け．さらに命令フ
エツチ機福部で早１り］にその分岐を実現し，切れ目な
く命令フェノチを行うことにより，分岐命令によるパイ
プラインの乱れを解消するものである。

本発明による分岐制御命令ＩＢの形式を次に示す。

ｒｌＢｉ　　　ＶＡｃｌｒｓＡｉ，ＶＡｄｒｓＢｉ，１
ここで，Ｉ｝３は命令名，ｊは同時丈行される１　１３
を識別する番号，ＶＡｄｒｓＡｉは分岐元となるアドレ
ス，ＶＡｄｒｓＢｉは分岐先となるアドレスを表す。

第１図は，本発明の原理構或図であり，本発明による命
令フエツチ機構部の機能を示している。

図中 １は命令フェッチス１・リームであり，命令フエッチで
のキャソシュミス時に主記憶からロードするタイミング
をとるためにＦｉＦｏスタンクで構威される。この命令
フェッチストリーム１では空にならないよう常に先行的
な命令フェノチが行われる。

２は，命令実行パイプラインであり，第８図に例示され
るような，Ｄ（デコード），Ａ（アドレス生或）１　Ｔ
（アトレス変換），Ｂ（ハッファアクセス），Ｅ（実行
），Ｗ（結果の書き込み）のステージで構威される。

３は　ＩＢＲＩないしＩＢＲｎからなるレジスタＩＢＲ
ｉであり，有効な分岐制御命令）Ｂｉの分岐元アトレス
ＶＡｄｒｓＡｉおよび分岐先アドレスＶＡｄｒｓＢｉを
対にして登録可能にする。

ＴＢＲの番号ｉは，別にオペランドの１つとして指定さ
れ．１≦ｊ≦ｎ（ｎは命令フェソチに必要なτ数）の値
をとる。

ＩＢ命令が命令フェッチストリーム１から命令実行パイ
プライン２に投入されると．その実行結果としてＶＡｄ
ｒｓＡｉどＶＡｄｒｓＢｉのレジスタＩＢＲｉへの登録
が行われる。この後，命令フェンチ機構部は ■　各レジスタＩＢＲｉの分岐元ア１・レスＶ　Ａ　（
ｌ　ｒ　ｓ　Ａ　ｉとフェノチされる命令のアドレスと
を比較し ■　一敗すれば幻の分岐先ア１・レスＶＡｄｒｓＢｉの
命令をフェッチし ■　ＶＡｄｒｓＡｉの命令の後続命令としてリンクし．
命令実行パイプライン２に投入させる。

〔作　用〕

第１図に示されている命令フェッチ機構部の機能をさら
に詳しく説明する。

今，命令フェッチス１・リーム１に，アトレスＶＡｄｒ
ｓＡｉ　（１≦１≦ｎ　）の命令が存在ずる場合，命令
フェッチ機構部は．アドレスＶＡｄｒｓＡｉの後続の命
令アトレスとしてアドレスＶＡｄｒｓＢｉが続くものと
判断してアドレスＶＡｄ　ｒ　ｓ　Ｂ　ｉをストリーム
にリンクする。

命令実行パイプライン２には．アドレスＶＡｄｒｓＡｉ
に始まる命令を投入後．続いてアドレスＶＡｄｒｓＢｉ
に始まる命令を投入し，以下この後続の命令の投入を続
ける。尚，命令ＩＢによって設定されたＩＢＲｉの内容
がどの時点から有効となるかについては，たとえば．命
令ＩＢの直後の命令から新ＩＢＲｉ　（ＩＢＲｉの更新
後の内容）が有効になるものとした場合，後続の命令が
旧ＩＢＲｉ　　（ＩＢＲｉの更新前の内容）の影響をう
けないことを保証するために．各命令（命令フェッチス
トリームおよびパイプライン内）には，旧ＩＢＲｉのリ
ンクの対象となったかどうかを示すタグを付加するよう
にし，命令ＩＢで新ＩＢＲｉが確定ずる迄に．その直後
の１命令を除く後続の全命令のタグを調べて，旧ＩＢＲ
ｉのリンクの対象となった命令が存在する場合には新Ｉ
ＢＲｉが確定した時点でその命令以降をキャンセル（無
効化）シ，旧ＩＢＲｉのＶＡｄｒｓＡｉの命令の後続の
命令に再リンクし．しかる後に新＋ＢＲｉをＩＢＲｉに
格納する必要がある。

さて．一般に命令フエツチにｎτ必要であるとすると．
従来の分岐制御の場合には，第９図に例示されているよ
うに分岐命令０１３　（ＯｒｄｉｎａｒｙＢｒａｎｃｈ
）がバイブラインに投入されてから分岐アドレスが生或
され．しかる後にターゲッｌ・がフェッチされ命令フエ
ツチ機構部に送られるため，少なくともｎτの時間ロス
が生じてしまう。本発明方弐の場合．命令ＩＢによるア
ドレスＶＡｄ　ｒ　ｓＡｉとアドレスＶＡｄｒｓＢｉの
生或および■ＢＲｉへの登録が．アドレスＶＡｄｒｓＡ
ｉの命令実行終了のｎτ前までに終了していれば２アド
レスＶＡｄｒｓＡｉの後続の命令としてアドレスＶＡｄ
ｒｓＢｉ以降の命令を，ペナルティＯでバイブラインに
投入することが可能となる。

ここで，プログラムを記述する立場で分岐命令を考えて
みると．分岐先アドレスはプログラム中で固定される場
合が多く．大抵の場合には分岐命令のかなり以前には（
分岐元アドレスと）分岐先アドレスをｈ１定できる。従
ってプログラムを記述する際には，　（分岐元アドレス
と）分岐先アドレスの決定を前送りにすることが多くの
場合可能であり．命令ＩＢが分岐命令のｎ命令（≧ｎτ
）以前に配置されれば．分１岐命令によるペナルティを
無＜シ，パイプラインの乱れを完全に吸収することが可
能となる。

実際には１　ｎ命令以前に命令ＩＢを配置することがで
きても，そのｎ命令内に別の分岐が存在する場合もあり
．この場合ＩＢＲの衝突を防くためにＩＢＲは複数七ソ
１・必要となる。しかしながら，高々ｎ　−ｔ−　１個
のＩ　Ｂ　Ｒで必要かつ１分であり，巨大なＩＢＲセッ
トを構築する必要はない。

第２図に，本発明による分岐制御命令ＩＢを適用したプ
ログラムを，従来の分岐命令の場合と対比させて示す。

（１）は，通常の分岐命令がｎ命令以上離れて配置され
ていた場合と，それを本発明方式の命令ＩＢに置き換え
た場合のものである。命令ＩＢは１セット（ｉ＝１）Ｌ
か使用していない。各分岐時点でのロスが○となる為，
（従来の分岐ロスｎτ）×（分岐の数）だｂノの処理の
高速化が計られる。

（２）は，通常の分岐命令が接近して（＜ｎ命令）配置
されていた場合と，それを本発明方式の命令ＩＢに置き
換えた場合のものである。命令ＩＢは２セット（ｉ＝１
．２）使用している。（１）同様（従来の分岐ロスｎτ
）×（分岐の数）だけの処理の高速化が計られる。

（３）は，ループの制御に使用した場合である。

Ｌ　ａ　ｂ　ｅ　１．　Ｂの実行後．［】スクイムＯで
１．　ａ　ｂ　ｅ　Ｉ　Ａからの実行が操り返される。

この場合ループバックのための分岐命令が完全に不必要
となる為．（従来の分岐ロスｎτ＋ループハック用の分
岐命令■τ）×（ループの回数）だけの処理の高速化が
計られる。

（４）は，多重ループの場合である。各ループのループ
ハックの起こるｎτ以前に命令ＩＢを配置することによ
り．命令ＩＢを１セットのみで，多重ループの場合でも
適用可能である。この場合（従来のロスＤτ）×（■各
ループの回数）だけの処理の高速化が計られる。

以上の場合はいずれも，従来の命令群を命令ＩＢを使用
する命令群に置換可能なケースでありさらに命令の数の
変更がなく機械的な処理が可能である。また，一般的に
プログラムの記述は高級言語でなされる場合がほとんど
であるため，命令ＩＢを効率よく使用するコンパイラを
作或すれば，従来のプログラムもコンパイルしなおすこ
とにより高速化を計ることが容易に可能となる。

以」二の様に．本発明方式による命令ＩＢを，従来の分
岐命令に置き換えて使用することにより，分岐命令によ
るバイブラインの乱れを解消することが可能となる。ま
た，分岐元・分岐先のアドレスを保持するレジスタＩＢ
Ｒｉは．高々ｎヶ用意するだけでよく本発明方式を実現
するための機構は容易に実現できる。

〔実施例］ 第３図ないし第７図により本発明の命令フェッチ機構部
の１実施例を説明する。

第３図は．分岐元アドレスＶＡｄｒｓＡｉの検出部であ
り，フエッチされた命令ｆｅｔｃｈ−　Ｄ　Ａ　Ｔ　Ａ
とフェッチアドレスｆｅｔｃｈ−Ａｄｒｓとが命令ス１
・リームと命令実行パイプラインへ流されるとき，最初
の５つのステージで，■△ｄｒｓＡｉと一致をとられる
。

ＶＡｄｒｓＡｉば，ＩＢ命令の実行により取り出された
直後の分岐元アドレスで，ＩＢＲｉへの登録を行う前に
取り出されたもの，ＶＡｄｒｓＡＶＡ．ｄ　ｒ　ｓＡ．
，ＶＡｄ　ｒ　ｓＡ３ぱそれぞれｌ　ＢＲ，，Ｉ　ＢＲ
２，ｌ　ＢＲ．の各レジスタから読み出された分岐元ア
ドレスである。

またＭ　ｃ．　ｈ　Ｘ　Ｏ　，　Ｍ　ｃ　ｈ　Ｘ　１　
．　Ｍ　ｃ　ｈ　Ｘ　２ＭｃｈＸＤ　　ＭｃｈＸＡば　
それぞれＶＡｄ　ｒ　ｓＡχと命令フェッチストリーム
およびパイプラインの前の複数のステージでのｆｅｔｃ
ｈ−Ａｄｒｓとの比較結果である。そしてＭｃ　ｈＡ．
，Ｍｃ　］ｌＡ２ＭｃｈＡ３は，それぞれ命令フエンチ
ストリームの最初のステージのｆｅｔｃｈ−Ａｄｒｓと
の比較結果であり，ＶＡｄｒｓＮＩＡはｆｅｔｃｈ−＾
ｄｒｓに命令量の４Ｂｙｔｅを力ｌ算した結果の次命令
アドレスである。

第４図の（ａ）は．タグ部であり，命令フェンチストリ
ームとパイプライン中で旧ＩＢＲｉにリンクした命令を
検出するため，命令フェッチを行ったＩ　．Ｂ　Ｒの番
号ｆｅｔｃｈ−　Ｉ　Ｂ　Ｒ　ｌ＃のタグを付加し実行
中のＩＢ命令の番号ＶＡｄｒｓ＃とを最初の５つのステ
ージで比較して，結果をＭｃ　ｈ＃０，Ｍｃｈ＃Ｉ　　
Ｍｃｈ＃２　　Ｍｃｈ＃Ｄ　　Ｍｃｈ＃Ａとして出力す
る。

第４図の（ｂ）は，＋ＢＲ登録部で，パイプラインのＴ
ステージでＩＢ命令ＩＢｉのオペランドＶＡｄｒｓＡｉ
とＶＡｄｒｓＢｉとを，ＩＢの番号ＶＡｄｒｓ＃（ｉ）
によりレジスクＩＢＲｉに登録する。

第５図は．命令フェンヂ要求部であり．第３図でＩＢ命
令の分岐元アドレスＶＡｄｒｓＡｉ　　（ｉ一Ｘ，１，
２．３）と一致する命令のフェッチアドレスｆｅｔｃｈ
　Ａｄｒｓが検出されたとき，ＩＢＲに基づいて対応す
る分岐先の命令フェッチ要求アドレスｌ−ｆｅｔｃｈ−
Ｒｃｑ−八ｄｒｓと命令フェッチＩＢＲ番号１　−ｆｅ
ｔｃｈ−　Ｉ　Ｂ　Ｒ　＃とを発生ずる。

第６図は，命令フェッチ処理を示す。命令フェッチ機構
部（第５図）から出力されたＩ　−ｆｅｔｃｈＲｅｑ−
八ｄｒｓとｌ　−ｆｅｔｃｈ　−　Ｉ　Ｂ　Ｒ＃とは，
命令キャッシュ機構部に送られ　ここでギャッシュξス
が発生すれば３主記憶から取りこんで，結果をｆｅｔｃ
ｈ　−ＤＡＴＡと　ｆｅｔｃｈ−Ａｄｒｓと　ｆｅｔｃ
ｈＩＢＲ＃とで命令フェッチ機構部へ返す。

第７図はキャンセル制１卸部であり，第３図と第４図（
ａ）から得られる信号ＭｃｈＸＡ，ＭｃｈＸｉ　　Ｍｃ
ｈＸ２　　ＭｃｈＸＤ　　ＭｃｈＸＡとＭ　ｃ　ｈ　ｆ
ｔ　Ｏ　　Ｍ　ｃ　ｈ　＃　Ｉ　　Ｍ　ｃ　ｈ　＃　２
　　Ｍ　ｃ　ｈ　ｔｔＤ，Ｍｃｈ＃Ａとを用いて１　旧
ＩＢＲｉのリンク対象となった命令以降をキャンセルす
るよう新ＩＢ命令の実行結果に基づく新ＩＢＲｉの確定
前に．ハリッド信号ｆｅｔｃｈ−Ｖａｌのリリースｔｅ
ｌ／ｔｅｌを各ステージで制御する。

［発明の効果］ 本発明による分岐制御命令と命令フエツチ機構部とを用
いることにより，分岐によるバイブラインの乱れを解消
することができ．処理の高速化と効率化とを図ることが
できる。

【図面の簡単な説明】

第１図は本発明の原理構成図，第２図は本発明を適用し
たプログラムを従来例と対比させて示す作用説明図，第
３図ないし第７図はそれぞれ本発明による命令フエンチ
機構部の１実施例の構或を示し，第３図は分岐元アドレ
ス検出部の構或図第４図（ａ）はタグ部の構戊図．第４
図（ｂ）はＩＢＲ登録部の構成図．第５図は命令フェッ
チ要求部の構或図．第６図は命令フェッチ処理の説明図
，第７図はキャンセル制御部の構威図，第８図は理想的
なパイプライン制御の例の説明図，第９図はバイブライ
ンの乱れの例の説明図である。 第１図中 ■，命令フェッチス１・リーム ２：命令実行パイプライン ３：レジスタＩＢＲｉ

Claims (2)

【特許請求の範囲】
1. （１）命令の実行をパイプライン制御方式で処理し、該
   パイプライン機構部に定常的に命令を投入するための命
   令フェッチストリームを有する命令フェッチ機構部を有
   した情報処理装置において、仮想アドレスＶＡｄｒｓＡ
   ｉとＶＡｄｒｓＢｉおよび整数ｉをオペランドにとる分
   岐制御命令ＩＢと、仮想アドレスＶＡｄｒｓＡｉとＶＡ
   ｄｒｓＢｉを対にして保持し得るレジスタＩＢＲｉと、 分岐制御命令ＩＢの実行により仮想アドレスＶＡｄｒｓ
   ＡｉとＶＡｄｒｓＢｉをレジスタＩＢＲｉに格納する手
   段と、 前記命令フェッチ機構部で、仮想アドレスＶＡｄｒｓＡ
   ｉの命令が命令フェッチストリームに読み込まれたこと
   を契機に、仮想アドレスＶＡｄｒｓＡｉの命令の後続ア
   ドレスとして仮想アドレスＶＡｄｒｓＢｉをリンクし、
   以降を仮想アドレスＶＡｄｒｓＢｉから読み込む様にス
   トリームを変更する手段とをそなえたことを特徴とする
   情報処理装置における分岐制御方式。
2. （２）請求項（１）において、命令フェッチストリーム
   およびパイプラインにある全ての命令にタグＴを付加し
   、該タグＴは当該命令が仮想アドレスＶＡｄｒｓＢｉに
   あり、かつレジスタＩＢＲｉによるリンクを経由したも
   のかどうかを示し、分岐制御命令ＩＢで新ＩＢＲｉが確
   定するまでにその後続の命令のタグを調べ、旧ＩＢＲｉ
   によるリンクの対象となった命令が存在する場合には、
   新ＩＢＲｉが確定した時点で該命令以降のストリームお
   よびパイプラインをキャンセルすると共に、レジスタＩ
   ＢＲｉの仮想アドレスＶＡｄｒｓＡｉの命令の後続の命
   令をリンクし、その後に新ＩＢＲｉをＩＢＲｉに格納す
   ることを特徴とする情報処理装置における分岐制御方式
   。