(57)【要約】本発明は多次元フィールドによるデータ処理に関し、これによればそのために有利には高級言語コードをどのようにして使用できるかが示されている。
2005508029.tif 000002
【特許請求の範囲】
【請求項１】
高級言語をリコンフィギュアラブルアーキテクチャに変換する方法において、
計算のために有限オートマトンを構築して複合的な組み合わせ網を個々のファンクションから形成し、該網に対しオペランドと結果を格納する記憶装置を割り当てることを特徴とする、
高級言語をリコンフィギュアラブルアーキテクチャに変換する方法。
【請求項２】
リコンフィギュアラブルＡＬＵをもつ多次元フィールドによりデータを加工および／または処理する方法において
高級言語コードを用意し該コードを変換して計算のために有限オートマトンを構築し、複合的な組み合わせ網を個々のファンクションから形成し、該網に対しオペランドおよび／または結果を格納する記憶装置を割り当てることを特徴とする、
多次元フィールドによりデータを加工および／または処理する方法。
【請求項３】
前記複合的な組み合わせ網を、ＰＡＥマトリクスができるかぎり長くコンフィギュレーションなしで稼働されるよう構築および／または分解する、請求項１または２記載の方法。
【請求項４】
複合的な命令を定めて前記複合的な組み合わせ網を、ＰＡＥマトリクスができるかぎり長くリコンフィギュレーションなしで稼働されるよう構築および／または分解する、請求項１から３のいずれか１項記載の方法。
【請求項５】
有限オートマトンをインペラティブなソーステキストからダイレクトに構築する、請求項１から４のいずれか１項記載の方法。
【請求項６】
有限オートマトンを、粗粒度のロジック回路および／または既存の細粒度の素子（ＶＰＵにおけるＦＰＧＡセル、ステートマシン等）に整合されたオペレーションから構築し、たとえばもっぱらそれらに整合されたオペレーションから構築する、請求項１から５のいずれか１項記載の方法。
【請求項７】
有限オートマトンを複数のコンフィギュレーションに分解する、請求項１から６のいずれか１項記載の方法。
【請求項８】
生成されたコンフィギュレーションを連続的にＰＡＥマトリックスにマッピングし、各コンフィギュレーション間で伝送すべき作業データおよび／または状態を記憶装置に格納する、請求項１から７のいずれか１項記載の方法。
【請求項９】
前記記憶装置をコンパイラにより指定またはまえもって用意させる、請求項１から８のいずれか１項記載の方法。
【請求項１０】
コンフィギュレーション中、ＶＰＵ外部のソースおよび／または内部の記憶装置からのデータを処理し、外部のソースおよび／または内部の記憶装置に書き込む、請求項１から９のいずれか１項記載の方法。
【請求項１１】
単一のデータ語よりも大規模なデータセット全体のために記憶装置を設ける、請求項１から１０のいずれか１項記載の方法。
【請求項１２】
進行中のコンフィギュレーションを処理するときにデータをコンパイラの指定により記憶装置に格納させる、請求項１から１１のいずれか１項記載の方法。
【請求項１３】
オペランドのための記憶装置、結果のための記憶装置、分岐および／または比較命令つまりたとえばIF, CASEなどのような条件、ループ（WHILE, FOR, REPEAT）から成る網、ならびに記憶装置を制御するためのアドレス発生器をオートマトンにより設ける、請求項１から１２のいずれか１項記載の方法。
【請求項１４】
状態に対し要求どおり記憶装置を割り当て、該割り当てにあたりアルゴリズム的に関連する状態と関連しない状態とを区別し、たとえば適正なファンクションを記述するためにアルゴリズム内で必要とされる状態と、使用されるハードウェアおよび／または選択されたマッピングによりまたは副次的な理由から発生する関連しない状態とを区別する、請求項１から１３のいずれか１項記載の方法。
【請求項１５】
Load/Storeオペレーションを、外部のアドレッシングつまり外部のコンポーネントとのデータ伝送を用いて、および内部のアドレッシングつまりＰＡＥ間のデータ伝送たとえばＲＡＭ−ＰＡＥとＡＬＵ−ＰＡＥとの間のデータ伝送を行う、請求項１から１４のいずれか１項記載の方法。
【請求項１６】
データ処理において第１のコンフィギュレーションを除去し、保護すべきデータを対応する記憶装置（ＲＥＧ）（メモリ、レジスタ、カウンタ等）に保持する、請求項１から１５のいずれか１項記載の方法。
【請求項１７】
第１のコンフィギュレーションを再びロードし、該コンフィギュレーションに割り当てられている事前に保護していたデータをアクセスする、請求項１から１６のいずれか１項記載の方法。
【請求項１８】
事前に保護されていたデータにアクセスするために第２のコンフィギュレーションをロードし、該第２のコンフィギュレーションはＲＥＧを適切なやり方で順序どおりに１つまたは複数のグローバルな記憶装置と接続し、たとえばアドレス発生器を用いて該グローバルな記憶装置にアクセスし、該アドレス発生器は有利にはグローバルな記憶装置に対するアドレスを発生して、書き込まれた記憶領域（PUSHAREA）を除去された第１のコンフィギュレーションに一義的に割り当て可能にする、請求項１から１７のいずれか１項記載の方法。
【請求項１９】
並列性および／またはベクトル化の可能性の表現のための変換（Par-Vec変換）を自動的に実行し、および／またはVECおよびPAR部分をペトリネットとして構成して、有利には個々の内容の完全な処理後に後続処理を制御する、請求項１から１８のいずれか１項記載の方法。
【請求項２０】
算術／論理命令を組み合わせ網にダイレクトにマッピングし、および／または、
ジャンプ（Jump/Call）を組み合わせ網にダイレクトに展開し、および／またはリコンフィギュレーションにより実現し、および／または、
条件およびコントロールフロー命令（ifなど）を組み合わせ網において完全に分解し、および／または処理し、および／または上位のコンフィギュレーションユニットへ転送し、該上位のコンフィギュレーションユニットは発生したステータスに従いリコンフィギュレーションを実行し、および／または、
Load/Storeオペレーションを別個のコンフィギュレーションにマッピングし、および／またはアドレス発生器により実現し、該アドレス発生器を用いて内部の記憶装置（REG{}）から外部の記憶装置への書き込みを行い、および／または外部の記憶装置および／または周辺機器から内部の記憶装置へのロードを行い、および／または、
Register-Moveオペレーションを組み合わせ網において各内部記憶装置（REG{}）間のバスを介して実現し、
Push/Popオペレーションを別個のコンフィギュレーションにより実現し、該オペレーションにより、組み合わせ網内における特定の内部レジスタおよび／または内部の記憶装置（REG{}）から外部の記憶装置への書き込みをアドレス発生器を用いて行わせ、および／またはそこからの読み出しを行わせ、該オペレーションを有利には本来のデータ処理コンフィギュレーション前または後に実行する、
請求項１から１９のいずれか１項記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
１．導入
本発明は特許請求の範囲の上位概念に記載の方法に関する。これによれば本発明は、リコンフィギュアラブルアーキテクチャをどのようにして最適に利用できるかという問題に取り組むものであり、たとえば所定の高級言語における命令をリコンフィギュアラブルアーキテクチャにおいてどのようにして最適に実行できるようにするかという問題に係わるものである。
【０００２】
いわゆる高級言語で記述されたデータ処理命令（プログラム）をデータ処理に利用される個々のアーキテクチャにおいて実行させるためにいわゆるコンパイラが知られており、コンパイラは高級言語の命令を、利用されるアーキテクチャにいっそう良好に整合された命令に変換する。その際に高度な並列処理を行うアーキテクチャを特別にサポートするコンパイラは、それゆえ並列処理コンパイラと呼ばれる。
【０００３】
従来技術による並列処理コンパイラは、セマフォおよび／または他の同期合わせ方式などたいていは特別な構造を利用する。この場合、一般にテクノロジー固有の方式が使われる。公知の手法は、機能的に記述されたアーキテクチャをそれに属する時間特性および命令的に記述されたアルゴリズムと組み合わせるのに適していない。このためいままで使用されてきた方法によれば、特殊な事例でしか申し分のない解決策が得られない。
【０００４】
リコンフィギュアラブルアーキテクチャ用のコンパイラたとえばリコンフィギュアラブルプロセッサ用のコンパイラは一般に、特定のリコンフィグアラブルハードウェアのために専用に作成されたマクロを使用し、マクロ作成のためにたいていはたとえばVerilog, VHDLまたはSystem-Cなどのようなハードウェア記述言語が使用される。そしてこのマクロは、あとで慣用の高級言語（たとえばC, C++）によりプログラムの流れの中から呼び出される（インスタンシエーション）。
【０００５】
粗粒度構造においてたいていは関数やスレッド全体をベースとして、プログラムパートを複数のプロセッサにマッピングするパラレルコンピュータ用のコンパイラが知られている。
【０００６】
さらにベクトルコンパイラも知られており、このコンパイラはたとえば大きい式の計算などのように十分に線形のデータ処理をベクトル化形式に変換し、それによってスーパースカラプロセッサやベクトルプロセッサ（たとえばPentium, Cray）において計算できるようにする。
【０００７】
本発明では、機能的または命令的にまとめられた演算規則を様々なターゲットテクノロジーたとえばＡＳＩＣ，リコンフィギュアラブルコンポーネント（ＦＰＧＡ，ＤＰＧＡ，ＶＰＵ，ChessArray, KressArray, Chameleon等、これらは以下ではＶＰＵという用語に統一）、シーケンシャルなプロセッサ（ＣＩＳＣ−ＣＰＵ／ＲＩＳＣ−ＣＰＵ，ＤＰＳ等、これらは以下ではＣＰＵという用語に統一）、ならびに並列計算機システム（ＳＭＰ，ＭＭＰ等）に自動的にマッピングする方法について説明する。たとえばこの関連で本出願人による以下の特許明細書を挙げておく：P 44 16 881.0-53, DE 197 81 412.3, DE 197 81 483.2, DE 196 54 846.2-53, DE 196 54 593.5-53, DE 197 04 044.6-53, DE 198 80 129.7, DE 198 61 088.2-53, DE 199 80 312.9, PCT/DE 00/01869, DE 100 36 627.9-33, DE 100 28 397.7, DE 101 10 530.4, DE 101 11 014.6, PCT/EP 00/10516, EP 01 102 674.7, PACT13, PACT17, PACT18, PACT22, PACT24, PACT25, PACT26US, PACT02, PACT04, PACT08, PACT10, PACT15, PACT18(a), PACT27, PACT19。これらを本願の参考文献とする。
【０００８】
ＶＰＵは基本的に多次元の均質または不均質のフラットなまたは階層状のセル（ＰＡＥ）のアレイ（ＰＡ）によって構成されており、それらのセルは任意の機能たとえば論理機能および／または算術機能および／またはメモリ機能および／またはネットワーク機能を実行することができる。各ＰＡＥのために一般に１つのロードユニット（ＣＴ）が設けられており、このユニットはコンフィギュレーションおよび場合によってはリコンフィギュレーションによってＰＡＥの機能を決定する。
【０００９】
本発明による方法は抽象的なパラレルマシンモデルをベースとしており、このモデルによれば有限オートマトンのほかインペラティブないしは命令的な問題記述も組み込まれ、種々のテクノロジーに対するインプリメントの効率的なアルゴリズム導出が可能となる。
【００１０】
従来技術によれば以下のコンパイラクラスが公知である：
古典的なコンパイラ、これはしばしばスタックマシンコードを生成し、実質的にノーマルなシーケンサとして構成されている非常に単純なプロセッサに適していた（N. Wirth, Compilerbau, Teubner Verlag）。
【００１１】
ベクトルコンパイラは、特別なベクトルコンピュータまたは極度にパイプライン化されたプロセッサに合わせてチューニングされた線形のコードを広範囲にわたり構築する。もともとコンパイラはCRAYなどのようなベクトルコンピュータのために利用することができた。Pentiumなどのような最新のプロセッサは、長いパイプライン構造をもつことから類似の方式を必要とする。個々の計算ステップはベクトル化されて（パイプライン化されて）実行されるので、コードはものすごく効率的になる。しかしながらパイプラインにとっては条件ジャンプが問題となり、それゆえジャンプ先を推定するジャンプ予測が有用となる。とはいえ推定が誤っているときには処理パイプライン全体を消去しなければならず、換言すればいかなるジャンプもこのようなコンパイラにとって問題を孕んでおり、本来の意味での並列処理は行われない。ジャンプ予測ならびに類似のメカニズムのためには、ハードウェアについてかなり余計なコストをかけなければならない。
【００１２】
粗粒度並列コンパイラは本来の意味ではほとんど存在せず、並列性は一般にはプログラマまたはオペレーティングシステムにより表され管理され、つまりたとえば種々のＩＢＭアーキテクチャ、ASCI RedなどのようなＭＭＰコンピュータシステムであればたいていはスレッドレベルで実行される。１つのスレッドは十分に独立性のあるプログラムブロックであり、あるいはそれどころか別のプログラムである。したがってスレッドは粗粒度で簡単に並列化することができる。同期合わせとデータ一貫性はプログラマもしくはオペレーティングシステムにより保証しなければならない。これは手間をかけてプログラミングしなければならず、並列コンピュータの計算能力の大部分を必要とする。しかもこのような粗い並列化によっても、本来実現可能な並列性のごく一部分しか実際には利用できない。
【００１３】
細粒度並列コンパイラ（ＶＬＩＷコンパイラ）は並列性を細粒度でＶＬＩＷ計算ユニットにマッピングしようと試みるものであり、このような計算ユニットによれば複数の演算を１クロックで並列に実行できるけれども、共通のレジスタセットをもっており、この制約されたレジスタセットが重大な問題点を成しており、その理由はこのレジスタセットがすべての演算に対しデータを供給しなければならないからである。しかもデータの依存性ならびに不一致の読み出し／書き込みオペレーション（LOAD/STORE）によって並列化がさらに難しくなる。
【００１４】
リコンフィギュアラブルプロセッサは多数の独立した計算ユニットを有しており、これらは一般に１つのフィールド内に配置されている。これらはたいてい共通のレジスタセットではなくバスによって互いに接続されている。これによって簡単にベクトル計算機構を構築できる一方、簡単に並列演算を実施することもできる。バス接続により慣用のレジスタコンセプトに反してデータ依存性が解消される。
【００１５】
本発明の課題は産業上の利用のための新規の方法を提供することにある。
【００１６】
この課題は独立請求項に記載の特徴により解決される。従属請求項には有利な実施形態が記載されている。
【００１７】
本発明によれば、リコンフィギュアラブルプロセッサ用コンパイラのためにベクトルコンパイラおよび並列コンパイラ（たとえばＶＬＩＷ）のためのコンセプトを同時に適用すること、つまりは細粒度レベルにおいてベクトル化および並列化することも提案される。
【００１８】
基本的な利点は、コンパイラが固定的に定められたハードウェア構造にマッピングを行う必要はなく、コンパイルされる個々のアルゴリズムのマッピングないしは変換に最適に整合するようハードウェア構造を本発明の方法によってコンフィギュレーションすることができる。
【００１９】
２．説明
アルゴリズム記述する実質的にいかなる方法論でも処理するための基礎として、有限オートマトンが用いられる。有限オートマトンの構造は図１に示されている。１つの単純な有限オートマトンは、組み合わせ網と、個々のデータ処理サイクル間のデータを一時記憶するレジスタステージとに分けられる。
【００２０】
有限オートマトンは複数の単純に組み合わせられた（つまりたとえば論理的および／または算術的な）データ操作を実行し、その後、安定状態に到達するようになり、これはレジスタ（セット）において表される。安定状態に基づき、次の処理ステップにおいてどのような次の状態に到達すべきか、さらには次の処理ステップにおいてどのような組み合わせデータ操作を実行すべきかが決定される。
【００２１】
たとえばプロセッサまたはシーケンサは有限オートマトンを表す。第１の処理ステップにおいてデータの減算を実行することができる。その結果が記憶される。次のステップにおいて減算結果に基づきジャンプを実行することができ、これによって結果の極性符号に応じて別の後続処理が実行されることになる。
【００２２】
図２に示されているように有限オートマトンにより、複雑なアルゴリズムを任意のシーケンシャルマシンにマッピングすることができる。図示されている複合有限オートマトンは、複合組み合わせ網とデータ格納用メモリとメモリ内のデータをアドレッシングするためのアドレス発生器とによって構成されている。
【００２３】
このようにしてどのような任意のシーケンシャルなプログラムであっても基本的に有限オートマトンとして捉えることができるが、その際にたいていは非常に大きい１つの網が発生する。したがって古典的な「フォン・ノイマン」アーキテクチャのプログラミングにおいて、つまりすべてのＣＰＵにおいて、組み合わせ演算がＣＰＵ内部のレジスタに合わせてそれぞれ個別の単純な一定のまえもって定められた一連の演算（OpCode）に分解される。この分解によって、一連の分解された組み合わせ演算を制御するための状態が発生するけれども、それらはもともとの組み合わせ演算それ自体においては存在しておらず、もしくは必要とされない。とはいえそのことから基本的にフォン・ノイマン型マシンの処理すべき状態を、組み合わせ網の算術状態つまり有限オートマトンのレジスタと区別しなければならない。
【００２４】
なお、ＶＰＵテクノロジー（これは基本的に文献PACT01, PACT02, PACT03, PACT04, PACT05, PACT08, PACT10, PACT13, PACT17, PACT18, PACT22, PACT24のうちのいくつかまたはすべてによって定義されている、これらを本願の参考文献とする）によれば、ＣＰＵの固定的なＯｐＣｏｄｅとは異なり、複合命令をフレキシブルなコンフィギュレーションなどにおいてマッピングすべきアルゴリズムに従いいっしょにコンパイルできるようになる。
【００２５】
２．１  コンパイラの動作
殊に有利であるのはコンパイラの動作にあたり、できるかぎり長い間ＰＡＥマトリックスにおいてリコンフィギュレーションされることなく実行されるよう複合命令を生成することである。
【００２６】
コンパイラはさらに有限オートマトンを有利にはインペラティブなソーステキストから、個々のＰＡＥマトリックスにきわめて良好に整合するよう生成し、つまり一般に粗粒度のロジック回路（ＡＬＵなど）および場合によっては存在する可能性のある微粒度の素子（ＶＰＵ内のＦＰＧＡセル、ステートマシン等）もきわめて良好に利用する演算がその中に設けられるようにする。その後、コンパイラにより生成された有限オートマトンは複数のコンフィギュレーションに分解される。
【００２７】
有限オートマトンの処理（解釈）はＶＰＵにおいて行われ、その際、生成された複数のコンフィギュレーションが連続的にＰＡＥマトリックスにマッピングされ、各コンフィギュレーション間で伝送すべき動作データおよび／または状態がメモリに格納される。この目的でPACT04から公知の方法もしくは対応するアーキテクチャを利用することができる。このメモリはコンパイラにより決定もしくは設定される。この場合、１つのコンフィギュレーションによって複数の命令が表される。１つのコンフィギュレーションは同時に多数のクロックに対しＰＡＥマトリックスの動作を決定し、それらのクロックの間、複数のデータがマトリックス内で処理される。それらはＶＰＵ外部のソースおよび／または内部メモリからのものであり、外部のソースおよび／または内部メモリに書き込まれる。この場合、内部メモリは従来技術に従いＣＰＵのレジスタセットを補い、それによればたとえばあるレジスタがメモリによって表され、レジスタごとに１つのデータ語ではなくデータセット全体がメモリごとに書き込まれる。
【００２８】
基本的に、実行中のコンフィギュレーションのデータおよび／または状態をコンパイラが決定するかたちでメモリに格納し、それによって次に実行されるコンフィギュレーションがそれらを利用できるようにすることもできる。
【００２９】
したがって命令に基づき並列化を行うコンパイラとの決定的な違いは、この方式によればＰＡＥマトリックスが以下のようにコンフィギュレーションおよびリコンフィギュレーションされることである。すなわちコンフィギュレーションされる一連の組み合わせ網がＶＰＵ上でエミュレートされるのに対し、慣用のコンパイラはロードされた一連の命令（ＯｐＣｏｄｅ）を組み合わせ、その際、１つの命令を１つの組み合わせ網とみなすことができる。
【００３０】
２．２  WHILE言語の実施例
次に、コンパイラの動作について単純な言語に基づき例を挙げて説明する。この場合、ベースにおいてすでに知られている言語を前提とするが、公知の刊行物［参考文献  学位論文Armin Nueckel"］では機能をスタティックな組み合わせ網にマッピングすることしか説明していないのに対し、本発明によればコンフィギュレーションへのマッピングないしは変換が行われ、これらのコンフィギュレーションはアルゴリズムおよび処理中に生じる状態に従い時間的な順序でＰＡＥマトリックスにマッピングされる。
【００３１】
プログラミング言語は、単純な論理結合および／または算術結合のほか命令"WHILE"が存在すること前提とし、これは以下の構文により定義されている：
WHILE
ここで考えられる構造：命令
命令シーケンス
ループ
１つの命令または命令シーケンスは既述のコンパイラ方式により組み合わせ網にマッピング可能である。
【００３２】
図３ａには組み合わせ網がそれに属する変数とともに示されている。この場合、網のあるステージ（０３０１）から次のステージ（０３０２）へと変わると、同じ変数（たとえばx1）の内容が変化する。図３ｂにはこの変化がたとえば命令
x1 := x1 + 1
に関して示されている。
【００３３】
ここではオペランドの読み出しと結果の格納のためのアドレッシングのために、アドレス発生器を命令の組み合わせ網と同期させることができる。処理される変数各々とともに、相応の新たなアドレスがオペランドと結果のために生成される（図３ｃ）。アドレス発生器の形式は基本的に任意であり、コンパイルされるアプリケーションのアドレッシングパターンに依存する。オペランドと結果について、共通の組み合わせられたまたは完全に別個のアドレス発生器をインプリメントすることができる。
【００３４】
一般にここで説明しているデータ処理モデルなどのようなデータ処理の場合、複数のデータがＰＡＥの１つの特定のコンフィギュレーション内部で処理される。したがって有利であるのはコンパイラを、たいていとはいわないが多くのアプリケーションにとって可能な簡単なＦＩＦＯモードのために構成することであり、これは少なくともデータメモリのために使用可能であり、この説明においてはデータならびにデータ処理の状態を格納するために（いわば慣用のＣＰＵにおける通常のレジスタの代用として）用いられる。換言すればメモリは、各コンフィギュレーションの間で変数を一時記憶するために用いられる。この場合も１つのコンフィギュレーションは通常のプロセッサの命令と類似しており、（たとえば複数の）メモリを通常のプロセッサのレジスタセットと対比させることができる。
【００３５】
２．３．３．  命令シーケンス
例として挙げる命令シーケンスは以下のようにして生成できる（図４ａ）：
x1 := 0;
WHILE TRUE DO
x1 := x1 + 1;
このシーケンスは、２．２．１による命令ならびにオペランドと結果のためのアドレス発生器によってマッピングされる。
【００３６】
有限のシーケンス
完全性を期するため、特別な形態のシーケンスをWHILE言語の定義された構造から離れて論じることにする。例として挙げる命令の有限のシーケンスは以下のようにして生成される：
FOR i := 1 TO 10
x1 := x1 + 1;
この種のシーケンスは２つの形式によってインプリメントされる：
ａ）WHILE構造（２．２．４）に従いｉを計算するための加算器とｘ１を計算するための別の加算器を生成すること。この場合、シーケンスはループとしてマッピングされ、再帰的に計算される（図５ａ）。
ｂ）ループを延ばすこと。これにより関数としてｉの計算が省略される。ｘ１の計算はｉ回インスタンシエーションされパイプラインとして構築され、これにより相前後して接続されたｉ個の加算器が生成される（図５ｂ）。
【００３７】
２．２．４  条件
WHILEを用いて条件を表すことができる。例：
2005508029.tif 000003
マッピングにより比較処理用の付加的なＰＡＥが生成される。比較結果はステータス信号により表され（PACT08のトリガを参照）、これは命令を処理するＰＡＥおよびアドレス発生器により評価される。図４ｂには結果として得られるマッピングが示されている。
【００３８】
条件（ここではWHILE、よくわかるよう一般的にいえばIF; CASEなど他の命令によっても実現可能）により後続処理に利用できるステータスが生成され（DE 197 04 728.9）、および／またはこのステータスはＣＴまたはローカルなロードコントローラ（DE 196 54 846.2）に送信可能であり、そこにおいてステータスから別のプログラムの流れおよび場合によっては未処理のリコンフィギュレーションが導出される。
【００３９】
２．２．５  基礎的な手法
上述の手法に従い各プログラムは以下のように構築されたシステムにマッピングされる：
１．オペランド用のメモリ（ＣＰＵのレジスタと対比）
２．結果用のメモリ（ＣＰＵのレジスタと対比）
３．ａ）指定および／またはｂ）比較命令つまりはIF, CASE, ループ（WHILE, FOR, REPEAT）から成る網
４．１と２によるメモリを制御するためのオプションのアドレス発生器
２．２．６  各状態との対応
既述のコンパイラの目的に関して、アルゴリズムに関連する状態と関連しない状態とが区別される。各状態はＶＰＵテクノロジーにおいて通例、ステータス信号（たとえばPACT08におけるトリガ）および／またはハンドシェーク（たとえばPACT02におけるRDY/ACK）によって表される。一般に各状態は（FPGA, DPGA, Chameleonコンポーネント、Morphicsなど他のテクノロジーにおいて）任意の信号、信号群および／またはレジスタによって表すことができる。明細書の大部分はＶＰＵにフォーカスをあてて説明するけれども、ここで開示されているコンパイラ手法をそのようなものもターゲットにして設計することができ、非関連状態は使用されているハードウェアおよび／または選択されたマッピングまたは他の副次的な理由から発生する。したがってこれらはマッピング（つまりハードウェア）にとって重要である。
【００４０】
関連状態だけにデータを与えればよい。したがってそれらの状態はデータといっしょにメモリに格納される。なぜならばそれらの状態はデータとの比較の結果として発生したものであったり、あるいはオペランドとしてデータとともに次の処理サイクルに必要とされるからである。
【００４１】
これに対して非関連状態は局所的および／または時間的にローカルに必要とされるので、メモリに記憶する必要がない。
【００４２】
例：
ａ）比較の状態情報はデータの別の処理にとって重要であり、なぜならば実行すべき機能はそれらによって決定されるからである。
ｂ）シーケンシャルな除算器がたとえば、シーケンシャルな除算だけしかサポートしないハードウェアへの除算命令のマッピングにより形成されるものとする。これにより除算における計算ステップを表す状態が生じる。この状態は非関連状態である。なぜならばアルゴリズムにとっては結果（したがって実行された除算）だけしか必要とされないからである。したがってこの事例では、結果と時間情報（つまりアベイラビリティ）だけしか必要とされない。このような関連状態と非関連状態とをコンパイラが区別すると有利である。
【００４３】
時間情報はたとえばPACT01, 02, 13によるＶＰＵテクノロジーにおいてはＲＤＹ／ＡＣＫハンドシェークによって得られる。しかしこれについてここで述べておくと、ハンドシェークも非関連状態を成しており、その理由はこれはデータの有効性だけを通報するものだからであり、その際、やはり残りの関連情報は有効なデータが存在するよう低減される。
【００４４】
２．２．７  時間との対応
多くのプログラミング言語において、殊にＣのようなシーケンシャルな言語において、厳密な時間順序が言語によって暗黙的にまえもって定められる。つまりシーケンシャルなプログラミング言語の場合、このことはたとえば個々の命令の順序によって行われる。これがプログラミング言語および／またはアルゴリズムによって必要とされるかぎり、時間情報がＲＤＹ／ＡＣＫやＲＥＱ／ＡＣＫなどのような同期モデルあるいはDE 101 10 530. 4などのようなタイムスタンプ方式にマッピングされるよう、コンパイラ手法が設計される。
【００４５】
換言すれば、シーケンシャルな言語の暗黙的な時間情報がハンドシェークプロトコルにマッピングされ、その際にハンドシェークプロトコル（ＲＤＹ／ＡＣＫプロトコル）によって時間情報が伝送され、たとえば命令の順序が保証される。
【００４６】
たとえば以下のforループは、変数inputstreamがループ実行ごとにＲＤＹによって確認されたときのみ実行され反復される。ＲＤＹが生じなければ、ループ実行はＲＤＹが到来するまで停止される。
while TRUE
s := 0
for i := 1 to 3
s := s + inputstream;
したがって命令処理によってのみ制御されるというシーケンシャルな言語の特性がコンパイルにおいて、データストリームによる処理もしくはデータの存在を制御するデータフロー方式と結合される。換言すれば、演算を実行可能でありデータを利用できるときのみ命令および／または指示（たとえばs := s + inputstream;）が処理される。
【００４７】
なお、この手法によっても通常、高級言語のシンタックスやセマンティクスは変化しない。つまり既存の高級言語のコードを新たにコンパイルしなおすことでＶＰＵにおいて問題なく実行させることができる。
【００４８】
２．２．８  データのロードおよび記憶
Load/Store（ロード／ストア）オペレーションの基礎として以下のことに留意されたい。
【００４９】
以下のアドレッシング形式がそれぞれ異なるかたちで処理される：
１．外部のアドレッシングすなわち外部のコンポーネントによるデータ転送
２．内部のアドレッシングすなわち各ＰＡＥ間のデータ転送たとえばＲＡＭ−ＰＡＥとＡＬＵ−ＰＡＥとの間のデータ転送
さらにデータ処理とデータのロードおよびストアの時間的な分離に殊に注目することができる。バス伝送が内部伝送と外部伝送に分解される。
ｂｔ１）外部の読み出しアクセス（ロードオペレーション）が分離され、１つの可能な実施形態によれば別個のコンフィギュレーションに変換される。データは外部記憶装置から内部メモリに転送される。
ｂｔ２）内部アクセスがデータ処理と結合され、つまり内部メモリ（レジスタオペレーション）がデータ処理のために読み出されもしくは書き込まれる。
ｂｔ３）外部書き込みアクセス（ストアオペレーション）が分離され、１つの可能な有利な実施形態によればこれも別個のコンフィギュレーションに変換される。データは内部メモリから外部記憶装置へ転送される。
【００５０】
ここで重要であるのは、ｂｔ１，ｂｔ２，ｂｔ３つまりデータのロード（Ｌｏａｄ）、データの処理（データ処理およびｂｔ２）およびデータの書き込み（ｂｔ３）を様々なコンフィギュレーションに変換することができ、これらを必要に応じてそれぞれ異なる時点で実行することができる。
【００５１】
この手法について以下の例に基づき説明する：
2005508029.tif 000004
この関数はコンパイラにより３つのパートもしくはコンフィギュレーション（subconfig）に変換できる：
example#dload: データを外部から（メモリ、周辺機器などから）ロードし、それらを内部メモリに書き込む。内部メモリは#rおよび元の変数の名前で表される。
example#process: 本来のデータ処理に対応。これによりデータが内部のオペランドから読み出され、結果が再び内部メモリに書き込まれる。
example#dstore: 結果が内部メモリから外部記憶装置（メモリ、周辺機器等）に書き込まれる。
2005508029.tif 000005
この手法の重要な効果は、オペランド読み出しにあたりi*j = 100 * 100 = 10,000回の外部アクセスの代わりにi+j = 100 + 100 = 200回の外部アクセスだけが実行されることである。しかもそれらのアクセスは依然として完全に線形であり、このことによって最近のバスシステム（Burst）および／または最近のメモリ（SDRAM, DDRAM, RAMBUS等）であれば伝送速度が格段に加速される。
【００５２】
オペランドに対しそれぞれ異なるメモリが割り当てられたので、内部のメモリアクセスは並列に行われる。
【００５３】
結果書き込みのためi=100回の外部アクセスが必要であり、これもやはり直線的に最高のパフォーマンスで実行可能である。
【００５４】
データ伝送の回数が事前に既知でなければ（たとえばWHILEループの場合）あるいは非常に多くの回数であれば、必要に応じてサブプログラムを呼び出してオペランドをあとからロードしたり、あるいは結果を外部に書き込むようにする手法を利用することができる。この目的で１つの有利な実施形態によれば（付加的に）ＦＩＦＯの状態が問い合わせられる：ＦＩＦＯが空であれば'empty'、ＦＩＦＯがいっぱいであれば'full'。これらの状態に応じてプログラムの流れが反応する。なお、特定の変数（たとえばai, bi, xi）はグローバルに定義されている。パフォーマンスの最適化のため、既述の方式に従いスケジューラがexample#dloada, example#dloadbをexample#processの呼び出し前に既に実行して、データをまえもってロードしておくようにすることができる。同様にexample#dstore(n)をexample#process終了後にさらに呼び出して、r#xを読み出すようにすることもできる。
2005508029.tif 000006
サブプログラム呼び出しならびにグローバル変数の管理は、リコンフィギュアラブルアーキテクチャにとって比較的煩雑である。したがって１つの有利な実施形態によれば後続の最適化を実行することができ、その際、すべてのコンフィギュレーションが十分に独立して実行され、完全に処理された後で終了する（terminate）。データb[j]は何回も必要とされるので、example#dloadbをそれに応じて何回も実行しなければならない。このためたとえば２つのオプションが設けられる：
オプション１：example#dloadbは実行されるたびに終了し、再スタートのたびにexample#processにより新たにコンフィギュレーションされる。
オプション２：example#dloadbはエンドレスで実行され、example#processによって終了させられる。
'idle'中、コンフィギュレーションは非アクティブ状態（待機状態）にある。
2005508029.tif 000007
待ちサイクルを避けるため、コンフィギュレーションが自身のタスクを一時的にそれ以上果たすことができなくなるとただちに、それらのコンフィギュレーションを終了させることもできる。対応するコンフィギュレーションはリコンフィギュアラブルコンポーネントから取り除かれるが、スケジューラの中にはとどまり続ける。この目的で以下では命令'reenter'が使用される。関連する変数は終了前に保護され、コンフィギュレーションが繰り返されるときに再び生成される：
2005508029.tif 000008
２．３  マクロ
高級言語の比較的複雑な機能たとえばループなどは一般にマクロにより実現される。この場合、マクロはコンパイラによりまえもって設定され、変換時点にインスタンシエーションされる（図４参照）。それらのマクロは高級言語の単純な言語構造によって構築されているかまたはアセンブラレベルで構築されている。既述のアルゴリズムに簡単に整合できるようにする目的で、マクロをパラメータ化することができる（図５の０５０２参照）。これらのマクロをここでも組み入れることができる。
【００５５】
２．４  フィードバックループおよびレジスタ
アルゴリズムを１つの組み合わせ網にマッピングする際、制御されずに揺動する遅延のないフィードバックが発生する可能性がある。実際にインプリメントされるPACT02によるＶＰＵテクノロジーの場合、これはＰＡＥの構造によって回避され、それによれば分離用に少なくとも１つのレジスタがたとえばＰＡＥ内に固定的に定義されている。
【００５６】
遅延のないフィードバックは一般に、生成された組み合わせ網のグラフ分析によって検出することができる。それに基づき、遅延のないフィードバックが発生するデータ経路中に所期のように分離用のレジスタが挿入される。このようにしてコンパイラはレジスタ手段もしくはメモリ手段を管理することができる。
【００５７】
ハンドシェークプロトコル（たとえば２．２．７によるＲＤＹ／ＡＣＫ）を使用することにより、レジスタを挿入しても計算の適正な機能が保証される。
【００５８】
２．５  プロセッサモデル／時分割多重（ＴＤＭ）
基本的に、実際に形成されるＰＡＥマトリックス各々は有限のサイズしかもっていない。それゆえ以下のステップでは２．２．５における段落４のａ／ｂによるアルゴリズムを、ＰＡＥマトリックスを成すよう相前後してコンフィギュレーションされる複数のコンフィグレーションに分割する必要がある。この目的は一般に、網においてできるかぎり多くのデータパケットをコンフィギュレーションしなおす必要なく計算することである。各コンフィギュレーションの間に一時記憶が行われ、その際、一時記憶装置はＣＰＵにおけるレジスタのようにシーケンシャルに実行される各コンフィギュレーション間のデータを記憶する。
【００５９】
このようにしてコンフィギュレーション、ＰＡＥマトリックスにおけるデータ処理ならびにメモリにおける一時記憶によって、シーケンシャルなプロセッサモデルが構築される。換言すればＶＰＵテクノロジーにおいて既述のコンパイルにより、Opcodeがシーケンシャルに実行されるのではなく複合的なコンフィギュレーションが実行される。ＣＰＵの場合にはOpcodeによって一般に１つのデータ語が処理されるのに対し、ＶＰＵテクノロジーの場合には複数のデータ語（データパケット）がコンフィギュレーションによって処理される。これによりリコンフィギュレーションの手間とデータ処理との関係が改善されることから、リコンフィギュアラブルアーキテクチャの効率が高まる。
【００６０】
これと同時にＶＰＵテクノロジーの場合には、レジスタの代わりにメモリが使用される。その理由は、各コンフィギュレーションの間でデータ語ではなくデータパケットが処理されるからである。
【００６１】
このメモリをランダムアクセスメモリ、スタック、ＦＩＦＯあるいはその他の任意のメモリアーキテクチャとして構成することができ、この場合、一般にＦＯＦＯにより最良かついちばん簡単に実現可能な構成が得られる。
【００６２】
ここでデータはコンフィギュレーションされるアルゴリズムに従いＰＡＥマトリックスにより処理され、１つまたは複数のメモリに格納される。ＰＡＥマトリックスは所定量のデータを処理した後にコンフィギュレーションしなおされ、新たなコンフィギュレーションにより一時的な結果がメモリから取り出され、プログラムの実行が継続される。この場合、外部記憶装置および／または周辺機器から新たなデータを付加的に計算へ流し込むこともできるし、結果を外部記憶装置および／または周辺機器へ書き込むこともできる。
【００６３】
換言すれば、データ処理の一般的な流れは内部のＲＡＭからの読み出し、マトリックスにおけるデータの処理ならびに内部のメモリへのデータの書き込みであり、その際、データを処理するために任意の外部のソースまたはデータ伝送の宛先も内部メモリに加えてあるいはその代わりに使用できる。
【００６４】
ＣＰＵにおける「シーケンス」がOpCodeの新たなロードとして定義されているのに対し、前述のＶＰＵの「シーケンス」によればやはりコンフィギュレーションにより（リ）コンフィギュレートが行われるものとして定義される。とはいえこのことは、特定の条件のもとではなくフィールドの部分が慣用の意味でシーケンサとして作動できることを意味するものではない。
【００６５】
いつおよび／またはどのようにシーケンス処理を行うかという情報、つまり次にどのコンフィギュレーションをコンフィギュレートすべきかという情報は、様々な情報によって表現することができ、それらは個別にまたは組み合わせて使用することができる。たとえば情報を導出するために以下のストラテジを単独におよび／または組み合わせてもしくは択一的に用いるのが有用である：
ａ）コンパイラにより変換時点に定義する；
ｂ）イベント網により定義する（トリガ、DE 197 04 728.9）、ここでイベント網は内部および／または外部の状態を表すことができる；
ｃ）メモリの占有率による（トリガ、DE 197 04 728.9, DE 196 54 846.2-53）
２．５．１  プロセッサモデルに及ぼされるＴＤＭの影響
アルゴリズムの分割により関連状態がはっきりと決定されることになり、それらはそれぞれ異なるコンフィギュレーションの間にメモリに格納される。状態が１つのコンフィギュレーション内でしか重要でなければ（局所的に関連する状態）それを記憶する必要はなく、このことは有利にはコンパイラ手法によって考慮される。
【００６６】
とはいえ、実行すべきプログラムをデバッグする目的で有用であるのは、この情報を記憶してデバッガがそれにアクセスできるようにすることである。これについてはDE 101 42 904.5を参照されたい。これも本願の参考文献とする。
【００６７】
さらに付加的な情報が重要となる場合があり、これはタスク切替メカニズムが（たとえばオペレーションシステムまたは割り込みソースにより）適用され、現在実行されているコンフィギュレーションが中断されて別のコンフィギュレーションがロードされるとき、および／または中断されていたコンフィギュレーションをあとの時点で続けようとするときである。以下でこれについて詳しく説明する。
【００６８】
簡単な例を挙げて、局所的に関連する状態に対する判別特徴を示すことにする：
ａ）"if () then ... else ..."タイプの分岐は単一のコンフィギュレーションに完全に収まり、つまり２つのデータ経路（分岐）はいっしょにこのコンフィグレーション内で完全にマッピングされる。比較の結果得られた状態は関連性があるけれども局所的であり、それというのもこの状態は以下のコンフィギュレーションではもはや必要とされないからである。
ｂ）同じ分岐は大きすぎて、単一のコンフィギュレーションには収まりきらない。この場合にはデータ経路全体をマッピングするために複数のコンフィギュレーションが必要である。このような状況では状態はグローバルに関連性があり、記憶して個々のデータに割り当てる必要がある。それというのも後続のコンフィギュレーションにより、データの後続処理において比較の個々の状態が必要とされるからである。
【００６９】
２．６  タスク切替
場合によってはオペレーティングシステムの投入により、状態の考察およびそれに対する対応への付加的な影響が及ぼされる。オペレーティングシステムは複数のタスクを管理するためにたとえばタスクスケジューラを利用し、これによってマルチタスクが提供される。タスクスケジューラは特定の時点でタスクを中断させて別のタスクをスタートさせ、そのタスクの処理後、中断されたタスクに戻って引き続き処理を行わせる。ここではタスクの処理に対応させることのできる１つのコンフィギュレーションが処理完了後のみ、つまりそのコンフィギュレーションサイクル内で処理すべきすべてのデータと状態が格納されているときにだけ終了することが保証されているかぎり、局所的に関連する状態を格納しないままにしておくことができる。この手法すなわちコンフィギュレーションの処理完了ならびに後続のタスク切替は、リコンフィギュアラブルプロセッサの動作に関して有利なやり方であるし、通常のプロセッサのシーケンスに実質的に対応するものであり、通常のプロセッサも現在処理中の命令を最初に実行完了させてからタスクを切り替える。
【００７０】
しかしながらたいていの適用事例に関しては、たとえばリアルタイムアプリケーションなどにおいては、タスク切替要求に対してきわめて短いリアクションが必要とされる。ここで有用となる可能性があるのは、完全な実行完了前にコンフィギュレーションを中断させることである。タスクスケジューラがコンフィギュレーションをそれが完全に実行完了する前に中断させるのであれば、局所的な状態および／またはデータを記憶させなければならない。さらにこのことが有利になるのは、あるコンフィギュレーションの実行完了時点を予測できないときである。コンフィギュレーションが（たとえばエラーなどによって）まったく終了しないという周知の停止の問題およびリスクと関連してこのことがさらに有用となり、これによってシステム全体のデッドロックを回避できるようになる。したがってここではタスク切替を考慮しながら、関連のある状態をタスク切替およびデータ処理の新たな適正な開始に必要なものとみなさなければならない。したがってタスク切替にあたり結果用のメモリおよび場合によってはオペランド用のメモリも保護すべきであり、あとの時点でつまりそのタスクに戻るときに再びそれらを生成しなければならない。このことはPUSH/POP命令と退避可能であり、従来技術による方式が行われる。さらにデータ処理の状態を保護する必要があり、つまり最後に完全に処理されたオペランドに対するポインタを保護しなければならない。ここではたとえばPACT18を参照されたい。
【００７１】
タスク切替の最適化に応じてたとえば２つのオプションがある：
ａ）中断されたコンフィギュレーションが新たにコンフィギュレートされ、オペランドだけがロードされる。データ処理は、コンフィギュレーションの処理がまだまったく開始されていなかったかのように始まる。換言すれば、単にすべてのデータ計算が最初から実行され、その際、場合によっては計算がすでに事前に実行されている。このオプションは簡単であるが効率的でない。
ｂ）中断されたコンフィギュレーションが新たにコンフィギュレートされ、その際、オペランドおよびすでに計算された結果が個々のメモリにロードされる。データ処理は、完全には計算されなかったオペランドのところから続けられる。このやり方は非常に効率的であるが、コンフィギュレーション処理中に発生する付加的な状態が場合によっては重要となことを前提としており、これはたとえば最後に完全に計算されたオペランドを指す少なくとも１つのポインタを保護しなければならないときであり、それによって新たなコンフィギュレーションが行われた後にその継承において新たに開始できるようにするときである。
【００７２】
２．７  コンテキスト切替
あとで説明するコンテキスト切替によって、関連データを管理するための特別に有利な変形実施形態が提供される。タスク切替および／またはコンフィギュレーションの実行ならびにその切替にあたり（たとえば特許出願DE 102 06 653.1を参照、これを本願の参考文献とする）必要とされる可能性があるのは、たとえば単に最終値を表すだけであったりすることから一般に動作データといっしょにはメモリに記憶されないデータあるいは状態を、後続のコンフィギュレーションのために保護することである。
【００７３】
本発明によれば有利にはインプリメントされたコンテキスト切替は、１番目のコンフィギュレーションが取り除かれ、保護すべきデータが対応するメモリ（ＲＥＧ）（メモリ、レジスタ、カウンタ等）に残されるようにして実行される。
【００７４】
その後、２番目のコンフィギュレーションをロードすることができ、これによりＲＥＧが定義された順序に従い適切なかたちで１つまたは複数のメモリと接続される。コンフィギュレーションはたとえばアドレス発生器を利用して１つまたは複数のグローバルメモリにアクセスすることができる。したがって個々のメモリロケーション各々をまえもってコンパイラにより決定させる必要がなく、および／またはメモリとして構成されたＲＥＧにアクセスする必要がない。各ＲＥＧ間のコンフィギュレーションされた接続に従いＲＥＧの内容が定義された順序どおりにグローバルメモリに書き込まれ、その際、個々のアドレスはアドレス発生器により設定される。アドレス発生器は、既述のメモリ領域（PUSHAREA）を取り除かれた１番目のコンフィギュレーションに割り当てることができるよう、１つまたは複数のメモリに対するアドレスを発生する。したがって様々なコンフィギュレーションに対し種々のアドレス空間を設けるのが有利である。この場合、コンフィギュレーションは慣用のプロセッサのPUSHに対応する。その後、別のコンフィギュレーションによりリソースが用いられる。
【００７５】
その後、１番目のコンフィギュレーションを再びスタートさせるようにする。そのまえに３番目のコンフィギュレーションがスタートし、これにより１番目のコンフィギュレーションのＲＥＧが定義された順序で互いに接続される。
【００７６】
１つまたは複数のグローバルメモリをアクセスする目的で、および／またはメモリとして構成されたＲＥＧをアクセスする目的で、コンフィギュレーションはやはりたとえばアドレス発生器を使用することができる。
【００７７】
その際に有利であるのは、１番目のコンフィギュレーションに割り当てられたPUSHAREAへの適正なアクセスが行われるよう、アドレス発生器がアドレスを発生させることである。発生されたＲＥＧのアドレスおよびコンフィギュレーションされるその順序によれば、ＲＥＧのデータが元の順序でメモリからＲＥＧへ書き込まれる。このコンフィギュレーションは慣用のプロセッサのPOPに対応する。その後、１番目のコンフィギュレーションが再びスタートする。
【００７８】
要約すると、コンテキスト切替は有利には次のようにして実行される。すなわちPUSH/POPとして知られている周知のプロセッサアーキテクチャと類似して動作する特別なコンフィギュレーションのロードによって、保護すべきデータがグローバルメモリによって交換される。PUSH/POP交換コンフィギュレーションを用いグローバルメモリを介したこのようなデータ交換は特別に重要であるとみなされる。
【００７９】
次にこの機能について１つの例に基づき説明する：
１つの関数によって２つの数列が加算され、それらの数列の長さは変換時点では未知であり実行時にはじめてわかる。
2005508029.tif 000009
この関数が実行中に中断され、たとえばタスク切替により、あるいはｘのために用意されているメモリがいっぱいになったために中断される。本発明によればa, b, xはこの時点でメモリ内に存在している。しかしiおよび必要に応じて長さを保護しなければならない。この目的でコンフィギュレーションexampleが終了させられ、レジスタ内容が維持され、コンフィギュレーションpushが開始され、これによりiと長さがレジスタから読み出され、メモリに書き込まれる。
2005508029.tif 000010
実行後、pushが終了させられ、その際、レジスタを消去することができる。別のコンフィギュレーションが実行される。いくらか後、コンフィギュレーションexampleが再び開始される。その前にコンフィギュレーションpopが開始され、これによりレジスタ内容が再びメモリから読み出される。
2005508029.tif 000011
実行後、popが終了させられ、レジスタ内容が保持される。コンフィギュレーションexampleが再び開始される。
【００８０】
２．８  アルゴリズムの最適化
既述の変換手法によって制御構造がアルゴリズム構造と分離される。たとえば１つのループは本体（WHILE）とアルゴリズム構造（命令）に分解される。有利にはアルゴリズム構造を、オプションとして分離処理のあとにつなげられる付加的なツールによって最適化することができる。たとえばあとにつなげられる代数的ソフトウェアによって、プログラミングされたアルゴリズムを最適化し最小化することができる。この種のツールはたとえばAXIOM, MARBLEなどの名称で知られている。最小化によって、アルゴリズムのいっそう高速な処理および／またはきわめて抑えられた所要スペースを実現することができる。その後、最適化の結果が再びコンパイラに導かれ、それに応じて後続処理される。さらにここで言及しておくと、最近のコンパイラ（フロントエンド）には（やはり部分的に代数的な）アルゴリズムに対する複数の最適化がすでにインプリメントされており、当然ながらそれらをここで述べた手法においてそのまま利用することができる。
【００８１】
なお、ここで敢えて述べておくと、既述のやり方および段落２．２．７「時間との対応」および２．３「マクロ」もPACT20によるコンパイラに適用することができる。これに関連してPACT20も本願の参考文献とする。
【００８２】
３．たとえばＶＬＩＷアーキテクチャをもつ従来技術によるプロセッサに対する適用性
ここで殊に指摘しておきたいのは、ＰＡＥマトリックスの代わりにたとえばＶＬＩＷプロセッサにおいて一般的であるような従来技術による複数の算術論理ユニットから成るアレイおよび／またはたとえばマルチプロセッサシステムなどにおけるような複数の完全なプロセッサから成るアレイも利用することができる。この場合、特別な事例として単一のＡＬＵの利用が挙げられ、したがって普通のＣＰＵにもこの手法を適用できる。
【００８３】
論文[参考文献  論文Armin Nueckel]によれば、WHILE言語をセマンティクス的に適正な有限オートマトンに変換できるようにした方法が開発された。さらに有限オートマトンを「サブプログラム」として使うこともできるし、その逆も可能である。これによってコンフィギュレーションをたとえばＣＰＵ、対称型マルチプロセッサ、ＦＰＧＡ、ＡＳＩＣ、ＶＰＵなどのような様々な実装テクノロジーにマッピングできるようになる。
【００８４】
たとえば、アプリケーションの一部分にそれぞれ最適に整合されたハードウェアを割り当てることができるし、あるいは個々の適正を求めて良好な適正かそうでもないかという判定に基づき最適なハードウェアを割り当てることができる。その際に有利には一時的なリソース割り当ておよびリソース予約も考えられる。換言すればたとえばあるデータフロー構造がデータフローアーキテクチャに割り当てられる一方、存在するならばおよび／または利用できるならばシーケンシャルな構造がシーケンサにマッピングされる。
【００８５】
個々のアルゴリズムに対するリソース割り当てにおいて挙げられる問題はたとえば、割り当てを管理するための"Job Assignment"アルゴリズムによって解決することができる。
【００８６】
４．インプリメンテーション
本発明によるコンパイラのインプリメンテーションは「通常の」シーケンシャルなプログラミング言語たとえばＣやＰａｓｃａｌなどを前提としている。これらの言語がもつ特性によれば、そのシーケンシャルなキャラクタゆえに時間順序が暗黙的かつ意図的に言語の定義それ自体によって生成される：
例Ａ：
行１：  i++
行２：  a = i * b
行３：  x = p - a
行４：  j = i * i
言語の定義により、行１は行２よりも行３よりも行４よりも前に実行されるとしっかりとまえもって定められている。とはいうものの、行４を行１の直後に実行することもでき、したがって行４を行２および行３と並列に処理することができる。
【００８７】
換言すれば、シーケンシャルな言語によりさらに別の作為的かつアルゴリズムに基づかない状態が構築される。ここで重要なのは、例Ａにおける計算の適正な時間的順序だけである。ｉが正しく定義されてはじめて、つまり行１が実行されてから、行４の計算が許可される。行２はｉが適正に定義されてはじめて（つまり行１が処理されてから）処理してよい。行３は行２の結果（変数ａ）が必要であり、したがってこれが適正に定義されてはじめて計算が許可される。したがってデータ依存性によっても特別な状態は生じない。
【００８８】
行２と行３における変数ａのデータ依存性に基づき（行３はオペランドとしてａを使用、ａは行２の結果）コンパイラにより自動的に、並列化もしくはベクトル化を表す以下の変換（arVec変換）を実行することができる。
行２：    VEC{a = i * b
行３：        x= p - a}
ここでVECは、’;’で分離される各式により相前後して処理され、中括弧内の式は基本的にパイプライン化できることを意味する。VECのあとのデータ処理が継続されるよう、有利にはすべての計算はVEC{}の終了時に実行され完了していなければならない。
【００８９】
いっそうよいのは、データ構造の内部表現としてコンパイラにおいて２つの式を１つのベクトルとして表すことである：
VEC{a = i * b; x = p - q}
行４は簡単なベクトルを表す：
VEC{j = i * i}
行４は行２および行３と同時に計算できるので、以下のようにして並列性を表現することができる：
PAR{{VEC{a = i * b; x = p - a}; VEC{j = i * i}
PARは、’{..}’で分離された各式を同時に処理できることを意味する。PARよりあとのデータ処理が継続されるよう、有利にはPAR{}の終了時にすべての計算が実行され完了していなければならない。
【００９０】
行１をいっしょに取り込むならば以下の通りとなる：
VEC{i++; PAR{{VEC{a = i * b; x = p - a}} {VEC{j = i * i}}}}
VEC{j = i * i}はただ１つの要素をもつベクトルとして表されるので、以下のように記述することもできる：
VEC{i++; PAR{{VEC{a = i * b; x = p - a}} {j = i * i}}}
別の例により真の状態を示す。
例Ｂ：
2005508029.tif 000012
ここで行６は行２と行３の計算後にのみ実行することができる。行４と行６の計算は択一的に行われる。つまり行３の状態はその後のデータ処理に関連する（関連状態）。
【００９１】
条件付けられた状態は変換にあたりIFによって表現できる：
2005508029.tif 000013
要約すると、
2005508029.tif 000014
別の関連状態はループにより生成される：
例Ｃ：
2005508029.tif 000015
行３の実行はループの終了後、はじめて許可される。つまり条件付きジャンプにおいて関連状態である。
【００９２】
ループの最初の変換は以下の通りである：
2005508029.tif 000016
行３および行４は並列に計算することができる。なぜならば行４は行３の結果に依存しないからである：
PAR{{a=a*i}{i++}}
行５は生成されたPARをもつベクトルである。その理由は、各値の計算が完全に終了してはじめて、ループへのジャンプが許可されるからである（つまりここでは時間的な依存性が存在する）。
VEC{PAR{{a=a*i}{i++}}; jump loop}
したがってこの条件に対して以下のようになる：
loop:  IF{{i>=100}{jump exit}{VEC{PAR{{a=a*i}{{i++}}; jump loop}}}
行１は条件付きベクトルである。これは条件の前に実行しなければならない（IFはオペランドとしてiを使用し、iは行１の結果である）。行６もはやり条件付きベクトルである。なぜならばａはオペランドとして使用され、ａは条件の結果だからである。
したがって以下の通りとなる（見やすく記述してある）：
2005508029.tif 000017
VEC{}とPAR{}の内容は単純な組み合わせ網とみなすことができる。有利にはVECとPARはペトリネットとして構成され、たとえば有利には個々の内容の完全な処理後に後続処理が制御されるようになる。
【００９３】
VECとPARは単純な組み合わせ網とみなせることから、ループ状態を保護する必要性が生じる。つまりこの場合には実際に、有限オートマトンを作り出すことが必要である。
【００９４】
この目的で命令REG{}によりレジスタに変数が格納される。これにより組み合わせ網VECとPACをレジスタREGと共働させて有限オートマトンが生成され、これはアルゴリズムに精確に一致するよう構成されている：
2005508029.tif 000018
ここで特に指摘しておくべきことは、本出願人のＶＰＵテクノロジー（PACT21参照）によれば各ＰＡＥに入力レジスタおよび／または出力レジスタが設けられており、組み入れられたハンドシェークプロトコル（RDY/ACK）により時間の正確さおよびデータの可用性が保証されている。この点からすれば有利には、VEC{}またはPAR{}から出たときにそれらの内部データ処理が完了していなければならないという要求が、あとで使用される変数すべてについて自動的に満たされる（データ処理が終わらなかったとしたら、以降の計算ステップは終了およびデータの到来を待つことになる）。組み込まれたレジスタによりフィードバックの揺動も排除される。したがってこのテクノロジーのために以下の式が適正である：
VEC{PAR{{a=a*i}{i++}} jump loop}
上述の構成をもたないまたは一部分しかもたない他のテクノロジーについては、この式を以下のように表すようにする：
VEC{PAR{{a=a*i}{i++}}; REG{a;i}; jump loop}
ここで述べておきたいのは、いずれにせよこの書式により本出願人のＶＰＵテクノロジーにおいても、アルゴリズムをリコンフィギュアラブルプロセッサへ適正かつ最適にマッピングできるようになる。
【００９５】
REGを組み合わせ網VECおよびPAR内で利用することができる。厳密にみればこれによってVECとPARは組み合わせ網の特性を失うことになる。しかしながら抽象的には、REGを組み合わせ網における１つの複合要素（REG要素）とみなすことができ、これは固有の実行時間に基づいている。後続の要素の処理はREG要素の計算終了に依存して行われる。このような概念的な不正確さを意識して以下ではVECとPAR内でのREGの使用が許可され、殊にそのようにすることが必要でもある。
【００９６】
既述のように、REGの使用は一般に本出願人によるＶＰＵの１つのコンフィギュレーション内では必要とされず、１つのコンフィギュレーションの計算結果が格納されるときにのみ常に明示的に必要とされ、そのようにしてREGがこの適用事例では実際に有限オートマトンの明示的なレジスタと一致するようになる。ループのための有限オートマトンの合成のほか、たとえば以下の事例において有限オートマトンが必要とされる：
リコンフィギュアラブルプロセッサのＰＡＥ内で処理するにはアルゴリズムが大きすぎる場合には、それを複数のサブアルゴリズムに分解する必要がある。各サブアルゴリズムはリコンフィギュアラブルプロセッサに対する１つのコンフィギュレーションを成す。相前後してつまりシーケンシャルに、各サブアルゴリズムがプロセッサにコンフィギュレーションされ、その際、それぞれ先行のコンフィギュレーションの結果がそれぞれ新たなコンフィギュレーションのためにオペランドとして用いられる。
【００９７】
換言すればリコンフィギュレーションにより有限オートマトンが生成され、これは時点ｔにおいてデータを処理して記憶させ、時点ｔ＋１において場合によってはあるコンフィグレーションの後、格納されたデータを必要に応じて異なるかたちで処理し、再び記憶させる。ここで重要であるのは、ｔは古典的な意味でクロックまたは命令によって定義されるのではなく、コンフィギュレーションによって定義される。これについてはたとえばプロセッサモデルのプレゼンテーション（PACT, 2000. 10, San Hose）を参照されたい。
【００９８】
さらに別の言葉で説明するとコンフィギュレーションはVECおよび／またはPARから成る組み合わせ網によって構成されており、次のコンフィグレーションで再利用できるようその結果が格納される（REG）。
コンフィギュレーション１：  VEC{オペランド；{VEC｜PAR};REG{結果１}}
コンフィギュレーション２：  VEC{結果１；{VEC｜PAR};REG{結果２}}
...
理解しやすくするため、これまで挙げた例および記述は構造VEC, PAR, REGを高級言語で表し、それらをその言語で構造化した。しかし一般的であるのはそして有利であるのは、それらの構造を最初は中間言語のレベル（コンパイラデザイン(Red Dragon), Aho, Sethi, Ullmannの原理を参照）で表すことである。ここで特に述べておきたいのは、アルゴリズムの構造をVEC, PAR, REGによって一般に完全自動でコンパイラがたとえばグラフ分析等の方式を利用して実行できることである。とはいえたとえばやはりここで考えられるのは、そして一部では有利であるのは、VEC, PAR, REGを上述のようにダイレクトに高級言語で記述可能にすることでプログラマ自身が高級言語で構造作成できるようになることである。
【００９９】
生成
VEC, PAR, REGの自動作成をコンパイラプロセスの種々の平面で実行することができる。さしあたり最もわかりやすいことがプリプロセッサ実行中、前述の例におけるソースコードをベースに記述される。しかしその後、別のコンパイラのために特別に整合されたコンパイラが必要とされる。
【０１００】
別の観点によれば、コンパイラはたいてい（たとえばループ内で）コードの自動最適化を行う。したがってコードの効率的な分解は最適化が実行されてからようやく有用となり、殊にこれはコンパイラ（たとえばSUIF, Stanford大学など）がすでにコードを並列処理および／またはベクトル化について最適化している場合である。
【０１０１】
したがって殊に有利な方法は、コンパイラのバックエンドへ分析をバインドすることである。バックエンドによりコンパイラ内部のデータ構造がターゲットプロセッサの命令に変換される。コンパイラ内部のデータ構造としてたいていはポインタ構造たとえばDAG/GAG、ツリーまたは３アドレスコードが使用される（コンパイラデザイン(Red Dragon), Aho, Sethi, Ullmann）。部分的にStack-Machine-Codeが使用される（コンパイラ自作 C'T 1986 1-5 参照）。データフォーマットは基本的に等価であり互いに変換可能であるので、本発明によれば有利な方式がたとえばツリーなどのようなグラフの後続処理に適用される。
【０１０２】
上述の方法に従ったデータ依存性および実現可能な並列性は、簡単にツリー内で構造に基づき自動的に識別することができる。この目的でたとえば公知の既成のグラフ分析手法を使用することができる。これに対する代案としてまたはオプションとして、相応に整合されたパース方式にによりアルゴリズムをデータ依存性、ループ、ジャンプ等について調べることができる。この場合、表現の評価に類似した方法をコンパイラにおいて使用することができる。
【０１０３】
マッピング
したがってアルゴリズムの後続の変換はターゲットアーキテクチャに大きく依存する。たとえば本出願人のプロセッサアーキテクチャ（VPU, XPP）により、ハードウェアにおける自動的なデータの同期合わせが提供される。つまりデータ依存性の適正な時間順序が自動的にハードウェアにおいて扱われる。別のアーキテクチャによれば一部では、データ伝送制御のため適切な状態マシンの合成が付加的に必要とされる。
【０１０４】
殊に重要であるのは条件付きジャンプの取り扱いである。たとえば本出願人のプロセッサアーキテクチャによれば、マッピングならびに実行のために複数のメカニズムが提供される：
１．上位のコンフィギュレーションユニットによるプロセッサまたはその一部分のリコンフィギュレーション（特許出願PACT01, 04, 05, 10, 13, 17）
２．複数のＰＡＥから成るアレイへのファンクションの展開（特許出願PACT08）、たとえば比較の両方の可能な分岐をこのアレイに同時にマッピング
３．ウェーブ（wave）コンフィギュレーション（PACT08, 13, 17）、それぞれ有効なコンフィギュレーションを選択するトークンを処理すべき種々のデータに付加
ここで述べておくと、メカニズム１は一般に典型的に使用すべき事例である。メカニズム２はすでにたいていのテクノロジーでは非常に手間がかかるかまったくインプリメント不可能であり、事例３はこれまで本出願人のＶＰＵテクノロジーによってのみ知られていたものである。
【０１０５】
それぞれ選択すべき実施方法は、アルゴリズムの複雑さと、必要とされるデータスループット（パフォーマンス）と、ターゲットプロセッサの精確な設計仕様とに依存する（たとえばＰＡＥの個数）。
【０１０６】
例：
簡単な比較により以下が計算されることになる：
2005508029.tif 000019
比較結果に応じたプロセッサのリコンフィギュレーション（メカニズム１）はたいして有用ではないようにみえる。アレイへの２つの分岐の展開（メカニズム２）は基本的に可能である。比較結果に応じてa=a*(-i)またはa=a*iを計算するＰＡＥが制御される（PACT08）。スペースに関して殊に効率的であるのは両方の計算を重ね合わせることであり（メカニズム３）、それにより比較後、結果とは無関係に同じＰＡＥがデータを後続処理するがデータにはトークンが設けられていて、このトークンにより比較に依存して局所的に、データを処理するそれぞれ後続のＰＡＥにおいて関数a=a*(-i)またはa=a*iが選択される（PACT08, 13, 17を参照）。
【０１０７】
メカニズム１によればグローバルに関連する状態が発生するが、その理由は後続の完全なコンフィギュレーションがそれに依存するからである。メカニズム２，３によれば局所的に関連する状態しか発生しないが、その理由はその状態は完全にインプリメントされた計算を超えてはもはや必要とされないからである。換言すれば、局所的またはグローバルな状態の関連性はプロセッサアーキテクチャへの選択されたマッピングにも依存する。１つのコンフィグレーションを超えてつまりは１つのコンフィギュレーションを表す有限オートマトンの組み合わせ網を超えて関連する状態（すなわち後続の有限オートマトンにより必要とされる状態）を、基本的にグローバルとみなすことができる。ここで使われる組み合わせ網という漠然とした用語について、もう一度述べておくことにする。
【０１０８】
生成されたプロセッサの命令モデル
本発明によれば、すべての基本命令を含むリコンフィギュアラブルプロセッサのためのプロセッサモデルが生成される。
【０１０９】
算術／論理命令は組み合わせ網にダイレクトにマッピングされる。
【０１１０】
ジャンプ（Jump/Call）は、組み合わせ網にダイレクトに展開されるかまたはリコンフィギュレーションにより実現される。
【０１１１】
条件およびコントロールフロー命令（if等）は組み合わせ網内で完全にトリガされて処理されるかまたは上位のコンフィグレーションユニットへ転送され、このユニットは発生した状態に依存してリコンフィギュレーションを実行する。
【０１１２】
Load/Storeオペレーションは有利には別個のコンフィギュレーションにマッピングされ、これはアドレス発生器により公知のＤＭＡのようにして実現され、これによれば内部メモリ（REG{}）からアドレス発生器により外部記憶装置への書き込みが行われるかまたは、外部記憶装置および／または周辺機器から内部メモリへのロードが行われる。しかしこれをデータ処理を行うコンフィギュレーションといっしょにコンフィギュレートしてもよいし、いっしょに動作させてもよい。
【０１１３】
Register-Moveオペレーションは組み合わせ網において各内部メモリ（REG{}）間のバスにより実現される。
【０１１４】
Push/Popオペレーションは別個のコンフィギュレーションにより実現され、これは場合によっては組み合わせ網における特定の内部レジスタおよび／または内部メモリ（REG{}）から外部記憶装置へのアドレス発生器を用いた書き込みまたは外部記憶装置からの読み出しを行い、有利には本来のデータ処理コンフィギュレーションの前または後に実行される。
【０１１５】
５．図面の説明
以下の図面にはコンパイラの実装例および構成例が示されている。
【０１１６】
図１ａには慣用の有限オートマトンの構造が示されており、これによれば組み合わせ網（０１０１）がレジスタ（０１０２）と結合されている。データを０１０１（０１０３）と０１０２（０１０４）へダイレクトに導くことができる。レジスタから組み合わせ網へのフィードバック（０１０５）により先行の１つまたは複数の状態に依存する状態処理が可能となる。処理結果は０１０６に示されている。
【０１１７】
図１ｂには、PACT01およびPACT04によるリコンフィギュアラブルアーキテクチャによる有限オートマトンが示されている（PACT04の図１２〜１５）。図１ａによる組み合わせ網（０１０１）はＰＡＥ０１０７に置き換えられる（０１０ｂ）。レジスタ（０１０２）はメモリ（０１０２ｂ）によって構成され、これは複数のサイクルにわたり記憶可能である。０１０５によるフィードバックは０１０５ｂにより行われる。入力（０１０３ｂないしは０１０４ｂ）は０１０３ないしは０１０４と等価である。０１０２ｂへのダイレクトなアクセスを、場合によってはバスを介してアレイ０１０ｂによって実現することができる。出力側０１０６ｂはやはり０１０６と等価である。
【０１１８】
図２には、リコンフィギュアラブルアーキテクチャに対する有限オートマトンのマッピングが示されている。０２０１（ｘ）は組み合わせ網（対応する図１ｂをＰＡＥとして構成することができる）を成している。この場合、１つまたは複数のオペランド用メモリ（０２０２）と１つまたは複数の結果用メモリ（０２０３）が設けられている。０１０３ｂ，０１０４ｂ，０１０６ｂによる付加的なデータ入出力側は、見やすくするため描かれていない。各メモリにはそれぞれ１つのアドレス発生器（０２０４，０２０５）が割り当てられている。オペランドメモリおよび結果メモリ（０２０２，０２０３）は物理的にまたは仮想的に互いに結合されており、これによればたとえばある関数もしくは別の関数の演算の結果をオペランドとして用いることができ、および／またはある関数の結果も新たに供給されたオペランドも別の関数のオペランドとして用いることができる。この種の結合はたとえばバスシステムにより形成可能であり、あるいはメモリの関数ならびに０２０１との網結合を新たにコンフィギュレートする（リ）コンフィグレーションにより形成することができる。
【０１１９】
図３には変数との対応に関する種々の観点が示されている。図３ａには、０３０１，０３０２，０３０３とでそれぞれ異なる計算段階が示されている。これらの段階は単純に組み合わせてもよいし、レジスタを介して互いに分離しておいてもよい。ｆ１，ｆ２，ｆ３は関数であり、ｘ１は既述の変数である。図３ｂには、関数x1 := x1 + 1における変数x1の利用が示されている。図３ｃには、１つのコンフィギュレーション内でのx1 := x1 + 1の計算のための有限オートマトンの特性が示されている。次のコンフィギュレーションにおいて、完全な有限オートマトンを得る目的で０３０６と０３０４が交換される。０３０５は、メモリ０３０４と０３０６のためのアドレス発生器を表す。
【０１２０】
図４にはループのインプリメンテーションが示されている。ハッチングされたモジュールはマイクロにより生成できる（０４２０，０４２１）。０４２１は、遅延のないフィードバックへグラフの分析によっても挿入することができる。図４ａには、
WHILE TRUE DO
x1 := x1 + 1;
の形式の単純なループのインプリメンテーションが示されている。ループのコアにはカウンタ+1（０４０１）が位置する。０４０２はマルチプレクサであり、これは最初に開始値x1（０４０３）を０４０１へ導き、その後、反復のたびにフィードバック（０４０４ａ，０４０４ｂ）を効かせる。フィードバック中にはレジスタ（REG{}参照）（０４０５）が組み込まれ、これによって０４０１の出力側からその入力側への遅延のないつまりは制御不可能なフィードバックの発生が回避される。０４０５はＶＰＵの動作サイクルでクロック制御され、したがって時間あたりの反復回数を決定する。個々の計数状態は０４０４ａまたは０４０４ｂにおいて取り出し可能である。しかし高級言語の定義によってはループは終了しない。たとえば（たとえばVHDL, Verilogなど従来技術による）ＨＤＬででは０４０４において信号を利用できるが、シーケンシャルなプログラミング言語（たとえばＣ）では０４０４を利用できない。その理由は、ループは終了せずしたがって出口値が供給されないからである。マルチプレクサ０４０２によりマクロが実現され、これはループ構造によって生成されている。マクロはWHILEの変換によりインスタンシエーションされる。レジスタ０４０５はマイクロの一部分でもあるし、あるいは従来技術によるグラフ分析に応じて精確に、遅延のないフィードバックの存在するところに挿入され、それによって揺動傾向が排除される。
【０１２１】
図４ｂには、
2005508029.tif 000020
の形式の本当のループの構造が示されている。この構造はコアでは図４ａに対応し、したがって同じ参照符号を用いた。付加的に示されている回路によれば、結果の妥当性がコントロールされ（０４１０）、ループの中止判定基準に達したときのみ０４０４ａの信号が後続の関数（０１４４）に転送される。中止判定はx1<10の比較により下される（比較ステージ０４１２）。比較結果として該とするステータスフラグ（０４１３）が、ループ制御用のマルチプレクサ０４０２および結果転送コントロール用の関数０４１１に送られる。ステータスフラグ０４１３はたとえばDE 197 04 728.9によるトリガによってインプリメントすることができる。同様に、ステータスフラグ手段０４１３をＣＴへ送ることができ、これに基づきＣＴはループの終了を識別し、リコンフィギュレーションを実行する。
【０１２２】
図５ａには
FOR i*=1 TO 10
x1 := x1 * x1;
という反復計算が示されている。基本機能は実質的に図４ｂに対応するので、参照符号をそのまま引き継いだ。関数ブロック０５０１は乗算を行う。FORループは別のループにより図４ｂと同様にインプリメントされ、これは単にブロック０５０３として示唆されている。ブロック０５０３は比較ステータスを中止判定部へ供給する。このステータスは反復制御にそのまま使用され、そのため手段０４１２（ここでは０５０２で示す）が省略される。
【０１２３】
図５ｂには
FOR i:1=1 TO 10
x1 := x1 * x1;
の計算の展開が示されている。変換時間に対する反復の回数は精確にわかっているため、計算をｉ個の乗算（０５１０）から成るシーケンスにマッピングすることができる。
【０１２４】
図６には、複数のコンフィギュレーションに及ぶ図４によるWHILEループの構成が示されている。この場合、ループ（０６０１）の状態は関連状態であり、その理由はこれにより後続のコンフィギュレーションにおける関数に決定的な影響が及ぼされるからである。計算は４つのコンフィギュレーション（０６０２，０６０３，０６０４，０６０５）に及んでいる。各コンフィギュレーションの間にデータがメモリ（REG{}参照）に格納される（０６０６，０６０７）。ここでは０６０７によりやはり０４０５が置き換えられる。リコンフィギュレーション判定基準としてメモリの占有状態を用いることができ、これは０６０６，０６０７、メモリの満杯／空および／または０６０１によって示唆されており、これによりループの中止が指示される。換言すれば、メモリの占有状態によってトリガが生成され（PACT01, PACT05, PACT08, PACT10）、これはコンフィギュレーションユニットへ送信され、リコンフィギュレーションをトリガする。ループ（０６０１）の状態もＣＴに送信することができる。それに応じてＣＴは中止判定基準に達したときに後続のアルゴリズムをコンフィギュレーションすることができ、もしくは必要に応じてまずはじめにループの残りの部分（０６０３，０６０４，０６０５）を実行してしまい、その後、後続のコンフィギュレーションをロードすることができる。
【０１２５】
６．並列性
図６には並列性の考えられ得る限界が示されている。オペランドの演算がフィードバック０６０８には依存していないかぎりループをブロックごとにつまりそれぞれメモリ０６０６／０６０７の占有状態により計算することができる。このようにして高度の並列性が達成される。
【０１２６】
オペランドの計算が先行の計算結果に依存しているかぎり、つまりフィードバック等０６０８が計算に入り込むかぎり、この手法は非効率的になり、その理由はループ内でただ１つのオペランドしか計算できないからである。
【０１２７】
有効なＩＬＰ（命令レベルの並列性 Instruction Level Parallelism）がループ内で高く、かつコンフィギュレーションにかかる時間が短ければ（PACT02, PACT04, PACT13, PACT17）、ＰＡＥに展開される計算をＶＰＵにおいてさらに効率的にすることができる。このことがあてはまらなければ、ループをシーケンシャルなアーキテクチャ（ＰＡとは別個のプロセッサまたはＰＡ内のインプリメンテーション、DE 196 51 075.9-53, DE 196 54 846.2-53ならびに殊にDE 199 26 538.0の図５、図１１、図１６、図１７、図２３、図３０、図３１、図３３に相応）にマッピングするのが有用である。
【０１２８】
計算時間の分析は以下のセクションに従い変換時点にコンパイラにおいて行うことができるし、および／または実験によりランタイムに測定することができ、これによってあとから最適化を導入できるようになり、このことで学習可能な殊に自己学習型のコンパイラが得られるようになる。
【０１２９】
本発明にとって重要であるのは分析および並列化の手法である。並列化の分析および実行のために、従来技術による様々な手法を利用することができる。マッピングすべき関数はグラフにより表される（PACT13; DE 199 26 538.0参照）。この場合、任意の個数の種々の関数からアプリケーションを合成することができる。グラフはそれらに含まれている並列性について調べられ、その際、事前に最適化のすべての手法を使用することができる。たとえば以下の検査を実行する：
６．０．１  ＩＬＰ（命令レベルの並列性）
ＩＬＰにより、どの命令を同時に実行できるかが表される（PAR{}参照）。この種の分析は、グラフ内の各ノードの依存性に関する考察に基づき簡単に行える。相応の手法は従来技術ならびに数学においてそれ自体十分に知られており、たとえばＶＬＩＷコンパイラおよび合成ツールを参照されたい。
【０１３０】
しかしながら特別な注意が必要であるのはたとえば場合によってはネストされた条件の実行（IF）である。なぜならば並列実行可能な経路の適正な述部はほとんどあるいはまったく的中しないことが多いからであり、その理由は個々のパラメータの値の空間との強い依存性が存在し、これは多くはまったくわからないかあるいは十分にはわからないからである。また、精確な分析のために、もはや有用に実行不可能なほど多くの計算時間が必要とされる可能性もある。
【０１３１】
このような事例ではたとえばプログラマの指示により分析を簡単にすることができ、および／またはそれ相応のコンパイラスイッチにより、疑いわしい状況では（場合によってはリソースを費やすかたちで）高い並列性をまたは（場合によってはパフォーマンスを費やすかたちで）低い並列性を前提とするよう動作させることができる。同様にこのような事例において、ランタイムに実験的な分析を実行することもできる。PACT10, PACT17によれば、ランタイムにプログラム特性に関する統計を作成できるようにする手法が公知である。このようにしてたとえばさしあたり最大並列性を前提とすることができる。個々の経路は統計ユニット（これはたとえばＣＴまたは別のステージにインプリメントされる、PACT10, PACT17を参照、ただし基本的にはPACT04によるユニットも利用可能）へそれぞれの実行についてメッセージを送り戻す。そして統計的な措置を用いることで、どの経路が実際に並列に実行されるのかを評価することができる。さらに可能性として挙げられるのは、経路が頻繁に並列に実行されるのか、まれにしか並列に実行されないのか、あるいはまったく並列には実行されないのかを、データに基づき評価することである。このような形式の経路利用メッセージは必須ではないが有利である。
【０１３２】
このようにして次のプログラム呼び出し時に実行を最適化することができる。なお、この目的で統計情報をたとえば不揮発にハードディスクなどに書き移すことができる。PACT22, PACT24から公知のように、複数のコンフィギュレーションを同時にコンフィギュレートすることができ、その後それらはトリガ（PACT08）により制御されるか、あるいはサブセットだけをコンフィギュレートしておき、残りのコンフィギュレーションは対応するトリガをロードユニット（ＣＴ、PACT10）へ送信することにより必要に応じてあとからロードされる。
【０１３３】
明瞭にするため以下で用いられる値PAR(p)により、関数から変換されたデータフローグラフ内で命令レベルにおいてどのような並列性がつまりどれだけ多くのＩＬＰが特定のステージ（ｐ）において達成可能であるかということが表される（図７ａ）。
【０１３４】
同じく重要であるのはベクトル並列性である（VEC{}参照）。ベクトル並列性は、比較的大きいデータ量を処理すべきときに役に立つ。そのような状況では線形のオペレーションシーケンスをベクトル化可能であり、つまりすべてのオペレーションは同時にデータ処理可能であって、その際、一般に個別のオペレーションは各々別個のデータ語を処理する。
【０１３５】
ループ内ではこのやり方は部分的には不可能となる。したがって分析と最適化が必要とされる。たとえば関数のグラフをペトリネットで表すことができる。ペトリネットのもつ特性によれば、結果の転送はノードによりコントロールされて行われ、そのことでたとえばループをモデリングすることができる。１つのループ内における結果のフィードバックによりデータスループットが決定される。例：
・演算結果ｎは演算ｎ＋１のために必要とされる：ループ内では１つの演算だけしか実行できない。
・演算結果ｎは演算ｎ＋ｍのために必要とされる：ループ内でｍ−１の演算を実行できる。
・結果によりループの中止が決定されるが、結果の演算には関与しない：フィードバックは不要である。場合によってはたしかに誤った（余計な）値がループに入るが、結果の出力は終了条件に達したときにただちにループ終了にあたって中止できる。
ループの分析の前に、それらのループを従来技術に従って最適化することができる。たとえば特定の命令をループから引き抜いて、ループの前または後ろにおくことができる。
【０１３６】
明瞭にするため以下で用いられる値VECにより、ある関数のベクトル化の可能性の程度を表すことができる。換言すればVECにより、どれだけ多くのデータ語を一群の演算の中で同時に処理できるかが表される。VECはたとえば関数ｎｎｏｄｅｓのために必要とされる計算素子数とベクトル内で同時に計算可能なデータｎｄａｔａとから計算することができ、これはたとえばVEC = ｎｎｏｄｅｓ / ｎｄａｔａにより計算できる。
【０１３７】
たとえばある関数を５つの計算素子にマッピング可能であり（ｎｎｏｄｅｓ = 5）、各計算素子各々において同時にデータを処理可能であれば（ｎｄａｔａ = 5）、VEC = 1である（図７ｂ）。これに対してたとえばある関数を５つの計算素子にマッピング可能であるが、１つの計算素子においてしかそのつどデータを処理できなければ（ｎｄａｔａ = 1）、VEC = 1/5である（図７ｃ）。
【０１３８】
１つの関数全体について、および／または１つの関数の一部分についてVECを計算可能である。VECの算出および評価は一般に有利であるけれども、本発明のコンパイラによれば両方のやり方を有利とすることができる。
【０１３９】
実現できれば有利であるが、図７ａによればPAR(p)はグラフの各列ごとに求められる。グラフにおける１つの行は、それが１クロック単位内で実行されるよう定義される。演算数は個々のＶＰＵのインプリメンテーションに依存する。
【０１４０】
PAR(p)が行ｐのノード数と一致するならば、すべてのノードを並列に実行できる。PAR(p)の方が小さければ、特定のノードだけが択一的に実行される。それぞれ１つのノードの択一的な実行はそれぞれ１つのＰＡＥ内にまとめられる。セレクション機構によってデータ処理のステータスに対応する択一性がランタイムに実現され、これについてはたとえばPACT08に記載されている。
【０１４１】
同様に、グラフの各行にVECも割り当てられる。ある行についてVEC=1であるということは、その行がパイプラインステージとして存在し続けることを意味する。ある行が１よりも小さければ、やはり１よりも小さい後続のすべての行がまとめられる。その理由はパイプライン化が不可能だからである。それらは演算順序に従い１つのシーケンスにまとめられ、その後、コンフィギュレートされてＰＡＥが形成され、ランタイムにシーケンシャルに実行される。これに相応する方法は、たとえばPCT/DE 97/02949および／またはPCT/DE 97/02998により知られている。
【０１４２】
既述の手法によれば、シーケンスのグループ分けにより複雑な並列プロセッサモデルを構築できる。たとえばリエントラントなコードをマッピングするためのシーケンサ構造を生成可能である。この目的でそのつど必要とされる同期合わせは、たとえばPACT18に記載されているタイムスタンプ方式によって実行可能であり、あるいはPACT08に記載されているトリガ方式により実行可能である。
【０１４３】
複数のシーケンサまたはシーケンシャルな部分が１つのＰＡにマッピングされる場合、所要パフォーマンスの理由から有利であるのは、個々のシーケンサのパフォーマンスを互いに調整し合うことである。このことは殊に有利には、シーケンサの動作周波数を整合し合うようにして行うことができる。PACT25およびPACT18からたとえば、個々のＰＡＥまたはＰＡＥグループによる固有のタイミング制御を許可する方式が知られている。
【０１４４】
この場合、シーケンサの周波数を、一般的にはそのシーケンサに割り当てられた関数の処理に必要とするサイクル数に基づき決定することができる。割り当てられたタスクを処理するために、たとえばあるシーケンサが自身の関数処理に５クロックサイクルを必要とする一方、残りのシステムはちょうど１つのクロックサイクルを必要とするならば、そのシーケンサのクロックを残りのシステムのクロックよりも５倍高めるようにする。多数のシーケンサが存在する場合、それぞれ異なるクロックサイクルを設定することができる。この場合、クロック逓倍および／またはクロック分周を行うことができる。
【０１４５】
複数の関数は上述の方法に従い分割される。分割にあたりそれに応じてデータおよび関連ステータスのためのメモリが挿入される。PACT13およびPACT18により、これに対する別の代案および／または発展させた手法が公知である。多くのＶＰＵはPACT01, PACT10, PACT13, PACT17, PACT22, PACT24に従い差分リコンフィギュレーションの機能を提供することができる。これを適用できるのは、リコンフィギュレーションにあたりＰＡＥアレイ内で比較的僅かな変更しか必要とされないときである。換言すれば、あるコンフィギュレーションは現在のコンフィギュレーションに対し変更部分だけしかリコンフィギュレートされない。この事例の場合には分割を、コンフィギュレーションに続く（差分）コンフィギュレーションは必要とされるリコンフィギュレーションデータだけを受け取り、完全なコンフィギュレーションを成さないように構成することができる。有利には本発明によるコンパイラは、このことを識別しサポートするように構成されている。
【０１４６】
リコンフィギュレーションのスケジューリングは、関数をロードユニット（ＣＴ）に通報するステータスにより行うことができ、ロードユニット自体は到来したステータスに基づき次のコンフィギュレーションまたはサブコンフィギュレーションを選択し、コンフィギュレートを行う。この種の方式は詳しくはPACT01, PACT05, PACT10, PACT13, PACT17により知られている。さらにスケジューリングによりサポートできるのは、別のコンフィギュレーションの実行時間中にコンフィギュレーションのプレロードを可能にすることである。この場合、複数のコンフィギュレーションを場合によっては投機的にプレロードすることもでき、つまりコンフィギュレーションがそもそも必要とされるのかを確かめずにプレロードすることも可能である。このことが殊に有利であるのは、たとえばコンフィギュレーションすることなく処理可能なかなり長いデータ流が生じたときにＣＴが少なくともほとんど負荷を受けておらず、殊にタスクの負荷がないときまたはごく僅かなタスクの負荷しかないときである。たとえばDE 197 04 728.9によるようなセレクションメカニズムによって、ランタイムに適用すべきコンフィギュレーションが選択される（たとえばPACT22/24のNISも参照）。
【０１４７】
同様にローカルなシーケンサをそのデータ処理ステータスによって制御することもでき、これについてはたとえばDE 196 51 075.9-53, DE 196 54 846.2-53, DE 199 26 538.0から公知である。これらのリコンフィギュレーションを実行するため、さらに別の依存ステータスまたは非依存ステータスをＣＴに向けて通報することができる（たとえばPACT04, LIBACK参照）。
【０１４８】
次に、これまで説明したことについて図面を参照しながら説明する。この場合、以下では説明を簡単にするため次の記号を使用する：Ｖは「または」、∧は「かつ」。
【０１４９】
図８ａには、達成可能な最大並列性で図７ａによるグラフをＰＡＥのグループにマッピングする様子が示されている。すべてのオペレーション（命令ｉ１〜ｉ１２）は個々のＰＡＥにマッピングされている。
【０１５０】
図８ｂには、同じグラフがたとえば最大利用可能なベクトル化の可能性で描かれている。ただしここではオペレーションの集合V2={i1, i3}, V3={i4, i5, i6, i7, i8}, V4={i9, i10, i11}は並列ではなくpar(par({2,3,4})=1である。したがってこの場合、複数のオペレーションから成る集合P2, P3, P4を１つのＰＡＥに割り当てることによってリソースが節約される。各ステージごとの各データ語に対するステータス信号によって、個々のＰＡＥにおいて実行すべきオペレーションが選び出される。ＰＡＥはパイプライン（ベクトル）として網結合され、各ＰＡＥはクロックごとにそれぞれ異なるデータ語についてオペレーションを実行する。
【０１５１】
この場合、以下のように進行する：
ＰＡＥ１はデータを計算しＰＡＥ２に転送する。それらのデータとともにＰＡＥ１は、i1を実行すべきなのかi2を実行すべきなのかを指示するステータス信号も転送する。
ＰＡＥ２はＰＡＥ１からのデータを引き続き計算する。到来したステータス信号に従い、実行すべきオペレーション（i1, i2）を選択して計算する。計算に従いＰＡＥ２は、（i4 Ｖ i5）Ｖ（i6 Ｖ i7 Ｖ i8）を実行すべきかを指示するステータス信号をＰＡＥ３に転送する。
ＰＡＥ３はＰＡＥ２のデータを引き続き計算する。到来したステータス信号に従い、実行すべきオペレーション（i4 Ｖ i5）Ｖ（i6 Ｖ i7 Ｖ i8）を選択し計算する。計算に従いＰＡＥ３は、i9 Ｖ i10 Ｖ i11を実行すべきかを指示するステータス信号をＰＡＥ４に転送する。
ＰＡＥ４はＰＡＥ３のデータを引き続き計算する。到来したステータス信号に従い、実行すべきオペレーションi9 Ｖ i10 Ｖ i11を選択して計算する。
ＰＡＥ５はＰＡＥ４のデータを引き続き計算する。
【０１５２】
実現可能な適切な手法ならびに既述のことをきわめて好適に実現可能なハードウェアについては、DE 197 04 728.9（図５および図６）に記載されている。PACT04およびPACT10, PACT13にも一般的に利用可能な手法について記載されているが、これは比較的煩雑な手法である。
【０１５３】
図８ｃにもはやり同じグラフが描かれている。この例ではベクトル化は不可能であるけれどもPAR(p)は高く、つまり１行の中でそれぞれ複数のオペレーションを同時に実行することができる。並列に実行可能なオペレーションは、P2 = {i1 ∧ i2}, P3 = {i4 ∧ i5 ∧ i6 ∧ i7 ∧ i8}, P4 = {i9 ∧ i10 ∧ i11}である。各ＰＡＥは、それらが任意のデータを互いに任意に交換し合えるよう網結合されている。この場合、個々のＰＡＥがオペレーションを実行するのは、対応するサイクル内でＩＬＰが生じるときだけであり、さもなければそれらは中立的に振る舞い（NOP）、その際にパフォーマンス損失を最小化するため場合によってはクロック数低減および／またはクロック遮断および／または電流遮断を行うことができる。
【０１５４】
この場合、以下のように進行する：
第１のサイクルではＰＡＥ２だけが動作し、ＰＡＥ２とＰＡＥ３へデータが転送される。
第２のサイクルではＰＡＥ２とＰＡＥ３が並列に動作し、それらのデータがＰＡＥ１，ＰＡＥ２，ＰＡＥ３，ＰＡＥ４，ＰＡＥ５へ転送される。
第３のサイクルではＰＡＥ１，ＰＡＥ２，ＰＡＥ３，ＰＡＥ４，ＰＡＥ５が動作し、データがＰＡＥ２，ＰＡＥ３，ＰＡＥ５へ転送される。
第４のサイクルではＰＡＥ２，ＰＡＥ３，ＰＡＥ５が動作しデータがＰＡＥ２へ転送される。
第５のサイクルではＰＡＥ２だけが動作する。
【０１５５】
したがってこのファンクションは計算のために５つのサイクルを必要とする。それゆえ相応のパフォーマンスを達成する目的で、対応するシーケンサをその周囲と比べて５倍のクロックで動作させるようにする。
【０１５６】
PACT02（図１９，図２０，図２１）にはこれに対応する実現可能な手法について記載されている。さらにPACT04, PACT10, PACT13にも一般的に利用可能な手法が記載されているが、これは比較的煩雑な手法である。さらに別の方式および／またはハードウェアを利用可能である。
【０１５７】
図８ｄには、利用可能な並列性が存在しない事例について図７ａに従ったグラフが示されている。データ語を計算するために、各ステージを相前後して実行する必要がある。各ステージ内で複数の分岐のうち必ずちょうど１つの分岐が処理される。
【０１５８】
このファンクションのためにも計算のために５つのサイクルが必要とされ、すなわちcy1 = (i1), cy2 = (i2 V i3), cy3 = (i4 V i5 V i6 V i7 Vi8), cy4 = (i9 V i10 Vi11), cy5 = (i12)が必要とされる。したがって対応するシーケンスを、適切なパフォーマンスを達成する目的でその周囲との比率において５倍のクロックにより動作させるようにする。この種のファンクションはたとえば図８ｃと同様、PACT02（図１９、図２０、図２１）による簡単なシーケンサによってマッピング可能である。PACT04およびPACT10, 13にも一般に利用可能な手法が記載されているが、これは比較的煩雑な手法である。
【０１５９】
図８に示されているマッピングを任意に合成したりグループ分けしたりすることができる。たとえば図９ａにも同じファンクションが描かれているが、このファンクションによれば経路（i2 ∧ （i4 Ｖ i5） ∧ i9）および（i3 ∧ （i6 Ｖ i7 V i8） ∧ （i9 Ｖ i10））を並列に実行可能である。（i4 Ｖ i5）、i6 Ｖ i7 Ｖ i8）、（i9 Ｖ i10）はそれぞれ択一的である。このファンクションをさらにベクトル化可能である。これにより構築可能なパイプラインによれば、３つのＰＡＥ（ＰＡＥ４，ＰＡＥ５，ＰＡＥ７）のためにそれぞれステータス信号に基づきそのつど実行すべきファンクションが定められている。
【０１６０】
図９ｂにも同様の例が示されており、この場合にはベクトル化は不可能である。とはいえ経路（i1 ∧ i2 ∧ （i4 Ｖ i5） ∧ i9 ∧ i12）および（i3 ∧ （i6 Ｖ i7 Ｖ i8） ∧ （i10 Ｖ i11））は並列である。このようにして最適なパフォーマンスを、並列な経路においてやはり並列処理を行う２つのＰＡＥの使用により達成することができる。ＰＡＥ相互間の同期合わせは、有利にはＰＡＥ１により生成されるステータス信号によって行われる。それというのもこれはファンクションの開始時（i1）と終了時（i12）に計算されるからである。
【０１６１】
ここで殊に言及しておきたいのは、複数のシーケンスから成る複数のアレイから１つの対称型並列プロセッサモデル（ＳＭＰ）または今日使用されている類似のマルチプロセッサモデルを生成できることである。
【０１６２】
さらに言及しておきたいのは、スケジューリング用のすべてのコンフィギュレーションレジスタに対しバックグラウンドにおいてもおよび／またはデータ処理中にも、新たなコンフィギュレーションをロードできることである。
【０１６３】
たとえばここでは、ハードウェアをDE 196 51 075.9-53により知られているように構築することが可能である。このようにすれば、互いに無関係に呼び出すことのできる独立したメモリ領域またはレジスタを利用することができる。到来するトリガによって特定の個所へのジャンプが行われ、場合によっては条件付きでも実行可能なジャンプ命令（JMP, CALL/RET）によってもジャンプさせることができる。
【０１６４】
DE 196 54 846.2-53によれば独立した書き込み／読み出しポインタを利用することができ、これにより基本的にバックグラウンドでの独立性つまりはアクセスの可能性が与えられる。さらにたとえばメモリをセグメント化することが可能であり、これによって付加的な独立性が与えられる。場合によっては条件付きでも実行可能なジャンプ命令（JMP, CALL/RET）を用いることでジャンプさせることができる。
【０１６５】
DE 197 04 728.9によればトリガにより選択可能な個々のレジスタを基本的に独立させることができ、したがって殊にバックグラウンドにおいて独立したコンフィギュレーションが可能となる。レジスタ内でのジャンプは不可能であり、選択はもっぱらトリガベクトルを介して行われる。
【０１６６】
PARおよびVECの効率を評価するための基本的なファクタは、個々の構造により処理されるデータの形式である。有用であるのはたとえば、大量のデータを処理する構造を展開することであり、つまりパイプライン化することまたは並列化することである。これはたとえばビデオデータや通信データの場合にあてはまる。僅かなデータしか処理しない構造（たとえばキーボード入力、マウス等）は展開しても有用ではなく、逆にそれによって他のアルゴリズムに対しリソースをブロックすることになってしまう。
【０１６７】
したがってここで提案されるのは、様々な指示ないしヒントに基づき、それ相応に大きいデータ量を処理するアルゴリズム、構造またはアルゴリズムの一部分だけを並列化およびベクトル化することである。この種の指示ないしヒントはたとえば以下のようなものとすることができる：
１．データ形式（アレイ、ストリームはたとえばデータ量が大きいことからたとえば個々のキャラクタよりも先に展開されるようにする）。
２．アクセス形式（線形のプログラムシーケンスはたとえばシーケンサにおいてマッピングされるようにする一方、ループはたとえば実行回数が高いことから展開するのが有用である）。
３．ソースおよび／またはターゲットの形式（キーボードやマウスのデータレートはたとえば効率的に展開するには低すぎるのに対し、ネットワークおよび／またはビデオのソースおよび／またはターゲットであるとデータレートは著しく高い）。
【０１６８】
その際、分析にあたりこれらの指示ないしはヒントのうち任意の集合を加えることができる。
【０１６９】
７．用語の定義
ローカル関連状態：
１つの特定のコンフィギュレーションにおいてのみ関連する状態
グローバル関連状態：
複数のコンフィギュレーションにわたり関連し、かつ複数のコンフィギュレーション間で交換する必要のある状態
関連状態：
１つのアルゴリズム内でその適正な実行のために必要とされ、つまりはそのアルゴリズムにより記述されそれにより利用される状態
非関連状態：
本来のアルゴリズムにとっては重要ではなく、アルゴリズム内にも記述されていないが、実行するハードウェアによりインプリメンテーションに依存して必要とされる状態
【図面の簡単な説明】
【０１７０】
【図１】図１ａは慣用の有限オートマトンの構造を示す図であり、図１ｂはPACT01およびPACT04によるリコンフィギュアラブルアーキテクチャによる有限オートマトンを示す図である。
【図２】リコンフィギュアラブルアーキテクチャに対する有限オートマトンのマッピングを示す図である。
【図３】変数との対応に関する種々の観点を示す図である。
【図４】ループのインプリメンテーションを示す図である。
【図５】反復計算および計算の展開について示す図である。
【図６】複数のコンフィギュレーションに及ぶ図４によるWHILEループの構成を示す図である。
【図７】データフローグラフおよびベクトル並列性について示す図である。
【図８】ＰＡＥのグループにマッピングする様子を示す図である。
【図９】マッピングの合成およびグループ分けを示す図である。
【国際公開パンフレット】
2005508029.tif 000021
2005508029.tif 000022
2005508029.tif 000023
2005508029.tif 000024
2005508029.tif 000025
2005508029.tif 000026
2005508029.tif 000027
2005508029.tif 000028
2005508029.tif 000029
2005508029.tif 000030
2005508029.tif 000031
2005508029.tif 000032
2005508029.tif 000033
2005508029.tif 000034
2005508029.tif 000035
2005508029.tif 000036
2005508029.tif 000037
2005508029.tif 000038
2005508029.tif 000039
2005508029.tif 000040
2005508029.tif 000041
2005508029.tif 000042
2005508029.tif 000043
2005508029.tif 000044
2005508029.tif 000045
2005508029.tif 000046
2005508029.tif 000047
2005508029.tif 000048
2005508029.tif 000049
2005508029.tif 000050
2005508029.tif 000051
2005508029.tif 000052
2005508029.tif 000053
2005508029.tif 000054
2005508029.tif 000055
2005508029.tif 000056
2005508029.tif 000057
2005508029.tif 000058
2005508029.tif 000059
2005508029.tif 000060
2005508029.tif 000061
2005508029.tif 000062
2005508029.tif 000063
2005508029.tif 000064
2005508029.tif 000065
2005508029.tif 000066
2005508029.tif 000067
2005508029.tif 000068
2005508029.tif 000069
2005508029.tif 000070
2005508029.tif 000071
2005508029.tif 000072
2005508029.tif 000073
2005508029.tif 000074
2005508029.tif 000075
2005508029.tif 000076
2005508029.tif 000077
2005508029.tif 000078
2005508029.tif 000079
2005508029.tif 000080
2005508029.tif 000081
2005508029.tif 000082
2005508029.tif 000083
2005508029.tif 000084
2005508029.tif 000085
2005508029.tif 000086
2005508029.tif 000087
2005508029.tif 000088
2005508029.tif 000089
2005508029.tif 000090
2005508029.tif 000091
2005508029.tif 000092
2005508029.tif 000093
2005508029.tif 000094
2005508029.tif 000095
2005508029.tif 000096
2005508029.tif 000097
2005508029.tif 000098
【国際公開パンフレット（コレクトバージョン）】
2005508029.tif 000099
2005508029.tif 000100
【国際調査報告】
2005508029.tif 000101
2005508029.tif 000102
2005508029.tif 000103
2005508029.tif 000104
2005508029.tif 000105
2005508029.tif 000106