(57)【要約】集積回路をレイアウトするレイアウト装置におけるレイアウト方法は、回路データに従って複数のセルを概略の位置に配置し、複数のセルの概略の位置への配置の結果に従って複数のセルを具体的な位置に配置する。複数のセルの具体的な位置への配置において、複数のセルを具体的な位置に配置し、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、求めたクリティカルエリア値が小さくなるように複数のセルの具体的な位置を変更する。
2004034463.tif 000002
【特許請求の範囲】
【請求項１】
集積回路をレイアウトするレイアウト装置におけるレイアウト方法であって、
回路データに従って、複数のセルを概略の位置に配置し、
前記複数のセルの概略の位置への配置の結果に従って、前記複数のセルを具体的な位置に配置する工程を含み、
前記複数のセルの具体的な位置への配置は、更に、
前記複数のセルを具体的な位置に配置し、
隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、
前記求めたクリティカルエリア値が小さくなるように、前記複数のセルの具体的な位置を変更する
ことを特徴とするレイアウト方法。
【請求項２】
前記複数のセルの具体的な位置は、前記求めたクリティカルエリア値が当該セルについての位置の交換により小さくなる場合、当該セルについての交換を行なうことにより変更される
ことを特徴とする請求の範囲第１項に記載のレイアウト方法。
【請求項３】
前記複数のセルの具体的な位置は、前記求めたクリティカルエリア値が当該セルについての回転により小さくなる場合、当該セルについての回転を行なうことにより変更される
ことを特徴とする請求の範囲第１項に記載のレイアウト方法。
【請求項４】
前記複数のセルの具体的な位置は、前記求めたクリティカルエリア値が所定の値よりも大きい場合、当該隣接して配置されたセルの間に隙間を挿入することにより変更される
ことを特徴とする請求の範囲第１項に記載のレイアウト方法。
【請求項５】
当該レイアウト方法は、更に、
前記複数のセルを隣接して配置した場合の各々の間におけるクリティカルエリア値を格納するクリティカルエリア値テーブルを用意する工程を含み、
前記クリティカルエリア値テーブルを参照することにより、前記隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求める
ことを特徴とする請求の範囲第１項に記載のレイアウト方法。
【請求項６】
当該レイアウト方法は、更に、
前記回路データと前記複数のセルの具体的な位置への配置の結果とに従って、前記複数のセルの間の配線を概略の位置に配置し、
前記配線の概略の位置への配置の結果に従って、前記配線を具体的な位置に配置する工程を含み、
前記配線の具体的な位置への配置は、更に、
前記配線を具体的な位置に配置し、
前記隣接して配置された配線の各々の間におけるクリティカルエリア値を演算により求め、
前記求めたクリティカルエリア値が所定の値より大きい場合であって、当該位置の近傍に配線の空き領域が存在する場合、当該隣接して配置された配線の間に当該空き領域を挿入する
ことを特徴とする請求の範囲第１項に記載のレイアウト方法。
【請求項７】
前記配線の具体的な位置への配置は、更に、
前記空き領域の挿入の結果タイミングのエラーが生じる場合、当該挿入された空き領域を削除して、当該隣接して配置された配線の具体的な位置を当該挿入以前の状態とする
ことを特徴とする請求の範囲第６項に記載のレイアウト方法。
【請求項８】
前記配線の概略の位置への配置は、更に、
前記配線を概略の位置に配置し、
前記配置された配線の混雑度を求め、
前記求めた配線の混雑度が小さくなるように、前記配線の概略の位置を変更する
ことを特徴とする請求の範囲第６項に記載のレイアウト方法。
【請求項９】
集積回路をレイアウトするレイアウト装置であって、
回路データに従って、複数のセルを概略の位置に配置するグローバルプレースメント手段と、
前記複数のセルの概略の位置への配置の結果に従って、前記複数のセルを具体的な位置に配置するディテールプレースメント手段とを含み、
前記ディテールプレースメント手段は、前記複数のセルを具体的な位置に配置し、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、前記求めたクリティカルエリア値が小さくなるように前記複数のセルの具体的な位置を変更する
ことを特徴とするレイアウト装置。
【請求項１０】
集積回路をレイアウトするレイアウト方法を実現するレイアウトプログラムであって、
前記レイアウトプログラムは、コンピュータに、
回路データに従って、複数のセルを概略の位置に配置させ、
前記複数のセルの概略の位置への配置の結果に従って、前記複数のセルを具体的な位置に配置させ、
前記複数のセルの具体的な位置への配置において、更に、
前記複数のセルを具体的な位置に配置させ、
隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求めさせ、
前記求めたクリティカルエリア値が小さくなるように、前記複数のセルの具体的な位置を変更させる
ことを特徴とするレイアウトプログラム。
【請求項１１】
集積回路をレイアウトするレイアウト方法を実現するプログラムを記録するコンピュータ読取可能なプログラム記録媒体であって、
前記プログラムは、コンピュータに、
回路データに従って、複数のセルを概略の位置に配置させ、
前記複数のセルの概略の位置への配置の結果に従って、前記複数のセルを具体的な位置に配置させ、
前記複数のセルの具体的な位置への配置において、更に、
前記複数のセルを具体的な位置に配置させ、
隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求めさせ、
前記求めたクリティカルエリア値が小さくなるように、前記複数のセルの具体的な位置を変更させる
ことを特徴とするプログラム記録媒体。
【発明の詳細な説明】
【技術分野】  本発明は、レイアウト方法及び装置並びにそのプログラム及び記録媒体に関し、特に、レイアウト設計においてランダム故障を考慮することによりＬＳＩの歩留を向上することができるレイアウト方法及び装置並びにそのプログラム及び記録媒体に関する。
【背景技術】  ＬＳＩ（半導体集積回路装置）の加工プロセスの微細化にともない、ランダム故障に起因するＬＳＩの製造歩留りの低下が顕著な問題になっている。ランダム故障とは、製造プロセス内に入り込んだ「小さなごみ（デフェクト）」に起因して、チップ上の配線がショート（短絡）又はオープン（開放）を起こしてしまうことをいう。ランダム故障は、製造プロセスの不具合に起因するシステム故障と共に、ＬＳＩの製造歩留り低下の２大要因である。
ところで、従来のセル及び配線の配置（レイアウト設計）においては、配線率、タイミング、クロストークノイズなどといった要素（以下、コストという）を元に、レイアウト（又はその最適化）が行なわれてきた。ここで、配線率とはＣＡＤにより完了した配線の割合である。タイミングとは主として配線長によって支配される素子から素子への伝搬の遅延を考慮した信号の伝搬のタイミングである。クロストークノイズとは隣接する配線の間における容量結合による相互の信号レベルへの影響である。
このように、従来、レイアウト設計におけるコストとしてのランダム故障を考慮しつつＬＳＩのレイアウト設計又はその最適化を行うことはなかった。この結果、例えば、同一の回路構成のＬＳＩについての全く同じネットリストのレイアウトでも、当該レイアウトによりＬＳＩを製造した場合における歩留り率が５％以上も異なる場合があった。
ランダム故障がレイアウト設計において考慮されない理由は、ランダム故障がデフェクトに起因するため、チップ上のどこでどのようにランダム故障が発生するのかを予想することができないためである。このように、レイアウト設計においてランダム故障が考慮されていないので、当該考慮をしようとしても、レイアウト設計にランダム故障を反映させる指標として何を用い、当該指標をどのようにレイアウトに反映させればよいのか、全く検討されていない。
本発明の目的は、レイアウト設計においてランダム故障を考慮することによりＬＳＩの歩留を向上することができるレイアウト方法を提供することにある。
また、本発明の他の目的は、レイアウト設計においてランダム故障を考慮することによりＬＳＩの歩留を向上することができるレイアウト装置を提供することにある。
また、本発明の他の目的は、レイアウト設計においてランダム故障を考慮することによりＬＳＩの歩留を向上することができるレイアウトプログラムを提供することにある。
また、本発明の他の目的は、レイアウト設計においてランダム故障を考慮することによりＬＳＩの歩留を向上することができるレイアウトプログラム記録媒体を提供することにある。
【発明の開示】
本発明のレイアウト方法は、集積回路をレイアウトするレイアウト装置におけるレイアウト方法であって、回路データに従って複数のセルを概略の位置に配置し、複数のセルの概略の位置への配置の結果に従って複数のセルを具体的な位置に配置する工程を含む。複数のセルの具体的な位置への配置において、更に、複数のセルを具体的な位置に配置し、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、求めたクリティカルエリア値が小さくなるように複数のセルの具体的な位置を変更する。
本発明のレイアウト方法によれば、ランダム故障の発生と相関関係を有するパラメータとしてクリティカルエリア値を用い、これに基づいて回路データに表れるセルを具体的な位置に配置する。これにより、チップ上のどこでどのように発生するのかを予想することができないランダム故障を、ＬＳＩのレイアウト設計におけるセルの配置において考慮することができる。従って、配線率等のコストに加えて、コストとしてのランダム故障（即ち、クリティカルエリア値）を考慮しつつ、セルの配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、半導体ビジネスに大きく寄与することができる。ＬＳＩの加工プロセスが微細化する程、製造歩留りがデフェクト即ちランダム故障に依存すると考えられるので、レイアウト設計によりランダム故障を低減することができる影響は大きい。
また、好ましくは、本発明のレイアウト方法は、更に、回路データと複数のセルの具体的な位置への配置の結果とに従って複数のセルの間の配線を概略の位置に配置し、配線の概略の位置への配置の結果に従って配線を具体的な位置に配置する工程を含む。配線の具体的な位置への配置において、更に、配線を具体的な位置に配置し、隣接して配置された配線の各々の間におけるクリティカルエリア値を演算により求め、求めたクリティカルエリア値が所定の値より大きい場合であって当該位置の近傍に配線の空き領域が存在する場合、当該隣接して配置された配線の間に当該空き領域を挿入する。
この構成のレイアウト方法により、クリティカルエリア値に基づいて回路データに表れる配線を具体的な位置に配置する。これにより、配線率等及びランダム故障（即ち、クリティカルエリア値）を、ＬＳＩのレイアウト設計における配線の配置において考慮し、配線の配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、レイアウト設計によりランダム故障を低減することができる。
本発明のレイアウト装置は、集積回路をレイアウトするレイアウト装置であって、回路データに従って複数のセルを概略の位置に配置するグローバルプレースメント手段と、複数のセルの概略の位置への配置の結果に従って複数のセルを具体的な位置に配置するディテールプレースメント手段とを含む。ディテールプレースメント手段は、複数のセルを具体的な位置に配置し、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、前記求めたクリティカルエリア値が小さくなるように前記複数のセルの具体的な位置を変更する。
本発明のレイアウト装置によれば、前述と同様に、クリティカルエリア値に基づいて回路データに表れるセルを具体的な位置に配置する。これにより、配線率等及びランダム故障（即ち、クリティカルエリア値）を考慮しつつ、セルの配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、レイアウト設計によりランダム故障を低減することができる。
本発明のレイアウトプログラムは、集積回路をレイアウトするレイアウト方法を実現するレイアウトプログラムである。前記プログラムは、コンピュータに、回路データに従って複数のセルを概略の位置に配置させ、複数のセルの概略の位置への配置の結果に従って複数のセルを具体的な位置に配置させる。複数のセルの具体的な位置への配置において、更に、複数のセルを具体的な位置に配置させ、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求めさせ、求めたクリティカルエリア値が小さくなるように複数のセルの具体的な位置を変更させる。
本発明のレイアウトプログラム記録媒体は、前述のようなレイアウトプログラムをコンピュータ読取可能な記録媒体に記録する。
本発明のレイアウトプログラム及びその記録媒体によれば、レイアウトプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤＲ／Ｗ、ＤＶＤ等の種々のコンピュータ読み取り可能な記録媒体に格納することにより提供される。これにより、本発明のレイアウト方法及びレイアウト装置をコンピュータ上に実現することができる。
【図面の簡単な説明】  第１図はレイアウト装置構成図であり、本発明のレイアウト方法を実行するレイアウト装置の構成の概略を示す。
第２図は、クリティカルエリア値説明図である。
第３図は、クリティカルエリア値説明図である。
第４図は、クリティカルエリア値説明図である。
第５図はレイアウト処理フローであり、本発明のレイアウト装置が実行するレイアウト処理を示す。
第６図はレイアウト処理フローであり、ディテールプレースメント処理の一例を示す。
第７図はレイアウト処理フローであり、ディテールプレースメント処理の一例を示す。
第８図はレイアウト処理フローであり、ディテールプレースメント処理の一例を示す。
第９図はレイアウト処理フローであり、グローバルルーティング処理の一例を示す。
第１０図はレイアウト処理フローであり、ディテールルーティング処理の一例を示す。
第１１図はレイアウト処理フローであり、ディテールルーティング処理の他の一例を示す。
第１２図は、レイアウト処理説明図である。
第１３図は、レイアウト処理説明図である。
第１４図は、レイアウト処理説明図である。
第１５図は、レイアウト処理説明図である。
第１６図は、レイアウト処理説明図であり、特に、第１６図（Ａ）及び第１６図（Ｂ）はセルを示し、第１６図（Ｃ）はチップを示し、第１６図（Ｄ）乃至第１６図（Ｆ）はセルの関係を示す。
第１７図は、レイアウト処理説明図であり、特に、第１７図（Ａ）及び第１７図（Ｂ）はクリティカルエリア値テーブルの一例を示す。
第１８図は、レイアウト処理説明図であり、特に、第１８図（Ａ）乃至第１８図（Ｃ）はセルの位置の変更について示す。
第１９図は、レイアウト処理説明図であり、特に、第１９図（Ａ）及び第１９（Ｂ）は配線の位置の変更について示す。
第２０図は、レイアウト処理説明図であり、特に、第２０図（Ａ）は配線の位置の変更について示し、第２０図（Ｂ）及び第２０図（Ｃ）は当該変更によるタイミングの変化を示す。
【発明を実施するための最良の形態】  第１図はレイアウト装置構成図であり、本発明のレイアウト方法を実行するレイアウト装置の構成の概略を示す。
レイアウト装置は、レイアウト処理部１、回路データ格納部２、セルライブラリ３、クリティカルエリア値テーブル４、レイアウト結果格納部５からなる。この例では、クリティカルエリア値テーブル４はセルライブラリ３内にその一部として設けられるが、これには制限されない。レイアウト処理部１は、グローバルプレースメント処理部１１、ディテールプレースメント処理部１２、グローバルルーティング処理部１３、ディテールルーティング処理部１４、クリティカルエリア値演算部１５からなる。
回路データ格納部２は、例えばＬＳＩの回路設計の結果得られた回路データを格納する。なお、回路データは、ＬＳＩについての回路データに限られず、セラミックの配線基板やプリント基板上のハイブリッド集積回路等の回路データ等であってもよい。レイアウト処理部１は、回路データ格納部２から回路データを読み出して、これについてのレイアウトを行い、その結果をレイアウト結果格納部５に格納する。このレイアウトを行う際、レイアウト処理部１は、セルライブラリ３及びクリティカルエリア値テーブル４を参照する。セルライブラリ３は、回路データにおいて用いられるセルの実際の回路のパターンを格納する。クリティカルエリア値テーブル４は、隣接するセルの間におけるクリティカルエリア値を格納する。
レイアウト処理部１は、当該レイアウト処理を行うレイアウトプログラムを当該レイアウト装置のＣＰＵ（中央演算処理装置）で実行することにより実現される。この時、レイアウトプログラムは主記憶上に存在する。レイアウトプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤＲ／Ｗ、ＤＶＤ等の種々のコンピュータ読み取り可能な記録媒体に格納することにより提供される。回路データ格納部２、セルライブラリ３及びレイアウト結果格納部５は、ディスク装置等の補助記憶上に存在し、必要に応じて主記憶上に読み出される。
グローバルプレースメント処理部１１は、回路データ格納部２から回路データを読み出して、これに従って、周知のグローバルプレースメント処理により複数のセルを概略の位置に配置し、当該配置の結果（レイアウトデータ）をディテールプレースメント処理部１２へ送る。
ディテールプレースメント処理部１２は、グローバルプレースメント処理部１１における複数のセルの概略の位置への配置（グローバルプレースメント）の結果に従って、複数のセルを具体的な（詳細な）位置に配置する。即ち、チップ上での当該セルの位置（座標）を定める。具体的には、ディテールプレースメント処理部１２は、周知のディテールプレースメント処理により複数のセルを具体的な位置に配置し、この処理により隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求め、求めたクリティカルエリア値が小さくなるように複数のセルの具体的な位置を変更し、当該変更後の配置の結果（レイアウトデータ）をグローバルルーティング処理部１３へ送る。
このように、本発明では、レイアウト設計のセル配置においてランダム故障を考慮するための指標として、隣接するセルの間におけるクリティカルエリア値を用いる。クリティカルエリア値は、ランダム故障の起こり易さを示す指標であるが、これについては後述する。更に、本発明では、一旦配置されたセルの位置を、隣接するセルの間におけるクリティカルエリア値が小さくなるように変更する。これにより、ランダム故障の指標であるクリティカルエリア値をレイアウト、特にセルの配置に反映させ、ＬＳＩ全体のクリティカルエリア値を小さくして、ランダム故障の発生率を小さくし、製造歩留りを向上することができる。
隣接するセルの間におけるクリティカルエリア値は、セル（実際には、セル内のトランジスタ等の回路素子又は配線のパターン）間の距離に依存する。従って、当該距離が定まるディテールプレースメント処理において、当該距離に基づいてクリティカルエリア値を求める。
ディテールプレースメント処理部１２は、実際には、クリティカルエリア値テーブル４を参照することにより、隣接して配置された複数のセルの各々の間におけるクリティカルエリア値を求める。このために、クリティカルエリア値テーブル４が予め用意される。クリティカルエリア値テーブル４は、複数のセルを隣接して配置した場合の各々のセル間におけるクリティカルエリア値を予め演算により求めたものを格納する。
また、複数のセルの具体的な位置は、詳細は後述するが、交換処理、回転処理、閾値処理により変更される。即ち、交換処理においては、求めたクリティカルエリア値が当該２個のセルについての位置の交換により小さくなる場合、当該２個のセルについての位置交換を行なう。回転処理においては、求めたクリティカルエリア値が当該セルについての回転により小さくなる場合、当該セルについての回転を行なう。閾値処理においては、複数のセルの具体的な位置は、前記求めたクリティカルエリア値が所定の値よりも大きい場合、当該隣接して配置されたセルの間に隙間（スペース）を挿入することにより変更される。
グローバルルーティング処理部１３は、回路データ格納部２から回路データを読み出して、これとディテールプレースメント処理部１２における複数のセルのディテールプレースメントの結果とに従って、複数のセルの間の配線を概略の位置に配置する。具体的には、グローバルルーティング処理部１３は、周知のグローバルルーティング処理により配線を概略の位置に配置し、この処理により配置された配線の混雑度を求め、求めた配線の混雑度が小さくなるように、前記配線の概略の位置を変更し、当該配置の結果（レイアウトデータ）をディテールルーティング処理部１４へ送る。
ディテールルーティング処理部１４は、グローバルルーティング処理部１３における配線のグローバルルーティングの結果に従って、配線を具体的な位置に配置し、これにより完成したレイアウト結果をレイアウト処理部１における処理結果としてレイアウト結果格納部５に格納する。具体的には、ディテールルーティング処理部１４は、周知のディテールルーティング処理により配線を具体的な位置に配置し、この処理により隣接して配置された配線の各々の間におけるクリティカルエリア値を演算により求め、求めたクリティカルエリア値が所定の値より大きい場合であって、当該位置の近傍に配線の空き領域が存在する場合、当該隣接して配置された配線の間に当該空き領域を挿入する。
このように、本発明では、レイアウト設計の配線の配置においてランダム故障を考慮するための指標として、隣接する配線の間におけるクリティカルエリア値を用いる。更に、本発明では、一旦配置された配線の位置を、隣接する配線の間におけるクリティカルエリア値が所定の値よりも小さくなるように変更する。これにより、ランダム故障の指標であるクリティカルエリア値をレイアウト、特に配線の配置に反映させ、ＬＳＩ全体のクリティカルエリア値を小さくして、ランダム故障の発生率を小さくし、製造歩留りを向上することができる。
隣接する配線の間におけるクリティカルエリア値は、配線間の距離に依存する。従って、当該距離が定まるディテールルーティング処理において、当該距離に基づいてクリティカルエリア値を求める。
ディテールルーティング処理部１４は、実際には、クリティカルエリア値演算部１５に隣接して配置された配線の間におけるクリティカルエリア値の算出を依頼することにより、前記クリティカルエリア値を求める。クリティカルエリア値演算部１５は、所定の演算処理により前記クリティカルエリア値を求め、ディテールルーティング処理部１４に渡す。
また、ディテールルーティング処理部１４は、前述の空き領域を挿入した場合には、必要に応じて、その結果として新たにタイミングのエラーが生じるか否かを調べる。そして、当該エラーを生じる場合、ディテールルーティング処理部１４は、当該挿入された空き領域を削除して、当該隣接して配置された配線の具体的な位置を当該挿入以前の状態とする。
ここで、クリティカルエリア値について、第２図を参照して説明する。クリティカルエリア値は、以下のようにして求められる。第２図に示すように、デフェクトＤが半径ｒの円形であるとする。デフェクトＤの中心（デフェクト中心）がそこに落ちたときに、２本の配線Ｗがショート又はオープン（以下、単にショートという）を起こすチップ上の点からなる領域の面積をＡ（ｒ）とする。面積Ａ（ｒ）は半径ｒのデフェクトＤのショート故障頻度の指標となる。即ち、面積Ａ（ｒ）が大きければ故障は多く、小さければ故障は少ないと考えられる。半径ｒのデフェクトＤの分布確率密度をＤ（ｒ）とする。このとき、デフェクト半径ｒのショート領域面積Ａ（ｒ）を分布確率密度Ｄ（ｒ）で積分した量ＡＣ（無名数）をクリティカルエリア又はクリティカルエリア値といい、以下のように求まる。即ち、
ＡＣ＝∫Ａ（ｒ）Ｄ（ｒ）ｄｒ（∫は「０」から「∞」まで）
である。
クリティカルエリア値ＡＣは、チップのデフェクトＤに対する平均的なショート領域面積を表している。従って、クリティカルエリア値ＡＣは、与えられたチップに対するランダム故障（又は歩留り）の指標となる量である。クリティカルエリア値ＡＣを計算する方法としては、モンテカルロ法、グリッド法、ボロノイ図法等、種々の周知の方法がある。なお、クリティカルエリア値ＡＣは、後述するように、チップのデフェクトＤに対する平均的なショート領域面積を表しており、ショート故障頻度、更にはランダム故障の指標となると考えられいた。しかし、これをレイアウト設計のセル及び配線の配置においてランダム故障を考慮するための指標として用いることは、本発明の知見に基づくものである。
クリティカルエリア値ＡＣは、前述のように、ディテールプレースメント処理及びディテールルーティング処理において用いられる。しかし、前者はセルの配置の処理であり、また、レイアウト処理に先立って用意できる。後者は配線の配置の処理であり、また、レイアウト処理において演算を実行しなければならない。両者における用途等が異なるので、以下のように異なる演算方法を用いることが望ましい。
ディテールプレースメント処理においては、ディテールプレースメント処理部１２は、予め用意されたクリティカルエリア値テーブル４を参照することにより、隣接するセルの間におけるクリティカルエリア値ＡＣを求める。即ち、予め用意されるものであり、また、クリティカルエリア値テーブル４を用意するために一度だけ演算すれば済むので、特に演算時間の長短は問題とならない。一方、セルの間におけるクリティカルエリア値ＡＣは、セルの内部のパターン形状（例えば、トランジスタの配置や形状）に依存するので、詳細な演算を行う必要がある。そこで、クリティカルエリア値ＡＣを求める演算方法として、詳細な演算に向いているモンテカルロ法を用いる。クリティカルエリア値テーブル４に格納されたクリティカルエリア値ＡＣは、既知の形状のセルの間におけるクリティカルエリア値ＡＣをモンテカルロ法により求めたものである。
ディテールルーティング処理においては、ディテールルーティング処理部１４は、クリティカルエリア値演算部１５に演算を依頼することにより、隣接する配線の間におけるクリティカルエリア値ＡＣを求める。即ち、レイアウト処理の中で個々の配線についてクリティカルエリア値ＡＣの演算を繰り返し行わなければならない。従って、演算時間が最大の問題である。従って、モンテカルロ法、グリッド法、ボロノイ図法等によってもよいが、この場合には長時間を要する。そこで、クリティカルエリア値ＡＣの演算は、以下のような方法によることが望ましい。
モンテカルロ法等が計算時間を多く要するのは、形状についての普遍性が高い手法を用いるためである。そこで、配線形状が、配線方向への細長い長方形が平行に並んでいる場合が多いことに着目して、このような配線形状の性質を利用して、クリティカルエリア値ＡＣを比較的簡便に高速に演算する。具体的には、配線データを所定の方向に走査し、当該走査の結果に基づいて相互に平行に配置される３本の配線の存在する領域を検出し、当該検出した領域についてのみクリティカルエリア値ＡＣを算出する。
この演算方法（以下、平行配線法という）によれば、任意の形状をとる配線についての普遍性が高い手法を用いることなく、配線データを走査するのみで、比較的簡単なアルゴリズムで短い計算時間でクリティカルエリア値ＡＣを計算することができる。クリティカルエリア値ＡＣの正確な算出が目的ではなく、レイアウトの指標とするのであるから、平行配線法による演算で十分である。
平行配線法によるクリティカルエリア値ＡＣの演算についての基本概念を第３図及び第４図に示す。
平行配線法によるクリティカルエリア値ＡＣの演算処理が対象とする配線形状を説明する。第３図に示すように、ＬＳＩチップ上において、配線は配線方向において同一の又は平行な領域（以下、トラックと言う）上に乗っているものとする。多くの高集積度のＬＳＩにおいて、セル間の配線はこのような配線の形状を有すると考えてよい。トラックは、下から順に、Ｉ、ＩＩ、ＩＩＩ、・・・とされる。トラックの長さは、最大でＬとされる。ＬＳＩチップ（又は、処理対象の配線領域、以下同じ）の下辺Ｂ及び上辺Ｔは、長さＬのトラックであり、その全体に配線が形成されているものとみなす（仮定する）。クリティカルエリア値ＡＣの演算処理時の走査方向は、例えば第３図のように定められる。即ち、トラックＢ、Ｉ、ＩＩ、ＩＩＩ、・・・Ｔの順に操作され、同一のトラックにおいてその左側から順に走査される。走査を開始する位置の座標を「０」とする。
また、平行配線法によるクリティカルエリア値ＡＣの演算処理においては、デフェクト半径に関する分布確率密度Ｄ（ｒ）は、以下の式で表されると（経験則から）仮定する。即ち、
Ｄ（ｒ）＝ｃｒｑ／ｒ０ｑ＋１（０≦ｒ≦ｒ０の場合）
＝ｃｒ０ｐ−１／ｒｐ（ｒ０≦ｒの場合）
である。ここで、ｃ＝（ｑ＋１）（ｐ−１）／（ｐ＋ｑ）である。更に、説明の簡単のため、以下の説明においては、ｐ＝３、ｑ＝１とする。
いま、第４図に示すように、ＬＳＩの配線データの中で、３本の（横方向に）平行な配線があるとする。このとき、中間（２本目）の配線を含む、１番目及び２番目配線と等距離にある線分と２番目及び３番目配線と等距離にある線分に囲まれた領域に関するクリティカルエリア値ＡＣ（第４図において太い斜線を付して示す）は簡単に計算でき、
ＡＣ＝ｒ０２Ｌ（２／（ａ３−ｂ１）−１／（２ａ３−ｂ１−ａ２）−１／（ａ３＋ｂ２−２ｂ１））
となる。ここで、第４図に示すように、Ｌは当該領域の長さ、ａ１及びｂ１は最下層の配線ｎｋの各々下端及び上端の座標、ａ２及びｂ２は中間の配線ｎｊの各々下端及び上端の座標、ａ３及びｂ３は最上層の配線ｎｉの各々下端及び上端の座標である。
平行配線法によるクリティカルエリア値ＡＣの演算処理は、配線データを前述の走査方向（後述する横方向及び縦方向）に順に走査することにより、第４図のような配線の重なり（重なりノード）を検出し、それについて逐次的にクリティカルエリア値ＡＣを近似的計算する。例えば、第３図の配線データにおいても、第４図の配線の重なりを持つ領域が数多く存在し、これらはその配線の座標を調べることにより容易に検出することができ、かつ、そのクリティカルエリア値ＡＣも前述の式により容易に近似的計算することができる。これにより、基本的に、配線（配線データ）の走査のみでクリティカルエリア値ＡＣの演算処理を行うことができるため、高速に計算することができる。
第５図はレイアウト処理フローであり、本発明のレイアウト装置が実行するレイアウト処理を示す。
グローバルプレースメント処理部１１が、回路データ格納部２から回路データを読出し、これに従って、セルライブラリ３のセルを用いて、第１２図の上段に示すように、複数のセルを概略の位置に配置する。即ち、グローバルプレースメント処理する（ステップＳ１１）。これについては後述する。
ディテールプレースメント処理部１２が、グローバルプレースメント処理部１１における複数のセルの概略の位置への配置の結果に従って、第１２図の下段に示すように、複数のセルを具体的な位置に配置する。即ち、ディテールプレースメント処理する（ステップＳ１２）。これについては、第６図乃至第８図を参照して後述する。
グローバルルーティング処理部１３が、回路データ格納部２から回路データを読出し、この回路データと、ディテールプレースメント処理部１２における複数のセルの具体的な位置への配置の結果とに従って、第１３図の上段に示すように、複数のセルの間の配線６４を概略の位置に配置する。即ち、グローバルルーティング処理する（ステップＳ１３）。これについては、第９図を参照して後述する。
ディテールルーティング処理部１４が、配線６４の概略の位置への配置の結果に従って、第１３図の下段に示すように、配線６４を具体的な位置に配置する。即ち、ディテールルーティング処理する（ステップＳ１４）。これについては、第１０図及び第１１図を参照して後述する。
最初に、第５図のステップＳ１１におけるグローバルプレースメント処理について詳細に説明する。
グローバルプレースメント処理部１１における周知のグローバルプレースメント処理の一例を以下に示す。即ち、回路データ格納部２の回路データから所定の順にセル６３が読み出され、第１２図の上段に示すように、所定の順でｎ個づつグローバルブロック６２に割り当てられる。グローバルブロック６２は、点線で示すように、例えばチップ６１を大きさの等しい複数の長方形（又は正方形）に仮想的に区切った領域である。グローバルブロック６２の数はこれに限られない。全てのセル６３がいずれかのグローバルブロック６２に割り当てられ、当該グローバルブロック６２内の空いている位置に配置される。この後、異なるグローバルブロック６２に割り当てられた各々のセル６３の位置を交換して、配線長等のコストが低下するなら交換後の配置を採用し、低下しないなら交換前の配置を採用する。これらのコストは、例えば配線が未だ定まっていないので、概略の計算により求める。これにより得られるセル６３のレイアウトが、周知のグローバルプレースメント処理の結果である。
回路データ格納部２は、例えばＬＳＩの回路設計の結果得られた回路データを格納する。この回路データは、第１４図に示すように、インバータやＮＡＮＤゲート回路のような複数のセル６３と、これらのセル６３の間を接続する配線６４とからなる。セル６３は、例えば回路記号、セル名（例えばＩＮＶ＃１）、当該セル６３の出現の順番（例えば（１）はＩＮＶ＃１の１番目）からなる。セル６３は、回路設計及びレイアウト設計において用いられる単位回路である。回路データにおいて用いることができる複数の種類のセル６３が、セルライブラリ３に予め用意される。
セルライブラリ３は、回路データにおいて用いられるセル６３即ち単位回路の種類ごとに、その実際のレイアウトパターンを格納する。セルライブラリ３は、第１５図に示すように、セル６３のリスト３１、セル６３のパターン３２からなり、他にクリティカルエリア値テーブル４を含む。リスト３１は、ＩＮＶ＃１等のセル名を格納する。各々のセル名はパターン３２をポイントする。パターン３２は、セル名の各々に対応して設けられ、当該セル６３の実際のレイアウトパターン（トランジスタ等のパターン、セル６３内の配線のパターン等）を格納する。ＩＮＶ＃１、ＩＮＶ＃２及びＮＡＮＤは、各々、反転回路＃１、反転回路＃２及びナンドゲート回路のセル６３の名前を示す。
なお、セル６３はこれらの例に限られない。例えば、セル６３は、ハーフアダー、フリップフロップ、セレクタ等の程度の回路を含む。例えば、フルアダー、シフトレジスタ、乗算回路等は、セル６３よりも大きいマクロとされ、複数のセル６３の組み合わせにより構成される。
また、セル６３には方向性がある。即ち、セル６３が、第１６図（Ａ）に示すような方向であるとすると、その内部のレイアウトパターンは第１６図（Ｂ）に示すようになる。第１６図（Ａ）及び第１６図（Ｂ）は、図示の便宜のため、簡単なセル６３を示すが、セル６３は、基本的には、上下及び左右に対象ではない。なお、第１６図（Ｂ）においては電源部分の図示を省略している。第１６図（Ａ）に示すセル６３のＡＢＣ及びＤの各辺が、第１６図（Ｃ）に示すＬＳＩのチップ６１のＡＢＣ及びＤの各辺に対応するように、セル６３が配置される。これにより、セル６３の上下左右が定まる。従って、第１６図（Ｄ）に示す通常（又は基本）のセル６３を基準とすると、第１６図（Ｅ）に示す１８０度回転したセル６３、第１６図（Ｆ）に示す鏡面の関係にあるセル６３が存在する。なお、第１６図（Ｄ）において、セル６３内の文字Ｆは、当該セル６３の方向を示すために便宜的に付したものである（他の図においても同じ）。
次に、第５図のステップＳ１２におけるディテールプレースメント処理について詳細に説明する。前述のように、本発明のディテールプレースメント処理においては、周知のディテールプレースメント処理の後に、セル６３の位置を変更するために、少なくとも、セル６３の交換処理、回転処理、閾値処理のいずれかが実行される。即ち、第６図、第７図及び第８図のいずれかのディテールプレースメント処理が実行される。
第６図はレイアウト処理フローであり、第５図のステップＳ１２においてディテールプレースメント処理部１２が実行するディテールプレースメント処理の一例を示す。
ディテールプレースメント処理部１２が、グローバルプレースメント処理部１１におけるグローバルプレースメントの結果を用いて、複数のセル６３を具体的な位置に配置する。即ち、周知のディテールプレースメント処理を実行する（ステップＳ２１）。
ディテールプレースメント処理部１２における周知のディテールプレースメント処理の一例を示す。即ち、グローバルプレースメントの結果に基づいて、第１２図の下段に示すように、各々のグローバルブロック６２内において、これに割り当てられたｎ個のセル６３（＃１〜＃ｎ）について、グリッドＧ上に配置する。即ち、セル６３の各辺がグリッドＧ上に位置するようにされる。グリッドＧは、グローバルブロック６２内において、仮想的に設けた直線である。グリッドＧは、縦及び横方向に等しい間隔で平行に複数本設けられ、その間隔はプロセスの最小加工寸法に依存する。セル６３の各辺はグリッドＧ上になければならない（セル６３のサイズがそのような大きさとされる）。第１２図において、グリッドＧは、図示の便宜のため、グローバルブロック６２の外に目盛りとして示される。この後、同一のグローバルブロック６２内において、各々のセル６３の位置を交換して、配線長等のコストが低下するなら交換後の配置を採用し、低下しないなら交換前の配置を採用する。これらのコストは、例えば配線が未だ定まっていないので、概略の計算により求める。これにより得られるセル６３のレイアウトが、周知のディテールプレースメント処理の結果である。
ディテールプレースメント処理部１２が、クリティカルエリア値テーブル４のクリティカルエリア値ＡＣを用いて、第１８図（Ａ）に示す当該セル６３についての位置の交換によりクリティカルエリア値ＡＣが当該交換前より小さくなる場合、当該セル６３についての交換を行なう（ステップＳ２２）。これにより、複数のセル６３の具体的な位置が変更される。
ディテールプレースメント処理部１２は、セル６３の交換処理において、クリティカルエリア値テーブル４１を用いる。クリティカルエリア値テーブル４１は、第１７図（Ａ）に示すように、セル６３ごとに、当該セル６３（列のセル）を行のセルの右隣にレイアウトした場合におけるクリティカルエリア値ＡＣを格納する。即ち、セル６３の種類の数をＣとすると、全てのセル６３の組み合わせＣ×Ｃについて、各々が右隣に配置された場合におけるクリティカルエリア値ＡＣを計算し、格納する。
前述のように、セル６３の方向は予め定められている。従って、「右隣にレイアウトする」とは、あるセル６３の辺Ｄに他のセル６３の辺Ｂが位置するようにレイアウトすることである。セル６３の内部は、前述のように、左右対称とは限らないので、あるセル６３の右隣にどのセル６３が配置されるかによって、当該２個のセル６３間のクリティカルエリア値ＡＣ（以下、単に値ＡＣともいう）が異なる。
例えば、第１８図（Ａ）に示すように、ステップＳ２１により４個のセルＡＢＣ及びＤがこの順に配置されたとする。この状態で、セルＢの位置とセルＣの位置とを交換してみる。これにより、セルＡとセルＢとの間の値ＡＣがセルＡとセルＣとの間の値ＡＣに変更され、セルＢとセルＣとの間の値ＡＣがセルＣとセルＢとの間の値ＡＣに変更され、セルＣとセルＤとの間の値ＡＣがセルＢとセルＤとの間の値ＡＣに変更される。変更前の値ＡＣの合計より、変更後の値ＡＣの合計が小さければ、セルＢの位置とセルＣの位置とを交換する。これにより、ＬＳＩ全体としての値ＡＣは小さくなり、ランダム故障の発生率は低下する。
第７図はレイアウト処理フローであり、第５図のステップＳ１２においてディテールプレースメント処理部１２が実行するディテールプレースメント処理の一例を示す。
ディテールプレースメント処理部１２が、ステップＳ２１と同様にして、周知のディテールプレースメント処理により、複数のセル６３を具体的な位置に配置する（ステップＳ２３）。
ディテールプレースメント処理部１２が、クリティカルエリア値テーブル４のクリティカルエリア値ＡＣを用いて、第１８図（Ｂ）に示す当該セル６３についての回転によりクリティカルエリア値ＡＣが当該回転前より小さくなる場合、当該セル６３についての回転を行なう（ステップＳ２４）。これにより、複数のセル６３の具体的な位置が変更される。
ディテールプレースメント処理部１２は、セル６３の回転処理において、クリティカルエリア値テーブル４２を用いる。クリティカルエリア値テーブル４２は、第１７図（Ｂ）に示すように、通常のセル６３（Ｎを付して表す）及び当該セル６３を１８０度回転したセル６３（Ｒを付して表す）ごとに、当該セル６３（列のセル）を行のセル６３の右隣にレイアウトした場合におけるクリティカルエリア値ＡＣを格納する。即ち、セル６３の種類の数をＣとすると、全てのセル６３の組み合わせ２Ｃ×２Ｃについて、各々が右隣に配置された場合におけるクリティカルエリア値ＡＣを計算し、格納する。
殆どの場合、セル６３の回転は回転角度が１８０度である場合を考慮すればよい。しかし、必要に応じて、９０度又は２７０度回転したセル６３を、セルライブラリ３に用意するようにしてもよい。この場合、クリティカルエリア値テーブル４２は、全てのセル６３の組み合わせＲＣ×ＲＣについて、クリティカルエリア値ＡＣを格納する。ここで、Ｒは回転の種類であり、例えば１〜４（０度、９０度、１８０度、２７０度）の値をとる。クリティカルエリア値テーブル４１はＲ＝１（０度のみ）の場合を示し、クリティカルエリア値テーブル４２はＲ＝２（０度及び１８０度）の場合を示す。
例えば、第１８図（Ｂ）に示すように、ステップＳ２３により３個のセルＡＢ及びＣがこの順に配置されたとする。この状態で、セルＢを１８０度回転してみる。これにより、セルＡ（Ｎ）とセルＢ（Ｎ）との間の値ＡＣがセルＡ（Ｎ）とセルＢ（Ｒ）との間の値ＡＣに変更され、セルＢ（Ｎ）とセルＣ（Ｎ）との間の値ＡＣがセルＢ（Ｒ）とセルＣ（Ｎ）との間の値ＡＣに変更する。変更前の値ＡＣの合計より、変更後の値ＡＣの合計が小さければ、セルＢを回転する。これにより、ＬＳＩ全体としての値ＡＣは小さくなり、ランダム故障の発生率は低下する。
なお、第１６図（Ｄ）に示す通常のセル６３に対して、第１６図（Ｆ）に示す内部のパターンが鏡面の関係にあるセル６３（Ｍを付して表す）も存在し得る。必要に応じて、当該鏡面の関係にあるセル６３を、セルライブラリ３に用意するようにしてもよい。この場合、クリティカルエリア値テーブル４２は、セル（Ｍ）についても、同様に各々の配置の場合についての値ＡＣを格納する。更に、セル（Ｍ）を種々の角度で回転したセル６３をセルライブラリ３に用意し、その値ＡＣをクリティカルエリア値テーブル４２に格納するようにしてもよい。
第８図はレイアウト処理フローであり、第５図のステップＳ１２においてディテールプレースメント処理部１２が実行するディテールプレースメント処理の一例を示す。
ディテールプレースメント処理部１２が、ステップＳ２１と同様にして、周知のディテールプレースメント処理により、複数のセル６３を具体的な位置に配置する（ステップＳ２５）。
ディテールプレースメント処理部１２が、クリティカルエリア値テーブル４のクリティカルエリア値ＡＣを用いて、クリティカルエリア値ＡＣが閾値αよりも大きい場合、第１８図（Ｃ）に示すように、当該隣接して配置されたセル６３の間に隙間を挿入する（ステップＳ２６）。これにより、複数のセル６３の具体的な位置が変更される。
ディテールプレースメント処理部１２は、セル６３の閾値処理において、クリティカルエリア値テーブル４１又は４２を用いる。例えば、第１８図（Ｃ）に示すように、ステップＳ２５により２個の通常のセルＡ及びＢがこの順に配置されたとする。この状態で、クリティカルエリア値テーブル４１の参照により、セルＡとセルＢとの間の値ＡＣを求め、これを閾値αと比較し、値ＡＣが閾値αよりも大きければ、セルＡとセルＢとの間に１グリッド分の隙間を挿入する。閾値αの値は経験的に予め定められる。回転したセル６３及び鏡面の関係にあるセル６３についても同様である。これにより、ＬＳＩ全体としての値ＡＣは小さくなり、ランダム故障の発生率は低下する。
なお、ディテールプレースメント処理部１２が、セル６３の交換処理、回転処理、閾値処理を全て実行するようにしてもよい。例えば、ステップＳ２１の後、ステップＳ２２、Ｓ２４、Ｓ２６を順に実行してもよい。また、ステップＳ２２、Ｓ２４、Ｓ２６の実行の順を適宜入れ換えてもよい。更に、３個の処理のいずれか２個の処理を選択して実行するようにしてもよい。クリティカルエリア値テーブル４２を設ける場合、クリティカルエリア値テーブル４１は省略することができる。
次に、第５図のステップＳ１３におけるグローバルルーティング処理について詳細に説明する。第９図はレイアウト処理フローであり、第５図のステップＳ１３においてグローバルルーティング処理部１３が実行するグローバルルーティング処理の一例を示す。
グローバルルーティング処理部１３が、回路データ格納部２から回路データを読出し、これに従って、配線６４を概略の位置に配置する（ステップＳ３１）。グローバルルーティング処理部１３における周知のグローバルルーティング処理の一例を示す。即ち、回路データ格納部２の回路データから所定の順に配線６４が読み出され、第１３図の上段に示すように、当該配線６４が接続するセル６３（第１３図には現れない）の配置されたグローバルブロック６２の間に配置される。全ての配線６４が１又は複数のグローバルブロック６２を通るように配置される。これにより得られる配線６４のレイアウトが、周知のグローバルルーティング処理の結果である。
グローバルルーティング処理部１３が、所定の演算により、グローバルブロック６２毎に、配置された配線６４の混雑度Ｋ＝ｎ１／ｎ２を求める（ステップＳ３２）。ここで、ｎ１は当該グローバルブロック６２に実際に配置された配線６４の本数であり、ｎ２は当該グローバルブロック６２に許容される配線６４の最大本数である。従って、ｎ２は、例えば当該グローバルブロック６２に存在するグリッドの数である。
グローバルルーティング処理部１３が、配線６４の混雑度が小さくなるように、配線６４の概略の位置を変更する（ステップＳ３３）。即ち、グローバルブロック６２毎の混雑度を均一化するように、再度グローバルルーティング処理を行なう。これにより、クリティカルエリア値ＡＣが極端に高い領域を無くすことができる。例えば、第１９図（Ａ）において、配線６４の混雑度が大きいグローバルブロック６２と小さいグローバルブロック６２とを求める。この場合、縦方向の配線６４に着目すると、第１行第２列、第２行第２列、第３行第２列及び第４行第２列のグローバルブロック６２（以下、これをＧＢ（１，２）、ＧＢ（２，２）、ＧＢ（３，２）及びＧＢ（４，２）と表す）において、その混雑度が高いことが判る。そこで、第１９図（Ｂ）に示すように、配線６４を移動させる（配線６４の位置を変更する）。即ち、混雑度の低いグローバルブロックＧＢ（２，１）及び（３，１）へ１本の配線６４を移動させ、グローバルブロックＧＢ（１，３）、ＧＢ（２，３）及びＧＢ（３，３）へ２本の配線６４を移動させる。第１９図（Ｂ）において、移動前の配線６４を点線で示し、移動後の配線６４を実線で示す。点線と対となっていない（実線のみの）配線６４は、移動されなかった配線である。これにより、縦方向の配線６４について（着目したグローバルブロック６２についての）混雑度が均一化される（実際の本数は更に多い）。横方向の配線６４についても、同様に混雑度が均一化される。
なお、配線６４の混雑度の均一化処理（ステップＳ３３）を実行する前に、周知の配線６４の混雑度の最適化処理が実行するようにしてもよい。しかし、これによっては配線６４の混雑度が均一化されないので、クリティカルエリア値ＡＣのかなり高い領域が残ってしまう。従って、均一化処理によりクリティカルエリア値ＡＣの最適化の前処理を行なうことが望ましい。
次に、第５図のステップＳ１４におけるディテールルーティング処理について詳細に説明する。第１０図はレイアウト処理フローであり、第５図のステップＳ１４においてディテールルーティング処理部１４が実行するディテールルーティング処理の一例を示す。
ディテールルーティング処理部１４が、グローバルルーティング処理部１３におけるグローバルルーティングの結果を用いて、配線６４を具体的な位置に配置する（ステップＳ４１）。ディテールルーティング処理部１４における周知のディテールルーティング処理の一例を示す。即ち、グローバルルーティングの結果に基づいて、第１３図の下段に示すように、各々のグローバルブロック６２内において、これに到達する又はこれを通過する配線６４について、グリッドＧ上に配置する。即ち、配線６４がグリッドＧ上に位置するようにされる。配線６４はグリッドＧ上になければならない。この後、同一のグローバルブロック６２内において、第１３図の下段に示すように、各々の配線６４の位置を変更して、配線長等のコストが低下するなら変更後の配置を採用し、低下しないなら変更前の配置を採用する。第１３図の下段において、変更前の配線６４を点線で示し、変更後の配線６４を実線で示す。これにより得られるセル６３のレイアウトが、周知のディテールルーティング処理の結果である。
ディテールルーティング処理部１４が、クリティカルエリア値演算部１５に依頼して、ディテールルーティング処理の結果、隣接して配置された配線６４の各々の間におけるクリティカルエリア値ＡＣを求める（ステップＳ４２）。前述のように、クリティカルエリア値演算部１５は、ディテールルーティング処理部１４からの依頼に応じて、モンテカルロ法等にはよらず、平行配線法による演算で、隣接する配線６４の間におけるクリティカルエリア値ＡＣを求め、その結果をディテールルーティング処理部１４に返す。
即ち、クリティカルエリア値演算部１５は、前記依頼と共に、ディテールルーティング処理の結果（である配線データ）を受け取る。この配線データは、第３図に示すような配線６４の縦方向及び横方向の組み合わせとなっている。次に、クリティカルエリア値演算部１５は、当該配線データを前述の所定の方向に走査し、当該走査の結果に基づいて第４図のような等間隔で相互に平行に配置される３本の配線６４の存在する領域を検出する。これは、配線６４の座標を調べることにより容易に検出することができる。前記検出のアルゴリズムとしては種々のものが考えられる。配線６４は２方向に延びるので、走査及び検出も当該２方向について行われる。次に、クリティカルエリア値演算部１５は、当該検出した領域の各々について、前述の式によりクリティカルエリア値ＡＣを逐次的に算出する。これにより、配線データの２方向についての走査のみで、クリティカルエリア値ＡＣを高速に計算することができる。
ディテールルーティング処理部１４が、クリティカルエリア値演算部１５により求めたクリティカルエリア値ＡＣが所定の値より大きい領域（ハイコスト領域Ｈ）を検索する（ステップＳ４３）。即ち、コストとしてのクリティカルエリア値ＡＣを改善すべき領域を求める。前記所定の値は経験的に予め定められる。例えば、１個のグローバルブロック６２内において、第２０図（Ａ）に示すように、ハイコスト領域Ｈが存在する場合がある。
ディテールルーティング処理部１４が、ハイコスト領域Ｈの周囲においてこれに隣接する空き領域（スペース）Ｓが存在するか否かを調べる（ステップＳ４４）。空き領域Ｓは、クリティカルエリア値ＡＣが０の領域（即ち、配線６４の本数が０の未配線領域）又はこれに近い値の領域である。例えば、１個のグローバルブロック６２内において、第２０図（Ａ）に示すように、空き領域Ｓが存在する場合がある。
空き領域Ｓが存在する場合、ディテールルーティング処理部１４が、当該ハイコスト領域Ｈの隣接して配置された配線６４の間にスペースを挿入することにより、再配線処理を行なう（ステップＳ４５）。例えば、第２０図（Ａ）において、ハイコスト領域Ｈに隣接する空き領域Ｓを含めてこれらを新たな領域Ｈ’とし、領域Ｈ’内に存在する配線６４の間に１グリッド分のスペースを挿入し、クリティカルエリア値ＡＣを小さくする。例えば、ハイコスト領域Ｈの配線６４の中で空き領域Ｓに近い側から順に、１グリッドづつスペースを挿入していく。ハイコスト領域Ｈの配線６４の本数よりも空き領域Ｓのグリッドの数が小さければ、ハイコスト領域Ｈの全ての配線６４の間にスペースを挿入することはできない。しかし、この場合でも、ＬＳＩ全体のクリティカルエリア値ＡＣは小さくなる。これにより得られる配線６４のレイアウトが、最終的なグローバルルーティング処理の結果である。なお、空き領域Ｓが存在しない場合、再配線処理（ステップＳ４５）は実行しない。
第１１図はレイアウト処理フローであり、第５図のステップＳ１４においてディテールルーティング処理部１４が実行するディテールルーティング処理の他の一例を示す。第１１図に示す処理は、第１０図に示す処理において、ステップＳ４５の後に処理を終了することなく、続けて実行される。
ステップＳ４５に続いて、ディテールルーティング処理部１４が、タイミングを再計算し、ステップＳ４５におけるスペースの挿入の結果、タイミングのエラーが生じるか否かを調べる（ステップＳ４６）。空き領域を挿入した結果、第２０図（Ａ）から判るように、当該位置を変更された配線６４の長さは、挿入したスペース（即ち、グリッドの数）の例えば２倍長くなる。これにより、当該配線６４の抵抗Ｒ及び寄生容量Ｃが大きくなり、時定数も大きくなるので、当該配線６４を伝搬する信号の遅延時間も大きくなる。例えば、当該配線６４が、第２０図（Ｂ）に示すように、フリップフロップ回路ＦＦ＃１及びＦＦ＃２へクロック信号ＣＬＫを供給する配線６４であるとする。この配線６４が、前述のように、その位置を変更されると、第２０図（Ｃ）に示すように、クロック信号ＣＬＫが遅延する。即ち、当該配線６４が、第２０図（Ａ）及び第２０図（Ｂ）に点線で示す直線形状から実線で示す迂回形状にされ、これにより、クロック信号ＣＬＫが、第２０図（Ｃ）に点線で示すタイミングから実線で示すタイミングに遅延する。このため、本来先に入力されるべきクロック信号ＣＬＫの入力が、フリップフロップ回路ＦＦ＃２への入力信号の入力よりも遅れてしまう。これにより、タイミングのエラーとなる。
タイミングのエラーが生じる場合、ディテールルーティング処理部１４が、当該挿入された空き領域を削除して、当該隣接して配置された配線６４の具体的な位置を当該挿入以前の状態とする（ステップＳ４７）。これにより、ランダム故障の発生率を低下させつつ、タイミングの悪化を防止することができる。なお、この場合、ステップＳ４３において検出したハイコスト領域Ｈが残る。そこで、実際には、ステップＳ４７において、タイミングのエラーを生じる配線６４を当該挿入以前の状態とし、その上で、支障のない範囲で、ハイコスト領域Ｈの他の配線６４の間にスペースを挿入するようにしてもよい。
【産業上の利用可能性】  以上説明したように、本発明によれば、レイアウト方法において、クリティカルエリア値に基づいて回路データに表れるセルを具体的な位置に配置することにより、ランダム故障を、ＬＳＩのレイアウト設計におけるセルの配置において考慮することができる。従って、配線率等のコストに加えて、コストとしてのランダム故障を考慮しつつ、セルの配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、半導体ビジネスに大きく寄与することができる。ＬＳＩの加工プロセスが微細化する程、製造歩留りがランダム故障に依存すると考えられるので、レイアウト設計によりランダム故障を大きく低減することができる。
また、本発明によれば、レイアウト方法において、更に、クリティカルエリア値に基づいて回路データに表れる配線を具体的な位置に配置することにより、配線率等及びランダム故障を、ＬＳＩのレイアウト設計における配線の配置において考慮し、配線の配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、レイアウト設計によりランダム故障を低減することができる。
また、本発明によれば、レイアウト装置において、クリティカルエリア値に基づいて回路データに表れるセルを具体的な位置に配置することにより、配線率等及びランダム故障を考慮しつつ、セルの配置について最適なレイアウト設計を行うことができる。この結果、ＬＳＩの歩留りを意図的に向上させることができ、レイアウト設計によりランダム故障を低減することができる。
また、本発明によれば、レイアウトプログラム及びその記録媒体において、レイアウトプログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤＲ／Ｗ、ＤＶＤ等の種々のコンピュータ読み取り可能な記録媒体に格納することにより提供される。これにより、本発明のレイアウト方法及びレイアウト装置をコンピュータ上に実現することができる。
【図１】
2004034463.tif 000003
【図２】
2004034463.tif 000004
【図３】
2004034463.tif 000005
【図４】
2004034463.tif 000006
【図５】
2004034463.tif 000007
【図６】
2004034463.tif 000008
【図７】
2004034463.tif 000009
【図８】
2004034463.tif 000010
【図９】
2004034463.tif 000011
【図１０】
2004034463.tif 000012
【図１１】
2004034463.tif 000013
【図１２】
2004034463.tif 000014
【図１３】
2004034463.tif 000015
【図１４】
2004034463.tif 000016
【図１５】
2004034463.tif 000017
【図１６】
2004034463.tif 000018
【図１７】
2004034463.tif 000019
【図１８】
2004034463.tif 000020
【図１９】
2004034463.tif 000021
【図２０】
2004034463.tif 000022
【国際調査報告】
2004034463.tif 000023
2004034463.tif 000024
2004034463.tif 000025
2004034463.tif 000026