JPH09204236A

JPH09204236A - 高速コンピュータにおけるタイミング信号発生方法及びその装置

Info

Publication number: JPH09204236A
Application number: JP8323213A
Authority: JP
Inventors: Bakusutaa Maikeru; バクスターマイケル
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1996-01-24
Filing date: 1996-12-03
Publication date: 1997-08-05
Anticipated expiration: 2016-12-03
Also published as: JP3784476B2; CN1162153A; DE19702326B4; US5854918A; DE19702326A1; CN1103951C

Abstract

(57)【要約】【課題】他の関数論理セットを駆動する全ての基準ク
ロックと独立してできる限り高速に選択したアルゴリズ
ムを実行することである。【解決手段】自己刻時式アルゴリズム実行のための方
法は、基準クロック２８に同期して関数論理２４の組へ
入力データを転送するステップと、機能論理の組につい
てのアルゴリズム実行時間に依存しているが基準クロッ
ク２８とは独立している速度で関数論理２４の組を駆動
するため最大速度パルスシーケンスを生成するステップ
と、最大速度パルスシーケンスに応じて関数論理２４の
組から出力データを生成するステップと、基準クロック
２８に同期して関数論理２４から出力データを転送する
ステップとを含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、高速コンピュータ
におけるタイミング信号発生方法及びその装置に関する
ものである。さらに詳しくは、本発明は、マスタ時刻基
準に厳密には同期していない自己刻時式アルゴリズム実
行のための方法並びにその装置に関する。

【０００２】

【従来の技術】高速コンピュータ・システムでは、各種
の必要なスイッチング動作を同期させるためのマスタ時
刻基準が必要とされる。ある種のコンピュータ・システ
ムでは、均一な１つのクロック信号が数個のクロック増
幅器で再バッファリングされてシステム内で使用される
メモリ装置全部のタイミング同期の唯一の供給源として
動作する。別のシステムでは、数個の更に異なる位相の
クロック信号を用いて別々のメモリ装置の組を駆動して
いる場合があるが、全て従来的にはシステム内のマスタ
時刻基準に同期されている。

【０００３】複数のクロック信号を使用する場合、異な
るメモリ装置が相対的に異なる速度でデータストリーム
または命令シーケンスによって状態を切り換えるかまた
は変更する。このような複数のクロック回路は、メモリ
装置間の関数論理がもっとも速い速度で周回できるよう
に設計されることが多い。パイプライン化システムで
は、たとえば、関数論理はメモリ装置間で分担され、目
標とする最小実行時間のシステム設計上の制約が関数論
理またはメモリ装置要素の個数の共同制約的増加なしに
維持されている。

【０００４】ある種のパイプライン化システムでは、高
速で幾つかのパイプライン機能ユニットの内部順位を維
持しつつ機能ユニットの入出力境界がシステム内の残り
のパイプライン機能ユニットと互換性のある低い速度で
維持されるように超ハーモニッククロックが使用されて
いる。従来技術の方法は「マイクロパイプライン化」と
して周知でありパイプライン化機能ユニットの内部メモ
リ装置がパイプラインの入力ポートおよび出力ポートに
見られる低速のストリーム速度と同期してパイプライン
のマイクロ演算をインタリーブ化する厳密に同期した超
ハーモニッククロック信号を有するような装置を含む。
残念ながら、マイクロパイプライン化の欠点としては、
それぞれのメモリ装置から実際に受信したトリガ信号に
最低限の歪みを保証するため低歪み木構造として数個の
クロック増幅器を必要とし、また一元的なタイミング間
隔を要求することが含まれる。つまり、一元的タイミン
グ間隔の内部で充分に動作できる程短い伝播遅延を有し
ていないマイクロパイプライン内部の論理要素の組は、
対応させるのが難しい。更に、ＲＬＤ内部の伝播遅延が
機能単位ごとに変化し、半包括的マイクロパイプライン
クロックを有することを困難にしているため、マイクロ
パイプライン化の概念は再設定可能な論理装置（ＲＬ
Ｄ）たとえばフィールド・プログラマブル・ゲートアレ
イ（ＦＰＧＡ）等を用いて実装するのが特に困難であ
る。

【０００５】

【発明が解決しようとする課題】従来、ＲＬＤが各種論
理設計の実施に使用される場合、実際のＲＬＤ相互接続
を生成するために使用する「ツール」の大半はレジスタ
転送言語（ＲＴＬ）パラダイムを使用している。このよ
うなパラダイムはＲＬＤ内部の関数論理およびメモリ装
置を駆動する独立したマスタ刻時基準クロックの存在に
強く依存している。このようなパラダイムはさらに、Ｒ
ＬＤ内部の論理設計の物理的実装が論理設計の全体的タ
イミング性能およびシリコン資源要求に依存することを
無視している。実際に、ＲＬＤツール製造メーカではＲ
ＬＤの物理特性に左右されないことを論理設計パラダイ
ムの「利点」として主張している。

【０００６】他の高速コンピュータ・システムはマスタ
時刻基準に同期したくロックシステムに付随する前述の
困難を回避するため、コンピュータの機能タスクを一組
の非同期刻時によるサブタスクに分割する試みを行なっ
ている。残念ながら、既存の非同期論理設計も多くの制
約を有している。これはたとえば、演算タスクを完了す
る際に「完了信号」を生成する必要があること、可変ま
たは未知の完了時刻を有すること、外部クロック要素を
必要とすること、データ依存の完了時刻を有すること、
外部回路と非同期的にインタフェースすること、外部回
路とのデータ交換をコヒーレントでない位相にするこ
と、外部クロック回路へ加えられた遅延がさらにシステ
ム全体を複雑化すること、同期外部回路の内部に埋め込
むことが難しいこと、システム全体の性能を外部クロッ
ク回路ネットワークに結合することがある。

【０００７】必要なのは、可能な限り高速なパイプライ
ン周波数を実現する上で固有の負担を、一元的なタイミ
ング間隔を用いるシステム内部でできるかぎり短いステ
ージ環遅延の制約を有する同時的な負担から分離するよ
うな自己刻時式アルゴリムの実行のための装置ならびに
方法である。

【０００８】

【課題を解決するための手段】請求項１記載の発明は、
第１の速度で入力データを受信するように結合され、前
記第１の速度とは独立した第２の速度で出力データを生
成し、前記第１の速度で前記出力データを送信するよう
に結合される関数論理の組と、前記第２の速度に対応す
る自己刻時式パルスシーケンスを生成し、前記関数論理
を制御するように結合されたパルスシーケンサとを含む
ことを特徴とするものである。

【０００９】そして、前記関数論理の組は予測される実
行時間を有することと、前記第２の速度は前記予測実行
時間に基づく最大速度であることを特徴とする。

【００１０】前記関数論理と前記パルスシーケンサは一
組のハードウェア資源の組の内部に配置されて前記ハー
ドウェア資源の動作パラメータ変動に対して同期的に応
答することを特徴とする。

【００１１】前記パルスシーケンサは自己刻時式発振を
生成する遅延ユニットを含むことを特徴とする。

【００１２】前記遅延ユニットは直列接続した一組の論
理装置を含み、それぞれの論理装置は予測可能な伝播遅
延を有することを特徴とする。

【００１３】前記直列接続の一組の論理装置は一組のキ
ャリー論理要素を含むことを特徴とする。

【００１４】前記一組のキャリー論理要素は再設定可能
な論理装置内にキャリー伝播論理を含むことを特徴とす
る。

【００１５】前記パルスシーケンサはさらに一組のクロ
ック信号を生成するシーケンスゲート論理を含み、前記
シーケンスゲート論理は遅延ユニット出力信号を受信す
るように結合されまた関数論理へ前記一組のクロック信
号を供給して前記第２の速度を提供するように結合され
ることを特徴とする。

【００１６】前記パルスシーケンサはさらにパルスカウ
ント信号を生成するパルスカウンタを含み前記パルスカ
ウンタは前記遅延ユニット出力信号を受信するように結
合されることを特徴とする。

【００１７】前記パルスシーケンサはさらに開始パルス
を生成して前記遅延ユニットの動作を開始するための開
始論理を含むことを特徴とする。

【００１８】前記関数論理は乗算器を含み、前記乗算器
は被乗数を受信するように結合されたマルチプレクサ
と、乗数と前記被乗数内部のビットのサブセットを受信
するように結合されて一組の部分積を生成する部分積ジ
ェネレータと、前記一組の部分積を受信するように結合
されて部分積の和を生成する部分積加算器と、前記部分
積の和を受信するように結合されて部分積の和を積算し
て積を生成する積積算器とを含み、前記乗数は前記遅延
ユニットにより生成された前記自己刻時式発振に応じて
制御されることを特徴とする。

【００１９】再設定可能な論理装置内のパルスシーケン
サであって、前記パルスシーケンサは自己刻時式発振を
生成するように結合された一組のキャリー論理素子を含
むことを特徴とする。

【００２０】請求項２記載の発明は、自己刻時式アルゴ
リズム実行システムを制御するための装置であって、前
記自己刻時式アルゴリズム実行システムは入力データを
受信して一組の制御信号に応じて出力データを生成する
関数論理を含み、前記装置は、開始信号を受信するよう
に結合されてこれに応じて開始パルスを生成する開始論
理と、前記開始パルスを受信するように結合されてこれ
に応じて遅延ユニット出力信号とフィードバック信号と
を生成する遅延ユニットと、前記遅延ユニット出力信号
を受信するように結合されてこれに応じてパルスカウン
ト信号を選択し選択的に停止信号を生成するパルスカウ
ンタと、前記パルスカウント信号を受信するように結合
されてこれに応じて前記一組の制御信号を生成するシー
ケンスゲート論理とを含み、前記開始論理は前記フィー
ドバック信号を受信し応答的に前記停止信号が生成され
ない場合には前記開始パルスを再生成するように結合さ
れることを特徴とする。

【００２１】請求項３記載の発明は、一組の関数論理と
パルスジェネレータを含む装置において自己刻時式アル
ゴリズム実行のための方法であって、前記方法は、第１
の速度で入力データを受信するステップと、前記第１の
速度と無関係な第２の速度で自己刻時式パルスシーケン
スを生成するステップと、前記パルスシーケンスに応答
して前記第２の速度で前記入力データを処理するステッ
プと、前記第１の速度で出力データを出力するステップ
とを含むことを特徴とする。

【００２２】また、前記パルスシーケンスを生成する前
記ステップは前記一組の関数論理に関連する実行時間に
従う最大速度で実行されることを特徴とする。

【００２３】前記入力データを受信するステップは基準
クロックと同期して実行され、前記生成ステップは前記
基準クロックとは独立した自己刻時式速度で実行され、
前記出力ステップは前記基準クロックと同期して実行さ
れることを特徴とする。

【００２４】前記生成ステップは、開始信号に応答して
自己刻時式発振を生成するステップと、停止信号を受信
するまで前記自己刻時式発振を維持するステップとを含
むことを特徴とする。

【００２５】前記生成ステップは、さらにパルスカウン
ト信号を生成するステップと、前記自己刻時式発振の周
期に対応する速度で前記入力データの処理を制御する一
組の制御信号を生成するステップとを含むことを特徴と
する。

【００２６】前記処理ステップは、さらに乗数と被乗数
内部のビットのサブセットを乗算することで一組の部分
積を生成するサブステップと、前記一組の部分積を加算
することにより部分積の和を生成するサブステップと、
前記部分積の和を直前の部分積の和に積算するサブステ
ップと、乗算積が生成されるまで前記処理ステップ内の
それぞれのサブステップを反復するサブステップとを含
むことを特徴とする。

【００２７】請求項４記載の発明は、自己刻時式アルゴ
リズム実行のための装置であって、第１の速度で入力デ
ータを受信する手段と、前記第１の速度と無関係な第２
の速度で自己刻時式パルスシーケンスを生成する手段
と、前記第２の速度で前記入力データを処理して前記自
己刻時式パルスシーケンスに応じて出力データを生成す
る手段と、前記第１の速度で前記出力データを出力する
手段とを含むことを特徴とする。

【００２８】前記生成手段は、自己刻時式発振を生成す
る手段を含むことを特徴とする。

【００２９】

【発明の実施の形態】本発明の実施の一形態を図面に基
づいて説明する。本発明は、高速コンピュータにおける
タイミング信号発生であり、特に、自己刻時式アルゴリ
ズム実行のための方法並びに装置である。

【００３０】本発明の装置は望ましくは関数論理セット
と、基準クロック入力と、パルスシーケンサとを含む。
関数論理セットは基準クロック入力に受信した基準クロ
ックと同期して入力データを受信し、関数論理セットの
物理的特性にしたがってパルスシーケンサによって決ま
る最大速度で入力データについてのアルゴリズム計算を
実行し、出力データを生成し、基準クロックと同期して
出力データを送信する。パルスシーケンサにより設定さ
れる最大速度は基準クロックに依存しない。

【００３１】本発明の方法は望ましくは、基準クロック
と同期して入力データを関数論理セットに転送する段階
と、機能的論理セットのアルゴリズム実行時間に依存す
るが基準クロックには依存しない速度で関数論理セット
を駆動するための最大速度パルスシーケンスを生成する
段階と、最大速度パルスシーケンスに応答して機能論理
セットから出力データを生成する段階と、基準クロック
に同期して関数論理からの出力データを送信する段階と
を含む。

【００３２】本発明は自己刻時式アルゴリズム実行のた
めの装置ならびに方法である。選択したアルゴリズムを
実行するように設計した関数論理セットと遅延ユニット
を対にすることで、本発明では第１に他の関数論理セッ
トを駆動する全ての基準クロックと独立してできる限り
高速に選択したアルゴリズムを実行する。つまり、周知
のタイミング装置およびその方法とは対称的に、アルゴ
リズムを実施する全ての機能論理セットのタイミング特
性は基準クロックの速度に制限されたり依存する必要が
ない。第２に、一組の自己刻時式パルスの生成に応じて
アルゴリズムを実施する関数論理セットに基づいた自己
刻時速度でデータ演算する。第３に、他の関数論理セッ
トで受信すべき特定の既知の時刻にデータを出力する。
その結果、本発明の装置ならびに方法はひとつの関数論
理セットを他の関数論理セットまたは基準クロックの動
作速度と無関係な速度で動作させることができるため、
ハードウェア設計を簡略化しつつ最大限可能なアルゴリ
ズム実行速度を維持することが可能で、従来技術に対し
て特に有利である。

【００３３】本発明はもっとも基本的な物理構造におい
て関数論理セットを観察することによりこれらの利点を
実現する。本発明はレジスタ転送論理（ＲＴＬ）パラダ
イムに依存しない。本発明はむしろ、アルゴリズムを実
行する関数論理セットに独自のタイミング回路を合わ
せ、関数論理セットが最大限可能な速度で演算できるよ
うにする。つまり、本発明はアルゴリズムの実行だけで
はなくタイミング速度のインクリメンタルな調停者とし
てシリコン資源をみなすことでシリコン資源内部の論理
設計を実施するための新規なパラダイムを定義する。従
来技術では、第１に従来技術のシステムにおける論理実
装の時間的インパクトがメモリ装置だけに見られる副作
用に依存すること、第２に、関数論理セットが従来技術
においてデータを通過するための通路として機械的に見
られていたが、実際には関数論理セットは関数論理セッ
トの全体の実行時間を減少するためのチャンスとみなす
ことができること、第３に、ＲＴＬパラダイムは関数論
理とメモリ装置の間の有用または一体的相互接続の効果
の分析に反対すること、第４に、従来技術における関数
論理の強調はアルゴリズム実装のあらゆる水準で個別の
タイミング回路の生成のための局部的フィードバックを
含む設計に強く反対すること等から新規のパラダイムに
注意を払っていない。

【００３４】本発明はザイリンクスＸＣ４０００シリー
ズ（ザイリンクス社、カリフォルニア州サンノゼ）フィ
ールドプログラマブルゲートアレイ（ＦＰＧＡ）などの
再設定可能な論理装置（ＲＬＤ）において実施するのが
好ましい。ＲＬＤは一組の設定可能な論理ブロック（Ｃ
ＬＢ）から構成される。それぞれのＣＬＢは望ましくは
少くともひとつの関数ジェネレータと１つまたはそれ以
上のキャリー論理素子を含む。当業者には周知のよう
に、ＦＰＧＡの内部構造は設定データセットまたは設定
ビット列を用いて動的に再設定することができる。何ら
かの任意のＣＬＢ内部で、特定の論理関数が設定ビット
列にしたがって関数ジェネレータ経由で生成される。そ
れぞれの関数ジェネレータは特定の安定した信号伝播遅
延を有する。たとえば、ザイリンクスＸＣ４０００シリ
ーズＣＬＢでは、第１と第２の関数ジェネレータ
（「Ｆ」および「Ｇ」型）のそれぞれが約４．５ナノ秒
の伝播遅延を有し、第３の関数ジェネレータ（「Ｈ」
型）は約２．５ナノ秒の伝播遅延を有する。キャリー論
理素子は典型的に非常に小さく安定した伝播遅延を有す
るように設計されたキャリー伝播遅延を含むことが当業
者には理解されよう。ザイリンクスＸＣ４０００シリー
ズＦＰＧＡ内部のキャリー伝播論理は１．５ナノ秒の伝
播遅延を有する。

【００３５】本発明はＲＬＤ内部の資源を組み合わせる
ことにより多段階のフィードバックを作成し各種内部伝
播遅延を発生する。このフィードバックはＲＬＤ内部の
１つまたはそれ以上の関数論理セットを駆動するための
個別のタイミング回路を作成するために使用する。好ま
しくは、本発明は「純粋な」遅延にもっぱら依存するか
わりに「内部」遅延を使用する。内部遅延は伝播が最小
パルス幅を必要とするような遅延と定義され、一方純粋
遅延は伝播遅延が基本的にパルス幅とは無関係な遅延で
ある。有利にも、内部遅延は安定し、充分に制御される
遅延である。本発明はＲＬＤ内部で実施する必要がな
く、他の従来周知の論理装置から構成できることは当業
者には理解されよう。

【００３６】本明細書ではＸビット×Ｙビット乗算を実
施してＰビットの積を得る（ここでＸ、Ｙ、Ｐは整数）
ような関数論理セットを開示するが、関数論理セットは
広範囲の別のアルゴリズムを実行するように設計できる
ことも当業者には理解されよう。このような別のアルゴ
リズムには、何らかの種類の算術、論理、グラフィッ
ク、ワードプロセシング、信号処理、またはネットワー
ク演算を実行するための段階を含むことができる。たと
えば、本発明はＲＬＤの内部ランダム・アクセス・メモ
リ（ＲＡＭ）の効率的な使用のためのタイミング信号、
複数ポートレジスタファイルまたはＲＬＤ内部のデータ
パス配線（たとえばＦＰＧＡ内部のクロスバ交換器）を
提供するために使用できる。

【００３７】明瞭にするため、以下図７から図８では３
２ビット積を得る典型的な１６ビット×１６ビット乗算
での詳細を示す。しかし、本発明は１６ビット以上また
は以下の乗算を実施できることが当業者には理解されよ
う。また、本明細書の残りの部分では、以下に説明する
信号およびビットは好ましくは２つの状態、論理値
「１」と論理値「０」だけを有する。本発明の要素は状
態遷移の立ち上がり端にだけ（即ち論理値「０」から論
理値「１」への遷移）応答するように説明するが、ＲＬ
Ｄは立ち上がり端だけまたは立ち上がりおよび立ち下が
り端両方の状態遷移に応答するように設定できることが
当業者には理解されよう。

【００３８】図１は、自己刻時式アルゴリズム実行のた
めの装置２０の好適実施例のブロック図である。装置２
０は入力バッファ２２、関数論理２４、出力バッファ２
６、同期状態マシン３０、パルスシーケンサ３４を含
む。入力バッファ２２は、外部回路（図示していない）
が線２９の入力イネーブル信号を状態「１」に保持する
度に外部回路から線１９経由で受信したＸビットの被乗
数またはＹビット乗数どちらかを読み込み、他方線２９
で基準クロック信号を受信する従来周知の装置である。
基準クロックは、好ましくは位相同期可変周波数クロッ
クおよびメッセージングと題する米国特許出願第０８／
５０１，９７０号に記載されているクロック発生機構を
用いて実装する。何らかの従来周知のクロック生成手段
が代わりに基準クロックを提供できることは当業者には
理解されよう。

【００３９】入力バッファ２２は関数論理２４へＸビッ
ト被乗数を線２１経由で、またＹビット乗数を線２３経
由で出力する。関数論理２４は被乗数と乗数を受信し、
乗算アルゴリズムにしたがってパルスシーケンサ３４に
依存するが基準クロックには依存しないタイミング速度
でこれらを乗算する。関数論理２４が乗算アルゴリズム
を実行するのに必要な時間はアルゴリズム実行時間であ
る。関数論理２４内部の伝播遅延がアルゴリズム実行時
間を決定し、関数論理を構成する一組の論理装置に基づ
いて従来は計算されている。関数論理２４は線２５を介
して出力バッファ２６へＰビット積を出力する。関数論
理２４の詳細は図７を参照して後述する。出力バッファ
２６は従来周知の形式で、外部回路が出力イネーブル信
号を論理値「１」に保持する度にＰビット積を読み込み
外部回路へ線２７経由で出力し、同時に線２８経由で基
準クロックを受信する。

【００４０】同期状態マシン３０は従来技術で周知の種
類で線２８の基準クロックが２回トリガし外部クロック
が同時に線２９の入力イネーブル信号を論理値「１」状
態に保持した後、線３２の状態信号９０（図１２参照）
を論理値「１」に遷移させる。

【００４１】同期状態マシン３０は従来技術で周知の種
類で線２８の基準クロックが２回トリガし外部クロック
が同時に線２９の入力イネーブル信号を論理値「１」状
態に保持した後、線３２の開始信号９０（図１２参照）
を論理値「１」に遷移させる。同期状態マシン３０は２
回基準クロックがトグルするのを待って開始信号９０を
論理値「１」に設定し、入力バッファ２２が外部回路か
らＸビット被乗数とＹビット乗数を両方とも順次受信で
きるようにする。

【００４２】パルスシーケンサ３４は同期状態マシン３
０からの線３２の開始信号９０をモニタし、開始信号９
０が論理値「１」に遷移した時に線３３から関数論理２
４へ一組の信号を生成して送出する。パルスシーケンサ
３４の動作の詳細と出力する信号の組については図２を
参照して後述する。装置２０が物理装置で実施されるか
または任意の物理装置の制約にしたがって設計される
と、関数論理２４の伝播遅延とパルスシーケンサ３４の
タイミング速度が分かるようになる。つまり、出力デー
タは入力データが入力バッファ２２に刻時された時点か
ら周知の時間内に出力バッファ２６に存在することにな
る。この周知の時間は装置温度と装置のエージングの関
数として物理装置の通常の性能変動により僅かに変動す
る。しかし、後述するようにパルスシーケンサ３４は関
数論理２４の内蔵部分とするのが好ましいことから、パ
ルスシーケンサ３４と関数論理２４の両方が同じ温度と
時間的変化を受けることになる。その結果、パルスシー
ケンサ３４と関数論理２４は高度に一致し、パルスシー
ケンサ３４は関数論理２４をオーバクロックしたりアン
ダークロックすることがない。

【００４３】図２を参照すると、本発明のパルスシーケ
ンサ３４の好適実施例のブロック図が示してある。パル
スシーケンサ３４は開始論理３６と、遅延ユニット３８
と、パルスカウンタ４０と、シーケンスゲート論理４２
とを含む。パルスシーケンサ３４のパルス速度、パルス
持続時間、パルス周期（もしあれば）も駆動する関数論
理２４について最適化するのが望ましい。パルスシーケ
ンサ３４は関数論理２４に類似の論理装置を使用して前
述したように温度とエージングの影響に同様に応答する
ように実装するのも好ましい。以下では関数論理２４の
組全体を駆動するパルスシーケンサ３４をひとつだけ説
明するが、複数のパルスシーケンサ３４を使用して、関
数論理２４動作中に異なる速度で異なる時刻に関数論理
２４の特定のサブセットを駆動するように設計すること
もできる。このような別の実施例において、多数のパル
スシーケンサ３４がそれぞれ開始パルス１０４を受信す
るのが好ましい。

【００４４】開始信号９０が線３２で論理値「１」に遷
移すると、開始論理３６は線４３にリセット（１）パル
ス１０５（図１２参照）と線３５の開始パルスを生成す
る。リセット（１）パルス１０５はパルスカウンタ４０
を初期化する。開始論理３６の詳細については図３を参
照して後述する。遅延ユニット３８は開始パルスを受信
し、第１の既知の遅延後に線３９（図１２参照）にフィ
ードバック信号１３２を生成する。遅延ユニット３８の
詳細は図４を参照して後述する。開始論理３６は線３７
経由でフィードバック信号１３２を受信して線３５に次
の開始パルスを生成し、これにより自己刻時発振を発生
させる。自己刻時発振の周期は開始論理３６、遅延ユニ
ット３８、線３７に付随する伝播遅延で定義される。好
ましくは、開始論理３６と遅延ユニット３８はＲＬＤ内
部に物理的に配置して線３７に付随する伝播遅延が最小
になるようにする。ザイリンクスＸＣ４０００シリーズ
ＦＰＧＡを用いる典型的実施例では、従来の配置方針を
用いてＣＬＢ配置を定義した場合線３７に付随する遅延
は１．７ないし２．２ナノ秒の範囲である。パルスカウ
ンタ４０から線４１で停止信号を受信すると、開始論理
３６は線３５の開始パルス生成を停止し、自己刻時発振
を停止する。

【００４５】パルスカウンタ４０は線３９で遅延ユニッ
ト出力信号１３３を受信し、これに応じて線４４のパル
スカウントと線４１の停止信号を生成する。パルスカウ
ントは線４３経由で初期パルスカウント（１が望まし
い）にリセットされ、遅延ユニット出力信号１３３がト
グルする度にインクリメントする。パルスカウントが最
大パルスカウント数に達すると、パルスカウンタ４０は
線４１に停止信号を生成する。線４４は最大パルスカウ
ントを伝送するのに充分な多数の２進ビット線から構成
される。たとえば、１６ビット×１６ビット乗算では、
パルスカウントは後述するような理由から８状態を必要
とする。つまり、線４４は少くとも３本の２進ビット線
から構成する必要があり、本明細書ではＭＵＸ（０）９
２（最下位ビット（ＬＳＢ））、ＭＵＸ（１）９４、お
よびＭＵＸ（２）９６（最上位ビット（ＭＳＢ））（図
１２参照）とする。パルスカウンタ４０の詳細は図５を
参照して後述する。

【００４６】シーケンスゲート論理４２は線４４でパル
スカウントを受信し、また遅延ユニット出力信号１３３
を線３９で受信する。これに応じて、シーケンスゲート
論理４２はリセット（２）信号９７（図１２参照）を線
４５に生成し、部分積加算器クロック信号（ＰＰＳ−Ｃ
ＬＫ）９８（図１２参照）、積アキュムレータクロック
（１）信号（ＰＡ−ＣＬＫ（１）９９（図１２参照）を
線４７に、線４８にはＰＡ−ＣＬＫ（２）１００、線４
９にはＰＡ−ＣＬＫ（３）１０１を生成する。それぞれ
のＣＬＫ９８、９９、１００、１０１はパルスカウント
と遅延ユニット出力信号１３３から導出した方形波信号
が好ましい。図１に図示したように、パルスカウント信
号４４、リセット（２）信号９７、ＰＰＳ−ＣＬＫ４
６、ＰＡ−ＣＬＫ４７、４８、４９は互いに関数論理２
４への線３３の信号出力の組として機能する。しかし自
己刻時パラダイムによれば、線３３の信号出力の組のい
ずれも線２８の基準クロックと意図的に同期しない。シ
ーケンスゲート論理４２の詳細は図６を参照して後述す
る。

【００４７】図３を参照すると、本発明の開始論理３６
の好適実施例のブロック図が示してある。開始論理３６
は図３に図示したように動作的に結合した一組の論理装
置を含む。ザイリンクスＸＣ４０００シリーズＦＰＧＡ
を用いて実現した典型的な実施例では、開始論理３６は
従来のザイリンクスライブラリ素子ＦＤＳ、ＡＮＤ２Ｂ
１、ＡＮＤ２Ｂ０およびＯＲ２Ｂ１を含む。

【００４８】図４を参照すると、本発明の遅延ユニット
３８の好適実施例のブロック図が示してある。遅延ユニ
ット３８はＲＬＤ内部に実施するのが好ましくｎを整数
とする一組のｎ個のＣＬＢ１３８、１４４、１５０、１
５４の内部のキャリー論理素子から構成される。好まし
くは、それぞれのキャリー論理素子は高速キャリー伝播
回路を含む。遅延ユニット３８はさらにｎ個のＣＬＢの
組の内部に関数ジェネレータのサブセットを含み、遅延
ユニット３８と遅延ユニット３８外部の論理即ち開始論
理３６、パルスカウンタ４０、シーケンスゲート論理４
２の間の信号配線を簡略化する。図示した実施例におい
て、遅延ユニット３８はキャリーイン信号の検証および
発生にそれぞれ対応する「ＥＸＡＭＩＮＥＣＩ」およ
び「ＦＯＲＣＥＣＩ」命令を用いてザイリンクスＸＣ
４０００シリーズＦＰＧＡ内に実装される。

【００４９】それぞれのＣＬＢ１３８、１４４、１５
０、１５４に使用する論理は、遅延ユニット３８に周知
の遅延（ザイリンクスＸＣ４０００キャリー論理素子で
１．５ナノ秒、またザイリンクスＸＣ４０００Ｆ型関数
ジェネレータで４．５ナノ秒）を付加する。遅延ユニッ
ト３８の動作周波数は直列接続のキャリー論理素子の個
数を増加または減少することにより変化させるのが好ま
しい。好適実施例において、最大速度自己刻時式パルス
シーケンサ３４が所望される。遅延ユニット３８を含む
ＣＬＢ１３８、１４４、１５０、１５４の個数は関数論
理２４のもっとも遅い部分に依存することになる。結果
として、関数論理２４のもっとも遅い部分は実行に
「ｔ」秒かかり、「ｔ」／２（即ち周期の半分）に等し
い合計遅延を有する「ｎ個」のＣＬＢは遅延ユニット３
８を含むのが好ましい。また、ＲＬＤのリアルタイムで
再プログラムする機能のため、遅延ユニット３８の遅延
は関数論理２４の処理演算の途中で動的に変化すること
がある。これにより、第１の関数論理２４の組の演算は
第１の自己刻時速度で実行され、第２の関数論理２４の
組のその他の演算は第２の自己刻時速度で実行され、以
下同様に続けることができる。

【００５０】第１のＣＬＢ１３８内部で、関数ジェネレ
ータ（１）１４０は線３５に開始パルスを受信し、パル
スをキャリー論理素子（１）１３９に渡す。キャリー論
理素子（１）１３９はキャリーアウト線１４２から第２
のＣＬＢ１４４へ信号を渡す。第２のＣＬＢ１４４内部
では、キャリー論理素子（２）１４５がパルスを受信し
て関数ジェネレータ（２）１４６へ渡し、さらにキャリ
ーアウト線１４８から第３のＣＬＢ１５０へパルスを転
送する。パルスを関数ジェネレータ（２）１４６へ渡す
ことでその時点で遅延ユニット３８からパルスを「タッ
プする」ことができ、線３９の遅延ユニット出力信号１
３３とすることができる。本明細書では、「タップ」は
遅延ユニット３８外部への信号の配送を容易にする遅延
ユニット３８内部の結合として定義する。実装する関数
論理２４の組によっては「タップ」は他にも遅延ユニッ
ト３８内部の別のロケーションで発生したり、またはい
くつかの位置に発生することがある。線３９がタップす
る遅延ユニット３８内部の正確な位置は、線３３にパル
スシーケンサによって生成される信号が、図１を参照し
て説明したような装置２０の動作を開始する外部回路
（図示していない）に対して位相的に整列するように選
択するのが好ましい。

【００５１】第３のＣＬＢ１５０内部では、キャリー論
理素子（３）１５１がパルスを受信しこれを次のＣＬＢ
内部のキャリー論理素子へ渡す動作を行ない、パルスが
「ｎ番目」のＣＬＢ１５４内部のキャリー論理素子
（ｎ）へ渡されるまで同じことが繰り返される。第３の
ＣＬＢ１５０と「ｎ番目」のＣＬＢ１５４の間のＣＬＢ
は同じ構造が望ましく、第３のＣＬＢ１５０と同じイン
タフェースを有するのが望ましい。第３のＣＬＢ１５０
内部で、第３のＣＬＢ１５０が遅延ユニット３８外部の
宛先へパルスを配送するためにタップしていないので遅
延ユニット３８の動作に関数ジェネレータ（３）１５２
は必要とされない。つまり、関数ジェネレータ（３）１
５２は有利にも関数論理２４の動作の一部を実装するた
めに使用される。

【００５２】ｎ番目のＣＬＢ内部では、キャリー論理素
子（ｎ）１５５がパルスを受信し、パルスを反転させて
反転パルスをフィードバック信号フィードバック信号１
３２として線３７に出力する関数ジェネレータ（ｎ）１
５６に渡す。このパルス反転を経由して、論理値「１」
と論理値「０」の間で自己刻時式発振回路が遷移する。
パルスは関数ジェネレータ（１）１４０が代わりに反転
させられることが当業者には理解されよう。

【００５３】遅延ユニット３８の動作周波数は直列に接
続したキャリー論理素子の個数を増減する（即ち「ｎ」
の値を変化させる）ことで変化し得る。別の実施例にお
いて「ｎ」はゼロでも良く、開始パルス、フィードバッ
ク信号１３２、遅延ユニット出力信号１３３が同じ信号
になる。さらに別の実施例において、遅延ユニット３８
の動作周波数は１つまたはそれ以上の関数ジェネレータ
を介してさらなる信号を配送することにより変化でき
る。さらに別の実施例において、遅延ユニット３８の動
作周波数はＲＬＤ内部にあって充分に限定された遅延特
性を有する信号配送資源を用いることで変更または調整
することができる。再設定不可能な装置において、個別
の素子が既知の最大信号伝播遅延を有するような論理を
用いて遅延ユニット３８を実施し得ることは当業者には
理解されよう。

【００５４】ここで図５を参照すると、本発明のパルス
カウンタ４０の好適実施例のブロック図が図示してあ
る。パルスカウンタ４０は図５に図示したように動作的
に結合された一組の論理装置１６０、１６２、１６４
（望ましくはライブラリ要素であるＲＯＭ１６Ｘ１、Ｆ
ＤＲ、ＡＮＤ３Ｂ３を用いてザイリンクスＸＣ４０００
シリーズＦＰＧＡで作成される）を含む。論理装置１６
０は論理装置１６２で相互に結合してパルスカウントを
実装する。論理装置１６２の現在の状態符号Ｑ３、Ｑ
２、Ｑ１、Ｑ０はパルスカウントを発生させ、それぞれ
が停止信号１３４に対応するように使用する。パルスカ
ウンタ４０は線４３でリセット（１）パルス１０５を受
信するまでインクリメントする。論理装置１６０に記憶
する符号は以下の現在状態／次状態の表から生成する。

【００５５】現在状態次状態Ｑ３Ｑ２Ｑ１Ｑ０ＲＤ３ＲＤ２ＲＤ１ＲＤ００００００００１０００１００１０００１０００１１００１１０１０００１０００１０１０１０１０１１００１１００１１１０１１１１０００１０００１０００１００１１０００１０１０１０００１０１１１０００１１００１０００１１０１１０００１１１０１０００１１１１１０００図６を参照すると、本発明のシーケンスゲート論理４２
の好適実施例のブロック図が図示してある。シーケンス
ゲート論理４２は図６に図示したように動作的に接続し
た一組の論理装置（望ましくは望ましくはライブラリ要
素Ｄ３＿８Ｅ、ＡＮＤ２Ｂ１、ＦＤ、ＦＤ＿１、ＮＯＲ
２、ＯＲ８、ＯＲ７を用いてザイリンクスＸＣ４０００
シリーズＦＰＧＡで作成される）シーケンスゲート論理
４２は図６に図示したようなグリッチ保安回路１７０を
用いて８つの状態を復号する。復号は時間的に線４４の
パルスカウントの順序である。最後のパルスカウント状
態（即ち（０，０，０））は正確に一度に復号される。
ＣＬＫ４６、４７、４８、４８は一組のグリッチ保安回
路１７０の出力の「論理和」を取ることで生成する。シ
ーケンスゲート論理４２の別の実施例で論理状態でコー
ダのド・モルガン化を用いて結線ＯＲを結線ＡＮＤゲー
トで置き換えることがＦＰＧＡ設計の当業者には理解さ
れよう。好適なシーケンスゲート論理４２は負のエッジ
でトリガされるフリップフロップと正のエッジでトリガ
されるフリップフロップを同数含み、同じ刻時がなされ
るフリップフロップどうしを連結するようなＣＬＢパッ
ケージごとに非常に高効率のデュアルフリップフロップ
方針を実行する。

【００５６】図７を参照すると、本発明の関数論理２４
の好適実施例のブロック図が図示してある。関数論理２
４はマルチプレクサ（ＭＵＸ）５０、部分積ジェネレー
タ（ＰＰＧ）５２、部分積加算器（ＰＰＳ）５４、積ア
キュムレータ（ＰＡ）５６から構成される。マルチプレ
クサ５０はＸビット被乗数を線２１に受信し、詳細は図
８を参照して後述するように、Ｓビット被乗数サブセッ
トを線４４のパルスカウントに応じて出力する。部分積
ジェネレータ５２は線２３のＹビット乗数とＳビット被
乗数サブセットを乗算して、後述の図９を参照して詳細
に説明するように一組の部分積を部分積加算器５４に出
力する。部分積加算器５４は部分積の組を組み合わせて
図１０を参照して詳細に後述するように線４６の部分積
加算器クロック信号（ＰＰＳ−ＣＬＫ）９８に応答して
積アキュムレータ５６へ部分積の和を出力する。積アキ
ュムレータ５６は開始論理３６からの線４５のリセット
（２）パルス１０７（図１２参照）を受信し、これに応
じて内部フリップフロップ（ＦＦ）をゼロにリセットす
る。リセット（２）パルス１０７の受信までは線２５に
直前のＰビット積が残っている。積アキュムレータ５６
は部分積の和を積の積算ビットのサブセットへ加算する
ことで積の積算を生成し、図１１を参照して詳細に後述
するように線４７、４８、４９のＰＡ−ＣＬＫ（１，
２，３）９９、１００、１０１（図１２参照）に応答し
て線２５にＰビット積を出力する。完全なＸビット×Ｙ
ビットの乗算は各Ｓビット被乗数サブセットがＹビット
乗数で乗算され積アキュムレータ５６に積算された後で
関数論理２４で実行される。

【００５７】図８を参照すると、関数論理２４内部のマ
ルチプレクサ５０の好適実施例のブロック図が図示して
ある。ＭＵＸ５０は第１のＭＵＸ５８と第２のＭＵＸ６
０を含む。それぞれのＭＵＸ５８、６０は線２１経由で
入力バッファ２２へ接続され、それぞれがＸビット被乗
数の半分を受信するようにしてある。第１のＭＵＸ５８
は偶数の被乗数ビット（即ち１６ビット被乗数では２の
０乗、２の２乗、２の４乗、．．．２の１４乗まで）を
受信し、一方第２のＭＵＸ６０は奇数の被乗数ビット
（即ち１６ビット被乗数では２の１乗、２の３
乗、．．．２の１５乗まで）を受信する。それぞれのＭ
ＵＸ５８、６０は線４４でパルスカウントを受信する。
Ｘビット×Ｙビット乗算の途中で、パルスカウントは初
期パルスカウントから最大パルスカウントを含むカウン
トまでインクリメントされる。１６ビット被乗数の場
合、初期パルスカウントは線４４で（０，０，１）に対
応するのが望ましく、ここで「１」はＬＳＢ、また最大
パルスカウントは（０，０，０）に対応するのが望まし
い。パルスカウントは望ましくは（０，０，１）から
（０，１，０）、（０，１，１）、（１，０，０）、
（１，０，１）、（１，１，０）、（１，１，１）さら
に（０，０，０）へ遷移する。

【００５８】第１と第２のＭＵＸ５８、６０はＳビット
の被乗数サブセットを部分積ジェネレータ５２へ出力す
る。つまり２ビット被乗数のサブセット（２のｉ乗と２
のｉ＋１乗）が部分積ジェネレータ５２へ送信される。
ここでビット２のｉ乗は第１のＭＵＸ５８から選択さ
れ、２のｉ＋１乗は第２のＭＵＸ６０から選択される。

【００５９】１６ビット乗算では、「Ｓ」は「２」に等
しく「ｉ」はパルスカウントが（０，０，１）から
（０，０，０）の範囲として０から１４までの範囲であ
るのが望ましい。

【００６０】図９を参照すると、関数論理内部の部分積
ジェネレータ５２の好適実施例のブロック図が図示して
ある。部分積ジェネレータ５２は部分積乗算器（ＰＰ
Ｍ）５１の第１の組とＰＰＭ５３の第２の組から構成さ
れ、これらの入力は第１と第２のＭＵＸ５８、６０およ
び線２３のＹビット乗数からＳビット被乗数のサブセッ
トを受信するように接続される。第１と第２の組のＰＰ
Ｍ５１、５３は部分積加算器５４に接続される。１６ビ
ット×１６ビット乗算では、ＰＰＭ５１、５３のそれぞ
れの組は並列に動作する２ビット×２ビットＰＰＭを含
み、合計３２ビットがそれぞれの乗算演算後に部分積加
算器５４へ送信される。線２３の１６ビット乗算器から
のそれぞれの２ビット乗算器対は８個のＰＰＭのひとつ
に結線されそれぞれの部分積乗算演算の間一定に保持さ
れる。それぞれのパルスカウントで、ひとつの２ビット
被乗数サブセット（即ち２のｉ乗と２のｉ＋１乗）が８
個のＰＰＭのそれぞれに結線されてパルスカウントが１
に設定された時には第１の２ビット被乗数の対（２の０
乗と２の１乗）から始まりパルスカウントが０に設定さ
れた時に最後の２ビット被乗数の対（２の１４乗と２の
１５乗）で終わる。図９で明らかにするために示してあ
るように、第１と第２のＰＰＭの組５１、５３からの２
つの１６ビット部分積のコラム位置は、従来技術で周知
のように、部分積加算器５４でビット加算するので垂直
方向に整列する。ビット２の０乗は最下位ビット（ＬＳ
Ｂ）でありビット２の１７乗は最上位ビット（ＭＳＢ）
である。１６ビット×１６ビット部分積生成について説
明したが、同じ説明がＸビット×Ｙビット部分積生成の
一般化した場合にも同様に適用されることは当業者に理
解されよう。

【００６１】図１０には、関数論理２４内の部分積加算
器５４の好適実施例のブロック図が示してある。部分積
加算器５４はＰＰＳ加算器６４、ＰＰＳインクリメント
加算器６６、一組のＰＰＳフリップフロップ６８を含
む。部分積加算器５４は部分積ジェネレータ５２で生成
された２つの部分積を受信するように結合される。部分
積加算器５４は２つの部分積を加算して部分積の和を生
成する。１６ビット×１６ビットの乗算の場合には、第
１の組のＰＰＭ５１からの２つのＬＳＢ（２の０乗〜と
２の１乗）が直接ＰＰＳフリップフロップ６８で受信さ
れ、ＰＰＳ加算器６４は第１と第２の組のＰＰＭ５１、
５３の両方からの１４ビット（２の２乗〜２の１５乗）
を加算する。ＰＰＳインクリメント加算器６６は第２の
組のＰＰＭ５３から２つのＭＳＢ（２の１６乗〜２の１
７乗）、また１４ビットＰＰＳ加算器６４からの桁上げ
（キャリーアウト）を受信し、１８ビット部分積の和
（２の０乗〜２の１７乗）が生成され出力される。加算
から得られた部分積の和は線４６の部分積加算器クロッ
ク信号（ＰＰＳ−ＣＬＫ）９８のトグルに応答してＰＰ
Ｓフリップフロップ６８に記憶される。

【００６２】図１１を参照すると、関数論理２４の積ア
キュムレータ５６の好適実施例のブロック図が示してあ
る。積アキュムレータ５６は、部分積加算器５４から部
分積の和を受信して積算を実行するように結合されたＰ
Ａ加算器７０と、ＰＡインクリメント加算器７１と、最
終的にＰビット積を格納するための一組のＰＡフリップ
フロップの組７２，７４，７６，７８，８０，８２，８
４，８６，８８を含む。１６ビット×１６ビット乗算の
場合では、ＰＡ加算器７０は１６ビット加算器であり、
ＰＡインクリメント加算器７１は２ビットインクリメン
ト加算器であり、ＰＡフリップフロップの組７２，７
４，７６，７８，８０，８２，８４，８６，８８は、３
２ビットの積（ｐの０乗からｐの３１乗、ここでｐの０
乗がＬＳＢ、ｐの３１乗がＭＳＢ）を記憶するための第
１のフリップフロップの組７２、第２のフリップフロッ
プの組７４、第３のフリップフロップの組７６、第４の
フリップフロップの組７８、第５のフリップフロップの
組８０、第６のフリップフロップの組８２、第７のフリ
ップフロップの組８４、第８のフリップフロップの組８
６、第９のフリップフロップの組８８を含む。部分積加
算器５４から受信した第１の部分積の和からの２つのＬ
ＳＢ（２の０乗〜２の１乗）は線４７のＰＡ−ＣＬＫ
（１）信号９９の昇端に応じて第２のフリップフロップ
の組７４に格納され、３２ビット積の２つのＬＳＢ（ｐ
の０乗〜ｐの１乗）になる。１６ビット積積算のサブセ
ット（ＰＡ加算器７０とＰＡインクリメント加算器７１
の出力からのビット２の１乗から２の１７乗）は線４８
の積アキュムレータクロック（２）信号１００の昇端に
応答して第１のフリップフロップ７２に格納される。Ｐ
Ａ加算器７０は部分積加算器５４から受信したそれぞれ
の部分積の和の２の０乗から２の１５乗までのビットを
加算して積の積算を発生する（ＰＡ加算器７０とＰＡイ
ンクリメント加算器７１の出力からのビット２の０乗か
ら２の１７乗）。それぞれの積の積算の２の２乗から２
の１７乗ビットまでは第１のフリップフロップの組７２
へフィードバックされる積の積算サブセットとなり，２
の０乗と２の１乗ビットの積の積算は線４９のＰＡ−Ｃ
ＬＫ（３）１０１の昇端に応答して第３から第９のフリ
ップフロップの組７６，７８，８０，８２，８４，８
６，８８のそれぞれの積の積算後に順次シフトされる。
ひとつのＰＡ−ＣＬＫ（１）信号９９がトグルした後、
ｐの０乗とｐの１乗ビットが第２のフリップフロップの
組７４に記憶され，８つのＰＡ−ＣＬＫ（２）１００が
トグルした後ｐの１６乗からｐの３１乗までのビットが
第１のフリップフロップの組７２に記憶され、７つのＰ
Ａ−ＣＬＫ（３）１０１がトグルした後、ｐの２乗とｐ
の３乗のビットが第９のフリップフロップの組８８に記
憶され、ｐの４乗とｐの５乗のビットが第８のフリップ
フロップの組８６に記憶され、ｐの６乗とｐの７乗のビ
ットが第７のフリップフロップの組８４に記憶され、ｐ
の８乗とｐの９乗のビットが第６のフリップフロップの
組８２に記憶され、ｐの１０乗とｐの１１乗のビットが
第５のフリップフロップの組８０に記憶され、ｐの１２
乗とｐの１３乗のビットが第４のフリップフロップの組
７８に記憶され、ｐの１４乗とｐの１５乗のビットが第
３のフリップフロップの組７６に記憶される。３２ビッ
ト積（ｐの０乗からｐの３１乗のビット）が線２５から
出力バッファ２６へ送出される。

【００６３】ここで図１２を参照すると、本発明の動作
の好適タイミング図８９が示してある。図１２に示して
あるタイミング波形は理想的なものであるから、論理作
用は何らかの状態遷移の瞬間に発生するものと考える。
タイミング図８９は開始信号９０と、Ｑ開始信号１２
８、開始パルス信号１３０、フィードバック信号１３
２、遅延ユニット出力信号１３３、停止信号１３４、リ
セット（１）信号９１、ＭＵＸ（０）信号９２、ＭＵＸ
（１）信号９４、ＭＵＸ（２）信号９６、ＰＰＳ−ＣＬ
Ｋ信号９８、リセット（２）信号９７、ＰＡ−ＣＬＫ
（１）信号９９、ＰＡ−ＣＬＫ（２）信号１００、ＰＡ
−ＣＬＫ（３）信号１０１、積信号１０２、第１の開始
信号１０４、次の開始信号１０６、第１のＰＰＳ−ＣＬ
Ｋ信号１０８、第１のＰＡ−ＣＬＫ（１）信号１０９、
第１のＰＡ−ＣＬＫ（２）信号１１０、第１のＰＡ−Ｃ
ＬＫ（３）信号１１２、積計算時間１１４を含む。第１
の開始信号１０４は図２に図示したように線３２でパル
スシーケンサ３４が受信する。第１の開始信号１０４に
応答して、開始論理３６は、リセット（１）パルス１０
５を線４３から送出しＭＵＸ（０）信号９２、ＭＵＸ
（１）信号９４、ＭＵＸ（２）信号９６をそれぞれ線４
４からマルチプレクサ５０へ送信することにより、ＭＵ
Ｘ（０）信号９２（ＬＳＢ）、ＭＵＸ（１）信号９４、
ＭＵＸ（２）信号９６（ＭＳＢ）をそれぞれ初期化す
る。これに応答して、マルチプレクサ５０は前述のよう
に１６ビット×１６ビット乗算で第１の２ビット被乗数
の対（２の０乗と２の１乗）を選択する。シーケンスゲ
ート論理４２は第１の１８ビット部分積の和がＰＰＳフ
リップフロップ６８入力に現われるまで部分積加算器５
４への第１のＰＰＳ−ＣＬＫ信号１０８送出を遅延させ
る。第１の１８ビット部分積の和がＰＰＳフリップフロ
ップ６８に記憶されてから、ＭＵＸ（０）信号９２、Ｍ
ＵＸ（１）信号９４、ＭＵＸ（２）信号９６が次の１８
ビット部分積の和の準備として次の状態（即ち（０，
１，０））にインクリメントされる。シーケンスゲート
論理４２も第１の１８ビット部分積の和が第２のフリッ
プフロップの組７４入力に現われるまで第１のＰＡ−Ｃ
ＬＫ（１）信号１０９送出を遅延させる。ＰＡ−ＣＬＫ
（１）信号１０９が線４７に送出される直前に、開始論
理３６がリセット（２）パルス１０７を線４５に生成し
て直前のＰビットの積信号１０２をクリアする。ＰＡ−
ＣＬＫ（１）信号９９は１６ビット×１６ビット乗算演
算が完了するごとに１回づつトグルする。線４８の第１
のＰＡ−ＣＬＫ（２）信号１１０は第１のフリップフロ
ップの組７２に出現した後でのみ生成され、この後ＰＡ
−ＣＬＫ（２）１００は第１のフリップフロップの組７
２に次の１６ビット積算のサブセットが現われるごとに
トグルする。ＰＡ−ＣＬＫ（２）１００は１６ビット×
１６ビット乗算演算が完了する度に８回トグルする。線
４９の第１のＰＡ−ＣＬＫ（３）信号１１２は第２の１
８ビット積の積算が第３のフリップフロップの組７６の
入力に出現した後でのみ生成され、この後次の１８ビッ
ト積の積算が第１のフリップフロップの組７２の入力に
出現する度にＰＡ−ＣＬＫ（３）信号１０１がトグルす
る。ＰＡ−ＣＬＫ（３）信号１０１は完全な１６ビット
×１６ビット乗算演算の度ごとに７回トグルする。本発
明を実施する物理装置に存在する既知の伝播遅延によ
り、積信号１０２は積計算時間１１４内で計算されるこ
とが分かる。その結果、次の開始信号１０６がパルスシ
ーケンサ３４に送出できるようにする第１の開始信号１
０４のあとのもっとも速い時間は積信号１０２が安定し
た後である．１６ビット×１６ビット乗算を説明した
が、Ｘビット×Ｙビット乗算を同様の方法で実行できる
ことは当業者には理解されよう。

【００６４】ここで図１３を参照すると、本発明で実行
する１６ビット×１６ビット乗算のための好適な部分積
加算のマトリクスが図示してある。１６ビット×１６ビ
ット乗算では、部分積加算器５４は８回の加算を行ない
積アキュムレータ５６は７回の積算を行ない、最後に前
述したような３２ビット積が線２５から出力バッファ２
６へ出力される。マトリクスの上部では、３２ビット積
のそれぞれのビットについて１カラムが図示してあり、
ＬＳＢは２の０乗、またＭＳＢは２の３１乗である。
「Ｉ、II、III、IV、Ｖ、VI、VII、VIII」と標識してあ
るマトリクスの部分を参照すると、部分積ジェネレータ
５２内部の８個の部分積乗算器６２の配列が図示してあ
る。「Ｉ」の部分では１６ビット被乗数の２の０乗およ
び２の１乗ビットが１６ビット乗数と乗算される。「I
I」の部分では１６ビット被乗数の２の２乗および２の
３乗ビットが１６ビット乗数と乗算される。このように
「VIII」の部分で１６ビット被乗数の２の１４乗および
２の１５乗ビットが１６ビット乗数と乗算されるまで続
く。積アキュムレータ５６はマトリクス内に示された方
法で８つの部分全てを加算し，３２ビットの積を得る。

【００６５】図１４を参照すると、本発明にしたがって
実行される８ビット×８ビット乗算での好適な部分積加
算のマトリクスが図示してある．８ビット×８ビット乗
算では、部分積加算器５４は４回の加算を行ない積アキ
ュムレータ５６が３回の積算を行ない、前述のように線
２５から出力バッファ２６へ１６ビット積が出力される
ように設計できる。マトリクス上部では、１６ビット積
のそれぞれのビットについてひとつのカラムが図示して
あり、ＬＳＢは２の０乗、ＭＳＢは２の１５乗である。
「Ｉ、II、III、IV」と標識してあるマトリクスの部分
を参照すると、部分積ジェネレータ５２内部のここでは
４個の部分積乗算器６２の配列が図示してある。「Ｉ」
の部分では８ビット被乗数の２の０乗ビットと２の１乗
ビットが８ビット乗数と乗算される。「II」の部分では
８ビット被乗数の２の２乗と２の３乗ビットが８ビット
乗数と乗算される。このように部分「IV」で８ビット被
乗数の２の６乗と２の７乗ビットが８ビット乗数と乗算
されるまで続く。積アキュムレータ５６はマトリクス内
に示したような方法で４つの部分を加算し，１６ビット
積を得る。

【００６６】図１５をここで参照すると、自己刻時式ア
ルゴリズム実行のための好適な方法のフローチャートが
示してある。好適な方法はステップ２００から始まり、
線２９の入力イネーブル信号が論理値「１」に設定され
る時に基準クロックからのトグルにより、前述したよう
な方法で入力バッファ２２が線２１と線２３の入力デー
タを基準クロックのトグルと同期して関数論理２４へ転
送する。次に、ステップ２０２では、線３２の開始信号
９０の論理値「０」から論理値「１」へのトグルに応答
して、パルスシーケンサ３４が線３３に最大速度パルス
シーケンスを発生し、関数論理２４についてのアルゴリ
ズム実行時間に依存するが線の基準クロック２８とは無
関係な速度で関数論理２４を駆動する。ステップ２０２
は図１６で詳細に説明する。ステップ２０４では、関数
論理２４が線３３の最大速度パルスシーケンスに応答し
て線２５に出力データを生成する。ステップ２０４は図
１２で詳細に説明する。ステップ２０６では、関数論理
２４から線２５を介して出力バッファ２６へ、線２８の
基準クロックからのトグルに同期しまたこれに応答して
転送され、同時に前述のように線３１の出力イネーブル
が論理値「１」に設定される。ステップ２０６の後、好
適な方法は終了する。

【００６７】図１６をここで参照すると、パルスシーケ
ンス（図１０のステップ２０２）を生成するための好適
な方法のフローチャートが示してある。好適な方法はス
テップ２５０から始まり、開始論理３６が線３２の開始
信号９０の開始と線４１の停止信号を監視する。ステッ
プ２５２で、開始信号９０が論理値「１」に遷移し停止
信号が論理値「０」のままだと、本方法はステップ２５
４へ進み、それ以外の場合にはステップ２５０へ戻る。
ステップ２５４では、開始論理３６がパルスカウンタ４
０を前述のように初期化する。ステップ２５５では開始
論理３６が前述のように遅延ユニット３８へ開始パルス
を送信する。次にステップ２５６では、前述のように遅
延ユニット出力信号１３３に応答して、パルスカウンタ
４０がパルスカウント信号（即ち１６ビット×１６ビッ
ト乗算の場合にはＭＵＸ（０）信号９２、ＭＵＸ（１）
信号９４、ＭＵＸ（２）信号９６）をインクリメントす
る。遅延ユニット出力信号１３３がタップされる遅延ユ
ニット３８内部の位置は、パルスシーケンサ３４のタイ
ミングパルスが装置２０に結合した外部回路と位相整列
するように変化できる。ステップ２５８では、パルスカ
ウント信号に応じて、前述の方法でシーケンスゲート論
理４２がＰＰＳ−ＣＬＫ信号９８とＰＡ−ＣＬＫ（１）
信号９９、ＰＡ−ＣＬＫ（２）信号１００、ＰＡ−ＣＬ
Ｋ（３）信号１０１を生成する。ステップ２６０では、
パルスカウント信号が最大のパルスカウント信号と等し
い場合、本方法はステップ２６２に進み、それ以外では
ステップ２５６に戻る。ステップ２６２では、パルスカ
ウンタ４０が線４１の停止信号を論理値「１」に設定し
て遅延ユニット３８への開始パルス送信を停止する。ス
テップ２６２で好適な方法は終了する。

【００６８】ここで図１７を参照すると、パルスシーケ
ンス（図１７のステップ２０４）に応じて出力データを
生成するための好適な方法のフローチャートが示してあ
る。

【００６９】好適な方法はステップ３００から始まり、
前述のようにマルチプレクサ５０がＸビット被乗数を入
力し、部分積ジェネレータ５２がＹビット乗数を入力
し、開始論理３６が部分積和と積の積算をゼロに初期化
する。ステップ３０２では、前述のように、マルチプレ
クサ５０は次のＳビット被乗数サブセットを選択する。
ステップ３０４では部分積ジェネレータ５２が現在のＳ
ビット被乗数サブセット（即ち、現在のサブセットとは
ステップ３０２で選択された次のサブセット）をＹビッ
ト乗数で乗算して前述のように部分積加算器５４へ送信
する部分積を生成する。ステップ３０６では、部分積加
算器５４が部分積の和を生成して前述した方法で積アキ
ュムレータ５６へ送信する。ステップ３０８では、積ア
キュムレータ５６が部分積の和を前述のように積の積算
に加算する。ステップ３１０では、次のＳビット被乗数
サブセットをさらにＹビット乗数と乗算しなければなら
ない場合、本方法はステップ３０２に戻り、それ以外の
場合にはステップ３１２へ進む。ステップ３１２では、
積アキュムレータ５６がＰビット積を出力バッファ２６
へ出力する。ステップ３１２の後好適な方法は終了す
る。

【００７０】本発明は計算システムの状況において使用
するのが望ましい。従来技術において、特定のアルゴリ
ズムの高速実装を提供するように設計された回路は多数
の回路層から構成されていた。それぞれの回路層は一組
の信号を受信し、特定の組の演算を実行し、一組の結果
を基準クロックと同期して出力する。信号はひとつの回
路層から別の回路層へ転送される。このような従来技術
の回路設計では多数の回路層が必要とされることが多
く、多量のハードウェア資源の使用が望まれなくとも必
要となる。従来技術に対し、本発明は最小数のハードウ
ェア資源を最大の自己刻時速度で最大限に再利用し、結
果を生成するアルゴリズムを実現するものである。つま
り、開始信号の受信から停止信号の生成に続けて結果を
発生するまで同じハードウェア資源の組み合わせを繰り
返し使用する。本発明は従来技術の高速回路で必要とさ
れるよりも明らかに少ないハードウェア資源を用い、何
らかの有意な結果生成速度のペナルティに苦しめられる
ことなくアルゴリズムを実装するための方法を提供す
る。これは本発明の１つまたはそれ以上の版をＲＬＤに
実装する際に特に有利である。

【００７１】前述した本発明は現行の論理回路設計に対
してその他多くの利点を得られることが当業者に理解さ
れよう。本発明は現在の非同期論理回路設計の観点で特
に有利である。たとえば、本発明は演算タスクの完了時
に「完了信号」の生成を必要としないこと、既知の予測
可能な完了時間を有すること、外部刻時要素を必要とせ
ず、かわりにそれ自身の内蔵パルスシーケンサによるタ
イミング素子を有すること、データに依存しない完了時
間を有すること、外部回路と同期的にインタフェースで
きること、外部回路とのデータ交換でコヒーレントな位
相が実現できること、タイミング素子に遅延を付加する
場合追加の局部的な回路の複雑さしか追加されないこ
と、また外部回路のシステム全体にではなく局部的な一
組の回路だけに性能が影響することなどである。

【００７２】本発明はいくつかの好適実施例を参照して
説明したが、各種の変更を提供できることが当業者には
理解されよう。このような変化は本発明の別の実施例を
提供できる。たとえば、遅延ユニット３８はＲＬＤ設定
に続けて連続的にパルスをリサイクルするように設計す
ることができ、これによって開始論理３６を排除するこ
とができよう。このような実施例では、ＲＳフリップフ
ロップによってマルチプレクサから遅延ユニット出力信
号をパルスカウンタ４０へ、また開始信号に応じてシー
ケンスゲート論理４２へ渡すようにできる。関数論理が
自己刻時式乗算回路の場合に制限されないことが当業者
には理解されよう。関数論理は自己刻時式除算回路、自
己刻時式コンボルバ回路、自己刻時式信号プロセッサ等
を含みこれらに制限されない関数を提供できる。好適実
施例に対する変化および変更は本発明により提供される
ものであって、後述の請求項によってのみ制限される。

【００７３】

【発明の効果】本発明は上述のように構成したので、選
択したアルゴリズムを実行するように設計した関数論理
セットと遅延ユニットを対にすることで、まず、第１に
他の関数論理セットを駆動する全ての基準クロックと独
立してできる限り高速に選択したアルゴリズムを実行す
る。つまり、周知のタイミング装置およびその方法とは
対称的に、アルゴリズムを実施する全ての機能論理セッ
トのタイミング特性は基準クロックの速度に制限された
り依存する必要がない。第２に、一組の自己刻時式パル
スの生成に応じてアルゴリズムを実施する関数論理セッ
トに基づいた自己刻時速度でデータ演算する。第３に、
他の関数論理セットで受信すべき特定の既知の時刻にデ
ータを出力する。その結果、本発明の装置ならびに方法
はひとつの関数論理セットを他の関数論理セットまたは
基準クロックの動作速度と無関係な速度で動作させるこ
とができるため、ハードウェア設計を簡略化しつつ最大
限可能なアルゴリズム実行速度を維持することが可能
で、従来技術に対して特に有利である。

【図面の簡単な説明】

【図１】本発明の実施の一形態を示す自己刻時式アルゴ
リズム実行のための装置の好適実施例のブロック図であ
る。

【図２】本発明のパルスシーケンサの好適実施例のブロ
ック図である。

【図３】パルスシーケンサ内部の開始論理の好適実施例
のブロック図である。

【図４】パルスシーケンサ内部の遅延ユニットの好適実
施例のブロック図である。

【図５】パルスシーケンサ内部のパルスカウンタの好適
実施例のブロック図である。

【図６】パルスシーケンサ内部のシーケンスゲート論理
の好適実施例のブロック図である。

【図７】本発明の関数論理の好適実施例のブロック図で
ある。

【図８】関数論理内部のマルチプレクサの好適実施例の
ブロック図である。

【図９】関数論理内部の部分積ジェネレータの好適実施
例のブロック図である。

【図１０】関数論理内部の部分積加算器の好適実施例の
ブロック図である。

【図１１】関数論理内部の積アキュムレータの好適実施
例のブロック図である。

【図１２】本発明の動作を示す好適タイミング図であ
る。

【図１３】本発明の１６ビット×１６ビット乗算のため
の好適部分積加算を示すマトリクスである。

【図１４】本発明の８ビット×８ビット乗算のための部
分積加算を示すマトリクスである。

【図１５】自己刻時式アルゴリズム実行のための好適な
方法のフローチャートである。

【図１６】パルスシーケンスを生成するための好適な方
法のフローチャートである。

【図１７】パルスシーケンスに応じて出力データを生成
するための好適な方法のフローチャートである。

【符号の説明】

２４関数論理２８基準クロック

Claims

【特許請求の範囲】

【請求項１】第１の速度で入力データを受信するよう
に結合され、前記第１の速度とは独立した第２の速度で
出力データを生成し、前記第１の速度で前記出力データ
を送信するように結合される関数論理の組と、前記第２
の速度に対応する自己刻時式パルスシーケンスを生成
し、前記関数論理を制御するように結合されたパルスシ
ーケンサとを含むことを特徴とする高速コンピュータに
おけるタイミング信号発生装置。
【請求項２】自己刻時式アルゴリズム実行システムを
制御するための装置であって、前記自己刻時式アルゴリ
ズム実行システムは入力データを受信して一組の制御信
号に応じて出力データを生成する関数論理を含み、前記
装置は、開始信号を受信するように結合されてこれに応
じて開始パルスを生成する開始論理と、前記開始パル
スを受信するように結合されてこれに応じて遅延ユニッ
ト出力信号とフィードバック信号とを生成する遅延ユニ
ットと、前記遅延ユニット出力信号を受信するように結
合されてこれに応じてパルスカウント信号を選択し選択
的に停止信号を生成するパルスカウンタと、前記パルス
カウント信号を受信するように結合されてこれに応じて
前記一組の制御信号を生成するシーケンスゲート論理と
を含み、前記開始論理は前記フィードバック信号を受信
し応答的に前記停止信号が生成されない場合には前記開
始パルスを再生成するように結合されることを特徴とす
る高速コンピュータにおけるタイミング信号発生装置。
【請求項３】一組の関数論理とパルスジェネレータを
含む装置において自己刻時式アルゴリズム実行のための
方法であって、前記方法は、第１の速度で入力データを
受信するステップと、前記第１の速度と無関係な第２の
速度で自己刻時式パルスシーケンスを生成するステップ
と、前記パルスシーケンスに応答して前記第２の速度で
前記入力データを処理するステップと、前記第１の速度
で出力データを出力するステップとを含むことを特徴と
する高速コンピュータにおけるタイミング信号発生方
法。
【請求項４】自己刻時式アルゴリズム実行のための装
置であって、第１の速度で入力データを受信する手段
と、前記第１の速度と無関係な第２の速度で自己刻時式
パルスシーケンスを生成する手段と、前記第２の速度で
前記入力データを処理して前記自己刻時式パルスシーケ
ンスに応じて出力データを生成する手段と、前記第１の
速度で前記出力データを出力する手段とを含むことを特
徴とする高速コンピュータにおけるタイミング信号発生
装置。