JP2005508029A - Program conversion method for reconfigurable architecture - Google Patents

Abstract

The present invention relates to data processing with multidimensional fields, which show how high-level language codes can be used advantageously for this purpose.

Description

マッピングにより比較処理用の付加的なＰＡＥが生成される。比較結果はステータス信号により表され（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（ロード／ストア）オペレーションの基礎として以下のことに留意されたい。
【００４９】
以下のアドレッシング形式がそれぞれ異なるかたちで処理される：
１．外部のアドレッシングすなわち外部のコンポーネントによるデータ転送
２．内部のアドレッシングすなわち各ＰＡＥ間のデータ転送たとえばＲＡＭ−ＰＡＥとＡＬＵ−ＰＡＥとの間のデータ転送
さらにデータ処理とデータのロードおよびストアの時間的な分離に殊に注目することができる。バス伝送が内部伝送と外部伝送に分解される。
ｂｔ１）外部の読み出しアクセス（ロードオペレーション）が分離され、１つの可能な実施形態によれば別個のコンフィギュレーションに変換される。データは外部記憶装置から内部メモリに転送される。
ｂｔ２）内部アクセスがデータ処理と結合され、つまり内部メモリ（レジスタオペレーション）がデータ処理のために読み出されもしくは書き込まれる。
ｂｔ３）外部書き込みアクセス（ストアオペレーション）が分離され、１つの可能な有利な実施形態によればこれも別個のコンフィギュレーションに変換される。データは内部メモリから外部記憶装置へ転送される。
【００５０】
ここで重要であるのは、ｂｔ１，ｂｔ２，ｂｔ３つまりデータのロード（Ｌｏａｄ）、データの処理（データ処理およびｂｔ２）およびデータの書き込み（ｂｔ３）を様々なコンフィギュレーションに変換することができ、これらを必要に応じてそれぞれ異なる時点で実行することができる。
【００５１】
この手法について以下の例に基づき説明する：

この関数はコンパイラにより３つのパートもしくはコンフィギュレーション（subconfig）に変換できる：
example#dload: データを外部から（メモリ、周辺機器などから）ロードし、それらを内部メモリに書き込む。内部メモリは#rおよび元の変数の名前で表される。
example#process: 本来のデータ処理に対応。これによりデータが内部のオペランドから読み出され、結果が再び内部メモリに書き込まれる。
example#dstore: 結果が内部メモリから外部記憶装置（メモリ、周辺機器等）に書き込まれる。

この手法の重要な効果は、オペランド読み出しにあたり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を読み出すようにすることもできる。

サブプログラム呼び出しならびにグローバル変数の管理は、リコンフィギュアラブルアーキテクチャにとって比較的煩雑である。したがって１つの有利な実施形態によれば後続の最適化を実行することができ、その際、すべてのコンフィギュレーションが十分に独立して実行され、完全に処理された後で終了する（terminate）。データb[j]は何回も必要とされるので、example#dloadbをそれに応じて何回も実行しなければならない。このためたとえば２つのオプションが設けられる：
オプション１：example#dloadbは実行されるたびに終了し、再スタートのたびにexample#processにより新たにコンフィギュレーションされる。
オプション２：example#dloadbはエンドレスで実行され、example#processによって終了させられる。
'idle'中、コンフィギュレーションは非アクティブ状態（待機状態）にある。

待ちサイクルを避けるため、コンフィギュレーションが自身のタスクを一時的にそれ以上果たすことができなくなるとただちに、それらのコンフィギュレーションを終了させることもできる。対応するコンフィギュレーションはリコンフィギュアラブルコンポーネントから取り除かれるが、スケジューラの中にはとどまり続ける。この目的で以下では命令'reenter'が使用される。関連する変数は終了前に保護され、コンフィギュレーションが繰り返されるときに再び生成される：

２．３ マクロ
高級言語の比較的複雑な機能たとえばループなどは一般にマクロにより実現される。この場合、マクロはコンパイラによりまえもって設定され、変換時点にインスタンシエーションされる（図４参照）。それらのマクロは高級言語の単純な言語構造によって構築されているかまたはアセンブラレベルで構築されている。既述のアルゴリズムに簡単に整合できるようにする目的で、マクロをパラメータ化することができる（図５の０５０２参照）。これらのマクロをここでも組み入れることができる。
【００５５】
２．４ フィードバックループおよびレジスタ
アルゴリズムを１つの組み合わせ網にマッピングする際、制御されずに揺動する遅延のないフィードバックが発生する可能性がある。実際にインプリメントされる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交換コンフィギュレーションを用いグローバルメモリを介したこのようなデータ交換は特別に重要であるとみなされる。
【００７９】
次にこの機能について１つの例に基づき説明する：
１つの関数によって２つの数列が加算され、それらの数列の長さは変換時点では未知であり実行時にはじめてわかる。

この関数が実行中に中断され、たとえばタスク切替により、あるいはｘのために用意されているメモリがいっぱいになったために中断される。本発明によればa, b, xはこの時点でメモリ内に存在している。しかしiおよび必要に応じて長さを保護しなければならない。この目的でコンフィギュレーションexampleが終了させられ、レジスタ内容が維持され、コンフィギュレーションpushが開始され、これによりiと長さがレジスタから読み出され、メモリに書き込まれる。

実行後、pushが終了させられ、その際、レジスタを消去することができる。別のコンフィギュレーションが実行される。いくらか後、コンフィギュレーションexampleが再び開始される。その前にコンフィギュレーションpopが開始され、これによりレジスタ内容が再びメモリから読み出される。

実行後、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}}}
別の例により真の状態を示す。
例Ｂ：

ここで行６は行２と行３の計算後にのみ実行することができる。行４と行６の計算は択一的に行われる。つまり行３の状態はその後のデータ処理に関連する（関連状態）。
【００９１】
条件付けられた状態は変換にあたりIFによって表現できる：

要約すると、

別の関連状態はループにより生成される：
例Ｃ：

行３の実行はループの終了後、はじめて許可される。つまり条件付きジャンプにおいて関連状態である。
【００９２】
ループの最初の変換は以下の通りである：

行３および行４は並列に計算することができる。なぜならば行４は行３の結果に依存しないからである：
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は行１の結果である）。行６もはやり条件付きベクトルである。なぜならばａはオペランドとして使用され、ａは条件の結果だからである。
したがって以下の通りとなる（見やすく記述してある）：

VEC{}とPAR{}の内容は単純な組み合わせ網とみなすことができる。有利にはVECとPARはペトリネットとして構成され、たとえば有利には個々の内容の完全な処理後に後続処理が制御されるようになる。
【００９３】
VECとPARは単純な組み合わせ網とみなせることから、ループ状態を保護する必要性が生じる。つまりこの場合には実際に、有限オートマトンを作り出すことが必要である。
【００９４】
この目的で命令REG{}によりレジスタに変数が格納される。これにより組み合わせ網VECとPACをレジスタREGと共働させて有限オートマトンが生成され、これはアルゴリズムに精確に一致するよう構成されている：

ここで特に指摘しておくべきことは、本出願人のＶＰＵテクノロジー（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）、それぞれ有効なコンフィギュレーションを選択するトークンを処理すべき種々のデータに付加
ここで述べておくと、メカニズム１は一般に典型的に使用すべき事例である。メカニズム２はすでにたいていのテクノロジーでは非常に手間がかかるかまったくインプリメント不可能であり、事例３はこれまで本出願人のＶＰＵテクノロジーによってのみ知られていたものである。
【０１０５】
それぞれ選択すべき実施方法は、アルゴリズムの複雑さと、必要とされるデータスループット（パフォーマンス）と、ターゲットプロセッサの精確な設計仕様とに依存する（たとえばＰＡＥの個数）。
【０１０６】
例：
簡単な比較により以下が計算されることになる：

比較結果に応じたプロセッサのリコンフィギュレーション（メカニズム１）はたいして有用ではないようにみえる。アレイへの２つの分岐の展開（メカニズム２）は基本的に可能である。比較結果に応じて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の変換によりインスタンシエーションされる。レジスタ０４０５はマイクロの一部分でもあるし、あるいは従来技術によるグラフ分析に応じて精確に、遅延のないフィードバックの存在するところに挿入され、それによって揺動傾向が排除される。
【０１２１】
図４ｂには、

の形式の本当のループの構造が示されている。この構造はコアでは図４ａに対応し、したがって同じ参照符号を用いた。付加的に示されている回路によれば、結果の妥当性がコントロールされ（０４１０）、ループの中止判定基準に達したときのみ０４０４ａの信号が後続の関数（０１４４）に転送される。中止判定は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ループの構成を示す図である。
【図７】データフローグラフおよびベクトル並列性について示す図である。
【図８】ＰＡＥのグループにマッピングする様子を示す図である。
【図９】マッピングの合成およびグループ分けを示す図である。【Technical field】
[0001]
1. Introduction
The invention relates to a method according to the superordinate concept of the claims. According to this, the present invention addresses the problem of how to best use a reconfigurable architecture, for example, how to optimally execute instructions in a given high-level language in a reconfigurable architecture. It relates to the problem of whether or not it can be done.
[0002]
So-called compilers are known in order to execute data processing instructions (programs) written in so-called high-level languages in individual architectures used for data processing, and compilers further convert high-level language instructions to the architectures used. Convert to a well-aligned instruction. A compiler that specifically supports an architecture that performs highly parallel processing at that time is therefore called a parallel processing compiler.
[0003]
Prior art parallel processing compilers often use special structures such as semaphores and / or other synchronization schemes. In this case, a technology-specific method is generally used. The known approaches are not suitable for combining a functionally described architecture with its time characteristics and imperatively described algorithms. For this reason, the methods that have been used so far do not provide a satisfactory solution only in special cases.
[0004]
Compilers for reconfigurable architectures, such as compilers for reconfigurable processors, generally use macros created specifically for specific reconfigurable hardware, and are often used for macro creation, for example Verilog, VHDL Or a hardware description language such as System-C is used. This macro is later called from the program flow (instantiation) by a conventional high-level language (for example, C, C ++).
[0005]
In a coarse-grained structure, a compiler for a parallel computer that maps a program part to a plurality of processors is known, usually based on a function or an entire thread.
[0006]
Vector compilers are also known, which convert sufficiently linear data processing into vectorized form, for example large expression calculations, so that in superscalar processors and vector processors (eg Pentium, Cray) Allow calculation.
[0007]
In the present invention, functional or imperatively organized operation rules are integrated into various target technologies such as ASIC, reconfigurable components (FPGA, DPGA, VPU, ChessArray, KressArray, Chameleon, etc., which are unified in the following term VPU. ), Sequential processors (CISC-CPU / RISC-CPU, DPS, etc., these are unified in terms of CPU in the following), and a method of automatically mapping to a parallel computer system (SMP, MMP, etc.) will be described. For example, the following patent specifications by the applicant in this connection are listed: 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. These are the references for this application.
[0008]
A VPU is basically composed of an array (PA) of multi-dimensional homogeneous or heterogeneous flat or hierarchical cells (PAE), which cells can have any function, such as logic functions and / or arithmetic functions and Memory functions and / or network functions can be performed. There is typically one load unit (CT) for each PAE, which unit determines the PAE function by configuration and possibly reconfiguration.
[0009]
The method according to the present invention is based on an abstract parallel machine model, which incorporates imperative or imperative problem descriptions in addition to finite automata, enabling efficient algorithm derivation for various technologies. It becomes.
[0010]
According to the prior art, the following compiler classes are known:
Classic compilers, which were often suitable for very simple processors that generated stack machine code and were essentially configured as normal sequencers (N. Wirth, Compilerbau, Teubner Verlag).
[0011]
Vector compilers build extensively linear code tuned for special vector computers or highly pipelined processors. Originally compilers could be used for vector computers such as CRAY. Modern processors such as Pentium require a similar scheme because of their long pipeline structure. Since the individual calculation steps are vectorized (pipelined) and executed, the code becomes extremely efficient. However, conditional jumps are a problem for pipelines, so jump prediction that estimates the jump destination is useful. However, if the estimation is incorrect, the entire processing pipeline must be erased, in other words any jumps are problematic for such compilers, and parallel processing in the original sense is not performed. For jump prediction as well as similar mechanisms, significant extra hardware costs must be incurred.
[0012]
Coarse-grained parallel compilers rarely exist in the original sense, and parallelism is generally represented and managed by programmers or operating systems, that is, for example, MMP computer systems such as various IBM architectures, ASCI Red, etc. It is executed at the thread level. One thread is a sufficiently independent program block, or even another program. Therefore, threads can be easily parallelized with coarse grain. Synchronization and data consistency must be guaranteed by the programmer or operating system. This requires time-consuming programming and requires most of the computing power of a parallel computer. Moreover, even with such rough parallelization, only a small part of the parallelism that can be originally realized can actually be used.
[0013]
The fine-grain parallel compiler (VLIW compiler) attempts to map parallelism to the VLIW calculation unit with fine-grained granularity. According to such a calculation unit, a plurality of operations can be executed in parallel in one clock. It has a register set, and this constrained register set constitutes a serious problem because it must supply data for all operations. Moreover, parallelism becomes more difficult due to data dependencies and mismatched read / write operations (LOAD / STORE).
[0014]
A reconfigurable processor has a number of independent computing units, which are generally located in one field. These are usually connected to each other by a bus rather than a common register set. While this makes it possible to easily construct a vector calculation mechanism, it is also possible to easily perform parallel operations. Contrary to the conventional register concept, data dependency is eliminated by bus connection.
[0015]
The object of the present invention is to provide a new method for industrial use.
[0016]
This problem is solved by the features of the independent claims. Advantageous embodiments are described in the dependent claims.
[0017]
According to the present invention, it is also proposed to apply the concepts for vector compilers and parallel compilers (eg VLIW) simultaneously for reconfigurable processor compilers, ie vectorization and parallelization at a fine granularity level. The
[0018]
The basic advantage is that the compiler does not need to map to a fixedly defined hardware structure, but the hardware structure is adapted by the method of the present invention to best match the mapping or transformation of the individual algorithms being compiled. Can be configured.
[0019]
2. Description
Finite automata are used as the basis for processing virtually any methodology describing the algorithm. The structure of a finite automaton is shown in FIG. One simple finite automaton is divided into a combinatorial network and a register stage that temporarily stores data between individual data processing cycles.
[0020]
A finite automaton performs a plurality of simply combined (ie, logical and / or arithmetic) data operations and then reaches a steady state, which is represented in a register (set). Based on the stable state, it is determined what next state should be reached in the next processing step, and what combination data manipulation should be performed in the next processing step.
[0021]
For example, a processor or sequencer represents a finite automaton. Data subtraction can be performed in the first processing step. The result is stored. In the next step, a jump can be performed based on the subtraction result, whereby another subsequent process is performed depending on the polarity sign of the result.
[0022]
As shown in FIG. 2, a finite automaton can map a complex algorithm to an arbitrary sequential machine. The composite finite automaton shown is composed of a composite combination network, a data storage memory, and an address generator for addressing data in the memory.
[0023]
In this way, any arbitrary sequential program can be basically regarded as a finite automaton, but in that case, a very large network is usually generated. Therefore, in classic "von Neumann" architecture programming, that is, in all CPUs, the combinational operations are broken down into a series of individual, predefined, predefined operations (OpCodes) that match the registers in the CPU. The Although this decomposition creates a state for controlling a series of decomposed combination operations, they do not exist or are not required in the original combination operation itself. That said, basically, the state to be processed by the von Neumann machine must be distinguished from the arithmetic state of the combinatorial network, that is, the register of the finite automaton.
[0024]
It should be noted that VPU technology (which is basically defined by some or all of the documents PACT01, PACT02, PACT03, PACT04, PACT05, PACT08, PACT10, PACT13, PACT17, PACT18, PACT22, PACT24. In contrast to the fixed OpCode of the CPU, compound instructions can be compiled together according to an algorithm to be mapped in a flexible configuration or the like.
[0025]
2.1 Compiler operation
Particularly advantageous is the operation of the compiler to generate compound instructions to be executed as long as possible without being reconfigured in the PAE matrix.
[0026]
The compiler also generates finite automata, preferably from imperative source text, to very well match individual PAE matrices, ie generally coarse-grained logic circuits (such as ALUs) and possibly present An operation that uses a very fine element (such as an FPGA cell in a VPU, a state machine, etc.) very well is provided therein. Thereafter, the finite automaton generated by the compiler is decomposed into a plurality of configurations.
[0027]
The processing (interpretation) of the finite automaton is performed in the VPU, in which a plurality of generated configurations are continuously mapped to the PAE matrix, and operation data and / or states to be transmitted between the configurations are stored in the memory. Stored. For this purpose, methods known from PACT04 or the corresponding architecture can be used. This memory is determined or set by the compiler. In this case, a plurality of instructions are represented by one configuration. One configuration determines the operation of the PAE matrix for multiple clocks simultaneously, during which multiple data are processed in the matrix. They are from sources external to the VPU and / or internal memory and are written to the external source and / or internal memory. In this case, the internal memory supplements the register set of the CPU according to the prior art, whereby, for example, a register is represented by the memory, and the entire data set is written for each memory instead of one data word per register.
[0028]
Basically, the data and / or state of the running configuration can be stored in memory as determined by the compiler so that it can be used by the next running configuration.
[0029]
Therefore, the decisive difference from a compiler that performs parallelization based on instructions is that according to this scheme, the PAE matrix is configured and reconfigured as follows. That is, while a series of configured combinatorial networks is emulated on a VPU, a conventional compiler combines a series of loaded instructions (OpCode), with one instruction regarded as one combinatorial network. be able to.
[0030]
2.2 Examples of WHILE language
Next, the operation of the compiler will be described with an example based on a simple language. In this case, it is assumed that the language is already known in the base, whereas the known publication [reference paper Dissertation Armin Nueckel "] only describes mapping functions to static combinatorial networks, According to the present invention, mapping or conversion to configurations is performed, and these configurations are mapped to the PAE matrix in temporal order according to the algorithm and the conditions that occur during processing.
[0031]
The programming language assumes that in addition to simple logical and / or arithmetic combinations, the instruction "WHILE" exists, which is defined by the following syntax:
WHILE
Possible structure: instruction
Instruction sequence
loop
One instruction or instruction sequence can be mapped to a combination network by the compiler method described above.
[0032]
FIG. 3a shows a combination network with variables belonging to it. In this case, the content of the same variable (for example, x1) changes when the stage (0301) with a network changes to the next stage (0302). FIG. 3b shows this change, for example
x1: = x1 + 1
Is shown with respect to.
[0033]
Here, the address generator can be synchronized with the instruction combination network for addressing for reading operands and storing results. With each variable being processed, a corresponding new address is generated for the operand and result (FIG. 3c). The form of the address generator is basically arbitrary and depends on the addressing pattern of the application being compiled. A common combined or completely separate address generator can be implemented for operands and results.
[0034]
In general, for data processing, such as the data processing model described herein, multiple data are processed within one specific configuration of the PAE. Thus, it is advantageous to configure the compiler for a simple FIFO mode that is possible for many, if not most, applications, which can be used at least for data memory, Is used to store data as well as the status of data processing (in other words, as a substitute for a normal register in a conventional CPU). In other words, the memory is used to temporarily store variables between each configuration. Again, one configuration is similar to a normal processor instruction, and memory (eg, multiple) can be contrasted with a normal processor register set.
[0035]
2.3.3. Instruction sequence
An example instruction sequence can be generated as follows (FIG. 4a):
x1: = 0;
WHILE TRUE DO
x1: = x1 + 1;
This sequence is mapped by the instruction according to 2.2.1 and the address generator for operands and results.
[0036]
Finite sequence
For the sake of completeness, we will discuss special forms of sequences apart from the defined structure of the WHILE language. An example finite sequence of instructions is generated as follows:
FOR i: = 1 TO 10
x1: = x1 + 1;
This kind of sequence is implemented in two forms:
a) Generate an adder for calculating i and another adder for calculating x1 according to the WHILE structure (2.2.4). In this case, the sequence is mapped as a loop and calculated recursively (FIG. 5a).
b) Extending the loop. This eliminates the calculation of i as a function. The calculation of x1 is instantiated i times and constructed as a pipeline, thereby generating i adders connected in series (FIG. 5b).
[0037]
2.2.4 Conditions
You can express conditions using WHILE. Example:

The mapping generates an additional PAE for comparison processing. The comparison result is represented by a status signal (see trigger in PACT08), which is evaluated by the PAE and address generator processing the instruction. FIG. 4b shows the resulting mapping.
[0038]
A condition (WHILE here, which can be realized by other instructions such as IF; CASE for the sake of clarity) can be used for subsequent processing (DE 197 04 728.9) and / or this status is CT Or it can be sent to a local load controller (DE 196 54 846.2), where another program flow and possibly a raw reconfiguration is derived from the status.
[0039]
2.2.5 Basic method
Each program is mapped to a system constructed as follows according to the method described above:
1. Operand memory (contrast with CPU registers)
2. Memory for results (contrast with CPU registers)
3. a) a specification and / or b) a comparison instruction, ie a network of IF, CASE, loop (WHILE, FOR, REPEAT)
4.1 Optional address generator for controlling memory according to 1 and 2
2.2.6 Correspondence with each state
For the purpose of the described compiler, a distinction is made between states associated with the algorithm and states not associated with it. Each state is typically represented in the VPU technology by a status signal (eg trigger in PACT08) and / or a handshake (eg RDY / ACK in PACT02). In general, each state can be represented by any signal, group of signals and / or registers (in other technologies such as FPGA, DPGA, Chameleon components, Morphics). Although much of the specification will focus on the VPU, the compiler approach disclosed herein can be designed to target such as well, the unrelated state being the hardware used and Occurs for selected mapping or other secondary reasons. They are therefore important for mapping (ie hardware).
[0040]
Data need only be given to relevant states. Their state is therefore stored in memory together with the data. This is because these states are generated as a result of comparison with the data, or are required for the next processing cycle together with the data as an operand.
[0041]
In contrast, unrelated states are required locally and / or locally in time and therefore do not need to be stored in memory.
[0042]
Example:
a) The status information of the comparison is important for the further processing of the data, since the function to be performed is determined by them.
b) Assume that a sequential divider is formed, for example, by mapping a divide instruction to hardware that only supports sequential division. This creates a state representing the calculation step in the division. This state is an unrelated state. This is because only the result (and thus the division performed) is needed for the algorithm. Therefore, in this case, only the result and time information (ie availability) is needed. It is advantageous for the compiler to distinguish between such related states and unrelated states.
[0043]
Time information is obtained, for example, by RDY / ACK handshaking in the VPU technology according to PACT01, 02, 13. However, to mention this here, handshaking is also unrelated, because it only reports the validity of the data, and the remaining relevant information is still valid. Data is reduced to be present.
[0044]
2.2.7 Response to time
In many programming languages, especially in sequential languages such as C, the exact time order is implicitly determined by the language. In the case of a sequential programming language, this is done, for example, by the order of the individual instructions. As long as this is required by the programming language and / or algorithm, the time information is mapped to a synchronization model such as RDY / ACK, REQ / ACK, etc. or a time stamp scheme such as DE 101 10 530.4, etc. A compiler approach is designed.
[0045]
In other words, implicit time information in a sequential language is mapped to a handshake protocol, in which case the time information is transmitted by the handshake protocol (RDY / ACK protocol), for example, the order of instructions is guaranteed.
[0046]
For example, the following for loop is executed and repeated only when the variable inputstream is confirmed by RDY for each loop execution. If RDY does not occur, loop execution is stopped until RDY arrives.
while TRUE
s: = 0
for i: = 1 to 3
s: = s + inputstream;
Thus, the sequential language property of being controlled only by instruction processing is combined with a data flow scheme that controls the processing by the data stream or the presence of data in compilation. In other words, instructions and / or instructions (eg, s: = s + inputstream;) are processed only when operations can be performed and data is available.
[0047]
Note that this technique usually does not change the syntax or semantics of high-level languages. In other words, by recompiling the existing high-level language code, the VPU can be executed without any problem.
[0048]
2.2.8 Loading and storing data
Note the following as the basis for Load / Store operations:
[0049]
The following addressing formats are handled differently:
1. Data transfer by external addressing or external components
2. Internal addressing, ie data transfer between each PAE, eg data transfer between RAM-PAE and ALU-PAE
In addition, special attention can be paid to the temporal separation of data processing and data loading and storage. Bus transmission is broken down into internal transmission and external transmission.
bt1) External read access (load operation) is isolated and converted to a separate configuration according to one possible embodiment. Data is transferred from the external storage device to the internal memory.
bt2) Internal access is combined with data processing, ie internal memory (register operations) is read or written for data processing.
bt3) External write access (store operation) is decoupled and according to one possible advantageous embodiment it is also converted into a separate configuration. Data is transferred from the internal memory to the external storage device.
[0050]
What is important here is that bt1, bt2, bt3, that is, data loading (Load), data processing (data processing and bt2) and data writing (bt3) can be converted into various configurations. Can be performed at different times as needed.
[0051]
This technique is illustrated based on the following example:

This function can be converted into three parts or a configuration (subconfig) by the compiler:
example # dload: Load data externally (from memory, peripherals, etc.) and write them to internal memory. Internal memory is represented by #r and the name of the original variable.
example # process: Supports original data processing. As a result, data is read from the internal operand, and the result is written back to the internal memory.
example # dstore: The result is written from the internal memory to the external storage device (memory, peripheral device, etc.).

An important effect of this approach is that only i + j = 100 + 100 = 200 external accesses are performed instead of i * j = 100 * 100 = 10,000 external accesses in reading the operand. Moreover, their access is still completely linear, which greatly increases the transmission rate for modern bus systems (Burst) and / or modern memories (SDRAM, DDRAM, RAMBUS, etc.).
[0052]
Since different memories are allocated to the operands, internal memory accesses are performed in parallel.
[0053]
I = 100 external accesses are required to write the result, which can also be performed linearly with the best performance.
[0054]
If the number of data transmissions is not known in advance (for example, in the case of a WHILE loop) or very many times, call the subprogram to load operands later if necessary, or send the result to the outside A technique for writing can be used. For this purpose, according to one advantageous embodiment, the status of the FIFO is (optionally) queried: 'empty' if the FIFO is empty, 'full' if the FIFO is full. The program flow reacts according to these conditions. Specific variables (for example, ai, bi, xi) are defined globally. In order to optimize performance, the scheduler can execute example # dloada and example # dloadb before calling example # process and load the data in advance according to the method described above. Similarly, example # dstore (n) can be called after example # process to read r # x.

Subprogram calls and global variable management are relatively cumbersome for reconfigurable architectures. Thus, according to one advantageous embodiment, subsequent optimizations can be performed, where all configurations are performed sufficiently independently and terminate after they have been fully processed. Since data b [j] is needed many times, example # dloadb must be executed many times accordingly. For this, for example, two options are provided:
Option 1: example # dloadb terminates each time it is executed and is reconfigured by example # process each time it restarts.
Option 2: example # dloadb is run endlessly and terminated by example # process.
During 'idle', the configuration is inactive (standby).

To avoid waiting cycles, configurations can be terminated as soon as they can temporarily no longer perform their tasks. The corresponding configuration is removed from the reconfigurable component, but remains in the scheduler. For this purpose, the instruction 'reenter' is used below. Related variables are protected before exiting and are regenerated when the configuration is repeated:

2.3 Macro
A relatively complex function of a high-level language such as a loop is generally realized by a macro. In this case, the macro is set in advance by the compiler and instantiated at the time of conversion (see FIG. 4). These macros are built with a simple language structure of a high-level language or are built at the assembler level. Macros can be parameterized (see 0502 in FIG. 5) in order to be able to easily match the algorithms already described. These macros can also be incorporated here.
[0055]
2.4 Feedback loops and registers
When mapping an algorithm to a single combinatorial network, uncontrolled and oscillating feedback without delay can occur. In the case of VPU technology according to PACT02 that is actually implemented, this is avoided by the structure of the PAE, whereby at least one register is fixedly defined in the PAE, for example, for separation.
[0056]
Feedback without delay can generally be detected by graph analysis of the generated combinatorial network. Based on this, a separation register is inserted as expected in the data path where feedback without delay occurs. In this way, the compiler can manage the register means or the memory means.
[0057]
By using a handshake protocol (eg RDY / ACK according to 2.2.7), the correct function of the calculation is guaranteed even if a register is inserted.
[0058]
2.5 Processor model / Time division multiplexing (TDM)
Basically, each PAE matrix actually formed has only a finite size. Therefore, in the following steps, it is necessary to divide the algorithm according to a / b of paragraph 4 in 2.2.5 into a plurality of configurations that are configured in sequence to form a PAE matrix. The purpose is generally to calculate as many data packets as possible in the network without having to reconfigure. Temporary storage is performed between the configurations, and the temporary storage device stores data between the configurations executed sequentially like a register in the CPU.
[0059]
In this way, a sequential processor model is constructed by configuration, data processing in the PAE matrix, and temporary storage in memory. In other words, with the above-described compilation in the VPU technology, Opcode is not executed sequentially but a complex configuration is executed. In the case of a CPU, one data word is generally processed by Opcode, whereas in the case of VPU technology, a plurality of data words (data packets) are processed by configuration. This improves the efficiency of the reconfigurable architecture because the relationship between reconfiguration effort and data processing is improved.
[0060]
At the same time, in the case of VPU technology, memory is used instead of registers. The reason is that data packets, not data words, are processed between each configuration.
[0061]
This memory can be configured as a random access memory, stack, FIFO, or any other memory architecture, in which case the best and most easily feasible configuration is generally obtained with FOFO.
[0062]
Here, the data is processed by the PAE matrix according to the configured algorithm and stored in one or more memories. The PAE matrix is reconfigured after processing a predetermined amount of data, the temporary result is retrieved from memory with the new configuration, and program execution continues. In this case, new data can be additionally flowed into the calculation from the external storage device and / or peripheral device, and the result can be written to the external storage device and / or peripheral device.
[0063]
In other words, the general flow of data processing is reading from the internal RAM, processing the data in the matrix as well as writing the data to the internal memory, with any external source to process the data Alternatively, data transmission destinations can be used in addition to or instead of the internal memory.
[0064]
The “sequence” in the CPU is defined as a new load of OpCode, whereas the “sequence” of the VPU described above is defined as (re) configuration performed by configuration. However, this does not mean that the field portion can operate as a sequencer in the conventional sense, not under specific conditions.
[0065]
Information about when and / or how to sequence, ie which configuration to configure next, can be represented by various information, which can be used individually or in combination Can do. For example, it is useful to use the following strategies alone and / or in combination or alternatively to derive information:
a) Define at the time of conversion by the compiler;
b) defined by an event network (trigger, DE 197 04 728.9), where the event network can represent internal and / or external states;
c) According to memory occupancy (trigger, DE 197 04 728.9, DE 196 54 846.2-53)
2.5.1 Effects of TDM on processor models
The division of the algorithm will clearly determine the relevant states, which are stored in memory during different configurations. If the state is only important within one configuration (locally related state), it need not be stored and this is advantageously taken into account by the compiler approach.
[0066]
Nonetheless, useful for the purpose of debugging the program to be executed is to store this information so that the debugger can access it. See DE 101 42 904.5 for this. This is also a reference for this application.
[0067]
Further additional information may be important, as the task switching mechanism is applied (eg by the operating system or interrupt source), interrupting the currently running configuration and loading another configuration When and / or when trying to continue the suspended configuration at a later time. This will be described in detail below.
[0068]
Let's use a simple example to show discriminative features for locally relevant states:
a) Branches of type "if () then ... else ..." fit completely in a single configuration, ie two data paths (branches) are fully mapped together in this configuration . The state resulting from the comparison is relevant but local, since this state is no longer required in the following configurations.
b) The same branch is too big to fit in a single configuration. In this case, multiple configurations are required to map the entire data path. In such situations, states are globally relevant and need to be stored and assigned to individual data. This is because subsequent configuration requires individual states of comparison in subsequent processing of the data.
[0069]
2.6 Task switching
In some cases, the introduction of an operating system has an additional impact on state considerations and responses. The operating system uses, for example, a task scheduler to manage multiple tasks, thereby providing multitasking. The task scheduler interrupts the task at a specific time and starts another task. After processing the task, the task scheduler returns to the interrupted task to continue processing. Here it is guaranteed that a single configuration that can be handled for a task will only finish after processing is complete, that is, when all data and states to be processed within that configuration cycle are stored. As long as you can, you can leave the locally relevant state unstored. This method, i.e. configuration completion and subsequent task switching, is an advantageous way for the operation of the reconfigurable processor and substantially corresponds to the sequence of the normal processor. The task is switched after the execution of the middle instruction is completed first.
[0070]
However, for most application cases, for example, in a real-time application, a very short reaction is required for a task switching request. It may be useful to interrupt the configuration before complete execution is complete. If the task scheduler interrupts the configuration before it is fully executed, the local state and / or data must be stored. This is even more advantageous when the end of execution of a configuration cannot be predicted. This is further useful in connection with the well-known outage problem and risk that the configuration does not complete at all (eg, due to errors), thereby avoiding system-wide deadlocks. Therefore, while considering task switching, the relevant state must be regarded as necessary for task switching and a new proper start of data processing. Therefore, the result memory and possibly the operand memory should also be protected when switching tasks, and they must be generated again at a later time, i.e. when returning to the task. This can be saved with the PUSH / POP instruction, and the method according to the prior art is performed. Furthermore, the state of data processing needs to be protected, that is, the pointer to the last fully processed operand must be protected. For example, see PACT18 here.
[0071]
There are two options for example depending on the task switching optimization:
a) The interrupted configuration is newly configured and only the operands are loaded. Data processing begins as if configuration processing had not yet started. In other words, all data calculations are simply performed from the beginning, in some cases the calculations are already performed in advance. This option is simple but not efficient.
b) The interrupted configuration is newly configured, with the operands and the already calculated results loaded into the individual memories. Data processing continues from the operands that were not completely calculated. This approach is very efficient, but assumes that the additional conditions that occur during the configuration process may be important in some cases, for example at least one that points to the last fully computed operand. This is when one pointer must be protected, thereby allowing a new start in its inheritance after a new configuration has been made.
[0072]
2.7 Context switching
The context switching described below provides a particularly advantageous variant for managing relevant data. What may be required for task switching and / or configuration execution and switching (see, for example, patent application DE 102 06 653.1, which is hereby incorporated by reference), for example, simply represents final values. In general, this means protecting data or states that are not stored in memory together with operational data for subsequent configuration.
[0073]
The context switching implemented according to the invention is advantageously performed such that the first configuration is removed and the data to be protected is left in the corresponding memory (REG) (memory, register, counter, etc.) Is done.
[0074]
A second configuration can then be loaded, which connects the REG to one or more memories in an appropriate manner according to the defined order. The configuration can access one or more global memories using, for example, an address generator. Thus, it is not necessary for the compiler to determine each individual memory location in advance and / or to access a REG configured as a memory. The contents of the REG are written to the global memory in the defined order according to the configured connection between the REGs, with individual addresses set by the address generator. The address generator generates addresses for one or more memories so that the previously described memory area (PUSHAREA) can be assigned to the removed first configuration. It is therefore advantageous to provide different address spaces for different configurations. In this case, the configuration corresponds to the PUSH of a conventional processor. Thereafter, the resource is used by another configuration.
[0075]
After that, the first configuration is started again. Before that, the third configuration starts, and the REGs of the first configuration are connected to each other in the defined order.
[0076]
For the purpose of accessing one or more global memories and / or for accessing a REG configured as a memory, the configuration can still use, for example, an address generator.
[0077]
In that case, it is advantageous that the address generator generates an address so that proper access to the PUSHAREA assigned to the first configuration is made. According to the address of the generated REG and the order in which it is configured, the REG data is written from the memory to the REG in the original order. This configuration corresponds to a conventional processor POP. Then the first configuration starts again.
[0078]
In summary, context switching is advantageously performed as follows. That is, the data to be protected is exchanged by the global memory by loading a special configuration that operates similar to the well-known processor architecture known as PUSH / POP. Such data exchange via global memory using a PUSH / POP exchange configuration is considered to be particularly important.
[0079]
The function will now be described based on an example:
Two sequences are added by one function, and the lengths of these sequences are unknown at the time of conversion and are known only at the time of execution.

This function is interrupted during execution, for example by task switching or because the memory prepared for x is full. According to the invention, a, b, x are present in the memory at this point. But i have to protect the length and if necessary. For this purpose, the configuration example is terminated, the register contents are maintained, and the configuration push is started, whereby i and the length are read from the register and written to the memory.

After execution, push is terminated and the register can be erased. Another configuration is performed. Some time later, the configuration example starts again. Before that, the configuration pop is started, and the register contents are read again from the memory.

After execution, pop is terminated and the register contents are retained. The configuration example is started again.
[0080]
2.8 Algorithm optimization
The control structure is separated from the algorithm structure by the conversion method described above. For example, one loop is broken down into a body (WHILE) and an algorithm structure (instruction). Advantageously, the algorithm structure can be optimized by additional tools that are optionally connected after the separation process. For example, the algebraic software that is connected later can optimize and minimize the programmed algorithm. This type of tool is known under the names AXIOM, MARBLE, etc. Minimization can achieve faster processing of the algorithm and / or very limited space requirements. Thereafter, the result of the optimization is led back to the compiler and further processed accordingly. It's also worth mentioning that modern compilers (front-ends) already implement multiple optimizations for algorithms (again partially algebraic), and of course they are implemented in the manner described here. It can be used as it is.
[0081]
It should be noted that the method described above and paragraphs 2.2.7 “Corresponding to time” and 2.3 “macro” can also be applied to the compiler based on PACT20. In this connection, PACT20 is also a reference for this application.
[0082]
3. Applicability to prior art processors with VLIW architecture, for example
It should be pointed out in particular here that instead of a PAE matrix, for example an array of arithmetic logic units according to the prior art as is common in VLIW processors and / or a plurality such as in a multiprocessor system, for example. An array of complete processors can also be used. In this case, the use of a single ALU is mentioned as a special case. Therefore, this method can be applied to a normal CPU.
[0083]
According to the paper [reference paper, Armin Nueckel], a method has been developed that allows the WHILE language to be transformed into a semantically appropriate finite automaton. Furthermore, a finite automaton can be used as a “subprogram” and vice versa. This allows the configuration to be mapped to various mounting technologies such as CPU, symmetric multiprocessor, FPGA, ASIC, VPU, etc.
[0084]
For example, optimally matched hardware can be assigned to each part of an application, or optimal hardware can be assigned based on a determination of whether it is good or not for each individual suitability. In this case, temporary resource allocation and resource reservation are also conceivable. In other words, for example, certain data flow structures are assigned to the data flow architecture, while sequential structures, if present and / or available, are mapped to the sequencer.
[0085]
Problems raised in resource assignment for individual algorithms can be solved, for example, by a “Job Assignment” algorithm for managing assignments.
[0086]
4). Implementation
The implementation of the compiler according to the invention assumes a “normal” sequential programming language such as C or Pascal. According to the properties of these languages, because of their sequential character, the time order is implicitly and intentionally generated by the language definition itself:
Example A:
Line 1: i ++
Line 2: a = i * b
Line 3: x = p-a
Line 4: j = i * i
By definition of the language, line 1 is firmly defined to be executed before line 2 before line 3 and before line 4. Nevertheless, line 4 can also be executed immediately after line 1, so that line 4 can be processed in parallel with lines 2 and 3.
[0087]
In other words, a further artificial and non-algorithm state is constructed with a sequential language. All that matters here is the proper time sequence of the calculations in Example A. Only after i is correctly defined, i.e., after row 1 is executed, the computation of row 4 is allowed. Row 2 may be processed only after i is properly defined (ie, after row 1 has been processed). Row 3 requires the result of row 2 (variable a), so calculation is only allowed if it is properly defined. Therefore, no special condition occurs due to data dependency.
[0088]
Based on the data dependency of variable a in rows 2 and 3 (row 3 uses a as an operand, a is the result of row 2), the compiler automatically converts the following conversion (arVec conversion) to represent parallelization or vectorization: ) Can be performed.
Line 2: VEC {a = i * b
Line 3: x = p-a}
Here, VEC is processed in succession by each expression separated by ';', meaning that the expression in curly braces can basically be pipelined. In order for the data processing after VEC to continue, all calculations should advantageously be performed and completed at the end of VEC {}.
[0089]
Even better, represent the two expressions as a vector in the compiler as an internal representation of the data structure:
VEC {a = i * b; x = p-q}
Row 4 represents a simple vector:
VEC {j = i * i}
Since row 4 can be computed simultaneously with row 2 and row 3, parallelism can be expressed as follows:
PAR {{VEC {a = i * b; x = p-a}; VEC {j = i * i}
PAR means that each expression separated by '{..}' can be processed simultaneously. In order for data processing after PAR to continue, all calculations should preferably be performed and completed at the end of PAR {}.
[0090]
If line 1 is fetched together:
VEC {i ++; PAR {{VEC {a = i * b; x = p-a}} {VEC {j = i * i}}}}
Since VEC {j = i * i} is represented as a vector with only one element, it can also be written as:
VEC {i ++; PAR {{VEC {a = i * b; x = p-a}} {j = i * i}}}
Another example shows the true state.
Example B:

Here, line 6 can only be executed after the calculation of lines 2 and 3. The calculations for lines 4 and 6 are performed alternatively. That is, the state of row 3 is related to subsequent data processing (related state).
[0091]
Conditional states can be expressed by IF for conversion:

In summary,

Another related state is created by a loop:
Example C:

Execution of line 3 is allowed only after the loop is finished. That is, it is a related state in conditional jump.
[0092]
The first transformation of the loop is as follows:

Rows 3 and 4 can be calculated in parallel. Because row 4 does not depend on the result of row 3:
PAR {{a = a * i} {i ++}}
Row 5 is a vector with the generated PAR. The reason is that the jump to the loop is permitted only after the calculation of each value is completed (that is, there is a temporal dependency here).
VEC {PAR {{a = a * i} {i ++}}; jump loop}
So for this condition:
loop: IF {{i> = 100} {jump exit} {VEC {PAR {{a = a * i} {{i ++}}; jump loop}}}
Row 1 is a conditional vector. This must be done before the condition (IF uses i as an operand, i is the result of row 1). Row 6 is a conditional vector. This is because a is used as an operand and a is the result of a condition.
Therefore, it is as follows (descriptively written):

The contents of VEC {} and PAR {} can be regarded as a simple combination network. The VEC and PAR are preferably configured as Petri nets, for example, so that subsequent processing is controlled after complete processing of the individual contents.
[0093]
Since VEC and PAR can be regarded as a simple combination network, it is necessary to protect the loop state. In other words, in this case, it is actually necessary to create a finite automaton.
[0094]
For this purpose, a variable is stored in the register by the instruction REG {}. This creates a finite automaton by combining the combinatorial network VEC and PAC with the register REG, which is configured to exactly match the algorithm:

It should be particularly pointed out here that according to the applicant's VPU technology (see PACT21), each PAE has an input register and / or output register, and an integrated handshake protocol (RDY / ACK) Ensures time accuracy and data availability. From this point of view, the requirement that their internal data processing must be complete when leaving VEC {} or PAR {} is automatically met for all variables used later. (If data processing has not ended, the subsequent calculation steps will wait for completion and arrival of data). The built-in resistor also eliminates feedback swings. The following formula is therefore appropriate for this technology:
VEC {PAR {{a = a * i} {i ++}} jump loop}
For other technologies that do not have the above configuration or have only a part, this equation should be expressed as:
VEC {PAR {{a = a * i} {i ++}}; REG {a; i}; jump loop}
It should be noted that in any case, this format enables the algorithm to be appropriately and optimally mapped to the reconfigurable processor in the applicant's VPU technology.
[0095]
REG can be used in combination networks VEC and PAR. Strictly speaking, this causes VEC and PAR to lose their combined network characteristics. However, abstractly, a REG can be viewed as a single complex element (REG element) in a combinatorial network, which is based on a specific execution time. Subsequent element processing is performed depending on the end of calculation of the REG element. With this conceptual inaccuracy in mind, the use of REG in VEC and PAR is permitted below, and it is particularly necessary to do so.
[0096]
As already mentioned, the use of REG is generally not required within one configuration of the Applicant's VPU and is always explicitly required only when the result of one configuration is stored, As such, REG actually matches the finite automaton explicit register in this application. Besides the synthesis of finite automata for loops, for example, finite automata are required in the following cases:
If the algorithm is too large to process within the PAE of the reconfigurable processor, it must be broken down into multiple sub-algorithms. Each sub-algorithm forms one configuration for the reconfigurable processor. In succession, that is, sequentially, each sub-algorithm is configured in the processor, with each previous configuration result being used as an operand for each new configuration.
[0097]
In other words, reconfiguration generates a finite automaton, which processes and stores the data at time t, possibly after some configuration at time t + 1, with the stored data differing as needed. Process and store again. What is important here is that t is not defined by the clock or instruction in the classical sense, but by the configuration. See, for example, the processor model presentation (PACT, 2000. 10, San Hose).
[0098]
In other words, the configuration is composed of a combination network composed of VEC and / or PAR, and the result is stored (REG) so that it can be reused in the next configuration.
Configuration 1: VEC {operand; {VEC | PAR}; REG {result 1}}
Configuration 2: VEC {Result 1; {VEC | PAR}; REG {Result 2}}
...
For ease of understanding, the examples and descriptions given so far represent the structures VEC, PAR, and REG in a high-level language and structured them in that language. What is common and advantageous, however, is to first represent their structure at an intermediate language level (see the principles of compiler design (Red Dragon), Aho, Sethi, Ullmann). It is particularly important to note that the compiler structure can be executed by VEC, PAR, and REG in general and automatically using a method such as graph analysis. However, for example, it is still possible to think of it here, and in some cases, it is advantageous that the VEC, PAR, and REG can be written in a high-level language directly as described above, so that the programmer can construct the high-level language. It will be possible to create.
[0099]
Generation
Automatic creation of VEC, PAR, and REG can be performed in various planes of the compiler process. For the time being, the most obvious thing is described based on the source code in the above example during execution of the preprocessor. But then a specially matched compiler is needed for another compiler.
[0100]
According to another aspect, compilers often perform automatic code optimization (eg, in a loop). Thus, efficient code decomposition is only useful after optimization has been performed, especially when a compiler (eg SUIF, Stanford University, etc.) has already optimized the code for parallel processing and / or vectorization. is there.
[0101]
A particularly advantageous method is therefore to bind the analysis to the compiler backend. The data structure in the compiler is converted into instructions of the target processor by the back end. A pointer structure such as DAG / GAG, tree or 3-address code is usually used as the data structure inside the compiler (compiler design (Red Dragon), Aho, Sethi, Ullmann). Partially Stack-Machine-Code is used (see the compiler's own C'T 1986 1-5). Since the data formats are basically equivalent and can be converted to each other, the present invention applies an advantageous scheme to the subsequent processing of graphs such as trees.
[0102]
Data dependencies and achievable parallelism according to the method described above can be easily identified automatically based on structure in the tree. For this purpose, it is possible to use, for example, a known ready-made graph analysis technique. As an alternative or as an option to this, the algorithm can be examined for data dependencies, loops, jumps, etc. in a correspondingly matched parse scheme. In this case, a method similar to expression evaluation can be used in the compiler.
[0103]
mapping
The subsequent transformation of the algorithm is therefore highly dependent on the target architecture. For example, Applicants' processor architecture (VPU, XPP) provides automatic data synchronization in hardware. That is, the proper time order of data dependency is automatically handled in hardware. According to another architecture, in some cases, the synthesis of appropriate state machines for data transmission control is additionally required.
[0104]
Of particular importance is the handling of conditional jumps. For example, Applicant's processor architecture provides multiple mechanisms for mapping and execution:
1. Reconfiguration of a processor or part of it by a higher-level configuration unit (patent application PACT01, 04, 05, 10, 13, 17)
2. Function expansion to an array of multiple PAEs (patent application PACT08), eg mapping both possible branches of a comparison simultaneously to this array
3. Wave configuration (PACT08, 13, 17), each adding a token that selects a valid configuration to various data to be processed
For now, mechanism 1 is typically a case that should typically be used. Mechanism 2 is already very cumbersome or impossible to implement at all for most technologies, and Case 3 is previously known only by the applicant's VPU technology.
[0105]
The implementation method to be selected depends on the complexity of the algorithm, the required data throughput (performance), and the exact design specifications of the target processor (eg, the number of PAEs).
[0106]
Example:
A simple comparison would calculate:

Reconfiguration of the processor (mechanism 1) according to the comparison results does not seem very useful. The deployment of two branches into the array (mechanism 2) is basically possible. PAE for calculating a = a * (− i) or a = a * i is controlled according to the comparison result (PACT08). Particularly efficient in terms of space is to superimpose both calculations (mechanism 3), so that after the comparison, the same PAE will process the data regardless of the result, but the data is provided with a token. The function a = a * (− i) or a = a * i is selected in each subsequent PAE that processes the data locally depending on the comparison by this token (PACT08, 13, 17). reference).
[0107]
Mechanism 1 causes a globally relevant condition because the subsequent complete configuration depends on it. Only locally relevant states occur according to mechanisms 2 and 3, because the states are no longer needed beyond fully implemented computations. In other words, the local or global state relevance also depends on the selected mapping to the processor architecture. States that are related beyond one configuration, ie beyond the combinatorial network of finite automata that represent a single configuration (ie, the states required by subsequent finite automata) can be considered basically global. . Let me reiterate the vague term “combination network” used here.
[0108]
Instruction model of the generated processor
According to the present invention, a processor model for a reconfigurable processor including all basic instructions is generated.
[0109]
Arithmetic / logical instructions are mapped directly to the combinatorial network.
[0110]
The jump (Jump / Call) is directly developed in the combination network or realized by reconfiguration.
[0111]
Condition and control flow instructions (such as if) are either fully triggered and processed in the combinatorial network or transferred to a higher-level configuration unit, which performs reconfiguration depending on the state that has occurred.
[0112]
Load / Store operations are advantageously mapped to a separate configuration, which is implemented as a well-known DMA by the address generator, which allows external storage from the internal memory (REG {}) by the address generator. Writing to the device is performed, or loading from an external storage device and / or peripheral device to the internal memory is performed. However, this may be configured together with the configuration for data processing or may be operated together.
[0113]
The Register-Move operation is realized by a bus between each internal memory (REG {}) in the combination network.
[0114]
Push / Pop operations are realized by a separate configuration, which may be a write or external write using an address generator from a specific internal register and / or internal memory (REG {}) to an external storage in some combinational networks. Reading from the storage device is performed and is preferably performed before or after the original data processing configuration.
[0115]
5). Description of drawings
The following drawings show an implementation example and a configuration example of a compiler.
[0116]
FIG. 1a shows the structure of a conventional finite automaton, in which a combination network (0101) is coupled to a register (0102). Data can be directly guided to 0101 (0103) and 0102 (0104). Feedback (0105) from the register to the combinatorial network allows state processing that depends on one or more previous states. The processing result is indicated by 0106.
[0117]
FIG. 1b shows a finite automaton with a reconfigurable architecture according to PACT01 and PACT04 (FIGS. 12-15 of PACT04). The combination network (0101) according to FIG. 1a is replaced by PAE0107 (010b). The register (0102) is constituted by a memory (0102b), which can be stored for a plurality of cycles. Feedback by 0105 is performed by 0105b. The input (0103b or 0104b) is equivalent to 0103 or 0104. Direct access to 0102b may be achieved by array 010b, possibly via a bus. The output side 0106b is also equivalent to 0106.
[0118]
FIG. 2 shows a finite automaton mapping for the reconfigurable architecture. 0201 (x) forms a combination network (corresponding FIG. 1b can be configured as a PAE). In this case, one or more operand memories (0202) and one or more result memories (0203) are provided. The additional data input / output side by 0103b, 0104b, and 0106b is not drawn for easy viewing. One address generator (0204, 0205) is assigned to each memory. The operand memory and the result memory (0202, 0203) are physically or virtually coupled to each other so that, for example, the result of the operation of one function or another function can be used as an operand and / or The result of one function and the newly supplied operand can be used as the operands of another function. This type of connection can be formed, for example, by a bus system, or can be formed by a (re) configuration that newly configures a memory function and a network connection with 0201.
[0119]
FIG. 3 shows various aspects relating to correspondence with variables. In FIG. 3a, different calculation stages are shown for 0301, 0302 and 0303 respectively. These steps may be simply combined or separated from each other via a register. f1, f2, and f3 are functions, and x1 is the variable described above. FIG. 3b shows the use of the variable x1 in the function x1: = x1 + 1. FIG. 3c shows the properties of a finite automaton for the calculation of x1: = x1 + 1 in one configuration. In the next configuration, 0306 and 0304 are exchanged for the purpose of obtaining a complete finite automaton. 0305 represents an address generator for memories 0304 and 0306.
[0120]
FIG. 4 shows a loop implementation. Hatched modules can be generated by the micro (0420, 0421). 0421 can also be inserted into the feedback without delay by analysis of the graph. In FIG.
WHILE TRUE DO
x1: = x1 + 1;
A simple loop implementation of the form is shown. Counter +1 (0401) is located at the core of the loop. 0402 is a multiplexer, which first leads the starting value x1 (0403) to 0401, and then applies feedback (0404a, 0404b) at each iteration. A register (see REG {}) (0405) is incorporated in the feedback, thereby avoiding the occurrence of non-controllable feedback, that is, uncontrollable feedback from the output side of 0401 to its input side. 0405 is clocked by the VPU operating cycle and thus determines the number of iterations per hour. Individual count states can be retrieved at 0404a or 0404b. However, the loop does not end depending on the definition of the high-level language. For example, in HDL (for example, according to the prior art such as VHDL and Verilog), a signal can be used in 0404, but in a sequential programming language (for example, C), 0404 cannot be used. The reason is that the loop does not end and therefore no exit value is supplied. The multiplexer 0402 implements a macro, which is generated by a loop structure. Macros are instantiated by WHILE conversion. Resistor 0405 is either a part of the micro, or is inserted precisely where there is no delay feedback in accordance with graph analysis according to the prior art, thereby eliminating the tendency to swing.
[0121]
In FIG.

A real loop structure of the form is shown. This structure corresponds to FIG. 4a in the core and therefore the same reference numbers were used. The circuit shown additionally controls the validity of the result (0410), and the 0404a signal is transferred to the subsequent function (0144) only when the loop abort criterion is reached. Cancel determination is x1 <10 by comparison (comparison stage 0412). As a comparison result, the status flag (0413) is sent to the loop control multiplexer 0402 and the result transfer control function 0411. The status flag 0413 can be implemented, for example, by a trigger according to DE 197 04 728.9. Similarly, status flag means 0413 can be sent to the CT, based on which the CT identifies the end of the loop and performs reconfiguration.
[0122]
In FIG.
FOR i * = 1 TO 10
x1: = x1 * x1;
Iterative calculation is shown. Since the basic function substantially corresponds to FIG. The function block 0501 performs multiplication. The FOR loop is implemented by another loop in the same way as in FIG. 4b, and this is simply suggested as block 0503. Block 0503 supplies the comparison status to the abort determination unit. This status is used as it is for repetitive control, so means 0412 (shown here as 0502) is omitted.
[0123]
In FIG.
FOR i: 1 = 1 TO 10
x1: = x1 * x1;
The evolution of the calculation is shown. Since the number of iterations over the conversion time is known exactly, the computation can be mapped to a sequence of i multiplications (0510).
[0124]
FIG. 6 shows the configuration of the WHILE loop according to FIG. 4 that spans multiple configurations. In this case, the state of the loop (0601) is a related state because it has a decisive influence on the function in the subsequent configuration. The calculation spans four configurations (0602, 0603, 0604, 0605). Data is stored in memory (see REG {}) during each configuration (0606, 0607). Here, 0405 also replaces 0405. Memory occupancy can be used as a reconfiguration criterion, which is indicated by 0606, 0607, memory full / empty and / or 0601, which indicates a loop abort. In other words, a trigger is generated according to the occupied state of the memory (PACT01, PACT05, PACT08, PACT10), which is sent to the configuration unit to trigger reconfiguration. The state of the loop (0601) can also be transmitted to the CT. Correspondingly, the CT can configure the subsequent algorithm when it reaches the abort criteria, or it will first execute the rest of the loop (0603, 0604, 0605) if necessary, then Subsequent configurations can be loaded.
[0125]
6). Parallelism
FIG. 6 shows possible limits of parallelism. As long as the operation of the operand does not depend on the feedback 0608, the loop can be calculated for each block, that is, according to the occupied state of the memory 0606/0607. In this way a high degree of parallelism is achieved.
[0126]
As long as the calculation of the operands depends on the previous calculation result, that is, as long as the feedback 0608 enters the calculation, this approach becomes inefficient, because only one operand can be calculated in the loop. .
[0127]
If the effective ILP (Instruction Level Parallelism) is high in the loop and the time required for configuration is short (PACT02, PACT04, PACT13, PACT17), the computation deployed in PAE is more efficient in VPU Can be. If this is not the case, the loop can be considered as a sequential architecture (a processor separate from PA or an implementation in PA, DE 196 51 075.9-53, DE 196 54 846.2-53 and in particular DE 199 26 538.0 in FIG. 11, 16, 17, 23, 30, 31, and 33).
[0128]
Computational time analysis can be done in the compiler at the time of conversion according to the following section and / or can be measured experimentally at run time, which allows later introduction of optimizations and learning A particularly self-learning compiler is possible.
[0129]
What is important to the present invention is an analysis and parallelization technique. Various techniques according to the prior art can be used for parallel analysis and execution. The function to be mapped is represented by a graph (see PACT13; DE 199 26 538.0). In this case, an application can be synthesized from an arbitrary number of various functions. The graphs are examined for the parallelism they contain, and all optimization techniques can be used in advance. For example, perform the following test:
6.0.1 ILP (Instruction Level Parallelism)
The ILP indicates which instructions can be executed simultaneously (see PAR {}). This kind of analysis can be done easily based on considerations about the dependency of each node in the graph. Corresponding techniques are well known per se in the prior art and mathematics, see for example VLIW compilers and synthesis tools.
[0130]
However, special care is required, for example, in some cases of nested condition execution (IF). This is because there are often few or no proper predicates for paths that can be executed in parallel, because there is a strong dependence on the space of individual parameter values, which is often not at all. I don't know or I don't know enough. Also, for accurate analysis, so much computation time may be required that it is no longer useful and feasible.
[0131]
In such cases, the analysis can be simplified, for example by a programmer's instruction, and / or a corresponding compiler switch, which allows high parallelism in a questionable situation (possibly in a resource-intensive manner) or ( It can be made to operate on the premise of low parallelism (in some cases in terms of performance). Similarly, in such cases, experimental analysis can be performed at runtime. According to PACT10 and PACT17, a technique is known that enables creation of statistics on program characteristics at runtime. In this way, for example, maximum parallelism can be assumed for the time being. Each path sends a message back for each execution to a statistical unit (this is implemented, for example, in CT or another stage, see PACT10, PACT17, but basically a unit with PACT04 is also available). By using statistical measures, it is possible to evaluate which route is actually executed in parallel. A further possibility is to evaluate based on the data whether the paths are frequently executed in parallel, rarely in parallel or not at all. This type of route usage message is advantageous but not essential.
[0132]
In this way, execution can be optimized at the next program call. For this purpose, the statistical information can be transferred to a hard disk or the like in a nonvolatile manner. As is known from PACT22, PACT24, multiple configurations can be configured simultaneously, after which they are controlled by a trigger (PACT08), or only a subset is configured and the remaining configurations are The corresponding trigger is loaded later as needed by sending it to the load unit (CT, PACT10).
[0133]
For clarity, the value PAR (p) used below allows what parallelism, ie how many ILPs, can be achieved at a particular stage (p) in the data flow graph transformed from the function at the instruction level. (FIG. 7a).
[0134]
Also important is vector parallelism (see VEC {}). Vector parallelism is useful when relatively large amounts of data should be processed. In such situations, linear operation sequences can be vectorized, i.e. all operations can process data simultaneously, with each individual operation typically processing a separate data word.
[0135]
This is partially impossible in a loop. Analysis and optimization are therefore required. For example, a function graph can be represented by a Petri net. According to the properties of Petri nets, the transfer of results is controlled by nodes, so that for example loops can be modeled. Data throughput is determined by feedback of the results within one loop. Example:
The operation result n is required for operation n + 1: only one operation can be executed in the loop.
The operation result n is required for the operation n + m: m−1 operations can be performed in the loop.
-The result of the loop is decided to stop the loop, but it is not involved in the calculation of the result: no feedback is required. In some cases, the wrong (extra) value will certainly enter the loop, but the resulting output can be stopped at the end of the loop as soon as the end condition is reached.
Prior to analysis of the loops, they can be optimized according to conventional techniques. For example, certain instructions can be pulled from the loop and placed before or after the loop.
[0136]
For clarity, the value VEC used below can represent the degree of vectorization of a function. In other words, VEC represents how many data words can be processed simultaneously in a group of operations. VEC is a function n _nodes The number of calculation elements required for data and data n that can be calculated simultaneously in a vector n _data And can be calculated from, for example, VEC = n _nodes / n _data Can be calculated by
[0137]
For example, a function can be mapped to five computing elements (n _nodes = 5), if each computing element can process data simultaneously (n _data = 5), VEC = 1 (FIG. 7b). On the other hand, for example, a function can be mapped to five computing elements, but if only one computing element can process data each time (n _data = 1), VEC = 1/5 (Fig. 7c).
[0138]
VEC can be calculated for an entire function and / or for a portion of a function. Although calculation and evaluation of VEC is generally advantageous, both approaches can be advantageous with the compiler of the present invention.
[0139]
Although it is advantageous if it can be realized, according to FIG. 7a, PAR (p) is determined for each column of the graph. A row in the graph is defined such that it is executed within one clock unit. The number of operations depends on the individual VPU implementation.
[0140]
If PAR (p) matches the number of nodes in row p, all nodes can be executed in parallel. If PAR (p) is smaller, only a specific node is executed alternatively. Each alternative execution of one node is grouped in one PAE. An alternative corresponding to the status of the data processing is realized at runtime by the selection mechanism, which is described, for example, in PACT08.
[0141]
Similarly, a VEC is assigned to each line of the graph. VEC = 1 for a row means that the row continues to exist as a pipeline stage. If a row is less than 1, all subsequent rows that are also less than 1 are combined. The reason is that pipelining is impossible. They are grouped into a sequence according to the order of operation, then configured to form a PAE and executed sequentially at runtime. Corresponding methods are known, for example, from PCT / DE 97/02949 and / or PCT / DE 97/02998.
[0142]
According to the method described above, a complex parallel processor model can be constructed by grouping sequences. For example, a sequencer structure for mapping reentrant code can be generated. The synchronization required for each purpose can be executed by a time stamp method described in PACT18, for example, or can be executed by a trigger method described in PACT08.
[0143]
When multiple sequencers or sequential parts are mapped to a single PA, it is advantageous for performance reasons to coordinate the performance of the individual sequencers with each other. This can be done particularly advantageously by matching the operating frequencies of the sequencers. From PACT25 and PACT18, for example, a scheme is known that allows specific timing control by individual PAEs or PAE groups.
[0144]
In this case, the sequencer frequency can generally be determined based on the number of cycles required to process the function assigned to that sequencer. To process an assigned task, for example, if a sequencer requires 5 clock cycles for its function processing, while the rest of the system requires exactly one clock cycle, the sequencer clock remains 5 times higher than the system clock. If there are multiple sequencers, different clock cycles can be set for each. In this case, clock multiplication and / or clock division can be performed.
[0145]
The plurality of functions are divided according to the method described above. The memory for data and associated status is inserted accordingly in the partitioning. With PACT13 and PACT18 another alternative and / or developed approach to this is known. Many VPUs can provide differential reconfiguration functions according to PACT01, PACT10, PACT13, PACT17, PACT22, and PACT24. This can be applied when reconfiguration requires relatively little change in the PAE array. In other words, some configurations are only reconfigured with respect to the current configuration. In this case, the split can be configured so that the (differential) configuration following the configuration receives only the reconfiguration data needed and does not form a complete configuration. Advantageously, the compiler according to the invention is arranged to identify and support this.
[0146]
Reconfiguration scheduling can be performed according to the status of reporting the function to the load unit (CT), and the load unit itself selects the next configuration or subconfiguration based on the arrived status and performs configuration. This type of method is known in detail by PACT01, PACT05, PACT10, PACT13, PACT17. Further support by scheduling is to allow configuration preload during the run time of another configuration. In this case, a plurality of configurations can be speculatively preloaded in some cases, that is, it is possible to preload without confirming whether the configuration is required in the first place. This is particularly advantageous when, for example, a fairly long data stream that can be processed without configuration occurs, the CT is at least almost unloaded, especially when there is no task load or very little. This is when there is only a small task load. The configuration to be applied at runtime is selected by a selection mechanism, for example according to DE 197 04 728.9 (see also NIS in PACT22 / 24, for example).
[0147]
Similarly, a local sequencer can be controlled by its data processing status, as is known, for example, from DE 196 51 075.9-53, DE 196 54 846.2-53, DE 199 26 538.0. In order to perform these reconfigurations, further dependent or non-dependent status can be reported to the CT (see eg PACT04, LIBACK).
[0148]
Next, what has been described so far will be described with reference to the drawings. In this case, the following symbols are used in the following for ease of explanation: V is “or” and ∧ is “and”.
[0149]
FIG. 8a shows how the graph according to FIG. 7a is mapped to a group of PAEs with the maximum achievable parallelism. All operations (instructions i1-i12) are mapped to individual PAEs.
[0150]
In FIG. 8b, the same graph is depicted, for example, with the maximum possible vectorization potential. However, here the set of operations V2 = {i1, i3}, V3 = {i4, i5, i6, i7, i8}, V4 = {i9, i10, i11} are not parallel but par (par ({2,3, 4}) = 1, so in this case resources are conserved by assigning a set of operations P2, P3, P4 to one PAE, with the status signal for each data word at each stage individually The operations to be executed in the PAE are selected, and the PAEs are networked as a pipeline (vector), and each PAE performs an operation on a different data word every clock.
[0151]
In this case, proceed as follows:
PAE1 calculates the data and transfers it to PAE2. Along with these data, PAE1 also transfers a status signal indicating whether i1 is to be executed or i2 is to be executed.
PAE2 continues to calculate data from PAE1. According to the incoming status signal, the operation (i1, i2) to be executed is selected and calculated. According to the calculation, PAE2 transfers a status signal indicating whether (i4 V i5) V (i6 V i7 V i8) should be executed to PAE3.
PAE3 continues to calculate PAE2 data. According to the incoming status signal, the operation (i4 V i5) V (i6 V i7 V i8) to be executed is selected and calculated. According to the calculation, the PAE 3 transfers a status signal indicating whether to execute i9 V i10 V i11 to the PAE 4.
PAE4 continues to calculate PAE3 data. According to the incoming status signal, the operation i9 V i10 V i11 to be executed is selected and calculated.
PAE5 continues to calculate the data for PAE4.
[0152]
A suitable method that can be implemented and hardware that can implement the above-mentioned statements very well are described in DE 197 04 728.9 (FIGS. 5 and 6). PACT04, PACT10, and PACT13 also describe methods that are generally available, but this is a relatively complicated method.
[0153]
The same graph is drawn in FIG. 8c. In this example, vectorization is impossible, but PAR (p) is high, that is, a plurality of operations can be executed simultaneously in one line. The operations that can be executed in parallel are P2 = {i1 ∧ i2}, P3 = {i4 ∧ i5 ∧ i6 ∧ i7 ∧ i8}, P4 = {i9 ∧ i10 ∧ i11}. Each PAE is network-coupled so that they can arbitrarily exchange arbitrary data with each other. In this case, each PAE performs an operation only when an ILP occurs in the corresponding cycle, otherwise they behave neutrally (NOP), in order to minimize performance loss. In some cases, the number of clocks can be reduced and / or clock interruption and / or current interruption can be performed.
[0154]
In this case, proceed as follows:
In the first cycle, only PAE2 operates and data is transferred to PAE2 and PAE3.
In the second cycle, PAE2 and PAE3 operate in parallel, and their data are transferred to PAE1, PAE2, PAE3, PAE4, and PAE5.
In the third cycle, PAE1, PAE2, PAE3, PAE4, and PAE5 operate, and data is transferred to PAE2, PAE3, and PAE5.
In the fourth cycle, PAE2, PAE3, and PAE5 operate and data is transferred to PAE2.
In the fifth cycle, only PAE2 operates.
[0155]
This function therefore requires 5 cycles for the calculation. Therefore, in order to achieve a reasonable performance, the corresponding sequencer is operated with a clock five times that of its surroundings.
[0156]
PACT02 (FIGS. 19, 20, and 21) describes a feasible method corresponding to this. Furthermore, generally available methods are described in PACT04, PACT10, and PACT13, but this is a relatively complicated method. Still other schemes and / or hardware may be utilized.
[0157]
FIG. 8d shows a graph according to FIG. 7a for the case where no parallelism is available. In order to calculate a data word, it is necessary to execute each stage in succession. Within each stage, exactly one branch of the plurality of branches is processed.
[0158]
This function also requires five cycles for the calculation: cy1 = (i1), cy2 = (i2 V i3), cy3 = (i4 V i5 V i6 V i7 Vi8), cy4 = (i9 V i10 Vi11), cy5 = (i12) is required. Therefore, the corresponding sequence is operated with a clock of 5 times in the ratio to its surroundings in order to achieve an appropriate performance. This type of function can be mapped by a simple sequencer according to PACT02 (FIGS. 19, 20, and 21), for example, as in FIG. 8c. PACT04 and PACT10, 13 also describe a generally available technique, but this is a relatively complicated technique.
[0159]
The mapping shown in FIG. 8 can be arbitrarily synthesized or grouped. For example, the same function is depicted in FIG. 9a, but according to this function, the paths (i2 ∧ (i4 V i5) ∧ i9) and (i3 ∧ (i6 V i7 V i8) ∧ (i9 V i10)) are It can be executed in parallel. (I4 V i5), i6 V i7 V i8), and (i9 V i10) are alternatives. This function can be further vectorized. According to the pipeline that can be constructed in this manner, the functions to be executed for each of the three PAEs (PAE4, PAE5, PAE7) are determined based on the status signals.
[0160]
A similar example is shown in FIG. 9b, in which case vectorization is not possible. However, the paths (i1ii2∧ (i4Vi5) ∧i9∧i12) and (i3∧ (i6Vi7Vi8) ∧ (i10Vi11)) are parallel. In this way, optimal performance can be achieved through the use of two PAEs that also perform parallel processing in parallel paths. The synchronization between the PAEs is preferably effected by a status signal generated by PAE1. This is because it is calculated at the start (i1) and end (i12) of the function.
[0161]
Of particular note here is the ability to generate a symmetric parallel processor model (SMP) or similar multiprocessor model in use today from multiple arrays of multiple sequences.
[0162]
It should be further noted that a new configuration can be loaded into all configuration registers for scheduling both in the background and / or during data processing.
[0163]
Here, for example, it is possible to build the hardware as known from DE 196 51 075.9-53. In this way, independent memory areas or registers that can be called independently of each other can be used. A jump to a specific point is performed by an incoming trigger, and in some cases, it is possible to jump by a jump instruction (JMP, CALL / RET) that can be executed conditionally.
[0164]
According to DE 196 54 846.2-53, independent write / read pointers can be used, which basically gives the background independence, ie the possibility of access. Further, for example, the memory can be segmented, which provides additional independence. In some cases, jumps can be made by using jump instructions (JMP, CALL / RET) that can be executed even under certain conditions.
[0165]
According to DE 197 04 728.9, the individual registers that can be selected by triggering can be made essentially independent, so that an independent configuration is possible, especially in the background. Jumps in registers are not possible and selection is made exclusively via trigger vectors.
[0166]
The basic factor for evaluating the efficiency of PAR and VEC is the format of the data processed by the individual structures. Useful, for example, is to deploy structures that process large amounts of data, i.e. pipelining or parallelizing. This is the case for video data and communication data, for example. Structures that process only a small amount of data (eg, keyboard input, mouse, etc.) are not useful to deploy and, conversely, block resources for other algorithms.
[0167]
Therefore, it is proposed here to parallelize and vectorize only an algorithm, structure or part of an algorithm that processes a correspondingly large amount of data based on various instructions or hints. This type of instruction or hint can be, for example:
1. Data format (arrays, streams are developed before individual characters, for example, because of the large amount of data).
2. Access format (linear program sequences are mapped in, for example, a sequencer, while loops are useful for deployment because of the high number of executions, for example).
3. Source and / or target format (keyboard and mouse data rates are too low for efficient deployment, for example, while network and / or video sources and / or targets have significantly higher data rates).
[0168]
At that time, any set of these instructions or hints can be added for analysis.
[0169]
7). Definition of terms
Local association status:
State relevant only in one specific configuration
Global association status:
Conditions that are related across multiple configurations and that need to be exchanged between multiple configurations
Related status:
The state required for its proper execution within an algorithm, ie, the state described and used by that algorithm
Unrelated state:
State that is not important to the original algorithm and is not described in the algorithm, but is required by the hardware to be executed depending on the implementation
[Brief description of the drawings]
[0170]
FIG. 1a is a diagram showing the structure of a conventional finite automaton, and FIG. 1b is a diagram showing a finite automaton with a reconfigurable architecture according to PACT01 and PACT04.
FIG. 2 is a diagram illustrating a mapping of a finite automaton to a reconfigurable architecture.
FIG. 3 is a diagram illustrating various viewpoints relating to correspondence with variables.
FIG. 4 shows a loop implementation.
FIG. 5 is a diagram showing iterative calculation and development of calculation.
6 shows the configuration of the WHILE loop according to FIG. 4 spanning a plurality of configurations.
FIG. 7 is a diagram showing a data flow graph and vector parallelism.
FIG. 8 is a diagram illustrating a state of mapping to a PAE group.
FIG. 9 illustrates mapping composition and grouping.

Claims (20)

In the method of converting a high-level language into a reconfigurable architecture,
Constructing a finite automaton for computation to form a composite combinatorial network from individual functions, and assigning a storage device for storing operands and results to the network,
How to convert a high-level language into a reconfigurable architecture. A high-level language code is prepared in a method of processing and / or processing data by a multi-dimensional field having a reconfigurable ALU, and the code is converted to construct a finite automaton for calculation, and a complex combination network is individually set. A storage device formed from a function and storing operands and / or results for the network,
A method of processing and / or processing data with multidimensional fields. The method according to claim 1 or 2, wherein the complex combinatorial network is constructed and / or decomposed so that the PAE matrix can run without configuration for as long as possible. 4. A method according to any one of claims 1 to 3, wherein a complex instruction is defined and the complex combinatorial network is constructed and / or decomposed so that the PAE matrix can be run as long as possible without reconfiguration. . The method according to any one of claims 1 to 4, wherein the finite automaton is constructed directly from imperative source text. Build a finite automaton from operations aligned with coarse-grained logic circuits and / or existing fine-grained elements (FPGA cells, state machines, etc. in VPU), for example, exclusively from operations aligned with them Item 6. The method according to any one of Items 1 to 5. The method according to any one of claims 1 to 6, wherein the finite automaton is decomposed into a plurality of configurations. The method according to any one of claims 1 to 7, wherein the generated configuration is continuously mapped to a PAE matrix and the working data and / or state to be transmitted between each configuration is stored in a storage device. 9. The method according to claim 1, wherein the storage device is designated or prepared in advance by a compiler. 10. A method as claimed in any preceding claim, wherein during configuration, data from a source external to the VPU and / or internal storage is processed and written to the external source and / or internal storage. 11. A method according to any one of the preceding claims, wherein storage is provided for an entire data set that is larger than a single data word. 12. A method according to any one of the preceding claims, wherein data is stored in a storage device as specified by a compiler when processing an ongoing configuration. To control storage for operands, storage for results, branch and / or compare instructions, ie, conditions such as IF, CASE, etc., a network of loops (WHILE, FOR, REPEAT), and storage The method according to claim 1, wherein the address generator is provided by an automaton. Allocate storage as required to state, distinguish between states that are algorithmically related and not related to the assignment, eg used with the states needed in the algorithm to describe the proper function 14. A method according to any one of the preceding claims, wherein the method distinguishes from unrelated conditions arising from hardware and / or selected mappings or for secondary reasons. 2. Load / Store operations using external addressing, i.e. data transmission with external components, and internal addressing, i.e. data transmission between PAEs, e.g. data transmission between RAM-PAE and ALU-PAE. 15. The method according to any one of 1 to 14. 16. A method according to any one of the preceding claims, wherein in data processing the first configuration is removed and the data to be protected is retained in a corresponding storage device (REG) (memory, register, counter, etc.). 17. A method according to any one of the preceding claims, wherein the first configuration is reloaded and the pre-protected data assigned to the configuration is accessed. Loading a second configuration to access pre-protected data, the second configuration connecting the REGs with one or more global storage devices in order in an appropriate manner; For example, an address generator is used to access the global storage device, which preferably generates an address for the global storage device to remove the written storage area (PUSHAREA). The method according to claim 1, wherein the method is uniquely assignable to a configuration. Performs transformations for the representation of parallelism and / or vectorization possibilities (Par-Vec transformation) automatically and / or configures the VEC and PAR parts as Petri nets, preferably individual content 19. A method according to any one of the preceding claims, wherein subsequent processing is controlled after complete processing. Map arithmetic / logical instructions directly to the combinatorial network and / or
Deploy jumps / calls directly into combinatorial networks and / or implement by reconfiguration and / or
Conditional and control flow instructions (such as if) are completely disassembled and / or processed in the combinatorial network and / or transferred to a higher-level configuration unit, which reconfigures according to the generated status And / or
Load / Store operations are mapped to separate configurations and / or implemented by an address generator, using the address generator to write from an internal storage device (REG {}) to an external storage device, And / or load from external storage devices and / or peripherals to internal storage devices, and / or
Register-Move operation is realized through a bus between each internal storage device (REG {}) in the combination network,
Push / Pop operation is realized by a separate configuration, which allows the address generator to write from a specific internal register and / or internal storage device (REG {}) to an external storage device in the combination network. Using and / or reading from, and preferably performing the operation before or after the original data processing configuration,
20. A method according to any one of claims 1 to 19.