アルゴリズムの本質的な並行処理を定量化及び分析する方法であって、前記方法はコンピューターによって実装されるように構成され、前記方法は、a前記コンピューターを、複数の演算セットによる前記アルゴリズムを表現するよう構成させるステップ、b前記コンピューターを、前記複数の演算セットに従いラプラス行列を取得するよう構成させるステップ、c前記コンピューターを、前記ラプラス行列の固有値及び固有ベクトルを計算するよう構成させるステップ、及びd前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させるステップ、を含むことを特徴とする前記方法。ステップbは、b1前記コンピューターを、演算セットに従い、前記アルゴリズムに関するデータフロー情報を取得するよう構成させるサブステップ、b2前記コンピューターを、前記データフロー情報に従い、前記アルゴリズムにおける演算を示す複数の頂点から成るデータフローグラフを取得するよう構成させ、前記頂点のうち対応する2つの頂点の相互接続を示し前記アルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺を取得するよう構成させるサブステップ、及びb3前記コンピューターを、前記データフローグラフに従って、前記ラプラス行列を取得するよう構成させるサブステップ、を含む、請求項1に記載の方法。ステップdは、d1前記コンピューターを、前記ラプラス行列の前記固有値及び前記固有ベクトルに従って、前記アルゴリズムの厳密な並列処理に関する情報のセットを取得するよう構成させるサブステップ、並びにd2前記コンピューターを、前記アルゴリズムの複数の依存性深さの少なくとも1つ及び前記厳密な並列処理に関する情報のセットに従って、前記アルゴリズムのマルチグレイン並列処理に関する情報のセットを取得するよう構成させるサブステップ、を含む、請求項1に記載の方法。前記厳密な並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものの数を表す厳密な並列処理の程度と、前記演算セットに対応する厳密な並列処理の構成のセット、をそれぞれ含む、請求項3に記載の方法。サブステップd2において、前記コンピューターは、前記依存性深さ及び前記厳密な並列処理に関する情報のセットに従って前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットをそれぞれ取得するよう構成されることを特徴とする請求項3に記載の方法。前記アルゴリズムのマルチグレイン並列処理に関する複数の情報のセットのそれぞれは、マルチグレイン並列処理の程度、及び、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項5に記載の方法。前記マルチグレイン並列処理に関する情報のセットは、前記依存性深さの最小のもの及び前記厳密な並列処理に関する情報のセットに従って取得される前記アルゴリズムの広義の並列処理に関する情報のセットを含むことを特徴とする請求項3に記載の方法。前記広義の並列処理に関する情報のセットは、前記アルゴリズムの前記演算セットの独立なものに埋め込まれた全ての可能な並列処理を特徴付ける広義の並列処理の程度、及び、広義の並列処理の構成のセットを含むことを特徴とする請求項7に記載の方法。サブステップd1において、前記厳密な並列処理の程度は、スペクトルグラフ理論に基づき、0に等しい前記固有値の数に等しいことを特徴とする請求項3に記載の方法。前記マルチグレイン並列処理に関する情報は、マルチグレイン並列処理の程度と、マルチグレイン並列処理の構成のセットを含むことを特徴とする請求項3に記載の方法。請求項1に記載のアルゴリズムの本質的な並行処理を定量化及び分析する方法を実行時にコンピューターに行わせるプログラム命令を記録した機械読み取り可能な記憶媒体を有するコンピュータープログラム製品。従って、本発明の目的は、ターゲットとなるハードウェア及び/又はソフトウェアのプラットフォームによってバイアスを受けない、アルゴリズムの本質的な並行処理を定量化及び分析する方法を提供することにある。従って、本発明によるアルゴリズムの本質的な並行処理を定量化及び分析する方法は、コンピューターによって実装されるように構成され、以下のステップを有する:aコンピューターを、複数の演算セットによるアルゴリズムを表現するよう構成させる、bコンピューターを、複数の演算セットに従いラプラス行列を取得するよう構成させる、cコンピューターを、ラプラス行列の固有値及び固有ベクトルを計算するよう構成させる、dコンピューターを、ラプラス行列の固有値及び固有ベクトルに従って、アルゴリズムの本質的な並行処理に関する情報のセットを取得させるよう構成させる。図1を参照し、本発明によるアルゴリズムの本質的な並行処理を評価する方法の好適な実施例は、コンピューターによって実装されるように構成され、以下のステップを有する。本質的な並列処理の程度は、ソフトウェア及びハードウェアの設計及び構成を考慮せず、アルゴリズム自身の並列処理の程度を示すものである。つまり、本発明の方法は、アルゴリズムを分析する時、ソフトウェア及びハードウェアによって制限されない。ステップ11において、コンピューターは、複数の演算セットによるアルゴリズムを表現するよう構成される。それぞれの演算セットは、等式、プログラムコード、フローチャート、その他、アルゴリズムを表すどのような形態であってもよい。下記の例においては、アルゴリズムは、下記のようにあらわされる、3つの演算セットO1、O2、及びO3を含む。O1=A1B1C1D1、O2=A2B2C2、及びO3=A3B3C3ステップ12は、演算セットに従ったラプラス行列Ldを取得するようコンピューターを構成することであり、下記のサブステップを含む。サブステップ121において、演算セットに従い、コンピューターは、アルゴリズムに関するデータフロー情報を取得するよう構成される。図2に示されるように、この例の演算セットに対応するデータフロー情報は、下記のように表現されてもよい。データ1=A1B1データ2=A2B2データ3=A3B3データ4=データ1データ7データ5=データ2C2データ6=データ3C3データ7=C1D1サブステップ122において、コンピューターは、データフロー情報に従って、データフローグラフを取得するよう構成される。データフローグラフは、アルゴリズムにおいて演算を表す複数の頂点及び、頂点のうち対応する2つの頂点の相互接続を示しアルゴリズムにおけるデータのソースとデスティネーションを示す方向性のある複数の辺によって構成される。図2に示されるデータフロー情報については、演算記号V1からV7つまり、頂点が加算記号の代わりに使われ、矢印つまり、方向性のある辺が、データのソースとデスティネーションを示し、これにより、図3のデータフローグラフが取得される。特に、演算記号V1が加算演算A1B1を示し、演算記号V2が加算演算A2B2を示し、演算記号V3が加算演算A3B3を示し、演算記号V4が加算演算データ1データ7を示し、演算記号V5が加算演算データ2C2を示し、演算記号V6が加算演算データ3C3を示し、そして演算記号V7が加算演算D1C1を示す。図3に示されるデータフローグラフから、演算記号V4が演算記号V1及びV7に依存することが分かる。同様に、演算記号V5が演算記号V2に依存し、演算記号V6が演算記号V3に依存し、演算記V4、V5及びV6は、互いに依存しない。サブステップ123において、コンピューターは、データフローグラフに従ったラプラス行列Ldを取得するように構成される。ラプラス行列Ldにおいて、i番目の対角の要素は、演算記号Viに接続される演算記号の数を示し、対角から外れた要素は、2つの演算記号が接続されているかどうかを示す。従って、ラプラス行列Ldは、明確にデータフローグラフを、線形代数形式によって示すことができる。図3に示されるデータフローグラフのセットは、下記のように示されてもよい。ラプラス行列Ldは、演算記号V1からV7の間の接続性を示し、第1列から第7列は、演算記号V1からV7をそれぞれ示す。例えば、最初の列において、演算記号V1は、演算記号V4に接続され、従って、行列要素は-1である。ステップ13において、コンピューターは、ラプラス行列Ldの固有値λ及び固有ベクトルXdを計算するように構成される。上記例において取得されたラプラス行列Ldについて、固有値λ及び固有ベクトルXdは、下記の通りである。ステップ14において、コンピューターは、ラプラス行列Ldの固有値λ及び固有ベクトルXdに従って、アルゴリズムの本質的な並列処理に関する情報のセットを取得するように構成される。上記本質的な並列処理に関する情報のセットは、演算セットのうち、互いに独立しており並列処理に実行可能な独立な演算セットを認識するように厳密に定義される。厳密な並列処理に関する情報のセットは、アルゴリズムの上記演算セットのうち、独立な演算セットの数を示す厳密な並列処理の程度、及び、演算セットに対応する厳密な並列処理の構成のセットをそれぞれ含む。F.R.K.チャン数学のリジョナルカンファレンスシリーズ、No.92、1997によって紹介されたスペクトルグラフ理論に基づき、グラフの接続された構成の数は、0に等しいラプラス行列の固有値の数に等しい。アルゴリズムに埋め込まれた厳密な並列処理の程度は、従って、0に等しい固有値λの数に等しい。その上、スペクトルグラフ理論に基づき、厳密な並列処理の構成は、0に等しい固有値λに関連付けられる固有ベクトルXdに従って、特定されてもよい。上記例から、0に等しいラプラス固有値は3つ存在するので、データフローグラフのセットは、3つの独立な演算セットから構成されることが分かる。従って、例示されるアルゴリズムに埋め込まれる厳密な並列処理の程度は、3に等しい。次に、固有ベクトルXdの第1、2、及び3の固有ベクトルは、0に等しい固有値λに関連付けられる。固有ベクトルXdの第1の固有ベクトルを観察することにより、演算記号V1、V4及びV7に対応する値が0ではないということが明らかであり、つまり、演算記号V1、V4及びV7は依存し、データフローグラフの接続されたものV1-V4-V7を形成する。同様に、0に等しい固有値λに関連付けられた固有ベクトルXdの第2及び3の固有ベクトルを形成し、演算記号V2、V5及び演算記号V3、V6は依存し、データフローグラフの残りの2つの接続されたものV2-V5及びV3-V6をそれぞれ形成すると理解される。従って、コンピューターは、3に等しい厳密な並列処理の程度、及び、図3に示されるようなグラフ、テーブル、等式、又はプログラムコードの形態で表現されうる厳密な並列処理の構成を取得するように構成される。ステップ15において、コンピューターは、アルゴリズムの複数の依存性深さの少なくとも1つ及び厳密な並列処理に関する情報のセットに従ったアルゴリズムのマルチグレイン並列処理に関する情報の複数のセットを取得するように構成される。マルチグレイン並列処理に関する情報のセットは、独立な演算セットに埋め込まれた全ての可能性のある並列処理を特徴付けるアルゴリズムの広義の並列処理に関する情報のセット含む。尚、アルゴリズムの依存性深さは、アルゴリズムの処理において重要な、関連付けられた逐次ステップを表し、つまり、アルゴリズムの可能な並列処理に対して相互補完的である。従って、アルゴリズムの異なる本質的な並列処理に関する情報は、異なる依存性深さに基づいて取得されてもよい。特に、厳密な並列処理に関する情報は、アルゴリズムの依存性深さのうち最大のものに対応するアルゴリズムの本質的な並列処理に関する情報であり、広義の並列処理に関する情報は、依存性深さのうち最小のものに対応するアルゴリズムの本質的な並列処理に関する情報である。例えば、上記アルゴリズムは、厳密な並列処理の2つの異なる構成、つまり、V1-V4-V7及びV2-V5を含むV3-V6は、V2-V5に似ており、同じ構成と考えられる。厳密な並列処理V1-V4-V7の構成については、演算記号V1及びV7が互いに独立である、つまり、演算記号V1及びV7が並列に処理されることができることが分かる。従って、アルゴリズムの広義の並列処理に関する情報のセットは、4に等しい広義の並列処理の程度を含み、広義の並列処理の構成は、厳密な並列処理の構成に類似する。この実施例の方法によれば、上記アルゴリズムの広義の並列処理の程度は、4に等しい。アルゴリズムを実装するのに、処理要素は7回の処理サイクルを要する。なぜならば、アルゴリズムは7個の演算記号V1-V7を含むからである。3に等しい厳密な並列処理の程度によれば、3個の処理要素を使ってアルゴリズムを実装するには、3回の処理サイクルを使う。4に等しい広義の並列処理の程度によれば、4個の処理要素を使ってアルゴリズムを実装するには、2回の処理サイクルを使う。更に、より多くの処理要素が使われるものの、少なくとも2回の処理サイクルがアルゴリズムを実装するのに必要であることが分かる。従って、アルゴリズムを実装するのに使われる処理要素の最適な数は、この実施例の方法に従って取得されうる。4×4離散コサイン変換DCTを例とすると、DCTアルゴリズムの演算セットは、図4に示されるデータフローグラフによって表現される。4×4DCTは当業者によってよく知られているので、その更に詳細については、簡潔さのためにここでは省略される。図4より、4×4DCTアルゴリズムの依存性深さの最大のものは、6に等しいことが分かる。依存性深さの最大のものつまり、6については、このアルゴリズムの厳密な並列処理の構成は、図5に示されるように取得されてもよく、このアルゴリズムの厳密な並列処理の程度は、この実施例の方法によれば、4に等しい。5に等しい依存性深さのうち1つをもって4×4DCTアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図6に示されるように取得されてもよく、本質的な並列処理の程度は8に等しい。更に、3に等しい依存性深さのうち1つをもって4×4DCTアルゴリズムの本質的な並列処理を分析する時、このアルゴリズムの本質的な並列処理の構成は、図7に示されるように取得されてもよく、本質的な並列処理の程度は16に等しい。つまり、この発明による方法は、アルゴリズムの本質的な並列処理を評価するのに使われてもよい。本発明は、最も実用的で好適な実施例と考えられるものに関連付けられて記載されたものの、この発明は、記載された実施例に限定されることなく、最も広い解釈の精神及び範囲に含まれる様々な配設を網羅するように意図され、そのような全ての変更や均等な配設を含む、と考えられなければならない。