2005年後期火曜2限青柳魅Aoyagi@cc.kyushu-u.ac.jp http://server-500.cc.kyushu-u.ac.jp/ 10月11日(火) 1.序 並列計算機の現状2.計算方式およびアーキテクチュアの分類(途中から) 3.並列計算の目的と課題4.数値計算における各種の並列化並列計算機や計算機クラスターなどの分散環境における並列処理の概論・MPIおよびOpenMPによる並列計算•理工学分野の並列計算アルゴリズム
2
出席点5割,レポート5割aoyagi@cc.kyushu-u.ac.jpへメールSubject:並列アルゴリズム学籍番号,氏名,専攻,座席番号(a-1,a-2,・・C-3など)
3

2-1.命令とデータの流れに着目した計算方式の分類1
◾   SISD (Single Instruction stream Single Data stream) ◾通常の逐次計算機■ SIMD (Single Instruction stream Multiple Data stream) ◾命令は一つだが，複数のデータに対して同じ処理を行う◾単純で,低コストで,高い並列生を持つ計算機を作れる計算機が物理的に大きくなると同期が大変. ◾画像処理のように同じ処理を同時に行う場合に便利■   MISD (Multiple Instruction stream Single Data stream) ▪例がない◾   MIMD (Multiple Instruction stream Multiple Data stream) ◾各々独立した計算機が,独立したデータに対して処理◾比較的大きな計算機を作れる▪自由度が高い
SISD (single instruction stream single data stream) SIMD (single instruction stream multiple data stream) MISD (multiple instruction stream single data stream) MIMD (multiple instruction stream multiple data stream)
■ UMA (Uniformed Memory Access model) ◾全プロセッサがアドレス空間を共有◾全プロセッサからメモリへのアクセス時間が一様■共有メモリモデル■   NUMA(Non-Uniformed Memory Access model) ▪アドレス空間は共有◾プロセッサから見たメモリアクセス時間は一様では無い◾分散共有メモリモデル■   NORA (NO Remote memory Access model) ◾アドレス空間を共有しない▪独立したメモリのみを持つ▪分散メモリモデル

8

■目的
◾計算時間の短縮(大規模高性能計算) ◾大メモリ容量が必要（大容量計算） ▪並列アルゴリズムの研究■計算科学・シミュレーションの例◾ナノスケール・分子シミュレーション◾大気・海洋シミュレーション（前述:地球シミュレータ参照） ■並列アルゴリズムの研究例◾粒子シミュレーションにおける「分割」
10

(a) Particle decomposition method (b) Spatial decomposition method粒子分割法粒子数は保存計算負荷は一定しかし粒子の位置は変動通信負荷は不均衡になりやすい粒子間相互作用(Force)の計算部DOi = 1, N DOj = 1, i Call calc_force(i,j) ENDDO ENDDO領域分割法領域内の粒子については通信負荷が無い(軽い)しかし領域内粒子の数は変動計算負荷は不均衡になりやすい11
■並列化不可能な部分が有る■アムダール則（3-1） ■計算負荷のアンバランス▪計算粒度の問題（3-2） ◾並列化によるオーバーヘッド◾通信のオーバーヘッド（3-3） ◾並列アルゴリズムそのもの
12

■高速(並列)化前高速化後■速度： / → lv ■時間: T → T ■今全体の(1-s)をn倍高速化できたとする■速度向上比Eff
■例えば全体の90%を並列化できたとしてn=10で・・Eff=約5.  2倍
13

計算負荷のアンバランス■同期待ち時間の増大通信のオーバーヘッド■プロセッサ間通信の「頻度」と計算粒度並列アルゴリズムによるオーバーヘッド■並列化の為にデータをコピーする■並列化の為の制御文を挿入
16

数値計算コアとなるSolverによる分類数値積分,連立一次方程式,固有値問題, ・・概して計算粒度が小さなアルゴリズムが多いシミュレーション手法による分類差分法,有限要素法,粒子多体問題, ・・自然を模倣したアルゴリズム等・・シミュレーテッドアニーリング,遺伝的アルゴリズム,ニューラルネットワーク, ・・計算粒度の大きなアルゴリズムが多い
18

自明な並列
最初にデータと仕事をばらまいて,最後に結果を回収・整理統合するタイプ.　もっとも粒度が大きな並列化が実現しやすい モンテカルロ法,パラメータサーベイ,探索問題,等ただし,データのばらまき・回収に通信量が多すぎたり,データが１プロセッサのメモリに入りきらない場合には，別の並列性を考慮する必要がある．
タスク並列
内容の異なる複数のタスク(処理のまとまり)からなり,それらを一定の順序制約のもとに処理するタイプ.  探索問題,分割統治法,疎行列計算など.  中粒度から大粒度.
データ並列
沢山の(別の)データのそれぞれに対して(同一の)処理を行うタイプ.密行列･ベクトルなど線形演算,物理シミュレーション,画像処理など. 「個々のデータに対する処理に, （近傍か遠方か又は部分データか全体データか）どこのデータが必要となるか」が効率の良い並列アルゴリズム生成のカギとなる. 中粒度～小粒度.
パイプライン型
データの列があり,データ要素に対して複数の処理を逐次的に施すタイプ.いわゆる流れ作業. 多倍長演算や動的計画法など. 19
SPMD(Single Program Multiple Data )並列プログラミングの一つのスタイルで,複数の計算機上に個々別々のデータが乗っているが、それを処理するプログラムはすべて同一のものを使う。しかし、プログラムが同ーだからといって処理内容が同一であるとは限らない。条件分岐を用いて、プロセッサ毎に全く異なる処理を行うプログラムをSPMDの枠内で記述することもできる( • •というか,通常そうする）.
Owner Computes Rule
分散メモリにおける並列プログラミングの3つのKEYポイントは,データの分散,処理(タスク)の分散,そして通信方法と通信量(頻度も重要)である. 3つを同時に考えながらプログラミングを行うことは難しい.まずはデータの分散を考え,処理(タスク)の分散をデータの分散に従わせることをOwner Computes Ruleと呼ぶ.通信は最適になるとは限らないが.
同期通信
同期通信では,データを持っているプロセスは送信(send)というルーチンを呼び,それを受け取るプロセスは受信(recv)というルーチンを呼ぶ.このタイプの通信では,データのやり取りと同期を兼ねており、受信ルーチンを呼び出すまでは相手のメッセージは自分の領域に入ってこないことが保証される点でプログラムの構造は比較的簡単な場合が多いが，通信は各時刻で必ず一方通行(half duplex)となる． 20
非同期通信
非同期通信では、受け手が受信ルーチンを呼び出していなくても送り手はデータを送信することができるので,送ってしまったら次の処理を開始し,演算と通信が同時に行われる様にアルゴリズムを工夫できる場合には「通信遅延の隠蔽」ができる.非同期通信では(うまくゆけば)双方向(full duplex)の通信が可能である.また動的負荷分散を考慮したMaster-Workerモデルなど，柔軟なプログラミングが可能だが，多用するとプログラムの構造が複雑になる.一般に,非同期通信は同期通信よりも多くのバッファメモリを必要とする. (例)自作の電子構造計算プログラムにおける2電子積分ル一チンの負荷分散Master-Workerタイプのアルゴリズムを用いており,各計算ノ一ド(横軸)でIteration (奥行に表示)毎.「積分計算の処理量」（縦軸）が異なる.
21

MPI (Message Passing Interface)分散メモリプログラミングのためのライブラリル一チンのインタフェースを定義. MPI Forumh(ttp://www.mpi-forum.org/)により策定(MPI-2.0, MPI-1.2, ・・)実装としては，MPICH(http://www-unix.mcs.anl.gov/mpi/mpich/)，LAMなどオープンソース＆フリーなものから,ベンダー提供のライブラリなど各種ある.事実上の世界標準.  共有メモリマシンでも利用できる. OpenMP共有メモリプログラミングのための指示文のセット逐次プログラムをベースとし、Pragma指示行という形で並列処理の仕方を定義.アルゴリズムが特定のパターンにマッチすれば簡単に並列化ができる. HPF (High Performance Fortran)逐次版fortranプログラムに指示行を加えて,データと処理の分散を指示.必要な通信はコンパイラにより自動的に生成される. 分散メモリ計算機上で,共有メモリ的なプログラミングを行うことを意図. 最近は少し元気がない?
22

MPI (Message Passing Interface )は,メッセージ通信のプログラムを記述するために広く使われる「標準」を目指して作られた，メッセージ通信のAPI仕様である。  MPIの標準化への取り組みはSupercomputing’92会議において、後にMPIフォーラムとして知られることになる委員会が結成され,メッセージ・パッシングの標準が作成された.これには主としてアメリカ,ヨーロッパの40の組織から約60人の人間が関わっており,産官学の研究者,主要な並列計算機ベンダのほとんどが参加した.そしてSupercomputing’93会議において草案MPI標準が示され，1994年にMPI-1がリリースされた．MPIの成功を受けて, MPIフォーラムはオリジナルのMPI標準文書の改定と拡張を検討し始めた.このMPI-2フォーラムにおける最初の成果物として, 1995年6月にMPI1.1がリリースされた. 1997年7月には, MPI1.1に対する追加訂正と説明がなされたMPI1.2と, MPI-1の機能の拡張を行ったMPI-2がリリースされた. MPI-2の仕様は基本的にMPI-1の改定ではなく,新たな機能の追加であるために, MPI-1で書かれたプログラムもMPI-2をサポートするプラットフォームで実行できる.以上( http://www.mpi-forum.org/)とMPI-1, MPI-2の日本語訳(MPI-Jプロジェクト)より抜粋.
23

MPIはインターフェースの規定であり,実装パッケージそのものではない. MPICHは,アメリカのアルゴンヌ国立研究所(Argonne National Laboratory)が模範実装として開発し、無償でソースコードを配布したライブラリである.移植しやすさを重視した作りになっているため盛んに移植が行われ, LAM同様, Linuxマシンは勿論,世界中のほとんどのベンダの並列マシン上で利用することができる.特に. MPICHではUNIX系に限らずWindows系へのサポートも行われている.さらに, SMP, Myrinetなどのハード面にも対応している上,バッチシステムDQS,グリッドツールキットGlobusといった様々なツールを使用できることも大きな特徴の一つである.また, MPICH 1.2.0では, MPI-1.2の全ての機能をカバーしており, MPI-2に関しても幾つかの機能についてはサポートしている. MPICH 1.2.0におけるMPI−2への対応等に関する詳細な情報は,  http://www− unix.mcs.anl.gov/mpi/mpich/に載せられている. LAM(Local Area Multicomputer)は、ノ一トルダム大学の科学コンピュータ研究室(Laboratory for Scientific Computing, University of Notre Dame ）が作成したフリーのMPIライブラリである. LAMは,標準的なMPI APIだけでなく幾つかのデバッキングとモニタリングツールをユーザに提供している. MPI−1を完全にサポートしているだけでなくMPI−2の標準的な幾つかの要素についても機能を提供している.最新バージョン7.0.xではMPI−2における1方向通信,動的プロセスの管理に関する機能がカバーされている.また, LAMは世界中のほとんどのUNIX系ベンダの並列マシン上で利用することができる.ただし, 2003年秋時点でWindowsに関してはサポートされていない. LAMは,並列ジョブ実行・デバッグ統合環境であるXMPIとの相性が良くXMPIを使用したいのであれば便利である．LAMに関する詳細な情報は，http://www.mpi.nd.edu/lam/にある.
24

MPI_Comm_size(MPI_COMM_WORLD, &p); 25
コミュニケ一タ:お互いに通信を行うプロセスの集合である.ほとんどのMPIルーチンは引数としてコミュニケータを取る.変数MPI_COMM_WORLDは,あるアプリケーションを一緒に実行している全プロセスからなるグループを表しており,これは最初から用意されている.また新しいコミュニケータを作成することも可能である. rank :コミュニケータ内の全てのプロセスは,プロセスが初期化されたときにシステムによって示されたIDをもっている.これは0から始まる連続した正数が割り当てられる.プログラマはこれを用いて,処理の分岐,あるいはメッセージの送信元や受信先を指定することができる．  MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);利用可能プロセッサ数:コミュニケータ内で利用できるプロセッサ数(p)は, MPI_Comm_size(MPI_COMM_WORLD, &p); により取得できる.
26

ジョブ(Job)コンピュータが処理する仕事の単位.プロセス(Process)アドレス空間を排他的に利用する計算処理の単位.プロセス実行中の資源や情報は個別に管理,生成や切り替えに時間がかかる.複数プロセスを並列計算に使うためには,プロセス間通信が必要.
スレッド(Thread)
プロセスをさらに細分化した並行処理単位.実行に必要な資源や情報の多くをスレッド間で共有できるため,スレッド固有の必要資源を少なくし,操作負荷を軽減することができる.