(57)【要約】コンピュータ装置は、入力側で第１のクロスバースイッチングユニット（１）が前置されるとともに第２のクロスバースイッチングユニット（３）が後置された構造化可能なＲＡＭユニット（２）を備えたＲＡＭベースの主要部分（Ｈｔ）を含む。第１のクロスバースイッチングユニット（１）からアドレス信号（１８、１３）がＲＡＭユニット（２）ないし第２のクロスバースイッチングユニット（３）に供給され、出力側の信号（１０）から第１のクロスバースイッチングユニット（１）へフィードバックされ、さらに出力される。特に主要部分（Ｈｔ）のコンフィギュアラブルな進行制御のための追加の制御部分（Ｓｔ）は、第１及び第２のクロスバースイッチングユニット（１ないし３）に対するカウンタ状態信号（１２）を生成するために、第１のクロスバースイッチングユニット（１）と一緒に刻時されるカウンタユニット（４）を含む。このコンピュータ装置は、特にグローバルセルオートマトン（ＧＣＡ）を組み込むのに適している。
2008513864.tif 000002
【特許請求の範囲】
【請求項１】
リコンフィギュアラブルなアーキテクチャを備えるコンピュータ装置であって、
複数のＲＡＭセル（２２１）を有する構造化可能なＲＡＭユニット（２）と、
入力部に前記アーキテクチャの入力データ（９）が外部から与えられ、出力部が第１のバス回線システム（２０）を介してＲＡＭユニット（２）の入力部と組み合わされた第１のクロスバースイッチングユニット（１）と、
入力部が第２のバス回線システム（２１）を介してＲＡＭユニット（２）の出力部と組み合わされ、出力部が、第１のクロスバースイッチングユニット（１）の入力部で第２のクロスバースイッチングユニット（３）の出力側データをフィードバックするために、第３のバス回線システム（１０）を介して第１のクロスバースイッチングユニット（１）の入力部と組み合わされた第２のクロスバースイッチングユニット（３）と、
を備えたＲＡＭベースの主要部分（Ｈｔ）を含み、
その際、アドレス指定のためにＲＡＭユニット（２）及び第２のクロスバースイッチングユニット（３）には第１のクロスバースイッチングユニット（１）により生成されるアドレス信号（１８ないし１３）が供給され、
第２のクロスバースイッチングユニット（３）の出力側データは、場合によりさらに処理された後、前記アーキテクチャの出力データ（１７）を出すために出力ネットワーク（８）へも供給され、
ならびに前記コンピュータ装置は、
カウンタユニット（４）を備える、主要部分（Ｈｔ）を進行制御するための追加の制御部分（Ｓｔ）の手段を含み、カウンタユニット（４）と第１のクロスバースイッチングユニット（１）には共通のクロック信号（１４）が供給され、第１及び第２のクロスバースイッチングユニット（１ないし３）にはカウンタユニット（４）により生成されるカウンタ状態信号（１２）が供給されるコンピュータ装置。
【請求項２】
第２のクロスバースイッチングユニット（３）の出力側データはまずプログラマブルな不一致論理ユニット（６）に供給されることを特徴とする、請求項１に記載のコンピュータ装置。
【請求項３】
第２のクロスバースイッチングユニット（３）の出力側のデータは、出力部が前記アーキテクチャの出力データ（１７）を出すための出力ネットワーク（８）と組み合わされた、後置されたレジスタユニット（７）へ供給されることを特徴とする、請求項１または２に記載のコンピュータ装置。
【請求項４】
カウンタユニット（４）には、共通のクロック信号（１４）が供給されるコンフィギュアラブルな比較ユニット（５）が付属しており、レジスタユニット（７）には、不一致論理ユニット（６）からのデータの受け取りを制御する比較ユニット（５）のクロック信号（１５）が供給され、カウンタユニット（４）には比較ユニット（５）のリセット信号（１６）が供給されることを特徴とする、請求項２及び３に記載のコンピュータ装置。
【請求項５】
第１のクロスバースイッチングユニット（１）にはレジスタユニット（７）の状態信号（１１）が供給されることを特徴とする、請求項３または４に記載のコンピュータ装置。
【請求項６】
ＲＡＭユニット（２）は、ＯＲ／ＭＵＸ切換ユニット（３００）と組み合わされたＲＡＭセル（２２１）を有するＲＡＭベース領域（２２０）を含むことを特徴とする、請求項１から５のいずれか一項に記載のコンピュータ装置。
【請求項７】
ＯＲ／ＭＵＸ切換ユニット（３００）には第１のクロスバースイッチング装置（１）からアドレス信号（１８）が供給されることを特徴とする、請求項６に記載のコンピュータ装置。
【請求項８】
第１のクロスバースイッチング装置（１）からのアドレス信号（１３）によってＲＡＭベース領域（２２０）の統合が行われることを特徴とする、請求項６または７に記載のコンピュータ装置。
【請求項９】
追加の記憶デバイスとしてＣＡＭｓが設けられていることを特徴とする、請求項１から８のいずれか一項に記載のコンピュータ装置。
【請求項１０】
少なくとも１つのＣＧＡが組み込まれていることを特徴とする、請求項１から９のいずれか一項に記載のコンピュータ装置。
【請求項１１】
記憶素子として特にＴＭＲ型式の磁気抵抗デバイスが設けられていることを特徴とする、請求項１から１０のいずれか一項に記載のコンピュータ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
１）序論
本発明は、特に、少なくとも１つのクロスバースイッチングユニットを含む、バス回線システムを備えるＲＡＭベースの主要部分と、進行制御をするための手段とを含む、アルゴリズムを並行して計算するためのリコンフィギュアラブルなアーキテクチャをもつコンピュータ装置に関する。
【背景技術】
【０００２】
２）従来技術（図１から図４を参照）
２．１  公知のコンピュータモデル
コンピュータの構成及び構造／アーキテクチャについては、例えば参考文献［７］に記載されている（同書の特に１７４頁から１８１頁、２２９から２４８頁、３７６頁から３８４頁、４００頁及び４０１頁を参照）。
【０００３】
一般に、図１の原理図から明らかないわゆる「フォンノイマンアーキテクチャ」は、万能コンピュータ装置であるとみなされる。この用語は、コンピュータによって、コンポーネント中央演算処理装置［ＣＰＵ、この内部にコントロールユニット（ＣＵ）及び算術論理ユニット（ＡＬＵ）が含まれる］と、メモリ（記憶装置）と、インプット／アウトプット（入出力部）と、バスシステムとを備えるアーキテクチャに基づき、アルゴリズム化が可能なあらゆる問題を原理的に計算可能であることを意味している。それぞれの問題に合わせたこのようなコンピュータの調整はプログラムによって行われ、すなわち、例えばプログラム言語Ｃ、Ｃ＋＋またはＪａｖａ（登録商標）等でのアルゴリズムのテキスト記述によって行われる。このプログラムは、それ自体が１つのプログラムである翻訳機能（コンパイラ）によって、機械が読むことのできるプログラムへ翻訳される。
【０００４】
プログラム処理は、図１に示すフォンノイマンアーキテクチャやこれに類似するアーキテクチャ（例えばハーバードアーキテクチャや改良型ハーバードアーキテクチャ）に基づくコンピュータでは、原則としてシーケンシャルな方法により行われる。このことは、大量の機械語命令で構成されるアルゴリズムが、第１の命令が既知であることによって処理されるという具合に理解される。１つの命令の後に続く命令は記憶装置の次のアドレスにある命令（標準のプログラムフロー）であるか、または、直近に実行された命令が、最新のプログラム状態を他の場所へ移す飛越し命令であったかのいずれかである。最新のプログラム状態を記憶する内部レジスタは、「プログラムカウンタ」（ＰＣ）と呼ばれる。
【０００５】
シーケンシャル処理のこのような原理は、１つの時点でちょうど１つの命令が処理中であることを意味している。これは「フォンノイマン原理」と呼ばれる。ＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ−Ｓｅｔ  Ｃｏｍｐｕｔｉｎｇ）、スーパースケーラ、またはＶＬＩＷ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ）などと呼ばれる現代のアーキテクチャは、１つの時点で１つを超える命令を実行するが、それでも順次性の原則は保たれている。全体として、このような実行原理を総称して「タイムシーケンシャル」（Ｃｏｍｐｕｔｉｎｇ  ｉｎ  Ｔｉｍｅ）と呼び、これはアルゴリズムが時間を必要とすることを示唆している。
【０００６】
プログラム処理のまったく別の原理が、プログラマブルロジックデバイス［ＰＬＤｓ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅｓ）、図２に対応］、ないしそのもっともよく知られた具体化であるＦＰＧＡｓ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙｓ）で意図されている。これらのアーキテクチャも万能型であり、すなわち、アルゴリズム化が可能なあらゆる問題に利用することができる。この場合のプログラミングは、多くの場合ビットレベルで定義され、したがって論理要素と呼ばれる基本的な計算単位が、１つのネットワークでつながれるという形で行われる。このようなプログラミングの形態は、多くの場合、「コンフィギュレーション」と呼ばれる。
【０００７】
ＰＬＤにおけるプログラム処理は、フォンノイマン原理とは異なり、最大の並行性をもって行われる。１つのデバイスのコンフィギュレーション全体を、１回のサイクルで完全に処理される単一の命令として把握することができる（フォンノイマン原理とは異なる。ただし、一定不変に定義されるのではなく、組み合わされたものとして把握される）。その場合、しばしば外部クロックパルスと関連づけられるサイクル時間は、組合せの複雑性に依存して決まることになる。そのために、プロセッサに比べて低いクロックレートが利用されるが、これは実行の並行性で補って余りあるものである。このような実行の原理は「空間コンピューティング（Ｃｏｍｐｕｔｉｎｇ  ｉｎ  Ｓｐａｃｅ）」と呼ばれる。
【０００８】
２．２  決定性有限オートマトン
問題をアルゴリズム化するための１つの重要なモデルが決定性有限オートトマトン［ＤＥＡｓあるいはＤＦＡｓ（ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｆｉｎｉｔｅ  ａｕｔｏｍａｔａ）］である。これは工学分野では「有限状態機械」（図３の原理図に示すＦＳＭｓ）とも呼ばれている。このモデルは問題を複数の状態のシーケンスとみなしており、これらの状態の間には、入力値に応じて定義された過渡関数がある（次状態デコーダ）。ＤＥＡのモデルは理論上はフォンノイマンモデルほど強力ではないものの、実際問題としては、場合によりモデルを追加して任意の問題を解くことができる。
【０００９】
このＤＥＡｓの最大の問題は、状態の数とともに関数が指数的に増加するという点にあり、これは半導体材料（特にシリコン）の所要スペースに関わる問題である。この理由から、相互に通信をする多数のオートマトンからなるモデルが好んで選択される。この種のコンピュータモデルは「複雑な協調的オートマトン」と呼ばれる。
【００１０】
２．３  ブール関数の説明
ブール関数またはスイッチング関数は写像ｆ：Ｂm→Ｂnであり、このときＢ＝｛０、１｝であり、これはｆ＝（ｆ1、ｆ2、．．．ｆn）という形態で表すことができ、すなわち、関数ｆk：Ｂm→Ｂのベクトルとして表すことができる。そこで以下においては、初期値をもつ関数ｆkだけについて考える。これは一般にｆとして表される。
【００１１】
さらに、ｆは論理和または論理積の標準形の形態で表せることが知られている。このことは、論理和標準形については、
ｆ＝ｚ１＋ｚ２．．．＋ｚｋ、このときｋ＝１、２、．．．２ｍ、かつ「＋」はＯＲ演算子（論理ＯＲ）（１）
及び、
ｚｉ＝ｙ１*ｙ２*．．．ｙｎ、このときｉ＝１、２、．．．、ｋ、このとき「*」はＡＮＤ演算子（論理ＡＮＤ）（２）
が成り立つことを意味している。当然ながら、記述されるべき関数が値「真」または「１」を得るようなｚｉだけが使用される。このとき記号ｙｊは、入力ベクトルｘ＝（ｉ1、ｉ2、．．．ｉk）がどのように入力ビットｉkになるかを規定する。入力ビットについては、集合｛０、１｝に含まれる値しか許容されていないのに対して、このことはｙｊについては変更されなければならず、すなわち、これらの値には３つの属性｛０、１、−｝のうちのいずれかが割り当てられる。このとき属性「１」は、ｙｊについてｉkが改変されることなく採用されることを意味しており、「０」は、ｉkを反転して選択しなければならないことを意味しており（／ｉkと表記）、「−」はドントケア（Don't care）を意味しており、すなわちｉkは使用されない。ｙｊについて値｛０、１｝だけが属性として使用される場合、これを「標準論理和標準形」と呼ぶ。
【００１２】
このような表記方法が重要である理由は、入力ビットの順序が既知である場合、それによって、前述の式（２）に掲げる「項（Ｔｅｒｍｅ）」とも呼ばれるサブストリング表記ｚｉを、いわば「ストリングターム」として表すことができるからである。すなわち、ｉ１、ｉ２、ｉ３の順序の場合、「１１１」はｚ１＝ｉ１*ｉ２*ｉ３であることを意味しており、「０−１」はｚ２＝／ｉ１*ｉ３を表しており、以下同様である。
【００１３】
３つの入力ビットの場合、考えられる全ての入力ベクトルの集合はｖ＝｛０００、００１、０１０、０１１、１００、１０１、１１０、１１１｝である。例えば関数ｆが入力ベクトル｛００１、０１１、１１１｝でのみ値「真」を得るときは、これらの入力ベクトルしか指定する必要がなく、またそれしか許されない。これは、ストリングタームの形態では１１１及び０−１により行うことができ、これは与えられた関数を完全に特徴づけており、次の論理和標準形と同形である。
ｆ＝／ｉ１*ｉ３＋ｉ１*ｉ２*ｉ３
【００１４】
２．４  連想メモリ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）（ＣＡＭ）
読出し／書込み用の記憶デバイス［ＲＡＭ（Ｒａｎｄｏｍ  Ａｄｄｒｅｓｓａｂｌｅ  Ｒｅａｄ／Ｗｒｉｔｅ  Ｍｅｍｏｒｙ）］は、通常、データやプログラムを記憶するのに用いられる。この場合、アドレスはアドレスバスに印加され、デバイス固有の待機時間の経過後に、読取プロセスの場合には記憶されているデータがデータバスに印加され、さらに利用することができる。書込プロセスもこれに準ずるやり方で進行する。
【００１５】
データを得ようとするエンティティ（例えばプロセッサ）の視点からはアドレスが既知であり、記憶されている内容は事前には未知である。しかしながら、その関係が正反対である用途も存在する。すなわち、記憶されている内容が既知であり、その内容がどのアドレスに保存されているかが関心の対象になり、この場合には答えが「存在しない」という場合もあり得る。このような種類の照会をサポートする記憶デバイスは、「連想メモリ（Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）（ＣＡＭｓ）（内容によってアドレス指定ができる記憶デバイス）」と呼ばれる。
【００１６】
ＣＡＭと呼ばれ、上記のような挙動を直接サポートする記憶デバイスは、特別なデバイスであり、決して頻繁に見られるものではない。しかし実際上の用途では、ＣＡＭの機能性を通常のＲＡＭデバイスでエミュレートすることができる。ただしそのためには、ＣＡＭに直接保存されることになるはずのデータ全てについて照会時に数値ではなく記憶アドレスが現れ、これに対応するアドレスが事前に算出されて、そのデータに呼応するＲＡＭアドレスに保存されなくてはならない。
【００１７】
２．５  セルオートマトン
セルオートマトン［ＣＡｓ（Ｃｅｌｌｕｌａｒ  Ａｕｔｏｍａｔａ）］は有限オートマトンの集合であり、１つのフィールドに所定のトポロジーで配置されるとともに、さらにそれ以外の特性も有する（参考文献［１］及び［４］参照）。このようなＦＳＭｓの集合はｎ次元アレイ（多くの場合ｎ＝２が成り立つ）として配置され、各々の場所に定まった座標が与えられる。各々のＦＳＭは一義的に隣接項を有し、これらの隣接項と通信することができる。ｎ＝２の場合、多くのケースでは周囲にある４個のＦＳＭｓ（Ｎ、Ｅ、Ｗ、Ｓの各方位。したがって「ＮＥＷＳ」とも呼ばれる）が隣接項であるとみなされる。
【００１８】
隣接項との通信は、直接の隣接項の状態を読取可能、かつそれによって評価可能であるように行われる。各々の時間ステップで、全てのセルの状態が並行して計算される。新たな状態を計算するために、さらに遠く離れたセルのデータを利用したいときは、そのデータをセルからセルへ段階的に運んでいかなくてはならない。そのため、古典的なセルオートマトンは、データの局在性が高い問題設定を計算するのに良く適している。
【００１９】
ＣＡｓは、上に検討したそれぞれのアーキテクチャと同様に万能コンピュータであるとみなされ、そのうえ、完全に並行して作業を行う。ＣＡｓのネットワークがハードウェア回路に、例えばＡＳＩＣやＰＬＤにマッピングされると、接続の数はオートマトンの数に伴って線形に増加する。接続自体は、選択されるトポロジーに応じて比較的短く、かつ固定的に敷設される。すなわち、ＣＡｓ相互の通信に要するコストは比較的小さい。このスイッチング関数をＲＡＭにマッピングするのに必要なメモリ使用量を、スイッチング関数の複雑性であるとみなすと、１つのセルの挙動に呼応するスイッチング関数の最大の複雑性は、入力変数の数に伴って指数的に増加するとともに、関数の出力変数の数に伴って線形に増加する。入力変数の数は、ここでは、セルと接続された全てのＣＡｓの状態を、そのセル自体の状態を含めてコーディングするのに必要な全てのビットの合計である。したがってセルの最大の複雑性は、実質的に、各オートマトンの接続の数によって制約される。
【００２０】
グローバルセルオートマトン（ＧＣＡｓ（Ｇｌｏｂａｌ  Ｃｅｌｌｕｌａｒ  Ａｕｔｏｍａｔａ））というコンセプトは、全てのセルの接続がそれぞれ最寄の隣接項とだけでなく、フィールド全体の任意のセルとの間で可能であることによって、ＣＡｓの制約を克服する。それにより、ＧＣＡが規定されたトポロジーを有するのではなく、問題設定に適合化された、場合により計算の継続時間中に変化するトポロジーを利用することさえ可能にするものである。このことは、プログラム処理の大幅な加速化につなげることができる。個々のオートマトンの接続の数は、場合により上限によって規定されている。ただ１つの接続しか許されない場合、これをシングルアームＧＣＡｓと呼び、一般な場合にはｋアームＧＣＡｓと呼ぶ。
【００２１】
その帰結として、ＧＣＡｓの１つのフィールドが具体化される場合、セル相互の通信のための所要コストはセルの数に伴って著しく増加する。個々のオートマトンの間の考えられる接続の数は、その数の２乗のペースで増加していく。
【００２２】
個々のオートマトン自体の複雑性、ないしその根底にあるスイッチング関数の複雑性は、従来型のＣＡｓの場合と同じく、実質的に、それぞれ個々のセルの接続の数に依存して決まる。ＧＣＡがリコンフィギュアラブルな回路（ＰＬＤ）にマッピングされる場合、任意のスイッチング関数を具体化することができるそれぞれ個々のセルは、最大限可能な複雑性を可能にしなければならない。
【００２３】
個々のオートマトンが、ローカルメモリを備えるそれぞれ１つの計算装置にマッピングされると、各々のセルは複雑なスイッチング関数をも具体化することができる。全てのセルの任意の通信に要するコストは、セルの数の２乗のペースで増加する。その場合、回路の細分性は、セルの数ないし各セルの間の接続のビット幅によって規定される。このような回路は、ＦＳＭｓの数及びビット幅に関して回路の設定事項に呼応するＧＣＡｓを、非常にうまく具体化することができる。それぞれ個々のセルで、複雑なスイッチング関数をも具体化することができる。しかしながら、個数や接続の所要ビット幅に関して所定の細分性と一致していないＧＣＡｓは、回路にマッピングするのが困難であることが欠点となる。
【００２４】
個々のセルが組合せ回路として製作される場合、各々のセルは、他の全てのセルのデータを、自分自身の状態も含めて処理できなくてはならない。この理由から、各々の組合せ回路は、全てのセルの２進コード化された全ての状態を入力変数として含むことができるスイッチング関数を具体化することができなくてはならない。スイッチング関数の出力変数の数は、個々のセルの全ての状態を２進コード化することを可能にするだけでよい。この場合の欠点は、スイッチング関数の複雑性が、入力変数の数に伴って指数的に増加することである。セル相互の通信に要するコストが多項式で増加することも、同様に欠点となる。
【００２５】
このように、ＧＣＡを組み込むために適した（リ）コンフィギュアラブルなアーキテクチャ（ＰＬＤ）は、ＦＳＭごとに任意の複雑性を組み込むことができなくてはならない。このことは、ＦＳＭｓをＰＬＤｓのセルへ直接マッピングしようとする場合、セルがそれぞれ任意の関数を組み込まなければならないことを意味している。それに基づいて、セルサイズの指数的な増大が起こることが知られている。さらに、ＰＬＤにおけるコンフィギュアラブルなネットワークは完全に製作されていなくてはならず、すなわち、各々のセル出力部がそれぞれ他のセルと接続可能でなくてはならない。それに伴ってネットワークは２乗のペースで増加していき、ネットワークのコンフィギュレーションも同様である。
【００２６】
現時点で、これら両方の要求を満たすＰＬＤアーキテクチャは知られていない。すなわち、完全なデザイン空間を含む大型セルは存在しておらず、完全なデザイン空間を含む小型セルしか存在しておらず［いわゆる「ルックアップテーブルストラクチャー」（ＬＵＴ）］、あるいは、任意の関数をマッピングするための不完全な手段を備える大型セルしか存在していない。全てのセルの完全な接続可能性は、大型セルでしか可能でない。したがって、既存のＰＬＤｓへのＧＣＡｓのマッピングは困難であり、多くの場合不可能でさえある。
【００２７】
前述した問題点を回避するために、「任意のアルゴリズムを並行して計算するためのリコンフィギュアラブルなアーキテクチャ」を発明の名称とする未公開の２００４年２月１３日付け独国特許出願第１０２００４００７２３２．９号明細書により、少なくともただ１つのコンフィギュアラブルな組合せ回路及び／またはリコンフィギュアラブルな組合せ回路を有し、その時点ｔn-1における出力変数は時点ｔnにおける組合せ回路の入力変数を形成し、時点ｔn-1と時点ｔnの間で組合せ回路網の出力変数を記憶するための手段を備える、コンピュータ装置のアーキテクチャが提案されている。
【００２８】
このとき時点ｔn-1及びｔnは、スイッチング関数の直接連続する評価を表している。技術的に好都合な具体化形態では、これらの時点はクロックパルス時間Ｔで印加されるクロックパルスから導き出すことができ、それにより、ｔn−ｔn-1＝ｋ・Ｔ（このときｋ＝１、２、３、．．．）が成り立つ。このとき所与の用途についてｋは一定であり、異なる用途については別様に選択することができる。
【００２９】
スイッチング関数の複雑性は入力変数の数に伴って指数的に増加し、かつ、出力変数の数ないしマッピングされるべきＧＣＡｓのフィールドにあるセルの数に伴って線形に増加し、ＧＣＡｓ相互の通信に要するコストはセルの数に伴って少なくとも２乗のペースで増加することは確かなので、上記で提案される（リ）コンフィギュアラブルなアーキテクチャはＧＣＡｓを組み込むのに適している。そのために該アーキテクチャは、少なくともただ１つのコンフィギュアラブルな組合せ回路で成り立っており、その時点ｔn-1における出力変数は時点ｔnにおける組合せ回路の入力変数を形成する。時点ｔn-1と時点ｔnの間では、この組合せ回路網の出力が特にレジスタ等の記憶装置に記憶され、それによって逐次論理システムないしＦＳＭが成立する。
【００３０】
すでに提案されているアーキテクチャは、さらに次のように構成されてもよい。
記憶手段としてレジスタ記憶装置が設けられてもよい。
特に、組合せ回路は３段階で構成されている。
このとき、
第１の段階は、入力回線を介してアドレス指定可能な、並列につながれた複数の記憶デバイスを含んでもよく、各々の記憶デバイスに、求められた帰属の主項のなかで結び合わされた入力変数の部分集合が供給されており、
第１の段階には、個々の主項の識別表示によってアドレス指定される記憶デバイスを備える第２の段階が後置されており、
第２の段階には、第２の段階の記憶デバイスに由来する個々の主項の出力値を論理和演算するための手段を備える第３の段階が後置されてもよい。
このとき、個々の主項は最小化法によって求めることができる。
さらに、第１の段階は少なくとも１つのクロスバースイッチングユニットを介して、いわゆるクロスバースイッチを介して、第２の段階と相互に組み合わされてもよい。
記憶デバイスとしてはＣＡＭｓ及び／またはＲＡＭｓが設けられてもよい。
少なくとも１つのＣＧＡが統合されていると特に好ましい。
記憶素子として、特にＴＭＲ型の磁気抵抗デバイスが設けられてもよい。このようなトンネル磁気抵抗素子は、それ自体公知である。
【００３１】
すでに提案されているアーキテクチャの上に挙げた詳細な構成には、特に、次に説明するような考察が根底にある。
【００３２】
選択された組合せ回路におけるスイッチング関数の複雑性は、出力変数の数に伴って線形に増加していくものの、セル相互の通信に要するコストは全て不要になる。このようなスイッチング関数に、少数の出力変数をもつ多数の個々のオートマトンをマッピングすることができ、または、多数の出力変数をもつ少数のＧＣＡｓ、あるいは種々のセルの混合をマッピングすることができる。それにより、細分性が規定されることがなく、ＦＳＭｓ相互の通信は原理的に完全に可能である。しかしながら、組合せ回路を組み込むことができるスイッチング関数の最大の複雑性によって、限界が生じる。
【００３３】
多数の入力部を備える組合せ回路（これは一般的なケースでは、複数のＦＳＭｓを含むＧＣＡがマッピングされる場合に生じる）を利用することは、入力部の数に対する、所要スペースの一種の指数的な依存性が同じく生じる可能性があることを意味している。上限とみなされるのは、各状態が１つのビットにコード化される場合、ｅｘｐ（状態の数）に伴うスペースの増大であり、一般的なケースにおいては所要スペースはもっと少なくなる。しかし、万能回路は最大のケースを含んでいなくてはならないので、指数的な増加の法則が適用されることになる。
【００３４】
このとき、組合せ回路を組み込む回路を３つの特別な区域／段階に分類するのが特に好ましいと考えられる。そのために、多数の入力変数と多数の出力変数をもつスイッチング関数を組合せ回路として具体化することができる、（リ）コンフィギュアラブルな回路が記載されている。
【００３５】
スイッチング関数のためのリコンフィギュアラブルな組合せ回路を設計するために前提となる考察として、次の２通りの可能性に着目する。
【００３６】
第１に、スイッチング関数全体をＲＡＭメモリにファイルすることが可能である。スイッチング関数の入力変数はアドレスビットを形成し、入力変数の各々の可能な組合せについてメモリセルをアドレス指定する。そうすれば、このメモリセルの内容はスイッチング関数の値に呼応し、記憶デバイスのデータ回線が関数の出力変数を形成する。このようなコンセプトの利点は、回路の単純な構造、簡単なリコンフィギュア可能性、記憶デバイスの高い集積度、及び、スイッチング関数の評価に必要な時間が一定なことである。ただし必要なメモリセルの数、すなわち必要な記憶デバイスのサイズは、入力変数の数に伴って指数的に増加する。この理由から、このやり方では小規模なスイッチング関数しかマッピングすることができない。
【００３７】
以上がＰＬＤｓにおける従来技術であり、ＦＰＧＡｓで多くの場合４つの２進値の入力変数と１つの２進値の出力とを含むルックアップテーブル構造として利用されている。
【００３８】
スイッチング関数を組合せ回路にマッピングする２番目の可能性は、２段階またはそれ以上の段階の回路にゲートをコンフィギュアラブルに配置することにある。それにより、最小のゲート消費量で、スイッチング関数を組合せ回路へマッピングすることが可能となる。このとき回路理論により、例えばリードマラー標準形あるいは高性能アルゴリズムといったスイッチング関数の好都合な表現形式が、論理最小化のために提供される。このような取組の利点は、ゲートの消費量が最低限になることであり、及び、高性能な方法とアルゴリズムを最小化のために利用できることである（参考文献［２］及び［３］参照）。この方法は、定まったスイッチング関数を表現するために、例えばＲＯＭｓを具体化するために、うまく利用することができる。例えばクロスバースイッチのようなハードウェアデバイスを介して、個々のゲートをリコンフィギュアラブルに配線することができるが、このとき、リコンフィギュア可能性のために要するコストは、スイッチング関数の入力変数の数に伴って指数的に増加する。
【００３９】
すでに提案されているアーキテクチャは、図４に示すように、その具体的な実施形態では、第２のＲＡＭ段階と呼ばれる複数のＲＡＭセルを有する、構造化されたＲＡＭユニットを備えたＲＡＭベースの主要部分を含み、該ＲＡＭユニットは、バス回線システムを介して、クロスバースイッチングユニット（クロスバースイッチ）の出力部とアドレス指定可能なように組み合わされている。その入力部に第１のＲＡＭ段階のデータが与えられる。論理ブロックを備える第２のＲＡＭ段階には、いわゆるＸＯＲ素子の形態の不一致論理素子が後置されており、そのデータは、さらに別のクロスバースイッチングユニットと組み合わされたレジスタユニットに供給される。このユニットを介して、一方では、外部から供給される入力データが第１のＲＡＭ段階に供給され、また他方では、再処理のための出力データが出される。このような種類のアーキテクチャでは、記憶エリアはアプリオリに分割されている。
【発明の開示】
【発明が解決しようとする課題】
【００４０】
３）課題設定
本発明の課題は、それぞれのアプリケーションの要請にいっそう適合化しながら、それぞれの記憶エリアを考慮したうえで、すなわち優れたスペース利用度で、迅速な計算が可能となるように、すでに提案されているコンピュータアーキテクチャを構成することである。
【課題を解決するための手段】
【００４１】
４）解決の取組
上述の課題は、本発明によれば、特許請求の範囲に記載された措置によって解決される。それによれば、リコンフィギュアラブルなアーキテクチャを備えるコンピュータ装置は次の各部分を含み、すなわち、
複数のＲＡＭセルを有する構造化可能なＲＡＭユニットと、
入力部にアーキテクチャの入力データが外部から与えられ、出力部が第１のバス回線システムを介してＲＡＭユニットの入力部と組み合わされた第１のクロスバースイッチングユニットと、
入力部が第２のバス回線システムを介してＲＡＭユニットの出力部と組み合わされ、出力部が、第１のクロスバースイッチングユニットの入力部で第２のクロスバースイッチングユニットの出力側データをフィードバックするために、第３のバス回線システムを介して第１のクロスバースイッチングユニットの入力部と組み合わされた第２のクロスバースイッチングユニットと、
を備えたＲＡＭベースの主要部分を含み、
アドレス指定のためにＲＡＭユニット及び第２のクロスバースイッチングユニットには第１のクロスバースイッチングユニットにより生成されるアドレス信号が供給され、
第２のクロスバースイッチングユニットの出力側データは、場合によりさらに処理された後、アーキテクチャの出力データを出すために出力ネットワークへ供給され、
ならびに前記コンピュータ装置は、
カウンタユニットを備える、主要部分を進行制御するための追加の制御部分の手段を含み、カウンタユニットと第１のクロスバースイッチングユニットには共通のクロック信号が供給され、第１及び第２のクロスバースイッチングユニットにはカウンタユニットにより生成されるカウンタ状態信号が供給される。
本明細書で使用している「コンフィギュアラブル」という用語は、「該当するコンピュータ部分の以後の挙動に影響を与える、特に動作のために利用される構造の特徴的な量の指定及び／または調整可能性」という意味で理解すべきである。「プログラマブル」とは、「該当するコンピュータ部分がそれに基づいて作動している現在のプログラム状態またはプログラム進行を変更する可能性」という意味に解される。
【００４２】
計算装置の本発明の構成と結びついた利点は、特に、可能なアプリケーションへの適合化という面で、すでに提案されている装置に比べて高いフレキシビリティを実現できるという点に見ることができ、記憶エリアのアプリオリに定まった分割は行われない。本発明によるアーキテクチャは、グローバルセルオートマトン及びこれに類似するコンピュータアーキテクチャを組み込むのに適している。このアーキテクチャでは、新たな状態の計算のために比較的短い時間しか必要なく、そのためにはランの回数を計算するだけでよい。このときアーキテクチャは、個々の計算ステップへの記憶装置の分割に関してフレキシブルであり、それと同時に、ランの回数の可変性を許容する。このような形態のコンピュータアーキテクチャは、特に、内蔵されたアプリケーションでの、例えば自動車分野での、非常にタイムクリティカルな計算や、通信工学、及び、特に制御が周期的な挙動である場合における自動化工学に適している。
【００４３】
すなわち、このようなコンピュータ装置の基本構造では、出力信号は、第２のクロスバースイッチングユニットから出ていき第３のバス回線システムを介して送られる出力側データの一部としてそのまま現れる。このことは、出力側データの記憶とそれ以後の処理が必ずしも必要ではないことを意味している。ただしこの場合、ランの回数は事前に規定される。
【００４４】
本発明によるコンピュータ装置では、ＲＡＭユニットは、入力データのリコンフィギュアラブルなブール関数が出力部で具体化されるように利用される。このことは、入力部がＲＡＭユニットのアドレスバスになり、出力部がＲＡＭユニットのデータバスになることを意味している。それにより、ＲＡＭユニットは作動時にＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）として作動し、（リ）コンフィギュレーションの間だけＲＡＭｓに書込みが行われる。
【００４５】
このような観点からすると、ＲＡＭユニットは小規模なＬＴＵ（ルックアップテーブル）構造のシーケンスとして作動しており、ＬＴＵのサイズと数を調整可能である。
【００４６】
第１及び第２のクロスバースイッチングユニットに供給されるカウンタ状態信号は、前述したシーケンスのどの点で計算が行われるかを表している。このとき計算の形式は、１回のサイクルごとにＲＡＭユニットの一部が利用され、１回の完全な計算のためにこのような複数回のサイクルが必要であるように構成される。各々のサイクルはカウンタユニットによって識別表示され、クロスバースイッチングユニットは各々のサイクルで固有の値にリコンフィギュレーションされて、シーケンスを可能にする。それと同時にカウンタユニットは、比較ユニットとともに、シーケンスがいつ終了するかを規定する。
【００４７】
このように本発明の措置によって、非常に迅速な計算と、できる限り優れたスペース活用度とを組み合わせた万能計算機が可能になるという利点がある。この措置の基礎となる役目を果たすのは、周知のとおり万能型であるＧＣＡ（グローバルセルオートマトン）モデルである。このモデルは、比較的簡単にただ１つのＬＵＴへ具体化することができ、ＧＣＡでは通信がグローバルであり、ないしはグローバルであり得るという理由から好ましい。他ならぬこのような通信のために、従来技術の場合、ＧＣＡを周知のＰＬＤへ具体化することが大きな問題となっているのである。
【００４８】
さらに従来技術では、非常に大型のＬＴＵは、アドレス回線の形態の入力部に伴ってスペース所要量が指数的に増えるという問題を示している。そのため、ＬＴＵサイズは最大５つの入力部に制限されるのが普通である。
【００４９】
しかし本発明は、ＧＣＡ及びこれに伴う万能コンピュータ装置を、ＬＴＵ'ｓの１つのシーケンスにマッピングすることを可能にする。このシーケンスは、カウンタによって（１回．．．Ｘ−１回のサイクルで）コンフィギュアラブルであり、ＲＡＭユニットは非常にうまく活用され、ないしは、同じサイズではるかに複雑なアルゴリズムを組み込むことができる。したがって該デバイスは、問題が全面的に処理できるように、計算時間のコスト（＝シーケンスの回数・サイクル時間）に合わせてスペース所要量を適合化することができる。それに応じてスペース活用度が優れている。
【００５０】
本発明によるコンピュータ装置の好ましい実施形態は、請求項１に従属する各請求項に記載されている。この場合、請求項１に記載の実施形態を、１つの従属請求項の特徴部と、または特に複数の従属請求項の特徴部と組み合わせることができる。それによれば、コンピュータ装置はさらに次のように構成されてもよい。
第２のクロスバースイッチングユニットの出力側のデータ／信号の記憶と処理のために、出力側データはまずプログラマブルな不一致論理ユニットに供給されると好ましい。この種の不一致ユニットにより、デザイン空間が拡大される。
上記に関わりなく、または特に上記に加えて、第２のクロスバースイッチングユニットの出力側のデータ／信号は、出力部がアーキテクチャの出力データを出すための出力ネットワークと組み合わされた、後置されたレジスタユニットへ供給することができる。このようなレジスタユニットは出力部をいっそう安定させる。
この場合、カウンタユニットには、共通のクロック信号が供給されるコンフィギュアラブルな比較ユニットが付属しているのが好都合であり、レジスタユニットには、不一致論理ユニットからのデータの受け取りを制御する比較ユニットのクロック信号が供給され、カウンタユニットには比較ユニットのリセット信号が供給される。
さらに、ＲＡＭユニットは、ＯＲ／ＭＵＸ切換ユニットと組み合わされたＲＡＭセルを有するＲＡＭベース領域を含むと好ましい。
この場合、ＯＲ／ＭＵＸ切換ユニットには、第１のクロスバースイッチング装置からアドレス信号が供給されてよい。
記憶デバイスとして、追加的にＣＡＭｓが設けられているのが好ましい。この場合、ＲＡＭｓの配線とその用途が、部分的にＣＡＭｓのそれに一致することを考慮する。すなわち、求められるのは内容ではなく、特定の内容が存在している場所である。このことは、ＲＡＭｓの一部をＣＡＭで置き換えることができ、または拡張できることを意味している。この範囲内で、ＲＡＭベースの主要部分にＣＡＭｓを利用することも可能である。
少なくとも１つのＣＧＡが統合ないしインプリメントされるのが特に好ましい。ＣＧＡは、複数の単純な状態オートマトンが結合されたものからなっている。状態オートマトンは、特に比較ユニットのクロック信号のクロックパルスで、それまでの結果（状態）と入力値とに基づいて新たな状態を計算する。そしてＣＧＡでは、このような複数の状態オートマトンが統合されており、個々のオートマトンのいくつかの出力部は他のオートマトンの入力部と接続されている。これは結合である。そしてこのインプリメントは、個々のオートマトンが「相並んで」ハードウェアで具体化されているような外観を呈する。このことは、レジスタユニットが設けられている場合、１つの状態オートマトンごとにそれぞれ複数のレジスタが、２進コード化された形態の状態を表すことを意味している。レジスタが設けられていない場合、これはいわゆる「非同期」オートマトンである。この場合には、第３のバス回線システムの回線の一部が状態コード化であるとみなされる。そしてオートマトンは、それ自体公知のやり方で、「個別に」インプリメントされる。結合は、第１及び第２のバス回線システムによって行われる。このときＲＡＭｓの多重分割は、インプリメントの可能性を拡張する役目を果たすことができる。
記憶素子として、特にＴＭＲ型式の磁気抵抗デバイスが設けられているのが好ましい。このようなトンネル磁気抵抗素子は十分に公知である。
【００５１】
次に、本発明によるコンピュータユニットの態様と機能形態について、図面を参照しながらさらに詳しく説明する。この場合、図１から図４はすでに説明したように従来技術に関わるものである。
【発明を実施するための最良の形態】
【００５２】
図５から図９には、対応する部分には同じ符号が付されている。図面では次のものが表示ないし表記されている。
１  第１のクロスバースイッチングユニットないしクロスバースイッチｒＣＢＳ１
２  構造化可能なＲＡＭユニットないしＲＡＭ
３  第２のクロスバースイッチングユニットないしクロスバースイッチｒＣＢＳ２
４  カウンタないしＣｏｕｎｔｅｒと呼ぶカウンタユニット
５  コンフィギュアラブルな比較ユニットないしＣｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｍｐａｒｅ
６  プログラマブルな不一致（ＸＯＲ）論理ユニットないしＰｒｏｇｒａｍｍａｂｌｅ  ＸＯＲ
７  レジスタユニットないしレジスタ
８  出力ネットワークないしＯｕｔｐｕｔ  Ｎｅｔｗｏｒｋ
９  回路への入力バスないしＩｎｐｕｔ
１０  フィードバックのための第３のデータバス回線システム
１１  状態信号ないしＳｔａｔｅ
１２  カウンタ状態信号
１３  アドレス信号
１４  クロック信号ないしＣｌｏｃｋ
１５  導き出されたクロック信号ないしＲ＿Ｃｌｋ
１６  リセット信号ないしＲｅｓｅｔ
１７  回路への出力バスないしＯｕｔｐｕｔ
１８  アドレス信号
２０  入力側の第１のバス回線システム
２１  出力側の第２のバス回線システム
Ｈｔ  ＲＡＭベースの主要部分
Ｓｔ  追加の制御部分
上記以外に図示している部品及びその名称については、以下の記載のなかで述べる。
【００５３】
５）本発明の説明
図５に示す、全般に符号Ｈｔが付されているアーキテクチャのＲＡＭベースの主要部分は、付属の符号１及び３が付された「クロスバースイッチ」とも呼ぶ２つのリコンフィギュアラブルなクロスバースイッチングユニットｒＣＢＳ１及びｒＣＢＳ２と、構造化可能なＲＡＭユニット２と、これらを接続する、図面ではアドレスバス（Ａ）及びデータバス（Ｄ）で表しているバスシステム２０及び２１と、追加のアドレス情報１３及び１８と、同時にユニット７の状態レジスタの入力部でもあるフィードバックをするデータバス１０と、回路への入力部のための接続バス９及び１１と、それまでの状態のフィードバック１１とで成り立っている。
【００５４】
追加の回路は、統合されたコンフィギュアラブルな進行制御のための、全般に符号Ｓｔが付された追加の制御部分、ならびに出力部へのインターフェースである。これには、リセット可能なカウンタ４と、リセット値でコンフィギュアラブルな比較ユニット５と、コンフィギュアラブルな不一致論理素子ないしＸＯＲ素子６と、多くの場合Ｄフリップフロップとして構成されるレジスタ７とが属している。クロックパルス１４は、カウンタ４及びｒＣＢＳ１（１）との両方に印加される。これら両方のユニットは、データの受け取りがポジティブな（または選択的にネガティブな）クロックパルスエッジで行われるように、クロックパルスで直接制御される。レジスタ７でのデータの受け取りは、クロックパルス１４から導き出されるＲ＿Ｃｌｋ１５によって行われる。コンフィギュアラブルな比較ユニット５での比較がポジティブな結果に終わった場合にだけ、このクロックパルスは通過し、すなわちポジティブな（またはネガティブな）クロックパルスエッジがレジスタ７に現れる。これは、計数値が比較値と一致している場合である。この場合には、ポジティブなクロックパルスエッジでも能動的なリセット信号１６がカウンタ４に出される。
【００５５】
レジスタ７の出力は、データバス１１を経由して、これまでの状態としてユニットｒＣＢＳ１（１）に結合されるとともに、出力部すなわち出力（切換）ネットワーク８へ結合される。このネットワーク８では、それぞれの状態を通常の形式で出力信号に変換することができる。なお、このユニットには本発明の枠内では特別な意義はない。
【００５６】
５．１  本発明に基づいて構成されたアーキテクチャの機能形態
構造化可能なＲＡＭとして構成され、本発明の明細書でさらに詳しく説明する記憶装置は、テーブルの記憶装置としての役目を果たす。すなわち、例えば小型のアドレスとして表現することができる記憶装置の第１の部分には、第１のテーブルが記憶されていると考えることができる。そして、この第１の部分に由来する値を用いて、例えば中程度のアドレスを表す第２のテーブルを記憶装置でアドレス指定することができ、さらに第３以下同様であり、最後には結果が確定する。
【００５７】
つまり本発明の用途は、有限状態オートマトン（ＦＳＭ）のアレイからなるセルオートマトン（ＣＡ）を、１つのデバイスで統合することを目指すものであり、そのために特に、ただし限定的にではなく、上に挙げた未公開の独国特許出願第１０２００４００７２３２．９号明細書に開示されている特徴部を利用する。同明細書では、コンフィギュアラブルなアーキテクチャに基づくグローバルセルオートマトン（ＧＣＡ）の具体化のコンセプトが展開され、記載されている。
【００５８】
５．２  機能形態の詳細
カウンタ４の意義は、必要なテーブルの数をアプリケーション固有に規定することにある。このことは、比較レジスタ５（Ｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｍｐａｒｅ）と合わせて考えなくてはならない。すなわち、このレジスタでは本来の動作の前に１つの数が記憶され、この数が、次の状態の完全な新規計算のために必要な動作時のランの回数を規定する。このとき比較レジスタ５における「０」は、ただ１つのテーブルすなわち古典的なルックアップテーブル（ＬＵＴ）が利用されることを意味しており、「１」は２つのテーブルが利用されることを意味しており、以下同様である。
【００５９】
このように、カウンタ４は、例えば０からＸ−１まで計数し、ただしこのときＸは好ましくは必ずしも２の累乗（例えば４、８、１６．．．）でなくてよい、非同期リセットを行う２進カウンタとして特徴づけられるのに対して、実際の計数終了は、ユニット５の比較レジスタによって規定される。そしてアクセスの終了は、次の状態が完全に計算されており、この状態を記憶できることを意味している。この記憶プロセスの制御は比較レジスタで行われ、すなわち、クロックパルスの制御によって行われる。
【００６０】
そのために信号Ｃｌｏｃｋ１４は、比較ユニット５のコンフィギュアラブルなレジスタで最新の比較と組み合わされて新たな信号Ｒ＿Ｃｌｋ１５となり、等しいかどうかの比較が真である場合にだけ、すなわちカウンタ値＝比較値である場合にだけ、ポジティブエッジが生じるようになっている。それと同時に、カウンタ４が定義されたとおり０にリセットされるように信号Ｒｅｓｅｔ１６が生成され、これが同時に開始値になる。この種の信号１５及び１６の生成は一般的な従来技術であり、したがって詳しく説明する必要をみない。これを実行できるようにするために、カウンタ４は、相応のリセット信号１６による非同期リセットのための入力部を装備していなくてはならない。
【００６１】
該回路の心臓部はＲＡＭユニット２で成り立っている。このＲＡＭユニットは入力側に、複数のアドレス部分バスに分割された、回線システム２０のアドレスバスを有する。さらに、ｈ＋１回線によってアドレス情報１８が提供される。このことは、個々のラン及びこれに伴う部分テーブルへのアクセスを制御するために必要である。テーブルアクセスの結果が（クロックパルスごとに部分テーブルへアクセスが部分的に並行して行われる）、同じく複数のデータ部分バスに分割可能な、回線システム２１のデータバスを介して出力される。追加の情報（１ビット）は、最後の通過時に多重化とＯＲ演算との間で切換を行うために必要である。
【００６２】
アドレスバス２０の情報、ならびにアドレス情報１８の情報は、リコンフィギュアラブルなクロスバースイッチｒＣＢＳ１１によって編成される。そのために入力バスシステムであるＩｎｐｕｔ９とＳｔａｔｅ１１、及び直近に読み出されたテーブル値のフィードバック１０が意図されており、その情報に基づいてアドレスバスを次回のクロックパルスのために編成することができる。その後の制御の役目をするのは、カウンタ４の最新値、現在進行中のサイクル、ならびにクロックパルス１４である。
【００６３】
このクロックパルス１４により、ＲＡＭユニットへ安定的に印加するために、入力値を中間記憶しておくことができる。これは状態Ｓｔａｔｅ１１については必要ない。それは、この値は記憶されており、Ｉｎｐｕｔ９ならびにデータバス１０を介してのフィードバックのために好都合であることが判明しているからである。これに代えて、フィードバック１０はすでにｒＣＢＳ２（３）で保存しておくこともできる。Ｓｔａｔｅ１０のためのデータバスの入力部を除いて、どの入力部も中間記憶をするように、または記憶をせずに直接結合するように、コンフィギュアラブルであることが前提となる。
【００６４】
素子ｒＣＢＳ１（１）は、クロスバースイッチとして製作されてもよい。このことは、ｒＣＢＳ１のどの出力部も各々の入力部から配線されていることを意味している。そして、これは自由にコンフィギュレーションすることができる。入力選択は最新のカウンタ状態にも左右されるので、このＣＢＳは、各々のカウンタ値について新たなコンフィギュレーションが記憶装置にロードされたリコンフィギュアラブルなＣＢＳとして製作するか、または、出力選択をカウンタ状態に依存させることができる、自由にコンフィギュアラブルな回路として製作するのが好ましい。リコンフィギュアラブルな回路としての実施形態は、特に、参考文献［２］に記載されており、それに対して、自由にコンフィギュアラブルな構造は市販のプログラマブルな論理デバイスに呼応しており、例えば参考文献［３］に記載されている。
【００６５】
追加のビット（追加情報）の生成は、自由にコンフィギュアラブルな回路の形態で行われなければならず、これは、このビットがすでにカウンタ４で計数値と比較値が等しいことの確認によって生成されておらず、このビットがその後に利用される場合である。２番目の可能性のほうがはるかに簡単ではあるが、フレキシブルさに欠けるので、一般にはｒＣＢＳ１での生成を前提とする。
【００６６】
ＲＡＭユニット２の出力は、第２のリコンフィギュアラブルなクロスバースイッチｒＣＢＳ２（３）によってさらに処理される。そのために、２kデータバス２１からの選択を可能にする、ｋビットのアドレス情報１３が追加的に必要である。さらにカウンタ４の値が、計数バス１２を介して、［Ｌｏｇ2（Ｘ）］（丸めることを意味する）によって伝送される。ｒＣＢＳ２については、ｒＣＢＳ１についての説明と同じことがコンフィギュレーション可能性ないし装備に関して当てはまる。
【００６７】
フィードバック１０は、最後のカウンタ状態になったときに次の状態を伝え、それ以前には中間結果をそのつど伝える。ただし次の状態が保存され、直接ないし換算されたうえで、周囲の出力部Ｏｕｔｐｕｔ１７に提供されるのが望ましい。そのために、好都合であると判明している場合には、１０の出力をコンフィギュアラブルなＸＯＲ素子（プログラマブルＸＯＲ）６で反転させることができる。これに関しては、最小化された論理和標準形（ＤＮＦ）としての表現のほうが、およそ半数のケースにおいて、最小化された反転論理和標準形（ＩＤＮＦ）よりも複雑であり、その逆も成り立つことが知られている。この両方を可能にするために、ユニット６が追加されている。
【００６８】
そして状態は場合により部分的に反転された形態で、クロックＲ＿Ｃｌｋ１５により制御されながら、レジスタ７に記憶される。Ｏｕｔｐｕｔ１７での出力は、場合により、状態ないしその表現から周囲で必要とされる信号が算出される、コンフィギュアラブルな組合せ回路Ｏｕｔｐｔ  Ｎｅｔｗｏｒｋ８によって再度換算されたうえで行われる。これは通常の措置である。
【００６９】
５．３  個々の素子の構造
ＲＡＭエリアないしＲＡＭユニット２
これに付属するのではないリコンフィギュアラブルなクロスバースイッチ１及び３を含めたＲＡＭエリア全体の構造が、図６に示されている。
【００７０】
ＲＡＭエリア２の全体は、複数のＲＡＭベース領域２２０に区分されている。図６では４つのベース領域が図示されており、この数は、絶対というわけではないが好ましくは２の累乗すなわち２、４、８、１６．．．である。このような個数の利点は、例えばサイズがＭの４つのエリアを、サイズ４*Ｍの１つのエリアに統合することができるという点に見ることができる。図６に示す２k個のベース領域２２０のこのような考えられる統合は、ｋ本の回線１３によって伝達される情報を用いて、ｒＣＢＳ２（３）で行われる。
【００７１】
ＲＡＭベース領域がｒＣＢＳ２の最新のコンフィギュレーションによって統合されないときは、または部分的に統合されないときは、ＲＡＭをセグメント化し、それによって上の５．１項及び５．２項に記載した機能形態を確保することが可能である。
【００７２】
ｒＣＢＳ１（１）と各々のＲＡＭベース領域との間の結合はアドレスバス２００によってそれぞれ行われ、これらのアドレスバスの総体がアドレスバス２０（図５）を形成する。各アドレスバスの回線のレイアウトはｒＣＢＳ１（１）でコンフィギュアラブルであり、入力としてはバスシステム９、１０及び１１、ならびにカウンタ状態１２を利用することができる。さらにｋビットのアドレス情報１３は、読み出されたデータバス２１０情報をｒＣＢＳ２（３）がどのような仕方で利用すべきかを表している。情報１３は、例えばカウンタ状態１２から生成されていてよく、０通過についてはＲＡＭ０が成り立ち、１についてはＲＡＭエリア１が成り立ち、以下同様であるが、これよりはるかに複雑な選択パターンもコンフィギュアラブルである。そのためにｒＣＢＳ２（３）の出力１０は、ＲＡＭベース領域の全てのデータバス２１の合計と等しいデータバス幅を有する。
【００７３】
ＲＡＭベース領域２２０
図７は、ＲＡＭベース領域２２０の詳細を示している。この領域は、複数のＲＡＭベースブロックまたはＲＡＭセル２２１で構成されており、これらの構造は通常のＲＡＭデバイスに対応している。本例では、それぞれ１つのアドレスバス２０１に、読み出されたＲＡＭ記憶セルのアドレスが印加され、通常のアクセス時間の経過後に、それぞれのデータバス２１１に結果が印加される。
【００７４】
ＲＡＭベース領域２２０におけるＲＡＭベースブロック２２１の数は、図７では４つに指定されている。具体的な個数は、絶対というわけではないが好ましくは、２の累乗すなわち２、４、８、１６．．．に相当している。ＲＡＭベースブロックの数は、アプリケーションで進行する種々のサイクルにＲＡＭ全体を分割することができる細分性を決定づける。それに対して、ＲＡＭユニット２におけるベース領域２２０の数は、どれだけの並行性及びこれに伴うデータバス幅で作業を行うことができるかを決定づける。
【００７５】
ＲＡＭベース領域に属するものとして、ＯＲ回路とマルチプレクサ選択回路とが組み合わされた、コンフィギュアラブルな切換ユニット３００がＯＲ／ＭＵＸ−Ｓｗｉｔｃｈとして図示されている（記号ＭＵＸ＝マルチプレクサ）。ここではアドレス情報１８に依存して、どのデータバスが出力部ＤＢ＿ｏｕｔ１０に現れるか、あるいは、データバスが事前に相互に論理的に組み合わされるかどうかが決定される。このような組合せは、未公開の独国特許出願第１０２００４００７２３２．９号明細書によれば、希望する機能性を可能にするために機械の最終段階で必要となる。
【００７６】
図８は、ＯＲ／ＭＵＸ切換ユニット３００の構造を示している。組合せはビット単位で行われることがわかる。図示しているように（データバス幅はここは図面表現上の理由から３つに限定されている）、各データバス２１０の接尾辞０をもつデータビットが論理サブユニット３１０にまとめられ、接尾辞１をもつデータビットがそれぞれ他のサブユニット３１０にまとめられることが明らかである。この場合、全てのサブユニット３１０は、相応のバス回線を介してアドレス情報１８と接続されている。
【００７７】
図９は、本発明による回路の特徴を持たせるためにＯＲ／ＭＵＸ切換サブユニット３１０に少なくとも存在しているべき内部構造を示している。論理ユニット３１１は相応のデータビットのＯＲ演算を可能にし、２k：１マルチプレクサ３１２はデータビットの選択を可能にする。これらの部分ユニット３１１及び３１２のうち、サブユニット３１０にそれぞれ１つが存在しており、そこではＯＲ／ＭＵＸスイッチユニット３００全体が１本のデータバス２１０のデータバス幅に相当している。部分ユニット３１１及び３１２の機能性、及びこれらに後置された２：１マルチプレクサ３１３の機能性はよく知られているので、これらの説明は省略することができる。
【００７８】
どの組合せが現在利用されるかの選択は、アドレス情報１８の追加の情報ビットを通じて行われる。未公開の独国特許出願第１０２００４００７２３２．９号明細書に定義された進行に基づいて、新たな状態を計算するための最初のランでは、異なるテーブルについて異なるＲＡＭベースブロックを利用するためにマルチプレクサを利用するよう尽力される。それに対して最後の通過時にはＯＲ演算が必要とされる。
【００７９】
追加の情報ビットは、ユニットｒＣＢＳ１（１）により、カウンタ値（１２）に基づいて計算されなくてはならない。
【００８０】
６）参考文献
[1]ロルフ・ホフマン(Rolf Hoffmann)、クラウス−ペーテル・フェルクマン(Klaus-Peter Voelkmann)、ヴォルフガング・ヘーネス(Wolfgang Heenes):「グローバルセルオートマトン(GCA):新たな大規模並列計算モデル(Globaler Zellularautomat (GCA):Ein neues massivparalleles Berechnungsmodell)」社団法人情報科学協会の報告書、並列アルゴリズムとコンピュータ構造、ISSN0177-0454 Nr.18(2001年)21-28頁;
http://www.ra.informatik.tu-darmstadt.de/publikationen/publik.html
[2]R.K.ブレイトン(R.K.Brayton)他:「VLSI合成のための論理最小化アルゴリズム(Logic Minimization Algorithms for VLSI Synthesis)」Kluwer Academic Publishers、 USA 1984、特に1から14頁、54から88頁、及び139から147頁
[3]マイク・トラップ(Mike Trapp):「PLDデザイン手法は既存のデザインを大容量デバイスに移行させる(PLD-design methods migrate existing designs to high-capacity devices)」EDN Access、1994年2月;
http://www.reed-electronics.com/ednmag/archives/1994/021794/04df1.htm
[4]ヴォルフガング・ヘーネス(Wolfgang Heenes)、ロルフ・ホフマン(Rolf Hoffmann)、クラウス−ペーテル・フェルクマン(Klaus-Peter Voelkmann):「グローバルセルオートマトンのアーキテクチャ(Architekturen fuer den globalen Zellularautomaten)」19th PARS Workship、2003年3月19-21、バーゼル;
http://www.ra.informatik.tu-darmstadt.de/publikationen/pars03.pdf
[5]国際公開第2004/040766A2号パンフレット
[6]米国特許出願公開第4870302A号明細書
[7]W.オバーシェルプ/G.フォッセン(W.Oberschelp/G.Vossen):「コンピュータ構成とコンピュータ構造(Rechneraufbau und Rechnerstrukturen)」8版2000年、オルデンブルク出版社(ドイツ)/ISBN3-486-25340-9
【図面の簡単な説明】
【００８１】
【図１】従来技術を説明する図。
【図２】従来技術を説明する図。
【図３】従来技術を説明する図。
【図４】従来技術を説明する図。
【図５】本発明に基づく装置の構造化可能でリコンフィギュアラブルなＲＡＭアーキテクチャの全体的構造を表す図。
【図６】リコンフィギュアラブルなクロスレールスイッチングユニットが付属する、ＲＡＭエリアないしＲＡＭユニットの構造を表す図。
【図７】ＲＡＭベース領域の構造を表す図。
【図８】ＯＲ／ＭＵＸ切換ユニットの構造を表す図。
【図９】この特別な切換ユニットの内部構造を表す図。
【図１】
2008513864.tif 000003
【図２】
2008513864.tif 000004
【図３】
2008513864.tif 000005
【図４】
2008513864.tif 000006
【図５】
2008513864.tif 000007
【図６】
2008513864.tif 000008
【図７】
2008513864.tif 000009
【図８】
2008513864.tif 000010
【図９】
2008513864.tif 000011
【国際調査報告】
2008513864.tif 000012
2008513864.tif 000013