(57)【要約】  並列な階層ストレージ・システムで並列データの分散および管理を調整するための方法およびコンピュータ・プログラム製品を提示する。並列データの階層マップが提供される。階層マップは、複数のマップ・オブジェクトを含み、各マップ・オブジェクトは、データの所与のアレイを、マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、またその並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述する。
2009545811.tif 000002
【特許請求の範囲】
【請求項１】
並列な階層ストレージ・システムで並列データの分散および管理を調整する方法であって、
複数のマップ・オブジェクトを含む、前記並列データの階層マップを提供することを含み、各マップ・オブジェクトが、データの所与のアレイを、前記マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、また前記並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述する方法。
【請求項２】
前記並列データにアクセスすることをさらに含み、前記アクセスすることが、前記並列データを含む前記階層の最も低いレベルに達するまで、大域アレイ・インデックスをサブアレイ・インデックスへと再帰的に変換することを含む、請求項１に記載の方法。
【請求項３】
前記階層マップ中のレベルｉにおけるマップ・オブジェクトが、レベルｉ−１の親マップ・オブジェクトにより作成されるサブアレイをどのように区分するかを記述する、請求項１に記載の方法。
【請求項４】
前記データの単一の大域ビューを提供する階層アレイを作成するために、前記データの前記階層マップおよび前記データの次元サイズを提供することをさらに含む、請求項１に記載の方法。
【請求項５】
前記階層アレイが、ツリー状構造を有しており、前記階層アレイの各レベルが、前記ストレージ階層中のレベルに割り当てられる、請求項４に記載の方法。
【請求項６】
前記階層アレイの最も低いレベルにおけるサブアレイが１つずつ処理される、請求項５に記載の方法。
【請求項７】
前記サブアレイの処理が完了したとき、前記サブアレイのデータを前記親サブアレイへとセーブすることをさらに含む、請求項６に記載の方法。
【請求項８】
前記階層アレイの最も低いレベルで、次のサブアレイのためにデータをロードすることをさらに含む、請求項７に記載の方法。
【請求項９】
アウトオブコア技法を用いて、前記ストレージ階層の隣接するレベル間のデータ移動を管理することをさらに含む、請求項１に記載の方法。
【請求項１０】
各階層アレイに対してデータ移動ポリシーを利用することをさらに含む、請求項４に記載の方法。
【請求項１１】
前記データ移動ポリシーが、最適な読取りおよび書込み性能を提供するために、動的に設定される、請求項１０に記載の方法。
【請求項１２】
データの前記分散および管理を前記調整することが、シリアル・プロセッサ・アーキテクチャ、並列プロセッサ・アーキテクチャ、および任意の深さのストレージ階層からなるグループの１つに対して行われる、請求項１に記載の方法。
【請求項１３】
並列な階層ストレージ・システムで並列データの分散および管理を調整するためのコンピュータ可読コードをその上に有するコンピュータ可読媒体であって、
複数のマップ・オブジェクトを含む、前記並列データの階層マップを提供するための命令を含み、各マップ・オブジェクトが、データの所与のアレイを、前記マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、また前記並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述するコンピュータ可読媒体。
【請求項１４】
前記並列データにアクセスするための命令をさらに含み、前記アクセスすることが、前記並列データを含む前記階層の最も低いレベルに達するまで、大域アレイ・インデックスをサブアレイ・インデックスへと再帰的に変換することを含む、請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記階層マップ中のレベルｉにおけるマップ・オブジェクトが、レベルｉ−１の親マップ・オブジェクトにより作成されるサブアレイをどのように区分するかを記述する命令をさらに含む、請求項１３に記載のコンピュータ可読媒体。
【請求項１６】
前記データの単一の大域ビューを提供する階層アレイを作成するために、前記データの前記階層マップおよび前記データの次元サイズを提供する命令をさらに含む、請求項１３に記載のコンピュータ可読媒体。
【請求項１７】
前記階層アレイが、ツリー状構造を有しており、前記階層アレイの各レベルが、前記ストレージ階層中のレベルに割り当てられる命令をさらに含む、請求項１６に記載のコンピュータ可読媒体。
【請求項１８】
前記階層アレイの最も低いレベルにおけるサブアレイが１つずつ処理される命令をさらに含む、請求項１７に記載のコンピュータ可読媒体。
【請求項１９】
前記サブアレイの処理が完了したとき、前記サブアレイのデータを前記親サブアレイへとセーブするための命令をさらに含む、請求項１８に記載のコンピュータ可読媒体。
【請求項２０】
前記階層アレイの最も低いレベルで、次のサブアレイのためにデータをロードする命令をさらに含む、請求項１９に記載のコンピュータ可読媒体。
【請求項２１】
アウトオブコア技法を用いて、前記ストレージ階層の隣接するレベル間のデータ移動を管理するための命令をさらに含む、請求項１３に記載のコンピュータ可読媒体。
【請求項２２】
各階層アレイに対してデータ移動ポリシーを利用するための命令をさらに含む、請求項１６に記載のコンピュータ可読媒体。
【請求項２３】
前記データ移動ポリシーが、最適な読取りおよび性能を提供するために、動的に設定される命令をさらに含む、請求項２２に記載のコンピュータ可読媒体。
【請求項２４】
データの前記分散および管理を前記調整することが、シリアル・プロセッサ・アーキテクチャ、並列プロセッサ・アーキテクチャ、および任意の深さのストレージ階層からなるグループの１つに対して行われる命令をさらに含む、請求項１３に記載のコンピュータ可読媒体。
【請求項２５】
メモリと、
プロセッサと、
通信インターフェースと、
前記メモリ、前記プロセッサ、および前記通信インターフェースを結合する相互接続機構とを備えるコンピュータ・システムであって、
前記プロセッサ上で実施されたときに、情報を処理するためのプロセスを提供する、並列な階層ストレージ・システムで並列データの分散および管理を調整するアプリケーションを用いて、前記メモリが符号化されており、前記プロセスが該コンピュータ・システムに、
複数のマップ・オブジェクトを含む、前記並列データの階層マップを提供するオペレーションであって、各マップ・オブジェクトが、データの所与のアレイを、前記マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、また前記並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述するオペレーションと、
前記並列データにアクセスするオペレーションであって、前記並列データを含む前記階層の最も低いレベルに達するまで、大域アレイ・インデックスをサブアレイ・インデックスへと再帰的に変換することを含むオペレーションと
を実施させるコンピュータ・システム。
【発明の詳細な説明】
【背景技術】
【０００１】
仮想メモリ・システムは、コンピュータ・プログラムに対する一貫したメモリのアドレス指定スキームを提供し、またコンピュータのほとんどのオペレーティング・システムの一般的な部分である。それらは、ユーザに非常に低コストで利益を提供するため、一般的になってきた。
【０００２】
大部分のコンピュータは、今日、ほとんどのユーザがすぐ動作するものと予測しているプログラムのすべてを同時にロードするためには、物理メモリの量が不十分である。例えば、ユーザが、オペレーティング・システム、電子メール・プログラム、ウェブ・ブラウザ、およびワード・プロセッサをメモリに同時にロードする場合、コンピュータ・メモリは、それをすべて保持するには十分ではない可能性がある。もし仮想メモリのようなものがない場合、利用可能なメモリを満たした後、コンピュータは、「すみませんが、これ以上アプリケーションをロードできません。新しいアプリケーションをロードするには、他のアプリケーションを閉じて下さい」と言う必要があるはずである。仮想メモリ・システムは、最近使用されていない物理メモリ位置を把握し、その物理位置に記憶されたデータの論理アドレス、または「仮想」アドレスを変更することなく、それらをハードディスクにコピーする。こうすることにより、新しいアプリケーションをロードするためのメモリ内空間が解放される。さらに、このコピーおよびアドレス変換は、オペレーティング・システムによって自動的に行われ、ユーザは、通常、それが生じていることさえ知らない。ハードディスク空間は、主メモリよりもはるかに安価であるため、仮想メモリを使用することはまた、経済的な利益も有する。
【０００３】
仮想メモリを物理メモリへとコピーするのを容易にするために、オペレーティング・システムは、仮想メモリを、固定数のメモリ・アドレスをそれぞれが含むページへと分割する。各ページは、それが必要になるまでディスク上に記憶される。そのページが必要となった場合、オペレーティング・システムは、それをディスクから主メモリにコピーし、仮想アドレスを物理アドレスへと変換する。ディスクから主メモリに仮想ページをコピーすることは、ページングまたはスワッピングとして知られる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許仮出願第６０／８３５，１４３号
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記で説明したものなど、従来の機構には様々な欠点がある。このような１つの欠点は、ハードドライブの読取り／書込み速度が、主メモリにアクセスするよりもはるかに遅いことであり、またハードドライブ技術は、データの小部分に、同時にアクセスするようには適合されていない。仮想メモリ・システムは汎用のアルゴリズムを使用するが、いくつかのアプリケーションには十分に適していない可能性がある。ユーザのシステムが、仮想メモリを過大に利用する必要がある場合、ユーザはかなりの性能劣化に気付くことになる。コンピュータ・システムが、ユーザが同時に作業しようとするものすべてを処理するのに十分なメモリを有しておらず、また主メモリのどのページをディスクに書き込むべきかに関して不適切な判断を行った場合、オペレーティング・システムは、メモリとハードディスクの間で行ったり来たりして、ページを絶えずスワップする必要がある。これはスラッシングとよばれ、それは、コンピュータの動作を非常に遅くするおそれがある。
【課題を解決するための手段】
【０００６】
本発明の実施形態は、このような欠点を大幅に克服し、かつ大域データ抽象化を用いて、ストレージ階層にわたるデータの分散および管理を効率的に調整するためのソフトウェア・プログラミング・モデルを提供する機構および技法を提供する。
【０００７】
並列な階層ストレージ・システムで並列データの分散および管理を調整する方法の特定の実施形態において、この方法は、複数のマップ・オブジェクトを含む、並列データの階層マップを提供することを含む。各マップ・オブジェクトは、データの所与のアレイを、マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、またその並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述する。
【０００８】
他の実施形態は、並列な階層ストレージ・システムで並列データの分散および管理を調整するためのコンピュータ可読コードをその上に有するコンピュータ可読媒体を含む。このコンピュータ可読媒体は、複数のマップ・オブジェクトを含む、並列データの階層マップを提供するための命令を含む。このコンピュータ可読媒体はさらに、各マップ・オブジェクトが、データの所与のアレイを、マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、また並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述する命令を含む。
【０００９】
さらに他の実施形態は、本発明の実施形態として本明細書に開示された方法オペレーションのすべてを処理するように構成されたコンピュータ化された装置を含む。そのような実施形態では、このコンピュータ化された装置は、メモリ・システム、プロセッサ、および通信インターフェースを、それらのコンポーネントを接続する相互接続機構中に含む。メモリ・システムは、プロセッサ上で実施されたときに（例えば実行時に）、このコンピュータ化された装置内で本明細書で説明するように動作して、本発明の実施形態として本明細書で述べる方法の実施形態およびオペレーションのすべてを実施する、本明細書で説明するエクストリーム仮想メモリを提供するプロセスで符号化される。したがって、本明細書で説明する処理を実施する、または実施するようにプログラムされたいずれのコンピュータ化された装置も本発明の実施形態である。
【００１０】
本明細書に開示された本発明の実施形態の他の構成は、上記で要約し、かつ以下で詳細に開示される方法の実施形態の諸ステップおよびオペレーションを実施するためのソフトウェア・プログラムを含む。より具体的には、コンピュータ・プログラム製品は、コンピュータ化された装置で実施されたとき、本明細書で説明するエクストリーム仮想メモリを提供する関連するオペレーションを提供する、符号化されたコンピュータ・プログラム論理をその上に含むコンピュータ可読媒体を有する１つの実施形態である。コンピュータ・プログラム論理は、コンピューティング・システムを用いて少なくとも１つのプロセッサ上で実行されたとき、本発明の実施形態として本明細書で示されるオペレーション（例えば、方法）をプロセッサに実施させる。本発明のこのような構成は、通常、光媒体（例えば、ＣＤ−ＲＯＭ）、フロッピー（登録商標）もしくはハードディスクなどのコンピュータ可読媒体、または１つまたは複数のＲＯＭもしくはメモリもしくはＰＲＯＭチップ中のファームウェアもしくはマイクロコードなど他の媒体上に構成された、または符号化されたソフトウェア、コードおよび／または他のデータ構造として、あるいはＡＳＩＣ（特定用途向けＩＣ）として、あるいは１つまたは複数のモジュール、共用ライブラリなどのダウンロード可能なソフトウェア・イメージとして提供される。ソフトウェアもしくはファームウェア、または他のこのようなコンフィギュレーションは、コンピュータ化された装置へとインストールされて、そのコンピュータ化された装置中の１つまたは複数のプロセッサに、本発明の実施形態として本明細書で説明する技法を実施させることができる。１群のデータ通信装置、または他のエンティティなど、コンピュータ化された装置の集合体中で動作するソフトウェア・プロセスはまた、本発明のシステムを提供することができる。本発明のシステムは、いくつかのデータ通信装置上の多くのソフトウェア・プロセス間で分散させることができるが、あるいはすべてのプロセスを、専用コンピュータのわずかな組で、または１つのコンピュータ単独で動作させることもできる。
【００１１】
本発明の諸実施形態は、厳密に、データ通信装置内などで、ソフトウェア・プログラムとして、ソフトウェアおよびハードウェアとして、または単独にハードウェアおよび／または回路として実施できることを理解されたい。本発明の特徴は、本明細書で述べるように、データ通信装置、コンピューティング装置、および／またはこのような装置に対するソフトウェア・システムで使用することができる。
【００１２】
前述の内容は、様々な図を通して同様の参照記号が同様の部分を指している添付の図面で示すように、本発明の好ましい実施形態の以下のさらに詳細な説明から明らかとなろう。図面は、かならずしも縮尺があっておらず、本発明の原理を説明する場合にはむしろ強調されている。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態による、階層ベクトルおよびマトリックスが、プロセッサにより近いストレージ・レベルで、どのようにより小さいサブアレイへと区分されるかを示す図である。
【図２】本発明の実施形態による、階層ベクトルを構成するために、アレイの次元情報および階層マップがどのように使用されるかの例を示す図である。
【図３】本発明の実施形態による、階層マトリックスを構成するために、アレイの次元情報および階層マップがどのように使用されるかの例を示す図である。
【図４】本発明の実施形態に従って、どのようにＭＡＴＬＡＢ、ｐＭａｔｌａｂ、およびｐＭａｔｌａｂ  ＸＶＭでベクトルを作成するかを示す図である。
【図５】本発明の実施形態に従って、ＭＡＴＬＡＢ、ｐＭａｔｌａｂ、およびｐＭａｔｌａｂ  ＸＶＭで作成される３つのベクトルをグラフィカルに示す図である。
【図６】従来のものと、ストリップマイニングのデータ・アクセス・パターンとの差を示す図である。
【図７】並列なマルチコア・プロセッサ・システムの例を示す図である。
【図８】本発明の実施形態による、各段階、ならびに関連するソフトウェアおよびハードウェア環境を示す図である。
【図９】本発明の実施形態に従って、アプリケーションに並列性および階層を徐々に追加することにより、どのようにして、開発者が単一のプロセッサから次第により並列的なハードウェアに遷移できるようになるかを示す図である。
【図１０】本発明の実施形態による、並列な階層ストレージ・システムで並列データの分散および管理を調整する方法の特定の実施形態の流れ図である。
【図１１】本発明の実施形態による、並列データの階層マップを提供する方法の特定の実施形態の流れ図である。
【発明を実施するための形態】
【００１４】
最近のデータ処理アプリケーションは、ますます大量のデータセットを扱う。これらのデータセットが、プロセッサの主メモリに適合するには大き過ぎることがしばしばある。この問題に対処するためには、２つの一般的な手法がある。それは共に、大量のデータセットを処理するための強力な方法であるが、プログラミングの複雑さをかなり増加させることになる。
【００１５】
第１の手法は、複数のプロセッサおよびメモリ・バンクを有する並列コンピュータを用いることにより、物理メモリの量を増加させることである。並列プログラミングにおける主な困難さは、各プロセッサが、それ自体のメモリ・アドレス空間を有することである。プログラマは、複数のアドレス空間にわたり、データセットを明示的に区分する必要がある。この区分は、データのどのサブセットを各プロセッサが所有するかを判定するために複雑なインデックス計算を必要とする。高い頻度で、プロセッサはまた、他のプロセッサのアドレス空間に常駐するデータにアクセスする必要があり、プロセッサ間でデータを明示的に交換するためのプログラムを必要とする。その結果、並列プログラミングは、単一のプロセッサに対するシリアル・プログラミングとは大幅に異なり、非常に重荷となり、また困難である。
【００１６】
第２の手法は、アウトオブコア・プログラミング法を用いることであり、それにより、プログラマは、物理メモリに適合するセクションへとデータを区分することができる。データは、始めは、ディスク・ストレージに常駐しており、処理のために、データのセクションは、１つずつ、プログラムによってメモリ中にロードされる。メモリとディスク間のデータ移動を管理するための一般的な技法である仮想メモリとは異なり、アウトオブコア法は、データのどのセクションをいつロードするかに対するアプリケーション制御を与える。こうすることにより高い性能が得られる。しかし、並列プログラミングと同様に、アウトオブコア技術は、プログラミング・スタイルのかなりの変更を必要とし、使用するのが非常に困難である。実際には、多くのアウトオブコア技術がまた、並列コンピュータ上でも動作するが、並列プログラミング技術のさらなる複雑さを招いている。アプリケーションは、その処理の必要性を両方の手法が満たすことをますます必要としている。これらの２つの組合せは、プログラマに特有の課題を提示する。
【００１７】
エクストリーム仮想メモリ（ＸＶＭ；ｅＸｔｒｅｍｅ  Ｖｉｒｔｕａｌ  Ｍｅｍｏｒｙ）は、大域データ抽象化を用いて、ストレージ階層にわたるデータの分散および管理を効率的に調整するためのソフトウェア・プログラミング・モデルである。ＸＶＭは、シリアルと並列のプロセッサ・アーキテクチャに適用可能であり、また任意の深さのストレージ階層に適用することができる。ＸＶＭは、メモリとディスクの間のデータ移動を透過的に管理する仮想メモリの使いやすさをエミュレートしようするので、このように名前が付けられている。
【００１８】
ＸＶＭは、ＰＧＡＳ（Ｐａｒｔｉｔｉｏｎｅｄ  Ｇｌｏｂａｌ  Ａｄｄｒｅｓｓ  Ｓｐａｃｅ；区分化大域アドレス空間）プログラミング・モデルを、アウトオブコア法と組み合わせている。ＰＧＡＳの重要な基本理念は、プログラマが、並列アプリケーションを開発するために、並列プログラミングの専門家である必要はないということである。ＰＧＡＳは、アプリケーションが、複数のメモリ・アドレス空間を単一の大域アドレス空間として見ることを可能にする。言い換えると、ＰＧＡＳは、プログラマが、シリアル・プログラムと同様に見える並列プログラムを書くことを可能にする。ＸＶＭは、ストレージ階層中のすべてのレベルに対して、アウトオブコア法を用いてＰＧＡＳモデルを拡張する。それは、アプリケーションが、複数のプロセッサ、および各プロセッサ上のストレージ階層にわたって分散されたメモリ・アドレス空間を、単一の大域アドレス空間として見ることを可能にする。
【００１９】
ＸＶＭは、ストレージの単一のレベル内に適合させるには大きすぎ、かつ複数プロセッサのストレージ階層にわたって分散させる必要のあるアレイを有するアプリケーションを対象とする。この分散は、階層マップを用いて達成される。単一のマップ・オブジェクトは、所与のアレイをどのように複数のサブアレイに区分するかを記述する。階層マップは、複数のマップから構成されており、階層マップのレベルｉにおけるマップは、レベルｉ−１におけるその親マップにより作成されるサブアレイをどのように区分するかを記述する。マップはまた、サブアレイを区分するとき、どのデータ分散（すなわち、ブロック、サイクリック、またはブロック−サイクリック）を使用するかも記述する。
【００２０】
アレイ・コンストラクタは、階層アレイを作成するための次元サイズおよび階層マップを受け入れる。階層アレイは、ＰＧＡＳインターフェースを介して、並列コンピュータのアドレス空間全体に分散されたデータの単一の大域ビューを提供する。階層アレイは、ツリー状の構造を有しており、そのアレイの各レベルは、並列コンピュータのストレージ階層のレベルに割り当てられる。図１は、階層ベクトルおよびマトリックスが、プロセッサにより近いストレージ・レベルで、どのようにより小さいサブアレイへと区分されるかを示している。階層マップのレベルｉにおけるマップは、階層アレイのレベルｉにおけるデータを、どのように区分するかを記述する。プロセッサは、リーフ・サブアレイとして知られる、階層アレイの最も低いレベルにおけるサブアレイに１つずつアクセスする。ＸＶＭは、ストレージ階層中の隣接するレベル間のデータ移動を管理するために、アウトオブコア技法を使用する。あるプロセッサが、リーフ・サブアレイで終了すると、ＸＶＭはそのサブアレイ・データを親サブアレイにセーブし、次いで、そのデータを次のリーフ・サブアレイ用にロードする。各ストレージ・レベルは、アレイをサブアレイへと区分する。プロセッサに近いレベルであるほど、アレイをより小さなサブアレイへと区分する。ストレージのその関連するレベル中には、同時に１つのサブアレイが常駐するに過ぎない。
【００２１】
図２および図３は、アレイの次元情報および階層マップが、どのように階層ベクトルおよびマトリックスをそれぞれ構成するために使用されるかに関する例を示している。
【００２２】
階層マップにより、プログラマは、現在の技術で要求されるように明示的にデータを区分するのではなく、どのようにデータを分散すべきかを暗黙的に記述することが可能になる。マップは、特定のデータ分散からアルゴリズムの実施を隔離する。その結果、アルゴリズムの実施を変更することなく、階層マップを単に変更することにより、データの分散を変更することができる。
【００２３】
いくつかの状況では、ストレージ・レベル間のデータ移動は不要である。ＸＶＭは、最適な読取りおよび書込み性能のために、異なるアクセス・パターンに調整するように、各階層アレイに対して動的に設定できるデータ移動ポリシーを導入する。これらのデータ移動ポリシーは、ストレージ・レベル間のデータ移動を阻止するために設定することができる。そのサブアレイが、それぞれロードされ、処理され、次いで、その後の計算で使用され、その結果が、他のアレイＢに記憶される階層アレイＡを考える。Ｂ中のデータだけが必要であり、Ａのコンテンツがセーブされる必要はない。したがって、Ａに対するデータ移動ポリシーは、その次のサブアレイがロードされたとき、現在のサブアレイのコンテンツを親サブアレイにセーブしないように構成することができ、したがって、性能が改善される。
【００２４】
要約すると、ＸＶＭプログラミング・モデルは、既存の方法に対していくつかの利点および改善を提供する。１つの利点は、階層アレイを用いて、システム上のすべてのストレージを単一の大域アドレス空間として見ることができることである。他の利点は、階層マップを用いて、プロセッサおよびストレージ階層に対するデータの特定のマッピングから、そのアルゴリズムを隔離できることである。さらに他の利点は、最適な性能のために、アレイごとのオブジェクト・レベルに対してデータ移動ポリシーを動的にカスタム化できることである。さらに他の利点は、並列プログラミングとアウトオブコア・プログラミング技法を共に、そのいずれの分野の専門知識を有することなく、または性能を犠牲にすることなく利用できることである。
【００２５】
ＸＶＭプログラミング・モデルは、データ・サイズが、物理メモリの全体量よりも大きいアプリケーション、従来のマイクロプロセッサ・アーキテクチャに対して高性能が必要なアプリケーション、および新たなマルチコア・マイクロプロセッサ・アーキテクチャに対するアプリケーションを含む、一連のアプリケーションに適用することができる。ＸＶＭは、これらの領域のそれぞれに対して個々に適用することができる。しかし、システムの開発では、アルゴリズム開発、アプリケーションのプロトタイピング、およびシステム実装にわたる全体の開発プロセス内で、これらのアプリケーション領域のすべてを利用することができる。
【００２６】
Ｍａｔｈｗｏｒｋｓ，Ｉｎｃ．により開発されたＭＡＴＬＡＢ（登録商標）は、数値計算を実施するための有力なプログラミング言語および開発環境であり、またアルゴリズム開発、シミュレーション、データ処理、テスト、およびシステム評価のために広く使用される。ＭＡＴＬＡＢコードの１行が、ＣまたはＦＯＲＴＲＡＮコードの１０行に取って代わるので、ユーザが達成する高い生産性によりＭＡＴＬＡＢの人気が高まっている。ｐＭａｔｌａｂは、並列のアレイおよび機能を提供するＭＡＴＬＡＢに対するＰＧＡＳライブラリであり、ユーザはほとんど努力することなくそのプログラムを並列化できるようになる。ｐＭａｔｌａｂは、マップを用いて、複数のプロセッサにわたりデータを透過的に分散させることによって、これを達成する。ｐＭａｔｌａｂ  ＸＶＭは、ＸＶＭプログラミング・モデルの最初の実施形態である。それは、ｐＭａｔｌａｂの機能を拡張して、ＭＡＴＬＡＢコードに対する最小の変更で、ＭＡＴＬＡＢプログラマに、物理メモリおよびディスク・ストレージにわたる階層アレイを構成させる。こうすることにより、最小量の努力で対処できる問題のサイズを大きく増やすことができる。例えば、ｐＭａｔｌａｂ  ＸＶＭを用いて、６４ギガポイント（１ＴＢ）の複素ＦＦＴが実証されている。
【００２７】
図４は、ＭＡＴＬＡＢ、ｐＭａｔｌａｂ、およびｐＭａｔｌａｂ  ＸＶＭにおいて、どのようにベクトルを作成するかを示している。ＭＡＴＬＡＢコードは、１６要素の０ベクトルを構成する。太字のテキストは、ｐＭａｔｌａｂにおける並列アレイ、およびｐＭａｔｌａｂ  ＸＶＭにおける階層アレイを作成するのに必要な追加部分を示す。ｐＭａｔｌａｂコードは、ベクトルをどのように分散させるかを記述するマップ・オブジェクト、ｇｌｏｂａｌ＿ｍａｐを構成する。マップ・コンストラクタへの第１の引き数［４  １］は、ベクトルを４つのプロセッサに分散する。第２の引き数｛  ｝は、デフォルトのデータ分散、すなわち、ブロックを設定する。第３の引き数０：３は、０から３のプロセッサにベクトルを設定する。ｐＭａｔｌａｂ  ＸＶＭコードは、各プロセッサ上のデータを、どのようにディスク上に常駐するサブアレイへと分割すべきかを記述するさらなるマップ、ｏｏｃ＿ｍａｐを構成する。第１の引き数［２  １］は、各プロセッサ上のデータを２つのサブアレイへと分散させる。第２の２つの引き数、すなわち、２組の｛  ｝は、データの分散およびデータの移動ポリシーをそのデフォルト値に設定する。最後に、ｇｌｏｂａｌ＿ｍａｐに対するマップ・コンストラクタは、ｏｏｃ＿ｍａｐを受け入れ、階層マップが得られる。図５は、その３つのベクトルをグラフィカルに示している。
【００２８】
ＸＶＭモデルは、ＨＰＥＣ（ｈｉｇｈ  ｐｅｒｆｏｒｍａｎｃｅ  ｅｍｂｅｄｄｅｄ  ｃｏｍｐｕｔｉｎｇ；高性能組込みコンピューティング）システムに適用することができる。例えば、一般的な最適化技法はデータ・ストリップマイニングである。図６は、従来のものと、ストリップマイニングのデータ・アクセス・パターンとの差を示す。多くの信号処理アルゴリズムは、例えば、ビデオ・フレームなど、１組のデータを順次に処理するオペレーションの連鎖から構成される。通常、フレームはキャッシュ・サイズよりもはるかに大きい。フレーム全体に各オペレーションを順次に適用するのではなく、そのフレームは、キャッシュ内に適合するセクションへと分解される。全体の処理連鎖は、単一のセクションに適用され、次いで、各セクションに対して繰り返される。データの各セクションは、全体の処理連鎖を通してキャッシュ中に存在し、性能を大きく改善する。
【００２９】
現在、ストリップマイニングは手動で実施される。プログラマは、キャッシュ中に適合できるデータのセクション・サイズを注意深く計算し、次いで、データセットに対して反復する場合、アレイ中にポインタを操作する。ＸＶＭは、ストリップマイニングを実施するためのさらにいっそう簡単な機構を提供する。プログラマは、キャッシュ内に適合するようなサイズのサブアレイを含む階層アレイを構成することができる。さらに、ＸＶＭは、サブアレイにわたって反復するための簡単なインターフェースを提供し、それは、処理されるキャッシュ中に新しいデータをロードする。
【００３０】
ＶＳＩＰＬ＋＋（Ｖｅｃｔｏｒ  Ｓｉｇｎａｌ  ａｎｄ  Ｉｍａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ  Ｌｉｂｒａｒｙ；ベクトル信号および画像処理ライブラリ）のＣ＋＋実装は、シリアルおよび並列ＨＰＥＣシステムを共に対象とする業界標準のＰＧＡＳライブラリである。ｐＭａｔｌａｂと同様に、ＶＳＩＰＬ＋＋は、マップを用いて、シリアル・プログラムに並列性を追加する。ＶＳＩＰＬ＋＋を、階層アレイをサポートするようにＸＶＭモデルを用いて拡張することになるが、ＶＳＩＰＬ＋＋ＸＶＭライブラリも作成することが可能であり、ストリップマイニングなどのキャッシュ最適化技法を、プログラマが容易に利用できるようになる。
【００３１】
図７は、並列なマルチコア・プロセッサ・システムの例を示す。プロセッサ・ベンダは、性能を高めるために、ますます、単一のチップ上に複数のプロセッサを使用するマルチコア・アーキテクチャを設計している。しかし、各ベンダは、異なるプログラミング・インターフェースを有しており、その結果、プログラマがベンダごとに新しいＡＰＩを学ぶ必要がある。さらに、異なるベンダのＡＰＩは、遠隔手続き呼出しに対するスレッドからプログラミング言語拡張にわたる異なるプログラミング・モデルを実装している。このＡＰＩおよびプログラミング・モデルの拡散は、マルチコア・アーキテクチャを採用する場合の重大な障害である。
【００３２】
ＸＶＭプログラミング・モデルは、マルチコア・プロセッサをプログラミングするのによく適している。通常、各サブプロセッサは、ローカルメモリのそれ自体の小さなバンクを有しており、複数のサブプロセッサが、主メモリのより大きなバンクを共用する。ＸＶＭは、複数のマルチコア・プロセッサにわたって分散された階層アレイを構成するために使用することができる。各マルチコア・プロセッサ上で、データは、複数のサブプロセッサにわたって分散され、かつサブプロセッサのローカルおよび主メモリにわたっており、マルチコア・プロセッサにわたる単一の大域アドレス空間を作成する。階層アレイを用いることは、マルチコア・プロセッサをプログラムするために学習する障壁を大幅に低減する。
【００３３】
前のセクションで提案したＶＳＩＰＬ＋＋ＸＶＭライブラリはまた、マルチコア・アーキテクチャに対して実装することもできる。異なるマルチコア・アーキテクチャ上にＶＳＩＰＬ＋＋ＸＶＭを実装することは、様々なベンダのライブラリに、一様なインターフェースを提供することになる。それは、マルチコア・アーキテクチャのプログラム可能性を高めると同時に、マルチコア・プロセッサ上でアプリケーションを実施することへの障壁を下げるはずである。
【００３４】
いずれのマイクロプロセッサベースのシステム開発も、同様の基本プロセスにしたがう。以下では、各段階に対する異なるソフトウェアおよびハードウェア要件を述べる。
【００３５】
アルゴリズム開発−データ処理アルゴリズムを開発し検証する。高速なプロトタイピングを可能にする高い生産性のソフトウェア環境が望ましい。そのソフトウェア環境を動作させ得る任意のハードウェアを使用することができる。
【００３６】
アプリケーションのプロトタイピング−データ処理アプリケーションのプロトタイプを作る。普通は、最終的な実装形態と同じプログラミング言語を使用する。通常、開発中に利用可能なターゲット・ハードウェア・プラットフォームは、いくつかあるに過ぎない。その解決策は、代理のハードウェア・プラットフォーム上で開発することである。
【００３７】
システム実装−ターゲット・プラットフォーム上にアプリケーションを実装すること。アプリケーションのプロトタイピングにおけるものと同じプログラミング言語を使用するにもかかわらず、この段階では、代理プラットフォームとターゲット・プラットフォームとの間の差を解決する必要がある。
【００３８】
ＸＶＭは、マルチコア・プロセッサベースのシステムを開発する場合、これらの段階のすべてに適用することができる。ＩＢＭのＣｅｌｌ  Ｂｒｏａｄｂａｎｄ  Ｅｎｇｉｎｅアーキテクチャに基づくシステムを開発することを考える。アルゴリズムは、ｐＭａｔｌａｂ  ＸＶＭで開発され、かつ検証される。アルゴリズム開発が完了すると、アプリケーションは、例えば、ＰｏｗｅｒＰＣベースのコンピュータのクラスタ上でプロトタイプが作られる。プロトタイプは、ＶＳＩＰＬ＋＋ＸＶＭライブラリのＰｏｗｅｒＰＣ実装を用いて書き込まれる。最後に、ＶＳＩＰＬ＋＋ＸＶＭライブラリのＣｅｌｌ実装を用いてターゲット・プラットフォームに移植される。図８は、これらの各段階、ならびに関連するソフトウェアおよびハードウェア環境を示す。
【００３９】
この開発プロセスは、２つの理由で、マイクロプロセッサベースのシステムを開発する現在の方法からの大きな脱却である。第１にプロセスのすべての段階が、ＸＶＭプログラミング・モデルを使用する。その結果、それぞれで開発されたアプリケーションは、構造的な類似性を共用し、段階間の遷移を簡単化する。アルゴリズムの開発およびアプリケーションのプロトタイピングでｐＭａｔｌａｂ  ＸＶＭおよびＶＳＩＰＬ＋＋ＸＶＭを使用することは、アルゴリズムと、遷移されるアルゴリズムのデータ構造とを共にプロトタイプへと遷移させることができる。アプリケーションのプロトタイピングおよびシステム実装の両方でＶＳＩＰＬ＋＋ＸＶＭを使用することは、アプリケーションをターゲット・プラットフォームに移植することを非常に簡単化する。
【００４０】
第２に、ＸＶＭは、本質的に、アプリケーションを再書込みすることなく、並列および階層構造を徐々に追加することができる。プログラマは、最初に、シリアル・プログラムを開発し、マップを用いて並列性を追加し、次いで、階層マップを用いて階層を追加することができる。例えば、アルゴリズムは、まずＭＡＴＬＡＢで開発され、ｐＭａｔｌａｂマップを追加することにより並列化され、次いで、ｐＭａｔｌａｂ  ＸＶＭ階層マップを追加することにより階層化される。プロトタイプおよび最終的なアプリケーションは、まずＶＳＩＰＬ＋＋を用いてシリアルに書き込まれ、ＶＳＩＰＬ＋＋マップを追加することにより並列化され、次いで、ＶＳＩＰＬ＋＋ＸＶＭ階層マップを追加することにより階層化され得る。図９は、アプリケーションに並列性および階層を徐々に追加することにより、どのようにして、開発者が単一のプロセッサから次第により並列的なハードウェアに遷移できるようになるかを示している。
【００４１】
現在開示された方法の流れ図が、図１０および１１に示されている。長方形のエレメントは、本明細書で「処理ブロック」を示しており、コンピュータのソフトウェア命令または命令群を表している。代替的には、処理ブロックは、デジタル信号プロセッサ回路またはＡＳＩＣ（特定用途向けＩＣ）など、機能的に等価な回路により実施される諸ステップを表す。流れ図は、いずれかの特定のプログラミング言語のシンタックスを示すものではない。そうではなくて、流れ図は、当業者が、本発明により必要な処理を実施するための回路を製作するために、またはコンピュータ・ソフトウェアを生成するために必要とする機能情報を示している。ループおよび変数の初期化、一時的数値変数の使用など、多くの定型化されたプログラム要素は示されていないことに留意されたい。本明細書でその他の形で示さない限り、述べられた諸ステップの特定のシーケンスは例示的なものに過ぎず、本発明の趣旨を逸脱することなく変更できることが、当業者であれば理解されよう。したがって、その他の形で述べられない限り、以下で述べる諸ステップは順序が定められておらず、可能な場合、諸ステップは、任意の便宜的または望ましい順序で実施できることを意味する。
【００４２】
図１０を次に参照すると、並列な階層ストレージ・システムで並列データの分散および管理を調整する方法１００の特定の実施形態が示されている。方法１００は、複数のマップ・オブジェクトを含む、並列データの階層マップを提供することを開示する処理ブロック１０２から開始する。さらに処理ブロック１０４で述べるように、各マップ・オブジェクトは、データの所与のアレイを、マップ・オブジェクトの親マップ・オブジェクトにより作成される、データの複数のサブアレイへとどのように区分するか、またその並列データを、どのように並列コンピュータのストレージ階層へと記憶するかを記述する。
【００４３】
処理ブロック１０６は、並列データにアクセスすることを述べており、そのアクセスは、並列データを含む階層の最も低いレベルに達するまで、大域アレイ・インデックスをサブアレイ・インデックスへと再帰的に変換することを含む。
【００４４】
処理ブロック１０８では、階層マップ中のレベルｉにおけるマップ・オブジェクトが、レベルｉ−１の親マップ・オブジェクトにより作成されるサブアレイをどのように区分するかを記述することが述べられている。マップはまた、サブアレイを区分するとき、どのデータ分散（すなわち、ブロック、サイクリック、またはブロック−サイクリック）を使用すべきかを記述する。階層マップにより、プログラマは、現在の技術で要求されるようにデータを明示的に区分するのではなく、どのようにデータを分散させるかを暗黙的に記述することが可能になる。マップは、アルゴリズムの実施を特定のデータ分散から隔離する。
【００４５】
処理は、処理ブロック１１０に進み、それは、データの単一の大域ビューを提供する階層アレイを作成するために、データの階層マップ、およびデータの次元サイズを提供することを開示する。階層アレイは、ツリー状の構造を有しており、アレイ中の各レベルは、並列コンピュータのストレージ階層中のレベルに割り当てられる。
【００４６】
処理ブロック１１２は、アウトオブコア技法を用いて、ストレージ階層の隣接するレベル間のデータ移動を管理することを述べる。ＸＶＭは、ストレージ階層の隣接するレベル間のデータ移動を管理するために、アウトオブコア技法を用いる。プロセッサが、リーフ・サブアレイで終了したとき、ＸＶＭは、そのサブアレイのデータを親サブアレイへとセーブし、次いで、次のリーフ・サブアレイのためにデータをロードする。
【００４７】
処理ブロック１１４は、データの分散および管理を調整することが、シリアル・プロセッサ・アーキテクチャ、並列プロセッサ・アーキテクチャ、および任意の深さのストレージ階層からなるグループの１つに対して行われることを開示する。
【００４８】
図１１を次に参照すると、階層アレイを作成し、かつ利用する特定の方法が示されている。方法２００は、処理ブロック２０２から開始し、それは、データの単一の大域ビューを提供する階層アレイを作成するために、データの階層マップおよびデータの次元サイズを提供することを開示する。階層アレイは、ツリー状構造を有しており、アレイ中の各レベルは、並列コンピュータのストレージ階層中のレベルに割り当てられる。
【００４９】
処理ブロック２０４は、階層アレイがツリー状構造を有しており、階層アレイの各レベルが、ストレージ階層のレベルに割り当てられていることを述べている。処理ブロック２０６は、階層アレイの最も低いレベルにおけるサブアレイが、１つずつ処理されることを開示する。
【００５０】
処理ブロック２０８は、サブアレイの処理が完了したとき、サブアレイのデータを親サブアレイへとセーブすることを述べる。処理ブロック２１０は、階層アレイの最も低いレベルにおける次のサブアレイのためにデータをロードすることを述べている。
【００５１】
処理ブロック２１２は、各階層アレイに対してデータ移動ポリシーを利用することを開示する。処理ブロック２１４は、データ移動ポリシーが、最適な読取りおよび書込み性能を提供するように動的に設定されることを述べている。
【００５２】
本発明の好ましい諸実施形態を述べてきたが、これらの概念を組み込む他の諸実施形態を使用できることが、いまや当業者には明らかであろう。さらに、本発明の一部として含まれるソフトウェアは、コンピュータで使用可能な媒体を含むコンピュータ・プログラム製品で実施することができる。例えば、このようなコンピュータで使用可能な媒体は、コンピュータ可読プログラム・コード・セグメントをその上に記憶させたハードドライブ装置、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、またはコンピュータ・ディスケットなどの読取り可能なメモリ装置を含むことができる。コンピュータ可読媒体はまた、デジタルまたはアナログ信号として、プログラム・コード・セグメントをその上で搬送する光、有線、または無線の通信リンクを含むこともできる。したがって、本発明は、前述の実施形態に限定されるのではなく、添付の請求項の趣旨および範囲によってのみ限定されるべきであることを提示する。
【図１】
2009545811.tif 000003
【図２】
2009545811.tif 000004
【図３】
2009545811.tif 000005
【図４】
2009545811.tif 000006
【図５】
2009545811.tif 000007
【図６】
2009545811.tif 000008
【図７】
2009545811.tif 000009
【図８】
2009545811.tif 000010
【図９】
2009545811.tif 000011
【図１０】
2009545811.tif 000012
【図１１】
2009545811.tif 000013
【国際調査報告】
2009545811.tif 000014
2009545811.tif 000015
2009545811.tif 000016