(57)【特許請求の範囲】
【請求項１】
第１の速度で入力データを受信するように結合され、受信した該入力データから出力データを生成し、該第１の速度で該出力データを送信するように結合される関数論理の組と、
演算処理する際の前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成し、前記関数論理を制御するように結合されたパルスシーケンサと、を含み、
前記関数論理は、前記パルスシーケンサにより生成された前記自己刻時式パルスシーケンスに応じて駆動することで、前記第１の速度と独立した第２の速度で前記出力データを生成すること
を特徴とするタイミング信号発生装置。
【請求項２】
一組の関数論理とパルスジェネレータを含む装置において自己刻時式アルゴリズム実行のための方法であって、
第１の速度で入力データを受信するステップと、
前記自己刻時式アルゴリズム実行する前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成するステップと、
生成された前記自己刻時式パルスシーケンスに応じて駆動することで前記第１の速度と独立した前記第２の速度で、受信した前記入力データを処理して出力データを生成するステップと、
前記第１の速度で前記出力データを出力するステップと、
を含むことを特徴とするタイミング信号発生方法。
【請求項３】
自己刻時式アルゴリズム実行のための装置であって、
第１の速度で入力データを受信する手段と、
前記自己刻時式アルゴリズム実行する前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成する手段と、
前記自己刻時式パルスシーケンスに応じて駆動することで前記第１の速度と独立した前記第２の速度で、受信した前記入力データを処理して出力データを生成する手段と、
前記第１の速度で前記出力データを出力する手段と、
を含むことを特徴とするタイミング信号発生装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速コンピュータにおけるタイミング信号発生方法及びその装置に関するものである。さらに詳しくは、本発明は、マスタ時刻基準に厳密には同期していない自己刻時式アルゴリズム実行のための方法並びにその装置に関する。
【０００２】
【従来の技術】
高速コンピュータ・システムでは、各種の必要なスイッチング動作を同期させるためのマスタ時刻基準が必要とされる。ある種のコンピュータ・システムでは、均一な１つのクロック信号が数個のクロック増幅器で再バッファリングされてシステム内で使用されるメモリ装置全部のタイミング同期の唯一の供給源として動作する。別のシステムでは、数個の更に異なる位相のクロック信号を用いて別々のメモリ装置の組を駆動している場合があるが、全て従来的にはシステム内のマスタ時刻基準に同期されている。
【０００３】
複数のクロック信号を使用する場合、異なるメモリ装置が相対的に異なる速度でデータストリームまたは命令シーケンスによって状態を切り換えるかまたは変更する。このような複数のクロック回路は、メモリ装置間の関数論理がもっとも速い速度で周回できるように設計されることが多い。パイプライン化システムでは、たとえば、関数論理はメモリ装置間で分担され、目標とする最小実行時間のシステム設計上の制約が関数論理またはメモリ装置要素の個数の共同制約的増加なしに維持されている。
【０００４】
ある種のパイプライン化システムでは、高速で幾つかのパイプライン機能ユニットの内部順位を維持しつつ機能ユニットの入出力境界がシステム内の残りのパイプライン機能ユニットと互換性のある低い速度で維持されるように超ハーモニッククロックが使用されている。従来技術の方法は「マイクロパイプライン化」として周知でありパイプライン化機能ユニットの内部メモリ装置がパイプラインの入力ポートおよび出力ポートに見られる低速のストリーム速度と同期してパイプラインのマイクロ演算をインタリーブ化する厳密に同期した超ハーモニッククロック信号を有するような装置を含む。残念ながら、マイクロパイプライン化の欠点としては、それぞれのメモリ装置から実際に受信したトリガ信号に最低限の歪みを保証するため低歪み木構造として数個のクロック増幅器を必要とし、また一元的なタイミング間隔を要求することが含まれる。つまり、一元的タイミング間隔の内部で充分に動作できる程短い伝播遅延を有していないマイクロパイプライン内部の論理要素の組は、対応させるのが難しい。更に、ＲＬＤ内部の伝播遅延が機能単位ごとに変化し、半包括的マイクロパイプラインクロックを有することを困難にしているため、マイクロパイプライン化の概念は再設定可能な論理装置（ＲＬＤ）たとえばフィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）等を用いて実装するのが特に困難である。
【０００５】
【発明が解決しようとする課題】
従来、ＲＬＤが各種論理設計の実施に使用される場合、実際のＲＬＤ相互接続を生成するために使用する「ツール」の大半はレジスタ転送言語（ＲＴＬ）パラダイムを使用している。このようなパラダイムはＲＬＤ内部の関数論理およびメモリ装置を駆動する独立したマスタ刻時基準クロックの存在に強く依存している。このようなパラダイムはさらに、ＲＬＤ内部の論理設計の物理的実装が論理設計の全体的タイミング性能およびシリコン資源要求に依存することを無視している。実際に、ＲＬＤツール製造メーカではＲＬＤの物理特性に左右されないことを論理設計パラダイムの「利点」として主張している。
【０００６】
他の高速コンピュータ・システムはマスタ時刻基準に同期したくロックシステムに付随する前述の困難を回避するため、コンピュータの機能タスクを一組の非同期刻時によるサブタスクに分割する試みを行なっている。残念ながら、既存の非同期論理設計も多くの制約を有している。これはたとえば、演算タスクを完了する際に「完了信号」を生成する必要があること、可変または未知の完了時刻を有すること、外部クロック要素を必要とすること、データ依存の完了時刻を有すること、外部回路と非同期的にインタフェースすること、外部回路とのデータ交換をコヒーレントでない位相にすること、外部クロック回路へ加えられた遅延がさらにシステム全体を複雑化すること、同期外部回路の内部に埋め込むことが難しいこと、システム全体の性能を外部クロック回路ネットワークに結合することがある。
【０００７】
必要なのは、可能な限り高速なパイプライン周波数を実現する上で固有の負担を、一元的なタイミング間隔を用いるシステム内部でできるかぎり短いステージ環遅延の制約を有する同時的な負担から分離するような自己刻時式アルゴリムの実行のための装置ならびに方法である。
【０００８】
【課題を解決するための手段】
請求項１記載の発明は、第１の速度で入力データを受信するように結合され、受信した該入力データから出力データを生成し、該第１の速度で該出力データを送信するように結合される関数論理の組と、演算処理する際の前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成し、前記関数論理を制御するように結合されたパルスシーケンサと、を含み、前記関数論理は、前記パルスシーケンサにより生成された前記自己刻時式パルスシーケンスに応じて駆動することで、前記第１の速度と独立した第２の速度で前記出力データを生成することを特徴とする。
【０００９】
そして、前記関数論理の組は予測される実行時間を有することと、前記第２の速度は前記予測実行時間に基づく最大速度であることを特徴とする。
【００１０】
前記関数論理と前記パルスシーケンサは一組のハードウェア資源の組の内部に配置されて前記ハードウェア資源の動作パラメータ変動に対して同期的に応答することを特徴とする。
【００１１】
前記パルスシーケンサは自己刻時式発振を生成する遅延ユニットを含むことを特徴とする。
【００１２】
前記遅延ユニットは直列接続した一組の論理装置を含み、それぞれの論理装置は予測可能な伝播遅延を有することを特徴とする。
【００１３】
前記直列接続の一組の論理装置は一組のキャリー論理要素を含むことを特徴とする。
【００１４】
前記一組のキャリー論理要素は再設定可能な論理装置内にキャリー伝播論理を含むことを特徴とする。
【００１５】
前記パルスシーケンサはさらに一組のクロック信号を生成するシーケンスゲート論理を含み、前記シーケンスゲート論理は遅延ユニット出力信号を受信するように結合されまた関数論理へ前記一組のクロック信号を供給して前記第２の速度を提供するように結合されることを特徴とする。
【００１６】
前記パルスシーケンサはさらにパルスカウント信号を生成するパルスカウンタを含み前記パルスカウンタは前記遅延ユニット出力信号を受信するように結合されることを特徴とする。
【００１７】
前記パルスシーケンサはさらに開始パルスを生成して前記遅延ユニットの動作を開始するための開始論理を含むことを特徴とする。
【００１８】
前記関数論理は乗算器を含み、前記乗算器は  被乗数を受信するように結合されたマルチプレクサと、乗数と前記被乗数内部のビットのサブセットを受信するように結合されて一組の部分積を生成する部分積ジェネレータと、前記一組の部分積を受信するように結合されて部分積の和を生成する部分積加算器と、前記部分積の和を受信するように結合されて部分積の和を積算して積を生成する積積算器とを含み、前記乗数は前記遅延ユニットにより生成された前記自己刻時式発振に応じて制御されることを特徴とする。
【００１９】
再設定可能な論理装置内のパルスシーケンサであって、前記パルスシーケンサは自己刻時式発振を生成するように結合された一組のキャリー論理素子を含むことを特徴とする。
【００２１】
請求項２記載の発明は、一組の関数論理とパルスジェネレータを含む装置において自己刻時式アルゴリズム実行のための方法であって、第１の速度で入力データを受信するステップと、前記自己刻時式アルゴリズム実行する前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成するステップと、生成された前記自己刻時式パルスシーケンスに応じて駆動することで前記第１の速度と独立した前記第２の速度で、受信した前記入力データを処理して出力データを生成するステップと、前記第１の速度で前記出力データを出力するステップと、を含むことを特徴とする。
【００２２】
また、前記パルスシーケンスを生成する前記ステップは前記一組の関数論理に関連する実行時間に従う最大速度で実行されることを特徴とする。
【００２３】
前記入力データを受信するステップは基準クロックと同期して実行され、前記生成ステップは前記基準クロックとは独立した自己刻時式速度で実行され、前記出力ステップは前記基準クロックと同期して実行されることを特徴とする。
【００２４】
前記生成ステップは、開始信号に応答して自己刻時式発振を生成するステップと、停止信号を受信するまで前記自己刻時式発振を維持するステップとを含むことを特徴とする。
【００２５】
前記生成ステップは、さらにパルスカウント信号を生成するステップと、前記自己刻時式発振の周期に対応する速度で前記入力データの処理を制御する一組の制御信号を生成するステップとを含むことを特徴とする。
【００２６】
前記処理ステップは、さらに乗数と被乗数内部のビットのサブセットを乗算することで一組の部分積を生成するサブステップと、前記一組の部分積を加算することにより部分積の和を生成するサブステップと、前記部分積の和を直前の部分積の和に積算するサブステップと、乗算積が生成されるまで前記処理ステップ内のそれぞれのサブステップを反復するサブステップとを含むことを特徴とする。
【００２７】
請求項３記載の発明は、自己刻時式アルゴリズム実行のための装置であって、第１の速度で入力データを受信する手段と、前記自己刻時式アルゴリズム実行する前記関数論理の物理的特性により決定された自己刻時式パルスシーケンスを生成する手段と、前記自己刻時式パルスシーケンスに応じて駆動することで前記第１の速度と独立した前記第２の速度で、受信した前記入力データを処理して出力データを生成する手段と、前記第１の速度で前記出力データを出力する手段と、を含むことを特徴とする。
【００２８】
前記生成手段は、自己刻時式発振を生成する手段を含むことを特徴とする。
【００２９】
【発明の実施の形態】
本発明の実施の一形態を図面に基づいて説明する。本発明は、高速コンピュータにおけるタイミング信号発生であり、特に、自己刻時式アルゴリズム実行のための方法並びに装置である。
【００３０】
本発明の装置は望ましくは関数論理セットと、基準クロック入力と、パルスシーケンサとを含む。関数論理セットは基準クロック入力に受信した基準クロックと同期して入力データを受信し、関数論理セットの物理的特性にしたがってパルスシーケンサによって決まる最大速度で入力データについてのアルゴリズム計算を実行し、出力データを生成し、基準クロックと同期して出力データを送信する。パルスシーケンサにより設定される最大速度は基準クロックに依存しない。
【００３１】
本発明の方法は望ましくは、基準クロックと同期して入力データを関数論理セットに転送する段階と、機能的論理セットのアルゴリズム実行時間に依存するが基準クロックには依存しない速度で関数論理セットを駆動するための最大速度パルスシーケンスを生成する段階と、最大速度パルスシーケンスに応答して機能論理セットから出力データを生成する段階と、基準クロックに同期して関数論理からの出力データを送信する段階とを含む。
【００３２】
本発明は自己刻時式アルゴリズム実行のための装置ならびに方法である。選択したアルゴリズムを実行するように設計した関数論理セットと遅延ユニットを対にすることで、本発明では第１に他の関数論理セットを駆動する全ての基準クロックと独立してできる限り高速に選択したアルゴリズムを実行する。つまり、周知のタイミング装置およびその方法とは対称的に、アルゴリズムを実施する全ての機能論理セットのタイミング特性は基準クロックの速度に制限されたり依存する必要がない。第２に、一組の自己刻時式パルスの生成に応じてアルゴリズムを実施する関数論理セットに基づいた自己刻時速度でデータ演算する。第３に、他の関数論理セットで受信すべき特定の既知の時刻にデータを出力する。その結果、本発明の装置ならびに方法はひとつの関数論理セットを他の関数論理セットまたは基準クロックの動作速度と無関係な速度で動作させることができるため、ハードウェア設計を簡略化しつつ最大限可能なアルゴリズム実行速度を維持することが可能で、従来技術に対して特に有利である。
【００３３】
本発明はもっとも基本的な物理構造において関数論理セットを観察することによりこれらの利点を実現する。本発明はレジスタ転送論理（ＲＴＬ）パラダイムに依存しない。本発明はむしろ、アルゴリズムを実行する関数論理セットに独自のタイミング回路を合わせ、関数論理セットが最大限可能な速度で演算できるようにする。つまり、本発明はアルゴリズムの実行だけではなくタイミング速度のインクリメンタルな調停者としてシリコン資源をみなすことでシリコン資源内部の論理設計を実施するための新規なパラダイムを定義する。従来技術では、第１に従来技術のシステムにおける論理実装の時間的インパクトがメモリ装置だけに見られる副作用に依存すること、第２に、関数論理セットが従来技術においてデータを通過するための通路として機械的に見られていたが、実際には関数論理セットは関数論理セットの全体の実行時間を減少するためのチャンスとみなすことができること、第３に、ＲＴＬパラダイムは関数論理とメモリ装置の間の有用または一体的相互接続の効果の分析に反対すること、第４に、従来技術における関数論理の強調はアルゴリズム実装のあらゆる水準で個別のタイミング回路の生成のための局部的フィードバックを含む設計に強く反対すること等から新規のパラダイムに注意を払っていない。
【００３４】
本発明はザイリンクスＸＣ４０００シリーズ（ザイリンクス社、カリフォルニア州サンノゼ）フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などの再設定可能な論理装置（ＲＬＤ）において実施するのが好ましい。ＲＬＤは一組の設定可能な論理ブロック（ＣＬＢ）から構成される。それぞれのＣＬＢは望ましくは少くともひとつの関数ジェネレータと１つまたはそれ以上のキャリー論理素子を含む。当業者には周知のように、ＦＰＧＡの内部構造は設定データセットまたは設定ビット列を用いて動的に再設定することができる。何らかの任意のＣＬＢ内部で、特定の論理関数が設定ビット列にしたがって関数ジェネレータ経由で生成される。それぞれの関数ジェネレータは特定の安定した信号伝播遅延を有する。たとえば、ザイリンクスＸＣ４０００シリーズＣＬＢでは、第１と第２の関数ジェネレータ（「Ｆ」および「Ｇ」型）のそれぞれが約４．５ナノ秒の伝播遅延を有し、第３の関数ジェネレータ（「Ｈ」型）は約２．５ナノ秒の伝播遅延を有する。キャリー論理素子は典型的に非常に小さく安定した伝播遅延を有するように設計されたキャリー伝播遅延を含むことが当業者には理解されよう。ザイリンクスＸＣ４０００シリーズＦＰＧＡ内部のキャリー伝播論理は１．５ナノ秒の伝播遅延を有する。
【００３５】
本発明はＲＬＤ内部の資源を組み合わせることにより多段階のフィードバックを作成し各種内部伝播遅延を発生する。このフィードバックはＲＬＤ内部の１つまたはそれ以上の関数論理セットを駆動するための個別のタイミング回路を作成するために使用する。好ましくは、本発明は「純粋な」遅延にもっぱら依存するかわりに「内部」遅延を使用する。内部遅延は伝播が最小パルス幅を必要とするような遅延と定義され、一方純粋遅延は伝播遅延が基本的にパルス幅とは無関係な遅延である。有利にも、内部遅延は安定し、充分に制御される遅延である。本発明はＲＬＤ内部で実施する必要がなく、他の従来周知の論理装置から構成できることは当業者には理解されよう。
【００３６】
本明細書ではＸビット×Ｙビット乗算を実施してＰビットの積を得る（ここでＸ、Ｙ、Ｐは整数）ような関数論理セットを開示するが、関数論理セットは広範囲の別のアルゴリズムを実行するように設計できることも当業者には理解されよう。このような別のアルゴリズムには、何らかの種類の算術、論理、グラフィック、ワードプロセシング、信号処理、またはネットワーク演算を実行するための段階を含むことができる。たとえば、本発明はＲＬＤの内部ランダム・アクセス・メモリ（ＲＡＭ）の効率的な使用のためのタイミング信号、複数ポートレジスタファイルまたはＲＬＤ内部のデータパス配線（たとえばＦＰＧＡ内部のクロスバ交換器）を提供するために使用できる。
【００３７】
明瞭にするため、以下図７から図８では３２ビット積を得る典型的な１６ビット×１６ビット乗算での詳細を示す。しかし、本発明は１６ビット以上または以下の乗算を実施できることが当業者には理解されよう。また、本明細書の残りの部分では、以下に説明する信号およびビットは好ましくは２つの状態、論理値「１」と論理値「０」だけを有する。本発明の要素は状態遷移の立ち上がり端にだけ（即ち論理値「０」から論理値「１」への遷移）応答するように説明するが、ＲＬＤは立ち上がり端だけまたは立ち上がりおよび立ち下がり端両方の状態遷移に応答するように設定できることが当業者には理解されよう。
【００３８】
図１は、自己刻時式アルゴリズム実行のための装置２０の好適実施例のブロック図である。装置２０は入力バッファ２２、関数論理２４、出力バッファ２６、同期状態マシン３０、パルスシーケンサ３４を含む。入力バッファ２２は、外部回路（図示していない）が線２９の入力イネーブル信号を状態「１」に保持する度に外部回路から線１９経由で受信したＸビットの被乗数またはＹビット乗数どちらかを読み込み、他方線２９で基準クロック信号を受信する従来周知の装置である。基準クロックは、好ましくは位相同期可変周波数クロックおよびメッセージングと題する米国特許出願第０８／５０１，９７０号に記載されているクロック発生機構を用いて実装する。何らかの従来周知のクロック生成手段が代わりに基準クロックを提供できることは当業者には理解されよう。
【００３９】
入力バッファ２２は関数論理２４へＸビット被乗数を線２１経由で、またＹビット乗数を線２３経由で出力する。関数論理２４は被乗数と乗数を受信し、乗算アルゴリズムにしたがってパルスシーケンサ３４に依存するが基準クロックには依存しないタイミング速度でこれらを乗算する。関数論理２４が乗算アルゴリズムを実行するのに必要な時間はアルゴリズム実行時間である。関数論理２４内部の伝播遅延がアルゴリズム実行時間を決定し、関数論理を構成する一組の論理装置に基づいて従来は計算されている。関数論理２４は線２５を介して出力バッファ２６へＰビット積を出力する。関数論理２４の詳細は図７を参照して後述する。出力バッファ２６は従来周知の形式で、外部回路が出力イネーブル信号を論理値「１」に保持する度にＰビット積を読み込み外部回路へ線２７経由で出力し、同時に線２８経由で基準クロックを受信する。
【００４０】
同期状態マシン３０は従来技術で周知の種類で線２８の基準クロックが２回トリガし外部クロックが同時に線２９の入力イネーブル信号を論理値「１」状態に保持した後、線３２の状態信号９０（図１２参照）を論理値「１」に遷移させる。
【００４１】
同期状態マシン３０は従来技術で周知の種類で線２８の基準クロックが２回トリガし外部クロックが同時に線２９の入力イネーブル信号を論理値「１」状態に保持した後、線３２の開始信号９０（図１２参照）を論理値「１」に遷移させる。同期状態マシン３０は２回基準クロックがトグルするのを待って開始信号９０を論理値「１」に設定し、入力バッファ２２が外部回路からＸビット被乗数とＹビット乗数を両方とも順次受信できるようにする。
【００４２】
パルスシーケンサ３４は同期状態マシン３０からの線３２の開始信号９０をモニタし、開始信号９０が論理値「１」に遷移した時に線３３から関数論理２４へ一組の信号を生成して送出する。パルスシーケンサ３４の動作の詳細と出力する信号の組については図２を参照して後述する。装置２０が物理装置で実施されるかまたは任意の物理装置の制約にしたがって設計されると、関数論理２４の伝播遅延とパルスシーケンサ３４のタイミング速度が分かるようになる。つまり、出力データは入力データが入力バッファ２２に刻時された時点から周知の時間内に出力バッファ２６に存在することになる。この周知の時間は装置温度と装置のエージングの関数として物理装置の通常の性能変動により僅かに変動する。しかし、後述するようにパルスシーケンサ３４は関数論理２４の内蔵部分とするのが好ましいことから、パルスシーケンサ３４と関数論理２４の両方が同じ温度と時間的変化を受けることになる。その結果、パルスシーケンサ３４と関数論理２４は高度に一致し、パルスシーケンサ３４は関数論理２４をオーバクロックしたりアンダークロックすることがない。
【００４３】
図２を参照すると、本発明のパルスシーケンサ３４の好適実施例のブロック図が示してある。パルスシーケンサ３４は開始論理３６と、遅延ユニット３８と、パルスカウンタ４０と、シーケンスゲート論理４２とを含む。パルスシーケンサ３４のパルス速度、パルス持続時間、パルス周期（もしあれば）も駆動する関数論理２４について最適化するのが望ましい。パルスシーケンサ３４は関数論理２４に類似の論理装置を使用して前述したように温度とエージングの影響に同様に応答するように実装するのも好ましい。以下では関数論理２４の組全体を駆動するパルスシーケンサ３４をひとつだけ説明するが、複数のパルスシーケンサ３４を使用して、関数論理２４動作中に異なる速度で異なる時刻に関数論理２４の特定のサブセットを駆動するように設計することもできる。このような別の実施例において、多数のパルスシーケンサ３４がそれぞれ開始パルス１０４を受信するのが好ましい。
【００４４】
開始信号９０が線３２で論理値「１」に遷移すると、開始論理３６は線４３にリセット（１）パルス１０５（図１２参照）と線３５の開始パルスを生成する。リセット（１）パルス１０５はパルスカウンタ４０を初期化する。開始論理３６の詳細については図３を参照して後述する。遅延ユニット３８は開始パルスを受信し、第１の既知の遅延後に線３９（図１２参照）にフィードバック信号１３２を生成する。遅延ユニット３８の詳細は図４を参照して後述する。開始論理３６は線３７経由でフィードバック信号１３２を受信して線３５に次の開始パルスを生成し、これにより自己刻時発振を発生させる。自己刻時発振の周期は開始論理３６、遅延ユニット３８、線３７に付随する伝播遅延で定義される。好ましくは、開始論理３６と遅延ユニット３８はＲＬＤ内部に物理的に配置して線３７に付随する伝播遅延が最小になるようにする。ザイリンクスＸＣ４０００シリーズＦＰＧＡを用いる典型的実施例では、従来の配置方針を用いてＣＬＢ配置を定義した場合線３７に付随する遅延は１．７ないし２．２ナノ秒の範囲である。パルスカウンタ４０から線４１で停止信号を受信すると、開始論理３６は線３５の開始パルス生成を停止し、自己刻時発振を停止する。
【００４５】
パルスカウンタ４０は線３９で遅延ユニット出力信号１３３を受信し、これに応じて線４４のパルスカウントと線４１の停止信号を生成する。パルスカウントは線４３経由で初期パルスカウント（１が望ましい）にリセットされ、遅延ユニット出力信号１３３がトグルする度にインクリメントする。パルスカウントが最大パルスカウント数に達すると、パルスカウンタ４０は線４１に停止信号を生成する。線４４は最大パルスカウントを伝送するのに充分な多数の２進ビット線から構成される。たとえば、１６ビット×１６ビット乗算では、パルスカウントは後述するような理由から８状態を必要とする。つまり、線４４は少くとも３本の２進ビット線から構成する必要があり、本明細書ではＭＵＸ（０）９２（最下位ビット（ＬＳＢ））、ＭＵＸ（１）９４、およびＭＵＸ（２）９６（最上位ビット（ＭＳＢ））（図１２参照）とする。パルスカウンタ４０の詳細は図５を参照して後述する。
【００４６】
シーケンスゲート論理４２は線４４でパルスカウントを受信し、また遅延ユニット出力信号１３３を線３９で受信する。これに応じて、シーケンスゲート論理４２はリセット（２）信号９７（図１２参照）を線４５に生成し、部分積加算器クロック信号（ＰＰＳ−ＣＬＫ）９８（図１２参照）、積アキュムレータクロック（１）信号（ＰＡ−ＣＬＫ（１）９９（図１２参照）を線４７に、線４８にはＰＡ−ＣＬＫ（２）１００、線４９にはＰＡ−ＣＬＫ（３）１０１を生成する。それぞれのＣＬＫ９８、９９、１００、１０１はパルスカウントと遅延ユニット出力信号１３３から導出した方形波信号が好ましい。図１に図示したように、パルスカウント信号４４、リセット（２）信号９７、ＰＰＳ−ＣＬＫ４６、ＰＡ−ＣＬＫ４７、４８、４９は互いに関数論理２４への線３３の信号出力の組として機能する。しかし自己刻時パラダイムによれば、線３３の信号出力の組のいずれも線２８の基準クロックと意図的に同期しない。シーケンスゲート論理４２の詳細は図６を参照して後述する。
【００４７】
図３を参照すると、本発明の開始論理３６の好適実施例のブロック図が示してある。開始論理３６は図３に図示したように動作的に結合した一組の論理装置を含む。ザイリンクスＸＣ４０００シリーズＦＰＧＡを用いて実現した典型的な実施例では、開始論理３６は従来のザイリンクスライブラリ素子ＦＤＳ、ＡＮＤ２Ｂ１、ＡＮＤ２Ｂ０およびＯＲ２Ｂ１を含む。
【００４８】
図４を参照すると、本発明の遅延ユニット３８の好適実施例のブロック図が示してある。遅延ユニット３８はＲＬＤ内部に実施するのが好ましくｎを整数とする一組のｎ個のＣＬＢ１３８、１４４、１５０、１５４の内部のキャリー論理素子から構成される。好ましくは、それぞれのキャリー論理素子は高速キャリー伝播回路を含む。遅延ユニット３８はさらにｎ個のＣＬＢの組の内部に関数ジェネレータのサブセットを含み、遅延ユニット３８と遅延ユニット３８外部の論理即ち開始論理３６、パルスカウンタ４０、シーケンスゲート論理４２の間の信号配線を簡略化する。図示した実施例において、遅延ユニット３８はキャリーイン信号の検証および発生にそれぞれ対応する「ＥＸＡＭＩＮＥ  ＣＩ」および「ＦＯＲＣＥ  ＣＩ」命令を用いてザイリンクスＸＣ４０００シリーズＦＰＧＡ内に実装される。
【００４９】
それぞれのＣＬＢ１３８、１４４、１５０、１５４に使用する論理は、遅延ユニット３８に周知の遅延（ザイリンクスＸＣ４０００キャリー論理素子で１．５ナノ秒、またザイリンクスＸＣ４０００Ｆ型関数ジェネレータで４．５ナノ秒）を付加する。遅延ユニット３８の動作周波数は直列接続のキャリー論理素子の個数を増加または減少することにより変化させるのが好ましい。好適実施例において、最大速度自己刻時式パルスシーケンサ３４が所望される。遅延ユニット３８を含むＣＬＢ１３８、１４４、１５０、１５４の個数は関数論理２４のもっとも遅い部分に依存することになる。結果として、関数論理２４のもっとも遅い部分は実行に「ｔ」秒かかり、「ｔ」／２（即ち周期の半分）に等しい合計遅延を有する「ｎ個」のＣＬＢは遅延ユニット３８を含むのが好ましい。また、ＲＬＤのリアルタイムで再プログラムする機能のため、遅延ユニット３８の遅延は関数論理２４の処理演算の途中で動的に変化することがある。これにより、第１の関数論理２４の組の演算は第１の自己刻時速度で実行され、第２の関数論理２４の組のその他の演算は第２の自己刻時速度で実行され、以下同様に続けることができる。
【００５０】
第１のＣＬＢ１３８内部で、関数ジェネレータ（１）１４０は線３５に開始パルスを受信し、パルスをキャリー論理素子（１）１３９に渡す。キャリー論理素子（１）１３９はキャリーアウト線１４２から第２のＣＬＢ１４４へ信号を渡す。第２のＣＬＢ１４４内部では、キャリー論理素子（２）１４５がパルスを受信して関数ジェネレータ（２）１４６へ渡し、さらにキャリーアウト線１４８から第３のＣＬＢ１５０へパルスを転送する。パルスを関数ジェネレータ（２）１４６へ渡すことでその時点で遅延ユニット３８からパルスを「タップする」ことができ、線３９の遅延ユニット出力信号１３３とすることができる。本明細書では、「タップ」は遅延ユニット３８外部への信号の配送を容易にする遅延ユニット３８内部の結合として定義する。実装する関数論理２４の組によっては「タップ」は他にも遅延ユニット３８内部の別のロケーションで発生したり、またはいくつかの位置に発生することがある。線３９がタップする遅延ユニット３８内部の正確な位置は、線３３にパルスシーケンサによって生成される信号が、図１を参照して説明したような装置２０の動作を開始する外部回路（図示していない）に対して位相的に整列するように選択するのが好ましい。
【００５１】
第３のＣＬＢ１５０内部では、キャリー論理素子（３）１５１がパルスを受信しこれを次のＣＬＢ内部のキャリー論理素子へ渡す動作を行ない、パルスが「ｎ番目」のＣＬＢ１５４内部のキャリー論理素子（ｎ）へ渡されるまで同じことが繰り返される。第３のＣＬＢ１５０と「ｎ番目」のＣＬＢ１５４の間のＣＬＢは同じ構造が望ましく、第３のＣＬＢ１５０と同じインタフェースを有するのが望ましい。第３のＣＬＢ１５０内部で、第３のＣＬＢ１５０が遅延ユニット３８外部の宛先へパルスを配送するためにタップしていないので遅延ユニット３８の動作に関数ジェネレータ（３）１５２は必要とされない。つまり、関数ジェネレータ（３）１５２は有利にも関数論理２４の動作の一部を実装するために使用される。
【００５２】
ｎ番目のＣＬＢ内部では、キャリー論理素子（ｎ）１５５がパルスを受信し、パルスを反転させて反転パルスをフィードバック信号フィードバック信号１３２として線３７に出力する関数ジェネレータ（ｎ）１５６に渡す。このパルス反転を経由して、論理値「１」と論理値「０」の間で自己刻時式発振回路が遷移する。パルスは関数ジェネレータ（１）１４０が代わりに反転させられることが当業者には理解されよう。
【００５３】
遅延ユニット３８の動作周波数は直列に接続したキャリー論理素子の個数を増減する（即ち「ｎ」の値を変化させる）ことで変化し得る。別の実施例において「ｎ」はゼロでも良く、開始パルス、フィードバック信号１３２、遅延ユニット出力信号１３３が同じ信号になる。さらに別の実施例において、遅延ユニット３８の動作周波数は１つまたはそれ以上の関数ジェネレータを介してさらなる信号を配送することにより変化できる。さらに別の実施例において、遅延ユニット３８の動作周波数はＲＬＤ内部にあって充分に限定された遅延特性を有する信号配送資源を用いることで変更または調整することができる。再設定不可能な装置において、個別の素子が既知の最大信号伝播遅延を有するような論理を用いて遅延ユニット３８を実施し得ることは当業者には理解されよう。
【００５４】
ここで図５を参照すると、本発明のパルスカウンタ４０の好適実施例のブロック図が図示してある。パルスカウンタ４０は図５に図示したように動作的に結合された一組の論理装置１６０、１６２、１６４（望ましくはライブラリ要素であるＲＯＭ１６Ｘ１、ＦＤＲ、ＡＮＤ３Ｂ３を用いてザイリンクスＸＣ４０００シリーズＦＰＧＡで作成される）を含む。論理装置１６０は論理装置１６２で相互に結合してパルスカウントを実装する。論理装置１６２の現在の状態符号Ｑ３、Ｑ２、Ｑ１、Ｑ０はパルスカウントを発生させ、それぞれが停止信号１３４に対応するように使用する。パルスカウンタ４０は線４３でリセット（１）パルス１０５を受信するまでインクリメントする。論理装置１６０に記憶する符号は以下の現在状態／次状態の表から生成する。
【００５５】
0003784476.tif 000002
図６を参照すると、本発明のシーケンスゲート論理４２の好適実施例のブロック図が図示してある。シーケンスゲート論理４２は図６に図示したように動作的に接続した一組の論理装置（望ましくは望ましくはライブラリ要素Ｄ３＿８Ｅ、ＡＮＤ２Ｂ１、ＦＤ、ＦＤ＿１、ＮＯＲ２、ＯＲ８、ＯＲ７を用いてザイリンクスＸＣ４０００シリーズＦＰＧＡで作成される）シーケンスゲート論理４２は図６に図示したようなグリッチ保安回路１７０を用いて８つの状態を復号する。復号は時間的に線４４のパルスカウントの順序である。最後のパルスカウント状態（即ち（０，０，０））は正確に一度に復号される。ＣＬＫ４６、４７、４８、４８は一組のグリッチ保安回路１７０の出力の「論理和」を取ることで生成する。シーケンスゲート論理４２の別の実施例で論理状態でコーダのド・モルガン化を用いて結線ＯＲを結線ＡＮＤゲートで置き換えることがＦＰＧＡ設計の当業者には理解されよう。好適なシーケンスゲート論理４２は負のエッジでトリガされるフリップフロップと正のエッジでトリガされるフリップフロップを同数含み、同じ刻時がなされるフリップフロップどうしを連結するようなＣＬＢパッケージごとに非常に高効率のデュアルフリップフロップ方針を実行する。
【００５６】
図７を参照すると、本発明の関数論理２４の好適実施例のブロック図が図示してある。関数論理２４はマルチプレクサ（ＭＵＸ）５０、部分積ジェネレータ（ＰＰＧ）５２、部分積加算器（ＰＰＳ）５４、積アキュムレータ（ＰＡ）５６から構成される。マルチプレクサ５０はＸビット被乗数を線２１に受信し、詳細は図８を参照して後述するように、Ｓビット被乗数サブセットを線４４のパルスカウントに応じて出力する。部分積ジェネレータ５２は線２３のＹビット乗数とＳビット被乗数サブセットを乗算して、後述の図９を参照して詳細に説明するように一組の部分積を部分積加算器５４に出力する。部分積加算器５４は部分積の組を組み合わせて図１０を参照して詳細に後述するように線４６の部分積加算器クロック信号（ＰＰＳ−ＣＬＫ）９８に応答して積アキュムレータ５６へ部分積の和を出力する。積アキュムレータ５６は開始論理３６からの線４５のリセット（２）パルス１０７（図１２参照）を受信し、これに応じて内部フリップフロップ（ＦＦ）をゼロにリセットする。リセット（２）パルス１０７の受信までは線２５に直前のＰビット積が残っている。積アキュムレータ５６は部分積の和を積の積算ビットのサブセットへ加算することで積の積算を生成し、図１１を参照して詳細に後述するように線４７、４８、４９のＰＡ−ＣＬＫ（１，２，３）９９、１００、１０１（図１２参照）に応答して線２５にＰビット積を出力する。完全なＸビット×Ｙビットの乗算は各Ｓビット被乗数サブセットがＹビット乗数で乗算され積アキュムレータ５６に積算された後で関数論理２４で実行される。
【００５７】
図８を参照すると、関数論理２４内部のマルチプレクサ５０の好適実施例のブロック図が図示してある。ＭＵＸ５０は第１のＭＵＸ５８と第２のＭＵＸ６０を含む。それぞれのＭＵＸ５８、６０は線２１経由で入力バッファ２２へ接続され、それぞれがＸビット被乗数の半分を受信するようにしてある。第１のＭＵＸ５８は偶数の被乗数ビット（即ち１６ビット被乗数では２の０乗、２の２乗、２の４乗、．．．２の１４乗まで）を受信し、一方第２のＭＵＸ６０は奇数の被乗数ビット（即ち１６ビット被乗数では２の１乗、２の３乗、．．．２の１５乗まで）を受信する。それぞれのＭＵＸ５８、６０は線４４でパルスカウントを受信する。Ｘビット×Ｙビット乗算の途中で、パルスカウントは初期パルスカウントから最大パルスカウントを含むカウントまでインクリメントされる。１６ビット被乗数の場合、初期パルスカウントは線４４で（０，０，１）に対応するのが望ましく、ここで「１」はＬＳＢ、また最大パルスカウントは（０，０，０）に対応するのが望ましい。パルスカウントは望ましくは（０，０，１）から（０，１，０）、（０，１，１）、（１，０，０）、（１，０，１）、（１，１，０）、（１，１，１）さらに（０，０，０）へ遷移する。
【００５８】
第１と第２のＭＵＸ５８、６０はＳビットの被乗数サブセットを部分積ジェネレータ５２へ出力する。つまり２ビット被乗数のサブセット（２のｉ乗と２のｉ＋１乗）が部分積ジェネレータ５２へ送信される。ここでビット２のｉ乗は第１のＭＵＸ５８から選択され、２のｉ＋１乗は第２のＭＵＸ６０から選択される。
【００５９】
１６ビット乗算では、「Ｓ」は「２」に等しく「ｉ」はパルスカウントが（０，０，１）から（０，０，０）の範囲として０から１４までの範囲であるのが望ましい。
【００６０】
図９を参照すると、関数論理内部の部分積ジェネレータ５２の好適実施例のブロック図が図示してある。部分積ジェネレータ５２は部分積乗算器（ＰＰＭ）５１の第１の組とＰＰＭ５３の第２の組から構成され、これらの入力は第１と第２のＭＵＸ５８、６０および線２３のＹビット乗数からＳビット被乗数のサブセットを受信するように接続される。第１と第２の組のＰＰＭ５１、５３は部分積加算器５４に接続される。１６ビット×１６ビット乗算では、ＰＰＭ５１、５３のそれぞれの組は並列に動作する２ビット×２ビットＰＰＭを含み、合計３２ビットがそれぞれの乗算演算後に部分積加算器５４へ送信される。線２３の１６ビット乗算器からのそれぞれの２ビット乗算器対は８個のＰＰＭのひとつに結線されそれぞれの部分積乗算演算の間一定に保持される。それぞれのパルスカウントで、ひとつの２ビット被乗数サブセット（即ち２のｉ乗と２のｉ＋１乗）が８個のＰＰＭのそれぞれに結線されてパルスカウントが１に設定された時には第１の２ビット被乗数の対（２の０乗と２の１乗）から始まりパルスカウントが０に設定された時に最後の２ビット被乗数の対（２の１４乗と２の１５乗）で終わる。図９で明らかにするために示してあるように、第１と第２のＰＰＭの組５１、５３からの２つの１６ビット部分積のコラム位置は、従来技術で周知のように、部分積加算器５４でビット加算するので垂直方向に整列する。ビット２の０乗は最下位ビット（ＬＳＢ）でありビット２の１７乗は最上位ビット（ＭＳＢ）である。１６ビット×１６ビット部分積生成について説明したが、同じ説明がＸビット×Ｙビット部分積生成の一般化した場合にも同様に適用されることは当業者に理解されよう。
【００６１】
図１０には、関数論理２４内の部分積加算器５４の好適実施例のブロック図が示してある。部分積加算器５４はＰＰＳ加算器６４、ＰＰＳインクリメント加算器６６、一組のＰＰＳフリップフロップ６８を含む。部分積加算器５４は部分積ジェネレータ５２で生成された２つの部分積を受信するように結合される。部分積加算器５４は２つの部分積を加算して部分積の和を生成する。１６ビット×１６ビットの乗算の場合には、第１の組のＰＰＭ５１からの２つのＬＳＢ（２の０乗〜と２の１乗）が直接ＰＰＳフリップフロップ６８で受信され、ＰＰＳ加算器６４は第１と第２の組のＰＰＭ５１、５３の両方からの１４ビット（２の２乗〜２の１５乗）を加算する。ＰＰＳインクリメント加算器６６は第２の組のＰＰＭ５３から２つのＭＳＢ（２の１６乗〜２の１７乗）、また１４ビットＰＰＳ加算器６４からの桁上げ（キャリーアウト）を受信し、１８ビット部分積の和（２の０乗〜２の１７乗）が生成され出力される。加算から得られた部分積の和は線４６の部分積加算器クロック信号（ＰＰＳ−ＣＬＫ）９８のトグルに応答してＰＰＳフリップフロップ６８に記憶される。
【００６２】
図１１を参照すると、関数論理２４の積アキュムレータ５６の好適実施例のブロック図が示してある。積アキュムレータ５６は、部分積加算器５４から部分積の和を受信して積算を実行するように結合されたＰＡ加算器７０と、ＰＡインクリメント加算器７１と、最終的にＰビット積を格納するための一組のＰＡフリップフロップの組７２，７４，７６，７８，８０，８２，８４，８６，８８を含む。１６ビット×１６ビット乗算の場合では、ＰＡ加算器７０は１６ビット加算器であり、ＰＡインクリメント加算器７１は２ビットインクリメント加算器であり、ＰＡフリップフロップの組７２，７４，７６，７８，８０，８２，８４，８６，８８は、３２ビットの積（ｐの０乗からｐの３１乗、ここでｐの０乗がＬＳＢ、ｐの３１乗がＭＳＢ）を記憶するための第１のフリップフロップの組７２、第２のフリップフロップの組７４、第３のフリップフロップの組７６、第４のフリップフロップの組７８、第５のフリップフロップの組８０、第６のフリップフロップの組８２、第７のフリップフロップの組８４、第８のフリップフロップの組８６、第９のフリップフロップの組８８を含む。部分積加算器５４から受信した第１の部分積の和からの２つのＬＳＢ（２の０乗〜２の１乗）は線４７のＰＡ−ＣＬＫ（１）信号９９の昇端に応じて第２のフリップフロップの組７４に格納され、３２ビット積の２つのＬＳＢ（ｐの０乗〜ｐの１乗）になる。１６ビット積積算のサブセット（ＰＡ加算器７０とＰＡインクリメント加算器７１の出力からのビット２の１乗から２の１７乗）は線４８の積アキュムレータクロック（２）信号１００の昇端に応答して第１のフリップフロップ７２に格納される。ＰＡ加算器７０は部分積加算器５４から受信したそれぞれの部分積の和の２の０乗から２の１５乗までのビットを加算して積の積算を発生する（ＰＡ加算器７０とＰＡインクリメント加算器７１の出力からのビット２の０乗から２の１７乗）。それぞれの積の積算の２の２乗から２の１７乗ビットまでは第１のフリップフロップの組７２へフィードバックされる積の積算サブセットとなり，２の０乗と２の１乗ビットの積の積算は線４９のＰＡ−ＣＬＫ（３）１０１の昇端に応答して第３から第９のフリップフロップの組７６，７８，８０，８２，８４，８６，８８のそれぞれの積の積算後に順次シフトされる。ひとつのＰＡ−ＣＬＫ（１）信号９９がトグルした後、ｐの０乗とｐの１乗ビットが第２のフリップフロップの組７４に記憶され，８つのＰＡ−ＣＬＫ（２）１００がトグルした後ｐの１６乗からｐの３１乗までのビットが第１のフリップフロップの組７２に記憶され、７つのＰＡ−ＣＬＫ（３）１０１がトグルした後、ｐの２乗とｐの３乗のビットが第９のフリップフロップの組８８に記憶され、ｐの４乗とｐの５乗のビットが第８のフリップフロップの組８６に記憶され、ｐの６乗とｐの７乗のビットが第７のフリップフロップの組８４に記憶され、ｐの８乗とｐの９乗のビットが第６のフリップフロップの組８２に記憶され、ｐの１０乗とｐの１１乗のビットが第５のフリップフロップの組８０に記憶され、ｐの１２乗とｐの１３乗のビットが第４のフリップフロップの組７８に記憶され、ｐの１４乗とｐの１５乗のビットが���３のフリップフロップの組７６に記憶される。３２ビット積（ｐの０乗からｐの３１乗のビット）が線２５から出力バッファ２６へ送出される。
【００６３】
ここで図１２を参照すると、本発明の動作の好適タイミング図８９が示してある。図１２に示してあるタイミング波形は理想的なものであるから、論理作用は何らかの状態遷移の瞬間に発生するものと考える。タイミング図８９は開始信号９０と、Ｑ開始信号１２８、開始パルス信号１３０、フィードバック信号１３２、遅延ユニット出力信号１３３、停止信号１３４、リセット（１）信号９１、ＭＵＸ（０）信号９２、ＭＵＸ（１）信号９４、ＭＵＸ（２）信号９６、ＰＰＳ−ＣＬＫ信号９８、リセット（２）信号９７、ＰＡ−ＣＬＫ（１）信号９９、ＰＡ−ＣＬＫ（２）信号１００、ＰＡ−ＣＬＫ（３）信号１０１、積信号１０２、第１の開始信号１０４、次の開始信号１０６、第１のＰＰＳ−ＣＬＫ信号１０８、第１のＰＡ−ＣＬＫ（１）信号１０９、第１のＰＡ−ＣＬＫ（２）信号１１０、第１のＰＡ−ＣＬＫ（３）信号１１２、積計算時間１１４を含む。第１の開始信号１０４は図２に図示したように線３２でパルスシーケンサ３４が受信する。第１の開始信号１０４に応答して、開始論理３６は、リセット（１）パルス１０５を線４３から送出しＭＵＸ（０）信号９２、ＭＵＸ（１）信号９４、ＭＵＸ（２）信号９６をそれぞれ線４４からマルチプレクサ５０へ送信することにより、ＭＵＸ（０）信号９２（ＬＳＢ）、ＭＵＸ（１）信号９４、ＭＵＸ（２）信号９６（ＭＳＢ）をそれぞれ初期化する。これに応答して、マルチプレクサ５０は前述のように１６ビット×１６ビット乗算で第１の２ビット被乗数の対（２の０乗と２の１乗）を選択する。シーケンスゲート論理４２は第１の１８ビット部分積の和がＰＰＳフリップフロップ６８入力に現われるまで部分積加算器５４への第１のＰＰＳ−ＣＬＫ信号１０８送出を遅延させる。第１の１８ビット部分積の和がＰＰＳフリップフロップ６８に記憶されてから、ＭＵＸ（０）信号９２、ＭＵＸ（１）信号９４、ＭＵＸ（２）信号９６が次の１８ビット部分積の和の準備として次の状態（即ち（０，１，０））にインクリメントされる。シーケンスゲート論理４２も第１の１８ビット部分積の和が第２のフリップフロップの組７４入力に現われるまで第１のＰＡ−ＣＬＫ（１）信号１０９送出を遅延させる。ＰＡ−ＣＬＫ（１）信号１０９が線４７に送出される直前に、開始論理３６がリセット（２）パルス１０７を線４５に生成して直前のＰビットの積信号１０２をクリアする。ＰＡ−ＣＬＫ（１）信号９９は１６ビット×１６ビット乗算演算が完了するごとに１回づつトグルする。線４８の第１のＰＡ−ＣＬＫ（２）信号１１０は第１のフリップフロップの組７２に出現した後でのみ生成され、この後ＰＡ−ＣＬＫ（２）１００は第１のフリップフロップの組７２に次の１６ビット積算のサブセットが現われるごとにトグルする。ＰＡ−ＣＬＫ（２）１００は１６ビット×１６ビット乗算演算が完了する度に８回トグルする。線４９の第１のＰＡ−ＣＬＫ（３）信号１１２は第２の１８ビット積の積算が第３のフリップフロップの組７６の入力に出現した後でのみ生成され、この後次の１８ビット積の積算が第１のフリップフロップの組７２の入力に出現する度にＰＡ−ＣＬＫ（３）信号１０１がトグルする。ＰＡ−ＣＬＫ（３）信号１０１は完全な１６ビット×１６���ット乗算演算の度ごとに７回トグルする。本発明を実施する物理装置に存在する既知の伝播遅延により、積信号１０２は積計算時間１１４内で計算されることが分かる。その結果、次の開始信号１０６がパルスシーケンサ３４に送出できるようにする第１の開始信号１０４のあとのもっとも速い時間は積信号１０２が安定した後である．１６ビット×１６ビット乗算を説明したが、Ｘビット×Ｙビット乗算を同様の方法で実行できることは当業者には理解されよう。
【００６４】
ここで図１３を参照すると、本発明で実行する１６ビット×１６ビット乗算のための好適な部分積加算のマトリクスが図示してある。１６ビット×１６ビット乗算では、部分積加算器５４は８回の加算を行ない積アキュムレータ５６は７回の積算を行ない、最後に前述したような３２ビット積が線２５から出力バッファ２６へ出力される。マトリクスの上部では、３２ビット積のそれぞれのビットについて１カラムが図示してあり、ＬＳＢは２の０乗、またＭＳＢは２の３１乗である。「Ｉ、II、III、IV、Ｖ、VI、VII、VIII」と標識してあるマトリクスの部分を参照すると、部分積ジェネレータ５２内部の８個の部分積乗算器６２の配列が図示してある。「Ｉ」の部分では１６ビット被乗数の２の０乗および２の１乗ビットが１６ビット乗数と乗算される。「II」の部分では１６ビット被乗数の２の２乗および２の３乗ビットが１６ビット乗数と乗算される。このように「VIII」の部分で１６ビット被乗数の２の１４乗および２の１５乗ビットが１６ビット乗数と乗算されるまで続く。積アキュムレータ５６はマトリクス内に示された方法で８つの部分全てを加算し，３２ビットの積を得る。
【００６５】
図１４を参照すると、本発明にしたがって実行される８ビット×８ビット乗算での好適な部分積加算のマトリクスが図示してある．８ビット×８ビット乗算では、部分積加算器５４は４回の加算を行ない積アキュムレータ５６が３回の積算を行ない、前述のように線２５から出力バッファ２６へ１６ビット積が出力されるように設計できる。マトリクス上部では、１６ビット積のそれぞれのビットについてひとつのカラムが図示してあり、ＬＳＢは２の０乗、ＭＳＢは２の１５乗である。「Ｉ、II、III、IV」と標識してあるマトリクスの部分を参照すると、部分積ジェネレータ５２内部のここでは４個の部分積乗算器６２の配列が図示してある。「Ｉ」の部分では８ビット被乗数の２の０乗ビットと２の１乗ビットが８ビット乗数と乗算される。「II」の部分では８ビット被乗数の２の２乗と２の３乗ビットが８ビット乗数と乗算される。このように部分「IV」で８ビット被乗数の２の６乗と２の７乗ビットが８ビット乗数と乗算されるまで続く。積アキュムレータ５６はマトリクス内に示したような方法で４つの部分を加算し，１６ビット積を得る。
【００６６】
図１５をここで参照すると、自己刻時式アルゴリズム実行のための好適な方法のフローチャートが示してある。好適な方法はステップ２００から始まり、線２９の入力イネーブル信号が論理値「１」に設定される時に基準クロックからのトグルにより、前述したような方法で入力バッファ２２が線２１と線２３の入力データを基準クロックのトグルと同期して関数論理２４へ転送する。次に、ステップ２０２では、線３２の開始信号９０の論理値「０」から論理値「１」へのトグルに応答して、パルスシーケンサ３４が線３３に最大速度パルスシーケンスを発生し、関数論理２４についてのアルゴリズム実行時間に依存するが線の基準クロック２８とは無関係な速度で関数論理２４を駆動する。ステップ２０２は図１６で詳細に説明する。ステップ２０４では、関数論理２４が線３３の最大速度パルスシーケンスに応答して線２５に出力データを生成する。ステップ２０４は図１２で詳細に説明する。ステップ２０６では、関数論理２４から線２５を介して出力バッファ２６へ、線２８の基準クロックからのトグルに同期しまたこれに応答して転送され、同時に前述のように線３１の出力イネーブルが論理値「１」に設定される。ステップ２０６の後、好適な方法は終了する。
【００６７】
図１６をここで参照すると、パルスシーケンス（図１０のステップ２０２）を生成するための好適な方法のフローチャートが示してある。好適な方法はステップ２５０から始まり、開始論理３６が線３２の開始信号９０の開始と線４１の停止信号を監視する。ステップ２５２で、開始信号９０が論理値「１」に遷移し停止信号が論理値「０」のままだと、本方法はステップ２５４へ進み、それ以外の場合にはステップ２５０へ戻る。ステップ２５４では、開始論理３６がパルスカウンタ４０を前述のように初期化する。ステップ２５５では開始論理３６が前述のように遅延ユニット３８へ開始パルスを送信する。次にステップ２５６では、前述のように遅延ユニット出力信号１３３に応答して、パルスカウンタ４０がパルスカウント信号（即ち１６ビット×１６ビット乗算の場合にはＭＵＸ（０）信号９２、ＭＵＸ（１）信号９４、ＭＵＸ（２）信号９６）をインクリメントする。遅延ユニット出力信号１３３がタップされる遅延ユニット３８内部の位置は、パルスシーケンサ３４のタイミングパルスが装置２０に結合した外部回路と位相整列するように変化できる。ステップ２５８では、パルスカウント信号に応じて、前述の方法でシーケンスゲート論理４２がＰＰＳ−ＣＬＫ信号９８とＰＡ−ＣＬＫ（１）信号９９、ＰＡ−ＣＬＫ（２）信号１００、ＰＡ−ＣＬＫ（３）信号１０１を生成する。ステップ２６０では、パルスカウント信号が最大のパルスカウント信号と等しい場合、本方法はステップ２６２に進み、それ以外ではステップ２５６に戻る。ステップ２６２では、パルスカウンタ４０が線４１の停止信号を論理値「１」に設定して遅延ユニット３８への開始パルス送信を停止する。ステップ２６２で好適な方法は終了する。
【００６８】
ここで図１７を参照すると、パルスシーケンス（図１７のステップ２０４）に応じて出力データを生成するための好適な方法のフローチャートが示してある。
【００６９】
好適な方法はステップ３００から始まり、前述のようにマルチプレクサ５０がＸビット被乗数を入力し、部分積ジェネレータ５２がＹビット乗数を入力し、開始論理３６が部分積和と積の積算をゼロに初期化する。ステップ３０２では、前述のように、マルチプレクサ５０は次のＳビット被乗数サブセットを選択する。ステップ３０４では部分積ジェネレータ５２が現在のＳビット被乗数サブセット（即ち、現在のサブセットとはステップ３０２で選択された次のサブセット）をＹビット乗数で乗算して前述のように部分積加算器５４へ送信する部分積を生成する。ステップ３０６では、部分積加算器５４が部分積の和を生成して前述した方法で積アキュムレータ５６へ送信する。ステップ３０８では、積アキュムレータ５６が部分積の和を前述のように積の積算に加算する。ステップ３１０では、次のＳビット被乗数サブセットをさらにＹビット乗数と乗算しなければならない場合、本方法はステップ３０２に戻り、それ以外の場合にはステップ３１２へ進む。ステップ３１２では、積アキュムレータ５６がＰビット積を出力バッファ２６へ出力する。ステップ３１２の後好適な方法は終了する。
【００７０】
本発明は計算システムの状況において使用するのが望ましい。従来技術において、特定のアルゴリズムの高速実装を提供するように設計された回路は多数の回路層から構成されていた。それぞれの回路層は一組の信号を受信し、特定の組の演算を実行し、一組の結果を基準クロックと同期して出力する。信号はひとつの回路層から別の回路層へ転送される。このような従来技術の回路設計では多数の回路層が必要とされることが多く、多量のハードウェア資源の使用が望まれなくとも必要となる。従来技術に対し、本発明は最小数のハードウェア資源を最大の自己刻時速度で最大限に再利用し、結果を生成するアルゴリズムを実現するものである。つまり、開始信号の受信から停止信号の生成に続けて結果を発生するまで同じハードウェア資源の組み合わせを繰り返し使用する。本発明は従来技術の高速回路で必要とされるよりも明らかに少ないハードウェア資源を用い、何らかの有意な結果生成速度のペナルティに苦しめられることなくアルゴリズムを実装するための方法を提供する。これは本発明の１つまたはそれ以上の版をＲＬＤに実装する際に特に有利である。
【００７１】
前述した本発明は現行の論理回路設計に対してその他多くの利点を得られることが当業者に理解されよう。本発明は現在の非同期論理回路設計の観点で特に有利である。たとえば、本発明は演算タスクの完了時に「完了信号」の生成を必要としないこと、既知の予測可能な完了時間を有すること、外部刻時要素を必要とせず、かわりにそれ自身の内蔵パルスシーケンサによるタイミング素子を有すること、データに依存しない完了時間を有すること、外部回路と同期的にインタフェースできること、外部回路とのデータ交換でコヒーレントな位相が実現できること、タイミング素子に遅延を付加する場合追加の局部的な回路の複雑さしか追加されないこと、また外部回路のシステム全体にではなく局部的な一組の回路だけに性能が影響することなどである。
【００７２】
本発明はいくつかの好適実施例を参照して説明したが、各種の変更を提供できることが当業者には理解されよう。このような変化は本発明の別の実施例を提供できる。たとえば、遅延ユニット３８はＲＬＤ設定に続けて連続的にパルスをリサイクルするように設計することができ、これによって開始論理３６を排除することができよう。このような実施例では、ＲＳフリップフロップによってマルチプレクサから遅延ユニット出力信号をパルスカウンタ４０へ、また開始信号に応じてシーケンスゲート論理４２へ渡すようにできる。関数論理が自己刻時式乗算回路の場合に制限されないことが当業者には理解されよう。関数論理は自己刻時式除算回路、自己刻時式コンボルバ回路、自己刻時式信号プロセッサ等を含みこれらに制限されない関数を提供できる。好適実施例に対する変化および変更は本発明により提供されるものであって、後述の請求項によってのみ制限される。
【００７３】
【発明の効果】
本発明は上述のように構成したので、選択したアルゴリズムを実行するように設計した関数論理とパルスシーケンサを対にすることで、まず、第１に関数論理は、他の関数論理を駆動する全ての基準クロックと独立してできる限り高速に選択したアルゴリズムを実行する。つまり、周知のタイミング装置およびその方法とは対称的に、関数論理の物理的特性は基準クロックの速度に制限されたり依存する必要がない。第２に、生成された自己刻時式パルスシーケンスに応じて駆動する関数論理は、第１の速度と独立した第２の速度で演算する。第３に、他の関数論理で受信すべき特定の既知の時刻にデータを出力する。その結果、本発明の装置ならびに方法はひとつの関数論理を他の関数論理または基準クロックの動作速度と無関係な速度で動作させることができるため、ハードウェア設計を簡略化しつつ最大限可能なアルゴリズム実行速度を維持することが可能で、従来技術に対して特に有利である。
【図面の簡単な説明】
【図１】本発明の実施の一形態を示す自己刻時式アルゴリズム実行のための装置の好適実施例のブロック図である。
【図２】本発明のパルスシーケンサの好適実施例のブロック図である。
【図３】パルスシーケンサ内部の開始論理の好適実施例のブロック図である。
【図４】パルスシーケンサ内部の遅延ユニットの好適実施例のブロック図である。
【図５】パルスシーケンサ内部のパルスカウンタの好適実施例のブロック図である。
【図６】パルスシーケンサ内部のシーケンスゲート論理の好適実施例のブロック図である。
【図７】本発明の関数論理の好適実施例のブロック図である。
【図８】関数論理内部のマルチプレクサの好適実施例のブロック図である。
【図９】関数論理内部の部分積ジェネレータの好適実施例のブロック図である。
【図１０】関数論理内部の部分積加算器の好適実施例のブロック図である。
【図１１】関数論理内部の積アキュムレータの好適実施例のブロック図である。
【図１２】本発明の動作を示す好適タイミング図である。
【図１３】本発明の１６ビット×１６ビット乗算のための好適部分積加算を示すマトリクスである。
【図１４】本発明の８ビット×８ビット乗算のための部分積加算を示すマトリクスである。
【図１５】自己刻時式アルゴリズム実行のための好適な方法のフローチャートである。
【図１６】パルスシーケンスを生成するための好適な方法のフローチャートである。
【図１７】パルスシーケンスに応じて出力データを生成するための好適な方法のフローチャートである。
【符号の説明】
２４      関数論理
２８      基準クロック
【図１】
0003784476.tif 000003
【図２】
0003784476.tif 000004
【図３】
0003784476.tif 000005
【図４】
0003784476.tif 000006
【図５】
0003784476.tif 000007
【図６】
0003784476.tif 000008
【図７】
0003784476.tif 000009
【図８】
0003784476.tif 000010
【図９】
0003784476.tif 000011
【図１０】
0003784476.tif 000012
【図１１】
0003784476.tif 000013
【図１２】
0003784476.tif 000014
【図１３】
0003784476.tif 000015
【図１４】
0003784476.tif 000016
【図１５】
0003784476.tif 000017
【図１６】
0003784476.tif 000018
【図１７】
0003784476.tif 000019