(57)【要約】 【課題】      ＯＰＣ処理を施すことが困難な領域の発生を予め抑制することができ、集積回路の歩留まりを向上可能な自動設計方法、自動設計装置及び半導体集積回路の製造方法を提供する。【解決手段】  格子リストファイル２５の中から累積コストが最小となる矩形領域を基点格子として抽出する累積コスト抽出モジュール１２１と、基点格子を基点として、始点格子Ｓから終点格子Ｔへの配線経路の探索を矩形領域１つ進める毎に基点格子の累積コストに探索コストを累積する探索コスト累積モジュール１２２と、探索先の矩形領域がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を格子リストファイル２５に格納するＯＰＣ困難性コスト加算モジュール１２４と、配線経路を探索する配線経路探索モジュール１１０と、始点格子Ｓと終点格子Ｔとを結線する結線モジュール１３０とを備える。【選択図】            図１
2007287052.tif 000002
【特許請求の範囲】
【請求項１】
配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として、前記始点格子及び前記終点格子を格子リストファイルに格納するステップと、
累積コスト抽出モジュールが、前記格子リストファイルの中から累積コストが最小となる矩形領域を基点格子として抽出するステップと、
探索コスト累積モジュールが、前記基点格子を基点として、前記始点格子から前記終点格子への配線経路の探索を矩形領域１つ進める毎に、前記基点格子の累積コストに探索コストを累積し、累積結果を探索先の矩形領域の累積コストとして前記格子リストファイルに格納するステップと、
ＯＰＣ困難性コスト加算モジュールが、前記探索先の矩形領域がＯＰＣ困難領域である場合に、前記探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を探索先の矩形領域に付された累積コストとして前記格子リストファイルに格納するステップと、
配線経路探索モジュールが、各矩形領域に付された累積コストを前記格子リストファイルから読み出して、前記各矩形領域に付された累積コストが最小となる配線経路を、複数の矩形領域に分割された配線領域において探索するステップと、
結線モジュールが、前記始点格子と前記終点格子とを前記配線経路により結線するステップ
とを含むことを特徴とする自動設計方法。
【請求項２】
前記ＯＰＣ困難領域が、前記配線領域内に予め敷設された第１の既配線の始終点、前記第１の既配線の長辺、前記第１の既配線の折れ曲がり部、及び前記配線領域とは異なる層に敷設された第２の既配線の長辺の少なくともいずれかから一定距離以内に設定されることを特徴とする請求項１に記載の自動設計方法。
【請求項３】
前記一定距離が、前記配線領域内に敷設される複数の配線間の最小線幅に等しいことを特徴とする請求項２に記載の自動設計方法。
【請求項４】
配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として、前記始点格子及び前記終点格子を格納する格子リストファイルと、
前記格子リストファイルの中から累積コストが最小となる矩形領域を基点格子として抽出する累積コスト抽出モジュールと、
前記基点格子を基点として、前記始点格子から前記終点格子への配線経路の探索を矩形領域１つ進める毎に、前記基点格子の累積コストに探索コストを累積し、累積結果を探索先の矩形領域の累積コストとして前記格子リストファイルに格納する探索コスト累積モジュールと、
前記探索先の矩形領域がＯＰＣ困難領域である場合に、前記探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を前記探索先の矩形領域に付された累積コストとして前記格子リストファイルに格納するＯＰＣ困難性コスト加算モジュールと、
各矩形領域に付された累積コストを前記格子リストファイルから読み出して、前記各矩形領域に付された累積コストが最小となる配線経路を、複数の矩形領域に分割された配線領域において探索する配線経路探索モジュールと、
前記始点格子と前記終点格子とを前記配線経路により結線する結線モジュール
とを備えることを特徴とする自動設計装置。
【請求項５】
自動設計装置に、累積コストが最小となる矩形領域を基点格子として抽出させ、前記基点格子を基点、配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として前記始点格子から前記終点格子への配線経路の探索を矩形領域１つ進める毎に前記基点格子の累積コストに探索コストを累積させ、探索先の矩形領域がＯＰＣ困難領域である場合に、前記探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算して前記探索先の矩形領域の累積コストを決定させ、複数の矩形領域に分割された配線領域内において、各矩形領域に付された累積コストが最小となる配線経路を探索させ、前記配線経路により前記始点格子と前記終点格子とを結線させてマスクデータを作成するステップと、
前記自動設計装置に、前記マスクデータに含まれる複数の配線に対してＯＰＣ処理を実施させ、前記マスクデータを補正させるステップと、
マスク製造装置に、補正されたマスクデータを用いてマスクを製造させるステップと、
リソグラフィー装置に、前記マスクのパターンを半導体ウエハに転写させるステップ
とを含むことを特徴とする半導体集積回路の製造方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は半導体集積回路のレイアウト設計に係り、特に配線工程に好適な自動設計方法、自動設計装置及び半導体集積回路の製造方法に関する。
【背景技術】
【０００２】
半導体集積回路のレイアウト設計においては、２点間の配線経路を求める方法として迷路法が知られている。迷路法は、配線する平面にグリッド（格子）を設定し、グリッドにより分割された２つの矩形領域間を結ぶ経路を探索する方法である。迷路法は、配線する平面に他の配線等の障害物が存在しても、その障害物をよけて配線経路を見つけることができるため、概略配線設計後の詳細配線設計等に広く利用されている（例えば、特許文献１参照。）。
【０００３】
半導体集積回路の微細化が進むと、集積回路製造マスクの図形パターンと実際に製造される集積回路の図形パターンのずれが大きくなり、このずれを補正するために、光近接効果補正（ＯＰＣ）が施される。
【０００４】
ＯＰＣ処理は、処理が必要な図形の近傍にある他の図形の形状にも影響を及ぼすため、処理が必要な図形の近傍に他の図形が集中している場合には、ＯＰＣ処理を施すことが困難になる。一方で、ＯＰＣ処理が適切に行われないと、設計パターンと異なるパターンの集積回路が製造されるため、回路の性能変動、又は配線のオープン、ショート等が発生する。
【０００５】
しかし、従来の迷路法を用いた配線経路探索方法では、ＯＰＣ処理を考慮した配線経路の最適化がなされていない。このため、探索された配線経路に対し、ＯＰＣ処理を施すことが困難な領域が発生する。ＯＰＣ処理を施すことが困難な領域が発生すると、設計パターンと大きくずれたパターンの集積回路が製造される場合があるため、回路の性能変動や配線のオープン又はショート等の発生を抑制できず、集積回路の歩留まりが低下する。
【特許文献１】特開平９−２９３０８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、自動配線工程において、ＯＰＣ処理を施すことが困難な領域の発生を予め抑制することができ、集積回路の歩留まりを向上可能な自動設計方法、自動設計装置及び半導体集積回路の製造方法を提供する。
【課題を解決するための手段】
【０００７】
本願発明の態様によれば、配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として、始点格子及び終点格子を格子リストファイルに格納するステップと；累積コスト抽出モジュールが、格子リストファイルの中から累積コストが最小となる矩形領域を基点格子として抽出するステップと；探索コスト累積モジュールが、基点格子を基点として、始点格子から終点格子への配線経路の探索を矩形領域１つ進める毎に、基点格子の累積コストに探索コストを累積し、累積結果を探索先の矩形領域の累積コストとして格子リストファイルに格納するステップと；ＯＰＣ困難性コスト加算モジュールが、探索先の矩形領域がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を探索先の矩形領域に付された累積コストとして格子リストファイルに格納するステップと；配線経路探索モジュールが、各矩形領域に付された累積コストを格子リストファイルから読み出して、各矩形領域に付された累積コストが最小となる配線経路を、複数の矩形領域に分割された配線領域において探索するステップと；結線モジュールが、始点格子と終点格子とを配線経路により結線するステップとを含む自動設計方法が提供される。
【０００８】
本願発明の他の態様によれば、配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として、始点格子及び終点格子を格納する格子リストファイルと；格子リストファイルの中から累積コストが最小となる矩形領域を基点格子として抽出する累積コスト抽出モジュールと；基点格子を基点として、始点格子から終点格子への配線経路の探索を矩形領域１つ進める毎に、基点格子の累積コストに探索コストを累積し、累積結果を探索先の矩形領域の累積コストとして格子リストファイルに格納する探索コスト累積モジュールと；探索先の矩形領域がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を探索先の矩形領域に付された累積コストとして格子リストファイルに格納するＯＰＣ困難性コスト加算モジュールと；各矩形領域に付された累積コストを格子リストファイルから読み出して、各矩形領域に付された累積コストが最小となる配線経路を、複数の矩形領域に分割された配線領域において探索する配線経路探索モジュールと；始点格子と終点格子とを配線経路により結線する結線モジュールとを備える自動設計装置が提供される。
【０００９】
本願発明の他の態様によれば、自動設計装置に、累積コストが最小となる矩形領域を基点格子として抽出させ、基点格子を基点、配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として始点格子から終点格子への配線経路の探索を矩形領域１つ進める毎に基点格子の累積コストに探索コストを累積させ、探索先の矩形領域がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算して探索先の矩形領域の累積コストを決定させ、複数の矩形領域に分割された配線領域内において、各矩形領域に付された累積コストが最小となる配線経路を探索させ、配線経路により始点格子と終点格子とを結線させてマスクデータを作成するステップと；自動設計装置に、マスクデータに含まれる複数の配線に対してＯＰＣ処理を実施させ、マスクデータを補正させるステップと；マスク製造装置に、補正されたマスクデータを用いてマスクを製造させるステップと；リソグラフィー装置に、マスクのパターンを半導体ウエハに転写させるステップとを含む半導体集積回路の製造方法が提供される。
【発明の効果】
【００１０】
本発明によれば、自動配線工程において、ＯＰＣ処理を施すことが困難な領域の発生を予め抑制することができ、集積回路の歩留まりを向上可能な自動設計方法、自動設計装置及び半導体集積回路の製造方法が提供できる。
【発明を実施するための最良の形態】
【００１１】
次に、図面を参照して、本発明の第１乃至第４の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。また、以下に示す第１乃至第４の実施の形態は、この発明の技術的思想を具体化するための装置や方法を例示するものであって、この発明の技術的思想は構成部品の材質、形状、構造、配置等を下記のものに特定するものではない。この発明の技術的思想は、特許請求の範囲において種々の変更を加えることができる。
【００１２】
（第１の実施の形態）
本発明の第１の実施の形態に係る自動設計装置は、図１に示すように、配線の始点となる矩形領域を始点格子Ｓ、終点となる矩形領域を終点格子Ｔとして、始点格子Ｓ及び終点格子Ｔを格納する格子リストファイル２５と、格子リストファイル２５の中から累積コストが最小となる矩形領域を基点格子（格子Ａ）として抽出する累積コスト抽出モジュール１２１と、基点格子（格子Ａ）を基点として、始点格子Ｓから終点格子Ｔへの配線経路の探索を矩形領域１つ進める毎に基点格子の累積コストに探索コストを累積し、累積コストを探索先の矩形領域（格子Ｂ）の累積コストとして格子リストファイル２５に格納する探索コスト累積モジュール１２２と、探索先の矩形領域(格子Ｂ）がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算し、加算結果を探索先の矩形領域に付された累積コストとして格子リストファイル２５に格納するＯＰＣ困難性コスト加算モジュール１２４と、配線経路を探索する配線経路探索モジュール１１０と、始点格子Ｓと終点格子Ｔとを結線する結線モジュール１３０とを備える。
【００１３】
探索モジュール１１０、累積コスト抽出モジュール１２１、探索コスト累積モジュール１２２、ＯＰＣ困難性コスト加算モジュール１２４、及び結線モジュール１３０は、図１に示すように、コンピュータシステムの演算処理装置（ＣＰＵ）１の一部として構成できる。
【００１４】
ＣＰＵ１には、操作者からの入力等を受け付ける入力装置４、ＣＰＵ１の処理結果等を表示する表示装置５及び出力装置６及びＣＰＵ１の演算処理に必要な各種プログラム等を記憶するプログラム記憶装置２ｍ、及びデータ記憶装置２ａが接続されている。入力装置４、表示装置５及び出力装置６は、入出力制御部３に接続されている。
【００１５】
ＣＰＵ１は、自動設計処理に必要な条件等を設定する設定モジュール１００を更に備える。探索コスト累積モジュール１２２及びＯＰＣ困難性コスト加算モジュール１２４は、配線経路のコストを計算するためのコスト計算モジュール１２０の中に含まれている。コスト計算モジュール１２０は、累積コスト抽出モジュール１２１及び始終点判定モジュール１２３を更に含む。
【００１６】
設定モジュール１００は、自動設計装置のメモリ空間内のチップ領域内に仮想的に配置された配線領域に対して、配線格子を設定する。配線領域は、例えば、図２に示すように、格子によりＡ〜Ｆ行、１〜６列の矩形領域で区画されている。矩形領域の一辺の長さは、例えば、配線領域に敷設する複数の配線間の最小線幅に等しくなるように設定することができる。以下に示す実施の形態では、各矩形領域の位置を、例えば（Ａ−１）のように（行−列）で表す。
【００１７】
図２に示す例では、（Ａ−４）に、配線の始点となるピン（始点格子Ｓ）３１が配置されている。（Ｆ−４）には、配線の終点となるピン（終点格子Ｔ）３２が配置されている。（Ｃ−１），（Ｃ−２），（Ｃ−３）には、予め敷設された他の配線１１（以下、「既配線」という。）が延伸している。
【００１８】
コスト計算モジュール１２０は、配線経路探索モジュール１１０が、配線経路の探索を矩形領域１つ分進める毎に、探索先の矩形領域のコストを計算する。コスト情報としては、例えば、以下に示す情報が設定される。
【００１９】
（１）配線経路の探索を矩形領域１つ進める毎に加算する探索コスト：１
（２）探索先の矩形領域がＯＰＣ困難領域である場合に加算するＯＰＣ困難コスト：１０
なお、本発明において「ＯＰＣ困難領域」とは、ＯＰＣ処理により配線を変形させることができない程度に他の配線と隣接する領域を指す。ＯＰＣ困難領域の位置設定は、自動配線工程後に実行されるＯＰＣ処理情報を考慮して決定される。例えば、図２に示すレイアウトでは、既配線１１の始終点が存在する矩形領域（Ｃ−３）から、既配線１１の長手方向に隣接する矩形領域（ｃ−４）に配線が存在すると、既配線１１のＯＰＣ処理が困難となり、製造後の配線のショート等の問題が発生する、というＯＰＣ処理情報が存在すると仮定する。第１の実施の形態では、このＯＰＣ処理情報に基づき、既配線１１の始終点に隣接する矩形領域（Ｃ−４）を「ＯＰＣ困難領域」と設定する場合を説明する。
【００２０】
累積コスト抽出モジュール１２１は、格子リストファイル２５の中から累積コストが最小となる矩形領域を基点格子として抽出する。例えば、図２では、格子リストファイル２５の中にはピン３１及びピン３２の情報のみしか入力されていないため、累積コスト抽出モジュール１２１が、まず、始点格子Ｓである（Ａ−４）を、基点格子として選択する。
【００２１】
探索コスト累積モジュール１２２は、予め設定されたコスト情報に基づいて、基点格子の累積コストに探索コストを累積し、探索先の矩形領域の累積コストを計算する。例えば、（Ａ−４）から矩形領域１つ進んだ（Ｂ−４）の探索コストは「１」である。このため、（Ｂ−４）の累積コストは、図３に示すように、（Ａ−４）の累積コスト「０」に探索コスト「１」を加えた「１」となる。
【００２２】
始終点判定モジュール１２３は、探索先の矩形領域が、既配線の始終点近傍に存在する矩形領域であるか否かを判定する。例えば、始終点判定モジュール１２３が、（Ｃ−４）を、既配線１１の始終点近傍に存在する矩形領域であると判定する。
【００２３】
ＯＰＣ困難性コスト加算モジュール１２４は、始終点判定モジュール１２３の判定結果に基づき、探索先の矩形領域がＯＰＣ困難領域の場合に、探索コスト累積モジュール１２２が加算した探索先の矩形領域の累積コストにＯＰＣ困難コストを加算する。例えば、図４に示すように、（Ｂ−４）から（Ｃ−４）の経路を探索する場合において、ＯＰＣ困難性コスト加算モジュール１２４が、（Ｂ−４）から（Ｃ−４）への矩形領域１つ分の探索コスト「１」と、ＯＰＣ困難領域である場合に加算するコスト「１０」と、（Ｂ−４）の累積コスト「１」とを加算した「１＋１＋１０＝１２」の値を、（Ｃ−４）に付された累積コストとして決定する。
【００２４】
配線経路探索モジュール１１０は、基点格子から探索格子への配線経路を探索する。結線モジュール１３０は、配線領域内の各矩形領域に付された累積コスト（図５参照）が最小となる経路を辿るように、図６に示すように、ピン３１とピン３２の間を配線３３ａで結線する。
【００２５】
図１のデータ記憶装置２ａは、設定データファイル２１、配線経路探索データファイル２２、コスト計算データファイル２３、結線データファイル２４、及び格子リストファイル２５を含む。設定データファイル２１は、設定モジュール１００が設定する設定データや、入力装置４を介して入力されるＯＰＣ処理情報等の各種条件を記憶する。配線経路探索データファイル２２は、配線探索に必要な情報や配線経路探索モジュール１１０の配線探索結果等を記憶する。コスト計算データファイル２３は、コスト計算に必要な情報やコスト計算モジュール１２０の計算結果等を記憶する。結線データファイル２４は、結線モジュール１３０による結線の結果を記憶する。格子リストファイル２５は、配線領域内の複数の矩形領域に付された累積コストを記憶する。  
図１において入力装置４は、キーボード、マウス、ライトペン又はフレキシブルディスク装置等を含む。操作者は、入力装置４より入出力データを指定したり自動設計に必要な数値等の設定が可能である。入力装置４により、出力データの形態等のレイアウトパラメータの設定、或いは演算の実行及び中止等の指示も入力可能である。表示装置５及び出力装置６は、それぞれディスプレイ及びプリンタ装置等を含む。表示装置５は、入出力データやレイアウト結果等を表示する。プログラム記憶装置２ｍは、入出力データやレイアウトパラメータ及びその履歴や、演算途中のデータ等を記憶する。
【００２６】
第１の実施の形態に係る自動設計方法について、図７に示すフローチャート及び図２〜図６を用いて詳細に説明する。
【００２７】
必要に応じて、データ記憶装置２ａに各種情報が設定された後、図７のステップＳ１０１において、設定モジュール１００が、格子リストファイル２５の中のデータを空にする。
【００２８】
ステップＳ１０２において、設定モジュール１００が、設定データファイル２１に格納された設定条件を読み出して、自動設計装置のメモリ空間内に仮想的に配置されたチップ領域内の配線領域に配線格子を設定し、配線格子で区画されたすべての矩形領域の累積コストを「０」にする。
【００２９】
ステップＳ１０３において、設計者により入力装置４を介して始点格子Ｓ及び終点格子Ｔの位置情報が入力されると、設定モジュール１００が、図２に示すように、指定された位置にある矩形領域内にピン３１，３２を設定する。ピン３１，３２の位置情報（Ａ−４），（Ｆ−４）は、格子リストファイル２５に格納される。
【００３０】
ステップＳ１０４において、配線経路探索モジュール１１０が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）を決定する。図２では、格子リストファイル２５の中には、（Ａ−４）と（Ｆ−４）しか格納されていないので、始点格子Ｓである（Ａ−４）が格子Ａとして選択される。選択された（Ａ−４）は、格子リストファイル２５から削除される。
【００３１】
ステップＳ１０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ａ−４）は、終点格子Ｔである（Ｆ−４）とは一致しないため、ステップＳ１０６に進む。
【００３２】
ステップＳ１０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。図２において、（Ａ−４）から探索可能な方向は、（Ａ−３），（Ｂ−４），（Ａ−５）であるが、ここでは、格子Ｂとして（Ａ−３）が選択されるとする。
【００３３】
ステップＳ１０７において、始終点判定モジュール１２３が、格子Ｂが既配線の始終点近傍であるか否かを判定する。（Ａ−３）は、配線の始終点近傍ではないので、ステップＳ１０８に進む。
【００３４】
ステップＳ１０８において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ｂの探索コストをＣとする。（Ａ−４）から（Ａ−３）に矩形領域１つ分進む場合のコストは「１」であるので、Ｃは「１」となり、計算結果がコスト計算データファイル２３に格納される。
【００３５】
ステップＳ１１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。未探索でない場合は、ステップＳ１１１に進み、格子Ａの累積コストにＣを加算した値と、既に格納された格子Ｂの累積コストの値とが比較される。（Ａ−３）は未探索であるので、ステップＳ１１２に進む。
【００３６】
ステップＳ１１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ａ−４）の累積コストは「０」であり、Ｃは上述の通り、「１」であるので、（Ａ−３）の累積コストは「０＋１＝１」となる。
【００３７】
ステップＳ１１３において、（Ａ−３）の累積コスト「１」の値が格子リストファイル２５に入力される。
【００３８】
ステップＳ１１４において、配線経路探索モジュール１１０が、格子Ａから未探索でかつ探索可能な方向があるか否かを判定する。ここでは、（Ａ−３）、（Ｂ−４）、（Ａ−５）うち、（Ａ−３）が探索されただけであるので、未探索な方向があると判定され、ステップＳ１０６に進む。
【００３９】
ステップＳ１０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ａ−４）から探索可能な方向にある格子Ｂとして（Ｂ−４）が選択される。
【００４０】
このようにして、ステップＳ１０６〜Ｓ１１４の各処理を繰り返すと、図３に示すように、配線経路探索モジュール１１０が、（Ａ−３）、（Ｂ−４）、（Ａ−５）を探索した段階で、未探索の方向がなくなる。その後、ステップＳ１１４において判定がＮＯとなるため、ステップＳ１０４に進む。
【００４１】
ステップＳ１０４において、累積コスト抽出モジュール１２１が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報（格子リスト）の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）とする。図３に示すように、格子リストには、（Ａ−３）、（Ａ−５）、（Ｂ−３）、及び終点格子（Ｆ−４）が入っており、終点格子を除くこれらのコストはすべて「１」である。ここでは、累積コスト抽出モジュール１２１が、格子Ａとして（Ｂ−４）を選択する場合を説明する。格子Ａとして選択された（Ｂ−４）は、格子リストから削除される。
【００４２】
ステップＳ１０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｂ−４）は、終点格子Ｔである（Ｆ−４）とは一致しないため、ステップＳ１０６に進む。
【００４３】
ステップＳ１０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。図３において、（Ｂ−４）から探索可能な方向は、（Ａ−４）、（Ｂ−３），（Ｂ−５），（Ｃ−４）であるが、ここでは、格子Ｂとして（Ｃ−４）が選択されるとする。
【００４４】
ステップＳ１０７において、始終点判定モジュール１２３が、格子Ｂが既配線１１の始終点近傍であるか否かを判定する。（Ｃ−４）は、配線の始終点近傍であるので、ステップＳ１０９に進む。
【００４５】
ステップＳ１０９において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ａから格子Ｂへの探索コストを計算する。（Ｂ−４）から（Ｃ−４）に矩形領域１つ分進む場合のコストは「１」となる。更に、ＯＰＣ困難性コスト加算モジュール１２４が、コスト計算データファイル２３に記憶されたコスト情報を読み出す。探索先の矩形領域がＯＰＣ困難領域（配線の始終点近傍）である場合に加算するコストは「１０」であるので、ＯＰＣ困難性コスト加算モジュール１２４が、（Ｃ−４）の探索コスト「１」とＯＰＣ困難性コスト「１０」とを加算した値Ｃを計算する。Ｃは、「１＋１０＝１１」となる。加算結果は、コスト計算データファイル２３に格納される。
【００４６】
ステップＳ１１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。（Ｂ−４）は未探索であるので、ステップＳ１１２に進む。
【００４７】
ステップＳ１１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｂ−４）の累積コストは「１」であり、Ｃは上述の通り、「１１」であるので、（Ｃ−４）の累積コストは「１＋１１＝１２」となる。
【００４８】
ステップＳ１１３において、（Ｃ−４）の累積コスト「１２」の値が格子リストファイル２５に入力される。
【００４９】
このようにして、格子（Ｂ−４）からの配線探索がすべて終了するまで、ステップＳ１０６〜Ｓ１１４の処理を繰り返すと、図４に示すように、配線経路探索モジュール１１０が、（Ａ−３）、（Ａ−５）、（Ｂ−３）、（Ｃ−４）、（Ｂ−５）を探索した段階で、未探索の方向がなくなる。その後、ステップＳ１１４において判定がＮＯとなるため、ステップＳ１０４に進む。
【００５０】
ステップＳ１０４〜Ｓ１１４の処理を繰り返していくと、ステップＳ１０４において、配線経路探索モジュール１１０が（Ｆ−４）を選択する。引き続き、ステップＳ１０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｆ−４）は、終点格子Ｔである（Ｆ−４）とは一致するため、ステップＳ１１５に進み、配線経路探索が終了する。配線経路探索が終了した状態のレイアウトを図５に示す。
【００５１】
その後、ステップＳ１１６において、結線モジュール１３０が、ピン３１とピン３２との間を配線３３ａで結線し、結線結果を結線データファイル２４に記憶させて、作業を終了する。
【００５２】
（比較例）
第１の実施の形態に係る自動設計方法の比較例を、図８〜図１０を用いて説明する。比較例に係る自動設計方法では、図８に示すように、配線領域が格子によりＡ〜Ｆ行、１〜６列の矩形領域で区画されている。始点格子Ｓとなるピン３１は、（Ａ−４）に配置されている。終点格子Ｔとなるピン３２は、（Ｆ−４）に配置されている。
【００５３】
配線経路の探索を矩形領域１つ進める毎に加算する探索コストを１とすると、図８に示すように、まず、ピン３１が存在する（Ａ−４）から、配線経路の探索が開始される。例えば、（Ａ−４）から（Ｂ−４）へ矩形領域１つ進む場合の探索コストは「１」であるので、（Ｂ−４）の累積コストは「０＋１＝１」となる。（Ｂ−４）から（Ｃ−４）へ矩形領域１つ進む場合の探索コストも１であるので、（Ｃ−４）の累積コストは、「１＋１＝２」となる。
【００５４】
このようにして、（Ａ−４）から（Ｆ−４）への配線探索を順に行っていくと、図９に示すように、各矩形領域に累積コストが入力される。累積コストの合計が最小となるような経路を選択する場合、（Ａ−４）、（Ｂ−４）、（Ｃ−４）、（Ｄ−４）、（Ｅ−４）、（Ｆ−４）となり、図１０に示すように、ピン３１とピン３２との間が配線３３ｂで接続される。
【００５５】
第１の実施の形態に係る自動設計方法と比較例に係る自動設計方法の配線探索手法との差異を説明するための図を図１１に示す。格子Ａを基点として格子Ｂへ探索を進める際の、格子Ｂの累積コストを計算する場合において、比較例では、単に、格子Ａの累積コストに、格子Ａから格子Ｂへ探索を進める場合に加算されるコストを加算した値を計算するのみである。
【００５６】
一方、第１の実施の形態に係る自動設計方法では、格子Ａの累積コストと格子Ａから格子Ｂへの探索を進める場合に加算されるコストに加え、更に、ＯＰＣ困難性を考慮したコストを加算している。これにより、格子Ｂの累積コストの値が比較例に比べて高くなるなるため、累積コストの最小値を辿る配線探索方法を適用した場合に、既配線１２の始終点と隣接する格子Ｂが、配線経路として選択されにくくなる。第１の実施の形態に係る自動設計方法では、ＯＰＣ処理を施すことができない領域を避けるように配線経路を決定することができるため、ＯＰＣ処理の困難な配線領域が発生することを抑制できる。その結果、配線形状の変形による回路の性能変動や、配線のオープン又はショートの発生を抑制でき、集積回路の歩留まりを向上させることができる。
【００５７】
第１の実施の形態に係る自動設計方法を用いて作成したレイアウトに基づいて製造される集積回路の例を図１２に示す。基板３０上で延伸する配線４１と配線４２は、一定間隔を空けて配置されている。このため、配線４２の配線幅が細くなることがない。一方、比較例により作成したレイアウトに基づいて製造される集積回路では、配線４３の配線幅Ｗが、配線４１の配線幅に比べて細く形成されてしまうため、断線等が発生し、歩留まりが低下する可能性がある。
【００５８】
（第２の実施の形態）
本発明の第２の実施の形態に係る自動設計装置は、図１４に示すように、累積コスト抽出モジュール１２１、探索コスト累積モジュール１２２、ＯＰＣ困難性コスト加算モジュール１２４、及び折れ曲がり判定モジュール１２５を備えるコスト計算モジュール１２０をＣＰＵ１に有する点が、図１に示す自動設計装置と異なる。
【００５９】
折れ曲がり判定モジュール１２５は、探索先の矩形領域が、既配線の折れ曲がり部分近傍の矩形領域であるか否かを判定する。「既配線の折れ曲がり部近傍」とは、既配線の折れ曲がり部の頂点、若しくは既配線の折れ曲がり部が存在する矩形領域から一定距離内にある矩形領域を指す。折れ曲がり部近傍であるか否かを判定するための距離は、ＯＰＣ処理情報に基づき設計者が自由に設定することができる。例えば、矩形領域の一辺を配線間の最小線幅とし、折れ曲がり部の存在する矩形領域の各辺に接する矩形領域を「既配線の折れ曲がり部近傍」と設定することにより、既配線の折れ曲がり部近傍領域に配線を敷設させにくくすることができる。
【００６０】
第２の実施の形態においては、図１５に示すように、既配線１３が（Ｃ−２）、（Ｃ−３）、（Ｂ−３）、（Ｂ−４）、（Ｂ−５）、（Ｄ−５）に延在し、始点格子Ｓとしてピン３４が（Ｃ−６）に配置され、終点格子Ｔとしてピン３５が（Ｄ−１）に配置されたレイアウトを想定する。後述する自動設計方法では、既配線１３の折れ曲がり部分（Ｂ−３）に隣接する（Ｂ−２）、及び折れ曲がり部分（Ｃ−３）に隣接する（Ｃ−４）を「折れ曲がり部分近傍の矩形領域」として設定した場合を説明する。他は、図１に示す自動設計装置と実質的に同様であるので、重複した説明を省略する。
【００６１】
第２の実施の形態に係る自動設計方法について、図１８に示すフローチャート及び図１５〜図１７のレイアウトを用いて詳細に説明する。
【００６２】
図１８のステップＳ２０１において、設定モジュール１００が、格子リストファイル２５の中のデータを空にする。
【００６３】
ステップＳ２０２において、設定モジュール１００が、設定データファイル２１に格納された設定条件を読み出して、配線領域に配線格子を設定し、配線格子で区画されたすべての矩形領域の累積コストを「０」にする。
【００６４】
ステップＳ２０３において、設計者により入力装置４を介して始点格子Ｓ及び終点格子Ｔの位置情報が入力されると、設定モジュール１００が、指定された位置にある矩形領域内にピン３４，３５を設定する。ピン３４，３５の位置情報（Ｃ−６）、（Ｄ−１）は、格子リストファイル２５に格納される。
【００６５】
ステップＳ２０４において、配線経路探索モジュール１１０が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）を決定する。格子リストファイル２５の中には、（Ｃ−６）と（Ｄ−１）しか格納されていないので、始点格子Ｓである（Ｃ−６）が格子Ａとして選択される。選択された（Ｃ−６）は、格子リストファイル２５から削除される。
【００６６】
ステップＳ２０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｃ−６）は、終点格子Ｔである（Ｄ−１）とは一致しないため、ステップＳ２０６に進む。
【００６７】
ステップＳ２０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｃ−６）から探索可能な方向は、（Ｂ−６）、（Ｄ−６）、（Ｃ−５）であるが、ここでは、格子Ｂとして（Ｃ−５）が選択されるとする。
【００６８】
ステップＳ２０７において、折れ曲がり判定モジュール１２５が、格子Ｂが既配線１３の折れ曲がり部分近傍であるか否かを判定する。（Ｃ−５）は、既配線１３の折れ曲がり近傍ではないので、ステップＳ２０８に進む。
【００６９】
ステップＳ２０８において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ｂの探索コストをＣとする。（Ｃ−６）から（Ｃ−５）に矩形領域１つ分進む場合のコストは「１」であるので、Ｃは「１」となり、計算結果がコスト計算データファイル２３に格納される。
【００７０】
ステップＳ２１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。未探索でない場合は、ステップＳ２１１に進み、格子Ａの累積コストにＣを加算した値と、既に格納された格子Ｂの累積コストの値とが比較される。（Ｃ−５）は未探索であるので、ステップＳ２１２に進む。
【００７１】
ステップＳ２１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｃ−６）の累積コストは「０」であり、Ｃは上述の通り、「１」であるので、（Ｃ−５）の累積コストは「０＋１＝１」となる。
【００７２】
ステップＳ２１３において、（Ｃ−５）の累積コスト「１」の値が格子リストファイル２５に入力される。
【００７３】
ステップＳ２１４において、配線経路探索モジュール１１０が、格子Ａから未探索でかつ探索可能な方向があるか否かを判定する。ここでは、（Ｂ−６）、（Ｄ−６）、（Ｃ−５）のうち、（Ｃ−５）が探索されただけであるので、未探索な方向があると判定され、ステップＳ２０６に進む。
【００７４】
ステップＳ２０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｃ−６）から探索可能な方向にある格子Ｂとして（Ｄ−６）が選択される。
【００７５】
このようにして、ステップＳ２０６〜Ｓ２１４の各処理を繰り返すと、配線経路探索モジュール１１０が、（Ｂ−６）、（Ｄ−６）、（Ｃ−５）を探索した段階で、未探索の方向がなくなる。その後、ステップＳ２１４において判定がＮＯとなるため、ステップＳ２０４に進む。
【００７６】
ステップＳ２０４において、累積コスト抽出モジュール１２１が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報（格子リスト）の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）とする。格子リストには、（Ｂ−６）、（Ｄ−６）、（Ｃ−５）、及び終点格子（Ｄ−１）が入っており、終点格子を除くこれらのコストはすべて「１」である。ここでは、累積コスト抽出モジュール１２１が、格子Ａとして（Ｃ−５）を選択する場合を説明する。格子Ａとして選択された（Ｃ−５）は、格子リストから削除される。
【００７７】
ステップＳ２０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｃ−５）は、終点格子Ｔである（Ｄ−１）とは一致しないため、ステップＳ２０６に進む。
【００７８】
ステップＳ２０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｃ−５）から探索可能な方向は、（Ｃ−４）及び（Ｃ−６）であるが、ここでは、格子Ｂとして（Ｃ−４）が選択されるとする。
【００７９】
ステップＳ２０７において、折れ曲がり判定モジュール１２５が、格子Ｂが既配線１３の折れ曲がり部分近傍であるか否かを判定する。（Ｃ−４）は、配線の折れ曲がり部分近傍であるので、ステップＳ２０９に進む。
【００８０】
ステップＳ２０９において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ａから格子Ｂへの探索コストを計算する。（Ｃ−５）から（Ｃ−４）に矩形領域１つ分進む場合のコストは「１」となる。更に、ＯＰＣ困難性コスト加算モジュール１２４が、コスト計算データファイル２３に記憶されたコスト情報を読み出す。探索先の矩形領域がＯＰＣ困難領域（配線の折れ曲がり近傍）である場合に加算するコストを「１０」とすると、ＯＰＣ困難性コスト加算モジュール１２４が、（Ｃ−４）の探索コスト「１」とＯＰＣ困難性コスト「１０」とを加算した値Ｃを計算する。Ｃは、「１＋１０＝１１」となる。加算結果は、コスト計算データファイル２３に格納される。
【００８１】
ステップＳ２１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。（Ｃ−４）は未探索であるので、ステップＳ２１２に進む。
【００８２】
ステップＳ２１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｃ−５）の累積コストは「１」であり、Ｃは上述の通り、「１１」であるので、（Ｃ−４）の累積コストは「１＋１１＝１２」となる。
【００８３】
ステップＳ２１３において、（Ｃ−４）の累積コスト「１２」の値が格子リストファイル２５に入力される。
【００８４】
このようにして、格子（Ｃ−５）を基点とする配線探索がすべて終了するまで、ステップＳ２０６〜Ｓ２１４の処理を繰り返すと、図１５に示すように、格子リストに（Ｄ−６）、（Ｂ−６）、（Ｃ−４）、（Ｆ−４）が格納された段階で、未探索の方向がなくなる。その後、ステップＳ２１４において判定がＮＯとなるため、ステップＳ２０４に進む。
【００８５】
ステップＳ２０４〜Ｓ２１４の処理を繰り返していくと、ステップＳ２０４において、配線経路探索モジュール１１０が（Ｄ−１）を選択する。ステップＳ２０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｄ−１）は、終点格子Ｔであるため、ステップＳ２１５に進み、配線経路探索が終了する。配線経路探索が終了した状態のレイアウトを図１６に示す。
【００８６】
その後、ステップＳ２１６において、結線モジュール１３０が、ピン３４とピン３５との間を配線３６ａで結線し、結線結果を結線データファイル２４に記憶させて、作業を終了する。
【００８７】
（比較例）
第２の実施の形態に係る自動設計方法の比較例を、図１９〜図２２を用いて説明する。比較例に係る自動設計方法では、始点格子Ｓとなるピン３４は、（Ｃ−６）に配置されている。終点格子Ｔとなるピン３５は、（Ｄ−１）に配置されている。
【００８８】
配線経路の探索を矩形領域１つ進める毎に加算する探索コストを「１」とすると、図１９に示すように、まず、ピン３４が存在する（Ｃ−６）から、配線経路の探索が開始される。例えば、（Ｃ−６）から（Ｃ−５）へ矩形領域１つ進む場合の探索コストは「１」であるので、（Ｃ−５）の累積コストは「０＋１＝１」となる。（Ｃ−５）から（Ｃ−４）へ矩形領域１つ進む場合の探索コストも１であるので、（Ｃ−４）の累積コストは、「１＋１＝２」となる。図２１、図２２に示すように、（Ｃ−６）から（Ｄ−１）への配線探索を順に行っていく。累積コストの合計が最小となるような経路を選択すると、（Ｃ−６）、（Ｃ−５）、（Ｃ−４）、（Ｄ−４）、（Ｄ−３）、（Ｄ−２）、（Ｄ−１）となる。この結果、図２２に示すように、ピン３４とピン３５との間が配線３６ｂで接続される。
【００８９】
第２の実施の形態に係る自動設計方法と比較例に係る自動設計方法の配線探索手法との差異を説明するための図を図２３に示す。矩形領域Ｂの累積コストを計算する場合に、比較例においては、格子Ａの累積コストに、格子Ａから格子Ｂへ探索を進める場合に加算されるコストを加算した値を計算していた。一方、第２の実施の形態に係る自動設計方法では、ＯＰＣ困難性を考慮したコストを更に加算することにより、格子Ｂの累積コストの値を、比較例に比べて高くなるように設定する。これにより、累積コストが最小となる迷路法を用いた配線経路探索方法を用いた場合に、既配線１２の折れ曲がり部分と隣接する矩形領域（格子Ｂ）が、配線経路として選択されにくくなるため、ＯＰＣ処理を施すことができない領域の発生を抑制できる。この結果、配線形状の変形による回路の性能変動や、配線のオープン又はショートの発生を抑制でき、集積回路の歩留まりを向上させることができる。
【００９０】
第２の実施の形態に係る自動設計方法を用いて作成したレイアウトに基づいて製造される集積回路の例を図２４に示す。基板３０上で延伸する配線４４、配線４５及び配線４６は一定間隔を空けて配置されており、配線４４と配線４６との間隔ｄ１は適度な間隔を有して配置されている。一方、比較例により作成したレイアウトに基づいて製造される集積回路では、配線４４と配線４７との間隔ｄｅが図２４の例に比べて近接しており、配線４４と配線４７との間にダスト等が付着すると、配線のショート等が発生し、歩留まりを低下させる可能性がある。
【００９１】
（第３の実施の形態）
本発明の第３の実施の形態に係る自動設計装置は、図２６に示すように、累積コスト抽出モジュール１２１、探索コスト累積モジュール１２２、ＯＰＣ困難性コスト加算モジュール１２４、異層判定モジュール１２６及び隣接判定モジュール１２７を備えるコスト計算モジュール１２０をＣＰＵ１に有する点が、図１に示す自動設計装置と異なる。
【００９２】
異層判定モジュール１２６は、探索先の矩形領域が、基点格子とは異なる層に存在するか否かを判定する。隣接判定モジュール１２７は、探索先の矩形領域と既配線との距離に応じて、探索先の矩形領域が、既配線の長手方向に隣接する矩形領域であるか否かを判定する。第３の実施の形態では、図２７（ａ）及び図２７（ｂ）に示すように、格子によりＡ〜Ｆ行、１〜６列の矩形領域で区画された２層の配線層に対して配線経路の探索を実施する場合を説明する。以下では、各矩形領域の位置を、例えば（Ａ−１−１）のように、（行−列−配線層）で表す。また、図２７（ａ）〜図２９（ｂ）に示す例では、既配線１４が、（Ｄ−１−１）、（Ｄ−２−１）、（Ｆ−６−１））に延在し、始点格子Ｓとしてピン３７が（Ｆ−１−１）に配置され、終点格子Ｔとしてピン３８が（Ａ−６−１）に配置されたレイアウトを想定する。
【００９３】
また、コスト計算モジュール１２０が計算するためのコスト情報として、以下の情報が設定される場合を仮定する。
【００９４】
（１）第１配線層で垂直方向に矩形領域１つ進める毎に加算する探索コスト：１
（２）第１配線層で水平方向に矩形領域１つ進める毎に加算する探索コスト：４
（３）第２配線層で垂直方向に矩形領域１つ進める毎に加算する探索コスト：４
（４）第２配線層で水平方向に矩形領域１つ進める毎に加算する探索コスト：１
（５）異なる配線層に進む場合に加算する探索コスト：２
（６）探索先の矩形領域がＯＰＣ困難領域である場合に加算するＯＰＣ困難コスト：１０
他は、図１に示す自動設計装置と実質的に同様であるので、重複した説明を省略する。
【００９５】
第３の実施の形態に係る自動設計方法について、図３０に示すフローチャート及び図２７（ａ）〜図２９（ｂ）のレイアウトを用いて詳細に説明する。
【００９６】
ステップＳ３０１において、設定モジュール１００が、格子リストファイル２５の中のデータを空にする。
【００９７】
ステップＳ３０２において、設定モジュール１００が、設定データファイル２１に格納された設定条件を読み出して、配線領域に配線格子を設定し、図２７配線格子で区画されたすべての矩形領域の累積コストを「０」にする。
【００９８】
ステップＳ３０３において、設計者により入力装置４を介して始点格子Ｓ及び終点格子Ｔの位置情報が入力されると、設定モジュール１００が、指定された位置にある矩形領域内にピン３７，３８を設定する。ピン３７，３８の位置情報（Ｆ−１−１）、（Ａ−６−１）は、格子リストファイル２５に格納される。
【００９９】
ステップＳ３０４において、配線経路探索モジュール１１０が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）を決定する。格子リストファイル２５の中には、（Ｆ−１−１）と（Ａ−６−１）しか格納されていないので、始点格子Ｓである（Ｆ−１−１）が格子Ａとして選択される。選択された（Ｆ−１−１）は、格子リストファイル２５から削除される。
【０１００】
ステップＳ３０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｆ−１−１）は、終点格子Ｔである（Ａ−６−１）とは一致しないため、ステップＳ３０６に進む。
【０１０１】
ステップＳ３０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｆ−１−１）から探索可能な方向は、（Ｅ−１−１）、（Ｆ−２−１）、（Ｆ−１−２）であるが、ここでは、格子Ｂとして（Ｅ−１−１）が選択されるとする。
【０１０２】
ステップＳ３０７において、異層判定モジュール１２６が、格子Ｂが基点格子とは異なる層にあるか否かを判定し、隣接判定モジュール１２７が、格子Ａ又は格子Ｂが既配線と隣接するか否かを判定する。（Ｅ−１−１）は、既配線１４に隣接するが、格子Ａとは同一層であるため、ステップＳ３０８に進む。
【０１０３】
ステップＳ３０８において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ｂの探索コストをＣとする。（Ｆ−１−１）から（Ｅ−１−１）に垂直方向に矩形領域１つ進む場合のコストは「１」であるので、Ｃは「１」となり、計算結果がコスト計算データファイル２３に格納される。
【０１０４】
ステップＳ３１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。（Ｅ−１−１）は未探索であるので、ステップＳ３１２に進む。
【０１０５】
ステップＳ３１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｆ−１−１）の累積コストは「０」であり、Ｃは上述の通り、「１」であるので、（Ｅ−１−１）の累積コストは「０＋１＝１」となる。
【０１０６】
ステップＳ３１３において、（Ｅ−１−１）の累積コスト「１」の値が格子リストファイル２５に入力される。
【０１０７】
ステップＳ３１４において、配線経路探索モジュール１１０が、格子Ａから未探索でかつ探索可能な方向があるか否かを判定する。ここでは、（Ｅ−１−１）、（Ｆ−２−１）、（Ｆ−１−２）のうち、（Ｅ−１−１）が探索されただけであるので、未探索な方向があると判定され、ステップＳ３０６に進む。
【０１０８】
ステップＳ３０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｆ−１−１）から探索可能な方向にある格子Ｂとして（Ｆ−１−２）が選択される。
【０１０９】
このようにして、ステップＳ３０６〜Ｓ３１４の各処理を繰り返すと、配線経路探索モジュール１１０が、（Ｅ−１−１）、（Ｆ−２−１）、（Ｆ−１−２）を探索した段階で、未探索の方向がなくなる。その後、ステップＳ３１４において判定がＮＯとなるため、ステップＳ３０４に進む。
【０１１０】
ステップＳ３０４において、累積コスト抽出モジュール１２１が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報（格子リスト）の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）とする。格子リストには、（Ｅ−１−１）、（Ｆ−２−１）、（Ｆ−１−２）及び終点格子（Ａ−６−１）が入っており、終点格子を除くこれらのコストは１、４、２であるので、累積コスト最小の矩形領域として累積コストが１である（Ｅ−１−１）が、格子Ａとして選択される。選択された（Ｅ−１−１）は、格子リストから削除される。
【０１１１】
ステップＳ３０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｅ−１−１）は、終点格子Ｔである（Ａ−６−１）とは一致しないため、ステップＳ３０６に進む。
【０１１２】
ステップＳ３０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｅ−１−１）から探索可能な方向は、（Ｅ−２−１）、（Ｆ−１−１）、（Ｅ−１−２）であるが、ここでは、格子Ｂとして（Ｅ−１−２）が選択されるとする。
【０１１３】
ステップＳ３０７において、異層判定モジュール１２６が、格子Ｂが格子Ａとは異なる層にあるか否かを判定し、隣接判定モジュール１２７が、格子Ａ又は格子Ｂが既配線と隣接するか否かを判定する。（Ｅ−１−２）は、格子Ａとは異なる層にあり、既配線１４に隣接するため、ステップＳ３０９に進む。
【０１１４】
ステップＳ３０９において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ａから格子Ｂへの探索コストを計算する。（Ｅ−１−１）から異なる層にある（Ｅ−１−２）へ進む場合のコストは「２」となる。更に、ＯＰＣ困難性コスト加算モジュール１２４が、コスト計算データファイル２３に記憶されたコスト情報を読み出す。探索先の矩形領域がＯＰＣ困難領域である場合に加算するコストを「１０」とすると、ＯＰＣ困難性コスト加算モジュール１２４が、（Ｅ−１−２）の探索コスト「２」とＯＰＣ困難性コスト「１０」とを加算した値Ｃを計算する。Ｃは、「２＋１０＝１２」となる。加算結果は、コスト計算データファイル２３に格納される。
【０１１５】
ステップＳ３１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。（Ｅ−１−２）は未探索であるので、ステップＳ３１２に進む。
【０１１６】
ステップＳ３１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｅ−１−１）の累積コストは「１」であり、Ｃは上述の通り、「１２」であるので、（Ｅ−１−２）の累積コストは「１＋１２＝１３」となる。
【０１１７】
ステップＳ３１３において、（Ｅ−１−２）の累積コスト「１３」の値が図２７（ｂ）に示すように、格子リストファイル２５に入力される。
【０１１８】
ステップＳ３１４において、配線経路探索モジュール１１０が、格子Ａから未探索でかつ探索可能な方向があるか否かを判定する。ここでは、（Ｅ−２−１）、（Ｆ−１−１）、（Ｅ−１−２）のうち、（Ｅ−１−２）が探索されただけであるので、未探索な方向があると判定され、ステップＳ３０６に進む。
【０１１９】
このようにして、格子（Ｅ−１−１）を基点とする配線探索がすべて終了するまで、ステップＳ３０６〜Ｓ３１４の処理を繰り返すと、図２７（ａ）に示すように、格子リストに（Ｆ−２−１）、（Ｆ−１−２）、（Ｅ−２−１）、（Ｅ−１−２）及び終点格子（Ａ−６−１）が格納された段階で、未探索の方向がなくなる。その後、ステップＳ３１４において判定がＮＯとなるため、ステップＳ３０４に進む。
【０１２０】
ステップＳ３０４において、累積コスト抽出モジュール１２１が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報（格子リスト）の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）とする。格子リストには、（Ｆ−２−１）、（Ｆ−１−２）、（Ｅ−２−１）、（Ｅ−１−２）及び終点格子（Ａ−６−１）が入っており、終点格子を除くこれらのコストは、４、２、５、１３であるので、累積コスト最小の矩形領域としてコスト「２」の（Ｆ−１−２）が格子Ａとして選択される。選択された（Ｆ−１−２）は、格子リストから削除される。
【０１２１】
ステップＳ３０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｆ−１−２）は、終点格子Ｔである（Ａ−６−１）とは一致しないため、ステップＳ３０６に進む。
【０１２２】
ステップＳ３０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある格子を探索格子（格子Ｂ）とする。（Ｆ−１−２）から探索可能な方向は、（Ｅ−１−２）、（Ｆ−２−２）、（Ｆ−１−１）であるが、ここでは、格子Ｂとして（Ｅ−１−２）が選択されるとする。
【０１２３】
ステップＳ３０７において、異層判定モジュール１２６が、格子Ｂが格子Ａとは異なる層にあるか否かを判定し、隣接判定モジュール１２７が、格子Ａ又は格子Ｂが既配線と隣接するか否かを判定する。（Ｅ−１−２）は、既配線に隣接するが、格子Ａとは同一層であるので、ステップＳ３０８に進む。
【０１２４】
ステップＳ３０８において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ｂの探索コストをＣとする。（Ｆ−１−２）から（Ｅ−１−２）に垂直方向に矩形領域１つ進む場合のコストは「４」であるので、Ｃは「４」となり、計算結果がコスト計算データファイル２３に格納される。
【０１２５】
ステップＳ３１０において、配線経路探索モジュール１１０が、格子Ｂが未探索であるか否かを判定する。図２７（ｂ）に示すように、（Ｅ−１−２）は未探索ではないので、ステップＳ３１１に進む。
【０１２６】
ステップＳ３１１において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ａの累積コストとＣとを加算した値が格子Ｂに格納された値に下回るか否かを判定する。下回る場合は、ステップＳ３１２に進み、上回る場合はステップＳ３１４へ進む。今、格子Ａとしての（Ｆ−１−２）の累積コストは「２」であり、Ｃは上述の通り、「４」であるので、（Ｅ−１−１）の累積コストは「２＋４＝６」となり、格子リストファイル２５に格納された（Ｅ−１−１）の値は「１２」であるので、「」６＜１２」となり、ステップＳ３１２に進む。
【０１２７】
ステップＳ３１２において、探索コスト累積モジュール１２２が、コスト計算データファイル２３と格子リストファイル２５を読み出して、格子Ｂの累積コストを計算する。（Ｆ−１−２）の累積コストは「２」であり、Ｃは上述の通り、「４」であるので、（Ｅ−１−１）の累積コストは「２＋４＝６」となる。
【０１２８】
ステップＳ３１３において、（Ｅ−１−２）の累積コストが「１２」から「６」に上書きされ、格子リストファイル２５に格納される。
【０１２９】
ステップＳ３１４において、配線経路探索モジュール１１０が、格子Ａから未探索でかつ探索可能な方向があるか否かを判定する。
【０１３０】
このようにして、ステップＳ３０４〜Ｓ３１４の処理を繰り返していくとステップＳ３０４において、配線経路探索モジュール１１０が（Ａ−６−１）を選択する。ステップＳ３０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ａ−６−１）は、終点格子Ｔであるため、ステップＳ３１５に進み、配線経路探索が終了する。配線経路探索が終了した状態のレイアウトを図２８（ａ）及び図２８（ｂ）に示す。
【０１３１】
その後、ステップＳ３１６において、結線モジュール１３０が、ピン３７とピン３８との間を配線４８及びビア３９、４０、７１、７２で結線し、結線結果を結線データファイル２４に記憶させて、作業を終了する。
【０１３２】
（比較例）
第３の実施の形態に係る自動設計方法の比較例を、図３１（ａ）〜図３４（ｂ）を用いて説明する。比較例に係る自動設計方法では、始点格子Ｓとなるピン３７は、（Ｆ−１−１）に配置されている。終点格子Ｔとなるピン３８は、（Ａ−６−１）に配置されている。
【０１３３】
配線経路の探索を水平・垂直方向に進める毎に加算する探索コストを第３の実施の形態と同じに設定すると、図３１（ａ）及び図３１（ｂ）に示すように、まず、ピン３７が存在する（Ｆ−１−１）から、配線経路の探索が開始される。例えば、（Ｆ−１−１）から（Ｅ−１−１）へ矩形領域１つ進む場合の探索コストは「１」であるので、図３２（ａ）に示すように、（Ｅ−１−１）の累積コストは「０＋１＝１」となる。（Ｆ−１−１）から異なる層である（Ｆ−１−２）へ進む場合の探索コストは「２」であるので、（Ｆ−１−２）の累積コストは、「０＋２＝２」となる。図３３（ａ）及び図３３（ｂ）に示すように、（Ｆ−１−１）から（Ａ−６−１）への配線探索を順に行っていき、累積コストの合計が最小となるような経路を選択すると、（Ｆ−１−１）、（Ｅ−１−１）、（Ｅ−１−２）、（Ｅ−２−２）、（Ｅ−３−２）、（Ｅ−４−２）、（Ｅ−５−２）、（Ｅ−６−２）、（Ｅ−６−１）、（Ｄ−６−１）、（Ｃ−６−１）、（Ｂ−６−１）、（Ａ−６−１）となる。この結果、図３４に示すように、ピン３７とピン３８との間が配線５３、５４、５５及びビア５１，５２で接続される。
【０１３４】
第３の実施の形態に係る自動設計方法と比較例に係る自動設計方法の配線探索手法との差異を説明するための図を図３５に示す。矩形領域Ｂの累積コストを計算する場合に、比較例においては、格子Ａの累積コストに、格子Ａから格子Ｂへ探索を進める場合に加算されるコストを加算した値のみを計算していた。一方、第３の実施の形態に係る自動設計方法では、格子Ａから格子Ｂへの探索を進める場合のコストに加えて、ＯＰＣ困難性を考慮したコストを更に加算することにより、格子Ｂの累積コストの値を、比較例に比べて高くなるように設定する。これにより、累積コストが最小となる迷路法を用いた配線経路探索方法を用いた場合に、既配線１５と隣接する矩形領域（格子Ｂ）が、配線経路として選択されにくくなるため、ＯＰＣ処理を施すことができない領域の発生を抑制できる。この結果、配線形状の変形による回路の性能変動や、配線のオープン又はショートの発生を抑制でき、集積回路の歩留まりを向上できる。
【０１３５】
（第４の実施の形態）
本発明の第４の実施の形態に係る自動設計装置は、図３６に示すように、累積コスト抽出モジュール１２１、探索コスト累積モジュール１２２、始終点判定モジュール１２３、ＯＰＣ困難性コスト加算モジュール１２４、折れ曲がり判定モジュール１２５、異層判定モジュール１２６及び隣接判定モジュール１２７を備えるコスト計算モジュール１２０をＣＰＵ１に有する点が、図１に示す自動設計装置と異なる。
【０１３６】
第４の実施の形態に係る自動設計方法について、図４０に示すフローチャート及び図３７（ａ）〜図３９（ｂ）のレイアウトを用いて詳細に説明する。
【０１３７】
図４０のステップＳ４０１において、設定モジュール１００が、格子リストファイル２５の中のデータを空にする。
【０１３８】
ステップＳ４０２において、設定モジュール１００が、設定データファイル２１に格納された設定条件を読み出して、配線領域に配線格子を設定し、配線格子で区画されたすべての矩形領域の累積コストを「０」にする。
【０１３９】
ステップＳ４０３において、設計者により入力装置４を介して始点格子Ｓ及び終点格子Ｔの位置情報が入力されると、設定モジュール１００が、指定された位置にある矩形領域内にピン１９，２０を設定する。ピン１９，２０の位置情報（Ｄ−１−１）、（Ｃ−１８−１）は、格子リストファイル２５に格納される。
【０１４０】
ステップＳ４０４において、配線経路探索モジュール１１０が、格子リストファイル２５を読み出して、格子リストファイル２５に格納された矩形領域の情報の中から、累積コストが最小となる矩形領域を探索し、基点格子（格子Ａ）を決定する。格子リストファイル２５の中には、（Ｄ−１−１）と（Ｃ−１８−１）しか格納されていないので、始点格子Ｓである（Ｄ−１−１）が格子Ａとして選択される。選択された（Ｄ−１−１）は、格子リストファイル２５から削除される。
【０１４１】
ステップＳ４０５において、配線経路探索モジュール１１０が、格子Ａと終点格子Ｔとが一致するか否かを判定する。（Ｄ−１−１）は、終点格子Ｔである（Ｃ−１８−１）とは一致しないため、ステップＳ４０６に進む。
【０１４２】
ステップＳ４０６において、配線経路探索モジュール１１０が、格子Ａを基点として、格子Ａから未探索で探索可能な方向を１つ選択し、選択された方向にある矩形領域を探索格子（格子Ｂ）とする。（Ｄ−１−１）から探索可能な方向は、（Ｅ−１−１）、（Ｃ−１−１）、（Ｄ−２−１）、（Ｄ−１−２）であるが、ここでは、格子Ｂとして（Ｅ−１−１）が選択されるとする。
【０１４３】
ステップＳ４０７において、（１）始終点判定モジュール１２３が、格子Ｂが既配線６１，６２，６３，６４，６５，６６の始終点近傍であるか否かを判定し、（２）異層判定モジュール１２６が、格子Ｂが基点格子とは異なる層にあるか否かを判定すると共に隣接判定モジュール１２７が、格子Ａ又は格子Ｂが既配線と隣接するか否かを判定し、（３）折れ曲がり判定モジュール１２５が、格子Ｂが既配線６１〜６６の折れ曲がり部分近傍であるか否かを判定する。（１）〜（３）のいずれかの条件を満たす場合は、ステップＳ４０９へ進み、満たさない場合は、ステップＳ４０８へ進む。ここでは、（Ｅ−１−１）は、既配線６１〜６６の始終点近傍にはなく、基点格子とは同一層であり、既配線６１〜６６の折れ曲がり部分近傍にもないため、ステップＳ４０８に進む。
【０１４４】
ステップＳ４０８において、探索コスト累積モジュール１２２が、コスト計算データファイル２３に記憶されたコスト情報を読み出して、格子Ｂの探索コストをＣとする。（Ｄ−１−１）から（Ｅ−１−１）に垂直方向に矩形領域１つ進む場合のコストは「１」であるので、Ｃは「１」となり、計算結果がコスト計算データファイル２３に格納される。
【０１４５】
ステップＳ４０９〜Ｓ４１５における各処理は、ステップＳ３０９〜Ｓ３１６における各処理と同様であるので、記載を省略する。配線経路探索が終了した状態のレイアウトを図３８（ａ）及び図３８（ｂ）に示す。その後、ステップＳ４１６において、図３９（ａ）及び図３９（ｂ）に示すように、結線モジュール１３０が、ピン１９とピン２０との間を配線７１、７２、７３及びビア６７、６８で結線し、結線結果を結線データファイル２４に記憶させて、作業を終了する。
【０１４６】
（比較例）
第４の実施の形態に係る自動設計方法の比較例を、図４１（ａ）〜図４２（ｂ）を用いて説明する。比較例に係る自動設計方法では、始点格子Ｓとなるピンは、（Ｄ−１−１）に配置されている。終点格子Ｔとなるピンは、（Ｃ−１８−１）に配置されている。
【０１４７】
配線経路の探索を水平・垂直方向に進める毎に加算する探索コストを第４の実施の形態と同様に設定すると、図４１（ａ）及び図４１（ｂ）に示すように、まず、ピン３７が存在する（Ｄ−１−１）から、配線経路の探索が開始される。例えば、（Ｄ−１−１）から（Ｅ−１−１）へ矩形領域１つ進む場合の探索コストは「１」であるので、図４２（ａ）に示すように、（Ｅ−１−１）の累積コストは「０＋１＝１」となる。（Ｄ−１−１）から異なる層である（Ｆ−１−２）へ進む場合の探索コストは「２」であるので、（Ｆ−１−２）の累積コストは、「０＋２＝２」となる。（Ｄ−１−１）から（Ｃ−１８−１）への配線探索を順に行っていき、累積コストの合計が最小となるような経路を選択し、配線及びビアで結線すると、図４２（ａ）及び図４２（ｂ）に示すようなレイアウトが得られる。
【０１４８】
図３９（ａ）及び図３９（ｂ）に示すレイアウトと比較例に係る図４０（ａ）及び図４０（ｂ）に係るレイアウトを見れば分かるように、第４の実施の形態に係る自動設計方法によれば、配線の間隔が、比較例に比べて広く設定される。これにより、比較例に比べて、ＯＰＣ処理を施すことができない領域の発生を抑制できるため、配線形状の変形による回路の性能変動や、配線のオープン又はショートの発生を抑制でき、集積回路の歩留まりを向上できることが分かる。
【０１４９】
（半導体集積回路の製造方法）
第１〜第４の実施の形態に係る自動設計システムを用いた半導体集積回路の製造方法の一例について、図４３のフローチャートを用いて説明する。以下に述べる半導体記憶装置の製造方法は、一例であり、この変形例を含めて、これ以外の種々の製造方法により実現可能であることは勿論である。
【０１５０】
ステップＳ１００において、自動設計装置を用いて、半導体集積回路のレイアウト設計を行う。即ち、ステップＳ１００１に示す回路配置工程において、図７、図１８、図３０及び図４０のフローチャートにしたがって、基点格子を基点、配線の始点となる矩形領域を始点格子、終点となる矩形領域を終点格子として始点格子から終点格子への配線経路の探索を矩形領域１つ進める毎に基点格子の累積コストに探索コストを累積させ、探索先の矩形領域がＯＰＣ困難領域である場合に、探索先の矩形領域の累積コストにＯＰＣ困難性コストを加算して探索先の矩形領域の累積コストを決定させ、複数の矩形領域に分割された配線領域内において、各矩形領域に付された累積コストが最小となる配線経路を探索させ、配線経路により始点格子と終点格子とを結線させて、チップ領域内の複数層の配線層を配線させたマスクデータを作成する。
【０１５１】
引き続き、ステップＳ１００２において、自動設計装置を用いて、ステップＳ１００１において作成されたマスクデータの回路検証、ＬＶＳ・ＤＲＣ検証等のレイアウトチェックを行い、ステップＳ１００３において、ＯＰＣ・ＭＤＰ処理及び検証を行う。引き続き、ステップＳ１００４において、自動設計装置を用いて、リソグラフィー検証等の各種サインオフ検証を実行し、マスクデータの準備が完了する。
【０１５２】
ステップＳ２００において、ステップＳ１００で得られたマスクデータに基づいて、電子ビーム露光装置等のパターンジェネレータ（マスク製造装置）を用いて、基板工程、配線工程、等にそれぞれ必要な枚数のマスク（レチクル）のセットを互いに所定の合わせ余裕で製造する。
【０１５３】
ステップＳ３００において、ステップＳ２００で製造されたレチクルのセットを用いたチップ製造工程が行われる。チップ製造工程は、ステップＳ３０１に示す前工程、ステップＳ３０４に示す後工程からなる。まず、ステップＳ３０２に示すフロントエンド工程（基板工程）では、例えば、酸化膜堆積装置により、ステップＳ３１０のシリコン基板上にシリコン酸化膜堆積工程を行い、ステップＳ３１１で、フォトレジスト膜塗布装置によりシリコン酸化膜上へのフォトレジスト膜塗布工程を行い、ステップＳ３１２において、ステップＳ２００で形成したマスクを用いて、リソグラフィ装置を用いたフォトリソグラフィー工程により、エッチングマスクを形成し、このエッチングマスクを利用して、エッチング装置によりシリコン酸化膜を選択的にエッチングする。更に、ステップＳ３１３において、イオン注入装置によるフォトレジスト膜とシリコン酸化膜をマスクとして用いた不純物イオンの選択的注入工程、ステップＳ３１４における、アニール炉による注入されたイオンの活性化処理等の種々の工程を繰り返し、各セルのトランジスタ等を形成する。
【０１５４】
ステップＳ３０２に示すフロントエンド工程の後は、ステップＳ３０３に示すバックエンド工程（表面配線工程）において、各工程に必要なレチクルを用いてステッパで所望のパターンを描画することにより、基板表面に対して配線処理を施す。
【０１５５】
即ち、ステップＳ３１５に示すように、例えばシリコン基板上に、ＣＶＤ装置、ＰＶＤ装置等を用いて、ＣＶＤ法、ＰＶＤ法等により絶縁膜を形成し、化学機械研磨（ＣＭＰ）装置を用いて、ＣＭＰ法により表面を平坦化する。ステップＳ３１６に示すように、レジスト膜塗布装置を用いて、層間絶縁膜の上にフォトレジストを塗布し、ステップＳ２００で形成したレチクルのセット中の表面配線用のレチクル、例えば、図６に示すレイアウトに基づき製造されたレチクル（マスク）を用いて、ステップＳ３１７に示すリソグラフィ装置を用いたフォトリソグラフィー工程によるフォトレジスト膜をパターニングし、エッチングマスクを形成する。
【０１５６】
ステップＳ３１８において、図６に示すレイアウトから製造されたレチクルに基づいて形成されたエッチングマスクを使用して、ＲＩＥ装置を用いたＲＩＥ等を行う。フォトレジストを除去し、表面を洗浄化した後、ステップＳ３１９において、配線溝の内部に金属を堆積して、配線を形成する。再び、フォトリソグラフィー工程による新たなエッチングマスクを形成し、この金属膜をパターニングする等の一連の工程を、レチクルのセット中のレチクルを順に用いて繰り返して、多層配線構造を形成する。
【０１５７】
表面配線工程の完了後、ステップＳ３０４のアッセンブル工程、ステップＳ４００の検査工程を経て、ステップＳ５００において製品として出荷される。
【０１５８】
実施の形態に係る半導体集積回路の製造方法によれば、ステップＳ１００１の回路配置工程において、ステップＳ１００３で実行されるＯＰＣ処理を考慮した配線設計がなされるため、ステップＳ１００３におけるＯＰＣ処理を適切に行うことができ、この結果、ステップＳ３０３に示す配線工程で配線のショート・オープンなどの不良を防止できるため、半導体集積回路の歩留まりが向上する。
【０１５９】
（その他の実施の形態）
上記のように、本発明は第１乃至第４の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。
【０１６０】
図７、図１８、図３０及び図４０にフローを示した一連の自動設計処理は、これらと等価なアルゴリズムのプログラムにより、図１、図１４、図２６、図３６に示したコンピュータシステム（自動設計装置）を制御して実行することができる。このプログラムは、図１、図１４、図２６、図３５にそれぞれ示したプログラム記憶装置２ｍに記憶させればよい。
【０１６１】
本発明に係る自動設計プログラムは、コンピュータ読取り可能な記録媒体に保存し、この記録媒体をプログラム記憶装置２ｍに読み込ませることにより、第１の実施の形態に係る自動設計の一連の自動設計の処理を実行することもできる。「コンピュータ読取り可能な記録媒体」とは、例えばコンピュータの外部メモリ装置、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのプログラムを記録することができるような媒体などを意味する。さらに、インターネット等の情報処理ネットワークを介して、このプログラムをプログラム記憶装置２ｍに記憶させることが可能である。
【０１６２】
本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。したがって、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【０１６３】
【図１】本発明の第１の実施の形態に係る自動設計装置を示すブロック図である。
【図２】本発明の第１の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図３】本発明の第１の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図４】本発明の第１の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図５】本発明の第１の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図６】本発明の第１の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図７】本発明の第１の実施の形態に係る自動設計方法を示すフローチャートである。
【図８】本発明の第１の実施の形態の比較例を示すＣＡＤデータである。
【図９】本発明の第１の実施の形態の比較例を示すＣＡＤデータである。
【図１０】本発明の第１の実施の形態の比較例を示すＣＡＤデータである。
【図１１】本発明の第１の実施の形態に係る自動設計方法と比較例に係る自動設計方法を際を説明するための図である。
【図１２】本発明の第１の実施の形態に係る自動設計方法を用いて製造可能な半導体集積回路の例を示す平面図である。
【図１３】本発明の第１の実施の形態の比較例に係る半導体集積回路を示す平面図である。
【図１４】本発明の第２の実施の形態に係る自動設計装置を示すブロック図である。
【図１５】本発明の第２の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図１６】本発明の第２の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図１７】本発明の第２の実施の形態に係る配線探索方法を示すＣＡＤデータである。
【図１８】本発明の第２の実施の形態に係る自動設計方法を示すフローチャートである。
【図１９】本発明の第２の実施の形態の比較例を示すＣＡＤデータである。
【図２０】本発明の第２の実施の形態の比較例を示すＣＡＤデータである。
【図２１】本発明の第２の実施の形態の比較例を示すＣＡＤデータである。
【図２２】本発明の第２の実施の形態の比較例を示すＣＡＤデータである。
【図２３】本発明の第２の実施の形態に係る自動設計方法と比較例に係る自動設計方法を際を説明するための図である。
【図２４】本発明の第２の実施の形態に係る自動設計方法を用いて製造可能な半導体集積回路の例を示す平面図である。
【図２５】本発明の第２の実施の形態の比較例に係る半導体集積回路を示す平面図である。
【図２６】本発明の第３の実施の形態に係る自動設計装置を示すブロック図である。
【図２７】本発明の第３の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図２７（ａ）は、第１配線層、図２７（ｂ）は第２配線層を示す。
【図２８】本発明の第３の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図２８（ａ）は、第１配線層、図２８（ｂ）は第２配線層を示す。
【図２９】本発明の第３の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図２９（ａ）は、第１配線層、図２９（ｂ）は第２配線層を示す。
【図３０】本発明の第３の実施の形態に係る自動設計方法を示すフローチャートである。
【図３１】本発明の第３の実施の形態の比較例を示すＣＡＤデータであり、図３１（ａ）は、第１配線層、図３１（ｂ）は第２配線層を示す。
【図３２】本発明の第３の実施の形態の比較例を示すＣＡＤデータであり、図３２（ａ）は、第１配線層、図３２（ｂ）は第２配線層を示す。
【図３３】本発明の第３の実施の形態の比較例を示すＣＡＤデータであり、図３３（ａ）は、第１配線層、図３３（ｂ）は第２配線層を示す。
【図３４】本発明の第３の実施の形態の比較例を示すＣＡＤデータであり、図３４（ａ）は、第１配線層、図３４（ｂ）は第２配線層を示す。
【図３５】本発明の第３の実施の形態に係る自動設計方法と比較例に係る自動設計方法を際を説明するための図である。
【図３６】本発明の第４の実施の形態に係る自動設計装置を示すブロック図である。
【図３７】本発明の第４の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図３７（ａ）は、第１配線層、図３７（ｂ）は第２配線層を示す。
【図３８】本発明の第４の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図３８（ａ）は、第１配線層、図３８（ｂ）は第２配線層を示す。
【図３９】本発明の第４の実施の形態に係る配線探索方法を示すＣＡＤデータであり、図３９（ａ）は、第１配線層、図３９（ｂ）は第２配線層を示す。
【図４０】本発明の第４の実施の形態に係る自動設計方法を示すフローチャートである。
【図４１】本発明の第４の実施の形態の比較例を示すＣＡＤデータであり、図４１（ａ）は、第１配線層、図４１（ｂ）は第２配線層を示す。
【図４２】本発明の第４の実施の形態の比較例を示すＣＡＤデータであり、図４２（ａ）は、第１配線層、図４２（ｂ）は第２配線層を示す。
【図４３】本発明に係る半導体集積回路の製造方法の一例を示すフローチャートである。
【符号の説明】
【０１６４】
１…ＣＰＵ
２ａ…データ記憶装置
２ｍ…プログラム記憶装置
３…入出力制御部
４…入力装置
５…表示装置
６…出力装置
１１〜１４…既配線
２１…設定データファイル
２２…配線経路探索データファイル
２３…コスト計算データファイル
２４…結線データファイル
２５…格子リストファイル
１００…設定モジュール
１１０…探索モジュール
１１０…配線経路探索モジュール
１２０…コスト計算モジュール
１２１…累積コスト抽出モジュール
１２２…探索コスト累積モジュール
１２３…始終点判定モジュール
１２４…ＯＰＣ困難性コスト加算モジュール
１２５…判定モジュール
１２６…異層判定モジュール
１２７…隣接判定モジュール
１３０…結線モジュール
【図１】
2007287052.tif 000003
【図２】
2007287052.tif 000004
【図３】
2007287052.tif 000005
【図４】
2007287052.tif 000006
【図５】
2007287052.tif 000007
【図６】
2007287052.tif 000008
【図７】
2007287052.tif 000009
【図８】
2007287052.tif 000010
【図９】
2007287052.tif 000011
【図１０】
2007287052.tif 000012
【図１１】
2007287052.tif 000013
【図１２】
2007287052.tif 000014
【図１３】
2007287052.tif 000015
【図１４】
2007287052.tif 000016
【図１５】
2007287052.tif 000017
【図１６】
2007287052.tif 000018
【図１７】
2007287052.tif 000019
【図１８】
2007287052.tif 000020
【図１９】
2007287052.tif 000021
【図２０】
2007287052.tif 000022
【図２１】
2007287052.tif 000023
【図２２】
2007287052.tif 000024
【図２３】
2007287052.tif 000025
【図２４】
2007287052.tif 000026
【図２５】
2007287052.tif 000027
【図２６】
2007287052.tif 000028
【図２７】
2007287052.tif 000029
【図２８】
2007287052.tif 000030
【図２９】
2007287052.tif 000031
【図３０】
2007287052.tif 000032
【図３１】
2007287052.tif 000033
【図３２】
2007287052.tif 000034
【図３３】
2007287052.tif 000035
【図３４】
2007287052.tif 000036
【図３５】
2007287052.tif 000037
【図３６】
2007287052.tif 000038
【図３７】
2007287052.tif 000039
【図３８】
2007287052.tif 000040
【図３９】
2007287052.tif 000041
【図４０】
2007287052.tif 000042
【図４１】
2007287052.tif 000043
【図４２】
2007287052.tif 000044
【図４３】
2007287052.tif 000045