(57)【要約】【課題】マルチプロセッサシステムにおける共有メモリの管理のための方法及び装置を提供する。【解決手段】  メモリ割当てテーブル（ＭＡＴ）の、それぞれが状態情報を有するエントリ及びバイナリツリーのノードが階層的なレベルにグループ分けされるよう、エントリをノードと関連させ、上位レベルノード及びエントリに関連するマルチプロセッサシステムの共有メモリのセグメントの数が多く、下位レベルノード及びエントリに関連する共有メモリのセグメントの数が少なくなるように、ノード及びエントリを共有メモリのセグメントと関連させる。これにより、少なくとも複数のエントリの状態情報が、前記共有メモリの関連する１つ以上のセグメントが予約可能であることを示すように前記ＭＡＴを初期化して、予約しようとしている前記共有メモリの所望サイズに対応するレベルにおいてＭＡＴ内のエントリのグループのうちの１つのエントリを選択する方法及び装置である。【選択図】図１
2006190299.tif 000002
【特許請求の範囲】
【請求項１】
メモリ割当てテーブルのエントリ及びバイナリツリーのノードが階層的なレベルにグループ分けされるように、前記エントリを前記ノードと関連させるステップと、
上位レベルノード及びエントリに関連するマルチプロセッサシステムの共有メモリのセグメントの数が多く、下位レベルノード及びエントリに関連する前記共有メモリのセグメントの数が少なくなるように、前記ノード及び前記エントリを前記共有メモリのセグメントと関連させるステップと、
予約しようとしている前記共有メモリの所望のサイズに対応する前記メモリ割当てテーブルのエントリの状態情報を評価し、１つ以上の上位レベルのエントリの状態情報を評価して、前記共有メモリの１つ以上のセグメントを選択するステップと、を有する方法。
【請求項２】
各エントリの前記状態情報は、関連する前記共有メモリの１つ以上のセグメントが既に予約されているかどうか、又は予約可能であるかどうかを示す識別情報を少なくとも含む請求項１に記載の方法。
【請求項３】
所定のエントリの前記状態情報は、前記所定のエントリの系列にある１つ以上の下位レベルのエントリと関連する前記共有メモリの１つ以上のセグメントが既に予約されていることを示す識別情報を含む請求項２に記載の方法。
【請求項４】
各エントリに対する前記状態情報は２ビットを越えない２進数データのみによって表される請求項２又は３に記載の方法。
【請求項５】
前記バイナリツリーの最上位レベルノードと関連する前記メモリ割当てテーブル内の最上位レベルのエントリは、前記共有メモリの前記セグメントの全てと関連しており、
前記バイナリツリーの複数の最下位レベルノードと関連する前記メモリ割当てテーブル内の複数の最下位レベルのエントリは、それぞれ前記共有メモリの１つのセグメントと関連している請求項１〜４のいずれか１項に記載の方法。
【請求項６】
前記共有メモリの１つ以上のセグメントを選択する前記ステップは、予約しようとしている前記共有メモリの所望のサイズに基づいて前記メモリ割当てテーブル内でのレベルを算出するステップを有する請求項５に記載の方法。
【請求項７】
前記メモリ割当てテーブル内の前記レベルはｌｏｇ２（Ｍ／Ｄ）に略等しいと算出され、上記式において、Ｍは前記共有メモリの予約可能な最大サイズであり、Ｄは予約しようとしている前記共有メモリの前記所望のサイズである請求項６に記載の方法。
【請求項８】
前記算出したレベルと関連する前記エントリのうち、関連する前記共有メモリの１つ以上のセグメントが予約可能であることを示す状態情報を有する１つのエントリを選択するステップを更に有する請求項６に記載の方法。
【請求項９】
前記選択したエントリの系列にある１つ以上の上位レベルのエントリを評価して、前記上位レベルのエントリが、関連する前記共有メモリのセグメントが予約可能であることを示す状態情報を有するかどうかを判定するステップを更に有する請求項８に記載の方法。
【請求項１０】
前記系列にある上位レベルのエントリのうちの１つの状態情報が前記共有メモリの前記関連するセグメントが予約可能であることを示すまで、前記上位レベルのエントリについて前記評価ステップを順次繰り返す請求項９に記載の方法。
【請求項１１】
前記系列にある前記上位レベルの１つ以上のエントリが、前記共有メモリの前記関連するセグメントが予約可能ではないことを示す状態情報を有することが、前記判定により示される場合、前記算出したレベルと関連する前記エントリのうちの別のエントリを選択し、前記エントリのうちの前記別のエントリは、関連する前記共有メモリの１つ以上のセグメントが予約可能であることを示す状態情報を有する請求項１０に記載の方法。
【請求項１２】
前記共有メモリの前記予約されたセグメントは、１つ以上の予約されたオブジェクトを形成する請求項１〜１１のいずれか１項に記載の方法。
【請求項１３】
前記予約されたオブジェクトを前記マルチプロセッサシステムの複数のプロセッサの間で共有するステップを更に有する請求項１２に記載の方法。
【請求項１４】
キーテーブル内で前記予約されたオブジェクトを前記バイナリツリーの前記関連するノードと関連させるステップを更に有する請求項１３に記載の方法。
【請求項１５】
前記共有メモリの前記１つ以上のセグメントを予約する前記ステップの前に、前記キーテーブルにアクセスしてオブジェクトが既に作成されているかどうかを判定するステップを更に有する請求項１４に記載の方法。
【請求項１６】
オブジェクトが既に形成されていることが前記キーテーブルにより示される場合、当該オブジェクトを使用するステップと、
オブジェクトが作成されていないことが前記キーテーブルにより示される場合、前記オブジェクトを形成するために前記共有メモリの１つ以上のセグメントを選択するステップと、を更に有する請求項１５に記載の方法。
【請求項１７】
メモリ割当てテーブルの、それぞれが状態情報を有するエントリ及びバイナリツリーのノードが階層的なレベルにグループ分けされるように、前記エントリを前記ノードと関連させるステップと、
上位レベルノード及びエントリに関連するマルチプロセッサシステムの共有メモリのセグメントの数が多く、下位レベルノード及びエントリに関連する前記共有メモリのセグメントの数が少なくなるように、前記ノード及び前記エントリを前記共有メモリのセグメントと関連させるステップと、
少なくとも複数のエントリの状態情報が、前記共有メモリの関連する１つ以上のセグメントが予約可能であることを示すように前記メモリ割当てテーブルを初期化するステップと、
予約しようとしている前記共有メモリの所望のサイズに対応するレベルにおいて前記メモリ割当てテーブル内のエントリのグループのうちの１つのエントリを選択するステップと、を有する方法。
【請求項１８】
前記選択するステップは、予約しようとしている前記共有メモリの前記所望のサイズに基づいて前記メモリ割当てテーブル内でのレベルを算出するステップを有する請求項１７に記載の方法。
【請求項１９】
前記メモリ割当てテーブル内の前記レベルはｌｏｇ２（Ｍ／Ｄ）に略等しいと算出され、上記式において、Ｍは前記共有メモリの予約可能な最大サイズであり、Ｄは予約しようとしている前記共有メモリの前記所望のサイズである請求項１８に記載の方法。
【請求項２０】
前記算出したレベルにおいて、前記エントリのグループのうちの、前記選択したエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示す状態情報を有する前記エントリを選択するステップを更に有する請求項１８に記載の方法。
【請求項２１】
前記算出したレベルにおいて、前記エントリのグループのうちの前記エントリを仮に選択するステップをさらに有し、前記仮に選択したエントリは、このエントリと関連する前記共有メモリの前記少なくとも１つの前記セグメントが予約可能であることを示す状態情報を有する請求項１８に記載の方法。
【請求項２２】
前記グループの前記エントリを仮に選択する前記ステップは、前記予約可能であることを示す状態情報を有する１つのエントリがみつかるまで前記グループの前記エントリの前記状態情報を逐次的に評価する請求項２１に記載の方法。
【請求項２３】
前記仮に選択したエントリの系列にある１つ以上の上位レベルのエントリの状態情報を評価して、前記状態情報が、前記仮に選択したエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示すかどうかを判定するステップを更に有する請求項２１に記載の方法。
【請求項２４】
前記評価するステップは、
現在のエントリの状態情報が、前記現在のエントリと関連する前記共有メモリの全てのセグメントが予約可能であることを示す場合に、前記系列にある連続する上位レベルのエントリの前記評価を継続するステップと、
前記現在のエントリの前記状態情報が、前記メモリ割当てテーブル内の下位レベルのエントリと関連する１つ以上のメモリセグメントに対して以前に予約が行われているが、前記現在のエントリと関連する全てのメモリセグメントが予約されているわけではないことを示すまで、前記ステップを繰り返すステップと、を有する請求項２３に記載の方法。
【請求項２５】
（ｉ）評価した全エントリの状態情報が、前記評価した個々のエントリと関連する前記共有メモリの全てのセグメントが予約可能であることを示し、かつ
（ｉｉ）前記逐次的な評価を終了する前に前記メモリ割当てテーブルの最上位レベルのエントリに到達した場合に、前記評価した全エントリの前記状態情報を変更し、
評価した各エントリの前記状態情報は、前記メモリ割当てテーブル内の下位レベルのエントリと関連する１つ以上のメモリセグメントに対して以前に予約が行われているが、前記現在のエントリと関連する全てのメモリセグメントが予約されているわけではないことを示すために変更される、請求項２４に記載の方法。
【請求項２６】
前記系列にある現在の上位レベルのエントリの状態情報の前記評価により、前記現在のエントリと関連する前記共有メモリの全てのセグメントが予約されていることが示される場合に、前記メモリ割当てテーブルの前記仮に選択したエントリを破棄するステップを更に有する請求項２４に記載の方法。
【請求項２７】
前記算出したレベルにおいて、前記仮に選択したエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示す状態情報を有する別のエントリを仮に選択するステップと、
前記仮に選択した別のエントリの系列にある１つ以上の上位レベルのエントリの状態情報の前記評価ステップを実行して、前記状態情報が、前記仮に選択した別のエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示すかどうかを判定するステップと、を更に有する請求項２６に記載の方法。
【請求項２８】
前記メモリ割当てテーブルの前記仮に選択したエントリを選択して、前記メモリ割当てテーブルの前記選択したエントリと関連する前記共有メモリの１つ以上のセグメントを予約するステップを更に有する請求項２４に記載の方法。
【請求項２９】
前記選択したエントリと関連する前記共有メモリの全てのセグメントが予約されていることを示すために前記選択したエントリの前記状態情報を変更するステップを更に有する請求項２８に記載の方法。
【請求項３０】
記憶媒体から複数のエントリを有するメモリ割当てテーブルを読み出すステップであって、前記エントリとバイナリツリーのノードが階層的なレベルにグループ分けされるように、各エントリが個々のノードと関連しており、前記ノード及び前記エントリはマルチプロセッサシステムの共有メモリのセグメントと関連しているステップと、
予約しようとしている前記共有メモリの所望のサイズに対応する前記メモリ割当てテーブルのエントリの状態情報を評価することによって前記共有メモリの１つ以上のセグメントを選択するステップと、
前記共有メモリの前記１つ以上の選択したセグメントが予約されたことを示すために前記メモリ割当てテーブルを変更するステップと、
前記変更したメモリ割当てテーブルを前記記憶媒体に書き戻すステップと、を有する方法。
【請求項３１】
共有メモリと通信動作が可能であり、それぞれがハードウェアキャッシュメモリでないローカルメモリを有する複数のパラレルプロセッサと、命令実行パイプラインとを有し、
前記プロセッサのうちの少なくとも１つは、
記憶媒体から複数のエントリを有するメモリ割当てテーブルを読み出し、その際、前記エントリとバイナリツリーのノードが階層的なレベルにグループ分けされるように、各エントリが個々のノードと関連しており、前記ノード及び前記エントリはマルチプロセッサシステムの共有メモリのセグメントと関連しており、
予約しようとしている前記共有メモリの所望のサイズに対応する前記メモリ割当てテーブルのエントリの状態情報を評価することによって前記共有メモリの１つ以上のセグメントを選択し、
前記共有メモリの前記１つ以上の選択したセグメントが予約されたことを示すために前記メモリ割当てテーブルを変更し、
前記変更したメモリ割当てテーブルを前記記憶媒体に書き戻すように動作可能である装置。
【請求項３２】
前記記憶媒体は前記共有メモリである請求項３１に記載の装置。
【請求項３３】
各プロセッサは、当該プロセッサのローカルメモリ内で１つ以上のプログラムを実行するために、前記共有メモリと前記ローカルメモリの間でデータのブロックを転送するように動作可能である請求項３１又は３２に記載の装置。
【請求項３４】
各プロセッサは当該プロセッサのローカルメモリの中で前記１つ以上のプログラムを実行することができるが、各プロセッサは前記共有メモリ内で前記１つ以上のプログラムを実行することができない。請求項３３に記載の装置。
【請求項３５】
前記プロセッサと関連するローカルメモリは共通の半導体基板に配置されている請求項３１〜３４のいずれか１項に記載の装置。
【請求項３６】
前記共有メモリはバスを介して前記プロセッサに結合される、請求項３１〜３４のいずれか１項に記載の装置。
【請求項３７】
前記プロセッサ、関連するローカルメモリ及び前記共有メモリは共通の半導体基板に配置されている請求項３６に記載の装置。
【請求項３８】
マルチプロセッサシステムに、
メモリ割当てテーブルの、それぞれが状態情報を有するエントリ及びバイナリツリーのノードが階層的なレベルにグループ分けされるように、前記エントリを前記ノードと関連させるステップと、
上位レベルノード及びエントリに関連するマルチプロセッサシステムの共有メモリのセグメントの数が多く、下位レベルノード及びエントリに関連する前記共有メモリのセグメントの数が少なくなるように、前記ノード及び前記エントリを前記共有メモリのセグメントと関連させるステップと、
少なくとも複数のエントリの状態情報が、前記共有メモリの関連する１つ以上のセグメントが予約可能であることを示すように前記メモリ割当てテーブルを初期化するステップと、
予約しようとしている前記共有メモリの所望のサイズに対応するレベルにおいて前記メモリ割当てテーブル内のエントリのグループのうちの１つのエントリを選択するステップと、を有するアクションを実行させることができる少なくとも１つのソフトウェアプログラムが記録されたコンピュータ可読記憶媒体。
【請求項３９】
前記グループの各エントリの状態情報を評価することによってことによって前記エントリを選択してから、前記選択したエントリの系列にある１つ以上の上位レベルのエントリの状態情報を評価する請求項３８に記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリの一部分を予約できるマルチプロセッサシステムの共有メモリの管理のための方法及び装置に関する。
【背景技術】
【０００２】
最先端のコンピュータアプリケーションは、リアルタイムのマルチメディア機能を伴っているために、近年はデータスループットが高くより高速なコンピュータが常に望まれている。グラフィックアプリケーションは処理システムへの要求が大きいアプリケーションの１つであり、その理由は、グラフィックアプリケーションが所望のビジュアル結果を実現するために、比較的短時間で非常に多くのデータアクセス、データの演算処理、及びデータ操作を要求するからである。これらのアプリケーションは、１秒間に数千メガビットのデータ処理等の非常に高速な処理速度を要求する。シングルプロセッサを採用し、高速の処理速度を実現している処理システムもある一方で、マルチプロセッサアーキテクチャを利用して実装されている処理システムもある。マルチプロセッサシステムでは、複数のプロセッサが並列に（あるいは少なくとも協調して）動作し、所望の処理結果を実現することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
既存のマルチプロセッサシステムの中には、データを記憶するため、複数のパラレルプロセッサが共有メモリを使用できるものがある。既に使用中の領域が割当てられないようにして、未使用の領域を割当てできるようにするために、メモリ管理技術が使用される。共有メモリの割当てを管理する従来のアプローチでは、メモリ領域のアービタとして管理プロセッサが使用される。この方法は、パラレルプロセッサの自主性を奪うため、場合によっては処理効率を低下させることがある。
【課題を解決するための手段】
【０００４】
本発明の１つ以上の実施形態は、システムの共有メモリからメモリ割当てテーブル（ＭＡＴ）にアクセスすることによって、メモリ割当てを制御するためのマルチプロセッサシステムのパラレルプロセッサを提供する。前記プロセッサは、テーブル内でメモリの未使用のセグメントを検索して、必要に応じて１つ以上のセグメントを予約するように更に動作可能である。また、本発明は、１回のＤＭＡサイクルにおいて、共有メモリからコピーし、容易に検索して、容易に更新できる極めてコンパクトなＭＡＴ構造を提供する。
【０００５】
ＭＡＴは好ましくは一次元の配列であり、配列内の各逐次的な位置は「ノード」に対応しており、各位置の内容は状態ビット（好ましくは２ビット）を含む。ＭＡＴのノードはバイナリツリーのノードを表している。ルートノードであるノード１は、レベル０（バイナリツリーの最上位）にあり、共有メモリの最大割当てスペースを表している。ノード１に従属する中間ノード２，３は、レベル１にあり、それぞれ最大割当てスペースの１／２を表している。ノード２に従属している中間ノード４，５と、ノード３に従属している中間ノード６，７は、レベル２にあり、それぞれ最大割当てスペースの１／４を表している。４レベルのバイナリツリー（Ｌ＝４）を仮定すると、終端ノード８，９（ノード４に従属）、終端ノード１０，１１（ノード５に従属）、終端ノード１２，１３（ノード６に従属）及び終端ノード１４，１５（ノード７に従属）は、レベル３にあり、それぞれ最大割当てスペースの１／８を表している。
【０００６】
ＭＡＴの各ノード位置の内容は、好ましくは２の状態ビットを含み、Ｎ＝一部予約、Ｉ＝予約可能、Ｕ＝使用済み、及びＣ＝続き、を表している。
【０００７】
上の例をそのまま使用すると共に、例えば最大割当てサイズが８ＫＢであるとすると、各終端ノード（例えばノード８〜１５）は、割当て可能なメモリの１ＫＢのセグメントを表しており、割当ての粒度が１ＫＢということになる。ＭＡＴのサイズは、ノードの数（２Ｌ−１）に２ビットを掛けた値に等しく、この場合は１５×２＝３０ビットとなる。
【０００８】
共有メモリのスペース（例えば１ＫＢのスペース）を取得しようとしているプロセッサは、（一回のＤＭＡ転送を有利に使用して）共有メモリからＭＡＴを読み出す。プロセッサは、必要なスペースのサイズを、次式：レベル＝ｌｏｇ２（最大スペース／要求スペース）を使用してバイナリツリー内のレベルに変換するが、この例では、レベル＝ｌｏｇ２（８ＫＢ／１ＫＢ）＝３となる。このレベルは、ＭＡＴの終端ノード８〜１５に対応している。プロセッサは、ノード８を起点として状態が（Ｉ）のノードを検索し、例えばこれがノード１０でみつかったとする。次に、より大きなメモリの領域（例えば２つ以上の連続するセグメント）が以前に予約されたかどうかを判定するため、ノード１０の系列（lineage）が調べられる。予約されていない場合、ノード１０とＭＡＴのエントリ１０と関連する共有メモリセグメントが予約されうる。
【０００９】
本発明の１つ以上の更なる態様によれば、方法及び装置は、メモリ割当テーブル（ＭＡＴ）のエントリ及びバイナリツリーのノードが階層的なレベルにグループ分けされるように、前記エントリを前記ノードと関連させるステップと、上位レベルノード及びエントリに関連するマルチプロセッサシステムの共有メモリのセグメントの数が多く、下位レベルノード及びエントリに関連する前記共有メモリのセグメントの数が少なくなるように、前記ノード及び前記エントリを前記共有メモリのセグメントと関連させるステップと、予約しようとしている前記共有メモリの所望のサイズに対応する前記ＭＡＴのエントリの状態情報を評価することによって前記共有メモリの１つ以上のセグメントを選択してから、１つ以上の上位レベルのエントリの状態情報を評価するステップと、を有する。
【００１０】
各エントリの状態情報は、（ｉ）関連する共有メモリの１つ以上のセグメントが既に予約されているかどうか、又は予約可能かどうかを示すインディケータ（標識情報）と、（ｉｉ）所定のエントリの系列にある１つ以上の下位レベルのエントリと関連する共有メモリの１つ以上のセグメントが既に予約されていることを示す識別情報、を少なくとも含む。
【００１１】
前記バイナリツリーの最上位レベルノード及び関連する前記ＭＡＴ内の最上位レベルのエントリは、好ましくは前記共有メモリの前記セグメントの全てと関連しており、前記バイナリツリーの複数の最下位レベルノード及び関連する前記ＭＡＴ内の複数の最下位レベルのエントリは、好ましくはそれぞれ前記共有メモリの１つのセグメントと関連している。
【００１２】
前記ＭＡＴは、少なくとも複数のエントリの状態情報が、前記共有メモリの関連する１つ以上のセグメントが予約可能であることを示すように好ましくは初期化される。
【００１３】
前記共有メモリの１つ以上のセグメントを選択する機能は、予約しようとしている前記共有メモリの所望のサイズに基づいて前記ＭＡＴ内でのレベルを算出することを含みうる。前記ＭＡＴ内の前記レベルはｌｏｇ２（Ｍ／Ｄ）に略等しいと算出され、上記式において、Ｍは前記共有メモリの予約可能な最大サイズであり、Ｄは予約しようとしている前記共有メモリの前記所望のサイズでありえる。
【００１４】
また、前記方法及び装置は、好ましくは前記算出したレベルと関連する前記エントリのうち、関連する前記共有メモリの１つ以上のセグメントが予約可能であることを示す状態情報を有する１つのエントリを選択する。前記方法及び装置は、更に、前記選択したエントリの系列にある１つ以上の上位レベルのエントリを評価して、前記上位レベルのエントリが、関連する前記共有メモリのセグメントが予約可能であることを示す状態情報を有するかどうかを判定する。この機能は、好ましくは、前記系列にある上位レベルのエントリのうちの１つの状態情報が前記共有メモリの前記関連するセグメントが予約可能であることを示すまで、前記上位レベルのエントリについて順次繰り返される。
【００１５】
前記系列にある前記上位レベルの１つ以上のエントリが、前記共有メモリの前記関連するセグメントが予約可能ではないことを示す状態情報を有することが、前記判定により示される場合、前記算出したレベルと関連する前記エントリのうちの別のエントリが選択される。
【００１６】
前記評価は、現在のエントリの状態情報が、前記現在のエントリと関連する前記共有メモリの全てのセグメントが予約可能であることを示す場合に、前記系列にある連続する上位レベルのエントリの前記評価を継続することを含みうる。前記評価は、前記現在のエントリの前記状態情報が、前記ＭＡＴ内の下位レベルのエントリと関連する１つ以上のメモリセグメントに対して以前に予約が行われているが、前記現在のエントリと関連する全てのメモリセグメントが予約されているわけではないことを示すまで、好ましくは繰り返される。
【００１７】
評価した全エントリの状態情報は、好ましくは、（ｉ）評価した全エントリの状態情報が、前記評価した個々のエントリと関連する前記共有メモリの全てのセグメントが予約可能であることを示し、かつ（ｉｉ）前記逐次的な評価を終了する前に前記ＭＡＴの最上位レベルのエントリに到達した、場合に変更される。例えば、評価した各エントリの前記状態情報は、前記ＭＡＴ内の下位レベルのエントリと関連する１つ以上のメモリセグメントに対して以前に予約が行われているが、前記現在のエントリと関連する全てのメモリセグメントが予約されているわけではないことを示すために変更される。
【００１８】
前記系列にある現在の上位レベルのエントリの状態情報の前記評価により、前記現在のエントリと関連する前記共有メモリの全てのセグメントが予約されていることが示される場合に、前記ＭＡＴの前記仮に選択したエントリが破棄されうる。この場合、前記算出したレベルにおいて、前記仮に選択したエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示す状態情報を有する別のエントリが仮に選択される。その後、前記仮に選択した別のエントリの系列にある１つ以上の上位レベルのエントリの状態情報の評価が実行され、前記状態情報が、前記仮に選択した別のエントリと関連する前記共有メモリの前記１つ以上のセグメントが予約可能であることを示すかどうかが判定されうる。
【発明の効果】
【００１９】
添付の図面を参照しつつ、ここに記載する本発明の説明を読めば、他の態様、特徴及び利点等は当業者に自明となるであろう。
【００２０】
本発明を説明するために、現在の好ましい形態を図面の形式に示すが、本発明は図示したとおりの構成ならびに手段に限定されないことを理解されたい。
【発明を実施するための最良の形態】
【００２１】
図面において、同一の要素は同じ参照符号によって参照される。本発明の１つ以上の特徴を実行するために適しうる処理システム１００の少なくとも一部が図１に示される。簡潔を期すと共に明確になるように、図１のブロック図は装置１００を例示するものとして本明細書において参照かつ記載される。しかし、この記載は同等の効力（force）を有する方法のさまざまな態様に容易に適用できることを理解されたい。
【００２２】
処理システム１００は、複数のプロセッサ１０２Ａ，１０２Ｂ，１０２Ｃ，１０２Ｄを備えるが、本発明の趣旨ならびに範囲から逸脱することなく、任意の数のプロセッサを使用できることが理解されよう。また、処理システム１００は、複数のローカルメモリ１０４Ａ，１０４Ｂ，１０４Ｃ，１０４Ｄと共有メモリ１０６を備える。少なくともプロセッサ１０２、ローカルメモリ１０４及び共有メモリ１０６は、好ましくは、適切なプロトコルに従って各構成要素間でデータを転送するように動作可能であるバスシステム１０８を介して（直接的又は間接的に）互いに結合されている。
【００２３】
各プロセッサ１０２は構成が同じであっても、構成が異っていてもよい。プロセッサは、共有（システム）メモリ１０６からデータを要求し、このデータを操作して所望の結果を得ることができる公知の技術であればいずれを利用しても実装することができる。例えば、プロセッサ１０２は、通常のマイクロプロセッサ、分散型マイクロプロセッサなど、ソフトウェア及び／又はファームウェアを実行することができる公知のマイクロプロセッサのいずれかを利用して実装することができる。例えば、プロセッサ１０２の１つ以上は、グレースケール情報、色情報、テクスチャデータ、ポリゴン情報、ビデオフレーム情報等を含むピクセルデータなどのデータを要求して操作することができるグラフィックプロセッサでありえる。
【００２４】
システム１００のプロセッサ１０２の１つ以上は、メイン（又は管理）プロセッサとしての役割を担いうる。メインプロセッサは、他のプロセッサによるデータの処理をスケジューリングし調整を行う。
【００２５】
システムメモリ１０６は、好ましくはメモリインターフェース回路（図示せず）を介してプロセッサ１０２に結合されたダイナミックランダムアクセスメモリ（ＤＲＡＭ）である。好ましくは、システムメモリ１０６はＤＲＡＭであるが、メモリ１０６は例えば、スタティックランダムアクセスメモリ（ＳＲＡＭ：Static Random Access Memory）、磁気ランダムアクセスメモリ（ＭＲＡＭ：Magnetic Random Access Memory）、光メモリ、ホログラフィックメモリなどとして、他の方法を用いて実装されうる。
【００２６】
各プロセッサ１０２は、好ましくはプロセッサコアと、内部でプログラムを実行するための関連するローカルメモリ１０４を有する。これらの構成要素は、設計者の希望に合わせて、共通の半導体基板に一体的に配置されても、別個に配置されてもよい。プロセッサコアは、好ましくは、論理命令がパイプライン式で処理される、プロセッシングパイプラインを用いて実装される。パイプラインは命令が処理される任意の数のステージに分けられうるが、一般にパイプラインは１つ以上の命令のフェッチ、命令のデコード、命令間の依存性チェック、命令の発行、及び、命令の実行ステップを有している。これに関連して、プロセッサコアは命令バッファ、命令デコード回路、依存性チェック回路、及び命令発行回路、を有する。
【００２７】
各ローカルメモリ１０４は、バスを介して関連するプロセッサコア１０２に結合されており、好ましくは、そのプロセッサコアと同じチップ（同じ半導体基板）に配置される。ローカルメモリ１０４は、ハードウェアキャッシュメモリ機能を実装するためのオンチップ又はオフチップのハードウェアキャッシュ回路、キャッシュレジスタ、キャッシュメモリコントローラなどが存在しないという点で、好ましくは従来のハードウェアキャッシュメモリでない。チップ上のスペースには限りがあることが多いため、ローカルメモリは共有メモリ１０６よりも相当サイズが小さいことがある。
【００２８】
プロセッサ１０２は、好ましくは、プログラムを実行したりデータを操作するために、バス１０８経由でシステムメモリ１０６からそれぞれのローカルメモリ１０４にデータ（プログラムデータを含みうる）をコピーするため、データアクセスリクエストを出す。データアクセスを容易にするためのメカニズムは、ＤＭＡ法などの公知の技術のいずれかを用いて実装されうる。この機能は、好ましくはメモリインタフェース回路によって実行される。
【００２９】
図２を参照すると、共有メモリ１０６は、１つ以上の下位領域１０６Ａ，１０６Ｂ，１０６Ｃ等を有しうる。領域のうちの１つである１０６Ｃは、共有メモリにあるデータ間のコヒーレンシの維持に有用な相互排除オブジェクト（ミューテックスオブジェクト）を作成するなどの、オブジェクト指向インタフェースのアクティビティのために予約されうる。例えば、ミューテックスオブジェクトは、プロセッサ１０２のうちの１つしかこのオブジェクトを予約できないようにする２値セマフォなどのセマフォ１０６Ｄでありえる。ミューテックスオブジェクトを管理するための従来の技術では、ミューテックスオブジェクトを確立するための一方的権限を有する管理プロセッサを用いるが、本発明は、管理プロセッサ、又は複数のプロセッサ１０２による管理のいずれによっても使用できる代替の技術を提供する。
【００３０】
図３を参照すると、ミューテックスオブジェクトの作成を管理するために、メモリ割当てテーブル（ＭＡＴ）が好ましくは使用される。１つ以上のプロセッサ１０２が予約することができる共有メモリ１０６の各セグメントにより（by way of）、１つ以上のミューテックスオブジェクトが確立されうる。共有メモリ１０６の１つ以上のセグメントをこのように予約することにより、コヒーレンシの必要条件を満たすために必要な場合、予約されたセグメントにある任意のデータが保護されることが保証される。ＭＡＴ１１０は、好ましくは（説明のため、１，２，３，．．．，１５の番号を付した）複数のエントリと各エントリに対する状態情報を含む一次元のテーブルである。ＭＡＴ１１０の各エントリは、好ましくは共有メモリ１０６の１つ以上のセグメントと関連しており、各セグメントは、プロセッサ１０２の１つ以上によって個別に又は一括して予約されうる。
【００３１】
図４を参照すると、状態情報は、Ｉ＝予約可能なセグメント、Ｎ＝少なくとも一部が予約されたセグメント、Ｕ＝予約されたセグメント、Ｃ＝続きのセグメント、などの複数の状態のうちの少なくとも１つをとることができる。これらの状態の各々については、下記に以下で更に詳細に後述する。しかし、現時点では、各状態情報は図４の真理値表に示すように好ましくは２進数形式で表されることに留意されたい。好ましくは、ＭＡＴ１１０の各エントリは、初期化状態ではＩの状態情報をとっており、関連するセグメントが予約可能となっている。この初期化処理は、プロセッサ１０２のうちの１つによって実行されても、メインプロセッサによって実行されてもよい。
【００３２】
ＭＡＴ１１０は、共有メモリ１０６のミューテックスオブジェクトの管理を実現するために極端に多量のデータを有する必要がないという点に留意されたい。実際、各エントリは、所定のエントリの状態を表す、２ビットなどの比較的少ないビット数のみを有していればよい。この為、ＭＡＴ１１０は、例えば共有メモリ１０６の一部などの記憶媒体の相当量のスペースを使用する必要がない。ＭＡＴ１１０を完全に定義するために必要とされるビット数が比較的少ないことにより、１回のＤＭＡ転送において、全ＭＡＴ１１０が共有メモリ１０６とプロセッサの間で転送できるようになり、有利である。割当てテーブルを確立するための従来技術では、テーブルのサイズが非常に大きくなり、これを１回のＤＭＡサイクルにおいて転送できる可能性が低いことを当業者は理解するであろう。
【００３３】
図５を参照すると、ＭＡＴ１１０の各エントリとバイナリツリーの各ノードが、レベル０、レベル１、レベル２、レベル３の階層的なレベルにグループ分けされるように、エントリは好ましくはノードと関連している。ルートノードであるノード１は、レベル０（バイナリツリーの最上位）にあり、共有メモリの最大割当てスペースを表している。この最大割当てスペースは、共有ヒープとも呼ばれることがある。ノード１は、ＭＡＴ１１０のエントリ１と関連している。ノード１に従属する中間ノード２，３は、ＭＡＴ１１０のエントリ２，３とそれぞれ関連している。ノード２，３はレベル１にあり、各ノードは最大割当てスペースの１／２（本例では共有メモリ１０６の４つのセグメント）を表している。ノード２に従属している中間ノード４，５と、ノード３に従属している中間ノード６，７は、ＭＡＴ１１０のエントリ４，５，６，７とそれぞれ関連している。これらのノードの各々は、最大割当てスペースの１／４（本例では共有メモリ１０６の２つのセグメント）を表している。
【００３４】
バイナリツリーに４レベルしかないと仮定すると、ノード８〜１５は終端ノードであり、これ以上の従属ノードが存在しない。終端ノード８，９はノード４に従属し、終端ノード１０，１１はノード５に従属し、終端ノード１２，１３はノード６に従属し、終端ノード１４，１５はノード７に従属している。これらのノードの各々は、ＭＡＴ１１０のエントリ８，９，１０，１１，１２，１３，１４，１５とそれぞれ関連している。これらのノードの各々は、最大割当てスペースの１／８（本例では共有メモリ１０６の１つのセグメント）を表している。
【００３５】
上の例をそのまま使用すると共に、例えば最大割当てサイズが８ＫＢであるとすると、各終端ノード（例えばノード８〜１５）は、予約（又は割当て）可能な共有メモリ１０６の１ＫＢのセグメントを表しており、割当ての粒度が１ＫＢということになる。この為、ＭＡＴ１１０のサイズは、ノード（エントリ）の数に、各エントリの状態情報を表しているビット数を掛けた値にほぼ等しい。ノード（エントリ）の数は、次式：２Ｌ−１（Ｌは、バイナリツリーにあるレベルの数）を用いて算出することができる。この為、ここまで説明した例では、ＭＡＴ１１０のサイズは、１５×２＝３０ビットとなる。
【００３６】
次に図６を参照すると、これは、ＭＡＴ１１０を使用して共有メモリ１０６内でミューテックスオブジェクトを管理するために、プロセッサ１０２の１つ以上によって実行されうる処理ステップを例示しているフローチャートである。例えば、ここでは、共有メモリ１０６のセグメントを使用した、数多くの２値セマフォの作成について説明する。アクション３００において、ＭＡＴ１１０が、好ましくは共有メモリ１０６などの記憶媒体から、プロセッサ１０２のうちの１つ（そのローカルメモリ１０４など）に読み出される。アクション３０２において、２値セマフォの作成先となるメモリの所望部分のサイズが、バイナリツリー内のレベル（つまりＭＡＴ１１０内でのレベル）に変換される。ＭＡＴ１１０のレベルは、次式：レベル＝ｌｏｇ２（Ｍ／Ｄ）に基づいて算出されることが好ましく、上記式において、Ｍは、共有メモリの予約可能な最大サイズ（最大割当てスペース）、Ｄは、予約しようとしている共有メモリの所望のサイズ（例えばセマフォのサイズ）である。上記の例のパラメータを使用すると、説明のために、使用可能スペースの最大サイズＭが８ＫＢであり、セマフォの所望のサイズＤが１ＫＢ（すなわち共有メモリ１０６の１つのセグメント）であるとする。このため、レベル＝Ｌｏｇ２（８ＫＢ／１ＫＢ）＝Ｌｏｇ２(８)＝３となる。
【００３７】
アクション３０４において、１つのエントリをそこから選択するエントリのグループを作成するために、算出したＭＡＴ１１０のレベルを、ＭＡＴ１１０の多数のエントリと関連させる。図５を参照すると、レベル３と関連しているノードは、ノード８〜１５である。算出して求めたレベル３と関連しているＭＡＴ１１０内のエントリのグループは、エントリ８〜１５を含む。これらのエントリのうちの１つが、その状態情報に基づいて選択される。詳細には、グループ内のエントリのうち選択されるエントリは、その選択したエントリと関連している共有メモリ１０６の１つ以上のセグメントが予約可能であることを示す状態情報を有するエントリである。ＭＡＴ１１０は初期化状態であると仮定したので（図３）、エントリ８〜１５のいずれも選択することができる。実際、これらのエントリの各々に関連する状態情報はＩであり、このため、各エントリに関連するセグメントが予約可能である。グループのエントリのうちの１つを選択するのに有用な方式であれば、どのようなものであっても本発明の趣旨及び範囲から逸脱することなく使用できることに留意されたい。例えば、グループのエントリの逐次的な走査を行って、最初にみつかった状態情報がＩのエントリを選択してもよい。
【００３８】
グループから１つのエントリを選択することは、更に処理を行ってからこの選択を確定し、共有メモリ１０６の関連するセグメントを予約するという点で、暫定的な選択に過ぎないことが好ましい。説明のため、エントリ８が、グループにおいて、関連するセグメントが予約可能であることを示す状態情報を含む最初のエントリであるため、これが仮に選択されるとする。アクション３０６において、仮に選択したエントリ８の系列（lineage）が、これに関連するセグメントが実際に予約可能であるかどうかを判定するために調べられる。より詳細には、この際、仮に選択したエントリ８の系列にある１つ以上の上位エントリの状態情報が評価され、この上位エントリの状態情報が、仮に選択したエントリ８に関連するセグメントが予約可能であることを示しているかどうかが判定される。
【００３９】
図５を参照すると、ノード８の次の上位ノード（親ノード）はノード４であり、このノードはレベル２にある。この為、ＭＡＴ１１０においてエントリ８の次の上位エントリは、エントリ４となる。親エントリは、ＭＡＴ１１０の任意のエントリから、次式：親ノード＝ＩＮＴＥＧＥＲ（現在のノード／２）に従って数学的に算出することができる。ＭＡＴ１１０のエントリ４の状態情報が、好ましくは評価される。図３を参照すると、ノード４の状態情報はＩであり、このため、エントリ４に関連するセグメント（すなわちエントリ８，９に関連するセグメント）が予約可能であることを示している。この状況では最終的な判定を行うことができないので、この評価は、連続する上位レベルで好ましくは続行される。
【００４０】
図５を参照すると、ノード４の次の上位ノード（親ノード）はノード２であり、このノードはレベル１にある。エントリ４の親エントリは、ＩＮＴＥＧＥＲ（４／２）＝エントリ２である。図３を参照すると、ノード２の状態情報はＩであり、このため、エントリ２に関連するセグメント（すなわちエントリ８〜１１に関連するセグメント）が予約可能であることを示している。この場合も、この状況では最終的な判定を行うことができないので、この評価は、連続する上位レベルで好ましくは続行される。
【００４１】
図５を参照すると、ノード２の次の上位ノードである親ノードはノード１であり、このノードはレベル０にある。エントリ２の親エントリは、ＩＮＴＥＧＥＲ（２／２）＝エントリ１である。図３を参照すると、ノード１の状態情報はＩであり、このため、エントリ１に関連するセグメント（すなわちエントリ８〜１５に関連するセグメント、すなわち全セグメント）が予約可能であることを示している。ＭＡＴ１１０のエントリ８の系列にはこれより上位のエントリがないため、好ましくは評価が終了する。この状況では、エントリ８が選択され、エントリ８に関連する共有メモリ１０６のセグメントが選択され予約されうる。
【００４２】
図７を参照すると、ミューテックスオブジェクトのその後の管理と更に別のセマフォの作成を容易にするために、ＭＡＴ１１０は、ＭＡＴ１１０のエントリ８と関連して予約される共有メモリ１０６のセグメントの予約に関して行われたアクションの特定の形態を記録するために、好ましくは変更される。より詳細には、ＭＡＴ１１０のエントリ８の状態情報は、好ましくはＩからＵに変更され、エントリ８に関連する共有メモリ１０６のセグメントが既に予約されていることを示すようになる。更に、エントリ８の系列にある上位エントリの評価が最上位エントリであるエントリ１（バイナリツリーのルートノード１に対応する）に達したため、好ましくはＭＡＴ１１０が更に変更される。より詳細には、エントリ８の系列の各エントリ（本例ではエントリ４，２，１）の状態情報が好ましくはＩからＮに変更され、これらエントリに関連するセグメントのうちの少なくとも１つが既に予約されていることを示すようになる。エントリ４，２，１の状態を変更することの意味は、更に別のセグメントの予約と関連して以下で更に詳細に後述する。
【００４３】
図７〜８を参照すると、共有メモリ１０６からＭＡＴ１１０を読み出し、予約しようとしているメモリの所望の部分のサイズに対応するレベルを算出して、この算出して求めたレベルと関連するＭＡＴ１１０のエントリのグループを決定する（establish）ことによって、サイズ１ＫＢの別のセマフォが作成されうる。この例では、算出したレベルは、Ｌ＝Ｌｏｇ２（８ＫＢ／１ＫＢ）＝３となる。レベル３と関連するＭＡＴ１１０のエントリのグループは、エントリ８〜１５を含む。エントリ８〜１５を逐次的に評価した結果（図７を参照）、エントリ９が、このエントリに関連するセグメントが予約可能であることを示すＩの状態を有することがわかる。次に、エントリ９の系列にある上位エントリの状態情報が評価される。より詳細には、エントリ９の親エントリが、親エントリ＝ＩＮＴＥＧＥＲ（９／２）＝４と算出される。エントリ４の状態情報が評価されてＮであることがわかり、エントリ４に関連する下位レベルのエントリに関連するセグメントのうちの少なくとも１つが既に予約されているが、エントリ４に関連するメモリセグメントが全て予約されているわけではないことを示す。この状況では、系列にある上位エントリの評価が終了されうる。これは、状態Ｎが最初にみつかったことで、仮に選択したエントリ９に関連する共有メモリ１０６のセグメントが予約可能であることが保証されるためである。これを受けて、エントリ９に関連する状態情報が、エントリ９に関連する共有メモリ１０６のセグメントが既に予約されていることを示すＩからＵに変更される（図８を参照）。その後、ＭＡＴ１１０が、好ましくは共有メモリ１０６に書き戻される。
【００４４】
図８〜９を参照すると、共有メモリ１０６からＭＡＴ１１０を読み出し、予約しようとしているメモリの所望の部分のサイズに対応するレベルを算出して、この算出して求めたレベルと関連するＭＡＴ１１０のエントリのグループを決定する（establish）ことによって、例えばサイズ２ＫＢの別のセマフォが作成されうる。この例では、算出したレベルは、Ｌ＝Ｌｏｇ２（８ＫＢ／２ＫＢ）＝２となる。レベル２と関連するＭＡＴ１１０のエントリのグループは、エントリ４，５，６，７を含む。エントリ４，５，６，７を逐次的に評価した結果（図８を参照）、エントリ５が、このエントリに関連するセグメントが予約可能であることを示すＩの状態を有することがわかる。次に、エントリ５の系列にある上位エントリの状態情報が評価される。より詳細には、エントリ５の親エントリが、親エントリ＝ＩＮＴＥＧＥＲ（５／２）＝２と算出される。エントリ２の状態情報が評価されてＮであることがわかり、エントリ２に関連する下位レベルのエントリに関連するセグメントのうちの少なくとも１つが既に予約されているが、エントリ２に関連するメモリセグメントが全て予約されているわけではないことを示す。この状況では、系列にある上位エントリの評価が終了されうる。この場合も、これは、状態Ｎが最初にみつかったことで、仮に選択したエントリ５に関連する共有メモリ１０６のセグメントが予約可能であることが保証されるためである。これを受けて、エントリ５に関連する状態情報が、エントリ９に関連する共有メモリ１０６のセグメントが既に予約されていることを示すＩからＵに変更される（図９を参照）。その後、ＭＡＴ１１０が共有メモリ１０６に書き戻される。
【００４５】
図５を参照すると、前述の例の議論では、予約可能な最大メモリサイズ（例えば共有ヒープサイズ）が２のべき乗であると仮定した。この為、最下位にある各終端ノード（ノード８〜１５）は、共有メモリ１０６の個々のセグメントと関連していた。しかし、一般に、共有ヒープのサイズは２の倍数ではなく、このため、バイナリツリーの終端ノードの１つ以上（及びＭＡＴ１１０のエントリの１つ以上）が、共有メモリ１０６のセグメントと関連しないことがある。例えば、共有ヒープのサイズが７個のセグメントのみを含み、ノード／エントリ１５が、共有ヒープのセグメントと関連していないことがある。この場合、ＭＡＴ１１０のエントリは、好ましくはノード１５が共有ヒープのセグメントと関連していないことを示す。
【００４６】
エントリ１５と関連する共有メモリのセグメントが存在しないことを反映するようにＭＡＴ１１０が変更されうる。エントリ１５が、「仮に」選択されうる。ＭＡＴ１１０のエントリ１５の次の上位エントリは、親ノード＝ＩＮＴＥＧＥＲ（１５／２）＝エントリ７である。ＭＡＴ１１０のエントリ７の状態情報が、好ましくは評価される。図９を参照すると、エントリ７の状態情報はＩであり、このエントリに関連するセグメント（すなわちエントリ１４，１５に関連するセグメント）が予約可能であることを示している。エントリ７がＵ又はＮの状態を有さなかったので、この評価は、連続する上位レベルで好ましくは続行される。エントリ７の親エントリは、ＩＮＴＥＧＥＲ（７／２）＝エントリ３である。エントリ７の状態情報はＩであり、このエントリに関連するセグメント（すなわちエントリ６〜７に関連するセグメント）が予約可能であることを示している。この場合も、エントリ３がＵ又はＮの状態を有さなかったので、この評価は、連続する上位レベルで好ましくは続行される。エントリ３の親エントリは、ＩＮＴＥＧＥＲ（３／２）＝エントリ１である。エントリ１の状態情報はＮであり、エントリ１に関連するセグメントのうちの１つ以上が既に予約されているが、このようなセグメントが全て予約されているわけではないことを示している。親エントリ（エントリ１）の状態がＮである（ルートノードであった）ため、評価は好ましくは終了する。
【００４７】
ＭＡＴ１１０のエントリ１５の状態情報は好ましくはＩからＵに変更され（図１０を参照）、これにより、エントリ１５が暫定的な選択にも最終的な選択にも使用できないことが保証される。更に、エントリ１５の系列にある上位エントリの評価が、最上位エントリであるエントリ１（バイナリツリーのルートノード１に対応する）に達したため、エントリ１５の系列内の各エントリであるエントリ７，３の状態情報が、好ましくはＩからＮに変更され、これらエントリと付けられているセグメントのうちの少なくとも１つが既に予約されていることを示すようになる。
【００４８】
図１０〜１１を参照すると、共有メモリ１０６からＭＡＴ１１０を読み出し、予約しようとしているメモリの所望の部分のサイズに対応するレベルを算出して、この算出して求めたレベルと関連するＭＡＴ１１０のエントリのグループを決定する（establish）ことによって、サイズ１ＫＢの別のセマフォが作成されうる。この例では、算出したレベルは、Ｌ＝Ｌｏｇ２（８ＫＢ／１ＫＢ）＝３となる。レベル３と関連するＭＡＴ１１０のエントリのグループは、エントリ８〜１５を含む。エントリ８〜１５を逐次的に評価した結果（図１０を参照）、エントリ１０が、このエントリに関連するセグメントが予約可能であることを示すＩの状態を有することがわかる。次に、エントリ１０の系列にある上位エントリの状態情報が評価される。より詳細には、エントリ１０の親エントリが、親エントリ＝ＩＮＴＥＧＥＲ（１０／２）＝５と算出される。エントリ２の状態情報が評価されてＵであることがわかり、エントリ１０及び１１に関連するセグメントが既に予約されていることを示す。
【００４９】
この為、グループの別のエントリ（エントリ１１など）が仮に選択される。これも同じ結果となり、親エントリ５の状態はＵとなる。この為、グループの更に別のエントリ（エントリ１２など）が仮に選択される。この親エントリは、ＩＮＴＥＧＥＲ（１２／２）＝６である。エントリ６の状態情報が評価されてＮであることがわかり、エントリ６に関連する下位レベルのエントリに関連するセグメントのうちの少なくとも１つが既に予約されているが、エントリ６に関連するメモリセグメントが全て予約されているわけではないことを示す。状態Ｎが最初にみつかったことで、仮に選択したエントリ１２に関連する共有メモリ１０６のセグメントが予約可能であることが確実となり、系列にある上位エントリの評価が終了されうる。次に、エントリ１２に関連する状態情報が、エントリ１２に関連する共有メモリ１０６のセグメントが既に予約されていることを示すＩからＵに変更される（図１１を参照）。その後、ＭＡＴ１１０が、好ましくは共有メモリ１０６に書き戻される。
【００５０】
図１１〜１２を参照すると、例えば、２ＫＢのサイズの別のセマフォを作成することが望ましいことがある。上の例をそのまま使用すると、予約可能な共有メモリ１０６のセグメントは２つ（すなわち、ＭＡＴ１１０のエントリ１０，１１に関連するセグメント）しかない。しかし、これらのセグメントを予約するために、追加の処理手法が好ましくは使用される点に留意されたい。これは、図１１〜１２に示した状況では、上で説明した２ＫＢのサイズのセマフォを予約する手法では、不十分（imcomplete）となってしまうためである。より詳細には、算出したレベルは、Ｌ＝Ｌｏｇ２（８ＫＢ／２ＫＢ）＝２となる。レベル２と関連するＭＡＴ１１０のエントリのグループは、エントリ４，５，６，７を含む。エントリ４，５，６，７を逐次的に評価した結果（図１１を参照）、このエントリに関連するセグメントが予約可能であることを示すＩの状態を含むエントリが存在しないことがわかる。この為、状態がＮのエントリが好ましくは更に評価されて、その系列にある下位レベルのエントリ（子エントリ）のいずれかの状態がＩであり、これらのエントリが互いに隣接しているかどうかが判定される。このグループで状態がＮの最初のエントリは、エントリ４である。エントリ４の子エントリは、４×２＝８、４×２＋１＝９であると求められる。エントリ８及び９は、いずれも状態がＵである。この為、グループの他のエントリが仮に選択される。このグループで状態がＮの２番目のエントリは、エントリ６である。エントリ６の子エントリは、６×２＝１２、６×２＋１＝１３であると求められる。エントリ１２の状態はＵであるが、エントリ１３の状態はＩである。この為、エントリ１３が予約の候補となりえる。次に、グループの別のエントリが仮に選択される。このグループで状態がＮの３番目のエントリは、エントリ７である。エントリ７の子エントリは、７×２＝１４、７×２＋１＝１５であると求められる。エントリ１５の状態はＵであるが、エントリ１４の状態はＩである。この為、エントリ１４が予約の候補となりえる。次に、２つの候補エントリ（エントリ１３及びエントリ１４）が互いに隣接しているかどうかが判定され、両者は隣接している。この為、更なるエントリの評価が終了されうる。エントリ１３，１４に関連する状態情報がＩからＵとＣにそれぞれ変更される（図１２を参照）。前述の例と同様に、エントリ１３のＵの状態は、エントリ１３に関連する共有メモリ１０６のセグメントが既に予約されていることを示している。エントリ１４のＣの状態は、エントリ１４に関連する共有メモリ１０６のセグメントが既に予約されているが、このセグメントがエントリ１３のセグメントと関連していることも示している。
【００５１】
本発明の１つ以上の更なる実施形態によれば、図１３を参照すると、ＭＡＴ１１０が定義する予約されたオブジェクトは、好ましくはシステムの複数のプロセッサの間で共有される。図１３は、予約されたオブジェクトをシステムのプロセッサ間で共有するために、図１（又はその別の実施形態）のマルチプロセシングシステムにおいて実装されうるキーテーブル１１２の構造を例示しているブロック図である。キーテーブル１１２は、複数のエントリを有し、各エントリは、オブジェクト名、オブジェクト０、オブジェクト１、オブジェクト２、．．．、オブジェクトＮと、共有メモリ１０６の下にあるセグメントを予約するために選択した関連するノードとを含む。（ノード１５を予約可能とする点を除き）図１２のＭＡＴ１１０を例に用いると、対応するキーテーブル１１２は、図１３に示すエントリを含みうる。より詳細には、オブジェクト０は、共有メモリのノード８が予約された共有オブジェクトの名前である。同様に、オブジェクト１は、共有メモリ１０６のノード９が予約された共有オブジェクトの名前である。予約されたオブジェクトをマルチプロセシングシステム１００のプロセッサ１０２間で共有するために、キーテーブル１１２は、追加オブジェクトを作成すると共に、既存のオブジェクトを使用するために、好ましくはＭＡＴ１１０と併用される。
【００５２】
図１４は、予約されたオブジェクトを、例えばシステム１００のプロセッサ１０２間で共有するために、本明細書に記載の実施形態によって使用されうる処理ステップを例示しているフローチャートである。アクション４００において、ＭＡＴ１１０が共有メモリ１０６内でロックされ、ＭＡＴ１１０がアンロックされるまで、共有メモリ１０６からＭＡＴ１１０を読み出したプロセッサ１０２しかＭＡＴ１１０を操作することができなくなる。この為、ＭＡＴ１１０がロックされている間は、ほかのプロセッサ１０２がＭＡＴ１１０にアクセスすることはできない。アクション４０２において、キーテーブル１１２がロックされ、共有メモリ１０６からＭＡＴ１１０を読み出したプロセッサ１０２に読み出される。
【００５３】
アクション４０４において、所望のオブジェクトが既に予約されているかどうかが判定される。このとき、好ましくはキーテーブル１１２内でオブジェクト名が調べらて、任意の関連ノードが既に予約されているかどうかが判定される。例えば、所定のプロセッサ１０２（またはタスク）がオブジェクト２を使用しようとしている場合、そのプロセッサは、このオブジェクト名を使用してキーテーブル１１２内でこの名前を検索し、関連するノード名を調べて、共有メモリ１０６のいずれかのノード（またはセグメント）が既に予約されているかどうかを判定する。この例では、ノード５がオブジェクト２に対して既に予約されている。ノード５が予約されている場合、下位レベルにおいてノード５と関連しているノード１０，１１も含まれうる点に注目されたい。アクション４０４の判定結果が「Ｙ」の場合、手順フローは好ましくはアクション４１０に進み、ＭＡＴ１１０とキーテーブル１１２が、共有メモリ１０６に書き込まれて、アンロックされる。その後、オブジェクト２を使用しようとするプロセッサは、共有メモリ１０６のノード５，１０，１１に関連するセグメントを使用することにより、これを使用することができる。
【００５４】
一方、アクション４０４の判定結果が「Ｎ」の場合、手順フローは好ましくはアクション４０６に進み、図６のアクション３０２〜３０８が実行される。言い換えれば、共有メモリ１０６の更に別のノード／セグメントを予約することによって新しいオブジェクトが作成される。アクション４０８において、図６のアクション３０２〜３０８で実行したノードとメモリセグメントの予約を反映するためにキーテーブル１１２が変更される。例えば、このようなアクションの結果、新しいオブジェクト５が作成され、このときノード１５（及びノード１５と関連するメモリセグメント）が予約されうる。この為、オブジェクト５がノード１５と関連していることを示すために、キーテーブル１１２が好ましくは更新される。次に手順フローはアクション４１０に進み、ＭＡＴ１１０とキーテーブル１１２が共有メモリ１０６に書き戻されて、アンロックされる。
【００５５】
以下に本明細書で説明している１つ以上の特徴を実行するのに適した、マルチプロセッサシステムのための好ましいコンピュータアーキテクチャを説明する。１つ以上の実施形態によれば、マルチプロセッサシステムは、ゲームシステム、家庭用端末、ＰＣシステム、サーバーシステム、及びワークステーションなどのメディアリッチアプリケーションを、スタンドアローン処理、及び／又は分散処理するために動作することができる、シングルチップソリューションとして実装されうる。ゲームシステムや家庭用端末などのいくつかのアプリケーションでは、リアルタイムの演算処理は必須である。例えば、リアルタイムの分散ゲームアプリケーションでは、ユーザーにリアルタイムの経験をしていると思わせる程速く、１つ以上のネットワークイメージの復元、３Ｄコンピュータグラフィック、オーディオ生成、ネットワーク通信、物理的シミュレーション、及び人工知能処理が実行される必要がある。従って、マルチプロセッサシステムの各プロセッサは、短時間で、かつ予測可能時間でタスクを完了する必要がある。
【００５６】
このために、また、本コンピュータアーキテクチャによれば、マルチプロセッシングコンピュータシステムの全プロセッサは、共通の演算モジュール（あるいはセル）から構成される。この共通の演算モジュールは、構造が一貫しており、また好ましくは、同じ命令セットアーキテクチャを採用している。マルチプロセッシングコンピュータシステムは、１つ以上のクライアント、サーバー、ＰＣ、モバイルコンピュータ、ゲームマシン、ＰＤＡ、セットトップボックス、電気器具、デジタルテレビ、及びコンピュータプロセッサを使用する他のデバイスから形成されうる。
【００５７】
複数のコンピュータシステムもまた、所望に応じてネットワークのメンバーとなりうる。一貫モジュール構造により、マルチプロセッシングコンピュータシステムによるアプリケーション及びデータの効率的高速処理が可能になる。またネットワークが採用される場合は、ネットワーク上にアプリケーション及びデータの高速送信が可能にする。この構造はまた、大きさや処理能力が様々なネットワークのメンバーの構築を単純化し、また、これらのメンバーが処理するアプリケーションの準備を単純化する。
【００５８】
図１５を参照すると、基本的な処理モジュールはプロセッサエレメント（ＰＥ）５００である。ＰＥ５００はＩ／Ｏインターフェース５０２、プロセッシングユニット（ＰＵ）５０４、及び複数のサブプロセッシングユニット５０８、すなわち、サブプロセッシングユニット５０８Ａ、サブプロセッシングユニット５０８Ｂ、サブプロセッシングユニット５０８Ｃ、及びサブプロセッシングユニット５０８Ｄを備えている。なお、好適には、ＰＵとしてパワーＰＣ（ＰＰＥ:Power PC Element）を、ＳＰＵとしてシナジスティックプロセッシングエレメント（ＳＰＥ:Synergistic Processing Element）を用いる。ローカル（あるいは内部）ＰＥバス５１２は、データ及びアプリケーションを、ＰＵ５０４、サブプロセッシングユニット５０８、及びメモリインターフェース５１１間に送信する。ローカルＰＥバス５１２は、例えば従来のアーキテクチャを備えることができ、又は、パケット−スイッチネットワークとして実装されうる。パケットスイッチネットワークとして実装される場合は、更なるハードウェアが必要であるものの、利用可能な帯域幅を増やす。
【００５９】
ＰＥ５００はデジタル論理回路を実装するよう様々な方法を用いて構成されうる。しかしながら、好ましくは、ＰＥ５００はＳＯＩ基板を用いた集積回路として構成でき、あるいは、シリコン基板に相補性金属酸化膜半導体（ＣＭＯＳ：Complementary Metal Oxide Semiconductor）を用いた単一の集積回路とすることも好適な構成である。基板の他の材料には、ガリウムヒ素、ガリウムアルミウムヒ素、及び、様々なドーパントを採用している他の、いわゆる、ＩＩＩ−Ｂ化合物を含む。ＰＥ５００はまた、高速単一磁束量子（ＲＳＦＱ：Rapid Single-flux-Quantum）論理回路などの超電導デバイスを用いて実装されうる。
【００６０】
ＰＥ５００は高帯域のメモリ接続５１６を介して、共有（メイン）メモリ５１４と密接に結合するよう構成できる。なお、メモリ５１４をオンチップ化してもよい。好ましくは、メモリ５１４はダイナミックランダムアクセスメモリ（ＤＲＡＭ：Dynamic Random Access Memory）であるが、メモリ５１４は例えば、スタティックランダムアクセスメモリ（ＳＲＡＭ：Static Random Access Memory）、磁気ランダムアクセスメモリ（ＭＲＡＭ：Magnetic Random Access Memory）、光メモリ、ホログラフィックメモリなどとして、他の方法を用いて実装されうる。
【００６１】
ＰＵ５０４とサブプロセッシングユニット５０８は好ましくは、それぞれダイレクトメモリアクセス（ＤＭＡ）の機能を備えたメモリフローコントローラ（ＭＦＣ：Memory Flow Controller）と結合されており、該コントローラはメモリインターフェース５１１と共に、ＰＥ５００のＤＲＡＭ５１４とサブプロセッシングユニット５０８、ＰＵ５０４間のデータ転送を促進する。ＤＭＡＣ及び／又はメモリインターフェース５１１は、サブプロセッシングユニット５０８及びＰＵ５０４に一体化して、別個に配置されうる。更に、ＤＭＡＣの機能及び／又はメモリインターフェース５１１の機能は、１つ以上の（好ましくは全ての）サブプロセッシングユニット５０８及びＰＵ５０４に統合することができる。また、ＤＲＡＭ５１４はＰＥ５００と統合されていても、別個に配置されていてもよいことに留意されたい。例えば、ＤＲＡＭ５１４は、実例で示しているように、チップ外に配置しても、あるいは一体化してオンチップ配置としてもよい。
【００６２】
ＰＵ５０４はデータ及びアプリケーションをスタンドアローン処理できる標準プロセッサなどでありうる。作動時、ＰＵ５０４は、好ましくは、サブプロセッシングユニットによるデータ及びアプリケーション処理をスケジューリングし、調整を行う。サブプロセッシングユニットは好ましくは、単一命令複数データ（ＳＩＭＤ：Single Instruction Multiple Data）プロセッサである。ＰＵ５０４の管理下、サブプロセッシングユニットは並列で、かつ独立して、これらのデータ及びアプリケーション処理を行う。ＰＵ５０４は好ましくは、ＲＩＳＣ（Reduced Instruction Set Computing）技術を採用しているマイクロプロセッサアーキテクチャであるパワーＰＣ（ＰｏｗｅｒＰＣ）コアを用いて実装される。ＲＩＳＣは、単純な命令の組合せを用いて、より複雑な命令を実行する。従って、プロセッサのタイミングは、単純で高速の動作に基づくものであり、マイクロプロセッサがより多くの命令を所定のクロック速度で実行できるようにする。
【００６３】
ＰＵ５０４はサブプロセッシングユニット５０８により、データ及びアプリケーション処理をスケジューリングし調整を行う、メインプロセッシングユニットの役割を果たしているサブプロセッシングユニット５０８のうちの、１つのサブプロセッシングユニットにより実装されうる。更に、プロセッサエレメント５００内には１つ以上の実装されたＰＵが存在しうる。なお、オンチップのＰＵを複数設けるようにしてもよい。
【００６４】
本モジュール構造によれば、特定のコンピュータシステムにおけるＰＥ５００の数は、そのシステムが要求する処理能力に基づく。例えば、サーバーにおけるＰＥ５００の数は４、ワークステーションにおけるＰＥ５００の数は２、ＰＤＡにおけるＰＥ５００の数は１とすることができる。特定のソフトウェアセルの処理に割当てられるＰＥ５００のサブプロセッシングユニット数は、セル内のプログラムやデータの複雑度や規模により決定される。
【００６５】
図１６は、サブプロセッシングユニット（ＳＰＵ）５０８の好ましい構造および機能を例示する。ＳＰＵ５０８アーキテクチャは好ましくは、多目的プロセッサ（平均して高性能を広範なアプリケーションに実現するように設計されているもの）と、特殊目的プロセッサ（高性能を単一のアプリケーションに実現するように設計されているもの）間の間隙を埋める。ＳＰＵ５０８は、ゲームアプリケーション、メディアアプリケーション、ブロードバンドシステムなどに高性能を実現するように、また、リアルタイムアプリケーションのプログラマーに高度な制御を提供するように設計される。ＳＰＵ５０８は、グラフィックジオメトリーパイプライン、サーフェースサブディビジョン、高速フーリエ変換、画像処理キーワード、ストリームプロセッシング、ＭＰＥＧのエンコード／デコード、エンクリプション、デクリプション、デバイスドライバの拡張、モデリング、ゲーム物理学、コンテンツ制作、音響合成及び処理が可能である。
【００６６】
サブプロセッシングユニット５０８は２つの基本機能ユニットを有し、それらはＳＰＵコア５１０Ａ及びメモリフローコントローラ（ＭＦＣ）５１０Ｂである。ＳＰＵコア５１０Ａはプログラムの実行、データ操作、などを行い、一方でＭＦＣ５１０ＢはシステムのＳＰＵコア５１０ＡとＤＲＡＭ５１４の間のデータ転送に関連する関数を実施する。
【００６７】
ＳＰＵコア５１０Ａはローカルメモリ５５０、命令ユニット（ＩＵ：Instruction Unit）５５２、レジスタ５５４、１つ以上の浮動小数点実行ステージ５５６、及び１つ以上の固定小数点実行ステージ５５８を有している。ローカルメモリ５５０は好ましくは、ＳＲＡＭなどの、シングルポートのランダムメモリアクセスを用いて実装される。殆どのプロセッサはキャッシュの導入により、メモリへのレイテンシを小さくする一方で、ＳＰＵコア５１０Ａはキャッシュより小さいローカルメモリ５５０を実装している。更に、リアルタイムアプリケーション（及び本明細書に述べているように、他のアプリケーション）のプログラマーたちに一貫した、予測可能なメモリアクセスレイテンシを提供するため、ＳＰＵ５０８Ａ内のキャッシュメモリアーキテクチャは好ましくない。キャッシュメモリのキャッシュヒット／ミスという特徴のために、数サイクルから数百サイクルまでの、予測困難なメモリアクセス時間が生じる。そのような予測困難性により、例えばリアルタイムアプリケーションのプログラミングに望ましい、アクセス時間の予測可能性が低下する。ＤＭＡ転送をデータの演算処理にオーバーラップさせることで、ローカルメモリＳＲＡＭ５５０においてレイテンシの隠蔽を実現しうる。これにより、リアルタイムアプリケーションのプログラミングが制御しやすくなる。ＤＭＡの転送に関連するレイテンシと命令のオーバーヘッドが、キャッシュミスにサービスしているレイテンシのオーバーヘッドを超過していることから、ＤＭＡの転送サイズが十分に大きく、十分に予測可能な場合（例えば、データが必要とされる前にＤＭＡコマンドが発行される場合）に、このＳＲＡＭのローカルメモリ手法による利点が得られる。
【００６８】
サブプロセッシングユニット５０８のうちの、所定の１つのサブプロセッシングユニット上で実行しているプログラムは、ローカルアドレスを使用している関連のローカルメモリ５５０を参照する。しかしながら、ローカルメモリ５５０のそれぞれの場所はまた、システムのメモリマップ全体内に実アドレス（ＲＡ：Real Address）も割当てられる。これにより、プリビレッジソフトウェア（Privilege Software）はローカルメモリ５５０をプロセスの有効アドレス（ＥＡ：Effective Address）にマッピングする、ローカルメモリ５５０と別のローカルメモリ５５０間のＤＭＡ転送を促進する。ＰＵ５０４はまた、有効アドレスを用いてローカルメモリ５５０に直接アクセスすることができる。好ましい実施形態では、ローカルメモリ５５０は５５６キロバイトのストレージを有し、またレジスタ５５２の容量は１２８×１２８ビットである。
【００６９】
ＳＰＵコア５０４Ａは、好ましくは、論理命令がパイプライン式で処理される、プロセッシングパイプラインを用いて実装される。パイプラインは命令が処理される任意の数のステージに分けられうるが、一般にパイプラインは１つ以上の命令のフェッチ、命令のデコード、命令間の依存性チェック、命令の発行、及び、命令の実行ステップを有している。これに関連して、ＩＵ５５２は命令バッファ、命令デコード回路、依存性チェック回路、及び命令発行回路、を有する。
【００７０】
命令バッファは、好ましくは、ローカルメモリ５５０と結合され、また、フェッチされる際に一時的に命令を格納するよう動作できる、複数のレジスタを備えている。命令バッファは好ましくは、全ての命令が一つのグループとしてレジスタから出て行く、つまり、実質的に同時に出て行くように動作する。命令バッファはいずれの大きさでありうるが、好ましくは、２あるいは３レジスタよりは大きくないサイズである。
【００７１】
一般に、デコード回路は命令を分解し、対応する命令の関数を実施する論理的マイクロオペレーションを生成する。例えば、論理的マイクロオペレーションは、算術論理演算、ローカルメモリ５５０へのロード及びストアオペレーション、レジスタソースオペランド、及び／又は即値データオペランドを特定しうる。デコード回路はまた、ターゲットレジスタアドレス、構造リソース、機能ユニット、及び／又はバスなど、命令がどのリソースを使用するかを示しうる。デコード回路はまた、リソースが要求される命令パイプラインステージを例示した情報を与えることができる。命令デコード回路は好ましくは、命令バッファのレジスタ数に等しい数の命令を実質的に同時にデコードするように動作する。
【００７２】
依存性チェック回路は、所定の命令のオペランドがパイプラインの他の命令のオペランドに依存しているかどうかを判断するために試験を行う、デジタル論理回路を含む。その場合、所定の命令はそのような他のオペランドが（例えば、他の命令が実行の完了を許容することにより）アップデートされるまで、実行されることができない。依存性チェック回路は好ましくは、デコーダー回路１１２から同時に送られる複数の命令の依存性を判断する。
【００７３】
命令発行回路は浮動小数点実行ステージ５５６、及び／または固定小数点実行ステージ５５８へ命令を発行するように動作することができる。
【００７４】
レジスタ５５４は好ましくは、１２８エントリのレジスタファイルなどの、相対的に大きな統一レジスタファイルとして実装される。これにより、レジスタが足りなくなる状態を回避するよう、レジスタリネーミングを必要としない、深くパイプライン化された高周波数の実装品が可能になる。一般に、リネーミング用ハードウェアは、処理システムのかなりの割合の領域と電力を消費する。その結果、ソフトウェアのループ展開、又は他のインターリーブ技術によりレイテンシがカバーされると、最新のオペレーションが実現されうる。
【００７５】
好ましくは、ＳＰＵコア５１０Ａはスーパースカラアーキテクチャであり、これにより１つ以上の命令がクロックサイクル毎に発行される。ＳＰＵコア５１０Ａは好ましくは、命令バッファから送られる同時命令の数、例えば２〜３命令（各クロックサイクル毎に２命令あるいは３命令が発行されることを意味する）に対応する程度まで、スーパースカラとして動作する。所望の処理能力に応じて、多数の、あるいは少数の浮動小数点実行ステージ５５６と、固定小数点実行ステージ５５８が採用される。好ましい実施形態では、浮動小数点実行ステージ５５６は１秒あたり３２０億の浮動小数点演算速度で演算し（３２ＧＦＬＯＰＳ）、また、固定小数点実行ステージ５５８は演算速度が１秒あたり３２０億回（３２ＧＯＰＳ）となっている。
【００７６】
ＭＦＣ５１０Ｂは、好ましくは、バスインターフェースユニット（ＢＩＵ：Bus Interface Unit）５６４、メモリ管理ユニット（ＭＭＵ：Memory Management Unit）５６２、及びダイレクトメモリアクセスコントローラ（ＤＭＡＣ：Direct Memory Access Controller）５６０を備えている。ＤＭＡＣ５６０は例外として、ＭＦＣ５１０Ｂは好ましくは、低電力化設計とするため、ＳＰＵコア５１０Ａやバス５１２と比べて半分の周波数で（半分の速度で）実行する。ＭＦＣ５１０Ｂはバス５１２からＳＰＵ５０８に入力されるデータや命令を処理するように動作することができ、ＤＭＡＣに対しアドレス変換を行い、また、データコヒーレンシーに対しスヌープオペレーションを提供する。ＢＩＵ５６４はバス５１２とＭＭＵ５６２及びＤＭＡＣ５６０間にインターフェースを提供する。従って、ＳＰＵ５０８（ＳＰＵコア５１０Ａ及びＭＦＣ５１０Ｂを含む）及びＤＭＡＣ５６０は、バス５１２と物理的に、及び／又は論理的に結合されている。
【００７７】
ＭＭＵ５６２は、好ましくは、メモリアクセスのために、実アドレスに有効アドレスを変換するように動作することができる。例えば、ＭＭＵ５６２は、有効アドレスの上位ビットを実アドレスビットに変換しうる。しかしながら下位のアドレスビットは好ましくは変換不能であり、また、実アドレスの形成及びメモリへのアクセスリクエストに使用する場合には、ともに論理的及び物理的なものと考えられる。１つ以上の実施形態では、ＭＭＵ５６２は、６４ビットのメモリ管理モデルに基づいて実装され、また、４Ｋ−、６４Ｋ−、１Ｍ−、及び１６Ｍ−バイトのページサイズを有する２６４バイトの有効アドレススペースと、２５６ＭＢのセグメントサイズを提供しうる。ＭＭＵ５６２は好ましくは、ＤＭＡコマンドに対し、２６５バイトまでの仮想メモリ、２４２バイト（４テラバイト）までの物理メモリをサポートするように動作することができる。ＭＭＵ５６２のハードウェアは、８−エントリでフルアソシエイティブのＳＬＢと、２５６−エントリと、４ウエイセットアソシエイティブのＴＬＢと、ＴＬＢに対してハードウェアＴＬＢのミスハンドリングに使用される４×４リプレースメント管理テーブル（ＲＭＴ：Replacement Management Table）と、を含む。
【００７８】
ＤＭＡＣ５６０は、好ましくは、ＳＰＵコア５１０Ａや、ＰＵ５０４、及び／又は他のＳＰＵなどの、１つ以上の他のデバイスからのＤＭＡコマンドを管理するように動作することができる。ＤＭＡコマンドには３つのカテゴリが存在し、それらは、プットコマンド、ゲットコマンド、及びストレージ制御コマンドである。プットコマンドは、ローカルメモリ５５０から共有メモリ５１４へデータを移動させるよう動作する。ゲットコマンドは、共有メモリ５１４からローカルメモリ５５０へデータを移動させるよう動作する。また、ストレージ制御コマンドには、ＳＬＩコマンドと同期化コマンドが含まれる。この同期化コマンドは、アトミックコマンド(atomic command)、信号送信コマンド、及び専用バリアコマンドを有しうる。ＤＭＡコマンドに応答して、ＭＭＵ５６２は有効アドレスを実アドレスに変換し、実アドレスはＢＩＵ５６４へ送られる。
【００７９】
ＳＰＵコア５１０Ａは、好ましくは、ＤＭＡＣ５６０内のインターフェースと通信（ＤＭＡコマンド、ステータスなどを送る）するために、チャネルインターフェース及びデータインターフェースを使用する。ＳＰＵコア５１０Ａはチャネルインターフェースを介して、ＤＭＡＣ５６０のＤＭＡキューへＤＭＡコマンドを送る。ＤＭＡコマンドがＤＭＡキューに存在すると、そのコマンドはＤＭＡＣ５６０内の発行及び完了論理により処理される。ＤＭＡコマンドに対する全てのバストランザクションが終了すると、完了信号がチャネルインターフェースを越えて、ＳＰＵコア５１０Ａへ送られる。
【００８０】
図１７はＰＵ５０４の一般的な構造及び機能を例示している。ＰＵ５０４は２つの機能ユニットを有しており、それらはＰＵコア５０４Ａとメモリフローコントローラ（ＭＦＣ）５０４Ｂである。ＰＵコア５０４Ａは、プログラム実行、データ操作、マルチプロセッサマネージメント関数などを実施し、一方でＭＦＣ５０４Ｂはシステム１００のＰＵコア５０４Ａとメモリスペース間のデータ転送に関連する機能を実行する。
【００８１】
ＰＵコア５０４ＡはＬ１キャッシュ５７０、命令ユニット５７２、レジスタ５７４、１つ以上の浮動小数点実行ステージ５７６、及び１つ以上の固定小数点実行ステージ５７８を有することができる。Ｌ１キャッシュは、共有メモリ１０６、プロセッサ１０２、又はＭＦＣ５０４Ｂを介してメモリスペースの他の部分、から受信したデータに対するデータキャッシングの機能を提供する。ＰＵコア５０４Ａが好ましくはスーパーパイプラインとして実装されるので、命令ユニット５７２は好ましくは、フェッチ、デコード、依存性チェック、発行、などを含む、多くのステージを備えた命令パイプラインとして実装される。ＰＵコア５０４はまた好ましくは、スーパースカラ構成であり、一方で１つ以上の命令がクロックサイクル毎に命令ユニット５７２から発行される。高度な処理（演算）能力を実現するために、浮動小数点実行ステージ５７６と固定小数点実行ステージ５７８は、パイプライン構成で複数のステージを有する。所望の処理能力に応じて、多数の、あるいは少数の浮動小数点実行ステージ５７６と、固定小数点実行ステージ５７８が採用される。
【００８２】
ＭＦＣ５０４Ｂは、バスインターフェースユニット（ＢＩＵ）５８０、Ｌ２キャッシュメモリ、キャッシュ不可能なユニット（ＮＣＵ：Non-Cachable Unit）５８４、コアインターフェースユニット（ＣＩＵ：Core Interface Unit）５８６、及びメモリ管理ユニット（ＭＭＵ）５８８を備えている。殆どのＭＦＣ５０４Ｂは、低電力化設計とするために、ＰＵコア５０４Ａとバス１０８と比べて、半分の周波数（半分の速度）で実行する。
【００８３】
ＢＩＵ５８０はバス１０８とＬ２キャッシュ５８２とＮＣＵ５８４論理ブロック間にインターフェースを提供する。このために、ＢＩＵ５８０はバス１０８上で、十分にコヒーレントなメモリオペレーションを実施するために、マスタデバイスとして、また同様にスレーブデバイスとして機能する。マスタデバイスとして、ＢＩＵ５８０はＬ２キャッシュ５８２とＮＣＵ５８４のために機能するため、バス１０８へロード／ストアリクエストを供給する。ＢＩＵ５８０はまた、バス１０８へ送信されうるコマンドの合計数を制限するコマンドに対し、フロー制御機構を実装しうる。バス１０８のデータオペレーションは、８ビート要するように設計され、そのために、ＢＩＵ５８０は好ましくは１２８バイトキャッシュラインを有するように設計され、また、コヒーレンシーと同期化の粒度単位は１２８ＫＢである。
【００８４】
Ｌ２キャッシュメモリ５８２（及びサポートハードウェア論理回路）は、好ましくは、５１２ＫＢのデータをキャッシュするように設計されている。例えば、Ｌ２キャッシュ５８２はキャッシュ可能なロード／ストア、データプリフェッチ、命令プリフェッチ、命令プリフェッチ、キャッシュオペレーション、及びバリアオペレーションを処理しうる。Ｌ２キャッシュ５８２は好ましくは８ウエイのセットアソシエイティブシステムである。Ｌ２キャッシュ５８２は６つのキャストアウトキュー（６つのＲＣマシンなど）と一致する６つのリロードキューと、８つ（６４バイト幅）のストアキューを備えうる。Ｌ２キャッシュ５８２はＬ１キャッシュ５７０において、一部の、あるいは全てのデータのコピーをバックアップするように動作しうる。この点は、処理ノードがホットスワップである場合に状態を回復するのに便利である。この構成により、Ｌ１キャッシュ５７０が少ないポート数でより速く動作することができ、また、より速くキャッシュツーキャッシュ転送ができる（リクエストがＬ２キャッシュ５８２でストップしうるため）。この構成はまた、キャッシュコヒーレンシー管理をＬ２キャッシュメモリ５８２へ送るための機構も提供しうる。
【００８５】
ＮＣＵ５８４は、ＣＩＵ５８６、Ｌ２キャッシュメモリ５８２、及びＢＩＵ５８０と連動しており、通常は、ＰＵコア５０４Ａとメモリシステム間のキャッシュ不可能なオペレーションに対して、キューイング／バッファリング回路として機能する。ＮＣＵ５８４は好ましくは、キャッシュ抑制ロード／ストア、バリアオペレーション、及びキャッシュコヒーレンシーオペレーションなどの、Ｌ２キャッシュ５８２により処理されないＰＵコア５０４Ａとの全ての通信を処理する。ＮＣＵ５８４は好ましくは、上述の低電力化目的を満たすように、半分の速度で実行されうる。
【００８６】
ＣＩＵ５８６は、ＭＦＣ５０４ＢとＰＵコア５０４Ａの境界に配置され、実行ステージ５７６、５７８、命令ユニット５７２、及びＭＭＵユニット５８８からのリクエストに対し、また、Ｌ２キャッシュ５８２及びＮＣＵ５８４へのリクエストに対し、ルーティング、アービトレーション、及びフロー制御ポイントして機能する。ＰＵコア５０４Ａ及びＭＭＵ５８８は好ましくはフルスピードで実行され、一方でＬ２キャッシュ５８２及びＮＣＵ５８４は２：１の速度比で動作することができる。従って、周波数の境界がＣＩＵ５８６に存在し、その機能の一つは、２つの周波数ドメイン間でリクエストの送信及びデータのリロードを行いながら、周波数の差を適切に処理することである。
【００８７】
ＣＩＵ５８６は３つの機能ブロックを有しており、それらは、ロードユニット、ストアユニット、及びリロードユニットである。更に、データプリフェッチ関数がＣＩＵ５８６により実施され、また好ましくは、ロードユニットの機能部である。ＣＩＵ５８６は、好ましくは、
（ｉ）ＰＵコア５０４ＡとＭＭＵ５８８からのロード及びストアリクエストを受ける、
（ｉｉ）フルスピードのクロック周波数をハーフスピードに変換する（２：１のクロック周波数変換）、
（ｉｉｉ）キャッシュ可能なリクエストをＬ２キャッシュ５８２へ送り、キャッシュ不可能なリクエストをＮＣＵ５８４へ送る、
（ｉｖ）Ｌ２キャッシュ５８２に対するリクエストとＮＣＵ５８４に対するリクエストを公正に調停する、
（ｖ）ターゲットウインドウでリクエストが受信されてオーバーフローが回避されるように、Ｌ２キャッシュ５８２とＮＣＵ５８４に対する転送のフロー制御を提供する、
（ｖｉ）ロードリターンデータを受信し、そのデータを実行ステージ５７６、５７８、命令ユニット５７２、又はＭＭＵ５８８へ送る、
（ｖｉｉ）スヌープリクエストを実行ステージ５７６、５７８、命令ユニット５７２、又はＭＭＵ５８８へ送る、
（ｖｉｉｉ）ロードリターンデータとスヌープトラフィックを、ハーフスピードからフルスピードへ変換する、
ように動作可能である。
【００８８】
ＭＭＵ５８８は、好ましくはＰＵコア５４０Ａに対して、第２レベルのアドレス変換機能などによりアドレス変換を行う。第１レベルの変換は好ましくは、ＭＭＵ５８８よりも小型で高速でありうる、別々の命令及びデータＥＲＡＴ（Effective to Real Address Translation）配列により、ＰＵコア５０４Ａにおいて提供されうる。
【００８９】
好ましい実施形態では、ＰＵコア５０４は、６４ビットの実装品で、４−６ＧＨｚ、１０Ｆ０４で動作する。レジスタは好ましくは６４ビット長（１つ以上の特殊用途のレジスタは小型でありうるが）であり、また、有効アドレスは６４ビット長である。命令ユニット５７２、レジスタ５７４、及び実行ステージ５７６と５７８は好ましくは、（ＲＩＳＣ）演算技術を実現するために、ＰｏｗｅｒＰＣステージ技術を用いて実装される。
【００９０】
本コンピュータシステムのモジュール構造に関する更なる詳細は、米国特許第６，５２６，４９１号に解説されており、該特許は参照として本願に組込まれる。
【００９１】
本発明の少なくとも１つの更なる態様によれば、上述の方法及び装置は、図面において例示しているような、適切なハードウェアを利用して実現されうる。この種のハードウェアは、公知の技術のいずれかを用いて実装することができる。この例には、標準的なディジタル回路、ソフトウェアプログラムおよび／またはファームウェアプログラムを実行するように動作可能な公知のプロセッサのいずれか、プログラマブル読出し専用メモリ（ＰＲＯＭ）、プログラマブル配列ロジックデバイス（ＰＡＬ）などの、１つ以上のプログラム可能なディジタル装置またはシステムなどがある。更に、図示している装置は、特定の機能ブロックに分割されて示されているが、そのようなブロックは別々の回路を用いて、及び／あるいは１つ以上の機能ユニットに組み合わせて実装されうる。更に、本発明の様々な態様は、輸送及び／又は配布のために、（フレキシブルディスク、メモリチップ、などの）適切な記憶媒体に格納されうる、ソフトウェア、及び／又はファームウェアプログラムを通じて実装されうる。
【００９２】
本明細書において、具体的な実施形態を用いて本発明を記載したが、これらの実施形態は、本発明の原理および利用の例を示すものに過ぎないことを理解されたい。このため、添付の請求の範囲に記載した本発明の趣旨および範囲から逸脱することなく、これら例示的な実施形態を種々に変更したり、上記以外の構成を考案し得ることが理解されよう。
【図面の簡単な説明】
【００９３】
【図１】本発明の１つ以上の態様により適しうる、サブプロセッサを２つ以上有するマルチプロセシングシステムの構造を例示した説明図。
【図２】本発明の１つ以上の態様による、図１の処理システムの共有メモリの構造及び動作を例示しているブロック図。
【図３】本発明の１つ以上の態様による、図１のシステムのメモリ割当てテーブルの特定の態様の概念図。
【図４】メモリ割当てテーブルのステータス状態（status states）とその２進数表現の関係を例示している真理値表。
【図５】本発明の１つ以上の態様による、処理システムのメモリ割当てテーブルの一部の特性を例示しているバイナリツリー図。
【図６】本発明の１つ以上の態様に従って実行されうる処理ステップを例示しているフローチャート。
【図７】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図８】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図９】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図１０】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図１１】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図１２】本発明の１つ以上の態様に従って、システムの共有メモリのセグメントが予約される際の、図１のシステムのメモリ割当てテーブルの概念図。
【図１３】本発明の１つ以上の更なる態様による、予約されたオブジェクトをシステムのプロセッサ間で共有するために図１（又は別の実施形態）のマルチプロセシングシステムにおいて実装されうるキーテーブルの構造を例示しているブロック図。
【図１４】本発明の１つ以上の更なる態様による、予約されたオブジェクトをシステムのプロセッサ間で共有するために実行されうる処理ステップを例示しているフローチャート。
【図１５】本発明の１つ以上の更なる態様の実装に使用されうる好適なプロセッサエレメント（ＰＥ）を例示した説明図。
【図１６】本発明の１つ以上の更なる態様により適しうる、図１５の一般的なサブプロセッシングユニット（ＳＰＵ）の構造を例示した説明図。
【図１７】本発明の１つ以上の更なる態様により適しうる、図１５の一般的なプロセッシングユニット（ＰＵ）の構造を例示した説明図。
【符号の説明】
【００９４】
１００  処理システム
１０２Ａ，１０２Ｂ，１０２Ｃ，１０２Ｄ  プロセッサ
１０４Ａ，１０４Ｂ，１０４Ｃ，１０４Ｄ  ローカルメモリ
１０６  共有メモリ（システムメモリ）
１０６Ｃ  ミューテックスオブジェクト
１０６Ｄ  セマフォ
１０８  バス
１１０  メモリ割当てテーブル
１１２  キーテーブル
１１２  デコーダー回路
５００  プロセッサエレメント
５０２  インターフェース
５０４  プロセッシングユニット
５０８Ａ  サブプロセッシングユニット
５０８Ｂ  サブプロセッシングユニット
５０８Ｃ  サブプロセッシングユニット
５０８Ｄ  サブプロセッシングユニット
５１０Ａ  コア
５１１  メモリインターフェース
５１２  バス
５１４  メモリ
５１４  共有メモリ
５１６  メモリ接続
５４０Ａ  ＳＰＵコア
５５０  ローカルメモリ
５５２  レジスタ
５５４  レジスタ
５５６  浮動小数点実行ステージ
５５８  固定小数点実行ステージ
５７０  キャッシュ
５７２  命令ユニット
５７２  レジスタ
５７４  レジスタ
５７４  実行ステージ
５７６  浮動小数点実行ステージ
５７６  実行ステージ
５７８  固定小数点実行ステージ
５８２  キャッシュメモリ
【図１】
2006190299.tif 000003
【図２】
2006190299.tif 000004
【図３】
2006190299.tif 000005
【図４】
2006190299.tif 000006
【図５】
2006190299.tif 000007
【図６】
2006190299.tif 000008
【図７】
2006190299.tif 000009
【図８】
2006190299.tif 000010
【図９】
2006190299.tif 000011
【図１０】
2006190299.tif 000012
【図１１】
2006190299.tif 000013
【図１２】
2006190299.tif 000014
【図１３】
2006190299.tif 000015
【図１４】
2006190299.tif 000016
【図１５】
2006190299.tif 000017
【図１６】
2006190299.tif 000018
【図１７】
2006190299.tif 000019