JPH0227491A - データ処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （イ）産業上の利用分野 本発明は、データ駆動型のデータ処理装置に関し、更に
詳述すれば、配列データ等のデータ集合をより有効的に
処理することを可使としたデータ処理装置に関する。

（ロ）　従来の技術 一般にデータ駆動型データ処理装置は、データの流れを
宛先情報にて示し、命令をアーク同士が接続されたノー
ドにて示すデータフローグラフをプログラムとして実行
する所謂非ノイマン型コンピュータである。

このようなデータ駆動型データ処理装置では、処理対象
のデータと、宛先情報とを含むデータパケットが種々の
処理要素、具体的にはデータ処理回路間を転送される間
に、データフローグラフに従った宛先情叩の付は替え、
データの複製あるいは命令（四則演算等）の実行が行わ
れる。

宛先情報は、データに対して実行諮れるべき命令の記憶
番地に対応しており、宛先情報の付は替えにより種々の
命令を同一のデータに施すことが可能である。即ち、宛
先情報により指示きれる宛先がデータフローグラフの上
の命令ノードを意味し、宛先情報の付は替えがデータフ
ローグラフの接続を意味する。

各処理要素は、データが到着すると直ちにそのデータに
所定の処理を施すように構成されており、データが各処
理要素にどのようなタイミングで到着するかは予め定め
られているわけではない、従って、二項演算のように二
つのデータがベアとして揃うことにより初めて実行可能
になる演算処理では、二つのデータの到着を待合わせて
検出するパケット待ち合わせ機構が必要になる。

従来のデータ駆動型データ処理装置に於ては、パケット
を待ち合わせるには、対になるパケットの内で、先に入
力されたパケットを、パケットの識別子から生成したハ
ツシュアドレスで指示されるメモリへ格納して待たせて
いた。後から入力されたパケットは、同じアドレスを読
み出すことにより、バク゛ットを対にして出力できる。

しかしながら、この方式では、同じハツシュアドレスを
持ち識別子の異なる二つ以上のパケットが入力されたと
きくハツシュ衝突）に、パケットを格納できなくなる。

この困難を避けるため、例えば、データ駆動型計算機に
おいてパケットの連鎖を使った方法が、電子情報通信学
会電子計算機研究会報告ＥＣ８３−２０の４７頁から５
３頁の報告「科学技術計算用データ駆動計算機５１ｇｍ
５−１のアーキテキチャ、に示されている。この例では
、１種類のメモリのみを持ち、ハツシュ衝突時には、最
初に入力されたパケットはメモリのハツシュアドレスの
場所に格納し、２番目以降に入力されたパケットはメモ
リの使用されていないアドレスに格納して、バッジコア
ドレスの等しい一パケットの連鎖を作っ工いる。

また、外部にバッファを設けた例が、昭和６３年年３月
１８日に行なわれた、情報処理学会第３６口金国大会予
稿集１２５頁から１２６頁の報告ｒ外部ハッンユキュー
を用いたデータ駆動形実行制御方式のシミュレーショ〉
による評価、に示されている。

この例では、主メモリの他にバッファメモリを持ら、ハ
ツシュ衝突時には、あらかじめ定めておいたバケ７）・
の優先順位に従って、優先順位の低いバケｙ１・をバッ
ファメモリへ一時的に待避し、ハツシュ衝突が回避され
た時に、バッファメモリより再度パケットを入力してい
る。

（ハ）発明が解決しようとする課題 しかしながら、前者の例°においては、ハツシュ衝突時
に、後から入力されたパケットはハツシュアドレスと異
なるアドレスへ格納されるため、この格納されたアドレ
スをハツシュアドレスとして持つパケットと新たなハツ
シュ衝突をおこす可能性がある。さらに、メモリのアド
レスとハツシュアドレスが異なることがあるので、ハツ
シュアドレスを生成するのに使用した情報もあわせてメ
モリに格納しなければならず、メモリ容量の増大をまね
く。

また、後者の例では、優先順位の低いパケットが対とな
って出力された後でないと、優先順位の高いパケットの
対の相手のパケットが入力されない場合には、永久にパ
ケットの対が生成きれず、システムがデッドロックする
。したがって、あらかしめ人力パケットの依存関係を調
べて優先順位を定めなければならず、特にデータ駆動型
計算機の場合、コンパイラ等のソフトウェアに対して、
大きな負担となる。また、常にデッドロックを回避でき
る優先順位づけが可能とは限らない、さらに、本来優先
順位がなく、入力順に処理されるべさパケ・／トに優先
順位、すなわち処理の順序を持ち込むことにより、処理
の効率の低下をもたらす。

本発明は、前記二つの例の、いずれの問題点をも解決し
うるものである。

（ニ）　課題を解決するための手段 本発明のデータ駆動型データ処理装置は、前記問題点を
解決するために、ハツシュアドレスによってアクセスさ
れ、パケットの待ら合わせを行なう主メモリとは別に、
ハツシュ衝突時に後から入力されたパケットを格納する
ためのバッファメモリを備え、主メモリとバッファメモ
リはいずれも、他のパケットを指示するポインタとパケ
ットとを対にして格納して、メモリ上でパケットの連鎖
が作成できるようになしたものである。

（ホ）　作用 本発明のデータ処理装置によれば、ハツシュアドレスご
とに、先頭のパケットは主メモリに、２番口以降のパケ
ットはバッフ７メモリに格納する事により、対の相手が
入力されるのを待っているパケットの連鎖を作る。従っ
て、パケットが入力されると識別子からハツシュアドレ
スを生成し、このハツシュアドレスに対応するパケット
の連鎖を先頭から順に読み出して識別子を比較し、識別
子の等しいパケットがあれば連鎖よ吟取り除いて、入力
されたパケットと対にして出力し、識別子の等しいパケ
ットがない場合には、入力されたバク゛ットを通炉の最
後に追加して、対の相手が入力されるのを待つ事となる
。

（へ）　実施例 第１図に本発明のデータ駆動型データ処理装置を用いた
システム例としてデータフロー計算機シスデムの概要を
示す。

同図に示すシステムは、システム内部のデータの基本７
１１位であるデータパケット（本来のデータ値の他に制
御情報を組み合わせて構成されている）を転送するリン
グ状転送践であるリングネッ）・ワークＲＮに、それ自
身がリングネットワークＲＮの一部をなすと共にデータ
パケットの入出力を制御するネットワークインタフェー
スＮＩＦ。

ＮＩＦ％ＮＩＦＩ・・・ＮＩＦｎを介して、ホストイン
タフェ−スＨ１、データ記憶装置ｆｔＤＭ、データフロ
ー計算装置ＤＦｃＩ〜ＤＦＣｎが結合されており、ホス
トインタフェースＨＥには更にホスト計算１１８Ｃが接
続されている。

同システムのデータフロー計算装置ＤＦＣＩ〜ＤＦＣｎ
とネットワークインタフェースＮＩＦＩ〜ＮＩＦｎそれ
ぞれとを組合わせたものは、内部がリング状をなすデー
タ駆動型データ（ｌａＦＪ装置として動作し、データフ
ローグラフによって記述されたデータ駆動型（データフ
ロー型）のプログラムを実行する。

具体的には、まずホスト計算機ＩＣから、ホストインタ
フェース８１、ネットワークインタフェースＮＩＦ、リ
ングネットワークＲＮ、ネットワークインタフェースＮ
ｒＦｉ（１は１〜ｎ）を介してデータフロー計算装置Ｄ
ＦＣ１にプログラムがダウンロードされ、次に同じ経路
で、プログラムの実行を開始させるデータパケットであ
る開始パケットがデータフロー計算装置ＤＦＣｉに入力
されるとプログラムの実行が開始され、プログラムの実
行が終了すると、実行の終了を示すデータパケットであ
る終了パケットが、データフロー計算機ＤＦＣ１からネ
ットワークインタフェースＮｒＦｉ１リングネットワー
クＲＮ、ネットワークインタフェースＮＩＦ、ホストイ
ンタフェースＨ１を介してホスト計算機ＨＣに出力きれ
る。

第２図に本発明のデータ駆動型データ処理装置の概略構
成を示す、同図の装置においてＱはキューメモリ、ＰＭ
はプログラム記憶手段、ＮＩＦはネットワークインタフ
ェース、パケット待ち合わせ手段、ＥＸＥは命令実行手
段であり、各処理要素がリング状に結合きれている。な
お、ｌ−ｒと！、ｙ、５０はデータ線である。

第２図を用いて本データ処理装置の動作の概略を説明す
る。１（スト計算機ＨＣからロードされたプログラム（
データフ１−グラフ）は、プログラム記憶手段ＰＭに格
納ｔ　ｉｔろ、開始パケットが各要素、即ちネットワー
クインタフェースＮＩＦ、パウット侍ら合わせ手段ＦＣ
，命令実行手段ＥＸＥ１キューメモリＱを介してプログ
ラム記憶手段ｆ’Ｍに到若するとプログラムの実行が開
始される。プログラムの実行中にプログラム記憶手段Ｐ
Ｍに入力されるパケットの制御ｆ＃報はこのデータ７０
−グラフに従って付は替えられたり、あるいは同じデー
タフローグラフに従ってデータパケットの複製処理が行
なわれたりする。プログラム記憶手段ＰＭから出力され
たパケットはネットワークインタフェースＮＩＦにおい
て外部に出力されるかパケット待ち合わせ手段ＦＣに向
けて転送されるかの選択がなされる。

パケット待ち合わせ手段ＦＣでは主に、例えば二項演算
命令などの左オペランドと右オペランドとをデータ対と
して検出して、二つのオペランドを対にして出力する発
火制御処理を行う、左オペランドは出力ラインＣに、右
オペランドは出力ラインｆに出力される。

命令実行手段ＥＸＥでは、到着したパケットの制御情報
によって指定される命令を到着したパケットに対して施
して出力する。

一方ネットワークインタフェースＮＩＦにおいて外部か
らパケットが入力される時、出力しようとしても出力で
きない時、及びプログラム記憶手段ＰＭにおいてデータ
の複製処理が行なわれる時はビジー状態となる。これら
の場合には後続するデータパケットは停止してビジー状
態の解除を待たなければならない、キューメモリＱはこ
のような時にデータを一時格納して待たせるためのバッ
ファリング機能を有している。

各処理要素において上記のような処理が施されながらデ
ータパケットが肩面することによってブし１グラムが実
行きれる。また、データ処理装置内部に複数のデータパ
ケットが存在する時には、各々のデータパケットに対し
て、異なる処理要素において同時に異なる処理を施すパ
イプライン型の処理を行なうことができる。従って、本
データ処理装置は、リング状のパイプライン型データ処
理装置と言える。

第３図に、本発明のデータ処理装置が特徴とするパケッ
ト待ち合わせ手段ＨＣの構成を示している。

第３図に於いて、（１）は入力パケット保持レジスタ、
（２）はハツシュアドレス生成回路、（３）は主メモリ
、（４）はバッファメモリ、〈５）は識別子比較回路、
（６）はパケット対出力回路、（７）は前パケットアド
レスレジスタ、（８）は現パケットアドレスレジスタ、
（９）は次パケットアドレスレジスタ、（１０）はバッ
ファメモリ未使用アドレス管理後入れ先出しメモリ、（
１１）はパケットポインター時記憶レジスタ、（１２）
は主メモリデータ領域、（１３）は主メモリ識別子領域
、（１４）は主メモリポインタ領域、（１５）はバッフ
ァメモリデータ領域、（１６）はバッファメモリ識別子
領域、（１７）はバッファメモリポインタ領域、（１８
）は入力パケット識別子、（１９）は識別子％（２０）
はパケットデータ、（２１）はアドレス、（２２）はポ
インタである。

第４図は主メモリ（３）とバッファメモリ（４）・との
間のバケット連鎖の関係の一例を示したものであり、こ
の例では、ハツシュアドレス１のパケット（’）　連Ｍ
　’　＊　−ｒ　Ｊ　、ハツシュアドレスｌのバク°ッ
トの連鎖１ｂ」、ハツシュアドレスｊのパケットの連＠
　’　Ｃ−４−ｄ　−ｅ　＠　→６　、がある。

第３図の構成に従い、以下に本発明の装置の動作を説明
する。尚ポインタはパケットの格納されているアドレス
として実現されている。

■、バッファメモリ〈４）の未使用領域を管理する後入
れ先出しメモリ（１０）は、最初バッファメモリ（４）
のすべてのアドレスが格納されている（すべてのアドレ
スが未使用であることを意味する）。

入力パケット保持レジスタ（１）にパケットが入力され
ると、ハツシュアドレス生成回路（２）によりハツシュ
アドレスが生成され、現パケットアドレスレジスタ（８
〉に格納きれるとともに、このアドレスを用いて主メモ
リ（３）を読み出し、パケットポイント−時記憶レジス
タ（１１）に格納する。主メモリ（３）にパケットが格
納されていない場合は■へ、格納されている場合は■へ
進む。

■、入力パケット保持レジスタ（１）に格納されている
パケットを、ポインタが何も指示しないようにして、レ
ジスタ（８）に格納されているアドレスを使って主メモ
リ（３）に書き込み、処理を終了する。

■、レジスタ（１１）に格納されているポインタを次パ
ケットアドレスレジスタ〈９）に格納し、レジスタ〈１
１）に格納されているパケットの識別子と、レジスタ（
１）に格納されているパケットの識別子を識別子比較回
路（５）で比較する。同じならば■へ、異なれば■へ進
む。

■、レジスタ（１）に格納されているパケットと、レジ
スタ（１１）に格納されているパケットをパケット対出
力回路（６）で対にして出力する。レジスタ（９）に格
納されているアドレスが、何も指示していない時はＶへ
、次のパケットを指示している場合は■へ進む。

Ｖ、Ｉで読み出したパケットを主メモリ（３）から消去
し、処理を終了する。

■、レジスタ（９）に格納きれているアドレスを使って
バッファメモリ（４）を読み出して、レジスタ（１１）
に格納し、レジスタ（８）に格納されているアドレスを
使って、レジスタ（１１）の内容を主メモリ（３）に書
き込む、レジスタ（９）に格納されているアドレスをメ
モリ（１０）へ書き込み、処理を終了する。

■、レジスタ（９）に格納されているアドレスが、何も
指示していない時は■へ、次のパケットを指示している
時は■へ進む。

■、メモリ（ｌＯ）を読み出してバッファメモリ（４）
の未使用アドレスを得、レジスタ（９）へ書き込むとと
もに、このアドレスを使って、レジスタ（１）に格納さ
れているパケットをバッファメモリ（４）へ書き込む、
レジスタ（９）に格納されているアドレスをレジスタ（
８）に格納されているアドレスで指示される主メモリ（
３）またはバッファメモリ（４）（どちらであるかはア
ドレスで識別される）のポインタ領域へ書き込み、処理
を終了する。

■、レジスタ（９）に格納されているアドレスを使って
バッファメモリ（４）を読み出しレジスタ（１１）に格
納するとともに、現パケットアドレスレジスタ（８）の
内容を前パケットアドレスレジスタ（７）へ、レジスタ
（９）の内容をレジスタ（８）へ転送する。レジスタ（
１１）に格納されているポインタをレジスタ（９）へ格
納し、レジスタ（１１）に格納されているパケットの識
別子をレジスタ（１）に格納されているパケットの識別
子と比較回路（５）で比較する。同じ場合はＸへ進み、
異なる場合は■から繰り返す。

Ｘ、レジスタ（１）に格納されているパケットと、レジ
スタ（１１）に格納されているパケットを出力回路（６
）で対にして出力し、レジスタ〈８）に格納されている
アドレスをメモリ（１０）に書き込む。

レジスタ（９）に格納されているアドレスが、何も指示
していない時はＸＩへ、次のパケットを指示している場
合はｘｎへ進む。

Ｘｌ、　　レジスタ（７）に格納きれているアドレスで
指示される主メモリ（３）またはバッファメモリ（４）
のポインタ領域が、何も指示しないようにし、処理を終
了する。

ｎ、レジスタ（７）に格納されているアドレスで指示さ
れる主メモリ（３）またはバッファメモリ（４）のポイ
ンタ領域に、レジスタ（９）に格納されているアドレス
を格納し、処理を終了する。

（ト）　発明の効果 本発明のデータ処理装置によれば、パケット待ち合わせ
手段に於て、バッファメモリが満杯にならないかぎり、
システムがデッドロックすることなしに、パケットの待
ち合わせを行なうことができる。また、新たなハツシュ
衝突を起こすこともない、さらに、依存間係などの、入
力パケットに関する情報があらかじめ分かっている必要
もない、従って、構成上の負担を招く事なく、処理能力
の向上を図ったデータ処理装置を実現する事ができる。

【図面の簡単な説明】

第１１５０は本発明を採用し得るデータ処理装置の構成
図、第２図は本発明を用いたデータ駆動型計算機の構成
図、第３図は本発明のデータ処理装置のパケット待ち合
わせ手段の構成図、第４図が本発明装置に用いるメモリ
図である。 （１）・・・入力パケット保持レジスタ、（２）・・・
ハツシュアドレス生成回路、（３）・・・主メモリ、（
４）・・・バッファメモリ、（５）・・・識別子比較回
路、（６）・・・パケット対出力回路、（７〉・・・前
パケットアドレスレジスタ、（８）・・・現パケットア
ドレスレジスタ、（９）・・・次パケットアドレスレジ
スタ、（１０）・・・バッファメモリ未使用アドレス管
理後入れ先出しメモリ、（１１）・・・パケットポイン
ター時記憶レジスタ、（１２）・・・主メモリデータ領
域、（１３）・・・主メモリ識別子ｆｉ域、り１４）・
・・主メモリポインタ領域、（１５）・・・バッファメ
モリデータ領域、（１６）・・・バッフアメモノ識別子
領域、（１７）・・・バッファメモリポインタ領域。 第１図

Claims (2)

【特許請求の範囲】
1. （１）逐次的に入力される識別子をもったパケットの中
   から同じ識別子をもつ二つのパケットを対にして出力す
   るパケット待ち合わせ機構を備えたデータ駆動型のデー
   タ処理装置に於て、パケット待ち合わせ機構中で、パケ
   ットと他のパケットを指示するポインタを対にして格納
   するメモリを主メモリとバッファメモリとで構成し、上
   記ポインタを使ってハッシュアドレス毎に先頭のパケッ
   トを主メモリに、２番目以降のパケットをバッファメモ
   リに格納する事を特徴としたデータ処理装置。
2. （２）請求項１に記載のデータ処理装置に於て、上記パ
   ケット待ち合わせ機構にパケットが入力されたときに、 ハッシュアドレスに対応する入力パケットが上記メモリ
   の連鎖にある場合、該パケットと入力パケットとを対に
   して出力すると共に、出力したパケットを連鎖から削除
   し、 ハッシュアドレスに対応する入力パケットが上記メモリ
   の連鎖中にない場合、入力を連鎖の最後に追加して、同
   じ識別子をもつパケットが入力されるのを待ち合わせす
   る事を特徴としたデータ処理装置。