(57)【要約】【課題】複数アプリケーションを考慮した用意すべきデータパス回路の機能を自動的に決定することのできる共通データフロー抽出システムを得る。【解決手段】アプリケーションａのデータフロー記述２ａとアプリケーションｂのデータフロー記述２ｂを解析して比較し、これら複数のアプリケーションのデータフロー記述間で共通に存在するデータフロー記述を抽出し、共通データフロー３として出力する共通データフロー抽出手段１を設ける。【選択図】図１
2010262359.tif 000002
【特許請求の範囲】
【請求項１】
複数のアプリケーションのデータフロー記述を解析して比較し、これら複数のアプリケーションのデータフロー記述間で共通に存在するデータフロー記述を抽出し、当該共通に存在するデータフロー記述を出力する共通データフロー抽出手段を備えたことを特徴とする共通データフロー抽出システム。
【請求項２】
Ｃ言語またはＲＴＬ言語による複数のアプリケーション動作記述を解析し、データフロー記述に展開するデータフロー展開手段を備え、共通データフロー抽出手段は、前記データフロー展開手段で展開された前記複数のアプリケーションのデータフロー記述を解析することを特徴とする請求項１記載の共通データフロー抽出システム。
【請求項３】
共通データフロー抽出手段は、
複数のアプリケーションのデータフロー記述の最終点を起点として演算段数毎に演算種類を比較するデータフロー比較部と、
前記データフロー比較部で、予め定めた目標段数分の一致段数が得られた場合に、当該目標段数のデータフロー記述部分を共通データフローとして抽出する共通データフロー抽出部とを備えたことを特徴とする請求項１または請求項２記載の共通データフロー抽出システム。
【請求項４】
請求項１から請求項３のうちのいずれか１項記載の共通データフロー抽出システムにおける共通に存在するデータフロー記述を抽出する共通データフロー抽出方法であって、
抽出する共通データフローの目標深さ段数を設定し、共通データフロー抽出対象である複数のアプリケーションのデータフロー記述のそれぞれの深さを計測し、前記複数のアプリケーションのデータフローのうち最も深さが小さいアプリケーションのデータフローを基準データフローとし、当該基準データフローの深さが前記目標深さ段数よりも小さい場合は、当該目標深さ段数を前記基準データフローの深さの値に変更するステップと、
一致段数を初期化後、前記複数のアプリケーションのデータフローの最終点を起点とし、それぞれのデータフローを一段ずつさかのぼりながら演算種類の一致／不一致を判定し、一致の場合は前記一致段数をカウントアップして引き続き一段データフローをさかのぼって判定を継続し、不一致の場合は一致段数を０にリセットして前記基準データフローではないデータフローの起点を一段上にずらして新たに判定を開始するステップと、
前記一致段数が前記目標深さ段数に達した場合は、一致したデータフロー部分を共通データフローとして抽出するステップと、
前記一致段数が前記目標深さ段数に達する前に前記基準データフローではないデータフローの最上段まで判定が終了した場合は、前記一致段数を０にリセットして前記基準データフローの起点を一段上にずらして新たに判定を開始するステップと、
前記一致段数が前記目標深さ段数に達する前に基準データフローの最上段まで判定が終了した場合は、前記一致段数を０にリセットして前記目標深さ段数を１減らして、再度各データフローの最終点を起点として判定を行うステップとを備えたことを特徴とする共通データフロー抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のアプリケーションのデータフロー記述から、共通に存在するデータフロー記述を抽出して出力する共通データフロー抽出システムおよび共通データフロー抽出方法に関する。
【背景技術】
【０００２】
単一の回路上で回路構成を切り替えながら複数種類のアプリケーションを実現するプラットフォーム回路や動的再構成回路では、汎用性の高すぎるデータパスを用いると充分な性能がでなかったり、回路規模が膨大になりすぎたりする問題がある。そこで、実現する機能をある程度絞り、性能と回路規模の最適化を図ったデータパス回路を用いることで、この問題を解決する。
【０００３】
従来、このような回路に用いられる共通データフローの検出としては、例えば、特許文献１に記載されているものがあった。この検出装置は、ディジタル回路動作についてデータフローグラフ中、一または複数の条件分岐から一つの条件分岐を選択し、この条件分岐に含まれる節点集合をいくつかのグループに分け、分けられたグループのそれぞれをサブグラフとする処理を一または複数の条件分岐に対して行って複数のサブグラフを得る。そして、これら複数のサブグラフを比較して同一サブグラフを検出する。更に、データフローグラフ中の各条件分岐に含まれる節点を一定法則でグループに分けてそれぞれをサブグラフとし、それらサブグラフを比較することにより同一サブグラフを検出するものである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１３９４２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記従来のような共通データフローを検出するシステムは、単一プログラムのデータフロー内からサブグラフと呼ばれる同一の処理機能を検出するシステムであるため、複数種類のアプリケーションプログラムを入力とすることができず、複数アプリケーション間で共通に存在する機能処理の抽出ができないという問題があった。
【０００６】
この発明は、上記問題点を解決するためになされたもので、複数アプリケーションを考慮した用意すべきデータパス回路の機能を自動的に決定することのできる共通データフロー抽出システムおよび共通データフロー抽出方法を得ることを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る共通データフロー抽出システムは、複数のアプリケーションのデータフロー記述を解析して比較し、これら複数のアプリケーションのデータフロー記述間で共通に存在するデータフロー記述を抽出し、共通に存在するデータフロー記述を出力する共通データフロー抽出手段を備えたものである。
【発明の効果】
【０００８】
この発明の共通データフロー抽出システムは、複数のアプリケーションのデータフロー記述間で共通に存在するデータフロー記述を抽出して出力するようにしたので、複数アプリケーションを考慮した用意すべきデータパス回路の機能を自動的に決定することができ、プラットフォーム回路や動的再構成回路設計の効率化を図ることができる。
【図面の簡単な説明】
【０００９】
【図１】この発明の実施の形態１による共通データフロー抽出システムを示す構成図である。
【図２】この発明の実施の形態１による共通データフロー抽出システムにおける共通データフロー例と共通データフロー抽出結果を用いた回路例を示す説明図である。
【図３】この発明の実施の形態２による共通データフロー抽出システムを示す構成図である。
【図４】この発明の実施の形態３による共通データフロー抽出システムの共通データフロー抽出手段の構成図である。
【図５−１】この発明の実施の形態３による共通データフロー抽出方法を示すフローチャート（その１）である。
【図５−２】この発明の実施の形態３による共通データフロー抽出方法を示すフローチャート（その２）である。
【図５−３】この発明の実施の形態３による共通データフロー抽出方法を示すフローチャート（その３）である。
【図５−４】この発明の実施の形態３による共通データフロー抽出方法を示すフローチャート（その４）である。
【図５−５】この発明の実施の形態３による共通データフロー抽出方法を示すフローチャート（その５）である。
【図６】この発明の実施の形態３による共通データフロー抽出システムにおけるアプリケーションａのデータフロー展開例の説明図である。
【図７】この発明の実施の形態３による共通データフロー抽出システムにおけるアプリケーションｂのデータフロー展開例の説明図である。
【図８】この発明の実施の形態３による共通データフロー抽出システムにおける共通データフロー抽出例の説明図である。
【発明を実施するための形態】
【００１０】
実施の形態１．
図１は、この発明の実施の形態１による共通データフロー抽出システムの構成図である。
図示の共通データフロー抽出システムは、共通データフロー抽出手段１を備えている。この共通データフロー抽出手段１は、入力されるアプリケーションａのデータフロー記述２ａとアプリケーションｂのデータフロー記述２ｂを解析して両者を比較し、アプリケーションａとアプリケーションｂとで共通するデータフロー部分を共通データフロー３として出力する手段である。データフローを記述する言語は、データフローを表現できる言語であれば、種類は問わない。また、ここでは二つのアプリケーションのデータフローを入力する例を示したが、三つ以上でもよい。
【００１１】
図２は、実施の形態１の共通データフロー抽出システムによって抽出される共通データフローの例（図中（ａ）に示す）と、この共通データフロー抽出結果を用いて構成した回路構成の例（図中（ｂ）に示す）である。
図２（ａ）において、アプリケーションａのデータフロー記述２ａと、アプリケーションｂのデータフロー記述２ｂを共通データフロー抽出手段１に入力した結果、アプリケーションａのデータフロー記述２ａとアプリケーションｂのデータフロー記述２ｂに共通するデータフローとして、共通データフロー（Ａ）３が抽出されたものとする。これにより、図２（ｂ）において、共通データフロー（Ａ）は共通ブロック（Ａ）６として１ブロックのみ設け、図２（ａ）において共通データフローとして抽出されなかった残りのデータフロー（Ｂ），（Ｃ）および（Ｄ）については、図２（ｂ）において共通化はされずに、それぞれ、ブロック（Ｂ）７、ブロック（Ｃ）８およびブロック（Ｄ）９として設けるような構成例が考えられる。尚、これら共通ブロック（Ａ）６とその他のブロック（Ｂ）〜（Ｄ）は接続手段１０によって相互に接続されている。
【００１２】
以上のように、実施の形態１の共通データフロー抽出システムによれば、複数のアプリケーションのデータフロー記述を解析して比較し、これら複数のアプリケーションのデータフロー記述間で共通に存在するデータフロー記述を抽出し、共通に存在するデータフロー記述を出力する共通データフロー抽出手段１を備えたので、複数アプリケーションを考慮した用意すべきデータパス回路の機能を自動的に決定することができ、動的再構成回路やプラットフォーム回路など、複数アプリケーションを同一回路上で動作させる回路のアーキテクチャ検討を効率化することが可能となる。
【００１３】
実施の形態２．
図３は、この発明の実施の形態２による共通データフロー抽出システムを示す構成図である。
図において、アプリケーションａの動作記述４ａおよびアプリケーションｂの動作記述４ｂは、ＣプログラムやＲＴＬ記述等で記述された動作記述である。データフロー展開手段５ａ，５ｂは、複数のアプリケーション動作記述を解析し、データフロー記述に展開する手段である。共通データフロー抽出手段１以降の構成は実施の形態１と同様である。
【００１４】
アプリケーションａの動作記述４ａおよびアプリケーションｂの動作記述４ｂは、それぞれ、データフロー展開手段５ａおよび５ｂに入力され、データフロー展開手段５ａ，５ｂは、それぞれ、アプリケーションａのデータフロー記述２ａおよびアプリケーションｂのデータフロー記述２ｂに展開する。
共通データフロー抽出手段１は、データフロー展開手段５ａ，５ｂで展開されたアプリケーションａのデータフロー記述２ａとアプリケーションｂのデータフロー記述２ｂを解析して両者を比較し、アプリケーションａとアプリケーションｂとで共通するデータフロー部分を共通データフロー３として出力する。尚、出力される共通データフロー３は、この共通データフロー抽出システムに入力された動作記述と同様のＣプログラムやＲＴＬ記述か、あるいは、データフロー記述でもよい。また、ここでは二つのアプリケーションの動作記述を入力する例を示したが、三つ以上でもよい。
【００１５】
また、上記共通データフロー抽出システムにおいて、入力するアプリケーションの動作記述をＣ言語とし、上記共通データフロー抽出システムの出力をＲＴＬ記述としてもよい。
また、上記共通データフロー抽出システムにより抽出した共通データフローを、ソフトウェアコンパイラにおいて基本演算を定義するファイル形式として出力すれば、上記共通データフローを共通データパス回路として実装している動的再構成回路やプラットフォーム回路のためのソフトウェアコンパイラ生成の効率化を図ることも可能である。
【００１６】
以上のように、実施の形態２の共通データフロー抽出システムによれば、Ｃ言語またはＲＴＬ言語による複数のアプリケーション動作記述を解析し、データフロー記述に展開するデータフロー展開手段を備え、共通データフロー抽出手段は、データフロー展開手段で展開された複数のアプリケーションのデータフロー記述を解析するようにしたので、Ｃ言語やＲＴＬ言語による複数のアプリケーション動作記述に対しても、その共通データフローを抽出することができる。
【００１７】
実施の形態３．
実施の形態３の共通データフロー抽出システムは、実施の形態１または２における共通データフロー抽出手段１をデータフロー比較部と共通データフロー抽出部を用いて構成したものである。
図４は、実施の形態３の共通データフロー抽出システムにおける共通データフロー抽出手段の構成図である。
図において、共通データフロー抽出手段は、第１入力部１０１ａ、第２入力部１０１ｂ、データフロー比較部１０２、共通データフロー抽出部１０３、目標深さ段数記憶部１０４、一致段数記憶部１０５を備えている。また、データフロー比較部１０２は、基準データフロー深さ段数記憶部１０２ａと、非基準データフロー深さ段数記憶部１０２ｂとを有している。ここで、共通データフロー抽出手段１はコンピュータを用いて実現され、データフロー比較部１０２および共通データフロー抽出部１０３は、それぞれの機能に対応したソフトウェアと、これを実行するためのＣＰＵやメモリ等のハードウェアから構成されている。あるいは、データフロー比較部１０２や共通データフロー抽出部１０３を専用のハードウェアで構成してもよい。
【００１８】
第１入力部１０１ａおよび第２入力部１０１ｂは、例えば、図１〜図３に示したアプリケーションａのデータフロー記述２ａやアプリケーションｂのデータフロー記述２ｂのように、比較対象とするデータフローの入力部である。尚、ここでは二つのアプリケーションのデータフロー記述に対して二つの入力部としたが、三つ以上のデータフロー記述に対しては三つ以上の入力部としてもよい。データフロー比較部１０２は、複数のアプリケーションのデータフロー記述の最終点を起点として演算段数毎に演算種類を比較する機能を有している。基準データフロー深さ段数記憶部１０２ａは、基準データフローとなるデータフローの深さ段数の値を保持し、非基準データフロー深さ段数記憶部１０２ｂは、非基準データフローとなるデータフローの深さ段数の値を保持する記憶部である。共通データフロー抽出部１０３は、データフロー比較部１０２で、予め定めた目標段数分の一致段数が得られた場合に、目標段数のデータフロー記述部分を共通データフローとして抽出する機能を有している。目標深さ段数記憶部１０４は、外部から設定されるか、あるいは初期値として予め設定される目標段数の値を保持する記憶部である。一致段数記憶部１０５は、データフロー比較部１０２での比較の結果、一致した段数の値を保持する記憶部である。
【００１９】
次に、実施の形態３の共通データフロー抽出システムの動作について説明する。
図５−１〜図５−５は、実施の形態３の共通データフロー抽出システムによる共通データフロー抽出方法を示すフローチャートである。
＜ステップＳＴ１＞共通データフローの目標深さ段数を設定する。この目標深さ段数の値は目標深さ段数記憶部１０４に記憶される。
＜ステップＳＴ２＞データフロー比較部１０２は、第１，第２入力部１０１ａ，１０１ｂより入力された複数ある抽出対象データフローの深さ段数を測る。
＜ステップＳＴ３＞上記ステップＳＴ２で求めた複数の抽出データフローの深さ段数のうち、最小深さ段数であるデータフローを基準データフローとして、その深さ段数の値を基準データフロー深さ段数記憶部１０２ａで保持する。また、他方のデータフローを非基準データフローとしてその深さ段数の値を非基準データフロー深さ段数記憶部１０２ｂに保持する。
＜ステップＳＴ４ａ，ＳＴ４ｂ＞データフロー比較部１０２は、ステップＳＴ１で設定した目標深さ段数と、ステップＳＴ３で求めた基準データフローの深さ段数を比較し、目標深さ段数の方が大きければ、目標深さ段数の値を基準データフローの深さ段数の値に変更する。即ち、目標深さ段数記憶部１０４の値を基準データフロー深さ段数記憶部１０２ａの深さ段数の値で変更する。一方、基準データフローの深さ段数が目標深さ段数以上であれば、変更しない。
【００２０】
＜ステップＳＴ５ａ，ＳＴ５ｂ＞目標深さ段数が０より大きければ、基準データフローの起点をデータフローの最下点、即ち、データフローの最終演算子に設定する。これは、基準データフローの起点段番号を０に設定することと等しい。一方、目標深さ段数が０であれば、共通データフローが抽出されなかったものとして処理を終了する。
＜ステップＳＴ６ａ，ＳＴ６ｂ＞“基準データフローの深さ段数−目標深さ段数”が“基準データフローの起点段番号”以上であれば、非基準データフローの起点を最下点に設定、即ち、非基準データフローの起点段番号を０に設定する。一方、“基準データフローの深さ段数−目標深さ段数”が“基準データフローの起点段番号”より小さければ、現“目標深さ段数”の共通データフローは抽出されなかったものとして、ステップＳＴ１８の処理に移る。
【００２１】
データフロー比較部１０２は、比較を開始する前の前処理として、次のステップＳＴ７〜ステップＳＴ１０を実行する。
＜ステップＳＴ７ａ，ＳＴ７ｂ＞“非基準データフローの深さ段数−目標深さ段数”が“非基準データフローの起点段番号”以上であれば、一致段数記憶部１０５の一致段数を０にリセットする。一方、“非基準データフローの深さ段数−目標深さ段数”が“非基準データフローの起点段番号”より小さければ、現基準データフローの起点では共通データフローが抽出されなかったものとして、ステップＳＴ１７の処理に移る。
＜ステップＳＴ８＞比較段数を０にリセットする。
＜ステップＳＴ９＞基準データフローの起点段を基準データフローの比較段に設定する。
＜ステップＳＴ１０＞非基準データフローの起点段を非基準データフローの比較段に設定する。
＜ステップＳＴ１１ａ，ＳＴ１１ｂ＞データフロー比較部１０２は、基準データフローの比較段と非基準データフローの比較段の演算種類を比較し、演算種類が一致するかを判定する。
＜ステップＳＴ１２ａ，ＳＴ１２ｂ＞ステップＳＴ１１の比較の結果、演算種類が一致するならば、一致段数記憶部１０５における一致段数をカウントアップする。結果、一致段数と目標深さ段数が等しくなると、共通データフロー抽出部１０３は、共通データフローが抽出されたものとしてこれを出力し、処理を終了する。一致段数が目標深さ段数に達していなければ、以下、データフロー比較部１０２は、ステップＳＴ１３からの処理を継続する。一方、演算種類が一致しないならば、ステップＳＴ１６の処理に移る。
【００２２】
＜ステップＳＴ１３＞基準データフローの比較段を１段さかのぼる。
＜ステップＳＴ１４＞非基準データフローの比較段を１段さかのぼる。
＜ステップＳＴ１５ａ，ＳＴ１５ｂ＞比較段数を１カウントアップする。比較段数が目標深さ段数に達したら、以下、ステップＳＴ１６からの処理を行う。一方、比較段数が目標深さ段数に達していなければ、ステップＳＴ１１〜ステップＳＴ１５の処理を繰り返す。
＜ステップＳＴ１６＞上記ステップＳＴ１５までの比較で共通データフローが抽出できなかったため、非基準データフローの起点を１段さかのぼる。即ち、非基準データフローの起点段番号を１カウントアップし、ステップＳＴ７〜ステップＳＴ１６を繰り返す。
＜ステップＳＴ１７＞上記ステップＳＴ１６までの比較、即ち、基準データフローの起点はそのままに、非基準データフローの起点を１段ずつさかのぼっての比較では共通データフローが抽出されなかったものとして、基準データフローの起点を１段さかのぼる。即ち、基準データフローの起点番号を１カウントアップする。
＜ステップＳＴ１８＞上記ステップＳＴ１７までの比較、即ち、現設定の目標深さ段数では共通データフローが抽出されなかったものとして、目標深さ段数を１カウントダウンし、再び、ステップＳＴ５〜ステップＳＴ１７の処理を繰り返す。
【００２３】
次に、共通データフロー抽出の具体例を説明する。
図６（ａ）はアプリケーションａのＣプログラム記述である。これを、データフロー展開手段５ａ（実施の形態２における図３参照）によってデータフロー展開したものが、図６（ｂ）のデータフローである。一方、図７（ａ）はアプリケーションｂのＣプログラム記述であり、同様にデータフロー展開手段５ｂによってデータフロー展開したものが、図７（ｂ）のデータフローである。上記アプリケーションａのデータフローとアプリケーションｂのデータフローに対し、実施の形態３の方法により共通データフロー抽出を実施した例が図８である。
【００２４】
＜ステップＳＴ１＞共通データフローの目標深さ段数を５段に設定する。
＜ステップＳＴ２＞抽出対象データフローであるアプリケーションａとアプリケーションｂのデータフローの深さ段数をそれぞれ測る。アプリケーションａの深さ段数は９段、アプリケーションｂの深さ段数は４段である。
＜ステップＳＴ３＞ステップＳＴ２で求めた複数の抽出データフローの深さ段数のうち、アプリケーションｂの深さ段数が最小であるため、アプリケーションｂのデータフローを基準データフローとする。
＜ステップＳＴ４ａ，ＳＴ４ｂ＞ステップＳＴ１で設定した目標深さ段数５段と、ステップＳＴ３で求めた基準データフローの深さ段数４段を比較し、目標深さ段数の方が大きいため、目標深さ段数の値を基準データフローの深さ段数４段に変更する。
【００２５】
＜ステップＳＴ５ａ，ＳＴ５ｂ＞目標深さ段数が４段と“０”より大きいため、基準データフローの起点をデータフローの最下点に設定する。
＜ステップＳＴ６ａ，ＳＴ６ｂ＞“基準データフローの深さ段数［４段］−目標深さ段数［４段］”が“基準データフローの起点段番号［０］”以上であるため、非基準データフローの起点を最下点に設定、即ち、非基準データフローの起点段番号を“０”に設定する。
＜ステップＳＴ７ａ，ＳＴ７ｂ＞“非基準データフローの深さ段数［９段］−目標深さ段数［４段］”が“非基準データフローの起点段番号［０］”以上であるため、一致段数を０にリセットする。
＜ステップＳＴ８＞比較段数を０にリセットする。
＜ステップＳＴ９＞基準データフローの起点段［０］を基準データフローの比較段に設定する。
＜ステップＳＴ１０＞非基準データフローの起点段［０］を非基準データフローの比較段に設定する。
＜ステップＳＴ１１ａ，ＳＴ１１ｂ＞基準データフロー（アプリケーションｂのデータフロー）の比較段［０］と非基準データフロー（アプリケーションａのデータフロー）の比較段［０］の演算種類、即ち、“―（減算）”と“＋（加算）”を比較する。このとき、減算と加算は演算種類が等しいものとして考えると、比較が一致する。
＜ステップＳＴ１２ａ，ＳＴ１２ｂ＞演算種類が一致したため、一致段数はカウントアップされて“１段”となる。この段階では、一致段数“１段”は目標深さ段数“４段”に達していないため、以下、ステップＳＴ１３からの処理を継続する。
【００２６】
＜ステップＳＴ１３＞基準データフローの比較段を１段さかのぼる。即ち、アプリケーションｂの比較段は“１”となる。
＜ステップＳＴ１４＞非基準データフローの比較段を１段さかのぼる。即ち、アプリケーション１の比較段は“１”となる。
＜ステップＳＴ１５ａ，ＳＴ１５ｂ＞比較段数を１カウントアップし、比較段数を“１段”とする。比較段数“１段”が目標深さ段数“４段”に達していないため、上記ステップＳＴ１１〜ステップＳＴ１５（ループ４）の処理を繰り返す。
＜ステップＳＴ１１ａ−２，ＳＴ１１ｂ−２＞基準データフローの比較段［１］と非基準データフローの比較段［１］の演算種類、即ち、“演算なし”と“＋（加算）”、“＋（加算）”と“＋（加算）”を比較する。このとき、片方の演算種類の比較が一致しないため、ステップＳＴ１６の処理へ移る。
【００２７】
＜ステップＳＴ１６＞上記ステップＳＴ１５までの比較で共通データフローが抽出できなかったため、非基準データフローの起点を１段さかのぼり、非基準データフローの起点段番号を“１”に更新し、上記ステップＳＴ７〜ステップＳＴ１５（ループ３）の処理を繰り返す。
＜ステップＳＴ７ａ−２，ＳＴ７ｂ−２＞“非基準データフローの深さ段数［９段］−目標深さ段数［４段］”が“非基準データフローの起点段番号［１］”以上であるため、一致段数を０にリセットする。
＜ステップＳＴ８−２＞比較段数を０にリセットする。
＜ステップＳＴ９−２＞基準データフローの起点段［０］を基準データフローの比較段に設定する。
＜ステップＳＴ１０−２＞非基準データフローの起点段［１］を非基準データフローの比較段に設定する。
＜ステップＳＴ１１ａ−３，ＳＴ１１ｂ−３＞基準データフロー（アプリケーションｂ）の比較段［０］と非基準データフロー（アプリケーションａ）の比較段［１］の演算種類、即ち、“＋（加算）”と“＋（加算）”を比較し、比較が一致する。
＜ステップＳＴ１２ａ−２，ＳＴ１２ｂ−２＞演算種類が一致したため、一致段数はカウントアップされて“１段”となる。この段階では、一致段数“１段”は目標深さ段数“４段”に達していないため、以下ステップＳＴ１３−２からの処理を継続する。
【００２８】
＜ステップＳＴ１３−２＞基準データフローの比較段を１段さかのぼる。即ち、アプリケーションｂの比較段は“１”となる。
＜ステップＳＴ１４−２＞非基準データフローの比較段を１段さかのぼる。即ち、アプリケーション１の比較段は“２”となる。
＜ステップＳＴ１５ａ−２，ＳＴ１５ｂ−２＞比較段数を１カウントアップし、比較段数を“１段”とする。比較段数“１段”が目標深さ段数“４段”に達していないため、ステップＳＴ１１〜ステップＳＴ１５（ループ４）の処理を繰り返す。
＜ステップＳＴ１１ａ−４，ＳＴ１１ｂ−４＞アプリケーションｂの比較段［１］とアプリケーションａの比較段［２］の演算種類、即ち、“＋（加算）”と“＋（加算）”、“＋（加算）”と“＋（加算）”を比較し、比較が一致する。
＜ステップＳＴ１２ａ−３，ＳＴ１２ｂ−３＞演算種類が一致したため、一致段数はカウントアップされて“２段”となる。この段階では、一致段数“２段”は目標深さ段数“４段”に達していないため、以下、ステップＳＴ１３−３からの処理を継続する。
【００２９】
＜ステップＳＴ１３−３＞基準データフローの比較段を１段さかのぼる。即ち、アプリケーションｂの比較段は“２”となる。
＜ステップＳＴ１４−３＞非基準データフローの比較段を１段さかのぼる。即ち、アプリケーション１の比較段は“３”となる。
＜ステップＳＴ１５ａ−３，ＳＴ１５ｂ−３＞比較段数を１カウントアップし、比較段数を“２段”とする。比較段数“２段”が目標深さ段数“４段”に達していないため、ステップＳＴ１１〜ステップＳＴ１５（ループ４）の処理を繰り返す。
＜ステップＳＴ１１ａ−５，ＳＴ１１ｂ−５＞アプリケーションｂの比較段［２］とアプリケーションａの比較段［３］の演算種類、即ち、“＋（加算）”と“＋（加算）”、“＋（加算）”と“＋（加算）”、“＋（加算）”と“＋（加算）”、“＋（加算）”と“＋（加算）”を比較し、比較が一致する。
＜ステップＳＴ１２ａ−４，ＳＴ１２ｂ−４＞演算種類が一致したため、一致段数はカウントアップされて“３段”となる。この段階では、一致段数“３段”は目標深さ段数“４段”に達していないため、以下、ステップＳＴ１３−４からの処理を継続する。
【００３０】
＜ステップＳＴ１３−４＞基準データフローの比較段を１段さかのぼる。即ち、アプリケーションｂの比較段は“３”となる。
＜ステップＳＴ１４−４＞非基準データフローの比較段を１段さかのぼる。即ち、アプリケーション１の比較段は“４”となる。
＜ステップＳＴ１５−４＞比較段数を１カウントアップし、比較段数を“３段”とする。比較段数“３段”が目標深さ段数“４段”に達していないため、ステップＳＴ１１〜ステップＳＴ１５（ループ４）の処理を繰り返す。
＜ステップＳＴ１１ａ−６，ＳＴ１１ｂ−６＞アプリケーションｂの比較段［３］とアプリケーションａの比較段［４］の演算種類、即ち、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”、“×（乗算）”と“×（乗算）”を比較し、比較が一致する。
＜ステップＳＴ１２ａ−５，ＳＴ１２ｂ−５＞演算種類が一致したため、一致段数はカウントアップされて“４段”となる。一致段数“４段”が目標深さ段数“４段”に達したため、共通データフローが抽出されたものとして、処理を終了する。
以上のようにして、複数のアプリケーションに共通するデータフローを抽出することが可能である。
【００３１】
以上のように、実施の形態３の共通データフロー抽出システムによれば、共通データフロー抽出手段として、複数のアプリケーションのデータフロー記述の最終点を起点として演算段数毎に演算種類を比較するデータフロー比較部１０２と、データフロー比較部１０２で、予め定めた目標段数分の一致段数が得られた場合に、目標段数のデータフロー記述部分を共通データフローとして抽出する共通データフロー抽出部１０３とを備えたので、複数のアプリケーション間で共通に存在するデータフローを容易かつ確実に抽出することができる。
【００３２】
また、実施の形態３の共通データフロー抽出方法によれば、抽出する共通データフローの目標深さ段数を設定し、共通データフロー抽出対象である複数のアプリケーションのデータフロー記述のそれぞれの深さを計測し、複数のアプリケーションのデータフローのうち最も深さが小さいアプリケーションのデータフローを基準データフローとし、基準データフローの深さが目標深さ段数よりも小さい場合は、目標深さ段数を基準データフローの深さの値に変更するステップと、一致段数を初期化後、複数のアプリケーションのデータフローの最終点を起点とし、それぞれのデータフローを一段ずつさかのぼりながら演算種類の一致／不一致を判定し、一致の場合は一致段数をカウントアップして引き続き一段データフローをさかのぼって判定を継続し、不一致の場合は一致段数を０にリセットして基準データフローではないデータフローの起点を一段上にずらして新たに判定を開始するステップと、一致段数が目標深さ段数に達した場合は、一致したデータフロー部分を共通データフローとして抽出するステップと、一致段数が目標深さ段数に達する前に基準データフローではないデータフローの最上段まで判定が終了した場合は、一致段数を０にリセットして基準データフローの起点を一段上にずらして新たに判定を開始するステップと、一致段数が目標深さ段数に達する前に基準データフローの最上段まで判定が終了した場合は、一致段数を０にリセットして目標深さ段数を１減らして、再度各データフローの最終点を起点として判定を行うステップとを備えたので、複数のアプリケーション間で共通に存在するデータフローを容易かつ確実に抽出することができる。
【符号の説明】
【００３３】
１  共通データフロー抽出手段、２ａ  アプリケーションａのデータフロー記述、２ｂ  アプリケーションｂのデータフロー記述、３  共通データフロー、４ａ  アプリケーションａの動作記述、４ｂ  アプリケーションｂの動作記述、５ａ，５ｂ  データフロー展開手段、１０１ａ  第１入力部、１０１ｂ  第２入力部、１０２  データフロー比較部、１０２ａ  基準データフロー深さ段数記憶部、１０２ｂ  非基準データフロー深さ段数記憶部、１０３  共通データフロー抽出部、１０４  目標深さ段数記憶部、１０５  一致段数記憶部。
【図１】
2010262359.tif 000003
【図２】
2010262359.tif 000004
【図３】
2010262359.tif 000005
【図４】
2010262359.tif 000006
【図５−１】
2010262359.tif 000007
【図５−２】
2010262359.tif 000008
【図５−３】
2010262359.tif 000009
【図５−４】
2010262359.tif 000010
【図５−５】
2010262359.tif 000011
【図６】
2010262359.tif 000012
【図７】
2010262359.tif 000013
【図８】
2010262359.tif 000014