JPH01283640A - データ駆動型制御方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データ駆動型制御方法に関し、特に並列実行
が可能となった複数の手続きを処理する場合、１つの手
続きの処理が終了するまでの他の手続きの実行を待ち合
せることで、手続き処理の実行順序による結果の非決定
性を防止したデータ・フロー・プログラムの命令制御方
法に関するものである。

〔従来の技術〕

データ駆動型制御は、データフロー、すなわち被処理デ
ータの準備状況に応じて、処理シーケンスを制御するも
のであって、いわゆる非ノイマン型コンピュータの実現
として研究されてきた。データ駆動の原理に基いて実行
されるプログラムは、第２図で示すように、長方形ブロ
ックの中に演算基が記載されたノード（加算、減算９等
）に対して、オペランド（データ、データアドレス、等
）が入力され、演算結果としてそれらの出力が与えられ
る。これらのノードへの入力と出力は矢印付きの線で表
わして、これらの線をアークと呼び。

繰上のデータをトークンと呼ぶ、このようにデータ・フ
ロー・プログラムは演算実行に必要なデータや制御の流
れが２次元の図式で表現されるため、理解性が高く、し
かも、並列処理の記述性が高い（電子通信学会誌、昭和
５８年２月号、ＰＰ１９１〜ＰＰ１９３）、そこで、並
列処理単位をプロセッサ単位に割り付けることで演算速
度を上げることもできるし、プログラムの理解性向上だ
けを狙うならデータ・フロー・プログラムを従来の逐次
型プロセッサで実行してもかまわない。

ところで、逐次型プロセッサ上でデータ駆動制御を行う
方法においては１例えば、特開昭６１−１２３９３７号
公報に記載されているように、並列実行可能となった命
令を待ち合せるために１つの命令実行待ちキューが用意
されていた。すなわち、上記公報に記載されたデータ駆
動型制御方式では、並列に実行可能状態となった命令は
１つの命令実行待ちキューへＦＩＦＯ（ファーストイン
・ファーストアウト）形式で登録されているため、例え
ば、同時に手続きＡを呼出す手続き呼出しＡ′と手続き
Ｂを呼出す手続き呼出しＢ′が実行可能となる場合、命
令実行待ちキューには手続き呼出しＡ′の命令が先頭に
、手続き呼出しＢ′の命令が最後尾に登録される。従っ
て、命令実行はまず手続き呼出しＡ′の命令が命令実行
待ちキューから取り出されて、手続きＡが呼出され、そ
の結果新たに実行可能となった手続きＡ内の命令が命令
実行待ちキューの最後尾にある手続き呼出しＢ′の命令
の後に登録される。そして、次に、命令実行待ちキュー
から手続き呼出しＢ′の命令が取り出されて、手続きＢ
が呼出され、その結果新たに実行可能となった手続きＢ
内の命令が実行待ちキューの最後尾にある手続きＡ内の
命令の後に登録される。このため１手続きＡと手続きＢ
の命令が交互に実行されてしまう。

〔発明が解決しようとする１ｌｌｌＪＩ）前述のように
、従来の技術においては、命令実行待ちキュー１つで命
令を制御しているため、同時に複数の手続きが並列に実
行可能となる場合には、プログラム設計時に手続きの間
の実行順序や終了時刻に十分な注意を払う必要であり、
しかも。

プログラムトレース時には、複数の手続きが交互に実行
されてしまうため、トレース結果の解析に多大な工数壁
いやすという問題点がある。

本発明の目的は、これらの問題を解決し、１つの手続き
が終了するまでの他の並列に実行可能状態にある手続き
を待ち合せることが可能なデータ駆動型制御方法を提供
することにある。

〔課題を解決するための手段〕

上記目的を達成するため、本発明のデータ駆動制御方法
は、演算処理名と入力データ入手先と該入力データを用
いて演算結果の出力通知先と該入力データが準備された
ことを示す入力データ数カウンタから構成される命令と
、実行可能状態にある命令の実行を待ち合せるための命
令実行待ちキューとデータ駆動の原理に基づいて命令の
実行を制御するデータ駆動命令実行制御部とを格納した
記憶手段を有するデータ駆動型制御方法において、該記
憶手段に、実行中の手続きのネストレベルを指示するネ
ストレベルカウンタとネストレベルカウンタの値に対応
してそれぞれに命令実行待ちキューとを格納しておき、
該ネストレベルカウンタは手続き呼出し命令または呼出
し元へ戻るリターン命令が発生するたびに更新しつつ、
データ駆動命令実行制御部はネストレベルカウンタで指
示される命令実行待ちキューから実行可能状態にある命
令を取り出し、命令内の演算処理名で指示される演算を
行い、演算結果により新たに実行可能状態となった命令
をネストレベルカウンタで指示される命令実行待ちキュ
ーの最後尾に登録することにより、１つの手続きが終了
するまで他の並列実行可能状態にある手続きの実行を待
ち合せることを可能としたものである。

〔作用〕

本発明においては、複数の手続き呼出し命令が並列に実
行可能となった時に、データ駆動命令実行制御部は手続
きの実行レベルを表示するネストレベルカウンタで指示
される命令実行待ちキューに上記複数手続き呼出し命令
を登録し、次に、該命令実行待ちキューの先頭にある命
令を取り出し、該命令が手続き呼出し命令の場合１手続
き呼出し命令処理において、ネストレベルカウンタは＋
１され、新たに実行可能となった手続き内の命令は更新
されたネストレベルカウンタが指示される命令待ちキュ
ーに登録していく。

以後、手続き呼出し命令が実行されるたびにネストレベ
ルカウンタは＋１だけ更新されていく。

また、同様に、呼出し元へのリターン命令が実行される
たびに、ネストレベルカウンタは−１される。

従って、１つの手続き処理が始まるとネストレベルカウ
ンタが更新されるので、該手続きが終了を示すリターン
命令が実行されるまでは、同一ネストレベルで実行可能
状態にある他の手続きの命令実行は待ち合せることが可
能になる。

〔実施例〕

以下、本発明の実施例を図面により詳細に説明する。

第２図は１本発明において適用されるデータ・フロー・
グラフの記述例を示す図である。

前述のように、第２図における演算ノード１２はデータ
駆動で実行される演算命令を表わしており、ノード１２
の中に演算の内容を示す演算処理名が記述され、また、
アーク１３は命令間で授受されるデータの流路を表わし
ている。通常のデータ・フロー・グラフの主ルーチン１
０は演算ノード１２とアーク１３を組み合せて記述され
、主ルーチンから呼出される手続き１１も主ルーチンと
同様に演算ノード１２とアーク１３の組み合せで記述さ
れ１階層的に記述することが可能である。

そして、命令は全てデータ駆動に基づいて実行されるの
で、命令の実行に必要な入力データの全てが揃った時点
で始めて演算が実行される。

第２図では、入力データで指示されたＸとｙを加算（Ａ
　Ｄ　Ｄ）する命令と、Ｘとｙを加算した結果を入力と
して、手続きを呼出す命令（ＣＡＬＬ）とから構成され
る。手続き呼出し命令の入力ＡとＢは呼出す手続き名を
表わしている。また、手続きＡで使用される演算ノード
１２はＡ１〜Ａｎで記述し１手続きＢで使用される演算
ノード１２は８１〜Ｂｍで記述しである。

第３図は、上記第２図に示したデータ・フロー・グラフ
に対応する命令語（命令テーブル）を表現した図である
。

第３図における命令テーブル２０は、ＦＩＦ○により命
令実行を待ち合せるためのリンケージポインタ２１と演
算処理内容を示す演算処理名２２と入力データの入手先
のアドレスを示す入力データ入手先２３と該入力データ
を入力した演算結果を出力として次命令に通知するため
の出力通知先２４と該命令の入力データの準備状況を表
示するための入力データ数カウンタ２５と演算結果を格
納するための出力データ格納エリア２６から構成される
。

そして、各演算ノード１２に対して、命令テーブル２０
が１面ずつ用意される。また、入力データ入手先２３と
出力通知２４と出力データ格納エリア２６は各々の個数
によって可変となることは言までもない、なお、ＡＤＤ
ノードの命令を構成する各エリアだけに記号が付けられ
ているが、他のＣＡＬＬノードの各エリアも、演算処理
名２２と入力データ入手先２３に手続き名が入っている
点のみが異なるだけで、それ以外のエリアは全く同じで
あるため、記号を省略しである。

第４図は、データ駆動制御において、並列に実行可能と
なった命令を逐次的に処理するために、命令実行を待ち
合せるための命令実行待ちキュー３の構成例を示したも
のである。第４図における命令実行待ちキュー３は、並
列に実行可能となった複数の手続きを処理する場合に、
１つの手続き処理で終了するまで、他の手続きを待ち合
せることができるようにしである。すなわち、命令実行
待ちキュー３は階層的に実行される手続きの実行階層を
表示するネストレベルカウンタ２で指示される階層分だ
け用意し、各階層に対応する命令実行待ちキューはキュ
ーに登録された先頭の命令のアドレスを示す先頭アドレ
スポインタ３０とキューに登録された最後尾の命令のア
ドレスを示す最終アドレスポインタ３１から構成される
。そして、実行可能となった命令テーブル２０は各命令
のリンケージポインタ２１を使用して、ネストレベルカ
ウンタ２で指示される命令実行待ちキュー３に登録する
。なお、この例では命令テーブルのリンケージをとるた
めに命令アドレスを用いたが、命令テーブルが識別可能
な番号であってもさしつかえない。

第１図は、本発明の一実施例を示すデータ駆動型制御方
法の機能ブロック図である。

第１図において、５は演算ノードやアークで表現された
データ・フロー・プログラム、２は実行中の手続きの階
層レベルを表示するネストレベルカウンタ、３は並列に
実行可能となった命令の実行を待ち合せるための命令実
行待ちキュー、４は命令内の演算処理名で指示される演
算を行う演算処理部、１はデータ・フロー表現されたプ
ログラム命令を、データ駆動で実行するデータ駆動命令
実行制御部である。

第５図は、第１図におけるデータ駆動命令実行制御部の
動作フローチャートであり、第６図は第２図におけるＡ
ＤＤ命令を実行し、その結果２つの手続き呼出し命令が
実行可能状態となった場合のネストレベルカウンタと命
令実行待ちキューの状態を表わす例を示し、第７図は第
２図における手続きＡを呼出すＣＡＬＬ命令を実行し、
その結果手続きＡ内の命令Ａ１が実行可能状態となった
場合のネストレベルカウンタと命令実行待ちキューの状
態を表わす例である。

次に、第５図と第６図および第７図により、第１図の機
能ブロックと第３図の命令実行の動作と第４図のネスト
レベルカウンタと命令実行待ちキューの動作を説明する
。

先ず、データ駆動命令実行制御部１は、実行すべきデー
タ・フロー・プログラム５内の命令の入力データ数カウ
ンタ２５とネストレベルカウンタ２と命令実行待ちキュ
ー３の先頭アドレスポインタ３０と最終アドレスポイン
タ３１を初期設定する（ステップ４１）（第１図の矢印
（、）　）　、そして、一番初めに実行すべき命令のア
ドレスをネストレベルカウンタ２で指示される命令実行
待ちキュー３に９．録する（ステップ４２）（第１図の
矢印（ｂ））、次に、ネストレベルカウンタ２で指示さ
れる命令実行待ちキュー３に実行可能な命令があれば（
ステップ４３．４４）（第１図の矢印（ｃ））、命令実
行待ちキュー３から先頭の命令アドレスを取り出した後
、先頭アドレスポインタ３０と必要があれば最終アドレ
スポインタ３１を更新しくステップ４５）、取り出した
命令内の演算処理名２２で定まる演算処理部４を決定し
て。

その命令アドレスを演算処理部４に引き継ぎ、演算処理
部４を起動する。起動を受けた演算処理部４は、その命
令アドレスで指示される命令内の入力データ入手先２３
から入力データを入手し、その入力データを用いて所定
の演算を行い、演算結果を出力データ格納エリア２６に
格納する（ステップ４６）（第１図の矢印（ｄ））。そ
して、データ駆動命令制御部１へ制御を戻す（第１図の
矢印（ｅ））。

次に、データ駆動命令制御部１は処理中の命令内で指示
される出力通知先２４を求め、出力データすなわち次命
令の入力データが準備されたことを入力データ数カウン
タ２５を用いて更新しくステップ４７．４８）　、次命
令の実行に必要な全ての入力データが揃えば（ステップ
４９）、次命令のアドレスをネストレベルカウンタ２で
指示される命令実行待ちキュー３の最終アドレスポイン
タ３１で指示される命令の次に登録するために最終アド
レスポインタ３１とリンケージポインタ２１を更新する
（ステップ５０）、また、次命令の入力データが全て揃
わなければ何もしない。さらに、出力通知先２４が複数
があれば前述の処理を繰り返す（ステップ４７〜ステツ
プ５０）。

そして、全ての出力通知先２４への出力データの通知が
終了すると、命令実行待ちキュー３に実行すべき命令ア
ドレスが登録されているか否かの判定処理（ステップ４
３．ステップ４４）に戻る。

命令アドレスが登録されていれば、前記命令実行処理（
ステップ４５〜ステツプ５０）を繰り返す。

一方、命令実行待ちキュー３に登録されている命令アド
レスがなければ、実行すべき命令がないものと判断して
データ・フロー・プログラムの処理を終了する。

次に、第２図のおけるデータ・フロー・プログラムの命
令実行について、第６図と第７図を用いて詳述する。

前述したように、データ駆動命令実行制御部１は、第２
図における主ルーチン１０の実行において、ネストレベ
ルカウンタ２を初期設定（例えば。

Ｏ）し、一番初めに実行すべき命令、すなわち、ＡＤＤ
命令をネストレベルカウンタ２で指示される命令実行待
ちキュー３に登録した後、該ＡＤＤ命令を命令実行待ち
キュー３から取り出し、命令の実行を行う、そして、該
ＡＤＤ命令の演算結果を手続きＡと手続きＢを呼出す２
つの手続き呼出し命令に通知する。その際、手続きを呼
出すための手続き名は固定的に与えられている。（第２
図の手続は呼出し命令（ＣＡＬＬ）の入力であるＡとＢ
）ので、該ＡＤＤ命令の演算結果が前記２つの手続き呼
出し命令に通知されると同時に２つの手続き呼出し命令
が実行可能状態となり、データ駆動命令実行制御部１は
該手続き呼出し命令を命令実行待ちキュー３へ登録する
。

そのネストレベルカウンタ２と命令実行待ちキュー３の
状態を第６図に示す、そして、次に、第６図の状態にお
いて、データ駆動命令実行制御部１により、命令実行待
ちキュー３から、手続きＡを呼出す手続き呼出し命令が
取り出され、手続きＡが呼出される。この手続きを呼出
す処理の過程がネストレベルカウンタ２は＋１だけ更新
され、手続きＡ内の命令の入力データ数カウンタ２Ｓが
初期設定された後、ネストレベルカウンタ２で指示され
る命令実行待ちキュー３に手続きＡの一番最初に実行す
べき命令（第２図ではＡｘ）が登録される（第７図）。

以後、ネストレベルカウンタ２が更新されるまでは、手
続きＡの命令が先立って実行され、手続きＢの呼出し命
令の実行が待ち合せられる。なお、手続きＡから主ルー
チンに戻るためのリターン命令が実行されるとネストレ
ベルカウンタ２は−１だけ更新される。そして、待ち合
せていた手続きＢを呼出す命令が実行される。

このように、本実施例においては、並列に実行可能状態
となった複数の手続きを実行する場合、１つの手続き処
理が終了するまで他の手続き処理を待ち合せることがで
きるため、大局的な並列性と局所的な並列性を無差別に
明示したり、実行したりすることがなくなり、プログラ
ムの理解性やテスト効率の向上が図れる。

〔発明の効果〕 以上説明したように５本発明によれば、複数の手続きが
並列に実行可能状態になっても、手続きの生起・終了の
シケースを保証することができるため、手続き内での局
所的な並列性と主ルーチンにおける大局的な並列性が無
差別に明示されたり、実行されたりすることがなくなり
、プログラムの理解性向上やプログラムのトレース時間
の削減が可能になる。

【図面の簡単な説明】

第１図は本発明の一実施例を示すデータ駆動型制御方法
の機能ブロック図、第２図は本発明で使用するデータ・
フロー・グラフの説明図、第３図は本発明の一実施例を
示すデータ駆動命令の結合図、第４図は本発明の一実施
例を示すネストレベルカウンタと命令実行待ちキューの
関係を示す説明図、第５図は第１図におけるデータ駆動
命令実行制御部の動作フローチャート、第６図は第２図
のデータ・フロー・プログラムの実行過程におけるネス
トレベルカウンタと命令実行待ちキューの関係の説明図
、第７図は第２図のデータ・フロー・プログラムの実行
過程におけるネストレベルヵウンタと命令実行待ちキュ
ーの関係の説明図である。 １・・・データ駆動命令実行制御部、２・・・ネストレ
ベルカウンタ、３・・・命令実行待ちキュー、４・・・
演算処理部、５・・・データ・フロー・プログラム、６
゜１０・・・主ルーチン、１１・・・手続き、１２・・
・演算ノード、１３・・・アーク、２０・・・命令テー
ブル、２１・・・リンケージポインタ、２２・・・演算
処理名、２３・・・入力データ入手先、２４・・・出力
通知先、２５・・・入力データ数カウンタ、２６・・・
出力データ格納エリア、３０・・・先頭アドレスポイン
タ、３１・・・最終アドレスポインタ。 鶏　２　目

Claims (1)

【特許請求の範囲】
1. １、演算処理名と入力データ入手先と該入力データを用
   いた演算結果の出力通知先と該入力データが準備された
   ことを示す入力データ数カウンタから構成される命令と
   実行可能状態となつた命令の実行を持ち合せるための命
   令実行待ちキューとデータ駆動の原理に基づいて命令の
   実行を制御するデータ駆動命令実行制御部とこれらを格
   納する記憶手段とを有するデータ駆動制御方法において
   、実行中の手続きのネストレベルを指示するネストレベ
   ルカウンタとネストレベルカウンタの値に対応してそれ
   ぞれに命令実行待ちキューとを該記憶手段に具備し、該
   ネストレベルカウンタは手続き呼出し命令または呼出し
   元へ戻るリターン命令が発生するたびに更新しつつ、デ
   ータ駆動命令実行制御部はネストレベルカウンタで指示
   される命令実行待ちキューから実行可能状態となつた命
   令を取り出し、命令内の演算処理名で指示される演算を
   行い、演算結果により新たに実行可能状態となつた命令
   をネストレベルカウンタで指示される命令実行待ちキュ
   ーの最後尾へ登録することにより、１つの手続きが終了
   まで他の並列に実行可能状態となつた手続きの実行を待
   ち合せるようにしたことを特徴とするデータ駆動型制御
   方法。