(57)【要約】  本発明は、非同期式回路において相対的遅延制約が課されたときに、素子または配線の遅延にばらつきがある場合であっても、好適なタイミング設計と高い歩留とを両立することを目的とする。回路設計装置１００において、回路設計記述を参照して回路を生成する論理合成部１１１と、回路におけるパスの遅延時間の確率分布を求める統計的タイミング解析部１１２と、相対的遅延制約が課された制約付パスのそれぞれにおける同一起点からの遅延時間の確率分布に基づいて、相対的遅延制約の充足率を求める相対的遅延制約充足率計算部１１３と、充足率が所定比率に達しない場合、制約付パスの遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更部１１７と、変更後確率分布に従うように回路の構成を変更する論理回路構成変更部１１４と、を備える（図１）。
2008133116.tif 000002
【特許請求の範囲】
【請求項１】
互いの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された複数のパスを含む回路の設計装置であって、
前記回路に含まれる各パスに対する遅延時間の確率分布を求める統計的タイミング解析部と、
前記相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）の各パスおける単一の起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算部と、
前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスに対する遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更部と、
前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更部と、
を備えたことを特徴とする回路設計装置。
【請求項２】
回路設計記述を参照して前記回路を生成する論理合成部を備えたことを特徴とする、請求項１に記載の回路設計装置。
【請求項３】
前記統計的タイミング解析部、前記相対的遅延制約充足率計算部、前記パス遅延確率分布変更部、前記論理回路構成変更部を繰り返し作動させて前記充足率が前記所定比率に達するように制御する制御部を備えたことを特徴とする、請求項１又は２に記載の回路設計装置。
【請求項４】
前記制御部が、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスに対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対のうち遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスに対する遅延時間を長くするように遅延時間の確率分布を変更することを特徴とする、請求項３に記載の回路設計装置。
【請求項５】
前記相対的制約充足率計算部が、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスにおける信号伝達が完了し、かつ、前記制約付パス対のうち遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求めるように構成されたことを特徴とする、請求項１又は２に記載の回路設計装置。
【請求項６】
前記制約付パス対の各パスに対する遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求めるように構成されたことを特徴とする、請求項５に記載の回路設計装置。
【請求項７】
前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする、請求項４に記載の回路設計装置。
【請求項８】
前記統計的タイミング解析部が、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求めるように構成されたことを特徴とする、請求項１又は２に記載の回路設計装置。
【請求項９】
前記統計的タイミング解析部が、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させるように構成されたことを特徴とする、請求項８に記載の回路設計装置。
【請求項１０】
前記統計的タイミング解析部が、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算するように構成されたことを特徴とする、請求項９に記載の回路設計装置。
【請求項１１】
前記論理合成部が、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成するように構成され、
前記タイミング解析部が、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求めるように構成されるとともに、
前記ネットリストにおける素子の配置と素子間の配線を行う配置配線部と、
前記回路の物理的構成を変更する配置配線変更部と、を備えたことを特徴とする、請求項２に記載の回路設計装置。
【請求項１２】
互いの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された複数のパスを含む回路の設計方法であって、
（ａ）回路設計記述に基づいて前記回路を生成する論理合成工程と、
（ｂ）前記回路含まれる各パスに対する遅延時間の確率分布を求める統計的タイミング解析工程と、
（ｃ）相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）の各パスにおける単一の起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算工程と、
（ｄ）前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスに対する遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更工程と、
（ｅ）前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更工程と、
を含むことを特徴とする回路設計方法。
【請求項１３】
（ｆ）前記充足率が前記所定比率に達するまで前記工程（ｂ）ないし（ｅ）を繰り返す工程を含むことを特徴とする、請求項１２に記載の回路設計方法。
【請求項１４】
前記繰り返し工程（ｆ）において、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスに対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対のうち遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスに対する遅延時間を長くするように遅延時間の確率分布を変更することを特徴とする、請求項１３に記載の回路設計方法。
【請求項１５】
前記相対的制約充足率計算工程（ｃ）において、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスにおける信号伝達が完了し、かつ、前記制約付パス対のうち飛燕時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求めることを特徴とする、請求項１２に記載の回路設計方法。
【請求項１６】
前記相対的制約充足率計算工程（ｃ）において、前記制約付パス対の各パスの遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求めることを特徴とする、請求項１５に記載の回路設計方法。
【請求項１７】
前記パス遅延確率分布変更工程（ｄ）における前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする、請求項１４に記載の回路設計方法。
【請求項１８】
前記統計的タイミング解析工程（ｂ）において、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求めることを特徴とする、請求項１２に記載の回路設計方法。
【請求項１９】
前記統計的タイミング解析工程（ｂ）において、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させることを特徴とする、請求項１８に記載の回路設計方法。
【請求項２０】
前記統計的タイミング解析工程（ｂ）において、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算することを特徴とする、請求項１９に記載の回路設計方法。
【請求項２１】
前記論理合成工程（ａ）において、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成し、
前記タイミング解析工程（ｂ）において、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求め、
前記論理回路構成変更工程（ｅ）において、前記ネットリストにおける素子の配置と素子間の配線を行うとともに、
（ｇ）前記回路の物理的構成を変更する配置配線変更工程を含むことを特徴とする、請求項１２に記載の回路設計方法。
【請求項２２】
互いの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された複数のパスを含む回路の設計プログラムであって、
（ａ）回路設計記述に基づいて前記回路を生成する論理合成処理と、
（ｂ）前記回路に含まれる各パスに対する遅延時間の確率分布を求める統計的タイミング解析処理と、
（ｃ）前記相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）の各パスにおける単一の起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算処理と、
（ｄ）前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスに対する遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更処理と、
（ｅ）前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更処理と、
をコンピュータに実行させることを特徴とする回路設計プログラム。
【請求項２３】
（ｆ）前記充足率が前記所定比率に達するまで前記処理（ｂ）ないし（ｅ）を繰り返す処理をコンピュータに実行させることを特徴とする、請求項２２に記載の回路設計プログラム。
【請求項２４】
前記繰り返し処理（ｆ）において、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスに対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対のうち遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスに対する遅延時間を長くするよう遅延時間の確率分布を変更する処理をコンピュータに実行させることを特徴とする、請求項２３に記載の回路設計プログラム。
【請求項２５】
前記相対的制約充足率計算処理（ｃ）において、前記制約付パス対のうち遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパスにおける信号伝達が完了し、かつ、前記制約付パス対のうち遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求める処理をコンピュータに実行させることを特徴とする、請求項２２に記載の回路設計プログラム。
【請求項２６】
前記相対的制約充足率計算処理（ｃ）において、前記制約付パス対の各パスの遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求める処理をコンピュータに実行させることを特徴とする、請求項２５に記載の回路設計プログラム。
【請求項２７】
前記パス遅延確率分布変更処理（ｄ）における前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする、請求項２４に記載の回路設計プログラム。
【請求項２８】
前記統計的タイミング解析処理（ｂ）において、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求める処理をコンピュータに実行させることを特徴とする、請求項２２に記載の回路設計プログラム。
【請求項２９】
前記統計的タイミング解析処理（ｂ）において、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させる処理をコンピュータに実行させることを特徴とする、請求項２８に記載の回路設計プログラム。
【請求項３０】
前記統計的タイミング解析処理（ｂ）において、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算する処理をコンピュータに実行させることを特徴とする、請求項２９に記載の回路設計プログラム。
【請求項３１】
前記論理合成処理（ａ）において、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成し、
前記タイミング解析処理（ｂ）において、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求め、
前記論理回路構成変更処理（ｅ）において、前記ネットリストにおける素子の配置と素子間の配線を行うとともに、
（ｇ）前記回路の物理的構成を変更する配置配線変更処理をコンピュータに実行させることを特徴とする、請求項２２に記載の回路設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本願は、先の日本特許出願２００７−１１４３８２号（２００７年４月２４日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は回路設計装置、回路設計方法および回路設計プログラムに関し、特に回路素子や配線の遅延（遅延時間）のばらつきを考慮した回路設計装置、回路設計方法および回路設計プログラムに関する。
【背景技術】
【０００２】
近年、微細化により、素子や配線の遅延のばらつきが増大しているため、集積回路のタイミング設計が困難になってきている。【０００３】
設計上は同一の素子や配線でも、製造時に異なるチップ上に実装された素子や配線の間で寸法や不純物濃度などの特性値にばらつきが生じ、その結果として、素子や配線の遅延値（遅延時間）にばらつきが生じる。【０００４】
従来のタイミング設計方法では、素子や配線のばらつき範囲内での最大遅延値と最小遅延値が用いられ、回路遅延（すなわち回路当りの遅延時間）の最大値あるいは最小値は当該回路内の素子や配線の最大遅延値あるいは最小遅延値から計算される。【０００５】
このとき、回路遅延のばらつきは素子や配線の遅延のばらつきが累積されたものとなる。【０００６】
【特許文献１】特開２００２−２２２２３２号公報
【特許文献２】特開２００６−２７７３５９号公報
【非特許文献１】ジェンス・スパーソ（Ｊｅｎｓ  Ｓｐａｒｓｏ）、スティーブ・ファーバー（Ｓｔｅｖｅ  Ｆｕｒｂｅｒ）著「非同期式回路設計の原理（Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ａｓｙｎｃｈｒｏｎｏｕｓ Ｃｉｒｃｕｉｔ  Ｄｅｓｉｇｎ）」、クルーワー学術出版（Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ）、２００１年、ｐｐ．１６−２７
【発明の開示】
【発明が解決しようとする課題】
【０００７】
以上の特許文献１、２並びに非特許文献１の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。
回路内の素子や配線によって、遅延が期待値よりも大きいものと小さいものとが混在するため、ほとんどの場合、素子や配線の遅延のばらつきは相殺される。【０００８】
そのため、上述の（従来のタイミング設計方法における）回路遅延計算では、回路遅延のばらつきが実際に製造されたチップで起こりうるばらつきよりも大きく（すなわち過大に）見積もられていることになるため、回路遅延が必要以上に大きくまたは小さく見積もられる場合がある。【０００９】
回路遅延が必要以上に大きく見積もられた場合、タイミング設計で課される回路遅延制約が必要以上に厳しい場合に相当するため、タイミング設計の収束性が低下する（すなわち、回路遅延制約を充足する回路の設計に要する期間が増大する）。【００１０】
一方、回路遅延が必要以上に小さく見積もられた場合、設計上はタイミング制約を満たしているにもかかわらず、製造されたチップの多くがタイミング制約を満たさないため、製造歩留が低下する。【００１１】
ばらつきが増大した場合のタイミング設計としては、統計的タイミング解析手法を用いる設計と非同期式回路設計が挙げられる。【００１２】
統計的タイミング解析手法とは、素子や配線および回路の遅延を単一の実数値ではなく確率分布として扱い、回路遅延の計算を素子や配線の遅延値の確率密度関数に対する統計的演算によって行うタイミング解析手法である（特許文献１、２）。【００１３】
統計的タイミング解析手法をタイミング設計で用いることにより、ばらつきを考慮した回路遅延の見積りが正確に行えるようになり、タイミング設計の収束性と製造歩留まりの維持の両立が可能となる。【００１４】
非同期式回路とは、回路内のラッチやフリップ・フロップの動作タイミングの制御を、クロック信号ではなくハンドシェイク信号を用いて行う方式の回路である。【００１５】
同期式回路では全てのラッチやフリップ・フロップがクロック信号に合わせて一斉に駆動されるのに対して、非同期式回路ではデータの送信側・受信側の関係にあるラッチやフリップ・フロップの間でデータ受理の要求と完了を通知する一対のハンドシェイク信号の通信が行われて、それぞれのラッチやフリップ・フロップはハンドシェイク信号の状態に応じて独自のタイミングで駆動される（非特許文献１）。【００１６】
非同期式回路は、ハンドシェイク信号が指定の順序で遷移する限りは遷移の間に要する時間が長くなっても正しく動作するため、遅延値のばらつきが大きくなってもタイミング設計が容易である。【００１７】
非同期式回路のタイミング設計では、同期式回路とは異なり、回路内の複数のパスの遅延の相対的大小関係（以下、「相対的遅延制約」とする。）を満たすように制約下の複数パスを含む回路の最適化が行われる。【００１８】
例えば、非同期式回路の一方式である束データ方式による設計の場合、データパスの遅延値よりも対応するハンドシェイク線の一方の遅延値が大きくなければならないという相対的遅延制約が課される。【００１９】
また、ＱＤＩ（Ｑｕａｓｉ  Ｄｅｌａｙ  Ｉｎｓｅｎｓｉｔｉｖｅ）遅延モデルによる回路方式の場合、回路内の分岐点から分岐先までの遅延がほぼ等しくなければならないという相対的遅延制約が課される。【００２０】
これらの相対的遅延制約を満たすために、相対的遅延制約の課されているパスのうちの一部の遅延の減少と一部の遅延の増大を並行して行うような回路最適化が行われる。【００２１】
同期式回路の場合はデータパス回路の遅延がクロック・サイクル時間よりも短くなるようにするタイミング設計が行われ、複数のパスの遅延の間での相対関係が制約条件として課されることがないため、相対的遅延制約は非同期式回路のタイミング設計特有の設計制約である。【００２２】
以上のように、非同期式回路の設計においてもタイミング設計が必要であるので、非同期式回路のタイミング設計においても前述の素子や配線の遅延値のばらつきを考慮する必要がある。【００２３】
非同期式設計技術において遅延値のばらつきが拡大しても歩留を向上させるための単純な方法として、相対的遅延制約を満たすようにマージンを入れて、タイミング設計を行うことが挙げられる。【００２４】
例えば、束データ方式の非同期式回路では、データパスと対応するハンドシェイク線のうちの要求線の間に、データパス遅延が要求線遅延よりも小さくなければならないという制約がある。【００２５】
束データ方式の非同期式回路のばらつきを考慮したタイミング設計を行う場合、データパス遅延と要求線遅延との差分に所定のマージンを入れて、ばらつきによってデータパス遅延が大きくなるか要求線遅延が小さくなるかのいずれが起こっても相対的遅延制約が満たされるようにして歩留を向上させる。【００２６】
その一方で、歩留向上のための過剰なタイミングマージンが非同期式回路の処理速度の低下につながるという問題がある。【００２７】
束データ方式では、非同期式回路の処理速度が最も長いハンドシェイク信号遅延により決定されるため、ハンドシェイク信号線へのタイミングマージンの挿入は処理速度を低下させる。【００２８】
以上により、素子や配線の遅延値のばらつきが増大しても、処理速度を必要以上に低下させることなく歩留の確保や向上を行うことのできる非同期式回路のタイミング設計方法が必要となる。【００２９】
従来技術の問題点は、素子や配線の遅延値のばらつきが大きい場合に、非同期式集積回路の設計において歩留と性能の両立が困難であるという点である。【００３０】
その理由は、従来のばらつき対応のタイミング設計手法は同期式回路の設計に対するものであって非同期式回路特有の相対的遅延制約を満たすようなタイミング設計を考慮しておらず、従来の非同期式集積回路の設計手法は遅延値のばらつきを考慮してのタイミング設計を行わないためである。【００３１】
したがって、非同期式回路において相対的遅延制約が課されたときに、素子または配線の遅延にばらつきがある場合であっても、好適なタイミング設計と高い歩留とを両立することのできる回路設計装置、回路設計方法および回路設計プログラムを提供することが課題となる。
【課題を解決するための手段】
【００３２】
本発明の第１の視点に係る回路設計装置は、複数のパスの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された回路（すなわち、互いの遅延時間の長短について制約が課された複数のパスを含む回路）の設計装置であって、回路設計記述を参照して前記回路を生成する論理合成部と、前記回路におけるパスの遅延時間の確率分布を求める統計的タイミング解析部と、前記相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）の各パスにおける同一（すなわち単一の）起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算部と、前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスの遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更部と、前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更部と、を備えたことを特徴とする。【００３３】
本発明の第２の視点に係る回路設計方法は、複数のパスの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された回路の設計方法であって、（ａ）回路設計記述に基づいて前記回路を生成する論理合成工程と、（ｂ）前記回路におけるパスの遅延時間の確率分布を求める統計的タイミング解析工程と、（ｃ）相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）のそれぞれのパスにおける同一（すなわち単一の）起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算工程と、（ｄ）前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスの遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更工程と、（ｅ）前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更工程と、を含むことを特徴とする。【００３４】
本発明の第３の視点に係る回路設計プログラムは、複数のパスの遅延時間の長短について制約（以下「相対的遅延制約」という。）が課された回路の設計プログラムであって、（ａ）回路設計記述に基づいて前記回路を生成する論理合成処理と、（ｂ）前記回路におけるパスの遅延時間の確率分布を求める統計的タイミング解析処理と、（ｃ）前記相対的遅延制約が課されたパスの対（以下「制約付パス対」という。）のそれぞれのパスにおける同一（すなわち単一の）起点からの遅延時間の確率分布に基づいて、前記相対的遅延制約の充足率を求める相対的遅延制約充足率計算処理と、（ｄ）前記充足率が所定の比率に達しない場合、前記制約付パス対の各パスの遅延時間の確率分布を変更して変更後確率分布とするパス遅延確率分布変更処理と、（ｅ）前記変更後確率分布に従うように前記回路の構成を変更する論理回路構成変更処理と、をコンピュータに実行させることを特徴とする。【００３５】
第１の展開形態に係る回路設計装置は、前記統計的タイミング解析部、前記相対的遅延制約充足率計算部、前記パス遅延確率分布変更部、前記論理回路構成変更部を繰り返し作動させて前記充足率が前記所定比率に達するように制御する制御部を備えたことを特徴とする。【００３６】
第２の展開形態に係る回路設計装置は、前記制御部が、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパス（すなわち、遅延時間が他方のパスよりも短くなるように前記相対的遅延制約が課されたパス）に対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対の他方のパス（すなわち、遅延時間が他方のパスよりも長くなるように前記相対的遅延制約が課されたパス）の遅延時間を長くするよう遅延時間の確率分布を変更することを特徴とする。【００３７】
第３の展開形態に係る回路設計装置は、前記相対的制約充足率計算部が、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパスにおける信号伝達が完了し、かつ、前記制約付パス対の他方のパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求めるように構成されたことを特徴とする。【００３８】
第４の展開形態に係る回路設計装置は、前記制約付パス対のそれぞれのパスの遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求めるように構成されたことを特徴とする。【００３９】
第５の展開形態に係る回路設計装置は、前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする。【００４０】
第６の展開形態に係る回路設計装置は、前記統計的タイミング解析部が、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求めるように構成されたことを特徴とする。【００４１】
第７の展開形態に係る回路設計装置は、前記統計的タイミング解析部が、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させるように構成されたことを特徴とする。【００４２】
第８の展開形態に係る回路設計装置は、前記統計的タイミング解析部が、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算するように構成されたことを特徴とする。【００４３】
第９の展開形態に係る回路設計装置は、前記論理合成部が、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成するように構成され、前記タイミング解析部が、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求めるように構成されるとともに、前記ネットリストにおける素子の配置と素子間の配線を行う配置配線部と、前記回路の物理的構成を変更する配置配線変更部と、を備えたことを特徴とする。【００４４】
第１０の展開形態に係る回路設計方法は、（ｆ）前記充足率が前記所定比率に達するまで前記工程（ｂ）ないし（ｅ）を繰り返す工程を含むことを特徴とする。【００４５】
第１１の展開形態に係る回路設計方法は、前記繰り返し工程（ｆ）において、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパスに対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対の他方のパスの遅延時間を長くするよう遅延時間の確率分布を変更することを特徴とする。【００４６】
第１２の展開形態に係る回路設計方法は、前記相対的制約充足率計算工程（ｃ）において、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパスにおける信号伝達が完了し、かつ、前記制約付パス対の他方のパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求めることを特徴とする。【００４７】
第１３の展開形態に係る回路設計方法は、前記相対的制約充足率計算工程（ｃ）において、前記制約付パス対のそれぞれのパスの遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求めることを特徴とする。【００４８】
第１４の展開形態に係る回路設計方法は、前記パス遅延確率分布変更工程（ｄ）における前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする。【００４９】
第１５の展開形態に係る回路設計方法は、前記統計的タイミング解析工程（ｂ）において、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求めることを特徴とする。【００５０】
第１６の展開形態に係る回路設計方法は、前記統計的タイミング解析工程（ｂ）において、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させることを特徴とする。【００５１】
第１７の展開形態に係る回路設計方法は、前記統計的タイミング解析工程（ｂ）において、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算することを特徴とする。【００５２】
第１８の展開形態に係る回路設計方法は、前記論理合成工程（ａ）において、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成し、前記タイミング解析工程（ｂ）において、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求め、前記論理回路構成変更工程（ｅ）において、前記ネットリストにおける素子の配置と素子間の配線を行うとともに、（ｇ）前記回路の物理的構成を変更する配置配線変更工程を含むことを特徴とする。【００５３】
第１９の展開形態に係る回路設計プログラムは、（ｆ）前記充足率が前記所定比率に達するまで前記処理（ｂ）ないし（ｅ）を繰り返す処理をコンピュータに実行させることを特徴とする。【００５４】
第２０の展開形態に係る回路設計プログラムは、前記繰り返し処理（ｆ）において、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパスに対する遅延時間を短くするように遅延時間の確率分布を変更して前記充足率を求め、前記充足率が前記所定比率に達しない場合、前記制約付パス対の他方のパスの遅延時間を長くするよう遅延時間の確率分布を変更する処理をコンピュータに実行させることを特徴とする。【００５５】
第２１の展開形態に係る回路設計プログラムは、前記相対的制約充足率計算処理（ｃ）において、前記制約付パス対のうち遅延時間を相対的に短くすべき一方のパスにおける信号伝達が完了し、かつ、前記制約付パス対の他方のパスにおける信号伝達が未了である同時確率分布に基づいて前記充足率を求める処理をコンピュータに実行させることを特徴とする。【００５６】
第２２の展開形態に係る回路設計プログラムは、前記相対的制約充足率計算処理（ｃ）において、前記制約付パス対のそれぞれのパスの遅延時間の確率分布およびそれらの相関に基づいて前記充足率を求める処理をコンピュータに実行させることを特徴とする。【００５７】
第２３の展開形態に係る回路設計プログラムは、前記パス遅延確率分布変更処理（ｄ）における前記変更後確率分布として、確率分布の特徴を示す統計量を用いることを特徴とする。【００５８】
第２４の展開形態に係る回路設計プログラムは、前記統計的タイミング解析処理（ｂ）において、素子および配線の遅延時間に対する所定の確率密度関数を参照して、前記回路におけるパスの遅延時間の確率分布を求める処理をコンピュータに実行させることを特徴とする。【００５９】
第２５の展開形態に係る回路設計プログラムは、前記統計的タイミング解析処理（ｂ）において、前記回路内の素子、配線およびパスの遅延時間を所定の確率分布モデルに回帰させる処理をコンピュータに実行させることを特徴とする。【００６０】
第２６の展開形態に係る回路設計プログラムは、前記統計的タイミング解析処理（ｂ）において、前記確率分布モデルを正規分布とし、前記確率密度関数の特徴量として期待値および標準偏差を用いて前記回路内のパスの遅延時間を計算する処理をコンピュータに実行させることを特徴とする。【００６１】
第２７の展開形態に係る回路設計プログラムは、前記論理合成処理（ａ）において、非同期式回路設計記述に基づいてゲートレベルのネットリストを生成し、前記タイミング解析処理（ｂ）において、前記ネットリストまたは配置配線情報に基づいてパスの遅延時間の確率分布を求め、前記論理回路構成変更処理（ｅ）において、前記ネットリストにおける素子の配置と素子間の配線を行うとともに、（ｇ）前記回路の物理的構成を変更する配置配線変更処理をコンピュータに実行させることを特徴とする。
【発明の効果】
【００６２】
本発明に係る回路設計装置、回路設計方法または回路設計プログラムにより、非同期式回路において相対的遅延制約が課されたときに、素子または配線の遅延にばらつきがある場合であっても、好適なタイミング設計と高い歩留とを両立することができる。【００６３】
その理由は、統計的タイミング解析により得られる回路内パスの遅延値の確率分布に基づいて相対的遅延制約の充足率を算出することでタイミング歩留を正確に予測し、予測されたタイミング歩留が所定のタイミング歩留制約を満たさない場合、当該制約を満たす場合の相対的遅延制約下のパスの遅延値の確率分布を求め、前記パスの遅延値の確率分布が求めた確率分布になるように回路の論理構成または物理構成を変更することにより、相対的遅延制約下のパスの遅延値の間に設けられるタイミングマージンを必要最小限の値に抑えることができるからである。
【図面の簡単な説明】
【００６４】
【図１】本発明を実施するための最良の形態の構成を示すブロック図である。
【図２】本発明を実施するための最良の形態の動作を示す流れ図である。
【図３】非同期式回路設計記述（すなわち、本発明の実施例に係る回路設計装置における非同期式回路設計記述）の一例である。
【図４】実施例で設計される（すなわち、本発明の実施例に係る回路設計装置によって設計される）非同期式回路の構成図である。
【図５】実施例での非同期式回路の設計（すなわち、本発明の実施例に係る回路設計装置による非同期式回路の設計）過程における相対的遅延制約の充足性判定の図である。
【符号の説明】
【００６５】
１００  回路設計装置
１０１  回路設計記述入力部
１０２  セルライブラリ入力部
１０３  タイミング歩留制約記述入力部
１０４  相対的遅延制約記述入力部
１１１  論理合成部
１１２  統計的タイミング解析部
１１３  相対的遅延制約充足率計算部
１１４  論理回路構成変更部
１１５  配置配線部
１１６  配置配線変更部
１１７  パス遅延確率分布変更部
１９９  ネットリスト・配置配線情報出力部
４００  非同期式回路
４０１、４０２  パス
４１１  ラッチ制御回路のセルによる構成
４２０  データパス回路
４２１  加算器
５００、５０１、５０２、５１０  グラフ
５１１  相対的遅延制約充足領域
【発明を実施するための最良の形態】
【００６６】
本発明の実施の形態に係る回路設計装置１００は、図１を参照すると、論理合成部１１１、統計的タイミング解析部１１２、相対的遅延制約充足率計算部１１３、論理回路構成変更部１１４、配置配線部１１５、配置配線変更部１１６、パス遅延確率分布変更部１１７を備える。【００６７】
論理合成部１１１は、非同期式回路設計記述をゲートレベルのネットリストに変換する。配置配線部１１５は、前記ネットリスト内の素子の配置や素子間の配線を行う。【００６８】
統計的タイミング解析部１１２は、ネットリストまたは配置配線情報に対して、統計的タイミング解析に基づいて回路内パスの遅延計算を行う。【００６９】
相対的遅延制約充足率計算部１１３は、相対的遅延制約が課された回路内パスが当該制約を充足する充足率を計算する。【００７０】
パス遅延確率分布変更部１１７は、充足率が所定のタイミング歩留制約を満たさない場合、充足率がタイミング歩留制約を満たす場合のパスの遅延値の確率分布を変更後確率分布として算出する。【００７１】
論理回路構成変更部１１４または配置配線変更部１１６は、パスの遅延値の確率分布が変更後確率分布となるように、回路の論理構成あるいは物理構成を変更する。【００７２】
以上の構成に基づいて、相対的遅延制約の課されたパスの遅延値の間のタイミングマージンを、所定の歩留を実現する上で必要最小限に抑えることによって、本発明の目的を達成する。【００７３】
本発明の実施形態に係る回路設計システム（本実施形態に係る回路設計装置を有するシステム）ついて図面を参照して詳細に説明する。【００７４】
図１を参照すると、本発明の実施形態に係る回路設計システムは、回路設計装置１００、回路設計記述入力部１０１、セルライブラリ入力部１０２、タイミング歩留制約記述入力部１０３、相対的遅延制約記述入力部１０４、ネットリスト・配置配線情報出力部１９９を備える。【００７５】
回路設計装置１００は、論理合成部１１１、統計的タイミング解析部１１２、相対的遅延制約充足率計算部１１３、論理回路構成変更部１１４、配置配線部１１５、配置配線変更部１１６、パス遅延確率分布変更部１１７を備える。【００７６】
以下、本発明を構成する各手段の動作の概略を述べる。【００７７】
回路設計記述入力部１０１は、ハンドシェイク信号に代表される当該回路内の制御信号の遷移順序と、ラッチやフリップ・フロップの間の論理回路で行われる処理と、制御信号遷移に対してのラッチやフリップ・フロップの制御手順とが記述された非同期式回路設計記述を回路設計装置１００へ入力する。【００７８】
セルライブラリ入力部１０２は、設計対象とされる非同期式回路を構成する素子および配線の論理的情報と物理的情報と延値計算に用いられる情報とが記述されたセルライブラリを回路設計装置１００へ入力する。【００７９】
なお、素子や配線の遅延値のばらつき情報は、セルライブラリ情報の一部として当該セルライブラリ内に記述しておいてもよい。ただし、セルライブラリに基本情報を記述しておいて、当該基本情報に基づいて、論理合成部１１１、統計的タイミング解析部１１２、相対的遅延制約充足率計算部１１３、論理回路構成変更部１１４、配置配線部１１５または配置配線変更部１１６のいずれかによって導出してもよい。【００８０】
タイミング歩留制約記述入力部１０３は、設計対象とされる非同期式集積回路の歩留に関する制約を記述したタイミング歩留制約記述を回路設計装置１００へ入力する。【００８１】
相対的遅延制約記述入力部１０４は、回路内における相対的遅延制約が記述された相対的遅延制約記述を回路設計装置１００へ入力する。【００８２】
ネットリスト・配置配線情報出力部１９９は、回路設計装置１００により設計された非同期式集積回路のネットリスト、素子配置および配線を出力する。【００８３】
論理合成部１１１は、入力された非同期式回路の回路設計記述およびセルライブラリに基づいて、セルライブラリ内に記述されている素子によって構成される回路のゲートレベルのネットリストを生成する。【００８４】
統計的タイミング解析部１１２は、ネットリスト、セルライブラリ、配置配線情報に基づいて、非同期式回路内のパスの遅延値の確率密度関数、または、所定の確率分布モデルによって、その遅延値を特徴づける統計量を算出し、当該パスの統計的遅延情報として出力する。【００８５】
なお、配置配線情報を用いることなく統計的タイミング解析を行うことも可能である。【００８６】
相対的遅延制約充足率計算部１１３は、統計的遅延情報、相対的遅延制約記述、タイミング歩留制約記述に基づいて、相対的遅延制約の充足率がタイミング歩留制約を満たしているか否かを判定する。【００８７】
パス遅延確率分布変更部１１７は、統計的パス遅延値情報と複数の確率変数に対する同時分布(同時確率分布)に対する計算規則に基づいて、相対的遅延制約が課されたパスに対し、タイミング歩留制約を満たすような遅延値の確率密度関数（または確率分布の特徴量）を変更後確率密度関数として求める。【００８８】
論理回路構成変更部１１４は、ネットリスト、統計的遅延情報、タイミング歩留不充足パス情報、相対的遅延制約記述、変更後確率密度関数（または確率分布の特徴量）に基づいて、タイミング歩留不充足パスの遅延値の確率密度関数（または確率分布の特徴量）が変更後確率密度関数（または確率分布の特徴量）となるよう、組合せ最適化、遅延素子の挿入、同一論理で異なる性能の素子への置換等を行い、ネットリストを変更する。【００８９】
配置配線部１１５は、ネットリストおよびセルライブラリから、ネットリスト内の素子を配置するとともに素子間の配線を行い、非同期式回路の配置配線情報を出力する。【００９０】
配置配線変更部１１６は、ネットリスト、配置配線情報、統計的遅延情報、タイミング歩留不充足パス情報、相対的遅延制約記述、確率密度関数（または確率分布の特徴量）に基づいて、タイミング歩留不充足パスの遅延値の確率密度関数（または確率分布の特徴量）が、確率密度関数（または確率分布の特徴量）となるように、回路内素子の同一論理であって異なる遅延の素子との交換、配線長の延長または短縮等を行い、前記ネットリストおよび前記配置配線情報を変更する。【００９１】
次に、図２のフローチャートを参照して、本実施形態に係る回路設計装置１００の動作について詳細に説明する。【００９２】
回路設計装置１００は、回路設計記述入力部１０１、セルライブラリ入力部１０２、タイミング歩留制約記述入力部１０３、相対的遅延制約記述入力部１０４から、それぞれ、回路設計記述、セルライブラリ、タイミング歩留制約記述、相対的遅延制約記述を入力する（ステップＳ１）。【００９３】
論理合成部１１１は、回路設計記述およびセルライブラリから、セルライブラリ内に記述されている素子で構成される当該回路のゲートレベルのネットリストを論理合成する（ステップＳ２）。【００９４】
統計的タイミング解析部１１２は、統計的タイミング解析を行い、ネットリストおよびセルライブラリから、非同期式回路内のパスの遅延値の確率密度関数（または所定の確率分布モデルにおいて遅延値の確率分布を特徴付ける統計量）を当該パスの統計的パス遅延値情報として生成する（ステップＳ３）。【００９５】
ここで、ネットリストは、ステップＳ７の工程前であればステップＳ２により生成されたものを指し、後述のステップＳ７の工程以後であれば変更後のものを指す。【００９６】
相対的遅延制約充足率計算部１１３は、統計的パス遅延値情報、相対的遅延制約記述、タイミング歩留制約記述に基づいて、相対的遅延制約の充足率を求め（ステップＳ４）、タイミング歩留制約を充足しているか否かを判定する（ステップＳ５）。【００９７】
タイミング歩留制約を充足した場合、ステップＳ８へ移り、充足しない場合、ステップＳ６へ移る（ステップＳ５）。【００９８】
パス遅延確率分布変更部１１７は、統計的パス遅延値情報から相対的遅延制約が課されているパスに対して前記タイミング歩留制約を満たす、遅延値の確率密度関数（または確率分布の特徴量）を求める（ステップＳ６）。【００９９】
論理回路構成変更部１１４は、ネットリスト、統計的パス遅延値情報、相対的遅延制約記述、パス遅延値の変更後確率密度関数（または確率分布の特徴量）から、タイミング歩留充足性判定において不充足と判定されたパスの遅延値の確率密度関数（または確率分布の特徴量）が変更後確率密度関数（または確率分布の特徴量）となるように、組合せ最適化、遅延素子の挿入または削除、同一論理で異なる性能の素子への置換によるパス遅延値短縮または延長を行うことによって、当該回路の論理的構成の変更を行い、当該変更を反映するように前記ネットリストの修正を行う（ステップＳ７）。【０１００】
配置配線部１１５は、ネットリストおよびセルライブラリから、ネットリスト内の素子を配置するとともに素子間の配線を行い、非同期式回路の配置配線情報を生成する（ステップＳ８）。【０１０１】
統計的タイミング解析部１１２は、ネットリストおよび配置配線情報から、非同期式回路内のパスの遅延値の確率密度関数（または所定の確率分布モデルにおいて遅延値の確率分布を特徴付ける統計量）を当該パスの統計的遅延情報として生成する（ステップＳ９）。【０１０２】
なお、ネットリストおよび配置配線情報とは、ステップＳ１３の工程前であればステップＳ８により生成されたネットリストおよび配置配線情報をいい、ステップＳ１３の工程以後であれば変更後のネットリストおよび配置配線情報をいう。【０１０３】
相対的遅延制約充足率計算部１１３は、統計的パス遅延値情報、相対的遅延制約記述、タイミング歩留制約記述に基づいて、相対的遅延制約の充足確率が、タイミング歩留制約を充足しているか否かを判定する（ステップＳ１０）。【０１０４】
前記判定の結果がタイミング歩留制約を充足する場合、ステップＳ１４へ移り、充足しない場合、ステップＳ１２へ移る（ステップＳ１１）。【０１０５】
パス遅延確率分布変更部１１７は、統計的パス遅延値情報に基づいて、相対的遅延制約が課されているパスに対して、タイミング歩留制約を満たすような、遅延値の確率密度関数（または確率分布の特徴量）を求める（ステップＳ１２）。【０１０６】
配置配線変更部１１６は、ネットリスト、配置配線情報、統計的パス遅延値情報、タイミング歩留不充足パス情報、相対的遅延制約記述、変更後のパス遅延値の確率密度関数（または確率分布の特徴量）に基づいて、タイミング歩留制約充足性判定において不充足と判定されたパスの遅延値の確率密度関数（または確率分布の統計量）が、変更後のパス遅延値の確率密度関数（または確率分布の特徴量）となるように、同一論理で異なる遅延の素子との交換、配線長の延長または短縮などによって配置配線を変更し、その変更を反映するようにネットリストおよび配置配線情報を修正する（ステップＳ１３）。【０１０７】
最後に、ネットリスト・配置配線情報出力部１９９は、ネットリストおよび配置配線情報を出力し（ステップＳ１４）、処理を終了する。【０１０８】
次に、本実施の形態の効果について説明する。【０１０９】
本実施の形態では、回路設計装置１００は、次のように構成されている。すなわち、論理合成部１１１または配置配線部１１５は、設計対象の非同期式回路のネットリストまたは配置配線情報を生成する。統計的タイミング解析部１１２は、ばらつきを考慮した当該回路内のパスの遅延値を解析する。相対的遅延制約充足率計算部１１３は、前記解析結果における相対的遅延制約の充足率を判定する。前記タイミング歩留制約が不充足の場合、パス遅延確率分布変更部１１７は、当該制約を充足させる場合の前記回路内パス遅延値の確率分布を後述の回路構成変更の目標として設定する。論理回路構成変更部１１４および配置配線変更部１１６は、前記目標を達するように設計対象の非同期式回路の論理構成および物理構成を変更する。【０１１０】
したがって、素子や配線の遅延値のばらつきが大きい場合であっても、非同期式回路特有の複数の回路内パスの遅延値の相対関係に関する制約を所定の確率以上で満たすことにより、所定の歩留を実現することができる。また、前記タイミング歩留制約を充足させる範囲内でタイミングマージンを最小にするように前記目標を設定して当該目標を達するように回路構成の変更を行うことにより、高歩留と高性能を両立する非同期式回路の設計を実現することもできる。
【実施例】
【０１１１】
次に、具体的な実施例を用いて、本発明の実施形態に係る回路設計システムの動作を説明する。【０１１２】
本実施例では、素子や配線の遅延値およびパスの遅延値が正規分布に従うとして、複数の素子や配線やパスの遅延値は互いに独立であるとする。【０１１３】
なお、異なる遅延値の確率分布モデルを用いる場合であっても、複数の素子や配線やパスの遅延値の間に相関関係が存在する場合であっても、確率計算を適切に行うことによって本発明の回路設計装置１００は適切に動作する。【０１１４】
回路設計装置１００は、回路設計記述入力部１０１、セルライブラリ入力部１０２、タイミング歩留制約記述入力部１０３、相対的遅延制約記述入力部１０４により、図３の非同期式回路設計記述、セルライブラリ、タイミング歩留制約記述、相対的遅延制約記述を入力する（ステップＳ１）。【０１１５】
本実施例では、セルライブラリには素子や配線の遅延値のばらつき情報として期待値と標準偏差が記述されているとする。【０１１６】
また、相対的遅延制約記述には、図３のｔｏｐ／ＬＣ１／Ｒｏ１からｔｏｐ／ＬＣ２／Ｒｉ２へのパスの遅延値が、ｔｏｐ／ｄｐ／ａまたはｔｏｐ／ｄｐ／ｂからｔｏｐ／ｄｐ／ｃへのパスの遅延値よりも大きいという制約が記述されているとする。【０１１７】
タイミング歩留制約記述には、前記相対的遅延制約の充足率が０．９９以上であるという制約が記述されているとする。【０１１８】
論理合成部１１１は、図３の非同期式回路設計記述およびセルライブラリから、図４に示す構成を備えた回路のゲートレベルのネットリストを論理合成する（ステップＳ２）。【０１１９】
なお、図４ではラッチ制御モジュール（ＬＣ１、ＬＣ２）のセルによる構成が４１１に示されており、セルはライブラリ内のものであるとする。【０１２０】
同様にラッチ（ａ、ｂ、ｃ）および加算器４２１も、ライブラリ内のセルで構成されているものとする。【０１２１】
統計的タイミング解析部１１２は、ネットリストおよびセルライブラリから、相対的遅延制約が課されたパス４０１、４０２の遅延値の確率分布を求める（ステップＳ３）。ここで、パス４０１はハンドシェイク要求信号線、パス４０２はデータパスである。【０１２２】
本実施例では、パス遅延値も正規分布に従うものと仮定している。ここでは、パス遅延値の確率分布を特徴づける期待値と標準偏差を求めるものとする。パス４０１の遅延値の確率分布は、一例として、図５のグラフ５０１に示される期待値５ｎｓで標準偏差０．５ｎｓの正規分布とし、パス４０２の遅延値の確率分布は、一例として、グラフ５０２に示される期待値６ｎｓで標準偏差０．６ｎｓの正規分布とする。【０１２３】
相対的遅延制約充足率計算部１１３は、相対的遅延制約が課されたパス４０１、４０２の遅延値の確率分布（図５の５０１、５０２）の同時分布５００に対して、相対的遅延制約を満たす相対的遅延制約充足領域５１１について同時分布５００を積分した充足率を求め、充足率がタイミング歩留制約を満たすか否か判定する。【０１２４】
ここで、グラフ５１０は、グラフ５００をｚ軸の方向から見た図である。【０１２５】
グラフ５００を相対的遅延制約充足領域５１１について積分して得られた充足率が、例えば、０．８９６であったとする（ステップＳ４）。この値はタイミング歩留制約０．９９よりも小さいため、タイミング歩留制約は不充足であると判定される（ステップＳ５）。【０１２６】
判定結果がタイミング歩留制約不充足であったため、ステップＳ６へ移る（ステップＳ５）。【０１２７】
パス遅延確率分布変更部１１７は、論理回路構成変更後にタイミング歩留制約を満たす場合のパス４０１、４０２の遅延値の確率分布の特徴量の１つとして期待値を求める。【０１２８】
独立な確率変数の期待値および標準偏差の加法性に基づき、論理最適化によりパス遅延値の期待値がａ倍となる場合、標準偏差は（√ａ）倍になると予測されることから、相対的遅延制約の充足率が前記タイミング歩留制約値である０．９９以上となる場合のパス４０１の遅延値の期待値は５ｎｓの０．８２倍の４．１０ｎｓ、パス４０２の遅延値の期待値は６ｎｓの１．１８倍の７．０８ｎｓとなる（ステップＳ６）。【０１２９】
論理回路構成変更部１１４により、相対的遅延制約が不充足であった図４の回路のパスのうちパス４０２の遅延値削減を試みるため、加算器４２１の論理最適化によって論理回路の構成を変更してネットリストの変更を行う。【０１３０】
このとき、変更後の期待値４．１０ｎｓが図４の回路のパス４０２の遅延値の期待値の最大値制約として設定される。【０１３１】
最大値制約が設定された場合であっても、さらに性能を向上させるため、当該制約を超えて、可能な限りパス４０２の遅延を短縮するように論理回路構成変更を行う（ステップＳ７）。【０１３２】
なお、論理回路構成変更によって最大値制約が満たされるとは限らない。【０１３３】
ステップＳ３に戻り、統計的タイミング解析部１１２は、変更後ネットリストおよびセルライブラリから、相対的遅延制約が課されているパス４０１、４０２の遅延値の確率分布を求める。【０１３４】
論理最適化により、例えば、遅延が短縮されたパス４０２の遅延値の期待値および標準偏差が、それぞれ４．５ｎｓおよび０．４７ｎｓとなったとする。【０１３５】
相対的遅延制約充足率計算部１１３は、図４の相対的遅延制約が課されているパス４０１、４０２の遅延値の同時分布から前記相対的遅延制約を充足する確率を求め、約０．９７２を得たとする。このとき、依然としてタイミング歩留制約値である０．９９よりも小さいため、タイミング歩留制約は不充足であると判定され（ステップＳ５）、ステップＳ６へ移る。【０１３６】
パス遅延確率分布変更部１１７は、論理回路構成変更によるパス４０１の遅延値変更に応じて、次回の論理回路構成変更時における、パス４０２の遅延値の変更後期待値を再計算し、その期待値として６．４８ｎｓを得たとする（ステップＳ６）。【０１３７】
論理回路構成変更部１１４は、前記相対的遅延制約が不充足であった図４の回路のパス４０１、４０２に対して、変更後期待値である６．４８ｎｓを目標に遅延素子追加によるパス４０２の遅延を大きくするように論理回路の構成変更を行い、ネットリストを変更する（ステップＳ７）。【０１３８】
このとき、パス４０１の遅延値の増大は性能の低下を招くため、遅延値が変更後期待値を超える最小値となるように構成変更を行う。【０１３９】
ステップＳ３に戻り、統計的タイミング解析部１１２は、再変更後のネットリストおよびセルライブラリから、相対的遅延制約が課されたパス４０１、４０２の遅延値の確率分布を求める。【０１４０】
その結果、遅延素子追加によって遅延が延長されたパス４０１の遅延値の期待値および標準偏差が、それぞれ６．６ｎｓおよび０．６３ｎｓとなったとする。【０１４１】
相対的遅延制約充足率計算部１１３は、パス４０１、４０２の遅延値の同時分布における相対性遅延制約充足範囲の確率を積分した充足率として約０．９９２を得たとする。この充足率は、タイミング歩留制約値である０．９９以上であるため、タイミング歩留制約が充足されたものと判定され（ステップＳ５）、ステップＳ８へ移る。【０１４２】
配置配線部１１５は、図４の回路の前記修正後ネットリスト内の素子を前記セルライブラリ内の物理情報に基づき配置するとともに当該素子間の配線を行って配置配線情報を生成する（ステップＳ８）。【０１４３】
統計的タイミング解析部１１２は、図４の非同期式回路のネットリストおよび配置配線情報からパス４０１、４０２の遅延値の解析を行った結果、非同期式回路内のパス４０１の遅延値の期待値および標準偏差が４．７５ｎｓおよび０．４９ｎｓの正規分布となり、パス４０２の遅延値が期待値および標準偏差が６．６６ｎｓおよび０．６３ｎｓの正規分布となったとする（ステップＳ９）。【０１４４】
相対的遅延制約充足率計算部１１３が、パス４０１、４０２の遅延値が図４の相対的遅延制約を満たす確率として０．９８８を得たとき、タイミング歩留制約は不充足と判定され（ステップＳ１１）、ステップＳ１２へ移る。【０１４５】
パス遅延確率分布変更部１１７は、配置配線変更後に相対的遅延制約が満たされるためのパス４０１、４０２の遅延値の期待値を求め、４．６５ｎｓおよび６．７８ｎｓを得る（ステップＳ１２）。【０１４６】
配置配線変更部１１６は、前記ネットリスト、配置配線情報、統計的パス遅延値情報、タイミング歩留不充足パス情報、相対的遅延制約記述に基づいて、対応関係のあるタイミング歩留不充足パス４０１の遅延値を延長し、またはパス４０２の遅延値を短縮するように配置配線の変更を行う。【０１４７】
性能低下を避けるため、パス４０１の短縮を行うように配置配線の最適化を行う（ステップＳ１３）。【０１４８】
再び、統計的タイミング解析部１１２は、図４の非同期式回路のネットリストおよび修正後配置配線情報に基づいて、パス４０２の遅延値の解析を行い、非同期式回路内のパス４０１の遅延値として、期待値４．６５ｎｓ、標準偏差０．４８ｎｓの正規分布を得たとする（ステップＳ９）。【０１４９】
相対的遅延制約充足率計算部１１３は、パス４０１、４０２の遅延値が図４の相対的遅延制約を満たす確率として０．９９１を得て、前記タイミング歩留制約が充足されたものと判定する（ステップＳ１１）ため、ステップＳ１４へ移る。【０１５０】
最後に、ネットリスト・配置配線情報出力部１９９は、図４の回路のネットリストと配置配線情報を出力して（ステップＳ１４）、処理を終了する。【０１５１】
本実施例によれば、次の効果が得られる。すなわち、統計的タイミング解析部１１２で得られる回路内のパスの遅延値の確率分布に基づいて、パス遅延確率分布変更部１１７は、相対的遅延制約が課されるパス４０１、４０２に対し、論理回路構成および配置配線を変更する際のパス遅延値の期待値の目標値を設定する。論理回路構成変更部１１４および配置配線変更部１１６は、相対的遅延制約における遅延を小さくすべきパス４０２の遅延値が最小化されるように回路構成の変更を行い、当該構成変更に応じて前記目標値を再設定して、次に遅延を大きくすべきパス４０１の遅延値が前記目標値を超える最小値となるように回路構成の変更を行う。以上により、所定のタイミング歩留制約を満たす範囲内において、図４の回路４００の性能の最大化が達成される。【０１５２】
また、パス遅延値の確率分布モデルを正規分布とし、パス遅延値の確率密度関数を期待値および標準偏差によって特徴付けることで、論理最適化および配置配線最適化の際のパス４０１、４０２の遅延値の確率分布の最適化目標設定が簡略化される効果もある。【０１５３】
以上本発明を上記実施例に即して説明したが、本発明は、上記実施例にのみ限定されるものではなく、本願特許請求の範囲の各請求項の発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。
【図１】
2008133116.tif 000003
【図２】
2008133116.tif 000004
【図３】
2008133116.tif 000005
【図４】
2008133116.tif 000006
【図５】
2008133116.tif 000007
【国際調査報告】
2008133116.tif 000008
2008133116.tif 000009
2008133116.tif 000010
2008133116.tif 000011