(57)【特許請求の範囲】
【請求項１】
複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおいて、
前記プロセッサエレメントのそれぞれは、レジスタ集合、演算ユニット及び制御ユニットに加えて、クロック毎に値が減じられていくカウンタと、該カウンタの値がゼロになった場合に割り込み要求信号を発生するゼロ比較器と、ユーザプロセス内のスレッドスケジューラの置かれているメモリアドレスを保持するユーザハンドラレジスタと、プログラムカウンタの値の退避先レジスタであるユーザ退避ＰＣとを含んで構成され、
前記プロセッサは、前記ゼロ比較器から前記割り込み要求信号が発生したプロセッサエレメントにてユーザレベル割り込み処理を開始し、プログラムカウンタの値を前記ユーザ退避ＰＣに設定すると共に前記ユーザハンドラレジスタの値を前記プログラムカウンタに設定する割り込み制御部と、プロセッサエレメント間で排他的に値の操作が行なえる計算機命令セットによって各プロセッサエレメントからアクセス可能な１ビットの記憶装置の集合とを含んで構成され、
前記ユーザプロセス内のスレッドスケジューラは、次に実行すべきスレッドが割り当てられるプロセッサエレメント内の前記カウンタに当該次に実行すべきスレッドに割り当てるタイムクォンタム値を設定すると共に前記ユーザハンドラレジスタに自スレッドスケジューラの置かれているメモリアドレスを設定して、前記プロセッサエレメントに当該次に実行すべきスレッドの実行を開始させるものであり、
複数のプロセッサエレメントで実行される複数のスレッド間の排他制御は、前記１ビットの記憶装置の集合を用いて行なうものであることを特徴とするマルチスレッド計算機システム。
【請求項２】
複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおいて、
前記プロセッサエレメントのそれぞれは、レジスタ集合、演算ユニット及び制御ユニットに加えて、クロック毎に値が減じられていくカウンタと、該カウンタの値がゼロになった場合に割り込み要求信号を発生するゼロ比較器と、ユーザプロセス内のスレッドスケジューラの置かれているメモリアドレスを保持するユーザハンドラレジスタと、プログラムカウンタの値の退避先レジスタであるユーザ退避ＰＣとを含んで構成され、
前記プロセッサは、前記ゼロ比較器から前記割り込み要求信号が発生したプロセッサエレメントにてユーザレベル割り込み処理を開始し、プログラムカウンタの値を前記ユーザ退避ＰＣに設定すると共に前記ユーザハンドラレジスタの値を前記プログラムカウンタに設定する割り込み制御部と、プロセッサエレメントに対応した識別番号をもつトークンを到着順に格納するキュー構造の集合であって、プロセッサエレメント間で排他的にトークンの追加、検索あるいは削除が行なえる計算機命令セットによって各プロセッサエレメントからアクセスできるキュー構造の集合とを含んで構成され、
前記ユーザプロセス内のスレッドスケジューラは、次に実行すべきスレッドが割り当てられるプロセッサエレメント内の前記カウンタに当該次に実行すべきスレッドに割り当てるタイムクォンタム値を設定すると共に前記ユーザハンドラレジスタに自スレッドスケジューラの置かれているメモリアドレスを設定して、前記プロセッサエレメントに当該次に実行すべきスレッドの実行を開始させるものであり、
複数のプロセッサエレメントで実行される複数のスレッド間の排他制御は、前記キュー構造の集合を用いて行なうものであることを特徴とするマルチスレッド計算機システム。
【請求項３】
複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおけるマルチスレッド実行制御方法において、
（ａ）ユーザプロセスのスレッドが割り当てられるプロセッサエレメント内のユーザハンドラレジスタにそのユーザプロセスのスレッドスケジューラの置かれているメモリアドレスを設定すると共に、そのプロセッサエレメント内のカウンタにそのスレッドに割り当てるタイムクォンタム値を設定して、そのプロセッサエレメントでそのスレッドの実行を開始させ、実行を開始させたスレッドと他のスレッドとの間の排他制御は、プロセッサ内に設けられ且つプロセッサエレメント間で排他的に値の操作が行なえる計算機命令セットによって各プロセッサエレメントからアクセス可能な１ビットの記憶装置の集合を用いて行なわせる段階
（ｂ）プロセッサエレメントにおけるスレッドの実行開始と同時にそのプロセッサエレメント内の前記カウンタの値を一定周期で更新し、予め定められたカウント値に達した時点でユーザレベル割り込みを発生させる段階
（ｃ）ユーザレベル割り込みの処理において、割り込み要求元のプロセッサエレメントの現在のプログラムカウンタの値をそのプロセッサエレメント内のユーザ退避ＰＣに設定し、そのプロセッサエレメント内のユーザハンドラレジスタに設定されたメモリアドレスをプログラムカウンタに設定することにより制御をユーザプロセス内のスレッドスケジューラに移す段階
を含むことを特徴とするマルチスレッド実行制御方法。
【請求項４】
複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおけるマルチスレッド実行制御方法において、
（ａ）ユーザプロセスのスレッドが割り当てられるプロセッサエレメント内のユーザハンドラレジスタにそのユーザプロセスのスレッドスケジューラの置かれているメモリアドレスを設定すると共に、そのプロセッサエレメント内のカウンタにそのスレッドに割り当てるタイムクォンタム値を設定して、そのプロセッサエレメントでそのスレッドの実行を開始させ、実行を開始させたスレッドと他のスレッドとの間の排他制御は、プロセッサエレメントに対応した識別番号をもつトークンを到着順に格納するプロセッサ内のキュー構造の集合であって、プロセッサエレメント間で排他的にトークンの追加、検索あるいは削除が行なえる計算機命令セットによって各プロセッサエレメントからアクセスできるキュー構造の集合を用いて行なわせる段階
（ｂ）プロセッサエレメントにおけるスレッドの実行開始と同時にそのプロセッサエレメント内の前記カウンタの値を一定周期で更新し、予め定められたカウント値に達した時点でユーザレベル割り込みを発生させる段階
（ｃ）ユーザレベル割り込みの処理において、割り込み要求元のプロセッサエレメントの現在のプログラムカウンタの値をそのプロセッサエレメント内のユーザ退避ＰＣに設定し、そのプロセッサエレメント内のユーザハンドラレジスタに設定されたメモリアドレスをプログラムカウンタに設定することにより制御をユーザプロセス内のスレッドスケジューラに移す段階
を含むことを特徴とするマルチスレッド実行制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は並列計算機システムに関し、特に、共有メモリ型マルチプロセッサ計算機上で、オペレーティングシステムを介することなく複数スレッドを効率的にスケジューリングするマルチスレッド計算機システムに関する。
【０００２】
【従来の技術】
より高い演算処理性能を得るために、一つのシステム内に複数のプロセッサエレメントを備えるマルチプロセッサ構成の計算機システムがある。そのような計算機システムのうち、各プロセッサエレメントが主記憶メモリを共有する構成のものは共有メモリ型マルチプロセッサ計算機システムと呼ばれ、分散メモリ型システムに比べプログラムの記述が容易であるという利点を持つ。
【０００３】
他方、ソフトウェア面では、一つのプロセスをスレッドと呼ばれる制御の流れに分割し、複数のスレッドを並行して実行する、マルチスレッド実行と呼ばれる並列実行方式がある。マルチプロセッサ計算機システム上では、複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行させることで処理性能が向上する。
【０００４】
マルチプロセッサ計算機システムにおけるスレッドの管理は、通常、マルチプロセッサ用オペレーティングシステムが行なう。すなわち、新しいスレッドの生成、別のスレッドとの同期、スレッドの消滅等を行なう場合、当該スレッドはオペレーティングシステムのサービスを呼び出す。
【０００５】
スレッドのプリエンプションもオペレーティングシステムを介して行なわれる。プリエンプションとは、長時間プロセッサを占有し続けるスレッドの実行を中断させ、他のスレッドの実行に切り替える処理である。プリエンプション機能をもつ計算機システムは、ハードウェアタイマ装置と、所定の時間が経過するとタイマ装置からプロセッサに割り込み信号を伝える仕組みを持っている。ユーザプログラムの実行を開始してから一定の時間が経過すると、タイマ割り込みによってオペレーティングシステムに制御が移り、オペレーティングシステムが実行スレッドの切り替えを行なう。
【０００６】
マルチプロセッサ計算機システム上で複数のスレッドを効率良く実行するには、スレッドの生成、同期、切り替え、消滅といったスレッド管理のオーバーヘッドを低減させることが重要である。
【０００７】
サン・マイクロシステムズのソラリス（Ｓｏｌａｒｉｓ）  オペレーティングシステムでは、オペレーティングシステムではなく、ユーザレベルのライブラリによってスレッドの管理を行なうことができる。これにより、より低いオーバーヘッドでスレッド管理ができるが、プリエンプションの場合にはオペレーティングシステムが介在する（マルチスレッドプログラミング入門、アスキー出版局、１９９６年９月、ｐ６９  〜ｐ７０  およびｐ７６  〜ｐ７７）。
【０００８】
特開平５−１５８９００号公報に記載されているプリエンプション処理回路は、オペレーティングシステムではなく、専用ハードウェアによってプリエンプションの受け付けを行なうものであるが、受け付け後の切り替え処理はオペレーティングシステムへの通常の割り込みによって行なっている。
【０００９】
他方、複数のスレッドによって共有される計算機資源、例えば主記憶メモリ上の共有変数を読み書きする場合には、複数のスレッドがその計算機資源を同時にアクセスすることで誤った処理結果を得ることを回避するために、排他制御と呼ばれる処理を行なう必要がある（排他制御については、例えば、Ａ．Ｓ．タネンバウム原著「ＯＳの基礎と応用」プレンティスホール・トッパン、第２章  ２．２節等に説明されている）。
【００１０】
排他制御は通常、テストアンドセットやエクスチェンジといった排他制御用のプロセッサ命令によって実現される。これらの命令は、主記憶上のあるメモリセルの値の検査とそのメモリセルへの新しい値の設定とを不可分に行なう。例えば、テストアンドセット命令は、以下の３つの操作を、割り込みあるいは他のプロセッサによって分断されること無く行なう。
（１）主記憶上のあるメモリセルの値の計算機レジスタへの読み出し
（２）そのメモリセルへの値１の書き込み
（３）計算機レジスタへ読み出した値と値０との比較
【００１１】
共有メモリ型マルチプロセッサ計算機システムでは、異なるプロセッサ間の排他制御を行なうため、これらの排他制御用命令は共有している主記憶メモリに対して作用する。すなわち、排他制御自身のために主記憶メモリへのアクセスが必要になる。
【００１２】
【発明が解決しようとする課題】
従来技術の第１の問題点は、マルチスレッド実行のために十分高速な割り込み応答処理ができず、スレッド切り替えのオーバーヘッドが大きかった点である。これは、割り込み処理がオペレーティングシステム内で処理されるため、ユーザプログラムからオペレーティングシステムへのコンテキストの切り替えが発生するからである。
【００１３】
第２の問題点は、排他制御処理自身のために主記憶メモリへのアクセスが発生し、マルチスレッド処理に不可欠なスレッド間の排他制御や同期処理のオーバーヘッドが大きかった点である。近年のプロセッサの処理速度は主記憶メモリのアクセス速度よりも格段に速いため、多くのプロセッサはキャッシュメモリと呼ばれる高速で小容量のメモリをプロセッサと主記憶メモリの間に備え、プロセッサは専らキャッシュメモリをアクセスすることでメモリアクセスによる処理の遅延を回避している。しかし、排他制御命令は常に主記憶メモリへのアクセスを行なうため、処理速度の低下を招く。
【００１４】
上に挙げた問題点はいずれもマルチスレッド処理のオーバーヘッドを増大させる原因となり、特に、粒度の小さいスレッド（含有する命令数の少ないスレッド）を単位としてマルチスレッド処理を行なう場合に大きな影響をもたらす。
【００１５】
【発明の目的】
本発明の目的は、オペレーティングシステムが介在しない高速なユーザレベル割り込みを提供し、マルチスレッド処理の効率を向上させることである。
【００１６】
本発明の他の目的は、マルチプロセッサ計算機システムにおけるプロセッサエレメント間の高速なロック機構を提供し、マルチスレッド処理の効率を向上させることである。
【００１７】
【課題を解決するための手段】
本発明の第１のマルチスレッド計算機システムは、複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおいて、
前記プロセッサエレメントのそれぞれは、レジスタ集合、演算ユニット及び制御ユニットに加えて、クロック毎に値が減じられていくカウンタと、該カウンタの値がゼロになった場合に割り込み要求信号を発生するゼロ比較器と、ユーザプロセス内のスレッドスケジューラの置かれているメモリアドレスを保持するユーザハンドラレジスタと、プログラムカウンタの値の退避先レジスタであるユーザ退避ＰＣとを含んで構成され、
前記プロセッサは、前記ゼロ比較器から前記割り込み要求信号が発生したプロセッサエレメントにてユーザレベル割り込み処理を開始し、プログラムカウンタの値を前記ユーザ退避ＰＣに設定すると共に前記ユーザハンドラレジスタの値を前記プログラムカウンタに設定する割り込み制御部と、プロセッサエレメント間で排他的に値の操作が行なえる計算機命令セットによって各プロセッサエレメントからアクセス可能な１ビットの記憶装置の集合とを含んで構成され、
前記ユーザプロセス内のスレッドスケジューラは、次に実行すべきスレッドが割り当てられるプロセッサエレメント内の前記カウンタに当該次に実行すべきスレッドに割り当てるタイムクォンタム値を設定すると共に前記ユーザハンドラレジスタに自スレッドスケジューラの置かれているメモリアドレスを設定して、前記プロセッサエレメントに当該次に実行すべきスレッドの実行を開始させるものであり、
複数のプロセッサエレメントで実行される複数のスレッド間の排他制御は、前記１ビットの記憶装置の集合を用いて行なうものである。
【００１８】
また、本発明の第２のマルチスレッド計算機システムは、複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおいて、
前記プロセッサエレメントのそれぞれは、レジスタ集合、演算ユニット及び制御ユニットに加えて、クロック毎に値が減じられていくカウンタと、該カウンタの値がゼロになった場合に割り込み要求信号を発生するゼロ比較器と、ユーザプロセス内のスレッドスケジューラの置かれているメモリアドレスを保持するユーザハンドラレジスタと、プログラムカウンタの値の退避先レジスタであるユーザ退避ＰＣとを含んで構成され、
前記プロセッサは、前記ゼロ比較器から前記割り込み要求信号が発生したプロセッサエレメントにてユーザレベル割り込み処理を開始し、プログラムカウンタの値を前記ユーザ退避ＰＣに設定すると共に前記ユーザハンドラレジスタの値を前記プログラムカウンタに設定する割り込み制御部と、プロセッサエレメントに対応した識別番号をもつトークンを到着順に格納するキュー構造の集合であって、プロセッサエレメント間で排他的にトークンの追加、検索あるいは削除が行なえる計算機命令セットによって各プロセッサエレメントからアクセスできるキュー構造の集合とを含んで構成され、
前記ユーザプロセス内のスレッドスケジューラは、次に実行すべきスレッドが割り当てられるプロセッサエレメント内の前記カウンタに当該次に実行すべきスレッドに割り当てるタイムクォンタム値を設定すると共に前記ユーザハンドラレジスタに自スレッドスケジューラの置かれているメモリアドレスを設定して、前記プロセッサエレメントに当該次に実行すべきスレッドの実行を開始させるものであり、
複数のプロセッサエレメントで実行される複数のスレッド間の排他制御は、前記キュー構造の集合を用いて行なうものである。
【００１９】
また本発明の第１のマルチスレッド実行制御方法は、複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおけるマルチスレッド実行制御方法において、オペレーティングシステムが介在しない高速なユーザレベル割り込みを提供するために、
（ａ）ユーザプロセスのスレッドが割り当てられるプロセッサエレメント内のユーザハンドラレジスタにそのユーザプロセスのスレッドスケジューラの置かれているメモリアドレスを設定すると共に、そのプロセッサエレメント内のカウンタにそのスレッドに割り当てるタイムクォンタム値を設定して、そのプロセッサエレメントでそのスレッドの実行を開始させ、実行を開始させたスレッドと他のスレッドとの間の排他制御は、プロセッサ内に設けられ且つプロセッサエレメント間で排他的に値の操作が行なえる計算機命令セットによって各プロセッサエレメントからアクセス可能な１ビットの記憶装置の集合を用いて行なわせる段階
（ｂ）プロセッサエレメントにおけるスレッドの実行開始と同時にそのプロセッサエレメント内の前記カウンタの値を一定周期で更新し、予め定められたカウント値に達した時点でユーザレベル割り込みを発生させる段階
（ｃ）ユーザレベル割り込みの処理において、割り込み要求元のプロセッサエレメントの現在のプログラムカウンタの値をそのプロセッサエレメント内のユーザ退避ＰＣに設定し、そのプロセッサエレメント内のユーザハンドラレジスタに設定されたメモリアドレスをプログラムカウンタに設定することにより制御をユーザプロセス内のスレッドスケジューラに移す段階
を含むことを特徴とする。
【００２０】
また、本発明の第２のマルチスレッド実行制御方法は、複数のプロセッサエレメントを含むプロセッサと前記複数のプロセッサエレメントで共有される主記憶メモリとを備え、一つのユーザプロセスを粒度の小さい複数のスレッドに分割し、そのユーザプロセス内のスレッドスケジューラの制御の下に複数のスレッドを複数のプロセッサエレメントに割り当てて同時に実行するマルチスレッド計算機システムにおけるマルチスレッド実行制御方法において、オペレーティングシステムが介在しない高速なユーザレベル割り込みを提供するために、
（ａ）ユーザプロセスのスレッドが割り当てられるプロセッサエレメント内のユーザハンドラレジスタにそのユーザプロセスのスレッドスケジューラの置かれているメモリアドレスを設定すると共に、そのプロセッサエレメント内のカウンタにそのスレッドに割り当てるタイムクォンタム値を設定して、そのプロセッサエレメントでそのスレッドの実行を開始させ、実行を開始させたスレッドと他のスレッドとの間の排他制御は、プロセッサエレメントに対応した識別番号をもつトークンを到着順に格納するプロセッサ内のキュー構造の集合であって、プロセッサエレメント間で排他的にトークンの追加、検索あるいは削除が行なえる計算機命令セットによって各プロセッサエレメントからアクセスできるキュー構造の集合を用いて行なわせる段階
（ｂ）プロセッサエレメントにおけるスレッドの実行開始と同時にそのプロセッサエレメント内の前記カウンタの値を一定周期で更新し、予め定められたカウント値に達した時点でユーザレベル割り込みを発生させる段階
（ｃ）ユーザレベル割り込みの処理において、割り込み要求元のプロセッサエレメントの現在のプログラムカウンタの値をそのプロセッサエレメント内のユーザ退避ＰＣに設定し、そのプロセッサエレメント内のユーザハンドラレジスタに設定されたメモリアドレスをプログラムカウンタに設定することにより制御をユーザプロセス内のスレッドスケジューラに移す段階
を含むことを特徴とする。
【００２１】
【作用】
カウンタがゼロになると割り込み制御部はユーザレベル割り込み処理を開始する。ユーザレベル割り込み処理では、予めユーザプロセスのスレッドスケジューラの開始アドレスに設定しておいたユーザハンドラレジスタの値をプログラムカウンタに設定し、オペレーティングシステムを経由すること無くスレッドスケジューラに制御を移行する。
【００２２】
複数のプロセッサエレメントで実行される複数のスレッド間の排他制御は、プロセッサ内に設けられた１ビットの記憶装置の集合またはキュー構造の集合を用いて行なわれ、主記憶メモリへアクセスする必要のないロック獲得及び解放機能を提供する。
【００２３】
【発明の実施の形態】
【構成の説明】
本発明の実施の形態について、図面を参照して詳細に説明する。
【００２４】
図１は、本発明が実施される計算機構成の一例を示す図である。プロセッサ１は内部に複数のプロセッサエレメント１１、１２及び１９を持ち、それらのプロセッサエレメントは共通の主記憶メモリ２に対してアクセスする。
【００２５】
図２を参照すると、本発明の第１の実施の形態は、内部に複数のプロセッサエレメントを有するプロセッサ１と、そのプロセッサ上で動作するオペレーティングシステム５０と、そのオペレーティングシステム上で動作するユーザプロセス１００とから構成される。
【００２６】
プロセッサ１内の各プロセッサエレメントは、一般的な計算機のプロセッサが持つレジスタ集合や演算ユニット、制御ユニット等の他に、ユーザレベルのプリエンプション割り込みを発生させるためのカウンタ２６とゼロ比較器２５、ユーザレベル割り込み発生時の制御移動に使用されるユーザハンドラレジスタ２０、ユーザ退避ＰＣ２３を備えている。
【００２７】
カウンタ２６の値は、クロック信号によってクロック毎に減算される。ゼロ比較器２５は、カウンタ２６の値とゼロとを比較する。ユーザハンドラレジスタ２０はユーザレベル割り込み発生時に実行制御を移すべきプログラムカウンタ値を保持しているレジスタであり、ユーザ退避ＰＣ２３はユーザレベル割り込みの発生直前のプログラムカウンタ値を退避しておくためのレジスタである。
【００２８】
図２のプログラムカウンタ（ＰＣ）２２及び割り込み制御部４１は一般的な計算機のプロセッサが持つプログラムカウンタ及び割り込み制御部と同等の機能を有するものであり、カーネルハンドラレジスタ２１及びカーネル退避ＰＣ２４は一般的な計算機のプロセッサにおける通常の割り込み発生時に用いられる割り込みハンドラレジスタ及びプログラムカウンタ退避用レジスタと同等の機能を有するものである。
【００２９】
ユーザプロセス１００はオペレーティングシステム５０により生成される実行プログラムの実体である。ユーザプロセス１００は主記憶メモリ空間を共有する複数のスレッド１０２、１０３及び１０４から構成され、これらのスレッドがプロセッサエレメントに割り当てられ、実行される。スレッドスケジューラ１０１はユーザプログラムとリンクされた形でユーザプロセス１００の内部に存在し、当該ユーザプロセスを構成する全スレッドの管理を行なう。
【００３０】
また、プロセッサ内には全プロセッサエレメントで共有されるロック変数セット３０とアクセス調停機構４０がある。ロック変数セット３０は１ビットの状態を記憶できるロック変数の集合であり、アクセス調停機構４０はロック変数へのアクセスをプロセッサエレメント間で調停する機構である。
【００３１】
【動作の説明】
図２を参照して、本実施の形態の動作について詳細に説明する。
【００３２】
オペレーティングシステム５０がユーザプロセス１００を開始させると、ユーザプロセス１００はその内部に組み込んだスレッドスケジューラ１０１を呼び出す。スレッドスケジューラ１０１は、ある決まったスケジューリングアルゴリズムに従って当該ユーザプロセス１００内のスレッドの集合をスケジューリングする。スレッドスケジューラ１０１が次に実行すべきスレッド（ここではスレッド１０２とする）を選択すると、スレッドスケジューラ１０１はスレッド１０２に割り当てるタイムクォンタム値をスレッド１０２が割り当てられるプロセッサエレメント１１のカウンタ２６に設定し、スレッドスケジューラ１０１の置かれているメモリアドレスを当該プロセッサエレメント１１のユーザハンドラレジスタ２０に設定した後、当該プロセッサエレメント１１でスレッド１０２の実行を開始させる。
【００３３】
スレッド１０２が実行されるのと並行して、カウンタ２６の値がクロック信号によって一定時間毎に減じられてゆく。その値がゼロになると、ゼロ比較器２５が割り込み制御部４１に割り込み要求信号を送る。割り込み制御部４１は当該プロセッサエレメント１１にてユーザレベル割り込みの処理を開始する。
【００３４】
ユーザレベル割り込み処理が開始すると、プロセッサエレメント１１は現在のプログラムカウンタ２２の値をユーザ退避ＰＣ２３に設定し、ユーザハンドラレジスタ２０の値をプログラムカウンタ２２に設定する。これにより、オペレーティングシステム５０を介することなく、ユーザプロセス１００の内部にあるスレッドスケジューラ１０１に速やかに制御が移行する。スレッドスケジューラ１０１は、レジスタセットの値をはじめとするスレッド１０２の実行状態をスレッドスケジューラ１０１の内部の管理データ領域に保存し、定められたスケジューリングアルゴリズムに従って次に実行開始すべきスレッドを選択し、次スレッドのレジスタセットの値を復元すると共に、カウンタ２６にそのスレッドに対応するタイムクォンタム値を設定して次スレッドの実行を開始する。
【００３５】
これに対して、従来の割り込み処理を用いる場合を以下に説明する。まず、割り込み処理開始時にユーザプログラムからオペレーティングシステムにコンテキストを切り替える。このコンテキスト切り替えには、
○現在のプログラムカウンタ２２の値のカーネル退避ＰＣ２４への設定
○カーネルハンドラレジスタ２１の値のプログラムカウンタ２２への設定
○プロセッサの動作モードのカーネルモードへの切り替え
○必要なレジスタセットの内容の主記憶メモリへの退避
といった処理が含まれる。このコンテキスト切り替えによって制御はオペレーティングシステム５０内部のカーネルレベル割り込みハンドラ５１、次いでプロセススケジューラ５２に移行する。プロセススケジューラ５２は割り込み要因を分析し、あらかじめ定められたスケジューリングアルゴリズムに従って次に実行すべきプロセスを決定する。そして、再度コンテキスト切り替えを行なって次プロセスの実行を開始する。このコンテキスト切り替えには、
○次プロセスのためのレジスタセットの設定
○次プロセス用論理アドレス空間の設定
○プロセッサの動作モードのユーザモードへの切り替え処理
が含まれる。これら一連の処理を終えて、ようやく制御がユーザプロセスに移行する。
【００３６】
つまり、ユーザレベル割り込み機構の導入により、オペレーティングシステムを経由することによるオーバーヘッドの無い、従来より高速なプリエンプション機構をユーザプログラムで利用することが可能になる。
【００３７】
なお、ユーザレベル割り込み機構の割り込み要因は、ダウンカウンタのゼロ一致によるプリエンプション割り込みに限定されるものではない。割り込み制御部さえ対応させれば、例えば、ユーザプロセス内で無効命令割り込みを処理するなどの目的に利用することも可能である。
【００３８】
次に図２を参照してロック変数セット３０を用いた高速ロック機構について説明する。各プロセッサエレメントは、本プロセッサに備わっているテストアンドセット命令を用いてロック変数セット３０の内部にあるロック変数にアクセスする。あるプロセッサエレメント１１がロック変数に対してテストアンドセット命令を用いると、アクセス調停機構４０は他のプロセッサエレメントからロック変数へのアクセスを一時的に禁止し、その間にプロセッサエレメント１１はロック変数の値をゼロと比較してプロセッサエレメント１１内の状態フラグに反映させ、ロック変数に値１を設定する。ソフトウェア側から見ると、本実施例で述べたテストアンドセット命令の動作は、従来のプロセッサが備えているテストアンドセット命令の動作と同様であるが、大きな遅延をもたらす主記憶メモリへのアクセスを伴わないため、従来よりもはるかに少ないオーバーヘッドで変数をロックすることができる。
【００３９】
プロセッサ内に搭載するロック変数の個数は８個、１６個または３２個が適当である。その理由は、ユーザ向けの高機能な排他制御及び同期制御機構はより基本的な排他制御機構を用いて容易に構築可能であり、そのような基本的な排他制御機構が用いるロック変数は少数で済むためと、ロック変数の個数を小さな２の冪乗個とすることでロック変数の番号を指定するための命令フィールド幅を小さくし、命令効率を高めることが可能であるためである。また、ロック変数の個数をレジスタセットの一般的なビット数である３２あるいは６４以内にすることにより、ロック変数セット全体を一つの特殊レジスタとして扱うことが可能になる。これによりロック変数セットをプロセスに対応するコンテキストに含めることが可能になり、プロセス毎に論理的に独立した高速ロック機構を用いることができるようになる。
【００４０】
上に述べたユーザレベル割り込み機構及び高速ロック機構の導入により、従来より細かな単位での並列処理が可能になり、マルチプロセッサ計算機の実効性能を高めると共に、その適用分野を拡大することができる。これが本実施の形態の効果である。
【００４１】
【発明の他の実施の形態】
次に、ユーザレベル割り込み機構の他の実施形態について説明する。
【００４２】
図２において、カウンタ２６の入力はクロック信号となっているが、この信号は計算機システムのクロック信号そのものには限らない。カウンタ２６の入力としてシステムクロック信号を適当な分周器で数分の一に分周したものを用いれば、カウンタ２６を構成するハードウェアのビット数やカウンタ２６に値を設定する計算機命令中のカウンタ値フィールドのビット幅を減らすことができ、ハードウェア及びソフトウェア双方の効率を改善できる。また、システムクロック信号ではなく、当該プロセッサエレメントの命令実行制御機構の信号をカウンタ２６に入力し、１命令実行する毎にカウンタ２６が減じられるようにする方式にしてもよい。
【００４３】
次に、高速ロック機構の他の実施形態について説明する。
【００４４】
図３を参照すると、高速ロック機構の第２の実施の形態は、各ロック変数がキュー構造になっているものである。各キュー６１、６２及び６９には、プロセッサエレメント数に等しい個数までのトークンを格納することができる。トークンは各プロセッサエレメントが発行するもので、トークンには発行したプロセッサエレメントの番号が付される。キューに一つ以上のトークンがある場合、当該キューの先頭にあるトークンを発行したプロセッサエレメントがそのキューに対応するロック変数をロックしていることを意味する。このロック変数を操作するために、ロック試行命令とロック解除命令の２種の計算機命令が備わっている。プロセッサエレメント１１、１２、…、１９とキュー６１、６２、…、６９との間に設けられたキュー制御機構６０は、ロック試行命令、ロック解除命令の実行時、キュー６１、６２、…、６９に対してプロセッサエレメント間で排他的にトークンの追加、検索、削除の操作を行なう。
【００４５】
プロセッサエレメント１１がロック試行命令を実行すると、キュー制御機構６０は、ロック試行命令のオペランドで指定されたキュー内（ここではキュー６１とする）に当該プロセッサエレメント１１のトークンが存在するか否かを検査し、もしトークンが存在しなければ新たにトークンを投入する。また、キュー制御機構６０は指定されたキュー６１の先頭に当該プロセッサエレメント１１に対応するトークンがあるか否かを調べ、その結果をプロセッサエレメント１１の状態フラグに設定する。ユーザプログラムはロック試行命令に続いて状態フラグを参照する分岐命令を実行することで、ロックを獲得できたか否かを判断する。
【００４６】
プロセッサエレメント１１がロック解除命令を実行すると、キュー制御機構６０は、ロック試行命令のオペランドで指定されたキュー内（ここではキュー６１とする）に当該プロセッサエレメント１１のトークンがあるか否かを検査し、もしあればそのトークンをキュー６１から除去する。
【００４７】
本実施形態は、ロックを要求した順序をキュー内で記憶し先着順にロックを獲得させるという点で、より公平な排他制御機構を実現できる特長を持つ。
【００４９】
【発明の効果】
本発明の第１の効果は、オペレーティングシステムを経ないユーザレベルの割り込み機構を実現できることである。これによりスレッド切り替えのためのオーバーヘッドが小さくなり、従来より小さな粒度でのマルチスレッド実行が可能になる。
【００５０】
本発明の第２の効果は、比較的応答速度の遅い主記憶メモリをアクセスすること無くプロセッサエレメント間の排他制御が実現できることである。これによりスレッド管理やスレッド間の通信にかかわるオーバーヘッドが小さくなり、従来より小さな粒度でのマルチスレッド実行が可能になる。
【００５１】
これらの低オーバーヘッド効果により、共有メモリ型マルチプロセッサ計算機の応用分野が拡大され、大きな粒度での並列性が少ないプログラムに対してもマルチスレッド実行による性能向上が可能になる。
【図面の簡単な説明】
【図１】本発明が実施される計算機の構成例を示す図である。
【図２】本発明の第１の実施の形態を示す図である。
【図３】本発明における高速ロック機構の第２の実施の形態を示す図である。
【符号の説明】
１  プロセッサ
２  主記憶メモリ
１１〜１９  プロセッサエレメント
２０  ユーザハンドラレジスタ
２１  カーネルハンドラレジスタ
２２  プログラムカウンタ
２３  ユーザ退避ＰＣ
２４  カーネル退避ＰＣ
２５  ゼロ比較器
２６  カウンタ
３０  ロック変数セット
４０  アクセス調停機構
４１  割り込み制御部
５０  オペレーティングシステム
５１  カーネルレベル割り込みハンドラ
５２  プロセススケジューラ
６０  キュー制御機構
６１〜６９  キュー
１００  ユーザプロセス
１０１  スレッドスケジューラ
１０２〜１０４  スレッド
【図１】
0003546694.tif 000002
【図２】
0003546694.tif 000003
【図３】
0003546694.tif 000004