JPH0424744B2 - - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は並列処理計算機に係り、特に流体力学
等の偏微分方程式の数値解を並列処理により求め
るのに好適なミンド（Mulitiple Instruction
Multiple Data）型並列処理計算機に関する。

〔従来の技術〕

従来、複数台の演算ユニツトによつて並列に処
理する計算機が発表されている。特に偏微分方程
式を解くために適した並列処理計算機がエイ・シ
ー・エム トランサクシヨンズ オン コンピユ
ータ システムズ １巻 ３号 1983年８月195
頁〜221頁（ACM Transactions on Computer，
Vo1.1，No.３，August 1983，p195−221）に提
案されている。この計算機は、演算ユニツトを一
次元格子に接続したMIMD型並列処理計算機で
あり、個々の演算ユニツトに自身のプログラムを
持たせているため、境界条件の処理等、演算ユニ
ツトで異なる処理にも対応できる特徴を持つてい
る。

一方、ミンド（MIMD）型並列処理計算機で
は、共通の処理のため各演算ユニツトに共通のプ
ログラムを持たせることが冗長であり、メモリ容
量が多くなるという欠点がある。この問題点の一
つの解決方法が、特開昭58−146952号公報に記載
されている。この計算機では、演算ユニツトを制
御する制御ユニツトに、各演算ユニツトのプログ
ラムを記憶し、演算ユニツトのプログラムの実行
に合わせて、プログラムの１部分だけを制御ユニ
ツトから演算ユニツトへ分配することにより、プ
ログラム記憶の冗長を少なくし、メモリ容量の削
減を意図している。また、ループ処理を分配する
単位とし、分配の回数および時間を少なくしてお
り、ループ内の演算が少なく、ループ内のくり返
し数が多い問題に有効である。

〔発明が解決しようとする問題点〕

上記、特開昭58−146952では、ループ内の演算
量が多く、演算ユニツトのプログラムメモリ容量
を越えるような場合について配慮されておらず、
また、くり返し数が少ないループが多数ある場
合、頻繁に分配を行なう必要が有り、分配に関す
る時間が増える問題がある。

流体数値解析では、ループの個数が多く、また
ループ内の演算量が多い。第２図に、流体数値解
析の例として、２次元粘性流解析の流れ図を示
す。

(1) 各格子点で流速ｕ，ｖの初期値u⁰，v⁰を設定
する。

(2) 終了判定 (3) 各格子点で時刻ｔ＋δtのｕ，ｖの中間値，
ｖを計算する。

(4) 各格子点で質量残差ｄを計算する。

(5) 各格子点の圧力ｐを反復求解する。

(6) 時刻ｔ＋δtのｕ，ｖの値u^v+1，v^v+1を補正計
算する。

(1)，(3)，(4)，(6)は２次元の各格子点について計
算するため２重のループ、また(5)については、反
復求解のループが加わり３重のループとなつてい
る。さらに、(2)〜(6)は時刻を更新するループに含
まれている。一方、格子状に接続した並列処理計
算機では、一般に空間の部分領域を１台の演算ユ
ニツトへ分担させることにより並列処理する方法
が行なわれる。計算時間の短縮は、演算ユニツト
の台数を増やし、１台の演算ユニツトの分担する
格子点を減らすことで実現される。すなわち、演
算ユニツトの台数の多い並列処理計算機では、(2)
〜(6)のループのくり返し数は小さくなる。以上の
理由により、上記特開昭58−146952の方法は、流
体数値解析の並列処理には適していない。

本発明の目的は、流体数値解析の上記例のよう
に、複数のループ処理を順次実行するアルゴリズ
ムを少ないメモリ容量で並列処理するのに適した
MIMD型並列処理計算機を提供することにある。

〔問題点を解決するための手段〕

本発明は、演算ユニツト内に自身のプログラム
を持つMIMD型並列処理計算機において、流体
数値解析を並列処理するとき、各演算ユニツト間
で共通の処理である基本計算部分の命令列（以
下、共通命令）と個別の処理である境界値設定等
の部分を記述する命令列（以下、個別命令）を分
離し、共通命令に関しては１命令毎に演算ユニツ
トに放送することにより、ループの個数、くり返
し回数、演算量にかかわらずメモリ容量を削減で
きるという点に着眼することにより生まれた。

演算ユニツト内の演算装置は、ノイマン型の制
御方法をとり命令が格納されているアドレスを示
す、プログラムカウンタを持つ。この場合、共通
命令と個別命令のメモリバンクを分離し、個別命
令に関しては、演算ユニツト内のメモリに記憶さ
せ、共通命令に関しては、命令キユーとしてフイ
フオ（FIFO：First In First Out Memory）を
用い、FIFOの出力を共通命令のアドレス空間へ
対応させることにより、共通命令に関しては、演
算ユニツトの実行状態に合わせて、命令を放送す
れば、共通命令のメモリ容量を少なくできる。

演算ユニツトの実行状態に合わせて、共通命令
を放送する方法として、制御ユニツトにその機能
を分担する場合、制御ユニツトでは、ループのく
り返し回数のカウント等の演算ユニツトの実行状
態を監視する必要があり、そのための時間がかか
る。発明者は、複数の演算ユニツトを主演算ユニ
ツト（Master Processing Unit；MP）と複数
の従演算ユニツト（Slave Processing Unit；
SP）に分け主演算ユニツトに共通命令を記憶さ
せるとともに、並列処理の一部分を分担させ、主
演算ユニツトの演算装置が共通命令を取り込む時
に、従演算ユニツトへ放送すれば、制御ユニツト
による演算ユニツトの実行状態の監視が不要とな
るという点に着目し本発明に至つた。

つまり、上記目的を達成するために、本発明で
は、命令をメモリから取り込む演算装置、共通メ
モリ用メモリバンク、個別命令用命令バンクを持
つ主演算ユニツトと、上記演算装置、FIFOから
なる命令キユー、個別命令用メモリバンクを持つ
複数の従演算ユニツトとから構成される並列処理
計算機において、主演算ユニツトの共通命令用メ
モリバンクに記憶される共通命令を主演算ユニツ
トの演算装置が取り込むときに、命令放送バスを
通じて、該共通命令を従演算ユニツトの命令キユ
ーに書き込み、従演算ユニツトの演算装置は、共
通命令のアドレス空間に対応させた上記FIFOの
命令キユーから共通命令を取り込むことによつ
て、主演算ユニツトに記憶された共通命令を他の
演算ユニツトで共用するようにしたものである。

〔作用〕

主演算ユニツトと従演算ユニツトはともに、並
列処理の一部分を分担し、主演算ユニツト内には
個別命令を記憶する。主演算ユニツトの演算装置
は、共通命令の実行の前に、プログラムカウンタ
の示すアドレスから共通命令を取り込み、この
時、取り込まれる命令を従演算ユニツトへ放送
し、命令キユーへ格納する。従演算ユニツトの演
算装置は、命令キユーから共通命令を取り込み、
実行するので、各演算ユニツトで共通の命令を記
憶する必要がない。

〔実施例〕

以下、本発明の一実施例を図面を用いて説明す
る。

第１図は本発明の並列処理計算機の構成図であ
り、複数の演算ユニツト毎を一次元に接続した例
を示す。第１図において、１は主演算ユニツト
（MP）、２は従演算ユニツト（SP）、３はデータ
転送ネツトワーク、１２は演算装置、１３はメモ
リバンク、１４はメモリバンク、１５はFIFOか
らなる命令キユーであり、主演算ユニツト１は演
算装置１２、メモリバンク１３、メモリバンク１
４で構成する。従演算ユニツト２は演算装置１
２、メモリバンク１４、命令キユー１５から構成
する。

主演算ユニツト１と従演算ユニツト２は単方向
の命令放送バス１０２で接続される。また、主演
算ユニツト１と従演算ユニツト２はデータ転送ネ
ツトワーク３にデータ信号１１３により接続され
る。

第３図はMXN台の演算ユニツトを二次元格子
に配置し、行毎と列毎にデータ転送ネツトワーク
３に接続した実施例を示す。主演算ユニツト１か
らは、MXN−１台の従演算ユニツト２へ命令放
送バス１０２が接続される。

演算ユニツトを二次元配置する実施例において
も、主演算ユニツト１と従演算ユニツト２の構成
は一次元配置と同様である。

第４図は演算ユニツト内の構成図である。主演
算ユニツト１と従演算ユニツト２はハードウエア
の多くを共通の設計で作ることができるので、ス
イツチの切換により、主演算ユニツト１から従演
算ユニツト２へ変更できる実施例を示す。

演算ユニツトは演算装置１２、メモリバンク１
３、メモリバンク１４、命令キユー１５、スイツ
チ回路１６から構成され、演算装置１２とメモリ
バンク１４はアドレスデータ信号１０１により接
続され、演算装置１２とスイツチ回路１６はアド
レスデータ信号１０４により、スイツチ回路１６
とメモリバンク１３はアドレスデータ信号１０５
により接続される。また、命令キユー１５とスイ
ツチ回路１６は、データ信号線１０３により接続
され、また、演算ユニツトの外にはスイツチ回路
１６より、命令放送バス１０２が出力され、命令
キユー１５には命令放送バス１０２が入力され
る。

スイツチ回路１６がアドレスデータ線１０５と
命令放送バス１０２を選択し、メモリバンク１３
を実装することにより、主演算ユニツトとして動
作し、スイツチ回路１６がデータ線１０３を選択
することにより従演算ユニツトとして動作する。

第５図に、主演算ユニツト１と従演算ユニツト
２のアドレスマツプを示し、メモリバンク１３に
アドレス０〜２¹⁶−１、メモリバンク１４にアド
レス２¹⁵〜２¹⁷−１を割り当てている。従演算ユ
ニツト２の命令キユー１５にはFIFOを用い、
FIFOの出力ポートを演算装置１２のアドレスの
０〜２¹⁶−１に割り当てている。演算装置１２に
は、命令列をメモリ上に記憶し、命令の実行時に
命令をメモリから取り込むノイマン型の演算装置
を用いる。一般に、ノイマン型の演算装置は、プ
ログラムカウンタを持ち、プログラムカウンタの
示すアドレスから、命令を取り込む。プログラム
カウンタの値は、命令列の実行の履歴により唯一
定まる。したがつて、従演算ユニツト２の命令キ
ユー１５にFIFOを用い、主演算ユニツト１の演
算装置１２が取り込んだ共通命令を順に命令キユ
ー１５に書き込み、従演算ユニツト２の演算装置
１２では、プログラムカウンタが共通命令のアド
レスを示し、命令キユー１５から命令を取り込む
ことにより、従演算ユニツト２は共通命令の実行
を主演算ユニツト１を追尾して実行することがで
きる。

第６図は、演算ユニツト内の回路図であり、６
１は遅延回路、１０２Ａはデータ信号、１０２Ｂ
は書き込み制御信号（命令放送バス１０２）；１
０３Ａはデータ信号、１０３Ｂは読み込み制御信
号（データ信号線１０３）；１０４Ａはデータ信
号、１０４Ｂはアドレス信号、１０４Ｃは読み込
み制御信号（アドレスデータ信号１０４）；１０
５Ａはデータ信号、１０５Ｂはアドレス信号、１
０５Ｃは読み込み制御信号（アドレス信号１０
５）である。スイツチ回路１６内には、主演算ユ
ニツト１か従演算ユニツト２を選択するスイツチ
かあり、接点Ｕと接点MPの接続により、主演算
ユニツト１が選択され、接点Ｕと接点SPの接続
により従演算ユニツト２が選択される。

以下、第６図を用い主演算ユニツト１の動作を
示す。メモリバンク１３には、演算ユニツト間で
共通となる命令を記憶し、メモリバンク１４には
個別の命令とデータを記憶させる。ただし、命令
とデータのメモリバンクを分離することも可能で
あり、その場合、データ用のメモリバンクを別に
設けメモリバンク１４には個別の命令だけを記憶
する。書き込み制御信号１０２Ｂは書き込み許可
信号と書き込み信号からなり、書き込み許可信号
は、全ての従演算ユニツト２の命令キユー１５が
満杯でなく、命令の書き込みが可能の時に全ての
従演算ユニツトで論理積をとることにより生成さ
れ、読み込み制御信号１０５Ｃ、読み込み制御信
号１０４Ｃをへて、演算装置１２へ読み込み許可
信号として入力される。演算装置１２は読み込み
許可信号が発行されている間、アドレス信号１０
４Ｂに共通の命令の格納されるアドレスを出力
し、読み込み制御信号１０４Ｃへ読み込み信号を
出力し、読み込み制御信号１０５Ｃをへて、メモ
リバンク１３へ読み込み信号として入力される。
メモリバンク１３からは、読み込み信号に同期し
て、データ信号１０５Ａに、共通の命令が出力さ
れ、データ信号１０４Ａをへて演算ユニツト１２
へ、データ信号１０２Ａをへて従演算ユニツト２
へ送られる。従演算ユニツトへは、命令の他に書
き込み制御信号１０２Ｂを通して、演算装置１２
が、読み込み制御信号１０４Ｃへ出力した読み込
み信号を遅延回路６１により遅延させ、書き込み
信号として出力する。したがつて、主演算ユニツ
ト１は従演算ユニツト２の命令キユー１５が満杯
でない間、共通の命令を取り込み、従演算ユニツ
ト２へ同一の命令を放送する。

次に、第６図を用い、従演算ユニツト２の動作
を示す。読み込み制御信号１０３Ｂは読み込み許
可信号と読み込み信号からなり、読み込み許可信
号は、命令キユー１５に命令が入つている間出力
され、読み込み制御信号１０４Ｃをへて、演算装
置１２へ読み込み許可信号として入力される。演
算装置１２は、読み込み許可信号が入力される間
主演算ユニツト１の演算装置１２と同様に、アド
レス信号１０４Ｂに、共通命令のアドレスを出力
し、読み込み制御信号１０４Ｃに読み込み信号を
出力する。読み込み信号は読み込み制御信号１０
３Ｂを経て、命令キユー１５へ出力され、命令キ
ュー１５から、主演算ユニツト１が放送した命令
が出力され、演算装置１２へ読み込まれる。すた
がつて、従演算ユニツト２は主演算ユニツト１の
共通命令の実行を追尾して共通命令を取り込み、
実行することができる。

第７図は、主演算ユニツト１と従演算ユニツト
２の共通命令の取り込みと実行のタイムチヤート
であり、演算装置１２として命令の先取り機構を
有するものを用いた実施例である。主演算ユニツ
ト１では主演算ユニツトと従演算ユニツト共通の
命令、命令、命令を順次取り込み、取り込
むと同時に命令放送バス１０２へ放送する。従演
算ユニツトでは、命令キューに命令が入つた後で
命令を取り込む。従つて、共通命令の取り込みと
実行の時刻は、従演算ユニツト２が主演算ユニツ
ト１に対して遅れている。しかし、この遅れてい
る時間は、命令の実行にともない累積することが
なく、遅れ時間は高々命令放送バス１０２の信号
の伝播時間と命令キュー１５のアクセス時間であ
り、従来の全ての命令を演算ユニツトに記憶する
MIMD型並列処理計算機と比べ、命令の取り込
みに要する時間に差はほとんどない。

第８図は、共通命令列と個別命令列を交互に実
行するときのプログラムを示す。主演算ユニツト
１のメモリバンク１３にはアドレス０から２¹⁶−
１が割り当てられ共通命令と分岐命令が記憶さ
れ、主演算ユニツト１と従演算ユニツト２のメモ
リバンク１４にはアドレス２¹⁰から２¹⁷−１が割
り当てられ個別命令と分岐命令が記憶される。こ
の例において、分岐命令は演算装置１２のプログ
ラムカウンタの値を、異なるメモリバンクを指し
示すように変える命令であり、分岐命令は、演
算装置１２のプログラムカウンタを個別命令を
指し示すように変え、分岐命令は、プログラム
カウンタを共通命令 ｎ＋１ を指し示すように変
える。従演算ユニツト２は、共通命令と分岐命令
を命令キュー１５から読み込むことにより、主
演算ユニツト１を追尾し共通命令を実行できる。

以下、共通命令と個別命令を分離する方法を述
べる。現在計算機プログラムとして、構造化プロ
グラムが主流となつている。構造化プログラム
は、３つの基本形（(a)処理の順序を示す連接、(b)
ある条件の成立する間は処理をくり返す反復、(c)
ある条件に従つて二つの処理の一方を選ぶ選択）
から構成される。構造化プログラムにおいては、
プログラムの論理構成が明確となるため、共通命
令と個別命令を分離することが容易となる。本実
施例の並列処理計算機で、流体数値解析を行なう
時、演算ユニツトは、解析する領域の部分領域を
受け持つ。部分領域を受け持つ格子点が複数の場
合、格子点毎の演算は同一のため、この部分は(b)
反復により記述される。各演算ユニツトが受け持
つ部分領域の格子点数を互いに等しくする制限す
れば、反復回数を演算ユニツトで等しくでき、こ
の部分を共通命令として取り扱う。境界値の設定
は、格子点が境界に含まれるかどうかによつて異
なるため、(C)選択によつて記述され、これは、演
算ユニツト毎に異なるため、個別命令として取り
扱う。

以下、並列計算例を説明する。計算例として、
第２図に示した２次元粘性流解析のうち、圧力を
反復求解する部分を並処列理する場合を示す。解
析する領域は、16×８の格子点を持つ長方形領域
を考え、周囲を境界とする。圧力の境界条件とし
て法線方向の微係数が０となるNeumann条件を
与え、また、反復法としてJacobi法を用いる。演
算ユニツトが４×４の16台が１次元に配列されて
いるものを用い、１台の演算ユニツトには４×２
の格子点が分担される。

１台の演算ユニツトでは、圧力Ｐのデータエリ
アとして配列P_i,j （ｉ＝０，１，２，３，４，
５；ｊ＝０，１，２，３）をとる。ｉ＝０，５ま
たはｉ＝０，３は演算ユニツトによつて境界値か
隣の演算ユニツトで計算された値が格納される。
第９図に処理の流れを示す。

(1) Ｋの更新 (2) 各格子点で次ステツプの圧力値P_i,j（^k+1）を
計算する。

(3) 隣に演算ユニツトが有れば、隣の演算ユニツ
トに接する格子点の圧力値を送出する。

(4) 隣に演算ユニツトが有れば、隣から送られた
圧力値を配列へ格納する。

(5) 境界に接していれば、境界の値を境界要素に
代入する。

(6) 演算ユニツト内の格子点について、収束した
かを判定し、さらに全ての演算ユニツトで収束
したかを判定する。

ここで、(1)，(2)については、共通命令として取
り扱う。(3)，(4)，(5)については演算ユニツトで処
理が異なるため個別命令として取り扱う。(6)につ
いても、収束したかどうかは、演算ユニツトによ
り異なるため個別命令として取り扱う。第２図の
他の部分に対しても、同様に共通命令と個別命令
が分離できる。すたがつて、本発明の並列処理計
算機では、プログラムを各演算ユニツトで共通の
命令と個別の命令に分離し、共通の命令を１台の
主演算ユニツト１に記憶し、命令の実行に合わせ
て従演算ユニツトへ送るので従演算ユニツト２に
は記憶させる必要なく、流体数値解析等を少ない
メモリ容量で並列処理できる。

なお、並列処理計算機では、解く問題の規模に
対応して、演算ユニツトの台数を増減できること
が必要である。そのために、第１図の実施例によ
れば、主演算ユニツト１は複数の従演算ユニツト
２の命令キユー１５へ共通命令を書き込むため、
命令放送バス１０２への出力レベルを、従演算ユ
ニツト２の台数の上限に合わせて大きくとつてお
く必要がある。命令キユー１５として、アクセス
時間の短かいFIFOを使えば、第１０図の構成は
可能となり、主演算ユニツト１の命令放送バス１
０２への出力レベルを小さくし、かつ演算ユニツ
トの台数を任意に変えることが可能となる。

第１０図においては１は主演算ユニツト、２は
従演算ユニツト、３はデータ転送ネツトワーク、
１２は演算装置、１３はメモリバンク、１４はメ
モリバンク、１５は命令キユー、１０２は命令放
送バス、１２０はデータ信号であり、命令キユー
１５をデータ信号１２０で連結している。主演算
ユニツト１の演算装置１２はメモリバンク１３か
ら共通命令を取り込む時、同時に命令放送バス１
０２へ共通命令を放送する。従演算ユニツト２の
演算装置１２が、命令キユー１５から命令を取り
込む時、同時に隣の命令キユー１５へ書き込む。
第１図の実施例との違いは、第１図の実施例では
共通命令を各従演算ユニツトへ同時刻に放送する
のに対し、第１０図の実施例では、主演算ユニツ
トから離れるのに従がい、従演算ユニツト２へ
は、命令キユー１５のアクセス時間分の遅れが累
積され命令が取り込まれる。しかし、命令キユー
１５にアクセス時間の短かいFIFOを用いれば、
主演算ユニツト１から離れることによる、従演算
ユニツト２の命令の取り込み時刻の遅れの累積は
無視できるため、第１図の実施例と同様の性能を
得、かつ主演算ユニツト１の命令放送バス１０２
への出力を小さくし、演算ユニツトの台数も任意
に変更できる。

〔発明の効果〕

本発明によれば、MIMD型並列処理計算機で
各演算ユニツト間で共通の命令を１台の演算ユニ
ツトに記憶し、他の演算ユニツトで共用できるの
で、総メモリ容量を小さくできる効果がある。

【図面の簡単な説明】

第１図は本発明の一次元配置した並列処理計算
機の構成図、第２図は２次元粘性流体数値解析の
流れ図、第３図は本発明の二次元配置した並列処
理計算機の構成図、第４図は第１図の演算ユニツ
トの構成図、第５図は第４図の演算ユニツト内の
メモリマツプ、第６図は第４図の演算ユニツトの
回路図、第７図は第４図の演算装置のタイミング
チヤート図、第８図は第４図の演算装置の命令の
実行順を示す図、第９図は第２図の２次元粘性流
解析の圧力を並列計算する流れ図、第１０図は本
発明の一実施例の並列処理計算機の構成図であ
る。 １……主演算ユニツト、２……従演算ユニツ
ト、３……データ転送ネツトワーク、１２……演
算装置、１３……メモリバンク、１４……メモリ
バンク、１５……命令キユー、１６……スイツチ
回路、１０１……アドレス・データ信号、１０２
……命令放送バス、１２０……データ信号。

Claims (1)

1. 【特許請求の範囲】 １ 命令をメモリから取り込む演算装置、共通命
   令用メモリバンク、個別命令用メモリバンクを持
   つ主演算ユニツトと、上記演算装置、FIFOから
   なる命令キユー、個別命令用メモリバンクを持つ
   複数の従演算ユニツトとから構成される並列処理
   計算機において、 主演算ユニツトの共通命令用メモリバンクに記
   憶された共通命令を主演算ユニツトの演算装置が
   取り込むときに、命令放送バスを通じて、該共通
   命令を従演算ユニツトの命令キユーに書き込み、
   従演算ユニツトの演算装置は、共通命令のアドレ
   ス空間に対応させた上記FIFOの命令キユーから
   共通命令を取り込むことによつて、主演算ユニツ
   トに記憶された共通命令を他の演算ユニツトで共
   用するようにしたことを特徴とする並列処理計算
   機。