(57)【要約】  計算機構の構成可能なアーキテクチャが少なくとも１つの個々に構成可能および／または再構成可能なスイッチング装置を有し、このスイッチング装置の出力変数は時点ｔn-1に、時点ｔnにおけるスイッチング装置の付属する入力に入力変数を形成する。時点ｔn-1とｔnとの間におけるスイッチング装置の出力変数をクロック制御されて記憶するための手段が設けられている。【選択図】      図９
2007522571.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つの個々に構成可能および／または再構成可能なスイッチング装置を有し、このスイッチング装置が、入力を備えたステージと出力を備えたステージとを有し、出力のうち少なくとも幾つかの出力の出力変数が、時点ｔn-1に、時点ｔnにおけるスイッチング装置の付属する入力に入力変数を形成し、時点ｔn-1とｔnとの間におけるスイッチング装置の出力変数をクロック制御されて記憶するための手段が設けられている計算機構の再構成可能なアーキテクチャ。
【請求項２】
記憶手段がレジスタ記憶素子であることを特徴とする請求項１記載のアーキテクチャ。
【請求項３】
３つのステージを前後に接続したスイッチング装置の３ステージ構成を特徴とする請求項１または２記載のアーキテクチャ。
【請求項４】
第１ステージが複数の並列に接続された記憶素子からなり、これらの記憶素子が入力線路を介してアドレス指定可能であり、付属する求められた項内で結合された入力変数の部分量が各記憶素子に供給することができ、
第１ステージの後方に配置される第２ステージが、個々の項の識別子によってアドレス指定可能な記憶素子を有し、
第２ステージの後方に配置される第３ステージが、第２ステージの記憶素子から個々の項の出力値を論理和演算するための手段を備えていることを特徴とする請求項３記載のアーキテクチャ。
【請求項５】
最小化法によって項が求められることを特徴とする請求項４記載のアーキテクチャ。
【請求項６】
少なくとも１つのクロスバースイッチを介して第１ステージが第２ステージと結合されていることを特徴とする請求項４または５記載のアーキテクチャ。
【請求項７】
記憶素子としてのＣＡＭおよび／またはＲＡＭを特徴とする請求項１ないし６のいずれか１つに記載のアーキテクチャ。
【請求項８】
少なくとも１つのＣＧＡを統合したことを特徴とする請求項１ないし７のいずれか１つに記載のアーキテクチャ。
【請求項９】
特にＴＭＲ型の磁気抵抗記憶素子を特徴とする請求項１ないし８のいずれか１つに記載のアーキテクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも１つのスイッチング装置を有する、アルゴリズムを並列計算するための計算機構のアーキテクチャに関する。
【背景技術】
【０００２】
公知の計算機モデル
図１の原理図から明らかとなるようないわゆる「フォンノイマン型アーキテクチャ」は一般に汎用計算機と見做される。ここでは、計算機の助けを借りて、コンポーネント中央処理装置［ＣＰＵ、その中に制御装置（ＣＵ）と演算論理ユニット（ＡＬＵ）が含まれる］、メモリ（記憶装置）、インプット／アウトプット（入力／出力）およびバス方式を有するこのアーキテクチャに基づいて、あらゆるアルゴリズム可能な問題は基本的に計算することができるということが理解できる。このような計算機をその都度の問題に調整することは、プログラムによって、すなわち例えばプログラム言語Ｃ、Ｃ＋＋またはＪａｖａ（登録商標）でアルゴリズムをテキスト記述することによって行われる。このプログラムは、それ自体プログラムである翻訳系（コンパイラ）によって機械読取可能なプログラムに変換される。
【０００３】
プログラムの処理が行われる計算機は図１によるフォンノイマン型アーキテクチャおよび類似のアーキテクチャ（例えばハーヴァード・アーキテクチャまたは修正ハーヴァード・アーキテクチャ）に基づいており、基本的に逐次型である。これは、大量の機械命令からなるアルゴリズムが、第１命令が既知であることによって処理されると理解される。或る命令に続く命令は記憶装置内で次のアドレスにある命令（正規プログラムフロー）であるか、または最後に実行された命令が、実際のプログラム位置を別の個所にずらす飛越し命令であったかのいずれかである。実際のプログラム位置を記憶する内部レジスタは「プログラムカウンタ」（ＰＣ）と称される。
【０００４】
この逐次処理原理は、或る時点に厳密に１つの命令が処理中であることを意味する。これがフォンノイマン原理と称される。ＲＩＳＣ（Reduced Instruction-Set Computing）、スーパースカラまたはＶＬＩＷ（Very Long Instruction Word）と称される最新のアーキテクチャは確かに或る時点に１つ以上の命令を実行するのではあるが、しかし逐次性の原理は維持される。全体としてこの実行原理は「時間逐次型」（Computing in Time）と称され、これはアルゴリズムが時間を必要とすることを意味する。
【０００５】
まったく別のプログラム処理原理がプログラム可能型論理モジュール［ＰＬＤ（Programmable Logic Devices）、図２に相当］もしくはその最も知られたインプリメンテーション、ＦＰＧＡ（Field-Programmable Gate Arrays）に設けられている。このアーキテクチャも汎用であり、すなわちあらゆるアルゴリズム可能な問題に利用可能である。その際、大抵はビット平面で定義され、それゆえに論理素子と称される要素演算ユニットがネットワーク内で相互接続されるように、プログラミングは行われる。このプログラミング形式は大抵、「構成（Configration）」と称される。
【０００６】
ＰＬＤ内でのプログラム処理は、フォンノイマン原理とは異なり最大並列性で行われる。１つのモジュールの構成全体は単一の命令として(しかしながらフォンノイマン原理とは異なり固定定義されるのでなく合成されて)把握することができ、この命令が１サイクル内で完全に処理される。しばしば外部クロックと結び付けられるサイクル時間は次に合成の複雑性に依存している。これにより、プロセッサと比較して低いクロックが使用されるが、しかしこのクロックは実行の並列性によって十分に補償される。この実行原理は「Computing in Space」と称される。
【０００７】
決定的有限オートマトン
問題をアルゴリズム化するための主要モデルの１つが決定的有限オートマトン［ＤＥＡ、またＤＦＡ（deterministic finite automata）］である。これらは技術において「Finite State Machines」（図３の原理図によるＦＳＭ）とも称される。このモデルは問題を、入力値に依存してそれらの間の定義された伝達関数を有する状態の系列と見做す（Next State Decoder）。ＤＥＡのモデルは理論上、フォンノイマンモデルほどに強力ではないが、実務において任意の問題を、場合によってはモデル内の付加物で、解決することができる。
【０００８】
このＤＥＡの最大の問題は、その関数が状態の数に伴って指数的に増加し、半導体材料（特にシリコン）の面積需要に関係してくることにある。この理由から、互いに通信する多数のオートマトンからなるモデルが好んで選択される。このような計算機モデルは「複雑な協力するオートマトン」と称される。
【０００９】
ブール関数の表現
ブール関数またはスイッチング関数は、Ｂ＝｛０、１｝とした写像（以下「コピー」）ｆ：Ｂm→Ｂnであり、これはｆ＝（ｆ1、ｆ2、…ｆn）の形で、つまり関数ｆk：Ｂm→Ｂのベクトルとして表現することができる。それゆえに以下では、出力値を有する関数ｆkのみから出発する。これらは一般にｆと称される。
【００１０】
さらに、ｆが論理和標準形または論理積標準形の形式で表現できることが知られている。論理和標準形にとってこれは、
ｆ＝ｚ１＋ｚ２…＋ｚｋ；ｋ＝１、２、…２ｍ、'＋'を論理和演算子として（論理ＯＲ）                                                      （１）
ｚｉ＝ｙ１＊ｙ２＊…ｙｎ；ｉ＝１、２、…ｋ、'＊'を論理積演算子として（論理ＡＮＤ）                                                    （２）
が妥当することを意味する。使用されるのは当然このようなｚｉのみであり、これについて、記述されるべき関数は値ＴＲＵＥまたは'１'を受け取る。記号ｙｊは、入力ベクトルｘ＝（ｉ1、ｉ2、…ｉk）からどのように入力ビットｉkが選ばれるべきかを決定する。入力ビットには量｛０、１｝からなる値のみ許容されているのに対して、ｙｊについてこれは変更されねばならない。これらの値には３つの属性｛０、１、−｝のうちの１つが割り当てられる。ｙｊ用の属性'１'は、ｉkがそのまま取られることを意味し、'０'は、ｉkが反転して選択されねばならないことを意味し（／ｉkとして表記）、'−'はドントケア、すなわちｉkは使用されない。ｙｊに値｛０、１｝のみが属性として使用される場合、「標準論理和標準形」と呼ばれる。
【００１１】
この表現が重要であるのは、これにより、入力ビットの順番が既知である場合前記式（２）による部分成員ｚｉが、「項」とも称され、いわゆる「ストリングターム」として表現可能となるからである。順番がｉ１、ｉ２、ｉ３の場合、"１１１"はｚ１＝ｉ１＊ｉ２＊ｉ３であることを意味し、"０−１"はｚ２＝／ｉ１＊ｉ３等である。
【００１２】
３つの入力ビットの場合、可能なすべての入力ベクトルの量はｖ＝｛０００、００１、０１０、０１１、１００、１０１、１１０、１１１｝である。例示的に関数ｆが入力ベクトル｛００１、０１１、１１１｝でのみ値ＴＲＵＥを受け取る場合、これらのみを明示する必要もありまたは明示することができる。ストリングタームの形式でこれは１１１と０−１によって行うことができる。これは与えられた関数を完全に特徴付け、論理和標準形ｆ＝／ｉ１＊ｉ３＋ｉ１＊ｉ２＊ｉ３と同形である。
【００１３】
内容アドレス記憶装置（ＣＡＭ）
読出し書込み記憶素子［ＲＡＭ（Random Addressable Read/Write Memory）］はふつうデータおよびプログラムを記憶するのに利用される。その場合、アドレスがアドレスバスに印加され、読出し過程のときモジュール固有の待ち時間の経過後、記憶されたデータがデータバスに印加され、継続使用することができる。書込み過程は上記と同様に作動する。
【００１４】
データを得たいとするインスタンス（例えばプロセッサ）の視点からアドレスは既知であり、記憶された内容は事前には既知でない。しかし、状況がまったく逆のアプリケーションが存在する。記憶された内容が既知であり、この内容がどのアドレスに記憶されているかに関心があり、答えが「存在しない」であることもある。この種の問合せを支援する記憶素子が内容アドレス記憶素子［ＣＡＭ(
Content- Addressable Memories）］と称される。
【００１５】
ＣＡＭと称されかつこの行動を直接支援する記憶素子は特殊なモジュールと見做され、決して頻繁に見られるものではない。しかし実際的応用のためＣＡＭの機能性は通常のＲＡＭモジュールによってエミュレートすることができる。しかしこのためには、ＣＡＭ内に直接記憶されることになるすべてのデータについて、問合せ時に、値ではなく記憶アドレスが明らかとなり、対応するアドレスが事前に計算され、データに対応したＲＡＭアドレスに記憶されねばならない。
【００１６】
セルオートマトン
セルオートマトン［ＣＡ（cellular automaton）は、１フィールド内に固定トポロジーで配置されかつその他の性質を有する大量の有限オートマトンである（非特許文献１、４参照）。これら大量のＦＳＭはｎ次元アレイ（大抵はｎ＝２）として配置されており、各場所に固定座標が与えられている。各ＦＳＭが明確に近傍系を有し、それらと通信することができる。ｎ＝２の場合、大抵、４つの周辺ＦＳＭ（「天空方向」においてＮ、Ｅ、Ｗ、Ｓ、それゆえに「ＮＥＷＳ近傍系」とも称される）が近傍系と見做される。
【００１７】
近傍系との通信は、直接的近傍系の状態が読出し可能、従って評価可能であるように行われる。各時間ステップですべてのセルの状態が並列に計算される。新たな状態を計算するのに遠く離れたセルからのデータが利用されねばならない場合、これらのデータはセルからセルへと歩進的にトランスポートされねばならない。こうして古典的セルオートマトンは、高いデータ局在性をもって問題提起を計算するのに十分適している。
【００１８】
ＣＡは、先に論じたアーキテクチャと同様に汎用計算機と見做され、しかもそれらは完全に並列に作動する。ＣＡのネットワークがハードウェアに、例えばＡＳＩＣに、またはＰＬＤにも、コピーされねばならない場合、結接の数はオートマトンの数に伴って線形に増加する。結線自体は、選択されるトポロジーに応じて比較的短く、固定布設されている。つまりＣＡ相互の通信支出は比較的少ない。スイッチング機能をＲＡＭにコピーするのに必要な所要メモリ量がこのスイッチング機能の計算量と見做される場合、１つのセルの挙動に相応するスイッチング機能の最大の計算量は入力変数の数に伴って指数的に増加し、また関数の出力変数の数に伴って線形に増加する。入力変数の数はこの場合、セルに接続されたすべてのＣＡの状態をセル自体の状態も含めて符号化するのに必要なすべてのビットの合計である。こうしてセルの最大の計算量は各オートマトンの結線の数によって実質的に限定されている。
【００１９】
グローバルセルオートマトン［ＧＣＡ（global cellular automata）］の構想は、１つのセルを最も近い近傍系だけでなくフィールド全体内の任意のセルへと結線することを可能とすることによって、ＣＡの制約を克服する。従ってＧＣＡはもはや固定トポロジーを有するのでなく、問題提起に適合され場合によっては計算の伝搬時間に対して変化しさえするトロポジーを使用することさえ可能である。これは問題処理に著しい加速をもたらすことがある。単一のオートマトンの結線の数は場合によっては上限によって確定されている。単一の結線のみが許容されている場合、単アームＧＣＡ、一般的にはｋアームＧＣＡと呼ばれる。
【００２０】
その結果、ＧＣＡの１フィールドを実現するときセル相互の通信に必要な支出はセルの数に伴って著しく増加する。個々のオートマトン間で可能な結線の数はオートマトンの数に２乗して増加する。
【００２１】
個々のオートマトン自体もしくは基礎となるスイッチング関数の計算量は、従来のＣＡにおけると同様に各セルの結線の数に実質的に依存している。再構成可能な回路（ＰＬＤ）にＧＣＡがコピーされねばならない場合、任意のスイッチング関数を実現することのできる個々のセルは最大可能な計算量を可能としなければならない。
【００２２】
ローカルメモリを有する各１つの演算装置に個々のオートマトンがコピーされる場合、各セルは複雑なスイッチング関数を実現することもできる。すべてのセルの任意の通信のための支出はセルの数に２乗して増加する。その場合回路の粒度（Ｋoernigkeit）は、セルの数もしくはセル間の結線のビット幅によって決まる。このような回路は、ＦＳＭの数およびビット幅の点で回路の設定に一致したＧＣＡをごく良好に実現することができる。複雑なスイッチング関数を個々のセルに実現することも可能である。しかし、結線の数と所要のビット幅の点で所定の粒度と一致しないＧＣＡは、これを回路にコピーするのが困難であるという不利がある。
【００２３】
個々のセルが組合せ論理回路として実施される場合、各セルは自己の状態も含めて別のすべてのセルのデータを処理可能でなければならない。この理由から各組合せ論理回路は、すべてのセルのすべての２進化状態を入力変数として含むことのできるスイッチング関数を実現できなければならない。スイッチング関数の出力変数の数は、単一のセルのすべての状態を２進化することを可能としなければならないだけである。その際不利な点として、スイッチング関数の計算量は入力変数の数に伴って指数的に増加する。セル相互の通信支出が多項式的に増加することもやはり不利である。
【００２４】
つまりＧＣＡを格納するのに適した（再）構成可能なアーキテクチャ（ＰＬＤ）はＦＳＭごとに任意の計算量を格納可能でなければならない。これは、（ＦＳＭがＰＬＤの１つのセルに直接コピーされねばならない場合）セルが任意のあらゆる関数を格納しなければならないことを意味する。そのことからセル寸法の指数的増大が生じることは知られている。それに加えて、ＰＬＤ内の構成可能なネットワークは完全に実施されていなければならない。すなわち、各セル出力はあらゆる別のセルと接続可能でなければならない。こうしてネットワークが２乗的に増大し、ネットワークの構成も同様である。
【００２５】
両方の要件を満たすＰＬＤアーキテクチャは現在市場になく、または知られていない。完全な設計空間を有する大きなセルは存在しない。あるのは、完全な設計空間を有する小さなセル［いわゆるルックアップテーブル構造（ＬＵＴ）］、または任意の関数をコピーするための不完全な可能性を有する大きなセルのみである。すべてのセルの完全接続性はセルが大きい場合にのみ可能である。従って、存在するＰＬＤへのＧＣＡのコピーは困難であり、はるかに不可能でさえある。
【発明の開示】
【発明が解決しようとする課題】
【００２６】
本発明の課題は、上記諸問題が少なくとも減少するように、技術分野に指摘したアーキテクチャを構成することである。特に、アルゴリズム内に隠れた並列性を実際に利用することのできる優れたモデルと判断されるＣＧＡをＰＬＤ等のプログラマブルハードウェアにコピーできる可能性が示されねばならない。すなわち、任意のＣＧＡの格納を可能とするＰＬＤアーキテクチャが明示されねばならない。
【課題を解決するための手段】
【００２７】
前記課題は、本発明によれば、請求項１に明示した措置で解決される。それによれば、冒頭に指摘した特徴を有するアーキテクチャは少なくとも１つの個々に構成可能および／または再構成可能なスイッチング装置を含み、このスイッチング装置が、入力を備えたステージと出力を備えたステージとを有し、出力のうち少なくとも幾つかの出力の出力変数が、時点ｔn-1に、時点ｔnにおけるスイッチング装置の付属する入力に入力変数を形成し、時点ｔn-1とｔnとの間におけるスイッチング装置の出力変数を記憶するための手段が設けられている。その際、すべての入力が（記憶された）出力によって占有されている必要はなく、自由入力も存在し得る。さらに、連結されていない出力、つまり例えば再使用されることのない最終結果のみを表す出力も設けておくことができる。
【００２８】
スイッチング関数の直接に連続する評価が時点ｔn-1、ｔnで表される。技術的に好ましい実現態様においてこれらの時点はクロック時間Ｔを有する印加クロックから導き出すことができ、ｋ＝１、２、３、…としてｔn−ｔn-1＝ｋ・Ｔが成り立つ。その際、与えられたアプリケーションについてｋは一定であり、さまざまなアプリケーションについてそれは異なるように選択することができる。
【００２９】
スイッチング関数の計算量が入力変数の数に伴って指数的に、また出力変数の数もしくはコピーされるべきＧＣＡのフィールド内のセル数に伴って直線的に増加し、ＧＣＡ相互の通信支出がセル数に伴って少なくとも２乗で増加することが確定しているので、本発明に係る（再）構成可能なアーキテクチャはＧＣＡを格納するのに適している。このためそれは少なくとも１つの個々に構成可能なスイッチング装置からなり、このスイッチング装置の出力変数は、時点ｔn-1に、時点ｔnにおけるスイッチング装置の入力変数を形成する。時点ｔn-1とｔnとの間にスイッチング装置の出力は記憶装置、特にレジスタに記憶され、こうして複雑なスイッチング装置もしくはＦＳＭが生じる。構成内の個々のステージはやはりスイッチング装置を意味する。この構成のみが各ステージの個々の組合せ論理回路内にあり、各ステージは構成可能な組合せ論理回路と記憶素子とからなる。
【００３０】
従って本発明に係るアーキテクチャでは、組合せ論理回路は、それらの各出力がアーキテクチャ入力の実際の値に依存したブールスイッチング関数ユニットとして設けられているのに対して、前記少なくとも１つのスイッチング装置は、それらの出力がこの時点および有限数の先行時点における入力の実際の値に依存したブールスイッチング関数ユニットであると理解することができる。従って、スイッチング装置は組合せ論理回路と少なくともエッジトリガ記憶素子とから構成される。
【００３１】
本発明に係るアーキテクチャの有利な諸構成は請求項１に従属する請求項から明らかとなる。請求項１による実施形態は複数のうちの１つの従属請求項の１つの特徴と、または主に複数の従属請求項の特徴とも、組合せることができる。従って、アーキテクチャは、なお以下の箇条書きの如くに構成しておくことができる。
記憶手段としてレジスタ記憶素子を設けておくことができ、ここでは一般にエッジトリガフリップフロップ素子である。
好ましくは、スイッチング装置は３ステージ式に構成されており、３つのステージは前後に接続されている。複数の入力を有するステージと複数の出力を有するステードとの間に配置される記憶素子を有する第２ステージは第１ステージで生成されるデータを処理しかつ処理されたデータを第３ステージに転送するのに役立つ。
その際有利には、第１ステージは複数の並列に接続された記憶素子を含むことができ、これらの記憶素子は入力線路を介してアドレス指定可能であり、付属する求められた項内で結合された入力変数の部分量は各記憶素子に供給することができ、
第１ステージの後方に、個々の項の識別子によってアドレス指定可能な記憶素子を有する第２ステージが配置されており、
第２ステージの後方に配置される第３ステージは、第２ステージの記憶素子から個々の項の出力値を論理和演算するための手段を備えている。
その際、好ましくは最小化法によって個々の項を求めることができる。
さらに、少なくとも１つのクロスバースイッチを介して第１ステージは第２ステージと結合しておくことができる。
記憶素子として有利にはＣＡＭおよび／またはＲＡＭを設けておくことができる。
特別有利には、少なくとも１つのＣＧＡを統合することができる。
記憶素子として、特にＴＭＲ型の磁気抵抗部品を設けておくことができる。相応するトンネル磁気抵抗素子はそれ自体公知である。
【００３２】
記憶素子として理解されるのは、一般に若干数のトランジスタまたは匹敵するモジュールと例えば前記磁気抵抗素子等の記憶機能を可能とする本来の素子（記憶ユニットごとに）とから構成されるあらゆる内部素子のアーキテクチャである。
【００３３】
本発明に係るアーキテクチャの前記他の諸構成の根底には特に以下に示す論述がある。
選択されたスイッチング装置内のスイッチング関数の計算量が確かに出力変数の数に伴って線形に増加するが、しかしセル相互の通信支出全体が省かれる。そのようなスイッチング関数に、若干数の出力変数を有する多くの個々のオートマトン、または多くの出力変数を有する若干数のＧＣＡ、またはさまざまなセルの混合物はコピーすることができる。従って、粒度（Ｇranularitaet）は設けられておらず、ＦＳＭ相互の通信は基本的に完全に可能である。しかし、組合せ論理回路を格納することのできるスイッチング関数の最大計算量によって限界が与えられている。
【００３４】
大量の入力を有する１つのスイッチング装置の利用‐これは一般的事例において、若干数のＦＳＭを有するＧＣＡがコピーされる場合に発生する‐は、いわば所要面積が入力の数に指数的に依存し得ることを意味する。各状態が１ビットで符号化されるとき面積の指数的（状態数）増加が上限と見做される。一般的事例において所要面積は小さくなる。しかし汎用回路は最大事例を含まねばならないので、指数的増大法則を適用すべきであろう。
【００３５】
ここで特別有利であると見做すことができるのは、スイッチング装置を格納する回路を３つの特殊な区域／ステップに分割することである。このため以下に示す（再）構成可能な回路は、大量の入力変数と大量の出力変数とを有するスイッチング関数をスイッチング装置として実現することができる。
【００３６】
スイッチング関数用の再構成可能なスイッチング装置を構想するために、起点となる考えとして２つの可能性を検討する。
【００３７】
一方で、１つのスイッチング関数を完全に１つのＲＡＭ記憶装置にファイルすることが可能である。スイッチング関数の入力変数はアドレスビットを形成し、入力変数の可能なあらゆる組合せについて記憶セルをアドレス指定する。その場合、この記憶セルの内容はスイッチング関数の値に一致し、記憶素子のデータ線路は関数の出力変数を形成する。この構想の利点は単純な回路構造と、簡単な再構成可能性と、記憶素子の高い集積密度と、スイッチング関数の評価を必要とする固定時間にある。しかしながら、所要の記憶セルの数、つまり所要の記憶素子の大きさは、入力変数の数に伴って指数的に増加する。この理由から、小さなスイッチング関数のみをこうしてコピーすることができる。
【００３８】
これは、ＰＬＤにおける技術の現状であり、Look-Up-Table-StructurとしてＦＰＧＡにおいて利用され、大抵は４つの２値入力変数と１つの２値出力とを有する。
【００３９】
スイッチング関数を組合せ論理回路にコピーする第２の可能性は、２ステージまたは多ステージネットワークにゲートを構成可能に配置することにある。従って、最小のゲート使用でスイッチング関数を組合せ論理回路にコピーすることが可能である。スイッチング回路理論はここでは例えばリード‐マラー形式等のスイッチング関数の好ましい表現形式を提供し、または論理式を簡素化するための高性能アルゴリズムも提供する。この式の利点はゲートの使用が最小となり、高性能方法およびアルゴリズムを簡素化に利用する可能性とにある（非特許文献２、非特許文献３参照）。この方法は、例えばＲＯＭ実現の固定スイッチング関数を表現するのに十分利用することができる。例えばクロスバースイッチ等のハードウェアモジュールを介して個々のゲートは再構成可能に接続することができるが、しかしここでは再構成可能性のための支出がスイッチング関数の入力変数の数に伴って指数的に増加する。
【００４０】
具体的実施例に基づく発明の説明
第１可能性の諸利点、高い集積度、再構成可能性、回路の簡素化と、第２変更態様の諸利点、ゲート関数の僅かな使用、最新方法の応用可能性とを結び付けることができるようにするために、本発明によれば以下の式が設けられている。
【００４１】
仮定された実施形態の基本的考えは、高い集積密度の諸利点を利用するためにＲＡＭモジュール内に極力多くの論理機能性を具現する再構成可能なスイッチング装置の開発である。このＲＡＭモジュールは、スイッチング関数一式を記憶する必要のないように、１つの多ステージ回路内で再構成可能に互いに接続されねばならない。
【００４２】
第１ステージ：
スイッチング関数の入力変数は組合せ論理回路の入力線路によって現される。回路の第１ステージは、入力線路によってアドレス指定される多数の並列に接続された記憶素子からなる。入力線路の部分量、従ってスイッチング関数の入力変数が各記憶素子に割り当てられている。最小化法によって求められるスイッチング関数の項（式（２）の最小化されたｚｉもしくはそのストリングターム表現）は、入力ステージの記憶素子に記憶される。このため、項内で結合された入力変数が割り当てられている各記憶素子内に、項内での入力変数の占有と、この項に対する明確な識別子が記憶される。各モジュールには入力変数の一部が割り当てられているだけなので、それぞれ部分項のみが記憶される。項内で結合された変数が割り当てられていない記憶素子内には、同様に項の一部は記憶されない。組合せ論理回路の入力線路に１つのビット組合せが印加されると、このビット組合せに適合したすべての記憶素子はその識別子を、データ線路を介して回路の第２ステージに転送する。
【００４３】
第２ステージ：
（部分）項の識別子は第２ステージ内の１つの記憶装置をアドレス指定する。この記憶装置には、各項に付属する識別子ビットパターンと、スイッチング関数の出力値が記憶されている。第１ステージから提供される識別子のビットパターンが記憶された項のビットパターンに一致する場合、この項は回路の入力線路に印加される。次に回路の第２ステージは入力線路に印加されるすべての項の出力値を、データ線路を介して第３ステージに転送する。
【００４４】
第３ステージ：
第３ステージでは個々の項の出力値が論理和（ＯＲ）演算され、こうしてスイッチング関数の結果を形成する。
【００４５】
以下、以上の論述を考慮して図面を参考に具体的実施例に基づいて本発明がなお説明される。図面は以下の部分を含み、そのうち図１〜図３は背景技術に記載の技術の現状について既に言及したものである。
【発明を実施するための最良の形態】
【００４６】
図中、対応する部品には同じ符号が付けてある。
【００４７】
図４〜図９による実施例について仮定する本発明に係るアーキテクチャは先に言及したように３つのステージを有し、詳細には１つのスイッチング関数用に１２の入力変数と１０の項と８つの出力変数とを有する。表１はこのため１つの例示関数についてすべての項（「極小項」とも称される）を示す。ストリングタームの表現は、その際３つの４群が生じるように選択されている。
【００４８】
【表１】
2007522571.tif 000003
【００４９】
ところでこの表を列ごとに検討すると、ごく少数の異なる組合せがストリングターム内に現れることが確認される。２値表現の場合、列ごとにここでは２４＝１６の異なる組合せが、３値表現の場合相応に３４＝８１の組合せが存在し得よう。この例ではそのうち列１〜３用に５、３、４のみが現れ、入力組合せはそれぞれ完全に「‐」である。
【００５０】
スイッチング関数のパラメータとして１つのビット組合せが入力に印加されると、印加されたビット組合せを有する１つの部分項を記憶する１つの記憶素子は付属する項の識別子を送り返す。第１ステージのこの記憶素子が図４では３値ＣＡＭとして実施されている。すなわち、２値情報としてアドレスバスに実際に印加される入力ベクトルは記憶された３値情報と比較される。目的について記憶されたやはり３値の識別子が出力として出力される。
【００５１】
全識別子が全体で項組合せの識別子を形成し、この識別子が組合せ論理回路の入力に印加される。この項組合せは複数の項を十分に含むことができる。図示例において例えば項３、４、８、または項４、５、８の組合せを印加することができる。最初の事例ではビット組合せ１００００１が、第２の事例では組合せ１１０００１が、第２ステージに印加される。
【００５２】
項組合せの識別子は回路の第２ステージで検知され、関与する各項についてスイッチング関数の付属する出力値を提供する。ところでこの第２ステージは１つの３値ＲＡＭのみからなる。すなわち、このステージのアドレスバス情報では３値であるが、しかしながら記憶されたデータは２値である。
【００５３】
回路の第３ステージでは、印加される項の出力値は論理和演算され、全体でスイッチング関数の関数値を形成する。
【００５４】
第１ステージの記憶素子
部分項を格納するための記憶素子として‐既に触れたように‐ごく特殊なモジュールもしくはごく特殊なアーキテクチャを利用することができ、ここでは図４により３値ＣＡＭで表される。その際、多重一致の問題もなお基本的に論議されねばならないが、しかしこれは別の実現可能性に関連して行うことにする。
【００５５】
完全連想キャッシュも第１ステージ用に利用することが可能である。ここでは部分項はいわゆるタグとして記憶することができ、キャッシュドデータは検知された項の識別子として役立つ。しかし部分項が未結合変数を含み、これらの変数が、印加されるビット組合せと比較してドントケア（ＤＣ）桁と表現される場合、ＤＣとの比較を満たすこの項のすべての占有について１つのタグがタグＲＡＭに印加されねばならない。さらに、ＤＣとの比較によって部分項の重なりが生じる。例えば上記例の第１部分項記憶装置内のビット組合せ００１１は項１にも項３にも付属する。つまり項の組合せだけでなく部分項の組合せも可能である。
【００５６】
この理由から、部分項記憶装置として実現するのに通常の、すなわち２値ＲＡＭモジュールもしくはアーキテクチャが使用される。これらＲＡＭのそれぞれは組合せ論理回路の入力線路の一部によってアドレス指定される。ＤＣ桁を有する同じ部分項に一致したビット組合せのアドレスでは（ストリングターム中の各ＤＣ桁は、ヒット桁の数が２進符号化のとき２だけ高められることを意味する）、それぞれ同じ識別子が記憶装置に蓄えられる。使用されるＲＡＭの出力幅が、識別子を表現するのに不可欠なビット幅よりも大きい場合、他のビットをコンテキスト値として利用することができる。このコンテキストは例えばスイッチング関数の入力変数の無効占有を表示することができる。
【００５７】
通常のＲＡＭは、例えばそのキャッシュ‐ミス出力にタグＲＡＭ等の存在しないデータ用の状態表示を持たないので、第２ステージでビット組合せの比較に使用されるデータ線路上で１つのビット組合せは印加されていない部分項用の標識として使用されねばならない。そのことが図５ｃ）に識別子８で与えられている。
【００５８】
第２ステージの記憶素子
部分項を記憶するための第１ステージのＲＡＭにおけると同様に、回路の第２ステージで項組合せを比較するときにもＤＣは考慮されねばならない。それゆえにここでも通常のＲＡＭが使用される。このＲＡＭは項組合せの識別子でアドレス指定される。
【００５９】
再び複数のアドレスが同じ項組合せに一致することがあるので、第２ステージの記憶装置は分割されねばならない。第１ステージのビット組合せが第２ステージの１つのＲＡＭをアドレス指定する。そこでは有効な各項組合せについて１つのインデックスが蓄えられており、このインデックスは関与する項の出力変数をそれ自身含むＲＡＭをやはりアドレス指定する。こうして、ドントケア桁を有する項組合せによって生じるさまざまなアドレスはスイッチング関数の出力値の同じインデックスにコピーすることができる。
【００６０】
図６は第２ステージのＲＡＭ組合せに対する第１ステージの結果の相応するコピーを示す。
【００６１】
図７による最終的アーキテクチャ
１つのＲＡＭは単一のインデックスを提供できるにすぎないので、スイッチング装置の第１ステージにおいて出力値記憶装置内に、検知された組合せに関与した全項の論理和演算された出力値が格納されねばならない。従ってこのステージにおける出力ＲＡＭはスイッチング関数の可能なあらゆる関数値を記憶できなければならない。可能な関数値の数はスイッチング関数の出力変数の数に伴って指数的に増加するので、スイッチング装置の第２ステージの複数の組合せ・出力記憶装置は並列に使用され、それらの出力組合せは論理和演算される。こうして１つのスイッチング関数のすべての関数値を生成することができる。
【００６２】
個々の組合せ記憶装置の容量を一層良好に利用できるようにするために、組合せ記憶装置のすべてのデータ線路は１つのクロスオーバスイッチを介して組合せ記憶装置のすべてのアドレス線路と接続される。こうして任意のデータ線路が組合せＲＡＭのアドレス指定を引き受けることができる。使用されないデータ線路はクロスオーバスイッチを介してコンテキスト情報として転送することができる。
【００６３】
最終ステップとしてスイッチング装置の第３ステージでは、個々の出力変数を反転することができるようにするために、そして場合によっては小さな論理式簡単化を得るために、生成された出力値はビットごとに排他的論理和関数を介してレジスタコンテントと演算される。従って回路の第３ステージは出力組合せの論理和演算と引き続き可能な個々の出力ビットの反転とからなる。
【００６４】
全体として、本発明に係るスイッチング装置について図７の基本回路図が得られる。
【００６５】
アーキテクチャの論議
本発明の意図は、大きな組合せ論理回路を実装するためのＲＡＭベースアーキテクチャを提供し、またこのアーキテクチャを‐いわば汎用機を格納するためのアプリケーションとして‐ＧＣＡを格納するために提供することである。ＲＡＭ内に任意の関数を格納するために記憶装置内の記憶場所は入力の数に伴って指数的に（そして出力の数に伴って線形に）増加しなければならない。上記事例においてこれは、１２の入力と１２の出力を有する任意の関数は４０９６＊１２ビットに相当する６１４４バイトの記憶場所を持つであろうことを意味する。３２の入力と８の出力の場合、これは既に４ギガバイトの記憶容量となろう。
【００６６】
多ステージネットワークの提案されたアーキテクチャは単に２１１．５バイトのＲＡＭを含み、つまり：
３×項‐ＲＡＭ１６×４        ２４バイト
３×組合せ‐ＲＡＭ６４×４    ９６バイト
３×出力‐ＲＡＭ１６×１２    ７２バイト
クロスオーバスイッチ構成      １８バイト
反転１２×１                  １．５バイト
合計                          ２１１．５バイト
【００６７】
従って主要な利点は、このアーキテクチャがＬＵＴベースアーキテクチャよりもかなりスペース節約的であることにある。その際考慮しなければならない点として、あらゆる関数がこうして表現可能であるのではない。
【００６８】
１つのアプリケーションをこのアーキテクチャにコピーできるようにするために、複数の不可欠な実施形態を満たしておかねばならない。第１条件は、１つの列に存在するさまざまな部分ストリングタームの数が第１ステージのＲＡＭにコピーできることである。これは、これらのＲＡＭがすべての組合せを格納することによって自動的に満たされている（なぜならば、それらがＣＡＭをエミュレートするので）。回路の入力幅だけはアプリケーションにとって十分でなければならない。
【００６９】
第２条件がこれに続く。簡単化後にアプリケーション内に含まれているさまざまな部分ストリングターム組合せの数が符号化可能でなければならない。これは、記憶桁の数が提供されねばならないことを意味する。効率性を推定するためにｍを組合せ論理回路の入力幅とする。これは、完全関数を表現するために２ｍの記憶セルが必要であろうことを意味しよう。
【００７０】
ところでｋがモジュールの並列性（モジュールの数）、２ｓが１モルの容量である場合、アプリケーションの一層効率的な記憶のために不等式
ｋ＊ｓ≦ｍ−１                                                  （３）
が妥当しなければならない。アンダフローが一層明確になればなるほど、実装は一層効率的となる。
【００７１】
条件３は、出力幅が好適に選択されていなければならないことを意味する。
【００７２】
ＧＣＡのアーキテクチャへのコピー
ＧＣＡを本発明に係るアーキテクチャにコピーするために、クロック制御で計算の進展を記憶する記憶素子をなお導入しなければならない。これは、ＧＣＡがＦＳＭのアレイとして定義されていることにその原因があり、それらは一般に同期化されている。ここでは、同期化のためグローバルクロックが受入れられると仮定されている。非グローバルの、特に相互関係のないクロックのすべての実装は本質的問題を生じるであろうが、しかし実際に該当することは希である。
【００７３】
図８は提案された種類の構成可能なアーキテクチャの他の例を示しており、いまや状態を記憶するためのレジスタを装備している。付加的に他の１つのクロスオーバスイッチが介装されており、このスイッチはここではなかんずく計算機用に入出力インタフェースを用意するのに役立つ。これは確かにアーキテクチャの基礎的理解にとって些細なことであるが、しかし実際の動作では不可欠である。なぜならば、計算機が外部端子を備えていなければならないからである。
【００７４】
この例示的アーキテクチャの記憶需要は次のように計算される
８×最小項‐ＲＡＭ２５６×８              ２キロバイト
８×組合せ‐ＲＡＭ６４Ｋ×８              ５１２キロバイト
８×出力ベクトル‐ＲＡＭ２５６×６４      １６キロバイト
２×クロスオーバスイッチ  構成            １キロバイト
反転レジスタ６４×１                      ８バイト
合計                                      ５３１キロバイト
【００７５】
従って、記憶装置の要求条件がいかに少ないかが明らかとなる。２６４＊６４ビット（＝２６７バイト）を有するＲＡＭはいずれにしても製造可能でない。このアーキテクチャにアプリケーションして第１ステージのＲＡＭによって線路が利用されないままとなる場合、これらはコンテキスト情報として利用することができる。１つの応用は、第２ステージのＲＡＭ用に付加的に可能とすることができるようなコンテキスト切換にある。つまり例えば１つのＲＡＭで単に１４のアドレスビットが必要である場合、これらの１４ビットにつついての情報は４倍記憶することができ、つまり４つの異なるコンテキストにある。
【００７６】
図９からは、ＣＧＡを格納するのに適した本発明に係る再構成可能なアーキテクチャの基本構造を読み取ることができる。この構造は図８による構造の一般化である。特にＲＡＭステージ１、２が破線で明確にされている。
【００７７】
参考文献
Rolf Hoffmann, Klaus-Peter Volkmann, Wolfgang Heenes: "Globaler Zellularautomat (GCA): Ein neues massivparallelles Berechnungsmodell", Mitteilungen-Gesellschaft fur Informatik e. V., Parallel-Algorithmen und Rechnerstrukturen, ISSN 0177-0454 Nr. 18, 2001, Seiten 21 - 28
R. K. Brayton et. Al.: ≪Logic Minimization Algorithms for VLSI Synthesis≫, Kluwer Academic Publishers, USA 1984
Mike Trapp: "PLD-design methods migrate existing designs to high-capacity devices", EDN Access, Febr. 1994; http://www.reed-electronics.com/ednmag/archives/1994/021794/04dfl.htm
Wolfgang Heenes, Rolf Hoffmann, Klaus-Peter Volkmann,: "Architekturen fur den globalen Zellularautomaten". 19th PARS Workshop, March 19-21, 2003 Basel; http://www.ra.informatik.tu-darmstadt.de/publikationen/pars03.pdf
【図面の簡単な説明】
【００７８】
【図１】技術の現状によるフォンノイマン型アーキテクチャの基本構造を示す。
【図２】技術の現状によるＰＬＤの全般的構造を示す。
【図３】技術の現状によるミーリー‐オートマトンの形式のＦＳＭの基本構造を示す。
【図４】本発明に係るアーキテクチャの記憶装置構造の１実施例を示す。
【図５】ＲＡＭへのストリングタームのコピーを示し、部分図ａ）は並列ストリングターム、部分図ｂ）はタグＲＡＭへの写素像、部分図ｃ）は従来のＲＡＭへのコピーである。
【図６】本発明に係るアーキテクチャの第１ステージの結果を第２ステージのＲＡＭ組合せにコピーしたものである。
【図７】例［（０、１）12→（０、１）12‐関数］についての最終的アーキテクチャを示す。
【図８】ＧＣＡを格納するための大きな組合せ論理回路を有するスイッチング装置についての本発明に係るアーキテクチャを示す。
【図９】ＣＧＡを格納するための本発明に係る再構成可能なアーキテクチャを示す。
【図１】
2007522571.tif 000004
【図２】
2007522571.tif 000005
【図３】
2007522571.tif 000006
【図４】
2007522571.tif 000007
【図５】
2007522571.tif 000008
【図６】
2007522571.tif 000009
【図７】
2007522571.tif 000010
【図８】
2007522571.tif 000011
【図９】
2007522571.tif 000012
【国際調査報告】
2007522571.tif 000013
2007522571.tif 000014
2007522571.tif 000015
2007522571.tif 000016