JPS5933556A - デ−タフロ−処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （技術分野） 本発明は、プログラム実行に際して発生する関数呼出し
や繰返しの制御を効率よく行うデータフロー処理方式に
関するものである。

（背景技術） 従来のデータフロー処理方式においては、関数（手続き
）の呼出しやループの繰返し制御において、関数呼出し
要求や繰返しの継続要求が発生する度に、関数やループ
本体をコピーする際のオーバヘッドが生ずるのを避ける
ために、関数識別子と繰返し識別子を併用して全てのデ
ータに伺与する方法や、繰返しを再帰関数呼出しの形式
のプログラムに変換して関数識別子のみを全てのデータ
に付与する方法が提案されていた。

前者の方法においては、第１図に示すように、データ１
４を運ぶトークン（パケット）１内に関数識別子フィー
ルド１１と繰返し識別子フィールド１２０両者をもうけ
る必要があり、複数の処理要素間を結合網で接続した構
成のデータフロー処理装置においては、処理要素内の転
送バスの幅が大きくなり、構造が複雑になると共に、結
合網内でのト−クンの転送コストが高くなるという欠点
があった。なお、同図の宛先フィールド１３はトークン
が送られるノード（命令）のアドレスを示す。

一方、後者の方法においては、第１図に示した繰返し識
別子フィールド１２は不要になるが、プログラマ又はコ
ンパイラが繰返しの形式を角部呼出しく　ｔａｉｌ　ｒ
ｅｃｕｒｓｉｖｅ　ｃａｌｌ　）の形に変換する必要が
あリ、プログラマにとって大きな負Ｊ［、、ｌとなるが
、又は、コンパイラ作成が困難になるという欠点があっ
た。

（発明の課題） 本発明の目的はこ、１１．らの欠点を解決するために、
関数呼出し制御の１こめの識別子と繰返し制御のための
識別子を統合化し、１つの識別子フィールドを用いて両
者の制御機能を実現したもので、以下詳細に説明する。

（発明の構成および作用） 第２図は、本発明の第１の実施例におけるトークン１０
０の構成を示しており、統合識別子フィールド１５を用
いることにより、関数呼出し制御及びループの繰返し制
御の両者の１・幾能を実現したもので羽、す、以下その
１ｈ制御制御釦ついて説明する。

統合識別子フィールド１５の説明の前に、チータフロー
処理における関数呼出し及びループの繰返し制御につい
て述べる。

第：３図は、Ｘ２−１−　ｙ２の値を求める関数ｆ（ｘ
、ｙ）をデータフローグラフによって示したものである
。

同図においてノードは演算を示し、有向アークはノード
間のデータの受渡しの関係を示している。

各ノードは、その全ての入力アークにデータを運ぶトー
クンが現れると演算の実行力ＺｐＪ能となり、演算が終
了するとその出方アークに結果トークンを出し、次のノ
ードに渡す。第３図眞おいて、関数ｆの入力引数Ｘ及び
ｙが揃えば、ｆ内の２つの乗算は同時に実行できる。

今、この関数ｆを用いて（（ａ−１））２＋（ｃ−（１
）２）／（（ａ＋ｂ）２＋（ｃ＋ｄ）２）を求める関数
ｇ’（ａ　、　１１．　Ｃ。

ｄ）を示すと、第４図のようなデータフローグラフとな
る。同図において、ノード２１及び２２は関数ｆを呼出
す命令を意味する。関数ｇにおいて加減算ａ−１−ｂ、
ａ−ｂ、ｃ＋ｄ、ｃ−ｄは同時に実行ｉＨＪ’能である
が、これらの演算が終了すると、関数ｆへの２つの呼出
しノード２１及び２２も並列に実行できる。

このとき関数ｆへ渡される引数には、ノード２１がらの
引数（ａ−１）及びｃ−ｄの値）とノード２２がもの引
数（ａ−１−ｂ及びｃ＋ｃＪＯ値）を区別するために、
それぞれの呼出し毎に異なる関数識別子１１をトークン
に（＝ＪＪうする方法が考えら」している。即ち、ノー
ド２１かもの全引数υＣは例えば関数識別子／＋ａｌを
Ｊジえ、ノード２２からの全引数には関数識別子、／＋
ｄ２を匈え、関数ｆ内の）−ドの実行ｏＪ能判定にこの
関数識別子を用いる。

上記の例は関数の画人呼出しく　ｒｅｅｎｔｒａｎｔ　
ｃａｌｌ　）の例であるが、関数の角部呼出しく　ｒｅ
ｃｔ＋ｒｓｉｖｅ　ｃａｌｌ　）の場合も、各関数呼出
しの実行毎に異なる関数識別子を割当ててトークンに付
馬する必要がある。

同様なことは、ループの繰返し実行の際にも必“〃とな
る。例えば、第：３図の関数ｆにおいて引数ｔ＋　＋　
１）が配列であり、その各要素ａＩ、１）Ｉ毎にａ、”
＋１）１′を求めたいとする。このようなとき、一般に
繰返し文が使用されるが、３％−ｉなるときａｉ２＋１
）１２とａｊ２−１−　Ｊ２０訓算は独立して実行でき
るので、ここでは各繰返しの実行毎に異なる繰返し識別
子１２を割当て、該識別子」２をトークンに伺力するこ
とによって繰返し文の並列実行が可能となる。

こＡしまで述べたように、関数識別子１１及び繰返し識
別子１２は、チータフロープログラムの並列実行の際の
実行環境（ｃｏｎｔｅｘｔ　）を規定する識別子である
と考えることができる。

従来の方式においては、第１図に示したように、関数識
別子１１及び繰返し識別子１２を独立なフィールドとし
てトークン内に収容してし・だが、本発明においては、
以下のような管理テーブルと命令セットをもうけること
によって、これらを１つの統合識別子■５として実現し
た。

システム内に、第５図に示すような識別子１５を管理す
るテーブル３をもうける。同図において、（ａ）は関数
ｆの呼出し前、（１））は関数ｆの呼出し後を示し、フ
リーリストヘッダ３１は未使用識別子リストの先頭を指
しており、このリストにつながＡじこいる識別子群は関
数呼出しやループ繰返し要求Ｖこよって使用することが
できる。

先ず、関数呼出し及び関数からの戻り制御について説明
する。例えば、関数ｇが関数ｆを呼出したと仮定したと
き、呼出し側の識別子１５の値をｉｄ　（ｇ）とし、呼
出された側の識別子１５の値を１（１（ハとしよう。関
数ｆを呼出す際のシーケンスとして、；Ｐ、　（３図に
示すように、先ず関数起動命令（ＣＡＬＬ　）４が実行
さ」１．る。この命令４は第５図（ａｌの管理テーブル
３を参照して、呼出さね、た関数ｆの識別子１（１（１
）をフリーリストヘッダ：（１で示される未使用識別イ
リストの先回識別子に割当てる。こσ）後、フリーリス
トヘッダ：３１の内容は、割当てらＪｌ、た識別子１ｄ
（７’）の次の識別子を指すように更新さＡしる（第５
図（Ｉｌｌ　）。さらにこのとき、関数ｆの終了時（１
０，〕Ｔ命令５笑行時に）再び識別子１５をｉ（ｌｆｇ
）の状態へ戻すために、１ｄ（ｆ）の識別子のエン）　
ＩＪへｉｒｌ（ｇ）の値を格納する。このｃＡ、ｒ、、
＋、命令４は、実際Ｖこは関数ｇの識別子ｉｄ（ｇｌの
環境で実行され、そのデータＦｆ１５１’ｌどして１ｄ
（ｆｌを有するようなトークン１００を生成する。この
トークン１００は、引数群を関数ｆへ渡す１．Ｉ　ＮＫ
命令群６へ渡される０、Ｌ　Ｉ　Ｎ　Ｋ命令６は、現識
別子ｉｔｌ（ｇ）の値をＣＡＬＬ命令４かも受取った値
ｉｃｌげ）へ更新する機能を有する。なお、１日ＣＴ命
令５の実行によって関数ｆを呼出した関数の位Ｍ（この
場合関数ｇであるが他の関数から関数ｆを呼出すことも
あり得る）へ正番地の内容をＬ　Ｉ　Ｎ　Ｋ命令を介し
て関数ｆ内のＪ（・Ｅｌｌｌ命令５に渡す必要がある。

なお、本実施例においては、Ｉｔ　Ｅ　Ｔ命令５の実行
時に管理テーブル３を現識別子１（１（ｆｌを用いて参
照することにより、自関数ｆを呼出した関数ｇの識別＝
ｆ口１（ｇ）に回復する手段を採用しているが、ＣＡＪ
ＪＬ命令４から直接、Ｊ？、　Ｅ　Ｔ命令５へもとの識
別子ｉｄ（ｇｌを渡す経路を作ることも可能である（第
６図の破線で示す）。

このとき、第５図の管理テーブル３の１（１（ｆ）のエ
ンドＩＪ　ＩＬｉｄ　（ｇ）の内容を書き込む操作、及
び、ＩｔＥ’ｌｌ’命令５で管理テーブル３を参照する
操作は不要となる。

次にループの繰返し制御について説明する。卯。

７図は、関数ｆ内にループ本体１１が存在し、１１σ）
実行を１回以上繰返す場合のデータフローグラフ例を示
す。同図にオ６いて、ＣＡＪＪｌ・命令４及びＬＩＭＫ
命令群６は、前述の場合と同様ループへ渡される引数群
の識別子をループ本体の直前の識別子ｉｄ（ハからルー
プへ入ったときの識別子１ｄ（ｈｏ）へ更新する。

繰返しの終了条件が満足さＪ＋Ｊ：ｃ、いとき、次の繰
返しを行うためにＥ　Ｎ　ｉ’　Ｅ　Ｉｔ、命令７が実
行さＪｌ、る。

この命令はＣＡ　Ｌ　Ｌ命令４と同様、１番目の繰返し
実行時における識別子１ｄ（ｈＨ）からｔ＋Ｘ番目の繰
返し実行時における識別子１（Ｊ（１＋４１１）へ変更
する制御を行う。但し、１番月の繰返しにおいて終了条
件が７Ｎ自足さｉｔたとき、結果はＥＸＩＴ命令８に渡
されるが、この命令は識別子をループ（／′Ｃ入る直前
の値巨１（ｆ）へ戻す必要がル〕る。従って、この場合
の１＝；Ｎｉ”ｌ引く、命令７ば、第８図［ａ’ｌ（ｉ
回目の繰返し時）及び（１＞ｌ　（しｌ−１回目σ）繰
返し時）に示すように、１（ｌ（ｈ、）から１（１（１
１７口）へ識別子が更■さ」Ｌる際に、９３浬チーグル
；３のｉｔＩ　（１＋３．１．１）のエンドりの内容が
ｉ（１（１）になるようにｉｔＩ（１＋、）のエントリ
の内容をコピー−「るように操作を行う。なお、第７図
におけるＳＷ命令ｔ＋Ｙ：９は終了条件の判定結果に応
じてトークンの切換え開開）を行う。即ち、終了条件が
満埴されなかったとき、トークンはＳＷ命令９の左下か
「フ出力され、そうでないときは右下から出力される。

この繰返し制御の場合も関数呼出し制御σつ場合と同様
、第７図の破線に示すような経路を介して繰返し終了時
に管理テーブル３を使用せずに制ｇ’４１することもで
きる。

（発明の効果） 以上説明したごとく、第１の実施例では関数識別子と繰
返し識別子を統合した識別子を用℃・ることにより、プ
ログラムの並列実行環境制御を統一的に行うことができ
、またデータを運ぶトーク、／の失効的なビット長が減
少することから、データバス幅及び識別子制御のための
・・−ドウエア量が少なくてよく、かつ、結合網を介し
ブこトークンσ）転送能力が向上するという利点がある
。

本発明は、トークンのビット長を実効的に減少できると
いう利点かあり、データフロー処理装置のハードウェア
が単純となり、また、その処理能力の向上が期待できる
ので、数値計算を始めとして知識情報処理における推論
機能のような並列度の高い複雑なアプリケーションに広
範に使用することができる。

【図面の簡単な説明】

第１図は従来のデータフロー処理方式における１・−ク
ンの形式、第２図は本発明の第１の実施例におけろトー
クンの形式、第３図はデータフローグラフ例、第４同は
関数呼出しを伴うデータフローグラフ例、第５図（ａ）
及び（１））はそれぞ」１．関数呼出しの前後における
識別子管理テーブルの内容、第６図は本発明の第１の実
施例における関数呼出し機構のデータフローグラフ、第
７図は本発明の第１の実施例におけるループ繰返し機構
を説明したチータフローグラフ、第８図（ａ）及び（Ｉ
〕）は繰返し制御を行う際の識別子管理テーブルの内容
を示す。 ４’＃　ＭＴ出出願願 人電気工業株式会社 特ｒｉ′ｌ出願代理人 弁理士　　　山　　本　　恵　　− 慕／図 番２図 界３図 （ａ） 菓ａ　図 （ｂ）

Claims (1)

【特許請求の範囲】
1. コンビーータ処理における関数呼出し制御及び繰返し制
   御の実現のためにデータを運ぶトークンの中に識別子を
   用いるデータフロー処理装置において、関数呼出し制御
   のための識別子と繰返し制御のための識別子を統合化し
   た単一の識別子フィールドが１・−クンの中にもうけら
   れることを特徴とするチータフロー処理方式。