(57)【特許請求の範囲】
【請求項１】
環境レベルと呼ぶ数値が付与されたノードと、ノード間を結合するアークとで構成されたデータフローグラフでプログラムを表現し、実行環境レベルと呼ぶ数値が付与されたトークンの値を前記データフローグラフに基づき更新していくことにより計算を実行するデータフロー計算機の実行制御装置において、
トークンが前記データフローグラフ上の経路に沿って伝播する途中でトークンの入力アークへの到着を監視し、指定された前記実行環境レベルを持つトークンが、該実行環境レベル以上の前記環境レベルを持つノードからアークで連結されたノードＸへ向かう全ての入力アーク上に揃うと、当該ノードＸに対応づけられた命令を識別する発火制御手段と、
当該ノードＸが前記発火制御手段で演算命令と識別された場合、到着したトークンを入力して演算を行い、該演算結果をトークンの値に代入し、該トークンを、該トークンの前記実行環境レベル以上の環境レベルを持つノードに向かう出力アーク上に伝播させる演算命令実行手段と、
当該ノードＸが前記発火制御手段で制御命令と識別された場合、当該ノードＸの命令内容に従って到着したトークンの経路を変更し、該トークンを、該トークンの前記実行環境レベル以上の前記環境レベルを持つノードに向かう出力アーク上に伝播させる制御命令実行手段を有する、
データフロー計算機の実行制御装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、非同期並列実行制御を行うデータフロー計算機の実行制御装置に関する。
【０００２】
【従来の技術】
データフロー計算機は、プログラムをノードとノード間の経路を示すアークからなるデータフローグラフで表現し、グラフ構造内をトークンと呼ぶデータの値を更新しながら流すことにより計算を実行する。
【０００３】
ノードには演算ノードと制御ノードがある。演算ノードでは、トークンの値を受け取り、与えられた演算を行い、結果をトークンの値として出力する。制御ノードでは、トークンを流す経路を制御する。
【０００４】
データフロー計算機に実行制御装置として、データ駆動実行制御装置、要求駆動実行制御装置がある。
【０００５】
データ駆動実行制御装置：
データ駆動実行制御装置は、データフローグラフの全てのノードに対して以下に示す方法で処理を施す。
【０００６】
１．全ての入力アーク上にトークンが到達するまでノードを待機させる。
【０００７】
２．入力アーク上にトークンが揃った後、ノードに与えられた機能を実行させる。これをノードの発火と呼ぶ。このとき、入力アーク上のトークンを取り除く。
【０００８】
３．実行結果を出力アーク上にトークンとして出力する。
【０００９】
それぞれのノードを上記実行方法に従って発火させることにより、グラフ全体を非同期並列に実行する。
【００１０】
従来のデータ駆動実行制御装置の構成例を図５に示す。以下図５の各手段の機能について説明する。
（発火制御手段１０Ｃ）
トークン到着監視機能１２は、全ての入力アーク上にトークンが揃ったノードを検出し、発火させる。ノード分類機能１３は、発火したノードを演算ノードと制御ノードに分類し、対応する命令実行手段に制御信号を送る。なお、演算命令を持つノードを演算ノード、制御命令を持つノードを制御ノードと呼ぶ。
（演算命令実行手段２０Ｃ）
入力トークン処理機能２１Ａは、発火したノードの入力アーク上のトークンを全て消去し、トークンの値を演算実行機能２２に送る。演算実行機能２２はトークンの値に対し、演算命令で与えられた演算を行い、結果をトークン出力機能２３Ｃに送る。トークン出力機能２３Ｃは、演算結果をトークンの値に代入し、トークンを発火したノードの出力アーク上に置く。
（制御命令実行手段３０Ｃ）
制御命令デコード機能３１では、制御ノードの命令を識別し、対応する命令実行機能に送る。命令実行機能では、与えられたノード種別に従って制御を行う。制御ノードには次のような種類がある。
【００１１】
・（分配ノード（Ｄ）３２Ｃ）１入力ｎ出力のノードである。入力アーク上のトークンを消去し、値をコピーしたトークンを全ての出力アーク上へ置く。
【００１２】
・（分岐ノード（ＳＷ）３３）２入力２出力のノードである。第２入力アーク上のトークンの値が真のとき、第１入力アーク上のトークンを第１出力アーク上へ置く。偽のときは、第１入力アーク上のトークンを第２出力アーク上へ置く。
【００１３】
・（手続き呼出しノード（ＣＡＬＬ）３４Ａ）２入力１出力のノードである。第２入力アーク上のトークンをコピーし、第１入力トーク上のトークンの値として格納されている関数名から関数の手続き開始ノードを求め、そのノードの第１入力アーク上に置く。また、出力アークの名前を値としたトークンを生成する。第１入力アーク上のトークンの値として格納されている関数名から関数の手続き復帰ノードを求め、そのノードの第１入力アーク上に、生成したトークンを置く。入力アーク上のトークンを消去する。
【００１４】
・（手続き開始ノード（ＥＮＴＲＹ）３６）１入力１出力のノードである。入力アーク上のトークンのコピーを出力アーク上に置く。入力アーク上のトークンを消去する。
【００１５】
・（手続き復帰ノード（ＲＥＴＵＲＮ）３５Ｃ）２入力０出力のノードである。第２入力アーク上の値をコピーしてトークンを生成する。第１入力アーク上のトークンの値として、指定されたアークに生成したトークンを置く。
【００１６】
図６に実行例を示す。図中で黒丸はトークン、白丸ノードは演算ノード、白丸に十字のノードは分配ノードを表す。また、網掛けノードは実行を終ったノードを表す。図中の太線のノードに注目して動作を説明する。
【００１７】
１．トークン到着監視機能１２は、入力アーク上にトークンが揃っていないため（図６（１）〜（３））、太線のノードを発火させない。
【００１８】
２．入力アーク上にトークンが揃った後（図６（４））、トークン到着監視機能１２はノードを発火させる。
【００１９】
３．ノード分類機能１３は、発火したノードを演算ノードであると識別し、演算命令実行手段２０Ｃへ制御信号を送る。
【００２０】
４．入力トークン処理機能２１Ａは、入力アーク上のトークンを取り除く。
【００２１】
５．演算実行機能２２により演算が行われる。
【００２２】
６．トークン出力機能２３は、出力アーク上にトークンを置く（図６（５））。
【００２３】
以上のように実行を行うことにより、グラフ全体を実行していく。
【００２４】
要求駆動実行制御装置：
要求駆動実行制御装置は、指定したノードに至る経路上のノードだけを選択し、計算を行う。この実行制御装置は、データフローグラフの全てのノードに対して以下に示す方法で処理を施す。
【００２５】
１．（ａ）出力アーク上に要求信号（デマンド）が到着するまでノードを待機させる。
【００２６】
（ｂ）出力アーク上にデマンドが到達した後、入力ア−クにデマンドを出力する。
【００２７】
（ｃ）全ての入力アーク上にトークンが到達するまでノード待機させる。
【００２８】
２．入力アーク上にトークンが揃った後、ノードを発火させる。このとき入力アーク上のトークンを取り除く。
【００２９】
３．演算結果を出力アークに出力する。
【００３０】
図７に実行例を示す。図中で白丸のノードは演算ノード、白丸に十字のノードは分配ノード、黒丸はトークン、右下りの八ッチングが施された丸はデマンドを表す。また、左下りのハッチングが施されたノードはデマンドを受けたノード、網掛けのノードは発火したノードを表す。上記のように各ノードを個別に実行させると、グラフ全体の動作は以下のようになる。
【００３１】
１．指定したノードより、グラフ上の各ノードの出力側から入力側へデマンドを伝播させる（図７（１）〜（５））。
【００３２】
２．全てのデマンドが開始ノードまで伝播すると、開始ノードから出力アークへトークンを送出する（図７（６））。
【００３３】
３．デマンドを受けたノードからなる部分グラフをデータ駆動実行する（図７（７）〜（１０））。
【００３４】
以上により、デマンドを受け取ったノードのみが選択的に実行される。
【００３５】
色付きトークン方式：
データフロー計算機において、複数実行環境下での多重実行方式として、色付きトークン方式がある。トークンに色と呼ぶタグを付け、実行環境毎に色を設定する。データ駆動実行制御装置の１，２，３項、要求駆動実行制御装置の１（ｃ），２，３項を以下のように変更することにより、色付きトークン方式による実行制御が実現される。
【００３６】
１．全ての入力アーク上に、色の等しいトークンが到達するまで、ノードを待機させる（１（ｃ）も同様）。
【００３７】
２．入力アーク上に色の等しいトークンが揃った後、ノードを発火させる。このとき、入力アーク上の色の等しいトークンを取り除く。
【００３８】
３．結果を出力アークに出力する。このとき、入力アーク上にあったトークンの色をコピーして出力する。
【００３９】
以上の実行方式を用いると、１つのグラフを、複数の実行環境下で（色別に）、互いに影響を及ぼさずに並列に実行させることができる。
【００４０】
従来の色付きトークン方式を使用した実行制御装置の構成例を図８に示す。以下図８の各手段の機能について説明する。
（発火制御手段１０Ｄ）
色付きトークン到着監視機能１６は、全ての入力アーク上に同じ色のトークンが揃ったノードを検出し、発火させる。ノード分類機能１３は、発火したノードを演算ノードと制御ノードに分類し、対応する命令実行手段に制御信号を送る。（演算命令実行手段２０Ｄ）
入力トークン処理機能２１Ｂは、発火したノードの入力アーク上の、同じ色を持つトークンを全て消去し、トークンの値を演算実行機能２２に送る。演算実行機能２２はトークンの値に対し、演算命令で与えられた演算を行い、結果をトークン出力機能２３Ｄに送る。トークン出力機能２３Ｄは、演算結果をトークンの値に代入し、入力アーク上より消去したトークンの色をコピーし、出力アーク上にトークンを置く。
（制御命令実行手段３０Ｄ）
制御命令デコード機能３１では、制御ノードの命令を識別し、対応する命令実行機能に送る。命令実行機能では、与えられたノード種別に従って制御を行う。制御ノードには次のような種類がある。
【００４１】
・（分配ノード（Ｄ）３２Ｂ）１入力ｎ出力のノードである。入力アーク上のトークンを消去し、値と色をコピーしたトークンを全ての出力アーク上へ置く。
【００４２】
・（分岐ノード（ＳＷ）３３）２入力２出力のノードである。第２入力アーク上のトークンの値が真のとき、第１入力アーク上のトークンを第１出力アーク上へ置く。偽のときは、第１入力アーク上のトークンを第２出力アーク上へ置く。
【００４３】
・（手続き呼出しノード（ＣＡＬＬ）３４Ｃ）２入力１出力のノードである。発火した際に、データフローグラフ上のどのトークンも使用していない色を求める。第２入力アーク上のトークンの値と、新たに生成した色によりトークンを生成する。第１入力アーク上のトークンの値より関数名を知り、生成したトークンを手続き開始ノードの第１入力アーク上に置く。また、入力アーク上のトークンの色と出力アークの名前の対を値とし、生成した色を付与したトークンを生成する。第１入力アーク上のトークンの値として格納されている関数名から関数の手続き復帰ノードを求め、そのノードの第１入力アーク上に生成したトークンを置く。入力アーク上のトークンを消去する。
【００４４】
・（手続き開始ノード（ＥＮＴＲＹ）３６）１入力１出力のノードである。入力アーク上のトークンのコピーを出力アーク上に置く。入力アーク上のトークンを消去する。
【００４５】
・（手続き復帰ノード（ＲＥＴＵＲＮ）３５Ｄ）２入力０出力のノードである。第１入力アーク上のトークンより手続き呼出し前の色を求め、第２入力アーク上の値をコピーしてトークンを生成する。第１入力アーク上のトークンの値として指定されたアークに生成したトークンを置く。
【００４６】
実際の実行例を図９に示す。図中で黒丸（Ｋ，ａ）は、値Ｋ色ａのトークンを表す。ここでは、１つのノードを注目して実行例を示す。
【００４７】
１．色付きトークン到着監視機能１６は、全ての入力アーク上に同じ色（ｉ）のトークンが揃ったことを検知し、ノードを発火させる（図９（３））。
【００４８】
２．ノード分類機能１３は、発火したノードを演算ノードであると識別し、演算命令手段２０Ｄへ制御信号を送る。
【００４９】
３．入力トークン処理機能２１Ｂは、入力アーク上の色（ｉ）のトークンを取り除く。
【００５０】
４．演算実行機能は演算２２を行う。
【００５１】
５．トークン出力機能２３Ｄは、同じ色（ｉ）を持つトークンを、出力アークへ出力する（図９（４））。
【００５２】
【発明が解決しようとする課題】
例えば、教育支援プログラムでは、基礎知識を持っていない学習者に対して多くの問題を与え、より多くの基礎知識を持っている学習者には、それら問題の一部を選択させたい場合がある。ここで、基礎知識の差をレベルの差ととらえ、基礎知識を多く持っているほどレベルが高いとする。
【００５３】
レベルの高い学習者は、基礎知識をそれほど必要としない。これに対して、レベルの低い学習者はより多くの問題により基礎知識を修得しなければならない。つまり、レベルの高い学習者が必要とする問題に、レベルの低い学習者が必要とする基礎知識を獲得するための問題を付け加えることにより、レベルの低い学習者用の問題が揃うと考えられる。このような場合には、レベルの高い学習者が必要とする問題は、レベルの低い学習者の必要とする問題の部分集合となる。
【００５４】
ここで、ある１つの問題を提示する機能をノードとし、提示する順序をアークとした問題提示プログラムを表現することを考える。複数レベルに対応する問題提示を行う場合に、各ノードについてレベル毎に選択的に実行する機能を与えられているときには、問題提示プログラムを１つ作成し、各レベルで共有すればよい。このような機能がない場合には、レベル毎に別個のプログラムを作成しなければならない。このように、レベル毎にプログラムを作ると、あるレベルに対応するプログラムを修正した場合には、そのレベル以下のプログラムに対して同じ修正を加えなければならない。このとき、共通部分を修正する場合には、修正しなければならないプログラム数は、さらに増えることになる。このような問題を解決するために、レベル毎にノードを選択的に実行させる機能が必要である。
【００５５】
レベル毎にノードを選択的に実行させる機能の実現方法として、条件分岐を利用する方法が考えられる。すなわち、ノードの前に分岐用のプログラムを付け加えて、条件を満たすトークンだけをノードに送ることにより、レベルに応じてノードを選択的に実行させることができる。この方法では全てのノードに対して分岐用プログラムを付与しなければならない。このため、問題の提示レベルを変更する場合に、分岐プログラムの修正が必要となるという問題がある。このように、条件分岐を利用する方法では、プログラムの作成時・修正時に、条件分岐に関する箇所の作成・修正作業が必要となり、プログラム作成者の負担が増大することになる。このような問題を解決するために、データフロー計算機にレベル毎にノードを選択的に実行させる機能を持たせる必要がある。
【００５６】
データ駆動実行制御装置では、入力アーク上にトークンが揃った場合に発火を行うことにより実行が進められる。この装置では、分岐命令と手続き呼出し命令で実行経路を選択する手段を与えている。要求駆動実行制御装置では、上記命令による選択の他に、デマンドを伝播させ、デマンドの到達したノードを選択的に実行させることができる。しかし、これらの装置では、レベルに応じて選択的にノードを発火する機能を持たない。
【００５７】
色付きトークンモデルは、実行環境の違いをトークンの色で表し、実行時には実行環境の違いを検出し、同じ実行環境のトークンにより実行を進める技術である。この方法は、レベルの違いに対応する技術ではなく、トークンはグラフ全体を、もしくはデマンドの伝播したノード全てをトークンの色別に実行することになる。従って、レベルに応じて選択的にノードを発火する機能を持たない。
【００５８】
本発明の目的は、レベルに応じてノードを選択的に実行させる、データフロー計算機の実行制御装置を提供することにある。
【００５９】
【課題を解決するための手段】
本発明の、データフロー計算機の実行制御装置は、
環境レベルと呼ぶ数値が付与されたノードと、ノード間を結合するアークとで構成されたデータフローグラフでプログラムを表現し、実行環境レベルと呼ぶ数値が付与されたトークンの値を前記データフローグラフに基づき更新していくことにより計算を実行するデータフロー計算機の実行制御装置において、
トークンが前記データフローグラフ上の経路に沿って伝播する途中でトークンの入力アークへの到着を監視し、指定された前記実行環境レベルを持つトークンが、該実行環境レベル以上の前記環境レベルを持つノードからアークで連結されたノードＸへ向かう全ての入力アーク上に揃うと、当該ノードＸに対応づけられた命令を識別する発火制御手段と、
当該ノードＸが前記発火制御手段で演算命令と識別された場合、到着したトークンを入力して演算を行い、該演算結果をトークンの値に代入し、該トークンを、該トークンの前記実行環境レベル以上の環境レベルを持つノードに向かう出力アーク上に伝播させる演算命令実行手段と、
当該ノードＸが前記発火制御手段で制御命令と識別された場合、当該ノードＸの命令内容に従って到着したトークンの経路を変更し、該トークンを、該トークンの前記実行環境レベル以上の前記環境レベルを持つノードに向かう出力アーク上に伝播させる制御命令実行手段を有する。
【００６０】
【作用】
本発明は、データフロー計算機の実行制御装置が、環境依存発火機能と環境依存分配機能を有することを特徴とする。
【００６１】
環境依存発火機能とは、ある実行環境レベルｍを持つトークンがあるノードｎに到達したときに、ｍ以上の環境レベルを持つノードからノードｎへ向かう全ての入力アーク（環境入力アークと呼ぶ）上に実行環境レベルｍのトークンが揃った場合にノードｎを発火させる機能である。環境依存分配機能とは、トークンの実行環境レベル以上の環境レベルを持つノードに向かう全ての出力アーク（環境出力アークと呼ぶ）上に、そのトークンを出力する機能である。
【００６２】
環境依存発火機能は、全ての環境入力アーク上にトークンが全て揃うまでノードを待機させ、全ての環境入力アーク上にトークンが揃った後、ノードを発火させる。また、環境依存分配機能は、全ての環境出力アーク上に実行環境レベルを与えたトークンを出力する機能である。従って、ある実行環境レベルｍをトークンに付与してプログラムの実行を開始させると、ｍ以上の環境レベルを持つノード間にだけトークンを伝播させ、ｍ以上の環境レベルを持つノードだけを実行させることができる。
【００６３】
【実施例】
次に、本発明の実施例について図面を参照して説明する。
【００６４】
ノードの集合をＮとする。ノードｎに対し、環境レベルとしてｔａｇ（ｎ）を付与する。さらに、実行環境レベルｍをトークンに付与する。ノードｎの第ｉ入力アークの先に接続されたノードの環境レベルをｔａｇin（ｎ，ｉ）、ノードｎの第ｊ出力アークの先に接続されたノードの環境レベルをｔａｇout （ｎ，ｊ）と表す。このとき、ｍ≦ｔａｇin（ｎ，ｉ）を満たす環境レベルを持つノードからノードｎへ張られたアークがノードｎの環境入力アークであり、ノードｎからｍ≦ｔａｇout （ｎ，ｊ）を満たす環境レベルを持つノードへ張られたアークが環境出力アークである。
【００６５】
図１は環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置の構成を示すブロック図である。それぞれの機能について以下で説明する。
（発火制御手段１０Ａ）
入力アーク選定機能１０は、ノードの入力アークから、トークンの実行環境レベル以上の環境レベルを持つノードを先のノードとして有する入力アークを環境入力アークとして選定する。トークン到着監視機能１２は、全ての環境入力アーク上にトークンが揃ったノードを検出し、発火させる。ノード分類機能１３は、発火したノードを演算ノードと制御ノードに分類し、対応する命令実行手段に制御信号を送る。
（演算命令実行手段２０Ａ）
入力トークン処理機能２１Ａは、発火したノードの環境入力アーク上のトークンを全て消去し、トークンの値を演算実行機能２２に送る。演算実行機能２２は、トークンの値に対して与えられた演算を行い、結果をトークン出力機能２３に送る。トークン出力機能２３Ａは、演算結果をトークンの値に代入し、実行環境レベルを与えたトークンを環境出力アーク上に置く。
（制御命令実行手段３０Ａ）
制御命令デコード機能３１では、制御ノードの命令を識別し、対応する命令実行機能に送る。命令実行機能では、与えられたノード種別に従って制御を行う。制御ノードには次のような種類がある。
【００６６】
・（分配ノード（Ｄ）３２Ａ）１入力ｎ出力のノードである。入力アーク上ののトークンを消去し、値と実行環境レベルをコピーしたトークンを全ての環境出力アーク上へ置く。
【００６７】
・（分岐ノード（ＳＷ）３３）２入力２出力のノードである。第２入力アーク上のトークンの値が真のとき、第１入力アーク上のトークンを第１出力アーク上へ置く。偽のときは、第１入力アーク上のトークンを第２出力アーク上へ置く。
【００６８】
・（手続き呼出しノード（ＣＡＬＬ）３４Ａ）２入力１出力のノードである。第２入力アーク上のトークンをコピーし、第１入力アーク上のトークンの値として格納されている関数名から関数の手続き開始ノードを求め、その第１入力アーク上に置く。また、出力アークの名前を値としたトークンを生成する。第１入力アーク上のトークンの値として格納されている関数名から関数の手続き復帰ノードを求め、そのノードの第１入力アーク上に生成したトークンを置く。入力アーク上のトークンを消去する。
【００６９】
・（手続き開始ノード（ＥＮＴＲＹ）３６）１入力１出力のノードである。入力アーク上のトークンのコピーを出力アーク上に置く。入力アーク上のトークンを消去する。
【００７０】
・（手続き復帰ノード（ＲＥＴＵＲＮ）３５Ａ）２入力０出力のノードである。第２入力アーク上のトークンの値と実行環境レベルをコピーしトークンを生成する。第１入力アーク上のトークンとして指定されたアークに生成したトークンを置く。
【００７１】
図２に実行例を示す。環境レベルとしてｔ１，ｔ２，ｔ３（ｔ１＜ｔ２＜ｔ３）を用いる。図中で黒丸はトークン、白丸ノードは演算ノード、白丸に十字のノードは分配ノードを表す。また、網掛けノードは実行の終ったノードを表す。ノードの左上の数字はノード番号を表し、右上の数字は環境レベルを表す。ノードｘよりｙに張られたアークをｘ→ｙと表す。アーク番号は、左から１，２・・・と付ける。
【００７２】
ここでは、実行環境レベルｔ２のトークンが伝播している場合について動作を説明する。まず、ノード４に注目し、動作を説明する。
【００７３】
１．ｉ＝２，３においてｔ２≦ｔａｇin（４，ｉ）となる。従って、入力アーク選定機能１１は、アーク２→４，３→４を環境入力アークと識別する。
【００７４】
２．これらの環境入力アーク上にトークンが揃うと（図２（２））、ノード４を発火する。
【００７５】
３．ノード分類機能１３は、ノード４を演算ノードと識別し、演算命令実行手段２０Ａへ制御信号を送る。
【００７６】
４．その後、入力トークン処理機能２１Ａは、入力アーク上のトークンを取り除く。
【００７７】
５．演算実行機能２２は演算を行う。
【００７８】
６．最後に、トークン出力機能２３Ａは、ｔ２≦ｔａｇout （４，１）から４→５を環境出力アークと判定し、実行環境レベルｔ２のトークンを出力する（図２（３））。
【００７９】
次に、ノード５に注目する。
【００８０】
１．入力アーク選定機能１１は、ｔ２≦ｔａｇin（５，１）からアーク４→５を環境入力アークであると判定する。環境入力アーク上にトークンが揃っているため、ノード５を発火させる。
【００８１】
２．ノード分類機能１３により、制御命令実行手段３０Ａへ制御信号が送られ、制御命令デコード機能３１により、分配ノードと判断される。
【００８２】
３．ｊ＝１，２において、ｔ２≦ｔａｇout （５，ｊ）は満たされる。このため、分配ノードでは、アーク５→６，５→７を環境出力アークと判定し、これらのアーク上に実行環境レベルｔ２のトークンを出力する（図２（４））。
【００８３】
以上のようにして、環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置は実行を行う。
【００８４】
要求駆動実行制御装置の実施例：
デマンド伝播に関しては、〔従来の技術〕と同様である。デマンドの伝播したノード、および、その入力アークからなる部分グラフを、実行するデータフローグラフとする。このグラフを環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置により実行させる。
【００８５】
色付きトークン方式によるデータ駆動実行制御装置への応用：
図３は、環境依存発火装置と環境依存分配機能を有するデータ駆動実行制御装置（色付きトークン方式）の構成を示すブロック図である。それぞれの機能について以下で説明する。
（発火制御手段１０Ｂ）
発火制御手段１０Ｂは、それぞれのノードに対して以下の処理を行う。
【００８６】
１．色検出機能１４は、入力アーク上のトークンの全ての色を検出する。
【００８７】
２．色別入力アーク選定機能１５は、色検出機能１４により検出された色の中で、未処理の色を選出する。次に、ノードの入力アークから、選出したトークンの実行環境レベル以上の環境レベルを持つノードを先のノードとして有する入力アークを環境入力アークとして選定する。
【００８８】
３．トークン到着監視機能１２は全ての環境入力アーク上に、選出した色と同じ色を持つトークンが揃ったノードを検出し、発火させる。発火が行われずに、かつ、色検出機能１４により検出された色のうち、未処理の色がある場合、１に戻る。
【００８９】
４．ノード分類機能１３は、発火したノードを演算ノードと制御ノードに分類し、対応する命令実行手段に制御信号を送る。色検出機能１４により検出された色のうち、未処理の色がある場合、１に戻る。
（演算命令実行手段２０Ｂ）
入力トークン処理機能２１Ｂは、発火したノードの環境入力アーク上で、同じ色を持つトークンを全て消去し、トークンの値を演算実行機能２２に送る。演算実行機能２２はトークンの値に対し、与えられた演算を行い、結果をトークン出力機能２３Ｂに送る。トークン出力機能２３Ｂは、演算結果をトークンの値に代入し、入力アーク上より消去したトークンの色と実行環境レベルを与えたトークンを環境出力アーク上に置く。
（制御命令実行手段３０Ｂ）
制御命令デコード機能３１では、制御ノードの命令を識別し、対応する命令実行機能に送る。命令実行機能では、与えられたノード種別に従って制御を行う。制御ノードには次のような種類がある。
【００９０】
・（分配ノード（Ｄ）３２Ｂ）１入力ｎ出力のノードである。入力アーク上ののトークンを消去し、値と色と実行環境レベルをコピーしたトークンを全て環境出力アーク上へ置く。
【００９１】
・（分岐ノード（ＳＷ）３３）２入力２出力のノードである。第２入力アーク上のトークンの値が真のとき、第１入力アーク上のトークンを第１出力アーク上へ置く。偽のときは、第１入力アーク上のトークンを第２出力アーク上へ置く。
【００９２】
・（手続き呼出しノード（ＣＡＬＬ）３４Ｂ）２入力１出力のノードである。発火した際に、データフローグラフ上のどのトークンも使用していない色を求める。第２入力アーク上のトークンの値と実行環境レベルと、新たに生成した色によりトークンを生成する。第１入力アーク上のトークンの値より関数名を知り、生成したトークンを手続き開始ノードの第１入力アーク上に置く。また、入力アーク上のトークンの色と出力アークの名前の対を値とし、実行環境レベルと新たに生成した色によりトークンを生成する。第１入力アーク上のトークンの値として格納されている関数名から関数の手続き復帰ノードを求め、そのノードの第１入力アーク上に生成したトークンを置く。入力アーク上のトークンを消去する。
【００９３】
・（手続き開始ノード（ＥＮＴＲＹ）３６）１入力１出力のノードである。入力アーク上のトークンのコピーを出力アーク上に置く。入力アーク上のトークンを消去する。
【００９４】
・（手続き復帰ノード（ＲＥＴＵＲＮ）３５Ｂ）２入力０出力のノードである。第１入力アーク上のトークンより手続き呼出し前の色を求め、第２入力アーク上のトークンの値と実行環境レベルをコピーしてトークンを生成する。第１入力アーク上のトークンの値として指定されたアークに生成したトークンを置く。
【００９５】
図４に実行例を示す。環境レベルとして、ｔ１，ｔ２，ｔ３（ｔ１＜ｔ２＜ｔ３）を用いる。ノードの左上の数字はノード番号を表し、右上の数字は環境レベルを表す。黒丸のトークンは、色ａを持ち、実行環境レベルとしてｔ１を与えている。黒の四角のトークンは、色ｂを持ち、実行環境レベルとしてｔ２を与えている。白丸のノードは演算ノード、白丸に十字のノードは分配ノードを表す。ノードｘよりｙに張られたアークをｘ→ｙと表す。アーク番号は、左から１，２，・・・と付ける。まず、ノード４に注目して動作を説明する。
【００９６】
１．色検出機能１４は、色ａとｂが存在することを検出する。
【００９７】
２．色別入力アーク選定機能１５は、まず色ａのトークンのタグより、実行環境レベルがｔ１であることを知る。ノード４では、ｉ＝１，２，３において、ｔ１≦ｔａｇin（４，ｉ）となる。従って、色別入力アーク選定機能１５はアーク１→４，２→４，３→４を環境入力アークと判定する。
【００９８】
３．トークン到着監視機能１２は、この環境入力アーク上に色ａのトークンが揃っていないため（図４（１））、ノード４をまだ発火させない。
【００９９】
４．次に、色別入力アーク選定機能１５は、色ｂのトークンのタグより実行環境レベルがｔ２であることを知る。ｉ＝２，３において、ｔ２≦ｔａｇin（４，ｉ）となる。従って、色別入力アーク選定機能１５はアーク２→４と３→４を環境入力アークと判定する。
【０１００】
５．トークン到着監視機能１２は、この環境入力アーク上に色ｂのトークンが揃っているため（図４（１））、ノード４を発火させる。
【０１０１】
６．ノード分類機能１３は、ノード４を演算ノードと識別し、演算命令実行手段２０Ｂへ制御信号を送る。
【０１０２】
７．入力トークン処理機能２１Ｂは、環境入力アーク上の色ｂのトークンを取り除く。
【０１０３】
８．演算実行機能２２は演算を行う。
【０１０４】
９．トークン出力機能２３Ｂは、ｔ２≦ｔａｇout （４，１）からアーク４→５を環境出力アークと判別し、入力トークンの色をコピーし、実行環境レベルｔ２としたトークンをアーク４→５に出力する（図４（２））。
【０１０５】
次に、ノード５に注目する。
【０１０６】
１．色検出機能１４は、色ｂが存在することを検出する。
【０１０７】
２．色別入力アーク選定機能１５は、色ｂのトークンのタグより実行環境レベルがｔ２であることを知る。ｔ２≦ｔａｇin（５，１）が満たされるため、色別入力アーク選定機能１５は、アーク４→５を環境入力アークと判定する。
【０１０８】
３．色別入力アーク選定機能１５は、環境入力アーク上に色ｂのトークンが揃っているため（図４（２））、ノード５を発火させる。
【０１０９】
４．ノード分類機能１３は、制御命令実行手段３０Ｂへ制御信号を送る。制御命令デコード機能３１がこのノードを分配ノードと判断する。
【０１１０】
５．ｊ＝１，２においてｔ２≦ｔａｇout （５，ｊ）であるので、分配ノードではアーク５→６，５→７を環境出力アークであると判定する。入力トークンの色をコピーし、実行環境レベルｔ２としたトークンを、これらの環境出力アーク上に出力する（図４（３））。
【０１１１】
以上のようにして、環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置（色付きトークンモデルを使用）は実行を行う。
【０１１２】
色付きトークンモデルによる要求駆動実行制御法への実施例：
デマンド伝播に関しては、〔従来の技術〕と同様である。デマンドの伝播したノード、および、その入力アークからなる部分グラフを、実行するデータフローグラフとする。この部分グラフを環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置（色付きトークンモデルを使用）により実行させる。
【０１１３】
【発明の効果】
以上示したように、本発明は、トークンに実行環境レベル、ノードに環境レベルを与えて、環境依存発火機能と環境依存分配機能を実行制御装置が有することにより、１つのデータフローグラフを複数の環境レベルで共有して同時に計算を進めても、互いに独立にそれぞれの環境レベルに応じた必要最小限の計算だけを行わせることが可能となる効果がある。
【図面の簡単な説明】
【図１】環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置の構成例を示すブロック図である。
【図２】環境レベルを用いた計算経路制御例を示す図である。
【図３】環境依存発火機能と環境依存分配機能を有するデータ駆動実行制御装置の構成例（色付きトークン方式）を示すブロック図である。
【図４】色付きトークン方式における環境レベルに応じた発火制御の例を示す図である。
【図５】従来のデータ駆動実行制御装置の構成例を示す図である。
【図６】データ駆動実行例を示す図である。
【図７】要求駆動実行例を示す図である。
【図８】従来のデータ駆動実行装置の構成例（色付きトークン）を示すブロック図である。
【図９】色付きトークンによる発火例を示す図である。
【符号の説明】
１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ    発火制御手段
２０Ａ，２０Ｂ，２０Ｃ，２０Ｄ    演算命令実行手段
３０Ａ，３０Ｂ，３０Ｃ，３０Ｄ    制御命令実行手段
１１    入力アーク選定機能
１２    トークン到着監視機能
１３    ノード分類機能
１４    色検出機能
１５    色別入力アーク選定機能
１６    色付きトークン到着監視機能
２１Ａ，２１Ｂ    入力トークン処理機能
２２    演算実行機能
２３Ａ，２３Ｂ，２３Ｃ，２３Ｄ    トークン出力機能
３１    制御命令デコード機能
３２Ａ，３２Ｂ，３２Ｃ    分配ノード（Ｄ）
３３    分配ノード（ＳＷ）
３４Ａ，３４Ｂ，３４Ｃ    手続き呼出しノード（ＣＡＬＬ）
３５Ａ，３５Ｂ，３５Ｃ，３５Ｄ    手続き復帰ノード（ＲＥＴＵＲＮ）
３６    手続き開始ノード（ＥＮＴＲＹ）
【図１】
0003732530.tif 000002
【図２】
0003732530.tif 000003
【図３】
0003732530.tif 000004
【図４】
0003732530.tif 000005
【図５】
0003732530.tif 000006
【図６】
0003732530.tif 000007
【図７】
0003732530.tif 000008
【図８】
0003732530.tif 000009
【図９】
0003732530.tif 000010