(57)【特許請求の範囲】
【請求項１】
各々が、排他制御を実行する前にロックを獲得するために読出信号をアサートし、かつ排他制御を実行した後にロックを解放するために書込信号をアサートする複数のプロセッサと、
前記複数のプロセッサに接続された１のロックレジスタと、
１又は２以上の第２のロック変数を記憶するメモリとを備え、
前記ロックレジスタは、
ロック状態又は非ロック状態の第１のロック変数を保持する保持手段と、
前記プロセッサの１つがアサートした読出信号を受信すると、それ以前に前記保持手段に保持されていた第１のロック変数を出力するロック変数出力手段と、
前記プロセッサの１つがアサートした読出信号を受信すると、前記読出信号を用いてロック状態の第１のロック変数を生成して前記保持手段に設定し、前記プロセッサの１つがアサートした書込信号を受信すると、非ロック状態の第１のロック変数を前記保持手段に設定するロック変数入力手段とを含み、
前記プロセッサの各々は、読出信号をアサートして前記ロックレジスタから第１のロック変数を読み出し、読み出した第１のロック変数が非ロック状態の場合にのみ前記メモリから第２のロック変数を読み出し可能であり、読み出した第２のロック変数が非ロック状態の場合に第２のロック変数をロック状態に書き換えることを特徴とするマルチプロセッサシステム。
【請求項２】
請求項１に記載のマルチプロセッサシステムであって、
前記ロックレジスタはさらに、
前記第１のロック変数がロック状態に設定されている間に前記プロセッサの１つがアサートした読出信号を受信すると、前記プロセッサに供給するためのバスリトライ信号を発生するバスリトライ手段を含むことを特徴とするマルチプロセッサシステム。
【請求項３】
請求項１または２に記載のマルチプロセッサシステムであってさらに、
前記複数のプロセッサに共通に接続された第１のバスと、
前記第１のバスに接続されたメモリと、
前記複数のプロセッサに共通に接続され、かつ前記ロックレジスタに接続された第２のバスとを備え、
前記複数のプロセッサは、前記第２のバスを介して前記ロックレジスタから第１のロック変数を読み出し、
前記ロックレジスタから非ロック状態の第１のロック変数を読み出したプロセッサは、前記第１のバスを介して前記メモリから前記第２のロック変数を読み出すことを特徴とするマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
［０００１］
本発明は、マルチプロセッサシステムに関し、さらに詳しくは、排他制御を実行する前にロックを獲得し、排他制御を実行した後にロックを解放するマルチプロセッサシステムに関する。
【背景技術】
［０００２］
従来、マルチスレッドプログラミングの実行環境として、ＭＥＳＩ（Ｍｏｄｉｆｉｅｄ  Ｅｘｃｌｕｓｉｖｅ  Ｓｈａｒｅｄ  Ｉｎｖａｌｉｄ）のようなキャッシュコヒーレンシプロトコルと、不可分（アトミック）転送をサポートするバスとが必要である。しかし、これらを実装したＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）及びバスは高価である。
［０００３］
今日、安価なＣＰＵであっても、Ｌｉｎｕｘサポートの必要性からＴＬＢ（Ｔｒａｎｓｌａｔｉｏｎ  Ｌｏｏｋ−ａｓｉｄｅ  Ｂｕｆｆｅｒ）を持っている。このようなＣＰＵを用いた場合、アトミック転送をサポートするバスさえ実装すれば、マルチプロセッサシステムを構築することができる。この場合、バススヌープのハードウェアサポートがなくても、ＮＵＭＡ（Ｎｏｎ−Ｕｎｉｆｏｒｍ  Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ）と同じＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）を利用すれば、ＴＬＢのサポートを使ってキャッシュコヒーレンシを維持することは可能である。
［０００４］
ここで、アトミック転送をサポートするバスが必要なのは、ＣＰＵ間の排他制御を可能にするためである。たとえば各ＣＰＵのＴＬＢを排他的に書き換えるためには、ロック変数をアトミックにリードモディファイライトする必要がある。しかし、ユニプロセッサを意図して設計された安価な組み込みプロセッサ及びそのバス規約は、アトミックリードモディファイライトをサポートしていない。
［０００５］
以下、アトミックリードモディファイライトの必要性を図５を参照して説明する。ここでは、ロック変数ｌｏｃｋをメモリ上にアロケートしている。
［０００６］
まずＣＰＵはメモリからロック変数ｌｏｃｋを読み出し（Ｓ１）、ｌｏｃｋ＝１か否かを判断する（Ｓ２）。ｌｏｃｋ＝１、つまりロック変数がロック状態になっている限り（Ｓ２でＹＥＳ）、ＣＰＵは繰り返しロック変数ｌｏｃｋを読み出す（Ｓ１）。一方、ｌｏｃｋ＝０、つまりロック変数が非ロック状態の場合（Ｓ２でＮＯ）、ＣＰＵはｌｏｃｋ＝１に書き換え、これにより排他制御に必要なロックを獲得する（Ｓ３）。ロックを獲得した後、ＣＰＵは所定の排他制御を実行する（Ｓ４）。排他制御を完了した後、ＣＰＵはｌｏｃｋ＝０に書き換え、これによりロックを解放する（Ｓ５）。
【０００７】
しかし、ｌｏｃｋ＝０を読み出してからｌｏｃｋ＝１に書き換えるまでの間に、他のＣＰＵがｌｏｃｋ＝０を読み出すと、ロックを獲得できると誤認する可能性がある。これを防止するためには、上述したロック変数の読出動作Ｓ１と書込動作Ｓ３とをアトミックに実行しなければならない。
【０００８】
また、上述したアトミックリードモディファイライトをＣＰＵに実行させるためのプログラムは、アトミック転送に必要な専用命令を使うため、Ｃのような高級言語ではなく、アセンブリ言語で記述しなければならない。
【０００９】
米国特許第５１７５８２９号明細書（下記の特許文献１）は、アトミック転送をＣＰＵ及びローカルバスに実装した装置を開示している。この種のマルチプロセッサシステムは、バスバンド幅を削減するために共有バス方式を採用し、ＭＥＳＩプロトコルを用いることによってロックを獲得できないＣＰＵが無駄なリードアクセスを繰り返さないようにする。
【００１０】
米国特許第５１７５８２９号明細書（下記の特許文献２）は、ロックを管理するためのスワップレジスタをＣＰＵに内蔵した装置を開示している。この装置は、スワップレジスタに格納したロック変数をメモリに格納したロック変数で時々スワップして更新し、ロックを獲得するためのリードアクセスはこのスワップレジスタに対して行われる。この装置も、高価でかつ複雑なアトミックリードモディファイライト機能の存在を前提としている。
【００１１】
米国特許第５６６６５１５号明細書（下記の特許文献３）は、リトライ信号を送ることによってロックをかけ、バスバンド幅の飽和を軽減した装置を開示している。この装置も、高価でかつ複雑なアトミックリードモディファイライト機能の存在を前提としている。
【特許文献１】
米国特許第５１７５８２９号明細書
【特許文献２】
米国特許第５５３５３６５号明細書
【特許文献３】
米国特許第５６６６５１５号明細書
【発明の開示】
【発明が解決しようとする課題】
［００１２］
本発明の目的は、ロック変数のアトミックリードモディファイライト機能を有する高価なシステムと同等の機能を簡単な構成で実現可能なマルチプロセッサシステムを提供することである。
課題を解決するための手段及び発明の効果
［００１３］
本発明によるマルチプロセッサシステムは、複数のプロセッサと、ロックレジスタとを備える。プロセッサの各々は、排他制御を実行する前にロックを獲得するために読出信号をアサートし、かつ排他制御を実行した後にロックを解放するために書込信号をアサートする。ロックレジスタは、複数のプロセッサに接続される。ロックレジスタは、保持手段と、ロック変数出力手段と、ロック変数入力手段とを含む。保持手段は、ロック状態又は非ロック状態の第１のロック変数を保持する。ロック変数出力手段は、プロセッサの１つが読出信号をアサートすると、それ以前に保持手段に保持されていた第１のロック変数を出力する。ロック変数入力手段は、プロセッサの１つが読出信号をアサートすると、ロック状態の第１のロック変数を保持手段に設定し、プロセッサの１つが書込信号をアサートすると、非ロック状態の第１のロック変数を保持手段に設定する。
［００１４］
上記マルチプロセッサシステムでは、あるプロセッサが読出信号をアサートすると、ロックレジスタから第１のロック変数が読み出されるとともに、ロックレジスタにロック状態の第１のロック変数が書き込まれる。読み出された第１のロック変数が非ロック状態の場合、そのプロセッサはロックを獲得することができる。第１のロック変数が読み出されるとともに、ロック状態の第１のロック変数が書き込まれるので、その直後に、別のプロセッサが読出信号をアサートしても、ロックレジスタからロック状態の第１のロック変数が読み出されるため、その別のプロセッサはロックを獲得することができない。このように、本発明によるマルチプロセッサシステムは、ロックレジスタを設けるだけで、ロック変数のアトミックリードモディファイライト機能を有する高価なシステムと同等の機能を実現することができる。
［００１５］
好ましくは、ロックレジスタはさらに、バスリトライ手段を含む。バスリトライ手段は、第１のロック変数がロック状態に設定されている間にプロセッサの１つが読出信号をアサートすると、プロセッサに供給するためのバスリトライ信号を発生する。
［００１６］
この場合、プロセッサはバスリトライ信号を受け、これによりロックの獲得が不可能なことを認識するので、むやみに読出信号をアサートしないようにすることができる。
［００１７］
好ましくは、マルチプロセッサシステムはさらに、第１のバスと、メモリと、２のバスとを備える。第１のバスは、複数のプロセッサに共通に接続される。メモリは、第１のバスに接続される。第２のバスは、複数のプロセッサに共通に接続される。ロックレジスタは第２のバスに接続される。
［００１８］
この場合、あるプロセッサがロックを獲得しているために、別のプロセッサがそのロックの解放を待っているとき、その別のプロセッサは第２のバス経由で読出信号をアサートしてロックレジスタから第１のロック変数を読み出し、その一方で、ロックを獲得しているプロセッサは第１のバス経由でメモリにアクセスする。したがって、ロックを獲得しているプロセッサからメモリへのアクセスは妨げられない。
［００１９］
さらに好ましくは、メモリは１又は２以上の第２のロック変数を記憶する。プロセッサの各々は、読出信号をアサートしてロックレジスタから第１のロック変数を読み出し、読み出した第１のロック変数が非ロック状態の場合、メモリから第２のロック変数を読み出し、読み出した第２のロック変数が非ロック状態の場合、第２のロック変数をロック状態に書き換える。
［００２０］
この場合、プロセッサはまずロックレジスタから第１のロック変数を読み出してロックを獲得し、続いてメモリから第２のロック変数を読み出してロックを獲得する。このようにロックを階層的に獲得するようにしているので、多数のロック変数を設定することができる。
［００２１］
［００２２］
［００２３］
［００２４］
［００２５］
［００２６］
【発明を実施するための最良の形態】
［００２７］
以下、図面を参照し、本発明の実施の形態を詳しく説明する。図中同一又は相当分には同一符号を付してその説明は繰り返さない。
【００２８】
図１を参照して、本発明の実施の形態によるマルチプロセッサシステム１０は、ＣＰＵ１１及び１２と、バスマスタ１３及び１４と、クロスバーバス１５及び１６と、システムメモリ１７と、ロックレジスタ１８とを備える。
【００２９】
ＣＰＵ１１及び１２と、バスマスタ１３及び１４とは、クロスバーバス１５に共通に接続される。ＣＰＵ１１及び１２と、バスマスタ１３及び１４とはまた、もう１つのクロスバーバス１６にも共通に接続される。システムメモリ１７はクロスバーバス１５に接続され、ロックレジスタ１８はクロスバーバス１６に接続される。ＣＰＵ１１又は１２はクロスバーバス１５経由でシステムメモリ１７にアクセス可能であり、クロスバーバス１６経由でロックレジスタ１８にもアクセス可能である。バスマスタ１３又は１４はクロスバーバス１５経由でシステムメモリ１７にアクセス可能であり、クロスバーバス１６経由でロックレジスタ１８にもアクセス可能である。
【００３０】
ロックレジスタ１８は、排他制御に必要なロックを管理するためのレジスタである。ＣＰＵ１１又は１２は、排他制御を実行する前に読出信号をアサートしてロックレジスタ１８からロックを獲得し、排他制御を実行した後に書込信号をアサートしてそのロックを解放する。ロックレジスタ１８はメモリ上にマップされるが、システムメモリ１７とは異なるアドレスが割り当てられる。
【００３１】
図２を参照して、ロックレジスタ１８は、ＣＰＵ１１又は１２から読出信号ＲＥＡＤ及び書込信号ＷＲＩＴＥを受け付け、読出データバス信号ＲＥＡＤｄａｔａｂｕｓ及びバスリトライ信号ＢＵＳＲｅｔｒｙを出力する。ロックレジスタ１８は、遅延フリップフロップ（ＤＦＦ）１９及び２０と、ＯＲ回路２１と、ＡＮＤ回路２２及び２３と、マルチプレクサ２４とを備える。ＯＲ回路２１は、読出信号ＲＥＡＤ及びＤＦＦ１９の出力信号を受ける。ＡＮＤ回路２２は、ＯＲ回路２１の出力信号、書込信号ＷＲＩＴＥの論理反転信号及びリセット信号ＲＥＳＥＴの論理反転信号を受ける。ＤＦＦ１９は、クロック信号ＣＬＫに同期してＡＮＤ回路２２の出力信号をラッチする。読出信号ＲＥＡＤがＨ（論理ハイ）レベル「１」の場合、マルチプレクサ２４はＤＦＦ１９の出力信号の出力信号を選択して出力する。一方、読出信号ＲＥＡＤがＬ（論理ロー）レベル「０」の場合、マルチプレクサ２４はＤＦＦ２０の出力信号を選択して出力する。ＤＦＦ２０は、クロック信号ＣＬＫに同期してマルチプレクサ２４の出力信号をラッチし、読出データバス信号ＲＥＡＤｄａｔａｂｕｓとして出力する。ＡＮＤ回路２３は、読出信号ＲＥＡＤ及びＤＦＦ１９の出力信号を受け、バスリトライ信号ＢＵＳＲｅｔｒｙを発生する。
【００３２】
ＤＦＦ１９は、ロック状態「１」又は非ロック状態「０」のメインロック変数ＬＯＣＫを保持する機能を有する。ＯＲ回路２１及びＡＮＤ回路２２は、ＣＰＵ１１又は１２が読出信号ＲＥＡＤをアサートすると、ロック状態「１」のメインロック変数ＬＯＣＫをＤＦＦ１９に設定し、ＣＰＵ１１又は１２が書込信号ＷＲＩＴＥをアサートすると、非ロック状態「０」のメインロック変数ＬＯＣＫをＤＦＦ１９に設定する機能を有する。マルチプレクサ２４及びＤＦＦ２０は、ＣＰＵ１１又は１２が読出信号ＲＥＡＤをアサートすると、それ以前にＤＦＦ１９に保持されていたメインロック変数ＬＯＣＫを出力する機能を有する。ＡＮＤ回路２３は、メインロック変数ＬＯＣＫがロック状態「１」に設定されている間にＣＰＵ１１又は１２が読出信号ＲＥＡＤをアサートすると、ＣＰＵ１１及び１２に供給するためのバスリトライ信号ＢＵＳＲｅｔｒｙを発生する機能を有する。
【００３３】
また、システムメモリ１７には、１又は２以上のサブロック変数ｌｏｃｋを記憶させている。ＣＰＵ１１又は１２はスヌープキャッシュを持たないので、サブロック変数ｌｏｃｋをアロケートするためのメモリ領域は非キャッシュ領域に設定する。
【００３４】
次に、ロックレジスタ１８の動作を図３を参照して説明する。
【００３５】
リセット信号ＲＥＳＥＴがＨレベルにアサートされると、クロック信号ＣＬＫが立ち上がる時刻ｔ１で、ロックレジスタ１８は初期化される。具体的には、ＡＮＤ回路２２は、読出信号ＲＥＡＤ及び書込信号ＷＲＩＴＥに関係なく、Ｌレベルの信号を出力し、ＤＦＦ１９はこれをラッチする。つまり、ＤＦＦ１９は非ロック状態「０」のメインロック変数ＬＯＣＫを保持する。
【００３６】
次に、１つのＣＰＵ１１又は１２がロックが獲得可能か否かを確認するために、読出信号ＲＥＡＤをＨレベルにアサートすると、ＡＮＤ回路２２の出力信号がＨレベルになる。ＤＦＦ１９は、クロック信号ＣＬＫが立ち上がる時刻ｔ２で、そのＨレベルの信号をラッチして出力する。ＤＦＦ１９の出力信号はＯＲ回路２１に与えられるので、読出信号ＲＥＡＤがＬレベルに戻った後も、ＤＦＦ１９はＨレベルの信号をラッチし続け、これによりロック状態「１」のメインロック変数ＬＯＣＫを保持する。
【００３７】
読出信号ＲＥＡＤがＬレベルに戻ると、マルチプレクサ２４はＤＦＦ２０の出力信号を選択し、ＤＦＦ２０はＬレベルの信号をラッチし続けるので、読出データバス信号ＲＥＡＤｄａｔａｂｕｓはＬレベルのまま維持される。したがって、当該ＣＰＵ１１又は１２はロックが獲得可能と認識する。
【００３８】
ロックが獲得可能と認識した直後に、他のＣＰＵ１２又は１１がロックが獲得可能か否かを確認するために、読出信号ＲＥＡＤをＨレベルにアサートしたとしても、ＤＦＦ１９の出力信号は既にＨレベルになっているので、ＡＮＤ回路２３はバスリトライ信号ＢＵＳＲｅｔｒｙをＨレベルにアサートする。したがって、当該他のＣＰＵはロックが獲得不可能と認識する。また、読出信号ＲＥＡＤがＨレベルにアサートされ、マルチプレクサ２４がＤＦＦ１９の出力信号を選択するので、クロック信号ＣＬＫが立ち上がる時刻ｔ３で、ＤＦＦ２０がＨレベルの信号をラッチし、これにより読出データバス信号ＲＥＡＤｄａｔａｂｕｓがＨレベルにアサートされる。
【００３９】
次に、当該ＣＰＵ１１又は１２がロックを解放するために、書込信号ＷＲＩＴＥをＨレベルにアサートすると、ＡＮＤ回路２２の出力信号がＬレベルになる。ＤＦＦ１９は、クロック信号ＣＬＫが立ち上がる時刻ｔ４で、そのＬレベルの信号をラッチして出力する。これにより、メインロック変数ＬＯＣＫは非ロック状態「０」にクリアされる。
【００４０】
その後、再びＣＰＵ１１又は１２がロックが獲得可能か否かを確認するために、読出信号ＲＥＡＤをＨレベルにアサートすると、クロック信号ＣＬＫが立ち上げる時刻ｔ５で、ＤＦＦ１９は前回と同様にＨレベルの信号をラッチして出力する。このとき、マルチプレクサ２４はＬレベルの信号を選択するので、ＤＦＦ２０はこれをラッチして出力する。したがって、読出データバス信号ＲＥＡＤｄａｔａｂｕｓはＬレベルに戻り、ＣＰＵ１１又は１２はロックが獲得可能と認識する。
【００４１】
次に、このロックレジスタ１８を用いたマルチプロセッサシステム１０全体の動作を図４を参照して説明する。
【００４２】
ＣＰＵ１１又は１２は、ロックレジスタ１８からメインロック変数ＬＯＣＫを読み出し（Ｓ１１）、ＬＯＣＫ＝１か否か、つまりメインロック変数ＬＯＣＫがロック状態「１」か否かを判断する（Ｓ１２）。非ロック状態「０」の場合（Ｓ１２でＮＯ）、ＣＰＵ１１又は１２は、システムメモリ１７からサブロック変数ｌｏｃｋを読み出し（Ｓ１３）、ｌｏｃｋ＝１か否か、つまりサブロック変数ｌｏｃｋがロック状態「１」か否かを判断する（Ｓ１４）。非ロック状態「０」の場合（Ｓ１４でＮＯ）、ＣＰＵ１１又は１２は、「１」をサブロック変数ｌｏｃｋに書き込み、これによりロックを獲得する（Ｓ１５）。ロックの獲得後、ＣＰＵ１１又は１２は、所定の排他制御を実行する（Ｓ１６）。排他制御の完了後、ＣＰＵ１１又は１２は「０」をサブロック変数ｌｏｃｋに書き込み、これによりロックを解放する（Ｓ１７）。
【００４３】
以上のように本発明の実施の形態によれば、ＣＰＵ１１又は１２が読出信号ＲＥＡＤをアサートすると、ロックレジスタ１８からメインロック変数ＬＯＣＫが読み出され、かつ直ちにロックレジスタ１８にロック状態「１」のメインロック変数ＬＯＣＫが書き込まれるので、その直後に、別のＣＰＵ１２又は１１が読出信号ＲＥＡＤをアサートしても、ロックレジスタ１８からロック状態「１」のメインロック変数ＬＯＣＫが読み出される。そのため、別のＣＰＵ１２又は１１はロックを獲得することができない。したがって、ロック変数のアトミックリードモディファイライト機能を有する高価なマルチプロセッサシステムと同等の機能をロックレジスタ１８を設けるだけで実現することができる。
【００４４】
また、メインロック変数ＬＯＣＫがロック状態「１」に設定されている間にＣＰＵ１１又は１２が読出信号ＲＥＡＤをアサートすると、バスリトライ信号ＢＵＳＲｅｔｒｙが発生し、ＣＰＵ１１及び１２はこのバスリトライ信号ＢＵＳＲｅｔｒｙを受けてロックの獲得が不可能なことを認識するので、むやみに読出信号ＲＥＡＤをアサートしないようにすることができる。
【００４５】
また、ロックの獲得又は解放のためのＣＰＵ１１又は１２からロックレジスタ１８へのアクセスは専用のクロスバーバス１６経由で行われるので、ＣＰＵ１１又は１２がロックを獲得しているために、別のＣＰＵ１２又は１１がそのロックの解放を待っているとき、別のＣＰＵ１２又は１１はクロスバーバス１６経由で読出信号ＲＥＡＤをアサートしてロックレジスタ１８からメインロック変数ＬＯＣＫを読み出し、その一方で、ロックを獲得しているＣＰＵ１１又は１２はクロスバーバス１５経由でシステムメモリ１７にアクセスする。したがって、ロックを獲得しているＣＰＵ１１又は１２からシステムメモリ１７へのアクセスは妨げられない。
【００４６】
また、１又は２以上のサブロック変数ｌｏｃｋをシステムメモリ１７に記憶しておき、ＣＰＵ１１又は１２はまずロックレジスタ１８からメインロック変数ＬＯＣＫを読み出してロックを獲得し、続いてシステムメモリ１７からサブロック変数ｌｏｃｋを読み出してロックを獲得するというように、ロックを階層的に獲得しているので、多数のロック変数ｌｏｃｋを設定することができる。
【００４７】
以上、本発明の実施の形態を説明したが、上述した実施の形態は本発明を実施するための例示に過ぎない。よって、本発明は上述した実施の形態に限定されることなく、その趣旨を逸脱しない範囲内で上述した実施の形態を適宜変形して実施することが可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施の形態によるマルチプロセッサシステムの全体構成を示す機能ブロック図である。
【図２】図１中のロックレジスタの構成を示す回路図である。
【図３】図２に示したロックレジスタの動作を示すタイミング図である。
【図４】図１に示したマルチプロセッサシステムによるロック獲得動作を示すフロー図である。
【図５】従来のマルチプロセッサによるロック獲得動作を示すフロー図である。
【符号の説明】
【００４９】
１０    マルチプロセッサシステム
１１，１２    ＣＰＵ
１５，１６    クロスバーバス
１７    システムメモリ
１８    ロックレジスタ
ＬＯＣＫ    メインロック変数
ｌｏｃｋ    サブロック変数
ＲＥＡＤ    読出信号
ＷＲＩＴＥ    書込信号
ＢＵＳＲｅｔｒｙ    バスリトライ信号
ＲＥＡＤｄａｔａｂｕｓ    読出データバス信号
【図１】
0004852427.tif 000002
【図２】
0004852427.tif 000003
【図３】
0004852427.tif 000004
【図４】
0004852427.tif 000005
【図５】
0004852427.tif 000006