JPH01169538A - 命令事前取出し装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、−殻内に、データ処理システム中のキャッシ
ュに関し、より詳しくは、分岐履歴テーブルを使ってキ
ャッシュに事前取出しすることにより、キャッシュの性
能を改善する装置及び方法に関する。

Ｂ、従来技術 高性能コンピュータ処理装置のパイプライン化の利用が
始まった時から、処理すべきコード内の条件付き分岐の
処理が高性能に対する主要な阻害因子であることが知ら
れて来た。パイプライン化の使用に先立ち、 １、命令を取り出す。

２、命令を復号する。

３、当該のレジスタにアクセスし、適当な計算を実行し
て、入力オペランドのアドレスを決定する。

４、当該の入力オペランドを取り出す。

５、入力オペランドを使って、命令によって指定される
処理を実行する。

６、処理の結果を記憶する。

という６個の事象シーケンスにより、デジタル式コンピ
ュータの処理を記述するのが、最も好都合と思われる。

非パイプライン式のマシンは、これらのステップを実行
し、次いで、次の命令を取り出して、シーケンスを繰り
返す。

パイプライン式マシンでは、これらの各ステップを、並
列な別々のハードウェア装置として物理的に実施する。

次のように、一連の命令で全装置が同時に動作する。あ
る命令がその最終結果を記憶する間に、次の命令が機能
的処理を実行し、その次の命令が入力オペランドを取り
出し、次の命令がオペランドのアドレスを計算し、次の
命令が復号され、次の命令がメモリから取り出される。

命令を処理する順序がわかっていれば、１サイクルに１
個の速度で命令を取り出し、次いでその命令をパイプラ
インに送り込むことが可能である。

つまり、１命令当たり理論上の６サイクルを必要とする
のでなく、１マシン・サイクルの間に、各命令が実行で
きる。

このシナリオは、厳密に順次的な命令の場合には非常に
有効であるものの、命令が順次実行されない場合にはあ
まり有効でない。分岐命令によって非順次処理が生じる
。分岐命令は、コンピュータにその利用可能なデータに
基づいて判断を下させるものであり、事実、この機能が
現代のコンピュータの威力の大きな源泉である。分岐が
選ばれる場合の効果は、順序通りならその分岐の次にく
るはずの命令の復号を中断して、メモリ中の別の記憶位
置から命令を復号し始めることである。

条件付き命令とは、ある条件（通常、分岐命令の直前に
ある命令の結果）のとき命令実行のこの転移（分岐）を
実行するだけの分岐命令である。

すなわち、分岐命令が復号される時点では、分岐を取る
かどうか、及びどこへ分岐するか（分岐先）が一般には
不明なので、分岐命令はパイプライン処理の円滑な順序
付けを中断する。従来技術では、分岐のためにパイプラ
イン式マシンが受ける不利益を軽減するために、様々の
試みが行なわれてきた。本発明は、分岐予知機構によっ
て提供される情報を使って、いわゆるキャッシュ・ミス
の影響を軽減する。

キャッシュは、コンピュータの主記憶装置よりも通常は
るかに小さく、かつはるかに高速のローカル・メモリで
ある。はぼすべての高性能デジタル式コンピュータがキ
ャッシュを使用し、市販のマイクロプロセッサにもロー
カル・キャッシュを有するものがある。直列式プロセッ
サを数個の並列パイプライン段に分割すると、１段当た
りの処理時間が単一命令の全体的処理時間よりも著しく
少なくなるので、パイプライン化の採用によりキャッシ
ュ使用の根拠が一部、動機付けられる。

したがって、パイプライン式マシンは、当然のこととし
て、サイクル時間がはるかに短い。したがって、アクセ
ス時間が一定しているメモリでは、アクセスを実行する
のに、長い非パイプライン・サイクルで必要となるより
も、より短いパイプライン・サイクルがより多く必要と
なる。メモリへのアクセス時間がプロセッサのサイクル
数の割に増大スルことが、マシンをパイプライン化する
ことの副作用である。

キャッシュが開発されたのは、パイプラインに相応した
サイクル時間で動作できるきわめて大きなメモリを妥当
なコストで作成することは不可能であったが、パイプラ
インに遅れずに動作できる小型メモリを作成することは
可能であったためである。キャッシュ中には、プロセッ
サが最も最近に参照した項目（命令及びデータ）を記憶
する。

プロセッサがその項目を再び参照する場合、パイプライ
ン・サイクル時間で、キャッシュからその項目を得るこ
とができる。こうした参照は、キャッシュ・ヒツトと呼
ばれる。キャッシュにない項目を参照する場合、プロセ
ッサは、より低速の主記憶装置からその項目を得なけれ
ばならない。いわゆるキャッシュ・ミスによって、主記
憶装置への参照が必要となる。

一度参照された項目（命令またはデータ）は、近い将来
に再び参照されることがあり得ることが認められている
。この特徴は「参照の時間的局在性」と呼ばれ、最も最
近に参照された項目をキャッシュ内に保存しておく理論
的根拠である。また、ある項目が参照される場合、参照
される項目に物理的に近接している他の項目も参照され
る可能性の高いことが経験的に認められる。この第２の
特徴は、「参照の空間的局在性」と呼ばれ、連続する項
目のブロックであるキャッシュ行を保存しておく理論的
根拠である。

上記で論じたように、通常のコンピュータは、大型の主
記憶装置と、ローカル・キャッシュ付きのパイプライン
式プロセッサを含んでいる。概念的に述べると、プロセ
ッサは、そのキャッシュから命令を取り出し、この命令
を復号し、そのキャッシュからオペランドを取り出し、
命令を実行する。

実際上は、通常、キャッシュとプロセッサの間に、近い
将来に復号される命令を保持する中間のバッファ段が存
在する。これは、命令バッファと呼ばれている。

キャッシュと同様に、（はるかに小規模なことを除き）
命令バッファは連続する命令ブロックを保持する。ただ
し、１キャッシュ行は通常６４バイトまたは１２８バイ
トであるが、命令バッファ中の１ブロツクは通常８バイ
トである。本体コンピュータでは、平均して、８バイト
のブロックで２個の命令を保持する。したがって、キャ
ッシュからの命令取出しが行なわれるごとに、おそらく
２個の有用な命令が命令バッファに転送される。

このため、キャッシュに課される帯域幅要件がいくらか
緩和され、このことが命令バッファの第１の重要な目的
である。命令バッファの第２の重要な目的は、パイプラ
インの復号装置に命令を正しい順序で転送できるように
ブロックをシフトさせることのできる制御を内蔵するこ
とである。

命令バッファがキャッシュと相違する主な点は、サイズ
が小さいことと再使用がないことである。

命令バッファのサイズは通常８ないし３２バイトの範囲
にあり、キャッシュのサイズは通常６４にないし２５６
にバイトである。キャッシュは主記憶装置をそっくりそ
のままエミュレートしなければならず、キャッシュへの
アドレスはすべて実アドレスで行なわれる。一方、命令
ブロックを命令バッファに入れる場合は、仮想アドレス
に基づいて認識されるにすぎない。命令バッファは小型
で、（関連する実アドレスを識別するための）ディレク
トリをもたないので、バッファ中の項目は一度使用され
ると廃棄される。つまり、命令バッファに１命令ブロツ
クが入れられると、分岐に達するまで、プロセッサは、
単に順次命令を復号していく。分岐が選ばれる場合には
、命令バッファに新しい命令ブロックが転送され、復号
が再開される。

「事前取出し」という用語をキャッシュ事前取出しに関
して使用する場合、命令バッファ中に命令を取り出すこ
とに関して使用する場合と意味が異なることに留意され
たい。

命令バッファに関して使用する場合の「事前取出し」は
、単に、命令を復号する前に（事前に取り出した命令が
復号されることに疑問の余地はないが）命令をバッファ
に入れることを意味するにすぎない。キャッシュに関し
て使用する場合の「事前取出し」は、常に、メモリ中の
特定の行が使用されるものと推測し、この行がプロセッ
サに参照されることが確実にわかる前にその行をキャッ
シュに転送することを意味する。したがって、命令バッ
ファへの事前取出しに特別な機構が必要でないこともあ
る。すなわち、この形式の事前取出しは、厳密に要求に
応じてほとんど制御なしに行なうことができる。ただし
、キャッシュへの事前取出しには、はとんど常に、実際
の要求取出しに末梢的にしか関係しない事象に基づいて
取出しを開始する、ある種の巧妙な機構が必要である。

本明細書に記載するようなメモリ階層では、様々な形の
取出しがすべて同時に行なわれる。各機構は、その設計
対象となる取出しの種類に基づいて、自身のアドレス・
レジスタを使用する。プロセッサ中の命令復号段で、い
わゆる「プログラム・カウンタＪ　　（ＰＣ）を使って
、命令バッファから個々の命令を取り出す。プログラム
・カウンタは、復号すべき命令のアドレスを含む。

マシンの状態、すなわち、マシンが論理的に取っている
プログラム中の位置がハーフワード・アドレスで表わさ
れるように、ハーフワード（２バイト）境界上に命令が
位置合わせされる。ダブルワード（８バイト）ブロック
を命令バッファ中に取り出す機構は、いわゆる「バッフ
ァ取出しアドレス」を使用する。これは、要求に基づい
て発生させることのできるダブルワード・アドレスであ
り、または分岐予知機構により発生させることができる
。

最後に、行をキャッシュ中に取り出すのに使用されるア
ドレスは、要求取出しに基づいて、または　。

キャッシュ事前取出し機構に基づいて、キャッシユ・ミ
スによって発生させる。

分岐命令のようなものが存在しない場合には、どんな命
令または命令ブロックまたはキャッシュ行を取り出すべ
きかについて、疑問の余地はない。

プロセッサは単に順次命令を連続的に命令バッファから
取り出し、命令バッファ取出し機構は、順次ブロックを
連続的にキャッシュから取り出し、キャッシュ・ミス機
能は主記憶装置から順次行を連続的に取り出す。したが
って、どの命令取出し過程でも、分岐が不確定性の唯一
の原因である。

当技術分野で既知の分岐予知機構が３種ある。取出し過
程に関して、それぞれがどのように異なっているか理解
しやすくするために、これらの機構について説明する。

使用されている機構のうち２つは、いわゆる「復号時間
」機構の変形である。最後の機構は、「取出し時間」機
構と呼ばれる。復号時間機構は、分岐が復号されるとき
に分岐の結果を予知する機構である。取出し時間機構は
、分岐を含む命令ブロックがキャッシュから命令バッフ
ァに転送されるときに分岐の結果を予知する機構である
。

当技術分野で既知の最も簡単な復号時間機構は、「静的
予知機構」と呼ばれる。この機構は、単に、復号された
分岐の種類に基づき（すなわち、静的情報に基づき）、
分岐の結果を推測する。−例を挙げると、この機構はカ
ウント分岐（ＢＣＴ）命令はすべて採用するが、高指標
分岐（ＢＸＨ）命令は採用しないものと推定する。すな
わち、この機構は、ＢＸＨはプログラムの他の部分に制
御を渡さないと自動的に推測するので、デコーダがＢＸ
Ｈを復号したとき、デコーダに順次命令を復号し続けさ
せる。デコーダがＢＣＴを復号したとき、この機構は、
常に、制御がプログラムの他の部分に渡されると推測す
るので、常にデコーダに復号をストップさせる。

ＢＣＴの場合、命令はまずパイプラインに入り、アドレ
ス計算を行なって分岐先命令のアドレスを決定し、次い
で分岐先ブロックをキャッシュから命令バッファ中に取
り出す。バッファ中でブロックが位置合わせされ（分岐
先命令がデコーダに渡され、そこで復号が再開される。

分岐を取らないことが正しく予知された場合、静的予知
機構はパイプラインの流れが中断されるのを妨げること
に留意されたい。分岐を取る場合には、流れが中断され
て、分岐先アドレスを計算することができ、分岐先命令
を取り出すことができるようになる。

ただし、分岐命令が実際に実行される前に、復号を再開
できる。したがって、分岐を取ることが正しく予知され
た場合、静的予知機構は、プロセ、ツサ・サイクルを保
管する。

ロスク（Ｌｏｓｑ）等の米国特許第４４７７８７２号明
細書及びＩＢＭテクニカル・ディスクロージャ・プルテ
ン、第２５巻、第５号に所載の°“復号分岐履歴テーブ
ル（Ｄｅｃｏｄｅ　Ｂｒａｎｃｈ　１ｌｉｓｔｏｒｙＴ
ａｂｌｅ）　’“と題する論文で、「復号履歴テーブル
」（ＤＨＴ）と呼ばれる他のより精巧な復号時間機構が
論じられている。これらは、静的予知機構と全く同じ方
式でパイプラインに作用するが、さらに履歴情報を使っ
てより高い予知精度を得る機Ｆｆ４である。復号履歴テ
ーブル（ＤＨＴ）は、命令が復号されるときに分岐命令
に関連するハーフワード・アドレス（プログラム・カウ
ンタ）を用いて各ビット項目にアクセスするという、ビ
ットのテーブルである。このテーブルは、分岐を実行す
るとき、履歴情報、すなわちその分岐が前に取られたか
否かを記録するのに使われる。同じ分岐を後で実行する
とき、このテーブルから前回の結果に関する情報も得ら
れ、その分岐が前回の実行時と同じ挙動を示すとの推測
が行なわれる。

復号時間機構は、分岐を正確に予知できる点ではパイプ
ラインに役立つとはいえ、分岐を取ることが正しく推測
された場合にそれを完全に利用することはできない。す
なわち、分岐が正しく推測される場合は、その分岐に関
連するパイプライン遅延のいくらかが節減されるものの
、分岐先アドレスが算出されて分岐先命令が取り出され
るまで、パイプラインは待たなければならない。取出し
時間機構は、分岐命令が取り出される時点で分岐の結果
を予知し、次いで分岐を取ると予知した場合には、分岐
先命令を直ちに取り出す機構である。

すなわち、取出し時間機構は、正しく予知した分岐を取
るための全パイプライン遅延を解消させる。

取出し時間機構は、一般に、「分岐履歴テーブルＪ　　
（ＢＩＴ）と呼ばれる。分岐履歴テーブルは、ズッセン
グート（Ｓｕｓｓｅｎｇｕｔｈ　）の米国特許第３５５
９１８３号明細書及びギュントナー（Ｇｕｅｎｔｈｎｅ
ｒ）等の米国特許第４５９４８５９号明細書で論じられ
ており、そこでは「転送及び間接予知テーブル」と呼ば
れている。分岐履歴テーブルは、過去の履歴を記憶する
点で、復号履歴テーブルに似ているものの、２つの重要
な点で異なっている。

第１に、キャッシュから命令バッファに分岐命令を取り
出すときに（すなわち、分岐命令を復号するより前に）
、分岐の結果を予知しなければならないので、（復号履
歴テーブルと一緒に使用されるようなプログラム・カウ
ンタでなく）ダブルワード・バッファ取出しアドレスと
の突合せに基づいて分岐があることを認識しなければな
らない。

第２の相違点は、分岐履歴テーブルは、分岐命令が復号
されるより前に、分岐先命令の命令取出しを開始しなけ
ればならないので、過去の分岐先ならびに過去の分岐の
挙動を記憶しておかなければならないことから生じる。

したがって、分岐履歴テーブルは、最近に取られた分岐
の分岐先命令のアドレスを含むテーブルである。分岐履
歴テーブルは、バッファ取出しアドレスによって、次の
ように駆動される。命令ブロックが命令バッファに転送
されるとき、バッファ取出しアドレスを使って分岐履歴
テーブルにアクセスする。その命令ブロックに含まれる
分岐命令の入口が分岐履歴テーブルにある場合、その入
口によって分岐先アドレスが供給され、分岐先命令を含
む命令ブロックが命令バッファに転送され始める。次い
で、分岐先命令のアドレスを使って、分岐府歴テーブル
が探索され、処理が続行する。

したがって、分岐履歴テーブルで駆動される機械では、
バッファ取出しアドレスを使用する命令バッファが分岐
履歴テーブルによって駆動され、デコーダは、プログラ
ム・カウンタを使って独立に稼動する。命令バッファ中
への転送はダブルワードごとに１サイクル当たり１ダブ
ルワードの速度で実行され、かつこのような転送のたび
ごとに分岐履歴テーブルを探索しなければならないので
、分岐履歴テーブルは、個々のハーフワード及び分岐先
アドレスを認識しなければならないものの、ダブルワー
ドごとに編成しなければならない。

タテノの米国特許第４５６１０５２号明細書には、メモ
リ、処理エレメント、及び命令バッファを備えた簡単な
処理システムが記載されている。

このメモリ・システムはある１サイクルでちょうど１つ
の要求に応じることができ、すなわち、１サイクルでち
ょうど１個の命令、またはちょうど１個のデータ・オペ
ランドのどちらか一方だけを、取り出すことが可能であ
る。上記の特許には、あるサイクルが命令を取り出すの
に使われるか、それともデータを取り出すのに使われる
かを決定するのに必要な論理機構の概要が記載されてい
る。

この論理機構は、命令バッファが空のとき、あるいは現
在実行中の命令がオペランド取出しを必要としないとき
、命令を取り出させる。この特許ではキャッシュを使用
せず、分岐やその予知については何も言及していない。

ポタシ５　（Ｐｏｔａｓｈ　）の米国特許第４４３５７
５６号明細書には、復号時間分岐予知が記載されている
。ただし、キャッシュ・ミスや分岐履歴テーブルは論じ
られていない。

ヒユーズ（Ｉｌｕｇｈｅｓ　）等の米国特許第４２００
９２７号明細書には、事前取出し機構が記載されている
。この特許では、３個の命令バッファを記載し、静的予
知を使用している。条件付き分岐に出会うと、１個のバ
ッフ１が「直通」経路に沿って命令を受け取り、もう１
個のバッファが分岐を取った経路に沿って命令を受け取
る。静的予知機構が、２つのストリームのどちらを事前
に実行するかを選択する。選択した経路に沿ってもう１
つの条件に出会う場合、静的予知機構を使って、後続の
経路のうち１つだけを第３の命令バッファ中に取り出す
。

リャン（Ｒｙａｎ）等の米国特許第４５５１７９９号明
細書には、命令用とデータ用に別々のキャッシュを有す
る分離キャッシュが記載されている。

ただし、分岐履歴テーブルを使ってキャッシュ事前取出
しを手助けすることは教示していない。

ＩＢＭテクニカル・ディスクロージャ・プルテン、第２
８巻、第８号（１９８８年１月）、３５１０ページに記
載の”ページ可能分岐履歴テーブルを使用する事前取出
しくＰｒｅｆｅｔｃｈｉｈｇ　ｔｌｓｉｎｇ　ａＰａｇ
ｅａｂｌｅ　Ｂｒａｎｃｈ　１ｌｉｓｔｏｒｙ　Ｔａｂ
ｌｅ）″と題する論文は、分岐履歴テーブルを使ってキ
ャッシュ行を取り出すことを教示している。そのために
、分岐先アドレスならびに行出ロアドレスを含む分岐履
歴テーブルが提案されている。このテーブルで分岐入口
が見つかると、命令バッフＴが分岐先アドレスによって
制御され、行出ロアドレスを使ってキャッシュ行の事前
取出しが行なわれる。ある行から出るとき（すなわち、
制御の流れがその行を離れるとき）、指定されていない
ハードウェアまたはソフトウェアによって出口解析が行
なわれ、将来使用できるように出口解析に基づき行出ロ
アドレスが更新される。本発明では、入口解析が行なわ
れる。すなわち、行に入る直前または入った時点で、解
析が行なわれる。本発明では、事前取出しを行なう時間
である入口で解析が行なわれるので、分岐履歴テーブル
中に行出ロアドレスの必要はない。さらに、本発明のよ
うな分岐解析を行なう機構は教示されていない。

ＩＢＭテクニカル・ディスクロージャ・プルテン、第２
２巻、第１２号（１９８０年５月）、５５３９ページに
所載の”分岐履歴テーブルを使ったキャッシュ行の事前
取出しくＵｓｉｎｇ　ａ　Ｂｒａｎｃｈｌｌｉｓｔｏｒ
ｙ　Ｔａｂｌｅ　ｔｏ　Ｐｒｅｆｅｔｃｈ　Ｃａｃｈｅ
　Ｌｉｎｅｓ）　”と題する論文は、分岐履歴テーブル
がキャッシュ中にない行に分岐先アドレスを発生させる
場合、その行をキャッシュ中に事前に取り出すのがおそ
らく適切であることを教示している。ただし、キャッシ
ュ行に基づいて分岐履歴テーブルを編成することも、キ
ャッシュ・ミスを予測するためにある行のすべての分岐
入口を解析することも教示していない。

ＩＢＭテクニカル・ディスクロージャ・プルテン、第２
３巻、第２号（１９８０年７月）、８５３ページに所載
の”分岐履歴テーブル機械におけるキャッシュ・ミスの
減少法（Ｒｅｄｕｃｉｎｇ　ＣａｃｈｅＭｉｓｓｅｓ　
ｉｎ　ａ　Ｂｒａｎｃｈ　１ｌｉｓｔｏｒｙ　Ｔａｂｌ
ｅ　Ｍａｃｈｉｎｅ）　”と題する論文は、キャッシュ
・ミスを利用して分岐履歴テーブル側での誤予知を識別
することを教示している。条件分岐レジスタ（ＢＣＲ）
は、主として、サブルーチンから戻るのに使用されてい
る。サブルーチンは異なる多くの位置から呼び出される
ので、過去の分岐先アドレスが現在の分岐先アドレスで
はないことが、ＢＣＲが誤予知される主な理由である。

したがって、本発明とは対照的に、分岐履歴テーブルが
キャッシュ中にない行に分岐先アドレスを発生させる場
合、及び基礎となる分岐がＢＣＲである場合には、分岐
履歴テーブルがおそらく誤っており、事前取出しを抑制
すべきである。

ＩＢＭテクニカル・ディスクロージャ・プルテン、第２
８巻、第４号（１９８５年９月）、１７３７ページに所
載の論文”小型キャッシュを使った分岐履歴テーブル（
ＢＨＴ）の防ＭＶＪ　（Ｕｓｉｎｇ　ａＳｍａｌｌ　Ｃ
ａｃｈｅ　ｔｏ　Ｉｌｅｄｇｅ　ｆ’ｏｒ　ａ　Ｂ　Ｈ
Ｔ　）　”には、分岐履歴テーブル側での誤予知に関連
する不利益を最小にする方法が提案されている。この論
文では、分岐を取らないと分岐履歴テーブルが推測する
ときでも、分岐先命令を命令バッファ中に取り出すこと
が提案されている。取らないと推測された分岐が取られ
た場合には、分岐先命令が命令バソノア中にあるので、
取られた経路に沿って直ちに復号が開始できる。

ＩＢＭテクニカル・ディスクロージャ・プルテン、第２
２巻、第８Ａ号（１９８０年１月）、３４３７ページに
所載の１′分岐履歴テーブルを使用する動的分岐予知（
Ｄｙｎａｍｉｃ　Ｂｒａｎｃｈ　Ｐｒｅｄｉｃｔｉｏｎ
ｔｌｓｉｎｇ　Ｂｒａｎｃｈ　ｌ１ｉｓｔｏｒｙ　Ｔａ
ｂｌｅ）″と題する論文は）キャッシュの挙動と分岐履
歴テーブルの関係を論じている。分岐履歴テーブルより
も多くの履歴を記憶しているキャッシュの場合、一連の
キャッシュ・ミスは、新しいまたは未記憶のコードが実
行され始め、分岐履歴テーブルによって生じる予知が新
しいコードにまず無関係であるらしいことを示す。した
がって、一連のキャッシュ・ミスの後、分岐履歴テーブ
ルによる予知は無視され、分岐を取った経路も取らなか
った経路も取り出してどちらの結果にも備える。

Ｃ１発明が解決しようとする問題点 したがって、本発明の目的は、分岐履歴を利用してキャ
ッシュへの事前取出しを行なうことにある。

本発明のもう１つの目的は、ある行の全分岐入口を解析
してキャッシュ・ミスを予測することにある。

Ｄ０問題点を解決するための手段 分岐履歴情報に基づいて将来のキャッシュ・ミスを推論
する分岐解析機構を使用して、分岐履歴テーブルに含ま
れる情報を使って、キャッシュ・ミスを予測し命令行の
キャッシュへの事前取出しを行なう装置が述べられる。

分岐履歴テーブルは、本発明が適用されるキャッシュ行
の取出し段に適合するように、行ごとに編成される。

本発明の別の実施例では、ある行への入口点に基づいて
その行中の分岐を実施する順序を決定する手段を使って
、どの出口点を使うか決定する。

Ｅ、実施例 ここで、本発明の全体的ブロック図を示した第１図を参
照する。プロセッサ１０は゛、復号、アドレス生成、キ
ャッシュ、実行の諸機能を実行する並列パイプライン式
装置を含んでいる。命令バッファ１１は、上記の機能を
実行するレジスタである。キャッシュ１２は、プロセッ
サ１０が使用する命令及びデータを供給し、メモリ１３
もプロセッサ１０が使用するデータ及び命令を供給する
。

上記のように、命令またはデータ、あるいはその両方が
キャッシュ１２中にない場合、プロセッサはそれをメモ
リ１３中で見つけようとする。メモリ１３は、ディレク
トリ（図示せず）を内蔵している。ディレクトリは、キ
ャッシュ１２中に行として記憶されているメモリ・ブロ
ックの索引である。別の実施例では、ディレクトリがキ
ャッシュの一部になっている。キャッシュ１２は、行ご
とに編成され、通常は６４にないし１２８にバイトの記
憶装置である。

キャッシュ１２は、命令バッファ１１に、ダブルワード
（メインフレームでは１ワードは４バイトであり、した
がってダブルワードは８バイトに等しい）を転送し、命
令バッファ１１は、プロセッサ１０が処理できるように
ダブルワードを保持する。

ローカル分岐履歴テーブル（ＢＨＴ）１５は、ダブルワ
ードごとに編成され、上記及び従来技術で周知の分岐履
歴テーブルの機能を実行する。バッファ取出しアドレス
・レジスタ１４は、キャッシュ１２から命令バッファ１
１に転送されるダブルワードのアドレスを保持するレジ
スタである。このアドレスは、要求に応じてプロセッサ
１０が生成することも、あるいは分岐予知機構が生成す
ることもできる。この図の場合、キャッシュ１２から命
令バッファ１１にダブルワードが移動するときに、ダブ
ルワード・アドレスを使って、線１４Ｂを介してＢＨＴ
１５を探索する。ＢＨＴ　１５によって分岐が予知され
た場合、線１４Ａ上の分岐先アドレスを反映するように
、バッファ取出しアドレス・レジスタ１４が更新される
。上記の諸要素は、当技術分野で周知の通常の計算機シ
ステムの要素である。ただし、第１図に示した残りの要
素、すな　　′わち次行アドレス・レジスタ２０１広帯
域ＢＨＴ２１、及び事前取出し機構２２は、新しい本発
明独自の要素である。

次行アドレス・レジスタ２ｏは、次に参照される行のア
ドレスを保持するレジスタである。このレジスタは、事
前取出し機構２２ならびにバッファ取出しアドレス・レ
ジスタ１４から入力を受け取り、アドレスすべき次行を
決定する。また、キャッシュ１２と同じ基準で編成され
ている広帯域ＢＨＴ２１に、次に参照される新しい行の
アドレスを与える。つまり、キャッシュ１２が１２８バ
イトの行を利用する場合、広帯域ＢＩＴ２１も１２８バ
イトの行を利用する。事前取出し機構２２は（メモリ１
３中のディレクトリで指示されるように）、キャッシュ
１２中にもう行がない場合に、命令シーケンス中の分岐
命令に基づいて、どの行をキャッシュ事前取出しすべき
かを決定する機構を内蔵している。

より一般的に言うと、次行アドレス・レジスタ２０は実
際に項目の待ち行列となることができる。

こうすると、将来の数行の解析が容易になり、新しい行
に入ると直ちに事前取出しが開始できる。

新しい行に入るとき、スタック中の最も古い項目をバッ
ファ取出しアドレス・レジスタ１４と比較することによ
り、過去の事前取出しの確認を行なう。

広帯域ＢＨＴ２ｉ中の項目は、幅が広く、ローカルＢＨ
Ｔ１５の場合のようなダブルワードではなく、行特有で
ある。すなわち、行アドレスによって合同（ｃｏｎｇｒ
ｕｅｎｃｅ　）クラスを選択し、項目中の高位ビットで
比較をさらに行なって、どの項目が所与の行に特有であ
るかを決定する。また、各項目中で、その行内部のハー
フワード・アドレスを指定しなければならない。ダブル
ワードで編成されているＢＩＴにとって一般に２方向セ
ット結合性で十分なので、６４バイトの行で編成されて
いるＢＩＴには８方向セット結合性で十分なはずである
。

上記の各パラメータは、通常の本体コンピュータに関連
性がある。ただし、この実施例の残りの部分では、より
小さな寸法を使って、本発明の教示をより簡単に説明し
やすくする。以下では、命令バッファ１１はダブルワー
ドを含み、ローカルＢＨＴ１５はダブルワードごとに編
成されているものと仮定する。さらに、キャッシュ行は
カッドワード（ダブルワード２個）であり、広帯域ＢＩ
Ｔ２１はカッドワードごとに編成されているものと仮定
する。最後に、ローカルＢＨＴ１５は２方向セット結合
性であり、１６個の合同クラスを有し、広帯域ＢＩＴ２
１は４方向セット結合性であり、１０２４個の合同クラ
スを有するものと仮定する。したがって、ローカルＢＨ
Ｔ　１５は３２個の項目を含み、広帯域ＢＩＴ２１は４
０９６個の項目を含む。

上記のことをさらに理解するため、第２Ａ図及び第２Ｂ
図を参照する。本体コンピュータ中の分岐アドレスは、
３１ビツトを含んでいる。３ｏ及び３４で示した最下位
ビット（バイト・オフセット）はＯビットであり、本発
明では無視される。

３２で示した４ビツトは、ローカルＢＨＴ中の合同クラ
スを選択するのに使用され、３６で示した１０ビツトは
、広帯域ＢＨＴ中の合同クラスを選択するのに使用され
る。３３及び３７は、当該ＢＩＴ中の高位アドレス・ビ
ットを示し、３１及び３５は、それぞれ、ダブルワード
内部及びカッドワード内部のハーフワード・オフセラト
ラ示ス。

したがって、広帯域ＢＩＴ２１は、１７個の高位ビット
３７、カッドワード３５内のハーフワード・オフセット
、それに、後で詳しく説明する分岐先アドレス（Ｔ　Ａ
　＋　）を保持する。ローカルＢＨＴ１５は、対応する
フィールド３３及び３１と分岐先アドレス（ＴＡｉ）を
保持し、従来技術の教示に従って動作する。

４方向セット結合性の例では、広帯域ＢＩＴ２１内に４
個のこのようなルックアップ・テーブルがあり、各ルッ
クアップ・テーブル中の個々のアドレスが１０桁の合同
クラス選択ビット３６によって選択される。次いで、比
較を行なって、高位ビット３７が要求した行のそれと合
致するかどうかを決定することができる。合致する場合
、次行アドレス・レジスタ２０中のアドレスにヒツトす
る。

実行されるキャッシュ行の実際のシーケンスがアドレス
Ａ及びＢを有するものと仮定する。Ａのアドレスをバッ
ファ取出しアドレス・レジスタ１４を介して次行アドレ
ス・レジスタ２０に入れ、次いで、そこから広帯域ＢＩ
Ｔ２１に供給する。

次に、広帯域ＢＩＴ２１が、アドレスＡによって生じた
すべてのヒツトをローカルＢＨＴ１５及び事前取出し機
構２２に同報通信する。次いで、ローカルＢＨＴ１５が
、従来技術の教示に従って、命令バッファ１１を制御す
る。事前取出し機構２２は、その解析を実行し、行Ｂの
アドレスを生成して次行アドレス・レジスタ２０及びメ
モリ１３中のキャッシュ・ディレクトリに送る。もし、
キャッシュ１２中に現われている行Ｂがディレクトリに
リストされていない場合は、キャッシュ事前取出し機構
がアドレスＢををする行をメモリから事前取出しする。

第３図及び第４図を参照すると、事前取出し機構２２の
動作が理解できる。第３図は、事前取出し機構２２の構
成図である。第４図は、ＢＨＴ２１中の行Ａを示す。こ
の説明では、行Ａ（１００）は８個のハーフワードＯ−
７を有するものとする。

実線１０１．１０２．１０３．１０４は、行１００で取
られる分岐を示す。すなわち、行Ａのハーフワード３の
ところに１０１で表わされる行ＡのハーフワードＯに向
かう分岐がある。分岐１０２は、ハーフワード６からハ
ーフワード１に向かう分岐を表わす。分岐１０３は、行
Ａのハーフワード４のところにあり、新しい行Ｂのハー
フワード３に進む。分岐１０４は、新しい行Ｃのハーフ
ワード５に進む。分岐９９が、この行のハーフワード５
に入る。この分岐は、概略的に示すように、次行アドレ
ス・レジスタ２０から受け取る。

行Ａについての項目シーケンスを下記の第１表にまとめ
て示す。

［第　　Ｉ　　表］ 分岐アドレス　分岐先アドレス　Ｉ／Ｅ　（内部二〇）
Ｂ　Ａ　ｏ　”　Ａ　＋　６　　Ｔ　Ａ　ｏ　＝　Ａ　
＋　１　　　　０Ｂ　Ａ　ｒ　＝　Ａ　＋　４　　Ｔ　
Ａ　ｒ　＝　Ｂ　＋　３　　　　１Ｂ　Ａ　２　＝　Ａ
　＋　７　　Ｔ　Ａ　２　＝　Ｃ＋　５　　　　１Ｂ　
Ａ　３　＝　Ａ　＋　３　　Ｔ　Ａ　３　＝　Ａ　＋　
’０　　　　０第Ｉ表を参照すると、分岐９９で行Ａの
位置５に入る場合、項目が順次実行されるときに出会う
最初の分岐アドレス（ＢＡｏで示す）はＡ＋６である。

これは、第工表に示すように、Ａ＋１という分岐先アド
レス（Ｔ　Ａ　ｏ　）を有する。内部／外部（Ｉ／Ｅ）
ビットは、ゼロにセットされ、この行内の内部分岐を示
す。Ａ＋４にある分岐アドレス１　（ＢＡＩ）は、その
分岐先アドレスとして、行Ｂ中のＢ＋３で示されるアド
レスを有する（ＴＡ　Ｉ＝　Ｂ　＋　３　）。このアド
レスは行Ａの外部のアドレスなので、工／Ｅビットは１
にセットされる。

分岐アドレス２（ＢＡ２）はＡ＋７に等しく、別の外部
行Ｃのハーフワード５へ分岐し、したがってＴＡ２はＣ
＋５に、またＩ／Ｅビットは１にセットされる。第１表
の第４の項目は、ＢＡ３がＡ＋３に等しく、Ａ＋０とい
う分岐先アドレス（ＴＡ　３）を有することを示してい
る。これは行Ａ内の内部分岐なので、■／Ｅビットはゼ
ロにセットされる。

第１図を再度参照すると、第１表に示す項目が線３１．
３２．３３．３４を介して回報通信される。すなわち、
ＢＡｏはＴＡｏと共に線３１を介し、ＢＡＩ及びＴＡＩ
は線３２を介し、ＢＡ２及びＴＡ２は線３３を介し、Ｂ
Ａａ及びＴＡ３は線３４を介し、Ｉ／Ｅビットに対する
当該の項目と共に同報通信される。

第３図を再度参照する。エントリ・レジスタ２０は、実
際には次行アドレスのカッドワード内部に、マツプ・テ
ーブル４０にアドレスするためのハーフワードを含んで
いるだけでよい。エントリ・レジスタ２０には、最初に
、新しい行への入口点がロードされる。行Ａの場合、こ
れは９９を介し、入口点は５である。本発明の動作の流
れを利用し理解する際、第３図中の様々なレジスタ、テ
ーブルなどに現われる項目は括弧に入れたレジスタに隣
接し、順次動作の結果を示すためセミコロンで分離しで
ある。

どの入口点についても、マツプ・テーブル４０は次の事
柄を示す。これは、実際の入口点でライン中に走査を進
めて出会うことになる最初に取った分岐に対応する入口
点を正規化し、１）正規化入口点を内部で取る場合には
、正規化入口点に対応する分岐を取った後で出会う次に
取った分岐の内部アドレス、または２）正規化入口点分
岐を外部へ取る場合には、新しい行の中への入口点、ま
たは３）取った分岐で正規化過程に出会わない場合には
、次の順次行のアドレスを与える。

第４図を再度参照すると、行Ａのアドレス５に入って、
アドレス人口６で入口１に分岐し、その後、順に進んで
、入口３で次の分岐が起こる。すなわち、値５を使って
マツプ・テーブルにアクセスすると、マツプ・テーブル
は値３を出力し、Ｉ／Ｅ標識をゼロにセットするはずで
ある。

第■表は、マツプ・テーブル４ｏの内容のサンプルを示
すもので、具体的には、行Ａ（１００）に従って、８個
の位置と各位置の内容を示している。たとえば、入口０
ないし３は、次に取られる分岐の内部アドレスを含み、
かつそれが行Ａ中の位置を通って前方に順次走査するこ
とによって得られる内部分岐であることの指示も含んで
いることに留意されたい。入口４で、新しい行への外部
分岐Ｂ＋３がある。したがって、以上の通り、入口点分
岐は外部に向かっているので、この入口は新しい行への
入口点である。残りの入口も同様に決定される。

［第　　■　　表コ 位　　置　　　　　　　　　内　　容 ０３、■ １３、Ｉ ２３、Ｉ ３３、■ ４Ｂ＋３、Ｅ ５３、Ｉ ６３、Ｉ ７Ｃ＋５、Ｅ このマツプ・テーブルは、出力を入力に戻して循環させ
ることにより、連続サイクルで探索される。これは、外
部行が見つかるまで、または、分岐が見つからなくなる
までこのサイクルを続け、分岐が見つからない場合は、
次行が次の順次行となる。４方向セット結合性広帯域Ｂ
ＨＴの場合、このプロセスは４サイクル以下で終了する
。各ルックアップの後、４個のレジスタ５Ｌ　５２．５
３．５４のうちの１個に結果を記憶する。ルックアップ
の結果が前回のルックアップの結果と一致することが判
明した場合、内部分岐サイクルが見っがったことがわか
る。この場合、過去のすべてのルックアップの最大値が
（分岐サイクルを通過するように）増分され、その結果
次の入口点が得られる。

この最大（ｍａｘ）機能は最大（ｍａｘ）回路６０で実
行される。

第４図のキャッシュ行と第■表のマツプ・テーブルの例
を参照すると、事前取出し機構の動作がより詳細に理解
できる。キャッシュ行の入口点は５にあり、したがって
、エントリ・レジスタ２゜は最初、５に設定される。こ
のため、マツプ・テーブル４０はその次の分岐位置を指
す３の出力を生成し、■／Ｅは工に設定される。この出
力は選択回路６５に送られる。選択回路６５はマツプ・
テーブル４０または加算器６６のいずれかから入力を選
択する。加算器６６は、最大（ｍａｘ）回路６０の出力
に１を加える。選択は、ＯＲ回路７０または線７１上の
Ｉ／Ｅビットのいずれかの制御下で行なわれる。３の出
力は、マツプ・テーブル４０から各レジスタ５１．５２
．５３．５４にも転送される。これらのレジスタはカウ
ンタ７２に結合される。カウンタ７２は発明ではモジュ
ーロ４のカウンタであり、各レジスタ５Ｌ　５２．５３
．５４を使用可能にする。カウンタ７２はクロック発生
器８０からクロック信号を受け取るが、この同じクロッ
ク信号がエントリ・レジスタ２０にも送られることに留
意されたい。事前取出し機構が外部分岐を見つける仕事
を完了すると、レジスタ５１．５２．５３．５４及びカ
ウンタ７２がリセットされ（９５）、新しい行への入口
点がエントリ・レジスタ２０に記憶される。この例では
、行Ａへ入る時の事前取出し機構の初期状態は、エンＩ
−ＩＪ・レジスタ２０が値５を含み、レジスタ５Ｌ５２
、５３．５４がすべて値Ｏを含むという状態である。

サイクルＯで、マツプ・テーブル４０は値３、■を出力
する。この値３がレジスタ５１．５２．５３．５４の入
力及び選択回路６５の入力に送られる。カウンタ回路７
２は、レジスタ５１を使用可能にさせ、レジスタ５１は
値３を出力する。比較回路９０．９１．９２．９３は、
エントリ・レジスタ２０中の値を、それぞれレジスタ５
１ないし５４の出力と比較する。この場合、比較回路９
０は値５と３を比較し、その他の全ての比較回路９１な
いし９３は値５とＯを比較する。そのどれも等しくなら
ないので、ＯＲ回路７０は、選択回路６５に影響しない
値Ｏを出力する。一方、マツプ・テーブル４０からの信
号Ｉは、選択回路６５に値３をその出力にまで送らせる
。最大回路６０はレジスタ５１ないし５４中に保持され
ている最大値、この場合には３を決定する。この値に、
増分器６６が１を加え、４を得る。

サイクル１では、クロック発生器８０が、エントリ・レ
ジスタ２０に選択回路６５の出力からの値３をロードさ
せる。マツプ・テーブル４０は、再び値３、工を出力す
る。値３はレジスタ５１ないし５４の入力に送られ、カ
ウンタ回路７２がレジスタ５２を使用可能にする。比較
回路９ｏ及び９１は、今度はレジスタ５１と５２の両方
がエントリ・レジスタ２０と同じ値を含むことを見つけ
る。ＯＲ回路７０が値１を出力し、このため、選択回路
６５は増分器６６の出力をエントリ・レジスタ２０に送
り戻す。この場合、最大回路６０は値３を出力し、その
結果、増分器６６、したがって選択回路６５も値４を出
力する。

サイクル２では、クロック発生器８０が、レジスタ２０
に選択回路６５の出力からの値４をロードさせる。マツ
プ・テーブル４０は、値Ｂ＋３、Ｅを出力する。信号Ｅ
は解析の終了を表わし、選択回路６５に新しい行アドレ
スＢ及び新しいハーフワードの入口点３を出力させ、さ
らに、レジスタ５１ないし５４を値Ｏにリセットする。

第３図に示したマツプ・テーブル４０は、後で第４図な
いし第１０図で説明する部分回路から構成される。マツ
プ・テーブルは直接アドレス可能なテーブルであり、そ
の入力は行内部のハーフワード・アドレスで、出力は上
記の通りである。マツプ・テーブル４０のマツプ機能の
実施態様は、次の通りである。

次に、第５図に構成を示した第５Ａ図及び第５Ｂ図を参
照する。Ａなどの行内部の分岐ＢＡ＋ごとに、ＢＡ＋°
が決定される。これは、ＢＡＩが外部分岐の場合は、分
岐先アドレスＴＡ、であり、ＢＡＩが内部分岐の場合に
は、最小のＢＡＩすなわち、≧Ｔ　Ａ　＋である。この
機能は第５Ａ図及び第５Ｂ図の回路で、実行される。第
１図からの線３１．３２．３３．３４が、レジスタ１０
５．１０６．１０７．１０８に結合され、分岐アドレス
項目（ＢＡＩ）、分岐先アドレス（ＴＡ＋）、及びＩ／
Ｅビットの設定をそれらのレジスタに転送する。

上述例によると、レジスタ１０５はＢＡｏ”６、ＴＡｏ
＝Ａ＋１、Ｉ／Ｅ＝Ｏを含み、レジスタ１０６はＢＡ、
＝４、ＴＡ＋＝Ｂ＋３、Ｉ／Ｅ＝１を含み、レジスタ１
０７はＢＡ２＝７、Ｔ　Ａ２　＝　Ｃ＋５、Ｉ／Ｅ＝１
を含む。最後に、レジスタ１０８は、第１表により、Ｂ
Ａ３＝３、Ｔ　Ａ　３＝　Ａ　＋　Ｏ１Ｉ／Ｅ＝Ｏを含
む。広帯域ＢＩＴ２１から線３１．３２．３３．３４を
介して新しい行に対する順次の値を受け取る。

比較回路１１０ないし１２５は、その両人力線に供給さ
れた情報の比較を行なって、ＢＡ入力≧ＴＡ入力の場合
、ＢＡ大入力出力線に渡す。そうでない場合、出力は表
現可能な最大数に１を加えた値にセットされる。この例
では、この値は、「ダミー」高次ビットを作成すること
によって得られる２進数１０００である。

比較回路１１０ないし１２５は、分岐アドレスを分岐先
アドレスと比較するが、この説明では４個ずつのグルー
プとして配列されている。比較回路１１０ないし１１３
は、一方の入力としてレジスタ１０５からの分岐アドレ
スを有し、それをレジスタ１０５．１０６．１０７．１
０８から得られる４個の分岐先アドレスのそれぞれと比
較する。

残りの比較回路１１４ないし１２５も、同様に、すべて
の分岐アドレスとすべての分岐先アドレスが４個ずつの
グループで比較されるように配列されている。次いで、
これらの比較の結果が最小選択回路１３０．１３１．１
３２．１３３に供給される。これらの選択回路は、その
入力線に印加された任意の値の最小値を比較して選択し
、その値をその出力線で供給するように構成されている
。

これらの選択回路は、同じ分岐先アドレスを比較してい
る比較回路の出力がすべて同じ最小選択回路に供給され
るように結合されている。つまり、たとえば、レジスタ
１０５からの分岐先アドレスをそれぞれ入力とする比較
回路１１０，１１４．１１８．１２２の出力が、最小選
択回路１３０に供給される。同様に、最小選択回路１３
１は、それぞれレジスタ１０２からの分岐先アドレスを
比較する比較回路１１１．１１５．１１９．１２３の出
力線からその入力を取る。最小選択回路１３２及び１３
３も、その入力が同様にして選択される。

最小選択回路１３０．１３１．１３２．１３３の出力線
は、次にそれぞれ選択回路１４０．１４１．１４２．１
４３に結合される。選択回路１４０１１４１．１４２．
１４３は、２つの入力のうち１つを選択して、その入力
をその出力線に供給する。上記のように、一方の入力は
最小選択回路１３０ないし１３３から導かれ、もう一方
の入力は１つのレジスタの分岐先アドレス部分から導か
れる。これらの選択回路は、選択回路１４０．１４１．
１４２．１４３がその第２人力をそれぞれレジスタ１０
５．１０６．１０７．１０８から導くように配列されて
いる。この選択は、当該の各レジスタ１０５．１０６．
１０７．１０８中のＩ／Ｅビットによって制御される。

Ｉ／Ｅ＝０の場合、結果として得られるＢＡ＋°出力は
最小選択アドレスであり、そうでない場合には分岐先ア
ドレスＴＡＩを指定する。

第５Ａ図及び第５Ｂ図に示すように、行Ａ（１００）用
のレジスタ１０５は、ＢＡｏ＝６、ＴＡ。

＝ｌ、Ｉ／Ｅビット＝Ｏの値をとる。この値は、第工表
にも載っており、第４図から導かれる。残りのレジスタ
も、上記のように同様にセットされる。つまり、比較回
路１１０は、６と１の入力を受け取り、６を出力する。

同様に、比較回路１１４は、４と１の入力を受け取って
４の出力を生成し、比較回路１１８は、７と１の入力を
受け取って７の出力を生成し、比較回路１２２は、３と
１の入力を受け取って３の出力を生成する。これらの出
力はそれぞれ最小選択回路１３０に供給され、その結果
、ここでこれら４個の値の最小値として３が選択され、
次いで、この値がレジスタ１０５からの分岐先アドレス
の値１（実際にはＡ＋１）と−緒に、選択回路１４０に
供給される。Ｉ／ＥビットはＯにセットされているので
、選択が行なわれて、３の値を選択し、ＢＡｏ’出力と
して供給される。

最小選択回路１３１は選択回路１１１．１１５．１１９
．１２３から入力を受け取ることに留意されたい。この
例では、最小値は３であるが、１０６からのＩ／Ｅビッ
トが１にセットされているので、選択回路１４１は単に
、レジスタ１０６からＢ＋３の分岐先アドレスを選択す
る。ＢＡ　　“に■ 対する出力として、Ｂ＋３ならびに１の外部ビットが供
給される。残りの出力ＢＡ　　’及びＢＡ　　’も、同
様にして計算できる。

次に、第６図を参照する。第５Ａ図及び第５Ｂ図の回路
での上記の動作と平行して、マツプ・テーブルは、ある
行中の各ハーフワードごとに、その行の任意のハーフワ
ードより後でいくつの分岐が起こるかを確定する。これ
を実施する回路が、第６図に示されている。分岐数は、
任意のハーフワード・アドレスより大きいかまたはそれ
に等しいＢＡｌの数の簡単な加算によって求められる。

この例で、行Ａ中での所望の出力を第３表に示す。

［第　　３　　表コ ハーフワード・アドレス　　　　　分　岐ＨＷ７　　　
　　　　　　　　１ ＨＷ６　　　　　　　　　　　２ ＨＷ５　　　　　　　　　　　２ ＨＷ４　　　　　　　　　　　３ ＨＷ３　　　　　　　　　　　４ ＨＷ２　　　　　　　　　　　４ ＨＷＩ　　　　　　　　　　　　４ ＨＷＯ４ これらの値は、第４図を見ると明白である。たとえば、
ハーフワード３に注目すると、ハーフワード３から行端
まで順次の前方向走査で出会う分岐が４個あることが認
められ、したがって、ハーフワード３に関連する値は４
である。ハーフワード４については、行の前方向走査で
３個の分岐に出会うことがわかり、したがって、値はＨ
Ｗ４＝３と指定される。

第６図の回路は、次のように動作する。デコーダ１５０
ないし１５３は、当該の線３１ないし３４上で、ＢＩＴ
２１からの適当な入力ＢＡ＋から２進数を受け取る。各
デコーダ１５０ないし１５３は１個の入力を有し、この
例では０と７の間のいずれかの２進数を受け取り、複数
の出力線上にその入力を指示する。各出力は、ある所与
の入力２進数に対して、その入力２進数に等しいかまた
はそれより小さな値を存するすべての出力が１に指定さ
れるような、ある特定のビット位置に割り当てられる。

入力２進数よりも大きな値を割り当てられているすべて
の場所は、０となる。つまり、デコーダ１５３上のＢＡ
ａ線を参照すると、６が入力された場合、位置Ｏないし
６はすべて１の値をとり、ビット位置７は０の値をとる
。同様に、他のすべてのデコーダも、そこに供給された
データを復号する。したがって、次いで、デコーダの出
力が結合され、選定されたすべてのビット位置が同じ加
算器に結合されるようにする。つまり、たとえば、１５
０．１５１．１５２．１５３からのビット位置７がすべ
て加算器（ＡＤＤ）ＩＥ３０に結合される。同様に、加
算器（ＡＤＤ）１６１ないし１６７はそれぞれ位置６な
いしＯをその入力とする。加算器１６０ないし１６７は
、当技術分野で周知の加算器であり、単に４個の入力を
加え、入力の加算に対応する値をとる２進数の出力を有
する。−例を挙げると、ハーフワード４を受け持つ加算
器１６３は、デコーダ１５３からＯを受け取るが、デコ
ーダ１５０ないし１５２からは１を受け取る。これは、
上記の第３表中の所望値と一致する。

第７図にデコーダ１５０ないし１５３を詳しく示す。

デコーダ２００は、標準のディジタル論理要素を使って
実現することができる。デコーダ２００は、２進コード
化入力を復号して、８個の互いに排他的な出力のうちの
１個にする。デコーダ２００の各出力は、行中の特定の
ハーフ・アドレスに対応している。このような復号器及
びデマルチプレクサは当技術分野で周知である。次いで
、デコーダの出力は、それぞれ、ＯＲゲート２０１ない
し２０８に適宜結合される。８個の出力を有するデコー
ダの例かられかるように、ＯＲゲート２０８は各出力に
結合されている。ＯＲゲー）２０８は、デコーダ２００
のゼロ位置に対するデータを運ぶ。

つまり、たとえば、デコーダ２００中への入力値が６の
場合、その線６がハイとなって１の値をとり、他のすべ
ての線は０の値をとる。線６はＯＲゲート２０２ないし
２０８に結合されているので、これらの各ゲートも１の
出力値をとる。つまり、デコーダ１５０はその線７上で
０の出力値をとるが、出力０ないし６は、すべて１とな
る。

第８図に構成を示す第８Ａ図及び第８Ｂ図は、ＢＡ＋と
ＢＡ＋’の間の対応関係がどのようにマツプ・テーブル
に入力されるかを示している。第８Ａ図及び第８Ｂ図の
回路は、ＢＩＴ２１から線３１ないし３４を介して、Ｂ
Ａ＋入力を受け取る。

ＢＡＤ’入力は第５Ａ図及び第５Ｂ図の対応回路から受
け取り、ＨＷＯないしＨＷ７の入力は第６図のカウンタ
回路から受け取る。

比較ブロック２１０は、ＢＡＩ入力を受け取って配列し
、かつ、ＢＡＤ’入力を受け取るスイッチ・ブロック２
２０を制御する。実際の配列されたＢＡ＋項目は、マツ
プ・テーブルベの入口には使われないが、この配列はＢ
Ａ＋“項目を配列し直すのに使われる。

比較ブロック２１０は、２個の入力を取り、これをその
最小出力と最大出力で配列し、２個の入力が交換された
かどうかを示す出力も供給する、最小最大比較機構（Ｃ
ＯＭＰ）２１１ないし２１５を含んでいる。つまり、最
小最大比較機構２１１は、２１１Ａと２１１Ｂで値を比
較し、その比較結果の指示を２１１０に供給する。今、
考察している例では、最小最大比較機構２１１は、その
入力でＢＡｏとＢＡ＋を受け取って配列し直し、ＢＡ　
ｏ　＝６かつＢ　Ａ　１＝　４のとき、最小出力２１１
ＡにＢＡ＋入力、最大出力２１１ＢにＢＡｏ入力が現わ
れるようにする。次いで、再配列の指示が２１１０に供
給される。これは、２１１Ｃからの信号に応答して、入
力の順序を交換すべきかどうかを決定するスイッチ２２
１に結合されている。残りのスイッチ及びスイッチ・ブ
ロック２２０も同様に動作し、比較ブロック２１０中の
当該の最小最大比較機構と対になっている。つまり、比
較機構２１２は結果信号をスイッチ２２２に供給し、比
較機構２１３．２１４．２１５はそれぞれの結果をスイ
ッチ２２３．２２４．２２５に供給する。

スイッチ・ブロック２２０の出力は、次に、選択回路２
３０ないし２３７に供給される。選択回路２３０ないし
２３７は、その選択入力に入力された値に応じて、４つ
の入力のうちのひとつを選択する。つまり、たとえば、
ハーフワードＯ上で４が選択回路２３０に供給される場
合、その入力からの値である４がその出力に供給される
。この例では、行中の分岐アドレスとして３の値、Ｉ／
Ｅビットの状況としてＩ／Ｅ＝０がその人力４に現われ
、この値がその出力、すなわち、ＩＮＯ出力で供給され
る。次いで、各選択回路からの出力がテーブル２５０に
供給され、そこに記憶される。

次に第９図には、テーブル２５０の内部動作と構成が示
されている。テーブル２５０は、レジスタ（ＲＥＧ）３
００ないし３０７を含んでいる。

この各レジスタ３００ないし３０７は、それぞれ第８Ａ
図及び第８Ｂ図の回路から受け取った入力ＩＮＯないし
ＩＮ７に結合されている。すべてのレジスタは入力線３
０８によって、並列にロードされる。つまり、レジスタ
３００ないし３０７は、記憶バッファとして働く。選択
回路３１０は、レジスタ３００ないし３０７に結合され
たその入力から任意の値を選択することができる。これ
らの入力は、エントリ・レジスタ２０から得られる入口
アドレスによって、３２０で選択される。選択回路３１
０の出力３２２は、読取り人力３２１によって使用可能
となる。

第１０図は、たとえば第３図の６０及び第５Ｂ図の１３
０で使用される最小最大比較回路（Ｇ。

ＭＰ）を示している。４人力の最小最大回路４００は、
５個の２人力最小最大回路４０１ないし４０５を含んで
いる。この４人力最小最大回路は、第８Ａ図のブロック
２１０と同じであり、それと同様の方式で動作する。こ
の回路を単純に反復拡大して、任意の数の入力に対応さ
せることもできる。これは、当技術分野で周知のように
、２ト一ン式の実施態様である。

Ｆ１発明の効果 本発明により、分岐履歴を利用してキャッシュ・ミスを
予測しながらキャッシュへの事前取出しを行なうことが
できる装置が実現された。

【図面の簡単な説明】

第１図は、本発明の全体的ブロック図である。 第２Ａ図は、ローカル分岐履歴テーブルの大きさに応じ
た分岐アドレスの論理的区分けを示す図である。 第２Ｂ図は、広帯域分岐履歴テーブルの大きさに応じた
分岐アドレスの論理的区分けを示す図である。 第３図は、事前取出し機構の構成図である。 第４図は、分岐の指示を伴うキャッシュ行の概略図であ
る。 第５図は、第５Ａ図と第５Ｂ図の結合様式を示す図であ
り、第５Ａ図と第５Ｂ図は、実行中に分岐命令に出会う
ごとに分岐命令相互間の対応関係を確立する回路を示す
図である。 第６図は、キャッシュ行中の分岐をカウントする回路の
図である。 第７図は、以上（≧）デコーダの図である。 第８図は、第８Ａ図と第８Ｂ図の結合様式を示す図であ
り、第８Ａ図と第８Ｂ図は、マツプ・テーブルに対応関
係を入力する回路の図である。 第９図は、テーブルの実施態様の図である。 第１０図は、最小最大回路の図である。 １０・・・・プロセッサ、１１・・・・命令ハ、ソファ
、１２・・・・キャッシュ、１３・・・・メモリ、１４
・・・・バッファ取出しアドレス・レジスタ、１５・・
・・ローカルＢＩＴ　（分岐履歴テーブル）、２０・・
・・次行アドレス・レジスタ、２１・・・・広帯域ＢＩ
Ｔ、２２・・・・事前取出し機構。 出願人　　インターナショナル・ビジネス・マシーンズ
優コーポレーション 代理人　　弁理士　　頓　　宮　　孝　　−（外１名） 〜　　　　　　　　　　　の

Claims (1)

1. 【特許請求の範囲】 メモリとデータ行についての一時高速記憶を提供するキ
   ャッシュとを有するコンピュータにおいて、前記データ
   行を前記メモリから前記キャッシュへ事前取出しする命
   令事前取出し装置であって、前記データ行のアドレスを
   生成する手段と、分岐に関する項目を記憶して提供する
   広帯域分岐履歴テーブル手段と、 前記広帯域分岐履歴テーブル手段によって提供される前
   記項目を受け取って前記キャッシュからの命令の取出し
   を制御するローカル分岐履歴テーブル手段と、 次データ行アドレスを計算して、前記次データ行アドレ
   スにより指示される次データ行が前記キャッシュに記憶
   されていないなら、前記次データ行を前記メモリから前
   記キャッシュへ事前取出しする事前取出し手段と、 を備えた前記装置。