JPH0573310A - 条件分岐の動的判定方式 - Google Patents
条件分岐の動的判定方式Info
- Publication number
- JPH0573310A JPH0573310A JP23669691A JP23669691A JPH0573310A JP H0573310 A JPH0573310 A JP H0573310A JP 23669691 A JP23669691 A JP 23669691A JP 23669691 A JP23669691 A JP 23669691A JP H0573310 A JPH0573310 A JP H0573310A
- Authority
- JP
- Japan
- Prior art keywords
- stage
- register
- branch
- pipeline
- interlock
- 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.)
- Withdrawn
Links
Landscapes
- Advance Control (AREA)
Abstract
(57)【要約】
【目的】 本発明は、パイプラインにおける条件分岐命
令の動的判定方式に関し、パイプラインで分岐命令の条
件判定の時期としてレジスタ依存によるインタロックが
解除された時点で速やかに行い、分岐条件判定を少ない
オーバーヘッドで可能にすることを目的とする。 【構成】 パイプライン１中を流れてきた条件分岐命令
が最初のレジスタリード機構３のステージに到達したと
きにインタロックが生じないと判明したときにレジスタ
値を読み、次のステージで条件判定機構４が分岐と判定
したときに分岐先の命令列をパイプラインの入口に投入
し、非分岐と判定したときに次に進み、第２番目のレジ
スタリード機構３のステージに到達したときにレジスタ
値を読み、次のステージで条件判定機構４が分岐と判定
したときに分岐先の命令列をパイプラインの入口に投入
し、非分岐と判定したときに次に進むように構成する。
令の動的判定方式に関し、パイプラインで分岐命令の条
件判定の時期としてレジスタ依存によるインタロックが
解除された時点で速やかに行い、分岐条件判定を少ない
オーバーヘッドで可能にすることを目的とする。 【構成】 パイプライン１中を流れてきた条件分岐命令
が最初のレジスタリード機構３のステージに到達したと
きにインタロックが生じないと判明したときにレジスタ
値を読み、次のステージで条件判定機構４が分岐と判定
したときに分岐先の命令列をパイプラインの入口に投入
し、非分岐と判定したときに次に進み、第２番目のレジ
スタリード機構３のステージに到達したときにレジスタ
値を読み、次のステージで条件判定機構４が分岐と判定
したときに分岐先の命令列をパイプラインの入口に投入
し、非分岐と判定したときに次に進むように構成する。
Description
【０００１】
【産業上の利用分野】本発明は、パイプラインにおける
条件分岐命令の条件分岐を動的に判定する動的判定方式
に関するものである。
条件分岐命令の条件分岐を動的に判定する動的判定方式
に関するものである。
【０００２】
【従来の技術】パイプライン計算機はパイプラインを命
令が滞りなく流れる時にその性能を最大に引き出すこと
ができるが、実際にそうすることは殆ど不可能であり、
円滑な流れを妨げるいくつかの要因が存在する。主な要
因の１つが分岐命令によるパイプライン中の命令のキャ
ンセルである。これは分岐によって命令の供給系列が変
更されるため、パイプラインの途中まで進んだ変更前の
系列の命令群を無効にし、新たな系列の命令をパイプラ
インの入口から投入し直さねばならず、その過程におい
てパイプラインに空が生じることによるオーバーヘッド
である。これ以外の主な要因にレジスタ間の依存関係に
よるインタロックがある。これはある命令Ａがパイプラ
インのあるステージでレジスタを読み出すときに、その
レジスタの内容を更新する命令Ｂがパイプライン中に存
在する場合はその変更を待ってから読み出し動作を行う
必要があるため、読み出し可能となるまで命令Ａは先に
進むことができなくなってしまう状況を意味する。これ
らのオーバーヘッドはパイプラインに本質的なもので完
全に除去することは不可能であるが、少しでも軽減する
ための工夫が提案され実施されている。例えば分岐予
測、バイパス、コンパイラによる命令の並び換えなどの
技術がそれである。
令が滞りなく流れる時にその性能を最大に引き出すこと
ができるが、実際にそうすることは殆ど不可能であり、
円滑な流れを妨げるいくつかの要因が存在する。主な要
因の１つが分岐命令によるパイプライン中の命令のキャ
ンセルである。これは分岐によって命令の供給系列が変
更されるため、パイプラインの途中まで進んだ変更前の
系列の命令群を無効にし、新たな系列の命令をパイプラ
インの入口から投入し直さねばならず、その過程におい
てパイプラインに空が生じることによるオーバーヘッド
である。これ以外の主な要因にレジスタ間の依存関係に
よるインタロックがある。これはある命令Ａがパイプラ
インのあるステージでレジスタを読み出すときに、その
レジスタの内容を更新する命令Ｂがパイプライン中に存
在する場合はその変更を待ってから読み出し動作を行う
必要があるため、読み出し可能となるまで命令Ａは先に
進むことができなくなってしまう状況を意味する。これ
らのオーバーヘッドはパイプラインに本質的なもので完
全に除去することは不可能であるが、少しでも軽減する
ための工夫が提案され実施されている。例えば分岐予
測、バイパス、コンパイラによる命令の並び換えなどの
技術がそれである。
【０００３】
【発明が解決しようとする課題】ここでは、条件分岐命
令の効率的な実現に絞って考える。条件分岐命令はある
レジスタの内容を読み出し、その値がある条件を満たし
た場合のみ分岐するものとする。このような条件分岐命
令の条件判定をパイプラインの中でどのステージで行う
のが良いだろうか。分岐先の命令列をパイプラインに投
入する時期を早くするには、なるべく早く条件判定をす
る必要がある。即ち条件判定ステージをパイプラインの
入口に近い方に置くのが良い。一方、条件判定に必要な
レジスタ値をオーバーヘッドなしに読むには遅い時期に
読む方が良い。なぜなら早く読もうとしてもレジスタ値
が確定するまで待たされてしまうからである。
令の効率的な実現に絞って考える。条件分岐命令はある
レジスタの内容を読み出し、その値がある条件を満たし
た場合のみ分岐するものとする。このような条件分岐命
令の条件判定をパイプラインの中でどのステージで行う
のが良いだろうか。分岐先の命令列をパイプラインに投
入する時期を早くするには、なるべく早く条件判定をす
る必要がある。即ち条件判定ステージをパイプラインの
入口に近い方に置くのが良い。一方、条件判定に必要な
レジスタ値をオーバーヘッドなしに読むには遅い時期に
読む方が良い。なぜなら早く読もうとしてもレジスタ値
が確定するまで待たされてしまうからである。
【０００４】このような条件分岐命令の効率的な実現の
ためには条件判定の時期を早くした方がいい面と、遅く
した方がいい面がある。これらの点に注目して、両方の
見地から最適な条件分岐判定を動的に行うことが望まれ
ている。
ためには条件判定の時期を早くした方がいい面と、遅く
した方がいい面がある。これらの点に注目して、両方の
見地から最適な条件分岐判定を動的に行うことが望まれ
ている。
【０００５】本発明は、パイプラインで分岐命令の条件
判定の時期としてレジスタ依存によるインタロックが解
除された時点で速やかに行い、パイプラインで条件分岐
命令の分岐条件判定を少ないオーバーヘッドで可能にす
ることを目的としている。
判定の時期としてレジスタ依存によるインタロックが解
除された時点で速やかに行い、パイプラインで条件分岐
命令の分岐条件判定を少ないオーバーヘッドで可能にす
ることを目的としている。
【０００６】
【課題を解決するための手段】図１を参照して課題を解
決するための手段を説明する。図１において、パイプラ
イン１は、命令列が順次流れる複数のステージから構成
されるものである。
決するための手段を説明する。図１において、パイプラ
イン１は、命令列が順次流れる複数のステージから構成
されるものである。
【０００７】レジスタ２は、分岐条件を判定するための
レジスタ値を格納するものである。レジスタリード機構
３は、レジスタ２から分岐判定に必要なレジスタ値を読
むものである。
レジスタ値を格納するものである。レジスタリード機構
３は、レジスタ２から分岐判定に必要なレジスタ値を読
むものである。
【０００８】条件判定機構４は、レジスタ２から読み込
んだレジスタ値をもとに条件判定を行い、分岐あるいは
非分岐を判定したりなどするものである。
んだレジスタ値をもとに条件判定を行い、分岐あるいは
非分岐を判定したりなどするものである。
【０００９】
【作用】本発明は、図１に示すように、パイプライン１
中のあるステージにレジスタリード機構３を設けると共
に次のステージに条件判定機構４を設けることを２組行
い、パイプライン１中を流れてきた条件分岐命令が最初
のレジスタリード機構３のステージに到達したときにイ
ンタロックが生じないと判明したときにレジスタ２から
レジスタ値を読み、次のステージで条件判定機構４がこ
のレジスタ値をもとに分岐と判定したときに分岐先の命
令列をパイプライン１の入口に投入し、非分岐と判定し
たときに次のステージに進み、一方、インタロックが生
じると判明したときにスキップし、第２番目のレジスタ
リード機構３のステージに到達したときにレジスタ２か
らレジスタ値を読み、次のステージで条件判定機構４が
このレジスタ値をもとに分岐と判定したときに分岐先の
命令列をパイプラインの入口に投入して次のステージに
進み、非分岐と判定したときに次のステージに進むよう
にしている。この際、インタロックの有無をコンパイル
時に解析し、その情報を条件分岐命令コードに付加し、
これを用いてインタロックを判定するようにしてもよ
い。
中のあるステージにレジスタリード機構３を設けると共
に次のステージに条件判定機構４を設けることを２組行
い、パイプライン１中を流れてきた条件分岐命令が最初
のレジスタリード機構３のステージに到達したときにイ
ンタロックが生じないと判明したときにレジスタ２から
レジスタ値を読み、次のステージで条件判定機構４がこ
のレジスタ値をもとに分岐と判定したときに分岐先の命
令列をパイプライン１の入口に投入し、非分岐と判定し
たときに次のステージに進み、一方、インタロックが生
じると判明したときにスキップし、第２番目のレジスタ
リード機構３のステージに到達したときにレジスタ２か
らレジスタ値を読み、次のステージで条件判定機構４が
このレジスタ値をもとに分岐と判定したときに分岐先の
命令列をパイプラインの入口に投入して次のステージに
進み、非分岐と判定したときに次のステージに進むよう
にしている。この際、インタロックの有無をコンパイル
時に解析し、その情報を条件分岐命令コードに付加し、
これを用いてインタロックを判定するようにしてもよ
い。
【００１０】また、レジスタリード機構３および条件判
定機構４の組をパイプライン１中に連続して設け、イン
タロックが解除された直後のステージでレジスタリード
機構３がレジスタ値を読み、次のステージの条件判定機
構４が分岐と判定したときに分岐先の命令列をパイプラ
インの入口に投入して次のステージに進み、非分岐と判
定したときに次のステージに進むようにしている。この
際、インタロックがいずれのステージで解除されるかを
コンパイル時に解析して条件分岐命令コードに付加し、
これを用いてインタロックを判定したり、インタロック
の有無をコンパイル時に解析し、その情報を条件分岐命
令コードに付加し、これを用いてインタロックを判定す
るようにしてもよい。
定機構４の組をパイプライン１中に連続して設け、イン
タロックが解除された直後のステージでレジスタリード
機構３がレジスタ値を読み、次のステージの条件判定機
構４が分岐と判定したときに分岐先の命令列をパイプラ
インの入口に投入して次のステージに進み、非分岐と判
定したときに次のステージに進むようにしている。この
際、インタロックがいずれのステージで解除されるかを
コンパイル時に解析して条件分岐命令コードに付加し、
これを用いてインタロックを判定したり、インタロック
の有無をコンパイル時に解析し、その情報を条件分岐命
令コードに付加し、これを用いてインタロックを判定す
るようにしてもよい。
【００１１】従って、パイプラインで分岐命令の条件判
定の時期としてレジスタ依存によるインタロックが解除
された時点で速やかに行うことにより、パイプラインに
おける条件分岐命令の分岐条件判定を少ないオーバーヘ
ッドで行うことが可能となる。
定の時期としてレジスタ依存によるインタロックが解除
された時点で速やかに行うことにより、パイプラインに
おける条件分岐命令の分岐条件判定を少ないオーバーヘ
ッドで行うことが可能となる。
【００１２】
【実施例】次に、図１から図３を用いて本発明の実施例
の構成および動作を順次詳細に説明する。
の構成および動作を順次詳細に説明する。
【００１３】図１は、本発明の１実施例構成図を示す。
図１において、パイプライン１は、命令列が順次流れる
複数のステージから構成されるものであって、任意のｘ
−１ステージにレジスタリード機構３−１と次のｘステ
ージに条件判定機構４−１、任意のｙ−１ステージにレ
ジスタリード機構３−２と次のｙステージに条件判定機
構４−２、およびインタロックフラグ６−ｘ、６−ｙな
どを設けたものである。
図１において、パイプライン１は、命令列が順次流れる
複数のステージから構成されるものであって、任意のｘ
−１ステージにレジスタリード機構３−１と次のｘステ
ージに条件判定機構４−１、任意のｙ−１ステージにレ
ジスタリード機構３−２と次のｙステージに条件判定機
構４−２、およびインタロックフラグ６−ｘ、６−ｙな
どを設けたものである。
【００１４】レジスタリード機構３−１、３−２は、レ
ジスタ２から、条件分岐命令の分岐判定するためのレジ
スタ値を読み込むものである。条件判定機構４−１、４
−２は、レジスタリード機構３−１、３−２がレジスタ
２から読み込んだリード値をもとに、条件分岐命令の条
件判定を行い、分岐／非分岐を判定するものである。分
岐と判定したときは、分岐先の命令列をパイプラインの
入口に投入する。非分岐と判定したときは、次の命令に
進む。
ジスタ２から、条件分岐命令の分岐判定するためのレジ
スタ値を読み込むものである。条件判定機構４−１、４
−２は、レジスタリード機構３−１、３−２がレジスタ
２から読み込んだリード値をもとに、条件分岐命令の条
件判定を行い、分岐／非分岐を判定するものである。分
岐と判定したときは、分岐先の命令列をパイプラインの
入口に投入する。非分岐と判定したときは、次の命令に
進む。
【００１５】レジスタ２は、条件分岐命令が分岐か、非
分岐かを判定するための値を格納するものである。制御
部５は、プログラムに従って全体を統括制御するもので
ある。
分岐かを判定するための値を格納するものである。制御
部５は、プログラムに従って全体を統括制御するもので
ある。
【００１６】インタロックフラグ６は、ステージで条件
分岐命令の条件判定を行うために、レジスタ２からレジ
スタ値を読み込もうとするとき、未だパイプライン１中
の他の命令によって更新されていなく、当該他の命令に
よって更新されるまでインタロックするか否かを表わす
フラグである。このインタロックフラグ６は、コンパイ
ル時に解析して命令コードに付加したインタロック情報
を参照し、設定してもよい。このインタロックフラグ６
は、命令がパイプライン１を流れるに従って順次図示矢
印のように流れて行く。従って、これらインタロックフ
ラグ６−ｘ、６−ｙに従って、いずれのステージで条件
分岐命令の条件判定を行うか決定する（図２を用いて詳
述する）。
分岐命令の条件判定を行うために、レジスタ２からレジ
スタ値を読み込もうとするとき、未だパイプライン１中
の他の命令によって更新されていなく、当該他の命令に
よって更新されるまでインタロックするか否かを表わす
フラグである。このインタロックフラグ６は、コンパイ
ル時に解析して命令コードに付加したインタロック情報
を参照し、設定してもよい。このインタロックフラグ６
は、命令がパイプライン１を流れるに従って順次図示矢
印のように流れて行く。従って、これらインタロックフ
ラグ６−ｘ、６−ｙに従って、いずれのステージで条件
分岐命令の条件判定を行うか決定する（図２を用いて詳
述する）。
【００１７】次に、図２のフローチャートに示す順序に
従い、図１の構成の動作を詳細に説明する。ここで、図
１に示すように、ｘ−１ステージにレジスタ２からレジ
スタ値を読み込むレジスタリード機構３−１を設けると
共に次のｘステージにレジスタ値をもとに条件分岐命令
の条件判定を行う条件判定機構４−１を設け、更に、ｙ
−１ステージにレジスタ２からレジスタ値を読み込むレ
ジスタリード機構３−２を設けると共に次のｙステージ
にレジスタ値をもとに条件分岐命令の条件判定を行う条
件判定機構４−２を設けたときのフローチャートであ
る。
従い、図１の構成の動作を詳細に説明する。ここで、図
１に示すように、ｘ−１ステージにレジスタ２からレジ
スタ値を読み込むレジスタリード機構３−１を設けると
共に次のｘステージにレジスタ値をもとに条件分岐命令
の条件判定を行う条件判定機構４−１を設け、更に、ｙ
−１ステージにレジスタ２からレジスタ値を読み込むレ
ジスタリード機構３−２を設けると共に次のｙステージ
にレジスタ値をもとに条件分岐命令の条件判定を行う条
件判定機構４−２を設けたときのフローチャートであ
る。
【００１８】図２において、Ｓ１は、ｘ−１ステージの
命令が条件分岐命令か判定する。ＹＥＳの場合には、Ｓ
２に進む。ＮＯの場合には、該当処理を行う。Ｓ２は、
ｘ−１ステージでレジスタ２を読むとインタロックする
か否かを判別する。これは、例えば条件分岐命令コード
にコンパイル時に付加されたビット（インタロック情報
を表わすビット）を参照してインタロックが発生するか
否かを判別する。ＹＥＳの場合（インタロックが発生す
る場合）には、Ｓ４でインタロックフラグ６−ｘをＯＮ
にセットし、次のｘステージに進む（Ｓ５に進む）。一
方、ＮＯの場合（インタロックが発生しない場合）に
は、Ｓ３でインタロックフラグ６−ｘをＯＦＦにセット
し、レジスタ２からレジスタ値を読み、次のｘステージ
に進む（Ｓ５に進む）。
命令が条件分岐命令か判定する。ＹＥＳの場合には、Ｓ
２に進む。ＮＯの場合には、該当処理を行う。Ｓ２は、
ｘ−１ステージでレジスタ２を読むとインタロックする
か否かを判別する。これは、例えば条件分岐命令コード
にコンパイル時に付加されたビット（インタロック情報
を表わすビット）を参照してインタロックが発生するか
否かを判別する。ＹＥＳの場合（インタロックが発生す
る場合）には、Ｓ４でインタロックフラグ６−ｘをＯＮ
にセットし、次のｘステージに進む（Ｓ５に進む）。一
方、ＮＯの場合（インタロックが発生しない場合）に
は、Ｓ３でインタロックフラグ６−ｘをＯＦＦにセット
し、レジスタ２からレジスタ値を読み、次のｘステージ
に進む（Ｓ５に進む）。
【００１９】Ｓ５は、ｘステージの命令が条件分岐命令
か判定する。ＹＥＳの場合には、Ｓ６に進む。ＮＯの場
合には、該当処理を行う。Ｓ６は、インタロックフラグ
６−ｘがＯＦＦか判定する。ＹＥＳの場合には、インタ
ロックしないので、Ｓ７でｘステージで条件判定し、 ・条件満足なら分岐先の命令をパイプラインの入口に投
入する。
か判定する。ＹＥＳの場合には、Ｓ６に進む。ＮＯの場
合には、該当処理を行う。Ｓ６は、インタロックフラグ
６−ｘがＯＦＦか判定する。ＹＥＳの場合には、インタ
ロックしないので、Ｓ７でｘステージで条件判定し、 ・条件満足なら分岐先の命令をパイプラインの入口に投
入する。
【００２０】・条件不満足なら次に進む。そして、Ｓ９
に進む。一方、ＮＯの場合には、インタロックするの
で、Ｓ８で次のＳ９に進む。
に進む。一方、ＮＯの場合には、インタロックするの
で、Ｓ８で次のＳ９に進む。
【００２１】以上によって、パイプライン中を流れてき
た条件分岐命令が最初のレジスタリード機構３−１のｘ
−１ステージに到達したときにインタロックが生じない
と判明したときにインタロックフラグ６−ｘをＯＦＦに
設定してレジスタ２からレジスタ値を読み、次のｘステ
ージで条件判定機構４−１がレジスタ値をもとに分岐を
判定し、条件満足なら分岐先の命令をパイプライン１の
入口に投入し、条件満足しないなら次のステージに進
む。一方、インタロックが生じると判明したときにイン
タロックフラグ６−ｘをＯＮに設定し、レジスタ値や条
件判定することなく、次のステージに進む。これによ
り、インタロックが発生しないときに入口に近いステー
ジで条件判定して条件満足したときに分岐先の命令列を
パイプラインの入口から投入し、パイプラインに投入し
た命令列のキャンセル数を少なくし、パイプラインの空
を削減することが可能となると共に、一方、インタロッ
クが発生するときに入口に近いステージで条件判定しな
いのでインタロックによるオーバヘッドを回避すること
が可能となる。そして、条件判定しなかった場合には、
後述するパイプライン１の後段で条件判定を行う。
た条件分岐命令が最初のレジスタリード機構３−１のｘ
−１ステージに到達したときにインタロックが生じない
と判明したときにインタロックフラグ６−ｘをＯＦＦに
設定してレジスタ２からレジスタ値を読み、次のｘステ
ージで条件判定機構４−１がレジスタ値をもとに分岐を
判定し、条件満足なら分岐先の命令をパイプライン１の
入口に投入し、条件満足しないなら次のステージに進
む。一方、インタロックが生じると判明したときにイン
タロックフラグ６−ｘをＯＮに設定し、レジスタ値や条
件判定することなく、次のステージに進む。これによ
り、インタロックが発生しないときに入口に近いステー
ジで条件判定して条件満足したときに分岐先の命令列を
パイプラインの入口から投入し、パイプラインに投入し
た命令列のキャンセル数を少なくし、パイプラインの空
を削減することが可能となると共に、一方、インタロッ
クが発生するときに入口に近いステージで条件判定しな
いのでインタロックによるオーバヘッドを回避すること
が可能となる。そして、条件判定しなかった場合には、
後述するパイプライン１の後段で条件判定を行う。
【００２２】Ｓ９は、インタロックフラグ６−ｙはＯＮ
か判定する。これは、Ｓ１からＳ８の処理で、インタロ
ックするとしてインタロックフラグをＯＮに設定し、未
だ条件分岐命令の条件判定が行われていないかを判定す
る。ＹＥＳの場合には、条件判定が行われていないの
で、Ｓ１０でレジスタ２からレジスタ値を読み、ｙステ
ージに進む（Ｓ１１に進む）。一方、ＮＯの場合には、
既に条件判定を行ったので、次のｙステージに進む（Ｓ
１１に進む）。
か判定する。これは、Ｓ１からＳ８の処理で、インタロ
ックするとしてインタロックフラグをＯＮに設定し、未
だ条件分岐命令の条件判定が行われていないかを判定す
る。ＹＥＳの場合には、条件判定が行われていないの
で、Ｓ１０でレジスタ２からレジスタ値を読み、ｙステ
ージに進む（Ｓ１１に進む）。一方、ＮＯの場合には、
既に条件判定を行ったので、次のｙステージに進む（Ｓ
１１に進む）。
【００２３】Ｓ１１は、ｙステージの命令が条件分岐命
令か判定する。ＹＥＳの場合には、Ｓ１２に進む。ＮＯ
の場合には、該当処理を行う。Ｓ１２は、インタロック
フラグ６−ｙがＯＮか判定する。ＹＥＳの場合（未だ条
件分岐命令の条件判定が行われていない場合）には、Ｓ
１３でｙステージで条件判定し、 ・条件満足なら分岐先の命令をパイプラインの入口に投
入する。
令か判定する。ＹＥＳの場合には、Ｓ１２に進む。ＮＯ
の場合には、該当処理を行う。Ｓ１２は、インタロック
フラグ６−ｙがＯＮか判定する。ＹＥＳの場合（未だ条
件分岐命令の条件判定が行われていない場合）には、Ｓ
１３でｙステージで条件判定し、 ・条件満足なら分岐先の命令をパイプラインの入口に投
入する。
【００２４】・条件不満足なら次に進む。そして、一連
の処理を終了する（ＥＮＤ）。一方、ＮＯの場合には、
既に条件分岐命令の条件判定を終了しているので、次に
進み、一連の処理を終了する（ＥＮＤ）。
の処理を終了する（ＥＮＤ）。一方、ＮＯの場合には、
既に条件分岐命令の条件判定を終了しているので、次に
進み、一連の処理を終了する（ＥＮＤ）。
【００２５】以上によって、パイプライン中を流れてき
た条件分岐命令がｘ−１ステージでインタロック発生す
るとしてインタロックフラグ６−ｘがＯＮに設定されて
いた場合、ｙ−１ステージでインタロックフラグ６−ｙ
がＯＮとなっているので、このｙ−１ステージでレジス
タリード機構３−２がレジスタ２からレジスタ値を読
み、次のｙステージで条件判定機構４−２がレジスタ値
をもとに分岐を判定し、条件満足なら分岐先の命令をパ
イプライン１の入口に投入して次のステージに進み、条
件満足しないなら次のステージに進むようにしている。
一方、インタロックフラグ６−ｙがＯＦＦに設定されて
いたときは、既に条件分岐命令の条件判定が実行されて
いたので、次のステージに進む。これにより、パイプラ
イン１の入口に近いｘ−１ステージでインタロック発生
するときに、パイプライン１の出口に近いｙ−１ステー
ジでレジスタ２からレジスタ値を読み、ｙステージでこ
のレジスタ値をもとに条件判定して条件満足したときに
分岐先の命令列をパイプラインの入口から投入し、パイ
プライン１の入口の近いｘ−１でレジスタ値を読むとき
のインタロックを回避することが可能となる。
た条件分岐命令がｘ−１ステージでインタロック発生す
るとしてインタロックフラグ６−ｘがＯＮに設定されて
いた場合、ｙ−１ステージでインタロックフラグ６−ｙ
がＯＮとなっているので、このｙ−１ステージでレジス
タリード機構３−２がレジスタ２からレジスタ値を読
み、次のｙステージで条件判定機構４−２がレジスタ値
をもとに分岐を判定し、条件満足なら分岐先の命令をパ
イプライン１の入口に投入して次のステージに進み、条
件満足しないなら次のステージに進むようにしている。
一方、インタロックフラグ６−ｙがＯＦＦに設定されて
いたときは、既に条件分岐命令の条件判定が実行されて
いたので、次のステージに進む。これにより、パイプラ
イン１の入口に近いｘ−１ステージでインタロック発生
するときに、パイプライン１の出口に近いｙ−１ステー
ジでレジスタ２からレジスタ値を読み、ｙステージでこ
のレジスタ値をもとに条件判定して条件満足したときに
分岐先の命令列をパイプラインの入口から投入し、パイ
プライン１の入口の近いｘ−１でレジスタ値を読むとき
のインタロックを回避することが可能となる。
【００２６】次に、図３を用いて条件判定時のインタロ
ック例について説明する。これは、パイプライン１の全
体のステージ数をＮとし、条件が成立して分岐する場合
は条件判定の次のサイクル（ステージ）で分岐先の命令
をパイプライン１の入口に投入するものとする。インタ
ロックは、ｘ−１ステージでレジスタ２のレジスタ値を
読む場合に０サイクル、あるいはｉサイクル発生すると
する。ｉは１≦ｉ≦ｙ−ｘを満たす値である。ｙ−１ス
テージでレジスタ２のレジスタ値を読む場合は０サイク
ルとする。パイプライン１のオーバーヘッドを分岐成立
時と不成立時について従来のｘ−１ステージあるいはｙ
−１ステージのいずれか１つで条件判定して次のステー
ジで条件判定する場合と、既述した本発明の場合とにつ
いてまとめたものが図３である。以下説明する。
ック例について説明する。これは、パイプライン１の全
体のステージ数をＮとし、条件が成立して分岐する場合
は条件判定の次のサイクル（ステージ）で分岐先の命令
をパイプライン１の入口に投入するものとする。インタ
ロックは、ｘ−１ステージでレジスタ２のレジスタ値を
読む場合に０サイクル、あるいはｉサイクル発生すると
する。ｉは１≦ｉ≦ｙ−ｘを満たす値である。ｙ−１ス
テージでレジスタ２のレジスタ値を読む場合は０サイク
ルとする。パイプライン１のオーバーヘッドを分岐成立
時と不成立時について従来のｘ−１ステージあるいはｙ
−１ステージのいずれか１つで条件判定して次のステー
ジで条件判定する場合と、既述した本発明の場合とにつ
いてまとめたものが図３である。以下説明する。
【００２７】（１） 分岐成立し、インタロックが０サ
イクルの場合： （１−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐した場合、ｘサイクル分
のパイプライン中の命令がキャンセルされるので、オー
バーヘッドはｘサイクルである。
イクルの場合： （１−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐した場合、ｘサイクル分
のパイプライン中の命令がキャンセルされるので、オー
バーヘッドはｘサイクルである。
【００２８】（１−２） 常にｙ−１ステージでレジス
タ読み出し、ｙステージで条件判定して分岐した場合、
ｙサイクル分のパイプライン中の命令がキャンセルされ
るので、オーバーヘッドはｙサイクルである（ｙ＞
ｘ）。
タ読み出し、ｙステージで条件判定して分岐した場合、
ｙサイクル分のパイプライン中の命令がキャンセルされ
るので、オーバーヘッドはｙサイクルである（ｙ＞
ｘ）。
【００２９】（１−３） 本発明の図１、図２の構成の
場合、ｘ−１ステージでインタロックしないと判明した
ので、ｘ−１ステージでレジスタ読み出し、ｘステージ
で条件判定して分岐した場合、ｘサイクル分のパイプラ
イン中の命令がキャンセルされるので、オーバーヘッド
はｘサイクルである。
場合、ｘ−１ステージでインタロックしないと判明した
ので、ｘ−１ステージでレジスタ読み出し、ｘステージ
で条件判定して分岐した場合、ｘサイクル分のパイプラ
イン中の命令がキャンセルされるので、オーバーヘッド
はｘサイクルである。
【００３０】従って、この場合には、（１−３）は、常
にｘ−１ステージでレジスタ読み出し、ｘステージで条
件判定する場合と同一のオーバーヘッドが最小のｘサイ
クル（ｘ＜ｙ）である。
にｘ−１ステージでレジスタ読み出し、ｘステージで条
件判定する場合と同一のオーバーヘッドが最小のｘサイ
クル（ｘ＜ｙ）である。
【００３１】（２） 分岐成立し、インタロックがｉサ
イクルの場合： （２−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐した場合、ｉサイクル分
のインタロックと、ｘサイクル分のパイプライン中の命
令がキャンセルされるので、オーバーヘッドは（ｘ＋
ｉ）サイクルである。
イクルの場合： （２−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐した場合、ｉサイクル分
のインタロックと、ｘサイクル分のパイプライン中の命
令がキャンセルされるので、オーバーヘッドは（ｘ＋
ｉ）サイクルである。
【００３２】（２−２） 常にｙ−１ステージでレジス
タ読み出し、ｙステージで条件判定して分岐した場合、
ｙ−１ステージではインタロックが解消されているの
で、ｙサイクル分のパイプライン中の命令がキャンセル
されるので、オーバーヘッドはｙサイクルである。
タ読み出し、ｙステージで条件判定して分岐した場合、
ｙ−１ステージではインタロックが解消されているの
で、ｙサイクル分のパイプライン中の命令がキャンセル
されるので、オーバーヘッドはｙサイクルである。
【００３３】（２−３） 本発明の図１、図２の構成の
とき、ｘ−１ステージでインタロックすると判明したの
で、ｘ−１ステージでレジスタ読み出しを行わず、ｙ−
１ステージでレジスタ読み出し、ｙステージで条件判定
して分岐した場合、ｙ−１ステージではインタロックが
解消されているので、ｙサイクル分のパイプライン中の
命令がキャンセルされるので、オーバーヘッドはｙサイ
クルである。
とき、ｘ−１ステージでインタロックすると判明したの
で、ｘ−１ステージでレジスタ読み出しを行わず、ｙ−
１ステージでレジスタ読み出し、ｙステージで条件判定
して分岐した場合、ｙ−１ステージではインタロックが
解消されているので、ｙサイクル分のパイプライン中の
命令がキャンセルされるので、オーバーヘッドはｙサイ
クルである。
【００３４】従って、この場合には、（２−３）は、常
にｙ−１ステージでレジスタ読み出し、ｙステージで条
件判定する場合と同一のオーバヘッドのｙサイクルであ
り、（２−１）との大小関係はｉの値に依存するが、一
般にｉ＝ｙ−ｘであることが多いので、このケースでは
どの方式でも差がないといえる。
にｙ−１ステージでレジスタ読み出し、ｙステージで条
件判定する場合と同一のオーバヘッドのｙサイクルであ
り、（２−１）との大小関係はｉの値に依存するが、一
般にｉ＝ｙ−ｘであることが多いので、このケースでは
どの方式でも差がないといえる。
【００３５】（３） 分岐不成立し、インタロックが０
サイクルの場合： （３−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐しない場合、次の命令に
進むので、オーバーヘッドは０サイクルである。
サイクルの場合： （３−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐しない場合、次の命令に
進むので、オーバーヘッドは０サイクルである。
【００３６】（３−２） 常にｙ−１ステージでレジス
タ読み出し、ｙステージで条件判定して分岐しない場
合、次の命令に進むので、オーバーヘッドは０サイクル
である（ｙ＞ｘ）。
タ読み出し、ｙステージで条件判定して分岐しない場
合、次の命令に進むので、オーバーヘッドは０サイクル
である（ｙ＞ｘ）。
【００３７】（３−３） 本発明の図１、図２の構成の
とき、ｘ−１ステージでインタロックしないと判明した
ので、ｘ−１ステージでレジスタ読み出し、ｘステージ
で条件判定して分岐しない場合、次の命令に進むので、
オーバーヘッドは０サイクルである。
とき、ｘ−１ステージでインタロックしないと判明した
ので、ｘ−１ステージでレジスタ読み出し、ｘステージ
で条件判定して分岐しない場合、次の命令に進むので、
オーバーヘッドは０サイクルである。
【００３８】従って、この場合には、（３−１）、（３
−２）、（３−３）の全てオーバヘッドが最小の０サイ
クルである。 （４） 分岐不成立し、インタロックがｉサイクルの場
合： （４−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐しない場合、レジスタ２
のレジスタ値を読むためにｉサイクルのインタロックが
発生するので、オーバーヘッドはｉサイクルである。
−２）、（３−３）の全てオーバヘッドが最小の０サイ
クルである。 （４） 分岐不成立し、インタロックがｉサイクルの場
合： （４−１） 常にｘ−１ステージでレジスタ読み出し、
ｘステージで条件判定して分岐しない場合、レジスタ２
のレジスタ値を読むためにｉサイクルのインタロックが
発生するので、オーバーヘッドはｉサイクルである。
【００３９】（４−２） 常にｙ−１ステージでレジス
タ読み出し、ｙステージで条件判定して分岐しない場
合、インタロックが解消されており、次の命令に進むの
で、オーバーヘッドは０サイクルである。
タ読み出し、ｙステージで条件判定して分岐しない場
合、インタロックが解消されており、次の命令に進むの
で、オーバーヘッドは０サイクルである。
【００４０】（４−３） 本発明の図１、図２の構成の
とき、ｘ−１ステージでインタロックすると判明したの
で、ｘ−１ステージでレジスタ読み出しを行わず、イン
タロクが解消されたｙ−１ステージでレジスタスタ読み
出し、ｙステージで条件判定して分岐しない場合、次の
命令に進ので、オーバーヘッドは０サイクルである。
とき、ｘ−１ステージでインタロックすると判明したの
で、ｘ−１ステージでレジスタ読み出しを行わず、イン
タロクが解消されたｙ−１ステージでレジスタスタ読み
出し、ｙステージで条件判定して分岐しない場合、次の
命令に進ので、オーバーヘッドは０サイクルである。
【００４１】従って、この場合には、（４−３）はオー
バーヘッドが最小の０サイクルとなる。以上のように、
（１−３）、（３−３）、（４−３）の本発明の場合に
は、いずれも最小のオーバーヘッドとなり、（２−３）
でも他の場合とほぼ同等のオーバーヘッドとなる。
バーヘッドが最小の０サイクルとなる。以上のように、
（１−３）、（３−３）、（４−３）の本発明の場合に
は、いずれも最小のオーバーヘッドとなり、（２−３）
でも他の場合とほぼ同等のオーバーヘッドとなる。
【００４２】尚、以上の実施例の説明は、図１のレジス
タリード機構３−１と条件判定機構４−１、レジスタリ
ード機構３−２と条件判定機構４−２の２組をパイプラ
イン１中に設けたけれども、これに限られず、パイプラ
イン１中に連続してこれらの組を設けてもよい。そし
て、条件分岐命令コード中のビットに、コンパイル時に
解析していずれのステージでインタロックが解消される
かの情報を設定しておき、この情報をハードウェア（あ
るいはソフトウェア）が検出してインタロック解消の直
後のステージでレジスタ２のレジスタ値を読み、次のス
テージで条件判定し、分岐成立のときに分岐先の命令列
をパイプライン１の入口から投入し、分岐不成立のとき
に次の命令に進むようにしてもよい。また、条件分岐命
令コード中のビットに、コンパイル時に解析してインタ
ロックの有無（例えばステージーｘ−１でインタロック
の発生の有無）を付加し、これをもとに既述したｘ−１
ステージでインタロックが発生するか否かを判定するよ
うにしてもよい。
タリード機構３−１と条件判定機構４−１、レジスタリ
ード機構３−２と条件判定機構４−２の２組をパイプラ
イン１中に設けたけれども、これに限られず、パイプラ
イン１中に連続してこれらの組を設けてもよい。そし
て、条件分岐命令コード中のビットに、コンパイル時に
解析していずれのステージでインタロックが解消される
かの情報を設定しておき、この情報をハードウェア（あ
るいはソフトウェア）が検出してインタロック解消の直
後のステージでレジスタ２のレジスタ値を読み、次のス
テージで条件判定し、分岐成立のときに分岐先の命令列
をパイプライン１の入口から投入し、分岐不成立のとき
に次の命令に進むようにしてもよい。また、条件分岐命
令コード中のビットに、コンパイル時に解析してインタ
ロックの有無（例えばステージーｘ−１でインタロック
の発生の有無）を付加し、これをもとに既述したｘ−１
ステージでインタロックが発生するか否かを判定するよ
うにしてもよい。
【００４３】
【発明の効果】以上説明したように、本発明によれば、
パイプライン１で条件分岐命令の条件判定の時期として
レジスタ２依存によるインタロックが解除された時点で
速やかに行う構成を採用しているため、パイプライン１
における条件分岐命令の分岐条件判定および分岐時の命
令のキャンセルによるオーバーヘッドを少なくできる。
パイプライン１で条件分岐命令の条件判定の時期として
レジスタ２依存によるインタロックが解除された時点で
速やかに行う構成を採用しているため、パイプライン１
における条件分岐命令の分岐条件判定および分岐時の命
令のキャンセルによるオーバーヘッドを少なくできる。
【図１】本発明の１実施例構成図である。
【図２】本発明の動作説明フローチャートである。
【図３】条件判定時のインタロック例である。
１：パイプライン ２：レジスタ ３、３−１、３−２：レジスタリード機構 ４、４−１、４−２：条件判定機構 ５：制御部 ６、６−ｘ、６−ｙ：インタロックフラグ
Claims (4)
- 【請求項１】 パイプラインにおける条件分岐命令の条
件分岐を動的に判定する動的判定方式において、 レジスタ（２）からレジスタ値を読むレジスタリード機
構（３）を持つステージおよびこのステージに続いて条
件判定を行う条件判定機構（４）を持つステージを２
組、パイプライン（１）中に設け、 パイプライン（１）中を流れてきた条件分岐命令が最初
の上記レジスタリード機構（３）のステージに到達した
ときにインタロックが生じないと判明したときにレジス
タリード機構（３）がレジスタ（２）からレジスタ値を
読み、次のステージで上記条件判定機構（４）が分岐と
判定したときに分岐先の命令列をパイプラインの入口に
投入して次のステージに進み、非分岐と判定したときに
次のステージに進み、一方、インタロックを生じると判
明したときにスキップし、第２番目の上記レジスタリー
ド機構（３）のステージに到達したときにレジスタ
（２）からレジスタ値を読み、次のステージで上記条件
判定機構（４）が分岐と判定したときに分岐先の命令列
をパイプラインの入口に投入して次にステージに進み、
非分岐と判定したときに次のステージに進むように構成
したことを特徴とする条件分岐の動的判定方式。 - 【請求項２】 パイプラインにおける条件分岐命令の条
件分岐を動的に判定する動的判定方式において、 レジスタ（２）からレジスタ値を読むレジスタリード機
構（３）を持つステージおよびこのステージに続いて条
件判定を行う条件判定機構（４）を持つステージの組を
パイプライン中に連続して設け、 インタロックが解除された直後のステージで上記レジス
タリード機構（３）がレジスタ（２）からレジスタ値を
読み、次のステージの上記条件判定機構（４）が分岐と
判定したときに分岐先の命令列をパイプラインの入口に
投入して次のステージに進み、非分岐と判定したときに
次のステージに進むように構成したことを特徴とする条
件分岐の動的判定方式。 - 【請求項３】 上記インタロックの有無をコンパイル時
に解析し、その情報を条件分岐命令コードに付加し、こ
れを用いてインタロックを判定するように構成したこと
を特徴とする請求項第１項および第２項記載の条件分岐
の動的判定方式。 - 【請求項４】 上記インタロックがいずれのステージで
解除されるかをコンパイル時に解析して条件分岐命令コ
ードに付加し、これを用いてインタロックを判定するよ
うに構成したことを特徴とする請求項第２項記載の条件
分岐の動的判定方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23669691A JPH0573310A (ja) | 1991-09-18 | 1991-09-18 | 条件分岐の動的判定方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP23669691A JPH0573310A (ja) | 1991-09-18 | 1991-09-18 | 条件分岐の動的判定方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0573310A true JPH0573310A (ja) | 1993-03-26 |
Family
ID=17004418
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP23669691A Withdrawn JPH0573310A (ja) | 1991-09-18 | 1991-09-18 | 条件分岐の動的判定方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0573310A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5588050A (en) * | 1993-08-27 | 1996-12-24 | Mitsubishi Denki Kabushiki Kaisha | Method and apparatus for performing color conversion |
| US6003127A (en) * | 1995-10-04 | 1999-12-14 | Nippondenso Co., Ltd. | Pipeline processing apparatus for reducing delays in the performance of processing operations |
-
1991
- 1991-09-18 JP JP23669691A patent/JPH0573310A/ja not_active Withdrawn
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5588050A (en) * | 1993-08-27 | 1996-12-24 | Mitsubishi Denki Kabushiki Kaisha | Method and apparatus for performing color conversion |
| US5729636A (en) * | 1993-08-27 | 1998-03-17 | Mitsubishi Denki Kabushiki Kaisha | Method and apparatus for performing tone conversion |
| US5917959A (en) * | 1993-08-27 | 1999-06-29 | Mitsubishi Denki Kabushiki Kaisha | Image processing device for modifying tone characteristics of image data |
| US6125202A (en) * | 1993-08-27 | 2000-09-26 | Mitsubishi Denki Kabushiki Kaisha | Image processing device for modifying tone characteristics of image data |
| US6003127A (en) * | 1995-10-04 | 1999-12-14 | Nippondenso Co., Ltd. | Pipeline processing apparatus for reducing delays in the performance of processing operations |
| US6308263B1 (en) | 1995-10-04 | 2001-10-23 | Nippondenso Co., Ltd. | Pipeline processing apparatus for reducing delays in the performance of processing operations |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US20010044892A1 (en) | Method and system for high performance implementation of microprocessors | |
| EP0454985B1 (en) | Scalable compound instruction set machine architecture | |
| US7010787B2 (en) | Branch instruction conversion to multi-threaded parallel instructions | |
| US5386562A (en) | Circular scheduling method and apparatus for executing computer programs by moving independent instructions out of a loop | |
| KR100638501B1 (ko) | 다중 명령 컴퓨터 프로그램을 구성하는 방법 | |
| US5596732A (en) | Method of optimizing instruction sequence of compiler | |
| JPH08305577A (ja) | 最適化装置 | |
| EP0442623A2 (en) | Reducing pipeline delays in compilers by code hoisting | |
| US5822561A (en) | Pipeline data processing apparatus and method for executing a plurality of data processes having a data-dependent relationship | |
| JP3435267B2 (ja) | マイクロプロセッサ及びそのロードアドレス予想方法 | |
| US20030023838A1 (en) | Novel fetch branch architecture for reducing branch penalty without branch prediction | |
| JPH0573310A (ja) | 条件分岐の動的判定方式 | |
| US20030212881A1 (en) | Method and apparatus to enhance performance in a multi-threaded microprocessor with predication | |
| US6526573B1 (en) | Critical path optimization-optimizing branch operation insertion | |
| JPH04263323A (ja) | 機械語命令列並べ換え方式 | |
| JP2629474B2 (ja) | 並列パイプライン命令処理装置の命令実行処理方式 | |
| JP2004013603A (ja) | アセンブリコード変換方法及び装置 | |
| JP3843594B2 (ja) | プロセッサ、コンパイラ及び命令列変換装置 | |
| Berson et al. | Integrating program optimizations and transformations with the scheduling of instruction level parallelism | |
| JP2869376B2 (ja) | データ依存関係を持つ複数のデータ処理を実行するパイプラインデータ処理方法 | |
| US20040187132A1 (en) | Method and apparatus for improving dispersal performance in a processor through the use of no-op ports | |
| JPS6319906B2 (ja) | ||
| JPS63138427A (ja) | 配列に対する命令のスケジユ−リング処理方式 | |
| JPH07295810A (ja) | 命令列最適化処理方法及び装置 | |
| JPH07248923A (ja) | コンパイラ |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19981203 |