(57)【要約】【課題】Ｘ軸方向に延在する異なる幅を有する複数の配線を、配線領域の幅が最小になるように自動配線する。【解決手段】配線領域をＸ軸に沿って複数のサブ領域に分割し、サブ領域に含まれる配線の配線幅の和をサブ領域の重みとして算出する。この重みが大きなサブ領域に含まれる配線から配線を配置する。配線レイアウトが一つのサブ領域の配線に限定して実行されるので、自動配線の計算量が少ない。また、最も配線領域幅が必要とされるサブ領域からレイアウトするから、他のサブ領域での配線がこの配線領域より広くなることが少なく、配線の再配置の回数が減少する。【選択図】図２
2006253389.tif 000002
【特許請求の範囲】
【請求項１】
配線の対象となる半導体集積回路の入出力領域の延在方向に延在し少なくとも１つの異なる配線幅を有する複数の配線を、該入出力領域の延在方向に沿って設けられた配線領域に配置する配線方法において、
該配線領域を該入出力領域の延在方向に対して垂直となる方向に分割して複数のサブ領域を作成する工程と、
該サブ領域に含まれる該配線の配線幅の和を該サブ領域の重みとして算出する工程と、
該重みが大きなサブ領域から順次、該サブ領域に含まれる該配線を配置する工程とを有することを特徴とする配線方法。
【請求項２】
該配線を配置する工程の前に、任意の該サブ領域に含まれる全ての該配線が他の該サブ領域に含まれるとき、該複数のサブ領域から該任意のサブ領域を除く簡約化工程を有することを特徴とする請求項１記載の配線方法。
【請求項３】
該配線を配置する工程は、該配線を含むサブ領域の数が多い順又は該配線を含むサブ領域の重みの和が大きい順に該配線を順位づけ、該順位の順に配置することを特徴とする請求項１又は２記載の配線方法。
【請求項４】
最大の該重みを該配線領域の幅として設定することを特徴とする請求項１、２又は３記載の配線方法。
【請求項５】
配線の対象となる半導体集積回路の入出力領域の延在方向に延在し少なくとも１つの異なる配線幅を有する複数の配線を、該入出力領域の延在方向に沿って設けられた配線領域に配置する配線装置において、
該配線領域を該入出力領域の延在方向に対して垂直となる方向に分割して複数のサブ領域を作成するサブ領域作成手段と、
該サブ領域に含まれる該配線の配線幅の和を該サブ領域の重みとして算出する重み算出手段と、
該重みが大きなサブ領域から順次、該サブ領域に含まれる該配線を配置する配線配置手段ととを有することを特徴とする配線装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は半導体集積回路の配線レイアウト設計における配線方法に関し、とくに、一方向に延在し、互いに異なる配線幅を有する配線の配線方法及び配線装置に関する。
【背景技術】
【０００２】
アナログ回路を含む半導体集積回路では、異なる幅を有する多数の配線を、配線領域内に互いに平行に配置する場合がある。これを、アナログマクロとＩ／Ｏ（入出力）回路を接続する配線を例に説明する。
【０００３】
図１１は配線レイアトを説明するための平面図であり、デジタル／アナログ回路を混積した半導体集積回路の一部を表している。図１１を参照して、半導体チップ周辺に設けられたＩ／Ｏ（入出力）領域１１にＩ／Ｏ回路３１ａ〜３１ｃが配置され、その近くにアナログマクロ３０が配置されている。本明細書では以下説明の便宜のために、Ｉ／Ｏ領域の延在方向をＸ方向とし、半導体チップ面内にありＸ方向に直交する方向をＹ方向とする。
【０００４】
アナログマクロ３０とＩ／Ｏ回路３１ａ〜３１ｃの間には矩形の配線領域１が設けられており、アナログマクロ３０とＩ／Ｏ回路３１ａ〜３１ｃとは配線領域１内に配置された配線３２ａ〜３２ｃ及び接続用配線３３、３４を介して接続される。即ち、接続用配線３３は、一端がアナログマクロ３０の入出力端子３０ａ〜３０ｄに接続され、他端はＹ方向へ延在してコンタクトホールを介してＸ方向へ延在する配線３２ａ〜３２ｃへ接続される。さらに、配線３２a 〜３２ｃは、その一端に設けられたコンタクトホール３５からＹ方向へ延在する接続用配線３４を介してＩ／Ｏ回路３１ａ〜３１ｃに接続される。このように、アナログマクロ３０とＩ／Ｏ回路３１ａ〜３１ｃはＸ方向に平行に延在する配線３２ａ〜３２ｃを介して接続される。
【０００５】
アナログマクロ３０の入出力配線には、アナログ信号を取り扱うことから非常に異なる電流容量が設定されることが多い。このため、電流容量に対応して設定される配線幅が、各配線毎に異なる場合が多い。また、上述のＸ方向に延在する配線３２ａ〜３２ｃのレイアウトは、検証の容易性を考慮して一層でなさることが好ましい。さらに、アナログ配線の配線長を短縮し、かつ配線領域を縮小する見地から、配線領域１の幅を可能な限り狭くすることが望まれる。
【０００６】
このように、互いに平行に延在する配線幅が異なる多数の配線３２ａ〜３２ｃを、一層の配線領域内に配線領域幅が小さくなるようにレイアウトする方法が必要とされている。しかし、幅が異なる配線をかかるレイアウト条件を満たすように配置する自動配線方法は知られていない。このため、従来は、設計者が試行錯誤により設計していた。
【０００７】
図１２は従来の配線レイアウト工程平面図であり、設計者が試行錯誤により設計する場合に利用できる半自動配線ツールを用いて配置された配線レイアウトを表している。図１５は、レイアウト対象配線表であり、レイアウトすべき配線の配線名と配線幅を表している。なお、図１５中の配線幅は配線幅の最小設計ルールを単位としている。試行錯誤による配線レイアウトでは、まず、図１２（ａ）を参照して、配置すべき全ての配線ａ１〜ｅ１をＸ軸上に配置する。
【０００８】
次いで、左端（Ｘ軸の小さい側）から、配線を選択し、重畳する配線を移動して配置することで配線をレイアウトする。具体的には先ず、図１２（ｂ）を参照して、左端の配線ａ１をそのまま配置する。次に、残りの配線ｂ１〜ｅ１の左端に位置する配線ｂ１を選択する。この配線ｂ１は、配置済みの配線ａ１と重畳するから、配線ａ１と重ならないようにＹ方向に移動して配置する。
【０００９】
次いで、図１２（ｃ）を参照して、残りの配線ｃ１〜ｅ１の左端の配線ｃ１を、他の全ての配線ａ１、ｂ１、ｄ１、ｅ１と重ならないようにＹ方向に移動して、例えばｂ１の上側（Ｙ方向の大きい方向）に配置する。
【００１０】
次いで、配線領域幅が最小になるように配線ａ１〜ｅ１を再配置する。例えば、図１２（ｄ）を参照して、配線ｃ１をＸ軸上に移動し、配線ｄ１、ｅ１を配線ｃ１上に移動する。その結果、配線領域幅が、配線幅＝２の配線ｂ１及び配線ｃ１、配線幅＝４の配線ｄ１の３本の配線ｂ１、ｃ１、ｄ１の配線幅の和８となり、最小の配線領域幅にレイアウトすることができた。
【００１１】
しかし、上述の配線ａ１〜ｅ１の再配置工程では、設計者が試行錯誤を繰り返して最適配置を見いださなければならない。この再配置は、全ての配線を対象としてなされるため、膨大な試行回数が必要であり、実用上は完全なレイアウトを望むことは難しい。従って、通常は設計者の勘と経験から、妥当な配線領域幅になるまで試行されたと判定されたとき、レイアウト工程を打ち切る。
【００１２】
上述した従来の配線レイアウトにおいて、各配線を配線領域幅が最小になるように配置することで設計者の関与を排除することも考えられる。図１３は従来の他の配線レイアウト工程平面図であり、自動配線による配線方法を表している。
【００１３】
この方法では、先ず、図１３（ａ）を参照して、配線ａ１、及び配線ｂ１を上述した図１２（ｃ）と同様に配置する。次いで、配線ｃ１を、この時点で配線領域幅が最小になるように、配線ｂ１の下に配置する。
【００１４】
次いで、図１３（ｂ）を参照して、配線ｄ１を、この時点で配線領域幅が最小になるように、配線ｃ１の下に配置する。次いで、図１３（ｃ）を参照して、配線ｅ１を同様に配置する。
【００１５】
しかし、この方法では、図１３（ｃ）に示されるように配線領域幅は配線ｂ１、ｃ１、ｅ１の配線幅の和９となり、上述した図１２（ｄ）に示される配線幅＝８より大きい。従って、最小配線領域幅とするには全配線を対象とした再配置が必要になる。
【００１６】
狭い配線領域に効率的に配線をレイアウトするため、配線の混雑度を指標とする自動配線方法が知られている（例えば、特許文献１を参照。）。この方法では、配線領域を格子状に区画し、各区画内に配置すべき配線の本数を混雑度とし、最初に最も本数の多い区画を対象として配線をレイアウトする。
【００１７】
この方法によれは、同一幅のデジタル配線のレイアウトでは、配線数が最大の区画で配線領域幅を最小にすることができれば、これと同一の配線領域幅を有する他の区画に配線を配置することができる。なお、配線幅が同一であるから、配線数は配線領域に配置される配線の配線幅の総和に対応する。
【００１８】
しかし、以下に述べるように、この方法を異なる配線幅を有する配線レイアウトに適用することはできない。図１４は、従来の改良された配線レイアウト方法を説明する平面図であり、配線の本数が多い区画からレイアウトする方法を配線幅が異なる配線に適用したときに生ずる問題を表している。なお、配線ａ１〜ｅ１は図１５に示した配線と同じである。
【００１９】
混雑度をある領域（区画）に配置される配線幅の総和としたとき、図１４を参照して、混雑度最大領域４０は３本の配線ｂ１、ｃ１、ｄ１が配置される領域である。従って、レイアウトは混雑度最大領域４０の配線ｂ１、ｃ１、ｄ１を配置することから出発する。例えば、配線ｄ１、配線ｂ１、配線ｃ１をこの順にＹ方向に配置する。次いで、次に混雑度の大きな領域に配置される配線ｅ１を配置する。この配線ｅ１は、混雑度最大領域４０の配線領域幅内に配置することができる。
【００２０】
次いで、３番目に混雑度の大きな領域に配置される配線ａ１を配置する。しかし、この配線ａ１は図１４に示すように、混雑度最大領域４０の配線領域からはみ出してしまう。その結果、配線領域幅は配線ａ１  ｂ１  ｃ１の配線幅の和１０となる。これを最小にするには、配線の再配置を行い、配線ｃ１を配線ｃ１’に移動しなければならない。
【００２１】
なお、かかる再配置の問題は、異なる配線幅の配線レイアウトでは、隣接する配線間に残りの配線を配置することができないスペースを生ずることに起因している。従って、デジタル回路のように配線幅が一定の場合はこの問題は生じない。なぜなら、いかなる配線も隙間なく等間隔で配置することができるので、隣接配線との間に無駄なスペースを生ずることがないからである。
【特許文献１】特開２００１−３４５３８６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
上述したように、従来の自動ないし半自動化された配線方法では、幅の異なる配線のレイアウトにおいて配線領域幅を最小にするには配線の再配置が必要であった。この配線の再配置は全ての配線を考慮して試行錯誤により配置しなければならず、多大の労力を必要とするため実用に適さない。
【００２３】
本発明は、異なる幅の配線を含みかつ一方向に延在する一群の配線を、幅の狭い配線領域に、僅かな再配置の負担でレイアウトすることができる配線方法及び配線装置を提供することを目的とする。
【課題を解決するための手段】
【００２４】
上述の課題を解決するための本発明の配線方法では、配線領域を入出力領域の延在方向（Ｘ軸）に沿って複数のサブ領域に分割し、サブ領域に含まれる配線の配線幅の和を各サブ領域の重みとして算出する。そして、重みが大きなサブ領域の順に各サブ領域に含まれる配線を配置する。
【００２５】
この構成によれば、最初に、重み、すなわち配線幅の和が最大のサブ領域に含まれる配線を配置する。その後、順次、次順の重みのサブ領域の配線を配置する。この構成では、レイアウトで考慮されるべき配線が重みの順で定まる１つのサブ領域に含まれる配線に限定されるから、レイアウト対象となる配線数が少なく、僅かな試行で配線を配置することができので実用的な自動配線が可能となる。さらに、最大の重みを有するサブ領域は最も広い配線領域幅を必要とするから、後に実行される他のサブ領域での配線レイアウトの際に配線領域幅が拡幅される機会が少なくなるので、配線を再配置しなければならない事態を少なくすることができる。
【００２６】
本発明の構成において、配線領域の幅を、最大の重みを有するサブ領域の重み、即ち配線幅の和と設定することができる。配線の配置の際にこの設定を超える配置が発生しなければ、直ちに最小の配線領域幅内に配置されたと確認できるので、最小の配線領域幅内へ自動配線されたことが担保される。
【００２７】
上述した本発明の構成において、任意のサブ領域に含まれる全ての配線が他のサブ領域にも含まれる場合、その任意のサブ領域を除去する（レイアウト操作の対象としない。）簡約化を行なうことができる。ある（他の）サブ領域に含まれる配線の一部が、別の（任意の）領域に完全に含まれる場合、その別の領域の配線を配置すれば、そのあるサブ領域の配線も必然に配置されるから、このあるサブ領域の配線はレイアウトを考慮する必要がなく省略できるからである。この簡約化により、レイアウトの操作対象となるサブ領域を少なくすることができるから、レイアウトがより簡単になる。
【００２８】
一つのサブ領域に含まれる配線を配置する際、配線順序を、延在するサブ領域が多い配線の順に、或いは、延在するサブ領域の重みの和の大きな順に設定することができる。これらの配線は、関与する他の配線が多い、或いは配線が密な（配置される配線幅の和が広い）サブ領域と関連している。これらの配線を先に配置することで、その後に配置される配線は関与する配線が少なく又配線密度が粗な配線となるから、後の配線の際に生ずる配線の再配置を容易にし又は回避することができる。
【００２９】
さらに、配線を配置する際、他のサブ領域にこの配線を配置した場合、最大の重みに相当する幅を有する配線領域内に配置可能か否を検査する配置検証を行なうことができる。そして、配置不能の場合は、配置された配線に代えて次順位の配線を配置する再配置を行なう。これにより、最も適切と予想される配線を先に配置する再配置が自動的に行なわれるので、自動配線において適切な再配置をなすことができる。
【００３０】
本発明の配線装置は、サブ領域作成手段と、重み算出手段と、配線配置手段とを有し、サブ領域作成手段は配線領域を入出力領域の延在方向（Ｘ軸）に対して垂直となる方向に分割して複数のサブ領域を作成し、重み算出手段はサブ領域に含まれる配線の配線幅の和をサブ領域の重みとして算出し、そして、配線配置手段は重みが大きなサブ領域から順次、該サブ領域に含まれる該配線を配置する。
【００３１】
この配線装置は、サブ領域作成手段と、重み算出手段と、配線配置手段とをプラグラムにより実行するコンピュータシステムとして構築することができる。かかる構成の配線装置は、上述した本発明の配線方法を実行することができるので、配線幅の異なる配線を容易に自動的に配置することができる。
【発明の効果】
【００３２】
本発明によれば、一方向に延在し、配線幅が異なる配線を含む一群の配線の配線順序を、自動的にかつ配線幅が小さくなるように順序づけることができるので自動配線が容易にであり、また再配置の必要がない又は少ない自動配線方法及びかかる配線方法を実行する配線装置を提供することができる。
【発明を実施するための最良の形態】
【００３３】
図１は本発明の第１実施形態配線レイアウト工程平面図であり、配線パターンを表している。図２は本発明の第１実施形態フローチャートである。
【００３４】
本実施形態に係る配線は、図１５に示した従来例と同一である。本実施形態では、図２を参照して、２つの工程群に分けられる。前半の工程群は、サブ領域の設定（工程Ｓ１）から配線テーブル４の作成（工程Ｓ５）に至る工程であり、主として本発明を適用するための準備工程であり、通常は一回のみ実行される。後半の工程群は、配線領域の決定（工程Ｓ６）から最高順位の配線を配置し（工程Ｓ９）、全てのサブ領域の配線を終了する（工程１２）に至る繰り返しルーチンを含む工程であり、具体的な配線の配置工程である。
【００３５】
初めに、前半のＳ１〜Ｓ５の工程を説明する。まず、図２の工程Ｓ１（サブ領域作成手段）では、図１（ａ）を参照して、配線領域１が延在するＸ方向に延在する配線ａ１〜ｅ１をＸ軸上に配置し、各配線の左端及び右端によりＸ軸を区分してサブ領域Ａ１〜Ｇ１を作成する。なお、配線ａ１〜ｅ１はこれからレイアウトの対象となる配線であり、表１５に示す配線幅を有している。
【００３６】
次いで、図２の工程Ｓ２（重み算出手段）では各サブ領域Ａ１〜Ｇ１の重みを算出する。図３は本発明の第１実施形態重みの説明図であり、各サブ領域における重みの算出方法を表している。図３を参照して、サブ領域Ａ１〜Ｇ１の各サブ領域ごとにそのサブ領域に含まれる配線を抽出する。例えば、サブ領域Ａ１には配線ａ１が、サブ領域Ｂ１には配線ａ１及び配線ｂ１が、以下同様にして、最後にサブ領域Ｇ１には配線ｃ１及び配線ｅ１が抽出される。次に、一つのサブ領域に含まれる配線の配線幅を加算し、加算により得られた配線幅の和を重みとする。この重みの算出は各サブ領域について行なわれる。
【００３７】
次いで、図２の工程Ｓ３では簡約化を行なう。簡約化は、図３を参照して、あるサブ領域に含まれる配線の全部が他の１つのサブ領域に含まれる場合、そのあるサブ領域をレイアウトの対象から除外することでなされる。例えば、サブ領域Ａ１に含まれる配線ａ１はサブ領域Ｂ１にも含まれるから、サブ領域Ａ１は除外される。サブ領域Ｂ１に含まれる配線ａ１、ｂ１は、他に配線ａ１及びｂ１を含むサブ領域がないから除外されない。このようにして、サブ領域Ｃ１、Ｄ１及びＦ１も除外される。その結果、除外されずに残った 3個のサブ領域Ｂ１、Ｅ１及びＧ１がレイアウト対象となる。このように、簡約化をすることでレイアウト対象となるサブ領域を減少することができる。
【００３８】
次いで、図２の工程Ｓ４及び工程Ｓ５では、それぞれ領域テーブル３及び配線テーブル４を作成する。図４は本発明の第１実施形態領域テーブル及び配線テーブルであり、これらのテーブルの記載内容と両テーブル間の関連を表している。
【００３９】
領域テーブル３には、サブ領域名を表す領域名、各サブ領域の重み、及び各サブ領域に含まれる配線のアドレス（配線テーブル４のアドレスの意である。）が含まれる。配線テーブル４には、配線名、その配線が延在するサブ領域のアドレス（領域テーブル３のアドレスの意である。）及び寄与度が含まれる。この寄与度は、配線が延在するサブ領域の重みの和であり、例えば配線ｂ１は重み８のサブ領域Ｂ１及び重み８のサブ領域Ｅ１に延在しており、その寄与度は両方のサブ領域Ｂ１、Ｅ１の重みの和１６となる。この寄与度は、配線が他の配線のレイアウトと関連する程度の指標となるもので、レイアウト密度の高いサブ領域と多く関係する程高くなる。さらに、領域テーブル３には、サブ領域に含まれる配線の寄与度をそのサブ領域に含まれる全ての配線について加算した寄与度の和が記載される。この、寄与度の和は、サブ領域内の配線が他のサブ領域と関連する程度を表している。
【００４０】
次に、後半のＳ６〜Ｓ１２（配線配置手段）の工程について説明する。まず、図２の工程Ｓ６では、配線領域幅を決定する。本第１の実施形態では、図４の領域テーブル３から最大の重み８（サブ領域Ｂ１及びＥ１の重み）を抽出し、これを配線領域幅と決定する。サブ領域Ｂ１に含まれる配線ａ１  ｂ１又はサブ領域Ｅ１に含まれる配線ｂ１、ｃ１、ｄ１を最密に配置したとき、配線幅がこの重み８に相当する。従って、重み８は実現可能な最も狭い配線領域幅を表している。即ち、幅が重み８の配線領域内に配線を配置可能ならば、この配置が最も狭い配線領域を与えることが担保される。
【００４１】
次いで、図２の工程Ｓ７では、最初のレイアウト操作対象となるサブ領域を決定するため、重み最大のサブ領域を選択する。即ち、図４の領域テーブル３から最大の重み８を有するサブ領域Ｂ１及びサブ領域Ｅ１を選択する。このように同一重みを有する同順位のサブ領域が複数あるときは、これらのサブ領域に含まれる配線の寄与度の和の大きい順から選択する。従って、寄与度の和が３９のサブ領域Ｅ１が選択される。このように選択することで、他のサブ領域と最も密接に関連する配線を含むサブ領域からレイアウトを決定することができる。従って、後に他のサブ領域にレイアウトされる配線との干渉が少なくなり、再配置が必要となる事態の発生が抑制される。なお、配線の寄与度の和の代わりに、含まれる配線の数が多い順、又は最も寄与度の高い配線を含むサブ領域の順に選択することもできる。
【００４２】
次いで、図２の工程Ｓ８では、選択されたサブ領域Ｅ１の配線レイアウトにおける配線を配置する順位を決定する。この配線の配置する順位（以下「配線順位」という。）は、以下のようにして決定される。
【００４３】
先ず、図４を参照して、選択されたサブ領域Ｅ１に含まれる配線ｂ１、ｃ１、ｄ１のアドレスを領域テーブル３から参照して配線テーブル４を検索し、最も寄与度の高い配線ｂ１を抽出して順位１とする。以下同様に寄与度の高い順に配線ｃ１、配線ｄ１をそれぞれ順位２、順位３とする。この寄与度に代えて、配線が延在するサブ領域の数の順、又は配線が延在するサブ領域の重みの順とすることもできる。必要ならば、Ｘ軸の左端に近い配線の順（本実施形態ではａ１、ｂ１・・・の順）とすることもできる。
【００４４】
次いで、図２の工程Ｓ９では、図１（ｂ）を参照して、工程Ｓ８で決定された順位１の配線ｂ１をＸ軸上に配置する。次いで、工程Ｓ１０の配置可能性の検証を行なう。この配置可能性検証は、配線ｂ１を配置したとき、この配線ｂ１を配置しても他のサブ領域でレイアウトが可能か否かを検証する。検証されるべきサブ領域は、配線ｂ１が延在するサブ領域Ｂ１であり配線テーブル４から検索される。
【００４５】
検証は、図１（ｂ）を参照して、検証すべきサブ領域Ｂ１に含まれる全ての配線、即ち配線ｂ１及び配線ａ１を配置する。これらの配線ａ１、ｂ１が、工程Ｓ６で決定された配線領域幅＝８内に配置される場合は配置可能と判定される。仮に、配線ａ１、ｂ１を配置すると配線領域幅＝８を超える場合は、配線不能と判定され、工程Ｓ２０が実行される。本実施形態では、図１（ｂ）から明らかに配置可能と判定される。次いで、この検証で配置された配線ａ１を取り除く。なお、後の工程で支障がなければこのまま残すこともできる。
【００４６】
次いで、工程Ｓ１１では、現在のレイアウト対象とされているサブ領域Ｅ１内にある未配置の配線の有無を調べ、無い場合はサブ領域Ｅ１の配線レイアウトが終了したとして次の工程Ｓ１２を実行する。工程Ｓ１２では、レイアウトがされていないサブ領域の有無を調べ、ある場合は工程Ｓ７に戻り、工程Ｓ７以降を繰り返す。このとき、レイアウトが終了しているサブ領域及び配線をレイアウト対象から除外し、残りのサブ領域及び配線に対して工程Ｓ７以降を実行する。無い場合は全てのサブ領域のレイアウトが完了したとして自動配線工程を終了する。
【００４７】
工程Ｓ１１でサブ領域Ｅ１内に未配置の配線が有ると判定された場合、工程Ｓ９以降を実行する。本実施形態では、配線ｂ１の配置した直後は領域Ｅ１に未配置の配線ｃ１及びｄ１が残されているから、工程Ｓ１１で未配置の配線が有ると判定され、工程Ｓ９を実行する。このとき、レイアウト済みの配線は対象から除外する。
【００４８】
再度の工程Ｓ９では、領域Ｅ１の未配置の配線ｃ１、ｄ１から寄与度が大きな配線ｃ１を、最高順位の配線として配置する。配線ｃ１は、図２（ｃ）を参照して、配線ｂ１の上側（Ｙ方向）に配置される。
【００４９】
次いで、工程Ｓ１０において配線ｃ１の配置可能性が検証される。この検証は、配線ｃ１が延在するサブ領域Ｇ１に対してなされる。即ち、図２（ｃ）を参照して、サブ領域Ｇ１に含まれる配線ｅ１を配線ｃ１の上側に配置する。その結果、配線領域幅は配線ｂ１、ｃ１、ｅ１を加算した幅＝９となり、工程Ｓ６で設定された配線領域幅＝８を超える。従って、配線ｃ１の配置可能性が否定される。この否定された配線ｃ１は取り除かれ、この時点では配置されない。
【００５０】
配置可能性が否定されると工程Ｓ２０以降の再配置工程が実行される。工程Ｓ２０では、先ず工程Ｓ２０１で配線順位の入れ替えが行なわれる。即ち、サブ領域Ｅ１の未配置配線ｃ１、ｄ１のうち、配置可能性が否定された配線ｃ１と、次の順位を有する配線ｄ１との順位を入れ替える。
【００５１】
次いで、工程Ｓ９に戻り、図１（ｄ）を参照して、残された未配線ｃ１、ｄ１のうち最高順位となった配線ｄ１を配線ｂ１の上側に配置する。この配線ｄ１は、他のサブ領域に延在しないから、工程Ｓ１０で配線可能性は必ず肯定される。次いで工程Ｓ１１を経て工程Ｓ９に戻り、図１（ｄ）を参照して、残りの未配線ｃ１が配線ｄ１の上側に配置される。
【００５２】
配置された配線ｃ１の配線可能性は、工程１０により再び検証される。図１（ｄ）に示すように、この配線レイアウトではサブ領域Ｇ１の全ての配線ｃ１及びｅ１が配線領域幅＝８以内に配置されており、配線ｃ１は配置可能と判定される。
【００５３】
この結果、工程Ｓ１１でサブ領域Ｅ１に含まれる全ての配線の配置が完了したと判定され、工程Ｓ１２を経て、工程Ｓ７に戻される。
【００５４】
工程Ｓ７では、残りのサブ領域Ｂ１及びＧ１のうち重みが大きいサブ領域Ｂ１を、レイアウト操作の対象として選択する。次いで、工程Ｓ８で、サブ領域Ｂ１に含まれる残りの配線ａ１を最高順位として（寄与度が最大の配線として）選択し、配置する。図１（ｅ）に配置された配線ａ１を示す。なお、配線ｂ１の配置後の配置可能性が検証されたのち、配線ａ１をそのまま残した場合はこの配線ａ１の配置工程は不要である。配線ａ１はサブ領域Ｂ１以外に延在しないので、必ず工程Ｓ１０で配置可能と判定される。
【００５５】
その後、工程Ｓ１１、Ｓ12を経て、工程Ｓ７に戻され、残りのサブ領域Ｅ１の配線レイアウトが実行される。サブ領域Ｅ１には残りの配線ｅ１があり、これは図１（ｅ）に示すように配線領域幅＝８の配線領域内に配置される。この配線ｅ１の配置工程は、図（ｄ）に示す先の配線ｃ１の配置可能性の検証時の位置にそのまま残されている場合は省略することができる。以上の工程を経て全ての配線が配置され、自動配線方法によるレイアウトが完了する。なお、レイアウト対象とされなかったサブ領域Ａ１、Ｃ１、Ｄ１、Ｆ１については、上記の工程で何ら考慮を払うことなく自動的に配線が完了している。
【００５６】
上記の工程Ｓ２０から始まる配線の再配置工程において、配線領域の幅が工程Ｓ６で設定された配線領域に入らない場合、それ以上自動配線を続行することができない。かかる場合、再配置工程で作成された配線領域が当初の配線領域幅より増加しても、その増加が許容し得る程度の拡幅ならば、配線領域幅を変更して続行することが望ましい。そのため、工程Ｓ２０からＳ１０において再配置不能となったとき、あるいは、再配置に伴う計算量が所定値を超えたとき、アラームを送出して配線領域幅の再設定を促すことが好ましい。
【００５７】
以下、本発明の第２実施形態について説明する。第２実施形態形態は、配線のレイアウト順をその配線が延在する領域の数で決定している。
【００５８】
図５は本発明の第２実施形態配線レイアウト平面図であり、レイアウトすべき配線の最終形態の一例を表している。図６は本発明の第２実施形態レイアウト対象配線表であり、図５に示すレイアウトされるべき配線の配線幅を表している。
【００５９】
本第２実施形態の配線レイアウトにおけるフローチャートは、工程Ｓ８の配線順位の決定方法を除いて図２に図示した第１実施形態のフローチャートと同様である。従って、説明を簡明にするため図２の工程を引用しつつ説明する。
【００６０】
まず、図５に示すように、Ｘ軸にそってサブ領域Ａ〜Ｉを設定する。このサブ領域Ａ〜Ｉは、第１実施形態と同様に配線ａ〜ｉの端面で区分される。次いで、第１実施形態工程Ｓ２、Ｓ３と同様にして、重みを算出し、さらに簡約化を行なった。図７は本発明の第２実施形態重みの説明図である。図７を参照して、サブ領域Ｂ、Ｄ、Ｆ、Ｈは簡約化によりレイアウト対象から除外される。
【００６１】
次いで、工程Ｓ４、Ｓ５と同様にして、領域テーブル５及び配線テーブル６を作成する。図８は本発明の第２実施形態領域テーブル及び配線テーブルである。なお、第１実施形態と異なり、寄与度の和及び寄与度は算出していない。
【００６２】
次いで、工程Ｓ６で最大の重み＝１２に対応する配線領域幅を設定する。次いで、工程Ｓ７及びＳ８で、領域テーブル５から重みが最大のサブ領域Ｅを選択し、選択されたサブ領域Ｅに含まれる配線ｂ、ｃ、ｅ、ｆ、ｇの配線順位を決定する。配線順位は、配線テーブル６を参照してその配線が延在するサブ領域の数が多い順とした。この順位が同順の場合は、配線名の登録順、即ち配線名のアルファベット順とした。その結果、配線順位は、配線ｂ、ｇは延在するサブ領域数が３個でアルファベット順に配線ｂが１位、配線ｇが２位、配線ｃ、ｆは延在するサブ領域数が２個でアルファベット順に配線ｃが 3位、配線ｆが４位、配線ｅは延在するサブ領域数が１個で５位となる。
【００６３】
次いで、工程９で順位１位の配線ｂをＸ軸上に配置する。図９及び図１０はそれぞれ本発明の第2 実施形態形態配線レイアウト工程平面図（その１）及び（その２）であり、配線の配置を表している。
【００６４】
次いで、工程１０で配線ｂの配置可能性を検証する。図９（ａ）を参照して、配線ｂが延在するサブ領域Ａ、Ｃに含まれる配線ａ、ｃ、ｄを配線ｂと共に配置し、設定された配線領域幅＝１２に配置できることが検証される。
【００６５】
次いで、工程Ｓ１１を経て工程９に戻り、残りの最高順位の配線ｇを配置し、さらに工程Ｓ１０でその配置可能性を検証する。図９（ｂ）を参照して、配線ｇが延在するサブ領域Ｇ、Ｉに含まれる配線ｆ、ｈ、ｉを配線ｂ、ｇと共に配置すると、領域Ｉでは配線幅が１３となり、設定された配線領域内に配置不能となり、配線ｇの配置可能性が否定される。このため、工程２０を経る再配置工程が開始される。
【００６６】
工程２０では、配線ｇと次順位の配線ｃの順位を入れ替え、工程Ｓ９で配線ｃを配置したのち、配線ｃの配置可能性を検証する。図１０（ｃ）を参照して、配線ｃが延在するサブ領域Ｃに含まれる配線ｂ、ｃ、ｄが設定領域幅内に配置できたので、配線ｃの配置可能性は肯定される。従って、次の工程Ｓ１１を実行して工程９へ戻り、残りの最高順位の配線ｇを配置したのち、工程Ｓ１０で配線ｇの配置可能性を検証する。
【００６７】
図１０（ｃ）を参照して、配線ｇが延在するサブ領域Ｉでの配置可能性が否定されるので、再び工程２０に移行し配線ｇと次順位の配線ｆとを入れ替える再配置を行なう。図１０（ｄ）を参照して、配線ｆを配置したとき、配線ｆが延在するサブ領域Ｇに配線ｈを配置すると配線幅が設定した配線領域幅を超えるので、配線ｆの配置可能性が否定されている。
【００６８】
同様にして、配線ｆを配線ｅに代えて配置し（配線ｅは配置可能である。）、残りの配線ｆ、ｇについて同様の再配置工程を繰り返すと、図１０（ｅ）を参照して、先に配線ｆが配置可能となり、その後配線ｇが配置可能となる。これにより、サブ領域Ｅの配線の配置が完了する。
【００６９】
次に、重みが１１のサブ領域Ａ、Ｉをアルファベット順にサブ領域Ａ、サブ領域Ｉの順に選択し、それぞれ残りの配線ａ、配線ｉを配置する。なお、これらの配線はさきになされた検証工程で配置可能性が保証されている。続いて、重みが１０のサブ領域Ｃ、Ｇ内の残りの配線ｄ、ｈを同様の手順で配置する。その結果、図５に示した配線の配置が確定する。
【００７０】
本第１及び第2 の実施形態により自動配線された配線レイアウトは、可能な最小幅の配線領域内でレイアウトされたことが担保されている。
【００７１】
上述した本明細書には以下の付記記載の発明が開示されている。
（付記１）
配線の対象となる半導体集積回路の入出力領域の延在方向に延在し少なくとも１つの異なる配線幅を有する複数の配線を、該入出力領域の延在方向に沿って設けられた配線領域に配置する配線方法において、
該配線領域を該入出力領域の延在方向に対して垂直となる方向に分割して複数のサブ領域を作成する工程と、
該サブ領域に含まれる該配線の配線幅の和を該サブ領域の重みとして算出する工程と、
該重みが大きなサブ領域から順次、該サブ領域に含まれる該配線を配置する工程とを有することを特徴とする配線方法。
（付記２）
該配線を配置する工程の前に、任意の該サブ領域に含まれる全ての該配線が他の該サブ領域に含まれるとき、該複数のサブ領域から該任意のサブ領域を除く簡約化工程を有することを特徴とする付記１記載の配線方法。
（付記３）
該配線を配置する工程は、該配線を含むサブ領域の数が多い順又は該配線を含むサブ領域の重みの和が大きい順に該配線を順位づけ、該順位の順に配置することを特徴とする付記１又は２記載の配線方法。
（付記４）
一つのサブ領域に含まれる該配線の一つを配置したのち、最大の該重みの幅を有する該配線領域内に他のサブ領域に含まれる残りの該配線を配置可能か否を検査する配置検証工程と、
配置不能と判定された場合に、該配置された配線に代えて次順位の配線を配置する再配置工程とを有することを特徴とする付記３記載の配線方法。
（付記５）
最大の該重みを該配線領域の幅として設定することを特徴とする付記１、２又は３記載の配線方法。
（付記６）
該配線が延在するサブ領域の重みの和を各配線毎に算出する工程と、
該配線が延在するサブ領域の重みの和を、サブ領域に含まれる全ての該配線について加算した積算値を算出する工程と、
該重みが同一の該サブ領域に対して、該積算値の大きい該サブ領域の順に配線を配置する工程とを有することを特徴とする付記１〜５の何れか１つに記載された配線方法。
（付記７）
該重みが同一の該サブ領域に対して、該重みが同一の該サブ領域に含まれる配線が延在する該サブ領域の数が多い順に配線を配置することを特徴とする付記１〜５の何れか１つに記載された配線方法。
（付記８）
配線の対象となる半導体集積回路の入出力領域の延在方向に延在し少なくとも１つの異なる配線幅を有する複数の配線を、該入出力領域の延在方向に沿って設けられた配線領域に配置する配線装置において、
該配線領域を該入出力領域の延在方向に対して垂直となる方向に分割して複数のサブ領域を作成するサブ領域作成手段と、
該サブ領域に含まれる該配線の配線幅の和を該サブ領域の重みとして算出する重み算出手段と、
該重みが大きなサブ領域から順次、該サブ領域に含まれる該配線を配置する配線配置手段ととを有することを特徴とする配線装置。
【産業上の利用可能性】
【００７２】
本発明によれば、自動配線により、互いに平行な配線幅が異なる配線を、容易に最小幅の配線領域内に配置することができるので、集積回路の設計が容易になり半導体装置の特性向上に寄与するところが大きい。
【図面の簡単な説明】
【００７３】
【図１】本発明の第１実施形態配線レイアウト工程平面図
【図２】本発明の第１実施形態フローチャート
【図３】本発明の第１実施形態重みの説明図
【図４】本発明の第１実施形態領域テーブル及び配線テーブル
【図５】本発明の第２実施形態配線レイアウト平面図
【図６】本発明の第２実施形態レイアウト対象配線表
【図７】本発明の第２実施形態重みの説明図
【図８】本発明の第２実施形態領域テーブル及び配線テーブル
【図９】本発明の第２実施形態配線レイアウト工程平面図（その１）
【図１０】本発明の第２実施形態配線レイアウト工程平面図（その２）
【図１１】配線レイアトを説明するための平面図
【図１２】従来の配線レイアウト工程平面図
【図１３】従来の他の配線レイアウト工程平面図
【図１４】従来の改良された配線レイアウト方法を説明する平面図
【図１５】レイアウト対象配線表
【符号の説明】
【００７４】
１  配線領域
２  サブ領域
３、５  領域テーブル
４、６  配線テーブル
３０  アナログマクロ
３０ａ〜３０ｄ  入出力端子
３１ａ〜３１ｃ  Ｉ／Ｏ回路
３２ａ〜３２ｃ、ａ１〜ｅ１  配線
３３、３４  接続用配線
３５  コンタクトホール
４０  混雑度最大領域
Ａ〜Ｉ、Ａ１〜Ｇ１  サブ領域
ａ〜ｉ、ａ１〜ｅ１  配線
【図１】
2006253389.tif 000003
【図２】
2006253389.tif 000004
【図３】
2006253389.tif 000005
【図４】
2006253389.tif 000006
【図５】
2006253389.tif 000007
【図６】
2006253389.tif 000008
【図７】
2006253389.tif 000009
【図８】
2006253389.tif 000010
【図９】
2006253389.tif 000011
【図１０】
2006253389.tif 000012
【図１１】
2006253389.tif 000013
【図１２】
2006253389.tif 000014
【図１３】
2006253389.tif 000015
【図１４】
2006253389.tif 000016
【図１５】
2006253389.tif 000017