JPS623340A - 分岐方法 - Google Patents

分岐方法

Info

Publication number
JPS623340A
JPS623340A JP61147716A JP14771686A JPS623340A JP S623340 A JPS623340 A JP S623340A JP 61147716 A JP61147716 A JP 61147716A JP 14771686 A JP14771686 A JP 14771686A JP S623340 A JPS623340 A JP S623340A
Authority
JP
Japan
Prior art keywords
instruction
branch
executed
instructions
address
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP61147716A
Other languages
English (en)
Other versions
JP2518616B2 (ja
Inventor
Beiruu Rii Rubii
ルビイ・ベイルウ・リイ
Jiei Baumu Aren
アレン・ジエイ・バウム
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Hewlett Packard Japan Inc
Original Assignee
Yokogawa Hewlett Packard Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Yokogawa Hewlett Packard Ltd filed Critical Yokogawa Hewlett Packard Ltd
Publication of JPS623340A publication Critical patent/JPS623340A/ja
Application granted granted Critical
Publication of JP2518616B2 publication Critical patent/JP2518616B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3005—Arrangements for executing specific machine instructions to perform operations for flow control
    • G06F9/30069—Instruction skipping instructions, e.g. SKIP
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/30003—Arrangements for executing specific machine instructions
    • G06F9/3005—Arrangements for executing specific machine instructions to perform operations for flow control
    • G06F9/30058—Conditional branch instructions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G06F9/3846—Speculative instruction execution using static prediction, e.g. branch taken strategy
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3854—Instruction completion, e.g. retiring, committing or graduating
    • G06F9/3858—Result writeback, i.e. updating the architectural state or memory
    • G06F9/38585—Result writeback, i.e. updating the architectural state or memory with result invalidation, e.g. nullification

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Advance Control (AREA)
  • Devices For Executing Special Programs (AREA)

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は分岐による実行効率の低下の防止等に有効な分
岐方式に関する。
〔従来技術およびその問題点〕
条件付き分岐により判衛を行う能力はコンピュータ・シ
ステムが有用な仕事を行うには欠くことのできない条件
である。分岐するか分岐しないかの決定は一つあるいは
それ以上の事象に基いて行われる。
これらの事象は条件と呼ばれることが多いが、これらは
、正数であるか、負数であるかあるいはＯであるかとい
う条件や、最近行なわれた演算で、オーバフロー、アン
ダフロー、あるいはキャリーがあったか、あるいは偶奇
のパリティが合致したかあるいは、その他多くのものが
含まれている。条件付き分岐はディジタル・コンピュー
タでは条件付き分岐命令により行われる。条件付き分岐
命令はループや１ｆ−ｔｈｅｎ−ｅｌｓｅ構文のような
高水準プログラム構文を構成するのに使用される。ルー
プや１ｆ−ｔｈｅｎ−ｅｌｓｅ橘文は非常叫求メ礫肩を
本草良く使用されるため、これらを実行する条件付き分
岐命令はできるだけ効率的に実行することが肝要である
。
コンピュータの命令は一つあるいは複数のステップを履
むことによって実行される。代表的には、これらのステ
ップは、最初にプログラム・カウンタが指す命令をフェ
ッチし、次にその命令が指示する演算をデコードし実行
し、＆後に結果をしまい込む。
単純な分岐命令はプログラム内のどこかに「ジャン　　
　　　□・・プ」するためにプログラム・カウンタの内
容を変更する。コンピュータ命令の実行速度を上げるた
めに、パイプライン方式と呼ばれる、同時に複数の命令
を実行する手法が開発された。パイプライン方式では、
たとえば、ＣＰＵ　（中央処理装置）は１つの命令をフ
ェッチしながら同時に別の命令を実行し、且つ同時に第
３の命令の結果をしまい込むことができる。
パイプライン方式のコンピュータ・システムでは。
分岐は高くつく操作である。なんとなれば、分岐命令を
実行すると、その実行結果が確定するまで他の命令の実
行が一時的に止められることがあるからである。条件付
き分岐命令を実行したらその条件が成立したとする。こ
の場合、ＣＰＵは目標アドレスと呼ばれる新しいアドレ
スに制御を移しここから実行を継続する。命令のフェッ
チはパイプライン方式コンピュータ内では命令のデコー
ドおよび実行と同時に進行するので、この条件付き分岐
命令を実行している時にはコンピュータは既にプログラ
ム内の分岐命令に続く命令をフェッチしてしまっている
。これは目標アドレスにある命令とは違う命令である。
したがって、ＣＰＵは、分岐命令の実行結果がわかって
且つ正しい命令がフェッチされるまで、分岐命令に続く
命令パイプラインを一時に止めておかなければならない
。コンピュータのスループットを最大限にするために、
コンピュータの設計者は命令パイプラインを一時止める
必要を極力少なくしてスループットを最大にするように
コンピュータを設計しようとしてきた。
先行技術では、条件付き分岐で命令パイプラインの進行
を止めてしまわないように幾つかの機構を使用してきた
。第１に、ある種の高性能処理装置ではいろいろな分岐
予測機構を使用して条件付き分岐が成功するか失敗する
かを予測していた。この手法は広範なハードウェアが必
要になり、その広範なハードウェアの必要のため最高性
能コンピュータ以外では全く受は入れることができない
。他の構成では。
プログラム中で分岐命令に続くアドレスにある命令と分
岐目標アドレスにある命令との両者をフェッチする。こ
の手法は、これも高価なハードウェアと、条件付き分岐
命令の後では常に２組の命令をフェッチするための余分
なメモリアクセスとが必要であるため、受入れることは
できない。更に別の構成では、命令内に、分岐命令の後
のアドレス命令と分岐目標アドレスにある命令のいずれ
がより実行される可能性が高いかをコンピュータに知ら
せるビットを備えている。これによりコンピュータ笑は
より可能承港性の高い命令をフェッチし、その予測が外
れた場合にのみパイプラインを一時的に止める。この手
法は高価なハードウェアを必要とし、また予測が外れた
場合にはパイプラインを逆流させ、適切な命令をフェッ
チするのに余分な時間が消費される。更に別の構成では
１分岐が起るか起らないかに基いて、ＣＰＵに分岐命令
に続く命令を常に実行するかまたは決して実行しないか
を指示するために、命令中の２ビツトを用いている。こ
の構成は命令中のビットをあまりに多く使用しており、
分岐命令が分岐により到達できる最大範囲が狭くなる。
最後に、更に他の構成では、分岐を行うか行わないかに
かかｂらずその前に、プログラム中で次のアドレスにあ
る命令を常に実行している。
プログラム中で分岐命令に続くアドレスにある命令を実
行する技法は遅延分岐（ｄｅｌａｙｅｄｂｒａｎｃｈｉ
ｎｇ）として知られている。遅延分岐は、パイプライン
内の命令が常に実行されパイプラインが止まることがな
いので望ましい。これは遅延分岐を採用することにより
、コンピュータが分岐命令を実行する時間が与えられる
とともに、コンピュータはパイプライン内の命令を実行
しながら次の命令のアドレスを受は取ることができるか
らである。
この技法は命令パイプラインが止まることを回避しては
いるが、分岐命令の後に結局はＮＯＰ　（無動作命令）
を置くことが必要になることが多いこともよく知られて
いる。この場合には最終的には何の役にもたたない命令
のために命令フェッチを行なうことになり上述の遅延分
岐の効果が打消されるので、シ 性能の向上はならない。
遅延分岐の長所を活用する一つのソフトウェア技法とし
てマーシャ（ｍｅｒｇｅｒ）がある。マーシャは、ルー
プ分岐命令がループの終りにあるループ構造で用いられ
る。マーシャはループの最初の命令と同じ命令をループ
の分岐命令の次の命令位置に複製し、更Ｙに分岐の目標
アドレスをループの第２の命令とすることにより、遅延
分岐の長所を利用している。マーシャに関して起り得る
ーっの問題は、ループから脱出する際にはプログラムは
必らずしも遅延分岐命令をもう一度実行したい（つまり
分岐命令の次のアドレスの命令まで実行したい）とは思
わないということである。これは常に遅延分岐を行なう
アーキテ４チャで問題となる点である。
先行技術の多くのコンピュータ・システムでは、分岐を
まもなく実行すると判定すると、コンピュータ・システ
ムは命令パイプラインを一時的に止める。
すなわちインタロックする。パイプラインをインタロッ
クするとはコンピュータが次の命令をフェッチするのを
停止させ、またパイプラインがパイプライン内の命令の
実行に移らないようにすることが含まれる。インタロッ
クを行なうと、パイプライン方式により得られる性能向
上が減殺されるので、回避すべきである。
〔発明の目的〕
本発明は、ハードウェアの量と性能の低下を最少限にす
る分岐方式を提出することにある。この方式のために命
令中のビットはできる限り消費しないことが好ましい。
というのも、１ビツトが消費されれば分岐命令の最大分
＃ｗＭ囲は実際半分になってしまうからである。
〔発明の概要〕
本発明の好ましい実施例によれば、ディジタル・コンピ
ュータ内の分岐方式が提供される９本発明の好ましい実
施例では、分岐が起るか起らないかを分岐のディスプレ
ースソフトに基いて静的に予測する分岐命令が与えられ
る。この方式では可能な場合には遅延分岐を利用するが
、遅延スロットに置かれた命令を有効に利用できない場
合には分岐命令の後に続く遅延スロットにある命令の取
り消しくｎｕｌ−Ｌｉｆｉｃａｔｉｏｎ）　　を行う。
本発明型はいくつかの点で先行技術よりすぐれている。
第１に、本発明の好ましい実施例は分岐ディスプレース
ソフトの現行の符号ビットに基いて、命令内に他のビッ
トを設けることを必要とせずに、条件付きの分岐命令に
ついて条件の合致により分岐が成功する可能性の方が高
いかまたは分岐が失敗する可能性の方が高いのかを予測
することができる。第２に本発明の好ましい実施例では
、条件付きの分岐の直後に置かれている命令の使用が最
適化される。
これにより命令パイプラインの進行が一時的に止まる可
能性と、その結果化じる性能の低下とが少なくなる。第
３に、本発明の好Ｉましい実施例は命令を利用すること
ができない場合にのみ分岐の後に置かれメた命令を取り
消す（ｎｕｌｌｉｆ３／）。最後に。
本発明の好ましい実施例は通常の遅延分岐のように分岐
命令の後に置かれた命令を常に実行したり、あるいは通
常の分岐のように分岐命令の後に置かれた命令は、常に
実行されないというのではなく、分岐の方向に基いても
っと柔軟且つ効率的な取り消しを行なう。
〔発明の実施例〕
第２図は本発明の１１１ましい実施例による比較分岐命
令の命令フォーマットである。比較分岐命令５０１はコ
ンピュータが命令を実行するのに使用する３２ビツトの
情報から構成されている。この命令は分岐の機能と２つ
のオペランドを比較する動作とを組み合わせたものであ
るが、本発明は分岐だけの命令によっても同様によく実
現することができる。比較分岐命令５０１は６ビツトの
命令コード・フィールド５０２，５ビツトの第１ソース
・レジスタ・アドレス・フィールド５０３．５ビツトの
第２ソース・レジスタ・アドレス・フィールド５０４．
３ビツトの条件コード・フィールド５０５．１１ビツト
の分、゛ 岐ディスプレースソフト・フィールド５０６および、５
゛ １ビツトのディスプレースソフト・フィールド符号　　
　　　・・ビット５０８．および取り消しビット５０７
から成　　　　　令が比較分岐命令であることを識別す
る。第１およ　　　　　ヨ“′っている。命令コード・
フィールド５０２はこの命び第２のソース・レジスタ・
アドレス・フィールド５０３と５０４とはその内容が比
較されることになるレジスタを指示する。分岐ディスプ
レースソフトは、正でも負でもよいが、フィールド５０
８と５０　　　　　・１、ニ６により指示される。すな
おちフィールド５０８をフィールド５０６の最上位ビッ
トの左側に連結してできる数が通常の符号付き２進数で
表現されたディ　　　　　６゜スプレースソフトになる
。このディスブレースメン　　　　　、トは分岐の目標
アドレスを計算するのに使用される。
本実施例では、取り消しビット５０颯をセットしておく
ことにより命令パイプライン内の次の命令の実行を取り
消すことができる。
本発明の好ましい実施例では、今実行されている命令の
実行を取消すことができる。取り消しの目的は、たとえ
その目的がフェッチされ、その命令が実行されてしまっ
ても、あたかもその命令がパイプライン内に全く存在し
ていなかったように見せかけることである。取り消しは
その命令がＣＰＵの状態を変えさせないようにすること
により行われる。コンピュータの状態を変えないように
するには、取り消しプロセスは取り消された命令の結果
がレジスタまたはメモリ・ロケーションに書き込まれな
いようにするとともに、副作用、たとえば、取り消され
た命令により発生する割り込み、が起ることのないよう
にしなければならない。これは好ましい実施例では、書
き込み信号を前の命令で発生した取り消し信号で抑止（
ｑｕａｌｉｆｙ）　して、放置しておけばにコンピュー
タ・システムの状態を変えてしまうであろう計算の結果
の記憶が生起しないようにすることにより行われる。今
実行中の命令の芹き込み信号を抑止する簡単な方法は、
書き込み信号と前の命令で発生し一時的に保持されてい
る取り消し信号の論理積を取ることである。命令により
発生した取り消し信号は、たとえば、処理装置のステー
タス・ワード内に保持し次の命令に使うようにすること
ができる。
取り消しは、極めて有効なメ技法である。なんとなれば
、この技法を用いれば、パイプライン中の他の命令によ
り行われている判衛の結果、今フェッチしようとしてい
る命令が実行されなくなるか否かに関係なくその命令を
パイプライン内にフェッチすることができるからである
。すなわちこのようにしてフェッチされた命令は単にパ
イプライン中を進行し。
演算結果を記憶するところまで進む。ここにおいてこの
命令を最後の瞬間に取り消し、その命令がパイプライン
中にはまるで存在しなかったと同じ効果を発揮すること
ができる。
パイプライン方式コンピュータ・システムでは、実行す
べき次の命令に関して明確な２つの概念が存在する。第
１の概念は時間的次命令である。これは命令パイプライ
ン中で、今実行されている命令のすぐ後を流れている命
令である。この命令は今実行中の命令後に実行され、動
作の結果は取り消されないかぎり記憶される。第２の概
念は空間的次命令である。これはプログラムの中で今実
行中の命令の直後に置かれている命令である。普通は今
実行中の命令に対する空間的次命令は時間的次命令でも
ある。こ分岐命令）の所で発生するこの場合、時間的次
命令は、一般にその分岐命令の空間的次命令ではない目
標アドレスにある命令になる。
遅延スロット命令とは遅延分岐命令の時間的次命令であ
る。一般に、遅延スロット命令は分岐命令の空間的次命
令となる。この規則の例外は分岐命令の次の分岐命令の
場合である。この場合には、第２の分岐命令の遅延スロ
ント命令は第２の分岐命令の空１１目的次命令ではなく
第１の分岐命令の目標アドレスとなる。
本発明の好ましい実施例における無条件分岐は取り消し
および遅延スロツ［−命令の概念を明確に示している。
取り消しビットがオフの場合には、無条件分岐命令の遅
延スロット命令は常に実行される。これは遅延分岐命令
を常に使用することに相当している。取り消しビットが
オンの場合は無条件分岐命令の遅延スロット命令は常に
取り消される。これは遅延スロット命令を決して実行し
ないことに相当する。
第１図は本発明の好ましい実施例による条件付き分岐命
令の動作を示す。第１図においてコンピュータでは条件
付き分岐命令では、条件付き分岐命令１０２を含む命令
列１００から成るプログラム１０１が実行されるとする
。分岐命令１０２の空間的次命令は命令１０３である。
条件付き分岐命令１０２が負の分岐ディスプレースソフ
トを有するとしたとき。
命令１０４が目標アドレスにあるとする。また条件付き
分岐命令１０２が正の分岐ディスプレースソフトを有す
るとしたとき、命令１０５が目標アドレスにあるとする
。プログラムの実行をグラフ１１０゜１１１．１１２，
１１３．および１１４により示す。
通常の実行中、プログラムはある命令を実行し、次いで
その命令の空間的次命令を実行する。
グラフ１１０，１１１．および１１３は取り消しビット
がオフの状態での分岐命令勇者考の動作を示す。これは
決して取り消しを行なわない、すなわち常に実行すると
いう場合に相当する。分岐命令に続く遅延スロット命令
は分岐が行われるか否かに関係なく、およびそのディス
プレースソフトが正か負かに関係なく常に実行される。
分岐命令が成立しなか台９ ったときは、実行グラフ１１０に示すように空間層〕笈 剪命令１０３から継続する６分岐条件が成立したときは
、先ず遅延スロット命令が実行される。次いでディスプ
レースソフトが正の場合には目標アドレスにある命令が
グラフ１１３に示したように実行される。
グラフ１１０，１４１，１１２．および１１４は取り消
しビットをオンとした分岐命令の動作を示している。こ
れは以下に説明する「取り消しを行なったり行なわなか
ったりする」場合に相当する。取り消しビットがオンの
場合、遅延スロット命令は分岐の方向および分岐を行な
うか行わないかを決める条件が真であるか偽りであるか
に基いて取り消されたり取り消されなかったりする。グ
ラフ１１６と１１４は、分岐をトリガする条件が偽で分
岐が行な力れない場合の分岐命令の動作を示す。分岐デ
イスプレースソフトが正であれば、遅延スロット命令は
、グラフ１１０に示されるように実行される。分岐デイ
スプレースソフトが負であれば、遅延スロット命令は、
グラフ１１４に示されるように取り消される。
イブライン中には全く存在していないかのように取り消
されることを示している。　　　　　　　　　　　　　
　　バグラフ１１１と１１２は分岐をトリガする条件が
真で分岐を行なう場合の、取り消しビットがオンになっ
ている分岐命令の動作を示す。分岐デイスプレースソフ
トが正の場合には、遅延スロット命令はグラフ１１２に
示すように取り消され実行は目標アドレスから続けられ
る。分岐ディスプレースソフトが負の場合には、グラフ
１１１に示すように遅延スロット命令が実行されてから
目標アドレスの命令に制御が移る。
ればもっと明瞭に理解されるであろう。最初のステップ
では取り消しビットがオンか否かを調べることである。
取り消しビットがオフであれば、分岐命令トがオンであ
れば、分岐命令の次の遅延スロット命令は分岐が行われ
且つ分岐ディスプレースソフトが負である場合、あるい
は分岐が行われず且つ分岐ディスプレースソフトが正で
ある場合の他は、実行されない。
本発明の好ましい実施例の動作は非常に単純だが非常に
有効な静的分岐予測を行なっている。この静的分岐予測
では、正および負のディスプレースソフトの分岐がどの
ように行われるかに基いて２分岐が行われることになる
か否かを予測する。したがってどの命令をフェッチすべ
きかを予測する。その有効性は条件付き分岐命令を用い
て成る高水憎のプログラム制御構造を実現するにあたり
一組のソフトウェア規約にしたがうコンピュータ・ソフ
トウェアによって決まる。たとえば、ループ構成は後方
への（つまりディスプレースソフトが負の）条７件付き
分岐により実現されるので、負のディスプレースソフト
の分岐動作は頻繁に起ることになる。事実、Ｎ回実行さ
れるループの場合には負のディスプレースソフトの分岐
はＮ回の中Ｎ−４回成功することになる。仮定されるソ
フトウェア規約の他の例として１ｆ−ｔｈｅｎ−ｅｌｓ
ｅ構文では稀にしか行われない部分は、前方への（つま
りディスプレースソフトが正の）分岐により制御を移し
て実行し、これにより、より頻繁に実行される部分を分
岐が起らなかった場合の実行径路中の分岐命令にすぐ後
に置くことができるようになる。たとえば、前方への分
岐により通常のプログラムでは稀にしか実行されないエ
ラー処理ルーチンへ飛ぶようにすることができる。加え
て、取り消しビットを備えている本発明の好ましい実施
例は上述の静的分岐予測技法と関連して遅延スロツト命
令の使用を一般化し最適化している。取り消しビットが
オンのときには、静的分岐予測技法により頻度が高いと
予測されているところ′の、後方への条か°゛ 件付き分岐に成功した場合または面方への条件付き分岐
が失敗した場合に遅延スロット命令が実行される。した
がって頻繁な径路内の有用な命令の幾つかは、たとえば
、上記のマーシャ技法で述べたようにして、遅延スロッ
ト命令として実行することができる。取り消しビットが
オンである場合、稀であることが予測されているところ
の、後方への条件付き分岐の失敗または、前方への条件
付き分岐の成功が起ると、遅延スロットの命令の実行が
取り消される。
したがって性能を低下させる取り消しが起るのはごく稀
である。４ 取り消しビットがオフの場合は、遅延スロット命令は常
に実行される。これは分岐成功時の実行径路と分岐失敗
時の実行径路とに共通な命令を遅延スロット命令とする
ことができる場合に相当する。
第４図は本発明の好ましい実施例を適用できる装置の機
能的ブロック図である。この装置は命令メモリ３０１．
オプションの仮想アドレス変換ユニット３ｏ２．命令ユ
ニット３０３．実行ユニット３０４゜オプションの浮動
小点ユニット３０５．およびオプションのレジスタ・フ
ァイル３０６の６つの機能要素を備えている。これらの
機能要素は結果バス３１０、第１オペランド・バス３１
１２次命令バス３１２、第２オペランド・バス３１３．
およびアドレス・バス３１４の５本のバスを介して互い
に接続されている。実行ユニット３０４と命令ユニット
３０３とだけが本発明の好ましい実施例の動作を行うの
に関係している。実行ユニットは分岐するか分岐しない
宙・ かの判断を行うための条件を発生しメよびまたは記憶す
る。命令ユニットはメモリからフェッチすべき次の命令
のアドレスを発生して分岐を行い、アドレ仁 スなプログラム・カウンタに記憶さ単る手段となる。
本発明の好ましい実施例では、メモリ・ユニットは慣行
ユニットが使用する論理回路と同程度の速さの高速キャ
シュである。
第５図は第４図−の装置のタイム・チャートである。
タイミング図は命令４０１，４０２，４０３．および４
０４の実行に関係する４つの段階を示している。
右方向に進行する時間を表す時間軸４６０はステップに
分割されている。各命令についての４つの時間ステップ
は、命令アドレス発生ステップ４１０゜命令フェッチ・
ステップ４１１．実行ステップ４１２、および書き込み
ステップ４１３である。命令の実行は所望の任意の深さ
にパイプライン化することができる。本発明の好ましい
実施例は４段階のパイプラインを備えている。第５図に
示すように、４つ乙１ の命令はＸの時間ステップにおいても実行されている。
時刻４５０で命令４０１の書き込みステップは命令４０
２の実行ステップ、命令４０３の命令フェッチ・ステッ
プおよび命令４０４の命令アドレス発生ステップとオー
バーラツプしている。このことは分岐命令について考え
れば、分岐命令が実行ステップにある間に次の命令がフ
ェッチされてしまっていることになるということを意味
する。命令アドレス発生ステップの間に、次の命令のア
ドレスが実行すべき次の命令のアドレスを含んでいるプ
ログラム・カウンタから計算され、命令ユニット３０３
に置かれる。命令フェッチ・ステップの間、次の命令が
命令メモリ３０１からフェッチされる。この動作は、命
令アドレス発生ステップで計算されたアドレスの内容を
アドレス・バス３１４′に与え、そのアドレスの内容を
次命令′ゞス３１２に移しここで命令−Ｌ　ニー　ツ、
、。
トによりデコードされることにより行われる。分岐。１
よ。□、え、え、工１．．ゎあユ。、９３□　　　′：
ユニット３０４でデコードされ実行される比較動作と組
み合わせることもできる。
実行ステップ４１２で、分岐命令が実行される。
実行ステップ４１２の間１分岐命令の目標アドレスおよ
びこの分岐命令の空間的次命令のアドレスの両方が発生
する。この分岐命令が他の動作と組み合わされていれば
、その動作はこのときに゛実行される。
実行ステップの終りに、２つのアドレスの一方がプ　　
　　　　９０グラム・カウンタに移される。どのアドレ
スがプログラム・カウンタに移されるかは実行ユニット
３０４に記憶されている条件で決まる。書き込みステッ
プ４１３の間では、組み合わされた動作による結果を記
憶する必要がないかぎり書込み等の動作は起らない。命
令実行による結果や割込受付等の副作月のメモリやレジ
スタへの書込みを皆、ステップ４１２および４１３より
早くない時期に行なうことにより、常にパイプライン内
にある命令を取り消すという概念を簡単に実現すること
ができる。
〔発明の効果〕
以上説明したように本発明によればハードウェアを複雑
化せずに、分岐命令による実行効率の低下を防止できる
。
【図面の簡単な説明】
ｖ１１図は本発明の一実施例に基いて実現された条件付
き分岐命令の動作を説明するための図、第２図は本発明
の一実施例に基いて実現された比較分岐命令のフォーマ
ットを示す図、第３図は本発明の一実施例に基く分岐動
作を示すフローチャート、第４図は本発明の一実施例に
基く装置の機能的ブロック図。 第５図は第４図に示す装置のタイム・チャートである。 １０１ニブログラム。 １０２：条件付き分岐命令。 １０３．１０４，１０５：命令。 ５０１：比較分岐命令。 ５０６：デイスプレースソフト・フィールド。 ５０７：取り消しビット。 ５ｏ８：ディスプレースソフト・フィールド符号ビット
・

Claims (1)

    【特許請求の範囲】
  1. パイプライン方式のコンピュータにおいて分岐の方向に
    基いて遅延スロット中の命令を実質的に実行するか否か
    を定める分岐方式。
JP14771686A 1985-06-28 1986-06-24 分岐方法 Expired - Lifetime JP2518616B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US750625 1985-06-28
US06/750,625 US4755966A (en) 1985-06-28 1985-06-28 Bidirectional branch prediction and optimization

Publications (2)

Publication Number Publication Date
JPS623340A true JPS623340A (ja) 1987-01-09
JP2518616B2 JP2518616B2 (ja) 1996-07-24

Family

ID=25018608

Family Applications (1)

Application Number Title Priority Date Filing Date
JP14771686A Expired - Lifetime JP2518616B2 (ja) 1985-06-28 1986-06-24 分岐方法

Country Status (8)

Country Link
US (2) US4755966A (ja)
EP (2) EP0207665B1 (ja)
JP (1) JP2518616B2 (ja)
KR (1) KR940005817B1 (ja)
CN (1) CN1010618B (ja)
AU (2) AU589977B2 (ja)
CA (1) CA1270573A1 (ja)
DE (2) DE3680722D1 (ja)

Families Citing this family (62)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5440704A (en) * 1986-08-26 1995-08-08 Mitsubishi Denki Kabushiki Kaisha Data processor having branch predicting function
US5341482A (en) * 1987-03-20 1994-08-23 Digital Equipment Corporation Method for synchronization of arithmetic exceptions in central processing units having pipelined execution units simultaneously executing instructions
US5247627A (en) * 1987-06-05 1993-09-21 Mitsubishi Denki Kabushiki Kaisha Digital signal processor with conditional branch decision unit and storage of conditional branch decision results
US5134561A (en) * 1987-07-20 1992-07-28 International Business Machines Corporation Computer system with logic for writing instruction identifying data into array control lists for precise post-branch recoveries
JPS6488844A (en) * 1987-09-30 1989-04-03 Takeshi Sakamura Data processor
US5155818A (en) * 1988-09-28 1992-10-13 Data General Corporation Unconditional wide branch instruction acceleration
EP0365187A3 (en) * 1988-10-18 1992-04-29 Apollo Computer Inc. Apparatus for selective execution of instructions following a branch instruction
EP0378415A3 (en) * 1989-01-13 1991-09-25 International Business Machines Corporation Multiple instruction dispatch mechanism
US5093908A (en) * 1989-04-17 1992-03-03 International Business Machines Corporation Method and apparatus for executing instructions in a single sequential instruction stream in a main processor and a coprocessor
US5136697A (en) * 1989-06-06 1992-08-04 Advanced Micro Devices, Inc. System for reducing delay for execution subsequent to correctly predicted branch instruction using fetch information stored with each block of instructions in cache
EP0442116A3 (en) * 1990-02-13 1993-03-03 Hewlett-Packard Company Pipeline method and apparatus
US5303377A (en) * 1990-03-27 1994-04-12 North American Philips Corporation Method for compiling computer instructions for increasing instruction cache efficiency
US5303356A (en) * 1990-05-04 1994-04-12 International Business Machines Corporation System for issuing instructions for parallel execution subsequent to branch into a group of member instructions with compoundability in dictation tag
EP0825529A3 (en) * 1990-05-04 1998-04-29 International Business Machines Corporation System for preparing instructions for instruction parallel processor and system with mechanism for branching in the middle of a compound instruction
EP0481031A4 (en) * 1990-05-04 1993-01-27 International Business Machines Corporation System for compounding instructions for handling instruction and data stream for processor with different attributes
JP2845578B2 (ja) * 1990-06-19 1999-01-13 甲府日本電気 株式会社 命令制御方式
US5283873A (en) * 1990-06-29 1994-02-01 Digital Equipment Corporation Next line prediction apparatus for a pipelined computed system
EP0463973A3 (en) * 1990-06-29 1993-12-01 Digital Equipment Corp Branch prediction in high performance processor
JP2834292B2 (ja) * 1990-08-15 1998-12-09 株式会社日立製作所 データ・プロセッサ
JP2508907B2 (ja) * 1990-09-18 1996-06-19 日本電気株式会社 遅延分岐命令の制御方式
JP2534392B2 (ja) * 1990-09-21 1996-09-11 三田工業株式会社 画像形成装置のための自己診断および自己修復システム
US5303355A (en) * 1991-03-27 1994-04-12 Motorola, Inc. Pipelined data processor which conditionally executes a predetermined looping instruction in hardware
US5450585A (en) * 1991-05-15 1995-09-12 International Business Machines Corporation Compiler with delayed conditional branching
JP2875909B2 (ja) * 1991-07-12 1999-03-31 三菱電機株式会社 並列演算処理装置
EP0855647A1 (en) * 1992-01-06 1998-07-29 Hitachi, Ltd. Computer for performing data fetch and data prefetch in parallel
US5434986A (en) * 1992-01-09 1995-07-18 Unisys Corporation Interdependency control of pipelined instruction processor using comparing result of two index registers of skip instruction and next sequential instruction
JPH06259262A (ja) * 1993-03-08 1994-09-16 Fujitsu Ltd 分岐確率を設定するコンパイラの処理方法および処理装置
US5426600A (en) * 1993-09-27 1995-06-20 Hitachi America, Ltd. Double precision division circuit and method for digital signal processor
JP3452655B2 (ja) * 1993-09-27 2003-09-29 株式会社日立製作所 ディジタル信号処理プロセッサおよびそれを用いて命令を実行する方法
US5815695A (en) * 1993-10-28 1998-09-29 Apple Computer, Inc. Method and apparatus for using condition codes to nullify instructions based on results of previously-executed instructions on a computer processor
TW261676B (ja) * 1993-11-02 1995-11-01 Motorola Inc
US5539888A (en) * 1993-12-23 1996-07-23 Unisys Corporation System and method for processing external conditional branch instructions
US5799180A (en) * 1995-10-31 1998-08-25 Texas Instruments Incorporated Microprocessor circuits, systems, and methods passing intermediate instructions between a short forward conditional branch instruction and target instruction through pipeline, then suppressing results if branch taken
US5905881A (en) * 1995-11-30 1999-05-18 Unisys Corporation Delayed state writes for an instruction processor
US5774709A (en) * 1995-12-06 1998-06-30 Lsi Logic Corporation Enhanced branch delay slot handling with single exception program counter
US5799167A (en) * 1996-05-15 1998-08-25 Hewlett-Packard Company Instruction nullification system and method for a processor that executes instructions out of order
US5796997A (en) * 1996-05-15 1998-08-18 Hewlett-Packard Company Fast nullify system and method for transforming a nullify function into a select function
US5867699A (en) * 1996-07-25 1999-02-02 Unisys Corporation Instruction flow control for an instruction processor
US5974538A (en) * 1997-02-21 1999-10-26 Wilmot, Ii; Richard Byron Method and apparatus for annotating operands in a computer system with source instruction identifiers
US6401196B1 (en) * 1998-06-19 2002-06-04 Motorola, Inc. Data processor system having branch control and method thereof
US6192515B1 (en) * 1998-07-17 2001-02-20 Intel Corporation Method for software pipelining nested loops
US6862563B1 (en) 1998-10-14 2005-03-01 Arc International Method and apparatus for managing the configuration and functionality of a semiconductor design
US20060168431A1 (en) * 1998-10-14 2006-07-27 Peter Warnes Method and apparatus for jump delay slot control in a pipelined processor
JP3470948B2 (ja) * 1999-01-28 2003-11-25 インターナショナル・ビジネス・マシーンズ・コーポレーション 動的コンパイル時期決定方法、バイトコード実行モード選択方法、及びコンピュータ
US6571385B1 (en) * 1999-03-22 2003-05-27 Intel Corporation Early exit transformations for software pipelining
WO2001016702A1 (en) 1999-09-01 2001-03-08 Intel Corporation Register set used in multithreaded parallel processor architecture
HK1046049A1 (zh) 1999-09-01 2002-12-20 Intel Corporation 用於多线程处理器的分支指令
US6662360B1 (en) * 1999-09-27 2003-12-09 International Business Machines Corporation Method and system for software control of hardware branch prediction mechanism in a data processor
US6446197B1 (en) * 1999-10-01 2002-09-03 Hitachi, Ltd. Two modes for executing branch instructions of different lengths and use of branch control instruction and register set loaded with target instructions
AU2001243463A1 (en) 2000-03-10 2001-09-24 Arc International Plc Memory interface and method of interfacing between functional entities
US7681018B2 (en) 2000-08-31 2010-03-16 Intel Corporation Method and apparatus for providing large register address space while maximizing cycletime performance for a multi-threaded register file set
DE10101949C1 (de) * 2001-01-17 2002-08-08 Infineon Technologies Ag Datenverarbeitungsverfahren
JP4141112B2 (ja) * 2001-04-12 2008-08-27 株式会社日立製作所 プロセッサおよびプロセッサシステム
US6785804B2 (en) * 2001-05-17 2004-08-31 Broadcom Corporation Use of tags to cancel a conditional branch delay slot instruction
US7437724B2 (en) 2002-04-03 2008-10-14 Intel Corporation Registers for data transfers
US7668622B2 (en) * 2004-03-30 2010-02-23 Honeywell International Inc. Efficient blending based on blending component availablity for a partial blend duration
JP2006011723A (ja) * 2004-06-24 2006-01-12 Matsushita Electric Ind Co Ltd 分岐制御方法、および情報処理装置
US8127113B1 (en) 2006-12-01 2012-02-28 Synopsys, Inc. Generating hardware accelerators and processor offloads
US8689200B1 (en) * 2011-01-12 2014-04-01 Google Inc. Method and system for optimizing an executable program by generating special operations for identical program entities
US8683455B1 (en) 2011-01-12 2014-03-25 Google Inc. Method and system for optimizing an executable program by selectively merging identical program entities
US20170277539A1 (en) * 2016-03-24 2017-09-28 Imagination Technologies Limited Exception handling in processor using branch delay slot instruction set architecture
US10970073B2 (en) 2018-10-02 2021-04-06 International Business Machines Corporation Branch optimization during loading

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS52120735A (en) * 1976-04-05 1977-10-11 Agency Of Ind Science & Technol Microporogram control unit

Family Cites Families (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
BE789583A (fr) * 1971-10-01 1973-02-01 Sanders Associates Inc Appareil de controle de programme pour machine de traitement del'information
GB1448866A (en) * 1973-04-13 1976-09-08 Int Computers Ltd Microprogrammed data processing systems
US4378589A (en) * 1976-12-27 1983-03-29 International Business Machines Corporation Undirectional looped bus microcomputer architecture
US4210960A (en) * 1977-09-02 1980-07-01 Sperry Corporation Digital computer with overlapped operation utilizing conditional control to minimize time losses
US4325120A (en) * 1978-12-21 1982-04-13 Intel Corporation Data processing system
SE456051B (sv) * 1980-02-11 1988-08-29 Western Electric Co Digital processoranordning anordnad for pipeline-databehandlingsoperationer
US4539635A (en) * 1980-02-11 1985-09-03 At&T Bell Laboratories Pipelined digital processor arranged for conditional operation
US4390946A (en) * 1980-10-20 1983-06-28 Control Data Corporation Lookahead addressing in a pipeline computer control store with separate memory segments for single and multiple microcode instruction sequences
US4514804A (en) * 1981-11-25 1985-04-30 Nippon Electric Co., Ltd. Information handling apparatus having a high speed instruction-executing function
WO1985000453A1 (en) * 1983-07-11 1985-01-31 Prime Computer, Inc. Data processing system
US4742454A (en) * 1983-08-30 1988-05-03 Amdahl Corporation Apparatus for buffer control bypass
JPH0754461B2 (ja) * 1985-02-08 1995-06-07 株式会社日立製作所 情報処理装置
CA1254661A (en) * 1985-06-28 1989-05-23 Allen J. Baum Method and means for instruction combination for code compression
JPS6393038A (ja) * 1986-10-07 1988-04-23 Mitsubishi Electric Corp 計算機

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS52120735A (en) * 1976-04-05 1977-10-11 Agency Of Ind Science & Technol Microporogram control unit

Also Published As

Publication number Publication date
DE3650413D1 (de) 1995-11-09
DE3650413T2 (de) 1996-03-07
CN86103708A (zh) 1986-12-24
EP0423906A3 (en) 1991-08-28
KR940005817B1 (ko) 1994-06-23
US4755966A (en) 1988-07-05
AU4867090A (en) 1990-05-10
KR870000643A (ko) 1987-02-19
AU5917186A (en) 1987-01-08
EP0423906A2 (en) 1991-04-24
CN1010618B (zh) 1990-11-28
CA1270573A1 (en) 1990-06-19
CA1272296C (ja) 1990-07-31
EP0207665B1 (en) 1991-08-07
AU589977B2 (en) 1989-10-26
AU627828B2 (en) 1992-09-03
JP2518616B2 (ja) 1996-07-24
EP0207665A1 (en) 1987-01-07
DE3680722D1 (de) 1991-09-12
US5051896A (en) 1991-09-24
EP0423906B1 (en) 1995-10-04

Similar Documents

Publication Publication Date Title
JPS623340A (ja) 分岐方法
US5859999A (en) System for restoring predicate registers via a mask having at least a single bit corresponding to a plurality of registers
US6115808A (en) Method and apparatus for performing predicate hazard detection
JP3120152B2 (ja) コンピューターシステム
US5655096A (en) Method and apparatus for dynamic scheduling of instructions to ensure sequentially coherent data in a processor employing out-of-order execution
US5710902A (en) Instruction dependency chain indentifier
JP3093639B2 (ja) プロセッサ内の資源割当て追跡方法及びそのシステム
US6185668B1 (en) Method and apparatus for speculative execution of instructions
JP3594506B2 (ja) マイクロプロセッサの分岐命令予測方法
US7865769B2 (en) In situ register state error recovery and restart mechanism
US6973563B1 (en) Microprocessor including return prediction unit configured to determine whether a stored return address corresponds to more than one call instruction
US6397326B1 (en) Method and circuit for preloading prediction circuits in microprocessors
JPH1069386A (ja) 推測的な実行を支援する論理装置
JP2001166935A (ja) プロセッサにおける分岐予測方法及びプロセッサ
JPH07248897A (ja) コンピュータ・システムにおける例外からの回復方法、及びそのための装置
JP2620511B2 (ja) データ・プロセッサ
US6622240B1 (en) Method and apparatus for pre-branch instruction
JP3207124B2 (ja) カウント／リンク・レジスタ変更命令の投機実行をサポートする方法及び装置
US20040172518A1 (en) Information processing unit and information processing method
CN1124546C (zh) 一种超标量处理器及在该超标量处理器中完成指令的方法
US5943494A (en) Method and system for processing multiple branch instructions that write to count and link registers
US5964870A (en) Method and apparatus for using function context to improve branch
EP1039376B1 (en) Sub-instruction emulation in a VLIW processor
US6851044B1 (en) System and method for eliminating write backs with buffer for exception processing
US6718460B1 (en) Mechanism for error handling in a computer system

Legal Events

Date Code Title Description
R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

EXPY Cancellation because of completion of term