(57)【特許請求の範囲】
【請求項１】
信号が接続された端子を備えた回路素子であるセルを有する電子回路において、それぞれ共通の始点の端子から共通の終点の端子に至る複数の前記セルを通過する信号経路を探索する方法であって、
前記共通の始点の端子から前記共通の終点の端子に至る複数の信号経路のなかで他の信号経路と区別すべき信号経路を探索する所定の条件を、前記複数の信号経路内の複数の前記端子毎に設定するステップと、
前記複数の信号経路のうち、前記所定の条件を満たす信号経路の探索を行うステップと、
をコンピュータに実行させることを特徴とする経路探索方法。
【請求項２】
信号が接続された端子を備えた回路素子であるセルが組み合わせて設計された電子回路において、それぞれ共通の始点の端子から共通の終点の端子に至る複数の前記セルを通過する信号経路を探索する方法であって、
前記共通の始点の端子から前記共通の終点の端子に至る複数の信号経路のうち、信号経路が同一の端子を通過することにより前記同一の端子に合流する信号経路が２つ以上有る場合には、前記２つ以上の信号経路のうちいずれかの信号経路を選択する第１の選択条件を前記同一の端子に設定するステップと、
前記同一の端子について、前記第１の選択条件を満たす信号経路が２つ以上有る場合には、第２の選択条件を用いて１つだけの信号経路を選択し、前記共通の始点の端子から前記共通の終点の端子に至る信号経路の探索を行うステップと、
をコンピュータに実行させることを特徴とする経路探索方法。
【請求項３】
前記第１の選択条件は、
前記同一の端子のセルと、前記同一の端子のセルの直前のセルに供給されるクロック信号の供給源と位相が同一であり、かつ、
前記同一の端子と、前記同一の端子のセルの直前のセルが有する端子に設定された経路識別子が同一であることを特徴とする請求項２記載の経路探索方法。
【請求項４】
前記第２の選択条件は、
各信号経路の遅延時間を算出しながら経路探索を行っている場合には、所定の始点の端子から前記同一の端子までの遅延時間に基づく条件であることを特徴とする請求項２又は３に記載の経路探索方法。
【請求項５】
それぞれデータ信号とクロック信号が接続されたデータ端子とクロック端子を備えた回路素子であるセルを有する電子回路の動作検証を行うタイミング解析方法において、
予め設定された第１の条件に基づいて、前記電子回路上でデータ信号が伝搬するデータ信号経路を探索して、前記タイミング解析に用いるデータ信号経路を抽出するステップと、
予め設定された第２の条件に基づいて、前記電子回路上でクロック信号が伝搬するクロック信号経路のなかで、同一のクロック端子を通過することにより前記同一のクロック端子に合流する２つ以上のクロック信号経路のうちいずれかのクロック信号経路を選択することにより、前記タイミング解析に用いるクロック信号経路を抽出するステップと、
前記抽出したデータ信号経路とクロック信号経路のそれぞれの組み合わせ毎に前記タイミング解析を行うステップと、
をコンピュータに実行させることを特徴とするタイミング解析方法。
【請求項６】
それぞれデータ信号とクロック信号が接続されたデータ端子とクロック端子を備えた回路素子であるセルを有する電子回路の動作波形の検証を行う波形解析方法において、
予め設定された条件に基づいて、前記電子回路上でクロック信号が伝搬するクロック信号経路のなかで合流する端子が同じ２つ以上のクロック信号経路を合成するステップと、
前記クロック端子毎に、前記クロック信号の波形解析を行う解析用情報の端子毎の作成を行い、当該クロック信号が伝搬するクロック信号経路を探索して前記波形解析に用いるクロック信号経路を抽出するステップと、
前記解析用情報を用いて、当該クロック信号が伝搬するクロック信号経路を伝搬するクロック信号のパルス幅を算出するステップと、
をコンピュータに実行させることを特徴とする波形解析方法。
【請求項７】
回路素子であるセルを有する電子回路上でデータ信号が伝搬するデータ信号経路から、予め設定された第１の条件に基づいて抽出されたデータ信号経路における始点の経路データを取得する始点経路データ取得手段と、
予め設定された第２の条件に基づいて、前記電子回路上でクロック信号が伝搬するクロック信号経路のなかで、同一のクロック端子を通過することにより前記同一のクロック端子に合流する２つ以上のクロック信号経路のうちいずれかのクロック信号経路を選択することにより抽出されたクロック信号経路における終点の経路データを取得する終点経路データ取得手段と、
前記始点経路データ取得手段及び終点経路データ取得手段がそれぞれ取得した前記始点及び終点の経路データを用いて、動作検証用のタイミング解析を行うシミュレーション手段と、
を有することを特徴とする電子回路シミュレーション装置。
【請求項８】
信号が接続された端子を備えた回路素子であるセルを有する電子回路において、それぞれ共通の始点の端子から共通の終点の端子に至る複数の前記セルを通過する信号経路を探索するための経路探索プログラムであって、
前記共通の始点の端子から前記共通の終点の端子に至る複数の信号経路のなかで他の信号経路と区別すべき信号経路を探索する所定の条件を、信号経路を識別する経路識別子とともに、前記端子毎に設定するステップと、
前記所定の条件に基づいて、前記複数の信号経路毎に前記共通の始点の端子から前記共通の終点の端子に至る信号経路の探索を行うステップと、
をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項９】
信号が接続された端子を備えた回路素子であるセルが組み合わせて設計された電子回路において、それぞれ共通の始点の端子から共通の終点の端子に至る複数の前記セルを通過する信号経路を探索するための経路探索プログラムであって、
前記共通の始点の端子から前記共通の終点の端子に至る複数の信号経路のうち、信号経路が同一の端子を通過することにより前記同一の端子に合流する信号経路が２つ以上有る場合には、前記２つ以上の信号経路のうちいずれかの信号経路を選択する第１の選択条件を前記同一の端子に設定するステップと、
前記同一の端子について、前記第１の選択条件を満たす信号経路が２つ以上有る場合には、第２の選択条件を用いて１つだけの信号経路を選択し、前記共通の始点の端子から前記共通の終点の端子に至る信号経路の探索を行うステップと、
をコンピュータに実行させることを特徴とする経路探索プログラム。
【請求項１０】
前記第１の選択条件は、
前記同一の端子のセルと、前記同一の端子のセルの直前のセルに供給されるクロック信号の供給源と位相が同一であり、かつ、
前記同一の端子と、前記同一の端子のセルの直前のセルが有する端子に設定された経路識別子が同一であることを特徴とする請求項９記載の経路探索プログラム。
【請求項１１】
前記第２の選択条件は、
各信号経路の遅延時間を算出しながら経路探索を行っている場合には、所定の始点の端子から前記同一の端子までの遅延時間に基づく条件であることを特徴とする請求項９又は１０に記載の経路探索プログラム。
【請求項１２】
それぞれデータ信号とクロック信号が接続されたデータ端子とクロック端子を備えた回路素子であるセルを有する電子回路の動作検証を行うタイミング解析プログラムにおいて、
予め設定された第１の条件に基づいて、前記電子回路上でデータ信号が伝搬するデータ信号経路を探索して、前記タイミング解析に用いるデータ信号経路を抽出するステップと、
予め設定された第２の条件に基づいて、前記電子回路上でクロック信号が伝搬するクロック経路のなかで、同一のクロック端子を通過することにより前記同一のクロック端子に合流する２つ以上のクロック信号経路のうちいずれかのクロック信号経路を選択することにより、前記タイミング解析に用いるクロック信号経路を抽出するステップと、
前記抽出したデータ信号経路とクロック信号経路のそれぞれの組み合わせ毎に前記タイミング解析を行うステップと、
をコンピュータに実行させることを特徴とするタイミング解析プログラム。
【請求項１３】
それぞれデータ信号とクロック信号が接続されたデータ端子とクロック端子を備えた回路素子であるセルを有する電子回路の動作波形の検証を行う波形解析プログラムにおいて、
予め設定された条件に基づいて、前記電子回路上でクロック信号が伝搬するクロック信号経路のなかで合流する端子が同じ２つ以上のクロック信号経路を合成するステップと、
前記クロック端子毎に、前記クロック信号の波形解析を行う解析用情報の端子毎の作成を行い、当該クロック信号が伝搬するクロック信号経路を探索して前記波形解析に用いるクロック信号経路を抽出するステップと、
前記解析用情報を用いて、当該クロック信号が伝搬するクロック信号経路を伝搬するクロック信号のパルス幅を算出するステップと、
をコンピュータに実行させることを特徴とする波形解析プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、予め登録されセルを組み合わせて設計された電子回路の動作検証用のシミュレーション（タイミング解析や波形解析など）を行うための技術に関する。
【０００２】
【従来の技術】
最近では、プリント配線板（ＰＣＢ）や集積回路などの電子回路はより短期間に、より低コストに開発することが非常に強く求められている。このようなことから、その開発を支援するＣＡＤ（Computer Aided Design ）技術の重要性も非常に増しつつある。
【０００３】
エレクトロニクス系のＣＡＤでは、深い知識が無くとも設計が行えるように、標準化、モデル化が重視されている。電子回路の機能的、或いは論理的な単位となる素子、或いは部品などは、例えばＮＡＮＤやＮＯＲなどの基本ゲートやフリップフロップ（以降、ＦＦと略記する）、シフト・レジスタなどから、ＣＰＵやメモリなどは、基本素子（セル）としてライブラリに登録させている。このことから、論理設計は、基本的に、ライブラリに登録されたセルのなかで必要なセルを選択し、その選択したセル同士を接続させることで行われる。セル同士の接続は、それらがそれぞれ持つピンとピンを結ぶことで行われる。
【０００４】
論理設計の結果はネットリスト（論理回路データ）に変換される。そのネットリストはライブラリに登録されたセルの相互接続として記述されている。そのネットリストを利用して、レイアウト設計やシミュレーションが行われる。
【０００５】
そのシミュレーションで行われる解析として、信号が伝搬していく時間差によって不具合（誤動作など）が生じるか否か確認するためのタイミング解析がある。そのタイミング解析としては、ＦＦなどにおいて、データを取り込むタイミングが遅すぎるか否か確認するセットアップタイムチェックや、そのデータを取り込むタイミングが早すぎるか否か確認するホールドタイムチェックなどが行われる。それ以外には、伝搬してきたクロック信号の波形が動作を保証する形を保っているか否か確認するパルス幅チェックなどが波形解析として行われる。
【０００６】
図３７は、上記タイミング解析を説明するための図である。同図（ａ）はその対象となる回路例、同図（ｂ）はその動作を示すタイミングチャートである。ここでは、各セル毎に異なった遅延時間を持たせる割り当て遅延モデルが採用されているとの前提で説明する。周知のように、それ以外には、遅延時間に幅を持たせた不確定遅延モデル（最大−最小遅延モデル）がある。
【０００７】
図３７（ａ）に示す回路において、ＦＦ１、２はセルに対応し、それらが有するＣＫ、ＤＴ、及びＱ端子はそれぞれセルが有するピンに対応する。丸で示すピン３は、クロック信号を入力する、或いは生成したクロック信号を出力するピン（クロックソース）である。ＦＦ１のＣＫ端子と接続された線が、クロックソース３とＦＦ２のＣＫ端子を結ぶ線と合流する点もピンとして扱われる。Ｔcsはクロックソース３から出力されたクロック信号がＦＦ１のＣＫ端子に入力するのに要する遅延時間、Ｔctはクロックソース３から出力されたクロック信号がＦＦ２のＣＫ端子に入力するのに要する遅延時間、Ｔd はＦＦ１のＣＫ端子に入力したクロック信号の立ち上がり（ライズ（Ｒｉｚｅ）エッジ）から、その立ち上がりによって変化するＦＦ１のＱ端子の出力信号（データ信号）がＦＦ２のＤＴ端子に入力するのに要する遅延時間である。
【０００８】
図３７（ｂ）において、“ＣＬＯＣＫ”では上記クロックソース３から出力されるクロック信号を示している。“ＦＦ１，ＣＫ”ではＦＦ１のＣＫ端子に入力されるクロック信号、“ＦＦ２，ＤＴ”ではＦＦ２のＤＴ端子に入力されるデータ信号、“ＦＦ２，ＣＫ”ではＦＦ２のＣＫ端子に入力されるクロック信号をそれぞれ示している。
【０００９】
クロック信号によって動作するＦＦ１、２間のデータ信号のやりとりは、クロック信号に同期させる必要がある。データ信号のやりとりができない、或いはやりとりするクロック信号のサイクルがずれるといったことは回避させなければならない。そのためには、ＦＦ２では、ＣＫ端子に入力するクロック信号が立ち上がるタイミングに対し、ＤＴ端子に入力するデータ信号が変化するタイミングが早すぎることなく、且つ遅すぎることもないようにしなければならない。それらの差が許容範囲内でなければならない。セットアップタイムチェック（オーバーディレイチェック）は、そのデータ信号が変化するタイミングが遅すぎるか否か確認するために行われ、他方のホールドタイムチェック（レーシングチェック）は、そのデータ信号が変化するタイミングが早すぎるか否か確認するために行われる。
【００１０】
図３７（ｂ）中のＴsetup 、及びＴholdは、それぞれ、ある程度の余裕を持ってその確認を行うために設定された時間である。図３７（ｂ）中の式は、それぞれ、Ｔcs＋Ｔd −Ｔct＋Ｔsetup ≦τ（τはクロック信号の周期を基に、セットアップタイムチェック用に設定された時間）はセットアップタイムチェックの結果がＯＫとなる関係を示し、Ｔcs＋Ｔd −Ｔct＋Ｔhold≧０はホールドタイムチェックの結果がＯＫとなる関係を示している。図３７（ｂ）中のＴs はＦＦ１、２間におけるクロック信号のスキュー（時間のずれ）を示している。
【００１１】
【発明が解決しようとする課題】
上記タイミング解析に用いる経路の探索は、解析の内容や伝搬する信号の種類別に行われる。データ信号が伝搬する経路（データ経路）では、従来、始点のピンから終点のピンに至る信号の経路のなかから、信号の伝搬に要する遅延時間が最大（或いは最小）となる経路を単に抽出するといったように、経路全体での遅延時間に単に注目して経路の探索を行っていた。しかし、ライブラリに登録されたセルのなかには、状況に応じて信号を出力するもの（例えばセレクタ）も存在する。このため、そのような探索では、場合によってはタイミング解析に用いるべきでない経路を抽出してしまうという問題点があった。それにより、タイミング解析は必ずしも高精度に行えなかった。
【００１２】
一方、クロック信号が伝搬する経路（クロック経路）の検索についても、従来はデータ信号が伝搬する経路の探索と同様に行っていた。しかし、セットアップタイムチェックやホールドタイムチェックでは、例えばクロック信号を分周する分周器が回路に用いられることもあって、遅延時間の差が最大（或いは最小）となるクロック経路とデータ経路の組み合わせが必ずしもタイミング的に最悪とはならない。このため、チェック結果が最悪となるクロック経路を必ずしも抽出することができないという問題点があった。それにより、タイミング解析の精度の低下を招いていた。これは波形解析においても同様である。
【００１３】
このようなことから、タイミング解析などを高精度に行うには、クロック経路は全て考慮する必要があると云える。しかし、現在の回路設計では、高集積化のために、クロック信号が分岐するピンやそれが合流するピンが数多く存在するのが普通となっている。そのような分岐合流によって、当然のことながら、経路は指数関数的に増大してその数は膨大となる。このため、全てのクロック経路を対象にしてタイミング解析などを行うことは、処理のために必要なメモリ容量や処理時間などの面から現実的でないと云える。従って、クロック経路を全て考慮する場合には、処理のために必要なメモリ容量や処理時間の増大を抑える必要があると考えられる。
【００１４】
本発明は、設計された電子回路の動作検証用のシミュレーションを常に高精度に行うための技術を提供することを目的とする。
また、本発明は、処理のために必要なメモリ容量や処理時間の増大を抑えつつ、設計された電子回路の動作検証用のシミュレーションを常に高精度に行うための技術を提供することを目的とする。
【００１５】
【課題を解決するための手段】
図１は、本発明による電子回路シミュレーション装置の原理構成図である。その図１を参照して、本発明による電子回路シミュレーション装置１１の構成、及びその動作を説明する。
【００１６】
経路探索装置１２は、設計された電子回路を対象に、信号が伝搬する経路の探索を行い、その動作検証用のシミュレーションを行うために用いる経路を抽出する。シミュレーション手段１３は、そのシミュレーションとして、タイミング解析や波形解析などを行い、その結果を出力する。
【００１７】
上記経路探索装置１２は、クロック信号が伝搬するクロック経路を対象にタイミング解析用の探索を行うクロック経路探索手段１４、データ信号が伝搬するデータ経路を対象にタイミング解析用の探索を行うデータ経路探索手段１５、及びクロック経路を対象に波形解析（パルス幅チェック）用の探索を行うパルス幅チェック用経路探索手段１６を具備する。それにより、各経路探索手段１４〜１６による探索結果をタイミング解析手段１３に送る。なお、経路探索装置１２は、各経路探索手段１４〜１６の全てを必ずしも具備する必要はない。
【００１８】
図２は、本発明のプログラムの原理構成図である。上記経路探索装置１２が実行するプログラム２１の構成、及びそのプログラム２１の実行時に参照される各種データを表したものである。
【００１９】
そのプログラム２１は、クロック経路探索手段１４を実現させるためのクロック経路探索ルーチン２２、データ経路探索手段１５を実現させるためのデータ経路探索ルーチン２３、及びパルス幅チェック用経路探索手段１６を実現させるためのパルス幅チェック用経路探索ルーチン２４を具備している。それにより、各経路探索手段１４〜１６は、ロードされてハードディスク装置に搭載のハードディスク等に格納されているプログラム２１を経路探索装置１２が実行することで実現される。
【００２０】
プログラム２１は、ライブラリＤＢ１、ネットリストＤＢ２、配線長データベースＤＢ３を参照する。ライブラリＤＢ１は、論理設計上の基本素子であるセルを登録したデータベースであり、各セルの動作や特性（遅延時間を含む）などを示す各種データも格納されている。ネットリストＤＢ２には、ライブラリＤＢ１に登録されたセルの相互接続関係を示すデータが格納されている。配線長データバースＤＢ３にはセル間を結ぶ配線の長さなどのデータが格納されている。
【００２１】
設計された電子回路は、それらデータベースＤＢ１〜３によって表される。このことから、各ルーチン２２〜２４は、それらによって表される電子回路を対象に経路探索を行うようになっている。
【００２２】
各ルーチン２２〜２４は、それぞれ、１つ以上の条件から構成された条件群２５〜２７を参照して経路探索を行う。各条件群２５〜２７を構成する条件は、それぞれ、対象とする経路の種類、及びその経路を探索する目的などを考慮して設定された、合流するピンが同じ複数の経路を１つにまとめるうえでその複数の経路間で成立しているべき関係、或いは状況を定義したものである。その条件は、プログラム２１内に予め設定（ここでは電子回路に応じた自動設定を含む）しておいても良いが、他のプログラムから与えられるものであっても良い。ユーザが適宜、設定できるようにしても良い。
【００２３】
上記条件群２６には、例えば始点のピンから終点のピンに至るデータ経路のなかで他と区別すべき経路が満たしている１つの条件、或いは複数の条件の組み合わせが設定されている。それにより、データ経路探索ルーチン２３による経路探索は、始点のピンから１つずつ先のピンに進めながら、各ピン毎に、直前に位置しているピンを表すデータ、及び経路識別用の経路識別コードを少なくとも作成していくことで行うようになっている。その経路識別コードの値は、少なくとも、条件を満たしたことが判明した後には既存でない値とさせることで、条件群２６を構成する条件のなかで満たしている条件の種類、その数、或いはその組み合わせなどによる経路の区別を可能とさせている。
【００２４】
データ経路探索ルーチン２３は、そのような経路探索をデータ経路探索手段１５に行わせる。それにより、全ての経路を考慮しつつ、満たす条件によって区別される経路の種類別に経路を抽出することが可能となる。言い換えれば異なる条件を満たす経路毎に区別して、経路を抽出することが可能となる。その結果、シミュレーションのために抽出すべき経路を確実に抽出することが可能となる。
【００２５】
一方、上記条件群２５、及び２７には、共に、例えば合流するピンが同じ２つ以上の経路が存在していた場合に、その２つ以上の経路を１つにまとめる（合成する）うえでそれらの間で満たすべき１つの条件、或いは複数の条件の組み合わせが設定されている。それにより、各経路探索ルーチン２２、及び２４による経路探索は、始点のピンから１つずつ先のピンに進めながら、各ピン毎に、１つにまとめるべき条件を満たす２つ以上の経路が合流するか否か確認し、そのような条件を満たす２つ以上の経路が合流していた場合に、それらのうちの１つを選択して残しつつ（或いはそれらを合成しつつ）行うようになっている。
【００２６】
各経路探索ルーチン２２、及び２４は、共に、そのような経路探索を各経路探索手段１４、及び１６にそれぞれ行わせる。それにより、全ての経路を考慮しつつ、シミュレーションで考慮する必要のない経路を経路探索の段階で排除させている。
【００２７】
シミュレーション手段１３は、各経路探索手段１４〜１６による経路探索の結果を用いて、タイミング解析や波形解析などのためのシミュレーションを行う。タイミング解析は経路探索手段１４、１５による経路探索の結果を用いて行い、波形解析（パルス幅チェック）は経路探索手段１６による経路探索の結果を用いて行う。電子回路シミュレーション装置１１は、それらの結果を表示装置やプリンタ、或いはＬＡＮ等で結ばれた外部装置などに出力する。
【００２８】
上述した各経路探索手段１４〜１６による経路探索では、何れも、シミュレーションで考慮する必要が考えられる経路を排除することなく、抽出する経路の数を最小限に抑えられる。その結果、それら経路探索結果のうちの少なくとも１つを用いて行うシミュレーションは常に高精度に行えるだけでなく、その処理のために要するメモリ容量の低減や処理時間の短縮も実現されることになる。
【００２９】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態につき詳細に説明する。
図３は、本実施の形態による電子回路シミュレーション装置（以降、シミュレーション装置と略記する）を搭載したＣＡＤ装置の構成図である。
【００３０】
そのＣＡＤ装置は、例えばコンピュータにＣＡＤ装置として動作させるためのプログラムをインストールすることで実現させたものである。そのＣＡＤ装置は、図３に示すように、ＣＰＵ３１、メモリ３２、例えばマウスやキーボードである入力装置３３、例えば表示装置である出力装置３４、例えばハードディスク装置である外部記憶装置３５、可搬記録媒体ＳＭとして、例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、光磁気ディスク、或いはフロッピーディスクを駆動する媒体駆動装置３６、ＬＡＮ等のネットワークと信号のやりとりを行うネットワーク接続装置３７が、バス３８によって相互に接続されて構成されている。
【００３１】
上記外部記憶装置３５に搭載された記憶媒体（例えばハードディスク）には上記プログラムが記憶されている。それ以外には、電子回路の設計に用いるライブラリ（データベース）が記憶されている。レイアウト設計後には、ライブラリに登録されたセルの相互接続を記述したネットリストの他に、ピン間の配線長を格納した配線長データベースが記憶される。ピン間の経路については経路と区別するためにパスと呼ぶことにする。
【００３２】
図４は、セルとピンの関係を説明する図である。その図４において、丸はピンを示し、矢印が付いた線はピン間のパスを示している。セルとして、３つのインバータと、２つのフリップフロップ（ＦＦ）が示されている。以降、１つ以上のセルを組み合わせて構成された回路についてはモジュールと呼ぶことにする。
【００３３】
図４に示すように、セル内にもパスは存在し、ピンはセル以外にも存在する。セル以外に存在しているピンは、モジュールへの信号の入力用、或いはモジュールからの信号の出力用に指定されたものである。
【００３４】
パスを流れる信号は、素子を動作させるためのクロック信号と、その素子に与えられるデータ信号と、に区別することができる。このことから、クロック信号が流れるパスはクロックパス、データ信号が伝搬するパスはデータパスとそれぞれ呼ぶことにする。２つのＦＦで構成された回路を例にとって、その回路でクロックパス、及びデータパスにそれぞれ対応している部分を図５に示す。
【００３５】
現在、設計される回路では、経路が複雑に分岐合流を繰り返しているのが普通となっている。このため、全ての経路を抽出してタイミング解析や波形解析を行うことは処理時間やメモリ容量などの面から現実的でない。本実施の形態では、以下のような経路探索を行い、全ての経路のなかで考慮する必要のない経路を経路探索の段階で排除することにより、高い精度を維持させつつ、処理時間の短縮や処理に要するメモリ容量の低減を実現させている。
【００３６】
本実施の形態では、ネットリストにセル相互の接続関係が記述された電子回路上で３種類の経路探索を行うようになっている。以降、それら経路探索の方法について、図６〜図１９に示す説明図を参照しながら詳細に説明する。
【００３７】
先ず、データ信号が伝搬する経路（データ経路）を対象にした経路探索について説明する。
図６は、電子回路上でデータパスによって接続されたピン間の接続関係を示すグラフである。理解を容易とするために、図６に示すグラフを対象に経路探索（データパスのトレース）を行う場合を例にとって、その経路探索方法について詳細に説明する。
【００３８】
図６において、ａ〜ｊが記入された丸はピンを表し、その間の線分はデータパスを表している。信号は、左から右に向かって流れることを前提としている。従って、始点とするピンはピンａであり、そのピンａから至る終点となるピンはピンｊである。
【００３９】
データパスからなる経路（データ経路）では、その経路上に、連動して動作しない素子（例えばセレクタ）などが存在していることがある。そのような素子が存在する経路は他の経路と区別する必要がある。このことから、経路探索を開始する前に、他と区別すべき経路の満たす経路条件を設定するようにしている。その設定は、ユーザが行っても良いが、自動的に行うようにしても良い。ここでは、便宜的に、以下の２つが設定されていることにする。
【００４０】
経路条件１）  ピンｂ、ピンｇの順に通る経路
経路条件２）  ピンｄを通る経路
経路条件中で指定されたピンには、例えばその旨を示すフラグを立てる。経路条件１、及び２が設定された場合には、ピンｂ、ｇ、及びｄにそれぞれフラグが立てられることになる。図７では、それらピンｂ、ｇ、及びｄは太線で示してある。
【００４１】
経路探索は、始点であるピンａから、データパスを１つずつ、先に進めていくことで行う。データパスを１つ進めた先に他のピンが存在していれば、探索上の進行を管理するために、イベントを新たに作成し、そのイベントの内容を示す情報（イベント情報）をそのピンに対応付けて保存する。始点であるピンａには、その前に他のピンが存在しないことから、経路探索を開始する時点でイベントを作成しその情報を保存している。
【００４２】
図６に示すグラフには、信号が分岐するピンとしてピンａ、ｃ〜ｅが存在し、信号が合流するピンとしてピンｇ〜ｊが存在する。これは、複数の経路が同じピンを通るということを意味する。このようなことから、同じピンを通る経路でもその区別が行えるようにするために、イベントを作成している。
【００４３】
図８は、図６に示すグラフにおいて、データパスを１つ先に進めたときに作成しているイベントを説明する図である。図８（ａ）において、吹き出し内に表記されたＡ〜Ｃは、それぞれ、それが付加されたピンａ〜ｃに作成したイベントを表している。以降は、吹き出し内に表記された記号はそのイベント自体を表すイベント名と呼ぶことにする。
【００４４】
図８（ａ）に示すように、ピンａからデータパスを１つ先に進めたことにより、ピンａ〜ｃにイベントを作成している。そのイベント情報としては、図８（ｂ）に示すように、それの前段に発生したイベントを示すデータ（ここではイベント名）、及び経路識別コードをイベント毎に保存するようにしている。前段に発生したイベント名は、経路を逆に遡ることができるようにするために保存している。経路識別コードは、ここでは経路が満たす経路条件で区別して経路を抽出するために保存している。その経路識別コードの値は、フラグを持つピンの１つ先のピンに進めた際に、既存でない値に変更する。
【００４５】
ピンａに対応付けられたイベントＡでは、前段のイベントが存在していないことから、前段のイベントとしては、その旨を示すデータが保存されている。経路識別コードとしては、予め定めた初期値（ここでは０）が保存されている。ピンｂ、及びｃにそれぞれ対応付けられたイベントＢ、及びＣでは、前段のイベント名として、Ａが保存されている。経路識別コードとしては、この時点ではフラグを持つピンの先にまで進んでいないために、イベントＡと同じ０が保存されている。
【００４６】
その状態から更にデータパスを１つ先に進めると、図９に示すように、ピンｄ、ｅ、及びｆでイベントを作成する。ピンｄは、経路条件２で指定されたピンｂの先に位置していることから、そのピンｄに対応付けられたイベントＤでは、経路識別コードとして、それまでに存在していない値の１を保存している。他の新たに作成したイベントＥ、及びＦの経路識別コードの値は０のままである。
【００４７】
図９に示す状態から更にデータパスを１つ先に進めると、図１０に示すように、ピンｇ、ｈでイベントを作成する。ピンｊは終点となるピンであるため、ここではイベントを作成していない。
【００４８】
ピンｇは、ピンｄ、ｅからデータパスで１つ先に位置している。このため、ピンｇでは、２つのイベントＧ１、Ｇ２を作成している。そのピンｇの直前に位置するピンｄは、フラグを持つ経路条件１で指定されたピンであり、そこではイベントＤが作成されている。このため、図１０（ｂ）に示すように、イベントＤを前段のイベントとするイベントＧ１では、経路識別コードの値はそれまでにない値の２となっている。
【００４９】
ピンｈは、ピンｅ、ｆからデータパスで１つ先に位置している。しかし、それらピンｅ、ｆにはフラグは付加されておらず、それらで作成されたイベントＥ、Ｆの経路識別コードは共に０である。このため、ピンｈでは、それらのうちから一つを選択することで、１つのイベントＨだけを作成している。ここでは、前端のイベントとしてイベントＦを選択している。イベントＧ２、Ｈでは経路識別コードは０のままである。
【００５０】
図１０に示す状態からデータパスを最後まで、即ち終点であるピンｊまで進めると、図１１に示すように、ピンｉ、ｊでイベントを作成することになる
ピンｉは、ピンｇ、ｈからデータパスで１つ先に位置している。ピンｇは、２つのイベントＧ１、Ｇ２が作成されている、フラグを持つピンである。ピンｈで作成したのはイベントＨの１つである。これらのことから、ピンｉでは、３つのイベントＩ１〜３を作成している。ピンｇはフラグを持つピンであることを示すために、前段のイベントをイベントＧ１とするイベントＩ１では、経路識別コートの値として、この時点ではそれまでにない値の３を保存させている。前段のイベントをイベントＧ２とするイベントＩ２では、経路識別コートの値として、この時点ではそれまでにない値の４を保存させている。
【００５１】
終点であるピンｊは、ピンｄ、ｉからデータパスで１つ先に位置している。ピンｄは、フラグを持つ、１つのイベントＤが作成されたピンである。ピンｉには、３つのイベントＩ１〜３が作成されている。これらのことから、ピンｊでは、４つのイベントＪ１〜４を作成している。前段のイベントをイベントＤとするイベントＪ１では、経路識別コードの値として、それまでにない値の５を保存させている。それ以外のイベントＪ２〜４では、経路識別コードの値は前段のイベントのそれと同じである。
【００５２】
ピンｊでイベントを作成することで、イベントの作成は終了する。その後は、そのピンｊで作成したイベント毎に、経路を特定する。イベントＪ１〜４から特定される経路は以下のようになる。
【００５３】
Ｊ１：ａ→ｂ→ｄ→ｊ（経路１）
Ｊ２：ａ→ｂ→ｄ→ｇ→ｉ→ｊ（経路２）
Ｊ３：ａ→ｃ→ｅ→ｇ→ｉ→ｊ（経路３）
Ｊ４：ａ→ｃ→ｆ→ｈ→ｉ→ｊ（経路４）
上記経路条件１、２を設定して、図６に示すグラフを対象に経路探索を行った場合、４つの経路が抽出される。しかし、図６に示すグラフに存在する経路は５つである。このことから明らかなように、経路条件で指定されたピンにフラグを持たせ、経路識別コードを使用してイベントを作成していくことにより、抽出する経路を減らせることができる。その経路は、満たす経路条件の違いによって区別して減らしているため、探索によって抽出すべき経路を抽出しないといったことを確実に回避することができる。このことから、タイミング解析の精度もより向上することになる。
【００５４】
イベントＪ１〜４から特定される経路１〜４については、予め設定された経路条件１、２のどれを満たしているかを調べる。それにより、経路１は経路条件２、経路２は経路条件１、２の両方を満たし、経路３、４は経路条件１、２の何れも満たしていないことが判明する。このため、経路３、４はそのうちの一方だけを代表させる。そのようにして、ピンａからピンｊに至る経路のなかから、満たしている経路条件が互いに異なる３つの経路を抽出する。
【００５５】
本実施の形態では、上記経路３、４のなかで代表させる経路の選択や、信号が合流するピンでのイベントの選択は、予め設定した選択規則に従って行っている。その選択規則は採用した遅延モデルによって異なるが、各パス毎に異なった遅延時間を割り当てた割り当て遅延モデル、及び各セルの遅延時間に幅を持たせた不確定遅延モデル（最大−最小遅延モデル）では、経路の遅延時間が最大、或いは最小の経路を選択するようにしている。
【００５６】
そのような選択を行うために、各イベントには、そのイベントが発生するまでの遅延時間を持たせている。イベントに持たせる遅延時間は、例えばデータパスを１つ先に進める度に、そのデータパスの遅延時間を直前のイベントが持つ遅延時間に加算して得られるそれまでの全遅延時間である。データパスを含むパスの遅延時間は、例えばライブラリ、或いは配線長データベースを参照することで取得することができる。
【００５７】
なお、本実施の形態では、経路識別コードの値は、フラグを持つピンの１つ先に位置するピンでそれまでに存在しない値に変更しているが、経路条件を満たしたか否かに応じて、経路識別コードの値を変更するようにしても良い。何れの方法で経路識別コードの値を変更しても、経路条件を満たした経路の経路識別コードの値は他の経路と異なった値とすることができる。
【００５８】
次にクロック信号が伝搬する経路（クロック経路）を対象にした経路探索について説明する。
例えばデータ信号の送り側のＦＦ、及びそれを受ける側のＦＦに、それぞれ同じクロックソースからクロック信号が供給される場合、クロックソースから出力されたクロック信号が送り側のＦＦに届くのに要する遅延時間と、それが受け側のＦＦに届くのに要する遅延時間と、の差が動作に大きく影響する。クロック信号が伝搬する経路を対象にした経路探索では、このことに着目している。先ず、その方法の原理について、図１２〜図１４に示す説明図を参照して詳細に説明する。
【００５９】
図１２に示すピンＳはクロックソースであり、ピンＴは送り側のＦＦのＣＫ端子（クロック信号を入力する端子）に対応するピンである。クロックソースであるピンＳからピンＴに至る経路は、ピンＡで分岐し、ピンＢで合流している。図１２中のａ、ｂは、ピンＡとピンＢを結ぶクロックパスである。
【００６０】
クロックパスａ、ｂにより、ピンＳからピンＴに至る経路は２つ存在していることになる。その２つの経路間の遅延時間の差は、クロックパスａ、ｂ間における遅延時間の差と一致する。
【００６１】
今、クロックパスａの遅延時間のほうがクロックパスｂのそれよりも大きいと仮定して、ピンＳからピンＴに至る経路のどこかに、クロック信号を受け側のＦＦに分岐させるピンが存在していることを考える。タイミング解析としては、セットアップタイムチェックに着目する。そのピンについては、ここでは分岐ピンと呼ぶことにする。クロックパスａ、ｂの遅延時間については、それぞれ遅延（ａ）、遅延（ｂ）と表記する。
【００６２】
スキュー（図３７参照）は、同じクロック信号が送り側のＦＦ、受け側のＦＦに届くのに要する遅延時間の差である。セットアップタイムチェックでは、そのスキューが大きいほど厳しくなる。
【００６３】
上記分岐ピンがピンＳとピンＡ間にある場合、遅延（ａ）＞遅延（ｂ）より、送り側のＦＦに至る経路はクロックパスａを通る経路のほうがスキューが大きくなる。その分岐ピンがピンＢとピンＴ間にある場合には、送り側のＦＦに至る経路はクロックパスａ、ｂの何れを通る経路であってもスキューは変わらない。これらのことから明らかなように、クロック信号が伝搬するクロックパスが異なる区間（ここではピンＡとピンＢ間）外に受け側のＦＦへの分岐ピンがあれば、クロックソース（ここではピンＳ）から送り側のＦＦに至る経路は遅延時間が最大のものであったときにスキューは最大（最悪）となる。
【００６４】
次に、クロック信号が伝搬するクロックパスが異なる区間内に分岐ピンがある場合について考える。ここでは、図１３に示すように、受け側のＦＦと接続されているピンＣがピンＡとピンＢ間に存在していることとする。図１３中のａ〜ｃは、それぞれ、ピンＡとピンＢを結ぶクロックパス、ピンＡとピンＣを結ぶクロックパス、ピンＣとピンＢを結ぶクロックパスである。各クロックパスａ〜ｃの遅延時間は、その符号を用いて表すことにする。
【００６５】
クロック信号が送り側のＦＦに伝搬していく経路は、ここでもピンＡとピンＢ間で２つ存在する。分岐ピンとしては、ピンＡ、及びＣの２つが考えられる。ピンＡを分岐ピンとしたときのスキューをｓｋｅｗ（ａ）、ピンＣを分岐ピンとしたときのスキューをｓｋｅｗ（ｃ）と表記する。
【００６６】
ピンＡ−Ｂの経路の遅延時間がピンＡ−Ｃ−Ｂの経路のそれより大きいということは、ａ＞ｂ＋ｃの関係があることを意味する。このとき、ｓｋｅｗ（Ａ）、ｓｋｅｗ（Ｃ）は、それぞれ
ｓｋｅｗ（Ａ）＝ａ−ｂ＋ｋ（ｋは経路によらない定数）    ・・・（１）
ｓｋｅｗ（Ｃ）＝ｃ＋ｋ
となる。従って、ａ＞ｂ＋ｃより、ａ−ｂ＞ｃの関係があることから、ｓｋｅｗ（Ａ）＞ｓｋｅｗ（Ｃ）となる。
【００６７】
一方、ピンＡ−Ｂの経路での遅延時間がピンＡ−Ｃ−Ｂの経路のそれより小さい場合には、ａ＜ｂ＋ｃの関係があることから、上記と同様にして、ｓｋｅｗ（Ａ）＜ｓｋｅｗ（Ｃ）の関係が導かれる。
【００６８】
これらのことから明らかなように、遅延時間が大きい経路上に分岐ピンが存在していたときにスキューは大きくなる。よって、送り側のＦＦへの経路については、遅延時間が最大の経路のみを考えれば良いことになる。同様にして受け側のＦＦへの経路については、遅延時間が最小の経路を考えれば良いことになる。タイミング解析としてホールドタイムチェックに着目しているときには、逆に、送り側のＦＦへの経路については遅延時間が最小の経路、受け側のＦＦへの経路については遅延時間が最大の経路をそれぞれ考えれば良いことになる。
【００６９】
例えば図１４に示すように、受け側のＦＦへの経路が複数、存在している場合がある。その図１４において、ａ〜ｄは、それぞれ、ピン間のクロックパスとその遅延時間を表している。
【００７０】
図１４に示すような場合にも、ピンＣ、Ｄから受け側のＦＦに至る経路を別々に考えれば、セットアップタイムチェックでは、クロックソースであるピンＳから送り側のＦＦに至る経路のなかで遅延時間が最大の経路上に分岐ピンが存在しているときにスキューは最悪のものとなる。
【００７１】
送り側のＦＦに至る経路のうち遅延時間が最大のものに複数の分岐ピンが存在している場合にも、各分岐ピンから受け側のＦＦに至る経路を別々に考えれば、受け側のＦＦに至る経路のなかで遅延時間が最小のもののときにスキューが最悪となる。これらのことから、スキューが最悪となるのは、結局、送り側のＦＦに至る経路のながで遅延時間が最大となっている経路上に、受け側のＦＦに至る経路のなかで遅延時間が最小のものの分岐ピンが存在しているケースであることが分かる。ホールドタイムチェックを考慮しているのであれば、その逆である。
【００７２】
タイミング解析では、基本的に、上述したような経路の組み合わせのときに結果が最悪となる。このことから、終点となるピンが同じ経路が複数、存在しているときには、複数の経路のなかでタイミング解析による結果が最悪となる経路を代表させている。全ての経路を考慮しつつ、１つにまとめられる複数の経路は一つにまとめている。それにより、高い精度を維持させつつ、タイミング解析で考慮すべき経路の数の低減を図っている。本実施の形態では、精度をより向上させるために、以下のようなことも考慮して経路の数の低減を図っている。以下、そのことについて具体的に説明する。
【００７３】
不確定遅延モデル（最大−最小遅延モデル）では、周知のように、パスの遅延時間に幅を持たせている。遅延時間の最大、最小に違いがある場合（実際には殆どである）、式（１）は以下のようになる。セットアップタイムチェックを想定して説明する。
【００７４】
ｓｋｅｗ（Ａ）＝ａ−ｂ（ｍｉｎ）＋ｋ
ここでｂ（ｍｉｎ）は、クロックパスｂの最小の遅延時間であり、最大の遅延時間は式（１）のままとしている。以降も同様に、最小の遅延時間には“（ｍｉｎ）”を付加し、最大の遅延時間にはシンボルを付加しないことにする。
【００７５】
図１３において、ピンＡ−Ｂを通る経路での最大の遅延時間がピンＡ−Ｃ−Ｂを通る経路のそれより大きい場合、ａ＞ｂ＋ｃより、ａ−ｂ＞ｃとなる。このため、ａ−ｂ（ｍｉｎ）＞ａ−ｂ＞ｃとなり、ｓｋｅｗ（Ａ）＞ｓｋｅｗ（Ｃ）がここでも成立する。
【００７６】
一方、ピンＡ−Ｂを通る経路での最大の遅延時間がピンＡ−Ｃ−Ｂを通る経路のそれより小さい場合には、ａ＜ｂ＋ｃより、ａ−ｂ＜ｃとなる。しかし、ａ−ｂ（ｍｉｎ）＞ａ−ｂであるため、ａ−ｂ（ｍｉｎ）＜ｃは必ず成立するとは限らない。よって、ｓｋｅｗ（Ａ）＜ｓｋｅｗ（Ｃ）も必ずしも成立しない。例えばａ＝１０、ｂ＝１０、ｃ＝１、ｂ（ｍｉｎ）＝８であれば、ｓｋｅｗ（Ａ）＜ｓｋｅｗ（Ｃ）は成立しない。
【００７７】
しかし、ｂ（ｍｉｎ）＋ｃ（ｍｉｎ）＞ａが成立したとすると、ａ−ｂ（ｍｉｎ）＜ｃ（ｍｉｎ）＜ｃも成立する。よって、ｓｋｅｗ（Ａ）＜ｓｋｅｗ（Ｃ）も成立する。このため、ピンＡ−Ｃ−Ｂを通る経路のみを考えれば良いということになる。
【００７８】
このように、ｂ（ｍｉｎ）＋ｃ（ｍｉｎ）＞ａが成立するときには、ピンＡ−Ｃ−Ｂを通る経路だけを残せば良く（ピンＡ−Ｂを通る経路はそれに吸収）、それが成立しないときには、ピンＡ−Ｃ−Ｂを通る経路、ピンＡ−Ｂを通る経路の両方を残すべきということになる。
【００７９】
始点となるクロックソースは１つであるため、ピンに複数のクロック信号が合流するのであれば、それが分岐するピンは必ず存在する。このことから、例えば２つのクロック信号が１つのピンに合流する場合、それが分岐するピンを求め、パスの最大遅延時間を加算して求めた経路の最大遅延時間が大きいほうの経路ではクロック信号が分岐するピンから合流するピンまでのパスの最小遅延時間を加算してその区間の最小遅延時間を求め、その求めた最小遅延時間が、経路の最大遅延時間が小さいほうの経路におけるその区間の最大遅延時間以上か否かに応じて、２つの経路をまとめれば良いことになる。
【００８０】
ところで、ｂ（ｍｉｎ）＋ｃ（ｍｉｎ）＞ａが成立したときには、上述したように、ａ−ｂ（ｍｉｎ）＜ｃも成立する。このことから、分岐するピンから合流するピンまでの経路の最小遅延時間を求めるのではなく、その分岐するピンから合流するピンの直前に位置する他に分岐するピンまでは経路の最小遅延時間を求め、それから合流するピンまでは、求めた経路の最小遅延時間にパスの最大遅延時間を加算しても良い。そのようにした場合には、ｂ（ｍｉｎ）＋ｃ＞ａはｂ（ｍｉｎ）＋ｃ（ｍｉｎ）＞ａより成立し易いため、タイミング解析の精度の低下を回避しつつ、より効率的に経路をまとめられるようになる。なお、ホールドタイムチェックを想定しているときには、経路のまとめ方はセットアップタイムチェック時のそれとは逆になる。
【００８１】
また、本実施の形態では、以下のことも考慮して経路をまとめるようにしている。
クロック信号が伝搬する経路のなかに、始点とするクロックソース以外のクロックソースを持つ経路が存在している場合がある。このことから、直前のクロックソースが同じでない経路は一つにまとめないようにしている。そのようにすることで、タイミング解析の精度が低下するのをより回避させることができる。
【００８２】
クロック信号は、常に同じ相で経路を伝搬していくとは限らない。例えばインバータを含んでいる経路では、そのインバータによって相が逆になる。その相の反転に伴いスキューが変化することがある。これは、伝搬する相の違いによって、タイミング解析の結果が最悪となる経路の組み合わせが異なってくる可能性があることを意味する。このことから、合流するピンにおいて、クロックソースから出力されたクロック信号を伝搬している相が同じでない経路は一つにまとめないようにしている。それにより、タイミング解析の精度が低下するのをより回避させている。
【００８３】
上述したように、経路のなかにはクロックソースを複数、持つ経路が存在する場合がある。このことから、本実施の形態では、クロック信号が伝搬する経路の探索でも、経路に経路識別コードを付している。その経路識別コードの値は、経路を先に進めていく過程において、クロックソースと指定されたピンを通過する際に、それまでにない値に変更している。それにより、経路識別コードの値が同じでない経路は１つにまとめないようにしている。
【００８４】
これらのことから、本実施の形態では、パスが同じピンに集まる複数の経路のなかで２つ以上の経路間で以下の条件が全て満たされていれば、それらの条件が全て満たされている経路を１つにまとめている。それにより、タイミング解析で最悪となる可能性のある経路は確実に排除しないようにしている。その条件については、以降、選択条件と呼ぶことにする。
選択条件１）直前のクロックソースが同じである
選択条件２）合流したピンにおいて、直前のクロックソースからの信号の伝搬の相が同じである
選択条件３）経路識別コードの値が同じである
選択条件４）各パスの最大遅延時間より各経路の最大遅延時間を算出しながら経路探索を行っている場合は、分岐するピンから合流するピンまでの区間において、その区間の最大遅延時間が最も大きい経路で各パスの最小遅延時間を加算して求められるその区間の最小遅延時間が、他の経路のその区間での最大遅延時間以上となっているとき
各パスの最小遅延時間より各経路の最小遅延時間を算出しながら経路探索を行っている場合は、分岐するピンから合流するピンまでの区間において、その区間の最小遅延時間が最も小さい経路で各パスの最大遅延時間を加算して求められるその区間の最大遅延時間が、他の経路のその区間での最小遅延時間以下となっているとき
上記選択条件４の代わりに、以下の選択条件４’を採用しても良い。
選択条件４’）各パスの最大遅延時間より各経路の最大遅延時間を算出しながら経路探索を行っている場合は、分岐するピンから合流するピンまでの区間において、その区間の最大遅延時間が最も大きい経路で分岐するピンから合流するピンの直前に位置する他の分岐のピンまでの各パスは最小遅延時間、それより先は各パスの最大遅延時間を加算して求められるその区間の遅延時間が、他の経路のその区間での最大遅延時間以上となっているとき
各パスの最小遅延時間より各経路の最小遅延時間を算出しながら経路探索を行っている場合は、分岐するピンから合流するピンまでの区間において、その区間の最小遅延時間が最も小さい経路で分岐するピンから合流するピンの直前に位置する他の分岐のピンまでの各パスは最大遅延時間、それより先は各パスの最小遅延時間を加算して求められるその区間の遅延時間が、他の経路のその区間での最小遅延時間以下となっているとき
次に、上記選択条件１〜４、或いは選択条件１〜３、及び４’を参照して行われる経路探索例について、図１５〜図１９に示す説明図を参照して詳細に説明する。ここでは混乱を避けるために、経路の最大遅延時間を求めていることにする。その最大遅延時間は、パスを一つ進める度に、それまでの遅延時間に、そのパスの最大遅延時間を加算していくことで求めている。
【００８５】
図１５では、クロックソースはピンｓであり、そのピンｓはピンａ、ｃとそれぞれ結ばれている。ピンｃはそのピンａと結ばれている。このことから、ピンａでパスが合流している。
【００８６】
ピンｃがクロック信号を逆相で伝搬する場合、ピンｓ−ａを通る経路とピンｓ−ｃ−ａを通る経路とでは選択条件１が成立しなくなる。このため、それらの経路はまとめられることなく、抽出されることになる。
【００８７】
図１６では、クロックソースはピンｓ、及びｃであり、ピンｓ−ａ−ｂ−ｃ−ｄ−ｇを通る経路と、ピンｓ−ａ−ｅ−ｆ−ｄ−ｇを通る経路の２つが存在している。それらの経路はピンｄで合流している。
【００８８】
そのピンｄにおいて、ピンｓ−ａ−ｂ−ｃ−ｄ−ｇを通る経路における直前のクロックソースはピンｃであり、ピンｓ−ａ−ｅ−ｆ−ｄ−ｇを通る経路のそれはピンｓである。それらの経路間は選択条件１を満たさないため、まとめられることなく抽出される。
【００８９】
図１７では、クロックソースはピンｓだけであり、ピンｓ−ａ−ｂ−ｃ−ｄ−ｇを通る経路と、ピンｓ−ａ−ｅ−ｆ−ｄ−ｇを通る経路の２つが存在している。それらの経路はピンｄで合流している。各ピンで信号の反転は起こらない。
【００９０】
それら２つの経路間では、選択条件１〜３を満たしている。このことから、選択条件４、或いは４’を満たすか否か調べることになる。ピンａとピンｂ間の最大遅延時間はｍａｘ（ａｂ）と表記し、その間の最小遅延時間はｍｉｎ（ａｂ）と表記する。他のピン間も同様に表記することにする。ピンｓ−ａ−ｅ−ｆ−ｄ−ｇを通る経路については、以降、経路ｓ−ａ−ｅ−ｆ−ｄ−ｇのようにも表記することにする。他の経路についても同様である。
【００９１】
ここでは最大遅延時間を求めていることを前提としているので、各経路のピンｄでの最大遅延時間を比較する。今、経路ｓ−ａ−ｂ−ｃ−ｄの方が最大遅延時間が大きいとする。それら経路が分岐するピンはピンａである。このことから、選択条件４を満たすか否か調べるとすると、ｍｉｎ（ａｂ）＋ｍｉｎ（ｂｃ）＋ｍｉｎ（ｃｄ）で算出される値をｍａｘ（ａｅ）＋ｍａｘ（ｅｆ）＋ｍａｘ（ｆｄ）で算出される値と比較することになる。その結果、前者の値が後者の値以上であれば、経路ｓ−ａ−ｅ−ｆ−ｄのほうは探索を打ち切ることになる。
【００９２】
選択条件４’を満たすか否か調べるとすると、ピンｄの直前に位置する分岐のあるピンはピンｂであるため、ｍａｘ（ａｂ）＋ｍｉｎ（ｂｃ）＋ｍｉｎ（ｃｄ）で算出される値をｍａｘ（ａｅ）＋ｍａｘ（ｅｆ）＋ｍａｘ（ｆｄ）で算出される値と比較することになる。その結果、前者の値が後者の値以上であれば、経路ｓ−ａ−ｅ−ｆ−ｄのほうは探索を打ち切ることになる。ｍａｘ（ａｂ）＋ｍｉｎ（ｂｃ）＋ｍｉｎ（ｃｄ）＞ｍｉｎ（ａｂ）＋ｍｉｎ（ｂｃ）＋ｍｉｎ（ｃｄ）であるのが普通なことから明らかなように、選択条件４’は選択条件４よりも満たしやすくなっている。
【００９３】
選択条件４、或いは４’を満たし、経路ｓ−ａ−ｅ−ｆ−ｄの探索を継続する場合には、経路ｓ−ａ−ｂ−ｃ−ｄのほうの探索は打ち切ることになる。選択条件４及び４’の何れも満たしていない場合には、各経路はそのまま探索を継続することになる。それら各経路には異なる経路識別コードが割り当てられる。
【００９４】
図１８では、クロックソースはピンｓだけであり、各ピンで信号の反転は起こらない。ピンｃまででは、経路ｓ−ａ−ｂ−ｃと、経路ｓ−ａ−ｇ−ｃの２つが存在している。ここでは、選択条件４及び４’の何れも満たさないため、各経路の探索は続行していることとする。経路識別コードの値は、経路ｓ−ａ−ｂ−ｃでは０、経路ｓ−ａ−ｇ−ｃでは１とする。
【００９５】
各経路の探索をピンｄまで進めると、そのピンｄまででは、経路ｓ−ａ−ｂ−ｃ−ｄと、経路ｓ−ａ−ｇ−ｃ−ｄの２つが存在していることになる。そのピンｄはピンｅ、ｈと結ばれている。この結果、ピンｆでは、経路ｓ−ａ−ｂ−ｃ−ｄ−ｅ（経路識別コード０）、経路ｓ−ａ−ｇ−ｃ−ｄ−ｅ（経路識別コード１）、経路ｓ−ａ−ｂ−ｃ−ｄ−ｈ（経路識別コード０）、及び経路ｓ−ａ−ｇ−ｃ−ｄ−ｈ（経路識別コード１）の４つの経路の合流を考慮することになる。
【００９６】
各経路間では前提から選択条件１、２が成立している。経路識別コードの値が異なる経路間では選択条件３を満たしていないため、そのコードの値が同じ経路間で選択条件４、或いは４’が満たされているか否か調べることになる。即ち経路ｓ−ａ−ｂ−ｃ−ｄ−ｅと経路ｓ−ａ−ｂ−ｃ−ｄ−ｈの間、及び経路ｓ−ａ−ｇ−ｃ−ｄ−ｅと経路ｓ−ａ−ｇ−ｃ−ｄ−ｈの間で選択条件４、或いは４’を満たしているか否か調べることになる。
【００９７】
その結果、経路ｓ−ａ−ｂ−ｃ−ｄ−ｅと経路ｓ−ａ−ｂ−ｃ−ｄ−ｈの間で選択条件４、或いは４’が満たされていることを確認すれば、それらのうちでピンｄからピンｆまでの区間における最大遅延時間が小さいほうの経路の探索は打ち切られる。選択条件４、及び４’が共に満たされていないことを確認すれば、各経路の探索は続行される。続行経路ｓ−ａ−ｂ−ｃ−ｄ−ｅと経路ｓ−ａ−ｂ−ｃ−ｄ−ｈの間で選択条件４、或いは４’が満たされていることを確認すれば、同様に、それらのうちでピンｄからピンｆまでの区間における最大遅延時間が小さいほうの経路の探索は打ち切られる。選択条件４、及び４’が共に満たされていないことを確認すれば、各経路の探索は続行される。各経路が共に選択条件４及び４’を満たしていなければ、例えば以下のように経路識別コードの値として０〜３のうちの何れかを持つ経路が最終的に抽出される。各経路が共に選択条件４或いは４’を満たしていれば、例えば以下の経路識別コードの値として０、或いは１を持つ経路だけが最終的に抽出される。
【００９８】
経路ｓ−ａ−ｂ−ｃ−ｄ−ｅ−ｆ−ｉ（経路識別コード０）
経路ｓ−ａ−ｇ−ｃ−ｄ−ｅ−ｆ−ｉ（経路識別コード１）
経路ｓ−ａ−ｂ−ｃ−ｄ−ｈ−ｆ−ｉ（経路識別コード２）
経路ｓ−ａ−ｇ−ｃ−ｄ−ｈ−ｆ−ｉ（経路識別コード３）
上述した経路探索は、経路の最大遅延時間に着目したものであり、経路の最小遅延時間に着目した経路探索も同様に行われる。データ信号を入力、或いは出力するピンをデータピン、クロック信号を入力、或いは出力するピンをクロックピンと呼べば、タイミング解析として行うセットアップタイムチェックでは、データ信号の送り側のセルが持つクロックピンへの経路は遅延時間が最大の経路、そのデータ信号の受け側のセルが持つクロックピンへの経路は遅延時間が最小の経路を用いる。ホールドタイムチェックでは、逆に、データ信号の送り側のセルが持つクロックピンへの経路は遅延時間が最小の経路、そのデータ信号の受け側のセルが持つクロックピンへの経路は遅延時間が最大の経路を用いる。送り側のセルが持つクロックピンへの経路、受け側のセルが持つクロックピンへの経路の片方、或いは両方が複数あれば、それらの経路の組み合わせ全てのチェックを行うことになる。
【００９９】
図１９は、経路探索によって抽出された経路を説明する図である。図１９中のエリア１９１はクロック経路の探索のためにトレースするクロックパスが存在しているエリアであり、エリア１９２はデータ経路の探索のためにトレースするデータパスが存在しているエリアである。ＦＦ１９３が送り側、ＦＦ１９４が受け側である。太線で描いた丸は経路条件中で指定されたピンを表している。各エリア１９１、及び１９２において、実線はタイミング解析のために抽出された経路、破線は抽出されなかった、即ち探索が途中で終了した経路を表している。
【０１００】
図１９に示すように、普通の線で描いた丸で示すクロックソースからＦＦ１９３のＣＫ端子へのクロック経路は１つだけであることからそれが抽出され、クロックソースからＦＦ１９４のＣＫ端子へのクロック経路は４つのなかから２つだけが抽出されている。ＦＦ１９３からＦＦ１９４へのデータ経路は５つ存在しているが、経路条件で指定されたピンを通る３つだけが抽出されている。このことから、上述したような経路探索を行うことにより、図１９に示す例では、１×２×３＝６回のタイミングチェックを行えば良いことになる。
【０１０１】
抽出される経路はタイミングチェック上、最悪となる可能性が考えられるものである。このため、その精度は、各経路の全ての組み合わせでタイミングチェックを行ったものと同じとなる。その全ての組み合わせの数は、上述したように、クロックソースからＦＦ１９３のＣＫ端子へのクロック経路は１つ、クロックソースからＦＦ１９４のＣＫ端子へのクロック経路は４つ、ＦＦ１９３からＦＦ１９４へのデータ経路は５つ存在しているため、１×４×５＝２０となる。このことから、精度を高く維持させつつ、抽出する経路の数を低減することによって、タイミングチェックの回数を大幅に低減できていることが分かる。
【０１０２】
抽出する経路の数やタイミングチェックの回数を低減させることで、処理に要するメモリ容量はより低減し、処理時間はより短くなる。このことから、これまでより大規模な電子回路のタイミングチェックも行えることになる。
【０１０３】
次に、パルス幅チェック（波形解析）用の経路探索について説明する。
クロックソースからのクロック信号はクロック経路を伝搬中にその波形が変化していく。その変化した後の波形がＦＦ等の動作を保証するだけの形を保っているか否か確認するのがパルス幅チェックである。チェックする内容としては、信号波形のライズエッジ（立ち上がり）から次のライズエッジまでの時間（以降、第１の周期幅と呼ぶ）、ライズエッジから次のフォール（Ｆａｌｌ）エッジ（立ち下がり）までの時間（以降、ハイレベル幅と呼ぶ）、フォールエッジから次のライズエッジまでの時間（以降、ローレベル幅と呼ぶ）、及びフォールエッジから次のフォールエッジまでの時間（以降、第２の周期幅と呼ぶ）、と最大で４種類ある。
【０１０４】
パルス幅チェックでは、始点となるクロックソースからチェックの対象となるピンまで、経路毎に各エッジの総遅延時間を算出し、各エッジ間の総遅延時間の差とクロックソースから出力されるクロック信号の波形から各パルス幅を求める必要がある。しかし、上述したように、現在、設計される回路では、経路が複雑に分岐合流を繰り返しているのが普通であるために、経路毎に各エッジ間の総遅延時間を求めることは現実的でない。このことから、本実施の形態では、分岐合流するクロック経路は以下のようにまとめるようにしている。
【０１０５】
例えば或るピンでクロック信号がハイレベルとなっている幅（ハイレベル幅）がチェックの対象であるとすると、そのピンへクロックソースからの信号が反転しないで伝搬しているのであれば、ハイレベル幅は、
ハイレベル幅＝（クロックソースでのハイレベル幅）−（（ピンでのライズエッジのクロックソースからの総遅延時間）−（ピンでのフォールエッジのクロックソースからの総遅延時間））
で計算される。従って、そのようにして計算されるハイレベル幅がタイミング解析で指定されたハイレベル幅より大きければ良いことになる。ただし、ここではパスの遅延時間には最大の遅延時間と最小の遅延時間とが存在しているため、最悪の場合を考えて、ハイレベル幅は、
ハイレベル幅＝（クロックソースでのハイレベル幅）−（（ピンでのライズエッジのクロックソースからの最大の総遅延時間）−（ピンでのフォールエッジのクロックソースからの最小の総遅延時間））
で計算することになる。
【０１０６】
それ以外の第１の周期幅、第２の周期幅、及びローレベル幅については、それぞれ以下のようにして計算する。
第１の周期幅＝（クロックソースでの第１の周期幅）−（（ピンでのライズエッジのクロックソースからの最大の総遅延時間）−（ピンでのライズエッジのクロックソースからの最小の総遅延時間））
第２の周期幅＝（クロックソースでの第２の周期幅）−（（ピンでのフォールエッジのクロックソースからの最大の総遅延時間）−（ピンでのフォールエッジのクロックソースからの最小の総遅延時間））
ローレベル幅＝（クロックソースでのローレベル幅）−（（ピンでのフォールエッジのクロックソースからの最大の総遅延時間）−（ピンでのライズエッジのクロックソースからの最小の総遅延時間））
或るピンへのクロック経路が複数、存在している場合、各経路でクロックソースからの信号が反転することなく伝搬するのであれば、上述の式でそのピンのハイレベル幅は算出される。それにより、経路毎に、（（ピンでのライズエッジのクロックソースからの最大の総遅延時間）−（ピンでのフォールエッジのクロックソースからの最小の総遅延時間））で計算される総遅延差が異なることになる。よって、クロックソースからの信号が反転することなく伝搬する経路のうち、（（ピンでのライズエッジのクロックソースからの最大の総遅延時間）−（ピンでのフォールエッジのクロックソースからの最小の総遅延時間））で計算される遅延差が最大となる経路が分かる。その最大の総遅延差でのチェックがタイミング的に最も厳しくなるので、その総遅延差でのチェックでハイレベル幅に問題がなければ他の経路でも問題は無いことになる。
【０１０７】
パルス幅チェックには、上記したように、最大で４種類のチェックがある。このことから、その４種類のチェックを行えるようにするためには、上記総遅延差（以降、第１の総遅延差と呼ぶ）の他に、（（ピンでのライズエッジのクロックソースからの最大の総遅延時間）−（ピンでのライズエッジのクロックソースからの最小の総遅延時間））で計算される総遅延差（以降、第２の総遅延差と呼ぶ）、（（ピンでのフォールエッジのクロックソースからの最大の総遅延時間）−（ピンでのライズエッジのクロックソースからの最小の総遅延時間））で計算される総遅延差（以降、第３の総遅延差と呼ぶ）、及び（（ピンでのフォールエッジのクロックソースからの最大の総遅延時間）−（ピンでのフォールエッジのクロックソースからの最小の総遅延時間））で計算される総遅延差（以降、第４の総遅延差と呼ぶ）、を用意する必要がある。同じピンで合流する複数の経路において、上述のように算出される各総遅延差別に、そのなかで最大のものを選択すれば、それら複数の経路はタイミング的に最も厳しいように１つにまとめられることになる。その結果、パルス幅チェックの精度の低下を回避しつつ、経路の数を低減できることになる。同じピンで合流する複数の経路を１つにまとめる（合成する）うえでそれら複数の経路間で満たすべき条件としては、以下のものを設定している。それにより、区別すべき経路は区別して扱っている。なお、その条件は以降、合成条件と呼ぶことにする。
【０１０８】
合成条件１：直前のクロックソースからの信号が伝搬する相が同じである
合成条件２：直前のクロックソースが同じである
経路探索は、上述の経路探索と同様に、始点とするクロックソースから１つずつ先のピンに進めながら、各ピン毎にイベントを作成していくことで行う。そのイベントとしては、直前のイベントを示すデータ、信号が反転しているか否かを示すデータ、及びパルス幅を算出するための各種総遅延差（遅延差の累算値）を少なくとも作成する。各種総遅延差は、直前のイベントで作成された各種総遅延差を更新する形で作成する。
【０１０９】
それら総遅延差は、具体的には以下のようにして作成（算出）している。ここでは、便宜的に、直前のイベントで作成されている第１〜第４の総遅延差は、それぞれ直前の第１〜第４の総遅延差、今回のイベントにおける第１〜第４の総遅延差はそれぞれ今回の第１〜第４の総遅延差と表記することにする。直前のイベントで示されるピンと結ぶパスにおいて、ライズエッジからライズエッジの伝搬に要する最大の遅延時間からフォールエッジからフォールエッジの伝搬に要する最小の遅延時間を減算して算出される遅延差を第１の遅延差、ライズエッジからライズエッジの伝搬に要する最大の遅延時間から最小の遅延時間を減算して算出される遅延差を第２の遅延差、フォールエッジからフォールエッジの伝搬に要する最大の遅延時間からライズエッジからライズエッジの伝搬に要する最小の遅延時間を減算して算出される遅延差を第３の遅延差、フォールエッジからフォールエッジの伝搬に要する最大の遅延時間から最小の遅延時間を減算して算出される遅延差を第４の遅延差、とそれぞれ表記することにする。
【０１１０】
先ず、クロック信号が反転していない場合には、即ちクロックソースからの信号が直前のイベント（ピン）及び今回のイベント（ピン）で共に反転しているか、或いは共に反転していない場合には、以下のようにして今回の第１〜第４の総遅延差が算出される。
【０１１１】
今回の第１の総遅延差＝（直前の第１の総遅延差）＋（第１の遅延差）
今回の第２の総遅延差＝（直前の第２の総遅延差）＋（第２の遅延差）
今回の第３の総遅延差＝（直前の第３の総遅延差）＋（第３の遅延差）
今回の第４の総遅延差＝（直前の第４の総遅延差）＋（第４の遅延差）
クロック信号が反転している場合には、即ち直前のイベント（ピン）におけるクロックソースからの信号の相が今回のイベント（ピン）におけるそれと異なっている場合には、以下のようにして今回の第１〜第４の総遅延差が算出される。ここでは、便宜的に、直前のイベントで示されるピンと結ぶパスにおいて、フォールエッジからライズエッジの伝搬に要する最大の遅延時間からフォールエッジからライズエッジの伝搬に要する最小の遅延時間を減算して算出される遅延差を第５の遅延差、フォールエッジからライズエッジの伝搬に要する最大の遅延時間からライズエッジからフォールエッジの伝搬に要する最小の遅延時間を減算して算出される遅延差を第６の遅延差、ライズエッジからフォールエッジの伝搬に要する最大の遅延時間からフォールエッジからライズエッジの伝搬に要する最小の遅延時間を減算して算出される遅延差を第７の遅延差、ライズエッジからフォールエッジの伝搬に要する最大の遅延時間から最小の遅延時間を減算して算出される遅延差を第８の遅延差、とそれぞれ表記する。
【０１１２】
今回の第１の総遅延差＝（直前の第３の総遅延差）＋（第５の遅延差）
今回の第２の総遅延差＝（直前の第４の総遅延差）＋（第６の遅延差）
今回の第３の総遅延差＝（直前の第１の総遅延差）＋（第７の遅延差）
今回の第４の総遅延差＝（直前の第２の総遅延差）＋（第８の遅延差）
次に上記合成条件１、２を参照して行われるパルス幅チェック用の経路探索例について、図２０、図１５、及び図１６に示す説明図を参照して詳細に説明する。
【０１１３】
図２０では、クロックソースはピンｓであり、終点はピンｇである。各ピンを結びパスで信号の反転は起こらないとする。経路ｓ−ａ−ｂ−ｃ−ｄ−ｇは経路ｓ−ａ−ｅ−ｆ−ｄ−ｇとピンｄで合流している。
【０１１４】
各経路ｓ−ａ−ｂ−ｃ−ｄ−ｇ、ｓ−ａ−ｅ−ｆ−ｄ−ｇ間では合成条件１、２を全て満たしている。このため、ピンｄでは、経路ｓ−ａ−ｂ−ｃ−ｄ、ｓ−ａ−ｅ−ｆ−ｄまでの各種総遅延差がそれぞれ比較して、最大となっている総遅延差を選択する。それにより、経路は１つに合成されることになる。
【０１１５】
図１５では、クロックソースはピンｓであり、そのピンｓはピンａ、ｃとそれぞれ結ばれている。ピンｃはそのピンａと結ばれている。このことから、ピンａでパスが合流している。
【０１１６】
ピンｃがクロック信号を逆相で伝搬する場合、経路ｓ−ａと経路ｓ−ｃ−ａ間は合成条件１を満たさなくなる。このため、それらの経路は合成されることなく、探索が続けられて抽出されることになる。
【０１１７】
図１６では、クロックソースはピンｓ、及びｃであり、経路ｓ−ａ−ｂ−ｃ−ｄ−ｇは経路ｓ−ａ−ｅ−ｆ−ｄ−ｇとピンｄで合流している。
そのピンｄにおいて、経路ｓ−ａ−ｂ−ｃ−ｄにおける直前のクロックソースはピンｃであり、経路ｓ−ａ−ｅ−ｆ−ｄ−ｇにおけるそれはピンｓである。このため、それらの経路間では合成条件２を満たさないため、まとめられることなく探索が続けられて抽出されることになる。
【０１１８】
このようにして、本実施の形態では、上述の経路探索と同様に、経路探索を行いながら、複数の経路の組み合わせのなかで１つにまとめられるものは一つにまとめている。それにより、全ての経路を考慮しつつ、最終的に抽出する経路数を低減させている。そのように経路数を低減させる結果、分岐合流を繰り返すような電子回路であっても、高精度なパルス幅チェックをより短い処理時間、より少ないメモリ容量で行えるようになる。
【０１１９】
上記第１〜第４の総遅延差は、パルス幅チェックの対象とするピンで残っていた経路毎に保持される。それら総遅延差は、直前のクロックソースから出力されるクロック信号の対応するパルス幅の時間と加算することにより、そのピンでのパルス幅を算出することができる。このことから、経路探索後のパルス幅チェックは極めて迅速に行うことができる。
【０１２０】
上述の経路探索やタイミング解析は図２１に示すフローに沿って行われる。次に、図２１を参照して、そのフローで行われる処理、及びその流れについて詳細に説明する。なお、その図２１に示すフローは、例えばユーザ（設計者）が入力装置３３を操作して、電子回路のなかでタイミング解析の対象とする部分を指定してその解析を指示した場合に、図３に示すＣＰＵ３１が、例えば外部記憶装置３５に搭載された記憶媒体（例えばハードディスク）に記憶されているプログラムを読み出して実行することで実現される。
【０１２１】
先ず、ステップＳ１では、設定された選択条件を全て満たす複数のクロック経路はそのうちの１つを選択しつつ、クロックソースと指定されたピンを始点として、クロックパスをトレースしていくことでクロック経路の探索を行うクロックパストレース処理を実行する。ステップＳ２では、データ経路を対象に、他と区別すべきデータ経路が満たすべき経路条件の設定を行う。その経路条件の設定は解析の対象となる部分に存在するセルの種類や組み合わせなどを基に自動的に行っても良いが、ユーザに設定させるようにしても良い。
【０１２２】
ステップＳ２に続くステップＳ３では、設定された経路条件を満たすか否か区別しつつ、データパスをトレースしていくことでデータ経路の探索を行うデータパストレース処理を実行する。次に移行するステップＳ４では、ステップＳ１のクロックパストレース処理で抽出したクロック経路、及びステップＳ３のデータパストレース処理で抽出したデータ経路の組み合わせ毎に、セットアップタイムチェック、及びホールドタイムチェックを行うタイミングチェック処理を実行する。その後は、ステップＳ５に移行して、例えば出力装置３４にチェック結果を出力させる。そのチェック結果を出力させることで、タイミングチェックにかかる一連の処理は終了する。
【０１２３】
一方、ステップＳ６では、予め設定された合成条件を満たすか否かに応じて複数のクロック経路を合成しつつ、クロックパスをトレースしていくことでパルス幅チェック用にクロック経路の探索を行うパルス幅チェック用トレース処理を実行する。その実行時には、各イベント（ピン）毎に、上記第１〜第４の総遅延差が算出される。このことから、続くステップＳ７では、ステップＳ６のパルス幅チェック用トレース処理で抽出したクロック経路毎に、その第１〜第４の総遅延差によりクロックソースから出力されるクロック信号の波形を変形させた後の波形の形状のチェックを行うクロックパルス幅チェック処理を実行する。その実行後はステップＳ５に移行して、そのチェック結果を例えば出力装置３４に出力させる。そのチェック結果を出力させることで、パルス幅チェックにかかる一連の処理が終了する。
【０１２４】
以降は、図２１に示すタイミング解析フローで実行される各種サブルーチン処理について詳細に説明する。
図２２は、上記ステップＳ１として実行されるクロックパストレース処理のフローチャートである。タイミング解析フロー内で実行される各種サブルーチン処理については、始めに図２２を参照して、クロックパストレース処理について詳細に説明する。
【０１２５】
先ず、ステップＳ１１では、指定されたクロックソースを始点として、それが出力するクロック信号の到達する範囲のピンを深さ優先探索などの手法により特定する処理１を実行する。続くステップＳ１２では、特定した範囲内に存在するピンを始点のピンから近い順に並べ替えて処理順とする処理２を実行する。
【０１２６】
上記近さは、例えば始点からパスを辿ってピンに至るまでに経由するピンの数から決定し、その数が少ないほど近いとする。ピンに至る経路が複数、存在している場合には、経由するピンの数が最も多い経路で経由することになるピンの数から近さを決定する。そのようにして処理順を決定することにより、例えば図１５〜図１８に示すグラフのようにその範囲、及びピンの接続関係が特定されることになる。
【０１２７】
ステップＳ１２に続くステップＳ１３では、決定した処理順に従って、ピンにイベントを作成していく処理３を実行する。それにより、各ピンにイベントを作成した後、一連の処理を終了する。
【０１２８】
上述のクロックパストレース処理の実行により、図２３〜図２７に示す各種サブルーチン処理が実行される。以降は、その各種サブルーチン処理について詳細に説明する。
【０１２９】
図２３は、上記ステップＳ１３として実行される処理３のフローチャートである。各種サブルーチン処理としては、始めに図２３を参照して、その処理３について詳細に説明する。
【０１３０】
先ず、ステップＳ２１では、始点のピンにはその直前のピン（イベント）が存在していないことから、他のピンと区別してイベントを作成する。そのイベントはピンに対応付けて作成される情報テーブルであり、ここでは、その情報テーブルに、経路に沿った総遅延時間、前段のイベントを示すデータであるイベント名、直前のクロックソースを示すデータとしてのイベント名、直前のクロックソースからの信号を伝搬する相を示すデータ、及び経路識別コードなどを格納している。始点のピンでは、前段のイベントが存在していないために、経路識別コードの値は０、前段のイベントはないことを示すデータ、信号の相は同相を示すデータを格納している。
【０１３１】
上記情報テーブルに格納する総遅延時間は、設定されているモードによって異なる。そのモードは、パスの最大遅延時間を加算していくモード（以降、便宜的に最大遅延モードと呼ぶ）、及びその最小遅延時間を加算していくモード（以降、便宜的に最小遅延モードと呼ぶ）の２つがある。特に詳細な説明は省略するが、そのモードを切り換えることで、処理３は異なるモードで２回、実行するようになっている。ここでは、混乱を避けるために、現在のモードを考慮した説明は最小限に抑えることにする。パスの遅延時間については例えば外部記憶装置３５に搭載の記憶媒体（例えばハードディスク）に記憶されたライブラリや配線長データベースを参照することで得ることができる。
【０１３２】
ステップＳ２１に続くステップＳ２２では、図２２のステップＳ１２で決定した処理順に従って、到達範囲内のピンを取り出す。次に移行するステップＳ２３では、取り出したピンのイベントを作成するピンのイベント作成処理を実行する。その後はステップＳ２４に移行する。
【０１３３】
ステップＳ２４では、イベントを作成していないピンが存在するか否か判定する。全ての経路を考慮しつつ、全てのピンにイベントを作成した場合、判定はＮＯとなり、ここで一連の処理を終了する。そうでない場合には、判定はＹＥＳとなり、上記ステップＳ２２に戻ってそれ移行の処理を同様に実行する。
【０１３４】
上記ステップＳ２２〜Ｓ２４で形成される処理ループは、ステップＳ２４の判定がＮＯとなるまで繰り返し実行される。それにより、図８〜図１１を参照して説明したのと同様に、各ピンに１つ以上のイベントが作成されることになる。
【０１３５】
図２４は、上記ステップＳ２３として実行されるピンのイベント作成処理のフローチャートである。次に図２４を参照して、そのイベント作成処理について詳細に説明する。
【０１３６】
先ず、ステップＳ３１では、現在、処理対象としているピンの前段に位置する全てのピンのイベントを順に取り出す。次に移行するステップＳ３２では、取り出した前段のイベントからピンに信号が伝搬した場合のイベントの内容を一時領域（メモリ３２、或いは外部記憶装置３５に確保される領域である）に作成して、内容を作成したイベントを仮イベントとする仮イベントの内容作成処理を実行する。それを実行した後はステップＳ３３に移行する。
【０１３７】
ステップＳ３３では、処理対象のピンに既に作成されたイベントがあるか否か判定する。ステップＳ３２で作成する仮イベントを含め、処理対象のピンに複数のイベントが作成されている場合、判定はＹＥＳとなってステップＳ３５に移行する。そうでない場合には、即ち処理対象のピンにイベントは作成されてなく、且つ作成した仮イベントも１つであった場合には、判定はＮＯとなってステップＳ３４に移行し、作成した仮イベントをイベントとしてピンに付加した後、一連の処理を終了する。
【０１３８】
一方、ステップＳ３５では、既に作成されているイベントのなかに仮イベントとの間で選択条件１〜３の成り立つイベント（以降、比較イベントと呼ぶ）があるか否か判定する。処理対象のピンで選択条件１〜３を満たす複数の経路が合流していない場合、判定はＮＯとなり、ステップＳ３４に移行して、仮イベントをイベントとしてピンに付加した後、一連の処理を終了する。そうでない場合には、判定はＹＥＳとなってステップＳ３６に移行する。
【０１３９】
上記ステップＳ３１で前段のピンのイベントを複数、取り出していれば、複数の仮イベントが作成される。このことから、ステップＳ３５では、仮イベント間でも選択条件１〜３が成り立っている仮イベントの有無も同様に判定している。複数の仮イベントの間で選択条件１〜３が成り立っていれば、そのうちの一つ、或いは複数の仮イベントを比較イベントとして扱っている。それにより、既に作成したイベント間では選択条件１〜３、及び選択条件４’（または４）の全てが成り立つことは回避させている。
【０１４０】
ステップＳ３６では、比較イベントと仮イベントの総遅延時間を比較して優先度を決定する。その優先度は、モードが最大遅延モードであれば、比較イベントと仮イベントのなかで総遅延時間が大きいほうが高いこととなり、それが最小遅延モードであればその逆となる。そのように優先度を決定した後はステップＳ３７に移行する。
【０１４１】
ステップＳ３７では、比較イベントと仮イベントの間で選択条件４’（または４）が成り立つか否か判定する。それら各イベントの条件テーブルを参照して経路を遡ることで特定される直前に経路が分岐するピンから現在、処理対象のピンまでの区間の遅延時間の間に選択条件４’（または４）が成立していた場合、判定はＹＥＳとなってステップＳ４０に移行する。そうでない場合には、判定はＮＯとなってステップＳ３８に移行する。
【０１４２】
ステップＳ３８では、処理対象のピンで合流する複数の経路は１つにまとめられないことから、比較イベントと仮イベントのなかで優先度の低いほうの経路識別コードを更新して、既存でない値とする。次に移行するステップＳ３９では、仮イベントをイベントとして処理対象のピンに付加する。その後に一連の処理を終了する。
【０１４３】
一方のステップＳ４０では、仮イベントのほうが優先度が高いか否か判定する。その仮イベントに高い優先度を設定していた場合、判定はＹＥＳとなり、ステップＳ４１で仮イベントの内容を比較イベントの内容に置き換えた後、言い換えれば比較イベントを持つ経路を、仮イベントを作成した経路にまとめた後、一連の処理を終了する。そうでない場合には、判定はＮＯとなり、ステップＳ４２で仮イベントの内容を破棄した後、言い換えれば仮イベントを作成した経路を、比較イベントを持つ経路にまとめた後、一連の処理を終了する。
【０１４４】
このようにして、本実施の形態では、経路探索のためのクロックパスのトレースを行いながら、選択条件１〜３、４’、或いは１〜４を満たす複数の経路はそのなかで優先度が最も高い経路にまとめている。
【０１４５】
図２５は、上記ステップＳ３２として実行される仮イベントの内容作成処理のフローチャートである。次にその内容作成処理について詳細に説明する。
先ず、ステップＳ５１では、経路識別コードの値や直前のクロックソースを決定する処理を行う。その次に移行するステップＳ５２では、直前のクロックソースから信号が伝搬する相を決定する処理を行う。その後はステップＳ５３に移行して、前段のイベントや経路の総遅延時間などを設定する処理を実行した後、一連の処理を終了する。
【０１４６】
上記ステップＳ５１〜Ｓ５３は、各仮イベント毎に行われる。それにより、各仮イベント毎に、仮イベントの内容を示すデータが一時領域に保存されることになる。
【０１４７】
上記ステップＳ５１、及びＳ５２では、それぞれ以下のような内容の処理が実行される。
図２６は、上記ステップＳ５１として実行される経路識別コード、直前のクロックソースの決定処理のフローチャートである。始めに図２６を参照して、その決定処理について詳細に説明する。
【０１４８】
先ず、ステップＳ６１では、前段のイベントを持つピンが始点以外のクロックソースか否か判定する。そのピンが始点以外のクロックソースであった場合、判定はＹＥＳとなってステップＳ６２に移行する。そうでない場合には、判定はＮＯとなってステップＳ６３に移行する。なお、ピンがクロックソースか否かは、例えばライブラリ、或いはネットリストを参照することで特定する。
【０１４９】
ステップＳ６２では、直前のピンが始点以外のクロックソースであることから、既存でない値を経路識別コードに設定するとともに、直前のクロックソースを示すイベント名として、そのクロックソースのイベント名を設定する。そのようにして経路識別コード、及び直前のクロックソースを示すイベント名を設定（決定）した後、一連の処理を終了する。
【０１５０】
ステップＳ６３では、直前のピンが始点以外のクロックソースでないことから、経路識別コード、及び直前のクロックソースを示すイベント名として、前段のイベントがそれぞれ持つものを設定する。そのようにして経路識別コード、及び直前のクロックソースを示すイベント名を設定（決定）した後、一連の処理を終了する。
【０１５１】
次に、図２５に示すフローチャート内でステップＳ５２として実行される信号伝搬の相決定処理について、図２７に示すそのローチャートを参照して詳細に説明する。
【０１５２】
先ず、ステップＳ７１では、前段のイベントを持つピンと結ぶパスで信号が反転するか否か判定する。例えばライブラリからそのパスで信号が反転することを確認した場合、判定はＹＥＳとなってステップＳ７２に移行し、信号が伝搬する相として、前段のイベントにおける信号が伝搬する相を反転したものに決定した後、一連の処理を終了する。そうでない場合には、即ち信号が反転していないか、或いは直前のイベントを持つピンがクロックソースであった場合には、判定はＮＯとなってステップＳ７３に移行し、信号が伝搬する相として、前段のイベントにおける信号が伝搬する相を決定した後、一連の処理を終了する。直前のイベントを持つピンがクロックソースであれば、その相は同相を決定する。
【０１５３】
図２１に示す解析フローでステップＳ１として実行されるクロックパストレース処理では、上述したような各種サブルーチン処理が実行される。それにより、セットアップタイムチェックやホールドタイムチェックといったタイミング解析を行ううえで用いるクロック経路をモード別に抽出するようになっている。
【０１５４】
図２８は、図２１に示すタイミング解析フローでステップＳ３として実行されるデータパストレース処理のフローチャートである。次に図２８を参照して、そのトレース処理について詳細に説明する。
【０１５５】
先ず、ステップＳ８１では、図２１のステップＳ２で設定された経路条件中で指定されたピン（始点、終点、或いは特定のピン、など）にフラグを付加するといった前処理を行う（図６、図７等参照）。続くステップＳ８２では、始点として指定されたピンから出力されるデータ信号の到達する範囲のピンを深さ優先探索などの手法により特定する処理を実行する。その次に移行するステップＳ８３では、特定した範囲内に存在するピンを始点のピンから近い順に並べ替えて処理順とする処理を実行する。
【０１５６】
上記ステップＳ８２、Ｓ８３の内容は、図２２のステップＳ１１の処理１、ステップＳ１２の処理２と同様である。ステップＳ８３の処理を実行することで、図６に示すグラフのように、データ信号が到達する範囲、及びピンの接続関係が特定されることになる。
【０１５７】
ステップＳ８３に続くステップＳ８４では、決定した処理順に従って、ピンにイベントを作成していく処理４を実行する。それにより、各ピンにイベントを作成した後、一連の処理を終了する。
【０１５８】
上述のデータパストレース処理の実行により、図２３〜図２７に示す各種サブルーチン処理が実行される。以降は、その各種サブルーチン処理について詳細に説明する。
【０１５９】
図２９は、上記ステップＳ８４として実行される処理４のフローチャートである。各種サブルーチン処理としては、始めに図２９を参照して、その処理４について詳細に説明する。
【０１６０】
先ず、ステップＳ９１では、始点のピンにはその直前のピン（イベント）が存在していないことから、他のピンと区別してイベントを作成する。ここでは、そのイベントである情報テーブルに、経路に沿った総遅延時間、前段のイベントを示すデータであるイベント名、及び経路識別コードなどを格納している。始点のピンでは、前段のイベントが存在していないために、経路識別コードの値は０、前段のイベントはないことを示すデータ、総遅延時間は０を格納している。
【０１６１】
上記情報テーブルに格納する総遅延時間は、処理３と同様に、モードを切り換えて２回、実行するようになっている。ここでも、混乱を避けるために、現在のモードを考慮した説明は最小限に抑えることにする。パスの遅延時間については例えば外部記憶装置３５に搭載の記憶媒体（例えばハードディスク）に記憶されたライブラリや配線長データベースを参照することで得ることができる。２つのモードについては、処理３と同様に、最大遅延モード、最小遅延モードとそれぞれ呼ぶことにする。
【０１６２】
ステップＳ９１に続くステップＳ９２では、図２８のステップＳ８３で決定した処理順に従って、到達範囲内のピンを取り出す。次に移行するステップＳ９３では、取り出したピンのイベントを作成するピンのイベント作成処理を実行する。その後はステップＳ９４に移行する。
【０１６３】
ステップＳ９４では、イベントを作成していないピンが存在するか否か判定する。全ての経路を考慮しつつ、全てのピンにイベントを作成した場合、判定はＮＯとなり、ここで一連の処理を終了する。そうでない場合には、判定はＹＥＳとなり、上記ステップＳ９２に戻ってそれ移行の処理を同様に実行する。
【０１６４】
上記ステップＳ９２〜Ｓ９４で形成される処理ループは、ステップＳ９４の判定がＮＯとなるまで繰り返し実行される。それにより、図８〜図１１を参照して説明したのと同様に、各ピンに１つ以上のイベントが作成されることになる。
【０１６５】
図３０は、上記ステップＳ９３として実行されるピンのイベント作成処理のフローチャートである。次に図３０を参照して、そのイベント作成処理について詳細に説明する。
【０１６６】
先ず、ステップＳ１０１では、現在、処理対象としているピンの前段に位置する全てのピンのイベントを順に取り出す。次に移行するステップＳ１０２では、取り出した前段のイベントからピンに信号が伝搬した場合のイベントの内容を一時領域（メモリ３２、或いは外部記憶装置３５に確保される領域である）に作成して、内容を作成したイベントを仮イベントとする仮イベントの内容作成処理を実行する。それを実行した後はステップＳ１０３に移行する。
【０１６７】
ステップＳ１０３では、処理対象のピンに既に作成されたイベントがあるか否か判定する。ステップＳ１０２で作成する仮イベントを含め、処理対象のピンに複数のイベントが作成されている場合、判定はＹＥＳとなってステップＳ１０４に移行する。そうでない場合には、即ち処理対象のピンにイベントは作成されてなく、且つ作成した仮イベントも１つであった場合には、判定はＮＯとなってステップＳ１０５に移行する。
【０１６８】
ステップＳ１０４では、既に作成されているイベントのなかに仮イベントの経路識別コードの値が同じイベント（比較イベント）があるか否か判定する。処理対象のピンで経路識別コードの値の異なる複数の経路が合流していない場合、判定はＮＯとなり、ステップＳ１０５に移行して、仮イベントをイベントとしてピンに付加した後、一連の処理を終了する。そうでない場合には、判定はＹＥＳとなってステップＳ１０６に移行する。
【０１６９】
上記ステップＳ１０１で前段のピンのイベントを複数、取り出していれば、複数の仮イベントが作成される。このことから、ステップＳ１０４では、仮イベント間でも経路識別コードの値が同じものの有無も同様に判定している。複数の仮イベントが同じ値の経路識別コードを持っていれば、そのうちの一つ、或いは複数の仮イベントを比較イベントとして扱っている。それにより、既に作成したイベント間では経路識別コードの値が一致しないようにさせている（図１０、或いは図１１等参照）。
【０１７０】
ステップＳ１０６では、比較イベントと仮イベントの総遅延時間を比較して優先度を決定する。その優先度は、モードが最大遅延モードであれば、比較イベントと仮イベントのなかで総遅延時間が大きいほうが高いこととなり、それが最小遅延モードであればその逆となる。そのように優先度を決定した後はステップＳ１０７に移行する。
【０１７１】
ステップＳ１０７では、仮イベントのほうが優先度が高いか否か判定する。その仮イベントに高い優先度を設定していた場合、判定はＹＥＳとなり、ステップＳ１０８で仮イベントの内容を比較イベントの内容に置き換えた後、言い換えれば比較イベントを持つ経路を、仮イベントを作成した経路にまとめた後、一連の処理を終了する。そうでない場合には、判定はＮＯとなり、ステップＳ１０９で仮イベントの内容を破棄した後、言い換えれば仮イベントを作成した経路を、比較イベントを持つ経路にまとめた後、一連の処理を終了する。
【０１７２】
このようにして、本実施の形態では、経路探索のためのデータパスのトレースを行いながら、経路識別コードの値が同じ経路はそれが合流するピンのイベントを作成する段階で優先度が最も高い経路にまとめている。
【０１７３】
図３１は、上記ステップＳ１０２として実行される仮イベントの内容作成処理のフローチャートである。次にその内容作成処理について詳細に説明する。
先ず、ステップＳ１１１では、経路識別コードの値を決定する経路識別コードの決定処理を実行する。その次に移行するステップＳ１１２では、前段のイベントや経路の総遅延時間などを設定する処理を実行する。一連の処理はその後に終了する。
【０１７４】
図３１は、上記ステップＳ１１１として実行される経路識別コードの決定処理のフローチャートである。次に図３１を参照して、その決定処理について詳細に説明する。
【０１７５】
先ず、ステップＳ１２１では、前段のイベントを持つピンが、設定された経路条件中で指定されているピンか否か判定する。上述したように、経路条件中で指定されたピンにはフラグを付加している。このことから、そのピンにフラグが付加されていた場合、判定はＹＥＳとなってステップＳ１２２に移行する。そうでない場合には、判定はＮＯとなってステップＳ１２３に移行する。
【０１７６】
ステップＳ１２２では、直前のピンにフラグが付加されていることから、既存でない値を経路識別コードに設定する。他方のステップＳ１２３では、経路識別コードの値として、前段のイベントが持つ経路識別コードと同じ値を設定する。そのようにして既存でない値の経路識別コード、或いは前段のイベントと同じ値の経路識別コードを設定した後に一連の処理を終了する。
【０１７７】
図２１に示すタイミング解析フローでステップＳ３として実行されるデータパストレース処理では、上述したような各種サブルーチン処理が実行される。それにより、設定した経路条件で区別しつつ、セットアップタイムチェックやホールドタイムチェックといったタイミング解析を行ううえで用いるデータ経路をモード別に抽出するようになっている。
【０１７８】
上記タイミング解析フローのステップＳ４のタイミングチェック処理は、ステップＳ１のクロックパストレース処理、及びステップＳ３のデータパストレース処理をそれぞれ実行した後に実行される。次に、そのタイミングチェック処理について、図３３に示すそのフローチャートを参照して詳細に説明する。
【０１７９】
上述したように、タイミング解析では、データ信号の送り側のセルが持つクロックピンへの経路、それの受け側のセルが持つクロックピンへの経路、及びそのデータ信号が伝搬する経路の組み合わせ全てでチェックを行う必要がある。このことから、タイミングチェック処理では、それら経路の組み合わせのなかから選択する組み合わせを順次、変更しつつ、タイミングチェックを行うようになっている。
【０１８０】
先ず、ステップＳ１３１では、データ信号の送り側のセルが持つクロックピンへの経路、それの受け側のセルが持つクロックピンへの経路、及びそのデータ信号が伝搬する経路の組み合わせのなかから、タイミングチェックを行っていない一つの組み合わせを選択する。ここでは、選択した組み合わせはケースと呼ぶことにする。
【０１８１】
ステップＳ１３１に続くステップＳ１３２では、そのケースのデータ経路が満たす経路条件や、送り側、受け側の各セルへのクロック経路の組み合わせから特定される、タイミングチェックを行ううえでの条件を考慮してタイミングチェックを行う。その後はステップＳ１３３に移行する。
【０１８２】
ステップＳ１３３では、今回、チェックしたケースは既にチェックしたケースよりタイミング的に厳しいか否か判定する。今回、チェックしたケースがタイミング的にこれまでで最悪であった場合、判定はＹＥＳとなり、ステップＳ１３４に移行して、そのケースやタイミングチェックで求めた値、及びデータ経路が満たす経路条件などを記録した後、ステップＳ１３５に移行する。その記録の際、既に記録されているものがあれば上書きする。そうでない場合には、判定はＮＯとなってステップＳ１３５に移行する。
【０１８３】
ステップＳ１３５では、経路の組み合わせのなかでタイミングチェックしていない組み合わせがあるか否か判定する。全ての組み合わせでタイミングチェックを行った場合、判定はＮＯとなり、ステップＳ１３６に移行して、記録されているタイミング的に１番厳しいケースやタイミングチェックで求めた値、データ経路が満たす経路条件などをチェック結果として特定した後、一連の処理を終了する。そうでない場合には、判定はＮＯとなって上記ステップＳ１３１に戻り、経路の組み合わせのなかから別のケースを選択する。
【０１８４】
上記タイミングチェック処理に続けて実行される図２１のステップ５では、ステップＳ１３６で特定したチェック結果を出力装置３４等に出力する。それにより、ユーザにタイミングチェックの結果が通知されることになる。
【０１８５】
通常、送り側のセルと受け側のセルの組み合わせは複数、存在している。受け側のセルが同時に送り側のセルであることもある。このことから、特に詳細な説明は省略するが、上述のタイミングチェック処理は、そのような組み合わせ毎に実行するようになっている。
【０１８６】
図３４は、図２１に示すタイミング解析フローでステップＳ６として実行されるパルス幅チェック用トレース処理のフローチャートである。次に図３４を参照して、そのトレース処理について詳細に説明する。
【０１８７】
先ず、ステップＳ１４１では、始点として指定されたクロックソースから出力されるクロック信号の到達する範囲のピンを深さ優先探索などの手法により特定する処理を実行する。その次に移行するステップＳ１４２では、特定した範囲内に存在するピンを始点のピンから近い順に並べ替えて処理順とする処理を実行する。
【０１８８】
ステップＳ１４２に続くステップＳ１４３では、決定した処理順に従って、ピンにイベントを作成していく処理５を実行する。それにより、各ピンにイベントを作成した後、一連の処理を終了する。
【０１８９】
図３５は、上記ステップＳ１４３として実行される処理５のフローチャートである。次に図３５を参照して、その処理５について詳細に説明する。
先ず、ステップＳ１５１では、始点のピンにはその直前のピン（イベント）が存在していないことから、他のピンと区別してイベントを作成する。ここでは、そのイベントである情報テーブルに、前段のイベントを示すデータであるイベント名、直前のクロックソースを示すデータであるイベント名、信号を伝搬している相を示すデータ、及び第１〜第４の総遅延差などを格納している。始点のピンでは、前段のイベントが存在していないために、前段のイベントはないことを示すデータ、直前のクロックソースを示すデータであるイベント名は自身のイベント名、相を示すデータは同相を示すデータ、第１〜第４の総遅延差としては０を格納している。
【０１９０】
ステップＳ１５１に続くステップＳ１５２では、図３４のステップＳ１４２で決定した処理順に従って、到達範囲内のピンを取り出す。次に移行するステップＳ１５３では、取り出したピンのイベントを作成するピンのイベント作成処理を実行する。その後はステップＳ１５４に移行する。
【０１９１】
ステップＳ１５４では、イベントを作成していないピンが存在するか否か判定する。全ての経路を考慮しつつ、全てのピンにイベントを作成した場合、判定はＮＯとなり、ここで一連の処理を終了する。そうでない場合には、判定はＹＥＳとなり、上記ステップＳ１５２に戻ってそれ移行の処理を同様に実行する。
【０１９２】
上記ステップＳ１５２〜Ｓ１５４で形成される処理ループは、ステップＳ１５４の判定がＮＯとなるまで繰り返し実行される。それにより、他の経路探索時と同様に、各ピンに１つ以上のイベントが作成されることになる。
【０１９３】
図３６は、上記ステップＳ１５３として実行されるピンのイベント作成処理のフローチャートである。次に図３６０を参照して、そのイベント作成処理について詳細に説明する。
【０１９４】
先ず、ステップＳ１６１では、現在、処理対象としているピンの前段に位置する全てのピンのイベントを順に取り出す。次に移行するステップＳ１６２では、取り出した前段のイベントからピンに信号が伝搬した場合のイベントの内容を一時領域（メモリ３２、或いは外部記憶装置３５に確保される領域である）に作成して、内容を作成したイベントを仮イベントとする仮イベントの内容作成処理を実行する。それを実行した後はステップＳ１６３に移行する。
【０１９５】
上記仮イベントの内容作成処理では、前段のイベント毎に、前段のイベントを示すイベント名、直前のクロックソースを示すイベント名、及びその直前のクロックソースから信号を伝搬している相を決定し、第１〜第４の総遅延差を算出する。直前のクロックソースや信号の相の決定は、例えば図２５に示す仮イベントの内容作成処理と同様に行っている。第１〜第４の総遅延差については、上述したように、決定した相に応じて、第１〜第４の遅延差、或いは第５〜第８の遅延差を算出し、それら算出した遅延差を、前段のイベントが持つ第１〜第４の総遅延差のなかで加算すべき総遅延差に加算することで算出している。
【０１９６】
ステップＳ１６３では、処理対象のピンに既に作成されたイベントがあるか否か判定する。ステップＳ１６２で作成する仮イベントを含め、処理対象のピンに複数のイベントが作成されている場合、判定はＹＥＳとなってステップＳ１６４に移行する。そうでない場合には、即ち処理対象のピンにイベントは作成されてなく、且つ作成した仮イベントも１つであった場合には、判定はＮＯとなってステップＳ１６６に移行する。
【０１９７】
ステップＳ１６４では、既に作成されているイベントのなかに仮イベントとの間で直前のクロックソース、及びそのクロックソースからの信号の相が同じものがあるか否か判定する。処理対象のピンで合成条件１、及び２を満たす複数の経路が合流している場合、判定はＹＥＳとなってステップＳ１６５に移行する。そうでない場合には、判定はＮＯとなってステップＳ１６６に移行する。
【０１９８】
上記ステップＳ１６１で前段のピンのイベントを複数、取り出していれば、複数の仮イベントが作成される。このことから、ステップＳ１６４では、仮イベント間でも合成条件１、２を満たすものの有無も同様に判定している。それにより、既に作成したイベント間では合成条件１、２を満たしているものは無いようにさせている。
【０１９９】
ステップＳ１６５では、合成条件１、２を満たすイベントの間で第１〜第４の総遅延差をそれぞれ比較し、イベントのなかの１つが持つ第１〜第４の総遅延差を、それらの間で最も値が大きい総遅延差に書き換える。そのようにして、合成条件１、２を満たす複数の経路を１つに合成した後、一連の処理を終了する。他方のステップＳ１６６では、仮イベントをイベントとしてピンに付加する。その後に一連の処理を終了する。
【０２００】
このようにして、本実施の形態では、パルス幅を算出するために用いる第１〜第４の総遅延差を算出しつつ、経路探索のためのデータパスのトレースを行っている。合成条件１、及び２を満たす複数の経路については、それらが合流するピンのイベントを作成する段階で１つにまとめている。
【０２０１】
図２１のステップＳ６のパルス幅チェック用トレース処理の実行後は、ステップＳ７のクロックパルス幅チェック処理が実行される。
そのパルス幅チェック処理では、例えば各経路毎に、その直前のクロックソースから出力されるクロック信号の各種パルス幅を最終的な第１〜第４の総遅延差により変形した後のパルス幅のチェックを行い、パルス幅が最悪となっている経路、その各種パルス幅などをチェック結果として特定するようになっている。そのチェック結果が、それに続くステップＳ５の実行時に出力装置３４等に出力される。それにより、ユーザにパルス幅チェックの結果が通知される。
【０２０２】
なお、本実施の形態では、予め設定された経路条件、選択条件、及び合成条件のなかの１種類の条件を参照して経路探索を行うようになっているが、それらのうちの複種類の条件を参照して経路探索を行うようにしても良い。具体的には例えば経路条件と選択条件、或いは経路条件と合成条件といったような条件を組み合わせ、組み合わされた条件を参照して経路探索を行うようにしても良い。選択条件、及び合成条件については、複数の経路を１つにまとめるうえで満たすべき条件の組み合わせを複数、用意するようにしても良い。
【０２０３】
タイミング解析に用いるデータ経路やクロック経路の探索は、モード別に行っているが、必ずしもモード別に行わなくても良い。モード別に行わないようにした場合、各モードでそれぞれ条件を満たしている複数の経路が同じピンに合流することも有り得る。従って、そのような場合には、条件を満たす複数の経路のなかから１つ以上の経路を選択することになる。
【０２０４】
本実施の形態では、経路探索以外に、その結果を用いたタイミング解析や波形解析のためのシミュレーションも行っているが、そのシミュレーションは、外部装置から経路探索結果を受け取って行うようにしても良い。そのために、経路探索を行う装置（経路探索装置）に本発明を適用しても良い。
【０２０５】
上述したようなシミュレーション（タイミング解析や波形解析など）、或いは経路探索を実現させるようなプログラムは、外部記憶装置３５に搭載された記憶媒体に記憶させるのではなく、可搬記録媒体ＳＭとして、ＣＤ−ＲＯＭやＤＶＤ、或いは光磁気ディスク等に記録させて配布しても良い。或いは、公衆網やＬＡＮ等で用いられる伝送媒体を介して、そのプログラムの一部、若しくは全部を配信するようにしても良い。そのようにした場合には、ユーザはプログラムを取得してコンピュータ（データ処理装置）にロードすることにより、そのコンピュータに本発明を適用させることができる。このことから、記録媒体は、プログラムを配信する装置がアクセスできるものであっても良い。
【０２０６】
（付記１）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索するために用いられる方法であって、
前記始点のピンから前記終点のピンに至る経路のなかで他と区別すべき経路が満たしている条件を設定し、
該設定した条件を満たすか否かにより区別して、該条件によって区別される経路毎に前記始点のピンから前記終点のピンに至る経路の探索を行う、
ことを特徴とする経路探索方法。
（付記２）  前記条件によって同じ種粳と区別される経路が複数、存在している場合、予め定められた選択規則に従って、該複数の経路のなかから１つを選択して残す、
ことを特徴とする付記１記載の経路探索方法。
（付記３）  前記区別は、前記経路が満たす条件の種類、該条件の数、或いは該条件の組み合わせを基に行う、
ことを特徴とする付記１、または２記載の経路探索方法。
（付記４）  前記経路の探索は、前記始点のピンから１つずつ先のピンに進めながら、各ピン毎に、直前に位置しているピンを表すデータ、及び経路識別用の経路識別コードを少なくとも作成していくことで行い、
前記経路識別コードの値は、前記条件によって経路を区別するために、少なくとも、前記条件を満たした後には既存でない値とする、
ことを特徴とする付記１、２、または３記載の経路探索方法。
（付記５）  前記選択規則に従った経路の選択は、前記経路識別コードが一致する経路を対象に行う、
ことを特徴とする付記４記載の経路探索方法。
（付記６）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索するために用いられる方法であって、
前記始点のピンから前記終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路が存在していた場合に、該２つ以上の経路のなかの１つを選択するうえで該２つ以上の経路間で満たすべき条件を設定し、
前記設定した条件を満たす２つ以上の経路はそのなかの１つだけを選択して残しつつ、前記始点のピンから前記終点のピンに至る経路の探索を行う、
ことを特徴とする経路探索方法。
（付記７）  前記条件を満たす２つ以上の経路のなかで遅延時間が最大、或いは最小の経路を選択する、
ことを特徴とする付記６記載の経路探索方法。
（付記８）  前記始点のピンは外部入力、或いは内部生成のクロック信号を出力するクロックソースである、
ことを特徴とする付記６、または７記載の経路探索方法。
（付記９）  前記条件は、前記合流するピンの直前に位置する前記クロックソースが前記２つ以上の経路で一致し、且つ該クロックソースからのクロック信号を伝搬している相が同じであることを含む、
ことを特徴とする付記８記載の経路探索方法。
（付記１０）  前記ピン間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記条件を満たす２つ以上の経路のなかで遅延時間が最大の経路を選択する場合に、前記条件は、該２つ以上の経路が分岐するピンから、該分岐するピンの直後に位置する前記合流するピンまでの区間を対象にして、該２つ以上の経路のうちの１つでパスの最小遅延時間を用いて算出される該区間の遅延時間が、該２つ以上の経路の他の経路でパスの最大遅延時間を用いて算出される該区間の遅延時間以上となる関係を含む、
ことを特徴とする付記７、８、または９記載の経路探索方法。
（付記１１）  前記ピン間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記条件を満たす２つ以上の経路のなかで遅延時間が最小の経路を選択する場合に、前記条件は、該２つ以上の経路が分岐するピンから、該分岐するピンの直後に位置する前記合流するピンまでの区間を対象にして、該２つ以上の経路のうちの１つでパスの最大遅延時間を用いて算出される該区間の遅延時間が、該２つ以上の経路の他の経路でパスの最小遅延時間を用いて算出される該区間の遅延時間以下となる関係を含む、
ことを特徴とする付記７、８、または９記載の経路探索方法。
（付記１２）  前記ピン間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記条件を満たす２つ以上の経路のなかで遅延時間が最大の経路を選択する場合に、前記条件は、該２つ以上の経路が分岐するピンから、該分岐するピンの直後に位置する前記合流するピンまでの区間を対象にして、該２つ以上の経路のうちの１つで該分岐するピンから該合流するピンの直前に位置する他の分岐するピンまではパスの最小遅延時間、該他の分岐するピンから該合流するピンまではピンの最大遅延時間を用いて算出される該区間の遅延時間が、該２つ以上の経路の他の経路でパスの最大遅延時間を用いて算出される該区間の遅延時間以上となる関係を含む、
ことを特徴とする付記７、８、または９記載の経路探索方法。
（付記１３）  前記ピン間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記条件を満たす２つ以上の経路のなかで遅延時間が最小の経路を選択する場合に、前記条件は、該２つ以上の経路が分岐するピンから、該分岐するピンの直後に位置する前記合流するピンまでの区間を対象にして、該２つ以上の経路のうちの１つで該分岐するピンから該合流するピンの直前に位置する他の分岐するピンまではパスの最大遅延時間、該他の分岐するピンから該合流するピンまではピンの最小遅延時間を用いて算出される該区間の遅延時間が、該２つ以上の経路の他の経路でパスの最小遅延時間を用いて算出される該区間の遅延時間以上となる関係を含む、
ことを特徴とする付記７、８、または９記載の経路探索方法。
（付記１４）  前記経路の探索は、前記始点のピンから１つずつ先のピンに進めながら、各ピン毎に、直前に位置しているピンを表すデータ、及び経路識別用の経路識別コードを少なくとも作成していくことで行い、
前記経路識別コードの値は、少なくとも、前記始点以外のクロックソースであるピンの先に進めた後には既存でない値とする、
ことを特徴とする付記８〜１３の何れか１項に記載の経路探索方法。
（付記１５）  前記条件は、前記経路識別コードが一致することを含む、
ことを特徴とする付記１４記載の経路探索方法。
（付記１６）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索するために用いられる方法であって、
前記始点のピンから前記終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路が存在していた場合に、該２つ以上の経路を１つに合成するうえで該２つ以上の経路間で満たすべき条件を設定し、
前記設定した条件を満たす２つ以上の経路は１つに合成しつつ、前記始点のピンから前記終点のピンに至る経路の探索を行う、
ことを特徴とする経路探索方法。
（付記１７）  前記経路の探索は、前記始点のピンから前記終点のピンに向けて１つずつ先のピンに進めながら、各ピン毎に、直前に位置しているピンを表すデータ、及び前記信号の波形解析を行うための解析用情報を少なくとも作成していくことで行い、
前記設定した条件を満たす２つ以上の経路の合成は、該２つ以上の経路でそれぞれ作成される解析用情報をまとめることで行う、
ことを特徴とする付記１６記載の経路探索方法。
（付記１８）  前記始点のピンが外部入力、或いは内部生成のクロック信号を出力するクロックソースであった場合に、前記条件は、前記合流するピンの直前に位置する前記クロックソースが前記２つ以上の経路で一致し、且つ該クロックソースからのクロック信号を伝搬している相が同じであることを含む、
ことを特徴とする付記１６、または１７記載の経路探索方法。
（付記１９）  前記解析用情報は、直前に位置するクロックソースからのクロック信号を伝搬する相を表すデータ、及び該クロック信号のパルス幅を算出するための遅延データを少なくとも含む、
ことを特徴とする付記１７記載の経路探索方法。
（付記２０）  前記パス間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記クロック信号が伝搬する相が前記直前に位置するピンと同じであった場合、該直前に位置するピンとの遅延差として、該クロック信号の立ち上がりから立ち上がりで伝搬するのに要する最大の遅延時間から最小の遅延時間を減算することで算出される始点の遅延差、該クロック信号の立ち上がりから立ち上がりで伝搬するのに要する最大の遅延時間から、該クロック信号の立ち下がりから立ち下がりで伝搬するのに要する最小の遅延時間を減算することで算出される終点の遅延差、該クロック信号の立ち下がりから立ち下がりで伝搬するのに要する最大の遅延時間から、該クロック信号の立ち上がりから立ち上がりで伝搬するのに要する最小の遅延時間を減算することで算出される第３の遅延差、及び該クロック信号の立ち下がりから立ち下がりで伝搬するのに要する最大の遅延時間から最小の遅延時間を減算することで算出される第４の遅延差、の少なくとも１つを算出し、
前記遅延データは、該始点〜第４の遅延差のうちの１つを加算の対象とする総遅延差を１つ以上有し、
前記遅延データの作成は、該始点〜第４の遅延差のなかで算出した遅延差を、前記直前に位置するピンで作成された遅延データのなかで加算すべき総遅延差に加算することで行う、
ことを特徴とする付記１９記載の経路探索方法。
（付記２１）  前記パス間を結ぶパスが最大遅延時間、及び最小遅延時間を持ち、前記クロック信号が伝搬する相が前記直前に位置するピンと逆であった場合、該直前に位置するピンとの遅延差として、該クロック信号の立ち下がりから立ち上がりで伝搬するのに要する最大の遅延時間から最小の遅延時間を減算することで算出される第５の遅延差、該クロック信号の立ち下がりから立ち上がりで伝搬するのに要する最大の遅延時間から、該クロック信号の立ち上がりから立ち下がりで伝搬するのに要する最小の遅延時間を減算することで算出される第６の遅延差、該クロック信号の立ち上がりから立ち下がりで伝搬するのに要する最大の遅延時間から、該クロック信号の立ち下がりから立ち上がりで伝搬するのに要する最小の遅延時間を減算することで算出される第７の遅延差、及び該クロック信号の立ち上がりから立ち下がりで伝搬するのに要する最大の遅延時間から最小の遅延時間を減算することで算出される第８の遅延差、の少なくとも１つを算出し、
前記遅延データは、該第５〜第８の遅延差のうちの１つを加算の対象とする総遅延差を１つ以上有し、
前記遅延データの作成は、該第５〜第８の遅延差のなかで算出した遅延差を、前記直前に位置するピンで作成された遅延データのなかで加算すべき総遅延差に加算することで行う、
ことを特徴とする付記１９記載の経路探索方法。
（付記２２）  前記設定した条件を満たす２つ以上の経路の合成は、該２つ以上の経路でそれぞれ前記遅延データとして作成した遅延差の種類別に、該遅延差が最大、或いは最小の遅延差を選択することで行う、
ことを特徴とする付記２０、または２１記載の経路探索方法。
（付記２３）  前記解析用情報を作成するピンの直前に位置するピンが前記始点のピン以外のクロックソースであった場合、前記相を表すデータは同相を表すデータとし、前記遅延データを構成する総遅延差の値は予め定めた初期値とする、
ことを特徴とする付記１９〜２２の何れか１項に記載の経路探索方法。
（付記２４）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索するために用いられる方法であって、
前記始点のピンから前記終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路が存在していた場合に、該２つ以上の経路を１つに合成するうえで該２つ以上の経路間で満たすべき条件を設定し、
前記始点のピンから１つずつ先のピンに進めながら、各ピン毎に、前記設定した条件を満たす２つ以上の経路が合流するか否か確認し、
該確認によって、前記設定した条件を満たす２つ以上の経路が合流することが判明した場合に、該２つ以上の経路のうちの１つを選択して残しつつ、前記始点のピンから前記終点のピンに至る経路の探索を行う、
ことを特徴とする経路探索方法。
（付記２５）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路の動作検証用のタイミング解析を行うために用いられる方法であって、
予め設定された第１の条件を満たすか否かにより区別しつつ、前記電子回路上でデータ信号が伝搬するデータ経路を探索して前記タイミング解析に用いるデータ経路を抽出し、
予め設定された第２の条件を満たすか否かに応じて、前記電子回路上でクロック信号が伝搬するクロック経路のなかで合流するピンが同じ２つ以上のクロック経路から１つを選択して残しつつ、該クロック信号が伝搬するクロック経路を探索して前記タイミング解析に用いるクロック経路を抽出し、
前記抽出したデータ経路、及びクロック経路のそれぞれの組み合わせ毎に前記タイミング解析を行う、
ことを特徴とするタイミング解析方法。
（付記２６）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路の動作検証用の波形解析を行うために用いられる方法であって、
予め設定された条件を満たすか否かに応じて、前記電子回路上でクロック信号が伝搬するクロック経路のなかで合流するピンが同じ２つ以上のクロック経路の合成、及び該クロック信号の波形解析を行うための解析用情報のピン毎の作成を行いつつ、該クロック信号が伝搬するクロック経路を探索して前記波形解析に用いるクロック経路を抽出し、
前記抽出したクロック経路で作成した前記解析用情報を用いて、該クロック経路を伝搬するクロック信号のパルス幅を確認する波形解析を行う、
ことを特徴とする波形解析方法。
（付記２７）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路の動作検証用のシミュレーションを行う装置であって、
予め設定された第１の条件を満たすか否かにより区別しつつ、前記電子回路上でデータ信号が伝搬するデータ経路を探索することで抽出されたデータ経路を示す始点の経路データを取得する始点の経路データ取得手段と、
予め設定された第２の条件を満たすか否かに応じて、前記電子回路上でクロック信号が伝搬するクロック経路のなかで合流するピンが同じ２つ以上のクロック経路から１つを選択して残しつつ、該クロック信号が伝搬するクロック経路を探索することで抽出されたクロック経路を示す終点の経路データを取得する終点の経路データ取得手段と、
前記始点、及び終点の経路データ取得手段がそれぞれ取得した前記始点、及び終点の経路データを用いて、前記動作検証用のタイミング解析を行うシミュレーション手段と、
を具備することを特徴とする電子回路シミュレーション装置。
（付記２８）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路の動作検証用のシミュレーションを行う装置であって、
予め設定された条件を満たすか否かに応じて、前記電子回路上でクロック信号が伝搬するクロック経路のなかで合流するピンが同じ２つ以上のクロック経路の合成、及び該クロック信号の波形解析を行うための解析用情報のピン毎の作成を行いつつ、該クロック信号が伝搬するクロック経路を探索することで抽出されたクロック経路を示す経路データを取得する経路データ取得手段と、
前記経路データ取得手段が取得した前記経路データで示されるピンの解析用情報を用いて、前記クロック信号のパルス幅を確認する波形解析を行うシミュレーション手段と、
を具備することを特徴とする電子回路シミュレーション装置。
（付記２９）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索する経路探索装置で実行されるプログラムであって、
前記始点のピンから前記終点のピンに至る経路のなかで他と区別すべき経路が満たしている条件を設定する機能と、
前記設定する機能により設定した条件を満たすか否かにより区別して、該条件によって区別される経路毎に前記始点のピンから前記終点のピンに至る経路の探索を行う機能と、
を実現させるプログラム。
（付記３０）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索する経路探索装置で実行されるプログラムであって、
前記始点のピンから前記終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路が存在していた場合に、該２つ以上の経路のなかの１つを選択するうえで該２つ以上の経路間で満たすべき条件を設定する機能と、
前記設定する機能により設定した条件を満たす２つ以上の経路はそのなかの１つだけを選択して残しつつ、前記始点のピンから前記終点のピンに至る経路の探索を行う機能と、
を実現させるプログラム。
（付記３１）  予め設計用に登録された基本素子であるセルを組み合わせて設計された電子回路を対象に、該電子回路上の始点のピンから終点のピンに至る信号の経路を探索する経路探索装置で実行されるプログラムであって、
前記始点のピンから前記終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路が存在していた場合に、該２つ以上の経路を１つに合成するうえで該２つ以上の経路間で満たすべき条件を設定する機能と、
前記設定する機能により設定した条件を満たす２つ以上の経路は１つに合成しつつ、前記始点のピンから前記終点のピンに至る経路の探索を行う機能と、
を実現させるプログラム。
【０２０７】
【発明の効果】
以上説明したように本発明は、始点のピンから終点のピンに至る経路のなかで他と区別すべき経路が満たしている条件を設定し、その設定した条件を満たすか否かにより区別して、その条件によって区別される経路毎に始点のピンから終点のピンに至る経路の探索を行う。このため、満たす条件によって区別される経路の種類別に経路を抽出することができる。
【０２０８】
本発明は、始点のピンから終点のピンに至る経路のなかで合流するピンが同じ２つ以上の経路を対象に、その２つ以上の経路のなかの１つを選択する（或いは合成する）うえでそれらの間で満たすべき条件を設定し、その設定した条件を満たす２つ以上の経路はそのなかの１つだけを選択して残しつつ（或いはそれらを合成しつつ）、始点のピンから終点のピンに至る経路の探索を行う。このため、全ての経路を考慮しつつ、残す必要が考えられない経路を経路探索の段階で排除させることができる。
【０２０９】
上述したようにして行う経路探索では、何れも、シミュレーション（タイミング解析や波形解析など）で考慮する必要が考えられる経路を排除することなく、抽出する経路の数を最小限に抑えることができる。このため、それら経路探索の結果を用いて行うシミュレーションを常に高精度に行うことができ、その処理のために要するメモリ容量の低減や処理時間の短縮も実現させることができる。たとえシミュレーションに用いる経路探索の結果の一つとして用いたとしても、その精度をより向上させることができるだけでなく、メモリ容量の低減や処理時間の短縮の実現にも効果が得られる。
【０２１０】
請求項１に記載の発明では、始点のピンから終点のピンに至る経路を探索する際に、設定された条件を満たすか否かによって経路を区別し、満たしている条件が同じ複数の経路はそのなかの１つを代表させる。このため、必要な経路を残しつつ、抽出する経路の数を低減させることができる。経路は満たす条件によって区別しているため、満たす条件によって処理内容を切り換えることも容易に行うことができる。
【０２１１】
請求項２に記載の発明では、解析結果が最悪となる可能性のある経路は確実に残しつつ、抽出する経路の数を低減させることができる。このため、解析結果の精度を低下させることなく、処理時間の短縮や、その処理に要するメモリ容量の低減を実現させることができる。
【０２１２】
経路を伝搬する信号の波形解析を行うための解析用情報を作成しながら、経路探索を行った場合には、その波形解析をより容易、且つ迅速に行うことができるようになる。
【０２１３】
このようなことから、本発明は、大規模化、経路が複雑化しつつある電子回路の設計を支援するうえで非常に有効である。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明のプログラムの原理構成図である。
【図３】本実施の形態による電子回路シミュレーション装置を搭載したＣＡＤ装置の構成図である。
【図４】セルとピンの関係を説明する図である。
【図５】クロックパス、データパスを説明する図である。
【図６】電子回路上でデータパスによって接続されたピン間の接続関係を示すグラフである。
【図７】図６のグラフにおいて、経路条件中で指定されたピンを示す図である。
【図８】図６のグラフにおいて、データパスを１つ先に進めたときに作成しているイベントを説明する図である。
【図９】図６のグラフにおいて、データパスを２つ先に進めたときに作成しているイベントを説明する図である。
【図１０】図６のグラフにおいて、データパスを３つ先に進めたときに作成しているイベントを説明する図である。
【図１１】図６のグラフにおいて、データパスを最後まで進めたときに作成しているイベントを説明する図である。
【図１２】クロック信号が伝搬する経路を対象にした経路探索方法の原理を説明するための図である（その１）。
【図１３】クロック信号が伝搬する経路を対象にした経路探索方法の原理を説明するための図である（その２）。
【図１４】クロック信号が伝搬する経路を対象にした経路探索方法の原理を説明するための図である（その３）。
【図１５】クロック信号が伝搬する経路を対象にした経路探索例を説明するための図である（その１）。
【図１６】クロック信号が伝搬する経路を対象にした経路探索例を説明するための図である（その２）。
【図１７】クロック信号が伝搬する経路を対象にした経路探索例を説明するための図である（その３）。
【図１８】クロック信号が伝搬する経路を対象にした経路探索例を説明するための図である（その４）。
【図１９】経路探索によって抽出された経路を説明する図である。
【図２０】パルス幅チェック用の経路探索を説明するための図である。
【図２１】タイミング解析フローを示す図である。
【図２２】クロックパストレース処理のフローチャートである。
【図２３】処理３のフローチャートである。
【図２４】ピンのイベント作成処理のフローチャートである。
【図２５】仮イベントの内容作成処理のフローチャートである。
【図２６】経路識別コード、直前のクロックソースの決定処理のフローチャートである。
【図２７】信号伝搬の相決定処理のフローチャートである。
【図２８】データパストレース処理のフローチャートである。
【図２９】処理４のフローチャートである。
【図３０】処理４におけるピンのイベント作成処理のフローチャートである。
【図３１】Ｓ１０２の仮イベントの内容作成処理のフローチャートである。
【図３２】経路識別コードの決定処理のフローチャートである。
【図３３】タイミングチェック処理のフローチャートである。
【図３４】パルス幅チェック用トレース処理のフローチャートである。
【図３５】処理５のフローチャートである。
【図３６】処理５におけるピンのイベント作成処理のフローチャートである。
【図３７】タイミング解析を説明するための図である。
【符号の説明】
１１    電子回路シミュレーション装置
１２    経路探索装置
１３    タイミング解析手段
１４    クロック経路探索手段
１５    データ経路探索手段
１６    パルス幅チェック用経路探索手段
２１    プログラム
２２    クロック経路探索用ルーチン
２３    データ経路探索用ルーチン
２４    パルス幅チェック用経路探索ルーチン
２５〜２７    条件群
ＤＢ１    ライブラリ
ＤＢ２    ネットリスト
ＤＢ３    配線長データベース
【図１】
0003987302.tif 000002
【図２】
0003987302.tif 000003
【図３】
0003987302.tif 000004
【図４】
0003987302.tif 000005
【図５】
0003987302.tif 000006
【図６】
0003987302.tif 000007
【図７】
0003987302.tif 000008
【図８】
0003987302.tif 000009
【図９】
0003987302.tif 000010
【図１０】
0003987302.tif 000011
【図１１】
0003987302.tif 000012
【図１２】
0003987302.tif 000013
【図１３】
0003987302.tif 000014
【図１４】
0003987302.tif 000015
【図１５】
0003987302.tif 000016
【図１６】
0003987302.tif 000017
【図１７】
0003987302.tif 000018
【図１８】
0003987302.tif 000019
【図１９】
0003987302.tif 000020
【図２０】
0003987302.tif 000021
【図２１】
0003987302.tif 000022
【図２２】
0003987302.tif 000023
【図２３】
0003987302.tif 000024
【図２４】
0003987302.tif 000025
【図２５】
0003987302.tif 000026
【図２６】
0003987302.tif 000027
【図２７】
0003987302.tif 000028
【図２８】
0003987302.tif 000029
【図２９】
0003987302.tif 000030
【図３０】
0003987302.tif 000031
【図３１】
0003987302.tif 000032
【図３２】
0003987302.tif 000033
【図３３】
0003987302.tif 000034
【図３４】
0003987302.tif 000035
【図３５】
0003987302.tif 000036
【図３６】
0003987302.tif 000037
【図３７】
0003987302.tif 000038