(57)【要約】  共有リソースを有するマルチプロセッサコンピュータシステムにおいて、供給リソースへのアクセスを要求する各マルチプロセッサが共有の優先権レベルを有する場合の公平な動的優先権コンフリクト解決のシステム及び方法を提供する。同位の優先権の場合、又は、単一のポートだけがアクティブである場合において、一般的な動的コンフリクト解決スキームは変更されてコンフリクト又は同位状態の公平な解決を保証する。コンフリクトする優先権のタイ状態があると判断されると、複数のプロセッサエレメントのうちの１つは、所定の優先権レベルに基づいて選択される。選択されたプロセッサエレメントの識別情報と、コンフリクトする優先権のタイ状態の構成が格納される。前のコンフリクトする優先権のタイ状態と同じ構成を有するコンフリクトする優先権のタイ状態が次に発生した場合、前のタイ状態時に選択されたプロセッサエレメントは、特定の優先権のタイ状態の構成における全てのプロセッサエレメントが選択されるまで、次に発生したコンフリクトする優先権のタイ状態時において選択されない。アクティブなポートが１つしかない状況では、従来の動的コンフリクト解決スキームを変更して、公平なアクセスを与え、また、優先権のタイ状態コンフリクトを少なくする。【選択図】  なし
2009512092.tif 000002
【特許請求の範囲】
【請求項１】
共有リソースへのアクセスを要求する複数のプロセッシングエレメントを含むコンピュータシステムであって、
前記共有リソースへのアクセスを同時に要求する複数のプロセッシングエレメント間での優先権タイ状態を動的に解決する、優先権コンフリクト解決回路比較器を含み、
前記優先権タイ状態は、前記複数のプロセッシングエレメントのうちの２つ以上のプロセッシングエレメントが共通の最高優先権を有することから生じ、
前記優先権コンフリクト解決回路比較器は、前記複数のプロセッシングエレメントのそれぞれに対応して割り当てられる、初期の所定の様々な優先権タイ状態時の優先度を含み、
前記複数のプロセッシングエレメントのうちの選択されたプロセッシングエレメントは、当該プロセッシングエレメントの前記初期の優先権タイ状態時の優先度が前記複数のプロセッシングエレメントのうちの最高優先権であることに基づいて、前記共有リソースにアクセスすることができ、
前記複数のプロセッサのうちの前記選択されたプロセッシングエレメントの識別情報は格納され、それにより、前記複数のプロセッシングエレメント間での後続の優先権タイ状態において、前記複数のプロセッサのうちの前記選択されたプロセッシングエレメントは、前記複数のプロセッシングエレメントの残りのプロセッシングエレメントのそれぞれが選択されるまで再度選択されない、コンピュータシステム。
【請求項２】
前記優先権コンフリクト解決回路比較器は、前記複数のプロセッシングエレメント間の間違った優先権を動的に補正する、請求項１に記載のコンピュータシステム。
【請求項３】
前記優先権コンフリクト解決回路比較器は、前記優先権タイ状態に続いて前記複数のプロセッシングエレメントのそれぞれが選択された後にリセットする、請求項１に記載のコンピュータシステム。
【請求項４】
前記複数のプロセッシングエレメントの各プロセッシングエレメントに対応して割り当てられる、前記所定の様々な優先権タイ状態時の優先度は、動的優先権コンフリクト解決回路の出力ポートによって保持される、請求項１に記載のコンピュータシステム。
【請求項５】
前記所期の所定の様々な優先権タイ状態時の優先度と、所定のプロセッサエレメント優先権レベルは、同じである、請求項１に記載のコンピュータシステム。
【請求項６】
前記所期の所定の様々な優先権タイ状態時の優先度と、前記所定のプロセッサエレメント前記優先権レベルは、コンピュータの起動時に決定される、請求項５に記載のコンピュータシステム。
【請求項７】
前記共有リソースは、セマフォである、請求項１に記載のコンピュータシステム。
【請求項８】
複数のプロセッシングエレメント及び共有リソースを含むコンピュータシステム内で、該複数のプロセッシングエレメントのうちの２つ以上のプロセッシングエレメントが共通の最高優先権を有することから生じる、コンフリクトする優先権タイ状態を動的に解決する方法であって、
前記複数のプロセッシングエレメントのそれぞれに対応して、所定の様々な初期優先権タイ状態時の優先度を割り当てるステップと、
最も高い、初期優先権タイ状態時の優先度を有する前記複数のプロセッシングエレメントのうちの要求を出したプロセッシングエレメントに、前記共有リソースへのアクセスを与えるステップと、
前記共有リソースへのアクセスを与えられた前記複数のプロセッシングエレメントのうちの前記要求を出したプロセッシングエレメントの識別情報を格納するステップと、
前記複数のプロセッシングエレメント間での後続のコンフリクトする優先権タイ状態において、前記共有リソースへのアクセスが前に与えられたプロセッシングエレメントには、前記複数のプロセッシングエレメントのそれぞれに前記共有リソースへのアクセスが与えられるまで、前記共有リソースへのアクセスを与えないステップと、
を含む、方法。
【請求項９】
前記アクセスを与えるステップ、前記格納するステップ、及び、前記アクセスを与えないステップは、優先権コンフリクト解決回路比較器によって実行される、請求項８に記載の方法。
【請求項１０】
前記複数のプロセッシングエレメント間で優先権を比較するステップと、
前記複数のプロセッシングエレメント間の間違った優先権を動的に補正するステップと、
を更に含む、請求項８に記載の方法。
【請求項１１】
前記複数のプロセッシングエレメントのそれぞれに対応して割り当てられる前記初期優先権タイ状態時の優先度を、前記優先権コンフリクト解決回路の各出力ポートにおいて保持するステップを更に含む、請求項８に記載の方法。
【請求項１２】
前記共通リソースは、セマフォである、請求項８に記載の方法。
【請求項１３】
複数のプロセッシングエレメント及び共有リソースを含むコンピュータシステムであって、
前記複数のプロセッシングエレメント間での前記共有リソースへのアクセスを制御する、動的コンフリクト解決回路を含み、
前記動的コンフリクト解決回路は、前記メモリリソースにアクセスする２つ以上の同時のプロセッシングエレメントの要求を解決するコンフリクト優先権スキームを含み、
要求のアクティビティが単一のアクティブポートに限られることに応じて、前記コンフリクト優先権スキームは、少なくとも１処理サイクルの間、各プロセッシングエレメントの現在のプロセッシングエレメント優先権レベルを保持する、コンピュータシステム。
【請求項１４】
前記プロセッシングエレメントは、セマフォへのアクセスを要求する、請求項１３に記載のコンピュータシステム。
【請求項１５】
前記要求のアクティビティが前記単一のポートに限られることに応じて、前記動的コンフリクト解決回路は、共有リソースへのアクセスが許可された後のプロセッシングエレメント優先権レベルの変更を禁止する、請求項１３に記載のコンピュータシステム。
【請求項１６】
複数のプロセッシングエレメント及び共有リソースを有するコンピュータシステムにおいて動的にコンフリクトを解決する方法であって、
前記共有リソースへの前記複数のプロセッシングエレメントからの同時アクセス要求を調停するようコンフリクト解決スキームを実施するステップと、
単一のポートがアクティブであることに応じて、共有リソースへのアクセスが許可された後の前記複数のプロセッシングエレメントのプロセッサエレメント優先権レベルの変更を禁止するステップと、
を含む、方法。
【請求項１７】
前記複数のプロセッシングエレメントは、セマフォへのアクセスを要求する、請求項１６に記載の方法。
【発明の詳細な説明】
【関連出願】
【０００１】
本発明は、２００５年１０月１７日に出願した米国特許出願番号第１１／２５２，３４１号の優先権を主張する。この出願の全体は、本願に参照として組み込む。
【技術分野】
【０００２】
本発明は、概して、マルチプロセッサコンピュータシステムにおける動的な優先権コンフリクトの解決のソフトウェア、システム、及び方法、より具体的には、等しい優先権値を有する場合の共有メモリを有するマルチプロセッサコンピュータシステムにおけるコンフリクト解決に係る。
【背景技術】
【０００３】
対称型マルチプロセッシング（「ＳＭＰ」）は、２以上の同質のプロセッサの単一のモノリシック中央メモリへの接続として定義される。しかし、最近まで、ハードウェア及びソフトウェアの制限によって、単一のメモリに効率よくアクセスしうる物理プロセッサの総数が抑えられてきた。これらの制限によって、コンピュータシステム内のプロセッサの数が増加するに従って計算効率を維持する機能が低下し、それにより、システム全体のスケーラビリティが減少してしまっていた。しかし、高速及びかつてないほどに安価なマイクロプロセッサの出現により、プロセッサの数の多いＳＭＰシステムが利用可能となり、また、ハードウェアの進歩により、効率低下は最小限で、単一のメモリに対し何百ものプロセッサを多重化する相互接続ネットワークが可能となっている。
【０００４】
しかし、同じメモリ空間を共有する複数のプロセッサを使用する任意のコンピュータシステムでは、少なくとも２つのプロセッサが同じメモリを同時にアクセスしようとする可能性がある。このような場合に、「コンフリクト」が存在すると言う。メモリ以外でも、複数のユーザが実質的に同時のアクセスを要求しうるシステム内の任意の単一のエレメントについてもコンフリクトは起こりうる。このようなコンフリクトの一例は、クロスバースイッチ上のポートを使用して、複数のポートからの入来信号を１つの選択出力ポートに経路選択する場合に発生しうる。この状況は、コンフリクトを解決することが必要となる。このようなコンフリクトを解決する目的で、特別な回路をコンピュータシステムに追加する必要があり、それにより、どの装置が、任意の所与の時間にメモリ又は別のシステムリソースにアクセスしてよいか決定する。
【０００５】
最も単純な回路では、所定の優先権値を、システム内の各プロセッサに単に割り当てる。コンフリクトが発生すると、回路は、優先権が最も高いプロセッサに、アクセスを許可する。他のプロセッサはいずれも、後の時間においてメモリへのアクセスを試みなければならず、従って、メモリへのアクセスは遅延される。この回路は実装するのは容易であるが、幾つかの主な欠点を有する。第一に、単一の優先権の高いプロセッサがリソースに連続的にアクセスし、優先権の低いプロセッサはリソースに永遠にアクセスできないという可能性がある。このようなイベントは、他のプロセッサをストールさせてしまい、システムの性能が大幅に下がる。第二に、プロセッサの数が増加するに従って、不平等なアクセスイベントが発生する可能性も高まってしまう。結果的に、何百ものプロセッサを有し、また、６４のプロセッサをはるかに超えるシステム規模の性能を依然として有する、メモリを共有するコンピュータシステムを構築することが非常に困難であった。
【０００６】
同じメモリへのアクセスを試みる複数のプロセッサ間のコンフリクトを解決する１つの解決策は、コロラド州コロラド・スプリングスのＳＲＣ  Ｃｏｍｐｕｔｅｒｓ社が譲受した米国特許第６，０２６，４５９号（以下「第６０２６４５９号特許」）に開示される。第６０２６４５９号特許に開示されるシステム及び方法は、このメモリアクセスの優先権問題を有利に解決し、また、全ての処理装置による共有メモリリソースへの平等な優先権アクセスを与える特別な有用性がある。
【０００７】
第６０２６４５９号特許に開示されるシステムは、コンピュータシステムにおいて複数のプロセッサを共有メモリに接続する目的で使用するクロスバースイッチでのコンフリクトを解決するよう機能する。比較的大きい数のプロセッサを使用するコンピュータシステムでは、全プロセッサが、時間の経過と共にメモリにアクセスする等しい優先権を有することを保証することが必要である。動作時、各入力ポートの優先権レベルは、各出力ポートによって保持される。起動時、これらの優先権レベルは、特定のコンピュータシステム設計に従って予め決められる。特定の出力ポートに対してコンフリクトが発生する場合、コンフリクトし合う入力の優先権レベルが評価され、アクセスは、優先権が最も高い入力に対して最初に許可される。この最初のアクセスが許可されると、「選択決定された（winning）」入力の優先権レベルは、最も低い優先権レベルに変更され、他の全ての入力の優先権は、１ずつ上げられる。
【０００８】
この技術を使用することで、全入力は、それらの出力の使用に基づいて全ての可能な優先権レベルを移動し、出力に対してアクセスが与えられたばかりの入力は低い優先権を有し、最近出力にアクセスしていない入力は高い優先権を有することになる。出力へのアクセスを要求する入力だけが評価されるので、第６０２６４５９号特許に開示されるようなシステムは、常に、有用な接続を可能にする。更に、最も長い時間の間出力を使用していない入力は、出力へのアクセスが可能にされる。
【０００９】
しかし、ある入力は、幾らかの時間の間、特定の出力ポートにアクセスする必要がない場合があるので、その優先権は時間の経過に従って最も高いレベルになり、そのレベルに留まってしまう。この最も高い優先権レベルへのインクリメント昇進は、２つ以上のポートに対して発生しうる。これは、最も高い優先権レベルは、一度に２以上の入力によって保持されることが適切に可能である唯一の優先権レベルだからである。従って、全て最も高い優先権レベルを有する入力間のコンフリクトに対処する機構が必要である。この優先権レベルのタイ状態は、同じ優先権を２つの異なる入力に不適切に割り当ててしまう回路エラーのイベント時にも遭遇しうる。
【００１０】
このようなタイ状態を解決する米国特許第６０２６４５９号に開示される１つの解決策では、優先権のコンフリクトが発生する場合に、元の所定の優先権に戻るようデフォルト設定する。この動作は、タイ状態を崩し、回路が機能を続行することを可能にするが、多くの同様のタイ状態が長い期間に亘って発生する場合、不平等なアクセスパターンを形成してしまいうる。このアプローチは、無期限にブロックされる入力がなく、また、任意の入力の最長待機時間は、アクセスが許可される継続時間に入力の総数をかけたものと等しいが、これは、タイ状態が繰り返し発生する場合、同じ入力（選択決定された入力）が選択されるという結果をもたらす。従って、最も高い優先権レベルを同時に所有する複数の入力間でのコンフリクトを公平に解決可能な方法及びシステムが必要である。
【００１１】
第６０２６４５９号特許に開示される技術のような技術の実施における第２の公平さに関する検討事項は、セマフォアクセスに対し繰り返し発生するプロセッサ選択現象である。マルチタスクシステムでは、セマフォは、共通リソースの状態を示す値を有する変数である。セマフォは、使用中のリソースをロックするよう使用する。リソースを必要とする処理は、セマフォを確認して、リソースの状態を決定し、処理方法を決定する。特定のセマフォを必要とするプロセッサは、そのセマフォがロックされていると分かると、そのセマフォが再び利用可能となるまで待機しなければならない。現行のシステムは、そのようなセマフォに対し不平等なアクセスを与える。一般的なシナリオでは、２つ以上のプロセッサが、同じセマフォに対しアクセスを同時に求める。第６０２６４５９号特許に記載されるような機構に基づいて、セマフォへのアクセスにおけるコンフリクトは、優先権の比較によって解決される。このような優先権の比較は、繰り返し発生するゆがんだ選択パターンをもたらす。従って、セマフォへのアクセスを求める複数の入力間でコンフリクトを公平に解決可能な方法及びシステムが必要である。
【発明の概要】
【００１２】
本発明のシステム及び方法は、これらのコンフリクト問題を有利に解決し、メモリアクセスについて公平且つ効率のよい解決を提供する。本願に開示する１つの特定の実施形態では、回路は、優先権がタイ状態の場合に選択決定された（アクセスを獲得した）ポートの識別情報を格納し、優先権タイ状態における全ポートが使用されるまで、次のタイ状態時に同じポートが選択されることを阻止する。全ポートが使用されると新しく処理が始まる。特に、タイ状態時に選択決定されるポートは、システムにより格納される。同じ状況下で次にタイ状態が発生する場合、前に選択決定されたポートとは異なる新しいポートに、全ポートが使用されるまで、アクセスが与えられる。タイ状態だった全ポートにアクセスが与えられると、新たに処理が始まる。タイ状態に対処するこの新しい方法は、メモリアクセス回路が、最も高い優先権タイ状態に対して常に同じポートをデフォルトで選択することを阻止する。
【００１３】
具体的には、本願には、供給メモリリソースへのアクセスを要求する複数のプロセッシングエレメントを含むコンピュータシステムを開示する。コンピュータシステムは、プロセッシングエレメント間でのメモリリソースへのアクセスを制御する優先権タイ状態解決器を有する優先権のコンフリクトを解決する回路を含む。優先権のコンフリクトを解決する回路は、複数のプロセッシングエレメントのそれぞれに対応して割り当てられる所定の様々な初期優先権を含む。一般的に、プロセッシングエレメントのうちの選択されたプロセッシングエレメントに、その初期優先権が最高優先権であることに基づいてメモリリソースへのアクセスが与えられると、その選択されたプロセッシングエレメントの初期優先権は、最も低い優先権に変更され、複数のプロセッシングエレメントの他の全てのプロセッシングエレメントの優先権は、次に高い優先権に上げられる。２つ以上のプロセッシングエレメントに割り当てられた優先権間でタイ（同順位）状態が発生する場合（２つ以上のプロセッシングエレメントが最高優先権を有する）、最初にアクセスが与えられるプロセッシングエレメントは、予め設定された基準に基づいて選択される。このプロセッシングエレメントの識別情報は格納されるので、同様のタイ状態が再び発生する場合には、このプロセッシングエレメントは、同じ最高優先権を有する他のタイ状態時のプロセッシングエレメントが同じアクセス付与統計値を有するまで、アクセスが与えられなくなる。全てのプロセッシングエレメントが等しいアクセス付与統計値を有すると、処理は最初から始められる。
【００１４】
本願には更に、複数のプロセッシングエレメント及び１つの共有メモリリソースを有し、１つの入力ポートだけがアクティブであるコンピュータシステムにおいて動的に優先権のコンフリクトを解決する方法を開示する。一般的に、優先権のコンフリクトは以下のステップを行うことで解決される。即ち、複数のプロセッシングエレメントのそれぞれに対応して所定の様々な初期優先権を割り当てるステップと、最も高い初期優先権を有する複数のプロセッシングエレメントのうちのアクセス要求を出すプロセッシングエレメントにメモリリソースへのアクセスを与え、アクセスを与えられたプロセッシングエレメント以外のプロセッシングエレメントの優先権を次に高い順位に上げるステップを行うことで解決される。本願に開示する一実施形態では、１つのポートだけがアクティブである場合に、そのポートの優先権は、少なくとも１つの選択サイクルの間、変更されない。
【００１５】
本願では、マルチプロセッサコンピュータシステムにおける単一のスイッチが、複数アクセスが同時に要求されるという問題に直面する場合のシリアルパケットコンフリクトを解決するシステム及び方法を開示する。レイヤクロスバースイッチ構成における複数のスイッチは、互いにチェーン接続され、トロイダルスイッチを形成する。最初に低い優先権として順番が決められたパケットは、共有リソースへのアクセスを提供するスイッチにリルーティングされることが可能である。
【図面の簡単な説明】
【００１６】
本発明の上述及び他の特徴及び目的、及び、それらを得る方法は、添付図面と共に以下の好適な実施形態の説明を参照することで明らかとなろう。また、発明自体は、添付図面と共に以下の好適な実施形態の説明を参照することで最良に理解されよう。
【００１７】
【図１】１乃至１６個のセグメントを含み、これらのセグメントは同数の幹線により互いに結合される、本発明の一実施形態によるコンピュータシステムを示す機能ブロックシステム概観図である。各セグメントは、メモリ及びクロスバーアセンブリに加えて、多数の再設定可能なプロセッサ及びコモディティプロセッサを含む。
【００１８】
【図２】図１のコンピュータシステムの相互接続ストラテジを示す略式機能ブロック図である。
【００１９】
【図３】例えば、１２の入力ポートと８の出力ポートを示す図２の相互接続ストラテジにおいてプロセッサスイッチとして使用される動的な優先権コンフリクトの解決及びデータ経路決定回路を示す略式ブロック図である。
【００２０】
【図４】本発明のシステム及び方法と共に使用するコンフリクト解決回路を示す機能ブロック図である。
【００２１】
【図５】本発明のシステムによる、優先権タイ状態が関与する動的な優先権コンフリクトの解決方法を説明するフローチャートである。
【００２２】
【図６】本発明のシステムによる、単一のアクティブポートが関与する動的な優先権コンフリクトの解決方法を説明するフローチャートである。
【００２３】
図面は、例示目的のみで本発明の実施形態を示す。当業者は、以下の説明から、本願に説明する以外の構造及び方法の代替の実施形態を、本願に説明する本発明の原理から逸脱することなく使用しうることは容易に認識されよう。
【発明を実施するための最良の形態】
【００２４】
図１は、本発明のある実施形態による対称型マルチプロセッシング・コンピュータシステム１０を示すハイレベル概観図である。例示的なコンピュータシステム１０は、適切な部分に、任意数の相互接続されたセグメント１２０乃至１２ｎを含むが、本発明の原理は、多数のプロセッサを有する任意のスケーラブルシステムに同様に適用可能である。様々なセグメント１２０乃至１２ｎは、以下により詳細に説明するように、多数の幹線１４０乃至１４ｍを介して結合される。
【００２５】
各セグメント１２は、コモディティプロセッサ１６０乃至１６ｐ（コモディティプロセッサ１６０は、マスタブート装置としても追加的に機能する）と、再設定可能なプロセッサ１８０乃至１８ｒの形式の機能的に区別される多数のプロセッシングエレメントを含む。コモディティプロセッサ１６は、多数の周辺装置相互接続（「ＰＣＩ」）インターフェイスモジュール２０に結合される。図示する実施形態では、各コモディティプロセッサは、２つのそのようなモジュール２０に結合され、それにより、コモディティプロセッサ１６が、セグメント１２のあらゆるＩ／Ｏ機能を実行可能にする。
【００２６】
コンピュータシステム１０は更に、システムコンソール２４を、コンピュータシステム１０の少なくとも１つのセグメント１２に結合するためのシリアル−ＰＣＩインターフェイスを含む。システムコンソール２４は、コンピュータシステム１０のユーザがブート情報をコンピュータシステム１０にダウンロードする、装置を設定する、状態をモニタリングする、及び診断機能を実行することができるよう使用可能である。コンピュータシステム１０内に設定されるセグメント１２の数に関係なく、１つのシステムコンソール２４しか必要ではない。
【００２７】
更に、ブート装置が、ＰＣＩモジュール２０のうちの１つを介してマスタ・ブート・コモディティプロセッサ１６０に結合されうる。コモディティプロセッサ１６１乃至１６ｐに結合されるＰＣＩモジュール２０は、セグメント１２を、例えば、ディスクアレイ２８０乃至２８ｓといったあらゆる他の周辺装置に結合するよう使用される。任意の１つ以上の周辺装置は、例えば、イーサネット（登録商標)接続によって置換されてもよい。
【００２８】
コンピュータシステム１０は、コモディティに基づいた高度なハードウェア及びビルディングブロックを含み、また、高性能コンピューティング（「ＨＰＣ」）の特異性に対応するようなんらかの拡張部を有する。ハードウェアについて、コンピュータシステム１０の基本単位は、セグメント１２である。各セグメント１２は、再設定可能及びコモディティプロセッサ１８、エレメント、メモリ、電源、及びクロスバー・スイッチ・アセンブリを含む。コンピュータシステム１０は、エンドユーザが、相互接続されたセグメント１２からなるシステムを設定可能であるという点で、「スケーラブル」である。各セグメント１２は、再設定可能なプロセッサ又はコモディティプロセッサ１６のいずれかに指定される幾つかのプロセッサを含む。１つのセグメントの一般的な構成は、４つのコモディティプロセッサ１６と、１６の再設定可能なプロセッサ１８でありうる。好適な一実施形態では、再設定可能なプロセッサ１８は、４つのプロセッサ(例えば、カリフォルニア州サンタクララのインテル社から販売されるＤｅｓｃｈｕｔｅｓ（ＴＭ）マイクロプロセッサ)と、８つのインターフェイスチップ（すなわち、１つの再設定可能なプロセッサ１８あたりに２つ）を含む個々のアセンブリ上に駐在しうる。各再設定可能なプロセッサ１８は、３００ＭＨｚより大きい内部プロセッサクロックレートと、１００ＭＨｚより大きいシステムクロック速度を有し、インターフェイスチップは、以下により詳細に説明及び図示するように、再設定可能なプロセッサ１８と、メモリに接続するメモリスイッチとの間を接続する。
【００２９】
コモディティプロセッサ１６は、コモディティプロセッサ・アセンブリ上に含まれうる。このコモディティプロセッサ・アセンブリは、コンピュータシステム１０の全ての入力及び出力を統括する。各コモディティプロセッサ・アセンブリは、１つのプロセッサ（再設定可能なプロセッサ１８と同じタイプ）、２つのインターフェイスチップ、２つのＩ／Ｏバッファ、及び２つの双方向性ＰＣＩバスを含む。各ＰＣＩバスは、単一のコネクタを有する。全てのＩ／Ｏポートは、プロセッサに対して等しい優先権を有するＤＭＡ能力を有有する。ＰＣＩモジュール２０は、共に使用されるコモディティプロセッサ１６に依存して、２つの目的を果たす。マスタ・ブート・コモディティプロセッサ１６０上のＰＣＩコネクタは、ブート装置２６及びシステムコンソール２４に接続するよう使用される。通常のコモディティプロセッサ１６１乃至１６ｐ上のＰＣＩモジュール２０は、他のあらゆる周辺機器に使用される。サポートされるＰＣＩに基づいた相互接続部は、小型コンピュータ用周辺機器インターフェイス（「ＳＣＳＩ」）、光ファイバーケーブルを利用した分散型データインターフェイス（「ＦＤＤＩ」）、高性能並列インターフェイス（「ＨＩＰＰＩ」）等を含む。各ＰＣＩバスは、対応するコモディティに基づいたホストアダプタを有する。
【００３０】
コモディティ機能をコンピューティング機能から分離することで、数値処理と、オペレーティングシステムの役割及び外部周辺機器のサービスの並行実行が可能となる。
【００３１】
図２を更に参照するに、図１のコンピュータシステム１０の相互接続ストラテジを、ｍ個の幹線１４０乃至１４ｍによって相互接続されるｎ個のセグメント１２０乃至１２ｎを使用する実施形態においてより詳細に示す。図示するように、それぞれ、再設定可能なプロセッサ１８０乃至１８ｒの１つに割り当てられる多数のメモリバンク５００乃至５０ｔ（ｎ個のセグメント１２を有するコンピュータシステム１０について１つのセグメント１２あたりにｔ個のメモリバンク５０が存在する）が、コンピュータシステム１０の一部を形成し、それぞれ、幹線１４０乃至１４ｍに、同数のメモリスイッチ５２０乃至５２ｕを介して結合される。メモリバンク５００乃至５０ｔに使用されるメモリは、同期静的ランダムアクセスメモリ（「ＳＳＲＡＭ」）又は他の好適な高速メモリ装置であり得る。更に図示するように、各セグメント１２０乃至１２ｎは、例えば、幹線１４０乃至１４ｍに、同数のプロセッサスイッチ５４０乃至５４ｖのうちの対応するプロセッサスイッチを介して結合される８つのプロセッサ（３つのコモディティプロセッサ１６０乃至１６２と、５つの再設定可能なプロセッサ１８０乃至１８４）を含む。
【００３２】
各セグメント１２は、クロスバースイッチを介して他の全てのセグメント１２と相互接続する。コンピュータシステム１０のクロスバースイッチ技術は、セグメント１２がセグメント境界に亘って、また、個別のセグメント１２内で均一なメモリアクセス時間を有することを可能にする。この技術は更に、コンピュータシステム１０が、システム内の全てのメモリに対して単一のメモリアクセスプロトコルを使用することを可能にする。クロスバースイッチは、高速フィールド・プログラマブル・ゲート・アレイ（「ＦＰＧＡ」）を使用して、メモリとプロセッサとの間に相互接続経路を与えうる。このとき、プロセッサとメモリの物理的な場所は関係ない。このクロスバースイッチは、各セグメント１２を相互接続し、異なるセグメント１２内にあるプロセッサ及びメモリが、均一なレイテンシで通信することを可能にする。本発明の一実施形態では、各クロスバースイッチは、１ティアあたり１クロックのレイテンシを有し、これには、再設定時間も含まれる。３２０個のプロセッサ１６、１８を使用する、１６個のセグメント１２を有するコンピュータシステム１０では、２つのクロスバーティアしか必要でない。各セグメントとメモリを相互接続するクロスバースイッチに加えて、一実施形態では、レイヤスイッチがＦＰＧＡのチェーンポートを介してチェーンされ、インターレイヤブロッキングを阻止するトロイダルスイッチを形成する。インターレイヤブロッキングは、１つのセグメントが、同じポートを介して特定の共有リソースへの同時アクセスを求める場合に発生する。一般的に、要求は、優先権であり、また、決められたコンフリクト解決スキームに応じて順番に並べられる。トロイダルスイッチを形成し、ＦＰＧＡを互いにチェーンすることで、低い優先権を有する要求は、他のＦＰＧＡにリルーティングされることが可能である。この他のＦＰＧＡは、所望の共有リソースへのアクセスを与えることができる。
【００３３】
図３を更に参照するに、図２の相互接続ストラテジにおけるプロセッサスイッチ５４０乃至５４ｖとして使用される、動的な優先権コンフリクトの解決及びデータ経路決定回路を示す。この例示的な実施形態では、多数のコンフリクト解決チップ６６の制御下にある多数のＦＰＧＡが実装されたデータ経路決定集積回路装置（「チップ」）６０を使用して、１２個の入力ポート６２（Ｉ０乃至Ｉ１１）を、８個の出力ポート６４（Ｏ０乃至Ｏ７）に相互接続する。図３は更に、各プロセッサスイッチ５４に関連付けられるチェーンポート７２を示し、それにより、複数のスイッチはトロイダルスイッチを形成する。
【００３４】
以下により詳しく説明するに、プロセッサスイッチ５４のデータ経路決定チップ６０及びコンフリクト解決チップ６６は、全ての処理装置（コンピュータシステム１０の各セグメント１２０乃至１２ｎのプロセッサ）による共有メモリリソース（メモリバンク５００乃至５０ｔ）への平等な優先権アクセスを与えるよう機能する。
【００３５】
図示する回路は、プロセッサ１２をメモリ５０に接続するよう使用されるクロスバースイッチにおけるコンフリクトを動的に解決するよう機能する。本発明の実施形態は、第１の複数の入力ポート（例えば、１２個)と第２の複数の出力ポート（例えば、８個）を有するスイッチ５４を含む。多数のこのようなスイッチ５４は、次に、２つのレベルにカスケード状にされ、それにより、各プロセッサ１２に任意のメモリバンク５０へのアクセスを与えることを可能にする。上述したように、多数のプロセッサ１２を使用するコンピュータシステム１０では、全プロセッサ１２が、長時間に亘って、メモリにアクセスするために等しい優先権を有することを保証することが必要である。
【００３６】
動作時、図４を更に参照するに、各入力ポートの優先権レベルは、各出力ポート６４によって保持される。起動時、これらの優先権レベルは、特定のコンピュータシステム設計に応じて予め決められる。１つのコンフリクト解決スキームでは、特定の出力ポートに対するコンフリクトが生じると、コンフリクトし合う複数の入力の優先権レベルが評価され、コンフリクト解決チップ又はモジュール８２によって優先権が最も高い入力に対してアクセスが最初に許可される。この最初のアクセスが許可されると、その「選択決定された（winning）」入力の優先権レベルは最も低い優先権レベルに変更され、他の全ての入力の優先権は、それぞれ、１ずつ上げられる。
【００３７】
この技術を使用することで、入力は、それらの出力の使用に基づいて全ての可能な優先権レベルを移動し、出力に対してアクセスが与えられたばかりの入力は低い優先権を有し、最近出力にアクセスしていない入力は高い優先権を有することになる。出力へのアクセスを供給する入力だけが評価されるので、システムは、常に、有用な接続を可能にする。更に、最も長い時間の間出力を使用していない入力は、出力へのアクセスが可能にされる。
【００３８】
ある入力は、幾らかの時間の間、特定の出力ポートへのアクセスを希望しない場合があるので、この遅延は、その優先権を最高レベルにインクリメントさせ、２つ以上のポートがアクティブである場合にそこに留まらせてしまう。開示する特定の実施形態では、最も高い優先権レベルは、一度に２つ以上の入力によって保持されることが適切に可能である唯一の優先権レベルである。その結果、以下に更に詳細に説明する、優先権タイ状態解決器８６が、全ての入力が最も高い優先権レベルを有するそれらの入力間のコンフリクトに対処する。同じような状況は、同じ優先権を２つの入力に不適切に割り当ててしまう回路エラーのイベント時にも遭遇しうる。
【００３９】
動作時、各入力ポートの優先権レベルは、各出力ポートによって保持される。起動時、これらの優先権レベルは、特定のコンピュータシステム設計に応じて予め決められる。上に開示したように、特定の出力ポートに対してコンフリクトが生じると、コンフリクトし合う複数の入力の優先権レベルが評価され、優先権が最も高い入力に対してアクセスが最初に許可される。この最初のアクセスが許可されると、「選択決定された（winning）」入力の優先権レベルは最も低い優先権レベルに変更され、他の全ての入力の優先権は、それぞれ、１ずつ上げられる。
【００４０】
ある入力は、幾らかの時間の間、特定の出力ポートへのアクセスを希望しない場合があるので、このイベントは、その優先権を最高レベルにインクリメントさせ、そこに留まらせてしまう。開示する特定の実施形態では、この最も高い優先権レベルは、一度に２つ以上の入力によって保持されることが適切に可能な唯一の優先権レベルである。その結果、本願では、全ての入力が最も高い優先権レベルを有するそれらの入力間のコンフリクトに対処する機構を開示する。同様の状況は、同じ優先権を２つの入力に不適切に割り当ててしまう回路エラーのイベント時にも遭遇しうる。全入力が共通の最も高い優先権レベルを有するそれらの入力間でコンフリクトが生じる状況において、最初に選択決定される入力は、予め決められた基準に基づいて選択される。本発明の一実施形態では、次のタイ状態の公平さは、タイ状態の選択決定された入力を格納することで保証される。開示したように、起動時に、優先権レベルは、特定のコンピュータシステム設計に応じて予め決定される。これらの優先権レベルは更に、エレメントの予め決められた優先権レベルと同じであっても同じでなくともよい所定の優先権タイ状態での優先度レベルも与える。優先権タイ状態が最初に発生する際、システムは、タイ状態での優先度レベルを参照して選択決定される入力を選択する。選択が行われると、そのタイ状態時に選択決定されるべきポートは格納され、それにより、共通の最も高い優先権レベルを有する入力間で次のタイ状態がある場合に、前に選択決定された入力は、残りの最も高い優先権レベルを有する入力のそれぞれが選択されるまで、選択からは除外される。
【００４１】
表１  コンフリクトするタイ状態の優先権のバランシング
【表１】
2009512092.tif 000003
【００４２】
このスキームのタイミングに関する説明を表１に示す。表１は、１つの単一の出力ポートに対して同時にアクセスを求める、３つのプロセッサエレメントからの３つの入力ポートを表す。この例では、各ポートが、供給されるべき単一のパケットを所有し、表１の列は、特定の時間インスタンスを表す。各イベントは、別個の時間インスタンスにおいて発生する。表１に示すコンフリクト解決スキームでは、利用可能な最も高い優先権は３であり、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤの最初の所定の優先権レベルは、それぞれ、３、２、１、及び０である。それぞれ最も高い優先権である３を有するプロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間でコンフリクトが発生する状況では、優先権比較スキームが、プロセッサＡの所定の優先権、即ち、３に基づいてプロセッサエレメントＡを優先して選択する。この選択後でも、複数のパケットが、単一のポートに対して依然として競い合うので、プロセッサエレメントＢ、Ｃ、及びＤ間の優先権タイ状態が、同様に、少なくとも最初は、所定の優先権に基づいて連続的に解決される。この場合、この状況の連続的なタイ状態の選択決定されるプロセッサエレメントは、それぞれ、プロセッサエレメントＢ、Ｃ、及びＤである。各タイ状態で選択決定されるプロセッサエレメント、及び、そのイベントを囲む状況又は構成が格納される。この結果、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤが、同時に、単一のポートを同時にアクセスしようと初めて試みる場合、アクセスは、プロセッサエレメントＡ、Ｂ、Ｃ、次にＤの順番で許可される。
【００４３】
４つの全てのプロセッサエレメントＡ、Ｂ、Ｃ、及びＤが同時に同じポートへのアクセスを求め、また、優先権のタイ状態を有する、４つのプロセッサ間の次のコンフリクトでは、残りのプロセッサが異なる順番で選択決定されるプロセッサエレメントとして選択される。プロセッサエレメントＡ、Ｂ、Ｃ、及びＤの優先権が３でタイ状態となる別のコンフリクトが生じる場合、本願に開示する本発明の一実施形態は、参加プロセッサが関連するタイ状態の前の選択決定されたプロセッサエレメント（表１にハイライト表示する）の識別情報と頻度を前に格納していることで、残りのプロセッシングエレメントが同様の状況において選択決定されるプロセッサエレメントとして選択されるまで前の選択決定されたプロセッサエレメントの選択が阻止される。ここでの例では、プロセッサエレメントＡが、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間のタイ状態での選択決定されるプロセッサエレメントとして選択されることが阻止される。なぜなら、プロセッサエレメントＡは、同じ参加プロセッサエレメントが関与した同様のコンフリクト優先権のタイ状態で以前に選択決定されたからである。残りの３つのプロセッシングエレメントのうち、プロセッサエレメントＢが、最も高い所定のタイ状態での先行優先権を有するので選択決定される。
【００４４】
上述の例を更に説明し、且つ、表１を参照するに、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間でのコンフリクトの次の発生（イベント２）を考える。これも最も高い優先権、即ち、３のタイ状態となることで発生する。プロセッサエレメントＡは、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間の同一の状況下の前のタイ状態において既に選択決定されたので、このタイ状態では、選択決定されない。残りのプロセッサエレメントＢ、Ｃ、及びＤの所定のタイ状態時の優先度レベルが比較され、その結果、プロセッサエレメントＢが選択決定される。プロセッサＢの選択決定が格納される。
【００４５】
プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間での第３のコンフリクトタイ状態が発生（イベント３）すると、プロセッサエレメントＡ及びプロセッサエレメントＢは共に既に選択決定されているのでプロセッサエレメントＣが選択決定される。同様に、イベント４では、プロセッサエレメントＡ、Ｂ、及びＣは既に選択決定されているので、プロセッサエレメントＤが選択される。なお、このスキームによってプロセッサエレメントを選択した結果、コンフリクトするタイ状態についても選択されたプロセッサの格納と状況の比較が行われることに留意されたい。例えば、プロセッサエレメントＡが選択されるという結果をもたらす第１のコンフリクトするタイ状態後、プロセッサエレメントＢ、Ｃ、及びＤは依然としてコンフリクト状態にあり、３の優先権レベルでタイ状態に依然としてある。これらのプロセッサエレメントの優先権タイ状態時の優先度を比較することで、プロセッサＢが選択される。同じコンフリクト及び優先権タイ状態が、５回目に繰り返される（イベント５）。この場合、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間のコンフリクトするタイ状態では、再び、プロセッサエレメントＡが選択されるが、プロセッサエレメントＢ、Ｃ、及びＤ間のタイ状態では、プロセッサエレメントＣが選択される。これは、プロセッサエレメントＢ、Ｃ、及びＤが関与するタイ状態におけるプロセッサエレメントＢの前の選択決定が格納されているので、プロセッサＣ及びＤが等しい選択統計値を有するまでプロセッサエレメントＢの次の選択が阻止される。所定の優先権レベルだけに基づいて繰り返される選択を格納及び阻止することで、タイ状態における入力コンフリクトの解決の公平さが阻止される。
【００４６】
全ての入力が最も高い優先権レベルを有する当該入力間のタイ状態の発生を説明する事例は、セマフォアクセスパターンである。多くのプロセッサが、システム内の幾つかの処理がノード間で正常にデータを動かす際にセマフォをロックしようとしうる。一般的に、セマフォはリタイアされ、リトライの間隔は、セマフォレジスタまで行きプロセッサに戻るループのレイテンシによって決定される。このループは、正常のデータ動作が未使用のセマフォ経路を最も高い優先権にインクリメントするための時間を与え、また、セマフォ経路は、そのような優先権のタイ状態では常に同じ優先権となるようデフォルトで決められる傾向がある。これは、スイッチポートの数が減少するに従ってより問題となる。なぜなら、優先権の数が最大値に到達し、タイ状態となる時間が短くなるからである。従って、この問題は、ループレイテンシが一定である場合に、１６×１６スイッチより４×４スイッチにおいてより明白となる。上述した本発明の実施形態は、２つ以上の入力が共通の最も高い優先権レベルを共有する場合に、入力に公平なアクセスを与えることでこの問題を解決する。
【００４７】
図５は、本発明による、共有リソースを有するマルチプロセッサコンピュータシステムにおいて共通の優先権を有する複数の入力に対する、動的なコンフリクト解決のための１つの例示的な方法のフローチャートである。処理は、コンフリクトの特定（５２０）から開始する。１つ以上のプロセッサエレメントが、共有リソースを同時にアクセスすることを求める。本願に開示するように、共有リソースは、一般的に、共有メモリリソースであるが、プロセッシングエレメントのバンクによって共有される入出力装置といった周辺機器であってもよい。２つ以上のプロセッシングエレメントが同じ共有リソースへのアクセスを要求していることを特定する（５２０）と、動的なコンフリクト解決スキームは、概して、各プロセッサエレメントに関連付けられる優先権に基づいてコンフリクトを解決する。しかし、この場合、共有リソースへのアクセスを要求するプロセッサエレメント間に優先権のタイ状態が存在することが判断される（５３０）。
【００４８】
優先権のタイ状態が存在することが判断される（５３０）と、存在しているプロセッサエレメントのタイ状態の構成を有する各プロセッサエレメントの選択統計値が読出しされる（５４０）。例えば、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤ間の優先権タイ状態がタイ状態構成を確立する。その構成の各エレメントが、その構成に関連付けられる選択統計値を有する。その特定のタイ状態構成の各参加プロセッサエレメントの選択統計値が読出しされると、それらの統計値は比較され（５５０）、参加プロセッサエレメントのいずれかが、他の参加プロセッサエレメントのいずれかよりも頻繁に選択されたかどうか判断される。全ての参加プロセッサエレメントが同等の選択統計値を有すると判断される場合、所定の優先権タイ状態時の優先度レベルに基づいて、又は、当該技術において妥当な技術であると知られる別の手段によって１つのプロセッサエレメントが選択される（５８０）。選択後、選択されたプロセッサの識別情報及び選択統計値が、現在の優先権タイ状態構成に対して格納される（５９０）。
【００４９】
１つ以上のプロセッサエレメントが、タイ状態に参加する別のプロセッサエレメントより頻繁に選択されたと判断される（５５０）と、選択基準が変更される。同様のタイ状態構成において前に選択され、従って、他の参加プロセッサエレメントに比べて高い選択統計値を有するプロセッサエレメントは、選択されないようにされる（５７０）。前の例を更に説明するに、プロセッサエレメントＡ、Ｂ、Ｃ、及びＤの選択統計値の比較することで、同じタイ状態構成においてプロセッサＡは、より高い所定の優先権タイ状態時の優先度レベルを所有するので選択されたことが明らかになりうる。プロセッサＡが選択されたことが明らかになることで、プロセッサエレメントＡは、その所定のタイ状態時の優先度レベルに関係なく、選択からは除外される。残りのプロセッサエレメントは、等しい選択統計値を有すると仮定すると、評価され、選択決定されるプロセッサエレメントが判断される（５７５）。ここでも、選択決定されたプロセッサエレメントの識別情報及び選択統計値が、現在の優先権タイ状態構成に対して格納される（５９０）。
【００５０】
本発明の別の実施形態では、コンフリクトの後、単一のアクティブポートの優先権は変更されない。図４に示すように、コンフリクト解決チップ８２の追加機能は、単一のアクティブポートが生じる場合の管理（９２）である。１つの入力ポートだけがアクティブである場合、各プロセッサエレメントの優先権は、同じに維持されるよう制約される。これは、入力ポートが、連続して少なくとも２つのパケットのために出力にアクセスすることを可能にするが、入力はより公平に扱われることを保証する。全入力ポートにこの２アクセス利点が与えられるので、公正さは迅速に平等化される。これは、全ての未使用の入力ポートが、１つの入力ポートの実行時に、最も高い優先権にインクリメントされることを阻止する。例えば、一般的な優先権スキーム下では、各非選択ポートの優先権は、出力ポートを競い合うパケットをその入力ポートが有するか否かに関わらず、１つずつ増加される。幾つかのパケットを有する単一のアクティブポートは、残りのプロセッサエレメントをそれぞれの最も高い優先権レベルにあげ、これらのプロセッサエレメントはその状態に維持される。次のコンフリクトが生じると、優先権のタイ状態は、幾つかのタイ状態の発生後には概して不公平となるようなタイ状態の解決をもたらす。或いは、各ポートが単一のパケット又は等しい数のパケットを有する場合、この優先権スキームは、第１の選択決定されたポート（勝者）に対し不公平なセマフォアクセスを与え続ける。本発明の実施形態は、このような不平等を解決する。
【００５１】
本発明の上述の実施形態を、表２を使って説明する。表２は、共有リソースへの同じ出力ポートへのアクセスを求める３つのプロセッサエレメントＡ、Ｂ、及びＣを示す。プロセッサエレメントＡ、Ｂ、及びＣは、（３）、（２）、及び（１）といった起動時によって決定される所定の優先権値と、それぞれ、３、２、及び１である実際の優先権レベルを有する。表２に示す各イベントは、別個の発生時間である。提示する例では、３つのプロセッサエレメントは、それぞれ、当時に同じリソースにアクセスしようとしている点でコンフリクトしている。各プロセッサエレメントは、優先権番号の後の・（中黒点）によって示されるように供給する単一のパケットを有する。
【００５２】
表２  単一ポートのコンフリクト時の優先権のバランシング
【表２】
2009512092.tif 000004
【００５３】
イベント１において、プロセッサエレメントＡ、Ｂ、及びＣ間でコンフリクトが認識される。各プロセッサエレメントは、単一のパケットで共有リソースにアクセスすることを同時に求める。コンフリクトの発生時のプロセッサエレメントＡ、Ｂ、及びＣのプロセッサ優先権値は、それぞれ、３、２、及び１である。従って、プロセッサエレメントＡが選択され、出力ポート／共有リソースへの最初のアクセスを得る。非選択ポートの優先権値は、１つずつ増加され、選択されたポートであるプロセッサエレメントＡの優先権値は、０にリセットされる。残りの２つのポートＢ及びＣは、供給するパケットを依然として有するので共有リソースへのアクセスを求め続ける。プロセッサエレメントＢ及びＣの優先権を比較することで、プロセッサエレメントＢが選択される。上述したように、非選択プロセッサエレメントの優先権値は、１つずつ増加され、選択されたプロセッサエレメントの値は、ゼロにリセットされる。この時点でのプロセッサエレメントＡ、Ｂ、及びＣの優先権値は、それぞれ、１、０、及び３である。
【００５４】
この時点では、１つの入力ポート、即ち、プロセッサエレメントＣに関連付けられる入力ポートだけがアクティブとなる。というのは、このポートが唯一パケットを有するからである。コンフリクトは存在しないが、一般的なコンフリクト解決スキームでは、当業者には周知であるように、プロセッサエレメントＣが選択され、プロセッサエレメントＣの優先権値をゼロにリセットし、非選択プロセッサの優先権値を１つずつ増加する。しかし、上述したように、これは、不平等な選択統計値を生成する。本発明の一実施形態では、また、本開示に説明するように、単一でアクティブなポートを選択すると、全プロセッサの優先権レベルは、変更されない。この例では、１つのポート、即ち、プロセッサＣだけがアクティブであるので、プロセッサエレメントＡ、Ｂ、及びＣの優先権値は、変化しない。この時点でのプロセッサエレメントＡ、Ｂ、及びＣの優先権値は、それぞれ、１、０、及び３である。
【００５５】
次のコンフリクトの発生後、優先権値を比較することで、プロセッサＣが再び選択される。しかし、ここでは、２つ以上のポートがアクティブである（プロセッサエレメントＡ、Ｂ、及びＣのそれぞれが、共有リソースへのアクセスを求めるパケットを有する）ので、プロセッサＣの優先権値は、ゼロにリセットされ、非選択ポートＡ及びＢの優先権値は、１つずつ増加される。処理は、表２に示すように続行する。従って、セマフォといった共有リソースに対して複数のプロセッサエレメントがアクセスを求める状況において公平な選択処理が行われる。
【００５６】
本発明の本実施形態を更に説明する目的で、４つの入力ポートが同時にアクティブであるが１つのパケットに対してだけである単純な事例を考える。最も高い優先権の入力が最初に送信され、その優先権は下げられるが、他の全ての入力の優先権は１つずつ上げられる。上述のスキームを使用して処理が４つのパケットに対して繰り返されると、優先権は開始した状態と同じ状態で終了することに留意されたい。これは、最初に通るセマフォがロックを得るので、セマフォアクセスについて公平ではない。他はリタイアされ、また、第１のセマフォがセマフォレジスタを使用して終了すると、セマフォレジスタは、再びセマフォアクセスを発行し、また、他の３つのチャネルを打ち負かすことができる。試験において、このような事例は、確かに発生し、また、高い時間的確率で第１のポートがセマフォのロックを得る非常に不公平なアクセスパターンがもたらされることが示されている（セマフォトラフィックに関する本願における説明を参照されたい）。２つ以上の入力ポートがアクティブである任意の場合において、本願に記載したように、優先権のリセット及びインクリメントが行われることを想起されたい。本発明のこの実施形態では、１つのポートがアクティブである場合、その単一のポートの優先権は、その現在値を保持する。これは、重いトラフィックが公平に交互に切り替わり、また、軽いセマフォタイプのトラフィックが、複数の優先権レベルを循環し１つのチャネルが単純な元のスキームを乱用することを阻止する。
【００５７】
図６は、共有リソースを有するマルチプロセッサコンピュータシステムにおける複数の入力に対する、動的なコンフリクト解決の方法の一実施形態のフローチャートを示す。図６に示す例示的な方法は、共有リソースへのアクセスを求めるプロセッサエレメント間のコンフリクトを特定すること（６１０）から開始する。例えば、１つ以上のプロセッサが、共有メモリリソースにアクセスするよう求めうる。各プロセッサは、そのリソースに１つ以上の情報パケットを送信することを望む。２つ以上のポート（それぞれ、プロセッサからの要求を表す）がアクティブであると判断される（６２０）場合（これは、各ポートが共有リソースに供給されることを求めるパケットを有することを意味する）、コンフリクトを解決する必要がある。本願に開示するように、同じリソースを求めるプロセッサエレメント間のコンフリクト解決は、一実施形態では、動的なコンフリクト解決スキームにより達成される（６３０）。
【００５８】
一般的に、各プロセッサエレメントに関連付けられる優先権レベルによって、どの入力ポートが共有リソースに対して最初にアクセスできるか決定される。１つのポートが選択され、かつ、供給リソースへのアクセスが許可されると、そのプロセッサエレメントに関連付けられる優先権レベルはゼロにリセットされる（６４０）。選択されないポート、即ち、プロセッサエレメントの優先権レベルは、１つずつ増加される（６５０）。
【００５９】
本発明のこの実施形態では、１つのポートだけがアクティブである場合、選択されたポートの優先権レベルはリセットされないことが、一般的に実現される。１つのポートだけがアクティブであることが判断される（６２０）と、プロセッサエレメント間のコンフリクトは、単一のプロセッサを選択する（６６０）ことで解決される。しかし、選択したプロセッサの優先権レベルをゼロにリセットするのではなく、全プロセッサエレメントの優先権レベルは、強制的に、同じに維持される（６７０）。結果として得られる選択パターンは、より公平なアクセスパターンである。これは、全ポートが、２つのアクセスがあるという利点を有することによる。
【００６０】
本発明の原理を、特定のマルチプロセッサコンピュータアーキテクチャに関連して上述したが、上述の説明は、例示的に過ぎず、発明の範囲を限定するものではないことは明らかに理解されよう。特に、上述の開示の教示内容は、当業者には他の変形を提案するであろうことが認識される。このような変形は、それ自体は既知であり、また、本願に既に記載した特徴の代わりに又は追加して使用されうる他の特徴も関連しうる。請求項の範囲は、本願では、特徴の特定の組み合わせに対して作成されたが、本願の開示内容の範囲は、明示的又は暗示的に開示した任意の新規の特徴又は任意の新規の特徴の組み合わせ、又は、当業者には明らかであり、また、任意の請求項に記載する同じ発明に関連するか否か、又は、本発明が直面する同じ技術的問題の任意又は全てを軽減するか否かに関わらず、それらの任意の一般化又は変形を含みうる。出願人は、ここでは、本願又は本願から導出される任意の更なる出願の審査経過時に上述の特徴及び／又は上述の特徴の組み合わせについて新しい請求項を作成する権利を保持する。
【００６１】
本発明は、特定の度合いの特殊性と共に説明及び図示したが、本開示は、例示的に過ぎず、部品の組み合わせ及び配置において多数の変更を、発明の精神及び範囲から逸脱することなく当業者により行われうることは理解されよう。当業者には明らかであるように、モジュール、マネジャ、機能、システム、エンジン、レイヤ、特徴、属性、方法論、及び本発明の他の面は、ソフトウェア、ハードウェア、ファームウェア、又はこれらの任意の組み合わせで実装可能である。当然ながら、ソフトウェアとして実装される本発明のコンポーネントは、コンピュータプログラミングの技術分野における当業者には、スクリプト、スタンドアロンプログラム、大きいプログラムの一部、複数の別個のスクリプト及び／又はプログラム、静的又は動的にリンクされたライブラリ、カーネルをロード可能なモジュール、デバイスドライバ、及び／又は、現在又は将来において知られるあらゆる又は任意の他の方法として実施可能である。更に、本発明は、任意の特定のプログラミング言語、又は、任意の特定のオペレーティングシステム又は環境での実施に限定されない。従って、本発明の開示内容は例示的であって、発明の範囲を限定するものではなく、発明の範囲は、請求項に記載する。
【図１】
2009512092.tif 000005
【図２】
2009512092.tif 000006
【図３】
2009512092.tif 000007
【図４】
2009512092.tif 000008
【図５】
2009512092.tif 000009
【図６】
2009512092.tif 000010
【国際調査報告】
2009512092.tif 000011