4. 1 並列化手法の種類
並列化についてはいくつかの手法がある。通常はメモリ全体を複数のＣＰＵで共有する共 有メモリ型、それぞれのＣＰＵにメモリが分散している分散メモリ型の２種類があげられる が、ここでは複数のマシンで複数のプログラムを同時に走らせる環境も一種の並列環境とし て取り上げる。それぞれの特徴は以下の通り。
4.1.1 共有メモリ型
普通は一台のマシンに複数ＣＰＵがあるマシン（symmetric multiprocessor, SMP）で利用す る。分散共有メモリ型という複数のマシン上のメモリを共有する方式もあるが、使える状況 は限られる。並列で走らせるためにメモリ内容をコピーするなどのオーバーヘッドはないが、
同時にメモリアクセスする際の速度低下や、他のＣＰＵがメモリを利用しているときに内容 を書き換えないようにする配慮が必要という問題がある。スレッド化だけであれば、ＯＳお よびコンパイラがサポートしていれば簡単に行えることが多い。一般的なのはＨＰＦ
（High-performance Fortran）などで並列に関わる演算を中心に並列化を行う。こうした言語を
用いればコンパイラが自動的に並列処理のコードを生成するため、複数のプロセッサを使っ ているという意識なしに並列計算が行える。しかし、こうした言語では大規模な配列やマト リックスに関わる演算ではきわめて有効であるが、それ以外の利用では柔軟性が少ない。
4.1.2 分散メモリ型
複数のネットワークでつながれたマシンを利用して計算する。それぞれのマシンで計算す るための情報は全て通信を通してコピーされるため、通信による速度低下がある。分散メモ リ型をＳＭＰマシンで実行することも可能であり、この場合は通信による速度低下は小さく なるが、メモリ空間は共有しないため、多少のオーバーヘッドはある。たいていの場合は手 動でコンパイラに並列化の指示を与える必要があるが、うまく並列化するとかなりの効率を 上げることも可能である。実装としてはＭＰＩ、ＰＶＭなどがある。
4.1.3 分散共有メモリ型
ネットワーク上で一つの仮想メモリを構築し、あたかも全てのマシンで、一つのメモリを 共有しているように見せかけて並列化を行うモデル。パフォーマンスを上げるための実装は かなり困難で、フリーのものは今のところ無い。
4.1.4 分散実行
複数のマシンで別々のプログラムを同時に走らせる。同じプログラムをパラメータを変え
ながら大量に走らせたいときには非常に有効。どこでどのプログラムが動いているかを管理 することが主な問題となり、プログラム変更などの手間はほとんどない。プロセス間通信が ないため、各プログラムのオーバーヘッドは小さくなる。最近ではインターネットを通じて 白血病解析プロジェクトなどが行われている。
4. 2 並列処理の効率
並列処理においてもっとも重要な観点は複数のプロセッサを効率的に動作させることであ り、このためには対象問題、アルゴリズム、実装などの種種の局面で内在する並列性を抽出 しなければならない。
種々の問題を並列計算機にあてはめ、プロセッサ間のロードバランスをとるのはきわめて 難しい問題である。さらにこれがうまく出来てもどこかの段階に修正が生じると全体を見直 す必要がある。
1 p
p
E T
= pT
(83) 並列処理の効率は簡単には式(83)で表される。すなわち、 個のプロセッサを用いたとき の効率は１個のプロセッサで行ったときの逐次処理計算時間T
を並列処理したときの計算時 間T
と の積で割ったものである。p
1
p
p
( ) ( ) 1 1
pR f = f f R
− +
(84) 並列処理の数学的な効率としてはアムダールの法則がある。これは並列処理の部分とそう でない部分の比率を関数として全体としての処理速度を表したもので、全体の処理速度が低 速部分に大きく影響されることがよくわかる。図２９ 並列化の速度向上
ここで、 は全体の処理に置ける並列化可能な処理の割合であり、 は総合的な速度 向上率、 は並列処理の速度向上率である。これを図示すると図２９となる。たとえば逐次 部分の割合がたとえ５％と少なくても、一万台のプロセッサで得られるスピードアップはわ ずか２０倍にしかならない。いかに逐次処理部分の割合が全体の効率を下げているかがわか る。
f
p
( )
R f R
並列化処理に置ける効率に重大な影響を及ぼすもう一つのファクターはプロセッサ間通信 の速度である。この処理が遅く、しかもプロセッサ間通信が多い場合には並列処理の効率は 著しく悪くなる。
プロセッサ間通信の頻度は処理の粒度に関係している。粒度とは複数のプロセッサに与え られるタスクの大きさのことである。一つのステートメントあるいはそれ以下のタスクを細 粒度、ループまたはサブルーチンレベルのタスクを祖粒度、それらの中間的な大きさのタス クを中粒度とよぶ。粒度が小さくなればプロセッサ間通信が多くなり、反対に粒度が大きく なればプロセッサ間通信は少なくなる。このため、プロセッサ間通信の速度が遅く、細粒度 の場合は並列処理効率が悪くなる。特に、ＰＣクラスタの場合、一般にはプロセッサ間通信 の速度が遅く、このため、細粒度での並列処理を行わせると複数台のプロセッサを用いてい るにもかかわらず、１台のプロセッサを用いたときより遅くなることもある。このため、特 にＰＣクラスタを用いる場合には、出来るだけ粒度を大きくしなければならない。
並列処理の効率に大きな影響を与えるもう一つのファクターはロードバランスである。ロ ードバランスとは並列計算機の各プロセッサに与えられた計算負荷の均等性のことであり、
並列処理の効率を高めるためには、できるだけロードをバランスさせなければならない。
各プロセッサに与えられた負荷が不均一であると、処理に不可避な同期待ちが多くなり、
処理効率は悪化する。たとえば、負荷が２倍異なれば計算時間が２倍異なり、同期をとるた めに遅いプロセッサを待つことになり、いくら他の全てのプロセッサが早く処理を済ませて も一番遅いプロセッサに足を引っ張られることになってしまう。このため、処理効率はこの ことだけで50％悪化する。
こうした問題を克服するため、各プロセッサに与える負荷は出来るだけ均一になるように しなければならない。しかし、これは連立一次方程式のガウス・ザイデル法に基づく解法や 傾斜法に基づく最適化計算など、多くの繰り返し計算手法ではデータの内容によって収束ま での時間が異なるため難しい。そのため、最初から静的に負荷を分散するのではなく、その 時々の各プロセッサの負荷を測定し、負荷を動的に均一化させる方法も有用である。しかし、
この方法では負荷を管理するプロセッサが別に必要となり、しかも、負荷の測定のためにプ ロセッサ間通信が必要となり、別のオーバーヘッドが大きくなる。
4. 3 数値計算の並列化
4.3.1 差分法の並列化
ラプラスの方程式やポアソン方程式で表される種種の物理現象（重力場、静電場、静磁場、
定常熱伝導、定常物質拡散、渦なし非圧縮性流れ、弾性体の平衡、結晶の成長など）のシミ ュレーションは差分法に基づいて行われる事が多い。この場合、複数の格子点を格子状にグ ループ化した領域を並列処理できるかどうかに基づいてプロセッサに割り当てる。もしくは 全体をプロセッサの数だけの領域に分割して行う。いずれの方法でもヤコビ型の緩和法を用 いるのかガウス・ザイデル型の緩和法を用いるかによって計算モデルが異なり、計算速度と 並列化効率のバランスが変わる。
4.3.2 有限要素法における並列化
有限要素法で定式化されたシミュレーションモデルでは細粒度ではベクトル計算の並列化 となり、これはＨＰＦなどの並列プログラミング言語で比較的容易に並列化できる。大粒度 での並列化では領域分割法（Domain Decomposition）が中心となっている。領域分割法は有限 要素法に置けるデータ分割あるいは負荷分割である。この方法では対象を幾何学的に複数の 領域に分割し、それらを対応するプロセッサに割り当てる。そして、領域内の計算が終了す れば互いに境界条件を交換し、再度、領域内の計算を行う。これを反復することで全領域の 計算を行う。領域分割法では領域の分割の方法によってプロセッサのロードバランスが大幅 に異なるため、並列化効率を上げるにはこの点に注意する必要がある。
4.3.3 粒子法による物質の挙動のシミュレーション
多数の粒子の相互作用を基本として各粒子の位置や速度を求め、粒子全体からなるシステ ムの挙動を計算するアプローチを粒子法（particle method）という。相互作用が重力の時は天 体力学に置けるＮ体問題となる。一方、相互作用がクーロン力の場合には分子動力学などの アプローチを用いて原子あるいは分子の配置を決定する解析が行える。
粒子法の並列化は大粒度では空間でのセルあるいはクラスター化した粒子群を一つのプロ セッサに割り当てる方法であり、細粒度での並列化はベクトル計算におけるinner loopの並列 化である。
4. 4 ＰＣクラスタによる格子ガスオートマトンの並列計算
4.4.1 分散メモリ型における実装
ＰＣクラスタを用いて並列計算を行う場合、並列化手法の種類としては分散メモリ型であ る。分散メモリ型の並列計算機においては、各プロセッサに１つのプロセスが起動される。
プロセスとは独立して動くプログラムのことをいう。よってプログラムを動かすことをプロ