(57)【特許請求の範囲】
【請求項１】
アルゴリズム計算要求を分配する方法であって、前記方法は、
要求側ホストシステムから計算要求と関連付けられたデータとを分散並列計算システムのホームノード内で受信することと、
前記計算要求を実行することに適用されるべき前記並列計算システムの処理ノードの数（Ｎ）を決定することと、
前記関連付けられたデータを分割することにより、各処理ノードに関連付けられた前記データの部分を識別することと、
別々の時間間隔のシーケンスの間に、複数の通信チャネルを介して、前記ホームノードからＮ個の処理ノードの各々に前記計算要求と前記分割されたデータに関連付けられた情報とを回帰的に通信することであって、各通信チャネルは、前記時間間隔の任意の１つの間に多くとも１つのノードによって通信のために用いられる、ことと、
前記Ｎ個の処理ノードの全てに対する前記回帰的な通信の完了後に、各処理ノードによって計算を開始することと、
前記回帰的な通信によって定義される回帰的な順序で対応するより高い処理ノードに通信される各処理ノードにおける計算によって生成される部分的結果を集めることにより、集められた結果を生成することと
を含み、
前記回帰的に通信することと、前記集めることとは、対応する処理ノードに関連付けられた別々の通信チャネルを利用する、方法。
【請求項２】
前記集められた結果を最終結果として前記ホームノードから前記要求側ホストに返すことをさらに含む、請求項１に記載の方法。
【請求項３】
アルゴリズム計算要求を分配する方法であって、前記方法は、
要求側ホストシステムから計算要求と関連付けられたデータとを分散並列計算システムのホームノード内で受信することと、
前記計算要求を実行することに適用されるべき前記並列計算システムの処理ノードの数（Ｎ）を決定することと、
前記関連付けられたデータを分割することにより、各処理ノードに関連付けられた前記データの部分を識別することと、
別々の時間間隔のシーケンスの間に、複数の通信チャネルを介して、前記ホームノードからＮ個の処理ノードの各々に前記計算要求と前記分割されたデータに関連付けられた情報とを回帰的に通信することであって、各通信チャネルは、前記時間間隔の任意の１つの間に多くとも１つのノードによって通信のために用いられる、ことと、
前記Ｎ個の処理ノードの全てに対する前記回帰的な通信の完了後に、各処理ノードによって計算を開始することと、
前記回帰的な通信によって定義される回帰的な順序で対応するより高い処理ノードに通信される各処理ノードにおける計算によって生成される部分的結果を集めることにより、集められた結果を生成することと、
前記集められた結果を前記Ｎ個の処理ノードに回帰的に通信することと、
前記Ｎ個の処理ノードの全てに対する前記集められた結果の前記回帰的な通信の完了後に、各処理ノードによって計算を続行することと、
前記集めることと、前記集められた結果を回帰的に通信することと、前記計算を続行することとを反復することと、
前記計算が完了したときに、前記集められた結果を最終結果として前記ホームノードから前記要求側ホストに返すことと
を含む、方法。
【請求項４】
並列処理システムであって、
ハワードカスケードに配置された複数の処理ノードと、
第１ホームノードであって、アルゴリズム処理要求に応答して、
（ａ）前記アルゴリズム処理要求と関連付けられたデータとを前記ハワードカスケードによって定義される時間順序で前記複数の処理ノードに放送することと、
（ｂ）前記ハワードカスケードの少なくともトップレベル処理ノードにアルゴリズムのデータセットを同時に放送することと
を行う第１ホームノードと
を含み、
前記複数の処理ノードの各々は、前記ハワードカスケードのノードシーケンスを定義するために、ノード番号に割り当てられており、
隣り合うノード番号を有する隣り合う処理ノードは、前記データセットの隣り合う部分を処理することと、前記隣り合う処理ノードによる処理結果を前記ハワードカスケードによって前記放送に対して定義される前記時間順序とは逆の時間順序で前記第１ホームノードに集めることとを行うように動作可能であり、
前記関連付けられたデータが分割されることにより、データセット情報を生成し、
対応する各処理ノードによって利用されるべき前記関連付けられたデータの部分が識別され、
前記放送することは、前記複数の処理ノードの各々に対して前記データセットの対応する部分を分配することを含む、システム。
【請求項５】
前記複数の処理ノードの各々の処理に対してパフォーマンスメジャーが決定され、
前記分割することは、各処理ノードの前記パフォーマンスメジャーに従って、前記関連付けられたデータを分割することにより、前記処理ノードの間の処理負荷のバランスを取ることを含む、請求項４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
この出願は、大規模並列インターネット計算と題されて２０００年６月２６日に出願された、共通に所有され同時係属していて且つ参照により本書に取り入れられる米国特許出願第０９／６０３，０２０号の一部継続出願である。この出願は、並列処理システム及び方法と題されて２００２年１月１０日に出願され、参照により本書に取り入れられる米国特許出願第６０／３４７，３２５号に対して優先権を主張している。
【背景技術】
【０００２】
（背景）
従来技術のプログラミング方法は、“クラスター”と称される並列処理アーキテクチャーで実行される。その様なクラスターは、一般に、２つのタイプ即ち共有メモリークラスター及び分散メモリークラスターの一方である。共有メモリークラスターは、バックプレーンを通してＲＡＭメモリーを介して接続された複数のコンピュータから成る。スケーリング問題に起因して、共有されるバックプレーンを介して相互に結合され得るプロセッサの数は限られている。分散メモリークラスターは、バックプレーンではなくてネットワークを利用する。いろいろな問題がある中で、分散メモリークラスターの１つの制限はネットワークスイッチアレイの帯域幅である。
【０００３】
より具体的には、Ｎノード分散メモリークラスターの各ノードは、計算を開始する前に初期データセットの一部を入手しなければならない。この様なクラスターにおいてデータを分配する在来の方法は、各ノードに自分のデータを中央ソースから入手させることである。大きなデータセットを必要とする問題については、このことはその問題を解くためにかかる時間のかなりの部分を意味する可能性がある。このアプローチは単純ではあるが、欠点が幾つかある。第１に、中央データソースはボトルネックである。即ち、何時でも１つのノードだけが該データソースにアクセスでき、その間は他のノードは待っていなければならない。第２に、大きなクラスターについては、ノードが中央データソースにアクセスしようと試みるときに発生する衝突の数は顕著な非能率を招来する。第３に、データセットをクラスター中に分配するためにＮ個の別々のメッセージが必要である。Ｎ個の別々のメッセージにより課されるオーバーヘッドは、クラスターのサイズに比例して深刻になる非能率を意味し、このことは大きなクラスターの紛れも無い欠点である。
【０００４】
従来技術の共有メモリークラスターは、あたかもメモリーが共有されているかのように１ノードから他のノードへ情報を転送する。共有メモリーモデルのデータ転送コストは非常に低いので、データ転送技術はクラスター型の非共有メモリーマシーン内でも使われる。あいにく、非共有メモリーアーキテクチャーで共有メモリーアーキテクチャーを使用すると能率が非常に低くなり、クラスター非能率は該クラスターの実際のプロセッサ能力のほぼ３から７％である。
【０００５】
中央データソースの性能を高めればこれらの欠点の影響を減少させることができるが、データへのアクセスを調整するために、或いは通信チャネルの性能を高めるために追加のプロトコル層を通信チャネルに付け加えるとコスト及び複雑さが増す。これらのコストは、ノードの数が増えるに連れて増大し、このことが従来技術において大きなクラスターのもう一つの重大な欠点である。
【０００６】
最後に、従来技術の或る高性能クラスターは侵略的な“並列化”方法も利用する。その方法では、第二者はクラスターで使われるアルゴリズムに内々に関与する。しかし、その様なクラスターのユーザは、根本のアルゴリズムの機密性を強く望むので、この方法は商業上は受け入れられない。
【０００７】
従来技術は４つの主要な並列プログラミング方法、即ちネステッド混合モデルパラレリズム（ｎｅｓｔｅｄ−ｍｉｘｅｄ  ｍｏｄｅｌ  ｐａｒａｌｌｅｌｉｓｍ）、ＰＯＳＩＸ
Ｐスレッド（ＰＯＳＩＸ  Ｐｔｈｒｅａｄｓ）、コンパイラーエクステンション（ｃｏｍｐｉｌｅｒ  ｅｘｔｅｎｓｉｏｎｓ）、及びワークシェアリング（ｗｏｒｋ  ｓｈａｒｉｎｇ）と親しい関係にある。ネステッド混合モデルパラレリズムでは、１つのタスクがサブタスクを大量に生じさせる。これは、並列プログラミングから利益を得る可能性のあるタスクを援助するためにより多くのプロセッサを割り当てるという効果を有する。サブタスクの全てが作られた後にならなければ計算速度の増大の量は不明のままであるので、どれほどのジョブ処理が生じるか推測するのは困難である。更に、具体的なジョブの幾つかの部分だけが並列処理から利益を得、またタスク発生についての計算コストは高いので、アルゴリズムレベルでの総並列活動は低減される。従来技術のいわゆるアムダールの法則（Ａｍｄａｈｌ’ｓ  Ｌａｗ）によれば、並列活動のたとえ小さなパーセンテージの変化であっても大きな実効計算コストを生じさせる。
【０００８】
ＰＯＳＩＸ  Ｐスレッド（ＰＯＳＩＸ  Ｐｔｈｒｅａｄｓ）は共有メモリーアーキテクチャーで使われる。共有されるメモリー内の各プロセッサは、他のスレッドと通信するときにスレッド保全のメッセージを通したり通さなかったりする別々の処理スレッドとして取り扱われる。これは共有メモリー環境ではうまく行きそうであるが、分散プロセッサ環境ではうまく行かない。共有メモリー環境でも多数のプロセッサと釣り合いを取れないことは従来技術において文書で良く証明されている。バス速度限界、メモリーコンテンション、キャッシュ問題などの故に、殆どの共有メモリーアーキテクチャーは、単一の問題で作業する６４個未満のプロセッサに限定される。従って、この数を上回る効率的スケーリングは問題である。この問題を扱う標準的方法は、同時に動作する複数の非通信アルゴリズムを持つことである。これでも、単一のアルゴリズムにより達成できる処理能率向上を制限する。
【０００９】
分散ポインタ、シーケンスポイント、及び明示同期化などのコンパイラーエクステンションは、ハードウェア機能を効率よくプログラミングするのを補助するツールである。従って、コンパイラーエクステンションツールは、他の従来技術方法と比べると並列処理効果を向上させるためには殆ど役立たない。
【００１０】
ワークシェアリングモデルは、ユーザ供給コンパイラー指示又はライブラリー関数呼び出しの関数としてアプリケーションの作業を該モデルがどのように分割するかということにより特徴づけられる。ワークシェアリングの最も一般的な例はループ展開である。もう一つのワークシェアリングツールは、ＯｐｅｎＭＰにおける並列領域コンパイラー指示であり、これもアルゴリズムレベルでの限定された並列活動に対処するものである。
【００１１】
従来技術の並列処理手法は、アルゴリズムに導入されるものであってアルゴリズムに“本来備わっている”ものではないことに留意するのは興味深いことである。このことは、おそらく、従来技術においてプログラミングとアルゴリズム開発とが歴史的に分離されていた結果であろう。
【発明の概要】
【課題を解決するための手段】
【００１２】
（概要）
下記の米国特許は、以降の教示にとって有益な背景を提供するものであり、参照により本書に取り入れられる：
米国特許第４，２７６，６４３号          ０６／１９８１
米国特許第４，６６７，２８７号          ０５／１９８７
米国特許第４，７１９，６２１号          ０１／１９８８
米国特許第４，９５８，２７３号          ０９／１９９０
米国特許第５，０２３，７８０号          ０６／１９９１
米国特許第５，０７９，７６５号          ０１／１９９２
米国特許第５，０８８，０３２号          ０２／１９９２
米国特許第５，０９３，９２０号          ０３／１９９２
米国特許第５，１０９，５１５号          ０４／１９９２
米国特許第５，１２５，０８１号          ０６／１９９２
米国特許第５，１６６，９３１号          １１／１９９２
米国特許第５，１８５，８６０号          ０２／１９９３
米国特許第５，２２４，２０５号          ０６／１９９３
米国特許第５，３７１，８５２号          １２／１９９４
本発明は、ハワードカスケード（ＨＣ）を構成し動作させる方法及びシステムを提供することによって、並列計算における多数の問題を解決する。アルゴリズム計算要求は、ＨＣのホームノードに送られて、該アルゴリズム計算要求を所望の数の処理ノードに拡張するために該ＨＣのノードを通して分配（カスケード）される。計算されるアルゴリズムは、ユーザにより予め定められても良くて、該ＨＣの各処理ノードの中に格納される。関連するデータは、要求された計算に参加する全ての処理ノードに放送される。部分的結果は、ＨＣの拡張とは逆の順序で上流に集塊化され、その後、結局、要求側ホストに転送される。
【００１３】
本発明の第１の局面は、ハワードカスケード（ＨＣ）に配置された複数の処理ノードを有する並列処理システムを提供する。該ＨＣは、（ａ）該ハワードカスケードの中で該アルゴリズム処理要求を複数の処理ノードに１つの時間シーケンス順序で放送し、（ｂ）同時にハワードカスケードの少なくともトップレベルの処理ノードにアルゴリズムのデータセットを放送するために、該アルゴリズム処理要求に応答して第１ホームノードに結合する。該ＨＣは、その後、該データセットの隣り合う部分を処理して結果を該時間シーケンス順序とは逆に該第１ホームノードに連続的に集めるように動作し得る該複数の処理ノードの中の隣り合う処理ノードに配慮する。
【００１４】
本発明の他の局面は、並列処理アーキテクチャー内での高度並列処理のためのコンテキストベースのアルゴリズムを処理するシステム及び方法を提供する。該方法は、始めに、該アルゴリズムにより実行される仕事がそのアルゴリズムに固有であるのか、それとも他のアルゴリズムに固有であるのか判定する。該方法は、その後、該アルゴリズムがデータ動作を必要とするか否か判定し；そしてその仕事が該アルゴリズムに固有であるか否かということと該アルゴリズムがデータ動作を必要とするか否かということとに基づいて該アルゴリズムを並列化する。
【００１５】
本発明の他の局面は、ハワードカスケードの中で用いられるアルゴリズムを並列処理するシステム及び方法を提供する。該方法は、該方法のための入力及び出力データ記述を抽出し；該アルゴリズムのためのデータを取得し；ハワードカスケードのノードで該アルゴリズムを処理し；ハワードカスケードを通してノード結果を集め；該アルゴリズムの並列処理を要求しているリモートホストに結果を返す。
【００１６】
本発明の更に他の局面は並列計算のためのシステム及び方法を提供する。該方法は、始めに、アルゴリズム計算要求と、関連するデータとを、要求側ホストから計算システムのホームノードに送るが、その要求は、該要求の計算に使用されることになる処理ノードの要求された数（Ｎ）を含む。該方法は、その後、その計算要求を該ホームノードから複数の処理ノードに分配するが、その複数の処理ノードは該ホームノードに結合されたＮ個の処理ノードを包含し、該分配は階層的順序で行われる。その後、該方法は、該関連データをホームノードから該複数の処理ノードの全てに放送し、該複数の処理ノードから受け取られた部分的計算結果から最終計算結果を集塊化し（この集塊化は該階層的順序の逆の順序で行われる）、その最終計算結果を該ホームノードから要求側ホストに返す。
【００１７】
本発明の他の局面は、アルゴリズム計算要求を分配するシステム及び方法を提供する。この方法は、分散型並列計算システムのホームノードの中で要求側ホストシステムから計算要求及び関連するデータを受け取るステップを含む。この方法は、該計算要求を実行するために使用される該並列計算システムの処理ノードの数（Ｎ）を決定するステップと、各処理ノードと関連するデータ部分を特定するために該関連データを分割するステップも含む。最後に、該方法は、別々の時間間隔のシーケンスの間に該計算要求と分割されたデータに関する情報とを該ホームノードから該Ｎ個の処理ノードの各々に複数の通信チャネルを介して回帰的に伝達するステップを含み、各通信チャネルはいずれか１つの時間間隔の間に多くても１つの処理ノード又はホームノードによる伝達のために使用され、Ｎ個の処理ノードの全てに回帰的に伝達する別々の時間間隔の数は最少にされる。
【００１８】
本発明の更に他の局面は、並列処理システムにおいて複雑なアルゴリズムについてアルゴリズム計算要求を分配するシステム及び方法を提供する。この方法は、複数の計算セクションを包含する複雑なアルゴリズムについての計算要求を要求側ホストから受け取り；該計算要求をハワードカスケードとして構成された複数のノードに拡張し；該ハワードカスケードの中で第１計算セクションを計算して部分的結果を作り；該部分的結果を制御装置に返し；該制御装置から更なる命令を受け取り；次の計算セクションを計算するべき旨の更なる命令の受け取りに応答して該ハワードカスケード内で次の計算セクションを計算して部分的結果を作り；該返すステップと、該受け取るステップと、次の計算セクションを計算するべき旨の更なる命令の受け取りに応答して次の計算セクションを計算する該ステップとを反復し；該複雑なアルゴリズムの処理を完了するべき旨の更なる命令に応答して該部分的結果を最終結果として該要求側ホストに返すステップを含む。
【００１９】
本発明の更に他の局面は、アルゴリズムを並列化するシステム及び方法を提供する。この方法は、始めに、新しいアルゴリズム記述をホストシステムから受け取る。次に、その新しいアルゴリズムは、該新しいアルゴリズムにより使用されるデータに関連すると共にその新しいアルゴリズムにより作られたデータに関連するテンプレート情報で自動的に注釈付けされる。最後に、その注釈付けされた新しいアルゴリズムはハワードカスケード並列処理システムの各処理ノードに格納される。
【図面の簡単な説明】
【００２０】
【図１】図１は、リモートホスト上で動作するアプリケーションを処理する従来技術の並列処理クラスターのブロック図である。
【図２】図２は、図１の従来技術クラスター、アプリケーション及びリモートホストの更なる詳細を示すブロック図である。
【図３】図３は、図１、図２の従来技術のリモートホスト及びクラスターを通してのアルゴリズム分割及び処理を概略的に示す。
【図４】図４は、図１、図２の従来技術並列アプリケーションを通して処理されるアルゴリズム内の１つの並列データ項目の更なる複雑さを示すブロック構成図である。
【図５】図５は、リモートホストに接続された１つのハワードカスケードアーキテクチャーシステム（ＨＣＡＳ）のブロック図である。
【図６】図６は、１つのハワードカスケードのブロック構成図である。
【図７】図７は、図６のハワードカスケード内での放送メッセージ通信を示すブロック構成図である。
【図８】図８は、図６のハワードカスケードを通しての集塊化を示す。
【図９】図９は、６つの異なるクラスターサイズについて円周率を１０００桁まで計算する不平衡アルゴリズムにおけるノードの処理時間を示すグラフである。
【図１０】図１０は、６つの異なるクラスターサイズについて円周率を１０００桁まで計算する平衡アルゴリズムにおけるノードの処理時間を示すグラフである。
【図１１】図１１は、ハワードカスケードのノード間での２つの時間単位における問題データセットの拡張を示すブロック構成図であり、各ノードは１つのプロセッサと１つの通信チャネルとを包含する。
【図１２】図１２は、ハワードカスケードのノード間での２つの時間単位における問題データセットの拡張を示すブロック構成図であり、各ノードは２つのプロセッサと２つの通信チャネルとを包含する。
【図１３】図１３は、３つのストリップで３つのレベルに分離された１つのハワードカスケードを示す。
【図１４】図１４は、集塊化時の図１３のハワードカスケードを示す。
【図１５】図１５は、スイッチ及びルータを含む図１３のハワードカスケードの更なる詳細を示す。
【図１６】図１６は、境界条件に配慮するために図１３のハワードカスケード内でのカスケードストリップの再構成を示す。
【図１７】図１７は、複数のホームノードを有する１つのハワードカスケードを示す。
【図１８】図１８は、図１７のハワードカスケード内のホームノードのための１つのホームノードネットワーク通信形態を示す。
【図１９】図１９は、図１７のハワードカスケード内の処理ノードのための１つの処理ノードネットワーク通信形態を示す。
【図２０】図２０は、７つの処理ノードと１つの未割り当て処理ノードとを有する１つのハワードカスケードを示す。
【図２１】図２１は、７つの処理ノードのうちの１つが故障したときに再割り当てされた図２０のハワードカスケードを示す。
【図２２】図２２は、図２０のハワードカスケードの更なる詳細を示す。
【図２３】図２３は、集塊化時の１つのハワードカスケードを示す。
【図２４】図２４は、集塊化時に故障した処理ノードに配慮するように再割り当てされた図２３のハワードカスケードを示す。
【図２５】図２５は、アルゴリズム処理要求の分配のときの１つのハワードカスケードを示す。
【図２６】図２６は、アルゴリズム処理要求の分配のときに故障した処理ノードに配慮するように再割り当てされた図２５のハワードカスケードを示す。
【図２７】図２７は、低いカスケードレベルにおいて追加の処理ノードを取得するためにアルゴリズム処理要求を再放送するように構成された１つのハワードカスケードを示す。
【図２８】図２８は、アルゴリズム処理要求を再放送する図２７のハワードカスケードを示す。
【図２９】図２９は、予備のホームノードを有する１つのハワードカスケードを示す。
【図３０】図３０は、故障ホームノード後に再構成された図２９のハワードカスケードを示す。
【図３１】図３１は、単一の通信チャネルを利用するハワードカスケードの２つの単一プロセッサノードを示す。
【図３２】図３２は、二重通信チャネルを利用するハワードカスケードの２つの２プロセッサノードを示す。
【図３３】図３３は、専有アルゴリズムと１つのハワードカスケードアーキテクチャーシステムとの間の１つのインターフェースを示す。
【図３４】図３４は、図３３のインターフェースに関連する更なる定義を示す。
【図３５】図３５は、図３３及び図３４のインターフェースを利用する１つのハワードカスケードを示す。
【図３６】図３６は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図３７】図３７は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図３８】３８は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図３９】図３９は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４０】図４０は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４１】図４１は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４２】図４２は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４３】図４３は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４４】図４４は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４５】図４５は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４６】図４６は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４７】図４７は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４８】図４８は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図４９】図４９は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５０】図５０は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５１】図５１は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５２】図５２は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５３】図５３は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５４】図５４は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５５】図５５は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５６】図５６は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５７】図５７は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５８】図５８は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図５９】図５９は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図６０】図６０は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図６１】図６１は、１つのハワードカスケードアーキテクチャーシステムのためのアルゴリズムを実行するプロセスを示す。
【図６２】図６２は、複雑なアルゴリズムのプロセスの１例を示す。
【図６３】図６３は、ＨＣＡＳで複雑なアルゴリズムを実行する１つの方法。
【図６４】図６４は、ＥＣＡＤＭカテゴリーアルゴリズムのための２Ｄデータセットを示す。
【図６５】図６５は、クラスターにおけるノード間での図６４の２Ｄデータセットのローデータ分配を示す。
【図６６】図６６は、クラスターにおけるノード間での図６４の２Ｄデータセットのコラムデータ分配を示す。
【図６７】図６７は、図６４の２Ｄデータセットを処理する１つのハワードカスケードを示すブロック図である。
【図６８】図６８は、２つのネットワークスイッチに接続するために２つの通信チャネルを各々利用する２つの処理ノードの一例を示す。
【図６９】図６９は、複数の通信チャネルを管理するために多チャネルソフトウェアＡＰＩを利用する処理ノードで動作するアプリケーションスレッドの一例を示す。
【図７０】図７０は、ＨＣＡＳにおいて１ノードあたりに２つの通信チャネルを使用することの１つの利点を示す。
【発明を実施するための形態】
【００２１】
図１は、リモートホスト２６で動作する並列アプリケーション２８を処理する従来技術の並列処理クラスター１０を示すブロック図を示す。当業者が理解するように、クラスター１０は例えばベーオウルフクラスターであり、これは、通信チャネル１４及びスイッチ１６を通して複数のプロセッサ１２同士を相互に接続させて並列アプリケーション２８を処理する。プロセッサ１２の数Ｎは、クラスターのタイプに慎重に合わされ、例えばベーオウルフクラスターについては１６個のプロセッサである。リモートホスト２６は、並列アプリケーション２８の実行時間を短縮することを目標として、データ経路１８を介してクラスター１０内のプロセッサ１２の集団的計算力にアクセスして並列アプリケーション２８を動作させる。
【００２２】
図２は、クラスター１０を使用する並列処理アプリケーション２８をいっそう詳しく示している。ノード１５（１）、１５（２）、１５（３）・・・１５（Ｎ）は、ノード１５を通してのコンピュータプログラム、データ、及びプロセス間メッセージの移動を容易にする通信チャネル１４を介して相互に接続する図１のプロセッサ１２を表わす。当業者が理解するように、通信チャネル１４は、例えば、コンピュータバス、ネットワークリンケージ、光ファイバーチャネル、イーサネット（登録商標）結線、スイッチメッシュ（例えば図１のスイッチ１６）及び／又はトークンリングから成って良い。クラスター１０は、クラスター１０にインターフェースを提供するゲートウェイ２４を更に有する。ゲートウェイ２４は、クラスター境界３６を通してリモートホスト２６と通信するために、通常、ネットワークインターフェース３０、インターネットインターフェース３４、及び同列間インターフェース３５などの１つ以上のインターフェースを提供する。
【００２３】
リモートホスト２６は、例えば、並列アプリケーション２８を動作させるコンピュータシステムである。実例として、図２は、ネットワークインターフェース３０を通してゲートウェイノード２４に接続されたアプリケーション２８及びリモートホスト２６を示している。動作時には、ゲートウェイ２４は、ホスト２６で動作する並列アプリケーション２８とクラスター１０内の個々の処理ノード１５との間での通信を可能にする。アプリケーション２８は、アルゴリズムコード及びデータの並列処理の前に該アルゴリズムコード及びデータを個々の処理ノード１５にロードする。
【００２４】
アプリケーション２８がアルゴリズムコード及びデータをノード１５にロードする主な従来技術方法が２つある。もしクラスター１０がカプセル化されたクラスターであれば、ゲートウェイ２４のネットワークアドレスだけがアプリケーション２８に知られ、アプリケーション２８はゲートウェイ２４と通信し、ゲートウェイ２４は該アルゴリズムコード及びデータをノード１５へ発送する。このアプローチでは内部のノード１５はホスト２６から隠されているが、アプリケーション２８は、利用するノードの数とゲートウェイ２４を通してのノード通信の取り扱いとを明示するために、依然としてノード１５についての情報を持たなければならない。
【００２５】
カプセル化されていないクラスター１０では、アプリケーション２８は、クラスター１０の組織及び構造に関する情報と、個々のノード１５に直にアクセスするための知識とを有する。一例では、アプリケーション２８は、各ノード１５に別々に話し掛け、アルゴリズム及びデータを特定のノード１５にロードするために遠隔手順呼び出し（ＲＰＣ）を使用し、ノード１５はそれぞれ別々にアプリケーション２８に応答する。
【００２６】
遺憾ながら、これら従来技術手法のいずれも、クラスター１０をアプリケーション２８に対して単一のマシーンのようには動作させない。従って、アプリケーション２８は、アルゴリズムコード及びデータを並列に適宜処理できるように、クラスター１０の具体的な内部アーキテクチャー及びトポロジーに適合するように推測的に設計されなければならない。
【００２７】
図３はアルゴリズムコード及びデータがリモートホスト２６及びクラスター１０を通してどのように分割され処理されるかを概略的に示している。その様なアルゴリズムコード及びデータがアルゴリズムデザイン４０として図３に論理的に示されている。初期化セクション４２は、始めに、アルゴリズム実行の前に入力データを準備し、このことは通常はデータ構造を準備して該データ構造に入力データをロードすることを含む。処理結果セクション４４は、アルゴリズム実行中に作られたデータを取り扱い、それは通常は情報の格納及び出力を含む。指定された並列セクション５６は、並列特定データ項目４８，５０，及び５２を含む。具体的には、並列データ項目４８，５０及び５２は、クラスター１０でいろいろなノード１５で実行されることになるアルゴリズムコードの部分を表わす。図４は、１つの並列データ項目４８を更に詳しく示しており、図３の並列データ項目５０及び５２も同様に構成される。処理結果セクション４４は、並列データ項目４８，５０及び５２の実行から出力されたデータを結合させて完全なデータセットを形成する。
【００２８】
各並列データ項目４８，５０及び５２は、アルゴリズムコード及びデータとしてクラスター１０に転送されて処理される。アルゴリズム実行との同期化は、並列アプリケーション２８とクラスター１０の個々のノード１５との間でのプロセス間通信により達成される。並列処理ライブラリーは、このプロセス間通信を容易にするが、アルゴリズムデザイン４０がアルゴリズムノード１５のトポロジーに適合するように推測的にフォーマットされることを依然として必要とする。即ち、アプリケーション２８がコンパイルされるときにクラスター１０のトポロジーが知られていて且つ固定されなければならない。
【００２９】
矢５８は、アルゴリズムデザイン４０を、リモートホスト２６での実行のために、並列アプリケーション２８にコンパイルするステップを表わす。要素４２，４４，４６，４８，５０，５２及び５６は、並列アプリケーション２８においてコンパイルされた要素４２’，４４’，４６’，４８’，５０’，５２’及び５６’として図解的に示されている。
【００３０】
並列アプリケーション２８は、リモートホスト２６により、次の順序で、即ち初期化セクション４２’、並列データ初期化４６’、コンパイルされた並列データ項目４８’、コンパイルされた並列データ項目５０’、コンパイルされた並列データ項目５２’、及び処理結果セクション４４’の順に、実行される。図３に示されている例では、コンパイルされた並列データ項目４８’は、アルゴリズムコード及び入力データを、図４のアルゴリズム転送セクション７０及びデータ入力セクション７２をそれぞれ介してクラスター１０内のノード１５（２）に転送する。コンパイルされた並列データ項目４８’は、データ処理が完了したときを判定するためにプロセス同期化７４（図４）を用いて、そのアルゴリズムのノード１５（２）での実行を制御する。ノード１５（２）が並列データ項目４８’の実行が完了したことを示したとき、データ出力転送セクション７６（図４）は結果をノード１５（２）から並列アプリケーション２８へ転送し返す。
【００３１】
同様に、並列アプリケーション２８の全てのアルゴリズムがクラスター１０のノード１５（２）、１５（４）、１５（５）によって同時に処理されるように、コンパイルされた並列データ項目５０’及びコンパイルされた並列データ項目５２’はノード１５（４）及び１５（５）をそれぞれ利用する。
【００３２】
並列アプリケーション２８の処理結果セクション４４’は、コンパイルされた並列データ項目４８’、５０’、及び５２’がクラスター１０によって処理されてそれぞれのデータ出力転送セクション７６によって返されるときに動作する。この例では、クラスター１０のノード１５（２）、１５（４）、１５（５）によって返されるデータは、完成したデータセットの処理を続けるために処理結果セクション４４’により結合される。
【００３３】
従来技術についての以上の記述から、高性能計算におけるアーキテクチャー設計の焦点が種々のハードウェア中心の解決策に集中していることは明らかであろう。このことは、並列処理の始めから、特に１９７０年代から、現実のことであった。更に、新しい並列処理システムについての現在の趨勢は、より低いコストでより高い性能を達成するために協力して動作する複数のプロセッサを使用する。従って、歴史的に、プロセッサ性能の改善、より高速のネットワーク、メモリー及びカーシング（ｃｈａｃｈｉｎｇ）技術の改善などのハードウェアの進歩はソフトウェアの進歩より遥かに先を行っている。
【００３４】
アムダールの法則（複数のプロセッサでの与えられたアプリケーションについての並列性能を予測する）が特別にハードウェアパラメータを扱わないにもかかわらず、これが従来技術の並列処理デザインの現実であった。アムダールの法則は次の方程式：  スピードアップ＝１／（（１−ｆ）＋ｆ／ｐ）により表わされ、ここでｆはアルゴリズムの中での並列活動のパーセントであり、ｐはプロセッサの個数に等しい。“スピードアップ”は、並列処理デザインにおける個々のリンクされているプロセッサの現在のプロセッサ速度のプロセッサ速度乗数、例えば１ｘ、２ｘなど、を決定する。
【００３５】
アムダールの法則は、アルゴリズムレベルでの並列活動の程度と、計算に使われるプロセッサの数とだけを考慮する。（プロセッサの数に関して）アムダールの法則の限界を発見することは、並列処理効果が使用できなくなる前にどれほど僅かの連続的活動が存在しなければならないかというがっかりするような理解をもたらす標準的作業である。即ち、アムダールの法則のもとで“最大スピードアップ”は次の関係：  ｌｉｍｐ⇒∞［１／（（１−ｆ）＋ｆ／ｐ］＝１／（１−ｆ）により与えられ、ここで“最大スピードアップ”は、もし無限の数のプロセッサｐがあれば個々のリンクされているプロセッサの現在のプロセッサ速度のプロセッサ速度乗数、例えば１ｘ、２ｘなど、に等しく、ｆはアルゴリズム内での並列活動のパーセントである。下の表１は、ｆの与えられた値についての最大スピードアップを示す。
【００３６】
【表１】
0005487128.tif 000002
以下で更に詳しく記載するように、アムダールの法則の主要パラメータは“ｆ”であるので、複数のプロセッサで高性能計算動作を生じさせる問題は、或る程度は（ａ）アルゴリズム中心の考え方から並列処理に接近することにより、且つ／又は交差通信の並列活動を増大させるハワードカスケード（ＨＣ）を利用することによって、克服され、その各々について以下で詳しく述べる。
（ハワードカスケードアーキテクチャーシステム）
ハワードカスケードアーキテクチャーシステム（“ＨＣＡＳ”）は、（１つ以上のプロセッサを各々包含する）ノードのクラスターがクラスター間ネットワークの外にある１つ以上のリモートホストコンピュータに対して単一のマシーンとして動作することを可能にするトポロジーを提供する。従来技術とは異なって、これは、（ａ）個々のクラスターノードとの直接通信無しで且つ／又は（ｂ）クラスタートポロジーについての詳細な情報無しで各々のリモートホストがアルゴリズムコード及びデータを該クラスター内で伝達して並列処理することを可能にする。より具体的には、一実施形態では、ＨＣＡＳは次の特徴を用いてリモートホストのために単一マシーン経験をもたらす。
【００３７】
・リモートホストによりアクセスされる前にクラスターの各ノードに完全な数学的及び論理的アルゴリズムが格納される。
【００３８】
・数学的及び論理的アルゴリズムにより処理されるデータセットを変更することにより数学的及び論理的アルゴリズムが並列化されるが、該アルゴリズム自体には追加、変更又は削除は発生しない
・リモートホストは、ネットワークに取り付けられているゲートウェイプロセッサにだけアルゴリズム処理要求及びデータを送る。リモートホストは数学的及び論理的アルゴリズムをホームノードに伝えない。
【００３９】
・リモートホストは、該ＨＣＡＳのゲートウェイのＩＰアドレス及び単一のポートアイデンティティーのみを知っている。クラスター内の複数の処理ノードを使用するために複数のポート及び／又は複数のＩＰアドレスは不要である。
【００４０】
・リモートホストは、クラスターにより使用されるプロセッサの数と該クラスターにより使用される接続性モデルを含む該クラスターの内部パラメータについての情報を必要としない。
【００４１】
・ゲートウェイはカスケード内のホームノードと通信し、ホームノードは、接続されている処理ノードへの通信を容易にする。
【００４２】
図５は、アルゴリズム中心の並列処理を提供する１つのＨＣＡＳ８０を示す。ＨＣＡＳ８０は、ゲートウェイ１０７と、ホームノード１１０と、図示のように３つの処理ノード８８，９０及び９２とを有する。当業者は、３つのノード８８，９０，９２が例示の目的で示されていて、もっと多数のノードをＨＣＡＳ８０に含ませても良いことを理解するはずである。処理ノード８８，９０，９２（及びＨＣＡＳ８０の他の任意のノード）は、以下で詳しく説明するＨＣに編成されている。ゲートウェイ１０７は、リモートホスト８２及びホームノード１１０と通信し、ホームノード１１０は、ノード８８，９０，９２への通信及びこれらの処理ノード間での通信を容易にする。
【００４３】
各処理ノード８８，９０，９２は、計算集中的なアルゴリズムを包含するアルゴリズムライブラリー９９を有し、アルゴリズムライブラリー９９は、好ましくは、グラフィックユーザインターフェース、アプリケーションソフトウェア、及び／又は計算非集中的な機能を含まない。リモートホスト８２は、計算集中的アルゴリズムライブラリーＡＰＩ８６を用いて作られているリモートアプリケーション８４と共に示されている。計算集中的アルゴリズムライブラリーＡＰＩ８６は、処理ノード８８，９０及び９２のアルゴリズムライブラリー９９の計算集中機能のためのインターフェースを定める。
【００４４】
動作時には、リモートホスト８２は、計算集中的アルゴリズムライブラリー８６により作られたアルゴリズム処理要求８３をゲートウェイ１０７に送る。ゲートウェイ１０７は、要求８３をデータ経路１０９を介してホームノード１１０のコントローラ１０８に伝える。ライブラリー９９の計算集中的アルゴリズムは、処理ノードにおいて改変されずに同じままであるので、ＨＣＡＳ８０内での“並列化”は、アルゴリズムがそのデータセットをどのように通過するかということの関数として行われる。該アルゴリズムの各々は、処理ノード８８，９０及び９２に置かれたとき、データテンプレート１０２と統合される。コントローラ１０８は、付加的な情報をアルゴリズム処理要求８３に付け加え、その要求及び付加的情報をそれぞれデータ経路１０４，１０６，１０８を介して処理ノード８８，９０，９２に分配するが、その付加的情報は（ａ）処理ノードの数（例えば、この例ではＮ＝３）及び（ｂ）データ分配情報を詳しく示す。各処理ノード８８，９０，９４は、アルゴリズム処理要求８３をデータテンプレートソフトウェア１０２へ発送する同一の制御ソフトウェア９４を有する。データテンプレートソフトウェア１０２は、アルゴリズムライブラリー９９内のアルゴリズム処理要求８３により特定された特定のアルゴリズムと通信するためにデータインデックス及び入力パラメータを計算する。
【００４５】
データテンプレートソフトウェア１０２は、特定の計算集中的アルゴリズムがデータを必要とするか否か判定する。該アルゴリズムがデータを必要とするならば、データテンプレート１０２はそのデータをホームノード１１０から要求する。その後、ライブラリー９９内の該アルゴリズムは、該データが何処にあるか、どれほどの量のデータがあるか、結果を何処に置くかということを含む適切なパラメータで呼び出される。データセットが操作されるだけなので、リモートホスト８２がＨＣＡＳ８０に関する情報を持つ必要はない。具体的には、リモートホスト８２は、どの処理ノード８８，９０，９２にも情報、データ、或いはプログラムを直接には送らない。ＨＣＡＳ８０は、リモートホスト８２にはゲートウェイ１０７を介して単一のマシーンとして見える。ＨＣＡＳ８０が処理を完了すると、各ノード８８，９０，９２からの結果は集塊化され（以下で詳しく説明する）、結果８５としてリモートホスト８２に伝えられる。
【００４６】
一実施形態では、ＨＣＡＳは、与えられた時間単位数で通信できるノードの数を最大にする。ＨＣＡＳは、例えばデータセット全体を全ての処理ノードに同時に放送することによって、従来技術における非能率（例えば、共有メモリー環境での衝突、中央データソースのネック、及びＮノードクラスターについてのＮ個のメッセージの必要性）を避ける。通信チャネルを介して同じ量のデータが転送されるとしても、放送は、Ｎ個の別々のメッセージを使用するオーバーヘッドを無くする。放送の一つの重要な利点は、データを送ることについてのオーバーヘッドがＨＣＡＳ内のノードの数と無関係であることである。これは、大きなクラスターの効率を維持するときに特に重要である。
【００４７】
各ＨＣＡＳは、図６のＨＣ１００などの、少なくとも１つのＨＣを有する。ＨＣ１００は、７個の処理ノード１１２，１１４，１１６，１１８，１２０，１２２及び１２４の中に例示されている。アルゴリズム処理要求１４０，１４２，１４４，１４６，１４８，１５０及び１５２は、ＨＣ１００のノード間で渡されるメッセージである。図示されているように、ＨＣ１００を７個のノードの全部に拡張するために３つの時間単位（時間１、時間２、時間３）が使われる。時間単位は、例えば、伝達媒体に関わらず、ＨＣＡＳにおける１メッセージについての伝達時間である。例えば、メッセージは、次の媒体即ちＬＡＮ、ＷＡＮ、共有されるバス、光ファイバーインターフェースなどのいずれかを横断して伝達可能である。
【００４８】
ＨＣ１００は、アルゴリズム処理要求をノードの任意のグループに送る。最大限の拡張は、全てのアルゴリズム処理要求１４０，１４２，１４４，１４６，１４８，１５０及び１５２のの問題セットが全ての要求された処理ノード（この例ではノード１１２，１１４，１１６，１１８，１２０，１２２及び１２４）に伝達されたときに生じる。ホームノード１１０は、並列処理に必ずしも参加しない。
【００４９】
ＨＣ１００が最大限に拡張されると、全てのノードがアルゴリズム処理要求を受け取っていて、関連するデータを受け取る準備ができている。各処理ノードは、そのアルゴリズム処理要求メッセージで受け取った情報に基づいて、どれほどの量のデータが来ると予想するべきか分かっている。各処理ノードは、ホームノード１１０により管理されるマルチキャストメッセージグループに加入して放送通信チャネルを聞こうとすることによって、該データを受け取る準備をする。該マルチキャストメッセージグループを通して、ホームノード１１０は単一のメッセージを放送し、このメッセージは、放送通信チャネルを聞こうとしている全てのノードにより受信される。ホームノード１１０は、全てのノードが該マルチキャストメッセージグループに加入するのを待ち、その後、データセットを全てのノードに同時に放送する。ＨＣ１００の放送通信チャネル１２１でのデータ放送の例が図７に示されている。
【００５０】
ＨＣ１００により使用されるデータ分解方式は、ノード数に基づいてデータセットを分割する。例えば、処理ノード１１２はデータの第１部分を受け取り、処理ノード１１４はデータの第２部分を受け取り、そしてＨＣ１００の最後の必要とされる処理ノードがデータの最後の部分を受け取るまで、同様に処理ノードがデータ部分を受け取る。この様にして、各処理ノードのためのデータが下流側の処理ノードにより受け取られるデータに隣接するようにデータセットが分配される。
【００５１】
ＨＣ１００の各ノードは、データを受け取るとき、データセット全体を格納するかそれとも自分が必要とするデータだけを格納するかを選ぶことができる。必要なデータだけが格納されるのであれば、残りのデータは受信時に捨てられても良い。このノード間選択は、以下で述べるように、改善された並列処理性能を促進する柔軟性を維持しながらデータを格納するために使われるメモリーの量を減少させる。
【００５２】
処理ノードは、自分のデータを受け取ると、マルチキャストメッセージグループから去る。ホームノード１１０は、どのノードがマルチキャストメッセージグループから去ったか監視し、このことにより、各ノードが自分のデータを受け取ったという明確な承認を提供する。ホームノード１１０は、処理ノードが指定されたタイムアウト後にマルチキャストメッセージグループに残っているか注意することによって、失敗した処理ノードを検出することができ、その時には、回復を試みる処理ノードとの個別通信チャネルを開くことができる。
【００５３】
処理ノードが自分達の結果を作り終わると、集塊化プロセスが始まる。集塊化とは、（ａ）各処理ノードからそれぞれの結果を集めて（ｂ）それらの結果を完全な解答の形にフォーマットすることを指す。各処理ノードは、自分の結果を直ぐ上流の処理ノードに送る。これにより、ＨＣ１００内での初期拡張の逆のシーケンス順序で結果の流れが生じる。ＨＣ１００による集塊化プロセスの例が図８に示されている。
【００５４】
集塊化の直接的結果は、各ノードからの結果が初期データセットの分解と同じ排列関係を保つことである。各処理ノードは、下流側の処理ノードを何個持っているか知っており、下流側ノードからの、後の下流側結果はデータの連続的ブロックを形成する。各処理ノードは、自分の結果データと、上流側処理ノードが受け取った結果を適切な位置に置くことを可能にする場所及びサイズの情報とを有する。ＨＣ１００を通して結果が上流へ送られるとき、該結果情報のサイズは、結果ブロック全体がホームノード１１０で組み立てられるまで連続的に膨らんで行く。
【００５５】
例えば、図８は、ＨＣ１００のノードを通して集塊化がどのように行われるか示している。第１時間単位（“Ｔｉｍｅ  １”）において、ノード１１６，１１８，１２２，１２４はそれぞれの結果を（それぞれ“ｐｒｏｃｅｓｓｏｒ  ３  ｄａｔａ”、“ｐｒｏｃｅｓｓｏｒ  ４  ｄａｔａ”、“ｐｒｏｃｅｓｓｏｒ  ６  ｄａｔａ”、及び“ｐｒｏｃｅｓｓｏｒ  ７  ｄａｔａ”として特定されている）上流側ノードに（即ち、ノード１１４、ノード１１２、ノード１２０、及びホームノード１１０（ノード１２４について）に伝える。第２時間単位（“Ｔｉｍｅ  ２”）においてノード１１４及び１２０がそれぞれの結果（その下流側ノードの結果を含む）を上流側ノード１１２及び１１０にそれぞれ伝えるようにして、これら上流側ノードでデータが塊になる。第３時間単位（“Ｔｉｍｅ  ３”）においては、図示されているように各下流側ノードからの結果がホームノード１１０で集塊化するので、集塊化は完了する。
【００５６】
従って、集塊化プロセスはＨＣ１００を通るデータの“逆流”と見なされても良い。この逆流の１つの重要な利点は、もし全ての処理ノードが結果をホームノード１１０に同時に差し出そうとした場合には、ノードを接続する通信ネットワークが飽和するであろうが、この逆流の場合には該通信ネットワークが飽和しないことである。従来技術の多くのクラスターアーキテクチャーは、結果が単一のノードに返されるときにネットワークボトルネックを経験する。このボトルネックは計算負荷が処理ノード間に均一に分配されていれば悪化する可能性があるが、これは最大の計算効率を得るために望ましいことである。
（並列処理アーキテクチャーのためのコンテキストベースのアルゴリズム）
一定のコンテキストベースのアルゴリズムは、アルゴリズムの作業定義要素と考えることのできるものである。例えば、カーネルは、畳み込みアルゴリズムを必要とするデータセットに対して実行される作業定義要素である。以下でいっそう詳しく述べるように、その様なコンテキストベースのアルゴリズムは（ａ）内部又は外部コンテキストで、及び／又は（ｂ）アルゴリズム的データ動作で、又はアルゴリズム的動作無しで、更に区別することができる。アルゴリズム的データ動作は、アルゴリズム内で自然なプロセスとして動くデータである。データを動かす内部要件を有するアルゴリズムの例はマトリクス反転アルゴリズムであるが、その理由は、マトリクス反転アルゴリズムにデータ運動が本来備わっているからである。
【００５７】
従って、アルゴリズムデータ動作により区別される一定のコンテキストベースのアルゴリズムは５つの並列化カテゴリーを定める：即ち、トランザクショナル（Ｔｒａｎｓａｃｔｉｏｎａｌ）、アルゴリズム的データ動作の無い内部コンテキスト（Ｉｎｔｅｒｎａｌ
Ｃｏｎｔｅｘｔ  Ｎｏ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｄａｔａ  Ｍｏｖｅｍｅｎｔ  （“ＩＣＮＡＤＭ”））、アルゴリズム的データ動作のある内部コンテキスト（Ｉｎｔｅｒｎａｌ  Ｃｏｎｔｅｘｔ  ｗｉｔｈ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｄａｔａ  Ｍｏｖｅｍｅｎｔ（“ＩＣＡＤＭ”））、アルゴリズム的データ動作の無い外部コンテキスト（Ｅｘｔｅｒｎａｌ  Ｃｏｎｔｅｘｔ  Ｎｏ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｄａｔａ  Ｍｏｖｅｍｅｎｔ（“ＥＣＮＡＤＭ”））、及びアルゴリズム的データ動作のある外部コンテキスト（Ｅｘｔｅｒｎａｌ  Ｃｏｎｔｅｘｔ  ｗｉｔｈ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｄａｔａ  Ｍｏｖｅｍｅｎｔ（“ＥＣＡＤＭ”）。これらのカテゴリーと該カテゴリーの重要性とは、以下でいっそう詳しく説明されるが、ＨＣ１００を含むあらゆるタイプの並列処理クラスターに関連する。
（トランザクショナルカテゴリー）
本技術分野で知られているベーオウルフクラスター及びＳＥＴＩ＠Ｈｏｍｅ並列処理アーキテクチャーは、両方とも、処理される問題が本質的にトランザクショナルであるときに最も良く働く。トランザクショナル問題は、問題スペースが多数の独立した問題からなっている問題である。従ってそれぞれの問題が別々に解決され、それらの問題間には交差通信や同期化は存在しない。この種の問題については殆どどの部類のコンピュータでも使用可能であり、唯一の課題は、データをコンピュータのグループに或いはコンピュータのグループから動かすことである。
【００５８】
例えば、次のアプリケーション即ち星スペクトル分析、一定のバンキングアプリケーション、及び遺伝子工学は、概して、トランザクショナル問題セットを有する。この様なアプリケーションは、交差通信が無い、高度の並列処理がある、高い規模設定性があるなど、幾つかの共通の特徴を有する。
【００５９】
ＨＣ１００は、トランザクショナルカテゴリーの問題セットを処理するのに役立つ。
（アルゴリズム的データ動作の無い内部コンテキスト（ＩＣＮＡＤＭ）カテゴリー）
多くの論理的問題及び数学的問題がＩＣＮＡＤＭカテゴリーに属する。定義により、ＩＣＮＡＤＭカテゴリーは、具体的な論理的／数学的アルゴリズムについて達成されるべき最終作業が該アルゴリズムに内在していて、変換されるデータを該アルゴリズムの一部分として動かす必要の無いカテゴリーである。次の例、即ち級数展開、ソベルエッジ検出（Ｓｏｂｅｌ  ｅｄｇｅ  ｄｅｔｅｃｔｉｏｎ）、畳み込み、マトリクス乗算、相関、交差相関、１次元高速フーリエ変換（１Ｄ−ＦＥＴ）、１Ｄウェーブレットなどは、ＩＣＮＡＤＭ問題セットを有する。
【００６０】
並列化に関して、級数展開を必要とする数値計算は、級数の始めの低次項と終わりの高次項の計算の複雑さに固有の不均衡を有する。級数展開に基づくアルゴリズムが並列処理により実行されるように並列インプリメンテーションに変換されるとき、この不均衡は並列効率を達成する上での障害となる。より具体的には、級数展開の項が並列処理アーキテクチャーのノードに連続する間隔で（例えば、１−１０，１１−２０，２１−３０，・・・）分配されるとき、始めの方の間隔が割り当てられたノードは終わりの方の間隔が割り当てられたノードより少ない計算を有する。計算負荷の不釣り合いは並列計算では非能率につながる。
【００６１】
一実施形態では、計算負荷は、並列計算の最大効率を達成するために全てのノードに均しく分配される。この分布は、ＨＣ１００内での、或いは従来技術の現存する並列処理アーキテクチャーの中での並列処理を更に向上させる。
【００６２】
級数展開の多様性が与えられたとしても、各項目についての計算の複雑さの増大を予測することは困難である。一実施形態では、計算負荷を均等にするためにｎ番目毎の項が各ノードに割り当てられる。ｎを並列処理アーキテクチャーのノードの数に等しくすることによって、各ノードの計算負荷は同数の低次項及び高次項を有することになる。級数の項の総数がノードの数で均等に割りきれる場合には、各ノードが等しい数の項を有することになる。７ノードのアレイ（例えば、図６のＨＣ１００）についての４２項の級数展開の例が表２に示されている。
【００６３】
【表２】
0005487128.tif 000003
級数の項の総数がノードの数で均等に割りきれない場合には、一実施形態ではその級数項はなるべく均等に分割される。７ノードアレイ（例えば、図６のＨＣ１００）での３９項級数展開の例が表３に示されている。
【００６４】
【表３】
0005487128.tif 000004
表４に見られるように、各ノードは、級数の長さを超えるときに自分の項を切り落とす。これは、多ノードアレイ（例えば、図２のクラスター１０の中、及び図６のＨＣ１００の中）での任意の長さの級数の相似分配の効率的手段を提供する。
【００６５】
均等に割りきれる場合（表２）、第１項と最終項との間に依然として僅かな不均衡がある。これは、各々のｎ番目間隔に存在する不均衡から生じる。アレイ内の第１ノードは全てのｎ番目間隔内の第１項を計算し、最後のノードは最後の項を計算する。しかし、連続する項間で複雑さが急速に増大しなくて、級数が長すぎない場合、殆どの級数展開のために、このレベルのバランシングで充分である。
【００６６】
それでもなお、連続する間隔における各ノードについて出発項を１だけ進め、最後の間隔における最後の項を計算したノードを第１項へ回転させて各ｎ番目間隔における計算上の不均衡を無くすることによって追加レベルのバランシングを達成することができる。この再バランシングの例が表４に示されており、７ノードアレイに分配された４２項級数展開を例示している。
【００６７】
【表４】
0005487128.tif 000005
表４の分配は、級数項の計算上の複雑さがどのくらい早く増大するか、或いは何個の項が計算されるかということに関わらず、完璧に近いバランシングを達成する。
【００６８】
これらの手法の有効性の例が図９及び図１０に示されている。図９及び図１０の各例において、並列アルゴリズムを用いて円周率の１０００桁が計算された。その並列アルゴリズムはａｒｃｔａｎ（ｘ）を使用するマチンの公式に基づいており、これは、ａｒｃｔａｎ（ｘ）が冪級数展開を用いて計算され、その級数中の連続する項の計算が高度に不均衡であるので選択された。計算は、アレイ内の１，３，７，１５，３１、及び６３個のノードを用いて実行された。具体的には、級数展開の項が連続する間隔（例えば、１−１０，１１−２０，２１−３０、・・・）でノードに分配される不均衡の場合を示している。計算上の不均衡は個々のノードの計算時間の極端な不均衡から明らかである。一方、図１０は、級数展開の項が表２に示されているようにノードに分配される均衡している場合を示す。個々のノードの計算時間がほぼ等しいことから、均衡度の劇的改善が明らかである。
【００６９】
マチンの公式を用いる円周率の計算の例はＩＣＮＡＤＭカテゴリーに適合する。その理由は、実行されることになる最後の作業がマチンの公式であり、そのアルゴリズムが本質的にデータを移動させないことにある。
【００７０】
コンピュータの接続されているグループ（例えば、図６のＨＣ１００のノード）を使って、表２−４及び図９、図１０で配慮されているような計算のスケールアップ及び計算のバランスの両方を生じさせることができる。
【００７１】
一定の実施形態では、ＩＣＮＡＤＭカテゴリー内の多数の関数をつなぎ合わせていっそう複雑な関数を作ることができる。例えば、Ｉｍａｇｅｏｕｔｐｕｔ＝２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ（Ｋｅｒｎｅｌ，２Ｄ−ＳＯＢＥＬ（ｉｍａｇｅｉｎｐｕｔ））を考察する。ここでｉｍａｇｅｉｎｐｕｔは畳み込みプロセスへの基本入力イメージであり、２−ＤＳＯＢＥＬはソベルエッジ検出アルゴリズムであり、Ｋｅｒｎｅｌは畳み込みカーネル（例えば、イメージ中に見出される物体）であり、２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮは畳み込みアルゴリズムであり、Ｉｍａｇｅｏｕｔｐｕｔは出力イメージである。２Ｄ−ＳＯＢＥＬエッジ検出アルゴリズムの出力は２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮアルゴリズムの入力要件と矛盾しない出力イメージアレイを作るので、データ変換が行われる必要は無い。
【００７２】
しかし、データ変換が必要ならば、上記方程式は次の形を取ることができ：  Ｉｍａｇｅｏｕｔｐｕｔ＝２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ（Ｋｅｒｎｅｌ，ＴＲＡＮＳＬＡＴＥ（２Ｄ−ＳＯＢＥＬ（ｉｍａｇｅｉｎｐｕｔ）））、ここでｉｍａｇｅｉｎｐｕｔは基本入力イメージであり、２−ＤＳＯＢＥＬはソベルエッジ検出アルゴリズムであり、Ｋｅｒｎｅｌは畳み込みカーネル（例えば、見出される物体）であり、２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮは畳み込みアルゴリズムであり、Ｉｍａｇｅｏｕｔｐｕｔは出力イメージであり、ＴＲＡＮＳＬＡＴＥは２Ｄ−ＳＯＢＥＬ出力を２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ関数の入力要件と矛盾しないようにするために必要な仮想の関数である。この形において、次の規則が適用される：
規則１：  現在のＴＲＡＮＳＬＡＴＥ関数についてデータ動作が不要ならば、それはＩＣＮＡＤＭカテゴリーの関数として取り扱われて良くて、更なる努力は不要である。
規則２：  現在のＴＲＡＮＳＬＡＴＥ関数についてデータ動作が必要ならば、方程式全体をＩＣＡＤＭ又はＥＣＡＤＭカテゴリーのアルゴリズムとして取り扱って良く、以下でいっそう詳しく論じる。
【００７３】
一実施形態では、並列処理を容易にするために数個の関数がこの様に結合される。特にＩＣＮＡＤＭクラスのアルゴリズムは、該アルゴリズムに入力された最大のデータセットのサイズの関数として更にスケーリングすることができる。その様なものとして、プロセッサの集合の速度は、充分なデータがあるならば、プロセッサの速度の合計の９０％以上となることができる。総合エンドツーエンド並列処理性能を保証するために、並列処理アーキテクチャーのＩ／Ｏは、ノードへ、またノードから、データを動かすために要する時間がそのデータを処理するのに要する時間の小さなパーセンテージであるように、セットされるべきである。
【００７４】
ＩＣＮＡＤＭカテゴリーアルゴリズムは、コンパイラー又は実行時変換プロセスを用いて並列化することができる。実行時変換プロセスは改善された柔軟性を与えるので、実行時変換プロセスが使われるのが好ましい（即ち、コンパイルされた解は、与えられた問題に必要な仕事に最大限に適合する計算資源を動的に割り当てない）。
（アルゴリズム的データ動作のある内部コンテキスト（Ｉｎｔｅｒｎａｌ  Ｃｏｎｔｅｘｔ  ｗｉｔｈ  Ａｌｇｏｒｉｔｈｍｉｃ  Ｄａｔａ  Ｍｏｖｅｍｅｎｔ（“ＩＣＡＤＭ”）））
一定の論理的及び数学的問題がこのカテゴリーに属する。定義により、特定の論理的又は数学的問題について達成される最終の仕事がアルゴリズムに本来備わっていて、変換されるデータがアルゴリズムの一部としてデータを動かすことを必要とするカテゴリーである。ＩＣＡＤＭカテゴリーに属するアルゴリズムの例は、マトリクス転置アルゴリズム及びガウス消去法アルゴリズムを含む。
【００７５】
ＩＣＡＤＭカテゴリーのアルゴリズムは、この様にデータの動作を必要とする。このことは、データ動作が速く行われるほど、アルゴリズムは複数のノード又はプロセッサに適用されたときに良好にスケーリングするということを意味する。このジレンマを解決する１つの方法は、より速いポイントツーポイント接続速度に焦点を合わせることであり、これは本質的に高価ではあるがＩＣＡＤＭカテゴリーのアルゴリズムのためには良く働く。
【００７６】
それでもなお、一実施形態では、データ動作並列化がＩＣＡＤＭカテゴリーのアルゴリズムのために使用される。接続されたノードのアレイ内の多プロセッサ通信のための最短時間最大ノード展開モデルを定義するために次のモデルを使用することができる。このモデルは、例えば、標準的スイッチメッシュの上の論理的オーバーレイとして、或いは固定接続モデルとして実現され、前者（論理的オーバーレイ）の方が好ましい：
【００７７】
【数１】
0005487128.tif 000006
ここで、Ｈ（）はＨＣを表わし、Ｐはマザーボードあたりのプロセッサの数であり、Ｃはマザーボードあたりの通信チャネルの数であり、ｔは拡張時間単位であり、ｘは該ＨＣのストリップ数（下で定義する）である。同様にマザーボードあたりにＰ個のプロセッサとマザーボードあたりにＣ個のチャネルとを有する与えられた数のノードについて拡張時間ｔは：
ｔ＝φｌｏｇ（（Ｎ＋Ｐ）／Ｐ）／ｌｏｇ（Ｃ＋１）ｋ
である。絵画的には、Ｐ＝１，Ｃ＝１，ｔ＝２であれば、拡張は図１１の様に示される。
【００７８】
論理的オーバーレイとしてのデータ通信は次の３つの方法のうちの１つで行われて良い：（１）問題セット分配及び集塊化のための直接カスケード通信；（２）全ノードへの初期データの１対多数（各ノードによる必須データの選択を考慮に入れるカスケード位置を用いる）；及び（３）データを共有する必要とされる全ての関連ノードへの中間データの補助的な１対多数。Ｐ＝２，Ｃ＝２，ｔ＝２であれば、展開は図１２に示されている。システム１６０，１６２，１６４，１６６，１６８，１７０，１７２，１７４、及び１７６は、２つのプロセッサと２つの通信チャネルとを含む単位を表わし（Ｐ＝２，Ｃ＝２）、これにより各システムはＨＣＡＳにおける２つのノードを表わす。この例において、システム１６０は、２つのホームノードＨ１及びＨ２を表わす。システム１６２は２つの処理ノードＰ１及びＰ２を表わす。システム１６４は２つの処理ノードＰ３及びＰ４を表わし、以降同様である。表５は、バイナリーツリー拡張とＨＣ（ノードあたりのプロセッサの選択数はＰ、通信チャネルの選択数はＣ）の拡張速度との比較を示し、控えめに構成されたノードでも（例えば、１つのプロセッサと１つのネットワークインターフェースカード（ＮＩＣ）とを有するマザーボード、即ちＰ＝１，Ｃ＝１）バイナリー拡張のほとんど２倍の拡張速度を作り出すことを示している。
【００７９】
【表５】
0005487128.tif 000007
前述したように、ＩＣＡＤＭカテゴリーのアルゴリズムは、コンパイラー又は実行時変換プロセスを用いて並列化することができる。好ましくは、実行時変換プロセスが使用されるが、その理由は、その柔軟性にある（コンパイルされた解は、任意の与えられた問題のために必要とされる仕事に最大限に適合する計算資源を動的に割り当てることができない）。一方、スケーリングは、ノードのグループを（例えば、ポイントツーポイント通信を介してまたは並列データ動作速度を介して）結合させる実効帯域幅の関数である。
（アルゴリズム的データ動作の無い外部コンテキスト（ＥＣＮＡＤＡ）カテゴリー）
一定の論理的及び数学的問題がこのカテゴリーに属する。定義により、ＥＣＮＡＤＡカテゴリーは、与えられた論理的又は数学的問題について達成されるべき最終作業が他のアルゴリズムに内在していて、変換されるデータが集団的アルゴリズムの一部分としてデータを動かすことを必要としないカテゴリーである。ＥＣＮＡＤＡカテゴリーのアルゴリズムの例はアダマール変換である。一実施形態では、ＥＣＮＡＤＡカテゴリーのアルゴリズムはＩＣＮＡＤＭカテゴリーのアルゴリズムのように扱われる。
（アルゴリズム的データ動作のある外部コンテキスト（ＥＣＡＤＭ）カテゴリー）
多くの論理的及び数学的問題がこのカテゴリーに属する。定義により、ＥＣＡＤＭカテゴリーは、与えられた論理的又は数学的問題について達成されるべき最終作業が他のアルゴリズムに内在していて基本アルゴリズムがデータ動作を必要とするカテゴリーである。
ＥＣＡＤＭカテゴリーのアルゴリズムについての任意の２Ｄデータセットがｍ個のロー及びｎ個のコラムのアレイとして図６４に例示されている。図６４の２Ｄデータセットは、例えば、デジタルカメラにより作られるようなｍロー及びｎコラムのピクセルから成るビットマップイメージである。この様なアレイで二次元ＦＦＴを計算するとき、それは２段階で行われる。始めに、入力データアレイの第１次元（ｍ個のロー又はｎ個のコラム）について１次元（１Ｄ）ＦＦＴが計算されて中間アレイを作る。第２に、その中間アレイの第２次元について１ＤのＦＦＴが計算されて最終結果を作る。ロー演算及びコラム演算は分離可能であるので、ロー或いはコラムのどちらが先に処理されるかということは重要ではない。
【００８０】
次に、ｍ個のローはＰ個の並列処理ノードに分配される。ノードに割り当てられるローは、ローインデックスと称される開始ローと、ローカウントとにより定められる。ローはノード間で分割されないので、ローカウントは整数に限定される。分配は、同量のローがノード１からＰ−１までに割り当てられ、残りのローがノードＰに割り当てられるように実行される。残りは、ローの数がＰ個のノードに均等に分けられない場合を処理するために設けられる。ローカウントとノードの数との積と該残りとの和がローの総数に等しくなるように、ローカウントよりは小さい最大の整数として該残りを計算することができる。この調整は、均等なロー分配を達成する。
【００８１】
ｍ個のローをＰ個のノードに分配するこのステップが図６５に示されている。プロセッサノード１からＰ−１までにはＭｒ個のローが割り当てられ、プロセッサノードＰには残りのＲｒ個のローが割り当てられる。各プロセッサノードｉには、（ｉ−１）とローカウントＭｒとの積に等しいローインデックスＩＲｉが割り当てられる。このローインデックスへのノード番号のマッピングは、データ分割を単純且つ効率的にする。
【００８２】
次のステップは、ｎ個のコラムをＰ個の並列処理ノードに均等に分配する。再び、コラムはノード間で分割されないので、分配は整数に限定される。コラム割り当てはローについての割り当てと同様に行われる。ｎ個のコラムをＰ個のノードに分配するこのステップが図６６に示されている。プロセッサノード１からＰ−１までにＭｃ個のコラムが割り当てられ、プロセッサノードＰには残りのＲｃ個のコラムが割り当てられる。各プロセッサノードｉには、コラムカウントＭｃの（ｉ−１）倍に等しいローインデックスＩＲｉが割り当てられる。
【００８３】
ローインデックス及びコラムインデックス、ローカウント及びコラムカウント、及びノード番号の間の関係が図６７の７ノードＨＣ１００Ａの文脈で更に例示され、これは１０２４個のロー及び７００個のコラムから成るイメージビットマップアレイをＨＣ１００Ａに分配する。この場合、ローカウントＭｒは１４７であり、ロー残りＲｒは１４２である。処理ノード１にはロー１から１４７までが割り当てられ、処理ノード２にはロー１４８から２９４までが割り当てられ、以降は処理ノード７まで同様であり、処理ノード７には残りのロー８８３から１０２４までが割り当てられる。チェックとして、６の１４７倍プラス１４２は総ローカウント１０２４に等しい。コラムカウントＭｃは１００であり、コ
ラム残りＲｃは０であり、その理由は、コラムの数が処理ノードの数で割り切れることにある。処理ノード１にはコラム１から１００までが割り当てられ、処理ノード２にはコラム１０１から２００までが割り当てられ、以降は処理ノード７まで同様であり、この処理ノード７にはコラム６０１から７００までが割り当てられる。
【００８４】
ホームノード１１０Ａは、図６との関係で前述したデータ分割を実行する。コマンド及びデータ分割（この場合には２Ｄ  ＦＦＴ）を記述するメッセージは処理ノード１１２，１１４，１１６，１１８，１２０，１２２，１２４（即ち、それぞれ、処理ノード１−７）に送られる。これらのメッセージは、図６７に矢で示されているように送られる。処理ノード１−７が自分達のコマンドメッセージを受け取ると、各処理ノードはホームノード１１０Ａがデータを送るのを待つ。データは、ＨＣ１００Ａ内の全ての処理ノードがデータを同時に受け取るように放送される。どのノードもデータセット全体を受け取るが、このことは、特にアレイ内に多数の並列処理ノードがある場合、各々のノードに別々のメッセージとデータセットの一部分とだけを送るより遥かに効率的である。
【００８５】
ノードは、自分のデータを受け取ると、他のノードとは無関係にコラムについて１Ｄ  ＦＦＴを続行する。コラムＦＦＴの結果が準備できると、それらは上流のホームノード１１０Ａに蓄積され、集塊化される。その後、ホームノード１１０Ａは、ローについて１Ｄ
ＦＦＴを計算するために中間結果を処理ノードに放送する。次に個々のコラム結果は上流のホームノード１１０Ａに蓄積され、集塊化されて最終結果にされ、プロセスを終了する。従って、ＨＣ１００Ａを通してのデータ分配は任意のサイズの２Ｄデータセットに単純に且つ効率良く対処することができる。同様に、２Ｄ  ＦＦＴが任意のグループのプロセッサのために並列化される。
【００８６】
従って、これらの手法は、このカテゴリーのアルゴリズムで通常見られる交差通信の難点を軽減する。例えば次のアルゴリズム：  Ｉｍａｇｅｏｕｔｐｕｔ＝２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ（Ｋｅｒｎｅｌ，（１Ｄ−ＦＦＴｃｏｌｕｍｎｓ（ＴＲＡＮＳＬＡＴＥｆｆｔ−Ｔｒａｎｓｐｏｓｅ（１Ｄ−ＦＦＴｒｏｗ（ｉｍａｇｅｉｎｐｕｔ）））））を考察する。ここでｉｍａｇｅｉｎｐｕｔは基本入力イメージであり、１Ｄ−ＦＦＴｃｏｌｕｍｎはコラム形１Ｄ  ＦＦＴであり、１Ｄ−ＦＦＴｒｏｗはロー形１Ｄ  ＦＦＴであり、Ｋｅｒｎｅｌは畳み込みカーネル（例えば、入力イメージに見出される物体）であり、２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮは畳み込みアルゴリズムであり、Ｉｍａｇｅｏｕｔｐｕｔは出力イメージであり、ＴＲＡＮＳＬＡＴＥｆｆｔ−ＴｒａｎｓｐｏｓｅはＦＦＴのためのマトリクス転置である。達成されるべき作業は２Ｄ−ＦＦＴの一部分ではないので（即ち、該アルゴリズムはデータを周波数領域に変換する）、関連する関数の作業単位を使って交差通信を制限することができる。この例では作業単位は２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮのカーネルパラメータによって定められる。２Ｄ−ＦＦＴのノード毎の最低周波数がカーネルパラメータの最低周波数の少なくとも２倍であれば、それは、プロセッサ間の交差通信無しでｉｍａｇｅｉｎｐｕｔをそのサイズに分割できるところの最小サイズを定める。このことは、ＴＲＡＮＳＬＡＴＥｆｆｔ−Ｔｒａｎｓｐｏｓｅ関数が自分のマトリクス転置を実行するときに低周波数データ（交差通信の目的）を維持する必要が無いので発生することである。２Ｄ−ＦＦＴのこの解釈では、ＦＦＴは３つの部分：即ち１Ｄ−ＦＦＴｒｏｗ、ＴＲＡＮＳＬＡＴＥｆｆｔ−Ｔｒａｎｓｐｏｓｅ、及び１Ｄ−ＦＦＴｃｏｌｕｍｎ、に分解される。この関数分解は、所要の転置の挿入に配慮するが、その関数がデータをプロセッサ間で動かすべきか否か決定することを可能にする。従って、下記のＡＬＧ（Ａ）からＡＬＧ（Ｂ）などのアルゴリズム間での変換が自動的に行われて良い。
【００８７】
ＡＬＧ（Ａ）＝Ｉｍａｇｅｏｕｔｐｕｔ＝２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ（Ｋｅｒｎｅｌ，（２Ｄ−ＦＦＴｃｏｌｕｍｎｓ（ｉｍａｇｅｉｎｐｕｔ）））であり、ここでｉｍａｇｅｉｎｐｕｔは基本入力イメージであり、１Ｄ−ＦＦＴｃｏｌｕｍｎｓはコラム形１Ｄ
ＦＦＴであり、１Ｄ−ＦＦＴｒｏｗはロー形１Ｄ  ＦＦＴであり、Ｋｅｒｎｅｌは畳み込みカーネル（例えば、その位置を突き止めるべき物体）であり、２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮは畳み込みアルゴリズムであり、Ｉｍａｇｅｏｕｔｐｕｔ（ＡＬＧ（Ａ））は出力イメージである。ＡＬＧ（Ｂ）＝Ｉｍａｇｅｏｕｔｐｕｔ＝２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮ（Ｋｅｒｎｅｌ，（１Ｄ−ＦＦＴｃｏｌｕｍｎｓ（ＴＲＡＮＳＬＡＴＥｆｆｔ−Ｔｒａｎｓｐｏｓｅ（１Ｄ−ＦＦＴｒｏｗ（ｉｍａｇｅｉｎｐｕｔ）））））であり、ここでｉｍａｇｅｉｎｐｕｔは基本入力イメージであり、１Ｄ−ＦＦＴｃｏｌｕｍｎｓはコラム形１Ｄ  ＦＦＴであり、１Ｄ−ＦＦＴｒｏはロー形１Ｄ  ＦＦＴであり、Ｋｅｒｎｅｌは畳み込みカーネル（例えばその位置を突き止めるべき物体）であり、２Ｄ−ＣＯＮＶＯＬＵＴＩＯＮは畳み込みアルゴリズムであり、Ｉｍａｇｅｏｕｔｐｕｔ（ＡＬＧ（Ｂ））は出力イメージであり、ＴＲＡＮＳＬＡＴＥｆｆｔ−ＴｒａｎｓｐｏｓｅはＦＦＴのためのマトリクス転置である。
【００８８】
ＥＣＡＤＭカテゴリーのアルゴリズムは、コンパイラー又は実行時変換プロセスを用いて並列化することができる。スケーリングは、主として、交差通信を拘束する仕事の関数である。好ましくは、実行時変換プロセスが使用されるが、その理由は、その柔軟性にある（コンパイルされた解は、任意の与えられた問題のために必要とされる仕事に最大限に適合する計算資源を動的に割り当てることができない）。
【００８９】
ＩＣＮＡＤＭ、ＩＣＡＤＭ、ＥＣＮＡＤＭ及びＥＣＡＤＭカテゴリー処理についての以上の記述は、ＨＣを含む並列処理アーキテクチャーを通してのアルゴリズムの並列処理を高めるために用いることのできる記述である。
（ＨＣを用いる大規模クラスターコンピュータネットワークスイッチ）
ＨＣは、従来技術に比べて一定の利点を提供する。例を挙げると、ＨＣは共有メモリークラスターのスイッチングネットワークのバックプレーンにより課されるクラスターサイズに関する制約を減少させる。二次元、レベル３のＨＣ１００Ｂの論理形が図１３に示されている。ＨＣ１００Ｂは例証的に“ストリップ”という符号が付されているセクションに分割されている。各ストリップは接続に関しては他のストリップから独立している。この独立性は、集塊化まで、処理全体を通じて保たれる。集塊化時には図１４に示されているように、ストリップ間で通信が行われる可能性がある。より具体的には、問題のデータセットを分配するとき、ホームノード１１０Ｂはトップレベルのノード１１２，１２０，１２４とだけ通信し、これらは各々のストリップの他の処理ノードと通信する。しかし、集塊化時には、図１４に示されているように、ストリップ間及びトップレベルのノード１１２，１２０，１２４間でノード間通信が単一方向に発生する可能性がある。従って、ＨＣ１００Ｂのストリップは、図１５に更に示されているように、スイッチトポロジーに関して分離可能である。
【００９０】
図１５において、ホームノード１１０Ｂとトップのノード１１２，１２０，１２４との間の通信のためにルータ２００が使用され、このストリップ間通信は問題分配及び／又は集塊化のときに行われて良い。ストリップ内でのノード接続性は、該ストリップ内のノードの数を考慮するスイッチを使用することによって達成される。図１５において、スイッチ２０２はストリップ１内のノード１１２，１１４，１１６，１１８間の物理的接続（即ち、ストリップ間通信）を提供し、スイッチ２０４はストリップ２内のノード１２０，１２２間の物理的接続（即ち、ストリップ間通信）を提供する。ストリップ３は、ルータ２００に接続されたノード１２４を１つだけ有するので、付加的なスイッチは不要である。ルータ２００のレベルでは相互作用は非常に僅かしか発生しないので、それは性能に無視できる程度の影響しか及ぼさない。この様にＨＣ１００Ｂのトポロジーは僅かなコストで極めて大きなクラスターに配慮する。
【００９１】
スイッチ２０２又は２０４等のスイッチは、相互に連結できるノードの数に制限を有する。例えば、ヒューレットパッカードＨＰ２５２４スイッチは２４個のポートを有し、相互に連結された１６に及ぶスイッチを持つことができる。従って、このスイッチングアレイで利用できるスイッチングポートの総数は３８４である。従って、スイッチングアレイ内の自分のスイッチとしてＨＰ２５２４を利用するストリップは、例えば３８４個に及ぶノードを接続することができる。ルータ２００に適するルータの例はヒューレットパッカードＨＤ９３０８ｍであり、これは合計１６８個のポートを有する。ＨＤ９３０８ｍをルータ２００として用いれば（１６８ｘ３８４）６４，５１２個のノードを相互に接続させることができる。
【００９２】
ＨＣ１００Ｂのトポロジーは、前記の３８４ノード境界などの境界条件で動作し得るように非常に大きなストリップを分解するように改造可能である。具体的には、一実施形態では、ストリップ内のノード（プロセッサ）の数は次のこと、即ち（ａ）ストリップは少なくとも１つのＨＣを有し、且つ（ｂ）ＨＣはＨＣの総数プラス残りの関数から成る、に従って制限されて良い。即ち、Ｈ＝Ｈ（ｘ）＋Ｈ（ｙ）＋・・・＋Ｒ（ｚ）であり、ここでＨ（）はＨより大きくないサイズを有するＨＣであり、Ｒ（）は０個、１個、または２個のノードである。従って、図１６に示されているように、大きなカスケードストリップを１つのスイッチを各々有する小さな複数のグループに分解することができる。ハワードカスケードをその成分カスケードに分解し、スイッチングネットワークを適切に関連付けることによって、私たちはスイッチの数を最小限にしながら高スイッチング速度を維持する。
（カスケージングコンピュータにおける複数の拡張チャネルの使用）
例えば図６のＨＣ１００などの、ＨＣとして接続されたコンピュータは、問題セット拡張の速度を高めるために複数の並列インターフェースを利用することができる。ＨＣについての一般的拡張速度は次の：
Ｎ１＝２ｔ−１                            （方程式１）
により表現することができ、ここでＮは拡張に用いられるノードの数であり、ｔは拡張に用いられる時間単位の数である。見て分かるように、この拡張速度は次の数のノード即ち｛０，１，３，７，１５，３１，６３，１２７，２５５，５１１，１０２３、・・・｝を提供し、これはベース２の幾何学的拡張である。方程式１を：
Ｎ２＝ｐ＊（ｐ＋１）ｔ−ｐ                    （方程式２）
に一般化することができ、ここでＮは拡張に用いられるノードの数であり、ｔは拡張に用いられる時間単位の数であり、ｐは拡張の並列チャネルの数である。
【００９３】
拡張の並列チャネルは、ノードあたりの、同時に動作することのできるバス接続（ネットワークカード、プロセッサ等）の数と一致する。ネットワークされたコンピュータの場合、これはネットワークインターフェースカード（ＮＩＣ）とパラレルバスとの両方を意味する。単一プロセッサコンピュータ（これは内部バスを１つだけ有する）については、拡張のチャネルの数は１であって方程式１が適用される。ノードあたりに２つのプロセッサがある場合、下記が適用される（方程式２に従って）。
【００９４】
Ｎ３＝２（２＋１）ｔ−２                      （方程式３）
ここでＮは拡張に用いられるノードの数であり、ｔは拡張に用いられる時間単位の数である。下の表６は２つの並列拡張チャネルについての拡張速度をノード数で明らかにしている。
【００９５】
【表６】
0005487128.tif 000008
方程式２の計算を方程式３と比べると方程式４が生じる：
Ｒ＝Ｎ１／Ｎ３                            （方程式４）
ここでＲは拡張のノードの数の比であり、Ｎ１は方程式１を用いる拡張のノードの数であり、Ｎ３は方程式３を用いる拡張のノードの数である。表７は、この様な拡張の比を明らかにする。
【００９６】
【表７】
0005487128.tif 000009
表７は、第２拡張と比べて、第１拡張が四分の一の拡張効率を提供することを例証している。前述のことは、ＨＣを用いて拡張の次元数を高めればクラスター効率が更に向上することも例証している。
【００９７】
図３１及び図３２は、並列チャネル通信のための代表的ハードウェア構成を例証してお
り、拡張の各並列チャネルはコンピュータプロセッサと通信チャネルとから成っている。図３１は、単一の通信チャネル４２４を介して第２プロセッサ４２２に接続された第１プロセッサ４２０を示している。一方、図３２に示されているように、拡張の複数の並列チャネルは複数のコンピュータプロセッサと複数の通信チャネルとから成っている。処理ノード１１２のプロセッサ４３０及びプロセッサ４３２は、２つの通信チャネル４３８及び４４０により処理ノード１１４のプロセッサ４３４及びプロセッサ４３６にそれぞれ接続されている。他の並列チャネル構成が後に続き、ＨＣがデータを希望どおりに効率よく移動させるように実現可能である。
（ＨＣ及びノード数）
ｎ次元ＨＣは各拡張レベルについて固定された数の処理ノードを消費することができる。例えば、２次元ＨＣは、表８により明らかにされる数のノードを消費することができる。
【００９８】
【表８】
0005487128.tif 000010
２次元ＨＣで例えば４，５、または６個のノードを消費できるためには、以下で述べるように、ＨＣについての上記のノード拡張アルゴリズムへの拡張を使用することができる。
【００９９】
より具体的には、時間に関しての拡張を、以下で定義する集合で示すことができる。ＨＣの自然なカスケード周波数は集合１：｛１，３，７，１５，３１、・・・、２ｔ−１｝の拡張速度であり、ここでｔは時間単位の数である。より一般的な場合には、集合１は集合２：｛ｄ１−１、ｄ２−１、ｄ３−１、ｄｔ−１｝の形を取り、ここでｄは拡張の次元の数（＝（ｐ＋１））であり、ｐは拡張の並列チャネルの数であり、ｔは時間単位の数である。集合２の要素の間にある拡張数を得るのが有益である。例えば集合３：｛ｄ１−１＋１、ｄ１−１＋２、ｄ１−１＋３、・・・、ｄ２−２｝を考察する。ここでｄは拡張の次元の数（＝ｐ＋１）であり、ｐは拡張の並列チャネルの数である。集合３は、第１及び第２の自然拡張項の間に存する値の集合をより具体的に示す。集合１の場合、これは集合４：｛２｝に変換する。中間数のノードについての一般的集合は集合５：｛ｄｔ−１＋１、ｄｔ−１＋２、ｄｔ−１＋３、・・・、ｄｔ−１＋ｔ、ｄ（ｔ＋１）−２｝に与えられ、ここでｄは拡張の次元の数（＝ｐ＋１）であり、ｐは拡張の並列チャネルの数であり、ｔは時間単位の数である。一般的ＨＣ構成級数は以下に与えられる：
【０１００】
【数２】
0005487128.tif 000011
見て分かるように、展開の各項は全ての前の項の和に等しい。各項がカスケードストリップに対応するので、２番目に高い項から開始して付加的なノードを追加して全ての空の潜在的スロットが満たされるまで続けることにより、或いは余分のノードをストリップに均等に分配することによって、ＨＣの釣り合いが取られる。カスケードストリップにノードを均等に分配することによってＨＣの釣り合いを保つことは、表９及び表１０において例証されているように、ノードにレベル分配することによって達成される：
【０１０１】
【表９】
0005487128.tif 000012
【０１０２】
【表１０】
0005487128.tif 000013
各々のストリップ境界とレベルとは時間単位を表わし、ストリップ内の１つのレベルにおけるノードの位置はそのタイムスロットで行われる可能性のある分配を表わすので、表１０に追加のノード８を付け加えると、追加の時間単位のために（表９に比べて）総処理時間が増大する。追加のノード８が一番上のレベルに付け加えられている表１０とは異なって、表１１は、追加の時間コスト無しで追加のノードをどのように付け加えられるかを示している。
【０１０３】
【表１１】
0005487128.tif 000014
ＨＣを均衡させる一つの方法は、ノードが時間に関して整列することを保証するためにノードスペースをレベルにより充填することである。表１２は、表１１のＨＣと関連してノードを付け加える１つの手法を例示している：
【０１０４】
【表１２】
0005487128.tif 000015
表１２において同じタイプ（それぞれＡ，Ｂ，Ｃ，又はＤ）で示されているいずれのノードも同じタイプの他のいずれのノードにも配置順序に関して取って代わることができる。ノードが時間効率よく付け加えられることを保証することにより、ＨＣシステムオーバーヘッドが低減される。
（集塊化通信経路を前もって作ること）
通常、従来技術では、複数のネットワークインターフェースカード（“ＮＩＣ”）を使用する実施形態は、ＮＩＣがデバイスドライバーレベルで接着されることを必要とする。このことは、既製のデバイスドライバーのアップグレードを利用できなくし、ＮＩＣを相互に無関係に使用して複数の通信チャネルを作り出す能力を除去する。ソフトウェアアプリケーションレベルがＮＩＣを個別に制御することを可能にすることによって、複数の通信チャネルを作り出していろいろに使用することができ、大きな通信柔軟性を与えることができる。例えば、通信帯域幅を広げるために２つのノード間に複数の通信チャネルを作ることができ、或いは１つのノードが他の多数のノードと同時に通信できるように通信チャネルを個別に使用することができる。各並列通信チャネルのために物理的に別々のスイッチネットワークを持つ必要があることの結果として、他の利点が得られる。この要件は、実現される並列通信チャネルの数と同等のチャネル冗長性を提供する。図６８は、それぞれ２つのＮＩＣ２４４ａ，２４４ｂ，２４４ｃ及び２４４ｄを各々有する２つの処理ノード１１２及び１１４の接続性の例を示している。各並列通信チャネルは、独立しているネットワークスイッチ２６０及び２６２を有する。処理ノード１１２は、処理ノード１１４との２つの可能な通信チャネル、即ちａ）ネットワークスイッチ２６０と接続し、従って処理ノード１１４内のＮＩＣ２４４ｃと接続するＮＩＣ２４４ａを使用すること、及びｂ）ネットワークスイッチ２６２と接続し、従って処理ノード１１４内のＮＩＣ２４４ｄと接続するＮＩＣ２４４ｂを使用すること、を有する。クラスター内の各ノードが同数のＮＩＣを有し、従って同数の並列通信チャネルを有し、これにより最上の通信スループットを得るために全てのスイッチネットワークとの接続を有することが好ましいが、必ずしもそうでなくても良い。
【０１０５】
図６９は、この例において複数の通信チャネル４４８及び４４８’を処理ノード１１２でどのように具体化できるかを示している。ソフトウェアアプリケーション（例えば、図５の制御ソフトウェア９４）は、複数のスレッドから成ることができる。各スレッドは、他のノードとの通信を容易にするために多チャネルソフトウェアＡＰＩ４４６を使用する。ＡＰＩ４４６は、チャネル資源プール４４７内の通信チャネル４４８及び４４８’の使用を調整するスレッド保全サブルーチンのライブラリーから成る。この例では、各チャネル４４８，４４８’は、特定のネットワークインターフェースデバイスドライバー４５２及び４５２’と通信するためにコマンド／制御スレッド４５０，４５０’をそれぞれ利用する。コマンド／制御スレッド４５０，４５０’は、特定の通信プロトコルを扱うためにネットワークインターフェースデバイスドライバー４５２，４５２’をそれぞれ使用する。ＡＰＩ４４６は、アプリケーションスレッド４４２及び４４４を特定のネットワークハードウェア及びプロトコル情報から切り離す。ＡＰＩ４４６は、アプリケーションスレッドが通信のために１つ以上のチャネルを使用することを可能にし、必要に応じて選択されたチャネルでのデータ分配及び復元を管理する。ＡＰＩ４４６は、チャネルプロトコルを扱い、チャネル故障を検出して回復することもできる。
【０１０６】
図７０は、ＨＣＡＳで利用されたときに付加的な効率を得るために複数の通信チャネルをどのように使えるかを例示している。この例では、ＨＣ１００は、１つのホームノード１１０と７つの処理ノード１１２，１１４，１１６，１１８，１２０，１２２，１２４及び１２６とから成る。各処理ノード１１２，１１４，１１６，１１８，１２０，１２２，１２４及び１２６は２つの並列通信チャネルを有する。１つのチャネルはＨＣ１００での問題拡張のために使われ、他方のチャネルはＨＣ１００での集塊化のために使われる。図７０の接続線は、ノード間で渡されるメッセージを表わす。線のスタイルは、キー４５６で示されているように、その間にメッセージが渡されるところの時間単位を示す。ホームノード１１０は、時間単位１の間に処理ノード１１２に処理要求を送る。時間単位２の間に、ホームノード１１０は処理要求を処理ノード１２０に送る。処理ノード１１２は、処理要求を処理ノード１１４に送り、その第２通信チャネルをホームノード１１０に向け、これにより集塊化のための用意が整う。時間単位３の間、ホームノード１１０は処理要求を処理ノード１２４に送る。処理ノード１１２は、その第１通信チャネルを使って、処理要求を処理ノード１１８に送る。処理ノード１１４は、その第１通信チャネルを使って処理要求を処理ノード１１６に送り、その第２通信チャネルを処理ノード１１４に向け、これにより集塊化のための用意が整う。処理ノード１２０は、その第１通信チャネルを使って処理要求を処理ノード１２２に送り、その第２通信チャネルを、処理ノード１１２に向け、これにより集塊化のための用意が整う。時間単位４の間、処理ノード３はその第２通信チャネルを処理ノード１１４に向け、これにより集塊化のための用意が整う。処理ノード１１８は、その第２通信チャネルを処理ノード１１２に向け、これにより集塊化のための用意が整う。処理ノード１１２は、その第２通信チャネルを処理ノード１２０に向け、
これにより集塊化のための用意が整う。処理ノード１２４は、その第２通信チャネルを処理ノード１２０に向け、これにより集塊化のための用意が整う。
【０１０７】
図示されているように、３つの時間単位の後に処理要求は７個の処理ノードの全てに送られている。時間単位４の間、処理ノードは、もしデータを待っているならば、データ放送を受け取るように自分達の第１通信チャネルを構成する。４時間単位後、データ集塊化通信路全体が確立され、これにより、処理ノードで通信チャネルが１つだけ利用可能である場合にデータ集塊化の前に通常費やされるチャネル構成オーバーヘッドが節約される。（ホームノードとしての処理ノード）
もし各処理ノードがホームノードスイッチネットワークに関連する付加的なＮＩＣを含んでいれば、ホームノードの代わりに処理ノードを使うことができる。例えば、もしホームノードが故障したならば、処理ノード又は他のホームノードが通信の欠如を検出する。一実施形態では、最低番号の通信ホームノードが、アクティブな処理ノードソフトウェアを終了させて遠隔手順呼び出しを通して新しいホームノードソフトウェアを始動させることによって、自分の処理ノードのうちの１つを新しいホームノードとして再構成するように選択する。故障したホームノードに割り当てられていた処理ノードは新しいホームノードに割り当て直され、処理が続行される。このことについて、図１７、図２０−図２４と関連して更に論じる。
（カスケードクラスターシステムにおける複数ホームノード）
ＨＣは、協力して動作する複数のホームノードを持つことができる。その様なＨＣは、更に故障したホームノードの検出及び軽減を自動化することができる。具体的には、ＨＣＡＳ内の各ＨＣクラスターは、ノードが脱落した場合に人の介在無しに、自分自身を再構成することができる。後継のホームノードは故障したノードと同様に動作するので、ＨＣは並列処理のために十分に機能する。更に、複数のホームノードは、複数のリモートホストによるアクセスを容易にする。
【０１０８】
同時に処理ノードを割り当てる複数のホームノードを持つために、ホームノードはデータを共有する。図１７は、１つのＨＣ１００Ｃにおける複数のゲートウェイノードのための通信路を示す。図１７は、例として、３つのホームノード１１０Ｃ、２２４，２２６を伴う９個の処理ノード１１２，１１４，１１６，１１８，１２０，１２２，１２４，１２６，１２８を有する。各ホームノードは他のホームノードの各々と通信することができる。システムスタートアップ時に、各ホームノードは自分が責任を持つ処理ノードのリストを有し、このことは、図１７では処理ノードスイッチネットワーク２２０と処理ノードとの間の通信ライン上でホームノードを特定することによって示されている。例えば、処理ノード１１８，１２０，１２２は、同じクラスターネットワークの一部分としてのホームノード２２４の制御下にある。表１３は、ＨＣ１００Ｃの全ての関連を明らかにする。
【０１０９】
ホームノード１１０Ｃ、２２４，２２６のいずれかが追加の処理ノードを必要とするならば、そのノードは、他のホームノードを求めて処理ノードのリストを調べて手空きのノードがあるか無いか調べ、スイッチ２２０はその後、新しい処理ノードを要求側ホームノードの制御下に置くために再構成を行う。他の実施形態では、処理パワーを必要としているホームノードは、追加の処理ノードを求める要求を他のホームノードの各々に放送することができ、これらのノードは、応答をし、そしてもし手空きの処理ノードが存在するならば、ＨＣ１００Ｃは再構成を行って特定のホームノードのために処理を行うノードを調整する。
【０１１０】
【表１３】
0005487128.tif 000016
ＨＣ１００Ｃの１つの動作例（図１７）では、ホームノード１（１１０Ｃ）及びホームノード２（２２４）はアイドル状態でホームノード３（２２６）が７個の処理ノードを必要としている。ホームノード３は、更に４個の処理ノードを求める要求を単一のマルチキャストメッセージでホームノード２及びホームノード１の両方に発する。その要求は、そのメッセージによりアドレス指定されるホームノードの総数も含んでいる。ホームノード１がそのマルチキャストメッセージを受け取って、アドレス指定されているホームノードの総数が２であると判定すると、ホームノード１は、要求されたノードの総数を該メッセージによりアドレス指定されたホームノードの総数で割ることによって２つの手空き処理ノードを返すべきであることを計算し、処理ノード１及び処理ノード２を特定する返送メッセージを送る。ホームノード２は、該マルチキャストメッセージを受け取ると、処理ノード４及び５を特定する返送メッセージを送る。
【０１１１】
ＨＣ１００Ｃの他の動作例では、ホームノード３は追加の処理ノードを１つだけ必要とする。ホームノード３は、１つの処理ノードを求めるマルチキャストメッセージをホームノード１及びホームノード２に対して発する。そのメッセージは、そのマルチキャストメッセージによりアドレス指定されるホームノードの総数も含んでいる。ホームノード１は、このマルチキャストメッセージを受け取ると、処理ノード１だけを特定する返送メッセージを送るが、その理由は、それが最低の番号を付されたホームノードであって且つ該要求が単一の処理ノードを求める要求だったことにある。ホームノード２は、該マルチキャストメッセージを受け取ると、もっと低い番号を持ったホームノードが該要求を満たしていることを認めるので、返送メッセージをホームノード３に送る必要はない。
【０１１２】
図１８は、ホームノード１１０Ｄについての一ＮＩＣ構成を示している。ホームノード１１０Ｄは２つのネットワークインターフェースカードＮＩＣ２４０及びＮＩＣ２４２を有する。ＮＩＣ２４０は、図１７の処理ノードスイッチネットワーク２２０に接続され、ＮＩＣ２４２は図１７のホームノードスイッチネットワーク２２２に接続されている。図１９は、ＮＩＣ構成の、処理ノード１１２と関連する別の接続を示している。処理ノード１１２は、処理ノードスイッチネットワーク２２０に接続された単一のネットワークインターフェースカードＮＩＣ２４４を有する。ネットワーク接続に関しての図１８のホームノード構成と図１９の処理ノード構成との１つの違いは、処理ノード１１２がホームノードスイッチネットワーク２２２に接続されたＮＩＣを持っていないことである。ホームノード及び処理ノードは種々のソフトウェアを包含するが、遠隔手順呼び出し（“ＲＰＣ”）を使ってノードのソフトウェア構成を変更することができる。従って、処理ノード１１２は、ホームノードスイッチネットワーク２２２に接続された第２のネットワークインターフェースカードを包含していれば、ＲＰＣによりホームノードとして動作するように再構成され得る。
（クラスター化されたコンピュータにおいてＩ／Ｏアクセスを減少させるオーバーラップデータの使用）
一実施形態では、ＨＣは従来技術の共有メモリークラスターではありふれている多数のデータ転送を無くするのに役立ち、その様なＨＣは、従来技術の３％から７％の範囲と比
べて４０％から５５％の範囲の計算効率を提供する。結合転送が低減されている場合、ＨＣ効率は８０％から９５％の範囲内にある。一例では、アルゴリズムはＨＣの２つの処理ノード、即ち処理ノード１及び処理ノード２、で動作する。５ｘ６要素マトリクスは、２つの処理ノードにより並列処理されるように２つの５ｘ３要素マトリクスに分割される。処理ノード１についてのデータが表１４に示され、処理ノード２についてのデータが表１５に示されている。
【０１１３】
【表１４】
0005487128.tif 000017
【０１１４】
【表１５】
0005487128.tif 000018
この例では、処理ノード１と処理ノード２とがデータ項目５，６，１５，１６，２５、及び２６を共有する必要があるということが仮定されている。これらの共有されるデータ項目を処理し転送するためのシーケンスが表１６に示されている。
【０１１５】
【表１６】
0005487128.tif 000019
表１６に見られるように、ＨＣによる処理は、僅か６個の境界データ処理のために１２個のデータ転送／受け取りを生じさせる。（必要なときに共有されるデータを所要のノードに提供するために）共有されるデータが重なり合うように境界データを変更することによって、必要なデータ転送の数が減少する。このことは、処理速度が多数のデータ転送と折衷されるので、重要である。上の例からのデータを用いて、表１７及び１８に示されているように、５ｘ６要素マトリクスは２個の６ｘ３要素マトリクスに分割される。
【０１１６】
【表１７】
0005487128.tif 000020
【０１１７】
【表１８】
0005487128.tif 000021
表１７のコラムａと表１８のコラムｂとは、オーバーラップするデータを表わす。オーバーラップする領域は１次元オーバーラップ領域である。このオーバーラップ領域は、データを転送する現在の必要無しにオーバーラップとして扱われる。ＨＣにおける処理ノード１及び処理ノード２の、結果としての処理シーケンスは表１９に示されている。
【０１１８】
【表１９】
0005487128.tif 000022
比較により、並列活動の数を考察する。オーバーラップ領域がある場合、処理ノード１及び処理ノード２はデータを並列に処理する。従って、６個の時間単位が消費される。データがオーバーラップしていない場合、データが処理ノード間で転送される毎に処理が逐次化され、従って１２個の時間単位が消費される（データ転送及びデータ処理が共に１個の時間単位を消費すると仮定して）。この効果は、オーバーラップする次元が多数あるときには、悪化する。例えば、表２０は、９個の処理ノードに分配される９ｘ１５要素マトリクスを示しており、各ノードについてのデータ項目間にオーバーラップがある。
【０１１９】
【表２０】
0005487128.tif 000023
表２０のアンダーラインが付されているデータ項目で分かるように、そのデータセットを有する処理ノードはオーバーラップ領域を含む（従って２次元オーバーラップを表わす）２次元マトリクスの全ての面を有する。これを１次元からＮ次元に類似的に拡張することができる。このオーバーラップ方法は、ノード間で連続的にデータを共有するのと比べて、クラスター転送のオーバーヘッドを減少させ、問題解決時の別々のプロセッサの効率的使用に配慮している。
（処理ノードのドロップアウトの検出及び取り替え）
前述したように、ＨＣは、働いていない処理ノードを検出して、その働いていない処理ノードのための関連作業を人間の介在無しで他の処理ノードに割り当て直すように構成することができる。従来技術のクラスターは、故障したノードを検出すること及びそれを回復させることの両方に大きな困難を有し、この困難は、コンピュータノードを問題にどのように割り当てるかということの関数である。通常、（例えば図１−図４に示されているように）従来技術ではリモートホスト又はクラスターの外部に存する他のコンピュータは、クラスターで動作するべきアプリケーションコードをコンパイルする。当該技術分野で知られているＭＰＩ又はＰＶＭなどのコンパイル時並列処理通信ツールが使用され、これにより処理ノード間の通信関係がコンパイル時に確立される。処理ノード関係がコンパイル時に形成されるときには、他の機能している処理ノードへの並列問題の実行時再割り当てを確立するのは困難である。ジョブを処理している過程でノードがクラスター内の他のノードとの通信を失ったならば、この無通信状態は、特殊化されたハードウェア及び／又は人間の介在無しでは訂正されない。
【０１２０】
一方、ＨＣの一実施形態では、ノード通信はコンパイル時にではなくて実行時に決定される。更に、ＨＣの幾何学的性質は、ジョブの持続時間にわたる実行時ノード通信関係を固定する。このことは、処理ノード通信故障を検出すること及び問題セットを他の処理ノードに割り当て直し、実行時にノード故障について訂正を行うことを可能にする。
【０１２１】
図２０は、カスケードに構成された７つの処理ノード１１２，１１４，１１６，１１８，１２０，１２２及び１２４を有する１つのＨＣ１００Ｅと、８番目の、割り当てられていない処理ノード１２６とを例示している。ホームノード１１０Ｅは、通常処理時に処理ノード１１２，１１４，１１６，１１８，１２０，１２２及び１２４と通信する。しかし、もしホームノード１１０Ｅが例えば適切な回数の再試行後に処理ノード１１２と連絡を取れなかったならば、ホームノード１１０Ｅは処理ノード１１２のアドレスを“通信していない”リストに載せ、ＨＣ１００Ｅ内でのその位置を占めるように他の処理ノードを直ちに割り当てる。図２１は、再構成後のクラスターＨＣ１００Ｅの接続を例示している。この例では、ホームノード１１０Ｅは通信路２５０の故障を検出する。その時ホームノード１１０Ｅはデータ経路２５２を介して処理ノード１２６と通信し、処理ノード１２６にＨＣ１００Ｅ内での自分の位置を知らせる。すると、処理ノード１２６は通信路２５４及び２５６をそれぞれ介して自分の下位ノード（処理ノード１１４及び処理ノード１１８）との通信を確立する。完了すると、ＨＣ１００Ｅは修理されていて、処理ノード１１２の代わりに処理ノード１２６を用いて処理が再開する。
【０１２２】
ネットワーク化されたノードが同じネットワーク上の他のノードと通信しようと試みたが通信できなかったというときには通信プロトコル（例えばＴＣＰ／ＩＰ）はエラーコードを返送するので、無通信は検出可能である。例えば、図２２は、図２０のノードとネットワークスイッチ２６０との物理的接続を示している。もし処理ノード１１２がネットワークスイッチ２６０と最早通信していなければ、ホームノード１１０Ｅは次の利用可能なノード（この例ではノード１２６）を後継者として選択する。ＨＣ１００Ｅの物理的接続トポロジーは、どのノードをカスケード内の何処に置くことをも、問題やオーバーヘッド無しに可能にする。
【０１２３】
他の実施形態に関して、図２３は、処理ノード１１２，１１４，１１６，１１８，１２
０，１２２及び１２４を通じての並列処理が完了していてＨＣ１００Ｆが集塊化された結果をホームノード１１０Ｆに返送するように構成されている状態のＨＣ１００Ｆを例示している。図２４は、処理ノード１１２の故障から生じる自主的エラー回復プロセスを示している。処理ノード１１４は、通信路２８０を介して処理ノード１１２と通信しようと試みると、エラーを受け取る。このとき処理ノード１１４は処理ノード１１２が通信していないことをホームノード１１０Ｆに知らせるために通信路２８２を介してメッセージを処理ノード１１０Ｆに直接送る。ホームノード１１０Ｆは、通信路２８４を用いて、処理ノード１１０が最早通信していないことを確かめる。ホームノード１１０Ｆは、その後、通信路２８６を用いて、次に利用可能な処理ノード（この場合は処理ノード１２６）を割り当てる。処理ノード１２６が処理ノード１１２に取って代わることを可能にするために必要な全ての情報が処理ノード１２６に送られる。ホームノード１１０Ｆは、その後、新しい上位ノード（即ちノード１２６）が存在することを通信路２８８及び２９０をそれぞれ介して処理ノード１１４及び処理ノード１１８に知らせる。処理ノード１１４及び処理ノード１１８は、その後、それぞれの結果を通信路２９２及び２９４をそれぞれ介して処理ノード１２６に送る。すると、処理ノード１２６はその集塊化した結果を通信路２９６を介して上流のホームノード１１０Ｆに送る。
【０１２４】
他の例では、ＨＣ１００Ｇは図２０のＨＣ１００Ｅに類似して構成される。図２５は、処理ノード１１２が処理ノード１１４にアルゴリズム処理要求を落とそうと試みて通信路３００が失敗したときに行われるエラー回復シーケンスを示している。処理ノード１１２は、通信路３０２を介してその故障をホームノード１１０Ｇに知らせる。その後、ホームノード１１０Ｇは、次に利用可能な処理ノード（この例では処理ノード１２６）を選択し、通信路３０４を介して新しいノードのアイデンティティーを処理ノード１１２に知らせる。その後、処理ノード１１２は、通信路３０６を介して処理ノード１２６にＨＣ１００Ｇ内でのその新しい位置を知らせ、元は処理ノード１１４に向けられていたアルゴリズム処理要求を伝える。その後、処理ノード１２６は、通信路３０８を介して処理ノード１１６へのカスケードを継続する。
【０１２５】
他のエラー回復例では、図２６のＨＣ１００Ｈは、結果が集塊化されているときに回復をする。図２６は、処理ノード１１６と処理ノード１１４との間の通信路３２０が故障したときに行われるＨＣ１００Ｈのエラー回復シーケンスを示す。処理ノード１１６は、その故障を通信路３２２を介してホームノード１１０Ｈに知らせる。ホームノード１１０Ｈは通信路３２４を介して次に利用可能な処理ノード（この例では処理ノード１２６）を選択する。その後、ホームノード１１０Ｈは、通信路３２６を介して、新しいノードのアイデンティティーを処理ノード１１６に知らせる。その後、処理ノード１１６は、通信路３２８を介して自分の結果を処理ノード１２６に送る。その後、処理ノード１２６は、通信路３３０を介して自分の集塊化された結果を処理ノード１１２に送る。
【０１２６】
予備の処理ノードが無い場合、ＨＣは現行の処理カスケードを一時停止させ、次の下位カスケードレベルでアルゴリズム処理要求を作り直し、ここで追加の手空き処理ノードを使って処理を再開することができる。この例では、ＨＣ１００Ｅは、ノード１２６が利用できないということが仮定されていることを除いて、図２０と同様に構成されている。図２７は、処理ノード１２０が通信路３４０を介して処理ノード１２２と通信できないときに行われるエラー回復シーケンスを示す。処理ノード１２０は、その故障を通信路３４２を介してホームノード１１０Ｅに知らせる。ホームノード１１０Ｅは、予備の処理ノードが無いと判定して、処理ノード１１２，１２０，１２４での現行のアルゴリズム処理要求の処理を停止させるために通信路３４４を介してコマンドを送る。処理ノード１１２は処理ノード１１４でのアルゴリズム処理を停止させ、これは処理ノード１１６でのアルゴリズム処理を停止させる。ホームノード１１０Ｅは、処理ノード１２２を故障リストに加える。図２８は、ノードのより小さなグループに通信路３６０を介して現行のアルゴリズム処理要求を再送し、３つの処理ノード１１８，１２０及び１２４を割り当てないままにしておく。この様に該アルゴリズム処理要求は人間の介在無しで代替ノードにより完成され、内部クラスターの任意の場所で使用可能となる。
【０１２７】
一実施形態では、ＨＣ内の各ノードは同じ計算能力を持つことができる。リモートホストとホームノードとの間の接続はジョブ処理中開いたままではないので、リモートホストに知らせることを必要とはせずに故障した主ホームノードを切り離して取り替えることができる。図２９は、ＨＣ１００Ｉにおいて予備ノード（ノード３３１）と共有されるリモートホスト３２９から付加的な通信路３８０を介して受け取られる情報を示す。図３０は、更に、主ホームノード１１０Ｉがもし故障すれば（例えば、通信路４００が故障すれば）、次に利用可能な予備ノードが故障したホームノード１１０Ｉに取って代わるべく使用され、この例では、予備の処理ノード３３１がＲＰＣによって再構成されて新しいホームノードになる。
【０１２８】
ＨＣ１００Ｉは、当業者に知られているクライアント−サーバーモデルを利用する必要はなく、従って、リモートホストとの接続は再建されて良い。
（ブラインド関数呼び出しのための潜在関数ＡＰＩ）
ＨＣＡＳは、専有アルゴリズムへの第３者のアクセスを回避するインターフェース方法で構築されて従来技術の１つの問題を克服することができる。図３３は、アプリケーションコード４６０とＨＣＡＳとの間の２つのインターフェースを示す。第１のインターフェ
ースは関数要求インターフェース４７６であり、第２のインターフェースはデータ要求インターフェース４６６である。関数要求インターフェース４７６を通して、アプリケーションコード４６０は複雑なアプリケーションプログラムインターフェース（“ＡＰＩ”）を持たずにパラメータリストで計算集中的アルゴリズムライブラリー９９（図５）の関数を呼び出すことができる。該ＡＰＩを使ってメッセージ作成ソフトウェアを呼び出す前に、テンプレート番号４６８、関数番号４７０、バッファーサイズのデータ定義４７２、及びバッファー４７４が作られる。テンプレート番号４６８は、関数番号４７０により選択される関数（計算集中的アルゴリズムライブラリー９９内の）のためのデータテンプレートを定義する。この情報は、図３４のパラメータ定義ファイル４８２に格納される。パラメータ定義ファイル４８２は実行時にアプリケーションコード４６０の初期化シーケンスの一部としてメッセージ作成ソフトウェア４８０に読み込まれる。該メッセージ作成ソフトウェアは、アプリケーションコード４６０により呼び出される静的動的リンクライブラリー（“ＤＬＬ”）である。アプリケーションコード４６０が（計算集中的アルゴリズムライブラリー９９の）関数を使うとき、該要求がトリガーされ、テンプレート番号４６８及び関数番号４７０は、バッファーサイズ４７２と、関数パラメータを含むバッファー４７４と共にメッセージ作成ソフトウェアに送られる。テンプレート番号４６８と関数番号４７０とは、バッファー４７４に包含されているパラメータの定義と、アプリケーションコード４６０の出力データ構造定義とを見出すために使われる。メッセージ作成ソフトウェア４８０は、このデータの全部を使って、ＨＣＡＳのホームノードに送られる出力メッセージ定義４８４を作成する。ホームノードは、テンプレート番号４６８と、データタイプ、次元数、及び各次元のサイズを定めるバッファー４７４に含まれるパラメータデータとを使って、使用する処理ノードの数を決定する。
【０１２９】
より具体的には、図３５は、出力メッセージ５０２を介して処理ノード１１２へのアルゴリズム処理要求の分配を開始する１つのホームノード１１０Ｊを示す。例示の目的上、処理ノード１１２が一つだけ示されている。処理ノード１１２は、呼び出された関数に必要とされるデータを待つ。その後、ホームノード１１０Ｊは、データ要求インターフェース４６６を介してそのデータを要求してアプリケーションコード４６０から受け取る。ホームノード１１０Ｊは、図３５においてアプリケーション５０４からデータを受け取って示されている。ホームノード１１０Ｊは、その後、データ放送メッセージ５００を使って該データを処理ノード１１２へ放送する。処理ノード１１２内の制御ソフトウェア９４（図５）は、その後、出力メッセージ５０２に含まれている出力メッセージ定義４８４から変換されたパラメータを使って計算集中的アルゴリズムライブラリー９９の中から選択された関数に対して関数呼び出しを行う。呼び出された関数は、データを処理し、結果を返送する。集塊化プロセスは、その後、該結果をホームノード１１０へ返送し、これは該結果をアプリケーション５０６へのデータとしてアプリケーションコード４６０に送り返す。ホームノード１１０Ｊは、その後、該結果をアプリケーションコード４６０に送り返す。
【０１３０】
アプリケーションコード４６０によりメッセージ作成ソフトウェア４８０に渡される或るパラメータタイプは、特別の値を包含することができる。１つのその様な値は、要求された関数への入力パラメータのために使われる特定のデータ領域を指すポインタについての記憶タイプであり、そのポインタ値は実行時に処理ノード制御ソフトウェアの中でのみ解明可能である。このことは、パラメータ通過の柔軟性及び効率を可能にする。
【０１３１】
要約すると、図３３の関数要求インターフェース４７６とデータ要求インターフェース４６６とは、アプリケーションコード４６０による敏感な関数へのアクセス要求無しに関数がデータレベルで“並列化”されることを可能にする。それは、アプリケーションプログラムへの単純ではあるが高度に拡張可能なＡＰＩにも備えている。
（ＨＣＡＳ上の複雑なアルゴリズム）
複雑なアルゴリズムは、１つ以上の分岐命令を含むアルゴリズムとして定義される。分岐命令は、１つ以上の変数と定数とを比較し、その比較に基づいて実行経路を選択するステートメントである。例えば：
ＩＦ（ｖａｒｉａｂｌｅ＿ａ＞１０）ｔｈｅｎ
｛
Ｅｘｅｃｕｔｉｏｎ−Ｐａｔｈ−Ａ
｝
ｅｌｓｅ
｛        Ｅｘｅｃｕｔｉｏｎ−Ｐａｔｈ−Ｂ
｝
上記の分岐命令で、変数ａの内容が１０より大きいか否かに基づいて２つの実行経路のうちの一方が選択される。実行経路は、別の分岐命令及び計算アルゴリズムを含んでいても良い。
【０１３２】
計算的アルゴリズムは常に１つ以上のサブルーチン又はライブラリー関数呼び出しとして表わされ得る。ＨＣＡＳでは、サブルーチン又はライブラリー関数として表わされ得るコードをＨＣＡＳ上のアルゴリズムライブラリーにインストールすることができる。従って、分岐命令の計算アルゴリズム的部分をＨＣＡＳ上で処理することができる。
【０１３３】
各分岐命令は、連続的な活動を表わす。複雑なアルゴリズムを実行する全ての並列処理は、自分達の処理の中の同じポイントで同じ判定を行う。これを達成する方法が本質的に２つある。第１の方法は、各プロセスが同じ判定を行うために十分な情報を有するように、複雑なアルゴリズムを実行している各プロセス（例えば、ＨＣＡＳ内の処理ノード）がその複雑なアルゴリズムを実行している他の全てのプロセスにメッセージを送ることである。この第１の方法は、必要とされる交差通信の量を最大化するので、解決策としては受け入れられない。第２の方法は、分岐命令を評価する中心の場所を使用する。例えば、この中心の場所は、リモートホストに、またはＨＣＡＳ内のホームノードにあって良い。条件変数データは、複雑なアルゴリズムを実行する各プロセスから中央の場所に送らなければならない唯一の情報であり、従ってデータ転送を最小限に保つ。
【０１３４】
分岐命令は、下記の属性を有する条件関数により表わすことができる：
ＦＵＮＣＴＩＯＮ＿ＮＡＭＥ（（Ｖａｒｉａｂｌｅ｜ｃｏｎｓｔａｎｔ）１＜ｃｏｍｐａｒｉｓｏｎ  ａｔｔｒｉｂｕｔｅ＞
（Ｖａｒｉａｂｌｅ｜ｃｏｎｓｔａｎｔ）２）
｛ｔｒｕｅ  ｐａｔｈ｝
ｅｌｓｅ
｛ｆａｌｓｅ  ｐａｔｈ｝
ここで：
ＦＵＮＣＴＩＯＮ＿ＮＡＭＥ＝条件タイプ、例えば：
ＩＦ，Ｗｈｉｌｅ，Ｕｎｔｉｌなど。
【０１３５】
Ｖａｒｉａｂｌｅ｜ｃｏｎｓｔａｎｔ  ＝変数の名称又は定数値
Ｃｏｍｐａｒｉｓｏｎ  ａｔｔｒｉｂｕｔｅ  ＝論理的又は数学的ステートメント、例えば
ＡＮＤ，ＯＲ，＜，＞，＝ＮＯＲ，ＮＡＮＤなど。
【０１３６】
これは（Ｖａｒｉａｂｌｅ｜ｃｏｎｓｔａｎｔ）１を（Ｖａｒｉａｂｌｅ｜ｃｏｎｓｔａｎｔ）２と比較する。
【０１３７】
注記：  この比較が真ならば、真経路（ｔｒｕｅ  ｐａｔｈ）が取られ、そうでなければ偽経路（ｆａｌｓｅ  ｐａｔｈ）が取られる。
【０１３８】
この様に、複雑なアルゴリズムにおける各々の分岐命令は関数呼び出しになる。条件関数と他の全てのＨＣＡＳ関数との唯一の差違は、条件データが複雑なアルゴリズム中の各分岐命令での評価のために中央の場所に送られることである。
【０１３９】
図６２は、分岐命令を含む複雑なアルゴリズムの例として１つのプロセス１１８０を示すフローチャートである。プロセス１１８０はステップ１１８２から始まってステップ１１８４に続く。ステップ１１８４は、イメージデータに対して２次元相関関数を用いて係数を計算するコードのセクション即ちセクションＡを表わす。ステップ１１８６は、ステップ１１８４で計算された係数を使用する分岐命令を表わす。もしその係数が０．９より大きければ、プロセス１１８０はステップ１１９０で進み、そうでなければプロセス１１８０はステップ１１８８に続く。ステップ１１８８は、この例では付加的なイメージ処理を実行するコードの第２セクション即ちセクションＢを表わす。セクションＢの計算の後、プロセス１１８０はステップ１１９０で続行する。ステップ１１９０は複雑なアルゴリズムの計算の結果を入手し、プロセス１１８０はステップ１１９２で終了する。この例に見られるように、複雑なアルゴリズムは、計算可能なセクション即ちセクションＡ１１８４及びセクションＢ１１８８と、ステップ１１８６のような条件関数とに分解することができる。
【０１４０】
図６３は、ＨＣＡＳで複雑なアルゴリズムを実行するための１つの実施形態を示す。図６３は、３つの相互に作用するプロセス即ちホストプロセス１２００、制御プロセス１３００及び計算プロセス１４００のための３つのフローチャートを示している。ホストプロセス１２００は、複雑なアルゴリズムの処理要求を発して結果を受け取るリモートホストコンピュータで動作するプロセスを表わす。制御プロセス１３００は、複雑なアルゴリズム中の条件分岐命令を調停するプロセスを表わす。制御プロセス１３００は、リモートホストコンピュータで又はＨＣＡＳ内で働くことができる。計算プロセス１４００は、ＨＣＡＳで複雑なアルゴリズムセクションを計算するプロセスを表わす。
【０１４１】
ホストプロセス１２００はステップ１２０２から始まってステップ１２０４で続行する。ステップ１２０４は複雑なアルゴリズムの処理要求制御プロセス１３００送る。ホストプロセス１２００はステップ１２０６に続行し、ここで、計算された結果を受け取るために待機する。
【０１４２】
制御プロセス１３００は、ステップ１３０２から開始してステップ１３０４で続行する。ステップ１３０４は、リモートプロセス１２００から複雑なアルゴリズムの処理要求を受け取り、ステップ１３０６で続行する。ステップ１３０６は、第１セクションを計算するように指示して複雑アルゴリズム処理セクションを計算プロセス１４００に送る。制御プロセス１３００はステップ１３０８で続行する。ステップ１３０８は、計算プロセス１４００が該複雑アルゴリズムのセクションを完了した後に結果を返送するのを待つ。
【０１４３】
計算プロセス１４００は、ステップ１４０２から開始してステップ１４０４で続行する。ステップ１４０４は、制御プロセス１３００から複雑アルゴリズム処理セクションを受け取る。計算プロセス１４００は、ステップ１４０６で続行し、ここで複雑アルゴリズム処理要求の指示されたセクションが計算される。計算プロセス１４００はステップ１４０８で続行する。ステップ１４０８は、計算されたセクションの結果を集塊化し、それを制御プロセス１３００に送る。計算プロセス１４００はステップ１４１０で続行し、ここで制御プロセス１３００からの指示を待つ。
【０１４４】
制御プロセス１３００は、ステップ１３０８で計算プロセス１４００から計算されたセクションの結果を受け取り、ステップ１３１０で続行する。複雑アルゴリズム処理要求をそれ以上計算する必要が無ければ、制御プロセス１３００はステップ１３１４で続行し、そうでなければ、ステップ１３１０が、計算プロセス１４００から返送された結果を用いて複雑アルゴリズム処理要求中のそれぞれの条件分岐を評価し、ステップ１３１２で続行する。
【０１４５】
ステップ１３１２は、計算プロセス１４００に指示メッセージを送ることによって複雑アルゴリズム処理要求の次のセクションの計算を開始する。制御プロセス１３００は、その後、ステップ１３０８で続行し、ここで、開始されたセクションの計算が計算プロセス１４００により完了されるのを待つ。
【０１４６】
計算プロセス１４００のステップ１４１０は、次にセクションを計算するか否か、そしてどのセクションを計算するかを示す指示を制御プロセス１３００から受け取る。もし次に計算するセクションが無ければ、計算プロセス１４００はステップ１４１４で終了し、そうでなければ計算プロセス１４００はステップ１４０６で続行し、ここで次のセクションが計算される。
【０１４７】
制御プロセス１３００のステップ１３１４において、計算されるべきセクションはもう無いということを示す指示メッセージが計算プロセス１４００に送られる。制御プロセス１３００はステップ１３１６で続行し、ここで、ステップ１３０８で計算プロセス１４００から受け取った最終結果をホストプロセス１２００に送る。制御プロセス１３００はその後ステップ１３１８で終了する。
【０１４８】
ホストプロセス１２００は、その結果をステップ１２０６で制御プロセス１３００から受け取る。ホストプロセス１２００はその後ステップ１２０８で終了する。
【０１４９】
上の例に見られるように、複雑なアルゴリズムの計算可能なセクション及び条件関数への分解、データは必要に応じて動かされるだけである。分岐命令を中央の場所で評価することによって分岐命令の本来の連続性が維持され、ＨＣＡＳは複雑なアルゴリズムを効率よく取り扱う。
（アルゴリズム展開ツールキット）
このセクション（アルゴリズム展開ツールキット）は、ＨＣ内でアルゴリズムを実行するための選択プロセスを説明する。この様なプロセスは、設計選択肢の問題として自動化されて良い。
【０１５０】
図３６は、新しいアルゴリズム５２０がＨＣＡＳ８０Ａで動作することとなるように新しいアルゴリズム５２０をアルゴリズムライブラリー９９に付け加えるためにアルゴリズム展開ツールキット５２２がどのように使われるかを示すブロック構成図である。アルゴリズム展開ツールキット５２２は、最少量の展開作業で新しいアルゴリズム５２０がＨＣＡＳ８０の処理ノード１１２，１１４，１１６及び１１８で並列に動作することを可能にするために新しいアルゴリズム５２０に付け加えることのできるルーチンのセットを含んでいる。付け加えられたルーチンは、新しいアルゴリズム５２０に自分がどの処理ノード上で動作しているか気づかせると共に、自分が処理しなければならないデータ構造に気づかせる。
【０１５１】
ホームノード１１０Ｋ、処理ノード１１２、処理ノード１１４、処理ノード１１６、及び処理ノード１１８は、計算集中的アルゴリズムライブラリー９９内の関数のためのデータ及びパラメータを定めるデータテンプレート定義５２８を含んでいる。ＨＣＡＳ８０Ａの全ての処理ノードは、データテンプレート定義５２８と計算集中的アルゴリズムライブラリー９９との同一のコピーを含んでいる。アルゴリズム展開ツールキット５２２は、データ経路５２４を介するデータ定義５２８及び計算集中的アルゴリズムライブラリー９９への新しいアルゴリズム５２０の追加と、データ経路５２６を介する、リモートホスト８２で動作するアプリケーションにより使用される並列インターフェースライブラリー５３０への新しいアルゴリズム５２０の追加とを容易にする。
【０１５２】
図３７は、アルゴリズム展開ツールキット５２２からのルーチンで拡張された新しいアルゴリズム５２０の１つのプロセス５５０を示すフローチャートである。プロセス５５０は、ステップ５５２から出発してステップ５５４で続行する。
【０１５３】
ステップ５５４は、図３８に記載されているメッシュツール関数への関数呼び出しであり、それは新しいアルゴリズムについての入力データ記述及び出力データ記述を抽出する。プロセス５５０はステップ５５６で続行する。
【０１５４】
ステップ５５６は、図５１に記載されている入力データ関数を獲得する関数呼び出しであり、それは新しいアルゴリズムのためのデータを獲得する。プロセス５５０はステップ５５８で続行する。
【０１５５】
ステップ５５８は、処理ノードのための結果を計算する関数呼び出しであり、この関数が動作する処理ノードのためにステップ５５６で獲得されたデータセットに対する新しいアルゴリズムの呼び出しである。プロセス５５０はステップ５６０で続行する。
【０１５６】
ステップ５６０は、図５３に記載されている集塊化結果関数に対する関数呼び出しであり、それはＨＣの集塊化段階の間に下流側処理ノードから結果を受け取る。プロセス５５０はステップ５６２で続行する。
【０１５７】
ステップ５６２は、図５７に記載されている結果返送関数に対する関数呼び出しであり、それはローカルな集塊化された結果を正しい処理ノードへ、或いは必要に応じてホームノードへ送る。プロセス５５０はステップ５６４で終了する。
【０１５８】
図３８は、図３７のプロセス５５０のステップ５５４で呼び出されたメッシュツールサブプロセス５７０を示すフローチャートである。メッシュツールサブプロセス５７０は、アルゴリズム要求メッセージから入力データ記述及び出力データ記述を抽出し、それがその上で動作するところの処理ノード位置を用いてローカル計算のためのメッシュサイズを計算する。メッシュは、使用されることになる入力データ及び出力データの記述であって、この処理ノードによりどれだけの量の結果が計算されるか、そして結果を計算するためにどの入力値が使われるかを定める。メッシュは、アルゴリズムのタイプ、ＨＣにおける処理ノードの位置、及びＨＣにおける処理ノードの総数に依存する。サブプロセス５７０はステップ５７２から始まり、ステップ５７４で続行する。
【０１５９】
ステップ５７４は、図３９に記載されている入力データサイズ発見関数に対する関数呼び出しであり、それはアルゴリズム処理要求から入力データサイズを抽出する。サブプロセス５７０はステップ５７６で続行する。
【０１６０】
ステップ５７６は、図４０に記載されている出力データサイズ計算サブプロセスに対する関数呼び出しであり、それは入力データセットサイズと新しいアルゴリズムの計算タイプとに基づいて出力データセットサイズを計算する。サブプロセス５７０はステップ５７８で続行する。
【０１６１】
ステップ５７８は、図４４に記載されているメッシュパラメータ計算サブプロセスに対する関数呼び出しであり、それはこの処理ノードによって結果のどの部分が計算されることになるかを定めるメッシュパラメータを計算する。サブプロセス５７０はステップ５８
０で終了し、自分が呼び出されたところに返る。
【０１６２】
図３９は、１つの入力データサイズ発見サブプロセス５９０を記述するフローチャートであって、これはステップ５９２から始まってステップ５９４で続行する。
【０１６３】
ステップ５９４は判定である。新しいアルゴリズムが級数展開であれば、サブプロセス５９０はステップ５９６で続行し、そうでなければサブプロセス５９０はステップ５９８で続行する。
【０１６４】
ステップ５９６は、データ入力ロー及びデータ入力サイズを該級数中の項の数にセットする。サブプロセス５９０はステップ６００で続行する。
【０１６５】
ステップ５９８は、第１データ入力ロー、コラム及び要素サイズを入力イメージサイズと調和させる。サブプロセス５９０はステップ６０２で続行する。
【０１６６】
ステップ６００は、データ入力要素サイズを要素あたりに提供される数字の数にセットする。サブプロセス５９０はステップ６０４で続行する。
【０１６７】
ステップ６０２は、第１データ入力サイズをステップ５９８で定められたデータ入力ローｘコラムｘ要素サイズにセットする。サブプロセス５９０はステップ６０６で続行する。
【０１６８】
ステップ６０４は、データ入力コラムを１にセットする。サブプロセス５９０はステップ６１２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１６９】
ステップ６０６は判定である。もし第２入力イメージがあれば、サブプロセス５９０はステップ６０８で続行し、そうでなければサブプロセス５９０はステップ６１２で終了して、呼び出しを行ったプロセスにコントロールを返す。
【０１７０】
ステップ６０８は、第２データ入力ロー、コラム及び要素サイズを第２入力イメージと調和させる。サブプロセス５９０はステップ６１０で続行する。
【０１７１】
ステップ６１０は、第２データ入力サイズを、ステップ６０８で定められるデータ入力ローｘコラムｘ要素サイズにセットする。サブプロセス５９０はステップ６１２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１７２】
図４０は図３７のプロセス５５０により呼び出された出力データサイズを見出す１つのサブプロセス６２０を示すフローチャートである。サブプロセス６２０は、ステップ６２２から始まってステップ６２４で続行する。
【０１７３】
ステップ６２４は判定である。新しいアルゴリズムが級数展開であれば、サブプロセス６２０はステップ６２８で続行し、そうでなければサブプロセス６２０はステップ６２６で続行する。
【０１７４】
ステップ６２６は判定である。もし第２イメージがあれば、サブプロセス６２０はステップ６３２で続行し、そうでなければサブプロセス６２０はステップ６３０で続行する。
【０１７５】
ステップ６２８は、図４１で定められる級数展開のためのサブプロセス出力級数サイズ計算を呼び出し、これは、新しいアルゴリズムにより計算される級数について出力データサイズを計算する。サブプロセス６２０はステップ６３４で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１７６】
ステップ６３０は図４２で定義される単一イメージについてサブプロセス出力データサイズ計算を呼び出し、これは単一のイメージについて出力データサイズを計算する。サブプロセス６２０は、ステップ６３４で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１７７】
ステップ６３２は、図４３で定められる２つのイメージについてサブプロセス出力デー
タサイズ計算を呼び出し、これは２つのイメージについて出力データサイズを計算する。サブプロセス６２０は、ステップ６３４で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１７８】
図４１は、新しいアルゴリズムで使われる級数展開について出力データサイズを計算するための１つのサブプロセス６４０を示す。サブプロセス６４０は、ステップ６４２から始まり、ステップ６４４で続行する。
【０１７９】
ステップ６４４は、データ出力ローを該級数の項の数にセットする。サブプロセス６４０はステップ６４６で続行する。
【０１８０】
ステップ６４６は、データ出力要素サイズを１にセットする。サブプロセス６４０はステップ６４８で続行する。
【０１８１】
ステップ６４８は、データ出力コラムを１にセットする。サブプロセス６４０はステップ６５０で続行する。
【０１８２】
ステップ６５０は判定である。新しいアルゴリズムがｅｘ展開であれば、サブプロセス６４０はステップ６５４で続行し、そうでなければサブプロセス６４０はステップ６５２で続行する。
【０１８３】
ステップ６５２は判定である。新しいアルゴリズムがシグマ平方根展開であれば、サブステップ６４０はステップ６５８で続行し、そうでなければサブプロセス６４０はステップ６５６で続行する。
【０１８４】
ステップ６５４は、出力データサイズをｅｘ展開のための集塊化構造のサイズにセットする。サブプロセス６４０はステップ６６０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１８５】
ステップ６５６は、データ出力サイズを該級数の項の数プラス１にセットする。サブプロセス６４０は、ステップ６６０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１８６】
ステップ６５８は、データ出力サイズを、ＡＳＣＩＩ浮動小数点数における数字の数にセットする。サブプロセス６４０は、ステップ６６０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１８７】
図４２は、入力データが単一のイメージであるときの出力データサイズを計算するための１つのサブプロセス６７０を示す。サブプロセス６７０は、ステップ６７２から始まり、ステップ６７４で続行する。
【０１８８】
ステップ６７４は、データ出力ローをデータ入力ローに等しくセットする。サブプロセス６７０はステップ６７６で続行する。
【０１８９】
ステップ６７６は、データ出力コラムをデータ入力コラムに等しくセットする。サブプロセス６７０はステップ６７８で続行する。
【０１９０】
ステップ６７８は判定である。新しいアルゴリズムがＦＦＴ計算であれば、サブプロセス６７０はステップ６８２で続行し、そうでなければサブプロセス６７０はステップ６８０で続行する。
【０１９１】
ステップ６８０は、データ出力サイズをデータ入力要素サイズに等しくセットする。サブプロセス６７０は、ステップ６８４で続行する。
【０１９２】
ステップ６８２は、データ出力要素サイズを２つの倍精度浮動小数点数のサイズにセットする。サブプロセス６７０はステップ６８４で続行する。
【０１９３】
ステップ６８４は、データ出力サイズをデータ出力ローｘコラムｘ要素サイズにセットする。サブプロセス６７０は、ステップ６８６で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０１９４】
図４３は、新しいアルゴリズムが２つの入力イメージを有するときに出力データのサイズを計算する１つのサブプロセス６９０を示す。サブプロセス６９０は、ステップ６９２から始まり、ステップ６９４で続行する。
【０１９５】
ステップ６９４は、データ出力ローを、データ入力第１ロー、マイナスデータ入力第２ロー、プラス１に等しくセットする。サブプロセス６９０はステップ６９６で続行する。
【０１９６】
ステップ６９６は、データ出力コラムを、データ入力第１コラム、マイナスデータ入力第２コラム、プラス１にセットする。サブプロセス６９０はステップ６９８で続行する。
【０１９７】
ステップ６９８は判定である。新しいアルゴリズムがコンブォルブ（ｃｏｎｖｏｌｖｅ）計算であれば、サブプロセス６９０はステップ７００で続行し、そうでなければサブプロセス６９０はステップ７０２で続行する。
【０１９８】
ステップ７００は、データ出力要素サイズを単精度浮動小数点数のサイズにセットする。サブプロセス６９０はステップ７０４で続行する。
【０１９９】
ステップ７０２は、データ出力要素サイズを倍精度浮動小数点数のサイズにセットする。サブプロセス６９０はステップ７０４で続行する。
【０２００】
ステップ７０４は、出力データサイズをデータ出力ローｘコラムｘ要素サイズにセットする。サブプロセス６９０は、ステップ７０６で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２０１】
図４４は、メッシュについてのパラメータを計算する１つのサブプロセス７１０を示す。サブプロセス７１０は、ステップ７１２から始まり、ステップ７１４で続行する。
【０２０２】
ステップ７１４は判定である。新しいアルゴリズムがπ、シグマ平方根又はＬＮ（Ｘ）計算であれば、サブプロセス７１０はステップ７１６で続行し、そうでなければサブプロセス７１０はステップ７１８で続行する。
【０２０３】
ステップ７１６は、図４５に記載されているＮの全ての値について１次元メッシュを計
算するサブプロセスを呼び出す。サブプロセス７１０は、ステップ７３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２０４】
ステップ７１８は判定である。新しいアルゴリズムがｅｘ計算であれば、サブプロセス７１０はステップ７２０で続行し、そうでなければサブプロセス７１０はステップ７２２で続行する。
【０２０５】
ステップ７２０は、図４６で定められている１次元連続ブロックメッシュを計算するサブプロセスを呼び出す。サブプロセス７１０は、ステップ７３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２０６】
ステップ７２２は判定である。新しいアルゴリズムが畳み込み、正規化相互相関又はエッジ検出アルゴリズムならば、サブプロセス７１０はステップ７２４で続行し、そうでなければサブプロセス７１０はステップ７２６で続行する。
【０２０７】
ステップ７２４は、図４６で定められている２次元連続ブロックローメッシュを計算するサブプロセスを呼び出す。サブプロセス７１０は、ステップ７３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２０８】
ステップ７２６は判定である。新しいアルゴリズムがＦＦＴ計算であれば、サブプロセス７１０はステップ７２８で続行し、そうでなければサブプロセス７１０はステップ７３０で続行する。
【０２０９】
ステップ７２８は、図４８で定められている２次元連続ブロックロー及びコラムメッシュを計算するサブプロセスを呼び出す。サブプロセス７１０は、ステップ７３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２１０】
ステップ７３０は、図４７で定められている２次元連続ブロックコラムメッシュを計算するサブプロセスを呼び出す。サブプロセス７１０は、ステップ７３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２１１】
図４５は、１次元の全てのＮメッシュを計算する１つのサブプロセス７４０を示す。サ
ブプロセス７４０は、ステップ７４２から始まり、ステップ７４４で続行する。
【０２１２】
ステップ７４４は、メッシュ入力サイズをデータ入力ローにセットする。サブプロセス７４０はステップ７４６で続行する。
【０２１３】
ステップ７４６は、メッシュ入力オフセットをデータ入力要素サイズｘ処理ノードのカスケード位置にセットする。サブプロセス７４０はステップ７４８で続行する。
【０２１４】
ステップ７４８は、メッシュ入力ステップを、アルゴリズム処理要求に働きかける処理ノードの数に等しくセットする。サブプロセス７４０はステップ７５０で続行する。
【０２１５】
ステップ７５０は判定である。メッシュが項０から始まるのであれば、サブプロセス７４０はステップ７５２で続行し、そうでなければサブプロセス７４０はステップ７５４で続行する。
【０２１６】
ステップ７５２は、メッシュスタートを処理ノードのカスケード位置にセットする。サブプロセス７４０はステップ７５６で続行する。
【０２１７】
ステップ７５４は、メッシュ入力スタートを処理ノードのカスケード位置プラス１にセットする。サブプロセス７４０は、ステップ７５６で続行する。
【０２１８】
ステップ７５６は、メッシュ出力サイズをデータ入力ローにセットする。サブプロセス７４０はステップ７５８で続行する。
【０２１９】
ステップ７５８は、メッシュ出力オフセットをデータ入力要素サイズｘ処理ノードのカスケード位置にセットする。サブプロセス７４０はステップ７６０で続行する。
【０２２０】
ステップ７６０は、メッシュ出力ステップを、アルゴリズム処理要求に働きかける処理ノードの総数にセットする。サブプロセス７４０は、ステップ７６２で続行する。
【０２２１】
ステップ７６２は判定である。メッシュが項０から始まるならば、サブプロセス７４０はステップ７６４で続行し、そうでなければサブプロセス７４０はステップ７６６で続行する。
【０２２２】
ステップ７６４はメッシュ出力スタートを処理ノードのカスケード位置に等しくセットする。サブプロセス７４０は、ステップ７６８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２２３】
ステップ７６６は、メッシュ出力スタートを処理ノードのカスケード位置プラス１にセットする。サブプロセス７４０は、ステップ７６８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２２４】
図４６は１次元連続ブロックメッシュを計算する１つのサブプロセス７８０を示しており、これは２次元連続ブロックローメッシュを計算するための同じサブプロセス７８０でもある。サブプロセス７８０は、ステップ７８２から始まり、ステップ７８４で続行する。
【０２２５】
ステップ７８４は、図４９で定められている、データ入力ローに基づいて線形メッシュを計算するサブプロセスを呼び出す。サブプロセス７８０はステップ７８６で続行する。
【０２２６】
ステップ７８６は、図５０で定められている、データ出力ローに基づいて線形メッシュを計算するサブプロセスを呼び出す。サブプロセス７８０は、ステップ７８８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２２７】
図４７は、２次元連続ブロックメッシュを計算する１つのサブプロセス８００を示すフローチャートである。サブプロセス８００は、ステップ８０２から始まり、ステップ８０４で続行する。
【０２２８】
ステップ８０４は、図４９で定められている、データ入力コラムで線形メッシュを計算するサブプロセスを呼び出す。サブプロセス８００はステップ８０６で続行する。
【０２２９】
ステップ８０６は、図５０で定められている、データ出力コラムに基づいて線形メッシュを計算するサブプロセスを呼び出す。サブプロセス８００は、ステップ８０８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２３０】
図４８は、２次元連続クロックロー及びコラムメッシュを計算する１つのサブプロセス８２０を示すフローチャートである。サブプロセス８２０は、ステップ８２２から始まり、ステップ８２４で続行する。
【０２３１】
ステップ８２４は、図４９で定められている、データ入力ローで線形メッシュを計算する下位関数を呼び出す。サブプロセス８２０はステップ８２６で続行する。
【０２３２】
ステップ８２６は、デー出力ローに基づいて線形メッシュを計算するサブプロセスを呼び出す。サブプロセス８２０はステップ８２８で続行する。
【０２３３】
ステップ８２８は、図４９で定められているデータ入力コラムで線形メッシュを計算する下位関数を呼び出す。サブプロセス８２０はステップ８３０で続行する。
【０２３４】
ステップ８３０は、データ出力コラムに基づいて線形メッシュを計算するサブプロセスを呼び出す。サブプロセス８２０は、ステップ８３２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２３５】
図４９は、ローに関して線形メッシュを計算する１つのサブプロセス８４０を示すフローチャートである。サブプロセス８４０は、データ入力計算及びデータ出力計算の両方のために呼び出すことのできるものである。サブプロセス８４０は、ステップ８４２から始まり、ステップ８４４で続行する。
【０２３６】
ステップ８４４は判定である。カーネルを伴う第２イメージが存在するならば、サブプロセス８４０はステップ８４８で続行し、そうでなければサブプロセス８４０はステップ８４６で続行する。
【０２３７】
ステップ８４６は、入力サイズをローにセットする。サブプロセス８４０はステップ８５０で続行する。
【０２３８】
ステップ８４８は、入力サイズを第１ローマイナス第２ローにセットする。サブプロセス８４０はステップ８５０で続行する。
【０２３９】
ステップ８５０は、メッシュサイズを、アルゴリズム処理要求に対して働きかける処理ノードの総数で割った入力サイズにセットする。サブプロセス８４０はステップ８５２で続行する。
【０２４０】
ステップ８５２は、メッシュインデックスを、該アルゴリズムがその上で動作するところの処理ノードのカスケード位置とメッシュサイズとの積にセットする。サブプロセス８４０はステップ８５４に続く。
【０２４１】
ステップ８５４は判定である。もしカーネルを伴う第２イメージが存在するならば、サブプロセス８４０はステップ８５６で続行し、そうでなければサブプロセス８４０はステップ８５８で続行する。
【０２４２】
ステップ８５６は、第２ローから１を引いて得られる差をメッシュインデックスに加える。サブプロセス８４０はステップ８５８で続行する。
【０２４３】
ステップ８５８は、メッシュ剰余を、アルゴリズム処理要求に働きかける処理ノードの総数で割った入力サイズの剰余にセットする。サブプロセス８４０はステップ８６０で続行する。
【０２４４】
ステップ８６０は判定である。もし処理ノードのカスケード位置がステップ８５８で計算されたメッシュ剰余より小さければ、サブプロセス８４０はステップ８６４で続行し、そうでなければサブプロセス８４０はステップ８６２で続行する。
【０２４５】
ステップ８６２は、処理ノードのカスケード位置をメッシュインデックスに加える。サブプロセス８４０はステップ８６６で続行する。
【０２４６】
ステップ８６４は、ステップ８５８で計算されたメッシュ剰余をメッシュインデックスに加える。サブプロセス８４０は、ステップ８６８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２４７】
ステップ８６６はメッシュサイズをインクリメントする。サブプロセス８４０は、ステップ８６８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２４８】
図５０は、コラムに関して線形メッシュを計算する１つのサブプロセス８８０を示すフローチャートである。サブプロセスは、データ入力計算及びデータ出力計算の両方のために呼び出すことのできるものである。サブプロセス８８０は、ステップ８８２から始まり、ステップ８８４で続行する。
【０２４９】
ステップ８８４は判定である。もしカーネルを伴う第２イメージが存在するならば、サブプロセス８８０はステップ８８８で続行し、そうでなければサブプロセス８８０はステップ８８６で続行する。
【０２５０】
ステップ８８６は、入力サイズをコラムにセットする。サブプロセス８８０は、ステップ８９０で続行する。
【０２５１】
ステップ８８８は、入力サイズを、第１コラムから第２ローを引いた差にセットする。サブプロセス８８０はステップ８９０で続行する。
【０２５２】
ステップ８９０は、メッシュサイズを、アルゴリズム処理要求に働きかける処理ノードの総数で割った入力サイズにセットする。サブプロセス８８０はステップ８９２で続行する。
【０２５３】
ステップ８９２は、メッシュインデックスを、該アルゴリズムがその上で動作するところの処理ノードのカスケード位置とメッシュサイズとの積にセットする。サブプロセス８８０はステップ８９４で続行する。
【０２５４】
ステップ８９４は判定である。もしカーネルを伴う第２イメージが存在するならば、サブプロセス８８０はステップ８９６で続行し、そうでなければサブプロセス８８０はステップ８９８で続行する。
【０２５５】
ステップ８９６は、第２コラムから１を引いた差をメッシュインデックスに加える。サブプロセス８８０はステップ８９８で続行する。
【０２５６】
ステップ８９８は、メッシュ剰余を、アルゴリズム処理要求に働きかける処理ノードの総数で割った入力サイズの剰余にセットする。サブプロセス８８０はステップ９００で続行する。
【０２５７】
ステップ９００は判定である。もし処理ノードのカスケード位置がステップ８９８で計算されたメッシュ剰余より小さければ、サブプロセス８８０はステップ９０４で続行し、そうでなければサブプロセス８８０はステップ９０２で続行する。
【０２５８】
ステップ９０２は、処理ノードのカスケード位置をメッシュインデックスに加える。サブプロセス８８０はステップ９０６で続行する。
【０２５９】
ステップ９０４は、ステップ８９８で計算されたメッシュ剰余をメッシュインデックスに加える。サブプロセス８８０は、ステップ９０８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２６０】
ステップ９０６はメッシュサイズをインクリメントする。サブプロセス８８０は、ステップ９０８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２６１】
図５１は、アルゴリズム処理要求を実行するために処理ノードが必要とする入力データを獲得する１つのサブプロセス９２０を示すフローチャートである。サブプロセス９２０はステップ９２２から始まり、ステップ９２４で続行する。
【０２６２】
ステップ９２４は判定である。アルゴリズム処理要求が入力データを期待しているならば、サブプロセス９２０はステップ９２６で続行し、そうでなければサブプロセス９２０はステップ９３０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２６３】
ステップ９２６は判定である。データがＨＣによりデータ放送として送られれば、サブプロセス９２０はステップ９２８で続行し、そうでなければサブプロセス９２０はステップ９３０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２６４】
ステップ９２８は、図５２で定められている放送メッセージを受け取るためにマルチキャストツールを使用するサブプロセスを呼び出す。サブプロセス９２０はステップ９３０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２６５】
図５２は、放送データを受け取るためにマルチキャストツールを使用する１つのサブプロセス９４０を示すフローチャートである。サブプロセス９４０は、ステップ９２９から始まり、ステップ９４４で続行する。
【０２６６】
ステップ９４４は、放送を受け取るためにマルチキャストソケットを開く。サブプロセス９４０はステップ９４６で続行する。
【０２６７】
ステップ９４６はマルチキャストデータを受け取る。サブプロセス９４０はステップ９４８で続行する。
【０２６８】
ステップ９４８は判定である。受け取るデータがもっとあれば、サブプロセス９４０はステップ９４６で続行し、そうでなければサブプロセス９４０はステップ９５０で続行する。
【０２６９】
ステップ９５０は、ステップ９４４で開かれたマルチキャストソケットを閉じる。サブプロセス９４０はステップ９５２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２７０】
図５３は、集塊化時に、下流側の処理ノードから結果を受け取る１つのサブプロセス９６０を示すフローチャートである。サブプロセス９６０はステップ９６２から始まり、ステップ９６４で続行する。
【０２７１】
ステップ９６４は判定である。集塊化がマルチホームノードを伴うタイプのものであれば、サブプロセス９６０はステップ９８０で終了し、呼び出しを行ったプロセスにコントロールを返し、そうでなければサブプロセス９６０はステップ９６６で続行する。
【０２７２】
ステップ９６６は、下流側の処理ノードから期待されるメッセージの数を判定する。サブプロセス９６０はステップ９６８で続行する。
【０２７３】
ステップ９６８は判定である。期待されるメッセージが無ければ、サブプロセス９６０はステップ９８０で終了して呼び出しを行ったプロセスにコントロールを返し、そうでなければサブプロセス９６０はステップ９７０で続行する。
【０２７４】
ステップ９７０は、受け取った結果を格納するために使用される結果ポインタをセットするサブプロセスを呼び出す。サブプロセス９６０はステップ９７２で続行する。
【０２７５】
ステップ９７２は、データが添付されているメッセージを受け取る。サブプロセス９６０はステップ９７４で続行する。
【０２７６】
ステップ９７４は結果を前の結果と結合させるサブプロセスを呼び出す。サブプロセス９６０はステップ９７６で続行する。
【０２７７】
ステップ９７６は判定である。データが添付されているメッセージがもっと期待されるならば、サブプロセス９６０はステップ９７０で続行し、そうでなければサブプロセス９６０はステップ９７８で続行する。
【０２７８】
ステップ９７８は、集塊化が完了した後に記憶装置を掃除するサブプロセスを呼び出す。サブプロセス９６０はステップ９８０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２７９】
図５４は、結果ポインタを集塊化結果のために準備ができている状態にセットする１つのサブプロセス９９０を示すフローチャートである。サブプロセス９９０はステップ９９２から始まり、ステップ９９４で続行する。
【０２８０】
ステップ９９４は判定である。集塊化タイプがローメッシュであれば、入力データのために割り当てられた現存するメモリーを使うことができ、サブプロセス９９０はステップ１０００で続行し、そうでなければサブプロセス９９０はステップ９９６で続行する。
【０２８１】
ステップ９９６は判定である。集塊化タイプが結果リストであれば、サブプロセス９９０はステップ１００２で続行し、そうでなければサブプロセス９９０はステップ９９８で続行する。
【０２８２】
ステップ９９８は判定である。ポインタが現在使用されていれば、サブプロセス９９０はステップ１００６で終了し、呼び出しを行ったプロセスにコントロールを返し、そうでなければサブプロセス９９０はステップ１００２で続行する。
【０２８３】
ステップ１０００は、データポインタを入力データスペースを指すように向けさせる。サブプロセス９９０はステップ１００６で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２８４】
ステップ１００２は、集塊化のためにもっとメモリーを割り当てる。サブプロセス９９０はステップ１００４で続行する。
【０２８５】
ステップ１００４は、ステップ１００２で割り当てられたメモリースペースにポインタを向けさせる。サブプロセス９９０はステップ１００６で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２８６】
図５５は、集塊化中に結果を処理する１つのサブプロセス１０２０を示すフローチャートである。サブプロセス１０２０はステップ１０２２から始まり、ステップ１０２４で続行する。
【０２８７】
ステップ１０２４は判定である。集塊化タイプが任意精度加算であれば、サブプロセス１０２０はステップ１０２６で続行し、そうでなければサブプロセス１０２０はステップ１０２８で続行する。
【０２８８】
ステップ１０２６は、受け取った集塊化データをＡＰＦＬＯＡＴ数に変換し、それを蓄積されている結果に加える。サブプロセス１０２０はステップ１０４０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２８９】
ステップ１０２８は判定である。集塊化タイプが浮動小数点加算であれば、サブプロセス１０２０はステップ１０３０で続行し、そうでなければサブプロセス１０２０はステップ１０３２で続行する。
【０２９０】
ステップ１０３０は、受け取った集塊化データを浮動小数点数に変換し、それを蓄積されている結果に加える。サブプロセス１０２０はステップ１０４０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２９１】
ステップ１０３２は判定である。集塊化タイプが最大を保存するタイプであれば、サブプロセス１０２０はステップ１０３４で続行し、そうでなければサブプロセス１０２０はステップ１０３６で続行する。
【０２９２】
ステップ１０３４は、受け取った集塊化結果を格納されている値と比較し、もしそれより大きければ格納されている値を受け取った集塊化データに置き換える。サブプロセス１０２０はステップ１０４０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２９３】
ステップ１０３６は判定である。集塊化タイプが結果リストであれば、サブプロセス１０２０はステップ１０３８で続行し、そうでなければサブプロセス１０２０はステップ１０４０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２９４】
ステップ１０３８は、結果ポインタを結果リストに加え、結果カウンタをインクリメントする。サブプロセス１０２０はステップ１０４０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２９５】
図５６は、使用された結果スペースを集塊化が完了した後に掃除する１つのサブプロセス１０５０を示すフローチャートである。サブプロセス１０５０はステップ１０５２から始まり、ステップ１０５４で続行する。
【０２９６】
ステップ１０５４は判定である。集塊化方法がＲＯＷＭＥＳＨであったならば、サブプロセス１０５０はステップ１０５８で終了し、呼び出しを行ったプロセスにコントロールを返す。そうでなければサブプロセス１０５０はステップ１０５６で続行する。
【０２９７】
ステップ１０５６は、割り当てられたメモリースペースを解放する。サブプロセス１０５０はステップ１０５８で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０２９８】
図５７は、局所の或いは集塊化された結果を正しい処理ノード或いはホームノードに返す１つのサブプロセス１０７０を示すフローチャートである。サブプロセス１０７０はステップ１０７２から始まり、ステップ１０７４で続行する。
【０２９９】
ステップ１０７４は、図５８で定められている、結果を受け取る宛先ノードのアドレスを得るサブプロセスを呼び出す。サブプロセス１０７０はステップ１０７６で続行する。
【０３００】
ステップ１０７６は、図５９で定められている、結果メッセージのためのフォーマットを得るサブプロセスを呼び出す。サブプロセス１０７０はステップ１０７８で続行する。
【０３０１】
ステップ１０７８は、図６０で定められている、結果メッセージを構築するサブプロセスを呼び出す。サブプロセス１０７０はステップ１０８０で続行する。
【０３０２】
ステップ１０８０は、図６１で定められている、結果メッセージを宛先ノードに送るサブプロセスを呼び出す。サブプロセス１０７０は、ステップ１０８２で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３０３】
図５８は、集塊化結果を受け取るノードのアドレスを決定する１つのサブプロセス１０９０を示すフローチャートである。サブプロセス１０９０はステップ１０９２から始まり、ステップ１０９４で続行する。
【０３０４】
ステップ１０９４は判定である。結果がホームノードに送られるべきであれば、サブプロセス１０９０はステップ１０９８で続行し、そうでなければサブプロセス１０９０はステップ１０９６で続行する。
【０３０５】
ステップ１０９６は、上流側処理ノードのためのアドレスを得る。サブプロセス１０９０はステップ１１００で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３０６】
ステップ１０９８はホームノードのアドレスを得る。サブプロセス１０９０はステップ１１００で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３０７】
図５９は結果メッセージのフォーマットを入手する１つのサブプロセス１１１０を示すフローチャートである。サブプロセス１１１０はステップ１１１２から始まり、ステップ１１１４で続行する。
【０３０８】
ステップ１１１４は判定である。その結果がホームノードへの結果であれば、サブプロセス１１１０はステップ１１１８で続行し、そうでなければサブプロセス１１１０はステップ１１１６で続行する。
【０３０９】
ステップ１１１６は、上流側処理ノードについてのメッセージフォーマットを得る。サブプロセス１１１０はステップ１１２０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３１０】
ステップ１１１８は、ホームノードについてのメッセージフォーマットを入手する。サブプロセス１１１０はステップ１１２０で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３１１】
図６０は、結果メッセージを作る１つのサブプロセス１１３０を示すフローチャートである。サブプロセス１１３０は、ステップ１１３２から始まり、ステップ１１３４で続行する。
【０３１２】
ステップ１１３４は判定である。メッセージがデータヘッダ無しで返されるのであれば、サブプロセス１０３０はステップ１１３６で続行し、そうでなければサブプロセス１１３０はステップ１１３８で続行する。
【０３１３】
ステップ１１３６は、データヘッダ無しのメッセージを作る。サブプロセス１１３０はステップ１１４４で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３１４】
ステップ１１３８は判定である。メッセージがデータヘッダを伴って作られるのであれば、サブプロセス１１３０はステップ１１４０で続行し、そうでなければサブプロセス１１３０はステップ１１４２で続行する。
【０３１５】
ステップ１１４２は、処理ノード結果メッセージを作る。サブプロセス１１３０はステップ１１４４で終了し、呼び出しを行ったプロセスにコントロールを返す。
【０３１６】
図６１は、結果メッセージを送る１つのサブプロセス１１６０を示すフローチャートである。サブプロセス１１６０はステップ１１６２から始まり、ステップ１１６４で続行する。
【０３１７】
ステップ１１６４は宛先ノードへのストリームソケットを開く。サブプロセス１１６０はステップ１１６６で続行する。
【０３１８】
ステップ１１６６はストリーム沿いにデータを送る。サブプロセス１１６０はステップ１１６８で続行する。
【０３１９】
ステップ１１６８は判定である。送るデータがもっとあれば、サブプロセス１１６０はステップ１１６６で続行し、そうでなければサブプロセス１１６０はステップ１１７０で続行する。
【０３２０】
ステップ１１７０はストリームソケットを閉じる。サブプロセス１１６０はステップ１１７２で終了し、呼び出しを行ったプロセスにコントロールを返す。
（不均質コンピュータシステム及び通信チャネルを使ってＨＣＡＳを作る）
ＨＣＡＳでは同等の仕様及び性能のコンピュータシステム及び通信チャネルを使うのが好ましいが、システム効率を顕著に低下させることなく、まちまちな仕様のシステム及びチャネルからＨＣＡＳを作ることができる。例えば、まちまちなプロセッサ速度、単一プロセッサマザーボード又は多プロセッサマザーボード、及びいろいろな数のＮＩＣを有するコンピュータシステムを同じＨＣＡＳ内のホームノード及び処理ノードとして利用することができる。
【０３２１】
従来技術の並列処理システムでは、ノード仕様のこの様なアンバランスは、処理アンバランスの原因となり、従ってクラスターにおける顕著な効率低下の原因となる。しかし、ＨＣＡＳでは、負荷バランシングを自動的に実行することができる。
【０３２２】
当業者に理解されるように、並列処理クラスターにおける負荷バランシングのために多くの手法を利用することができる。ＨＣＡＳに利用できる１つの手法は、各処理ノードに必要な処理量を、その処理能力及び通信能力に基づいて比例的に配分することである。例えば、プロセッサクロックの遅い処理ノードには、プロセッサクロックの速い処理ノードよりも相対的に少量の処理されるべきデータを配分することができ、或いは級数展開で計算をする相対的に少数の要素を配分することができる。他の例では、２つの処理ノードが同一のプロセッサクロック速度を有するが、第１の処理ノードは第２の処理ノードの帯域幅の２倍の帯域幅を有する通信チャネルを有する。第１処理ノードは、第２処理ノードがデータを受け取るために使う時間のうちにより大量のデータを受け取ることができるので、第１処理ノードには第２処理ノードによりも多くのデータが配分される。
【０３２３】
ＨＣにおけるアルゴリズム処理要求の拡張は、メッセージサイズが小さいので通信チャネル速度による影響をあまり受けない。通信チャネル帯域幅のアンバランスに起因する問題拡張時のシステム性能のアンバランスは取るに足りない。
（別の例）
下記のセクションは、ＨＣＡＳで動作させることのできるアルゴリズムの別の例を提供する。
（並列処理のための２次元物体変換データの分解）
２次元物体の幾何学的変換は、並進運動、スケーリング、回転、及びシアリングを含む。このセクションは、一実施形態において、２Ｄ物体の幾何学的変換をＨＣでどのように実行できるか説明する。データ分割は、任意の数の並列処理ノード及び任意の大きさの物体を処理する。
【０３２４】
２Ｄ物体は、（ｘ、ｙ）平面における座標として表わされた該物体のエンドポイントにより定義される。マトリクスＭｘｙに、これらＮ個のエンドポイントをコラムベクトルとして表わさせる：
【０３２５】
【数３】
0005487128.tif 000024
エンドポイントは一様座標に変換され、第３座標を１にセットし、新しいマトリクスＭＨを作る：
【０３２６】
【数４】
0005487128.tif 000025
この一様座標への変換は、２Ｄ変換問題をマトリクス乗算に変え：ＭＴ＝Ｔ×ＭＨ、ここでＴは３×３変換マトリクスを表わし、ＭＨは一様座標の３×Ｎマトリクスとして表わされた２Ｄ物体である。得られた積ＭＴは、元の２Ｄ物体の変換を表わす。
【０３２７】
変換マトリクスＴは、変換のタイプに依存して、次のマトリクスのうちの１つに等しくなることができる：
【０３２８】
【数５】
0005487128.tif 000026
ｔｘ＝ｘ方向の並進運動オフセット
ｔｙ＝ｙ方向の並進運動オフセット
【０３２９】
【数６】
0005487128.tif 000027
ｓｘ＝ｘ方向のスケールファクター
ｓｙ＝ｙ方向のスケールファクター
【０３３０】
【数７】
0005487128.tif 000028
θ＝原点の回りの回転の角度
【０３３１】
【数８】
0005487128.tif 000029
ｓｈｘ＝ｘ方向のシアー定数
ｓｈｙ＝ｙ方向のシアー定数
２Ｄ物体変換問題は、ＨＣで実行されるマトリクス乗算問題に変わっている。任意のマトリクスが下で表２１に示されている、Ｊ個のロー及びＫ個のコラムに排列された数のアレイ。データ分割はマトリクスの要素を並列処理ノードに一様に分配する。
【０３３２】
【表２１】
0005487128.tif 000030
マトリクス乗算問題ＭＴ＝Ｔ×Ｍを考察する。ここでマトリクスＴは次元３×３を有し、マトリクスＭは次元３×Ｎを有し、結果としての積ＭＴも次元３×Ｎを有する。３×Ｎは積ＭＴのサイズを表わすものとする。マトリクス乗算のＨＣ実行では、Ｐ個の並列処理ノードは、それぞれ、Ｔ及びＭのコピーを受け取る。３×Ｎ＞Ｐと仮定し、解のサイズ３×Ｎをノードの数Ｐで割って整数の商Ｗ及び剰余Ｒを得る。Ｗ個の要素がＰ個のノードの各々に割り当てられる。剰余Ｒは、始めのＲ個のノードの各々に１要素ずつ割り当てられる。このようにして始めのＲ個のノードには総数Ｗ＋１個の要素が割り当てられ、残っているＰ−Ｒ個のノードの各々には総数Ｗ個の要素が割り当てられる。割り当てられる要素の総数は：Ｒ（Ｗ＋１）＋（Ｐ−Ｒ）Ｗ＝ＰＷ＋Ｒ＝３×Ｎである。
【０３３３】
上記のアプローチは、ノード計算負荷を１要素以内に均衡させる。
【０３３４】
７ノードＨＣでの３個のロー及び５０個のコラムから成る積マトリクスＭＴの分配を考える。この場合、整数商Ｗは１５０／７＝２１であり、剰余Ｒは３である。処理ノードＰ１からＰ３には２２個の要素がそれぞれ割り当てられ、ノードＰ４からＰ７には２１個がそれぞれ割り当てられる。マトリクスデータ分割は、総数１５０個の要素で計算され、表２２に示されている。
【０３３５】
【表２２】
0005487128.tif 000031
処理ノードＰ１は変換マトリクスＴのロー１に物体マトリクスＭのコラム１から２２を乗じて、結果の自分の部分を計算する。処理ノードＰ２は変換マトリクスＴのロー１に物体マトリクスＭのコラム２３から４４を乗じて、結果の自分の部分を計算する。処理ノードＰ３は、変換マトリクスＴのロー１及び２と物体マトリクスＭのコラム１から１６及び４５から５０とを使って自分の結果を計算する。仕事の分配は、処理ノードＰ４からＰ７に同様に分散される。
【０３３６】
ホームノードは、マトリクスデータ分割を行う。コマンド（この場合にはマトリクス乗算）とデータ分割とを記述するメッセージが処理ノードに送られる。ノードは、自分達のコマンドメッセージを受け取ると、ホームノードが入力マトリクスデータを送るのを待つ。データは、カスケード中の全てのノードがそれを同時に受け取るように、放送されて良い。この様に各ノードは両方の入力マトリクスを受け取るが、これは、各ノードに別々のメッセージと入力データの各ノードのための部分とだけを送るより効率が良い。このことは、多数の並列処理ノードを考慮するときには特に重要である。ノードは、入力マトリクスを受け取ると、他のノードとは別に積の計算を続けることができる。マトリクス乗算結果は、準備ができると、ホームノードに蓄積されて最終結果に合併される。このポイントで処理は完了する。
【０３３７】
この例が示すように、ＨＣに適用される２Ｄ物体変換データ分配は任意のサイズの物体に簡単に且つ効率的に配慮する。
（並列処理のためのマトリクス乗算データの分解）
このセクションは、ＨＣでマトリクス乗算をどのように実行できるかを説明する。説明されるマトリクス分割は、任意の数の並列処理ノードと任意の大きさのマトリクスとを処理することができる。
【０３３８】
任意のマトリクスがＭ個のローとＮ個のコラムとに排列された数のアレイとして表２３に示されている。データ分割は、マトリクスの要素を並列処理ノードに均等に分配する。
【０３３９】
【表２３】
0005487128.tif 000032
マトリクス乗算問題Ａ×Ｂ＝Ｃを考察する。ここで入力マトリクスＡは次元Ｍ×Ｎを有し、入力マトリクスＢは次元Ｎ×Ｑを有し、結果としての積Ｃは次元Ｍ×Ｑを有する。Ｅ＝Ｍ×Ｑにより積Ｃのサイズを表わす。マトリクス乗算実行時には、Ｐ個の並列処理ノードの各々はＡ及びＢのコピーを受け取る。Ｅ＞Ｐと仮定し、解のサイズＥをノードの数Ｐで割ると、整数の商Ｗと剰余Ｒとが得られる。Ｗ個の要素がＰ個のノードの各々に割り当てられる。剰余Ｒは、始めのＲ個のノードに１要素ずつ、分配される。従って、始めのＲ個のノードにはそれぞれ要素総数Ｅｉ＝Ｗ＋１が割り当てられ、残りのＰ−Ｒ個のノードには要素総数Ｅｉ＝Ｗが割り当てられる。割り当てられる要素の総数はＲ（Ｗ＋１）＋（Ｐ−Ｒ）Ｗ＝ＰＷ＋Ｒ＝Ｅに等しい。
【０３４０】
もう一度、ノード計算負荷は１要素以内に均衡される。
【０３４１】
７ノードのＨＣにおける５０個のローと５０個のコラムとから成る積マトリクスの分配を考察する。この場合、整数商Ｑは２５００÷７＝３５７であり、剰余Ｒは１である。処理ノードＰ１には３５８個の要素が割り当てられ、ノードＰ２からＰ７にはそれぞれ３５７個が割り当てられる。このマトリクスデータ分割が表２４に示されている。
【０３４２】
【表２４】
0005487128.tif 000033
処理ノードＰ１は、ロー１から７を全てのコラムについて計算し、次にロー８をコラム１から８だけについて計算し、合計３５８個の要素について計算する。Ｐ１はマトリクスＡの始めの８ローとマトリクスＢの全部とを使って、自分の結果を計算する。
【０３４３】
処理ノードＰ２は、ロー８をコラム９から５０まで、ロー９から１４を全てのコラムについて、ロー１５をコラム１から１５について計算し、合計で３５７要素を計算する。Ｐ２は、マトリクスＡのロー８から１５とマトリクスＢの全部とを使って、自分の結果を計算する。
【０３４４】
１＜ｉ≦７について、処理ノードＰｉは要素３５７（ｉ−１）＋２から３５７ｉ＋１を計算する。コラム幅５０で割ると、７ｉ−６から７ｉ＋１のローインデックス範囲がもたらされる。第１ロー、即ち７ｉ−６、はコラム７ｉ−５から５０について計算される。最後のロー、即ち７ｉ＋１、はコラム１から７ｉ＋１について計算される。残りのローは全てのコラムについて計算される。計算される要素の総数は５１−（７ｉ−５）＋６（５０）＋７ｉ＋１＝５６−７ｉ＋３００＋７ｉ＋１＝３５７に等しい。Ｐｉは、マトリクスＡのロー７ｉ−６から７ｉ＋１とマトリクスＢの全部とを使って自分の結果を計算する。
【０３４５】
ホームノードは、マトリクスデータ分割を行う。コマンド（この場合にはマトリクス乗算）とデータ分割とを記述するメッセージが処理ノードに送られる。ノードは、自分達のコマンドメッセージを受け取ると、ホームノードが入力マトリクスデータを送るのを待つ。データは、カスケード中の全てのノードがそれを同時に受け取るように、放送されて良い。この様に各ノードは両方の入力マトリクスを受け取るが、これは、各ノードに別々のメッセージと入力データの各ノードのための部分とだけを送るより効率が良い。
【０３４６】
ノードは、入力マトリクスを受け取ると、他のノードとは別に積の計算を続けることができる。マトリクス乗算結果は、準備ができると、ホームノードに蓄積されて最終結果に合併される。このポイントで処理は完了する。この例が示すように、ＨＣに適用されるマトリクスデータ分配は任意のサイズのマトリクスに簡単に且つ効率的に配慮する。
（高速フーリエ変換を用いる２次元畳み込みのための並列処理データの分解）
このセクションは、高速フーリエ変換を用いる２次元畳み込みをＨＣでどの様に分割できるかを説明する。この分割は任意の数の並列処理ノードと任意の大きさのイメージとに対処することができる。
【０３４７】
ピクセル値のＭ個のロー及びＮ個のコラムを含むイメージと、Ｊ個のロー及びＫ個のコラムを含むより小さなカーネルイメージとを考察する（Ｊ≦Ｍ，Ｋ≦Ｎ）。このイメージ及びカーネルに対して２Ｄ畳み込みを実行する効率的方法は、２Ｄ高速フーリエ変換の使用を含む。始めに、イメージのサイズと調和するようにカーネルがパッドされる。その後、イメージ及びカーネルに対して２Ｄ  ＦＦＴが別々に実行される。その結果は、要素毎に乗算され、その後に逆２Ｄ  ＦＦＴがその積に対して適用される。最終結果は、２Ｄ畳み込みを直接計算するのと同等である。
【０３４８】
任意の入力イメージとカーネルとがピクセルのアレイとしてそれぞれ表２５及び２６に示されている。各並列処理ノードはカーネル全体のコピーを受け取る。イメージはロー或いはコラムにより処理ノードに一様に分配され、ここでデータ分割をロー分配によって説明する。
【０３４９】
【表２５】
0005487128.tif 000034
【０３５０】
【表２６】
0005487128.tif 000035
入力イメージのＭ個のローはＰ個の並列処理ノードに一様に分配される。ノードに割り当てられるローは、ローインデックスと称される出発ローＩＲｉとロー総数Ｍｉとにより定められる。ローはノード間に分割されないので、ロー総数は整数に制限される。Ｍ＞Ｐと仮定して、Ｍ個のローはＰ個のノードで割られ、整数の商Ｑと剰余Ｒとが得られる。Ｐ個のノードの各々にＱ個の連続するローが割り当てられる。どんな剰余Ｒも、始めのＲ個のノードに１ローずつ分配される。従って始めのＲ個のノードには、それぞれ、総数Ｍｉ＝Ｑ＋１個のローが割り当てられ、残りのＰ−Ｒ個のノードには総数Ｍｉ＝Ｑのローが割り当てられる。割り当てられるローの総数はＲ（Ｑ＋１）＋（Ｐ−Ｒ）Ｑ＝ＰＱ＋Ｒ＝Ｍに等しい。始めのＲ個のノードについてのローインデックスＩＲｉは（ｉ−１）（Ｑ＋１）＋１である。残りのＰ−Ｒ個のノードについては、ＩＲｉは（ｉ−１）Ｑ＋Ｒ＋１に等しい。
【０３５１】
このセクションで説明されたこのアプローチは、１ロー以内に均衡されたノード計算負荷を維持する。ノードへのローのマッピングが下の表２７に示されている。
【０３５２】
【表２７】
0005487128.tif 000036
１０２４ロー及び７００コラムから成るイメージの７ノードＨＣでの分配を考察する。この場合、整数商Ｑは１０２４÷７＝１４６であり、ロー剰余Ｒは２である。処理ノードＰ１及びＰ２には１４７ローがそれぞれ割り当てられ、ノードＰ３からＰ７には１４６がそれぞれ割り当てられる。Ｐ１についてのローインデックスは１であり、Ｐ２についてのローインデックスは１４８であり、以降Ｐ７までこの様であり、Ｐ７は８７９のローインデックスを有する。
【０３５３】
ＨＣ計算の開始時に、コマンド（この場合には２Ｄ畳み込み）を記述するメッセージが処理ノードに送られる。ノードは、自分のコマンドメッセージを受け取ると、ホームノードが入力データを送るのを待つ。そのデータは、カスケード中の全てのノードがそれを同時に受け取るように、放送される。各ノードはデータセット全体を受け取るが、これは、各ノードに別々のメッセージと入力データの各ノードのための部分とだけを送るより効率が良い。
【０３５４】
ノードは、入力データを受け取ると、他のノードとは別に、自分に割り当てられたローで２Ｄ畳み込み続ける。それぞれの結果が準備できると、それらはホームノードに蓄積され、最終結果に合併される。このポイントでプロセスは完了する。
【０３５５】
この例が示すように、ＨＣに適用されるデータ分配は、任意のサイズのイメージ及びカーネルに簡単且つ効率的に配慮する。
（並列処理のための線形連立方程式の分解）
このセクションは、ＨＣで分割された線形連立方程式Ａｘ＝ｂの解を説明する。下記の分割方法は、任意の数の並列処理ノードと任意の大きさの連立方程式とを処理する。方程式Ａｘ＝ｂ、より具体的には：
【０３５６】
【数９】
0005487128.tif 000037
の解を考察する。ここでＡは係数のＮ×Ｎマトリクスであり、ｂはＮ×１のコラムベクトルであり、ｘは求められているＮ×１の解である。
【０３５７】
ｘを求めるために、Ａに対してＬＵ因数分解が行われる。ＬＵ因数分解の結果として、Ａ＝ＬＵとなるように下側三角マトリクスＬ及び上側三角マトリクスＵが得られる。元の方程式のＡに代入してＬＵｘ＝ｂ或いはＵｘ＝Ｌ−１ｂとすると、ｘも解くことができる。
【０３５８】
始めに、Ａ及びｂは、表２８に示されているようにＮ個のローとＮ＋１個のコラムとを有する単一の入力マトリクスに結合される。データ分割により、入力マトリクスのローが並列処理ノードに一様に分配される。
【０３５９】
【表２８】
0005487128.tif 000038
入力マトリクスのＮ個のローはＰ個の並列処理ノードに一様に分配される。ノードに割り当てられるローは、ローインデックスＩＲｉと称される開始ローと、ローの総数Ｎｉとにより定められる。ローはノード間に分割されないので、ロー総数は整数に制限される。Ｎ＞Ｐと仮定して、Ｎ個のローはＰ個のノードで割られ、整数の商Ｑと剰余Ｒとが得られる。Ｐ個のノードの各々にＱ個の連続するローが割り当てられる。どんな剰余Ｒも、始めのＲ個のノードに１ローずつ分配される。従って始めのＲ個のノードには、それぞれ、総数Ｎｉ＝Ｑ＋１個のローが割り当てられ、残りのＰ−Ｒ個のノードには総数Ｎｉ＝Ｑのローが割り当てられる。割り当てられるローの総数はＲ（Ｑ＋１）＋（Ｐ−Ｒ）Ｑ＝ＰＱ＋Ｒ＝Ｎに等しい。始めのＲ個のノードについてのローインデックスＩＲｉは（ｉ−１）（Ｑ＋１）＋１である。残りのＰ−Ｒ個のノードについては、ＩＲｉは（ｉ−１）Ｑ＋Ｒ＋１に等しい。
【０３６０】
このセクションで説明されたこのアプローチは、１ロー以内に均衡されたノード計算負荷を維持する。ノードへのローのマッピングが表２９に示されている。
【０３６１】
【表２９】
0005487128.tif 000039
１００ロー及び１０１コラムの入力マトリクスの７ノードＨＣでの分配を考察する。この場合、整数商Ｑは１０１００÷７＝１４４２であり、ロー剰余Ｒは６である。処理ノードＰ１からＰ６には１４４３ローがそれぞれ割り当てられ、ノードＰ７には１４４２ローが割り当てられる。Ｐ１についてのローインデックスは１であり、Ｐ２についてのローインデックスは１４４４であり、以降Ｐ７までこの様であり、Ｐ７は８６５９のローインデックスを有する。
【０３６２】
ホームノードは、このセクションのマトリクスデータ分割を実行する。コマンド（この場合には線形解）及びデータ分割は処理ノードに送られる。ノードは、自分達のコマンドメッセージを受け取ると、ホームノードが入力マトリクスデータを送るのを待つ。データは、カスケード内の全てのノードが該データを同時に受け取るように、放送される。従って各ノードはデータセット全体を受け取れるが、これは、各ノードに別々のメッセージと入力データの各ノードのための部分とだけを送るより効率が良い。
【０３６３】
ノードは、入力マトリクスを受け取ると、各反復でピボットローを決定するためにデータを共有する場合を除いて他のノードとは別に、自分に割り当てられたローで線形連立方程式を解く。個々の結果が準備できると、それらはホームノードに蓄積されて最終結果に合併される。このポイントでプロセスは完了する。
【０３６４】
この例が示すように、ＨＣに適用されるデータ分配は任意のサイズの線形連立方程式に簡単且つ効率的に配慮する。
【０３６５】
上記の明示された実施形態からのバリエーションが本書で考えられることを当業者は理解するであろう。説明は上記実施形態に制限されるべきではなくて、下記の請求項により評価されるべきである。
【図１】
0005487128.tif 000040
【図２】
0005487128.tif 000041
【図３】
0005487128.tif 000042
【図４】
0005487128.tif 000043
【図５】
0005487128.tif 000044
【図６】
0005487128.tif 000045
【図７】
0005487128.tif 000046
【図８】
0005487128.tif 000047
【図９】
0005487128.tif 000048
【図１０】
0005487128.tif 000049
【図１１】
0005487128.tif 000050
【図１２】
0005487128.tif 000051
【図１３】
0005487128.tif 000052
【図１４】
0005487128.tif 000053
【図１５】
0005487128.tif 000054
【図１６】
0005487128.tif 000055
【図１７】
0005487128.tif 000056
【図１８】
0005487128.tif 000057
【図１９】
0005487128.tif 000058
【図２０】
0005487128.tif 000059
【図２１】
0005487128.tif 000060
【図２２】
0005487128.tif 000061
【図２３】
0005487128.tif 000062
【図２４】
0005487128.tif 000063
【図２５】
0005487128.tif 000064
【図２６】
0005487128.tif 000065
【図２７】
0005487128.tif 000066
【図２８】
0005487128.tif 000067
【図２９】
0005487128.tif 000068
【図３０】
0005487128.tif 000069
【図３１】
0005487128.tif 000070
【図３２】
0005487128.tif 000071
【図３３】
0005487128.tif 000072
【図３４】
0005487128.tif 000073
【図３５】
0005487128.tif 000074
【図３６】
0005487128.tif 000075
【図３７】
0005487128.tif 000076
【図３８】
0005487128.tif 000077
【図３９】
0005487128.tif 000078
【図４０】
0005487128.tif 000079
【図４１】
0005487128.tif 000080
【図４２】
0005487128.tif 000081
【図４３】
0005487128.tif 000082
【図４４】
0005487128.tif 000083
【図４５】
0005487128.tif 000084
【図４６】
0005487128.tif 000085
【図４７】
0005487128.tif 000086
【図４８】
0005487128.tif 000087
【図４９】
0005487128.tif 000088
【図５０】
0005487128.tif 000089
【図５１】
0005487128.tif 000090
【図５２】
0005487128.tif 000091
【図５３】
0005487128.tif 000092
【図５４】
0005487128.tif 000093
【図５５】
0005487128.tif 000094
【図５６】
0005487128.tif 000095
【図５７】
0005487128.tif 000096
【図５８】
0005487128.tif 000097
【図５９】
0005487128.tif 000098
【図６０】
0005487128.tif 000099
【図６１】
0005487128.tif 000100
【図６２】
0005487128.tif 000101
【図６３】
0005487128.tif 000102
【図６４】
0005487128.tif 000103
【図６５】
0005487128.tif 000104
【図６６】
0005487128.tif 000105
【図６７】
0005487128.tif 000106
【図６８】
0005487128.tif 000107
【図６９】
0005487128.tif 000108
【図７０】
0005487128.tif 000109