No | 215632 | |
著者(漢字) | オズジャン,メテハン | |
著者(英字) | Ozcan,Metehan | |
著者(カナ) | オズジャン,メテハン | |
標題(和) | 非同期式回路におけるタイミング制約の検証と制約違反の修正方式に関する研究 | |
標題(洋) | Verification and Violation Correction of Timing Constraints for Asynchronous Circuits | |
報告番号 | 215632 | |
報告番号 | 乙15632 | |
学位授与日 | 2003.03.12 | |
学位種別 | 論文博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 第15632号 | |
研究科 | 工学系研究科 | |
専攻 | 先端学際工学専攻 | |
論文審査委員 | ||
内容要旨 | 非同期式システムの設計では、論理ゲートや配線の遅延に関して設ける仮定、すなわち遅延モデルが重要な役割を果たす。遅延変動に対して悲観的な遅延モデルに基づいた設計では、現実には起こりそうもない遅延変動に対しても正しい動作を保証する必要があるため、実用的観点からは効率の良い回路とは言えず、十分な速度性能を得ることが困難である。そこで、近年、設計時に遅延情報を利用し、タイミング最適化を図る非同期式回路の設計方式が提案されている。このようなタイミング最適化では、設計時、特にレイアウト段階で従来の設計方式とは異なる新しいタイミング制約を適用する必要がある。本研究の目的は、ゲートレベルの非同期式回路に対して、広く研究が行われている静的タイミング解析手法を用いたタイミング検証方式を確立し、適切なCADフレームワークを構築することにある。これは同期式システム設計と非同期式システム設計で共通に利用することの出来るレイアウトツールと、非同期式論理合成との間を繋ぐものとなる。本論文の主な提案内容はレイアウト後の回路におけるタイミング制約の検証方式と、制約違反が存在した場合の修正方式である。 初めに、非同期式回路設計に関する基礎知識についてまとめる。すなわち、非同期式コミュニケーションプロトコル、データエンコード方式、遅延モデルや非同期式制御回路の論理合成方式などである。次に、提案されている二つのタイミング最適化設計方式について説明する。Relative Timingに基づく非同期式システム設計方式とScalable-Delay-Insensitiveモデルに基づく非同期式システム設計方式である。これらの設計方式では、遅延情報を利用することによりタイミング最適化を実現する。但し、遅延の絶対値を設計段階で求めるのは非常に困難であるため、相対的な信号遷移の順序関係を用いる。 これら二つの設計方式の特色に基づき、提案する検証方式と違反個所の修正方式の基本概念を以下の様に考える。基本的に、タイミング制約は「速いパスと遅いパス」により表現することが出来、遅いパスの最小遅延が、速いパスの最大遅延にマージンを加えたものよりも大きくなることが要求されるものであると言える。また、タイミング制約の違反は遅延パッドを遅いパスの終点に加えることで修正される。速いパスと遅いパスの情報は始点、終点、通過点、非通過点及びそれぞれの極性から構成され、論理合成段階で各パスに対して生成され、遅延検証は極性を持った深さ優先探索を用いた静的タイミング解析に基づいて行われる。回路に遅延制約違反個所がある場合、遅延パッドを挿入する場所とその大きさがユーザに対して出力され、再度レイアウトを行うことで違反を修正する。 本論文では、一般的な非同期式回路に対するタイミング制約の検証と制約違反の修正を行うアルゴリズムを提案する。タイミング制約はインターリーブすることがあるため、遅延制約を修正することにより、新たな制約違反を生じる可能性がある。従って、制約違反の修正処理は慎重に行わなければならない。提案するアルゴリズムはタイミング制約の特定のソートを適用した分岐限定法の原理に基づいている。また、タイミング制約違反の修正は、遅延パッドの大きさによる昇順に基づいて行われる。この方式により、実時間内で特定の場所に最小の大きさの遅延パッドを挿入することが出来る。もし修正を行うことが出来ない場合、すなわち、修正することにより新たな制約違反を生じ、結果として初期状態の制約でさらに新しい制約違反を生じる事になる場合、ユーザは論理合成を更新するための制約の競合情報を得ることが出来る。 次に、提案する検証方式・修正方式の例として、非同期式データパス回路とSDIモデルに基づいた局所同期型VLSIについて考察し、あらゆるタイプの非同期式データパス回路を実際にカバーするための指針が導き出されることを示す。非同期式2線2相式回路の休止相のオーバーヘッドを隠蔽する効果的な手法として細粒度化がある。細粒度パイプラインの局所的な完了信号生成回路は単純な組み合わせ回路ではないため、特定の処理が必要となる。そこで、様々な細粒度パイプライン構成に対して提案手法を適用する。また、同期式回路と同様のレジスタ転送レベル仕様記述を利用することの出来るSDIモデルに基づいた局所同期型VLSI設計方式がある。局所同期型VLSIではグローバルクロックの代わりに要求-応答ハンドシェイクに基づいて生成される局所的なタイミング信号を用いる。この局所的なタイミング信号生成回路はセルフリセット構造を利用し、パルス的なタイミング信号を生成する。しかしながら、正しく動作するためには多くの制約を満たさなければならない。これらの制約は詳細に解析すると、ローカルタイミング生成セルを注意深<設計することにより満たすことが出来る制約と、セル間のインバータ回路の遅延に関する制約であることがわかる。これらの制約を満たす条件は本論文で提案する方式を適用する事により得ることが出来ることを示す。 最後に、実装を行ったCADフレームワークについて説明し、幾つかの実験結果を示す。タイミング制約検証と制約違反の修正方法に関して提案したアルゴリズムはCAD環境として実装されている。また、細粒度パイプラインデータパス回路に関する制約情報の自動生成機能も実装し、さらに、SDIモデルに基づく局所同期型VLSIへの拡張も行った。これにより、一般的な非同期式回路に対するタイミング制約も、速いパスと遅いパスの形式で明示的に制約を示すことにより検証と修正を行うことが出来る。また、構築したCAOフレームワークを用いて、細粒度化回路を設計し、レイアウトを行った。実行時間は大きな回路でもタイミング制約検証と修正を数分程度で行うことが出来ることがわかった。 | |
審査要旨 | 本論文は「Verification and Violation Correction of Timing Constraints for Asynchronous Circuits」と題して英文で10章から成っている。非同期式システムの設計では、論理ゲートや配線の遅延に関して設ける仮定、すなわち遅延モデルが重要な役割を果たす。遅延変動に対して悲観的な遅延モデルに基づいた設計では、現実には起こりそうもない遅延変動に対しても正しい動作を保証する必要があるため、実用的観点からは効率の良い回路とは言えず、十分な速度性能を得ることが困難である。そこで、近年、設計時に遅延情報を利用し、タイミング最適化を図る非同期式回路の設計方式が提案されている。このようなタイミング最適化では、設計時、特にレイアウト段階で従来の設計方式とは異なる新しいタイミング制約を適用する必要がある。本論文は、非同期回路設計用CADフレームワークを構築するために、ゲートレベルの非同期式回路に対して静的タイミング解析手法を用いた新しいタイミング検証方式を提案したものである。 第1章「Introduction」では、本研究の技術的背景と非同期式回路設計に関する従来の研究を概観し、本論文の目的と構成を述べている。 第2章「Timing Optimization based Synchronous Synthesis Methodologies」では、遅延情報(相対的な信号遷移の順序関係)を利用することによりタイミング最適化を実現する二つの設計方式として、Relative Timingに基づく非同期式システム設計方式とScalable-Delay-Insensitiveモデルに基づく非同期式システム設計方式が有効であると述べている。 第3章「Constraint Format Determination」では、非同期式回路において検証するべきタイミング制約を、「速いパス」と「遅いパス」の組で表現され、遅いパスの最小遅延が速いパスの最大遅延にマージンを加えたものよりも大きくなるべきもの、として定式化している。また、タイミング制約に違反がある場合の修正は指定された大きさの遅延パッドを指定された場所に存在する遅いパスの終点に加えること、として定式化している。 第4章「Verification and Corrrection Methodology」では、本論文で提案するタイミング制約検証/修正方式が前提とする非同期システム設計の流れを述べている。 第5章「Verification and Violation Correction of Constraints」では、非同期式回路に対するタイミング制約の検証と制約違反の修正を行うアルゴリズムを提案している。タイミング制約はインターリーブすることがあるため、遅延制約を修正すると新たな制約違反を生じる可能性があることを指摘し、その可能性を考慮した制約違反の修正処理手順を示している。また、タイミング制約違反の修正は、遅延パッドの大きさによる昇順に基づいて行われるので、実時間内で特定の場所に最小の大きさの遅延パッドを挿入することが出来ると述べている。 第6章「Constraints for Asynchronous Data-Path Circuits and their Verification」では、提案する検証手法の適用例として、2線2相式を前提とした細粒度化パイプライン構成のデータパス回路における局所的な完了信号生成回路のタイミング制約を検証し、修正する手順を述べている。 第7章「SDI Model-based Locally-Timed Asynchronous Circuits」では、SDIモデルに基づいた局所同期型VLSIにおける局所的タイミング信号生成回路が正しく動作するために満たすべき制約に関して、本論文で提案する方式で検証し、修正する手順を述べている。 第8章「CAD Environment」では、提案したタイミング制約検証アルゴリズムと違反修正アルゴリズムを実装して現在開発中のCAD環境について説明している。 第9章「Experimental Results」では、構築したCADフレームワークを用いて、細粒度化回路の設計およびレイアウトを行い、タイミング制約の検証と修正を行った結果を示している。 第10章「Conclusion」では、本研究で得られた成果を総括し、今後の課題を指摘している。 以上に要するに、本論文は、設計時に遅延情報を利用してタイミング最適化を図る非同期式回路の諭理合成段階で導出されたタイミング制約をレイアウト段階で検証し、違反があれば修正するアルゴリズムを提案し、設計支援CADフレームワークとして実装して、その有効性を示したものであり、その成果は工学的に貢献するところが大きい。よって本論文は博士(学術)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |