(57)【要約】【課題】  マクロ間の領域のように限られた領域において、効率のよい配線を可能とし、配線性を向上することができる自動配線方法、自動配線装置及びプログラムを提供すること。【解決手段】  本発明にかかる自動配線方法は、マクロ間の領域に、所定の一方向を配線方向とする配線方向制限領域を設定し、端子間の配線経路を探索し、配線経路が配線方向制限領域を通過する場合、配線方向に沿うように配線方向制限領域を通過する配線を敷設し、配線経路が配線方向制限領域の一端部のみを通る場合、配線方向に沿うように配線方向制限領域の一端部を通る第１の配線と、配線方向制限領域内に前記配線方向と異なる方向へ向かう第２の配線とを敷設するものである。【選択図】  図５
2006309391.tif 000002
【特許請求の範囲】
【請求項１】
配線禁止領域を含む回路領域内に配線を敷設する処理をコンピュータが実行する自動配線方法であって、
前記コンピュータは、配置情報記憶部に格納された第１及び第２の配線禁止領域の配置情報を取得し、
前記コンピュータは、前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を制限領域情報記憶部に格納し、
前記コンピュータは、接続情報記憶部に格納された回路領域内の端子の接続情報を取得し、
前記コンピュータは、前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索し、
前記コンピュータは、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設した配線敷設情報を配線敷設情報記憶部に格納し、
前記コンピュータは、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設した前記配線敷設情報を前記配線敷設情報記憶部に格納する、
自動配線方法。
【請求項２】
前記配線方向制限領域の配線方向は、前記第１の配線禁止領域と前記第２の配線禁止領域が並ぶ方向と直交する方向である、
請求項１に記載の自動配線方法。
【請求項３】
前記配線経路の探索は、
前記配線経路が、前記配線方向制限領域の配線方向に沿った配線トラック上を一直線で通る経路ではない場合、前記配線方向制限領域の外部の領域であって、前記配線方向制限領域の配線方向に沿った配線トラック上に通過点を決定し、
前記通過点の前の点から前記通過点までの配線経路を探索し配線を敷設した後、前記通過点から前記通過点の後の点までの配線経路を探索し配線を敷設する、
請求項１に記載の自動配線方法。
【請求項４】
前記配線方向と異なる方向の経路を含む配線の敷設において、前記配線経路が前記配線方向制限領域の一端部もしくは他端部のいずれか一方のみを通る場合、前記配線方向に沿うように前記配線方向制限領域の一端部もしくは他端部のいずれか一方を通る第１の配線と、前記配線方向制限領域内に前記配線方向と異なる方向へ向かう第２の配線とを敷設する、
請求項１乃至３のいずれか一つに記載の自動配線方法。
【請求項５】
前記第２の配線が敷設される方向は、前記配線方向制限領域の配線方向に直行する方向である、
請求項４に記載の自動配線方法。
【請求項６】
前記第２の配線は、前記第１の配線と、前記配線方向制限領域に接する前記第１もしくは第２の配線禁止領域の端子とを接続する配線である、
請求項４又は５に記載の自動配線方法。
【請求項７】
前記第１及び第２の配線の敷設は、前記通過点を介さずに、前記第１の配線と前記第２の配線とを一度に敷設する、
請求項４乃至６のいずれか一つに記載の自動配線方法。
【請求項８】
前記配線禁止領域は、マクロセルの領域である、
請求項１乃至７のいずれか一つに記載の自動配線方法。
【請求項９】
配線禁止領域を含む回路領域内に配線を敷設する処理をコンピュータに実行させるプログラムであって、前記処理は、
配置情報記憶部に格納された第１及び第２の配線禁止領域の配置情報を取得し、
前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を制限領域情報記憶部に格納し、
接続情報記憶部に格納された回路領域内の端子の接続情報を取得し、
前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索し、
前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設した配線敷設情報を配線敷設情報記憶部に格納し、
前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設した前記配線敷設情報を前記配線敷設情報記憶部に格納する、
プログラム。
【請求項１０】
回路領域内の第１及び第２の配線禁止領域の配置情報を取得する配置情報取得部と、
前記回路領域内に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を生成する配線方向制限領域設定部と、
前記回路領域内の端子の接続情報を取得する接続情報取得部と、
前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索する配線経路探索部と、
前記探索した配線経路に配線を敷設する配線敷設部とを有する自動配線装置であって、
前記配線方向制限領域設定部は、前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、前記配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を生成し、
前記配線敷設部は、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設し、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設する、
自動配線装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動配線方法、自動配線装置及びプログラムに関し、特に、集積回路やプリント基板の設計に用いられる自動配線方法、自動配線装置及びプログラムに関する。
【背景技術】
【０００２】
ＬＳＩ等の集積回路の設計では、設計効率や設計品質の向上を図るため、各種の設計支援システムやプログラムが用いられている。例えば、設計支援システムやプログラムでは、集積回路の領域内に自動的に配線を敷設する自動配線方法が従来から利用されている。この自動配線方法は、任意のマクロ（マクロセル）を配置した後、配線の始点と終点を選択し、自動的に配線経路を選択し配線を敷設する。
【０００３】
自動配線方法では、近年の集積回路の高速化に対応するため、できるだけ配線長を短くするような配線経路を選択する必要がある。このため、マクロ間の領域のような限られた領域を通過する配線が増加する傾向にある。さらに、集積回路の高機能化により回路全体の配線数も増えており、マクロ間を通過する配線はさらに増加している。したがって、マクロ間の領域のような限られた領域に効率よく配線する自動配線方法が望まれている。
【０００４】
図１０は、従来の自動配線方法を用いて、マクロ間の領域に配線を敷設した例を示している。この自動配線方法では、２つのマクロ８２０の間の領域に、あらかじめ配線トラック８２１が設けられている。従来の自動配線方法では、所定の配線幅、配線間隔で配線トラック８２１の上を通るように配線が敷設される。
【０００５】
しかしながら、この従来の方法では、図に示すように、マクロ間を通過（貫通）するような配線を複数設けようとすると、配線と配線が衝突（接触）してしまうことがある。
【０００６】
例えば、従来の自動配線方法では、配線トラック８２１に沿っていれば、どのような配線も可能であるため、マクロ８２０間を通過する際に、配線が折れ曲がることがある。例えば、始点８１ａから終点８１ｂまでを接続する配線８１は、２つのマクロ８２０の間で折れ曲がっている。そして、配線８１を敷設した後に、始点８２ａから終点８２ｂを接続する配線８２を設けようとすると、配線８１が、マクロ８２０の間を通過する方向（Ｙ軸方向）の配線トラック８２１を全て使用しているため、配線８２は配線８１と衝突し、配線８２を敷設することができないのである。そうすると、従来の自動配線方法では、マクロ８２０間にこれ以上配線できないため、図１１に示すように、マクロ８２０間を通過せずにマクロ８２０を迂回するように配線８２を敷設することになってしまう。
【０００７】
したがって、従来の自動配線方法では、マクロ間の領域で折れ曲がった配線が存在すると、配線が接触し、マクロ間を通過する配線数が減ってしまうため、効率よく配線することが困難であるという問題がある。上記のようにマクロを迂回する配線を設けると、配線長が長くなってしまうため、高速化、高集積化の妨げとなる。
【０００８】
一方、従来の他の自動配線方法として特許文献１が知られている。特許文献１では、配線の方向を制限する配線制限領域を設けることで、配線性の向上を図っている。しかし、特許文献１では、主に、メモリセル内部の配線性向上を図るものであり、メモリセル内を一直線に通過するワード線やデジット線（ビット線）を配線の対象としているため、マクロ間の領域には適用されておらず、配線制限領域の配線方向も単一方向のみである。
【０００９】
仮に上記のようなマクロ間の配線の折れ曲がりを防止するため、特許文献１のような配線制限領域をマクロ間の領域に単純に適用しようとすると、配線制限領域に隣接するマクロの端子に配線できない場合がある。
【００１０】
図１２は、マクロ間の領域に特許文献１の配線制限領域を単純に適用した例である。この方法では、配線制限領域の配線方向は、マクロ間を通過する方向（Ｙ軸方向）のみに限られる。例えば、始点８３ａから終点８３ｂまでを接続する配線８３は、配線制限領域８５をＹ軸方向のみで通過するため、マクロ８２０間の途中で折れ曲がることなく配線できる。しかし、始点８４ａから終点８４ｂまでを接続する配線８４を設けようとすると、終点８４ｂが配線制限領域８５に隣接しているため、配線８４を終点８４ｂ付近でＸ軸方向へ配線しようとするが、配線制御領域の配線方向がＹ軸方向のみのため、配線方向と直行するＸ軸方向へ配線できず、終点８４ｂに接続することができない。
【００１１】
したがって、特許文献１の方法により単純に配線制限領域を用いた場合でも、配線制限領域の配線方向が単一方向のみのため、マクロの端子に配線することができず、未配線となり、効率よく配線することは困難である。
【特許文献１】特開２００１−１５６１７７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
このように、従来の自動配線方法では、マクロ間のように限られた領域において、配線の方向に制限が無いと、領域を通過する配線数が減ってしまい、領域内の配線方向を単純に一方向のみに限ってしまうと、領域に接する端子に配線できなくなってしまうため、効率よく配線するのが困難であるという問題があった。
【課題を解決するための手段】
【００１３】
本発明にかかる自動配線方法は、配線禁止領域を含む回路領域内に配線を敷設する処理をコンピュータが実行する自動配線方法であって、前記コンピュータは、配置情報記憶部に格納された第１及び第２の配線禁止領域の配置情報を取得し、前記コンピュータは、前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を制限領域情報記憶部に格納し、前記コンピュータは、接続情報記憶部に格納された回路領域内の端子の接続情報を取得し、前記コンピュータは、前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索し、前記コンピュータは、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設した配線敷設情報を配線敷設情報記憶部に格納し、前記コンピュータは、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設した前記配線敷設情報を前記配線敷設情報記憶部に格納するものである。
【００１４】
この自動配線方法によれば、２つの配線禁止領域の間に、配線方向を一方向とする配線方向制限領域を設けるため、この領域を通過する配線を、無駄な折れ曲がりがなく一方向に配線することができる。また、配線方向制限領域を配線方向に通過しない配線については、異なる方向にも配線するため、配線方向制限領域に接する端子へも配線を敷設することが可能である。したがって、マクロ間のように限られた領域に、効率よく配線することができる。
【００１５】
本発明にかかるプログラムは、配線禁止領域を含む回路領域内に配線を敷設する処理をコンピュータに実行させるプログラムであって、前記処理は、配置情報記憶部に格納された第１及び第２の配線禁止領域の配置情報を取得し、前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を制限領域情報記憶部に格納し、接続情報記憶部に格納された回路領域内の端子の接続情報を取得し、前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索し、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設した配線敷設情報を配線敷設情報記憶部に格納し、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設した前記配線敷設情報を前記配線敷設情報記憶部に格納するものである。
【００１６】
このプログラムによれば、２つの配線禁止領域の間に、配線方向を一方向とする配線方向制限領域を設けるため、この領域を通過する配線を、無駄な折れ曲がりがなく一方向に配線することができる。また、配線方向制限領域を配線方向に通過しない配線については、異なる方向にも配線するため、配線方向制限領域に接する端子へも配線を敷設することが可能である。したがって、マクロ間のように限られた領域に、効率よく配線することができる。
【００１７】
本発明にかかる自動配線装置は、回路領域内の第１及び第２の配線禁止領域の配置情報を取得する配置情報取得部と、前記回路領域内に、所定の一方向を配線方向とする配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を生成する配線方向制限領域設定部と、前記回路領域内の端子の接続情報を取得する接続情報取得部と、前記配線方向制限領域情報と前記接続情報に基づき前記端子間の配線経路を探索する配線経路探索部と、前記探索した配線経路に配線を敷設する配線敷設部とを有する自動配線装置であって、前記配線方向制限領域設定部は、前記配置情報に基づき、前記第１の配線禁止領域と前記第２の配線禁止領域との間の領域に、前記配線方向制限領域を設定し、前記配線方向制限領域を設定した配線方向制限領域情報を生成し、前記配線敷設部は、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過する場合、前記配線方向に沿うように前記配線方向制限領域の一端部から他端部まで通過する配線を敷設し、前記配線経路が前記配線方向制限領域の一端部から他端部まで前記配線方向に向かって通過しない場合、前記配線方向と異なる方向の経路を含む配線を敷設するものである。
【００１８】
この自動配線装置によれば、２つの配線禁止領域の間に、配線方向を一方向とする配線方向制限領域を設けるため、この領域を通過する配線を、無駄な折れ曲がりがなく一方向に配線することができる。また、配線方向制限領域を配線方向に通過しない配線については、異なる方向にも配線するため、配線方向制限領域に接する端子へも配線を敷設することが可能である。したがって、マクロ間のように限られた領域に、効率よく配線することができる。
【発明の効果】
【００１９】
本発明によれば、マクロ間の領域のように限られた領域において、効率のよい配線を可能とし、配線性を向上することができる自動配線方法、自動配線装置及びプログラムを提供することができる。
【発明を実施するための最良の形態】
【００２０】
発明の実施の形態１．
まず、本発明の実施の形態１にかかる自動配置配線システムについて説明する。本実施形態にかかる自動配置配線システムは、配線方向制限領域を通過する配線の場合、一方向に配線し、配線方向制限領域の一端から他端まで通過しない配線の場合、複数の方向に配線することを特徴としている。
【００２１】
図１は、本実施形態にかかる自動配置配線システムの構成を示している。この自動配置配線システム（自動配線装置）１００は、マクロ（マクロセル）データとネット情報に基づいて、各マクロを自動的に配置し、最適な経路で各配線を自動的に敷設する処理を実行するシステムである。自動配置配線システム１００は、例えば、パーソナルコンピュータやサーバコンピュータ等のコンピュータにより構成されている。
【００２２】
図９は、自動配置配線システム１００を実現するためのハードウェア構成の例を示している。例えば、自動配置配線システム１００は、中央処理装置（ＣＰＵ）２０１とメモリ２０４とを含んでいる。ＣＰＵ２０１とメモリ２０４とは、バスを介して補助記憶装置としてのハードディスク装置（ＨＤＤ）２１３に接続される。自動配線装置システムは、典型的には、ユーザ・インターフェース・ハードウェアを備える。ユーザ・インターフェース・ハードウェアとしては、例えば、入力をするためのポインティング・デバイス（マウス、ジョイスティック等）やキーボード等の入力装置２０５や、視覚データをユーザに提示するための液晶ディスプレイなどの表示装置２１１がある。ハードディスク装置２１３等の記憶媒体にはオペレーティングシステムと共同してＣＰＵ２０１等に命令を与え、自動配置配線システム１００の機能を実施するためのコンピュータ・プログラムを記憶することができる。コンピュータ・プログラムは、メモリ２０４にロードされることによって実行される。図１中の各ブロックは、これらのハードウェアもしくはハードウェア上で実行されるソフトウェアによって構成される。尚、自動配置配線システム１００は、単一のコンピュータでなくとも、複数のコンピュータによって構成することも可能である。
【００２３】
図１に示されるように、自動配置配線システム１００は、自動配置配線部１１０、記憶部１２０、入力部１３０及び表示部１４０を備えている。
【００２４】
自動配置配線部１１０は、自動配置配線処理を実行する。例えば、自動配置配線部１１０は、ＣＰＵ等の制御処理装置からなり、記憶部１２０に予め記憶されたＯＳプログラムやアプリケーションプログラムに基づき、各種の処理を実行する。自動配置配線部１１０は、自動配置部１１１、配線方向制限領域設定部１１２、自動配線部１１３を有している。例えば、自動配置部１１１、配線方向制限領域設定部１１２、自動配線部１１３の各処理を記述したプログラムが記憶部１２０に格納されており、このプログラムがメモリ上に展開され、ＣＰＵがプログラムに従って処理を行い、他のハードウェア構成と協働することによって、各部を構成することができる。
【００２５】
記憶部１２０は、ハードディスクやメモリ等の内部記憶手段や光ディスク等の外部記憶手段により構成され、ＯＳプログラムやアプリケーションプログラム、各プログラムの処理に必要な各種データ等が格納される。ここでは、各種データとして、ネット情報１２１、マクロデータ１２２、マクロ配置位置情報１２３、配線方向制限領域情報１２４、レイアウト情報１２５が格納される。
【００２６】
ネット情報１２１は、ネットリストであり、例えば、論理合成ツール等により、あらかじめＲＴＬ回路を論理合成し生成されている。ネットリストには、ゲートやマクロ等の端子間のネット（接続情報）が記述されている。
【００２７】
マクロデータ１２２は、マクロライブラリ（マクロセルライブラリ）であり、内部の配置配線の設計が完了しているマクロの集合である。通常、ライブラリのマクロ内部はブラックボックス化されているため、マクロ内の領域は、配線できない配線禁止領域となる。例えば、各マクロは、種々の機能を有しており、ＣＰＵコアやＲＡＭ，ＲＯＭ等である。マクロデータ１２２には、各マクロの端子の位置情報等も含んでいる。
【００２８】
マクロ配置位置情報１２３は、マクロを配置した位置を示す情報（配線禁止領域の配置情報）である。例えば、マクロ配置位置情報１２３は、Ｘ−Ｙ座標におけるマクロの各頂点の座標位置（Ｘ−Ｙ位置）である。
【００２９】
配線方向制限領域情報１２４は、マクロ間を通過する配線の配線方向を制限する配線方向制限領域の位置や、配線方向制限領域内の配線方向を示す情報である。例えば、配線方向制限領域情報１２４は、配線方向制限領域の位置を示す座標位置、配線方向を示すＸ軸方向やＹ軸方向、配線方向制限領域内の配線ピッチや配線数等を含んでいる。
【００３０】
レイアウト情報１２５は、ネット情報１２１とマクロデータ１２２を自動的に配置配線した結果を示す情報である。例えば、レイアウト情報１２５は、各マクロの位置情報や、各端子の位置情報、各端子を接続する配線の経路情報（配線敷設情報）等を含んでいる。
【００３１】
自動配置部１１１は、自動配置処理を実行する。すなわち、自動配置部１１１は、ネット情報１２１とマクロデータ１２２を入力として、各マクロを最適な位置に配置し、マクロ配置位置情報１２３を生成して記憶部１２０に記憶する。また、自動配置部１１１は、端子の接続情報（ネット情報１２１）を取得する接続情報取得部でもあり、マクロデータを取得するマクロデータ取得部でもある。
【００３２】
配線方向制限領域設定部１１２は、配線方向制限領域設定処理を実行する。すなわち、配線方向制限領域設定部１１２は、マクロ配置位置情報１２３を入力として、各マクロ間に配線方向制限領域を設定し、配線方向制限領域情報１２４を生成して記憶部１２０に記憶する。また、配線方向制限領域設定部１１２は、マクロ等の配置情報を取得する配置情報取得部でもある。
【００３３】
自動配線部１１３は、自動配線処理を実行する。すなわち、自動配線部１１３は、ネット情報１２１、マクロデータ１２２、マクロ配置位置情報１２３、配線方向制限領域情報１２４を入力として、マクロ等の各端子を最適な経路を探索して配線を敷設し、レイアウト情報１２５を生成して記憶部１２０に記憶する。特に、本実施形態の自動配線部１１３は、マクロ間の配線方向制限領域を一方向に通過する配線を敷設するとともに、配線方向制限領域内を折れ曲がる配線も敷設可能である。また、自動配線部１１３は、端子間の配線経路を探索する配線経路探索部でもあり、探索した経路に配線を敷設する配線敷設部でもある。
【００３４】
入力部１３０は、自動配置配線システム１００の処理に必要な情報をユーザから受け付ける。例えば、キーボードやマウス等の入力装置を介して、ユーザから、ネット情報１２１やマクロデータ１２２等に関する情報（ネットリストのファイル名等）を受け付け、当該情報を自動配置部１１１等に入力する。
【００３５】
表示部１４０は、自動配置配線システム１００の処理に関する情報を表示する。例えば、レイアウト情報１２５等を、自動配線部１１３から受け付け、当該情報をＣＲＴやＬＣＤ等の表示装置に表示する。
【００３６】
次に、図２のフローチャートを用いて、本実施形態にかかる自動配置配線処理について説明する。この自動配置配線処理（Ｓ２０１〜Ｓ２０５）は、自動配置配線部１１０の自動配置部１１１、配線方向制限領域設定部１１２、自動配線部１１３において実行される処理である。
【００３７】
まず、自動配置部１１１は、ネット情報１２１の読み込みを行う（Ｓ２０１）。例えば、ユーザが、自動配置部１１１の入力であるネット情報１２１のファイル名等を入力すると、自動配置部１１１は、この入力により処理すべきネット情報１２１を記憶部１２０から読み込む。
【００３８】
次いで、自動配置部１１１は、マクロデータ１２２の読み込みを行う（Ｓ２０２）。例えば、ユーザが、自動配置部１１１の入力であるマクロデータ１２２のファイル名等を入力すると、自動配置部１１１は、この入力により処理すべきマクロデータ１２２を記憶部１２０から読み込む。
【００３９】
次いで、自動配置部１１１は、マクロの自動配置処理を実行する（Ｓ２０３）。例えば、自動配置部１１１は、Ｓ２０１で読み込んだネット情報１２１等を考慮して、Ｓ２０２で読み込んだマクロデータ１２２の各マクロを最適な位置に配置する。このとき、自動配置部１１１は、設計ルール等で決まるピッチに基づいて、マクロ間の総配線長が最短となるようにマクロを配置し、マクロ配置位置情報１２３を生成する。
【００４０】
次いで、配線方向制限領域設定部１１２は、配線方向制限領域設定処理を実行する（Ｓ２０４）。例えば、配線方向制限領域設定部１１２は、Ｓ２０３で生成されたマクロ配置位置情報１２３のマクロについて、各マクロ間の領域に、隣り合うマクロの位置関係に応じた配線方向となるように配線方向制限領域を設定し、配線方向制限領域情報１２４を生成する。
【００４１】
次いで、自動配線部１１３は、自動配線処理を実行する（Ｓ２０５）。例えば、自動配線部１１３は、Ｓ２０１で読み込まれたネット情報１２１のネットに基づいて、Ｓ２０２で読み込まれたマクロデータ１２２のマクロの端子等を最適な経路で接続する。このとき、自動配線部１１３は、マクロ間の領域に配線を設ける場合、Ｓ２０４で生成された配線方向制限領域情報１２４の配線方向を考慮し、所定の方向となるように配線する。
【００４２】
次に、図３のフローチャートを用いて、図２のＳ２０４の配線方向制限領域設定処理について説明する。この配線方向制限領域設定処理（Ｓ３０１〜Ｓ３０６）は、上述のとおり、配線方向制限領域設定部１１２により実行される処理である。
【００４３】
まず、配線方向制限領域設定部１１２は、マクロ配置位置情報１２３を取得する（Ｓ３０１）。例えば、配線方向制限領域設定部１１２は、自動配置部１１１によりマクロ配置位置情報１２３の生成が完了すると、記憶部１２０からマクロ配置位置情報１２３を読み込む。
【００４４】
次いで、配線方向制限領域設定部１１２は、配線方向制限領域の座標を決定する（Ｓ３０２）。例えば、配線方向制限領域設定部１１２は、マクロ配置位置情報１２３から、各マクロが隣り合う領域（各マクロに挟まれる領域）を配線方向制限領域として、この領域の座標位置を決定する。
【００４５】
次いで、配線方向制限領域設定部１１２は、隣り合うマクロの位置関係が上下関係か左右関係か判定する（Ｓ３０３）。例えば、配線方向制限領域設定部１１２は、マクロ配置位置情報１２３から、各マクロが隣り合う方向（並ぶ方向）を求め、各マクロの位置関係を判定する。ここで、上下関係とは、図４（ａ）に示すように、２つのマクロ２０が上と下にＹ軸方向に隣り合う関係、つまり、２つマクロ２０と配線方向制限領域２１がＹ軸方向に並ぶ関係をいう。左右関係とは、図４（ｂ）に示すように、２つのマクロ２０が右と左にＸ軸方向に隣り合う関係、つまり、２つマクロ２０と配線方向制限領域２１がＸ軸方向に並ぶ関係をいう。
【００４６】
Ｓ３０３において、隣り合うマクロの位置関係が上下関係であると判定された場合、配線方向制限領域設定部１１２は、配線方向制限領域における通過配線の配線方向をＸ軸方向に設定する（Ｓ３０４）。例えば、図４（ａ）に示すように、マクロ２０の位置関係が上下関係の場合、配線方向制限領域設定部１１２は、配線方向制限領域２１の配線方向を、配線方向制限領域２１を右端から左端（左端から右端、一端から他端）まで通過（貫通）する通過配線（貫通配線）２２の方向（通過方向）とする。つまり、配線方向制限領域設定部１１２は、配線方向制限領域２１の配線方向を、マクロ２０が隣り合う方向（Ｙ軸方向）と直交するＸ軸方向とする。
【００４７】
また、Ｓ３０３において、隣り合うマクロの位置関係が左右関係であると判定された場合、Ｓ３０４と反対に、配線方向制限領域設定部１１２は、配線方向制限領域における通過配線の配線方向をＹ方向に設定する（Ｓ３０５）。例えば、図４（ｂ）に示すように、マクロ２０の位置関係が左右関係の場合、配線方向制限領域設定部１１２は、配線方向制限領域２１の配線方向を、配線方向制限領域２１を上端から下端（下端から上端、一端から他端）まで通過する通過配線２２の方向とする。つまり、配線方向制限領域設定部１１２は、配線方向制限領域２１の配線方向を、マクロ２０が隣り合う方向（Ｘ軸方向）と直交するＹ軸方向とする。
【００４８】
Ｓ３０４もしくはＳ３０５の後、配線方向制限領域設定部１１２は、配線方向制限領域情報１２４を出力する（Ｓ３０６）。例えば、配線方向制限領域設定部１１２は、マクロ配置位置情報１２３の全ての隣り合うマクロについて、Ｓ３０２〜Ｓ３０５を行い、配線方向制限領域の位置と配線方向を設定し、これを配線方向制限領域情報１２４として記憶部１２０に記憶する。
【００４９】
このように、配線方向制限領域を通過する通過配線の配線方向を、通過配線が通過する一方向と設定することで、マクロ間の領域で不要な折れ曲りの無い配線が可能となる。
【００５０】
次に、図５及び図６のフローチャートを用いて、図２のＳ２０５の自動配線処理について説明する。図５の自動配線処理（Ｓ５０１〜Ｓ５１５）は、上述のとおり、自動配線部１１３により実行される処理である。図６は、図５のＳ５０２の処理の詳細を示している。例えば、自動配線部１１３は、配線方向制限領域設定部１１２により配線方向制限領域情報１２４の生成が完了すると、ネット情報１２１を参照し、ネット情報１２１の各ネットについて、Ｓ５０１以下の処理を行う。
【００５１】
まず、自動配線部１１３は、最初に配線するネットを選択する（Ｓ５０１）。例えば、自動配線部１１３は、ネット情報１２１を参照し、ネット情報１２１の最初に記述されているネットを選択する。
【００５２】
次いで、自動配線部１１３は、ネットの配線経路を探索する（Ｓ５０２）。例えば、自動配線部１１３は、Ｓ５０１もしくはＳ５１４で選択されたネットについて、始点の端子から終点の端子までを接続する配線の経路を探索する。Ｓ５０６やＳ５０８、Ｓ５１１でネットの途中まで配線を敷設した後の場合には、まだ配線を敷設していない残りの部分について配線経路を探索する。
【００５３】
この配線経路の探索では、配線トラックに沿って、できるだけ配線長が最短となるような経路を探索する。配線禁止領域や配線方向制限領域等によって、ネットの始点と終点とを１本の直線で接続できない場合、経路の途中の配線トラック上に通過点を設け、通過点で配線が折れ曲がって配線トラックを通るような経路とする。
【００５４】
図６に示すように、Ｓ５０２では、まず、第１の点と第２の点を直線で接続する（Ｓ６０１）。例えば、ネットの１回目の探索の場合、第１の点と第２の点はネットの始点と終点となり、通過点を設定した後の探索の場合、第１の点と第２の点は通過点とネットの終点となる。
【００５５】
次いで、第１の点と第２の点が一直線で接続できるかどうか判定する（Ｓ６０２）。Ｓ６０２において、一直線で接続できると判定された場合、一直線のままの配線経路とする。また、Ｓ６０２において、一直線で接続できないと判定された場合、配線経路が最短距離となるような位置に通過点を設定する（Ｓ６０３）。
【００５６】
次いで、配線経路に配線禁止領域が存在するかどうか判定する（Ｓ６０４）。Ｓ６０４において、配線禁止領域が存在しないと判定された場合、そのままの配線経路とする（Ｓ６０１やＳ６０３の経路）。Ｓ６０４において、配線禁止領域が存在すると判定された場合、配線経路が配線禁止領域を迂回するような位置に通過点を設定する（Ｓ６０５）。
【００５７】
次いで、配線経路に配線方向制限領域が存在するかどうか判定する（Ｓ６０６）。Ｓ６０６において、配線方向制限領域が存在しないと判定された場合、そのままの配線経路とする（Ｓ６０１やＳ６０３、Ｓ６０５の経路）。Ｓ６０６において、配線方向制限領域が存在すると判定された場合、配線方向制限領域の配線トラックが空いているか、すなわち、配線方向制限領域に未配線の配線トラックがあるかどうか判定する（Ｓ６０７）。Ｓ６０７において、配線トラックが空いていると判定された場合、配線方向制限領域を通る最短距離に通過点を設定する（Ｓ６０８）。このとき、Ｓ６０１やＳ６０３、Ｓ６０５で探索した経路が、すでに配線方向制限領域の空いている配線トラック上を通る場合は、あらたに通過点を設ける必要なはいが、この経路が空いている配線トラック上を通らない場合、配線方向制限領域の外であって、配線方向制限領域の配線方向に沿った配線トラック上を通り最短となる位置、すなわち、敷設済みの配線を避けるような位置に通過点を設ける。Ｓ６０７において、配線トラックが空いていないと判定された場合、配線方向制限領域を迂回するような位置に設定する（Ｓ６０９）。このときの迂回経路は、配線方向制限領域を迂回するとともに、配線禁止領域も迂回する必要がある。
【００５８】
こうして、Ｓ５０２では、ネットの始点から終点まで一直線の配線経路、もしくは、ネットの途中で通過点を設けた配線経路が探索される。通過点を設けた場合、まず、ネットの始点から通過点までの配線をＳ５０３〜Ｓ５１１で敷設し、さらに、この通過点からネットの終点（もしくは他の通過点）までの配線をＳ５０３〜Ｓ５１２で敷設する。
【００５９】
次いで、自動配線部１１３は、配線経路に配線方向制限領域が存在するか否か判定する（Ｓ５０３）。例えば、自動配線部１１３は、配線方向制限領域情報１２４を参照し、Ｓ５０２で探索した配線経路が、配線方向制限領域を通るか（重なるか）、配線方向制限領域の一端や他端を通るかどうか判定する。
【００６０】
Ｓ５０３において、配線経路に配線方向制限領域が存在すると判定された場合、自動配線部１１３は、配線経路の配線方向制限領域での通過配線の設定方向がＸ軸方向がＹ軸方向か判定する（Ｓ５０４）。例えば、自動配線部１１３は、配線方向制限領域情報１２４を参照し、Ｓ５０３で判定した配線経路と重なる配線方向制限領域において、設定されている配線方向を判定する。
【００６１】
Ｓ５０４において、配線方向制限領域の設定方向がＸ軸方向と判定された場合、自動配線部１１３は、配線経路が配線方向制限領域をＸ軸方向に通過するかどうか判定する（Ｓ５０５）。例えば、自動配線部１１３は、図４（ａ）のように、配線方向制限領域２１の配線方向がＸ軸方向の場合、ネットの配線経路が配線方向制限領域２１を右端から左端（一端から他端）まで通過するかどうか判定する。
【００６２】
Ｓ５０５において、配線経路が配線方向制限領域をＸ軸方向に通過すると判定された場合、自動配線部１１３は、配線方向制限領域をＸ軸方向に通過する配線を敷設する（Ｓ５０６）。例えば、自動配線部１１３は、図４（ａ）のように、配線方向制限領域２１の配線方向（Ｘ軸方向）と配線経路の方向が一致し、配線経路が配線方向制限領域２１を一端から他端まで通過する場合、通過配線２２を敷設する。Ｓ５０６の後は、Ｓ５０２に戻り、再度、配線を敷設した位置からネットの終点までの配線経路を探索する。
【００６３】
Ｓ５０５において、配線経路が配線方向制限領域をＸ軸方向に通過しないと判定された場合、自動配線部１１３は、配線方向制限領域の配線方向（Ｘ軸方向）以外の方向（Ｙ軸方向）を含む配線を敷設する（Ｓ５０９）。すなわち、配線方向制限領域の配線方向に制限されずに、配線方向の垂直方向（Ｙ軸方向）を含む配線を通過点を設けることなく、一度に、最短距離となるように敷設する。例えば、配線方向制限領域を配線方向の垂直方向（Ｙ軸方向）に通過する、つまり、隣り合うマクロの端子同士が、配線方向制限領域を介して接続されるような場合、配線方向制限領域をＹ軸方向にのみ通る配線を敷設する。また、配線経路が配線方向制限領域の一端もしくは他端のいずれか一方のみしか通らない場合、つまり、配線経路が配線方向制限領域の途中でマクロの端子に接続されるような場合、配線方向制限領域の配線方向と直交する方向（Ｙ軸方向）の配線と、配線方向（Ｘ軸方向）の配線を敷設する。すなわち、配線方向制限領域の外の始点（もしくは通過点）からマクロの端子へ折れ曲がった配線を、一度に敷設する。
【００６４】
Ｓ５０９の後、自動配線部１１３は、選択されたネットの終点まで配線を敷設したかどうか判定し（Ｓ５１５）、ネットの終点まで配線していない場合、Ｓ５０２に戻り、再度、配線を敷設した位置からネットの終点までの配線経路を探索する。Ｓ５１５において、ネットの終点まで配線したと判定した場合、Ｓ５１３の処理を行う。
【００６５】
Ｓ５０４において、配線方向制限領域の設定方向がＹ軸方向と判定された場合、自動配線部１１３は、配線経路が配線方向制限領域をＹ軸方向に通過するかどうか判定する（Ｓ５０７）。例えば、自動配線部１１３は、図４（ｂ）のように、配線方向制限領域２１の配線方向がＹ軸方向の場合、ネットの配線経路が配線方向制限領域２１を上端から下端（一端から他端）まで通過するかどうか判定する。
【００６６】
Ｓ５０７において、配線経路が配線方向制限領域をＹ軸方向に通過すると判定された場合、自動配線部１１３は、配線方向制限領域をＹ軸方向に通過する配線を敷設する（Ｓ５０８）。例えば、自動配線部１１３は、図４（ｂ）のように、配線方向制限領域２１の配線方向（Ｙ軸方向）と配線経路の方向が一致し、配線経路が配線方向制限領域２１を一端から他端まで通過する場合、通過配線２２を敷設する。Ｓ５０８の後は、Ｓ５０２に戻り、再度、配線を敷設した位置からネットの終点までの配線経路を探索する。
【００６７】
Ｓ５０７において、配線経路が配線方向制限領域をＹ軸方向に通過しないと判定された場合、自動配線部１１３は、配線方向制限領域の配線方向（Ｙ軸方向）以外の方向（Ｘ軸方向）を含む配線を敷設する（Ｓ５０９）。例えば、上記と同様に、配線方向制限領域を配線方向の垂直方向（Ｘ軸方向）に通過する場合、配線方向制限領域をＸ軸方向にのみ通る配線を敷設し、配線経路が配線方向制限領域の一端もしくは他端のいずれか一方のみしか通らない場合、配線方向制限領域の配線方向と直交する方向（Ｘ軸方向）の配線と、配線方向（Ｙ軸方向）の配線を敷設する。Ｓ５０９の後は、上記と同様にＳ５１５の処理を行う。
【００６８】
Ｓ５０３において、配線経路に配線方向制限領域が存在しないと判定された場合、自動配線部１１３は、配線経路に配線禁止領域が存在するか否か判定する（Ｓ５１０）。例えば、自動配線部１１３は、マクロ配置位置情報１２３を参照し、Ｓ５０３で判定した配線経路が、マクロの領域等の配線禁止領域を通るか（重なるか）、配線禁止領域の一部を通るかどうか判定する。
【００６９】
Ｓ５１０において、配線経路に配線禁止領域が存在すると判定された場合、自動配線部１１３は、配線禁止領域を迂回する配線を敷設する（Ｓ５１１）。例えば、自動配線部１１３は、マクロ配置位置情報１２３を参照し、Ｓ５１０で判定した配線経路と重なる配線禁止領域を避ける方向に配線を敷設する。Ｓ５１１の後は、Ｓ５０２に戻り、再度、配線を敷設した位置からネットの終点までの配線経路を探索する。
【００７０】
Ｓ５１０において、配線経路に配線禁止領域が存在しないと判定された場合、自動配線部１１３は、選択されたネットの終点まで配線を敷設する（Ｓ５１２）。例えば、自動配線部１１３は、探索した配線経路に配線方向制限領域も配線禁止領域も存在しない場合、何の制約もないため、探索通りに探索位置からネットの終点まで配線を敷設する。
【００７１】
Ｓ５１２もしくはＳ５１５の後、自動配線部１１３は、全てのネットについて配線したか判定する（Ｓ５１３）。Ｓ５１３において、配線されていないネットが存在すると判定された場合、自動配線部１１３は、さらに次のネットを選択し（Ｓ５１４）、Ｓ５０２に戻って、再度、ネットの始点からネットの終点までの配線経路を探索する。Ｓ５１３において、全てのネットについて配線が完了したと判定された場合、この自動配線処理を終了する。例えば、自動配線部１１３は、このときにレイアウト情報１２５を出力する。
【００７２】
ここで、図７及び図８を用いて、図５の自動配線処理によって配線を敷設した場合の具体例について説明する。図７及び図８では、配線トラック２３が設けられており、この配線トラック２３に沿うように配線が敷設される。図７は、配線方向制限領域２１にネット６１，６２の配線を敷設する例である。この例では、配線方向制限領域設定部１１２によって、２つのマクロ２０の間に配線方向制限領域２１が設けられている。この配線方向制限領域２１では、マクロ２０の位置関係が左右関係なので、その配線方向はＹ軸方向となっている。
【００７３】
図５の自動配線処理が開始されると、まず、自動配線部１１３は、Ｓ５０１において、始点６１ａと終点６１ｂを接続するネット６１を選択し、Ｓ５０２において、始点６１ａから終点６１ｂまでの配線経路の探索する。このとき、始点６１ａと終点６１ｂを直線で結ぼうとすると、配線方向制限領域２１の配線方向に対し斜めの方向となるため、配線方向制限領域２１の空いている配線トラックを配線方向に通るような通過点６１ｃを決定し（Ｓ６０８）、始点６１ａから通過点６１ｃまでの経路を探索する。
【００７４】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５０４において、始点６１ａから通過点６１ｃまでの配線経路に配線方向制限領域２１が存在し、配線方向制限領域２１の配線方向がＹ軸方向であると判定し、Ｓ５０７の処理を行う。Ｓ５０７において、自動配線部１１３は、始点６１ａから通過点６１ｃまでの配線経路が、配線方向制限領域２１の一端と他端の両方を通るため、この配線経路は配線方向制限領域２１をＹ軸方向に通過すると判定し、Ｓ５０８の処理を行う。Ｓ５０８において、自動配線部１１３は、配線方向制限領域２１をＹ軸方向に通過する配線を、始点６１ａから通過点６１ｃまで敷設する。
【００７５】
次いで、自動配線部１１３は、Ｓ５０２に戻り、通過点６１ｃから終点６１ｂまでの配線経路を探索する。このとき、通過点６１ｃと終点６１ｂの間には、配線方向制限領域２１も配線禁止領域３０もないため、配線トラックに沿う最短経路が配線経路となる。
【００７６】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５１０において、通過点６１ｃと終点６１ｂの間には、配線方向制限領域２１も配線禁止領域３０も存在しないため、Ｓ５１２の処理を行う。Ｓ５１２において、自動配線部１１３は、通過点６１ｃから終点６１ｂまで配線を敷設し、ネット６１の配線が完了する。
【００７７】
その後、自動配線部１１３は、Ｓ５１３において、未配線のネットが残っているため、Ｓ５１４において、次のネットであるネット６２を選択し、Ｓ５０２を行う。Ｓ５０２において、自動配線部１１３は、始点６２ａから終点６２ｂまでの配線経路の探索する。このとき、始点６２ａと終点６２ｂを直線で結ぼうとすると、配線禁止領域３０を通過するため、配線方向制限領域２１の空いている配線トラックを配線方向に通るような通過点６２ｃを決定し（Ｓ６０８）、始点６２ａから通過点６２ｃまでの経路を探索する。このとき、配線方向制限領域２１には、すでにネット６１が敷設されているため、ネット６１の配線トラックを避けるように経路を選択する。
【００７８】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５１０において、始点６２ａと終点６２ｂの間には、配線方向制限領域２１は存在しないが配線禁止領域３０が存在するため、Ｓ５１１の処理を行う。Ｓ５１１において、自動配線部１１３は、配線禁止領域３０を迂回するように、始点６２ａから通過点６２ｃまで配線を敷設する。
【００７９】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５０４において、通過点６２ｃから終点６２ｂまでの配線経路に配線方向制限領域２１が存在し、配線方向制限領域２１の配線方向がＹ軸方向であると判定し、Ｓ５０７の処理を行う。Ｓ５０７において、自動配線部１１３は、通過点６２ｃから終点６２ｂまでの配線経路が、配線方向制限領域２１の一端と他端の両方を通らず、配線方向制限領域２１の一端側しか通らないため、この配線経路は配線方向制限領域２１をＹ軸方向に通過しないと判定し、Ｓ５０９の処理を行う。Ｓ５０９において、自動配線部１１３は、配線方向制限領域２１をＹ軸方向へ向かう配線を敷設し、Ｘ軸方向へ向かう配線を敷設する。つまり、自動配線部１１３は、通過点６２ｃから配線方向制限領域２１の一端を通り配線方向のＹ軸方向へ進み、さらに、Ｘ軸方向へ折れ曲がって終点６２ｂまで配線を敷設し、ネット６２の配線が完了する。
【００８０】
その後、自動配線部１１３は、Ｓ５１５において、終点６２ｂまで配線が終了しているため、Ｓ５１３を行い、Ｓ５１３では、全てのネットの配線が完了しているため、自動配線処理を終了する。
【００８１】
図８は、配線方向制限領域２１にネット７１，７２，７３の配線を敷設する例である。この例では、図７と同様に、２つのマクロ２０の間に、配線方向をＹ軸方向とする配線方向制限領域２１が設けられている。
【００８２】
図５の自動配線処理が開始されると、まず、自動配線部１１３は、Ｓ５０１において、始点７１ａと終点７１ｂを接続するネット７１を選択し、Ｓ５０２において、始点７１ａから終点７１ｂまでの配線経路の探索する。このとき、始点７１ａと終点７１ｂを直線で結ぼうとすると、配線禁止領域３０を通過してしまうため、配線方向制限領域２１の空いている配線トラックを配線方向に通るような通過点７１ｃを決定し（Ｓ６０８）、始点７１ａから通過点７１ｃまでの経路を探索する。
【００８３】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５０４において、始点７１ａから通過点７１ｃまでの配線経路に配線方向制限領域２１が存在し、配線方向制限領域２１の配線方向がＹ軸方向であると判定し、Ｓ５０７の処理を行う。Ｓ５０７において、自動配線部１１３は、始点７１ａから通過点７１ｃまでの配線経路が、配線方向制限領域２１の一端と他端の両方を通らず、配線方向制限領域２１の他端側しか通らないため、この配線経路は配線方向制限領域２１をＹ軸方向に通過しないと判定し、Ｓ５０９の処理を行う。
【００８４】
Ｓ５０９において、自動配線部１１３は、配線方向制限領域２１をＸ軸方向へ向かう配線を敷設し、Ｙ軸方向へ向かう配線を敷設する。つまり、自動配線部１１３は、始点７１ａから配線方向制限領域２１をＸ軸方向へ進み、さらに、配線方向へ折れ曲がって配線方向制限領域２１の他端を通り通過点７１ｃまで配線を敷設する。
【００８５】
次いで、自動配線部１１３は、Ｓ５１５において、終点７１ｂまで配線が終了していないため、Ｓ５０２に戻り、通過点７１ｃから終点７１ｂまでの配線経路を探索する。このとき、通過点７１ｃと終点７１ｂの間には、配線方向制限領域２１も配線禁止領域３０もないため、配線トラックに沿う最短経路が配線経路となる。
【００８６】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５１０において、通過点７１ｃと終点７１ｂの間には、配線方向制限領域２１も配線禁止領域３０も存在しないため、Ｓ５１２の処理を行う。Ｓ５１２において、自動配線部１１３は、通過点７１ｃから終点７１ｂまで配線を敷設し、ネット７１の配線が完了する。
【００８７】
その後、自動配線部１１３は、Ｓ５１３において、未配線のネットが残っているため、Ｓ５１４において、次のネットであるネット７２を選択し、Ｓ５０２を行う。ネット７２の配線については、図７のネット６１と同様のため説明を省略する。
【００８８】
自動配線部１１３は、ネット７２の配線が完了すると、Ｓ５１３において、未配線のネットが残っているため、Ｓ５１４を行い、Ｓ５１４では、次のネットであるネット７３を選択し、Ｓ５０２を行う。
【００８９】
Ｓ５０２において、自動配線部１１３は、始点７３ａから終点７３ｂまでの配線経路の探索する。このとき、始点７３ａと終点７３ｂを直線で結ぼうとすると、配線禁止領域３０を通過するため、配線方向制限領域２１の空いている配線トラックを配線方向に通るような通過点７３ｃを決定し（Ｓ６０８）、始点７３ａから通過点７３ｃまでの経路を探索する。このとき、配線方向制限領域２１には、すでにネット７１，７２が敷設されているため、ネット７１，７２の配線トラックを避けるように経路を選択する。
【００９０】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５１０において、始点７３ａと終点７３ｂの間には、配線方向制限領域２１は存在しないが配線禁止領域３０が存在するため、Ｓ５１１の処理を行う。Ｓ５１１において、自動配線部１１３は、配線禁止領域３０を迂回するように、始点７３ａから通過点７３ｃまで配線を敷設する。
【００９１】
次いで、自動配線部１１３は、Ｓ５０２に戻り、通過点７３ｃから終点７３ｂまでの配線経路を探索する。このとき、通過点７３ｃと終点７３ｂを直線で結ぼうとすると、配線方向制限領域２１の配線方向に対し斜めの方向となるため、配線方向制限領域２１の空いている配線トラックを配線方向に通るような通過点７３ｄを決定し（Ｓ６０８）、通過点７３ｃから通過点７３ｄまでの経路を探索する。
【００９２】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５０４において、通過点７３ｃから通過点７３ｄまでの配線経路に配線方向制限領域２１が存在し、配線方向制限領域２１の配線方向がＹ軸方向であると判定し、Ｓ５０７の処理を行う。Ｓ５０７において、自動配線部１１３は、通過点７３ｃから通過点７３ｄまでの配線経路が、配線方向制限領域２１の一端と他端の両方を通るため、この配線経路は配線方向制限領域２１をＹ軸方向に通過すると判定し、Ｓ５０８の処理を行う。Ｓ５０８において、自動配線部１１３は、配線方向制限領域２１をＹ軸方向に通過する配線を、通過点７３ｃから通過点７３ｄまで敷設する。
【００９３】
次いで、自動配線部１１３は、Ｓ５０２に戻り、通過点７３ｄから終点７３ｂまでの配線経路を探索する。このとき、通過点７３ｄと終点７３ｂの間には、配線方向制限領域２１も配線禁止領域３０もないため、配線トラックに沿う最短経路が配線経路となる。
【００９４】
次いで、自動配線部１１３は、Ｓ５０３，Ｓ５１０において、通過点７３ｄと終点７３ｂの間には、配線方向制限領域２１も配線禁止領域３０も存在しないため、Ｓ５１２の処理を行う。Ｓ５１２において、自動配線部１１３は、通過点７３ｄから終点７３ｂまで配線を敷設し、ネット７３の配線が完了する。
【００９５】
その後、自動配線部１１３は、Ｓ５１３において、全てのネットの配線が完了しているため、自動配線処理を終了する。
【００９６】
このように、本実施形態では、自動配置処理後にマクロ間に配線方向制限領域を設定し、配線方向制限領域に所定の条件で配線を敷設することにより、効率のよい配線を可能としている。すなわち、Ｓ５０６やＳ５０８のように、配線方向制限領域の一端部から他端部まで配線方向に向かって通過する場合、配線方向に沿うように一方向に配線を敷設することで、マクロ間の領域で無駄な折れ曲りが無い配線が可能となる。また、Ｓ５０９のように、配線経路が配線方向制限領域を配線方向に通過しない場合、配線方向と異なる方向の経路を含む配線を敷設することで、配線方向制限領域に接するマクロの端子等に接続する配線も可能となる。さらに、Ｓ５０６やＳ５０８で配線方向制限領域を通過する配線を一度に敷設するのと同様に、Ｓ５０９でも配線方向と異なる方向を含む配線を通過点を設けることなく一度に敷設することにより、効率よく配線を敷設することができる。
【００９７】
これにより、マクロ間の配線性が向上し、マクロ間に多く配線を通すことが可能となり、マクロを迂回するような配線が少なくなり、配線長の増加を低減し、動作速度の低下を防ぐことが出来る。
【００９８】
尚、本発明の要旨を逸脱しない範囲で種々の変形、実施が可能である。例えば、配線禁止領域をマクロの領域として説明したが、マクロ以外の配線できない領域であってもよい。また、上述の例では、ＬＳＩ等の集積回路に自動配線する場合について説明したが、これに限らず、プリント基板における自動配線に本発明を適用してもよい。
【図面の簡単な説明】
【００９９】
【図１】本発明にかかる自動配置配線システムの構成を示すブロック図である。
【図２】本発明にかかる自動配置配線処理を示すフローチャートである。
【図３】本発明にかかる配線方向制限領域設定処理を示すフローチャートである。
【図４】本発明にかかる配線方向制限領域設定処理による配線方向制限領域の設定例を示す図である。
【図５】本発明にかかる自動配線処理を示すフローチャートである。
【図６】本発明にかかる自動配線処理を示すフローチャートである。
【図７】本発明にかかる自動配線処理による配線例を示す図である。
【図８】本発明にかかる自動配線処理による配線例を示す図である。
【図９】本発明にかかる自動配置配線システムのハードウェア構成図である。
【図１０】従来の自動配線処理による配線例を示す図である。
【図１１】従来の自動配線処理による配線例を示す図である。
【図１２】従来の自動配線処理による配線例を示す図である。
【符号の説明】
【０１００】
１００  自動配置配線システム
１１０  自動配置配線部
１１１  自動配置部
１１２  配線方向制限領域設定部
１１３  自動配線部
１２０  記憶部
１２１  ネット情報
１２２  マクロデータ
１２３  マクロ配置位置情報
１２４  配線方向制限領域情報
１２５  レイアウト情報
１３０  入力部
１４０  表示部
【図１】
2006309391.tif 000003
【図２】
2006309391.tif 000004
【図３】
2006309391.tif 000005
【図４】
2006309391.tif 000006
【図５】
2006309391.tif 000007
【図６】
2006309391.tif 000008
【図７】
2006309391.tif 000009
【図８】
2006309391.tif 000010
【図９】
2006309391.tif 000011
【図１０】
2006309391.tif 000012
【図１１】
2006309391.tif 000013
【図１２】
2006309391.tif 000014