(57)【要約】【課題】本発明は、アルゴリズムの中に組み込まれた固有平行度の上限を定量し、信号と情報処理システムが新規開発プラットフォーム上での開発を促進するためのアルゴリズム固有平行度の分析方法を提供することを課題とする。【解決手段】本発明のアルゴリズムの固有平行度の分析方法は、演算を代表するノードと、データ依存度とデータの流れを示す有向辺からなる、アルゴリズムのデータフローグラフを生成するステップと、前記データフローグラフを代表する行列を生成するステップと、前記データフローグラフの前記行列の階数と次元数に基づいて、前記固有平行度を定量するステップと、を備えることを特徴とする。【選択図】図１
2013534671.tif 000002
【特許請求の範囲】
【請求項１】
演算を代表するノードと、データ依存度とデータの流れを示す有向辺からなる、アルゴリズムのデータフローグラフを生成するステップと、
前記データフローグラフを代表する行列を生成するステップと、
前記データフローグラフの前記行列の階数と次元数に基づいて、固有平行度を定量するステップと、を備えることを特徴とするアルゴリズムの固有平行度の分析方法。
【請求項２】
前記データフローグラフは、前記アルゴリズムを代表するデータフローモデルから生成されることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【請求項３】
前記行列は、複数の前記データフローグラフからその中の線形方程式に写像されることで生成されることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【請求項４】
前記行列は依存度行列であり、下記［数１］のフォームを有し、このうち、vjは 第ｊのノードを表し、且つ、eiは第ｉの辺を表すものであることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【数１】
2013534671.tif 000023
【請求項５】
前記行列はラプラス行列であり、下記［数２］のフォームを有し、degree(vi)は 第ｉのノードに結ばれる辺の数であることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【数２】
2013534671.tif 000024
【請求項６】
前記固有平行度は、前記ノードの数から前記行列の階数を引いたものに等しいことを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【請求項７】
アルゴリズムより生成される前記データフローグラフの前記行列の基底に基づいて、零空間を張ることによって、それぞれの独立演算集合を特定するステップを、更に備えることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【請求項８】
前記ノードの数が前記辺の数よりも小さくない場合、前記行列は依存度行列であり、さもなくば、前記行列はラプラス行列であることを特徴とする請求項１に記載のアルゴリズムの固有平行度の分析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アルゴリズムの固有平行度（intrinsic parallelism）の分析と定量に関するものである。
【背景技術】
【０００２】
アムダールの法則（G. M. Amdahl, 「シングルプロセッサによって、大規模な演算能力を達成する可能性」、ＡＦＩＰＳコンファレンス刊行物、第４８３−４８５ページ、１９６７年）は、ソフトウェアプログラムの平行化により得られる最大の高速化の理論を提供する。逐次部分は、データ依存度が高すぎたため、平行化されることができず、この最大高速化の理論は、プログラム内の逐次部分の比率に基づいて決定される。アムダールの法則は平行度に対して簡潔で、且つ初歩的な概念レベルのアイデアを提供する。しかしながら、この技術により測定された平行度は、アルゴリズム自身ではなく、ターゲットプラットフォームによって決められる。したがって、このような平行度の測定は、アルゴリズムに固有的のものではなく、ターゲットプラットフォームの違いによって偏向が生じる。
【０００３】
アムダールの法則に類似する、グラフに基づく技術定量（V. Escuder、R. Duran、R. Rico「グラフ理論によって命令レベルの平行度を定量する」、第２回性能評価方法とツール国際コンファレンス刊行物、２００７年）は、グラフ理論に基づき、プログラムの命令レベルの平行度（Instruction level parallelism、ＩＬＰ）において、まず、データ依存行列Ｄは命令順序を表し、続いて、プログラムのクリティカルパスの長さは、Ｄの行列の掛け算によって決定される。この技術は、さらに特定のプロセッサ指向のプラットフォームのみに使用されるという制限を受ける。このため、命令レベル平行度の定量化はアルゴリズムに対して、同様に非固有的であるので、依然として、ターゲットプラットフォームと使用されるコンパイラによって決められる。
【０００４】
Prihozhy等は、演算複雑度とアルゴリズムのクリティカルパスの長さの比率に定義される平行化レベル（parallelization potential）に基づいて、平行度を推定する方法を提示した（A. Prihozhy、M.MattavelliとD. Mlynek、「マルチメディアの平行化レベルの推定を効率的に実現するために、アルゴリズムクリティカルパスの動的推定」、ＩＥＥＥイメージ技術回路とシステム刊行物、第５９３〜６０８ページ、第１５巻、第５号、２００５年５月）。この方法は、演算の合計数を用いて複雑度を測定するものである。この場合のクリティカルパスの長さは、順次に行わなければならない演算の最大数量と定義される。この方法は、アムダールの法則や命令レベル平行度方法と比べ、演算数量の平行化レベルに基づいて、更に多くの固有平行度測定を明らかにするが、もちろん、データ度が比較的に低い状態の場合である。演算の数とクリティカルパスの長さはＣ／Ｃ＋＋プログラムで生成されたデータフローの実行グラフに基づいて計算されるので、プログラミングスタイル言語とデータ構造による偏向（バイアス）の影響を受けるため、上記の方法はアルゴリズム固有の平行度を導出することはできない。
【０００５】
一方、アルゴリズムのデータフローモデルによって生成された因果軌跡グラフ（causation trace graph）は、更に多くのアルゴリズム固有の依存度と演算平行度を表すことができる。一般的には、因果軌跡グラフは線形部分に相対して更に多くの順次演算により構成されており、比較的に広い部分は、比較的に高い平行度を含む。論文（J. W. Janneck、D. Miller と D. B. Parlour、 "データフロープログラムのプロファイリング," IEEE ICME 2008年刊行物 第１０６５-１０６８ページ、２００８年６月）によれば、演算の平行度は同じ時間内の平均完成仕事量を用いて測定することができる。しかしながら、この方法は、平行度を正確に定量することができない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記に鑑み、本発明の目的は、アルゴリズムの固有平行度の分析方法を提供することを課題とする。
【課題を解決するための手段】
【０００７】
本発明は、アルゴリズムの固有平行度の分析方法を提供する。アルゴリズム固有の複雑度に基づいて、アルゴリズムと構造を同時に最適化すること（Algorithm  /architecture co-exploration AAC）は、新規に開発される電子システムレベル（electronic system level、ESL）のデザインの時代において、すでに一つの設計のパラダイムとなっている。アルゴリズムの固有平行度は、最も重要な複雑度の測定のメカニズムの一つであり、新規開発プラットフォームの開発を促進することができ、特定用途向け集積回路（application specific integrated circuits、ASIC)と、リコンフィギュラブル回路と、大量平行処理ユニット（processing elements、PE)、及び埋め込まれるマルチコアＣＰＵなどを含み、現代と未来の信号及び情報処理アプリケーションに採用される高度アルゴリズムとして好適に用いられる。よって、アルゴリズム平行度の利用は、同時にアルゴリズムと構造を最適化するのに対して、必要であり、且つ不可欠である。本発明の目的は、線形代数の理論に基づいて、システム化の方法を提供し、アルゴリズムにおいての固有平行度の上限を定量することである。それによって信号と情報処理システムが新規開発プラットフォーム上での開発を促進する。言い換えれば、得られた平行度は、アルゴリズム自身に対して固有的なものであるため、ハードウェア、或はソフトウェアに影響されることはないので、信号と情報処理システムのアルゴリズム/構造の共同開発を助長することができる。
【０００８】
上記目的を達成するために、本発明に基づいたアルゴリズムの固有平行度の分析方法は、演算を代表するノードと、データ依存度とデータの流れを示す有向辺からなるアルゴリズムのデータフローグラフを生成するステップと、前記データフローグラフを代表する行列を生成するステップと、前記データフローグラフの前記行列の階数と次元数に基づいて、前記固有平行度を定量するステップとを備えることを特徴とする。
【０００９】
上記の如く、本発明で開示された一つのアルゴリズムの複雑度は固有平行度上の測定方法であり、新しいアルゴリズム／構造の共同設計方法に用いられ、アルゴリズムと構造を同時に開発することができることによって、システムの最適化が可能となる。演算複雑度の分析とデータフローモデルは、アルゴリズムと構造の同時最適化において、重要な役割を果たす。信号と情報処理の発展性と未来性のために、固有平行度は最も重要な複雑度測定のメカニズムの一つである。アルゴリズムのデータフローモデルと依存度、及び／或はラプラス行列に基づいて、データフローグラフを線形方程式に写像し、線形方程式システムの自由度を表すことによって、本発明は、アルゴリズムに組み込まれた固有平行度をシステム的に定量することができる。また、本発明では、階数理論は固有平行度の定量の加速に用いられる。また、得られた固有平行度は、特定用途向け集積回路（application specific integrated circuits,ＡＳＩＣ）、リコンフィギュラブル回路、大量平行処理単位（processing element,ＰＥ）、及び組み込みマルチコアＣＰＵなどに用いられ、さらに複雑な信号と情報処理を必要とするプラットフォームのデザイン空間の開発にも使用される。
【発明の効果】
【００１０】
従来の技術と比べて、本発明の方法はいくつかの長所を有する。まず、アルゴリズムの平行度を定量するために、理論的に信憑性が高い方法を提供する。一方、因果軌跡グラフは（J. W. Janneck, D. Miller と D. B. Parlourより提示される）、相対する平行度の比較情報のみを提供する。また、データフローモデル化より、本発明の方法は不規則のデータ依存度に用いられ、アルゴリズムを特徴付けるのにも適用される。また、高レベルプログラミングモデルとＩＬＰの定量による分析とを比較すると、本発明の平行度のメカニズムは固有性を有するため、特定のプロセッサ指向のプラットフォームだけに制限されず、アルゴリズムを一般的なプラットフォームに写像することができ、さらに分散式システム上にも写像することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の好ましい実施形態に係るアルゴリズム平行度の分析方法のフロー図である。
【図２】アルゴリズム平行度の分析方法による一つの状況を示した図である。
【図３】一つの実施形態のデータフローグラフを示した図である。
【発明を実施するための形態】
【００１２】
本発明の内容をさらに明らかにするため、以下に、図面を参照しながら詳しく説明する。このうち同一の符号は、同じ機能の構成要素を指す。
【００１３】
アルゴリズムに含まれる各種の平行度のうちの一つは、互いに独立した独立演算集合として表示されることができるため、同時性がなくても、平行に実行されることができる。しかしながら、独立演算集合は依存する演算から構成され、順次に実行する必要がある。よって、厳密に言うと、アルゴリズムに含まれる平行度は全ての独立演算集合の数である。本発明の方法の主な目標は、データフローモデルと線形代数に基づいて生成されたデータフローグラフを分析することによって、固有平行度を得ることである。まず、アルゴリズムの入力を分析し、アルゴリズムの出力は、固有平行度の上限と関連する独立演算集合を含み、前記独立演算集合は同時化する必要がなく、平行に実行されることができる。
【００１４】
図１はフロー図であり、本発明の好ましい実施形態に係るアルゴリズム平行度の分析方法を表す。図２は、アルゴリズム平行度の一つの状況を分析した状態を示す図である。図１と図２に示すように、ステップＳ０１はアルゴリズムからデータフローグラフを生成する。これは演算を代表するノードv1からv7、及びデータ依存度と流れを示す有向辺e1からe4により構成される。明確に説明するため、図２に示されるアルゴリズムは、簡単な例とするが、その目的を制限するものではない。本実施形態において、データフローグラフは、アルゴリズムを表すデータフローモデルにより生成される。データフローモデルはアルゴリズムの動作、或は機能を表現できるものだけでなく、構造上の特性も明らかにすることができる。
【００１５】
ノードv1からv7は演算を代表し、且つ有向辺e1からe4はデータの依存度と流れを表すものである。例えば、ノードv1は、変数Ａ１とＢ１の計算を表し、且つv1からv4の辺e1は、ノードv1とv4のデータの依存度と流れを代表するものであり、その他はこれによって類推することができる。
【００１６】
ステップＳ０２は、データフローグラフを代表する行列の例を生成する。行列は、例えば、ラプラス行列、或は依存行列である。ラプラス行列のフォームは、以下である。
2013534671.tif 000003
【００１７】
degree（vi）は第iのノードviに結ばれた辺の数量である。依存行列のフォームは、以下の通りである。
2013534671.tif 000004
【００１８】
vjは第ｊのノードを代表し、且つeiは第ｉの辺を代表する。説明するために、図２に示す行列はラプラス行列である。この行列は、ラプラス行列にせよ、依存行列にせよ、いずれも、上記のフォームによって生成することができる。また、データフローグラフを生成する時、辺は依存度を表すことができる以外に、更に、辺の上の重みによって、処理ユニットの依存度を表すことができる。このほかに、この行列はデータフローグラフから写像される複数の線形方程式によって生成することができる（この部分については後述する）。
【００１９】
ステップＳ０３において、生成されたデータフローグラフの行列の階数と次元数によって固有平行度を定量する。階数理論に基づいて、平行度は、変数の数から行列の階数を引いたものに等しいことを導出することができる。このほか、行列の階数は従来の方法に基づいて、容易に計算されることができ、例えば、被的階段行列（reduced echlon matrix）の方式である。図２に示すように、ラプラス行列の変数の数は７に等しく、且つ行列の階数は４であるから、平行度は３に等しい。
【００２０】
また、アルゴリズム平行度の分析方法は、アルゴリズムに基づいて生成されたデータフローグラフの行列の基底によって、零空間を張ることでそれぞれの独立演算集合を特定するステップを更に備えることができる。
【００２１】
以下は、本発明のさらなる説明である。
【００２２】
［アルゴリズムを代表するデータフローモデル］
信号処理の応用において、固有平行度はデータフローモデルにより生成される因果グラフによって固有化されることができる。これは数学の表現式から得られたデータフローモデルが演算の関連性とデータ転送を明確に描くことができ、且つ設計パラメータからの制限を受けられない。よって、ノードと有向辺によって、それぞれの演算の間のデータ依存度を明確に表すことができる。ノードは演算を表し、有向辺はデータの源と目的地を表す。即ち、データの流れである。また、データの駆動の本質により、データフローモデルはアルゴリズムの並行性、或は平行度を自然に表現することができる。故に、従来の高レベルのプログラミングモデルと比べて、データフローモデルは、更なるアルゴリズムの固有複雑特徴を含むだけでなく、実施上の構造情報も示している。アルゴリズム/構造において、データフローモデルはアルゴリズムと構造との間のブリッジとして、従来の方法において、両者は、元々二つの独立した設計段階である。よって、本発明の平行度分析システムはアルゴリズムを代表するためにデータフローモデルを採用する。
【００２３】
［データフローグラフを線形方程式に写像する］
一つのアルゴリズムのデータフローグラフＧは、演算を代表するｎ個のノードと、データ依存度とデータ流れを表すｍ個の辺により構成され、そのうちＧのノード集合はＶ（Ｇ）＝{v1, v2,…，vn}であり、且つＧの辺集合はＥ(Ｇ)={e1, e2,…，em}である。変数xiをデータフローグラフＧの各演算viに割り当てることによって、本発明は線形方程式を用いて各演算との間のデータ依存度を転換することができ、即ち、依存度制限である。もし、演算viが演算vjに依存した場合、このデータ依存度制約は次の式で表すことができる。
【数１】
2013534671.tif 000005
【００２４】
したがって、ｎ個の演算（或はn個のノード）とｍ個のデータ依存度（或は有向辺）を有するデータフローグラフは、ｎ個の変数とｍ個の方程式を有する線形方程式システムに転換することができる。よって、ｍ掛けるｎの依存度行列Ｍとなり、且つＭｘ＝ ０である。
【数２】
2013534671.tif 000006
【００２５】
ここでは、一つの簡単な例のみを上げており、１と−１を用いて、依存度を表す。更に、依存度は異なる用途に基づいて異なる値を与えることができ、明らかなことは、本発明の依存行列は従来図論においての関連行列の転置形式として見なすことができ、列と行は辺とノードにそれぞれ対応する。次に、更に多くのデータフローグラフの特徴を表すために、データフローグラフを代表する線形方程式の高階形式を考慮する。次に、元の線形方程式の二次形式を研究する。
【数３】
2013534671.tif 000007
【００２６】
従って、依存度行列の二次形式は容易に得ることができ、そしてＭｔＭはスペクトルグラフ理論においてのｎ掛けるｎのラプラス行列Ｌと同等である。
【数４】
2013534671.tif 000008
【００２７】
比較的に簡単な例は、degree（vi）は第iのノードに結ばれた辺の数である。ラプラス行列において、i番目の対角線要素は、i番目演算の演算数に結ばれており、且つ非対角要素は２つの演算が結ばれているかどうかを表す。前記［数４］を［数３］に代入することにより、ｘTＬｘの値は、隣接するノードの平方差の総和であることを示すことができる。
【数５】
2013534671.tif 000009
【００２８】
2013534671.tif 000010
【００２９】
これまで、すでに説明したように、依存度行列Ｍとラプラス行列Ｌは簡潔な方式を用いてデータフローグラフを代表することができる。次に、依存度行列、或はラプラス行列に基づいて、アルゴリズムの独立演算集合と固有平行度を如何に得るかを説明する。
【００３０】
［依存度行列に基づく手法］
アルゴリズムの独立演算集合の数量を得て、且つ固有平行度を導出するために、本発明は、まず、データフローグラフを代表する線形方程式を解くことにより、データフローグラフにおいて、連結する成分を識別する。最後に、独立演算集合は、Ｍの中の零空間を構成する張る基底によって、容易に識別することができる。また、連結する成分の数量は依存度行列零空間の次元数に等しく、同時に、演算の数から依存度行列の階数を引いたものにも等しい。
【数６】
2013534671.tif 000011
【００３１】
ＤｏＰはアルゴリズムの固有平行度の上限を表し、dim Null ＭはＭの零空間の次元数であり、Ｍｘ ＝０の自由変数の数を表し、且つrankＭはＭの行階数であり、線形独立方程式の数を示す。理由と簡単な証明は、以下の段落で示される。
【００３２】
仮に、二つの演算、或はノードviとvjは直接結ばれておらず、その他のノードによって結ばれた場合、それに関連する変数は必ず等しいものである。即ち、xi＝xjである。その結果、同じノードと連結する成分のその関連する変数値は等しくなる。つまり、連結する成分は一次元自由度を生成することができ、或はアルゴリズムを代表する線形方程式システムの自由変数を生成する。また、Ｍの零空間のそれぞれ線性独立基底は連結する成分に対応する。よって、連結する成分の数（平行度）は、当然のことながら、線形方程式システムの自由度に等しい。さらに、階数の定理に基づいて：
【数７】
2013534671.tif 000012
【００３３】
次の結論を容易に導くことができる：自由度（平行度）も変数の数が依存度行列の階数を引いたものに等しく、それはデータ依存度による有効制約の次数である。
【００３４】
このように、本発明は、最初にデータフローモデルによってアルゴリズムを示しており、且つデータ依存度情報を含むデータフローグラフを生成する。次に、平行度を示すために、本発明は、データフローグラフを再び線形方程式システムに変換する。最後に、本発明は平行度が線形方程式システムの自由度と同等であることを証明する。
【００３５】
表１は、アルゴリズムを代表するデータフローグラフと線形依存度方程式システムのそれぞれの用語の実際の定義をまとめたものである。一般的に、アルゴリズムにおいて、いずれもデータ依存制約の最大平行度がアルゴリズムの演算の数量に等しいものはない。しかしながら、仮に、アルゴリズムがより高いデータ依存を含む場合は、その相対する平行度は下がる。その結果、平行度とデータ依存度は互いに補うものである。本発明の方法において、有効なデータ依存度は、依存度行列の階数によって定量することができる。逆に、平行度は依存度行列の零空間の次元数によって定量することができる。階数理論［数７］に基づいて、定量且つ互いに補う平行度と依存度を容易に確認することができ、本発明の正確性も証明することができる。
【表１】
2013534671.tif 000013
【００３６】
［ラプラス行列に基づく方法］
従来のスペクトルグラフ理論の性質は次のことに言及している。（１）一つの連結グラフの最小のラプラス固有値は０に等しく、且つ対応する固有ベクトル＝[１，１，...，１]Ｔである。（２）一つの連結グラフのラプラス行列は、一つの固有値＝０の固有値が存在する。（３）グラフの中の連結する成分の数はラプラス行列の固有値が０の固有値の数に等しい。よって、アルゴリズムにおいての厳格平行度の次数は、データフローグラフのラプラス行列の固有値＝０の固有値の数である。また、スペクトルグラフ理論に基づいて、独立演算集合は、固有値＝０と関連する固有ベクトルに基づいて識別することができる。このほかに、それぞれの独立演算集合の固有値と固有ベクトルを比較することによって、平行度は、同次、或は非同次であることを知ることができる。
【００３７】
よって、階数理論に基づいて、ラプラス行列の固有値＝０の固有値の数を計算することによって、以下のアルゴリズムの平行度を得ることができる。
【数８】
2013534671.tif 000014
【００３８】
λはラプラス行列の固有値であり、且つdim Ｌはラプラス行列の次元数であり、演算或はノードの数量と同じである。ラプラス行列は依存度行列の二次フォームであることから、零空間の次元数は同じである。いずれかの方法でも、アルゴリズムの固有平行度を求めることができることを再び示している。
【００３９】
［上述の二つの方法の間から一つを選択して、固有平行度を求める］
ｎ個のノードとｍ個の辺から構成されるデータフローグラフは、その関連する依存度行列とラプラス行列の次元数が、それぞれｍ掛けるｎとｎ掛けるｎである。よって、本発明は、元の行列を階段行列に転換する時に、低い複雑度を有する方法を適応的に選択する。
【数９】
2013534671.tif 000015
【００４０】
仮に、演算（ノード）の数が依存度（有向辺）の数より大きい場合は、依存度行列法を用いて、それ以外の場合は、ラプラス行列法を使用したほうが好ましい。
【００４１】
図３はデータフローグラフの例であり、データフローグラフを用いて、アルゴリズムの固有平行度の方法を説明するためのものである。
【００４２】
Ａ) 依存度行列に基づく方法
図１に基づいて、６つのデータ依存度によって、次の5つの方程式が得られる。
【数１０】
2013534671.tif 000016
【００４３】
その結果、依存度行列と関連する線形方程式システムは、次のように表示される。
【数１１】
2013534671.tif 000017
【００４４】
その対応する被約階段行列は、次のように表示される。
【数１２】
2013534671.tif 000018
【００４５】
最後に、依存度行列が張る零空間は、次のように表示される。
【数１３】
2013534671.tif 000019
【００４６】
前記［数１２］に基づいて、明らかなことは、データフローグラフは、元々、６つのデータ関連制約を含むが、依存度行列の階数は５である。つまり、有効依存制約の次数は５である。また、前記［数１３］に基づいて、依存度行列の零空間の次元数は２であり、且つその基底は{[１１００１１０]ｔと[００１１００１]ｔ}である。よって、厳格平行度の次数は２である。さらに、依存度グラフの零空間が張る基底に基づいて、同じ値を共有しているため、第１と、第２と、第５、及び第６のノードは結ばれていることがわかる。したがって、それらは独立演算集合を形成する。一方、その他のノードは、もう一つの独立演算集合を形成する。前記の場合は代表的な例として、本発明の定量された固有平行度の方法の有効性を明らかに示している。
【００４７】
Ｂ)ラプラス行列に基づく方法
図３に示されるデータフローグラフのラプラス行列は、次のように表示される。
【数１４】
2013534671.tif 000020
【００４８】
その対応する被約階段行列は、次のように表示される。
【数１５】
2013534671.tif 000021
【００４９】
最終的に、対応するラプラス行列のλ＝０の固有空間は、次のように表示される。
【数１６】
2013534671.tif 000022
【００５０】
前記［数１５］に基づいて、明らかなことは、ラプラス行列の階数は５だけである。つまり、有効な依存制約の次数は５だけである。また、前記［数１６］に基づいて、ラプラス行列の零空間の次元数は２であり、且つ基底は{[１１００１１０]ｔと[００１１００１]ｔ}である。結果、厳格平行度の次数は２である。また、ラプラスグラフに対応するλ＝０の固有ベクトルに基づいて、同じ値を共有しているため、第１と、第２と、第５、及び第６のノードは結ばれていることを発見することができる。したがって、それらは独立演算集合を形成する。一方、その他のノードは、もう一つの独立演算集合を形成する。要するに、依存度行列、或はラプラス行列の方法に基づいて、いずれも同じ結果を得ることができる。
【００５１】
このように、本発明はアルゴリズムの複雑度を表す固有平行度の測定方法に関するものであり、新しいアルゴリズム／構造の共同設計方法に用いられ、アルゴリズムと構造を同時に開発することができることによって、システムを最適化することができる。アルゴリズムの複雑度の分析とデータフローモデルは、アルゴリズムと構造を同時に最適化することにおいて、重要な役割を果たす。未来の信号と情報処理のために、固有平行度は最も重要な複雑度測定のメカニズムの一つであることは明らかである。アルゴリズムのデータフローモデルと依存度、及び／又はラプラス行列に基づいて、データフローグラフを線形方程式に写像し、線形方程式システムの自由度を表すことによって、本発明は、アルゴリズムに組み込まれた固有平行度をシステム的に定量することができる。また、本発明では、階数理論は固有平行度の定量を加速するために用いられる。また、得られた固有平行度は、特定用途向け集積回路（application specific integrated circuits,ＡＳＩＣ）、リコンフィギュラブル回路、大量平行処理単位（processing element,ＰＥ）、及び組み込みマルチコアＣＰＵなどに用いられ、さらに複雑な信号と情報処理を必要するプラットフォームのデザイン空間の開発にも使用される。
【００５２】
本発明は特定の実施形態を参照して詳述してきたが、これに制限されるものではない。当分野に係る技術者が前記の内容に基づいてさまざまな修正または実施を行うことができ、本発明の要旨を逸脱しない範囲の設計変更などがあっても、本発明に含まれる。
【産業上の利用可能性】
【００５３】
本発明は以上の如く構成されることで、アルゴリズムの中に組み込まれた固有平行度の上限を定量し、信号と情報処理システムの新規開発プラットフォーム上での開発を促進するためのアルゴリズム固有平行度の分析方法を提供し得るものである。
【符号の説明】
【００５４】
Ｓ０１、Ｓ０２、Ｓ０３      ステップ
【図１】
2013534671.tif 000025
【図２】
2013534671.tif 000026
【図３】
2013534671.tif 000027
【国際調査報告】
2013534671.tif 000028