(57)【特許請求の範囲】
【請求項１】
マルチノードコンピュータネットワークにおけるデッドロックを回避するためのメッセージ受渡し装置であって、
ノードインタフェースが生成したネットワークメッセージを、ネットワークメッセージの処理要件とメッセージ通信プロトコルとに従って個々のメッセージタイプに復号化する復号器と、
前記ネットワークメッセージのメッセージタイプ毎に割り当て量が設定され、前記ネットワークメッセージを記憶する、様々なタイプのネットワークメッセージを受け取るための単一のバッファと、
前記バッファと前記復号器とに結合され、前記バッファに記憶された未処理であるいずれかのメッセージタイプのネットワークメッセージの数が当該メッセージタイプの割り当て量に達したら、前記ノードインタフェースに対し当該メッセージタイプのネットワークメッセージ発生を停止させる通知を行なう、前記バッファを通してノード間での前記ネットワークメッセージの受渡しを制御する出力制御装置と、
を含むメッセージ受渡し装置。
【請求項２】
前記バッファがノードの出力とネットワークとの間に結合されている請求項１に記載の装置。
【請求項３】
前記バッファが、前記ネットワークメッセージの主要なトラヒックのパターンに従って決定された前記割り当て量に従って可変的に区切られている請求項１に記載の装置。
【請求項４】
前記ネットワークメッセージが前記バッファ内に稠密形式で記憶される請求項１に記載の装置。
【請求項５】
メッセージの受渡しを許可するマルチキャストが存在するかどうかを判定するための、および、マルチキャストメッセージのために前記バッファ内に必要とされるエントリの個数を減らすための、前記バッファに結合されているマルチキャストエンジンをさらに含む請求項１に記載の装置。
【請求項６】
前記バッファをメッセージがバイパスすることを可能にするための、前記バッファに結合されているバイパスエンジンをさらに含む請求項１に記載の装置。
【請求項７】
前記バッファ内に記憶されるメッセージのオーバフローの指示時に前記バッファが拡張される請求項１に記載の装置。
【請求項８】
前記ネットワークメッセージタイプがその処理要件とメッセージ通信プロトコルとに基づいて分類されている請求項１に記載の装置。
【請求項９】
前記ネットワークメッセージタイプが、確実に完了されなければならないトランザクションに関する高信頼トランザクションメッセージと、応答メッセージまたは他の回答メッセージを必要としないトランザクションに関する通知メッセージと、確実に完了される必要がないトランザクションに関する不信頼トランザクションメッセージとを含む請求項８に記載の装置。
【請求項１０】
前記バッファが、前記ネットワークメッセージタイプの各々に関して、個々のメッセージタイプに許容されている未処理メッセージの最大数に基づいた予約割り当て量を含む請求項９に記載の装置。
【請求項１１】
前記バッファのサイズが、ノードが常に入力メッセージを処理することが可能であるために十分な大きさであり、それによって、通信におけるデッドロックを回避して順方向転送を促進する請求項１０に記載の装置。
【請求項１２】
前記高信頼トランザクションメッセージに関する前記予約割り当て量のサイズが、ノード１つ当たりの未処理トランザクションの最大数と、トランザクション１つ当たりの最大メッセージファンアウトと、各メッセージタイプのサイズと、高信頼相互通信を必要とするノードの合計数の１／２との積である請求項１０に記載の装置。
【請求項１３】
前記通知メッセージに関する前記予約割り当て量のサイズが、ノードが未処理のまま有することが許可されている前記通知メッセージの数に基づいている請求項１０に記載の装置。
【請求項１４】
前記不信頼トランザクションメッセージに関する前記予約割り当て量のサイズが、前記不信頼トランザクションメッセージに関するトランザクションの予測頻度に基づいている請求項１０に記載の装置。
【請求項１５】
前記メッセージタイプの各々が複数のサブメッセージタイプを含む請求項９に記載の装置。
【請求項１６】
前記高信頼トランザクションメッセージに関する前記サブメッセージタイプが、調停トランザクションメッセージタイプと正規トランザクションメッセージタイプとを含む請求項１５に記載の装置。
【請求項１７】
前記サブメッセージタイプが前記バッファの領域の管理を可能にする請求項１５に記載の装置。
【請求項１８】
前記ネットワークメッセージが、マルチキャストがあるかどうかに関する情報を有するヘッダを含む請求項１に記載の装置。
【請求項１９】
前記出力制御装置が、前記ネットワークメッセージタイプの各々のネットワークメッセージの数を制限する請求項１に記載の装置。
【請求項２０】
メッセージファンアウト数を減らすように前記ネットワーク内でのメッセージ転送を確実なものにするためのネットワークインタフェースをさらに含む請求項１に記載の装置。
【請求項２１】
ネットワークメッセージを使用するマルチノードコンピュータネットワークにおけるデッドロックを回避するための方法であって、
ネットワークインタフェースユニットは、ノードインタフェースが生成したネットワークメッセージのメッセージタイプの各々に対して、前記メッセージタイプ毎に前記ネットワークメッセージの割り当て量を設定し、前記ネットワークメッセージを記憶する、単一のバッファの予約領域を割り当てる段階と、
ネットワークインタフェースユニットは、前記ノードインタフェースが生成したネットワークメッセージを、ネットワークメッセージの処理要件とメッセージ通信プロトコルとに従って個々のメッセージタイプに復号化する段階と、
ネットワークインタフェースユニットは、前記単一のバッファに記憶された未処理であるいずれかのメッセージタイプのネットワークメッセージの数が当該メッセージタイプの割り当て量に達したら、前記ノードインタフェースに対し当該メッセージタイプのネットワークメッセージ発生を停止させる通知を行なうことで、前記バッファを通してノード間での前記ネットワークメッセージのフロー制御を実現する段階と、
を含む方法。
【請求項２２】
データ処理システムであって、
プロセッサ間通信ネットワークと、
少なくとも１つのプロセッサを含む第１のプロセッサノードと、
前記第１のプロセッサノードに結合されており、かつ前記プロセッサ間通信ネットワークに結合されている第１のネットワークインタフェースユニットと、
少なくとも１つのプロセッサを含む第２のプロセッサノードと、
前記第２のプロセッサノードに結合されており、かつ前記プロセッサ間通信ネットワークに結合されている第２のネットワークインタフェースユニットと、
を備え、前記第１のネットワークインタフェースユニットは、
前記第１のプロセッサノードから第１のネットワークメッセージを受け取る第１のノードインタフェースと、
前記第１のノードインタフェースから受け取った第１のネットワークメッセージを、出力メッセージの処理要件とメッセージ通信プロトコルとに従って個々のメッセージタイプに復号化する第１の復号器と、
前記第１のネットワークメッセージのメッセージタイプ毎に割り当て量が設定され、前記第１のネットワークメッセージをそのメッセージタイプ毎に記憶する、前記第１のプロセッサノードから様々なタイプの第１のネットワークメッセージを受け取る単一の第１のバッファと、
前記第１のバッファと前記第１の復号器とに結合され、前記第１のバッファに記憶された未処理であるいずれかのメッセージタイプの第１のネットワークメッセージの数が当該メッセージタイプに対する割り当て量に達したら、前記第１のノードインタフェースに対し当該メッセージタイプのネットワークメッセージの発生を停止させる通知を出力する、前記第１のバッファを通しての前記第１のメッセージの受渡しを制御する第１の出力制御装置と、
を含み、前記第２のネットワークインタフェースユニットは、
前記第２のプロセッサノードから第２のネットワークメッセージを受け取る第２のノードインタフェースと、
前記第２のノードインタフェースから受け取った第２のネットワークメッセージを、出力メッセージの処理要件とメッセージ通信プロトコルとに従って個々のメッセージタイプに復号化する第２の復号器と、
前記第２のネットワークメッセージのメッセージタイプ毎に割り当て量が設定され、前記第２のネットワークメッセージをそのメッセージタイプ毎に記憶する、前記第２のプロセッサノードから様々なタイプの第２のネットワークメッセージを受け取る単一の第２のバッファと、
前記第２のバッファと前記第２の復号器とに結合され、前記第２のバッファに記憶された未処理であるいずれかのメッセージタイプの第２のネットワークメッセージの数が当該メッセージタイプに対する割り当て量に達したら、前記第２のノードインタフェースに対し当該メッセージタイプのネットワークメッセージの発生を停止させる通知を出力する、前記第２のメッセージの受渡しを制御する第２の出力制御装置と、
を含むデータ処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的にコンピュータネットワークメッセージ通信に関するものであり、さらに特に、マルチノードコンピュータネットワークにおけるメッセージ制御の際のデッドロックの防止に関する。
なお、本願は、１９９８年５月８日付けの米国仮出願No．６０／０８４，７９５に基づくものである。
【０００２】
また、本願は、次の同時係属出願と関連している。同時係属米国特許出願番号０９／０４１，５６８、「パイプライン化されたスヌーピープロトコルを有する相互接続用マルチプロセッサノードのためのキャッシュコヒーレンスユニット」の名称で、１９９８年３月１２日に出願（米国特許第６，６３１，４４８号）、同時係属米国特許出願番号０９／００３，７７１、「統合されたメッセージパッシングサポートを備える分散共有メモリマルチプロセッサのためのメモリ保護メカニズム」の名称で、１９９８年１月７日に出願（米国特許第６，２１２，６１０号）、同時係属米国特許出願番号０９／００３，７２１、「分散共有メモリマルチプロセッサシステムのための統合されたメッセージパッシングおよびメモリ保護を備えるキャッシュコヒーレンスユニット」の名称で、１９９８年１月７日に出願（米国特許第６，２０９，６１０号）、同時係属米国特許出願番号０９／２８１，７１４、「分散共有メモリマルチプロセッサのための分割疎ディレクトリ」の名称で、１９９９年３月３０日に出願（米国特許第６，５６０，６８１号）。
【０００３】
【従来の技術】
マルチノードコンピュータネットワークでは、ネットワークメッセージをインタコネクトに通過させることによってノードが互いに通信し合う。こうしたネットワークメッセージは、そのネットワークの種類と要件とに応じて、様々な形のノード相互間通信をサポートする。例えば並列処理システムでは、ネットワークメッセージは共有メモリマルチプロセッサシステムにおけるキャッシュコヒーレンス通信を特にサポートし、分散メモリマルチコンピュータシステムにおいてはメッセージ受渡し通信をサポートする。１つのコンピュータシステムで１つ以上の形式のメッセージ通信をサポートする場合が多い。
【０００４】
ネットワークが適正に機能するためには、ネットワークメッセージ制御の際のデッドロックを防止することが重要である。一般的に、デッドロックは、（１）或る資源が１つのプロセスに割り当てられる相互排除、（２）資源が増加的に獲得されかつプロセスが別の資源を待ちながら１つの資源を保持する保持および待機、（３）割当てられた資源を別のプロセスが強制的に獲得することができない無横取り（ｎｏ  ｐｒｅｅｍｐｔｉｏｎ）、（４）他のプロセスが保持している資源を待つという従属関係の鎖を２つ以上のプロセスが環状に形成する環状待機という４つの条件の全てが満たされる時に発生する。
【０００５】
ネットワークメッセージ通信においては、「資源」は、ネットワークメッセージを１つのノードから別のノードへ転送するときにそれを保持するために利用可能なバッファ領域と定義され、「プロセス」は、ネットワークメッセージを生成し消費するノードと定義される。デッドロックが発生すると、ネットワーク内の幾つかのノードが先に進めなくなる（すなわち、ネットワークメッセージを処理できなくなる）。適切な回復処置がなければ、ネットワークはリセットまたは割込を開始しなければならず、このことはメッセージの損失を生じさせシステム全体に損害を与える可能性がある。
【０００６】
デッドロックは、防止、回避、および、検出／回復を含む幾つかの手法のいずれかによって対処することが可能である。防止手法は、上記の４つの条件の１つを取り除き、それによってデッドロックの発生を不可能にすることによる。回避手法は、各資源の割振りの前にデッドロック条件を検査して、デッドロックの発生可能性がない場合にだけ資源割当てを許可することによる。検出／回復手法は、デッドロックを防止も回避もしないが、デッドロック発生後にそのデッドロック状況を検出して、こうしたデッドロック状況から回復させることによる。
【０００７】
デッドロックを回避するための一般的な手法の１つは、要求メッセージと応答メッセージとのために、２つの別々のインタコネクト、または、同じ１つのインタコネクト内の２つの別々のチャネルを設けることによる。この手法では、ノードが提起する要求の数を制限することによって、そのノードの応答メッセージのための十分なバッファを確保する。この手法の一例が、ＡＮＳＩ／ＩＥＥＥ  Ｓｔｄ．１５９６−１９９２，Ｓｃａｌａｂｌｅ  Ｃｏｈｅｒｅｎｃｅ  Ｉｎｔｅｒｆａｃｅ（ＳＣＩ）（１９９２）に記述されている。単純な要求−応答メッセージ通信プロトコルだけを許可するネットワークでは、この手法は、デッドロックを回避する上で十分なものである。
【０００８】
要求転送（ｒｅｑｕｅｓｔ  ｆｏｒｗａｒｄｉｎｇ）を可能にするメッセージ通信プロトコルのような、より先進的なメッセージ通信プロトコルでは、２つのインタコネクトを使用する上記の手法を、インタコネクトの個数を増加させることによって拡張する。必要とされる独立のインタコネクトの個数は、メッセージ通信プロトコルの従属連鎖の最大長さに対応する。
【０００９】
ＬｅｎｏｓｋｉとＷｅｂｅｒによってＳｃａｌａｂｌｅ  Ｓｈａｒｅｄ−Ｍｅｍｏｒｙ  Ｍｕｌｔｉｐｒｏｃｅｓｓｉｎｇ（１９９５）で説明されている別の手法は、２つの別個のインタコネクトチャネルを使用する要求転送メッセージ通信を可能にするが、この２つのチャネルをメッセージ通信プロトコルのバックオフ機構と結合する。潜在的なデッドロック状況が検出されると、その潜在的デッドロック状況が解消され終わるまで、転送を必要とする全ての要求に対して否定応答を送ることによって、バックオフ機構が要求−応答トランザクションに復帰する。
【００１０】
しかし、要求メッセージと応答メッセージとのために別々のインタコネクトまたはインタコネクトチャネルを必要とすることは、相互接続ネットワークとその管理構造とに対して追加のオーバヘッドを負わせることになる。これに加えて、別々のインタコネクト上のメッセージを互いに順序付けることは不可能であり、かつ、メッセージの順序付けに関する仮定を単純化することが不可能であるので、この多重インタコネクト手法もメッセージ通信プロトコルを複雑化する。さらに、バックオフ機構を有することも、メッセージ通信プロトコルをさらに複雑化する。
【００１１】
検出／回復を使用する別の手法は、デッドロックが検出される時に、使用可能であるバッファを拡張することを含む。これは、ＫｕｂｉａｔｏｗｉｃｓおよびＡｇａｒｗａｌの″Ａｎａｔｏｍｙ  ｏｆ  ａ  Ｍｅｓｓａｇｅ  ｉｎ  ｔｈｅＡｌｅｗｉｆｅ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ，″  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ７ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ（１９９３）によって、Ａｌｅｗｉｆｅ機械の形で既に具体化されている。このＡｌｅｗｉｆｅアプローチでは、ある特定の期間内にその出力キューがブロックされ終わった後で、ネットワークインタフェースチップがプロセッサに中断信号を送る。その後で、そのプロセッサが入力キューをローカルメモリ内に記憶する。
【００１２】
このＡｌｅｗｉｆｅアプローチは、入力キューがオーバフローする時には何時でも、ローカルメモリ中の入力キューを拡張することによって、仮想無限バッファをエミュレートする。しかし、このアプローチは、このバッファのサイズの管理を取り扱わない。さらに、このＡｌｅｗｉｆｅは、まず最初に潜在的なデッドロック状況を検出することと、その次にプロセッサにキューをローカルメモリ内に拡張させることによって、ソフトウェア的にデッドロック状況を解決することとに依存している。同じデッドロックに捕らえられている未処理の要求をプロセッサが有する可能性があり、かつ、特殊な実行中止／障害回復機構なしでは、このデッドロックが解決され終わるまでプロセッサが中断処理を行うことが不可能であるので、上記アプローチは常に実現可能というわけではない。
【００１３】
【発明が解決しようとする課題】
したがって、求められているものは、要求メッセージと応答メッセージとのための別個のインタコネクトチャネルをサポートするために必要とされるインタコネクト管理オーバヘッドを増大させることがなく、かつ、バックオフ機構サポートとソフトウェア管理デッドロック回復との複雑性を排除する、メッセージ通信デッドロックを回避するための手法である。
【００１４】
本発明は、マルチノードコンピュータネットワークにおいてノード間のメッセージを制御する際にデッドロックを回避するためのコンピュータアーキテクチャを提供する。
【００１５】
【課題を解決するための手段】
デッドロックを回避する本発明は、ノードからの出力ネットワークメッセージの全てをバッファリングするために、ノード出力とネットワークとの間にバッファとその関連の制御回路系とを挿入する。関連のフロー制御回路系を伴うバッファの適正なサイズ決定が、十分なバッファリングを確実なものとし、その結果として、バッファがオーバフローせず、環状待機に含まれる一群のノードの中の少なくとも１つのノードが常に入力メッセージを処理し、それによって順方向転送を促進し、デッドロックを回避することが可能である。
【００１６】
上記バッファを効果的に管理するために、ネットワークメッセージが、そのメッセージの処理要件とメッセージ通信プロトコルとに基づいて、好ましくは３つのタイプに分類される。この好ましい実施様態では、これらのメッセージタイプが、「高信頼トランザクションメッセージ（ｒｅｌｉａｂｌｅ  ｔｒａｎｓａｃｔｉｏｎ  ｍｅｓｓａｇｅ）」、「通知メッセージ（ｐｏｓｔｅｄ  ｍｅｓｓａｇｅ）」、「不信頼トランザクションメッセージ（ｕｎｒｅｌｉａｂｌｅ  ｔｒａｎｓａｃｔｉｏｎ  ｍｅｓｓａｇｅ）」と呼ばれる。本発明は、各メッセージタイプ毎に割り当て量をバッファ内に予約し、この割り当て量に基づいて、未処理である各タイプのネットワークメッセージの個数を常に制御する。合計バッファサイズは、これらのメッセージタイプの領域要件の合計である。実施様態の１つでは、本発明は、さらに、より精密な領域要件を許可するために、各々のメッセージタイプ毎にそのメッセージタイプをさらに区分する。バッファサイズを縮小させるための他の考慮も組み込まれている。
【００１７】
したがって、本発明のアーキテクチャは、インタコネクトに対する出力メッセージを受け取るためのバッファと、そのメッセージを個々のメッセージタイプに復号化するための復号器と、上記バッファを通してのメッセージの受渡しを制御するための、上記バッファと上記復号器とに結合されている出力制御装置とを含む。
【００１８】
本発明は、別々の要求チャネルと応答チャネルとをサポートするために必要とされるインタコネクト管理オーバヘッドを回避する。本発明は、さらに、メッセージバックオフをサポートするメッセージ通信プロトコルの複雑性と、ソフトウェア管理デッドロック回復手順に関連した複雑性とを取り除く。
【００１９】
【発明の実施の形態】
本発明は、マルチノードコンピュータネットワークにおいてノード間のメッセージを制御する際にデッドロックを回避するためのコンピュータアーキテクチャを提供する。本発明は、ノードからの出力メッセージを一時的に記憶するように予め計算された最適サイズを有するメッセージ通信バッファを含む。メッセージはその処理要件とメッセージ通信プロトコルとにしたがって分類され、メッセージ通信バッファ内の予約割り当て量が個々のタイプのメッセージに割り当てられる。この予約割り当て量は、オーバフローを防止するために、未処理である可能性がある最大数のメッセージを常に制限する機構によって制御される。メッセージ通信バッファは、ノードが常に入力メッセージを処理することが可能であることを確実なものにするのに十分な大きさであり、それによって、デッドロックを回避し、順方向転送を促進する。上記バッファが空である時、または、上記バッファ内のデータが破損している時には、システム性能を向上させるために、上記バッファをバイパスすることも可能である。これに加えて、多数のメッセージを生成し通過を許可するマルチキャスト（同報通信）が存在するかどうかを判定するために、マルチキャストエンジンがメッセージヘッダから情報を受け取る。
【００２０】
図１は、複数のノード１０２とインタコネクト１０４とを有するコンピュータネットワーク１００を示す。各ノード１０２は、スタンドアロン型データ処理システム、または、ノード１０２の集合体で構成されているデータ処理システムの一部分のどちらかとして構成されている。後者の場合には、記憶装置および／または入出力（Ｉ／Ｏ）のような共通の資源が、個々のノードによって共有されている。これに加えて、各ノード１０２はネットワークインタフェースユニット（ＮＩＵ）１０６を含み、このネットワークインタフェースユニット１０６は個々のノード１０２をインタコネクト１０４に接続する。好ましくは、インタコネクト１０４は、接続されている個々のノード１０２相互間のポイントツーポイント接続を提供する。
【００２１】
図２は、入力キュー２０２Ａまたは２０２Ｂと出力キュー２０４Ａまたは２０４Ｂとを各々が含む２つのノード１０２Ａ、１０２Ｂのネットワークにおける、デッドロック条件を示すブロック図である。入力キュー２０２Ａ、２０２Ｂが入力ネットワークメッセージを記憶し、出力キュー２０４Ａ、２０２Ｂが出力ネットワークメッセージを記憶する。ネットワークメッセージは出力キュー２０４Ａまたは２０４Ｂからインタコネクト１０４を経由して入力キュー２０２Ａまたは２０２Ｂに進む。メッセージＲｅｑＢＡ  ６０２とメッセージＲｅｑＡＢ  ６０４とがノード１０２Ａとノード１０２Ｂとの間で転送される時にこれらを保持するために使用可能なバッファ領域がこれらのキューによってモデル化されている。宛先ノード１０２Ａまたは１０２Ｂがブロック状態になり、入力メッセージを処理できなくなると、さらに到着した入力メッセージはまずそのノードのそれぞれの入力キュー２０２Ａまたは２０２Ｂを埋めはじめ、最終的には、インタコネクト１０４を経て送出ノードのそれぞれの出力キュー２０４Ｂまたは２０４Ａまで後退する。
【００２２】
図２では、入力キュー２０２Ａ、２０２Ｂと出力キュー２０４Ａ、２０４Ｂは一杯になっている。メッセージＲｅｑＢＡ  ６０２とメッセージＲｅｑＡＢ  ６０４とが処理されて、入力キュー２０２Ａ、２０２Ｂの各々の先頭から削除されるまでは、上記キューの領域は解放されない。ノード１０２Ａは、対応する応答メッセージを出力キュー２０４Ａに送出することなしに、要求メッセージＲｅｑＢＡ  ６０２を処理することはできない。しかるに、出力キュー２０４Ａが一杯であり、かつ、この出力キュー２０４Ａは、ノード１０２Ｂの入力キュー２０２Ｂが領域を解放するまでは、領域を解放することができない。出力キュー２０４Ａが一杯ではなくなるまで、メッセージＲｅｑＢＡ  ６０２がブロックされる。同様に、出力キュー２０４Ｂが一杯なので、ノード１０２Ｂが要求メッセージＲｅｑＡＢ  ６０４の処理をブロックされ、かつ、ノード１０２Ａの入力キュー２０２Ａが領域を解放し終わるまでは、ノード１０２Ｂが要求メッセージＲｅｑＡＢ  ６０４を処理することができない。このようなデッドロック条件が存在する限り、ノード１０２は個々の要求を処理することができない。
【００２３】
図２では、デッドロック発生の４つの条件の各々が満たされている。まず第１に、入力キュー２０２Ａ、２０２Ｂと出力キュー２０４Ａ、２０４Ｂの各エントリは、ノード１０２Ａまたはノード１０２Ｂが発生した１つのネットワークメッセージが格納されればそれによって占有されるので、相互排除が存在する。第２に、ノード１０２Ａとノード１０２Ｂの各々は、その個々の入力キュー２０２Ａまたは２０２Ｂが新たなネットワーク要求を受け取ることを阻止し、これと同時に、各ノード１０２は、その個々の出力キュー２０４Ａまたは２０４Ｂにおいて領域が使用可能になるのを待機しているので、保持および待機が存在する。第３に、ネットワークメッセージはその宛先ノードにおいてだけ随意に削除されることが可能である（すなわち、ノード１０２Ａだけが入力キュー２０２Ａからメッセージを削除することが可能であり、ノード１０２Ｂだけが入力キュー２０２Ｂからメッセージを削除することが可能である）ので、横取り（ｐｒｅｅｍｐｔｉｏｎ）がない。そして、第４に、各ノード１０２は他のノード１０２がその個々の入力待ち行列２０２Ａまたは２０２Ｂ内の領域を解放するのを待機しているので、ノード１０２Ａとノード１０２Ｂの双方が環状待機の状態にある。
【００２４】
図２では、ネットワークメッセージのためのメッセージ通信バッファとして機能するキュー２０２Ａ、２０２Ｂ、２０４Ａ、２０４Ｂが別々に設けられている。このことは余分な順序付け上の制約を加え、デッドロックを発生しやすくする。しかし、上記バッファがキューとして実現されない場合でさえ、デッドロックが発生する可能性がある。これに加えて、こうしたメッセージ通信バッファが、ノード１０２とインタコネクト１０４との間に存在する。好ましい実施様態では、メッセージ通信バッファがＮＩＵ  １０６内にあり、このＮＩＵ  １０６はノード１０２の一部である。別の実施様態では、メッセージ通信バッファをノード１０２の他の部分および／またはインタコネクト１０４の中に含めることも可能である。
【００２５】
図３は、ノード内インタコネクト３１２（好ましくはシステムバス）によって接続された複数のプロセッサ３０２と記憶装置３０６とＩ／０  ３０８とＮＩＵ１０６とを含む実施様態における、図１のノード１０２のブロック図である。あるいは、ノード内インタコネクト３１２がクロスババックプレーン（ｃｒｏｓｓ−ｂａｒ  ｂａｃｋｐｌａｎｅ）であることも可能である。さらに、図３はノード１０２内の構成要素３０２、３０６、３０８を示しているが、本発明は、構成要素３０２、３０６、３０８、１０６が半導体チップの形で一体化されている別の組合せの形にも適用可能である。好ましくは、ノード１０２内のプロセッサ３０２と他の構成要素３０６、３０８とからの要求と応答とに対応して、ＮＩＵ１０６がネットワークメッセージを生成し受け取る。ＮＩＵ  １０６はメッセージ通信バッファ４２０を含み、インタコネクト１０４に接続されている。ネットワークメッセージが１つのノード１０２からＮＩＵ  １０６とインタコネクト１０４とを通過して別のノード１０２に進む。このネットワークメッセージはメッセージ通信バッファ４２０内に一時的に記憶される。
【００２６】
図４は、図３のＮＩＵ  １０６の１つの実施様態のブロック図であり、このＮＩＵ  １０６は、メッセージ通信バッファ４２０とその関連の制御回路系を含み、この制御回路系は、ノードインタフェース４０２と、メッセージタイプ復号器４０４と、出力制御装置４０８と、マルチプレクサ４１２と、マルチキャストエンジン４１６と、ネットワークインタフェース４１８とを含む。
【００２７】
ノード内コネクト３１２とＮＩＵ  １０６との間の通信点であるノードインタフェース４０２は、出力ネットワークメッセージを生成し、インタコネクト１０４からの入力ネットワークメッセージを受け取って処理する。
復号器４０４は、ノードインタフェース４０２から出力ネットワークメッセージを受け取り、その出力メッセージの処理要件とメッセージ通信プロトコルとにしたがって出力メッセージを個々のタイプに復号化する。この好ましい実施様態では、３つのタイプのメッセージ、すなわち、（１）高信頼トランザクションメッセージ、（２）通知メッセージ、（３）不信頼トランザクションメッセージがある。「トランザクション」は、ノード１０２がネットワーク内の他のノード１０２と通信しまたは資源を交換しようとする時に、ノード１０２によって開始される一連のネットワークメッセージを意味する。高信頼トランザクションメッセージは、ハードウェアによって確実に完了することを必要とするトランザクションに関連するメッセージであり、すなわち、このメッセージは、ノード１０２によって出力され、受け取られ、処理されることが常に保証されている。通知メッセージは、応答メッセージまたは他の応答メッセージを要求せずに宛先ノードに到着する個々のメッセージである。不信頼トランザクションメッセージは、ハードウェアによって確実に完了することを必要としないトランザクションに関するメッセージであるが、未完了のトランザクションを回復させるソフトウェア層によって管理されているメッセージである。ソフトウェアがトランザクションのタイムアウトを検査し、割り当てられているタイムアウトの範囲内でトランザクションが完了しない場合には、そのトランザクションを再び開始させることが可能である。その結果として、不信頼トランザクションメッセージをネットワークハードウェアが排除することが可能であり、すなわち、処理されることなくインタコネクト１０４から削除することが可能である。説明を理解し易くするために、確実に完了する必要がない個々のメッセージを通知メッセージとして類別する。これら３つのメッセージタイプの組合せが広範囲の通信トラヒックを代表する。
【００２８】
システム設計者は、システム要件に基づいてどのメッセージタイプを使用するかを選択する。例えば、高信頼トランザクションメッセージおよび／または通知メッセージは、共有メモリマルチプロセッサシステムにおいてキャッシュコヒーレンスおよび記憶整合性を維持するためのハードウェアベースのスキームに適している。これとは対照的に、不信頼トランザクションメッセージは、ソフトウェアベースの信頼性検査を有する、メッセージ受渡し基本命令を使用するシステムに適している。
【００２９】
出力制御装置４０８は、メッセージ通信バッファ４２０によるメッセージの蓄積を管理し、バッファ４２０内のメッセージを追跡する。出力制御装置４０８は、ノードインタフェース４０２と共に、各タイプのメッセージに関するバッファ４２０内の予約割り当て量を維持し、各メッセージタイプについてメッセージ数がバッファ４２０内の予約割り当て量を超えないことを確実なものにする。プログラム可能制御レジスタ（図示されていない）が出力制御装置４０８とノードインタフェース４０２とに対して各メッセージタイプに関する使用可能な予約割り当て量を通知する。
【００３０】
通知メッセージに関しては、ノード１０２がその割り当て量に達したら、出力制御装置４０８が、割り当て量に達したことをノードインタフェース４０２に信号で知らせる。高信頼トランザクションメッセージの場合には、ノードインタフェース４０２が、既に開始した未処理の高信頼トランザクションの数をカウントする。通知メッセージまたは高信頼トランザクションについて規定割り当て量に達した時には、ノードインタフェース４０２は、ノードインタフェース４０２により多くの当該タイプのメッセージを開始させる原因となる新たな要求を停止させるかまたは後退させる。ノード１０２が不信頼トランザクションメッセージの割り当て量に達すると、出力制御装置４０８は、不信頼トランザクションの発生を停止させるためにノードインタフェース４０２に信号を送る。ノードインタフェース４０２は、応答メッセージを必要とする、入力した不信頼トランザクションメッセージの全てをドロップすることも行なう。したがって、応答メッセージは発生させられない。ドロップされたメッセージは最終的に発信元ノード１０２においてトランザクションタイムアウトとなる。
【００３１】
出力制御装置４０８は、ネットワークメッセージをバッファ４２０からマルチプレクサ４１２に伝送する。これに加えて、出力制御装置４０８は、ネットワークメッセージをノードインタフェース４０２からマルチプレクサ４１２に直接伝送してバッファ４２０をバイパスすることも可能である。バッファ４２０をバイパスする場合には、出力制御装置４０８がライン４１４を介してマルチプレクサ４１２にエラー空信号（ｅｒｒｏｒ−ｅｍｐｔｙ  ｓｉｇｎａｌ）を送り、それによってマルチプレクサ４１２はノードインタフェース４０２からのネットワークメッセージを選択する。バッファ４２０が空の時に（性能の向上のために）、または、バッファ４２０からのメッセージ読取り時に訂正不可能なエラーが検出される時に、出力制御装置４０８はバッファ４２０をバイパスする。メッセージはバッファ４２０を稠密形式で占有するので、メッセージヘッダに相当するバッファ４２０の内容の一部に訂正不可能なエラーが発生するとバッファ４２０の内容全体が破損される。これは、上記ヘッダ内に指定された破損メッセージのサイズと後続メッセージの始点とが判別できないからである。
【００３２】
マルチプレクサ４１２はネットワークメッセージをマルチキャストエンジン４１６に転送し、マルチキャストエンジン４１６は、そのメッセージを１つ以上のノード１０２に転送するべきかどうかを決定する。マルチキャストエンジン４１６は、別々のメッセージを発生させて各宛先ノード１０２に送るために、メッセージヘッダ内の宛先情報を使用する。この好ましい実施様態では、マルチキャストエンジン４１６がバッファ４２０の外側にあり、マルチキャストメッセージがバッファ４２０の１つのエントリだけを占有するので、バッファ４２０のサイズが小さくなる。
【００３３】
ネットワークインタフェース４１８は、マルチキャストエンジン４１６からの出力ネットワークメッセージをインタコネクト１０４に伝送し、インタコネクト１０４からの入力ネットワークメッセージをノードインタフェース４０２に伝送する。
ノード１０２からの出力メッセージを一時的に記憶するバッファ４２０は、各メッセージタイプ毎の予約割り当て量を記憶するように予め計算されたサイズを有する。予約割り当て量の割当ては、バッファ４２０がオーバフローするのを防止するために、未処理である可能性があるメッセージの最大数を常に制限する機構によって管理される。したがって、バッファ４２０は、ノードが常に入力メッセージを処理することが可能であることを確実なものにするのに十分なサイズにされ、それによって、デッドロックを回避し、通信における順方向転送を促進する。
【００３４】
高信頼トランザクションメッセージのために予約されているバッファ４２０の割り当て量は、（１）ノード１つ当たりの未処理トランザクションの最大数と、（２）トランザクション１つ当たりのメッセージのファンアウトの最大数と、（３）各メッセージのサイズと、（４）高信頼の相互通信を必要とするノードの合計数の１／２との積によって決定される。少なくとも２つのバッファが環状待機に関与するのであるから、ノードの合計数の１／２が計算に使用される。個々のタイプのメッセージトランザクションに関するメッセージのファンアウトの計算を、図５から図８を参照して後に説明する。
【００３５】
通知メッセージのために予約されている各ノード１０２内のバッファ４２０の割り当て量は、ノード１０２が未処理のまま有する可能性がある通知メッセージの個数によって決定される。通知メッセージは、発信元ノードのノードインタフェース４０２からその通知メッセージが送出される時点から、その通知メッセージが上記発信元ノードのバッファ４２０を出ていくまで、未処理のままである。バッファ領域の計算は出力バッファ４２０に関して行われるので、宛先ノード１０２に通知メッセージが到着する前に通知メッセージの未処理数のカウントを減らしても良い。
【００３６】
不信頼トランザクションメッセージに割り当てられている割り当て量は、そのようなトランザクションの予測頻度によって決定され、その割り当て量のオーバフローが稀にしか起こらないような大きさのサイズにされる。
任意の時刻においてバッファ４２０を占有できるメッセージの最大数を表すバッファ４２０の全体サイズは、各タイプのメッセージに関して必要な空き領域の合計である。これに加えて、そのシステムが主に採用する通信トラヒックのパターンに基づいて、システム構成に適合するようにバッファ４２０が区切られる。システム設計者は、バッファ４２０を区切るために、出力制御装置４０８内とノードインタフェース４０２内のプログラム可能制御要素を変更する。例えば、並列処理コンピュータシステムでは、共有メモリトラヒック構成要素が高信頼トランザクションと通知メッセージとを必要とし、メッセージ受渡しトラヒック構成要素は通知メッセージと不信頼トランザクションメッセージとを必要とする。例えば、メッセージ受渡しだけのシステムでは、バッファ４２０は通知メッセージと不信頼トランザクションメッセージとのためだけに区切られることになる。こうして、バッファ４２０は、上記システム内の通信トラヒックパターンに適合するようにカスタマイズされ、あらゆる構成に対してフルに利用される。
【００３７】
本発明によるデッドロック回避方法を具体化する時には、メッセージ通信バッファ４２０の合計サイズが、考慮されるべき重要事項である。したがって、本発明は、このバッファ４２０のサイズを減少させるために幾つかの機構を組み合わせる。まず第１に、本発明は、バッファ４２０に関して容量をより厳密に計算することを可能にするために、各メッセージタイプにおけるさらなる細分化を可能にする。例えば、この好ましい実施様態では、調停トランザクションが正規トランザクションよりも最大メッセージファンアウトが小さいので、本発明は、高信頼トランザクションメッセージタイプにおいて、調停トランザクションと正規トランザクションとを区別する。したがって、より厳密なファンアウト数を各タイプのトランザクションに関して使用することが可能であり、この結果として、高信頼トランザクションメッセージに関して必要なバッファサイズがより小さくなる。第２に、ノード１０２間のメッセージ転送を確実なものとするために、本発明がネットワーク通信層の下の層に依存することが好ましい。この好ましい実施様態では、これは、ネットワークインタフェース４１８の形で具体化されている。伝送を確実なものにすることにより、ネットワークメッセージ通信層におけるアクノリッジが必要でなくなり、それによってファンアウトが著しく削減される。第３に、マルチキャストエンジン機構が、マルチキャストメッセージがバッファ４２０内の１つのエントリだけを占有することを可能にし、バッファ４２０のサイズをさらに小さくする。第４に、本発明は、好ましくはバッファ４２０内に稠密形式でメッセージを記憶する。したがって、データを保持しないメッセージがバッファ４２０を占有する領域は、データを保持するメッセージがバッファ４２０内に占有する領域に比べて小さい。各メッセージのサイズがそのヘッダにおいて指定される。
【００３８】
この好ましい実施様態では、バッファ４２０は、１つの半導体チップの形でＮＩＵ  １０６内に含まれているスタティックＲＡＭ（ＳＲＡＭ）である。例えば、中規模マルチプロセッサ相互接続ネットワークは、合計３２個のノードを有し、４個までのノードで各グループが構成される複数のグループを有し、各グループ内のノードは同じ１つの記憶装置を共用するので高信頼通信が必要である。各ノード１０２は、標準ＩｎｔｅｌTMＱｕａｄ  Ｐｅｎｔｉｕｍ−ＰｒｏTM  ＡＰ４５０ＧＸサーバプラットフォームを含み、このサーバプラットフォームは、４個のＰｅｎｔｉｕｍ−Ｐｒｏプロセッサ３０２と、メモリサブシステム用の１ギガバイトまでのダイナミックＲＡＭ（ＤＲＡＭ）３０６と、Ｉ／０  ３０８取付け用の２つのＰＣＩブリッジとを含む。ＮＩＵ  １０６は、共有メモリタイプの通信トラヒックとメッセージ受渡しタイプの通信トラヒックの両方をサポートする、１６ビットから４８ビットまでのネットワークメッセージを生成する。この実施様態では、バッファ４２０は、８キロバイトの先入れ先出し（ＦＩＦＯ）ＳＲＡＭとして実現されている。
【００３９】
別の実施様態では、バッファ４２０を、ＮＩＵ  １０６を含むローカルノード１０２（図３）内のＤＲＡＭ  ３０６の予約部分の中に展開することが可能である。この別の実施様態は、集積回路チップ上のバッファ４２０の部分が何時オーバフローしたかを検出し、ＤＲＡＭ  ３０６に対するダイレクトメモリアクセス（ＤＭＡ）を介したマネジメントスワッピングを行う。ＮＩＵ  １０６は、ソフトウェアの介入またはインタコネクト１０４内に発生させられるべき新たなネットワークメッセージを必要とせずに、上記ＤＭＡを行う。ＤＲＡＭが比較的安価であるので、バッファ２４０の大きな領域と低コストでＤＲＡＭ内に割り当てることが可能である。より高い性能を得るために、バッファ４２０のオンチップ部分が、オーバフローが稀であるように適切なサイズにされる。
【００４０】
図５から図８は、各タイプの通信トランザクションに関するメッセージファンアウトの計算を示している。ファンアウトとは、１つのトランザクションに関してインタコネクタ１０４内で転送されうるメッセージの数である。第１のノード１０２（発信元ノード１０２）が、要求メッセージを第２のノード１０２に送ることによってトランザクションを開始する。これに応答して、第２のノード１０２が発信元ノード１０２に対する応答を発生させる。第２のノードは、同様にまたはその代わりに、第３のノードまたは一連のノード１０２に対するメッセージ連鎖を発生する。トランザクションが完了すると、発信元ノード１０２は完了メッセージを受け取る。発信元ノード１０２が要求メッセージを送出する時点から発信元ノード１０２が完了メッセージを受け取るまで１つのトランザクションが存在する。任意の時刻においてノード１０２は、進行中の一定の数の未処理トランザクションを有する。
【００４１】
「調停」と呼ばれる新たな要求がトランザクションの途上で発生させられる場合がある。例えば、追い立てメッセージ（ｅｖｉｃｔｉｏｎ  ｍｅｓｓａｇｅ）が、トランザクションを処理するために必要な資源を解放するために、必要とされることもあり得る。調停は、バッファ領域計算における新たなトランザクションの開始として考慮される。
【００４２】
図５は、基本的な要求−応答トランザクションを示す。ノード１０２Ａが要求メッセージＡＢをノード１０２Ｂに送り、ノード１０２Ｂは、ノード１０２Ａに対する応答メッセージＢＡで応答する。ノード１０２Ｂが応答メッセージＢＡを発生させる前に、要求メッセージＡＢがノード１０２Ｂで受信されなければならない。したがって、常に、インタコネクト１０４内には、転送中のメッセージ（ＡＢまたはＢＡのどちらか）は１つだけしかない。したがって、要求−応答トランザクションに関するファンアウトは１である。
【００４３】
図６は、要求転送トランザクションを示す。ノード１０２Ａがノード１０２Ｂに要求メッセージＡＢを送る。その後で、ノード１０２Ｂがノード１０２Ｃに要求メッセージＡＢ（この時点ではメッセージＢＣ）を送る。さらに、ノード１０２Ｃがノード１０２Ａに対して応答メッセージＣＡで応答する。ノード１０２がその次のメッセージを発生させる前に、メッセージＡＢ、メッセージＢＣ、メッセージＣＡの各々がその宛先ノード１０２によって受信されなければならない。すなわち、インタコネクト１０４内には常に多くとも１つのメッセージが存在し、したがって、このトランザクションに関するファンアウトは１である。
【００４４】
図７は、中間応答を伴う要求転送トランザクションを示す。ノード１０２Ａは要求メッセージＡＢをノード１０２Ｂに送る。その後で、ノード１０２Ｂは、その要求メッセージＡＢ（この時点ではメッセージＢＣ）をノード１０２Ｃに転送すると同時に中間応答メッセージＢＡをノード１０２Ａに送る。ノード１０２ＣはメッセージＢＣに応答して、最終応答メッセージＣＡによってノード１０２Ａに応答する。中間応答メッセージＢＡが、要求メッセージＢＣまたは最終応答メッセージＣＡのどちらかと同時にインタコネクタ１０４内で転送中である可能性があるので、このトランザクションに関するファンアウトは２である。
【００４５】
図８は、要求−応答トランザクションに応答して発生させられる調停トランザクションを示す。ノード１０２Ｂは、ノード１０２Ａからの要求メッセージＡＢを処理すると同時に、ノード１０２Ｃに対する調停要求メッセージＢＣも発生する。ノード１０２Ｃは調停応答メッセージＣＢをノード１０２Ｂに返す。ノード１０２Ａからノード１０２Ｂへのトランザクションと、ノード１０２Ｂからノード１０２Ｃへのトランザクションとの両方が、単純な要求−応答連鎖であるので、各トランザクションに関するファンアウトは１である。
【００４６】
図９はメッセージ通信バッファ４２０の具体例である。この図９の具体例では、ネットワークメッセージ５１０−１からネットワークメッセージ５１０−ｎである複数のネットワークメッセージがバッファ４２０を通過する時に、バッファ４２０が、これらのネットワークメッセージを記憶する。各ネットワークメッセージ５１０は、ヘッダ５０２と変数データ５０４とを含む。この好ましい実施様態では、ヘッダ５０２がメッセージタイプ５０２−２、メッセージ発信元５０２−４、メッセージ宛先５０２−６、メッセージサイズ５０２−８を含む。「メッセージタイプ」フィールド５０２−２は、メッセージ５１０タイプが高信頼トランザクションメッセージ、通知メッセージ、または、不信頼トランザクションメッセージのどれであるかを表示する。「メッセージ発信元」フィールド５０２−４はメッセージ５１０の発信元ノード１０２を表示する。「メッセージ宛先」フィールド５０２−６は、メッセージ５１０が送られるべきノード１０２を表示する。「メッセージサイズ」フィールド５０２−８は、メッセージ５１０のサイズを表示する。別の実施様態では、ヘッダ５０２が、メッセージ５１０に関する他の情報を伴う他のフィールドを含むことが可能である。
【００４７】
上記では、本発明の好ましい実施様態を参照しながら、本発明を説明してきた。この開示内容を理解することによって、他の実施様態が当業者には明らかになるだろう。例えば、本発明は他の構成の形で実現されることが可能である。さらに、本発明は、本明細書で説明しているネットワークシステム以外のネットワークシステムと組み合わせて効果的に使用されることが可能である。したがって、上記の好ましい実施様態に対するこうした変形例や他の変形例が添付の請求範囲内に含まれている。
【図面の簡単な説明】
【図１】ネットワークインタフェースを経由してインタコネクトに接続されている複数のノードを有するコンピュータネットワークを示すブロック図である。
【図２】２ノード形ネットワークにおけるデッドロック条件を示すブロック図である。
【図３】図１のノードのブロック図である。
【図４】図３のネットワークインタフェースユニット（ＮＩＵ）のブロック図である。
【図５】各タイプのメッセージトランザクションに関するメッセージファンアウトの計算を示す。
【図６】各タイプのメッセージトランザクションに関するメッセージファンアウトの計算を示す。
【図７】各タイプのメッセージトランザクションに関するメッセージファンアウトの計算を示す。
【図８】各タイプのメッセージトランザクションに関するメッセージファンアウトの計算を示す。
【図９】図４のメッセージ通信バッファの実施様態を示す。
【図１】
0004509248.tif 000002
【図２】
0004509248.tif 000003
【図３】
0004509248.tif 000004
【図４】
0004509248.tif 000005
【図５】
0004509248.tif 000006
【図６】
0004509248.tif 000007
【図７】
0004509248.tif 000008
【図８】
0004509248.tif 000009
【図９】
0004509248.tif 000010