JPS6165336A

JPS6165336A - 高速演算方式

Info

Publication number: JPS6165336A
Application number: JP59186316A
Authority: JP
Inventors: Shinichiro Miyaoka; 宮岡　伸一郎; Akira Muramatsu; 晃村松; Seiju Funabashi; 舩橋　誠寿
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1984-09-07
Filing date: 1984-09-07
Publication date: 1986-04-03
Also published as: US4757466A

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】〔発明の利用分野〕本発明は実システムの数値シミュレーションに係り、特
に電子回路、論理回路、構造解析、潮流〔発明の背景〕数値計算を高速に実行する計算機として、スーパーコン
ピュータやアレイプロセッサがあるが、これらには以下
のような問題点がある。

（１）利用分野で述べたようなスパース、不規則な系の
計算では、ベクトル長が短かくなるため著しく効率が悪
化する。

（２）さらに並列度を高め高速化することが困難である
。

データフローマシンで実用化されたもの（溝目、外：画
像処理プロセッサＴＩＰ−１，信学技法ＥＣ８ｌ−５９
）もあるが、データ読み出し部が直列であるため高速化
に限界がある。

〔発明の目的〕

本発明の目的は、スーパーコンピュータ等のベクトル計
算に不適な、すなわち、不規則な構造のためアドレス計
算が複雑となる、あるいはスパースな構造のためベクト
ル長を長くとることが困難な問題に対し、問題に内′在
する並列計算可能性を最大限まで引き出して高速に計算
することを可能とする演算装置を提供することにある６
〔発明の概要〕数値計算における処理はデータフローグラフで表現でき
る。データフローグラフとは、演算命令をノード（節点
）で、データの流れをアーク（枝）で表現したグラフで
ある。たとえば線形方程式を解くための（ａ　）　Ｌ　
Ｕ分解、（ｂ）三角方程式の求解はそれぞれ第１図（ａ
）、（ｂ）のようなデータフローグラフで書かれる。あ
るノードに入力するアークのデータが全てそろえばその
ノードの演算は実行可能ということが分るため、スーパ
ーコンピュータなどで用いているベクトル化の方法に比
べ計算に内在する並列性を自然に表現できる方式といえ
る。

数値計算のデータフローグラフの特徴として以下の３点
が挙げられる。

（ｉ）　　ノードの種類は、加減乗除の四則演算だけで
ある。

（ｉｔ）　　グラフとして見たとき、ループが存在しな
い。

（ｔｉｔ）　　入力端（第１図、（ａ）のａ１１＋　ａ
３□、・・・など）の値が変更されることはない。

このことから、本発明では以下に述べるようなアークに
蓄積機能を持たない簡単なネットワーク型演算（ノード
間の接続関係をたどって行く型の演算）で、並列に計算
を実行することが可能となることを利用して計算の高速
化をはかる点に特徴がある。

（ｉ）　　入力データがそろっている、すなわち演算実
行可能なノードを判別する。

（ｉｔ）　　当該ノードの演算（四則演算のみ）を実行
する。

（ｉｉｉ　）　　当該ノードの出力先ノードを検索し、
当該ノードの演算結果を出力先ノードの入力データとし
て設定する。

一般には、入力データのそろっているノードは同時に多
数個存在し、これらは並列に実行可能である。

〔発明の実施例〕

以下、本発明の実施例を第２図により説明する。

本実施例では、演算装置全体を３重のループによって構
成している。第１　（または第２．第３）のループは、
ノードの入力データをそろえ演算ユニットに送るファイ
ンプロセッサ１　（２，３）、四則演算を行う演算ユニ
ット７　（８，９）、Ｆｉ　Ｆ　Ｏ（Ｆｊｒｇｔ　Ｉｎ
　Ｆｉｒｓｔ　０ｕｔ）の機能を持つデータバッファ１
．０　（１，１，１２）　、出力先のノードを検出する
ファンアウトプロセッサ１３（１４゜１５）、および交
換ネツ１〜ワーク１９から構成される。ファインプロセ
ッサ１〜３にはそれぞれ、命令メモリ４〜６が、ファン
アウトプロセッサ１３〜１５にはそれぞれ、接続構造メ
モリ１６〜１８が接続されている。

ところで、データフローグラフは２人力多出力ノードで
表現され（このようにグラフを構成することは一般的に
可能）、またループの多重度に等しい数のサブグラフに
分割されているものとする。

命令の種類や接続構造に関するデータは、サブグラフに
対応して分割されてメモリに格納される。

本実施例の場合、サブグラフの数は３であり、命令の種
類などは命令メモリ４〜６に分散して格納され、接続構
造に関するデータはメモリ１６〜１８に分散して格納さ
れている。

次に命令メモリ４〜６と、接続構造メモリ１６〜１８の
構成について詳細に述べる。命令メモリ４には、第３図
（、）に示すように、ノード番号ＡＩをアドレスとして
ＴＡ、Ｇ、ＯＰ、Ｄ、、Ｐの４つのデータを格納してい
る。ＴＡＧは、ノードの２つの入力のうち一方の値が確
定したときに１の値をとり、２人力とも確定していない
か演算が既に終了しているときにＯの値をとるものとす
る。

ｏｐは演算の種類（加減乗除）を示す演算コードである
。Ｄ２は、入力の一方の値が確定している場合にその値
を示している。Ｐは当該ノードの出力先のノード番号（
一般には多数個ある）が格納されている接続構造メモリ
１６の先頭アドレスを示すポインタである。接続構造メ
モリ１６には、ノードごとに、複数個ある出力先ノード
番号を連続して格納してあり、その先頭アドレスは命令
メモリ４に格納されているポインタＰで指示し、最終ア
ドレスであることは格納データがＥＮＤフラグであるこ
とにより判定する。

交換ネタ１〜ワーク１９は、その入力データ髪指定され
たアドレスに従って分配する機能を持ち、多段スイツチ
ネツ１〜ワーク、またはクロスバスイッチなどで構成す
るものとする。

第２図、第３図に従い、第１のループを例にとって動作
説明を行う。第３図（ａ）に示すように、ファインプロ
セッサ１は、交換ネットワーク１９からノード番号Ａ、
と入力データＤ、の組２０を受けとり、命令メモリ４の
アドレスＡ、からＴＡＧを読み出す。ＴＡＧがＯであれ
ばＤｌ　を命令メモリ４の当該アドレスにＤ２として書
き込み、ＴＡＧを１に変更する。ＴＡＧが１の場合は、
２つの入力データがそろっているのでＤ２　を読み出し
くＯＰ、Ｄ、、Ｄ、、Ｐ）の組２１を演算ユニット７に
送出し、ＴＡＧを０に戻す。

演算ユニット７は、Ｄｌ、Ｄ、に演算ＯＰを施し、その
演算結果りとポインタＰの組（ＰＪ　）をデータバッフ
ァ１０に送出する。

第３図（ｂ）に示すように、ファンアウトプロセッサ１
３は、データバッファ１０から先着順に（ＰＪ　、　Ｄ
）の組２３を取り出し、ｐ、、を接続構造メモリ１６の
アドレスとして出力先のノード番号ＡＪを読み出す。さ
らに、出力先のノード番号ＡＪ　と演算結果データＤ（
出力先ノードの入力データとなる）の組２４を交換ネッ
トワーク１９に入力する。出力先のノードは通常複数個
あるので、ファンアウトプロセッサ１３はアドレスを】
、っずつ増加させながらＥＮＤフラグに至るまで」二連
の処理を続ける。

交換ネットワーク１９はノード番号Ａｊ　をデコードし
て、（Ａｊ、Ｄ）の組をファインプロセッサ１〜３のい
ずれかに送る。すなわち、Ａ、に関する情報を格納した
メモリに接続されているファンインプロセッサに向けて
当該データを送るものとする。

以上の処理はループに沿ってパイプライン的に実行され
る。すなわち、ファンインプロセッサ、演算ユニット、
ファンアウトプロセッサ、交換ネットワークのそれぞれ
は、同時に異なったノードに対し処理を行っている。

以上、第１のループに着目して動作を説明してきたが、
第２．第３のループの動作も全く同様である。これらの
ループは、交換ネットワークを介してデータ交換を行い
ながら並列に計算を進める。

さらに並列度を高めたければ、ループ数を増やすことに
より構成上の具体的な変更を行うことなしに拡張を図る
ことが可能である。

第２図には記載していないが、演算ユニット７（８，９
）はホストコンピュータ（でイクロプロセッサレベルの
もので可）に接続され、メモリへのデータのロードと演
算結果の読み出しは、ホストコンピュータが行うものと
する。演算の終了は、ラアインプロセッサへの入力がな
くなった時点とする。

〔発明の効果〕

本発明によれば、問題に内在する並列性を最大限に引き
出すことができるので、スーパーコンピュータなどのベ
クトル計算機が不得意とするスパース、不規則な問題に
対しても高速に計算を行うことが可能である。たとえば
、最大性能８００ＭＦＬＯＰＳのスーパーコンピュータ
でも、スパースがつ不規則な行列のＬＵ全分解は、１０
〜３゜ＭＦＬＯＰＳと最大性能の数十分の−の性能しか
出すことができない。これに対し、本発明でループ数を
８とすれば４０　ＭＦＬＯＰＳ、１６とすれば８０８Ｆ
ＬＯＰＳとスーパーコンピュータをしのぐ性能を出すこ
とが可能である。ただし、演算ユニットには１゜ＭＦＬ
ＯＰＳの浮動小数点プロセッサを用い、マシンサイクル
は１００ｎ　ｓと仮定している。

さらに本発明の効果として、目的を限定しているのでハ
ードウェア量が少なくて済むこと、拡張性に富み並列度
をさらに向」二させることが容易であることが挙げられ
る。

【図面の簡単な説明】

第１図はデータフローグラフの一例を示す図、第２図は
演算装置の全体構成図、第３図はメモリ７〜９・・・演
算ユニット、１０〜１２・・・データバッファ、１３〜
１５・・・ファンアウトプロセッサ、１６〜１８・・・
接続構造メモリ、１９・・・交換ネット９ｉｎ− （し）を２目 ′　　　　　　　　　　７７７シイン７’Ｏｔ　　Ｑ命令メ［１１７アシ４シアロセラｒ　　　　　　　　　　　　　　　　　　　ユ
ニ、トメモリ７γン４ン４ン今メモ、ワｔｓ　　　　　　　　　ｒ２、ｔＱ竿３目（せ）

Claims

【特許請求の範囲】１、演算命令をノードで表現し、被演算データをアーク
で表現したデータフローグラフにもとづいて演算処理を
おこなう数値計算装置において、被演算データがそろい
演算の実行が可能となった演算命令を判別する第１のス
テップと、判別された演算命令を実行する第２のステッ
プと、実行された演算命令の出力先ノードに対応する演
算命令を探索し、第２のステップで得られた演算結果を
探索された演算命令の被演算データとして設定する第３
のステップとからなることを特徴とする高速演算方式。２、上記被演算データは複数のブロックに分割されてお
り、各ブロックにたいして上記第１〜３のステップを並
列に実行することを特徴とする第１項の高速演算方式。