(57)【要約】【課題】半導体集積回路のレイアウト設計におけるイタレーションを抑止し、設計効率を向上する。【解決手段】レイアウト設計装置は、半導体集積回路の第１の領域に配線可能な配線リソースを算出する配線リソース算出部１と、複数のセルを当該セルのサイズに基づいて第１の領域に配置するセル配置部２と、セルの接続情報に基づいて、第１の領域に配置した複数のセルのネット接続コストを算出するネット接続コスト算出部３と、第１の領域においてネット接続コストに対し配線リソースが不足している場合、第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与する仮想拡張領域付与部４と、付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを第１の領域に再配置するセル再配置部５と、を備える。【選択図】図１
2014089499.tif 000002
【特許請求の範囲】
【請求項１】
入力されたネットリストに基づいて、半導体集積回路の第１の領域に配線可能な配線リソースを算出し、
前記ネットリストに含まれる複数のセルを当該セルのサイズに基づいて前記第１の領域に配置し、
前記ネットリストに含まれるセルの接続情報に基づいて、前記第１の領域に配置した複数のセルの接続度合いを示すネット接続コストを算出し、
前記第１の領域において前記ネット接続コストに対し前記配線リソースが不足している場合、当該第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与し、
前記付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを前記第１の領域に再配置する、
半導体集積回路のレイアウト設計方法。
【請求項２】
前記第１の領域は、前記半導体集積回路全体の配置領域である、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項３】
前記第１の領域は、前記半導体集積回路全体の配置領域を分割した分割領域である、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項４】
前記半導体集積回路を複数の階層ブロックに分割し、
前記第１の領域は、前記分割した階層ブロックの領域である、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項５】
前記ネットリストに含まれる複数のセルを機能に基づいてグループ化し、
前記第１の領域への配置では、前記セルのグループに基づいて配置する、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項６】
前記ネット接続コストは、セルの入力端子及び出力端子に接続される配線に基づいた値である、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項７】
前記ネット接続コストは、前記入力端子の端子数と、前記出力端子の端子数と前記出力端子に接続されるセル数との乗算結果と、を合計した値である、
請求項６に記載の半導体集積回路のレイアウト設計方法。
【請求項８】
前記ネット接続コストは、前記合計した値を所定の範囲の値に変換した値である、
請求項７に記載の半導体集積回路のレイアウト設計方法。
【請求項９】
前記配線リソースは、前記第１の領域における配線で使用可能な有効配線トラック数に基づいた値である、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１０】
前記配線リソースは、隣接する２つの配線層の前記有効配線トラック数の平均値を合計した値である、
請求項９に記載の半導体集積回路のレイアウト設計方法。
【請求項１１】
前記有効配線トラック数は、前記第１の領域の全配線トラック数から、前記セルの配置前に前記第１の領域に配置された回路ブロックにより使用されている配線トラック数を差し引いた値である、
請求項９に記載の半導体集積回路のレイアウト設計方法。
【請求項１２】
前記第１の領域における前記ネット接続コストと前記配線リソースを比較し、前記ネット接続コストが前記配線リソースよりも大きい場合、前記配線リソースが不足していると判断する、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１３】
前記第１の領域における前記配線リソースに対する前記ネット接続コストの割合である配線リソース充足率に応じて、前記配線リソースの不足を判断する、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１４】
前記付与する仮想拡張領域は、前記第１の領域における前記配線リソースに対する前記ネット接続コストの割合である配線リソース充足率に応じたサイズである、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１５】
前記付与する仮想拡張領域は、垂直方向の配線トラック数と水平方向の配線トラック数に応じたサイズである、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１６】
前記セルの配置または再配置後、概略配線を行い、
前記概略配線の結果、配線混雑領域が存在する場合、前記配線混雑領域に配置したセルに前記仮想拡張領域を再付与し、
前記再付与した仮想拡張領域を加えたセルのサイズに基づいて、前記セルの配置を変更する、
請求項１に記載の半導体集積回路のレイアウト設計方法。
【請求項１７】
前記セルの配置の変更では、  前記再付与した仮想拡張領域を加えたセルと他のセルとの重なりをほぐす、
請求項１６に記載の半導体集積回路のレイアウト設計方法。
【請求項１８】
前記再付与する仮想拡張領域は、配線混雑のレベルに応じたサイズである、
請求項１６に記載の半導体集積回路のレイアウト設計方法。
【請求項１９】
コンピュータに半導体集積回路のレイアウト設計処理を実行させる半導体集積回路のレイアウト設計プログラムであって、前記レイアウト設計処理は、
入力されたネットリストに基づいて、半導体集積回路の第１の領域に配線可能な配線リソースを算出し、
前記ネットリストに含まれる複数のセルを当該セルのサイズに基づいて前記第１の領域に配置し、
前記ネットリストに含まれるセルの接続情報に基づいて、前記第１の領域に配置した複数のセルの接続度合いを示すネット接続コストを算出し、
前記第１の領域において前記ネット接続コストに対し前記配線リソースが不足している場合、当該第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与し、
前記付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを前記第１の領域に再配置する、
半導体集積回路のレイアウト設計プログラム。
【請求項２０】
入力されたネットリストに基づいて、半導体集積回路の第１の領域に配線可能な配線リソースを算出する配線リソース算出部と、
前記ネットリストに含まれる複数のセルを当該セルのサイズに基づいて前記第１の領域に配置するセル配置部と、
前記ネットリストに含まれるセルの接続情報に基づいて、前記第１の領域に配置した複数のセルの接続度合いを示すネット接続コストを算出するネット接続コスト算出部と、
前記第１の領域において前記ネット接続コストに対し前記配線リソースが不足している場合、当該第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与する仮想拡張領域付与部と、
前記付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを前記第１の領域に再配置するセル再配置部と、
を備える半導体集積回路のレイアウト設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路のレイアウト設計方法、レイアウト設計プログラム及びレイアウト設計装置に関し、例えば、ネットリストに基づいてセルを配置する半導体集積回路のレイアウト設計方法、レイアウト設計プログラム及びレイアウト設計装置に好適に利用できるものである。
【背景技術】
【０００２】
近年、半導体集積回路（ＬＳＩ：Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）の大規模化が進み、さらに、高い周波数による動作など高性能化も要求されている。このため、半導体集積回路の設計の難易度が高くなり、設計期間がますます長くなる傾向にあることから、設計効率の向上が強く望まれている。
【０００３】
ＬＳＩの設計では、回路設計工程において、マクロやセルの機能や接続関係が設計される。その後、レイアウト設計工程において、マクロ配置、セル配置及び配線を含む配置配線が行われ、さらに、遅延時間を計算しタイミング解析が行われる。ＬＳＩのセル配置に関する技術として、例えば、特許文献１〜３が知られている。
【０００４】
図１７は、特許文献１に記載された従来のセル配置装置の構成を示している。図１７に示すように、従来のセル配置装置は、入力手段９０１、パーティショニングベースの配置処理手段９０２、抽出手段９０３、レジスティブネットワーク方式の配置処理手段９０４を備えている。
【０００５】
パーティショニングベースの配置処理手段９０２は、半導体チップを分割した領域に各セルを振分けて各セルの暫定配置を決める。抽出手段９０３は、ネットの数が一定値を越えた配線が混雑している領域、信号伝達の遅延が大きいネットの領域等を抽出する。レジスティブネットワーク方式の配置処理手段９０４は、該暫定配置から各セルに仮想のネットが張られているとみなして、ネットをバネと考えて反発力を発生させ、セルをその領域から追い出すことでセルの配置を決める。
【０００６】
なお、予めセルの配置結果がある場合には、入力手段９０１がセルの配置結果を入力し、該入力した配置結果における各セルの位置から各セルに仮想のネットが張られているとみなして、レジスティブネットワーク方式の配置処理手段９０４で配置結果を改善する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−０８３００４号公報
【特許文献２】特開平１１−３１２１８５号公報
【特許文献３】特開２００３−２８２７１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載の従来技術は、ＬＳＩの開発設計において、局所的な配線の混雑を発生させず、タイミング収束のイタレーションの少ない配置結果を得ることを目的とした技術である。この従来技術は、ＬＳＩのセルを配置する際に、パーティショニングベースとレジスティブネットワークの配置方式を組合せることで、パーティショニングベースの欠点とレジスティブネットワークの欠点の各々を補う特徴を有する。パーティショニングベースの欠点である、チップを分割する初期段階では、セルの最終的な配置結果を予想することが困難であり、処理を進めたとき配線性が良くなるか悪くなるかを判定しにくい欠点を補い、また、レジスティブネットワークの欠点である、ネットを２つのセル間のバネとして近似しているため配線長が見積もりにくい欠点を補う。
【０００９】
本発明者は、特許文献１に記載された従来技術を検討し、この従来技術は、局所的な配線混雑領域の発生によりタイミング収束のイタレーションが増加する問題があることを見出した。
【００１０】
その理由は、昨今のＬＳＩは、数千万ゲートの論理を搭載し、かつ、各セルの論理接続が複雑であることから、従来技術のようにパーティショニングベース方式により全セルを領域に均一に暫定配置した場合、各領域のセル面積が均一となるようにセルが配置されるため、論理接続が複雑なセルが多く存在する領域では、局所的な配線混雑領域や、それに伴う配線迂回の発生する可能性が増加するためである。
【００１１】
具体的には、２千万ゲートの論理を搭載するＬＳＩでは、配線混雑領域がＬＳＩ全体で１０％程度発生し、特に、昨今のＬＳＩでは、各セルの論理接続が複雑であるため、局所的な配線混雑領域が発生することになる。そうすると、従来技術のパーティショニングベース方式による全セルを領域に均一に配置した暫定配置で局所的な配線混雑領域が集中した場合、レジスティブネットワーク方式によるセルの移動距離が大きくなり、更には、タイミングを収束させるためのリピータ（バッファ）が所望の位置に配置できず、また、同様にタイミングを収束させるためにセルをサイズアップした際に、セルを所望の位置に配置することができない。したがって、タイミングが収束できず、タイミング収束のイタレーションが増加する。
【００１２】
以上のように、従来技術では、半導体集積回路のレイアウト設計において、イタレーションが発生し、設計効率が悪化するという問題がある。
【００１３】
その他の課題と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１４】
一実施の形態によれば、半導体集積回路のレイアウト設計装置は、配線リソース算出部、セル配置部、ネット接続コスト算出部、仮想拡張領域付与部、セル再配置部を備えている。配線リソース算出部は、入力されたネットリストに基づいて、半導体集積回路の第１の領域に配線可能な配線リソースを算出する。セル配置部は、ネットリストに含まれる複数のセルを当該セルのサイズに基づいて第１の領域に配置する。ネット接続コスト算出部は、ネットリストに含まれるセルの接続情報に基づいて、第１の領域に配置した複数のセルの接続度合いを示すネット接続コストを算出する。仮想拡張領域付与部は、第１の領域においてネット接続コストに対し配線リソースが不足している場合、当該第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与する。セル再配置部は、付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを第１の領域に再配置する。
【発明の効果】
【００１５】
前記一実施の形態によれば、半導体集積回路のレイアウト設計におけるイタレーションを抑止し、設計効率を向上することができる。
【図面の簡単な説明】
【００１６】
【図１】実施の形態に係る半導体集積回路のレイアウト設計装置の主要な特徴を示す構成図である。
【図２】実施の形態１に係る半導体集積回路のレイアウト設計装置を実現するためのシステム構成を示す構成図である。
【図３】実施の形態１に係る半導体集積回路のレイアウト設計装置を実現するためのコンピュータシステムのハードウェア構成を示す構成図である。
【図４】実施の形態１に係る半導体集積回路のレイアウト設計装置の機能構成を示すブロック図である。
【図５】実施の形態１に係る半導体集積回路のレイアウト設計方法を示すフローチャートである。
【図６】実施の形態１に係る半導体集積回路のレイアウト設計方法のネット接続コスト算出動作を説明するための説明図である。
【図７】実施の形態１に係る半導体集積回路のレイアウト設計方法の配置領域分割動作を説明するための説明図である。
【図８】実施の形態１に係る半導体集積回路のレイアウト設計方法の配線リソース算出動作を説明するための説明図である。
【図９】実施の形態１に係る半導体集積回路のレイアウト設計方法のセル群分割動作を説明するための説明図である。
【図１０】実施の形態１に係る半導体集積回路のレイアウト設計方法のＨａｌｏ削除動作を説明するための説明図である。
【図１１】実施の形態１に係る半導体集積回路のレイアウト設計方法のセル群ネット接続コスト算出動作を説明するための説明図である。
【図１２】実施の形態１に係る半導体集積回路のレイアウト設計方法の配線リソース判定動作を説明するための説明図である。
【図１３】実施の形態１に係る半導体集積回路のレイアウト設計方法のＨａｌｏ付与動作を説明するための説明図である。
【図１４】実施の形態１に係る半導体集積回路のレイアウト設計方法の配置領域分割動作を説明するための説明図である。
【図１５】実施の形態２に係る半導体集積回路のレイアウト設計装置の機能構成を示すブロック図である。
【図１６】実施の形態２に係る半導体集積回路のレイアウト設計方法を示すフローチャートである。
【図１７】従来のセル配置装置の構成を示す構成図である。
【発明を実施するための形態】
【００１７】
（実施の形態の概要）
実施の形態の説明に先立って、図１を用いて、実施の形態の主要な特徴についてその概要を説明する。
【００１８】
図１に示すように、実施の形態に係る半導体集積回路のレイアウト設計装置は、配線リソース算出部１、セル配置部２、ネット接続コスト算出部３、仮想拡張領域付与部４、セル再配置部５を備えている。
【００１９】
配線リソース算出部１は、入力されたネットリストに基づいて、半導体集積回路の第１の領域に配線可能な配線リソースを算出する。セル配置部２は、ネットリストに含まれる複数のセルを当該セルのサイズに基づいて第１の領域に配置する。ネット接続コスト算出部３は、ネットリストに含まれるセルの接続情報に基づいて、第１の領域に配置した複数のセルの接続度合いを示すネット接続コストを算出する。仮想拡張領域付与部４は、第１の領域においてネット接続コストに対し配線リソースが不足している場合、当該第１の領域に配置したセルに仮想的にサイズを膨らませる仮想拡張領域を付与する。セル再配置部５は、付与した仮想拡張領域を加えたセルのサイズに基づいて、当該セルを含む複数のセルを第１の領域に再配置する。
【００２０】
このように、実施の形態では、半導体集積回路の配置領域（第１の領域）の配線リソースと、配置領域に配置したセルのネット接続コストを算出し、このネット接続コストに対し配線リソースが不足している場合、仮想拡張領域を付与したセルのサイズに基づいてセルを再配置する。
【００２１】
セルのネット接続コストと配線リソースを用いることで、配線前の工程において配線混雑の可能性を判定することができる。レイアウト設計において、配線リソースの不足に応じて仮想拡張領域を付与したセルを再配置するため、配線の混雑が発生する領域に配線領域を確保することができ、セル配置後の配線によって配線の混雑が発生することを抑止できる。このため、配線の混雑によるイタレーションを抑止し、設計効率を向上することができる。
【００２２】
（実施の形態１）
以下、図面を参照して実施の形態１について説明する。図２は、本実施の形態に係る半導体集積回路のレイアウト設計装置を実現するためのシステム構成を示し、図３は、そのシステムに含まれるコンピュータ装置のハードウェア構成を示している。
【００２３】
図２に示すように、本実施の形態に係る半導体集積回路のレイアウト設計システムは、コンピュータ装置１０とサーバ２０を備えている。コンピュータ装置１０とサーバ２０とはネットワーク３０を介して接続されており、サーバ２０は記録媒体２１を備えている。
【００２４】
記録媒体２１は、本実施の形態に係る半導体集積回路のレイアウト設計方法を実行するレイアウト設計プログラムを格納している。サーバ２０は、インターネットなどのネットワーク３０を介してエンジニアリングワークステーション等のコンピュータ装置１０に接続される。記録媒体２１に格納されているレイアウト設計プログラムは、ネットワーク３０を介してコンピュータ装置１０にダウンロードされる。ダウンロードされたレイアウト設計プログラムは、コンピュータ装置１０のローカルなハードディスク或はメモリなどにストアされて実行処理を行う構成になっている。
【００２５】
コンピュータ装置１０は、ワークステーションやパーソナルコンピュータ等の情報処理装置である。図３に示すように、コンピュータ装置１０は、ＣＰＵ１２、メインメモリ１３、ハードディスク１４等を内蔵した本体部１１、本体部１１からの指示により画面表示を行う表示装置１５、このコンピュータ装置１０にユーザの指示や文字情報を入力するためのキーボード１６、および表示装置１５の画面上における任意の位置を指定し、その位置に表示されていたアイコン等に応じた指示を入力するマウス１７から構成される。
【００２６】
ＣＰＵ１２及びメインメモリ１３は、プログラムを実行し各部を制御する制御部の一例であり、ハードディスク１４は、プログラム等を記憶する記憶部の一例である。制御部と記憶部は、一つの装置でもよいし、複数の装置であってもよい。例えば、複数の制御装置や複数の記憶装置に分散されていてもよい。また、表示装置１５は、ユーザに対し種々の出力を行う出力装置の一例であり、キーボード１６、マウス１７は、ユーザが種々の入力操作を行う入力装置の一例である。
【００２７】
ハードディスク１４には、例えば、サーバ２０からダウンロードされたレイアウト設計プログラム１８と、レイアウト設計処理等に必要なその他の各種データ１９が格納される。レイアウト設計プログラム１８は、図５に後述するレイアウト設計方法の処理を実行するためのプログラムである。各種データ１９は、図４に後述する各格納部に格納されるデータである。
【００２８】
コンピュータ装置１０が、レイアウト設計プログラム１８および各種データ１９をメインメモリ１３にロードし、ＣＰＵ１２はメインメモリ１３にロードされたレイアウト設計プログラム１８を実行することで、本実施形態に係るレイアウト設計方法の各処理が実施されて、レイアウト設計装置（図４に後述する機能構成）が実現される。
【００２９】
なお、コンピュータ装置１０の基本動作は、ハードディスク１４に格納された基本プログラムであるオペレーティングシステム（ＯＳ）を介して実行される。
【００３０】
図４は、本実施の形態に係る半導体集積回路のレイアウト設計装置の構成を示している。レイアウト設計装置１００は、コンピュータ装置１０上でレイアウト設計プログラムが実行されて実現される処理部１０１と、コンピュータ装置１０のハードディスク１４等に相当する各種データの格納部１０２を備えている。なお、各処理部及び各格納部は、１つのコンピュータ装置１０により実現してもよいし、複数のコンピュータ装置１０により実現してもよい。
【００３１】
図４に示すように、レイアウト設計装置１００の格納部１０２は、配置前ネットリスト格納部２０１、配置情報格納部２０２、ネット接続コスト格納部２０３、配線リソース格納部２０４、Ｈａｌｏ格納部２０５、配置後ネットリスト格納部２０６を備えている。また、レイアウト設計装置１００の処理部１０１は、セル配置処理部１１０、ネット接続コスト算出処理部１２０、配線リソース算出処理部１３０、Ｈａｌｏ処理部１４０、概略配線処理部１５０を備えている。
【００３２】
配置前ネットリスト格納部２０１は、予め設計されたネットリストを格納する。このネットリストは、マクロ配置済みでセル配置前のネットリストであり、マクロの構成、接続関係及び配置位置、セルの構成、接続関係等が定義されている。特に、ネットリストは、セルの入力端子と出力端子ごとに接続関係が記載されている。配置前ネットリスト格納部２０１に格納されたネットリストは、処理部１０１の入力情報であり、処理部１０１は入力されるネットリストに基づいてセル配置を行う。
【００３３】
配置情報格納部２０２は、処理部１０１のセル配置処理部１１０が、セルの配置処理に必要な情報を格納する。例えば、配置情報格納部２０２は、配置領域を分割した分割領域の情報、分割領域したセル群の情報、分割領域に割付けた（配置した）セル群の情報等を格納する。
【００３４】
ネット接続コスト格納部２０３は、処理部１０１のネット接続コスト算出処理部１２０が算出したネット接続コストを格納する。ネット接続コスト格納部２０３は、ネットリストに含まれる全てのセルのネット接続コストや、分割領域ごとに割付けられているセル群のネット接続コストを格納する。
【００３５】
配線リソース格納部２０４は、処理部１０１の配線リソース算出処理部１３０が算出した配線リソースを格納する。配線リソース格納部２０４は、分割領域ごとの配線リソースを格納する。
【００３６】
Ｈａｌｏ格納部２０５は、処理部１０１のＨａｌｏ処理部１４０に付与されたセルのＨａｌｏ（仮想拡張領域）に関する情報（Ｈａｌｏ情報）を格納する。Ｈａｌｏ情報は、Ｈａｌｏのサイズを含み、付与されたセルと関連付けて格納されている。
【００３７】
配置後ネットリスト格納部２０６は、処理部１０１の処理結果（出力情報）のネットリストを格納する。このネットリストは、セル配置済みのネットリストであり、マクロの構成、接続関係及び配置位置、セルの構成、接続関係及び配置位置等が定義されている。配置後ネットリスト格納部２０６のネットリストは、本実施の形態によるセル配置により、局所的な配線混雑の発生が抑止されたネットリストである。
【００３８】
セル配置処理部１１０（図１のセル配置部２及びセル再配置部５に相当）は、半導体集積回路の配置領域の分割とセルの割付けを行い、これを繰り返すことで分割領域にセルに配置する。また、セル配置処理部１１０は、セルにＨａｌｏが付与された場合、配置領域の分割とセルの割付けを再度行う。セル配置処理部１１０は、配置領域分割処理部１１１、セル群分割処理部１１２、セル群割付け処理部１１３、配置領域分割判定部１１４、配線混雑領域確認処理部１１５、重なりほぐし処理部１１６を備えている。
【００３９】
配置領域分割処理部１１１は、半導体集積回路の配置領域をカットラインにより複数の分割領域に分割する。セル群分割処理部１１２は、分割された各分割領域にセル群を分割する（振り分ける）。特に、セル群分割処理部１１２は、セルにＨａｌｏが付与された場合、Ｈａｌｏを含めたサイズを用いて、セル群を分割する。セル群割付け処理部１１３は、分割されたセル群を各分割領域に割付ける（配置する）。
【００４０】
配置領域分割判定部１１４は、配置領域の分割処理の繰り返しを終了（配置終了）するか否か判定する。具体的には、配置領域分割判定部１１４は、分割領域ごとのセル数が所定数より小さいか否か判定する。
【００４１】
配線混雑領域確認処理部１１５は、セル配置後、局所的な配線混雑領域の有無を確認する。重なりほぐし処理部１１６は、セルの配置が重なっている（配置領域が重複している）場合、重なりが無くなるよう（ほぐすよう）にセルの配置を変更する。特に、重なりほぐし処理部１１６は、セルにＨａｌｏが付与された場合、Ｈａｌｏを含めたサイズを用いて、セルの重なりをほぐす。
【００４２】
ネット接続コスト算出処理部１２０（図１のネット接続コスト算出部３に相当）は、セルの接続関係に基づいてセルのネット接続コストを算出する。ネット接続コスト算出処理部１２０は、セル用ネット接続コスト算出処理部１２１、セル群用ネット接続コスト算出処理部１２２を備えている。セル用ネット接続コスト算出処理部１２１は、ネットリストに含まれる全セルのネット接続コストを算出する。セル群用ネット接続コスト算出処理部１２２は、分割領域ごとに割付けられているセル群のネット接続コストを算出する。
【００４３】
配線リソース算出処理部１３０（図１の配線リソース算出部１に相当）は、配線トラック数に基づいて、分割領域ごとの配線リソースを算出する。
【００４４】
Ｈａｌｏ処理部１４０（図１の仮想拡張領域付与部４に相当）は、セルに対しＨａｌｏの付与／削除を行う。Ｈａｌｏ処理部１４０は、Ｈａｌｏ付与判定部１４１、Ｈａｌｏ付与処理部１４２、Ｈａｌｏ削除処理部１４３、Ｈａｌｏ再付与処理部１４４を備えている。
【００４５】
Ｈａｌｏ付与判定部１４１は、分割されたセル群の各セルにＨａｌｏの付与が必要か否か判定する。具体的には、Ｈａｌｏ付与判定部１４１は、ネット接続コストに対し配線リソースが不足しているか否か判定する。Ｈａｌｏ付与処理部１４２は、ネット接続コストに対し配線リソースが不足している場合、セルにＨａｌｏを付与する。Ｈａｌｏ削除処理部１４３は、セルに付与されているＨａｌｏを削除する。Ｈａｌｏ再付与処理部１４４は、セル配置後、局所的配線混雑領域が発生している場合、セルにＨａｌｏを再付与する。
【００４６】
概略配線処理部１５０は、セルの配置後、局所的配線混雑を確認するため、概略配線を行う。
【００４７】
図５のフローチャートは、本実施の形態に係る半導体集積回路のレイアウト設計方法を示している。半導体集積回路のレイアウト設計において、マクロ配置が行われ、マクロ配置後のネットリストが生成された後、以下の処理が実行される。
【００４８】
まず、レイアウト設計装置１００は、半導体集積回路のネットリストに含まれる全てのセルごとに、入力端子数、出力端子数、および、出力端子に接続されるセル数に応じてネット接続コストを算出する（ステップＳ１）。
【００４９】
次いで、レイアウト設計装置１００は、ｍｉｎ−ｃｕｔ法等で配置領域を分割し（ステップＳ２）、分割した配置領域の配線リソースを、配線トラックに基づき算出する（ステップＳ３）。
【００５０】
次いで、レイアウト設計装置１００は、ｍｉｎ−ｃｕｔ法により、カットラインを横切る配線本数が最小になり、かつ、セル面積の偏りがないようにセル群を分割し（振り分け）、分割した配置領域に割付け（ステップＳ４、Ｓ５）、セルにサイズを仮想的に膨らませるための仮想的なセルサイズ情報（以下、Ｈａｌｏとも言う）が付与されている場合、Ｈａｌｏを削除する（ステップＳ６）。
【００５１】
次いで、レイアウト設計装置１００は、ステップＳ１で算出したネット接続コストに基づき、領域のセル群のネット接続コストを算出し（ステップＳ７）、ステップＳ７で算出したネット接続コストに対し、ステップＳ３で算出した配線トラックが不足している場合、セルを仮想的に膨らませるＨａｌｏを付与し、ステップＳ４のセル群の分割に戻る（ステップＳ８、Ｓ９）。この場合、Ｈａｌｏを付与したセルのサイズで、セル群の分割、割付けを行う（ステップＳ４〜Ｓ７）。
【００５２】
次いで、レイアウト設計装置１００は、配線トラックが足りている場合、分割領域に属するセル数がｍｉｎ−ｃｕｔ法の目標関数である十分少ないセル数であるか判定し、セル数が多い場合、ステップＳ２に戻る（ステップＳ１０）。この場合、配置領域をさらに分割し、分割領域にセル群の分割、割付けを行う（ステップＳ２〜Ｓ８）。
【００５３】
レイアウト設計装置１００は、ｍｉｎ−ｃｕｔ法により、全てのセルの配置が完了した時点で、概略配線を実行し、局所的な配線混雑領域がないか確認する（ステップＳ１１、Ｓ１２）。
【００５４】
レイアウト設計装置１００は、局所的な配線混雑が存在する場合には、その領域に含まれるセルに、セルを仮想的に膨らませるＨａｌｏを付与し、セルの重なりをほぐし、ステップＳ１１に戻る（ステップＳ１３、Ｓ１４）。また、レイアウト設計装置１００は、局所的な配線混雑領域がない場合、処理を完了する（ステップＳ１２）。
【００５５】
これによりセル配置が完了し、その後、配線が行われ、さらに、遅延時間の計算及びタイミング解析が行われる。本実施の形態のセル配置により、局所的な配線混雑が生じないため、タイミング解析からレイアウト設計（セル配置）へのイタレーションの発生を抑えられる。
【００５６】
以下、図６から図１３を用いて、図５のレイアウト設計方法の処理フローを具体的に説明する。まず、セル用ネット接続コスト算出処理部１２１は、半導体集積回路のネットリストに含まれる全セルに対し、入力端子数、出力端子数、および、出力端子に接続されるセル数に応じてネット接続コストを算出する（ステップＳ１）。セル用ネット接続コスト算出処理部１２１は、配置前ネットリスト格納部２０１に格納されたセル配置前の半導体集積回路のネットリストを参照し、このネットリストに含まれる全セルのネット接続コストを算出して、算出したネット接続コストをネット接続コスト格納部２０３に格納する。ネット接続コストは、他のセルとの接続度合いを示し、配線の混雑度を判断するための１つの指標であり、少なくともセルの入力端子及び出力端子に接続される配線に基づいている。さらに、ネット接続コストは、例えば、以下の（式１）により算出される。
ネット接続コスト＝ネットの接続されている入力端子数＋Σ（各出力端子×各出力端子に接続されるセル数）  ・・・（式１）
【００５７】
（式１）によりセルに接続される全ての入出力配線の数をネット接続コストとすることができる。図６は、ステップＳ１において、ネットリストに含まれるセルに設定するネット接続コストの一例を示している。なお、セルとは、図６のように１つのフリップフロップやゲート回路などから構成されるプリミティブセル（基本セル：最小単位の機能セル）である。
【００５８】
図６の例では、図６（ａ）のセル３０１と図６（ｄ）のセル３０４は、共に入力端子が一つ、出力端子が一つで、同じ入力、出力端子数を持つセルである。ここで、入力端子については、セル３０１、セル３０４共にネットが接続されており、ネットの接続されている入力端子数は一つと同じである。一方、出力端子については、セル３０１の出力端子に接続されるセルは一つであるが、セル３０４の出力端子に接続されるセルは三つとセル３０１に比べ二つ多い。
【００５９】
このため、上記（式１）のネット接続コストの算出式を用いると、図６（ａ）のセル３０１のネット接続コスト＝１＋１×１＝２となり、図６（ｄ）のセル３０４のネット接続コスト＝１＋１×３＝４となる。
【００６０】
同様に、図６（ｂ）のセル３０２は、入力端子数＝３、出力端子数＝１、出力端子に接続されるセル数＝１であるため、ネット接続コスト＝３＋１×１＝４となる。図６（ｃ）のセル３０３は、入力端子数＝１、出力端子数＝３、出力端子に接続されるセル数＝１であるため、ネット接続コスト＝１＋３×１＝４となる。図６（ｅ）のセル３０５は、入力端子数＝３、出力端子数＝３、出力端子に接続されるセル数＝３であるため、ネット接続コスト＝３＋１×３＋１×３＋１×３＝１２となる。
【００６１】
この（式１）により算出した値をネット接続コストとして以降の処理を行ってもよいし、別の値に変換（変更）してもよい。図６の例では、（式１）により算出したネット接続コストを、特定の範囲を決め、その範囲内のネット接続コストを同一のネット接続コストとして扱う。ネット接続コストを所定の範囲に丸めることにより、処理を簡略化することができ、また、配線リソースと比較するためのパラメータ調整を行うことができる。
【００６２】
例えば、ネット接続コストが１から３の範囲を１、４から５の範囲を２、６から８の範囲を３、９から１０の範囲を４、１１から１２の範囲を５とする。これにより、図６に示すように、ネット接続コスト算出の例で算出したセル３０１＝２、セル３０２＝４、セル３０３＝４、セル３０４＝４、セル３０５＝１２の各ネット接続コストを、前記のネット接続コストの範囲に基づき、セル３０１＝１、セル３０２、セル３０３、セル３０４＝２、セル３０５＝５と各々のネット接続コストを設定する。
【００６３】
次いで、配置領域分割処理部１１１は、半導体集積回路の配置領域をカットラインにより分割する（ステップＳ２）。配置領域の分割には、一般的な配置技術であるｍｉｎ−ｃｕｔ法などを用いることでよい。配置領域分割処理部１１１は、配置前ネットリスト格納部２０１に格納されたセル配置前の半導体集積回路のネットリストを参照してセルを配置する配置領域を特定し、例えば、この配置領域を均等に２分割し、２分割した分割領域の情報を配置情報格納部２０２に格納する。
【００６４】
図７は、ステップＳ２において、半導体集積回路の配置領域を分割した分割領域の一例を示している。図７の例は、配置領域Ａ１をカットラインＣ１で分割した例である。すなわち、配置領域Ａ１を、カットラインＣ１により、それぞれの面積が１／２となるように、分割領域Ｂ１と分割領域Ｂ２に分割する。なお、この例では、分割領域Ｂ２に、ある機能を持つマクロＭ１が既に配置されている。なお、マクロとは、所定の機能を実現するように、複数の回路から構成された回路ブロックである。
【００６５】
次いで、配線リソース算出処理部１３０は、ステップＳ２で分割した各分割領域に存在する配線トラック数を元に配線リソースを算出する（ステップＳ３）。配線リソース算出処理部１３０は、配置情報格納部２０２に格納された分割領域を参照して、この分割領域の配線リソースを算出し、算出した配線リソースを配線リソース格納部２０４に格納する。
【００６６】
図８は、ステップＳ３において、配線リソースを算出するために用いる、分割領域の配線トラックの一例を示している。図８の例は、図７のステップＳ２で分割した分割領域Ｂ２に存在する配線トラックの例である。図８（ａ）は分割領域Ｂ２のメタル１層で水平方向（Ｘ方向：横方向）に配線トラックＬ１が延在することを示し、図８（ｂ）は分割領域Ｂ２のメタル２層で垂直方向（Ｙ方向：縦方向）に配線トラックＬ２が延在することを示し、図８（ｃ）は分割領域Ｂ２のメタル３層で水平方向に配線トラックＬ３が延在することを示し、図８（ｄ）は分割領域Ｂ２のメタル４層で垂直方向に配線トラックＬ４が延在することを示している。なお、図８（ｄ）のメタル４層の配線トラックＬ４は、他の図８（ａ）、図８（ｂ）、図８（ｃ）の層の配線トラックＬ１、Ｌ２、Ｌ３に対して倍の間隔で配線トラックが延在している。つまり、図８（ａ）、図８（ｂ）、図８（ｃ）の領域に対する配線トラックＬ１、Ｌ２、Ｌ３の配線トラック密度を１とした場合、図８（ｄ）の配線トラックＬ４の配線トラック密度は半分の０．５となる。
【００６７】
配線リソースは、配線の混雑度を判断するための１つの指標であり、少なくとも分割領域において配線のために使用可能な有効配線トラック数に基づいている。ここで、一般に配線を行う場合、隣接するメタル層の水平方向と垂直方向の２方向の配線トラックに沿って配線が敷設されてセル間が接続される。このため、１つの入力端子または出力端子の配線には、隣接するメタル層の水平方向の配線トラックと垂直方向の配線トラックが必要となる。したがって、配線リソースは、隣接する２つのメタル層の配線トラック数の平均（１／２）を合計した値となる。図８の分割領域Ｂ２の配線リソースは、図８（ａ）と図８（ｂ）のペア、図８（ｂ）と図８（ｃ）のペア、図８（ｃ）と図８（ｄ）のペアに基づき、（１層のトラック数＋２層のトラック数）／２＋（２層のトラック数＋３層のトラック数）／２＋（３層のトラック数＋４層のトラック数）／２が、全体の配線リソースとなる。これにより、精度よく配線リソースの過不足を判断することができる。なお、全てのメタル層の配線トラックを単純に合計した値を配線リソースとして、簡易に配線リソースを求めてもよい。
【００６８】
このとき、電源配線等により、既に配線トラックが使われている場合には、そのトラックは使用済みとしカウントしない。更に、当該領域にマクロ等が配置されている場合、そのマクロで使用されるトラックは使用済みとしカウントしない。これにより、確実に使用可能な有効配線トラック数を用いて、配線リソースを算出できる。
【００６９】
図８ではマクロＭ１が配置され、かつ、メタル１層とメタル２層をマクロＭ１で使用済みであり、図８（ａ）のメタル１層の有効配線トラックと図８（ｂ）のメタル２層の有効配線トラックは、マクロＭ１で使用済みのトラックを除いたものとなる。
【００７０】
そうすると、配線リソースを算出する算出式の一例は、次の（式２）、（式３）となる。
配線リソース＝Σ（（（ｎ層の有効配線トラック）＋（ｎ＋１層の有効配線トラック））／２）  ・・・（式２）
有効配線トラック＝ｎ層の配線トラック−ｎ層の使用済みのトラック  ・・・（式３）
【００７１】
次いで、セル群分割処理部１１２、ステップＳ２で分割した各配置領域のカットラインを横切る配線の本数が最小になるようにセル群を分割し（振り分け）（ステップＳ４）、セル群割付け処理部１１３は、分割したセル群を分割領域に割付ける（ステップＳ５）。セル群の分割と分割領域へのセル群の割付けは、一般的な配置技術であるｍｉｎ−ｃｕｔ法などを用いることでよく、更に、当該手法の目標である、セル面積の合計が一定の範囲内に収まることを条件とし、セルがどちらかの領域に偏らないようにする。
【００７２】
セル群分割処理部１１２は、配置情報格納部２０２に格納された分割領域を参照して、ネットリストに含まれるセル群を２つの分割領域に振り分ける。セル群割付け処理部１１３は、振り分けた２つのセル群を各分割領域に割付け、割り付けたセル群と分割領域の情報を配置情報格納部２０２に格納する。
【００７３】
図９は、ステップＳ４において、分割したセル群を分割領域に割り付ける一例を示している。特に、図９では、図７ステップＳ２で分割した各分割領域Ｂ１、Ｂ２のカットラインＣ１を横切る配線の本数Ｄ１が最小になるようにセルをセル群Ｅ１とセル群Ｅ２のセルの集まりに分割し、分割領域Ｂ１とＢ２に分割したセル群Ｅ１、Ｅ２を割付けている。
【００７４】
次いで、Ｈａｌｏ削除処理部１４３は、各セルに対してセルにサイズを仮想的に膨らませるためのＨａｌｏが付与されている場合、Ｈａｌｏを削除する（ステップＳ６）。ステップＳ９がまだ実行されていない場合にはＨａｌｏが付与されていないため、ステップＳ９が実行されてＨａｌｏが付与された後、ステップＳ６でＨａｌｏが削除される。Ｈａｌｏ削除処理部１４３は、Ｈａｌｏ格納部２０５を参照し、各セルに付与されているＨａｌｏをＨａｌｏ格納部２０５から削除する。
【００７５】
図１０は、ステップＳ６においてＨａｌｏを削除する一例を示している。図１０の例では、セルＨ１にＨａｌｏ Ｈ２が付与されていたため、Ｈａｌｏ Ｈ２を削除し、セルのサイズを元のセルＨ１のサイズとする。すなわち、セルＨ１に付与されているＨａｌｏ Ｈ２を削除することで、セルの仮想的な膨らませを削除する。このように、各セルに付与されているＨａｌｏを削除しておくことで、後続のセルへのＨａｌｏ付与処理においてＨａｌｏを付与する対象となるセル以外のセルにＨａｌｏが付与されないようにする。
【００７６】
次いで、セル群用ネット接続コスト算出処理部１２２は、ステップＳ１の各セルのネット接続コストを参照して、ステップＳ４で分割したセル群のネット接続コストを算出する（ステップＳ７）。セル群用ネット接続コスト算出処理部１２２は、ネット接続コスト格納部２０３に格納されたネット接続コストを参照し、配置情報格納部２０２に格納された分割されたセル群の情報を参照し、各セル群のネット接続コストを算出し、算出したネット接続コストをネット接続コスト格納部２０３に格納する。
【００７７】
図１１は、ステップＳ７において各セル群のネット接続コストを算出する一例を示している。図１１の例は、図７のステップＳ２で分割された分割領域Ｂ１、Ｂ２に対し、図９のステップＳ４，Ｓ５で分割及び割付けを行ったセル群の例である。各セルのネット接続コストはステップＳ１で算出しており、図１１は、ネット接続コストごとにセル群を分類した状態を示している。
【００７８】
セル群Ｃ１１は、図９で分割領域Ｂ１に割付けられたセル群Ｅ１に含まれ、セル群Ｃ２１は、図９で分割領域Ｂ２に割付けられたセル群Ｅ２に含まれ、共に、図６（ａ）、つまり、入力、出力端子数がともに１つで、出力に接続されるセル数が１つであり、ネット接続コストが１のセル群である。
【００７９】
セル群Ｃ１２は、図９で分割領域Ｂ１に割付けられたセル群Ｅ１に含まれ、セル群Ｃ２２は、図９で分割領域Ｂ２に割付けられたセル群Ｅ２に含まれ、共に、図６（ｂ）、つまり、入力端子数が３つ、出力端子数が１つで接続されるセル数が１つであり、ネット接続コストが２のセル群である。
【００８０】
セル群Ｃ１３は、図９で分割領域Ｂ１に割付けられたセル群Ｅ１に含まれ、セル群Ｃ２３は、図９で分割領域Ｂ２に割付けられたセル群Ｅ２に含まれ、共に、図６（ｅ）、つまり、入力端子数が３つ、出力端子数が３つで、各出力端子に接続されるセル数が３ずつであり、ネット接続コストが５のセル群である。
【００８１】
図９で分割領域Ｂ１に割付けられたセル群Ｃ１１〜Ｃ１３では、セル群Ｃ１１にネット接続コストが１のセルが４つ、セル群Ｃ１２にネット接続コストが２のセルが３つ、セル群Ｃ１３にネット接続コストが５のセルが２つある。このため、分割領域Ｂ１のセル群のネット接続コストは、「Σ（ネット接続コスト×セル数）」により、１×４＋２×３＋５×２＝２０となる。
【００８２】
同様に、図９で分割領域Ｂ２に割付けられたセル群Ｃ２１〜Ｃ２３では、セル群Ｃ２１にネット接続コストが１のセルが３つ、セル群Ｃ２２にネット接続コストが２のセルが２つ、セル群Ｃ２３にネット接続コストが５のセルが３つあるため、分割領域Ｂ２のセル群のネット接続コストは、１×３＋２×２＋５×３＝２２となる。
【００８３】
次いで、Ｈａｌｏ付与判定部１４１は、ステップＳ７で求めた分割したセル群のネット接続コストに対し、ステップＳ３で求めた各分割領域に存在する配線リソースが足りているかを判定する（ステップＳ８）。Ｈａｌｏ付与判定部１４１は、ネット接続コスト格納部２０３に格納されている分割したセル群のネット接続コストを参照し、配線リソース格納部２０４に格納されている分割領域の配線リソースを参照し、分割領域ごとに、ネット接続コストと配線リソースを比較する。
【００８４】
図１２は、ステップＳ８において判定する、分割領域ごとのセル群と配線リソース（配線トラック）の一例を示している。図１２の例では、図７と同様に、カットラインＣ１により配置領域が分割領域Ｂ１と分割領域Ｂ２に分割され、かつ、分割領域Ｂ２には機能を持つマクロＭ１が配置されている。このため、ステップＳ３で求めた配線リソースは、分割領域Ｂ１の配線リソースＴ１に比べて分割領域Ｂ２の配線リソースＴ２の方が少ない。一方、図１１のステップＳ７で求めた分割したセル群のネット接続コストは、セル群Ｅ１は２０、セル群Ｅ２は２２と、セル群Ｅ２の方が大きい。
【００８５】
ここで、"ネット接続コスト／配線リソース"により配線リソース充足率を求め、配線リソース充足率が１を超える場合、各分割領域の配線リソースが不足していると判断する。なお、配線リソース充足率の下限の判定基準は、使用するプロセスや使用する配線層により可変である。このように、ステップＳ７で求めた分割したセル群のネット接続コストに対し、ステップＳ３で求めた各分割領域の配線リソースが足りているかを判断する。
【００８６】
なお、配線リソース充足率の代わりに、ネット接続コストと配線リソースを単純に比較し、簡易に配線リソースの過不足を判断してもよい。ネット接続コストよりも配線リソースが大きい場合、配線リソースは足りていると判断し、ネット接続コストよりも配線リソースが小さい場合、配線リソースは不足していると判断する。
【００８７】
ステップＳ８において分割領域で配線リソースが不足していると判断された場合、Ｈａｌｏ付与処理部１４２は、配線リソースが不足していると判断された分割領域に割付けたセル群にサイズを仮想的に膨らませるためのＨａｌｏを付与する（ステップＳ９）。Ｈａｌｏ付与処理部１４２は、配線リソースの不足量に応じて分割領域のセル群にＨａｌｏを付与し、付与したＨａｌｏの情報をＨａｌｏ格納部２０５に格納する。図１３は、ステップＳ９においてＨａｌｏを付与する一例を示している。図１３の例では、セルＨ１に対し、仮想的にサイズを膨らませるためのＨａｌｏ Ｈ２を付与している。
【００８８】
付与するＨａｌｏのサイズは、ステップＳ７で求めた各セルのネット接続コストに準じて（応じて）付与し、ネット接続コストの高いセルには付与するＨａｌｏサイズを大きくする。これにより、コストが大きく配線がより必要なセルに対して、配線の領域を確保できる。また、ステップＳ８で求めた配線リソース充足率が高いほど、配線リソースが不足しているため、セルに付与するＨａｌｏサイズは、配線リソース充足率に比例して大きくする。これにより、配線リソースがより必要なセルに対して、配線の領域を確保することができる。
【００８９】
ここで、付与するＨａｌｏの水平方向（Ｘ方向）と垂直方向（Ｙ方向）の拡大比率については、使用するプロセスや使用する配線層により可変であり、例えば、水平方向の配線トラックが垂直方向の配線トラックに比べて多い場合には、垂直方向の配線トラックが不足するため、Ｈａｌｏは水平方向の拡大比率を多くする。これにより、水平方向・垂直方向の配線トラック数に応じて、必要な配線の領域を確保することができる。
【００９０】
ステップＳ９でＨａｌｏを付与した後、ステップＳ４以降の処理が繰り返される。すなわち、Ｈａｌｏを付与したサイズに基づいて、セル群の分割及び割付けが行われる。Ｈａｌｏを付与したセル群について、Ｈａｌｏを付与したサイズである仮想的なセルサイズのＨａｌｏ  Ｈ２をセルのサイズとして扱うことで、元のサイズであるセルＨ１と比べて領域を広げ、配線リソースの確保を可能とする。
【００９１】
ステップＳ８において分割領域で配線リソースが足りていると判断された場合、配置領域分割判定部１１４は、ステップＳ４で分割したセル群が十分少ないセル数となっているかを判断し（ステップＳ１０）、更に分割が必要な場合には、ステップＳ２のカットラインによる配置領域分割に戻り、ステップＳ２以降の処理が繰り返される。すなわち、さらに配置領域を分割し、分割領域にセルが割付けられる。セルの分割が十分であるかの判定は、一般的な配置技術であるｍｉｎ−ｃｕｔ法などの手法に基づくことでよい。
【００９２】
図１４（ａ）は、２回目のカットラインによる分割の例を示し、図１４（ｂ）は、最終のカットラインによる分割の例を示している。図１４（ａ）のように、２回目の分割では、縦方向のカットラインＣ１により分割された２つの分割領域を、横方向のカットラインＣ２によりそれぞれ２つに分割し、４つの分割領域とする。図１４（ａ）では、分割領域のセル数が所定値よりも多いため、さらに分割を繰り返す。
【００９３】
図１４（ｂ）のように、最終の分割では、縦方向のカットラインＣ１、Ｃ３、Ｃ４により分割され、横方向のカットラインＣ２、Ｃ５、Ｃ６により分割され、１６個の分割領域となる。図１４（ｂ）では、分割領域のセル数が所定値よりも小さいため、分割が不要となり、セルの配置が終了する。
【００９４】
例えば、配置領域分割判定部１１４は、配置情報格納部２０２を参照し、各分割領域に割付けられているセルが１よりも大きい場合、ステップＳ２以降の処理を繰り返して、さらに領域を分割し、各分割領域に割付けられているセルが１の場合、分割領域へのセルの配置が完了しているため、領域の分割処理を終了する。例えば、配置領域分割判定部１１４は、分割領域のセルが１になった場合、セルの配置情報に基づいて、配置後のネットリストを生成し、配置後ネットリスト格納部２０６に格納する。
【００９５】
次いで、セル配置後のネットリストにおいて配線の混雑箇所を確認する。なお、ステップＳ１〜ステップＳ１０の処理により、配線の混雑は抑えられているため、ステップＳ１１〜ステップＳ１４を実行せずに処理を終了してもよい。ステップＳ１〜ステップＳ１０に加えて、ステップＳ１１〜ステップＳ１４を実行することで、さらに配線の混雑を抑えることができる。
【００９６】
ステップＳ１０において、分割したセル群が十分少ないセル数であると判断された場合、概略配線処理部１５０は、ステップＳ１からステップＳ１０によるセルの配置結果に対して概略配線を実施する（ステップＳ１１）。概略配線については、一般的な概略配線技術を使用することでよい。例えば、概略配線処理部１５０は、配置後ネットリスト格納部２０６を参照し、配置後のセル間に対し概略配線を行い、概略配線後のネットリストを配置後ネットリスト格納部２０６に格納する。
【００９７】
次いで、配線混雑領域確認処理部１１５は、局所的な配線混雑領域がないことを確認し、混雑領域が存在しない場合には処理を完了する（ステップＳ１２）。配線混雑領域の検出については、一般的な技術を利用することでよく、例えば、概略配線結果の配線グラフで、点と枝のコストが一定値以上の箇所を配線混雑部と判断する。配線混雑領域確認処理部１１５は、配置後ネットリスト格納部２０６の概略配線後のネットリストを参照し、局所的な配線混雑領域を検出する。なお、本実施の形態では、ステップＳ１からステップＳ９により、各セルのネット接続コストを考慮した分割領域へのセル割付けをしているため、極端な局所的配線混雑領域は発生しない。
【００９８】
ステップＳ１２において、局所的な配線混雑領域があると判定された場合、Ｈａｌｏ再付与処理部１４４は、局所的に配線が混雑していると判断された領域内に位置するセルに対して、サイズを仮想的に膨らませるためのＨａｌｏを再付与する（ステップＳ１３）。Ｈａｌｏ再付与処理部１４４は、配線の混雑度に応じてセルにＨａｌｏを付与し、付与したＨａｌｏの情報をＨａｌｏ格納部２０５に格納する。
【００９９】
セルに付与するＨａｌｏのサイズは、ステップＳ９でセルに付与したＨａｌｏより大きいサイズとし、混雑領域のレベルによって決定し、配線混雑レベルの高い領域のセルへは、配線混雑レベルの低い領域のセルより大きいＨａｌｏを付与する。ここで、ステップＳ１２の局所配線混雑領域で、水平方向で配線が混雑している場合には垂直方向にＨａｌｏを付与し、垂直方向で配線が混雑している場合には水平方向にＨａｌｏを付与し、水平方向、垂直方向共に配線が混雑している場合には垂直方向と水平方向の両方にＨａｌｏを付与する。これにより、以前のステップＳ９でセルに付与したＨａｌｏより大きいサイズのＨａｌｏを付与することで、次のステップであるステップＳ１４のセルの重なりほぐしにより、ステップＳ１２で局所配線混雑領域と判断された領域の配線リソースを確保することができる。
【０１００】
次いで、重なりほぐし処理部１１６は、ステップＳ１３でセルにＨａｌｏを再付与したことによるセルの重なりをほぐす（ステップＳ１４）。重なりほぐし処理部１１６は、Ｈａｌｏ格納部２０５を参照し、Ｈａｌｏを付与したサイズに基づいて、セルの重なりがほぐされ、その後のネットリストを配置後ネットリスト格納部２０６に格納する。セルの重なりほぐしは、一般的な配置技術に搭載されている機能を使用することでよい。この際、ステップＳ１３により、配線の混雑領域のレベルに応じて、セルにＨａｌｏを再付与しているため、セルの重なりをほぐすことで、配線混雑領域の配線リソースを確保できる。
【０１０１】
セルの重なりをほぐした後、ステップＳ１１の概略配線にもどり、ステップＳ１２で局所的な配線混雑領域が存在する場合は、再度ステップＳ１３でセルにＨａｌｏを付与して処理を繰返す。ステップＳ１２で局所的な配線混雑領域が存在しない場合、処理を終了する。
【０１０２】
近年、半導体集積回路のレイアウト設計において、半導体集積回路の回路規模の増加と論理接続の複雑化に伴い、回路素子と配線の混雑領域が発生し、一方で半導体集積回路の高周波数化によりタイミングを収束させるために回路素子と配線がさらに混雑化する傾向になっている。これにより、混雑緩和やタイミング収束のため、配置配線とタイミング解析を繰り返すイタレーションが増加している。このイタレーションの増加により、半導体集積回路の設計効率が悪化している。
【０１０３】
このため、本実施の形態では、半導体集積回路のレイアウト設計において、局所的な配線の混雑領域を発生させることなくタイミングを収束できる配置結果を求めることを可能にする。
【０１０４】
すなわち、上記のように本実施の形態では、ネット接続コストに対する配線リソースの不足に応じてセルにＨａｌｏを付与し、Ｈａｌｏを含めてセルを再配置するようにした。これにより、セルの配置を決める過程で、配線の混雑に応じた配置の疎密を作り、配線混雑の発生する領域を疎にして配線混雑を抑止し、疎にした配置領域にタイミングを収束させるためのリピータを配置することを可能とするため、局所的な配線混雑領域の発生を抑え、タイミングを収束させる効果がある。したがって、配線の混雑によりイタレーションを抑止し、設計効率を向上することができる。
【０１０５】
なお、従来のレイアウト設計方法として、セルを配置した後に概略配線を実行して配線混雑領域を改善する方法がある。この方法では、全てのセルを配置することから、局所的な配線混雑領域が集中した場合に、タイミング収束のイタレーションが増加する問題が発生する。これに対し、本実施の形態では、セルの配置処理中に、配線混雑を防ぐようにセルを配置するため、セル配置後のイタレーションを抑止することができる。
【０１０６】
また、従来のレイアウト設計方法として、ネットリストを構成するモジュール間の接続と各セルの接続から特定した配線混雑が予想される箇所のセルのサイズを膨らませた後に配置する方法もある。この方法では、配置領域と配置領域に存在する配線トラックを考慮することなく、ネットリストの構成に基づきセルのサイズを膨らませた後に全てのセルを配置することから、実際の配置領域と配線トラックを考えた場合、無駄なセルの膨らませによる面積増加や、セルの膨らませの不足により局所的な配線混雑領域が集中した場合、タイミング収束のイタレーションが増加する問題が発生する。これに対し、本実施の形態では、ネット接続コストに対する配線リソースの不足に応じてセルのＨａｌｏを付与するため、適切にＨａｌｏを付与し、効果的にイタレーションを抑止することができる。
【０１０７】
また、上記特許文献２は、概略配線、詳細配線、レイアウト検証の各工程の実行後に、配線ができない箇所に位置するセルのサイズを膨らませることにより配線リソースを確保するものである。特許文献２では、本実施の形態の持つ配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更する機能を持たないため、概略配線以降にセルのサイズを膨らませても局所配線混雑部に対し適切な状態で配線リソースを追加確保できず、レイアウトを収束させることができない。
【０１０８】
特許文献２が概略配線、詳細配線、レイアウト検証の各工程の実行後に、配線ができない箇所に位置するセルのサイズを膨らませているのに対し、本実施の形態では、配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更する。本実施の形態では、配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更することにより、配置結果そのものに局所配線混雑の領域を発生させないことを可能とする 
【０１０９】
また、上記特許文献３は、論理が同じセルは、駆動能力によらず同サイズにしておくことで低駆動セルについては配線領域の確保を可能にしている。また、セル内の配線禁止領域を取る、または、セルの左右に配線領域を付与しておくことで、配線リソースを確保することも記載されている。
【０１１０】
特許文献３では、本実施の形態の持つ配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更する機能を持たないため、一律にサイズを膨らませて配置することで配線混雑の発生していない箇所でサイズを膨らませることによる面積増加が発生し、最適面積でレイアウトを完了することができない。
【０１１１】
特許文献３が配置前に駆動能力に関係なく同機能のセルのサイズを同じサイズに膨らませている、つまり、配置・配線性に基づいたセルのサイズ変更ではないのに対し、本実施の形態では、配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更する。本実施の形態では、配置アルゴリズムの中で配線性を考慮して個別にセルサイズを変更することにより、配線混雑の発生する箇所のみセルのサイズを膨らませ、面積増を抑え、かつ、配線のできる配置結果を得ることを可能とする。
【０１１２】
（実施の形態２）
以下、図面を参照して実施の形態２について説明する。実施の形態１では、半導体集積回路の配置領域を分割しセルの配置を行ったのに対し、本実施の形態では、半導体集積回路の配置領域を分割せずにセルの配置を行う。その他については、実施の形態１と同様であるため、説明を適宜省略する。
【０１１３】
図１５は、本実施の形態に係る半導体集積回路のレイアウト設計装置の構成を示している。図１５のレイアウト設計装置１００は、実施の形態１の図４と比べて、セル配置処理部１１０が、配置領域分割処理部１１１、セル群分割処理部１１２、配置領域分割判定部１１４を有していない。その他の構成は、図４と同様である。本実施の形態では、セル群割付け処理部１１３は、半導体集積回路の配置領域（チップ全体の配置領域）に、ネットリストの全てのセルを配置する。セル群用ネット接続コスト算出処理部１２２は、半導体集積回路の配置領域に配置されたセル群のネット接続コストを算出する。配線リソース算出処理部１３０は、半導体集積回路の配置領域の配線リソースを算出する。
【０１１４】
図１６は、本実施の形態に係る半導体集積回路のレイアウト設計方法を示している。基本的に、図１６のフローチャートは、図５のフローチャートから領域分割の処理を除外した処理となる。
【０１１５】
図１６と図５との違いは、図５のカットラインによる配置領域分割（ステップＳ２）、セル群の分割（ステップＳ４）、セル群が十分少ないセル数となっているかの判断（ステップＳ１０）のステップを削除した点、分割領域の配線リソース算出（ステップＳ３）を分割領域ではなく、配置領域全体を対象とする配置領域の配線リソース算出（ステップＳ３１）に変更した点、および、分割領域へのセル群割付け（ステップＳ５）を、配置領域へのセル群の配置（ステップＳ５１）に変更した点である。
【０１１６】
すなわち、図１６に示すように、レイアウト設計装置１００は、半導体集積回路のネットリストに含まれる全てのセルごとに、入力端子数、出力端子数、および、出力端子に接続されるセル数に応じてネット接続コストを算出する（ステップＳ１）。
【０１１７】
次いで、レイアウト設計装置１００は、半導体集積回路の配置領域全体の配線リソースを、配線トラックに基づき算出する（ステップＳ３１）。
【０１１８】
次いで、レイアウト設計装置１００は、半導体集積回路の配置領域全体にセル面積の偏りがないようにセル群を配置し（ステップＳ５１）、セルにＨａｌｏが付与されている場合、Ｈａｌｏを削除する（ステップＳ６）。
【０１１９】
次いで、レイアウト設計装置１００は、ステップＳ１で算出したネット接続コストに基づき、配置領域のセル群のネット接続コストを算出し（ステップＳ７）、ステップＳ７で算出したネット接続コストに対し、ステップＳ３１で算出した配線トラックが不足している場合、セルを仮想的に膨らませるＨａｌｏを付与し、ステップＳ５１のセル群の配置に戻る（ステップＳ８、Ｓ９）。この場合、Ｈａｌｏを付与したセルのサイズで、セル群の配置を行う（ステップＳ５１〜Ｓ８）。
【０１２０】
次いで、レイアウト設計装置１００は、配線トラックが足りている場合、概略配線を実行し、局所的な配線混雑領域がないか確認する（ステップＳ１１、Ｓ１２）。
【０１２１】
レイアウト設計装置１００は、局所的な配線混雑が存在する場合には、その領域に含まれるセルに、セルを仮想的に膨らませるＨａｌｏを付与し、セルの重なりをほぐし、ステップＳ１１に戻る（ステップＳ１３、Ｓ１４）。また、レイアウト設計装置１００は、局所的な配線混雑領域がない場合、処理を完了する（ステップＳ１２）。
【０１２２】
以上のように本実施の形態では、配置領域を分割することなく、半導体集積回路全面の配置領域に対し、配線混雑が発生すると判断したセルに仮想的にサイズを膨らませるＨａｌｏを付与し、配置領域にセルを再度割り当てる。これにより、実施の形態１と同様に、セルの配置を決める過程で、各セルの論理接続を考慮し、配線混雑の発生する領域の配置を疎にすることで配線領域を確保することで、局所的な配線混雑領域の発生を抑え、タイミングを収束させることが可能となる。
【０１２３】
（実施の形態３）
本実施の形態は、実施の形態１に対し、半導体集積回路を階層ブロックに分割して、セルを配置する例である。本実施の形態のシステム構成は実施の形態１と同じであり、説明は省略する。半導体集積回路の回路規模が大きくなると、一般的に階層レイアウト設計法により、半導体集積回路を複数の階層ブロックに分割してレイアウトを実施する。
【０１２４】
この階層レイアウト設計を行なう際、図５のセルへのネット接続コスト算出処理（ステップＳ１）の後に、階層ブロックの分割を実施し、各分割されたブロックに対して図５のカットラインによる配置領域分割処理（ステップＳ２）以降の処理を実施することにより、階層ブロック内の配置を実施し、全ての階層ブロックの配置を終えたら、通常の階層レイアウト設計法に戻る。
【０１２５】
階層ブロック内にセルを配置する際に、配線の混雑する領域の配置を疎にして配線リソースを確保することで配線混雑を抑止し、配置が疎である領域にタイミング収束のためのセル移動とリピータを配置することで、階層レイアウト手法を適用した大規模ＬＳＩのレイアウトにおいて、局所的な配線混雑領域の発生を抑え、タイミングを収束させることができる。
【０１２６】
（実施の形態４）
本実施の形態は、実施の形態１に対し、セル群をグループ化して配置する例である。本実施の形態のシステム構成は実施の形態１と同じであり、説明は省略する。半導体集積回路を構成する機能単位にセル群をグループ化し、一箇所に固めて配置する、所謂、グループ配置が一般的に実施される。
【０１２７】
このグルーピングを行なう際、図５のセルへのネット接続コスト算出処理（ステップＳ１）の後に、グループ配置を実施し、図５のセル群の分割処理（ステップＳ４）と、分割領域へのセル群割付け処理（ステップＳ５）の処理で、配置されたグループを考慮する。
【０１２８】
半導体集積回路を構成する機能単位にセル群をグループ化して配置するグループ配置に本実施の形態を適用し、グルーピングを行なう際に、配線の混雑する領域の配置を疎にして配線リソースを確保することで配線混雑を抑止し、配置が疎である領域にタイミング収束のためのセル移動とリピータを配置することで、半導体集積回路を構成する機能単位にセル群をグループ化して配置するグループ配置において、局所的な配線混雑領域の発生を抑え、タイミングを収束させることができる。
【０１２９】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で 種々変更可能であることはいうまでもない。
【符号の説明】
【０１３０】
１      配線リソース算出部
２      セル配置部
３      ネット接続コスト算出部
４      仮想拡張領域付与部
５      セル再配置部
１０    コンピュータ装置
１１    本体部
１３    メインメモリ
１４    ハードディスク
１５    表示装置
１６    キーボード
１７    マウス
１８    レイアウト設計プログラム
１９    各種データ
２０    サーバ
２１    記録媒体
３０    ネットワーク
１００  レイアウト設計装置
１０１  処理部
１０２  格納部
１１０  セル配置処理部
１１１  配置領域分割処理部
１１２  セル群分割処理部
１１３  セル群割付け処理部
１１４  配置領域分割判定部
１１５  配線混雑領域確認処理部
１１６  重なりほぐし処理部
１２０  ネット接続コスト算出処理部
１２１  セル用ネット接続コスト算出処理部
１２２  セル群用ネット接続コスト算出処理部
１３０  配線リソース算出処理部
１４０  Ｈａｌｏ処理部
１４１  Ｈａｌｏ付与判定部
１４２  Ｈａｌｏ付与処理部
１４３  Ｈａｌｏ削除処理部
１４４  Ｈａｌｏ再付与処理部
１５０  概略配線処理部
２０１  配置前ネットリスト格納部
２０２  配置情報格納部
２０３  ネット接続コスト格納部
２０４  配線リソース格納部
２０５  Ｈａｌｏ格納部
２０６  配置後ネットリスト格納部
【図１】
2014089499.tif 000003
【図２】
2014089499.tif 000004
【図３】
2014089499.tif 000005
【図４】
2014089499.tif 000006
【図５】
2014089499.tif 000007
【図６】
2014089499.tif 000008
【図７】
2014089499.tif 000009
【図８】
2014089499.tif 000010
【図９】
2014089499.tif 000011
【図１０】
2014089499.tif 000012
【図１１】
2014089499.tif 000013
【図１２】
2014089499.tif 000014
【図１３】
2014089499.tif 000015
【図１４】
2014089499.tif 000016
【図１５】
2014089499.tif 000017
【図１６】
2014089499.tif 000018
【図１７】
2014089499.tif 000019