(57)【要約】【課題】  対称型マルチプロセッシング・クラスタ環境におけるプロセス間通信の方法を提供する。【解決手段】  対称型マルチプロセッシング（ＳＭＰ）クラスタ環境であって、ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードが多数のプロセスを含んでいる環境において、プロセス間で通信を行うための機能が提供される。この機能は、１つのＳＭＰノードにおいて、ＳＭＰノードの共用メモリを用いて、集合通信のメッセージをプロセス間でノード内転送するステップと、ノード内転送するステップに応答して、集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ並行してノード間転送するステップであって、ここでｎ又はｍのうちの少なくとも１つは１よりも大きい、ステップとを含む。並行して転送するステップは、ｎ個のＳＭＰノード又はｍ個の他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される。より具体的には、この機能は、１つのＳＭＰノードから多数の他のＳＭＰノードへ、又は多数のＳＭＰノードから１つの他のＳＭＰノードへ、又は多数のＳＭＰノードから多数の他のＳＭＰノードへ、のいずれかの様式で多数のメッセージを並行してノード間転送するステップを含む。【選択図】      図７
2009519504.tif 000002
【特許請求の範囲】
【請求項１】
複数のＳＭＰノード（１０２）を有する対称型マルチプロセッシング（ＳＭＰ）クラスタ内のプロセス（１０６）間で通信を行う方法であって、前記ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードは多数のプロセスを含み、
（ｉ）１つのＳＭＰノードにおいて、前記ＳＭＰノードの共用メモリ（１０７）を用いて、集合通信のメッセージをプロセス間でノード内転送するステップと、
（ｉｉ）前記転送するステップ（ｉ）に応答して、前記集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ並行してノード間転送するステップであって、ｎ又はｍのうちの少なくとも１つは１より大きく、前記並行して転送するステップは、前記ｎ個のＳＭＰノード又は前記ｍ個の他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される、ステップと
を含む方法。
【請求項２】
前記並行して転送するステップ（ｉｉ）は、１つのＳＭＰノードから多数の他のＳＭＰノードへ、又は多数のＳＭＰノードから１つの他のＳＭＰノードへ、又は多数のＳＭＰノードから多数の他のＳＭＰノードへ、のいずれかの様式で多数のメッセージを並行してノード間転送するステップを含む、請求項１に記載の方法。
【請求項３】
前記転送するステップ（ｉ）は、前記ＳＭＰノードにおいて、前記ＳＭＰノードの前記共用メモリを用いて、前記集合通信のメッセージを１つのプロセスから前記多数のプロセスへノード内転送するステップを含み、前記並行して転送するステップ（ｉｉ）は、前記多数のメッセージを前記ＳＭＰノードから多数の他のＳＭＰノードへ転送するステップを含み、前記多数のプロセスの各々のプロセスは、前記多数のメッセージのうちの１つのメッセージを前記多数の他のＳＭＰノードのうちの異なるＳＭＰノードに転送する、請求項１に記載の方法。
【請求項４】
前記転送するステップ（ｉ）は、前記ＳＭＰノードにおいて、前記ＳＭＰノードの前記共用メモリを用いて、メッセージを少なくとも２つのプロセスから前記ＳＭＰのリード・プロセスへノード内転送するステップを含み、前記並行して転送するステップ（ｉｉ）は、前記集合通信の前記多数のメッセージを、多数のＳＭＰノードから前記ｍ個の他のＳＭＰノードへ並行してノード間転送するステップを含み、前記転送するステップ（ｉ）は前記多数のＳＭＰノードにわたって繰り返され、前記多数のＳＭＰノードの多数のリード・プロセスは、前記集合通信の前記多数のメッセージを、前記ｍ個の他のＳＭＰノードのうちの少なくとも１つのプロセスへ並行してノード間転送する、請求項１に記載の方法。
【請求項５】
前記転送するステップ（ｉ）及び前記並行して転送するステップ（ｉｉ）に関与する前記ＳＭＰノード及びプロセスを、用いられる集合コミュニケータの作成時に予め定めるステップをさらに含む、請求項１に記載の方法。
【請求項６】
異なるＳＭＰノード及びプロセスに対して、前記転送するステップ（ｉ）及び前記並行して転送するステップ（ｉｉ）のうちの少なくとも１つを、前記集合通信が終了するまで自動的に繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記集合通信は、メッセージ・パッシング・インターフェース（ＭＰＩ）コミュニケータ内で行われる、請求項１に記載の方法。
【請求項８】
前記ｎ個のＳＭＰノード又は前記ｍ個の他のＳＭＰノードのうちの前記少なくとも１つは、前記多数のプロセスが並行転送を行うことを促進するための多数の通信チャネルを備える、請求項１に記載の方法。
【請求項９】
前記請求項のいずれか１項に記載の方法の全ステップを実行するように適合させた手段を備えるシステム。
【請求項１０】
コンピュータ・プログラムであって、該コンピュータ・プログラムがコンピュータ・システム上で実行されるとき、前記請求項のいずれか１項に記載の方法の全ステップを実行するための命令を含むコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、メッセージ処理に関し、より具体的には、対称型マルチプロセッシング（ＳＭＰ）クラスタ環境において、プロセス間で集合通信のメッセージを通信することに関する。
【背景技術】
【０００２】
対称型マルチプロセッサ（ＳＭＰ）とは、コンピュータ・システムにおけるハードウェアの一態様を指し、より具体的には、プロセッサ平面そのものの物理レイアウト及び設計に関する。そうした多数のプロセッサ・ユニットは、１つの特徴として、グローバル・メモリの共用、及びＳＭＰシステムの入力／出力（Ｉ／Ｏ）への同等なアクセスを有する。ＳＭＰクラスタとは、多数のＳＭＰシステム／ノードが並列計算のために互いに結合されている環境を指す。ＳＭＰクラスタはますます一般的になりつつあり、現在では科学的及び工学的並列計算の分野に広く設置されている。これらのクラスタ環境は、典型的には、ニューヨーク州アーモンク所在のＩｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ（ＩＢＭ）社によって提供される高性能スイッチ（ＨＰＳ）のような、低レイテンシ及び高帯域幅のスイッチ・ネットワークによって接続された何百ものＳＭＰノードを含む。各々のＳＭＰノードは、例えば、２個から６４個までのＣＰＵを有し、スイッチと単一のアダプタ性能とのあいだの隔たりを埋めるために１つより多くのスイッチ・アダプタを有することが多い。例えば、８つのＩＢＭ  Ｐｏｗｅｒ４  ＣＰＵを有するＩＢＭ  ｅＳｅｒｖｅｒ  ｐＳｅｒｉｅｓ  ６５５には、２つのスイッチ・アダプタを取り付けることができる。
【０００３】
さらなる背景として、メッセージ・パッシング・インターフェース（ＭＰＳ）規格は、次の概要を定めている。即ち、並列ジョブ中のプロセスは、ドメイン内でのメッセージの保全性を保証する通信ドメイン（又は「コミュニケータ」）内でメッセージを交換する。１つのドメインで発行されたメッセージは、別のドメインで発行されたメッセージとは干渉しない。一旦並列ジョブが開始すると、プロセスのサブセットは必要に応じて協働して別個の通信ドメインを形成することができる。
【０００４】
ＭＰＩ規格は、一組の集合通信動作を定める。ＭＰＩ集合のうちの幾つかは「ルート付き」であり、これは、メッセージのソース又はシンクのどちらかが唯一のＭＰＩプロセスであることを意味する。このような集合は、１対多数、又は多数対１の通信パターンに関するものである。最も頻繁に用いられるのは、ＭＰＩ＿ＢｃａｓｔとＭＰＩ＿Ｒｅｄｕｃｅである。ＭＰＩ＿Ｂａｒｒｉｅｒ、ＭＰＩ＿Ａｌｌｒｅｄｕｃｅ及びＭＰＩ＿Ａｌｌｔｏａｌｌといったルート付きではない集合は、多数対多数の通信パターンに関するものである。
【０００５】
ＳＭＰクラスタ上においては、集合通信（例えばＭＰＩコミュニケータのコンテキストにおいて行われる）は、通常、各々のＳＭＰノード上の高速共用メモリ通信チャネルを有利に用いる階層型メッセージ分散モデルに従う。しかしながら、スイッチ技術の急速な発展により、単一のＭＰＩプロセスは、利用可能なスイッチ・ネットワーク容量を十分には利用できないことが多い。１つのアダプタが供給できるよりも高い帯域幅を達成するためにストリッピング技術が用いられているが、レイテンシ要件を満たす助けにはなっていない。
【０００６】
【非特許文献１】「ＩＢＭ  Ｐａｒａｌｌｅｌ  Ｅｎｖｉｒｏｎｍｅｎｔ  ｆｏｒ  ＡＩＸ  ５Ｌ：  ＭＰＩ  Ｓｕｂｒｏｕｔｉｎｅ  Ｒｅｆｅｒｅｎｃｅ」Ｖｅｒｓｉｏｎ  ４、Ｒｅｌｅａｓｅ  ２、Ｍｏｄｉｆｉｃａｔｉｏｎ  １（２００５年８月）、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎ刊行。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従って、ＳＭＰクラスタ環境の集合通信のための、スイッチ／アダプタ容量が十分に利用され、共用メモリが集合動作のうちのＳＭＰ間通信部分を促進するような、新規の通信方法が望まれる。
【課題を解決するための手段】
【０００８】
対称型マルチプロセッシング（ＳＭＰ）クラスタ環境であって、ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードが多数のプロセスを含む環境において、プロセス間の通信の方法を提供することにより、従来技術の欠点が克服され、そして付加的な利点がもたらされる。この方法は、（ｉ）１つのＳＭＰノードにおいて、ＳＭＰノードの共用メモリを用いて、集合通信のメッセージをプロセス間でノード内転送するステップと、（ｉｉ）転送するステップ（ｉ）に応答して、ｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ集合通信の複数のメッセージを並行してノード間転送するステップとを含み、ここで、ｎ又はｍのうちの少なくとも１つは１よりも大きく、そして、並行して転送するステップは、ｎ個のＳＭＰノード又はｍ個の他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される。
【０００９】
改善された態様においては、並行して転送するステップ（ｉｉ）は、１つのＳＭＰノードから多数の他のＳＭＰノードへ、又は多数のＳＭＰノードから１つの他のＳＭＰノードへ、又は多数のＳＭＰノードから多数の他のＳＭＰノードへ、のいずれかの様式で多数のメッセージを並行してノード間転送するステップを含む。少なくとも１つのＳＭＰノード、又は少なくとも１つの他のＳＭＰノードの多数の通信チャネルは、多数のプロセスによる並行して転送するステップの実行を促進するために用いられる。さらに、転送するステップ（ｉ）及び並行して転送するステップ（ｉｉ）に関与するＳＭＰノード及びプロセスは、用いられるコミュニケータの作成時に定めることができる。
【００１０】
別の態様においては、対称型マルチプロセッシング（ＳＭＰ）クラスタ環境であって、ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードが多数のプロセスを含む環境において、プロセス間通信を行うためのシステムが提供される。このシステムは、１つのＳＭＰノードにおいて、ＳＭＰノードの共用メモリを用いて、集合通信のメッセージをプロセス間でノード内転送するための手段と、ノード内転送するステップに応答して、集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ並行してノード間転送するための手段とを含み、ここで、ｎ又はｍのうちの少なくとも１つは１より大きく、そして、並行して転送するステップは、少なくとも１つのＳＭＰノード又は少なくとも１つの他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される。
【００１１】
さらなる態様においては、対称型マルチプロセッシング（ＳＭＰ）クラスタ環境においてプロセス間通信を行う方法を実施するための、少なくとも１つのコンピュータにより実行可能な命令の少なくとも１つのプログラムを具体的に実施する、少なくとも１つのコンピュータにより読み取り可能な少なくとも１つのプログラム記憶装置が提供される。ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードは多数のプロセスを含む。この方法は、１つのＳＭＰノードにおいて、ＳＭＰノードの共用メモリを用いて、集合通信のメッセージをプロセス間でノード内転送するステップと、ノード内転送するステップに応答して、集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ並行してノード間転送するステップとを含み、ここで、ｎ又はｍのうちの少なくとも１つは１より大きく、そして、並行して転送するステップは、ｎ個のＳＭＰノード又はｍ個の他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される。
【００１２】
さらに、本発明の技法により付加的な特徴及び利点が実現される。本発明の他の実施形態及び態様は、ここでより詳細に説明され、本発明の特許請求の範囲の一部分と見なされる。
【００１３】
本発明として見なされる対象物は、本明細書に添付の特許請求の範囲において具体的に指摘され、明確に請求される。本発明の上述及び他の目的、特徴、及び利点は、添付の図面に関連して記述される以下の詳細な説明から明らかとなる。
【発明を実施するための最良の形態】
【００１４】
一般的に述べれば、本明細書において提供されるのは、対称型マルチプロセッシング（ＳＭＰ）クラスタ環境において、集合通信のメッセージをプロセス間で転送するための新規な通信方法である。ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードは多数のプロセスを含む。この方法は、最初に１つのＳＭＰノードにおいて集合通信のメッセージをプロセス間でノード内転送するステップを含む。このメッセージのノード内転送は、そのＳＭＰノードの共用メモリを用いて実行される。例えば、ブロードキャスト動作の際に、ＳＭＰノードのルート・プロセスがメッセージを共用メモリにストアし、次いでこれにそのＳＭＰノードの多数の他のプロセスがアクセスすることができる。ノード内転送に応答して、本通信方法は次に、集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへの並行したノード間転送をもたらし、ここで、ｎ又はｍのうちの少なくとも１つは１より大きい。この並行転送は、ｎ個のＳＭＰノードの多数のプロセス又はｍ個の他のＳＭＰノードの多数のプロセスによって実行される。ここでは以下でブロードキャスト動作に関して説明されるが、当業者であれば、示される通信方法は、ルート付き及び非ルート付きの両方の他の集合通信に容易に適用できることに気付くであろう。
【００１５】
本発明の１つ又は複数の態様を組み込んで用いる処理環境の１つの実施形態が図１に図示される。この特定の実施例においては、処理環境１００は、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎにより提供されるｐＳｅｒｉｅｓサーバなどの複数の演算又は処理ノード１０２を含み、これらは同じくＩｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＳＰスイッチ又は高性能スイッチ（ＨＰＳ）などのパケット・スイッチ・ネットワークとすることができる接続部１０４により互いに結合されている。ここでもまた、図１は例示のためだけに示されていることに留意されたい。各々の処理ノード内においては、多数のユーザ・プロセス１０６を実行する複数のプロセッサが備えられている。これらのプロセッサは、低レイテンシ及び高帯域幅の接続部を介して互いに結合され、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＡＩＸ又はＬＩＮＵＸのようなオペレーティング・システムにより管理されて、対称型マルチプロセッシング（ＳＭＰ）をもたらす。１つの実施例においては、マルチプロセッシングは、各々のスレッドが１つのプロセッサ上で稼動するマルチプロセッシング・スレッドを用いることによって可能になる。さらに、１つの実施形態においては、１つ又は複数のプロセッサは、マルチスレッドそのものを与えることができる。換言すれば、この実施例においては、１つ又は複数のプロセッサが２つのスレッドを実行することができる。他の実施例においては、１つ又は複数のプロセッサが任意の数のスレッドを実行することができる。
【００１６】
環境１００において、メッセージ・パケット又はメッセージは、共用メモリ１０７を用いて、ノード内（即ち、ＳＭＰノード内で）転送される。ＳＭＰノードの１つ又は複数のプロセス１０６がメッセージを共用メモリにストアし、次いでこれにそのＳＭＰノードの１つ又は複数の他のプロセスがアクセスすることができる。メッセージは、パケット・スイッチ・ネットワーク１０４に結合した通信アダプタ１１２を用いて、ノード間（即ちＳＭＰノードの間で）転送される。ＳＭＰノードと、その対応する通信アダプタとの間の通信は、パケットを送受信する機能を含む。１つの実施形態においては、インターフェースは、ここではＭＰＩライブラリとも呼ぶメッセージ・パッシング・インターフェース（ＭＰＩ）１１０を含む。
【００１７】
アダプタへのアクセスは、各々のＳＭＰノード内のカーネル／拡張デバイス・ドライバ１０８によって媒介される。拡張１０８は、オペレーティング・システム自体（例えば、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＡＩＸオペレーティング・システム）の権限を有する一組の機能を含む。カーネル／拡張は、ユーザ・プロセス１０６による１つ又は複数のアダプタ１１２の使用を認可し、そして必要であればユーザ・プロセスを中断する権限を有する。ユーザ・プロセス１０６は、ＭＰＩライブラリ１１０を通してアダプタ１１２と通信する。ＭＰＩライブラリは、例えば、その全体が引用によりここに組み入れられる非特許文献１に詳細に説明されている。
【００１８】
本明細書で用いられる「並列ジョブ」とは、プロセッサの集合体の上で実行される一組のプロセス又はタスクである。プロセスは、共同で問題を解決するために、協働しデータを交換する。「タスク」又は「プロセス」とは、１つ又は複数の制御フローの中のアドレス空間を含む実行プログラム（命令シーケンス）のインスタンスである。「アドレス空間」とは、プロセスが参照又はアクセスすることができる、一組の記憶位置である。「ＭＰＩコミュニケータ」とは、一群の通信プロセスを含む論理エンティティである。１つの実施例においては、コミュニケータは、コンテキストＩＤと呼ばれる識別子を用いて実施することができる。「通信ドメイン」とは、コミュニケータを構成するプロセスがメッセージを交換するコンテキストである。これは、ドメイン内で送信されたどのメッセージもそのドメイン外（即ち異なるコミュニケータ内）のプロセスには送信されないという点で、安定性及び孤立性の特性を持つ。「通信ドメイン」及び「コミュニケータ」は、ここでは交換可能なように用いられる。「集合通信」とは、コミュニケータの全メンバーが参加する必要がある動作である。
【００１９】
ここではＭＰＩ＿Ｂｃａｓｔ動作のようなＭＰＩ集合動作に関して説明されるが、示される構想は、定義により各々のノードにおいて共用メモリを含む対称型マルチプロセッシング（ＳＭＰ）クラスタ環境における、プロセス間での任意の集合通信のメッセージの転送にも容易に適用することができる。ここで示されるのは、ＳＭＰノード上の集合通信のための新規の共用メモリ・メッセージ通信方法である。この新規の方法は、多数の並行ＳＭＰ間通信を可能にする。この並行通信方法により、スイッチ／アダプタ容量はより十分に利用され、また、共用メモリの使用により、集合動作のうちのＳＭＰ間通信部分が促進される。
【００２０】
スイッチ・ネットワーク上においては、ＭＰＩ集合動作は、一般に、一連のポイント・ツー・ポイントの送信／受信通信にマッピングされる。ポイント・ツー・ポイントのメッセージは、特定の順序及びトポロジーに従って、スイッチ・リンクを介して転送される。ＭＰＩ＿Ｂｃａｓｔの実施は、メッセージがあまり大きくない場合には、最適性能のための、１つのタイプのツリー・アルゴリズムを用いることが多い。二分ツリー、二項ツリー、及び他のアルファツリーは、特に最も頻繁に用いられる。メッセージが全てのタスクに到達するのに必要な時間は、大よそ、
Ｔ＝Ｈ・（Ｌ＋Ｏ）                                ［１］
であり、ここでＬは１つのノードから別のノードへスイッチ・リンクを介してメッセージを転送するための時間である。Ｏは、ＭＰＩプロセスがメッセージを準備し、それを転送用スイッチに与えるための時間であり、Ｈはツリーの高さである。通常は、Ｈ＝Ｌｏｇ２Ｎであり、ここでＮはツリーのノードの数（ＭＰＩ＿Ｂｃａｓｔ動作に参加するＭＰＩプロセスの数）である。対数の底はＬとＯの間の関係を反映し、ＯがＬに近い場合には、最適性能は底２で達成される。Ｏが遥かに小さい場合には、底は２より大きくなる可能性があり、ツリーの高さは減ることになる。この場合には、プロセスは現行のメッセージが送出されるとすぐに次のメッセージの処理にかかる。Ｏが非常に小さい場合には、メッセージは次々に高速でディスパッチされるので、逐次化しても無害となる。別のネットワークの実施例においては、ＯはＬに近く、従って多数の親プロセスが用いられて逐次化が除去され、依然として２より大きな対数の底が採用される。
【００２１】
図２は、一般的に２００で表される、二項ツリーのＭＰＩ＿Ｂｃａｓｔ動作の１つの実施例を示す。矢印は、メッセージの転送を表す。ＭＰＩ＿Ｂｃａｓｔには１６のＭＰＩプロセス（０乃至１５で符号付けされる）が存在し、プロセス０がルートである。ツリーの高さは４である。
【００２２】
単一プロセッサのコンピュータのクラスタ上においては、上述の通信アルゴリズムは良好に動作する。しかしながら、ＳＭＰクラスタ上では、このアルゴリズムはさらなる改善なしには最適とはならないことが多い。その理由は、ＳＭＰクラスタには異なる性能特性をもった２つの異なる通信チャネル、即ち共用メモリとアダプタ・スイッチとが存在するからである。共用メモリはスイッチよりも高速である。
【００２３】
上述のアルゴリズムを用いるＳＭＰクラスタ上のＭＰＩ＿Ｂｃａｓｔの時間は、
Ｔ＝Ｈ１・（Ｌ１＋Ｏ）＋Ｈ２・（Ｌ２＋Ｏ）                  ［２］
であり、ここで
Ｈ１＝Ｌｏｇ２Ｎ                                          ［２．１］
であり、Ｎはクラスタ内のＳＭＰノードの数であり、
Ｌ１＝スイッチのレイテンシ、
Ｈ２＝Ｌｏｇ２Ｍ                                          ［２．２］
であり、ここでＭは各々のＳＭＰノード上のＭＰＩプロセスの数であり、
Ｌ２＝共用メモリのレイテンシ
である。
【００２４】
図３は、４つのＳＭＰノード３０１を有するＳＭＰクラスタ環境で実行されるＭＰＩ＿Ｂｃａｓｔ動作３００の１つの実施例を示し、ここで各々のＳＭＰノードには４つのプロセス又はタスクがあり、プロセスの合計数は１６である（ここでもまた０乃至１５で符号付けされる）。上述のアルゴリズムを用いると、Ｎ＝４、Ｍ＝４、Ｈ１＝２、及びＨ２＝２である。
【００２５】
ＳＭＰクラスタ環境のための、改善された通信アルゴリズムが開発されている。これらの通信アルゴリズムは、ＳＭＰ内では共用メモリが用いられ、ＳＭＰごとに１つのＭＰＩプロセスが、それ自体及びそのＳＭＰ上の他の全てのＭＰＩプロセスの代表としてＳＭＰ間通信に参加する階層モデルに従う。このことは、集合通信のＳＭＰ内部分と、ＳＭＰ間部分とに対して、異なる最適化を可能にする。この方法においては、共用メモリは、ポイント・ツー・ポイントのレベルではなく、集合動作レベルにおいて用いられる。例えば、ＭＰＩ＿Ｂｃａｓｔにおいて、ＳＭＰノードごとに１つのプロセスが、そのＳＭＰノード上のプロセスの代表として選択される。ルート・プロセスは、ルートＳＭＰノードと呼ばれるＳＭＰノードにおける代表である。図４のＳＭＰクラスタ環境の通信の実施例においては、最左端のＳＭＰノード４０１がルートＳＭＰノードである。代表プロセスは、初めにＳＭＰ間通信（例えば、プロセス０とプロセス８の間、プロセス８とプロセス１２の間、及びプロセス０とプロセス４の間のメッセージ通信）により、それら自体の間でＭＰＩ＿Ｂｃａｓｔを実行する。一旦ＳＭＰ間通信が完了すると、全てのＳＭＰノードで受信されたメッセージは代表プロセスのバッファから共用メモリ・バッファにコピーされ、次いで、同じＳＭＰノード上の他のプロセスがそのデータを共用メモリ・バッファから並行してコピーする。共用メモリ・バッファは、そのノード上の全てのプロセスがアクセスすることができ、従って、式［２．２］の対数の底はＭとすることができるので、ＳＭＰ内サブ・ツリーは平坦になる。このことは、所要時間を、
Ｔ＝Ｈ１・（Ｌ１＋Ｏ）＋（Ｌ２＋Ｏ）                ［３］
に減らす。
【００２６】
図４は、図３の実施例と同じＳＭＰクラスタ環境において、この通信方法４００を用いて実行されるＭＰＩ＿Ｂｃａｓｔを示す。違いは、共用メモリによるメッセージの転送が多数のプロセスによって同時に実行されることである。ＳＭＰ間通信部分は同じままである。
【００２７】
ブロードキャストされるメッセージが大規模である場合には、より小さな部分に分割して、同じ方法を用いて、１つずつ順にブロードキャストすることが可能である。他の通信アルゴリズムもまた存在する。例えば、ＭＰＩ＿Ｂｃａｓｔのルートはメッセージを小さな部分に分割し、非ルート・プロセスの各々に別個の部分を送信することができる。次いで、全てのプロセスがＭＰＩ＿Ａｌｌｇａｔｈｅｒを実行して、メッセージを完成させる。それにもかかわらず、これらの通信アルゴリズムをＳＭＰクラスタに適用する際には一般的な方法が取られる。即ち、ＳＭＰノードごとに１つのプロセスがＳＭＰ間通信に参加する。従来技術における種々の共用メモリ最適化は集合動作のＳＭＰ内部分のみに焦点を合わせている。より大規模なＳＭＰクラスタに対しては、通信のＳＭＰ間部分が全体の性能を支配しているので、上述の共用メモリ最適化による高速化効果は限られたものとなる。
【００２８】
従って、本明細書で示されるのは、性能を著しく向上させることが可能な、ＳＭＰクラスタ上の集合通信に対する新規な方法である。並行通信方法と呼ばれるこの方法は、ＳＭＰノード内での共用メモリ通信の並行性と、ＳＭＰ間のスイッチ通信の並行性との両方による利益を得る。この通信方法は小規模なメッセージの集合通信を最も向上させるものであり、各ＳＭＰノードへ／からの、十分なアダプタ及びネットワーク容量があれば、利益は大規模なメッセージにも及ぶ。
【００２９】
現在のスイッチ技術は、単一のプロセスが完全に利用できるよりも大きな帯域幅容量を与えるので、ノード上の多数のタスクが、プロセスごとに著しく性能を損失することなくアダプタ及びスイッチを並行して用いることを可能にする。１つのプロセスのみにＳＭＰ間通信をさせることは、アダプタ及びスイッチの能力に比較して、集合通信に対する全体的な性能を限られたものにする。並行通信方法は、単一のプロセスに集中すること及び十分なアダプタ／スイッチ容量を用いずに済ますことをやめることによって、ＳＭＰ間通信性能を向上させる。このことは、共用メモリ最適化を利用することによって可能となる。並行方法はまた、ＳＭＰ内段階とＳＭＰ間段階を含む。ＳＭＰ内段階においては、共用メモリの最適化は、集合レベルで実行される。ＳＭＰ間通信においては、ＳＭＰごとに１つより多くのＭＰＩプロセス（必要であれば全プロセス）が、スイッチ・ネットワークにアクセスしてメッセージの転送に参加する。従って、式［２．１］の対数の底は増加して、Ｍほどにまで大きくすることができる。特により大規模なＳＭＰノード総数に対して、ツリーはより平坦になり全体的な性能が向上する。
【００３０】
ここでもまた、ＭＰＩ＿Ｂｃａｓｔを実施例として用いると、並行通信アルゴリズムに含まれるステップは、以下の通りである。
（１）非ルートＳＭＰノード上の代表プロセスは、他のＳＭＰノードからのメッセージの受信に関与する。これは、ＭＰＩ＿Ｂｃａｓｔにおいては、各々のＳＭＰに送られるメッセージは１つだけになるからである。これは、決してＳＭＰ間通信に幾つのプロセスが参加するかに対する制限ではない。実際には、ＭＰＩ＿Ｂｃａｓｔにおいて、ＳＭＰごとに多数のプロセスがメッセージを他のＳＭＰノードに並行して送信し、ＭＰＩ＿ＲｅｄｕｃｅにおいてＳＭＰごとに多数のプロセスがメッセージを並行して受信する。ＭＰＩ＿Ｂａｒｒｉｅｒ及びＭＰＩ＿Ａｌｌｇａｔｈｅｒのような幾つかのルート付きではない集合通信においては、ＳＭＰごとに多数のプロセスが送信と受信の両方に参加する。
（２）ＭＰＩコミュニケータ作成のあいだに収集され、各々のプロセスにおいてキャッシュされるプロセス・レイアウトの知識に基づいて、ＳＭＰノードは、Ｎをクラスタ内のＳＭＰノードの数、ｍをＳＭＰ間通信に参加するように選択されたＳＭＰごとのＭＰＩプロセスの数として、高さＬｏｇｍＮのツリーに編成することができる。ｍ関連のツリーは、各々の非リーフ・ノードがｍ個の子ノードを有するＬｏｇｍＮツリーの例の１つである。全てのプロセスは、それが所属するＳＭＰの位置に基づいて、その親ＳＭＰと子ＳＭＰを推定する。
（３）ＳＭＰ内Ｂｃａｓｔは、集合レベルにわってルートＳＭＰ上のメモリを共用する。このステップの所要時間はＬ２＋Ｏである。
（４）ルートＳＭＰ上のＭ個のプロセスは、ループ内のＳＭＰ間ブロードキャストを開始する。各々の繰返しにおいて、メッセージがｍ個の子ＳＭＰノードに送信される。ｍ個の子ＳＭＰノードへのメッセージの送信は、ルートＳＭＰのｍ個のプロセスによって並行して行われる。ルートＳＭＰ上のｉ番目のプロセスは、ｊ番目の繰返しにおいて、（ｍ・ｊ＋ｉ）番目の子ＳＭＰノード上の代表プロセスにメッセージを送信する。ここで、０＜ｉ＜＝ｍ、０＜＝ｊ＜ＬｏｇｍＮである。各々の繰返しに要する時間は、Ｌ１’＋Ｏである。スイッチ／アダプタに並行してアクセスする多数のプロセスが存在するので、Ｌ１’は、Ｌ１よりも長くなる可能性がある。しかし、現代のスイッチ・アダプタは逐次化することなしに多数の並行アクセスを可能にするので、Ｌ１’はＬ１・ｍより遥かに短いはずである。
（５）非ルートＳＭＰノードにおいては、代表プロセスはメッセージを待ち、他のプロセスはＳＭＰ内Ｂｃａｓｔを待つ。一旦代表プロセスがメッセージを受信すると、代表プロセスはＳＭＰ内Ｂｃａｓｔに加わり、そのメッセージを集合レベルの共用メモリを通じて他のプロセスに渡す。ＳＭＰ間通信に、共用メモリによるノード内Ｂｃａｓｔを重ねるために、代表プロセスは、初めにメッセージを直接に共用メモリ・バッファ内に受信することができる。受信が完了すると、このＳＭＰ上の全てのｍ個のプロセスは、共用メモリ・バッファをＳＭＰ間通信のための送信バッファとして用いて、子ＳＭＰノードへのメッセージの転送を開始することができる。メッセージが子ＳＭＰノードに向けて送り出された後に、これらのプロセスは、メッセージを共用メモリ・バッファからそれら自体のユーザ指定受信バッファにコピーすることができる。
（６）ＳＭＰ内Ｂｃａｓｔの後で、非ルートＳＭＰがツリーのリーフでない場合には、そのＳＭＰのｍ個のプロセスは、ステップ（４）と同様のループに入り、メッセージを子ＳＭＰノード上の代表プロセスに送信する。
【００３１】
各々の繰返しにおいて、メッセージが到達するＳＭＰノードの数はｍ倍になり、あらゆるプロセスが行う繰返しの数は最多でＬｏｇｍＮとなる。
【００３２】
図５は、多数のノード５０１を有するＳＭＰクラスタ５００において実行され、上で略述された並行通信アルゴリズムを用いるＭＰＩ＿Ｂｃａｓｔを示す。この実施例においては、プロセス０、４、８、及び１２が選択された代表プロセスである。ｍ＝３である。ＳＭＰ間通信は並行して行われるので、ノード間ＳＭＰ転送の所要時間はＬ１＋Ｏにすぎない。これに対して図４においては、ＳＭＰ間通信には２・（Ｌ１＋Ｏ）を要する。並行通信方法は、１つのプロセスのメッセージ送信能力により制限されないので、より高い並行度が達成される。このことは、より良好なアダプタ／スイッチ利用につながる。
【００３３】
一般化されたアルゴリズムの擬似コードを以下に列挙する。この擬似コードは、プロセス０がルートであり、プロセスはＳＭＰノード上に均等に分散されることを仮定している。
rank:          rank of thisprocess,
srank:         rank ofthe SMP this process is on,
size:          total number ofprocesses,
ssize:         totalnumber of SMP nodes,
psize:         number ofprocesses per SMP, and
prank:         rank ofthis process within the SMP
base:          number ofprocesses per SMP participating inter-SMP
communication.
MPI_Bcast
if this task is non-root representative
for Cur = 1 tossize, cur multiply by (base +1) each time 
if srank is less than Cur ・ (base +1)) 
source process rank is ((srank = cur)/base) ・ psize + 
((srank - cur) mod base)
receive message from source process
break
intra-SMP Bcast through collectiveshared memory
if prank is less than base
for Cur =Cur・ (base +1) to ssize, Cur multiply by (base +1)
eachtime 
destination process rank is (Cur + srank ・ base + 
prank) ・ psize 
if the destination process rank is less than size
send message to destination.
【００３４】
上述されたように、このアルゴリズムを用いてメッセージが全てのプロセスに到達するのに要する時間は、
Ｔ＝Ｈ１’・（（Ｌ１’＋Ｏ）＋（Ｌ２＋Ｏ））＋（Ｌ２＋Ｏ）          ［４］
であり、ここでＨ１’はより平坦なツリーの高さであり、Ｈ１’＝ＬｏｇｍＮである。最右端の項は、ステップ（３）のコストである。式［４］を式［３］に比べると、ツリーのレベルごとにＳＭＰ内で費やされる追加の時間があるが、ツリーの高さが減らされるのでＳＭＰ間通信に費やされる時間はより短くなる。ｍの選択された値が、
（数７）
Ｈ１・（Ｌ１＋Ｏ）＝Ｈ１’・（Ｌ１’＋Ｏ）＞  Ｈ１’・（Ｌ２＋Ｏ）        ［５］
を満たす限り、全体的な性能は向上することになる。通常は、共用メモリのレイテンシはスイッチのレイテンシＬ１よりも遥かに小さく、上記の条件を達成することは難しくない。ｍが１に等しい場合には、アルゴリズムは従来のアルゴリズムに還元される。一方、選択されるｍをＳＭＰごとのプロセスの数より少なくする必要がなく、簡単な修正でそれをサポートすることができる。
【００３５】
図７は、対称型マルチプロセッシング・クラスタ環境において、集合のプロセス間で並行して通信するための１つの実施形態のフローチャートである。集合通信は（１つの実施例において）ＭＰＩ＿Ｂｃａｓｔである。集合中の各々のプロセスは、この図の通信方法を実施する。プロセスは、７００において開始し、集合全体（即ちプロセス群）の内部と、ユーザ・プロセスが実行されるＳＭＰノードの内部との両方における、プロセスのランクを判定する（７０５）。さらに、そのプロセスが所属するＳＭＰノードのランクが判定される。次いで、方法は、プロセスがそのＳＭＰノード上の第１のプロセスであってルート・プロセスではないか否かを判定する（７１０）。プロセスがそのＳＭＰノードの第１のプロセスであるがルート・プロセスではないと仮定すると、変数「Ｃｕｒ」が１に設定される（７１５）。Ｃｕｒはメッセージを受信したＳＭＰノードの数を記録する。次に、変数Ｃｕｒに、ＳＭＰ間通信に参加するＳＭＰノードごとのプロセスの数に１を加えたものを掛け合わせる（７２０）。方法は、そこで変数Ｃｕｒが、そのプロセスが所属するＳＭＰノードのランクより大きくなったか否かを判定する（７２５）。「いいえ」であれば、再び変数Ｃｕｒに、ＳＭＰ間通信に参加するノードごとのプロセスの数に１を加えたものを掛け合わせる。
【００３６】
変数ＣｕｒがプロセスのＳＭＰノードのランクより大きくなると、メッセージが次段のＳＭＰノードへ送信される。このＳＭＰノードのランクと変数Ｃｕｒとに基づいて、ソース・プロセスのランクが算定される（７３０）。次いで、ソース・プロセスから転送された各々のメッセージが受信される（７３５）。
【００３７】
プロセスがＳＭＰノード上の第１プロセス以外のものである場合、又は、ルート・プロセスである場合、又は、これが受信プロセスである場合には、ＳＭＰ内共用メモリによるブロードキャストが実行される（７４０）。この通信方法は、ＳＭＰ内のプロセッサのランクがＳＭＰ間通信に参加するＳＭＰノードごとのプロセッサの数より少ないか否かを判定する（７４５）。そうである場合には、ブロードキャスト通信は終了する（７６０）。そうではない場合には、方法は、変数Ｃｕｒに、ＳＭＰ間通信に参加するノードごとのプロセスの数に１を加えたものを掛け合わせ（７５０）、変数Ｃｕｒがプロセスの数より大きくなったか否かを調査する（７５５）。そうである場合には、通信方法は終了する（７６０）。そうではない場合には、このプロセスのランク及びＣｕｒに基づいて、送り先プロセスのランクが算定され（７８０）、メッセージが送り先プロセスに送信される（７８５）。その後、方法は、変数Ｃｕｒがプロセスの数より大きいか否かを判定し（７５５）、そうである場合には、処理は終了する。
【００３８】
図８は、コミュニケータ作成時において通信アルゴリズムを設定するための１つの方法を示す。ここでもやはり、コミュニケータは、互いの間で通信することが可能な一組のプロセスを表す抽象概念である。各々のプロセスは、コミュニケータを識別するためのハンドルと、そのコミュニケータ内での割り当てランクとを与えられる。コミュニケータの作成は、新規のコミュニケータのメンバーになる全てのプロセスが参加しなければならない集合動作の中で行われる。コミュニケータが作成されると、そのコミュニケータ内のメンバーの数も、各々のプロセスに割り当てられるランクも、どちらも変更することはできない。ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤのプロセス０が、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤのランク１に対してＭＰＩ＿Ｓｅｎｄを行い、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤのプロセス１が、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤのランク０からのＭＰＩ＿Ｒｅｃｖを行うときのように、全ての通信は何らかのコミュニケータのコンテキスト内で指定される。
【００３９】
ＭＰＩにおいては、全てのプロセスはＭＰＩ＿Ｉｎｉｔを呼び出す必要があり、ＭＰＩ＿Ｉｎｉｔの呼び出しが戻された後に、各々の呼び出しプロセスは、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤと呼ばれるコミュニケータを与えられ、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤ内のランクを割り当てられる。一旦コミュニケータ（即ちＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤ）が利用可能になると、以前から存在するコミュニケータを利用する動作により付加的なコミュニケータを作成して必要な通信を行うことができる。Ｎ個のプロセスを伴うＭＰＩジョブの開始時には、ジョブ開始フレームワークは、各々のプロセスが使用可能なＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤを有するのに必要とする情報を作成して、各々のプロセスに与える必要がある。
【００４０】
新規のコミュニケータ作成は、先立って作成されたコミュニケータを用いて情報を交換することができる一組のプロセスの間で集合的なものであるので、作成プロセスは、各々のプロセスに、新規のコミュニケータには何個のプロセスが存在し、そして、どれが各々のＳＭＰに所属することになるのかについての情報を与えることができ、各々のプロセスに、それが所属するＳＭＰ内でのランクを割り当てることができる。各々のＳＭＰが１つのプロセスを有するのか又は数個のプロセスを有するのかについての情報、及び、各々のＳＭＰが同じ数のプロセスを有するか否かについての情報を導き出すことができる。特定のアルゴリズムが新規のコミュニケータのサイズ及びレイアウトに適合するか否かについての判定を行うことができ、新規のコミュニケータの全てのメンバーは、その判定を記録することができる。コミュニケータ作成の最も簡単な実施例は、全てのプロセスがＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤ上のＭＰＩ＿ＣＯＭＭ＿ｄｕｐを呼び出し、各々のプロセスが、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤをミラーリングするがそれとは異なる新規のコミュニケータに関するハンドルを返される場合である。作成後は、コミュニケータ上のＭＰＩ＿Ｂｃａｓｔなどの呼び出しを行う、コミュニケータの各々のプロセスは、作成時に選択され、全てのプロセスにおいて等しく記録された通信アルゴリズムを用いることができる。
【００４１】
従って、図８を参照すると、通信アルゴリズムの選択は８００で開始し、集合内のプロセスの数及びジョブ・トポロジーなどの要素が収集される（８０５）。共用メモリを用いることができるか否かの調査が行われる（８１０）。「いいえ」である場合には変数Ａｌｇは「正規」に設定されるが、これは図３に示されるような正規の通信方法を用いるべきであることを意味する。共用メモリを用いることができると仮定すると、並行ＳＭＰ間通信が有益であるか否かの調査が行われる（８２５）。「いいえ」である場合には、変数Ａｌｇは、「共用メモリ」（ＳＨＭＥＭ）通信方法（図４に示されるような）に設定される（８３０）。並行ＳＭＰ間通信が有益であると仮定すると、変数Ａｌｇは「並行」に設定される（８３５）が、これは図５に示されるような通信方法を用いるべきであることを意味する。変数Ａｌｇが設定された後で、アルゴリズム選択は終了する（８２０）。
【００４２】
図９は、ＭＰＩ＿Ｂｃａｓｔの動作の１つの実施形態を示す。ブロードキャスト動作は９００で始まり、変数Ａｌｇを参照して、変数が「正規」、「ＳＨＭＥＭ」、又は「並行」に設定されているかを判定する（９０５）。「正規」である場合には、例えば図３の正規の非共用メモリによるブロードキャストが用いられ（９１０）、ブロードキャスト動作は終了する（９２５）。そうではなく、変数Ａｌｇが「ＳＨＭＥＭ」に設定されている場合には、図４に示されるように、ノード・リーダには非共用メモリによるブロードキャスト、ＳＭＰノード内では共用メモリによるブロードキャストが用いられる（９１５）。さらにまた、変数Ａｌｇが「並行」に設定されている場合には、ブロードキャスト動作に対して図５に示されるような並行ＳＭＰ間通信が用いられる（９２０）。
【００４３】
当業者であれば、上記の議論から、ここに説明される並行ＳＭＰ間通信方法は、ＳＭＰクラスタ上のＭＰＩ＿Ｂｃａｓｔ以外の集合通信動作に適用できることに気付くであろう。ＭＰＩ＿Ｓｃａｔｔｅｒは、全ての非ルート・プロセスがメッセージの個別の断片を取得するという点を除いて、ＭＰＩ＿Ｂｃａｓｔと同様のものである。
【００４４】
ＭＰＩ＿Ｒｅｄｕｃｅは、ＭＰＩ＿Ｂｃａｓｔに関する並行ＳＭＰ間通信アルゴリズムにおけるメッセージ転送の方向を反転させることによって、実施することができる。ＭＰＩ＿Ｂｃａｓｔにおけると同様に、ＳＭＰノードの代表プロセスとして選択された１つのプロセスが存在する。同じ子ＳＭＰノード上のプロセスは、最初に、共用メモリによりＳＭＰ内削減操作を実行するが、ここで代表プロセスはＳＭＰ内削減動作のルートである。次いで、多数のＳＭＰノードの代表プロセスは、スイッチ・ネットワークを通じて、中間の削減結果を親ＳＭＰノードの多数のプロセスに送信する。多数のプロセスの各々において、受信されたメッセージ及びローカル・メッセージに対する削減動作の結果が、ローカル・メッセージの代りとして、共用メモリＳＭＰ内削減動作に用いられる。メッセージが削減される代りに連結される場合には、ＭＰＩ＿ＲｅｄｕｃｅはＭＰＩ＿Ｇａｔｈｅｒになる。
【００４５】
ＭＰＩ＿Ａｌｌｒｅｄｕｃｅは、最初に、プロセス０をルートとするＭＰＩ＿Ｒｅｄｕｃｅを実行し、次いで、ＭＰＩ＿Ｂｃａｓｔを通じて削減結果をプロセス０から全ての他のプロセスにブロードキャストすることによって実施される。ＭＰＩ＿Ａｌｌｇａｔｈｅｒのような他のルート付きではない集合通信においては、ＭＰＩ＿Ｂｃａｓｔ又はＭＰＩ＿Ｒｅｄｕｃｅにおけるように一方向にメッセージを転送する代りに、メッセージを交換することによって、並行ＳＭＰ間通信方法を適用することができる。ＭＰＩ＿Ａｌｌｇａｔｈｅｒにおいては、全てのプロセスは、他のプロセスにブロードキャストするためのメッセージを有する。プロセスは最初に、共用メモリによりＳＭＰ内のオールギャザ（ａｌｌｇａｔｈｅｒ）を実行する。次いで、ＳＭＰ間通信に参加するプロセスの各々は、並行して、別個のＳＭＰからの１つのプロセスとメッセージを交換する。他のＳＭＰから受信されたメッセージは、動作の終了時に、また可能的にはＳＭＰ間通信の段階の間に、共用メモリのオールギャザ（ａｌｌｇａｔｈｅｒ）により、同じＳＭＰ上の他のプロセスと交換される。ＭＰＩ＿Ａｌｌｔｏａｌｌは、１つのプロセスから全ての他のプロセスへ別個のメッセージが送信されるという点でのみ、ＭＰＩ＿Ａｌｌｇａｔｈｅｒとは異なる。ＭＰＩ＿Ｂａｒｒｉｅｒは、全てのメッセージが空である、即ち、メッセージがデータを含まない場合のＭＰＩ＿Ａｌｌｇａｔｈｅｒとして実施することができる。
【００４６】
並行通信アルゴリズムのプロトタイプは、ＭＰＩ＿Ｂａｒｒｉｅｒ、ＭＰＩ＿Ｂｃａｓｔ、及びＭＰＩ＿Ｒｅｄｕｃｅに関して開発されている。Ｉｎｔｅｌ  ＭＰＩベンチマーク２．３（例えばｈｔｔｐ：／／ｗｗｗ．ｉｎｔｅｌ．ｃｏｍ／ｃｄ／ｓｏｆｔｗａｒｅ／ｐｒｏｄｕｃｔｓ／ａｓｍｏｎａ／ｅｎｇ／ｃｌｕｓｔｅｒ／ｍｐｉ／２１９８４７．ｈｔｍを参照されたい）は、８個の１６叉ＳＭＰノードのクラスタ（ＩＢＭ  ｐＳｅｒｉｅｓ  Ｎｉｇｈｔｈａｗｋ  ＩＩ）上で、プロトタイプを用いて実行されており、６４プロセス（ＳＭＰごとに８プロセス）のＭＰＩ＿Ｂｃａｓｔの性能数値が図６に示される。図３の方法は、簡単な二項ツリー・アルゴリズムである。図４の方法は、二項ツリー・アルゴリズムにＳＭＰ内での集合レベル共用メモリ最適化を加えたものである。図５の方法は、本発明の態様を用いた並行通信である。数値は図５の方法に関する著しい性能向上を示している。
【００４７】
上記の詳細な説明は、コンピュータ又はコンピュータ・ネットワーク上で実行されるプログラム手続きを用いて論じられている。これらの手続きによる説明及び表現は、当業者により、彼／彼女らの作業の実質を他の当業者に最も効果的に伝えるために用いられる。それらは、ハードウェア又はソフトウェア、又は、それら２つの組み合わせにより実施することができる。
【００４８】
ここで手続きは、そして一般的に、所望の結果に導く一連のステップであると考えられる。これらのステップは、物理的な量の物理的な取扱いを必要とするものである。必須ではないが通常は、これらの量は、ストアし、転送し、組み合わせ、比較し、及び他の仕方で取り扱うことが可能な電気信号又は磁気信号の形態を取る。主として一般的用法の理由から、これらの信号を、ビット、値、要素、シンボル、キャラクタ、項、数値、オブジェクト、属性、などにより言及することが便利な場合がある。しかしながら、これら及び類似の用語の全ては、適切な物理量と関連付けられるべきものであり、これらの物理量に付与された単に便利なラベルであることに留意されたい。
【００４９】
さらに、実行される取扱いは、しばしば、人間のオペレータによって実行される知的活動に一般に関連する、付加又は比較といった用語により言及される。殆どの場合、ここに説明される本発明の一部分を構成する操作のいずれにおいても、そのような人間のオペレータの能力は必要ではなく、望ましいものでもない。操作は機械による操作である。本発明の操作を実行するのに有用な機械は、汎用デジタル・コンピュータ又は類似の装置を含む。
【００５０】
本方法の各々のステップは、メインフレーム・コンピュータ、パーソナル・コンピュータなどの任意の一般的なコンピュータ上で実行することができ、また、例えばＣ＋＋、Ｊａｖａ、Ｆｏｒｔｒａｎなどの任意のプログラミング言語から生成される１つ又は複数のプログラム・モジュール又はオブジェクト、又はそれらの一部分に準ずるものとすることができる。さらにまた、各々のステップ、又は各々のステップを実施するファイル或いはオブジェクトなどは、専用ハードウェア、又はその目的のために設計された回路モジュールにより、実行することができる。
【００５１】
本発明は、コンピュータと通信するための高級な手続き又はオブジェクト指向プログラミング言語により実施されることが好ましい。しかしながら、本発明は、所望ならば、アセンブリ言語又は機械語により実施することができる。いかなる場合においても、言語はコンパイラ型言語又はインタープリタ型言語とすることができる。
【００５２】
本発明は、記録媒体を備えたメカニズム又はコンピュータ・プログラムとして実施することができる。このようなメカニズム又はコンピュータ・プログラムは、ＣＤ−ＲＯＭ、ディスケット、テープ、ハード・ドライブ、コンピュータＲＡＭ又はＲＯＭ、及び／又は、電子的、磁気的、光学的、生物学的、又は他の同様のプログラム実施形態を含むことができるが、これらに限定はされない。実際には、メカニズム又はコンピュータ・プログラムは、本発明の方法による、汎用又は専用のプログラム可能なコンピュータの動作を制御するための、機械により可読な信号をストア又は伝達するための、及び／又は、本発明のシステムによるコンポーネントを構築するための、磁気的又は光学的などの任意の固体又は流体の伝達媒体を含むことができる。
【００５３】
本発明は、また、システムにより実施することができる。システムは、プロセッサ及び記憶装置と、随意に、ストレージ装置と、ビデオ・ディスプレイなどの出力装置と、及び／又は、キーボード又はコンピュータ・マウスなどの入力装置とを含むコンピュータを備えることができる。さらに、システムは、相互接続されたコンピュータのネットワークを備えることができる。コンピュータは、スタンドアロン型（例えば従来のデスクトップ型パーソナル・コンピュータなど）とすること、又は別の装置（例えば電子試験装置）に組み込まれたものとすることが等しく可能である。システムは、例えば、本発明の方法ステップを実行するために、必要な目的に合わせて専用に構築してもよく、又は、コンピュータにストアされた本明細書の教示による、コンピュータ・プログラムによって選択的に起動され又は再構成される、１つ又は複数の汎用コンピュータを備えてもよい。ここに示された手続きは、本質的に、特定のコンピュータ・システム又は他の装置に関連付けられるものではない。種々のこれらのシステムに必要な構造は、与えられた説明から明白となる。
【００５４】
この場合もまた、本発明の１つ又は複数の態様の機能は、ソフトウェア、ファームウェア、ハードウェア、又はそれらの何らかの組合せにより実施することができる。
【００５５】
本発明の１つ又は複数の態様は、例えばコンピュータ使用可能媒体を有する製造品（例えば、１つ又は複数のコンピュータ・プログラム）に、含めることができる。その媒体は内部に、例えば、コンピュータ可読プログラム・コード手段又は論理（例えば、命令、コード、コマンドなど）を有し、本発明の機能を提供し促進する。製造品は、コンピュータ・システムの一部分として含めるか、又は単独で販売することができる。
【００５６】
さらに、本発明の機能を実施するために、機械により実行可能な命令の少なくとも１つのプログラムを具体化する機械によって読み取り可能な、少なくとも１つのプログラム記憶装置を提供することができる。
【００５７】
本明細書で図示された流れ図は実施例にすぎない。これらの図又はその中に記載されたステップ（又は動作）には、本発明の趣旨から逸脱することなく多数の変形が存在しうる。例えば、ステップは異なる順序で実行することができ、或いは、ステップを追加、消去若しくは修正することが可能である。これらの変形の全ては本発明の特許請求の範囲の一部分であると見なされる。
【００５８】
本明細書においては、好ましい実施形態が図示され、詳細に説明されたが、当業者には、本発明の趣旨から逸脱することなく種々の修正、追加、置換えなどを施すことが可能であることは明らかであり、従って、これらは添付の特許請求の範囲において規定される本発明の範囲内にあると見なされる。
【図面の簡単な説明】
【００５９】
【図１】本発明の１つ又は複数の態様を組み込んで用いた対称型マルチプロセッシング（ＳＭＰ）クラスタ環境の１つの実施形態の図である。
【図２】ＳＭＰ環境又は非ＳＭＰ環境において、プロセス間のメッセージの配布のために、従来の二項ツリーを用いたＭＰＩ＿Ｂｃａｓｔに関する１つの通信方法の図である。
【図３】ＳＭＰクラスタ環境内において、ＭＰＩ＿Ｂｃａｓｔメッセージの配布のために、二項ツリーを用いる別の通信方法の図である。
【図４】ＳＭＰノード間のメッセージ配布のために二項ツリーを用い、ＭＰＩ＿Ｂｃａｓｔメッセージの配布のために集合レベルのＳＭＰ内共用メモリを用いるさらに別の通信方法の図である。
【図５】本発明の１つの態様による、ＭＰＩ＿ＢｃａｓｔメッセージをＳＭＰノード内転送し、続いてメッセージを並行してＳＭＰ間転送するための、並行通信方法の１つの実施形態の図である。
【図６】本発明の特定の態様による、図３、図４、及び図５の異なるメッセージ通信方法を用いたＭＰＩ＿Ｂｃａｓｔ実行時間をメッセージのサイズに対して示す試験結果のグラフである。
【図７】本発明の１つの態様による、ＭＰＩ＿Ｂｃａｓｔメッセージを並行転送するための通信方法の１つの実施形態のフローチャートである。
【図８】本発明の１つの態様による、コミュニケータ作成時において通信アルゴリズムの選択を決定するための１つの実施形態のフローチャートである。
【図９】本発明の１つの態様による、集合通信時において、コミュニケータ作成時に選択された通信アルゴリズムを用いて通信方法を確かめるための１つの実施形態のフローチャートである。
【符号の説明】
【００６０】
１００：処理環境
１０２：処理ノード
１０４：接続、パケット・スイッチ・ネットワーク
１０６：ユーザ・プロセス
１０７：共用メモリ
１０８：カーネル／拡張デバイス・ドライバ
１１０：メッセージ・パッシング・インターフェース、ＭＰＩライブラリ
１１２：通信アダプタ
２００：二項ツリーＭＰＩ＿Ｂｃａｓｔ動作
０〜１５：ＭＰＩプロセス
３００、４００、５００：ＭＰＩ＿Ｂｃａｓｔ動作
３０１、４０１、５０１：ＳＭＰノード
【図１】
2009519504.tif 000003
【図２】
2009519504.tif 000004
【図３】
2009519504.tif 000005
【図４】
2009519504.tif 000006
【図５】
2009519504.tif 000007
【図６】
2009519504.tif 000008
【図７】
2009519504.tif 000009
【図８】
2009519504.tif 000010
【図９】
2009519504.tif 000011
【手続補正書】
【提出日】平成21年2月19日(2009.2.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のＳＭＰノード（１０２）を有する対称型マルチプロセッシング（ＳＭＰ）クラスタ内のプロセス（１０６）間で通信を行う方法であって、前記ＳＭＰクラスタのうちの少なくとも幾つかのＳＭＰノードは多数のプロセスを含み、
（ｉ）１つのＳＭＰノードにおいて、前記ＳＭＰノードの共用メモリ（１０７）を用いて、集合通信のメッセージをプロセス間でノード内転送するステップと、
（ｉｉ）前記転送するステップ（ｉ）に応答して、前記集合通信の多数のメッセージをｎ個のＳＭＰノードからｍ個の他のＳＭＰノードへ並行してノード間転送するステップであって、ｎ又はｍのうちの少なくとも１つは１より大きく、前記並行して転送するステップは、前記ｎ個のＳＭＰノード又は前記ｍ個の他のＳＭＰノードのうちの少なくとも１つにおける多数のプロセスによって実行される、ステップと
を含む方法。
【請求項２】
前記並行して転送するステップ（ｉｉ）は、１つのＳＭＰノードから多数の他のＳＭＰノードへ、又は多数のＳＭＰノードから１つの他のＳＭＰノードへ、又は多数のＳＭＰノードから多数の他のＳＭＰノードへ、のいずれかの様式で多数のメッセージを並行してノード間転送するステップを含む、請求項１に記載の方法。
【請求項３】
前記転送するステップ（ｉ）は、前記ＳＭＰノードにおいて、前記ＳＭＰノードの前記共用メモリを用いて、前記集合通信のメッセージを１つのプロセスから前記多数のプロセスへノード内転送するステップを含み、前記並行して転送するステップ（ｉｉ）は、前記多数のメッセージを前記ＳＭＰノードから多数の他のＳＭＰノードへ転送するステップを含み、前記多数のプロセスの各々のプロセスは、前記多数のメッセージのうちの１つのメッセージを前記多数の他のＳＭＰノードのうちの異なるＳＭＰノードに転送する、請求項１に記載の方法。
【請求項４】
前記転送するステップ（ｉ）は、前記ＳＭＰノードにおいて、前記ＳＭＰノードの前記共用メモリを用いて、メッセージを少なくとも２つのプロセスから前記ＳＭＰのリード・プロセスへノード内転送するステップを含み、前記並行して転送するステップ（ｉｉ）は、前記集合通信の前記多数のメッセージを、多数のＳＭＰノードから前記ｍ個の他のＳＭＰノードへ並行してノード間転送するステップを含み、前記転送するステップ（ｉ）は前記多数のＳＭＰノードにわたって繰り返され、前記多数のＳＭＰノードの多数のリード・プロセスは、前記集合通信の前記多数のメッセージを、前記ｍ個の他のＳＭＰノードのうちの少なくとも１つのプロセスへ並行してノード間転送する、請求項１に記載の方法。
【請求項５】
前記転送するステップ（ｉ）及び前記並行して転送するステップ（ｉｉ）に関与する前記ＳＭＰノード及びプロセスを、用いられる集合コミュニケータの作成時に予め定めるステップをさらに含む、請求項１に記載の方法。
【請求項６】
異なるＳＭＰノード及びプロセスに対して、前記転送するステップ（ｉ）及び前記並行して転送するステップ（ｉｉ）のうちの少なくとも１つを、前記集合通信が終了するまで自動的に繰り返すステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記集合通信は、メッセージ・パッシング・インターフェース（ＭＰＩ）コミュニケータ内で行われる、請求項１に記載の方法。
【請求項８】
前記ｎ個のＳＭＰノード又は前記ｍ個の他のＳＭＰノードのうちの前記少なくとも１つは、前記多数のプロセスが並行転送を行うことを促進するための多数の通信チャネルを備える、請求項１に記載の方法。
【請求項９】
前記請求項のいずれか１項に記載の方法の全ステップを実行するように適合させた手段を備えるシステム。
【請求項１０】
コンピュータ・プログラムであって、該コンピュータ・プログラムがコンピュータ・システム上で実行されるとき、前記請求項のいずれか１項に記載の方法の全ステップをコンピュータに実行させるための命令を含むコンピュータ・プログラム。
【国際調査報告】
2009519504.tif 000012
2009519504.tif 000013
2009519504.tif 000014