(57)【要約】【課題】トーラス区画化を容易にするために並列コンピュータのプロセッサを相互接続する方法およびシステムを提供すること。【解決手段】本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法およびシステムを提供し、（ａ）プロセッサのそれぞれは処理装置およびスイッチを含み、（ｂ）スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、（ｃ）Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、（ｄ）区画のそれぞれは、プロセッサのうちの少なくとも１つの処理装置を含み、（ｅ）Ｌは２以上の整数、Ｒは１以上の整数である。例示的実施形態では、この方法およびシステムは、Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続すること、および区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定することを含む。【選択図】図８
2005174289.tif 000002
【特許請求の範囲】
【請求項１】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するステップと、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するステップと
を含む方法。
【請求項２】
前記接続するステップが、
スイッチ１の前記第１の外部ポートとスイッチ２の前記第１の外部ポートを結合するステップ
を含む請求項１に記載の方法。
【請求項３】
前記接続するステップが、
Ｌ≧３の場合は、第（Ｌ−１）のスイッチの前記第４の外部ポートと第Ｌのスイッチの前記第４の外部ポートを接続するステップと、
１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの前記第３の外部ポートと第（ｉ＋１）のスイッチの前記第２の外部ポートを接続するステップと、
１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの前記第４の外部ポートと第（ｉ＋２）のスイッチの前記第１の外部ポートを接続するステップ
をさらに含む請求項２に記載の方法。
【請求項４】
前記接続するステップが、
前記Ｌ個のスイッチをケーブルで接続するステップ
を含む請求項１に記載の方法。
【請求項５】
前記設定するステップが、
前記区画のスパンを計算するステップ
を含む請求項１に記載の方法。
【請求項６】
前記計算するステップが、
前記区画中の最小座標、ＭＩＮを探索するステップと、
前記区画中の最大座標、ＭＡＸを決定するステップと、
前記区画のスパンを座標ｉの集合（ＭＩＮ≦ｉ≦ＭＡＸ、ｉは整数）と等しくなるように設定するステップと
を含む請求項５に記載の方法。
【請求項７】
前記計算するステップが、
前記区画のスパンが厳密に１座標を含み、ｉがそのスパンに属する１座標である場合には、
第ｉのスイッチの前記第１の内部ポートと前記第２の内部ポート（Ｉ１、Ｉ２）を接続するステップ
をさらに含む請求項６に記載の方法。
【請求項８】
前記計算するステップが、
前記区画のスパンが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標である場合には、
ｉ＝１の場合は、
第１のスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するステップと、
第１のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第２のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するステップと、
第２のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップを実行し、
ｉ＝Ｌ−１の場合は、
第（Ｌ−１）のスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するステップと、
第（Ｌ−１）のスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップと、
第Ｌのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するステップと、
第Ｌのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップを実行し、
それ以外で、２≦ｉ≦Ｌ−２の場合は、
第（ｉ−１）のスイッチの前記第３の外部ポートと前記第４の外部ポート（Ｅ３、Ｅ４）を接続するステップと、
第ｉのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するステップと、
第（ｉ＋１）のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するステップを実行することをさらに含む請求項６に記載の方法。
【請求項９】
前記計算するステップが、
前記区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンに属する３座標である場合には、
第ｉのスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップと、
第（ｉ＋２）のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第（ｉ＋２）のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するステップを実行し、
（ｉ＋１）が前記区画に属する場合は、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するステップと、
第（ｉ＋１）のスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するステップを、
（ｉ＋１）が前記区画に属さない場合は、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第３の外部ポート（Ｅ２、Ｅ３）を接続するステップを実行することをさらに含む請求項６に記載の方法。
【請求項１０】
前記計算することが、
前記区画のスパンが少なくとも４座標を含み、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである場合には、
ｉ＝ＭＩＮの場合は、
第ｉのスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップを実行し、
ｉ＝ＭＡＸの場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するステップを実行し、
ｉ＝ＭＩＮ＋１かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップを実行し、
ｉ＝ＭＩＮ＋１かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第２の外部ポートと前記第４の外部ポート（Ｅ２、Ｅ４）を接続するステップを、
ｉ＝ＭＡＸ−１かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するステップを実行し、
ｉ＝ＭＡＸ−１かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第１の外部ポートと前記第３の外部ポート（Ｅ１、Ｅ３）を接続するステップを、
ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するステップと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するステップを実行し、
ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第１の外部ポートと前記第４の外部ポート（Ｅ１、Ｅ４）を接続するステップを実行することをさらに含む請求項６に記載の方法。
【請求項１１】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するステップ
を含む方法。
【請求項１２】
前記接続するステップが、
スイッチ１の前記第１の外部ポートとスイッチ２の前記第１の外部ポートを結合するステップ
を含む請求項１１に記載の方法。
【請求項１３】
前記接続することが、
Ｌ≧３の場合は、第（Ｌ−１）のスイッチの前記第４の外部ポートと第Ｌのスイッチの前記第４の外部ポートを接続するステップと、
１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの前記第３の外部ポートと第（ｉ＋１）のスイッチの前記第２の外部ポートを接続するステップと、
１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの前記第４の外部ポートと第（ｉ＋２）のスイッチの前記第１の外部ポートを接続するステップ
をさらに含む請求項１２に記載の方法。
【請求項１４】
前記接続するステップが、
前記Ｌ個のスイッチをケーブルで接続するステップ
を含む請求項１１に記載の方法。
【請求項１５】
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するステップ
をさらに含む請求項１１に記載の方法。
【請求項１６】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチは拡張トーラス・アーキテクチャで接続され、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するステップ
を含む方法。
【請求項１７】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続するシステムであって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するように構成された接続モジュールと、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するように構成された設定モジュールと
を含むシステム。
【請求項１８】
前記接続モジュールが、
スイッチ１の前記第１の外部ポートとスイッチ２の前記第１の外部ポートを結合するモジュール
を含む請求項１７に記載のシステム。
【請求項１９】
前記接続モジュールが、
Ｌ≧３の場合は、第（Ｌ−１）のスイッチの前記第４の外部ポートと第Ｌのスイッチの前記第４の外部ポートを接続するように構成された接続モジュールと、
１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの前記第３の外部ポートと第（ｉ＋１）のスイッチの前記第２の外部ポートを接続するように構成された接続モジュールと、
１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの前記第４の外部ポートと第（ｉ＋２）のスイッチの前記第１の外部ポートを接続するように構成された接続モジュール
をさらに含む請求項１８に記載のシステム。
【請求項２０】
前記接続モジュールが、
前記Ｌ個のスイッチをケーブルで接続するように構成された接続モジュール
を含む請求項１７に記載のシステム。
【請求項２１】
前記設定モジュールが、
前記区画のスパンを計算するように構成された計算モジュール
を含む請求項１７に記載のシステム。
【請求項２２】
前記計算モジュールが、
前記区画中の最小座標、ＭＩＮを探索するように構成された探索モジュールと、
前記区画中の最大座標、ＭＡＸを決定するように構成された決定モジュールと、
前記区画のスパンを、座標ｉの集合（ＭＩＮ≦ｉ≦ＭＡＸ、ｉは整数）と等しくなるように設定するように構成された設定モジュールと
を含む請求項２１に記載のシステム。
【請求項２３】
前記計算モジュールが、
前記区画のスパンが厳密に１座標を含み、ｉがそのスパンに属する１座標である場合には、
第ｉのスイッチの前記第１の内部ポートと前記第２の内部ポート（Ｉ１、Ｉ２）を接続するように構成された接続モジュール
をさらに含む請求項２２に記載のシステム。
【請求項２４】
前記計算モジュールが、
前記区画のスパンが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標である場合には、
ｉ＝１の場合は、
第１のスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するように構成された第１の接続モジュールと、
第１のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第２の接続モジュールと、
第２のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するように構成された第３の接続モジュールと、
第２のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第４の接続モジュールをさらに有し、
ｉ＝Ｌ−１の場合は、
第（Ｌ−１）のスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するように構成された第１の接続モジュールと、
第（Ｌ−１）のスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第２の接続モジュールと、
第Ｌのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するように構成された第３の接続モジュールと、
第Ｌのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第４の接続モジュールをさらに有し、
それ以外で、２≦ｉ≦Ｌ−２の場合は、
第（ｉ−１）のスイッチの前記第３の外部ポートと前記第４の外部ポート（Ｅ３、Ｅ４）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するように構成された第２の接続モジュールと、
第ｉのスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するように構成された第３の接続モジュールと、
第（ｉ＋１）のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第４の接続モジュールと、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するように構成された第５の接続モジュールをさらに有する、請求項２２に記載のシステム。
【請求項２５】
前記計算モジュールが、
前記区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンに属する３座標である場合には、
第ｉのスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第２の接続モジュールと、
第（ｉ＋２）のスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第３の接続モジュールと、
第（ｉ＋２）のスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するように構成された第４の接続モジュールと、
（ｉ＋１）が前記区画に属する場合は、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するように構成された第５の接続モジュールと、
第（ｉ＋１）のスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するように構成された第６の接続モジュールを、
（ｉ＋１）が前記区画に属さない場合は、
第（ｉ＋１）のスイッチの前記第２の外部ポートと前記第３の外部ポート（Ｅ２、Ｅ３）を接続するように構成された第５の接続モジュール
をさらに含む請求項２２に記載のシステム。
【請求項２６】
前記計算モジュールが、
前記区画のスパンが少なくとも４座標を含み、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである場合には、
ｉ＝ＭＩＮの場合は、
第ｉのスイッチの前記第３の外部ポートと前記第１の内部ポート（Ｅ３、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第２の接続モジュールを含み、
ｉ＝ＭＡＸの場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第２の外部ポートと前記第２の内部ポート（Ｅ２、Ｉ２）を接続するように構成された第２の接続モジュールを含み、
ｉ＝ＭＩＮ＋１かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第２の外部ポートと前記第１の内部ポート（Ｅ２、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第２の接続モジュールを含み、
ｉ＝ＭＩＮ＋１かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第２の外部ポートと前記第４の外部ポート（Ｅ２、Ｅ４）を接続するように構成された接続モジュールを含み、
ｉ＝ＭＡＸ−１かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第３の外部ポートと前記第２の内部ポート（Ｅ３、Ｉ２）を接続するように構成された第２の接続モジュールを含み、
ｉ＝ＭＡＸ−１かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第１の外部ポートと前記第３の外部ポート（Ｅ１、Ｅ３）を接続するように構成された接続モジュールを含み、
ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉが前記区画に属する場合は、
第ｉのスイッチの前記第１の外部ポートと前記第１の内部ポート（Ｅ１、Ｉ１）を接続するように構成された第１の接続モジュールと、
第ｉのスイッチの前記第４の外部ポートと前記第２の内部ポート（Ｅ４、Ｉ２）を接続するように構成された第２の接続モジュールを含み、
ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉが前記区画に属さない場合は、
第ｉのスイッチの前記第１の外部ポートと前記第４の外部ポート（Ｅ１、Ｅ４）を接続するように構成された接続モジュールをさらに含む請求項２２に記載のシステム。
【請求項２７】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続するシステムであって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するように構成された接続モジュール
を含むシステム。
【請求項２８】
前記接続モジュールが、
スイッチ１の前記第１の内部ポートとスイッチ２の前記第１の外部ポートを結合するように構成された結合モジュール
を含むシステム。
【請求項２９】
前記接続モジュールが、
Ｌ≧３の場合は、第（Ｌ−１）のスイッチの前記第４の外部ポートと第Ｌのスイッチの前記第４の外部ポートを接続するように構成された接続モジュールと、
１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの前記第３の外部ポートと第（ｉ＋１）のスイッチの前記第２の外部ポートを接続するように構成された接続モジュールと、
１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの前記第４の外部ポートと第（ｉ＋２）のスイッチの前記第１の外部ポートを接続するように構成された接続モジュール
をさらに含む請求項２８に記載のシステム。
【請求項３０】
前記接続モジュールが、
前記Ｌ個のスイッチをケーブルで接続するように構成された接続モジュール
を含む請求項２７に記載のシステム。
【請求項３１】
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するように構成された設定モジュール
をさらに含む請求項２７に記載のシステム。
【請求項３２】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続するシステムであって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチは拡張トーラス・アーキテクチャで接続され、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するように構成された設定モジュール
を含むシステム。
【請求項３３】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する読取り可能なプログラム・コードが実施された、プログラマブル・コンピュータと共に使用可能なコンピュータ・プログラム製品であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するためのコンピュータ可読コードと、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するためのコンピュータ可読コードと
を含むコンピュータ・プログラム。
【請求項３４】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する読取り可能なプログラム・コードが実施された、プログラマブル・コンピュータと共に使用可能なコンピュータ・プログラム製品であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、
前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチを拡張トーラス・アーキテクチャで接続するためのコンピュータ可読コード
を含むコンピュータ・プログラム。
【請求項３５】
トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する読取り可能なプログラム・コードが実施された、プログラマブル・コンピュータと共に使用可能なコンピュータ・プログラム製品であって、前記プロセッサのそれぞれは処理装置およびスイッチを含み、前記スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、前記Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、前記区画のそれぞれは、前記プロセッサのうちの少なくとも１つの前記処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数であり、前記Ｌ個のスイッチの前記外部ポート間の前記Ｌ個のプロセッサの前記Ｌ個のスイッチは拡張トーラス・アーキテクチャで接続され、
前記区画のそれぞれをトーラスとして相互接続するために前記接続されたＬ個のスイッチを設定するためのコンピュータ可読コード
を含むコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は並列コンピュータに関し、詳細には、トーラス区画化を容易にするために並列コンピュータのプロセッサを相互接続する方法およびシステムに関する。
【背景技術】
【０００２】
マイクロプロセッサやメモリなどのコンピュータ・ハードウェアのコストが減少し、コンピュータによる解決を必要とする問題の複雑さが増大するにつれて、並列計算処理がますます重要になってきている。並列コンピュータは、通常、密結合多重プロセッサ、すなわち、ケーブルによって相互接続され、単一のオペレーティング・システムの下で稼動するマイクロプロセッサの集合体を使用する。これは、それぞれがそれ自体のオペレーティング・システムを有するいくつかの単一プロセッサ・コンピュータが(イーサネット（Ｒ）などの)ネットワークで接続される、疎結合多重コンピュータと対照をなす。
【０００３】
密結合プロセッサ
効率を高めるために、密結合多重プロセッサ中の単一のマイクロプロセッサ（以後「プロセッサ」という）のハードウェアは、普通、以下の２部分に分けられる。
（１）多重プロセッサを含む並列コンピュータ上で動作するプログラムの処理を実行するのに使用される処理装置（以後「ＰＵ」という）、および
（２）そのプロセッサとコンピュータ中の他のプロセッサの間のやりとりを処理するのに使用されるスイッチ。
各プロセッサにおいて、ＰＵおよびスイッチは論理的に結合される。通常、ＰＵおよびスイッチは電気的に結合される。
【０００４】
スイッチ
各スイッチは、ある数の外部ポートおよび内部ポートを有する。図１にＰＵ１１２およびスイッチ１１４に分けられた従来技術のプロセッサ１１０を示す。スイッチ１１４は、Ｅ１、Ｅ２、Ｅ３、Ｅ４とラベル付けされた４つの外部ポート、およびＩ１、Ｉ２とラベル付けされた２つの内部ポートを含む。あるスイッチの外部ポートは、別のスイッチの外部ポートにケーブルで接続され得る。各外部ポートには１本のケーブルだけしか接続できない。外部ポートにケーブルが接続されないこともあり得る。２つの内部ポートＩ１およびＩ２は、スイッチ１１４などのスイッチを、ＰＵ１１２などのＰＵに接続する。スイッチは、それ自体の（内部および外部）ポート対間の内部接続を行うことができ、しがたって、異なるＰＵ間のケーブル接続を行うことができる。
【０００５】
典型的なスイッチ１１４は、少なくとも４つの外部ポート、少なくとも２つの内部ポート、およびフル・クロスバーのスイッチング機能を含み、スイッチの各ポートを任意の対にすることを考えると、このスイッチは、各対の２ポートを接続するように設定され得る。
【０００６】
スイッチ接続
各スイッチは、相互接続することができる。例えば、従来技術の図２には、２つのプロセッサ（ＰＵ／スイッチ組合せ）１１０および１２０が示され、プロセッサ１２０はＰＵ１２２およびスイッチ１２４を含む。スイッチ１１４は、図２に示すように、ポートＥ１とポートＩ１、ポートＥ４とポートＩ２を接続するように設定される。スイッチ１２４は、図２に示すように、ポートＥ１とポートＩ１、ポートＥ２とポートＩ２、およびポートＥ３とポートＥ４を接続するように設定される。スイッチ１１４のポートＥ４とスイッチ１２４のポートＥ１の間のケーブル１３０も示されている。結果として、スイッチ１１４のポートＩ２はスイッチ１２４のポートＩ１に接続され、したがってそれら２つのＰＵを接続する。
【０００７】
ポートＪとポートＫの間の接続は対（Ｊ、Ｋ）で表される。スイッチの設定は、その各ポート間の接続の集合であり、各ポートは多くとも１つの接続対に出現するにすぎない。例えば、図２のスイッチ１１４の設定は、集合｛（Ｅ１，Ｉ１），（Ｅ４，Ｉ２）｝で表される。この図でのスイッチ１２４の設定は、集合｛（Ｅ１，Ｉ１），（Ｅ２，Ｉ２），（Ｅ３，Ｅ４）｝で表される。
【０００８】
接続の集合は空であることもあり、それは、そのスイッチのどのポートも相互に接続されていないことを示す。接続はスイッチ設定に動的に付加することも、そこから除去することも可能である。接続はいつでも除去することができる。
【０００９】
接続が付加され得るのは、その接続が、すでに既存の接続によって使用されているスイッチのポートを使用しない場合だけである。例えば、図２のスイッチ１１４の設定｛（Ｅ１，Ｉ１），（Ｅ４，Ｉ２）｝には、接続（Ｅ２、Ｅ３）が付加され得る。しかし、接続（Ｅ１、Ｅ３）は付加され得ない。というのは、図２のスイッチ１１４の設定では、ポートＥ１はすでに接続（Ｅ１、Ｉ１）によって使用されているからである。
【００１０】
相互接続アーキテクチャ
物理的制約のために、各スイッチは少数のポートだけしか持つことができず、そのため、１つのスイッチ（したがってそのＰＵ）は、少数の他のスイッチ（ＰＵ）だけにしか直接接続され得ない。物理的制約と電気的制約とのために、各ケーブルの長さが何らかの指定された量を超えられないこともある。ケーブルが外部ポート間に配置される方式は、そのコンピュータの相互接続アーキテクチャを形成する。すなわち、それらのケーブルの配置は固定される。（ケーブルがポートに差込み可能な場合であっても、ケーブルの配置が変更されると、それは別の相互接続アーキテクチャを構成することになる。）
【００１１】
セルラー構造
プロセッサは、通常、しばしばセルラー構造と呼ばれる規則的な構造で配列される。１つの非常に一般的なセルラー構造では、プロセッサは１次元、２次元、または３次元配列のセルに配置される。配列は、各次元でのコンピュータの長さを指定することによって定義され、その長さはプロセッサの数によって与えられる。例えば、２次元配列の場合には、その２つの次元をＸとＹとすると、配列はＸ次元の長さＬＸとＹ次元の長さＬＹによって指定される。この配列は合計ＬＸ×ＬＹ個のプロセッサを含む。例えば、図３に、合計２０個のプロセッサを含むＬＸ＝５、ＬＹ＝４の２次元配列１４０を示す。配列中の各プロセッサは、図３に示すように、その配列中の座標によって識別される。これらの座標は、そのプロセッサを含むＰＵおよびスイッチも識別する。３次元配列では、各プロセッサ（ＰＵおよびスイッチ）は、そのプロセッサのそれぞれＸ次元、Ｙ次元、Ｚ次元での座標を与える３座標の組合せ（ｘ、ｙ、ｚ）によって識別される。
【００１２】
スイッチの外部ポートの接続
コンピュータの相互接続アーキテクチャは、各スイッチの外部ポート間でケーブルが配置される方式を指定する。通常、ケーブリングは各次元ごとに別々になされる。例えば、３次元配列の場合には、スイッチは、Ｘスイッチ、Ｙスイッチ、Ｚスイッチに分けられ、それぞれがそれ自体の４外部ポート、２内部ポートを備える。ケーブルは、２つのスイッチが同じ次元を持つ（両方がＸスイッチであるなどの）場合に限り、あるスイッチの外部ポートを別のスイッチの外部ポートに接続することができる。
【００１３】
また、各次元の分離と共に、コンピュータは各次元での１次元の「ライン」にも分けられる。１ライン内では、１つを除くすべての座標が定数値を有し、定数以外の座標は、その座標の可能なすべての値をとる。例えば、図４には、座標ｙが１に固定されているＸライン１５２、および座標ｘが４に固定されているＹライン１５４が示されている。
【００１４】
コンピュータが単純で規則的な構造を持つために、次元Ｘを例にとると、ケーブルは同じＸラインに属するスイッチ間だけに配置され、コンピュータ中のすべてのＸラインは、通常、同じケーブリング構造を有する。例えば、長さＬＸ×ＬＹ×ＬＺの３次元コンピュータでは、Ｘ次元でのケーブリング（同じＸラインに属するＸスイッチ間に配置されるケーブル）は長さＬＸの１ラインのケーブリングによって指定される。この１ラインのケーブリングはそのコンピュータ中のすべてのＸラインに複製される。したがって、この種の「規則的」コンピュータでのケーブリング・アーキテクチャを指定するには、長さＬＸのラインでのケーブリング、長さＬＹのラインでのケーブリング、長さＬＺのラインでのケーブリングの３つのケーブリングを指定すれば十分である。
【００１５】
メッシュおよびトーラス相互接続アーキテクチャ
２つの一般的な従来技術の相互接続アーキテクチャが、メッシュ・アーキテクチャおよびトーラス・アーキテクチャである。例えば、図５に示すように、従来技術のメッシュ・アーキテクチャ１６０は、スイッチ１６１、１６２、１６３、１６４、１６５、１６６、１６７、１６８を含む。また、例えば、図６に示すように、従来技術のトーラス・アーキテクチャ１７０は、スイッチ１７１、１７２、１７３、１７４、１７５、１７６、１７７、１７８を含む。
【００１６】
再び次元Ｘを例にとると、メッシュ・アーキテクチャ１６０では、１Ｘライン中のＸスイッチは直線式に、すなわち、スイッチ１６１、１６２、１６３、１６４、１６５、１６６、１６７、１６８として接続される。トーラス・アーキテクチャ１７０では、Ｘスイッチは巡回式に、すなわち、１７１、１７３、１７５、１７７、１７８、１７６、１７４、１７２、から１７１に戻るように接続される。図５および６には長さ８のラインでのメッシュおよびトーラスが示されているが、これらが任意の長さのラインにどのように適用され得るかは明らかである。
【００１７】
トーラス・アーキテクチャ１７０は、スイッチ１６１とスイッチ１６８の間にケーブルを付加することによってメッシュ・アーキテクチャ１６０から得ることもできるはずである。しかし、これは、ケーブルの長さの制限に違反することになる可能性が高い。ケーブルを短く保つには、図６に示すようにそのサイクルが「折り畳まれる」。
【００１８】
メッシュおよびトーラスは、図５および６でのラインのメッシュおよびトーラス・ケーブリングを、そのコンピュータ中のすべてのＸライン、Ｙライン、Ｚラインにそれぞれ複製することによって、２次元および３次元配列に定義される。
【００１９】
区画化
相互接続アーキテクチャの有用性での重要な一要因は、それがコンピュータをいくつかの独立部分に区画化する際の柔軟性である。区画化は、いくつかのプログラム、あるいは「ジョブ」をコンピュータ上で同時に走らせる際に重要である。ジョブの実行を開始するときに、ユーザは「区画」、すなわちそのジョブ専用に使用されるコンピュータの部分を指定する。「ユーザ」は、人間のユーザ、またはジョブ・スケジューラなどのシステム・ソフトウェアの一部とすることができる。コンピュータの１区画とは、１ジョブによって使用される１組のＰＵである。
【００２０】
ＰＵの指定
区画Ｐは、各次元ごとに、Ｘ次元での座標の集合ＰＸ、Ｙ次元での座標の集合ＰＹ、Ｚ次元での座標の集合ＰＺを与えることによって指定される。したがって、座標（ｘ、ｙ、ｚ）のＰＵは、ｘがＰＸに属し、ｙがＰＹに属し、ｚがＰＺに属する場合に限り、区画Ｐに属する。言い換えると、ＰＵの座標の集合は、ＰＸ、ＰＹおよびＰＺのデカルト積である。例えば、８×８×８の３次元コンピュータでは、ユーザは、Ｘ次元での集合ＰＸ＝｛３，４｝、Ｙ次元での集合ＰＹ＝｛３，５｝、Ｚ次元での集合ＰＺ＝｛１｝によって１区画を指定することができる。この区画に属するＰＵは、座標（３、３、１）、（３、５、１）、（４、３、１）、（４、５、１）のＰＵである。
【００２１】
各区画は、ジョブが開始、終了するときに、それぞれ、動的に形成され、解除される。あるジョブが別のジョブを妨害するのを防ぐために、異なるジョブは同じＰＵも、同じケーブルも使用することができない。異なるジョブは同じスイッチを使用できるが、スイッチの使用は、異なるジョブが同じＰＵまたはケーブルを使用できないという要件によって制限される。
【００２２】
接続タイプの指定
区画中のＰＵを指定する以外に、ユーザは、区画の接続タイプ、すなわちアーキテクチャも指定する。２つの非常に一般的な接続タイプがメッシュ・アーキテクチャおよびトーラス・アーキテクチャである。接続タイプの指定は、ユーザがコンピュータの１区画を取得している場合、そのユーザは、自分の区画がそのコンピュータ全体の小規模バージョン「に見える」ようにしようとすることを示すものである。
【００２３】
メッシュ・アーキテクチャ
メッシュ・アーキテクチャ１６０などのメッシュ・アーキテクチャは、あらゆる区画が、スイッチを適正に設定することによって（一般に、より小さい）メッシュとして相互接続され得るという望ましい特性を有する。例えば、図７には、区画｛１６３，１６４，１６６，１６７｝が、接続１８０、１８１、１８２、１８３、１８４、１８５、１８６、１８７、１８８、１８９、１９０を介して従来技術のメッシュとして相互接続されるために各スイッチがどのように設定されるかが示されている。より詳細には、図７は、区画｛１６３，１６４，１６６，１６７｝が、内部結合１８０、１８２、１８３、１８５、１８７、１８８、１９０および外部接続１８１、１８４、１８６、１８９を介して従来技術のメッシュとして相互接続されるために各スイッチがどのように設定されるかを示すものである。図７には、ＰＵ１６４と１６６など２つのＰＵ間の接続が、外部接続１８４と１８６など連続する２つ以上の外部接続によってなされ得ることも示されている。ＰＵ１６５は、ＰＵ１６５が（ａ）別の既存の区画に属していた場合、あるいは（ｂ）故障していた場合には、「スキップ」され得る。外部接続は、ケーブル、光ファイバ、または別のタイプの電磁的結合を用いて実装され得る。
【００２４】
より一般的には、２つの異なる区画が「オーバーラップ」しないという条件で、それぞれがメッシュとして相互接続された、複数の区画が同時に存在し得る。より正確には、１次元区画（座標の集合）のスパンは、その区画中の最小の座標とその区画中の最大の座標とを含むそれらの間にある座標の集合であると定義される。例えば、区画｛１６３，１６４，１６６，１６７｝のスパンは｛１６３，１６４，１６５，１６６，１６７｝である。２つの区画がオーバーラップしないという要件は、それらのスパンが共通の座標を含まないことである。
【００２５】
多次元設定中のオーバーラップ区画は、１次元の場合のオーバーラップ区画を一般化したものである。３次元の場合には、例えば、３次元区画Ｐが、座標集合ＰＸ、ＰＹ、ＰＺのデカルト積によって定義される場合には、Ｐのスパンは、ＰＸのスパン、ＰＹのスパン、ＰＺのスパンのデカルト積になる。２つの３次元区画ＰおよびＱは、ＰのスパンとＱのスパンが共通の座標を含む場合には、オーバーラップする。ＰがＰＸ、ＰＹ、ＰＺによって定義され、ＱがＱＸ、ＱＹ、ＱＺによって定義される場合、ＰおよびＱは、ＰＸとＱＸがオーバーラップし、ＰＹとＱＹがオーバーラップし、あるいはＰＺとＱＺがオーバーラップする場合には、オーバーラップする。
【００２６】
トーラス・アーキテクチャ
図６のトーラス・アーキテクチャ１７０などのトーラス・アーキテクチャは、複数の非オーバーラップ区画中のあらゆる区画が（より小さい）トーラスの相互接続構造を持つように構成され得るという望ましい特性を持たない。図示のように、これは、サイズ２以上の任意の２区画について当てはまる。例えば、区画｛１７１，１７２｝はトーラスとして相互接続され得るが、それはライン中のケーブルすべてを使用した場合だけである。したがって、この区画は、例えば、｛１７６，１７７｝など、サイズが少なくとも２の任意のトーラス相互接続区画と同時に存在し得ない。
【００２７】
使用される接続数
ＰＸがＸラインの区画であるとし、ＮＸがＰＸ中の座標の数であるとすると、ＮＸ≧２の場合には、ＰＸの任意のトーラス相互接続は、Ｘライン中で少なくともＮＸ個の外部接続、またはケーブルを使用する。同じことがＹ次元とＺ次元にも当てはまる。
【００２８】
区間区画
あるラインの１次元区画Ｐは、Ｐが｛１７３，１７４，１７５，１７６，１７７｝などの連続した座標の集合である場合には、区間区画である。ある配列の３次元区画Ｐは、ＰＸ、ＰＹおよびＰＺがすべて１次元区間区画である場合には、区間区画である。Ｐは、ＰのスパンがＰそれ自体と同じである場合に限り区間区画である。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
したがって、トーラス区画化を容易にするために並列コンピュータのプロセッサを相互接続する方法およびシステムが求められている。
【課題を解決するための手段】
【００３０】
本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法およびシステムを提供し、（ａ）プロセッサのそれぞれは処理装置およびスイッチを含み、（ｂ）スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、（ｃ）Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、（ｄ）区画のそれぞれは、プロセッサのうちの少なくとも１つの処理装置を含み、（ｅ）Ｌは２以上の整数、Ｒは１以上の整数である。例示的実施形態では、この方法およびシステムは、（１）Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続すること、および（２）区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定することを含む。
【００３１】
例示的実施形態では、接続することは、スイッチ１の第１の外部ポートとスイッチ２の第１の外部ポートを結合することを含む。別の実施形態では、接続することは、（ａ）Ｌ≧３の場合には、第（Ｌ−１）のスイッチの第４の外部ポートと第Ｌのスイッチの第４の外部ポートを接続すること、（ｂ）１≦ｉ≦Ｌ−１（ｉは整数）の場合には、第ｉのスイッチの第３の外部ポートと第（ｉ＋１）のスイッチの第２の外部ポートを接続すること、および（ｃ）１≦ｉ≦Ｌ−２（ｉは整数）の場合には、第ｉスイッチの第４の外部ポートと第（ｉ＋２）スイッチの第１の外部ポートを接続することを含む。具体的実施形態では、接続することは、Ｌ個のスイッチをケーブルで接続することを含む。
【００３２】
例示的実施形態では、設定することは、区画のスパンを計算することを含む。例示的実施形態では、計算することは、（ａ）区画中の最小座標、ＭＩＮを探索すること、（ｂ）区画中の最大座標、ＭＡＸを決定すること、および（ｃ）その区画のスパンが座標ｉの集合（ＭＩＮ≦ｉ≦ＭＡＸ、ｉは整数）と等しくなるように設定することを含む。別の実施形態では、計算することは、区画のスパンが厳密に１つの座標を含み、ｉがそのスパンに属する１座標である場合には、第ｉのスイッチの第１の内部ポートと第２の内部ポート（Ｉ１、Ｉ２）を接続することを含む。
【００３３】
別の実施形態では、計算することは、区画のスパンが厳密に２つの座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標である場合には、（１）ｉ＝１の場合は、（ａ）第１のスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続すること、（ｂ）第１のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、（ｃ）第２のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続すること、および（ｄ）第２のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続することを、（２）ｉ＝Ｌ−１の場合は、（ａ）第（Ｌ−１）のスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続すること、（ｂ）第（Ｌ−１）のスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続すること、第Ｌのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続すること、および（ｄ）第Ｌのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続することを、（３）それ以外で、２≦ｉ≦Ｌ−２の場合は、（ａ）第（ｉ−１）のスイッチの第３の外部ポートと第４の外部ポート（Ｅ３、Ｅ４）を接続すること、（ｂ）第ｉのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続すること、（ｃ）第ｉのスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続すること、（ｄ）第（ｉ＋１）のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、および（ｅ）第（ｉ＋１）のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続することを含む。
【００３４】
更に別の実施形態では、計算することは、区画のスパンが厳密に３つの座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンに属する３座標である場合には、（１）第ｉのスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続すること、（２）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続すること、（３）第（ｉ＋２）のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、（４）第（ｉ＋２）のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続すること、（５）（ｉ＋１）がその区画に属する場合には、（ａ）第（ｉ＋１）のスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続すること、および（ｂ）第（ｉ＋１）のスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続すること、（６）（ｉ＋１）がその区画に属さない場合には、第（ｉ＋１）のスイッチの第２の外部ポートと第３の外部ポート（Ｅ２、Ｅ３）を接続することを含む。
【００３５】
また更に別の実施形態では、計算することは、区画のスパンが少なくとも４座標を含み、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである場合には、（１）ｉ＝ＭＩＮの場合は、（ａ）第ｉのスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続すること、および（ｂ）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続することを、（２）ｉ＝ＭＡＸの場合は、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、および（ｂ）第ｉのスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続することを、（３）ｉ＝ＭＩＮ＋１かつｉがその区画に属する場合は、（ａ）第ｉのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続すること、および第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続することを、（４）ｉ＝ＭＩＮ＋１かつｉがその区画に属さない場合は、第ｉのスイッチの第２の外部ポートと第４の外部ポートを接続することを、（５）ｉ＝ＭＡＸ−１かつｉがその区画に属する場合は、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、および（ｂ）第ｉのスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続することを、（６）ｉ＝ＭＡＸ−１かつｉがその区画に属さない場合は、第ｉのスイッチの第１の外部ポートと第３の外部ポート（Ｅ１、Ｅ３）を接続することを、（７）ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉがその区画に属する場合は、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続すること、および（ｂ）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続することを、（８）ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉがその区画に属さない場合は、第ｉのスイッチの第１の外部ポートと第４の外部ポート（Ｅ１、Ｅ４）を接続することを含む。
【００３６】
例示的実施形態では、この方法およびシステムは、Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続することを含む。例示的実施形態では、接続することは、スイッチ１の第１の外部ポートとスイッチ２の第１の外部ポートを接続することを含む。別の実施形態では、接続することは、（ａ）Ｌ≧３の場合は、第（Ｌ−１）のスイッチの第４の外部ポートと第Ｌのスイッチの第４の外部ポートを接続すること、（ｂ）１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの第３の外部ポートと第（ｉ＋１）のスイッチの第２の外部ポートを接続すること、および（ｃ）１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの第４の外部ポートと第（ｉ＋２）のスイッチの第１の外部ポートを接続することを含む。具体的実施形態では、接続することは、Ｌ個のスイッチをケーブルで接続することを含む。別の実施形態では、この方法およびシステムは、区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定することを含む。
【００３７】
本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法およびシステムを提供し、（ａ）プロセッサのそれぞれは、処理装置およびスイッチを含み、（ｂ）スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、（ｃ）Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、（ｄ）各区画のそれぞれはプロセッサのうちの少なくとも１つの処理装置を含み、（ｅ）Ｌは２以上の整数、Ｒは１以上の整数であり、（ｆ）Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチは拡張トーラス・アーキテクチャで接続される。例示的実施形態では、この方法およびシステムは、区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定することを含む。
【００３８】
本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する読取り可能なプログラム・コードが実施された、プログラマブル・コンピュータと共に使用可能なコンピュータ・プログラム製品を提供し、各プロセッサのそれぞれは処理装置およびスイッチを含み、スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、各区画のそれぞれはプロセッサのうちの少なくとも１つの処理装置を含み、Ｌは２以上の整数、Ｒは１以上の整数である。例示的実施形態では、このコンピュータ・プログラム製品は、（１）Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続するためのコンピュータ可読コード、および（２）区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定するためのコンピュータ可読コードを含む。
【発明を実施するための最良の形態】
【００３９】
本発明は、トーラス区画化を容易にするために並列コンピュータのプロセッサを相互接続する方法およびシステムを提供する。例示的実施形態では、この方法およびシステムは、メッシュ・アーキテクチャ１６０などのメッシュ・アーキテクチャ、およびトーラス・アーキテクチャ１７０などのトーラス・アーキテクチャ中のスイッチの空き外部ポートを利用して、メッシュ・アーキテクチャおよびトーラス・アーキテクチャにはない有用な特性を備える相互接続アーキテクチャを実現する。例示的実施形態では、本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法およびシステムを提供し、（ａ）プロセッサのそれぞれは処理装置およびスイッチを含み、（ｂ）スイッチは第１の外部ポート、第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、および第２の内部ポートを含み、（ｃ）Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、（ｄ）区画のそれぞれは、プロセッサのうちの少なくとも１つの処理装置を含み、（ｅ）Ｌは２以上の整数、Ｒは１以上の整数である。例示的実施形態では、この方法およびシステムは、（１）Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続すること、および（２）区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定することを含む。
【００４０】
図１２を参照すると、例示的実施形態では、本発明は、Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続するステップ６１０、および各区画のそれぞれを相互接続するために接続されたＬ個のスイッチを設定するステップ６１２を含む。
【００４１】
スイッチの相互接続
例示的実施形態では、この方法およびシステムは、図８に、長さＬ＝８個の対応するＰＵおよび８個の対応するスイッチ１７１、１７２、１７３、１７４、１７５、１７６、１７７、１７８を含む８プロセッサ（Ｌは２以上の整数）の例示的ラインで示すように、各スイッチの外部ポート間のＬ個のスイッチを拡張トーラス・アーキテクチャで相互接続することを含む。例示的実施形態では、各スイッチはケーブルで相互接続される。
【００４２】
例示的実施形態では、この方法およびシステムは、スイッチのすべてで外部ポートを接続する。例示的実施形態では、この方法およびシステムは、図８の接続２１０で例示するように、スイッチ１７１などのスイッチ１のポートＥ１とスイッチ１７２などのスイッチ２のポートＥ１を接続する。例示的実施形態では、Ｌ≧３の場合、この方法およびシステムは、２２０で例示するように、スイッチ１７７などのスイッチ（Ｌ−１）のポートＥ４とスイッチ１７８などのスイッチＬのポートＥ４を接続する。例示的実施形態では、１≦ｉ≦Ｌ−１であるすべての数ｉについて、この方法およびシステムは、接続２３０、２３１、２３２、２３３、２３４、２３５、２３６のように、スイッチｉのポートＥ３とスイッチ（ｉ＋１）のポートＥ２を接続する。例示的実施形態では、１≦ｉ≦Ｌ−２であるすべての数ｉについて、この方法およびシステムは、接続２４０、２４１、２４２、２４３、２４４、２４５のように、スイッチｉのポートＥ４とスイッチ（ｉ＋２）のポートＥ１を接続する。具体的実施形態では、この方法およびシステムは、ケーブルで各ポートを接続する。
【００４３】
各スイッチには、多くとも４つのケーブルがそのスイッチの外部ポートに接続されるにすぎない。例示的実施形態では、各スイッチは、この方法およびシステムが適用される前は、最初に、少なくとも４つの空き外部ポートを有する。
【００４４】
図１３を参照すると、例示的実施形態では、接続するステップ６１０は、スイッチ１の第１の外部ポートとスイッチ２の第１の外部ポートを結合するステップ７１０を含む。別の実施形態では、図１４に示すように、接続するステップ６１０は、Ｌ≧３の場合は、第（Ｌ−１）のスイッチの第４の外部ポートと第Ｌのスイッチの第４の外部ポートを接続するステップ７２２と、１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの第３の外部ポートと第（ｉ＋１）のスイッチの第２の外部ポートを接続するステップ７２４と、１≦ｉ≦Ｌ−２（ｉは整数）の場合、第ｉのスイッチの第４の外部ポートと第（ｉ＋２）のスイッチの第１の外部ポートを接続するステップ７２６とを含む。具体的実施形態では、図１５に示すように、接続するステップ６１０は、Ｌ個のスイッチをケーブルで接続するステップ７３２を含む。
【００４５】
スイッチの設定
例示的実施形態では、この方法およびシステムは、少なくとも１つの区画Ｐについて、その少なくとも１つの区画Ｐをトーラスとして相互接続するために、拡張トーラス・アーキテクチャ２００などのトーラス・アーキテクチャで相互接続されているＬ個のスイッチを設定することを含む。本発明に従って相互接続されているスイッチのライン中の任意の複数の非オーバーラップ区画について、それらのスイッチは、個々の区画に属するＰＵがトーラスとして相互接続されるように設定される。例えば、図９には、区画｛１７１｝、｛１７２，１７３，１７４，１７５｝、および｛１７６，１７７，１７８｝について、これら３区画のそれぞれがトーラスとして相互接続されて、スイッチ設定３００を生じるために、１７１、１７２、１７３、１７４、１７５、１７６、１７７、１７８がどのように設定されるかが示されている。これらの区画の１つによって使用されるケーブルおよびスイッチ接続を太線で示してある。
【００４６】
図１０に、スイッチ１７４などのスイッチを使用して２つの異なる区画、すなわち、区画｛１７１，１７２，１７３，１７４｝と｛１７５，１７６｝のための相互接続が形成されるようなスイッチ設定４００を生じる区画｛１７１，１７２，１７３，１７４｝、｛１７５，１７６｝、および｛１７７，１７８｝の例を示す。
【００４７】
図１１に、スイッチ設定５００を生じる区画｛１７１，１７３，１７５，１７６｝および｛１７７，１７８｝の例を示す。スイッチ設定５００は、Ｐのスパンが｛１７１，１７２，１７３，１７４，１７５，１７６｝である場合など、ＰのスパンがＰ自体より大きい、｛１７１，１７３，１７５，１７６｝などの区画Ｐにトーラス相互接続を形成するために、この方法およびシステムが（ａ）Ｐのスパンにトーラス相互接続を形成し、（ｂ）次いで、スイッチｃを、Ｐのスパン内にあるがＰ自体にはないすべてのｃについて、変更されたスイッチ設定がＰＵｃを迂回するようにリセットする。
【００４８】
例示的実施形態では、この方法およびシステムはＰのスパンを、（１）ＭＩＮと呼ばれる、Ｐ中の最小座標を探索し、（２）ＭＡＸと呼ばれる、Ｐ中の最大座標を探索し、（３）Ｓ（Ｐのスパン）が、ＭＩＮ≦ｉ≦ＭＡＸである座標ｉの集合と等しくなるように設定することによって計算する。例示的実施形態では、Ｓが厳密に１座標を含む場合には、この方法およびシステムは、そのスパンに属する座標であるｉを用いて、図９の接続３１０のように、スイッチｉの設定に接続（Ｉ１、Ｉ２）を付加する。
【００４９】
図１６を参照すると、例示的実施形態では、設定するステップ６１２は、区画のスパンを計算するステップ８１０を含む。図１７を参照すると、例示的実施形態では、計算するステップ８１０は、区画中の最小座標、ＭＩＮを探索するステップ８２２と、区画中の最大座標、ＭＡＸを決定するステップ８２４と、区画のスパンを座標ｉの集合（ＭＩＮ≦ｉ≦ＭＡＸ、ｉは整数）と等しくなるように設定するステップ８２６とを含む。
【００５０】
厳密に１座標を含むＳ
別の実施形態では、図１８に示すように、計算するステップ８１０は、区画のスパンが厳密に１座標を含み、ｉがそのスパンに属する１座標である場合には、第ｉのスイッチの第１の内部ポートおよび第２の内部ポート（Ｉ１、Ｉ２）を接続するステップ９１０を含む。
【００５１】
厳密に２座標を含むＳ
例示的実施形態では、Ｓが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンＳに属する２座標である場合には、（１）ｉ＝１の場合は、この方法およびシステムは、（ａ）スイッチ１の設定に接続（Ｅ３、Ｉ２）および（Ｅ１、Ｉ１）を付加し、（ｂ）スイッチ２の設定に接続（Ｅ２、Ｉ２）および（Ｅ１、Ｉ１）を付加し、（２）ｉ＝Ｌ−１の場合は、この方法およびシステムは、（ａ）スイッチ（Ｌ−１）の設定に、それぞれ、図１０のスイッチ１７７での接続４１０および４１２のように、接続（Ｅ３、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（ｂ）スイッチＬの設定に、それぞれ、図１０のスイッチ１７８での接続４１４および４１６のように、接続（Ｅ２、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（３）それ以外で、２≦ｉ≦Ｌ−２の場合は、この方法およびシステムは、（ａ）スイッチ（ｉ−１）の設定に、図１０のスイッチ１７４での接続４２０のように、接続（Ｅ３、Ｅ４）を付加し、（ｂ）スイッチｉの設定に、図１０のスイッチ１７５での接続４２２および４２４のように、接続（Ｅ２、Ｉ１）および（Ｅ３、Ｉ２）を付加し、（ｃ）スイッチ（ｉ＋１）の設定に、図１０のスイッチ１７６での接続４２６および４２８のように、接続（Ｅ１、Ｉ１）および（Ｅ２、Ｉ２）を付加する。
【００５２】
別の実施形態では、図１９に示すように、計算するステップ８１０は、区画のスパンが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標であり、ｉ＝１である場合には、（ａ）第１のスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続し、（ｂ）第１のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続し、（ｃ）第２のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続し、（ｄ）第２のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続するステップ１０１２を含む。
【００５３】
別の実施形態では、図２０に示すように、計算するステップ８１０は、区画のスパンが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標であり、ｉ＝Ｌ−１である場合には、（ａ）第（Ｌ−１）のスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続し、（ｂ）第（Ｌ−１）のスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続し、（ｃ）第Ｌのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続し、（ｄ）第Ｌのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続するステップ１０２２を含む。
【００５４】
別の実施形態では、図２１に示すように、計算するステップ８１０は、区画のスパンが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンに属する２座標であり、２≦ｉ≦Ｌ−２である場合には、（ａ）第（ｉ−１）のスイッチの第３の外部ポートと第２の外部ポート（Ｅ３、Ｅ４）を接続し、（ｂ）第ｉのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続し、（ｃ）第ｉのスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続し、（ｄ）第（ｉ＋１）のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続し、（ｅ）第（ｉ＋１）のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続するステップ１０３２を含む。
【００５５】
厳密に３座標を含むＳ
例示的実施形態では、Ｓが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンに属する３座標である場合には、この方法およびシステムは、（１）スイッチｉの設定に、図９のスイッチ１７６での接続３２０および３２２のように、接続（Ｅ３、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（２）スイッチ（ｉ＋２）の設定に、図９のスイッチ１７８での接続３３０および３３２のように、接続（Ｅ１、Ｉ１）および（Ｅ２、Ｉ２）を付加し、（３）（ｉ＋１）が区画Ｐに属する場合には、スイッチ（ｉ＋１）の設定に、図９のスイッチ１７７での接続３４０および３４２のように、接続（Ｅ２、Ｉ１）および（Ｅ３、Ｉ２）を付加し、（４）（ｉ＋１）が区画Ｐに属さない場合には、スイッチ（ｉ＋１）の設定に、接続（Ｅ２、Ｅ３）を付加する。
【００５６】
別の実施形態では、図２２に示すように、計算するステップ８１０は、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標である場合には、第ｉのスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続するステップ１１１２と、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標である場合には、第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続するステップ１１１４と、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標である場合には、第（ｉ＋２）のスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続するステップ１１１６と、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標である場合には、第（ｉ＋２）のスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続するステップ１１１８を含む。
【００５７】
別の実施形態では、図２３に示すように、計算するステップ８１０は、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標であり、（ｉ＋１）がその区画に属する場合には、（ａ）第（ｉ＋１）のスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続し、（ｂ）第（ｉ＋１）のスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続するステップ１１２２と、区画のスパンが厳密に３座標を含み、ｉ、ｉ＋１、ｉ＋２がそのスパンの属する３座標であり、（ｉ＋１）がその区画に属さない場合には、第（ｉ＋１）のスイッチの第２の外部ポートと第３の外部ポート（Ｅ２、Ｅ３）を接続するステップ１１２４とを含む。
【００５８】
少なくとも４座標を含むＳ
例示的実施形態では、Ｓが少なくとも４座標を含み、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである場合には、（１）ｉ＝ＭＩＮの場合は、この方法およびシステムはスイッチｉの設定に、図１０のスイッチ１７１での接続４３０および４３２などの接続（Ｅ３、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（２）ｉ＝ＭＡＮの場合は、この方法およびシステムはスイッチｉの設定に、図１０のスイッチ１７４での接続４４０および４４２などの接続（Ｅ１、Ｉ１）および（Ｅ２、Ｉ２）を付加し、（３）ｉ＝ＭＩＮ＋１かつｉがＰに属する場合は、この方法およびシステムはスイッチｉの設定に、スイッチ１７２での接続４５０および４５２などの接続（Ｅ２、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（４）ｉ＝ＭＩＮ＋１かつｉがＰに属さない場合は、この方法およびシステムはスイッチｉの設定に、図１１のスイッチ１７２での接続５１０などの接続（Ｅ２、Ｅ４）を付加し、（５）ｉ＝ＭＡＸ−１かつｉがＰに属する場合は、この方法およびシステムはスイッチｉの設定に、図１０のスイッチ１７３での接続４６０および４６２などの接続（Ｅ１、Ｉ１）および（Ｅ３、Ｉ２）を付加し、（６）ｉ＝ＭＡＸ−１かつｉがＰに属さない場合は、この方法およびシステムはスイッチｉの設定に接続（Ｅ１、Ｅ３）を付加し、（７）ＭＩＮ＋２≦ｉ＝ＭＡＸ−２かつｉがＰに属する場合は、この方法およびシステムはスイッチｉの設定に、図１１のスイッチ１７３での接続５２０および５２２などの接続（Ｅ１、Ｉ１）および（Ｅ４、Ｉ２）を付加し、（８）ＭＩＮ＋２≦ｉ＝ＭＡＸ−２かつｉがＰに属さない場合は、この方法およびシステムはスイッチｉの設定に、図１１のスイッチ１７４での接続５３０などの接続（Ｅ１、Ｅ４）を付加する。
【００５９】
別の実施形態では、図２４に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＩＮである場合には、（ａ）第ｉのスイッチの第３の外部ポートと第１の内部ポート（Ｅ３、Ｉ１）を接続し、（ｂ）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続するステップ１２１２を含む。
【００６０】
別の実施形態では、図２５に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＡＸである場合には、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続し、（ｂ）第ｉのスイッチの第２の外部ポートと第２の内部ポート（Ｅ２、Ｉ２）を接続するステップ１２２２を含む。
【００６１】
別の実施形態では、図２６に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＩＮ＋１かつｉがその区画に属する場合には、（ａ）第ｉのスイッチの第２の外部ポートと第１の内部ポート（Ｅ２、Ｉ１）を接続し、（ｂ）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続するステップ１２３２を含む。
【００６２】
別の実施形態では、図２７に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＩＮ＋１かつｉがその区画に属さない場合には、第ｉのスイッチの第２の外部ポートと第４の外部ポート（Ｅ２、Ｅ４）を接続するステップ１２４２を含む。
【００６３】
別の実施形態では、図２８に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＡＸ−１かつｉがその区画に属する場合には、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続し、（ｂ）第ｉのスイッチの第３の外部ポートと第２の内部ポート（Ｅ３、Ｉ２）を接続するステップ１２５２を含む。
【００６４】
別の実施形態では、図２９に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ｉ＝ＭＡＸ−１かつｉがその区画に属さない場合には、第ｉのスイッチの第１の外部ポートと第３の外部ポート（Ｅ１、Ｅ３）を接続するステップ１２６２を含む。
【００６５】
別の実施形態では、図３０に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉがその区画に属する場合には、（ａ）第ｉのスイッチの第１の外部ポートと第１の内部ポート（Ｅ１、Ｉ１）を接続し、（ｂ）第ｉのスイッチの第４の外部ポートと第２の内部ポート（Ｅ４、Ｉ２）を接続するステップ１２７２を含む。
【００６６】
別の実施形態では、図３１に示すように、計算するステップ８１０は、区画のスパンが、各座標ｉがＭＩＮ≦ｉ≦ＭＡＸである少なくとも４座標を含み、ＭＩＮ＋２≦ｉ≦ＭＡＸ−２かつｉがその区画に属さない場合には、第ｉのスイッチの第１の外部ポートと第４の外部ポート（Ｅ１、Ｅ４）を接続するステップ１２８２を含む。
【００６７】
代替のスイッチ設定
例示的実施形態では、コンピュータのハードウェア設計に応じて、スイッチの設定への変更が必要とされることがある。例えば、特定のスイッチにあるポートＩ１およびＩ２への接続を入れ替える必要があることもある。例えば、Ｓが厳密に２座標を含み、ｉおよびｉ＋１がそのスパンＳに属する２座標であり、ｉ＝１である場合には、この方法およびシステムは、接続（Ｅ３、Ｉ２）および（Ｅ１、Ｉ１）ではなく、接続（Ｅ３、Ｉ１）および（Ｅ１、Ｉ２）を付加する。
【００６８】
スイッチの接続
図３２を参照すると、例示的実施形態では、本発明は、Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチを拡張トーラス・アーキテクチャで接続するステップ１３１０を含む。図３３を参照すると、例示的実施形態では、接続するステップ１３１０は、スイッチ１の第１の外部ポートとスイッチ２の第１の外部ポートを結合するステップ１３２２を含む。別の実施形態では、図３４に示すように、接続するステップ１３１０は、Ｌ≧３の場合は、第（Ｌ−１）のスイッチの第４の外部ポートと第Ｌのスイッチの第４の外部ポートを接続するステップ１３３２と、１≦ｉ≦Ｌ−１（ｉは整数）の場合は、第ｉのスイッチの第３の外部ポートと第（ｉ＋１）のスイッチの第２の外部ポートを接続するステップ１３３４と、１≦ｉ≦Ｌ−２（ｉは整数）の場合は、第ｉのスイッチの第４の外部ポートと第（ｉ＋２）のスイッチの第１の外部ポートを接続するステップ１３３６とを含む。具体的実施形態では、図３５に示すように、接続するステップ１３１０は、ケーブルでＬ個のスイッチを接続するステップ１３４２を含む。別の実施形態では、図３６に示すように、本発明は、区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定するステップ１３５２を含む。例示的実施形態では、設定するステップ１３５２は、設定するステップ６１２を含む。
【００６９】
スイッチの設定
例示的実施形態では、本発明は、トーラス区画化を容易にするために並列コンピュータのＬ個のプロセッサを相互接続する方法およびシステムを提供し、（ａ）プロセッサのそれぞれは処理装置およびスイッチを含み、（ｂ）スイッチは第１の外部ポート、および第２の外部ポート、第３の外部ポート、第４の外部ポート、第１の内部ポート、第２の内部ポートを含み、（ｃ）Ｌ個のプロセッサはＲ個の非オーバーラップ区画を含み、（ｄ）区画のそれぞれはプロセッサのうちの少なくとも１つの処理装置を含み、（ｅ）Ｌは２以上の整数、Ｒは１以上の整数であり、（ｆ）Ｌ個のスイッチの外部ポート間のＬ個のプロセッサのＬ個のスイッチは拡張トーラス・アーキテクチャで接続される。図３７を参照すると、例示的実施形態では、本発明は、区画のそれぞれをトーラスとして相互接続するために接続されたＬ個のスイッチを設定するステップ１４１０を含む。例示的実施形態では、設定するステップ１４１０は設定するステップ６１２を含む。
【００７０】
多次元配列
スイッチの相互接続
例示的実施形態では、この方法およびシステムは、ＰＵおよびスイッチを備えるプロセッサのｎ次元配列（ｎは２以上の整数）でスイッチを相互接続することを含む。例えば、ｎ＝３次元配列では、この方法およびシステムは、（１）１Ｘライン、１Ｙライン、および１Ｚラインでのスイッチを相互接続し、（２）次いで、その結果生じる相互接続を、その配列のすべてのＸライン、すべてのＹライン、およびすべてのＺラインに複製する。
【００７１】
スイッチの設定
例示的実施形態では、スイッチの設定は、ＰＵおよびスイッチを備えるプロセッサのｎ次元配列（ｎは２以上の整数）に適用される。ＰＸ、ＰＹ、ＰＺによって指定される区画を仮定すると、この方法およびシステムは、（１）１次元区画ＰＸを用いたスイッチの設定を適用してすべてのＸスイッチでのスイッチ設定を探索し、（２）１次元区画ＰＹを用いたスイッチの設定を適用してすべてのＹスイッチでのスイッチ設定を探索し、（３）１次元区画ＰＺを用いたスイッチの設定を適用してすべてのＺスイッチでのスイッチ設定を探索する。
【００７２】
例示的実施形態では、３次元配列における任意の複数Ｍ個の非オーバーラップ区画に、任意の順序で個々の区画ごとにスイッチを設定することによって、この方法およびシステムは、Ｍ中の個々の区画Ｐごとに、Ｐに属するＰＵが３次元トーラスとして相互接続されるようにスイッチを設定する。また、例示的実施形態では、３次元配列中の任意の複数Ｍ個の非オーバーラップ区画に任意の順序で個々の区画ごとに、それぞれ、サイズＮＸ、ＮＹ、ＮＺの集合ＰＸ、ＰＹ、ＰＺによって定義されるＭ中の個々の区画Ｐごとに、その区画のＸラインごとにスイッチを設定することによって、この方法およびシステムは、以下のようにトーラス・アーキテクチャを形成する。
（１）ＮＸ＝１の場合は、外部接続を使用したＸライン中のＰのトーラス相互接続は形成されない。
（２）ＰＸが区間区画であり、ＮＸ＝２である場合は、多くとも３つの外部接続を使用してＸライン中のＰのトーラス相互接続が形成されるにすぎず、ＮＸ＝２はＸライン中のＰのトーラス相互接続を形成するのに必要とされる最小可能外部接続数よりせいぜい１大きいにすぎない。
（３）ＰＸが区間区画であり、ＮＸ≧３である場合は、多くともＮＸ個の外部接続を使用してＸライン中のＰの相互接続が形成されるにすぎず、ＮＸ≧３はＸライン中のＰのトーラス相互接続を形成するのに必要とされる最小可能外部接続数である。
【００７３】
動的環境
本発明が、区画がいつでも形成され、解除され得る動的環境でも適用され得ることに留意すべきである。Ｐ１、Ｐ２、・・・ＰｋがＭ中の区画を表すとすると、この方法およびシステムは、（１）Ｐ１に、Ｐ１のトーラス相互接続を実現するスイッチ接続の集合Ｃ１が得られるようにスイッチを設定し、（２）次いで、Ｐ２に、そのうちのどの接続もＣ１中の接続によって使用されるスイッチのポートを使用せず、そのうちの接続がＣ１中の接続のいずれも妨げることなく実施され得る、Ｐ２のトーラス相互接続を実現するスイッチ接続の集合Ｃ２が得られるようにスイッチを設定し、（３）次いで、Ｐ３に、そのうちのどの接続もＣ１またはＣ２中の接続によって使用されるスイッチのポートを使用せず、そのうちの接続がＣ１またはＣ２中の接続のいずれも妨げることなく実施され得る、Ｐ３のトーラス相互接続を実現するスイッチ接続の集合Ｃ３が得られるようにスイッチを設定し、（４）残りの区画についてもＰｋに達するまで同様にスイッチを設定する。
【００７４】
例示的実施形態では、Ｐ１、Ｐ２、・・・Ｐｋが複数の非オーバーラップ区画であるとすると、個々の区画のトーラス相互接続を実現するスイッチ接続の集合を生成するためにスイッチを設定することによって、ＰがＰ１、Ｐ２、・・・Ｐｋのいずれともオーバーラップしない任意の区画に関して、この方法およびシステムは、以前にＰ１、Ｐ２、・・・Ｐｋについて得られたスイッチ接続のいずれも妨げることのないＰのトーラス相互接続を実現するスイッチ接続の集合を得る。
【００７５】
例示的実施形態では、ｆ（１）＝０、ｆ（２）＝３、Ｎ≧３のすべてのＮについてｆ（Ｎ）＝Ｎによって定義される関数ｆを用いると、区画ＰがＰ１、Ｐ２、・・・Ｐｋのいずれともオーバーラップしない区間区画である場合には、この方法およびシステムは、多くとも以下の外部接続数を有するにすぎないＰのトーラス相互接続を形成する。
ｆ（ＮＸ）ＮＹ  ＮＺ＋ＮＸ  ｆ（ＮＹ）ＮＺ＋ＮＸ  ＮＹ  ｆ（ＮＺ）
ＮＸもＮＹもＮＺも２ではない場合には、この方法およびシステムは、Ｐのトーラス相互接続を形成するのに必要とされる最小可能外部接続数を用いてＰのトーラス相互接続を形成する。
【００７６】
結論
以上、本発明の好ましい実施形態および様々な代替手段について十分に説明してきたが、本明細書での教示が与えられた場合には、本発明から逸脱しない多数の代替手段および均等物が存在することを、当分野の技術者は理解するであろう。したがって、本発明は、前述の説明によってではなく、添付の特許請求の範囲によってのみ限定されるものである。
【図面の簡単な説明】
【００７７】
【図１】従来技術のプロセッサを示す構成図である。
【図２】２つの従来技術のプロセッサの従来技術の相互接続を示す構成図である。
【図３】従来技術の配列を示す図である。
【図４】従来技術の配列を示す図である。
【図５】従来技術のメッシュ相互接続アーキテクチャを示す構成図である。
【図６】従来技術のトーラス相互接続アーキテクチャを示す構成図である。
【図７】従来技術のメッシュ相互接続アーキテクチャを示す構成図である。
【図８】本発明の例示的実施形態による拡張トーラス・アーキテクチャを示す構成図である。
【図９】本発明の例示的実施形態によるスイッチ設定を示す構成図である。
【図１０】本発明の例示的実施形態によるスイッチ設定を示す構成図である。
【図１１】本発明の例示的実施形態によるスイッチ設定を示す構成図である。
【図１２】本発明の例示的実施形態による流れ図である。
【図１３】本発明の例示的実施形態による接続するステップを示す流れ図である。
【図１４】本発明の例示的実施形態による接続するステップを示す流れ図である。
【図１５】本発明の具体的実施形態による接続するステップを示す流れ図である。
【図１６】本発明の例示的実施形態による設定するステップを示す流れ図である。
【図１７】本発明の例示的実施形態による計算するステップを示す流れ図である。
【図１８】本発明の別の実施形態による計算するステップを示す流れ図である。
【図１９】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２０】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２１】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２２】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２３】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２４】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２５】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２６】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２７】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２８】本発明の別の実施形態による計算するステップを示す流れ図である。
【図２９】本発明の別の実施形態による計算するステップを示す流れ図である。
【図３０】本発明の別の実施形態による計算するステップを示す流れ図である。
【図３１】本発明の別の実施形態による計算するステップを示す流れ図である。
【図３２】本発明の例示的実施形態による流れ図である。
【図３３】本発明の例示的実施形態による接続するステップを示す流れ図である。
【図３４】本発明の例示的実施形態による接続するステップを示す流れ図である。
【図３５】本発明の具体的実施形態による接続するステップを示す流れ図である。
【図３６】本発明の別の実施形態による流れ図である。
【図３７】本発明の例示的実施形態による流れ図である。
【符号の説明】
【００７８】
１１０、１２０  プロセッサ
１１２、１２２  ＰＵ
１１４、１２４  スイッチ
１３０  ケーブル
１４０  ２次元配列
１５２  Ｘライン
１５４  Ｙライン
１６０  メッシュ・アーキテクチャ
１６１〜１６８  スイッチ
１７０  トーラス・アーキテクチャ
１７１〜１７８  スイッチ
２００  拡張トーラス・アーキテクチャ
３００、４００、５００  スイッチ設定
Ｅ１〜Ｅ４  外部ポート
Ｉ１、Ｉ２  内部ポート
【図１】
2005174289.tif 000003
【図２】
2005174289.tif 000004
【図３】
2005174289.tif 000005
【図４】
2005174289.tif 000006
【図５】
2005174289.tif 000007
【図６】
2005174289.tif 000008
【図７】
2005174289.tif 000009
【図８】
2005174289.tif 000010
【図９】
2005174289.tif 000011
【図１０】
2005174289.tif 000012
【図１１】
2005174289.tif 000013
【図１２】
2005174289.tif 000014
【図１３】
2005174289.tif 000015
【図１４】
2005174289.tif 000016
【図１５】
2005174289.tif 000017
【図１６】
2005174289.tif 000018
【図１７】
2005174289.tif 000019
【図１８】
2005174289.tif 000020
【図１９】
2005174289.tif 000021
【図２０】
2005174289.tif 000022
【図２１】
2005174289.tif 000023
【図２２】
2005174289.tif 000024
【図２３】
2005174289.tif 000025
【図２４】
2005174289.tif 000026
【図２５】
2005174289.tif 000027
【図２６】
2005174289.tif 000028
【図２７】
2005174289.tif 000029
【図２８】
2005174289.tif 000030
【図２９】
2005174289.tif 000031
【図３０】
2005174289.tif 000032
【図３１】
2005174289.tif 000033
【図３２】
2005174289.tif 000034
【図３３】
2005174289.tif 000035
【図３４】
2005174289.tif 000036
【図３５】
2005174289.tif 000037
【図３６】
2005174289.tif 000038
【図３７】
2005174289.tif 000039