(57)【要約】【課題】命令発行の際に、実行性能の観点で効率的な発行グループの決定（命令グルーピング）を、簡素なハードウェアで実現する。【解決手段】複数の演算器に発行する予定の複数の命令を格納する命令バッファ４０１〜４０３と、命令バッファに格納された任意の２つの命令間に存在する依存関係である第１依存関係と、命令バッファに格納された各命令と発行済みの各命令との間に存在する依存関係である第２依存関係とを検出し、命令バッファに格納されている複数の命令のうち、第１依存関係及び第２依存関係のいずれをも有しない命令のグループを、複数の演算器に発行することが可能な命令のグループとして決定する依存関係検出部４３１及び４３２と、決定されたグループに含まれる命令を、複数の演算器に発行するディスパッチ部４４１〜４４３とを備える。【選択図】図４
2010262542.tif 000002
【特許請求の範囲】
【請求項１】
複数の命令を複数の演算器に同時発行可能なプロセッサであって、
複数の演算器に発行する予定の複数の命令を格納する命令バッファと、
前記命令バッファに格納された任意の２つの命令間に存在する依存関係である第１依存関係と、前記命令バッファに格納された各命令と発行済みの各命令との間に存在する依存関係である第２依存関係とを検出し、前記命令バッファに格納されている前記複数の命令のうち、前記第１依存関係及び前記第２依存関係のいずれをも有しない命令のグループを、前記複数の演算器に発行することが可能な命令のグループとして決定するグループ決定部と、
前記グループ決定部で決定された前記グループに含まれる前記命令を、前記複数の演算器に発行するディスパッチ部と
を備えるプロセッサ。
【請求項２】
前記グループ決定部は、
前記命令バッファに格納された各命令によって、定義又は参照されるリソースの情報と実行される演算器の情報とを特定するリソースデコード部と、
前記リソースデコード部が特定した前記リソースの情報及び前記演算器の情報に基づいて、前記第１依存関係及び前記第２依存関係を検出する依存関係検出部とを含む
請求項１記載のプロセッサ。
【請求項３】
前記依存関係検出部は、前記命令バッファに格納された任意の２つの命令が、同一のリソースを定義もしくは参照する場合、又は、同一の演算器で実行される場合に、前記任意の２つの命令間に前記第１依存関係が存在すると判断する
請求項２記載のプロセッサ。
【請求項４】
前記依存関係検出部は、前記命令バッファに格納された各命令と発行済みの各命令とを比較し、２つの命令が、同一のリソースを定義もしくは参照する場合、又は、同一の演算器で実行される場合に、前記２つの命令間に前記第２依存関係が存在すると判断する
請求項２又は３記載のプロセッサ。
【請求項５】
前記グループ決定部は、さらに、
前記命令バッファに格納された命令ごとに、当該命令の前記演算器上での実行が完了するまでのサイクル数を抽出するサイクルデコード部と、
前記サイクルデコード部での抽出結果に基づいて、前記命令バッファに格納された命令ごとに、当該命令によって定義されるリソースの定義が完了するまでに所定のサイクル数以上を要するリソースを検出し、検出した前記リソースを、次サイクルにおいて参照することができない非レディ状態であると判定する非レディ検出部とを含み、
前記依存関係検出部は、前記命令バッファに格納された命令ごとに、当該命令が、発行済みの命令によって定義されるリソースが非レディ状態であると判定された前記リソースを参照する場合に、当該命令と前記発行済みの命令との間に前記第２依存関係が存在すると判断する
請求項４記載のプロセッサ。
【請求項６】
前記グループ決定部は、さらに、前記レディ検出部における判定結果に基づいて、リソースごとに、当該リソースが非レディ状態であるか否かを記憶しているリソース状態記憶テーブルを含み、
前記依存関係検出部は、前記リソース状態記憶テーブルを参照することにより、前記第２依存関係が存在するか否かを判断する
請求項５記載のプロセッサ。
【請求項７】
前記リソース状態記憶テーブルは、リソースごとに、当該リソースが次サイクルにおいて参照することができるレディ状態であるか否かを示すレディフラグと、当該リソースの前記非レディ状態が継続するサイクル数を示す非レディ継続サイクル数とを記憶している
請求項６記載のプロセッサ。
【請求項８】
前記リソース状態記憶テーブルは、前記ディスパッチ部により前記グループに含まれる前記命令が、前記複数の演算器に発行されるごとに、前記リソース状態記憶テーブルに記憶されている前記非レディ継続サイクル数を所定数減算する
請求項７記載のプロセッサ。
【請求項９】
前記リソース状態記憶テーブルは、前記命令バッファに格納された複数の命令が同一リソースを定義する場合、前記サイクルデコード部での抽出結果に基づいて、各命令の前記サイクル数のうち、最大のサイクル数を、前記リソース状態記憶テーブルに、前記同一リソースに対応する前記非レディ継続サイクル数として格納する
請求項７又は８記載のプロセッサ。
【請求項１０】
前記リソース状態記憶テーブルに記憶されている前記レディフラグが既に前記非レディ状態を示しており、かつ前記非レディ継続サイクル数として既にサイクル数が設定されているリソースについて、前記命令バッファに格納されている命令が当該リソースを定義する場合には、前記命令バッファに格納されている前記命令の前記演算器上での実行が完了するまでのサイクル数が前記非レディ継続サイクル数よりも大きい場合にのみ、前記非レディ継続サイクル数に、前記命令バッファに格納されている前記命令の前記演算器上での実行が完了するまでのサイクル数を上書きする
請求項８記載のプロセッサ。
【請求項１１】
前記依存関係検出部は、前記リソース状態記憶テーブルの前記レディフラグを参照することにより前記第２依存関係を検出する
請求項７〜１０のいずれか１項に記載のプロセッサ。
【請求項１２】
前記グループ決定部は、前記依存関係検出部により前記第１依存関係及び前記第２依存関係のいずれかが検出された場合、前記命令バッファに記憶されている命令のうち、検出された依存関係を有する命令よりも実行順で直前までの命令を、次サイクルに前記複数の演算器に発行することが可能な命令のグループとして決定する
請求項１１記載のプロセッサ。
【請求項１３】
前記グループ決定部は、前記第２依存関係に基づいて、新たな前記グループを決定した場合、前記第２依存関係を求める際に参照した前記レディフラグに前記レディ状態であることを示す値を設定し、当該レディフラグに対応するエントリの前記非レディ継続サイクル数を０に設定する
請求項１２記載のプロセッサ。
【請求項１４】
前記グループ決定部により、前記グループが決定された後、当該グループに含まれる命令の実行順で直後の命令を、次サイクルで発行される命令のグループの先頭命令とする
請求項１２又は１３に記載のプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数命令を並列実行可能なプロセッサに関し、特に、スーパースカラ型のアーキテクチャを有するプロセッサに関する。
【背景技術】
【０００２】
プロセッサは、メモリに格納された命令シーケンスを実行する。実行性能を向上させるには、命令シーケンスを実行する際に、並列実行可能な複数の命令を同時実行させる方がよい。
【０００３】
複数命令を並列実行可能なプロセッサアーキテクチャに、スーパースカラというアーキテクチャが存在する。スーパースカラでは、あるリソース（レジスタ等）の定義が、既に実行中の命令により完了していない場合、そのリソースを参照する命令の発行を止めて、次の依存関係の無い命令を先に実行するハードウェアによる制御が行なわれる。
【０００４】
しかしながら、上記スーパースカラでは、例外が発生した時点におけるプロセッサの状態を、保持及び復元するための複雑な機構が必要である。
【０００５】
一方、複数の命令を並列実行可能なプロセッサアーキテクチャにＶＬＩＷ（Very Long Instruction Word）というアーキテクチャが存在する。ＶＬＩＷでは、コンパイラが並列実行可能な命令を予めコンパイル時に抽出し、並列実行可能な複数命令で構成された並列実行コードを生成する。
【０００６】
ＶＬＩＷでは、プロセッサは比較的シンプルな構成となる。しかしながら、ＮＯＰ命令を挿入することによるコードサイズの増加、及び既存命令セットとの非互換という問題を有している。
【０００７】
上述のように、複数命令を並列実行する方式には、スーパースカラ、ＶＬＩＷが存在し、各々に長所短所が存在する。
【０００８】
命令発行制御の方法の一例が特許文献１に開示されている。特許文献１では、予め１つ以上の命令で構成される命令グループ単位で、命令の発行を制御している。
【０００９】
また、特許文献１によれば、予め定められた発行グループ内の個々の命令が定義及び参照するリソース（レジスタファイル等）の情報とそのリソースの待ち時間情報とを格納するテーブルを用意している。その待ち時間情報を活用する事によって、既に発行されている命令グループ内の命令との依存関係を検出し、依存が存在する場合には、該当する命令グループ内の命令の発行を止め、依存関係の無い命令グループ内の命令を先に発行するという手法を提案している。
【００１０】
上記発行制御の方法によって、命令発行前に依存関係にある１つ以上の命令を有する命令グループを抽出し、命令スケジューリングを実施する事が可能となる。
【００１１】
命令発行制御の方法の他の一例が特許文献２に開示されている。特許文献２は、スレッド内で同時実行可能な命令の数をカウントし、スレッド処理に費やすサイクル数を計算し、優先度を考慮し、複数のスレッド内の命令を効率的に発行する装置に関する発明である。
【００１２】
特許文献２の段落００４０〜段落００４５では、既存ハードウェアで実施される一般的な命令グルーピングの手法について、説明されている。
【００１３】
上記説明における、命令発行前の時点で実施される既存の命令グルーピング機構においては、発行しようとしている命令グループ内の命令に限って依存関係を抽出し、適宜発行グループの制御が実施される。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特許第３９８４７８６号公報
【特許文献２】特開２００８−１２３０４５号公報（段落００４０〜００４５）
【発明の概要】
【発明が解決しようとする課題】
【００１５】
しかしながら、特許文献１に記載の発行制御方法では、命令キュー内に依存関係のある命令を保持し、その依存関係を逐次検出しながら、複数の命令グループに対して発行制御を実施する必要がある。また、命令発行時に命令グループ単位で動的に命令スケジューリングを実行するため、命令発行後に例外が発生した場合のプロセッサの状態を復元するためのハードウェアの投資が必要になる。したがって、上記文献の制御方法は、上記２点の理由によりハードウェアが複雑化するという問題がある。
【００１６】
また、特許文献２に記載の手法では、上記グルーピングの制約により、命令グループ内の命令間の依存関係、及び命令グループを跨った命令間の依存関係を考慮したグルーピングによる発行制御が実施できない。このため、命令実行時に、本来適切にグルーピングが実施されていれば発生しなかった、ペナルティサイクルが生じる場合がある。したがって、既存の命令発行前の時点における命令グルーピング機構では、最適な性能が達成できていないケースが発生する場合が考えられるという問題がある。
【００１７】
本発明は、上述の課題を解決するためになされたものであり、命令発行の際に、実行性能の観点で効率的な発行グループの決定（命令グルーピング）を、簡素なハードウェアで実現できるプロセッサを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記目的を達成するために、本発明に係るプロセッサは、複数の命令を複数の演算器に同時発行可能なプロセッサであって、前記複数の演算器への最後の命令発行のサイクルの次サイクルにて前記複数の演算器に発行する予定の複数の命令を格納する命令バッファと、前記命令バッファに格納された任意の２つの命令間に存在する第１依存関係と、前記命令バッファに格納された各命令と発行済みの各命令との間に存在する第２依存関係とを求め、前記命令バッファに格納されている前記複数の命令のうち、前記第１依存関係及び前記第２依存関係を有しない命令のグループを、前記次サイクルにて前記複数の演算器に発行することが可能な命令のグループとして決定するグループ決定部と、前記グループ決定部で決定された前記グループに含まれる前記命令を、前記次サイクルにおいて、前記複数の演算器に発行するディスパッチ部とを備える。
【００１９】
既存ハードウェアの命令グルーピング機構で実施されるグルーピングにより、命令グループ間でペナルティサイクルが発生する本質的な原因は、既存ハードウェアでは命令バッファに格納された命令間の依存関係しか考慮しておらず、既に発行された命令グループとの依存関係を検出する事ができないからである。
【００２０】
この構成によると、命令バッファに格納された命令間の依存関係だけでなく、すでに発行済みの命令との依存関係をも参照して、次サイクルにて発行される命令のグループを決定している。このため、発行済みの命令グループ間で発生するペナルティを緩和することができ、命令発行の際に、実行性能の観点で効率的な発行グループの決定（命令グルーピング）を、簡素なハードウェアで実現できる。
【００２１】
なお、本発明は、このような特徴的な処理部を備えるプロセッサとして実現することができるだけでなく、プロセッサに含まれる特徴的な処理部をステップとする命令発行制御方法として実現することができる。また、命令発行制御方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現することもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００２２】
本発明によると、発行しようとする命令バッファ内に存在する命令間の依存関係だけでなく、命令バッファ内に存在する命令と既に発行された命令グループ内の命令との依存関係も検出し命令グルーピングを行なう。このため、発行された命令グループ間のペナルティを緩和し、性能向上に寄与する。
【００２３】
上記性能向上に関する理由をより詳細に考察すると、定性的には下記２点の様に説明できる。
【００２４】
（１）本来先行して発行可能である命令が、既に発行された命令と依存関係を持つ後続の命令と同時発行されるために、既に発行された命令が完了するまで、依存関係を持つ後続命令と共に、発行を待たされるというケースを解消できるから。
【００２５】
（２）既に発行された命令と依存関係を持つ後続命令を、命令発行の先頭命令として、グルーピングを実施した方が並列度が向上する場合において、その後続命令が先頭命令とされない事によるグルーピング効率の悪化が削減できるから。
【図面の簡単な説明】
【００２６】
【図１】理想的な命令グルーピング及び既存ハードウェアでの命令グルーピングによる実行性能を比較する図である。
【図２】既存ハードウェア（従来のプロセッサ）の構成を示す図である。
【図３】既存ハードウェアにより実施される命令グルーピングの詳細を示す図である。
【図４】本発明の実施の形態に係るプロセッサの構成を示す図である。
【図５】リソース状態記憶テーブルの一例を示す図である。
【図６】本発明の実施の形態に係るプロセッサにより実施されるグルーピングの詳細を示す図である。
【図７】本発明の実施の形態に係るプロセッサでの命令グルーピングによる実行性能を示す図である。
【図８】非レディ状態のリソースの検出処理のフローチャートである。
【図９】リソース状態記憶テーブルへのデータの書込み処理のフローチャートである。
【図１０】命令発行の制御方法のフローチャートである。
【発明を実施するための形態】
【００２７】
まず、一般的なスーパースカラ型のアーキテクチャを有するプロセッサについて説明した後に、本実施の形態に係るプロセッサについて説明する。
【００２８】
図１は、２種類の命令グルーピングによる実行性能を比較した図である。
【００２９】
図１の比較図は、命令コード１０１と、理想的結果１０２と、従来結果１０３との各欄より構成される。
【００３０】
命令コード１０１には、ループ処理を構成する命令コードが示されており、命令コード１０１は、分岐先のラベルと、命令コードのニーモニック表現と、命令が参照又は定義するリソースとからなる。
【００３１】
ここで、命令コード１０１に示される各命令が実行されるプロセッサ（図示せず）は、最大３命令を並列実行可能であり、ロード・ストア演算器、積和演算器、算術演算器及び分岐実行ユニットが各１要素で構成されているものとする。しかし、本発明の本質は、プロセッサの最大並列実行可能数、演算器の種類及び個数等の構成によりなんら制限されるものではない。
【００３２】
命令コード１０１内のｌｄ命令及びｌｄｐ命令は、それぞれ、ロード・ストア演算器で実行される、ロード命令及びロードペア命令である。ｍａｃ命令は積和演算器で実行される、積和演算命令である。ａｄｄ命令は算術演算器で実行される、加算命令である。ｂｒ命令は分岐実行ユニットで実行される、分岐命令である。上記命令の動作の詳細については、当業者ならば容易に推察できよう。このため、その詳細な説明はここでは繰り返さない。
【００３３】
ここで、ｌｄ命令、ｌｄｐ命令は、実行完了までのサイクル数、即ちレイテンシは２サイクルであり、その他の命令のレイテンシは１サイクルである事を想定する。しかし、これらの実行サイクルは仮の定義であり、本発明の本質は、これらのサイクル数の定義によりなんら制限されるものではない。
【００３４】
図１の比較表の理想的結果１０２は、理想的な命令のグルーピング結果を示す。理想的結果１０２のＧｒｐの列に“／／”が存在する場合、その行までの命令コードが発行グル
ープ（同一サイクルで発行される命令のグループ）として定義され、その直後の命令が新たな発行グループの先頭命令コードとして定義される。また、Ｐｅｎａｌｔｙの列はペナルティサイクルを示し、その行までの発行グループが、次発行グループ以降の何れかの命令実行をストールさせる場合のペナルティサイクル数を示すものとする。
【００３５】
理想的結果１０２での命令グルーピングの結果を下記に示す。
【００３６】
[ld r1,(r4+)]   [mac acc,r2,r5]   [add r0,-1]     （第１命令グループ）
[ld r5,(r4+)]                                     （第２命令グループ）
[mac acc,r3,r1] [ldp r2,r3,(r6+)] [br r0,0 L0001] （第３命令グループ）
【００３７】
理想的結果１０２は、命令グループ間にペナルティサイクルが発生しない、即ち実行性能の観点で効率が良い、命令グルーピングの結果を表す。
【００３８】
なぜなら、理想的結果１０２では、第１命令グループ（ｌｄ，ｍａｃ，ａｄｄ）と第２命令グループ（ｌｄ）との間、及び第２命令グループ（ｌｄ）と第３命令グループ（ｍａｃ，ｌｄｐ，ｂｒ）との間で、ペナルティサイクルが発生していないからである。つまり、命令グループ間に依存関係にある場合には、全て命令実行開始までに、リソースの参照が可能となっている。
【００３９】
図１の比較表の従来結果１０３は、既存の命令グルーピング処理による命令グルーピングの結果を示す。従来結果１０３での命令グルーピングの結果を下記に示す。
【００４０】
[ld r1,(r4+)]     [mac acc,r2,r5] [add r0,-1]  （第１命令グループ）
[ld r5,(r4+)]     [mac acc,r3,r1]              （第２命令グループ）
[ldp r2,r3,(r6+)] [br r0,0 L0001]              （第３命令グループ）
【００４１】
従来結果１０３では、命令グループ間での依存関係を考慮していないため、第１命令グループ（ｌｄ，ｍａｃ，ａｄｄ）と第２命令グループ（ｌｄ，ｍａｃ）との間に真の依存関係によるペナルティサイクルが発生する。なぜなら、ｌｄ命令が定義するレジスタｒ１を次のサイクルで、ｍａｃ命令が参照するためである。ｌｄ命令の実行完了までには２サイクルを要するため、ｍａｃ命令の実行開始までに１サイクルのペナルティサイクルが発生するからである。
【００４２】
結局、理想的結果１０２では、下記に示す様にループ１回の実行に４サイクル要する。
【００４３】
３（３命令グループの発行サイクル）＋１（ｌｄｐのループ運搬依存サイクル）＝４
【００４４】
一方、従来結果１０３では、下記に示す様にループ１回の実行に５サイクル要する。
【００４５】
３（３命令グループの発行サイクル）＋１（レジスタｒ１の依存に関するペナルティサイクル）＋１（ｌｄｐのループ運搬依存サイクル）＝５
【００４６】
高々１サイクルの差であるが、繰り返し実行されるループ内のペナルティサイクルであるため、メディア処理等では２５％の性能劣化として問題が顕在化してしまう。
【００４７】
次に、従来結果１０３では、上記のようなグルーピングを実施してしまうのかの理由について詳細に説明を行う。図２は、既存ハードウェア（従来のプロセッサ）の構成を示す図である。図２では、インオーダーな並列実行を前提とした、一般的な命令発行制御が行なわれる。なお、図２では、３つの命令を並列実行可能なプロセッサについて示しているが、本発明の本質は並列実行数により、なんら制限されるものではない。
【００４８】
プロセッサは、命令バッファ２０１〜２０３と、リソースデコード部２１１〜２１３と、依存関係検出部２３１及び２３２と、ディスパッチ部２４１〜２４３とを含む。
【００４９】
命令バッファ２０１〜２０３の各々は、命令キャッシュ（図示せず）からフェッチした命令を格納する記憶装置である。
【００５０】
リソースデコード部２１１〜２１３は、それぞれ、命令バッファ２０１〜２０３に格納された命令が定義又は参照するリソースの情報、及び当該命令が実行される演算器の情報等を抽出する処理部である。
【００５１】
依存関係検出部２３１及び２３２の各々は、命令が実行される演算器の依存関係、及び命令が定義又は参照するリソースの依存関係を検出する処理部である。つまり、依存関係検出部２３１及び２３２の各々は、共通の演算器を使用する命令間の依存関係、共通のリソースを定義又は参照する命令間の依存関係を検出する。
【００５２】
ディスパッチ部２４１〜２４３は、命令グループに含まれる各命令を適宜演算器に発行する処理部である。
【００５３】
図３に、図２に示した既存ハードウェアにより実施されるグルーピングの詳細を示す。まず命令バッファ２０１、２０２、２０３にそれぞれ格納された命令３０１、３０２、３０３の間には資源制約、及びデータ依存制約のいずれもが存在しない。このため、最大並列実行数の命令である全３命令が、ディスパッチ部２４１、２４２、２４３によりディスパッチされ、命令３１１、３１２、３１３が各演算器へ発行される。
【００５４】
次に命令バッファ２０１、２０２、２０３には、命令３２１、３２２、３２３がそれぞれ格納される。ここで命令３２１と命令３２３はどちらもロード・ストア演算器で実行される命令であり、同時に実行することができないため、資源制約が発生する。したがって、命令３３１と命令３３２のみがディスパッチされる。
【００５５】
最後に命令バッファ２０１、２０２には、命令３４１、３４２がそれぞれ格納される。命令３４１、３４２間には資源制約、データ依存制約のいずれも存在しないため、命令３５１、３５２がディスパッチされる。
【００５６】
この時、第１命令グループの命令３１１（ｌｄ命令）が定義するレジスタｒ１を、第２命令グループの命令３３２（ｍａｃ命令）が参照するため、第１命令グループと第２命令グループとの間には、データ依存関係、即ち真の依存関係が発生する。ｌｄ命令のレイテンシは２サイクルである。このため、第２命令グループの命令の実行開始までに１サイクルのペナルティが発生してしまう。したがって、図１の比較図では、従来結果１０３のａｄｄ命令の列のＰｅｎａｌｔｙの項目に“１”が示されている。
【００５７】
前述の通り、理想的な命令グルーピングではペナルティサイクルが発生していなかったので、既存ハードウェアの命令グルーピングでは、５／４＝１．２５、即ち２５％の性能劣化が顕在化する事になる。
【００５８】
図４は、本発明の実施の形態に係るプロセッサの構成を示す図である。本実施の形態に係るプロセッサは、最大３命令を並列実行可能なプロセッサである。しかし、本発明の本質は最大並列実行可能数になんら制限されるものではない。
【００５９】
プロセッサは、命令バッファ４０１〜４０３と、リソースデコード部４１１〜４１３と、ディスパッチ部４４１〜４４３と、サイクルデコード部４５１〜４５３と、非レディ検出部４６１〜４６３と、依存関係検出部４３１及び４３２と、リソース状態記憶テーブル４７０とを含む。
【００６０】
命令バッファ４０１〜４０３、リソースデコード部４１１〜４１３及びディスパッチ部４４１〜４４３は、図２で示した既存ハードウェアにおける命令バッファ２０１〜２０３、リソースデコード部２１１〜２１３及びディスパッチ部２４１〜２４３と、それぞれ同じ機能を有する構成要素である。このため、その詳細な説明はここでは繰り返さない。
【００６１】
以下では、新規に追加された構成要素について説明する。
【００６２】
サイクルデコード部４５１、４５２、４５３は、それぞれ、命令バッファ４０１、４０２、４０３に格納されている命令のレイテンシをデコードする処理部である。
【００６３】
非レディ検出部４６１、４６２、４６３は、サイクルデコード部４５１、４５２、４５３からそれぞれ出力される命令バッファ４０１、４０２、４０３に格納された命令のレイテンシ、及びリソースデコード部４１１、４１２、４１３からそれぞれ出力される命令バッファ４０１、４０２、４０３に格納された命令が定義するリソース情報を入力として、レイテンシが２以上の場合、各命令が定義するリソースを命令グループ発行後のサイクルにて非レディと判定する。つまり、命令グループ発行後のサイクル（次サイクル）において、そのリソースを参照又は定義することができないと判定する。
【００６４】
具体的には以下の様になる。
【００６５】
例えば、命令バッファ４０１に命令コード［ｌｄ  ｒ１，（ｒ４＋）］が格納されているものとする。この命令はレジスタｒ４を参照することにより指定されるアドレスのメモリの値をレジスタｒ１に定義する命令であり、レイテンシは２である。したがって、この命令で定義されるレジスタｒ１は、ｌｄ命令発行後のサイクルにおいては、非レディと判定される。
【００６６】
上記非レディと判定されたリソース（レジスタｒ１）は、リソース状態記憶テーブル４７０に登録される。
【００６７】
ここで、リソース状態記憶テーブル４７０について説明する。図５は、リソース状態記憶テーブル４７０の一例を示す図である。リソース状態記憶テーブル４７０は、リソースごとにリソースの状態を記憶する記憶装置であり、リソースごとに、リソース番号４７１と、レディフラグ４７２と、非レディ継続サイクル数４７３とを記憶している。
【００６８】
レディフラグ４７２は、次発行サイクルからリソースを参照可能か否かを示すフラグである。レディフラグ４７２が１の場合には、次発行サイクルからリソースを直ちに参照することが可能である、即ちリソースは非レディではないこと（レディであること）を示す。レディフラグ４７２が０の場合には、次発行サイクルからリソースを直ちに参照することが不可能である、即ちリソースは非レディであることを示す。
【００６９】
非レディ継続サイクル数４７３は、非レディの状態が継続するサイクル数を示す。
【００７０】
上述のｌｄ命令のレジスタｒ１に話を戻すと、レジスタｒ１は、ｌｄ命令後のサイクルにおいて非レディと判定されることより、リソース状態記憶テーブル４７０は、非レディ検出部４６１から出力された非レディ情報を受けて、レジスタｒ１に対応するテーブルエントリのレディフラグ４７２が１である場合には、レディフラグ４７２を０に変更し、非レディ継続サイクル数４７３に２を登録する。
【００７１】
既にレディフラグ４７２が０の場合には、リソース状態記憶テーブル４７０は、新規に登録しようとする非レディ継続サイクル数と、非レディ継続サイクル数４７３に登録されている既存のサイクル数とを比較する。リソース状態記憶テーブル４７０は、新規に登録しようとする非レディ継続サイクル数のほうが大きい場合には、新規の非レディ継続サイクル数を、非レディ継続サイクル数４７３に登録し、新規に登録しようとする非レディ継続サイクル数のほうが小さい場合には、新規のサイクル数を非レディ継続サイクル数４７３に登録することは行なわずに、既存のサイクル数が非レディ継続サイクル数４７３に継続して登録されたままとなる。以上、非レディ検出部４６１から出力される非レディ情報に関する、リソース状態記憶テーブル４７０の処理について説明したが、非レディ検出部４６２及び４６３から出力される非レディ情報も同様の処理が並列に実施されるものとする。
【００７２】
依存関係検出部４３１、４３２は、既存ハードウェアと同様に、命令バッファ４０１、４０２、４０３に格納された命令間の依存関係（請求項における第１依存関係）だけでなく、命令バッファ４０１、４０２、４０３に格納された各命令とリソース状態記憶テーブル４７０の各リソースのエントリとの依存関係（請求項における第２依存関係）を検出する。即ち、リソース状態記憶テーブル４７０に登録された、各リソースのエントリのレディフラグ４７２を参照し、非レディ状態であるエントリと依存関係にある命令の検出を行う。
【００７３】
依存関係検出部４３１、４３２は、命令バッファ４０１、４０２、４０３に格納された命令間に依存を検出するか、又は命令バッファ４０１、４０２、４０３に格納された各命令とリソース状態記憶テーブル４７０の各リソースに対応したエントリとの依存を検出した場合、依存を検出した命令の直前の命令を発行グループの区切りとする。発行グループの区切りまでの命令がディスパッチ部４４１、４４２、４４３に格納され、ディスパッチ部４４１、４４２、４４３に格納された発行グループの区切りまでの命令が適宜演算器ユニットに発行される。
【００７４】
もし、リソース状態記憶テーブル４７０のエントリの依存関係によって、発行グループが決定された場合、非レディ検出部４６１〜４６３は、該当するエントリのレディフラグ４７２は１に、非レディ継続サイクル数４７３は０に設定される。
【００７５】
図６に、図４に示したプロセッサにより実施されるグルーピングの詳細を示す。まず、命令バッファ４０１、４０２、４０３にそれぞれ格納された命令５０１、５０２、５０３間には資源制約、データ依存制約いずれも存在しない。このため、ディスパッチ部４４１、４４２、４４３により最大並列実行数である全３命令（命令５１１、５１２、５１３）が各演算器へ発行される。
【００７６】
次に命令バッファ４０１、４０２、４０３には、命令５２１、５２２、５２３がそれぞれ格納される。ここで命令５２１と命令５２３はどちらもロード・ストア演算器で実行されるため、資源制約が発生する。さらに、命令５１１と命令５２２との間にはレジスタｒ１による真の依存関係が発生し、かつｌｄ命令のレイテンシは２である。このため、第１命令グループの命令５１１、５１２、５１３の実行直後にはレジスタｒ１を参照する事ができない。
【００７７】
したがって、命令５１１と命令５２２との間には依存関係があると判定され、命令５２２の直前の命令５２１のみが第２命令グループとなる。したがって、命令５３１のみがディスパッチされる。
【００７８】
最後に命令バッファ４０１、４０２、４０３には、命令５４１、５４２、５４３がそれぞれ格納される。命令５４１、５４２、５４３間には資源制約、データ依存制約いずれも存在しないため、命令５５１、５５２、５５３がディスパッチされる。
【００７９】
この様に命令グループを定義すると、第１命令グループの５１１が定義するレジスタｒ１を、第３命令グループの５４１が参照するまでに、第１命令グループの５１１の実行が完了している。このため、命令５１１と命令５５１との間にはペナルティサイクルが発生しない。
【００８０】
図７に本提案手法による実行性能を示す。図７の比較図は、図１の比較図に本発明結果６０４の欄を加えたものである。
【００８１】
本発明結果６０４の欄は、本実施の形態による命令のグルーピング結果を示す。従来結果１０３の欄に示す既存ハードウェアによる命令グルーピングでは１サイクルのペナルティが発生している。しかし、本発明結果６０４では理想的結果１０２と同様にペナルティサイクルが発生しない。したがって、実行性能を劣化させる課題が解決されている。
【００８２】
上記でも概要を説明したが、以下では図４の非レディ検出部４６１、４６２、４６３が実行する処理について詳細に説明する。図８は、非レディ検出部４６１を用いた非レディ状態のリソースの検出処理のフローチャートである。なお、非レディ検出部４６２、４６３も、非レディ検出部４６１と同様の処理を実行するため、その詳細な説明は繰り返さない。
【００８３】
まず、リソースデコード部４１１にて、命令バッファ４０１内の命令が定義するリソースを検出する（Ｓ７０１）。次にサイクルデコード部４５１が、命令バッファ４０１内の命令のレイテンシを検出する（Ｓ７０２）。
【００８４】
非レディ検出部４６１は、Ｓ７０１、Ｓ７０２で得た情報に基づき、命令バッファ４０１内の命令がその命令内で使用しているリソースを定義するか否かを判断する（Ｓ７０３）。
【００８５】
命令がリソースを定義しないと判断した場合には（Ｓ７０３でＮＯ）、非レディ検出部４６１は、そのリソースは非レディ状態ではない、つまり、次発行サイクルから直ちに参照可能であると判定する（Ｓ７０５）。
【００８６】
命令がリソースを定義すると判断した場合には（Ｓ７０３でＹＥＳ）、非レディ検出部４６１は、命令バッファ４０１内の命令のレイテンシが２以上か否かを判断する（Ｓ７０４）。レイテンシが２以上ではない場合、つまり、レイテンシが１の場合には（Ｓ７０４でＮＯ）、非レディ検出部４６１は、そのリソースは非レディではない、つまり、次発行サイクルから直ちに参照可能であると判定する（Ｓ７０５）。
【００８７】
逆に、Ｓ７０４、Ｓ７０５の判定結果がどちらも真、即ち命令が特定のリソースを定義し、かつレイテンシが２以上であると判定した場合には（Ｓ７０３でＹＥＳ、かつＳ７０４でＹＥＳ）、非レディ検出部４６１は、そのリソースは非レディあると判定する（Ｓ７０６）。リソースが非レディであるとは、即ち次発行サイクルからは直ちに参照することができない事を示す。
【００８８】
図９は、リソース状態記憶テーブル４７０へのデータの書込み処理のフローチャートである。
【００８９】
まず、リソース状態記憶テーブル４７０には、非レディ検出部４６１〜４６３から出力された非レディ情報（リソース番号、非レディ継続サイクル数（＝命令のレイテンシ））が入力される。リソース状態記憶テーブル４７０は、図８で説明した非レディ検出のアルゴリズムにより検出された、この非レディ情報の合計数を判定する（Ｓ８０１）。非レディ情報が１つも存在しない場合（Ｓ８０１でＮＯ）、リソース状態記憶テーブル４７０は、テーブル内の全ての非レディ状態にあるエントリの非レディ継続サイクル数４７３を所定の数（典型的な例では“１”）だけ減算する（Ｓ８０８）。
【００９０】
非レディ情報が１つ以上存在する場合（Ｓ８０１でＹＥＳ）、リソース状態記憶テーブル４７０は、非レディ情報のリソース番号に重なりがあるか判定する（Ｓ８０２）。非レディ情報のリソース番号に重なりがある場合（８０２でＹＥＳ）、リソース状態記憶テーブル４７０は、同一のリソース番号の非レディ情報の内、最もレイテンシの大きい非レディ情報を選択する（Ｓ８０３）。
【００９１】
リソース状態記憶テーブル４７０は、テーブル内の該当リソース（非レディリソース）のエントリを参照する（Ｓ８０４）。このエントリ参照及び以降のエントリ内容更新は、非レディ検出部４６１〜４６３から出力された非レディ情報に重なりがない場合、最大３並列でハードウェア的に実施されるものとする。
【００９２】
リソース状態記憶テーブル４７０は、非レディ情報のリソース番号で指定される該当リソースエントリがレディ状態であるかを判定する（Ｓ８０５）。
【００９３】
該当リソースエントリがレディ状態であれば（Ｓ８０５でＹＥＳ）、リソース状態記憶テーブル４７０は、直ちに該当リソースエントリのレディフラグ４７２を０にし、非レディ継続サイクル数４７３に、非レディ情報のレイテンシを登録する（Ｓ８０７）。
【００９４】
該当リソースエントリが既に非レディ状態である場合（Ｓ８０５でＮＯ）、リソース状態記憶テーブル４７０は、該当リソースエントリの非レディ継続サイクル数が、非レディ情報のレイテンシよりも小さい値であるかを判定する（Ｓ８０６）。
【００９５】
該当リソースエントリの非レディ継続サイクル数４７３が、非レディ情報のレイテンシよりも小さい値である場合には（Ｓ８０６でＹＥＳ）、リソース状態記憶テーブル４７０は、直ちに該当リソースエントリの非レディ継続サイクル数４７３に、非レディ情報のレイテンシを登録する（Ｓ８０７）。
【００９６】
該当リソースエントリの非レディ継続サイクル数４７３が、非レディ情報のレイテンシ以上の場合には（Ｓ８０６でＮＯ）、既存の非レディ継続サイクル数がそのままリソース状態記憶テーブル４７０の該当エントリに保持される。
【００９７】
Ｓ８０７の処理の実施の有無に係わらず、最終的にはＳ８０８の処理が実施される。
【００９８】
上述の処理により、リソース状態記憶テーブル４７０の各リソースのレディ状態が適切に更新される。
【００９９】
図１０に、命令発行の制御方法のフローチャートを示す。
【０１００】
まず、依存関係検出部４３１は、命令バッファ４０１に格納されている命令と命令バッファ４０２に格納されている命令との依存関係を検出する。この依存関係を（依存Ａ−１）と定義する（Ｓ９０１）。
【０１０１】
同時に、依存関係検出部４３２は、命令バッファ４０１に格納されている命令と命令バッファ４０３に格納されている命令との依存関係、及び命令バッファ４０２に格納されている命令と命令バッファ４０３に格納されている命令との依存関係を検出する。この依存関係を（依存Ａ−２）と定義する（Ｓ９０１）。
【０１０２】
さらに、依存関係検出部４３１は、上記（依存Ａ−１）と共に、命令バッファ４０２に格納されている命令とリソース状態記憶テーブル４７０の各リソースとの依存関係を検出する。この依存関係を（依存Ｂ−１）と定義する（Ｓ９０２）。
【０１０３】
さらに同時に、依存関係検出部４３２は、上記（依存Ａ−２）共に、命令バッファ４０３に格納されている命令とリソース状態記憶テーブル４７０の各リソースのエントリとの依存関係を検出する。この依存関係を（依存Ｂ−２）と定義する（Ｓ９０２）。
【０１０４】
（依存Ａ−１）、（依存Ａ−２）、（依存Ｂ−１）及び（依存Ｂ−２）の何れもが存在しない場合には（Ｓ９０３でＹＥＳ）、ディスパッチ部４４１、４４２、４４３は、命令バッファ４０１、４０２、４０３に格納されている全ての命令をディスパッチする（Ｓ９０４）。
【０１０５】
（依存Ａ−１）、（依存Ａ−２）、（依存Ｂ−１）及び（依存Ｂ−２）の何れかが存在する場合には（Ｓ９０３でＮＯ）、以下に示す命令ディスパッチの制御が行なわれる。
【０１０６】
つまり、（依存Ａ−２）及び（依存Ｂ−２）がどちらも存在せず、（依存Ａ−１）もしくは（依存Ｂ−１）が存在する場合、命令バッファ４０１に記憶されている命令もしくはリソース状態記憶テーブル４７０の対応エントリと、命令バッファ４０２に記憶されている命令との間に依存関係が存在する事を意味する。この場合、依存関係検出部４３１が上記依存を検出し、ディスパッチ部４４２〜４４３に制御信号を送り、命令バッファ４０２、４０３に格納されている命令のディスパッチを抑制する。即ち、命令バッファ４０１に格納された命令のみがディスパッチされる（Ｓ９０５、Ｓ９０６）。
【０１０７】
また、（依存Ａ−１）及び（依存Ｂ−１）がどちらも存在せず、（依存Ａ−２）もしくは（依存Ｂ−２）が存在する場合、命令バッファ４０１もしくは命令バッファ４０２に記憶されている命令又はリソース状態記憶テーブル４７０の対応エントリと、命令バッファ４０３に記憶されている命令との間に、依存関係が存在する事を意味する。この場合、依存関係検出部４３２は上記依存を検出し、ディスパッチ部４４３に制御信号を送り、命令バッファ４０３に格納されている命令のディスパッチを抑制する。即ち、命令バッファ４０１、４０２に格納された命令のみがディスパッチされる（Ｓ９０５、Ｓ９０６）。
【０１０８】
さらに、（依存Ａ−１）あるいは（依存Ｂ−１）が存在し、かつ（依存Ａ−２）あるいは（依存Ｂ−２）が存在する場合（数学的に表すと「（（依存Ａ−１）｜｜（依存Ｂ−１））＆＆（（依存Ａ−２）｜｜（依存Ｂ−２））」）、命令バッファ４０２のディスパッチの抑制が優先される。即ち、（依存Ａ−１）あるいは（依存Ｂ−１）が存在する場合、（依存Ａ−２）あるいは（依存Ｂ−２）の存在に係わらず、命令バッファ４０２、４０３のディスパッチが抑制され、命令バッファ４０１に格納されている命令のみがディスパッチされる（Ｓ９０５、Ｓ９０６）。
【０１０９】
上述の処理により、命令バッファ４０１、４０２、４０３に格納されている命令間の依存関係だけでなく、既に発行された命令グループ内の命令との間の依存関係も検出し、命令グループの発行を制御することができる。このため、発行された命令グループ間のペナルティを緩和し、性能向上に寄与する事が可能となる。
【０１１０】
また上記方法は、命令バッファが３つの場合における処理であるが、命令バッファが４以上の場合においても、命令間に複数の依存関係が検出された場合、先頭命令から、最も近い依存に関して発行グループを制御する、即ち、命令グループ内の命令間に依存関係が存在しない様に、発行グループを制御する方法は同一となる。
【０１１１】
また、図４においては先頭の命令バッファが固定されている例であるが、命令バッファをリング結合し、それに伴う先頭命令を示すポインタを更新し、先頭ポインタ変更による、依存関係検出部、ディスパッチ部の制御変更を行う様な、より効率的な処理を実施する事も可能であるが、この内容については、本特許の本質ではない為、説明を省略する。
【０１１２】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【０１１３】
本発明は並列実行アーキテクチャの根幹に係わる技術であり、簡素なハードウェアにも係わらず、実行性能の高いプロセッサを提供可能とする技術である。本発明により、並列実行可能な簡素なアーキテクチャを、バイナリ互換性を維持しつつ実現可能である。
【０１１４】
したがって、組み込み分野、汎用ＰＣ分野、スーパーコンピューティング分野等の何れにおいても有用な技術となろう。
【符号の説明】
【０１１５】
２０１〜２０３、４０１〜４０３  命令バッファ
２１１〜２１３、４１１〜４１３  リソースデコード部
２３１、２３２、４３１、４３２  依存関係検出部
２４１〜２４３、４４１〜４４３  ディスパッチ部
４５１〜４５３  サイクルデコード部
４６１〜４６３  非レディ検出部
４７０  リソース状態記憶テーブル
【図１】
2010262542.tif 000003
【図２】
2010262542.tif 000004
【図３】
2010262542.tif 000005
【図４】
2010262542.tif 000006
【図５】
2010262542.tif 000007
【図６】
2010262542.tif 000008
【図７】
2010262542.tif 000009
【図８】
2010262542.tif 000010
【図９】
2010262542.tif 000011
【図１０】
2010262542.tif 000012