(57)【特許請求の範囲】
【請求項１】
それぞれ個別アルゴリズム（ａ，ｂ，ｃ，ｄ，ｅ）を実行するために十分なリソースを有しているリコンフィギュレーション可能な回路（１）を用いて個別アルゴリズムを実行するための方法であって、
実行すべきアルゴリズムを前記回路において時間的に相次いで実行し、
該回路をアルゴリズムの実行の期間および／または実行の後に、次に実行されるべきアルゴリズムに対して、少なくとも、次に実行されるべきアルゴリズムが現在実行中のアルゴリズムとは異なっている場合、リコンフィギュレーションし、しかも
現在実行中のアルゴリズムの実行後に種々異なったアルゴリズムが実行される可能性があるとき、実行中のアルゴリズムの次に最大の確率で実行されるだろうというアルゴリズムに対して回路をリコンフィギュレーションする
いう方法において、
所定のアルゴリズムの次に実行されるべき可能性がある種々異なったアルゴリズムのそれぞれに対して、それぞれのアルゴリズムが該所定のアルゴリズムの実行後過去においてどのくらいの頻度で実行されたかを求め、かつ
回路を、該所定のアルゴリズムの実行後過去において最も頻繁に実行されたアルゴリズムに対してリコンフィギュレーションする
ことを特徴とする方法。
【請求項２】
現在実行中のアルゴリズムの実行の期間に行われる、次に実行されるべきアルゴリズムの実行に対する回路（１）のリコンフィギュレーションの際に、現在実行中のアルゴリズムの実行に対してコンフィギュレーションされた回路部分をリコンフィギュレーションする
請求項１記載の方法。
【請求項３】
所定のアルゴリズムの後に実行されるべき可能性がある種々異なったアルゴリズムのそれぞれに対して、数（ｘ）を割り当て、ここで該数はそれぞれ
所定の初期値（ｘ０）を有し、
当該の数に配属されているアルゴリズムが所定のアルゴリズムの実行後に実行されるとき、所定の値（＋Δｘ）だけ変化され、かつ
当該の数に配属されているアルゴリズムが所定のアルゴリズムの実行後に実行されないとき、所定の別の値（−Δｘ）だけ変化される
請求項１または２記載の方法。
【請求項４】
それぞれ個別アルゴリズム（ａ，ｂ，ｃ，ｄ，ｅ）を実行するために十分なリソースを有しているリコンフィギュレーション可能な回路（１）を用いて個別アルゴリズムを実行するための装置であって、
実行すべきアルゴリズムは前記回路において時間的に相次いで実行され、
該回路は、少なくとも、次に実行すべきアルゴリズムがちょうど現在実行中のアルゴリズムとは異なっている場合、アルゴリズムの実行の期間および／または実行の後に、次に実行すべきアルゴリズムに対してリコンフィギュレーションされ、しかも
現在実行中のアルゴリズムの実行後に種々異なったアルゴリズムが実行される可能性があるとき、回路は、実行中のアルゴリズムの次に最大の確率で実行されるだろうというアルゴリズムに対してリコンフィギュレーションされる
という装置において、
所定のアルゴリズムの後に実行されるべき可能性がある種々異なったアルゴリズムのそれぞれに対して、それぞれのアルゴリズムが所定のアルゴリズムの実行後過去においてそれぞれのアルゴリズムが何回実行されたかが求められ、かつ
回路は、所定のアルゴリズムの実行後の過去において最も頻繁に実行されたアルゴリズムに対してリコンフィギュレーションされる
ことを特徴とする装置。
【請求項５】
現在実行中のアルゴリズムの実行の期間に行われる、次に実行されるべきアルゴリズムの実行に対する回路（１）のリコンフィギュレーションの際に、現在実行中のアルゴリズムの実行に対してコンフィギュレーションされた回路部分がリコンフィギュレーションされる
請求項４記載の装置。
【請求項６】
所定のアルゴリズムの後に実行されるべき可能性がある種々異なったアルゴリズムのそれぞれに対して、数（ｘ）を割り当て、ここで該数はそれぞれ
所定の初期値（ｘ０）を有し、
当該の数に配属されているアルゴリズムが所定のアルゴリズムの実行後に実行されるとき、所定の値（＋Δｘ）だけ変化され、かつ
当該の数に配属されているアルゴリズムが所定のアルゴリズムの実行後に実行されないとき、所定の別の値（−Δｘ）だけ変化される
請求項４または５記載の装置。
【請求項７】
前記数（ｘ）の変化はアップ方向またはダウン方向に計数するカウンタ（２１，２２，２３，２４，２５）によって行われる
請求項６記載の装置。
【請求項８】
前記カウンタ（２１，２２，２３，２４，２５）は前記数（ｘ）を、該数が所定の最大値より小さいときにだけ高める
請求項７記載の装置。
【請求項９】
前記カウンタ（２１，２２，２３，２４，２５）は前記数（ｘ）を、該数が所定の最小値より大きいときにだけ低減する
請求項７または８記載の装置。
【発明の詳細な説明】
【０００１】
本発明は、請求項１の上位概念に記載の通り、それぞれ個別アルゴリズムを実行するために十分なリソースを有しているリコンフィギュレーション可能な回路を用いて個別アルゴリズムを実行するための方法であって、実行すべきアルゴリズムを前記回路において時間的に相次いで実行し、該回路をアルゴリズムの実行の期間および／または実行の後に、次に実行されるべきアルゴリズムに対して、少なくとも、次に実行されるべきアルゴリズムが現在実行中のアルゴリズムとは異なっている場合、リコンフィギュレーションし、しかも現在実行中のアルゴリズムの実行後に種々異なったアルゴリズムが実行される可能性があるとき、実行中のアルゴリズムの次に最大の確率で実行されるだろうというアルゴリズムに対して回路をリコンフィギュレーションするいう方法および請求項４の上位概念に記載の、この方法を実施するための装置に関する。この種のコンフィギュレーション可能な回路は、Jack Jean 外４名，Dynamic Reconfiguration to Support Concurrent Applications, PROCEEDINGS IEEE SYMPOSIUM ON FPGAS FOR CUSTOM COMUTING MACHINES, 米国，１９９８年４月，p３０２−３０３から公知である。
【０００２】
リコンフィギュレーション可能な回路は大きさ、ひいてはリソースが制限されている。２つまたは複数のアルゴリズムを同時にまたは個別の比較的大きなアルゴリズムを実行するためにこのような回路のリソースでは十分でないことがしばしばある。
【０００３】
リコンフィギュレーション可能な回路に存在しておりかつこの回路だけによって実行されるようになっているより多くのリソースを必要とする比較的大きなアルゴリズムは一般に、複数の部分アルゴリズムに分割される。部分アルゴリズムのそれぞれは、それ自体ここでも１つのアルゴリズムを表しておりかつ回路がこの部分アルゴリズムを実行するための十分なリソースを有しているように選択されている。
【０００４】
これら部分アルゴリズムは、回路において時間的に相次いで次のように実行される：これら部分アルゴリズムのそれぞれが、これら部分アルゴリズムに対してコンフィギュレーションされる回路によって実行されかつ１つの部分アルゴリズムの実行後、次にくる部分アルゴリズムが実行され、ここで回路は、この次にくる部分アルゴリズムが前者の部分アルゴリズムとは異なっている限り、前者の部分アルゴリズムの実行後に、次にくる部分アルゴリズムに対してコンフィギュレーション変換される。
【０００５】
データに依存した分岐によって、最初実行時に、すなわち比較的大きなアルゴリズムの本来の実行ないし処理の期間中に、比較的大きなアルゴリズムのこれら部分アルゴリズムのどれが実際に必要とされるかがわかる。コンパイル時、すなわち実行時間の前には、どの部分アルゴリズム、ひいては回路のコンフィギュレーションが実際に必要とされるについての示唆は存在していない。
【０００６】
比較的大きなアルゴリズムをこのためには僅かすぎるリソースを有しているリコンフィギュレーション可能な回路でも実行するための方策は次の点にある：この回路を例えば、比較的大きなアルゴリズムのすべての部分アルゴリズムに対する前以て決められているプログラムフローに相応して、順次個別にコンフィギュレーションするのである。その際、必要とされる、コンフィギュレーションされる部分アルゴリズムのみが実行される。部分アルゴリズムが必要とされなければ、この部分アルゴリズムのコンフィギュレーションはこの部分アルゴリズムの実行なしに消去される。
【０００７】
比較的大きなアルゴリズムの必要とされない部分に対する実行時間の期間中の回路のコンフィギュレーションのためには、高い実行時間が要求される。従って、実行の期間に早期に、必要なコンフィギュレーションを認識しかつロードする方法が必要とされる。
【０００８】
M. Vasilko および Djamel Ait-Boudaoud：“Architectural Synthesis Techniques for Dynamically Reconfigurable Logic”（Reiner W. Hartenstein, Manfred Glesner（Eds.）：“Field-Programmable Logic, Smart Applications, New Paradigms and Compilers”6ｔｈ International Workshop on Field-Programmable Logic and Application, FPL' 96, Darmstadt, Germany, September 23-25, 1996, Proceedings, Springer-Verlag, S290-296）から、比較的大きなアルゴリズムの個々の部分アルゴリズムを回路においてコンフィギュレーションする順序をコンパイル時に計算することが公知である。その際リコンフィギュレーションコントローラが維持され、そこでは部分アルゴリズムをコンフィギュレーションするシーケンスは固定である。その際コンフィギュレーションすべきである正しい部分アルゴリズムを突き止めるために、分岐の結果が必要とされる。
【０００９】
本発明の課題は、それぞれ個別アルゴリズムを実行するために十分なリソースを有しているリコンフィギュレーション可能な回路を用いて個別アルゴリズムを実行するための方法において、どのようにしたら実行時間を短縮することができるか、すなわち次に正しい部分アルゴリズムがくる確率が一層高められるようにする手法を示すことである。
【００１０】
この課題は、請求項１に記載の方法および請求項４に記載の装置によって解決される。
【００１２】
これによれば有利にも、所定のアルゴリズムの実行時間の期間に既に、次にくる部分アルゴリズムが回路においてコンフィギュレーションされかつ場合によっては、現在実行中のアルゴリズムの実行時間の期間に既に、次にくる部分アルゴリズム動作を開始することができる。これに対する前提条件は確かに、この形式にダイナミックにコンフィギュレーション可能である回路である。これに適しているのは、Xilinx 社の所定の製品、例えばこの形式のダイナミックなコンフィギュレーションに対する基礎となっている可能性を既に提供するモジュールＸＣ６２ｘｘである。モジュールのコンフィギュレーションはメモリの書き込みのように行うことができる。コンフィギュレーションメモリセルはアドレス指定されかつ引き続いて書き込まれる。これによりこのモジュールは実行時間の期間にコンフィギュレーションすることができる。
【００１５】
本発明の方法は、比較的大きなアルゴリズムの個々の部分アルゴリズムのコンフィギュレーションの順序がコンパイル時に計算されかつスタチックな方法である先に述べた公知の方法に比べて、所定のアルゴリズムに対して次にくる部分アルゴリズムとして実行されるべきであるアルゴリズムを一層早期に推定することができるという利点を有しており、これによりコンフィギュレーションおよび計算の間の並行性、ひいてはシステムパフォーマンスが高められ、殊に実行時間が短縮される。
【００１６】
この方法においては、回路を現在実行中のアルゴリズムの実施後に次にくるアルゴリズムに対してコンフィギュレーションすることができおよび／または回路は、現在実行中のアルゴリズムの実施の期間に次にくるアルゴリズムに対してコンフィギュレーションすることができ、すなわちダイナミックにコンフィギュレーションすることができる。
【００１７】
回路が次にくるアルゴリズムに対して現在実行中のアルゴリズムの実施後にコンフィギュレーションされるかまたは実施の期間にコンフィギュレーションされるかに無関係に、この方法自体はダイナミックな方法である。というのは、次に来るアルゴリズムは定まっておらず、確率に従って決定されるからである。
【００１９】
この方法では、少なくとも１つの所定のアルゴリズムに少なくとも２つのアルゴリズムが配属されており、これらアルゴリズムのそれぞれが、それぞれ別の所定の確率を以て、この所定のアルゴリズムの実行期間および／または実行後に次にくるアルゴリズムとして実行されるために考慮され、およびこれらの配属されているアルゴリズムのうち、例えば最大の確率を有しているものが次にくるアルゴリズムとして実際に実行される。このことは、これらの配属されているアルゴリズムのそれぞれの確率がこれらアルゴリズムすべてに対して同じであることはありえないこと、およびこれらのアルゴリズムには、それぞれ確率が違う、例えば相対的に最大の確率を有する個別のアルゴリズムがあるということを意味している。
【００２０】
種々異なっている配属されているアルゴリズムの種々異なった確率は、この方法では、付加的な情報としてわかっていなければならない。この付加的な情報がないと、それぞれ１つの所定のアルゴリズムに配属されている２つのアルゴリズムの場合、この所定のアルゴリズムの実行期間および／または実行後に次にくるアルゴリズムとして実行される確率はそれぞれ５０％であって、この情報がないと、確実な決定を下すことができない。
【００２１】
そこで付加的な情報を得るために、本願発明では次のような手続がとられる：所定のアルゴリズムに配属されておりかつ該所定のアルゴリズムの実行の期間および／または実行後に次にくるアルゴリズムとして実行されるために考慮されるそれぞれのアルゴリズムに対して、該他方の配属されているアルゴリズムのそれぞれに比較して、一方の配属されているアルゴリズムが過去において前記所定のアルゴリズムの実行の期間および／または実行後に次にくるアルゴリズムとして何回実行されたかを求め、ここで前記所属のアルゴリズムのうち、当該過去において比較的に最も頻繁に実行されたものが、前記所定のアルゴリズムの今回の実行の期間および／または実行後に次にくるアルゴリズムとして実施されるために最大の確率を有している。
【００２２】
この方法では、過去の決定から将来について補外される。所定のアルゴリズムが例えば、所定のアルゴリズムの実行の期間および／または実行後に次にくるアルゴリズムとして実行されるために考慮される２つの配属されているアルゴリズムを有しておりかつ近い過去において一方の配属されているアルゴリズムが次にくるアルゴリズムよりも頻繁に選択されたのであるならば、この配属されているアルゴリズムが比較的大きな確率を以て必要とされることから出発することができる。ここでは確率は、１つの配属されているアルゴリズムが比較的頻繁に生じることが確かであるというように考えたい。
【００２３】
この方法は有利には、所定のアルゴリズムに配属されておりかつ該所定のアルゴリズムの実行の期間および／または実行後に次にくるアルゴリズムとして実行されるために考慮されるそれぞれのアルゴリズムに対して、前記配属されているアルゴリズムが前記所定のアルゴリズムに対して次にくるアルゴリズムとしてまだ実行されていない場合には、該配属されているアルゴリズムすべてに対して同じ初期値をとる変化する数をその都度割り当て、ここで該配属されているアルゴリズムが所定のアルゴリズムに対して次にくるアルゴリズムとして実行されるとき、該配属されているアルゴリズムの数は所定の値だけ該数の極値に向かう方向において変化され、ここで極値は該配属されているアルゴリズムすべてに対して所定で同じであり、一方同時に、所定のアルゴリズムに対して次にくるアルゴリズムとして実行されないそれぞれ他方の配属されているアルゴリズムの数は所定の値だけ極値から低減する方向において変化され、前記数が最初に極値に達する配属されているアルゴリズムが、所定のアルゴリズムの現在の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００２４】
この方法を実施するための好適でかつ有利な装置では、所定のアルゴリズムに配属されておりかつ該所定のアルゴリズムの実行の期間および／または実行後に次にくるアルゴリズムとして実行されるために考慮されるそれぞれのアルゴリズムに、それぞれアップ・ダウンカウンタが配属されており、ここでそれぞれのカウンタにおいて、前記配属されているアルゴリズムが前記所定のアルゴリズムに対する次にくるアルゴリズムとしてまだ実行されていない限り、該配属されているアルゴリズムの数を表示している計数状態は該数の初期値に調整設定されており、ここで該カウンタは次のように制御されるようになっている：
カウンタの前記配属されているアルゴリズムが所定のアルゴリズムに対して次にくるアルゴリズムとして実行されるとき、該カウンタの計数状態は所定の値だけ該計数状態の極値に向かう方向において変化され、一方同時に、配属されているアルゴリズムが所定のアルゴリズムに対して次にくるアルゴリズムとして実行されないそれぞれ別のカウンタの計数状態は所定の絶対値だけ極値から低減する方向において変化され、ここで
当該カウンタが最初に極値に達する配属されているアルゴリズムが、所定のアルゴリズムの現在の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００２５】
有利にも本発明によれば、ダイナミックにコンフィギュレーション可能なシステムにおけるコンフィギュレーションの際に時間節約が可能になる。実現の際には、飛び越し予測ユニット（Branch Prediction）の場合と類似した技術を使用することができる。
【００２６】
以下の説明において本発明を各図に基づいて例として詳細に説明する。その際：
図１は、実行すべき種々異なったアルゴリズムに対して時間的に順次コンフィギュレーションすべきであるリコンフィギュレーション可能な回路を略示しており、ここで１つのアルゴリズムから矢印が示すアルゴリズムは上述のアルゴリズムの実行の間または実行後に実行されるべきものであり、かつ
図２は、次に続くアルゴリズムとして実行されるべきである最大の確率を有するアルゴリズムを求めるための装置のブロック線図を示す。
【００２７】
図１において、リコンフィギュレーション可能な回路は１によって示されている矩形のブロックによって象徴的に示されている。回路１は１つのアルゴリズムを実行するようにコンフィギュレーションされかつ別のアルゴリズムを実行するようにコンフィギュレーション変換することができる。
【００２８】
それぞれのこの種のアルゴリズムを処理するために、回路１は十分なリソースを有していなければならない。１つのアルゴリズムが比較的大きく、その結果このアルゴリズムを実行するために回路１のリソースが十分でなければ、次のように処置することができる：この比較的大きなアルゴリズムを比較的小さな部分アルゴリズムに分割して、これら部分アルゴリズムのそれぞれを実行するために回路１のリソースが十分であるようにし、かつこれら部分アルゴリズムを順次処理する。
【００２９】
例えば１つの部分アルゴリズムが処理されると、回路１におけるこの部分アルゴリズムに対するコンフィギュレーションを廃棄しかつ回路１に次の部分アルゴリズムに対するコンフィギュレーションをインプリメンテーションすることができる。この計算の中間結果を回路におけるこの回路１および／または外部メモリに保持して、これにより計算が続行されるようにすることができる。これにより、大きなアルゴリズムを比較的小さなリコンフィギュレーション可能な回路１において例えばＰＦＧＡ（Feld-Programmierbares Gate Array）の形において処理することができる。
【００３０】
比較的大きなアルゴリズムの実行時間のために、部分アルゴリズムの実行の期間に、回路１におけるこの部分アルゴリズムに対するコンフィギュレーションのもはや必要とされない部分を次の別の部分アルゴリズムに対して既にコンフィギュレーション変換し、一方この部分アルゴリズムに対するコンフィギュレーションの別の部分がこのアルゴリズムに基づいて引き続き計算するようにすれば、有利である。この並列化によって、速度面での利点が実現される。
【００３１】
大抵、比較的大きなアルゴリズムのうち、所定の部分アルゴリズムの実時点の計算の次にくる部分アルゴリズムは実時点の計算に依存している。このことは殊に、所定の部分アルゴリズムに２つの部分アルゴリズムが配属されており、これらのそれぞれが実時点の計算に依存して、次にくる部分アルゴリズムとして問題になるような場合に当てはまる。これにより、次にくる部分アルゴリズムは、漸く後で、すなわち配属されている２つの部分アルゴリズムのいずれが次にくる部分アルゴリズムとして実行されるべきであるかの条件の計算後に、突き止められることができる。
【００３２】
時間を節約するために、例えば、次のように処置することができる：所定の部分アルゴリズムに配属されておりかつそれぞれが次にくる部分アルゴリズムとして問題になる２つまたは複数の部分アルゴリズムのうち、実行すべき次にくる部分アルゴリズムとして、ランダムに１つを選択する。これが正しい次にくる部分アルゴリズムであれば、この部分アルゴリズムに対する回路１のコンフィギュレーションのための時間は低減される。誤っていれば、決定は補正されなければならない、すなわちこれまでのコンフィギュレーションは廃棄されかつ回路１の新しいコンフィギュレーションがスタートされる。次にくる部分アルゴリズムの可能性が２つである場合には、正しい部分アルゴリズムがコンフィギュレーションされるチャンスは５０％である。本発明はこの確率を一層高めるための手法を提供する。
【００３３】
図１に基づいてこのことを詳細に説明する。実行すべき種々異なったアルゴリズムに対して時間的に順次コンフィギュレーションすることができるコンフィギュレーション可能な回路であって、ここでは１つのアルゴリズムから矢印が示すアルゴリズムは前者のアルゴリズムの実行の期間または実行後に実行されるべきものであり、この回路図は、同一の回路１において、順次例えば最大５つのアルゴリズムａ，ｂ，ｃ，ｄおよびｅが実施され、回路１に対してその都度コンフィギュレーションすることができるようになっているというダイナミックなコンフィギュレーションのシーケンスプランを示している。
【００３４】
このシーケンスプランにおいて、すべての生じるアルゴリズムａないしｅがリストアップされておりかつ矢印によって、これらアルゴリズムａないしｅのいずれが直接相次いで実行されるべきであるかが分かるように示されている。
【００３５】
アルゴリズムａないしｅは、比較的大きな実行すべきアルゴリズムの部分アルゴリズムであってよい。
【００３６】
実行すべきアルゴリズムに対してコンフィギュレーションされている回路１は図１においては、各アルゴリズムを示しているアルファベットがこの回路のブロック内に収められているように図示されている。
【００３７】
５つのアルゴリズムａないしｅの処理は基本的にこれらアルゴリズムのそれぞれによって始めることができる。例えば、アルゴリズムａを以て処理が始まるものと仮定する。
【００３８】
図１によれば、このアルゴリズムａに対してコンフィギュレーションされている回路１から１つの矢印がアルゴリズムｂに対してコンフィギュレーションされている回路１を示しかつ別の矢印がアルゴリズムｃに対してコンフィギュレーションされている回路１を示している。このことは、アルゴリズムａが、これに２つのアルゴリズム、ここではアルゴリズムｂおよびｃが配属されている所定のアルゴリズムであることを意味している。この２つのアルゴリズムのそれぞれは、それぞれ別の所定の確率を以て、このアルゴリズムａの実行の期間および／またはこの実行の後次にくるアルゴリズムとして実行される対象である。
【００３９】
類似のことはアルゴリズムｄに対してコンフィギュレーションされる回路１に対して当てはまる。この回路１から１つの矢印がアルゴリズムｃに対してコンフィギュレーションされる回路１にでており、別の矢印がアルゴリズムｄ自体に対してコンフィギュレーションされる回路１にでておりかつもう１つの矢印がアルゴリズムｅに対してコンフィギュレーションされる回路１にでている。このことは、アルゴリズムｄが、これに３つのアルゴリズム、ここではアルゴリズムｃ，ｄおよびｅが配属されている所定のアルゴリズムであることを意味している。これらアルゴリズムのそれぞれは、それぞれ別の所定の確率を以て、このアルゴリズムｄの実行の期間および／またはこの実行の後次にくるアルゴリズムとして実行される対象である。
【００４０】
アルゴリズムｂに対してコンフィギュレーションされる回路１からは唯一の矢印が、アルゴリズムｅに対してコンフィギュレーションされる回路１を示している。このことは、アルゴリズムｂの実行中および／または実行後、アルゴリズムｅだけが次にくるアルゴリズムとして実行されることを意味している。同じことは、アルゴリズムｃおよびｅに対しても当てはまり、すなわちアルゴリズムｂの実行中および／または実行後、アルゴリズムｄだけが次にくるアルゴリズムとして実行されかつアルゴリズムｅの実行中および／または実行後、アルゴリズムａだけが次にくるアルゴリズムとして実行される。というのは、アルゴリズムｃからは１つの矢印だけがアルゴリズムｄを示しかつアルゴリズムｅからは１つの矢印だけがアルゴリズムａを示しているからである。
【００４１】
アルゴリズムａに対して共通に配属されている２つのアルゴリズムｂおよびｃに対して、この配属されているアルゴリズムｂまたはｃが他方の配属されているアルゴリズムｃないしｂに比較して過去においてアルゴリズムａの実行の期間および／または実行後に次にくるアルゴリズムとしてどの位の回数実行されたかが求められる。これら２つの配属されているアルゴリズムｂ，ｃのうち、過去において比較的に最も頻繁に実行されたところのアルゴリズムが、所定のアルゴリズムａの現時点の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００４２】
類似して、アルゴリズムｄに対して共通に配属されている３つのアルゴリズムｃ，ｄ，ｅに対して、この配属されているアルゴリズムｃまたはｄまたはｅがそれぞれ他方の配属されているアルゴリズムｄ，ｅないしｃ，ｅないしｃ，ｄに比較して過去においてアルゴリズムｄの実行の期間および／または実行後に次にくるアルゴリズムとしてどの位の回数実行されたかが求められる。これら3つの配属されているアルゴリズムｃ，ｄおよびｅのうち、この過去において比較的に最も頻繁に実行されたところのアルゴリズムが、所定のアルゴリズムｄの現時点の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００４３】
所定のアルゴリズムａないしｄに配属されておりかつ所定のアルゴリズムａないしｄの現時点の実行の期間および／または実行後に次にくるアルゴリズムとして実行される対象であるそれぞれのアルゴリズムｂ，ｃないしｃ，ｄ，ｅにそれぞれ、それ自体変化する数ｘが割り当てられる。この数は、これら配属されているすべてのアルゴリズムｂ，ｃないしｃ，ｄ，ｅに対して、この配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｄまたはｅが、この所定のアルゴリズムａないしｄに対して次にくるアルゴリズムとしてまだ実行されていない場合には、同じ初期値ｘ０をとる。
【００４４】
配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｄまたはｅの数ｘは、この配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｄまたはｅが所定のアルゴリズムａないしｄに対して次にくるアルゴリズムとして実行されるとき、これら配属されているすべてのアルゴリズムｂ，ｃないしｃ，ｄ，ｅに対して同じである、この数ｘの所定の極値ｘ１に向かって方向（＋）に所定の絶対値Δｘだけ変化され、一方同時に、所定のアルゴリズムａないしｄに対して次にくるアルゴリズムとして実行されないそれぞれ別の配属されているアルゴリズムｂまたはｃないしｄ，ｅまたはｃ，ｅまたはｃ，ｄが極値ｘ１から方向（−）において所定の絶対値Δｘだけ低減方向に変化される。
【００４５】
数ｘが最初に極値ｘ１に達するところの配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｅが、所定のアルゴリズムａもしくはｄの現在の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００４６】
図２には、この方法を実施するための装置が示されている。
【００４７】
この装置において、所定のアルゴリズムに配属されておりかつ、この所定のアルゴリズムの実行の期間および／または実行後に実行されるための対象になっているそれぞれのアルゴリズムに、それぞれ１つのアップ・ダウンカウンタ２１，２２，２３，２４ないし２５が配属されている。
【００４８】
カウンタ２１は、ａ→ｂによって示されているように、所定のアルゴリズムａおよび配属されているアルゴリズムｂに配属されており、カウンタ２２は、ａ→ｃによって示されているように、所定のアルゴリズムａおよび配属されているアルゴリズムｃに配属されており、カウンタ２３は、ｄ→ｃによって示されているように、別の所定のアルゴリズムｄおよび配属されているアルゴリズムｃに配属されており、カウンタ２４は、ｄ→ｄによって示されているように、別の所定のアルゴリズムｄおよび配属されている同一のアルゴリズムｄに配属されておりかつカウンタ２５は、ｄ→ｅによって示されているように、別の所定のアルゴリズムｄおよび配属されているアルゴリズムｅに配属されている。
【００４９】
それぞれのカウンタ２１，２２，２３，２４ないし２５において、配属されているアルゴリズムｂ，ｃ，ｃ，ｄ，ｅの数ｘを表している計数状態は、この配属されているアルゴリズムｂ，ｃ，ｃ，ｄ，ｅが所定のアルゴリズムａまたはｄに対する次にくるアルゴリズムとしてまだ実行されていない限りには、初期値ｘ０に調整設定されている。
【００５０】
カウンタ２１ないし２５は次のように制御される：カウンタ２１，２２，２３，２４または２５の計数状態ｘは、このカウンタ２１，２２，２３，２４または２５の所属のアルゴリズムｂ，ｃ，ｄないしｅが所定のアルゴリズムａないしｄに対して次にくるアルゴリズムとして実行されるとき、この計数状態ｘの所定の極値ｘ１に向かって方向（＋）に所定の絶対値Δｘだけ変化され、一方同時に、所属のアルゴリズムｂ，ｃ；ｃ，ｄないしｅが所定のアルゴリズムａないしｄに対して次にくるアルゴリズムとして実行されないそれぞれ別のカウンタ２２ないし２５，２１および２３ないし２５，…ないし２１ないし２４が極値ｘ１から方向−において所定の絶対値Δｘだけ低減方向に変化される。
【００５１】
カウンタが最初に極値ｘ１に達するところの配属されているアルゴリズムｂ，ｃ，ｃ，ｄ，ｅが、所定のアルゴリズムａまたはｄの現在の実行の期間および／または実行後に次にくるアルゴリズムとして実行されるための最大の確率を有している。
【００５２】
例えば、それぞれのカウンタ２１，２２，２３，２４または２５は２ビットカウンタである。これは例えば、所属のアルゴリズムｂ，ｃ，ｃ，ｄないしｅが、所定のアルゴリズムａまたはｄに対して次にくるアルゴリズムとしてまだ実行されていない限り、初期値ｘ０＝００に調整設定されている。
【００５３】
数ｘは初期値ｘ０＝００の他に、値ｘ＝０１，ｘ＝１０およびｘ＝１１をとることができ、その際ｘ＝１１＝ｘ１は、ここでは最大値である極値を形成している。
【００５４】
例えば所定のアルゴリズムａに対して、所属のアルゴリズムｂまたはｃが次にくるアルゴリズムとして選択されるときはいつでも、このアルゴリズムｂまたはｃに配属されているカウンタ２１ないし２２において計数状態ｘは絶対値Δｘ＝１だけ高められ、一方同時に、別の選択されないアルゴリズムｃないしｂに配属されているカウンタ２２ないし２１における計数状態ｘは絶対値Δｘ＝１だけ低減される。
【００５５】
所定のアルゴリズムｄに対して、所属のアルゴリズムｃまたはｄまたはｅが次にくるアルゴリズムとして選択されるときはいつでも、このアルゴリズムｃまたはｄまたはｅに配属されているカウンタ２３ないし２４ないし２５において計数状態ｘは絶対値Δｘ＝１だけ高められ、一方同時に、別の選択されないアルゴリズムｄ，ｅないしｃ，ｅないしｃ，ｄに配属されているカウンタ２４，２５ないし２３，２５ないし２３，２４における計数状態ｘはその都度絶対値Δｘ＝１だけ低減される。
【００５６】
絶対値Δｘを高めることはここではいずれの場合も、絶対値Δｘを方向＋に変化することを意味しかつ絶対値Δｘを低減することは絶対値Δｘを方向−に変化することを意味している。
【００５７】
１つのカウンタにおいて極値ｘ１に達っしておりかつこのカウンタに配属されているアルゴリズムが次にくるアルゴリズムとして更新されると、極値ｘ１は維持される。あるカウンタにおいて初期値ｘ０に達した後も類似して、この値は、該カウンタに配属されているアルゴリズムが新たに、選択されないときにも維持される。
【００５８】
所定のアルゴリズムａまたはｄに対して、この所定のアルゴリズムａまたはｂの次にくるアルゴリズムが実際に実行されることに当たり最大の確率を有している配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｅを求めるために、マスクレジスタ３を使用すると効果的である。ここにはそれぞれのカウンタ２１ないし２５にそれぞれ１つの桁が配属されておりかつここでは所定のアルゴリズムａないしｄに配属されているカウンタ２１および２２ないし２３および２４および２５に配属されているそれぞれの桁はそれぞれ値、例えば１にセットされる。この値は、これらカウンタ２１および２２ないし２３および２４および２５だけの計数状態ｘへのアクセスを可能にするものである。同時に、それぞれの別の所定のアルゴリズムｄないしａに配属されているすべての桁は別の値、例えば０にセットされる。この値は、この別の所定のアルゴリズムｄないしａに配属されているカウンタ２３および２４および２５ないし２１および２２の計数状態ｘへのアクセスを阻止するものである。
【００５９】
最大値発見器４は、マスクレジスタ３の桁が一方の値、例えば１によって占有されているすべてのカウンタ２１，２２ないし２３および２４および２５における極値ｘ１を探索する。極値ｘ１が１つの場合または極値ｘ１が同じ計数状態において複数個ある場合、最大値発見器４によって、結果レジスタ５の、当該カウンタ２１および／または２２ないし２３および／または２４および／または２５に配属されている桁において、極値ｘ１を指示する値がセットされる。この所定のアルゴリズムａないしｄに対して、配属されているアルゴリズムｂまたはｃないしｃまたはｄまたはｅが次にくるアルゴリズムとして選択される。このアルゴリズムの、結果レジスタ５における桁に、極値ｘ１を指示する値が最初に現れる。
【００６０】
図２に示されているように、極値ｘ１を指示する値は１に等しくかつ例えば結果レジスタ５の最上位の桁がこの値１によって占有されている。このことは殊に、所定のアルゴリズムａに関連して、次にくるアルゴリズムとして配属されているアルゴリズムｃではなくて、配属されているアルゴリズムｂが選択されることを意味している。
【００６１】
このようにして、確率の高い次にくるアルゴリズムを早期に既に選択することができ、しかもプログラムシーケンスにおける決定がこの時点で計算される必要はない。誤った次にくるアルゴリズムが選択されたとすれば、プログラムシーケンスにおける決定後直ちに、コンフィギュレーション過程は中断されかつ別のおよび正しい次にくるアルゴリズムがロードされる。
【図面の簡単な説明】
【図１】  実行すべき種々異なったアルゴリズムに対して時間的に順次コンフィギュレーションすべきであるリコンフィギュレーション可能な回路のシーケンス図である。
【図２】  次に続くアルゴリズムとして実行されるべきである最大の確率を有するアルゴリズムを求めるための装置のブロック線図である。
【図１】
0003668425.tif 000002
【図２】
0003668425.tif 000003