(57)【要約】  ネットワークにおいてパケットをルーティングするための方法および装置について記載する。ネットワークは、n個の層を含むノードの階層構造によって特徴付けられるトポロジを有する。Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。この方法は、第1のノードにおいて少なくともパケットのパケットヘッダーを受信するステップと、パケットヘッダーに基づいて、層L、層L+1、または層L-1のいずれかにおける第2のノードにパケットを送信するかどうかを決定するステップとを含む。パケットは、第1のノードで受信されるとすぐ、パケット全体の受信を待つことなく、第1のノードからの送信前にパケットをコピーすることなく、第2のノードに送信することができる。
2012521687.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおいてパケットをルーティングする方法であって、前記ネットワークが、n個の層を備えるノードの階層構造によって特徴付けられるトポロジを有し、Lが前記構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表し、前記方法が、
第1のノードにおいて少なくともパケットのパケットヘッダーを受信するステップと、
前記パケットヘッダーに基づいて、層L、層L+1、または層L-1のいずれかにおける第2のノードに前記パケットを送信するかどうかを決定するステップと、
前記パケットを、前記第1のノードで受信されるとすぐ、前記パケット全体の受信を待つことなく、前記第1のノードからの送信前に前記パケットをコピーすることなく、前記第2のノードに送信するステップと
を含む方法。
【請求項２】
前記n個の層が、n-1個のスイッチノードの層および1個の計算ノードの層を含み、前記構造における各ノードが、ユニットごとに複数のノードを有するいくつかのユニットにグループ分けされたノードを含み、前記計算層以外の層における各ノードが、前記構造における次に低い層におけるユニットのスイッチノードを備え、
前記第1のノードがスイッチノードであり、
前記層Lにおける第2のノードにパケットを送信するステップが、ポイントツーポイントリンクによって前記第1のノードと同じユニット内の前記第2のノードに前記パケットを送信するステップを備え、
前記層L+1または前記層L-1における第2のノードにパケットを送信するステップが、ポイントツーポイントリンクによって前記第1のノードと異なるユニット内の前記第2のノードに前記パケットを送信するステップを備える
請求項1に記載の方法。
【請求項３】
n-1個のスイッチノードの層および1個の計算ノードの層を含むn個の層を備えるノードの階層構造を備え、前記階層構造における各層がノードの1つまたは複数のユニットを含み、Lが、前記構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表し、ユニット内のノードの数が1より大きく、
前記スイッチノードが、
少なくともパケットのパケットヘッダーを受信し、
前記パケットヘッダーに基づいて、層L、層L+1、または層L-1のいずれかにおける第2のノードに前記パケットを送信するかどうかを決定し、
メッセージを備える1つまたは複数のパケットを、前記スイッチノードで受信されるとすぐ、前記パケット全体の受信を待つことなく、前記スイッチノードからの送信前に前記パケットをコピーすることなく、前記第2のノードに送信する
ように構成される
システム。
【請求項４】
前記計算ノードがそれぞれ
少なくとも1つのプロセッサと、
通信ハードウェアと、
メモリと
を含む請求項3に記載のシステム。
【請求項５】
前記少なくとも1つのプロセッサがアプリケーションプロセッサ、およびオペレーティングシステムプロセッサを備える請求項4に記載のシステム。
【請求項６】
前記通信ハードウェアがフィールドプログラマブルゲートアレイ(FPGA)を備える請求項4に記載のシステム。
【請求項７】
前記通信ハードウェアが前記計算ノードへのトラフィックを監視するように構成される請求項4に記載のシステム。
【請求項８】
前記通信ハードウェアが
前記計算ノードにおいて受信されたメッセージを前記プロセッサに向けて送り出し、
異なるノードに送信するために前記プロセッサからのメッセージを受信する
ように構成される請求項4に記載のシステム。
【請求項９】
前記計算層以外の層における各ノードが、前記構造における次に低い層におけるユニットのスイッチノードを備え、
ユニットごとに、
前記ユニット内の各ノードが、ポイントツーポイントリンクによって、前記ユニット内の互いのノードに接続され、
前記ユニット内の各ノードが、ポイントツーポイントリンクによって、前記ユニットのローカルスイッチノードに接続され、
前記ユニット内の各ノードが、前記ユニットのローカルブロードキャストネットワークによって、前記ユニット内の互いのノード、および前記ローカルスイッチノードに接続される
請求項3に記載のシステム。
【請求項１０】
前記スイッチノードがそれぞれ
プロセッサと、
通信ハードウェアと
を備える請求項3に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子通信に関する。
【背景技術】
【０００２】
ノードおよびリンクのネットワークの配列は、ネットワークトポロジによって定義される。ネットワークトポロジは、ネットワークノード間の物理的および論理的な相互接続を決定することができ、そこで各ノードは、1つまたは複数の他のノードへの1つまたは複数のリンクを有する。ネットワークの物理的なトポロジは、ノード間の物理的な接続の構成によって決定される。構成は、例えば輪、星形、線、格子、超立方体、またはトーラスなど、多次元の幾何学形状によって表され得る。ネットワークの論理的なトポロジは、ノード間のデータの流れによって決定される。
【０００３】
処理ノードのネットワークは、スーパーコンピューティングアプリケーションに使用され得る。例えば、大きいスーパーコンピューティングアプリケーションは、ネットワークの異なる処理ノード上で稼働する命令の異なるサブセットに分割され得る。待ち時間を短縮し、効率を向上させるために、ネットワーク全体にわたるトラフィックの分散、およびローカルレベルでのノード間の通信の最大化が好ましい。
【０００４】
通常、ネットワークトポロジの複雑さが増すにつれて、ネットワークのアドレス指定およびルーティングの方式は複雑さが増す。複雑なルーティングテーブルは、実施するのにかなりの中央処理装置(CPU)の時間を必要とする可能性がある。従来のパケットのルーティングは、パケットのヘッダーにおける宛先アドレスを復号し、パケットを転送することができるようになる前に、パケットがノードで完全に受信されなければならないことを必要とし、結果として待ち時間がもたらされる。待ち時間も、複雑なアドレス指定方式に伴って増加し得る。複雑なネットワークトポロジでは、ノードに対するホップカウントの比が高くなる可能性があり、この場合、ホップごとに複数のクロックサイクル分のパケット待ち時間をもたらすことになる。
【発明の概要】
【課題を解決するための手段】
【０００５】
本明細書は、ネットワークトポロジに関連するシステム、方法、およびコンピュータプログラム製品について記載する。一般に、一態様において、本発明は、ノードの階層構造を含むネットワークを特徴とする。ノードの構造は、n-1個のスイッチノードの層および1個の計算ノードの層を含むn個の層を含む。その構造における各層は、いくつかのユニットにグループ分けされたmn-L個のノードを含み、ここでmは、ユニット内のノードの数を表し、1より大きい整数である。Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。計算層以外の層における各ノードは、その構造における次に低い層におけるユニットのスイッチノードを含む。ユニットごとに、ユニット内の各ノードは、ポイントツーポイントリンクによって、ユニット内の互いのノードに接続され、ユニット内の各ノードは、ポイントツーポイントリンクによって、そのユニットのローカルスイッチノードに接続され、ユニット内の各ノードは、ユニットのローカルブロードキャストネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードに接続される。
【０００６】
ネットワークの実装形態は、以下の特徴のうちの1つまたは複数を含み得る。各計算ノードは、1つまたは複数のアプリケーションの命令を実行するよう動作可能な処理要素を含み得る。その構造における最下層は、計算ノードの層とすることができ、mn個の計算ノードを含み得る。ユニット内の各ノードは、Ｅｔｈｅｒｎｅｔ（登録商標）ネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードに接続することができる。各計算ノードは、処理要素、コントローラ、およびメモリを含み得る。各計算ノードは、フィールドプログラマブルゲートアレイとして実装される通信ハードウェアを含み得る。
【０００７】
一般に、別の態様において、本発明は、n個の層を含むノードの階層構造を含むネットワークを特徴とする。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含む。その構造における各層は、ノードの1つまたは複数のユニットを含み、Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表し、ユニット内のノードの数は、1より大きい。計算層以外の層における各ノードは、その構造における次に低い層におけるユニットのスイッチノードを含む。ユニットごとに、ユニット内の各ノードは、ポイントツーポイントリンクによって、ユニット内の互いのノードに接続され、ユニット内の各ノードは、ポイントツーポイントリンクによって、そのユニットのローカルスイッチノードに接続され、ユニット内の各ノードは、ユニットのローカルブロードキャストネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードに接続される。
【０００８】
ネットワークの実装形態は、以下の特徴のうちの1つまたは複数を含み得る。1つまたは複数のユニットに含まれる1つまたは複数のポイントツーポイントリンクを非アクティブ化することができる。その構造における層の各ユニットは、同じ数のノードを有し得る。その構造における各層の各ユニットは、同じ数のノードを有し得る。各ユニットは、8つのノードを含む2×2×2の立方体によって表されるローカルの3次元ネットワークトポロジを含み得る。各計算ノードは、1つまたは複数のアプリケーションの命令を実行するよう動作可能な処理要素を含み得る。
【０００９】
その構造における最下層は、計算ノードの層とすることができる。ユニット内の各ノードは、Ｅｔｈｅｒｎｅｔ（登録商標）ネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードに接続することができる。各計算ノードは、処理要素、コントローラ、およびメモリを含み得る。各計算ノードは、フィールドプログラマブルゲートアレイとして実装される通信ハードウェアを含み得る。
【００１０】
一般に、別の態様において、本発明は、ノードの階層構造およびプロセッサを含むネットワーク接続デバイスを特徴とする。ノードの階層構造は、n-1個のスイッチノードの層および1個の計算ノードの層を含むn個の層を含む。Lは、階層構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。プロセッサは、パケットにおいて受信されるn個のビットの組を処理するように構成され、各計算ノードは、n個のビットの組によって完全にアドレス指定され、層Lの各スイッチノードは、n-L個の最上位ビットの組によって完全にアドレス指定される。
【００１１】
ネットワーク接続デバイスの実装形態は、以下の特徴のうちの1つまたは複数を含み得る。n個のビットの組のそれぞれは、同じ数のビットを含み得る。いくつかの実装形態において、各層は、ノードの1つまたは複数のユニットを含み、各ユニットは、ローカルの2×2×2の立方体状ネットワーク(cubic network)を含み、3次元のそれぞれの辺、x、y、zごとに2つのノードを備え、各ノードは、{0,0,0}から{1,1,1}の範囲の3次元のアドレス{x,y,z}を使用して立方体状ネットワーク内に論理的に配置され、この場合、立方体のネットワーク内に各ノードを論理的に配置する3次元アドレスは、n個のビットの組のうちの1つを含む。いくつかの実装形態において、各層は、ノードの1つまたは複数のユニットを含み、各ユニットは、ローカルの2×4×4のネットワークを含み、x次元の辺ごとに2つのノード、ならびにyおよびz次元のそれぞれの辺ごとに4つのノードを備え、各ノードは、{0,0,0,0,0}から{1,1,1,1,1}の範囲の3次元のアドレス{x,y1,y2,z1,z2}を使用してローカルネットワーク内に論理的に配置され、この場合、ローカルネットワーク内に各ノードを論理的に配置する3次元アドレスは、n個のビットの組のうちの1つを含む。
【００１２】
一般に、別の態様において、本発明は、ネットワークにおいてパケットをルーティングする方法を特徴とする。ネットワークは、n個の層を含むノードの階層構造によって特徴付けられるトポロジを有する。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含み、Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。構造の層Lのスイッチノードにおいてパケットが受信される。パケットは、n個のビットの組を含む第1のアドレスを備えるヘッダーを含む。スイッチノードは、n-L個のビットの組を含む第2のアドレスを有する。パケットは、第1のアドレスおよび第2のアドレスの比較に基づいて、層L、層L+1、または層L-1のいずれかにおけるノードに転送される。
【００１３】
いくつかの実装形態において、第1のアドレスのn-L個の最上位ビットの組が第2のアドレスのn-L個のビットの組に一致する場合、ポイントツーポイントリンク上で、第1のアドレスのn-L+1個の最上位ビットの組によって完全にアドレス指定された構造の層L-1のノードにメッセージを転送することができる。n-L個の組は一致しないが、第1のアドレスのn-L-1個の最上位ビットの組が第2のアドレスのn-L-1個の最上位ビットの組に一致する場合、ポイントツーポイントリンク上で、第1のアドレスのn-L個の最上位ビットの組によって完全にアドレス指定された構造の層Lのスイッチノードにメッセージを転送することができる。第1のアドレスのn-L-1個の最上位ビットの組が第2のアドレスのn-L-1個の最上位ビットの組に一致しない場合、ポイントツーポイントリンク上で、第2のアドレスのn-L-1個の最上位ビットの組によって完全にアドレス指定された構造の層L+1のスイッチノードにメッセージを転送することができる。
【００１４】
一般に、別の態様において、本発明は、ネットワークにおいてパケットをルーティングする方法を特徴とし、ネットワークは、n個の層を有するノードの階層構造によって特徴付けられるトポロジを有する。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含み、Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。パケットは、層Lの計算ノードから層Lの第2の計算ノードまたは層L+1のスイッチノードのいずれかに送信され得る。パケットは、n個のビットの組を含む第1のアドレスを備えるヘッダーを含み、計算ノードは、n個のビットの組を含む第2のアドレスを有する。パケットは、第1および第2のアドレスの比較に基づいて送信され得る。
【００１５】
いくつかの実装形態において、第1のアドレスのn-1個の最上位ビットの組が第2のアドレスのn-1個の最上位ビットの組に一致する場合、ポイントツーポイントリンク上で、第1のアドレスのn個のビットの組によって完全にアドレス指定された構造の層Lの第2の計算ノードにメッセージを転送することができる。n-1個の組が一致しない場合、ポイントツーポイントリンク上で、第2のアドレスのn-1個の最上位ビットの組によって完全にアドレス指定された構造の層L+1のスイッチノードにメッセージを転送することができる。
【００１６】
一般に、別の態様において、本発明は、ネットワークにおいてパケットをルーティングする方法を特徴とし、ネットワークは、n個の層を含むノードの階層構造によって特徴付けられるトポロジを有する。Lは、階層構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表す。この方法は、第1のノードにおいて少なくともパケットのパケットヘッダーを受信するステップと、パケットヘッダーに基づいて、層L、層L+1、または層L-1のいずれかにおける第2のノードにパケットを送信するかどうかを決定するステップとを含む。パケットは、第1のノードで受信されるとすぐ、パケット全体の受信を待つことなく、第1のノードからの送信前にパケットをコピーすることなく、第2のノードに送信される。
【００１７】
この方法の実装形態は、以下の特徴のうちの1つまたは複数を含み得る。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含み得る。その構造における各層は、ユニットごとに複数のノードを有するいくつかのユニットにグループ分けされたノードを含むことができ、計算層以外の層における各ノードは、その構造における次に低い層におけるユニットのスイッチノードを含み得る。第1のノードは、スイッチノードとすることができ、層Lにおける第2のノードにパケットを送信するステップは、ポイントツーポイントリンクによって第1のノードと同じユニット内の第2のノードにパケットを送信するステップを含み得る。層L+1または層L-1における第2のノードにパケットを送信するステップは、ポイントツーポイントリンクによって第1のノードと異なるユニット内の第2のノードにパケットを送信するステップを含み得る。
【００１８】
一般に、別の態様において、本発明は、n個の層を含むノードの階層構造を含むシステムを特徴とする。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含み、階層構造における各層は、ノードの1つまたは複数のユニットを含む。Lは、その構造における層を表し、かつ整数であって、L=0が最下層を表し、L=n-1が最上層を表し、ユニット内のノードの数は、1より大きい。スイッチノードは、少なくともパケットのパケットヘッダーを受信し、パケットヘッダーに基づいて、層L、層L+1、または層L-1のいずれかにおける第2のノードにパケットを送信するかどうかを決定し、メッセージを形成する1つまたは複数のパケットを、スイッチノードで受信されるとすぐ、パケット全体の受信を待つことなく、スイッチノードからの送信前にパケットをコピーすることなく、第2のノードに送信するように構成される。
【００１９】
システムの実装形態は、以下の特徴のうちの1つまたは複数を含み得る。計算ノードはそれぞれ、少なくとも1つのプロセッサ、通信ハードウェア、およびメモリを含み得る。少なくとも1つのプロセッサは、アプリケーションプロセッサ、およびオペレーティングシステムプロセッサを含み得る。通信ハードウェアは、フィールドプログラマブルゲートアレイ(FPGA)を含み得る。通信ハードウェアは、計算ノードへのトラフィックを監視するように構成され得る。通信ハードウェアは、計算ノードにおいて受信されたメッセージをプロセッサに向けて送り出し、異なるノードに送信するためのプロセッサからのメッセージを受信するように構成され得る。計算層以外の層における各ノードは、その構造における次に低い層におけるユニットのスイッチノードを含み得る。ユニットごとに、ユニット内の各ノードは、ポイントツーポイントリンクによって、ユニット内の互いのノードに接続することができ、ユニット内の各ノードは、ポイントツーポイントリンクによって、そのユニットのローカルスイッチノードに接続することができ、ユニット内の各ノードは、ユニットのローカルブロードキャストネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードに接続することができる。スイッチノードはそれぞれ、プロセッサおよび通信ハードウェアを含み得る。
【００２０】
実装形態は、以下の利点のうちの1つまたは複数を実現することができる。階層的な3次元(3-D)ネットワークトポロジによって、簡単なアドレス指定方式が可能になり、ルーティングは、本質的にネットワークトポロジにリンクされ、待ち時間が短縮された状態で高速なメッセージ配信を促進する。また、ネットワークトポロジは、密なローカルの処理ノードの組の利点も提供し、ローカルレベルにおけるトラフィックの分散を容易にする。このネットワークトポロジは、ポイントツーポイントおよびマルチキャストの通信において、ノードに対するホップカウントの比を低減する。プロトコルはストリーム式であり、これによって、パケットがスイッチノードで完全に受信される前に、スイッチノードがメッセージの転送を開始することができ、待ち時間をさらに最低限に抑える。マルチキャストおよびブロードキャスト通信は、ネットワーク全体を使用することなく、パケット配信に必要なネットワーク層のみを使用する。
【００２１】
本発明の1つまたは複数の実施形態の詳細が添付の図面および以下の説明に記載されている。本発明の他の特徴、目的、および利点は、説明および図面、ならびに特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００２２】
【図１】ネットワークトポロジを有するネットワーク例を示す図である。
【図２】階層的なツリーネットワーク例を示す図である。
【図３】階層的な3-Dネットワーク例を示す図である。
【図４】図2の階層的なツリーネットワークのアドレス指定方式の例を示す図である。
【図５】階層的な3-Dネットワークの2×2×2のユニットについてのアドレス指定の例を示す図である。
【図６】階層的な3-Dネットワークの2×4×4のユニットについてのアドレス指定の例を示す図である。
【図７】ネットワークトポロジを有するネットワーク例を示す図である。
【図８】階層的なツリーネットワーク例を示す図である。
【図９】図8の階層的なツリーネットワークについてのアドレス指定方式の例を示す図である。
【図１０】図4のアドレス指定方式を使用して、図2の階層的なツリーネットワークにおいてスイッチノードで受信されるメッセージをルーティングするためのプロセス例を示すフローチャートである。
【図１１】図4のアドレス指定方式を使用して、図2の階層的なツリーネットワークにおける計算ノードから発せられるメッセージをルーティングするためのプロセス例を示すフローチャートである。
【図１２】コンピュータシステム例を示す概要図である。
【発明を実施するための形態】
【００２３】
様々な図における類似の参照記号は、類似の要素を示す。
【００２４】
ノードの階層構造を含むネットワークトポロジを有するネットワークについて説明する。いくつかの実装形態において、階層構造は、n-1個のスイッチノードの層および1個の計算ノードの層のn個の層を含み得る。その構造における各層は、1つまたは複数のユニットを含むことができ、ユニットは、1組のノードを含む。層内の各ユニットは、異なる層におけるユニットと同じ数のノードまたは異なる数のノードを有し得る。計算層以外の層における各ノードは、その構造における次に低い層におけるユニットのスイッチノードを含み得る。ユニット内の各ノードは、ポイントツーポイントリンクによって、ユニット内の互いのノード、およびユニットのローカルスイッチノードに接続することができる。ユニット内の各ノードは、ユニットのローカルブロードキャストネットワークによって、ユニット内の互いのノード、およびローカルスイッチノードにも接続することができる。
【００２５】
ネットワークトポロジは、階層的な(例えばツリー)ネットワークトポロジおよび完全に接続されたネットワークトポロジの混合である。いくつかの実装形態において、階層構造における層の各ユニットは、2×2×2の配列で8つの完全に接続されたノードを有しており、これは、3次元のそれぞれにおける辺ごとに2つのノードを備える立方体状ネットワークとして視覚化することができる。メッセージは、簡単なアドレス指定方式を使用して、この3-Dネットワークを介してルーティングすることができる。ユニットにローカルのこの3-Dネットワークを、構造の層を通じて階層的に繰り返して、ネットワーク全体を通じて同じ属性を維持することができる。この配列によって、複雑なルーティングテーブル、または実施にかなりのCPU時間がかかる他の複雑な方式の必要なく、複雑なネットワークを実現することができる。
【００２６】
ネットワークトポロジ100の例が図1に示されている。特に、図1は、ネットワークトポロジ100の階層構造の最下層における計算ノード104のユニット102を示す。ユニット102のローカルネットワークトポロジが、リーフノードとして知られる8つの計算ノード104の周りに形成されている。
【００２７】
いくつかの実装形態において、各計算ノード104は、1つまたは複数のアプリケーションの命令を実行するように動作可能な処理要素を含む。いくつかの実装形態において、異なる計算ノード104は、異なる処理要素を含む。いくつかの実装形態において、いくつかの計算ノード104は、異なるまたは一意の処理要素を含み、残りの計算ノード104は、均一の処理要素を含む。いくつかの実装形態において、1つまたは複数のスイッチノード108は、例えばトラフィック管理のための処理要素を含む。
【００２８】
各計算ノード104は、ポイントツーポイントリンク106(例えば、高速のリンク間ノード)によってユニット102の互いの計算ノード104に接続される。各計算ノード104は、ポイントツーポイントリンク110(例えば、高速のスイッチ-ノードリンク)によって次に高い層におけるユニットのスイッチノード108に接続される。各計算ノード104は、ユニット102のローカルブロードキャストネットワーク112によって、ユニット102の互いの計算ノード104、およびスイッチノード108にも接続される。スイッチノード108は、ネットワークトポロジ100の階層構造の他のユニットの他のローカルブロードキャストネットワークに、ユニット102のローカルブロードキャストネットワーク112をブリッジすることができる。ローカルブロードキャストネットワーク112は、ユニット102のすべての計算ノード104、またはユニット102の計算ノード104のサブセットとの通信を可能にする。
【００２９】
オペレーティングシステム(OS)ソフトウェアは、各ノードおよびスイッチにおいてネットワーク全体にわたって分散することができる。OSソフトウェアは、ローカルサービス、およびシステム全体のスーパバイザ機能を含むことができる。いくつかの実装形態において、各計算ノード104は、Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク114によって、ユニット102の互いの計算ノード104、およびスイッチノード108にも接続される。Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク114は、アプリケーションソフトウェアに依存しないシステム管理機能(例えば、低データレートシステムのメンテナンスおよび監視)に使用することができる。Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク114における通信の例には、CPU温度、時間同期、および送信制御プロトコル(TCP)についてのログ情報がある。いくつかの実装形態において、ネットワークトポロジ100がＥｔｈｅｒｎｅｔ（登録商標）ネットワーク114を含まない場合、システム管理メッセージを、ポイントツーポイントリンク(例えば、ノード間のリンクおよびスイッチ-ノード間のリンクなど)上で運ぶことができる。
【００３０】
いくつかの実装形態において、ネットワークトポロジ100の階層構造における各層の各ユニットは、同じノード配列を有する。しかし、最下層の上の層について、ユニットの各ノードは、下の層におけるユニットのスイッチノードである。例えば、スイッチノード108は、2番目に低い層(すなわち、層L=1)におけるユニットのノードであり、最下層(すなわち、層L=0)におけるユニット102のスイッチとして働く。いくつかの実装形態において、ある層におけるユニットのスイッチノードは、ポイントツーポイント(すなわちスイッチ間)リンクによって完全に接続される。例えば、2番目に低い層におけるユニットのスイッチノード108は、スイッチ間リンク116によって、同じユニット内のすべての他のスイッチノード、および上の層におけるユニットのスイッチノードに接続される。上述したように、他の実装形態において、ユニット内のノードの数は、層によって異なり得る。
【００３１】
多次元の階層的に拡張可能なネットワークは、図1のネットワークトポロジ100の例を使用することができる。階層構造における各層の各ユニットが8つのノードの2×2×2の立方体のローカルの3-Dネットワークトポロジを有する実装形態において、{0,0,0}から{1,1,1}までの3-Dアドレスを使用して、各ノードをオクテット以内で論理的に配置することができる。すなわち、各ノードは、3ビットを使用して、ユニット内でアドレス指定される。階層構造の最下層の計算ノードの完全なアドレスは、3ビットの組に分割される2進数である。2進数の3つの最下位ビット(LSB)の組は、最下層のユニットの特定の計算ノード(すなわち、リーフノード)を識別し、最上位の3ビットの各組は、階層構造における上位層のユニットの特定のスイッチノードに対応する。多次元の階層的に拡張可能なネットワークのアドレス指定について、以下に図4〜図5を参照してより詳しく説明する。
【００３２】
記載された多次元の階層ネットワークは、必要に応じて、スーパーコンピューティングアプリケーションに対応するために、連続的に大きい階層的な層でスケールアップすることができる。多次元の階層ネットワークは、スーパースケールコンピューティングにおいて必要な効率的で柔軟な高速通信を提供する。例えば、ユニットのローカルネットワークトポロジ内の専用のポイントツーポイント通信の使用は、ローカルスループットを最大にする。ユニットのローカルブロードキャストネットワークは、ポイントツーポイントリンクに依存しないグループ通信を可能にする。各スイッチノードは、ポイントツーポイントおよびブロードキャストリンクを含む別のユニットの一部であり、フレキシブルなネットワークを通じてポイントツーポイント、マルチキャスト、およびブロードキャスト通信を提供する。
【００３３】
多次元の階層ネットワークは、待ち時間を最低限に抑え、コストおよび消費電力に対する性能を最大にするために、システムオーバーヘッドを取り除くように設計することができる。例えば、多次元の階層ネットワークを実装するシステムは、業界標準のアプリケーションプログラミングインターフェイス(API)をメッセージパッシング用に備えたソフトウェアアプリケーションを、最低限のソフトウェアオーバーヘッドで実装して提供することができる。
【００３４】
図2は、階層的なツリーネットワーク200の例を示す。階層的なツリーネットワーク200の例は、図1のネットワークトポロジ100の例の階層構造を見る1つの方法を示す。
【００３５】
階層的なツリーネットワーク200の例は、n-1個のスイッチノード108の層および1個の計算ノード104の層を含むn個の層を含み、ここではn=10である。示したように、計算ノード104の層210は、最下層(すなわち、層L=0)である。スイッチノード108の層210は、上位のn-1=9つの層である(すなわち、層L=1,2,...,9)。各層Lは、mn-L個のノードを含み、ここでmは、ユニット内のノードの数を表し、1を超える整数である。図2の例において、ユニット内のノードの数mは8である。したがって、最下層の各ユニットは、8つの計算ノード104を含み、上位層の各ユニットは、8つのスイッチノード108を含む。各スイッチノード108は、次に低い層210におけるユニットのノードのスイッチとして働く。n=10およびm=8のこの例について、最下層(すなわち層L=0)は、810-0=1,073,741,824個の計算ノード104を含む。各計算ノード104は、1つまたは複数のソフトウェアアプリケーションの命令を実行するよう動作可能な処理要素を含み得る。
【００３６】
図2をわかりやすくするために、スイッチ-ノードリンク110およびスイッチ間リンク116の一部のみが示されている。最下層のユニットの計算ノード104間のノード間リンク106、および上位層のユニットのスイッチノード108間のスイッチ間リンク116は示されていない。層L=1以外の、スイッチノード108の各層210からの1つのサブツリーのみが示されている。ブロードキャストネットワーク112も示されていない。
【００３７】
図3は、階層的な3-Dネットワーク300の例を示す。階層的な3-Dネットワーク300の例は、図1のネットワークトポロジ100の例の階層構造を見る別の方法を示す。図3は、階層的な3-Dネットワーク300の例の層310、311におけるスイッチノード(例えばスイッチノード108)、および層312における計算ノード(例えば計算ノード104)を含むノードの3つの層310〜312を示す。階層的な3-Dネットワーク300の例は、追加の層(図示せず)を含み得る。図3をわかりやすくするために、層311および312のそれぞれの一部のみが示されている。
【００３８】
この実装形態において、階層的な3-Dネットワーク300における層の各ユニット320は、3次元のそれぞれにおける辺ごとに2つのノードを備える立方体状ネットワークとして、2×2×2の配列の8つの完全に接続されたノードを有する。上の2つの層310および311において、各ノード(すなわちスイッチノード108)は、次に低い層、すなわち、それぞれ層311および312におけるユニット320のノードのスイッチとして働く。層のユニット320の各スイッチノード108は、同じ層における同じユニット320の互いのスイッチノード108、および次に低い層におけるユニット320の各ノードにリンクされる。例えば、層310におけるユニット320は、8つのスイッチノード322a〜hを含む。スイッチノード322a〜hのそれぞれは、次に低い層、すなわち層311に含まれるユニットのスイッチノードとして機能する。この例において、スイッチノード322hは、8つのノード324a〜hを含む層311におけるユニット320のスイッチノードとして機能する。8つのノード324a〜hもスイッチノードであり、この場合、ノード324a〜hのそれぞれは、次に低い層、すなわち層312に含まれるユニットのスイッチノードとして機能する。例えばスイッチノード324hは、8つのノード326a〜hを有する層312に含まれるユニット320のスイッチノードとして機能する。この例では、8つのノード326a〜hは、計算ノードである。
【００３９】
図4は、図2の階層的なツリーネットワーク200のアドレス指定方式400の例を示し、アドレス指定方式は、プロセッサを含むネットワーク接続デバイスによって実施することができる。アドレス指定方式400の例は、4バイトのアドレス語の30ビットアドレス405(すなわち、ビット0からビット29)としてメッセージの宛先アドレスを提供する。30ビットアドレス405は、3ビットの10個の組410、すなわちビットフィールドAdd0、Add1、・・・、Add9に分割される。4バイトのアドレス語の2つの最上位ビット(MSB)(すなわちビット30および31)は、将来使用するために、予備のビットフィールド420として取っておくことができる。
【００４０】
30ビットアドレス405の3つの最下位ビット(LSB)の組410(すなわち、ビットフィールドAdd0)は、階層的なツリーネットワーク200の最下層のユニットの特定の計算ノード104を識別し、最上位ビットの各組410(すなわち、ビットフィールドAdd1からAdd9)は、階層構造における連続する上位層のユニットの特定のスイッチノード108に対応する。すなわち、最下層L=0のユニットの8つの計算ノード104は、Add0によってアドレス指定され、層L=1からL=9におけるスイッチノード108はそれぞれ、Add1からAdd9によってアドレス指定される。
【００４１】
各計算ノード104は、完全な30ビットアドレス405によって(すなわち、ビットフィールドAdd0からAdd9によって)完全にアドレス指定される。所与の層の各スイッチノード108は、所与の層からMSBの組410までのビットフィールドの組410を使用して、部分的なアドレスによって完全にアドレス指定される。例えば、層L=3のスイッチノード108は、ビットフィールドAdd3からAdd9によって完全にアドレス指定される。
【００４２】
いくつかの実装形態において、各メッセージパケットは、例えば、宛先アドレス、メッセージパケットのサイズ、メッセージパケットのチェックサム、およびソースアドレスを含むいくつかのフィールドを備えるヘッダーを含む。データが送信されるとき、ヘッダーを、オペレーティングシステム(OS)ソフトウェアおよびハードウェアによって一部分データに付加することができる。パケットヘッダーは、パケットをそのまま配信するのに必要なすべてのデータを提供する。チェックサムは、パケット全体が有効であることの簡単なチェックを提供するために、送信時にOSによって追加することができる。チェックは、宛先で行うことができる。一例では、使用されるチェックサムは、インターネットプロトコルで使用される1の補数和(compliment sum)である(RFC971)。
【００４３】
予備のビットフィールド420は、アドレス範囲の拡張のために使用することができ、それによってアドレス指定方式400の同じ全構造を維持しながら、柔軟な数のアドレス語を可能にする。例えば、4バイトのアドレス語のMSB(すなわち、ビット31)は、宛先アドレスが4バイトのアドレス語で完全に指定されるかどうか、または4バイトのアドレス語における宛先アドレスがマルチワードの宛先アドレスの上位部分であるかどうかを示す継続ビットとすることができる。その後のアドレス語は、MSBを使用して、マルチワードの宛先アドレスの別の部分を示すこともできる。
【００４４】
4バイトのアドレス語の第2のMSB(すなわちビット30)は、宛先アドレスがポイントツーポイントのプロトコルアドレスであるかどうか、または宛先アドレスが宛先の組(例えば複数のノード)の記述子を指定するかどうかを示すことができる。宛先アドレスが組の記述子を指定することを第2のMSBが示す場合、宛先アドレスのビットは、その組の宛先の識別子を含み得る。一実装形態において、後述するように、メッセージを送信するためのリンクを割り当てるために、組の記述子をノードの通信ハードウェアによって使用することができる。
【００４５】
アドレス指定方式400の例を使用したメッセージのルーティングは、例えば複雑なルーティングテーブルなど、複雑なルーティング方式を必要としない。最下層のユニットのソース計算ノード104から送信された単一の宛先メッセージでは、メッセージパケットを送信すべきリンクは、同じユニットの他の7つのピアの計算ノード104のうちの1つ、または(例えば、図1のスイッチ-ノードリンク110によって)ソース計算ノード104が接続されるスイッチノード108のいずれかに対する。ビットフィールドAdd1からAdd9の組410がメッセージパケットのヘッダーで指定されたソース計算ノード104のアドレスと宛先計算ノード104のアドレスとの間で等しい場合、メッセージは、リンク(例えば、図1のノード間リンク106)上で他の7つのピアの計算ノード104のうちの1つに送信される。ビットフィールドAdd1からAdd9の組410がソース計算ノード104のアドレスと宛先計算ノード104のアドレスとの間で等しくない場合、メッセージは、リンク上で第2の層の接続されたスイッチノード108に送信される。
【００４６】
スイッチノード108におけるメッセージのルーティングでは、アドレスビットフィールドの類似の比較が行われる。例えば、所与の層Lのユニットの所与のスイッチノード108について、単一の宛先メッセージパケットを送信するためのリンクは、(例えば、図1のスイッチ間リンク116によって)所与のスイッチノード108が接続される層L+1のスイッチノード108、(例えば、図1のスイッチ間リンク116によって)同じユニットの他の7つのピアのスイッチノード108のうちの1つ、または所与のスイッチノード108が接続される層L-1の8つのノードのうちの1つのいずれかに対する。メッセージパケットが送信されるリンクは、所与のスイッチノード108のアドレスのビット範囲Add(L)からAdd9を宛先ノードのアドレスの対応するビット範囲と比較することによって決定される。メッセージのルーティングは、図10〜図11を参照して以下でさらに説明する。
【００４７】
階層的なツリーネットワーク200のアドレス指定方式400の例では、ポイントツーポイントまたはマルチキャストでのノードに対するホップカウントの比は低い。このネットワーク200の例において、ユニットの任意の第1の計算ノード104から送信されたメッセージは、最大で18のホップの異なるユニットの任意の第2の計算ノード104に到達することができる。例えば、層L=0における第1のユニットの第1の計算ノード104から、メッセージは、9つのホップを取って、階層構造の最上層(すなわち層L=9)に到達し、別の9つのホップを取って、最下層(すなわち層L=0)に到達して、最下層の第2のユニットの第2の計算ノード104にルーティングされる。しかし、最上位ビットの組410のうちの1つまたは複数がソース計算ノード104と宛先計算ノード104との間で共通であるため、メッセージが最上層にルーティングされる必要がない場合、メッセージは、最大18より少ないホップでルーティングすることができる。
【００４８】
いくつかの実装形態において、4バイトのアドレス語は、受信されたメッセージパケットヘッダーの最初の部分である。4バイトのアドレス語の後、どれだけのデータを送信するかを示すパケットサイズフィールドが続き得る。この構成は、ストリーム式のリンクプロトコルを容易にし、それによって、いったん4バイトのアドレス語が受信され、メッセージパケットがスイッチノード108で完全に受信される前に、任意のスイッチノード108がメッセージの転送を開始することができ、輻輳のためにメッセージパケットをバッファに入れる必要がある場合を除いて、待ち時間が最低限に抑えられる。ホップごとに2サイクルの待ち時間では、プロトコルがストリーム式であり、メッセージパケットをバッファに入れる必要がない場合、ソース計算ノード104からのメッセージの送信の開始から宛先計算ノード104でのメッセージの受信の開始までの最大待ち時間は、36サイクルである。
【００４９】
図5は、例えば、図3の階層的な3-Dネットワーク300の例など、階層的な3-Dネットワークの2×2×2のユニットについてのアドレス指定500の例を示す。ユニットは、3次元X、Y、およびZのそれぞれにおける辺ごとに2つのノードを備える立方体状ネットワークとして、2×2×2の配列の8つの完全に接続されたノードを有する。{0,0,0}から{1,1,1}までの3-Dアドレス{X,Y,Z}を使用して、各ノードを立方体状ネットワーク内に論理的に配置することができる。すなわち、各ノードは、3次元のそれぞれの各ビットである3ビットを使用して、ユニット内でアドレス指定される。
【００５０】
図2の階層的なツリーネットワーク200は、層の間を垂直に、またユニット内を水平に、ツリーネットワークを単に移動するだけで、任意の他のノードから任意のノードに容易に到達することを示す。図3の階層的な3-Dネットワーク300は、複雑さおよびネットワークによって実現可能な柔軟性を示す。階層的な3-Dネットワークトポロジを実装するシステムは、階層的なツリーネットワーク200および階層的な3-Dネットワーク300の両方によって表すことができ、図4のアドレス指定方式400を使用することができ、この場合、各2×2×2のユニットのアドレス指定は、図5のアドレス指定500による。階層的なツリーネットワーク200の図から、3ビットアドレスフィールドは、ユニットの8つのノードのうちの1つを識別することができる。階層的な3-Dネットワーク300の図から、3ビットアドレスフィールドは、ローカルな立方体状ネットワークの3-Dデカルト座標におけるインデックスとして使用することができる。
【００５１】
図6は、階層的な3-Dネットワークの2×4×4のユニットについてのアドレス指定方式600の例を示す。ユニットは、X次元の辺ごとに2つのノード、ならびにYおよびZ次元のそれぞれの辺ごとに4つのノードを備える3-Dネットワークとして、2×4×4の配列の32個の完全に接続されたノード(図示せず)を有する。{0,0,0,0,0}から{1,1,1,1,1}までの3-Dアドレス{X,Y1,Y2,Z1,Z2}を使用して、各ノードをローカルネットワーク内に論理的に配置することができる。すなわち、各ノードは、X次元で1ビット、Y次元で2ビット、Z次元で2ビットの5ビットを使用してユニット内でアドレス指定される。図5および図6は、階層的な3-Dネットワークのユニットについての2つのアドレス指定の例(すなわち2×2×2および2×4×4の配列)を示しているが、階層的な3-Dネットワークトポロジにおいて他の3-Dノード配列の異なるアドレス指定を実施することができる。
【００５２】
いくつかの実装形態において、ノード間の1つまたは複数のポイントツーポイントリンクを非アクティブ化することができる。例えば、階層ネットワークの2×4×4のユニットについてのアドレス指定600の例により階層的な3-Dネットワークを実装するシステムにおいて、システム上で稼働するアプリケーションが必要とするのがユニットごとに18個のみのノードである場合、2×4×4のユニットを、YおよびZの次元におけるノード間のいくつかの論理的なリンクが非アクティブ化された状態で、2×3×3のユニットとして接続することができる。
【００５３】
いくつかの実装形態において、階層ネットワークのすべての層のユニットは、同じローカルの3-Dネットワークトポロジを有する。これらの実装形態において、ある層のユニット内のノードを識別するアドレスビットの組のそれぞれは、同じ数のビットを有する。
【００５４】
いくつかの実装形態において、階層ネットワークの異なる層のユニットは、異なるローカルの3-Dネットワークトポロジを有し得る。これらの実装形態において、異なる層のユニット内のノードを識別するアドレスビットの組は、異なる数のビットを有し得る。例えば、最下層の計算ノードのユニットは、ローカルの2×4×4のネットワークトポロジを有することができ、ユニットの各計算ノードは、5ビットのアドレスフィールド(例えば{X,Y1,Y2,Z1,Z2})によって識別され、上位層のスイッチノードのユニットは、ローカルの2×2×2のネットワークトポロジを有することができ、この場合、あるユニットの各スイッチノードは、3ビットのアドレスフィールド(例えば{X,Y,Z})によって識別される。
【００５５】
階層ネットワークトポロジは、3より高い次元のネットワークとして実装することができる。例えば、システムは、階層的な4次元(4-D)ネットワークトポロジを実装することができる。図7は、4次元を有することができるネットワークトポロジ700の例を示す。
【００５６】
図7は、ネットワークトポロジ700の階層構造の最下層における計算ノード704のユニット702を示す。ユニット702のローカルネットワークトポロジが16個の計算ノード704の周りに形成されている。一例において、ユニット702のローカルネットワークトポロジは、2×2×2×2のネットワークトポロジとすることができる。
【００５７】
各計算ノード704は、ポイントツーポイントリンク706によってユニット702の互いの計算ノード704に接続される。各計算ノード704は、ポイントツーポイントリンク710によって次に高い層におけるユニットのスイッチノード708に接続される。また、各計算ノード704は、ユニット702のローカルブロードキャストネットワーク712によって、ユニット702の互いの計算ノード704、およびスイッチノード708にも接続される。スイッチノード708は、ネットワークトポロジ700の階層構造の他のユニットの他のローカルブロードキャストネットワークに、ユニット702のローカルブロードキャストネットワーク712をブリッジすることができる。いくつかの実装形態において、各計算ノード704は、Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク(図示せず)によって、ユニット702の互いの計算ノード704、およびスイッチノード708にも接続される。
【００５８】
図8は、階層的なツリーネットワーク800の例を示す。階層的なツリーネットワーク800の例は、図7のネットワークトポロジ700の例の階層構造を見る1つの方法を示す。一例において、階層的なツリーネットワーク800の例における各ユニットのローカルネットワークトポロジは、2×2×2×2のネットワークトポロジとすることができる。
【００５９】
階層的なツリーネットワーク800の例は、1個のスイッチノード708の層および1個の計算ノード704の層を含む。計算ノード704の層は下位層であり、スイッチノード708の層は上位層である。階層的なツリーネットワーク800の例における層の各ユニットに16個のノードがある。各スイッチノード708は、下位層におけるユニットのノードのスイッチとして働く。この例では、下位層は、162=256個の計算ノード704を含む。
【００６０】
図8をわかりやすくするために、スイッチノード708の上位層からの2つのサブツリーのみが示されている。したがって、スイッチ-ノードリンク710の一部分のみが示されている。さらに、下位層のユニットの計算ノード704間のノード間リンク、および上位層のユニットのスイッチノード708間のスイッチ間リンクは示されていない。
【００６１】
図9は、図8の階層的なツリーネットワーク800についてのアドレス指定方式900の例を示す。アドレス指定方式900の例は、1バイトで8ビットアドレス905(すなわち、ビット0からビット7)としてメッセージの宛先アドレスを提供する。8ビットアドレス905は、4ビットの2つの組910、すなわちビットフィールドAdd0およびAdd1に分割される。階層的なツリーネットワーク800の各ユニットがローカルの2×2×2×2のネットワークトポロジを有する場合、各ノードは、4次元のそれぞれについて1ビットを使用して、ユニット内でアドレス指定される。いくつかの実装形態において、図8の階層的なツリーネットワーク800のアドレス指定方式は、複数のバイトを使用することができ、将来の使用のために、予備のビット(図示せず)が取ってある。
【００６２】
8ビットアドレス905(すなわちビットフィールドAdd0)の4LSBの組910は、階層的なツリーネットワーク800の下位層のユニットの特定の計算ノード704を識別し、4MSBの組910(すなわちビットフィールドAdd1)は、階層構造における上位層の特定のスイッチノード708に対応する。各計算ノード704は、完全な8ビットアドレス905(すなわち、ビットフィールドAdd0およびAdd1)によって完全にアドレス指定される。上位層の各計算ノード708は、MSBのビットフィールドの組910(すなわち、ビットフィールドAdd1)を使用して部分的なアドレスによって完全にアドレス指定される。例えば、図8のスイッチノード810および820は、それぞれAdd1={0,0,0,0}およびAdd1={1,1,1,1}によって完全にアドレス指定される。図8の計算ノード825は、ポイントツーポイントリンクによってスイッチノード820に接続され、{Add1,Add0}={1,1,1,1,0,0,0,1}によって完全にアドレス指定される。
【００６３】
図10は、図4のアドレス指定方式400を使用して、図2の階層的なツリーネットワーク200においてスイッチノードで受信されるメッセージをルーティングするためのプロセス1000の例のフローチャートである。便宜上、プロセス1000の例について、図1〜図2および図4、ならびにプロセス1000を実行するシステムを参照して説明する。
【００６４】
プロセス1000の例は、ネットワークトポロジ(例えば図1のネットワークトポロジ100)のアドレス指定システムについてのものである。ネットワークトポロジは、n個の層を含むノードの階層構造を有する。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含む。その構造における層は、整数である「L」によって表され、L=0は最下層を表し、L=n-1は最上層を表す。構造の層Lにおける所与のユニットのスイッチノードで受信したメッセージの場合、プロセス1000の例は、構造において1つ上の層(すなわち、所与のユニットのスイッチノードに直接接続された層L+1におけるスイッチノードに)、または構造において1つ下の層(すなわち、スイッチノードに直接接続された層L-1におけるノードのうちの1つに)、または所与のユニットの他のピアスイッチノードのうちの1つのいずれかにメッセージをルーティングする。
【００６５】
システムは、構造の層Lのスイッチノードでメッセージを受信し、メッセージは、n個のビットの組を含む第1のアドレス(例えば宛先アドレス)を備えるヘッダーを含み、スイッチノードは、n-L個のビットの組を含む第2のアドレスを有する(ステップ1010)。例えば、アドレス指定システムは、図4のアドレス指定方式400の例とすることができ、各計算ノードの30ビットアドレス405は、10個のビットの組410を含む。
【００６６】
システムは、第1のアドレスのMSBのn-L個の組が第2のアドレスのn-L個のビットの組に一致するかどうかを決定する(決定1020)。例えば、システムは、第1および第2のアドレスのそれぞれのビットの組に対してビットマスクを適用することによって、ビットの組が一致するかどうかを決定することができる。
【００６７】
n-L個の組が一致することをシステムが決定した場合(決定1020の「yes」の分岐)、システムは、第1のアドレスのMSBのn-L+1個の組によって完全にアドレス指定された構造の層L-1のノードに、ポイントツーポイントリンク上でメッセージを転送する(ステップ1030)。例えば、システムは、階層的なツリーネットワーク200の1つ下のレベルのスイッチノードにスイッチ間リンク上で(例えば、図1〜図2のスイッチ間リンク116など)、または計算ノードにスイッチ-ノードリンク上(例えば図1〜図2のスイッチ-ノードリンク110)でメッセージを転送することができる。
【００６８】
システムは、メッセージを受信するノード(すなわち、第1のアドレスのMSBのn-L+1個の組によって完全にアドレス指定された層L-1のノード)が宛先ノードであるかどうかを決定する(決定1070)。例えば、システムは、メッセージを受信するノードが第1のアドレスのすべてのビットによって完全にアドレス指定された計算ノードであるかどうかを決定することができる。メッセージを受信するノードが宛先ノードであることをシステムが決定した場合(決定1070の「yes」の分岐)、プロセス1000の例が終了する。メッセージを受信するノードが宛先ノードではないことをシステムが決定した場合(決定1070の「no」の分岐)、プロセス1000の例は、ステップ1010から繰り返し、メッセージは、層L-1のノードで受信される。
【００６９】
n-L個の組が一致しないことをシステムが決定した場合(決定1020の「no」の分岐)、システムは、第1のアドレスのMSBのn-L-1個の組が第2のアドレスのMSBのn-L-1個の組に一致しているかどうかを決定する(決定1040)。n-L-1個の組が一致することをシステムが決定した場合(決定1040の「yes」の分岐)、システムは、第1のアドレスのMSBのn-L個の組によって完全にアドレス指定された構造の層Lのスイッチノードに、ポイントツーポイントリンク上でメッセージを転送する(ステップ1050)。例えば、システムは、同じユニットのピアスイッチノードのうちの1つに、スイッチ間リンク上で(例えば、図1〜図2のスイッチ間リンク116など)、階層的なツリーネットワーク200の層Lのユニット内で水平にメッセージを転送することができる。プロセス1000の例は、メッセージが層Lのノードで受信されるステップ1010から繰り返す。
【００７０】
n-L-1個の組が一致しないことをシステムが決定した場合(決定1040の「no」の分岐)、システムは、第2のアドレスのMSBのn-L-1個の組によって完全にアドレス指定された構造の層L+1のスイッチノードに、ポイントツーポイントリンク上でメッセージを転送する(ステップ1060)。例えば、システムは、階層的なツリーネットワーク200の1つ上のレベルの、ユニットのスイッチノードに直接接続された層L+1のスイッチノードのみにスイッチ間リンク上で(例えば、図1〜図2のスイッチ間リンク116など)メッセージを転送することができる。プロセス1000の例は、メッセージが層L+1のノードで受信されるステップ1010から繰り返す。
【００７１】
図11は、図4のアドレス指定方式400を使用して、図2の階層的なツリーネットワーク200における計算ノードから発せられるメッセージを宛先ノードにルーティングするためのプロセス1100の例のフローチャートである。便宜上、プロセス1100の例について、図1〜図2および図4、ならびにプロセス1000を実行するシステムを参照して説明する。
【００７２】
プロセス1100の例は、ネットワークトポロジ(例えば図1のネットワークトポロジ100)のアドレス指定システムについてのものである。ネットワークトポロジは、n個の層を含むノードの階層構造を有する。n個の層は、n-1個のスイッチノードの層および1個の計算ノードの層を含む。その構造における層は、整数である「L」によって表され、L=0は最下層を表し、L=n-1は最上層を表す。構造の層Lにおける所与のユニットの計算ノードから発せられたメッセージの場合、プロセス1100の例は、構造において1つ上の層(すなわち、所与のユニットの計算ノードに直接接続された層L+1におけるスイッチノードに)、または所与のユニットの他のピアスイッチノードのうちの1つのいずれかにメッセージをルーティングする。
【００７３】
メッセージは、構造の層Lの計算ノードからルーティングされている。メッセージは、n個のビットの組を含む第1のアドレス(例えば宛先アドレス)を備えるヘッダーを含み、計算ノードは、n個のビットの組を含む第2のアドレス(例えばソースアドレス)を有する。例えば、アドレス指定システムは、図4のアドレス指定方式400の例とすることができ、各計算ノードの30ビットアドレス405は、10個のビットの組410を含む。
【００７４】
システムは、第1のアドレスのMSBのn-1個の組が第2のアドレスのMSBのn-1個の組に一致するかどうかを決定する(決定1120)。このチェックは、宛先ノードが所与のユニットにあるかどうかを決定する。宛先ノードが所与のユニットにあることを示す、n-1個の組が一致することをシステムが決定した場合(決定1120の「yes」の分岐)、システムは、第1のアドレスのn個のビットの組によって完全にアドレス指定された構造の層Lの計算ノードに、ポイントツーポイントリンク上でメッセージを転送する(ステップ1130)。例えば、システムは、同じユニットのピア計算ノードのうちの1つに、ノード間リンク上で(例えば、図1のノード間リンク106など)階層的なツリーネットワーク200の層Lのユニット内で水平にメッセージを転送することができる。転送されたメッセージを受信する層Lの計算ノードは、第1のアドレスによって指定される宛先ノードである。ステップ1130の後、プロセス1100の例は終了する。
【００７５】
宛先ノードが異なるユニットにあることを示す、n-1個の組が一致しないことをシステムが決定した場合(決定1120の「no」の分岐)、システムは、第2のアドレスのMSBのn-1個の組によって完全にアドレス指定された構造の層L+1のスイッチノードに、ポイントツーポイントリンク上でメッセージを転送する(ステップ1140)。例えば、システムは、階層的なツリーネットワーク200の1つ上のレベルの、ユニットの計算ノードに直接接続された層L+1のスイッチノードのみにスイッチ-ノード間リンク上で(例えば、図1〜図2のスイッチ-ノード間リンク110など)メッセージを転送することができる。プロセス1100の例は、図10のステップ1010へ続き、メッセージが層L+1のスイッチノードで受信される。
【００７６】
いくつかの実装形態において、システムは、サーバからのＥｔｈｅｒｎｅｔ（登録商標）通信を使用して初期化される(例えばブートされる)。初期化プロセスは、システムのネットワークトポロジが構成ファイルで指定されている場合、ノードアドレスおよびレベル情報を運ぶことができる。いくつかの実装形態において、システムは、ネットワークトポロジを自律的に検出することができる。システムは、実際のシステムが指定されたネットワークトポロジに一致することを検証することができる。
【００７７】
いくつかの実施形態において、システムは、1つまたは複数の接続された半導体素子を使用して階層的な3-Dネットワークトポロジ(例えば、階層的なツリーネットワーク200および階層的な3-Dネットワーク300の両方によって表されるネットワークトポロジ)で設計することができる。例えば、システムを、フィールドプログラマブルゲートアレイ(FPGA)を各ノードになど、複数のプログラマブルロジックデバイス上に実装することができる。いくつかの実装形態において、各ノードは、特定用途向け集積回路(ASIC)で実装される。他の実装形態において、複数のノード(例えば8つのノード)の各ユニットは、ASICで実装され、ユニットのすべてのポイントツーポイント通信リンクをユニットのASIC内に集中させ、そのユニット内で高速なローカル通信を提供する。
【００７８】
いくつかの実装形態において、システムの1つまたは複数のノードは、コントローラ、プロセッサ、およびメモリを含む。いくつかの実装形態において、複数のノード(例えば、8つの計算ノードによって囲まれる、ハブとして働く1つのスイッチノード)のコントローラ、プロセッサ、およびメモリは、シリコンウエハーの1つまたは複数のダイ上で統合される。
【００７９】
いくつかの実装形態において、システムの各計算ノードは、プロセッサ、例えば中央処理装置(CPU)、および通信ハードウェア、例えばコントローラとして実装されるものなどを含む。他のノードからリンク上で受信されるトラフィックを、所与の計算ノードの通信ハードウェアによって所与の計算ノードのプロセッサに渡すことができる。通信ハードウェアのソフトウェア可読レジスタを使用してリンク状態の統計を集めるために、トラフィックを監視することができる。所与の計算ノードからのトラフィックを、所与の計算ノードの通信ハードウェアによって送信することができる。例えば、トラフィックの宛先が単一のポイントである場合、所与の計算ノードの通信ハードウェアは、必要に応じて、トラフィックを、同じユニットの別の計算ノード、または所与の計算ノードに接続されたスイッチノードにルーティングすることができる。トラフィックの宛先が複数のポイント(例えば、ノードの組へのマルチキャスト)である場合、プロセッサソフトウェアは、組の記述子を使用して、データを送信するためのリンクを割り当てることができ、リンクは、他のノードへのリンク、またはブロードキャストネットワーク上のリンクとすることができる。次いで、所与の計算ノードの通信ハードウェアは、割り当てられたリンク上でデータを送信する。いくつかの実装形態において、計算ノードの通信ハードウェアは、FPGAとして実装される。
【００８０】
いくつかの実装形態において、システムの1つまたは複数のスイッチノードは、プロセッサ、および通信ハードウェアを含む。所与のスイッチノードで受信されたトラフィックは、適切なリンク上で所与のスイッチノードの通信ハードウェアによって転送され得る。所与のスイッチノードで受信された組のトラフィックは、所与のスイッチノードのプロセッサによってインターセプトされ、組の記述子に従って割り当てられるリンク上で所与のスイッチノードの通信ハードウェアによって転送され得る。
【００８１】
いくつかの実装形態において、スイッチノードまたは計算ノードで、ノードの通信ハードウェアは、いったん宛先アドレスがノードで受信されると、パケット全体が到着する前に、パケットの送信を開始することができる。パケットの宛先アドレスおよびサイズをメッセージヘッダーの最初の2つの要素として含めることは、このプロセスを容易にする。すべての通信リンクは、同じデータレートで稼働することができるため、データ到着レートとデータ送信レートとの間の差はない。宛先に到着すると、パケットのチェックを行うことができる。
【００８２】
システムが過負荷状態に近いとき、輻輳の時間中にメッセージのバッファリングを可能にするために、先入れ先出し(FIFO)データ構造を提供することができる。FIFOの使用量は、分散されたOSソフトウェアに対して、アプリケーションの分散を変更する必要があることを示すことができる。例えば、1つのFIFOがすべてのパケットに使用されている場合、特定のリンクの使いすぎが示され、OSは、ネックを軽減するための行動をとることができる。例えば、アプリケーションの分散は、OSソフトウェアによって動的に変更することができる。
【００８３】
いくつかの実装形態において、計算ノードのプロセッサによってメッセージパケットの転送が実行される。これによって、スイッチノードプロセッサがデータをコピーする必要なく、あるノードから別のノードに送信されるデータを、データが生成されたバッファから直接送信し、データが使用されるバッファに入れることができ、それによって処理時間が改善する。すなわち、OSソフトウェアは、データをコピーせず、このことは効率を向上させる。というのは、ソフトウェアのコピーは、1つは読取り用、もう1つは書込み用の2つのメモリバスアクセスを必要とし、通常、データをメモリからキャッシュに取得し、別のキャッシュにコピーする必要があり、次いでこれをフラッシュする必要があるからである。これに対して、本明細書に記載したシステムは、データをメモリにドロップするためにノードでOSハードウェアを使用することができる。データを受信するためのメモリバッファは、予め選択され、データを受信する用意ができている可能性がある。何らかの理由のために、バッファの用意ができていない場合、OSソフトウェアは、依然としてそのデータを受信することはできるが、コピーが必要である場合がある。いくつかの例で、アプリケーションは、アプリケーション用に用意ができているデータがあるかどうかを決定し、データをアプリケーションのバッファにコピーするようOSに要求するのではなく、そのデータへのポインタを要求することができる。
【００８４】
いくつかの実装形態において、パケットが計算ノードから送信されるようにスケジュールされると、アプリケーションは、OSに対する呼び出しを行って、送信するためにパケットの制御をOSに渡す。一実装形態の例において、計算ノードは、アプリケーションプロセッサおよびOSプロセッサを含む。OSは、ネットワーク全体にわたって分散され、ハードウェアとソフトウェアに分割される。送信されるメッセージは、アプリケーションから、アプリケーションプロセッサ上で稼働するOSスタブソフトウェア(stub software)に渡される。次いでパケットは、ノード上のOSハードウェアに渡され、これは、OSプロセッサ上で稼働するOSソフトウェアによって管理される。この例は2つのプロセッサを使用するが、これは必須ではない。いくつかの実装形態において、ノードにおけるOSハードウェアは、FPGAを含むいくつかのプロセッサにインターフェイスするように設計され、上記の例で、機能がFPGAとその内蔵のプロセッサに分割される。
【００８５】
パケット転送のためのハードウェアを計算ノードのメモリ管理ハードウェアに統合することによって、OSハードウェアおよびソフトウェアは、パケットが送信の用意ができていることをアプリケーションがいったん示すと、データメモリにアクセスすることができる。データメモリアクセスは、プロセッサに透過的であり、これによってプロセッサは、OSソフトウェアがパケットを送信している間、他のタスクを実行することができる。別の実装形態例では、キャッシュコントローラがパケットのハードウェアに統合され、したがって、データは、メインメモリではなく、キャッシュメモリとの間で送受信される。キャッシュコントローラは、メインメモリとの間でデータを移動させるために使用される。
【００８６】
ソース計算ノードから宛先計算ノードに送信されたパケットは、1つまたは複数の中間スイッチノードを通過することができる。中間スイッチノードの通信ハードウェアは、メッセージパケットの第1の部分として受信された宛先アドレスフィールドに基づいて、入ってくるメッセージを送信するためのリンクを決定するため、コピー操作は中間スイッチノードでは必要ない。これによって、中間スイッチノードは、決定されたリンクが使用可能である限り、メッセージをコピーする必要なく、決定されたリンク上でのパケットの転送を開始することができる。いくつかの実装形態において、決定されたリンクがパケットの紛失を防ぐために使用されている場合、FIFOデータ構造が使用される。これに対して、従来のネットワークでは、複雑なルーティング(例えば、ルーティングテーブルを使用する)は、通常必須である。というのは、複数のメッセージが単一のリンク上で送信される必要がある場合があるからである。複雑なルーティングでは、宛先アドレスがパケットヘッダーから復号され、メッセージが転送される前に、メッセージを一時的にコピーすることが必要となることが多い。
【００８７】
パケットが計算ノードで受信されるようにスケジュールされたとき、アプリケーションは、到着するパケットを予想し、パケットの計算ノードのメモリにデータバッファを割り当てることができる。計算ノードのパケット転送ハードウェア(例えば、FPGA、ASIC、またはシリコンダイなどで実装される通信ハードウェアまたはコントローラ)は、パケットを割り当てられたデータバッファに入れることができる。アプリケーションが到着するパケットを予想していない場合、OSソフトウェアは、パケットの計算ノードのメモリにデータバッファを割り当てることができる。アプリケーションソフトウェアがパケットデータにアクセスするために呼び出しを行うと、計算ノードのメモリ管理ハードウェアは、アプリケーションによってアクセスするための割り当てられたデータバッファにパケットを入れることができる。
【００８８】
したがって、パケットデータをあるメモリエリアから別のメモリエリアにコピーする必要はなく、むしろ、データを、ソフトウェアのコピー無しにメモリに入れることができ、それによって待ち時間が短縮され、性能が向上する。メモリコピー操作は、単語ごとに2つのメモリアクセス、すなわち1つの読取りアクセスおよび1つの書込みアクセスを要する。本明細書に記載したゼロコピー方式は、これらのメモリアクセスを無くし、パケット転送の処理時間を短縮する。さらに、従来のシステムにおいて、計算ノードのプロセッサは、メモリコピーの期間の間、使用不可となる。これに対して、記載したシステムにおいて、計算ノードは、使用可能なままである。パケット送信が厳しいシステムにおけるこれら両方の要因(すなわち、メモリアクセスおよびプロセッサの使用不可)は、システムにおける帯域幅の損失の主な原因である。
【００８９】
図12は、コンピュータシステム1200の例の概要図である。システム1200は、上述したアクションおよび方法を実行するために使用することができる。上述したネットワークトポロジを使用するシステムの部分または側面は、コンピュータシステム1200の例のうちの1つまたは複数の要素で実装することができる。システム1200は、プロセッサ1218、メモリ1216、記憶装置1252、および入出力デバイス1254を含み得る。構成要素1218、1216、1252、および1254のそれぞれは、システムバス1256を使用して相互接続される。プロセッサ1218は、システム1200内で命令を処理することができる。これらの命令は、上述したシステム、構成要素、および技術の1つまたは複数の態様を実施することができる。いくつかの実装形態において、プロセッサ1218は、単一スレッドプロセッサである。他の実装形態において、プロセッサ1218は、マルチスレッドプロセッサである。プロセッサ1218は、複数の処理コアを含むことができ、入出力デバイス1254上のユーザインターフェイスのグラフィカル情報を表示するために、メモリ1216または記憶装置1252に格納される命令を処理することができる。
【００９０】
メモリ1216は、システム1200内に情報を格納する揮発性または不揮発性などのコンピュータ可読媒体である。メモリ1216は、例えば、ネットワークルーティングの機能に関係するプロセスを格納することができる。記憶装置1252は、システム1200の永続的なストレージを提供することができる。記憶装置1252は、フロッピー（登録商標）ディスク装置、ハードディスク装置、光ディスク装置、テープ装置、または他の適した永続的な記憶媒体を含むことができる。記憶装置1252は、上述した様々なデータベースを格納することができる。入出力デバイス1254は、システム1200についての入出力操作を提供する。入出力デバイス1254は、キーボード、ポインティング装置、およびグラフィカルユーザインターフェイスを表示するための表示装置を含み得る。
【００９１】
図12に示されるコンピュータシステムは、一例にすぎない。一般に、本明細書に記載した主題の実施形態および操作は、本明細書に開示した構造、およびその構造的な均等物、またはそれらのうちの1つまたは複数の組合せを含めて、デジタル電子回路、コンピュータソフトウェア、ファームウェア、またはハードウェアに実装することができる。本明細書に記載した主題の実施形態は、すなわち、データ処理装置によって実行するために、またはデータ処理装置の操作を制御するために、コンピュータ記憶媒体上で符号化されたコンピュータプログラム命令の1つまたは複数のモジュールなど、1つまたは複数のコンピュータプログラムとして実施することができる。あるいは、またはさらに、例えば、データ処理装置によって実行するのに適した受信装置に送信するための情報を符号化するように生成される、機械が生成した電子、光、電磁信号などの人工的に生成された伝搬信号においてプログラム命令を符号化することができる。コンピュータ記憶媒体は、コンピュータ可読記憶装置、コンピュータ可読記憶基板、ランダムまたはシリアルアクセスメモリアレイまたはデバイス、またはそれらのうちの1つまたは複数の組合せとすることができ、またはそれに含まれ得る。
【００９２】
「データ処理装置」という用語は、一例としてプログラム可能プロセッサ、コンピュータ、またはマルチプロセッサまたはコンピュータを含む、データを処理するためのすべての装置、デバイス、およびマシンを含む。装置は、ハードウェアに加えて、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらの1つまたは複数の組合せを構成するコードなど、当該のコンピュータプログラムの実行環境を作るコードを含み得る。
【００９３】
コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる)は、コンパイル言語、インタプリタ言語、または宣言言語または手続き言語を含めて、任意の形のプログラミング言語で書くことができ、スタンドアロンプログラムとして、またはモジュール、コンポーネント、サブルーチン、またはコンピューティング環境での使用に適した他のユニットを含む任意の形で配置することができる。コンピュータプログラムは、ファイルシステムにおけるファイルに必ずしも対応していなくてよい。プログラムは、(例えば、マークアップ言語ドキュメントに格納される1つまたは複数のスクリプトなど)他のプログラムまたはデータを保持するファイルの一部、当該のプログラムに専用の単一のファイル、または複数の連携ファイル(coordinated files)(例えば、1つまたは複数のモジュール、サブプログラム、コードの一部を格納するファイルなど)に格納することができる。コンピュータプログラムは、1つのコンピュータで、または1つのサイトの複数のコンピュータで、または複数のサイトにわたって分散され、通信ネットワークで相互接続された複数のコンピュータで実行するように配置することができる。
【００９４】
この明細書に記載したプロセスおよび論理フローは、入力データに対して作用し、出力を生成することによって、機能を実行するために、1つまたは複数のプログラムを実行する1つまたは複数のプログラム可能プロセッサによって実行することができる。プロセスおよび論理フローは、FPGAまたはASICなど、専用論理回路によって実行することもでき、また装置は、専用論理回路として実装することもできる。
【００９５】
コンピュータプログラムの実行に適したプロセッサは、一例として、汎用および専用のマイクロプロセッサ、および任意の種類のデジタルコンピュータの任意の1つまたは複数のプロセッサを含む。一般に、プロセッサは、読取り専用メモリまたはランダムアクセスメモリ、あるいはその両方から命令およびデータを受信する。コンピュータの必須要素は、命令を実行するプロセッサ、および命令およびデータを格納する1つまたは複数のメモリ装置である。一般に、コンピュータは、磁気、光磁気ディスク、または光ディスクなど、データを格納する1つまたは複数の大容量記憶装置も含み、またはそれとの間でデータの送受信を行うように動作可能に結合され、または記憶装置を含みかつ動作可能に結合される。しかし、コンピュータは、こうしたデバイスを有する必要はない。さらに、コンピュータは、数ある中でも例えば自動車電話、携帯情報端末(PDA)、携帯用音声または映像プレーヤー、ゲーム機、全地球測位システム(GPS)受信機など、別のデバイスに埋め込むことができる。
【００９６】
コンピュータプログラム命令およびデータを格納するのに適したコンピュータ可読媒体は、一例としてEPROM、EEPROM、フラッシュメモリ装置などの半導体メモリ装置、内部ハードディスクや取外し式ディスクなどの磁気ディスク、光磁気ディスク、およびCD-ROMおよびDVD-ROMディスクを含めて、すべての形の不揮発性メモリ、媒体、およびメモリ装置を含む。プロセッサおよびメモリは、専用論理回路によって補うことができ、またはそれに組み込むことができる。
【００９７】
ユーザとの対話を提供するために、本明細書に記載した主題の実施形態は、情報をユーザに表示するCRT(陰極線管)またはLCD(液晶表示装置)モニタなどの表示装置、およびユーザがコンピュータに入力を提供することができるマウスやトラックボールなどのキーボードおよびポインティング装置を有するコンピュータ上に実装することができる。他の種類の装置を使用してユーザとの対話を提供することもでき、例えば、ユーザに提供されるフィードバックは、例えば視覚フィードバック、聴覚フィードバック、または触覚フィードバックなど、任意の形の感覚フィードバックとすることができ、ユーザからの入力は、可聴音、音声、または触覚入力を含めて任意の形で受信することができる。
【００９８】
本明細書に記載した主題の実施形態は、例えばデータサーバとしてバックエンド構成要素を含む、または例えばアプリケーションサーバなどのミドルウェア構成要素を含む、または例えばユーザが本明細書に記載した主題の実装と対話することができるグラフィカルユーザインターフェイスやWebブラウザを有するクライアント構成要素などのフロントエンド構成要素を含む、あるいはこうしたバックエンド、ミドルウェア、およびフロントエンドの構成要素のうちの1つまたは複数の任意の組合せを含むコンピューティングシステムで実施することができる。システムの構成要素は、任意の形または媒体のデジタルデータ通信、例えば通信ネットワークなどによって相互接続することができる。通信ネットワークの例には、ローカルエリアネットワーク(「LAN」)および広域ネットワーク(「WAN」)、例えばインターネットなどがある。
【００９９】
コンピューティングシステムは、クライアントおよびサーバを含み得る。クライアントおよびサーバは、一般に互いに離れており、通常、通信ネットワークを介して対話する。クライアントとサーバとの関係は、それぞれのコンピュータ上で稼働し、相互にクライアント-サーバ関係を有するコンピュータプログラムによって生じる。
【０１００】
本明細書は、多くの特定の実装形態の詳細を含むが、これらは、任意の発明の範囲、または特許請求され得るものについての限定と解釈されるものではなく、むしろ、特定の発明の特定の実施形態に固有であり得る特徴の説明として解釈されるものとする。別々の実施形態の文脈で本明細書に記載したいくつかの特徴は、単一の実施形態に組合せで実施することもできる。逆に、単一の実施形態の文脈で記載した様々な特徴は、複数の実施形態で別々に、または任意の適した副結合で実施することもできる。さらに、特徴は、いくつかの組合せで動作するものとして上述しており、最初にそのよう特許請求しているが、特許請求した組合せのうちの1つまたは複数の特徴は、いくつかの場合、組合せから切り離すことができ、特許請求した組合せは、副結合または副結合の変形を対象とすることができる。
【０１０１】
同様に、操作は図に特定の順序で示されているが、これは、望ましい結果を達成するために、こうした操作が示した特定の順序で、または連続する順序で実行されること、またはすべての示した操作が実行されることを必要とするものと理解されるものではない。いくつかの状況では、マルチタスクおよび並行処理が有利である場合がある。さらに、上記の実施形態における様々なシステム構成要素の分離は、すべての実施形態においてこうした分離を必要とするものと理解されるものではなく、一般に、記載したプログラム構成要素およびシステムを、単一のソフトウェア製品に統合し、または複数のソフトウェア製品にパッケージすることができることを理解されたい。
【０１０２】
本発明のいくつかの実施形態について説明してきた。それにも関わらず、本発明の意図および範囲から逸脱することなく、様々な変更を加えることができることを理解されたい。したがって、他の実施形態は、以下の特許請求の範囲内である。
【符号の説明】
【０１０３】
100  ネットワークトポロジ
102  ユニット
104  計算ノード
106  ポイントツーポイントリンク
108  スイッチノード
110  スイッチ-ノードリンク
112  ブロードキャストネットワーク
114  Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク
116  スイッチ間リンク
200  階層的なツリーネットワーク
300  階層的な3-Dネットワーク
400  アドレス指定方式
500  アドレス指定
600  アドレス指定方式
700  ネットワークトポロジ
702  ユニット
704  計算ノード
706  ポイントツーポイントリンク
708  スイッチノード
710  ポイントツーポイントリンク
800  階層的なツリーネットワーク
900  アドレス指定方式
1200  コンピュータシステム
1216  メモリ
1218  プロセッサ
1252  記憶装置
1254  入出力デバイス
1256  システムバス
【図１】
2012521687.tif 000003
【図２】
2012521687.tif 000004
【図３】
2012521687.tif 000005
【図４】
2012521687.tif 000006
【図５】
2012521687.tif 000007
【図６】
2012521687.tif 000008
【図７】
2012521687.tif 000009
【図８】
2012521687.tif 000010
【図９】
2012521687.tif 000011
【図１０】
2012521687.tif 000012
【図１１】
2012521687.tif 000013
【図１２】
2012521687.tif 000014
【国際調査報告】
2012521687.tif 000015
2012521687.tif 000016