(57)【要約】【解決手段】集積回路を最適化及び／設計するための方法及びシステムを提供する。集積回路（ＩＣ）を設計するプロセスの一部として、第１セットの配線リソースを使用して、ＩＣ表現上で接続を経路指定し、第１セット内の配線リソースが一旦経路指定に使用されたら、配線リソースに使用済みとマーキングする段階と、前記表現で第２セットの配線リソースを使用して、前記第２セット内の配線リソースが以前に接続を経路指定するのに使用されているか否かを確認すること無く、ＩＣ上の接続の経路指定を行う段階と、を含んでおり、第２セットの配線リソースは、平均で、物理的な寸法が、第１セット内の配線リソースとは異なっている。ＩＣを最適化及び／又は設計するための他の方法及びシステムについても説明されており、更に、システムに１つ又はそれ以上これらの方法を実行させる実行可能なプログラム命令が入っている機械読み取り可能な媒体についても説明されている。【選択図】図９
2009536376.tif 000002
【特許請求の範囲】
【請求項１】
機械で実施される方法において、
集積回路（ＩＣ）を設計するプロセスの一部として、第１セットの配線リソースを使用して前記ＩＣの表現上で接続を経路指定し、前記第１セット内の前記配線リソースが一旦経路指定に使用されたら、配線リソースに使用済みとマーキングする段階と
前記ＩＣの表現内で第２セットの配線リソースを使用して、前記第２セット内の配線リソースが以前に接続を経路指定するのに使用されているか否かを確認すること無く、前記ＩＣ上の接続を経路指定する段階と、から成り、
前記第２セットの配線リソースは、平均で、物理的な寸法が前記第１セットの配線リソースとは異なっている、方法。
【請求項２】
前記第２セットの前記配線リソースは、平均で、前記第１セット内の前記配線リソースより長く、前記第２セットを使用する経路指定は、前記第２セット内の前記配線リソースに、これらの配線リソースが一旦使用されたときに、予約済みとマーキングすること無く実行される、請求項１に記載の方法。
【請求項３】
機械で実施される方法において、
設計されている集積回路（ＩＣ）の表現内で駆動コンポーネントのファンアウトを確定する段階と、
前記駆動コンポーネントに関して、前記ＩＣの前記表現内で、前記駆動コンポーネントによって駆動されるロードを確定する段階と、
前記ロードを前記駆動コンポーネントに接続するために使用される既存の配線リソースの使用を確定する段階と、
前記既存の配線リソースの使用、前記駆動コンポーネントのファンアウト、及び前記駆動コンポーネントによって駆動されるロードに基づいて、前記ＩＣの設計を最適化する段階と、から成る方法。
【請求項４】
前記最適化する段階は、前記駆動コンポーネントを複製することによって前記駆動コンポーネントのファンアウトを減らすか否か判定する段階であって、前記複製は前記決定に応答して自動的に実行される、判定する段階を含んでいる、請求項３に記載の方法。
【請求項５】
機械で実施される方法において、
集積回路（ＩＣ）を設計するプロセスの一部として、ロードから駆動コンポーネントまでの経路指定ネットを確定して、前記駆動コンポーネントの複製版に利用できる場所を確定する段階と、
前記ＩＣの表現内に、前記経路指定ネットと前記利用できる場所とに基づいて、前記駆動コンポーネントの前記複製版を作成し、前記表現内で、前記複製版と前記ロードの間に接続を作成する段階と、から成る方法。
【請求項６】
前記駆動コンポーネントからの同じ経路指定ネット内にあり、前記ロードと同じ区域内にある他のロードを、前記複製版に接続するか否か判定する段階を更に含んでいる、請求項５に記載の方法。
【請求項７】
機械で実施される方法において、
集積回路（ＩＣ）を設計するプロセスの一部として、前記ＩＣの表現内でコンポーネントを複製し、それを、前記コンポーネントの出力と等価な出力を有する複製コンポーネントと標示する段階と、
前記表現内で、前記複製コンポーネントと、前記複製コンポーネントのロードとの間の接続を経路指定する段階と、
前記複製コンポーネントを、前記コンポーネントの少なくとも１つの既存のロードを駆動するソースとして使用するか否か判定する段階と、から成る方法。
【請求項８】
前記判定する段階は、前記指定経路及び接続が前記表現内に作成され、前記複製コンポーネントを、前記複製コンポーネントとは切断されている前記少なくとも１つの既存のロードに接続した後で行われる、請求項７に記載の方法。
【請求項９】
機械で実施される方法において、
配線遅延に関する値を、集積回路の表現内の配線網の幾何学形状に基づいて調整すべきか否か判定する段階と、
前記幾何学形状が第１型式であれば、前記値を調整する段階と、
前記ＩＣを設計するためのプロセスの中で、調整後の値に基づいて指定経路の決定を下す段階と、から成る方法。
【請求項１０】
実行可能なプログラム命令が入っている機械読み取り可能媒体であって、前記プログラム命令がデータ処理システムによって実行されると、前記データ処理システムが、以下の方法、即ち、
集積回路（ＩＣ）を設計するプロセスの一部として、第１セットの配線リソースを使用して前記ＩＣの表現上で接続を経路指定し、前記第１セット内の前記配線リソースが一旦経路指定に用いられたら、配線リソースに使用済みとマーキングする段階と、
前記ＩＣの表現内で第２セットの配線リソースを使用して、前記第２セット内の配線リソースが以前に接続を経路指定するのに使用されているか否かを確認すること無く、前記ＩＣ上の接続を経路指定する段階と、から成り、
前記第２セットの配線リソースは、平均で、物理的な寸法が前記第１セットの配線リソースとは異なっている、方法を実行するようになっている媒体。
【請求項１１】
前記第２セットの前記配線リソースは、平均で、前記第１セット内の前記配線リソースより長く、前記第２セットを使用する経路指定は、前記第２セット内の前記配線リソースに、これらの配線リソースが一旦使用されたときに、予約済みとマーキングすること無く実行される、請求項１０に記載の媒体。
【請求項１２】
実行可能なプログラム命令が入っている機械読み取り可能媒体であって、前記プログラム命令がデータ処理システムによって実行されると、前記データ処理システムが、以下の方法、即ち、
設計されている集積回路（ＩＣ）の表現内で駆動コンポーネントのファンアウトを確定する段階と、
前記駆動コンポーネントに関して、前記ＩＣの前記表現内で、前記駆動コンポーネントによって駆動されるロードを確定する段階と、
前記ロードを前記駆動コンポーネントに接続するために使用される既存の配線リソースの使用を確定する段階と、
前記既存の配線リソースの使用、前記駆動コンポーネントのファンアウト、及び前記駆動コンポーネントによって駆動されるロードに基づいて、前記ＩＣの設計を最適化する段階と、から成る方法を実行するようになっている媒体。
【請求項１３】
前記最適化する段階は、前記駆動コンポーネントを複製することによって前記駆動コンポーネントのファンアウトを減らすか否か判定する段階であって、前記複製は前記決定に応答して自動的に実行される、判定する段階を含んでいる、請求項１２に記載の媒体。
【請求項１４】
実行可能なプログラム命令が入っている機械読み取り可能媒体であって、前記プログラム命令がデータ処理システムによって実行されると、前記データ処理システムが、以下の方法、即ち、
集積回路（ＩＣ）を設計するプロセスの一部として、ロードから駆動コンポーネントまでの経路指定ネットを確定して、前記駆動コンポーネントの複製版に利用できる場所を確定する段階と、
前記ＩＣの表現内に、前記経路指定ネットと前記利用できる場所とに基づいて、前記駆動コンポーネントの前記複製版を作成し、前記表現内で、前記複製版と前記ロードの間に接続を作成する段階と、から成る方法を実行するようになっている媒体。
【請求項１５】
前記方法は、前記駆動コンポーネントからの同じ経路指定ネット内にあり、前記ロードと同じ区域内にある他のロードを、前記複製版に接続するか否か判定する段階を更に含んでいる、請求項１４に記載の媒体。
【請求項１６】
実行可能なプログラム命令が入っている機械読み取り可能媒体であって、前記プログラム命令がデータ処理システムによって実行されると、前記データ処理システムが、以下の方法、即ち、
集積回路（ＩＣ）を設計するプロセスの一部として、前記ＩＣの表現内でコンポーネントを複製し、それを、前記コンポーネントの出力と等価な出力を有する複製コンポーネントと標示する段階と、
前記表現内で、前記複製コンポーネントと、前記複製コンポーネントのロードとの間の接続を経路指定する段階と、
前記複製コンポーネントを、前記コンポーネントの少なくとも１つの既存のロードを駆動するソースとして使用するか否か判定する段階と、から成る方法を実行するようになっている媒体。
【請求項１７】
前記判定する段階は、前記指定経路及び接続が前記表現内に作成され、前記複製コンポーネントを、前記複製コンポーネントとは切断されている前記少なくとも１つの既存のロードに接続した後で行われる、請求項１６に記載の媒体。
【請求項１８】
実行可能なプログラム命令が入っている機械読み取り可能媒体であって、前記プログラム命令がデータ処理システムによって実行されると、前記データ処理システムが、以下の方法、即ち、
配線遅延に関する値を、集積回路の表現内の配線網の幾何学形状に基づいて調整すべきか否か判定する段階と、
前記幾何学形状が第１型式であれば、前記値を調整する段階と、
前記ＩＣを設計するためのプロセスの中で、調整後の値に基づいて指定経路の決定を下す段階と、から成る方法を実行するようになっている媒体。
【請求項１９】
データ処理システムにおいて、
集積回路（ＩＣ）を設計するプロセスの一部として、第１セットの配線リソースを使用して前記ＩＣの表現上で接続を経路指定し、前記第１セット内の前記配線リソースが一旦経路指定に使用されたら、配線リソースに使用済みとマーキングするための手段と、
前記ＩＣの表現内で第２セットの配線リソースを使用して、前記第２セット内の配線リソースが以前に接続を経路指定するのに使用されているか否かを確認すること無く、前記ＩＣ上の接続を経路指定するための手段と、を備えており、
前記第２セットの配線リソースは、平均で、物理的な寸法が前記第１セットの配線リソースとは異なっている、データ処理システム。
【請求項２０】
データ処理システムにおいて、
設計されている集積回路（ＩＣ）の表現内で駆動コンポーネントのファンアウトを確定するための手段と、
前記駆動コンポーネントに関して、前記ＩＣの前記表現内で、前記駆動コンポーネントによって駆動されるロードを確定するための手段と、
前記ロードを前記駆動コンポーネントに接続するために使用される既存の配線リソースの使用を確定するための手段と、
前記既存の配線リソースの使用、前記駆動コンポーネントのファンアウト、及び前記駆動コンポーネントによって駆動されるロードに基づいて、前記ＩＣの設計を最適化するための手段と、を備えているデータ処理システム。
【請求項２１】
データ処理システムにおいて、
集積回路（ＩＣ）を設計するプロセスの一部として、ロードから駆動コンポーネントまでの経路指定ネットを確定して、前記駆動コンポーネントの複製版に利用できる場所を確定するための手段と、
前記ＩＣの表現内に、前記経路指定ネットと前記利用できる場所とに基づいて、前記駆動コンポーネントの前記複製版を作成し、前記表現内で、前記複製版と前記ロードの間に接続を作成するための手段と、を備えているデータ処理システム。
【請求項２２】
データ処理システムにおいて、
集積回路（ＩＣ）を設計するプロセスの一部として、前記ＩＣの表現内でコンポーネントを複製し、それを、前記コンポーネントの出力と等価な出力を有する複製コンポーネントと標示するための手段と、
前記表現内で、前記複製コンポーネントと、前記複製コンポーネントのロードとの間の接続を経路指定するための手段と、
前記複製コンポーネントを、前記コンポーネントの少なくとも１つの既存のロードを駆動するソースとして使用するか否か判定するための手段と、を備えているデータ処理システム。
【請求項２３】
データ処理システムにおいて、
配線遅延に関する値を、集積回路の表現内の配線網の幾何学形状に基づいて調整すべきか否か判定するための手段と、
前記幾何学形状が第１型式であれば、前記値を調整するための手段と、
前記ＩＣを設計するためのプロセスの中で、調整後の値に基づいて指定経路の決定を下すための手段と、を備えているデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概括的には、回路設計の分野に関し、より具体的には、ハードウェア記述言語を通した自動回路設計合成に関する。
【背景技術】
【０００２】
本出願は、２００６年３月２４日出願の同時係属米国仮特許出願第６０／７８５，４４３号に関係しており、同仮出願の出願日の恩典を請求し、同仮出願を参考文献としてここに援用する。
【０００３】
集積回路（ＩＣ）の回路設計では、設計者は、しばしばコンピュータ支援設計技法を利用する。ハードウェア記述言語（ＨＤＬ）として知られている標準的な言語は、複雑な回路の設計及びシミュレーションを支援する目的で回路を記述するために開発されてきた。ＶＨＤＬやVerilogの様な幾つかのＨＤＬが、業界の標準として徐々に発展した。ＶＨＤＬとVerilogは、抽象的なデータ型式を使って、ハードウェアモデルを、ゲートレベル、レジスタ・トランスファ・レベル（ＲＴＬ）、又は行動レベルで定義できる汎用ハードウェア記述言語である。
【０００４】
ＨＤＬコンパイラを使って回路を設計する場合、設計者は、先ず回路要素をＨＤＬソースコードで記述し、次にソースコードをコンパイルして合成されたＲＴＬネットリストを作り出す。ＲＴＬネットリストは、回路要素の図式的表現に相当する。合成された回路要素の入っている回路は、しばしば、タイミング関係を改良し、不必要又は冗長な論理要素を削除するため、最適化される。その様な最適化は、通常、異なるゲート型式の置換、又は回路内のゲートの組み合わせ及び削除を伴う。図１は、目標アーキテクチャと呼ばれる所定のアーキテクチャを有するフィールドプログラマブルゲートアレイ（ＦＰＧＡ）の様な、或る型式のＩＣを設計するための代表的なフローを示している。演算１０１は、コンパイラがＩＣの記述（例えば、ＨＤＬで書かれた記述）を受け取ることを伴っており、コンパイラは、演算１０３で、ＨＤＬ記述からＲＴＬ記述への合成を実行する。演算１０５で、ＲＴＬ記述は、Xilinx  ＦＰＧＡのアーキテクチャの様な目標アーキテクチャにマップされ、目標アーキテクチャ内での最適化が実行される。最適化が完了すると、目標アーキテクチャのネットリストが作成される。ＩＣのコンピュータ支援設計のための様々な方法及びシステムについては、米国特許第６，４３８，７３５号、第６，４４９，７６２号、及び第６，９７３，６３２号に記載されており、それら全てを参考文献としてここに援用する。
【０００５】
図２は、ＩＣの設計を最適化するための先行技術による方法に関し更に詳しく示している。演算１５１で、或る特定のコンポーネントによって駆動されるロードが求められ、演算１５３で、それらのロードの内の最もクリティカルなロードが求められる。次に、特にクリティカルなコンポーネントが複製され（演算１５５）、最もクリティカルなロードが、複製されたクリティカルコンポーネントに接続される（演算１５７）。これは、配線網のソースのファンアウトを元のクリティカルなコンポーネントから少なくすることに繋がる。ロードがＩＣのタイミングの制約又は要件に悪影響を及ぼす場合（又は負のスラックを有している場合）は、ロードはクリティカルであるとみなされ、コンポーネントは、クリティカルなロードを駆動しているのでクリティカルであるとみなされる。次に、演算１５９で、ＩＣのスラックは再度計算され、スラックが改良されたか否か判定される（演算１６１）。スラックが改良されていなければ、複製は廃棄され（演算１６３）、処理は演算１５１へ戻る。スラックが改良されていれば、図２に示す様に、処理は演算１６１から演算１５１へ戻り、他のクリティカルコンポーネントを有する他のパスを最適化する。図３Ａ、図３Ｂ、及び図３Ｃは、図２の最適化法の例を示している。
【０００６】
図３Ａは、図１の方法に従って設計され、図２の方法に従って最適化された集積回路の少なくとも一部分を表わしている。設計は、図３Ａに示している段階では、集積回路の表現２０１に９個のスイッチマトリクス（ＳＭ）を含んでいる。スイッチマトリクスは、Xilinx社製のゲートアレイの様な或る型式のフィールドプログラマブルゲートアレイに使用される一般的な相互接続装置である。スイッチマトリクス２０２−２１０は、信号を受け取るロードに信号を出力するドライバコンポーネントの様な各種コンポーネントの相互接続に備えている。図３Ａに示している設計は、１個のドライバ２１５と７個のロードＬ１−Ｌ２を含んでいる。具体的には、ドライバ２１５は、図３Ａに示している様に、配線Ｗ１、Ｗ２、及びＷ３を含む経路指定ネットを通してロード２１６−２２２を駆動する。経路指定ネットは、ＩＣ上の既存の配線リソースであるこれら３本の配線を含んでいる。配線を接続しているスイッチマトリクス２０９上のスイッチは、ＳＷ１、ＳＷ２、及びＳＷ３と標示されており、ドライバのスイッチはＳＷＤと標示されている。この設計のクリティカルロードは、クリティカルな順にＬ１、Ｌ２、Ｌ３、Ｌ４であり、最もクリティカルなのがＬ１である。各ロード上のネットの遅延は、配線遅延、スイッチ遅延、及び各スイッチのファンアウトに依る。３本の配線がスイッチＳＷ１、ＳＷ２、ＳＷ３に伸びており、それらのキャパシタンスが配線遅延の一因となるので、スイッチＳＷＤのファンアウトは３である。ドライバＤ２１５からのネットの合計ファンアウトは７であるが、スイッチＳＷＤのルートファンアウトは３に過ぎない。スイッチＳＷＤのルートファンアウトを図３Ｂに更に詳しく示しているが、図３Ｂに示すように、ドライバコンポーネント２１５は、スイッチマトリクス２０９に入力を提供し、その入力をドライバ２３０が受け取り、ドライバ２３０は、スイッチＳＷＤの３つのパスゲート（２２５、２２６、２２７）を駆動する。各パスゲートは寄生キャパシタンスを有しており、その１例が、パスゲート２２５上の寄生キャパシタンス２３１として示されている。これらの寄生キャパシタンスは、ルートファンアウトで遅延を追加する。ドライバコンポーネント２１５が、フリップフロップ、ルックアップテーブル、又はデジタル論理回路を含む他の型式の論理の様な、多種多様な論理コンポーネントの内の１つでよいものと理解されたい。
【０００７】
上記の複製法は、既存の配線リソースを使ってどの様にネットを配線するかということには注意を払わず、ファンアウト、特にネットのルートのファンアウトを減らすことに専心している。例えば、クリティカルロードＬ１とＬ２を隔離することによってファンアウトを減らしたい場合は、ドライバＤを複製し、コピーされたドライバ２１５Ａが残りのロードを駆動するようにすることもできる。ドライバ２１５が駆動するネットのファンアウトの合計は２になり（７から減る）、ドライバ２１５Ａが駆動するネットのファンアウトの合計は５になる。これを図３Ｃに示している。しかしながら、遅延については、ドライバ２１５Ａが駆動するネットのルートの遅延は複製前と同じ３のままなので、クリティカルロードＬ３及びＬ４の遅延は殆ど変わらず、より速い配線Ｗ１を使ってＬ１とＬ２を接続しても、ロードＬ３及びＬ４を接続しているスイッチ２５４と配線Ｗ１Ａの遅延は大きくなる。
ここに述べる改良された経路指定及び最適化の技法を含む技法を含めて、改良された自動回路設計技法を提供することが望まれる。
【０００８】
【特許文献１】米国仮特許出願第６０／７８５，４４３号
【特許文献２】米国特許第６，４３８，７３５号
【特許文献３】米国特許第６，４４９，７６２号
【特許文献４】米国特許第６，９７３，６３２号
【発明の開示】
【課題を解決するための手段】
【０００９】
本発明は、集積回路を設計するための様々な方法と装置に関しており、具体的には、データ処理システムを使って１つ又は複数の集積回路を設計する自動設計に関する。本発明の１つの態様によれば、集積回路を設計するための或る代表的な方法は、ＩＣを設計するプロセスの一部としての第１経路指定レベルで、第１セットの配線リソースを使用してＩＣの表現上の接続を経路指定し、第１セット内の配線リソースが一旦経路指定に用いられたら、使用済みとマーキングする段階と、ＩＣの表現で第２セットの配線リソースを使用する第２経路指定レベルで、第２セット内の配線リソースが以前に接続を経路指定するのに使用されているか否かを確認すること無く、ＩＣ上の接続の経路指定を行う段階と、を含んでおり、第２セットの配線リソースは、平均で、物理的な寸法が第１セットの配線リソースとは異なっている。通常、第２セットの配線リソースは、平均で、第１セット内の配線リソースより長く、第２セットを使用する経路指定は、第２セット内の配線リソースに、これらの配線リソースが経路指定演算の一部として一旦使用されたときに、予約済みとマーキングすること無く実行される。
【００１０】
本発明の別の態様によれば、或る代表的な方法は、設計されているＩＣの表現内の駆動コンポーネントのファンアウトを確定する段階と、駆動コンポーネントに関して、ＩＣの表現内で、駆動コンポーネントによって駆動されるロードを確定する段階と、ロードを駆動コンポーネントに接続するために使用される既存の配線リソースの使用を確定する段階と、既存の配線リソースの使用、駆動コンポーネントのファンアウト、及び駆動コンポーネントによって駆動されるロードに基づいてＩＣの設計を最適化する段階と、を含んでいる。通常、最適化する段階は、駆動コンポーネントを複製することによって駆動コンポーネントのファンアウトを減らすか否か判定する段階を含んでおり、複製する段階は、複製を実施するため機械読み取り可能媒体を備えて構成されているデータ処理システムによって自動的に実施される。
【００１１】
本発明の別の態様によれば、或る代表的な方法は、集積回路を設計するプロセスの一部として、ロードから駆動コンポーネントまでの経路指定ネットを確定して、駆動コンポーネントの複製板に利用できる場所を確定する段階と、集積回路の表現内に、経路指定ネットと利用できる場所とに基づいて、駆動コンポーネントの複製版を作成し、表現内で、複製版とロードの間に接続を作成する段階と、を含んでいる。本方法は、クリティカルロードから利用可能な配線を通って後戻りし、複製されたドライバに利用できる空間を確認することによって複製を実行する、ロードに基づく複製を実行するのに使用することができる。更に、同じ複製されたドライバによって駆動される領域内の他のクリティカルロードも、以下に述べる漸進的な経路指定方法によって接続してもよい。
【００１２】
ここに述べている本発明の別の態様によれば、或る代表的な方法は、集積回路を設計するプロセスの一部として、ＩＣの表現内のコンポーネントを複製し、そのコンポーネントを、元のコンポーネントの出力と等価な出力を有する複製コンポーネントと標示する段階と、表現内で、複製されたコンポーネントと複製されたコンポーネントのロードとの間の接続を経路指定する段階と、複製されたコンポーネントを、コンポーネントの少なくとも１つの既存のロードを駆動するソースとして使用するか否か判定する段階と、を含んでいる。この態様の少なくとも或る実施形態は、ロードを駆動するために、元のソースではなく等価なソースから経路指定することができる。合成プロセス全体を通して、複製物にタグを配置することによって、以前に複製された等価なソースを識別することができるので、経路指定演算は、元のソースではなくこれらのソースを使用することもできる。
【００１３】
ここに述べている本発明の別の態様によれば、或る代表的な方法は、配線遅延に関する値を、設計されている集積回路の表現内の配線網の幾何学形状に基づいて調整すべきか否か判定する段階と、その幾何学形状が第１型式であれば値を調整する段階と、集積回路を設計するプロセスの中で、調整後の値に基づいて経路指定の決定を下す段階と、を含んでいる。この代表的な実施形態は、特定の長い距離の配線網が、基本的に、切替マトリクスのグループを通る直線なのか、又は切替マトリクスの別のグループを通る階段状のパスなのかに基づいて、測定されるか又は見積もられる、特徴付けられた配線遅延を調整するのに使用することができる。
【００１４】
本発明は、本発明の様々な方法を実行することができるコンピュータシステムを提供し、本発明は、更に、コンピュータシステムの様なデータ処理システムによって実行されると、データ処理システムに、ここに述べた１つ又は複数の方法を実施させる、プログラム命令が入っている、機械読み取り可能媒体の様なコンピューター読み取り可能媒体を提供している。本発明のこの他の特徴は、添付図面と以下の詳細な説明から明らかになるであろう。
【００１５】
本発明を、例を挙げて説明するが、本発明は、添付図面の形態に限定されるわけではなく、また図面では、類似の参照番号は同様な要素を示している。
【発明を実施するための最良の形態】
【００１６】
自動設計プロセスを通して集積回路を設計するための方法とシステム、及び機械読み取り可能媒体について説明する。
【００１７】
本発明を、以下に述べる多くの細部に関連付けて説明するが、添付図面は、本発明を例証している。以下の説明及び図面は、本発明を例証するものであり、本発明を限定するものではない。本発明を徹底的に理解して頂けるように、多くの具体的な詳細事項について説明する。しかしながら、或る例では、本発明を細部で不必要に曖昧にするのを避けるために、周知の又は従来通りの詳細事項については説明しない。
【００１８】
既存の配線リソースに基づき複製によってファンアウトを減らす
経路指定ネットのルートのファンアウトの様なファンアウトを減らすために複製を実行するときに、既存の配線リソースに関する情報を利用することによって、図３Ｃに対して図５に示す様に、経路指定の決定を改良し、良好な結果を実現することができる。具体的には、ドライバ２１５を複製する前に既存の配線リソースを考慮することによって、クリティカルロードＬ１、Ｌ２、Ｌ３及びＬ４を、ドライバＤ（ドライバ２１５）からの配線Ｗ１に接続し、残りのロードを、図５にドライバ３１１として示すドライバＤの複製コピーからの配線で駆動すべきである、と判定することができる。ロードＬ１−Ｌ４は同じ配線Ｗ１で駆動されるので、スイッチＳＷＤにおけるルートのファンアウトは「１」のままである。ドライバの複製コピー３１１におけるルートのファンアウトは「１」だけ減るので、ドライバ３１１によって駆動される他のロードは、複製されたドライバのルートのファンアウトが減るため良好なネット遅延を有することになる。クリティカルロードＬ１−Ｌ４は、図３Ａに示す元のネットリストと比べてネット遅延が改良され、図３Ｃに示す唯２つのクリティカルパスでの改良に対して、４つの異なるパスで改良されている。
【００１９】
図４は、経路指定ネット全体を通して、ルートのファンアウト場所又は中間のファンアウト場所の何れかでドライバを複製するときに、経路指定ツリーに関する情報を使って経路指定演算を実行するための一般的な方法を示している。演算３０１は、ドライバ２１５の様なクリティカルドライバに関して、クリティカルドライバによって駆動されるクリティカルロードを判定する段階を含んでいる。この段階には、通常、或るロードがクリティカルロードであるか否か判定する段階と、次にそれらのクリティカルロードを駆動するドライバを確定する段階とが伴う。それらのドライバは、クリティカルロードを駆動するのでクリティカルドライバである。このロードは、例えば、タイミングの制約又は要件に影響するのでクリティカルである。例えば、ロードは、或る特定のロード出力でのスラック測定値が、負であるか、又は十分に正ではない場合にクリティカルとなる。図５に示している設計の場合、ロードＬ１−Ｌ４は、クリティカルドライバ２１５によって駆動されるクリティカルロードである。勿論、演算３０１は、この決定を、この最適化前の元の設計に基づいて実行し、従って、演算３０１では、図３Ａに示す集積回路を用いて、クリティカルドライバ２１５に関し、何れのロードがクリティカルであるか判定する。次に、同じ最適化されていない設計を使って、演算３０３は、クリティカルドライバをそのロード全てに接続している経路指定ツリーに関する情報を判定する。この様に、図３Ａに示している設計の場合、演算３０３は、クリティカルドライバ２１５をロードＬ１−Ｌ７の７つ全てに接続している経路指定ツリーに関する情報を判定する。次に、演算３０５では、クリティカルドライバからの経路指定ツリーは、ロードに関する情報を用い、そして経路指定ツリーに関する情報を用いて最適化される。従って、最適化プロセスは、ドライバの複製のやり方、及び元のロードに対する複製ドライバと元のドライバの経路指定のやり方を確定するときに、クリティカルドライバ２１５を、その様々なロードに連結するのに使用されている実際の存在している配線リソースを考慮する。而して、演算３０５の最適化プロセスは、図３Ａに示す設計を変えて図５に示す設計を作り出し、この設計では、複製されたドライバ３１１は、ファンアウトが減り、クリティカルロードを除く全てのロードを駆動するのに対して、元のドライバ２１５は、図３Ａに示す同じ経路指定ネットを使い続けており、ルートのファンアウトは減っている。先に述べた様に、この方法は、或る設計の全てのクリティカルドライバでルートのファンアウトを減らすために実行することができ、随意的に、経路指定ツリー全体に亘って中間ドライバでファンアウトの削減を実行するのに用いてもよい。この方法は、オペレーションリサーチの分野で知られている技法を使って実行され、ロード、ドライバ、及びロードをドライバに連結している実際の存在している配線リソースに関する情報を用いて、最適又は最適に近い経路指定を実現するが、実際の存在している配線リソースは、複製によって作成された新しいドライバに連結するのにも使用することができる。オペレーションリサーチ技法で最適化されるパラメーターは、タイミングでもよい。
【００２０】
図６は、図４の方法を実行し、図６の場合はクリティカルドライバ又はコンポーネントと想定されている、ドライバからのルートのファンアウトを減らすことによって集積回路の設計を最適化する１つの具体例を示すフローチャートである。「ドライバ」又は「コンポーネント」は、フリップフロップ又はルックアップテーブルの様な論理要素か、又は、信号を生成する他のデジタル論理コンポーネントのことであり、信号は、その信号を入力として受け取る他のコンポーネントへ出力されることになる。図６の方法は、演算３５１で始まり、或る特定のクリティカルコンポーネントに関し、何れのロードが、その特定のクリティカルコンポーネントによって駆動されるかを判定する。演算３５３では、経路指定ネットツリーを、特定のクリティカルコンポーネントによって駆動されるネット毎に計算し又は判定する。例えば、その経路指定ツリーの各分岐点におけるファンアウトを判定し、何れのノードがネット上でクリティカルであるかを判定する。次に、演算３５５では、実際の経路指定ツリーに関する情報を集めた後、特定のクリティカルコンポーネントの複製版である複製ドライバを、経路指定ネットツリーの１つの分岐上の全クリティカルロードに対して作成し、この複製ドライバを用いて、それらのロードを駆動する。代わりに、元のドライバを用いて経路指定ネットツリーの１つの分岐上のロードを駆動し、この特定のクリティカルコンポーネントの複製である複製ドライバを用いて、経路指定ネットツリーの他の全てのロードを駆動してもよい。この代替案は、図５の設計を作成するのに実行された案であり、元のドライバ２１５を、４つのクリティカルロードを駆動するためその位置に保ち、複製ドライバ３１１を用いて、修正された経路指定ネットツリーを通して、残りのロードを駆動している。演算３５７では、クリティカルロードを、複製ドライバに接続し、次いで演算３５９で、スラックが再度計算される。演算３６１で、スラックが改善されていると判定されると、本方法は、演算３６５を通って戻り、演算３５１から再開する図６の演算を繰り返すことにより、他の経路指定ネットの最適化を試みる。演算３６１で、スラックが改善されていないと判定されると、演算３６３で複製は廃棄され、処理は演算３５１へ戻り、設計を他の方法で最適化するよう試みる。
【００２１】
ロードをベースにした複製
ネット上のクリティカルロードが少ない場合は、ロードをベースにした複製が実行される。各ロード毎に専用のコピーが作成される。図３Ａに示している例で、ロードＬ３とＬ４がクリティカルでなければ、ロードＬ１とＬ２に対してのみドライバのコピーを作成するのが良い解である。ドライバがフリップフロップの場合、ドライバをロードに近接して配置し、ロードを最高速の可能な配線に接続する。ロードをベースにして複製する場合、プロセスは、ロード側で始まり、経路指定ネットを、ロードから利用可能な既存の配線を通ってドライバへ遡ることによって調べる。このプロセスは、既存の配線網を通って遡るプロセスで、複製されたドライバを設置するのに利用できる場所を考慮に入れることもできる。更に、このプロセスは、同じドライバによって駆動される他のクリティカルロードが同じ区域に存在するか否かを評価し、以下に述べる漸進的な経路指定技法を使って、他のクリティカルロードを複製ドライバに接続することもできる。これは、特定のクリティカルロードに対してドライバを複製し、複製されたドライバをクリティカルロードに接続するだけの先行技術の解決法とは異なっている。このロードをベースにした複製プロセス版を、図７に示している。図７に示されている方法は、図１の演算１０５に示している最適化プロセスの様な最適化プロセスの一部分であると理解されたい。図７の方法は、演算４０１で始まり、ロードをベースにして複製できるクリティカルロードが選択される。演算４０３では、そのクリティカルロードから元のドライバまで遡る経路指定ネットを求め、その元のドライバの新規コピーに利用可能な場所も判定する。次に演算４０５では、本方法は、複製されたコピーの経路指定ネットと利用可能な場所に基づいて、複製ドライバを作成し、それを、選択されたクリティカルロードに接続する。次いで、本方法は、演算４０７で、選択されたクリティカルロード付近の、元のドライバからのと同じ経路指定ネット内の他のクリティカルロードを調べて、前記他のクリティカルロードを複製ドライバに接続するか否かを決定する。
【００２２】
漸進的な経路指定
図８、図９及び図１０は、設置操作後、又は設置操作と同時に経路指定演算を実行するための方法に関する。この演算技法は、設計を合成し最適化するのに使用されるコンパイラのランタイムが、しばしば、ここに述べている漸進的な経路指定技法を使うことによって改良されるので、受け入れ可能なＩＣ設計を、しばしば、先行技術の技法より速く作成することになる。この技法は、特定のＩＣアーキテクチャ内の特徴付けられた配線遅延を利用しており、これらの特徴付けられた配線遅延は、実測した配線遅延でもよいし、特定のチップのアーキテクチャに関する知識に基づいて予測し又は見積もった配線遅延であってもよい。特定のチップのアーキテクチャは、目標アーキテクチャと呼ばれることもあり、通常は、プログラム可能集積回路の供給元によって決められる。目標アーキテクチャの例は、カリフォルニア州サンホゼ市のXilinx社製の或る集積回路のプログラムされたルックアップテーブル及び付帯論理である。目標アーキテクチャの他の例としては、Altera他の製造元から販売されているフィールドプログラマブルゲートアレイ及び複雑なプログラマブルロジックデバイスの周知のアーキテクチャが挙げられる。図８は、特定のＩＣアーキテクチャの例を示しており、図３Ａと図３Ｂの切替マトリクスと同様の切替マトリクスのアレイを利用している。これらの切替マトリクスは、異なるスイッチマトリクスの間に使用できる既存の配線リソースによって接続されている。スイッチマトリクス内のスイッチは、設計が完了した後は、これら様々な既存の配線リソースに接続されていてもいなくてもよい。図８に示す集積回路４５１のアーキテクチャは、スイッチマトリクス４５２−４５９を含んでおり、それらは、１つのセットの配線リソース内の配線リソースの平均の物理的な寸法に基づき３つの異なるセットの配線リソースとして特徴付けられたものによって連結されている。具体的には、配線４６１Ａ、４６１Ｂ、４６１Ｃ及び４６１Ｄは、それらの配線リソースの平均長さが、図８の他の配線リソースの長さより短いので、第１セットの配線リソースの一部と見なされる。更に、配線リソース４６１Ｅと４６１Ｆも、長さが短かければ、第１セットの配線リソースの一部と見なされる。もっと長い配線リソース、即ち第２セットの配線リソースには、配線リソース４６３Ａ、４６３Ｂ、４６３Ｃ及び４６３Ｄが含まれる。これらの配線リソースは、長さが、より長い配線リソースよりは短いが、第１セットの配線リソースの短い配線リソースよりは長いので、中間の配線リソース又は配線リソースのセットと見なされる。図８に示す最も長い配線リソースのセットである第３セットの配線リソースには、配線リソース４６５Ａ、４６５Ｂ及び４６５Ｃが含まれる。これらの配線リソースは、図８に示す他の何れの配線リソースよりも長い。図８で表されている集積回路はもっと大きくてもよいし、図示していない更なるスイッチマトリクスがあるものと理解頂きたく、更に、図示のスイッチマトリクスを相互に接続するのに、図示していない追加の配線リソースが使用されているものと理解頂きたい。図８を簡素化するために、これらの追加の配線リソースは示されていない。３つのセットの配線リソースは、それぞれ、経路指定をどの様に実行するか、経路指定ネットによる遅延をどの様に見積もるかを定義するのに使用される。図８の場合、各セットは、ネットの指定経路の距離に基づいて定義されている。第１セットは、架設距離が最短のネットのセットであり、それらのネットを経路指定するプロセスにおいて、配線リソースは、使用されるように敷設される。短いランの端と端を接続する有限の少数の配線がある。その様なネットが経路指定されると、既に完了した経路指定で使用された配線は予約済みとマーキングされ、次の経路指定が完了する前に、本方法は、配線リソースが利用可能か否か確認して判定する（配線リソースが既に予約済みとマーキングされているか、又は利用不能な配線リソースのリストに載っていないかを見ることによって判定される）。通常、配線距離が短いほど、配線ネットによる遅延はより正確で、配線を実測するか、又は具体的な集積回路の配線の物理的構造に基づいて配線遅延を推定することによって、得ることができる。集積回路のXilinx製ＦＰＧＡ Virtex 群では、第１セットの配線リソースは５ｘ５ＣＬＢボックスで定義されており、それは、これらがピンをこの距離で接続する最短最速の配線だからである。第２セットの配線リソースは、平均で、第１配線リソースの短い距離よりより長い距離用に定義されている。例えば、第２セットの配線リソースは、２本又はそれ以上の短い配線で経路指定できるようなネットに使われる。この具体例は図８には示されていないが、或る種のＩＣアーキテクチャは、スイッチマトリクスが、２つの短い配線を相互に接続して、１つの長い配線にすることができるようにしている。この第２セットの配線リソースでは、ネットの遅延が見積もられるが、以下に述べる様に、配線リソースは、経路指定プロセスで用いられる際に予約済みにされない。もっと長い距離に亘る経路指定プロセスでは、使用する配線の選択肢がもっと多いので、これは受け入れられるやり方である。幾つかの配線の選択は同様なネット遅延に至るので、遅延予測はなお正確であり、遅延予測における相対誤差は小さい。Xilinx製ＦＰＧＡ Virtex 群では、このセットの配線リソースは、１３ｘ１３ボックスで定義されている。予測遅延は、このボックス内のポイントからポイントまでの遅延から得られ、遅延の値は、ルックアップテーブルに記憶される。第３セットの配線リソースは、第２セットよりも長い、チップ全体を跨ぐことができる様な距離用である。このセットの配線リソースでは、配線遅延を見積もるために、統計的迂回路分析による見積器を使用してもよい。
【００２３】
図９は、経路指定方法の一般的な例を示しており、本例では、配線リソースのグループ又はセットを、各セットの配線リソースの間の平均の物理的寸法の差に基づいて識別する。図９の方法は、演算５０１に示すように、自動設計プロセスの間にコンポーネントを集積回路の表現内に配置した後、又は配置すると同時に実行される。演算５０３では、予約済みとマーキングされることになる短い経路が定義される。図８の例では、配線リソース４６１Ａ−４６１Ｆが短い経路と定義されるが、これらの経路は、１つ又は複数のそれらの配線リソースを使用して経路指定演算を実行した後で予約済みとマーキングされることになる。演算５０５では長い経路が定義されるが、これらの経路は、経路指定と配置が実行されるときに予約済みにされないので、経路指定プロセスは、長い経路を使って経路指定を行う際に、長い経路が予約済みか否かについて確認しない。勿論、これでは、特定の長い経路が接続の経路指定に以前に用いられているか否かを確認するため何らの努力も払われていないので、或る経路が２回以上用いられる可能性が生じる。図８の例では、配線リソース４６３Ａ−４６３Ｄは、演算５０５で定義される長い経路のセットの例である。先ず経路指定と配置が完了した後、演算５０７で、経路指定演算を実行したときに予約済みとマーキングされなかった長い経路を重複して使用しているか否か判定するため、検査が実行される。演算５０７を実行するのに必要なソフトウェア演算は、使用された経路を予約済みとマーキングし、次の経路指定を行うときに、配線リソースが以前に使用されているか否かを確認するのに必要なソフトウェア演算よりも、掛かる時間が短いと予測される。つまり、経路指定演算は、長い経路に関する以前の経路指定演算が或る経路を使用したか否かについて無視する方が、長い経路を指定するときに、以前の経路指定演算が長い経路の何れかを使用したかを実際に確認するよりも、早くなると予測される。長い経路の使用が重複する場合は、演算５０９で、本方法は、それらの重複使用を、重複使用になっているそれぞれの経路を別のパスを通るよう経路指定することにより正すのであるが、重複使用を避けるため、最大の正のスラックを有する信号を再経路指定のために選択するのが望ましい。
【００２４】
図１０は、図９に示す方法と同様の、そして図８に示す様なアーキテクチャでも利用できる、漸進的経路指定方法の更に詳細な例である。図１０の方法は演算５５１で始まり、演算５５１で、集積回路の短い相互接続の様な少なくとも相互接続のセットについて、配線遅延が特徴付けられる。図８の例では、スイッチマトリクスとフィールドプログラマブルゲートアレイの間の相互接続は、それらの遅延を実測するか、又はそれらの遅延を見積もるか又は予測するか、の何れかによって特徴付けられる。演算５５３では、既に特徴付けられている短い接続が、ドライバとそのドライバのロードとの間の経路指定を確定することによって実行される。各場合で、経路指定が実行される度に、その経路には予約済みとマーキングされるので、その後の短い接続の経路指定は、所望の経路が以前に使用されているか否かを、使用する前に確認することができる。以前の使用は、予約済みか否かによって示される。理解頂ける様に、代わりの実施形態では、利用可能な経路指定リソースのリストが維持され、経路指定リソースが一旦使用されると、そのリソースはリストから取り除かれるので、その後の経路指定演算は、経路指定演算が終了する前に、そのリストを確認し、その配線リソースが利用可能であるか否かを、リストに載っているか否かに依って判定することができる。これは、予約済みにすること、又は配線リソースが経路指定演算で既に用いられたことを示すことの別の方法であると考えられる。演算５５５では、特徴付けられることになるかもしれない中間接続が経路指定されるが、これらの経路指定演算は、経路指定された中間接続に予約済みのマーキングをすること無く行われるので、その後の中間接続の経路指定も、所望の経路が、以前の経路指定演算で使用されていたために既に予約済みになっているか否かを調べて確認すること無く実行される。演算５５７では、長い接続の経路指定が、これらの長い接続の経路指定を確定することによって実行されるが、予約済みとすること無く、所望の経路が既に使用されているか否かを、以前の経路指定演算でマーキングされた予約済みで確認することも無く実行される。最後に、演算５５９で、先ず経路指定と配置が完了した後で、同じ経路の重複使用について確認が実行され、重複使用は、先に述べた様に正される。
【００２５】
等価なリソースから経路を指定する
図１１Ａ、図１１Ｂ、図１１Ｃ及び図１２は、等価なリソースから経路指定するための方法に関する。ネットの経路指定をする必要があるときにこの方法を使えば、本システムは、或る特定のネットの全ノードのドライバの複製例の様な、このネットの何れの等価なソースからでも、動的に経路指定することができる。図１２に示す方法は、図１１Ａ、図１１Ｂ及び図１１Ｃに示す回路に関係して、等価なソースから経路指定するための１つの具体的な方法について説明するのに用いられる。この方法は、最適化に際して、又は複製を実行するときは何時でも、実行することができる。更に、この方法は、複製したオブジェクトの様なオブジェクトを配置するときは何時でも、又は集積回路の設計を最適化しようとするときにそれらのオブジェクトを辺りで動かすときに、使用することができる。演算７０１では、或る特定のコンポーネントを複製するか否かを判定する。図１１Ａに示す回路の場合、図１１Ａに示す様に、６個のルックアップテーブルのアレイ６０４の３つのロードＬ１、Ｌ２及びＬ３と、集積回路の他の部分のロードＬ５と、更にクリティカルロードＬ４  ６０５と、を目下駆動しているドライバ６０１を複製するか否かの決定が行われる。クリティカルロードＬ４は、スラックを改善する必要があるので、図１１Ａに示している様に、その出力信号Ａに５つのロードを駆動させているドライバ６０１を複製することが決められる。複製演算が実行されると、図１１Ｂに示す回路になり、ドライバ６０１が複製されて複製ドライバ６０１Ａが作成され、ドライバ６０１Ａは、ドライバ６０１からの出力と等価又は同一の出力Ａ’を生成する。この新しく複製されたドライバは、スイッチマトリクス６０９を通して、ロード６０５に連結されている。ドライバ６０１は、スイッチマトリクス６０３を通してロードＬ１、Ｌ２及びＬ３を駆動し続け、ロードＬ５も駆動し続ける。図１１Ｂに示す設計は、少なくとも、ドライバ６０１に関し、スイッチマトリクス６０３への入口におけるルートのファンアウトは減っており、ロード６０５が、ドライバ６０１の複製コピーである専用のドライバを有しているという点において、図１１Ａに示す設計に勝る改良型となっている。演算７０３に示す様に、コンポーネントを複製するときは、複製したコンポーネントであることを標示し、それが、複製された等価なコンポーネントの等価な出力を有していることを示す。このタグは、集積回路の設計を最適化するプロセスで、コンポーネントを経路指定し、辺りを動かすときに、システムが、複製されたコンポーネントを元のコンポーネントと等価であると識別できるようにしている。図１１Ｂに示す設計は、演算７０５の結果であり、複製されたコンポーネントが設計内に配置されており、接続は、複製コンポーネント、この場合はドライバ６０１Ａと、ロード６０５の間に経路指定されている。コンポーネントの経路指定及び／又は配置を最適化し続けるプロセスで、演算７０７では、複製されたコンポーネントを、元のコンポーネントの幾つかのロードを駆動するためソースとして使用するか否か判定する。例えば、最適化プロセスの間にシステムが配置し経路指定する際に、或るロードへの接続を、それを駆動するよ���に目下割り当てられているコンポーネントから経路指定するか、又はコンポーネントからの信号の他の等価なソースから経路指定するかを自動的に判定することができる。この演算及び演算７０９の結果を図１１Ｃに示しており、ロードＬ５も、複製されたドライバ６０１Ａはドライバ６０１と等価なソースなので、複製ドライバ６０１Ａに連結されている。これによって作り出された結果では、ドライバ６０１Ａのルートのファンアウトは３に減り、潜在的に短い経路指定リソースを、ロード６０５の駆動に大きく影響を及ぼす可能性無しに、ロードＬ５を駆動するのに利用できるようになっている。図１２の方法は、コンポーネントを配置し又は移動させるときに実行され、オブジェクトを集積回路の設計の辺りに配置する際に、それらのロードを駆動するための等価なソースを利用できるようになるので、「配置子」に大きな柔軟性を与える。
【００２６】
経路指定の幾何学形状を調整する
図１３と図１４は、特徴付けられた配線遅延が配線ネットの幾何学形状に基づいて調整される、本発明の或る態様に関している。少なくとも或るチップアーキテクチャでは、実質的に水平方向又は実質的に垂直方向の配線パスを通る配線遅延は、実質的に対角線状又は階段状の配線パスに関して予測される配線遅延より僅かに長いことが観察されている。経路指定ネットにおける、これら２つの幾何学形状の間の違いを図１３に示している。ドライバＤ２（ドライバ８１９）とロードＬ２（ロード８２１）の間の経路指定ネットは、実質的に水平な経路指定パスである。一方、ドライバＤ１とロードＬ１（ドライバ８１５とロード８１７）の間の経路指定パスは、集積回路８０１の実質的に対角線状のパスに沿っている。この集積回路は、９つのスイッチマトリクス８０２−８１０を含んでおり、それらは、集積回路全体に亘って、ロードとドライバを相互接続できるようにする働きがある。水平又は対角線の方向、又は垂直方向の何れかのスイッチマトリクス間の配線遅延は、演算８５１に示している様に特徴付けられる。この特徴付けは、列に沿う、又は対角線状のパス又は実質的に対角線状のパスに沿う、隣接する又は数個のスイッチマトリクスの間のタイミング遅延を実測して行ってもよい。特徴付けは、実測するのではなく、予測又は見積もりを使って実行してもよい。演算８５３では、長い配線ネットの場合、特徴付けられた配線遅延をネットの幾何学形状に基づいて調整する必要があるか否か判定される。例えば、長い配線ネットを、主に、水平方向又は垂直方向線の様な直線に沿わせるか、又は、主に、ドライバ８１５をロード８１７に連結している配線ネットが取っているパスの様な階段状のパスに沿わせるかが決められる。演算８５３で、実際に、特徴付けられている配線遅延を調整する必要があると判定された場合は、演算８５５で調整され、その後、演算８５７で、経路指定決定が、調整された配線遅延に基づいて下される。
【００２７】
タイミング遅延の調整は、オブジェクトを異なるスイッチマトリクスの付近で移動させ配置する際に、動的に調整することができる。特徴付けられた配線遅延を調整する必要があるか否かの判定は、特定のネットを、水平線に沿ってではなく、ロードに向かって進む水平方向及び垂直方向の線分によって、配線することになる確率を計算することによって実行される。このジグザグの確率は、或る特定のパスの部分で既に用いられている配線を統計学的に考慮することによって計算することができ、この確率は、ロードとドライバの間の経路指定演算を完了する前に計算することができる。水平又は垂直線上にロードを有するドライバの数の分布を、設計する際に考慮することができる（又は、設計の収集の際に統計学的に計算することができる）。経路指定アーキテクチャは、限られた数の水平及び垂直方向の経路指定リソースしか有していないので、全てのロードを、直接配線を使って経路指定できるわけではない。代わりに、幾つかのロード用の配線は、水平又は垂直方向の線から迂回することになる。その迂回の確率は、設計内の、水平又は垂直方向の配線の数と、ドライバに対するロードの数の分布（例えば、２０セルが７個のロードを、セルが１０個のロードを有する）に基づいて計算される。その結果、このジグザグ確率に基づいて、全ての長い配線に追加的な配線遅延が加えられる。
【００２８】
データ処理システム
図１５は、本発明の或る実施形態を実施するのに用いられるコンピュータシステムのブロック図を示している。コンピュータシステムは、実行可能なコンピュータプログラム命令を記憶する１つ又は複数の機械読み取り可能媒体を含んでおり、この命令は、コンピュータシステムの様なデータ処理システムによって実行されると、コンピュータシステムがここに記載されている１つ又は複数の方法を実行することになる。コンピュータシステムは、例えば、ここに記載されている漸進的な経路指定方法を、集積回路の合成の一部として実行するのに用いられる。コンピュータシステムは、プロセッサ９０２を含んでおり、プロセッサ９０２は、バス９０１を通して、ランダムアクセスメモリ９０４、読み取り専用メモリ（ＲＯＭ）９０６、及び大容量記憶装置９０７に連結されている。大容量記憶装置９０７は、フロッピー（登録商標）ディスクドライブ、固定ディスクドライブ、又はフラッシュメモリの様な不揮発性記憶機構、の様な持続型データ記憶装置を表している。プロセッサ９０２は、インテルペンティアム（登録商標）プロセッサの様な汎用プロセッサか、又は特定目的プロセッサ、又は特別にプログラムされた論理装置で具現化することができる。ディスプレイ装置９２０は、バス９０１を通してプロセッサ９０２に連結されており、コンピュータシステム９００に図形出力を提供する。キーボード９２１とカーソル制御ユニット９２２は、バス９０１に連結されており、情報とコマンド選択肢をプロセッサ９０２に通信する。プロセッサ９０２には、バス９０１を通して入出力インターフェース１２３も連結されており、入出力インターフェース１２３は、データを制御し、そのデータを、コンピュータシステム９００に接続されているプリンタや他のコンピュータなどの電子装置に伝送するのに用いられる。図１５に示しているコンピュータシステムのアーキテクチャは、例証の目的で提供されているに過ぎず、本発明と組み合わせて使用されるコンピュータは、この特定のアーキテクチャに限定されないことに留意されたい。
【００２９】
上記明細書では、本発明を、その特定の代表的な実施形態に関連付けて説明してきた。これに対して、特許請求の範囲に記載されている本発明の広い精神及び範囲から逸脱することなく、様々な修正を施せることは明らかである。従って、明細書と図面は、限定するものではなく例証するためのものであると考えて頂きたい。
【図面の簡単な説明】
【００３０】
【図１】本発明の少なくとも或る実施形態で用いられるＨＤＬ合成のプロセスを示すフローチャートである。
【図２】自動コンピュータ支援設計システムにおいて集積回路の設計を最適化するための先行技術による方法を示すフローチャートである。
【図３Ａ】自動設計プロセスの間の集積回路の表現を示している。
【図３Ｂ】図３Ａに示す設計の切替マトリクス内の更なる詳細を示している。
【図３Ｃ】図２に示す方法に従って実行された先行技術での最適化の結果を示している。
【図４】集積回路設計の最適化を実行するための、本発明の１つの代表的な実施形態を示すフローチャートである。
【図５】図４に示す方法の１つの実施形態から作り出された最適化の表現を示している。
【図６】ルートのファンオウトが、少なくとも部分的には、ルートに連結されている既存の配線網に関する知識に基づいて減る、集積回路設計を最適化するための具体的な実施形態を示すフローチャートである。
【図７】ここに記載されている本発明の別の態様の代表的な実施形態を示すフローチャートである。
【図８】少なくとも或る型式のＩＣ内の相互接続のレイアウトを示している。
【図９】本発明の或る実施形態による、経路指定プロセスの代表的な方法を示すフローチャートである。
【図１０】図９に示す方法と同様の、図８に示す様な集積回路のアーキテクチャを使用する経路指定プロセスの具体例を示す別のフローチャートである。
【図１１Ａ】或る具体的な集積回路の設計のプロセスを時系列で示している。
【図１１Ｂ】或る具体的な集積回路の設計のプロセスを時系列で示している。
【図１１Ｃ】或る具体的な集積回路の設計のプロセスを時系列で示している。
【図１２】ここに述べた或る実施形態による代表的な方法を示すフローチャートであり、この方法は、図１１Ａ、図１１Ｂ、及び図１１Ｃに示す変化を作り出す。
【図１３】複数のスイッチマトリクスを有する集積回路のレイアウトの例を示している。
【図１４】図１３に示す２つの異なる幾何学形状の様な、経路指定ネットの幾何学形状に基づいて、配線遅延を調整する本発明の或る実施形態による、代表的な方法を示すフローチャートである。
【図１５】ここに述べる１つ又は複数の実施形態を実施するのに用いられ、実行可能なプログラムの命令を記憶してデータ処理システムにここに述べる１つ又は複数の方法を実行させる１つ又は複数の形態の機械読み取り可能な媒体を含んでいる、コンピュータシステムの様なデータ処理システムのブロック図である。
【図１】
2009536376.tif 000003
【図２】
2009536376.tif 000004
【図３Ａ】
2009536376.tif 000005
【図３Ｂ】
2009536376.tif 000006
【図３Ｃ】
2009536376.tif 000007
【図４】
2009536376.tif 000008
【図５】
2009536376.tif 000009
【図６】
2009536376.tif 000010
【図７】
2009536376.tif 000011
【図８】
2009536376.tif 000012
【図９】
2009536376.tif 000013
【図１０】
2009536376.tif 000014
【図１１Ａ】
2009536376.tif 000015
【図１１Ｂ】
2009536376.tif 000016
【図１１Ｃ】
2009536376.tif 000017
【図１２】
2009536376.tif 000018
【図１３】
2009536376.tif 000019
【図１４】
2009536376.tif 000020
【図１５】
2009536376.tif 000021
【国際調査報告】
2009536376.tif 000022
2009536376.tif 000023
2009536376.tif 000024
2009536376.tif 000025
2009536376.tif 000026