JPS635777B2 - - Google Patents

Description

請求の範囲 １ プログラムとして構成される複数個のインス
トラクシヨンをストアするためのメモリ手段を備
え、 前記プログラムは、検査されるべき条件を特定
する前記プログラムのそれぞれのロケーシヨンに
おける条件付ブランチインストラクシヨンを含
み、 パイプライン化された態様で同時に前記プログ
ラムの異なるインストラクシヨンをそれぞれ取出
しかつ実行するためのインストラクシヨン先取り
手段およびインストラクシヨン実行手段をさらに
備え、 前記ロケーシヨンの各々における前記条件付ブ
ランチインストラクシヨンはさらに、検査される
べき条件の状態を予測する多数のエンコーデイン
グを有し、 前記先取り手段が前記条件付ブランチインスト
ラクシヨンの１個を取出したときを検出しかつ前
記取出された条件付ブランチインストラクシヨン
においてエンコードされた検査されるべき条件の
予測された状態に基づき次のインストラクシヨン
を取出す制御手段と、 前記取出された条件付ブランチインストラクシ
ヨンの前記エンコーデイングをそのメモリロケー
シヨンにおいて予め定められる態様で変化させ
て、前記条件の予測された状態がそのインストラ
クシヨンが実行されるときの前記条件の実際の状
態と等しかつたか否かを示すための書込手段とを
さらに備え、 前記書込手段は、前記取出された条件付ブラン
チインストラクシヨンが実行された最後の２回に
わたつて前記予測された状態が前記条件の実際の
状態と等しくなかつたときに、前記取出された条
件付ブランチインストラクシヨンへエンコードさ
れる前記条件の予測された状態を変化させる、改
良されたデイジタル装置。 ２ プログラムとして構成される複数個のインス
トラクシヨンをストアするためのメモリ手段を備
え、 前記プログラムにおけるあるロケーシヨンにお
ける条件付ブランチインストラクシヨンは、検査
されるべき条件を特定し、前記条件のある状態を
予測し、かつ前記あるロケーシヨンにおける前記
インストラクシヨンが最後に実行されたときに前
記予測された状態が前記条件の実際の状態に等し
かつたことを示す第１のエンコーデイングを有
し、かつ 前記プログラムにおける他のロケーシヨンにお
ける他の条件付ブランチインストラクシヨンは、
検査されるべき同じ条件を特定し、前記条件の前
記同じ状態を予測するが、前記他のロケーシヨン
の前記インストラクシヨンが最後に実行されたと
きに前記予測された状態が前記条件の実際の状態
に等しくなかつたことを示す第２のエンコーデイ
ングを有し、 条件付ブランチインストラクシヨンの前記エン
コーデイングを、そのインストラクシヨンが実行
されるときに、そのメモリロケーシヨンにおいて
変化させて、前記予測された状態が前記命令の実
行期間中に前記条件の実際の状態と等しかつたか
または等しくなかつたかを示すための書込手段を
さらに備え、 前記書込手段は、１つの行において２回にわた
つて、予測された状態が前記条件の実際の状態と
マツチしないときに、前記取出された条件付ブラ
ンチインストラクシヨンへエンコードされる前記
条件の予測された状態を変化させる、プログラマ
ブルデイジタル装置。 ３ プログラムとして構成された複数個のインス
トラクシヨンをストアするためのメモリ手段を備
え、 前記インストラクシヨンの少なくとも１つは、
検査されるべき条件を特定する条件付ブランチイ
ンストラクシヨンであり、 前記条件付ブランチインストラクシヨンは、前
記条件の第１の状態をそれぞれ予測する１個以上
のエンコーデイングを有し、かつ、条件の第２の
状態をそれぞれ予測する１個以上のエンコーデイ
ングを有し、かつ 前記複数のエンコーデイングはまた、前記条件
の前記予測された状態が、前記条件付ブランチイ
ンストラクシヨンの前の実行の間に前記条件の実
際の状態といかに比較されたかのヒストリを与
え、 前記条件付ブランチインストラクシヨンの前記
エンコーデイングをそのメモリロケーシヨンにお
いて予め定める態様で変化させて、そのインスト
ラクシヨンが実行されるごとに前記条件の予測さ
れた状態が前記条件の実際の状態に等しかつたか
否かを示し、かつ予測された状態が、前記条件付
ブランチインストラクシヨンが実行された最後の
２回前記条件の実際の状態とマツチしなかつたと
きに、前記条件付ブランチインストラクシヨンへ
エンコードされる前記条件の予測された状態を変
化させる書込手段をさらに備える、プログラマブ
ルデイジタル装置。 ４ 前記条件付ブランチインストラクシヨンは４
つのエンコーデイングを有しており、前記４つの
エンコーデイングは、それぞれ、前記条件に対す
る真の状態を予測しかつ最後の予測が正しかつた
ことを示し、前記条件の真の状態を予測しかつ最
後の予測が誤りであつたことを示し、前記条件に
対する偽の状態を予測しかつ最後の予測が正しか
つたことを示し、さらに前記条件に対する偽の状
態を予測しかつ最後の予測が誤りであつたことを
示す、請求の範囲第３項記載の装置。 発明の背景 この発明はデイジタルコンピユータのアーキテ
クチヤに関するものであり、より特定的には、こ
の発明はパイプライン態様で同時にいくつかの異
なるインストラクシヨンで作動するデイジタルコ
ンピユータのアーキテクチヤに関するものであ
る。 この発明をより良く理解するために、パイプラ
イン化したデイジタルコンピユータの基本モジユ
ールを図解した第１図を参照する。この第１図の
コンピユータはインストラクシヨン先取モジユー
ル（IPF），実行モジユール（EX）、およびメモ
リモジユール（Ｍ）を含む。さらに、実行モジユ
ールはアドレスモジユール(A)、オペランドモジユ
ール（Ｏ）、および計算モジユール(C)を含む。 モジユールIPF，Ａ，ＯおよびＣは同時にプロ
グラムの異なるインストラクシヨンで作動する。
そのプログラムにおけるインストラクシヨンのす
べてはメモリモジユールＭにストアされる。モジ
ユールIPFはメモリモジユールＭからのインスト
ラクシヨンを取出す働きをし、モジユールＡはイ
ンストラクシヨンにおいて要求されるオペランド
のアドレスを形成する働きをし、モジユールＯは
モジユールＡによつて形成されるアドレスである
オペランドを取出し、かつモジユールＣはモジユ
ールＯにより取出されたオペランドについて計算
し、メモリモジユールＭにその結果をストアする
働きをする。 任意の１個のモジユールが上述した機能を行な
つた後、そのモジユールはその結果を次のモジユ
ールへ通す。その次のモジユールは、次いで、そ
の上述の機能を行ない、新しい結果を次のモジユ
ールへ通す。このように、モジユールIPF，Ａ，
ＯおよびＣはインストラクシヨンが通過する“パ
イプライン”を形成し、かつバス１０，１１およ
び１２はそのモジユールがそれらの結果をパイプ
ラインを介して次のモジユールへ通過させる手段
を与える。 バス１３，１４，１５および１６はまた、モジ
ユールIPF，Ａ，ＯおよびＣがそれぞれ、それら
の上述の機能を行ないながらメモリモジユールへ
情報の種々のアイテムを読出しおよび／または書
込む手段として提供される。たとえば、モジユー
ルIPFはメモリからインストラクシヨンを取出す
ためにバス１３を用い、モジユールＡはオペラン
ドアドレスを形成するために必要とされるメモリ
からインデツクスレジスタを取出すためにバス１
４を用い、モジユールＯはバス１５を用いてモジ
ユールＡによつて形成されるアドレスでメモリか
らオペランドを取出し、かつモジユールＣはバス
１６を用いて計算された結果をメモリへ戻してス
トアする。 第２図は、第１図のコンピユータが９個のイン
ストラクシヨンＩ１ないしＩ９からなるプログラ
ムを実行するシーケンスをより詳細に示す。これ
らのインストラクシヨンはメモリＭに存在するも
のとして第１図に図解される。インストラクシヨ
ンＩ１ないしＩ９は逐次的にメモリで互いに続
き、かつインストラクシヨンＩ５は条件付きブラ
ンチインストラクシヨンである。それは条件を検
査し、その条件が真であればインストラクシヨン
Ｉ１へ戻るように分岐、その条件が偽であればイ
ンストラクシヨンＩ６へ分岐する。 条件付きブランチインストラクシヨンのための
典型的なフオーマツトは参照数字１７で示すよう
な、OPコード（OP）およびブランチアドレス
（BA）からなる。OPコードOPは条件付きブラン
チであるものとしてインストラクシヨンを識別し
かつ検査されるべき条件を識別する１および０の
１個の予め割当てられた組合わせである。たとえ
ば、バロースB4800コンピユータの２進化10進22
は等しい場合のブランチを特定し、それに対し２
進化10進25は等しくない場合のブランチを特定す
る。BAは特定した条件が真であれば次に実行さ
れるべきインストラクシヨンのメモリモジユール
Ｍにおけるアドレスである。 第２図のサイクル１の間、モジユールIPFはイ
ンストラクシヨンＩ１を取出す。その後、サイク
ル２の間、モジユールＡはインストラクシヨンＩ
１によつて必要とされるオペランドのアドレスを
形成し、他方、モジユールIPFは同時にインスト
ラクシヨンＩ２を取出す。この動作シーケンスは
条件付きブランチインストラクシヨンＩ５がモジ
ユールIPFによつて取出されるサイクル５を通じ
て、第２図に示されるようなパイプライン化され
た態様で続く。 条件付きブランチインストラクシヨンＩ５を取
出した後、モジユールIPFは次のインストラクシ
ヨンとしてインストラクシヨンＩ１またはインス
トラクシヨンＩ６を取出すべきかどうかを決定す
る必要がある。もしインストラクシヨンＩ５によ
つて検査されるべき条件がそのインストラクシヨ
ンがモジユールIPFによつて取出された後すぐに
テストする状態であればこれは何ら問題はない。
しかし、その条件が先行するインストラクシヨン
Ｉ４によつて変化されることができ、そのためそ
の条件はインストラクシヨンＩ４がパイプライン
の最終モジユールＣにより行なわれるまで検査の
ためには利用できないであろう。これは、第２図
に示すように、サイクル７が終るときに生じる。 実際の条件自体はちようど１ビツトであつても
よく、または全計算シーケンスの結果であつても
よい。たとえば、IBM360コンピユータおよび
IBM370コンピユータは“条件コード”と呼ばれ
るフリツプフロツプの組を含み、かつコンピユー
タがテストし得る各可能な条件は条件コードのフ
リツプフロツプにストアされる。条件コードのう
ちの１個が“イコール”であり、かつコンピユー
タが演算インストラクシヨンを行なつた直後に自
動的に“１”にセツトされまたは“０”にリセツ
トされる。 いくつかの先行技術におけるパイプライン化さ
れたコンピユータにおいてモジユールIPFは常に
ブランチアドレスBAでインストラクシヨンを取
出し、続いて条件付きブランチインストラクシヨ
ンを取出す。この動作が第２図のサイクル６に示
されており、インストラクシヨンＩ１はモジユー
ルIPFによつて取出される。その後で、サイクル
７および８において、インストラクシヨンＩ２お
よびＩ３はそれぞれモジユールIPFによつて取出
される。次に、サイクル８で、モジユールＣはイ
ンストラクシヨンＩ５によつて特定される条件が
インストラクシヨンＩ１，Ｉ２，およびＩ３がサ
イクル６，７および８の間モジユールIPFによつ
て取出されるべきであつたようなものであつたか
どうかを決定する。 インストラクシヨンＩ６が代わりに取出される
べきであつたならば、そのことがモジユールＣに
よつて、制御ライン１８を介してモジユール
IPF，ＡおよびＯへ信号で知らされる。この信号
に応答し、モジユールIPFはそれぞれサイクル
９，１０および１１の間インストラクシヨンＩ
６，Ｉ７およびＩ８を取出し、かつモジユール
Ａ，ＯおよびＣはインストラクシヨンＩ１，Ｉ２
およびＩ３で任意のさらに他の動作より先んず
る。 しかしながら、多数のサイクルは役に立たない
動作を行なうので多くのサイクルが無駄であると
いう問題がこのシーケンスの動作にはある。上述
の例において、モジユールIPFはサイクル６ない
し８を無駄にする。典型的には、プログラムは数
千の条件付きブランチインストラクシヨンを含
み、かつこれらの無駄になつたサイクルはコンピ
ユータのスループツトを意義深く減少させる。 これらの無駄になつたサイクルの数を減少させ
る１つの方法は、コンピユータがテストし得る条
件ごとに条件付き予測子フリツプフロツプを付加
することである。たとえば、１個の条件付き予測
子フリツプフロツプは等しい場合のブランチ
（branch−if−equal）インストラクシヨンによつ
て検査される“イコール”条件のために付け加え
られることができ、かつそのフリツプフロツプは
それが検査された最後の数回にわたりその条件の
実際の状態に基づき、“イコール”条件のために
真または偽の予測した状態を示すであろう。次
に、条件付きブランチインストラクシヨンがモジ
ユールIPFにより見つけられると、次のインスト
ラクシヨンが、条件予測子フリツプフロツプにス
トアされ検査されている条件の予測した状態に基
づき取出される。 しかしこの機構はなおも数多くのサイクルを無
駄にする。その理由は第３図を観察することによ
つてわかる。そこには、インストラクシヨンＩ１
０ないしＩ２３からなるプログラムが図解されて
おり、インストラクシヨンＩ１４およびＩ１６は
条件付きブランチインストラクシヨンである。 インストラクシヨンＩ１４からインストラクシ
ヨンＩ２０へのブランチはあまり頻繁に行なわれ
ないものとし、それに対しインストラクシヨンＩ
１６からＩ１０へのブランチは非常に頻繁に行な
われるものと想定する。これは非常に実用的な可
能性である。なぜならばインストラクシヨンＩ１
３はインストラクシヨンＩ１４が検査する例外条
件のための比較を行なつており、かつインストラ
クシヨンＩ１５はインストラクシヨンループＩ１
０−Ｉ１６が繰返されるべきであるかどうかを示
すための“イコール”条件をセツトまたはリセツ
トしているからである。 このように、条件付きブランチインストラクシ
ヨンＩ１６による第３図のプログラムにおける無
駄なサイクルを最小にするために、予測した“イ
コール”条件は真であるべきである。しかし、同
時に、条件付きブランチインストラクシヨンＩ１
４による無駄なサイクルを最小にするために、予
測したイコール条件は偽でなければならない。こ
のように、条件の１個の予測した状態が、プログ
ラムにおける或る場所での条件付きブランチイン
ストラクシヨンにより生じる無駄なサイクルを最
小にする一方で、プログラムにおける他の場所で
の条件付きブランチインストラクシヨンにより生
じる無駄なサイクルを最大にするというジレンマ
がある。 このジレンマは条件予測子フリツプフロツプの
ための１つの状態を選択することによつて、かつ
次にその１個の予測した状態が常に正しい予測で
あるようにプログラムを再構成することによつて
表面上は避けられるかもしれない。たとえば、条
件予測子フリツプフロツプは、“イコール”条件
が偽であり、“ノツトイコール”条件が真である
ということを示すものと想定する。次に、条件付
きブランチインストラクシヨンＩ１４は“イコー
ルでない場合のブランチ（branch−if−not−
equal）”インストラクシヨンに変えられ、インス
トラクシヨンＩ２０−Ｉ２３が直接インストラク
シヨンＩ１４に続くメモリロケーシヨンへ移動さ
れ、かつインストラクシヨンＩ１５−Ｉ１９はＩ
１４から遠く隔たつたいくつかのメモリロケーシ
ヨンへ移動されるものと想定する。これらの変化
では、比較的高速なブランチは、インストラクシ
ヨンＩ１４から遠く隔たつたその新しいロケーシ
ヨンでインストラクシヨンＩ１４からインストラ
クシヨンＩ１５へ生じ、かつ前に説明したよう
に、インストラクシヨンＩ１６からインストラク
シヨンＩ１０への比較的高速なブランチが生じ
る。 しかし、インストラクシヨンのこのような構成
は、プログラム（図示せず）の多くの他の部分に
よつて用いられるサブルーチンをインストラクシ
ヨンＩ２０−Ｉ２３が形成するような状況に対し
てはメモリスペースを非常に浪費する。その場
合、それが実行速度を増大するために上述したよ
うに用いられるたびごとにＩ２０−Ｉ２３コード
を繰返す必要があろう。そして、長いまたはしば
しば用いられサブルーチンのためのコードは繰返
しは非実用的なほどに多くのメモリを用いる。さ
らに、そのようなタスクは非常に莫大なもので時
間がかかるので実行時間を増大するために上述し
た態様で数千およびさらには数百万ものインスト
ラクシヨンを含む予め存在するプログラムを再構
成するというのは非実用的である。 したがつて、この発明の主たる目的は先行技術
についての上述した無駄なサイクルが実質的に最
小化されるパイプライン化された形式で同時にプ
ログラムのいくつかのインストラクシヨンを実行
するデイジタルコンピユータを提供することであ
る。 この発明の他の目的は、条件付ブランチインス
トラクシヨンの分岐予測の修正が不必要な場合に
そのような修正が生じることを防止できるデイジ
タルコンピユータを提供することである。 発明の簡単な概要 この目的および他の目的はプログラムとして構
成される複数個のインストラクシヨンをストアす
るためのメモリ手段を提供することによつてこの
発明に従つて達成され、それらのインストラクシ
ヨンのいくつかは条件付きブランチインストラク
シヨンであり、各条件付きブランチインストラク
シヨンは条件を検査し、かつその条件の状態に基
づき１個のインストラクシヨンまたは他のインス
トラクシヨンへ分岐し、かつ各条件付きブランチ
インストラクシヨンはさらに、検査されるべき条
件の状態を予測する多数のエンコーデイングを有
し、各条件付ブランチインストラクシヨンはま
た、条件の予測した状態が、取出された条件付ブ
ランチインストラクシヨンの前の実行の間の条件
の実際の状態といかに比較されたかのヒストリを
与えるようにエンコードされる。

【図面の簡単な説明】

この発明の種々の特徴および利点は添付図面を
参照して詳細な説明において説明される。 第１図は先行技術の任意のパイプライン化され
たデイジタルコンピユータの基本的コンポーネン
トを示す。 第２図は第１図のパイプライン化されたデイジ
タルコンピユータの動作を示す。 第３図は第１図のパイプライン化されたデイジ
タルコンピユータにおいて無駄なサイクルを生じ
る１対の条件付きブランチインストラクシヨンを
有するプログラムを示す。 第４Ａ図および第４Ｂ図はこの発明により構成
されるパイプライン化されたデイジタルコンピユ
ータにおける無駄なサイクルを大幅に減少した２
個の条件付きブランチインストラクシヨンのエン
コーデイングを示す。 第５Ａ図および第５Ｂ図はこの発明により構成
されるパイプライン化されたデイジタルコンピユ
ータにおける無駄なサイクルを大幅に減少した２
個の条件付きブランチインストラクシヨンの他の
エンコーデイングを示す。 第６図はこの発明により構成されるデイジタル
コンピユータにより第５Ａ図および第５Ｂ図のイ
ンストラクシヨンのエンコーデイングが更新され
るシーケンスを示す状態図である。 第７図はこの発明により構成されるデイジタル
コンピユータの１つの好ましい実施例の詳細回路
を示す。

【発明の詳細な説明】

この発明の好ましい一実施例を第４Ａ図ないし
第５Ｂ図を参照して詳細に説明する。この実施例
において、複数個のインストラクシヨンはプログ
ラムとして構成されかつ条件付きブランチインス
トラクシヨンはそのプログラムにおけるいくつか
の場所に存在する。これらのいくつかの場所にお
ける各条件付きブランチインストラクシヨンは１
個の条件を検査する。しかし、各条件付きブラン
チインストラクシヨンはいくつかの可能なエンコ
ーデイングを有し、かつ各場所のエンコーデイン
グはその場所のブランチインストラクシヨンによ
り検査されるべき条件の状態を予測する。 たとえば、検査されている１つの条件がイコー
ル条件であるものと想定する。次に、この発明に
よるイコールインストラクシヨンについてのブラ
ンチの適当なエンコーデイングが第４Ａ図に示さ
れる。OPコードは16進Ａ２またはＢ２のいずれ
かとして与えられる。これらのエンコーデイング
の双方はイコール条件がテストされるべきである
ことを特定し、かつイコール条件が真であればア
ドレスBAのインストラクシヨンへ分岐が行なわ
れる。しかし、さらに、OPコードＡ２は、イコ
ール条件が検査されるときに真であろうというこ
とを予測するのに対し、OPコードＢ２はイコー
ル条件が検査されるときに偽であろうということ
を予測する。これらのOPコードはイコール条件
がそのロケーシヨンで検査されるときに最も真ま
たは偽になりそうであるかどうかということに基
づいて、ブランチまたはイコールインストラクシ
ヨンが生じる各ロケーシヨンでＡ２またはＢ２の
いずれかであるようにプログラムにおいて選択的
に構成されている。たとえば、第３図を参照する
とインストラクシヨンＩ１４によつて検査される
イコール条件はほとんど常に偽であると説明され
ており、そのためインストラクシヨンＩ１４の
OPコードはＢ２としてエンコードされる。逆に、
インストラクシヨンＩ１６によつて検査されるイ
コール条件はほとんど常に真であると説明された
ので、インストラクシヨンＩ１６のOPコードは
Ａ２としてエンコードされよう。 そこで、この発明によれば、インストラクシヨ
ン先取モジユールはインストラクシヨンＩ１４お
よびＩ１６を取出すと、これらのインストラクシ
ヨンへエンコードされる予測された条件を検出
し、それらの予測に基づいて次のインストラクシ
ヨンを取出す。これは、順次、第２図および第３
図を参照して議論した非常に多くの無駄なサイク
ルを除去する。なぜならば、この発明において、
条件の予測した状態はその条件を検査するインス
トラクシヨンの場所に相関し、その条件自体に単
純に相関しない。 ノツトイコール条件を検査する条件付きブラン
チインストラクシヨンのための同様なエンコーデ
イングを第４Ｂ図に示す。そこでは、16進OPコ
ードＡ５およびＢ５はともに、ノツトイコール条
件が検査されるべきであり、ノツトイコール条件
が真であればロケーシヨンBAのインストラクシ
ヨンへ分岐すべきであるということを特定する。
しかし、さらに、エンコーデイングＡ５はノツト
イコール条件が真であろうということを予測し、
かつエンコーデイングＢ５はノツトイコール条件
が偽であろうということを予測する。そのため、
たとえば、第３図のプログラムのインストラクシ
ヨンＩ１４がノツトイコール条件を検査し、その
条件の最も起こりそうな状態がそのロケーシヨン
で検査されるときに真であつたならば、インスト
ラクシヨンＩ１２はＡ５のエンコーデイングを有
するであろう。 この発明の他の実施例によれば、条件付きブラ
ンチインストラクシヨンは検査されるべき条件の
状態を予測するのみならずそれが過去において検
査されたときにその条件の実際の状態の歴史を与
えるために、プログラムのそれぞれのロケーシヨ
ンでさらにエンコードされる。このエンコーデイ
ングの２個の例を第５Ａ図および第５Ｂ図に示
す。 第５Ａ図において、イコールのときのブランチ
（branch on equal）インストラクシヨンは４個
のOPコードＡ２，Ｂ２，Ｃ２またはＤ２によつ
て特定される。エンコーデイングＡ２およびＣ２
はともに、イコール条件が真であろうということ
を予測し、エンコーデイングＢ２およびＤ２はと
もにイコール条件が偽であろうということを予測
する。しかし、さらに、エンコーデイングＡ２お
よびＢ２は、イコール条件は、それがこのインス
トラクシヨンによつて検査された最後のときに真
であつた、ということを伝える。OPコードＣ２
およびＤ２は、比較的には、このインストラクシ
ヨンがイコール条件を検査した最後のときにそれ
が偽であつたということを伝える。 イコールでないときのブランチ（branch on
not equal）インストラクシヨンのための同様な
エンコーデイングが第５Ｂ図に与えられる。そこ
では、OPコードＡ５，Ｂ５，Ｃ５およびＤ５は
各々検査を特定しノツトイコール条件で分岐す
る。OPコードＡ５およびＣ５はノツトイコール
条件の真の状態を予測し、かつOPコードＢ５お
よびＤ５はノツトイコール条件の偽の状態を予測
する。さらにOPコードＡ５およびＢ５はノツト
イコール条件が、それがこのインストラクシヨン
によつて検査された最後のときに真であつたとい
うことを伝え、かつOPコードＣ５およびＤ５は
ノツトイコール条件がこのインストラクシヨンに
よつて検査された最後のときに偽であつたという
ことを伝える。 第５Ａ図および第５Ｂ図のインストラクシヨン
は検査された条件の最終状態をエンコードするの
で、そのエンコーデイングはそのインストラクシ
ヨンが実行される時間とともに更新されなければ
ならない。この更新は第６図の状態図によつて示
されるシーケンスにおいて行なわれる。この図は
PT／LT，PT／LF，PF／LF，およびPF／LT
として示される４個の可能な状態を含む。 状態PT／LTは、考察されているインストラク
シヨンが検査されるべき条件のための真の状態を
予測し、かつそのインストラクシヨンが実行され
た最後のときに真の条件に遭遇したということを
意味する。これは、イコールのときのブランチイ
ンストラクシヨンのためのＡ２のエンコーデイン
グおよびイコールでないときのブランチインスト
ラクシヨンのためのＡ５のエンコーデイングに対
応する。同様に、状態PF／LFは、考察されてい
るブランチインストラクシヨンは検査されるべき
条件のための偽の状態を予測し、かつそのインス
トラクシヨンが実行されている最後のときに偽の
条件に遭遇したということを意味する。 プログラムの特定のロケーシヨンにおけるイン
ストラクシヨンは状態PT／LTに対応するエンコ
ーデイングを有するものと想定する。次に、その
インストラクシヨンが実行されるとき、検査され
た条件の実際の状態が真であればそのエンコーデ
イングは変わらないままである。しかしながら、
検査された条件の実際の状態が偽であれば、その
インストラクシヨンのエンコーデイングは状態
PT／LFに対応するように変えられる。 次にそこでエンコードされた状態PT／LFを有
するインストラクシヨンが実行されるものと想定
する。次に、検査された条件が真であれば、その
インストラクシヨンのエンコーデイングはPT／
LFからPT／LTまで変えられる。しかし、検査
された条件が偽であれば、そのインストラクシヨ
ンのエンコーデイングはPT／LFからPF／LFへ
変わる。 換言すれば、条件の予測した状態は、２個の間
違つた予測が行において生じるまで変えられな
い。そして、条件付きブランチインストラクシヨ
ンが第３図のインストラクシヨンＩ１６のよう
に、プログラムループの底部で共通に配置される
ので、このことは望ましい。通常、ブランチは、
何度も一方方向に行なわれ、かつ１回だけ他方方
向に行なわれる。しかし、ブランチがその他方方
向に行なわれるとき、予測した条件は不変でなけ
ればならず、そのためループが入れられた次のと
きに、共通な一方方向のブランチが再び予測され
よう。第４Ａ図ないし第６図のインストラクシヨ
ンを実行するパイプライン化したデイジタルコン
ピユータのハードウエアの１つの好ましい実施例
が図解される第７図を次に参照する。そのハード
ウエアはインストラクシヨン先取ステージIPF′、
アドレスステージA′、オペランドステージO′お
よび計算ステージC′を含む。これらのステージは
第１図の先行技術のステージIPF，AO，および
Ｃにより前に行なわれたすべて機能を行なう。し
かし、それらはまたこれから説明するような態様
で第４Ａ図ないし第６図の条件付きブランチイン
ストラクシヨンで作動するための付加的な回路を
含む。 まず最初に、モジユールIPF′はメモリバス３
０を介してメモリ（図示せず）のプログラムから
インストラクシヨンを取出す。導体３０Ａはイン
ストラクシヨンのアドレスをメモリへ送るための
手段を与え、かつ導体３０Ｂは読出指令をメモリ
へ送るための手段を与える。 各々取出されたインストラクシヨンは導体３０
Ｃ上でメモリから受けられ、かつそこから、それ
はレジスタ３１にストアされる。そのレジスタは
導体３２を介して制御回路３３へ送られるOPコ
ード部分を有する。順次、回路３３は条件付きブ
ランチインストラクシヨンが、第４Ａ図−第５Ｂ
図の前述したOPコードをデコードすることによ
つてレジスタ３１にあるときを検出する。 レジスタ３１のインストラクシヨンは、検査さ
れるべき条件の真の状態を予測する条件付きブラ
ンチインストラクシヨンであれば、回路３３はリ
ード３４で制御信号PTを発生する。逆に、条件
付きブランチインストラクシヨンが検査されるべ
条件の偽の状態を予測するレジスタ３１にあれ
ば、回路３３はリード３５で他の制御信号PFを
発生する。 信号PTおよびPFはインストラクシヨン取出回
路３６へ送られる。信号PTに応答して、回路３
６はFIFOバツフア３７へ、レジスタ３１のブラ
ンチインストラクシヨンのアドレスを転送する。
そのアドレスはプログラムカウンタ３８にあり、
かつそのため回路３６はマルチプレクサ４０を介
してFIFO３７へプログラムカウンタ３８を通過
させる導体３９に信号を発生する。FIFO３７の
実際のロードはリード線４１の回路３６によつて
発生される書込信号に応答して行なわれる。 その後で、回路３６はブランチアドレスBAを
レジスタ３１からプログラムカウンタ３８へ転送
する。それは、プログラムカウンタをロードする
状態４４上のロード信号を同時に発生しながら、
マルチプレクサ４３を介してアドレスBAを通過
させるリード線４２上の制御信号を発生させこと
によつて行なわれる。次に、プログラムカウンタ
３８の新しい内容は後続のインストラクシヨンを
取出すため導体３０Ａを介して送られる。 逆に、信号PFが真であれば、回路３６はFIFO
３７にブランチアドレスBAをストアする。これ
は、マルチプレクサ４０を介してアドレスBAを
通過させる導体３９に他の制御信号を送り、かつ
同時に書込信号を導体４１でFIFOへ送ることに
よつて達成される。その後で後続のインストラク
シヨンが、プログラムカウンタの古い内容をイン
クリメントすることによつてかつその結果を用い
て導体３０Ａを介してそのメモリをアドレスする
ことによつて取出される。 各モジユールが特定のインストラクシヨンでそ
の動作を完了された後、第１図に関して前述した
ように、それはその結果を次のモジユールへ通過
させる。これを発生するために、バス４５，４６
および４７は種々のモジユール間で与えられる。
しかし、第７図の実施例はレジスタ３１のインス
トラクシヨンのアドレスを一方のモジユールから
他のモジユールへ、バス４５，４６および４７上
で従来から通されている情報とともに、通過させ
るための手段としてのモジユール端にバス４２，
４８，４９および５０を含む。 レジスタ５１はバス４８上でそれが受けるアド
レスを一時的に記憶するためモジユールA′に設
けられる。同様にレジスタ５２および５３は先行
するモジユールからそれらが受けるアドレスを一
時的に記憶するためモジユールO′およびC′にそれ
ぞれ設けられる。モジユールC′は以下のようにそ
のレジスタ５３のアドレスを利用する。 バス４７上でモジユールC′へ通されるこれらの
結果はモジユールC′が動作すべきインストラクシ
ヨンのOPコードを含む。このOPコードはレジス
タ５４にストアされかつそこから、OPコードは
制御回路５５および５６ならびにマルチプレクサ
５７へ送られる。回路５５は、レジスタ５４のイ
ンストラクシヨンが、そのインストラクシヨンが
実行された最後のときにその条件が真であつたと
いうことを示すエンコーデイングを備えた条件付
きブランチインストラクシヨンであれば導体５８
に信号LTを発生する。また、回路５５は、レジ
スタ５４のインストラクシヨンがそのインストラ
クシヨンが実行された最後のときに検査された条
件が偽であつたということを示すエンコーデイン
グを備えた条件付きブランチインストラクシヨン
であれば、導体５９に信号LFを発生する。 回路５６は、レジスタ５４のインストラクシヨ
ンが、検査された条件の状態が真であるというこ
とを予測する条件付きブランチインストラクシヨ
ンであれば、導体６０に信号PTを発生する。そ
して、回路５６は、レジスタ５４のインストラク
シヨンが、検査された条件の状態が偽であるとい
うことを予測する条件付きブランチインストラク
シヨンであれば導体６１に信号PFを発生する。 マルチプレクサ５７は検査され得る条件のすべ
てを受け、かつそれは導体６２に対し検査される
べきその１個の条件をゲート処理することによつ
てレジスタ５４のOPコードに応答する。導体５
８−６２のすべての信号は、書込制御回路６３へ
送られ、この回路６３は第６図に関して前述した
態様でレジスタ５３に保持されるアドレスでその
インストラクシヨンのエンコーデイングを修正す
るように作動する。 たとえば、リード線５０−６１上の信号は、条
件付きブランチインストラクシヨンがPF／LT状
態に対応するエンコーデイングでレジスタ５２に
あつたということを表示するものと想定する。さ
らに、リード線６２上の信号は検査された条件の
現在の状態が真であることを示すものと想定す
る。その場合、書込制御回路６３はPT／LT状態
に対応してリード線６４Ａにエンコーデイングを
発生しかつ導体６４Ｂを介して書込指令を送るよ
うに動作する。その情報は、それが導体６４Ｃの
アドレスによつて特定されるロケーシヨンでメモ
リに書込まれる場合に、そのメモリへバス６４を
介して送られる。 上の例では、検査されるべき条件の予測した状
態と実際の状態とが同じであり、そのため何のセ
ツト信号もパイプラインの先行するステージへ送
られる必要がなかつた。しかし、リード線６２の
信号が、検査されるべき条件の実際の状態が偽で
あるということを示すものと想定する。この場
合、書込制御回路６３はPF／LF状態に対応する
リード線６４Ａに信号を発生し、導体６４Ｂに書
込指令を送り、かつ導体６５にリセツト信号を発
生する。 そのリセツト信号に応答し、モジユール
IPF′の取出回路３６はFIFO３７の出力をプログ
ラムカウンタ３８へ転送する。これは、マルチプ
レクサ４３を介してFIFO３７の出力を通過させ
る導体４２に信号を発生させることによつて、か
つ導体４４上のプログラムカウンタのためのロー
ド信号を同時に発生させることによつて達成され
る。その後、回路３６は導体６６上の信号を
FIFO３７へ送り、かつプログラムカウンタの新
しい内容が用いられてそのメモリからインストラ
クシヨンを取出す。 この発明の種々の好ましい実施例を詳細に説明
した。しかしながら、さらに、多くの変形および
修正がこの発明の性質および精神から逸脱するこ
となくこれらの詳細に対してなされ得る。たとえ
ば、この発明により構成される任意のパイプライ
ン化されたデイジタルコンピユータにおけるステ
ージの数は重要でないということを理解すべきで
ある。すなわち、コンピユータは１個のインスト
ラクシヨンで動作するインストラクシヨン先取ス
テージおよび他のインストラクシヨンで同時に作
動する実行ステージを有する必要があるだけであ
る。そして、実行ステージはモジユールA′，
O′およびC′のような他のステージへさらに区分化
されてもよく区分化されなくてもよい。 また、第７図に説明された種々の回路コンポー
ネントの詳細なインプリメンテーシヨンも関係が
ないということを理解すべきである。たとえば、
モジユールIPF′の取出回路３６およびモジユー
ルC′の書込制御回路６３は回路設計者の最良で任
意の数の方法で実現されてもよい。任意の半導体
販売者により販売される標準的な論理ゲートかま
たは１個の半導体チツプ上の１個のカスタム集積
回路がたとえば用いられてもよい。 さらに、検査されるべき条件のヒストリがない
ということを除きその条件の予測した状態のみが
条件付きブランチインストラクシヨンへエンコー
ドされれば、第７図の回路のいくつかが除去され
ることができるということを理解すべきである。
たとえば、条件付きブランチインストラクシヨン
が第４Ａ図および第４Ｂ図についてエンコードさ
れれば、レジスタ５１−５３，制御回路５５，お
よび制御回路５５に応答する書込制御回路６３の
部分は除去されることができる。 さらに、検査されるべき条件の予測した状態お
よび／またはその条件の最終状態は数多くの異な
る方法で条件付きブランチインストラクシヨンへ
エンコードされることができるということが理解
されるべきである。特に、その情報をインストラ
クシヨンのOPコードへエンコードする必要がな
い。代わりに、その情報はブランチアドレスBA
の任意の使用しないビツト組合わせへエンコード
されることができる。たとえば、ブランチアドレ
スが２進化10進であれば、そのアドレスの用いら
れない16進組合わせが用いられてブランチ予測お
よびブランチヒストリ情報をエンコードすること
ができる。 さらに他の代替例として、この発明はちようど
１個の条件付きブランチインストラクシヨンを含
むプログラムを実行する任意のデイジタル装置へ
併用されてもよいということを理解すべきであ
る。たとえば、１個の条件付きブランチインスト
ラクシヨンは、レジスタの内容を連続的に更新
し、次いでそのレジスタの内容を検査するプログ
ラムループにあるものと想定する。さらに、レジ
スタへ進む更新された情報が、検査条件が常にそ
のループを介して最初の100回の間常に偽であり、
検査条件が常に負のループを介して次の100回の
間真であるようなものと想定する。明らかに、第
６図に関して説明したこの発明の実施例はそのプ
ログラムループのデイジタル装置の実行を意義深
く改良する。 したがつて、多くの変形および修正がこの発明
の性質および範囲を逸脱することなく上述した詳
細に対してなされ得るので、この発明は前記詳細
に限られるものではなく、添付の請求の範囲によ
つて規定されるということを理解すべきである。