新世代への鍵 砂原 秀樹（月刊ASCII 1986年6月号16)連載

砂原　秀樹氏の連載をスクラップする。


35年後になっても面白く読むことができた。いかに自分が無知であり続けていたことが分かる。

　素子技術による処理の高速化が限界に近付きつつある現在,処理速度の壁を打ち破るためには計算方式の根本的な改善が必要である.その1つの考え方として古くから研究されているのが,並列処理方式である.
　しかし,これまでに登場した並列計算機のうちで実用的なものはごくわずかにすぎない。その原因はどこにあるのだろうか?

結局並列処理というのが良いアイデアなので35年間続けられてきたということだろう。

　複数のプロセッサを用意し,同時に複数の命令を実行することで処理の高速化を狙う並列処理方式は,計算機建築家にとって非常に古くからある研究課題である.並列計算機開発の歴史の源流は,世界最初の電子計算機ENIACに遡ることができる。当時,並列処理というものが意識されていたかどうかは別として,ENIACの持つ20個の累算器,そして1個の乗算装置と1個の除算開平装置はそれぞれ独立して動作させることができ,それらを同時に稼動させることによって一種の並列処理を実現していたことになる.しかし,プログラム内蔵式計算機の登場以後,次の並列計算機の登場は1964年のCDC6600を待たねばならない。

なんと計算機は最初から並列処理を実現していたとは、並列処理は基本的なものだったということか。

曙
　1964年にControl Data Corporation(CDC)が米国ローレンスリバモア国立研究所に納入した計算機CDC6600は,当時最高の計算速度を実現することが目標であった.そのために,CDC6600では8種10台の独立した演算装置を用意し,複数の演算を並列に実行することにより処理の高速化を図っていた.この,並列に実行できる演算の検出はコンパイラなどにより自動的に行われる.こうした工夫により,CDC6600では1MFLOPSという当時としては驚異的な処理速度を実現していた.
　その後,CDCはCDC7600(5MFLOPS),CDC STAR100(50MFLOPS)と,常に時代の最高速計算機を目標に開発を続けた(これらはいずれも,後述するパイプライン型の計算機である).1972年,それらのプロジェクトの中心的人物であったS.CrayがCDCをスピンアウトし彼自身の会社Cray Research Inc.を設立したため,CDCは主役の座をCray Researchに明け渡すことになる.しかしCDCは超高速計算機の分野から撤退したわけではなく,CYBER205(800MFLOPS)などを開発しCrayを常に脅かす存在となっている。
　Cray Research Inc.の設立と同時に発表され,たった4年の短い開発期間で登場したCRAY-1は,商業的に成功した最初の並列計算機の1つと言えよう.CRAY-1ではCDC6600の経験を汲み,複数の独立した演算装置を用意すると同時に,パイプラインという技法を用いて,科学技術計算に多用されるベクトル計算を高速に処理できるようになっている.

並列処理にパイプラインは35年後のパソコンでは基本的なものになっている。スパコンnの技術ををパソコンで使えていることが嬉しい。

第1の光
　パイプライン技法とは,ある処理を細分化し,それぞれをオーバラップさせて実行することにより高速化を図る技法である.例えば,ノイマン型計算機の実際は「命令の読み出し」「命令の解釈」「命令の実行」のように細分化されるが,これらを図1のようにオーバラップさせて実行すると処理時間を短縮することができる(実際には分岐命令などがあるため,前もって解釈しておいた命令が無駄になる場合もある.しかし,分岐命令などの流れを乱す命令の実行される確率は非常に低いため,この方法が有効に作用するのである).こうした方法は,80286など最近のマイクロプロセッサなどでも多く採用されている.

第1の光
　このようなパイプライン技法をベクトル演算(配列の演算)に適用したのが,CRAY-1などに利用されているパイプライン式ベクトル演算ユニットである.

　上に示したようなプログラムを実行した場合,全体で64回の乗算が行われることになる.したがって,一般の計算機でこれを実行すると図2(a)のようになる.しかし,CRAY-1では1回の乗算(浮動小数点演算)を7段に分けており,その各段をオーバラップさせて図2(b)のようにパイプライン化することで処理の高速化を図っている.したがってある一瞬を見てみると、7つの乗算を同時に実行していることになる.

　これで明らかなように,パイプラインの段数を多くすれば多くするほど並列に実行される命令の数は多くなる.しかし逆に,パイプラインの各段全部が稼働するまでの時間(つまり,最初の計算結果が得られるまでの時間のことで,立ち上がり時間と呼ばれる)が長くなるため,あまり多くの段数に分割してもそれほど効果は得られない。
　こうした自己矛盾を解決するために,CRAY-1ではチェイニング(chaining)という方法を利用できるようになっている.これは、1つの演算の結果をいったん中間結果として記憶装置に格納せずに,次の演算を引き続いて行う機能である。

　例えば,ここに示されるようなプログラムを実行する場合,基本的には,まず「A(I)*B(I)」の計算を配列の全要素に対して行った後,その結果とC(I)の加算を行うことになる.これに対しチェイニングという技法では,図3に示したように「A(I)*B(I)」の最初の要素の結果が求まるとすぐに,その結果と「C(I)」の加算を開始できるようになっている.つまり,演算のパイプラインをつなぎ合わせる処理方法がチェイニングである。

　これにより,必要に応じてパイプラインの長さを調節できることになり,効率的な処理が可能となる.
　CRAY-1の成功の原因は単にパイプライン処理による処理の高速化だけではなく,こうした柔軟な対応能力にあったわけである.このほかにもCRAY-1ではさまざまな工夫がなされているが,それらはS-810,VP-400,SX-1,CRAY-2など,今日の科学技術計算用スーパーコンピュータに受け継がれている.
　しかし,こうした計算機において高速に処理することができるのはベクトル演算のみであり,スカラ演算などの処理速度は一般の計算機なみである.したがって,記号処理などベクトル演算をあまり含まないプログラムの実行を高速化することはできない.また並列処理とはいうものの,その範囲は対象となるベクトル演算の周辺のみであり,より広範囲におよぶプログラム全体としての並列性を引き出すことは難しい.
　これらの問題点は,パイプライン型計算機が従来のノイマン型計算機でのベクトル演算をパイプライン化しただけにすぎず,その原理はまったく変わっていないために起こるのである.したがって,パイプライン型計算機といえども,フォン・ノイマンの原理から脱却することはできないのである.

思い出した。35年前は画像や動画圧縮とかをパソコンで処理できるような時代ではなかったので並列化にはあまり思いが至らなかった。とにかくシングルスレッドを速くという考えしかなかった。だってV30のクロックはたった10MHzだったのだから。今より数百倍も遅いCPUだった。毎年のようにクロックが上がっていく時代は並列化よりも高速化が望みだった。

オーケストラ
パイプライン型計算機の開発と並行して,まったく別の原理に基づく並列計算機が開発されている.それは,64000人の人間が指揮者に合わせて計算をしデータを交換しながら非常に膨大な数値積分を行うというリチャードソンの発想(これは,1920年というまだ電子計算機のない時代の発想である)に基づく計算機で,演算装置と記憶装置を持つプロセッサを多数用意し,それらを1つの制御装置で制御し処理を進めるようなアレイ型計算機である。1965年米国イリノイ大学で開発を始めた「ILLIACIV」は,こうした計算機の中で最も有名なものの1つであろう.
　ILLIAC IV計算機の本体は,正方格子状に配置された64台のプロセッサ(PU)と,それを制御する1台の制御装置(CU)で構成されたプロセッサ・アレイである(図4参照)。これに,入出力の処理を行うための入出力サブシステムと,ホスト計算機のバローズB6500を加えたものがILLIAC IV計算機の全体像である。当初の計画では、4台のプロセッサ・アレイが実装される予定であったが,実際には1台のみが実装された.

　さてここで,ILLIACIVを例としてアレイ型計算機の動作原理について説明しよう.

流石に素人にはこの辺は難しくてよく分からない。

第2の光
　アレイ型計算機の動作原理は,リチャードソンの発想そのままである.つまり、1台の制御装置(CU)が指揮者となりながら,64台のプロセッサ(PU)が同じ命令を実行していくわけである.たとえば,AddならばAddという命令を、全部のPUが実行するのである.
　CUはプログラムカウンタを持ち,そこで命令の取り出し・解釈を行い,それに基づき64台のPUが一斉に同じ命令を実行する(つまりプログラムカウンタは1つしかないことになる).
　例えば,前出のリスト2のプログラムを実行する場合,各PUに配列A,B,Cの各要素を格納しておき,まず乗算を,続いて加算を各PUで1回ずつ一斉に行うだけですんでしまう。したがって,その実行時間は一般の計算機で乗算1回と加算1回を実行する時間と同等であり,配列の要素が64個の場合それだけで64倍のスピードが得られるわけである.

　しかし,配列の演算は同じ添字の要素同士の演算であるとは限らない.例えば,リスト3のようなプログラムを実行する場合を考える.配列Aの各要素を各PUが格納している,つまりA(I)の内容を格納しているのはPU#I-1であると仮定すると,加算の対象となるデータA(I)はそのプロセッサに,A(I+1)はすぐ隣のプロセッサに格納されていることになる.したがって,リスト3のプログラムを実行するためには,まず隣のプロセッサからA(I+1)をもらってきた後に,A(I)との加算を行うことになる(図5参照)。

　アレイ型計算機では,このように他のプロセッサとデータを交換(交信)することで添字の異なる要素同士の演算を実現している.ここで問題となるのは,各PUが直接交信できるPUは数台しかないという点である(ILLIAC IVでは4台)、それ以外のPUと交信を行うためには,その間にあるPUに中継をしてもらわなければならない.したがって,効率的な処理を行うためには,できるだけ隣のプロセッサとだけデータの交換を行うように配列の要素の配置を考えなければならないのである.しかし,アレイ型計算機が対象とする偏微分方程式などの応用分野では,そのような配置は比較的容易に実現できることが明らかにされている.

「偏微分方程式などの応用分野では,そのような配置は比較的容易に実現できる」といわれても素人にはピンとこない。特定の分野でのシミュレーションとかには利用されたのだろうか。

　ところでアレイ型計算機では,常にすべてのPUで同じ命令が実行されている.しかし,リスト4に示されたような条件分岐を含むプログラムを実行する場合,すべてのプロセッサが同じ命令を実行しては困ることがある.
　こうした問題を解決するために,ILLIACINでは各演算装置ごとにモードフリップフロップと呼ばれるものを設けている.このモードフリップフロップが1のときは演算を行い,Oのときは演算を実行しないようになっており,これで条件分岐を実現している.リスト4のプログラムの場合,まずIF文の条件によって各PUのモードフリップフロップを設定し,THENの部分の命令を実行する.さらにモードフリップフロップの内容を反転させて,ELSEの部分を実行することにより結果が得られる.ここで注意すべき点は、モードフリップフロップが0の間,PUは休んでいる状態にあることである.したがって,場合によっては大幅な性能低下を招くおそれがある.
　この他,演算の対象となる配列の大きさとプロセッサ・アレイの大きさが異なる場合の要素の割り当ての問題などさまざまな問題があるが,応用分野を特定すれば非常に効率のよい処理を行うことができる.
　ILLIAC IVプロジェクトは、その当時の実装技術の信頼性が低かったために必ずしも成功を収めたとは言いがたいが,さまざまな並列アルゴリズムの開発など,のちの並列処理技術研究に多大な影響を与えた.また,このようなアレイ型計算機の考え方はその後,非常にユニークな計算機を生み出した.
　1979年に,英国のICL(International Computer Ltd.)が開発を始めたDAP(Data Array Processor)はアレイ型計算機であるとともに,非常に興味深い構造を持っている.
　DAPでは,4K×1bitのメモリを持つプロセッサが,64×64(4096)台のプロセッサ・アレイを構成している.これらのプロセッサは,1bitの全加算器と3個の1bitレジスタからなる.したがって,1つのプロセッサの演算能力は1bitのみということになる(図6(a),(b)参照).そのためDAPでの演算処理は,各プロセッサが独立して直列に行う場合(データを1bitずつ読み出しながら行う方法)と,隣のプロセッサと協調して並列に行う場合(データの各bitを各プロセッサが担当して行う方法)がある。

「応用分野を特定すれば非常に効率のよい処理を行うことができる」とかはそうだろうと納得がいくし、「必ずしも成功を収めたとは言いがたい」なんだから知らなかったのは当然か。

　また,DAPにはMCUレジスタと呼ばれる多数のレジスタが用意されており,これがプロセッサ・アレイ中を縫うように走るデータハイウェイを介してプロセッサと接続されているプロセッサは1bitの処理能力しか持たないため、プロセッサ・アレイの列または行に対応するMCUレジスタのbitと接続されることになる.つまり,i列j行のプロセッサはMCUレジスタのbit iとbit jに接続されている。
　このようなプロセッサ・アレイは,ホスト計算機からは図7のような3次元のメモリとして見ることができる.しかしそれは,単にホスト計算機のメモリとして動作するだけでなく,能動的にデータを処理する“Logic in Memory"という発想を含んでいる.

　さらに,図7に示されるように垂直方向や水平方向などさまざまな形式でデータを格納することができ,DAPに柔軟なデータ処理能力を与えている.
　1980年に最初の3台の商用機が設置され,現在も稼働中であるDAPはさらに拡張・改良が続けられており,今後が期待される.
　アレイ型計算機は,複数の演算装置を用意し,それらで同時に同じ命令を実行することで並列処理を実現していた,しかし,並列に実行できるのは同じ命令にすぎず,効果的に動作させるためには応用分野を特定しなければならなかった.これは,アレイ型計算機が結局はノイマン型計算機の変形にすぎなかったことに原因がある。つまりアレイ型計算機も,フォン・ノイマンの原理から脱却することはできないのである.

非ノイマン型のコンピュータを知らないから、何がどう不満なのか分からない。ノイマン型でいいではないか。素人には不満が分からない。

第3の光
　Flynnの分類によると,アレイ型計算機は複数のデータの流れ(stream)を1つの命令の流れで制御している。つまりSIMD型(single instruction stream/multiple data stream)の並列処理方式に属する.このように考えると,複数のデータの流れを複数の命令で並列に制御するMIMD型(multiple instruction stream/multiple data stream)の計算機を考えることができる.
　こうした考え方に基づき開発されたのが,Carnegie-Mellon大学で開発されたC.mmpやCm*である.これらの計算機は,DECのLSI-11を複数台用意し,それらを共有メモリや階層バスで接続したものである.こうした計算機では、処理は基本的に個々のプロセッサで独立に進められる.したがって,それらの処理は一般の計算機と変わりない.そして他のプロセッサと交信をする必要が生じた場合にのみ,共有メモリや階層バスを介して他のプロセッサとデータを交換する.このとき次のような問題が生じる.
　いまここで,プロセッサ1からプロセッサ2へデータを次々と転送している場合を考える.一般にこれを実現するために,共有メモリ上にバッファを設けそれを介してデータの転送を行うが,その際バッファの溢れや空を検出するためにバッファ中のデータの数を管理することになる.そこでバッファ中のデータの数を共有メモリ上のアドレスAに格納し,プロセッサ1ではデータをバッファに入れるごとに,アドレスAの内容を読み出し,それに1を加えてアドレスAへ書き込む処理を繰り返し行う.またプロセッサ2では,バッファからデータを取り出すごとに,アドレスAの内容を読み出し,それから1を引いてアドレスAへ書き込む処理を繰り返しているとする(図8参照).

　こうしたときに,ある時点でアドレスAの?容が5であったとしよう.この時,それぞれのプロセッサでの処理が図9に示すような時間関係で行われた場合,アドレスAの内容が正しいものではなくなってしまう.これは,プロセッサ2がアドレスAの内容に変更を加えている最中に,プロセッサ1がアドレスAを読み出してしまうために起こる.

　これを解決するために,MIMD型の計算機ではあるデータに変更を加えている間は他のプロセッサからアクセスできないようにする機構を用いている.たいていの場合はそのために特別のハードウェアを設けるわけではなく、ソフトウェアによってデータのロック・アンロックの処理を行っている.

この機構マイコンのCPUにも登場したと思う。あやふやだけどマルチコアCPUの1次キャッシュへのアクセスがこれではなかっただろうか。

再び
　MIMD型の計算機は,共有データのアクセスのたびに起こるデータのロック・アンロニック処理のオーバヘッドや,他のプロセッサによりロックされているデータをアクセスする際に生じる待ち時間などのため,処理の高速化という点ではあまり貢献しなかった.結局,MIMD型計算機も,フォン・ノイマンの原理を脱却することはできなかったわけである.
　しかし,C.mmp上に実装されたHydraなどのオペレーティング・システムは,「オブジェクト指向」という新しい概念を生み出したのである.MIMD型計算機は,オブジェクト指向という一般的な問題を並列に処理するための新しい示唆を与え,その後の計算機科学の歴史に大きな影響を与えたのである.
　やっと一筋の光明が見えてきた.

うむ、ここで「オブジェクト指向」が出てくるとは。
とにかく35年前は理解できないことが、その後のCPUの進歩や言語の進歩を体験したことにより少しはコメントを書けるようになった。
スクラップ作業は楽しい。