Comments
Description
Transcript
第3章 多相クロック同期回路のためのタイミ ング解析
第3章 多相クロック同期回路のためのタイミ ング解析 本章では, レベルセンシティブラッチのループを含む多相クロック同期回路のタイミン グ解析を効率的に扱う手法を述べる.1) 3.1 はじめに 前章で述べたように静的タイミング解析, いわゆる STA は, 同期回路が正常動作する ための重要な条件であるタイミング基準を満たすことを確認するために有効な手法と して長い歴史 30), 7), 4), 5) を持っている. 当時の同分野の研究は 6) にまとめられているが, ただ現在でも確定遅延に基くタイミング解析に限定しても, STA が持つ課題は完全に は解決されてるとは言えない. タイミング解析を適用する回路を分類すると以下のよ うにまとめることができるが, 以下本章ではレベル転送同期回路の STA によるタイミ ング解析を扱う (表 3.1). 表 3.1 適用回路. 回路 STA クロック 同期回路 単一クロック 転送 相 備考 エッジ転送 単一 (両エッジ） レベル転送 単相 （反転レベル） 多相 STA 同期回路 複数クロック マルチサイクル マルチクロック (*)CDC： 転送 多相 Clock domain crossing シミュレータ シミュレータ 非同期回路 22 3.2 レベルセンシティブラッチのフィードバックループの タイミング解析 1) 概要 静的タイミング解析を適用する場合, その回路がエッジトリガーラッチ (フリップフ ロップ) を用いた同期回路であるときは比較的やさしい．というのは，この場合，各 ラッチの入力信号のセットアップタイム等のタイミング制約が他のラッチのそれとは 分離されるからである．この特徴は，このような同期回路に対する強力なタイミング 解析ツールを開発するのに利用されている. 一方、レベルセンシティブラッチを用い た同期回路では、各ラッチの入力信号のタイミング制約は互いに分離できない．とい うのは，ラッチがトランスペアレント動作をしているときはその出力の変化の時刻は その入力，すなわち，前段のラッチの出力のそれに依存するからである (図 3.1). その 場合，タイミング解析はより困難である．更に，今日の多相クロック回路では，通常， レベルセンシティブラッチを含むループや，異なる相のクロックによってドライブさ れるラッチの出力信号を入力するゲートを含んでいる (図 3.2). 以上のような回路のタイミング解析を正確に，効率良く行うのは困難な問題の一つ であり, 特にゲーティングを扱う方法については知りうる限りでは, 本研究を遂行した 1992 年当時は実使用はまだされていなかった. レベルセンシティブラッチベースの設計のタイミング解析はこのように困難である が, 後に述べるようにタイミング最適化に自由度をもたらすものであるためその扱いの 効率化は重要な課題である. 本研究はそれを扱ったものである. これを可能にしたのは後に述べるクロックレベル の概念の導入とトレースに伴うクロックレベルの伝搬である. 最近ではタイミング値の 伝搬の他にスリュー情報の伝搬などの扱いが文献 13) においても見られるがタイミング 値の伝搬とともにクロックレベルと呼ばれる相情報を伝搬させる初めての試みである. Dagenais と Runamin は前述のループを扱うために有用な概念, すなわち retardation を 導入した.23) retardation(本論文のアルゴリズム用に拡張した retardation は 2) 節で改め て定義する) とは, クロックのイネーブルエッジを基準として，ラッチの入力信号がどれ 23 図 3.1 到着時間と出発時間（分離と非分離）. だけ遅れて到着するかを示す仮想的な遅延値である．ラッチに対して retardation を与え ると，そのラッチの出力変化時刻は入力のそれとは直接には関係がなくなる (retardation を介してのみ関係する)，すなわち，分離される．このことは，それをあたかもフリッ プフロップのごとく扱うことと等価である．この retardation を用いて，本論文前の研 究を比較する. Ousterhout は，すべてのラッチに 0 の retardation を与えて扱う方法を 提案した.20) これによって各ラッチの入力信号のタイミング制約は他のラッチのそれと独立にな る. Ousterhout は，この手法を用いたタイミング解析ツール (CRYCTAL) を関発した． CRYSTAL は，レベルセンシティブラッチを含むループを扱う先駆的なものであるが， トランスペアレント動作をしているラッチから別のラッチヘの転送があるときのタイ ミングマージンの貸し借りを扱うことができない.23) つまり，悲観的すぎる解析結果を もたらしてしまう．ここで，“タイミングマージンの貸し借り ”を図 3.3 の例を用いて 説明する．図 3.3 で, L1 の入カデータは P2 までに到着すればよいが, もし,P1 に到着し たとすると t1 − t2 だけ L1 はデータを早く出せる．その結果，L1 と L2 間の設計が楽に なり，逆に，L1 はそれを貸している分 L1 とその前段のラッチ間の設計が苦しくなると いう現象を指している．この場合，L1 は L2 にタイミングマージンを貸していて，L2 はそれを L1 から借りている．Timing borrowing あるいは Cycle stealing などと呼ばれ 24 図 3.2 異なるクロックの相の信号のゲーティング. る. これを利用すれば自由度の高いタイミング設計が可能となり結果としてタイミング 最適化が可能となる. 図 3.4 により具体的なタイミングの貸し借りを利用した一相レベ ル転送パイプラインにおけるタイミング貸し借りの例を示した. このパイプラインス テージの最終段におけるタイミングスラックを次段以降のタイミング最適化に利用す ることが出来る. ここでタイミングスラック, あるいは単にスラックとはタイミング上 の余裕度, あるいはマージンのことであり, STA では一般にスラックという用語を用い る. 例えばセットアップタイム基準できまる信号の到着時刻より, このスラックの値だ け余裕をもってデータが到着していることを表す. レベルセンシティブラッチの場合, その入力の到着時間に依存してラッチからのデータの出発時間が早められるため次段 のラッチにおける信号の取り込みがその分だけ楽になる. 他方，Agrawal は，クロック周期の境界を超えて，その入力にデータが転送される ラッチにだけ retardation を与える方法を提案した.17) このような方法で, 上記のタイミ ングマージンの貸し借りを扱うことを可能にした．しかし，この方法は，その上のよ うなラッチをタイミングトレースの終点として扱っているため，クロック周期間のタ イミングマージンの貸し借りは扱えない.23) 上記の二つの研究においては, retardation は定数であった．より後になって，Szyman- ski，および，Dagenais と Runamin は，retardation を変数と考えるタイミング解析手法 を提案した.21), 23) さて，ここで本論文と同じパストレース法を採用している Dagenais 25 図 3.3 タイミングマージンの貸し借り. と Runamin によって行われたものの紹介と問題点を比較のために述べる. Dagenais と Runamin のタイミング解析ツールである TAMIA はパス探索の手法とし ては，Breadth First Search 法を採用している．彼らは，異なるクロックの相間，およ び，異なるクロックの周期間のタイミングマージンの貸し借りを扱うことができる手 法を提案した．ところで，Breadth First Search 法は，上記のゲーティングを扱うのに は適していない.22) そのため，TAMIA は，上記のようなゲーティングを含む回路のタ イミング解析の場合，通常，クロックの相数回だけ各エレメントを処理しなければな らない．処理の内容は，各エレメントについて，相数回だけの接続エレメントヘのメッ セージ送信処理と，回路の構造 (上記のゲーティングを含む場合のその周辺の構造) に 依存して決まる数のエレメントについての，相数回だけのディレイモデルの評価であ る．一般に，メッセージ送信処理に比べてディレイモデルの評価は複雑で，時間がか かる.22) 更に，レベルセンシティブラッチを含むフィードバックループが存在し、上記のゲー 26 図 3.4 サイクルスティーリングの例. ティングがループに存在するか，ゲーティングされた信号がループに入力される場合 を考えると，あるラッチに与えられた retardation の影響がループを１周するまでに, 各 エレメントは，N · M 回だけメッセージ送信処理が施され，また，ループを構成するエ レメントのディレイモデルは，この場合，最悪で N 0 回評価される．ここで，N は，こ の回路のクロックの相数, N 0 はゲーティングに関係する相数であり，M は，このルー プを信号が１周するのに要する周期数である．各ラッチに与えられた retardation が安 定するまで上記の処理を繰り返す． これに対し，本論文では，レベルセンシティブラッチを含むループ，および，異な るクロックの相に同期する信号のゲーティングをもった回路も正確に、効率良く扱う ためにクロックレベル, クロックレベル伝搬処理，日付変更線処理, および, 拡張された retardation という概念を用いた手法を提案している. この手法により得られた結果を まとめると以下のようになる． (1) フィードバックループが存在しない場合は，各エレメントの処理回数は１回である． (2) フィードバックループが存在する場合でも，retardation の影響がループを１周す るのに要する各エレメントの処理回数は１回である． (3) 従って，ループの安定タイミングを求めるための各エレメント当りの処理回数は 27 著しく軽減される. (4) (1)，(2), (3) は，異なるクロックの相に同期する信号のゲーティングが存在する 場合でも変わらない． (5) 異なるクロックの相間，および，異なるクロックの周期間のタイミングマージン の貸し借りを扱うことができる． 最後に, 本章の構成を述べると, 2) 節で提案する手法で導入する概念の定義，3) でそ れらの概念を用いたアルゴリズムの概要と議論, および, 既存手法との比較，4) 節で実 験結果について述べる. 2) 準備 対象回路に対する仮定 多相クロック同期回路（但し, 異なる周期をもつクロックの相の混在を許さない）の 静的タイミング解析を扱う．ここでいう同期回路は，いわゆる完全同期回路，すなわ ち, データ信号が直接（クロック信号とゲートされることなしに）クロックピンに入り， それによって，出力信号が変化することはないとする．また，データ転送は，同一周 期内か，継続する次の周期内に完了するものとする．つまり，多周期かけてデータを 転送することはないものとする. 概念の定義 ここで，まず, 必要ないくつかの概念の定義を行う. [定義１］（クロックレベル） 多相クロック回路の場合，そのクロックの相を要素とす る集合を P , 整数の集合を N とする．P から N への写像を f とする．f : P → N このとき，写像 f が次の性質をもつように定められているならば, クロックの相 P はクロックレベル f (P ) をもつと言う． 図 3.5 によって f の性質を説明する. 図 3.5 では，クロックの相，Phase 1(Phase2) と Phase3 間のデータ転送は許容され，Phase1 と Phase2 間のデータ転送は同相転送で あるという意味で許容されない．具体的には，Phase1，あるいは, Phase2 に同期し た信号を Phase3 のクロックで取り込む動作は同一のクロック周期で行われること 28 図 3.5 クロックレベルの定義の例. を表現するため Phase1(Phase2) にはレベル 10[f (P hase1) ＝ 10，f (P hase2) ＝ 10] を与え，Phase3 には 20[f (P hase3) = 20] を与える．このようにクロックレベル が昇順，あるいは，同一であるデータの取込み動作は同一周期に行われ，降順で あるデータの取込み動作はクロックの周期の境界を超えて行われるように f を決 める．クロックレベルを与える写像 f は，対応するクロックシステムをどういう 転送関係のもとで設計者が用いるかによって決まる． [定義終] 従って，f を決めるにあたって，f (P ) の値そのものは重要ではなく，P1 , P2 とかが どのような転送関係にあるかによって決まる f (P1 ) と f (P2 ) との大小関係のみが重要 である．ある相 P のクロックが特定のラッチに供給されている場合，このラッチはク ロックレベル f (P ) をもつと言う． 例えば, 図 3.7 でラッチ L1 はレベル k もち，L2 はレベル k1 と k2 をもつと言う. ま た，それぞれの出力信号に対しても, 対応するレベルのクロックに同期しているという 意味で, L1 の出力信号はレベル k をもつと言う. また一相クロックであっても図 3.6 の ように反転レベルを用いるパイプライン転送の場合に反転レベルがイネーブルレベル であるようなラッチには伝搬された元々のクロックレベルに正の整数を加算すること 29 で２相クロックと見なし, 扱うことにする. このようにすることで統一的に効率的な扱 いが可能となる. 図 3.6 一相反転レベル転送（ラッチベースパイプライン）. 図 3.7 ラッチへのクロックレベルの割り当て. [定義２]（クロックレベル伝搬処理） クロックレベルは，遅延計算されるパスにそっ て各エレメントのピンに伝えられる．この処理をクロックレベル伝搬処理と呼ぶ． [定義終] クロックレベル伝搬処理の過程で，伝搬されるクロックレベルが変更を受ける場合 がある．それを図 3.8 に示す．この処理はパストレースがラッチを通過するときに行わ れ，ラッチの入力ピンに伝わったクロックレベルは，そのラッチに供給されているク ロックのレベルに変更される． 次に拡張された retardation を定義する. [定義 3]（retardation） retardation とは、ラッチの入力信号が，そのラッチの供給ク ロックのイネーブルエッジから測ってどれだけ遅れて到着したかを表す遅延値（イ 30 図 3.8 クロックレベルの伝搬. ネーブルエッジに間に合っている場合は負の値となる）であり，ラッチがもって ［定義終］ いるクロックレベルごとに定義される（図 3.9）． クロックレベルごとに retardation を定義することの意味は以下で明らかになる. クロック周期 (多重化された周期) の取扱いと日付変更線処理 本論文の手法では，転送される信号の変化が起こったクロック周期の始まりから，す べての変化の時刻，および，後出する到着時間を測っている．対象回路に対する仮定 により，どのクロック周期にデータ転送が行われるかを知る必要はなく，単に，デー タ転送が，それが発せられた周期内に完了するか，次の周期内に完了するかを知りさ えすればよい．それを知るために用いられるのがクロックレベルである. それが発せ られた周期は多相，多周期にわたる検証を代表している周期であるという意味で多重 化された１周期である．本論文では多重化された１周期を一つ固定する．そして，す べての時刻は，この周期の始まりから測るものとする．今，あるラッチ L1 とラッチ L2 間のデータ転送の検証を考える．このとき L2 の到着時間 (信号の変化の時刻が，特に， ラッチ等に取り込まれるべき有意のデータが確定する時刻であるとき，その時刻を到 着時間と呼ぶことにする) に対する表 3.2 に示す補正処理を日付変更線処理と呼ぶこと にする． 表 3.2 において到着時間は補正前の到着時間を表している. 表に示すように，この処 理はデータ転送がクロックの周期の境界を超えて，次の周期に及んだときに、ラッチ の入力ピンや，外部出力ピンなどの検証が必要なピンで行われる． 31 図 3.9 クロックレベルごとの retardation. 以下に，日付変更線処理が行われたときのタイミング解析 (セットアップタイムの場 合) の式を示す． ArrivalT ime − ClockP eriod < P hase + P ulseW idth − SetupT ime + Skew (3.1) 式 (3.1) の右辺の値は, L1 にクロックが入るクロック周期の終わり (すなわち，次の 周期の始まり) から測った値である． 左辺の値を同じ基準点から測った値にするために日付変更線処理が必要になる．従っ 表 3.2 日付変更線処理後の修正された到着時間. K1 ≤ k2 K1 > k2 フォワードトレース 到着時間 到着時間-周期 バックワードトレース 到着時間 到着時間+周期 32 て，多重化した１周期で検証を行う本論文の手法においては，データの到着時間の遅れ を表す retardation も, どのクロックレベルで日付変更線処理を行った後での retardation であるかを示してはじめて意味を持つことになる. 遅延モデル 本論の議論は詳細な遅延モデルに依存するものではないが, 以下の議論では，一定の モデルを想定していた方が説明上都合がよい．そこで，本章では次の遅延モデルを想 定する．まず，信号の配線抵抗を無視する．従って，あるエレメントの出力変化の時 刻は，それに接続するエレメントの入力変化の時刻と等しい．特に，同一信号のファ ンアウト先の各エレメントの入力変化の時刻は相互に等しい．また，各エレメントに 対して，出力と入力の負荷容量に依存した伝搬遅延が，入力ピンと出力ピンの対ごと に定義されているとする．回路に存在する遅延はこの遅延のみとする．すなわち，配 線の負荷容量，エレメントのドライブ能力等に依存する遅延，エレメント内部の固定 ゲート遅延は，すべて，上記の遅延に含まれているとする. 3) アルゴリズム 提案する手法の概要 提案する手法の概要を図 3.10 に示す． 提案の手法においては，拡張した retardation を用いており，トレースの始点と終点 は外部入力ピンと外部出力ピンのみである．始点と終点にはバリッドタイムと呼ばれ るタイミング仕様が与えられるが，それは信号の値が確定した時刻（あるいは新しい 信号の値に変化した時刻）と，その信号が同期しているクロックのクロックレベルか らなっている． はじめに，外部クロックピンのみからトレースを行い，クロックレベル伝搬処理に よって各ラッチにクロックレベルを与える．ラッチがどのクロックレベルをもっている かは，クロック定義のみに依存し，静的に決まっている．次に，データ信号のトレース を行う．トレースはバックワード，フォワードの両方向を行う．このとき，セットアッ プタイム等の検証を行う．もし，上記のトレース後に回路に未トレース部分があれば それはフィードバックループの存在を意味する． 未トレース部から任意のラッチを選択し，retardation の初期値を与え，そのラッチ 33 図 3.10 アルゴリズムのアウトライン. をトレースの始点に新たに加える．このラッチを始点としたトレースによってもなお 未トレース部分が残るならば，更に未トレース部からの始点の追加を繰り返す．この 初期値としては，ラッチのセットアップタイムエラーを起こさない限界値か、0 のいず れの値に設定してもアルゴリズムは構成可能であるが，ここでは 0 に設定した．この 初期値はトレースによって増加した場合に更新される． 回路は retardation が安定するまで繰り返しトレースされる. ratardation が安定して いるか否かの判定はラッチのクロック入力信号がもっているクロックレベルごとに行 われる (retardation の拡張). データ信号のトレース時には，外部データピンに与えた クロックレベルも伝搬され，その信号がクロックの周期の境界を超えてラッチの入力 に供給されたか否かを判定するのに用いられる (日付変更線処理)．安定が実現された 状態で各ラッチの入力ピンでセットアップタイム等の検証を行う．最後に，外部出力 ピンからループまでの検証を行う．なお，検証は目付変更線処理後の到着時間に対し て行う. 34 詳細についての議論 以下に，アルゴリズムの詳細を, 異なるクロックレベルをもつ信号のゲーティングの 扱い，および，フィードバックループの扱いについて述べる． 特に断らない限り，フォーワードトレース時のセットアップタイムチェックについて のみ議論する． (１) ゲーティングの扱い 図 3.11 に, ゲーティングにおいて最悪タイミング (悲観的変化時刻) がどのように決 定されるかを示す． 図 3.11 最悪タイミングの選択. ここで，最悪タイミングとは，この時刻で検証を行えば，このエレメントの出力信 号の他の変化の時刻での検証を省略できるという意昧での代表の時刻である．図 3.11 において，tk は信号の入力時刻を示し，t(i)k はこの信号 tk の中でクロックレベル i を 持つ信号の到着時間を示す. すなわち t(i)1, t(i)2, …, t(i)n は, t1, t2, …, tn のそれぞれのクロックレベル i を持つ到 着時間を表す. もし, クロックレベル i を持つ信号を tk が持たない場合には t(i)k は −∞ を表すとする. また，tpd (Aj , Y ) は，このエレメントのピン Aj と Y 間の伝搬遅延を表 している．この最悪タイミングの計算は、そのエレメントでゲーティングされる信号 のクロックレベルごとに行なわれる. 従って，このようなエレメントの出力信号の最悪タイミングは，ゲーティングの対 象となるクロックレベルの数だけの複数のタイミング値 (信号変化時刻) からなる．こ の信号を取り込む次段のラッチで，最小のタイミングマージンを与えるという意味で 35 の最悪タイミングは，一つのタイミング値だけであるはずであるが，それをクロック レベルごとに計算する必要性を図 3.12 に示す． 図 3.12 複数クロックレベルの伝搬の必要性. 同時に，それはクロックレベル伝搬処理の必要性を示している．図 3.12 に示す回路 構成では，L2 あるいは L4 で最小のタイミングマージンを与える時刻は L2 あるいは L4 での日付変更線処理に依存するため，エレメント G においてはクロックレベルごとに 最悪タイミングを計算する必要がある. (２) フィードバックループの扱い 図 3.13 に基づいてフィードバックループの扱いを説明する． 図 3.13 には二つの基本閉路 loop1, loop2 がある．これらのループには五つのラッチ L1 , L2 , L3 , L4 , L5 が含まれている．仮に L1 , L3 , L4 がクロックレベル k1 (＝ 10) をもち， L2 , L5 がクロックレベル k2 (＝ 20) をもつとする．この回路はループをもっているから 外部入力カピンに対するタイミング指定のほかに，一部のラッチに対して retardation の任意の初期値 (本論文では初期値は 0) を与える必要がある．本手法では，どのラッチ に retardation を与えるかについては特に制限 (例えば, クロック周期の境界を横切って データ転送が行われるラッチであるなどの制限) を設ける必要がないので，ループの安 定タイミングを求めるための繰返し解析の回数を減らすために都合のよいラッチに対し て retardation を与えることができる自由度がある (但し，回数削減のために retardation 36 図 3.13 手法を説明する簡単な回路. を与えるべきラッチをどのように選択したらよいかは今後の課題であり，現状では，任 意のラッチに retardation を与えている)． この例では，L3 あるいは, L4 のどちらか一方のラッチに対して retardation の初期 0 を与えればよい．例えば, L3 に与えるとする. L3 に与えた retardation と, 外部入力ピ ンに与えたタイミング仕様とからエレメント G2 の入力ピン A, B における信号変化時 刻が求まる．それぞれ Ta , Tb とする．Ta はクロックレベル k2 をもち，Tb はクロックレ ベル k1 をもつ．従って，G2 の出力信号，すなわち，L3 の入力信号は到着時間 (時刻 Ta0 , クロックレベル k2 ) および，(時刻 Tb0 , クロックレベル k1 ) をもっている．ここで Ta0 は G2 の pin to pin ディレイを Ta に対して考慮したものである．L3 はクロックレベル k1 をもっており，k1 < k2 であるから，Ta0 は日付変更繰処理によって修正される．Ta0 は Ta0 −“ クロック周期 ”となる． 図 3.9 に示すように retardation の計算はラッチのクロックレベルごとに行われる．こ の retardation の更新を必要とするラッチは, retardation の初期値を与えたものである． この計算によって retardation が増加したなら，この新たな retardation に基づいて再び パストレースを繰り返す．この繰返し処理が収束することを示す必要かあるが，その 37 ために以下の定理を証明する. 定理 1 回路の各エレメントの出力信号の変化の時刻は，ループ解析のために始点とし て選ばれたラッチのクロックレベルごとの retardation の単調非減少関数である. (証明) クロックトレース処理によってラッチには静的にクロックレベルが割り付け られる. 従って, 図 3.8 に示すクロックレベルによって，回路の各出力信号がもつクロッ クレベルの組も繰返しパストレースによらず静的に確定している．ループ中のエレメ ントは組合せ回路とラッチに分類されるが，組合せ回路では図 3.11 により, 出力信号 のレベルごとの信号変化時刻が，入力信号のそれの単調非減少関数であり, トランスペ アレント動作をしているラッチにおいてもレベルセンシティブラッチの性質によりレ ベルごとに目付変更線処理された後での信号変化時刻に対して単調非減少である．ま た，ラッチの入力ピンが繰り返しトレースされるたびごとに，そこで同一の日付変更線 処理がされるから，始点として選ばれたラッチのレベルごとの retardation のどれかが 増加すれば回路の各エレメントの出力信号の変化の時刻は単調非減少変化をする．(証 明終) 定理により，回路の各エレメントの出力信号の変化の時刻は retardation を与えたい ずれかのラッチの retardation の単調非減少関数であるから，この出力変化時刻が減少 したり，振動したりすることはない．従って，ゆくゆくはタイミングエラーを引き起 こすか，一定の値に収束する．これによりこの回路のタイミング解析を完了すること ができる. 既存の手法との比較 まず，比較する上で処理の手数の意味を明らかにする．ある素子がトレースされる ことによって必要となる計算は次の二つである． (ａ) メッセージ送信処理 (ｂ) ディレイモデル評価処理 (ａ) は，ある素子のトレースの終了後に次にトレースが可能となる素子を選択する ために必要なその接続素子へのメッセージ送信処理である．ある素子に対して (ａ) の タイプの処理を行う回数とトレースされる回数は等しい．(ｂ) はワーストケースタイ ミング選択のために必要なディレイ計算である．一般に (ｂ) の方が (ａ) に比べて計算 量が大きい． 38 図 3.14 に示す例は，３相クロック同期回路である． 図 3.14 従来手法の処理手順. この回路は，別々のクロックの相 T1 と T2 とに同期する信号のゲーティング (G1 ) を もっている．クロックは T1 → T2 → T3 → T1 → T2 · · · のように供給されるとする．L1 でワーストケースのタイミング検証ができるためには従来の手法, 例えば, Dagenais の 手法と本論文の手法とでどのように処理手数が異なるかを比較する. Dagenais の手法 ではクロックの供給シーケンスは実際のそれを反映したものであるため１周期の間に 図 3.14 に示すように処理が行われる．図で太い線で示した素子とパスで遅延計算が行 われる．この手法では，ある相 (例えば T1 ) のクロックがイネーブルである期間に他の 相 (T2 ) にある素子も (ａ) のタイプの処理はされるから, １周期の間にすべての素子で ３回 (相数 (T1 , T2 , T3 )) 接続素子への (ａ) タイプの処理と，少なくとも１回の (ｂ) タイ プの処理が行われる．NOR ゲート G1 のようなエレメントでは，そのディレイモデル は２回評価される．しかも，この手法では回路全体を解析するのに要する周期数，言い 換えればあるラッチの retardation の影響が回路全体に伝わるのに要する周期数は，回 路に存在する最大長のパスのラッチ段数に依存する．従って，L2 , L3 の前段の構造に よってはフィードバックループが存在しない場合でも１周期のみで L1 のワーストケー スタイミングを検証することはできない． 39 一方、本論文の手法では実際のクロック供給シーケンスにとらわれることなく，T1 がイネーブルである期間の信号伝搬に対するタイミング解析と，T2 がイネーブルであ る期間の信号伝搬に対するタイミング解析とをクロックレベル伝搬処理，日付変更線 処理によって１周期内に多重化して処理している．また，ループが存在しないときは retardation を与える必要がないので１周期内に回路全体，特に L1 においてワースト ケースの検証ができる．このときすべての素子のトレース回数, ディレイモデルの評価 回数とも１回である． しかも, この性質は回路にループが存在しないという以外に回路構造によらない．次 に, 図 3.15 に示すループが存在する回路を考える． 図 3.15 比較のためのサンプル回路. 図において矩形はラッチを示し，T1 , T2 , T3 はクロックの相を示している．この回路 は３クロックサイクルのフィードバックループをもっている. Dagenais の手法は CaseB に相当する．この手法では，斜線で示す三つのラッチに retardation の初期値を与えなければならない．エレメント L1 の retardation の影響が ループを１周するまでに３周期 (このループのサイクル数) 要する．１周期の間に各エ レメントは３回 (相数) トレースされるから retardation がループを一巡する間に各エレ 40 メントは 3 × 3 ＝ 9 回トレースされることになる．この間のディレイモデルの評価は通 常１回であるが, 図 3.15 のように信号のゲーティングが L1 と L2 の間に存在する場合 には，L1 から L2 までトレースを行う間にループ中の各エレメントは２回 (ゲーティン グに関係する相数) 評価される． 一方，本論文の手法は CaseA に相当する．この場合 retardation を与えるべきラッチ は L1 のみでよく, １周期内に retardation の影響が一巡する．この１周期内に各エレメ ントがトレースされる回数は１回である．従って，ディレイモデルの評価回数も１回で ある．このことは図 3.15 のような信号のゲーティングが存在する場合でも変わらない. 4) 実験結果 提案する手法はタイミング解析ツール T ACS4 として実現され, 実際の製品開発に適 用された. 表 3.3 はいくつかの実データに対する適用結果を示している． 表 3.3 ループ解析実験結果. 8bit counter test-data IO-chip CPU-chip 素子数 102 201 9714 31654 ピンペア数 159 393 21062 70791 ループ解析数 1 3 4 5 前処理用トレース 0.016 0.033 11.45 181.28 ループ解析 (1 回目）(sec.) 0.034 0.066 8.47 100.4 ループ解析（2 回目)(sec.) converge 0.084 7.92 62.05 ループ解析（３回目)(sec.) converge 0.066 10.13 98.5 ループ解析（4 回目)(sec.) converge converge 9.55 149.6 ループ解析〈5 回目)(sec.) converge converge convege 161.93 これらの適用結果は，手法の実用性と，そのいくつかの性質を示している．適用結 果によればループ解析の繰返し数は回路規模に応じて増加するが，その増加の仕方は， ある程度に規模が大きくなったところではゆるやかであることがわかる。 41 5) おわりに 多相クロック同期回路のタイミング解析を扱うための効率の良い, しかも，容易に実 現可能な手法を提案し，タイミング解析ツール T ACS4 として実現した．一般に最近 の多相クロック同期回路はレベルセンシティブラッチを含むループや異なるクロック の相に同期した信号のゲーティングをもっているが，T ACS4 はそれを効率良く扱うこ とができる．すなわち，既存の手法と異なり，外部ピン以外に，ループを解析するた めのトレースの始点をどのラッチにするかを特に限定することはなしに上記の回路を 解析可能である．しかも，retardation の変化の影響がループを１巡するまでに各エレ メントが処理される回数は１回である． これを可能にしたのは，導入したクロックレベルの概念，クロックレベル伝搬処理， 日付変更線処理，および，クロッレベルごとに定義する retardation である．また，レ ベルセンシティブラッチを扱う場合に問題となる異なるクロックの相間，および，異 なるクロックの周期間のタイミングマージンの貸し借りも扱うことが可能である．回 路の微細化等に伴いタイミングモデルがより複雑になった場合にここで述べたモデル の評価回数の削減が更に重要になってくると考えられる．また，ラッチ集合からの始 点のラッチの選び方で繰り返し回数は減らすことができると考えられるため, 提案す る手法において retardation を与えるべきラッチの自由度が大きいことは，より複雑な ループを含む回路に対して収束の速い手法を研究する上で有利な性質をもっていると 言える．同アルゴリズムを実装したツールは当時（∼1996 年）, IBM 互換, 計算機事業 で多数の LSI、基板のタイミング検証に適用した他, TV 会議 TV 電話用 DSP（CMOS) （1μm, 2 層 Al CMOS プロセス 538K トランジスタ, 面積:13.80mm × 15.4mm）, 幾何 学演算用 DSP（0.35μm,3 層 Al CMOS プロセス 1.3M トランジスタ, 面積:11.84mm × 12.07mm）など研究所での LSI 開発において, タイミング解析に適用し, 実用性も確認 した. レベルセンシティブラッチを扱うタイミング解析の繰り返し解析の収束条件をば らつきを想定した上で拡張することは今後の課題であり, 第６章に展望を述べる. 42