(57)【特許請求の範囲】
【請求項１】
ラッチレスダイナミック非同期デジタルパイプライン回路であって、
第１のプリチャージ制御信号および第１の評価制御信号だけに応答して、第１のプリチャージフェーズ、それに続く第１の評価フェーズ、およびそれに続く第１の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成された第１の処理ステージであって、この第１の処理ステージの出力は、前記第１の隔離フェーズのときはその入力における変化から隔離され、前記第１のプリチャージ制御信号は前記第１の評価制御信号から切り離されるような第１の処理ステージと、
第２の処理ステージのフェーズを示す遷移信号に応答して、前記第１のプリチャージ制御信号および第１の評価制御信号を前記第１の処理ステージに提供するよう構成された第１のステージコントローラと、
第２のプリチャージ制御信号および第２の評価制御信号だけに応答して、第２のプリチャージフェーズ、それに続く第２の評価フェーズ、およびそれに続く第２の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成された第２の処理ステージと、
前記第２の評価ステージの終了に基づきアサートされる前記第２の処理ステージの前記フェーズを示す前記遷移信号を提供するよう構成されている終了ジェネレータと、を含み、
前記第２の処理ステージの前記ステージを示す前記遷移信号が前記第１のステージのコントローラによって受信されることによって、前記第１の処理ステージが、前記第２の処理ステージの前記フェーズを示す前期遷移信号がアサートされたとき、前記プリチャージフェーズ、前記評価フェーズ、および前記隔離フェーズを通って循環させることを可能にするように、１つの相互接続が、前記第１の処理ステージと前記第２の処理ステージとの間に設けられた、
ラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項２】
請求項１に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージの前記フェーズを示す第１の遷移信号を前記第１のステージコントローラへ提供するよう構成されている第１の終了ジェネレータをも含む、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項３】
請求項２に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をアサートし、前記第１のプリチャージ制御信号をデアサートするとき、前記第１の処理ステージが前記第１の評価フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項４】
請求項２に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をデアサートし、前記第１のプリチャージ制御信号をデアサートするとき、前記第１の処理ステージが前記第１の隔離フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項５】
請求項２に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をデアサートし、前記第１のプリチャージ制御信号がデアサートされたとき、前記第１の処理ステージが前記第１のプリチャージフェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項６】
請求項２に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージが前記評価フェーズに入り、その前のステージが有効な入力を前記第１の処理ステージに提供したとき、前記第１の遷移信号がアサートされる、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項７】
請求項２に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージが前記プリチャージステージに入ったとき、前記第１の遷移信号がデアサートされる、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項８】
ラッチレスダイナミック非同期デジタルパイプライン回路であって、
第１のプリチャージ制御信号および第１の評価制御信号だけに応答して、第１のプリチャージフェーズ、それに続く第１の評価フェーズ、およびそれに続く第１の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成された第１の処理ステージと、
前記第１のプリチャージ制御信号および前記第１の評価制御信号を前記第１の処理ステージに提供し、遷移信号に応答する第１のステージコントローラであって、この第１のプリチャージ制御信号は前記第１の評価制御信号から隔離されるような第１のステージコントローラと、
第２のプリチャージフェーズ、それに続く第２の評価フェーズ、およびそれに続く第２の隔離フェーズから構成されるフェーズのサイクルを通って駆動される第２の処理ステージであって、この第２の処理ステージの前記出力は、前記第２の隔離フェーズのときはその前記入力の変化から隔離され、そのフェーズを示す遷移信号を前記第１のステージコントローラに提供するような第２の処理ステージとを含む、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項９】
請求項８に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージの前記フェーズを示す第１の遷移信号を前記第１のステージコントローラに提供するよう構成されている第１の終了ジェネレータをも含む、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１０】
請求項９に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をアサートし、前記第１のプリチャージ制御信号をデアサートするとき、前記第１の処理ステージが前記第１の評価フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１１】
請求項９に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をデアサートし、前記第１のプリチャージ制御信号をデアサートするとき、前記第１の処理ステージが前記第１の隔離フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１２】
請求項９に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１のステージコントローラが前記第１の評価制御信号をデアサートし、前記第１のプリチャージ制御信号がアサートされるとき、前記第１の処理ステージが前記第１のプリチャージフェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１３】
請求項９に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージが前記評価フェーズに入り、前段のステージが有効な入力を前記第１の処理ステージに提供したとき、前記第１の遷移信号がアサートされる、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１４】
請求項９に記載のラッチレスダイナミック非同期デジタルパイプライン回路において、
前記第１の処理ステージが前記プリチャージステージに入ったとき、前記遷移信号がデアサートされる、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項１５】
プリチャージ制御信号および評価制御信号を提供するよう構成され、前記プリチャージ制御信号は前記評価制御信号から隔離されているようなステージコントローラと、
入力および出力を持つ機能ブロックであって、前記ステージコントローラからの前記プリチャージ制御信号および前記評価制御信号だけに応答して、プリチャージフェーズ、それに続く評価フェーズ、およびそれに続く隔離フェーズから構成されるフェーズのサイクルを通って駆動され、前記プリチャージフェーズに戻るように構成され、前記隔離フェーズのとき、前記出力がその入力の変化から隔離されているような機能ブロックと、
を含むラッチレスダイナミックロジックを持つラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージ。
【請求項１６】
請求項１５に記載のラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージにおいて、
前記第１の評価制御信号がアサートされ、前記第１のプリチャージ制御信号がデアサートされるとき、前記第１の処理ステージが前記第１の評価フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージ。
【請求項１７】
請求項１５に記載のラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージにおいて、
前記第１の評価制御信号がデアサートされ、前記第１のプリチャージ制御信号がデアサートされるとき、前記第１の処理ステージが前記第１の隔離フェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージ。
【請求項１８】
請求項１５に記載のラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージにおいて、
前記第１評価制御信号がデアサートされ、前記第１プリチャージ制御信号がアサートされるとき、前記第１処理ステージが前記第１プリチャージフェーズに入る、
ことを特徴とするラッチレスダイナミック非同期デジタルパイプライン回路の処理ステージ。
【請求項１９】
ラッチレスダイナミック非同期デジタルパイプライン回路であって、
第１の処理ステージと、第２の処理ステージとを含み、
前記第１の処理ステージは、
第１のプリチャージ制御信号により制御されるプルアップスタック、第１の評価制御信号により制御されるプルダウンスタック、第１のデータ入力、および第１のデータ出力を含む、第１の機能ブロックであって、第１のプリチャージ制御信号および第１の評価制御信号だけに応答して、第１のプリチャージフェーズ、それに続く第１の評価フェーズ、それに続く第１の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成され、前記第１のプリチャージ制御信号および第２のプリチャージ制御信号が前記第１の隔離フェーズにおいてデアサートされるとき前記第１のデータ出力は前記第１のデータ入力の変化から隔離されるような第１の機能ブロックと、
前記第１のプリチャージ制御信号、前記第１の評価制御信号、および有効な入力信号を入力として受信するよう構成された非同期Ｃ素子を含み、この非同期Ｃ素子は、前記第１の評価制御信号および前記有効なデータ入力がアサートされるときにアサートされ、かつ、前記第１のプリチャージ制御信号がアサートされるときにデアサートされるような第１の遷移信号を生成する、第１の終了ジェネレータと、
前記第１の遷移信号を入力として受信し、第１の遅延した遷移信号を出力として生成するよう構成された複数のインバータを含む第１のマッチドディレイ素子と、
前記第１のマッチドディレイ素子から前記第１の遅延した遷移信号を入力として受信し、前記第１の評価制御信号を出力として生成するよう構成されたインバータと、
第２の処理ステージから入力として前記第１の評価制御信号および第２の遷移信号を受信し、前記第１の遅延した遷移信号がデアサートされるときにデアサートされ、および、前記第１の遷移信号がアサートされ並びに前記第２の制御信号がアサートされるときにアサートされるような、中間制御信号を生成するよう構成された非同期Ｃ素子と、入力として、前記中間制御信号、前記第１の遅延した遷移信号、および前記第２の遷移信号を受信し、前記第１のプリチャージ制御信号を生成するよう構成されたＮＡＮＤゲートと、を含む第１のステージコントローラとを含み、
前記第２の処理ステージは、
第２のプリチャージ制御信号により制御されるプルアップスタックと、第２の評価制御信号により制御されるプルダウンスタックと、第２のデータ入力と第２のデータ出力とを含む第２の機能ブロックであって、第２のプリチャージ制御信号および第２の評価制御信号だけに応答して、第２のプリチャージフェーズ、それに続く第２の評価フェーズ、およびそれに続く第２の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成され、前記第２のプリチャージ制御信号および前記第２の評価制御信号が前記第２の隔離フェーズにおいてデアサートされるときに前記第２のデータ出力が前記第２のデータ入力の変化から隔離されるような、第２の機能ブロックと、
前記第２のプリチャージ制御信号、前記第２の評価制御信号、および前記第１の遅延した遷移信号を入力として受信するよう構成された非同期Ｃ素子であって、前記第２の評価制御信号および前記有効なデータ入力がアサートされるときにはアサートされ、および、前記第２のプリチャージ制御信号がアサートされるときにはデアサートされるような第２の遷移信号を生成する非同期Ｃ素子を含む第２の終了ジェネレータと、
前記第２の遷移信号を入力として受信し、第２の遅延した遷移信号を出力として生成するよう構成されている複数のインバータを含む第２のマッチドディレイ素子と、
前記第２のマッチドディレイ素子から入力として前記第２の遅延した遷移信号を受信し、前記第２の評価制御信号を出力として生成するよう構成されたインバータ、前記第２の遅延した遷移信号および第３の遷移信号を環境から入力として受信し、前記第２の遅延した遷移信号がデアサートされるときにはデアサートされ、および、前期第１の遅延した遷移信号がアサートされ並びに前記第２の遷移信号がアサートされるときにはアサートされるような、中間制御信号を生成するよう構成された非同期Ｃ素子、および、前記第２の遅延した遷移信号と前記第２の遷移信号と前記中間制御信号とを入力として受信し前記第２のプリチャージ信号を出力として生成するよう構成されたＮＡＮＤゲートを含む、第２のステージコントローラとを含む、
ラッチレスダイナミック非同期デジタルパイプライン回路。
【請求項２０】
ラッチレスダイナミック非同期パイプラインを用いたラッチレスダイナミック非同期デジタルパイプライン処理の方法であって、
前記方法は、
第１のプリチャージ制御信号および第１の評価制御信号だけに応答して、第１のプリチャージフェーズ、それに続く第１の評価フェーズ、およびそれに続く第１の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成された第１の処理ステージを提供するステップと、
第２のプリチャージ制御信号および第２の評価制御信号だけに応答して、第２のプリチャージフェーズ、それに続く第２の評価フェーズ、およびそれに続く第２の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成された第２の処理ステージであって、第２の隔離フェーズのときにはこの第２の処理ステージの前記出力がその入力の変化から隔離されるような第２の処理ステージを提供するステップと、
前記第１の処理ステージで前記第１の評価フェーズを実行するステップと、
前記第２の処理ステージで前記第２の評価フェーズを実行し、前記第２の処理ステージの前記フェーズを示す遷移信号を前記第１のステージコントローラに提供するステップと、
前記第２の処理ステージが、前記第２の評価フェーズおよび前記第２の隔離フェーズのうち１つに留まる間に、前記第１の処理フェーズの前記第１の隔離フェーズ、前記第１の評価フェーズ、および前記プリチャージフェーズを実行するステップであって、その結果第１の処理フェーズおよび第２の処理フェーズがプリチャージフェーズによる分離を伴わずに２つの別個のトークンを格納するようなステップと、
を含むラッチレスダイナミック非同期デジタルパイプライン処理の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、非同期パイプライン処理用の回路および方法に関するものであり、特に、高バッファおよび高スループットをもたらすパイプラインに関するものである。
関連出願へのクロスリファレンス
本願は、米国仮特許出願、題名「高速ＤＳＰアプリケーション用の微細（fine-grain）パイプライン化した非同期加算器」（出願番号60/199,439号、2000年4月25日出願）の優先権を主張するものであり、また、参照によってその全体を本明細書に合体させるものとする。
【０００２】
関連技術の背景
数ギガヘルツのスループットの能力を持つパイプライン設計の需要が増加してきた。幾つかの新規な同期パイプラインが、これらの高速アプリケーションのために開発されてきた。例えば、ウェーブパイプラインでは、データの複数の波が２つのラッチの間で伝搬される。しかしながら、このアプローチでは、経路遅延（データ依存性の遅延を含む）のバランスの正確さのために、アーキテクチャのレベルからレイアウトのレベルに至るまで、多大な努力を要するが、このようなシステムでもなお、プロセス、温度、および電圧の変化に対して高い脆弱性が残っている。その他の挑戦的な同期アプローチには、クロック遅延ドミノ、スキュー耐性（skew-tolerant）ドミノ、およびセルフリセット回路が挙げられる。これらのアプローチは、複雑なタイミング制約を必要とし、柔軟性に欠ける。さらに、これらの回路用の高速グローバルクロック分配には大きな課題が残されている。
【０００３】
グローバルクロッキングをローカルハンドシェイキング（local handshaking）で置換する非同期設計は、高速設計をより実現可能なものにする潜在能力を持つ。非同期パイプラインは、高速クロックの分配に関連する問題、例えば無駄なクロックパワーおよびクロックスキューの管理などの問題を回避する。さらに、グローバルクロックの欠如は、パイプラインのデータアイテムの幾つかが長い間にわたり変化することを可能にするため、パイプラインに自然な柔軟性を与える。最後に、この非同期コンポーネントの固有の柔軟性は、パイプラインが異なる速度で作動する変化した環境をインターフェイスすることを可能にする。即ち、非同期パイプラインスタイルはシステムオンチップの設計に有用である。
【０００４】
ある従来技術のパイプラインは、ウィリアムのps0デュアルレイル非同期パイプラインである（T. Williams, Self-Timed Rings and Their Application to Division, Ph. D. Thesis, Stanford University, June 1991; T. Williams et al., “A Zero-Overhead Self Timed 160ns 54b CMOS Driver, IEEE JSSC, 26(11):1651-1661, Nov. 1991）。図１は、ウィリアムのps0パイプライン10を図示する。各パイプラインステージ12a、12b、12cは、デュアルレイル機能ブロック14a、14b、14cおよび終了検出器16a、16b、16cから構成される。これらの終了検出器は、接続されている機能ブロックの出力部でデータの有効性またはデータがないことを指し示す。
【０００５】
それぞれの機能ブロック14a、14b、14cは、ダイナミックロジックを使用して実現される。各ステージのプリチャージ／評価の制御入力、すなわちＰＣは、次のステージの終了検出器の出力と結合されている。例えば、ステージ12aのプリチャージ／評価の制御入力部、すなわちＰＣは、ステージ12bの終了検出器16bと結合され、ライン18a上の機能ブロック14aに渡される。その入力がリセットされたときでさえ、プリチャージロジックブロックはそのデータ出力を保持することができるため、暗黙のラッチ（implicit latch）の機能性も提供することができる。従って、ps0ステージは明示のラッチ（explicit latch）を持たない。図２（ａ）は、例えば、如何にしてデュアルレイルＡＮＤゲートがダイナミックロジックで実現されるのか、即ち一対のデュアルレイル、f1およびf0が、デュアルレイル入力a1a0およびb1b0のＡＮＤを実現する。
【０００６】
各ステージ12a、12b、12cにある終了検出器16a、16b、16cはそれぞれ、プリチャージおよび演算のたびに終了の信号を出す。データ出力の有効性或いは無効性は、それぞれの個別のビットのために２つのレイルを「ＯＲ」することによりチェックされ、その後、Ｃ素子を使用して全ての結果を組み合わせる（図２（a）を参照されたい。）。Ｃ素子は、基本的な非同期状態保持素子である。より詳細には、Ｃ素子のｎ入力の出力は、全ての入力がハイのときはハイであり、全ての入力がローのときはローであり、それ以外の場合はその以前の値を保持する。これは、典型的には、プルアップおよびプルダウンの一連のスタックの付属したＣＭＯＳゲートと出力のインバータ（状態を保持するために装着された弱いフィードバックインバータが付属している）によって実現される。
【０００７】
ウィリアムのps0デュアルレイルパイプラインのためのパイプライン制御のシーケンスは、以下のとおりである。ステージＮ＋１が評価を完了したときステージＮはプリチャージされる。ステージＮ＋１がリセットを完了したときステージＮは評価する。有効なデータ入力をステージＮ−１から受信した後でのみ、実際の評価が開始する。このプロトコルは、連続的なデータトークンがリセットトークンまたはスペーサ（spacer）によって常に隔離される。
【０００８】
パイプラインステージの事象の完全なサイクルは、どのように単一のデータトークンが初期の空のパイプラインを通って流れるのかを観察することによって導かれる。ステージ12aによる１つの評価から次への事象のシーケンスは、(i)ステージ12aが評価し、その後、(ii)ステージ12bが評価し、その後、(iii)ステージ12bの終了検出器16bが評価の完了を検出し、そしてその後、(iv)ステージ12aはプリチャージする。それと同時に、ステップ(ii)を終了した後、(iii)’ステージ12cは評価し、その後、(iv)’ステージ12cの終了検出器16cは評価の完了を評価し、そしてステージ12bのプリチャージを開始し、その後、(v)ステージ12bはプリチャージし、そして最後に、(vi)ステージ12bの終了検出器16bがプリチャージの完了を検出し、これによってステージ12aのプリチャージを開放し、ステージ12aが再度評価をすることをできるようにする。従って、１つの評価から次までのステージに対する完全なサイクルでは６つの事象がある。
【０００９】
上述したパイプラインのための完全なサイクルは、３つの評価、２つの終了検出、および１つのプリチャージから構成される。従って、分析的なパイプラインサイクル時間Tpsoは、
Tpso=3・tEval+ 2・tCD+ tPrech                 （１）
である。ここでtEvalとtPrechは、各ステージのための評価およびプリチャージの時間であり、tCDは、各終了検出器による遅延時間である。
ステージごとのフォワードレイテンシ（待ち時間）、即ちＬは、最初の空のパイプラインにおいて最初のデータトークンがあるステージの出力から次のステージの出力まで移動するときにかかる時間に応じて定義される。Ps0の場合、このフォワードレイテンシは、単純に以下のようにステージの評価遅れである。
Lps0=tEva                              （２）
【００１０】
このタイプのラッチフリー非同期ダイナミックパイプライン（例えばps0）の欠点は、代替ステージは、普通、スペーサ或いはリセットトークンを包含しなければならず、このことはパイプラインの容量を５０％にしてしまう。「ウィリアムのパイプライン」のその他の欠点は、ステージの間で幾つかの同期点を必要とすることである。さらに、ウィリアムのパイプラインは、パイプラインの相互作用を制約することによって、即ち、ステージのプリチャージおよび評価を隣接するステージの特定の事象を用いて同期化することによってデータのインテグリティ(integrity)を保持する。
【００１１】
３つの最近の競争相手の非同期パイプラインは性能を向上させたが、本発明によるデジタル信号処理パイプライン機器によって除去された多数の欠点を持つ。
【００１２】
ルノーディン（Renaudin）による設計は、大記憶容量を提供する（M. Renaudin et al. “New Asynchronous Pipeline Scheme: Application to the Design of Self-timed Ring Divider, IEEE JSSC, 31(7); 1001-1013, July 1996）。ルノーディンのパイプラインは、余分なラッチ或いは「アイデンティティステージ（identity stage）」無しで１００％の容量を達成する。彼らのアプローチは、容量を向上するためにダイナミックゲートの内部構造を局所的に操作するというものである。
【００１３】
しかしながら、ルノーディンのパイプラインには２つの重大な欠点がある。第１には、ルノーディンのパイプラインでは、追加のトランジスタを使用したにもかかわらず、各ダイナミックゲートの出力インバータを変更してゲートインバータにすることによって余分なラッチングが達成されてしまう。ルノーディンのパイプラインにおける第２の欠点は、比較的に低いスループットである。特に、ルノーディンのパイプラインは、pc0と称するはるかに保守的なps0パイプラインの形式に基づくものである。従って、これらの出力はpc0を改善したものであるが、ps0のものよりも一層悪い。
【００１４】
モルナー他による２つのFIFO設計（asp* FIFOおよびマイクロパイプライン化FIFO）は、文献で説明されているうちでは最も競争力があるパイプラインであり、０．６μmのCMOSで１．１ギガのスループットおよび１．７ギガ・アイテム／秒で報告されている（C. Molnar et al. , “Two FIFO Ring Performance Experiments,’ Proceedings of IEEE,87(2):297-307, February 1999）。
【００１５】
モルナーの第１のFIFO、即ちasp*は、重大な欠点を持つ。処理ロジックがパイプラインロジックに追加されるとき、asp* FIFOのスループットが、本明細書で述べたパイプラインの設計に比べて顕著に悪化することが予想される。この性能の低下は、asp* FIFOがロジックブロックを分離するための明示的なラッチを必要とするために起こる。これらのラッチは設計上必須であり、即ち、これらは、プロトコルがデータオーバーランにならないことを保証している。その結果、asp*では、ラッチとは別個の組み合わせロジックの場合では、ロジック処理の不利益が顕著になり得る。さらに、asp* FIFOは、明示的に標準化されていない複雑なタイミング想定を持つ。即ち、実際には、初期のバージョンはタイミングの問題のため不安定であった。
【００１６】
モルナーの第２の設計であるマイクロパイプライン化FIFOも、幾つかの欠点を持つ。第１に、このマイクロパイプラインは、実際には２つの並行な「ハーフレート」FIFOから構成され、それぞれが合計のスループットの半分（0.85ギガ・アイテム／秒）しか提供しない。従って、ネットのスループット１．７ギガ・アイテム／秒は、領域あたりで大きなコストをかけた場合のみ達成される。第２には、このマイクロパイプラインは、非常に高価な遷移ラッチ（transition latch）を使用することである。マイクロパイプライン化FIFOのその他の制限は、ロジックプロセスを全く実行できない、即ち、FIFOとしてしか使用できないということである。この制限の理由は、各ラッチの要素が隣接ステージの間で共用されているといった、複雑なラッチ構造を使用しているからである。その結果として、ラッチ間のロジックブロックの挿入が不可能になる。
【００１７】
文献で報告されているなかで最速の設計は、０．１８μmのCMOSプロセスでスループット３．３−４．５GHzのIPCMOSパイプラインである（S. Shuster et al., “Asynchronous Interlocked Pipelined CMOS Circuits Operating at 3.3-4.5 GHz, Proceedings ISSCC, February 2000）。IPCOMSは、プロトコルレベルと同様に回路上でも欠点を持つ。第１に、IPCMOSは、顕著な遅れを持つ大きくて複雑な制御回路を使用する。第２に、IPCMOSは、検証および設計に大きな労力を要する極めてアグレッシブな回路技術を活用する。例えば、これらの「ストローブ」回路におけるゲートの１つは、複数データストリームから２つのプルアップスタックおよびプルダウンスタックへの入力の相対的な到着時間に依存して、プルアップスタックおよびプルダウンスタックを通る短絡回路を潜在的に持つことができる。彼らのアプローチは、正確な出力を保証するスタックの割り当て制限（ratioing）に基づくものである。第３にIPCMOSでは、パイプラインステージは、有効なデータ入力が到着した後でのみ評価することを可能な状態にされる。従って、ステージをプリチャージリリースするための遅れのため、ステージの前方レイテンシーは悪い。
【００１８】
本発明の目的は、プリチャージと評価の分離を通じて大記憶容量および高スループットを提供することである。その他の目的は、隣接するデータトークン間の「リセット」スペーサの必要性を低減して、その結果記憶容量を増大することである。
また、本発明の目的は、明示的なラッチを必要としないプロトコルを持つ非同期パイプラインを提供することである。
また、本発明の目的は、シンプルで片側のタイミング制約を持つ非同期パイプラインを提供することであるが、これは容易に満足され得る。
また、本発明の目的は、データの到着前に評価することが可能にされる機能ブロックを持つ非同期パイプラインを提供することである。従って、空のパイプラインへのデータ挿入は、連続するそれぞれのステージを通って波及することができる。
本発明のさらなる目的は、ステージがその入力におけるいかなる変化にも関係なくその出力の状態を安定化することができるような、高度なデータインテグリティ（保全性）を持つ非同期パイプラインを提供することである。
本発明のさらなる目的は、臨界的な遅延を低減した、小さなチップ面積であり、低い消費電力であり、シンプルで小さく、かつ、速い制御回路を持ち、その結果オーバーヘッドを低減させた非同期パイプラインを提供することである。
本発明のさらなる目的は、複数の入力データストリームをマージする能力を持つ非同期パイプラインを提供することである。
【００１９】
発明の概要
本発明のこれらの目的およびその他の目的は、パイプラインにおいてデータトークンをより高密度に圧縮させ、その結果、大記憶、或いはバッファリングの容量を可能にする非同期デジタルパイプライン回路を通じて、本発明の原理に基づき達成される。その他の利点となる特徴は、低い前方レイテンシーおよび容易に達成される片側のタイミング制約を含む。
【００２０】
ラッチレスダイナミックロジックを持つ非同期デジタルパイプライン回路は、第１の処理ステージを持ち、この処理ステージは、第１のプリチャージフェーズ、それに続く第１の評価フェーズ、およびそれに続く第１の隔離フェーズから構成されるフェーズのサイクルを通って駆動されるよう構成されている。第１の隔離フェーズでは、第１の処理ステージの出力は、それの入力における変化から隔離すなわち分離されるが、その出力において格納されたデータの値は保持する。第１の処理ステージは、処理の３つのサイクルを通ってパスするために、第１のプリチャージ制御信号および第１の評価制御信号に応答する。第１のステージコントローラは、遷移信号に応答し、第１の処理ステージへ第１および第２の分離させた、即ち別個の制御信号を提供する。
【００２１】
第２の処理ステージは、第２のプリチャージフェーズ、それに続く第２の評価フェーズ、およびそれに続く第２の隔離フェーズから構成されるフェーズのサイクルを通って駆動され、第２のプリチャージ制御信号および第２の評価制御信号だけに（solely）応答するよう構成されている。第２の処理ステージは、そのステージのフェーズを示す遷移信号を提供する。第１の処理ステージコントローラにより遷移信号が受信されることで、第２の処理ステージが評価フェーズおよび隔離フェーズのうちの１つに留まっている間、第１の処理ステージが、プリチャージフェーズ、評価フェーズ、および隔離フェーズを通ってサイクル（循環）させることを可能にするようにして、第１の処理ステージと第２の処理ステージとの間は相互接続される。このような状況下、第１の処理ステージおよび第２の処理ステージは、スペーサで分離せずに異なるデータトークンを格納することができる。
【００２２】
第１の処理ステージと第２の処理ステージとの間に単一の明示的な同期点を提供する。第２の処理ステージのフェーズを示す遷移信号がアサート（asserted）されたとき、第１の処理ステージは、プリチャージ、評価、および隔離のサイクルを始めることが可能になる。この単一の明示的な同期点は、操作の並行性を増大させる。第２の処理ステージのフェーズを示す遷移信号がデアサート（de-asserted）されたときであっても、第１の処理ステージのフェーズを変化させるコマンドは無い。
本発明のさらなる特徴、その本質および様々な利点は、添付の諸図面および以下の好適な実施態様からより明らかとなるであろう。
【００２３】
好適な実施態様の詳細な説明
本発明による非同期デジタルパイプライン回路は、各処理ステージにおいてプルアップおよびプルダウンの制御を切り離す。ダイナミックゲートは、２つの別個の入力、「pc（プリチャージ）」および「eval（評価）」信号により制御される。これらの入力を使用して、ステージは、一連の区別可能な３つのフェーズ：評価、隔離（isolate）およびプリチャージを通って駆動されるが、このことは本明細書にて後で詳細に説明する。隔離フェーズでは、ステージは、その入力のいかなる変化にも関係せずにその出力状況を保持する。その結果として、隣接するパイプラインステージは、区別可能なデータアイテムを格納する能力を持ち、従って１００％の記憶容量を得る。
【００２４】
図３は、本発明によるパイプライン１００の簡単化したブロック図を説明する。３つの例示のステージ102a／102b／102cが図示されているが、これよりも多い或いは少ないステージにし得ることも考えられる。各ステージ102a／102b／102cは、それぞれ、３つのコンポーネント：機能ブロック104a／104b／104c、終了ジェネレータ106a／106b／106c、およびステージコントローラ108a／108b／108cを含むことができる。それぞれの機能ブロック104a／104b／104cは、次のステージのためにリセットスペーサとデータトークンを交互に生成し、それの終了ジェネレータ106a／106b／106cは、当該ステージの評価或いはプリチャージの終了を示す。第３のコンポーネントであるステージコントローラ108a／108b／108cは、「pc」および「評価(eval)」信号を生成し、これら信号は、それぞれの機能ブロック104a／104b／104c、および、終了ジェネレータ106a／106b／106cを制御する。これらのコンポーネントは以下でさらに詳細に説明する。
【００２５】
「バンドルドデータ（束にしたデータ）」と称する一般的に使用される非同期スキームを使用してシングルレイルの非同期データ経路を実現する。さらに詳細には、ライン110a／110b／110c上の制御信号である「Req（要求）」信号は、それぞれのステージ102a／102b／102cへの新たな入力の到着を示す。例えば、ライン110b上の「要求」信号は、終了ジェネレータ106bへの入力であって、終了ジェネレータ106aからの出力である。「要求」信号の値が高い場合は、新たなデータの到着、即ち前段のステージが評価を終了したことを示す。一方、「要求」信号の値が低い場合は、スペーサの到着、即ち前段のステージがプリチャージを終了したことを示す。正確な動作のためには、シンプルなタイミング制約を満足させなければならない。即ち、「要求」は、ステージへのデータ入力が安定し有効となった後で到着させなければならない。この要件は、遅れを提供する「マッチドディレイ」素子112a112b112cを挿入することによって満たされる。なお、この遅れは、機能ブロック104a／104b／104cを通るときの最悪の遅れ以上とする。このアプローチの利点は、標準的なシングルレイル（同期スタイル）機能ブロックを使用してデータ経路自身を作成できることである。
【００２６】
マッチドディレイを実現する一般的な方法は幾つかあり、例えばマッチドディレイ素子112a／112b／112cである。１つの好適な実施態様は、当該分野で知られているインバータ連鎖を使用することである。或いは、ゲートの数およびそのトランジスタのサイズが全体の遅れを決定するような、トランスミッションゲートも使用され得る。代替の技術は、ロジックブロックの最悪の場合のクリティカルパスを複製し、これを遅延ラインとして使用する。バンドルドデータは広く使用されてきたが、これには市販される同期フィリップス80C51マイクロコントローラチップが含まれる。
【００２７】
図４で、機能ブロック104a／104b／104cの一部をより詳細に図示する。より詳細には、図４は、パイプラインステージにおける機能ブロック104の１ゲートを示してある（接尾辞a、b、cが省略される場合は、説明する特徴は同じ符号を持つ全てのコンポーネントに共通である）。ライン114の「pc」入力信号は、プルアップスタック115（即ちプリチャージ）を制御し、ライン116の「eval（評価）」入力信号はプルダウンスタック117の下部（foot）を制御する。「pc」が低い値でアサートされ、かつ、「pc」が低い値でデアサートされたとき、プリチャージが発生する。「eval」が高い値でアサートされ、かつ、「pc」が高い値でデアサートされたとき、評価が発生する。両者の信号がデアサートされたとき、当該ゲート出力は、ゲート入力から効果的に隔離され、このようにして「隔離フェーズ(isolate phase)」に入る。短絡回路を避けるために、「pc」および「eval」信号は、同時にアサートされることはない。
【００２８】
図３の参照を続けるが、終了ジェネレータ106は、非同期Ｃ素子、即ち「aC」である。非同期Ｃ素子は、典型的には３つのタイプの入力：「＋」でマークされるもの、「−」でマークされるもの、第３のタイプはマークされないものを持つ。全てのマークされていない入力および全ての「＋」入力が高い値である場合は、「aC」の出力は高い値にセットされる。逆に、全てのマークされていない入力および全ての「−」入力が低い値である場合は、「aC」出力は低い値にリセットされる。全てのその他の組み合わせの場合は、「aC」はその出力値を保持する。終了ジェネレータ106は、ステージコントローラ108からの負の入力「pc」114と正の入力「eval（評価）」116とを持ち、さらに、前のステージの出力からの正の入力「Req（要求）」とを持つ。
【００２９】
本発明によるパイプライン100では、終了ジェネレータ106の出力、即ち「Done（完了）」信号はライン120上に置かれる。ステージ102が評価を開始したとき、即ち、２つのケース：（１）ステージ102がその評価フェーズに入ったとき、即ち「eval」信号が高い値になったとき、（２）前のステージが、有効なデータ入力を供給したとき、即ち、前のステージの「Req」終了信号が高い値になった場合には、この「Done」出力信号は高い値にセットされる。ステージがプリチャージすることが可能になる、即ち「pc」が低い値でアサートされたとき、「Done」信号は容易にリセットされる。従って、ステージのプリチャージは即座に「Done」をリセットし、一方、ステージが評価の状態にあり、かつ、有効なデータ入力が到着した場合のみ、評価は「Done」をセットする。
【００３０】
ライン120上の終了ジェネレータ106の出力は、マッチドディレイ素子112を通って供給され、この素子は（終了ジェネレータで一緒にされたとき）、機能104を抜ける最悪の場合の経路にマッチ、即ち合致させる。典型的には極めて微細(fine-grain)な、即ち「ゲートレベル」パイプラインの場合、マッチドディレイは不要とすることもできる。その理由は、終了ジェネレータ106によって生成されたaC自身の遅れは、多くの場合、機能ブロック104の遅れに既にマッチしており、従って、追加のマッチドディレイは必要でないからである。
【００３１】
最後に、ライン120上の終了信号「完了(Done)」は３つの経路に分岐され、下記の３つのコンポーネント：(i)ライン122上の前のステージのコントローラ108(現在のステージの状況を示す。例えば、ライン122b上のステージコントローラ108aへ)、(ii)現在のステージのステージコントローラ108（例えば、ライン124b上のステージコントローラ108b（マッチドディレイ素子112bを通って）へ、(iii)次のステージの終了ジェネレータ106（例えば、ライン110c上の終了ジェネレータ106cへ（マッチドディレイ素子112b）を通って）、へと供給される。
【００３２】
図３の参照を続けるが、ステージコントローラ108は、機能ブロック104と終了ジェネレータ106とのために制御信号「pc」と「eval(評価)」とを生成する。ステージコントローラ108自身は、２つの入力：
(1)ライン124上の現在のステージの遅れた「Done（完了）」信号（即ち「Req（要求）」、以降、信号Ｓと称する。例えば、信号Ｓはライン124b上のステージコントローラ108に到着することができる。）、
(2)次のステージの「Done」信号（以降、信号Ｔと称する。例えば、信号Ｔはライン122c上のステージコントローラ108bに到着することができる。）、
を受信する。ステージコントローラ108は、２つの隔離された信号「pc」と「eval」とを生成する。ステージコントローラのプロトコルとその実現の詳細は、以降、本明細書にて詳細に説明する。
【００３３】
図５に図示するように、パイプライン100の各ステージ102は、３つのフェーズを通って回転する。サイクル200aは第１のステージNを説明するためのものであり、サイクル200bは隣接するステージN+1を説明するためのものである。ステージNは、その評価フェーズ202aを終了した後、その隔離フェーズ204aに入り、典型的にはステージN+1から信号を受信するまではプリチャージフェーズ206aに進行することは無いが、これについて以下で説明する。プリチャージフェーズ206aが終了し次第、評価フェーズ202aに再度入り、サイクルを終了する（ステージN+1は、同様に、点線で示すように評価202b、隔離204b、およびプリチャージ206bを通過する）。
【００３４】
ステージNとN+1との間には、１つの明示的な同期点、即ち相互接続がある。点線210で示すように、ステージN+1がその評価フェーズ202bを終了するとすぐに、前のステージNがその全体の次のサイクル：即ち、新たなデータアイテムに対するプリチャージフェーズ206a、評価フェーズ202a、および隔離フェーズ204a、を実行することが可能になる。点線211で示すように、１つの黙示的な同期点、即ち、それの先行するステージNの評価フェーズ202aのステージN+1の評価フェーズ202bの依存性もある。ステージは有効な入力データをその先行するステージから受信するまでは、ステージは新たなデータを生成することはできない。これらの同期点は、図５において因果の弧（causality arc）で図示される。
【００３５】
ステージが評価を終えるとすぐに、自己リセット操作によってその入力から自己を隔離する。ステージは、このステージがプリチャージフェーズに入ることが可能であるか否かを問わず、隔離フェーズに入る。その結果、前のステージは、次のデータトークンを無事に評価したとしても、プリチャージだけをすることができない。そのため、現在のステージは隔離されたままとなる。例えば、ステージN+1がその評価フェーズ202aを終了したとき、そのステージは隔離フェーズ204aに入り、一方、ステージNはステージN+1の出力の影響を受けることなくプリチャージ206aおよび評価202aに入ることができる。
【００３６】
このプロトコルには２つの利点：(a)より高いスループット（ステージN+1がプリチャージを始める前でさえもステージNは次のデータアイテムを評価することができるからである）、(b)同じ理由からより大きな容量（スペーサで分離すること無く、隣接のパイプラインステージが同時に別個のデータトークンを保持する能力を持つからである）がある。
【００３７】
ステージコントローラの形式仕様を図６(a)でペトリネット（同時挙動を説明するのに一般的に使用される良く知られているグラフィック表現）の形式で考える。これは、ラベルを付けられた事象で示される遷移、および、黒の点で示されるトークンを格納する場所から構成される。そこに入ってくるアーク（弧）の全てがトークンを持つとき、遷移は発火（fire）して、その後、トークンはそこから出て行くアークの全ての上に置かれる（ペトリネットのさらなる詳細は、タダオ・ムラタの「ペトリネット」（Tadao Murata, “Petri Nets: Property, Analysis and Applications,” Proceedings of the IEEE, 77(4), April 1989; L.Y. Rosenblum）およびヤコレブの「シグナルグラフ」（A.V. Yakolev, “Signal Graphs: From Self-Timed to Timed Ones,” Proceedings of International Workshop on Timed Petri Nets, Torino, Italy, pp. 199-207, July 1985）およびタムアー・チュの「VLSI非同期デジタル回路設計用のモデル」（Tam-Anh Chu, “On the Models for Designing VLSI Asynchronous Digital Circuits,” Integration, the VLSI Journal, 4(2):99-113, June 1986）に述べられている。これらの文献は参照によってその全体を本明細書に合体させるものとする。
【００３８】
ステージコントローラ108のためのペトリネット仕様は、図５に関して上述したように、ステージサイクルの一連のフェーズから推論され得る。ステージNのコントローラは、２つの入力、SおよびTを持ち、これらは、それぞれステージNとステージN+1の「Done（完了）」出力である（図３を参照されたい。）。また、コンとローラは、２つの出力「pc」および「eval」を持ち、これらはステージNを駆動する。
【００３９】
図６(a)は、ステージコントローラの予備的な設計のためのペトリネットを図示する。図６(a)で示した仕様は、本明細書で詳述した幾つかの欠点が表現されている。302でステージNのプリチャージのための条件を可能にすることはあいまいである。即ち、ステージNはデータアイテムの評価を終了し、304で隔離フェーズに入り（信号S124は高い値である）、ステージN+1は、306で同じデータアイテムを評価する（信号T122は高い値である）。ステージN+1がブロックされたり遅くなったりしたときに問題が起こり、その高い値のT122出力の保持を続行する可能性があり、一方、ステージNは全ての新たなデータ入力を処理する（プリチャージし、その後で評価する）。この場合、信号S124とT122とは再度高い値となり、しかし、ステージNとステージN+1とは、今は別個のトークンを持っている。この場合は、ステージN+1は新たなデータを吸収していないため、ステージNをプリチャージしてはならない。
【００４０】
この問題の解決策は、状態変数「ok2pc117」を加えることによって達成され、これはステージコントローラの非同期C素子によって実現される（図６(b)を参照されたい）。図６(b)の仕様は、本明細書で指摘する相違点はあるが実質的には図６(a)と同一である。ステージN+1がデータアイテムを吸収したか否かを、変数「ok2pc153」は効果的に記録する。ペトリネット350で説明するように、「ok2pc153」は、352でステージNがプリチャージした後即座にリセットされ（信号S124は低い値である）、N+1が354でその後のプリチャージになったときのみすぐに、再度セットされる（信号T122は低い値である）。
【００４１】
図７(a)および図７(b)は、図６(b)のコントローラを実現させたものを示す。この実現は、２つの入力：T122とS124とを合体させ、３つの出力信号：pc114、eval116、およびok2pcを生成し、これらの出力信号のそれぞれはシングルゲートを使用して実現される。コントローラは、上述した前の章の条件を直接的に実現する。
【００４２】
より詳細には、信号eval16は、信号S124に通じているインバータ150の出力である。図３および図５と共に図７を参照すると、何らかのさらなる入力がなくeval116が低い値でデアサートされたときに、ステージ104は評価フェーズ202から隔離フェーズ204へとサイクル即ち循環する。この実施態様では、ステージ104が評価した後、信号eval116はライン120a上の終了検出器およびマッチドディレイ素子112を通過する。マッチドディレイ素子112の出力は、ライン124上のS信号である。ステージコントローラ108のインバータを通過した後、eval信号116は低い値でデアサートされ、これによって当該ステージは隔離フェーズ204に入ることが可能になる。
【００４３】
ok2pc信号153の生成は、図７(b)でより詳細に図示してあるが非同期C素子152によって実行される。ステージN+1が評価を終え、T122が低い値になった後、ok2pc153は高い値にセットされるので、T信号122を受信するためにインバータ156を加える。ok2pcの生成は追加のゲートディレイをpc114への制御経路に加えたように見えるが、図６のプロトコルは、クリティカルパスからこの計算を実行する、即ち、ok2pcは「バックグラウンド・モード」でセットされ、その結果、T122がアサートされる前にok2pcが典型的にはセットされる。その結果、pc114へのクリティカルパスはただ１つのゲートディレイ、即ち入力T122から３−入力のNAND3ゲート154を通って出力pc114までのゲートディレイとなる。
【００４４】
図８は、本発明のその他の実施態様による１つの完成したパイプラインステージ401を図示する。より詳細には、図３に示したパイプラインステージ102の機能ブロック104および終了ジェネレータ106は、組み合わせた機能ブロック405に一体化させてある。ステージ401も、マッチドディレイ素子412とステージコントローラ408を含む（ダッシュで示してある）。機能ブロック405の出力419は、次のステージ（図８には図示せず）へとパスされる。終了ジェネレータ（図示せず）の出力420は２つの信号に分割され、１つはマッチドディレイ素子412へ渡され、もう１つは信号422aとなり、この信号は前のステージ或は環境へと渡される。マッチドディレイ素子412の出力は信号S424である。ステージコントローラ108に関連して説明したステージコントローラ408への入力は、信号S424と次のステージ（図８には図示せず）からの信号T422bである。
【００４５】
ステージNのための事象の全体サイクルは、図３と図５とを参照してたどることができる。ステージNによる１つの評価から次の評価へのサイクルは、下記の３つの操作から構成される。ステップ(i)では、ステージNが評価する。ステップ(ii)では、ステージN+1が評価し、次に、ステージNのコントローラがNのプリチャージ入力（pc=low）がアサートすることを可能にする。ステップ(iii)では、ステージNがプリチャージし、ステージNのコントローラを通過して前記プリチャージが終了することによって、Nが再度評価することが可能になる（evalは高い値でアサートされる）。図３と図５の符号番号を参照すると、処理は以下のとおりに進行する。ステップ(i)では、ステージ102aが202aを評価し、隔離ステージ204aに進み、そして待機する。その後、ステップ(ii)では、ステージ102bが202bを評価し、ステージ102bの評価の終了を受けて、ステージコントローラ108aは信号T112bを受信し、pc114aをアサートする。ステップ(iii)では、ステージ102aは206aをプリチャージし、再度評価することが可能になる。
【００４６】
上述したように、余分なマッチドディレイはゲートレベルパイプラインには不要なものとすることができる。その理由は、終了検出器とその他の遅れは、ゲートの評価およびプリチャージに既にマッチしているからである。その後、以前に紹介された表記法では、ステップ(i)の遅れはtEvalであり、ステップ(ii)の遅れはtaC+tNAND3であり、そして、ステップ(iii)の遅れはtPrech+tINVである。ここで、tNAND3とtINVとは、図７(a)のNAND3-154とインバータ150とをそれぞれ通過する遅れである。従って、分析的なパイプラインサイクル時間は下記にようになる。
THC=tEval+tPrech+taC+tNAND3+tINV            （３）
ステージのレイテンシーは、以下のように単純に当該ステージの評価遅れである。
LHC=tEval                                      （４）
【００４７】
本発明によるパイプライン100は、正確な操作のために片側のタイミング制約を必要とする。現在のステージが評価し、かつ、次のステージがプリチャージした（S=1、T=0）後すぐにok2pc信号153は高い値となる。続いて、次のステージによる評価の結果に応じて信号Tは高い値となる。正確な操作のため、T信号がhighに即ち高くなる前に、ok2pc信号は、以下のようにその上昇遷移を終了しなければならない。
tok2pc↑＜tEval+tINV                          （５）
実際はこの制約は非常に容易に満たされた。
【００４８】
適切なプリチャージ幅を実施しなければならない。この設計では、この制約は、制約を束にすることによって部分的に実施される。即ち、aC素子と（任意選択の）マッチドディレイとは、共に、機能ブロックの最悪のケースのプリチャージ時間よりも大きな遅れを持たなければならない。従って、図７(a)におけるNAND3-154へのS信号は適切に保持される。
【００４９】
プリチャージ幅に対する追加の制約があり、この制約は、NAND3-154へのT信号がデアサートされてはならないというものである。例えば、T信号が高い値でアサートされた場合には、ステージ102aのNAND3-154aは、102aのプリチャージを開始する（図３）。同時に、信号T122bは、以下のように、ステージ102cの終了ジェネレータ106cの非同期C素子（aC）、ステージコントローラ108bのNAND3-154b、および、ステージ102bの終了ジェネレータ106bの非同期C素子（aC）、最後にコントローラ108aのNAND3-154aを通過した後、リセットのみされる。
【数１】
0003869726.tif 000002
全てのステージが同じであると仮定すると、この制約は以下のようになる。
【数２】
0003869726.tif 000003
この制約も容易に満たされた。
【００５０】
図７(a)のインバータ150を使用することで、評価をした後でステージを隔離することが可能になる。この束にした制約は、隔離フェーズが開始を早くし過ぎないことを既に保証している。
【００５１】
実施例
事例研究として、本明細書で述べたパイプラインを使用して、ゲートレベル・パイプライン化加算器をシミュレートした。この実施例は、パイプラインステージに対する複数の入力ストリームがどのようにして単一の出力ストリームへとマージされ得るのかを示す。32ビットのリップルキャリー(ripple-carry)型加算器を選択したが、その理由は、その設計がシンプルであり、非常に微細なパイプラインに順応するからである。この加算器の構成は、マルチメディア処理用のDSPなどの高スループットのアプリケーションに適する。
【００５２】
図９は、リップルキャリー型加算器の例示のステージ500を示す。この加算器の各ステージは、全加算器であり、３つのデータ入力：A502、B504、キャリーイン(carry-in)Cinと、２つの出力：キャリーアウト(carry-out)Cout508とSum510を持つ。これらの論理式は以下のようになる。
【数３】
0003869726.tif 000004
【００５３】
デュアルレイルとシングルレイルの符号化の組み合わせを用いて加算器のデータ経路を表現する。排他的論理和の操作は、そのオペランドの真数と補数の値の両者を必要とするため、２つのレイルを使用して、ダイナミックロジックの実現のために必要なデータ入力A、B、Cinの各自を表現する。さらに、ステージCoutは次のステージのCinであるため、これも２つのレイルを使用して表現する。一方、Sum（合計）は、たった１つのレイルを使用して表現するが、その理由はそれの補数が必要でないからである。全体のデータ経路は、束にしたデータ経路であり、従って、２つのレイルを使用して幾つかの信号が表現されていたとしてもシングルレイルと考えることができる。
【００５４】
A502、B504、Cin506、およびCout508をa1a0、b1b0、cin1cin0、およびcout1cout0でそれぞれ表記し、加算器の式は以下のように記述される。
Sum=(a1b0+a0b1)cin0+(a1b1+a0b0)cin1        （１０）
cout1=a1b1+(a1+b1)cin1                    （１１）
cout0=a0b0+(a0+b0)cin0                    （１２）
【００５５】
本実施態様では、３つの出力：Sum、cout1およびcout0は、単一のダイナミックゲートを使用して実現した。従って、各ステージはただ１つのロジックレベルを持つ。
本明細書で説明したパイプライン構造とは異なり、このパイプライン化加算器は非線形構造である。ステージ500は、３つの別個の入力ストリーム即ち２つのデータオペランドとキャリーインをマージすることができる。従って、パイプライン構造の代替の実施態様を複数のソースを扱うために説明する。特に、それぞれの全加算器が複数入力ストリームの同期点を表現するため、加算器は複数の束にされた入力（即ち、「要求」信号）を処理する能力を持たなければならない。
【００５６】
入力A502とB504とは、共通のバンドリング信号のreqab523を伴う１つの共有データストリームに属するものと考えられ得る。キャリーインのreqc525を伴うCin入力は、その他のストリームを形成する。従って、ほんの２つの入力ストリーム：データオペランドおよびキャリーインが仮定される。実際には、これは、オペランドが同じソースから来る場合のような多くのアプリケーションにおいてリーズナブルな仮定である。この仮定が持ちこたえられな場合、我々のアプローチは３つの独立スレッドを扱えるように拡張され得る。
【００５７】
図１０は、終了ジェネレータ506のその他の実施態様を示す。終了ジェネレータ506は、データ入力reqab523とキャリーイン入力reqc525と同期を取る。それぞれの加算（addition）の要求信号は、１つのトランジスタを終了ジェネレータの非同期C素子552のプルダウンスタックに加えることによって、適応する。結果ととして生じる「Done(完了)」出力信号520は、３つの宛先、即ち、キャリーインを送信したステージへの、および、オペランドを送信したステージへの「肯定応答」、および、次のステージへの「要求」へと分岐する。
【００５８】
図１１で加算器アーキテクチャの全体を示す。シフトレジスター568a、568b、および568cは、オペランドのビットを、それぞれ、加算器ステージ500a、500b、および500cの各々へ提供する。シフトレジスター570a、570b、および570cは、それぞれの加算器ステージ500a500b500cに装着され、これは当該ステージから出て来る合計ビット（sum bits）のストリームを積算するためのものである。加算操作のための合計ビットの全てが利用可能になったらすぐに、これらは並行に各シフトレジスターから１ビット読み取られることができる。シフトレジスターは、それら自体で本明細書で説明した実施態様に基づく非同期パイプラインとして作成され得る。
【００５９】
32ビットリップルキャリー加算器は、３．３V電源および300°Kの操作条件の０．６μmのHP CMOSプロセスを使用するHSPICEでシミュレーションした。高いスループットのためにトランジスタのサイズを最適化するために特別な考慮を払った。各ダイナミックゲートのプリチャージPMOSトランジスタは、18λ／2λのW/L比を持った。評価スタックのNMOSトランジスタは、n−スタックの効果的な幅がp−スタックの１／３となるようなサイズにする。さらに、それぞれの設計のために、タイミング制約は快適に満たされることが保証された。
表１はシミュレーション結果をまとめたものである。
【００６０】
【表１】
0003869726.tif 000005
【００６１】
表１は、サイクルタイムの全体をリストし、同様にそれを分解したコンポーネント：ステージ評価時間（tEval）、ステージプリチャージ時間（tPrech）、終了ブロックを通過するときの遅れ（taC）、同じく制御ゲートを通過するときの遅れ（tNAND3とtINV）をリストする。最後に、この表は、各加算器のスループットを１秒あたり何百万操作するのかでリストする。加算器のスループットは、１０２３（百万操作／秒）であることがわかった。
前述のものは本発明の原理を説明することのみを目的とし、本発明の範囲および本質を離れることなく当業者によって様々な変形が施され得ることが理解されるであろう。
【図面の簡単な説明】
【図１】  先行技術のパイプラインを説明する図である。
【図２ａ】  図１の先行技術のパイプラインの機能ブロックの回路を説明する図である。
【図２ｂ】  図１の先行技術のパイプラインの終了検出器を説明する図である。
【図３】  本発明による非同期デジタルパイプライン回路のブロック図である。
【図４】  本発明による図３のブロック図のゲートの回路図である。
【図５】  本発明による非同期デジタルパイプライン回路のステージの相互作用およびフェーズのシーケンスを説明する図である。
【図６ａ】  例示のパイプラインステージコントローラの例示のペトリネット（Petri-net）仕様を説明する図である。
【図６ｂ】  本発明によるパイプラインステージコントローラのペトリネット仕様を説明する図である。
【図７ａ】  本発明による図３で示した非同期デジタルパイプライン回路のステージコントローラの論理図である。
【図７ｂ】  本発明による図７(a)で示したステージコントローラの一部の回路図である。
【図８】  本発明による非同期デジタルパイプライン回路の代替の実施態様のブロック図である。
【図９】  本発明による例示の実施態様の簡単化したブロック図である。
【図１０】  本発明による図９の実施態様の一部のブロック図である。
【図１１】  本発明によるその他の実施態様の簡単化したブロック図である。
【図１】
0003869726.tif 000006
【図２ａ】
0003869726.tif 000007
【図２ｂ】
0003869726.tif 000008
【図３】
0003869726.tif 000009
【図４】
0003869726.tif 000010
【図５】
0003869726.tif 000011
【図６ａ】
0003869726.tif 000012
【図６ｂ】
0003869726.tif 000013
【図７ａ】
0003869726.tif 000014
【図７ｂ】
0003869726.tif 000015
【図８】
0003869726.tif 000016
【図９】
0003869726.tif 000017
【図１０】
0003869726.tif 000018
【図１１】
0003869726.tif 000019