JPS5927352A

JPS5927352A - デ−タフロ−計算機制御方式

Info

Publication number: JPS5927352A
Application number: JP13587182A
Authority: JP
Inventors: Shigeki Yamada; 茂樹山田
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1982-08-04
Filing date: 1982-08-04
Publication date: 1984-02-13

Abstract

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

Description

【発明の詳細な説明】発明の技術分野本発明は、タグ付トークン制御方式を用いたデータフロ
ー計算機において、効率的にタグ発生・消去の管理を行
う方式に関するものである。

技術の背景従来、７オン・ノイマン型と称されてきた計算機では、
ただ１個のプログラムカウンタによって指定されたアド
レスの命令をメモリから順次数シ出して実行するために
、基本的には一度に１個の命令しか実行できず、多数の
異なる命令を一度に並列実行させることが本質的に困難
であった。データフロー制御方式を用いた計算機（デー
タフロー計算機）は、７オン・ノイマン型計算機と異な
ってプログラムカウンタを持たず「演算対象であるオペ
ランド、即ちデータがすべて使用可能になったとき、そ
の命令が実行可能となる」というデータ駆動の規則にし
たがって命令実行が制御される。このデータ駆動の規則
によυ、データが揃って実行可能となった命令が複数個
あれば、これらを同時に並列実行できるので、７オン・
ノイマン型計算機に比較して高い処理能力を実現するこ
とができる。データフロー計算機における命令実行制御
の一例を以下に示す。

第１図は、Ｃ＝（，４＋１　）＊（ｆ−１、Ｄ＝（Ａ−
Ｅ）／Ｂのプログラムをコンパイラによって変換したデ
ータフローグラフで、各ノードはデータフロー計算機の
命令に対応し、ノード間を接続するアーク上をデータ（
これをトークンと呼ぶ）が移動する。

たとえは、第１図で初期値としてＡｍ８　、　Ｂ＝２　
　を仮定し、ノード町にＡｍ８のデータが入力されると
ノード町が起動され、演算結果８＋１＝９を出力アーク
上に出力する。一方ノードｎ、は、Ａｍ８とＢ＝２の２
個のデータが揃った時点で起動され、演算結果８−２＝
６を出力する。これによシ、ノード町の２個の入力デー
タ（９と６）と、ノードｎ４の２個の入力データ（６と
２）が揃ったので、両ノードが並列起動され、ノードｎ
、は９＊６＝５４を、ノードｎ、は６＋２＝３を出力し
演算を終了する。

第１図のブータフローブ２７については、実際には、命
令ノードの演算種類と、ノード間の接続関係をプログラ
ムとしてメモリ上に記憶させ、マシンがある命令の演算
結果（データ）を、指定された接続関係にしたがって次
の命令の存在するメモリへ転送することによシ実現さ九
る。

ここで第１図のプログラムが同時に異なる２個のプログ
ラム（ＰＩＱ）　　から呼び出されて並列実行されると
きには、第１図のデータフローグラフの同一アーク上に
２個のプログラムｐ＋Ｑに対応した２種類のトークンが
存在する。この上うな猿境下で演算を実行する方法とし
て、各々のトークンにＰｒＱのいずれから呼び出された
かを示す識別情報（環境タグ）を付加し、同じタグを持
つトークンとおしの間で演算を行う「タグ付トークン方
式」が提案されている。

従来技術と問題点従来のタグ付トークン方式をそのままデータフロー計算
機で実現させようとすると、以下のような問題が生じる
。

たとえば、プログラムＰ１がプログラムＰ、を呼出し、
プログラムＰ、がプログラムＰ１を呼出す場合、Ｐ、で
使用されるトークンの環境タグピット長はＰ１識別コー
ド長であシ、Ｐ、で使用されるトークンの環境タグビッ
ト長はＰ１識別コード長十Ｐ、識別コード長となる。す
なわち、プログラムのネストの深さに応じて実行時に環
境タグピット長が可変にな、ってしまい、ハードウェア
の制御が著しく複雑化するとともに、ネストが深い場合
には環境タグピット長が非常に大きくなシ、効率的なデ
ータフロー計算機を提供することが困難であった。

発明の目的本発明は、これらの欠点を除去するため、メモリ上に環
境タグを記憶するタグ管理テーブルを用意し、該タグ管
理テーブルの空きエリアのメモリアドレスポインタを新
環境タグとして用い、該空きエリアに旧環境タグを記憶
させることによシ、環境タグを固定ピットに抑えるとと
もに、環境タグの発生・消去を高速かつ容易に行うもの
で、以下本発明の実施例を図面を用いて詳細に説明する
。

発明の実施例第２図は本発明によるデータフロー計算機のシステム構
成図で、１１〜１□ＩｄＫ個のプロセシングエレメント
（ＰＲ）であシ、これは通常の７オン・ノイマン型計算
機のプロセッサ（メモリを含む）に相当する。各ＰＥは
命令演算の実行以外にオペランドの到着の待ち合わせや
実行可能な命令の検出などデータフロー制御に特有な機
能を有する。ＰＥ１゜〜１Ｋによって演算された結果の
オペランドは、ある規則（これをＰＥマツピング法と呼
ぶ）にしたがって転送先のＰＥが決められ、オペランド
ネットワーク２に送シ出される。オペランドネットワー
ク２は、オペランドに付加された転送先ＰＫ番号を見て
ルーチングを行い、所定のＰＨにオペラン、ドを送シこ
む。３．〜３．は入出力機器類を制御する大めの１０コ
ントローラでオペランドネットワーク２を介してＰＥ１
．〜１Ｋに接続されている。各１０コントローラには、
ＰＥと同じように固有の装置番号が付与されておシ、Ｐ
Ｅから１０コントローラを制御するときには、制御デー
タ（オペ２ンド）に宛先１０コントローラ番号を付加す
ることにょシ、オペランドネットワーク２内でルーチン
グされて新宮のＩＯコントローラに送られる。４は複数
の入出力機器であシ、各１０コントローラ＃１（３，）
”２（３＊）＋・・・・・・、＊ｍ（Ａｍ）にはそれぞ
れ”１　＊　”Ｍ　ｒ・聞・、ｒｍ台の入出力機器が接
続されている。５．〜５には各ＰＥ１．〜１Ｘを共通メ
モリコントローラ６および共通メモリ７に接続するだめ
のパスカップ２である。８は共通パスである。

第６図は、本発明の一実施例である共通メモリコントロ
ー２６と共通メモリ７の関連を説明する詳細図である。

ここで９は受信データレジスタで、各ＰＥよシ共通バス
８を介して送られてきた環境タグの更新および復旧要求
が、一旦この受信データレジスタ９に記憶される。受信
データレジスタ９は、第５図に示すように制御オーダフ
ィールド９、と環境タグフィールド９．よ多構成される
。１０は９Ｍアドレスレジスタで、受信データの送信側
装置を指定する送信装置番号フィールド１０１及び受信
側装置を指定する受信装置番号フィールド１０゜よ多構
成される。１１はシーケンス制御部で、受信データレジ
スタ９内の制御オーダをデコードし、演算・テスト回路
１２や各種レジスタ類に対して各種タイミング信号や制
御信号を発生する。１６は共通メモリ（ｃｈｒ　）７を
アクセスするためのアドレスを記憶する０Ｍアドレスレ
ジスタ、１４ｔｊ、演算の中間結果や各種制御情報を記
憶するデータレジスタ群、１５はオペランドパス、１６
はリサルトパスである。１７は共通パス８を介してＰＥ
にアンサデータを返すための送信データレジスタ、　１
８は送信アドレスレジスタで、受信アドレスレジスタ１
０と同様に送信装置番号フィールド１８１および受信装
置番号フィールド１８．よ多構成される。

まず、環境タグを新たに発生する方法を述べる。

ステップ１：環境タグ発生要求は、あるＰＥでタグ発生
のための特殊な命令（たとえはプロシージャコール命令
）を実行した場合に、共通メモリコントロー５６へ伝え
られる。たとえばＰＥ＃１（１□）でタグ発生要求命令
が実行されると、ＰＥ＊１（１ｔ）は第４図αの「アド
レス」、第４図すの「データ」からなる第４図のＰＥか
ら共通メモリコントローラ６への転送情報に示すように
新タグ発生に必要な情報（新タグ要求の制御オーダと現
在の環境タグピット）をパスカップラ＃１（５，）を経
由してメモリコントローラ６内の受信データレジスタ９
０制御オーダフィールド９゜と環境タグフィールド９．
に送シ、また送信装置番号と受信装置番号を受信アドレ
スレジスタ１０内の送信装置番号フィールド１０．と受
信装置番号フィールド１０．に送シこむ。第４図すの制
御オーダ１はタグ発生要求を意味する。

ステップ２ニジ−ケンス制御部１１は、受信データレジ
スタ９０制御オーダフイールド９．をデコードして新タ
グ発生要求（＝１）であることを知ると、環境タグピッ
トをキーとして、演算・テスト回路１２を用いてハツシ
ングを行う。すなわち、Ｘをキー、ハツシュ関数Ａ（ｚ
）を、たとえばＡ（ｚ）　＝が（モジュロ２５６）とし
、共通メモリ７上に用意したハツシュテーブル（タグ管
理テーブル）のエントリサイズを２５６とすると、第４
図すからｚ−２４とし”ｒ　Ｚ２＝　２４”　−５７６
となるが、モジュロ２５６の演算を行うのでこの値はＡ
（Ｚ）〜２４”＝５７６→５７６−２５６　ｘ　２　＝
　６４　（モジュロ２５６の演＄＃）となシ、この値が
最終的に演算・テスト回路１２よシ出力される。この陣
をノ・ツシュテープルのアドレスとして使用するために
、ＣＭアドレスレジスタ１３に一旦スドアスル。ハツシ
ュテーブルは、第５図に示すように共通メモリ７の０番
地から２５５番地までのエリアを占めており、各エント
リは空／塞表示フィールドおよび環境タグフィールドよ
多構成される。この例では、ハツシュテーブルの６４番
地を読み出す。

これを演算・テスト回路１２に入力し、空／塞表示フィ
ールドをテストすることによシ、６４番地に塞表示が誉
きこまれていることをシーケンス制御部１１が検出する
。これは、ハツシュ法における衝突現象であシ、６４番
地には、既に他の用途のために情報が記憶されているこ
とを示している。

ステップ６：衝突現象を回避して別の空きエリアを見つ
ける方法として、開番地法や連鎖法など種々の方法が公
知であるが、ここでは最も簡単な開番地法を述べる。す
なわちシーケンス制御部１１は、　ＣＭアドレスレジス
タ１３　（７）　内容（〜６４）を演算・テスト回路１
２で＋１して再びＣＭアドレスレジスタ１６に戻す。こ
れによって共通メモリ７の６５番地の内容を読み出す。

第５図に示すように、６５番地の内容の空／塞表示フィ
ールドは空を示しておシ、これを演算・テスト回路１２
で検出すると、シーケンス制御部１１はこのメモリアド
レス（６５番地）自体を新しい環境タグとして割シ当て
るために、ＣＭアドレスレジスタ１６の内容（−６５）
を演算・テスト回路１２経由（演算実行させず、単にス
ルーさせる）で送信データレジスタ１７にストアする。

さらに新タグ発生を要求したＰＥ＃１（１１）に新タグ
を送シ返すために、受信アドレスレジスタ１０　（７）
該各フィールド１０．　、１０．内の送信装置番号（＝
Ｊ）Ｅ＃１）　　と受信装置番号（−メモリコントロー
ラ番号）とを演算・テスト回路１２で互いに入れかえ、
送信アドレスレジスタ１８ニセツトする。その結果は、
送信アドレスレジスタ１８内の送信装置番号＝メモリコ
ントローラ番号、受信装置番号＝ＰＥ＃１　となる。

ステップ４：送信アドレスレジスタ１８と送信データレ
ジスタ１７の内容を共通バスに送シ出す前に以下の後処
理を行う。すなわち、シーケンス制御部１１は、演算・
テスト回路１２で、受信データレジスタ９の環境タグフ
ィールド９．（値２４）と空／塞衣示フイレルドに対応
するビット位置を１（＝塞状態）にしたフィールドとを
合成編集し、リザルトバス１６を経由して共通メモリ７
０６５′＆地（ＣＭアドレスレジスタ１３で指定されて
いる）にストアする。その結果のハツシュテーブルのマ
ツプを嬉６図に示す。

ステップ５：縦波に、送信アドレスレジスタ１８と送信
データレジスタ１７の内容を示す第７図αの「ア、ドレ
ス」、第７図すの「データ」を共通バス８を介してＰＥ
＃１へ返送することによシ、ＰＥ群１．〜１には６５と
いう値を持つ新環境タグをオペ２ンドデータに付加して
使用することができる。

以上示したように、新環境タグの割シ当て要求が発生す
るたびに、テーブルの空きエリアを探してそのアドレス
を新環境タグとして割）当てることによシ、多数の環境
タグビットが互いに重複しないように容易に制御するこ
とができる。

次に旧櫨境タグへの復旧（現環境タグから旧嬢境タグに
戻す）方法を説明する。

ステップ１：タグの復旧要求は、タグ発生要求と同様に
特殊な命令によシ発せられ、この命令を実行しているＰ
Ｒ（たとえばＰＡ’＃３（１ａ）　）よシバスカツプラ
５８．共通バス８を経由してＰＲから共通メモリコント
ローラ６への転送情報を示す第８図αの「アドレス」、
第８図すの「データ」に示す制御情報が受信アドレスレ
ジスタ１０と受信データレジスタ９に入れられる。シー
ケンス制御部１１は、第８図すの制御オーダ（〜２（タ
グ復旧要求））を見て、タグ復旧〜要求であることを検
出し、受信データレジスタ９の現環境タグフィールド９
．（値６５を持つ）を演算・　　」テスト回路１２に入
力し、スルーさせてＣＭアドレスレジスタ１５にストア
する。この値（現環境タグの値６５）は第６図に示すよ
うに旧環境タグを記憶している共通メモリエリアのアド
レスそのものであるから、旧環境タグを記憶するエリア
をわざわざサーチする必要はなく、現環境タグを用いて
、直接、高速に旧項境タグ（値２４）を読み出すことが
できる。これを演算・テスト回路１２に入れ、スルーで
通過させ、リザルトハス１６を介して送信データレジス
タ１７にストアする。シーケンス制御部は、さらに受信
アドレスレジスタ１ｏの送信装置番号（ＰＥＩＩ５）と
、受信装置番号（メそリコントローラ番号）とを演算・
テスト回路１２で互いに入れかえて、送信アドレスレジ
スタ１７ニセツトスル。

以上によシ、第９図αの「アドレス」、第９図すの「デ
ータ」に示すプロセシングエレメントとメモリコントロ
ーラとの間の転送情報が編集される。

ステップ２：送信アドレスレジスタ１８と送信データレ
ジスタ１７の内容を共通バスに送シ出す前に以下の後処
理を行う。すなわち、シーケンス制御部１１は、オール
ゼロデータを演算・テスト回路１２よシ出力させ、これ
をＣＭアドレスレジスタ１６で示される番地（６５番地
）に書きこむことにより第５図の状態に戻す。以後、６
５番地は空きエリ・アとみなされ、次のタグ要求が発生
したときに再び６５という値を割シ当てることができる
。

ステップ６：最後に、送信アドレスレジスタ１８と送信
データレジスタ１７の内容を共通バス８を介してＰＥ５
６（１，）へ返送し、２４という値の旧櫃境タグを通知
する。ＰＥ群１．〜１には、以後この旧壊境タグをオペ
ランドデータに付加して使用することができる。

つぎに、プログラムがネスト構造をなしている場合にも
、固定長のタグビットを利用して矛盾ない制御が可能で
あることを示す。

第１０図は、プロシージャＰ１がプロシージャＰ２をコ
ールし、プロシージャＰ２がプロシージャＰ６Ｐ６をコ
ールし、プロシージャＰ６がプロシージャＰ４をコール
する様子を示している。この例では、プロシージャコー
ル命令の実行に、よシ新グロシージャ用に新環境タグが
割シ尚てられ、プロシージャリターン命令の実行によ）
旧環境タグへの復帰が行われる。第１０図のプロシージ
ャＰ４と第１１図のプロシージャＰ４か並列実行されて
いる場合のハツシュテーブルの状態は、前述の動作原理
によれば、たとえば第１２図のようになる。すなわち、
第１０図のネスト構造に対しては２４→６５→１２９→
１の環境タグリストが組まれてお夛、ネストの深さに関
係なく一定長の環境タグビット（本実施例では、テーブ
ルサイズ２５６から求められる８ビツト）で実現できる
。

また、第１０図のプロシージャＰ４の環境タグ（＝１）
と、第１１図のプロシージャＰ４の環境タグ（−９７）
は、ハツシュテーブルの空きエリア探索にもとづき、互
いに異なる値が割シ当てられることが保証されている。

したがって両プロシージャがたとえ並列実行されても両
グロシージャで生成されるデータの環境タグが互いに異
なるため、ＰＥ（１，〜ＩＫ）内で両データが混在して
も正しく識別して処理することができる。

以上述べた本発明においては、本実施例に限定されるこ
となく、目的・用途に応じて公知の任意のハツシュ関数
を選択できるし、衝突処理に関しても公知の任意の技術
が適用できる。また本実施例では説明を簡単化するため
、ハツシュ関数Ａ（ｚ）の出力そのものをハツ７ユテー
ブルアドレストシたが、ハツシュテーブルが共通メモリ
上のどの場所にあっても実現できるようにするためには
、ハツシュテーブルのベースアドレスを、たとえはデー
タレジスタ群１２０１個に記憶させ、ハツシュ関数Ａ（
２）の出力と該ペースアドレス令加算することにより容
易に実現できる。

さらに新タグ発生法としては、空きエリアのメモリアド
レスをタグとして割シ当てる方法ならば何でもよく、た
とえば空きエリアをポインタ・リストでチェイン接続し
ておき、タグ発生要求に応じて空きエリアのアドレスを
新タグとして割シ当て、空きエリアに旧タグを格納し、
旧タグへの復帰要求に対しては、現在使用中のタグで示
されるアドレスのエリアから旧タグを取・シ出し、この
エリアを空きエリアのチェインに戻す方式にも適用可能
である。

発明の詳細な説明したように本発明はタグ管理テーブルの空きエリ
アのメモリアドレスを新タグピットとして用い、旧タグ
ピットを該空きエリアに記憶させることによシ、プロシ
ージャ呼出しのネストが深くなってもタグビットを常に
一定長で実現でき、タグの発生・消去などの制御を高速
、容易かつ経済的に実現することができる。

【図面の簡単な説明】

第１図はデータフローグラフの例、第２図は本発明を用
いたデータフロー計算機のシステム構成図、第５図は本
発明のメモリコントローラおよび共通メモリの一実施例
の詳細図、第＋団α、ｂ、第７図α、ｂ〜第９図α、ｂ
はプロセシングエレメントとメモリコントローラとの間
の転送情報、第５図及びＭ６図はタグ管理テーブルのマ
ツプ、第１０図及び１１図はプロシージャコール・リタ
ーンと壌境タグの移り変わ９を示す遷移図、第１２図は
第１０図および第１１図に対応するタグ管理テーブルの
マツプである。１、〜１に・・・プロセシング・エレメント、２・・・
オペランドネットワーク、６□〜６ｒｎ・・・１０コン
トロー２．４・・・入出力機器、５．〜５Ｋ・・・パス
カップラ、６・・・共通メモリコントローラ、７・・・
共通メモリ、８・・・共通パス、９・・・受信データレ
ジスタ、１０・・・受信アドレスレジスタ、１１・・・
シーケンス制６１１部、１２・・・演算・テスト回路、
１６・・・ＣＭアドレスレジスタ、１４・・・データレ
ジスタ群、１５・・・オペランドパス、１６・・・リザ
ルトバス、１７・・・送信データレジスタ、１８・・・
送信アドレスレジスタ。特許出願人　日本電信電話公社代理人　弁理士玉蟲久五部（外３名）第１図第　２　図第３図第４因　　　ｂ α ３１！５　　日第　６　馨ａ　　　第７図　　　　ｂ第　８　図第　９　図第１１図第１２図

Claims

【特許請求の範囲】

タグ付トークン制御方式を用いたデータフロー計算機に
おいて、メモリ上にタグを記憶するタグ管理テーブルを
用意し、新タグ発生要求が生じた場合に、該タグ管理テ
ーブルの空きエリアを検出し、該空きエリアのメモリア
ドレスと１対１に対在使用しているタグに１対１に対応
するメモリアドレスを用いて該タグ管理テーブルエリア
をアクセスし、旧タグを取り出す手段とによシ、固定長
のタグによるタグ付トークン制御を行うことを特徴とす
るデータフロー計算機の制御方式。