勉強会資料 並列処理の基礎 笠原寛壽 平成 14 年 5 月 11 日^{1 はじめに より速いコンピュータが様々な分野で求められて いる。その中で並列処理は高速計算に対する魅力的 で実行可能なアプローチとなってきた。並列処理で は、問題または問題のクラスを解くのに最も適した 並列アーキテクチャを選ぶことが可能であり、単一 プロセッサと比べて非常に少ない時間で解けるとい う利点がある。 2 並列 2.1 並列と並行 「並列」という言葉はしばしば「並行」とは区別 して使われる。 「並行処理」とは、論理的には同時処理が出来る 仕事があるが、処理装置が一つしか存在しないた め、仕事を頻繁に切り替えて少しづつ処理すること である。一方、「並列処理」というのは、処理装置 が多数あり、それによって二つ以上の仕事が物理的 に同時に行われることである。並列では各処理は独 立している。例えば、並行は、ときどき立ちどまっ て考えるという行動、並列は、歩きながら考えると いう行動だと考えればよい。 並列に独立して実行いうる仕事 (あるいは演算) の個数を「並列度」という。アルゴリズムまたはプ ログラム上では大きな並列度を持っていても、実行 時における並列度は処理装置 (または演算装置) の 個数で制限される。}^{2.2 空間並列と時間並列 並列処理には、空間方向の並列化 (空間分割型並 列) と、時間方向の並列化すなわち (時分割型並列) が考えられる。 空間方向の並列化とは、多数の処理装置を空間的 に配置することであり、時間方向の並列化とは、一 連の仕事を複数の工程 (ステージ) に分け、それぞ れを各装置に割りあてることである。 2.3 同期と非同期 同期 仕事の進行に時間の概念を導入して、複数の仕事 の終了を待ちあわせて、次の複数の仕事が開始され る。 Do ループの展開や、配列データに対する処理 等、同一命令型がその典型である。時間の最も長い ものに合わせるため、待ち時間が多くなる。 非同期 仕事の半順序を重視して、時間の概念は特に考慮 にいれない。一つの仕事は、前提となる仕事がすべ て終了すれば、他の仕事と関係なく実行を開始でき る。データフローグラフで表せるものは、非同期を 想定している。 3 処理単位 プロセッサ数の大きい並列コンピュータにおいて は、多数のタスクまたはデータをプロセッサに静的 または動的に割りあてる必要があるが、タスク間 の通信やデータ交換に要する時間が、割りあて方に よって大きな影響を受ける。あたえられた問題を細 かく分割して、多数のプロセッサで同時に実行する ことは、処理の並列度を上げることに対応し、並列}

1 度が高いほうがその問題に対する計算時間が少なくてすむ。他方、並列度を上げると使用するプロセッサが多くなるので、一般にプロセッサ間の通信負荷も増大する。つまり、並列度と通信負荷の間にはトレードオフがある。

並列処理の単位となる大きさを粒度 (granuality) と呼び、その大きさによっておおよそ細粒度 (fine grain)、中粒度 (medium grain)、粗粒度 (coarse grain) に分けられる。細粒度は演算や命令単位に分ける方法で、演算装置を複数持つ計算機に適している。中粒度はループ文ほどの単位に分ける方法で、 Do ループの繰り返し間の並列性の利用は、マルチプロセッサで従来より行なわれている。さらに粗粒度では、サブルーチンほどの単位に分け、これもやはりマルチプロセッサ型の計算機に適している。

4 駆動方式

計算機アーキテクチャは、機械命令の起動形態で分類すると、コントロール駆動、データ駆動、要求駆動に大分類できる。コントロール駆動は、 SISD 方式、 SIMD 方式、 VLIW 方式、演算パイプライン方式、マルチプロセッサ方式に分類できる。また、データ駆動方式、要求駆動方式が非ノイマン型並列計算機と呼ばれるのに対して、 SISD 以外のコントロール駆動方式は、ノイマン型並列計算機と呼ばれる。また、マルチプロセッサ方式、データ駆動方式、要求駆動方式は MIMD 方式に属する。

ここに多くの方式を挙げたが、以下に簡単な説明を示めす。

4.1 コントロール駆動方式 (control driven)

制御駆動方式とも呼ばれる。

機械命令の実行の順序は、一つの制御装置によって決められ逐次的になされる。処理の流れをプログラムカウンタ (PC) により制御される、いわゆるノイマン型計算機である。つまり、並列実行可能な命令であっても PC に指示されるまで行なわない、実行の順序を待つタイプと言える。

コントロール駆動方式は、演算装置の構成によって、つぎのように分類される。 4.1.1 SISD(Single Instruction Single Data

Stream) 方式

SISD 方式では、演算装置が一つ設置されており、一つの機械命令の実行によって一つの演算結果が得られる。 SISD 方式の代表例として、汎用大型計算機をあげることができる。汎用計算機とは、特にこれといった特徴はないが、すべてのことを無難にしかもかなり高速にこなすといったタイプの計算機である。過去のソフトウェアの継続利用というおおきな足かせがあり、機械命令レベルでのアーキテクチャは 1964 年の IBM360 の発表以来ほぼ固定化されている。したがって、レジスタ、トランスファレベル以下で高速化が図られている。

4.1.2 SIMD(Single Instruction Multiple Data Stream) 方式

SIMD 方式では、演算装置が多数設置されており、それらが一つの制御部から発せられた演算命令を同時に実行する。演算装置が非常に多いとき、真価を発揮する。この方式により、定型的な並列処理の高速化を達成できる。ベクトルや配列といった集合に対する演算を必要とする分野に適している。

4.1.3 VLIW(Very Long Instruction Word) 方式

VLIW 方式は、語長の長い機械命令を多数のフィールドに分割し、個々のフィールドで演算器やメモリを独立に制御する方式である。並列性の検出をコンパイル時に行う。そのため、実行時の並列制御は簡単になるので、ハードウェア構成は単純で高速化を達成できる。

4.1.4 演算パイプライン (arithmetic pipeline) 方式

演算装置が多数のステージからなる流れ作業の原理で構成されており、ベクトルや配列などに対する定型型処理に適している。各ステージでの処理時間が等しいとき、最大性能が得られる。大量データが入力されて結果が出るまでに時間がかかるが、結果が出始めると連続的に結果が得られる。 4.1.5 マルチプロセッサ (multiprocessor) 方式

多数のプロセッサが相互通信網を用いて互いに密に通信し、協調しながら並列に動作する。マルチプロセッサの目的として、同一処理を多数のプロセッサで分担 (負荷分散) したり、異なる機能をおのおののプロセッサで分担 (機能分散) して高速化を図る。また、ニーズに応じた性能をプロセッサ台数で調整できることが利点にあげられる。

4.2 データ駆動方式 (data driven)

データの依存関係により実行の半順序がつけられる。この方式には PC がなく、マシン命令は必要なオペランドやデータがそろうと実行される。入力の到着を待つタイプと言える。したがって、原理的には、プログラムに内在するすべての並行性を実行時に同時に引き出すことができる。また、副次効果がないため関数型言語に適しており、プログラムの検証も容易であるとされている。処理手順はデータの流れをあらわすデータフローグラフによって表現できる。ベクトル化が容易でないような科学技術計算や人工知能用言語 PROLOG の処理系などの非定型的処理の高速化に期待されているが、メモリ構成などを中心に解決すべき問題点は多い。

同一プログラムが複数地点で同時に呼ばれたり、再帰的に呼ばれたりすることができる方式を動的データ駆動方式、そうでないものを静的データ駆動方式という。動的データ駆動方式では、異なる環境でのトークン間でのミスマッチをふせぐ手段が必要となる。

4.3 要求駆動方式 (demand driven)

機械命令はその結果が要求されるとき、起動される。その計算の中で、必要ならば別の結果への要求が出される。出力の要求を待つタイプと言える。要求された命令からの結果は、要求した命令に返される。結果を返す過程はデータ駆動的になされる。

実行過程が処理してみないと分からない動的なもので、あらかじめデータフローグラフにコンパイルできない場合、要求を伝える過程で解釈実行しながらデータフローグラフを生成する。従って、データ駆動方式がコンパイラ向きなのに対して、要求駆動

方式はインタプリタ向きなものとなっている。要求 駆動方式は関数型言語の項書き換えモデルや論理型 言語 PROLOG の実行制御過程との親和性がよいと されている。 参考文献 [1] 富田眞治. 並列計算機構成論. 昭晃堂 [2] 富田眞治. 末吉敏則. 並列処理マシン. オーム社 [3] 高橋義造. 並列処理機構. 丸善株式会社 [4] 渋沢進. 並列分散処理入門. 培風館 [5] 富田研新入生セミナー「並列処理概論」（平成 10 年度）