基板の配線設計方法及びプログラム
【課題】配線設計において、簡易的に配線混雑を回避することが可能な配線設計方法を提供することを目的とする。
【解決手段】複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、基板を複数のタイルに分割し、複数のタイルに対応するように、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する。
【解決手段】複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、基板を複数のタイルに分割し、複数のタイルに対応するように、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板の配線設計方法及びプログラムに関する。
【背景技術】
【０００２】
半導体集積回路を備える半導体チップや、半導体パッケージの配線基板や、様々な電気機器のプリント回路基板（ＰＣＢ）等の様々な配線基板は、通常、配線が引き回される複数の配線層を備える。
【０００３】
配線の設計時間の短縮のために、自動配線設計ツールにより、自動的に配線を設計する手法が用いられている。これにより、配線の設計にかかる時間を短縮することが可能となる（例えば、特許文献１〜３参照）。
【０００４】
しかしながら、このような自動配線設計ツールにおいては、各配線層における配線方向は、配線層全体に亘り固定されている。すなわち、例えば、第１方向の配線層では、配線層全体（全面）に亘り、配線が延びる方向は第１方向である。
【０００５】
そこで、このような自動配線設計ツールを用いて配線を設計した際に、配線が混雑しているような領域が、配線層上に生じてしまう場合、設計者は、配線設計を行う前の状態に戻って、フロアプランを再検討したり、配線層自体を新たに追加したりすることによって、自動配線設計ツールを用いた配線設計を進めていた。従って、自動配線設計ツールを用いても、設計時間が長期化する傾向を避けることは難しいものであった。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平２−２２２０７２号公報
【特許文献２】特開２００７−２１４３２９号公報
【特許文献３】特開２０００−３１１９４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、配線設計において、簡易的に配線混雑を回避することが可能な配線設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様にかかる配線設計方法は、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、前記基板を複数のタイルに分割し、前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する、ことを備える。
【０００９】
本発明の一態様にかかるプログラムは、コンピュータを、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行う手段と、前記基板を複数のタイルに分割する手段と、前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成する手段と、前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する手段と、として機能させる。
【発明の効果】
【００１０】
本発明によれば、配線設計において、簡易的に配線混雑を回避することが可能な配線設計方法を提供することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施形態を説明するための図（その１）である。
【図２】第１の実施形態を説明するための図（その２）である。
【図３】第１の実施形態を説明するための図（その３）である。
【図４】第１の実施形態にかかる配線の設計方法を示すフローチャート（その１）である。
【図５】第１の実施形態にかかる配線の設計方法を示すフローチャート（その２）である。
【図６】第１の実施形態にかかる配線の設計方法を示すフローチャート（その３）である。
【図７】第１及び第２の実施形態を説明するための図（その４）である。
【図８】第１の実施形態にかかる配線の設計方法を示すフローチャート（その４）である。
【図９】第２の実施形態にかかる配線の設計方法を示すフローチャートである。
【図１０】第２の実施形態を説明するための図である。
【図１１】第３の実施形態を説明するための図である。
【図１２】第３の実施形態にかかる配線の設計方法を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図を参照して、本発明の実施形態を説明する。この説明に際して、全図面にわたり共通する部分には、共通する符号を付す。ただし、本発明は、この実施形態に限定されるものではない。
【００１３】
また、ここでは、ＬＰＤＤＲ２（Low Power Double Data Rate ２）といった半導体集積回路における、回路ブロック（機能ブロック、論理ブロック等）間を接続する配線の配線設計を例に説明するが、本発明は、このような半導体集積回路に限定されるものではない。
【００１４】
本発明の実施形態について説明する前に、本発明者が本発明をなすに至った経緯について、図１から図３を用いて、以下に説明する。
【００１５】
本発明者は、ＬＰＤＤＲ２等の半導体集積回路を設計していた。ＬＰＤＤＲ２においては、回路ブロックは、細長い長方形、もしくは、細長い長方形を有するＬ字型をしているものが多く、このような回路ブロックの間を接続する配線の設計を行っていたのである。
【００１６】
詳細には、本発明者は、以下のように、配線設計を行っていた。すなわち、図１（ａ）に示されるように、複数の配線層２は互いに重ねられており、複数の回路ブロック４は、配線層２上に配置されており、回路ブロック４の間を接続する配線３は、複数の配線層２に亘って引き回されるものとして設計される。さらに、各配線層２上に配線３が延びることができる方向（配線方向）は、Ｘ方向（横方向）と、Ｙ方向（縦方向）と、定められている。さらに、配線層毎に、配線層全面に亘って、同一の配線方向を有するものとして、定められていた。そして、本発明者は、このような配線層上の配線の設計を、自動配線設計ツールを用いて、行っていたのである。
【００１７】
ところで、このようにして得られた概略配線の設計結果においては、配線層上の特定の領域に、配線が混雑してしまうような状況が生じてしまうことがあった。このような場合、先に説明したように、設計者は、フロアプラン（回路ブロックの配置位置）から再検討したり、配線層を新たに追加したりすることで、配線が混雑する状況を避けていた。
【００１８】
しかしながら、本発明者は、配線設計の結果を分析して、配線層上の特定の領域において、複数の配線が特定の配線方向に偏ることに起因して、配線が混雑する領域が生じると考えていた。すなわち、本発明者は、このような細長い長方形の形状を持つ、回路ブロックどうしを接続する配線について設計を行うと、配線層上の特定の領域に、Ｘ方向、Ｙ方向、いずれかの方向に延びる配線が集中して存在することが多くなり、配線層上の特定の領域に配線が混雑してしまう状況が生じてしまうと、考えていたのである。
【００１９】
さらに、本発明者は、このような状況において、配線層上の配線方向を局所的に変更することにより、言い換えると、配線層の一部領域の配線方向を変更することにより、配線層上の特定の領域に配線が混雑してしまう状況を避けることができるのではないかと考えていた。
【００２０】
また、本発明者は、細長い長方形、もしくは、細長い長方形を有するＬ字型の回路ブロック間を接続する配線の設計においては、配線層上の配線方向を局所的に変更することは、効果的であると、考えていた。
【００２１】
そこで、本発明者は、所定の規則に従って、配線が混雑している配線層上の領域を検出して、その領域の配線方向を変更する、ことを考えたのである。
【００２２】
詳細には、本発明者は、以下のように、配線設計を行うことを考えたのである。まず、基板は、複数の互いに重なった配線層を備え、配線層毎に、配線は、配線層全面に亘って、同一の配線方向に延びるものとして仮決めして、概略配線設計を行う。
【００２３】
なお、概略配線とは、トポロジーと呼ばれるものであり、配線層上の詳細な座標を持つ配線ではなく、図１（ｂ）に示されるような、基板１上に仮想的に形成されたセル５（Ｇセルと呼ばれる）の有する各辺のうち、どの辺を横切るかという事項が定められた配線のことを言う。
【００２４】
次に、図２（ａ）に示されるように、基板１を所定の大きさに仮想的に分割して、複数のタイルＴを仮想的に形成する。これによって、各タイルＴは、図２（ｂ）に示されるように、各タイルＴに対応する座標を有するものであって、各配線層２の一部である部分配線領域２ａを、複数備えるものとなる。
【００２５】
そして、概略配線より算出されたタイルＴの有する配線方向毎の配線３の本数が、所定の数を超えているタイルＴがある場合（オーバーフローしている場合）には、図３に示すように、そのタイルＴの備える複数の部分配線領域２ａの配線方向を、必要に応じて変更する。タイルＴの有する配線方向毎の配線の本数の算出方法については、後述する。
【００２６】
このようにすることで、フロアプランの変更を伴わず、簡易的に、配線設計を行うことができる。従って、配線設計にかかる時間を短縮することができる。
【００２７】
（第１の実施形態）
次に、本発明にかかる第１の実施形態を、図１から図８を用いて、説明する。
【００２８】
ここでは、半導体集積回路の配線設計、詳細には、回路ブロック間の配線の配線設計を例として、説明する。ただし、本発明は、半導体集積回路に限定されるものではなく、半導体パッケージの配線基板や、ＰＣＢボード等にも用いることができる。また、本発明は、回路ブロック間を接続する配線の配線設計に限られるものではなく、その他の配線の配線設計にも用いることができる。
【００２９】
まず、基板及び配線について説明する。基板は、複数の配線層を備える。配線層には、複数の回路ブロックが搭載され、さらに、回路ブロック間を電気的に接続するための複数の配線が、引き回されることとなる。また、これらの配線は、配線層上に延びることができる方向（配線方向）が、限定されている。ここでは、配線方向は、配線層の平面の有する辺とそれぞれ平行である、Ｘ方向（横方向）と、それと直角に交わるＹ方向（縦方向）と、に限定されているものとして、説明する。しかしながら、本発明においては、配線方向は、Ｘ方向とＹ方向とに限定されるものではなく、配線層の平面の有する辺に対して、４５°に傾いた斜め方向を含むものでも良く、すなわち、配線方向が、複数の所定の方向に限定されていれば良い。
【００３０】
次に、本実施形態の配線設計方法を行うための準備について説明する。設計者は、設計の準備として、各回路ブロックの形状及び大きさ、各回路ブロックの接続関係、配線基板上に各回路ブロックをどのように配置するのか（フロアプラン）、を決定する。さらに、これらの情報に基づいて、設計者は、配線層の数と、各配線層における配線方向を、配線層全面に亘って同一の配線方向であると仮定して、決定する。
【００３１】
次に、本実施形態の配線設計方法を説明する。本実施形態の配線設計方法は、概略的には、以下の５つのステップで構成されている。この５つのステップの流れを図４のフローチャートに示す。各ステップは、以下の通りである。
【００３２】
（ステップ１）概略配線設計
（ステップ２）タイル分割
（ステップ３）タイルの選択
（ステップ４）Ｘ方向の配線について判定／処理（配線層の配線方向を局所的に変更する）
（ステップ５）Ｙ方向の配線について判定／処理
なお、ここでは、ステップ４及びステップ５において、先に、Ｘ方向の配線に対して、処理（ステップ４）を進め、次に、Ｙ方向の配線に対して処理（ステップ５）を行う場合について説明するが、順番を入れ替えて、先に、Ｙ方向の配線に対して処理を行い、次に、Ｘ方向の配線に対して処理を行っても良い。
【００３３】
さらに、本実施形態の配線設計方法は、この一連のステップを実施した後に、すべてのタイルに対して処理が施されるまで、ステップ３からステップ５を繰り返す。
【００３４】
また、これらのステップは、詳細には、以下のステップで構成されている。
【００３５】
（ステップ１）
ステップ１の「概略配線設計」を構成するステップを、図５のフローチャートを用いて説明する。以下に説明する、ステップ１にかかる概略配線設計の方法は、一例であり、他の概略配線方法を用いても良い。
【００３６】
（ステップ１−１）配線自動設計ツールに、各回路ブロックの形状及び大きさ、各回路ブロックの接続関係、フロアプラン、配線層の数、各配線層の配線方向等を入力する。次に、ステップ１−２に進む。
【００３７】
（ステップ１−２）次に、配線自動設計ツールを用いて、入力された情報をもとに、概略配線設計を行う。このステップにおいては、概略配線設計を行うために、基板上に仮想的なセル（Ｇセル）を設ける。
【００３８】
詳細には、図１（ｂ）に示されるように、基板１上に、Ｇセル５と呼ばれる仮想的なマス目状のセルを設ける。このＧセル５上のマス目（セル）の大きさは、任意に選択することができ、例えば、基板の面積、配線本数、設計時間等を考慮して、選択することができる。このＧセル５は、概略配線時に、配線混雑度を見積もるために用いられる。
【００３９】
次に、ステップ１−３に進む。
【００４０】
（ステップ１−３）自動配線設計ツールは、これらの入力データに基づいて、図１（ｂ）に示されるように、回路ブロックを接続する配線３が、Ｇセル５の有する辺のうち、どの辺を横切るかを、決定する。つまり、概略配線設計を行う。ここで得られた概略配線の結果は、後で使用するため、データとして格納しておく。次に、ステップ１−４に進む。
【００４１】
（ステップ１−４）Ｇセルの有する各辺を横切る配線の本数（セル配線数Ｎ（ｉ）と呼ぶ）が、適切なものであるかを判定する。
【００４２】
詳細には、Ｇセルの有する各辺に対して、横切ることができる配線の本数（セル配線可能本数Ｍ（ｉ）と呼ぶ）が、デザインルールや配線層の数等に従って、定められている。この値は、あらかじめ、配線自動設計ツールに入力されている。なお、このデザインルールとは、配線層上の配線が守らなくてはならない規則のことであり、例としては、配線同士の間隔が、定められた値以上にしなくてはならないといった規則のことである。
【００４３】
そして、セル配線数Ｎ（ｉ）がセル配線可能本数Ｍ（ｉ）を超えているような辺が、検出されない場合には、ステップ１−５に進む。
【００４４】
一方、セル配線数Ｎ（ｉ）がセル配線可能本数Ｍ（ｉ）を超えているような辺が、検出された場合には、ステップ２−１に進む。
【００４５】
（ステップ１−５）ステップ１−３で得られた概略配線の結果に基づき、詳細配線の設計を行う。詳細配線とは、概略配線の結果に基づき、基板上における詳細な座標が定められた配線のことを言う。詳細配線の設計が完了した後は、配線設計が完了したものとして、一連の処理を終了することとなる。
【００４６】
（ステップ２）
ステップ２の「タイル分割」を構成するステップを、図６のフローチャートを用いて説明する。なお、以下に説明する、ステップ２にかかる複数のタイルの形成方法は、一例であり、他のタイルの形成方法を用いて行っても良い。
【００４７】
（ステップ２−１）基板１に、ステップ１−２で仮想的に形成したＧセルを利用して、次の処理を行うための仮想的なマス目状のタイルを形成する。なお、ここでは、Ｇセルをずらして、仮想的なマス目状のタイルを形成する方法について説明するが、Ｇセルをそのまま用いて仮想的なマス目状のタイルを形成しても良く、Ｇセルを利用することなくタイルを形成しても良い。Ｇセルをそのまま用いてタイルを形成する場合には、例えば、後述するタイル配線本数はセル配線数Ｎ（ｉ）となり、タイル配線可能本数は、セル配線可能本数Ｍ（ｉ）となる。
【００４８】
詳細には、図７（ａ）のように、Ｇセル５のマス目を、Ｘ方向（図７（ａ）中の横方向）、Ｙ方向（図７（ａ）中の縦方向）、ともに、Ｇセル５を、半マス分位相をずらして、タイルＴを形成することとなる新たなマス目を仮想的に形成する。言い換えると、Ｇセル５上の各辺が交わる各点が、各タイルＴの中央に位置するように、タイルＴの輪郭となる新たなマス目を形成する。
【００４９】
詳細には、タイルＴは、Ｘ方向について着目すると、図７（ａ）に示されるように、Ｘ方向に延びるＧセル５上の２つの辺の一部、すなわち、辺Ａの半分と辺Ｂの半分とを含むこととなる。また、Ｙ方向についても、Ｘ方向と同様に、タイルＴは、Ｙ方向に延びるＧセル５上の２つの辺のそれぞれ半分を含むこととなる。
【００５０】
ここでは、この１つのマス目をタイルＴと呼ぶ。この各タイルＴは、図２（ｂ）に示されるように、各タイルＴに対応するものであって各配線層２の一部である部分配線領域２ａを、複数備えるものとなる。
【００５１】
Ｇセルのマス目をずらして、タイルＴを形成することにより、Ｇセルを用いて行われる概略配線の結果を利用して、各タイルＴに含まれる配線の本数を算出することが容易となる。詳細は、後述する。
【００５２】
次に、ステップ２−２へ進む。
【００５３】
（ステップ２−２）このステップにおいて、各タイルＴに含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、算出する。
【００５４】
算出方法をわかりやすく説明するため、例として、図７（ａ）に示されるタイルＴが含む配線の本数（タイル配線本数）の算出と、このタイルＴが含むことができる配線の最大本数（タイル配線可能本数）の算出と、について、説明する。
【００５５】
図７（ａ）に示されるように、タイルＴは、その内部に、Ｘ方向に延びる２つのＧセル５上の辺の一部、すなわち、辺Ａの一部と辺Ｂの一部とを含んでいる。ここでは、例として、ステップ１−３で得られた概略配線の設計結果において、辺Ａを横切るＹ方向の配線の本数（Ｙ方向セル配線数）は、３本とし（Ｎ（Ａ）＝３）、同様に、辺Ｂを通過するＹ方向の配線の本数（Ｙ方向セル配線数）は、４本とする（Ｎ（Ｂ）＝４）。
【００５６】
そして、タイルＴに含まれるＹ方向の配線の本数(Ｙ方向タイル配線本数)は、タイルＴにその一部が含まれるような辺を通過するＹ方向配線の本数（Ｙ方向セル配線数）の総和を、算出し、その値の１／２と仮定する。すなわち、上記の例の場合には、タイルＴに含まれるＹ方向の配線の本数は、｛Ｎ（Ａ）＋Ｎ（Ｂ）｝×１／２となり、図７（ａ）に示されるタイルＴの場合には、（３＋４）×１／２＝３．５本となる。
【００５７】
次に、同様にして、図７（ａ）に示されるタイルＴについて、Ｙ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）を算出する。タイルＴに含まれている辺Ａ及び辺Ｂには、先に説明したように、それぞれ、各辺に対して通過することができる配線の本数（セル配線可能本数）が、配線層の数、及び、配線層の配線方向に応じて、あらかじめ定められている。ここでは、辺Ａのセル配線可能本数をＭ（Ａ）と、辺Ｂのセル配線可能本数をＭ（Ｂ）とする。そして、このような場合、図７（ａ）に示されるタイルＴのＹ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）は、配線本数（Ｙ方向タイル配線本数）の算出と同様に、｛Ｍ（Ａ）＋Ｍ（Ｂ）｝×１／２となる。
【００５８】
また、タイルＴにおける、Ｘ方向の配線の本数（Ｘ方向タイル配線本数）と、Ｘ方向の配線の最大配線本数（Ｘ方向タイル配線可能本数）とについては、これまで説明した方法と同様に算出する。
【００５９】
ここで算出された配線本数（タイル配線本数）、最大配線本数（タイル配線可能本数）は、データとして格納しておく。次に、ステップ３へ進む。
【００６０】
（ステップ３）
ステップ３の「タイルの選択」を構成するステップを、図８のフローチャートを用いて説明する。
【００６１】
（ステップ３−１）これから述べるような処理が行われていないタイルＴが存在するか否かを判定する。この際、未処理のタイルＴが存在していなければ、詳細配線設計を行うステップ１−５へ戻る。一方、未処理のタイルＴが存在していれば、ステップ３−２に進む。
【００６２】
（ステップ３−２）ステップ２で形成された複数のタイルＴのうち、未処理（これから説明するような処理が行われていない）であるタイルＴを１つ選択する。この後、この選択したタイルＴに着目して、一連の処理を行っていく。次に、ステップ４−１へ進む。
【００６３】
（ステップ４）
ステップ４の「Ｘ方向の配線について判定／処理」を構成するステップを、図８のフローチャートを用いて説明する。
【００６４】
（ステップ４−１）ステップ３−２で選択したタイルＴにおいて、Ｘ方向の配線について、オーバーフローしているか否かの判定を行う。
【００６５】
ここでは、１つのタイルＴについて、ステップ２−２で算出されたこのタイルＴが含む配線方向毎の配線本数（タイル配線本数）を、同じくステップ２−２で算出されたこのタイルＴが含むことができる配線方向毎の最大配線本数（タイル配線可能本数）と比較して、この配線本数が最大配線本数よりも大きい場合には、その配線方向の配線は、オーバーフローしていると定義する。
【００６６】
そして、Ｘ方向の配線が、オーバーフローしていない場合には、次に、Ｙ方向の配線について処理を行うため、ステップ５−１へ進む。一方、Ｘ方向の配線が、オーバーフローしている場合には、ステップ４−２へ進む。
【００６７】
（ステップ４−２）このステップでは、ステップ４−１において、Ｘ方向の配線がオーバーフローと判定された場合、選択されたタイルＴの備える複数の部分配線領域２ａのうちの１つを選択して、配線方向を変更する（局所的に配線方向を変更する）。
【００６８】
各タイルＴは、ステップ２で説明したように、図２（ｂ）のような、各タイルＴの座標に対応するものであって各配線層２の一部である部分配線領域２ａを、複数備えている。従って、Ｘ方向の配線が、オーバーフローと判定されたタイルＴの備える複数の部分配線領域２ａのうち、Ｙ方向の配線方向を持つ部分配線領域２ａを１個選択し、その選択した部分配線領域２ａの配線方向を、Ｙ方向からＸ方向に変更するのである。
【００６９】
この際、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、例えば、下の部分配線領域２ａから順次１個選択し、配線方向を変更しても良く、あらかじめ定められた所定の順番に従って部分配線領域２ａを１個選択し、配線方向を変更するものであれば良い。このようにすることで、隣接する他のタイルＴに対する処理も、同様な処理を行うことができ、隣接するタイルＴ同士で、部分配線領域２ａの構成（各タイルＴの備える複数の部分配線領域２ａにおいて、Ｘ方向の配線方向を持つ部分配線領域２ａと、Ｙ方向の配線方向を持つ部分配線領域２ａと、の組み合わせ）が異なるといった状況を、言い換えると、隣接するタイルＴ同士において、隣接する部分配線領域２ａの配線方向が異なるといった状況を、減らすことができる。
【００７０】
次に、ステップ４−３へ進む。
【００７１】
（ステップ４−３）このステップにおいては、ステップ４−２で、１個の部分配線領域の配線方向が変更されたことから、それに伴って、配線方向毎の、選択されたタイルＴが含むことができる配線の最大配線本数（タイル配線可能本数）の値を、変更する。
【００７２】
すなわち、図３を例に挙げて説明すると、タイルＴの備える部分配線領域２ａは６個であり、詳細には、Ｘ方向の配線方向を持つ部分配線領域２ａは３個、Ｙ方向の配線方向を持つ部分配線領域２ａは３個である。さらに、ここでは、１つの部分配線領域２ａは、最大４本の配線を含むことができるものとする。従って、変更前においては、このタイルＴについては、Ｘ方向及びＹ方向の配線ともに、１２本が最大配線本数（タイル配線可能本数）となる。
【００７３】
しかしながら、１つの部分配線領域２ａの配線方向を変更したことから、このタイルＴでは、Ｘ方向の配線方向を持つ部分配線領域２ａは４個、Ｙ方向の配線方向を持つ部分配線領域２ａは２個となる。従って、タイルＴにおいては、Ｘ方向の最大配線本数は１６本、Ｙ方向の最大配線本数は８本となる。すなわち、最大配線本数（タイル配線可能本数）は変更されることとなるのである。
【００７４】
従って、ステップ２−２で説明した手順と同様にして、再度、配線方向毎の、選択されたタイルＴの最大配線本数（タイル配線可能本数）を再度算出することとなる。この算出された値は、更新された最大配線本数として、後で使用するため、データとして格納しておく。次に、ステップ４−４−１へ進む。
【００７５】
（ステップ４−４−１）次に、ステップ４−２において、１個の部分配線領域の配線方向を変更した後、選択されたタイルＴのＹ方向の配線がオーバーフローしているかを判定する。その際に用いられる最大配線本数（タイル配線可能本数）は、ステップ４−３で算出されたものを用いる。Ｙ方向の配線がオーバーフローしていない場合には、ステップ４−１へ戻る。一方、Ｙ方向の配線がオーバーフローしている場合には、ステップ４−５へ進む。
【００７６】
（ステップ４−５）ステップ４−４−１において、Ｙ方向の配線がオーバーフローしている場合には、解なしとして、自動配線設計ツールは、エラー出力する。その後、一連の処理は、終了する。
【００７７】
そして、Ｘ方向の配線について、オーバーフローしている旨の判定がなくなるまで、ステップ４−１からステップ４−５を繰り返すのである。このような繰り返しにおいては、先に説明したように、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、このような順に限られるものではなく、あらかじめ決まられた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００７８】
ステップ４−１からステップ４−５を繰り返して、Ｘ方向の配線について、オーバーフローしている旨の判定がなくなった場合には、ステップ５−１へ進む。
【００７９】
（ステップ５）
ステップ５の「Ｙ方向の配線について判定／処理」を構成するステップを以下に説明する。このステップ５を構成するステップは、ステップ４を構成するステップと同様のものであるため、詳細な説明は、省略する。なお、ステップ５は、図８のフローチャートに示される。
【００８０】
（ステップ５−１）このステップでは、ステップ３−２で選択したタイルＴについて、Ｙ方向の配線について、オーバーフローしているか否かの判定を行う。
この際、ステップ４−３を経ていない場合には、ステップ２−２で算出された最大配線本数（タイル配線可能本数）を、一方、ステップ４−３を経ている場合には、ステップ４−３で更新された最大配線本数を、用いることとなる。
【００８１】
Ｙ方向の配線が、オーバーフローしていない場合には、次に、未処理のタイルＴを選択するために、ステップ３−１へ戻る。一方、Ｙ方向の配線が、オーバーフローしている場合には、ステップ５−２へ進む。
【００８２】
（ステップ５−２）このステップにおいては、ステップ５−１において、Ｙ方向の配線が、オーバーフローしているものと判定された場合、選択されたタイルＴの備える複数の部分配線領域のうち、Ｘ方向の配線方向をもつ部分配線領域の１個を選択して、配線方向を、Ｘ方向からＹ方向に変更するのである。これまでと同様に、例えば、図３に示されるように、上の部分配線領域２ａから順次変更する。しかしながら、このような順に限られるものではなく、あらかじめ決められた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００８３】
次に、ステップ５−３へ進む。
【００８４】
（ステップ５−３）このステップにおいては、ステップ５−２で、１個の部分配線領域の配線方向が変更されたことから、それに伴って、配線方向毎の、選択されたタイルＴが含むことができる配線の最大配線本数（タイル配線可能本数）の値が、変更されることとなる。従って、ステップ４−３で説明したように、再度、最大配線本数を算出する。この算出された値は、更新された最大配線本数として、後で使用するため、データとして格納しておく。次に、ステップ５−４−１へ進む。
【００８５】
（ステップ５−４−１）次に、ステップ５−２において、１個の部分配線領域の配線方向を変更した後、タイルＴのＸ方向の配線がオーバーフローしているかを判定する。その際に用いられる最大配線本数（タイル配線可能本数）は、ステップ５−３で算出されたものを用いる。Ｘ方向の配線がオーバーフローしていない場合には、ステップ５−１へ戻る。一方、Ｘ方向の配線がオーバーフローしている場合には、ステップ５−５へ進む。
【００８６】
（ステップ５−５）ステップ５−４−１において、Ｘ方向の配線がオーバーフローしている場合には、解なしとして、自動配線設計ツールは、エラー出力する。その後、一連の処理は、終了する。
【００８７】
そして、Ｙ方向の配線について、オーバーフローしている旨の判定がなくなるまで、ステップ５−１からステップ５−５を繰り返すのである。このような繰り返しにおいては、先に説明したように、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、このような順に限られるものではなく、あらかじめ決まられた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００８８】
ステップ５−１からステップ５−５を繰り返して、Ｙ方向の配線について、オーバーフローしている旨の判定がなくなった場合には、ステップ３−１へ戻る。
【００８９】
そして、未処理のタイルＴがなくなるまで、ステップ３−１から３−２、ステップ４−１からステップ４−５、ステップ５−１からステップ５−５、を繰り返し、未処理のタイルＴがなくなったら、概略配線の設計を完了し、詳細配線設計を行うためのステップ１−５へ戻る。
【００９０】
以上のようにして、配線設計結果を得ることができる。
【００９１】
従って、このようにすることで、配線層の追加やフロアプランの再検討を伴わず、簡易的に、配線設計を行うことができる。
【００９２】
本実施形態の変形例として、以下のようなものが挙げられる。
【００９３】
本実施形態においては、ステップ３−２において、タイルＴをランダムに１個選択して、その選択したタイルＴについて、オーバーフローしているか否か判定して、処理（配線方向の検討、変更）を行ってきた。それに対して、変形例においては、先に、タイルＴ毎、配線方向毎に、オーバーフローしているかどうかの判定を行い、次に、オーバーフローしていると判定されたタイルＴの中から、一連の処理を行うタイルＴを、選択することもできる。
【００９４】
さらに、先に、タイルＴ毎、配線方向毎に、オーバーフローしているかどうかの判定、及び、最大配線本数（タイル配線可能本数）を超えている配線の本数の算出を行い、最大配線本数を超える配線本数が多い順に、タイルＴを選択して、そのタイルＴに対して一連の処理を行うこともできる。
【００９５】
また、配線設計にかかる時間が長い場合等には、最大配線本数を超える配線本数が多い上位何個のタイルＴのみを選択して、一連の処理を行うこともできる。
【００９６】
（第２の実施形態）
次に、本発明にかかる第２の実施形態を、図７から図１０を用いて、説明する。なお、第１の実施形態と同様のステップについては、説明を省略する。
【００９７】
本実施形態の配線設計方法は、図８のフローチャートで示され、図８中のタイルＴを、後で説明する本実施形態のタイルＴｇに置き換えたものとなる。
【００９８】
本実施形態が、第１の実施形態と異なる点としては、第１の実施形態におけるタイルＴの集合であるタイルＴｇを用いて、配線設計を進めていくことである。これにより、第２の実施形態においては、ステップ２の「タイル分割」が、第１の実施形態のものとは異なることとなる。従って、ここでは、このステップ２の「タイル分割」について、詳細に説明する。なお、以下の説明においては、第１の実施形態におけるタイルをタイルＴとし、本実施形態におけるタイルをタイルＴｇとする。
【００９９】
ステップ２の「タイル分割」を構成するステップを、図９を用いて説明する。図９に示すように、タイルＴｇのタイル配線本数及びタイル配線可能本数を算出するステップにおいては、第１の実施形態におけるタイルＴのタイル配線本数及びタイル配線可能本数を算出するステップ（ステップ２−１、２−２（図６中、Ｓ２−１、Ｓ２−２））に、以下に説明するステップ２−３及びステップ２−４が追加されることとなる。
【０１００】
（ステップ２−３）このステップにおいては、この後の処理で用いられるタイルＴｇを仮想的に形成する。
【０１０１】
図７（ｂ）に示されるように、互いに隣接する所定の数のタイルＴを、集合させて、所定の大きさのタイルＴｇとする。このタイルＴｇを形成するタイルＴの数は、任意に選択することができ、設計者が、基板の面積、配線本数、設計時間等を考慮して、配線自動設計ツールに入力しておく。これによって、各タイルＴｇは、図１０に示されるように、各タイルＴｇに対応する座標を有するものであって各配線層２の一部である部分配線領域２ｂを、複数備えるものとなる。さらに、部分配線領域２ｂは、図２（ｂ）に示される、タイルＴｇを構成する複数のタイルＴに対応する座標を有する各配線層２の一部である複数の部分配線領域２ａ（図２（ｂ）に示す部分配線領域２ａ）が集合したものとなる。
【０１０２】
次に、ステップ２−４へ進む。
【０１０３】
（ステップ２−４）このステップにおいては、各タイルＴｇに含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴｇが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、ステップ２−２で算出されたタイルＴが含む配線の本数（タイル配線本数）、タイルＴが含むことができる最大配線本数（タイル配線可能本数）に基づいて、算出する。
【０１０４】
ここでは、タイルＴｇが含む配線方向毎の配線の本数（タイル配線本数）は、タイルＴのＹ方向（もしくは、Ｘ方向）の配線本数を、行毎（もしくは、列毎）に足したもの（総和）を算出し、その算出された値のうちの最大数とする。さらに、タイルＴｇが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）も、同様に、タイルＴのＹ方向（もしくは、Ｘ方向）の最大配線本数を、行毎（もしくは、列毎）に足したもの（総和）を算出し、その算出された値のうちの最小数とする。
【０１０５】
この算出方法をわかりやすく説明するため、例として、図７（ｂ）に示されるタイルＴｇが含む配線の本数（タイル配線本数）を算出する方法について、以下に説明する。
【０１０６】
図７（ｂ）には、タイルＴが縦４個横４個（以下、このようなタイルＴの配列を４×４と示す。）集合した、タイルＴｇが示されている。図７（ｂ）に示されているタイルＴ内の数字は、ステップ２−２で得られた、各タイルＴが含む、Ｙ方向の配線の本数を示す。また、各タイルＴの行（図７（ｂ）においては、各行に４つのタイルＴがある）の右側に記載された数字は、その行のタイルＴに含まれるＹ方向の配線の本数の総和を示す。例えば、図７（ｂ）における一番上の行については、その行に含まれるＹ方向の配線の本数は、行における配線本数の総和であるから、２＋１＋３＋３＝９本となる。そして、同様に算出すると、各行の総和は、上から、９本、９本、８本、１０本となる。
【０１０７】
さらに、図７（ｂ）に示されるタイルＴｇにおける、Ｙ方向の配線の本数（Ｙ方向タイル配線本数）は、各行のＹ方向の配線の本数の総和のうちの最大値となることから、１０本となる。
【０１０８】
また、各タイルＴｇの、Ｙ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）、Ｘ方向の配線の本数（Ｘ方向タイル配線本数）、Ｘ方向の配線の最大配線本数（Ｘ方向タイル配線可能本数）は、先に説明した方法と同様に算出する。
【０１０９】
ここで算出された配線本数、最大配線本数（タイル配線可能本数）は、データとして格納しておく。次に、ステップ３へ進む。
【０１１０】
以上のようにして、タイルＴｇにおけるタイル配線本数、タイル配線可能本数が算出される。以下、ステップ３の「タイル選択」、ステップ４の「Ｘ方向の配線についての判定／処理」、ステップ５の「Ｙ方向の配線についての判定／処理」については、第１の実施形態のおけるタイルＴを、本実施形態のタイルＴｇに置き換えることで、第１の実施形態と同様に説明することができるため、説明を省略する。
【０１１１】
なお、本実施形態のステップ２では、タイルＴを用いてタイルＴｇを形成する方法について説明したが、タイルＴを用いることなく、タイルＴｇを形成しても良い。
【０１１２】
このように、本実施形態においては、タイルＴが集合したものであるタイルＴｇを用いて配線設計を行うことから、第１の実施形態と比べて、より配線設計にかかる時間を短縮することができる。
【０１１３】
さらに、本実施形態に対しても、第１の実施形態の変形例を適用することは可能である。
【０１１４】
（第３の実施形態）
次に、本発明にかかる第３の実施形態を、図１１、図１２を用いて、説明する。なお、以下の説明においては、第１の実施形態におけるタイルをタイルＴとし、第２の実施形態におけるタイルをタイルＴｇとする。
【０１１５】
本実施形態が、第２の実施形態と異なる点としては、必要に応じて、選択したタイルＴｇをさらに分割して、複数のタイル（２次タイル）Ｔｇ２を形成して、配線設計を進めていくことである。
【０１１６】
本実施形態を説明する前に、このように、タイルＴｇを分割して、複数のタイルＴｇ２を形成することによって、効果的に、配線設計を行うことが可能になることについて、説明する。
【０１１７】
第２の実施形態においては、配線を設計するために、タイルＴｇ毎に、部分配線領域の構成（各タイルＴｇの備える複数の部分配線領域において、Ｘ方向の配線方向を持つ部分配線領域と、Ｙ方向の配線方向を持つ部分配線領域と、の組み合わせ）を決定していた。従って、タイルＴｇのサイズが大きいほど、配線方向が変わる箇所が少なくなるため、配線設計が容易になり、配線設計にかかる時間を短くすることができる。
【０１１８】
しかしながら、以下に示すような例のように、タイルＴｇでは、Ｘ方向の配線、Ｙ方向の配線、ともに、混雑していることから、配線設計の解を得ることができないが、タイルＴｇを分割により小さくすることによって、配線設計の解を得ることができる場合がある。
【０１１９】
以下に、図１１を用いて、このような例について説明する。図１１（ａ）には、タイルＴ（第１の実施形態におけるタイルＴ）が４×４集合して形成した、タイルＴｇ（第２の実施形態におけるタイルＴｇ）が示されている。さらに、このタイルＴｇは、８個の部分配線領域２ｂを、詳細には、Ｘ方向の配線方向を持つ部分配線領域２ｂを４個、Ｙ方向の配線方向を持つ部分配線領域２ｂを４個、備えるものとする。従って、各タイルＴは、Ｘ方向の配線方向を持つ部分配線領域２ａを４個、Ｙ方向の配線方向を持つ部分配線領域２ａを４個、備えることとなる。
【０１２０】
また、ここでは、各部分配線領域が含むことができる配線の最大配線本数を、１本と仮定する。従って、タイルＴの備える部分配線領域２ａの構成から、各タイルＴの含むことができる最大配線本数（タイル配線可能本数）は、Ｘ方向、Ｙ方向、ともに、４本ということになる。さらに、図１１（ａ）に示されるタイルＴｇは、タイルＴを４×４集合したものであることから、第２の実施形態のステップ２−４で説明した方法に従い、タイルＴｇの最大配線本数（タイル配線可能本数）を算出すると、Ｘ方向及びＹ方向の最大配線本数は、ともに、１６本となる。
【０１２１】
ところで、図１１（ａ）に示されるように、タイルＴｇを構成するタイルＴ内に記載された数字は、ステップ１の概略配線の結果から得られた、各タイルＴが含む配線の本数（タイル配線本数）を示すものである。これらの各タイルＴが含む配線の本数に基づいて、第２の実施形態のステップ２−４で説明した方法を用いて、タイルＴｇが含む配線の本数（タイル配線本数）を算出する。その結果、タイルＴｇの含む配線の本数は、Ｘ方向の配線については、１７本、Ｙ方向の配線については、１７本となる。
【０１２２】
従って、タイルＴｇの含むＸ方向の配線の本数（Ｘ方向タイル配線本数）とＹ方向の配線の本数（Ｙ方向タイル配線本数）とが、算出されたタイルＴｇの最大配線本数（タイル配線可能本数）１６本を超えていることから、Ｘ方向、Ｙ方向、どちらの方向の配線についても、オーバーフローしている状況にある。
【０１２３】
すなわち、第２の実施形態で説明した配線設計方法においては、この図１１（ａ）で示されるタイルＴｇに対しては、設計に対する解を得ることができない。
【０１２４】
しかしながら、このような状況にあるタイルＴｇを、さらに、図１１（ｂ）に示すような、タイルＴが２×２で並ぶようなタイルＴｇ２に、分割する。このように、タイルＴｇを分割して４つのタイルＴｇ２を形成した場合、各タイルＴｇ２に含まれる配線の本数（タイル配線本数）は、以下のようになる。すなわち、図１１（ｂ）中の右上、右下、左上、左下、の順に、タイルＴｇ２に含まれる配線の本数を、（Ｘ方向、Ｙ方向）の順に並べると、（１４、３）、（３、３）、（２、１４）、（２、１４）となる。
【０１２５】
さらに、このタイルＴｇ２についての最大配線本数（タイル配線可能本数）を、これまで説明した方法を用いて算出すると、Ｘ方向、Ｙ方向の配線は、ともに、８本である。
【０１２６】
従って、各タイルＴｇ２の状況は、以下のようになる。
【０１２７】
右下のタイルＴｇ２については、配線の本数（タイル配線本数）が（３、３）であることから、Ｘ方向、Ｙ方向、ともに、配線はオーバーフローしている状況ではない。その結果、この右下のタイルＴｇ２については、配線方向を変えることなく、配線設計を行うことができる。
【０１２８】
左上、左下の各タイルＴｇ２については、ともに、配線の本数（タイル配線本数）が（２、１４）であることから、Ｙ方向の配線については、オーバーフローしている状況である。しかしながら、左上、左下の各タイルＴｇ２の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域１個、Ｙ方向の部分配線領域７個」にすることにより、Ｘ方向、Ｙ方向、ともに、配線がオーバーフローする状況を回避することができる。
【０１２９】
右上のタイルＴｇ２については、配線の本数（タイル配線本数）が（１４、３）であることから、Ｘ方向の配線については、オーバーフローしている状況である。そして、この右下のタイルＴｇ２が有する部分配線領域の構成を変更したとしても、配線がオーバーフローする状況を回避することができない。つまり、設計に対する解を得ることができない。
【０１３０】
しかしながら、このような状況にある右下のタイルＴｇ２を、さらに、図１１（ｃ）に示すような、４つのタイルＴｇ３（ここで説明する例においては、タイルＴｇ３はタイルＴと等しい。）に、分割する。このように、タイルＴｇ２を分割して４つのタイルＴｇ３を形成した場合、各タイルＴｇ３に含まれる配線の本数（タイル配線本数）は、以下のようになる。すなわち、図１１（ｃ）中の右上、右下、左上、左下、の順に、タイルＴｇ３に含まれる配線の本数を、（Ｘ方向、Ｙ方向）の順に並べると、（７、１）、（７、１）、（６、２）、（６、２）となる。
【０１３１】
さらに、このタイルＴｇ３についての最大配線本数（タイル配線可能本数）は、先に説明したように、Ｘ方向、Ｙ方向の配線は、ともに、４本である。
【０１３２】
従って、各タイルＴｇ３の状況は、以下のようになる。
【０１３３】
右上、右下のタイルＴｇ３については、ともに、配線の本数（タイル配線本数）が（７、１）であることから、Ｘ方向の配線については、オーバーフローしている状況にある。しかしながら、右上、右下の各タイルＴｇ３の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域７個、Ｙ方向の部分配線領域１個」にすることにより、Ｘ方向、Ｙ方向の配線が、ともに、オーバーフローする状況を回避することができる。
【０１３４】
左上、左下の各タイルＴｇ３については、ともに、配線の本数（タイル配線本数）が（６、２）であることから、Ｘ方向の配線については、オーバーフローしている状況にある。しかしながら、左上、左下の各タイルＴｇ３の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域６個、Ｙ方向の部分配線領域２個」にすることにより、Ｘ方向、Ｙ方向の配線が、ともに、オーバーフローする状況を回避することができる。
【０１３５】
以上のようにして、タイルＴｇをさらに分割して、タイルＴｇ２、タイルＴｇ３を複数形成することによって、効果的に、配線設計を行うことが可能になるのである。
【０１３６】
次に、本実施形態の配線設計方法を説明する。
【０１３７】
本実施形態の配線設計方法は、複数のステップで構成され、これらのステップの流れは、図１２のフローチャートで示される。
【０１３８】
以下に、本実施形態特有のステップのみ、詳細に説明する。
【０１３９】
第１及び第２の実施形態においては、ステップ４−４−１及びステップ５−４−１で、配線がオーバーフローしている状況を回避できない場合には、配線設計の解がないものとして、エラーを出力していた。しかしながら、本実施形態では、このステップで、エラーを出力せずに、次のステップへ進むものとした。すなわち、以下のようなステップとなる。
【０１４０】
（ステップ４−４−２）Ｙ方向の配線がオーバーフローしている場合には、ステップ６−１へ進む。
【０１４１】
（ステップ５−４−２）Ｘ方向の配線がオーバーフローしている場合には、ステップ６−１へ進む。
【０１４２】
さらに、本実施形態においては、以下のようなステップを有する。
【０１４３】
（ステップ６−１）
このステップでは、ステップ３−２で選択されたタイルＴｇが、さらに分割することが可能かどうかを判定する。既に、選択されたタイルＴｇが、タイルＴと同じものである場合には、分割することができない。従って、選択されたタイルＴｇを分割することができる場合には、ステップ６−２へ進む。一方、選択されたタイルＴｇを分割することができない場合には、ステップ６−４へ進む。
【０１４４】
（ステップ６−２）
このステップでは、ステップ２−３で説明した方法と同じように、ステップ３−２で選択されたタイルＴｇを分割して、複数のタイルＴｇ２を形成する。この際、タイルＴｇ２は、所定の数のタイルＴを集合させたものとなり、その数は、設計者が、任意に決めることができる。
【０１４５】
さらに、ステップ２−４で説明した方法と同じように、各タイルＴｇ２に含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴｇ２が含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、算出する。
【０１４６】
次に、ステップ６−３へ進む。
【０１４７】
（ステップ６−３）
このステップでは、ステップ６−２で形成した、複数のタイルＴｇ２を、未処理のタイルとして、登録する。次に、ステップ３−１へ進む。
【０１４８】
以下、第１の実施形態と同様に、複数のタイルＴｇ２を選択し、選択したタイルＴｇ２に対して、Ｘ方向の配線について判定／処理を行い、次いで、Ｙ方向の配線について判定／処理を行う。
【０１４９】
なお、ここでは、Ｘ方向の配線に対して、先に一連の処理を進め、次に、Ｙ方向の配線に対して処理を行う場合について説明したが、順番を入れ替えて、処理を行っても良い。
【０１５０】
（ステップ６−４）ステップ６−１において、タイルＴｇをさらに分割することができないと判定された場合には、ステップ３−２で選択されたタイルＴｇに対する処理を終了して（スキップして）、他のタイルＴｇの処理を行うために、ステップ３−１へ進む。
【０１５１】
このようにして、配線設計結果を得ることができる。
【０１５２】
そして、本実施形態によれば、第２の実施形態にかかる配線設計方法において、設計に対する解を得ることができない場合であっても、配線層の追加やフロアプランの再検討を伴わず、簡易的に、配線設計を行うことができる。従って、配線設計にかかる時間を短縮することができる。さらに、配線方向の変更を、タイル毎に検討することができるため、十分に配線層の配線方向の最適化を図ることができる。
【０１５３】
なお、先に説明した実施形態の配線設計方法は、ソフトウェアで構成することができ、ソフトウェアで構成する場合には、配線設計方法の少なくとも一部を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【０１５４】
また、配線設計方法の少なくとも一部を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【０１５５】
また、本発明は、上記各実施形態に限定されるものではなく、これら以外の各種の形態を採ることができる。すなわち、本発明の趣旨を逸脱しない範囲で適宜変形して実施することができる。
【符号の説明】
【０１５６】
Ａ、Ｂ Ｇセル上の辺
Ｔ、Ｔｇ、Ｔｇ２、Ｔｇ３ タイル
１ 基板
２ 配線層
２ａ、２ｂ 部分配線領域
３ 配線
４ 回路ブロック
５ Ｇセル
【技術分野】
【０００１】
本発明は、基板の配線設計方法及びプログラムに関する。
【背景技術】
【０００２】
半導体集積回路を備える半導体チップや、半導体パッケージの配線基板や、様々な電気機器のプリント回路基板（ＰＣＢ）等の様々な配線基板は、通常、配線が引き回される複数の配線層を備える。
【０００３】
配線の設計時間の短縮のために、自動配線設計ツールにより、自動的に配線を設計する手法が用いられている。これにより、配線の設計にかかる時間を短縮することが可能となる（例えば、特許文献１〜３参照）。
【０００４】
しかしながら、このような自動配線設計ツールにおいては、各配線層における配線方向は、配線層全体に亘り固定されている。すなわち、例えば、第１方向の配線層では、配線層全体（全面）に亘り、配線が延びる方向は第１方向である。
【０００５】
そこで、このような自動配線設計ツールを用いて配線を設計した際に、配線が混雑しているような領域が、配線層上に生じてしまう場合、設計者は、配線設計を行う前の状態に戻って、フロアプランを再検討したり、配線層自体を新たに追加したりすることによって、自動配線設計ツールを用いた配線設計を進めていた。従って、自動配線設計ツールを用いても、設計時間が長期化する傾向を避けることは難しいものであった。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平２−２２２０７２号公報
【特許文献２】特開２００７−２１４３２９号公報
【特許文献３】特開２０００−３１１９４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、配線設計において、簡易的に配線混雑を回避することが可能な配線設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様にかかる配線設計方法は、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、前記基板を複数のタイルに分割し、前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する、ことを備える。
【０００９】
本発明の一態様にかかるプログラムは、コンピュータを、複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行う手段と、前記基板を複数のタイルに分割する手段と、前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成する手段と、前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する手段と、として機能させる。
【発明の効果】
【００１０】
本発明によれば、配線設計において、簡易的に配線混雑を回避することが可能な配線設計方法を提供することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施形態を説明するための図（その１）である。
【図２】第１の実施形態を説明するための図（その２）である。
【図３】第１の実施形態を説明するための図（その３）である。
【図４】第１の実施形態にかかる配線の設計方法を示すフローチャート（その１）である。
【図５】第１の実施形態にかかる配線の設計方法を示すフローチャート（その２）である。
【図６】第１の実施形態にかかる配線の設計方法を示すフローチャート（その３）である。
【図７】第１及び第２の実施形態を説明するための図（その４）である。
【図８】第１の実施形態にかかる配線の設計方法を示すフローチャート（その４）である。
【図９】第２の実施形態にかかる配線の設計方法を示すフローチャートである。
【図１０】第２の実施形態を説明するための図である。
【図１１】第３の実施形態を説明するための図である。
【図１２】第３の実施形態にかかる配線の設計方法を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図を参照して、本発明の実施形態を説明する。この説明に際して、全図面にわたり共通する部分には、共通する符号を付す。ただし、本発明は、この実施形態に限定されるものではない。
【００１３】
また、ここでは、ＬＰＤＤＲ２（Low Power Double Data Rate ２）といった半導体集積回路における、回路ブロック（機能ブロック、論理ブロック等）間を接続する配線の配線設計を例に説明するが、本発明は、このような半導体集積回路に限定されるものではない。
【００１４】
本発明の実施形態について説明する前に、本発明者が本発明をなすに至った経緯について、図１から図３を用いて、以下に説明する。
【００１５】
本発明者は、ＬＰＤＤＲ２等の半導体集積回路を設計していた。ＬＰＤＤＲ２においては、回路ブロックは、細長い長方形、もしくは、細長い長方形を有するＬ字型をしているものが多く、このような回路ブロックの間を接続する配線の設計を行っていたのである。
【００１６】
詳細には、本発明者は、以下のように、配線設計を行っていた。すなわち、図１（ａ）に示されるように、複数の配線層２は互いに重ねられており、複数の回路ブロック４は、配線層２上に配置されており、回路ブロック４の間を接続する配線３は、複数の配線層２に亘って引き回されるものとして設計される。さらに、各配線層２上に配線３が延びることができる方向（配線方向）は、Ｘ方向（横方向）と、Ｙ方向（縦方向）と、定められている。さらに、配線層毎に、配線層全面に亘って、同一の配線方向を有するものとして、定められていた。そして、本発明者は、このような配線層上の配線の設計を、自動配線設計ツールを用いて、行っていたのである。
【００１７】
ところで、このようにして得られた概略配線の設計結果においては、配線層上の特定の領域に、配線が混雑してしまうような状況が生じてしまうことがあった。このような場合、先に説明したように、設計者は、フロアプラン（回路ブロックの配置位置）から再検討したり、配線層を新たに追加したりすることで、配線が混雑する状況を避けていた。
【００１８】
しかしながら、本発明者は、配線設計の結果を分析して、配線層上の特定の領域において、複数の配線が特定の配線方向に偏ることに起因して、配線が混雑する領域が生じると考えていた。すなわち、本発明者は、このような細長い長方形の形状を持つ、回路ブロックどうしを接続する配線について設計を行うと、配線層上の特定の領域に、Ｘ方向、Ｙ方向、いずれかの方向に延びる配線が集中して存在することが多くなり、配線層上の特定の領域に配線が混雑してしまう状況が生じてしまうと、考えていたのである。
【００１９】
さらに、本発明者は、このような状況において、配線層上の配線方向を局所的に変更することにより、言い換えると、配線層の一部領域の配線方向を変更することにより、配線層上の特定の領域に配線が混雑してしまう状況を避けることができるのではないかと考えていた。
【００２０】
また、本発明者は、細長い長方形、もしくは、細長い長方形を有するＬ字型の回路ブロック間を接続する配線の設計においては、配線層上の配線方向を局所的に変更することは、効果的であると、考えていた。
【００２１】
そこで、本発明者は、所定の規則に従って、配線が混雑している配線層上の領域を検出して、その領域の配線方向を変更する、ことを考えたのである。
【００２２】
詳細には、本発明者は、以下のように、配線設計を行うことを考えたのである。まず、基板は、複数の互いに重なった配線層を備え、配線層毎に、配線は、配線層全面に亘って、同一の配線方向に延びるものとして仮決めして、概略配線設計を行う。
【００２３】
なお、概略配線とは、トポロジーと呼ばれるものであり、配線層上の詳細な座標を持つ配線ではなく、図１（ｂ）に示されるような、基板１上に仮想的に形成されたセル５（Ｇセルと呼ばれる）の有する各辺のうち、どの辺を横切るかという事項が定められた配線のことを言う。
【００２４】
次に、図２（ａ）に示されるように、基板１を所定の大きさに仮想的に分割して、複数のタイルＴを仮想的に形成する。これによって、各タイルＴは、図２（ｂ）に示されるように、各タイルＴに対応する座標を有するものであって、各配線層２の一部である部分配線領域２ａを、複数備えるものとなる。
【００２５】
そして、概略配線より算出されたタイルＴの有する配線方向毎の配線３の本数が、所定の数を超えているタイルＴがある場合（オーバーフローしている場合）には、図３に示すように、そのタイルＴの備える複数の部分配線領域２ａの配線方向を、必要に応じて変更する。タイルＴの有する配線方向毎の配線の本数の算出方法については、後述する。
【００２６】
このようにすることで、フロアプランの変更を伴わず、簡易的に、配線設計を行うことができる。従って、配線設計にかかる時間を短縮することができる。
【００２７】
（第１の実施形態）
次に、本発明にかかる第１の実施形態を、図１から図８を用いて、説明する。
【００２８】
ここでは、半導体集積回路の配線設計、詳細には、回路ブロック間の配線の配線設計を例として、説明する。ただし、本発明は、半導体集積回路に限定されるものではなく、半導体パッケージの配線基板や、ＰＣＢボード等にも用いることができる。また、本発明は、回路ブロック間を接続する配線の配線設計に限られるものではなく、その他の配線の配線設計にも用いることができる。
【００２９】
まず、基板及び配線について説明する。基板は、複数の配線層を備える。配線層には、複数の回路ブロックが搭載され、さらに、回路ブロック間を電気的に接続するための複数の配線が、引き回されることとなる。また、これらの配線は、配線層上に延びることができる方向（配線方向）が、限定されている。ここでは、配線方向は、配線層の平面の有する辺とそれぞれ平行である、Ｘ方向（横方向）と、それと直角に交わるＹ方向（縦方向）と、に限定されているものとして、説明する。しかしながら、本発明においては、配線方向は、Ｘ方向とＹ方向とに限定されるものではなく、配線層の平面の有する辺に対して、４５°に傾いた斜め方向を含むものでも良く、すなわち、配線方向が、複数の所定の方向に限定されていれば良い。
【００３０】
次に、本実施形態の配線設計方法を行うための準備について説明する。設計者は、設計の準備として、各回路ブロックの形状及び大きさ、各回路ブロックの接続関係、配線基板上に各回路ブロックをどのように配置するのか（フロアプラン）、を決定する。さらに、これらの情報に基づいて、設計者は、配線層の数と、各配線層における配線方向を、配線層全面に亘って同一の配線方向であると仮定して、決定する。
【００３１】
次に、本実施形態の配線設計方法を説明する。本実施形態の配線設計方法は、概略的には、以下の５つのステップで構成されている。この５つのステップの流れを図４のフローチャートに示す。各ステップは、以下の通りである。
【００３２】
（ステップ１）概略配線設計
（ステップ２）タイル分割
（ステップ３）タイルの選択
（ステップ４）Ｘ方向の配線について判定／処理（配線層の配線方向を局所的に変更する）
（ステップ５）Ｙ方向の配線について判定／処理
なお、ここでは、ステップ４及びステップ５において、先に、Ｘ方向の配線に対して、処理（ステップ４）を進め、次に、Ｙ方向の配線に対して処理（ステップ５）を行う場合について説明するが、順番を入れ替えて、先に、Ｙ方向の配線に対して処理を行い、次に、Ｘ方向の配線に対して処理を行っても良い。
【００３３】
さらに、本実施形態の配線設計方法は、この一連のステップを実施した後に、すべてのタイルに対して処理が施されるまで、ステップ３からステップ５を繰り返す。
【００３４】
また、これらのステップは、詳細には、以下のステップで構成されている。
【００３５】
（ステップ１）
ステップ１の「概略配線設計」を構成するステップを、図５のフローチャートを用いて説明する。以下に説明する、ステップ１にかかる概略配線設計の方法は、一例であり、他の概略配線方法を用いても良い。
【００３６】
（ステップ１−１）配線自動設計ツールに、各回路ブロックの形状及び大きさ、各回路ブロックの接続関係、フロアプラン、配線層の数、各配線層の配線方向等を入力する。次に、ステップ１−２に進む。
【００３７】
（ステップ１−２）次に、配線自動設計ツールを用いて、入力された情報をもとに、概略配線設計を行う。このステップにおいては、概略配線設計を行うために、基板上に仮想的なセル（Ｇセル）を設ける。
【００３８】
詳細には、図１（ｂ）に示されるように、基板１上に、Ｇセル５と呼ばれる仮想的なマス目状のセルを設ける。このＧセル５上のマス目（セル）の大きさは、任意に選択することができ、例えば、基板の面積、配線本数、設計時間等を考慮して、選択することができる。このＧセル５は、概略配線時に、配線混雑度を見積もるために用いられる。
【００３９】
次に、ステップ１−３に進む。
【００４０】
（ステップ１−３）自動配線設計ツールは、これらの入力データに基づいて、図１（ｂ）に示されるように、回路ブロックを接続する配線３が、Ｇセル５の有する辺のうち、どの辺を横切るかを、決定する。つまり、概略配線設計を行う。ここで得られた概略配線の結果は、後で使用するため、データとして格納しておく。次に、ステップ１−４に進む。
【００４１】
（ステップ１−４）Ｇセルの有する各辺を横切る配線の本数（セル配線数Ｎ（ｉ）と呼ぶ）が、適切なものであるかを判定する。
【００４２】
詳細には、Ｇセルの有する各辺に対して、横切ることができる配線の本数（セル配線可能本数Ｍ（ｉ）と呼ぶ）が、デザインルールや配線層の数等に従って、定められている。この値は、あらかじめ、配線自動設計ツールに入力されている。なお、このデザインルールとは、配線層上の配線が守らなくてはならない規則のことであり、例としては、配線同士の間隔が、定められた値以上にしなくてはならないといった規則のことである。
【００４３】
そして、セル配線数Ｎ（ｉ）がセル配線可能本数Ｍ（ｉ）を超えているような辺が、検出されない場合には、ステップ１−５に進む。
【００４４】
一方、セル配線数Ｎ（ｉ）がセル配線可能本数Ｍ（ｉ）を超えているような辺が、検出された場合には、ステップ２−１に進む。
【００４５】
（ステップ１−５）ステップ１−３で得られた概略配線の結果に基づき、詳細配線の設計を行う。詳細配線とは、概略配線の結果に基づき、基板上における詳細な座標が定められた配線のことを言う。詳細配線の設計が完了した後は、配線設計が完了したものとして、一連の処理を終了することとなる。
【００４６】
（ステップ２）
ステップ２の「タイル分割」を構成するステップを、図６のフローチャートを用いて説明する。なお、以下に説明する、ステップ２にかかる複数のタイルの形成方法は、一例であり、他のタイルの形成方法を用いて行っても良い。
【００４７】
（ステップ２−１）基板１に、ステップ１−２で仮想的に形成したＧセルを利用して、次の処理を行うための仮想的なマス目状のタイルを形成する。なお、ここでは、Ｇセルをずらして、仮想的なマス目状のタイルを形成する方法について説明するが、Ｇセルをそのまま用いて仮想的なマス目状のタイルを形成しても良く、Ｇセルを利用することなくタイルを形成しても良い。Ｇセルをそのまま用いてタイルを形成する場合には、例えば、後述するタイル配線本数はセル配線数Ｎ（ｉ）となり、タイル配線可能本数は、セル配線可能本数Ｍ（ｉ）となる。
【００４８】
詳細には、図７（ａ）のように、Ｇセル５のマス目を、Ｘ方向（図７（ａ）中の横方向）、Ｙ方向（図７（ａ）中の縦方向）、ともに、Ｇセル５を、半マス分位相をずらして、タイルＴを形成することとなる新たなマス目を仮想的に形成する。言い換えると、Ｇセル５上の各辺が交わる各点が、各タイルＴの中央に位置するように、タイルＴの輪郭となる新たなマス目を形成する。
【００４９】
詳細には、タイルＴは、Ｘ方向について着目すると、図７（ａ）に示されるように、Ｘ方向に延びるＧセル５上の２つの辺の一部、すなわち、辺Ａの半分と辺Ｂの半分とを含むこととなる。また、Ｙ方向についても、Ｘ方向と同様に、タイルＴは、Ｙ方向に延びるＧセル５上の２つの辺のそれぞれ半分を含むこととなる。
【００５０】
ここでは、この１つのマス目をタイルＴと呼ぶ。この各タイルＴは、図２（ｂ）に示されるように、各タイルＴに対応するものであって各配線層２の一部である部分配線領域２ａを、複数備えるものとなる。
【００５１】
Ｇセルのマス目をずらして、タイルＴを形成することにより、Ｇセルを用いて行われる概略配線の結果を利用して、各タイルＴに含まれる配線の本数を算出することが容易となる。詳細は、後述する。
【００５２】
次に、ステップ２−２へ進む。
【００５３】
（ステップ２−２）このステップにおいて、各タイルＴに含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、算出する。
【００５４】
算出方法をわかりやすく説明するため、例として、図７（ａ）に示されるタイルＴが含む配線の本数（タイル配線本数）の算出と、このタイルＴが含むことができる配線の最大本数（タイル配線可能本数）の算出と、について、説明する。
【００５５】
図７（ａ）に示されるように、タイルＴは、その内部に、Ｘ方向に延びる２つのＧセル５上の辺の一部、すなわち、辺Ａの一部と辺Ｂの一部とを含んでいる。ここでは、例として、ステップ１−３で得られた概略配線の設計結果において、辺Ａを横切るＹ方向の配線の本数（Ｙ方向セル配線数）は、３本とし（Ｎ（Ａ）＝３）、同様に、辺Ｂを通過するＹ方向の配線の本数（Ｙ方向セル配線数）は、４本とする（Ｎ（Ｂ）＝４）。
【００５６】
そして、タイルＴに含まれるＹ方向の配線の本数(Ｙ方向タイル配線本数)は、タイルＴにその一部が含まれるような辺を通過するＹ方向配線の本数（Ｙ方向セル配線数）の総和を、算出し、その値の１／２と仮定する。すなわち、上記の例の場合には、タイルＴに含まれるＹ方向の配線の本数は、｛Ｎ（Ａ）＋Ｎ（Ｂ）｝×１／２となり、図７（ａ）に示されるタイルＴの場合には、（３＋４）×１／２＝３．５本となる。
【００５７】
次に、同様にして、図７（ａ）に示されるタイルＴについて、Ｙ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）を算出する。タイルＴに含まれている辺Ａ及び辺Ｂには、先に説明したように、それぞれ、各辺に対して通過することができる配線の本数（セル配線可能本数）が、配線層の数、及び、配線層の配線方向に応じて、あらかじめ定められている。ここでは、辺Ａのセル配線可能本数をＭ（Ａ）と、辺Ｂのセル配線可能本数をＭ（Ｂ）とする。そして、このような場合、図７（ａ）に示されるタイルＴのＹ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）は、配線本数（Ｙ方向タイル配線本数）の算出と同様に、｛Ｍ（Ａ）＋Ｍ（Ｂ）｝×１／２となる。
【００５８】
また、タイルＴにおける、Ｘ方向の配線の本数（Ｘ方向タイル配線本数）と、Ｘ方向の配線の最大配線本数（Ｘ方向タイル配線可能本数）とについては、これまで説明した方法と同様に算出する。
【００５９】
ここで算出された配線本数（タイル配線本数）、最大配線本数（タイル配線可能本数）は、データとして格納しておく。次に、ステップ３へ進む。
【００６０】
（ステップ３）
ステップ３の「タイルの選択」を構成するステップを、図８のフローチャートを用いて説明する。
【００６１】
（ステップ３−１）これから述べるような処理が行われていないタイルＴが存在するか否かを判定する。この際、未処理のタイルＴが存在していなければ、詳細配線設計を行うステップ１−５へ戻る。一方、未処理のタイルＴが存在していれば、ステップ３−２に進む。
【００６２】
（ステップ３−２）ステップ２で形成された複数のタイルＴのうち、未処理（これから説明するような処理が行われていない）であるタイルＴを１つ選択する。この後、この選択したタイルＴに着目して、一連の処理を行っていく。次に、ステップ４−１へ進む。
【００６３】
（ステップ４）
ステップ４の「Ｘ方向の配線について判定／処理」を構成するステップを、図８のフローチャートを用いて説明する。
【００６４】
（ステップ４−１）ステップ３−２で選択したタイルＴにおいて、Ｘ方向の配線について、オーバーフローしているか否かの判定を行う。
【００６５】
ここでは、１つのタイルＴについて、ステップ２−２で算出されたこのタイルＴが含む配線方向毎の配線本数（タイル配線本数）を、同じくステップ２−２で算出されたこのタイルＴが含むことができる配線方向毎の最大配線本数（タイル配線可能本数）と比較して、この配線本数が最大配線本数よりも大きい場合には、その配線方向の配線は、オーバーフローしていると定義する。
【００６６】
そして、Ｘ方向の配線が、オーバーフローしていない場合には、次に、Ｙ方向の配線について処理を行うため、ステップ５−１へ進む。一方、Ｘ方向の配線が、オーバーフローしている場合には、ステップ４−２へ進む。
【００６７】
（ステップ４−２）このステップでは、ステップ４−１において、Ｘ方向の配線がオーバーフローと判定された場合、選択されたタイルＴの備える複数の部分配線領域２ａのうちの１つを選択して、配線方向を変更する（局所的に配線方向を変更する）。
【００６８】
各タイルＴは、ステップ２で説明したように、図２（ｂ）のような、各タイルＴの座標に対応するものであって各配線層２の一部である部分配線領域２ａを、複数備えている。従って、Ｘ方向の配線が、オーバーフローと判定されたタイルＴの備える複数の部分配線領域２ａのうち、Ｙ方向の配線方向を持つ部分配線領域２ａを１個選択し、その選択した部分配線領域２ａの配線方向を、Ｙ方向からＸ方向に変更するのである。
【００６９】
この際、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、例えば、下の部分配線領域２ａから順次１個選択し、配線方向を変更しても良く、あらかじめ定められた所定の順番に従って部分配線領域２ａを１個選択し、配線方向を変更するものであれば良い。このようにすることで、隣接する他のタイルＴに対する処理も、同様な処理を行うことができ、隣接するタイルＴ同士で、部分配線領域２ａの構成（各タイルＴの備える複数の部分配線領域２ａにおいて、Ｘ方向の配線方向を持つ部分配線領域２ａと、Ｙ方向の配線方向を持つ部分配線領域２ａと、の組み合わせ）が異なるといった状況を、言い換えると、隣接するタイルＴ同士において、隣接する部分配線領域２ａの配線方向が異なるといった状況を、減らすことができる。
【００７０】
次に、ステップ４−３へ進む。
【００７１】
（ステップ４−３）このステップにおいては、ステップ４−２で、１個の部分配線領域の配線方向が変更されたことから、それに伴って、配線方向毎の、選択されたタイルＴが含むことができる配線の最大配線本数（タイル配線可能本数）の値を、変更する。
【００７２】
すなわち、図３を例に挙げて説明すると、タイルＴの備える部分配線領域２ａは６個であり、詳細には、Ｘ方向の配線方向を持つ部分配線領域２ａは３個、Ｙ方向の配線方向を持つ部分配線領域２ａは３個である。さらに、ここでは、１つの部分配線領域２ａは、最大４本の配線を含むことができるものとする。従って、変更前においては、このタイルＴについては、Ｘ方向及びＹ方向の配線ともに、１２本が最大配線本数（タイル配線可能本数）となる。
【００７３】
しかしながら、１つの部分配線領域２ａの配線方向を変更したことから、このタイルＴでは、Ｘ方向の配線方向を持つ部分配線領域２ａは４個、Ｙ方向の配線方向を持つ部分配線領域２ａは２個となる。従って、タイルＴにおいては、Ｘ方向の最大配線本数は１６本、Ｙ方向の最大配線本数は８本となる。すなわち、最大配線本数（タイル配線可能本数）は変更されることとなるのである。
【００７４】
従って、ステップ２−２で説明した手順と同様にして、再度、配線方向毎の、選択されたタイルＴの最大配線本数（タイル配線可能本数）を再度算出することとなる。この算出された値は、更新された最大配線本数として、後で使用するため、データとして格納しておく。次に、ステップ４−４−１へ進む。
【００７５】
（ステップ４−４−１）次に、ステップ４−２において、１個の部分配線領域の配線方向を変更した後、選択されたタイルＴのＹ方向の配線がオーバーフローしているかを判定する。その際に用いられる最大配線本数（タイル配線可能本数）は、ステップ４−３で算出されたものを用いる。Ｙ方向の配線がオーバーフローしていない場合には、ステップ４−１へ戻る。一方、Ｙ方向の配線がオーバーフローしている場合には、ステップ４−５へ進む。
【００７６】
（ステップ４−５）ステップ４−４−１において、Ｙ方向の配線がオーバーフローしている場合には、解なしとして、自動配線設計ツールは、エラー出力する。その後、一連の処理は、終了する。
【００７７】
そして、Ｘ方向の配線について、オーバーフローしている旨の判定がなくなるまで、ステップ４−１からステップ４−５を繰り返すのである。このような繰り返しにおいては、先に説明したように、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、このような順に限られるものではなく、あらかじめ決まられた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００７８】
ステップ４−１からステップ４−５を繰り返して、Ｘ方向の配線について、オーバーフローしている旨の判定がなくなった場合には、ステップ５−１へ進む。
【００７９】
（ステップ５）
ステップ５の「Ｙ方向の配線について判定／処理」を構成するステップを以下に説明する。このステップ５を構成するステップは、ステップ４を構成するステップと同様のものであるため、詳細な説明は、省略する。なお、ステップ５は、図８のフローチャートに示される。
【００８０】
（ステップ５−１）このステップでは、ステップ３−２で選択したタイルＴについて、Ｙ方向の配線について、オーバーフローしているか否かの判定を行う。
この際、ステップ４−３を経ていない場合には、ステップ２−２で算出された最大配線本数（タイル配線可能本数）を、一方、ステップ４−３を経ている場合には、ステップ４−３で更新された最大配線本数を、用いることとなる。
【００８１】
Ｙ方向の配線が、オーバーフローしていない場合には、次に、未処理のタイルＴを選択するために、ステップ３−１へ戻る。一方、Ｙ方向の配線が、オーバーフローしている場合には、ステップ５−２へ進む。
【００８２】
（ステップ５−２）このステップにおいては、ステップ５−１において、Ｙ方向の配線が、オーバーフローしているものと判定された場合、選択されたタイルＴの備える複数の部分配線領域のうち、Ｘ方向の配線方向をもつ部分配線領域の１個を選択して、配線方向を、Ｘ方向からＹ方向に変更するのである。これまでと同様に、例えば、図３に示されるように、上の部分配線領域２ａから順次変更する。しかしながら、このような順に限られるものではなく、あらかじめ決められた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００８３】
次に、ステップ５−３へ進む。
【００８４】
（ステップ５−３）このステップにおいては、ステップ５−２で、１個の部分配線領域の配線方向が変更されたことから、それに伴って、配線方向毎の、選択されたタイルＴが含むことができる配線の最大配線本数（タイル配線可能本数）の値が、変更されることとなる。従って、ステップ４−３で説明したように、再度、最大配線本数を算出する。この算出された値は、更新された最大配線本数として、後で使用するため、データとして格納しておく。次に、ステップ５−４−１へ進む。
【００８５】
（ステップ５−４−１）次に、ステップ５−２において、１個の部分配線領域の配線方向を変更した後、タイルＴのＸ方向の配線がオーバーフローしているかを判定する。その際に用いられる最大配線本数（タイル配線可能本数）は、ステップ５−３で算出されたものを用いる。Ｘ方向の配線がオーバーフローしていない場合には、ステップ５−１へ戻る。一方、Ｘ方向の配線がオーバーフローしている場合には、ステップ５−５へ進む。
【００８６】
（ステップ５−５）ステップ５−４−１において、Ｘ方向の配線がオーバーフローしている場合には、解なしとして、自動配線設計ツールは、エラー出力する。その後、一連の処理は、終了する。
【００８７】
そして、Ｙ方向の配線について、オーバーフローしている旨の判定がなくなるまで、ステップ５−１からステップ５−５を繰り返すのである。このような繰り返しにおいては、先に説明したように、例えば、図３に示されるように、上の部分配線領域２ａから順次１個選択し、配線方向を変更する。しかしながら、このような順に限られるものではなく、あらかじめ決まられた所定の順番に従って部分配線領域２ａの配線方向を変更すれば良い。
【００８８】
ステップ５−１からステップ５−５を繰り返して、Ｙ方向の配線について、オーバーフローしている旨の判定がなくなった場合には、ステップ３−１へ戻る。
【００８９】
そして、未処理のタイルＴがなくなるまで、ステップ３−１から３−２、ステップ４−１からステップ４−５、ステップ５−１からステップ５−５、を繰り返し、未処理のタイルＴがなくなったら、概略配線の設計を完了し、詳細配線設計を行うためのステップ１−５へ戻る。
【００９０】
以上のようにして、配線設計結果を得ることができる。
【００９１】
従って、このようにすることで、配線層の追加やフロアプランの再検討を伴わず、簡易的に、配線設計を行うことができる。
【００９２】
本実施形態の変形例として、以下のようなものが挙げられる。
【００９３】
本実施形態においては、ステップ３−２において、タイルＴをランダムに１個選択して、その選択したタイルＴについて、オーバーフローしているか否か判定して、処理（配線方向の検討、変更）を行ってきた。それに対して、変形例においては、先に、タイルＴ毎、配線方向毎に、オーバーフローしているかどうかの判定を行い、次に、オーバーフローしていると判定されたタイルＴの中から、一連の処理を行うタイルＴを、選択することもできる。
【００９４】
さらに、先に、タイルＴ毎、配線方向毎に、オーバーフローしているかどうかの判定、及び、最大配線本数（タイル配線可能本数）を超えている配線の本数の算出を行い、最大配線本数を超える配線本数が多い順に、タイルＴを選択して、そのタイルＴに対して一連の処理を行うこともできる。
【００９５】
また、配線設計にかかる時間が長い場合等には、最大配線本数を超える配線本数が多い上位何個のタイルＴのみを選択して、一連の処理を行うこともできる。
【００９６】
（第２の実施形態）
次に、本発明にかかる第２の実施形態を、図７から図１０を用いて、説明する。なお、第１の実施形態と同様のステップについては、説明を省略する。
【００９７】
本実施形態の配線設計方法は、図８のフローチャートで示され、図８中のタイルＴを、後で説明する本実施形態のタイルＴｇに置き換えたものとなる。
【００９８】
本実施形態が、第１の実施形態と異なる点としては、第１の実施形態におけるタイルＴの集合であるタイルＴｇを用いて、配線設計を進めていくことである。これにより、第２の実施形態においては、ステップ２の「タイル分割」が、第１の実施形態のものとは異なることとなる。従って、ここでは、このステップ２の「タイル分割」について、詳細に説明する。なお、以下の説明においては、第１の実施形態におけるタイルをタイルＴとし、本実施形態におけるタイルをタイルＴｇとする。
【００９９】
ステップ２の「タイル分割」を構成するステップを、図９を用いて説明する。図９に示すように、タイルＴｇのタイル配線本数及びタイル配線可能本数を算出するステップにおいては、第１の実施形態におけるタイルＴのタイル配線本数及びタイル配線可能本数を算出するステップ（ステップ２−１、２−２（図６中、Ｓ２−１、Ｓ２−２））に、以下に説明するステップ２−３及びステップ２−４が追加されることとなる。
【０１００】
（ステップ２−３）このステップにおいては、この後の処理で用いられるタイルＴｇを仮想的に形成する。
【０１０１】
図７（ｂ）に示されるように、互いに隣接する所定の数のタイルＴを、集合させて、所定の大きさのタイルＴｇとする。このタイルＴｇを形成するタイルＴの数は、任意に選択することができ、設計者が、基板の面積、配線本数、設計時間等を考慮して、配線自動設計ツールに入力しておく。これによって、各タイルＴｇは、図１０に示されるように、各タイルＴｇに対応する座標を有するものであって各配線層２の一部である部分配線領域２ｂを、複数備えるものとなる。さらに、部分配線領域２ｂは、図２（ｂ）に示される、タイルＴｇを構成する複数のタイルＴに対応する座標を有する各配線層２の一部である複数の部分配線領域２ａ（図２（ｂ）に示す部分配線領域２ａ）が集合したものとなる。
【０１０２】
次に、ステップ２−４へ進む。
【０１０３】
（ステップ２−４）このステップにおいては、各タイルＴｇに含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴｇが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、ステップ２−２で算出されたタイルＴが含む配線の本数（タイル配線本数）、タイルＴが含むことができる最大配線本数（タイル配線可能本数）に基づいて、算出する。
【０１０４】
ここでは、タイルＴｇが含む配線方向毎の配線の本数（タイル配線本数）は、タイルＴのＹ方向（もしくは、Ｘ方向）の配線本数を、行毎（もしくは、列毎）に足したもの（総和）を算出し、その算出された値のうちの最大数とする。さらに、タイルＴｇが含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）も、同様に、タイルＴのＹ方向（もしくは、Ｘ方向）の最大配線本数を、行毎（もしくは、列毎）に足したもの（総和）を算出し、その算出された値のうちの最小数とする。
【０１０５】
この算出方法をわかりやすく説明するため、例として、図７（ｂ）に示されるタイルＴｇが含む配線の本数（タイル配線本数）を算出する方法について、以下に説明する。
【０１０６】
図７（ｂ）には、タイルＴが縦４個横４個（以下、このようなタイルＴの配列を４×４と示す。）集合した、タイルＴｇが示されている。図７（ｂ）に示されているタイルＴ内の数字は、ステップ２−２で得られた、各タイルＴが含む、Ｙ方向の配線の本数を示す。また、各タイルＴの行（図７（ｂ）においては、各行に４つのタイルＴがある）の右側に記載された数字は、その行のタイルＴに含まれるＹ方向の配線の本数の総和を示す。例えば、図７（ｂ）における一番上の行については、その行に含まれるＹ方向の配線の本数は、行における配線本数の総和であるから、２＋１＋３＋３＝９本となる。そして、同様に算出すると、各行の総和は、上から、９本、９本、８本、１０本となる。
【０１０７】
さらに、図７（ｂ）に示されるタイルＴｇにおける、Ｙ方向の配線の本数（Ｙ方向タイル配線本数）は、各行のＹ方向の配線の本数の総和のうちの最大値となることから、１０本となる。
【０１０８】
また、各タイルＴｇの、Ｙ方向の配線の最大配線本数（Ｙ方向タイル配線可能本数）、Ｘ方向の配線の本数（Ｘ方向タイル配線本数）、Ｘ方向の配線の最大配線本数（Ｘ方向タイル配線可能本数）は、先に説明した方法と同様に算出する。
【０１０９】
ここで算出された配線本数、最大配線本数（タイル配線可能本数）は、データとして格納しておく。次に、ステップ３へ進む。
【０１１０】
以上のようにして、タイルＴｇにおけるタイル配線本数、タイル配線可能本数が算出される。以下、ステップ３の「タイル選択」、ステップ４の「Ｘ方向の配線についての判定／処理」、ステップ５の「Ｙ方向の配線についての判定／処理」については、第１の実施形態のおけるタイルＴを、本実施形態のタイルＴｇに置き換えることで、第１の実施形態と同様に説明することができるため、説明を省略する。
【０１１１】
なお、本実施形態のステップ２では、タイルＴを用いてタイルＴｇを形成する方法について説明したが、タイルＴを用いることなく、タイルＴｇを形成しても良い。
【０１１２】
このように、本実施形態においては、タイルＴが集合したものであるタイルＴｇを用いて配線設計を行うことから、第１の実施形態と比べて、より配線設計にかかる時間を短縮することができる。
【０１１３】
さらに、本実施形態に対しても、第１の実施形態の変形例を適用することは可能である。
【０１１４】
（第３の実施形態）
次に、本発明にかかる第３の実施形態を、図１１、図１２を用いて、説明する。なお、以下の説明においては、第１の実施形態におけるタイルをタイルＴとし、第２の実施形態におけるタイルをタイルＴｇとする。
【０１１５】
本実施形態が、第２の実施形態と異なる点としては、必要に応じて、選択したタイルＴｇをさらに分割して、複数のタイル（２次タイル）Ｔｇ２を形成して、配線設計を進めていくことである。
【０１１６】
本実施形態を説明する前に、このように、タイルＴｇを分割して、複数のタイルＴｇ２を形成することによって、効果的に、配線設計を行うことが可能になることについて、説明する。
【０１１７】
第２の実施形態においては、配線を設計するために、タイルＴｇ毎に、部分配線領域の構成（各タイルＴｇの備える複数の部分配線領域において、Ｘ方向の配線方向を持つ部分配線領域と、Ｙ方向の配線方向を持つ部分配線領域と、の組み合わせ）を決定していた。従って、タイルＴｇのサイズが大きいほど、配線方向が変わる箇所が少なくなるため、配線設計が容易になり、配線設計にかかる時間を短くすることができる。
【０１１８】
しかしながら、以下に示すような例のように、タイルＴｇでは、Ｘ方向の配線、Ｙ方向の配線、ともに、混雑していることから、配線設計の解を得ることができないが、タイルＴｇを分割により小さくすることによって、配線設計の解を得ることができる場合がある。
【０１１９】
以下に、図１１を用いて、このような例について説明する。図１１（ａ）には、タイルＴ（第１の実施形態におけるタイルＴ）が４×４集合して形成した、タイルＴｇ（第２の実施形態におけるタイルＴｇ）が示されている。さらに、このタイルＴｇは、８個の部分配線領域２ｂを、詳細には、Ｘ方向の配線方向を持つ部分配線領域２ｂを４個、Ｙ方向の配線方向を持つ部分配線領域２ｂを４個、備えるものとする。従って、各タイルＴは、Ｘ方向の配線方向を持つ部分配線領域２ａを４個、Ｙ方向の配線方向を持つ部分配線領域２ａを４個、備えることとなる。
【０１２０】
また、ここでは、各部分配線領域が含むことができる配線の最大配線本数を、１本と仮定する。従って、タイルＴの備える部分配線領域２ａの構成から、各タイルＴの含むことができる最大配線本数（タイル配線可能本数）は、Ｘ方向、Ｙ方向、ともに、４本ということになる。さらに、図１１（ａ）に示されるタイルＴｇは、タイルＴを４×４集合したものであることから、第２の実施形態のステップ２−４で説明した方法に従い、タイルＴｇの最大配線本数（タイル配線可能本数）を算出すると、Ｘ方向及びＹ方向の最大配線本数は、ともに、１６本となる。
【０１２１】
ところで、図１１（ａ）に示されるように、タイルＴｇを構成するタイルＴ内に記載された数字は、ステップ１の概略配線の結果から得られた、各タイルＴが含む配線の本数（タイル配線本数）を示すものである。これらの各タイルＴが含む配線の本数に基づいて、第２の実施形態のステップ２−４で説明した方法を用いて、タイルＴｇが含む配線の本数（タイル配線本数）を算出する。その結果、タイルＴｇの含む配線の本数は、Ｘ方向の配線については、１７本、Ｙ方向の配線については、１７本となる。
【０１２２】
従って、タイルＴｇの含むＸ方向の配線の本数（Ｘ方向タイル配線本数）とＹ方向の配線の本数（Ｙ方向タイル配線本数）とが、算出されたタイルＴｇの最大配線本数（タイル配線可能本数）１６本を超えていることから、Ｘ方向、Ｙ方向、どちらの方向の配線についても、オーバーフローしている状況にある。
【０１２３】
すなわち、第２の実施形態で説明した配線設計方法においては、この図１１（ａ）で示されるタイルＴｇに対しては、設計に対する解を得ることができない。
【０１２４】
しかしながら、このような状況にあるタイルＴｇを、さらに、図１１（ｂ）に示すような、タイルＴが２×２で並ぶようなタイルＴｇ２に、分割する。このように、タイルＴｇを分割して４つのタイルＴｇ２を形成した場合、各タイルＴｇ２に含まれる配線の本数（タイル配線本数）は、以下のようになる。すなわち、図１１（ｂ）中の右上、右下、左上、左下、の順に、タイルＴｇ２に含まれる配線の本数を、（Ｘ方向、Ｙ方向）の順に並べると、（１４、３）、（３、３）、（２、１４）、（２、１４）となる。
【０１２５】
さらに、このタイルＴｇ２についての最大配線本数（タイル配線可能本数）を、これまで説明した方法を用いて算出すると、Ｘ方向、Ｙ方向の配線は、ともに、８本である。
【０１２６】
従って、各タイルＴｇ２の状況は、以下のようになる。
【０１２７】
右下のタイルＴｇ２については、配線の本数（タイル配線本数）が（３、３）であることから、Ｘ方向、Ｙ方向、ともに、配線はオーバーフローしている状況ではない。その結果、この右下のタイルＴｇ２については、配線方向を変えることなく、配線設計を行うことができる。
【０１２８】
左上、左下の各タイルＴｇ２については、ともに、配線の本数（タイル配線本数）が（２、１４）であることから、Ｙ方向の配線については、オーバーフローしている状況である。しかしながら、左上、左下の各タイルＴｇ２の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域１個、Ｙ方向の部分配線領域７個」にすることにより、Ｘ方向、Ｙ方向、ともに、配線がオーバーフローする状況を回避することができる。
【０１２９】
右上のタイルＴｇ２については、配線の本数（タイル配線本数）が（１４、３）であることから、Ｘ方向の配線については、オーバーフローしている状況である。そして、この右下のタイルＴｇ２が有する部分配線領域の構成を変更したとしても、配線がオーバーフローする状況を回避することができない。つまり、設計に対する解を得ることができない。
【０１３０】
しかしながら、このような状況にある右下のタイルＴｇ２を、さらに、図１１（ｃ）に示すような、４つのタイルＴｇ３（ここで説明する例においては、タイルＴｇ３はタイルＴと等しい。）に、分割する。このように、タイルＴｇ２を分割して４つのタイルＴｇ３を形成した場合、各タイルＴｇ３に含まれる配線の本数（タイル配線本数）は、以下のようになる。すなわち、図１１（ｃ）中の右上、右下、左上、左下、の順に、タイルＴｇ３に含まれる配線の本数を、（Ｘ方向、Ｙ方向）の順に並べると、（７、１）、（７、１）、（６、２）、（６、２）となる。
【０１３１】
さらに、このタイルＴｇ３についての最大配線本数（タイル配線可能本数）は、先に説明したように、Ｘ方向、Ｙ方向の配線は、ともに、４本である。
【０１３２】
従って、各タイルＴｇ３の状況は、以下のようになる。
【０１３３】
右上、右下のタイルＴｇ３については、ともに、配線の本数（タイル配線本数）が（７、１）であることから、Ｘ方向の配線については、オーバーフローしている状況にある。しかしながら、右上、右下の各タイルＴｇ３の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域７個、Ｙ方向の部分配線領域１個」にすることにより、Ｘ方向、Ｙ方向の配線が、ともに、オーバーフローする状況を回避することができる。
【０１３４】
左上、左下の各タイルＴｇ３については、ともに、配線の本数（タイル配線本数）が（６、２）であることから、Ｘ方向の配線については、オーバーフローしている状況にある。しかしながら、左上、左下の各タイルＴｇ３の有する部分配線領域の構成を、「Ｘ方向の部分配線領域４個、Ｙ方向の部分配線領域４個」から、「Ｘ方向の部分配線領域６個、Ｙ方向の部分配線領域２個」にすることにより、Ｘ方向、Ｙ方向の配線が、ともに、オーバーフローする状況を回避することができる。
【０１３５】
以上のようにして、タイルＴｇをさらに分割して、タイルＴｇ２、タイルＴｇ３を複数形成することによって、効果的に、配線設計を行うことが可能になるのである。
【０１３６】
次に、本実施形態の配線設計方法を説明する。
【０１３７】
本実施形態の配線設計方法は、複数のステップで構成され、これらのステップの流れは、図１２のフローチャートで示される。
【０１３８】
以下に、本実施形態特有のステップのみ、詳細に説明する。
【０１３９】
第１及び第２の実施形態においては、ステップ４−４−１及びステップ５−４−１で、配線がオーバーフローしている状況を回避できない場合には、配線設計の解がないものとして、エラーを出力していた。しかしながら、本実施形態では、このステップで、エラーを出力せずに、次のステップへ進むものとした。すなわち、以下のようなステップとなる。
【０１４０】
（ステップ４−４−２）Ｙ方向の配線がオーバーフローしている場合には、ステップ６−１へ進む。
【０１４１】
（ステップ５−４−２）Ｘ方向の配線がオーバーフローしている場合には、ステップ６−１へ進む。
【０１４２】
さらに、本実施形態においては、以下のようなステップを有する。
【０１４３】
（ステップ６−１）
このステップでは、ステップ３−２で選択されたタイルＴｇが、さらに分割することが可能かどうかを判定する。既に、選択されたタイルＴｇが、タイルＴと同じものである場合には、分割することができない。従って、選択されたタイルＴｇを分割することができる場合には、ステップ６−２へ進む。一方、選択されたタイルＴｇを分割することができない場合には、ステップ６−４へ進む。
【０１４４】
（ステップ６−２）
このステップでは、ステップ２−３で説明した方法と同じように、ステップ３−２で選択されたタイルＴｇを分割して、複数のタイルＴｇ２を形成する。この際、タイルＴｇ２は、所定の数のタイルＴを集合させたものとなり、その数は、設計者が、任意に決めることができる。
【０１４５】
さらに、ステップ２−４で説明した方法と同じように、各タイルＴｇ２に含まれる配線方向毎の配線の本数（タイル配線本数）、及び、各タイルＴｇ２が含むことができる配線方向毎の配線の最大配線本数（タイル配線可能本数）を、算出する。
【０１４６】
次に、ステップ６−３へ進む。
【０１４７】
（ステップ６−３）
このステップでは、ステップ６−２で形成した、複数のタイルＴｇ２を、未処理のタイルとして、登録する。次に、ステップ３−１へ進む。
【０１４８】
以下、第１の実施形態と同様に、複数のタイルＴｇ２を選択し、選択したタイルＴｇ２に対して、Ｘ方向の配線について判定／処理を行い、次いで、Ｙ方向の配線について判定／処理を行う。
【０１４９】
なお、ここでは、Ｘ方向の配線に対して、先に一連の処理を進め、次に、Ｙ方向の配線に対して処理を行う場合について説明したが、順番を入れ替えて、処理を行っても良い。
【０１５０】
（ステップ６−４）ステップ６−１において、タイルＴｇをさらに分割することができないと判定された場合には、ステップ３−２で選択されたタイルＴｇに対する処理を終了して（スキップして）、他のタイルＴｇの処理を行うために、ステップ３−１へ進む。
【０１５１】
このようにして、配線設計結果を得ることができる。
【０１５２】
そして、本実施形態によれば、第２の実施形態にかかる配線設計方法において、設計に対する解を得ることができない場合であっても、配線層の追加やフロアプランの再検討を伴わず、簡易的に、配線設計を行うことができる。従って、配線設計にかかる時間を短縮することができる。さらに、配線方向の変更を、タイル毎に検討することができるため、十分に配線層の配線方向の最適化を図ることができる。
【０１５３】
なお、先に説明した実施形態の配線設計方法は、ソフトウェアで構成することができ、ソフトウェアで構成する場合には、配線設計方法の少なくとも一部を実現するプログラムをフレキシブルディスクやＣＤ−ＲＯＭ等の記録媒体に収納し、コンピュータに読み込ませて実行させてもよい。記録媒体は、磁気ディスクや光ディスク等の着脱可能なものに限定されず、ハードディスク装置やメモリなどの固定型の記録媒体でもよい。
【０１５４】
また、配線設計方法の少なくとも一部を実現するプログラムを、インターネット等の通信回線（無線通信も含む）を介して頒布してもよい。さらに、同プログラムを暗号化したり、変調をかけたり、圧縮した状態で、インターネット等の有線回線や無線回線を介して、あるいは記録媒体に収納して頒布してもよい。
【０１５５】
また、本発明は、上記各実施形態に限定されるものではなく、これら以外の各種の形態を採ることができる。すなわち、本発明の趣旨を逸脱しない範囲で適宜変形して実施することができる。
【符号の説明】
【０１５６】
Ａ、Ｂ Ｇセル上の辺
Ｔ、Ｔｇ、Ｔｇ２、Ｔｇ３ タイル
１ 基板
２ 配線層
２ａ、２ｂ 部分配線領域
３ 配線
４ 回路ブロック
５ Ｇセル
【特許請求の範囲】
【請求項１】
複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、
前記基板を複数のタイルに分割し、
前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、
前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する、
ことを特徴とする配線設計方法。
【請求項２】
前記タイルは、前記概略配線における配線混雑度を見積もるために、前記基板を格子状に分割したセルと対応する、ことを特徴とする請求項１に記載の配線設計方法。
【請求項３】
前記タイルは、前記概略配線における配線混雑度を見積もるために、前記基板を格子状に分割したセルと対応するタイルの集合である、ことを特徴とする請求項１に記載の配線設計方法。
【請求項４】
前記タイルをさらに複数の２次タイルに分割し、
前記複数の２次タイルに対応するように、前記複数の第１方向配線の部分配線領域及び前記複数の第２方向配線の部分配線領域を分割して、複数の第１方向配線の２次部分配線領域と、複数の第２方向配線の２次部分配線領域と、を形成し、
前記２次タイルにおける第１方向配線がオーバーフローしている場合には、この２次タイルに対応する前記第２方向配線の２次部分配線領域を、第１方向配線の２次部分配線領域に変更する、
ことを特徴とする、請求項３に記載の配線設計方法。
【請求項５】
コンピュータを、
複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行う手段と、
前記基板を複数のタイルに分割する手段と、
前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成する手段と、
前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する手段と、
として機能させるためのプログラム。
【請求項１】
複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行い、
前記基板を複数のタイルに分割し、
前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成し、
前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する、
ことを特徴とする配線設計方法。
【請求項２】
前記タイルは、前記概略配線における配線混雑度を見積もるために、前記基板を格子状に分割したセルと対応する、ことを特徴とする請求項１に記載の配線設計方法。
【請求項３】
前記タイルは、前記概略配線における配線混雑度を見積もるために、前記基板を格子状に分割したセルと対応するタイルの集合である、ことを特徴とする請求項１に記載の配線設計方法。
【請求項４】
前記タイルをさらに複数の２次タイルに分割し、
前記複数の２次タイルに対応するように、前記複数の第１方向配線の部分配線領域及び前記複数の第２方向配線の部分配線領域を分割して、複数の第１方向配線の２次部分配線領域と、複数の第２方向配線の２次部分配線領域と、を形成し、
前記２次タイルにおける第１方向配線がオーバーフローしている場合には、この２次タイルに対応する前記第２方向配線の２次部分配線領域を、第１方向配線の２次部分配線領域に変更する、
ことを特徴とする、請求項３に記載の配線設計方法。
【請求項５】
コンピュータを、
複数の第１方向配線の配線層及び複数の第２方向配線の配線層を備える基板対して概略配線を行う手段と、
前記基板を複数のタイルに分割する手段と、
前記複数のタイルに対応するように、前記複数の第１方向配線の配線層及び前記複数の第２方向配線の配線層を分割して、複数の第１方向配線の部分配線領域と、複数の第２方向配線の部分配線領域と、を形成する手段と、
前記タイルにおける第１方向配線がオーバーフローしている場合には、このタイルに対応する前記第２方向配線の部分配線領域を、第１方向配線の部分配線領域に変更する手段と、
として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−２０４０００（Ｐ２０１１−２０４０００Ａ）
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１０−７０５５９（Ｐ２０１０−７０５５９）
【出願日】平成２２年３月２５日（２０１０．３．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２２年３月２５日（２０１０．３．２５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]