JPH0642253B2 - クリティカルパスの解析処理方式 - Google Patents

Description

【発明の詳細な説明】 〔概 要〕 大規模ディジタル回路における遅延時間の解析処理方式
に関し、 クリティカルパルスの追跡およびクロックスキューチェ
ックの高速化のため必要な記憶容量の削減を目的とし、 各フリップフロップ又はゲート回路の端子ピン毎に積算
遅延時間値と前段フリップフロップ又はゲート回路の端
子ピン番号を格納するクリティカルディレイテーブルを
作成するクリティカルディレイテーブル作成手段と、次
に遅延時間計算すべき次段フリップフロップ又はゲート
回路の端子ピン番号とクリティカルパスを開始点までさ
かのぼった開始ピン番号を格納するイベントテーブルを
作成するイベントテーブル作成手段を備え、遅延時間計
算の開始点から最終点まで、フリップフロップ又はゲー
トの各段毎に、クリティカルディレイテーブル及びイベ
ントテーブルを、互いに相手テーブルを参照しつつ作成
して、遅延時間計算処理を実行するよう構成する。

〔産業上の利用分野〕

本発明はＣＡＤ（計算機緩用設計）に係わり、特に大規
模なディジタル回路における遅延時間の解析方式に関す
る。

大規模なディジタル回路の設計においては、論理シミュ
レーションによって論理の正しさを確認すると共に、フ
リップフロップ間の遅延時間を算出し所定の許容範囲に
あるかを検証することが行われる。大規模ディジタル回
路の遅延時間計算処理には大きな計算機処理時間を要す
るため、効率的な計算方式が要望される。

〔従来の技術〕

大規模なディジタル回路の遅延時間計算処理では、考え
られる全てのパス（経路）を計算するには膨大な計算機
処理時間を要するため、一番厳しいパス（通常最も遅延
時間の大きいパスであるが、最も遅延時間の小さいパス
の場合もある。以下、クリティカルパスと呼ぶ）の遅延
時間（以下、ディレイと呼ぶ）を計算する方式をとって
いる。

第５図は従来の遅延時間計算処理方式を説明するための
図である。

図(a)は、遅延時間の計算処理の対象となるディジタル
回路の例である。図(a)において、Ａ，Ｂ，Ｃ，Ｈ，Ｉ
はフリップフロップ回路（以下ＦＦと略記する）を、
Ｄ，Ｅ，Ｆ，Ｇは途中のゲート回路を示す。

また、ａ，ｂ，ｃ，ｍ，ｎはＦＦのクロックピンを示
し、ｄ，ｅ，ｆ，ｇ，ｈ，ｉ，ｊ，ｋ，ｌはＦＦ又はゲ
ートの入力ピンを示す。

遅延時間計算処理は、ＦＦのＡ，Ｂ，Ｃのクロックピン
ａ，ｂ，ｃを出発点として、クリティカルパスによるデ
ィレイ（以下、クリティカルディレイと呼ぶ）計算を開
始し、ＦＦ−Ｈ，Ｉのデータ入力ピンｋ又はｌに到達す
るまで計算処理する。本例では、クリティカルパスは最
もディレイの大きいパスとする。

計算処理は、出発点のＦＦから最終のＦＦまで、各ゲー
ト段ごとに次々とディレイ値を積算して積算ディレイ値
を計算し、複数入力のゲート段では、その各入力ピンま
での積算ディレイ値のうち最も大きい値を示すピンを通
る経路をクリティカルパスとして、この積算ディレイ値
を使用して次段ピンまでのディレイを加算したものが次
段ピンの積算クリティカルディレイ値である。このよう
にして、最終段ＦＦの入力ピンまでの積算クリティカル
ディレイ値を計算する。第５図(a)に示したディジタル
回路に対する計算処理は、同図(b)に示すように、以下
に説明する手順で行われる。

クロック入力端子CLK1からＦＦ−Ａのピンａまでのデ
ィレイｔａを回路構成データによる経路長から計算す
る。

同様にクロック入力端子CLK2からＦＦ−Ｂのピンｂま
でのディレイｔｂを計算する。

同様にクロック入力端子CLK3からＦＦ−Ｃのピンｃま
でのディレイｔｃを計算する。

ＦＦ−ＡにおけるディレイとＦＦ−Ａの出力ピンから
ゲートＤの入力ピンｄまでの経路長によるディレイを加
算して、ピンａからピンｄまでのディレイを算出し、こ
れにｔａを加えた値をピンｄのディレイｔｄとして算出
する。

同様に、ＦＦ−ＢにおけるディレイとＦＦ−Ｂの出力
ピンからゲートＤの入力ピンｅまでの経路長によるディ
レイに、ｔｂを加算してピンｅのディレイｔｅを算出す
る。

同様に、ゲートＥの入力ピンｆのディレイｔｆを算出
する。

同様に、ゲートＥの入力ピンｇのディレイｔｆを算出
する。

ゲートＤの入力ピンｄとｅのディレイｔｄとｔｅを比
較する。ｔｄ＜ｔｅであれば、ピンｅを通るパスをクリ
ティカルパスとする。

同様に、ゲートＥの入力ピンｆとｇのディレイｔｆと
ｔｇを比較し、ｔｆ＜ｔｇであればピンｇを通るパスを
クリティカルパスとする。

ゲートＥにおけるディレイとゲートＦの入力ピンｈま
での経路長によるディレイに、クリティカルパスによる
ディレイｔｇを加えて、ゲートＦの入力ピンｈにおける
クリティカルパスを通るディレイの積算値：クリティカ
ル積算ディレイｔｈを算出する。

同様に、ゲート回路ＤにおけディレイとゲートＧの入
力ピンｉまでの経路長によるディレイに、クリティカル
パスによるディレイｔｅを加えて、ゲートＧの入力ピン
ｉのクリティカル積算ディレイｔｉを算出する。

同様に、ゲートＧの入力ピンｊのクリティカル積算デ
ィレイｔｊを算出する。

ゲートＧの入力ピンｉとｊのディレイｔｉとｔｊを比
較する。ｔｉ＜ｔｊであれば、ピンｊを通るパスをクリ
ティカルパスとする。

ゲートＤにおけるディレイとゲートＨの入力ピンｋま
での経路長によるディレイに、クリティカルディレイｔ
ｅを加えて、ゲートＨの入力ピンｋにおけるクリティカ
ル積算ディレイｔｋを算出する。

ゲートＧにおけるディレイとゲートＩの入力ピンｌま
での経路長によるディレイに、クリティカルディレイｔ
ｊを加えて、ゲートＩの入力ピンｌにおけるクリティカ
ル積算ディレイｔｌを算出する。

以上の計算の結果、最終段のＦＦであるＨとＩの入力ピ
ンｋ及びｌにおけるクリティカル積算ディレイが得ら
れ、ディレイが設計基準に適合するかをチェックするこ
とできる。

このディレイ計算をしたディジタル回路の設計者は、ク
リティカルディレイ値を知りたいだけではなく、どのよ
うなルートであったかも知りたい場合がある。また、Ｆ
Ｆのピンにおけるディレイチェック（以下、ＦＦチェッ
クと呼ぶ）を行うには、クリティカルパスの開始側及び
終了側のＦＦ間のクロックスキューも関係する。

例えば、ＦＦ−Ｈのデータ入力ピンｋに至るクリティカ
ルパスが破線で示すごとく、ｂ→ｅ→ｋであったとする
と、ＦＦ−Ｈにおけるディレイチェックは、データ入力
ピンｋとクロックピンｍの間で行われ、スキューはクロ
ックCLK1とCLK2の関係で決まる。即ち、 Ｔcd＋Ｔｄ＋Ｔskew≦Ｔcm＋τ を満足するかがチェックされる。

ここに、 Ｔcb：ＬＳＩ端子からピンｂまでのディレイ。

ＴCM：ＬＳＩ端子からピンｍまでのディレイ。

Ｔｄ ：ピンｋまでのクリティカルディレイ値。

Ｔskew：CLK1とCLK2間のスキュー値。

τ：クロック周期。

例えば、ＦＦ−Ｉのデータ入力ピンｌに至るクリティカ
ルパスが破線で示すごとく、ｃ→ｇ→ｈ→ｊ→ｌであっ
たとすると、ＦＦチェックは、データ入力ピンｌとクロ
ックピンｎの間で行われ、同一クロックCLK3であってク
ロックスキューはない。

従来、クリティカルパスの追跡を高速に行い、且つクロ
ックスキューのチェックを早急に求めるためには次の方
法が採られていた。

(1)通過する全部のピンについてクリティカル積算ディ
レイ値と共に、クリティカルパスの開始ピンの番号を、
記憶させておき、終了ピンまで伝達させることにより、
ＦＦチェック時の開始クロックピンの情報をすばやく入
手する。

(2)クリティカルパス上の各ピンにおいて、クリティカ
ル積算ディレイ値と共に、前段のピン番号を記憶させて
おく。これにより、、再度ディレイ計算なしでクリティ
カルパスの追跡ができるようにする。

(3)(1)と(2)の併用で、クリティカルパス上の各ピンに
おいて、クリティカル積算ディレイ値に加えて、前段の
ピン番号と開始ピン番号の両方を記憶させておく。

〔発明が解決しようとする問題点〕

上記従来のクロックピン情報入手の方法(1)〜(3)によれ
ば、次のような問題点があった。

(1)クリティカルディレイ算出後、クリティカルパスを
辿るには、再度ディレイ計算が必要となる。

(2)クリティカルパスは終了ピンから逆追跡すれば簡単
に見つかるが、チェック時に開始ピンを見つけるとき
も、常に逆追跡をする必要がある。

(3)大規模回路では全体回路のピン数が数万〜百万にも
なり、前段ピン番号と開始ピン番号の両方を記憶させる
ことは記憶容量的に問題がある。

本発明は、このような従来の問題点を解消したクリティ
カルパスの解析処理方式を提供しようとするものであ
る。

〔問題点を解決するための手段〕

第１図は、本発明のクリティカルパスの解析処理方式の
原理ブロック図を示す。

図において、１はクリティカルディレイテーブルであ
り、各ピン毎に積算遅延時間値11と前段のピン番号12を
格納する。

２はイベントテーブルであり、次に遅延時間値計算すべ
き次段ピン番号21とクリティカルパスを計算開始点まで
さかのぼった開始ピン番号22を格納する。

３はクリティカルディレイテーブル作成手段であり、イ
ベントテーブル２を参照しつつ各段のフリップフロップ
又はゲートのピンごとにクリティカルディレイテーブル
を作成する。

４はイベントテーブル作成手段であり、クリティカルデ
ィレイテーブル１を参照しつつ各段ごとにイベントテー
ブル２を作成する。

〔作 用〕

イベントテーブル２は各ＦＦ段毎に備え、イベントテー
ブル２には次に計算すべき次段ピン番号21を記憶し、遅
延時間値計算を進行させる。このイベントテーブル２
に、次に計算すべきピン番号21と共に開始ピン番号22も
記憶させる。

各ピン毎の積算遅延時間値の計算は、イベントテーブル
２の指示する順序で行われ、計算した積算遅延時間値11
は、前段ピン番号12と共にクリティカルディレイテーブ
ル１に格納する。イベントテーブル２は各ゲート段毎に
作成され、二つのゲート段分準備しておけばよく、処理
の済んだゲート段のテーブルの領域は、新しいゲート段
のテーブルの領域として使用することができる。

計算が次々と伝達されて、最終ピンに到達したところ
で、イベントテーブル２を開始ピンテーブルとして保存
する。別途格納してある開始ピンへのクロックと最終ピ
ンへのクロックの情報により、ＦＦチェックのためのク
ロックスキューを求めることができる。

以上のように、開始ピン情報は各ピン毎に持たせる必要
なく、二つのＦＦ段のピン分だけで済むから所要記憶容
量は大幅に縮小される。

例えば、ピン数が50万ピンであるとし、ゲート段数が20
段であるとし、開始ピン１本当り８バイトを要するとす
ると、開始ピン情報に要する記憶容量は、クリティカル
ディレイテーブルに設ける場合は、50万×８バイト＝40
0万バイトとなり、イベントテーブルに記憶させる場合
は、１ゲート段分のイベントテーブル２の予想量は50万
ピン／20段＝2.5万であるから 約2.5万×２×８バイト＝40万バイトとなる。

〔実施例〕

以下第２図乃至第４図に示す実施例により、本発明をさ
らに具体的に説明する。

第２図は、本発明の一実施例の処理装置における主記憶
上のメモリ使用状況を示す図である。

図において、20はイベントテーブル領域であり、２ゲー
ト段分のイベントテーブルを格納する大きさを持つ。

10はクリティカルディレイテーブル領域であり、解析処
理対象回路のピン数分のクリティカルテーブルを格納す
る大きさを必要とする。

30はクリティカルディレイテーブル作成プログラム領域
であり、積算ディレイルーチンその他を格納する。

40はイベントテーブル作成プログラム領域であり、次段
ピン検出ルーチン、ディレイ比較ルーチン、開始ピン検
出ルーチンを格納する。

50は回路構成データ領域であり、設計されたディジタル
回路の構成を示す各種データを格納する。

60は初期データ領域であり、開始ピン番号、最終ピン番
号、クリティカルの定義（ディレイ最大か最小か）等の
初期条件を格納する。

第４図は、本発明の一実施例による処理を示すフローチ
ャートである。

第３図は、本発明の一実施例による処理例を示す図であ
る。

第３図において、Ａ〜Ｉ，ａ〜ｌ及びCLK1〜CLK3は、第
５図と同じく、それぞれＦＦ又はゲート、ピン及びクロ
ック端子を示す。

テーブル(2)−１は、第１ゲート段のイベントテーブル
を示し、テーブル(2)−２は第２ゲート段のイベントテ
ーブルを示す。テーブル(1)−１は、第１ゲート段に属
するＦＦの各ピン毎のクリティカルディレイテーブルを
示し、テーブル(1)−２は第２ゲート段に属するゲート
の各ピン毎のクリティカルディレイテーブルを示す。テ
ーブル(3)は、最終ゲート段のイベントテーブルであ
り、これが開始ピンテーブルとなったことを示す。

以下、第４図のフローチャートの各ステップに従って、
第２図および第３図を参照して本実施例による処理の流
れを説明する。

イベントテーブル作成プログラムは、データ領域に格
納してある初期条件データ中の開始ピン情報を読み出
し、回路構成データを参照してテーブル(2)−０を作成
し、イベントテーブル領域に格納する。これには、次段
ピン及び開始ピン情報として共にａ，ｂ，ｃが記載され
る。テーブル(2)−０の作成を終わればクリティカルデ
ィレイテーブル作成プログラムに制御を渡す。

クリティカルディレイテーブル作成プログラムは、テ
ーブル(2)−０に従って、ピンａ，ｂ，ｃの積算クリテ
ィカルディレイ値ta,tb,tcの計算を行い、前段ピン番号
も記載してテーブル(1)−１を作成し、クリティカルデ
ィレイテーブル領域に格納する。積算クリティカルディ
レイ値ta,tb,tcはそれぞれクロック端子CLK1,CLK2,CLK3
からピンa,b,cまでのディレイ値であり、前段ピン番号
はa,b,cである。テーブル(1)−１の作成を終われば制御
をイベントテーブル作成プログラムに渡す。

イベントテーブル作成プログラムは回路構成データか
ら、次に計算すべき次段ピンｄとその開始ピンａ、次段
ピンｆとその開始ピンａ、同様にｅとｂ、ｇとｃを記載
したテーブル(2)−１を作成し、イベントテーブル領域
に格納する。

クリティカルディレイテーブル作成プログラムは、テ
ーブル(2)−１に従って、ピンａからピンｄ、ピンａか
らピンｆ、ピンｂからピンｅ、ピンｃからピンｇまでの
ディレイ値を計算し、それぞれテーブル(1)−１のta,t
b,tcを加算した値ta,te,tf,tgを積算クリティカルディ
レイ値としてテーーブル(1)−２を作成しクリティカル
ディレイテーブル領域に格納する。

イベントテーブル作成プログラムは、回路構成データ
を読み次に計算すべき次段ピンをk,i,hとする。次い
で、初期データ領域からクリティカルの方向を読み、デ
ィレイの大きい側であることを認識し、ピンｄとｅの積
算クリティカルディレイ値をテーブル(1)−２から読ん
で比較し、td＜teであったからピンｅを通るパスをピン
ｋへのクリティカルパスとして開始ピンをｂとし、同様
にtf＜tgであったからピンｇを通るパスをピンｈへのク
リティカルパスとして開始ピンをｃとする。次段ピン
ｋ，ｉ，ｈと開始ピンｂ，ｂ，ｃとしてテーブル(2)−
２を作成し、イベントテーブル領域のテーブル(2)−０
の格納されていた場所に格納する。

クリティカルディレイテーブル作成プログラムは、テ
ーブル(2)−２に従ってピンｈのディレイ計算を行い、
テーブル(1)−３を作る。ピンｇを通るパスがクリティ
カルであるから、ピンｇからピンｈまでのディレイ値を
計算しこれにtgを加えた値を積算クリティカルディレイ
値thとし、前段ピン番号ｇを付けてテーブル(1)−３を
作り、クリティカルディレイテーブル領域に格納する。

イベントテーブル作成プログラムは、テーブル(1)−
３の結果からピンｊに関するテーブル(2)−３を作り、
イベントテーブル領域のテーブル(2)−１の格納されて
いた場所に格納する。

クリティカルディレイテーブル作成プログラムは、ピ
ンｉおよびピンｊについてディレイ計算し、テーブル
(1)−４を作りクリティカルディレイテーブル領域に格
納する。

イベントテーブル作成プログラムは、ピンｌについて
のイベントテーブル(2)−４を作る。そのためには、テ
ーブル(1)−４を読み、ピンｉとピンｊの積算クリティ
カルディレイ値を比較し、ti＜tjであったから、ピンｌ
へのクリティカルパスはピンｊを通るパスであることが
判り、開始ピン番号としてｃを記載する。作成したテー
ブル(2)−４はイベントテーブル領域のテーブル(2)−２
のあった場所に格納する。

クリティカルディレイテーブル作成プログラムは、ピ
ンｋについてディレイ計算を行いテーブル(1)−５を作
る。即ち、テーブル(2)−２からクリティカルパスはｂ
→ｅ→ｋであることが判るから、ピンｅからピンｋまで
のディレイを計算しteを加算してtkを算出し、前段ピン
番号ｅを付加する。次いで、ピンｌについてディレイ計
算し、テーブル(1)−５を作る。即ち、クリティカルパ
スはピンｊを通るパスであるから、ピンｊからピンｌへ
のディレイを計算し、これにｔｊを加算して積算ディレ
イ値ｔｌとし、前段ピン番号ｊを付加する。テーブル
(1)−５が、求める最終段のピンｋおよびｌの積算クリ
ティカルディレイ値ｔｋおよびｔｌである。作成したテ
ーブルはクリティカルディレイテーブル領域に格納す
る。

イベントテーブル作成プログラムは、テーブル(2)−
２とテーブル(2)−４から最終ピンｋとピンｌの開始ピ
ン情報ｂ，ｃを抜き出してテーブル(3)としてイベント
テーブル領域に保存する。テーブル(3)からクロックス
キューチェックに必要な開始ピンを知ることができる。

〔発明の効果〕

以上説明のように本発明によれば、大規模ディジタル回
路のディレイ解析において、所要記憶容量が少なくて、
クリティカルパスの追跡およびクロックスキューのチェ
ックを高速に行うことができ、データ処理効率の向上に
寄与する効果は大である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の一実施例におけるメモリ使用状況を示
す図、 第４図は本発明の一実施例による処理を示すフローチャ
ート、 第３図は本発明の一実施例による処理例を示す図、 第５図は従来例による処理例を示す図である。 図面において、 １はクリティカルディレイテーブル、 ２はイベントテーブル、 ３はクリティカルディレイテーブル作成手段、 ４はイベントテーブル作成手段、 10はクリティカルディレイテーブル領域、 11は積算遅延時間値、12は前段ピン番号、 20はイベントテーブル領域、 21は次段ピン番号、22は開始ピン番号、 30はクリティカルディレイテーブル作成プログラム領
域、 40はイベントテーブル作成プログラム領域、 50は回路構成データ領域、60は初期データ領域、 をそれぞれ示す。

Claims (1)

【特許請求の範囲】
1. 【請求項１】大規模ディジタル回路における遅延時間の
   解析処理方式であって、 各フリップフロップ又はゲート回路の端子ピン毎に積算
   遅延時間値(11)と前段フリップフロップ又はゲート回路
   の端子ピン番号(12)を格納するクリティカルディレイテ
   ーブル(1)を作成するクリティカルディレイテーブル作
   成手段(3)と、 次に遅延時間計算すべき次段フリップフロップ又はゲー
   ト回路の端子ピン番号(21)とクリティカルパスを開始点
   までさかのぼった開始ピン番号(22)を格納するイベント
   テーブル(2)を作成するイベントテーブル作成手段(4)を
   備え、 遅延時間計算の開始点から最終点まで、フリップフロッ
   プ又はゲートの各段毎に、クリティカルディレイテーブ
   ル(1)及びイベントテーブル(2)を、互いに相手テーブル
   を参照しつつ作成して、遅延時間計算処理を実行するよ
   う構成したことを特徴とするクリティカルパスの解析処
   理方式。