並列ライブラリとグリッドコンピューティング

丸山悠樹

平成 14 年 5 月 1 日

1 並列ライブラリ

1.1 OpenMP

1.1.1 OpenMP とは

OpenMP とは共有メモリ型マルチプロセッサ向けの並列プログラミング標準化インターフェースのことである。 OpenMP のプログラミングは、 C、 C++、 Fortran などのベース言語に並列実行や同期を指示する指示文を記述することによって行う。また、コンパイルオプションにより、指示文を無視することで逐次実行が可能なので、逐次版と並列版を同じソースで管理でき、デバッグもしやすいため、段階的な並列化が可能である。

1.1.2 OpenMP の概要

OpenMP は fork-join による並列実行モデルを用いている。 OpenMP で記述されたプログラムは、マスタスレッドと呼ばれる単一のスレッドで実行を開始する。マスタスレッドは並列構文が現れるまで逐次リージョンを実行する。マスタスレッドは、並列指示文に遭遇すると複数のスレッドから成るチームを作成し、そのチームのマスタになる。ワークシェアリング構文に対応するブロックは、全スレッドによって実行されなければならない。全てのスレッドにより並列に実行される部分を並列リージョンという。また、ワークシェアリング構文に no wait 指示節が指定されていなければ、ワークシェアリング構文の最後で暗黙のバリア同期をチーム内の全スレッドに対して実行し、その後の処理はマスタスレッドのみが実行を続ける。 1 つのプログラムにおいて、いくつでも並列構文を使うことができる。従って、プログラムは実行中に fork と join を繰り返すことになる 1.1.3 OpenMP を用いた簡単なプログラム例

資料の左下に OpenMP を用いた簡単なプログラムを示す。また、このプログラムを逐次プログラムとした時のソースを左上に示す。

parallel 構文 parallel 指示文は並列リージョンを定義する。並列リージョンとは、複数のスレッド (チーム) によって並列実行される部分であり、関数呼び出しも重複実行される。この指示文は並列実行を開始する基本的な構文である。パラレルリージョン内では実行時ライブラリ関数 omp get thread num() でスレッド ID を得ることができる。元のスレッドは、スレッド ID は０になり、マスタースレッドになる。

for 構文 for 指示文は直後の for ループのイタレーション (オーバーラップで実行できないループの繰り返し) を並列実行 (データ並列) する。 For ループは正規形でなくてはならず、ループ制御変数は整数型で強制的に private 属性になる。 For 構文は何も指定しなかったらブロック分割になるが、スケジュール構文を使うことで簡単に分割の指定ができる。 schedule(static,chunk size) が指定された場合、ループは chunk size で指定されたサイズのチャンク (かたまり) に分割される。生成された各チャンクは、チーム内のスレッドに割り当てられる。 chunk size が指定されない場合はイタレーションはほぼ同じサイズのチャンクに分割され、各スレッドに割り当てられる。

また、いくつかの指示文では、ユーザが指示節を用いて、そのリージョンの実行中に変数のスコープ属性を制御することができる。スコープ属性指示節は、その指示節が指定されている指示文の文脈の有効範囲にある変数のみに適応される。

shared 構文内で指定された変数がスレッド間で共有される。

private 構文内で指定された変数がスレッドごとに占有される。

1.2 MPI(Message Passing Interface)

1.2.1 メッセージパッシング方式とは

メッセージパッシング方式とは、プロセッサ間でメッセージを交信しながら並列処理を実現する方式である。並列処理では、複数のプロセッサが通信を行いながら同時に処理を進めていく。そこで問題になるのがプロセッサ間の通信となるのだが、メッセージパッシング方式ではプロセッサ間での通信をお互いのデータの送受信で行う。

そのため、「プロセッサ i 上でプロセッサ j にデータを送る。」というプロセスと「プロセッサ j 上でプロセッサ i からデータを受ける」というプロセスが必ずペアとして成り立たなければならない。このような方式の中で最も代表的なライブラリとして MPI と PVM がある。

1.2.2 MPI とは

MPI(Message Passing Interface) とは、分散メモリ環境における並列プログラミングの標準的な実装である。その名の通りメッセージパッシング方式に基づいた仕様であり、 MPI の仕様に準じた実装ライブラリは、複数存在する。その中の幾つかはフリーで配布されており、 UNIX 系を中心として Windows、 Mac とほぼ全ての OS、アーキテクチャに対応している。そのため、どのような環境においても MPI はフリーで使用することができる。

MPI の標準化への取り組みは Supercomputing’92 会議において、後に MPI フォーラムとして知られることになる委員会が結成され，メッセージ・パッシングの標準を作り始めたことで具体化した。そして Supercomputing’93 会議において草案 MPI 標準が示され、 1994 年に初めてリリースされた。

1997 年 7 月には、 MPI1.1 に対する追加訂正と説明がなされた MPI1.2 と、 MPI-1 の機能の拡張を行った MPI-2 がリリースされた。 MPI-2 への主な取り組みとしては，

• 入出力 (I/O)

• Fortrun90、 C++言語向けの枠組み

• 動的プロセス制御

• グラフィック

• 実時間対応

などが挙げられる。この中で特に注目すべきは動的プロセスの制御の導入である。これまで、 PVM では実現されていた機能であるが、 MPI-1 では実現されていなかった。この機能実現は，単に MPI のプログラミングがより高度なことが実現できるようになったというだけでなく、 PVM の優位性が一つ崩れたという意味でも重要である。 1.2.3 MPI の通信方式

MPI においてデータを交換するための通信関数には、任意の 2 つのプロセス同士だけが関わる 1 対 1 通信と、任意のグループに属するプロセスが全て関わる集団通信が用意されている。さらに、 1 対 1 通信、集団通信のそれぞれにブロッキング通信とノンブロッキング通信が用意されており、それぞれを適所で使用することができる。

ブロッキング通信ブロッキングとは、操作が完了するまで手続きから戻ることがない場合のことを意味する。この場合、各作業はその手続きが終了するまで待たされることになり効率が悪くなる場合がある。例えば送信、受信が宣言されてから完了するまで処理は待機状態になるため、非常に無駄が多くなってしまう。ただし、各操作の完結が保証されているためノンブロッキングに比べ簡単である。

ノンブロッキング通信ノンブロッキングとは、操作が完了する前に手続きから戻ることがあり得る場合のことを意味する。送信、受信が宣言されてからも処理を継続することができるため、ブロッキング通信に比べ通信待ちの時間が少なくなり、処理時間の軽減を計ることができ、より効率の良いプログラムを作成することができる。特に、非同期通信などを行う場合にはノンブロッキング通信は必要不可欠となる。しかし、操作の完了が保証されていないため、ノンブロッキング通信を完了するための関数 (MPIWait()) を呼び出す必要がある。基本的には 1 対 1 通信のみにしかノンブロッキング通信は存在しない。

1.2.4 MPI を用いた簡単なプログラム例

資料の右ページに OpenMP の代わりに MPI を用いた簡単なプログラムを示す。プログラム中の MPI 関数は次の様になっている。

MPI_Init(&argc,&argv)

MPI ライブラリを利用するための準備（初期化）。

MPI_Comm_size(MPI_COMM_WORLD,
          &node_size)

コミュニケータ (お互いに通信を行うプロセスの集合) 内のプロセスの数を取得。この関数により node_size にはプロセス数が入力される。

MPI_Comm_rank(MPI_COMM_WORLD,

&node_id) コミュニケータ内の各プロセスが自分の rank(コミュニケータ内の全てのプロセスは、プロセスが初期化されたときにシステムによって示された ID をもっている。これは 0 から始まる連続した正数が割り当てられる。プログラマはこれを用いて、処理の分岐、あるいはメッセージの送信元や受信先を指定することができる。 ) を取得。この関数により node_id には自分の rank 番号が入力される。

MPI_Send( void *buf, int count,
     MPI Datatype datatype,
     int dest, int tag,
     MPI Comm comm )

基本的なブロックキング送信の操作を行う。送信バッファのデータを特定の受信先に送信する。 void *buf ：送信バッファの開始アドレス int count ：データの要素数

 MPI Datatype datatype ：データタイプ
 int dest ：受信先の rank

int tag ：メッセージ・タグ

 MPI Comm comm ：コミュニケータ
MPI_Recv( void *buf, int count,
       MPI Datatype datatype,
       int source, int tag,
       MPI Comm comm,
       MPI Status *status )

要求されたデータを受信バッファから取り出す。またそれが可能になるまで待つ。 void *buf ：受信バッファの開始アドレス

 int source ：送信元の rank

int tag ：メッセージ・タグ (メッセージを識別するために割り当てられた任意の整数)

 MPI Status *status ：送信元のランク

や送信時に指定されたタグの値を格納する。

     MPI_Finalize()

MPI の実行環境を終了する。

1.3 PVM(Parallel Virtual Machine)

1.3.1 PVM とは

MPI はインターフェイスの規定であるのに対して、 PVM は実装パッケージそのものである。 PVM は、 TCP/IP ネットワークで接続された何台ものコンピュータを仮想的に 1 台のマシンととらえて、並列プログラムを走らせることのできるメッセージ・パッシングの環境とライブラリを提供する。

その歴史は、 1991 年にオークリッジ国立研究所とテネシー大学で開発に始まり、 PVM プロジェクトとして発展をしてきた。 PVM プロジェクトはその実験的性質から、副産物として科学者のコミュニティあるいはその他の分野の研究者に役立つようなソフトウェアをこれまで作り出してきている。元々は、ワークステーション・クラスタのための TCP/IP ベースの通信ライブラリであったが、現在では多くの並列計算機にも移植されている。しかしながら、 PVM では各並列計算機ベンダが独自にチューニングを施した独自の PVM を開発しており、移植性に乏しいという欠点がある。これは、 MPI フォーラムのような第三者的なしっかりとした決定機関を保有していないことに起因している。かつては分散メモリ環境では PVM が主流であったものの、現在は MPI に押されており、 Web 上における情報量も MPI と比較して圧倒的に少ないのが現状である。

1.3.2 MPI と PVM の比較

最近の動向としては、 MPI が新規格である MPI-2 の仕様において、それまでの PVM にしか無かった「動的なプロセス管理」の機能を取り入れるなど活発な動きを見せており、 MPI がかなり優勢な状況となっている。

PVM は、ワークステーションをクラスタにすることで再利用するという世界で育ってきたものである。そのために不均質ないくつものマシンやオペレーティング・システムを直接に管理する。そしてダイナミックに仮想マシンを形成することができる。 PVM のプロセス管理の機能では、アプリケーションの中から動的にプロセスを生成したり、停止したりすることができる。この機能は MPI-1 にはなく、 MPI-2 で採り入れられている。さらに利用可能なノードのグループを管理する機能では、ノード数を動的に増減したり調べたりすることができる。これは、 MPI ではまだ採り入れられていない。

しかし PVM の利用における最大の問題点は、先にも述べた移植性である。それに対して MPI は、その実装が MPP(Massively Parallel Processors) やほとんど同一な特定のワークステーション・クラスタを対象としている。 MPI は PVM の後に設計されたために、明らかに PVM における問題点を学んでいる。つまり MPI の方が PVM に比べて、高レベルのバッファ操作が可能であり、高速にメッセージを受け渡すことができる。そして、オープンなフォーラムによって達成された「標準」であるために、 MPI で作成されたプログラムは非常に移植性が高い。

2 グリッドコンピューティング

2.1 グリッドコンピューティングとは

グリッドコンピューティングとは、地理的に分散する複数のコンピュータをネットワークで網の目 (グリッド) のように結び、バーチャルな高性能コンピュータとし、ユーザーはそこから、必要な時に必要なだけの計算リソースや記憶容量を取り出して使って大規模な処理を行うという概念である。複数のコンピュータに並列処理を行わせることで、一台一台の性能は低くとも高速に大量の処理を実行できるようになる。

現在のところ、ビジネス利用や学術研究など、多くの可能性が模索され、実現に向けてさまざまな試みが行なわれている。 distributed.net や SETI@home など、インターネットを通じて家庭のパソコンの空いている CPU パワーを集め、暗号解読や医療研究などの複雑な処理を行わせる分散コンピューティングプロジェクトは既にいくつかあるが、グリッドコンピューティングはこうした技術を含む、より包括的な概念といえる。グリッド技術の普及や標準化を進めている The Global Grid Forum を始め、学術機関を中心に研究が進められていたが、最近では IBM 社が商用化を目指すプロジェクトを立ち上げている。

可能性グリッドコンピューティングは強力なコンセプトで、その主な魅力は 1 台のサーバのコンピューティングパワーを最大限に活用させることにある。現在のところ、コンピュータは作動していない時間がかなりあり、プロセッサは処理するデータを待っているような状態となっている。グリッドの世界では、停止している数百台、数千台のサーバのコンピューティングパワーを活用したり、大量の処理能力を必要とする人に「貸し出し」たりすることが可能だといわれている。重要な要素グリッドコンピューティングを実現するためには、地域的な

ものを全然意識しなくていいシームレス (seamless) であることと、ネットワーク上の各種資源をその場所を意識せずに利用できる高いトランスペアレンシ (transparency) であることが求められる。

問題点技術的問題が山ほどあるのは当然ながら、最も厄介な問題は、社会的および政治的な次元にあるといわれている。例えば、信頼関係がまるでない見ず知らずの他人の間におけるコンピューティングの共有をどのように促進すればいいのかといったことである。また、セキュリティーをどう確保するかということや、利用度に応じた料金の負担をどのように実現するかというなども問題であるといわれている。

2.2 代表的なグリッドコンピューティングシステム

Akenti(アメリカ) 分散ネットワーク環境でのスケーラブルなセキュリティサービスを提供するセキュリティモデルおよびアーキテクチャ。

Albatross(オランダ) グリッドコンピューティング環境におけるクラスタシステム (広域クラスタシステム) 上でのプログラミング方法や、高性能を得るための方法などに関する研究プロジェクト。

AppLeS(アメリカ) アプリケーションレベルでのスケジューリングに着目した研究プロジェクト。

Condor(アメリカ) 分散配置された多数のワークステーション等を使って高スループットな計算を行うための開発環境等の枠組みを提供するシステム。

EuroTools(ヨーロッパ)ヨーロッパ全体で高性能計算・ネットワークを利用するためのプロジェクト。

Globus(アメリカ) アメリカを中心とした、現在最も大きなプロジェクト。グリッドコンピューティング環境のソフトウェアインフラストラクチャを構築するためのツール群を提供している。

Grid Forum(世界中) グリッドコンピューティングシステムの標準化を目指し、さまざまな技術要素に関して意見交換を行う会合

IceT(アメリカ) グリッドコンピューティング環境における仮想的な計算機の併合／分割や、コードやデータの可搬性などの機能を備えたメタコンピューティングシステム。 IPG(アメリカ) コンセントにプラグを差し込むだけで誰もが電力の供給

を受けることができるのと同様に、国中／世界中の情報を簡単に引き出すことができるような枠組み、仕組みを提供するシステムに関する研究プロジェクト。

Legion(アメリカ) デスク上のパソコン／ワークステーションから世界中の資源にアクセスすることのできる、オブジェクトベースのメタシステムソフトウェアプロジェクト。

NetSolve(アメリカ) ネットワークを介して遠隔地にある科学技術計算用ライブラリを利用するためのクライアント・サーバモデルに基づくシステム。

Ninf(日本) 遠隔手続き呼出しの手法を利用し、プログラマが容易に遠隔地にあるハードウェア、ソフトウェア、データベース等を利用することのできるシステム。

PACX-MPI(ドイツ) グリッドコンピューティング環境用に拡張したMPI 通信ライブラリ。

UNICORE(ドイツ) ユーザが遠隔地にある計算資源にジョブを送信するためのシステム。

#define N
int calc(int a);
main(int argc,char *argv[])
{
 int *out,i;
 out = (int *)calloc(N,sizeof(int));
 for (i = 0;i < N;i++) {
  out[i] = calc(i);
 }
}

逐次プログラム

#define N
int calc(int a);
main(int argc,char *argv[])
{
 int *out,i;
 out = (int *)calloc(N,sizeof(int));
 #pragma omp parallel shared(out) private(i)
 {
  #pragma omp for schedule(static)
  for (i = 0;i < N;i++) {
   out[i] = calc(i);

}

 }
 free(out);
}

OpenMP プログラム

#include <mpi.h>//ヘッダファイルの読み込み
#define N
int calc(int a);
main(int argc,char *argv[])
{
 MPI_Status status;
 int node_id,node_size;
 int start,end;
 int *out,i;
 out = (int *)calloc(N,sizeof(int));
 MPI_Init(&argc,&argv);
 MPI_Comm_rank(MPI_COMM_WORLD,&node_id);//プロセス数の

取得

 MPI_Comm_size(MPI_COMM_WORLD,&node_size);//ランクの取

得

 start = node_id*(N/node_size);
 end = (node_id + 1)*(N/node_size);
 for (i = start;i < end;i++) {
  out[i] = calc(i);
 }
 if (node_id == 0) {
  for (j = 1;j < node_size;j++) {
   MPI_Recv(out+j*N/node_size,N/node_size*sizeof(int),
          MPI_INT,j,100,MPI_COMM_WORLD,&status);

}

 }
 else {
  MPI_Send(out+start,N/node_size*sizeof(int),
         MPI_INT,0,100,MPI_COMM_WORLD);
 }
 MPI_Finalize();
 free(out);
}

MPI プログラム