JP4621292B2 - キャッシュ制御装置およびキャッシュ制御方法 - Google Patents

Description

本発明は、複数のスレッドに属するリクエストに対してパイプライン処理を実行し、リクエストに応じたキャッシュデータを出力させるキャッシュ制御装置およびキャッシュ制御方法に関し、特に、確実に処理効率を向上することができるキャッシュ制御装置およびキャッシュ制御方法に関する。

従来、キャッシュメモリを備えたＣＰＵ（Central Processing Unit）などのプロセッサにおいては、例えばキャッシュメモリから命令を読み出す命令フェッチなどの処理の高速化を図るために、パイプライン処理が行われることがある。パイプライン処理は、１つの命令の読み出しを要求するリクエストに関する処理を複数のサイクル（またはステージともいう）に分け、各サイクルの処理を独立して実行する処理である。すなわち、先行するリクエストに対する１サイクルの処理が完了すると、すぐに次のリクエストに対して同じサイクルの処理が実行され、同時に、先行するリクエストに対しては、後段のサイクルの処理が実行される。したがって、パイプライン処理が行われる場合には、複数のリクエストに対して、流れ作業のように各サイクルの処理が実行されるため、同時に複数のリクエストに関する処理を進行させることができ、処理時間を大幅に短縮することができる。

このようなパイプライン処理が実行される際には、パイプラインにリクエストが投入された順序でリクエストに対する応答を出力する必要がある。具体的には、例えば命令フェッチのための複数のリクエストがパイプライン処理される場合、パイプラインにリクエストが投入された順序で、それぞれのリクエストに対応する命令をキャッシュメモリから出力する必要がある。これは、キャッシュメモリに対してリクエストを送出する命令制御部では、リクエストを送出した順序で命令が読み出されなければ、一連の処理を正常に実行できない虞があるからである。

ところで、キャッシュメモリは、ＣＰＵの外部に設けられるメインメモリなどと比較すると、高速に動作する一方で容量が小さいため、リクエストによって読み出しを要求された命令が必ずしもキャッシュメモリに格納されているとは限らない。このため、キャッシュメモリに格納されていない命令が要求されるとキャッシュミスが生じ、すぐには要求された命令がキャッシュメモリから出力されないことがある。このような場合、リクエストに関する処理を実行するパイプラインでは、処理を一旦中断（以下「ストール」という）する必要がある。

そこで、例えば特許文献１には、パイプライン処理がストールすると、パイプラインへの新たなリクエストの投入を停止させ、ストール発生時に既にパイプライン処理中であったリクエストをパイプラインへ再投入することが記載されている。こうすることにより、パイプラインへ投入されたリクエストの順序を崩すことなく、リクエストに対する応答を出力することができる。

特開２００７−２６３９２号公報

上述したように、パイプライン処理は、プロセッサにおける処理の高速化を図ることができるが、近年では、さらに処理効率を向上するため、一連のリクエストからなる複数のスレッドが並列にパイプライン処理されることがある。すなわち、例えば２つのスレッドに属するリクエストを交互に１つのパイプラインへ投入し、２つのスレッドの処理を同時に進行させて、処理効率を高めることができる。

しかしながら、このようなパイプライン処理において１つのスレッドに関するストールが発生すると、処理効率の向上に一定の限界があるという問題がある。すなわち、例えば２つのスレッドに属するリクエストが交互にパイプラインへ投入されている場合、上記特許文献１に記載の技術を利用すると、一方のスレッドに属するリクエストのみについてキャッシュミスなどが生じた際には、両方のスレッドに属するすべてのリクエストがパイプラインに再投入されることになる。つまり、キャッシュミスが生じておらず、処理が続行可能であったスレッドのリクエストもパイプラインに再投入され、このスレッドの処理が遅延してしまう。

本発明はかかる点に鑑みてなされたものであり、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上することができるキャッシュ制御装置およびキャッシュ制御方法を提供することを目的とする。

上記課題を解決するために、本発明は、複数のスレッドに属するリクエストに対してパイプライン処理を実行し、リクエストに応じたキャッシュデータを出力させるキャッシュ制御装置であって、複数のスレッドに属するリクエストに対して、キャッシュデータを出力するパイプライン処理を構成する個々の処理を互いに独立して実行する複数の処理手段と、前記複数の処理手段それぞれに対応して設けられ、個々の処理手段において処理中のリクエストに対応し当該リクエストが属するスレッドのパイプライン処理が停止したか否かを示すスレッド別のバリッドビットを保持する複数の保持手段と、パイプライン処理の停止を示すバリッドビットが保持された保持手段に対応する処理手段において処理中のリクエストを順次レジスタに格納する格納手段と、前記格納手段によってレジスタに格納されたリクエストおよび外部から新たに入力されるリクエストの優先度を決定して、いずれか１つのリクエストを前記複数の処理手段へ投入する投入手段とを有する構成を採る。

この構成によれば、パイプライン処理のストールが発生した際に、パイプライン処理がストールしたことをリクエストに対応するバリッドビットによってスレッド別に記憶し、スレッド別のバリッドビットによって、パイプライン処理を再実行するリクエストを決定する。このため、１つのスレッドのパイプライン処理がストールしても、他のスレッドの処理を続行することができ、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上することができる。

また、本発明は、上記構成において、前記格納手段は、前記複数の保持手段によって保持されたバリッドビットに基づいて、パイプライン処理が停止したスレッドに属するリクエストを前記複数の処理手段に投入された順序でレジスタに格納する構成を採る。

この構成によれば、バリッドビットに基づいて、パイプライン処理が停止したスレッドに属するリクエストに対してパイプライン処理が開始された順序でパイプライン処理を再実行することになる。このため、スレッド内でのリクエストの順序を崩すことなくストールしたスレッドのリクエストに対して再度パイプライン処理することができる。

また、本発明は、上記構成において、前記投入手段は、前記複数の保持手段によって保持されたバリッドビットをスレッドごとにラッチするラッチ手段と、前記ラッチ手段によってラッチされたバリッドビットおよび前記複数の処理手段へ前回投入されたリクエストに応じて今回前記複数の処理手段へ投入するリクエストを決定する決定手段とを含む構成を採る。

この構成によれば、バリッドビットをスレッドごとにラッチし、バリッドビットと前回パイプライン処理が開始されたリクエストとに応じて今回パイプライン処理を開始するリクエストを決定する。このため、ストールしたスレッドのリクエストおよび外部から新たに入力されたリクエストの中から確実に１つのリクエストを選択することができる。

また、本発明は、上記構成において、前記決定手段は、前記ラッチ手段によってラッチされたスレッドごとのバリッドビットがすべてパイプライン処理の停止を示していない場合に、外部から新たに入力されるリクエストを前記複数の処理手段へ投入すると決定する構成を採る。

この構成によれば、いずれのスレッドのパイプライン処理もストールしていない場合に、外部から新たに入力されるリクエストに対してパイプライン処理を開始させるため、処理中のリクエストに対して正常にパイプライン処理が実行されている間は、次々に新たなリクエストに対する処理を開始することができる。

また、本発明は、上記構成において、前記決定手段は、前記ラッチ手段によってラッチされた１つのスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該スレッドに属するリクエストであって前記格納手段によってレジスタに格納されたリクエストを前記複数の処理手段へ投入すると決定する構成を採る。

この構成によれば、１つのスレッドのパイプライン処理がストールした場合に、このスレッドに属するリクエストに対してパイプライン処理を開始させるため、パイプライン処理の再実行対象としてレジスタに格納されたリクエストに対して最優先でパイプライン処理を開始させることができ、ストールが発生したスレッドのリクエストに対して早急にパイプライン処理を実行することができる。

また、本発明は、上記構成において、前記決定手段は、前記ラッチ手段によってラッチされた複数のスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該複数のスレッドのうち前記複数の処理手段へ前回投入されたリクエストが属するスレッドとは異なるスレッドに属するリクエストを前記複数の処理手段へ投入すると決定する構成を採る。

この構成によれば、複数のスレッドのパイプライン処理がストールした場合に、前回パイプライン処理が開始されたスレッドとは異なるスレッドに属するリクエストに対してパイプライン処理を開始させる。このため、複数のスレッドが同時にストールした場合でも、１つのスレッドに属するリクエストのみに偏ってパイプライン処理の再実行が行われることがない。

また、本発明は、上記構成において、前記決定手段は、前記ラッチ手段によってラッチされた複数のスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該複数のスレッドのうち前記複数の処理手段へ前回リクエストが投入されてからの経過時間が最も長いスレッドに属するリクエストを前記複数の処理手段へ投入すると決定する構成を採る。

この構成によれば、複数のパイプライン処理がストールした場合に、前回パイプライン処理の再実行が行われてからの経過時間が最も長いスレッドに属するリクエストに対してパイプライン処理を開始させる。このため、複数のスレッドが同時にストールした場合でも、各スレッドのリクエストに対して公平にパイプライン処理を再実行させることができる。

また、本発明は、上記構成において、前記格納手段は、前記複数の処理手段に投入されたリクエストをスレッド別に前記複数の処理手段の数ずつ記憶する記憶手段を含み、対応するバリッドビットがパイプライン処理の停止を示すリクエストであって、最初に前記複数の処理手段に投入されたリクエストから順に前記記憶手段から出力してレジスタに格納する構成を採る。

この構成によれば、それぞれのスレッドについてパイプライン処理のサイクル数ずつリクエストを記憶し、ストールしたスレッドに属するリクエストのうち、最初にパイプライン処理が開始されたリクエストから順にレジスタに格納する。このため、パイプライン処理が実行中のリクエストを確実に記憶しておくことができ、パイプライン処理の再実行時に、スレッドごとにパイプライン処理が開始されたリクエストの順序を再現することができる。

また、本発明は、複数のスレッドに属するリクエストに対してパイプライン処理を実行し、リクエストに応じたキャッシュデータを出力させるキャッシュ制御方法であって、複数のスレッドに属するリクエストに対して、キャッシュデータを出力するパイプライン処理を構成する個々の処理を互いに独立して実行する複数の処理ステップと、１つのリクエストが前記複数の処理ステップの最終ステップに到達した際に当該リクエストが属するスレッドのパイプライン処理が停止する場合、前記複数の処理ステップのそれぞれに対応するウェイトポートのうちパイプライン処理が停止したスレッドに属するリクエストに対して処理中である処理ステップに対応するウェイトポートに、パイプライン処理が停止したことを示すバリッドビットをスレッド別に設定する設定ステップと、前記設定ステップにてパイプライン処理の停止を示すバリッドビットが設定されると、当該バリッドビットが設定されたウェイトポートに対応する処理ステップにおいて処理中のリクエストを順次レジスタに格納する格納ステップと、前記格納ステップにてレジスタに格納されたリクエストおよび外部から新たに入力されるリクエストの優先度を決定して、いずれか１つのリクエストに対して前記複数の処理ステップを開始させる制御ステップとを有するようにした。

この方法によれば、パイプライン処理のストールが発生した際に、パイプライン処理がストールしたことをリクエストに対応するバリッドビットによってスレッド別に記憶し、スレッド別のバリッドビットによって、パイプライン処理を再実行するリクエストを決定する。このため、１つのスレッドのパイプライン処理がストールしても、他のスレッドの処理を続行することができ、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上することができる。

本発明によれば、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上することができる。

図１は、一実施の形態に係る情報処理装置の要部構成を示すブロック図である。 図２は、一実施の形態に係る命令キャッシュ部の内部構成を示すブロック図である。 図３は、パイプライン処理に係るＴＬＢ処理部、タグＲＡＭ処理部、およびデータＲＡＭ処理部の具体的構成を示すブロック図である。 図４は、一実施の形態に係るバリッドビットと再投入リクエストの出力ポートとの対応を示す図である。 図５は、一実施の形態に係るプライオリティ決定部の内部構成を示すブロック図である。 図６は、一実施の形態に係る優先度の決定処理を説明する図である。 図７は、一実施の形態に係るパイプライン処理を示すフロー図である。 図８は、一実施の形態に係る優先度決定処理を示すフロー図である。 図９は、一実施の形態に係るパイプライン処理のタイムチャートの一例を示す図である。 図１０は、ストール発生時のリクエストおよびバリッドビットの状態を模式的に示す図である。 図１１は、図１０に続く図である。 図１２は、図１１に続く図である。 図１３は、図１２に続く図である。 図１４は、図１３に続く図である。 図１５は、図１４に続く図である。 図１６は、図１５に続く図である。

符号の説明

１３０ 命令制御部
１４０ 命令キャッシュ部
１４１ セレクタ
１４２ａ サイクルＴ処理部
１４２ｂ サイクルＭ処理部
１４２ｃ サイクルＢ処理部
１４２ｄ サイクルＲ処理部
１４３ａ、１４３ｂ、１４３ｃ、１４３ｄ ウェイトポート
１４４ プライオリティ決定部
１４４ａ−０ ＴＨ０用レジスタ更新部
１４４ａ−１ ＴＨ１用レジスタ更新部
１４４ｂ−０ ＴＨ０用レジスタ部
１４４ｂ−１ ＴＨ１用レジスタ部
１４４ｃ 前回出力用レジスタ部
１４４ｄ 優先度決定部
１４５ ＴＬＢ処理部
１４６ タグＲＡＭ処理部
１４７ データＲＡＭ処理部
１４８ リクエスト記憶部
１４９ レジスタ部

以下、本発明の一実施の形態について、図面を参照して詳細に説明する。本実施の形態の骨子は、パイプライン処理のストールが発生した場合に、複数のスレッドそれぞれについて各サイクルにおけるリクエストの有無を記録し、ストールの発生原因となったスレッドのリクエストのみをパイプラインに再投入し、他のスレッドのリクエストについては処理を続行することである。

図１は、本実施の形態に係る情報処理装置の要部構成を示すブロック図である。同図に示す情報処理装置は、ＣＰＵ１００、二次キャッシュ部２００、および主記憶部３００を有している。

ＣＰＵ１００は、二次キャッシュ部２００または主記憶部３００から命令やデータを読み出したり、読み出された命令に従ってデータに対する演算処理を行ったり、演算処理されたデータを二次キャッシュ部２００または主記憶部３００に書き込んだりする。具体的には、ＣＰＵ１００は、演算処理部１１０、データキャッシュ部１２０、命令制御部１３０、および命令キャッシュ部１４０を有している。

演算処理部１１０は、命令制御部１３０から命令を受け取り、命令に従ってデータキャッシュ部１２０からデータを読み出したり、データに対する演算処理を実行したり、演算処理後のデータをデータキャッシュ部１２０に書き込んだりする。

データキャッシュ部１２０は、データを一時的に記憶するキャッシュメモリを備えており、演算処理部１１０によって使用されるデータを格納する。また、データキャッシュ部１２０は、必要に応じて二次キャッシュ部２００からデータを読み出したり、二次キャッシュ部２００へデータを書き込んだりする。

命令制御部１３０は、命令のフェッチを要求するリクエストを命令キャッシュ部１４０へ送出し、リクエストに応じた命令を命令キャッシュ部１４０から取得する。このとき、命令制御部１３０は、複数のスレッドごとにリクエストを管理しており、それぞれのスレッドに属するリクエストを順番に命令キャッシュ部１４０へ送出する。そして、命令制御部１３０は、命令キャッシュ部１４０から取得された命令を演算処理部１１０へ受け渡す。

命令キャッシュ部１４０は、命令を一時的に記憶するキャッシュメモリを備えており、命令制御部１３０から送出されたリクエストを受け取ると、パイプライン処理を実行して要求された命令をキャッシュメモリから命令制御部１３０へ出力する。また、命令キャッシュ部１４０は、必要に応じて二次キャッシュ部２００から命令を読み出したり、二次キャッシュ部２００へ命令を書き込んだりする。なお、命令キャッシュ部１４０の具体的な構成および動作については、後に詳述する。

二次キャッシュ部２００は、命令およびデータを一時的に記憶するキャッシュメモリを備えており、ＣＰＵ１００のデータキャッシュ部１２０および命令キャッシュ部１４０との間で命令やデータをやり取りするとともに、必要に応じて主記憶部３００から命令またはデータを読み出したり、主記憶部３００へ命令またはデータを書き込んだりする。

主記憶部３００は、情報処理装置のメインメモリを備えており、ＣＰＵ１００による演算処理に必要な命令およびデータをすべて格納している。そして、これらの命令およびデータのうち、頻繁に使用されるものが二次キャッシュ部２００やＣＰＵ１００内のデータキャッシュ部および命令キャッシュ部１４０に格納されている。

図２は、本実施の形態に係る命令キャッシュ部１４０の内部構成を示すブロック図である。同図に示す命令キャッシュ部１４０は、セレクタ１４１、サイクルＴ処理部１４２ａ、サイクルＭ処理部１４２ｂ、サイクルＢ処理部１４２ｃ、サイクルＲ処理部１４２ｄ、ウェイトポート１４３ａ〜１４３ｄ、プライオリティ決定部１４４、ＴＬＢ（Transfer look-aside buffer）処理部１４５、タグＲＡＭ（random access memory）処理部１４６、データＲＡＭ処理部１４７、リクエスト記憶部１４８、およびレジスタ部１４９を有している。なお、図２は、スレッドＴＨ０およびスレッドＴＨ１の２つのスレッドに属するリクエストが命令制御部１３０から送出される場合の命令キャッシュ部１４０の構成を示している。また、図２は、命令キャッシュ部１４０内の機能ブロックを示しており、実際に情報処理装置に実装される命令キャッシュの具体的構成を限定するものではない。

セレクタ１４１は、命令制御部１３０から送出されるスレッドごとのリクエスト、およびレジスタ部１４９に保持されているスレッドごとのリクエスト（図中「Ｓ０」および「Ｓ１」で示す）のいずれかを出力する。具体的には、セレクタ１４１は、プライオリティ決定部１４４から出力されるセレクト信号に従い、３つのリクエストのうち最も優先されるリクエストをサイクルＴ処理部１４２ａへ出力する。

サイクルＴ処理部１４２ａは、セレクタ１４１によって選択されたリクエストの仮想アドレスでＴＬＢ処理部１４５をアクセスし、対応する物理アドレス情報を取得する。そして、サイクルＴ処理部１４２ａは、リクエストと共に物理アドレス情報をサイクルＭ処理部１４２ｂへ出力する。同時に、サイクルＴ処理部１４２ａは、リクエストをリクエスト記憶部１４８の１つのポートに記憶させる。このとき、サイクルＴ処理部１４２ａは、リクエスト記憶部１４８に設けられたスレッドごとの複数のポートを順番に使用してリクエストを記憶させる。すなわち、サイクルＴ処理部１４２ａは、前回リクエストが記憶されてからの経過時間が最も長いポートを入力されたリクエストの記憶用のポートとする。また、後述するように、サイクルＴ処理部１４２ａは、セレクタ１４１において選択されたリクエストのアドレスでタグＲＡＭをアクセスし、ウェイごとに登録されているデータの物理アドレスを次サイクルの処理部へ出力させる。同様に、サイクルＴ処理部１４２ａは、セレクタ１４１において選択されたリクエストのアドレスでデータＲＡＭをアクセスし、ウェイごとのデータを次サイクルの処理部へ出力させる。

サイクルＭ処理部１４２ｂは、ＴＬＢ処理部１４５から取得された物理アドレス情報とタグＲＡＭ処理部１４６におけるタグＲＡＭの物理アドレスとを比較し、ウェイを決定する。すなわち、サイクルＭ処理部１４２ｂは、データＲＡＭ処理部１４７に設けられた複数のウェイのいずれかに要求された命令がキャッシュされているか否かを物理アドレスのマッチングにより判定し、命令がキャッシュされている場合には、命令がキャッシュされたウェイを特定する。そして、サイクルＭ処理部１４２ｂは、リクエストと共に命令がキャッシュされたウェイの情報をサイクルＢ処理部１４２ｃへ出力する。

なお、入力された物理アドレス情報に一致する物理アドレスがタグＲＡＭ処理部１４６に格納されていなければ、要求された命令がデータＲＡＭ処理部１４７に格納されていないことになり、キャッシュミスが生じる。

サイクルＢ処理部１４２ｃは、サイクルＭ処理部１４２ｂにおけるウェイの決定に従って、データＲＡＭ処理部１４７におけるデータＲＡＭから出力されたデータをウェイセレクトして命令制御部１３０へ出力させる。このとき、サイクルＢ処理部１４２ｃは、命令制御部１３０へ出力される命令に、対応するリクエストの識別情報を付加する。そして、サイクルＢ処理部１４２ｃは、リクエストと共にデータＲＡＭ処理部１４７からの命令の出力が正常に実行されたか否かを示す結果情報をサイクルＲ処理部１４２ｄへ出力する。

サイクルＲ処理部１４２ｄは、リクエストおよび結果情報が入力されると、結果情報を参照してデータＲＡＭ処理部１４７から正常に命令が出力されたか否かを確認し、正常に処理が完了した場合には、その旨の完了信号を制御信号として命令制御部１３０へ送出する。また、サイクルＲ処理部１４２ｄは、例えばキャッシュミスの発生などにより処理をストールさせる必要がある場合には、その旨のビジー信号を制御信号として命令制御部１３０へ送出する。

これらのセレクタ１４１、サイクルＴ処理部１４２ａ、サイクルＭ処理部１４２ｂ、サイクルＢ処理部１４２ｃ、およびサイクルＲ処理部１４２ｄは、本実施の形態に係るパイプライン処理部を形成する。また、サイクルＴ処理部１４２ａからサイクルＲ処理部１４２ｄまでの各処理部は、例えばキャッシュミスなどによりストールが発生する際、ストールの原因となったリクエストがサイクルＲ処理部１４２ｄへ入力された時点で処理を中断する。そして、それぞれの処理部は、ストールの原因となったリクエストと同一スレッドのリクエストに関する処理中である場合に、それぞれ対応するウェイトポート１４３ａ〜１４３ｄにおいてストールしたスレッドのバリッドビットを１にセットする。同様に、それぞれの処理部は、ストールの原因となったリクエストと同一スレッドのリクエストに関する処理中でない場合に、それぞれ対応するウェイトポート１４３ａ〜１４３ｄにおいてストールしたスレッドのバリッドビットを０にセットする。

具体的には、例えばスレッドＴＨ０のリクエストに関してキャッシュミスが発生し、このリクエストがサイクルＲ処理部１４２ｄへ入力された時点で、サイクルＴ処理部１４２ａがスレッドＴＨ０に属するリクエストの処理中である場合、サイクルＴ処理部１４２ａは、ウェイトポート１４３ａにおけるスレッドＴＨ０のバリッドビットＴＷ０を１にセットし、サイクルＲ処理部１４２ｄは、ウェイトポート１４３ｄにおけるスレッドＴＨ０のバリッドビットＲＷ０を１にセットする。このように、バリッドビットが１にセットされたスレッドのリクエストは、再度パイプライン処理部に投入されることになる。

また、サイクルＴ処理部１４２ａからサイクルＲ処理部１４２ｄまでの各処理部は、バリッドビットに１をセットするのと同時に、実行中の処理に対応するリクエストが記憶されているリクエスト記憶部１４８のポートの識別情報をウェイトポート１４３ａ〜１４３ｄにセットする。すなわち、上述した例では、サイクルＴ処理部１４２ａおよびサイクルＲ処理部１４２ｄがそれぞれのリクエストを記憶するポートの識別情報をウェイトポート１４３ａおよびウェイトポート１４３ｄにセットする。ポートの識別情報は、サイクルＴ処理部１４２ａがリクエストをリクエスト記憶部１４８のポートに記憶する際に取得され、各処理部にリクエストと共に入力される。

ウェイトポート１４３ａ〜１４３ｄは、それぞれスレッドごとのバリッドビットを記憶しており、対応するサイクルの処理部１４２ａ〜１４２ｄにおける処理状況によってスレッドごとに１または０を取り得るバリッドビットを保持する。具体的には、ウェイトポート１４３ａ〜１４３ｄは、それぞれスレッドＴＨ０およびスレッドＴＨ１に対応する２つのバリッドビットを記憶している。すなわち、例えばウェイトポート１４３ａは、スレッドＴＨ０に対応するバリッドビットＴＷ０とスレッドＴＨ１に対応するバリッドビットＴＷ１とを保持する。その他のウェイトポート１４３ｂ〜１４３ｄも同様に、それぞれスレッドに対応するバリッドビットＭＷ０、ＭＷ１、ＢＷ０、ＢＷ１、ＲＷ０、およびＲＷ１を保持している。これらのバリッドビットは、初期状態ではすべて０にセットされている。

そして、いずれかのスレッドに対するパイプライン処理のストールが発生すると、ウェイトポート１４３ａ〜１４３ｄは、このスレッドのリクエストを処理中であった処理部１４２ａ〜１４２ｄに対応する２つのバリッドビットのうちストールが発生したスレッドのバリッドビットを１にセットする。このとき、ウェイトポート１４３ａ〜１４３ｄは、バリッドビットが１にセットされたリクエストを記憶するリクエスト記憶部１４８のポートの識別情報を同時に記憶する。すなわち、ウェイトポート１４３ａ〜１４３ｄは、ストールの発生によりパイプライン処理部への再投入が必要となったリクエストに対応するバリッドビットを１にセットする。このバリッドビットのセットは、スレッドごとに行われる。

さらに、ウェイトポート１４３ａ〜１４３ｄは、セレクタ１４１において選択されたリクエストに対応するバリッドビットを１から０に変更する。すなわち、セレクタ１４１において選択されたリクエストは、パイプライン処理部への再投入が実行されたため、対応するバリッドビットが初期状態の０に戻される。

プライオリティ決定部１４４は、ウェイトポート１４３ａ〜１４３ｄに保持されるバリッドビットからセレクタ１４１における出力の優先度を決定し、どのリクエストを出力させるかを示すセレクト信号をセレクタ１４１へ出力する。このとき、プライオリティ決定部１４４は、スレッドＴＨ０に関するバリッドビットＴＷ０、ＭＷ０、ＢＷ０、およびＲＷ０のいずれかが１であったり、スレッドＴＨ１に関するバリッドビットＴＷ１、ＭＷ１、ＢＷ１、およびＲＷ１のいずれかが１であったりする場合は、レジスタ部１４９に格納された再投入用のリクエストＳ０、Ｓ１を優先させる。なお、プライオリティ決定部１４４の具体的な構成および動作については、後に詳述する。

ＴＬＢ処理部１４５は、命令制御部１３０が要求する命令の仮想アドレスと実際に命令が記憶されている物理アドレスとの対応関係を記憶している。そして、ＴＬＢ処理部１４５は、サイクルＴ処理部１４２ａからアクセスされることにより、サイクルＴ処理部１４２ａに入力されたリクエストによって要求される命令の物理アドレス情報をサイクルＴ処理部１４２ａへ提供する。

タグＲＡＭ処理部１４６は、データＲＡＭ処理部１４７にキャッシュされた命令の主記憶部３００における物理アドレスを記憶している。そして、タグＲＡＭ処理部１４６は、サイクルＴ処理部１４２ａによってアクセスされたラインの物理アドレスをウェイごとにサイクルＭ処理部１４２ｂへ提供する。すなわち、タグＲＡＭ処理部１４６は、データＲＡＭ処理部１４７に格納されている命令の物理アドレスをサイクルＭ処理部１４２ｂへ提供する。

データＲＡＭ処理部１４７は、例えばセットアソシアティブ方式のキャッシュメモリを備えており、命令制御部１３０によって頻繁に要求される命令を複数のウェイそれぞれに記憶している。そして、データＲＡＭ処理部１４７は、サイクルＢ処理部１４２ｃによってウェイセレクトされた命令を命令制御部１３０へ出力する。

ここで、図３を参照して、パイプライン処理におけるＴＬＢ処理部１４５、タグＲＡＭ処理部１４６、およびデータＲＡＭ処理部１４７の具体的構成および処理内容について説明しておく。図３においては、各サイクルの処理部１４２ａ〜１４２ｄの下に、各サイクルに関連する構成を図示している。

まず、サイクルＴにおいては、仮想アドレスと物理アドレスの対応関係を記憶するＴＬＢ２０１から、リクエストに付随する仮想アドレス情報に対応する物理アドレス情報がレジスタ２０２へ出力される。同時に、リクエストによって指定されるラインの命令の物理アドレスがタグＲＡＭ２０５からレジスタ２０６へ出力される。さらに、複数のウェイ（図３においては２ウェイ）にそれぞれ命令を格納するデータＲＡＭ２０９からすべてのウェイの命令がレジスタ２１０へ出力される。

次に、サイクルＭにおいては、レジスタ２０２に格納された物理アドレス情報とレジスタ２０６に格納されたウェイごとの物理アドレスとが比較部２０７によってマッチングされ、レジスタ２０２に格納された物理アドレス情報に一致する物理アドレスの命令を保持するデータＲＡＭ２０９のウェイ情報がレジスタ２０８へ出力される。このウェイ情報は、命令制御部１３０が要求する命令が格納されたデータＲＡＭ２０９のウェイを示している。また、サイクルＭにおいては、レジスタ２１０に保持されたウェイごとの命令がレジスタ２１１へ出力される。

そして、サイクルＢにおいては、レジスタ２１１に格納されたウェイごとの命令のうち、レジスタ２０８に格納されたウェイ情報に対応する命令がセレクタ２１２から出力される。これにより、データＲＡＭ２０９の複数のウェイそれぞれに格納された命令のうち、リクエストによって要求された命令が命令制御部１３０によって取得されることになる。また、サイクルＢにおいては、レジスタ２０２に格納されていた物理アドレス情報がレジスタ２０３に格納され、続くサイクルＲにおいては、この物理アドレス情報がレジスタ２０４に格納される。

このように、各サイクルにおいては、要求された命令の物理アドレス情報、タグＲＡＭ２０５に保持されたすべての物理アドレスのうちアクセスされたラインの物理アドレス、およびデータＲＡＭ２０９に保持されたすべての命令のうちアクセスされたラインの命令が各サイクルに対応するレジスタに格納された上で、それぞれのサイクルの処理が実行されるため、各サイクルの処理を互いに独立して実行することが可能であり、同時に複数のリクエストに対する処理を流れ作業のように実行するパイプライン処理が可能となる。本実施の形態においては説明を簡略化するため、以上のような処理が図２に示すパイプライン処理部、ＴＬＢ処理部１４５、タグＲＡＭ処理部１４６、およびデータＲＡＭ処理部１４７によって実行されるものとする。

リクエスト記憶部１４８は、パイプライン処理部におけるサイクルＴからサイクルＲに対応する４つのポートをスレッドごとに備えており、サイクルＴ処理部１４２ａから出力されるすべてのリクエストをスレッドごとのいずれかのポートに一時的に記憶する。そして、リクエスト記憶部１４８は、ウェイトポート１４３ａ〜１４３ｄにおけるバリッドビットを監視し、いずれかのスレッドに関するバリッドビットに１となったものが検出されると、このバリッドビットに対応するリクエストを順次ポートからレジスタ部１４９へ出力する。

具体的には、リクエスト記憶部１４８は、スレッドごとの４つのバリッドビットを監視し、図４に示す表に従ってリクエストを出力するポートを決定する。図４は、スレッドＴＨ０およびスレッドＴＨ１に関して共通に使用される表を示しており、ＴＷからＲＷまでの４つのバリッドビットの値とリクエストを出力する出力ポートの識別情報を格納するウェイトポート１４３ａ〜１４３ｄとの対応関係を示している。なお、図中Ｓは、レジスタ部１４９にリクエストが格納されているか否かを示し、Ｓが１の時にはレジスタ部１４９がリクエストを保持中であることを示し、Ｓが０の時にはレジスタ部１４９が空いていることを示す。また、図４において、「＊」は、その値が出力ポートの決定に無関係であることを示し、例えばバリッドビットＲＷが１、かつレジスタ部１４９が空いていれば、他のバリッドビットの値とは無関係に、バリッドビットＲＷを格納するウェイトポート１４３ｄに識別情報が格納されたポートが出力ポートに決定される。

図４から明らかなように、レジスタ部１４９が空いているときには、最も先行してパイプライン処理部へ投入されたリクエストがレジスタ部１４９へ出力される。また、レジスタ部１４９がリクエストを保持中であるときには、レジスタ部１４９に保持されたリクエストの次にパイプライン処理部へ投入されたリクエストが、レジスタ部１４９が空くのと同時に出力されることになる。すなわち、例えばバリッドビットＢＷ、ＲＷが１でレジスタ部１４９がリクエストを保持中である場合、レジスタ部１４９に保持されているリクエストはバリッドビットＲＷに対応するリクエストであり、このリクエストがパイプライン処理部へ再投入されていないことから、まだバリッドビットＲＷが０に戻されていないと考えられる。そこで、図４においては、バリッドビットＢＷを格納するウェイトポート１４３ｃに識別情報が格納されたポートが出力ポートに決定され、レジスタ部１４９が空き次第、バリッドビットＢＷに対応するリクエストがリクエスト記憶部１４８から出力される。結果として、レジスタ部１４９に格納されるリクエストの順序は、パイプライン処理部へ投入された順序通りとなる。

その後、プライオリティ決定部１４４は、出力ポートから出力されてパイプライン処理部へ再投入されるリクエストに対応するウェイトポート１４３ａ〜１４３ｄのバリッドビットを０に変更する。すなわち、上記の例では、リクエスト記憶部１４８がバリッドビットＲＷを格納するウェイトポート１４３ｄに格納された識別情報の出力ポートからリクエストを出力した後、プライオリティ決定部１４４は、このリクエストがセレクタ１４１において選択される際に、バリッドビットＲＷを１から０に変更する。また、このとき、レジスタ部１４９が空くことから、バリッドビットＢＷに対応するリクエストがリクエスト記憶部１４８からレジスタ部１４９へ出力される。

他の例を挙げると、スレッドＴＨ０に関するパイプライン処理のストールが発生した際に、スレッドＴＨ０のリクエストが例えばサイクルＴ処理部１４２ａおよびサイクルＲ処理部１４２ｄに入力されている場合、バリッドビットＴＷ０、ＲＷ０が１にセットされている。そして、バリッドビットＲＷ０が１であることから、リクエスト記憶部１４８は、図４の表に従って、バリッドビットＲＷ０に対応して記憶された識別情報のポートからリクエストを出力する。そして、このリクエストがセレクタ１４１を経由してパイプライン処理部へ再投入される際に、プライオリティ決定部１４４は、バリッドビットＲＷ０を０に変更する。これにより、バリッドビットＴＷ０のみが１となることから、リクエスト記憶部１４８は、図４の表に従って、バリッドビットＴＷ０に対応して記憶された識別情報のポートからリクエストを出力する。

このように、リクエスト記憶部１４８は、いずれかのスレッドに関してパイプライン処理のストールが発生すると、図４の表に従ってリクエストを出力する出力ポートを決定することにより、後段のサイクルまでパイプライン処理が進行していたリクエストほど早くレジスタ部１４９へ出力する。したがって、先行してパイプライン処理部に投入されたリクエストほど早くパイプライン処理部への再投入の対象となり、それぞれのスレッドにおけるリクエストの投入順序が崩れることがない。

レジスタ部１４９は、リクエスト記憶部１４８から出力されるリクエストをスレッド別に保持し、セレクタ１４１へ出力する。レジスタ部１４９にリクエストが保持されている期間は、プライオリティ決定部１４４によってリクエストの出力の優先度が決定されているサイクルであり、パイプライン処理のサイクルＰに相当する。したがって、本実施の形態におけるパイプライン処理は、サイクルＰ、サイクルＴ、サイクルＭ、サイクルＢ、およびサイクルＲがこの順序で繰り返される処理である。

図５は、本実施の形態に係るプライオリティ決定部１４４の内部構成を示すブロック図である。図５に示すプライオリティ決定部１４４は、ＴＨ０用レジスタ更新部１４４ａ−０、ＴＨ１用レジスタ更新部１４４ａ−１、ＴＨ０用レジスタ部１４４ｂ−０、ＴＨ１用レジスタ部１４４ｂ−１、前回出力用レジスタ部１４４ｃ、および優先度決定部１４４ｄを有している。

各スレッド用のレジスタ更新部１４４ａ−０、１４４ａ−１は、それぞれスレッドごとの４つのバリッドビットのうち１つでも値が１（すなわち「バリッド」）のバリッドビットがあれば、それぞれのスレッド用のレジスタ部１４４ｂ−０、１４４ｂ−１に１をセットする。また、いずれかのスレッドがセレクト信号により選択された場合に、該当するスレッドのレジスタ更新部１４４ａ−０、１４４ａ−１は、対応するレジスタ部１４４ｂ−０、１４４ｂ−１を０にリセットする。なお、レジスタ更新部１４４ａ−０、１４４ａ−１は、レジスタ部１４４ｂ−０、１４４ｂ−１に対する１のセットと０へのリセットとが競合した場合には、１のセットを優先する。

したがって、レジスタ更新部１４４ａ−０、１４４ａ−１は、対応するスレッドのパイプライン処理がストールしてリクエストの再投入が必要となった場合に、ストールしたスレッドに対応するレジスタ部１４４ｂ−０、１４４ｂ−１に１をセットすることになる。

スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１は、対応するレジスタ更新部１４４ａ−０、１４４ａ−１によって更新され、保持した０または１を１サイクルの処理時間に対応する１クロックごとに優先度決定部１４４ｄへ出力する。

前回出力用レジスタ部１４４ｃは、優先度決定部１４４ｄから前回出力されたセレクト信号がスレッドＴＨ０のリクエストの再投入を選択する信号であった場合に０を保持し、前回出力されたセレクト信号がスレッドＴＨ１のリクエストの再投入を選択する信号であった場合に１を保持する。また、前回出力用レジスタ部１４４ｃは、前回出力されたセレクト信号が命令制御部１３０からの新たなリクエストの投入を選択する信号であった場合は、既に保持された値を継続して保持する。

優先度決定部１４４ｄは、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１および前回出力用レジスタ部１４４ｃに保持されたビットに基づいて、セレクタ１４１に入力されるリクエストの優先度を決定し、どのリクエストを出力させるかを示すセレクト信号をセレクタ１４１へ出力する。

具体的には、優先度決定部１４４ｄは、図６に示す表に従ってリクエストの優先度を決定し、セレクト信号を出力する。図６は、ＴＨ０用レジスタ部１４４ｂ−０、ＴＨ１用レジスタ部１４４ｂ−１、および前回出力用レジスタ部１４４ｃに保持されたそれぞれのビットの値とセレクト信号との対応関係を示している。ここで、図６中のセレクト信号Ｅは、命令制御部１３０から新たに入力されたリクエストをセレクタ１４１から出力させ、セレクト信号ＴＨ０は、レジスタ部１４９から再投入されるスレッドＴＨ０のリクエストをセレクタ１４１から出力させ、セレクト信号ＴＨ１は、レジスタ部１４９から再投入されるスレッドＴＨ１のリクエストをセレクタ１４１から出力させる。また、図６において、「＊」は、その値がリクエストの優先度の決定に無関係であることを示し、例えばスレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１内に保持されたビットがいずれも０であれば、前回出力用レジスタ部１４４ｃ内に保持されたビットの値とは無関係に、命令制御部１３０から出力されたリクエストを優先するセレクト信号Ｅが優先度決定部１４４ｄから出力される。

図６に示す表から明らかなように、優先度決定部１４４ｄは、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の双方に０が保持されていれば、命令制御部１３０からの新たなリクエストを優先させ、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の一方に１が保持されていれば、１を保持しているレジスタ部に対応するスレッドのリクエストを優先させる。これは、パイプライン処理がストールしたスレッドがある場合には、このスレッドのリクエストが最優先されることになり、レジスト部１４９からサイクルＴ処理部１４２ａへ再投入されることを意味している。

また、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の双方に１が保持されていれば、優先度決定部１４４ｄは、前回出力用レジスタ部１４４ｃに保持されたビットを参照し、前回とは異なるスレッドのリクエストを選択するセレクト信号を出力する。すなわち、スレッドＴＨ０、ＴＨ１の双方のパイプライン処理がストールしていれば、優先度決定部１４４ｄは、２つのスレッドのリクエストを交互にサイクルＴ処理部１４２ａに再投入させる。

なお、本実施の形態においては、スレッドＴＨ０およびスレッドＴＨ１の２つのスレッドのリクエストが並行して命令キャッシュ部１４０に入力されるものとしたが、３つ以上のスレッドのリクエストが並行して命令キャッシュ部１４０に入力される場合には、これらのスレッドのリクエストが順番にサイクルＴ処理部１４２ａに再投入されるようにすれば良い。このとき、優先度決定部１４４ｄは、前回リクエストが再投入されてからの経過時間が最も長いスレッドのリクエストを再投入するＬＲＵ（Least Recently Used）方式を採用しても良い。また、優先度決定部１４４ｄは、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１のいずれかに１が保持されてから所定時間経過した後にセレクト信号を出力する。

次いで、上記のように構成された命令キャッシュ部１４０におけるパイプライン処理について、図７に示すフロー図を参照しながら説明する。なお、図７に示すフロー図は、１つのリクエストに対する命令キャッシュ部１４０内での処理を示しており、このリクエストに対する処理が実行されている間にも、同じスレッドのリクエストや異なるスレッドのリクエストに対する処理が流れ作業のように実行されている。

まず、命令制御部１３０からスレッドごとのリクエストがパイプライン処理部へ投入され（ステップＳ１０１）、セレクタ１４１を経てサイクルＴ処理部１４２ａに入力される。このとき、プライオリティ決定部１４４によって、セレクタ１４１における優先度を決定する処理が実行されているが、ここでは、命令制御部１３０からの新たなリクエストが優先されたものとして、優先度決定処理の説明を省略する。セレクタ１４１における優先度決定処理は、パイプライン処理の最初のサイクルＰの処理に相当する。

リクエストがサイクルＴ処理部１４２ａに入力されると、サイクルＴ処理部１４２ａによって、リクエストと共に入力された仮想アドレス情報に対応する物理アドレス情報をＴＬＢ処理部１４５から取得する（ステップＳ１０２）。サイクルＴ処理部１４２ａによって取得される物理アドレス情報は、命令制御部１３０が要求する命令の主記憶部３００における物理アドレスである。そして、取得された物理アドレス情報およびリクエストは、サイクルＴ処理部１４２ａからサイクルＭ処理部１４２ｂへ出力される。また、サイクルＴ処理部１４２ａによって、リクエスト記憶部１４８におけるリクエストが属するスレッド用のいずれかのポートが選択され、リクエストが格納されてポートの識別情報が取得される。このとき、サイクルＴ処理部１４２ａによって選択されるポートは、該当するスレッド用のポートのうち前回リクエストを記憶してからの経過時間が最も長いポートである。以上の処理がサイクルＴの処理に相当する。

リクエストおよび物理アドレス情報がサイクルＭ処理部１４２ｂに入力されると、サイクルＭ処理部１４２ｂによって、入力された物理アドレス情報に一致する物理アドレスがタグＲＡＭ処理部１４６に記憶されているか否かが判定される（ステップＳ１０３）。そして、サイクルＭ処理部１４２ｂによって、命令制御部１３０が要求する命令が格納されたデータＲＡＭ処理部１４７内のウェイが特定される。そして、命令が格納されたデータＲＡＭ処理部１４７のウェイ情報およびリクエストは、サイクルＭ処理部１４２ｂからサイクルＢ処理部１４２ｃへ出力される。このとき、サイクルＭ処理部１４２ｂに入力された物理アドレス情報に一致する物理アドレスがタグＲＡＭ処理部１４６に記憶されていなければ、命令制御部１３０が要求する命令がデータＲＡＭ処理部１４７に格納されていないことになり、キャッシュミスが発生することになる。このため、サイクルＭ処理部１４２ｂからサイクルＢ処理部１４２ｃへ、キャッシュミスの発生が通知される。以上の処理がサイクルＭの処理に相当する。

リクエストおよびウェイ情報がサイクルＢ処理部１４２ｃに入力されると、サイクルＢ処理部１４２ｃの制御によって、ウェイ情報によって示されるデータＲＡＭ処理部１４７のウェイから命令が命令制御部１３０へ出力される（ステップＳ１０４）。キャッシュミスが発生していなければ、命令制御部１３０が要求する命令がデータＲＡＭ処理部１４７から出力され、この命令は、命令制御部１３０によって取得され、演算処理部１１０へ受け渡される。また、キャッシュミスが発生していれば、データＲＡＭ処理部１４７から命令制御部１３０へ命令が出力されることはない。このようなデータＲＡＭ処理部１４７からの命令の出力が正常に実行されたか否かを示す結果情報とリクエストは、サイクルＢ処理部１４２ｃからサイクルＲ処理部１４２ｄへ出力される。

リクエストおよび結果情報がサイクルＲ処理部１４２ｄに入力されると、サイクルＲ処理部１４２ｄによって、例えばキャッシュミスの発生などに伴うパイプライン処理の一時中断が必要か否かが結果情報に基づいて判定される（ステップＳ１０５）。この判定の結果、サイクルＢまでの処理が正常に完了し、命令がデータＲＡＭ処理部１４７から命令制御部１３０へ出力されていれば（ステップＳ１０５Ｎｏ）、パイプライン処理の完了を通知する完了信号が制御信号として、サイクルＲ処理部１４２ｄから命令制御部１３０へ送出される（ステップＳ１０７）。この場合には、以上の処理がサイクルＲの処理に相当し、１つのリクエストに対するパイプライン処理が終了したことになる。

一方、例えばキャッシュミスの発生などにより、いずれかのスレッドのパイプライン処理にストールが発生する場合は（ステップＳ１０５Ｙｅｓ）、命令キャッシュ部１４０内のパイプライン処理がビジー状態であることを通知するビジー信号が制御信号として、サイクルＲ処理部１４２ｄから命令制御部１３０へ送出される（ステップＳ１０６）。このビジー信号は、パイプライン処理がストールしたスレッドの情報を含んでおり、ビジー信号が命令制御部１３０によって受信されると、以後、パイプラインがストールしたスレッドのリクエストが命令制御部１３０から命令キャッシュ部１４０へ出力されなくなる。

また、パイプライン処理部においては、ストールが発生したことにより、サイクルＴ処理部１４２ａからサイクルＲ処理部１４２ｄまでの各処理部によって、処理中のリクエストが属するスレッドが確認され、処理中のリクエストがストール発生スレッドに属するものである場合には、対応するウェイトポート１４３ａ〜１４３ｄのバリッドビットが１に設定される（ステップＳ１０８）。すなわち、例えばスレッドＴＨ０に対するパイプライン処理にストールが発生し、サイクルＲ処理部１４２ｄにスレッドＴＨ０のリクエストが到達した時点でサイクルＭ処理部１４２ｂがスレッドＴＨ０のリクエストに関する処理中である場合には、サイクルＭ処理部１４２ｂおよびサイクルＲ処理部１４２ｄに対応するウェイトポート１４３ｂ、１４３ｄのスレッドＴＨ０に対応するバリッドビットＴＷ０、ＲＷ０が１に設定される。同時に、処理中のリクエストがストール発生スレッドに属するものでない場合には、対応するウェイトポート１４３ａ〜１４３ｄのバリッドビットが０に設定される。ストールが発生した場合には、以上の処理がサイクルＲの処理に相当する。

以上のパイプライン処理において、ストールが発生したスレッドに関しては処理が中断されるが、この間、ストールが発生していないスレッドに関しては処理が続行される。すなわち、例えばスレッドＴＨ０のパイプライン処理にストールが発生しても、スレッドＴＨ１のパイプライン処理が正常に実行されていれば、既に実行中であるスレッドＴＨ１のパイプライン処理はスレッドＴＨ０のパイプライン処理に関係なく続行される。したがって、複数のスレッドに対するパイプライン処理が並行して実行される場合に、いずれかのスレッドのパイプライン処理がストールしても、他のスレッドのパイプライン処理が続行され、確実に処理効率を向上することができる。

そして、パイプライン処理がストールしたスレッドのバリッドビットが１に設定されると、所定時間の間処理が待機状態となり（ステップＳ１０９）、所定時間経過後（ステップＳ１０９Ｙｅｓ）、バリッドビットを監視しているリクエスト記憶部１４８によって、パイプライン処理部へ再投入するリクエストが決定される（ステップＳ１１０）。具体的には、リクエスト記憶部１４８によって図４に示した表が用いられることにより、バリッドビットに１が設定されているリクエストが順次パイプライン処理部へ再投入されることになる。すなわち、ウェイトポート１４３ａ〜１４３ｄは、スレッドごとのバリッドビットを記憶しているため、ストール発生スレッドのリクエストが順次再投入対象のリクエストに決定される。このとき、図４から明らかなように、パイプライン処理が先行しているリクエストほど先に再投入対象となるため、ストール発生スレッド内のリクエストの処理順番が崩れることはない。

そして、各ウェイトポート１４３ａ〜１４３ｄのスレッドごとのバリッドビットには、リクエスト記憶部１４８においてリクエストが記憶されたポートの識別情報が対応付けられており、図４に示した表が使用されて再投入対象に決定されたバリッドビットに対応するポートからリクエストがレジスタ部１４９へ出力される。このリクエストは、レジスタ部１４９によって保持される。同時に、リクエスト記憶部１４８によって、レジスタ部１４９へ出力されたリクエストに対応するウェイトポート１４３ａ〜１４３ｄのバリッドビットが０に戻される。

レジスタ部１４９に再投入対象のリクエストが保持されると、プライオリティ決定部１４４によって、セレクタ１４１における出力の優先度を決定する優先度決定処理が実行される（ステップＳ１１１）。この優先度決定処理の間は、レジスタ部１４９にリクエストが保持されており、優先度決定処理はサイクルＰの処理に相当する。ここでの優先度決定処理は、再投入対象のリクエストに対する優先度決定処理であるため、図７において最後の処理となっているが、実際の優先度決定処理は、パイプライン処理部へ投入されるリクエストを決定する処理であり、パイプライン処理の最初の工程である。優先度決定処理の内容については、後に詳述する。

プライオリティ決定部１４４による優先度決定処理によってセレクタ１４１からの出力が再投入対象のリクエストに決定されると、レジスタ部１４９に保持されたリクエストがセレクタ１４１を介してサイクルＴ処理部１４２ａに再投入される（ステップＳ１１２）。以後、上述したステップＳ１０２のサイクルＴ処理から順番にパイプライン処理が実行され、ストール発生スレッドのパイプライン処理がリクエストの順番を崩すことなく再実行される。

次に、本実施の形態に係る優先度決定処理について、図８に示すフロー図を参照しながら説明する。

まず、レジスタ更新部１４４ａ−０によって、ウェイトポート１４３ａ〜１４３ｄにおけるスレッドＴＨ０のバリッドビット（ＴＷ０、ＭＷ０、ＢＷ０、およびＲＷ０）の中に１が設定されているものがあるか否かが判定され（ステップＳ２０１）、１つでも１が設定されているバリッドビットがあれば（ステップＳ２０１Ｙｅｓ）、ＴＨ０用レジスタ部１４４ｂ−０に値が１のビットを格納する（ステップＳ２０２）。また、１が設定されているバリッドビットがなければ（ステップＳ２０１Ｎｏ）、ＴＨ０用レジスタ部１４４ｂ−０には、値が０のビットが初期状態のまま格納されている（ステップＳ２０３）。

同様に、レジスタ更新部１４４ａ−１によって、ウェイトポート１４３ａ〜１４３ｄスレッドＴＨ１のバリッドビット（ＴＷ１、ＭＷ１、ＢＷ１、およびＲＷ１）の中に１が設定されているものがあるか否かが判定され（ステップＳ２０４）、１つでも１が設定されているバリッドビットがあれば（ステップＳ２０４Ｙｅｓ）、ＴＨ１用レジスタ部１４４ｂ−１に値が１のビットを格納する（ステップＳ２０５）。また、１が設定されているバリッドビットがなければ（ステップＳ２０４Ｎｏ）、ＴＨ１用レジスタ部１４４ｂ−１には、値が０のビットが初期状態のまま格納されている（ステップＳ２０６）。

そして、優先度決定部１４４ｄによって、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１および前回出力用レジスタ部１４４ｃに格納されたビットからセレクタ１４１における出力の優先度が判定され、セレクト信号が決定される（ステップＳ２０７）。セレクト信号の決定は、図６に示した表を用いて実行され、決定されたセレクト信号は、セレクタ１４１へ送出される（ステップＳ２０８）。

すなわち、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１に格納されたビットの値がいずれも０である場合には、命令制御部１３０からの新たなリクエストを優先させる旨のセレクト信号Ｅがセレクタ１４１へ送出される。また、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１に格納されたビットの値のいずれか一方のみが１である場合には、１が格納されたレジスタ部に対応するスレッドに属するリクエストを優先させる旨のセレクト信号ＴＨ０またはセレクト信号ＴＨ１がセレクタ１４１へ送出される。

さらに、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１に格納されたビットの値がいずれも１である場合には、前回出力用レジスタ部１４４ｃの内容が確認され、前回優先されたリクエストが属するスレッドとは異なるスレッドに属するリクエストを優先させる旨のセレクト信号ＴＨ０またはセレクト信号ＴＨ１がセレクタ１４１へ送出される。具体的には、例えば前回はスレッドＴＨ０のリクエストを優先させる旨のセレクト信号ＴＨ０が送出されていれば、今回はスレッドＴＨ１のリクエストを優先させる旨のセレクト信号ＴＨ１が送出される。これにより、複数のスレッドに関するパイプライン処理が同時にストールしている場合に、これらのスレッドのリクエストを公平にパイプライン処理部へ再投入させ、スレッド間での処理時間の偏りを排除することができる。

セレクト信号がセレクタ１４１へ送出されると、選択されたスレッドに対応するレジスタ部１４４ｂ−０、１４４ｂ−１がリセットされ（ステップＳ２０９）、優先度決定処理が終了する。この優先度決定処理は、それぞれのリクエストに対するサイクルＰの処理に相当し、パイプライン処理部へリクエストが投入（または再投入）されるか否かが決定される処理である。

次に、本実施の形態に係るパイプライン処理の具体例について、図９〜１６を参照して説明する。図９は、スレッドＴＨ０に属するリクエスト０−１、０−２と、スレッドＴＨ１に属するリクエスト１−１、１−２とが本実施の形態に係る命令キャッシュ部１４０に投入された場合の、各レジスタ部におけるビットおよびビジー信号の状態を示すタイムチャートである。

ここでは、スレッドＴＨ０に属するリクエストとスレッドＴＨ１に属するリクエストとが交互に命令キャッシュ部１４０に投入されるものとする。すなわち、クロック２においてリクエスト０−１に対するサイクルＰの処理が開始され、クロック３においてリクエスト１−１に対するサイクルＰの処理が開始され、クロック４においてリクエスト０−２に対するサイクルＰの処理が開始され、クロック５においてリクエスト１−２に対するサイクルＰの処理が開始される。

これらのリクエストに対するパイプライン処理は並行して実行されるが、スレッドＴＨ０に属するリクエスト０−１に関してキャッシュミスが発生すると、スレッドＴＨ０については、リクエスト０−１がサイクルＲの処理まで進行したクロック６の時点でストールが発生する。このとき、同じスレッドＴＨ０に属するリクエスト０−２は、サイクルＭの処理まで進行している。したがって、図１０に示すように、クロック６の完了時には、リクエスト０−１が入力されているサイクルＲ処理部１４２ｄに対応するウェイトポート１４３ｄのバリッドビットＲＷ０が１に設定され、リクエスト０−２が入力されているサイクルＭ処理部１４２ｂに対応するウェイトポート１４３ｂのバリッドビットＭＷ０が１に設定される。同時に、サイクルＲ処理部１４２ｄからは、スレッドＴＨ０に関してストールが発生したことを示すビジー信号０が命令制御部１３０へ送出される。

一方、この時点では、スレッドＴＨ１に関してはストールが発生しておらず、スレッドＴＨ１に属するリクエストに対する処理は続行される。しかし、スレッドＴＨ１に属するリクエスト１−１に関してキャッシュミスが発生すると、スレッドＴＨ１については、リクエスト１−１がサイクルＲの処理まで進行したクロック７の時点でストールが発生する。このとき、同じスレッドＴＨ１に属するリクエスト１−２は、サイクルＭの処理まで進行している。したがって、図１１に示すように、クロック７の完了時には、リクエスト１−１が入力されているサイクルＲ処理部１４２ｄに対応するウェイトポート１４３ｄのバリッドビットＲＷ１が１に設定され、リクエスト１−２が入力されているサイクルＭ処理部１４２ｂに対応するウェイトポート１４３ｂのバリッドビットＭＷ１が１に設定される。同時に、サイクルＲ処理部１４２ｄからは、スレッドＴＨ１に関してストールが発生したことを示すビジー信号１が命令制御部１３０へ送出される。

そして、スレッドＴＨ０に関するストールが発生してから所定の時間（ここでは５クロック）が経過すると、リクエスト記憶部１４８によって、ウェイトポート１４３ａ〜１４３ｄに保持されたバリッドビットＴＷ０、ＭＷ０、ＢＷ０、およびＲＷ０が参照され、ストールしたスレッドＴＨ０に属し、最初にパイプライン処理部に投入されたリクエスト０−１がレジスタ部１４９へ格納される。また、ウェイトポート１４３ａ〜１４３ｄに保持されたバリッドビットＴＷ１、ＭＷ１、ＢＷ１、およびＲＷ１が参照され、ストールしたスレッドＴＨ１に属し、先にパイプライン処理部に投入されたリクエスト１−１がレジスタ部１４９へ格納される。すなわち、図１２に示すように、クロック１２においては、バリッドビットＭＷ０、ＲＷ０、ＭＷ１、およびＲＷ１が１であるため、図４に示す表からバリッドビットＲＷ０およびＲＷ１に対応するリクエスト０−１および１−１がレジスタ部１４９に格納される。

また、クロック１２においては、ウェイトポート１４３ａ〜１４３ｄにおけるバリッドビットＭＷ０、ＲＷ０、ＭＷ１、およびＲＷ１が１であることから、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の双方に値が１のビットが格納される。ここでは、前回出力用レジスタ部１４４ｃに１が格納されているものとすると、クロック１２における優先度決定処理では、スレッドＴＨ０に属するリクエストをパイプライン処理部へ再投入することが決定され、クロック１３においては、リクエスト０−１に対するサイクルＴの処理が開始されることになる（図１３参照）。

そして、レジスタ部１４９にはスレッドＴＨ０に対応するリクエストが格納されていないことになるため、リクエスト記憶部１４８によって、ウェイトポート１４３ａ〜１４３ｄに保持されたバリッドビットＴＷ０、ＭＷ０、ＢＷ０、およびＲＷ０が参照され、ＭＷ０が１であることから、リクエスト０−２がレジスタ部１４９へ格納される。すなわち、図１３に示すように、クロック１３においては、バリッドビットＭＷ０、ＭＷ１、およびＲＷ１が１であるため、図４に示す表からバリッドビットＭＷ０およびＲＷ１に対応するリクエスト０−２およびリクエスト１−１がレジスタ部１４９に格納される。

また、クロック１３においては、ウェイトポート１４３ａ〜１４３ｄにおけるバリッドビットＭＷ０、ＭＷ１、およびＲＷ１が１であることから、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の双方に値が１のビットが格納される。また、クロック１２においてスレッドＴＨ０を選択するセレクト信号ＴＨ０が出力されているため、前回出力用レジスタ部１４４ｃには、値が０のビットが格納されている。このため、クロック１３における優先度決定処理では、スレッドＴＨ１に属するリクエストをパイプライン処理部へ再投入することが決定され、クロック１４においては、リクエスト１−１に対するサイクルＴの処理が開始されることになる（図１４参照）。このように、クロック１３においてスレッドＴＨ１のリクエストがパイプライン処理部へ再投入されることにより、プライオリティ決定部１４４によって、ウェイトポート１４３ｄのバリッドビットＲＷ１が０に戻される。

その後、レジスタ部１４９にはスレッドＴＨ１に対応するリクエストが格納されていないことになるため、リクエスト記憶部１４８によって、ウェイトポート１４３ａ〜１４３ｄに保持されたバリッドビットＴＷ１、ＭＷ１、ＢＷ１、およびＲＷ１が参照され、ＭＷ１が１であることから、リクエスト１−２がレジスタ部１４９へ格納される。すなわち、図１４に示すように、クロック１４においては、バリッドビットＭＷ０およびＭＷ１が１であるため、図４に示す表からバリッドビットＭＷ０およびＭＷ１に対応するリクエスト０−２およびリクエスト１−２がレジスタ部１４９に格納される。

また、クロック１４においては、ウェイトポート１４３ａ〜１４３ｄにおけるバリッドビットＭＷ０およびＭＷ１が１であることから、スレッドごとのレジスタ部１４４ｂ−０、１４４ｂ−１の双方に値が１のビットが格納される。また、クロック１３においてスレッドＴＨ１を選択するセレクト信号ＴＨ１が出力されているため、前回出力用レジスタ部１４４ｃには、値が１のビットが格納されている。このため、クロック１４における優先度決定処理では、スレッドＴＨ０に属するリクエストをパイプライン処理部へ再投入することが決定され、クロック１５においては、リクエスト０−２に対するサイクルＴの処理が開始されることになる（図１５参照）。このように、クロック１４においてスレッドＴＨ０のリクエストがパイプライン処理部へ再投入されることにより、プライオリティ決定部１４４によって、ウェイトポート１４３ｂのバリッドビットＭＷ０が０に戻される。

そして、クロック１５においては、ウェイトポート１４３ａ〜１４３ｄにおけるバリッドビットＭＷ１が１であることから、ＴＨ１用レジスタ部１４４ｂ−１のみに値が１のビットが格納される。このため、クロック１５における優先度決定処理では、スレッドＴＨ１に属するリクエストをパイプライン処理部へ再投入することが決定され、クロック１６においては、リクエスト１−２に対するサイクルＴの処理が開始されることになる（図１６参照）。このように、クロック１５においてスレッドＴＨ１のリクエストがパイプライン処理部へ再投入されることにより、プライオリティ決定部１４４によって、ウェイトポート１４３ｂのバリッドビットＭＷ１が０に戻される。

こうして、図１６に示すように、ウェイトポート１４３ａ〜１４３ｄに保持されるバリッドビットがすべて０になるとともに、順序を崩すことなくストール発生時に処理中であったリクエストがパイプライン処理部へ再投入されたことになる。このため、複数のスレッドに属するリクエストが並行して処理されるパイプライン処理にストールが発生した場合にも、それぞれのスレッドにおいてリクエストの順序を遵守して正常にリクエストに応じた命令を命令制御部１３０へ出力することができる。また、ウェイトポート１４３ａ〜１４３ｄにおいては、スレッドごとのバリッドビットを保持するため、いずれかのスレッドのパイプライン処理にストールが発生しても、他のスレッドに関してはパイプライン処理部へ投入済みのリクエストに対する処理を続行することができ、処理効率を向上することができる。

以上のように、本実施の形態によれば、パイプライン処理を構成する複数の処理それぞれについて、複数のスレッドのパイプライン処理がストールしたか否かを示すスレッドごとのバリッドビットをウェイトポートが保持し、バリッドビットに基づいてパイプライン処理部へ再投入するスレッド内でのリクエストの順序を決定するとともに、複数のスレッドのリクエストおよび外部から新たに入力されるリクエストのいずれを優先させるかを決定する。このため、スレッドごとにリクエストの再投入に関する管理を行うことができ、１つのスレッドのパイプライン処理がストールしても、既にパイプライン処理が開始されている他のスレッドの処理を続行することができ、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上することができる。

本発明は、複数のスレッドに対するパイプライン処理が実行される場合に、確実に処理効率を向上する際に適用することができる。

Claims (9)

1. 複数のスレッドに属するリクエストに対してパイプライン処理を実行し、リクエストに応じたキャッシュデータを出力させるキャッシュ制御装置であって、
   複数のスレッドに属するリクエストに対して、キャッシュデータを出力するパイプライン処理を構成する個々の処理を互いに独立して実行する複数の処理手段と、
   前記複数の処理手段それぞれに対応して設けられ、個々の処理手段において処理中のリクエストに対応し当該リクエストが属するスレッドのパイプライン処理が停止したか否かを示すスレッド別のバリッドビットを保持する複数の保持手段と、
   パイプライン処理の停止を示すバリッドビットが保持された保持手段に対応する処理手段において処理中のリクエストを順次レジスタに格納する格納手段と、
   前記格納手段によってレジスタに格納されたリクエストおよび外部から新たに入力されるリクエストの優先度を決定して、いずれか１つのリクエストを前記複数の処理手段へ投入する投入手段と
   を有することを特徴とするキャッシュ制御装置。
2. 前記格納手段は、
   前記複数の保持手段によって保持されたバリッドビットに基づいて、パイプライン処理が停止したスレッドに属するリクエストを前記複数の処理手段に投入された順序でレジスタに格納することを特徴とする請求項１記載のキャッシュ制御装置。
3. 前記投入手段は、
   前記複数の保持手段によって保持されたバリッドビットをスレッドごとにラッチするラッチ手段と、
   前記ラッチ手段によってラッチされたバリッドビットおよび前記複数の処理手段へ前回投入されたリクエストに応じて今回前記複数の処理手段へ投入するリクエストを決定する決定手段と
   を含むことを特徴とする請求項１記載のキャッシュ制御装置。
4. 前記決定手段は、
   前記ラッチ手段によってラッチされたスレッドごとのバリッドビットがすべてパイプライン処理の停止を示していない場合に、外部から新たに入力されるリクエストを前記複数の処理手段へ投入すると決定することを特徴とする請求項３記載のキャッシュ制御装置。
5. 前記決定手段は、
   前記ラッチ手段によってラッチされた１つのスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該スレッドに属するリクエストであって前記格納手段によってレジスタに格納されたリクエストを前記複数の処理手段へ投入すると決定することを特徴とする請求項３記載のキャッシュ制御装置。
6. 前記決定手段は、
   前記ラッチ手段によってラッチされた複数のスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該複数のスレッドのうち前記複数の処理手段へ前回投入されたリクエストが属するスレッドとは異なるスレッドに属するリクエストを前記複数の処理手段へ投入すると決定することを特徴とする請求項３記載のキャッシュ制御装置。
7. 前記決定手段は、
   前記ラッチ手段によってラッチされた複数のスレッドのバリッドビットの中にパイプライン処理の停止を示すバリッドビットがある場合に、当該複数のスレッドのうち前記複数の処理手段へ前回リクエストが投入されてからの経過時間が最も長いスレッドに属するリクエストを前記複数の処理手段へ投入すると決定することを特徴とする請求項３記載のキャッシュ制御装置。
8. 前記格納手段は、
   前記複数の処理手段に投入されたリクエストをスレッド別に前記複数の処理手段の数ずつ記憶する記憶手段を含み、
   対応するバリッドビットがパイプライン処理の停止を示すリクエストであって、最初に前記複数の処理手段に投入されたリクエストから順に前記記憶手段から出力してレジスタに格納することを特徴とする請求項１記載のキャッシュ制御装置。
9. 複数のスレッドに属するリクエストに対してパイプライン処理を実行し、リクエストに応じたキャッシュデータを出力させるキャッシュ制御装置によるキャッシュ制御方法であって、
   前記キャッシュ制御装置が有する複数の処理手段が、複数のスレッドに属するリクエストに対して、キャッシュデータを出力するパイプライン処理を構成する個々の処理を互いに独立して実行する複数の処理ステップと、
   １つのリクエストが前記複数の処理ステップの最終ステップに到達した際に当該リクエストが属するスレッドのパイプライン処理が停止する場合、前記キャッシュ制御装置が有する複数の処理手段が、前記複数の処理ステップのそれぞれに対応するウェイトポートのうちパイプライン処理が停止したスレッドに属するリクエストに対して処理中である処理ステップに対応するウェイトポートに、パイプライン処理が停止したことを示すバリッドビットをスレッド別に設定する設定ステップと、
   前記設定ステップにてパイプライン処理の停止を示すバリッドビットが設定されると、前記キャッシュ制御装置が有する格納手段が、当該バリッドビットが設定されたウェイトポートに対応する処理ステップにおいて処理中のリクエストを順次レジスタに格納する格納ステップと、
   前記キャッシュ制御装置が有する決定手段が、前記格納ステップにてレジスタに格納されたリクエストおよび外部から新たに入力されるリクエストの優先度を決定して、いずれか１つのリクエストに対して前記複数の処理ステップを開始させる制御ステップと
   を有することを特徴とするキャッシュ制御方法。

Images