(57)【特許請求の範囲】
【請求項１】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及び加速の量を計算するための遅延変更曲線を生成するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成するために、ビクティムの遅延を縮小することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記ビクティムの遅延を縮小により、前記最長のパスを短縮するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項２】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパスに対する非クリティカルパス中の各タイミングアークへの前記最終到着時刻の修正により前記非クリティカルパスを遅延させることで、前記アグレッサの遅延を増加することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記アグレッサの遅延を増加することにより、前記最長のパスを短縮するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項３】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成することで、前記ビクティムの遅延を縮小すること、又は、前記クロストーク軽減手段が、非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻の修正により前記非クリティカルパスを遅延させることで、前記アグレッサの遅延を増加することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記ビクティムの遅延を縮小又は前記アグレッサの遅延を増加することの少なくとも一方により、前記最長のパスを短縮するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項４】
前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、更に以下のステップを備えることを特徴とする請求項１から請求項３のいずれか１項に記載のクロストークの軽減方法。
（ｇ）  前記ノイズ対応タイミング解析手段が、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、
（ｈ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｉ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、ビクティムの遅延を縮小又はアグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、
（ｊ）  前記ノイズ対応タイミング解析手段が、前記ステップｉによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、
（ｋ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｇから前記ステップｊまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項５】
前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段における前記ステップｇから前記ステップｋまでの処理を、前記ステップｃから前記ステップｆまでの処理に先立って実行することを特徴とする請求項４に記載のクロストークの軽減方法。
【請求項６】
前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段における前記ステップｇから前記ステップｋまでの処理を、前記ステップｃから前記ステップｆまでの処理の後に実行することを特徴とする請求項４に記載のクロストークの軽減方法。
【請求項７】
前記クロストーク軽減手段が、前記ステップｉにて、
前記最短のパスの延長により前記パスにグリッチが生じる場合には、前記最短のパスの更なる延長を不可とすることを特徴とする請求項４に記載のクロストークの軽減方法。
【請求項８】
前記ノイズ対応タイミング解析手段が、前記アグレッサ及び前記ビクティムのそれぞれのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を与えるように、前記遅延変更曲線を修正するステップを更に備えることを特徴とする請求項１から請求項３のいずれか１項に記載のクロストークの軽減方法。
【請求項９】
前記クロストーク軽減手段が、前記ステップｄにて、
前記最長のパスの短縮により前記パスにグリッチが生じる場合には、前記最長のパスの更なる短縮を不可とすることを特徴とする請求項１から請求項３のいずれか１項に記載のクロストークの軽減方法。
【請求項１０】
前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を行なうことを特徴とする請求項１から請求項３のいずれか１項に記載のクロストークの軽減方法。
【請求項１１】
前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記非クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を行なうことを特徴とする請求項２又は請求項３に記載のクロストークの軽減方法。
【請求項１２】
前記ノイズ対応タイミング解析手段が、ビクティムに対し作用するアグレッサ、及び前記アグレッサとなり他の前記ビクティムに対し作用する前記ビクティムの影響のコーンを調査するステップを更に備えることを特徴とする請求項１から請求項３のいずれか１項に記載のクロストークの軽減方法。
【請求項１３】
前記クロストーク軽減手段が、前記最長のパスの前記短縮により前記非クリティカルパスによる新たな最長のパスを構成し、前記最長のパスを前記クリティカルパスとすることを特徴とする請求項３に記載のクロストークの軽減方法。
【請求項１４】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成するために、前記ビクティムの遅延を縮小することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記ビクティムの遅延を縮小により、前記最短のパスを延長するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項１５】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパスに対する非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻を修正して前記非クリティカルパスを遅延させることにより、前記アグレッサの遅延を増加することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記アグレッサの遅延を増加することにより、前記最短のパスを延長するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項１６】
コンピュータ上で実行される集積回路のクロストークの軽減方法であって、
前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成することで、前記ビクティムの遅延を縮小すること、又は、前記演算手段が、非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻を修正して前記非クリティカルパスを遅延させることにより、前記アグレッサの遅延を増加することを特徴とする。
（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、
（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、
（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記ビクティムの遅延を縮小又は前記アグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、
（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、
（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【請求項１７】
前記ノイズ対応タイミング解析手段が、前記アグレッサ及び前記ビクティムのそれぞれのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を与えるように、前記遅延変更曲線を修正するステップを更に備えることを特徴とする請求項１４から請求項１６のいずれか１項に記載のクロストークの軽減方法。
【請求項１８】
前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を実行することを特徴とする請求項１４から請求項１６のいずれか１項に記載のクロストークの軽減方法。
【請求項１９】
前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、更に以下のステップを備えることを特徴とする請求項１４から請求項１６のいずれか１項に記載のクロストークの軽減方法。
（ｇ）  前記ノイズ対応タイミング解析手段が、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、
（ｈ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、
（ｉ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、ビクティムの遅延を縮小又はアグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、
（ｊ）  前記ノイズ対応タイミング解析手段が、前記ステップｉによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、
（ｋ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｇから前記ステップｊまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、集積回路中のクロストーク（crosstalk：混線、漏話）の軽減に関し、特に、セットアップ妨害の場合に遅延を縮小しホールド妨害の場合に遅延を増加させることにより、アグレッサ（Aggressor：クロストークの影響を与えるネット）を弱くしビクティム（Victim：クロストークの影響を受けるネット）を強くしてクロストークを軽減する集積回路とそのクロストーク軽減方法に関する。
【０００２】
【従来の技術】
ディジタル集積回路中のクロストークは、集積回路のサイズが縮小するにつれてその問題の重要性がますます増加している。
【０００３】
従来よりディジタル集積回路は、クロストークによる様々な問題や障害が発生している。例えば、これに制限するのではないが、グリッチ（glitching）により機能的な障害を引き起こすことに加えて、更にクロストークにより、２つ同時の又はほぼ同時の信号の切り替えによる特定の相互作用に基づく回路遅延の減速及び加速の双方を遅延させる変化が引き起こされる。
【０００４】
従来の集積回路を縮小する方法は、サブミクロン（submicron）を処理する技術に深く関連し、クロストークの問題がゲートレベルタイミング（gate level timing）に重要な影響を及ぼしている。従来の設計技術では、動作周波数の増加に伴ってより密な金属ピッチやより高くより狭い信号線を導入し、これらは各信号線の間の影響を増加させている。全静電容量中に占める信号線対の静電容量の割合が増加して、今日では最小のピッチ配線のために８０％と高い値を取ることがある。
【０００５】
更に、従来の集積回路におけるカップリング（coupling）の増加により、各信号線間のクロストークが増加するという問題がある。本質的にクロストークには、問題となる２つの影響がある。まず１つ目は、クロストークは、隣接する信号線において信号が切り替えられることによってその信号線に短いパルスが発生するグリッチ（glitching）と呼ばれる機能的な影響がある。グリッチは、ラッチ（latch）への論理レベルの変更を伝播することで、機能的な障害を引き起こす。
【０００６】
２つ目は、クロストークは動的遅延（dynamic delay、つまり不確実な遅延）を引き起こす。動的遅延においては、隣接した信号線に流れる信号が同時に切り替わる場合に、回路に減速あるいは加速のいずれかを引き起こす。従来技術の０．１ミクロンの場合では、動的遅延の量が名目上の遅延の＋／−８０％となることがある。
【０００７】
クロストークによる動的遅延の影響を考慮する場合には、クロストーク対応の静的タイミング解析（ＳＴＡ：static timing analysis）、セットアップ妨害（setup violation）や、ホールド妨害（hold violation）セットアップが知られているが、前述のクロストークの発生は設計プロセスの中では認識されていなかった。
【０００８】
前述の従来技術のクロストーク問題においては、多くの従来の研究はクロストークの軽減の問題に向けられていた。従来の研究には、クロストークモデリング（crosstalk modeling）、クロストークの影響による遅延変更（delay change）の計算、クロストーク対応の静的タイミング解析（ＳＴＡ）がある。しかし、この従来技術では、前述のクロストークの動的遅延の問題に対応することができない。
【０００９】
従来よりビクティム（victim）を強くしアグレッサ（aggressor）を弱めることが動的遅延を削減する方法としてよく知られている。商用ベンダーは、大きな「ノイズスラック（noise slack）」（こうしたアグレッサは、ビクティムにはならないように弱くすることができる）を持つアグレッサを弱くし、ノイズスラックの小さい（又はノイズスラックのない）ビクティムを強化する「ノイズバランシング（noise balancing）」を行なう。
【００１０】
しかし、前述の従来技術においてはクリティカルパスを意識しないため、この従来の「ブランケット（blanket、全面的な）」アプローチでは動的遅延の問題を悪化させることがある。
【００１１】
更に、遅延変更はアグレッサとビクティムがスイッチングのタイムポジション（time position）を変更しその強さを変更しない場合においても重要であり、クリティカルパスのダウンストリーム（downstream、下流）のアグレッサ又はビクティムにおいて、強さの変更の場所が現われるかもしれない。従来技術においては、遅延変更の削減をガイドするクロストーク対応のＳＴＡを用いたとしても、遅延変更を削減することができなかった。
【００１２】
「カップリングの効果」（coupling effects）
従来技術において、ほぼ同時に隣接した信号線の各信号が切り替わると、その信号のドライバの抵抗が切り替え時よりも高くなり、その信号が遅延する重要な効果が発生する。
【００１３】
図４８は、カップリングの効果（coupling effects）による遅延をいかに計測するかを示す図であり、アグレッサとその遅延の計測点と、ビクティムとその遅延の計測点を示している。なお、図４８の信号線がビクティム又はアグレッサであることは、現在のスイッチングの条件において当てはまるのであって、各信号線の永久の特徴とするものではない。従って、異なるスイッチング条件においては、図４８の中のビクティムとアグレッサの役割は交代する場合もありえる。
【００１４】
ビクティムとアグレッサとの間のスイッチングの時間の差は、スキュー（skew：ゆがみ）により示される。入力のスキュー（input skew）は、ビクティム及びアグレッサの入力波形の５０％のスイッチングポイントにて切り替えた場合の差である。出力のスキュー（output skew）は、図４８に示されるように送信先ゲートへの入力で測定されたアグレッサとビクティムの波形の５０％のスイッチングポイントの差である。
【００１５】
アグレッサとビクティムが反対方向である場合には、ビクティムは、隣接したアグレッサのスイッチングがない場合（つまりグレッサの信号線が静かな場合（quiet aggressor line））場合と比較して遅くなることがある。
【００１６】
図４９では、ビクティムの信号が高く変わると同時に、アグレッサの信号が低く（つまり点線）変わった場合を示す図である。実線は、隣接するアグレッサが切り替えられた場合を示し、このビクティムの信号波形の突出部は、減速の効果を示している。アグレッサの信号は低く変わったので、そのより低い（より強い抵抗の）ドライバは低い抵抗に切り替わる。他方では、ビクティムの高い（より弱い抵抗の）ドライバも切り替わる。比較的強いアグレッサと比較的弱いビクティムにおける最大の減速のポイントは、わずかにビクティムの後でアグレッサが切り替えられた時である。
【００１７】
図５０は、同じ方角へアグレッサ及びビクティムがスイッチング（切り替え）られた場合を示す。隣接するアグレッサを切り替えることは、名目上の場合（nominal case）においてビクティムを遅くしていたカップリングによる静電容量の内のいくらかの影響を有効に削除して、ビクティムのスイッチングを助ける。
【００１８】
様々な要因（例えば、アグレッサとビクティムのドライバの相対的なサイズ、出力のスキュー、ネット上に含まれる電気的な特性、ネット間でカップリングされる量、アグレッサの信号の遷移の時間（signal transition time）（すなわちスキュー（skew））、またこれらに制限されるものではない）が、減速や加速の量に影響を及ぼす。静的タイミング解析（ＳＴＡ）では、信号の変わる方向が考慮されない。例えば、クロストーク対応のＳＴＡによる最終到着時刻（ＬＡＴ：latest arrival time）の計算により、信号が反対方向に切り替わる最悪の場合のスイッチングタイムが得られる。同様に、最前到着時刻（ＥＡＴ: earliest arrival time）の計算により、信号が同じ方向に切り替わる最良の場合のスイッチングタイムが得られる。
【００１９】
「遅延変更曲線」（ＤＣＣ：delay change curve）
信号線間のカップリング（coupling）が切り替えの要因のみで表わされる場合の従来のＳＴＡによるアプローチは、ＬＡＴとＥＡＴによりカップリングの可能性の最悪と最良の場合（つまり減速の最大の遅延あるいは加速の最小の遅延）を算出することができる。これらの従来技術のアプローチは、設計を過度に抑制しており、もしより精巧な解析が実行された場合に必要とするよりも長いクロック期間（clock period）を示すという損失がある。この従来技術は、およそ最近のクロストーク対応のＳＴＡによるアプローチの中で用いられている。
【００２０】
しかし、遅延変更曲線（ＤＣＣ：delay change curve）に基づいたより新しい従来技術のアプローチが、タイミング解析のために（しかしクロストーク軽減のためにではなく）導入されている。図５１に示されるように、従来技術のＤＣＣは、入力のスキューの作用である減速又は加速の量を示す。
【００２１】
入力のスキューはアグレッサがビクティムの前に切り替えられる場合にはネガティブ（negative）と考える。入力のスキューはアグレッサとビクティムとが同時に切り替えられる場合にはゼロである。遅延変更曲線（ＤＣＣ）は、ビクティムを調整しかつアグレッサの入力のスキューの大きなネガティブ（negative）から大きなポジティブ（positive）までを調べることにより生成さる。減速や加速の発生した入力のスキューの範囲は、有効なスキューのウィンドウ（effective skew window）として参照される。しかし、従来技術におけるＤＣＣの使用は、クロストーク軽減のためにではなくタイミング解析のためのみである。
【００２２】
従来技術におけるＤＣＣは、減速と加速に影響する予めリストアップされた各パラメーターの関数であり、特定のネット（回路）用にカスタマイズされる。従来技術の遅延変更曲線（ＤＣＣ）による十分な特性付けを行なうためにはあまりにもパラメーターが多いので、従来技術による部分的な特徴付け（partial characterization）又は解析的な生成（analytic generation）のいずれかのみが、従来技術において利用可能である。
【００２３】
更に、従来技術の遅延変更曲線の傾斜特性は重要である。経験的な証拠に基づいて、大きなネガティブのスキューからカーブのピークを与えるスキューまでの入力のスキューの変化が、減速又は加速の割合の比較的遅い変化を引き起こす。上述のように、従来ではＤＣＣをクロストークの軽減に用いていない。
【００２４】
【発明が解決しようとする課題】
上述したように従来の技術では、以下に述べるような問題点があった。
【００２５】
従来では、セットアップ妨害の場合の遅延を縮小し、ホールド妨害の場合の遅延を増加させることを保証することができなかった。従来のブランケットなアプローチにおいては、不必要で効果がない強さの変更を生むために計算上の資源が要求されるという計算上の資源の浪費があった。また、全ての強さの変更が、希望するゴールに近づくか又は変更を実行しないことを保証できなかった。
【００２６】
本発明の第１の目的は、上記従来技術の欠点を解決し、セットアップ妨害の場合に遅延を縮小できホールド妨害の場合に遅延を増加できることを保証し、効率よくクロストークを軽減する集積回路とそのクロストーク軽減方法を提供することにある。
【００２７】
本発明の第２の目的は、上記従来技術の欠点を解決し、計算上の資源の浪費を解消する集積回路とそのクロストーク軽減方法を提供することにある。
【００２８】
本発明の第３の目的は、上記従来技術の欠点を解決し、全ての強さの変更が、希望するゴールに近づくか又は変更を実行しないことを保証する集積回路とそのクロストーク軽減方法を提供することにある。
【００２９】
【課題を解決するための手段】
上記目的を達成するため本発明は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及び加速の量を計算するための遅延変更曲線を生成するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成するために、ビクティムの遅延を縮小することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記ビクティムの遅延を縮小により、前記最長のパスを短縮するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００３０】
請求項２の本発明によるクロストークの軽減方法は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパスに対する非クリティカルパス中の各タイミングアークへの前記最終到着時刻の修正により前記非クリティカルパスを遅延させることで、前記アグレッサの遅延を増加することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記アグレッサの遅延を増加することにより、前記最長のパスを短縮するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００３１】
請求項３の本発明によるクロストークの軽減方法は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成することで、前記ビクティムの遅延を縮小すること、又は、前記クロストーク軽減手段が、非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻の修正により前記非クリティカルパスを遅延させることで、前記アグレッサの遅延を増加することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと、静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける短縮可能な最長のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最長のパスのパス遅延のクロック期間との差と、セットアップ時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最長のパスに対するセットアップ時間妨害が存在し、かつ前記最長のパスが短縮可能である場合に、前記ビクティムの遅延を縮小又は前記アグレッサの遅延を増加することの少なくとも一方により、前記最長のパスを短縮するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最長のパスの短縮に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最長のパスに対するセットアップ時間妨害がない又は前記最長のパスを更に短縮できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００３２】
請求項４の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、更に以下のステップを備えることを特徴とする。（ｇ）  前記ノイズ対応タイミング解析手段が、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、（ｈ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｉ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、ビクティムの遅延を縮小又はアグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、（ｊ）  前記ノイズ対応タイミング解析手段が、前記ステップｉによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、（ｋ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｇから前記ステップｊまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００３３】
請求項５の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段における前記ステップｇから前記ステップｋまでの処理を、前記ステップｃから前記ステップｆまでの処理に先立って実行することを特徴とする。
【００３４】
請求項６の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段における前記ステップｇから前記ステップｋまでの処理を、前記ステップｃから前記ステップｆまでの処理の後に実行することを特徴とする。
【００３５】
請求項７の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段が、前記ステップｉにて、前記最短のパスの延長により前記パスにグリッチが生じる場合には、前記最短のパスの更なる延長を不可とすることを特徴とする。
【００３６】
請求項８の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、前記アグレッサ及び前記ビクティムのそれぞれのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を与えるように、前記遅延変更曲線を修正するステップを更に備えることを特徴とする。
【００３７】
請求項９の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段が、前記ステップｄにて、前記最長のパスの短縮により前記パスにグリッチが生じる場合には、前記最長のパスの更なる短縮を不可とすることを特徴とする。
【００３８】
請求項１０の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を行なうことを特徴とする。
【００３９】
請求項１１の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記非クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を行なうことを特徴とする。
【００４０】
請求項１２の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、ビクティムに対し作用するアグレッサ、及び前記アグレッサとなり他の前記ビクティムに対し作用する前記ビクティムの影響のコーンを調査するステップを更に備えることを特徴とする。
【００４１】
請求項１３の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段が、前記最長のパスの前記短縮により前記非クリティカルパスによる新たな最長のパスを構成し、前記最長のパスを前記クリティカルパスとすることを特徴とする。
【００４２】
請求項１４の本発明によるクロストークの軽減方法は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成するために、前記ビクティムの遅延を縮小することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記ビクティムの遅延を縮小により、前記最短のパスを延長するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００４３】
請求項１５の本発明によるクロストークの軽減方法は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパスに対する非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻を修正して前記非クリティカルパスを遅延させることにより、前記アグレッサの遅延を増加することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記アグレッサの遅延を増加することにより、前記最短のパスを延長するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００４４】
請求項１６の本発明によるクロストークの軽減方法は、コンピュータ上で実行される集積回路のクロストークの軽減方法であって、前記コンピュータ上のノイズ対応タイミング解析手段が、クロストークにより発生する減速及びスピードアップの量を計算するための遅延変更曲線を生成し、短縮可能でありかつ前記短縮によりグリッチの生じないクリティカルパスの候補の数を増加させるように、前記遅延変更曲線を修正するステップと、以下のステップを含み、前記コンピュータ上のクロストーク軽減手段が、前記遅延変更曲線により決定されるクロストークを原因とする遅延の増加を縮小した前記クリティカルパス又は前記遅延の増加の縮小により移動した前記クリティカルパス中の、各タイミングアークへの最終到着時刻を修正してより速いクリティカルパスを作成することで、前記ビクティムの遅延を縮小すること、又は、前記演算手段が、非クリティカルパス中の各前記タイミングアークへの前記最終到着時刻を修正して前記非クリティカルパスを遅延させることにより、前記アグレッサの遅延を増加することを特徴とする。（ａ）  前記ノイズ対応タイミング解析手段が、前記タイミングアークにより連結された入力ゲートを備える各パスと静的タイミング解析に基づいて、タイミンググラフを生成するステップ、（ｂ）  前記ノイズ対応タイミング解析手段が、生成した前記遅延変更曲線に基づいてビクティムとアグレッサのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を決定することによって、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、（ｃ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｄ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、前記ビクティムの遅延を縮小又は前記アグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、（ｅ）  前記ノイズ対応タイミング解析手段が、前記ステップｄによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、（ｆ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｃから前記ステップｅまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００４５】
請求項１７の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、前記アグレッサ及び前記ビクティムのそれぞれのタイミングウィンドウ内の最も大きな減速又は加速を示す位置を与えるように、前記遅延変更曲線を修正するステップを更に備えることを特徴とする。
【００４６】
請求項１８の本発明によるクロストークの軽減方法は、前記ノイズ対応タイミング解析手段が、入力が到達する前記タイミングアークの前記最終到着時刻の最大値と、最悪の場合における前記クリティカルパスの各前記タイミングアークへの入力と出力との間の遅延を決定することにより、前記最終到着時刻の前記修正を実行することを特徴とする。
【００４７】
請求項１９の本発明によるクロストークの軽減方法は、前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、更に以下のステップを備えることを特徴とする請求項１４から請求項１６のいずれか１項に記載のクロストークの軽減方法。（ｇ）  前記ノイズ対応タイミング解析手段が、前記タイミンググラフにおける延長可能な最短のパスを決定するステップ、（ｈ）  前記ノイズ対応タイミング解析手段が、前記最短のパスのパス遅延とホールド要求時間を比較することでセットアップ時間妨害の存在を判定するステップ、（ｉ）  前記クロストーク軽減手段が、前記最短のパスに対するホールド要求時間妨害が存在し、かつ前記最短のパスが延長可能である場合に、ビクティムの遅延を縮小又はアグレッサの遅延を増加することの少なくとも一方により、前記最短のパスを延長するステップ、（ｊ）  前記ノイズ対応タイミング解析手段が、前記ステップｉによる前記最短のパスの延長に基づいて、前記タイミンググラフを再計算するステップ、（ｋ）  前記クロストーク軽減手段及び前記ノイズ対応タイミング解析手段が、前記ステップｇから前記ステップｊまでの処理を、前記最短のパスに対するホールド要求時間妨害がない又は前記最短のパスを更に延長できないことの少なくとも一方が達成されるまで繰り返し実行するステップ。
【００５９】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００６０】
本発明では、クロストークの影響による遅延の軽減を、ターゲットのトランジスタのサイジング（transistor sizing）やバッファ挿入（buffer insertion）により、クロストークのアグレッサを弱める又はクロストークのビクティムを強化することにより行なう。
【００６１】
従来の技術では、遅延変更曲線（ＤＣＣ）がクロストーク軽減のためにではなく単にタイミング解析のために使用されたり、クロストーク軽減による遅延変更曲線の修正を行なっている。従って、クロストーク軽減に遅延変更曲線（ＤＣＣ）を適用することは、本発明の斬新な特徴である。
【００６２】
また、従来技術の遅延変更曲線の生成、また従来のシステムにおいて減速や加速を生じる入力のスキュー、アグレッサ／ビクティムの強度、スキューの割合、特定のネットへの適応、カップリングの量は、本発明の範囲内ではない。
【００６３】
遅延変更曲線（ＤＣＣ）はこれを修正することができ、例えば、解析する潜在的なパスの制限、アグレッサやビクティムの受理可能な強化の可能性の増加、解析を要求するアグレッサとビクティムの相互作用（interaction）の数の縮小、ビクティムかアグレッサの正確な位置の選別を許可しタイミングウィンドウ内のそれぞれの最悪の場合の減速又は加速を与えること等が考えられる。遅延変更曲線（ＤＣＣ）の修正なしでは、変更が有用である保証が影響の小さなコーン（cone）を越えない。
【００６４】
大きなポジティブのスキュー（large positive skew）のカーブのピークを生むスキューからスキューへの変化は、減速や加速における早く変化すること（fast change）又は遅く変化すること（slow change）により引き起こされる。早く変化すること（fast change）には、カーブの傾斜が予言可能でないカーブのピークに近い範囲がある。この場合では、解析及びクロストーク軽減アルゴリズムの続行を援助するため、図１において示されるように、カーブのピークが右に拡張され、実際のカーブ上に「ステップダウン（step down）」が注入される。
【００６５】
遅い変更の場合には、図２に示されるように、ステップダウン（step down）の代わりに１つの傾斜の傾斜路（ramp）が入力される。従来技術のＤＣＣへの修正では、減速／加速のカーブのピークからの大きなポジティブの入力のスキューへの入力のスキューの変更を保証し、その減速／加速は少なくとも入力のスキューの変化率以上変化する。続く説明は、本発明によるＤＣＣの修正が完了した場合について説明することとし、またＤＣＣの修正に関してはこれより後によく詳しく述べることとする。
【００６６】
「ＬＡＴとＥＡＴの修正」
アグレッサとビクティムの相互作用は、静止しているもの（例えばビクティム）及び、その静止しているものに関連するある方向に移動するもの（例えばアグレッサ）とに分類することができる。この相互作用は、更にアグレッサとビクティムの相互作用中に活発であるＤＣＣ中の部分によっても分類できる。ＳＴＡのウィンドウがアグレッサとビクティムのスイッチングタイムを示すので、アグレッサとビクティムの両方の最も大きな減速又は加速を示すウィンドウ内の正確な位置を見つけることができる。
【００６７】
ＬＡＴ（latest arrival time：最終到着時刻）の修正については、ビクティムがアグレッサに関し右から左まで移動する。図３では、ビクティムの現在のＬＡＴが、アグレッサの有効なスキューのウィンドウの外部にある場合を示す（つまり、現在のビクティムのＬＡＴは右端の最も減速したスキューの位置の右であり、アグレッサの有効なスキューのウィンドウ内にない）。全ての図において、ＥＡＴ（earliest arrival time：最前到着時刻）を、Ｔ１により示す。また、ＬＡＴをＴ２により示す。ビクティム（又はアグレッサ）の正確な選択した位置は、ＴＸＶ（ＴＸＡ）である。図３では、有効なスキューのウィンドウのいずれか一方の端における減速が「０」である。
【００６８】
ビクティムとアグレッサの正確な位置は、最大の減速又は加速を得るためにそれらのウィンドウ内のいかなる場所にも選択することができる。また、選ばれた正確な位置は、その減速及び加速のピークの各面におけるＤＣＣの切り離しのため常に最大の減速か加速であり、最も小さい相対的な分離である。しかし、最大のＬＡＴ又は最小のＥＡＴを達成するアグレッサ又はビクティムの正確な位置の選択は、必ずしも最大の減速あるいは加速を与える位置に相当するとは限らない。
【００６９】
図３に示されるケース１において、ＴＸＶの位置がアグレッサのＴＸＡの位置と同じである場合、最大の減速が生じる。しかし、修正済のＬＡＴ位置は、現在のウィンドウ内にある。従って、最大のＬＡＴは現在のＬＡＴと同じ位置である。また、ＴＸＶはその位置で選ばれる。
【００７０】
図４に示されるケース２の場合（つまり、現在のビクティムのＬＡＴが右端の最も減速したスキュー位置の右であり、アグレッサの有効なスキューのウィンドウ内にある場合）では、Ｔ２Ｖが更に左に移動すると共に、アグレッサの有効なスキューのウィンドウ（aggressor effective skew window：ＡＥＳＷ）の影響下に入り、その減速がＬＡＴを増加させる。Ｔ２Ｖの左への移動は、傾斜がこの重要な遅延変更曲線（ＤＣＣ）の範囲にあることが想定されるため、減速の増加を押さえＬＡＴにおけるネットの減少を引き起こす。
【００７１】
結局更に左へ移動すると、図５のケース３のように示される（つまり、右端の現在のビクティムのＬＡＴの最も減速したスキュー位置であり、減速したスキュー位置の右端と左端の間である）。ＴＸＶの位置は、今右端の最も減速したスキュー位置にあり、「０」のスキュー位置ではない。これは、アグレッサ位置は、アグレッサウィンドウ内の任意の場所から選ぶことができるためである。
【００７２】
ビクティムが左に移動し続けて減速が一定であり、ＬＡＴがビクティム移動をトレースし、ＡＥＳＷはスキュー位置がＴ２ＶからＴ１Ａにあたる０まで移動する。その後、アグレッサウィンドウはもはやトレースすることができない。図６のケース４（すなわち、現在のビクティムのＬＡＴが左端の最も減速したスキュー位置の左にあり、アグレッサの有効なスキューのウィンドウ内にある場合）に示されるように、減速は継続して最大でＴ２Ｖの左まで達しスキュー位置「０」から左端の最も減速したスキュー位置の左に至る。その位置では、少なくともＬＡＴの左移動と同じくらい速く、減速が減少し始める。従ってＬＡＴは、Ｔ２Ｖの更に左への移動と共に減少することになる。
【００７３】
最終的に、図７のケース５に示されるように(つまり、現在のビクティムのＬＡＴが左端の最も減速したスキュー位置の左であり、アグレッサの有効なスキューのウィンドウ内にない場合) Ｔ２ＶがＡＥＳＷの左端をクリアする局面に入る。従ってＬＡＴは、ビクティムの右から左の移動を全体的に減少させ、かつアグレッサを固定する。
【００７４】
ＥＡＴの修正においては、ここでビクティムが左から右まで移動するとして説明する。図８示されるケース１の場合（つまり、現在のビクティムのＥＡＴが右端の最も加速したスキューの位置の左側にあり、アグレッサの有効なスキューのウィンドウ（ＡＥＳＷ）内にない場合)では、現在のビクティムのＥＡＴがＡＥＳＷの外部である。加速は、ビクティム・ウィンドウ内に含まれ、従ってＥＡＴは変わらない。
【００７５】
ビクティムＴ１Ｖが、ＡＥＳＷの右端の最大の加速位置に位置したＴＸＶと共により右に移動し、現在のビクティムのＥＡＴはＡＥＳＷの左端に触れる。右端と左端は、ＤＣＣに関するこれらの意味を保持する。ビクティムＴＩＶの更に右への移動はＥＡＴを増加させるものではなく、加速は少なくともＥＡＴの移動の割合で増加するため、右端の最大の加速位置における加速が常に方向づけるものと考えることができる。
【００７６】
従って図９のケース２（つまり、現在のビクティムのＥＡＴが右端の最も加速したスキューの位置の左側にあり、アグレッサの有効なスキューのウィンドウ内にある場合）に示されるように、新しいＥＡＴは一定である。
【００７７】
ＴＩＶが右端の最大の加速位置に到着する場合、新しいＥＡＴは再び増加し始め、その増加は継続し図１０のケース３（つまり、現在のビクティムのＥＡＴが右端の最も加速したスキュー位置か、又は右端の最も加速したスキュー位置と左端の最も加速したスキュー位置との間にある場合）に示されるように現在のＥＡＴが左端の最大の加速位置をクリアして加速が減少し始めるまで続く。
【００７８】
ＤＣＣのこの部分では、加速はＴ１Ｖが右に移動するよりもゆっくり減少し、図１１のケース４（つまり、現在のビクティムのＥＡＴが左端の最も加速したスキューの位置の右側にあり、アグレッサの有効なスキューのウィンドウ内にある場合)に示されるようにＥＡＴは増加し続け、図１２のケース５（つまり、現在のビクティムのＥＡＴが右端の最も加速したスキューの位置の左側にあり、アグレッサの有効なスキューのウィンドウ内にない場合)に示されるようにＴ１ＶはＡＥＳＷの終端をクリアする。従ってＥＡＴは、ビクティムの左から右の移動を全体的に増加させるか又は変化させず、アグレッサを固定する。
【００７９】
従って、ＬＡＴ又はＥＡＴの最大の変更を与える、ビクティムとアグレッサのウィンドウ内の正確な位置を決定することができる。遅延変更曲線（ＤＣＣ）のピーク位置及び修正済のＤＣＣの傾斜は、アグレッサとビクティムの任意の相対的な移動を含むように拡張することのできるようにＬＡＴ又はＥＡＴを変更することを可能にする。
【００８０】
「タイミンググラフ」（timing graph）
図１３は、タイミンググラフに関連したいくつかの用語の定義を示す。タイミンググラフは、静的タイミング解析（ＳＴＡ：static timing analysis）の結果を使用して、容易に構築される。ノードは、ゲートへの入力（入力ゲート）を示す。またエッジは、他のゲートに対するゲート及びネット（nets）を介した接続（例えば、タイミングアーク（timing arcs））を示す。エッジとの結合は、ＬＡＴとＥＡＴのネットに対する価値である。２つのダミーのノードが挿入されており、Downstream_Dummy_Nodeはラッチ（latches）を出力するために接続する全てのエッジのデスティネーションノード（destination node）であり、またUpstream_Dummy_Nodeはラッチを入力するために接続する全てのエッジのソースノード（source node）である。各パスは、分岐（forks）や結合（joins）を持つことがある。ダウンストリーム出力（Downstream fan-out）は分岐におけるノードから出るエッジであり、アップストリーム入力（Upstream fan-in）は結合におけるノードに入るエッジである。
【００８１】
「アルゴリズム的方法」（ALGORITHMIC STRATEGIES）
クロストーク軽減のための基本的な２つの方法は、ビクティムを強化しアグレッサを弱めることである。設計中の特定のネットの動的遅延感受性（Dynamic delay susceptibility）は、それらの信号線のドライバの強さ（サイズ）の強い機能である。ビクティムの強さを増加させることは、カップリングによるビクティムの遅延増加や遅延減少の感受性を小さくする。
【００８２】
ビクティムの強さの増加はカップリングによる影響を縮小する直接のアプローチであり、ビクティムに影響を与えるアグレッサの強さの縮小はカップリングによる影響を縮小する間接のアプローチである。これは、アグレッサのクロストーク感受性が、ビクティムが現実に増加するように見るためである。本発明は、この両方の方法を使用する。
【００８３】
強さは、使用するゲートの出力におけるトランジスタ・サイジング（transistor sizing）及び（又は）バッファ挿入（buffer insertion）により変えることができる。モデムＡＳＩＣ（Modem ASIC）ライブラリは、ゲート（つまり２つあるいは３つのサイズだけ）のサイズの大きな範囲を含んでいない。一方、様々に異なるバッファ（あるいはインバータ）サイズは利用可能である。従って、強さの変更はゲートサイジング（gate sizing）及びバッファ挿入の組み合わせにより行なう。例えば、強さの増加は、バッファの追加及び（又は）ゲートサイズの調整と同様に、バッファのサイズを変更することにより行なうことができる。バッファやゲートのサイズ調節を多く呼び出すことは、実際の強さの変更の最終決定の前に必要となりうる。従って、バッファ挿入の効果はクロストーク軽減の全体的な効果に決定的である。本発明では、従来のバッファ挿入技術を用いる。
【００８４】
遅延変更曲線（ＤＣＣ）及び標準のＳＴＡにより、クロストーク対応のＳＴＡ（crosstalk aware STA）を生み出すことができる。更に、クロストーク対応のＳＴＡツールは、ＬＡＴの最長のパス及びＥＡＴの最短のパスを識別することができる。式（１）により、各エッジのＬＡＴを計算することができる。
【００８５】
【数１】
0003800329.tif 000002
ここでＷＣＤは最悪の場合の遅延（worst case delay）を意味する。ＬＡＴの最長のパスは、出力ラッチにおける最大のＬＡＴを取り、入力ラッチにおけるパス上のゼロスラックエッジ（zero slack edges、スラックのないエッジ）を見つけることにより構築することができる。同じデスティネーションノードを備える他のエッジは、ポジティブなスラックを持つことになる。
【００８６】
同様に、式（２）により、各エッジのＥＡＴを計算することができる。
【００８７】
【数２】
0003800329.tif 000003
ここでＢＣＤは最良の場合の遅延を意味する。ＥＡＴの最短のパスは、出力ラッチにおける最小のＥＡＴを取り、入力ラッチにおけるパス上の最小のゼロスラックエッジ（zero slack edges）を見つけることにより構築することができる。同じデスティネーションノードを備える他のエッジは、ネガティブなスラックを持つことになる。
【００８８】
図１４は、本発明のビクティムを強化する方法を示す。ＬＡＴの最長のパス（クリティカルパス）のみがここに示されている。ビクティムを強化するエッジをαとして指定する。αにおける強さの変更はαの遅延を減少させ、またクリティカルパス上の他のエッジβは後ろに移動する。αの強さの変更の結果移動するエッジは、クリティカルパスのエッジのみではなく、クリティカルパス上のエッジの移動によりそれに接触することになる非クリティカルパス上のエッジも含まれる。ビクティムとしてαに関連したエッジを移動させることにより作成されたパスを、ビクティムパス（victim paths）と呼ぶ。クリティカルパスのエッジは第１のビクティムパスの一部である。また、非クリティカルパスのエッジは第２のビクティムパスの一部である。βのエッジが新しいクリティカルパスを形成するために十分に後ろに移動できるように、αの移動は十分に大きい。これは、非クリティカルパスにおいてエッジβのデスティネーションノードでポジティブなスラックを持つエッジがゼロスラックエッジとなるためであり、オリジナルのエッジβは今ポジティブなスラックを持つ。
【００８９】
新しいクリティカルパスが形成された場合、αの移動よりも少ない量で短縮を終了するクリティカルパスが生み出される。クロストークの軽減を始める前に、機能的なエラーを引き起こすグリッチの例は全て従来技術を用いることで削除される。クリティカルパスを短くするのに必要な強さの増加によって、そのビクティムがグリッチアグレッサ（glitch aggressor：グリッチのために機能的なエラーを引き起こすアグレッサ）になる場合には、そのビクティムを強くすることを許可しない。
【００９０】
ビクティムがアグレッサに変わる可能性（及びその逆）のために、ビクティムとしてのα、アグレッサとしてのα、及びアグレッサ及びビクティムの両方としての各βの解析が必要である。図１４には示されていないが、αの移動の結果移動するエッジによる第２パスがあり、β解析もまたそれらのパス上で行なわれることになる。
【００９１】
図１５は、アグレッサを弱め非クリティカルパスを遅らせる方法を示す。ビクティムの強化と同様に、アグレッサの強さの減少によりそのアグレッサがグリッチビクティム（glitch victim）に変わる場合には、そのアグレッサを弱めることを許可しない。ビクティムを強化する際には、アグレッサとビクティムとしてα及びβの場合を全て解析しなければならない。アグレッサを強化した非クリティカルパス上のα及びβは、後方よりも前方に進むことになる。ビクティムの強化と同様に、動いている第１パスと第２パス上の全てのβを解析する必要がある。アグレッサを弱める方法において、アグレッサとしてαに関連したエッジを移動させることにより作成されるパスを、アグレッサを弱めるパス（aggressor weakening paths）と呼ぶ。アグレッサを弱める方法において、移動するエッジの第１パスと第２パスを、第１と第２のアグレッサを弱めるパス（primary and secondary aggressor weakening paths）と呼ぶ。
【００９２】
「アグレッサとビクティムの相互作用」
上述のアルゴリズムによる方法を実行し、かつＬＡＴの最長のパスをセットアップ妨害の場合に短縮しＥＡＴの最短のパスをセットアップ妨害の場合に延長することを保証するために、強さの変更と移動又は単なる移動によるアグレッサとビクティムの相互作用の効果を解析する必要がある。
【００９３】
上記の注意すべき問題点及び従来技術の問題点に加えて、クロストークの軽減を実際的かつ効率的にするために、解析の範囲を、第１パスと第２パスのエッジの直接隣接するエッジまでに制限することが重要である。
【００９４】
その結果、他の問題点及び（又は）従来技術の問題点は、その効力が局所的でなくかつ希望するパスの長さ変更するために有効であることが保証できないため、従来技術による強さの変更及び移動を許可してはいけないことである。
【００９５】
「相互作用の基本原則」（interaction ground rules）
本明細書では、ビクティムを強化する場合において、セットアップ妨害とホールド妨害のみを議論する。しかし、関連する技術分野における通常の技術により、この議論を容易に他の場合まで延長することができる。
【００９６】
一般に（例外であるトレース（tracing）の場合は、より詳しく次の項目で説明するとして）、αの強さの変更や任意のビクティム上のβの移動の影響は、自身が移動するビクティム又は静止しているビクティムの双方において、それらのビクティムのネットＬＡＴを一定にするか又はそれらのＬＡＴを縮小する。同様に、自身が移動する又は静止している任意のアグレッサの影響は、α又はβにおいて、α又はβのネットＬＡＴを一定に維持するがそれを縮小する。
【００９７】
アグレッサとビクティムの両方が移動するすることは可能であり、これはアグレッサとビクティムとが両方とも同じクリティカルパス上にある場合や、一方が（例えばビクティムが）第１のクリティカルパスにあり他の一方が（例えばアグレッサが）第２パス上にある場合あるためである。
【００９８】
中間の効果（Intermediate effects）とは、双方が移動するアグレッサとビクティムの間に位置するビクティムに対する、アグレッサの影響である。
【００９９】
中間の効果は、アグレッサとビクティムとの相対的なタイムシフト（relative time shifts）を決定するので、中間の効果の量は一般に計測可能である。
【０１００】
環境の効果（Environmental effects）とは、全てのβの又はαのビクティムのネットＬＡＴに対する影響である。更に、それらのビクティムがアグレッサとみなされる場合には、全てのβのビクティム又はαのビクティムのビクティムに対する影響も調べる。より詳しく次の項目で説明するように、環境の効果は、α又はβとこの環境の場所との間で相互作用が起き場合には、ＬＡＴを低下させるか、あるいは同じレベルにＬＡＴを維持する。環境の効果は、クリティカルパスの短縮を強化する。
【０１０１】
従ってクリティカルパスの短縮は、αの強化とβの動作のトレースのために計算され、環境効果によって増加することがある。環境の効果の量は計測することができない。環境の効果の予測は、変更の影響が集中するゴールや集中することのない変更の影響を予測することと同じである。
【０１０２】
上述の説明は、ＥＡＴの場合にもあてはめることができる。許された相互作用は同様にしてネットＥＡＴに増加や抑制を行なう。環境の効果は、同様にしてＥＡＴを一定にするか又は増加させる。
【０１０３】
「トレース」（tracing）
相互作用の基本原則の基準を満たさないためにアグレッサ又はビクティムとの間の相互作用が却下される場合にも、その強さの変更や移動がトレース（tracing）により実行されることがある。トレースは、ビクティムに対し作用するアグレッサ、及びアグレッサとなり他のビクティムに対し作用するビクティムによる影響のコーン（cone）を調査するプロセスである。この相互作用のコーンのリーフ（leaves）における相互作用が、相互作用の基本原則の基準を満たす場合には、オリジナルの相互作用が許される。解析されたコーンのサイズは、トレース半径（tracing radius）と呼ぶ。トレース半径は、効率と効能とを交換する。例えば、これに制限するのではないが、より大きなトレース半径は本発明のクロストークを軽減するアルゴリズムに、相互作用の基本原則の基準を満たす強さの変更を見つけるより多くの機能を与えることができる。
【０１０４】
「アグレッサとビクティムの相互作用の例」
ブランケット（blanket、全面的）なクロストーク軽減は、カップリングによりセットアップ妨害（setup violations）及びホールド妨害（hold violations）の両方のアドレシングを要求する。アグレッサ・ビクティム相互作用の解析には、ＢＭ（backward movement：後方への移動の）減速、ＢＭ加速、ＦＭ（forward movement：前方への移動の）減速、ＦＭ加速の４つのカテゴリーがある。適切な解析は、その動作が使用の状況下において許可されるものに依存し、以下に詳しく説明する。
【０１０５】
減速の場合において、詳細なアグレッサ・ビクティム解析には、セットアップ妨害の状況におけるＢＭ減速解析の２つのケースがある。図１６に示すケース２は、アグレッサであるαのＢＭ減速解析である。ビクティムを強化することにより、次の２つの影響がる。１つは、強さの変更による減速↑、ＬＡＴ↑（この各記号は、より減速することとＬＡＴがより長くなることを意味する）であり、もう１つは、移動の効果によるゲート／バッファ構成の遅延の減少である。第２の効果は、ビクティムが静止している間にはアグレッサのＴ２Ａが左に移動するので、ケース２のＤＣＣの範囲において減少↓、ＬＡＴ↓（この各記号は、減速が低下することとＬＡＴがより短くなることを意味する）となることである。
【０１０６】
アグレッサとビクティムの双方がパスを移動させることはないので、中間の効力はなく、また環境の効果は強さの変更の移動（β型の移動）に制限されず、環境の効果はこの場合適用可能ではない。ＢＭの改善（BM remedy）は、ビクティムとアグレッサの相互作用に相互作用の基本原則の基準を満たさせる。強さの変更の効力及び移動の効力が互いに打ち消しあう（つまりバランス（balance）がある）か、ＬＡＴにネット減少がある場合に、相互作用が許される。
【０１０７】
許可（Permission）は、このαの強さの増加が生じることを許すことを意味する。これは次により詳しく説明することとして、βの考察から始める。全てが続いてうまくいく場合には、αの強度が確固となる。単一のアグレッサ／ビクティム相互作用のみをここでは説明しているが、多数の相互作用への拡張はより詳しく次に説明する。
【０１０８】
バランスがない場合には、トレースが実行され、影響のコーンが検査される。もしコーンのリーフ（leaves）がトレース半径に先立ってＬＡＴ↓を生み出す場合には、許可が得られる。
【０１０９】
もしトレースが成功しなかった場合には、回避（Bypassing）を実行することができる。回避は、更にαを強化することを含み、その結果恐らく強さの変更の効力を相殺するよりも多くの移動の効力があり、それは相互作用に含まれる特定のネットに依存し、それは希望する効果を生むかもしれないし生まないかもしれない。
【０１１０】
許可が３つの全てのテストにおいて最終的に与えられない場合、新しい候補α（がもしある場合には）をクロストークの軽減を継続するために見つけなくてはいけない。
【０１１１】
図１７に示されるケース４は、アグレッサであるβのＢＭ減速解析である。β型エッジについては、強さの変更の効力はない。移動は、ケース４にて移動が残る場合には減速↑とＬＡＴ↑を生み出し、ケース３に移動が継続する場合には減速が一定でありＬＡＴは変更されず、ケース２又はケース１に移動が継続する場合には減速↓ＬＡＴ↓である。
【０１１２】
ＢＭの改善は、ケース２においてバランスを達成するようにトレースするか回避することである。バランスを達成できずかつトレースを失敗した場合には、減速の増加を回避し、そしてアグレッサの移動の増加の量としてそれを減少させる。ここで、ＬＡＴ↓となるバランスの位置（balance point）を達成するためにどれだけの移動を付加することが必要であるかが注目される。最終的に成功するように回避するには、αの強さを必要とされる付加的な移動を達成するように増加できることが必要である。
【０１１３】
加速解析（speedup analysis）は減速解析（slowdown analysis）の間に実行する。ビクティムにおける減速の影響を知るため、加速解析はアグレッサのために必要である。従って、セットアップ妨害の軽減あるいはホールド妨害の軽減用のアルゴリズムは、全て減速及び加速の両方を同時に考慮しなくてはいけない。
【０１１４】
加速解析では、環境の効果がＥＡＴを一定にするか増加させる。従って図１７に示されるように、環境の効果は常にＴ１Ａを増加させ、Ｔ１ＡとＴ２Ｖの間の分離を増加させ、よって減速とＬＡＴを減少させる。環境の改善は必要ではない。
【０１１５】
また図に示したように、前述の例はアグレッサとビクティムの相互作用を示すものであり、より詳しく次に説明する。
【０１１６】
「相互作用の場合の概要」
ここで説明するアグレッサ・ビクティム相互作用の場合の概要を、図１８から図２１に示し、図２２は、これら各図面において使用する略語の意味を示す。ＮＲＮ（no remedy needed）は、改善が必要ではないことを示す。それはβを含んでいるほとんどのケースをカバーする。［、］の括弧内の左側では、ＮＶ（ＮＡ）、ＤＶ（ＤＡ）及びＵＶ（ＵＡ）によりそれぞれ、動いていないビクティム（アグレッサ）、ダウンストリーム（downstream：下流）のビクティム（アグレッサ）、及びアップストリーム（upstream：上流）のビクティム（アグレッサ）を示す。括弧内の右側のｍ、ｉ及びｅの表示は、それぞれ移動の効果、中間の効果、環境の効果を意味する。これらの表示は、示された改善をどの効果により行なったのかを示す。
【０１１７】
「Ａ→」及び「Ｖ→」の項目は、特定のｍ、ｉ、ｅの効果を生み出すアグレッサ又はビクティムによる移動を示し、「→」はアップストリームへの移動であり「←」はダウンストリームへの移動である。各図１８から図２１の改善方法の列においては、次に説明する各ケースを示す。また特に、正常な改善（normal remedy）を意味するＮＲＥＭの列がある。
【０１１８】
アグレッサとしてのα又はビクティムとしてのβを含む場合にはＮＲＮ以外が示され、強さの変更が含まれている。ＢＹは、前述の例のケース４におけるアグレッサとしてのβのＢＭ解析における回避又はトレースを示す。ＣＢＹは、前述の例のケース２におけるアグレッサとしてのβのＢＭ解析における条件付の回避又はトレースを示す。ＣＯＫ（条件付のＯＫ、又はトレース）は、アグレッサとビクティムのトラッキングがあり、つまり両方ともパスを移動し、回避をすることができない。
【０１１９】
ＥＲＥＭの列は、環境の改善（environmental remedy）を意味する。ＥＲＥＭの列の各項目においては、ＮＲＮとＮＡ以外がないことは重要である。これは、相互作用の可能な全ての場合において、環境上の相互作用がＬＡＴの短縮又は変更なしであるか、ＥＡＴの延長又は延長なしであることを意味する。
【０１２０】
「静的タイミング解析（ＳＴＡ）の関係」
ＬＡＴの最長パスの短縮あるいはＥＡＴの最短パスの延長後において、タイミングウィンドウを更新して環境変更を拡大するために静的タイミング解析を実行する。αの強さの変更による変更、全てのβの移動、全てのトレースが、その設計をＳＴＡへ渡す前にクロストーク軽減アルゴリズム自身によって注釈される。クロストークがある状態でのタイミング解析は「鶏と卵」の問題であり、そこでの減速や加速は、減速又は加速に影響するタイミングウィンドウなどに影響する。その結果、解析結果の変更が互いに基礎を置く。従って、希望の終了条件が得られるまで、アルゴリズムに関して下に記述されるように、変更が反復して実行される。クロストーク対応のＳＴＡにおいてこの固有のループする状況が与えられても、クロストークのモデルは常に収束を保証しなければならない。ここで、全ての環境上の変更がＬＡＴの短縮又は変更なしや、ＥＡＴの延長又は変更なしを引き起こすので、タイミング解析の各反復においてタイミングウィンドウは常に減少か一定である。従って、収束は保証される。
【０１２１】
要求される反復の数は少なく、かつＥＡＴを計算する最も速い打ち消しとＬＡＴを計算する最も遅い打ち消しを用いることにより効果が打ち消され、各反復の最悪の場合（すなわち、可能な限り広い場合）でもタイミングウィンドウが維持される。
【０１２２】
任意のクロストーク軽減前の初期のタイミング解析は、以下のように実行できる。まず、最悪の場合のスクロストークの効果を考えて計算されたタイミングウィンドウにより開始する。最悪の場合のクロストークの結果を考慮する第１の反復の後には、ＬＡＴ↓かつＥＡＴ↑となる(つまり、すべての相互作用が最悪の場合になるとは限らないので、タイミングウィンドウは縮む)。そして、解析は上述の環境の変更と同様であり、再び静的タイミング解析が収束する。
【０１２３】
「クロストークの軽減」
本発明の本実施の形態のクロストークを軽減するアルゴリズムは、上述のタイミンググラフ（timing graph）により動作する。
【０１２４】
タイミンググラフは、ダウンストリーム（下流）の方向（つまりタイミンググラフ中の指定されたエッジの方向）へ、αから開始しラッチ又はフリップフロップの境界で終了するように横断する。全ての移動するエッジはコーン（cone）を形成する。横断中に、カップリングのクロストークの影響を計算する。アルゴリズムの任意のポイントにおいて、アクティブなエッジをアグレッサ又はビクティムとして解析する。解析されているエッジと相互に作用するエッジは、既に解析されたコーンの部分上にあるか（つまり、移動しその求められた移動先に現在固定している）、まだ解析されていないコーンの部分上にある。アグレッサ・ビクティム相互作用の詳細は、全体的なアルゴリズム及び複雑さの評価のセクションの後に続けてより詳しく説明する。
【０１２５】
「アグレッサとビクティムの解析」
図２３から図２６は、セットアップ妨害とホールド妨害に対する本発明のビクティムの強化とアグレッサを弱める実施例を示す。
【０１２６】
ビクティムの強化方法は、α及び全てのβにおけるアグレッサの動的なＬＡＴの全体的な短縮、及びアグレッサの動的なＥＡＴの前面的な延長により、最長のパスの短縮又は最短のパスの延長のいずれかのゴールがトラック上に常にあることの保証を要求する。アグレッサを弱くする方法においては、非クリティカルパス上にはスラックが常にあるため短縮や延長が可能であり、ＬＡＴ又はＥＡＴに制限はない。
【０１２７】
図２７から図３０は、クロストーク軽減アルゴリズムの実行中に加速と減速を計算する本発明の実施の形態による方法を示す。
【０１２８】
強さが修正されているエッジであるαが解析された場合、強さの変更の結果移動するエッジは、αからタイミンググラフの目的とする終端まで下るコーン（cone）の中に全てある（Downstream_Dummy_Node）。
【０１２９】
アグレッサであるαの影響は、図２７で示されるように、そのコーン中のエッジはビクティム分析がそれらのエッジにて終わると考えられる。αは、弱める又は強化することと、前方又は後方に移動することができる。コーン中にない固定エッジについては、正確な結果を計算できる。αよりもクリティカルパス上で初期のビクティムのために、回避を要求する可能性がある。そうなれば、回避がこの情況に意味を持たないから、その後別のαを選ばなければならない。
【０１３０】
相互作用がＮＲＮ型である場合、ビクティムに対する影響は環境上であると考えられ、解析中において無視されない。もちろん、αとアップストリームのビクティムとの間の相互作用のＮＲＮの効果は、ＬＡＴの最長のパスを短縮するか又はＥＡＴの最短のパスを更に延長する効果がある。
【０１３１】
αが図２８により示されるようなビクティムである場合、ダウンストリームのアグレッサとαの間の相互作用は常にＮＲＮ型であり、アップストリームからダウンストリームまでタイミンググラフを横断するので、その中間の効果は未知でありその結果アグレッサとビクティムとの間の正確なスキューを決定することができず、環境の効果として相互作用を扱う。アップストリームのアグレッサの場合には、正確な効果を計算することができる。回避は必要ではなく、前述のテーブルを調べることによりこれを見つけることができる。固定したアグレッサ（αからDownstream_Dummy_Nodeまでのコーン上ではない）と、αとの間の正確な効果も同様に計算される。
【０１３２】
図２９に示されるように、βがアグレッサである場合、固定のビクティムの相互作用は正確な結果を用いる。既に分析されたビクティムに対する効果を環境の効果として扱い、また効果のループを可能にすることはクロストーク対応のＳＴＡに続く。
【０１３３】
ビクティムβをビクティムとして前に説明したときに、ビクティムβに影響する共通の移動及び中間の効果が既に説明されたので、環境の効果としての処理は受理可能である。今考慮する必要のあるただ１つの効果は、ビクティムのアグレッサ（つまりβ自身）に対する中間の効果である。βに作用する中間の効果は、パスβが弱められる第１又は第２のアグレッサ上であるか、第１又は第２のビクティムパスであるかに関わらず、ＬＡＴ↓とＥＡＴ↑を生み出す。ダウンストリームのビクティム及びまだ解析されていないビクティムに対する効果は、コーンを横断する間にこれらのビクティムに遭遇する場合に扱われる。アップストリームのビクティムに対する効果は、常にＮＲＮ型であり、環境の効果として扱う。
【０１３４】
図３０に示されるように、βがビクティムである場合、固定又は以前に解析されたアグレッサとβとの間の全ての相互作用の正確な結果を計算する。
【０１３５】
まだ解析されていないパス上のアグレッサを移動させることは、それらのパスを刺激するαと同じぐらいに移動するとみなし、そのため中間の効果(それはこの時点で未知である)を無視する。中間の効果は、環境の効果のために考慮され、そして移動するアグレッサをビクティムとして解析する。中間の効果は、求めるゴールへの到着に有用である。
【０１３６】
「アルゴリズムの説明」
図４６及び図４７は、本発明の実施の形態によるクロストークの軽減方法を説明するためのフローチャートである。プロセスは、クリティカルパスのアップストリームにおいて開始し、パスの各部分を変更する。グリッチ（glitch）が生じる場合には、この方法ではクロストークを軽減できない。従って、本発明では、ここではグリッチがないことを仮定して説明する。
【０１３７】
最初のステップＳ１では、上述のようにタイミンググラフを生成する。ステップＳ１で生成されたタイミンググラフに基づいて、次のステップＳ２で、初期化ステップを実行し、そこで短縮することのできる最長のパスを計算する。次のステップＳ３では、パスの長さ、クロック期間（clock period）及びセットアップ要求時間（setup requirement time）を比較する（最長のパスのクロック期間への長さとセットアップ時間を比較する）。一度比較が実行されたならば、ステップＳ４においてセットアップ要求時間妨害（setup requirement time violation）が生じたかどうか判定する。そうでない場合には、クリティカルパスを短くする必要がないので、後で説明するステップＳ８〜Ｓ１３を実行する。
【０１３８】
しかし、セットアップ要求時間妨害が生じたことがステップＳ４で判定された場合、ステップＳ５において、パスの短縮が可能であると決定する。パスの短縮が不可能である場合には、後で説明するステップＳ８〜Ｓ１３を実行する。しかし、パスの短縮が可能である場合には、ステップＳ６において、ビクティムの強化又はアグレッサを弱めることを行なう。他のパスに対する影響を回避することがより直接のアプローチであるため、ビクティムの強化を、アグレッサを弱めることよりも先に試みることとする。セットアップ要求時間妨害においては、パスが長過ぎることに問題である。従って、ステップＳ６ではパスを短縮する。
【０１３９】
ステップＳ７では、タイミンググラフをステップＳ６において行なわれた変更に基づいて再計算する。そしてステップＳ３からステップＳ７までの処理を、セットアップ要求時間妨害が発生しない（つまり、ステップＳ４において「ＮＯ」である）か、又はパスを更に短縮することができない（つまり、ステップＳ５において「ＮＯ」である）状態に達するまで、繰り返し実行する。一度このいずれかが（ステップＳ４又はステップＳ５における「ＮＯ」）生じたならば、下に記述するように、その後ホールド要求時間妨害（hold requirement time violations）を扱うために延長する可能なパスを、ステップＳ８〜ステップＳ１３において考慮する。ホールド要求時間妨害においては、パスが短過ぎることに問題があるため、その問題の発生したパスを延長する。
【０１４０】
ステップＳ１３では、初期化ステップを実行する。また、延長可能な最短のパスを決定する。その後、ステップＳ８において、パスの長さ、クロック期間及びホールド要求時間を比較する（最短のパスのクロック期間への長さとホールド要求時間を比較する）。ステップＳ９では、ホールド要求時間妨害があるかどうかを判定する。ホールド要求時間妨害がない場合には、パス延長を実行する必要はないため、ここでの処理を終了する。しかし、ホールド要求時間妨害がある場合には、ステップＳ１０に進み、そのパスの延長が可能であるかどうかを判定する。もしパスを延長することができない場合には、最良のクロストークの軽減が実現されたとして、このプロセスを終了する。
【０１４１】
しかし、パスが延長できるとステップＳ１０において判定された場合には、ステップＳ１１に進み、ビクティムの強化又はアグレッサを弱めることによりパスを延長する。前に注意された理由のために、ここではビクティムの強化を、アグレッサを弱めることよりも先に試みる。一度ステップＳ１１が収容すると、その後タイミンググラフをステップＳ１１で行なわれた変更を組込むために再計算する。ステップＳ８からステップＳ１２までの処理は、ステップＳ９又はステップＳ１０のいずれかにおいて「ＮＯ」となるまで繰り返し実行し、いずれかにおいて「ＮＯ」となった場合には処理を終了する。
【０１４２】
上述の方法では、セットアップ妨害がより一般的なので、セットアップ妨害をホールド妨害に先立って解析している。また、セットアップ妨害修正のために行なわれた変更は、ホールド妨害用のパスを延長するために否定的に影響することはない。また本発明は２段階のアプローチを取り、セットアップ時間妨害とホールド要求時間妨害との異なる選択をαのために行ない妨害を修正している。しかし、本発明は上述の手続きに制限されるものではない。例えば、セットアップ時間妨害とホールド要求時間妨害のための処理を実行する順番を逆にしたり、またこの一方のみを実行することとしてもよい。
【０１４３】
図３１は、クロストークの短縮（Mitigate_Crosstalk）のトップレベルの手続きを示し、まずＬＡＴの最長のパスLAT_longest_pathsと、ＥＡＴの最短のパスEAT_shortest_pathsを見つける。セットアップ妨害及びホールド妨害のそれぞれについては、セットアップ時間又はホールド時間に遭遇するまで、繰り返しのループを継続しパスの短縮又は延長を行なうか又は変更を行なわない。前の注意のように、セットアップ妨害及びホールド妨害に対して、ビクティムの強化を、アグレッサを弱めることよりも前に試みる。ビクティムの強化が遅延を縮小するの対して、逆にアグレッサを弱めることは遅延を増加させるが、この遅延の増加は目標を達成するための将来の繰り返しにおいて実行されないかもしれない。
【０１４４】
図３２の本発明の実施の形態に示されるように、αを調べるLook_for_αは、強化する又は弱める対象の候補（それらはステップＳ６及びＳ１１を実行するために使用される）を捜すためにMitigate_Crosstalkによって呼ばれる。Look_for_αは、ダウンストリームダミーノードDownstream_Dummy_Nodeからその探索を始める。従って、最新のエッジ（つまり、ラッチに最も接近しているエッジ）が、最初に考慮されαであるとみなされる。αが分岐（fork）と結合（join）との間に位置しないので、分岐や結合との遭遇は全て回避される。一度強さを変更する候補が見つかれば（つまり、エッジは可能な限り強いわけではない）、ビクティムを強くするための最小の強さ（又はアグレッサを弱めるための最大の強さ）として、現在のmovement_thresholdの上へ（下へ）全体的な移動を引き起こし、かつ現在の強さより大きい（より小さい）ものが選択される。
【０１４５】
ビクティムパスが活発な場合、まず移動の出発点Movement_thresholdを、ビクティムのパスがアクティブの場合に「０」にセットし、アグレッサの弱められたパス（aggressor weaken paths）がアクティブの場合に大きな正の数にセットする。必要な回避の回数が増加すると共に、Movement_thresholdは増加する。
【０１４６】
回避は、パスを弱めるアグレッサ（aggressor weakening paths）ではなくビクティムのパスに許可される。これは、パスを弱めるアグレッサは、パスに沿った任意の地点で前方又は後方へのネット移動を行なうことができるので、回避はこの情況において意味をほとんど持たないからである。
【０１４７】
movement_thresholdを満たす強さを見つけることができない場合には、新しいグリッチのビクティム(アグレッサ)を生成するか、又は必要とされる移動を生成できる単なるサイジングやバッファを用いた代案がなく、強さの変更の可能性strength_change_possibleをリセットとするかのいずれかとなる。
【０１４８】
セットアップ妨害又はホールド妨害がアクティブであるかどうかに基づいて、ちょうど新しいLAT_Longest_Path又はEAT_Shortest_Pathを生じさせた移動を引き起こす最小の(最大の)強さに、強さを初期化する。強さの変更が可能であるとして、αはアグレッサ及びビクティムの両方として評価される。
【０１４９】
次に、コーンの横断（traversal）が開始する。もしその時弱くされたアグレッサWeaken_Aggressorである場合には、αａにより始まるコーンは、Evaluate_α_As_Victimにより解析される（図３４を参照）。このコーンは、第２パスの短縮又は延長が可能であって、第１パスが第２パスと第１パスとが結合するそのゴールに到着する能力に影響するので、ビクティムに関連したコーンの前に解析する。
【０１５０】
weaken_aggressorのコーン（少なくとも１つある場合に）が解析された後、αｖのコーンの解析を開始する。そして、横断が成功（β_proceed==TRUE）である場合、αの強さの変更及びβの動作は相互作用の基本原則の基準を満たし、また最長のパスの短縮又は最短のパスの延長ができることが保証される。
【０１５１】
図３３に示されるように、αのアグレッサとしての評価Evaluate_α_As_Aggressorは、αとそのビクティムの間の相互作用を決定するために、本発明の図２７の中で概説された実施の形態の手続きに従う。動的にＥＡＴ及びＬＡＴの両方が更新される。単一のビクティムに対する多数のアグレッサの蓄積された影響を説明するための技術の詳細は、本発明の範囲外である。また、本発明のクロストーク軽減アルゴリズムは他の技術に依存するものではない。また本発明において、それぞれの効果は単純に重ね合わせることができる。
【０１５２】
いくつかの手続きに現われる擬似コードのセグメントは、遭遇した特定のビクティムへ移動したアグレッサの全てを決定した後に現われる。トレースが、上述のように実行される。図４０において示されるように、トレースの処理は、最初に現在のアグレッサの移動及び（又は）強さの変更による、特定のビクティムのＬＡＴ及びＥＡＴ動的遅延変更を決定する。
【０１５３】
これらの変更がＬＡＴ↓とＥＡＴ↑のネットの変更を生み出す場合、トレースは成功しており、トレースツリー（trace tree）の現在のサブツリー（subtree）に沿って続けたトレースを終了することができる。
【０１５４】
もしＬＡＴ↑又はＥＡＴ↓の場合には、ダウンストリームのエッジへの影響のない変更を吸収するスラッグがエッジに十分である。もしダウンストリームのエッジの相互作用が許可されれば、トレースは非常により複雑になり、回路の残りの大部分を含むことになる。スラックが十分にある場合には、トレースは現在のサブツリーと他のサブツリーを検査し続けることができ、そうでなければトレースが完全に失敗することになる。
【０１５５】
Evaluate_α_As_Aggressorに戻ると、トレースがその時成功した場合には、回避は現在のビクティムを提供するためには必要でなく、αの他のビクティムを検査できる。しかし、回避が必要な場合には、図３９に示されるようにUpdate_Movement_Thresholdがmovement_thresholdを更新する。
【０１５６】
ビクティムの各アグレッサのために、Update_Movement_Thresholdは、必要な回避の量を調べ、これを達成するようにmovement_thresholdを変更する。図１８から図２１の事例分析がＢＹ又はＣＢＹの決定を生む場合、更なる移動はＬＡＴ↑又はＥＡＴ↓を引き起こす。しかし、遅延変更曲線（ＤＣＣ）の向かい側に回避することによって、更なる移動は希望の結果であるＬＡＴ↓又はＥＡＴ↑を引き起こす。ビクティムに対する全体的な影響は個々のアグレッサの影響の重ね合せであるので、状況の改善は、ＮＲＮである相互作用によるＬＡＴ↓又はＥＡＴ↑のように全体的なαの移動を増加させることや、ＢＹ又はＣＢＹの相互作用を回避することによる。
【０１５７】
Update_Movement_Thresholdは、回避の要求により最小から最大までのＢＹ又はＣＢＹを生む相互作用を最初に命じる。その後、それらの動作はシミュレートされ、希望する効果が得られるまでＬＡＴ及びＥＡＴに対する全体的な影響を計算する。
【０１５８】
これにより、必要な移動と引き返すステップが増え、Binary_Search_For_Movement_Thresholdは、正確な最小のＬＡＴ↓又はＥＡＴ↑を得るために最小の移動の量を必要とする。
【０１５９】
図３４に示されるLook_for_αに戻ると、Evaluate_α_As_Victimは、図２８に概説された手続きに従いαとそのアグレッサの間の相互作用を決定する。もし全体的にＬＡＴ↓又はＥＡＴ↑ならば、トレースとおそらくmovement_thresholdの更新が実行される。
【０１６０】
Evaluate_β_Pathは、αのダウンストリームから行き先の評価するβに前進する。分岐に遭遇する場合には、その分岐の生じるノードでスタックに格納する。全ての第２パスは最初に調査され、その後第１パスを調査する。第２パスにおける選択は任意である。
【０１６１】
図３５及び図３６に示されるように、Evaluate_β_Pathでは、図３０で説明された手続きにより、Evaluate_β_As_Victimがβとそのアグレッサの間の相互作用を決定する。全体的にＬＡＴ↑又はＥＡＴ↓ならば、トレースとおそらくmovement_thresholdの更新が実行される。
【０１６２】
Evaluate_β_pathに戻ると、ビクティムとしてのβの評価が成功しかつ回避が要求されない場合には、Evaluate_β_As_Aggressorはこのβの調査を終了するために呼ばれる。この手続きは、図２９の中で説明された手続きに従い、トレースとおそらくmovement_thresholdの更新が実行される。Next_Unexplored_Edgeは、βの評価を継続するかどうか決めるために呼ばれる。βがＮＵＬＬの場合には、Downstream_Dummy_Nodeに到達し、パスの終端に成功し、αの移動を保持することができる。βのデスティネーションノードで利用可能なスラックが、βが必要とする十分な移動をサポートできない場合にも、パスは終了することができる（図４１に示されるSlack_Terminate_Pathを参照）。この場合、ダウンストリームにβを移動する送信はなく、更にβをチェックする必要もない。これはクリティカルパスが変更され、成功した結果と考えられる。そして、Evaluate_β_Pathは、正しくLook_for_αに戻る。
【０１６３】
たとえβの強さが変更されなくとも、それはまだ移動し、アグレッサのような他の効果を備え、また同様にアグレッサとして影響する。従って、βは、ビクティムとアグレッサとのそれぞれに評価される。これは、αの場合と同じ個別の評価原理が該当する。
【０１６４】
Look_for_αにおいて、回避がβに必要でない場合には、ここでの処理は成功となる。αにおいて強さの変更が正しくできない場合や、新しいαの探索においてUpstream_Dummy_Nodeに遭遇した場合には、Look_for_αは不成功となる。回避が必要でありかつαの強さの変更が実行されることができた場合には、βの評価の新たなラウンドが新たな移動の量と共に開始される。
【０１６５】
「アルゴリズムの複雑さ」
本発明のクロストークの軽減（Mitigate_Crosstalk）の複雑さが図４２に示される。複雑さの大部分はβのチェックにある。回避がクリティカルパス上で要求された場合、クリティカルパス未満の移動の量は相互作用の基本原則の基準を満たさない。αのサイジングの数が約１０未満に制限されているので、およそ１０のβのチェックが必要である。
【０１６６】
この観察と、βがクリティカルパスからコーンの中に常にあり、その頻繁なスラックの制限がβの動作を止め、更なるサイズ変更を終了する事実とを組み合わせると、複雑さはその評価未満であることが意味される。更に、スラックの制限がαのサイズの増加や縮小のあいまいさを増加させる。
【０１６７】
「クロストークの軽減の適応」
図４３は、Mitigate_Crosstalk（クロストーク軽減部１０）の適応例を示す。
【０１６８】
上に議論されるように、Mitigate_Crosstalk（クロストーク軽減部１０）によるクリティカルパスの短縮又は延長の後の、クロストーク対応の静的タイミング解析ＳＴＡへのいくつかの呼び出しは、タイミングウィンドウを更新する必要があった。Mitigate_Crosstalk（クロストーク軽減部１０）とノイズ対応タイミング解析部３０（noise aware timing analyzer）との間の通信のためには、どのような便利なフォーマットを使用してもよく、またＳＤＦは現在タイミング情報を交換するための業界基準である。
【０１６９】
バッファリング又はゲートサイジング（gate sizing）がどのように変わるかを決定した後、この決定の情報を、エンジニアリングチェンジオーダ（ＥＣＯs：engineering change orders）により、配置及びルーティングソフトウェア２０（placement and routing tools）に送信することができる。ワイヤー・ネット（wire net）の長さやカップリングの決定に必要なレイアウト情報は、こうした情報を交換するための業界基準であるＤＳＰＦ又はＳＰＥＦを使用して送信することができる。
【０１７０】
ここでこれに制限するのではないが、バッファ挿入は本実施の形態にはない。しかし、本発明の他の実施の形態として、バッファ挿入を、ビクティムを強くすること（つまり、バッファによって運ばれるセグメントに信号線を分割する）のために使用することができる。同様にバッファの除去を、アグレッサを弱めるために使用できる。また、強化できるビクティムや弱めることのできるアグレッサを決定する前述の方法は、個々のバッファで駆動される信号線のセグメントに適用することができる。
【０１７１】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０１７２】
【発明の効果】
以上説明したように本発明によれば、以下のような効果が達成される。例えば、これに制限するのではないが、本発明は遅延不確実性によって影響を受けた特定のパスを軽減の目標とするので、ノイズバランシング（noise balancing）に基づいた従来技術のブランケット（blanket）アプローチより優秀である。すなわち、本発明は、変更の軽減（mitigating changes）が、セットアップ妨害の場合の遅延を縮小できホールド妨害の場合の遅延を増加できることを保証する。本発明は更に、軽減による副作用が常に改善を生み出すか、又は軽減による変化がないことを保証する。
【０１７３】
クリティカルパスについての知識は、弱めるべきアグレッサと強化するビクティムと、これらの強さを全クリティカルパス及び第２のパスに対する影響を考慮してどのように変更すべきかを、正確に示すために使用することができる。その方法は２つの長所を持つ。１つは、クリティカルパスに専念することによって、従来のブランケットなアプローチにおいて、必要な計算上の資源が不必要で効果がない強さの変更を生むために要求されるという、計算上の資源の浪費の問題を縮小できる。
【０１７４】
２番目に、全ての強さの変更が、希望するゴールに近づくか又は変更を実行しないことを保証する。対照的に、従来の技術のブランケット（blanket）の変更はゴールに近づくことが保証されていない。
【０１７５】
更に、正確な減速及び加速の効果ついての知識が、アグレッサ及びビクティムが関連して切り替わる度に、クロストーク軽減に遅延変更曲線（ＤＣＣ）を適用することによって、従来技術のスイッチ要因により遅延を評価する方法よりもより正確な結果を産出する。
【０１７６】
更に、本発明の新しい修正済の遅延変更曲線（ＤＣＣ）は、強化できるビクティムや弱めることのできるアグレッサを見つける可能性を増加させる。修正済の遅延変更曲線（ＤＣＣ）は、更に相互作用の規則の小さな集合を可能し、そのため本発明の他の利点としてソフトウェア生成の負担を緩和することができる。修正済の遅延変更曲線（ＤＣＣ）は、更に正確なビクティム及びアグレッサ位置を、最悪の場合の減速又は加速を想定して決定することができることを保証する。
【０１７７】
本発明の他の利点は、他の非クリティカルパスを計算する必要に基づいた、クロストーク軽減の必要条件を縮小する処理を含む。更に、本発明の方法を用いると意図したゴールに接近して移動することが保証されるので、従来のブランケットな方法における修正の割合を改善している。
【図面の簡単な説明】
【図１】  本発明の一実施の形態による速度低下の場合の修正したＤＣＣを示す図である。
【図２】  上記実施の形態における荒れた場合の修正したＤＣＣを示す図である。
【図３】  上記実施の形態における最終到着時刻（ＬＡＴ）の修正のケース１を説明するための図である。
【図４】  上記実施の形態における最終到着時刻（ＬＡＴ）の修正のケース２を説明するための図である。
【図５】  上記実施の形態における最終到着時刻（ＬＡＴ）の修正のケース３を説明するための図である。
【図６】  上記実施の形態における最終到着時刻（ＬＡＴ）の修正のケース４を説明するための図である。
【図７】  上記実施の形態における最終到着時刻（ＬＡＴ）の修正のケース５を説明するための図である。
【図８】  上記実施の形態における最前到着時刻（ＥＡＴ）修正のケース１を説明するための図である。
【図９】  上記実施の形態における最前到着時刻（ＥＡＴ）修正のケース２を説明するための図である。
【図１０】  上記実施の形態における最前到着時刻（ＥＡＴ）修正のケース３を説明するための図である。
【図１１】  上記実施の形態における最前到着時刻（ＥＡＴ）修正のケース４を説明するための図である。
【図１２】  上記実施の形態における最前到着時刻（ＥＡＴ）修正のケース５を説明するための図である。
【図１３】  上記実施の形態におけるタイミンググラフを示す図である。
【図１４】  上記実施の形態におけるビクティムの強化方法を示す図である。
【図１５】  上記実施の形態におけるアグレッサの弱化方法を示す図である。
【図１６】  上記実施の形態における強さの変更の一例を示す図である。
【図１７】  上記実施の形態における移動のみの場合の一例を示す図である。
【図１８】  上記実施の形態における後方への移動を減速する場合を示す図である。
【図１９】  上記実施の形態における後方への移動を加速する場合を示す図である。
【図２０】  上記実施の形態における前方への移動を減速する場合を示す図である。
【図２１】  上記実施の形態における前方への移動を加速する場合を示す図である。
【図２２】  上記実施の形態における図１８〜図２１において用いられた記号を説明する図である。
【図２３】  上記実施の形態におけるビクティムがセットアップ時間妨害のために強くなる場合の一例を示す図である。
【図２４】  上記実施の形態におけるアグレッサがセットアップ時間妨害のために弱くなる場合の一例を示す図である。
【図２５】  上記実施の形態におけるビクティムがホールド時間妨害のために強くなる場合の一例を示す図である。
【図２６】  上記実施の形態におけるアグレッサがホールド時間妨害のために弱くなる場合の一例を示す図である。
【図２７】  上記実施の形態におけるαのアグレッサとしての解析の一例を示す図である。
【図２８】  上記実施の形態におけるαのビクティムとしての解析の一例を示す図である。
【図２９】  上記実施の形態におけるβのアグレッサとしての解析の一例を示す図である。
【図３０】  上記実施の形態におけるβのビクティムとしての解析の一例を示す図である。
【図３１】  上記実施の形態におけるクロストーク軽減方法を実行するためのトップレベルの処理を示す図である。
【図３２】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３３】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３４】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３５】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３６】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３７】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３８】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図３９】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図４０】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図４１】  上記実施の形態におけるクロストーク軽減方法を実行するための追加の処理を示す図である。
【図４２】  上記実施の形態における複雑さを示す図である。
【図４３】  上記実施の形態における適応例を示す図である。
【図４４】  上記実施の形態の説明において用いる記号の説明を示す図である。
【図４５】  上記実施の形態の説明において用いる記号の説明を示す図である。
【図４６】  上記実施の形態におけるクロストーク軽減の動作を説明するためのフローチャートである。
【図４７】  上記実施の形態におけるクロストーク軽減の動作を説明するためのフローチャートである。
【図４８】  従来の集積回路のアグレッサ及びビクティムの一例を示す図である。
【図４９】  信号の変化のクロストークによる減速を示す図である
【図５０】  信号の変化のクロストークによる加速を示す図である。
【図５１】  減速を例証する遅延変更曲線（ＤＣＣ）を示す図である。
【符号の説明】
１０  クロストーク軽減部（Mitigate_Crosstolk）
２０  配置及びルーティングソフトウェア
３０  ノイズ対応タイミング解析部
【図１】
0003800329.tif 000004
【図２】
0003800329.tif 000005
【図３】
0003800329.tif 000006
【図４】
0003800329.tif 000007
【図５】
0003800329.tif 000008
【図６】
0003800329.tif 000009
【図７】
0003800329.tif 000010
【図８】
0003800329.tif 000011
【図９】
0003800329.tif 000012
【図１０】
0003800329.tif 000013
【図１１】
0003800329.tif 000014
【図１２】
0003800329.tif 000015
【図１３】
0003800329.tif 000016
【図１４】
0003800329.tif 000017
【図１５】
0003800329.tif 000018
【図１６】
0003800329.tif 000019
【図１７】
0003800329.tif 000020
【図１８】
0003800329.tif 000021
【図１９】
0003800329.tif 000022
【図２０】
0003800329.tif 000023
【図２１】
0003800329.tif 000024
【図２２】
0003800329.tif 000025
【図２３】
0003800329.tif 000026
【図２４】
0003800329.tif 000027
【図２５】
0003800329.tif 000028
【図２６】
0003800329.tif 000029
【図２７】
0003800329.tif 000030
【図２８】
0003800329.tif 000031
【図２９】
0003800329.tif 000032
【図３０】
0003800329.tif 000033
【図３１】
0003800329.tif 000034
【図３２】
0003800329.tif 000035
【図３３】
0003800329.tif 000036
【図３４】
0003800329.tif 000037
【図３５】
0003800329.tif 000038
【図３６】
0003800329.tif 000039
【図３７】
0003800329.tif 000040
【図３８】
0003800329.tif 000041
【図３９】
0003800329.tif 000042
【図４０】
0003800329.tif 000043
【図４１】
0003800329.tif 000044
【図４２】
0003800329.tif 000045
【図４３】
0003800329.tif 000046
【図４４】
0003800329.tif 000047
【図４５】
0003800329.tif 000048
【図４６】
0003800329.tif 000049
【図４７】
0003800329.tif 000050
【図４８】
0003800329.tif 000051
【図４９】
0003800329.tif 000052
【図５０】
0003800329.tif 000053
【図５１】
0003800329.tif 000054