(57)【要約】  本発明は、ハードウェアシステムにおける分散障害許容型クロックパルス発生であって、システムクロックパルスを複数の相互通信する障害許容クロックパルス同期化アルゴリズム（TS-Algs）により分散発生させ、任意の数のそのようなTS-Algsが過渡的障害の影響を受けやすいクロックパルス信号のユーザ定義された恒久的ネットワーク（TS-Net）を介して互いに情報を交換し、各TS-Algは、自らがそのローカルクロックパルスを発生させる一ないし複数の機能ユニット（Fu1,Fu2, ...）に割り当てられており、さらに、すべてのクロックパルスを確実な方法で周波数に関して同期させ、クロックパルスの発生および／または同期化の正確性に悪影響を及ぼすことなく、指定された数の過渡的および／または恒久的障害が起こりうるとともに、前記システムクロックパルスは、最大可能周波数を、自動的に達成する。本発明は、さらに、そのようなハードウェアシステムに関する。
2008507050.tif 000002
【特許請求の範囲】
【請求項１】
ハードウェアシステム、特にＶＬＳＩチップ、システムオンチップ、ＩＰコア、ＰＣＢおよびＰＣＢシステムにおける、分散障害許容型クロックパルス発生のための方法であって、
・外部または内部のクロック発振器を使用せずに、複数の相互通信する障害許容クロックパルス同期化アルゴリズム（TS-Algs）によって、
ｉ．任意の数の前記TS-Algsが、過渡的な障害の影響を受けやすいクロックパルス信号のユーザ定義された恒久的なネットワーク（TS-Net）を介して、相互に情報を交換し、
ｉｉ．各TS-Algを、そのローカルクロックパルスを発生させる、ひとつまたは複数の機能ユニット（Fu1, Fu2, ...）に割り当てて、
前記システムクロックパルスを分散発生させ、
・任意の二つのローカルクロックパルス信号が、最大で所与の期間内における指定された一定の数のクロックサイクル分だけ互いに異っているので、チップ上の任意の数の機能ユニット間のグローバル同期通信を可能にするグローバルシステムクロックパルスを任意のローカルクロックパルスから適切なクロックパルス変換スイッチング回路（除算器等）によって発生させることができるという意味で、確実な方法で、すべてのローカルクロックパルスを周波数に関して同期させ、
・TS-AlgsまたはTS-Netにおいて、クロックパルスの発生および／または同期化の正確性に悪影響を及ぼすことなく、指定された数の過渡的および／または恒久的障害が起こりうるとともに、
・前記システムクロックパルスは、使用される製造技術、TS-AlgsおよびTS-Netの配置と経路、ならびに現在の動作条件（温度、供給電圧等）によって決定される最大可能周波数を、自動的に達成する
ことを特徴とする方法。
【請求項２】
前記グローバルシステムクロックパルスの利用可能性が、前記チップ上の前記信号経路のエンドツーエンドの信号遅延の最大値対最小値の比にのみ依存するが、その最大値に依存するのではないことを特徴とする請求項１に記載の方法。
【請求項３】
既に動作状態にあるローカルクロックパルスの、そして、それから導かれるグローバルシステムクロックパルスの、同期化の正確性が、ハードウェアが電源投入段階にある間でも保証されることを特徴とする請求項１または請求項２に記載の方法。
【請求項４】
実装形態が、たとえば、エラスティックパイプラインやMuller-Cゲートなどの非同期論理回路により達成されることを特徴とする請求項１ないし請求項２に記載の方法。
【請求項５】
前記グローバルシステムクロックパルスの安定性がTS-Algsにおいて可変遅延素子または専用クロックパルス変換回路を用いることにより改善され、現在の遅延時間またはクロックパルス補正値が、
・製造時に統計的に、および／または、
・実行時に前記チップのそれぞれのアプリケーションにあわせて設定可能に、および／または、
・動作パラメータ（温度および／または供給電圧等）の一回のもしくは継続的な測定に基づいて自動的に
取得されることを特徴とする請求項１から２のいずれか一項に記載の方法。
【請求項６】
請求項１から５のいずれか一項に記載の方法により分散発生させた前記クロックパルスの周波数分割が、グローバルに適切に同期化されたmacrotickを利用可能にすることで、準安定性の問題のないデータ伝送を可能とすることを特徴とする、チップなどのハードウェアシステムの様々な機能ユニット間のグローバルデータ伝送方法。
【請求項７】
請求項１から５のいずれか一項に記載の方法に基づいてリセット段階中におけるローカルパルスのグローバルな同期化を保証することで、すべての機能ユニットの確定した開始時点を認識するために使用することができることを特徴とする、チップやＰＣＢやＰＣＢシステムの機能ユニットの同期リセット方法。
【請求項８】
請求項１から７のいずれか一項に記載の方法を実行するハードウェアシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
Ｉ．概観（図４および図５参照）
デジタルＶＬＳＩチップの今後の発展は、集積密度や複雑性やクロック周波数の持続的な上昇により特徴づけられる。しかし、そのことによって、すべての機能ユニット（Fu）に、同期設計パラダイムに必要な同期クロックパルスを提供することの難しさが増すことになる。
【０００２】
*  チップ上のすべての機能ユニットをアドレス指定するためには、信号は、完全なクロックパルスサイクルを（複数）必要とする。
【０００３】
*  クロックツリーのスキュー最適化のためにますますコストのかかる手続きが要求されている。
【０００４】
*  クロックツリーおよびバッファが大容量の電力と表面積を消費し、重大な電源の問題と干渉放射の原因となる。
【０００５】
*  最大クロックパルス周波数は場所と経路に基づいてのみ測定可能である（穏当な選択でなければならない）。
【０００６】
これに加えて、クロックパルス信号が古典的な単一障害点であるという事実があげられる：
*  外部の水晶振動子は、高価で、かさばり、機械的にダメージを受けやすい。
【０００７】
*  クロックツリーにおけるすべての（過渡的なものも含む）エラーはシステム障害に繋がる。
【０００８】
ところで、ＶＬＳＩチップにおいてトラックの遅延がスイッチング回数を決定するという事実があり、クロックパルス発生のための方法として、障害許容型分散システムの分野からもたらされた方法であるクロック同期（Clock synchronization）技法が代案として考えられる。この場合の基礎となる考え方は、別個のローカルクロックパルス発生ユニット（TS-Alg）をすべての（あるいは充分な数の）機能ユニットに割り当てることによって、各機能ユニットにローカルクロックパルス（microtick）を供給することである。すべてのTS-Algは、完全に相互接続されていて、そのローカルなmicrotickを互いに同期させるために、このTS-Net を利用する。
【０００９】
用いられた方法の同期の正確性π = π(Θ) は、TS-Netにおける最も遅い経路と最も速い経路との比Θにのみ左右される（実質的に遅延の影響を受けない）。所望のグローバル同期クロックパルスに一致するmacroticksは、（プログラム可能な）除算器÷πにおけるスイッチングによって、microticksから得ることができる。この方法の利点は次のような点にある：
*  チップが自らのクロックパルスを発生させるので、外部の発振器が必要でない。単純なリング発振器とは異なり、チップ全体がクロックパルス発生に関与するので、アプリオリに周波数の安定性を向上させる。また、温度補償手段を提供することもできる。
【００１０】
*  チップは、自動的に最大可能周波数で動作するが、この最大可能周波数は、TS-Netの場所と経路および動作条件により生ずる遅延に依存する。実際には、TS-Algの適切なパラメータ指定で最も遅い経路をマスクすることができる。
【００１１】
*  同期化のパラダイムは、（microticksに基づく）ローカルの機能ユニットの設計に適用可能なだけでなく、機能ユニット相互間の（microticksを介した）グローバル通信でも保持させることが可能である。
【００１２】
*  この方法は、正しいと証明可能なTS-Netにおける設定可能な数の過渡的なエラーと永久的なエラーとを許容する。
【００１３】
*  TS-Algsの数は、要求に応じて最適な数を選択可能なので、クロックパルス発生のオーバーヘッド（表面積等）をそれにより監視することができる。
【００１４】
*  また、この手順は、クロックパルスレートが高い非常に大規模なチップの場合に解決が困難な同期リセットの問題に対するエレガントな解法を提供する。
【００１５】
II.詳細説明
要約−従来の同期ＶＬＳＩチップにおけるクロックパルスの分配に伴う問題の深刻化に鑑み、外部クロックパルス源（発振器、水晶振動子−ｃｆ．図４および５）を用いることなくその問題に対処しつつもなお同期設計パラダイムを維持する新しい方法を提案する。動作原理は、「孤島領域」（一ないし複数の空間的に隣り合った機能ユニット）に対するローカルクロックパルスを、非同期に実行される分散アルゴリズムによって発生させることからなる。これらのローカルクロックパルスの保証された同期化の正確性もまた、システム全体にわたるグローバルクロックパルスの発生を可能にする。アルゴリズムの分散性と、その障害許容性と、時間関連変数（他の技術や動作条件）の変化へのフレキシブルな適合を可能とするとともに互いに物理的に大きく離隔した孤島領域間であっても高速な同期通信を可能とするその時間独立性とによって、ロバストで障害許容性のあるクロックパルスを発生させることができる。ここで説明する方法は、グローバル通信が非同期で確立されるものであり複数のローカルクロックパルス源が存在しないものであるという点でＧＡＬＳ技法とは異なる。 
１．動機
回路における電気信号の伝搬速度は、光の速度と、いわゆるＲＣ時間遅延との二つの作用の結果、大幅に制限される。通常用いられる媒体において、光の速度は、真空中の光の速度の約２／３、つまり、２×１０８ｍ／ｓないし２０ｃｍ／ｎｓとなる計算である。ＲＣ遅延とは、いわゆるＲＣ素子を構成する寄生抵抗器とコンデンサにより生ずるものである。これらのＲＣ素子もまた、信号エッジの平坦化をもたらすローパスフィルタに他ならない。振幅域におけるこの平坦化によって、最終的には時間域における信号遅延が起こり、その遅延は抵抗と静電容量との積にかなりよく一致する。
【００１６】
光の速度は、信号の伝搬速度にとっての逆らうことのできない物理的な限界を表すものだが、ＲＣ遅延の方は最適化が可能である。したがって、新しい技術の開発に際しては、寄生抵抗と静電容量の低減に常に特別な注意が払われている。とはいえ、現在でも、ＲＣ遅延が実際の速度の限界を表すものとなっている。
【００１７】
もっとも、ＲＣ遅延が最適化を通じて克服可能であり、光の速度という厳しい物理的な限界に到達したと楽観的に仮定しても、２ｃｍサイズのマイクロチップのエッジに沿って信号が伝搬するのに０．１ｎｓを要することになる。今日では一般的な１０ＧＨｚオーダーのクロックパルスレートによれば、これは、すでにひとつの完全なクロックサイクルに相当する。半導体の国際技術ロードマップ（ＩＴＲＳ０２）[ITRS02]によれば、チップの寸法がほぼ同等のままであるとして、クロックパルスレートが１年で約２５％増加すると予測されている。これは、１０年間で、チップのエッジに沿って信号が伝搬するのに３クロックパルスサイクル以上を要するようになることを意味する。この推定は、前述のＲＣ遅延を無視するものであり、特に、広域に分散化したネットワークにあっては、伝搬距離はチップのエッジの長さよりかなり長くなる。したがって、状況はより深刻である。 
特にクロックパルスの分配の場合には、一方で、ネットワークの物理的な広がりがほどよい大きさであり、他方で、ランタイム固有の位相偏移の効果が特に高いため、上述の問題がすでに非常に重要なものとなっている。チップ上に同期モデルを適切に実装することができるようにするための試みがいくつかなされつつある（[Restle01]
[Restle01][Intel02]参照）。最終的には、このモデルが−少なくともその現在のかたちでは−もはや支持することができない幻想であることが判明するのは時間の問題に過ぎない。設計上、定義された位相偏移に対する制御を行うためのまあまあ適当な方法が存在するとはいえ、主たる課題は、種類の違いや動作条件等によって異なる遅延の予測不能なばらつきに代表される。信号とクロックエッジのそれぞれに対する相対位置に対して十分な知識がない結果、いわゆる準安定性という未定義の論理状況が生じる。 
クロックパルス以外の信号においても、付随する実行時間はますます問題化している。設計の許容可能クロック周波数を、クリティカルパスにおけるゲート遅延に基づいて適切に推定することが以前はまだ容易であったが、今では、相互接続の実行時間が非常に重要な要素となっているので、同様の推定が可能なのは、場所および時間を最終決定した後となる。その結果、設計プロセスにおける最終段階にならないと修正措置を配置することができないことになるので、設計サイクルの実際の遅延やコストアップをもたらす。 
リセットラインでさえ、特別な注意が必要である。もしも、システムの始動中に、所与のクロックサイクルｋの間、リセットが停止状態になれば、同じクロックパルスサイクルにおける個々の機能ユニットがそれを検知し、それに対応した処理を行う。しかし、それらの機能ユニットのひとつが、信号遅延のため、クロックパルスサイクルｋ＋１においてのみそのリセットを検知した場合には、この非同期性は、システム始動中の予測不能な影響をもたらす可能性がある。障害注入実験[Scherrer02]の過程で、リセット信号の解釈に矛盾があったとき、処理システムが非常に敏感に反応してしまう可能性があることがわかっている。
【００１８】
したがって、総合的にみると、実行時間が常に支配的な影響力をもつことから、ＶＬＳＩチップ上の実行の同期状態を保証することは、ますます大きくなるクロックパルスレートを考慮すると、構成的技術的手段のみによっては、不可能である。同期設計パラダイムか、同期状態の定義の外挿概念など他の体系的な解法か、そのどちらかの代替手段を発見しなければならないのである。 
同時に、クロックパルスレートが大きく、許容電圧が低く、チップ上の構造が小さければ、障害率が大きくなることをあらかじめ考慮しておかなければならない[Const02][Salim01]。障害許容性を強化する手段は別にして、これには、障害許容クロックパルスの使用増加が必要となる。特に、安全が極めて重視される用途（飛行機[Truong97]）や、任務の時間が極めて長い用途（宇宙旅行[Gaisler02]）で、既にそのような実情にあり、そのような場合には多少なりとも重要なオーバーヘッドが必要となる。したがって、同期状態を達成するという課題に対する解決手段はいずれにしても、最初から、障害許容ということについても考慮しておくべきである。
【００１９】
2.従来の技術と傾向
２．１  「同期化」という用語を理解する
同期化という用語は、異なる文脈において異なる意味で使用される。二つの最も重要な解釈について以下に論述することにより用語説明とする：
位相同期とは、最も高いレベルの同期化を表す。二つ以上のクロックパルス信号が、その位相偏移が最小となるか、できる限り一定となるくらいに正確に、互いに一致するのでなければならない。したがって、同期化特性の尺度は、最大位相偏移度数である。例えば、いくつかの論理回路がロックステップモード（lock-step mode）で動作しなければならない場合、位相同期が必要となる。古典的な同期設計は、位相同期を絶対的なものとして前提しており、実行時間が決定的であることを考慮すると維持できないことがまさにこのことを示している。この場合に考慮されるクロックパルスが仮に同じソースから発生させたものであったとしても、それらの相対的な位相は、実行時間およびスキューのためにひずみを生ずるものとなる。 
時間同期（クロック同期）は、分配されるクロックの一致に関連する。同期されるクロックタイムは、通常、相関関係がまったくないローカルクロックパルス信号に由来するものであり、同期状態は、クロックインパルスを特定的に抜かしたり加えたりすることにより達成される。同期化特性は、二つのクロックタイムの間の最大偏差に基づいて評価されるものであり、これは精度と呼ばれることもある。位相同期化と比較すると、その粒度はわかる程度にきめ細かくはなく、問題は、高周波数クロックパルス内の位相偏移のひとつではなく、ローカルカウンタの示す値の（積分！）偏差のひとつである。 
基本的に、時間同期化であっても、同期化手段によってのみ達成可能である。許容性の低い水晶振動子だけを選択することは適切ではない。なぜなら、そこから得られるローカルクロックタイムは、長時間経つと互いに大きくずれていくからである。
【００２０】
２．２  クロックパルス分配
現在の設計におけるクロックパルス分配は、性能と電力消費のスペックによってますます増大する問題を示している。高クロック周波数の要求と、マイクロチップ上のゲート数の増大は、スイッチング処理数の増加と高いファンアウトによるクロックツリーの電力消費の増加を意味する。クロックパルスネットワークは、チップ全体の電力消費の２５％〜５０％を占める[Dobberpuhl92]。また、クロックサイクルの短縮化の結果、クロックスキュー（二つの異なるコンポーネントにおけるクロックパルス発生の間の差）の許容可能なマージンが減少する。したがって、現代のプロセッサの設計において、できる限りスキューのないクロックパルスの分配を保証するための相当な努力がなされなければならない。クロックパルス分配は、主に、個々のツリーレベルを統合するネットワーク構造との関連でバランスのとれたツリー（Ｈ−ツリー、Ｘ−ツリー）によって、達成される。この方法を用いて、各末端ノードへのリード長とその経路中のバッファ数とをできるだけ一致させる試みがなされており、ゼロ−スキュールーティングを提唱する者もいる[Restle02]。
【００２１】
クロックパルス分配ネットワークの多数のファンアウトを「駆動」できるようにするためには、クロックスキュー低減のためチップを横断してできるだけ均等に分配すべき多数のバッファ（数百〜数千）が必要である。各バッファは、クロックスキューの増加をもたらす製造過程の結果、その駆動電力および遅延特性に関してわずかではあるが一定の不正確さを有する[Restle01]。現代のプロセッサ設計においては、しばしば、いわゆるスキュー除去（deskewing）回路が導入される。これらの回路は、クロックパルス分配ネットワークの個々のバッファの実行時間のばらつきを補償する機能を有するプログラム可能な遅延を処理する。バッファの駆動電力およびそれに伴う遅延時間は、供給電圧および周囲温度等の動作パラメータに大きく左右される。また、ラインの抵抗は、たとえば、エレクトロマイグレーションの結果変化するので、その経路の実行時間特性に変化を来す可能性がある。高い周波数（ＧＨｚの範囲）のせいで、表皮効果（電流が導体の表面のみ流れること）も、より深刻な問題になりつつある[Chen02]。表皮効果は、リードの抵抗、ひいては実行時間特性をクロック周波数とともに変動させる。
【００２２】
上で説明したパラメータの不正確さのため、クロックスキューに対する安全性の許容範囲を広く計画する必要があるので、ＶＬＳＩチップの最大許容可能クロック周波数は実質的に低くなる。また、多くのクロックバッファの同期スイッチングは、クロックツリーのアンテナ効果の結果現実にあらわれる、電源内の無視できない干渉信号や、クロストークや、低域電磁干渉放射を生成する。
【００２３】
２．３  クロック同期化
全システム共通の時間の概念は、ノードのネットワークにおけるクロック同期化のための同期化されたクロック（カウンタ）の形で導入される。ここで、ハードウェアベースのアプローチとソフトウェアベースのアプローチとは区別可能であって、一般に、ハードウェアによる実装形態によって、プロトコルオーバーヘッドの減少とそれに伴う実行時間のばらつきの低減によって、より高い同期化の正確性が達成される[Ram90]。ｆ個のビザンチン障害ノードを許容することができるためにｎ＞３ｆ個のノードが利用可能でなければならないことは一般に真である[DHS86]。
【００２４】
クロック同期化の基本原理：
各ノードはカウンタをインクリメントするローカルクロックパルス発生器を有するとともに、すべてのノードはローカルで同一のアルゴリズムを実行する。アルゴリズムに対して関連する時間関連情報は、個々のノード間のメッセージを介して交換される。所定のインターバル（再同期化インターバル）の最後で、メッセージに基づいて計算された補正関数を入力し、ローカルカウンタの示す値をローカルクロックに適用して、アルゴリズムの新しいラウンドを開始する。
【００２５】
クロック同期化アルゴリズムは、その補正関数に基づいて３つのグループに分類することができる：
*  収束ベースの
*  コンシステンシーベースの
*  確率論的
収束ベースのアルゴリズムでは、ひとつのメッセージは、再同期化のインターバルの間に一度、すべての他ノードへ送信される。再同期化の一回のインターバルの中で、適切な数の他ノードメッセージを回収した後で、収束関数（たとえば、障害許容平均[LL88]）をこれらの時間関連メッセージに適用する。それから、その収束関数の結果にしたがって、ローカルクロックを調節する。
【００２６】
コンシステンシーベースのアルゴリズムは、すべてのゼロエラーノードがシステム全体の無矛盾の認識を有するという考えに基づくものである[Lamport85]。これは、送信機が（ビザンチン）エラーを有するか否かにかかわらず、すべてのゼロエラーノードがひとつの送信機のクロックの同一の値に合意することを意味する。仮に、送信機が正しければ、これも自身により送信された値である。収束ベースのアルゴリズムのものと同様のしかたで、ここでも、各ノードがそのクロックの現在値を再同期化インターバルごとに一回ずつ送信する。時間関連メッセージはノードにより転送（リレー）され、その結果、すべてのノードにシステムの一致した認識が存在する。（送信時点における）ノードの現在のクロックタイムをそれぞれ求めるために、すべての他ノードから受信した関連値からメジアンを算出する。そして、あらかじめ取得しておいた全ノードの無矛盾のクロック値のメジアンから、ノードのローカルクロックの新しい値を取得する。 
確率論的同期化アルゴリズムは、ローカルクロックの新しい値を求めるために、一般に、データ収集と統計的テストという２段階で進行する[Lu89]。
【００２７】
一般に、文献に提示されているアルゴリズムの機能を保証するためには、そのアルゴリズムにおける前提を想定しなければならないことに留意されたい[Ram90]。収束ベースのアルゴリズムでは、メッセージをユニークに送信機に割り当てることができなければならないが、これは、完全にネットワークされた構造によって、あるいは署名を利用して、達成することができる。また、メッセージの送信時間には上限がなくてはならず、達成することができる精度もこの限界により明確に決定される[LL84]。クロックは、開始時点で同期化されていなければならない、すなわち、クロック相互のずれは所定の限界内にあるのでなければならない。収束ベースのアルゴリズムは、ソフトウェア[SIFT78]とハードウェア[Miner92]の両方で、また、ハイブリッド形態（ソフトウェア／ハードウェアの組み合わせ）[SynUTC02]でも、実装実績がある。コンシステンシーベースのアルゴリズムの場合も、メッセージを送信機にユニークに割り当てることができなければならないが、さらに、各ゼロエラーノードにおいてシステムの同じグローバルな像を達成し、メッセージに関する非常に高いオーバーヘッドを達成するために、多くのラウンドの情報交換がなされなければならない。ここでも、アルゴリズムに要求される精度を保証するために、メッセージ伝送時間の上限が既知でなければならない。確率論的アルゴリズムは、統計的テストを実施するための適切なデータが利用可能となるまで多くのラウンドの情報交換を必要とし、そしてまた、同期化の達成は、１未満の確率でのみ保証することができる。さらに、確率論的方法は、統計的テストの実施と必要なデータの格納に要するハードウェアコストが莫大な額となるため、ソフトウェア的解法でのみ意味のある使用が可能である。
【００２８】
クロック同期化で達成可能な精度は一般に、数μｓ〜１００ｎｓのオーダーである[KKMS95][SynUTC02]。
【００２９】
２．４  障害許容クロックパルス
障害許容クロックパルスとは、多くのノードをまたがって利用可能であり、あらかじめ定義された限界（精度）で同期化され、その同期状態を損なわずに所定数のエラークロックパルス源を許容することができるクロックパルス信号と理解される。
【００３０】
障害許容クロックパルスの発生に関する文献[VanAlen91][Choi90][Vasan98]に記載されている主だった手法は、それぞれがひとつのローカルクロックパルス発生器を備えるノードであって、ｆがシステムの許容するビザンチンエラーの数を表すとき、ｎ＞３ｆとなるようなｎ個のノードについて考察する。各ノードは、二地点間接続（自身のクロックパルスも自分自身にフィードバックされる場合には、ｎ２個のリード）を介して他のすべてのノードとクロック信号を交換する。グローバルに交換されるクロック信号は、システム全体にわたって同期化させたクロックパルスを表すいわゆるmacroticksを示す。対照的に、高周波数クロックパルスは、グローバルクロックパルス信号の時間的な順序を保証するために、microticksに分割されて、個々のノードにおいて用いられる。受信したすべての（自身のものも含む）macroticksから、各ノードにおける選択関数（Voter）を利用して、基準クロックパルスを取得する。そして、必要に応じてローカルクロックパルスを、アナログまたはデジタルＰＬＬ（Phase Locked Loop: フェーズロックループ）を用いて、選択された基準クロックパルスに合わせる。
【００３１】
ゼロエラーノード間の信号実行時間はどれもほぼ同一なので、ゼロエラーノードのvoterが同一シーケンスにおけるゼロエラーノードのすべてのクロックパルス信号を（無矛盾に）検知することは、広く承認された仮説であり、[Vasan98]および[VanAlen91]の実装形態においても用いられている。実際の条件下では、クロックパルス分配のセクションで既に説明したように、クロックスキューと信号実行時間の問題がますます重要視されてきているため、このような仮説は維持することができない。異なる実行時間を補償するための手法が[Shin88]に開示されているが、これによると、２ｎ個の位相検出器と２ｎ２本のリードが必要となり、ハードウェアコストがさらにかさむことになるとともにエラーが発生しやすくなる。
【００３２】
個々のクロックパルスエッジの位相偏移によって、votersとの不一致が生ずることがあるばかりでなく、さらに、個々のノードへのvoter入力における準安定性の問題を生ずる可能性がある。個々の入力フリップフロップのセットアップとホールドの時も信号の変動が起こりうるからである。準安定性問題の確率を、専用入力バッファ回路を用いて低く抑えることはもちろん可能だが、完全にゼロにすることはできないのであって、コンセプトとしてエレガントな解法を提示するものとはいえない。
【００３３】
ＰＬＬの入力信号が基準信号に対して大きく偏移を示す場合には、ＰＬＬは信号を成功裡に調節することができないので、同期が永久に失われる可能性がある。
【００３４】
２．５  ＧＡＬＳシステム
セクション１で説明したように、チップ全体にわたる同期状態を確立することはもはや不可能であるとするなら、少なくとも、空間的に画定された領域―たとえば、ＳＯＣ（System on a chip：チップ上に構築されたシステム全体の多数の複合機能ユニットのひとつ）内の機能ユニット―どうしの同期状態を維持するよう試みることができるだろう。そして、これら同期状態の「孤島」間の通信は、非同期技術により達成可能である。その手法は、頭字語GALS（Globally Asynchronous Locally Synchronous）により知られている[Chapiro84]。ＧＡＬＳ技法は、証明された同期設計方法を機能ユニット内で継続不変に使用することを可能とするものであるが、非同期通信ユニットとのまさにそのインターフェースにおいて基本的な問題が生ずる。非同期／同期間インターフェースにおける準安定性の発生を防ぐために同期回路を使用しなければならない。このような同期装置は主に休止可能／伸長可能クロックに基づくものであり、非同期／同期インターフェースにおいて実質的に遅延時間を生じさせる[Chelcea00]。
【００３５】
ＧＡＬＳ技法に伴うもう一つの深刻な問題は、ローカルクロックパルスが完全に非同期で動作するため、ばらばらにドリフトし互いに離れていく方向にずれてしまう可能性があることである。したがって、何らかの対策を講じることなくしては交換される情報の時間的順序を確立することは不可能である。その結果、ＧＡＬＳ技法は実際に使用可能ではあるが、その現在の形態では、コンセプトとしてエレガントであるとはいえず、技術的に完成しているともいえない。
【００３６】
２．６  非同期論理回路
より必然性の高い処理として、チップ上に論理回路の全体を完全非同期に実装する方向での施策が考えられる。これは、単にクロックパルスを間引きすることによって実現できることではなく、綿密かつ系統だった処理が必要である。このテーマに関する学術論文が多年にわたり知られている（たとえば[Huffman54]参照）。デジタル論理回路のこのような非同期的な実装形態は、コンセプトとして、いくつか魅力的な利点（電力消費の低減やモジュラリティの向上など）を提供するかもしれないことは検討の対象となりうる[Myers01][Hauck95][Berkel99]。しかし、そのコンセプトの実用的な実装形態に対する方法に係る従来の提案は、価格、性能、効率の側面における現在の成熟度の点で、同期設計パラダイムのとしては、限定的な境界領域においてのみ実用となる代替案にすぎない[Steininger04]。その点に加え、ツールや既存モジュールにおいて、ひいては開発者の訓練において、同期設計が確立されているといってもその段階は、全く新しい非同期設計の世界への移行が、どのみち、やっとのことで段階的に仮にも実現することができるに過ぎないものであるのと同程度である。
【００３７】
２．７  仮想的非同期システム 
[Fai04]において提案されている分散クロック発生のための方法は、同期の世界と非同期の世界との一種の折衷案と考えることができる。ＶＬＳＩチップ上の個々の機能ユニットに集中型発振器のクロックパルスを供給するのではなく、各機能ユニットを、それぞれのクロックパルスをローカルで発生させる専用クロックパルスセルに割り当てる。これは、専用ローカル発振器を使用するのではなく、ＭＯＳＦＥＴからなるクロックパルスセルを二次元格子に配置することによって達成される。各クロックパルスセルは、専用クロックパルスラインによって４つの隣接クロックパルスセル（上下左右）に接続されている。クロックパルスセルの論理回路は、格子構造によって分散リング発振器の作用が達成されるように、クロックパルスセルが同じ状態にあるときにクロックラインを状態変化させる。
【００３８】
しかし、ローカルクロックパルス信号の各ペアごとに一定の同期の正確性を保証すべき時間同期方法それぞれに、（ほぼ）完全な接続が必要とされることが、分散アルゴリズムの理論から知られている。そのうちの後者は、グローバルな同期状態も保証されなければならない場合には、必ずしも不可欠ではない。しかし、すべてのクロックパルスセルの完全な二地点間接続を実装することが実際上不可能なので、[Fai04]に記載されている方法ではそれを達成することはできない：実際、一般に、６本のクロックラインを必要とする３Ｄ格子構造のためのクロックパルスセルの構築が困難であることは明らかである。完全な接続の場合に必要となるｎ−１本のクロックパルスラインの処理はこの方法では実装不可能である。
【００３９】
その上、[Fai04]に記載されているクロックパルスの発生は障害許容型ではない：すなわち、クロックラインのひとつにおける単一の過渡的障害が完全にクロックを機能停止させたり、ローカルでのオーバークロッキングを引き起こしたりする可能性がある。このことは、現代のＶＬＳＩチップにおいて微粒子の衝突や電源供給の変動や漂遊ピックアップにより生ずる過渡的な障害がますます増えている状況を考慮すると、許容できるものではない。
最後に、[Fai04]に記載されている分散型クロックパルス発生器の実装形態は、そこで提示されているコンセプトが技術に左右されない格子レベルに依存するものであるにもかかわらず、技術に左右されるトランジスタレベルに直接基づいている。 
要するに、[Fai04]において提示されている方法は、したがって、TS-Nets（特に完全に接続されたTS-Algs）に適合するものではなく、技術に左右され、障害許容性を有するものではなく、特に、一定の限定された同期の正確性をもたらすものではないので、機能ユニット間の同期グローバル通信を実現することができないものである。
【００４０】
３．本発明の解決手段の原理
はじめに、ここで、本発明が関与するところもの、すなわち、次のような特徴を備えるハードウェアシステム特にＶＬＳＩチップやＳＯＣやＩＰコアやＰＣＢやＰＣＢシステムにおける分散型で障害許容型のクロックパルスの発生方法について簡単な要約を提供する。
【００４１】
*  システムクロックパルスを、外部もしくは内部のクロック発振器を利用せずに、複数の相互通信障害許容クロックパルス同期化アルゴリズム（TS-Algs）によって、分散発生させる
ｉ．任意の数のそのようなTS-Algsが互いに、過渡的な故障の影響を受けやすいユーザ定義された恒久的なクロックパルス信号のネットワーク（TS-Net）を介して、情報を交換する
ｉｉ．各TS-Algは、ひとつないし複数の機能ユニット（Fu1、Fu2、・・・）に割り当てられ、その機能ユニットのローカルクロックパルスを発生させる
*  任意の２つのローカルクロックパルス信号は、所与の期間内においては、所定の定数のクロックサイクル分だけ互いに異なるので、グローバルクロックパルスが発生可能であり、チップ上の任意の数の機能ユニット間でグローバル同期通信が可能となるが、その意味で、すべてのローカルクロックパルスは周波数について確実な方法で同期される。このグローバルシステムクロックパルスは、適切なクロックパルス変換スイッチング回路（除算器等）によって、任意のローカルクロックパルスから導くことができる
*   TS-AlgsまたはTS-Netにおいては、所定数の過渡的および／または恒久的な障害が起こりうるが、クロックパルスの発生および／または同期化の正確性に悪影響を及ぼすことはない
*  システムクロックパルスは、使用する製造技術や、TS-AlgsおよびTS-Netの配置およびルーティングや、現在の動作条件（温度、供給電圧等）によって決定される、最大可能周波数を自動的に達成する。
【００４２】
この方法には、グローバルシステムクロックパルスの利用可能性が、チップ上の信号経路のエンドツーエンドの信号遅延の最大値対最小値の比にのみ依存し、その最大値に依存するのではないための規定が用意されている。 
既に動作状態にあるローカルクロックパルスの、そして、そのローカルクロックパルスから導かれるグローバルシステムクロックパルスの、同期化の正確性が、ハードウェアが電源投入段階にある間でも保証されるのであれば有利であるかもしれない。
【００４３】
実装形態が、たとえば、エラスティックパイプラインやMuller-Cゲートなどの非同期論理回路を有するものにより達成されるものであれば有益である。
【００４４】
また、TS-Algsにおいて可変遅延素子または特殊クロックパルス変換回路を用いてグローバルシステムクロックパルスの安定性を強化することも有益であるが、この場合、電流遅延時間および／またはクロックパルス補正値は、製造時に統計的に取得され、および／または実行時にチップの各アプリケーション用に構成可能で、および／または一時的ないし継続的な動作パラメータ（温度および／または供給電圧等）の測定に基づいて自動取得される。
【００４５】
本発明は、また、ハードウェアシステムの（たとえば、チップの）様々な機能ユニット間のグローバルデータ伝送のための方法であって、上述の処理に従って発生させたクロックパルスの周波数分割によってグローバルで適切に同期化されたmacrotickを利用可能にすることで、準安定性の問題のないデータ伝送を可能とする方法を含む。
【００４６】
本発明は、また、クロックパルス発生のための前記方法が、リセット段階中においてもローカルパルスのグローバルな同期を保証するものであり、したがって、すべての機能ユニットが決まった開始時点を認識するために利用可能であることを特徴とする、ＶＬＳＩチップの同期リセット方法を含む。
【００４７】
本発明は、また、そのような方法を実装するハードウェアシステムに関する。
【００４８】
セクション２における考察に基づくと、同期する孤島間の非同期通信に伴う問題への概念的にエレガントな解法を見いだすことができたとしたら、実質的に非同期な手法すなわちＧＡＬＳ技法が非常に魅力的なものであったということになるだろう。そこで、さらに、チップ上のローカルに同期化させた機能ユニット（モジュール）であって、互いに位相同期化させず、互いに周波数同期化させたものからなる構造を想定する必要がある。この文脈における「周波数同期化」とは、二またはそれ以上のクロックパルス信号の周波数を一致させることに関連する。これは、位相同期化とは対照的で、掛かる時間が長い。その合間の期間にクロックパルス間で実質的な位相偏移が起こることはまったく許容可能であるが、決定的なのは、検討対象となっている各期間の位相偏移の数がたったひとつの定数によって異なるものとなるかもしれないことである。（このことから、無限長の（すなわち十分に大きい）時間間隔で考えると、すべてのクロック信号が同数のクロックインパルスを有することになる。）クロックパルス信号にカウンタを結びつけて考えると、任意の大きい時間間隔をはさんだカウンタ値間の最大偏移が同期化特性の尺度となる。クロック同期化との関連で、この特徴は、精度といってもよいだろう。クロック同期化と違い、提案された周波数同期化の場合には、ローカルインパルスを導入したり抑制したりする（「レート補正」）および／または時間の誤差補正を施す（「状態補正」）代わりに、周波数のパリティは継続的に保証される。一般に、クロック同期化の場合の制約は（長い距離、異なる速度を有しそれぞれがローカルクロックパルスを有する等）、検討対象としている対象のチップレベルの制約とはまったく異なるものなので、その解決手段や品質ベンチマークでさえ共用できるものではない。
【００４９】
セクション２．１において提示した定義の文脈において、周波数同期化は、すなわち、位相同期化と時間同期化の折衷を表す。このことは、また、時間関連の偏移を考慮すると明らかとなる。位相同期化の場合、検討対象となるクロックパルス信号間の偏移は、どんな状況下であってもクロックパルスの半分より大きくなることはなく、時間同期化により、上述のまったく異なる前提のために、１μｓの同期化の正確性が優良とみなされる（ｃｆ．セクション２．３）−これは、１ＧＨｚで１０００クロックパルスサイクルに相当する。位相同期化をチップ全体にわたり達成することはもはや不可能であるという事実に鑑み、数クロックパルスサイクルの許容偏移を伴う周波数同期化は、無理無く言って「最大限の努力」を表すものである。
【００５０】
したがって、ＧＡＬＳ技法とは異なり、同期する孤島のローカルクロックパルスは、もはや相互に無関係ではなく、その代わり、周波数に関して同期している。このために必要な同期化は全モジュールに共通の分散アルゴリズムによってグローバル時間基準を確立することによって達成される。（ｃｆ．セクション４）。 
ＶＬＳＩチップの各モジュールまたは適切な数のモジュール（＝ひとつないしそれ以上の物理的に隣り合った機能ユニット）を、一方で、この分散アルゴリズムを実行することでグローバル時間基準の確立に貢献し、他方で、そのモジュールのためにローカルクロックパルスを導出することをもっぱらのタスクとするその目的に特化した非常にシンプルなひとつの機能ユニットにより、増加させなければならない。通常のアルゴリズムは、全ノードへの機能の複製に基づくものなので、この機能ユニットを全モジュールに対して同じ方法で実装することができる。重要な課題は、コンセプト上の段階自体における準安定性に伴う問題を除去するために非同期論理回路を用いてその機能ユニットを実装することである。また、純粋に実用上の観点から、それが必要なのは、アルゴリズムの同期的実装に必要なクロックパルスをまず最初にそのアルゴリズム自身によって発生させなければならないからである。
【００５１】
文献中で提案されている処理（位相同期化、そして時間同期化）は、複数のクロックパルス源の存在を前提とするものであり、その処理のタスクは、実質的に、それらのクロックパルス源により供給されるクロックパルス信号間の適切な同期化を確立することからなる。本稿で提案されている手法は、[Fai04]においてすでに新たな分野を開拓したまったく異なる手段を採用する：すなわち、この場合、ローカルクロックパルス発生器はなく、分散アルゴリズムにより発生させたひとつの共用仮想クロックパルス信号のローカルインスタンスがあるだけである。したがって、原則として、互いにずれた異なる信号の可能性はなく、位相偏移は、アルゴリズムの実行または処理の時間のみにより発生する。したがって、この場合、その方法の目的は、適切な規則に適合したクロックパルスを発生させることからなる。
【００５２】
その実装形態が一定の同期化の正確性を可能とするものではない[Fai04]とはまったく対照的で、後述のセクションにおいて提示した分散アルゴリズムでは、障害許容と保証された最大位相偏移（＝同期化の正確性）とがエレガントにかつ比較的容易に達成可能となる。このようにして発生させたローカルクロックパルスは、それにより供給されるモジュール上のシンプルなクロックツリーによって分配されるが、それは、所与のモジュールの機能ユニットが物理的に互いに隣り合っているため重大ではない。低周波数のグローバルクロックパルス（macrotick）上にローカルクロックパルス（microticks）を適切にマッピングすることによって、無矛盾の同期時間の基礎を最終的にすべてのモジュールに対して導くことができる[Kopetz97]。このことが可能なのは、任意の二つのローカルクロックパルス信号間の位相偏移が特定の最大値を超えることがないである。
【００５３】
同期／非同期インターフェースを伴うＧＡＬＳアーキテクチャーの既知の問題は、したがって、概念的には提案された方法によって容易に克服可能である。グローバルクロックパルスを発生させるアルゴリズムは、非同期論理回路の原理と適合するように実装されている。これは、当然、コストがかかり、煩雑なものではあるが、完全に準安定性を回避するものとなる。グローバル通信を伴わない限りにおいて、ローカル機能ユニットは、ローカルクロックパルスに基づいて、通常どおり、同期状態に設計することができる。もっとも、グローバルクロックパルスの存在があるため、グローバルデータ通信であっても、通常の同期設計によって実装することが可能である。ここでも、準安定性に伴い起こりうる問題を適切なmacroticksの選択により、完全に回避することができる。
【００５４】
まとめると、本稿の解決手段は、次のような顕著な利益をもたらそうとするものである：
*  回路に対するクロックパルスを自己発生させ、定数により限界づけられた全システムにわたる同期化の正確性を保証しつつローカルクロックパルス源（発振器、水晶振動子）に関して節約すること。
【００５５】
*  チップが、すべての時点において最大可能クロック周波数で動作する
*  複雑でエネルギーをくうグローバルクロックツリーを無批判な二地点間接続に置き換えること
*  同期の抽象観念と所与の物理的制約下で効果的な同期状態とを維持することに関する最適なトレードオフ
*  クロック信号の、より障害許容性が高く恒久的なエラー
このような動作原理の可能な実装形態を、以下のセクションで、詳細に提示する。
【００５６】
４．使用する基本アルゴリズム
4.1 基本原則
出発点は、メッセージレベルにおける、収束に基づく既存のアルゴリズム（セクション２．３参照）である[Srikanth87]。このアルゴリズムは、ｎ個の、そのすべてが二地点間の接続を用いてメッセージを介して互いに通信可能な、コンピュータノードからなる分散システムを想定するものである（完全にネットワークされた構造、図１参照）。つまり、各ノードは、ｎ個の入力とｎ個の出力（それぞれについて、ｎ−１個の他ノードから／への入出力、および、自ノードへのループバック）を備えている。最広義における通信がラウンドに基づいて行われ、無障害条件下で各ノードは、それぞれのラウンドごとにｎ個すべての出力に同時に少なくともひとつの同期化メッセージを送信する（ここでは、他の特定アプリケーションのみに対するメッセージに関しては想定しないものとする）。これらの同期化メッセージに基づく共通の時間軸が、分散合意を援用することによって確立されている。この合意は、ｎ＞３ｆとした場合のｆ個までの障害ノードについて正しく機能する（すなわち、ラウンドごとノードごとにｆ個までの障害ないし紛失メッセージが許容可能である）。したがって、システム設計の時点で、予想される障害の個数ｆが何個かについて考慮に入れることができる。[WS03]および[Widder03]において提示されている複合障害モデルを用いると、障害許容性を、実際に、より正確に要求に一致させるよう、選択することが可能である。
【００５７】
このアルゴリズムは、時間軸を、それぞれひとつのクロックパルスステップに対応するラウンドに対して昇順に番号を付けたラウンドの順番の形で送信する。ひとつのラウンドから次ラウンドへの移行は、各時点においてネットワーク上のすべての（障害のない）ノードの最低限度の同期化が保証されるという合意にしたがって、固定されている。特に、次のようなことを障害のないノードに対して保証することができる。所与の時点において、あるノードがラウンドｋにあるとすると、その同じ時点において、他のすべてのノードが、｜ｉ−ｋ｜＜Θ＋２としたときのラウンドｉにある。この関係において、品質パラメータΘはシステムにおける一メッセージの最長実行時間対最短実行時間の比により定義される。時間軸は、（最初は）外部（絶対）基準に対して同期化していないが、それはシステム内部においてだけ該当する（精度は保証されるが正確性はその限りではない）。
【００５８】
アルゴリズムの実行形態をすべてのノードについて同様とすることにより、メッセージの交換によりローカルコピー間の所望の相互作用が得られることになり、究極的には、アルゴリズムの持続的かつ自律的な実行が実現することになる。動的な行動は、アルゴリズムに対するローカル処理時間とそれに従った各々の実行時間により決定される。オリジナルのアルゴリズムは、[Srikanth87]により提供されているが、ここでは、ハードウェアにマッピングするのにより適しているように思われる次のような簡約バージョンについて考察する。実行は、最初は、初期化フェーズ（initialization phase（登録商標））から開始して、主に、２つの規則（１）および（２）に基づいて行われる。すなわち、
(R) “Reset”: 
on reset
send (msg[1]) {once}
local_tick := 1
したがって、各ノードは、まずそのローカルカウンタを値１にセットし、アルゴリズム実行を開始するため、対応するメッセージを全ノードに送信する。
【００５９】
(1) “Relay”:
when received (msg[k]) from f+1
then send (msg[k]) {once}
あるノードが少なくともｆ＋１個の他のノードから―すなわち少なくともひとつの障害のないノードから―メッセージ “k” を受信すると、自ノードは自らそのメッセージ “k” を自ノードを含む全ノードに送信する。上述のように、同じアルゴリズムが同時に他のすべてのノードで走るので、ラウンドｋ＋１に相当する時間に対応するノードに関していわゆるグローバルな「共通像（consensus picture）」が現出することになる。この規則は、ｋ＞ local_tickが成り立つ限りにおいて、それぞれのノードがどのラウンド（local_tick）にあるかにかかわらず使用可能である。
【００６０】
(2) “Increment”: 
when received (msg[k]) from 2f+1
then send (msg[k+1]) {once}
local_tick := k+1
あるノードｐが少なくとも２ｆ＋１個の（自ノードを含む）ノードからメッセージ “k” を受信する場合、明らかにラウンドｋにあってラウンドｋ＋１に移る準備のできている適格な大多数のノードがある。より精確にいえば、最悪の（ｆ個の障害ノードがある）場合であっても、依然として、２ｆ＋１個のノードのうち少なくともｆ＋１個が、メッセージ“k”をすでに送信した正しいノードなのである。したがって、“k” 個のメッセージのフラッディングが予想されるように、すべての障害のないノードについて、規則（１）が開始されなければならないのであり、規則（２）にしたがって、強制的に、すべての障害のないノードがｋ＋１の状態へ遷移する。したがって、ノードｐはそのローカルラウンドカウンタを１クロックステップだけ増加させ、対応するメッセージ“k+1“を送信する。なお、この規則は、当該ノードがそれ自身ラウンドｋにあるときにのみ用いられる。
【００６１】
このように、ノードｑによる同期化メッセージｋのノードｐからの受信は、ノードｐがラウンドｋ＋１に移行する準備ができている、すなわち、グローバルクロックステップを１だけインクリメントしなければならないという見解を有するとの趣旨のノードｑへのメッセージに相当する。（ここで、このことが、ノードｐがすでにラウンドｋにある、すなわち、それ自体がラウンドｋ＋１に移行する、ということを意味するわけでは必ずしもないことに留意されたい。）
ひとつのノードが所与のメッセージ（例えば“k”）を送信するのは一度だけでなければならないことに留意されたい。２つの規則のうち後に「開始（fires）」する方は、もはやメッセージ送信の必要がない、すなわち、同じメッセージのレプリカは受信側で拒絶される。さらに、決定的要因は、メッセージ送信側が疑いなく特定されること（すなわち、二地点間接続の要求）である。これがないと、障害ノードが他のノードに成り代わり偽装してメッセージを送信することが可能となってしまう。 
さらに、少なくともｆ＋１個の他のノードのlocal_tickがノードｐのそれに先立つ場合にのみ、規則（１）が規則（２）よりも前にノードｐに適用されることは興味深く特筆に値する。この場合、ノードｐには依然として不利な要因があるものの、対応するメッセージを送信することにより、より速いノードの判定の形成に貢献している。
【００６２】
4.2 ブート
リセットの後には、すべてのノードが受信可能となっていることを確認しなければならない。その後、各ノードは、すでに述べたように、メッセージ“1”を送出して、アルゴリズムを適切に開始させる。続いて、規則（１）および（２）の適用をスタートする。遅鈍ノード−すなわち、初期化完了が遅いノード−については、いわゆる追い上げ規則によって、すぐに現在の状態まで引き上げることができる。開始処理については[Widder03]に詳述されている。
【００６３】
4.3 特徴
このアルゴリズムの最も重要な特徴を以下に挙げる。
【００６４】
*  アルゴリズムに基づいて、すべての参加（無障害）ノードについて所定程度の同期化が達成されることを保証するグローバルクロックパルスを、「ラウンド（rounds）」（＝microticks）の形で分散発生させる。
【００６５】
*  アルゴリズムは、時間に依存しないので、メッセージ実行時間について（および／またはメッセージ受信までの応答時間について）何ら制約する必要がない。
【００６６】
*  メッセージの（処理時間を含む）最長実行時間の最短実行時間に対する比率Θだけが達成可能な同期化の正確性を決定する。絶対実行時間は、精度のためには重要ではない（が、外部同期化が望まれる場合の正確性のためには重要である）ことに留意されたい[Widder04]。
【００６７】
*  アルゴリズムに基づいて設定された時間軸によって、π（Θ）microticksの粒度でメッセージの時間的配列が可能となる。
【００６８】
*  その機能と精度が形式的に証明することができる[Widder03]。
【００６９】
*  アルゴリズムの適正な開始が指定条件下で形式的に証明することができる[Widder03]。
【００７０】
*  ｆ個までの障害は（それがビザンチン障害であっても）同時に許容可能である。障害許容性は単純にノードの数により計ることができる。
【００７１】
5.オンチップクロックパルス発生の用途
上述のアルゴリズムは、もともと、分散システム上のコンピュータノードを同期化させることを想定するものであった。ここでの我々のアプローチは、一ないし複数の、例えばVLSIチップやシステムオンチップ（Systems-on-a-Chip）上のハードウェア機能ユニット（HW-FU）用に、できる限り、個々の実行時間に関する何らかの想定を必要とせずに、同期化させた周波数クロックパルスを提供するためにこのアルゴリズムを利用することにある。このことは、次のような重要な課題を克服することに繋がる。
【００７２】
5.1.同期化の正確性
ソフトウェアで実装された同期化アルゴリズムでは、１μｓオーダーの精度があれば優秀であると考えられる。ハードウェアにおいては、通常のクロックパルスレートは、１００ＭＨｚほどのオーダーになるので、そこで要求される精度は（絶対尺度で考えて）数オーダーの単位で向上させたものでなければならない。 
関連する要因が主として２つのクロックパルスの間の位相偏移のみであって、Θ＝１が３６０°すなわち完全なクロックサイクルに相当し、それ以上の値が複数のクロックサイクルに相当するハードウェアにおいては、Θの値に関してさえ少なくとも一般的ではない。一方で、ソフトウェアによる解法にとっての待ち行列およびノードの性能低下に伴う典型的な問題はハードウェアにおける直接並列処理においてはほとんど起きないため、ハードウェアにより実装する場合には、ソフトウェアに実装される場合に比して、メッセージの遅延時間の差が実質的に低くなることが想定できる。 
解法：
したがって、Θ≦２を想定することが、典型的な要求という観点からも、またハードウェアの固有の制約に関しても、きわめて現実的であると考えられる。ここで、相対的な変移のみを考慮する選択されたアルゴリズムがきわめて適合するものであることがわかる。 
5.2.通信のオーバーヘッド
アルゴリズムがソフトウェアに実装される場合、通信媒体がすでにノード間に存在すると仮定する。そのような媒体は、いずれにせよアプリケーション関連データの交換に必要とされるものであり、アルゴリズムはこの既存構成に追加されるだけであり、利用可能帯域に関してはオーバーヘッドの原因となるだけである。必要とされる二地点間接続は必ずしも物理的に実現されなければならないわけではない。決定的な要素は、受信者がメッセージをその送信者に一意に関連づけることができることだけであり、−そのためには、関連づけされたアドレス指定や送信者ＩＤや必要に応じて署名を伴うものであれば、例えばバスを介した仮想二地点間接続で十分である。さらに、システム全体の障害許容性を維持するために、このバスが障害許容性を有するものであることが、対応する冗長性により確保されていなければならない。 
しかし、提供されたハードウェア実装形態において、アルゴリズムは、単にグローバルなクロックパルス信号を提供する役割を果たしているのにすぎない。通信インフラは、特にその用途のために設定しなければならないので、常にハードウェア上のオーバーヘッドと考えられるべきである。所望のクロックパルスレートはバスが同期化によって１００％フルにロードされていてデータ通信に利用できないときにだけ達成することができるものなので、データ通信用の既存のバスを利用することは除外可能である。
【００７３】
ノード間のシリアル通信は、周波数と同期化の正確性に関して（ソフトウェアに基づく解法と違って）満足な結果が得られないため、除外可能である。そして、物理的な二地点間接続が実際に確立され得ない場合には並列接続だけが経済的かつ有意味に実装可能である−これは、たった１クロックパルスの供給のためのｎ２個の並列接続を意味する。バス（と仮想二地点間接続）として物理的に実装することで、プロトコルオーバーヘッド（アービトレーション、送信者ＩＤおよび署名、など）がもたらされ、ひいては、クロックパルスレートおよび／または達成される同期化の正確性が実質的に低減される。これに加え、多重冗長設計が必要となる。 
解法：
従来の解法−すなわち、単一のグローバルクロックライン−は、効率の尺度を形成する超えることのできない基準であって、それは実質的にいかなる新しいアプローチの受容をも妨げるものである。したがって、メッセージの情報量を１ビットまで抑制する必要があると考えられるので、物理的な二地点間接続にはシンプルな１ビット信号が適切である。この場合、シリアル伝送か並列伝送かの議論は無用である。 
5.3.メッセージの情報量制限
アルゴリズムの実装における重要課題は、今や、この最小１ビット単位の情報で何とか間に合わせることにある。特に、この制約下では、アルゴリズムで定めているような現在のラウンド数に相当する数字（ｋ）そのものを送信することができない。 
解法:
ｋの値をインクリメンタルに（すなわち、インパルスとして）送信し、各受信側で対応する絶対値をカウンタとして扱う。送信者ＩＤは、このように実装することはできないので、設計上物理的な二地点間接続を実装することが必須となる。
【００７４】
これら所与の制約下にあって、遷移信号方式の手法[Hauck95]を使用することは有効である。
【００７５】
5.4.ｋに相当する絶対値なしでブートすること 
原アルゴリズムでは、ブートは、最初のうちは、互いに最初は一致する大多数のノードにより達成され、それから、クロックパルスの進行がイネーブルにされる。上述の遅鈍ノードは、追い上げ規則によって追いつく。しかし、そのためには、ｋの絶対値を知っている必要がある。遅鈍ノードのローカルカウンタは現在の値を有するものではないからである。 
解法:
そこで、解法としては、（ａ）何とか追い上げ規則なしですますことができるようにブート戦略を変更することや、（ｂ）ｋの値を「随時」伝送することや、（ｃ）各ノードについて、そのノード自体が既に初期化されているかいないかにかかわらず、カウンタが動作するようにハードウェアを設計することからなるものとなろう。
【００７６】
５．５  メッセージの複数のトリガ
ｋの絶対値はメッセージ中には含まれていないので、それぞれの規則が各ｋごとに一度だけトリガされるようにすることが重要である。さらに、すべてのメッセージが一度だけ送信されるようにすること、すなわち、二つの規則のうち早いほうのみがトリガされるようにすることが、様々な理由から望ましい。この要請は、並列処理の特質（両方の規則が、当然、「同時に」トリガされうる）ゆえに、ハードウェアに実装することは困難である。
【００７７】
解法:
可能な解法としては、ｋの偶数値および奇数値に対するフラグとしてそれぞれクロックパルスの立ち上がり端または立ち下がり端を用いることが考えられるが、それによって、短い時間内に同じｋの値が送信される（立ち上がり端に続いて立ち上がり端が来る）ことを簡単に回避することができる。なお、長い時間の場合には、同一メッセージを従来の手法で除去することができる。
【００７８】
５．６  アルゴリズムの複雑性
ソフトウェアによる解法においては、コンピュータノードにおける複雑な計算であっても、ソフトウェアで実行可能なので、その実行に伴う問題はない。純粋にハードウェアに基づく解法の場合、必要な機能は直接ハードウェア（たとえばステートマシン）に実装されなければならないので、乗算のようなアルゴリズム的に簡単な計算であっても実質的なオーバーヘッドとなる可能性がある。また、非同期論理回路を用いた所望の実装形態がさらにオーバーヘッドをもたらす。ｎ個のメッセージが各ノードで受信されるので、受信されたメッセージを処理するためにシステム全体で総計ｎ２個のユニットが実装されなければならないことを忘れてはならない。
【００７９】
解法:
ここでは、利用可能な一般的な解法はないので、ハードウェアに実装する際に、できる限り、細部にわたる最適化を行わなければならない。そのために、アルゴリズムを、最適な方法でハードウェアにマッピング可能となるように、変換することができなければならない。 
ハードウェアによる実装形態には、細部に踏み込んでいくと、解決すべき多くの課題があるが、それは、異なる（未知の）実行時間で並列に走る処理の場合に、実行順序の配列が問題となるという事実に主に関連するものである。なお、このような処理は、ソフトウェアであれば、順序だった不可分な仕方での実行が可能である。
【００８０】
ここまで述べてきたすべての解法にはハードウェア上にできるだけ効率的なマッピングを達成するという共通の目的があるという事実に留意されたい。ノードの周波数同期化のための分散アルゴリズムを用いる基本的な方法とともに、非同期ハードウェアにそれらを実装することも他のやりかたで実現可能である。したがって、ここで提示されている解決は、いずれも、必須というわけではない。
【００８１】
６．ＨＷ実装形態案
６．１  アーキテクチャー
上で提示した議論は、図２に示すような１ビットラインからなるインターメッシュ構造を提起するものである。幸い、このアーキテクチャーをサポートするチップアーキテクチャーが、市場に出回るようになったばかりである：たとえば、Arteris[Arteris04]が提供するＮｏＣ（ネットワークオンチップ）設計戦略は、もともとＧＡＬＳアーキテクチャーとともに使用するためのものとして構想されたものであり、データとクロックパルス用に必要とされる通信構造を非常によくサポートするものと思われるスイッチ機構を備えるものである。
【００８２】
６．２  機能ブロックの諸実装形態
各コンピュータノードが、たとえばローカルプロセッサを駆動するグローバルに同期化された時間軸とは独立のローカルクロックパルスも備えるものであることは、ソフトウェアによる解法においては暗黙の前提である。このローカルプロセッサクロックパルスは、受信メッセージ間の間隔やグローバルタイムの精度と比較して、数オーダーの規模で、より良い時間解決となる。したがって、入力メッセージが実質的に連続的に受信され処理されると仮定することが理にかなっている。 
しかし、ハードウェアによる解法の目的は、ローカルクロックパルス発生器が無くても、なんとかして、発生させた分散グローバルクロックパルスからローカルクロックパルスを導くことである。よって、メッセージを受信し処理するために利用可能なクロック信号はアプリオリには存在しないことになる。したがって、明らかに、このアルゴリズムは、すべてのクロックパルス発生に関連するユニットがクロックパルスなしに動作する、すなわち、非同期論理回路（図２の網掛けボックス）において実装されている場合にだけ、開始可能である。したがって、ローカル論理回路（すなわち、ローカルクロックパルスを備える論理回路）が同期式ハードウェアを用いて実装されたと仮定したときに必然的に発生する準安定性問題と競合状態を、適切な設計を用いて、回避することも可能である。
【００８３】
したがって、これらの非同期式のボックスは、共同でクロックパルスを発生させて、それぞれの機能ユニットＨＷ−ＦＵｎにそれを供給することができるところに配置される。このように、グローバル時間軸が利用可能となることで、たとえば、個々の機能ユニット間の通信が簡素化され、あるいは、アクション（周辺機器へのアクセス、アクチュエータの制御等）の同期化が可能になる。
【００８４】
図３に、本実装形態の提案された動作原理を示す。基本ブロック図は、図２におけるひとつの「網掛けボックス」に対応する。実装形態の原理は次のようなものである：
各ノードが（すなわち、この場合、各ハードウェア機能ユニットＨＷ−ＦＵ）各メッセージを正確にただ一度だけ送信すると仮定する。そのメッセージは、ラインのエッジに他ならない。この仮定に基づいて、入力ｉごとにひとつずつ必要となる各受信ノードのカウンタＺｅｘｔ，ｉによって、メッセージ数（すなわち、原アルゴリズムの”k“）を提供することができる。同時に、各メッセージが送信されるごとに、内部カウンタＺｉｎｔがインクリメントされる。メッセージは、すべての出力に同時に送出されるので、基本的に、すべてのチャネルに対してひとつの共通カウンタがあれば足りることになる。ここで、カウンタ値の比較に基づいて、受信したメッセージが、ひとつか、あるいはことによるとｋの値が大きく複数か、がローカルに判定可能となる。これは、単にZext,i >Zint を満たす場合ということである。充分多数のチャネル上でそうなった場合には、新規メッセージ（＝フランクまたはエッジ）を送信することができ、および／または、ローカル時間軸が１クロックインパルスlocal_tick分だけ増加される。 
上に述べてきたことから、Zext,iおよびZintを「相対的に」比較することだけが必要であることがわかる。したがって、カウンタのハードウェアコストを節約し、代わりに、差だけが見えるようにエントリをペアで除去するキューを提供するのが容易になる。これらのキューは、[Sutherland89]にしたがってエラスティックパイプラインとして非同期実装形態を用いて、より簡便に（必ずしもそうでないこともあるが、）実装することができる。このことは、図３に、「内部パイプ（Int.Pipe）」および「外部パイプ（Ext.Pipe）」によって、図式的に示されている。モジュール「差と比較（Difference &Comparison）」は、これらのパイプからのエントリがそれぞれペアで、すなわち、同時に内部パイプおよび外部パイプから、消費されることを保証する。外部パイプにエントリがあり、内部パイプがすでに空である場合には明らかにZext,i >Zint,となるが、これは、次のモジュール「アルゴリズムの規則の使用（Using the rules of the algorithm）」により対応づけて評価される。ここで、二つの規則のうちのひとつだけが常に「作動される（fired）」よう注意が払われなければならない。メッセージを読むこともそれを消費することなので、Zintはチャネルごとに複製されなければならず、すべてのZint,iに対して同時にメッセージ送信中にエントリの挿入が起こる。
【００８５】
必要なパイプの深度は、受信したラウンド数と送信したラウンド数の間の予想される最大差から取得され、アルゴリズムによって、値Θを限界とする。ここで、キューのコストは、前記限界値Θ≦2を用いて限界値内に維持することができる。
【００８６】
ソフトウェアにおける実装形態の場合のように、ここで、ひとつの入力で自身のメッセージを受信することが好ましい。このことは、最短実行時間を（たとえば、内部接続を介して）均衡を崩すほどに短くしてしまうとΘの値を悪化させることになるので、それを回避することに大いに貢献する。
【００８７】
６．３  障害許容
インパルスによるメッセージｋのインクリメンタルな伝送により、エラーは、一旦起こると常にそのまま残ってしまう。これにより明らかにこの解法のロバスト性を減ずることになる。たとえ、ｆ個までのそのようなエラーが許容可能であったとしても、そのような実装形態の「任務時間（Mission Time）」は、そのようなエラーを補正する方法が見つからない限りは現実的には有限である。それは、たとえば、データレベルでは、ノード間でｋの絶対値またはlocal_tickをときどき交換することによって可能となる。そのような補正メッセージに対する時間的制約は、いずれにせよ利用可能な障害許容性（複数の障害の蓋然性のためだけの設計）のため、まったく重要ではないということになろう。
【００８８】
６．４  周波数安定化
分散型クロック発生器はいかなる水晶発振器をも用いないので、クロックパルス周波数の一定性および安定性は、相対的に低い。もちろん、チップは、常に、それぞれの動作条件により、内部処理に最適な最大の周波数で動作するが、このことは、外部同期コンポーネントとのインターフェーシングをますます困難にする。
【００８９】
しかし、周波数の安定性は、なかんずく、チップ製造中に、あるいはランタイムで動的に、プログラムされるか、あるいは実際に動作中に継続的にプログラムされている、TS-Netのクロックラインにおける可変遅延素子を統合することにより、改善することができる。後者の例としては、チップの温度を継続して計測し、チップ固有の温度曲線にしたがって遅延を調整する、TCXO’sにより知られている温度補償があげられよう。
【００９０】
別個のクロックパルス信号をローカルクロックパルスから導出する、クロックパルス変換回路を使用することが代替オプションとして利用可能である。ここで、「加算機ベースのクロック（Adder-based Clocks）」[SSHL97] [SSHL97] [SSHL97] [SSHL97] [SSHL97] [SSHL97]が、（たぶんPLLsやDLLsと組み合わせて）使用できる。加算機ベースのクロックは、完全でないクロック比を発生させることもできる。
【００９１】
６．５  リセット
クロックパルス分配に伴う問題と同様の問題が、大規模VLSIチップおよび高クロック周波数において、（電源投入）リセット時にすべての機能ユニットが同じクロックサイクルで始動することを保証することをますます困難にしている。クロックパルス発生に用いられる分散アルゴリズムは、電源投入中であってもグローバルな同期化を保証するものなので、すべての機能ユニットの動作をきれいに同時始動させることが容易に実現可能である。そのために必要なのは、ただ、すべての機能ユニットがオープンコレクタのリセット済ラインを「スキップした（skipped）」macrotickを待つことだけである：すなわち、macrotick開始時にこのラインが作動していないことを発見した各機能ユニットＦＵが、その動作を開始することができる。保証された同期化の正確性は、すべての機能ユニットが同じmacrotickでこれを実行することを保証する。
【００９２】
提案された解法の利点
*  回路が自らのクロックパルスを発生させるので、保証された全システムにわたる同期化の正確性を一定に制限して、ローカルクロックパルス源（発振器、水晶振動子）を節約する。
【００９３】
*  障害許容クロックパルスを取得するすべてのハードウェアベースの方法と異なり、ハードウェア機能ユニット上にローカルクロックパルス発生器およびPLLsを必要とすることはなく、分散されたユニット間の相互作用の結果としてクロックパルスを発生させる。
【００９４】
*  複雑でエネルギーを消費するクロックツリーとともに、チップ全体にわたってクロックスキューを最適化するための高いコストをなしですます。
【００９５】
*  ＧＡＬＳ技法と違って、同期設計パラダイムを、ローカル（microticksレベル）とグローバル（macroticksレベル）の両面で維持する。macroticksを適切に選択することで準安定性の問題をも回避可能である。
【００９６】
*  絶対実行時間についていかなる前提も必要としない。処理時間の最も遅い場合と最も速い場合との間の相対的な差Θでさえ、達成可能な精度に影響を与えるだけである。
【００９７】
*  クロックパルスを発生させ分配する間、任意のｆ個の障害が許容可能である。アーキテクチャーは、自由に、ｆとの関係を天秤にかけることができる。障害許容クロックパルス発生のための伝統的な方法をもってしては、これすら不可能である。
【００９８】
*  障害のない条件下では、最も遅いｆ個のノードがアルゴリズムによって「引き上げ」られる、すなわち、それらがシステム全体の速度を遅くすることはあり得ない。
【００９９】
*  アルゴリズムの実装のため非同期論理回路（エラスティックパイプライン、Muller-Cゲート）を使用する結果、基本的に準安定性に伴う問題が回避される。ローカルクロックパルスを適合させるための慣例となっている解決手段では、準安定性は適切に起こりえないものとすることができるだけで、回避することができるわけではない。[Kopetz97]
*  クロックパルスレートはそれぞれの条件に自動的に適合される、すなわち、チップは常に最大周波数で動作する。チップ設計または技術上の変更は、せいぜいΘ値の調整を要求するだけで、それ以外に、クロックパルス発生アルゴリズムの改変は不要である。
【０１００】
*  分散型のクロック発生により、電源投入段階中であっても同期化が保証されるので、すべての機能ユニットの動作がきれいに同期して始動させることをチップ上で実現することができる。既存の方法とはまったく対照的に、これは、高クロック周波数では大規模チップに実装することがますます困難となっている同期リセットを要求するものではない。
【図面の簡単な説明】
【０１０１】
参考文献
[Widder03]  Josef Widder著「部分的に同期しているシステムにおけるクロック同期化の起動（Booting clock synchronization in partially synchronous systems）」，In Proceedings of the 17th International Symposium on Distributed Computing (DISC’03), vol.2848 of LNCS, pp.121-135.Springer 2003.
[LeLann03]  Gerard Le Lann and Ulrich Schmid共著「部分的に同期しているシステムにおいてタイマー不要の完璧な障害検出器を実現する方法（How to implement a timer-free perfect failure detector in partially synchronous systems）」，Technical Report 183/1-127, Department of Automation, Technische Universitat Wien, April 2003
[Intel02]  Ram Bhamidipati, Ahmad Zaidi, Siva Makineni, Kah K.Low, Robert Chen, Kin-Yip Liu and Jack Dalgrehn共著「高性能ネットワークプロセッサ実装への挑戦と方法論（Challenges and Methodologies for Implementing High-Performance Network Processors）」，Intel Technology JournalVol.06, issue 03, August 15, 2002.Intel Corporation.
[Scherrer02]  Christoph Scherrer and Andreas Steininger共著「障害導入実験の結果に基づくエラー検出機構の効率的な組み合わせの特定（Identifying Efficient Combinations of Error Detection Mechanisms Based on Results of Fault-Injection Experiments）」，IEEE Transactions on Computers Vol.51, No.2, February 2002, pp.235-239.IEEE Computer Society Press.
[Choi90]  Bong-Rak Choi, Kyu Ho Park and Myunghwan Kim共著「大規模マルチプロセッサシステムのための障害許容クロック同期化アルゴリズムの改良されたハードウェア実装形態（An Improved Hardware Implementation of the Fault-Tolerant Clock Synchronization Algorithm for Large Multiprocessor Systems）」，IEEE Transactions on Computers Vol.39, No.3, March 1990, pp.404-407.IEEE Computer Society Press.
[VanAlen91]  D.J.VanAlen and A.K.Somani共著「全デジタルフェーズロックループ障害許容クロック（An All Digital Phase Locked Loop Fault Tolerant Clock）」，International Symposiun on Circuits and Systems, Vol.05, June 1991, pp.3170-3173.IEEE Computer Society Press.
[Vasan98]  Nagesh Vasanthavada and Peter N.Marinos共著「悪質な障害存在下での障害許容クロックの同期化（Synchronization of Fault-Tolerant Clocks in the Presence of Malicious Failures）」，IEEE Transactions on Computers Vol.37, No.4, April 1988, pp.440-448.IEEE Computer Society Press.
[Miner92]  Paul S.Miner, Peter A.Padilla and Wilfredo Torres共著「障害許容クロック同期化回路の証明可能な正しい設計（A Provably Correct Design of a Fault-Tolerant Clock Synchronization Circuit）」，in Proc.Digital Avionics Systems Conference, IEEE/AIAA 11th, 5-8 Oct.1992, pp.341 − 346.
[Schneider87]  Fred B.Schneider著「ビザンチンクロック同期化のためのプロトコルを理解する（Understanding Protocols for Byzantine Clock Synchronization）」，Technical Report 87-859, Dept.of Computer Science, Cornell University, Ithaca, N.Y., Aug.1987.
[Lamport85]  Leslie Lamport and P.M Melliar-Smith共著「障害存在下でのクロック同期化（Synchronizing Clocks in the Presence of Faults）」，Journal of the ACM.Vol.32, pp.52-78, Jan.1985.
[Restle01]  Phillip J.Restle, et.al.共著「マイクロプロセッサのためのクロック分散型ネットワーク（A Clock Distribution Network for Microprocessors）」，IEEE Journal of Solid-State Circuits Vol.36, No.5, May 2001, pp.792-799.IEEE Computer Society Press.
[Srikanth87]  T.K.Srikanth and S.Toueg共著「最適なクロック同期化（Optimal clock synchronization）」，Journal of the ACM.Vol.34, no.3, pp.626-645, July.1987.
[Shin88]  K.G.Shin and P.Ramanathan共著「ハードウェアクロック同期化における伝送遅延（Transmission Delays in Hardware Clock Synchronization）」，IEEE Transactions on Computers.Vol.C-37,No.11, pp.1465-1467, Nov.1988.
[Chapiro84]  Daniel M.Chapiro著「グローバルに非同期でローカルに同期するシステム（Globally-Asynchronous Locally-Synchronous Systems）」，Ph.D.thesis, Stanford University, Oct.1984.
[Myers01]  Chris J.Myers著「非同期回路設計（Asynchronous Circuit Design）」，John Wiley and Sons, July 2001
[Steininger04]  A.Steininger, M.Delvai and W.Huber共著「同期および非同期設計の方法−ハードウェア設計者の観点（Synchronous and Asynchronous Design Methods − A hardware Designer’s Perspective）」，International Conference on Computer Design (ICCD) 2004 (submission).
[Fai04]  Fairbanks Scott (GB)「分散型クロック発生器の方法および装置（）」，米国特許公開US patent no.US2004108876, 
[Kopetz97]  H.Kopetz著「実時間システム−分散型組み込みアプリケーションの設計原理（Real Time Systems − Design Principles for Distributed Embedded Applications）」，Kluwer Academic Publishers, Boston 1997.
[Const02]  Cristian Constantinescu著「ＶＬＳＩ回路の信頼性に対するディープサブミクロン技術の影響（Impact of Deep Submicon Technology on Dependability of VLSI Circuits）」，Proceedings of the International Conference on Dependable Systems and Networks (DSN) 2002.pp.205-209, June 2002
[ITRS02]  国際半導体技術ロードマップ２００１年版（International Technology Roadmap for Semiconductors 2001） ()
[Sutherland89]  IE Sutherland著「マイクロパイプライン（Micropipelines）」，Communications ofthe ACM, Vol.32, No.6, Jun.1989, pp.720-738.
[Salim01]  M.Salim Maza and M.Linares Aranda共著「クロストークとグラウンドバウンス存在下のクロック分配ネットワークの分析（Analysis of Clock Distribution Networks in the Presence of Crosstalk and Groundbounce）」，IEEE ICECS.Sep.2001, pp 773-776.
[Dobberpuhl92]  D.W.Dobberpuhl et al.共著「２００ＭＨｚ  ６４−ｂデュアルイシューＣＭＯＳマイクロプロセッサー（A 200-Mhz 64-b dual issue CMOS microprocessor）」，IEEE Journal on Solid-State Circuits.Vol.27, pp.1555-1565, Nov 1992.
[Restle02]  J.Phillip Restle, et al.共著「パワー４マイクロプロセッサのクロック分配（The clock distribution of the Power4 microprocessor）」固体回路コンファレンス２００２（Solid-State Circuits Conference, 2002），ISSCC 2002 IEEE International, Vol.1, 2002, pp.144 − 145.
[Chen02]  Charlie Chung-Ping Chen and Ed Cheng共著「将来のＳＯＣ設計上の課題と解法（Future SOC Design Challenges and Solutions）」，International Symposium on Quality Electronic Design.pp.534 − 537, March 2002.  
[Friedman01]  Eby G.Friedman著「同期デジタル集積回路におけるクロック分配ネットワーク（Clock Distribution Networks in Synchronous Digital Integrated Circuits）」，Proceedings of the IEEE.Vol.89,No.5,pp.665 − 692,May 2001.
[Ram90]  P.Ramanathan, K.G.Shin and R.W.Butler共著「分散型システムにおける障害許容クロック同期化（Fault-Tolerant Clock Synchronization in Distributed Systems）」， Computer, Vol.23, No.10, pp.30−42, Oct.1990.IEEE Computer Society Press.
[Lu89]  Meiliu Lu, Du Zhang and Tadao Murata共著「障害許容クロック同期化の自己診断のための設計アプローチ（A Design Approach for Self-Diagnosis of Fault-Tolerant Clock Synchronization）」，IEEE Transactions on Computers.Vol.38 , Issue 9, Sept.1989, pp.1337 − 1341.IEEE Computer Society Press.
[SynUTC02]  Martin Horauer, Ulrich Schmid, Klaus Schossmaier, Roland Holler, Nikolaus Kero共著「ＰＳｎＵＴＣ−イーサネット（登録商標）ＬＡＮのための高精度時間同期プロトタイプシステムの評価（PSynUTC - - Evaluation of a High Precision Time Synchronization Prototype System for Ethernet （登録商標）LANs）」，Proceedings of the 34th {IEEE} Precise Time and Time Interval Systems and Application Meeting (PTTI'02), Reston, Virginia, December 2002, pp.263-278.
[SSHL97]  Klaus Schossmaier, Ulrich Schmid, Martin Horauer, Dietmar Loy共著「協定世界時同期化ユニット（ＵＴＣＳＵ）の仕様と実装形態（Specification and Implementation of the Universal Time Coordinated Synchronization Unit (UTCSU)）」，Real-Time Systems 12(3), May 1997, pp.295-327.
[Arteris04]  Arteris著「Ａｒｔｅｒｉｓ  ｕｎｖｅｉｓ戦略、ネットワークオンチップ設計を可能にする技術（Arteris unveis strategy, technology for enableing Network-on-Chip (NoC) design）」，Press Release March 2004,
[Chelcea00]  Tiberiu Chelcea and Steven M.Novick共著「混合クロックシステムのための低レイテンシーＦＩＦＯ（A Low-Latency FIFO for Mixed-Clock Systems）」，IEEE Computer Society Workshopon VLSI, April 2000, pp.119 − 126.
[Huffman54]  D.A.Huffman著「順次スイッチング回路の合成（The Synthesis of sequential switching circuits）」，Journal of the Franklin Institute, March/April 1954.
[Hauck95]  S.t Hauck著「非同期設計方法概論（Asynchronous Design Methodologies: An Overview）」，Proceedings of the IEEE, Vol.83, pp.69 − 93, 1995.
[Berkel99]  C.H.van Berkel, M.Josephs and S.Nowick共著「技術精査：非同期回路の応用（Scanningthe Technology: Applications of asynchronous circuits）」，Proceedings of the IEEE, Vol.87, pp.223-233, 1999.
[Gaisler02]  Jiri Gaisler著「ＳＰＡＲＣ  Ｖ８アーキテクチャーに基づく携帯型障害許容マイクロプロセッサ（A Portable and Fault-Tolerant Microprocessor Based on the SPARC V8 Architecture）」， 2002.Proceedings of the International Conference on Dependable Systems and Networks.  June 2002, pp.409 − 415.
[Truong97]  T.Kien Truong著「統合モジュラーアビオニクス用シングルチップ障害許容クロック（Single Chip Fault Tolerant Clock for Integrated Modular Avionics）」，16th Digital Avionics Systems Conference (DASC), AIAA/IEEE ,  Vol.1, Oct.1997, pp.: 2.1-36-44 vol.1
[LL88]  J.Lundelius-Welch and N.Lynch共著「クロック同期化のための新しい障害許容アルゴリズム（A New Fault-Tolerant Algorithm for Clock Synchronization）」，Proc.of 3rd ACM Symposium onPrinciples of Distributed Computing, August 1984, pp.75-88.
[SIFT78]  John H.Wensley et al.共著「ＳＩＦＴ：航空管制用障害許容コンピュータの設計と分析（SIFT: Design and Analysis of a Fault tolerant Computer for Aircraft Control）」，Proc.IEEE Vol.66, Oct 1978.
[Widder04]  Josef Widder著「有界非同期性存在下の分散コンピューティング（Distributed Computing in the Presence of Bounded Asynchrony）」，Ph.D.thesis, Vienna University of Technology.May 2004.
[DHS86]  Danny Dolev, Joseph Y.Halpern and H.Raymond Strong共著「クロック同期化達成の可能性と不可能性について（On the Possibility and Impossibility of Achieving Clock Synchronization）」， Journal of Computer and System Sciences.Vol.32, pp.230 250, 1986.
[LL84]  Jennifer Lundelius-Welch and Nancy A.Lynch共著「クロック同期化の上限と下限（An Upperand Lower Bound for Clock Synchronization）」，Information and Control.Vol.62 pp.190-204, 1984.
[WS03]  Josef Widder and Ulrich Schmid共著「ノードとリンクの複合型障害を有する部分的同期システムにおけるクロック同期化の起動（Booting Clock Synchronization in Partially Synchronous Systems with Hybrid Node and Link Failures）」，Technical Report, Nr.183/1-126, Department of Automation, Vienna University of Technology.January 2003.
[KKMS95]  Hermann Kopetz, Andreas Kruger, Dietmar Millinger and Anton Schedl共著「タイムトリガーマルチクラスター実時間システムのための同期化戦略（A Synchronization Strategy for a Time-Triggered Multicluster Real-Time System）」，Proceedings Reliable Distributed Systems (RDS'95), Sept.1995, Bad Neuenahr, Germany
【図１】
2008507050.tif 000003
【図２】
2008507050.tif 000004
【図３】
2008507050.tif 000005
【図４】
2008507050.tif 000006
【図５】
2008507050.tif 000007
【国際調査報告】
2008507050.tif 000008
2008507050.tif 000009
2008507050.tif 000010
2008507050.tif 000011
2008507050.tif 000012
2008507050.tif 000013