JPH0644299B2 - デ−タフロ−プロセツサ - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、メモリ部、演算部をパイプライン状のバスで
結合し、データフロー方式により演算順序をコントロー
ルすることを特徴とするデータフロープロセッサに関す
るものである。

（従来の技術） 従来、データフロープロセッサとして日本電気株式会社
製のμPD7281がある。

μPD7281は第６図に示されるような構成を持つ。外部バ
スから装置に入力されるデータの単位となるトークン
は、データ値、入力後にリンクテーブル92を参照するた
めのリンクテーブルアドレス、そのトークンが処理され
るべき装置を示すモジュール番号を持ち、トークン入力
部91は、外部バスを通るトークンのモジュール番号がそ
の装置の番号と一致する場合にそのトークンを内部に入
力し、そうでない場合トークン出力部97を通じてそのま
ま外部バスから出力する。入力されたトークンは、その
持つリンクテーブルアドレスによりリンクテーブル92を
参照し、そこでファンクションテーブル93を参照するた
めのファンクションテーブルアドレスと次回にリンクテ
ーブル92を参照するためのリンクテーブルアドレスを得
た後にファンクションテーブル93へ送られる。

トークンはファンクションテーブル93においてそのファ
ンクションテーブルアドレスによる参照を行い、そこで
データメモリ94の管理情報の参照・更新を行うと同時に
プロセッシングユニット96での処理内容を示す処理コー
ドとデータメモリ94のアクセスアドレスを得、データメ
モリ94に送られ、そこで必要に応じて２項演算の相手方
のオペランドとの待合わせあるいは定数演算のための定
数の読み出しを行う。キューメモリ95はプロセッシング
ユニット96が前のトークンを処理中で次のトークンを入
力できない時にトークンを一時保持するためのメモリで
あり、プロセッシングユニット96がビジーでない場合に
は、トークンはキューメモリ95からプロセッシングユニ
ット96に送られ、その処理コードに応じて、算術演算、
論理演算、シフト、比較、ビット反転、プライオリティ
エンコーディング、分流、数値発生、コピー、内部レジ
スタを利用した演算などのうちの１つの処理を受ける。
なおトークンの持つ処理コードが出力を示すものである
場合には、トークンはキューメモリ95からトークン出力
部97へ送られ、入力トークンの形に変形された後に、外
部バスへ出力される。プロセッシングユニット96で処理
をうけたトークンは、リンクテーブル92に送られ、再び
そのリンクテーブルアドレスにより参照を行う。以下同
様にして出力命令が実行されるまで内部のリンクバスを
回り、そのデータ値に対して必要な処理を受ける。

（発明が解決しようとする問題点） 前述のデータフロープロセッサでベクトルデータの形を
した複数のデータをまとめて扱いこれに対して処理を行
う場合には、それらを２項演算の積み重ねに分解し、そ
の様な部分部分の２項演算の２つのデータを待ち合わせ
命令によってプロセッサ内で待ち合わせることにより処
理を進めて行かねばならず、この場合１つの２項演算を
行うためにトークンが内部リングを１周する必要がある
ために処理速度が遅くなるという問題点がある。

これを解決するためにプロセッシングユニットにレジス
タを持ち、まとめて処理されるべき複数データを次々に
プロセッシングユニットに流し込み、レジスタ内の内部
状態を利用して高速に処理することができるが、この場
合にはベクトルデータの連続演算が終了し結果を出力す
るべきことを知るためにこれらのまとまったデータの数
を演算のための命令として予めプログラムし通過するト
ークンを計数しなければならず、長さが可変のベクトル
データを入力して処理するということは出来ない。

例えば疎行列を扱う数値計算でみられるようなもとの行
列のうち非０要素のみを持つベクトルを処理する場合を
考える。このときベクトルデータの長さは可変であり、
これらのデータをメモリから連続して読出しそれらの総
和をとる処理を行うデータフロープロセッサに入力する
ときには、それらが連続データとして流れるために同一
の識別子を持たせることによりその処理プログラムを記
述するフローグラフにおける同一のアークに流さねばな
らない。その際その最後尾を識別するためにそのトーク
ンがベクトルデータの終端であることを示すデータを持
つトークンを最後につけるという形態で流す必要があ
る。しかしさらにこのように総和をとるプログラムモジ
ュールが同じデータフロープロセッサ上に複数ありそれ
らを独立に動作させようとするときには、１つしかない
レジスタを共有ししかも正しい動作を行わせるために、
同時には１つのプログラムモジュールしか累積加算処理
を行わないように同期動作をソフトウェアにより実現し
なければならない。

そのばあいのプログラムを記述するフローグラフの一例
を第７図に示す。第７図においては上で説明したように
同一の識別子を持って入力されて来るデータトークン列
の各々のデータについて、まず終端マークであるかどう
かを判定し、その後に累積加算動作を行い、終端マーク
検出時にレジスタの読み出し動作を行っている。さらに
上記のような複数のプログラムモジュールにおける累積
加算処理が互いに干渉することを防ぐために、同時には
高々１つのプログラムモジュールしか動作しなように制
御している。

このように長さは可変で最後に最後尾であることを識別
情報のあるベクトルデータを次々にこのデータフロープ
ロセッサに入力しそのベクトルデータ要素の総和を求め
るという問題に対しては、そのベクトルの最後尾を認識
することにより入力データを一度ずつプロセッシングユ
ニットを通すだけで処理することは出来ず、ソフトウェ
アでこれを実現しなければならず、さらに複数のプログ
ラムモジュールの同期もプログラムしなければならない
のでソフトウェアの負担が大きくなり、同期のオーバー
ヘッドにより処理速度が遅くなることは避けられない。

本発明は可変長のベクトルデータを持つトークン列が加
算動作のためにプロセッシングユニットに１度ずつ通る
だけで処理を完了することが出来、さらに複数のプログ
ラムモジュール間の干渉も発生しないような機構を導入
することによりデータフロープロセッサ内のトークン流
量を減らし、高速な処理を実現するデータフロープロセ
ッサを提供することを目的としている。

（問題点を解決するための手段） 本発明のデータフロープロセッサは、リングバス上に順
に接続された、トークンの行き先アドレスを貯えておく
リンクテーブル、命令コードを参照するためのアドレス
を生成するファンクションテーブルアドレス生成部、命
令コードを貯えておくファンクションテーブル、２項演
算に用いるデータを一時貯えるデータメモリ、トークン
を一時保持するキューメモリ、トークンに対するデータ
処理を行い前記リンクテーブルへその結果を出力するプ
ロセッシングユニットを持ち、さらにキューメモリから
トークンを外部バスへ送出するトークン出力部と外部バ
スからトークンを入力してリンクテーブルまたは前記ト
ークン出力部へ送出するトークン入力部と、を持つこと
により構成されることを特徴としている。

（作用） 本発明においては長さＮのベクトルデータの和を求める
場合、それらのベクトルデータを持つ長さＮの組トーク
ンを用いる。これらのトークンはトークンとして従来か
ら持っていたリンクテーブルアドレス、データ値などの
他に組識別子を持つ。これは例えばＮ個の組トークンの
先頭のトークンでは“１”、２個目からＮ−１個目まで
は“２”、最後尾では“０”というものである。これら
のトークンは同じリンクテーブルアドレスを持ち、リン
クテーブルでの参照によって同じファンクションテーブ
ルベースアドレスを得た後に連続してファンクションテ
ーブルアドレス生成部に入力されるが、ここでそれの持
つファンクションテーブルベースアドレスと上記組識別
子とを演算することによりファンクションテーブルのア
クセスアドレスを得る。これにより例えばこの場合には
先頭のトークンは「そのデータ値をプロセッシングユニ
ットのレジスタに設定し、トークンは消滅する」という
命令コードを、２個目からＮ−１個目までは「そのデー
タ値をプロセッシングユニットのレジスタに加算し、ト
ークンは消滅する」という命令コードを、Ｎ個目は「そ
のデータ値をプロセッシングユニットのレジスタに加算
し、その後レジスタの値を結果データトークンとする」
という命令コードを持つ。

このような方法により、処理すべきベクトルデータの長
さがあらかじめデータフロープロセッサ内のプログラム
により与えられてなくても、演算部にこれらＮ個のトー
クンを１回送るだけで入力される組トークンが異なる命
令を実行することにより目的の完結した処理を行うこと
が可能になる。

（実施例） 次に本発明について図面を参照して説明する。

第１図は本発明の一実施例におけるデータフロープロセ
ッサの構成を示す内部ブロック図であり、11はトークン
入力部、12はリンクテーブル、20はファンクションテー
ブルアドレス生成部、13はファンクションテーブル、14
はデータメモリ、15はキューメモリ、16はプロセッシン
グユニット、17はトークン出力部であり、リンクテーブ
ル12、ファンクションテーブルアドレス生成部20、ファ
ンクションテーブル13、データメモリ14、キューメモリ
15、プロセッシングユニット16は図に示すようにこの順
にパイプライン方式のバスでリング状に接続しており、
トークンはこの内部リングバス上でデータフロープロセ
ッサ内のパイプラインクロックに同期して転送される。

第２図は本発明の一実施例を用いたデータ処理装置の例
の全体構成図である。本装置においては複数のデータフ
ロープロセッサ１、２と、１つのメモリインタフェース
回路３が外部バス５で結ばれており、外部バス５はメモ
リインタフェース回路３を介してメモリ４と接続されて
いる。外部バス５上でトークンはハンドシェーク方式に
より非同期に転送される。

第３図はデータの単位であるトークンの形式を示す。

外部バス５上でのトークン60はモジュール番号61、組識
別子62、リンクテーブルアドレス63とデータ部64からな
る。

65はリンクテーブル12からファンクションテーブルアド
レス生成部20へ送られる、また66はファンクションテー
ブルアドレス生成部20からファンクションテーブル13へ
送られるトークンの形式を示す。

この実施例で用いられるトークンについては１つまたは
複数のトークンからなる組トークンで１つのまとまりと
して処理することが出来る。組トークンは常に連続して
処理装置内を流れ、また同一のモジュール番号61と同一
のリンクテーブルアドレス63、83、87を持つ。

組識別子62、82、86は組トークン内でのそのトークンの
識別に用いられ、そのトークンが単独で組トークンを構
成する場合には“０”を、また複数のトークンからなる
組トークン内で互いを区別する必要がある場合にはそれ
ぞれ異なる値を持つことができる。ただし組トークン内
の最後尾のトークンは組識別子として“０”を持つ。

トークン入力部11は前段のデータフロープロセッサまた
はメモリインタフェース回路からのトークン入力リクエ
スト信号42により入力されるトークンのうちそのモジュ
ール番号61が、その装置に与えられた番号に等しいもの
のみを内部へ取り込みリンクテーブル12へパイプライン
サイクルに同期して送り、その他のトークンは通過トー
クンとしてそのままトークン出力部17へ送る。ただしリ
ンクテーブル12あるいはトークン出力部17が以下に述べ
るように組トークンの処理中でビジー状態である場合に
はトークンを送出せず、更に前段のデータフロープロセ
ッサまたはメモリインタフェース回路にハンドシェーク
のアクノレジ信号43を返さないことにより入力を停止す
る。

リンクテーブル12はプロセッシングユニット16またはト
ークン入力部11からトークンを入力するが、両方から同
時にそのリクエストがあった場合には通常はトークン入
力部11からの入力を優先する。ただしプロセッシングユ
ニット16がコピー動作により連続トークン生成中はそれ
を優先し、またどちらからのものであっても入力された
トークンの組識別子が“０”でない場合には、そのトー
クンが複数のトークンからなる組トークンの最後尾以外
のトークンであり、さらに連続して組トークンの残りが
入力されてくることがわかるので、それらのトークンの
送出元でない方に対してビジー状態であることを知らせ
入力を停止することにより、それらの組トークン全体を
優先して連続して入力する。これにより組トークンの連
続性が保証される。

プロセッシングユニット16またはトークン入力部11から
リンクテーブル12に入力されたトークンは従来と同様に
そのリンクテーブルアドレス63を用いてその内部メモリ
を参照し、そこで得たファンクションテーブルベースア
ドレス81及び次回のリンクテーブル12参照のためのリン
クテーブルアドレス83を持ってファンクションテーブル
アドレス生成部20に送られる。このときのトークン形式
を第３図の65に示す。

ファンクションテーブルアドレス生成部20では後述のよ
うにファンクションテーブルアドレス85を生成し、第３
図の66の形式のトークンをファンクションテーブル13に
送る。

ファンクションテーブル13では入力されるトークン66の
ファンクションテーブルアドレス85によりその内部のテ
ーブルをアクセスし、データメモリ14の管理情報の参照
・更新を行なうと同時にプロセッシングユニット16での
処理内容を示す処理コード、及びデータメモリ14のアク
セスアドレスをトークンに付加する。

データメモリ14は上記アクセスアドレスによってアクセ
スされ、必要に応じて２項演算のデータの、またはメモ
リインターフェース回路に対する書込みトークン出力の
時のデータを持つトークンとアドレスを持つトークンの
待ち合わせのためのキューとして、あるいは定数演算の
ための定数などの格納のためのメモリとして用いられ
る。

キューメモリ15は、プロセッシングユニット16あるいは
トークン出力部17にトークンを入力する前にトークンを
一時保持するためのメモリであり、キューの先頭のトー
クンの処理コードに応じてトークンをプロセッシングユ
ニット16またはトークン出力部17に送出するという動作
を行う。

プロセッシングユニット16は従来と同様にトークンのデ
ータに対する算術演算、論理演算、シフト、比較、ビッ
ト反転、プライオリティエンコーディング、分流、数値
発生、コピー、内部レジスタの操作とそれを用いた演算
を行う機能、あるいは前記機能の一部を持ち、キューメ
モリ15から入力されたトークンの持つデータに対して同
じくそのトークンの持つ処理コードに従って演算処理を
行い、演算結果のデータを持つトークンをリンクテーブ
ル12へ送る。

キューメモリ15を構成するＦＩＦＯの先頭のトークンの
処理コード68が出力を示すものである場合、そのトーク
ンはトークン出力部17に送られる。ただしトークン出力
部17がビジー状態である場合にはそこへの出力を停止す
る。

トークン出力部17はキューメモリ15またはトークン入力
部11から入力されたトークンに対してトークンを外部バ
ス5a上のトークン形式60に変形し、外部バス5aを介して
後段のデータフロープロセッサまたはメモリインタフェ
ース回路に対して出力する。ただしキューメモリ15また
はトークン入力部11の両方から同時にそのリクエストが
あった場合には通常はトークン入力部11からの入力を優
先する。ただしどちらからのものであっても入力された
トークンの組識別子が“０”でない場合には、そのトー
クンが複数のトークンからなる組トークンの最後尾以外
のトークンであり、さらに連続して組トークンの残りが
入力されてくることがわかるので、それらのトークンの
送出元でない方に対してビジー状態であることを知らせ
入力を停止することにより、それらの組トークン全体を
優先して連続して入力する。これにより組トークンの連
続性が保証される。

メモリインタフェース回路３はデータフロープロセッサ
１、２からこれを行き先とするモジュール番号61を持つ
トークン60を入力された時にその中のリングテーブルア
ドレス63、データ64で指定される動作を行う。例えば読
出し要求トークンが与えられた時にデータ64に含まれる
値をアドレスとしてメモリ４から読出し動作を行い読み
だした値を持つトークンをリンクテーブルアドレス63で
指定されたデータフロープロセッサに送り出す、あるい
は書込みデータを持つトークンと書込みアドレスを持つ
トークンが組トークンとして与えられた時にそれらを用
いてメモリ４に対する書込み動作を行うなどである。さ
らにメモリインタフェース回路３は値Ｎと「読出し組ト
ークン生成命令」を持つトークンが与えられるとメモリ
４からＮ回の読出し動作を行い、それらの値を持ちさら
にそれぞれ必要な組識別子を持つ長さＮの組トークンを
生成してデータフロープロセッサに対して送出する。

次に第４図を用いてファンクションテーブルアドレス生
成部20の実施例の詳細について述べる。

ファンクションテーブルアドレス生成部20はレジスタ50
を持ち、リンクテーブル12から入力されたトークン形式
65を持つトークンをパイプラインクロックに同期してこ
のレジスタ50に保持する。レジスタ50に保持されたトー
クン65のファンクションテーブルベースアドレス81の値
と組識別子82の値とが加算器51に入力され、加算器51は
その和をトークン形式66を持つ出力トークンのファンク
ションテーブルアドレス85フィールドの値として出力す
る。出力トークン66のその他のフィールド86、87、88に
はレジスタ50上の対応するフィールド82、83、84の値が
そのまま用いられる。

これにより組トークンを構成する複数のトークンが同一
のリンクテーブルアドレスを持ってリンクテーブルに入
力されることにより同一のファンクションテーブルベー
スアドレスを持っていても、異なる組識別子を持つこと
によって異なるファンクションテーブルアドレスを持つ
ことが可能となる。それを用いてファンクションテーブ
ル13の異なったアドレスをアクセスすることにより、同
一のリンクテーブルアドレス63を持ち常に連続してデー
タフロープロセッサ内を流れる組トークンの中の各々の
トークンが異なった処理を受けることができる。

次にこのデータフロープロセッサを用いて長さＮのベク
トルデータの和を求める場合の方法と動作について説明
する。

あらかじめリンクテーブル12のアドレスａにファンクシ
ョンテーブルベースアドレスとしてｂを、ファンクショ
ンテーブル13のアドレス（ｂ＋１）に「そのデータ値を
プロセッシングユニットのレジスタに設定し、トークン
は消滅する」という命令コードを、アドレス（ｂ＋２）
に「そのデータ値をプロセッシングユニットのレジスタ
に加算し、トークンは消滅する」という命令コードを、
アドレスｂには「そのデータ値をプロセッシングユニッ
トのレジスタに加算し、その後レジスタの値を結果デー
タトークンとする」という命令コードを設定しておく。

また長さＮの組トークンをメモリインタフェース回路に
おいて用意し、データとしては和を取られるべきＮ個の
データのそれぞれを、リンクテーブルアドレスとして値
ａを持たせる。また組識別子としては先頭のトークンで
は“１”、２個目からＮ−１個目までは“２”、最後尾
では“０”を持たせる。

この組トークンを構成するトークンは連続してリンクテ
ーブル12に入力されそのリンクテーブルアドレスで示さ
れるアドレスａにアクセスすることにより、形式65でフ
ァンクションテーブルベースアドレス81としてｂを持つ
トークンがＮ個連続してファンクションテーブルアドレ
ス生成部20に送られる。ファンクションテーブルアドレ
ス生成部20において、先頭のトークンはファンクション
テーブルベースアドレスと組識別子“１”とを加えるこ
とにより（ｂ＋１）を、２個目からＮ−１個目までは同
様に（ｂ＋２）を、最後尾ではｂを、それぞれファンク
ションテーブルアドレス85として得る。

これらのトークンはそのまま連続してファンクションテ
ーブル13に送られ、それらの持つファンクションテーブ
ルアドレスによりテーブルをアクセスすることにより、
先頭のトークンは「そのデータ値をプロセッシングユニ
ットのレジスタに設定し、トークンは消滅する」という
命令コードを、２個目からＮ−１個目までは「そのデー
タ値をプロセッシングユニットのレジスタに加算し、ト
ークンは消滅する」という命令コードを、Ｎ個目は「そ
のデータ値をプロセッシングユニットのレジスタに加算
し、その後レジスタの値を結果データトークンとする」
という命令コードを持ち、その後プロセッシングユニッ
ト16においてそのコードに従ってレジスタを利用するこ
とにより和を求めることが出来る。

なお本実施例と異なり、長さＮの組トークンの最後尾の
組識別子として“０”をその他のトークンでは“１”を
用い、先頭からＮ−１個目までのトークンはレジスタへ
の加算を、最後尾のトークンは加算、結果出力とレジス
タクリアを同時に行うという命令を用いることも可能で
ある。さらに組識別子として“１”を持つＮ個のトーク
ンと“０”を持つ１つのトークンからなる長さＮ＋１の
組トークンを用い、前者はレジスタ加算を、後者は加算
を行わずに結果出力とレジスタクリアを行うという実現
もできる。

例として従来の装置の問題点の項で述べた累積加算処理
を本実施例を用いて行う場合のプログラムを記述すると
フローグラフの一例を第５図に示す。第５図においては
上で説明したように同一の識別子を持って入力されて来
るデータトークン列で終端はそのトークンの組識別子で
識別されるためそれを判定する命令は不要であり、かつ
各々のベクトルデータは組トークンに対する制御によっ
て必ず連続して流れるため、複数のプログラムモジュー
ル間で干渉を起こす可能性はなく、従って同期メカニズ
ムを組み込む必要もない。これによりプログラムの負担
が軽減され、また同期制御のためのプログラムオーバー
ヘットがないため処理の高速化が実現されている。

（発明の効果） 以上説明したように本発明によれば、連続データの中で
個々のトークンにより異なった処理を行わせることが可
能になり、特にレジスタを用いる場合のように従来連続
トークンに対する同一の処理の前後に前処理と後処理を
行わせていたような場合について、その連続データの数
があらかじめ分かっていなくても、演算部にこれらＮ個
のトークンを１回送るだけでそれらの前後処理をその中
間の処理と連続的に行うことができ、プログラムの負担
の軽減と処理の高速化を図ることができる。

【図面の簡単な説明】

第１図は本発明のデータフロープロセッサの構成図、第
２図はデータフロープロセッサを用いた処理装置の例を
示す全体構成図、第３図は本発明の説明に供するトーク
ンの形式を示す図、第４図はファンクションテーブルア
ドレス生成部20の実施例を示す詳細な構成図、第５図は
本発明における累積加算処理の実現法を示すフローグラ
フ図、第６図は従来の装置を説明するためのデータフロ
ープロセッサの構成図、第７図は従来装置における累積
加算処理の実現法を示すフローグラフ図である。 図において、 11……トークン入力部、12……リンクテーブル、13……
ファンクションテーブル、14……データメモリ、15……
キューメモリ、16……プロセッシングユニット、17……
トークン出力部、20……ファンクションテーブルアドレ
ス生成部。

Claims (1)

【特許請求の範囲】
1. 【請求項１】データの単位であるトークンを内部のリン
   グ状のバスに流すことにより処理を行うデータフロープ
   ロセッサであって、前記バス上に順に接続された、トー
   クンの行き先アドレスを貯えておくリンクテーブル、命
   令コードを参照するためのアドレスを生成するファンク
   ションテーブルアドレス生成部、命令コードを貯えてお
   くファンクションテーブル、２項演算に用いるデータを
   一時貯えるデータメモリ、トークンを一時保持するキュ
   ーメモリ、トークンに対するデータ処理を行い前記リン
   クテーブルへその結果を出力するプロセッシングユニッ
   トを持ち、さらにキューメモリからトークンを外部バス
   へ送出するトークン出力部と外部バスからトークンを入
   力してリンクテーブルまたは前記トークン出力部へ送出
   するトークン入力部と、を持つことにより構成され、本
   データフロープロセッサに対する入力として、連続して
   流れる複数のトークンからなりその中で互いを識別する
   組識別子を持つ組トークンが与えられたときに、ファン
   クションテーブルでトークンに対する処理の命令を参照
   するためのアドレスを、前記ファンクションテーブルア
   ドレス生成部において、組トークン内の各トークンが共
   通して持つファンクションテーブルベースアドレスと、
   各トークンで異なる前記組識別子との演算によって生成
   することを特徴とするデータフロープロセッサ。