(57)【要約】【課題】後戻りのない高速な配線経路計画を可能とする自動レイアウト設計装置、自動レイアウト設計方法及び自動レイアウト設計プログラムを提供する。【解決手段】自動レイアウト設計装置のＣＰＵ１は、セル間の最短経路である概略配線経路を選定する概略配線経路選定モジュール１ａ、混雑エリアを抽出する混雑エリア選定モジュール１ｂ、混雑エリアを通過する概略配線経路を対象とした混雑テーブルを作成する混雑テーブル作成モジュール１ｃ、混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成するＶセル生成モジュール１ｄ、仮想配置セルをつなぐ仮想配線経路を選定する仮想配線経路選定モジュール１ｅ、仮想配置セルの縮退処理を行うＶセル縮退モジュール１ｆ、一部の仮想配置セルを電気特性を補うバッファリングセルに置き換えるＰセル配置モジュール１ｇを備える。【選択図】　　　図１
2004013675.tif 000002
【特許請求の範囲】
【請求項１】
セル間の最短経路である概略配線経路を選定する概略配線経路選定モジュールと、
混雑エリアを抽出する混雑エリア選定モジュールと、
前記混雑エリアを通過する前記概略配線経路を対象とした混雑テーブルを作成する混雑テーブル作成モジュールと、
前記混雑エリアを回避するように前記セル間の仮想配線経路を決定するための仮想配置セルを生成するＶセル生成モジュールと、
前記仮想配置セルをつなぐ前記仮想配線経路を選定する仮想配線経路選定モジュールと、
前記仮想配置セルの縮退処理を行うＶセル縮退モジュール
とを備えることを特徴とする自動レイアウト設計装置。
【請求項２】
一部の前記仮想配置セルを電気特性を補うバッファリングセルに置き換えるＰセル配置モジュールを更に備えることを特徴とする請求項１に記載の自動レイアウト設計装置。
【請求項３】
前記Ｖセル生成モジュールは、前記仮想配線経路に対する最初の仮想配置セル生成である場合、混雑エリアアウトラインに沿って前記仮想配置セルを生成することを特徴とする請求項１又は２に記載の自動レイアウト設計装置。
【請求項４】
前記Ｖセル生成モジュールは、前記仮想配線経路に対する最初の仮想配置セル生成でない場合、前記混雑エリアと衝突している前記仮想配線経路を形成している前記仮想配置セル間に新たな仮想配置セルを生成することを特徴とする請求項１〜３のいずれか１項に記載の自動レイアウト設計装置。
【請求項５】
セル間の最短経路である概略配線経路を選定するステップと、
混雑エリアを抽出するステップと、
前記混雑エリアを通過する前記概略配線経路を対象とした混雑テーブルを作成するステップと、
前記混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成するステップと、
前記仮想配置セルをつなぐ前記仮想配線経路を選定するステップと、
前記仮想配置セルの縮退処理を行うステップ
とを含むことを特徴とする自動レイアウト設計方法。
【請求項６】
一部の前記仮想配置セルを電気特性を補うバッファリングセルに置き換えるステップを更に含むことを特徴とする請求項５に記載の自動レイアウト設計方法。
【請求項７】
前記仮想配置セルを生成するステップは、前記仮想配線経路に対する最初の仮想配置セル生成である場合、混雑エリアアウトラインに沿って前記仮想配置セルを生成することを特徴とする請求項５又は６に記載の自動レイアウト設計方法。
【請求項８】
前記仮想配置セルを生成するステップは、前記仮想配線経路に対する最初の仮想配置セル生成でない場合、前記混雑エリアと衝突している前記仮想配線経路を形成している前記仮想配置セル間に新たな仮想配置セルを生成することを特徴とする請求項５〜７のいずれか１項に記載の自動レイアウト設計方法。
【請求項９】
セル間の最短経路である概略配線経路を選定する命令と、
混雑エリアを抽出する命令と、
前記混雑エリアを通過する前記概略配線経路を対象とした混雑テーブルを作成する命令と、
前記混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成する命令と、
前記仮想配置セルをつなぐ前記仮想配線経路を選定する命令と、
前記仮想配置セルの縮退処理を行う命令
とを含むことを特徴とする自動レイアウト設計プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＬＳＩの自動レイアウト設計に用いるもので、特に大規模なＬＳＩの自動レイアウト設計装置、自動レイアウト設計方法及び自動レイアウト設計プログラムに関する。
【０００２】
【従来の技術】
従来、ＡＳＩＣなどの自動レイアウト設計に用いられる代表的な手順を図９を参照して説明する。
【０００３】
（イ）まず、ステップＳ４０１において、セルライブラリ情報、ネットリスト（回路接続情報）、タイミング制約情報、レイアウト制約情報（設計基準）などをレイアウトシステムに入力し、データベースを作成する。
【０００４】
（ロ）次に、ステップＳ５０１において、ネットリストの接続関係を用い、できるだけセル間の配線長を最短化することを考慮し、配置位置を決定する処理を行う。信号線にタイミング制約がある場合、配置位置の制約に変換し優先的に必要な領域に配置する処理を行う。
【０００５】
（ハ）次に、ステップＳ５０２において、セル間の配線経路を決定する配線処理を行う。
【０００６】
（ニ）次に、ステップＳ４０９において、情報の出力処理を行い、パターンレイアウトデータやシミュレーションによる動作確認のための情報を出力する。
【０００７】
ここで、ステップＳ５０２における配線処理の詳細を説明する。配線処理は、概略配線処理（ステップＳ４０３）と詳細配線処理（ステップＳ４０４）の２段階からなる。
【０００８】
ステップＳ４０３において、ＬＳＩチップを平均的な格子状に区切り、概略配線領域を区分けする。ここでは、この各領域を「配線ボックス」と呼ぶ。配線ボックスの形状は、格子状に限らず、配線可能領域などの情報により長方形など他の形状でも構わない。各配線ボックスに含まれるセルとセルの接続関係を配線ボックス間での接続線に仮想し、最短経路法などにより全体的な配線計画を行う。ここで、その配線ボックスを入出力する配線数と、配線ボックス内で利用可能な配線数（以下「配線リソース」と呼ぶ。）からその配線ボックスの配線混雑度を見積もることができる。又、配線ボックスのサイズが必要な精度の得られる大きさである場合は、概略配線から信号のディレイ時間の見積もりも可能となる。ステップＳ４０４において、混雑による配線リソース不足やディレイ時間によるタイミングに問題がある場合は、ステップＳ４０５に進み、その条件を適合するように配置条件を設定し、配置処理をやり直す必要がある。図９では、ステップＳ４０５における配置改善処理とステップＳ４０２における配置処理を合わせて、広義の配置処理（ステップＳ５０１）としている。配線混雑度に問題がない場合は、ステップＳ４０６に進む。
【０００９】
次に、ステップ４０６において、レイアウト制約情報（設計基準）、タイミング制約情報に従い、各配線ボックス内の利用可能な配線経路（配線グリッド）を検索し、セル間の配線を完成させる。この処理は、配線の詳細な位置や幅、配線層などを決定するため、計算量が非常に多く、時間のかかる処理である場合が多い。高密度なＬＳＩでは、概略配線で考慮されない部分で設計基準が満たせない配線や、局所的な混雑により配線ができない部分が生ずる場合がある。ステップＳ４０７において、配線に問題がないか判断し、問題がある場合は、ステップＳ４０８に進み、配線を修正する処理を行う。ステップＳ４０７において、問題がない場合は、配線が完了し、ステップＳ４０９に進む。
【００１０】
次に、図１０に、大規模なマクロセル１１を有するＬＳＩチップ５上に、セル１２ａ、１２ｂ…、１２ｆを自動レイアウト設計で配置した図を示す。図１０は、図９における概略配線処理（ステップＳ４０３）を行った際の図であり、ＬＳＩチップ５は配線ボックス１４に分割されている。ここで、「マクロセル」とは、まとまった機能を有する、設計済みのセルの集合体である。通常、ＬＳＩは製造コストを上昇させないために、最低限必要な配線層を用いて設計することが望ましい。このような条件では、すでに設計が完了している大規模なマクロセル１１の配置したエリアは、マクロセル１１自身が複数の配線層を用いて作成されており、又、電気的特性上、他配線からの影響を避ける目的で、マクロセル１１上を通過する配線を禁止している場合がある。このような場合、各セル１２ａ、１２ｂ…、１２ｆからの配線計画がマクロセル１１上を通過できないため、マクロセル１１に沿うように通過する概略配線が計画され、マクロセル１１の周辺で配線が集中する。図１０において、セルＡ１２ａとセルＤ１２ｄを配線する配線Ａ−Ｄ、セルＢ１２ｂとセルＥ１２ｅを配線する配線Ｂ−Ｅ、セルＣ１２ｃとセルＦ１２ｆを配線する配線Ｃ−Ｆがマクロセル１１の周囲の配線ボックス１４に集中していることが分かる。
【００１１】
この状態を詳細に説明するため、図１１に、マクロセルの周辺とセル間の配線計画を示す。図１１（ａ）に示すように、ＬＳＩチップ５上には、マクロセルを配置するマクロセルエリア２０とセルを配置するセル設置可能エリア２１を有する。図１１（ｂ）は、図１１（ａ）の点線で囲んだ部分を拡大した図である。セルＡ１２ａからセルＢ１２ｂの配線Ａ−Ｂ、セルＣ１２ｃからセルＤ１２ｄの配線Ｃ−Ｄは、△印で示すマクロセルエリア上を通過できないため、その周辺のエリアを経由するように配線計画される。図１１（ｂ）では、マクロセルエリアの周辺に×印で示す混雑領域が存在し、特に配線ボックス３Ｃ１４ａに配線が集中していることが分かる。配線ボックス３Ｃの「３Ｃ」は、各配線ボックスの横、縦に割り付けられた数字及びアルファベットによって特定された位置「３Ｃ」を指す。このように、マクロセル１１の周辺は配線が非常に混雑した状態となる。
【００１２】
【発明が解決しようとする課題】
従来の概略配線処理では、上述のように、マクロセルの周辺で配線が混雑する他、マクロセルの間や回路接続性が高いセルが集中する領域で配線が混雑する。詳細配線処理では、概略配線処理における配線計画に従って、その配線ボックス内での再配線を試みる。配線ボックス間に渡って配線計画の見直しが必要である等、概略配線計画とは異なった配線経路を検索しなければならないときは、詳細配線処理において、配線の自動修正が困難な場合がある。その際は、概略配線処理あるいは、概略配線処理の前段階である配置処理からやり直さなければならない場合もある。
【００１３】
そこで、本発明では、後戻りのない高速な配線経路計画を可能とする自動レイアウト設計装置、自動レイアウト設計方法及び自動レイアウト設計プログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の特徴は、（イ）セル間の最短経路である概略配線経路を選定する概略配線経路選定モジュールと、（ロ）混雑エリアを抽出する混雑エリア選定モジュールと、（ハ）混雑エリアを通過する概略配線経路を対象とした混雑テーブルを作成する混雑テーブル作成モジュールと、（ニ）混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成するＶセル生成モジュールと、（ホ）仮想配置セルをつなぐ仮想配線経路を選定する仮想配線経路選定モジュールと、（へ）仮想配置セルの縮退処理を行うＶセル縮退モジュールとを備える自動レイアウト設計装置であることを要旨とする。ここで「セル」とは、ある単一の機能を有する基本ゲートを指す。又、「混雑エリア」とは、一定の混雑度（各配線ボックスへ計画された配線数を、各配線ボックス内の配線リソースを基準値とした相対値で表した値）を上回る配線ボックスを含む領域である。
【００１５】
本発明の第１の特徴に係る自動レイアウト設計装置によると、概略配線処理において、配線の信号優先度と混雑エリアの情報から配線経路の見直しを行い配線経路を決定するため、後戻りのない配線経路計画が可能となる。
【００１６】
又、第１の特徴に係る自動レイアウト設計装置は、（ト）一部の仮想配置セルを電気特性を補うバッファリングセルに置き換えるＰセル配置モジュールを更に備えていても良い。この自動レイアウト設計装置によると、概略配線段階からバッファの挿入も含めた配線経路選定処理を行うことができる。
【００１７】
又、第１の特徴に係る自動レイアウト設計装置のＶセル生成モジュールは、仮想配線経路に対する最初の仮想配置セル生成である場合、混雑エリアアウトラインに沿って仮想配置セルを生成しても良い。ここで、「混雑エリアアウトライン」とは、混雑エリアの周囲を取り囲むように生成したラインである。この自動レイアウト設計装置によると、最初の仮想配置セル生成において、混雑エリアを回避した仮想配線経路を選定することができる。
【００１８】
更に、第１の特徴に係る自動レイアウト設計装置のＶセル生成モジュールは、仮想配線経路に対する最初の仮想配置セル生成でない場合、混雑エリアと衝突している仮想配線経路を形成している仮想配置セル間に新たな仮想配置セルを生成しても良い。この自動レイアウト設計装置によると、最初の仮想配置セル生成でない場合、即ち、仮想配置セルの縮退処理により仮想配線経路が混雑エリアと衝突した際の仮想配置セル生成において、混雑エリアを回避した仮想配線経路を選定することができる。
【００１９】
本発明の第２の特徴は、（イ）セル間の最短経路である概略配線経路を選定するステップと、（ロ）混雑エリアを抽出するステップと、（ハ）混雑エリアを通過する概略配線経路を対象とした混雑テーブルを作成するステップと、（ニ）混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成するステップと、（ホ）仮想配置セルをつなぐ仮想配線経路を選定するステップと、（へ）仮想配置セルの縮退処理を行うステップとを含む自動レイアウト設計方法であることを要旨とする。
【００２０】
本発明の第２の特徴に係る自動レイアウト設計方法によると、概略配線処理において、配線の信号優先度と混雑エリアの情報から配線経路の見直しを行い配線経路を決定するため、後戻りのない配線経路計画が可能となる。
【００２１】
又、第２の特徴に係る自動レイアウト設計方法は、（ト）一部の仮想配置セルを電気特性を補うバッファリングセルに置き換えるステップを更に含んでいても良い。この自動レイアウト設計方法によると、概略配線段階からバッファの挿入も含めた配線経路選定処理を行うことができる。
【００２２】
又、第２の特徴に係る自動レイアウト設計方法の仮想配置セルを生成するステップは、仮想配線経路に対する最初の仮想配置セル生成である場合、混雑エリアアウトラインに沿って仮想配置セルを生成しても良い。この自動レイアウト設計方法によると、最初の仮想配置セル生成において、混雑エリアを回避した仮想配線経路を選定することができる。
【００２３】
更に、第２の特徴に係る自動レイアウト設計方法の仮想配置セルを生成するステップは、仮想配線経路に対する最初の仮想配置セル生成でない場合、混雑エリアと衝突している仮想配線経路を形成している仮想配置セル間に新たな仮想配置セルを生成しても良い。この自動レイアウト設計方法によると、最初の仮想配置セル生成でない場合、即ち、仮想配置セルの縮退処理により仮想配線経路が混雑エリアと衝突した際の仮想配置セル生成において、混雑エリアを回避した仮想配線経路を選定することができる。
【００２４】
本発明の第３の特徴は、（イ）セル間の最短経路である概略配線経路を選定する命令と、（ロ）混雑エリアを抽出する命令と、（ハ）混雑エリアを通過する概略配線経路を対象とした混雑テーブルを作成する命令と、（ニ）混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成する命令と、（ホ）仮想配置セルをつなぐ仮想配線経路を選定する命令と、（へ）仮想配置セルの縮退処理を行う命令とを含む自動レイアウト設計プログラムであることを要旨とする。
【００２５】
上記の命令を実現させる自動レイアウト設計プログラムは、自動レイアウト設計装置の処理制御装置（ＣＰＵ）に接続されているプログラム記憶装置に保存される。本発明の第３の特徴に係る自動レイアウト設計プログラムを読み出すことにより、自動レイアウト設計装置に上記の命令を実現させることが可能となる。
【００２６】
【発明の実施の形態】
次に、図面を参照して、本発明の実施の形態を説明する。以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付している。但し、図面は模式的なものであることに留意すべきである。
【００２７】
本発明の実施の形態に係る自動レイアウト設計装置は、図１に示すように、処理制御装置（ＣＰＵ）１に入力装置６、出力装置７、データ記憶装置８、プログラム記憶装置９が接続されている。ＣＰＵ１は、セル間の最短経路である概略配線経路を選定する概略配線経路選定モジュール１ａ、混雑エリアを抽出する混雑エリア選定モジュール１ｂ、混雑エリアを通過する概略配線経路を対象とした混雑テーブルを作成する混雑テーブル作成モジュール１ｃ、混雑エリアを回避するようにセル間の仮想配線経路を決定するための仮想配置セルを生成するＶセル生成モジュール１ｄ、仮想配置セルをつなぐ仮想配線経路を選定する仮想配線経路選定モジュール１ｅ、仮想配置セルの縮退処理を行うＶセル縮退モジュール１ｆ、一部の仮想配置セルを電気特性を補うバッファリングセルに置き換えるＰセル配置モジュール１ｇを備える。以下の説明において、仮想配置セルは「Ｖセル」、バッファリングセルは「Ｐセル」と記載する。
【００２８】
概略配線経路選定モジュール１ａは、セル間の最短の配線経路を選定し、このとき最短経路法等を用いる。混雑エリア選定モジュール１ｂは、混雑度を算出し、一定の混雑度を上回る配線ボックスを混雑エリアとして抽出する。そして、混雑エリアの周囲に混雑エリアアウトラインを生成する。混雑テーブル作成モジュール１ｃは、信号優先度、対象配線経路、最大混雑度、混雑経路の混雑度を集計した加算混雑度等が記述された混雑テーブルを作成する。混雑テーブルの詳細については後述する。
【００２９】
Ｖセル生成モジュール１ｄは、仮想配線経路に対する最初のＶセル生成である場合、混雑エリアアウトラインに沿ってＶセルを生成する。又、仮想配線経路に対する最初のＶセル生成でない場合、混雑エリアと衝突している仮想配線経路を形成しているＶセル間に新たなＶセルを生成する。仮想配線経路選定モジュール１ｅは、Ｖセルの配置に沿って対象となっているセル間の配線を行う。
【００３０】
Ｖセル縮退モジュール１ｆは、Ｖセルの間引き処理を行ったり、線分に折れ曲がりがない配線経路に存在するＶセルを削除したりする。Ｐセル配置モジュール１ｇは、一部のＶセルをＰセルを置き換える。Ｐセルは、例えば、信号増幅を行ったり、セル間のタイミング違反を発生させないようにタイミング調整を行ったりする必要がある場合に配置される。
【００３１】
入力装置６は、キーボード、マウス等の機器を指す。入力装置６から入力操作が行われると対応するキー情報がＣＰＵ１に伝達される。出力装置７は、モニタなどの画面を指し、液晶表示装置（ＬＣＤ）、発光ダイオード（ＬＥＤ）パネル、エレクトロルミネッサンス（ＥＬ）パネル等が使用可能である。データ記憶装置８は、ＣＰＵ１における処理において、計算途中や解析途中のデータを一時的に保存する。又、混雑テーブルや仮想配線経路を保存しても構わない。プログラム記憶装置９は、混雑テーブルの作成、Ｖセルの生成、仮想配線経路の選定などをＣＰＵ１に実行させるためのプログラムを保存する。
【００３２】
本発明の実施の形態に係る自動レイアウト設計装置によると、概略配線処理において、配線の信号優先度と混雑エリアの情報から配線経路の見直しを行い配線経路を決定するため、後戻りのない配線経路計画が可能となる。
【００３３】
次に、本発明の実施の形態に係る自動レイアウト設計装置を用いて、自動レイアウト設計を行う方法について、図２及び図６を参照して説明する。図６は、セルＡ１２ａとセルＢ１２ｂ間に配線を行う際の模式図である。
【００３４】
（イ）まず、図２のステップＳ８０において、セルライブラリ情報、ネットリスト（回路接続情報）、タイミング制約情報、レイアウト制約情報（設計基準）などをレイアウトシステムに入力し、データベースを作成する。次に、ステップＳ９０において、ネットリストの接続関係を用い、できるだけセル間の配線長を最短化することを考慮し、配置位置を決定する処理を行う。信号線にタイミング制約がある場合、配置位置の制約に変換し優先的に必要な領域に配置する処理を行う。
【００３５】
（ロ）次に、ステップＳ１０１において、概略配線経路の決定を行う。これは、最短経路法等によって行う。例えば、図６（ａ）に示すように、セルＡ１２ａからセルＢ１２ｂまでの最短の配線経路を計画する。同様に他配線すべてについて概略配線経路を決定する。
【００３６】
（ハ）その結果、ステップＳ１０２において、概略配線の各配線ボックス内にそれぞれの信号が配線計画され、配線ボックス内の配線リソースと比較することにより、配線が混雑する領域が分かる。この混雑する領域の中から、各配線ボックスへ計画された配線数が、その配線ボックス内の配線リソースを上回るなど、一定の基準値を上回る配線ボックスを混雑エリアとして抽出する。そして、図６（ａ）に示すように、混雑エリアの周囲に混雑エリアアウトライン２５を生成する。混雑エリアアウトライン２５は特定の閉じたエリアとなるように作成し、原則として、中抜きのような図形は生成しない。
【００３７】
（ニ）次に、ステップＳ１０３において、混雑エリアアウトライン２５を通過する配線を抽出し、混雑テーブルを作成する。混雑テーブルについては後に詳述する。
【００３８】
（ホ）次に、ステップＳ１０４において、混雑テーブル内の配線数が、全配線数に対してある一定の比率以上ある場合は、配線領域全体が混雑している場合であり、本発明では解決しないためエラーとする。ステップＳ１０４において、対象配線の数が指定率以上でない場合は、ステップＳ１１２に進む。
【００３９】
（へ）次に、ステップＳ１１２において、配線経路が混雑エリアを回避できたか判断する。図６（ａ）に示すように、混雑エリアを回避できていないときは、ステップＳ１０５に進む。ステップＳ１０５におけるＶセルの生成処理の詳細フローを図３に示す。図３のステップＳ２０１において、Ｖセルの生成処理が、最初のＶセル生成であるか判断する。最初のＶセル生成である場合は、ステップＳ２０２に進み、混雑エリアアウトラインに沿ってＶセルを生成する。最初のＶセル生成でない場合については後述する。図６（ｂ）では、セルＡ１２ａからセルＢ１２ｂまでの間の混雑エリアアウトライン２５に隣接する配線ボックス上にＶセル３０ａ、３０ｂ、…、３０ｇを生成している。
【００４０】
（ト）次に、ステップＳ１０６において、生成したＶセルをつなぐ仮想配線経路を生成する。この段階では、複数の経路探索を行い、混雑度や配線ベクトルの優先方向などをベースに、隣接するＶセルへの接続性のみを高速に経路検索する。この時点ではＶセルはすでに配置処理で配置された通常のセルとの重なりは考慮しない。図６（ｂ）では、セルＡ１２ａ、Ｖセル３０ａ、３０ｂ、…、３０ｇ、セルＢ１２ｂをつなぐ仮想配線経路を作成している。
【００４１】
（チ）次に、ステップＳ１０７において、仮想配線経路が選定可能であるか判断し、適切な仮想配線経路がない場合は、ステップＳ１０８に進み、混雑度計算の基準値を変更する。仮想配線経路がある場合は、ステップＳ１０９に進み、混雑エリアと衝突するか判断する。例えば、図６（ｂ）においては、仮想配線経路が混雑エリアと衝突していないので、ステップＳ１１１に進み、Ｖセルの縮退処理としてＶセル間の間引き処理を行う。図６（ｃ）では、一つおきに間引き処理を行い、図６（ｂ）に示したＶセル３０ａ、３０ｃ、３０ｅ、３０ｇが縮退している。
【００４２】
（リ）次に、ステップＳ１１２において、混雑が回避できたか判断する。混雑が回避できていない場合はステップＳ１０５に戻る。そして、ステップＳ１０５において、再びＶセルを生成する。Ｖセル生成処理では、図３のステップＳ２０１において、最初のＶセル生成であるかどうか判断する。最初のＶセル生成でない場合、即ち、Ｖセルの縮退処理により仮想配線経路が混雑エリアと衝突した際のＶセル生成である場合は、ステップＳ２０３に進む。ステップＳ２０３において、混雑エリアと衝突している仮想配線経路を形成しているＶセル間に新たなＶセルを生成する。図６（ｃ）では、Ｖセル３０ｄ、３０ｆ間の仮想配線経路が混雑エリアと衝突しているので、図６（ｄ）に示すように、Ｖセル３０ｄ、３０ｆ間の、混雑エリアに隣接する配線ボックスにＶセル３０ｈを生成している。
【００４３】
（ヌ）ステップＳ１０５において、新たなＶセルを生成した後は、再び、ステップＳ１０６に進み、Ｖセル間の仮想配線経路を選定し、ステップＳ１０７、ステップＳ１０９の判定を行う。図６（ｄ）では、ステップＳ１０９の判定において、仮想配線経路が混雑エリアと衝突しないので、ステップＳ１１１に進み、Ｖセルのマージ縮退処理を行う。図６（ｄ）では、線分に折れ曲がりがない配線経路にＶセルが存在するため、Ｖセル３０ｆを縮退している。その結果、図６（ｅ）に示す仮想配線経路が計画された。
【００４４】
（ル）仮想配線経路が混雑エリアを回避できるまで、ステップＳ１０５〜Ｓ１１１の処理を繰り返す。ステップＳ１１２において、混雑が回避できた場合は、ステップＳ１１３に進み、Ｐセル配置処理を行う。Ｐセル配置処理の詳細フローを図４に示す。ステップＳ３０１において、仮想配線経路による電気特性違反があるか判断する。電気特性違反とは、例えば、信号の減縮が起こったり、セル間のタイミング違反が発生するなどが挙げられる。この場合ステップＳ３０２に進み、配置したＶセルに換え、Ｐセルの配置処理を行う。Ｐセルは、例えば、信号増幅を行ったり、セル間のタイミング違反を発生させないようにタイミング調整を行ったりする。図６（ｆ）は、図６（ｅ）にＰセル配置処理を行った結果を示す。図６（ｆ）に示すように、仮想配置したＶセル３０ｄがＰセル３１に置き換えられている。Ｐセル３１に置き換えられなかったＶセル３０ｄ、３０ｈは、最終的な配線経路計画では配置されない。Ｖセルは、セル間の仮想配線経路を位置決めするための仮想配置セルだからである。
【００４５】
（ヲ）ステップＳ１０１〜ステップＳ１１３の概略配線処理を、混雑テーブルにエントリーされたすべての配線について繰り返す。一つの配線における概略配線処理を行う度に、混雑度は変化するので、概略配線処理を行う配線の順番は、信号優先度の高い順番としても構わない。
【００４６】
（ワ）その後、ステップＳ１２０において、レイアウト制約情報（設計基準）、タイミング制約情報に従い、各配線ボックス内の利用可能な配線経路（配線グリッド）を検索し、セル間の詳細配線を完成させる。次に、ステップＳ１３０において、情報の出力処理を行い、パターンレイアウトデータやシミュレーションによる動作確認のための情報を出力する。
【００４７】
ここで、混雑テーブルの一例を表１に示す。
【００４８】
【表１】
2004013675.tif 000003
混雑テーブルには、例えば、信号優先度、対象配線経路、最大混雑度、混雑経路の混雑度を集計した加算混雑度等が記述される。ここでは、混雑エリアアウトライン内から外に出ていない配線、混雑エリアアウトラインに奇数回の接点がある配線（混雑エリアアウトライン内外をまたぐ配線）等は処理対象としない。混雑テーブルに記述する信号優先度とは、信号の種類によりその優先度をＡ、Ｂ、Ｃ段階等で評価することによって行う。例えば、図５に示すように、クロック信号、タイミング制約つき信号（セル間での時間タイミングが予め決められている信号）、アナログ信号、一般信号、クリップ信号（電源に接続されていたり、予め電位が設定されていたりする信号）の順に優先度を低くすると設定しても良い。又、最大混雑度、加算混雑度の計算例を図７に示す。図７（ａ）における配線ボックス内の数値は、各配線ボックス毎の混雑度を表し、＋記号が配線リソースより配線計画が上回っている領域を、−記号が配線リソースに余裕がある領域を表す。ここでは、＋１以上の値をもつ配線ボックスを混雑エリアとし、混雑エリアアウトライン２５を生成した場合の例を示す。セルＡ１２ａからセルＢ１２ｂまでの最短経路法における概略配線経路Ａ−Ｂを点線で示す。この配線経路Ａ−Ｂは、混雑エリアアウトライン２５で囲われた配線が混んでいる領域を通過している。通過した配線ボックスの混雑度は、配線ボックス２Ｅは−１、配線ボックス３Ｄは＋３、配線ボックス４Ｃは＋２、配線ボックス５Ｂは−１である。このとき、図７（ｂ）に示すように、配線経路Ａ−Ｂの最大混雑度は＋３（配線ボックス３Ｄ）となる。又、加算混雑度は、＋３（配線ボックス３Ｄ）＋２（配線ボックス４Ｃ）＝＋５となる。
【００４９】
次に、本発明に係る自動レイアウト設計方法を用いた後の混雑テーブルの例を表２に示す。
【００５０】
【表２】
2004013675.tif 000004
表２における最大混雑度、加算混雑度の計算例を図８に示す。図８は、図７に示した配線経路を本発明に係る自動レイアウト設計方法を用いて変更した後の図である。図８（ａ）における配線ボックス内の数値は、図７（ａ）と同様に、各配線ボックスの混雑度を表している。セルＡ１２ａからセルＢ１２ｂまでの本発明適用後の概略配線経路Ａ−Ｂを実線で表す。配線経路Ａ−Ｂが通過した配線ボックスの混雑度は、配線ボックス２Ｆは０、配線ボックス３Ｆは＋１、配線ボックス４Ｅは＋１、配線ボックス５Ｅは＋１、配線ボックス６Ｄは０、配線ボックス６Ｃは＋１、配線ボックス６Ｂは−２である。このとき、図８（ｂ）に示すように、配線経路Ａ−Ｂの最大混雑度は＋１（配線ボックス３Ｆ、配線ボックス４Ｅ、配線ボックス５Ｅ、配線ボックス６Ｃ）となる。又、加算混雑度は、＋１（配線ボックス３Ｆ）＋１（配線ボックス４Ｅ）＋１（配線ボックス５Ｅ）＋１（配線ボックス６Ｃ）＝＋４となる。
【００５１】
表１と表２、図７と図８を比較すると、本発明に係る自動レイアウト設計方法により、高い混雑度の領域を迂回するように配線経路が変更され、最大混雑度及び加算混雑度とも混雑が緩和されたことが分かる。又、最初に配線計画されていた領域の混雑度も低下している。
【００５２】
本発明の実施の形態に係る自動レイアウト設計方法によると、概略配線処理において、配線の信号優先度と混雑エリアの情報から配線経路の見直しを行い配線経路を決定するため、後戻りのない配線経路計画が可能となる。又、概略配線経路の選択方法として混雑しているエリアを特定し、隣接するエリアのみを対象とした配線経路検索により、高速な概略配線経路の選定が可能となる。これは従来の迷路法や順序グラフを用いた方法では回避できない配線も対象となる。
【００５３】
更に、従来の配線処理では、配線が混雑している場合、詳細配線段階で概略配線経路と詳細配線経路に差が生じ、概略配線時には発生しなかったタイミングエラーなどが詳細配線時に判明するなどの問題があった。本発明では特性制約情報を元に、概略配線段階からバッファの挿入も含めた配線経路選定処理を行うことができるため、詳細配線段階での大きな迂回が発生せず、詳細配線段階での配線経路探索の時間も短縮できる。よって、全体として高速なレイアウト処理が可能となる。
【００５４】
（その他の実施の形態）
本発明は上記の実施の形態によって記載したが、この開示の一部をなす論述及び図面はこの発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態、実施例及び運用技術が明らかとなろう。
【００５５】
例えば、本発明の実施の形態に係る自動レイアウト設計装置は、データ記憶装置８、プログラム記憶装置９を分けて備えると記述したが、これらの記憶装置を一つの記憶装置で代用しても構わない。同様に、ＣＰＵ１内の各モジュールは、一つのＣＰＵ１内にあると記述したが、複数のＣＰＵ１に分けて備えられていても良い。その際、複数のＣＰＵ１間でデータのやりとりが行えるようにバスなどで装置間を接続する。
【００５６】
又、本発明の実施の形態において、自動レイアウト設計装置のＣＰＵ１に備えられた、概略配線処理を行うために必要なモジュールについて説明したが、本発明の実施の形態に係る自動レイアウト設計装置は、概略配線処理以外の処理、例えば入力処理、配置処理、詳細配線処理、出力処理を行うモジュールを備えていても良いことは勿論である。
【００５７】
又、本発明の実施の形態において、混雑エリアを通過する概略配線経路を対象として、混雑テーブルを作成すると説明したが、混雑エリアを通過しないすべての概略配線経路に対して混雑テーブルを作成しても良い。そして、これらの混雑テーブルをデータベースとして保存し、次回のレイアウト設計の参考資料としても用いても構わない。
【００５８】
このように、本発明はここでは記載していない様々な実施の形態等を含むことは勿論である。従って、本発明の技術的範囲は上記の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【００５９】
【発明の効果】
本発明によれば、後戻りのない高速な配線経路計画を可能とする自動レイアウト設計装置、自動レイアウト設計方法及び自動レイアウト設計プログラムを提供することができる。
【図面の簡単な説明】
【図１】本発明の実施に形態に係る自動レイアウト設計装置の構成図である。
【図２】本発明の実施の形態に係る自動レイアウト設計方法のフローチャートである。
【図３】図２のステップＳ１０５の詳細フローチャートである。
【図４】図２のステップＳ１１３の詳細フローチャートである。
【図５】本発明の実施の形態に係る自動レイアウト設計装置で使用する混雑テーブルの信号優先度の例である。
【図６】本発明の実施の形態に係る自動レイアウト設計方法を説明する模式図である。
【図７】（ａ）は、本発明の実施の形態に係る自動設計方法適用前の概略配線経路と混雑度を示す模式図である。（ｂ）は、（ａ）におけるＡ−Ｂ経路の混雑度を示す棒グラフである。
【図８】（ａ）は、本発明の実施の形態に係る自動設計方法適用後の概略配線経路と混雑度を示す模式図である。（ｂ）は、（ａ）におけるＡ−Ｂ経路の混雑度を示す棒グラフである。
【図９】従来の自動レイアウト設計方法のフローチャートである。
【図１０】従来の自動レイアウト設計方法におけるレイアウトイメージを表す模式図である。
【図１１】従来の自動レイアウト設計方法におけるレイアウトイメージの混雑エリアを表す模式図である。
【符号の説明】
１　処理制御装置（ＣＰＵ）
１ａ　概略配線経路選定モジュール
１ｂ　混雑エリア選定モジュール
１ｃ　混雑テーブル作成モジュール
１ｄ　Ｖセル生成モジュール
１ｅ　仮想配線経路選定モジュール
１ｆ　Ｖセル縮退モジュール
１ｇ　Ｐセル配置モジュール
５　ＬＳＩチップ
６　入力装置
７　出力装置
８　データ記憶装置
９　プログラム記憶装置
１１　マクロセル
１２ａ　セルＡ
１２ｂ　セルＢ
１２ｃ　セルＣ
１２ｄ　セルＤ
１２ｅ　セルＥ
１２ｆ　セルＦ
１４　配線ボックス
１４ａ　配線ボックス３Ｃ
２０　マクロセルエリア
２１　セル設置可能エリア
２５　混雑エリアアウトライン
３０ａ、３０ｂ、…、３０ｈ　Ｖセル
３１　Ｐセル
【図１】
2004013675.tif 000005
【図２】
2004013675.tif 000006
【図３】
2004013675.tif 000007
【図４】
2004013675.tif 000008
【図５】
2004013675.tif 000009
【図６】
2004013675.tif 000010
【図７】
2004013675.tif 000011
【図８】
2004013675.tif 000012
【図９】
2004013675.tif 000013
【図１０】
2004013675.tif 000014
【図１１】
2004013675.tif 000015