(57)【特許請求の範囲】
【請求項１】
アーキテクチャ上規定されている論理レジスタの数を上回る数の物理レジスタと、割り付けられていない物理レジスタの番号を保持するフリー・リストと、各論理レジスタにそれぞれ対応して設けられた各エントリに物理レジスタ番号が書き込まれるようになっているマッピング・テーブルとを具備するout-of-order実行の可能なスーパースカラ・アーキテクチャを採用するプロセッサのレジスタ・リネーミング方法において、
第１のサイクルでは、同時にレジスタ・リネーミングが行われる複数の命令のデスティネーション・オペランドとして示される論理レジスタ番号の各々に対し命令の順序に基づいて個別の符号を対応させ、かつ、ソース・オペランドとして示される論理レジスタ番号の各々に対し、同時にレジスタ・リネーミングが行われる命令とＲＡＷ（read-after-write）依存関係にある場合に、その依存関係にある命令のデスティネーション・オペランドに対応する符号を対応させ、
第１のサイクルに続く第２のサイクルでは、対応する符号のある論理レジスタ番号を、それぞれ対応する符号に応じて該フリー・リストから取り出され割り付けられる物理レジスタ番号にリネームする一方、対応する符号のない論理レジスタ番号を、それぞれ該マッピング・テーブルをアクセスして得られる物理レジスタ番号にリネームし、
前記第１のサイクルの処理と前記第２のサイクルの処理とをパイプライン処理として実行することを特徴とするレジスタ・リネーミング方法。
【請求項２】
アーキテクチャ上規定されている論理レジスタの数を上回る数の物理レジスタと、割り付けられていない物理レジスタの番号を保持するフリー・リストと、各論理レジスタにそれぞれ対応して設けられた各エントリに物理レジスタ番号が書き込まれるようになっているマッピング・テーブルとを具備するout-of-order実行の可能なスーパースカラ・アーキテクチャを採用するプロセッサのレジスタ・リネーミング方法において、
最終サイクルに先行するサイクルでは、同時にレジスタ・リネーミングが行われる複数の命令のデスティネーション・オペランドとして示される論理レジスタ番号の各々に対し命令の順序に基づいて個別の符号を対応させ、かつ、ソース・オペランドとして示される論理レジスタ番号の各々に対し、同時にレジスタ・リネーミングが行われる命令とＲＡＷ（read-after-write）依存関係にある場合に、その依存関係にある命令のデスティネーション・オペランドに対応する符号を対応させ、
最終サイクルでは、対応する符号のある論理レジスタ番号を、それぞれ対応する符号に応じて該フリー・リストから取り出され割り付けられる物理レジスタ番号にリネームする一方、対応する符号のない論理レジスタ番号を、それぞれ該マッピング・テーブルをアクセスして得られる物理レジスタ番号にリネームし、
前記最終サイクルに先行するサイクルの処理及び前記最終サイクルの処理をパイプライン処理として実行することを特徴とするレジスタ・リネーミング方法。
【発明の詳細な説明】
技術分野
本発明は、out-of-order実行の可能なスーパースカラ・アーキテクチャをとるプロセッサにおいて、１クロック・サイクル当り多くの命令の処理を可能とするようなレジスタ・リネーミング方式に関するものである。
背景技術
Out-of-order実行の可能なスーパースカラ・アーキテクチャをとるプロセッサにおいては、アーキテクチャ上規定されている論理レジスタの数を上回る数の物理レジスタを備えており、動的レジスタ・リネーミングという手法が活用される。
すなわち、各サイクルごとに、複数の命令においてオペランドとして示される論理レジスタ番号を比べて依存関係を調べ、その依存関係が解消するように論理レジスタ番号をそれぞれ適切な物理レジスタ番号にリネームする。
レジスタ・リネーミングを実現するには、リオーダ・バッファを用いる方式とマッピング・テーブルを用いる方式が知られている。リオーダ・バッファを用いる方式は、例えば、米国カリフォルニア州サンタクララ（Santa Clara）のインテル社（Intel Corporation）から入手可能な商標ペンティアム（Pentium）プロセッサにおいて採用されている。マッピング・テーブルを用いる方式は、Keller，R．M．"Look-Ahead Processors．“Computing Surveys，Vol．7，no．4（December 1975），pp．177-195に示されており、例えば、米国カリフォルニア州マウンテンビュー（Mountain View）のＭＩＰＳ社（MIPS Technologies，Inc．）から入手可能な商標R10000プロセッサにおいて採用されている。
リオーダ・バッファを用いる方式と比較して、マッピング・テーブルを用いる方式は、マッピング・テーブルをアクセスするためのステージが余分に必要となるが、命令間の依存性を調べる論理回路は比較的単純なものですむ。
スーパースカラ・プロセッサにおいては、より効率的にレジスタ・リネーミングを行い、１サイクル当りより多くの命令のデコード／発行を行うことによって、処理性能を向上させることが求められている。
しかしながら、１サイクル当りレジスタ・リネーミングを行う命令の数を現在の水準よりさらに増やすのは、そのための論理回路が極度に大規模なものとなるため困難であるという問題がある。
本発明は、上記問題点を解決するため創案されたものであり、その目的は、１サイクル当り処理できる命令の数を現在の水準よりさらに増やすことを可能とするレジスタ・リネーミング方式を提供することにある。
発明の開示
本発明によるレジスタ・リネーミング方式を採用するプロセッサは、フリーな、即ち、割り付けられていない物理レジスタの番号を保持するフリー・リスト、及び、各論理レジスタにそれぞれ対応して設けられた各エントリに物理レジスタ番号が書き込まれるようになっているマッピング・テーブルを備える。
本発明によるレジスタ・リネーミング方式は、命令間の依存性の検出を前処理として行うようなパイプライン化によって、１サイクル当りより多くの命令の処理を可能とするものである。
まず、同時にレジスタ・リネーミングが行われる複数の命令について以下のような前処理が行われる。
（ａ）デスティネーション・オペランドとして示される論理レジスタ番号の各々に対し、命令の順序に基づいて個別の符号を対応させる。この符号は将来フリー・リストから取り出され割り付けられる物理レジスタ番号に置き換えられるべき指標である。
（ｂ）ソース・オペランドとして示される論理レジスタ番号の各々に対し、同時にレジスタ・リネーミングが行われる命令とＲＡＷ(read-after-write)依存関係にある場合に、その依存関係にある命令のデスティネーション・オペランドに対応する符号を対応させる。
上記のような前処理の後に、命令群中にオペランドとして示される論理レジスタ番号をそれぞれ適切な物理レジスタ番号にリネームする。対応する符号のある論理レジスタ番号は、それぞれ対応する符号に応じてフリー・リストから取り出され割り付けられる物理レジスタ番号にリネームする。対応する符号のない論理レジスタ番号は、それぞれマッピング・テーブルをアクセスして得られる物理レジスタ番号にリネームする。
同じタイミングで、マッピング・テーブルの内容の更新が行われる。即ち、命令群中でデスティネーション・オペランドとして示される論理レジスタ番号にそれぞれ対応するマッピング・テーブルのエントリの内容を、それぞれ対応する符号に応じて割り付けられる物理レジスタ番号に書き換える。複数の命令において同じ論理レジスタ番号がデスティネーション・オペランドとして示されている場合には、その中の最後方に位置する命令に関する書き込みが有効となる。
以上のように、２段階で行う、即ちパイプライン化することによって、比較的単純な回路を用いて、１サイクル当りより多くの命令のレジスタ・リネーミングを行うことが可能となる。
【図面の簡単な説明】
第１図は、本発明のレジスタ・リネーミング方式を実現するために必要となるハードウェアのブロック図である。第２図は、本発明の一実施例において、ある命令列に関してレジスタ・リネーミングが行われる際の、マッピング・テーブル及び各Ｆレジスタの内容の変化を具体的に示す図である。
発明を実施するための最良の形態
以下に、本発明によるレジスタ・リネーミング方式を実現する好ましい一実施例について、図面を参照しながら説明する。なお、以下に述べる本発明によるレジスタ・リネーミング方式を採用するプロセッサの実施例は、アーキテクチャ上はR0，R1，...R7の８つの論理レジスタの存在を想定しているが、ハードウェアとしてはP00，P01，...P31の３２個の物理レジスタを備えるRISCマシンであり、１サイクル当り４つまでの命令のレジスタ・リネーミングを行えるように構成されているものとする。
図１は本発明のレジスタ・リネーミング方式を実現するために必要となるハードウェアのブロック図であって、１はマッピング・テーブル、２はフリー・リストを表している。
次に、上記各構成要素ごとにその詳細な構成を説明する。
（Ａ）マッピング・テーブル（ＭＴ）
図１に示されるように、本実施例においては、マッピング・テーブル（以下ではＭＴと記す）１はRO，R1，...R7の８つの論理レジスタにそれぞれ対応して設けられた１０〜１７の８つのエントリで構成される。ＭＴの各々のエントリは、１つの物理レジスタ番号が書き込まれる構成となっている。
（Ｂ）フリー・リスト（ＦＬ）
フリー・リスト（以下ではＦＬと記す）は、フリーな、即ち、割り付けられていない物理レジスタの番号を保持するものである。
フリーな物理レジスタを割り付ける際に、ＦＬからフリーな物理レジスタの番号が取り出される。逆に、ある物理レジスタの割り付けを解除する際に、その物理レジスタの番号がＦＬに登録されるようになっている。
図１に示されるように、本実施例においては、ＦＬ２はＦレジスタ２１、２２、２３、２４とレジスタ・ファイル２８を具備する。
各々のＦレジスタは１つの物理レジスタ番号が書き込まれる構成となっており、ＦＬからフリーな物理レジスタの番号が取り出されるのは、Ｆレジスタからとなっている。即ち、１サイクルでレジスタ・リネーミングが行われる命令の数だけＦレジスタが必要で、本実施例のプロセッサの場合、F1，F2，F3，F4の４つのＦレジスタを備えている。
ＦＬにあるレジスタ・ファイル２８は、各々のエントリに１つの物理レジスタ番号が書き込まれるようになっており、循環型のＦＩＦＯキューを構成する。即ち、割り付けが解除された物理レジスタの番号がキューの末尾に加えられ、物理レジスタ番号が取り出されたＦレジスタにキューの先頭から物理レジスタ番号が補充されるようになっている。
ついで、本実施例におけるレジスタ・リネーミングの過程を説明する。
本実施例においては、▲１▼前処理、▲２▼レジスタ・リネーミングの実行及びＭＴの内容の更新、の２ステージで、レジスタ・リネーミングが行われる。以下に各ステージごとに動作内容を説明する。
▲１▼前処理
同時にレジスタ・リネーミングが行われる複数の命令について以下のような前処理が行われる。
（１ａ）デスティネーション・オペランドとして示される論理レジスタ番号の各々に対し、＠1，＠2，...と命令順の符号を付す。本実施例においては、符号＠1，＠2，＠3，＠4は、ＦＬにあるＦレジスタF1，F2，F3，F4にそれぞれ対応するものである。
（１ｂ）ソース・オペランドとして示される論理レジスタ番号の各々に対し、同時にレジスタ・リネーミングが行われる命令とＲＡＷ(read-after-write)依存関係にある場合に、その依存関係にある命令のデスティネーション・オペランドに付される符号を付す。即ち、２番目以降に位置する命令の各々において、ソース・オペランドとして示される論理レジスタ番号の各々をその命令以前に位置する命令のデスティネーション・オペランドとして示される論理レジスタ番号と比較し、一致する場合に同じ符号を付す。一致するものが複数個存在する場合には、その中の最後方に位置する命令におけるものを選択する。
▲２▼レジスタ・リネーミングの実行及びＭＴの内容の更新
上記のような前処理の後に、命令群中にオペランドとして示される論理レジスタ番号をそれぞれ適切な物理レジスタ番号にリネームし、ＭＴの内容を更新する。具体的には、以下のような処理が行われる。
（２ａ）符号を付された論理レジスタ番号は、それぞれ付された符号に対応してＦＬから取り出され割り付けられる物理レジスタ番号にリネームする。符号を付されていない論理レジスタ番号は、それぞれＭＴをアクセスして得られる物理レジスタ番号にリネームする。
（２ｂ）命令群中でデスティネーション・オペランドとして示される論理レジスタ番号にそれぞれ対応するＭＴのエントリの内容を、それぞれ付された符号に対応して割り付けられる物理レジスタ番号に書き換える。複数の命令において同じ論理レジスタ番号がデスティネーション・オペランドとして示されている場合には、その中の最後方に位置する命令に関する書き込みが有効となる。
以上が、本実施例におけるレジスタ・リネーミングの過程であるが、ついで、具体的な動作例について説明する。いま、本実施例のプロセッサにおいて、以下のような４つの命令のレジスタ・リネーミングを行うものとしよう。
命令１  mul  R0，R1，R2    ；R0＝R1*R2
命令２  mul  R1，R3，R4    ；R1＝R3*R4
命令３  add  R0，R0，R1    ；R0＝R0＋R1
命令４  div  R0，R0，R5    ；R0＝R0/R5
以上の命令列は、それ以前に位置する命令によって、R1，R2，R3，R4，R5の各レジスタにそれぞれデータD1，D2，D3，D4，D5が入るものとして、{(D1*D2)＋(D3*D4)}/D5を計算し、レジスタR0に格納する、というものである。
本実施例のプロセッサにおいて、上記命令列に関してレジスタ・リネーミングが行われる過程を、以下に詳細に説明する。
まず、レジスタ・リネーミングのための前処理が次のように行われる。
命令１  mul  R0(＠1)，R1(none)，R2(none)
命令２  mul  R1(＠2)，R3(none)，R4(none)
命令３  add  R0(＠3)，R0(＠1)，R1(＠2)
命令４  div  R0(＠4)，R0(＠3)，R5(none)
即ち、各命令において命令コードの次に示されるデスティネーション・レジスタ・オペランドに対して、それぞれ順に符号＠1，＠2，＠3，＠4を付す。
２番目以降に位置する命令の各々において、各ソース・レジスタ・オペランドをその命令以前に位置する命令のデスティネーション・レジスタ・オペランドと比較し、一致する場合に同じ符号を付す。一致するものが複数個存在する場合には、その中の最後方に位置する命令におけるものを選択する。
命令１においては、いずれのソース・オペランドにも符号を付すことはない。実際には、「符号を付さない」ソース・オペランドにはデフォルトの符号（例えば＠０）が付されることになる。
命令２においては、各ソース・オペランドを命令１のデスティネーション・オペランドR0と比較し、この場合一致するものはないので符号を付すことはない。
命令３においては、各ソース・オペランドを命令１及び２のデスティネーション・オペランドと比較し、この場合、第１ソース・オペランドが命令１のデスティネーション・オペランドと、第２ソース・オペランドが命令２のデスティネーション・オペランドと一致するので、それぞれ符号＠1，＠2を付す。
命令４においては、各ソース・オペランドを命令１、２及び３のデスティネーション・オペランドと比較し、この場合、第１ソース・オペランドが命令１及び３のデスティネーション・オペランドと一致するので、後の方の命令３における符号＠3を付す。
以上のようなレジスタ・リネーミングのための前処理は、適切な回路を用いることにより１サイクルで実現される。
次サイクルにおいて、レジスタ・リネーミングの実行及びＭＴの内容の更新が行われるが、この時点のＭＴ及びＦＬにある各Ｆレジスタの内容が図２（Ａ）に示されるようなものであるとしよう。
符号を付されたレジスタ・オペランドは、それぞれ付された符号に対応してＦＬから取り出され割り付けられる物理レジスタ番号にリネームする。また、符号を付されていないレジスタ・オペランドは、それぞれＭＴを論理レジスタ番号でアクセスして得られる物理レジスタ番号にリネームし、与えられた命令列は次のような内容に読み替えられる。
命令１  mul  P19，P03，P22
命令２  mul  P08，P29，P05
命令３  add  P27，P19，P08
命令４  div  P21，P27，P07
また、命令１〜４におけるデスティネーション・オペランドにそれぞれ対応するＭＴのエントリの内容を、それぞれ付された符号に対応して割り付けられる物理レジスタ番号に書き換える。ここでは、図２（Ｂ）に示されるように、R0及びR1に対応するＭＴのエントリの内容がそれぞれP21、P08に書き換えられている。R0に関しては、P19，P27，P21の３重の割り付けが存在するが、ＭＴには最後のP21が書き込まれる。さらに、図２（Ｂ）に示されるように、物理レジスタ番号が取り出された各Ｆレジスタにフリーな物理レジスタの番号P31，P01，P17，P14が補充されている。
以上が、本実施例のプロセッサにおける、与えられた命令列に関するレジスタ・リネーミングの過程である。
また、前処理の段階で、マッピング・テーブルの内容の更新に関する論理レジスタ番号と符号の対応関係を確定しておくような構成とすることもできる。即ち、前処理の段階で、同時にレジスタ・リネーミングが行われる複数の命令において、同じ論理レジスタ番号がデスティネーション・オペランドとして示されている場合、その中の最後方に位置する命令以外は、マッピング・テーブルの内容の更新に関しては、無効であることを確定しておくようにする。
例えば、上述の動作例で、前処理の段階で、
命令１  R0→＠１：無効
命令２  R1→＠２：有効
命令３  R0→＠３：無効
命令４  R0→＠４：有効
と確定しておき、次サイクルにおいて、有効の場合のみ、付された符号に対応して割り付けられる物理レジスタ番号の書き込みを可とする。
以上のように、マッピング・テーブルの内容の更新に関しても前処理を行うような構成とすることで、さらなる回路の簡素化が可能となる。
産業上の利用可能性
以上のように、本発明のレジスタ・リネーミング方式によれば、命令間の依存性の検出を前処理として行うようなパイプライン化によって、比較的単純な回路を用いて、１サイクル当りより多くの命令の処理が可能となる。
【図１】
0003592673.tif 000002
【図２】
0003592673.tif 000003