5 月 1 日勉強会資料並列計算機

永野貴宣 2002 年 5 月 1 日

1 並列計算機の概観 ; 1.1 なぜ並列計算機を作るのか ; 並列計算機は、複数のＣＰＵを同時に動 ; 作させる方式である。複数のＣＰＵを用 ; いるのには、主として以下の３つの理由 ; がある。 ; • 同時に動作させることにより、単 ; 一ジョブの処理を高速に行う。 (高 ; 速処理) ; • 同時に動作させることにより、高 ; い信頼性を得る。 (高信頼性) ; • 複数のＣＰＵでメモリ、ディスク、 ; 入出力を共有することにより、多 ; くのユーザに対して効率良く資源 ; を運用し、コストを低減する。 (資 ; 源の共有) ; 通常、並列計算機と言った場合は、単一 ; ジョブの高速化を主たる目的としたシス ; テムを指す。 ; 1.2 並列処理の基礎 ; 高性能の並列計算機を構成するために ; は、並列アルゴリズム、並列プログラ ; ミング言語、並列コンパイラ、並列オペ ; レーティングシステム (以下並列ソフト ; ウェア)、ハードウェア、の一体化した ; 研究が必要である。 // 一般にある問題 ; を並列計算機のマシン命令で実行する ; までの処理過程は、次の４段階に大別 ; できる。 ; 1. ある問題に対する最適の並列アル ; ゴリズムの選択 ; 2. 並列プログラミング言語によるそ ; のアルゴリズムの記述 ; 3. オブジェクトコードへの翻訳 (コ ; ンパイル)^{4. 計算機による実行 ; プログラムの効率は、アルゴリズムと、 ; アルゴリズムをプログラム化するプロ ; グラミング技術、コンパイラの翻訳能 ; 力に大きく依存する。アルゴリズムの ; 並列度 (独立で同時に実行できる演算の ; 数) と計算機の並列度が合致すれば、最 ; も効率の良いプログラムができる。 ; 1.2.1 並列処理の基本原理 ; 並列計算機アーキテクチャは原理的に ; は、空間方向の並列化 (空間分割型並列 ; 処理) と、時間方向の並列化 (時間分割 ; 型並列処理)、の２種類に大別すること ; ができる。 ; 空間分割型並列処理には、多数のプロ ; セッサを空間的に配置したプロセッサ ; アレイまたはマルチプロセッサ方式が ; ある。時間分割型並列処理には、演算装 ; 置などをいくつかの基本ステップに分解 ; して、各基本演算操作を時分割で多数の ; データに対して施すようにしたパイプラ ; イン方式がある。 ; 空間方向の並列化では、直感的には N ; 個のプロセッサを並列に動作させれば性 ; 能は N 倍になる。正確には、ベクトル ; の長さ (要素数) を n とし、 1 つのプロ ; セッサの処理時間を t_{a} とすると、 N 個 ; のプロセッサでは処理時間は ⌈n/N⌉t_{a} ; となり、性能は n/⌈n/N⌉ 倍となる。 (n ; が N の倍数なら N 倍) ; 時間方向の並列化については、例えば処 ; 理時間が 5t かかるステップを、さらに ; 細かいステップに分解して、各ステップ ; の処理時間を t ずつに５つに分解してや ; れば良い。単一のデータに対しては演算 ; 時間は 5t の時間がかかるが、ベクトル ; 長が大きい一連のデータに対しては、 1 ; データ当たりの演算時間は t となり、高 ; 速化が可能である。}

1 1.2.2 並列処理の効率 ; アムダールの法則単一プロセッサで最 ; 良の直列アルゴリズムによる実行時間 ; を T_{1}、 N 個のプロセッサで並列アルゴ ; リズムによる実行時間を T_{N} とすると、 ; S_{N} = T_{1}/T_{N} で定義される速度向上比 ; は、直列アルゴリズムの中でどうしても ; 並列化できない割合を α とすれば、 ; S_{N} = \frac{N}{1 + (N − 1)α} ; で与えられる。これをアムダールの法則 ; という。 ; ここで、 N → ∞ としたとき、 S_{N} → ; 1/α となるから、アルゴリズムで並列化 ; できない部分の割合、並列アルゴリズム ; の性能に大きな影響を与えるということ ; になる。一般に n の関数 α(n) であり、 ; 効率の良いアルゴリズムは、 n → ∞ の ; とき、 α(n) → 0、すなわち S_{N} = N と ; なって、プロセッサ数 N に比例した線 ; 型スピードアップがえられるものであ ; る。 ; ベクトルに対する性能長さ n のベク ; トルの処理時間 t は、理想的な計算機に ; 対して、または実際の計算機に対しては ; 一次近似として、 ; t = r_{∞}^{−1}(n + n_{\frac{1}{2}} ) ; と表わせる。 ; • 最大性能 r_{∞} ; 1 秒間に実行される等価なスカラー ; 演算の単位で測った最大計算速度。 ; n → ∞ の時にこの性能が得られ ; ることになる。 r_{∞} は使用される ; 計算機技術の特性を示すもので、 ; クロック周期に逆比例する。 ; • 半性能長 n_{\frac{1}{2}} ; 最大性能の半分を達成するのに必 ; 要なベクトル長。 n_{\frac{1}{2}} は計算機アー ; キテクチャの並列性の度合を示す ; ものである。 ; 平均性能長 r を、 ; r = n/t = r_{∞}/(1 + \frac{n_{\frac{1}{2}}}{n} ) ; ベクトル効率を、 ; η = r/r_{∞} = (1 + \frac{n_{\frac{1}{2}}}{n} )^{−1} ; とすると、 η = \frac{1}{2} となるのは、確 ; かに n = n_{\frac{1}{2}} のときである。 ; 1.2.3 プロセス間通信と同期 ; 並列処理では、複数のプロセスが協調し ; ながら仕事を実行する。そのために、プ ; ロセス間でのデータ通信、正しい実行を ; 保証するために同期をとる必要がある。 ; 同期の方式には、共有メモリに置かれた ; 共有変数による方式と、メッセージ交換 ; による方式がある。 ; • 共有変数による方法 ; 共有メモリを介したプロセス間通 ; 信は、送信プロセスがデータを共 ; 有変数に書きこみ、受信プロセス ; がその共有変数を読み出すことに ; よって同期をとる。相互排除 (2 つ ; のプロセスが同時に共有変数にア ; クセスすることのないように制御 ; する方法) と、条件同期 (プロセス ; が他のプロセスによって、ある条 ; 件が満たされるまで待つ方法) の ; 2 つの方式がある。 ; 同期によるオーバーヘッドを小さ ; くするために、同期にはハードウ ; ェアを設けるのが普通だが、セマ ; フォのようなソフトウェアで実現 ; される同期機構を併用することが ; 多い。セマフォは以下の 2 つの基 ; 本操作によってアクセスされる整 ; 数変数 s(≥ 0) である。

2 – P (s):プロセスを監視し、 s >

0 になるまでプロセスの実行を遅らせ、 s > 0 になれば s を 1 減す。

– V (s):s を 1 増加させる。

使い方としては、プロセスＡとＢを並列に実行しているとして、プロセスＡを実行中にＢとの同期が必要な所で一旦 P (s) を呼び出し、Ｂが同期がとれる所まで実行された時点で V (s) を呼び出すことで、プロセスＡの実行が再開する、という感じである。

• メッセージ交換による方法共有変数の読出し・書込みのかわりに、プロセスがメッセージを送信・受信する。この送受信命令を使用する方式と、遠隔手続き呼出しによる場合がある。

2 並列計算機の諸方式

2.1 並列計算機の分類

計算機は制御駆動型 (control-driven)、データ駆動型 (data-driven)、要求駆動型 (demand-driven) の 3 つに大別される。現在の商用計算機は、すべての系列が制御装置によって解読され実行される制御駆動型であり、フォンノイマン型とも呼ばれる。

2.1.1 Flynn の分類

制御駆動型の計算機 (並列計算機に限らずに、計算機全体に対して) は、計算機の命令流の数 (Single or Multiple) と、データ流の数 (Single or Multiple) に着目して、次の 4 つに分類される。

• SISD:単一命令単一データ流単一の命令を順番にメモリから取り出して、単一のデータ流に対して処理を施す。いわゆる普通の計算機である。最近のプロセッサは処理のパイプライン化が普通に行なわれているが、並列処理が単一のＣＰＵ内の演算器レベルなので、並列計算機の中にはいれず、 SISD の中にいれてしまうのが普通である。

• SIMD:単一命令流複数データ流多数の演算装置に対して、単一の命令をブロードキャストして、複数のデータに対して同一の処理を行う方式。単純な処理に対しては、低いコストで高い並列性を得ることができることから、画像処理等の専用マシンとしては有利だが、全ての演算装置が単一の命令しか実行できないため、複雑な処理を行う汎用マシンとしては不利。

• MISD:複数命令単一データ流単一のデータに対して、同時に複数の命令が実行される方式。このカテゴリに入る計算機は存在しない。

• MIMD:複数命令複数データ流独立の命令実行能力を持った複数のＣＰＵが、互いにデータを交換しながら、複数のデータ流に対して処理を行う方式。それぞれのプロセッサが独立に動作するので、汎用性、柔軟性が高いが、同期操作が必要でプログラミングも困難な場合が多い。この MIMD 方式が最近の並列計算機の主流となっている。

2.1.2 共有メモリシステムに関する分類

MIMD 型の並列計算機はバラエティに富んでいるため、共有メモリシステムに着目して以下の 3 つのタイプに分類する。

• UMA(Uniform Memory Access model: 均一アクセスモデル) 全てのプロセッサがアドレス空間を共有し、かつ同一時間でアクセス可能な共有メモリのモデル。プロセッサ数が 10 程度までの小規模汎用システムで、この方式がとられている。既存のシステムとの互換性が高い。

• NUMA(Non-Uniform Memory Access model:不均一アクセスモデル) UMA よりもプロセッサ数が増えた場合、均一時間で全ての共有メモリにアクセスしようとすると、アクセス時間が大きくなってしまう。このため、メモリを分散し、近くのメモリは高速に、遠くのメモリは結合網を介してアクセスし、ある程度遅延を許すようにする。これが NUMA である。 NUMA はデータアクセスの局所性を利用すれば、遠隔メモリのアクセスで起こる遅延をかなり避けることができる。また、 UMA のシステムがそのまま利用できるという利点がある。

• NORA(NO Remote Memory Access model:無遠隔アクセスモデル) 共有メモリを物理的に持たず、プロセッサ毎にローカルメモリを持ち、メッセージ転送によって他のプロセッサと交信するタイプ。

以上の 3 つのシステムを比較すると、 UMA は汎用性に優れているが、大規模システムの構築は難しい。逆に NORA は大規模な数値計算などの専用目的で利用される。 NUMA はちょうどこの 2 つの中間である。

2.2 ノイマン SISD 型の基本動作

図 1 にノイマン SISD 型の命令プロセッサ IP(instruction processor) とデータプロセッサ DP(data processor) の状態遷移図を示す。 IM、 DM はそれぞれ命令メモリ (instruction momory)、データメモリ (data memory) である。

• IP の機能

1. 次に実行する命令のアドレスを、自分自身の内部メモリと DP からのステータス情報とから決定する。

2. 命令をフェッチするために、 IM へアクセスする。

3. IM より命令をフェッチし、命令をデコードする。

4. DP へ遂行すべきオペレーション (操作) を通知する。

5. インデックスレジスタなどによるアドレス修飾を行って、オペランドの実行アドレスを決定し、 DP へ送り出す。

6. DP がオペレーションを行ったあとのステータス情報をうけとる。

• DP の機能

1. 遂行すべきオペレーションの指示を IP から受けとる。

2. オペランドのアドレスを IP から受けとる。

3. DM へフェッチしてオペランドを受けとる。

4. 同上

5. オペレーションの実行 6. オペレーションの結果を DM にストアし、オペレーションの結果生じたステータス情報を IP へ送り出す。

2.3 プロセッサアレイ

プロセッサアレイは、 1 個の IP によって多数 (N 個) の DP が制御される SIMD 型である。図 2 の分散メモリ型では、 DM は各 DP のローカルメモリとして分散されている。図 3 の共有メモリ型では、 DM はグローバルメモリとして各 DP に共有される。

2.4 マルチプロセッサ

マルチプロセッサは、 IP も複数となり多重命令流の MIMD 型である。図 4 の分散メモリ型は粗結合型、図 5 の共有メモリ型は密結合型とよばれる。

References

[1] 「並列コンピュータ」著

[2] 「並列計算機アーキテクチャ」著

[3] 「並列計算機」 R.W.Hockney C.R.Jesshope 共著奥川峻史黒住祥祐共訳