JPS6155706B2 - - Google Patents

Description

【発明の詳細な説明】

本発明は、高速計算のための並列処理計算機で
あつて、簡単な構成で数多くのプロセツサの組み
込みが可能で、しかも高能率なMIMD形の複合計
算機に関するものである。 従来、偏微分方程式のイクスプリシツト差分解
法に典型的に見られる様に、すべての格子点での
計算手順が同一である場合を想定し、各格子点毎
あるいは隣接する幾つかの格子点を集めたブロツ
ク毎の処理を１台づつのプロセツサに担わせると
いう構想に基くマルチコンピユーターあるいはマ
ルチプロセツサが幾つか知られている。そのう
ち、制御装置の一元的管理の下ですべてのプロセ
ツサが完全に同期して同じステツプ数のマイクロ
命令を実行するという２次元アレイプロセツサタ
イプのSIMD形計算機（ILLIACなど）ではか
なり限られた計算法に対して偉力を発揮するがそ
の他の計算法に対しては、離れたプロセツサ間の
データー転送や、それの一元的管理の面で不都合
な接続構成になつていて、あまり能率がよくな
い。次に、すべてのプロセツサ間のデーター転送
が直接的に行える様にするため共有メモリーと共
通バスを設ける方法も幾つか提案され、バス競合
やメモリー競合を時分割バスシステム、クロスバ
ススイツチシステムあるいは多ポートメモリーシ
ステムの形で処理しているが、それぞれ、バスコ
ントロールが複雑で能率が下つたり、ハードウエ
ア量が莫大になつたり、メモリーが高価となる欠
点を持つている。さらに、メモリー競合を避ける
ため、共有メモリー相当分を各プロセツサの私有
メモリー部分に設け、メモリーの更新はブロード
キヤステイング機能によつて行い、計算処理は各
プロセツサが独自で行うというSIMDとMIMDの
混合形計算機（天気予報用のSMS201など）もあ
るが、やはり用途が極く限られてしまう。 本発明は、一つに利用者側からみたとき偏微分
方程式の数値解法におけるADI法や分割作用素法
なども容易に使えるようにするためには一次元配
列構成のプロセツサ群の１台づつのプロセツサが
格子点の各一次元配列の計算を担う方が能率がよ
いこと、また行列演算やFFT計算でも、一次元
配列構成が無駄のない妥当なものであるとの知見
からなされた。もう一つはアーキテクチヤにおい
て、任意のプロセツサ間の直接的なデーター転送
が可能であるようにするために、クロスバタイプ
のネツトワークになるが、そのハードウエア量を
極力小さくするために一元的管理方式でなく、独
自で転送機能をもつバツフアメモリーを介するこ
と、そしてプロセツサ側でも能率向上化のために
DMAチヤネルを設けるという考えに基いてなさ
れた。 本発明の複合計算機では、それぞれが私有メモ
リーを有する１台の主プロセツサと複数Ｎ台の従
プロセツサからなる階層的アーキテクチアをとる
構成において並行処理の途中のデーターを従プロ
セツサ間で送受することのためにＮ行Ｎ列の２次
元配列のバツフアメモリーを設け、プロセツサ側
に具えるDMAチヤネルに接続する形をとる。 図面によつて本発明計算機の基本的なバス接続
方法を説明する。第１図及び第１Ａ図は、その基
本形及び機能モデルを示すものであり、主プロセ
ツサをMU、従プロセツサをAU−ｊ（ｊ＝０、
１、………、Ｎ−１）そして好ましくはFIFO型
のバツフアメモリーをBM−（ｉ、ｊ）（ｉ、ｊ＝
０、１、………、Ｎ−１）と記す。第１図におい
てMUのデーターバスは、すべてのBM−（ｉ、
ｊ）（ｉ、ｊ＝０、１、………、Ｎ−１）につな
がり、各AU−ｊのデーターバスはｊ行目のBM
−（ｉ、ｊ）（ｉ＝０、１………、Ｎ−１）および
ｊ列目のBM−（ｊ、ｋ）（ｋ＝０、１、………、
Ｎ−１）につながつている。 また、BMとしてFIFOを用いる場合には、好
ましい使用例としてこれらすべてのFIFOには出
力側から入力側へ戻す循環用データーバスも具え
られている。各BM−（ｉ、ｊ）でみるとき、第
２図に示されている様に、入力側にはAU−ｉお
よびAU−ｊからの２種のデーターバスがそれぞ
れゲートを通してつながり、出力側は、それぞれ
別のゲートを通して、入力側に入つたと同じデー
ターバスに接続されている。ただし、第２図の実
施例においては、MUとAUとのデータのやりと
りもBMを通して行う場合のためのバス、及び
BMとしてFIFOを用いるときの循環用データバ
スも付加してある。循環用データーバスはMUへ
のデーターバスが使用されるのと同時に使用され
るようになつている。そして、循環させる必要が
ないとき、そのバスは切れる様になつている。こ
の循環用バスは逐次計算過程で途中結果をMUに
送つたとき、それと同じデーターが引き続き、
AUでの計算に利用されるような場合にFIFOに
残しておくのが都合よいときに用いられる。 上記のようなパスビルデイングを持つた並列計
算機では、明らかに、MUと任意のAUの間およ
び任意のAU同志の間で直接的なデーター転送が
可能であるから汎用性が著しく拡がる。そのう
え、任意のAU同志間でデーターの相互変換が同
時にできて能率がよい。AU−ｉとAU−ｊの間
でデーター交換を行う場合に、AU−ｉがBM−
（ｉ、ｊ）にデーターを送り、つづいてBM−
（ｊ、ｉ）からデーターを受けとる動作と、AU
−ｊがBM−（ｊ、ｉ）にデーターを送り、つづ
いてBM−（ｉ、ｊ）からデーターを受けとる動
作が全く並行して行われる。さらに大事な点は、
互いに相手側のプロセツサの進行状況を直接に関
知することなく、間に立つBMにデーターが現れ
ることだけをみていればよい。しかも、そのデー
ターの出現を指示するOUTPUT READY信号を
DMAコントローラが受信する様にしてあるの
で、プロセツサとしてはそのデーターが実際に必
要になるまで他の計算を進めておればよく、非同
期式の利点がよく生かされている。 また、一元的管理方式を排した非同期式である
ために、本来、信号線の数が少くてよいととも
に、共通バスをもたないクロスバタイプのパスビ
ルデイングであるにも拘らず、各BMに外から接
続されるデーターバスはたかだか３種類だけであ
るために、ハードウエア量が比較的に少くてよい
点はプロセツサの台数を増すことに大きく道を拓
くものである。 つぎに、本計算機の並列処理動作の理解を容易
にするため、並列プログラムとその処理の概要を
説明する。この場合、取扱うべき２次元配列デー
タは、それらの格子点座標を（Ｉ、Ｊ）としたと
き（ただし、Ｉ、Ｊ＝１、２、３………Ｎ−１、
Ｎ）、文字Ｕで代表させ、通常はＵ（Ｉ、Ｊ）と
して表現されるべき変数である。 第１Ａ図は、第１図に示した従プロセツサ群
AU−０、………AU−（Ｎ−１）が、バツフア−
マトリクス〔BM−（ｉ、ｊ）〕を介しての接続構
造により、各バツフアーメモリーBMを前記各格
子点（Ｉ、Ｊ）に対応させた場合に格子点の各行
（Ｊ）を受けもつAU−縦列（実線円の列）と、
格子点の各列（Ｉ）を受けもつAU横列（破線円
の横列）として見られるという機能モデルを示し
たものである。ただし、従プロセツサAU及びバ
ツフアーメモリーBMにおける番号又は座標を表
わすｉ及びｊは０からＮ−１までの整数であり、
格子点座標のＩ及びＪは前記の通り、１からＮま
での整数であるため、それぞれ、ｉ＝Ｉ−１、及
びｊ＝Ｊ−１となることに留意すべきである。し
たがつて、２次元配列変数は各格子点（Ｉ、Ｊ）
について、縦列中のＪ（＝ｊ＋１）番目の従プロ
セツサAUにより、行位置（Ｉ＝１、２………
Ｎ）データを扱うことを意味した Ｕ（Ｉ、／Ｊ／） 及び、横列中のＩ（＝ｉ＋１）番目の従プロセツ
サAUによりＪ列のデータを扱うことを意味する Ｕ（／Ｉ／、Ｊ） として表わされる。これにより、並列演算はいず
れかの行位置中の全格子点、及びいずれかの列位
置中の全格子点について、各一つの従プロセツサ
により実行される。並列処理プログラムは、例え
ば次の通りである。 PDO 10 Ｊ＝１、Ｎ DO 20 Ｉ＝１、Ｎ 20U（／Ｉ／、Ｊ）＝Ｕ（Ｉ＋１、／Ｊ／） ＋Ｕ（Ｉ−１、／Ｊ／） 10 CONTINUE、 ここに、PDOは、PARALLELDO文を示し、
ラベル番号10までの実行文をインデツクスＪの動
く範囲に相当するAU−ｊ（ｊ＝Ｊ−１）の組が
各行位置について並列処理することを指示する。
インデツクスＩについてのDO文は指示された従
プロセツサが共通に行う標準的処理である。な
お、上記PDO文中に現れる式の右辺の配列変数
はすべてＵ（※、／Ｊ／）の形のものに限る（た
だし、列位置にあればＵ（／Ｉ／、※）の形とな
る）。これは明快な並列動作を指示するための制
約である。また、左辺には列位置用のＵ（／
Ｉ／、Ｊ）が出ているが、このとき、代入用の
“＝”操作の中にバツフアメモリを介したデータ
転送が含まれるのである。 上記の代入文では、第１Ａ図の縦列（実線）位
置にあるすべての従プロセツサは、ラベル番号20
の式の右辺の計算結果が出るだびに各従プロセツ
サが対応する行位置のバツフアメモリ（ｉ、ｊ）
群（ｉ＝０、１、………、Ｎ−１）に書き入れて
いく。指定された縦プロセツサによる上記のよう
なバツフアメモリへの書き込みが済めば、同じく
第１Ａ図の横列（破線図示）位置から見てすべて
の縦プロセツサがそれぞれにつながるバツフアメ
モリの内容を集め、これによつて｛Ｕ（／Ｉ／、
Ｊ）｝を得るものである。かくして、第１Ａ図の
列位置において、例えば次のようなプログラムに
移ることができる。 PDO 30 Ｉ＝１、Ｎ DO 40 Ｊ＝１、Ｎ 40U（／Ｉ／、Ｊ）＝Ｕ（／Ｉ／、Ｊ＋１） ＋Ｕ（／Ｉ／、Ｊ−１） 30 CONTINUE この例では代入文が転送をともなわないものに
なつている。 本発明の並列処理動作は上記のとおりであり、
以下、本発明の装置構成の実施例につき詳細に説
明する。 実施例 本発明の効果を確認するための試作例を掲げ
る。この実施例では、市販のマイクロコンピユー
タの中で、本発明の試作実施に都合がよいと判断
した８ビツトマイクロプロセツサF8（米フエア
チヤイルド社およびモステツク社）を用いた。全
体構成の概略は第３図に示されている。主プロセ
ツサMUと16台に示されている。主プロセツサ
MUと16台の従プロセツサAU−ｊ（ｊ＝０、
１、２、………、Ｆ−16進数表示）と16行16列の
２次元配列のバツフアメモリーBM−（ｉ、ｊ）
を構成するFIFO群からなつている。MUは
CPU3850とDMI3852（ダイナミツクメモリーイ
ンターフエイス）と２台のDMA3854（ダイレク
トメモリーアクセス）とPIO3861（ベリフエラル
Ｉ／Ｏ）と4KバイトROMおよび8KバイトRAM
から成つている。１台のDMAは従プロセツサと
のデーター送受を制御し、もう１台のDMAは
Ｉ／Ｏプロセツサ（この試作品ではF8ソフルウ
エアー開発用ボードSDB−50 MK79019を利用）
とのデーター送受を制御する。PIOはMUが直接
にデーターを入出力するためと、AUからの割り
込み要求を受け入れるために具えられている。ま
た、すべてのAUは同一構成になつていて、それ
ぞれCPU、DMI、DMA（１台）、2KバイトROM
および4KバイトRAMから成つている。そして、
各FIFOメモリーは、64ワード×４ビツト
FIFO3341Aの２ケを並列接続して作られてい
る。この実施例の全体構成の主要部とバス接続の
模様が第３図に示されている。図では、例えば、
FIFO（Ｏ、Ｆ）には、MUからと、AU−Ｆから
と、AU−Ｏからのバスおよび循環用バスが接続
されている様子が読みとれるであろう。 第２図に示した各FIFOメモリーにおけるバス
接続法を実施した回路が第４図に描かれており、
ゲートの開閉の論理が図の中央部に示されてい
る。この論理はプロセツサとFIFOの間の信号線
の開閉にも利用される。FIFO−（ｉ、ｊ）への
データーシフトイン要求（SI REQ）あるいはデ
ーターシフトアウト要求（SO REQ）は関与す
る３台のプロセツサMU，AU−ｊ，AU−ｉから
くるが、SI REQとSO REQは全く独立に受け入
れられるようになつている。第４図の中央の左側
にSI REQ用、右側にSO REQ用の論理が組んで
あるが、いずれにおいても１つのプロセツサがこ
のFIFOとの間のデーターの送受を行つていると
き、他のプロセツサの要求は受けつけられないよ
うになつている。要求が受け付けられたプロセツ
サにはイソプツトレデイー（IR）あるいはアウ
トプツトレデイー（OR）信号が と
して送られる。FIFOはそのプロセツサからの
XFER信号を受けると同時にデーターを入力する
があるいは出力する。各プロセツサのSI REQお
よびSO REQ信号は、CPU上のポート１（P1）
にラツチさせるデーターから作られる。MUが
FIFO−（ｉ、ｊ）とデーターをやりとりしたい
ときには（P1）_7〜0に16進２ケタ数字‘ij’をお
く。AU−ｊがFIFO−（ij）とデーターをやりと
りしたいときには（P1）_4〜0に‘oi’をおく。同
じくAU−ｊがFIFO−（ｊ、ｉ）とデーターのや
りとりをするときには（P1）_4〜0に‘1i’をお
く。このデーターはプロセツサがDMAコントロ
ーラに始動を指示するのに先立つてラツチされな
ければならない。そのデーターによつてSI
FEQ、SO REQ信号を作る論理は第５図に示さ
れている。この図で、点線で囲んだ部分がそれぞ
れ１枚の板の上に乗せられる分である。REQ−
ｊ板とはｊ行目に並ぶFIFO群（FIFO−（ｉ、
ｊ）（ｉ＝０、１、２、………、Ｆ）とｊ列目に
並ぶFIFO群（FIFO−（ｊ、ｉ）（ｉ＝０、１、
２………、Ｆ））へ送るSI REQとSO FEQ信号
を作る論理を乗せた板である。なおFIFO群その
ものは各行に並ぶものを集めて１枚の板に乗せ
る。 MUと各AU−ｊ間で送受される、その他の信
号はCPU上のポート０（P0）を通して交わされ
る。第６図にその詳細が描かれている。ここで、
MUの（P0）_3〜0には信号を交わしたいプロセツ
サAU−ｊの16進番号‘ｊ’をラツチする。それ
に加えて（P0）₆に１をおくときは、AU−ｊに計
算のスタートを指示するものと約束し、（P0）₄に
１をおくときは、再度プログラム読み込みの状態
に戻すことを指示するものと約束する。またMU
が（P0）₇に１を受けたときはAU−ｊから計算終
了の信号が送られたものと解する。つぎに、MU
が（P0）₅に１をおくときは、（P0）_3〜0の値に拘ら
ず、すべての従プロセツサに同時に同じ指示を与
えることを意味する。一方、Ｕ−ｊ側では、
（P0）₇に１をおくことはMUを計算終了を知らせ
ることであり、（P0）₅に１をおくことはMUに割
り込み要求をすることをになつている。また、
（P0）₆に１を受けると計算のスタート指示を得た
と解し、（P0）₄に１を受けると、計算を休止し、
再度プログラム読み込み状態に戻る指示を得たと
解するものとする。 参考計算例 この試作実施例を用いる計算例をあげ、単一の
CPUで行う計算（いまの場合、MUだけで行う計
算）との比較により、本発明計算機の効果につい
て述べる。なお、以下で計算時間とは機械語で作
成したプログラムをたどつて算出したものであ
る。 そのまえに、まずこの実施例計算機に組み込ま
れた各プロセツサの基本サイクルと基本ルーチン
処理時間をあげておく。F8 CPUのクロツクは最
大2MHzであつて、このクロツクで作動させると
クロツクサイクルは500nsである。マシンサイク
ルには短いものと長いものとがあつて、それぞれ
２μｓ（４クロツクサイクル）と３μｓ（６クロ
ツクサイクル）である。個々の命令サイクルは、
これらのマシンサイクルの組み合せからなり、最
短２μｓのものから最長13μｓのものまである。
なお、各マシンサイクルの間でCPUがメモリー
の読み書きをしていない残余の時間にRAMのリ
フレツシユやDMA転送を行うので、DMA転送ス
ピードは高速で、ほぼ１マシンサイクルあたり１
バイトの転送が行われる。実際にはリフレツシユ
モードや命令の種類により、巾があつて１バイト
の転送時間の最短２μｓから最長５μｓである。 さて、浮動小数点演算はすべて４バイト長（指
数部１バイト、仮数部３バイト）で行うものとす
る。浮動小数点演算用のマイクロプログラムは、
すべてのプロセツサの私メモリーROMに入れて
ある。そのうち幾つかのサブルーチンの計算実行
時間をあげておく。浮動加減算は、場合によつて
巾があり、26μｓ〜1600μｓとなるが、通常の場
合を想定すれば、大きめにみて１ｍｓ程度とな
る。また浮動乗算（ブース法）は、3.5ｍｓ、浮
動除算（引き放し法）は４ｍｓになる。浮動小数
点数のレジスター間転送は20μｓ、メモリー・レ
ジスター間転送は32μｓである。また浮動小数点
数１語をFIFOを介して転送するには（FIFOに
停まることがないとき）典型値で20μｓかかる
が、これはCPU内でのレジスター間転送と同程
度である。ただしこれらの転送を行うサブルーチ
ンへジヤンプする前の置数等にかかる時間に違い
があつて、レジスター間転送へ行くまえに17μ
ｓ、レジスター・メモリー間転送へ行くには25μ
ｓ、FIFOを介したメモリー・メモリー間転送へ
行くには53μｓだけかかる（この場合、DMAコ
ントローラへの指示も含まれる）。 次に、効果と直接に関係ないが、FIFOバツフ
アメモリーを介したデーター転送のソフトウエア
上の便宜をはかつておく。すなわち、FIFOの２
次元配列に対応した専用メモリーをMUおよびす
べてのAUのRAM中に設ける。MUのRAMには、
16×16の２次元配列状のメモリーを確保するもの
とし、しかも各結節点に４ワード（16バイト）分
の容量を用意する（これを深さ４ワードのメモリ
ーと表現し、各ワード分に番号ｍ＝０、１、２、
３をつける）。そのために必要な4096バイト用に
バイト番地2000〜2FFFをあてる。そしてFIFO
−（ｉ、ｊ）に対応するのが2ijo〜2ijFの４ワー
ド長である。一方、AU−ｊのRAMには、これに
直接つながるクロス状配置のFIFO−（ｉ、ｊ）
（ｉ＝０、１、………、Ｆ）とFIFO−（ｉ、ｋ）
（ｋ＝０、１、………、Ｆ）に対応して１次元配
列状のメモリーを２つ並びだけ確保するものと
し、しかも各点に深さ８ワード分を用意する（各
ワードに再び番号ｍ＝０、１、………、７をつけ
る）。そのために必要な1024バイト用にバイト番
地1COO〜1FFFをあてる。そのうち1COO〜
1DFF番地が横線状配置のFIFO−（ｉ、ｊ）（ｉ
＝０、１、………、Ｆ）に対応し、1EOO〜
1FFF番地が縦線状配置のFIFO−（ｉ、ｋ）（ｋ
＝０、１、………、Ｆ）に対応する。そして
FIFO−（ｉ、ｊ）に対応するのが‘1COO＋20×
ｉ〜1CIF＋20×ｉ’の８ワード長で、FIFO−
（ｊ、ｋ）に対応するのが、‘1EOO＋20×ｋ〜
1EIF＋20×ｋ’の８ワード長である（第７，
８，９図参照）。以下では、MUの深さをもつた
２次元配列専用メモリーあるいはAUの深さをも
つたクロス状配列専用メモリーにおいて同一の深
さ位置にある（スライスされた）メモリーを表現
するために記号((ｍ＝・))を用いることにする。
さらに、AUの場合、クロス状メモリーのうち、
横線上のものに行メモリー、縦線上のものに列メ
モリーを冠して呼ぶことにする。 計算例 １ （行列の積） 16行16列の２つの行列ＡとＢがMU内の専用メ
モリー((ｍ＝０))と((ｍ＝１))に与えられてい
て、行列の積ABを計算して、結果を((ｍ＝０))
に入れるものとする。この計算をAU群によつて
行うために、Ａの各行を対応するAUの行メモリ
ー((ｍ＝０))へ送る（Ａの第ｊ行｛ａ｝ｉ＝
０、１、………、ＦをAU−ｊに送る）。つぎ
に、Ｂの各列を対応した列を位置するすべての
FIFOに（シリアルに）入れる。（第ｋ列にある
FIFO−（ｋ、ｉ）（ｉ＝０、１、………、Ｆ）に
はすべて同じくＢの第ｋ列の要素がつめられる。
いまの場合、ちようど16ワード分で各FIFOが一
杯になる）。AU−ｊはｋ＝０、１、………、Ｆ
の順に、FIFO−（ｋ、ｊ）のデーターを受けて
は積和

【式】を計算し、その結果を行メ モリー((ｍ＝１))にストアする。この計算はすべ
てのAUが並行して行うことになる。最後に、各
AUの行メモリー((ｍ＝１))のすべてをMUの専
用メモリー((ｍ＝０))に転送してやればよい。以
上の計算に必要な時間は1.27秒になる。このうち
各AUが16ケの積和を計算する時間が1.20秒であ
り、大部分を占めている。 比較のために、上の計算を並列処理でなくMU
だけで単一処理を行うと、そのときの計算時間は
19.4秒となる。従つて（並列処理時間）／（単一
処理時間）＝１／15.3である。16台のAUを用いて
15.3倍のスピードアツプだから能率比は0.95（＝
15.3／16）であるといえる。 計算例 ２ （連立一次方程式のガウス消去解法） 16元連立一次方程式 を解く問題で、係数行列Ａ＝｛aji｝の各行に対応
したAUの行メモリー((ｍ＝０))にあらかじめ与
えられているとする。行列Ａの第ｊ行｛aji｝ｉ
＝０、………、ＦはAU−ｊの行メモリー〓ｍ＝
０))に与えられる。そして、方程式の右辺のデー
ター｛bj｝ｊ＝０、１、………、ＦがMU内のあ
る場所（例えばIBCO〜IBFF番地）に与えられた
とき、方程式を解き、その解｛xi｝ｉ＝０、１、
………、Ｆを同じ場所にストアするものとする。
この問題をガウス消去法で解くために、まず
｛bj｝ｊ＝０、１、………、Ｆの各成分bjをそれ
ぞれAU−ｊの一定の場所（例えばIEOO〜IE03
番地）に転送する。転送後は、AU側だけで計算
されるが、ここでは、消去の際、特別なピボツテ
イングが不要で単純に計算が続くものとして、計
算時間の評価を行う。さて、未知数x₀の消去を行
うために係数（ａ_０１／ａ_００、ａ_０２／ａ_００、……
…、ａ_０Ｆ／ａ_００、ｂ_０／ａ_００）を AU−０で計算し、その結果をAU−１からAU−
Ｆまでのすべてに送る。このとき、AU−ｊ（ｊ
＝１、２、………、Ｆ）に送るには、FIFO−
（ｊ、０）（ｊ＝１、２、………、Ｆ）を介すると
よい。それを受けたすべてAUで消去計算を並行
して行う。次に、変数x₁の消去のために、係数計
算をAU−１で行い、AU−２からAU−Ｆまでの
すべてに送る。それを受けたAUで消去計算を並
行して行う。この操作を順次繰り返えしていく。
最後にたどりついた式からAU−Ｆがｘ_Fの値を
決めると、この値の代入計算にうつるが、その場
合、ｘ_Fの値をすべてのAU−Ｅ〜AU−０へ順に
転送し、それぞれにおいてｘ_Fの代入計算をやつ
てしまう。つづいて、AU−Ｅで未知数ｘ_Eを決
め、その値をAU−Ｄ〜AU−０へ順に転送し、
それを受けたAUでは直ちにｘ_Eの代入計算を済
ませてしまう。このように逐次代入計算を行つて
いくが、その際、既知となつたxj値をすべての
AU−ｋ（ｋ＝ｊ−１、ｊ−２、………、０）に
転送している間、その値を得たAU−（ｊ−１）
は直ちにｘ_j-1を決める計算を同時に行うことが
可能である。また得られた解の値をMUに送るこ
とも計算の終つたAUから順次行えばよい。以上
の計算に要する時間は887ｍｓである。 一方、同じ問題をMUだけで単一処理する場合
の時間は7277ｍｓである。従つて（並行処理時
間）／（単一処理時間）＝１／8.2となり、能率比
は0.51（＝8.2／16）である。この場合、能率比
が0.51まで落ちこむのは、ガウス消去法のアルゴ
リズムに本来的にシリアルな部分がかなりの割合
を占めるからであつて、止むを得ないことであ
る。 計算例 ３ （FFTの計算） FFTの計算を、本発明の並列処理計算機でど
のように行うかを説明するために必要な範囲で、
もともとのアルゴリズムを述べる。取り扱う離散
的なフーリエ変換を式 で定義する。ただし、ここで簡単のために、Ｎ＝
２〓（γは自然数）とする。FFTの計算法では
｛x₀(k)｝から｛Ｘ（ｎ）｝を求めるために ｛x₀(k)｝→｛x₁(k)｝→……… →｛ｘ_l(k)｝→………｛ｘ〓(k)｝ のステツプをを踏む。ここで｛ｘ_l-1(k)｝から
｛ｘ_l(k)｝の計算には、対になつた式の組 を用いる。ここでｐの値はインデツクスｋをγビ
ツトの２進数字で表示し、つぎにこの２進数字を
γ−ｌビツト分右シフトし、上位γ−ｌビツトに
は０を埋め、その後ビツトの順序をひつくり返え
した２進数字のとる値に等しくする。最後に得ら
れた｛ｘ〓(k)｝から求める｛Ｘ（ｎ）｝を得るた
めには、ｎの２進数表示のビツト順序をひつくり
返えしたときの値をと表わすとき、Ｘ（ｎ）＝
ｘ〓（）とすればよい。 （※）式の計算は、具体的には の形で行われる。 このアルゴリズムをMUだけで実行する場合に
は、（※）式に従つてｘ_l(k)とｘ_l（k′）の対毎に計
算を行つていくので、ｋ＝０、１、２、………と
順を追つていけば、先に計算済みのものに到るこ
とがあるが、そこはとばして先に行けばよい。例
えばＮ＝16（γ＝４）のとき、｛x₁(k)｝を求める
のに、ｋ＝０、１、………、７まで計算すれば、
ｋ＝８、………、Ｆに対する計算は既に済んでい
る。 上のアルゴリズムをできるだけ並列処理によつ
てAU群で実行する方法を説明する。まず、途中
で必要になるCOS値、SIN値の数表があらかじめ
用意されている場合について述べる。ｘ_l(k)の計
算は、AU−ｋが担うものとすれば番号の対ｋと
k′に対応したプロセツサAU−ｋとAU−k′（※
※）の計算を並行処理させる。実際に、AU−
k′が、ｘ_l-1（k′）値をFIFO−（k′、ｋ）に送るの
と同時にAU−ｋはｘ_l-1(k)をFIFO−（ｋ、k′）に
送る。そしてAU−k′がFIFO−（ｋ、k′）からｘ_l
−１(k)を受けとるのと同時にAU−ｋはFIFO−
（k′、ｋ）から、ｘ_l-1（k′）を受けとる。つづい
て、AU−k′がTRを計算し、その計果をFIFO−
（k′、ｋ）に送るのと同時に、AU−ｋはTIを計
算し、その結果をFIFO−（ｋ、k′）に送る。そし
てまたそれぞれのプロセツサが対応したFIFOを
介してTIあるいはTRを受けとる。最後に、AU
−k′はｘ_l（k′）の値を決め、AU−ｋはｘ_l(k)の値
を決める。これらの動作がすべての対（ｋ、k′）
に対して同時に並行的に行われ、そしてｌ＝１、
２、………、γと逐次計算される。 さて、COS値、SIN値を数表で与えておくので
はなく、必要の都度計算する場合には、CORDIC
法を用いると都合がよい。それは、このアルゴリ
ズムがまた一対のAU−ｋとAU−k′を用いること
によつてうまく計算されるからである（CORDIC
法そのものの計算については後掲の計算例４で述
べる）。 Ｎ＝16として、16台のAUを用いる場合の計算
時間を掲げておく。 (i) COS値、SIN値の数表をあらかじめ用意して
おく場合 MUだけによる計算では690ｍｓである。一
方、MUからAU群にデーターを与え、その後
AU群に計算を行わせ、最終結果をMUにまで
戻す時間は60ｍｓとなる。したがつて（並列処
理時間）／（単一処理時間）＝１／11.5であ
り、能率比は0.72（＝11.5／16）となる。 (ii) COS値、SIN値を必要の都度CORDIC法によ
つて計算する場合 MUだけで行う計算時間は2600ｍｓであり、
AU群によつて計算する場合は244ｍｓとな
る。したがつて（並列処理時間）／（単一処理
時間）＝１／10.66であつて、能率比は0.67（＝
10.66／16）となる。 上の結果で、(i)の場合の能率比が0.72ほどまで
になるのは、MUだけで行う計算においてとばす
ということがなされるのに対してAU群による計
算では確かにうまく対毎の計算が行われスピード
アツプになるが、転送にかかる時間分だけ能率を
おとすからである（とばす計算時間は０であ
る）。(ii)の場合には、さらにCORDIC法が完全に
並列化されるアルゴリズムでないことによつても
う少し能率比が落ちてしまうのである。 計算例 ４ （CORDIC法によるCOS値、SIN値の計算） 計算例３のFFT計算で必要になつたのはcos
ｐπ／８、sinｐπ／８（０ｐ７）の値であつた。
ここ ではｐを与えたとき、それらの値をCORDIC法に
基いて、２台のAU−ｋとAU−k′の対が計算する
ものとする。４ｐ７に対しては関係式cos
ｐπ／８＝−cos８−ｐ／８πとsinｐπ／８＝sin８−
ｐ／８πを利用す るものとすれば０ｐ３に対して計算されれば
よい。この場合アルゴリズムは次の様になる。 初期値を x₀＝0.60725293501………、y₀＝０、v₀＝ｐπ／
８とおき、ｎ＝０、１、２、………、16に対して
次の反復計算を行う（完止法）（ｎ＝16でとめて
いるのは10進で５桁ぐらいの精度でよしとするか
らである）。 (i) ｖ_o〓０ならばｘ_o+1＝ｘ_o−２^-nｙ_o、 ｙ_o+1＝ｙ_o＋２^-nｘ_o、ｖ_o+1＝ｖ_o−γ_o、 (ii) ｖ_o＜０ならばｘ_o+1＝ｘ_o＋２^-nｙ_o、 ｙ_o+1＝ｙ_o−２^-2ｘ_o、ｖ_o+1＝ｘ_o＋γ_o ただし、ここでγ_o＝arctan2^-n（ｎ＝０、１、
２、………、16）の値は用意されているとする。
最後に得られるx₁₇とy₁₇をそれぞれcos ｐπ／８
とsin ｐπ／８の近似値とするものである。この
アルゴリズムをAU−ｋとAU−k′の対に実現させ
るとすれば、AU−ｋに｛ｘ_o+1を決める計算さ
せ、AU−k′に｛ｙ_o+1｝を決める計算をさせるも
のとする。初期値や｛γ_o｝、｛ｖ_o｝の値はいづれ
のAUも保持し、｛ｖ_o+1｝の計算はどちらのAUに
おいても実行するものとする（一方だけで計算し
て他方に転送する方法よりすこしだけスピードが
早いからである）。このとき１つのｐに対して計
算時間は47.7ｍｓとなる。 一方、上記アルゴリズムを単独のMUだけで計
算するときの時間は60ｍｓである。従つて（並列
処理時間）／（単一処理時間）＝１／1.2となり、
能率比は0.6（＝1.2／２）である。能率比が0.6に
とどまるのは、｛ｖ_o+1｝の計算を２台のプロセツ
サで分業することができないからである。このこ
とが、また計算例３の最後のところに述べたこと
につながるのである。 計算例 ５ （ADI法の応例−ナビエ・ストークス方程式の
差分解法） 非圧縮性粘性流体の２次元的流れを記述するナ
ビエ・ストークス方程式を流れ関数Ψと渦度ζを
用いて表現すれば ∂ζ／∂ｔ＋∂Ψ／∂ｙ∂ζ／∂ｘ−∂Ψ／∂ｘ∂ζ／
∂ｙ＝１／ＲΔζ （Ｒはレイノズル数） ζ＝−ΔΨ となる。いま、正方形状のくぼみ領域０＜ｘ、ｙ
＜１内の流れを考えるものとし、 境界条件 Ψ＝０ および ∂Ψ／∂ｘ（０、ｙ）＝∂Ψ／∂ｘ（１、ｙ）＝０、 ∂Ψ／∂ｙ（ｘ、０）＝０ ∂Ψ／∂ｙ（ｘ、１）＝Ｕ を与える。そして初期条件は静止状態に対応した Ψ＝０、ζ＝０ とする。これは、くぼみの中の流体が開いた一辺
での一様速度Ｕでどのように駆動されるかをみる
ためのモデルになつている。 上の偏微分方程式系を近似的に解く差分法の中
でADI法の範ちゆうに入るものの一例をあげる。
正方形領域０＜ｘ、ｙ＜１の各辺を15等分し、格
子間隔ｈ＝１／15の網目をつくり、格子点（ｘ
_i、ｙ_j）＝（ih、jh）上の未知関数値をζ_i、_jなどと
表わす。また、時間ステツプ巾をτとし、時刻ｔ
＝ｎτにおける値を、さらに上つき添数でもつて
ζ^ｎ _ｉ、_ｊなどと表わす。差分商に対して次のような
記号を用いる： Δ_1hζ_i、_j＝１／ｈ^２（ζ_i+1、_j−２ζ_i、_j＋ζ_i-1、_j
）、 Δ_2hζ_i、_j＝１／ｈ^２（ζ_i、_j+1−２ζ_i、_j＋ζ_i、_j-1
）、 δ_1hζ_i、_j＝１／２ｈ（ζ_i+1、_j−ζ_i-1、_j）、 δ_2hζ_i、_j＝１／２ｈ（ζ_i、_j+1−ζ_i、_j-1）、 実際に、計算例として用いる差分アルゴリズム
は次の通りである：Ｊ＝15として

【表】

【表】 ここでΨの上つき添数ｒは内部反復の何回目で
あるかを示し、その反復回数をＲ_o+1、反復のパ
ラメーターをτ^ｎ＋１〓としている。 上記のアルゴリズムをAU群によつて実現する
ために、ζ計算の前半部分(1)の、各ｊに対応した
値の組

【式】（ｉ＝１、２、………、Ｊ− １）を未知数とする連立方程式を解くことを各
AU−ｊに行わせ、後半部分(2)の、各ｊに対応し
た値｛ζ^ｎ＋１ _ｊ、_ｋ（ｋ＝１、２、………Ｊ−１）を
未
知数とする連立方程式を解くこともAU−ｊに行
わせるものとする。Ψについて解く(3)、(4)でも同
様な分担を行う。 以下では、１回の時間ステツプｎ＋ｎ−１を踏
むのにかかる計算時間を考えるものとする。い
ま、AU−ｊに着目し、そのメモリーに｛ζ
^ｎ _ｉ、_ｊ｝、｛Ψ^ｎ _ｉ、_ｊ｝（ｉ＝０、１、２、………
、Ｊ）
および｛ζ^ｎ _ｊ、_ｋ｝、｛Ψ^ｎ _ｊ、_ｋ｝（ｋ＝０、１、
……
…、Ｊ）が保持されているとする。そして、各
AU−ｉ（ｉ＝１、………、Ｊ−１）には｛h₂Δ_2
ｈζ^ｎ _ｉ、_ｊ｝、｛2hδ₂hζ^ｎ _ｉ、_ｊ｝｛2hδ₂hΨ^ｎ _ｉ
、_ｊ｝（ｊ＝
１、２、………、Ｊ−１）の値も保持されている
とする。なお、各AU−ｉが｛ζ^ｎ _ｉ、_ｊ｝と｛Ψ
^ｎ _ｉ、_ｊ｝の値を知つてさえいれば、上記の差の値を
計算することは容易である（これに対して、その
AU−ｉが同じデーターをもつていても、h₂Δ_1h
ζ^ｎ _ｉ、_ｊ、2hδ_1hζ^ｎ _ｉ、_ｊなどは直ちに計算できな
い。
というのはAU−ｉ自身にはζ^ｎ _ｉ±１、_ｊの値は保持
されていないからである）。 さて、手順を述べる。 (i) まずAU−ｊはすべてのAU−ｉ（ｉ＝１、
２、………、Ｊ−１）からそれぞれFIFO−
（ｉ、ｊ）を介して｛h²Δ_2hζ^ｎ _ｉ、_ｊ、2hδ_2hζ
^ｎ _ｉ、_ｊ、2hδ_2hΨ^ｎ _ｉ、_ｊ｝の値を受けとる。そうす
る
と、

【式】 に関する方程式(1)の係数ならびに右辺の値がす
べて決まる。特に右辺の（ ）の値（それとＡ
^ｎ _ｉ、_ｊとかく）は(2)式を解くときも再び利用され
るのでメモリーに保持しておく。そして ｛τ／８ｈ^２×2hδ_1hΨ^ｎ _ｉ、_ｊ｝（ｉ＝１、２、…
……、 Ｊ−１）の値を計算し、ストアしておく。 (ii) AU−ｊはダブルスウイープ法によつて(1)式
を解き、

【式】 （ｉ＝０、１、………、Ｊ）を決める。その
際、逆スウイープの段階で

【式】 がｉ＝Ｊ、Ｊ−１、Ｊ−２、………、０の順に
決まつてくるが、それがすべて済むのを持つの
でなく

【式】 が一つづつ決まる毎に、値の組｛

【式】τ／８ｈ^２ ・2hδ_1hΨ_i、_j、Ａ^ｎ _ｉ、_ｊ｝をDMAチヤネルを
通してFIFO−（ｉ、ｊ）に送る。 (iii) 次にAU−ｊはすべてのFIFO−（ｊ、ｋ）
（ｋ＝１、２、………、Ｊ−１）からそれぞれ
｛

【式】τ／８ｈ^２ ・2hδ_1hΨ_j、_k、Ａ_j、_k｝の値を受けとる。
そうすると、｛ζ^ｎ＋１ _ｊ、_ｋ｝（ｋ＝０、１、………
、
Ｊ）に関する連立方程式(2)の係数および右辺の
値をすべて知つたことになる。そこで再びダブ
ルスウイープ法によつてこの方程式を解く。そ
して値の組｛ζ^ｎ＋１ _ｊ、_ｋ、h²Δ_2hΨ^ｎ _ｊ、_ｋ｝をDM
Aチ
ヤネルを通して各FIFO−（ｊ、ｋ）（ｋ＝１、
２、………、Ｊ−１）に送る（もちろん、h²Δ
_2hΨ^ｎ _ｊ、_ｋはあらかじめ計済算みとしている）。 (iv) さらにAU−ｊはすべてのFIFO−（ｉ、ｊ）
（ｉ＝１、２、………、Ｊ−１）からそれぞれ
｛ζ^ｎ＋１ _ｉ、_ｊ、h²Δ_2hΨ^ｎ _ｉ、_ｊ｝の値を受けとる
。既に
保持している｛Ψ^ｎ _ｉ、_ｊ｝とあわせば、方程式(3)
の右辺の（ ）の値（それをＢ^ｎ＋１、^０ _ｉ、_ｊとかく
）
が決まる。そこで再びダブルスウイープ法によ
つて

【式】 （ｉ＝０、１、２、………、Ｊ）を決める。そ
して、値の組｛Ｂ^ｎ＋１、^０ _ｉ、_ｊ、

【式】 ｝を各FIFO−（ｉ、ｊ）（ｉ＝１、２、……
…、Ｊ−１）に送る。 (v) AU−ｊはすべてのFIFO−（ｊ、ｋ）（ｋ＝
１、２、………、Ｊ−１）からそれぞれ｛Ｂ
^ｎ＋１、^０ _ｊ、_ｋ、

【式】 ｝を受けとり、(4)式を解き、｛Ψ^ｎ＋１、^１ _ｊ、_ｋ｝
を決
める。そして値の組｛h²Δ_2hΨ^ｎ＋１、^１ _ｊ、_ｋ、Ψ
^ｎ＋１、^１ _ｊ、_ｋ｝をFIFO−（ｊ、ｋ）（ｋ＝１、２、
…
……、Ｊ−１）に送る。 (vi) 再びAU−ｊはすべてのFIFO−（ｉ、ｊ）
（ｉ＝１、２、………、Ｊ−１）からそれぞれ
｛h²Δ_2hΨ^ｎ＋１、^１ _ｉ、_ｊ、Ψ^ｎ＋１、^１ _ｉ、_ｊ｝を
受けとり、方程
式(3)の右並Ｂ^ｎ＋１、^１ _ｉ、_ｊを計算し、それを解く
とに
よつて

【式】 を決める。そしてまた（Ｂ^ｎ＋１、^１ _ｉ、_ｊ、

【式】 ｝を各FIFO−（ｉ、ｊ）に送る。 (vii) 以下(v)と同じ動作→(vi)と同じ動作→………→
(v)と同じ動作を繰り返えすことによつて｛Ψ
^ｎ＋１ _ｊ、_ｋ＝Ψ^ｎ＋１、^Ｒｎ＋１ _ｊ、_ｋ、｝を決める
に到る。ただ
し、最後の(v)の動作では値の組｛ζ^ｎ＋１ _ｊ、_ｋ、h²
Δ
_2hζ^ｎ＋１ _ｊ、_ｋ、2hδ_2hζ^ｎ＋１ _ｊ、_ｋ、2hδ_2hΨ^ｎ
＋１ _ｊ、_ｋ、Ψ
_ｏ＋１ｊ、_ｋ｝を各々FIFO−（ｊ、ｋ）（ｋ＝１、２、
………、Ｊ−１）に送ることによつて全体のル
ープの(i)に戻ることができる。 ここに述べた動作を行うために、保持したり、
転送したりするデーターが幾種類かあるが、これ
らをストアするために既述したAU内の専用メモ
リーを利用するのである（第９図参照）。それぞ
れの位置に深さ８ワード分の容量があつて、それ
らに番号ｍ＝０、１、２、………、７とつけた。
具体的に各データーをどのワードに割り振るかを
示した例が第１０図に示されている。第１０図で
は、一つのAU−ｊが行う反復計算の途中で、ど
の値がFIFOに送られ、FIFOから受けとられる
かについても示されている。第１０図でＨ−Ｒと
あるのはAU−ｊ内の行メモリーのそれぞれに受
けとられる値の種類を示している。Ｈ−Ｓとある
のは同じ行メモリーのそれぞれからFIFOに送る
値の種類を示している。Ｖ−Ｒとあるのは列メモ
リーのそれぞれに受け入れられる値、Ｖ−Ｓは同
じく列メモリーのそれぞれから送り出す値を示し
ている。上の方からＨ−Ｒ、Ｈ−Ｓ→Ｖ−Ｒ、Ｖ
−Ｓ→Ｈ−Ｒ、Ｈ−Ｓ→………→Ｖ−Ｒ、Ｖ−Ｓ
の繰り返えし計算でｎ→ｎ＋１の１ステツプが完
了することが示されている。ただし、送り状態
（Ｓ）で斜線の引いてない値は単に保持しておく
ことを示し、受けの状態（Ｒ）で斜線の引いてな
い値は、既に保持されたままのものであることを
示している。 上のアルゴリズムで１ステツプすすめるために
必要な計算時間は内部反復回数Ｒ_o+1を５回とす
るならば3875ｍｓになる。同じ計算をMUだけで
行うと、54156ｍｓとなる。従つて、（並列処理時
間）／（単一処理時間）＝１／13.8であり、能率
比0.99（＝13.8／14）となる（いまの場合、実働
のプロセツサAUは14台としている）。これは高
能率比である。それは、実際に並列処理する場
合、FIFOを介する転送にかかる時間が18μｓ／
１ワードぐらいで、それらを合わせても全体の
0.5％に過ぎず、実質的計算部分の殆んどが並列
処理されていることになるからである。 上の結果は、14台のAUを用いて並列処理した
場合のものであるが、これを一般化して、Ｑ台の
AUを利用して、内部反復回数をＲとしたとき、
１ステツプすすめるのに要する計算時間は（74.1
＋40.3R）Ｑ＋1.0R＋15.0ｍｓ（Ｒ＝５なら
275.6Q＋20.0ｍｓ）となる。MUだけで計算する
場合は（73.1＋39.9R）Q²＋（16.2＋0.2R）Ｑｍｓ
（Ｒ＝５なら272.6Q²＋17.2Qｍｓと評価される。
これから、Ｑが大きな値になれば、AU群で行う
ときおよそ（74.1＋40.3R）Ｑｍｓ、MUだけで行
うときおよそ（73.1＋39.9R）Q²ｍｓである（こ
の場合Ｑとは一辺がＱ＋１等分された格子点上で
考えていることにあたる）。従つて（並列処理時
間）／（単一処理時間）＝１／0.988Q（Ｒ＝１の
とき）でＲも大きくなると＝１／0.99Qになる。
従つて能率比はやはり0.99となる。 この例のような非線形偏微分方程式をADI法で
解くとき、各AUが処理する計算が十分に複雑で
あつて、明らかに転送にかかる時間に比して多く
の時間が必要なので能率比が極めて高くなつた印
象を与えるかもしれないが、実は方程式自体が簡
単な形をしたポアソン方程式でも能率比は0.99を
下らないことが次の例でわかる。 計算例 ６ （ADI法の応用例−ポアソン方程式の差分解
法） 計算例５で考察したナビエ・ストークス方程式
の後半のΨに対する方程式ΔΨ＝−ζがポアソン
方程式に外ならない。従つて前の差分アルゴリズ
ムの後半のΨ計算の内部反復の部分だけを取り出
してみればよい。そうすると、AU群で計算する
場合には、５回反復で2822ｍｓ、MUだけで５回
反復するときは39095ｍｓである。従つて（並列
処理時間）／（単一処理時間）＝１／13.85で、能
率比は0.99（＝13.85／14）となる。 計算例 ７ （計算例６と同じポアソン方程式を単純反復法
で解く場合） 取り扱うアルゴリズムは Ψ^ｎ＋１ _ｉ、_ｊ＝Ψ^ｒ _ｉ、_ｊ＋τ〓／ｈ^２（Ψ^ｒ _ｉ＋１、_ｊ＋Ψ^ｒ _ｉ−１、_ｊ＋Ψ^ｒ _ｉ、_ｊ＋１＋Ψ^ｒ _ｉ、_ｊ−１−
４Ψ^ｒ _ｉ、_ｊ）＋τ〓ζ_i、_j （ｒ＝０、１、２、………） である。これをAU群で実現するためには次の(i)
(ii)の手順を必要回数だけ繰り返えせばよい。 (i) AU−ｊがすべてのFIFO−（ｉ、ｊ）（ｉ＝
１、２、………、Ｊ−１）からそれぞれ値Ψ
^ｒ _ｉ、_ｊ＋１＋Ψ^ｒ _ｉ、_ｊ＋１を受けとる。上式の右辺
を計算
し、その結果を｛Ψ^ｒ＋１ _ｉ、_ｊ｝として各FIFO−
（ｉ、ｊ）（ｉ＝１、２、………、Ｊ−１）に送
る。 (ii) 次にAU−ｊはすべてのFIFO−（ｊ、ｋ）
（ｋ＝１、２、…………、Ｊ−１）から値Ψ
^ｒ＋１ _ｊ、_ｋを受け、和Ψ_ｒ＋１ｊ、_ｋ＋１＋Ψ^ｒ＋１
_ｊ、_ｋ−１を求めて、そ
れを各FIFO−（ｊ、ｋ）（ｋ＝１、２、……
…、Ｊ−１）に送る。 ５回反復に要する計算時間は992ｍｓである。
一方MUだけで単純反復計算を行うときの計算時
間は５回反復で13469ｍｓとなる。従つて（並列
処理時間）／（単一処理時間）＝１／13.58であ
り、能率比は0.97（＝13.58／14）となる。 参考のために、一般的にＱ台のAUでＲ回反復
した場合の計算時間を評価すると14.1QRｍｓで
あり、MUだけでやる場合の計算時間13.7Q²Rｍ
ｓに比して１／0.97Qとなり、能率比は一般的に
も0.97であることがわかる。 計算例 ８ （計算例６と同じポアソン方程式をガウスザイ
デル法で解く場合） 取り扱うアルゴリズムは Ψ^ｒ＋１ _ｉ、_ｊ＝１／４（Ψ^ｒ＋１ _ｉ−１、_ｊ＋Ψ_ｒｉ＋１、_ｊ＋Ψ^ｒ＋１ _ｉ、_ｊ−１＋Ψ^ｒ _ｉ、_ｊ＋１）＋h₂ζ、
_j （ｒ＝０、１、２、………） である。これをAU群に実現させる場合、各ｊに
対する未知数の組｛Ψ^ｒ＋１ _ｉ、_ｊ｝（ｉ＝１、２、３
、
………、Ｊ−１）の計算をAU−ｊに担当させる
ものとする。そのとき、例えばAU−２がΨ^ｒ＋１ _１、_２
を求めるたには、既にΨ^ｒ＋１ _２、_１が計算済みでなけ
れ
ばならない。だから、AU−１がΨ^ｒ＋１ _２、_１を決めれ
ば、それを先にFIFO−（２、１）を通してAU−
２に送つて後、AU−１はΨ^ｒ＋１ _３、_１の計算にうつる
が、そのとき同時にAU−２はΨ^ｒ＋１ _２、_２の計算にう
つるという具合に行つていけば、Ψ^ｒ＋１ _ｉ、_ｊの値は
ｉ
＋ｊの低い番号から高い番号の方へ波状的に決ま
つていくことになる。AU−ｊの動作でみれば、
Ψ^ｒ＋１ _ｉ、_ｊの値を決めるために、FIFO−（ｊ、ｊ＋
１）を介してΨ^ｒ _ｉ、_ｊ＋１の値を得、次にFIFO−
（ｊ、ｊ−１）を介してΨ^ｒ＋１ _ｉ、_ｊ−１を得て、上
式の右
辺を計算した後その値をΨ^ｒ＋１ _ｉ、_ｊとしてFIFO−（
ｊ
−１、ｊ）とFIFO−（ｊ＋１、ｊ）に送ること
をｉ＝１、２、………、Ｊ−１の順に繰り返え
す。これが済めば、つづいて｛Ψ^ｒ＋２ _ｉ、_ｊ｝（ｉ＝
１、２、………、Ｊ−１）の計算に入ることにな
る。以上にみるように、この計算では、FIFOバ
ツフアメモリーをすべて利用する必要がなく、三
重対角線上に並ぶものだけを使つている。 上の計算をＱ台のAUでＲ回の反復を行うと計
算時間は8.6（Ｒ＋１）Ｑｍｓである。同じ計算
をMU上で行えば（7.8Q²＋0.05Q）Ｒｍｓであ
り、（並列処理時間）／（単一処理時間）＝１／
（0.907Q＋0.0058）（１＋１／Ｒ）^-1となり、ＱとＲが 少し大きめになれば、≒１／0.907Qとなり、能
率比は0.907になる。 ADI法に比べて能率比が落ちるのは、ガウス・
ザイデル法が本来シリアル的なアルゴリズムで完
全な並列処理ができないからである。 以上、とくに計算例５〜８にみる様に、偏微分
方程式の差分近似方程式を反復解法で解くとき、
本発明計算機は能率比0.9〜0.99という高い性能
をもつことが判明した。中でもADI法の場合、Ｑ
台AUを用いいれば、殆んど無駄なくＱ倍の性能
をもつ機械になつていることがわかつた。

【図面の簡単な説明】

第１図は本発明の並列処理計算機の基本的配列
状態の一例を示すブロツク線図、第１Ａ図は第１
図の基本的配列における従プロセツサ群が２次元
配列バツフアーを介して横列及び縦列の機能を有
する態様を示す機能線図、第２図は一つのFIFO
バツフアメモリーにおけるデータバスの接続様式
を示す結線図、第３図は本発明の実施例になる並
列処理計算機の大要図、第４図は第２図に示すバ
ス接続の詳細な実施例回路図、第５図は第４図に
おけるSI REQ、SO REQの信号を作り出すため
の論理回路の実施例を示す図、第６図は主プロセ
ツサと各従プロセツサ間の送受信号の交換を示す
論理回路図、第７図ないし第９図は各プロセツサ
におけるバイトの番地の割当て例を示す図、第１
０図は計算例５のナビエ・ストークス方程式の
ADI解法におけるデーターの割り振りとデーター
の送受様式を示す図である。 MU……主プロセツサ、AU……従プロセツ
サ、FIFO……FIFOシリアルメモリー。

Claims (1)

1. 【特許請求の範囲】 １ １台の主プロセツサと複数Ｎ台の従プロセツ
   サの１次元配列からなる階層的アーキテクチユア
   をとる並列処理計算機において、 主プロセツサMUと各従プロセツサAU間、お
   よび任意の２台の従プロセツサ同志間でのデータ
   転送のためのＮ行Ｎ列の２次元配列からなるバツ
   フアメモリーBM群を備え、 前記従プロセツサAUに番号ｉ＝０、１、２、
   ………、Ｎ−１をつけ、前記バツフアメモリー
   BMに２次元配列番号（ｉ、ｊ）、ｉ、ｊ＝０、
   １、………、Ｎ−１をつけるとき、番号（ｉ、
   ｊ）のメモリーには、番号ｉおよびｊの従プロセ
   ツサにつながる２種のデータバスが入力され、出
   力側も、その２種のバスにつながる接続様式をも
   つことを特徴とする並列処理計算機。