(57)【要約】【課題】簡単な処理で、希望するパターンを得るレイアウト設計を可能にする。【解決手段】  未配線ネットを選択する選択手段２２と、選択された前記未配線ネット及びその周辺の所定の既配線ネットを含む領域から、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンとのずれに対する補正処理が困難となる領域を検出して、補正処理の困難さの度合いをデータ化した補正処理困難度を出力する補正処理困難度検出手段２１，２４と、前記補正処理が困難となる領域近傍に、前記補正処理困難度に基づくコストを設定するコスト設定手段２３と、前記コストを用いて、前記未配線ネットの配線経路の探索を行う配線経路探索手段２５と、を具備したことを特徴とする。【選択図】図１
2008166606.tif 000002
【特許請求の範囲】
【請求項１】
未配線ネットを選択する選択手段と、
選択された前記未配線ネット及びその周辺の所定の既配線ネットを含む領域から、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンとのずれに対する補正処理が困難となる領域を検出して、補正処理の困難さの度合いをデータ化した補正処理困難度を出力する補正処理困難度検出手段と、
前記補正処理が困難となる領域近傍に、前記補正処理困難度に基づくコストを設定するコスト設定手段と、
前記コストを用いて、前記未配線ネットの配線経路の探索を行う配線経路探索手段と、
を具備したことを特徴とする配線装置。
【請求項２】
前記コスト設定手段は、前記補正処理困難度が所定の閾値よりも高い場合に、前記補正処理が困難となる領域近傍に前記コストを設定する
ことを特徴とする請求項１に記載の配線装置。
【請求項３】
未配線ネットを選択する選択手順と、
選択された前記未配線ネット及びその周辺の所定の既配線ネットを含む領域から、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンとのずれに対する補正処理が困難となる領域を検出して、補正処理の困難さの度合いを数値化した補正処理困難度を出力する補正処理困難度検出手順と、
前記補正処理が困難となる領域近傍に、前記補正処理困難度に基づくコストを設定するコスト設定手順と、
前記コストを用いて、前記未配線ネットの配線経路の探索を行う配線経路探索手順と、
を具備したことを特徴とする配線方法。
【請求項４】
前記コスト設定手順は、前記補正処理困難度が所定の閾値よりも高い場合に、前記補正処理が困難となる領域近傍に前記コストを設定する
ことを特徴とする請求項３に記載の配線方法。
【請求項５】
前記配線経路探索手順による配線経路の探索結果に対して、前記補正処理が困難となる領域を再検出して前記補正処理困難度が所定の閾値を超えたか否かを判定する補正処理困難度再検出手順と、
前記補正処理困難度再検出手順によって前記補正処理困難度が所定の閾値を超えたことが示された場合には、前記補正処理が困難となる領域に含まれる前記既配線ネットの１つを未配線ネットに変更する変更手順とを具備し、
前記変更手順によって変更された未配線ネットに対して、前記補正処理困難度検出手順、コスト設定手順、配線経路探索手順、補正処理困難度再検出手順及び変更手順を繰返す
ことを特徴とする配線方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路レイアウト設計の配線工程に好適な配線装置及び配線方法に関する。
【背景技術】
【０００２】
集積回路の微細化に伴って、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンのずれが著しくなっている。このずれを補正するために、集積回路の設計パターンを製造マスクのパターンに変換する際に、ＯＰＣ（Optical Proximity Correction）処理を施す。ＯＰＣ処理は、設計時に意図した形状をリソグラフィ工程で再現することができるように、マスク・パターン設計時に、光近接効果によるパターンずれ等に応じて、パターンを予め変形させておくものである。これにより、希望する回路パターンを得る。
【０００３】
しかし、ＯＰＣ処理は、ＯＰＣ処理が必要な図形の近傍にある他の図形の形にも影響を及ぼすため、ＯＰＣ処理が必要な図形の近傍に他の配線などが集中している場合には、設計パターンと製造される集積回路のパターンを一致させるようなＯＰＣ処理が困難となる。その結果、設計パターンとはずれたパターンを有する集積回路が製造され、回路の性能が変動したり、配線のオープンやショートが発生してしまうという問題が発生する。
【０００４】
そこで、特許文献１においては、ＯＰＣ処理困難なパターンを削減する技術が開示されている。即ち、特許文献１の提案においては、設計したパターンからパターンずれが生じるような問題となる領域を抽出する。そして、抽出した領域をサブ領域に分割し、各サブ領域について、最適な露光強度が得られるように、設計パターンを補正する。こうして、ＯＰＣ処理困難なパターンを削減し、所望の回路パターンを得るようになっている。
【０００５】
しかしながら、特許文献１の提案においては、設計されたパターンに対して、ＯＰＣ処理困難なパターンを削減するように設計結果に対して修正が施されることから、修正の自由度が低く、ＯＰＣ処理困難なパターンを十分に削減することができないという問題がある。
【特許文献１】特開平９−１８０９８２号公報
【特許文献２】特開２００６−１２６７４５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、配線設計過程において、パターンを自動修正することにより、所望の回路パターンを得ることができる配線装置及び配線方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様に係る配線装置は、未配線ネットを選択する選択手段と、選択された前記未配線ネット及びその周辺の所定の既配線ネットを含む領域から、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンとのずれに対する補正処理が困難となる領域を検出して、補正処理の困難さの度合いをデータ化した補正処理困難度を出力する補正処理困難度検出手段と、前記補正処理が困難となる領域近傍に、前記補正処理困難度に基づくコストを設定するコスト設定手段と、前記コストを用いて、前記未配線ネットの配線経路の探索を行う配線経路探索手段と、を具備したものであり、
本発明の一態様に係る配線方法は、未配線ネットを選択する選択手順と、選択された前記未配線ネット及びその周辺の所定の既配線ネットを含む領域から、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンとのずれに対する補正処理が困難となる領域を検出して、補正処理の困難さの度合いを数値化した補正処理困難度を出力する補正処理困難度検出手順と、前記補正処理が困難となる領域近傍に、前記補正処理困難度に基づくコストを設定するコスト設定手順と、前記コストを用いて、前記未配線ネットの配線経路の探索を行う配線経路探索手順と、を具備したものである。
【発明の効果】
【０００８】
本発明によれば、配線設計過程において、パターンを自動修正することにより、所望の回路パターンを得ることができるという効果を有する。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照して本発明の実施の形態について詳細に説明する。
【００１０】
（第１の実施の形態）
図１は本発明の一実施の形態に係る配線装置を示すブロック図である。本実施の形態は、配線設計の過程で、ＯＰＣ処理等による問題を考慮したレイアウト設計を行うことにより、設計の自由度を向上させ、簡単に予定した回路パターンの形成を可能にするマスクパターンの設計を行うものである。
【００１１】
先ず、ＯＰＣ処理等の問題について説明する。近年の微細化要求により、ウエハ上に設計パターン通りのパターンを形成することが困難になってきている。設計の忠実度を向上させる手段としては、ウエハ上に設計値通りのパターンを形成するためのマスクパターンを作成する光近接効果補正（Optical Proximity Correction:ＯＰＣ）、プロセス近接効果補正（Process Proximity Correction:ＰＰＣ）、と呼ばれる技術が広く利用されている。以下、ＯＰＣ及びＰＰＣを総称して「ＯＰＣ」と呼ぶ。
【００１２】
設計の忠実度の検証は、各製造工程に起因して発生するシステマティック不良の対策としても重要である。システマティック不良対策としては、リソグラフィー工程で起こるもの、エッチング工程で起こるもの等が挙げられる。
【００１３】
設計パターンのハーフピッチが１４０ｎｍを下回ると、所定のデザインルールが守られていたとしても、設計パターンによってはＯＰＣ処理を十分に行えない領域が発生する。このため、ＯＰＣ処理による適切な補正が行われず、ウエハ形状に問題が発生し、歩留まりを低下させる問題が増加する（以下、ＯＰＣ問題という）。
【００１４】
従来、ＯＰＣ問題の修正対策としては、リソグラフィーシミュレーションをベースとしたチェック（以下、「リソグラフィールールチェック」と呼ぶ。）が用いられていた。リソグラフィールールチェックでは、ＯＰＣ後のパターンに対してリソグラフィーシミュレーションを実施する。そして、得られたパターンと設計パターンとのずれを比較し、デバイス的に問題となり得る部分を検出する。エラー内容に関しては、エラー種別（オープン、ショート、ショートニング等）、エラーレベル、問題が明らかな致命的エラー、致命的ではないがプロセスの振れに対して十分なマージンがないＯＰＣ問題(以下、「グレーゾーンエラ」と呼ぶ。））等に分類することができる。
【００１５】
設計におけるリソグラフィールールチェックは、小規模のセル設計においては、これらを任意に配置して実施する。その結果、ＯＰＣ問題が発生し得るパターンがあれば、事前にレイアウトを修正することが可能である。
【００１６】
一方、チップ及びマクロブロックレベルの設計においては、自動配置配線ツールなどが広く利用されている。このため、一方向に延びる配線パターンが支配的なレイアウトが実現できており、配線パターンのバリエーションが少ないため、ＯＰＣ問題の発生確率は高くない。
【００１７】
しかしながら、チップ及びマクロレベルの比較的大規模な半導体集積回路の設計に際し、ランダムディフェクト対策による歩留向上設計やクロストーク対策等が本格的に実施され始めると、以下の問題が生じる。
【００１８】
（ａ）配線パターンのバリエーションが増え、ＯＰＣ問題の発生確率が高くなる。
【００１９】
（ｂ）ＯＰＣ問題の発生確率が高くなることにより、リソグラフィールールチェックが必要となる。配線パターンは大規模な領域を占めるため、多大な計算機リソースと処理時間を要し、実用的な時間で検証することが困難である。
【００２０】
（ｃ）リソグラフィールールチェックにおいては、グレーゾーンエラーが多く検出される。歩留向上させるためには、グレーゾーンエラーについての対策も重要である。グレーゾーンエラーは、フェイタルエラーに比べ検出数が多く、対策方法も難しいため、エラーが多く検出されると実用的時間で全て対応することは益々困難となる
そこで、本実施の形態においては、配線設計の過程で、ＯＰＣ問題の発生確率に応じたＯＰＣ処理困難度を検出し、ＯＰＣ問題の発生確率が高いパターン（ＯＰＣ処理困難なパターン）を発生させないレイアウト設計を行うものである。ＯＰＣ処理困難度及びＯＰＣ処理困難なパターンの検出方法としては、本件出願人が先に出願した特許文献２における手法を採用する。本実施の形態においては、特許文献２の手法によって検出されるＯＰＣ処理困難なパターンをＯＰＣ問題箇所として定義する。
【００２１】
次に、特許文献２のＯＰＣ問題箇所の抽出方法及び本実施の形態において定義するＯＰＣ処理困難度について図２の例を用いて説明する。図３はＯＰＣ問題箇所の検出フローを示すフローチャートである。
【００２２】
図２は、配線済みのレイアウトの一部を示す例であり、図中の各矩形は、配線、又はピン等のレイアウト図形である。図３のステップＳ１では、レイアウト図形の頂点にマークが付加される。図４は丸印によってマークが付加された様子を示している。
【００２３】
次のステップＳ２では、付加された各マークに対してＯＰＣの影響が強く及ぶ領域が定義される。図５はマークを表す丸印を囲む矩形によってこのような領域を定義した様子を示している。次のステップＳ３では、ＯＰＣの影響が強く及ぶ領域の重なりをチェックし、重なっている領域は同じグループになるようにグループ分けする。図６はグループ分けの様子を示している。太線で囲まれた部分がそれぞれのグループである。本実施の形態においては、各グループをＯＰＣ処理困難度判定ブロックとする。
【００２４】
次のステップＳ４では、各グループ（ＯＰＣ処理困難度判定ブロック）内のマークの数がカウントされ、あらかじめ定められた基準値を越えるグループはＯＰＣ問題箇所とされる。ここで、あらかじめ定められた基準値を６とすると、図７の斜線で示すように、１つのグループがＯＰＣ問題箇所として抽出される。また、本実施の形態においては、ＯＰＣ処理困難度判定ブロック内のマークの数に基づいてＯＰＣ処理困難度を定義する。例えば、ＯＰＣ処理困難度判定ブロック内のマークの数が多いほど、ＯＰＣ処理困難度が高いものとする。
【００２５】
なお、特許文献１においては、ＯＰＣ問題箇所の抽出をより高精度にするために、頂点以外に追加マークを配置する例が記載されているが、本実施の形態においても同様の追加マークを用いてよい。
【００２６】
図１において、演算処理装置（ＣＰＵ）１内のＯＰＣ処理困難度検出モジュール２１は、上述したＯＰＣ処理困難度及びＯＰＣ問題箇所の検出が可能である。ＣＰＵ１は、入出力制御部２を介して入力装置３、表示装置４及び出力装置５が接続される。入力装置４は操作者からのデータや命令などの入力を受け付けて、その情報を入出力制御部２を介してＣＰＵ１に供給する。ＣＰＵ１は、後述するように、レイアウト設計等の種々の演算を実行する。ＣＰＵ１からのレイアウト結果の出力は、入出力制御部２を介して表示装置４及び出力装置５に与えられる。表示装置４及び出力装置５は、ＣＰＵ１の出力結果を、表示すると共に出力する。
【００２７】
プログラム記憶装置６は、半導体集積回路のレイアウトプログラム等を格納する。データ記憶装置７は、半導体集積回路のレイアウト設計に必要な所定のデータ等を格納する。ＣＰＵ１は、プログラム記憶装置６から読み出したプログラムに基づいて動作して、データ記憶装置７に対するデータの書込み及び読出しを行い、レイアウト設計を行う。
【００２８】
ＣＰＵ１は、上述したように、ＯＰＣ処理困難度及びＯＰＣ問題箇所を検出する補正処理困難度検出手段としてのＯＰＣ処理困難度検出モジュール２１を備える。ＯＰＣ処理困難度検出モジュール２１は、チップ領域上に配置しようとするセル、配線、ビア等のレイアウトに応じてＯＰＣ処理困難度及びＯＰＣ問題箇所を検出する。
【００２９】
本実施の形態においては、ＣＰＵ１は、ＯＰＣ処理困難度及びＯＰＣ問題箇所を検出しながら、ピン相互間の配線を決定する。データ記憶装置７は、ピンの配置に関する情報を記憶すると共に、ピン同士の接続に関する配線情報（ネット）を保持する。未配線ネット選択モジュール２２は、配線情報に基づいて未配線ネットを選択する。ＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール２４は、ＯＰＣ処理困難度判定ブロックの近傍の所定の領域を設定して、設定した領域の情報を探索コスト設定モジュール２３に出力する。
【００３０】
探索コスト設定モジュール２３は、ＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール２４によって設定された領域について、ＯＰＣ処理困難度に基づくコストを設定する。また、探索コスト設定モジュール２３は、ＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール２４によって設定された領域以外の領域については、予め定められた所定の規則に従った探索コストを設定する。
【００３１】
配線経路探索モジュール２５は、未配線ネットについて、探索コストを用いた経路探索を行う。例えば、配線経路探索モジュール２５は、迷路法による経路探索を行うことができる。経路探索の探索結果は、データ記憶装置７に与えられて記憶されるようになっている。
【００３２】
次に、このように構成された実施の形態の作用について図８のフローチャート及び図９乃至図１４の説明図を参照して説明する。図９乃至図１４はチップ上の所定のピンＰ１，Ｐ２の周辺のレイアウトを示している。
【００３３】
先ず、比較のために、一般的な手法によるレイアウト設計を採用した場合に、ＯＰＣ処理困難なパターンが再現されてしまう例について説明する。いま、図９に示すように、チップ上の各種ピンのうちの２つのピンＰ１，Ｐ２近傍に配線Ｍ１，Ｍ２がレイアウトされているものとする。更に、図１０に示すように、ピンＰ１，Ｐ２を接続する配線Ｖ１がレイアウトされるものとする。
【００３４】
この場合に、ＯＰＣ処理が困難なパターンを調べる。即ち、図３のステップＳ１において、レイアウト図形の頂点にマークＭＫを付加する。更に、各マークＭＫに対してＯＰＣの影響が強く及ぶ領域ＲＯを定義する（ステップＳ２）。次に、領域ＲＯの重なりをチェックし、重なっている領域は同じグループになるようにグループ分けする（ステップＳ３）。次に、各グループのうちマークの数が予め定められた基準値を越えるグループはＯＰＣ問題箇所とする（ステップＳ４）。例えば、あらかじめ定められた基準値を１０とすると、図１１の太枠で示すように、１つのグループがＯＰＣ問題箇所として抽出されてしまう。
【００３５】
そこで、本実施の形態においては、上述したように、パターンのレイアウト設計時に、ＯＰＣ問題を検討する。本実施の形態では、既配線ネット及び未配線ネットの用語は、レイアウト設計が終了済みの配線又はレイアウト設計が未終了の配線のことをいう。
【００３６】
いま、チップ上の各種ピンのうち相互に接続されるべき２つのピンＰ１，Ｐ２があるものとする。図９はこれらのピンＰ１，Ｐ２の配置及びピンＰ１，Ｐ２近傍の既配線Ｍ１，Ｍ２を示している。チップ上のピンレイアウト並びに既配線ネット及び未配線ネットについての情報は、データ記憶装置７に記憶されている。
【００３７】
未配線ネット選択モジュール２２は、図８のステップＳ１０において、データ記憶装置７から読み出した情報に基づいて、チップ上に未配線ネットがあるか否かをチェックする。未配線ネットが存在する場合には、処理をステップＳ１１に移行し、存在しない場合には処理を終了する。
【００３８】
ステップＳ１１では、未配線ネット選択モジュール２２によって未配線ネットが選択される。次に、ＯＰＣ処理困難度検出モジュール２１は、終了済みのレイアウトに対して、ＯＰＣ処理困難度を検出する。即ち、ＯＰＣ処理困難度検出モジュール２１は、ステップＳ１において、レイアウト図形の頂点にマークＭＫを付加する。次に、ＯＰＣ処理困難度検出モジュール２１は、各マークＭＫに対してＯＰＣの影響が強く及ぶ領域ＲＯを定義し（ステップＳ２）、次いで、領域ＲＯの重なりをチェックして、重なっている領域をグループ化して、ＯＰＣ困難度判定ブロックＮＰとする（ステップＳ１２）。
【００３９】
図１２はこの状態を示している。なお、１つの領域ＲＯによってもＯＰＣ処理困難度判定ブロックＮＰが構成される。
【００４０】
次に、本実施の形態においては、ＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール２４は、ＯＰＣ困難度判定ブロックＮＰの近傍に所定範囲の領域ＲＢを設定する。例えば、領域ＲＢは、ＯＰＣ困難度判定ブロックＮＰの縁辺から外側に１〜数配線ピッチ分の幅を有して設定される。
【００４１】
図１２は斜線によってこの領域ＲＢを示している。なお、図１２においては、図面の簡略化のために、１つのＯＰＣ困難度判定ブロックＮＰの周辺に設定した領域ＲＢのみを示している。上述したように、１つ以上の領域ＲＯによって構成されるＯＰＣ処理困難度判定ブロックＮＰの周辺にも領域ＲＢが設定される。
【００４２】
次に、探索コスト設定モジュール２３は、各領域ＲＢについて、当該領域ＲＢ内のマーク数に応じたコストを設定する（ステップＳ１３）。即ち、本実施の形態においては、ＯＰＣ処理困難度判定ブロック内のマーク数に基づいてＯＰＣ処理困難度を判定し、判定結果のデータに応じたコストを設定する。ＯＰＣ処理困難度が高い程コストを高くするのである。なお、探索コスト設定モジュール２３は、ＯＰＣ処理困難度に加えて、各領域ＲＢの方向に応じてコストを変化させてもよい。
【００４３】
次に、配線経路探索モジュール２５は、ステップＳ１４において、コストを用いた経路探索を行う。例えば、配線経路探索モジュール２５は、迷路法を利用した経路探索を行う。迷路法においては、経路を設定する２点間に格子状の経路を設定する。そして、格子の１グリッド毎に経路を検索する。この場合には、各グリッドにコストを課し、２点間に設定した各経路のコストの和が最小の経路を探索結果とする。なお、グリッドは、配線ピッチに設定すればよい。
【００４４】
本実施の形態においては、領域ＲＢ内のグリッドには、当該領域のマーク数に応じたコストが設定されている。従って、マーク数が多い領域ＲＢを通過する経路については、総コストが比較的高くなることが考えられる。配線経路探索モジュール２５は、総コストが最小の経路を探索結果として出力する。
【００４５】
図１３は配線経路探索モジュール２５の探察結果を示している。図１３においては、図１２の領域ＲＢを迂回する配線Ｖ２がレイアウト設計されたことを示している。
【００４６】
図１４は図１３のレイアウトについて、図２のフローを採用してＯＰＣ処理困難なパターンを検出した検出結果を示している。図１４に示すように、いずれのＯＰＣ処理困難度判定ブロックＮＰについても、マーク数は少なく最大で６個である。従って、図１１との比較から明らかなように、本実施の形態を採用することで、ＯＰＣ処理困難なパターンを発生させないパターンの生成が可能である。
【００４７】
ステップＳ１４の処理が終了すると、ステップＳ１０に処理を戻して、次の未配線ネットに対して同様の処理を繰返す。
【００４８】
このように、本実施の形態においては、配線レイアウトの設計段階で、ＯＰＣ処理困難度を求め、ＯＰＣ処理困難度が高い領域を迂回するように、新たな配線パターンを設計する。従来のように配線工程後の配線の修正では、修正の自由度が小さい。これに対し、配線工程中の配線修正では、自由度が高い修正が可能である。即ち、ＯＰＣ処理が困難なパターンが発生することを抑制したレイアウト設計が可能であり、リソグラフィルールチェックを不要にして、所望の配線を得るためのマスクパターンを容易に生成することができる。これにより、回路の性能の変動や、配線のオープンやショートの発生を大幅に削減可能である。
【００４９】
（第２の実施の形態）
図１５は本発明の第２の実施の形態を示すブロック図である。図１５において図１と同一の構成要素には同一符号を付して説明を省略する。
【００５０】
上記実施の形態においては、全てのＯＰＣ処理困難度判定ブロックの近傍に、ＯＰＣ処理困難度に応じてコストを決める領域を設定した。これに対し、本実施の形態は、ＯＰＣ処理困難度の判定基準を設けて、判定基準以上の困難度を有するＯＰＣ処理困難パターンの近傍領域のみに、コストを決める領域を設定するものである。
【００５１】
本実施の形態においては、ＯＰＣ処理困難度検出モジュール２１及びＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール２４に夫々代えて、ＯＰＣ困難パターン抽出モジュール３１及びＯＰＣ処理困難パターンの近傍領域設定モジュール３４を設けたＣＰＵ１を採用した点が第１の実施の形態と異なる。
【００５２】
ＯＰＣ処理困難パターン抽出モジュール３１は、ＯＰＣ処理困難度判定ブロックのうちＯＰＣ処理困難度が判定基準以上のものを抽出する。ＯＰＣ処理困難パターンの近傍領域設定モジュール３４は、ＯＰＣ処理困難パターン抽出モジュール３１によって抽出されたブロックの近傍領域を設定するようになっている。
【００５３】
次に、このように構成された実施の形態の作用について図１６のフローチャートを参照して説明する。図１６において図８と同一の手順には同一符号を付して説明を省略する。
【００５４】
いま、図９の例を用いて説明する。図１６のステップＳ３１においては、ＯＰＣ問題箇所の判定基準を低い値に設定する。例えば、図１１の例では、マーク数が１０以上をＯＰＣ問題箇所の判定基準としたが、同じ例において、判定基準を例えば６にするのである。ステップＳ１０，Ｓ１〜Ｓ３においては、ＯＰＣ処理困難度判定ブロックが設定される。
【００５５】
本実施の形態においては、次のステップＳ３２において、モジュール３１は、ＯＰＣ処理困難度判定ブロックのうち、マーク数が判定基準を超えるものをＯＰＣ問題箇所とする。例えば、図１２の例においては、６個のマークを有するＯＰＣ処理困難度判定ブロックＮＰ（太枠）のみがＯＰＣ問題箇所とされる。ステップＳ３１において、判定基準が低い値に設定されているので、ＯＰＣ問題箇所を確実に抽出することができる。
【００５６】
ステップＳ３３においては、モジュール３４によって、ＯＰＣ問題箇所とされたＯＰＣ処理困難度判定ブロック近傍に領域ＲＢが設定され、モジュール２３によって、その領域ＲＢにコストが設定される。そして、ステップＳ１４において、モジュール２５は、設定されたコストを用いて迷路法による経路探索を行う。こうして、この場合にも、図１３に示す配線パターンが新たに設計される。
【００５７】
このように本実施の形態においても、第１の実施の形態と同様の効果を得ることができる。
【００５８】
なお、ステップＳ３２においては、低い値の判定基準を用いてＯＰＣ問題箇所を判定しており、判定基準の設定の仕方によってはＯＰＣ問題箇所と判定された場合でも、配線の障害とならない可能性もある。そこで、ステップＳ３３においてコストを設定する場合には、ＯＰＣ処理困難度判定ブロック内のマーク数に応じた数に設定するようにしてもよい。
【００５９】
（第３の実施の形態）
図１７は本発明の第３の実施の形態に採用されるレイアウト設計の方法を示すフローチャートである。図１７において図８と同一の手順には同一符号を付して説明を省略する。
【００６０】
第１及び第２の実施の形態においては、未配線ネットについての経路探索結果は既配線ネットの影響を受け、経路探索結果によって新たなＯＰＣ問題箇所が生じる可能性がある。しかし、この場合でも、未配線ネットの選択順を変更することで、ＯＰＣ問題箇所の発生を防止することができることがある。本実施の形態はこのような未配線ネットの選択順を変更する例である。本実施の形態においてもハードウェア構成は、図１と同様のものを採用することができる。
【００６１】
図１７はステップＳ４１〜Ｓ４３の手順を付加した点が図８のフローと異なる。ステップＳ４１は、経路探索の結果により新たにＯＰＣ問題箇所が発生したか否かを判定する手順である。なお、ステップＳ４１では図３のステップＳ１〜Ｓ４と同様の処理によってＯＰＣ問題箇所が検出される。新たなＯＰＣ問題箇所が発生しない場合には、処理をステップＳ１０に戻し、発生した場合には処理をステップＳ４２に移行する
ＣＰＵ１は、ステップＳ４２において、ＯＰＣ問題箇所を構成する複数のネットのうち任意のネットを選択し、その選択したネットを未配線ネットとする。次に、ＣＰＵ１は、未配線ネットに戻したネットを選択して、処理をステップＳ１に移行するようになっている。
【００６２】
次に、このように構成された実施の形態の作用について図１８乃至図２４の説明図を参照して説明する。図１８乃至図２４はチップ上の所定のピンＰ１１，Ｐ１２の周辺のレイアウトを示している。
【００６３】
図１８は２つの既配線Ｍ１１，Ｍ１２と未配線のピンＰ１１，Ｐ１２とを示している。なお、既配線Ｍ１１，Ｍ１２の領域は、両端のピンの領域も含んだものである。図１７のステップＳ１０，Ｓ１１，Ｓ１，Ｓ２，Ｓ１２，Ｓ１３，Ｓ１４の各手順は図８と同様である。図１９は図１８のレイアウトに対してステップＳ１３までの手順が実行された状態を示している。
【００６４】
ＯＰＣ処理困難度判定ブロックＮＰは、マーク数が６であり、その近傍領域に設定されるコストは比較的小さい。また、既配線Ｍ１１，Ｍ１２相互の間隔は、比較的広いので、ステップＳ１４による経路探索によって、図２０に示す配線Ｖ１２が探索結果として得られることがある。
【００６５】
本実施の形態においては、ＣＰＵ１は、ステップＳ４１において、配線Ｖ１２によって新たにＯＰＣ問題箇所が発生しないか否かを判定する。即ち、ステップＳ４１においては、例えば図３のステップＳ１〜Ｓ４の処理が行われて、ＯＰＣ問題箇所が抽出される。図２１では抽出されたＯＰＣ問題箇所を太枠によって示している。図１９と図２１との比較から明らかなように、図２１のＯＰＣ問題箇所は、新たな配線Ｖ１２によって発生したものである。
【００６６】
新たな配線は、既配線のレイアウトの影響を受けることから、ステップＳ１１において選択される未配線ネットの順番が異なれば、ＯＰＣ問題箇所が発生しないことも考えられる。そこで、新たにＯＰＣ問題箇所が発生した場合には、ＣＰＵ１は、データ記憶装置７を制御して、ＯＰＣ問題箇所を構成する複数のネット中の任意のネットを未配線ネットに戻す。図２２は図２０中の新たな配線Ｖ１２を残し、既配線Ｍ１１を未配線ネットにした状態を示している。なお、ピンＰ２１，Ｐ２２は、配線Ｍ１１を消去したことによって未配線となったピンを示している。
【００６７】
ＣＰＵ１は、次のステップＳ４３において、未配線ネットとなったピンＰ２１，Ｐ２２相互間の配線レイアウトを決定するために、この未配線ネットを選択する。次に、ＣＰＵ１は処理をステップＳ１に戻して、ステップＳ１４までの手順を繰返す。
【００６８】
図２２は太枠によってＯＰＣ処理困難度判定ブロックＮＰを示し、太枠で囲った斜線部によって、ＯＰＣ処理困難度判定ブロックＮＰの近傍の領域ＲＢを示している。ＯＰＣ処理困難度判定ブロックＮＰ内のマーク数が比較的多いことから、この領域ＲＢには比較的高いコストが設定される。領域ＲＢ内に設定されるコストが比較的高いので、ステップＳ１４の経路探索においては、ピンＰ２１，Ｐ２２相互を結ぶ配線がこの領域ＲＢを回避するように設定される。
【００６９】
図２３は経路探索の結果により得られた配線Ｖ３１を示している。次のステップＳ４１では、配線Ｖ３１による新たなＯＰＣ問題箇所が発生していないか否かが判定される。図２４は図３のステップＳ１〜Ｓ３の処理の結果を示している。図２４に示すように、ＯＰＣ処理困難度判定ブロックＮＰ内の最大マーク数は、図２１の場合よりも少ない。即ち、配線レイアウト順を変更することで、ＯＰＣ問題箇所が発生することを防止することができる可能性があることが分かる。
【００７０】
このように本実施の形態においては、ＯＰＣ問題箇所が発生する場合には、未配線ネットの選択順を変更するようになっており、これにより、ＯＰＣ問題箇所の発生を抑制することができる。
【００７１】
なお、本実施の形態は、第１の実施の形態に適用した例について説明したが、第２の実施の形態にも同様に適用可能であることは明らかである。即ち、第２の実施の形態を示す図１６のステップＳ１４以降に図１７のステップＳ４１〜Ｓ４３を実行するようにすればよい。
【００７２】
また、本実施の形態は、図１７のステップＳ４３を省略することも可能である。この場合には、ステップＳ４２から処理をステップＳ１１に移行させて、他の未配線ネットを選択させればよい。
【図面の簡単な説明】
【００７３】
【図１】本発明の一実施の形態に係る配線装置を示すブロック図。
【図２】配線済みのレイアウトの一部を示す説明図。
【図３】ＯＰＣ問題箇所の検出フローを示すフローチャート。
【図４】丸印によってマークが付加された様子を示す説明図。
【図５】付加された各マークに対してＯＰＣの影響が強く及ぶ領域を示す説明図。
【図６】グループ分けの様子を示す説明図。
【図７】ＯＰＣ問題箇所を示す説明図。
【図８】第１の実施の形態の作用を説明するためのフローチャート。
【図９】第１の実施の形態の作用を説明するための説明図。
【図１０】第１の実施の形態の作用を説明するための説明図。
【図１１】第１の実施の形態の作用を説明するための説明図。
【図１２】第１の実施の形態の作用を説明するための説明図。
【図１３】第１の実施の形態の作用を説明するための説明図。
【図１４】第１の実施の形態の作用を説明するための説明図。
【図１５】本発明の第２の実施の形態を示すブロック図。
【図１６】第２の実施の形態の作用を説明するためのフローチャート。
【図１７】第３の実施の形態に採用されるレイアウト設計の方法を示すフローチャート。
【図１８】第３の実施の形態の作用を説明するための説明図。
【図１９】第３の実施の形態の作用を説明するための説明図。
【図２０】第３の実施の形態の作用を説明するための説明図。
【図２１】第３の実施の形態の作用を説明するための説明図。
【図２２】第３の実施の形態の作用を説明するための説明図。
【図２３】第３の実施の形態の作用を説明するための説明図。
【図２４】第３の実施の形態の作用を説明するための説明図。
【符号の説明】
【００７４】
１…ＣＰＵ、２１…ＯＰＣ処理困難度検出モジュール、２２…未配線ネット選択モジュール、２３…探索コスト設定モジュール、２４…ＯＰＣ処理困難度判定ブロックの近傍領域設定モジュール、２５…配線経路探索モジュール。
【図１】
2008166606.tif 000003
【図２】
2008166606.tif 000004
【図３】
2008166606.tif 000005
【図４】
2008166606.tif 000006
【図５】
2008166606.tif 000007
【図６】
2008166606.tif 000008
【図７】
2008166606.tif 000009
【図８】
2008166606.tif 000010
【図９】
2008166606.tif 000011
【図１０】
2008166606.tif 000012
【図１１】
2008166606.tif 000013
【図１２】
2008166606.tif 000014
【図１３】
2008166606.tif 000015
【図１４】
2008166606.tif 000016
【図１５】
2008166606.tif 000017
【図１６】
2008166606.tif 000018
【図１７】
2008166606.tif 000019
【図１８】
2008166606.tif 000020
【図１９】
2008166606.tif 000021
【図２０】
2008166606.tif 000022
【図２１】
2008166606.tif 000023
【図２２】
2008166606.tif 000024
【図２３】
2008166606.tif 000025
【図２４】
2008166606.tif 000026