(57)【特許請求の範囲】
【請求項１】
命令実行部と、命令バッファメモリと、命令フェッチ部とを持つマルチスレッドプロセッサが備える命令発行制御装置であって、
実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、
前記実行中のスレッドのうち、ストール中でないスレッドを選択するスレッド選択部と、
前記選択されたスレッドから同時発行可能な命令が発行されるように前記マルチスレッドプロセッサを制御する命令発行制御部とを備え、
前記リソース管理部は、前記命令実行部、前記命令バッファメモリ、および前記命令フェッチ部からの現在占有されている共有リソースの識別情報、共有リソースを占有するスレッドの識別情報、前記命令バッファメモリに格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数の情報を受理し、前記実行中のスレッドの各々について、当該スレッドが共有リソースを占有しているか否かを調べ、占有している場合には、あと何サイクルストールするかを示すストールサイクル数を、リソーステーブルを用いて管理しており、前記ストールサイクル数が１以上であるか否かを判断し、前記ストールサイクル数が０ならスレッドはストール中でないと判断して前記ストール情報を更新する
命令発行制御装置。
【請求項２】
命令バッファメモリと命令フェッチ部と命令実行部と命令発行制御装置とを備えたマルチスレッドプロセッサであって、
前記命令発行制御装置は、
実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、
前記実行中のスレッドのうち、ストール中でないスレッドを選択するスレッド選択部と、
前記選択されたスレッドから同時発行可能な命令が前記命令実行部へ発行されるよう制御する命令発行制御部とを備え、
前記リソース管理部は、前記命令実行部、前記命令バッファメモリ、および前記命令フェッチ部からの現在占有されている共有リソースの識別情報、共有リソースを占有するスレッドの識別情報、前記命令バッファメモリに格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数の情報を受理し、前記実行中のスレッドの各々について、当該スレッドが共有リソースを占有しているか否かを調べ、占有している場合には、あと何サイクルストールするかを示すストールサイクル数を、リソーステーブルを用いて管理しており、前記ストールサイクル数が１以上であるか否かを判断し、前記ストールサイクル数が０ならスレッドはストール中でないと判断して前記ストール情報を更新する
マルチスレッドプロセッサ。
【請求項３】
前記リソース管理部は、前記ストール情報としてのスレッドレディフラグを保持する第１フラグ保持部と、前記ストールサイクル数を管理するためのカウンタである第１カウンタとを備え、
前記第１カウンタが１以上であれば、前記スレッドレディフラグを０にセットし、
前記第１カウンタが０であれば、前記スレッドレディフラグを１にセットする
請求項２に記載のマルチスレッドプロセッサ。
【請求項４】
前記マルチスレッドプロセッサは、複数スレッドの各々の命令列を格納する複数の命令バッファを備え、
前記命令発行制御部は、前記複数の命令バッファに格納された命令のうち、次に前記命令実行部に発行されるべき同時発行が可能な１以上の命令を命令グループとしてグループ化する命令グループ化部を備えており、
前記命令グループ化部は、前記複数の命令バッファに格納された命令のうち、前記命令実行部で実行中である命令と依存関係をもたない命令を優先して前記命令グループに含めるように前記グループ化を行う
請求項３に記載のマルチスレッドプロセッサ。
【請求項５】
前記リソース管理部は、前記実行中のスレッドの各々が、共有リソースの各々を現在占有しているか否かを示すリソースレディフラグを保持する第２フラグ保持部と、
前記実行中のスレッドの各々が、前記共有リソースの各々を占有する残りサイクル数を示す第２カウンタとを有しており、
前記命令グループ化部は、前記複数の命令バッファに格納された命令のうち、現在占有されている共有リソースを使用する命令が前記命令グループに含まれないように前記グループ化を行う
請求項４に記載のマルチスレッドプロセッサ。
【請求項６】
前記命令グループ化部は、現在占有されている前記共有リソースの識別情報及び当該共有リソースを占有するスレッドの識別情報を、前記リソース管理部に通知し、
前記リソース管理部は、通知された前記共有リソースに対応する前記第２カウンタに応じて、通知された前記識別情報に対応するスレッドの前記第１カウンタを更新する
請求項５に記載のマルチスレッドプロセッサ。
【請求項７】
前記命令グループ化部は、前記複数の命令バッファに格納された命令が前記命令実行部で既に実行されている命令と依存関係を有する場合には、前記命令バッファに格納された命令が属する前記実行中のスレッドの識別情報及び、前記既に実行されている命令の残り実行サイクル数を前記リソース管理部に通知し、
前記リソース管理部は、通知された前記残り実行サイクル数に応じて前記識別情報に対応するスレッドの前記第１カウンタを更新する
請求項４に記載のマルチスレッドプロセッサ。
【請求項８】
前記マルチスレッドプロセッサは、前記命令実行部が用いるデータを保持するデータキャッシュメモリを備えており、
前記命令実行部は、データキャッシュミスが発生した場合に、実行中のスレッドの識別情報及び、前記データキャッシュミスが生じたデータを前記マルチスレッドプロセッサの外部にあるメインメモリから前記データキャッシュメモリへ転送するのに要するサイクル数を前記リソース管理部へ通知し、
前記リソース管理部は、通知された前記サイクル数に応じて前記識別情報に対応するスレッドの前記第１カウンタを更新する
請求項４に記載のマルチスレッドプロセッサ。
【請求項９】
前記マルチスレッドプロセッサは、命令キャッシュメモリと、
前記命令キャッシュメモリから命令を取得し、取得した前記命令を前記命令バッファへ供給する命令フェッチ部とを備えており、
前記命令フェッチ部は、命令をフェッチする際に命令キャッシュミスが発生した場合に、実行中のスレッドの識別情報及び、前記命令キャッシュミスが生じた命令を前記マルチスレッドプロセッサの外部にあるメインメモリから前記命令キャッシュメモリへ転送するのに要する第２のサイクル数を前記リソース管理部へ通知し、
前記リソース管理部は、通知された前記第２のサイクル数に応じて前記識別情報に対応するスレッドの前記第１カウンタを更新する
請求項８に記載のマルチスレッドプロセッサ。
【請求項１０】
前記命令実行部は、分岐命令を実行する場合には、その分岐先アドレスが確定するまでに要するサイクル数及び当該分岐命令が属するスレッドの識別情報を前記リソース管理部に通知し、
前記リソース管理部は、通知された前記サイクル数に応じて前記識別情報に対応するスレッドの第１カウンタを更新する
請求項４に記載のマルチスレッドプロセッサ。
【請求項１１】
前記マルチスレッドプロセッサは、バスコントロールユニットを備え、
前記バスコントロールユニットは、前記命令キャッシュメモリ、前記データキャッシュメモリ、及び前記マルチスレッドプロセッサの外部にあるメインメモリとそれぞれ接続されており、
前記命令キャッシュメモリ及び前記データキャッシュメモリでキャッシュミスが生じた時に、前記バスコントロールユニットが既に占有されている場合には、
前記バスコントロールユニットは、現在の占有があと何サイクル継続するかを示す残り占有サイクル数を前記リソース管理部へ通知し、
前記リソース管理部は、通知された前記残り占有サイクル数に応じて前記第１カウンタを更新する
請求項９に記載のマルチスレッドプロセッサ。
【請求項１２】
前記リソース管理部は、前記実行中のスレッドの各々について、前記第１カウンタが示す値よりも大きいストールサイクル数が通知された場合にのみ、当該第１カウンタが示す値を通知された前記ストールサイクル数で上書きする
請求項６〜１１のいずれか１項に記載のマルチスレッドプロセッサ。
【請求項１３】
前記リソース管理部は、前記マルチスレッドプロセッサの１サイクル動作毎に、前記第１カウンタ及び前記第２カウンタが示す値から事前に定められた特定の値を減ずる
請求項５に記載のマルチスレッドプロセッサ。
【請求項１４】
前記命令発行制御部は、さらに、分岐予測器を備えており、
前記分岐予測器は、前記命令実行部が分岐命令の実行を完了する前に分岐先アドレスを予測し、当該予測アドレスを用いて前記分岐命令を実行するとともに、前記分岐先アドレスの予測が外れることにより発生する可能性があるストールサイクル数を前記リソース管理部に通知し、
前記リソース管理部は、前記通知を受けた場合には、前記第１カウンタが示す値に通知されたストールサイクル数を加算する
請求項３に記載のマルチスレッドプロセッサ。
【請求項１５】
１サイクル動作で複数の命令グループを同時に命令実行部へ発行するＳＭＴ（Simultaneous Multi Threading）方式のマルチスレッドプロセッサであって、
前記マルチスレッドプロセッサは、前記命令実行部と、命令バッファメモリと、命令フェッチ部と、命令発行制御装置とを備えており、
前記命令発行制御装置は、
実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、
前記実行中のスレッドのうち、ストールしていないスレッドを選択するスレッド選択部と、
前記選択されたスレッドの各々に属する複数の命令グループを同時に前記命令実行部へ発行するよう制御する命令グループ化部とを備え、
前記リソース管理部は、前記命令実行部、前記命令バッファメモリ、および前記命令フェッチ部からの現在占有されている共有リソースの識別情報、共有リソースを占有するスレッドの識別情報、前記命令バッファメモリに格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数の情報を受理し、前記実行中のスレッドの各々について、当該スレッドが共有リソースを占有しているか否かを調べ、占有している場合には、あと何サイクルストールするかを示すストールサイクル数を、リソーステーブルを用いて管理しており、前記ストールサイクル数が１以上であるか否かを判断し、前記ストールサイクル数が０ならスレッドはストール中でないと判断して前記ストール情報を更新する
マルチスレッドプロセッサ。
【請求項１６】
命令実行部と、命令バッファメモリと、命令フェッチ部とを持つマルチスレッドプロセッサの命令発行制御方法であって、
前記命令発行制御方法は、
実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理ステップと、
前記実行中のスレッドのうち、ストールしていないスレッドを選択するスレッド選択ステップと、
前記選択されたスレッドから同時発行可能な命令が発行されるよう制御する命令発行制
御ステップとを含み、
前記リソース管理ステップにおいて、前記命令実行部、前記命令バッファメモリ、および前記命令フェッチ部からの現在占有されている共有リソースの識別情報、共有リソースを占有するスレッドの識別情報、前記命令バッファメモリに格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数の情報を受理し、前記実行中のスレッドの各々について、当該スレッドが共有リソースを占有しているか否かを調べ、占有している場合には、あと何サイクルストールするかを示すストールサイクル数を、リソーステーブルを用いて管理しており、前記ストールサイクル数が１以上であるか否かを判断し、前記ストールサイクル数が０ならスレッドはストール中でないと判断して前記ストール情報を更新する
命令発行制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数スレッドを実行可能なプロセッサアーキテクチャに関するものである。
【背景技術】
【０００２】
単一スレッドの実行時には、様々な要因（命令キャッシュミス、データキャッシュミス、命令間ペナルティ等）によってプロセッサがストールする。
【０００３】
このストールするサイクルによって、単一スレッドの実行時におけるプロセッサの実行効率（すなわち、スループット）が低下してしまう。
【０００４】
そこで、プロセッサの実行効率を向上させる為、複数のスレッドを同時に実行可能なアーキテクチャを有するマルチスレッドプロセッサが提案されている。
【０００５】
複数のスレッドを同時に実行可能なマルチスレッドプロセッサでは、例えばラウンドロビン方式を用いて、実行するスレッドを一定の時間間隔で切替えながらスレッドの実行を行う方式が知られてきた。
【０００６】
この場合、スレッド毎の処理に要する時間は、単一スレッド実行時よりも長くなるが、あるスレッドがストールしていても一定時間後には別のスレッドが実行される為、単一スレッド実行時と比較して全体のスループットが向上し、そのためプロセッサの実行効率が向上する。
【０００７】
しかしながら、複数スレッドの切替えの際に、単に一定の時間間隔でスレッドを切り替えたのでは、処理完了までの処理時間の見積もりが困難となり、実時間性が要求される分野での実用性が低い。また、スレッドの実行順序も最適ではないため、プロセッサの実行効率が悪い。
【０００８】
そこで、処理時間の見積もりや実行効率を向上させるスレッド切替えを実施する為に、特許文献１、２のような技術が提案されている。
【０００９】
特許文献１では、詳細な全体構成図を用いて、スレッドスケジューラの説明がなされている。この構成により、スレッドの優先度を考慮して、より優先度の高いスレッドの実行効率が高まる様にスレッドを選択する事が可能となる。
【００１０】
また、特許文献２では、スレッド内の命令発行グループをカウントし、スレッド処理に費やすサイクル数を計算し、優先度を考慮し、複数スレッドを効率的に切り替える技術に関して説明がなされている。
【００１１】
図１２を用いて、より具体的に説明する。
【００１２】
図１２は従来技術の命令発行制御装置を備えるマルチスレッドプロセッサの全体構成図を示す。
【００１３】
なお、本全体構成図は同時にＮスレッドの実行が可能なマルチスレッドプロセッサを想定しているが、本質的に、実行可能なスレッドの数になんら限定されない。
【００１４】
図１２に示すように、従来技術の命令発行制御装置を備えるマルチスレッドプロセッサは、命令キャッシュメモリ１０１と、命令フェッチ部１０２と、命令バッファ１０３と、命令発行制御装置１０４と、命令実行部１０７と、データキャッシュメモリ１０８と、レジスタファイル１０９とを備える。
【００１５】
命令キャッシュメモリ１０１は、命令フェッチ部の要求に基づき、命令を命令バッファ１０３へ供給する。要求された命令がキャッシュされていない場合、マルチスレッドプロセッサの外部にあるメインメモリ（図示なし）から命令を取得する。
【００１６】
命令フェッチ部１０２は、命令バッファ２０３の要求に従い、命令を命令キャッシュメモリ２０１から命令バッファ１０３へフェッチする。
【００１７】
命令バッファ１０３は、対応するスレッド毎にＮ個存在し、各スレッドが実行すべき命令の列を格納する。
【００１８】
命令発行制御装置１０４は、命令バッファ１０３に制御信号を送り、命令実行部１０７が次に実行すべき命令を命令グループとして発行する。
【００１９】
命令実行部１０７は、加算器や乗算器等、複数の演算器を含む処理部であり、命令バッファより発行された命令グループを実行する。
【００２０】
データキャッシュメモリ１０８は、命令実行部１０７の要求により、演算に必要なデータを命令実行部１０７へ供給する。データキャッシュメモリ１０８は、要求されたデータを格納していない場合には、マルチスレッドプロセッサの外部にあるメインメモリ（図示なし）から要求されたデータを取得した後、命令実行部１０７へ供給する。
【００２１】
レジスタファイル１０９は、対応するスレッド毎にＮ個存在し、各スレッドの命令実行に関するレジスタアクセスに対応する。すなわち、命令バッファ１０３に格納された各スレッドを実行することによって読み出し及び書き込みの対象とされるデータを保持するレジスタ群である。
【００２２】
命令発行制御装置１０４は、命令グループ化部１０５とスレッド選択部１０６を備える。
【００２３】
命令グループ化部１０５は、スレッド選択部１０６が選択したスレッドに対応する命令バッファ１０３内の命令のうち、命令バッファ内の依存関係に基づき、同時に実行できる１以上の命令を命令グループとしてグループ化する。
【００２４】
すなわち、選択されたスレッド毎に、同一サイクルに発行可能な命令を１つのグループとしてグループ化する。
【００２５】
スレッド選択部１０６は、あらかじめ決められ又は動的に変化する優先度に基づき、Ｎ個のスレッドの中から、次に実行すべきスレッドを決定する。
【００２６】
すなわち、図１に示す従来技術の命令発行制御装置１０４は、スレッド選択部１０６により予め決定され又は動的に変化する優先度により、実行するスレッドを決定する。また、実行するスレッドに対応する命令バッファ１０３に格納された命令列を発行可能なグループにグループ化して、命令実行部１０７へ発行する。
【先行技術文献】
【特許文献】
【００２７】
【特許文献１】国際公開第２００６／１２９７６７号
【特許文献２】特開２００８−１２３０４５号公報
【発明の概要】
【発明が解決しようとする課題】
【００２８】
しかしながら、従来のスレッド切替方式では、スレッドストールの発生によるマルチスレッドプロセッサのスループットの低下を十分に抑えることができないという課題があった。
【００２９】
より詳細には、図１１を用いて説明する。
【００３０】
図１１は、スレッドＡ８０１、スレッドＢ８０２及びスレッドＣ８０３の３つのスレッドに割り当てられた命令の実行タイミング及びストールタイミングを示す模式図である。
【００３１】
スレッドＡ８０１、スレッドＢ８０２、スレッドＣ８０３には、図に示すようにストールサイクルが発生する区間が予め存在しているものとする。
【００３２】
これらのスレッドを従来技術で実行した結果が、タイムチャート８０４、タイムチャート８０５及びタイムチャート８０６になる。
【００３３】
タイムチャート８０４は、スレッドＡ８０１による命令の実行タイミング及びストールタイミングを示す。
【００３４】
タイムチャート８０５は、スレッドＢ８０２による命令の実行タイミング及びストールタイミングを示す。
【００３５】
タイムチャート８０６は、スレッドＣ８０３による命令の実行タイミング及びストールタイミングを示す。
【００３６】
図１１のタイムチャート８０４〜８０６に示すように、例えばスレッドＡ８０１にサイクル８２１が割り当てられた後、スレッドＢ８０２にサイクル８２２が割り当てられ、次にスレッドＣ８０３にサイクル８２３が割り当てられる。
【００３７】
更に、スレッドＡ８０１にサイクル８２４が割り当てられ、次にスレッドＢ８０２にサイクル８２５が割り当てられ、次にスレッドＣ８０３にサイクル８２６が割り当てられる。
【００３８】
また、サイクル８３１〜サイクル８３６の６サイクルは、各スレッドにサイクルが割り当てられたにも係らず、各スレッドがストールしている為、スレッド実行出来ないサイクルとなる。
【００３９】
図１１では、サイクル８３１〜サイクル８３６の６サイクル分無駄になっている。
【００４０】
特許文献１では、キャッシュミスや分岐予測ミス等のストール時間を考慮してスレッドを切り替える事について言及されているが、それを実現するための処理に必要な制御線や具体的なアルゴリズムは開示されていない。また、依存関係を持つ命令間のペナルティを考慮したスレッド切替えに関しては、言及されていない。
【００４１】
特許文献２では、命令間ペナルティを考慮してスレッド制御を行うとの説明があるものの、具体的な制御方法に関しては言及されていない。
【００４２】
つまり、上記先行技術文献には、命令実行における様々な要因（命令／データキャッシュミス、命令間ペナルティ）に起因して発生するスレッドストールによって低下するマルチスレッドプロセッサのスループットを向上させるための具体的な技術が提案されていなかった。
【００４３】
本発明は、上記従来の問題点を解決するもので、スレッドストールの発生によるマルチスレッドプロセッサのスループットの低下を抑制することができる命令発行制御装置及びかかる命令発行制御装置を備えたマルチスレッドプロセッサを提供することを目的とする。
【課題を解決するための手段】
【００４４】
前記従来の課題を解決するために、本発明のある局面に係る命令発行制御装置は、実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、実行中のスレッドのうち、ストール中でないスレッドを選択するスレッド選択部と、選択されたスレッドから同時発行可能な命令が発行されるようにマルチスレッドプロセッサを制御する命令発行制御部とを備える。
【００４５】
この構成により、命令発行制御装置が備えるリソース管理部は、実行中のスレッドごとにストール中であるか否か及びストール中である場合にはあと何サイクルストールするかを管理できる。命令発行制御装置は、この管理情報を参照してストールするスレッドが実行されないように命令バッファから命令を発行する。その結果、スレッドストールの発生によるマルチスレッドプロセッサのスループットの低下を十分に抑えることができる命令発行制御装置を実現できる。
【００４６】
具体的には、リソース管理部は、実行中のスレッドの各々について、あと何サイクルストールするかを示すストールサイクル数を管理しており、ストールサイクル数が１以上であるか否かを判断し、ストールサイクル数が０ならスレッドはストール中でないと判断してストールサイクル識別情報を更新する。
【００４７】
また、本発明のある局面に係るマルチスレッドプロセッサは、命令実行部と命令発行制御装置とを備えたマルチスレッドプロセッサであって、命令発行制御装置は、実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、実行中のスレッドのうち、ストール中でないスレッドを選択するスレッド選択部と、選択されたスレッドから同時発行可能な命令が命令実行部へ発行されるよう制御する命令発行制御部とを備える。
【００４８】
この構成により、命令発行制御装置が備えるリソース管理部は、実行中のスレッドごとにストール中であるか否か及びストール中である場合にはあと何サイクルストールするかを管理できる。命令発行制御装置は、この管理情報を参照してストールするスレッドが実行されないように命令を発行する。その結果、スレッドストールの発生によるスループットの低下が十分に抑えられたマルチスレッドプロセッサを実現できる。
【００４９】
具体的には、リソース管理部は、実行中のスレッドの各々について、あと何サイクルストールするかを示すストールサイクル数を管理しており、ストールサイクル数が１以上であるか否かを判断し、ストールサイクル数が０ならスレッドはストール中でないと判断してストールサイクル識別情報を更新する。
【００５０】
より具体的には、リソース管理部は、ストール情報としてのスレッドレディフラグを保持する第１フラグ保持部と、ストールサイクル数を管理するためのカウンタである第１カウンタとを備え、第１カウンタが１以上であれば、スレッドレディフラグを０にセットし、第１カウンタが０であれば、スレッドレディフラグを１にセットする。
【００５１】
さらに、マルチスレッドプロセッサは、複数スレッドの各々の命令列を格納する複数の命令バッファを備え、命令発行制御部は、複数の命令バッファに格納された命令のうち、次に命令実行部に発行されるべき同時発行が可能な１以上の命令を命令グループとしてグループ化する命令グループ化部を備えており、命令グループ化部は、複数の命令バッファに格納された命令のうち、命令実行部で実行中である命令と依存関係をもたない命令を優先して命令グループに含めるようにグループ化を行う。
【００５２】
これにより、実行中の命令と依存関係をもつ命令を実行してスレッドがストールすることを回避し、その結果、実行効率を高めたマルチスレッドプロセッサを実現できる。
【００５３】
具体的には、リソース管理部は、実行中のスレッドの各々が、共有リソースの各々を現在占有しているか否かを示すリソースレディフラグを保持する第２フラグ保持部と、実行中のスレッドの各々が、共有リソースの各々を占有する残りサイクル数を示す第２カウンタとを有しており、命令グループ化部は、複数の命令バッファに格納された命令のうち、現在占有されている共有リソースを使用する命令が命令グループに含まれないようにグループ化を行う。
【００５４】
また、命令グループ化部は、現在占有されている共有リソースの識別情報及び共有リソースを占有するスレッドの識別情報を、リソース管理部に通知し、リソース管理部は、通知された共有リソースに対応する第２カウンタに応じて、通知された識別情報に対応するスレッドの第１カウンタを更新する。
【００５５】
また、命令グループ化部は、複数の命令バッファに格納された命令が命令実行部で既に実行されている命令と依存関係を有する場合には、命令バッファに格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数をリソース管理部に通知し、リソース管理部は、通知された残り実行サイクル数に応じて識別情報に対応するスレッドの第１カウンタを更新する。
【００５６】
また、マルチスレッドプロセッサは、命令実行部が用いるデータを保持するデータキャッシュメモリを備えており、命令実行部は、データキャッシュミスが発生した場合に、実行中のスレッドの識別情報及び、データキャッシュミスが生じたデータをマルチスレッドプロセッサの外部にあるメインメモリからデータキャッシュメモリへ転送するのに要するサイクル数をリソース管理部へ通知し、リソース管理部は、通知されたサイクル数に応じて識別情報に対応するスレッドの第１カウンタを更新する。
【００５７】
また、マルチスレッドプロセッサは、命令キャッシュメモリと、命令キャッシュメモリから命令を取得し、取得した命令を命令バッファへ供給する命令フェッチ部とを備えており、命令フェッチ部は、命令をフェッチする際に命令キャッシュミスが発生した場合に、実行中のスレッドの識別情報及び、命令キャッシュミスが生じた命令をマルチスレッドプロセッサの外部にあるメインメモリから命令キャッシュメモリへ転送するのに要するサイクル数をリソース管理部へ通知し、リソース管理部は、通知されたサイクル数に応じて識別情報に対応するスレッドの第１カウンタを更新する。
【００５８】
また、命令実行部は、分岐命令を実行する場合には、その分岐先アドレスが確定するまでに要するサイクル数及び分岐命令が属するスレッドの識別情報をリソース管理部に通知し、リソース管理部は、通知されたサイクル数に応じて識別情報に対応するスレッドの第１カウンタを更新する。
【００５９】
これにより、さらに分岐命令の実行にともない発生するストールサイクルもリソース管理部で管理し、ストールするスレッドを実行スレッドとして選択しないことにより、実行効率を高めたマルチスレッドプロセッサを実現できる。
【００６０】
また、マルチスレッドプロセッサは、バスコントロールユニットを備え、バスコントロールユニットは、命令キャッシュメモリ、データキャッシュメモリ、及びマルチスレッドプロセッサの外部にあるメインメモリとそれぞれ接続されており、命令キャッシュメモリ及びデータキャッシュメモリでキャッシュミスが生じた時に、バスコントロールユニットが既に占有されている場合には、バスコントロールユニットは、現在の占有があと何サイクル継続するかを示す残り占有サイクル数をリソース管理部へ通知し、リソース管理部は、通知された残り占有サイクル数に応じて第１カウンタを更新する。
【００６１】
これにより、同一のバスコントロールユニットに接続された他の要素（ＤＳＰ等）がバスコントロールユニットを占有している場合の占有時間をリソース管理部が管理することができ、その結果、より正確にストールサイクル数を管理し、マルチスレッドプロセッサのスループットを改善することができる。
【００６２】
なお、リソース管理部は、実行中のスレッドの各々について、第１カウンタが示す値よりも大きいストールサイクル数が通知された場合にのみ、第１カウンタが示す値を通知されたストールサイクル数で上書きする。
【００６３】
また、リソース管理部は、マルチスレッドプロセッサの１サイクル動作毎に、第１カウンタ及び第２カウンタが示す値から事前に定められた特定の値を減ずる。
【００６４】
また、本発明の他の局面に係るマルチスレッドプロセッサは、命令発行制御部は、さらに、分岐予測器を備えており、分岐予測器は、命令実行部が分岐命令の実行を完了する前に分岐先アドレスを予測し、予測アドレスを用いて分岐命令を実行するとともに、分岐先アドレスの予測が外れることにより発生する可能性があるストールサイクル数をリソース管理部に通知し、リソース管理部は、通知を受けた場合には、第１カウンタが示す値に通知されたストールサイクル数を加算する。
【００６５】
これにより、分岐予測器の分岐予測が外れることで発生する分岐予測ミスペナルティに起因したストールサイクルを事前にリソース管理部で管理することができ、分岐予測のミスに起因したストールサイクルを隠蔽する事が可能となる。
【００６６】
また、本発明の他の局面に係るマルチスレッドプロセッサは、１サイクル動作で複数の命令グループを同時に命令実行部へ発行するＳＭＴ（Simultaneous Multi Threading）方式のマルチスレッドプロセッサであって、マルチスレッドプロセッサは、命令発行制御装置を備えており、命令発行制御装置は、実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部と、実行中のスレッドのうち、ストールしていないスレッドを選択するスレッド選択部と、選択されたスレッドの各々に属する複数の命令グループを同時に命令実行部へ発行するよう制御する命令グループ化部とを備える。
【００６７】
これにより、ＳＭＴ方式のマルチスレッドプロセッサにおいても、ストールサイクルを管理することによりストールするスレッドを実行対象から除くことができ、マルチスレッドプロセッサのスループットを向上させることができる。
【００６８】
なお、本発明は、このような命令発行制御装置及びマルチスレッドプロセッサとして実現できるだけでなく、命令発行制御装置及びマルチスレッドプロセッサに含まれる特徴的な手段をステップとする命令発行制御方法として実現することもできる。
【発明の効果】
【００６９】
以上より、本発明は、スレッドストールの発生によるマルチスレッドプロセッサのスループットの低下を抑制することができる命令発行制御装置及びかかる命令発行制御装置を備えたマルチスレッドプロセッサを提供することができる。
【図面の簡単な説明】
【００７０】
【図１】図１は、本発明の実施の形態１における命令発行制御装置を備えたマルチスレッドプロセッサの全体構成図である。
【図２】図２は、本発明の実施の形態１におけるリソース管理テーブルの詳細を示す図である。
【図３】図３は、本発明の実施の形態１における第１カウンタの書換えアルゴリズムの処理の流れを示すフローチャートである。
【図４】図４は、本発明の実施の形態１における第２カウンタの書換えアルゴリズムの処理の流れを示すフローチャートである。
【図５】図５は、本発明の実施の形態１における命令発行制御部の機能を説明する図である。
【図６】図６は、本発明の実施の形態１における命令グループ化部による命令のグループ化、及び命令間ペナルティによる第１カウンタの上書きを行うためのアルゴリズムを説明するフローチャートである。
【図７】図７は、本発明の実施の形態１における効果を説明する模式図である。
【図８】図８は、実施の形態１の変形例におけるバスコントロールユニットを説明する模式図である。
【図９】図９は、本発明の実施の形態２における分岐予測器を含むマルチスレッドプロセッサの全体構成図である。
【図１０】図１０は、本発明の実施の形態３におけるマルチスレッドプロセッサの全体構成図である。
【図１１】図１１は、従来技術の命令発行制御装置を用いた場合の命令の実行タイミングを示す模式図である。
【図１２】図１２は、従来技術の命令発行制御装置を備えたマルチスレッドプロセッサの全体構成図である。
【発明を実施するための形態】
【００７１】
（実施の形態１）
以下、本発明の実施の形態１における命令発効制御装置、及び命令発行制御装置を備えたマルチスレッドプロセッサについて、図面を参照しながら説明する。
【００７２】
図１は、本発明の実施の形態１における命令発行制御装置を備えたマルチスレッドプロセッサ１００の全体構成図である。
【００７３】
従来技術からの変更点は、リソース管理部２１０を追加した点と、それに伴うスレッド選択部２０６及び命令グループ化部２０５の処理内容を変更した点である。
【００７４】
図１に示すように、マルチスレッドプロセッサ１００は、命令キャッシュメモリ２０１と、命令フェッチ部２０２と、命令バッファ２０３と、命令発行制御装置２２０と、命令実行部２０７と、データキャッシュメモリ２０８と、レジスタファイル２０９とを備える。
【００７５】
命令キャッシュメモリ２０１は、命令フェッチ部２０２の要求に基づき、命令を命令バッファ２０３へ供給する。要求された命令がキャッシュされていない場合、マルチスレッドプロセッサ１００の外部にあるメインメモリ９０４（後述する図８参照）から命令を取得する。
【００７６】
命令フェッチ部２０２は、命令バッファ２０３の要求に従い、命令を命令キャッシュメモリ２０１から命令バッファ２０３へフェッチする。
【００７７】
命令バッファ２０３は、対応するスレッド毎にＮ個存在し、各スレッドが実行すべき命令の列を格納する。
【００７８】
例えば、マルチスレッドプロセッサ１００がＮ個のスレッドを実行できる場合、第１命令バッファ〜第Ｎ命令バッファまでの合計Ｎ個の命令バッファがあるものとする。なお、ここでは原則として、Ｎ個の命令バッファを総称して命令バッファ２０３と記載する。
【００７９】
命令発行制御装置２２０は、命令バッファ２０３に制御信号を送り、命令実行部２０７が次に実行すべき、同時発行可能な１以上の命令を命令グループとして発行させるよう制御する。
【００８０】
命令実行部２０７は、加算器や乗算器等、複数の演算器を含む処理部であり、命令バッファ２０３より発行された、同時発行可能な１以上の命令からなる命令グループを実行する。
【００８１】
データキャッシュメモリ２０８は、命令実行部２０７の要求により、演算に必要なデータを命令実行部２０７へ供給する。
【００８２】
データキャッシュメモリ２０８は、要求されたデータを格納していない場合には、マルチスレッドプロセッサ１００の外部にあるメインメモリ９０４（後述する図８参照）から要求されたデータを取得した後、命令実行部２０７へ供給する。
【００８３】
レジスタファイル２０９は、対応するスレッド毎にＮ個存在し、各スレッドの命令実行に関するレジスタアクセスに対応する。すなわち、命令バッファ２０３に格納された各スレッドを実行することによって読み出し及び書き込みの対象とされるデータを保持するレジスタ群である。
【００８４】
命令発行制御装置２２０は、命令グループ化部２０５と、スレッド選択部２０６と、リソース管理部２１０とを備える。
【００８５】
命令グループ化部２０５は、スレッド選択部２０６により選択されたスレッドに対応する命令バッファ２０３内の命令列から、リソース管理部２１０の情報と、命令バッファ２０３内の依存関係とに基づき、次に命令実行部２０７に発行すべき同時発行可能な１以上の命令を命令グループとしてグループ化する。
【００８６】
スレッド選択部２０６は、予め決められたもしくは動的に変化する優先度と、リソース管理部２１０の情報を用いて、次に実行すべきスレッドを決定する。
【００８７】
リソース管理部２１０は、リソーステーブルを管理する。リソーステーブルは、マルチスレッドプロセッサ１００が実行可能なスレッド毎に対応して存在する。例えば、マルチスレッドプロセッサ１００がＮスレッドを実行可能であれば、第１リソーステーブルから第ＮリソーステーブルまでのＮ個のリソーステーブルが存在する。
【００８８】
リソース管理部２１０は、命令実行部２０７，命令バッファ２０３及び命令フェッチ部２０２からの情報を受理し、（１）各スレッドが共有リソースを占有しているか否か、（２）占有している場合には共有リソースが開放されるまでの残りサイクル数、（３）スレッドがストールしているか否か、及び（４）ストールしている場合には残りストールサイクル数、を対応するリソーステーブルを用いて管理する。
【００８９】
すなわち、マルチスレッドプロセッサ１００が備える命令発行制御装置２２０は、実行中のスレッドの各々がストール中であるか否かを示すストール情報を管理するリソース管理部２１０と、実行中のスレッドのうち、ストール中でないスレッドを選択するスレッド選択部２０６と、選択されたスレッドから同時発行可能な命令が発行されるようにマルチスレッドプロセッサ１００を制御する命令発行制御部２０４とを備えている。
【００９０】
ここで、実行中のスレッドとは、既に命令バッファ２０３に読み込まれているスレッドを意味する。本実施の形態では、第１命令バッファから第Ｎ命令バッファまでＮ個の命令バッファがあるので、それに対応して最大でＮ個のスレッドが実行中となりうる。
【００９１】
言い換えれば、命令発行制御装置２２０は、命令バッファ２０３に格納されているストール中でないスレッドに属する複数の命令のうち、同時発行可能な命令を、命令バッファ２０３から命令実行部２０７に発行する。
【００９２】
また、リソース管理部２１０は、実行中のスレッドの各々について、あと何サイクルストールするかを示すストールサイクル数を管理している。リソース管理部２１０はストールサイクル数が１以上であるか否かを判断し、ストールサイクル数が１以上ならスレッドはストール中であると判断して、対応するリソーステーブルのストール情報を更新する。
【００９３】
一方、ストールサイクル数が０ならスレッドはストール中でないとリソース管理部２１０は判断して、対応するリソーステーブルのストールサイクル識別情報を更新する。
【００９４】
具体的には、リソース管理部２１０は、ストール情報としてのスレッドレディフラグを保持する第１フラグ保持部３０４と、ストールサイクル数を管理するためのカウンタである第１カウンタ３０３とを備えている。
【００９５】
リソース管理部２１０は、第１カウンタ３０３が１以上であれば、スレッドレディフラグを０にセットし、第１カウンタ３０３が０であれば、スレッドレディフラグを１にセットする。
【００９６】
また、マルチスレッドプロセッサ１００は、複数スレッドの各々の命令列を格納する複数のバッファを有する命令バッファ２０３を備えており、命令発行制御部２０４は、命令バッファ２０３に格納された命令のうち、次に命令実行部２０７に発行されるべき同時発行が可能な１以上の命令を命令グループとしてグループ化する命令グループ化部２０５を備えている。
【００９７】
ここで、命令グループ化部２０５は、複数のバッファを有する命令バッファ２０３に格納された命令のうち、命令実行部２０７で実行中である命令と依存関係をもたない命令を優先して命令グループに含めるようにグループ化を行う。
【００９８】
さらにまた、リソース管理部２１０は、実行中のスレッドの各々が共有リソースの各々を現在占有しているか否かを示すリソースレディフラグを保持する第２フラグ保持部３０６と、実行中のスレッドの各々が共有リソースの各々を占有する残りサイクル数を示す第２カウンタ３０５とを有している。
【００９９】
ここで、命令グループ化部２０５は、複数のバッファを有する命令バッファ２０３に格納された命令のうち、現在占有されている共有リソースを使用する命令が、命令実行部２０７へ発行される命令グループに含まれないようにグループ化を行う。
【０１００】
また、命令グループ化部２０５は、現在占有されている共有リソースの識別情報及び共有リソースを占有するスレッドの識別情報を、リソース管理部２１０に通知し、リソース管理部２１０は、通知された共有リソースに対応する第２カウンタ３０５に応じて、通知された識別情報に対応するスレッドの第１カウンタ３０３を更新する。
【０１０１】
また、命令グループ化部２０５は、命令バッファ２０３に格納された命令が命令実行部２０７で既に実行されている命令と依存関係を有する場合には、命令バッファ２０３に格納された命令が属する実行中のスレッドの識別情報及び、既に実行されている命令の残り実行サイクル数をリソース管理部に通知する。
【０１０２】
その後、通知を受けたリソース管理部２１０は、通知された残り実行サイクル数に応じて、通知された識別情報に対応するスレッドの第１カウンタを更新する。
【０１０３】
また、命令実行部２０７は、データキャッシュミスが発生した場合には、実行中のスレッドの識別情報及び、データキャッシュミスが生じたデータをマルチスレッドプロセッサ１００の外部にあるメインメモリ９０４からデータキャッシュメモリ２０８へ転送するのに要するサイクル数をリソース管理部２１０へ通知する。
【０１０４】
その後、リソース管理部２１０は、通知されたサイクル数に応じて、通知された識別情報に対応するスレッドの第１カウンタ３０３を更新する。
【０１０５】
また、命令フェッチ部２０２は、命令をフェッチする際に命令キャッシュミスが発生した場合に、実行中のスレッドの識別情報及び、命令キャッシュミスが生じた命令をマルチスレッドプロセッサ１００の外部にあるメインメモリ９０４から命令キャッシュメモリ２０１へ転送するのに要するサイクル数をリソース管理部２１０へ通知する。
【０１０６】
次に、リソース管理部２１０は、通知されたサイクル数に応じて、通知された識別情報に対応するスレッドの第１カウンタ３０３を更新する。
【０１０７】
また、命令実行部２０７は、分岐命令を実行する場合には、その分岐先アドレスが確定するまでに要するサイクル数及び、その分岐命令が属するスレッドの識別情報をリソース管理部２１０に通知し、リソース管理部２１０は通知されたサイクル数に応じて、通知された識別情報に対応するスレッドの第１カウンタ３０３を更新する。
【０１０８】
なお、リソース管理部２１０は、実行中のスレッドの各々について、第１カウンタ３０３が示す値よりも大きいストールサイクル数が通知された場合にのみ、第１カウンタ３０３が示す値を通知されたストールサイクル数で上書きする。
【０１０９】
また、リソース管理部２１０は、マルチスレッドプロセッサ１００の１サイクル動作毎に、第１カウンタ３０３及び第２カウンタ３０５が示す値から事前に定められた特定の値を減ずる。
【０１１０】
以下、より詳細に説明する。
【０１１１】
図２は、本発明の実施の形態１におけるリソース管理テーブルの詳細を示す図である。
【０１１２】
リソース管理部２１０は、Ｎ個（マルチスレッドプロセッサ１００が実行するスレッド数をＮ個とする場合。以下同様）のスレッドに対応したＮ個のリソーステーブルから構成される。
【０１１３】
全てのリソーステーブルの構成は同じであるため、ここでは第Ｎリソーステーブル３０２を用いて説明する。
【０１１４】
第Ｎリソーステーブル３０２は、第１カウンタ３０３と、第１フラグ保持部３０４と、第２カウンタ３０５と、第２フラグ保持部３０６とを備える。
【０１１５】
第１カウンタ３０３は、スレッドがストールするサイクル数を示すスレッドストールサイクル３２１を保持するカウンタである。
【０１１６】
第１フラグ保持部３０４は、スレッドが実行可能であることを示すスレッドレディフラグ３１１を保持する。
【０１１７】
スレッドストールサイクル３２１が１以上の場合には、スレッドレディフラグ３１１は０であり、スレッドが実行不可能であることを示す。
【０１１８】
また、スレッドストールサイクル３２１が０の場合には、スレッドレディフラグ３１１は１であり、スレッドが実行可能であることを示す。
【０１１９】
第２カウンタ３０５は、共有リソースへのデータ書き込みを実行する命令により共有リソースへデータが書き込まれている場合、その書き込み命令が完了するまでのプロセッサの残りサイクル数を示すカウンタ（以後、命令実行サイクルともいう）を共有リソース毎に保持する。即ち各共有リソースへの書込完了迄のプロセッサのサイクル数を保持する。
【０１２０】
第２フラグ保持部３０６は、共有リソースが利用可能であることを示すリソースレディフラグを保持する。リソースレディフラグは、命令実行サイクルが１以上の場合には０であり共有リソースが使用不可能であること、及び命令実行サイクルが０の場合には１であり共有リソースが使用可能であることを示す。
【０１２１】
なお、リソースレディフラグ及び命令実行サイクルは、共有リソースの数だけ保持される。本実施の形態では、Ｍ個の共有リソースに対応し、第１リソースレディフラグ３１２から第Ｍリソースレディフラグ３１５及び第１命令実行サイクル３２２から第Ｍ命令実行サイクル３２５が、第２フラグ保持部３０６及び第２カウンタ３０５に、それぞれ保持されている。
【０１２２】
なお、第１カウンタ３０３、第１フラグ保持部３０４、第２カウンタ３０５、第２フラグ保持部３０６は、例えばプロセッサ内のレジスタにより実現することができる。
【０１２３】
図３は、本発明の実施の形態１における第１カウンタ３０３の書換えアルゴリズムの処理の流れを示すフローチャートである。
【０１２４】
図１の全体構成図に示すように、リソース管理部２１０は、命令実行部２０７、命令フェッチ部２０２、命令発行制御部２０４から制御信号を受け、各々データキャッシュミス、命令キャッシュミス、命令間ペナルティ等のスレッドがストールするイベント情報が入力される。イベント情報にはイベント固有のストールサイクル数が含まれており、このストールサイクル数も同時に、リソース管理部２１０へ通知される（Ｓ４０１）。
【０１２５】
例えば、命令実行部２０７にデータキャッシュミス、命令フェッチ部２０２に命令キャッシュミス、命令発行制御部２０４（が備える命令グループ化部２０５）に命令間ペナルティのイベントが各々発生した場合、命令実行部２０７、命令フェッチ部２０２及び命令グループ化部２０５は各々、発生したスレッド等の識別情報及びストールサイクル数をリソース管理部２１０に通知する。
【０１２６】
リソース管理部２１０は通知されたイベントのストールサイクル数と、既に第１カウンタ３０３内に格納されているスレッドストールサイクル３２１との比較を行う（Ｓ４０２）。そして、新たに通知されたイベントのストールサイクル数の方が大きい場合には、リソース管理部２１０は、既に第１カウンタ３０３に格納されているスレッドサイクル３２１を、新たに通知されたイベントのサイクル数で上書きする（Ｓ４０３）。
【０１２７】
また、新たに通知されたイベントのストールサイクル数の方が小さい場合には、リソース管理部２１０は既に第１カウンタ３０３に格納されているスレッドサイクル数を変更せず、そのまま保持する（Ｓ４０４）。
【０１２８】
上述の様なアルゴリズムにより、リソース管理部２１０は、各スレッドに対応したスレッドストールサイクルを管理する。
【０１２９】
図４は、本発明の実施の形態１における第２カウンタ３０５の書換えアルゴリズムの処理の流れを示すフローチャートである。
【０１３０】
リソース管理部２１０は、まず命令発行制御部２０４から、実行される命令の実行サイクル数と、命令が定義する使用共有リソースを通知される（Ｓ５０１）。
【０１３１】
次に、リソース管理部２１０は新たに通知された実行サイクル数が、２以上であるかを判定する（Ｓ５０２）。
【０１３２】
新たに通知された実行サイクル数が、２未満である場合、その命令が使用すると定義されている共有リソースは命令実行後、直ちに使用可能であるので、第２カウンタ３０５にて管理する必要はない。従ってリソース管理部２１０は第２カウンタ３０５を更新しない（Ｓ５０３）。
【０１３３】
新たに通知された実行サイクル数が、２以上である場合、その命令が使用すると定義されている共有リソースは命令実行後１サイクル以上完了を待たなければ使用できない。従って、この実行サイクル数は第２カウンタ３０５によって管理される必要がある。
【０１３４】
ここで、新たに通知された実行サイクル数をＳとし、命令完了サイクル数をＳ−１と定義する。リソース管理部２１０は、この命令完了サイクル数Ｓ−１が、対応する共有リソースの第２カウンタ３０５に保持された命令実行サイクルよりも大きいか否かを判定する（Ｓ５０４）。
【０１３５】
もし、第２カウンタ３０５が保持する命令実行サイクルの方が、Ｓ−１よりも大きい場合には、リソース管理部２１０は、既存の命令実行サイクルをそのまま保持する（Ｓ５０５）。
【０１３６】
また、Ｓ−１が、第２カウンタ３０５が保持する命令実行サイクルよりも大きい場合には、リソース管理部２１０は、対応する第２カウンタ３０５を命令完了サイクルＳ−１で上書きする（Ｓ５０６）。
【０１３７】
共有リソースが命令により使用されることが事前に定義されている場合には、リソース管理部２１０は上記アルゴリズムにより、対応する共有リソースを使用する命令の実行が完了するまでのサイクル数を第２カウンタ３０５に保持し、その共有リソースが使用不可である事を管理する。
【０１３８】
図５は、本発明の実施の形態１における命令発行制御部２０４の機能を説明する図である。
【０１３９】
既に説明した様に、命令発行制御部２０４は、命令グループ化部２０５と、スレッド選択部２０６とを備える。
【０１４０】
ここで、命令グループ化部２０５は、命令バッファ２０３に格納された命令列を、リソース管理部２１０内の第２フラグ保持部３０６及び命令バッファ２０３内の命令間の依存関係に基づき、同時発行可能な命令グループとしてグループ化する機能を有する。
【０１４１】
更に命令バッファ２０３に格納された命令間の命令間ペナルティを検出し、そのペナルティサイクルをスレッドストールサイクルとして、リソース管理部２１０に登録する機能も有する。
【０１４２】
次に、図６を用いて、上記リソース管理部２１０による命令の選択、及び命令間ペナルティによりスレッドストールサイクルを上書きするアルゴリズムを説明する。
【０１４３】
図６は、本発明の実施の形態１における命令グループ化部２０５による命令のグループ化、及び命令間ペナルティによる第１カウンタの上書きを行うためのアルゴリズムを説明するフローチャートである。
【０１４４】
まず、命令グループ化部２０５により、命令バッファ２０３に格納された命令列の内、同時発行可能な複数個の命令候補が選択され、その命令が使用する共有リソースが検出される（Ｓ７０１）。
【０１４５】
次に、命令グループ化部２０５は、選択された命令候補間又は命令候補とリソース管理部２１０が管理する共有リソースとの間に依存関係があるかをチェックする（Ｓ７０２）。
【０１４６】
選択された命令候補各々が、命令候補間及びリソース管理部２１０が管理する共有リソースの何れとも依存関係がない場合には、命令グループ化部２０５は、命令候補全てを命令グループとしてグループ化し、命令を発行するよう命令バッファ２０３へ制御信号を送り制御する（Ｓ７０３）。
【０１４７】
一方、命令候補間、あるいは命令候補とリソース管理テーブル、何れかに依存関係がある場合には、命令グループ化部２０５は、依存関係のある直前の命令迄の命令候補を命令グループとしてグループ化し、発行するよう制御する（Ｓ７０４）。
【０１４８】
さらに、依存関係に起因する命令間ペナルティサイクル分、スレッドがストールするとして、命令グループ化部２０５は、リソース管理部２１０に通知する（Ｓ７０５）。
【０１４９】
その通知は図３に示す、第１カウンタ３０３の書換えアルゴリズムを用いて、リソース管理部２１０により処理される。
【０１５０】
次に、スレッド選択部２０６の機能について、再び図５を用いて説明する。
【０１５１】
スレッド選択部２０６は、リソース管理部２１０の第１フラグ保持部３０４からスレッドレディフラグの値を取得する。スレッド選択部２０６は、スレッドレディフラグの値が１であるスレッドに限り、次に実行すべきスレッドの選択候補とする。
【０１５２】
上記の様な制御をする事で、命令発行制御部２０４は、ストール状態にあるスレッドを選択・発行する事がなく、常にレディ状態のスレッドを選択・発行し続けるので、マルチスレッドプロセッサのスループットが向上する。
【０１５３】
図７は、本発明の実施の形態１における効果を説明する模式図である。
【０１５４】
なお、図１１と同じ内容を示す図には同一の符号を付し、詳しい説明を省略する。
【０１５５】
スレッドＡ８０１、スレッドＢ８０２、スレッドＣ８０３には、図に示すようにストールサイクルが発生する区間が予め存在しているものとする。
【０１５６】
これらのスレッドを本実施の形態における命令発行制御装置２２０を備えたマルチスレッドプロセッサ１００で実行した結果が、タイムチャート８０７、タイムチャート８０８及びタイムチャート８０９になる。
【０１５７】
図１１に示したように、既存技術では、スレッドＡの実行結果８０４、スレッドＢの実行結果８０５、スレッドＣの実行結果８０６各々において、ストールサイクルが２サイクル発生する。
【０１５８】
この結果は、スレッド実行全体の２５％がストールしている事を意味する。
【０１５９】
一方、本実施の形態における命令発行制御装置２２０を備えたマルチスレッドプロセッサ１００で同じスレッドを実行した結果であるタイムチャート８０７からタイムチャート８０９では、ストールサイクルが１サイクルも発生していない。
【０１６０】
これは、命令発行制御装置２２０は各スレッドがストールしている間、そのスレッドを発行の選択候補としないためである。
【０１６１】
その結果として、従来技術に対して、本実施の形態における命令発行制御装置２２０を備えたマルチスレッドプロセッサ１００では、全体のスループットが２５％向上する事が確認出来る。
【０１６２】
（変形例）
次に、実施の形態１の変形例に係る命令発行制御装置２２０及びマルチスレッドプロセッサ１００について説明する。
【０１６３】
本変形例では、キャッシュミス等のペナルティがバスのアクセス状況によって変化する場合の対処方法を示す。
【０１６４】
図８は、本変形例におけるバスコントロールユニット９０３を説明する模式図である。
【０１６５】
図８に示すように、バスコントロールユニット９０３には、バスを介して、命令キャッシュメモリ２０１、データキャッシュメモリ２０８、プロセッサ外のメインメモリ９０４が接続されている。バスコントロールユニット９０３には、さらにＤＳＰ（Digital Signal Processor）９０５、他のＣＰＵ（Central Processing Unit）９０６、ＤＭＡＣ９０７（Direct Memory Access Controller）が接続されている。
【０１６６】
バスコントロールユニット９０３は、バスを制御する制御チップである。バスコントロールユニット９０３は、例えばメインメモリ９０４から命令キャッシュメモリ２０１へ命令を転送し、またメインメモリ９０４からデータキャッシュメモリ２０８へデータを転送する。
【０１６７】
メインメモリ９０４は、例えばマルチスレッドプロセッサ１００が命令実行部２０７で実行する命令やデータを外部記憶から一時的に読み込み、保持する記憶部である。メインメモリ９０４はＲＡＭ（Random Access Memory）等である。
【０１６８】
ＤＳＰ９０５は、デジタル信号処理に特化したマイクロプロセッサである。
【０１６９】
ＤＭＡＣ９０７は、ＣＰＵを介さずに，入出力機器とメモリ間でバスを通じて直接データをやりとりするＤＭＡ（Direct Memory Access）を実現するためのコントローラである。
【０１７０】
ここで、命令キャッシュメモリ２０１及びデータキャッシュメモリ２０８でキャッシュミスが生じた時に、バスコントロールユニット９０３が既に（例えば他のＣＰＵやＤＰＳ等の処理装置によって）占有されている場合には、バスコントロールユニット９０３は、現在の占有があと何サイクル継続するかを示す残り占有サイクル数をリソース管理部２１０へ通知する。
【０１７１】
次に、リソース管理部２１０は、通知された残り占有サイクル数に応じて第１カウンタを更新する。
【０１７２】
以上述べたことを、より具体的に説明する。
【０１７３】
実施の形態１では、命令キャッシュミス、及びデータキャッシュミスのペナルティは各々固定のペナルティサイクルとしていた。
【０１７４】
しかし、バスコントロールユニット９０３には、図８に示すように、他の要素であるＤＳＰ９０５、他のＣＰＵ９０６、ＤＭＡＣ９０７等が接続されている場合もある。この場合、例えば命令キャッシュメモリ２０１から命令転送の要求をバスコントロールユニット９０３に送ったとしても、他の要素がバスコントロールユニット９０３を占有している限りは、命令の転送は開始されない。
【０１７５】
即ち、他の要素がバスコントロールユニット９０３を占有しているサイクル数＋メインメモリ９０４から命令キャッシュメモリ２０１への転送サイクルを、リソース管理部２１０の第１カウンタ３０３に書き込む事で、実際に命令キャッシュへの転送が完了する迄のサイクル数を管理したスレッド制御が可能となる。
【０１７６】
以上述べたように、本変形例に係るマルチスレッドプロセッサ１００においては、同一のバスコントロールユニット９０３に接続された他の要素（ＤＳＰ９０５等）がバスコントロールユニット９０３を占有している場合の占有時間をリソース管理部２１０が管理することによって、より正確にストールサイクル数を管理し、マルチスレッドプロセッサ１００のスループットを改善することができる。
【０１７７】
（実施の形態２）
次に、本発明の実施の形態２における命令発行制御装置２２０及びマルチスレッドプロセッサ３００について説明する。
【０１７８】
本実施の形態において、命令発行制御部２０４が分岐予測器を備えるマルチスレッドプロセッサ３００は、ストールサイクル数を管理し、スループットを向上させることができる。
【０１７９】
図９は、本実施の形態における分岐予測器１００５を含むマルチスレッドプロセッサ３００の全体構成図である。なお、図１と同じ構成要素については同一の符号を付け、詳細な説明は省略する。
【０１８０】
図９に示すマルチスレッドプロセッサ３００と、図１に示したマルチスレッドプロセッサ１００との違いは、図９に示すマルチスレッドプロセッサ３００が備える命令発行制御装置２２０には、分岐予測器１００５が追加されている点である。
【０１８１】
すなわち、命令発行制御部２０４は、さらに、分岐予測器１００５を備えており、分岐予測器１００５は、命令実行部２０７が分岐命令の実行を完了する前に分岐先アドレスを予測し、予測したアドレスを用いて分岐命令を実行するとともに、分岐先アドレスの予測が外れることにより発生する可能性があるストールサイクル数をリソース管理部２１０に通知する。
【０１８２】
リソース管理部２１０は、分岐予測器１００５から分岐先アドレスを予測した旨の通知を受けた場合には、第１カウンタ３０３が示す値に通知されたストールサイクル数を加算する。
【０１８３】
次に、より詳細に説明する。
【０１８４】
一般的に、分岐命令が実行されると、その分岐先アドレスが確定する迄にペナルティサイクルが発生し、そのペナルティサイクルの間は後続の命令を発行する事が出来ない。その結果、命令実行部２０７はストールし、実行効率が低下する。
【０１８５】
分岐予測器１００５は、命令実行部２０７が分岐命令の実行を完了する前に分岐先アドレスを予測し、分岐命令実行のペナルティサイクルを隠蔽するための機構である。
【０１８６】
分岐予測器１００５は、命令バッファ２０３から分岐命令を発行する際にその分岐先アドレスを予測し、分岐先アドレスに指定された命令を投機的にフェッチさせて実行する。
【０１８７】
よって、分岐予測器１００５の予測が正しい場合、分岐命令実行のペナルティは隠蔽される。しかし、分岐予測器１００５の分岐予測が外れた場合には、分岐予測器１００５は、投機的に実行した命令をキャンセルし分岐予測前の状態から命令を再実行させる必要がある。
【０１８８】
従って、分岐予測器１００５による分岐予測が外れた場合には結局分岐命令実行相当分のペナルティが発生してしまう。
【０１８９】
この予測ミスに伴うペナルティを隠蔽する為に、本実施の形態におけるマルチスレッドプロセッサ３００が備える分岐予測器１００５は、分岐予測をした際に、分岐予測が外れたことに起因して発生する可能性のあるスレッドのストールサイクルをリソース管理部２１０へ通知する。
【０１９０】
上記の様に、分岐予測時にスレッドがストールする可能性があるとし、スレッドをストールさせる可能性のあるサイクル数をリソース管理部２１０が有する第１カウンタ３０３に加算する事で、分岐予測ミスペナルティに起因するストールサイクルを隠蔽する事が可能となる。
【０１９１】
なお、第１カウンタ３０３の更新に関しては、分岐予測器１００５の予測精度及び分岐命令の種類（通常分岐、間接分岐）によって、更新アルゴリズムを適宜変更する事でマルチスレッドプロセッサ３００のスループットをより向上させる事が可能となる。
【０１９２】
例えば、分岐予測器１００５は前回の分岐命令予測が正しかったか否かを記憶し、前回の予測が正しかった場合には、前回の予測を間違った場合よりも少ないストールサイクル数をリソース管理部２１０に通知することが考えられる。
【０１９３】
また、分岐予測器１００５は、分岐命令が通常分岐であれば、間接分岐よりも少ないストールサイクル数をリソース管理部２１０に通知することや、逆に、間接分岐よりも多いストールサイクル数をリソース管理部２１０に通知することも考えられる。
【０１９４】
以上述べた本実施の形態にかかる分岐予測器１００５を備えたマルチスレッドプロセッサ３００により、分岐予測器１００５の分岐予測が外れることで発生する分岐予測ミスペナルティに起因したストールサイクルを隠蔽する事が可能となる。
【０１９５】
（実施の形態３）
次に、本発明の実施の形態３における命令発行制御装置２２０及びマルチスレッドプロセッサ４００について説明する。
【０１９６】
本実施の形態に係るＳＭＴ（Simultaneous Multithreading）機能を有するマルチスレッドプロセッサ４００は、ストールサイクル数を管理することにより、スループットが向上する。
【０１９７】
図１０は、本実施の形態におけるマルチスレッドプロセッサ４００の全体構成図である。なお、図１と同じ構成要素については同一の符号を付け、詳細な説明は省略する。
【０１９８】
本実施の形態において新規に追加された構成要素は、命令実行チェック部１１０５である。
【０１９９】
実施の形態１の説明で述べたとおり、命令実行部２０７には、命令グループ化部２０５によりグループ化された同時実行可能な１以上の命令からなる命令グループが発行される。
【０２００】
ここで、命令グループ化部２０５がグループ化する命令は、命令実行部２０７が備える演算ユニットの構成に基づき決定される。
【０２０１】
より具体的に、命令実行部２０７が備える演算ユニットが、整数演算ユニット２個、メモリアクセスユニット１個、分岐ユニット１個で構成される場合を考える。
【０２０２】
この場合、最も優先度の高いスレッドにて整数演算ユニットを使用する３命令で構成される命令列があったとしても、整数演算ユニットが２個しかないため、命令グループ化部２０５は、２命令で構成される命令列からなる命令グループとしてグループ化してしまう。
【０２０３】
逆に、命令グループ化部２０５が、（同一のスレッドに属する命令間の依存関係により）整数演算ユニットを使用する１命令で構成されるグループをグループ化する場合には、整数演算ユニット及びそれ以外のユニットに空きがあるにも係わらず、１つの整数演算ユニットを使用する命令グループが発行される。
【０２０４】
その結果、命令実行部２０７の処理効率が低下するという課題が生じる。
【０２０５】
本実施の形態におけるマルチスレッドプロセッサ４００は、上記課題を、命令実行チェック部１１０５を設ける事で解決する。
【０２０６】
具体的には、レディ状態のスレッドから優先度順に実行すべきスレッドを決定する手順を以下の通りに行う。
【０２０７】
まず、命令グループ化部２０５は最優先のスレッドに属する命令をグループ化する。
【０２０８】
次に、命令実行チェック部１１０５は、命令実行部２０７が有する演算ユニットに空きがあるか否かをチェックする。
【０２０９】
もし、空きがある場合には、スレッド選択部２０６が次の優先度のスレッドを選択した後、そのスレッドに属する命令のうち先の命令グループと同時に（すなわち、同一サイクルで）発行可能な１以上の命令があれば、命令グループ化部２０５は、その命令をあらたな命令グループとしてグループ化し、命令実行部２０７へ発行するよう制御する。
【０２１０】
上記操作を命令発行の最大幅に到達、もしくは命令実行部２０７が有する演算ユニットの数の最大値、もしくはレディ状態にあるスレッドが無くなるまで繰り返す事で、同一発行サイクルに異なるスレッドの命令グループを発行する事が出来る。
【０２１１】
一般的に上記技術は、ＳＭＴとして知られているが、本実施の形態ではリソース管理部２１０が有する第１フラグ保持部３０４のスレッドレディフラグを考慮してスレッド選択部２０６がスレッドの選択を行う。
【０２１２】
さらに、リソース管理部２１０が有する第２フラグ保持部３０６のリソースレディフラグを考慮して、命令グループ化部２０５が命令のグループ化をする事に特徴がある。
【０２１３】
すなわち、１サイクル動作で複数の命令グループを同時に命令実行部２０７へ発行でき、命令発行制御装置２２０を備えたＳＭＴ方式のマルチスレッドプロセッサ４００において、命令発行制御装置２２０は、実行中のスレッドの各々がストール中であるか否かを示すストール情報としてスレッドレディフラグ３１１を保持する第１フラグ保持部３０４と、実行中のスレッドのうちストールしていないスレッドを選択するスレッド選択部２０６と、選択されたスレッドの各々に属する複数の命令グループを同時に命令実行部２０７へ発行するよう制御する命令グループ化部２０５とを備えている。
【０２１４】
こうした構成により、ＳＭＴ方式のマルチスレッドプロセッサ４００においても、ストールサイクルを管理することによりストールするスレッドを実行対象から除くことができ、マルチスレッドプロセッサ４００のスループットを向上させることができる。
【０２１５】
なお、上記実施の形態１〜３に係る命令発行制御装置及びマルチスレッドプロセッサに含まれる各処理部は典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又はすべてを含むように１チップ化されてもよい。
【０２１６】
ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０２１７】
また、集積回路化はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後にプログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）、又はＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
【０２１８】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて各処理部の集積化を行ってもよい。バイオ技術の適用等が可能性として考えられる。
【０２１９】
また、上記実施の形態１〜３に係る命令発行制御装置及びマルチスレッドプロセッサの機能の一部又は全てを、ＣＰＵ等のプロセッサがプログラムを実行することにより実現してもよい。
【０２２０】
さらに、本発明は上記プログラムであってもよいし、上記プログラムが記録された記録媒体であってもよい。また、上記プログラムは、インターネット等の伝送媒体を介して流通させることができるのは言うまでもない。
【０２２１】
また、上記実施の形態１〜３に係る命令発行制御装置及びマルチスレッドプロセッサの機能のうち少なくとも一部を組み合わせてもよい。
【０２２２】
また、上記で用いた数字は、すべて本発明を具体的に説明するために例示するものであり、本発明は例示された数字に制限されない。
【０２２３】
また、構成要素間の接続関係は、本発明を具体的に説明するために例示するものであり、本発明の機能を実現する接続関係はこれに限定されない。
【０２２４】
さらに、上記の実施の形態は、ハードウェア及び／又はソフトウェアを用いて構成されるが、ハードウェアを用いる構成は、ソフトウェアを用いても構成可能であり、ソフトウェアを用いる構成は、ハードウェアを用いても構成可能である。
【０２２５】
さらに、本発明の主旨を逸脱しない限り、本発明に係る実施の形態１〜３に対して当業者が思いつく範囲内の変更を施した各種変形例も本発明に含まれる。
【産業上の利用可能性】
【０２２６】
本発明は、プロセッサのスレッド発行制御に関するアーキテクチャの根幹に係わる技術であり、実行性能の高いプロセッサを提供可能とする技術である。本発明により、実行効率の高いスレッド発行制御を簡素なハードウェアにて、実現可能である。
【０２２７】
従って、組み込み分野、汎用ＰＣ分野、スーパーコンピューティング分野等の何れにおいても有用な技術となる。
【符号の説明】
【０２２８】
１００  マルチスレッドプロセッサ（実施の形態１）
１０１  命令キャッシュメモリ
１０２  命令フェッチ部
１０３  命令バッファ
１０４  命令発行制御装置
１０５  命令グループ化部
１０６  スレッド選択部
１０７  命令実行部
１０８  データキャッシュメモリ
１０９  レジスタファイル
２０１  命令キャッシュメモリ
２０２  命令フェッチ部
２０３  命令バッファ
２０４  命令発行制御部
２０５  命令グループ化部
２０６  スレッド選択部
２０７  命令実行部
２０８  データキャッシュメモリ
２０９  レジスタファイル
２１０  リソース管理部
２２０  命令発行制御装置
３００  マルチスレッドプロセッサ（実施の形態２）
３０２  第Ｎリソーステーブル
３０３  第１カウンタ
３０４  第１フラグ保持部
３０５  第２カウンタ
３０６  第２フラグ保持部
４００  マルチスレッドプロセッサ（実施の形態３）
９０３  バスコントロールユニット
９０４  メインメモリ
９０５  ＤＳＰ
９０６  他のＣＰＵ
９０７  ＤＭＡＣ
１００５  分岐予測器
１１０５  命令実行チェック部
【図１】
0005548037.tif 000002
【図２】
0005548037.tif 000003
【図３】
0005548037.tif 000004
【図４】
0005548037.tif 000005
【図５】
0005548037.tif 000006
【図６】
0005548037.tif 000007
【図７】
0005548037.tif 000008
【図８】
0005548037.tif 000009
【図９】
0005548037.tif 000010
【図１０】
0005548037.tif 000011
【図１１】
0005548037.tif 000012
【図１２】
0005548037.tif 000013