(57)【特許請求の範囲】
【請求項１】
複数の処理対象情報を処理対象として保持し、該複数の処理対象情報の到着順序から処理順序に変更するリオーダリング装置であって、
処理待ちの複数の処理対象情報をそれぞれ異なる格納位置に記憶する記憶手段と、
前記記憶手段の格納位置がロウ番号に対応付けられ、前記到着順序における順位がカラム番号に対応付けられ、処理待ちの各処理対象情報の格納位置と順位に対応する要素が所定値を有し、処理対象情報格納待ちの格納位置と、該処理対象情報格納待ちの格納位置に割り当てられた順位とに対応する要素が該所定値を有する、マトリクス情報を保持するマトリクス手段と、
前記記憶手段の格納位置のうち、処理可能な１つ以上の処理対象情報の格納位置を示す、第１のベクタ情報を保持するベクタ手段と、
前記第１のベクタ情報の各要素と、前記マトリクス情報の各カラムの各要素の論理積を計算して、カラム毎の演算結果を示す第３のベクタ情報を生成し、カラム毎に該第３のベクタ情報のすべての要素の論理和を計算して、前記到着順序における前記処理可能な１つ以上の処理対象情報の順位を示す第２のベクタ情報を生成し、該第２のベクタ情報が示す１つ以上の順位の前記所定値を有する順位のうち、カラム番号が最も小さいカラムを選択することによって、最先の到着順位を選択し、選択された順位に対応するカラムの前記第３のベクタ情報において前記所定値を有する要素を求め、得られた要素に対応する格納位置の処理対象情報を処理することで、前記処理順序に従った処理を実現する制御手段と
を備えることを特徴とするリオーダリング装置。
【請求項２】
前記制御手段は、前記得られた要素に対応する格納位置の処理対象情報が処理されたとき、前記選択された順位に対応するカラムが前記到着順序における最後尾に来るように、前記マトリクス情報のカラムをローテートシフトすることを特徴とする請求項１記載のリオーダリング装置。
【請求項３】
複数の処理対象情報格納待ちの格納位置に割り当てられた順位のうち先頭を指すポインタ情報を保持するポインタ手段をさらに備え、前記制御手段は、該ポインタ情報が指す順位に対応するカラムにおいて前記所定値を有する要素を求め、得られた要素に対応する格納位置に新たな処理対象情報を格納することを特徴とする請求項１または２記載のリオーダリング装置。
【請求項４】
前記制御手段は、前記記憶手段に新たな処理対象情報を格納したとき、および、前記記憶手段に格納された処理対象情報を処理したとき、前記ポインタ手段のポインタ情報が新たな先頭を指すように該ポインタ情報を更新することを特徴とする請求項３記載のリオーダリング装置。
【請求項５】
前記記憶手段は、情報処理装置における発行待ちの複数の命令を、前記処理待ちの複数の処理対象情報として記憶し、前記制御手段は、該記憶手段に記憶された命令を発行する処理を行うことを特徴とする請求項１、２、３、または４記載のリオーダリング装置。
【請求項６】
前記記憶手段は、パケット通信における処理待ちの複数のパケット情報を、前記処理待ちの複数の処理対象情報として記憶し、前記制御手段は、該記憶手段に記憶されたパケット情報を処理することを特徴とする請求項１、２、３、または４記載のリオーダリング装置。
【請求項７】
複数の処理対象情報を処理対象として保持し、該複数の処理対象情報の到着順序から処理順序に変更するコンピュータのためのプログラムであって、
処理待ちの複数の処理対象情報を記憶手段のそれぞれ異なる格納位置に格納し、
前記記憶手段の格納位置がロウ番号に対応付けられ、前記到着順序における順位がカラム番号に対応付けられ、処理待ちの各処理対象情報の格納位置と順位に対応する要素が所定値を有し、処理対象情報格納待ちの格納位置と、該処理対象情報格納待ちの格納位置に割り当てられた順位とに対応する要素が該所定値を有する、マトリクス情報を保持し、
前記記憶手段の格納位置のうち、処理可能な１つ以上の処理対象情報の格納位置を示す、第１のベクタ情報を保持し、
前記第１のベクタ情報の各要素と、前記マトリクス情報の各カラムの各要素の論理積を計算して、カラム毎の演算結果を示す第３のベクタ情報を生成し、カラム毎に該第３のベクタ情報のすべての要素の論理和を計算して、前記到着順序における前記処理可能な１つ以上の処理対象情報の順位を示す第２のベクタ情報を生成し、
前記第２のベクタ情報が示す１つ以上の前記所定値を有する順位のうち、カラム番号が最も小さいカラムを選択することによって、最先の到着順位を選択し、
選択された順位に対応するカラムの前記第３のベクタ情報において前記所定値を有する要素を求め、
得られた要素に対応する格納位置の処理対象情報を処理することで、前記処理順序に従った処理を実現する
手順を前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置における命令やパケット送受信装置におけるパケット等を処理対象として、複数の処理対象の処理順序を変更するリオーダリング装置に関する。
【背景技術】
【０００２】
情報処理装置における命令処理においては、命令の到着順ではなく、命令の発行可能な順に命令を発行するリオーダリング制御が行われる場合がある。この場合、図１４に示すように、命令の発行順序は、到着順から発行可能な順に変更される。
【０００３】
このように、命令を複数個受け付けることが可能で、後に到着した命令が先に到着した命令よりも先に発行可能となった場合に、後に到着した命令を先に発行すれば、発行までの待ち時間が減るため、全体としての実行時間が短くなる。
【０００４】
このようなリオーダリング制御は、従来より、マイクロプロセッサ、磁気ディスク装置、テープ装置等において、命令処理の最適化のために採用されている（例えば、下記の特許文献１〜３を参照）。
【特許文献１】特開平０８−１１０９０１号公報
【特許文献２】特開２０００−０４８５４９号公報
【特許文献３】特開平２００２−３０４８２３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のリオーダリング制御では、到着順に並んでいる命令を発行可能な順に検索するために複雑な操作が必要であり、一定の処理時間がかかる。しかし、命令実行時間をより短くするためには、発行可能な命令が複数ある場合にどれを発行するかを早く確実に決定することが望まれる。
【０００６】
本発明の課題は、情報処理装置における命令のような、複数の処理対象の中から処理可能なものを短時間で確実に検索することで、それらの処理対象のリオーダリングに要する時間を短縮することである。
【課題を解決するための手段】
【０００７】
図１は、本発明のリオーダリング装置の原理図である。図１のリオーダリング装置は、記憶手段１０１、マトリクス手段１０２、ベクタ手段１０３、および制御手段１０４を備え、複数のエントリを処理対象として保持し、それらのエントリの処理順序を第１の順序から第２の順序に変更する。
【０００８】
記憶手段１０１は、処理待ちの複数のエントリをそれぞれ異なる格納位置に記憶する。マトリクス手段１０２は、記憶手段１０１の格納位置がロウ番号に対応付けられ、第１の順序における順位がカラム番号に対応付けられ、処理待ちの各エントリの格納位置と順位に対応する要素が所定値を有する、マトリクス情報を保持する。ベクタ手段１０３は、記憶手段１０１の格納位置のうち、処理可能な１つ以上のエントリの格納位置を示す、第１のベクタ情報を保持する。
【０００９】
制御手段１０４は、まず、第１のベクタ情報とマトリクス情報の各カラムとを演算し、それぞれのカラムの演算結果から、第１の順序における処理可能な１つ以上のエントリの順位を示す第２のベクタ情報を生成する。次に、第２のベクタ情報が示す１つ以上の順位から処理すべき順位を選択し、選択された順位に対応するカラムにおいて所定値を有する要素を求める。そして、得られた要素に対応する格納位置のエントリを処理することで、第２の順序に従った処理を実現する。
【００１０】
第１のベクタ情報とマトリクス情報の各カラムとの演算においては、第１のベクタ情報の全要素と各カラムの全要素の間で並列に演算が実行され、それぞれのカラムの演算結果が集計されて、第２のベクタ情報が生成される。
【００１１】
この第２のベクタ情報に、処理可能なエントリの順位を示す要素が複数個含まれている場合、あらかじめ決められたポリシーに従って、それらの要素が示す複数の順位の１つが選択され、その順位に対応するマトリクス情報のカラムから、所定値を有する要素が求められる。そして、所定値を有する要素に対応する格納位置が求められ、記憶手段１０１のその格納位置に記憶されたエントリが処理される。
【００１２】
記憶手段１０１は、例えば、後述する図２の記憶領域２０１に対応し、マトリクス手段１０２のマトリクス情報は、例えば、ビットマトリクス２０３に対応し、ベクタ手段１０３の第１のベクタ情報は、例えば、後述する図４のビットベクタ２０５に対応する。制御手段１０４は、例えば、後述する図１０および図１１のリオーダリング回路、または図１３のプロセッシングエレメント１３０１−１〜１３０１−ｎに対応する。
【発明の効果】
【００１３】
本発明によれば、処理可能なエントリの格納位置を示すベクタ情報と、マトリクス情報の各カラムとの間で演算を行うだけで、どの順位のエントリが処理可能かを簡単かつ高速に検索できる。したがって、複数の処理対象のリオーダリングに要する時間が短縮される。
【発明を実施するための最良の形態】
【００１４】
以下、図面を参照しながら、本発明を実施するための最良の形態を詳細に説明する。
本実施形態のリオーダリング制御では、ビットマトリクスを用いることで、発行可能な命令が短時間で確実に検索される。このリオーダリング制御の概要は、以下の通りである。
（１）命令を格納する記憶領域の複数の格納位置（アドレス）に対応付けられた番号をロウ番号とし、命令の到着順位を示す番号をカラム番号とするビットマトリクスを保持する記憶装置を用意する。
【００１５】
そして、すべての発行待ち命令を記憶領域のそれぞれ異なる格納位置に格納し、それぞれの命令の格納位置を示すビット列を、命令到着順に順位を付けてビットマトリクスの複数のカラムに記憶する。各ビット列において、命令が格納された格納位置に対応するビットには、論理“１”または“０”が所定値として記憶され、それ以外の格納位置に対応するビットには、他方の論理（“０”または“１”）が記憶される。
【００１６】
さらに、残された命令格納待ちの格納位置を示すビット列を、上記ビット列に続く順位に任意の順に並べて記憶する。各ビット列において、命令格納待ちの格納位置に対応するビットには、論理“１”または“０”が所定値として記憶され、それ以外の格納位置に対応するビットには、他方の論理（“０”または“１”）が記憶される。このようにして、記憶領域のすべての格納位置と等価な複数のビット列が、順序付けられてビットマトリクスに保持される。
（２）すべての発行待ち命令中におけるある命令の到着順位は、ビットマトリクスにおいて、その命令の格納位置を示すビット列のカラム番号に対応する。そこで、ビットマトリクスを用いて、発行待ち命令のうち発行可能なすべての命令について順位を求め、発行可能な命令のうちで到着順位の一番早い命令の順位を得る。
（３）ビットマトリクスにおいて、上記（２）で得られた順位のビット列が示す格納位置を得る。この格納位置は、すべての発行可能な命令のうち、到着順位の一番早い命令の格納位置に対応する。
（４）上記（３）で得られた格納位置の命令を発行し、発行された命令の格納位置を示すビット列のカラム番号以降のすべてのビット列を、発行された命令の格納位置を示すビット列が最後尾に来るように、ローテートシフトする。
（５）上記（４）の操作後、残された発行待ち命令の格納位置を示す複数のビット列は、ビットマトリクスの先頭カラムから連続した順位で到着順に並び、これらのビット列に続く順位には、命令格納待ちのすべての格納位置を示す複数のビット列が並ぶ。したがって、上記（１）の状態が維持される。
（６）新たに到着した命令は、ビットマトリクスにおいて命令格納待ちの格納位置を示す複数のビット列のうち、一番早い順位のビット列が示す格納位置に格納する。これにより、上記（５）の連続性を保持して上記（１）の状態が維持される。
（７）上記（２）の操作を高速に行うには、「格納位置を示すビット列」の表現として、格納位置のビットマップ等、複数の格納位置を重畳して表現できるものを用いる。
（８）上記（６）の操作を高速に行うには、ビットマトリクスにおいて命令格納待ちの格納位置を示す複数のビット列のうち、一番早い順位のビット列の順位を指すポインタを保持しておく。そして、１つの命令が記憶領域に格納されると、ポインタが次の順位を指し、１つの命令が記憶領域から発行されると、ポインタが前の順位を指すように、このポインタの値を加減し、ポインタ加減の都度、ポインタが指す順位のビット列が示す格納位置に、次に到着する命令を格納する。
【００１７】
次に、図２から図８までを参照しながら、８個の格納位置を有する記憶領域に命令を登録し、発行可能な命令から順に発行する、リオーダリング制御の一例を説明する。この場合、それぞれの格納位置には１〜８の到着順位が割り当てられ、命令が発行される度にその順位が変化する。したがって、８行８列のビットマトリクスが用いられる。
【００１８】
図２は、このような記憶領域２０１に４個の命令が格納されているときのビットマトリクス２０３を示している。このビットマトリクス２０３のロウ番号１〜８は記憶領域２０１の格納位置＃１〜＃８にそれぞれ対応し、カラム番号１〜８は命令の到着順位１〜８にそれぞれ対応している。
【００１９】
各カラムのビット列において、論理“１”のビットは、発行待ち命令（登録済み命令）の格納位置または命令格納待ちの格納位置を示し、論理“０”のビットは、それ以外の格納位置を示す。この例では、到着順位１〜４のカラムに、発行待ち命令の格納位置＃６、＃３、＃５、および＃１をそれぞれ示す４つのビット列が保持されており、到着順位５〜８のカラムに、命令格納待ちの格納位置＃８、＃７、＃４、および＃２をそれぞれ示す４つのビット列が保持されている。
【００２０】
次格納位置のビットベクタ２０２は上記（８）で述べたポインタに対応し、ビットベクタ２０２における論理“１”のビットは、次に到着した命令の格納位置を示すビット列を保持する、ビットマトリクス２０３のカラムを指す。この例では、到着順位５のカラムに保持されたビット列が示す格納位置＃８が、次格納位置となる。
【００２１】
到着順検索のビットベクタ２０４は発行可能な命令の検索結果を表し、ビットベクタ２０４における論理“１”のビットは、発行可能な命令の格納位置を示すビット列を保持する、ビットマトリクス２０３のカラムを指す。この例では、まだ発行可能な命令が存在しないため、ビット列２０４のすべてのビットが論理“０”となっている。
【００２２】
この状態において新しい命令が到着すると、ビットベクタ２０２における論理“１”のビットが指す到着順位５のカラムが検索され、論理“１”のビットに対応する格納位置＃８が次格納位置として得られる。このとき、ビットベクタ２０２とビットマトリクス２０３の各ロウのビット列との論理積（ＡＮＤ）が計算される。
【００２３】
この場合、格納位置＃８のロウのみのＡＮＤ演算結果に論理“１”が含まれ、それ以外の格納位置のロウについては、ＡＮＤ演算結果がすべて論理“０”となる。こうして、検索結果として格納位置＃８が得られるので、図３に示すように、到着した命令は記憶領域２０１の格納位置＃８に格納される。このとき、ビットベクタ２０２のポインタ（論理“１”のビット）が１ビット右（到着順位が遅くなる方向）にシフトされ、到着順位６のビットが論理“１”となる。
【００２４】
次に、記憶領域２０１に格納された命令の中に発行可能な命令が存在する場合、その命令の到着順位が検索される。例えば、格納位置＃１と＃３の命令が発行可能な状態にある場合、図４に示すように、発行可能な命令の格納位置が論理“１”となるビットベクタ２０５が生成され、ビットベクタ２０５とビットマトリクス２０３の各カラムのビット列とのＡＮＤ演算が行われる。そして、各カラムのＡＮＤ演算結果を示すビットマトリクスにおいて、カラム毎に論理和（ＯＲ）が計算され、ＯＲ演算結果がビットベクタ２０４に保持される。
【００２５】
このとき、ビットベクタ２０５の全要素と各カラムのビット列の全要素の間で、ＡＮＤ演算が並列に行われるため、発行可能な命令を高速に検索することができる。
この場合、到着順位２および４のカラムについては、ＡＮＤ演算結果に論理“１”が含まれるため、そのＯＲ演算結果は論理“１”となる。一方、到着順位１、３、および５〜８のカラムについては、ＡＮＤ演算結果がすべて論理“０”となるため、そのＯＲ演算結果は論理“０”となる。こうして、発行可能な命令の検索結果として到着順位２と４が得られるが、この段階では発行する命令の格納位置は特定されない。
【００２６】
次に、得られた２つの到着順位のうち順位２の方が早いので、到着順位２の命令の格納位置が検索される。このとき、図５に示すように、ビットベクタ２０４において到着順位４が論理“０”に変更され、到着順位２のみが論理“１”となるビットベクタ２０４と、ビットマトリクス２０３の各ロウのビット列とのＡＮＤ演算が行われる。
【００２７】
この場合、格納位置＃３のロウのみのＡＮＤ演算結果に論理“１”が含まれ、それ以外の格納位置のロウについては、ＡＮＤ演算結果がすべて論理“０”となる。こうして、検索結果として格納位置＃３が得られるので、記憶領域２０１の格納位置＃３に格納された命令が発行される。
【００２８】
命令が発行されると、図６に示すように、ビットマトリクス２０３の到着順位２のカラムが最後の順位に来るように、到着順位２〜８のカラムがローテートシフトされ、格納位置＃３の命令が削除される。そして、次格納位置の到着順位を早めるため、図７に示すように、ビットベクタ２０２のポインタが１ビット左にシフトされる。
【００２９】
ビットマトリクス２０３の初期値としては、例えば、図８に示すような値が用いられる。このとき、ビットベクタ２０２の初期値は到着順位１を指し、命令は到着順に格納位置＃１〜＃８に格納される。なお、ビットマトリクス２０３の初期値は、論理“１”のビット位置がロウ間およびカラム間で重複しないように選べばよく、必ずしも図８の値には限られない。
【００３０】
このようなビットマトリクスを用いたリオーダリング制御によれば、次のような効果が得られる。
（ａ）発行可能な命令の格納位置が論理“１”となるビットベクタと、ビットマトリクスの各カラムのビット列との間でＡＮＤ演算を行うだけで、どの到着順位の命令が発行可能かを簡単かつ高速に検索できる。上述した例では、ＡＮＤ演算結果に論理“１”が含まれるカラムに対応する到着順位の命令が発行可能である。
（ｂ）複数の命令が発行可能な場合でも、同様に発行可能な命令の格納位置が論理“１”となるようなビットベクタを生成するだけで、上記（ａ）と同様の操作が適用できる。
（ｃ）発行する命令を検索する際、発行する命令の到着順位が論理“１”となるようなビットベクタと、ビットマトリクスの各ロウのビット列との間でＡＮＤ演算を行うだけで、どの格納位置の命令を発行するかが簡単に検索できる。
（ｄ）複数の命令が発行可能な場合でも、発行する命令を到着順位により選択することで上記（ｃ）と同様の操作が適用できる。
（ｅ）発行された命令の到着順位のカラムがビットマトリクスの最後の到着順位に来るように、カラムをローテートシフトすることで、記憶領域内の命令を並べ替える等の複雑な操作を行うことなしに、ビットマトリクスで次に発行すべき命令を決定できる。
（ｆ）次に到着した命令の格納位置を示すカラムの到着順位が論理“１”となるようなビットベクタを保持しておけば、そのビットベクタとビットマトリクスの各ロウのビット列との間でＡＮＤ演算を行うだけで、どの格納位置に命令を格納すればよいかが簡単に検索できる。
（ｇ）次に到着した命令の格納位置を示すビットベクタにおいて、命令が到着した場合は到着順位が遅くなる方向にシフト演算を行い、命令を発行した場合は到着順位が早くなる方向にシフト演算するだけで、次格納位置を変更することができる。このビットベクタのシフト演算は、ビットマトリクスのローテートシフトとは別に行われる。
【００３１】
次に、図９から図１１までを参照しながら、上述したリオーダリング制御をＣＰＵ（中央処理装置）の命令処理に適用した場合の具体例について説明する。
図９は、アウトオブオーダ方式で命令を実行するマイクロプロセッサの構成例を示している。このマイクロプロセッサ９０１は、命令デコーダ９１１、フェッチ機構９１２、バスインタフェース９１３、キャッシュ９１４、リザベーションステーション（ＲＳ）９１５、リオーダバッファ（ＲＯＢ）９１６、実行ユニット９１７、およびリタイアメントレジスタファイル（ＲＲＦ）９１８を備える。
【００３２】
バスインタフェース９１３は、プロセッサバス９０２を介して外部のメモリ（不図示）にアクセスする。フェッチ機構９１２は、メモリまたはキャッシュ９１４からマクロ命令をプリフェッチし、命令デコーダは、そのマクロ命令をマイクロ命令列へ変換する。
【００３３】
マイクロ命令のオペランドは、アウトオブオーダ実行に備えて、リタイアメントレジスタファイル９１８のエントリに置き換えられ、レジスタリネーミングが行われる。このとき、先行命令の実行結果をオペランドとする命令は、先行命令のデコード時にその実行結果格納先として予約したエントリをオペランドとするように、レジスタリネーミングされる。
【００３４】
命令デコーダ９１１から発行された命令は、一旦、リザベーションステーション９１５に入力され、依存関係にあるオペランドデータを待つ。リザベーションステーション９１５のスケジューラはリオーダリング回路を含み、オペランドデータが揃った命令のうち、一番古く発行された命令から順に実行ユニット９１７に発行する。このとき、リオーダリング回路は、マイクロ命令の順序を到着順（インオーダ）から発行可能な順（アウトオブオーダ）に変更する。
【００３５】
ただし、命令デコーダ９１１からインオーダ（プログラム順）で発行されるマイクロ命令の実行結果は、インオーダにリタイアメントレジスタファイル９１８に反映する必要がある。そこで、実行ユニット９１７が出力するアウトオブオーダの実行結果は、リオーダバッファ９１６により、インオーダに戻される。このため、命令デコード時には、実行結果格納先としてリオーダバッファ９１６のエントリが予約される。
【００３６】
図１０および図１１は、リザベーションステーション９１５内に設けられるリオーダリング回路の構成例を示している。このリオーダリング回路は、解放順位指示器１００１、ＯＲ回路１００２−２〜１００２−ｎ、１１０４−１〜１１０４−ｎ、ＡＮＤ回路１００３−１〜１００３−ｎ、１１０３−１〜１１０３−ｎ、ラッチ回路１００４−１〜１００４−ｎ（Ｃ１〜Ｃｎ）、マルチプレクサ１００５、１００６、１１０２、割り当て順位指示器１００７、解放要求ベクタ１１０１、インバータ１１０５−２〜１１０５−ｎ、およびＮＯＲ回路１１０６−２〜１１０６−ｎを備える。
【００３７】
ラッチ回路１００４−１〜１００４−ｎは、それぞれｎビットのビット列を保持するフリップフロップ等の記憶回路であり、図２のビットマトリクス２０３に対応する。この場合、ラッチ回路１００４−１〜１００４−ｎにはｎ行ｎ列のビットマトリクスが保持され、ラッチ回路１００４−ｉ（ｉ＝１〜ｎ）には到着順位ｉのカラムが保持される。
【００３８】
ラッチ回路１００４−１〜１００４−ｎは、常にそれぞれ異なる位置の１ビットのみが論理“１”の値を持ち、記憶領域（不図示）のｎ個のエントリ格納位置のうちの１つをそれぞれ指すセレクタとして機能する。
【００３９】
解放順位指示器１００１は、図５のビットベクトル２０４に対応し、次に発行（解放）すべきエントリ（マイクロ命令）の順位を指すｎビットのビットベクトルを保持する。このビットベクトルは、高々１ビットのみ論理“１”の値を持ち、ラッチ回路１００４−１〜１００４−ｎのいずれかを指す。ただし、解放すべきエントリが存在しない場合は、すべてのビットが論理“０”となる。
【００４０】
ＯＲ回路１００２−２は、解放順位指示器１００１の１番目および２番目のビットの論理和を出力し、ＯＲ回路１００２−ｉ（ｉ＝３〜ｎ）は、ＯＲ回路１００２−（ｉ−１）の出力と解放順位指示器１００１のｉ番目のビットの論理和を出力する。
【００４１】
ＡＮＤ回路１００３−１は、解放指示パルスＰ１と解放順位指示器１００１の１番目のビットの論理積をラッチ回路１００４−１に出力し、ＡＮＤ回路１００３−ｉ（ｉ＝２〜ｎ）は、解放指示パルスＰ１とＯＲ回路１００２−ｉの出力の論理積をラッチ回路１００４−ｉに出力する。
【００４２】
したがって、解放順位指示器１００１のｋ番目のビット（ｋ＝１〜ｎ）が論理“１”のときに解放指示パルスＰ１が論理“１”になると、ＡＮＤ回路１００３−１〜１００３−（ｋ−１）は論理“０”を出力し、ＡＮＤ回路１００３−ｋ〜１００３−ｎは論理“１”（ラッチ指示信号）を出力する。
【００４３】
ラッチ回路１００４−ｉ（ｉ＝ｋ〜ｎ−１）は、ｎビットのビット列を出力し、ＡＮＤ回路１００３−ｉがラッチ指示信号を出力したとき、ラッチ回路１００４−（ｉ＋１）から出力されるビット列をラッチする。ラッチ回路１００４−ｎは、ｎビットのビット列を出力し、ＡＮＤ回路１００３−ｎがラッチ指示信号を出力したとき、マルチプレクサ１００５から出力されるビット列をラッチする。
【００４４】
マルチプレクサ１００５は、ラッチ回路１００４−１〜１００４−ｎから出力されるｎ個のビット列のうち、解放順位指示器１００１が指すｋ番目のビット列を選択して、ラッチ回路１００４−ｎに出力する。
【００４５】
こうして、ラッチ回路１００４−ｋ〜１００４−ｎは、解放指示パルスＰ１と解放順位指示器１００１のビットベクトルから生成されるラッチ指示信号により、図６に示したローテートシフト操作を行う。このとき、ラッチ回路１００４−１〜１００４−ｎは、常に割り当て順（到着順）を維持する。
【００４６】
割り当て順位指示器１００７は、図２のビットベクトル２０２に対応し、次に到着したエントリの順位を指すｎビットのビットベクトルと、フルエントリ時の退避ビット（１ビット）の合計ｎ＋１ビットを保持し、常にいずれか１ビットのみが論理“１”の値を持つ。ビットベクトルは、ラッチ回路１００４−１〜１００４−ｎのいずれかを指す。
【００４７】
また、割り当て順位指示器１００７は、ビットベクトルと退避ビットの内の論理“１”の値を持つビットの位置によりエントリ登録済みの格納位置の数を監視し、すべての格納位置にエントリが登録された場合、フルエントリ信号Ｓ２を論理“１”として出力する。
【００４８】
割り当て順位指示器１００７は、解放指示パルスＰ１が入力されたとき、エントリが減る方向（左方向）にビットベクトルをシフトし、割り当て指示パルスＰ２が入力されたとき、エントリが増える方向（右方向）にビットベクトルをシフトする。ただし、両パルスが同時に入力された場合はシフト動作を行わない。
【００４９】
マルチプレクサ１００６は、ラッチ回路１００４−１〜１００４−ｎから出力されるｎ個のビット列のうち、割り当て順位指示器１００７が指すビット列を選択して、割り当て格納位置ポインタＳ１として出力する。これにより、次に到着したエントリは、割り当て格納位置ポインタＳ１が指す格納位置に格納される。
【００５０】
解放要求ベクタ１１０１は、図４のビットベクトル２０５に対応し、ｎビットのビットベクトルを保持する。各ビットは各エントリの解放要求を示し、解放が要求されたエントリに対応するビットが論理“１”の値を持つ。したがって、同時に複数エントリの解放が要求されている場合は、複数のビットが論理“１”になる。
【００５１】
ラッチ回路１００４−１〜１００４−ｎは、常に割り当て順を維持しているため、解放要求ベクタ１１０１とこれらのビット列を比較することで、解放要求ベクタ１１０１の情報を割り当て順に並び替えて、一番古いエントリの順位を抽出することができる。この操作は、次のようにして行われる。
【００５２】
ＡＮＤ回路１１０３−ｉ（ｉ＝１〜ｎ）は、ラッチ回路１００４−ｉから出力されるビット列と、解放要求ベクタ１１０１のビットベクトルの論理積を、ＯＲ回路１１０４−ｉに出力する。
【００５３】
ＯＲ回路１１０４−１は、ＡＮＤ回路１１０３−１から出力されるｎビットの論理和（ＯＲリダクション）を出力し、ＯＲ回路１１０４−ｉ（ｉ＝２〜ｎ）は、ＡＮＤ回路１１０３−ｉから出力されたｎビットと、ＯＲ回路１１０４−（ｉ−１）の出力の論理和（ＯＲリダクション）を出力する。
【００５４】
インバータ１１０５−ｉ（ｉ＝２〜ｎ）は、ＯＲ回路１１０４−ｉの出力を反転し、ＮＯＲ回路１１０６−ｉは、インバータ１１０５−ｉの出力とＯＲ回路１１０４−（ｉ−１）の出力の論理和の否定を出力する。
【００５５】
解放順位指示器１００１は、ＯＲ回路１１０４−１の出力を１番目のビットとして保持し、ＮＯＲ回路１１０６−２〜１１０６−ｎの出力を２番目〜ｎ番目のビットとして保持する。
【００５６】
したがって、ｋ番目のＡＮＤ回路１１０３−ｋ（ｋ＜ｎ）の出力に論理“１”のビットが含まれていれば、ＯＲ回路１１０４−ｋは論理“１”を出力し、ＮＯＲ回路１１０６−（ｋ＋１）〜１１０６−ｎはすべて論理“０”を出力する。
【００５７】
こうして、解放順位指示器１００１は、解放が要求された複数エントリの順位のうち、最も左の順位に対応するビットのみが論理“１”となり、それ以外のビットが論理“０”となるビットベクトルを保持する。このビットベクトルは、解放が要求された複数エントリのうち一番古いものの順位を指している。
【００５８】
マルチプレクサ１１０２は、ラッチ回路１００４−１〜１００４−ｎから出力されるｎ個のビット列のうち、解放順位指示器１００１が指すビット列を選択して、解放エントリポインタＳ３として出力する。これにより、解放エントリポインタＳ３が指す格納位置のエントリが発行（解放）される。
【００５９】
なお、図１１の回路は、解放要求ベクタ１１０１から解放エントリポインタＳ３を得るために設けられているが、他にも、割り当て情報とエントリ情報のマッチング結果を割り当て順に並び替える操作のように、割り当て順への並び替え回路として一般的に利用可能である。
【００６０】
このようなリオーダリング回路によれば、各エントリの滞留時間をカウントしなくても、一番古い発行可能な命令をアクセスすることができる。したがって、より簡単かつ高速に、アウトオブオーダ方式で命令を実行することが可能となる。
【００６１】
ところで、本発明のリオーダリング制御は、ＣＰＵにおける命令処理だけでなく、様々な処理対象に適用することが可能である。例えば、パケット送受信装置におけるパケット情報を処理対象とした場合、複数のパケット情報の処理順序を変更することができる。
【００６２】
図１２は、このようなパケット送受信装置に用いられるネットワーク通信ＬＳＩ（Large Scale Integration ）の構成例を示している。この通信ＬＳＩ１２０１は、バスインタフェース１２１１、送信バッファ１２１２、送信管理部１２１３、および送信インタフェース１２１４を備える。
【００６３】
パケット送信時に、上位プログラムは、装置内バス１２０２を介して通信ＬＳＩ１２０１にパケット送信要求を転送する。この要求を受けて、バスインタフェース１２１１は、パケット長とパケットの宛先を送信管理部１２１３に転送して、送信バッファ１２１２の割り当てを要求する。
【００６４】
割り当て要求を実行可能な場合、送信管理部１２１３は、内部にパケット制御情報のエントリを生成し、送信バッファ１２１２の割り当てアドレスと、生成されたエントリの番号をバスインタフェース１２１１に転送して、割り当て通知を行う。この通知を受けて、バスインタフェース１２１１は、送信バッファ１２１２へのパケットデータの書き込みを開始する。
【００６５】
パケットデータの書き込みを完了すると、バスインタフェース１２１１は、送信可能になった割り当てエントリの番号を転送して、送信管理部１２１３に送信可能通知を行う。
送信可能パケットがある場合、送信管理部１２１３は、送信開始アドレスと送信パケット長を送信インタフェース１２１４に転送して、送信要求を行う。この要求を受けて、送信インタフェース１２１４は、送信バッファ１２１２からパケットデータを読み出し、装置外ネットワーク１２０３を介して宛先に転送する。送信管理部１２１３は、送信インタフェース１２１４から送信完了通知を受け取ると、対応するエントリを削除する。
【００６６】
このような送信制御においては、バスインタフェース１２１１は、複数のパケットについてそれらのデータ書き込みを同時並行してＤＭＡ（Direct Memory Access）転送するため、送信管理部１２１３は、複数のエントリを同時に維持しなければならない。また、ネットワークの帯域を有効活用するため、宛先の異なるパケット間では後で割り当てられたパケットでも送信可能になった時点で送信する必要があり、割り当て順とは異なる順序でエントリを解放しなければならない。
【００６７】
そこで、図１０および図１１に示したリオーダリング回路が送信管理部１２１３内に設けられ、パケットのリオーダリング制御が行われる。この場合、パケット制御情報がエントリとして記憶領域に登録され、送信インタフェース１２１４からの送信完了通知が解放要求ベクタ１１０１のビット値に反映される。
【００６８】
従来の送信管理部では、次に送信すべきパケットのエントリを逐次検索するか、もしくは規模の大きな前詰機能付きキューの回路を用いてハードウェア実装する必要があった。これに対して、本発明のリオーダリング回路によれば、規模の小さな回路で高速に検索可能なため、大量の短いパケットをリオーダして送信することが可能となる。
【００６９】
なお、図１２の通信ＬＳＩ１２０１では、送信パケットの情報を処理対象としてリオーダリングを行っているが、同様に、受信パケットの情報を処理対象としてリオーダリングを行うことも可能である。
【００７０】
ところで、本発明のリオーダリング制御は、ハードウェア回路だけでなく、並列処理を行うソフトウェアにより実装することもできる。例えば、図１３に示すような並列計算機を用いれば、ｎ個のプロセッシングエレメント（ＰＥ）１３０１−１〜１３０１−ｎにより、ビットマトリクスの並列処理を行うことができる。
【００７１】
この場合、ＰＥ１３０１−ｉ（ｉ＝１〜ｎ）のメモリには、ｎ行ｎ列のビットマトリクスの到着順位ｉのカラムと、図２〜図７に示したリオーダリング制御を行うプログラムが格納される。そして、ＰＥ１３０１−１〜１３０１−ｎは、他のＰＥと通信しながらそのプログラムを実行することで、到着順位１〜ｎのカラムを並列に処理してリオーダリング制御を行う。
【００７２】
（付記１）複数のエントリを処理対象として保持し、該複数のエントリの処理順序を第１の順序から第２の順序に変更するリオーダリング装置であって、
処理待ちの複数のエントリをそれぞれ異なる格納位置に記憶する記憶手段と、
前記記憶手段の格納位置がロウ番号に対応付けられ、前記第１の順序における順位がカラム番号に対応付けられ、処理待ちの各エントリの格納位置と順位に対応する要素が所定値を有する、マトリクス情報を保持するマトリクス手段と、
前記記憶手段の格納位置のうち、処理可能な１つ以上のエントリの格納位置を示す、第１のベクタ情報を保持するベクタ手段と、
前記第１のベクタ情報と前記マトリクス情報の各カラムとを演算し、それぞれのカラムの演算結果から、前記第１の順序における前記処理可能な１つ以上のエントリの順位を示す第２のベクタ情報を生成し、該第２のベクタ情報が示す１つ以上の順位から処理すべき順位を選択し、選択された順位に対応するカラムにおいて前記所定値を有する要素を求め、得られた要素に対応する格納位置のエントリを処理することで、前記第２の順序に従った処理を実現する制御手段と
を備えることを特徴とするリオーダリング装置。
（付記２）前記マトリクス情報において、エントリ格納待ちの格納位置と、該エントリ格納待ちの格納位置に割り当てられた順位とに対応する要素が、前記所定値を有することを特徴とする付記１記載のリオーダリング装置。
（付記３）前記制御手段は、前記第１のベクタ情報の各要素と、前記マトリクス情報の各カラムの各要素の論理積を計算して、カラム毎の演算結果を示す第３のベクタ情報を生成し、カラム毎に該第３のベクタ情報のすべての要素の論理和を計算して、前記第２のベクタ情報を生成することを特徴とする付記２記載のリオーダリング装置。
（付記４）前記制御手段は、前記得られた要素に対応する格納位置のエントリが処理されたとき、前記選択された順位に対応するカラムが前記第１の順序における最後尾に来るように、前記マトリクス情報のカラムをローテートシフトすることを特徴とする付記２または３記載のリオーダリング装置。
（付記５）複数のエントリ格納待ちの格納位置に割り当てられた順位のうち先頭を指すポインタ情報を保持するポインタ手段をさらに備え、前記制御手段は、該ポインタ情報が指す順位に対応するカラムにおいて前記所定値を有する要素を求め、得られた要素に対応する格納位置に新たなエントリを格納することを特徴とする付記２、３、または４記載のリオーダリング装置。
（付記６）前記制御手段は、前記記憶手段に新たなエントリを格納したとき、および、前記記憶手段に格納されたエントリを処理したとき、前記ポインタ手段のポインタ情報が新たな先頭を指すように該ポインタ情報を更新することを特徴とする付記５記載のリオーダリング装置。
（付記７）前記マトリクス手段は、エントリの到着順を前記第１の順序として用いることを特徴とする付記１、２、３、４、５、または６記載のリオーダリング装置。
（付記８）前記制御手段は、前記第２のベクタ情報が示す１つ以上の順位のうち、最先の順位を前記処理すべき順位として選択することを特徴とする付記１、２、３、４、５、６、または７記載のリオーダリング装置。
（付記９）前記記憶手段は、情報処理装置における発行待ちの複数の命令を、前記処理待ちの複数のエントリとして記憶し、前記制御手段は、該記憶手段に記憶された命令を発行する処理を行うことを特徴とする付記１、２、３、４、５、６、７、または８記載のリオーダリング装置。
（付記１０）前記記憶手段は、パケット通信における処理待ちの複数のパケット情報を、前記処理待ちの複数のエントリとして記憶し、前記制御手段は、該記憶手段に記憶されたパケット情報を処理することを特徴とする付記１、２、３、４、５、６、７、または８記載のリオーダリング装置。
（付記１１）複数のエントリを処理対象として保持し、該複数のエントリの処理順序を第１の順序から第２の順序に変更するコンピュータのためのプログラムであって、
処理待ちの複数のエントリを記憶手段のそれぞれ異なる格納位置に格納し、
前記記憶手段の格納位置がロウ番号に対応付けられ、前記第１の順序における順位がカラム番号に対応付けられ、処理待ちの各エントリの格納位置と順位に対応する要素が所定値を有する、マトリクス情報を保持し、
前記記憶手段の格納位置のうち、処理可能な１つ以上のエントリの格納位置を示す、第１のベクタ情報を保持し、
前記第１のベクタ情報と前記マトリクス情報の各カラムとを演算し、それぞれのカラムの演算結果から、前記第１の順序における前記処理可能な１つ以上のエントリの順位を示す第２のベクタ情報を生成し、
前記第２のベクタ情報が示す１つ以上の順位から処理すべき順位を選択し、
選択された順位に対応するカラムにおいて前記所定値を有する要素を求め、
得られた要素に対応する格納位置のエントリを処理することで、前記第２の順序に従った処理を実現する
手順を前記コンピュータに実行させることを特徴とするプログラム。
【図面の簡単な説明】
【００７３】
【図１】本発明のリオーダリング装置の原理図である。
【図２】第１のビットマトリクスを示す図である。
【図３】第２のビットマトリクスを示す図である。
【図４】第３のビットマトリクスを示す図である。
【図５】第４のビットマトリクスを示す図である。
【図６】第５のビットマトリクスを示す図である。
【図７】第６のビットマトリクスを示す図である。
【図８】ビットマトリクスの初期値を示す図である。
【図９】マイクロプロセッサの構成図である。
【図１０】リオーダリング回路の構成図（その１）である。
【図１１】リオーダリング回路の構成図（その２）である。
【図１２】通信ＬＳＩの構成図である。
【図１３】並列計算機の構成図である。
【図１４】従来のリオーダリング制御を示す図である。
【符号の説明】
【００７４】
１０１  記憶手段
１０２  マトリクス手段
１０３  ベクタ手段
１０４  制御手段
２０１  記憶領域
２０２、２０４、２０５  ビットベクタ
２０３  ビットマトリクス
９０１  マイクロプロセッサ
９１１  命令デコーダ
９１２  フェッチ機構
９１３  バスインタフェース
９１４  キャッシュ
９１５  リザベーションステーション
９１６  リオーダバッファ
９１７  実行ユニット
９１８  リタイアメントレジスタファイル
１００１  解放順位指示器
１００２−２、１００２−ｎ、１１０４−１、１１０４−２、１１０４−ｎ  ＯＲ回路
１００３−１、１００３−２、１００３−ｎ、１１０３−１、１１０３−２、１１０３−ｎ  ＡＮＤ回路
１００４−１、１００４−２、１００４−ｎ  ラッチ回路
１００５、１００６、１１０２  マルチプレクサ
１００７  割り当て順位指示器
１１０１  解放要求ベクタ
１１０５−２、１１０５−ｎ  インバータ
１１０６−２、１１０６−ｎ  ＮＯＲ回路
１２０１  通信ＬＳＩ
１２１１  バスインタフェース
１２１２  送信バッファ
１２１３  送信管理部
１２１４  送信インタフェース
１３０１−１、１３０１−２、１３０１−ｎ  プロセッシングエレメント
【図１】
0004814653.tif 000002
【図２】
0004814653.tif 000003
【図３】
0004814653.tif 000004
【図４】
0004814653.tif 000005
【図５】
0004814653.tif 000006
【図６】
0004814653.tif 000007
【図７】
0004814653.tif 000008
【図８】
0004814653.tif 000009
【図９】
0004814653.tif 000010
【図１０】
0004814653.tif 000011
【図１１】
0004814653.tif 000012
【図１２】
0004814653.tif 000013
【図１３】
0004814653.tif 000014
【図１４】
0004814653.tif 000015