(57)【要約】【課題】ループ構造を含むデータフローグラフを各ノードの実行順序の決定および実行可否の判断が可能なパイプライン的動作に変形するデータフローグラフ処理装置等を提供する。【解決手段】データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部２１と、データフローグラフの開始ノードから値出力ノードへの依存関係を追加する依存関係追加部２２と、前回のイタレーションと今回のイタレーションへの依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する隠れ依存関係追加部２３とを有する構成とした。【選択図】図１
2012105593.tif 000002
【特許請求の範囲】
【請求項１】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部と、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する依存関係追加部と、
前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する隠れ依存関係追加部と
を有することを特徴とするデータフローグラフ処理装置。
【請求項２】
前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序の決定を行う実行順序決定部を有することを特徴とする、請求項１に記載のデータフローグラフ処理装置。
【請求項３】
前記実行順序決定部は、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、請求項２に記載のデータフローグラフ処理装置。
【請求項４】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加し、
前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前期値更新ノードから前期値出力ノードへ追加する
ことを特徴とするデータフローグラフ処理方法。
【請求項５】
前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序を決定することを特徴とする、請求項４に記載のデータフローグラフ処理方法。
【請求項６】
前記実行順序を決定する処理で、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
前記データフローグラフの各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、請求項５に記載のデータフローグラフ処理方法。
【請求項７】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する手順、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する手順、
および、前記値更新ノードから前記値出力ノードへ、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する手順、
をコンピュータに実行させることを特徴とするデータフローグラフ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データフローグラフ処理装置、データフローグラフ処理方法およびデータフローグラフ処理プログラムに関し、特にデータフローグラフからループ構造を取り除いて各ノードの実行順序の決定および実行可否の判断が可能なように変形することを可能とするデータフローグラフ処理装置等に関する。
【背景技術】
【０００２】
パーソナルコンピュータは、通常は１台に１つのプロセッサ（ＣＰＵ: Central Processing Unit、主演算制御手段）を持ち、そこで数々の演算処理を実行している。しかしながら、近年ではプロセッサ単独での演算能力向上が限界に達しているので、１つのプロセッサの中で実際に演算処理を行う部分（コア）を複数個持つものが主流になっている。このような構成のプロセッサをマルチコアプロセッサという。【０００３】
マルチコアプロセッサは、複数のコアを利用して複数のスレッド（プロセッサの利用単位）を同時に実行することが可能であるが、マルチコアプロセッサで動作性能の向上や消費電力の抑制の効果を得るためには、プログラムの側が複数スレッドの同時実行に対応したものであることが通常の場合には必要である。このため、１つのプログラムの中で並行して実行可能な部分を抽出して、それらを各々別のコアに割り振ることが必要となる。これを、コンピュータプログラムの並列化という。【０００４】
データフローグラフは、コンピュータ装置を利用したデータ処理の流れをグラフィカルに表現する手法の一つである。この手法は、コンピュータプログラムの並列化においても利用可能である。【０００５】
データフローグラフによるコンピュータプログラムの並列化手法では、ある計算が使用するデータやその計算結果にもとづいて、各計算の依存関係をデータフローグラフとしてとらえる。データフローグラフにおいて、ノードは計算を示す。そして、ノード間をつなぐ有向エッジ（矢印、以後単にエッジという）は、該ノード間のデータ依存関係、即ちある計算が別の計算の結果を利用するという関係を示す。そして、このデータフローグラフに基づいて、各ノードが示す各計算の実行順序が決定される。【０００６】
データフローグラフにおいて、各ノードが計算を実行し、一つのノードからエッジでつながる別のノードにその計算結果を渡し、これを受けたノードが計算を行う…という一連の動作を「パイプライン的」な動作という。データフローグラフは、このような「パイプライン的」な計算の動作のつながりを図示したものである。【０００７】
しかしながら、データフローグラフ上にループ構造が存在すると、このループ構造の中にあるノードは該ループ構造内のいずれかのノードの計算結果を利用するという依存関係を持つことになるので、これらのノードの実行順序の決定および実行可否の判断が不可能であるという問題がある。【０００８】
このループ構造の問題は、非特許文献１にもあるように、遅延ノードを利用して解決することが可能であるということが知られている。遅延ノードは、入力された値を所定のイタレーション（iteration, 繰り返し、反復）回数だけ保持してから出力するノードである。即ち、遅延ノードは、過去のイタレーションで記憶しておいた計算結果を、現在のイタレーションにおいて利用することが可能である。データフローグラフがループ構造をもつ場合には、そのループ構造に遅延ノードが含まれている。【０００９】
遅延ノードは、入力された値を直接出力せずに記憶し、そして過去に記憶した値を出力するが、「現在の値を記憶する」動作と「過去の値を出力する」動作との間には依存関係がないので、それぞれを独立に実行可能である。従って、そのような遅延ノードがループ構造に存在する場合には、遅延ノードを値出力ノードと値更新ノードという２つのノードに分割することによって、ループ構造を分解することが可能である。ただし、Ｎ回目のイタレーションにおける値更新ノードの計算結果は、Ｎ＋１回目以降のイタレーションの値出力ノードが使用する、という二つ以上のイタレーションにわたる依存関係が存在する（Ｎは自然数）。【００１０】
図１１は、非特許文献１に記載された既存技術に係るデータフローグラフ処理装置９１０の構成を示す説明図である。データフローグラフ処理装置９１０は、一般的なコンピュータ装置としての構成を備えている。即ち、データフローグラフ処理装置９１０は、コンピュータプログラムとして記述された各種処理を実行する主体である主演算制御手段（ＣＰＵ: Central Processing Unit）９１１と、データを記憶する記憶手段９１２と、操作者からのデータ入力および操作入力を受け付けると共に処理結果を操作者に提示する入出力手段９１３とを備える。【００１１】
主演算制御手段９１１でコンピュータプログラムが動作することにより、主演算制御手段９１１は遅延ノード分割部９２１および実行順序決定部９２４として動作する。遅延ノード分割部９２１は、記憶手段に記憶された処理前データフローグラフ９３１に対して後述の処理を行い、処理の完了した処理後データフローグラフ９３２を記憶手段９１２に記憶する。実行順序決定部９２４は、この処理後データフローグラフ９３２から、各ノードの実行順序の決定および実行可否の判断を行う。【００１２】
図１２は、図１１に示した遅延ノード分割部９２１による処理の概念について示す説明図である。図１２（ａ）には遅延ノード分割部９２１の動作を示すフローチャートを、図１２（ｂ）には遅延ノード分割部９２１に対して入力される処理前データフローグラフ９３１の例を、図１２（ｃ）には遅延ノード分割部９２１から出力される処理後データフローグラフ９３２の例を、各々示している。【００１３】
図１２（ｂ）に示した例では、処理前データフローグラフ９３１は、ノードＡ１〜Ａ８の８つのノードで構成されている。それらの中で、ノードＡ７およびＡ８が遅延ノードに該当する。遅延ノードは、入力データを直接出力せずに記憶し、次のイタレーションで出力する。即ち、遅延ノードが出力する値は過去のイタレーションで当該遅延ノードが記憶した値であり、現在のイタレーションでの入力値は現在の出力値の計算には使われない。【００１４】
このため、遅延ノード分割部９２１は、遅延ノードであるノードＡ７およびＡ８を各々、当該遅延ノードが保持する過去のイタレーションの値を出力する「値出力ノード」と、当該遅延ノードへ現在のイタレーションの値を記憶させる「値更新ノード」に分割する（図１２（ａ）のステップＳ９５１）。【００１５】
ノードＡ７は、遅延ノード分割部９２１によって値更新ノードＡ７ｕおよび値出力ノードＡ７ｏに分割される。同様にノードＡ８も、遅延ノード分割部９２１によって値更新ノードＡ８ｕおよび値出力ノードＡ８ｏに分割される。図１２（ｃ）は、図１２（ｂ）に示した処理前データフローグラフ９３１に対してこの遅延ノードの分割処理を行った結果を示している。【００１６】
ノードＡ７を分割した後は、値更新ノードＡ７ｕと値出力ノードＡ７ｏはグラフ上では接続関係を持たないが、値更新ノードＡ７ｕと値出力ノードＡ７ｏは同一の内部状態（記憶データ）を共有している。値更新ノードＡ８ｕおよび値出力ノードＡ８ｏについても同様である。【００１７】
そして、遅延ノードＡ７への入力エッジは値更新ノードＡ７ｕが、遅延ノードＡ７からの出力エッジは値出力ノードＡ７ｏがそれぞれ引き継ぐ。同様に、遅延ノードＡ８への入力エッジは値更新ノードＡ８ｕが、遅延ノードＡ８からの出力エッジは値出力ノードＡ８ｏが、それぞれ引き継ぐ。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】Arquimedes Canedo他（IBM Research, Tokyo）、「Automatic Parallelizationof Simulink Applications」、Code Generation and Optimization 2010、２０１０年４月２４日
【発明の開示】
【発明が解決しようとする課題】
【００１９】
図１３は、図１２（ｂ）および図１２（ｃ）に示した処理前データフローグラフ９３１および処理後データフローグラフ９３２を対比して示す説明図である。ここに示した例では、遅延ノード分割部９２１による処理の結果、処理後データフローグラフ９３２の中には、値出力ノードＡ７ｏ〜値更新ノードＡ８ｕのブロック９３２ａが、処理後データフローグラフ９３２の中の残りの部分（ブロック９３２ｂ）から孤立している。【００２０】
元々、全てのノードが１つにつながっていた処理前データフローグラフ９３１が、遅延ノード分割部９２１による処理によって、処理後データフローグラフ９３２はブロック９３２ａと９３２ｂの２つのブロックに分かれた。このような状態を、ここでは「グラフの分裂」という。【００２１】
ちなみに、データフローグラフの遅延ノードを分割して、このようなグラフの分裂が発生するか否かは、遅延ノードの位置や数に依存するものである。図１４は、図１２〜１３に示した処理前データフローグラフ９３１、およびそれとは別の処理前データフローグラフ９４１に対して遅延ノード分割部９２１による処理を各々行った結果である処理後データフローグラフ９３２および９４２について示す説明図である。処理前データフローグラフ９３１→処理後データフローグラフ９３２は、グラフの分裂が発生する場合について示している。それに対して、処理前データフローグラフ９４１→処理後データフローグラフ９４２は、グラフの分裂が発生しない場合について示している。【００２２】
処理前データフローグラフ９３１には、フィードバック側のパス上に遅延ノードであるノードＡ７およびＡ８が直列に接続されて存在する。そのため、これにノード分割部９２１による処理を行うと、処理後データフローグラフ９３２ではグラフの分裂が発生することになる。これに対して、処理前データフローグラフ９４１にはフィードバック側のパス上に遅延ノードＢ１が１つだけ存在する。これにノード分割部９２１による処理を行うと、処理後データフローグラフ９４２ではループ構造が分解されるだけであるので、グラフの分裂とはならない。【００２３】
以上で説明したように、データフローグラフの遅延ノードを分割するだけだと、グラフの分裂が発生する場合がある。グラフの分裂が発生すると、分裂したデータフローグラフの相互間の異なるイタレーションにおける依存関係が不明なものとなり、パイプライン的な動作を示すものではなくなるので、データフローグラフの各ノードが示す各計算の実行順序の決定および実行可否の判断が不可能となる。これでは、マルチコアプロセッサによる動作性能の向上や消費電力の抑制の効果を得ることができない。【００２４】
本発明の目的は、ループ構造を含むデータフローグラフを各ノードの実行順序の決定および実行可否の判断が可能なよう、パイプライン的な動作に適したデータフローグラフに変形することを可能とするデータフローグラフ処理装置、データフローグラフ処理方法およびデータフローグラフ処理プログラムを提供することにある。
【課題を解決するための手段】
【００２５】
上記目的を達成するため、本発明に係るデータフローグラフ処理装置は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部と、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加する依存関係追加部と、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する隠れ依存関係追加部を有することを特徴とする。【００２６】
上記目的を達成するため、本発明に係るデータフローグラフ処理方法は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加し、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加することを特徴とする。【００２７】
上記目的を達成するため、本発明に係るデータフローグラフ処理プログラムは、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する手順、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加する手順、および前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する手順、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２８】
本発明は、上記したように遅延ノード分割部が遅延ノードを値更新ノードと値出力ノードに分割した後で、それらの間に前回のイタレーションと今回のイタレーションとの間の依存関係を示す隠れ依存関係を追加する構成としたので、前述したグラフの分裂が発生することはない。これによって、ループ構造を含むデータフローグラフを各ノードの実行順序の決定および実行可否の判断が可能な、パイプライン的な動作に適したデータフローグラフに変形することを可能であるという、優れた特徴を持つデータフローグラフ処理装置、データフローグラフ処理方法およびデータフローグラフ処理プログラムを提供することができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の実施形態に係るデータフローグラフ処理装置の構成を示す説明図である。
【図２】図１に示した遅延ノード分割部による処理の概念について示す説明図である。図２（ａ）には遅延ノード分割部に対して入力される処理前データフローグラフの例を、図２（ｂ）には遅延ノード分割部から出力される第１の処理中データフローグラフの例を、各々示している。
【図３】図２に示した処理前データフローグラフおよび第１の処理中データフローグラフを対比して示す説明図である。
【図４】図１に示したノード分割部、依存関係追加部および隠れ依存関係追加部の各々の動作について示すフローチャートと、各段階の処理の概念について示す説明図である。図４（ａ）にはノード分割部、依存関係追加部および隠れ依存関係追加部の各々の動作について示すフローチャートを、図４（ｂ）には各段階の処理の概念について各々示している。図４（ａ）では、処理前データフローグラフ上に存在する特定の遅延ノードＣ１について、その処理に伴う変化を示す。
【図５】図１に示したデータフローグラフ処理装置で、遅延ノードを１個のみ含む処理前データフローグラフを処理した例を示す説明図である。
【図６】図５の続きである。
【図７】図１に示したデータフローグラフ処理装置で、遅延ノードを複数個含む処理前データフローグラフを処理した例を示す説明図である。
【図８】図７の続きである。
【図９】図１に示した実行順序決定部による各ノードの実行順序の決定および実行可否の判断の動作について示すフローチャートである。
【図１０】図６および図８に示した処理後データフローグラフに対して、実行順序決定部が実行順序を決定した結果を示す説明図である。図１０（ａ）には実行順序決定処理前のデータフローグラフ、図１０（ｂ）には実行順序決定処理後のデータフローグラフを、各々示している。
【図１１】非特許文献１に記載された既存技術に係るデータフローグラフ処理装置の構成を示す説明図である。
【図１２】図１１に示した遅延ノード分割部９２１による処理の概念について示す説明図である。図１２（ａ）には遅延ノード分割部９２１の動作を示すフローチャートを、図１２（ｂ）には遅延ノード分割部９２１に対して入力される処理前データフローグラフ９３１の例を、図１２（ｃ）には遅延ノード分割部９２１から出力される処理後データフローグラフ９３２の例を、各々示している。
【図１３】図１２（ｂ）および図１２（ｃ）に示した処理前データフローグラフおよび処理後データフローグラフを対比して示す説明図である。
【図１４】図１２〜１３に示した処理前データフローグラフ、およびそれとは別の処理前データフローグラフに対して遅延ノード分割部による処理を各々行った結果である処理後データフローグラフについて示す説明図である。
【発明を実施するための形態】
【００３０】
（第１の実施形態）
以下、本発明の第１の実施形態の構成について添付図１に基づいて説明する。
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
本実施形態に係るデータフローグラフ処理装置１０は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部２１と、データフローグラフの開始ノードから値出力ノードへの依存関係を追加する依存関係追加部２２と、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する隠れ依存関係追加部２３とを有する。そして、隠れ依存関係が追加されたデータフローグラフを利用して実行順序の決定を行う実行順序決定部２４をさらに有する。
【００３１】
また、実行順序決定部２４は、各ノードの実行順序を決定する際には、隠れ依存関係が追加されたデータフローグラフから隠れ依存関係を無視し、各ノードがある時点で実行可能であるか否かを判断する際には、隠れ依存関係が追加されたデータフローグラフの隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断する。
【００３２】
この構成を備えることにより、データフローグラフ処理装置１０は、ループ構造を含むデータフローグラフを各ノードの実行順序の決定および実行可否の判断が可能なように変形することが可能となる。
以下、これをより詳細に説明する。
【００３３】
図１は、本発明の実施形態に係るデータフローグラフ処理装置１０の構成を示す説明図である。データフローグラフ処理装置１０は、一般的なコンピュータ装置としての構成を備えている。即ち、データフローグラフ処理装置１０は、コンピュータプログラムとして記述された各種処理を実行する主体である主演算制御手段（ＣＰＵ: Central Processing Unit）１１と、データを記憶する記憶手段１２と、操作者からのデータ入力および操作入力を受け付けると共に処理結果を操作者に提示する入出力手段１３とを備える。
【００３４】
主演算制御手段１１でコンピュータプログラムが動作することにより、主演算制御手段１１は遅延ノード分割部２１、依存関係追加部２２、隠れ依存関係追加部２３、および実行順序決定部２４といった各機能部として動作する。そして、これらの機能部は、記憶手段に記憶された処理前データフローグラフ３１に対して後述の処理を行い、処理の完了した処理後データフローグラフ３３を記憶手段１２に記憶する。以下、遅延ノード分割部２１、依存関係追加部２２、および隠れ依存関係追加部２３の各々の動作について説明する。実行順序決定部２４の動作については後述する。
【００３５】
（遅延ノード分割部）
図２は、図１に示した遅延ノード分割部２１による処理の概念について示す説明図である。図２（ａ）には遅延ノード分割部２１に対して入力される処理前データフローグラフ３１の例を、図２（ｂ）には遅延ノード分割部２１から出力される第１の処理中データフローグラフ３２ａの例を、各々示している。
【００３６】
図２（ａ）に示した例では、処理前データフローグラフ３１は、ノードＡ１〜Ａ８の８つのノードで構成されている。それらの中で、ノードＡ７およびＡ８が遅延ノードに該当する。遅延ノードは、入力データを直接出力せずに記憶し、次のイタレーションで出力する。即ち、遅延ノードが出力する値は過去のイタレーションで当該遅延ノードが記憶した値であり、現在のイタレーションでの入力値は現在の出力値の計算には使われない。
【００３７】
このため、遅延ノード分割部２１は、遅延ノードであるノードＡ７およびＡ８を各々、当該遅延ノードが保持する過去のイタレーションの値を出力する「値出力ノード」と、当該遅延ノードへ現在のイタレーションの値を記憶させる「値更新ノード」に分割する。ノードＡ７は、遅延ノード分割部２１によって値更新ノードＡ７ｕおよび値出力ノードＡ７ｏに分割される。同様にノードＡ８も、遅延ノード分割部２１によって値更新ノードＡ８ｕおよび値出力ノードＡ８ｏに分割される。図２（ｂ）は、図２（ａ）に示した処理前データフローグラフ３１に対してこの遅延ノードの分割処理を行った結果を示している。
【００３８】
ノードＡ７を分割した後は、値更新ノードＡ７ｕと値出力ノードＡ７ｏはグラフ上では接続関係を持たないが、値更新ノードＡ７ｕと値出力ノードＡ７ｏは同一の内部状態（記憶データ）を共有している。値更新ノードＡ８ｕおよび値出力ノードＡ８ｏについても同様である。
【００３９】
そして、遅延ノードＡ７への入力エッジはノードＡ７ｕが、遅延ノードＡ７からの出力エッジはノードＡ７ｏがそれぞれ引き継ぐ。同様に、遅延ノードＡ８への入力エッジはノードＡ８ｕが、遅延ノードＡ８からの出力エッジはノードＡ８ｏが、それぞれ引き継ぐ。
【００４０】
図３は、図２に示した処理前データフローグラフ３１および第１の処理中データフローグラフ３２ａを対比して示す説明図である。ここに示した例では、遅延ノード分割部２１による処理の結果、第１の処理中データフローグラフ３２ａの中には、値出力ノードＡ７ｏ〜値更新ノードＡ８ｕのブロック３２ａ２が、第１の処理中データフローグラフ３２ａの中の残りの部分（ブロック３２ａ１）から孤立している。このような状態が、ここでいう「グラフの分裂」である。
【００４１】
元々、全てのノードが１つにつながっていた処理前データフローグラフ３１が、遅延ノード分割部２１による処理によって、第１の処理中データフローグラフ３２ａはブロック３２ａ１とブロック３２ａ２の２つのブロックに分かれた。このようなグラフの分裂が発生しても、ノードＡ７ｕ（ブロック３２ａ１）が記憶した値は将来のイタレーションでノードＡ７ｏ（ブロック３２ａ２）が使用し、ノードＡ８ｕ（ブロック３２ａ２）が記憶した値は将来のイタレーションでノードＡ８ｏ（ブロック３２ａ１）が使用するという、グラフやイタレーションを超えた依存関係は存在している。
【００４２】
以上で説明したノード分割部２１の動作は、背景技術の欄で説明した遅延ノード分割部９２１の動作と同一である。ここで説明したように、データフローグラフの遅延ノードを分割するだけだと、グラフの分裂が発生する場合がある。グラフの分裂が発生すると、分裂したデータフローグラフの相互間の依存関係が不明であるので、データフローグラフの各ノードをパイプライン的に繰り返し動作させることが困難となる。
【００４３】
（依存関係追加部および隠れ依存関係追加部）
本実施形態では、その点を解決して、データフローグラフの各ノードをパイプライン的に繰返し動作させることを容易なものとするため、ノード分割部２１の他に、図１に示した依存関係追加部２２および隠れ依存関係追加部２３を備えている。
【００４４】
図４は、図１に示したノード分割部２１、依存関係追加部２２および隠れ依存関係追加部２３の各々の動作について示すフローチャートと、各段階の処理の概念について示す説明図である。図４（ａ）にはノード分割部２１、依存関係追加部２２および隠れ依存関係追加部２３の各々の動作について示すフローチャートを、図４（ｂ）には各段階の処理の概念について各々示している。図４（ａ）では、処理前データフローグラフ３１上に存在する特定の遅延ノードＣ１について、その処理に伴う変化を示す。
【００４５】
処理前データフローグラフ３１が入力されたノード分割部２１は、図２〜図３に説明したように、遅延ノードＣ１を値更新ノードＣ２と値出力ノードＣ３に分割する動作を行い、第１の処理中データフローグラフ３２ａを出力する（ステップＳ１０１）。
【００４６】
これに続いて、依存関係追加部２２が、第１の処理中データフローグラフ３２ａに対して開始ノードＣ４から値出力ノードＣ３への依存関係（エッジ）を追加する処理を行い、第２の処理中データフローグラフ３２ｂを出力する（ステップＳ１０２）。
【００４７】
ここで、開始ノードＣ４とは、処理対象のデータフローグラフにおいて、全てのノードの処理の起点となるノードである。依存関係追加部２２は、開始ノードＣ４から値出力ノードＣ３へのエッジを追加することによって、値出力ノードＣ３がもとのデータフローグラフから孤立することを防ぐとともに、値出力ノードＣ３は開始ノードＣ４の直後に実行可能であることを明示するものである。
【００４８】
最後に、隠れ依存関係追加部２３が、第２の処理中データフローグラフ３２ｂに対して値更新ノードＣ２から値出力ノードＣ３へ隠れ依存関係（破線エッジ）を追加する処理を行い、処理後データフローグラフ３３を出力する（ステップＳ１０３）。ここでいう隠れ依存関係とは、第Ｎ回目のイタレーションから第Ｎ＋１回目のイタレーションに至るイタレーションの相互間の依存関係を表すものである。
【００４９】
実行順序決定部２４は、隠れ依存関係の破線エッジを通常のエッジとはみなさず、同一のイタレーションにおける値更新ノードＣ２から値出力ノードＣ３への依存関係は無いもとみなす。同時に、データフローグラフ処理装置１０は、データフローグラフ上で、ひとつのイタレーションの中での各ノードの実行順序を決める際には、隠れ依存関係を無視する。そして、実行順序決定部２４は、ノードが実行可能か否かを判定する場合には、隠れ依存関係を含む全ての依存関係を使用する。これについて詳しくは後述する。
【００５０】
（遅延ノードを１個のみ含むデータフローグラフの処理例）
以下、データフローグラフ処理装置１０が実際に行う処理の内容について実例を挙げて説明する。図５〜６は、図１に示したデータフローグラフ処理装置１０で、遅延ノードを１個のみ含む処理前データフローグラフ６１を処理した例を示す説明図である（紙面の都合で２頁に分けて示す）。データフローグラフ６１は、ノードＤ１〜Ｄ８の８個のノードで構成され、その中でノードＤ２〜Ｄ５およびＤ７で構成されるループ構造がある。そして、ノードＤ４が遅延ノードである。
【００５１】
この処理前データフローグラフ６１が入力されたノード分割部２１は、遅延ノードであるノードＤ４を値更新ノードＤ４ｕおよび値出力ノードＤ４ｏに分割し、遅延ノードＤ４への入力エッジを値更新ノードＤ４ｕに、遅延ノードＤ４からの出力エッジを値出力ノードＤ４ｏに、それぞれ引き継ぐ（図４・ステップＳ１０１）。この処理結果が、図５に示す第１の処理中データフローグラフ６２ａである。
【００５２】
これに続いて、依存関係追加部２２が、第１の処理中データフローグラフ６２ａに対して開始ノードＤ８から値出力ノードＤ４ｏへの依存関係（エッジ）を追加する（ステップＳ１０２）。この処理結果が、図５に示す第２の処理中データフローグラフ６２ｂである。
【００５３】
最後に、隠れ依存関係追加部２３が、第２の処理中データフローグラフ６２ｂに対して値更新ノードＤ４ｕから値出力ノードＤ４ｏへ隠れ依存関係（破線エッジ）を追加する（ステップＳ１０３）。この処理結果が、図６に示す処理後データフローグラフ６３である。
【００５４】
隠れ依存関係を無視すると、処理後データフローグラフ６３にはループ構造が存在しないことがわかる。実行順序決定部２４は、各ノードの実行順序を決める際に、隠れ依存関係（破線エッジ）を無視し、通常の依存関係だけを使用する。そして、実行順序決定部２４は、各ノードの実行を開始可能か否かを判断するために、隠れ依存関係（破線エッジ）を含む全ての依存関係を使用する。各ノードの実行順序の決定、および各ノードの実行を開始可能か否かの判断については後述する。
【００５５】
（遅延ノードを複数個含むデータフローグラフの処理例）
図７〜８は、図１に示したデータフローグラフ処理装置１０で、遅延ノードを複数個含む処理前データフローグラフ７１を処理した例を示す説明図である（紙面の都合で２頁に分けて示す）。データフローグラフ７１は、ノードＥ１〜Ｅ９の９個のノードで構成され、その中でノードＥ２〜Ｅ５およびＥ７〜Ｅ８で構成されるループ構造がある。そして、ノードＥ７およびＥ８が遅延ノードである。
【００５６】
この処理前データフローグラフ７１が入力されたノード分割部２１は、遅延ノードであるノードＥ７およびＥ８を各々値更新ノードＥ７ｕと値出力ノードＥ７ｏ、および値更新ノードＥ８ｕと値出力ノードＥ８ｏに分割し、遅延ノードＥ７への入力エッジを値更新ノードＥ７ｕに、遅延ノードＥ７からの出力エッジを値出力ノードＥ７ｏに各々引き継ぐ。また、遅延ノードＥ８への入力エッジを値更新ノードＥ８ｕに、遅延ノードＥ８からの出力エッジを値出力ノードＥ８ｏに各々引き継ぐ（図４・ステップＳ１０１）。この処理結果が、図８に示す第１の処理中データフローグラフ７２ａである。
【００５７】
これに続いて、依存関係追加部２２が、第１の処理中データフローグラフ７２ａに対して開始ノードＥ９から値出力ノードＥ７ｏおよびＥ８ｏへの依存関係（エッジ）を追加する（ステップＳ１０２）。この処理結果が、図８に示す第２の処理中データフローグラフ７２ｂである。
【００５８】
最後に、隠れ依存関係追加部２３が、第２の処理中データフローグラフ７２ｂに対して値更新ノードＥ７ｕから値出力ノードＥ７ｏへ、そして値更新ノードＥ８ｕから値出力ノードＥ８ｏへ各々隠れ依存関係（破線エッジ）を追加する（ステップＳ１０３）。この処理結果が、図８に示す処理後データフローグラフ７３である。
【００５９】
隠れ依存関係を無視すると、処理後データフローグラフ７３にはループ構造が存在しないことがわかる。実行順序決定部２４は、各ノードの実行順序を決める際に、隠れ依存関係（破線エッジ）を無視し、通常の依存関係だけを使用する。そして、実行順序決定部２４は、各ノードの実行を開始可能か否かを判断するために、隠れ依存関係（破線エッジ）を含む全ての依存関係を使用する。各ノードの実行順序の決定、および各ノードの実行を開始可能か否かの判断については後述する。
【００６０】
（実行順序の決定および実行可否の判断）
図９は、図１に示した実行順序決定部２４による各ノードの実行順序の決定および実行可否の判断の動作について示すフローチャートである。図１に示した実行順序決定部２４は、隠れ依存関係追加部２３が出力した処理後データフローグラフ３３に対して、各ノードの実行順序を決定し（ステップＳ２０１）、各ノードの実行が開始可能であるか否かを判断する（ステップＳ２０２）。
【００６１】
ステップＳ２０１で、実行順序決定部２４が各ノードの実行順序を決定する際には、処理後データフローグラフ３３上に隠れ依存関係（破線エッジ）がある場合にはそれを無視し、開始ノードを始点として幅優先探索あるいは深さ優先探索を行い、各ノードに相異なる番号を割り当てる。このようにして割り当てられた番号をノードの実行順序とする。前述したように、隠れ依存関係（破線エッジ）を無視しさえすれば、処理後データフローグラフ３３にはループ構造が存在しないので、このような処理が容易なものとなる。
【００６２】
ステップＳ２０２で、実行順序決定部２４が各ノードの実行を開始可能か否かを判断する際には、処理後データフローグラフ３３上の全てのノードについて、あるノードにつながる隠れ依存関係（破線エッジ）を含む全ての入力エッジの処理が完了している場合に、そのノードが実行可能とする。ちなみに、各ノードの実行が完了したことは、依存関係をもつノードからノードへシグナルとして伝えられる。また、開始ノードは入力エッジを持たないので、ユーザからの実行開始指令を受けさえすれば、常に実行可能である。
【００６３】
図１０は、図６および図８に示した処理後データフローグラフ６３および７３に対して、実行順序決定部２４が実行順序を決定した結果を示す説明図である。図１０（ａ）には実行順序決定の処理前データフローグラフ６３、図１０（ｂ）には実行順序決定の処理後データフローグラフ７３を、各々示している。実行順序はノードごとに番号で示すこととする。
【００６４】
処理後データフローグラフ６３については、まず開始ノードＤ８を実行順序「１」とする。開始ノードＤ８からは、ノードＤ１およびＤ４ｏに依存関係の実線エッジがつながっているので、ノード間で順序が重複しないよう、ノードＤ１を実行順序「２」、ノードＤ４ｏを実行順序「３」とする。もちろん、ノードＤ１およびＤ４ｏで実行順序を逆にしてもよい。
【００６５】
ここで、ノードＤ１からノードＤ２に依存関係の実線エッジがつながっているが、ノードＤ２にはこれの他にノードＤ７からの入力エッジもあるので、ノードＤ２はここではまだ実行されない。従って、ノードＤ４ｏから実線エッジがつながっているノードＤ５のみが実行され、実行順序「４」となる。
【００６６】
ノードＤ５にはノードＤ６およびＤ７に依存関係の実線エッジがつながっているので、先ほどと同様にノード間で順序が重複しないよう、ノードＤ６およびＤ７が各々実行順序「５」および「６」となる。ここで先ほどのノードＤ２は、ノードＤ７からの入力エッジの処理が完了して実行可能となり、実行順序「７」となる。
【００６７】
以後これらと同様に、ノードＤ３が実行順序「８」、ノードＤ４ｕが実行順序「９」となる。ここまでで処理後データフローグラフ６３の全てのノードが実行されたことになり、実行不可能なノードは存在しないことがわかる。
【００６８】
処理後データフローグラフ７３についても同様に、まず開始ノードＥ８を実行順序「１」とする。開始ノードＥ８からは、ノードＥ１、Ｅ８ｏ、およびＥ７ｏに依存関係の実線エッジがつながっているので、これらを各々実行順序「２」「３」「４」とする。
【００６９】
ノードＥ１およびＥ８ｏからはノードＥ２に依存関係の実線エッジがつながっており、またこれと同様にノードＥ７ｏからはノードＥ８ｕに実線エッジがつながっているので、これらノードＥ２およびノードＥ８ｕを各々実行順序「５」および「６」とする。ここで、ノードＥ２につながっているノードＥ１およびＥ８ｏからの入力エッジの処理は実行順序「３」までで完了しているので、ノードＥ２はここで実行可能である。
【００７０】
以後これらと同様に、ノードＥ３が実行順序「７」、ノードＥ４が実行順序「８」、ノードＥ５が実行順序「９」、そしてノードＥ７ｕおよびＥ６が実行順序「１０」および「１１」となり、ここまでで処理後データフローグラフ７３の全てのノードが実行されたことになり、実行不可能なノードは存在しないことがわかる。
【００７１】
（第１の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係るデータフローグラフ処理方法は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し（図４・ステップＳ１０１）、データフローグラフの開始ノードから値出力ノードへの依存関係を追加し（図４・ステップＳ１０２）、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前期値更新ノードから前期値出力ノードへ追加する（図４・ステップＳ１０３）。そして、隠隠れ依存関係が追加されたデータフローグラフを利用して実行順序を決定する（図９・ステップＳ２０１〜２０２）。
【００７２】
また、実行順序の決定および実行可否の判断を実行順序決定部が行う処理で、各ノードの実行順序を決定する際には、隠れ依存関係が追加されたデータフローグラフから隠れ依存関係を無視し（図９・ステップＳ２０１）、データフローグラフの各ノードがある時点で実行可能であるか否かを判断する際には、隠れ依存関係が追加されたデータフローグラフの隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断する（図９・ステップＳ２０２）。
【００７３】
ここで、上記各動作ステップについては、これをコンピュータで実行可能なプログラムとして構成し、前記各ステップをパーソナルコンピュータ１０に実行させるようにしてもよい。本プログラムは、非一時的な記録媒体、例えば、ＤＶＤ、ＣＤ、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。
この動作により、本実施形態は以下のような効果を奏する。
【００７４】
本実施形態では、遅延ノードを分割して値出力ノードと値更新ノードに分割した場合に、その値出力ノードは開始ノードの直後に実行可能であることを利用して、開始ノードから依存関係の実線エッジを追加した。そして、分割された値出力ノードと値更新ノードとの間の関係を、イタレーションの相互間の依存関係を示す「隠れ依存関係」として示した。
【００７５】
従って、背景技術の欄で説明したような、遅延ノードの分割によるグラフの分裂は、ここでは発生し得ない。また、実行順序については隠れ依存関係を無視して、依存関係にのみ基づいて決定できる。かつ、実行可否の判断は、隠れ依存関係を含めた全ての依存関係を利用して判断できる。
【００７６】
本明細書では、本実施形態の装置もしくは方法によって、１つもしくは２つの遅延ノードをもつデータフローグラフを処理する場合の例を示したが、本実施形態では任意の数の遅延ノードを含むデータフローグラフを処理することが可能である。また、本実施形態では、遅延ノードの数についてだけでなく、その位置についても特に制限はない。
【００７７】
これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。
【００７８】
上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
【００７９】
（付記１）  入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部と、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する依存関係追加部と、
前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する隠れ依存関係追加部と
を有することを特徴とするデータフローグラフ処理装置。
【００８０】
（付記２）  前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序の決定を行う実行順序決定部を有することを特徴とする、付記１に記載のデータフローグラフ処理装置。
【００８１】
（付記３）  前記実行順序決定部は、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、付記１に記載のデータフローグラフ処理装置。
【００８２】
（付記４）  入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加し、
前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前期値更新ノードから前期値出力ノードへ追加する
ことを特徴とするデータフローグラフ処理方法。
【００８３】
（付記５）  前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序を決定することを特徴とする、付記４に記載のデータフローグラフ処理方法。
【００８４】
（付記６）  前記実行順序を決定する処理で、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
前記データフローグラフの各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、付記５に記載のデータフローグラフ処理方法。
【００８５】
（付記７）  入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する手順、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する手順、
および、前記値更新ノードから前記値出力ノードへ、前回のイタレーションから今回のイタレーションへの依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する手順、
をコンピュータに実行させることを特徴とするデータフローグラフ処理プログラム。
【００８６】
（付記８）  前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序を決定する手順を前記コンピュータに実行させることを特徴とする、付記７に記載のデータフローグラフ処理プログラム。
【００８７】
（付記９）  前記実行順序の決定および実行可否の判断を行う手順で、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
前記データフローグラフの各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、付記８に記載のデータフローグラフ処理プログラム。
【００８８】
この出願は２０１１年２月１日に出願された日本出願特願２０１１−０２０２１６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００８９】
コンピュータプログラムの並列化、そしてこれによるコンピュータプログラムのマルチコアプロセッサ（もしくはマルチスレッドプロセッサなど）への対応化に適用できる。
【符号の説明】
【００９０】
１０  データフローグラフ処理装置
１１  主演算制御手段
１２  記憶手段
１３  入出力手段
２１  遅延ノード分割部
２２  依存関係追加部
２３  隠れ依存関係追加部
２４  実行順序決定部
３１、６１、７１  処理前データフローグラフ
３２ａ、３２ｂ、６２ａ、６２ｂ、７２ａ、７２ｂ  処理中データフローグラフ
３２ａ１、３２ａ２  ブロック
３３、６３、７３  処理後データフローグラフ
【図１】
2012105593.tif 000003
【図２】
2012105593.tif 000004
【図３】
2012105593.tif 000005
【図４】
2012105593.tif 000006
【図５】
2012105593.tif 000007
【図６】
2012105593.tif 000008
【図７】
2012105593.tif 000009
【図８】
2012105593.tif 000010
【図９】
2012105593.tif 000011
【図１０】
2012105593.tif 000012
【図１１】
2012105593.tif 000013
【図１２】
2012105593.tif 000014
【図１３】
2012105593.tif 000015
【図１４】
2012105593.tif 000016
【手続補正書】
【提出日】平成25年8月1日(2013.8.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部と、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する依存関係追加部と、
前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する隠れ依存関係追加部と
を有することを特徴とするデータフローグラフ処理装置。
【請求項２】
前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序の決定を行う実行順序決定部を有することを特徴とする、請求項１に記載のデータフローグラフ処理装置。
【請求項３】
前記実行順序決定部は、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、請求項２に記載のデータフローグラフ処理装置。
【請求項４】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加し、
前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する
ことを特徴とするデータフローグラフ処理方法。
【請求項５】
前記隠れ依存関係が追加された前記データフローグラフを利用して前記実行順序を決定することを特徴とする、請求項４に記載のデータフローグラフ処理方法。
【請求項６】
前記実行順序を決定する処理で、
各ノードの実行順序を決定する際には、前記隠れ依存関係が追加された前記データフローグラフから前記隠れ依存関係を無視し、
前記データフローグラフの各ノードがある時点で実行可能であるか否かを判断する際には、前記隠れ依存関係が追加された前記データフローグラフの前記隠れ依存関係を含めた全ての依存関係にもとづいて実行可能か否かを判断することを特徴とする、請求項５に記載のデータフローグラフ処理方法。
【請求項７】
入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する手順、
前記データフローグラフの開始ノードから前記値出力ノードへの依存関係を追加する手順、
および、前記値更新ノードから前記値出力ノードへ、前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を前記値更新ノードから前記値出力ノードへ追加する手順、
をコンピュータに実行させることを特徴とするデータフローグラフ処理プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
上記目的を達成するため、本発明に係るデータフローグラフ処理装置は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する遅延ノード分割部と、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加する依存関係追加部と、前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する隠れ依存関係追加部を有することを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
上記目的を達成するため、本発明に係るデータフローグラフ処理方法は、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割し、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加し、前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加することを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
上記目的を達成するため、本発明に係るデータフローグラフ処理プログラムは、入力データフローグラフに含まれる遅延ノードを値更新ノードと値出力ノードに分割する手順、入力データフローグラフの開始ノードから値出力ノードへの依存関係を追加する手順、および前記データフローグラフに対応する計算のｎ回目の実行から当該計算のｎ＋１回目の実行への依存関係を示す隠れ依存関係を値更新ノードから値出力ノードへ追加する手順、をコンピュータに実行させることを特徴とする。
【国際調査報告】
2012105593.tif 000017
2012105593.tif 000018
2012105593.tif 000019
2012105593.tif 000020