(57)【要約】【課題】高性能計算（ＨＰＣ）システムにおけるオン・デマンド・インスタンシエーションの方法を開示する。【解決手段】上記方法は、ノード・クラスタを含むＨＰＣサーバに対して外部に共用宣言される、第１ポート番号と第１ホスト名とを規定するクライアントからの接続要求を受信する工程、第１ポート番号と第１ホスト名とに相当するＨＰＣサーバでのサービスを識別する工程、識別サービスが利用可能であるか否かを判定する工程、及び、識別するサービスが利用可能な場合、クラスタにおける１つ又は複数のノードでの識別サービスを備えるホストをインスタンス化する工程を備える。【選択図】図１
2006146865.tif 000002
【特許請求の範囲】
【請求項１】
高性能計算（ＨＰＣ）システムにおけるオン・デマンド・インスタンシエーションのロジックであって、コンピュータ判読可能媒体においてコード化され、実行される場合に方法を行うよう動作可能であり、該方法は：
第１ポート番号と第１ホスト名とを規定するクライアントからの接続要求を受信する工程；
を備え；
該第１ポート番号と該第１ホスト名は、ノード・クラスタを備えるＨＰＣサーバに対して外部に共用宣言され；
該方法は更に、該第１ポート番号と該第１ホスト名とに相当する該ＨＰＣサーバでのサービスを識別する工程；
該識別サービスが利用可能か否かを判定する工程；及び
該識別サービスが利用可能な場合、該クラスタにおける１つ又は複数のノードでの該識別サービスを備えるホストをインスタンス化する工程；
を備えることを特徴とするロジック。
【請求項２】
請求項１記載のロジックであって、該接続要求が：
伝送制御プロトコル（ＴＣＰ）接続要求又はユーザ・データグラム・プロトコル（ＵＤＰ）接続要求であることを特徴とするロジック。
【請求項３】
請求項１記載のロジックであって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセスするよう動作可能であり；
該複数のエントリの各々が：
サービス；及び
該サービスに相当する該ＨＰＣサーバに対して外部に共用宣言される、ポート番号とホスト名；
を規定し；
更に、該第１ポート番号と該第１ホスト名とに相当する該ＨＰＣサーバでの該サービスを、該ＨＰＣサーバでの該サービス・リストによって識別するよう動作可能であることを特徴とするロジック。
【請求項４】
請求項１記載のロジックであって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセスするよう動作可能であり；
該複数のエントリの各々が：
サービス；及び
該クラスタにおける１つ又は複数のノードで実行される場合に、該サービスを備えるホストに相当する該ＨＰＣサーバの内部にある、ポート番号とホスト名；
を規定し；
更に、該クラスタにおける１つ又は複数のノードでの該識別サービスを備える該ホストを、該ＨＰＣサーバでの該サービス・リストによってインスタンス化するよう動作可能であることを特徴とするロジック。
【請求項５】
請求項１記載のロジックであって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセスするよう動作可能であり；
該複数のエントリの各々が、サービスと、該サービスが利用可能か否かを示す１つ又は複数の規則を規定し；
更に、該識別サービスが利用可能か否かを、該サービス・リストによって判定するよう動作可能であることを特徴とするロジック。
【請求項６】
請求項５記載のロジックであって、該規則は：
該サービスが利用可能か否かを、該クライアントからの該接続要求に関連した時間に基づいて示すことを特徴とするロジック。
【請求項７】
請求項１記載のロジックであって、更に：
該識別サービスが利用不能である場合、該第１ポート番号に相当する該ＨＰＣサーバ上のポートをブロック化して、該識別サービスを該クライアントがアクセスすることを妨げるよう動作可能であることを特徴とするロジック。
【請求項８】
請求項１記載のロジックであって、更に：
該クラスタにおける１つ又は複数のノードで該識別サービスを備える該ホストに相当する該ＨＰＣサーバで、ブート画像、ファイル・システム、及びオペレーティング・システム（ＯＳ）構成をアクセスするよう動作可能であり；かつ
該ブート画像、該ファイル・システム及び該ＯＳ構成ファイルを用いて、該クラスタにおける１つ又は複数のノードで該識別サービスを備える該ホストをインスタンス化するよう動作可能であることを特徴とするロジック。
【請求項９】
請求項１記載のロジックであって、該識別サービスが：
ウェブ・サーバであることを特徴とするロジック。
【請求項１０】
請求項１記載のロジックであって、更に：
該クラスタにおける１つ又は複数のノードでの該識別サービスを備える該ホストのアドレスをスプーフィングし、該ホストのために、該ホストがブートしている間に接続シーケンスを開始するよう動作可能であることを特徴とするロジック。
【請求項１１】
請求項１記載のロジックであって：
該アドレスが、インターネット・プロトコル・オーバ媒体アクセス制御（ＩＰ／ＭＡＣ）アドレスであり；かつ
該接続要求が、伝送制御プロトコル・オーバＩＰ（ＴＣＰ／ＩＰ）接続シーケンス又は、ユーザ・データグラム・プロトコル（ＵＤＰ）オーバＩＰ（ＵＤＰ／ＩＰ）接続シーケンスであることを特徴とするロジック。
【請求項１２】
請求項１記載のロジックであって、該ノード・クラスタが：
３次元のトーラスを備えるトポロジによってお互いに結合される複数のノード；
を備えることを特徴とするロジック。
【請求項１３】
請求項１記載のロジックであって、該ノード・クラスタにおけるノードが：
２つのスイッチに結合される中央処理装置（ＣＰＵ）であることを特徴とするロジック。
【請求項１４】
高性能計算（ＨＰＣ）システムにおけるオン・デマンド・インスタンシエーションの方法であって：
第１ポート番号と第１ホスト名とを規定するクライアントからの接続要求を受信する工程；
を備え；
該第１ポート番号と該第１ホスト名は、ノード・クラスタを備えるＨＰＣサーバに対して外部に共用宣言され；
更に、該第１ポート番号と該第１ホスト名とに相当する該ＨＰＣサーバでのサービスを識別する工程；
該識別サービスが利用可能か否かを判定する工程；及び
該識別サービスが利用可能な場合、該クラスタにおける１つ又は複数のノードでの該識別サービスを備えるホストをインスタンス化する工程；
を備えることを特徴とする方法。
【請求項１５】
請求項１４記載の方法であって、該接続要求が：
伝送制御プロトコル（ＴＣＰ）接続要求又はユーザ・データグラム・プロトコル（ＵＤＰ）接続要求であることを特徴とする方法。
【請求項１６】
請求項１４記載の方法であって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセスする工程；
を備え；
該複数のエントリの各々が：
サービス；及び
該サービスに相当する該ＨＰＣサーバに対して外部に共用宣言される、ポート番号とホスト名；
を規定し；
更に、該第１ポート番号と該第１ホスト名とに相当する該ＨＰＣサーバでの該サービスを、該ＨＰＣサーバでの該サービス・リストによって識別する工程；
を備えることを特徴とする方法。
【請求項１７】
請求項１４記載の方法であって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセスする工程；
を備え；
該複数のエントリの各々が：
サービス；及び
該クラスタにおける１つ又は複数のノードで実行される場合に、該サービスを備えるホストに相当する該ＨＰＣサーバの内部にある、ポート番号とホスト名；
を規定し；
更に、該クラスタにおける１つ又は複数のノードでの該識別サービスを備える該ホストを、該ＨＰＣサーバでの該サービス・リストによってインスタンス化する工程；
を備えることを特徴とする方法。
【請求項１８】
請求項１４記載の方法であって、更に：
複数のエントリを備える、該ＨＰＣサーバでのサービス・リストをアクセス工程；
を備え；
該複数のエントリの各々が、サービスと、該サービスが利用可能か否かを示す１つ又は複数の規則を規定し；
更に、該識別サービスが利用可能か否かを、該サービス・リストによって判定する工程；
を備えることを特徴とする方法。
【請求項１９】
請求項１８記載の方法であって、該規則は：
該サービスが利用可能か否かを、該クライアントからの該接続要求に関連した時間に基づいて示すことを特徴とする方法。
【請求項２０】
請求項１４記載の方法であって、更に：
該識別サービスが利用不能である場合、該第１ポート番号に相当する該ＨＰＣサーバ上のポートをブロック化して、該識別サービスを該クライアントがアクセスすることを妨げる工程；
を備えることを特徴とする方法。
【請求項２１】
請求項１４記載の方法であって、更に：
該クラスタにおける１つ又は複数のノードで該識別サービスを備える該ホストに相当する該ＨＰＣサーバで、ブート画像、ファイル・システム、及びオペレーティング・システム（ＯＳ）構成をアクセス工程；及び
該ブート画像、該ファイル・システム及び該ＯＳ構成ファイルを用いて、該クラスタにおける１つ又は複数のノードで該識別サービスを備える該ホストをインスタンス化する工程；
を備えることを特徴とする方法。
【請求項２２】
請求項１４記載の方法であって、該識別サービスが：
ウェブ・サーバであることを特徴とする方法。
【請求項２３】
請求項１４記載の方法であって、更に：
該クラスタにおける１つ又は複数のノードでの該識別サービスを備える該ホストのアドレスをスプーフィングし、該ホストのために、該ホストがブートしている間に接続シーケンスを開始する工程；
を備えることを特徴とする方法。
【請求項２４】
請求項１４記載の方法であって：
該アドレスが、インターネット・プロトコル・オーバ媒体アクセス制御（ＩＰ／ＭＡＣ）アドレスであり；かつ
該接続要求が、伝送制御プロトコル・オーバＩＰ（ＴＣＰ／ＩＰ）接続シーケンス又は、ユーザ・データグラム・プロトコル（ＵＤＰ）オーバＩＰ（ＵＤＰ／ＩＰ）接続シーケンスであることを特徴とする方法。
【請求項２５】
請求項１４記載の方法であって、該ノード・クラスタが：
３次元のトーラスを備えるトポロジによってお互いに結合される複数のノード；
を備えることを特徴とする方法。
【請求項２６】
請求項１４記載の方法であって、該ノード・クラスタにおけるノードが：
２つのスイッチに結合される中央処理装置（ＣＰＵ）であることを特徴とする方法。
【請求項２７】
高性能計算（ＨＰＣ）システムにおけるオン・デマンド・インスタンシエーションのシステムであって：
第１ポート番号と第１ホスト名とを規定するクライアントからの接続要求を受信する手段；
を備え；
該第１ポート番号と該第１ホスト名は、ノード・クラスタを備えるＨＰＣサーバに対して外部に共用宣言され；
更に、該第１ポート番号と該第１ホスト名とに相当する該ＨＰＣサーバでのサービスを識別する手段；
該識別サービスが利用可能か否かを判定する手段；及び
該識別サービスが利用可能な場合、該クラスタにおける１つ又は複数のノードでの該識別サービスを備えるホストをインスタンス化する手段；
を備えることを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的に、データ処理に関し、特に、ＨＰＣシステムにおけるオン・デマンド・インスタンシエーションに関する。
【背景技術】
【０００２】
高性能計算（ＨＰＣ）は多くの場合、複雑な物理的現象又はアルゴリズム現象をモデリングし、シミュレーションし、解析する科学者及び技術者によって用いられる計算システムによって特徴付けられる。現在、ＨＰＣマシンは通常、ノードと呼ばれる数多くの、１つ又は複数のプロセッサから成るＨＰＣクラスタを用いて設計されている。大部分の大規模の科学アプリケーション及び工学アプリケーションについては、性能は、個々のノードの速度ではなく、個々のノードの並列スケーラビリティによって主に判定される。したがって、スケーラビリティは多くの場合、そのような高性能クラスタを構築するか購入するうえでの制約要因である。スケーラビリティは通常、ｉ）ハードウェア、ｉｉ）メモリ帯域幅、Ｉ／Ｏ帯域幅、並びに通信帯域幅、ｉｉｉ）ソフトウェア、ｉｖ）アーキテクチャ、及びｖ）アプリケーションに基づいたものとみなされる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
大部分の通常のＨＰＣの環境における処理帯域幅、メモリ帯域幅、及びＩ／Ｏ帯域幅は通常、うまくバランスがとれておらず、したがって、うまくスケーリングされていない。多くのＨＰＣ環境は、ハイエンドのデータ処理要件を満たすＩ／Ｏ帯域幅を有していないか、インストールされている不必要な構成部分が多すぎるブレードによって構築されており、このことはシステムの信頼度を劇的に低減する傾向にある。よって、多くのＨＰＣ環境は、生産指向環境における効率的な処理を行ううえでの頑健なクラスタ管理ソフトウェアを備えない場合がある。
【課題を解決するための手段】
【０００４】
本発明は、ＨＰＣシステムに関連した欠点と問題との何れか又は両方を削減するか除去する場合がある。
【０００５】
一実施例では、高性能計算（ＨＰＣ）システムにおけるオン・デマンド・インスタンシエーションの方法は、ノード・クラスタを含むＨＰＣサーバに対して外部に共用宣言される第１ポート番号と第１ホスト名とを規定するクライアントからの接続要求を受信する工程、第１ポート番号と第１ホスト名とに相当するＨＰＣサーバでのサービスを識別する工程、識別サービスが利用可能であるか否かを判定する工程、及びクラスタにおける１つ又は複数のノードでの識別サービスを備えるホストを、識別サービスが利用可能な場合、インスタンス化する工程を備える。
【０００６】
本発明の実施例は１つ又は複数の技術上の効果を備え得る。例として、特定の実施例は、ＨＰＣサーバでのサービスをクライアントが要求することを可能にし得る。特定の実施例では、サービスにアクセスするうえでの１つ又は複数の基準を、サービスをアクセスする旨のクライアントからの要求が満たす場合にのみ、ＨＰＣサーバでのサービスがクライアントに利用可能である。特定の実施例は、仮想クラスタにおけるホストの高利用可能性を備える。特定の実施例は、インターネット・サービス要求を動的に監視し、要求サービスを備えるホストに対してそのような要求をマッピングし、そのホストをインスタンス化する。本発明の特定の実施例は、上記の技術上の効果の全部又は一部を備えるか、上記の技術上の効果を何ら備えるものでない。特定の実施例は、１つ又は複数の別の技術上の効果を備える場合があり、その１つ又は複数は、添付図面、明細書、及び特許請求の範囲から当業者に容易に明らかとなり得る。
【発明を実施するための最良の形態】
【０００７】
本発明の特定の実施例は、１つ又は複数の技術上の効果を備え得る。例として、特定の実施例は、ＨＰＣシステムで実行するジョブをスケジューリングすることに通常関連する時間要件を軽減し得る。特定の実施例は、ＨＰＣシステムで実行するジョブをスケジューリングすることに通常関連する計算量上の要件を軽減し得る。本発明の特定の実施例は、上記の技術上の効果の全部又は一部を備えるか、上記の技術上の効果を何ら備えない。特定の実施例は、その１つ又は複数が添付図面、明細書、及び特許請求の範囲から当業者に容易に明らかであり得る、その１つ又は複数の別の、技術上の効果を備える場合がある。
【０００８】
本願開示及びその特徴並びに効果がより徹底的に分かるよう、次に、下記明細書を添付図面とともに参照する。
【実施例】
【０００９】
図１は、ソフトウェアのアプリケーション及び処理、例えば、大気シミュレーション、気象シミュレーションや衝撃シミュレーションを、ＨＰＣ手法を用いて実行する高性能計算（ＨＰＣ）システム１００を示す構成図である。システム１００は、処理性能にかなり同様なＩ／Ｏ性能を備えている、種々の計算ノード１１５の間で動的に割り当てられるＨＰＣ機能をユーザに備える。一般的に、これらのノード１１５は、とりわけ、この、入出力（Ｉ／Ｏ）性能の増加とファブリック・レーテンシの低減が理由で容易にスケーリング可能である。例えば、分散アークテクチャにおけるノード１１５のスケーラビリティは：
Ｓ（Ｎ）＝１／（（ＦＰ／Ｎ）＋ＦＳ）＊（１−Ｆｃ＊（１−ＲＲ／Ｌ）；
である、アムダールの法則の派生形によって表す場合があり、Ｓ（Ｎ）＝Ｎプロセッサでの高速化であり、Ｆｐ＝並列コードの割合であり、Ｆｓ＝非並列コードの割合であり、Ｆｃ＝通信に充てられる処理の割合であり、ＲＲ／Ｌ＝遠隔メモリ帯域幅の局所メモリ帯域幅に対する比率である。したがって、ＨＰＣシステム１００が、処理性能にかなり等しいか、かなり近づいているＩ／Ｏ性能を備えることによって、ＨＰＣシステム１００はＨＰＣアプリケーションの全体効率を向上させ、システム管理の容易化を可能にする。
【００１０】
ＨＰＣシステム１００は、（科学者や技術者などの）ユーザがジョブ１５０を投入してＨＰＣサーバ１０２上で処理することを可能にする分散クライアント／サーバ・システムである。例えば、システム１００は、１つ又は複数の管理ワークステーション又は局所クライアント１２０にネットワーク１０６を介して接続されるＨＰＣサーバ１０２を含み得る。しかし、スタンドアロン型計算環境又は何れかの別の適切な環境であり得る。要約すれば、システム１００は、スケーラビリティの高いノード１１５を含み、かつ、ユーザが、ジョブ１５０を投入し、スケーラブルなノード１５０をジョブ１５０に動的に割り当て、割り当てられたノード１１５を用いてジョブ１５０を自動的に実行することを可能にする何れかのＨＰＣ計算環境である。ジョブ１５０は、ＨＰＣ手法を用いて処理され、何れかの適切なユーザによって投入されるよう処理可能な何れかのバッチ・ジョブ又はオンライン・ジョブであり得る。例えば、ジョブ１５０は、シミュレーション、モデル、又は何れかの別の高性能要件に対する要求であり得る。ジョブ１５０は、クラスタ化データベース、オンライン・トランザクション処理システム、又はクラスタ化アプリケーション・サーバなどのデータ・センター・アプリケーションを実行する要求である場合もある。本明細書及び特許請求の範囲の原文記載の「ｄｙｎａｍｉｃａｌｌｙ」の語は一般的に、特定の処理が少なくとも部分的には実行時に１つ又は複数の変数に基づいて判定されるということを表す。本明細書及び特許請求の範囲の原文記載の「ａｕｔｏｍａｔｉｃａｌｌｙ」の語は一般的に、適切な処理がＨＰＣシステム１００の少なくとも部分によって実質的に行われるということを表す。この「ａｕｔｏｍａｔｉｃａｌｌｙ」の語が更に、何れかの適切なユーザ又は管理者による、システム１００との相互作用を、本願の開示の範囲から逸脱することなく想定しているということが分かるものである。
【００１１】
ＨＰＣサーバ１０２は、複数の、バランスされたノード１１５及びクラスタ管理ノード１３０を用いてジョブ１５０を処理するよう動作可能な何れかの、局所コンピュータ又は遠隔コンピュータを備える。一般的に、ＨＰＣサーバ１０２は、ブレード・サーバ又は別の分散サーバなどの分散コンピュータを備える。サーバ１０２は、その構成がどんなものであっても、複数のノード１１５を含む。ノード１１５は、例えば、ブレード、汎用パーソナル・コンピュータ（ＰＣ）、マッキントッシュ、ワークステーション、ユニックス（Ｕｎｉｘ）ベースのコンピュータ、又は何れかの別の適切な装置などの何れかのコンピュータ装置又は処理装置を備える。一般的に、図１は、本願の開示とともに用い得るコンピュータの一例に過ぎないものを備える。例えば、図１は本願開示とともに用い得る一サーバ１０２を示すが、システム１００は、サーバ以外のコンピュータや、サーバ・プールを用いて実施することが可能である。すなわち、本願の開示は、汎用コンピュータ以外のコンピュータや、通常のオペレーティング・システムなしのコンピュータを想定している。本明細書及び特許請求の範囲の原文において用いているように、「ｃｏｍｐｕｔｅｒ」の語は、パーソナル・コンピュータ、ワークステーション、ネットワーク・コンピュータ、又は何れかの別の適切な処理装置に及ぶことが意図されている。ＨＰＣサーバ１０２又はコンポーネント・ノード１１５は、リナックス（Ｌｉｎｕｘ）、ユニックス（Ｕｎｉｘ）、ウィンドウズ（登録商標）・サーバ、又は何れかの別の適切なオペレーティング・システムを含む何れかのオペレーティング・システムを実行するよう形成し得る。一実施例によれば、ＨＰＣサーバ１０２は、遠隔ウェブ・サーバを含んでいてもよく、遠隔ウェブ・サーバに通信可能に結合されていてもよい。したがって、サーバ１０２は、ノード１１５を動的に割り当ててＨＰＣジョブ１５０を処理するのに適した何れかの組み合わせでソフトウェア及び／ハードウェアを備えている何れかのコンピュータを備え得る。
【００１２】
概略を述べれば、ＨＰＣサーバ１０２は、管理ノード１０５、複数のノード１１５を備えるグリッド１１０、及びクラスタ管理エンジン１３０を含む。特に、サーバ１０２は、ｉ）デュアル・プロセッサと、ｉｉ）大容量の、高帯域幅のメモリと、ｉｉｉ）デュアル・ホスト・チャネル・アダプタ（ＨＣＡ）と、ｉｖ）統合ファブリック・スイッチングと、ｖ）ＦＰＧＡサポートと、ｖｉ）冗長な電源入力すなわちＮ＋１の電源との構成部分の一部又は全部を備えている複数のブレード（ノード１１５）を含む標準の１９インチのラックであり得る。これらの種々の構成部分によって、障害がノード・レベルに限定されることが可能になる。しかし、ＨＰＣサーバ１０２及びノード１１５がこれらの構成部分を全部含まない場合があるということが分かるものである。
【００１３】
管理ノード１０５は実質的に専ら、管理者を管理するか支援する少なくとも１つのブレードを備える。例えば、管理ノード１０５は２つのブレードを備える場合があり、２つのブレードのうちの１つは（アクティブ構成／パッシブ構成などの）冗長性を有する。一実施例では、管理ノード１０５は、ＨＰＣノード１１５と同じ種類のブレード又は計算装置であり得る。しかし、管理ノード１０５は、少なくとも部分的にグリッド１１０を管理するよう動作可能な状態にとどまっている限り、何れかの数の回路を含み、何れかの適切な方法で構成される何れかのノードであり得る。多くの場合、管理ノード１０５は、グリッド１１０に併せて表している複数のＨＰＣノード１１５から物理的又は論理的に分離されている。図示する実施例では、管理ノード１０５は、グリッド１１０にリンク１０８を介して通信可能に結合し得る。リンク１０８は、何れかの適切な通信プロトコルを実施する何れかの通信管路を備え得る。一実施例では、リンク１０８は管理ノード１０５とグリッド１１０との間の、ギガビット又は１０ギガビットのイーサネット（登録商標）通信を備える。
【００１４】
グリッド１１０は、処理能力を向上させるよう相互接続されるノード群１１５である。グリッドは、通常、３次元トーラスであるが、本願の開示の範囲から逸脱することなく、メッシュ、超立方体、又は何れかの別の形状若しくは構成であり得る。グリッド１１０におけるノード１１５間のリンクは、例えばファイバ又は銅などの、電気信号又は電磁気信号を伝達することが可能な、直列又は並列の、アナログ・リンク、ディジタル・リンク、又は何れかの別の種類のリンクを備え得る。各ノード１１５は統合スイッチによって構成される。このことによって、ノード１１５が３次元トーラスの基本的な構成体により容易になることを可能にし、別のノード１１５間のＸＹＺ距離を最小にすることに寄与する。更に、このことは、最大でギガビット・レベルの速度での大容量システムで銅線を機能させる場合があり、一部の実施例では、最長のケーブルは５メートル未満である。要約すれば、ノード１１５は、一般的に、最短距離の通信とＩ／Ｏ帯域幅の増加とに最適化される。
【００１５】
各ノード１１５は、クラスタ管理エンジン１３０と通信可能に結合されるクラスタ・エージェント１３２を含み得る。一般的には、エージェント１３２は要求又はコマンドを管理ノード１０５及び／又はクラスタ管理エンジン１３０から受信する。エージェント１３２は、ノード１１５の物理ステータスを判定し、処理データを「ハートビート」などによって管理ノード１０５に通信するよう動作可能な何れかのハードウェア、ソフトウェア、ファームウェア、又はそれらの組み合わせを含み得る。別の実施例では、管理ノード１０５は、エージェント１３２を周期的にポーリングして関連ノード１１５のステータスを判定し得る。エージェント１３２は、クラスタ管理エンジン１３０の少なくとも部分と互換である状態のままである限り、例えば、Ｃ、Ｃ＋＋、アセンブラ、ジャバ（Ｊａｖａ）、ビジュアル・ベーシック（Ｖｉｓｕａｌ  Ｂａｓｉｃ）及び他の言語又はそれらの組み合わせなどの何れかの適切なコンピュータ言語で書かれる場合がある、すなわち記述される場合がある。
【００１６】
クラスタ管理エンジン１３０は、ノード１１５を動的に、割り当て、管理し、ノード１１５を用いてジョブ１５０を実行するよう動作可能な、何れかのハードウェア、ソフトウェア、ファームウェア、又はそれらの組み合わせを含み得る。例えば、クラスタ管理エンジン１３０は、Ｃ、Ｃ＋＋、ジャバ、ビジュアル・ベーシック、アセンブラ、４ＧＬの何れかの適切なバージョン、及びその他の言語又はそれらの何れかの組み合わせにおいて作成すなわち記述される場合がある。クラスタ管理エンジン１３０を図１に単一のマルチタスク・モジュールとして示しているが、このエンジンによって行われる特徴と機能は、（図７に更に詳細に表すように）例えば、物理層モジュール、仮想層モジュール、ジョブ・スケジューラ、及びプレゼンテーション・エンジンなどの、複数のモジュールによって行い得る。更に、管理ノード１０５の外部に示すが、管理ノード１０５は通常、クラスタ管理エンジン１３０と関連する１つ又は複数の処理を実行し、クラスタ管理エンジン１３０を記憶させ得る。更に、クラスタ管理エンジン１３０は、本願の開示の範囲から逸脱することなく、別のソフトウェア・モジュールの子モジュールすなわちサブモジュールであり得る。したがって、クラスタ管理エンジン１３０は、ノード１１５とジョブ１５０とをインテリジェントに管理するよう動作可能な１つ又は複数のソフトウェア・モジュールを備える。特定の実施例では、クラスタ管理エンジンは、以下に説明するように、ジョブ１５０にノード１１５を割り当てるスケジューラ５１５を含む。スケジューラ５１５は、以下に更に説明するように、ジョブ１５０にノード１１５を割り当てるスケジューリング・アルゴリズムを用い得る。
【００１７】
サーバ１０２は、クライアント・サーバ環境又は別の分散環境においてネットワーク１０６を介してクライアント１２０などの別のコンピュータ・システムと通信するインタフェース１０４を含み得る。特定の実施例では、サーバ１０２はジョブ１５０又はジョブ・ポリシーをネットワーク１０６から受信してディスク・ファーム１４０に記憶させる。ディスク・ファーム１４０は、ノードを相互接続するものと同じ広帯域インタフェースを用いて計算アレイに直接接続される場合もある。一般的には、インタフェース１０４は、適切な組み合わせにおける、ネットワーク１０６と通信するよう動作可能な、ソフトウェア及び／又はハードウェアにコード化される論理を備える。特に、インタフェース１０４は、物理的信号を通信するよう動作可能な通信ネットワーク１０６又はハードウェアに関連した１つ又は複数の通信プロトコルをサポートするソフトウェアを備え得る。
【００１８】
ネットワーク１０６は、コンピュータ・サーバ１０２と、クライアント１２０などの何れかの別のコンピュータとの間の無線通信又は有線通信を容易にする。実際に、サーバ１０２とクライアント１２０との間に存在するものとして図示しているが、ネットワーク１０６は、本願の開示の範囲から逸脱することなく、種々のノード１１５間に存在する場合もある。すなわち、ネットワーク１０６は、種々の計算構成部分間での通信を容易にするよう動作可能な何れかのネットワーク又はサブネットワークに及ぶ。ネットワーク１０６は、例えば、インターネット・プロトコル（ＩＰ）パケット、フレーム・リレイ・フレーム、非同期転送モード（ＡＴＭ）・セル、音声、データ、及び別の適切な情報をネットワーク・アドレス間で通信し得る。ネットワーク１０６は、１つ又は複数の場所での、１つ又は複数の、ローカル・エリア・ネットワーク（ＬＡＮ）、無線アクセス・ネットワーク（ＲＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネットとして知られるグローバル・コンピュータ・ネットワークの全部若しくは一部、及び／又はいずれかの別の通信システムを含み得る。
【００１９】
一般的には、ディスク・ファーム１４０は、ジョブ１５０、プロファイル、ブート画像、又は別のＨＰＣ情報を記憶させる何れかのメモリ、データベース又はストレージ・エリア・ネットワーク（ＳＡＮ）である。図示する実施例によれば、ディスク・ファーム１４０は、１つ又は複数のストレージ・クライアント１４２を含む。ディスク・ファーム１４０は、いくつかの通信プロトコル、例えば、インフィニバンド（ＩｎｆｉｎｉＢａｎｄ）（ＩＢ）、ギガビット（Ｇｉｇａｂｉｔ）・イーサネット（Ｅｔｈｅｒｎｅｔ）  （登録商標）（ＧＥ）、又はファイバチャネル（ＦｉｂｒｅＣｈａｎｎｅｌ）（ＦＣ）
のうちの何れかによってデータ・パケットを処理し、ルーティングする場合がある。データ・パケットは通常、ディスク・ファーム１４０内のデータを伝送するのに用いられる。データ・パケットは、発信元識別子と宛て先識別子とを有するヘッダを含み得る。発信元識別子、例えば、発信元アドレスは情報の発信元を識別し、宛て先識別子、例えば宛て先アドレスは情報の受信先を識別する。
【００２０】
クライアント１２０は、ジョブ投入画面又はアドミニストレーション（管理）画面がユーザにグラフィカル・ユーザ・インタフェース（ＧＵＩ）１２６を介して提示されるよう動作可能な何れかの装置である。概略を述べれば、図示するクライアント１２０は、少なくともＧＵＩ１２６を含み、システム１００に関連した何れかの適切なデータを受信し、送信し、処理し、記憶するよう動作可能な電子計算機装置を備える。通信可能にサーバ１０２に結合される何れかの数のクライアント１２０が存在する場合があるということが分かるものである。更に、「ｃｌｉｅｎｔ  １２０」及び「ｕｓｅｒ  ｏｆ  ｃｌｉｅｎｔ  １２０」は、本願の開示の範囲から逸脱することなく、適宜、同義で用い得る。更に、図示を容易にするよう、各クライアントは１つのユーザによって用いられるという点で表している。しかし、多くのユーザが１つのコンピュータを用いて、ジョブ１５０を同じＧＵＩ１２６を用いて通信し得る。
【００２１】
本願の開示に記載のように、クライアント１２０は、パーソナル・コンピュータ、タッチ画面端末、ワークステーション、ネットワーク・コンピュータ、キオスク、無線データ・ポート、携帯電話、携帯情報端末（ＰＤＡ）、これら若しくは別の装置の内部の１つか複数のプロセッサ、又は何れかの別の適切な処理装置に及ぶことが意図されている。例えば、クライアント１２０は、情報を受け入れることが可能な、キーパッド、タッチ画面、マウス、又は別の装置などの入力装置、ディジタル・データ、視覚情報を含む、サーバ１０２若しくはクライアント１２０の処理に関連した情報を伝える出力装置、又はＧＵＩ１２６を含むコンピュータを備え得る。入力装置も出力装置も、磁気コンピュータ・ディスクなどの固定記憶媒体又は取り外し可能記憶媒体、ＣＤ−ＲＯＭ、又は別の適切な媒体を含んで、アドミニストレーション画面及びジョブ投入画面、すなわちＧＵＩ１２６を介してクライアント１２０のユーザからの入力を受信し、出力をそのユーザに備え得る。
【００２２】
ＧＵＩ１２６は、ｉ）クライアント１２０のユーザがシステム１００とインタフェースをとって１つ又は複数のジョブ１５０を投入する工程；及び／又はｉｉ）システム管理者（又はネットワーク管理者）がクライアント１２０を用いて、何れかの適切な監視目的でシステム１００とインタフェースをとる工程；を可能にするよう動作可能なグラフィカル・ユーザ・インタフェースを備える。一般的に、ＧＵＩ１２６は、ＨＰＣシステム１００によって備えられるデータの効率的でかつユーザ・フレンドリな提示をクライアント１２０のユーザに備える。ＧＵＩ１２６は、ユーザによって操作される双方向フィールド、プルダウン・リスト、及びボタンを有する複数のカスタム化可能なフレームすなわち表示を備え得る。一実施例では、ＧＵＩ１２６は、種々のジョブ・パラメータ・フィールドを表示し、クライアント１２０のユーザからのコマンドを入力装置のうちの１つを介して受信するジョブ投入ディスプレイ（表示）を表示させる。代替的に、又は組み合わせによって、ＧＵＩ１２６は、ノード１１５の物理ステータス及び論理ステータスを図６Ａ乃至６Ｂに示すようにシステム管理者に提示し、種々のコマンドを管理者から受信する場合がある。管理者コマンドは、ノードを利用可能（不能）なものとして印しを付けるコマンド、保守するようノードをシャットダウンさせるコマンド、ノードを再ブートするコマンド、又は何れかの別の適切なコマンドを含み得る。更に、グラフィカル・ユーザ・インタフェース（ｇｒａｐｈｉｃａｌ  ｕｓｅｒ  ｉｎｔｅｒｆａｃｅ）の語を単数形か複数形で用いて、１つ又は複数のグラフィカル・ユーザ・インタフェースと、特定のグラフィカル・ユーザ・インタフェースの表示の各々を表し得るということが分かるものである。したがって、ＧＵＩ１２６は、情報をシステム１００において処理し、結果をユーザに効率的に提示する、一般的なウェブ・ブラウザなどの何れかのグラフィカル・ユーザ・インタフェースを想定している。サーバ１０２は、クライアント１２０からのデータをウェブ・ブラウザ（例えば、マイクロソフト（Ｍｉｃｒｏｓｏｆｔ）社のインターネット・エクスプローラ（Ｉｎｔｅｒｎｅｔ  Ｅｘｐｌｏｒｅｒ）又はネットスケープ（Ｎｅｔｓｃａｐｅ）社のナビゲータ（Ｎａｖｉｇａｔｏｒ））を介して受け入れ、適切なＨＴＭＬ応答又はＸＭＬ応答をネットワーク１０６を用いて戻すことが可能である。
【００２３】
処理の一特徴では、ＨＰＣサーバ１０２はまず、初期化すなわちブートされる。この処理中に、クラスタ管理エンジン１３０は、グリッド１１０におけるノード１１５の存在、状態、位置、及び／又は別の特性を判定する。上記のように、このことは、各ノードが初期化されるか、管理ノード１０５によってほぼ即時にポーリングされると、通信される「ハートビート」に基づく場合がある。次に、クラスタ管理エンジン１３０は、グリッド１１０の種々の部分を１つ又は複数の仮想クラスタ２２０に、例えば、所定のポリシーに基づいて動的に割り当て得る。一実施例では、クラスタ管理エンジン１３０は、考えられる障害についてノード１１５を継続して監視し、ノード１１５のうちの１つに障害が起こったということを判定すると、種々の回復手法のうちの何れかを用いて障害を効果的に管理する。クラスタ管理エンジン１３０が一意の実行環境を仮想クラスタ２２０の割り当てノード毎に管理し、備える場合もある。実行環境は、ホスト名、ＩＰアドレス、オペレーティング・システム、構成サービス、局所ファイル・システム並びに共有ファイル・システム、及びインストールされているアプリケーション群並びにデータ群を含み得る。クラスタ管理エンジン１３０は、関連ポリシーによって、かつ優先度などのクラスタ間ポリシーによってノードを仮想クラスタ２２０から動的に加算するか減算する場合がある。
【００２４】
ユーザは、クライアント１２０にログオンする場合、ＧＵＩ１２６を介してジョブ投入画面が提示される場合がある。ユーザがジョブ・パラメータを入力し、ジョブ１５０を投入すると、クラスタ管理エンジン１３０はジョブ投入、関連パラメータ、及び、ジョブ１５０、ユーザ又はユーザ群と関連した何れかの所定のポリシーを処理する。クラスタ管理エンジン１３０は更に、適切な仮想クラスタ２２０を、少なくとも部分的にはこの情報に基づいて判定する。エンジン１３０は更に、ジョブ空間２３０を仮想クラスタ２２０内に割り当て、ジョブ１５０を割り当てノード１１５にわたってＨＰＣ手法を用いて実行する。少なくとも部分的にはこの向上されたＩ／Ｏ性能に基づいて、ＨＰＣサーバ１０２はジョブ１５０の処理をよりすばやく完了し得る。完了すると、クラスタ管理エンジンは結果１６０をユーザに通信する。
【００２５】
図２はノード（又はブレード）１１５の例を示す。ノード１１５は、１つ又は複数のジョブ１５０の、スレッド又は処理などの全部又は一部を処理するよう、何れかの向きでの何れかの計算装置を含む。制約ではなく例として、ノード１１５は、ゼオン（ＸＥＯＮ）マザーボード、オプテロン（ＯＰＴＥＲＯＮ）マザーボード、又は別の計算装置を含み得る。ノード１１５は、グリッド１１０におけるノード１１５にわたってスイッチング機能を分散させることを可能にする統合ファブリックを備えるアーキテクチャを有する。特定の実施例では、グリッド１１０におけるノード１１５にわたってそのような機能を分散させることはグリッド１１０における集中スイッチングを妨げる場合があり、そのことは同様に、グリッド１１０におけるフォールト・トレランスを向上させ、グリッド１１０におけるノード１１５間の並列通信を可能にする。
【００２６】
ノード１１５は、２つのＣＰＵ１６４と、スイッチ（又はファブリック）１６６を含む。ノード１１５への言及は、適宜、２つのＣＰＵ１６４と、スイッチ１６６とに及び得る。ノード１１５への言及は、適宜、ＣＰＵ１６４のみに及び得る。スイッチ１６６は、統合スイッチであり得る。特定の実施例では、スイッチ１６６は２４個のポートを有する。スイッチ１６６上の２つのポートは、ノード１１５との間の入出力を行うよう、ノード１１５を管理ノード１０５に結合し得る。更に、グリッド１１０における３次元メッシュ、３次元トーラス、又は別のトポロジの実施を容易にするよう、スイッチ１６６上の２つのポートは各々、グリッド１１０のｘ軸に沿ってノード１１５を別のノード１１５に結合する場合があり、スイッチ１６６上の２つのポートは各々、グリッド１１０のｙ軸に沿ってノード１１５を別のノード１１５に結合する場合があり、スイッチ１６６上の２つのポートは各々、グリッド１１０のｚ軸に沿ってノード１１５を別のノード１１５に結合する場合がある。更に、スイッチ１６６上の別のポートはノード１１５を別のノード１１５にグリッド１１０において結合して、グリッド１１０における（４次元トーラス又は４つ以上の次元を含む別の非伝統的なトポロジなどの）多次元トポロジの実施を容易にする場合がある。特定の実施例では、スイッチ１６６上の１つ又は複数のポートは、ノード１１５を１つ又は複数の別のノード１１５にグリッド１１０の１つ又は複数の対角線軸に沿って結合する場合があり、そのことは、ノード１１５と、ノード１１５から比較的遠いところにある１つ又は複数の別のノード１１５との間の通信ジャンプ又は通信ホップを削減し得る。制約ではなく例として、スイッチ１６６上のポートは、ノード１１５からいくつかの３次元ジュンプ離れたところにある、グリッド１１０の北東軸に沿って存在する別のノード１５５に結合し得る。特定の実施例では、スイッチ１６６はインフィニバンド（ＩｎｆｉｎｉＢａｎｄ）・スイッチである。特定のスイッチ１６６を図示し、説明したが、本発明は何れかの適切なスイッチ１６６を想定している。
【００２７】
リンク１６８ａはＣＰＵ１６４ａをスイッチ１６６に結合する。リンク１６８ｂはＣＰＵ１６４ａを以下に説明するように、別のノード１１５における別のスイッチ１６６に結合する。リンク１６８ｃはＣＰＵ１６４ｂをスイッチ１６６に結合する。リンク１６８ｄはＣＰＵ１６４ｂを、以下に説明するように別のスイッチ１６６に結合する。リンク１６８ｅと１６８ｆは、スイッチ１６６を、以下に更に説明するように、別のノード１１５における２つの別のＣＰＵ１６４に結合する。特定の実施例では、リンク１６８は、各方向に毎秒約１ギガバイトを通信することができるインフィニバンド４Ｘリンクを含む。特定のリンク１６８を示し、説明したが、本発明は何れかの適切なリンク１６８を想定している。リンク１７０は、ノード１１５へのＩ／Ｏリンクである。リンク１７０は、各方向に毎秒約１ギガバイトを通信することができるインフィニバンド４Ｘリンクを含む。特定のリンク１７０を示し、説明したが、本発明は何れかの適切なリンク１７０を想定している。リンク１７２は、スイッチ１６６を、以下に説明するように、別のノード１１５における別のスイッチ１６６にスイッチ１６６を結合する。特定の実施例では、リンク１７２は、各方向に毎秒約３ギガバイトを通信することができるインフィニバンド１２Ｘリンクを含む。特定のリンク１７２を示し、説明したが、本発明は何れかの適切なリンク１７２を想定している。
【００２８】
図３は、ノード１１５におけるＣＰＵ１６４の例を示す。ＣＰＵ  １６４の例を示し、説明したが、本発明は何れかの適切なＣＰＵ１６４を想定している。ＣＰＵ１６４は、プロセッサ１７４、メモリ・コントローラ・ハブ（ＭＣＨ）１７６、メモリ装置１７８、及びホスト・チャネル・アダプタ（ＨＣＡ）１８０を含む。プロセッサ１７４は、ハードウェア構成部分、ソフトウェア構成部分、組み込み論理構成部分又は２つ以上のそのような構成部分の組み合わせを含む。特定の実施例では、プロセッサ１７４は、インテル（ＩＮＴＥＬ）社によるＮＯＣＯＮＡ（ノコナ）ＸＥＯＮ（ゼオン）プロセッサ１７４である。特定の実施例では、プロセッサ１７４は、約１メガバイトのキャッシュを有し、毎秒約７．２ギガフロップが可能な約３．６ギガヘルツのプロセッサである。特定の実施例では、プロセッサ１７４は、ハイパスレッディングを備える。特定の実施例では、プロセッサ１７４は、メモリ帯域幅の効率的な利用を備えるメモリ・コントローラを含む。特定のプロセッサ１７４を示し、表したが、本発明は何れかの適切なプロセッサ１７４を想定している。
【００２９】
バス１８２はプロセッサ１７４とＭＣＨ１７６とをお互いに結合する。特定の実施例では、バス１８２は、毎秒約６．４ギガバイトを通信することができる約８００ＭＨｚのフロント・サイド・バス（ＦＳＢ）である。特定のバス１８２を示し、説明したが、本発明は何れかの適切なバス１８２を想定している。ＭＣＨ１７６は、プロセッサ１７４と、メモリ装置１７８などの、ＨＰＣシステム１００の１つ又は複数の別の構成部分との間の通信を容易にする、ハードウェア構成部分、ソフトウェア構成部分、若しくは組み込み論理構成部分、又は２つ以上のそのような構成部分の組み合わせを含む。特定の実施例では、ＭＣＨ１７６は、プロセッサ１７４と、メモリ装置１７８、バス１８２、レベル２（Ｌ２）キャッシュ及び、ＣＰＵ１６４の１つ又は複数の別の構成部分のうちの１つ又は複数のものとの間の通信を制御するＣＰＵ１６４用のノースブリッジである。特定の実施例では、ＭＣＨ１７６は、リンデンハースト（ＬＩＮＤＥＮＨＵＲＳＴ）Ｅ７５２０ＭＣＨ１７６である。特定の実施例では、メモリ装置１７８はＭＣＨ１７６に別個に結合される２つのダブル・データ・レート（ＤＤＲ）のメモリ装置を含む。制約ではなく例として、メモリ装置１７８は、その各々が、チャネル毎に毎秒約３．２ギガバイトが可能なその２つのＤＤＲ２−４００メモリを含み得る。特定のメモリ装置１７８を示し、説明したが、本発明は何れかの適切なメモリ装置１７８を想定している。
【００３０】
特定の実施例では、リンクは、プロセッサ１７４と、ＩＣＨに結合される基本Ｉ／Ｏシステム（ＢＩＯＳ）と、ＩＣＨに結合される、ギガビット（Ｇｉｇａｂｉｔ）・イーサネット（Ｅｔｈｅｒｎｅｔ）（登録商標）（ＧｂＥ）コントローラ又は別のイーサネット（Ｅｔｈｅｒｎｅｔ）（登録商標）・インタフェースとの何れか又は両方などの、ＨＰＣシステム１００の１つ又は複数の別の構成部分との間のＩ／Ｏを容易にする１つ又は複数のハードウェア構成部分、ソフトウェア構成部分、又は組み込み論理構成部分を含むＩ／Ｏコントローラ・ハブ（ＩＣＨ）にＭＣＨ１７６を結合する。特定の実施例では、ＩＣＨは、ＣＰＵ１６４のＩ／Ｏ機能を制御するＣＰＵ１６４用のサウスブリッジである。ＩＣＨに結合されるイーサネット（登録商標）・インタフェースは、ＩＣＨと、イーサネット（登録商標）・インタフェースに結合されるベースボード管理コントローラ（ＢＭＣ）との間の通信を容易にし得る。特定の実施例では、ＨＰＣシステム１００の管理ノード１０５又は別の構成部分は、１つ又は複数のそのようなＢＭＣを含む。特定の実施例では、リンクはイーサネット（登録商標）・インタフェースをスイッチに結合し、それによって１つ又は複数のＧｂＥ管理ポートへのアクセスを備える。
【００３１】
バス１８４は、ＭＣＨ１７６とＨＣＡ１８０とをお互いに結合する。特定の実施例では、バス１８４は、毎秒約４ギガバイトを通信することが可能なＰＣＩ−Ｅｘｐｒｅｓｓ（エクスプレス）８Ｘバス１８４などの、端末構成部分相互接続（ＰＣＩ）バス１８４である。特定のバス１８４を図示し、説明したが、本発明は何れかの適切なバス１８４を想定している。ＨＣＡ１８０は、ＣＰＵ１６４にチャネル・ベースのＩ／Ｏを備える、ハードウェア構成部分、ソフトウェア構成部分、若しくは組み込み論理構成部分、又は２つ以上のそのような構成部分の組み合わせを含む。特定の実施例では、ＨＣＡ１８０はメラノックス（ＭＥＬＬＡＮＯＸ）社のインフィニバンドＨＣＡ１８０である。特定の実施例では、ＨＣＡ１８０は、ノード１１５におけるスイッチ１６６に対して処理構成要素（ＰＥ）毎に約１．８５ギガバイトを可能にし、基本Ｉ／Ｏシステム（ＢＩＯＳ）、イーサネット（登録商標）・インタフェース又は別のＩ／ＯなどのＩ／ＯにＰＥ毎に対して約８００メガバイトを可能にする場合がある、毎秒約２．６５ギガバイトの帯域幅を備える。特定の実施例では、ＨＣＡ１８０は、スイッチ１６６での帯域幅が毎秒約３．７ギガバイトに達して、ピーク時で毎秒約１３．６ギガフロップとなることと、スイッチ１６６でのＩ／Ｏ速度がギガフロップ毎約５０メガバイトに達してフロップ毎約０．２７バイトとなることとの何れか又は両方を可能にする。特定のＨＣＡ１８０を示し、説明したが、本発明は何れかの適切なＨＣＡ１８０を想定している。各リンク１６８は、ＨＣＡ１８０をスイッチ１６６に結合する。リンク１６８ａは、以下に説明するように、ＨＣＡ１８０に対して１次のスイッチ１６６である第１スイッチ１６６にＨＣＡ１８０を結合する。特定の実施例では、ＨＣＡ１８０を含むノード１１５は、第１スイッチ１６６を含む。リンク１６８ｂは、以下に説明するように、ＨＣＡ１８０に対して２次のスイッチである第２スイッチ１６６にＨＣＡ１８０を結合する。特定の実施例では、ＨＣＡ１８０を含まないノード１１５は、以下に説明するように、第２スイッチ１６６を含む。
【００３２】
図４は、２つのスイッチ１６６と４つのプロセッサ１７４とを含むノード対１８６の例を示す。ノード対１８６におけるスイッチ１６６は、お互いに対して冗長であり、そのことはノード対１８６でのフォールト・トレランスを向上させ得る。ノード対１８６における第１スイッチ１６６が適切に機能していない場合、ノード対１８６における第２スイッチ１６６がノード対１８６における４つのＣＰＵ全てにスイッチングを備え得る。ノード対１８６では、スイッチ１６６ａは、ＣＰＵ１６４ａと１６４ｂとに対しては１次スイッチ１６６であり、ＣＰＵ１６４ｃと１６４ｄとに対しては２次スイッチ１６６である。スイッチ１６６ｂは、ＣＰＵ１６４ｃと１６４ｄとに対して１次スイッチ１６６であり、ＣＰＵ１６４ａと１６４ｂとに対して２次スイッチ１６６である。両方のスイッチ１６６ａと１６６ｂが適切に機能している場合、スイッチ１６６ａはＣＰＵ１６４ａと１６４ｂとにスイッチングを備える場合があり、スイッチ１６６ｂはＣＰＵ１６４ｃと１６４ｄとにスイッチングを備え得る。スイッチ１６６ａが適切に機能しているが、スイッチ１６６ｂが適切に機能していない場合、スイッチ１６６ａは、ＣＰＵ１６４ａ、１６４ｂ、１６４ｃ及び１６４ｄにスイッチングを備え得る。スイッチ１６６ｂが適切に機能しているが、スイッチ１６６ａが適切に機能していない場合、スイッチ１６６ｂがＣＰＵ１６４ａ、１６４ｂ、１６４ｃ、及び１６４ｄにスイッチングを備え得る。
【００３３】
リンク１７２は、グリッド１１０におけるノード対１８６の外部の６つのノード１１５にノード対１８６における各ノード１１５を結合する。制約ではなく例として、スイッチ１６６ａでのリンク１７２ａは、グリッド１１０におけるノード１１５ａのノース（北）方向にあるノード対１８６の外部の第１ノード１１５にノード１１５ａを結合し、スイッチ１６６ａでのリンク１７２ｂは、グリッド１１０におけるノード１１５ａのサウス（南）方向にあるノード対１８６の外部の第２ノード１１５にノード１１５ａを結合し、スイッチ１６６ａでのリンク１７２ｃは、グリッド１１０におけるノード１１５ａのイースト（東）方向にあるノード対１８６の外部の第３ノード１１５にノード１１５ａを結合し、スイッチ１６６ａでのリンク１７２ｄは、グリッド１１０におけるノード１１５ａのウエスト（西）方向にあるノード対１８６の外部の第４ノード１１５にノード１１５ａを結合し、スイッチ１６６ａでのリンク１７２ｅは、グリッド１１０におけるノード１１５ａの上にあるノード対１８６の外部の第５ノード１１５にノード１１５ａを結合し、スイッチ１６６ａでのリンク１７２ｆは、グリッド１１０におけるノード１１５ａの下にあるノード対１８６の外部の第６ノード１１５にノード１１５ａを結合する。特定の実施例では、リンク１７２は、お互いに異なるノード対１８６の外部のノード１１５群にノード対１８６におけるノード１１５ａ及び１１５ｂを結合する。制約ではなく例として、スイッチ１６６ａでのリンク１７２は、ノード対１８６の外部の第１ノード１１５、ノード対１８６の外部の第２ノード１１５、ノード対１８６の外部の第３ノード１１５、ノード対１８６の外部の第４ノード１１５、ノード対１８６の外部の第５ノード１１５、及びノード対１８６の外部の第６ノード１１５を含む、ノード対１８６の外部の、第１の６つのノード１１５の群をノード１１５ａに結合し得る。スイッチ１６６ｂでのリンク１７２は、ノード対１８６の外部の第７ノード１１５、ノード対１８６の外部の第８ノード１１５、ノード対１８６の外部の第９ノード１１５、ノード対１８６の外部の第１０ノード１１５、ノード対１８６の外部の第１１ノード１１５、及びノード対１８６の外部の第１２ノード１１５を含む、ノード対１８６の外部の、第２の６つのノード１１５の群をノード１１５ｂに結合し得る。
【００３４】
特定の実施例では、リンク１７２は、第１端の反対側の、グリッド１１０の第２端に隣接する第２ノード１１５にグリッド１１０の第１端に隣接する第１ノード１１５を結合し得る。制約ではなく例として、グリッド１１０の左端に隣接する第１ノード１１５と、グリッド１１０の左端の反対側にある、グリッド１１０の右端に隣接する第２ノード１１５を検討する。リンク１７２は、グリッド１１０における、第２ノード１１５の位置に対する第１ノード１１５の位置にもかかわらず、第１ノード１１５が第２ノード１１５のイースト方向にあり、第２ノード１１５が第１ノード１１５のウエスト方向にあるように、第１ノード１１５と第２ノード１１５とをお互いに結合し得る。別の例として、グリッド１１０の前端に隣接する第１ノード１１５と、グリッド１１０の前端の反対側にある、グリッド１１０の後端に隣接する第２ノード１１５を検討する。リンク１７２は、グリッド１１０における、第２ノード１１５の位置に対する第１ノード１１５の位置にもかかわらず、第１ノード１１５が第２ノード１１５のサウス方向にあり、第２ノード１１５が第１ノード１１５のノース方向にあるように、第１ノード１１５と第２ノード１１５とをお互いに結合し得る。更に別の例として、グリッド１１０の上端に隣接する第１ノード１１５と、グリッド１１０の上端の反対側にある、グリッド１１０の下端に隣接する第２ノード１１５を検討する。リンク１７２は、グリッド１１０における、第２ノード１１５の位置に対する第１ノード１１５の位置にもかかわらず、第１ノード１１５が第２ノード１１５の下にあり、第２ノード１１５が第１ノード１１５の上にあるように、第１ノード１１５と第２ノード１１５とをお互いに結合し得る。
【００３５】
図５Ａ乃至図５Ｄは、システム１００におけるグリッド１１０とその利用又はトポロジの種々の実施例を示す。図５Ａは、複数のノード種類を用いたグリッド１１０の一構成、すなわち３次元トーラスを示す。例えば、図示するノード種類は外部Ｉ／Ｏノード、ファイル・システム（ＦＳ）サーバ、ＦＳメタデータ・サーバ、データベース・サーバ、及び計算ノードである。図５Ｂは、グリッド１１０の「フォールディング（畳むこと）」の例を示す。フォールディングは一般的に、グリッド１１０の１つの物理的な先端が、相当する軸方向の先端と接続し、それによってより頑健なトポロジすなわちエッジレス・トポロジを備えることを可能にする。この実施例では、ノード１１５は、ラップアラウンドされて、ノード・ライン２１６によるほぼシームレスなトポロジ接続を備える。ノード・ライン２１６は、２つ以上のノード１１５を相互接続する何れかの通信プロトコルを実施する何れかの適切なハードウェアであり得る。例えば、ノード・ライン２１６はギガビット・イーサネット（登録商標）を実施する銅線ケーブル又は光ファイバ・ケーブルであり得る。特定の実施例では、上記のように、ノード・ライン２１６は、１つ又は複数のリンク１７２を含む。
【００３６】
図５Ｃは、そのグリッド１１０内に割り当てられる１つの仮想クラスタ２２０を備えているそのグリッド１１０を示す。１つの仮想クラスタ２２０しか示していないが、本願の開示の範囲から逸脱することなく、グリッド１１０における仮想クラスタ２２０の（ゼロを含む）何れかの数であり得る。仮想クラスタ２２０は、関連ジョブ１５０を処理する論理的なノード群１１５である。例えば、仮想クラスタ２２０は、同様なジョブ１５０を投入すると思われる、１つの研究グループ、部署、研究所、又は何れかの別のユーザ群と関連し得る。仮想クラスタ２２０は、何れかの形状であり得るものであり、グリッド１１０内に何れかの数のノード１１５を含み得る。実際に、図示する仮想クラスタ２２０が複数の物理的に隣接しているノード１１５を含んでいるが、クラスタ２２０は、ジョブ１５０を処理するよう動作可能な論理的に関連したノード１１５の分散クラスタであり得る。
【００３７】
仮想クラスタ２２０は、何れかの適切な時点で割り当て得る。例えば、クラスタ２２０は、システム１００が初期化されると、例えば起動パラメータに基づいて割り当ててもよく、例えば、変動する、サーバ１０２のニーズに基づいて動的に割り当ててもよい。更に、仮想クラスタ２２０は経時的にその形状とサイズとを変えて、変動するリクエスト、デマンド、及び状況にすばやく対応し得る。例えば、仮想クラスタ２２０は、動的に変動させて、先行時点ではクラスタ２２０の部分であった第２ノード１１５の障害に応じて自動的に割り当てられる第１ノード１１５を含み得る。特定の実施例では、クラスタ２２０は、ノード１１５を処理の要求に応じて共有し得る。特定の実施例では、スケジューラ５１５が、以下に説明するように、スケジューリング・アルゴリズムによって１つ又は複数のジョブ１５０に１つ又は複数の仮想クラスタ２２０を割り当て得る。
【００３８】
図５Ｄは、仮想クラスタ２２０例の内部に割り当てられる種々のジョブ空間２３０ａ及び２３０ｂ各々を示す。一般的には、ジョブ空間２３０は、受信ジョブ１５０を完了するよう動的に割り当てられる仮想クラスタ２２０内のノード１１５の群である。通常、実行ジョブ１５０毎に１つのジョブ空間２３０が存在し、逆もあてはまるが、本願の開示の範囲から逸脱することなく、ジョブ空間２３０はノード１１５を共有し得る。ジョブ空間２３０のディメンションは、ユーザ又は管理者によって手作業で入力してもよく、ジョブ・パラメータ、ポリシー、及び／又は何れかの別の適切な特性に基づいて動的に判定してもよい。特定の実施例では、スケジューラ５１５は、以下に説明するように、スケジューリング・アルゴリズムによってジョブ空間２３０の１つ又は複数のディメンションを判定し得る。
【００３９】
図６Ａ及び図６Ｂは、システム１００による、管理グラフィカル・ユーザ・インタフェース４００の種々の実施例を示す。多くの場合、管理ＧＵＩ４００は、クライアント１２０にＧＵＩ１２６を用いて提示される。一般的に、管理ＧＵＩ４００は、種々の管理用対話画面若しくは管理用対話ディスプレイをシステム管理者に提示するもの及び／又は種々のジョブ投入画面若しくはジョブ・プロファイル画面をユーザに提示するものである。これらの画面又はディスプレイは、種々の収集情報表示に組み立てられるグラフィカル構成要素から成る。例えば、ＧＵＩ４００は、（図６Ａに示す）グリッド１１０の物理的状態の表示、又は（図６Ｂに示す）グリッド１１０におけるノード１１５の論理的な、割り当てすなわちトポロジの表示を提示し得る。
【００４０】
図６Ａは例示的ディスプレイ４００ａを示す。ディスプレイ４００ａは、ノード１１５を効果的に管理するよう、管理者に提示される情報を含み得る。例示的実施例は、グリッド１１０の論理的な、「ピクチャ」すなわちスクリーンショットを備えている標準的なウェブ・ブラウザを含む。例えば、このピクチャはグリッド１１０と構成ノード１１５との物理的な状態を備え得る。各ノード１１５が何れかの数の色のうちの１つであり、各色が種々の状態を表す場合がある。例えば、障害ノード１１５が赤色であり、利用ノード又は割り当てノード１１５が黒色であり、非割り当てノード１１５がシェード・カラーである場合がある。更に、ディスプレイ４００ａは、管理者が、ノード１１５のうちの１つの上にポインタを移動させ、その種々の物理的属性を視ることを可能にし得る。例えば、管理者には、「ノード」、「利用可能性」、「プロセッサ利用率」、「メモリ利用率」、「温度」、「物理位置」、及び「アドレス」を含む情報が備えられる場合がある。当然、これらは例示的なデータ・フィールドに過ぎず、何れかの適切な物理ノード情報又は論理ノード情報が管理者用ディスプレイであり得る。ディスプレイ４００ａは、管理者が、グリッド１１０の表示を回転させるか何れかの別の適切な関数を行うことを可能にする場合もある。
【００４１】
図６Ｂは例示的なディスプレイ４００ｂを示す。ディスプレイ４００ｂは、グリッド１００の論理的な状態の表示すなわちピクチャを提示する。図示する実施例は、グリッド１１０内に割り当てられる仮想クラスタ２２０を提示する。ディスプレイ４００ｂは更に、１つ又は複数のジョブ１５０を実行するよう、クラスタ２２０内に割り当てられる２つの例示的なジョブ空間２３０を表示する。ディスプレイ４００ｂは、管理者に、（割り当て又は非割り当てなどの）種々の状態によってグループ化されるノード１１５の数を視るよう、ポインタをグラフィカル仮想クラスタ２２０上に移動させることを可能にし得る。更に、管理者は、適切なジョブ情報が提示されるようにジョブ空間２３０のうちの１つの上にポインタを移動させ得る。例えば、管理者は、ジョブ名、開始時間、ノード数、推定終了時間、プロセッサ利用度、Ｉ／Ｏ利用度他を視ることができる場合がある。
【００４２】
（例示的ディスプレイ４００ａ及び４００ｂ各々によって上記に表す）管理ＧＵＩ１２６が例示的な目的のためのものにすぎず、図示するグラフィカル構成要素、更には図示しない別の管理構成要素を何ら含まない場合があり、それらの構成要素の一部又は全部を含む場合もあるということが分かるものである。
【００４３】
図７は、システム１００による、クラスタ管理エンジン１３０の一実施例を示す。この実施例では、クラスタ管理エンジン１３０は、複数のサブモジュール又は構成部分、すなわち、物理マネージャ５０５、仮想マネージャ５１０、ジョブ・スケジューラ５１５、及び局所のメモリ又は変数５２０を含む。
【００４４】
物理マネージャ５０５は、種々のノード１１５の物理的状態を判定し、この判定状態に基づいて効果的にノード１１５を管理するよう動作可能な何れかのソフトウェア、論理、ファームウェア、又は別のモジュールである。物理マネージャはこのデータを用いて、ノード１１５の障害を効率的に判定し、この障害に効率的に応答する場合がある。一実施例では、物理マネージャ５０５は複数のエージェント１３２に通信可能に結合され、各エージェントは１つのノード１１５上に存在する。上記のように、エージェント１３２は、少なくとも物理情報を収集し、マネージャ５０５に通信する。物理マネージャ５０５は更に、クライアント１２０のある場所にいるシステム管理者に警告を、ネットワーク１０６を介して通信するよう動作される。
【００４５】
仮想マネージャ５１０は、仮想クラスタ２２０と、ノード１１５の論理的状態とを管理するよう動作可能な何れかのソフトウェア、論理、ファームウェア、又は別のモジュールである。一般的に、仮想マネージャ５１０は、ノード１１５の論理的表現をノード１１５の物理的状態とリンクする。これらのリンクに基づいて、仮想マネージャ５１０は、ノード障害又は、ＨＰＣ処理を増加させる（システム若しくはユーザの）要求に応じる場合などに、仮想クラスタを生成し、これらのクラスタ２２０に対する種々の変更を処理し得る。仮想マネージャ５１０は、非割り当てノード１１５などの仮想クラスタ２２０の状態をスケジューラ５１５に通信して、非実行状態又は待ち行列に入っている状態の、ＨＰＣ処理及びＨＰＣジョブ１５０の動的バックフィルを可能にする場合もある。仮想マネージャ５１０は更に、ジョブ１５０の特定ノード１１５との互換性を判定し、この情報をスケジューラ５１５に通信する場合がる。特定の実施例では、仮想マネージャ５１０は、個々の仮想クラスタ２２０を表すオブジェクトであり得る。
【００４６】
特定の実施例では、クラスタ管理エンジン１３０は、スケジューラ５１５を含む。スケジューラ５１５は、スケジューリング・アルゴリズムによってジョブ１５０にノード１１５を割り当てる、ハードウェア構成部分、ソフトウェア構成部分、若しくは組み込み論理構成部分又は、１つか複数のそのような構成部分を含む。特定の実施例では、スケジューラ５１５はプラグインである。特定の実施例では、クラスタ管理エンジン１５０がジョブ１５０を受信することに応じて、クラスタ管理エンジン１３０は、ジョブ１５０に１つ又は複数のノード５１５を割り当てるようスケジューラ５１５をコールする。特定の実施例では、ジョブ１５０に１つ又は複数のノード５１５を割り当てるよう、クラスタ管理エンジン１３０がスケジューラ５１５をコールすると、クラスタ管理エンジン１３０は、ジョブ１５０に割り当てるのに利用可能な、グリッド１１０におけるノード１１５をスケジューラ５１５に対して識別する。制約ではなく例として、クラスタ管理エンジン１３０が、ジョブ１５０に１つ又は複数のノード１１５を割り当てるようスケジューラ５１５をコールすると、クラスタ管理エンジン１３０は、ジョブ１５０への割り当てに利用可能な、グリッド１１０におけるノード１１５の全てのリストをスケジューラ５１５に通信し得る。特定の実施例では、クラスタ管理エンジン１３０は、ジョブ１５０に対する割り当てに利用可能なノード１１５の数がジョブ１５０に要求されるノード１１５の数以上である場合にのみ、ジョブ１５０に１つ又は複数のノード１１５を割り当てるよう、スケジューラ５１５をコールする。
【００４７】
上記のように、特定の実施例では、グリッド１１０は、その各々が４つのＣＰＵ１６４に結合されるその３次元の、スイッチ１６６のトーラスである。スケジューラ５１５は、グリッド１１０を、ノード１１５のトーラスとして論理的に構成する。サイズが〔ｘ，ｙ，ｚ〕の、スイッチ１６６のトーラスは、〔４ｘ，ｙ，ｚ〕、〔ｘ，４ｙ，ｚ〕、〔ｘ，ｙ，４ｚ〕、〔２ｘ，２ｙ，ｚ〕、〔２ｘ，ｙ，２ｚ〕、及び〔ｘ，２ｙ，２ｚ〕の６つの考えられる論理的な構成を備える。スケジューラ５１５が、ジョブ１５０に１つ又は複数のノード１１５を割り当てる場合、スケジューラ５１５はジョブ１５０に最も適した論理的な構成を選択し得る。
【００４８】
メッセージ・パッシング・インタフェース（ＭＰＩ）は、ジョブ１５０における処理間の通信の標準である。特定の実施例では、スケジューラ５１５はジョブ１５０に割り当てられる各ノード１１５にＭＰＩランクを割り当てる。Ｎ個の処理を含むジョブ１５０について、スケジューラ１５０は各処理に０とＮ−１との間の一意の整数のランクを割り当てる。ジョブ１５０における第１処理にメッセージを通信するよう、ジョブ１５０における第２処理は、第１処理のランクを規定し得る。同様に、ジョブ１５０における第１処理からメッセージを受信するよう、ジョブ１５０における第２処理は、第１処理のランクを規定し得る。同様に、ジョブ１５０における第１処理からメッセージを受信するよう、ジョブ１５０における第２処理は第１処理のランクを規定し得る。スケジューラ１５０は、その各々がその各々のブロードキャスト・グループにおける処理からその各々のブロードキャスト・グループにおける全ての別の処理までのメッセージの通信を容易にする、その１つ又は複数のブロードキャスト・グループを規定する場合もある。ブロードキャスト・グループにおける第１処理からメッセージを受信するよう、ブロードキャスト・グループにおける第２処理はブロードキャスト・グループを規定し得る。
【００４９】
特定の実施例では、スケジューラ５１５は、「ｓｐａｔｉａｌ」と「ｃｏｍｐａｃｔ」と「ａｎｙ」との３つの種類の要求を処理する。「ｒｅｑｕｅｓｔ」への言及は、適宜、ジョブ１５０に及び、適宜、その逆もあてはまる。ユーザがジョブ１５０をＨＰＣサーバ１０２に投入すると、ユーザは要求の種類を規定し得る。「ｓｐａｔｉａｌ」の要求は、空間的に記述されるジョブ１５０に及ぶ。既存のＭＰＩアプリケーションのうちの１つのクラスは、ジョブ１５０における処理間の空間的な関係を呈する。例として、気象モデルがある。気象モデルを含むジョブ１５０を処理するよう、ＨＰＣサーバ１０２は、緯度経度（又は同様な座標システム）に及ぶ２次元グリッドを用いて、地球の表面を分割し、時間を離散的な時間ステップに分割する場合がある。ジョブ１５０の各処理は特定の領域の気象をモデル化する。各時間ステップの始めに、処理は、処理に隣接する４つの別の処理の各々と境界値を交換し、更に、特定の領域の気象を計算する。気象モデルを含むジョブ１５０を処理するよう、ＨＰＣサーバ１０２は、２次元のグリッドではなく、緯度経度と高度（又は同様な座標システム）に及ぶ３次元のグリッドを用いて地球の表面を分割し得る。
【００５０】
ジョブ１５０における処理間で空間的な関係を呈するＭＰＩアプリケーションについて、ユーザはジョブ１５０にノード１１５のトリプレット
【００５１】
【数１】
2006146865.tif 000003
を要求し得る。次元Ｓの全てが１よりも大きい場合、要求は３次元の要求である。次元Ｓのうちの１つが１に等しい場合、要求は２次元の要求である。次元Ｓのうちの２つが１に等しい場合、要求は１次元の要求である。要求をノード１１５に割り当てるよう、スケジューラ１５０は空間的な座標をＭＰＩランクに：
【００５２】
【数２】
2006146865.tif 000004
としてマッピングし得る。Ｓｘ、Ｓｙ、及びＳｚは要求のサイズを示し、ｘはゼロとＳｘとの間であり、ｙはゼロとＳｙとの間であり、ｚはゼロとＳｚとの間である。ノード１１５を２次元の要求に割り当てるよう、スケジューラ１５０は、空間座標をＭＰＩランクに：
【００５３】
【数３】
2006146865.tif 000005
としてマッピングし得る。特定の実施例では、空間座標をＭＰＩランクにマッピングするよう、スケジューラ５１５はまず、グリッド１１０のｚ軸に沿って増加させ、次にグリッド１１０のｙ軸に沿って増加させ、更にグリッド１１０のｘ軸に沿って増加させる。スケジューラ５１５がＭＰＩランクに空間座標をマッピングすることに関して正しくない前提、例えば、まず、グリッド１１０のｘ軸に沿って増加させ、次にグリッド１１０のｙ軸に沿って増加させ、更にグリッド１１０のｚ軸に沿って増加させるという前提に対処するよう、クラスタ管理エンジン３０は要求ジョブ１５０を、例えば、
【００５４】
【数４】
2006146865.tif 000006
としてスケジューラ５１５に提示し得る。
【００５５】
「ｃｏｍｐａｃｔ」要求は、空間的に記述されていないジョブ１５０に及ぶ。スケジューラ５１５は、コンパクト要求に割り当てられる、ノード１１５の対の各々の間の最大通信距離（又は最大ホップ・カウント）を最小にするよう、ノード１１５をコンパクト要求に割り当て得る。「ａｎｙ」要求は、処理間通信をほとんど必要としないか全く必要としないジョブ１５０に及ぶ。スケジューラ１５０は何れかのノード１１５の群を割り当てて何れかの要求を満たし得る。そのようなジョブ１５０は、グリッド１１０における断片化から生じるホールを充填する機会をスケジューラ１５０に備える。
【００５６】
ユーザは、ジョブ１５０をＨＰＣサーバ１０２に投入する場合、ジョブ１５０にアグレシブ・フラグを規定する場合もある。特定の実施例では、アグレシブ・フラグは、ノード１１５をジョブ１５０に割り当てる目的でスケジューラ５１５に割り当てられる自由度を示す、ゼロと１との間の浮動小数である。高い数は低い数よりも自由度をスケジューラ５１５に与える。ユーザが空間的な要求をＨＰＣサーバ１０２に投入し、空間的な要求上のアグレシブ・フラグをゼロに設定する場合、空間的な要求に対応するようノード１１５が利用可能である場合のみジョブ１５０をスケジューリングする。特定の実施例では、ユーザが空間的な要求をＨＰＣサーバ１０２に投入し、空間的な要求上のアグレシブ・フラグをゼロより大きな数に設定する場合、スケジューラ５１５は空間的な要求に対応しようとするが、スケジューラ５１５は、空間的な要求に対応することが可能でない場合、ジョブ１５０をコンパクトな要求としてスケジューリングする。特定の実施例では、コンパクトな要求は、コンパクトな要求に割り当てられるノード１１５の対の間のホップ・カウントが無限であることを可能にし得る。クラスタ管理エンジン１３０は、割り当てに利用可能なノード１１５の数が要求ノード１１５数以上である場合のみ、スケジューラ５１５をコールするので、スケジューラ１５０は、そのような要求に常に対応することが可能である。特定の実施例では、コンパクトな要求のアグレシブ・フラグは、コンパクトな要求に割り当てられるノード１１５の対の間のホップ・カウントに対する限界を示す。そのような実施例では、ホップ・カウントに対する限界は
【００５７】
【数５】
2006146865.tif 000007
に等しい場合があり、ａはアグレシブ・フラグである。
【００５８】
特定の実施例では、クラスタ管理エンジン１３０がスケジューラ５１５をコールして１つ又は複数のノード１１５をジョブ１５０に割り当てる場合、クラスタ管理エンジン１３０は：要求される、ノード１１５の数；要求種類；ジョブ１５０のサイズ；ジョブ１５０上のアグレシブ・フラグ；（スケジューラ５１５が後に調節してグリッド１１０のノード・ベースのサイズを判定する）グリッド１１０のスイッチ・ベースのサイズ；（特定の実施例では、４に等しい、）スイッチ１６６毎のノード１１５の数；ジョブ１５０への割り当てに利用可能なノード１１５の数；及び（例えば、ジョブ１５０への割り当てに利用可能なノード１１５全てのリストなどの）ジョブ１５０への割り当てに利用可能な１つ又は複数のノード１１５を識別するもの；の入力をスケジューラ５１５に備える。特定の実施例では、ＲｅｑｕｅｓｔｅｄＮｏｄｅｓは要求されるノード１１５の数を示し、ＲｅｑｕｅｓｔＴｙｐｅは要求種類を示し、（アレイを含む）ＲｅｑｕｅｓｔｅｄＳｉｚｅはジョブ１５０のサイズを示し、ＡｇｇｒｅｓｓｉｖｅＦｌａｇはジョブ１５０上のアグレシブ・フラグを示し、（アレイを含む）ＴｏｒｕｓＳｉｚｅはグリッド１１０のスイッチ・ベースのサイズを示し、ＮｏｄｅｓＰｅｒＳｗｉｔｃｈはスイッチ１６６毎のノード１１５の数を示し、ＮｕｍＦｒｅｅＮｏｄｅｓはジョブ１５０への割り当てに利用可能なノード１１５の数を示し、（アレイを含む）ＦｒｅｅＮｏｄｅＬｉｓｔはジョブ１５０への割り当てに利用可能な１つ又は複数のノード１１５を識別する。
【００５９】
特定の実施例では、スケジューラ５１５がジョブ１５０をスケジューリングする（かスケジューリングしようとする）場合、スケジューラ５１５は、（ジョブ１５０に割り当てられるノード１１５のリストなどの）ジョブ１５０に割り当てられるノード１１５を識別するもの；ジョブ１５０に割り当てられる各ノードのＭＰＩランク；及び（１）スケジューラ５１５がジョブ１５０をスケジューリングしたこと；（２）スケジューラ５１５はジョブ１５０をスケジューリングしなかったこと；又は（３）スケジューラ５１５がジョブ１５０をスケジューリングすることが全く可能でないということを示す戻り値；の出力を備える。
【００６０】
特定の実施例では、ノード１１５をジョブ１５０に割り当てるよう、スケジューラ５１５はまず、ジョブ１５０をスケジューリングするよう変数を初期化し、次に変数によってジョブ１５０をスケジューリングし、クラスタ管理エンジン１３０で処理するようスケジュール（又は結果）を変換する。ＳｐａｔｉａｌＡｌｌｏｗｅｄ、ＣｏｍｐａｃｔＡｌｌｏｗｅｄ、及びＡｎｙＡｌｌｏｗｅｄの３つの変数は、スケジューリングが可能な種類を示す。スケジューラ５１５は、ＳｐａｔｉａｌＡｌｌｏｗｅｄ、ＣｏｍｐａｃｔＡｌｌｏｗｅｄ、及びＡｎｙＡｌｌｏｗｅｄを初期化するよう以下のロジックの例を用い得る：
【００６１】
【表１】
2006146865.tif 000008
特定の実施例では、スケジューラ５１５は、グリッド１１０のより小さい次元の前にグリッド１１０のより大きな次元を示すよう、グリッド１１０のスイッチ・ベースのサイズを形成させる。（アレイを含む）ＴｏｒｕｓＭａｐは、グリッド１１０のより小さい次元の前にグリッド１１０のより大きな次元を示すよう、グリッド１１０のスイッチ・ベースのサイズを形成させたグリッド１１０のスイッチ・ベースのサイズを示す。スケジューラ５１５は、ＴｏｒｕｓＭａｐをＦｒｅｅＮｏｄｅＬｉｓｔに識別されているノード１１５の全てに適用する。（アレイを含む）ＩｎｖｅｒｓｅＴｏｒｕｓＭａｐはＴｏｒｕｓＭａｐの逆数であり、スケジューラ５１５はＩｎｖｅｒｓｅＴｏｒｕｓＭａｐを、処理するようクラスタ管理エンジン１３０にリストを戻す前にジョブ１５０に割り当てられるノード１１５のリストに適用する。制約ではなく例として、クラスタ管理エンジン１３０が１４×１６×１５のスイッチ・ベースのトーラス・サイズをスケジューラ５１５に通信する場合、スケジューラ５１５はＴｏｒｕｓＭａｐを｛２，０，１｝に設定する。その場合、スイッチ・ベースのトーラス・サイズは１６×１５×１４となり、｛ｘ，ｙ，ｚ｝の指数を有するＦｒｅｅＮｏｄｅＬｉｓｔにおけるノード１５５については、スケジューラ５１５がＴｏｒｕｓＭａｐを適用した後のノード１５５の指数は｛ｙ，ｚ，ｘ｝である。上記例のＩｎｖｅｒｓｅＴｏｒｕｓＭａｐは｛１，２，０｝である。
【００６２】
特定の実施例では、ＮｕｍＭａｐＤｉｍｅｎｓｉｏｎｓは、スイッチ・ベースのトーラスをノード・ベースのトーラスに変換する場合に修正する次元の数を示す。ＭａｐＤｉｍｓｉｏｎｓ［２］及びＭａｐＭｏｄ［２］は、修正する次元の指数と、修正する次元の各々の乗数を備える。スケジューラ５１５は、修正する次元のうちの１つを４で掛けてもよく、修正する次元のうちの２つの各々を２で掛けてもよい。スケジューラ５１５は、どちらの乗算を適用するかを判定し、次に、適宜、当初はスイッチによって記述された、トーラスのサイズを修正する。スケジューラ５１５は、ＲｅｑｕｅｓｔＴｙｐｅによって、どちらの乗算を適用するかを判定する。
【００６３】
特定の実施例では、スケジューラ５１５は要求を満たすメッシュのリストを生成する要求に１つ又は複数の座標変換を適用する。メッシュは、グリッド１１０に埋め込まれるボックスを含む。
【００６４】
【数６】
2006146865.tif 000009
の始点と
【００６５】
【数７】
2006146865.tif 000010
の終点がメッシュを規定する。メッシュは、１つ又は複数の次元における終点よりも大きな始点を有する場合、１つ又は複数の次元において「ラッピング」する。制約ではなく例として、［３，７，５］での始点と［２，９，４］での始点とを備えているメッシュはｘ次元とｙ次元でラッピングする。グリッド１１０における点［ｘ，ｙ，ｚ］は、
【００６６】
【数８】
2006146865.tif 000011
である場合、非ラッピング・メッシュに存在する。スケジューラ５１５が要求を満たすメッシュ・リストを生成した後、スケジューラ５１５は、要求への割り当てに利用可能なノード１５５の群に対してスケジューリング可能なメッシュをスケジューラ５１５が識別するまでスケジューラ５１５はリストをループする。一般的に、３次元の要求は、要求を満たす６つのメッシュをもたらす傾向にあり、２次元の要求は、要求を満たす数百のメッシュをもたらす傾向にあり、１次元の要求は、要求を満たす数十のメッシュをもたらす傾向にある。特定の実施例では、スケジューラ５１５は、要求を満たすメッシュ数を最大にするよう、２次元又は３次元の要求に対するノード・ベースのトーラスを設定する。
【００６７】
１次元の要求をスケジューリングする（か、１次元の要求に１つ又は複数のノード１１５を割り当てる）よう、変数を初期化するのに、スケジューラ５１５は、グリッド１１０におけるスイッチ１６６のｙ軸とｚ軸をノード１１５の２×２の構成に設定する。スケジューラ５１５は、グリッド１１０におけるスイッチ１６６のｚ軸が未使用の次元であるようにジョブ１５０をマッピングする。スケジューラ５１５は更に、ジョブ１５０をｚ軸に沿ってｙ軸にフォールディングする。したがって、特定の実施例では、１次元の要求には：
【００６８】
【表２】
2006146865.tif 000012
が適用され、［ｎ］は０から１−ｎまでの範囲の指数を有する１次元のアレイを適宜、示す。制約ではなく例として、ａ＝｛４，６，２｝は適宜、
【００６９】
【数９】
2006146865.tif 000013
に相当する。
【００７０】
特定の実施例では、スケジューラ５１５は、２次元の要求をスケジューリングするよう、グリッド１１０におけるスイッチ１６６のｙ軸とｚ軸とをノード１１５の２×２の構成に設定して変数を初期化する場合もある。特定の実施例では、スケジューラ５１５は、スケジューリングするよう、２次元要求を第３の、未使用の次元にフォールディングして、よりコンパクトな形状を生成する。多くのそのようなフォールディングが考えられる場合があるので、スケジューラ５１５はそのようなフォールディングの最大数をもたらす（ノード１１５の２×２の構成とは異なり得る）構成を選択し得る。スケジューラ５１５は、２次元の要求について考えられる６つの構成の各々を検査し、６つの考えられる構成毎に考えられるフォールディングの数を計算する場合がある。特定の実施例では、スケジューラ５１５は最大の考えられるフォールディング数を可能にする構成を選択する。特定の実施例では、２つの１×４の構成が互角の場合、スケジューラ５１５はまず、ｚ軸を修正する１×４の構成を選択し、次にｙ軸を修正する１×４の構成を選択する。特定の実施例では、１×４の構成と２×２の構成が互角の場合、スケジューラ５１５は２×２の構成を選択する。特定の実施例では、２つ以上の２×２の構成が互角の場合、スケジューラ５１５はまず、ｙ軸とｚと軸を修正する２×２の構成を選択し、次にｘ軸とｚ軸とを修正する２×２の構成を選択し、更に、ｘ軸とｙ軸とを修正する２×２の構成を選択する。特定の実施例では、３次元の要求が、フォールディングを可能にする代わりにお互いに対してその各々が一意のその６つの向き（又は回転）を可能にする以外は、２次元の要求をスケジューリングするよう、スケジューラ５１５が変数を初期化することになるので、スケジューラ５１５は３次元の要求をスケジューリングするよう変数を初期化する。
【００７１】
特定の実施例では、コンパクトな要求をスケジューリングするよう変数を初期化するのに、スケジューラ５１５は、コンパクトな要求のｚ軸を４で掛けて１×４の構成を生成する。１×４の構成を用いて、コンパクトな要求を処理することは、コンパクトな要求に割り当てられるスイッチ１６６に結合されるノード１１５の全てを用いることを容易にし、このことは同様に、グリッド１１０におけるスイッチ・ポイントでの断片化を削減する。特定の実施例では、スケジューラ５１５は同様に、何れかの要求をスケジューリングするよう変数を初期化する。
【００７２】
パーティションは、スケジューリングするのに利用可能な、グリッド１１０におけるノード１１５の全てを含む最小メッシュである。ＰａｒｔＳｔａｒｔ［３］はパーティションの始点座標を示し、ＰａｒｔＥｎｄ［３］はパーティションの終点座標を示し、ＰａｒｔＳｉｚｅ［３］  はパーティションのサイズを示し、ＰａｒｔＷｒａｐｓ［３］はパーティションがラッピングするか否かを示す。スケジューラ５１５は要求を満たすノード１１５をサーチする長さを削減するようパーティションを構成し得る。パーティションは、グリッド１１０よりもずっと小さい場合がある。ｉ＝０、１、及び２の場合、ＰａｒｔＳｔａｒｔ［ｉ］は、（アレイを含む）ＦｒｅｅＭｅｓｈにおいて考えられるｉの座標の全てのうちの最小の値を含む。ＰａｒｔＳｉｚｅ［ｉ］＝ＰａｒｔＥｎｄ［ｉ］−ＰａｒｔＳｔａｒｔ［ｉ］＋１である。ＰａｒｔＳｉｚｅ［ｉ］がＴｏｒｕｓＳｉｚｅ［ｉ］に等しい場合、ＰａｒｔＷｒａｐｓ［ｉ］はＴｒｕｅ（真）である。スケジューラ５１５は（アレイを含む）ＮｏｄｅＩｎＵｓｅをＦｒｅｅＭｅｓｈにおける全てのノードについてＮＯＤＥ＿ＮＯＴ＿ＩＮ＿ＵＳＥに設定し、他のノードの全てについてＮＯＤＥ＿ＩＮ＿ＵＳＥに設定する。
【００７３】
特定の実施例では、ＦｒｅｅＹ［ｉ，ｊ，ｋ］は、
【００７４】
【数１０】
2006146865.tif 000014
までの線｛ｉ，ｊ，ｋ｝に沿ったフリー・ノード１５５の数を含む。ＦｒｅｅＸ［ｉ，ｊ，ｋ］は、
【００７５】
【数１１】
2006146865.tif 000015
までの線｛ｉ，ｊ，ｋ｝に沿ったフリー・ノード１５５の数を含む。スケジューラ５１５は、ＦｒｅｅＹ［ｉ，ｊ，ｋ］とＦｒｅｅＸ［ｉ，ｊ，ｋ］とを用いて、以下に説明するようにスキャン・アルゴリズムを実行する。特定の実施例では、ＳｐａｔｉａｌＡｌｌｏｗｅｄ又はＣｏｍｐａｃｔＡｌｌｏｗｅｄがＴｒｕｅである場合のみ、ＦｒｅｅＹ［ｉ，ｊ，ｋ］と  ＦｒｅｅＸ［ｉ，ｊ，ｋ］とを構成する。
【００７６】
ＳｐａｔｉａｌＡｌｌｏｗｅｄがＴｒｕｅである場合、スケジューラ５１５は、要求をスケジューリングするよう種々の構造を試みる。
【００７７】
【数１２】
2006146865.tif 000016
の最大６つの一意の向きを有する。これらの６つの向きは、スケジューラ５１５がメッシュに適用し得る、４つの一意の９０°の回転と２つの一意の１８０°の回転とに相当する。いずれかの２つの次元がお互いに等しい場合、３つの一意の向きのみが利用可能である。スケジューラ５１５はメッシュをスケジューリングする場合、考えられる向きを全て考慮する。ジョブ１５０が２次元である、すなわちジョブ１５０の１つの次元が１に等しい場合、スケジューラ５１５は、ジョブ１５０の２つの、使用次元すなわち、ジョブ１５０の１より大きい次元、の何れかを、ジョブ１５０の未使用次元、すなわちジョブ１５０の１に等しい次元にアコーディオンに似たかたちでフォールディングして、よりコンパクトな３次元のメッシュを生成し得る。スケジューラ５１５がフォールディングの長さの整数の倍数でない次元をフォールディングする場合、最後のフォールディングは先行するフォールティングの全てよりも短くなり、それによって２次元のメッシュが３次元メッシュ上に連結されることになる。ジョブ１５０が１次元の場合、スケジューラ５１５はジョブ１５０を２つの未使用次元の何れかにフォールディングし得る。スケジューラ５１５は更に、２つの結果次元の何れかを残りの未使用次元にフォールディングし得る。メッシュの結果形状は、一般的に言えば、４つのメッシュを連結したものとなる。
【００７８】
図８は、ｙ次元にフォールディングされる１次元要求の例を示す。図８では、スケジューラ５１５は、２次元メッシュ｛１，２，４｝と、この２次元メッシュに連結される｛１，１，３｝を生成するよう、｛１，１，１１｝の１次元要求を４のフォールディング長を用いてｙ次元にフォールディングしている。スケジューラ５１５は第１フォールディングにゼロの番号を付し、第２フォールディングに１の番号を付し、第３の短いフォールディングに２の番号を付す場合がある。スケジューラ５１５がフォールディングに沿ったノード１１５にＭＰＩランクを割り当てる場合、ＭＰＩランクは、偶数番号のフォールディングに沿ってｚ値が増加するにつれ、かつ、奇数番号のフォールディングに沿ってｚ値が減少するにつれて増やされる。制約ではなく例として、［０，０］でのノード１１５のＭＰＩランクはゼロである場合があり、［０，１］でのノード１１５のＭＰＩランクは１である場合があり、［０，２］でのノード１１５のＭＰＩランクは２である場合があり、［０，３］でのノード１１５のＭＰＩランクは３である場合がある。［１，３］でのノード１１５のＭＰＩランクは４である場合があり、［１，２］でのノード１１５のＭＰＩランクは５である場合がある、などである。連結はｚ  ＝  ０で開始するが、これはフォールディングを偶数を有するからである。スケジューラ５１５が奇数の完全なフォールディングを用いて要求をフォールディングした場合、連結はむしろｚ  ＝  ３で開始し、ｘ  ＝  ０に向けて内側に進むことになる。特定の実施例では、スケジューラ５１５はアコーディオンに似たフォールディングのみを考慮する。別の種類のフォールディングも存在する。制約ではなく例として、フォールディングは階段形状を形成する場合がある。スケジューラ５１５は、１次元のジョブ１５０に対する特定のフォールディングを禁止する場合がある。上記のように、特定の実施例では、スケジューラ５１５は１次元のジョブ１５０を２度フォールディングする。第２フォールディングは、スケジューラ５１５が最初にフォールディングした次元をフォールディングするか、スケジューラ５１５がフォールディングした対象の最初の次元をフォールディングする。図８では、スケジューラ５１５は、ｚ次元をフォールディングしており、ｙ次元にフォールディングしている。スケジューラ５１５が最初にフォールディングした次元を第２フォールディングがフォールディングした場合、スケジューラ５１５は、最大３つの連結を生成し、メッシュの合計を４つとする場合がある。特定の実施例では、スケジューラ５１５は、２つの連結までしか可能にしない。その結果、スケジューラ５１５が１次元のジョブ１５０をスケジューリングする場合、第１フォールディングが連結をもたらさなかった場合でなければ、第２フォールディングは、スケジューラ５１５が最初にフォールディングした対象の次元をフォールディングすることに制限される。ジョブ１５０のサイズがフォールディング長の整数の倍数であれば、連結は何ら生じない。特定の実施例では、そのような制限によって、スケジューラ５１５が２つの連結までしか可能にしないものとなる。特定の実施例では、スケジューラ５１５は当初、要求を満たす、考えられるメッシュ全てを構成する。要求が１次元か２次元の場合、スケジューラ５１５は、考えられる、アコーディオンに似たフォールディングの各々と、そのようなフォールディング各々の、考えられる向きの各々を構成する。要求が３次元の場合、スケジューラ５１５は、要求の、考えられる向きの各々を構成する。特定の実施例では、スケジューラ５１５は、以下に説明するように、Ｔｒｙ  Ｓｔｒｕｃｔｕｒｅｓのリストを用いてそのような構成の各々を記録する。
【００７９】
ＣｏｍｐａｃｔＡｌｌｏｗｅｄがＴｒｕｅである場合、スケジューラ５１５は、要求される、ノード１１５の数を含むコンパクトなメッシュを構成する。スケジューラ５１５はメッシュを最善のフィットと指定し、メッシュを（アレイを含む）ＢｅｓｔＦｉｔに記憶する。制約ではなく例として、Ｎを、要求される、ノード１１５の数とし、Ｑを、Ｎの立方根を整数に丸めたものとする。スケジューラは当初、ＢｅｓｔＦｉｔを｛Ｑ，Ｑ，Ｑ｝に設定する。Ｎ＝Ｑ３の場合、スケジューラ５１５は終了する。さもなければ、スケジューラ５１５は、以下に説明するように、ＢｕｉｌｄＣｏｍｐａｃｔＦｉｔｓ関数によってＢｅｓｔＦｉｔの１つ又は複数の次元を増やすことになる。スケジューラ５１５は更に、ＢｅｓｔＦｉｔの次元以上でかつグリッド１１０の次元以下である次元を有するメッシュ全てを構成して、（アレイを含む）Ｆｉｔを用いてメッシュを記録する。
【００８０】
スケジューラ５１５は更に、望ましくないメッシュをＦｉｔから取り除く。上記のように、特定の実施例では、グリッド１１０は、その各々が４つのＣＰＵ１６４に結合されるそのスイッチ１６６の３次元トーラスである。スイッチ１６６毎に４つのＣＰＵ１６４を含むグリッド１１０を補正するよう、１次元における４倍又は２次元における２倍によってトーラスを修正する。スイッチ１６６での１つのＣＰＵ１６４が処理を実行する場合にスイッチ１６６でのＣＰＵ１６４の全てが処理を実行するようにスケジューラ５１５が要求を満たす可能性を増加させるよう、増倍率の整数の倍数である１つ又は複数の修正次元におけるサイズを有するメッシュのみを保持する。制約ではなく例として、スケジューラ５１５が、ｙ次元におけるスイッチ１６６のトーラスを２によって乗算し、ｚ次元におけるスイッチ１６６のトーラスを２によって乗算する場合、スケジューラ５１５は、偶数のｙ次元とｚ次元とを有するＦｉｔにおけるメッシュのみを保持することになる。
【００８１】
スケジューラ５１５は更に、残りのメッシュにおける最大ホップ・カウントによってＦｉｔにおける残りのメッシュをソートする。サイズが
【００８２】
【数１３】
2006146865.tif 000017
のメッシュにおける何れかの２つのノード間の最大距離は、
【００８３】
【数１４】
2006146865.tif 000018
である。２つのメッシュが、お互いに同一の最大ホップ・カウントを有する場合、スケジューラ５１５は、メッシュを別のメッシュの前に近づけて立方体になるようにする。制約ではなく例として、
【００８４】
【数１５】
2006146865.tif 000019
は同じ最大距離を有するが、スケジューラ５１５は、Ｍ２をＭ１の前に配置する。
【００８５】
スケジューラ５１５は、望ましくないメッシュをＦｉｔから取り除かなかった場合でも、少なくともＮ個のノード１１５を含むメッシュ全てを生成する訳ではないことになる。制約ではなく例として、Ｎが２７に等しいものであり、ＢｅｓｔＦｉｔが｛３，３，３｝に等しかった場合、Ｆｉｔはメッシュ｛１，１，２７｝を含むものでないことになる。｛１，１，２７｝のメッシュは合理的なメッシュ数をもたらさないことになり、要求を満たす少なくとも１つのメッシュを常にもたらすことになるが、これは、Ｆｉｔがグリッド１１０に等しいメッシュを含むことになり、Ｎがグリッド１１０におけるノード１１５の数以下である場合にのみクラスタ管理エンジン１３０がスケジューラ５１５をコールするからである。
【００８６】
ＡｎｙＡｌｌｏｗｅｄが真である場合、１つ又は複数のフリー・メッシュを構成するよう、スケジューラ５１５は、フリー・ノード１１５を識別するまで、ｘ軸を外部ループとし、ｙ軸を次のループとし、ｚ軸を内部ループとして、ＮｏｄｅＩｎＵｓｅをループする。フリー・メッシュは、フリー・ノード１１５のみを含むメッシュを含み、フリー・ノード１１５はジョブ１５０に割り当て可能なノード１１５を含む。スケジューラ５１５は、ＮｕｍＦｒｅｅＭｅｓｈｅｓとＦｒｅｅＭｅｓｈ［ＮｕｍＦｒｅｅＭｅｓｈｅｓ］とを構成する。ＮｕｍＦｒｅｅＭｅｓｈｅｓはグリッド１１０におけるフリー・メッシュの数を示し、ＦｒｅｅＭｅｓｈは、グリッド１１０における１つ又は複数のフリー・メッシュ構造を、グリッド１１０におけるフリー・メッシュ毎に識別するリストである。制約ではなく例として、ノード１１５の指数は
【００８７】
【数１６】
2006146865.tif 000020
であり得る。
スケジューラ５１５が、例えば
【００８８】
【数１７】
2006146865.tif 000021
などの非フリー・ノード１１５を識別するまでｚ軸を増やし得る。スケジューラ５１５はＦｒｅｅＭｅｓｈ．ｓｔａｒｔ［２］をｋ１に設定する場合があり、ＦｒｅｅＭｅｓｈ．ｅｎｄ［２］をｋ２−１に設定する場合がある。ＦｒｅｅＭｅｓｈ．ｓｔａｒｔ［２］はｚ軸に沿ったフリー・メッシュの開始値に相当し、ＦｒｅｅＭｅｓｈ．ｅｎｄ［２］はフリー・メッシュの終了値に相当する。スケジューラ５１５は、
【００８９】
【数１８】
2006146865.tif 000022
までの線が少なくとも１つの非フリー・ノードを含むように、更に、ｙ軸をｊ１から始めて第１値ｊ２を識別し得る。スケジューラ５１５は更に、ＦｒｅｅＭｅｓｈ．ｓｔａｒｔ［１］をｊ１に設定し、ＦｒｅｅＭｅｓｈ．ｅｎｄ［２］をｊ２−１に設定する。スケジューラ５１５は更に、
【００９０】
【数１９】
2006146865.tif 000023
までの線が少なくとも１つの非フリー・ノードを含むように、ｘ軸をｉ１から始めて第１値ｉ２を識別する。スケジューラは更に、ＦｒｅｅＭｅｓｈ．ｓｔａｒｔ［０］をｉ１  に設定し、ＦｒｅｅＭｅｓｈ．ｅｎｄ［０］を
【００９１】
【数２０】
2006146865.tif 000024
に設定する。スケジューラ５１５は、グリッド１１０における全てのノード１１５を対象とするよう、上記処理を繰り返す。上記処理は一意のフリー・メッシュ群をもたらすものでない。別の順序でループすることは、異なるフリー・メッシュ群を生成する傾向にあるが、それは２つ以上のフリー・メッシュがお互いに境界を共有する場合のみである。ノード１１５において全体が取り囲まれるフリー・メッシュは常に一意である。図９及び図１０は、２次元の場合に、ｙ軸を内部ループとして用いる場合とｘ軸を内部ループとして用いる場合との違いを示す。図９は、ｙ軸を内部ループとして用いて構成される２つのフリー・メッシュを示し、図１０は、ｘ軸を内部ループとして用いて構成される２つのフリー・メッシュを示す。図９では、領域５３０は使用中のノード１１５を含み、領域５３２ａは第１のフリー・メッシュであり、領域５３２ｂは第２のフリー・メッシュである。同様に、図１０では、領域５３０は使用中のノード１１５を含み、領域５３２ａは第１のフリー・メッシュであり、領域５３２ｂは第２のフリー・メッシュである。
【００９２】
特定の実施例では、スケジューラ５１５は第１スケジューリング・アルゴリズムを用いて空間的な要求をスケジューリングし、第２スケジューリング・アルゴリズムを用いてコンパクトな要求をスケジューリングし、第３スケジューリング・アルゴリズムを用いて何れかの要求をスケジューリングする。第１スケジューリング・アルゴリズムと第２スケジューリング・アルゴリズムはお互いに同様であるが、お互いに比較的異なるスキャン・アルゴリズムを用いる。スケジューラ５１５がジョブ１５０をスケジューリングする場合、スケジューラ５１５はＭＰＩランクによってＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔにおけるジョブ１５０に割り当てられるノード１５０を示す、すなわち、ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔ［ｉ］はＭＰＩランク  ｉを有する。｛Ｓｘ，Ｓｙ，Ｓｚ｝のサイズを有する空間的な要求をスケジュール化するよう、スケジューラ５１５は、スキャン・アルゴリズムを用いて、空間的な要求についてのＮｏｄｅＩｎＵｓｅにおける始点をサーチする。以下のロジック例はスキャン・アルゴリズムの記述例を備える。ＰａｒｔＳｔａｒｔはパーティションの始点であり、ＰａｒｔＥｎｄはパーティションの終点であり、Ｔｘ，Ｔｙ，及びＴｚ  は各々、ｘ次元、ｙ次元、及びｚ次元におけるトーラス・サイズである。
【００９３】
【表３】
2006146865.tif 000025
【００９４】
上記ロジックは比較的非効率的であるが、それはスケジューラ５１５が最大Sｘ×Sｙ×Sｚ回までＮｏｄｅＩｎＵｓｅにおける各点を評価するからである。コンパクト要求の上記スキャンでは、ｚのループが例えば、ｚ１からｚ１＋１まで増やされるにつれ、ｉ内部ループとｊ内部ループは変わることなく、ｋループは終点でしか変わらない。その結果、
【００９５】
【数２１】
2006146865.tif 000026
までの２次元メッシュは更なる計算から除外され、スケジューラ５１５は、
【００９６】
【数２２】
2006146865.tif 000027
までの２次元メッシュを更なる計算に追加する。ｉ内部ループ、ｊ内部ループ、及びｋ内部ループは、
【００９７】
【数２３】
2006146865.tif 000028
のｚ軸に沿った２次元のメッシュのシーケンスにおけるフリー・ノード１１５をカウントする。ｚループは１つのメッシュを取り除き、別のものを追加する。  ｙ  ループでは同様な作用がｙ軸に沿って生じる。（その両方ともアレイを含む）そのＦｒｅｅＸ及びＦｒｅｅＹ  は処理時間を削減することを容易にする。特定の実施例では、スケジューラ５１５は以下のアルゴリズムを用いて、コンパクトな要求をスキャンする：
【００９８】
【表４】
2006146865.tif 000029
特定の実施例では、スケジューラ５１５は次元におけるパーティション・ラッピングに対応するよう以下の修正の１つ又は複数のものを適用する：（１）次元における指数がアレイ限界を超える場合、スケジューラ５１５は、何れかのアレイ参照の前に指数にモジュラス関数を適用する；（２）パーティションがｘ次元又はｙ次元においてラッピングする場合、例えば点ａから点ｂまでの線区間についてフリー・ノード１１５を計算するよう、スケジューラ５１５は、ｘ次元又はｙ次元における点ａからパーティションの終点までの１つのものと、パーティションの始点から点ｂまでの別のものとの２つの線区間についてフリー・ノード１１５を計算する。
【００９９】
特定の実施例では、空間的な要求に適用可能なスキャン・アルゴリズムは、コンパクトな要求に適用可能な上記スキャン・アルゴリズムに同様である。特定の実施例では、空間的な要求に適用可能なスキャン・アルゴリズムとコンパクトな要求に適用可能な上記スキャン・アルゴリズムとの違いには以下のことが含まれる。すなわち、（１）スケジューラ５１５は、特定のカウントを有するメッシュにおける点を識別する代わりに、ノード１１５の全てがフリーであるメッシュにおける点を探し、そのことはメモリ参照を削減する傾向にあるということ；と（２）スケジューラ５１５は、最大２つの別のメッシュをそのベース・メッシュに連結させたそのベース・メッシュを生成するようフォールディングされる、１次元の要求又は２次元の要求を処理する場合があるので、１つ又は複数の連結メッシュを処理する必要がある場合がある。特定の実施例では、スキャン・アルゴリズムに対するそのような修正は、１６×１６×１６の構成をスケジューリングするスケジューラ５１５に関連した最大実行時間の桁を、１つ又は複数、削減する傾向にある。
【０１００】
空間的な要求をスケジューリングするよう、スケジューラ５１５は、スケジューリング可能なＴｒｙ  Ｓｔｒｕｃｔｕｒｅを識別するまでＴｒｙ構造におけるリストにおける各Ｔｒｙ構造にスキャン・アルゴリズムを適用するスケジューリング・アルゴリズムを用いる。リストにおけるＴｒｙ構造でスケジューリング可能なものが何らなく、空間的な要求上のアグレシブ・フラグがゼロである場合、スケジューラ５１５は、空間的な要求をスケジューリングすることなくクラスタ管理エンジン１３０に返答する。さもなければ、スケジューラ５１５はコンパクトなスケジューリング・アルゴリズムを用いて空間的な要求をスケジューリングしようとする。
【０１０１】
特定の実施例では、空間的なアルゴリズムによる要求をスケジューリングすることには、最大、２つのフォールディングと１つの回転との３つの変換が関係する。スケジューラ５１５はＴｒｙにおける以下のフィールドを用いて変換を追跡する：
【０１０２】
【表５】
2006146865.tif 000030
特定の実施例では、コンパクト・スケジューリング・アルゴリズムは、機能するＴｒｙ機能を識別するまで、Ｔｒｙ機能のリストにおける各メッシュにスキャン・アルゴリズムを適用する。リストにおけるメッシュ数は比較的大きい場合がある。制約ではなく例として、トーラスが１６×１６×１６のノード１１５を含み、要求が１００のノード１１５に対するものである場合、ＢｅｓｔＦｉｔ＝｛４，４，５｝であり、このことは、Ｔｒｙ構造リストにおいて２０００を超えるメッシュをもたらす。２進サーチをＴｒｙ構造に適用することは望ましい場合があるが、Ｔｒｙ構造リストの２進サーチは特定の実施例では機能しないものである。条件Ｃを含む２進サーチは：（１）Ｃが要素ｉについて真であったならば、ｉ以上の全てのｊについてＣが真であったということ；及び（２）Ｃが要素ｉについて偽であったならば、ｉ以下の全てのｊについてＣが偽であったということ；でない限り機能しないものである。特定の実施例では、Ｔｒｙ構造の２進サーチは機能しないものであるが、それは、例えばメッシュＭ１  ＝  ｛４，４，４｝を用いたスキャンが、要求を満たすのに十分なノードを見つけることになる一方、例えばメッシュＭ２  ＝  ｛２，２，１０｝を用いたスキャンが、Ｔｒｙ構造リストにおいてＭ２がＭ１を上回っているにもかかわらず、要求を満たすのに十分なノードを見つけないことになるという可能性が存在するからである。特定の実施例では、最大距離の２進サーチは機能する。スケジューラ５１５は、最大距離によってＴｒｙ構造リストにおけるメッシュをグループ化する場合、最大距離ｉを有する、リストにおけるメッシュに対するフィットを識別すれば、ｉ以上のｊ全てについて、最大距離ｊを有する、リストにおける少なくとも１つのメッシュもフィットすることになる。最大距離ｉを有する、リストにおけるメッシュが何らフィットしない場合、ｉ以下の最大距離を有する、リストにおけるメッシュも何らフィットしないことになる。制約ではなく例として、
【０１０３】
【数２４】
2006146865.tif 000031
が、フィットする最大距離ｉを有するメッシュであると仮定する。したがって、
【０１０４】
【数２５】
2006146865.tif 000032
も機能する。帰納的推論はｉ以上のｊ全てにあてはまる。最大距離ｉを有する、リストにおけるメッシュが何ら機能しない場合、最大距離ｉ−１を有する何れかのメッシュ
【０１０５】
【数２６】
2006146865.tif 000033
もフィットしない。
【０１０６】
【数２７】
2006146865.tif 000034
に及ぶからである。よって、スケジューラ５１５は初期化中にＭａｘＤｉｓｔａｎｃｅ［ＮｕｍＭａｘＤｉｓｔａｎｃｅｓ，２］を構成する。
【０１０７】
特定の実施例では、Ｆｉｔにおけるメッシュの２進サーチは最善のフィットを保証するものでないが、最善のフィットに対する相当好適な上限を備える。特定の実施例では、Ｆｉｔにおけるメッシュの２進サーチは効率的である、約１０００のメッシュに対して約１０のスキャンを生成する。スケジューラ５１５は、最大長に対する２進サーチを実行するか上限から下方線形サーチを実行するよう、上限を使用し得る。特定の実施例では、下方線形サーチのほうが、効率が高い傾向にある。
【０１０８】
スケジューラ５１５はＦｉｔに対する２進サーチを実行し、ＨｉｇｈＦｉｔとＨｉｇｈＳｔａｒｔ［３］とを戻す。ＨｉｇｈＦｉｔは要求を満たすＦｉｔの指数であり、ＨｉｇｈＳｔａｒｔはグリッド１１０におけるフィットの始点である。下方線形サーチを実行するアルゴリズムはＨｉｇｈＦｉｔとＨｉｇｈＳｔａｒｔとから開始する。特定の実施例では、スケジューラ５１５は現行のＨｉｇｈＦｉｔメッシュの最大距離を減らす。スケジューラ５１５は更に、要求を満たすメッシュをスケジューラ５１５が識別するまで、最大距離を含むメッシュ全てをループする。要求を満たすメッシュをスケジューラ５１５が識別する場合、スケジューラ５１５はメッシュをＨｉｇｈＦｉｔに設定し、もう一度最大距離を減らし、当該処理を繰り返す。スケジューラ５１５がそのようなメッシュを何ら識別しない場合、アルゴリズムの出口処理を行い、現行のＨｉｇｈＦｉｔが最善のフィットとなる。スケジューラ５１５は、特定の最大距離に対するフィットを識別することが可能でない場合、より短い最大距離に対するフィットを識別することが可能でない。
【０１０９】
スケジューラ５１５はＦｉｔメッシュをループし、ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔの終わりに１つ又は複数のノード１１５を挿入する。３つのループの順序は、ノード・ベースのトーラスにスイッチ・ベースのトーラスをスケジューラ５１５がマッピングする方法によって変わってくる。スケジューラは、１つの次元において、４×１の構成を用いてスイッチ・ベースのトーラスをマッピングする場合、１つの次元が内部ループである。スケジューラ５１５は、２つの次元において、２×２の構成を用いてスイッチ・ベースのトーラスをマッピングする場合、２つの次元が最も内部にあるループである。
【０１１０】
何れかの要求をスケジューリングするよう、スケジューラ５１５は、ノード１１５の要求数を何れかの要求に割り当てるまで、ＦｒｅｅＭｅｓｈをループし、何れかの要求を満たす。
【０１１１】
スケジューラ５１５は、ＦｒｅｅＭｅｓｈをループするにつれ、ノード１１５をＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔ漸増的に挿入する。特定の実施例では、スケジューラ５１５は以下のようにＦｒｅｅＭｅｓｈをループする：
【０１１２】
【表６】
2006146865.tif 000035
スケジューラ５１５は、ＭＰＩランクによるＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔにおけるノード・ベースの座標を用いた選択ノード１１５を示す。ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔ［ｉ，０］はＭＰＩランクｉのノード１１５のｘ座標であり、ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔ［ｉ，１］はＭＰＩランクｉのノード１１５のｙ座標であり、ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔ［ｉ，２］はＭＰＩランクｉのノード１１５のｚ座標である。ＦｒｅｅＮｏｄｅＬｉｓｔはスイッチ・ベースの座標における、スケジューラ５１５に転送される、利用可能ノード１１５のリストである。特定の実施例では、ＦｒｅｅＮｏｄｅＬｉｓｔにおけるｍｐｉＲａｎｋフィールドを設定するよう、スケジューラ５１５は以下のアルゴリズム例を用いる：
【０１１３】
【表７】
2006146865.tif 000036
以下のロジック例は、スケジューラ５１５の特定の実施例を記述する。特定の実施例では、ジョブ１５０をスケジューリングするよう、クラスタ管理エンジン１３０がスケジューラ５１５をコールする場合、クラスタ管理エンジン１３０はスケジューラ５１５に、以下の入力パラメータ値を伝達する。
【０１１４】
【表８】
2006146865.tif 000037
特定の実施例では、スケジューラ５１５は、ジョブ１５０をスケジューリングしようとした後、以下のうちの１つを戻す：
【０１１５】
【表９】
2006146865.tif 000038
スケジューラ５１５は、ジョブ１５０をスケジューリングする場合、適宜、ＦｒｅｅＮｏｄｅ構造のｍｐｉＲａｎｋフィールドを設定する。特定の実施例では、クラスタ管理エンジン１３０とスケジューラ５１５との間のラッパ機能が、クラスタ管理エンジン１３０からの入力を、スケジューラ５１５が想定する形式に変換し、スケジューラ５１５からの出力を、クラスタ管理エンジン１３０が想定する形式に変換する。
【０１１６】
特定の実施例では、ジョブ１５０が理論的にスケジューリング可能であるか否かを判定するｓｅｔＳｃｈｅｄｕｌａｂｌｅは以下のロジック例を包含する：
【０１１７】
【表１０】
2006146865.tif 000039
特定の実施例では、ジョブ・サイズを評価するようスケジューラ５１５がコールするＲａｎｋは以下のロジック例を包含する。Ｒａｎｋに対するＩｎｐｕｔは３つの要素を有する１次元アレイＩｎ［３］を含む。ＲａｎｋからのＯｕｔｐｕｔは、Ｉｎの指数をサイズの昇順によって示す３つの要素を有する１次元アレイＲａｎｋ［３］を含む。
【０１１８】
【数２８】
2006146865.tif 000040
である。特定の実施例では、Ｒａｎｋはバブル・アルゴリズムを含む。
【０１１９】
【表１１】
2006146865.tif 000041
特定の実施例では、ジョブ１５０が理論的にスケジューリング可能か否かを判定するｓｅｔＳｃｈｅｄｕｌａｂｌｅは以下のロジックを包含する：
【０１２０】
【表１２】
2006146865.tif 000042
特定の実施例では、可能なスケジューリング種類を設定するｉｎｉｔＳｃｈｅｄｕｌｅｒは以下のロジック例を包含する。ジョブ１５０が１つのノード１１５しか要求しない場合、ｉｎｉｔＳｃｈｅｄｕｌｅｒは、元の要求にかかわらず、可能な種類をＡｎｙに設定する：
【０１２１】
【表１３】
2006146865.tif 000043
特定の実施例では、空間的な要求について、スイッチ・ベースのトーラスをノード・ベースのトーラスにマッピングするｓｅｔＴｏｒｕｓＦｏｒＳｐａｔｉａｌは以下のロジック例を包含する：
【０１２２】
【表１４】
2006146865.tif 000044
特定の実施例では、ジョブ１５０の最も大きな次元と次に大きな次元ｊＲａｎｋ［２］とｊＲａｎｋ［１］とにおいてグリッド１１０を２倍にするｓｅｔＴｏｒｕｓＦｏｒ１Ｄは以下のロジック例を包含する：
【０１２３】
【表１５】
2006146865.tif 000045
特定の実施例では、ｓｅｔＴｏｒｕｓＦｏｒ２Ｄは６つの方法のうちの１つにおいて、スイッチ・ベースのトーラスをノード・ベースのトーラスにマッピングする：
【０１２４】
【表１６】
2006146865.tif 000046
ＴはＴｏｒｕｓＳｉｚｅである。最初の３つの構成は、スイッチ１６６毎のノード１１５をスケジューラ５１５が２×２のノード１１５として構成することによってもたらされる。後の３つの構成は、スイッチ１６６毎のノード１１５をスケジューラ５１５が１×１のノード１１５として構成することによってもたらされる。特定の実施例では、ｓｅｔＴｏｒｕｓＦｏｒ２Ｄは、スケジューラ５１５がマップ毎に生成することになるＴｒｙ構造をカウントし、最大のＴｒｙ構造数を生成することになるマップを選択する。互角の場合には、ｓｅｔＴｏｒｕｓＦｏｒ２Ｄは上記の順序によってマップを選択する。スケジューラ５１５はｐＳｉｚｅ［６，４］を：
【０１２５】
【表１７】
2006146865.tif 000047
を含めるよう構成する。
【０１２６】
特定の実施例では、ｓｅｔＴｏｒｕｓＦｏｒ２Ｄは以下のロジック例を包含する：
【０１２７】
【表１８】
2006146865.tif 000048
【０１２８】
【表１９】
2006146865.tif 000049
特定の実施例では、ｓｅｔＴｏｒｕｓＦｏｒ３Ｄは以下のロジック例を包含する：
【０１２９】
【表２０】
2006146865.tif 000050
【０１３０】
【表２１】
2006146865.tif 000051
特定の実施例では、コンパクトな要求のｚ次元を４×１の構成に設定するｓｅｔＴｏｒｕｓＦｏｒＣｏｍｐａｃｔは以下のロジック例を包含する：
【０１３１】
【表２２】
2006146865.tif 000052
特定の実施例では、何れかの要求のｚ次元を４×１の構成に設定するｓｅｔＴｏｒｕｓＦｏｒＡｎｙは以下のロジック例を包含する：
【０１３２】
【表２３】
2006146865.tif 000053
特定の実施例では、ｓｅｔＰａｒｔｉｔｉｏｎは以下のロジック例を包含する：
【０１３３】
【表２４】
2006146865.tif 000054
特定の実施例では、ＦｒｅｅＹとＦｒｅｅＸとを構成するｉｎｉｔＳｃａｎは以下のロジック例を包含する：
【０１３４】
【表２５】
2006146865.tif 000055
特定の実施例では、要求における次元の数を判定するｂｕｉｌｄＳｐａｔｉａｌＴｒｉｅｓは以下のロジック例を包含する：
【０１３５】
【表２６】
2006146865.tif 000056
特定の実施例では、３次元の要求についてＴｒｙＬｉｓｔを構築し、１次元の要求又は２次元の要求におけるフォールディング毎にＴｒｙ構造を構築するｂｕｉｌｄ３Ｄｔｒｙは以下のロジック例を包含する：
【０１３６】
【表２７】
2006146865.tif 000057
特定の実施例では、回転毎のＴｒｙ構造と指数マップとに対して、一意の回転の数ＮｕｍＯｒｉｅｎｔを計算するｓｅｔＯｒｉｅｎｔは以下のロジック例を包含する：
【０１３７】
【表２８】
2006146865.tif 000058
【０１３８】
【表２９】
2006146865.tif 000059
【０１３９】
【表３０】
2006146865.tif 000060
【０１４０】
【表３１】
2006146865.tif 000061
特定の実施例では、ｂｕｉｌｄ２Ｄｔｒｙは以下のロジック例を包含する：
【０１４１】
【表３２】
2006146865.tif 000062
特定の実施例では、２次元のメッシュの、考えられるフォールディング全てを構築するｂｕｉｌｄ２Ｄｆｏｌｄは以下のロジック例を包含する：
【０１４２】
【表３３】
2006146865.tif 000063
以下のロジック例によって構成されるアレイｔは結果のＴｒｙのメッシュ・サイズである。スケジューラ５１５はｔのＲａｎｋ  をアレイｔＲａｎｋに記録する：
【０１４３】
【表３４】
2006146865.tif 000064
【０１４４】
【表３５】
2006146865.tif 000065
特定の実施例では、ｂｕｉｌｄ１Ｔｒｙは、１次元の要求のフォールディングのリストを生成し、フォールディング毎に、ｂｕｉｌｄ２ＤＦｏｌｄをコールして、１つ又は複数の追加のフォールディングのリストを生成する。ｂｕｉｌｄ１Ｔｒｙは、以下の構造例を包含するＯｎｅＤＦｏｌｄＬｉｓｔにフォールディングのリストを記録する：
【０１４５】
【表３６】
2006146865.tif 000066
特定の実施例では、ｏｎｅＤは第１フォールディングを含む。特定の実施例では、ｔｗｏＤは第１フォールディングから生成されるフォールディングのリストを含む。ＮｕｍＴｗｏＤＦｏｌｄｓは、ｔｗｏＤにおけるフォールディング数を示す。特定の実施例では、ｂｕｉｌｄ２Ｄｆｏｌｄに転送されるメッシュ・サイズを示す。スケジューラ５１５は、ｔｗｏＤの要素についてＴｒｙ構造を生成し、ｂｕｉｌｄ３Ｄｔｒｙをコールして各Ｔｒｙ構造の、考えられる回転全てを構築する。特定の実施例では、ｂｕｉｌｄ１Ｔｒｙは以下のロジック例を包含する：
【０１４６】
【表３７】
2006146865.tif 000067
【０１４７】
【表３８】
2006146865.tif 000068
【０１４８】
【表３９】
2006146865.tif 000069
【０１４９】
【表４０】
2006146865.tif 000070
特定の実施例では、ＢｅｓｔＦｉｔ［３］を構成するｂｕｉｌｄＣｏｍｐａｃｔＦｉｔｓは以下のロジック例を包含する：
【０１５０】
【表４１】
2006146865.tif 000071
【０１５１】
【表４２】
2006146865.tif 000072
【０１５２】
【表４３】
2006146865.tif 000073
特定の実施例では、ｂｕｉｌｄＦｒｅｅＭｅｓｈｅｓ  Ｆｕｎｃｔｉｏｎは以下のロジック例を包含する：
【０１５３】
【表４４】
2006146865.tif 000074
【０１５４】
【表４５】
2006146865.tif 000075
【０１５５】
【表４６】
2006146865.tif 000076
【０１５６】
【表４７】
2006146865.tif 000077
特定の実施例では、スケジューラ５１５がジョブ１５０を正常にスケジューリングする場合Ｔｒｕｅを戻すＳｃｈｅｄｕｌｅＪｏｂは以下のロジック例を包含する：
【０１５７】
【表４８】
2006146865.tif 000078
特定の実施例では、ｓｃｈｅｄｕｌｅＳｐａｔｉａｌは以下のロジック例を包含する：
【０１５８】
【表４９】
2006146865.tif 000079
特定の実施例では、ＡｓｓｉｇｎｅｄＮｏｄｅＬｉｓｔを構築するｓｅｔＳｐａｔｉａｌＮｏｄｅＩｎＵｓｅは以下のロジック例を包含する：
【０１５９】
【表５０】
2006146865.tif 000080
特定の実施例では、ｓｃａｎＳｐａｔｉａｌは以下のロジック例を包含する：
【０１６０】
【表５１】
2006146865.tif 000081
【０１６１】
【表５２】
2006146865.tif 000082
特定の実施例では、Ｆｉｔに対して２進サーチを実行するｓｃｈｅｄｕｌｅＣｏｍｐａｃｔＦｕｎｃｔｉｏｎは以下のロジック例を包含する：
【０１６２】
【表５３】
2006146865.tif 000083
特定の実施例では、ｓｅｔＣｏｍＰａｃｔＮｏｄｅＩｎＵｓｅは以下のロジック例を包含する：
【０１６３】
【表５４】
2006146865.tif 000084
特定の実施例では、ＳｃａｎＣｏｍｐａｃｔは以下のロジック例を包含する：
【０１６４】
【表５５】
2006146865.tif 000085
【０１６５】
【表５６】
2006146865.tif 000086
特定の実施例では、ｓｃｈｅｄｕｌｅＡｎｙは以下のロジックを包含する：
【０１６６】
【表５７】
2006146865.tif 000087
特定の実施例では、ｓｅｔＭｐｉＲａｎｋは以下のロジックを包含する：
【０１６７】
【表５８】
2006146865.tif 000088
特定の実施例では、スケジューラ５１５は、以下に定義する以下の構造例を用いてノード１１５をジョブ１５０に割り当てる。上記のように、クラスタ管理エンジン１３０はＦｒｅｅＮｏｄｅ構造のリストをジョブ１５０とともにスケジューラ５１５に伝達する。このリストはスケジューリングに利用可能なノード１１５全てを含む。このリストでは、スイッチ・ベースの座標がリストにおける利用可能ノード１１５を識別する。スケジューラ５１５がジョブ１５０をスケジューリングする場合、スケジューラ５１５は戻す前にｍｐｉＲａｎｋを設定する。
【０１６８】
【表５９】
2006146865.tif 000089
特定の実施例では、スケジューラ５１５はＦｏｌｄ  Ｓｔｒｕｃｔｕｒｅを用いて、１次元の空間的な要求と２次元の空間的な要求とをスケジューラ５１５がフォールディングする方法を記録する。
【０１６９】
【表６０】
2006146865.tif 000090
特定の実施例では、スケジューラ５１５はＴｒｙ構造を用いて、空間的なジョブ１５０をスケジューリングするのに用いるメッシュに関する情報を記憶する。Ｔｒｙ構造は、ベース・メッシュと、最大２つまでの連結メッシュとに関する情報を含む。
【０１７０】
【表６１】
2006146865.tif 000091
特定の実施例では、スケジューラ５１５は、ＦｒｅｅＭｅｓｈ構造を用いて、スケジューリングに利用可能な、グリッド１１０におけるメッシュに関する情報を記憶させる。スケジューラ５１５はＦｒｅｅＭｅｓｈを用いて「何れかの」要求をスケジューリングする。
【０１７１】
【表６２】
2006146865.tif 000092
特定の実施例では、スケジューラ５１５は、以下に定義する以下の変数例を用いてノード１１５をジョブ１５０に割り当てる。
【０１７２】
【表６３】
2006146865.tif 000093
【０１７３】
【表６４】
2006146865.tif 000094
クラスタ管理エンジン１３０は更に、スケジューラ５１５などによって、効率的なチェック・ポインティングを行うよう動作可能であり得る。再起動ダンプは通常、ディスクに書き込まれるデータの７５％を超えるデータを備える。このＩ／Ｏは、多くの場合、処理がプラットフォームの障害によって喪失されないように行われる。このことに基づいて、ファイル・システムのＩ／Ｏは、プロダクティブＩ／ＯとディフェンシブＩ／Ｏとの２つの部分に分離することが可能である。プロダクティブＩ／Ｏは、例えば、視覚化ダンプ、主要物理変数の経時的なトレーシング他などの科学的方法を行ううえでユーザが要求する、データの書き込みである。ディフェンシブＩ／Ｏは、かなりの期間にわたって実行される大規模シミュレーションを管理するよう行われる。よって、Ｉ／Ｏ帯域幅の増加によって、チェック・ポインティングに係わる時間とリスクとを大いに削減する。
【０１７４】
エンジン１３０に戻れば、局所メモリ５２０は、システム１００の複数の特徴の論理的な記述（すなわちデータ構造）を備える。局所メモリ５２０は、互換コードによって定義、処理、又は取り出しを行うよう動作可能な何れかの物理データ記憶機構又は論理データ記憶機構に記憶させ得る。例えば、局所メモリ５２０は、１つ又は複数の拡張マーク付け言語（ＸＭＬ）のテーブル又は文書を備え得る。種々の構成要素は、ＳＱＬステートメント若しくはＳＱＬスクリプト、仮想記憶アクセス方法（ＶＳＡＭ）ファイル、フラット・ファイル、２進データ・ファイル、ビートリーブ（Ｂｔｒｉｅｖｅ）・ファイル、データベース・ファイル、又はコンマで区切られた値（ＣＳＶ）ファイルによって記述し得る。各構成要素は変数、テーブル、又は何れかの別のデータ構造を備え得るということが分かるものである。局所メモリ５２０は１つのサーバ１０２上に記憶されているか複数のサーバ又はノードにわたって記憶されている複数のテーブル又はファイルを備える場合もある。更に、エンジン１３０内部に存在しているように示されているが、局所メモリ５２０の一部又は全部は、本願の開示の範囲から逸脱することなく内部のものか外部のものであり得る。
【０１７５】
図示する局所メモリ５２０は、物理リスト５２１、仮想リスト５２２、グループ・ファイル５２３、ポリシー・テーブル５２４、及びジョブ・キュー５２５を含む。しかし、図示していないが、局所メモリ５２０は、本願の開示の範囲から逸脱することなく、ジョブ・テーブルと監査ログとを含む別のデータ構造を含み得る。図示された構造に戻れば、物理リスト５２１はノード１１５に関する識別管理情報と物理的な管理情報とを記憶させるよう動作可能である。物理リスト５２１は、ノード１１５毎に少なくとも１つのレコードを含む多次元のデータ構造であり得る。例えば、物理レコードは、「ノード」、「利用可能性」、「プロセッサ利用率」、「メモリ利用率」、「温度」、「物理位置」、「アドレス」、「ブート画像」他などのフィールドを含み得る。各レコードは上記例示的フィールドを全く含まない場合があり、上記例示的フィールドの一部又は全部を含む場合もある。一実施例では、物理レコードは、例えば仮想リスト５２２などの別のテーブルへの外部キーを備え得る。
【０１７６】
仮想リスト５２２は、ノード１１５に関する論理管理情報又は仮想管理情報を記憶させるよう動作可能である。仮想リスト５２２は、ノード１１５毎に少なくとも１つのレコードを含む多次元データ構造であり得る。例えば、仮想レコードは、「ノード」、「利用可能性」、「ジョブ」、「仮想クラスタ」、「２次ノード」、「論理位置」、「互換性」他などのフィールドを含み得る。各レコードが、上記例示的フィールドを何ら含まない場合があり、上記例示的フィールドの一部又は全部を含む場合もあるということが分かるものである。一実施例では、仮想レコードは、例えばグループ・ファイル５２３などの別のテーブルへのリンクを含み得る。
【０１７７】
グループ・ファイル５２３は、アクセス・コントロール・リスト（すなわちＡＣＬ）などの、ユーザ・グループ情報及びセキュリティ情報を記憶させるよう動作可能な１つ若しくは複数のテーブル又はレコードを備える。例えば、各グループ・レコードは、ユーザが利用可能なサービス、ノード１１５、又はジョブのリストを含み得る。各論理グループは、ジョブ１５０を投入するか、システム１００の少なくとも一部分を管理することができる１つ又は複数のユーザの事業グループ若しくは事業単位、部署、プロジェクト、セキュリティ・グループ、又は何れかの別の集合と関連し得る。この情報に基づいて、クラスタ管理エンジン１３０は、ジョブ１５０を投入するユーザが有効なユーザであるかを判定し、判定結果が肯定の場合、ジョブを実行する上で最適なパラメータを判定し得る。更に、グループ・テーブル５２３は、各ユーザ・グループを、仮想クラスタ２２０と関連させるか、特定のグループの領域内部に存在するノードなどの１つ又は複数の物理ノード１１５と関連させる場合がある。これによって、各グループが、資源をめぐって競合することなく個々の処理空間を有することを可能にする。しかし、上記のように、仮想クラスタ２２０の形状とサイズは、動的である場合があり、必要性、時間、又は何れかの別のパラメータによって変動し得る。
【０１７８】
ポリシー・テーブル５２４は１つ又は複数のポリシーを含む。ポリシー・テーブル５２４とポリシー５２４を適宜、同義に用い得るということが分かるものである。ポリシー５２４は一般的に、ジョブ１５０及び／又は仮想クラスタ２２０に関する処理情報及び管理情報を記憶している。例えば、ポリシー５２４は、問題サイズ、問題実行時間、時間スロット、横取り、ノード１１５又は仮想クラスタ２２０のユーザ割り当て率などを含む何れかの数のパラメータ又は変数を含み得る。
【０１７９】
ジョブ・キュー５２５は、実行を待つ１つ又は複数の、ジョブ１５０のストリームを表す。一般的に、キュー５２５は、（ゼロを含む）何れかの数のジョブ１５０又は、それに対する参照を記憶させる、バブル・アレイ、データベース・テーブル、又はポインタ・アレイなどの、何れかの適切なデータ構造を含む。グリッド１１０又は複数のキュー５２５と関連する１つのキュー５２５が存在し、各キュー５２５が、グリッド１１０内の一意の仮想クラスタ２２０の１つと関連付けられる場合がある。
【０１８０】
動作の一特徴では、クラスタ管理エンジン１３０は、計算を行い、情報を交換することによって問題を協調して解決するＮのタスクから成るジョブ１５０を受信する。クラスタ管理エンジン１３０は、Ｎのノード１１５を割り当て、Ｎのタスクの各々を１つの特定のノード５１５に何れかの適切な手法を用いて割り当て、それによって問題が効率的に解決されることが可能になる。例えば、クラスタ管理エンジン１３０は、ユーザによって供給される、ジョブ・タスク配置ストラテジなどのジョブ・パラメータを利用し得る。とにかく、クラスタ管理エンジン１３０は、サーバ１０２のアーキテクチャを駆使しようとし、同様に、ユーザにとってより高速なターンアラウンドを備え、システム１００の全体スループットを向上させると思われる。
【０１８１】
一実施例では、クラスタ管理エンジン１３０は更に、次の例のトポロジの何れかによって、ノード１１５を選択し、割り当てる。
【０１８２】
特定の、２次元（ｘ，ｙ）又は３次元（ｘ，ｙ，ｚ）。ノード１１５を割り当て、タスクを特定の次元で順序付けして、それによって、効率的な、近隣同士の通信を確保する場合がある。特定のトポロジは、物理的な通信トポロジが問題トポロジに一致して、ジョブ１５０の協調タスクが近隣のタスクと頻繁に通信することを可能にするということが望ましい種々のジョブ１５０を管理する。例えば、２ｘ２ｘ２次元（２，２，２）における８つのタスクの要求は立方体に割り当てられることになる。最善のフィットの目的では、２Ｄの割り当ては、効率的な近隣同士の通信を確保する一方で３次元に「フォールディング」することが可能である。クラスタ管理エンジン１３０は、特定の次元の形状を何れかの向きで自由に割り当てることができる場合がある。例えば、２ｘ２ｘ８のボックスは、垂直方向又は水平方向に、利用可能な物理ノード内に割り当て得る。
【０１８３】
最善のフィットの立方体。クラスタ管理エンジン１３０は、Ｎのノード１１５を立方体の体積において割り当てる。このトポロジはジョブ１５０を効率的に処理し、それによって、協調タスクが、何れかの２つのノード１１５間での距離を最小にすることによって、何れかの別のタスクとデータを交換することを可能にする。
【０１８４】
最善のフィットの球体。クラスタ管理エンジン１３０は、Ｎのノード１１５を球体の体積において割り当てる。例えば、第１タスクが球体の中心ノード１１５に配置され、残りのタスクが中央ノード１１５を取り囲むノード１１５上に配置される場合がある。残りのタスクの配置順序は通常重要でないということが分かるものである。このトポロジは、第１タスクと全ての別のタスクとの間の距離を最小にする場合がある。このことは、タスク２乃至Ｎが第１タスクと通信するが、お互いには通信しない大規模の問題クラスを効率的に処理する。
【０１８５】
任意。クラスタ管理エンジン１３０がＮのノード１１５を割り当てるが、ノード１１５が論理的に位置特定されるか物理的に位置特定されることに対する考慮の度合いは低くなっている。一実施例では、このトポロジはバックフィル目的でのグリッド１１０の積極的な利用を奨励し、別のジョブ１５０への影響はわずかなものである。
【０１８６】
上記トポロジと、付随する説明は図示する目的に過ぎず、実際に使用されるトポロジもそのようなトポロジを割り当てる手法も表さない場合がある。
【０１８７】
クラスタ管理エンジン１３０は、ジョブ１５０のパラメータ又はポリシー５２４のパラメータとして記憶される配置重みを利用し得る。一実施例では、配置重みは０と１との間のモディファイア値であり、この値は、要求されるタスク配置ストラテジ（又は処理配置ストラテジ）によってクラスタ管理エンジン１３０がどれだけ積極的にノード１１５を配置させようとするものであるかを表す。この例では、０の値は最適なストラテジ（又は次元）が考えられる場合のみノード１１５を配置させることを表し、１の値は、要求を処理するのに十分な、空き状態のノード１１５が存在するか、別のかたちで利用可能なノード１１５が存在する限り、直ちにノード１１５を配置させることを表す。通常、配置重みは、大規模のジョブ１５０の枯渇を妨げてＨＲＣシステム１００のジョブ・スループットを確保するために、資源予約などの管理ポリシー５２４をオーバライドするものでない。
【０１８８】
上記図示と、付随する説明は、ノード１１５とジョブ１５０とを管理する論理的な手法を実施するエンジン１３０の例示的なモジュール図を備える。しかし、この図は例示的なものに過ぎず、システム１００はこれらやその他のアルゴリズムを実施する論理構成要素の何れかの適切な組み合わせと配置とを用いることが想定されている。よって、これらのソフトウェア・モジュールは、ノード１１５とジョブ１５０とを効果的に管理する構成要素の何れかの適切な組み合わせと配置とを含み得る。しかし、種々の図示モジュールの処理は、適宜、合成される場合及び／又は分離される場合がある。
【０１８９】
図１１はインタフェース１０４の例を示す。インタフェース１０４は、ネットワーク１０６とＨＰＣサーバ１０２との間のインタフェースを備える、ハードウェア構成部分、ソフトウェア構成部分、若しくは組み込み論理構成部分、又は２つ以上のそのような構成部分の組み合わせを含む。特定の実施例では、インタフェース１０４は、インスタンシエーション・マネージャ５３４とインスタンシエーション・データ５３６とを含む。インスタンシエーション・マネージャ５３４は、クライアント１２０からの接続要求に応じてノード１１５でのホストを動的にインスタンス化する、ハードウェア構成部分、ソフトウェア構成部分、若しくは組み込み論理構成部分、又は２つ以上のそのような構成部分を含む。特定の実施例では、クライアント１２０からの接続要求は、伝送制御プロトコル（ＴＣＰ）接続要求である。ＴＰＣ接続要求を説明するが、本発明は何れかの適切な接続要求を想定している。制約ではなく例として、クライアント１２０からの接続要求は、ユーザ・データグラム・プロトコル（ＵＤＰ）又は別のＩＰベースの接続要求であり得る。
【０１９０】
特定の実施例では、ＨＰＣサーバ１０２の内部にあるホスト名とポート番号とに対して、ＨＰＣサーバ１０２に対して外部に共用宣言されるホスト名とポート番号をマッピングする、ルータ又は、ルータに対するインタフェースとして機能する。インスタンシエーション・マネージャ５３４は、特定のニーズに応じて、クライアント１２０からの接続要求に応答して１つ又は複数のノード１１５での１つ又は複数のホストを動的にインスタンス化するよう、（例えば、物理マネージャ５０５と仮想マネージャ５１０との何れか又は両方などの、）クラスタ管理エンジン１３０の１つ又は複数の構成部分と相互作用し得る。
【０１９１】
インスタンシエーション・データ５３６は、クライアント１２０からの接続要求に応じてノード１１５でのホストをインスタンス化するデータを含む。特定の実施例では、インスタンシエーション・データ５３６は、ＨＰＣサーバ１０２に対して外部に共用宣言される、サービスの１つ又は複数のリストを含む。サービスへの言及は、適宜、アプリケーションを包含し、逆も、適宜、あてはまる。ＨＰＣサーバ１０２に対して外部に共用宣言される、サービス・リストへの言及は、適宜、ルーティング・テーブルを包含し、逆も、適宜、あてはまる。特定の実施例では、インスタンシエーション・マネージャ５３４は、そのようなルーティング・テーブルを設定し、維持する。特定の実施例では、ＨＰＣサーバ１０２に対して外部に共用宣言されるサービス・リストにおけるエントリは：（１）サービス；（２）サービスに相当する、ＨＰＣサーバ１０２に対して外部に共用宣言されるホスト名とポート番号；及び（３）インスタンス化される場合、サービスを備えるホストに相当する、ＨＰＣサーバ１０２に対して内部にあるホスト名とポート番号；を規定する。エントリは、ホストを利用可能にすることとする時点、ホストのインスタンス化を行うこととする時点、及びホストを利用不能とすることとする時点を支配する規則と条件との何れか又は両方を規定する場合もある。制約ではなく例として、ホストはウェブ・サーバを備え得る。インスタンシエーション・マネージャ５３４が営業時間中にウェブ・サーバに相当するＨＴＴＰポートでのＨＴＴＰ要求を何ら受信しない場合、ホストは営業時間中に非インスタンス化状態にとどまっている場合があり、インスタンス化される場合にホストが用いることになる１つ又は複数の（グリッド１１０におけるノード１１５などの）１つ又は複数の資源は、別のホストとサービスとの何れか又は両方に利用可能であり得る。クライアント１２０の場所にいるユーザがウェブ・ブラウザを用いてウェブ・サーバを営業時間中にアクセスする場合、インスタンシエーション・マネージャ５３４はホストをインスタンス化してウェブ・サーバをクライアント１２０に備え得る。クライアント１２０の場所にいるユーザが、ウェブ・ブラウザを用いて営業時間外にウェブ・サーバをアクセスする場合、インスタンシエーション・マネージャ５３４はウェブ・サーバに相当するＨＴＴＰポートをブロック化して、ウェブ・サーバをクライアント１２０に備えることからホストを妨げる。
【０１９２】
特定の実施例では、サービスを備えるよう、インスタンシエーション・データ５３６はノード１１５でホストをインスタンス化する１つ又は複数のブート画像を含む。特定の実施例では、サービスを備えるよう、インスターシエーション・データ５３６はノード１１５でホストをインスタンス化する１つ又は複数のファイル・システムを含む。特定の実施例では、インスタンシエーション・データ５３６は更に、サービスを備えるよう、ノード１１５でのホストをインスタンス化する１つ又は複数のＯＳ構成ファイルも含む。制約ではなく例として、ＨＰＣサーバ１０２に対して外部に共用宣言されるポート番号を規定するクライアント１２０からの接続要求を受信するインスタンシエーション・マネージャ５３４に応じて、インスタンシエーション・マネージャ５３４は、ノード１１５でのサービス用のホストを初期化するよう、サービス用の、ブート画像と、１つ又は複数のファイル・システムとを用いて、グリッド１１０における利用可能なノード１１５をブートし得る。インスターシエーション・マネージャ５３４は、ＩＰトラフィックをクライアント１２０からノード１１５までルーティングするよう、局所ルーティング・テーブルと、１つ又は複数のＯＳ構成ファイルとの１つ又は複数を更新する場合もある。特定の実施例では、クライアント１２０からの接続要求に応じるＨＰＣサーバ１０２に関連した時間要求を軽減するよう、インスタンシエーション・マネージャ５３４はターゲット・ホストのＩＰ／ＭＡＣアドレスをスプーフィングし、ターゲット・ホストのためにＴＣＰ／ＩＰ接続シーケンスを開始する。クライアント１２０とインスタンシエーション・マネージャ５３４との間のＴＣＰ／ＩＰ接続シーケンスは、ターゲット・ホストがブートしている間に行われる。ＴＣＰ／ＩＰ接続シーケンスを説明したが、本発明は何れかの適切な接続シーケンスを想定している。制約ではなく例として、インスタンシエーション・マネージャ５３４は、ターゲット・ホストのためにユーザ・データグラム・プロトコル（ＵＤＰ）オーバＩＰ（ＵＤＰ／ＩＰ）又は別のＩＰベースの接続シーケンスを開始することが可能である。
【０１９３】
特定の実施例では、インスタンシエーション・マネージャ５３４は、ＨＰＣサーバ１０２での各ホストがアクティブ状態にあるか、非アクティブ状態にあるかを追跡する。特定の実施例では、インスタンシエーション・マネージャ５３４は、ＨＰＣサーバ１０２での各ホストがアクティブ状態にあるか、非アクティブ状態にあるかの制御も行う。特定の実施例では、インスタンシエーション・マネージャ５３４はサービスが利用可能であることとするか否かを判定し得る。サービスはもはや利用可能であることとするものでないということをインスタンシエーション・マネージャ５３４が判定する場合、インスタンシエーション・マネージャ５３４は、サービスを備えるようインスタンシエーション・マネージャ５３４がホストをインスタンス化した１つ又は複数のノード１１５をシャットダウンするか、アイドル状態にするか、別の方法で利用不能にし、それに応じて１つ又は複数のルーティング・テーブルを更新する。
【０１９４】
図１２は、本願の開示の一実施例による、ジョブ投入を動的に処理する方法６００の例を示す流れ図である。一般的に、図１２は、バッチ・ジョブ投入を受信し、ジョブ・パラメータと、関連ポリシー５２４とに基づいてノード１１５をジョブ空間２３０に動的に割り当て、割り当て空間を用いてジョブ１５０を実行する方法６００を表す。以下の説明は、方法６００を行ううえでのクラスタ管理モジュール１３０の処理に焦点を当てる。しかし、機能が適切な状態のままである限り、記載機能の一部又は全てを実施する論理構成要素の何れかの適切な組み合わせと配置とを用いることを想定している。
【０１９５】
モジュール６００は、工程６０５から始まり、ＨＰＣサーバ１０２はジョブ投入１５０をユーザから受信する。上記のように、一実施例では、ユーザはジョブ１５０を、クライアント１２０を用いて投入し得る。別の実施例では、ユーザは、ＨＰＣサーバ１０２を用いてジョブ１５０を直接投入し得る。次に、工程６１０で、クラスタ管理エンジン１３０は、ユーザに基づいてグループ５２３を選択する。ユーザが検証されると、クラスタ管理エンジン１３０は、工程６１５で、ユーザをグループ・アクセス制御リスト（ＡＣＬ）と比較する。しかし、クラスタ管理エンジン１３０が何れかの適切なセキュリティ手法を用いてユーザを検証する場合があるということが分かるものである。判定グループ５２３に基づいて、クラスタ管理エンジン１３０は、ユーザが要求サービスに対するアクセスを有するかを判定する。要求されるサービス及びホスト名に基づいて、クラスタ管理エンジン１３０は、工程６２０で、仮想クラスタ２２０を選択する。通常、仮想クラスタ２２０は、ジョブ１５０の投入前に識別され、割り当てられる。しかし、仮想クラスタ２２０が確立されていない場合、クラスタ管理エンジン１３０は上記手法のうちの何れかを用いて仮想クラスタ２２０を自動的に割り当てる。次に、工程６２５で、クラスタ管理エンジン１３０は、ジョブ１３０の投入に基づいてポリシー５２４を取り出す。一実施例では、クラスタ管理エンジン１３０は、ユーザ、ジョブ１５０、又は何れかの別の適切な基準に関連した適切なポリシー５２４を判定し得る。クラスタ管理エンジン１３０は更に、工程６３０で、ジョブ１５０のディメンションを判定するか別の方法で計算する。適切なディメンションが長さ、幅、高さ、又は何れかの別の適切なパラメータ若しくは特性を含み得るということは分かるものである。上記のように、これらのディメンションは仮想クラスタ２２０内の適切なジョブ空間２３０（又はノード１１５の部分集合）を判定するのに用いられる。初期パラメータが確立された後、クラスタ管理１３０は、工程６３５乃至６６５で、ＨＰＣサーバ１０２上でジョブ１５０を実行しようとする。
【０１９６】
判定工程６３５では、クラスタ管理エンジン１３０は、既に確立されているパラメータを用いて、所望のジョブ空間２３０を割り当てるのに十分利用可能なノードが存在しているかを判定する。ノード１１５が十分存在していない場合には、工程６４０で、クラスタ管理エンジン１３０が仮想クラスタ２２０におけるノード１１５の最も早く利用可能な部分集合２３０を判定する。更に、クラスタ管理エンジン１３０は、工程６４５で、部分集合２３０が利用可能であるまでジョブ・キュー１２５にジョブ１５０を追加する。処理は次に判定工程６３５に戻る。利用可能なノード１１５が十分になると、クラスタ管理エンジン１３０は、工程６５０で、利用可能なノード１１５から最適な部分集合２３０を動的に判定する。最適な部分集合２３０は、最高速処理時間、最高の信頼度のノード１１５、物理位置若しくは仮想位置、又は最初に利用可能なノード１１５を含む何れかの適切な基準を用いて判定し得るということが分かるものである。工程６５５では、クラスタ管理エンジン１３０は判定部分集合２３０を選択仮想クラスタ２２０から選択する。次に、工程６６０で、クラスタ管理エンジン１３０は、選択部分集合２３０を用いてジョブ１５０に選択ノード１１５を割り当てる。一実施例によれば、クラスタ管理エンジン１３０は、仮想ノード・リスト５２２におけるノード１１５の状態を「非割り当て」から「割り当て」に変更し得る。部分集合２３０が適切に割り当てられると、クラスタ管理エンジン１３０は工程６６５で、ジョブ・パラメータ、取り出したポリシー５２４、及び何れかの別の適切なパラメータに基づいて割り当て空間を用いてジョブ１５０を実行する。何れかの適切な時点では、クラスタ管理エンジン１３０は、ジョブ結果１６０をユーザに通信するか別の方法で提示する場合がある。例えば、結果１６０は、フォーマット化され、ＧＵＩ１２６を介してユーザに提示される場合がある。
【０１９７】
図１３は、本願の開示の一実施例による、グリッド１１０における仮想クラスタ２２０の動的バックフィルを行う方法７００の例を示す流れ図である。概略を述べれば、方法７００は、仮想クラスタ２２０において利用可能な空間を判定する工程、その空間と互換の最適ジョブ１５０を判定する工程、及びその利用可能空間において判定ジョブ１５０を実行する工程を表す。以下の説明は、この方法を行ううえでのクラスタ管理モジュール１３０の処理に焦点を当てることとする。しかし、上記流れ図と同様に、システム１００は、上記機能の一部又は全部を実施する論理構成要素の何れかの適切な組み合わせと配置とを用いることが想定されている。
【０１９８】
方法７００は工程３０５から開始し、クラスタ管理エンジン１３０は、ジョブ・キュー５２５をソートする。図示する実施例では、クラスタ管理エンジン１３０は、キュー５２５に記憶されているジョブ１５０の優先度に基づいてキュー５２５をソートする。しかし、クラスタ管理エンジン１３０が、適切なジョブ１５０又は最適なジョブ１５０が実行されることになるように何れかの適切な特性を用いてキュー５２５をソートし得るということは分かるものである。次に、工程７１０で、クラスタ管理エンジン１３０は、仮想クラスタ２００のうちの１つにおける利用可能ノード１１５の数を判定する。当然、クラスタ管理エンジン１３０がグリッド１１０又は、仮想クラスタ２２０のうちの何れか１つ又は複数のものにおける、利用可能なノード１１５の数を判定する場合もある。工程７１５では、クラスタ管理エンジン１３０は第１ジョブ１５０をソートされるジョブ・キュー５２５から選択する。次に、７２０で、クラスタ管理エンジン１３０は、選択ジョブ１５０の最適な形状（又は別のディメンション）を動的に判定する。選択ジョブ１５０の最適な形状又はディメンションが判定されると、クラスタ・エンジン１３０が、工程７２５乃至７４５で、適切な仮想クラスタ２２０においてジョブ１５０のバックフィルを行うかを判定する。
【０１９９】
判定工程７２５では、選択ジョブ１５０に十分に利用可能なノード１１５が存在するかをクラスタ管理エンジン１３０が判定する。利用可能なノード１１５が十分に存在する場合、工程７３０で、クラスタ管理エンジン１３０が何れかの適切な手法を用いて、選択ジョブ１５０にノード１１５を動的に割り当てる。例えば、クラスタ管理エンジン１３０は、図６に表す手法を用い得る。次に、工程７３５では、クラスタ管理エンジン１３０は、仮想クラスタ２２０における利用可能なノードの数を再計算する。工程７４０では、クラスタ管理エンジン１３０は割り当てノード１１５のジョブ１５０を実行する。ジョブ１５０が実行されることによって（、又は、選択ジョブ１５０に十分なノード１１５が存在しなかった場合）、クラスタ管理エンジン１３０は工程７４５で、ソートされるジョブ・キュー５２５における次のジョブ１５０を選択し、処理は工程７２０に戻る。ループとして図示したが、クラスタ管理エンジン１３０が、何れかの適切な時点で方法７００に示す手法を開始し、実行し、終結する場合があるということが分かるものである。
【０２００】
図１４は、本願の開示の一実施例による、グリッド１１０におけるノード１１５の障害を動的に管理する方法８００の例を示す流れ図である。概略を述べれば、方法８００は、ノード１１５に障害が起きたということを判定する工程、ジョブの回復と管理とを自動的に行う工程、及び障害ノード１１５を２次ノード１１５と置き換える工程を表す。以下の説明は、この方法を行ううえでのクラスタ管理モジュール１３０の処理に焦点を当てることとする。しかし、上記流れ図のように、システム１００は、記載機能の一部又は全部を実施する論理構成要素の何れかの適切な組み合わせと配置とを用いることを想定している。
【０２０１】
方法８００は工程８０５から始まり、クラスタ管理エンジン１３０は、ノード１１５に障害が起こったということを判定する。上記のように、クラスタ管理エンジン１３０は、何れかの適切な手法を用いて、ノード１１５に障害が起こったということを判定し得る。例えば、クラスタ管理エンジン１３０は、種々の時点でノード１１５（又はエージェント１３２）を取り出す場合があり、ノード１１５から応答がないことに基づいてノード１１５に障害が起こったということを判定し得る。別の例では、ノード１１５上に存在しているエージェント１３２は「ハートビート」を通信する場合があり、この「ハートビート」がないことはノード１１５の障害を示し得る。次に、工程８１０で、クラスタ管理エンジン１３０は障害ノード１１５を仮想クラスタ２２０から取り除く。一実施例では、クラスタ管理エンジン１３０は仮想リスト５２２におけるノード１１５の状態を「割り当て」から「障害」に変更し得る。クラスタ管理エンジン１３０は次に、判定工程８１５で、ジョブ１５０が障害ノード１１５に関連しているかを判定する。ノード１１５と関連しているジョブ１５０が何らない場合には、処理は終了する。上記のように、処理が終了する前に、クラスタ管理エンジン１３０は、管理者にエラー・メッセージを通信してもよく、置き換えノード１１５を自動的に判定してもよく、何れかの別の処理を行ってもよい。障害ノード１１５と関連したジョブ１５０が存在する場合、クラスタ管理エンジン１３０は、工程８２０で、ジョブ１５０と関連した別のノード１１５を判定する。次に、工程８２５では、クラスタ管理エンジン１３０は全ての適切なノード１１５のジョブ１５０を強制終了する。例えば、クラスタ管理エンジン１３０は、ジョブ１５０を終了するよう、強制終了ジョブ・コマンドを実行するか、何れかの別の適切な手法を用いる場合がある。次に、工程８３０では、クラスタ管理エンジン１３０は、仮想リスト５２２を用いてノード１１５の割り当て解除を行う。例えば、クラスタ管理エンジン１３０は、仮想リスト５２２におけるノード１１５の状態を「割り当て」から「利用可能」に変更し得る。ジョブが終結され、全ての適切なノード１１５の割り当て解除が行われると、工程８３５乃至８５０で、クラスタ管理エンジン１３０は利用可能ノード１１５を用いてジョブ１５０を再実行しようとする。
【０２０２】
工程８３５では、クラスタ管理エンジン１３０は、ポリシー５２４と、工程８２５での強制終了ジョブ１５０のパラメータとを取り出す。クラスタ管理エンジン１３０は更に、工程８４０で、取り出したポリシー５２４及びジョブ・パラメータに基づいて、仮想クラスタ２２０におけるノード１１５の最適部分集合２３０を判定する。ノード１１５の部分集合２３０が判定されると、工程８４５で、クラスタ管理エンジン１３０はノード１１５の部分集合２３０を動的に割り当てる。例えば、クラスタ管理エンジン１３０は、仮想リスト５２２におけるノード１１５のステータスを「非割り当て」から「割り当て」に変更し得る。このノード１１５の部分集合が、ジョブ１５０が実行していた元のノード部分集合とは異なり得るということは分かるものである。例えば、クラスタ管理エンジン１３０は、この実行をプロンプトしたノード障害が理由で別のノード部分集合が最適であるということを判定し得る。別の例では、２次ノード１１５が障害ノード１１５を置き換えるよう動作可能であり、新たな部分集合２３０が旧ジョブ空間２３０にかなり同様であるということを判定した場合がある。割り当て部分集合２３０が判定され、割り当てられると、工程８５０で、クラスタ管理エンジン１３０はジョブ１５０を実行する。
【０２０３】
上記流れ図と、付随する説明は、例示的方法６００、７００及び８００を示す。要約すれば、システム１００は、これらやその他のタスクを行うのに適切な何れかの手法を用いることを想定している。よって、この流れ図における工程の多くは、表しているものと同時に行われる場合及び／又は表しているものとは異なる順序で行われる場合がある。更に、システム１００は、当該方法が適切の状態のままである限り、工程を追加して方法を用いるか、工程を少なくして方法を用いる場合、及び／又は別の工程を備えている方法を用いる場合がある。
【０２０４】
図１５は、ＨＰＣシステム１００におけるオン・デマンド・インスタンシエーションの方法例を示す。方法は工程９００から始まり、インタフェース１０４は、ＨＰＣサーバ１０２に対して外部に共用宣言される、ポート番号とホスト名とを規定するクライアント１２０からの接続要求を受信する。工程９０２では、接続要求に応じて、インスタンシエーション・マネージャ５３４は、ＨＰＣサーバ１０２に対して外部に共用宣言されるサービス・リストを備えるインスタンシエーション・データ５３６をアクセスする。工程９０４では、インスターシエーション・マネージャ５３４は、接続要求において規定されるポート番号とホスト名とに相当するサービスを識別するよう、サービス・リストを用いる。工程９０６では、インスタンシエーション・マネージャ５３４は、識別サービスがクライアント１２０に利用可能であるか否かをサービス・リストによって判定する。上記のように、識別サービスがクライアント１２０に利用可能であるか否かは、接続要求に関連した時間、クライアント１２０でのユーザの識別情報、又は接続要求の別の特徴によって変わってくる場合がある。工程９０６では、識別サービスがクライアント１２０に利用可能な場合、当該方法は工程９０８に進む。工程９０８では、インスターシエーション・マネージャ５３４は、グリッド１１０における１つ又は複数のノード１１５でのホストをインスタンス化して、クライアント１２０に識別サービスを備えるよう、識別サービスに相当するＨＰＣサーバ１０２の内部にある、ホスト名とポート番号とを示すインスタンシエーション・データ５３６を用いる。上記のように、インスタンシエーション・マネージャ５３４は、ノード１１５でのホストをインスタンス化するよう、ブート画像、ファイル・システム、及びＯＳ構成を含むインスタンシエーション・データ５３６を用いる場合もあり、この時点で該方法が終了する。工程９０６では、識別サービスがクライアント１２０に利用不能である場合、当該方法は工程９１０に進む。工程９１０では、インスターシエーション・マネージャ５３４は、接続要求において規定されるポートをブロック化して、識別サービスをクライアント１２０がアクセスすることを妨げ、この時点で当該方法が終了する。図１５に示す当該方法における特定の工程を、特定の順序で行われるものとして図示し、説明したが、図１５に示す当該方法における何れかの適切な工程は何れかの適切な順序で行い得る。
【０２０５】
本願の開示は、特定の実施例と、概括的に関連している方法とによって表したが、これらの実施例と方法との改変と置換が当業者に明らかとなる。よって、例示的実施例の上記記載は本願の開示を規定するものでも制約するものでもない。別の変更、置換及び改変も、本願の開示の趣旨及び範囲から逸脱することなく考えられる。
【図面の簡単な説明】
【０２０６】
【図１】本願開示の一実施例による、高性能計算システムの例を示す図である。
【図２】図１に示すＨＰＣシステムにおけるノードの例を示す図である。
【図３】ノードにおける中央処理装置（ＣＰＵ）の例を示す図である。
【図４】ノード対の例を示す図である。
【図５Ａ】図１のシステムにおけるグリッドとその利用との種々の実施例を示す図である。
【図５Ｂ】図１のシステムにおけるグリッドとその利用との種々の実施例を示す別の図である。
【図５Ｃ】図１のシステムにおけるグリッドとその利用との種々の実施例を示す更に別の図である。
【図５Ｄ】図１のシステムにおけるグリッドとその利用との種々の実施例を示す更に別の図である。
【図６Ａ】図１のシステムによる、グラフィカル・ユーザ・インタフェースの種々の実施例を示す図である。
【図６Ｂ】図１のシステムによる、グラフィカル・ユーザ・インタフェースの種々の実施例を示す別の図である。
【図７】図１におけるシステムによる、クラスタ管理ソフトウェアの一実施例を示す図である。
【図８】ｙ次元にフォールディングされる１次元の要求の例を示す図である。
【図９】ｙ軸を内部ループとして用いて構成される２つのフリー・メッシュを示す図である。
【図１０】ｘ軸を内部ループとして用いて構成される２つのフリー・メッシュを示す図である。
【図１１】図１に示すＨＰＣシステムのインタフェース例を示す図である。
【図１２】図１の高性能計算システムによる、バッチ・ジョブを投入する方法を示す流れ図である。
【図１３】図１の高性能計算システムによる、グリッドの動的なバックフィルを行う方法を示す流れ図である。
【図１４】図１の高性能計算システムによる、ノード障害を動的に管理する方法を示す流れ図である。
【図１５】図１に示すＨＰＣシステムによる、オン・デマンド・インスタンシエーションの方法例を示す図である。
【符号の説明】
【０２０７】
１００  システム
１０２  ＨＰＣサーバ
１０４  インタフェース
１０５  管理ノード
１０６  ネットワーク
１０８  リンク
１１０  グリッド
１１５  ノード
１２０  局所クライアント
１２６  ＧＵＩ
１３０  クラスタ管理エンジン
１３２  エージェント
１４０  ディスク・ファーム
１４２  ストレージ・クライアント
１５０  ジョブ
１６４  ＣＰＵ
１６４ａ  ＣＰＵ
１６４ｂ  ＣＰＵ
１６４ｃ  ＣＰＵ
１６４ｄ  ＣＰＵ
１６６  スイッチ
１６６ａ  スイッチ
１６６ｂ  スイッチ
１６８ａ  リンク
１６８ｂ  リンク
１６８ｃ  リンク
１６８ｄ  リンク
１６８ｅ  リンク
１６８ｆ  リンク
１６８ｇ  リンク
１６８ｈ  リンク
１７０  リンク
１７２ａ  リンク
１７２ｂ  リンク
１７２ｃ  リンク
１７２ｄ  リンク
１７２ｅ  リンク
１７２ｆ  リンク
１７４  プロセッサ
１７６  ＭＣＨ
１７８  メモリ装置
１８０  ＨＣＡ
１８２  バス
１８６  ノード対
２１６  ノード・ライン
２２０  仮想クラスタ
２３０ａ  ジョブ空間
２３０ｂ  ジョブ空間
４００ａ  ＧＵＩ
４００ｂ  ＧＵＩ
５０５  物理マネージャ
５１０  仮想マネージャ
５１５  ジョブ・スケジューラ
５２０  局所メモリ
５２１  物理リスト
５２２  仮想リスト
５２３  グループ・ファイル
５２４  ポリシー・テーブル
５２５  ジョブ・キュー
５３４  インスタンシエーション・マネージャ
５３６  インスタンシエーション・データ
６００  方法
６０５  工程
６１０  工程
６１５  工程
６２０  工程
６２５  工程
６３０  工程
６３５  判定工程
６４０  工程
６４５  工程
６５０  工程
６５５  工程
６６０  工程
６６５  工程
７００  方法
７０５  工程
７１０  工程
７１５  工程
７２０  工程
７２５  判定工程
７３０  工程
７３５  工程
７４０  工程
７４５  工程
８００  方法
８０５  工程
８１０  工程
８１５  判定工程
８２０  工程
８２５  工程
８３０  工程
８３５  工程
８４０  工程
８４５  工程
８５０  工程
９００  工程
９０２  工程
９０４  工程
９０６  判定工程
９０８  工程
９１０  工程
【図１】
2006146865.tif 000095
【図２】
2006146865.tif 000096
【図３】
2006146865.tif 000097
【図４】
2006146865.tif 000098
【図５Ａ】
2006146865.tif 000099
【図５Ｂ】
2006146865.tif 000100
【図５Ｃ】
2006146865.tif 000101
【図５Ｄ】
2006146865.tif 000102
【図６Ａ】
2006146865.tif 000103
【図６Ｂ】
2006146865.tif 000104
【図７】
2006146865.tif 000105
【図８】
2006146865.tif 000106
【図９】
2006146865.tif 000107
【図１０】
2006146865.tif 000108
【図１１】
2006146865.tif 000109
【図１２】
2006146865.tif 000110
【図１３】
2006146865.tif 000111
【図１４】
2006146865.tif 000112
【図１５】
2006146865.tif 000113
【外国語明細書】
2006146865.tif 000114
2006146865.tif 000115
2006146865.tif 000116
2006146865.tif 000117
2006146865.tif 000118
2006146865.tif 000119
2006146865.tif 000120
2006146865.tif 000121
2006146865.tif 000122
2006146865.tif 000123
2006146865.tif 000124
2006146865.tif 000125
2006146865.tif 000126
2006146865.tif 000127
2006146865.tif 000128
2006146865.tif 000129
2006146865.tif 000130
2006146865.tif 000131
2006146865.tif 000132
2006146865.tif 000133
2006146865.tif 000134
2006146865.tif 000135
2006146865.tif 000136
2006146865.tif 000137
2006146865.tif 000138
2006146865.tif 000139
2006146865.tif 000140
2006146865.tif 000141
2006146865.tif 000142
2006146865.tif 000143
2006146865.tif 000144
2006146865.tif 000145
2006146865.tif 000146
2006146865.tif 000147
2006146865.tif 000148
2006146865.tif 000149
2006146865.tif 000150
2006146865.tif 000151
2006146865.tif 000152
2006146865.tif 000153
2006146865.tif 000154
2006146865.tif 000155
2006146865.tif 000156
2006146865.tif 000157
2006146865.tif 000158
2006146865.tif 000159
2006146865.tif 000160
2006146865.tif 000161
2006146865.tif 000162
2006146865.tif 000163
2006146865.tif 000164
2006146865.tif 000165
2006146865.tif 000166
2006146865.tif 000167
2006146865.tif 000168
2006146865.tif 000169
2006146865.tif 000170
2006146865.tif 000171
2006146865.tif 000172
2006146865.tif 000173
2006146865.tif 000174
2006146865.tif 000175
2006146865.tif 000176
2006146865.tif 000177
2006146865.tif 000178
2006146865.tif 000179
2006146865.tif 000180
2006146865.tif 000181
2006146865.tif 000182
2006146865.tif 000183
2006146865.tif 000184
2006146865.tif 000185
2006146865.tif 000186
2006146865.tif 000187
2006146865.tif 000188
2006146865.tif 000189
2006146865.tif 000190
2006146865.tif 000191
2006146865.tif 000192
2006146865.tif 000193
2006146865.tif 000194
2006146865.tif 000195
2006146865.tif 000196
2006146865.tif 000197
2006146865.tif 000198
2006146865.tif 000199
2006146865.tif 000200
2006146865.tif 000201
2006146865.tif 000202
2006146865.tif 000203
2006146865.tif 000204
2006146865.tif 000205
2006146865.tif 000206
2006146865.tif 000207
2006146865.tif 000208
2006146865.tif 000209
2006146865.tif 000210
2006146865.tif 000211
2006146865.tif 000212
2006146865.tif 000213
2006146865.tif 000214
2006146865.tif 000215
2006146865.tif 000216
2006146865.tif 000217
【図１】
2006146865.tif 000218
【図２】
2006146865.tif 000219
【図３】
2006146865.tif 000220
【図４】
2006146865.tif 000221
【図５Ａ】
2006146865.tif 000222
【図５Ｂ】
2006146865.tif 000223
【図５Ｃ】
2006146865.tif 000224
【図５Ｄ】
2006146865.tif 000225
【図６Ａ】
2006146865.tif 000226
【図６Ｂ】
2006146865.tif 000227
【図７】
2006146865.tif 000228
【図８】
2006146865.tif 000229
【図９】
2006146865.tif 000230
【図１０】
2006146865.tif 000231
【図１１】
2006146865.tif 000232
【図１２】
2006146865.tif 000233
【図１３】
2006146865.tif 000234
【図１４】
2006146865.tif 000235
【図１５】
2006146865.tif 000236