JPH03250221A - 分岐予測方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は機械命令を複数のステージに分けて実行するパ
イプライン計算機における分岐処理方式に関し、特に分
岐予測テーブルを数多く持てないｌチップマイクロプロ
セッサの分岐処理の高速化に関する。

〔従来の技術〕

パイプライン計算機においては一つの機械命令を、命令
の読み込み、解読、演算、書き込み等の複数のステージ
に分け、流れ作業的に実行し、処理時間の短縮を図って
いる。そのためパイプライン計算機では、連続する命令
は高速↓こ実行できるが、分岐命令が出現するとパイプ
ラインステージをキャンセルし、命令の読み込みから実
行し直さなければならないため、性能が低下する要因と
なっていた０分岐命令の内、無条件分岐命令については
、分岐することが予め分かつているため、分岐先番地が
計算でき次第命令の読み込みに移れるが、条件分岐命令
については、演算結果によって条件が成立した場合には
分岐の処理を行うが１条件が不成立の場合には、分岐を
行わずに次番地の命令をそのまま実行するため、演算結
果によって条件が決定するまで分岐の処理に移れない。

そのため、条件が成立した場合の性能低下が著しい。

そこで、条件分岐を高速化するため１分岐予測と呼ばれ
る手法が考えられた。分岐予測方式については、アイ・
イー・イー・イー、コンピュータ、（１９８４年１月）
第６頁から第２２頁（ＩＥＥＥ。

ＣＯＭＰＵＴＥＲ，（Ｊａｎ、　１９８４）ｐ　ｐ　６
−２２）において論じられている。

従来の分岐予測方式では、分岐命令番地４分岐先番地９
分岐予測判定ビットの３つのフィールドを持った分岐予
測テーブルを、数十から数百エントリーを持ち、実行中
の分岐命令の番地が、テーブル中の分岐命令番地と一致
した場合、分岐予測判定ビットの状態に従って、分岐す
るか否かを予測し１分岐すると予測された場合には条件
の成立を待たずに、テーブル中の分岐先番地から命令読
み込みを開始するため、予測が成功した場合には分岐に
伴う性能の低下が緩和され、全体として処理性能が向上
する１分岐予測判定ビットは、過去の分岐の成立、不成
立によって決定される。

〔発明が解決しようとする課題〕

上記従来技術では１分岐予測テーブルを数十から数百エ
ントリー持ち１条件分岐命令を出来るだけ多くテーブル
に登録することによって性能を向上させることを前提と
している。そのため、１チツプマイクロプロセツサのよ
うにテーブルのエントリー数を数多くとれない場合には
、あまり性能向上が期待出来ないという問題点があった
。

本発明の目的は１分岐予測テーブルのエントリー数が少
ない場合にも分岐予測の効果を出し、特に１チツプマイ
クロプロセツサにおいて、最適な分岐予測方式を提供す
ることにある。

〔課題を解決するための手段〕

上記目的を達成するためには、分岐予測が最も効果的に
作用する。プログラムのループ部分を構成する条件分岐
命令を優先的に分岐予測テーブルに登録すればよい。そ
のため、分岐先番地が分岐命令番地より後方である場合
をテーブルの登録条件とする。

〔作用〕

プログラムのループ部分では、ループ終了の判定のため
の条件分岐命令がループの最後即ち上位番地側にあり、
条件が成立した場合には後方即ち低位番地側に分岐する
。ループ内に他に条件分岐命令が出現しなければ単純に
条件分岐命令を登録すればよいが、例えばループ内に条
件文（ＩＦ文等）があるとその条件文に対する条件分岐
命令がテーブルに登録されてしまい、ループ終了のため
の条件分岐命令がテーブルに登録されない場合がでてく
る０分岐先番地が分岐命令番地より後方である場合をテ
ーブルの登録条件にすれば、ループ内の条件文に対する
条件分岐命令はテーブルに登録されず、ループ終了のた
めの条件分岐命令が登録される。

〔実施例〕

以下５本発明の実施例を第１図〜第１１図により説明す
る。

第１図は本発明の一実施例の基本的構造を示している０
分岐予測を行うパイプライン計算機は、分岐予測テーブ
ル（ＢＰＴ）１００、分岐予測テーブル登録セレクタ（
ＢＰＳＥＬ）　１０１　、プログラムカウンタ比較器（
ＧＯＭＰ）１０２　、プログラムカウンタインクリメン
タ（ＩＮＣ）１０３．プログラムカウンタ（ＰＣ）１０
４　、命令アドレスセレクタ（ＩＡＳＥＬ）１０５．命
令アドレスレジスタ（ＩＡＲ）１０６　、命令キャッシ
ュ（ＩＣ）１０７、プログラムカウンタ退避レジスタ（
ＰＣ５）１０８．命令コードユニット（ＤＥＣ）２００
．命令実行ユニット（ＥＸＥＣ）３００を主な構成要素
とする。分岐予測テーブル（ＢＰＴ）１００は、分岐命
令アドレス（ＢＩＡ）１００１．分岐先アドレス（ＢＴ
Ａ）１００１　を含む。分岐予測テーブル登録セレクタ
（ＢＰＳＥＬ）　１０１はプログラムカウンタバッファ
（ＰＣＢ）１０１１を含む。命令デコードユニット（Ｄ
ＥＣ）２００は、制御信号（ＣＯＮＴＲＯＬ）　２０１
、ディスプレースメントマイナス信号（ＤＩＳＰＭ）２
０２、条件分岐命令判定信号（ＢＣＣ）２０３を含む。

命令実行ユニット（ＥＸＥＣ）　３００は、算術論理演
算（ＡＬＵ）３０１　、条件コード生成部（ＣＯＮＤ）
３０２を含む。

ＩＡＲ１０６の内容であるアドレスに従ってＩＣ１０７
から読み出された命令は、ＤＥＣ２００で解読され、Ｃ
０ＮＴＲ０Ｌ２０１　ニよりＥＸＥＣ３００を制御し、
ＥＸＥＣ３００は所定の演算を行う、ＰＣ１０４は次に
読みだすべき命令のアドレスを保持しており、　ｌＮＣ
ｌＯ３はＰＣＩ０４の内容を命令の語長に合わせてイン
クリメントする。Ｃ０ＮＰ１０２はＰＣ１０４とＢＩＡ
ｌｏｏＩとを比較し、一致した場合はＢＴＡ１００２の
内容をＩＡＳＥＬ１０５に送る。

ＩＡＳＥＬ１０５はＤＥＣ２００からの信号２０４、Ｅ
ＸＥＣ３００からの信号３０３、Ｃ０ＮＰ１０２からの
信号１０２１に基づき、Ｐ　Ｃ１０４、ＰＣ５１０８，
ＢＴＡ１０２１　、　ＡＬＵ３０１の出力ＡＬＵＯＵＴ
３０５の内の一つを選択し、ＩＡＲ１０６に送る。その
時、　ＢＴＡ１０２１が選択された場合は、ＢＴＡ１０
２１の内容をｌＮＣｌＯ４に送ると共にＰＣ１０３の内
容をＰＣ５１０８に退避する。　ＰＣＢＩＯＩＩはＰＣ
１０４の内容を保持し、　ＢＰＴｌｏｏの更新のタイミ
ングに合わせてＢＰＴｌｏｏにその内容を送る。　ＢＰ
ＳＥＬＬＯＬは、Ｃ０ＮＤ３０２からの条件成立信号３
０４とＤＥＣ２００からのＤＩＳＰＭ２０２及びＢＣＣ
２０３の内容によりＰＣＢＩＯＩＩの内容とＡＬＵ３０
１の出力である分岐先アドレス（ＡＬＵＯＵＴ３０５）
をそれぞれＢＰＴｌｏｏの中のＢＩＡｌｏｏＩとＢＴＡ
１００２に格納する。

第２図は本実施例で述べる計算機の分岐予測を含む基本
動作を表すタイミングチャートである。

ｔｏからｔ８は時系列を表し、一つの時間（タイミング
）が１マシンサイクルに相当する。一つの命令は、ＰＣ
，Ｉ　Ｆ、Ｄ、Ｅ、Ｗに分かれたパイプラインステージ
で実行される。ＰＣステージではＰＣ１０４をインクリ
メントし、次に読み出すべき命令のアドレスを計算する
。尚、本実施例では命令長は４バイト固定とする。ＰＣ
ステージの終了後、即ちＩＦステージと同じタイミング
でＢＩＡｌｏｏＩとＰＣ１０４の比較がＣ０ＮＰ１０２
によって行われる。両者が一致した場合、ＩＡＳＥＬ１
０５はＢＴＡ１０００２の内容をＩＡＲに送り、次から
は予測されたアドレスからの実行が始まる。両者が一致
しない場合には、通常通りインクリメントされたＰＣｌ
、０４が使われる。ＩＦステージではＰＣステージで決
定されたアドレスに従いＩＣ１０７から命令を読み出す
。Ｄステージでは読み出された命令を解読し、ＥＸＥＣ
３００に演算を指示する等、各種制御を行う０本実施例
では分岐予測を行うのは条件分岐命令の分岐先がプログ
ラムカウンタ相対アドレスだけの場合、即ち分岐先アド
レスが静的に決定できる場合に限るので、分岐先が後方
であることを示すディスプレースメントマイナス信号Ｄ
ＮＳＰＭ２０２は命令中のオペランドの特定のビットを
見ればよく、Ｄステージで判定できる。また、条件分岐
命令であるかどうかは命令中のオペコードの特定のビッ
トの組合せで決定できるので条件分岐命令判定信号ＢＣ
Ｃ２０３はＤステージで判定できる。

ＢＣＣ２０３は分岐予測を行う命令の種類を限定するた
めにも使用できる。ＥステージではＤステージで指示さ
れた演算をＥＸＥＣ３００で実行する６Ｗステージでは
Ｅステージの実行によって得られた結果をレジスタ等に
書き戻す。

第２図は、第１命令がコンデイション生成命令、第２命
令が条件分岐命令の場合である。第１命令のアドレスを
ａ−４番地とし、時間１０で計算されたとする。時間ｔ
１では第１命令の読み出しと第２命令のアドレスの計算
が行われる。時間ｔ２では第１命令の解読、第２命令の
読み出しと第３命令のアドレスの計算が行われる。以下
同様に。

分岐等で制御が乱れないかぎり、それぞれの命令はパイ
プラインステージに従って流れていく。尚この場合、第
２命令のアドレス（ａ）はＢＩＡｌｏｏＩと一致しなか
ったとする。

時間ｔ３で演算された第１命令の結果（コンデイション
）が５時間ｔ４で第２命令（条件分岐命令）の条件を満
足した場合は、第２命令で示されたアドレスに分岐する
。分岐先アドレスは時間ｔ４で計算されるので１時間ｔ
５から命令の読み出しを行う。時間ｔ４で分岐が起こる
と分かったとき、第３命令、第４命令は既に読み出され
ているので実行を途中でキャンセルする。時間ｔ５以降
は、再び分岐等が起きないかぎり命令はパイプラインス
テージに従って流れていく、このように、分岐予測が働
かなかった場合、条件分岐命令で条件が成立した場合、
２サイクルの空き時間が生じる。

時間ｔ４で分岐が起こると分かったとき、その分岐先が
自命令より後方である（　ａ　＜　ｂ　）かどうかは第
２命令のＤステージ即ち時間ｔ３で分かつているので、
分岐先が自命令より後方である場合、第２命令のアドレ
ス（ａ）と分岐先アドレス（ｂ）を時間ｔ５でＢＰＴｌ
ｏｏに登録する。即ち、条件成立信号３０４が時間ｔ４
で出力された場合。

ＢＰＳＥＬＩＯＩはその前のタイミング（時間ｔ３）で
出力されたＢＣＣ２０３とＤＩＳＰＭ２０２に従ってＰ
ＣＢＩＯＩＩの内容を時間ｔ５でＢＩＡｌｏｏＩに、Ａ
ＬＵＯＵＴ３０５をＢＴＡ１００２にそれぞれ格納する
。

第３図は、分岐予測が成功した場合を示す。第２図と同
様に第１命令がコンデイション生成命令、第２命令が条
件分岐命令である。時間ｔ２で第２命令のアドレスとＢ
ＩＡｌｏｏＩの内容が一致したとする。この場合、ＩＡ
ＳＥＬ１０５はＢＴＡ１００２の内容を次に読みだすア
ドレスとしてＩＡＲ１０６に送ると共に、その次に読み
出すべきアドレスを計算するためにｌＮＣｌＯ４にも送
る。また、予測が失敗した場合の回復用にＰＣ１０３の
内容（ａ＋４）をＰＣ５１０ｇに退避する。

このようにして時間ｔ３では予測された分岐先アドレス
（ｂ）から読み出しが始まり、時間ｔ４ではアドレスｂ
＋４から読み出しが起こる。時間ｔ４で第２命令の実行
の結果、条件が成立し１分岐が起こることが確認されれ
ば、予測は成功であり、むだな待ち時間無しに条件分岐
が実行されるので計算機の性能が向上する。

第４図は、分岐予測が失敗した場合を示す。第２図と同
様に第１命令がコンデイション生成命令、第２命令が条
件分岐命令である。第３図と同様に時間ｔ２で第２命令
のアドレスとＢＩＡｌｏｏＩの内容が一致したとする。

時間ｔ２では予測されたアドレス（ｂ）から読み呂しが
始まる。時間ｔ３ではアドレスｂ＋４から読み出しが起
こる。時間ｔ４で第２命令の実行の結果１条件が成立せ
ず、アドレスａ＋４の命令を実行すべきことが分かった
場合、ＩＡＳＥＬ１０５はＰＣ１０４の内容（ｂ＋ｓ）
でなく、退避していたＰＣ５１０８の内容（ａ＋４）を
次に読みだすアドレスとしてＩＡＲ１０６に送る。第３
及び第４命令はキャンセルされる。　ＰＣ５１０８の内
容の内容はｌＮＣｌＯ４にも送られる。このように、分
岐予測が失敗した場合５分岐予測が働かなかった場合と
同様に２サイクルの空き時間が生じる。分岐予測が頻繁
に失敗すると、無駄な空き時間が増えるので最悪の場合
計算機の性能が低下するが、一般に分岐予測が行われる
ループ部分は数多く実行され、分岐予測が成功する可能
性の方が高いので分岐予測は平均的に計算機の性能を向
上させる。

第５図は、本実施例におけるＢＰＴｌｏｏ及びＢＰＳＥ
ＬＩＯＩの詳細を表したものである。ＢＰＴ１００内の
ヴアリツドビット（Ｖ）１００３は分岐予測テーブル内
のデータが有効かどうかを表す。Ｖ６Ｏ１３はリセット
時にリセット信号ｌｉ！１００４によってクリアされる
。また、仮想記憶をサポートする計算機で命令アドレス
が論理アドレスである場合、プロセス切り換えによって
もクリアされる。ただし、この場合、ＢＩＡｌｏｏＩが
アドレスの一部としてプロセス番号を保持している場合
はＶ６Ｏ１３をクリアする必要はない。

ＢＰＳＥＬＩＯＩ内のＰＣＢＩＯＩＩはラッチ１０１１
　、１０１２゜１０１３から成る。これらのラッチは１
サイクルごとにデータを送るので、第２図の実施例の場
合。

時間ｔ２でＰＣＢＩＯＩＩに入れられたデータは時間ｔ
５で出力される。ラッチ１０１２，１０１３は、それぞ
れＤＩＳＰＭ２０２．　ＢＣＣ２０３のデータを保持す
る。

第２図の実施例の場合、時間ｔ３でラッチされた信号は
時間ｔ４で条件分岐成立信号３０４とアンドゲート１０
１４によって論理積がとられた分岐予測テーブル登録信
号（ＢＰＴＳ）１．０１７となる。

ＢＰＴＳ１０１７はゲート１０１５．１０１６を開き、
それぞれＰＣＢＩＯＩｌ、　ＡＬＵＯＵＴ３０５の内容
をＢＰＴｌｏｏに送る。

ＢＰＴＳ１０１７はＶ６Ｏ１３のセット信号としても使
用され、分岐予測テーブルを有効にする。

第６図は分岐予測テーブル登録セレクタ（ＢＰＳＥＬ）
の別の実施例である。この実施例は条件分岐命令の分岐
先がプログラムカウンタ相対アドレスだけでないが分岐
先アドレスが静的に決定できる場合、例えば絶対アドレ
ス等で、ディスプレースメントマイナス信号（ＤＩＳＰ
Ｍ）がＤステージでは分からない場合のものである。Ｐ
ＣＢＩＯＩＩの出力とＡＬＵＯＵＴ３０５の内容は減算
器（ＳＯＢ）１０１ｇによって減算され、大小関係が判
定される。

ＡＬＵＯＵＴ３０５の内容の方が小さいと判定された場
合、ディスプレースメントマイナス信号１０１９が出力
される。他の動きは先の実施例と同じである。

第７図は分岐予測テーブル（ＢＰＴ）及びプログラムカ
ウンタ比較器（ＣＯＭＰ）の別の実施例である。この実
施例は分岐予測テーブルが４エントリの場合である。４
エントリのテーブルは分岐命令アドレス（ＰＣＢ）の一
部によって区別される２個ずつの２つのセットに分けら
れる。あるアドレスがどちらのセットに分類されるかは
アドレスの一部を使用してセット判定器（ＳＥＴＩ）４
００によって決定される。１つのセット内のどちらのエ
ントリに登録すべきかは入れ換え優先順位決定器（ＲＥ
ＰＲ）５００によって決定される。ＲＥＰＲ５００は、
１つのセット内のエントリ内の入れ換え優先ビット（Ｒ
Ｐ）によって登録されたのが古い方のエントリを判定し
、そちらのエントリを登録すべき対象として決定すると
共に入れ換え優先ビットを付は換え、それまでの優先順
位を反転する。５ＥＴ１４００及びＲＥＰＲ５００によ
って登録すべきエントリが一つに決まる。

分岐予測テーブルからの読み出しの場合、比較すべきア
ドレス（ｐｃ）に対しセット判定器（ＳＥＴ２）６００
によってセットが選ばれ、１つのセット内の２エントリ
に対し２つの比較器によって同時に比較が行われる。分
岐予測テーブルのエントリ数を増やすことにより、より
多くの命令を登録できるので分岐予測の効果が大きくな
り計算機の性能がより向上する。

第８図は分岐予測テーブル（ＢＰＴ）及びプログラムカ
ウンタ比較器（ＣＯＭＰ’）の第７図とは異なる実施例
である。あるアドレスがどちらのセットに分類されるか
はセット判定器（ＳＥＴ３）７００によって、ディスプ
レースメントマイナス信号（ＤＩＳＰＭ）を使用し分岐
先が前方か後方かで決定される０分岐予測テーブルから
の読み出しの場合は、比較すべきアドレス（ｐｃ）に対
し４つの比較器によって同時に比較が行われる。

第９図から第１１図までは本発明の実施例に対する効果
的な使用法について説明するためのプログラム例及びフ
ローチャートである。第９図のプログラムに対し、第１
０図のような命令展開、即ち条件の判定をループの始め
だけで行い、ループの最後がループの先頭への無条件分
岐となっている展開では、分岐予測が働かないため本発
明の効果が表われない。それに対し、第１１図のような
命令展開、即ち条件の判定をループの始めだけでなく、
ループの最後でも行う形の展開では、分岐予測が働き、
本発明の効果が表われている。従って、本発明を使用す
る計算機システムにおいて。

計算機言語を機械語に翻訳するコンパイラは、第９図の
ようなプログラムに対し、第１０図のような展開でなく
、第１１図のような展開を行えばよい。

〔発明の効果〕

本発明によれば、分岐予測によって条件分岐命令の無駄
な空き時間を減らすことができ、計算機の性能が向上す
る。特に、数少ない分岐予測テーブルでもループを構成
する条件分岐命令を選んでテーブルに登録することがで
き、少ないハードウェアで分岐予測の効果を発揮できる
。

本発明によれば、分岐予測テーブルが１エントリしか無
い場合でも第１２図のようなループを持つプログラムに
対し、第１の条件分岐（１２０１）は分岐予測テーブル
に登録せず第２図の条件分岐（１２０２）だけを分岐予
測テーブルに登録するので、分岐予測の効果が発揮でき
るが、分岐先が後方であるという制限を加えないと、第
１．第２の条件分岐の両方を分岐予測テーブルに登録し
てしまうので分岐予測が失敗し１分岐予測の効果が出な
い。

【図面の簡単な説明】

第１図は本発明の一実施例の構成図、第２図から第４図
までは第１図の実施例による基本的動作のタイムチャー
ト、第５図は第１図の中の要素の詳細図、第６図は第５
図と同じ部分の別の実施例による詳細図、第７図は第１
図の中の要素の別の実施例による詳細図、第８図は第７
図と同じ部分の別の実施例による詳細図、第９図から第
１１図は本発明を効果的に使用するためのコンパイラの
展開方法、第１２図は本発明の効果を示すための説明図
である。 １００・・・分岐予測テーブル、１０１・・・分岐予測
テーブル登録セレクタ、１０２・・・プログラムカウン
タ比較器、１０３・・・プログラムカウンタ、１０５・
・・命令アドレスセレクタ、２００・・・命令デコード
第 図 第 ４ 図 第５図 ０６ 第 図 第 ９ 図 ｗｈｉ　１ｅ（ａ＜ｂ）ｂｅｇｉｎ 処理１ 第 処理１ 第 処理１ ＬＡＢＥＬ２：処理２ 第 ２ 図 図 ／”　ＬＡＢＥＬｌｌこ分岐率／ 図 ／”ａ−ｂの計算＄７

Claims (1)

1. 【特許請求の範囲】 １、一機械命令を複数のステージに分けて実行するパイ
   プライン計算機において、条件分岐命令の機械番地とそ
   の条件分岐命令の分岐先機械番地を対にして保持する一
   組以上の分岐予測テーブルを持ち、分岐命令が出現した
   場合にその機械番地と分岐予測テーブル内の命令機械番
   地を比較し、一致した場合には分岐予測テーブル内の分
   岐先機械番地から命令の読み込みを始めるものであつて
   、条件分岐命令の条件が成立し、尚かつその分岐先が自
   命令より後方である場合に上記分岐予測テーブルの更新
   条件とすることを特徴とする分岐予測方式。 ２、特許請求の範囲第１項において、分岐命令の機械番
   地と分岐予測テーブル内の命令機械番地が一致しなかつ
   た場合に、条件分岐命令に続く命令の処理を分岐先命令
   の処理よりも優先する分岐予測方式。 ３、特許請求の範囲第１項において、分岐命令の機械番
   地と分岐予測テーブル内の命令機械番地が一致しなかつ
   た場合、分岐命令の分岐先が自命令より後方の場合には
   分岐先命令の処理を条件分岐命令に続く命令の処理より
   も優先し、分岐命令の分岐先が自命令より後方でない場
   合には条件分岐命令に続く命令の処理を、分岐先命令の
   処理よりも優先する分岐予測方式。 ４、特許請求の範囲第１項において、分岐命令の機械番
   地と分岐予測テーブル内の命令機械番地が一致しなかつ
   た場合に分岐先命令の処理を、条件分岐命令に続く命令
   の処理よりも優先する分岐予測方式。 ５、特許請求の範囲第１項において、命令中のオペコー
   ドとオペランドの一部の組合せを分岐予測テーブルの更
   新条件に使用する分岐予測方式。 ６、条件分岐命令の機械番地とその条件分岐命令の分岐
   先機械番地を対にして保持する一組の分岐予測テーブル
   を持ち、分岐命令が出現した場合にその機械番地と分岐
   予測テーブル内の命令機械番地を比較し、一致した場合
   には分岐予測テーブル内の分岐先機械番地から命令の読
   み込みを始める計算機において、一つのループを構成す
   るプログラムを実行する場合でループ内に二つ以上の条
   件分岐命令を持ち、その内の二つ以上の条件が成立し分
   岐が起こる場合で、尚かつ分岐先が自命令より後方であ
   る条件分岐命令が一つしか無い場合に、その分岐先が自
   命令より後方である条件分岐命令を分岐予測テーブルに
   登録することを特徴とする分岐予測方式。 ７、特許請求の範囲第１項において、プログラム中のル
   ープ構造に対し、ループ終了条件の判定のために使われ
   る条件分岐命令をループの最後に置く展開を行う分岐予
   測方式。