(57)【要約】マルチスレッディングプロセッサにおけるスケジューリング方法に関し、マルチスレッディングプロセッサの動作状態に応じてコンテキストユニットに割り当てられたスレッドから実行するスレッドを動的に選択し、同時実行するスレッド数または組み合わせを動的に変化させる。また、コンテキストスイッチの際にマルチスレッディングプロセッサの動作状態に応じてコンテキストユニットに割り当てるスレッドを動的に選択する。動作状態を判断する一例としては、スレッドごとに所定の期間内のフェッチストール回数、キャッシュミス回数、メモリアクセスレーテンシまたはＩＰＣカウンタなどが設定された基準値を超えるかどうかで判断する。組み合わせの選択法の一例としては、スレッドを同時実行する際マルチスレッディングプロセッサ内の特定ユニットへの処理集中を避けるように、負荷の高いものと少ないものを明示的に選択する方法がある。
2004044745.tif 000002
【特許請求の範囲】
【請求項１】
マルチスレッディングプロセッサにおけるスケジューリング方法であって、
実行可能な複数のスレッドを割り当て、
実行するスレッド数を前記マルチスレッディングプロセッサの動作状態に応じて動的に決定し、
前記割り当てられた複数スレッドから前記決定された数のスレッドを選択し、
同一期間内に前記選択されたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法。
【請求項２】
マルチスレッディングプロセッサにおけるスケジューリング方法であって、
コンテキストスイッチするスレッド数を前記マルチスレッディングプロセッサの動作状態に応じて動的に決定し、
実行可能な複数のスレッドから前記決定された数のスレッドを割り当て、
同一期間内に前記割り当てられたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法。
【請求項３】
請求項１または請求項２において、
さらにフェッチストール基準値を設定し、
所定の期間内のフェッチストール回数を記録し、
前記フェッチストール回数が前記フェッチストール基準値を超える場合スレッド数を減少させ、
前記フェッチストール回数が前記フェッチストール基準値を超えない場合スレッド数を増加させるようにスレッド数を決定することを特徴とするスケジューリング方法。
【請求項４】
請求項１または請求項２において、
さらにレーテンシ基準値を設定し、
所定の期間内のメモリアクセスレーテンシを記録し、
前記メモリアクセスレーテンシが前記レーテンシ基準値を超える場合スレッド数を減少させ、
前記メモリアクセスレーテンシが前記レーテンシ基準値を超えない場合スレッド数を増加させるようにスレッド数を決定することを特徴とするスケジューリング方法。
【請求項５】
請求項１または請求項２において、
さらに所定の期間内のフェッチストール回数を記録し、
前記フェッチストール回数が多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするスケジューリング方法。
【請求項６】
請求項１または請求項２において、
さらに所定の期間内のキャッシュミス回数を記録し、
前記キャッシュミス回数の多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするスケジューリング方法。
【請求項７】
請求項１または請求項２において、
さらに所定の期間内の１サイクルあたりに実行した命令数を記録し、
前記１サイクルあたり実行できる命令数の多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするスケジューリング方法。
【請求項８】
請求項１または請求項２において、
所定の条件で少なくとも１つのスレッドを選択し、
前記選択されたスレッドの命令をフェッチして実行し、
前記実行の際の資源競合度を記録し、
前記所定の条件を変更し、
所定の回数前記資源競合度の記録を繰り返す第１の期間と、
前記第１の期間で記録された資源競合度が最も低くなる条件に基づきスレッドを選択し、
前記選択されたスレッドの命令をフェッチし実行する第２の期間を有することを特徴とするスケジューリング方法。
【請求項９】
実行可能な複数のスレッドを割り当て、同一期間内に前記複数スレッドの命令を同時フェッチし、実行するマルチスレッディングプロセッサにおけるスケジューリング方法であって、
同一プロセスから複数のスレッドを優先的に選択し、
前記選択されたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法。
【請求項１０】
それぞれが１つのスレッドに対応付けられる複数のコンテキストユニットと、
スレッドを実行する際の資源競合度を測定する資源競合測定ユニットと、
前記測定された資源競合度に応じて前記コンテキストユニットに対応付けられたスレッドのうち少なくとも１つのスレッドを選択するとともに選択されたスレッドの命令をフェッチするフェッチユニットと、
前記フェッチされた命令をデコードするデコードユニットと、
デコードされた命令を実行する命令実行ユニットを備えたマルチスレッディングプロセッサ。
【請求項１１】
それぞれが１つのスレッドに対応付けられる複数のコンテキストユニットと、
スレッドを実行する際の資源競合度を測定する資源競合測定ユニットと、
前記コンテキストユニットに対応付けられるスレッドを前記測定された資源競合度に応じて少なくとも１つ選択するとともに選択されたスレッドの命令をフェッチするフェッチユニットと、
前記フェッチされた命令をデコードするデコードユニットと、
前記デコードされた命令を実行する命令実行ユニットを備えたマルチスレッディングプロセッサ。
【請求項１２】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、さらに所定の期間内のフェッチストール回数を記録するフェッチストールカウンタを有し、フェッチストール基準値が設定され、
前記フェッチストール回数が前記フェッチストール基準値を超える場合スレッド数を減少させ、
前記フェッチストール回数が前記フェッチストール基準値を超えない場合スレッド数を増加させるようにスレッドが選択されることを特徴とするマルチスレッディングプロセッサ。
【請求項１３】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、さらに所定の期間内のメモリアクセスレーテンシを記録するメモリアクセスレーテンシカウンタを有し、レーテンシ基準値が設定され、
前記メモリアクセスレーテンシが前記レーテンシ基準値を超える場合スレッド数を減少させ、
前記メモリアクセスレーテンシが前記レーテンシ基準値を超えない場合スレッド数を増加させるようにスレッドが選択されることを特徴とするマルチスレッディングプロセッサ。
【請求項１４】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、さらに所定の期間内のフェッチストール回数を記録するフェッチストールカウンタを有し、
前記フェッチストール回数の多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするマルチスレッディングプロセッサ。
【請求項１５】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、所定の期間内のキャッシュミス回数を記録するキャッシュミスカウンタを有し、
前記キャッシュミス回数の多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするマルチスレッディングプロセッサ。
【請求項１６】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、さらに所定の期間内の１サイクルあたり実行できる命令数を記録するＩＰＣカウンタを有し、
前記１サイクルあたり実行できる命令数の多いスレッドと少ないスレッドを組み合わせて選択することを特徴とするマルチスレッディングプロセッサ。
【請求項１７】
請求項１０または請求項１１において、
前記マルチスレッディングプロセッサは、所定の条件で少なくとも１つのスレッドを選択し、
前記選択されたスレッドの命令をフェッチして実行し、
前記実行の際の資源競合度を記録し、
前記所定の条件を変更し、
所定の回数前記資源競合度の記録を繰り返す第１の期間と、
前記第１の期間で記録された資源競合度が最も低くなる条件に基づきスレッドを選択し、
前記選択されたスレッドの命令をフェッチし、
前記フェッチされた命令をデコードし、
前記デコードされた命令を実行する第２の期間を有することを特徴とするマルチスレッディングプロセッサ。
【請求項１８】
それぞれが１つのスレッドに対応付けられる複数のコンテキストユニットと、
同一プロセスから少なくとも１つのスレッドを優先的に選択するとともに選択されたスレッドの命令をフェッチするフェッチユニットと、
前記フェッチされた命令をデコードするデコードユニットと、
前記デコードされた命令を実行する命令実行ユニットを備えたマルチスレッディングプロセッサ。
【発明の詳細な説明】
【技術分野】  本発明は、マルチスレッディングプロセッサにおけるスケジューリング方法およびマルチスレッディングプロセッサに関し、特に、実行するスレッドをマルチスレッディングプロセッサの動作状態に応じて動的に選択するスケジューリング方法およびマルチスレッディングプロセッサに関する。
【背景技術】  テキストエディタなどで作成される命令手順書であるプログラムがプロセッサで実行される状態をプロセスと呼ぶ。プロセスにより行われる処理を複数に分割したものがスレッドである。各スレッドに対し、そのスレッドが使用するレジスタ、プログラムカウンタなどの情報が存在する。この情報をコンテキストと呼ぶ。
近年複数のスレッド（またはプロセス）を１つのプロセッサ上で同時に実行可能なＳＭＴ（Ｓｉｍｕｌｔａｎｅｏｕｓ  Ｍｕｌｔｉ  Ｔｈｒｅａｄｉｎｇ）プロセッサが注目されている。マルチスレッディングプロセッサには、スレッド毎のコンテキストを保存するための複数のコンテキストユニットが実装されている。マルチスレッディングプロセッサは、コンテキストユニット毎にスレッドを割り当て、複数スレッドを同時実行する。
マルチスレッディングプロセッサは、各スレッドに対応するプログラムカウンタにより指定されるアドレスから命令を読み込み（これをフェッチと呼ぶ）、複数スレッドを同時実行する。同時に実行可能なスレッド数は実装されたコンテキストユニット数に制限されるため、マルチスレッディングプロセッサは、コンテキストユニットに割り当てられていない待機状態のスレッドから次に実行するスレッドを選択し、実行可能なスレッドを切り替える（これをコンテキストスイッチと呼ぶ）。本明細書においては、実行スレッドの選択やコンテキストスイッチによるスレッドの切り替えをスケジューリングと呼ぶ。
しかしながら、従来のスケジューリングでは、マルチスレッディングプロセッサは、実装されたコンテキストユニットをすべて使用し、コンテキストスイッチの際に選択された実行可能な全スレッドの命令を同時フェッチしていた。また、コンテキストスイッチの際に選択されるスレッドは、マルチスレッディングプロセッサの動作状態を反映したものではなかった。
従って、選択されたスレッドの組み合わせによっては、マルチスレッディングプロセッサ内の特定ユニットに処理が集中することで、効率的なスレッドの実行を妨げる資源競合による遅延が生じ、実装されたコンテキストユニットをすべて使用してスレッドを実行してもマルチスレッディングプロセッサの処理効率が向上しないでいた。
例えば、命令フェッチやメモリアクセス命令でアクセスされるデータが高速な転送レートのキャッシュ上になく、キャッシュミスが発生した場合には、低速な転送レートのメインメモリにアクセスすることで遅延が生じるが、マルチスレッディングプロセッサにおいても同様に複数スレッドの命令が同時フェッチ、実行されることでキャッシュ競合が発生してキャッシュミスが増加し、メモリアクセスによる遅延によってマルチスレッディングプロセッサの処理効率が向上しないことがある。
マルチスレッディングプロセッサにおける処理効率の向上を図る一手法としては、文献（Ｑｕｉｎｎ  Ａ．  Ｊａｃｏｂｓｏｎ，“Ｍｕｌｔｉｔｈｒｅａｄｉｎｇ  ｐｒｏｃｅｓｓｏｒ  ｗｉｔｈ  ｔｈｒｅａｄ  ｐｒｅｄｉｃｔｏｒ”，米国特許番号６，２４７，１２１  Ｊｕｎ．１２，２００１）がある。この特許は、マルチスレッディングプロセッサにおいて、分岐命令の実行を待たずに分岐予測に基づき投機的スレッドを生成し、マルチスレッディングプロセッサ上で実行するものであるが、同一または別プロセスが複数存在する場合のスケジューリングについての提案はされていない。
【発明の開示】
本発明の目的は、資源競合による遅延が生じないように、実行するスレッドを選択するスケジューリング方法およびマルチスレッディングプロセッサを提供することにある。
上記目的は、本発明第１の発明によれば、マルチスレッディングプロセッサにおけるスケジューリング方法であって、実行可能な複数のスレッドを割り当て、実行するスレッド数を前記マルチスレッディングプロセッサの動作状態に応じて動的に決定し、前記割り当てられた複数スレッドから前記決定された数のスレッドを選択し、同一期間内に前記選択されたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法を提供することで達成される。
また、上記目的は、本発明第２の発明によれば、マルチスレッディングプロセッサにおけるスケジューリング方法であって、コンテキストスイッチするスレッド数を前記マルチスレッディングプロセッサの動作状態に応じて動的に決定し、実行可能な複数のスレッドから前記決定された数のスレッドを割り当て、同一期間内に前記割り当てられたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法を提供することで達成される。
また、上記目的は、本発明第８の発明によれば、本発明第１の発明または第２の発明において、所定の条件で少なくとも１つのスレッドを選択し、前記選択されたスレッドの命令をフェッチして実行し、前記実行の際の資源競合度を記録し、前記所定の条件を変更し、所定の回数前記資源競合度の記録を繰り返す第１の期間と、前記第１の期間で記録された資源競合度が最も低くなる条件に基づきスレッドを選択し、前記選択されたスレッドの命令をフェッチし実行する第２の期間を有することを特徴とするスケジューリング方法を提供することで達成される。
また、上記目的は、本発明第９の発明によれば、実行可能な複数のスレッドを割り当て、同一期間内に前記複数スレッドの命令を同時フェッチし、実行するマルチスレッディングプロセッサにおけるスケジューリング方法であって、同一プロセスから複数のスレッドを優先的に選択し、前記選択されたスレッドの命令をフェッチし実行することを特徴とするスケジューリング方法を提供することで達成される。
また、上記目的は、本発明第１０の発明によれほ、それぞれが１つのスレッドに対応付けられる複数のコンテキストユニットと、スレッドを実行する際の資源競合度を測定する資源競合測定ユニットと、前記測定された資源競合度に応じて前記コンテキストユニットに対応付けられたスレッドのうち少なくとも１つのスレッドを選択するとともに選択されたスレッドの命令をフェッチするフェッチユニットと、前記フェッチされた命令をデコードするデコードユニットと、デコードされた命令を実行する命令実行ユニットを備えたマルチスレッディングプロセッサを提供することで達成される。
上記発明の実施の一形態によれば、各スレッドのフェッチストール回数を基に、同時実行するスレッドの数や組み合わせを動的に選択し、選択されたスレッドが実行される。また、別の実施の形態によれば、同一プロセスからのスレッドを優先的に選択し、選択されたスレッドが実行される。さらに別の実施の形態によれば、所定の条件を変更しながら、マルチスレッディングプロセッサの資源競合度を測定する第１の期間と、前記フェーズで測定された資源競合度が最も低くなる条件でスレッドが選択される第２の期間を有し、選択されたスレッドが実行される。
このように、マルチスレッディングプロセッサの動作状態に応じてコンテキストユニットに割り当てられたスレッドから実行するスレッドを動的に選択し、同時実行するスレッド数または組み合わせを動的に変化させることにより、資源競合による遅延を避け、マルチスレッディングプロセッサの処理効率を向上させることが可能になる。
【図面の簡単な説明】  図１は、本発明の実施の形態におけるマルチスレッディングプロセッサの構成例である。
図２は、第１の実施の形態を説明する図である。
図３は、フェッチストール回数による動作状態判定を説明するフローチャートである。
図４は、メモリアクセスレーテンシによる動作状態判定を説明するフローチャートである。
図５は、第２の実施の形態を説明する図である。
図６は、各スレッドと対応するフェッチストール回数の例である。
図７は、各スレッドと対応するキャッシュミス回数の例である。
図８は、各スレッドと対応するＩＰＣ値の例である。
図９は、第３の実施の形態を説明する図である。
図１０は、第４の実施の形態を説明する図である。
【発明を実施するための最良の形態】  以下、本発明の実施の形態について図面に従って説明する。しかしながら、本発明の技術的範囲はかかる実施の形態によって限定されるものではなく、特許請求の範囲に記載された発明とその均等物に及ぶものである。
図１は、本発明の実施の形態におけるマルチスレッディングプロセッサの構成例である。マルチスレッディングプロセッサ１は、各スレッドのコンテキストを保存するためのコンテキストユニットを同時実行するスレッド数分有する。図１の例ではコンテキストユニット１０〜１３の４つである。各コンテキストユニットは、演算結果を格納するためのレジスタ１４と、次に命令を読み出すべきアドレスを格納するプログラムカウンタ１５と、読み出された命令を格納する命令バッファ１６とを有する。
マルチスレッディングプロセッサにおける命令実行の流れは次のようなものである。まず、フェッチユニット１７は、各スレッドのプログラムカウンタ１５により指定されるアドレスの命令をフェッチするため、キャッシュメモリ２２を検索する。キャッシュメモリ２２に指定されたアドレスが無ければ（これをキャッシュミスと呼ぶ）メインメモリ２から、キャッシュメモリ２２に指定されたアドレスがあればキャッシュメモリ２２から、指定されたアドレスの命令を対応するコンテキストユニットの命令バッファ１６に格納する。デコードユニット１９は、命令バッファ１６に格納された命令をデコードし、命令実行ユニット２０がデコードされた命令を実行する。
また、マルチスレッディングプロセッサ１は、その動作状態を判断するために以下のカウンタを備えている。フェッチの際に何らかの原因で命令取得に失敗し（例えば、キャッシュミスの発生など）デコード処理が行えない場合がある（これをフェッチストールと呼ぶ）。フェッチユニット１７は、スレッドごとにフェッチストール回数を記録するフェッチストールカウンタ１８を備える。
命令実行ユニット２０は、１サイクルあたりに実行した命令数をスレッド毎に記録するＩＰＣ（ＩｎｓｔｒｕｃｔｉｏｎＰｅｒＣｙｃｌｅ）カウンタ２１を備える。１サイクルとは、マルチスレッディングプロセッサの内部周波数の逆数で（示される単位時間で）ある。キャッシュメモリ２２は、キャッシュミス回数をスレッド毎に記録するキャッシュミスカウンタ２３と、キャッシュミスの際にメインメモリにアクセスし命令やデータが読み出されるまでの時間を記録するメモリアクセスレーテンシカウンタ２４を有する。
図２は、第１の実施の形態を説明する図である。第１の実施の形態は、同時実行するスレッドのフェッチストール回数からマルチスレッディングプロセッサの動作状態を判断し、同時実行するスレッド数をマルチスレッディングプロセッサの動作状態に応じて動的に変更することで、資源競合による遅延を避ける例である。あらかじめフェッチストール基準値が設定されるものとする。
図２には、コンテキストユニットとそのコンテキストユニットに割り当てられたスレッドＩＤ、そのスレッドのプロセスＩＤおよびスレッドの実行状態が描かれている。図２ａは、プロセスＩＤ０から４スレッド（スレッドＩＤ０〜３）がコンテキストユニット１０〜１３に割り当てられ、４スレッドとも実行されている状態である。
図３のフェッチストール回数による動作状態の判定を行った結果、所定期間のフェッチストール回数がフェッチストール基準値より大きければ、図２ａで４スレッドが同時実行されていた状態から、図２ｂの２スレッドの同時実行状態に遷移する。新たな動作状態の判定によって、フェッチストール回数がフェッチストール基準値より大きければ、図２ｂの２スレッド実行状態から図２ｃの１スレッド実行状態になり、フェッチストール回数がフェッチストール基準値以下であれば、図２ｂの２スレッド実行状態から図２ａの４スレッド同時実行状態に遷移する。このように、図２ａと図２ｂ、図２ｂと図２ｃの間で状態遷移が起こる。
図３は、フェッチストール回数による動作状態判定を説明するフローチャートである。まず所定期間が経過したか判定する（Ｓ３１）。所定期間が経過していなければ、所定期間が経過するまでステップ３１を繰り返す。所定期間が経過していれば、その期間内のフェッチストール回数が設定されたフェッチストール基準値より大きいかを判定する（Ｓ３２）。ステップＳ３２の判定は、例えば、コンテキストユニットに割り当てられたスレッドの所定期間内のフェッチストール回数の合計をフェッチストール基準値と比較すればよい。
ステップＳ３２で、フェッチストール回数がフェッチストール基準値より大きい場合、同時実行するスレッド数を減らす（Ｓ３３）。これは、多数のスレッドを実行することによる資源競合が発生し、処理効率を下げていると考えられるためであり、スレッド数を減少させることで資源競合を回避する。
逆に、ステップＳ３２で、フェッチストール回数がフェッチストール基準値以下であれば、同時実行するスレッドを増やす（Ｓ３４）。これは、使用されていないコンテキストユニットが存在し、さらに現在実行しているスレッドで資源競合が発生していないことから、処理効率を向上させる余地が残されていると考えられるからである。ステップＳ３３、Ｓ３４が終了すると、再び所定の期間が経過まで待ちステップＳ３１からの処理を繰り返す。
第１の実施の形態によれば、フェッチストール回数により、マルチスレッディングプロセッサの動作状態を判定し、それに合わせて同時実行するスレッド数を変更することで資源競合による遅延をさけ、処理性能を向上させることが可能となる。なお、第１の実施の形態は、フェッチストール回数による動作状態判定を行ったが、メモリアクセスレーテンシによる動作状態判定を行うことも可能である。メモリアクセスレーテンシにより判定を行うために、レーテンシ基準値が設定されているものとする。
図４は、メモリアクセスレーテンシによる動作状態判定を説明するフローチャートである。まず所定期間が経過したか判定する（Ｓ４１）。所定期間が経過していなければ、所定期間が経過するまでステップＳ４１を繰り返す。所定期間が経過していれば、その期間内のメモリアクセスレーテンシが設定されたレーテンシ基準値より大きいかを判定する（Ｓ４２）。
ステップＳ４２で、メモリアクセスレーテンシがレーテンシ基準値より大きい場合、同時実行するスレッド数を減らす（Ｓ４３）。これは、多数のスレッドを実行することによる資源競合が発生し、処理効率を下げていると考えられるためであり、スレッド数を減少させることで資源競合を回避する。
逆に、ステップＳ４２で、メモリアクセスレーテンシが基準値以下であれば、同時実行するスレッドを増やす（Ｓ４４）。これは、使用されていないコンテキストユニットが存在し、さらに現在実行しているスレッドで資源競合が発生していないことから、処理効率を向上させる余地が残されていると考えられるからである。ステップＳ４３、Ｓ４４が終了すると、再び所定の期間が経過まで待ちステップＳ４１からの処理を繰り返す。
同様に、キャッシュミスカウンタを使用し、マルチスレッディングプロセッサの動作状態を判定することも可能である。さらに、ＩＰＣカウンタを使用し、マルチスレッディングプロセッサの動作状態を判定することも可能である。この場合は、測定されたＩＰＣ値がＩＰＣ用に設定された基準値より大きい場合スレッド数を増加させ、少ない場合スレッド数を減少させるように選択する点が、図３や図４と異なる。
図５は、第２の実施の形態を説明する図である。第２の実施の形態は、コンテキストスイッチの際にフェッチストール回数の多いスレッドと少ないスレッドを組み合わせて、同時実行するスレッドを動的に選択することで資源競合による遅延を避ける例である。なお、コンテキストスイッチ以外のタイミングにおいて、第１の実施の形態が適用されるものとする。
図５の縦軸は時間経過を表し、横軸は実行対象のスレッドを表す。実線はそのスレッドがコンテキストユニットに割り当てられていることを示し、色付きの部分はそのスレッドが実行されていることを示す。
図５のコンテキストスイッチ５１は、実行対象のスレッドとしてスレッド０〜１１まで１２スレッド存在し、スレッド０〜３の４スレッドが４つのコンテキストユニットに割り当てられている状態を表す。コンテキストスイッチ５１では、最初スレッド０〜３がすべて実行状態にある。図５では、第１の実施の形態が適用され、コンテキストスイッチ５１から５２までの間に同時実行されるスレッド数が動的に変化している。
コンテキストスイッチ５２のタイミングにおいて、フェッチストール回数の上位２つのスレッドと下位２つのスレッドが選択された結果（図６を参照）、スレッド４、５、７、８が４つのコンテキストユニットに割り当てられる。さらに第１の実施の形態が適用された結果、コンテキストスイッチ５２においてまずスレッド４が実行され、その後第１の実施の形態が適用されスレッド数が動的に変化している。
図６は、コンテキストスイッチ５２における各スレッドと対応するフェッチストール回数の例である。第２の実施の形態においては、スレッドごとのフェッチストール回数が累積されて記録されており、上位２つのスレッドとしてスレッド５と８、下位２つのスレッドとしてスレッド４と７が選択される。
同様に、コンテキストスイッチ５３のタイミングにおいて、フェッチストール回数の上位２つのスレッドと下位２つのスレッドが選択された結果、スレッド２、３、７、１０がコンテキストユニットに割り当てられる。さらに第１の実施の形態が適用された結果、コンテキストスイッチ５３において最初スレッド２、３、７、１０の４スレッドが実行され、その後も第１の実施の形態が適用されスレッド数が動的に変化している。
第２の実施の形態によれば、マルチスレッディングプロセッサの動作状態を反映したフェッチストール回数のうち、上位２つと下位２つのスレッドを選択することにより、資源競合による遅延を避け、マルチスレッディングプロセッサの処理効率を向上させることができる。好ましくは、第１の実施の形態と合わせて実施し、動的に同時実行するスレッドを選択することにより更なる性能向上を図ることが可能である。
なお、スレッドの選択法としては、上位１つと下位３つや、上位３つと下位１つとすることも可能である。また、実装されたコンテキストユニットが４つ以外の場合の上位と下位の数の組み合わせは何通りもあるが、明示的に上位のスレッドと下位のスレッドを組み合わせて選択することにより第２の実施の形態が適用可能である。
また、第２の実施の形態は、フェッチストール回数によりスレッドを選択したが、キャッシュミス回数による選択を行うことも可能である。図７は、各スレッドと対応するキャッシュミス回数の例である。図７の例において、例えばキャッシュミス回数の上位２つと下位２つを選択すればスレッド１、２、５、１１が選択される。
同様に、ＩＰＣ値によるスレッド選択を行うことも可能である。図８は、各スレッドと対応するＩＰＣ値の例である。図８の例において、例えばＩＰＣ値の上位２つと下位２つを選択すれば、スレッド２、３、８、１０が選択される。
図９は、第３の実施の形態を説明する図である。第３の実施の形態は、フェッチの際またはコンテキストスイッチにおいて、同一プロセスのスレッドを実行スレッドとして優先的に選択することによって、資源競合による遅延を避ける例である。同一プロセスのスレッドは同一のメモリ空間を共有し動作するため、別メモリ空間で動作する異なるプロセスのスレッドを選択するよりキャッシュミスの増加（キャッシュ競合）が少なく、キャッシュメモリより低速なメインメモリにアクセスすることによる遅延が避けられる。
図９ａは、プロセス０からの４スレッド（スレッド０〜３）が優先的にコンテキストユニットに割り当てられ、４スレッドとも実行される状態を示している。図９ｂは、コンテキストに割り当てられたプロセス０のスレッド０と３、プロセス４のスレッド４と５のうちプロセス４からの２スレッド（スレッド４と５）が実行される状態を示している。
第３の実施の形態によれば、別メモリ空間で動作する異なるプロセスのスレッドを選択するのではなく、同一のメモリ空間を共有し動作する同一プロセスのスレッドを優先的に選択するため、複数スレッド間で悪影響を及ぼすことなく、資源競合による遅延を避け、マルチスレッディングプロセッサの処理効率を向上させることが可能である。好ましくは、第１または第２の実施の形態と組み合わせて実施し、より処理効率のよいスレッドを選択することが望ましい。
図１０は、第４の実施の形態を説明する図である。第４の実施の形態は、条件を変えて動作状態を測定するサンプリングフェーズとサンプリングフェーズで測定された動作状態で最も処理効率のよい条件で実行スレッドを選択する実行フェーズに分けてスレッドを実行することで、資源競合による遅延を避ける例である。
まずサンプリングフェーズ１０２では、例えば、図２ａの４スレッド（スレッド０〜３）を実行する。次に図２ｂの２スレッドとしてスレッド０、１とスレッド２、３の２通りを実行する。そして、図２ｃの１スレッドとしてスレッド０、スレッド１、スレッド２、スレッド３の４通りを実行する。なお、サンプリングフェーズにて実行されるスレッドの組み合わせは、上記以外にも存在し、例えば、２スレッド実行時にスレッド０、２の組を追加することも可能である。
この様にして各スレッドの統計情報を収集し、最適なスレッド数を決定する。最適なスレッドを選択するための統計情報としては、例えば、スレッドあたりのフェッチストール回数を使用することができる。実行フェーズ１０３では、サンプリングフェーズ１０２で決定された最適な組み合わせのスレッドを実行する。
第４の実施の形態によれば、様々な組み合わせの動作状態を実際に測定してから最適な組み合わせを決定するため、資源競合による遅延を避け、マルチスレッディングプロセッサの処理効率を向上させることが可能である。
なお、第４の実施の形態において動作状態の判定にフェッチストール回数を用いたが、ＩＰＣ値、キャッシュミス回数、メモリアクセスレーテンシなどを使用することも可能である。さらに、最適な組み合わせの決定方法としては、あるスレッドに注目し、そのスレッドの処理効率が最も高くなる条件で選択する方法を適用することも可能である。
また、本発明の実施の形態において実施される方法を各ユニットが機能として実現することも可能である。一例を挙げれば、図３の判定をフェッチユニット１７で実施することが可能である。
【産業上の利用の可能性】
以上説明したように本発明によれば、マルチスレッディングプロセッサの動作状態を計測することによって同時実行するスレッド数や組み合わせを動的に選択し、資源競合による遅延を避けるスケジューリングを行うことで、マルチスレッディングプロセッサの処理効率を向上させることができる。
【図１】
2004044745.tif 000003
2004044745.tif 000004
【図３】
2004044745.tif 000005
【図４】
2004044745.tif 000006
【図５】
2004044745.tif 000007
【図６】
2004044745.tif 000008
【図７】
2004044745.tif 000009
【図８】
2004044745.tif 000010
2004044745.tif 000011
【図１０】
2004044745.tif 000012
【国際調査報告】
2004044745.tif 000013
2004044745.tif 000014
2004044745.tif 000015
2004044745.tif 000016