JPH0363726A - 階層型分岐ヒストリテーブル - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本特許は１分岐命令の高速処理に関し、特に分岐ヒスト
リテーブルを用いた分岐命令の高速処理に関する。

［従来の技術］ 分岐命令の高速化は、ノイマン型コンピュータにおける
重要な問題であり、その解決として、過去の分岐命令の
アドレスと分岐先アドレスを対にして記憶する分岐ヒス
トリテーブル（特公昭５０−２２３８４号）や、過去の
分岐命令のアドレスとその分岐したかどうかの結果を記
憶する分岐デコードテーブル（米国特許４，４７７．８
７２号）がある。

［発明が解決しようとする課題］ 上述した従来の分岐高速化技術のうち１分岐ヒストリテ
ーブルは１分岐命令類度が２５％程度というふうに異常
に多いため、どうしても多数の分岐命令について記憶し
なければならず、そのためどうしても容量が大きいメモ
リで構成することが多い。

しかしながら、今日の論理回路の著しい高速化に対して
、メモリはそれほど高速されていない。

そのため高速コンピュータの設計では、マシンサイクル
を小さく設定する必要があるため、メモリアクセスタイ
ムの遅さがネックとなってしまう。

このため分岐ヒストリテーブルの索引が遅れて分岐命令
の性能がでないという問題が発生する。特にループ用の
分岐命令のように、必ず複数回その分岐命令を実行する
場合には、そのループの性能を上げるために極力早目に
分岐ヒストリテーブルを索引する必要がある。

したがって１本発明は同じ分岐命令を繰返し実行する場
合に特に高速化の可能な分岐ヒストリテーブルを提供し
ようとするものである。

［課題を解決するための手段］ 本発明の階層型分岐ヒストリテーブルは、命令語の先取
りを行うデータ処理装置において、過去の分岐命令の実
行履歴に従って分岐命令のアドレス情報とその分岐命令
に対応する分岐先アドレスを含む分岐情報を保持する。

高速にアクセス可能な第１の分岐ヒストリテーブル手段
と、過去の分岐命令の実行履歴に従って分岐命令のアド
レス情報とその分岐命令に対応する分岐先アドレスを含
む分岐情報を記憶する。第１分岐ヒストリテーブル手段
に比較して大容量な第２分岐ヒストリテーブル手段と、
命令語の先取りにおいて先取る命令語のアドレス情報が
前記第１分岐ヒストリテーブル手段に登録されているか
どうかを検出する第１検出手段と、命令語の先取りにお
いて先取る命令語のアドレス情報が前記第２の分岐ヒス
トリテーブルに登録されているかどうかを検出する第２
検出手段と、第１の検出手段により、第１分岐ヒストリ
テーブル手段に先取る命令語のアドレス情報が登録され
ていることが検出された場合はそれに対応する分岐先ア
ドレスを第１分岐ヒストリテーブル手段より読出し、第
２検出手段により登録されていることが検出された場合
はそれに対応する分岐先アドレスを第２分岐ヒストリテ
ーブル手段より読出す手段とから構成される。

［実施例］ 次に１本発明について図面を参照して説明する。

第１図は本発明の一実施例である。第１図において、命
令アドレスレジスタａ１は、命令語の先取リアドレスを
受けるレジスタであり、アナログレジスタ変換器（図示
せず）より線１０１を介して出力される命令語アドレス
を受け、信号線１０２を介してアドレス比較回路ａ４及
び命令アドレスレジスタｂ５に送出する。

分岐命令アドレスレジスタ２は、最近の分岐命令に対す
るその命令アドレスを保持するレジスタであり、そのア
ドレスを線１０３を介しアドレス比較回路ａ４に送出す
る。このレジスタは本発明において特に設けたもので、
１〜１６ビツト程度の容量である。

分岐先アドレスレジスタ３は９分岐命令アドレスレジス
タ２に対応してその分岐先アドレスを保持するレジスタ
であり、そのアドレスを線１０４を介し分岐先アドレス
選択回路１１に送出する。

これも上記と同じように本発明において特に設けたもの
であり、容量も上と同じである。

アドレス比較回路ａ４は、命令先取りアドレスと分岐ヒ
ストリテーブル中の分岐命令のアドレスを比較する比較
回路であり、命令アドレスレジスタａ１より信号線１０
２を介して入力される命令取出しアドレスと１分岐命令
アドレスレジスタ２より信号線１０・３を介して入力さ
れる分岐命令のアドレスを比較し、一致したかどうかを
信号ｌ１ｌ１０５を介し優先度制御回路１０に送出する
。これも本発明において特に設けたものである。

命令アドレスレジスタｂ５は、メモリで構成された分岐
ヒストリテーブルを索引するための命令取出しアドレス
を保持するレジスタであり、信号線１０２を介して命令
アドレスレジスタａ１より送出される命令先取りアドレ
スを受け、その一部を信号線１０６を介しアドレスとし
て１分岐命令アドレスアレイ６及び分岐先アドレスアレ
イ７に。

その残りを信号線１０７を介してアドレス比較回路ｂ８
に送出する。　分岐命令アドレスアレイ６は１分岐命令
のアドレスを記憶するメモリであり。

命令アドレスレジスタｂ５より信号線１０６を介して出
力される命令取出しアドレスの一部をアドレスとしてそ
の分岐命令アドレスを信号線１０８を介してアドレス比
較回路ｂ８に送出する。容量はＩＫ〜２にビット程度で
ある。

命令先アドレスアレイ７は１分岐命令アドレスアレイ６
に対応してその分岐先アドレスを記憶するメモリであり
、命令アドレスレジスタｂ５より信号線１０６を介して
出力される命令取出しアドレスの一部をアドレスとし、
その分岐先アドレスを信号線１０９を介して分岐先アド
レスアレイレジスタ９に送出する。これも前記と同じ（
ＩＫ〜２にビットのものである。

アドレス比較回路ｂ８は、アドレス比較回路ａ４と同様
に、命令先取リアドレスと分岐ヒストリテーブル中の分
岐命令のアドレスを比較する比較回路であり、命令アド
レスレジスタｂ５より信号線１０７を介し送出される命
令取出しアドレスと信号線１０８を介し分岐命令アドレ
スアレイ６より送出される分岐命令のアドレスを比較し
、その結果を信号線１１０を介して優先度制御回路１０
に送出する。

分岐先アドレスアレイレジスタ９は、予測される分岐先
アドレスを受けるレジスタであり、信号線１０９を介し
分岐先アドレスアレイ７より送出される分岐先アドレス
を受け、信号線１１１を介して分岐先アドレス選択回路
１１に送出する。

優先度制御回路１０は１分岐先アドレスレジスタ３に保
持されている分岐先アドレスと分岐先アドレスアレイ７
に保持されている分岐先アドレスのどちらを選択するか
を制御する回路であり、信号線１０５を介しアドレス比
較回路ａ４より送出された一致情報と信号線１１０を介
してアドレス比較回路ｂ８より送出される一致情報とに
より。

予ハ１分岐先アドレス選択信号を信号線１１３を介して
分岐先アドレス選択回路１１に送出し、又。

予測アドレスを検出したことを示す信号を信号線１１２
を介して命令先取り制御装置（図示せず）に送出する。

本発明において特に設けたものである。

命令先アドレス選択回路１１は、予測分岐先アドレスを
選択する選択回路であり、信号線１０４を介し分岐先ア
ドレスレジスタ３より送出される予測アドレスと信号線
１１１を介して分岐先アドレスアレイレジスタ９より送
出される予測アドレスを選択し、信号線１１４を介しア
ナログディジタル変換器に送出する。これも前記と同じ
く本発明において特に設けたものである。

次に本例の動作について簡単に説明する。

分岐命令アドレスアレイ６及び分岐先アドレスアレイ７
のみにアドレスが登録されていた場合のタイムチャート
を第２図に示す。図の左側の括弧を付した数字は第１図
の装置の参照数字を示している。この場合の動作は従来
の方式と同じであり。

命令アドレスレジスタａ１にＴ、で命令取出しアドレス
が保持されると１次のＴ２で命令アドレスレジスタｂ５
にそれが保持される。ここで命令アドレスレジスタｂ５
のアドレスと分岐命令アドレスアレイ６のアドレスがア
ドレス比較回路ｂ８で比較されるが、それが一致すると
＋Ｔ３ではその予測分岐先アドレスが分岐先アドレスア
レイレジスタ９に分岐先アドレスアレイ７より読出され
ているので、優先度制御回路１０は信号線１１３により
分岐先アドレス選択回路１１にこれを選択させる。

さて８本特許で追加した部分の動作を第３図に示す。こ
の場合、命令アドレスレジスタａ１と分岐命令アドレス
レジスタ２の内容が直接アドレス比較回路ａ４で比較さ
れ、その結果により、優先度制御回路１０は信号線１１
３により分岐先アドレス選択回路１１に分岐先アドレス
レジスタ３を選択させる。

［発明の効果］ 以上説明したように本発明は、高速で動作可能な小容量
の分岐ヒストリテーブルと、低速ではあるが、大容量な
分岐ヒストリテーブルとを階層構造に持つことにより、
一部なりとも３Ｔかかつている処理をＩＴに短縮するこ
とができる。これにより、短いループなどのように何度
も同じアドレスで分岐するような場合に、そのアドレス
を高速で動作可能な小容量の分岐ヒストリテーブルに入
れておくことにより、命令先取りの遅れによる分岐性能
の低下を抑えることができる。

す図である。

記号の説明＝１・・・命令アドレスレジスタａ、　　２
・・・分岐命令アドレスレジスタ、３・・・分岐先アド
レスレジスタ、４・・・アドレス比較回路ａ、５・・・
命令アドレスレジスタｂ、６・・・分岐命令アドレスア
レイ、７・・・分岐先アドレスアレイ、８・・・アドレ
ス比較回路す、９・・・分岐先アドレスアレイレジスタ
。

１０・・・優先度制御回路、１１・・・分岐先アドレス
選択回路。

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示す図、第２図およ
び第３図は実施例のタイムチャートを示第２図 Ｔ＋　　Ｔ２　　Ｔ３Ｔ４　　Ｔ５ 虹工 ■ 出力　　　几 二ｔ＝Ｘ 出力　　　　　＝ｎニー （１） （５） （２） （４）出力 （３） 第３図 Ｔ１Ｔ２　　Ｔ３　　Ｔ４　　Ｔ５ Ｉ【 ■ 几 ４烏

Claims (1)

1. 【特許請求の範囲】 １、命令語の先取りを行うデータ処理装置において、 過去の分岐命令の実行履歴に従って分岐命令のアドレス
   情報と該分岐命令に対応する分岐先アドレスを含む分岐
   情報を保持する、高速にアクセスが可能な第１分岐ヒス
   トリテーブル手段と、過去の分岐命令の実行履歴に従っ
   て分岐命令のアドレス情報と該分岐命令に対応する分岐
   先アドレスを含む分岐情報を記憶する、第１分岐ヒスト
   リテーブル手段に比べて大容量な第２分岐ヒストリテー
   ブル手段と、 命令語の先取りにおいて先取る命令語のアドレス情報が
   前記第１分岐ヒストリテーブル手段に登録されているか
   どうかを検出する第１検出手段と、命令語の先取りにお
   いて先取る命令語のアドレス情報が前記第２分岐ヒスト
   リテーブル手段に登録されているかどうかを検出する第
   ２検出手段と、第１検出手段により、第１分岐ヒストリ
   テーブル手段に先取る命令語のアドレス情報が登録され
   ていることが検出された場合はそれに対応する分岐先ア
   ドレスを第１分岐ヒストリテーブル手段より読出し、第
   ２検出手段により登録されていることが検出されていた
   場合はそれに対応する分岐先アドレスを第２分岐ヒスト
   リテーブル手段より読出すことを特徴とする階層型分岐
   ヒストリテーブル。