考察 並列処理プログラミ

ングの

考察 並列処理プログラミ

1925-1995

中 弘

田

の処理を完了するまでの経過時間を問題とする タ^ーン ア ラ ウン ド タ イ ム (turn-arround­

time) の短縮化であり， 他は， 一定時間にコン

ピュ^ータが有効に動作する割合を問題とするス ル^ープット (throughput)の向上である。前者 はもっばらハ^ードウェアの性能向上の問題であ り， 後者はソフトウェアヘの比重が重<, OS (operating system) の大きな目的の1つでも ある。タ^ーンアラウンドタイムの短縮化，

ル^ープットの向上とも， 人間まで含めたデ^ータ 処理システムの問題として広く考える必要があ るが， ここでは狭義に考えており， システム設 計に関わることは取り上げない。

デ^ータ処理の基本的パタ^ーンは， 入力⇒処理

⇒出力の繰り返しであるが， 人出力を行う周辺 装置の速度がCPU (central processing unit) に比して遅い ため， 初 期の直列処理のコン ピュ^ータでは図l^{に示すように，} CPU ^は入出 力が完了するまで「待ち」の状態となり， CPU に遊休時間が生じる。このような状態を少なく して処理効率を上げる対策として考えられたの が， 処理が終了し出力が始まると同時に次の デ^ータを読み込むという， 周辺装置の同時動作 である（図2)。また， 記憶装置から取り出した 命令を解読して実行する execution cycle の ス はじめに

最近， 複数のプロセッサを並べて高速処理を 実現しようという並列コンピュ^ータヘの期待が 高まっている。

メモリ^ー内にプログラムを内蔵しておいて，

それを順番に取り出して実行する逐次制御方式 のコンピュ^ータは， その開発の当初から， いわ ゆるノイマン型コンビュ^ータとして目覚ましい 発達を遂げてきて現在に至っている。 もっと も， この方式のコンビュ^ータをノイマン型と呼 ぶことについては異論もある100 ENIAC ^が達 成した加減算 0.2ms という速度は， 当時とし ては画期的なもので， 米国における全ての計算 需要に対処できるとさえ思われたにもかかわら ず， その完成と前後して今後の改良点として，

全体としての処理速度の向上の必要性が指摘さ れている¹²⁾。その後のコンピュ^ータ開発の主目 標は高速化， 小型化， 大容量化であり， それに 向かってハ^ードウェア， ソフトウェアの研究が 続けられてきている。

2.

1.

� � �

● : im : ●

.... imDmJinnIDJ ....

一

-389 (585)-

直列処理

間

図1

峙 入力

処理 出力

高速処理の要求に対する基本的な対応は， 高 速論理素子の開発であり， リレ^ー⇒真空管⇒卜 ランジスタ⇔IC⇒ LSI^⇒ VLSI の流れであり，

また， 第1世代， 第2^……第5世代として説明 されている。 このような流れの中においても，

別な角度から高速処理実現のための努力がなさ れてきている。

ここでいう処理高速化には2つの意味があ り， 1つは， デ^ータ処理の要求があってからそ

42 2·3号 入力

I

""H'i'i'I

処理

．

^{• ロ}

出力

_．

--iIIImIIInIInID--� _．

←

:—

: -4件目一―-:

時 閏

図2 入出力装置の同時動作による処理

崎間

CPU

I ! l I! I I I

;} . プA111/0:

i ^I

^{I i}

^II

^{I I}

^D

,. プ'�^{二豆）。は待ち崎間}

ジ•プe1ii1/oll;/oll;/olll 11011入出力動作中

図3 多重処理におけるCPUの動作

間に次の命令を取り出す fetch cycle を済ま せておくという「先回り制御」も実現している。

一般的なデ^ータ処理（特に事務計算の分野に おいて）では， 入出力のデ^ータ量が多いのに対 して CPU を必要とする計算· 処理が少ない ため， 周辺装置の同 時 動 作を とりいれても CPU に遊休時間が生じがちであった。次に考 えられた手段は． この遊休時間に別のジョプを 処理させようということである。すなわち， 同 一時間帯に複数のプログラム（複数のジョプ）

を実行させようという多重処理の概念である

（図3)。 これによるとコンビュ^ータは外見上，

同時に複数のジョプを実行しているように見え る。実測においても いまジョプA, B, C, そ れぞれの処理時間が20分， 30分, 40分であると すると， 単独処理では3つのジョプの処理に90 分かかるが， 多重処理では50分程度になる。

TSS (time Sharing System) もこの概念の延 長線上にあると考えられる。これらの実現の背 景には． 入出カチャネルをはじめ多くのハ^ード ウェアの開発・進歩があることは論を待たな

し'o

3. 並列処理の発想

高速処理の実現には複数のプロセッサを結合 して並列処理を行えばよい， というアイディア はコンビュ^ータの歴史のごく初期の頃からあっ たが13), 最近まで本格的に研究されてこなかっ た。その理由は主に次のように考えられる。

(1) その有効性は予想できるものの， 逐次制 御方式コンピュ^ータの急速な発達と使い易 さに満足していた。 プロセッサの速度はこ の10年間に1,000^{倍も向上している。}

(2) 実験の結果必ずしも速くならなかっ た。 並列処理はプロセッサ間の結合網と いった資源通信を行う手間の代償として 高速処理を実現しようとするものである。

(3) ソフトウェア開発が容易でない。 逐次ア ルゴリズムは， たいていの逐次制御方式コ ンビュ^ータ上で動作するが， 並列アルゴリ ズムはハ^ー ドウェアヘの依存性が高く， ど のような並列コンビュ^ータにも適用できる ような並列アルゴリズムを設計することは 極めて難しい¹⁴⁾。

(4) 並列コンピュ^ータの利用分野は， 莫大な 計算量を必要とし逐次処理的要素の少ない 自然科学分野 と 考 え ら れ ていた。コ ン ビュ^ータの利用分野で， 科学技術用の比率 は10%前後であるため， メ^ーカ^ーの開発意 欲が小さかった。

最近になって並列コンピュ^ータ． 特に超並列 コンピュ^ータが注目されるようになってきた。

並列コンピュ^ータと超並列コンビュ^ータの明確 な区別はない。 プロセッサの数が100^個までを 並列コンビュ^ータ． それ以上のものを超並列コ ンビュ^ータとするケ^ース¹⁵'. 1,000^{台規模のプロ} セッサを持つか． あるいは論理的に1,000台規 模まで拡張可能であること¹⁶⁾ とするものなど があるが， ビジネス分野での利用の場合． 必ず しも超並列である必要はないと考えられる。

注目されるようになったきっかけは， 米国の ベンチャ^ー企業「シンキングマシンズ」が約6 -390 (586)-

万個のプロセッサをつないだコンビュ^ータを開 発し， ^一定の成果を上げたことによる。 逐次型 と超並列型では， コンピュ^ータの構造や取り扱 う問題も異なり， プログラムの性質も違うので 単純な比較は難しいが， 少なくとも処理しよう とするジョプによっては超並列型が優れている ことが証明された。 一方背景として， 今後の逐 次型の発達について， 限界が感じられることで ある。ス^ーパ^ーコンビュ^ータの速度も， 微細加 工技術 と光速の壁の ため， GIPS (Giga In­

struction Per Second, giga ⁼ 10^{りが限界と} 考えられている171が， 並列型なら現在の技術を 基本として毎秒テラ(tera⁼l0¹²)^{回の実現も可} 能と考えられている。また， 並列コンピュ^ータ は自然科学分野以外でも有効に利用できる可能 性が認識されてきたことにもよる。

複数のプロセッサの接続を考える場合， すべ てを同じプロセッサにするか， それぞれが特徴 をもつ専用プロセッサにするかの検討が必要に なる。 人間社会の組織の例では， 前者の傾向が 見られるのが行政組織， 企業組織は後者に近い といえる。 専用プロセッサを結合した並列コン ピュ^ータの小規模なものは， 汎用プロセッサと 浮動小数点演算用プロセッサを接続したものな ど， すでにいくつか制作されている。 専用プロ セッサを結合するケ^ースでは， どうしてもその アプリケ^ーションを意識したハ^ードの設計， す なわちデ^ータ ベ^ース用， グラフィックス用と いった専用機にならざるをえないことから， 汎 用機としては均質型のプロセッサをもつ並列コ ンビュ^ータが優勢となり， さらに各プロセッサ が従うべき命令の与え方により， MIMD^型と SIMD型に類別される。

並列コンピュータ

<専用プロセッサ結合 MIMD181 均質プロセッサ結合<

SIMD191

4. 並列処理の有効性

図4において並列処理を実施するケ^ースを考 えてみる。

デ^ータA, B, Cを入力して， 若干の計算の 後 その結果によって別々の処理をするという ものである。並列処理においても， デ^ータ入力 が完了するまではプロセッサ2, 3は待ち状態 である。ステップ②③④は同時に処理可能であ り， それらの完了を待ってステップ⑤が処理可 能となる。 ステップ②③④とステップ⑤はデ^ー 夕依存関係にあり， この段階でプロセッサ2, 3 は待ち状態となる。処理M, Nのどちらを実行

するかは

·x >

内容によっては， 判断結果が出る前に両方とも 実行してしまうことも可能である。処理内容に よってはとは， 処理M, N^がX^{の値を用いな} い（デ^ータ依存関係がない）処理の場合である。

処理M, N^中でXの値を用いる必要が生じた 場合， そこで処理を^一時停止してX^の値が算 出されるのを待つという， プロセッサ間の処理 進行の同期化を図る必要がある。また処理M,

Nの実行中または実行後， ステップ⑤⑥が完了 し， 処理M, Nの何れを実行すべきかがわかる ので， 処理M, Nのどちらかが無駄になるとい う「投機的処理」を覚悟しなければならない。

図4の縦軸は時間の経過を意味するので， この ような投機的処理を含んでいても並列処理が速 いことを示している。

しかし， 現実のジョプは（特に事務処理にお いては）， 前ステップの処理結果を次の処理に 用いるというケ^ースが多く（デ^ータ依存度が高 く）， またプロセッサ間の結合• 制御や通信を 行う手間が必要になるため， 必ず速くなるとは 限らない。 このことは， メモリを共有にするか 分散メモリにするかという課題が根底にある。

分散メモリ ・ システムでは， すべてのプロセッ サからどのデ^ータ格納領域へもアクセスが可能 であるため， 他のプロセッサがあるデ^ータを書 き換える場合， その処理が終わる前にデ^ータを

r逐次処!!I---.

— ^―

―-

プロセッサ1 プロセッサ2 プロセッサ3

図4 逐次処理と並列処理

読み出そうとするプロセッサが生じないように しなければならない（図4において， ②③④の 処理が終了するまで⑤の処理を実行してはなら ない）。各 メモリ単位（ メモリセル）にフラグを 設けて， デ^ータの書き換えが終了したかどうか を示す工夫が考えられるが， そのような制御は 主としてソフトウェアの領域と考えられる。

このような事情で従来， 並列コンピュ^ータの 適用分野として， 莫大な計算量を必要とし逐次 処理的要素の少ない 自然科学分野， 原子物理 学， 天気予報， 構造解析， 流体力学， 資源探査 など⁰� が挙げられてきた理由である。しかし，

事務処理， ビジネス分野においても， 必ずしも 逐次処理を必要としないデ^ータベース検索， 画 像処理， オンライントランザクション処理， 人 工知能などの分野での活用， マルチメディア実 現のための基礎技術としても期待できる。

5. 並列処理のプログラミング 従来の逐次処理方式のコンピュ^ータであれ ば， 高速化は素子や内部構成の改良によって可 能であり， また高速化がプログラミングの分野 に及ぼす影響はごく僅かなものであった。 しか し長期的に見た主流は並列コンピュ^ータであろ う。 並列コンピュ^ータは従来のプログラミング のスタイルに深刻な問題を引き起こすことにな

る。

現在のプログラムは1時点では1つの処理を するが， 並列プログラムでは1つのタスクを多 くの部分に分割し， 命令やデ^ータが整然と流れ るように各部分を制御するという「ミツバチの 並列プログラム四の技法を確立する必要があ る。 ミツバチは巣を保持するため， 並列プログ ラムを実行している。 ミツバチは個々では弱い が協力して働く。 並列プログラムも， ミッパチ のようにして多数のプロセスもしくは活動場所 を作り出し， 問題に耐えうるような多大な計算 力を作り出すことができる。 ミツバチは視覚的 や化学的な信号により協力し合う。同様に， 並 列プログラムのプロセスも^一緒に働くためにコ ミュ^ニケ^ートし合わなければならない。

並列プログラムに関わる問題点を大別する と， 並列化コンパイラの開発， 並列型プログラ ム言語の開発， 並列処理向き問題解決法（アル ゴリズム）の開発 ・ 教育， の3つになり， それ ぞれ相互補完的関係を有している。 すなわち，

理想に近い並列化コンパイラが開発できれば，

他の2つは比較的簡単な問願となる。

(1) 並列化コンパイラの開発

現在， 非常に多数の人が COBOL, BASIC, C といった逐次処理型プログラム言語を使用 してプログラミングしている。 これらの人々 に， 新たに開発された複数の命令を^一度に実行 できるようなプログラム言語を習得してもらう には長期間を要する。 また既に多大な費用と期 間を費やして開発された逐次処理型プログラム 資産は膨大なものである。

これらのことから， 既存の逐次処理型プログ ラム言語で作成されたプログラムから， 並列性 を抽出して新しい型のプログラムを生成できる ような並列化コンパイラが要請されるととも に， 低並列コンピュ^ータから超並列コンピュ^ー 夕まで， 様々なスケ^ールのコンピュ^ータに極力 少ない手直しで対応できるOSの開発も不可欠 である。

-392 (588)-

(2) 並列型プログラム言語の開発

逐次処理を前提に作成されたプログラムから 並列性を抽出するという考え方そのものに相当 な無理がある。 長期的視点からすると， 並列型 プログラム言語の開発が望ましい。 この観点か ら期待されるのが， 文部省重点領域研究「超並 列原理に基づく情報処理基本体系」における成

果である。

このプロジェクトは応用， 言語, OS, ハ^ード ウェアの4つの班に分かれて研究し．「応用」班 が作成したプログラムは「言語」班が開発した 言語で記述し． 「OS」班作成の OS の下で制御 され．「ハ^ードウェア」班が作成したハ^ードウェ ア上で稼働する^u� という構想である。 ここで は， 実用性を重視して C言語を ベ^ースとした NCX 言語． 既存の言語にとらわれない超並列

v

(3) 並列処理向き問題解決法（アルゴリズ ム）の開発 ・ 教育

並列コンビュ^ータのプログラミングにおい て． プログラマは使用するハ^ードウェアのア^ー キテクチャを全く念頭におく必要がないことが 理想である。 具体的には， 個々のプロセッサの 機能， プロセッサ台数， プロセッサ間のメッ セ^ージ転送機能や同期の方法． プロセッサ間の 距離や結合方式といったことがらから， どの程 度独立してプログラミングできるかである。 こ れは並列処理の効率や， MIMD/SIMD システ ムとも関連し， また開発されるであろ う並列化 コンパイラの機能とも密接に絡んでいる。 単一 プロセッサ下のア ルゴリズムをそのまま用いる のではなく， 並列性を活用するためのアルゴリ ズムの工夫とその教育（特に膨大な数の既存の 情報処理技術者への再教育） がある意味では最 も大きな課題かもしれない。

並列プログラムのテスト法， デバッグ法は．

処理の再現性がない場合もあることを考える と， 逐次プログラムの場合と比べて極めて難し くなると想像される。 しかし， デバッグの基本 はやはりプログラム実行のトレ^ースと内部状態

の表示0�と考えられる。

6. 並列処理の課題

並列コンピュ^ータ制作のためのハ^ードウェア 技術は， VLSI に代表される集積回路技術や高 密度実装技術によってすでに十分整っており，

これからの課題は広義のソフトウェア面の環境 整備である。 プログラミングについては前項の 議論と重複するので， ここではそれ以外の課題 についてとりあげる。

(1) 設計段階からの並列性 (Paralled by Design)

並列コンピュ^ータが広く利用される条件とし て， 並列度の拡大が可能でバランスのとれた ア^ーキテクチャ^ーの開発があげられる。 プロ セッサの速度， プロセッサとメモリ間のデ^ータ 転送速度， プロセッサ間の通信速度などのバラ ンスを考えた設計が必要となる。 このことを Cray-XMP の設計者 Steve Chen 氏は "Par­

ailed by Design"«� と表現している。

(2) 可視化のためのネットワ^ーク， OS の開 発

多くの利用者がアクセスできるためには， 高 速のデ^ータネットワ^ークの構築が不可欠であ る。 また大規模計算の結果は数値としてではな く， リアルタイムに画像として提示することが 好ましい。 そのためには並列コンピュ^ータ，

ワ^ークステ^ーション， ^パソコンなどの異機種を 接続するためのソフトウェアや， OS も Unix, Max, Windows などの異なるシステムを接続 することが欠かせない。

(3) ソフトウェアの開発

低並列から超並列コンピュ^ータまで， さまざ まな並列度のコンピュ^ータに対応できるプログ ラミング言語や OS などの基本ソフトウェア の開発。同ープログラムを異なる並列コン ピュ^ータに移植した場合， いかに少ない手直し -393(589)-

でそのコンビュ^ータの性能を引き出せるか，

ア^ーキテクチャ^ーの違いをソフトウェアでどの 程度カバ^ーできるかが課題となる。

従来の逐次処理コンピュ^ータであっても， 異 なる機種間の客観的性能比較は相当に困難で あった。 並列コンビュ^ータでは^一層その見極め は困難になることが想像される。 今後並列コン ピュ^ータが普及し， 多くのユ^ーザ^ーが利用を開 始していくことを考えると， ^ハー ドウェア／ソ フトウェア／アプリケ^ーショ ンを網羅した総合 的性能評価の手法（ベンチマ^ークプログラム）

の開発も欠かせない。

注

(1) Joel N. Shurkin: Engine of The Mind p. 159, 165, WASHINGTON SQUARE PRESS, 1985 プログラム内蔵 (stored program) 型コンピュ^ー

タの構想は， ノイマン (John von Neumann) が プ ロジェクトに参加す る1年前から Moore School で討議されており， 彼はENIACには何の 関係もなく， EDVAC 計画に携わった1メンバ^ー に過ぎない。

(2) Herman H. Goldstine : The Compute- from Pascal to von Neumann, p. 186, Prince-ton University Press, 1972

(3) 情報システムハンドプック：p, 3-354, 情報シス テムハンドブック編集委員会編， 培風館， 1989

(4) 情報システムハンドプック： p. 3-355, 前掲 (5) 日経サイエンス1993, 8「超並列のパラダイム」：

日経サイエンス社

(6) 馬場敬信稿「超並列マシンヘの道」， 情報処理 Vol. 32, No. 4 p. 349, 情報処理学会

(7) 河合敏夫稿「人に優しい超並列コンピュ^ータ」：

日経サイエンス1993, 8 p25, 日経サイエンス社 (8) Multiple-Instruction--stream / Mui tip le-Data­

stream, 複数の命令の流れと複数のデ^ータの流れ

を意味する。 非同期的実行意味論。

(9) Single-Instruction-stream/Multiple-Data-stream, 単^一の命令の流れと複数のデ^ータの流れを意味す る。 同期的実行意味論。

(10) 馬場敬信稿， 前掲， p. 354

(Jl) DAVID GELERNTER 稿「超並列コンピュ^ータ プログラミング」． 別冊サイエンス， p. 49, 1988. 8

日経サイエンス社

(rn 「超並列原理に基づく情報処理基本体系」． 情報 処理Vol. 36, No. 6 p. 500-, 情報処理学会 (13) 雨宮真人稿， 「超並列プログラミング言語とその

処理系」， 情報処理Vol. 36, No. 6 p. 5 14, 情報処 (14) 馬場敬信稿． 前掲，理学会 p. 358

(15) 日経サイエンス1993. 8, p. 31

参 考 文 献

情報処理ハンドブック：情報処理学会論， オ^ーム社，

1972

横山 保：コンビュ^ータの歴史， 中央経済社， H. 7 情報科学辞典：岩波書店， 1990

-394(590)-