(57)【要約】 【課題】      マルチカットビアへの置換率を高くでき、歩留まりの高い半導体集積回路を製造可能な自動設計方法、自動設計プログラム及び半導体集積回路を提供する。【解決手段】    始点領域Ｓ及び終点領域Ｅを矩形領域リスト格納部２５に格納するステップと、始点領域Ｓから終点領域Ｅへの配線経路の探索を矩形領域１つ分進める毎に配線コストを加算するステップと、配線領域ｒにマルチカットビアを配置するためのビアコストを配線コストに乗算するステップと、障害物リスト格納部２４に格納された障害物情報に基づいて障害物コストを加算するステップと、配線コスト、ビアコスト及び障害物コストを集計するステップと、集計した結果に基づいて始点領域Ｓから終点領域Ｅへの配線経路を探索するステップと、始点領域Ｓと終点領域Ｅとを結線するステップと、マルチカットビアを配置するステップとを備える。【選択図】            図１
2006065403.tif 000002
【特許請求の範囲】
【請求項１】
格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納するステップと、
配線コスト加算部が、前記始点領域から前記終点領域への配線経路の探索を前記矩形領域１つ分進める毎に配線コストを加算するステップと、
ビアコスト乗算部が、前記複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを前記配線コストに乗算するステップと、
障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算するステップと、
集計部が、前記配線コスト、前記ビアコスト及び前記障害物コストの集計結果を前記矩形領域リストに格納するステップと、
経路探索部が、前記集計結果に基づいて、前記複数層の配線領域において前記配線経路を探索するステップと、
結線部が、前記始点領域と前記終点領域とを結線するステップと、
ビア配置部が、前記複数層の配線領域のいずれかに前記マルチカットビアを配置するステップ
とを備えることを特徴とする自動設計方法。
【請求項２】
チップ領域分割部が、チップ領域を複数の前記配線領域に分割するステップと、
混雑度計算部が、前記複数の配線領域中の特定の配線領域の配線の混雑度を計算し、混雑度リスト格納部に格納するステップ
とを更に有し、
前記経路探索部が、前記混雑度の計算結果に基づいて、前記特定の配線領域において前記配線経路を探索することを特徴とする請求項１に記載の自動設計方法。
【請求項３】
小領域分割部が、前記配線領域を複数の小領域に分割するステップと、
置換率計算部が、前記複数の小領域の中の特定の小領域に対するマルチカットビアへの置換率を計算し、置換率リスト格納部に格納するステップと、
再配線部が、前記置換率の計算結果と基準値とを比較し、前記計算結果が前記基準値を下回る場合に前記特定の小領域及び前記特定の小領域の周囲の他の小領域の配線を引きはがして再配線するステップ
とを更に含むことを特徴とする請求項１又は２に記載の自動設計方法。
【請求項４】
格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納する手順と、
配線コスト加算部が、前記始点領域から前記終点領域への配線経路の探索を前記矩形領域１つ分進める毎に配線コストを加算する手順と、
ビアコスト乗算部が、前記複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを前記配線コストに乗算する手順と、
障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算する手順と、
集計部が、前記配線コスト、前記ビアコスト及び前記障害物コストの集計結果を前記矩形領域リストに格納する手順と、
経路探索部が、前記集計結果に基づいて、前記複数層の配線領域において前記配線経路を探索する手順と、
結線部が、前記始点領域と前記終点領域とを結線する手順と、
ビア配置部が、前記複数層の配線領域のいずれかに前記マルチカットビアを配置する手順
とを自動設計装置に実行させるための自動設計プログラム。
【請求項５】
格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納するステップと、
配線コスト加算部が、前記始点領域から前記終点領域への配線経路の探索を前記矩形領域１つ分進める毎に配線コストを加算するステップと、
ビアコスト乗算部が、前記複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを前記配線コストに乗算するステップと、
障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算するステップと、
集計部が、前記配線コスト、前記ビアコスト及び前記障害物コストの集計結果を前記矩形領域リストに格納するステップと、
経路探索部が、前記集計結果に基づいて、前記複数層の配線領域において前記配線経路を探索するステップと、
結線部が、前記始点領域と前記終点領域とを結線するステップと、
ビア配置部が、前記複数層の配線領域のいずれかに前記マルチカットビアを配置するステップ
により製造される半導体集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は半導体集積回路のレイアウト設計に係り、特にレイアウト設計における配線工程に好適なレイアウト設計技術に関する。
【背景技術】
【０００２】
半導体集積回路のレイアウト設計においては、２点間の配線経路を求める方法として、迷路法が知られている（例えば、特許文献１参照）。迷路法は、配線する平面にグリッド（格子）を設定し、このグリッドにより分割された２点の矩形領域間を結ぶ経路を探索する配線探索方法である。この迷路法は、既配線等の障害物が存在しても障害物をよけて配線経路を見つけることができるため、概略配線設計後の詳細配線設計等に広く利用されている。
【０００３】
一方、半導体集積回路の製造においては、微細化・高集積化への要求に伴い、素子間を接続する配線形状を設計通りに形成することがますます困難になってきている。例えば、配線が微細化するにつれ、上下の配線層を接続するビアの位置まで配線が到達しない現象（ショートニング）等が発生し易くなる。このため、接続不良やビアの高抵抗化が生じ、歩留まりが低下する。
【０００４】
ビア不良による歩留まり低下を防ぐために、配線間を接続する１つのビア（シングルカットビア）を複数のビア（マルチカットビア）に置換する手法が提案されている。しかし、現在一般的に用いられている手法は、配線設計後に後処理として適用されるため、配線設計中のマルチカットビアへの置換は考慮されていない。このため、シングルカットビアからマルチカットビアへの置換を設計上行えない領域が多数発生し、マルチカットビアへの置換率を高くすることができない。
【０００５】
【特許文献１】特開平７−２４９０６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、マルチカットビアへの置換率を高くでき、歩留まりの高い半導体集積回路を製造可能な自動設計方法、自動設計プログラム及び半導体集積回路を提供する。
【課題を解決するための手段】
【０００７】
本発明の第１の特徴は、以下の各ステップを含む自動設計方法であることを要旨とする：
（ａ）格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納するステップ、
（ｂ）配線コスト加算部が、始点領域から終点領域への配線経路の探索を矩形領域１つ分進める毎に配線コストを加算するステップ、
（ｃ）ビアコスト乗算部が、複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを配線コストに乗算するステップ、
（ｄ）障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算するステップ、
（ｅ）集計部が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リストに格納するステップ、
（ｆ）経路探索部が、集計結果に基づいて、複数層の配線領域において配線経路を探索するステップ、
（ｇ）結線部が、始点領域と終点領域とを結線するステップ、
（ｈ）ビア配置部が、複数層の配線領域のいずれかにマルチカットビアを配置するステップ。
【０００８】
第２の特徴は、以下の各ステップを自動設計装置に実行させるための自動設計プログラムであることを要旨とする：
（ａ）格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納する手順、
（ｂ）配線コスト加算部が、始点領域から終点領域への配線経路の探索を矩形領域１つ分進める毎に配線コストを加算する手順、
（ｃ）ビアコスト乗算部が、複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを配線コストに乗算する手順、
（ｄ）障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算する手順、
（ｅ）集計部が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リストに格納する手順、
（ｆ）経路探索部が、集計結果に基づいて、複数層の配線領域において配線経路を探索する手順、
（ｇ）結線部が、始点領域と終点領域とを結線する手順、
（ｈ）ビア配置部が、複数層の配線領域のいずれかにマルチカットビアを配置する手順。
【０００９】
第３の特徴は、以下の各ステップにより製造された半導体装置であることを特徴とする。
【００１０】
（ａ）格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域、終点となる矩形領域を終点領域として、矩形領域リスト格納部に格納するステップ、
（ｂ）配線コスト加算部が、始点領域から終点領域への配線経路の探索を矩形領域１つ分進める毎に配線コストを加算するステップ、
（ｃ）ビアコスト乗算部が、複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを配線コストに乗算するステップ、
（ｄ）障害物コスト加算部が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算するステップ、
（ｅ）集計部が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リストに格納するステップ、
（ｆ）経路探索部が、集計結果に基づいて、複数層の配線領域において配線経路を探索するステップ、
（ｇ）結線部が、始点領域と終点領域とを結線するステップ、
（ｈ）ビア配置部が、複数層の配線領域のいずれかにマルチカットビアを配置するステップ。
【発明の効果】
【００１１】
本発明によれば、マルチカットビアへの置換率を高くでき、歩留まりの高い半導体集積回路を製造可能な自動設計方法、自動設計プログラム及び半導体集積回路が提供できる。
【発明を実施するための最良の形態】
【００１２】
次に、図面を参照して、本発明の第１乃至第３の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。また、図面は模式的なものであり、厚みと平均寸法の関係、各層の厚みの比率等は現実のものとは異なることに留意すべきである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。以下に示す第１乃至第３の実施の形態は、この発明の技術的思想を具体化するための装置や方法を例示するものであって、この発明の技術的思想は構成部品の材質、形状、構造、配置等を下記のものに特定するものではない。この発明の技術的思想は、特許請求の範囲において種々の変更を加えることができる。
【００１３】
（第１の実施の形態）
本発明の第１の実施の形態に係る自動設計装置は、図１に示すように、操作者からのデータや命令などの入力を受け付ける入力装置４と、レイアウト設計等の種々の演算を実行する演算処理部（ＣＰＵ）１ａと、レイアウト結果等を出力する表示装置５及び出力装置６と、半導体集積回路のレイアウト設計に必要な所定のデータ等を記憶したデータ記憶装置２ａと、半導体集積回路のレイアウトプログラム等を記憶したプログラム記憶装置２ｍとを備える。入力装置４、表示装置５及び出力装置６は、入出力制御装置３を介してＣＰＵ１ａに接続されている。
【００１４】
ＣＰＵ１ａは、自動設計装置のメモリ空間内に仮想的に設置された半導体集積回路のチップ領域上に、複数層の配線とその配線間を接続するビアを自動配置する。このため、図１に示すＣＰＵ１ａは、経路探索部１１０、コスト計算部１２０、結線部１３０、及びビア配置部１４０を備える。
【００１５】
経路探索部１１０は、図４（ａ）及び図４（ｂ）に示すように、格子（グリッド）により複数の矩形領域に分割された複数層の配線領域において、配線の始点となる始点領域Ｓと配線の終点となる終点領域Ｅの格子間を結線するのに最小コストとなる配線経路を、迷路法により探索する。コスト計算部１２０は、経路探索部１１０が配線経路の探索を矩形領域１つ分進める毎に、探索する矩形領域の環境に応じたコストを計算する。このため、コスト計算部１２０は、図１に示すように、配線コスト加算部１２１、ビアコスト乗算部１２２、障害物コスト加算部１２３、及び集計部１２４を備える。
【００１６】
配線コスト加算部１２１は、２点の矩形領域間の配線経路の探索を矩形領域１つ分進める毎に配線コストを加算する。ビアコスト乗算部１２２は、探索が異なる層に対して行われる場合に、異なる層のいずれかに複数のビアを配置するためのビアコストを配線コストに乗算する。障害物コスト加算部１２３は、探索が異なる層に対して行われる場合に、探索を行う矩形領域の周囲に存在する障害物の情報に基づいて、障害物コストを加算する。集計部１２４は、配線コスト加算部１２１、ビアコスト乗算部１２２、障害物コスト加算部１２３により計算されたコストを集計する
例えば、図４（ａ）及び図４（ｂ）に示すレイアウトに対し、配線コスト加算部１２１、ビアコスト乗算部１２２、障害物コスト加算部１２３がそれぞれ配線経路を計算するためのコストとして、以下に示す情報が入力される。
【００１７】
第１層配線領域で水平方向に１矩形領域進む配線コスト：１
第１層配線領域で垂直方向に１矩形領域進む配線コスト：４
第２層配線領域で水平方向に１矩形領域進む配線コスト：４
第２層配線領域で垂直方向に１矩形領域進む配線コスト：１
異なる層の配線領域に１矩形領域進む配線コスト：２
マルチカットビアを配置するためのビアコスト：２
探索する矩形領域を定義する四辺に隣接する矩形領域に存在する障害物Ｏの障害物コスト：１
ここで「水平方向」とは、図４〜図１０の紙面左右方向を指し、「垂直方向」とは、図４〜図１０の紙面上下方向を指す。図４〜図１０では、説明のために、各矩形領域の水平方向に１〜７、垂直方向にＡ〜Ｆの記号を付している。以下においては、各矩形領域の位置情報を『矩形領域Ｇ（水平方向の位置−垂直方向の位置−配線層）』の順に示す。
【００１８】
図４（ａ）に示すように、始点領域Ｓ及び終点領域Ｅの２点の位置の情報が入力された場合において、始点領域Ｇ（Ｂ−２−１）から紙面左方向に１矩形領域進んだ矩形領域Ｇ（Ｂ−１−１）への配線経路の探索は、上述する『第１層配線領域で水平方向に１矩形領域分進む配線コスト』に該当する。このため、配線コスト加算部１２１は、矩形領域Ｇ（Ｂ−１−１）に対して配線コスト「１」を加算する。また、矩形領域Ｇ（Ｂ−２−１）から矩形領域Ｇ（Ｂ−１−１）への探索は、同一配線領域上における配線探索であるので、ビアを発生させる必要がない。このため、ビアコスト乗算部１２２は、矩形領域Ｇ（Ｂ−１−１）に対するビアコストを加算しない。この結果、集計部１２４は、始点領域Ｓのコスト「０」に配線コスト「１」のみを加えた「１」を矩形領域Ｇ（Ｂ−１−１）のコストとして集計する。その結果、矩形領域Ｇ（Ｂ−１−１）の領域には、図５（ａ）に示すように、コスト「１」の情報が格納される。
【００１９】
矩形領域Ｇ（Ｂ−２−１）から紙面上方向に１矩形領域進んだ矩形領域Ｇ（Ａ−２−１）への探索は、『第１配線領域で垂直方向に１矩形領域分進む配線コスト』に該当する。このため、配線コスト加算部１２１は、矩形領域Ｇ（Ａ−２−１）に対して配線コスト「４」を加算する。矩形領域（Ｂ−２−１）から矩形領域Ｇ（Ａ−２−１）への探索は、異なる層への探索ではない。なお、矩形領域（Ｂ−２−２）の周辺には、既配線等の障害物Ｏは存在しない。このため、障害物コスト加算部１２３は、矩形領域（Ｂ−２−２）に対する障害物コストを加算しない。この結果、集計部１２４は、図５（ａ）に示すように、始点領域Ｓのコスト「０」に配線コスト「４」を加えたコスト「４」の値を集計し、矩形領域Ｇ（Ａ−２−１）の領域に「４」の情報を格納する。
【００２０】
矩形領域Ｇ（Ｂ−２−１）から上層方向に１矩形領域進んだ矩形領域Ｇ（Ｂ−２−２）への探索を行う場合は、『異なる層の配線領域に１矩形領域分進む配線コスト』に該当する。このため、配線コスト加算部１２１は、矩形領域（Ｂ−２−２）の領域に対して配線コスト「２」を加算する。矩形領域Ｇ（Ｂ−２−１）から矩形領域Ｇ（Ｂ−２−２）への探索は、異なる層への探索であるので、ビアを形成する必要がある。ビアコスト乗算部１２２は、マルチカットビアを配置するためのビアコストとしてコスト「２」の値を配線コスト「２」の値に乗算し、「４」の値を算出する。この結果、集計部１２４は、始点領域Ｓのコスト「０」にビアコスト乗算部１２２の乗算結果「４」を加えたコスト「４」の値を集計結果とし、図５（ｂ）に示すように、「４」の情報を格納する。図６（ａ）及び図６（ｂ）に示すように、始点領域Ｓの周辺の矩形領域から順次コストを計算していくと、最終的には、図７（ａ）及び図７（ｂ）に示すように、ほぼ全ての配線領域におけるコストが計算される。
【００２１】
図１の結線部１３０は、コスト計算部１２０が計算したコストに基づき、経路探索部１１０が探索した最小コストとなる配線経路（図７（ａ）、（ｂ）においては矢印で示してある。）を結線し、図８（ａ）及び図８（ｂ）に示すように、メモリ空間内に設置された配線領域上に配線Ｍを敷設する。ビア配置部１４０は、複数層の配線間を接続するための１つのビア（シングルカットビアＶ１，Ｖ２）を配置する、或いは図９（ａ）及び図９（ｂ）に示すように、複数のビア（マルチカットビアＶ３，Ｖ４）を配置する。
【００２２】
図１のデータ記憶装置２ａは、配線コスト格納部２１、ビアコスト格納部２２、障害物コスト格納部２３、障害物リスト格納部２４、及び矩形領域リスト格納部２５を備える。配線コスト格納部２１には、配線優先方向等の配線経路の探索要求に応じて入力装置４等により設定可能な配線コストの情報が格納される。ビアコスト格納部２２には、ビアの数、形状、大きさ数等に応じて、入力装置４等により設定可能なビアコストの情報が格納される。障害物コスト格納部２３には、探索する矩形領域の周囲に存在する既配線等の障害物に応じて、入力装置４等により設定可能な障害物コストの情報が格納される。障害物リスト格納部２４には、メモリ空間内の配線領域上に既に敷設された配線等の障害物リスト等が格納される。矩形領域リスト格納部２５には、配線領域上で経路探索が行う際の起点となる起点領域の情報、及びコスト計算部１２０により計算された起点領域周辺の矩形領域のコスト情報等が格納される。
【００２３】
図１において入力装置４は、キーボード、マウス、ライトペン又はフレキシブルディスク装置等を含む。操作者は、入力装置４より入出力データを指定したり自動設計に必要な数値等の設定が可能である。入力装置４により、出力データの形態等のレイアウトパラメータの設定、或いは演算の実行及び中止等の指示も入力可能である。表示装置５及び出力装置６は、それぞれディスプレイ及びプリンタ装置等を含む。表示装置５は、入出力データやレイアウト結果等を表示する。プログラム記憶装置２ｍは、入出力データやレイアウトパラメータ及びその履歴や、演算途中のデータ等を記憶する。
【００２４】
次に、第１の実施の形態に係る自動設計方法について、図２〜図３に示すフローチャート及び図４〜図１０を用いて詳細に説明する。
【００２５】
（ａ）図２のステップＳ１００において、図１に示す自動設計装置が自動設計処理を実行するために必要な各種情報が、入力装置４を介して入力される。例えば、図１に示すコスト計算部１２０が計算するための配線コスト、ビアコスト、障害物コストの情報が入力され、配線コスト格納部２１、ビアコスト格納部２２、障害物リスト格納部２４にそれぞれ格納される。
【００２６】
（ｂ）ステップＳ２００において、迷路法による配線の経路探索処理が行われる。ステップＳ２０１において、グリッドにより分割された全ての格子領域のコストが「０」に初期化される。図４（ａ）及び図４（ｂ）に示すように、ステップＳ２０３において、探索の始点となる始点領域Ｓの情報及び探索の終点となる終点領域Ｅの情報が、入力装置４等を介して図１の矩形領域リスト格納部２５に格納される。ここでは、例えば始点領域Ｓとして矩形領域Ｇ（Ｂ−２−１）、終点領域Ｅとして矩形領域Ｇ（Ｅ−６−１）の位置情報が格納される。
【００２７】
（ｃ）ステップＳ２０５において、図１の経路探索部１１０が、矩形領域リスト格納部２５に格納された情報に基づいて、コスト最小となる起点領域Ｍを選択する。図４に示す例では、矩形領域リスト格納部２５には、始点領域Ｓ及び終点領域Ｅの情報しか入っていない。このため、経路探索部１１０は、起点領域Ｍとして、始点領域Ｓ、即ち矩形領域Ｇ（Ｂ−２−１）を選択する。続いて、ステップＳ２０７において、経路探索部１１０は、起点領域Ｍが終点領域Ｅに一致するか否かを判定する。起点領域Ｍの矩形領域Ｇ（Ｂ−２−１）は終点領域Ｅの矩形領域Ｇ（Ｅ−６−１）とは異なるので、ステップＳ２０９に進む。
【００２８】
（ｄ）ステップＳ２０９において、経路探索部１１０は、起点領域Ｍから探索の方向（探索領域Ｐ）を１つ選択する。図４では、矩形領域Ｇ（Ｂ−２−１）からの探索方向としては、紙面右方向、左方向、上方向、下方向、及び上層方向が考えられるが、ここでは、探索領域Ｐとして右方向を選ぶとする。この結果、探索領域Ｐは矩形領域Ｇ（Ｂ−３−１）となる。ステップＳ２１１において、コスト計算部１２０は、探索領域Ｐが上層又は下層方向にあるか否かを判定する。探索領域Ｐが上層又は下層方向にある場合は、ステップＳ２１５へ進む。探索領域矩形領域Ｐが上層又は下層方向にない場合は、ステップＳ２１３に進む。図４に示すように、矩形領域Ｇ（Ｂ−３−１）は、起点領域Ｍである矩形領域Ｇ（Ｂ−２−１）からみて上層又は下層方向ではないので、ステップＳ２１３へ進む。
【００２９】
（ｅ）ステップＳ２１３において、配線コスト加算部１２１は、配線コスト格納部２１に格納された情報に基づいて、配線コストを加算する。図４に示すように、矩形領域Ｇ（Ｂ−３−１）は、矩形領域Ｇ（Ｂ−２−１）からみて『第１層配線領域で水平方向に１矩形領域進むコスト』である。したがって、配線コスト加算部１２１は、コスト「１」を加算し、プログラム記憶装置２ｍに格納する。
【００３０】
（ｆ）ステップＳ２１７において、コスト計算部１２０は、探索領域Ｐが未探索であるか否かを判定する。未探索な場合はステップＳ２２１に進み、未探索でない場合は、ステップＳ２１９へ進む。現時点では、矩形領域Ｇ（Ｂ−３−１）は未探索であるので、ステップＳ２１１へ進む。ステップＳ２１１において、集計部１２４は、プログラム記憶装置２ｍに格納された探索領域Ｐの配線コスト等を集計し、集計結果を起点領域Ｍのコストに加算して、矩形領域リスト格納部２５に格納する。矩形領域Ｇ（Ｂ−３−１）のコストは、配線コストの「１」と障害物コストの「０」と始点領域Ｓの「０」とを加えた「１」となる。このため、集計部１２４は、図５（ａ）に示すように、「１」の値を、矩形領域リスト格納部２５の矩形領域Ｇ（Ｂ−３−１）の領域に格納する。
【００３１】
（ｇ）ステップＳ２２３において、経路探索部１１０は、起点領域Ｍから未探索の方向があるか否か判定する。未探索の方向がある場合はステップＳ２０９へ進み、未探索の方向がない場合はステップＳ２０５へ進む。現時点では、探索領域Ｐとして矩形領域Ｇ（Ｂ−３−１）を探索したのみであるので、ステップＳ２０９に進む。ステップＳ２０９において、経路探索部１１０は、起点領域Ｍから探索の方向（探索領域Ｐ）を１つ選択する。経路探索部１１０は、矩形領域Ｇ（Ｂ−２−１）からの探索方向として、上層方向の矩形領域Ｇ（Ｂ−２−２）を選択したとする。ステップＳ２１１において、コスト計算部１２０は、探索領域Ｐが上層又は下層方向にあるか否かを判定する。矩形領域Ｇ（Ｂ−２−２）は、上層方向への探索であるので、ステップＳ２１５へ進む。
【００３２】
（ｈ）ステップＳ２１５において、配線コスト加算部１２１が、配線コスト格納部２１に格納された情報に基づいて、コストを加算する。探索領域Ｐの矩形領域Ｇ（Ｂ−２−２）は、矩形領域Ｇ（Ｂ−２−１）からみて『異なる層に１矩形領域進む配線コスト』であるので、配線コスト加算部１２１はコスト「２」を加算し、プログラム記憶装置２ｍに格納する。続いて、ビアコスト乗算部１２２は、ビアコスト格納部２２に格納された情報に基づいて、配線コスト加算部１２１が加算した値にビアコストを乗算する。ここで、ビアコスト格納部２２に格納された配線コストは「２」である。よって、ビアコスト乗算部１２２は、配線コスト加算部１２１が加算した「２」とビアコスト「２」を乗算し、コスト「４」の情報をプログラム記憶装置２ｍに格納する。さらに、障害物コスト加算部１２３は、障害物リスト格納部２４に格納された情報に基づいて、探索領域Ｐの周辺に存在する障害物コストを加算する。ここでは、探索領域Ｐの周辺に障害物は何も存在しないので、障害物コストは「０」となる。障害物コスト加算部１２３は、「０」の情報を、プログラム記憶装置２ｍに格納する。
【００３３】
（ｉ）ステップＳ２１７において、コスト計算部１２０は、探索領域Ｐが未探索であるか否かを判定する。矩形領域Ｇ（Ｂ−２−２）は未探索であるので、ステップＳ２２１へ進む。ステップＳ２２１において、集計部１２４は、コスト計算部１２０が計算した探索領域Ｐのコストのそれぞれを起点領域Ｍのコストに加算し、矩形領域リスト格納部２５に格納する。ここで、プログラム記憶装置２ｍに格納された矩形領域Ｇ（Ｂ−２−２）のコストは、始点領域Ｓの「０」、配線コストとビアコストを乗算した「４」、及び障害物コストの「０」をそれぞれ加えた「４」となる。集計部１２４は、図５（ｂ）に示すように、矩形領域リスト格納部２５の矩形領域Ｇ（Ｂ−２−２）の領域に、コスト「４」の情報を格納する。
【００３４】
（ｊ）ステップＳ２２３において、経路探索部１１０は、起点領域Ｍから未探索の方向があるか否か判定する。現時点では、探索領域Ｐとして矩形領域Ｇ（Ｂ−３−１）及び矩形領域Ｇ（Ｂ−２−２）が探索されたのみで、未探索の方向が存在するので、ステップＳ２０９に進む。このように、ステップＳ２０９〜Ｓ２２３の各工程を繰り返し、起点領域Ｍの周辺の全ての矩形領域のコストを矩形領域リスト格納部２５に格納する。
【００３５】
（ｋ）ステップＳ２２３において、探索領域Ｐが全て探索されたと判定された場合は、ステップＳ２０５に進み、経路探索部１１０が、新たな起点領域Ｍを検索する。図５（ａ）に示す例では、矩形領域Ｇ（Ａ−２−１）、矩形領域Ｇ（Ｂ−１−１）、矩形領域Ｇ（Ｂ−３−１）、矩形領域Ｇ（Ｃ−２−１）、矩形領域Ｇ（Ｂ−２−２）の５つの領域にコスト情報が格納されているが、コストが最小となる領域は、コストが「１」である矩形領域Ｇ（Ｂ−１−１）又は矩形領域Ｇ（Ｂ−３−１）であるので、いずれかが選択される。ここでは、新たな起点領域Ｍとして、矩形領域Ｇ（Ｂ−３−１）を選択する。
【００３６】
（ｌ）ステップＳ２０７において、経路探索部１１０は、起点領域Ｍが終点領域Ｅに一致するか否かを判定する。起点領域Ｍの矩形領域Ｇ（Ｂ−３−１）は終点領域Ｅの矩形領域Ｇ（Ｅ−６−１）とは異なるので、ステップＳ２０９に進む。ステップＳ２０９において、経路探索部１１０は、起点領域Ｍから探索の方向を１つ選択し、探索領域Ｐを決定する。ここでは、探索領域Ｐとして左方向を選ぶとする。この結果、探索領域Ｐは矩形領域Ｇ（Ｂ−２−１）となる。ステップＳ２１１において、コスト計算部１２０は、探索領域Ｐが上層又は下層方向にあるか否かを判定する。矩形領域Ｇ（Ｂ−２−１）は、上層又は下層方向への探索ではないので、ステップＳ２１３に進む。
【００３７】
（ｍ）ステップＳ２１３において、配線コスト加算部１２１は、配線コスト格納部２１に格納された情報に基づいて、コストを加算する。矩形領域Ｇ（Ｂ−２−１）は、『第１層配線領域で水平方向に１矩形領域進むコスト』であるので、配線コスト加算部１２１はコスト「１」を加算し、プログラム記憶装置２ｍに格納する。
【００３８】
（ｎ）ステップＳ２１７において、コスト計算部１２０は、探索領域Ｐが未探索であるか否かを判定する。矩形領域Ｇ（Ｂ−２−１）は未探索ではないので、ステップＳ２１９へ進む。ステップＳ２１９において、集計部１２４は、コスト計算部１２０が計算した探索領域Ｐのコストを集計し、前回の探索で計算された探索領域Ｐのコストに比べて大きくなるか否かを判定する。ここで、探索領域Ｐである矩形領域Ｇ（Ｂ−２−１）のコストは、起点領域Ｍの「１」に配線コストの「１」を加えた「２」となる。一方、前回の探索で計算された探索領域のコストと今回の探索で計算された探索領域との大小関係は、２＞０となり、今回の探索で計算された探索領域のコストの方が大きくなるため、ステップＳ２２３に進む。
【００３９】
（ｏ）図６（ａ）及び図６（ｂ）に示すように、ステップＳ２０５〜Ｓ２２３の各工程を順次繰り返していくと、始点領域Ｓを始点とした各矩形領域のコストが計算される。最終的には、ステップＳ２０７において、起点領域Ｍの位置と終点領域Ｅの位置とが同一になり、図７（ａ）及び図７（ｂ）に示すように、配線領域の各矩形領域のコストの計算が完成する。図３のステップＳ３００において、図１の結線部１３０が、経路探索部１１０が探索した最小コストとなる配線経路の情報に基づいて、図８（ａ）及び図８（ｂ）に示すように、始点領域Ｓと終点領域Ｅとを結線し、配線Ｍを敷設する。ビア配置部１４０は、配線Ｍをそれぞれ接続するビアＶ１，Ｖ２を配置する。ステップＳ４００において、ビア配置部１４０は、図９に示すように、ビアＶ１，Ｖ１をマルチカットビアＶ３，Ｖ４に置換し、作業を終了する。
【００４０】
第１の実施の形態に係る自動設計方法を用いたコストの計算手法を図１０に示す概略図を用いて説明する。第１の実施の形態に係る自動設計方法によれば、図１０に示す第１層配線領域の領域Ａから第２層配線領域の領域Ｂへ配線の経路探索を行う場合には、配線コストにビアコストｋ（ｋは１以上の定数）が乗算される。ビアコストｋが配線コストに乗算されることにより、領域Ｂのコストがより高く計算されるため、領域Ａの上層にある領域Ｂは、最小コスト経路として選択されにくくなる。この結果、異なる層への配線探索がされにくくなるため、ビアの発生率が低くなる。図９（ａ）及び図９（ｂ）に示すように、配線領域上に複数のビアを配置したい場合においては、ビアの数、大きさ、形状に応じてビアコストｋの値を大きく設定することで、配線の混雑しない領域にビアを配置するように設計できるので、マルチカットビアの置換率を高くすることができる。
【００４１】
また、領域Ａに隣接する領域Ｃ，Ｄ，Ｅ，Ｆ及び領域Ｂに隣接する領域Ｇ，Ｈ，Ｉ，Ｊのうち、領域Ｃ及び領域Ｉに障害物（既配線）Ｏが存在するような場合は、領域Ａから領域Ｂへ探索を行う際の障害物コストとして、領域Ｃ及び領域Ｉのコストを加算することで、領域Ｂのコストがより高く計算される。配線が混雑する領域のコストを高く計算することにより、配線が混雑する領域にはビアが配置されにくくなる。このため、配線が混雑しない領域にビアを配置できることになり、マルチカットビアへの置換率を高くできる。マルチカットビアへの置換率が高くなることにより、ビア不良による歩留まりの低下を抑制できるので、歩留まりの高い半導体集積回路も提供できる。なお、図４〜図１０に示す例においては、探索領域Ｐの周囲を定義する四辺に隣接する矩形領域に障害物が存在する場合に障害物コストを加算する。しかし、障害物コストの加算は、探索領域Ｐに隣接する矩形領域の情報に限られず、より広範囲の障害物の情報を考慮した探索をしてもよい。
【００４２】
図２及び図３にフローを示した一連の自動設計処理は、図２及び図３と等価なアルゴリズムのプログラムにより、図１に示したコンピュータシステム（自動設計装置）を制御して実行できる。このプログラムは、図１に示したプログラム記憶装置２ｍに記憶させればよい。
【００４３】
即ち、第１の実施の形態に係る自動設計プログラムは、
（ａ）矩形領域リスト格納部２５が、格子により複数の領域に分割された複数層の配線領域から配線の始点となる矩形領域を始点領域Ｓ、終点となる矩形領域を終点領域Ｅとして格納する手順、
（ｂ）配線コスト加算部１２１が、始点領域Ｓから終点領域Ｅへの配線経路の探索を矩形領域１つ分進める毎に配線コストを加算する手順、
（ｃ）ビアコスト乗算部１２２が、複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを配線コストに乗算する手順、
（ｄ）障害物コスト加算部１２３が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算する手順、
（ｅ）集計部１２４が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リストに格納する手順、
（ｆ）経路探索部１１０が、集計結果に基づいて、複数層の配線領域において配線経路を探索する手順、
（ｇ）結線部１３０が、始点領域と終点領域とを結線する手順、
（ｈ）ビア配置部１４０が、複数層の配線領域のいずれかにマルチカットビアを配置する手順
とを含んでいる。
【００４４】
第１の実施の形態に係る自動設計プログラムは、コンピュータ読取り可能な記録媒体に保存し、この記録媒体をプログラム記憶装置２ｍに読み込ませることにより、第１の実施の形態に係る自動設計の一連の自動設計の処理を実行することもできる。「コンピュータ読取り可能な記録媒体」とは、例えばコンピュータの外部メモリ装置、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのプログラムを記録することができるような媒体などを意味する。具体的には、フレキシブルディスク、ＣＤ−ＲＯＭ，ＭＯディスク、カセットテープ、オープンリールテープなどが「コンピュータ読取り可能な記録媒体」に含まれる。例えば、コンピュータシステムの本体は、フレキシブルディスク装置（フレキシブルディスクドライブ）及び光ディスク装置（光ディスクドライブ）を内蔵若しくは外部接続するように構成できる。フレキシブルディスクドライブに対してはフレキシブルディスクを、また光ディスクドライブに対してはＣＤ−ＲＯＭをその挿入口から挿入し、所定の読み出し操作を行うことにより、これらの記録媒体に格納されたプログラムをコンピュータシステムを構成するプログラム記憶装置２ｍにインストールすることができる。また、所定のドライブ装置を接続することにより、例えばゲームパック等に利用されているメモリ装置としてのＲＯＭや、磁気テープ装置としてのカセットテープを用いることもできる。さらに、インターネット等の情報処理ネットワークを介して、このプログラムをプログラム記憶装置２ｍに記憶させることが可能である。
【００４５】
図２〜図３に示すフローチャートに従い、２つの配線層に配線とビアの自動配置を行った半導体集積回路の一部を図１１〜図１３に例示する。図１１（ａ）は図１２の第ｋ配線３３ａの存在する上面からみた平面図であり、図１１（ｂ）は、図１２の第ｋ＋１配線３６ａ，３６ｄの存在する上面からみた平面図である。図１２は、図１１のＡ−Ａ方向からみた断面図であり、図１３は、図１１のＢ−Ｂ方向からみた断面図である。
【００４６】
図１１〜図１３に示す半導体集積回路は、現実には、自動設計装置（ＣＡＤシステム）により、図２及び図３に示すフローチャートに従って作成されたレイアウト情報に基づき、イオンビーム露光装置等のパターンジェネレータ等を用いて、半導体集積回路の実際の製造に使用される製造マスク（例えばレチクル）を用いて作成する。製造マスクには、マクロセルや論理セル（論理素子）を構築する素子の製造に必要な製造マスク、第１配線の電源配線及び信号配線等の製造に必要な製造マスクの他、第ｋ配線３３ａの製造に必要な製造マスク、第ｋ配線３３ａと第ｋ＋１配線３６ａの間の第ｋ層間絶縁膜３４にビア・ホールを開口するに必要な製造マスク、第ｋ＋１配線３６ａの製造に必要な製造マスク等が少なくとも含まれる。そして、これらの複数枚の製造マスクのセットを露光装置（ステッパ）に使用し、それぞれの段階のフォトリソグラフィー工程を行い、フォトリソグラフィー工程とイオン注入、反応性イオンエッチング（ＲＩＥ）、ＣＶＤ、スパッタリング等の種々の半導体製造プロセスとを組み合わせれば、図１１〜図１３に示すような半導体集積回路が製造できる。
【００４７】
第１の実施の形態に係る半導体集積回路は、図１２に示すように、半導体基板３０と、半導体基板３０の上に堆積された第１層間絶縁膜３１と、第１層間絶縁膜３１の上層に配置された第ｋ−１層間絶縁膜３２を有する。第ｋ−１層間絶縁膜３２の上には、第ｋ配線３３ａが配置されている。第ｋ配線３３ａの上には，第ｋ層間絶縁膜３４が配置されている。第ｋ層間絶縁膜３４の中には，第ｋ配線３３ａの終端部に接続された２つのビアプラグ３５ａ，３５ｂが埋め込まれている。第ｋ層間絶縁膜３４の上には、ビアプラグ３５ａ，３５ｂに接続された第ｋ＋１配線３６ａと、第ｋ層間絶縁膜３４上で第ｋ＋１配線３６ａから離間して配置された第ｋ＋１配線３６ｄとが配置されている。第ｋ＋１配線３６ａ，３６ｄの上には第ｋ＋１層間絶縁膜３７が配置されている。
【００４８】
図１１（ａ）に示すように、第ｋ配線３３ａが配置された層には、第ｋ配線３３ｂ、３３ｃがそれぞれ第ｋ配線３３ａから離間して配置されている。第ｋ配線３３ｃには、ビアプラグ３５ｃ、３５ｄが配置されている。第ｋ配線３３ｃは、図１２に示すように、このビアプラグ３５ｃ、３５ｄを介して上層の第ｋ＋１配線３６ａの一端に接続されている。第ｋ＋１配線３６ａの他の一端には、図１１（ｂ）に示すように、ビアプラグ３５ａ，３５ｂが配置されている。ビアプラグ３５ａ，３５ｂの下層には、図１２に示すように、第ｋ配線３３ａの一端が接続されている。
【００４９】
図１１（ａ）及び１１（ｂ）に示すように、本発明の第１の実施の形態に係る半導体集積回路によれば、配線の隣接しない領域に複数のビア（マルチカットビア）が配置されるため、１つのビアを配置する場合に比べて、ビアの欠損等による高抵抗化や断線が生じにくい。このため、歩留まりの高い半導体集積回路が提供できる。
【００５０】
（第２の実施の形態）
本発明の第２の実施の形態に係る自動設計装置は、図１４に示すように、操作者からのデータや命令などの入力を受け付ける入力装置４と、レイアウト設計等の種々の演算を実行するＣＰＵ１ｂと、レイアウト結果等を出力する表示装置５及び出力装置６と、半導体集積回路のレイアウト設計に必要な所定のデータ等を記憶したデータ記憶装置２ｂと、半導体集積回路のレイアウトプログラム等を記憶したプログラム記憶装置２ｎとを備える。入力装置４、表示装置５及び出力装置６は、入出力制御装置３を介してＣＰＵ１ｂに接続されている。ＣＰＵ１ｂは、経路探索部１１０、コスト計算部１２０、結線部１３０、及びビア配置部１４０、チップ領域分割部１５１、混雑度計算部１５２、及び混雑度判定部１５３を備える。
【００５１】
チップ領域分割部１５１は、図１５に示すように、プログラム記憶装置２ｎ等に格納されたチップ領域を分割するための情報に基づいて、自動設計装置のメモリ空間内に仮想的に設置されたチップ領域を複数の配線領域ｒに分割する。混雑度計算部１５２は、プログラム記憶装置２ｎ等に格納された配線の混雑度を計算するための情報に基づいて、配線領域ｒそれぞれの配線の混雑度を計算し、混雑度リスト格納部２６に格納する。混雑度判定部１５３は、混雑度リスト格納部２６に格納された各領域の混雑度の情報に基づいて、配線探索部１１０の配線の探索方法を決定する。
【００５２】
データ記憶装置２ｂは、配線コスト格納部２１、ビアコスト格納部２２、障害物コスト格納部２３、障害物リスト格納部２４、矩形領域リスト格納部２５、及び混雑度リスト格納部２６を備える。混雑度リスト格納部２６は、混雑度計算部１５２が計算した配線の混雑度の情報を格納する。他は、第１の実施の形態と実質的に同様であるので、説明を省略する。
【００５３】
次に、第２の実施の形態に係る自動設計方法について、図１４〜図１９を用いて説明する。
【００５４】
（ａ）図１６のステップＳ１００において、図１４に示す自動設計装置が自動設計処理を実行するために必要な各種情報が、入力装置４を介して入力される。例えば、図１４に示す自動設計装置がメモリ空間内のチップ領域上に概略配線を配置するための情報、チップ領域上を複数の領域に分割するための情報、配線の混雑度を計算するための情報、配線の混雑度の既定値、迷路法による配線の経路探索を行うための情報等が、入力装置４を介してデータ記憶装置２ｂ等に記憶される。
【００５５】
（ｂ）ステップＳ１１０において、図１４の自動設計装置が、データ記憶装置２ｂ及びプログラム記憶装置２ｎに格納された情報に基づいて、チップ領域上に概略配線を配置する。ステップＳ１２０において、チップ領域分割部１５１は、プログラム記憶装置２ｎ等に格納された情報に基づいて、図１５に示すように、チップ領域を複数の配線領域ｒに分割する。図１５では説明のために、チップ領域上の各領域の水平方向に１〜６、垂直方向にａ〜ｆの記号を付している。以下においては、各領域の位置情報を『配線領域ｒ（水平方向の位置−垂直方向の位置）』の順に示す。
【００５６】
（ｃ）ステップＳ１３０において、混雑度計算部１５２は、図１５に示すチップ領域の中から配線領域ｒを１つ選択し、ステップＳ１４０において、配線領域ｒの配線の混雑度を計算する。なお、図１５に示す値は、混雑度を示す数値の一例であり、混雑度の計算方法は特に限定されない。例えば、ステップＳ１１０における概略配線を基にした配線の混雑度を計算してもよいし、後述する詳細配線のリソース数や詳細配線が消費する予測矩形領域数を元に計算してもよい。混雑度計算部１５２の計算結果の情報は、混雑度リスト格納部２６に格納される。
【００５７】
（ｄ）ステップＳ１５０において、混雑度判定部１５３は、混雑度計算部１５２が計算した配線領域ｒの混雑度が、データ記憶装置２ｂ等に予め記憶された基準値以下になるか否かを判定する。配線領域ｒの混雑度が基準値以下になる場合は、ステップＳ２００に進み、基準値を上回る場合は、ステップＳ２５０に進む。例えば、図１５に示す例おいては、基準値が予め１．０に設定されていると仮定する。混雑度計算部１５２が配線領域ｒ（ｃ−２），（ｃ−３），（ｄ−２），（ｅ−５）を選んだ場合は、これらの配線領域ｒは基準値を上回るので、ステップＳ２５０に進む。混雑度計算部１５２が他の配線領域ｒを選んだ場合は、基準値１．０を下回るので、ステップＳ２００に進む。
【００５８】
（ｅ）ステップＳ２００において、詳細配線の探索経路処理が行われる。ステップＳ２００は、図２に示す手法と実質的に同様であるので、説明を省略する。ステップＳ２５０については、後述する。ステップＳ３００において、図１４の結線部１３０が、経路探索部１１０が探索した最小コストとなる配線経路の情報に基づいて、配線を敷設する。ステップＳ３２１において、結線部１３０は、チップ領域上の全ての配線領域ｒが結線されているか否かを判定し、結線がなされていない場合は、ステップＳ１３０に進む。全ての領域ｒが結線されている場合は、ステップＳ４００に進み、ビア配置部１４０がシングルカットビア或いはマルチカットビアを配置して作業を終了する。
【００５９】
〜第２の配線方法（ステップＳ２５０の詳細）〜
次に、ステップＳ２５０に示す第２の配線方法について説明する。ステップＳ２５０では、迷路法による配線の探索方法として、マルチカットビアへの置換を考慮しない探索方法を用いる点が、ステップＳ２００に示す配線方法と異なる。他は、ステップＳ２００と実質的に同様であるので、詳細な説明を省略する。
【００６０】
（ａ）図１７のステップＳ２５０ａにおいて、配線領域上の全ての矩形領域のコストを「０」に初期化する。ステップＳ２５０ｂにおいて、探索の開始点である始点領域Ｓの情報及び探索の終了点である終点領域Ｅの情報を、入力装置４等を介して図１４の矩形領域リスト格納部２５に格納する。図１８（ａ）の例では、始点領域Ｓとして矩形領域Ｇ（Ｂ−２−１）、終点領域Ｅとして矩形領域Ｇ（Ｅ−６−１）の情報を格納する。
【００６１】
（ｂ）ステップＳ２５０ｃにおいて、図１４の経路探索部１１０が、矩形領域リスト格納部２５に格納された情報に基づいて、コスト最小となる起点領域Ｍを選択する。現時点では、矩形領域リスト格納部２５には、始点領域Ｓ及び終点領域Ｅの情報しか入っていない。このため、経路探索部１１０は、起点領域Ｍとして、始点領域Ｓ、即ち矩形領域Ｇ（Ｂ−２−１）を選択する。ステップＳ２５０ｄにおいて、経路探索部１１０は、起点領域Ｍが終点領域Ｅに一致するか否かを判定する。図１８においては、起点領域Ｍの矩形領域Ｇ（Ｂ−２−１）は終点領域Ｅの矩形領域Ｇ（Ｅ−６−１）とは異なるので、ステップＳ２５０ｅに進む。
【００６２】
（ｃ）ステップＳ２５０ｅにおいて、経路探索部１１０は、起点領域Ｍから探索の方向（探索領域Ｐ）を１つ選択する。図１８においては、矩形領域Ｇ（Ｂ−２−１）からの探索方向として、紙面右方向、左方向、上方向、下方向、及び上層方向が考えられるが、ここでは、探索領域Ｐとして右方向を選ぶとする。この結果、探索領域Ｐは矩形領域Ｇ（Ｂ−３−１）となる。ステップＳ２５０ｆにおいて、コスト計算部１２０は、データ記憶装置２ｂに格納されたコスト情報に基づいて、探索領域Ｐの配線コストの計算を行う。なお、上述したように、ステップＳ２５０ｆにおいては、第１の実施の形態で説明したステップＳ２００に示す手法とは異なり、ビアコスト及び障害物コストについては考慮しない。図１８に示すように、矩形領域Ｇ（Ｂ−３−１）は、起点領域Ｍからみて「第１層配線領域で水平方向に１矩形領域進むコスト」である。したがって、配線コスト加算部１２１は、配線コストとしてコスト「１」を加算し、プログラム記憶装置２ｎに格納する。
【００６３】
（ｄ）ステップＳ２５０ｇにおいて、コスト計算部１２０は、探索領域Ｐが未探索であるか否かを判定する。未探索な場合はステップＳ２５０ｉに進み、未探索でない場合は、ステップＳ２５０ｈへ進む。矩形領域Ｇ（Ｂ−３−１）は未探索であるので、ステップＳ２５０ｉへ進む。ステップＳ２５０ｉにおいて、集計部１２４は、プログラム記憶装置２ｎに格納された探索領域Ｐの配線コスト等を起点領域Ｍのコストに加算し、矩形領域リスト格納部２５に格納する。ここで、矩形領域Ｇ（Ｂ−３−１）のコストは、始点領域Ｓの「０」に、配線コストの「１」を加えた「１」となる。このため、集計部１２４は、図１８に示すように、「１」の値を、矩形領域リスト格納部２５の矩形領域Ｇ（Ｂ−３−１）の領域に格納する。
【００６４】
（ｅ）ステップＳ２５０ｊにおいて、経路探索部１１０は、起点領域Ｍから未探索の方向があるか否か判定する。未探索の方向がある場合はステップＳ２５０ｄへ進み、未探索の方向がない場合はステップＳ２５０ｃへ進む。現時点では、探索領域Ｐとして矩形領域Ｇ（Ｂ−３−１）を探索したのみであるので、ステップＳ２５０ｄに進む。その後、ステップＳ２５０ｅにおいて、経路探索部１１０は、起点領域Ｍから探索の方向（探索領域Ｐ）を１つ選択する。経路探索部１１０は、矩形領域Ｇ（Ｂ−２−１）からの探索方向として、上層方向の矩形領域Ｇ（Ｂ−２−２）を選択する。
【００６５】
（ｇ）ステップＳ２５０ｆにおいて、コスト計算部１２０は、データ記憶装置２ｂに格納されたコスト情報に基づいて、探索領域Ｐの配線コストの計算を行う。探索領域Ｐの矩形領域Ｇ（Ｂ−２−２）は、『異なる層に１矩形領域進む配線コスト』であるので、配線コスト加算部１２１はコスト「２」を加算し、プログラム記憶装置２ｎ等に格納する。
【００６６】
（ｈ）ステップＳ２５０ｇにおいて、コスト計算部１２０は、探索領域Ｐが未探索であるか否かを判定する。矩形領域Ｇ（Ｂ−２−２）は未探索であるので、ステップＳ２５０ｉへ進む。ステップＳ２５０ｉにおいて、集計部１２４は、コスト計算部１２０が計算した探索領域Ｐのコストを起点領域Ｍのコストに加算し、矩形領域リスト格納部２５に格納する。ここで、プログラム記憶装置２ｎに格納された矩形領域Ｇ（Ｂ−２−２）のコストは、始点領域Ｓの「０」に、配線コストの「２」を加えた「２」である。集計部１２４は、図１８（ｂ）に示すように、矩形領域リスト格納部２５の矩形領域Ｇ（Ｂ−２−２）の領域に、コスト「２」の情報を格納する。
【００６７】
（ｈ）ステップＳ２５０ｊにおいて、経路探索部１１０は、起点領域Ｍから未探索の方向があるか否か判定する。現時点では、探索領域Ｐとして矩形領域Ｇ（Ｂ−３−１）及び矩形領域Ｇ（Ｂ−２−２）が探索されたのみで、未探索の方向が存在するので、ステップＳ２５０ｄに進む。このようにして、ステップＳ２５０ｄ〜Ｓ２５０ｊを繰り返し、未探索の方向が存在しなくなった場合は、ステップＳ２５０ｃに進む。このようにして、ステップＳ２５０ｃ〜Ｓ２５０ｊの各工程を繰り返していけば、図１９（ａ）、図１９（ｂ）に示すようなコスト情報が得られる。この時の最小コスト経路は、図１９（ａ）及び図１９（ｂ）中の矢印で示すように、矩形領域Ｇ（Ｂ−２−１）→（Ｂ−３−１）→（Ｂ−４−１）→（Ｂ−５−１）→（Ｂ−６−１）→（Ｂ−６−２）→（Ｃ−６−２）→（Ｄ−６−２）→（Ｅ−６−２）となる。最小コスト経路に基づいて配線及びビアを配置すれば、図２０（ａ）及び図２０（ｂ）に示すようなレイアウトが得られる。
【００６８】
第１の実施の形態のステップＳ２００において説明した手法では、マルチカットビアへの置換を考慮した経路を探索するために、一般的な迷路法を用いた場合に比べてより多くの配線リソースを必要とする。このため、配線混雑度の大きな領域では、マルチカットビアへの置換を考慮した配線が困難である。そこで、第２の実施の形態においては、配線の混雑度の低い領域にはマルチカットビアへの置換を考慮した配線探索手法（ステップＳ２００）を用い、配線の混雑度の高い領域にはシングルカットビアへの置換を考慮した配線探索手法（ステップＳ２５０）を選択的に用いることにより、配線可能性を犠牲にすることなくマルチカットビアの置換率を向上できる。マルチカットビアへの置換率が高くなることで、ビア不良による歩留まりの低下が抑制されるため、より歩留まりの高い半導体集積回路が提供できる。
【００６９】
図１６及び図１７にフローを示した一連の自動設計処理は、図１６及び図１７と等価なアルゴリズムのプログラムにより、図１４に示したコンピュータシステム（自動設計装置）を制御して実行できる。即ち、第２の実施の形態に係る自動設計プログラムは、
（ａ）チップ領域分割部１５１が、チップ領域を複数層の配線領域ｒに分割する手順、
（ｂ）混雑度計算部１５２が、複数層の配線領域ｒ中の特定の配線領域ｒの配線の混雑度を計算し、混雑度リスト格納部２６に格納する手順、
（ｃ）混雑度判定部１５３が、混雑度の計算結果に基づいて、ダブルカットビアを配置するための配線探索手法を特定の配線領域に用いるか否かを判断する手順、
（ｄ）矩形領域リスト格納部２５が、複数の矩形領域に分割された少なくとも２層の配線領域から、配線の始点領域Ｓ及び終点領域Ｅを格納する手順、
（ｅ）配線コスト加算部１２１が、始点領域Ｓから終点領域Ｅへの配線経路の探索を矩形領域１つ分進める毎に配線コストを加算する手順、
（ｆ）ビアコスト乗算部１２２が、混雑度の計算結果に基づいて、配線領域ｒに配置されるマルチカットビアのビアコストを配線コストに乗算する手順、
（ｇ）障害物コスト加算部１２３が、混雑度の計算結果に基づいて、障害物リスト格納部２４に格納された障害物情報に基づいて、障害物コストを加算する手順、
（ｈ）集計部１２４が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リスト格納部２５に格納する手順、
（ｉ）経路探索部１１０が、集計結果に基づいて複数の配線領域において配線経路を探索する手順、
（ｊ）結線部１３０が、始点領域Ｓと終点領域Ｅとを結線する手順、
（ｋ）ビア配置部１４０が、複数の配線領域にマルチカットビアを配置する手順、
等を含む。
【００７０】
また、このプログラムは、コンピュータ読取り可能な記録媒体に保存し、この記録媒体をプログラム記憶装置２ｎに読み込ませることにより、第２の実施の形態に係る自動設計方法の一連の処理を実行することができる。ここで、「コンピュータ読取り可能な記録媒体」とは、第１の実施の形態で説明した種々の媒体を意味する。
【００７１】
（第３の実施の形態）
本発明の第３の実施の形態に係る自動設計装置は、図２１に示すように、操作者からのデータや命令などの入力を受け付ける入力装置４と、レイアウト設計等の種々の演算を実行するＣＰＵ１ｃと、レイアウト結果等を出力する表示装置５及び出力装置６と、半導体集積回路のレイアウト設計に必要な所定のデータ等を記憶したデータ記憶装置２ｃと、半導体集積回路のレイアウトプログラム等を記憶したプログラム記憶装置２ｏとを備える。入力装置４、表示装置５及び出力装置６は、入出力制御装置３を介してＣＰＵ１ｃに接続されている。ＣＰＵ１ｃは、経路探索部１１０、コスト計算部１２０、結線部１３０、及びビア配置部１４０、小領域分割部１６０、置換率計算部１６１、及び再配線部１６２を備える。
【００７２】
小領域分割部１６０は、図２３に示すように、プログラム記憶装置２ｏ等に格納された配線領域ｒを小領域ｓに分割するための情報に基づいて、自動設計装置のメモリ空間内に仮想的に設置された半導体集積回路の配線領域ｒを複数の小領域ｓに分割する。置換率計算部１６１は、プログラム記憶装置２ｏ等に格納された配線の混雑度を計算するための情報に基づいて、小領域ｓのマルチカットビアへの置換率を計算し、置換率リスト格納部２７に格納する。再配線部１６２は、置換率リスト格納部２７に格納された各小領域ｓの混雑度の情報に基づいて、小領域ｓの配線を引きはがし、再配線する。
【００７３】
データ記憶装置２ｃは、配線コスト格納部２１、ビアコスト格納部２２、障害物コスト格納部２３、障害物リスト格納部２４、矩形領域リスト格納部２５、及び置換率リスト格納部２７を備える。置換率リスト格納部２７は、置換率計算部１６１が計算した各小領域ｓの置換率の情報を格納する。他は、第１又は第２の実施の形態と実質的に同様である。
【００７４】
次に、第３の実施の形態に係る自動設計方法について、図２１〜図２４を用いて説明する。
【００７５】
（ａ）図２２のステップＳ１００において、図２１に示す自動設計装置が自動設計処理を実行するために必要な各種情報が、入力装置４を介して入力される。例えば、図２１に示す自動設計装置がメモリ空間内の配線領域ｒを複数の小領域ｓに分割するための情報、マルチカットビアへの置換率を計算するための情報、置換率の基準値、迷路法による配線の経路探索を行うための情報等が、入力装置４を介してデータ記憶装置２ｃ或いはプログラム記憶装置２ｏ等に格納される。ステップ２００〜４００は、第１又は第２の実施の形態において説明した手順と実質的に同様である。
【００７６】
（ｂ）ステップＳ５０１において、図２１の小領域分割部１６０が、データ記憶装置２ｃ或いはプログラム記憶装置２ｏに格納された情報に基づいて、図２３に示すように、配線領域ｒを小領域ｓに分割する。図２３では説明のために、配線領域ｒの各領域の水平方向に１〜６、垂直方向にＡ〜Ｆの記号を付している。以下においては、各領域の位置情報を『小領域ｓ（水平方向の位置−垂直方向の位置）』の順に示す。
【００７７】
（ｃ）ステップＳ５０２において、置換率計算部１６１は、配線領域ｒから特定の小領域ｓを１つ選択し、ステップＳ５０３において、小領域ｓのマルチカットビアへの置換率を計算する。ステップＳ５０３における置換率の計算方法は、特に限定されない。計算結果の置換率の情報は、図２３に示すように、置換率リスト格納部２７の小領域ｓに格納される。
【００７８】
（ｄ）ステップＳ５０５において、再配線部１６２は、置換率リスト格納部２７に格納された置換率の情報を読み込み、小領域ｓの置換率が基準値を下回るか否かを判定する。置換率が基準値を下回る場合は、ステップＳ５０７に進む。置換率が基準値を下回らない場合は、ステップＳ５１０に進む。
【００７９】
（ｅ）ステップＳ５０７において、置換率が基準率を下回る場合は、再配線部１６２が、特定の小領域ｓとその周囲の他の小領域ｓの配線を引きはがす。図２３の例においては、特定の小領域ｓとして、置換率が周囲に比べて極端に低い（５０％）である小領域ｓ（Ｄ−２）が選択されると仮定する。ステップＳ５０７において、再配線部１６２は、小領域ｓ（Ｄ−２）とその周囲の小領域ｓ（Ｄ−３），（Ｅ−２），（Ｅ−３）の配線を引きはがす。引き続き、再配線部１６２は、小領域ｓ（Ｄ−２）とその周囲の小領域の配線を、ステップＳ２００又はステップＳ２５０において説明した配線探索処理により再配線する。ステップＳ５１０において、置換率計算部１６１は、配線領域ｒ上の全ての小領域ｓを選択したか否かを判定し、選択していない場合は、ステップＳ５０２に進み、再び小領域ｓを選択する。全ての小領域ｓが選択された場合は、作業を終了する。
【００８０】
第３の実施の形態に係る自動設計方法によれば、図２３に示すように、マルチカットビアへの置換率が局所的に低い領域（例えば、小領域ｓ（Ｄ−２））及びその周囲の配線を、再配線部１６２が、第１の実施の形態において説明した手法により再配線する。置換率が局所的に低い領域に対してマルチカットビアへの置換を考慮した再配線をすることにより、図２４の小領域ｓ（Ｄ−２）に示すように、マルチカットビアの置換率を５０％から７０％に向上させることができる。この結果、半導体集積回路全体としてのマルチカットビアへの置換率を、５〜１０％程度高くすることができ、歩留まりの向上が図れる。
【００８１】
図２２にフローを示した一連の自動設計処理は、図２２と等価なアルゴリズムのプログラムにより、図２１に示したコンピュータシステム（自動設計装置）を制御して実行できる。即ち、第３の実施の形態に係る自動設計プログラムは、
（ａ）矩形領域リスト格納部２５が、格子により複数の領域に分割された複数層の配線領域から配線の始点となる始点領域Ｓ及び終点となる終点領域Ｅを格納する手順、
（ｂ）配線コスト加算部１２１が、始点領域Ｓから終点領域Ｅへの配線経路の探索を矩形領域１つ分進める毎に配線コストを加算する手順、
（ｃ）ビアコスト乗算部１２２が、複数層の配線領域のいずれかに配置されるマルチカットビアのビアコストを配線コストに乗算する手順、
（ｄ）障害物コスト加算部１２３が、障害物リスト格納部に格納された障害物情報に基づいて、障害物コストを加算する手順、
（ｅ）集計部１２４が、配線コスト、ビアコスト及び障害物コストの集計結果を矩形領域リストに格納する手順、
（ｆ）経路探索部１１０が、集計結果に基づいて、複数層の配線領域において配線経路を探索する手順、
（ｇ）結線部１３０が、始点領域Ｓと終点領域Ｅとを結線する手順、
（ｈ）ビア配置部１４０が、複数層の配線領域のいずれかにマルチカットビアを配置する手順、
（ｉ）小領域分割部１６０が、配線領域ｒを複数の小領域ｓに分割する手順、
（ｊ）置換率計算部１６１が、複数の小領域ｓの中の特定の小領域ｓに対するマルチカットビアへの置換率を計算し、置換率リスト格納部２７に格納する手順、
（ｋ）再配線部１６２が、置換率の計算結果と基準値とを比較し、計算結果が基準値を下回る場合には、特定の小領域ｓ及び特定の小領域ｓの周囲の他の小領域ｓの配線を引きはがして再配線する手順
とを含む。また、このプログラムは、コンピュータ読取り可能な記録媒体に保存し、この記録媒体をプログラム記憶装置２ｏに読み込ませることにより、第３の実施の形態に係る自動設計方法の一連の処理を実行することもできる。
【００８２】
上記のように、本発明は第１乃至第３の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。したがって、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【００８３】
【図１】本発明の第１の実施の形態に係る自動設計装置を示すブロック図である。
【図２】本発明の第１の実施の形態に係る自動設計方法を示すフローチャート（その１）である。
【図３】本発明の第１の実施の形態に係る自動設計方法を示すフローチャート（その２）である。
【図４】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その１）である。
【図５】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その２）である。
【図６】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その３）である。
【図７】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その４）である。
【図８】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その５）である。
【図９】本発明の第１の実施の形態に係る自動設計方法の配線探索方法を示すＣＡＤデータ（その６）である。
【図１０】本発明の第１の実施の形態に係る自動設計方法を説明する概略図である。
【図１１】本発明の第１の実施の形態に係る自動設計方法を用いて製造可能な半導体集積回路の一例を示す平面図（その１）である。
【図１２】図１１のＡ−Ａ方向からみた断面図の一例である。
【図１３】図１１のＢ−Ｂ方向からみた断面図の一例である。
【図１４】本発明の第２の実施の形態に係る自動設計装置を示すブロック図である。
【図１５】本発明の第２の実施の形態に係る自動設計方法の一例を示すＣＡＤデータである。
【図１６】本発明の第２の実施の形態に係る自動設計方法を示すフローチャート（その１）である。
【図１７】本発明の第２の実施の形態に係る自動設計方法を示すフローチャート（その２）である。
【図１８】本発明の第２の実施の形態に係る自動設計方法の第２の配線探索方法を示すＣＡＤデータ（その１）である。
【図１９】本発明の第２の実施の形態に係る自動設計方法の第２の配線探索方法を示すＣＡＤデータ（その２）である。
【図２０】本発明の第１の実施の形態に係る自動設計方法の第２の配線探索方法を示すＣＡＤデータ（その３）である。
【図２１】本発明の第３の実施の形態に係る自動設計装置を示すブロック図である。
【図２２】本発明の第３の実施の形態に係る自動設計方法を示すフローチャートである。
【図２３】本発明の第３の実施の形態に係る自動設計方法の一例を示すＣＡＤデータ（その１）である。
【図２４】本発明の第３の実施の形態に係る自動設計方法の一例を示すＣＡＤデータ（その２）である。
【符号の説明】
【００８４】
１ａ，１ｂ，１ｃ…ＣＰＵ
２ａ，２ｂ，２ｃ…データ記憶装置
２ｍ，２ｎ，２ｏ…プログラム記憶装置
４…入力装置
２１…配線コスト格納部
２２…ビアコスト格納部
２３…障害物コスト格納部
２４…障害物リスト格納部
２５…矩形領域リスト格納部
２６…混雑度リスト格納部
２７…置換率リスト格納部
１１０…経路探索部
１１０…配線探索部
１２０…コスト計算部
１２１…配線コスト加算部
１２２…ビアコスト乗算部
１２３…障害物コスト加算部
１２４…集計部
１３０…結線部
１４０…ビア配置部
１５１…チップ領域分割部
１５２…混雑度計算部
１６０…小領域分割部
１６２…再配線部
【図１】
2006065403.tif 000003
【図２】
2006065403.tif 000004
【図３】
2006065403.tif 000005
【図４】
2006065403.tif 000006
【図５】
2006065403.tif 000007
【図６】
2006065403.tif 000008
【図７】
2006065403.tif 000009
【図８】
2006065403.tif 000010
【図９】
2006065403.tif 000011
【図１０】
2006065403.tif 000012
【図１１】
2006065403.tif 000013
【図１２】
2006065403.tif 000014
【図１３】
2006065403.tif 000015
【図１４】
2006065403.tif 000016
【図１５】
2006065403.tif 000017
【図１６】
2006065403.tif 000018
【図１７】
2006065403.tif 000019
【図１８】
2006065403.tif 000020
【図１９】
2006065403.tif 000021
【図２０】
2006065403.tif 000022
【図２１】
2006065403.tif 000023
【図２２】
2006065403.tif 000024
【図２３】
2006065403.tif 000025
【図２４】
2006065403.tif 000026