(57)【要約】【課題】フロアプランの的確な改善指標を早期に提示することにより、手戻りの多発を抑制し、設計期間の短縮化および設計品質の向上を図ること。【解決手段】設計支援装置２００では、配線長下限総和／配線リソース算出部２０２により配線長下限総和および配線リソースを算出し、判断部２０３により配線収束可能か否かを判断する。これにより前処理におけるスクリーニングが実行される。配線収束不可能な場合、配線リソース使用率算出部２０５により初期経路の配線リソース使用率を算出し、判断部２０３により配線収束可能か否かを判断する。これにより初期経路生成処理におけるスクリーニングが実行される。配線収束不可能な場合、配線リソース使用率算出部２０５により最適化配線経路の配線リソース使用率を算出し、判断部２０３により配線収束可能か否かを判断する。これにより最適化処理におけるスクリーニングが実行される。【選択図】        図２
2006268477.tif 000002
【特許請求の範囲】
【請求項１】
設計対象回路に関する回路情報を取得する取得手段と、
前記取得手段によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出する配線長下限総和／配線リソース算出手段と、
前記配線長下限総和／配線リソース算出手段によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断する判断手段と、
を備えることを特徴とする設計支援装置。
【請求項２】
前記判断手段によって配線収束可能であると判断された場合、前記チップデータ上に、前記ネットの配線経路を生成する配線経路生成手段と、
前記配線経路生成手段によって生成された配線経路と、前記配線リソースとに基づいて、前記配線経路に関する配線リソース使用率を算出する配線リソース使用率算出手段と、を備え、
前記判断手段は、
前記配線リソース使用率算出手段によって算出された配線リソース使用率に基づいて、前記ネットの配線収束可能性を判断することを特徴とする請求項１に記載の設計支援装置。
【請求項３】
設計対象回路に関する回路情報を取得する取得工程と、
前記取得工程によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出する配線長下限総和／配線リソース算出工程と、
前記配線長下限総和／配線リソース算出工程によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断する判断工程と、
を含んだことを特徴とする設計支援方法。
【請求項４】
設計対象回路に関する回路情報を取得させる取得工程と、
前記取得工程によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出させる配線長下限総和／配線リソース算出工程と、
前記配線長下限総和／配線リソース算出工程によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断させる判断工程と、
をコンピュータに実行させることを特徴とする設計支援プログラム。
【請求項５】
請求項４に記載の設計支援プログラムを記録したコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＬＳＩのレイアウト設計を支援する設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
従来から、配置後に配線性を見積もる従来技術として、各ネットのバウンディングボックスに基づいて混雑度を見積もる手法がある。この手法では、各ネットの配線は最短経路をとるため、実際の配線で起こり得る、障害物や混雑度領域の迂回発生が見積もれない。したがって、実際の配線よりも楽観的に混雑度を見積もることになる。
【０００３】
この楽観性を避けるために、通常の配線をある程度おこなって混雑度を見積もる手法もある。この手法では見積もりの精度は向上するが、もともと配線性の厳しい回路の場合、最適解を見つけるのに時間がかかるという問題が起こる。また、配線性に問題がある場合に、何を改善すればよいかを見つけるのは設計者のスキルに依存する部分が大きい。
【０００４】
このような混雑度を見積もるレイアウト方法としては、たとえば、下記特許文献１および２が挙げられる。特許文献１では、配置後に初期概略配線を行い、その経路に基づき遅延解析を行う。違反がある場合は配置まで手戻りし、それ以外は詳細配線を行う。その際、制約の厳しいネットは初期概略経路を守って配線し、それ以外のネットは混雑度を緩和するように配線する。また、特許文献２では、詳細配線結果に基づき遅延解析を行い、違反のあった部分回路を抽出し、論理再最適化および部分再レイアウトを行う。
【０００５】
【特許文献１】特開２０００−１７２７３８号公報
【特許文献２】特開２０００−０２９９１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、近年の回路の集積度向上および大規模化に伴い、タイミングやシグナルインテグリティ（ＳＩ）の制約が厳しくなる一方、フロアプラン段階ではクロック形状や配線経路などの不確定要因が大きく、配線性、タイミングおよびＳＩを精度良く判断するためにはクロック生成や配置配線フローまでを実行する必要がある。このようにクロック生成や配置配線フローまで実行すると迂回設計になる場合が多く、手戻りが多発して設計期間が長期化するという問題があった。
【０００７】
また、フロアプランが配線性、タイミングおよびＳＩを満たしていない場合、何を改善すればよいかは、実行ログの解析や過去のノウハウから設計者が判断するものである。したがって、効率的な改善ができるかどうかは設計者のスキルに依存するため、上記制約下において配線性が確保できるようなフロアプランの作成が困難であり、設計品質が低下するという問題があった。
【０００８】
また、上記特許文献１の従来技術では、詳細配線において混雑度の緩和がおこなうこととしているが、概略経路が初期概略配線して違反なしと判断しても、詳細経路で制約違反となるリスクが高くなり、上述したようにフロアプランの作成が困難であり、設計品質が低下するという問題があった。また、配線混雑度が高く配線収束しない回路では、配線収束をさせることが必要であるため、手戻りが多発することとなり、上述したように設計期間が長期化するという問題があった。
【０００９】
また、上記特許文献２の従来技術では、詳細配線経路に基づいた遅延解析、すなわち、レイアウトの収束段階において制約違反部分に関する領域だけを最適化しようとするものであるため、レイアウトの初期段階における制約違反を検出することができない。したがって、上述したように手戻りが多発することとなり、設計期間が長期化するという問題があった。
【００１０】
この発明は、上述した従来技術による問題点を解消するため、ＬＳＩのレイアウト設計において、フロアプランの的確な改善指標を早期に提示することにより、手戻りの多発を抑制し、設計期間の短縮化および設計品質の向上を図ることができる設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、この発明にかかる設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体は、設計対象回路に関する回路情報を取得し、取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出し、算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断することを特徴とする。
【００１２】
また、上記発明において、配線収束可能であると判断された場合、前記チップデータ上に、前記ネットの配線経路を生成し、生成された配線経路と、前記配線リソースとに基づいて、前記配線経路に関する配線リソース使用率を算出し、算出された配線リソース使用率に基づいて、前記ネットの配線収束可能性を判断することとしてもよい。
【００１３】
また、上記発明において、配線収束可能であると判断された場合、前記配線経路を最適化し、最適化された配線経路（以下、「最適化配線経路」という）と、前記配線リソースとに基づいて、前記最適化配線経路に関する配線リソース使用率を算出し、算出された前記最適化配線経路に関する配線リソース使用率に基づいて、前記ネットの配線収束可能性を判断することとしてもよい。
【００１４】
また、上記発明において、配線収束不可能であると判断された場合、前記ネットの配線収束可能性に関する改善情報を生成することとしてもよい。
【００１５】
また、上記発明において、配線収束不可能であると判断された配線経路を最適化することにより、概略配線経路を生成し、生成された概略配線経路を前記改善情報として出力することとしてもよい。
【００１６】
また、上記発明において、前記概略配線経路と、前記配線リソースとに基づいて、前記概略配線経路に関する配線リソース使用率を算出し、前記概略配線経路に関する配線リソース使用率に基づいて、前記概略配線経路の混雑度をあらわす配線混雑度マップを生成し、生成された配線混雑度マップを前記改善情報として出力することとしてもよい。
【００１７】
また、上記発明において、前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付け、前記概略配線経路に関する配線リソース使用率に基づいて、前記概略配線経路がマッピングされた前記チップデータ上の配線混雑領域を検出し、検出された配線混雑領域の中から、前記入力手段によって入力されたクリティカルネットではないネット（以下、「非クリティカルネット」という）を抽出し、抽出された非クリティカルネットに関する改善指標を、前記改善情報として出力することとしてもよい。
【００１８】
また、上記発明において、前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付け、入力されたクリティカルネットの配線経路が迂回経路か否かを判定し、判定された判定結果に基づいて、前記クリティカルネットに関する改善指標を、前記改善情報として出力することとしてもよい。
【００１９】
また、上記発明において、配線収束可能であると判断された場合、前記最適化配線経路を前記ネットの概略配線経路として出力することとしてもよい。
【００２０】
また、上記発明において、前記最適化配線経路に関する配線リソース使用率に基づいて、前記最適化配線経路の混雑度をあらわす配線混雑度マップを生成し、生成された配線混雑度マップを前記改善情報として出力することとしてもよい。
【００２１】
また、上記発明において、前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付け、入力されたクリティカルネットに関する改善指標を生成することとしてもよい。
【００２２】
これらの発明によれば、概略配線の前処理、初期経路生成および経路最適化の各段階において、配線性を満たすかどうかを判断することができる。また、配線性を満たさないネットをふるい落とすことによって、配線性の早期判断を提示することができる。また、前処理において配線性を満たさないと判断した場合でも、概略配線経路、配線混雑度およびそれらに基づいて自動的に判断された混雑度の改善指標を出力することもできる。
【００２３】
さらに、概略配線経路に基づいて、タイミング解析ツールやシグナルインテグリティ解析ツールを用いてチェックを行った解析結果から得られるクリティカルネットの改善方法を判断することもできる。また、フロアプラン後の配置・配線フローにおいても、フロアプランの効率的な改善指標を提示することができる。
【発明の効果】
【００２４】
本発明にかかる設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体によれば、ＬＳＩのレイアウト設計において、フロアプランの的確な改善指標を早期に提示することにより、手戻りの多発を抑制し、設計期間の短縮化および設計品質の向上を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２５】
以下に添付図面を参照して、この発明にかかる設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体の好適な実施の形態を詳細に説明する。
【００２６】
（設計支援装置のハードウェア構成）
まず、この発明の実施の形態にかかる設計支援装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる設計支援装置のハードウェア構成を示すブロック図である。
【００２７】
図１において、設計支援装置は、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、ＨＤＤ（ハードディスクドライブ）１０４と、ＨＤ（ハードディスク）１０５と、ＦＤＤ（フレキシブルディスクドライブ）１０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）１０７と、ディスプレイ１０８と、Ｉ／Ｆ（インターフェース）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１００によってそれぞれ接続されている。
【００２８】
ここで、ＣＰＵ１０１は、設計支援装置の全体の制御を司る。ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。ＨＤＤ１０４は、ＣＰＵ１０１の制御にしたがってＨＤ１０５に対するデータのリード／ライトを制御する。ＨＤ１０５は、ＨＤＤ１０４の制御で書き込まれたデータを記憶する。
【００２９】
ＦＤＤ１０６は、ＣＰＵ１０１の制御にしたがってＦＤ１０７に対するデータのリード／ライトを制御する。ＦＤ１０７は、ＦＤＤ１０６の制御で書き込まれたデータを記憶したり、ＦＤ１０７に記憶されたデータを設計支援装置に読み取らせたりする。
【００３０】
また、着脱可能な記録媒体として、ＦＤ１０７のほか、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、メモリーカードなどであってもよい。ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３１】
Ｉ／Ｆ１０９は、通信回線を通じてインターネットなどのネットワーク１１４に接続され、このネットワーク１１４を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３２】
キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００３３】
スキャナ１１２は、画像を光学的に読み取り、設計支援装置内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００３４】
（設計支援装置の機能的構成）
つぎに、この発明の実施の形態にかかる設計支援装置の機能的構成について説明する。図２は、この発明の実施の形態にかかる設計支援装置の機能的構成を示すブロック図である。図２において、設計支援装置２００は、取得部２０１と、配線長下限総和／配線リソース算出部２０２と、判断部２０３と、初期配線経路生成部２０４と、配線リソース使用率算出部２０５と、配線経路最適化部２０６と、改善情報生成部２０７と、から構成されている。
【００３５】
まず、取得部２０１は、設計対象回路に関する回路情報２１０を取得する。ここで、回路情報２１０には、たとえば、設計対象回路の接続情報を示すネットリストや、設計対象回路に含まれる電源などの障害物データが含まれる。
【００３６】
また、配線長下限総和／配線リソース算出部２０２は、取得部２０１によって取得された回路情報２１０に含まれているネットの配線長下限の総和と、回路情報２１０に含まれている設計対象回路内の障害物データがマッピングされたチップデータの配線リソースとを算出する。ここで、まず、配線長下限総和／配線リソース算出部２０２による算出処理について具体的に説明する。図３は、この発明の実施の形態にかかる実施の形態におけるチップデータを示す説明図であり、図４は、この発明の実施の形態にかかるバウンディングボックスを示す説明図である。
【００３７】
図３において、配線長下限総和／配線リソース算出部２０２は、チップデータ３００をグローバルセルＧと呼ばれる複数の矩形領域に分割する。各グローバルセルＧには、複数本の配線トラックＴが平行に引かれている。また、障害物データＯは、チップデータ３００上の配置位置となる座標を有しており、この座標を手掛かりとしてグローバルセルＧ上に配置される。これにより、グローバルセルＧの各配線トラックＴが空いているか障害物データＯで塞がっているかを判定することができる。
【００３８】
また、図４において、配線長下限総和／配線リソース算出部２０２は、回路情報２１０であるネットリスト内の各ネットＮ（Ｎ１，・・・，Ｎｉ，・・・，Ｎｎ）のバウンディングボックスＢ（Ｂ１，・・・，Ｂｉ，・・・，Ｂｎ）を用いて、ｘ方向の配線長下限お
よびｙ方向の配線長下限を算出する。バウンディングボックスＢは、任意のネットＮｉの端子ｔｉを包含する最小矩形である。
【００３９】
たとえば、ネットＮｉが端子ｔｉ１、ｔｉ２の接続情報を示しているとすると、各端子ｔｉ１、ｔｉ２が有する座標から、図４に示すバウンディングボックスＢｉを形成することができる。ここで、端子ｔｉ１の座標を（ｓｉ_ｘ，ｓｉ_ｙ）、端子ｔｉ２の座標を
（ｅｉ_ｘ，ｅｉ_ｙ）とすると、ネットＮｉの配線長下限Ｌｉは、下記式（１）によっ
て算出することができる。
【００４０】
Ｌｉ＝｜ｅｉ_ｘ−ｓｉ_ｘ｜＋｜ｅｉ_ｙ−ｓｉ_ｙ｜・・・（１）
【００４１】
また、式（１）から、ネットＮｉのｘ方向における配線長下限Ｌｉ_ｘは下記式（２）
によって、ｙ方向における配線長下限Ｌｉ_ｙは下記式（３）によってあらわすことがで
きる。
【００４２】
Ｌｉ_ｘ＝｜ｅｉ_ｘ−ｓｉ_ｘ｜・・・（２）
Ｌｉ_ｙ＝｜ｅｉ_ｙ−ｓｉ_ｙ｜・・・（３）
【００４３】
これにより、全ネットＮにおける、ｘ方向に必要な配線長下限Ｌｉ_ｘの総和Ｌｘは下
記式（４）によって、ｙ方向に必要な配線長下限Ｌｉ_ｙの総和Ｌｙは下記式（５）によ
ってあらわすことができる。
【００４４】
【数１】
2006268477.tif 000003
【００４５】
また、チップデータ３００全体の配線リソースをｘ方向およびｙ方向にわけて算出する
。具体的には、ｘ方向の配線トラックＴｘの空き部分の長さの総和から配線リソースＡｘを算出する。同様に、ｙ方向の配線トラックＴｙの空き部分の長さの総和から配線リソースＡｙを算出する。
【００４６】
図５は、ｘ方向のチップデータ３００を示す説明図であり、図６は、ｙ方向のチップデータ３００を示す説明図である。まず、図５において、チップデータ３００ｘには、障害物データＯ１（縦ｈ１、幅ｗ１），Ｏ２（縦ｈ２、幅ｗ２）がマッピングされている。長さｌｘの配線トラックＴｘの数をｆ本（図５では４本）とすると、ｘ方向の配線リソースＡｘは、下記式（６）によってあらわされる。
【００４７】
Ａｘ＝ｆ×ｌｘ−ｗ１×ｈ１−ｗ２×ｈ２・・・（６）
【００４８】
また、図６において、チップデータ３００ｙには、障害物データＯ３（縦ｈ３、幅ｗ３），Ｏ４（縦ｈ４、幅ｗ４）がマッピングされている。長さｌｙの配線トラックＴｙの数をｇ本（図６では４本）とすると、ｙ方向の配線リソースＡｙは、下記式（７）によってあらわされる。
【００４９】
Ａｙ＝ｇ×ｌｙ−ｗ３×ｈ３−ｗ４×ｈ４・・・（７）
【００５０】
また、図２において、判断部２０３は、配線長下限総和／配線リソース算出部２０２によって算出された配線長下限（Ｌｉ_ｘ、Ｌｉ_ｙ）の総和（Ｌｘ、Ｌｙ）と配線リソー
ス（Ａｘ、Ａｙ）とに基づいて、チップデータ３００にマッピングされるネットＮの配線収束可能性を判断する。具体的には、下記式（８）または（９）が成立する場合、配線収束不可能と判断する。
【００５１】
Ａｘ＜Ｌｘ・・・（８）
Ａｙ＜Ｌｙ・・・（９）
【００５２】
この配線長下限総和／配線リソース算出部２０２による配線長下限（Ｌｉ_ｘ、Ｌｉ_
ｙ）の総和（Ｌｘ、Ｌｙ）と配線リソース（Ａｘ、Ａｙ）の算出処理と、判断部２０３による配線長下限（Ｌｉ_ｘ、Ｌｉ_ｙ）の総和（Ｌｘ、Ｌｙ）と配線リソース（Ａｘ、Ａ
ｙ）を用いた判断処理は、ＬＳＩの概略配線における前処理段階、初期経路生成段階および最適化段階のうち、前処理段階に関するスクリーニング処理である。
【００５３】
また、図２において、初期配線経路生成部２０４は、判断部２０３によって配線収束可能であると判断された場合、チップデータ３００上に、初期経路となるネットＮｉの配線
経路Ｒａｉを生成する。この場合、配線混雑度、タイミング、ＳＩは考慮せず、迂回経路
は障害物を迂回する際に発生するもののみとする。
【００５４】
また、配線リソース使用率算出部２０５は、全ネットＮの配線経路Ｒａが生成されたチップデータ３００におけるグローバルセルＧ毎の配線リソース使用率ｇｒ_ｋを算出する。配線リソース使用率ｇｒ_ｋとは、グローバルセルＧｋ（ｋはグローバルセルＧの番号）中の空いている配線トラックＴのうちどれだけの割合が配線に占められているかであり、グローバルセルＧｋの配線リソース使用率ｇｒ_ｋを以下のように定義する。
【００５５】
ｇｒ_ｋ＝（Ｇｋ内で使用される配線トラック長）／（Ｇｋの空き配線トラック長）
・・・（１０）
【００５６】
この場合、上述した判断部２０３では、配線リソース使用率ｇｒ_ｋ＞１となるグローバルセルＧｋを容量あふれグローバルセルＧｋｆとし、容量あふれグローバルセルＧｋｆが下記の条件（ア）を満たさなかった場合、配線収束可能と判断して、配線経路（初期経路）Ｒａを出力する。図７は、配線経路（初期経路）Ｒａがマッピングされたチップデータ３００を示す説明図である。一方、下記の条件（ア）を満たした場合、配線収束不可能と判断する。図８は、容量あふれグローバルセルＧｋｆを有するチップデータ３００を示す説明図である。
【００５７】
・条件（ア）：『図８において、チップデータ３００全体をｐ×ｑのグローバルセルＧｋで分割する場合、容量あふれグローバルセルＧｋｆがα［％］以上を占めるｒ×ｓの矩形領域Ｆが１つ以上存在する。』
【００５８】
この初期配線経路生成部２０４による配線経路（初期経路）Ｒの生成処理と、配線リソース使用率算出部２０５による配線経路（初期経路）Ｒａに関する配線リソース使用率ｇｒ_ｋの算出処理と、判断部２０３による配線経路（初期経路）Ｒａに関する配線リソース使用率ｇｒ_ｋを用いた判断処理は、ＬＳＩの概略配線における前処理段階、初期経路生成段階および最適化段階のうち、初期経路生成段階に関するスクリーニング処理である。
【００５９】
また、図２において、配線経路最適化部２０６は、判断部２０３によって配線収束可能であると判断された場合、すなわち、上記条件（ア）を満たさなかった場合、初期経路である配線経路Ｒａを最適化する。この最適化処理をさらに複数段階にわける。このわけ方は、たとえば一般的な最適化のイタレーション（ｉｔｅｒａｔｉｏｎ）毎とする。具体的には、この最適化イタレーションでは、ネットＮを１本ごとに経路修正する。経路修正の方法は、前回の最適化イタレーションにおけるネットＮのコストよりも、コストが小さくなる経路があればその経路を選択し、ない場合には前回の最適化イタレーションでの経路を維持する。
【００６０】
この場合、上述した判断部２０３では、イタレーション毎に容量あふれグローバルセルＧｋｆを調べ、以下の条件（イ）を満たした場合、配線収束不可能と判断する。
【００６１】
・条件（イ）：『図８において、チップデータ３００全体をｐ×ｑのグローバルセルＧｋで分割する場合、最適化イタレーションｊにおいて容量あふれグローバルセルＧｋｆがβ［％］以上を占めるｒ×ｓの矩形領域Ｆが１つ以上存在する。』
【００６２】
この配線経路最適化部２０６による配線経路（初期経路）Ｒａの最適化処理と、配線リソース使用率算出部２０５による最適化配線経路Ｒｂに関する配線リソース使用率ｇｒ_ｋの算出処理と、判断部２０３による最適化配線経路Ｒｂに関する配線リソース使用率ｇｒ_ｋを用いた判断処理は、ＬＳＩの概略配線における前処理段階、初期経路生成段階および最適化段階のうち、最適化段階に関するスクリーニング処理である。
【００６３】
また、図２において、改善情報生成部２０７は、判断部２０３によって判断された判断結果に基づいて、ネットの配線収束可能性に関する改善情報を生成する。具体的には、下記（ｉ）〜（iv）の判断結果の場合に、改善情報を生成する。
【００６４】
（ｉ）  前処理段階において配線収束不可能と判断された場合
（ii）  初期経路生成段階において配線収束不可能と判断された場合
（iii）  最適化段階において配線収束不可能と判断された場合
（iv）  前処理段階、初期経路生成段階および最適化段階においてすべて配線収束可能と判断された場合
【００６５】
ここで、改善情報生成部２０７の具体的な構成について説明する。図９は、改善情報生成部２０７の具体的な機能的構成を示すブロック図である。図９において、改善情報生成部２０７は、入力部９０１と、概略配線経路生成部９０２と、配線混雑度マップ生成部９０３と、迂回判定部９０４と、改善指標出力部９０５と、検出部９０６と、抽出部９０７と、から構成されている。
【００６６】
まず、入力部９０１は、上述した判断部２０３による判断結果（ｉ）〜（iv）や、ネットＮをタイミング解析・ＳＩ解析結果となるクリティカルネットの入力を受け付ける。概略配線経路生成部９０２は、判断結果（ｉ）〜（iii）が入力された場合、その判断結果（ｉ）〜（iii）の判断元となる配線経路を最適化することにより、概略配線経路を生成する。
【００６７】
具体的には、判断結果（ｉ）の場合、取得部２０１によって取得された回路情報２１０であるネットリスト内のネットＮをチップデータ３００にマッピングすることで概略配線経路Ｒｃを生成する。また、概略配線経路生成部９０２は、判断結果（ii）の場合、初期配線経路生成部２０４によって生成された配線経路Ｒａを最適化することにより、概略配線経路Ｒｃを生成する。さらに、判断結果（iii）の場合、配線経路最適化部２０６における最適化配線経路Ｒｂを最適化することにより、概略配線経路Ｒｃを生成する。また、生成された概略配線経路Ｒｃは改善情報として出力される。
【００６８】
この最適化の手法としては、たとえば、各ネットＮｉのコストを算出することによって最適化することができる。具体的には、ネットＮｉの配線経路Ｒａｉ（Ｒｂｉ）とは異なる他の配線経路を探索し、探索経路のコストＣを、下記式（１１）により算出する。
【００６９】
Ｃ＝ａ×（ネットＮｉの線長）＋ｂ×（ネットＮｉが通過する領域の混雑度）＋ｃ
・・・（１１）
【００７０】
式（１１）において、ａ〜ｃは任意の係数である。また、『ネットＮｉが通過する領域の混雑度』とは、ネットＮｉが通過する領域内に存在する他のネットの本数である。なお、係数ｂについては、判断結果（ｉ）、（iv）の場合、ｂ＝０であり、判断結果（ii）の場合、ｂ＝ｂ１＞０であり、判断結果（iii）の場合、ｂ＝ｂ２＞ｂ１である。ネットＮｉにおいて、探索経路のコストＣｉが最小となる探索経路をネットＮｉのあらたな配線経路Ｒｃｉに設定する。これにより、概略配線経路Ｒｃを生成することができる。
【００７１】
また、判断結果（iv）の場合、配線経路最適化部２０６における最適化配線経路Ｒｂを概略配線経路Ｒｃとして出力する。図１０に、概略配線経路生成部９０２によって生成された概略配線経路Ｒｃを有するチップデータ３００の一例を示す。
【００７２】
また、配線混雑度マップ生成部９０３は、概略配線経路Ｒｃと概略配線経路Ｒｃに関する配線リソース使用率ｇｒ_ｋとに基づいて、概略配線経路Ｒｃの配線混雑度をあらわす配線混雑度マップというイメージデータを生成する。図１１に、配線混雑度マップ生成部９０３によって生成された配線混雑度マップ１１００の一例を示す。図１１において、配線混雑度を色の濃淡によってあらわしている。ここでは、色が濃くなるにしたがって配線混雑度が高いことを示している。
【００７３】
また図９において、迂回判定部９０４は、クリティカルネットの配線経路Ｒａｉ（またはＲｂｉ、Ｒｃｉ）が迂回経路か否かを判定する。図１２は、ネットＮｉの配線経路Ｒａｉ（またはＲｂｉ、Ｒｃｉ）を示す説明図である。図１２において、ネットＮｉがクリティカルネットであるとすると、端子ｔｉ１，ｔｉ２を含む最小矩形Ｓ１を設定し、この最小矩形Ｓ１を上下左右に均等に拡大して拡大矩形Ｓ２を設定する。ネットＮｉの配線経路Ｒａｉ（またはＲｂｉ、Ｒｃｉ）がすべて拡大矩形Ｓ２に包含されている場合は、ネットＮｉの配線経路Ｒａｉ（またはＲｂｉ、Ｒｃｉ）は迂回経路ではなく、拡大矩形Ｓ２からはみ出している経路ｒがある場合には、迂回経路であると判定する。
【００７４】
また、図９において、検出部９０６は、概略配線経路Ｒｃに関する配線リソース使用率ｇｒ_ｋ（ｇｒ_ｋ＞１）に基づいて、チップデータ３００上の配線混雑領域を検出する。この配線混雑領域とは、配線混雑度マップ１１００において、配線リソース使用率ｇｒ_ｋが所定のパーセント以上のグローバルセルＧｋの集合である。また、抽出部９０７は、検出部９０６によって検出された配線混雑領域の中から、クリティカルネットではないネット（以下、「非クリティカルネット」という）を抽出する。
【００７５】
また、改善指標出力部９０５は、配線混雑度に関する改善指標と、クリティカルネットに関する改善指標とを出力する。具体的には、判断結果（ｉ）の場合、ｘ方向またはｙ方向の配線リソースの不足、配線層または配線エリアの拡張に関する改善指標を出力する。また、クリティカルネットに関する改善指標も出力する。
【００７６】
また、判断結果（ii）、（iii）の場合、混雑度情報の詳細として、配線難易度、混雑領域の座標、混雑領域内のネットＩＤが出力される。また配線混雑度の具体的な改善指標として、『ネットリストを見直し入力ピン数やファンアウト数を減らす方が良いネット』、『フロアプランや配置を見直して配置される領域を変える方が良いネット』、または『配線層を考慮する方が良いネット』を出力する。クリティカルネットに関する改善指標に関しては、迂回判定部９０４による判定結果と抽出部９０７により抽出された非クリティカルネットに基づいて出力する。
【００７７】
また、判断結果（iv）の場合、配線混雑度に関する改善指標とクリティカルネットに関する改善指標を出力する。配線混雑度には問題がなく、クリティカルネットに関しては、『ネットＮｉを優先して配線する。』、『ネットＮｉを、配線層を制限して配線する。』または『ネットｎの形状を制限する』といった改善指標を出力する。
【００７８】
なお、図２に示した取得部２０１、配線長下限総和／配線リソース算出部２０２、判断部２０３、初期配線経路生成部２０４、配線リソース使用率算出部２０５、配線経路最適化部２０６、および改善情報生成部２０７は、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７などに記録されたプログラムを、ＣＰＵ１０１が実行することによって、または、Ｉ／Ｆ１０９によって、その機能を実現する。
【００７９】
（設計支援処理手順）
つぎに、この発明の実施の形態にかかる設計支援処理手順について説明する。図１３は、この発明の実施の形態にかかる設計支援処理手順を示すフローチャートである。図１３において、まず、回路情報２１０が取得された場合（ステップＳ１３０１：Ｙｅｓ）、前処理（ステップＳ１３０２）、初期経路生成処理（ステップＳ１３０３）、および最適化処理（ステップＳ１３０４）を実行する。
【００８０】
そして、概略配線経路Ｒｃ、配線混雑度マップ１１００および配線混雑度に関する改善指標を出力する（ステップＳ１３０５）。そして、クリティカルネットが入力された場合（ステップＳ１３０６：Ｙｅｓ）、クリティカルネットに関する改善指標を出力し（ステップＳ１３０７）、一連の処理を終了する。一方、クリティカルネットが入力されなかった場合（ステップＳ１３０６：Ｎｏ）、一連の処理を終了する。
【００８１】
つぎに、図１３に示した前処理（ステップＳ１３０２）の具体的な処理手順について説明する。図１４は、前処理（ステップＳ１３０２）の具体的な処理手順を示すフローチャートである。図１４において、まず、チップデータ３００をグローバルセルＧに分割する（ステップＳ１４０１）。つぎに、各グローバルセルＧに障害物データＯをマッピングし（ステップＳ１４０２）、ｘ方向の配線長下限Ｌｉ_ｘの総和Ｌｘおよびｙ方向の配線長
下限Ｌｉ_ｙの総和Ｌｙを算出する（ステップＳ１４０３）。
【００８２】
また、ｘ方向の配線リソースＡｘおよびｙ方向の配線リソースＡｙを算出する（ステップＳ１４０４）。このあと、ｘ方向の配線長下限Ｌｉ_ｘの総和Ｌｘおよび配線リソース
Ａｘと、ｙ方向の配線長下限Ｌｉ_ｙの総和およびＬｙ配線リソースＡｙから配線収束可
能か否かを判断する（ステップＳ１４０５）。配線収束可能である場合（ステップＳ１４０５：Ｙｅｓ）、初期経路生成処理（ステップＳ１３０３）に移行する。一方、配線収束不可能である場合（ステップＳ１４０５：Ｎｏ）、図１８に示す概略配線経路生成処理に移行する。
【００８３】
つぎに、図１３に示した初期経路生成処理（ステップＳ１３０３）の具体的な処理手順について説明する。図１５は、初期経路生成処理（ステップＳ１３０３）の具体的な処理手順を示すフローチャートである。図１５において、各ネットＮｉの初期経路を生成する（ステップＳ１５０１）。
【００８４】
つぎに、配線リソース使用率ｇｒ_ｋを算出し（ステップＳ１５０２）、チップデータ３００を分割したグローバルセルＧの中から、容量あふれグローバルセルＧｋｆを抽出する（ステップＳ１５０３）。そして、この容量あふれグローバルセルＧｋｆに基づき、配線収束可能か否かを判断する（ステップＳ１５０４）。配線収束可能である場合（ステップＳ１５０４：Ｙｅｓ）、最適化処理（ステップＳ１３０４）に移行する。一方、配線収束不可能である場合（ステップＳ１５０４：Ｎｏ）、図１８に示す概略配線経路生成処理に移行する。
【００８５】
つぎに、図１３に示した最適化処理（ステップＳ１３０４）の具体的な処理手順について説明する。図１６および図１７は、最適化処理（ステップＳ１３０４）の具体的な処理手順を示すフローチャートである。図１６において、ネット番号ｉをｉ＝１に、最適化イタレーション番号ｊをｊ＝１に設定する（ステップＳ１６０１）。つぎに、ネットＮｉの配線経路候補を探索し（ステップＳ１６０２）、探索が厳しいか否かを判断する（ステップＳ１６０３）。探索が厳しいか否かは、探索が不可能であるか探索が可能であっても所定時間以上かかる場合は探索が厳しいと判断する。
【００８６】
探索が厳しいと判断された場合（ステップＳ１６０３：Ｙｅｓ）、未選択の配線アルゴリズムがあるか否かを判定する（ステップＳ１６０４）。未選択の配線アルゴリズムがある場合（ステップＳ１６０４：Ｙｅｓ）、配線アルゴリズムを切り替える（ステップＳ１６０５）。すなわち、より探索範囲が広い配線アルゴリズムに切り替える。そして、ステップＳ１６０２に移行する。一方、未選択の配線アルゴリズムがない場合（ステップＳ１６０４：Ｎｏ）、図１８に示す概略配線経路生成処理に移行する。
【００８７】
また、ステップＳ１６０３において、探索が容易であった場合（ステップＳ１６０３：Ｎｏ）、探索経路ごとにネットＮｉのコストＣｉを算出する（ステップＳ１６０６）。コストＣｉの算出方法については、下記式（１２）を用いておこなう。
【００８８】
Ｃｉ＝ａ×（ネットＮｉの線長）＋ｂ×（ネットＮｉが通過する領域の混雑度）＋ｃ
・・・（１２）
【００８９】
このコストＣｉの算出処理の完了前にタイムアップになった場合（ステップＳ１６０７：Ｙｅｓ）、未選択の最適化パラメータがあるか否かを判定する（ステップＳ１６０８）。未選択の最適化パラメータがある場合（ステップＳ１６０８：Ｙｅｓ）、式（１２）中の最適化パラメータｂを、未選択の最適化パラメータｂに切り替えて（ステップＳ１６０９）、ステップＳ１６０６に移行する。一方、未選択の最適化パラメータｂがない場合（ステップＳ１６０８：Ｎｏ）、図１８に示す概略配線経路生成処理に移行する。
【００９０】
また、ステップＳ１６０７において、タイムアップにならなかった場合（ステップＳ１６０７：Ｎｏ）、図１７に示すステップＳ１７０１に移行する。図１７において、まず、最適化イタレーション：ｊ−１におけるネットＮｉのコストＣｉよりもコストが小さい探索経路があるか否かを判定する（ステップＳ１７０１）。
【００９１】
最適化イタレーション：ｊ−１におけるネットＮｉのコストＣｉよりもコストが小さい探索経路がある場合（ステップＳ１７０１：Ｙｅｓ）、当該探索経路を最適化イタレーション：ｊの配線経路に、当該コストＣｉを最適化イタレーション：ｊのコストに決定する（ステップＳ１７０２）。
【００９２】
一方、最適化イタレーション：ｊ−１におけるネットＮｉのコストＣｉよりもコストが小さい探索経路がない場合（ステップＳ１７０３：Ｎｏ）、最適化イタレーション：ｊ−１におけるネットＮｉの配線経路を最適化イタレーション：ｊの配線経路に、最適化イタレーション：ｊ−１におけるネットＮｉのコストＣｉを最適化イタレーション：ｊのコストに決定する（ステップＳ１７０３）
【００９３】
そして、ネット番号ｉをインクリメントして（ステップＳ１７０４）、ネット番号ｉが最終ネットＮｎのネット番号ｎより大きいか否かを判定する（ステップＳ１７０５）。ｉ＞ｎでない場合（ステップＳ１７０５：Ｎｏ）、図１６に示したステップＳ１６０２に移行する。一方、ｉ＞ｎの場合（ステップＳ１７０５：Ｙｅｓ）、最適化イタレーション番号ｊがｊ＝１か否かを判定する（ステップＳ１７０６）。
【００９４】
ｊ＝１の場合（ステップＳ１７０６：Ｙｅｓ）、最適化イタレーション番号ｊをインクリメントして（ステップＳ１７０７）、図１６に示したステップＳ１６０２に移行する。一方、ｊ＝１でない場合（ステップＳ１７０６：Ｎｏ）、最適化された配線経路について配線リソース使用率ｇｒ_ｋを算出し（ステップＳ１７０８）、チップデータ３００を分割したグローバルセルＧの中から、容量あふれグローバルセルＧｋｆを抽出する（ステップＳ１７０９）。
【００９５】
そして、この容量あふれグローバルセルＧｋｆに基づき、配線収束可能か否かを判断する（ステップＳ１７１０）。配線収束不可能である場合（ステップＳ１７１０：Ｎｏ）、図１８に示す概略配線経路生成処理に移行する。一方、配線収束可能である場合（ステップＳ１７１０：Ｙｅｓ）、最適化イタレーション番号ｊが最大値ｊmaxより大きいか否かを判定する（ステップＳ１７１１）。
【００９６】
ｊ＞ｊmaxの場合（ステップＳ１７１１：Ｙｅｓ）、図１３に示したステップＳ１３０５に移行する。一方、ｊ＞ｊmaxでない場合（ステップＳ１７１１：Ｎｏ）、最適化イタレーション：ｊにおける全ネットＮのコスト総和ΣＣ（j）と最適化イタレーション：ｊ
−１における全ネットＮのコスト総和ΣＣ（j−１）が等しいか否かを判定する（ステッ
プＳ１７１２）。
【００９７】
ΣＣ（j）＝ΣＣ（j−１）の場合（ステップＳ１７１２：Ｙｅｓ）、図１３に示した
ステップＳ１３０５に移行する。一方、ΣＣ（j）＝ΣＣ（j−１）でない場合（ステッ
プＳ１７１２：Ｎｏ）、ステップＳ１７０７に移行して、最適化イタレーション番号ｊをインクリメントする。
【００９８】
つぎに、概略配線経路生成処理手順について説明する。図１８は、概略配線経路生成処理手順を示すフローチャートである。図１８において、ネット番号ｉをｉ＝１に設定する
（ステップＳ１８０１）。つぎに、ネットＮｉの配線経路候補を探索する（ステップＳ１８０２）。探索経路ごとにネットＮｉのコストＣｉを算出する（ステップＳ１８０３）。コストＣｉの算出処理は、上述した式（１１）を用いておこなう。そして、コストＣｉが最小となる探索経路を選択する（ステップＳ１８０４）。
【００９９】
コストＣｉがコストしきい値Ｃthより小さいか否かを判定する（ステップＳ１８０５）。Ｃｉ＜Ｃthでない場合（ステップＳ１８０５：Ｎｏ）、未選択の最適化パラメータｂがあるか否かを判定する（ステップＳ１８０６）。未選択の最適化パラメータｂがある場合（ステップＳ１８０６：Ｙｅｓ）、上述した式（１１）の最適化パラメータｂを、あらたな最適化パラメータｂに切り替えて（ステップＳ１８０７）、ステップＳ１８０３に移行する。最適化パラメータｂを切り替えることにより、概略配線経路Ｒｃの生成を高速に実行することができる。
【０１００】
一方、未選択の最適化パラメータｂがない場合（ステップＳ１８０６：Ｎｏ）、未選択の配線アルゴリズムがあるか否かを判定する（ステップＳ１８０８）。未選択の配線アルゴリズムがある場合（ステップＳ１８０８：Ｙｅｓ）、現在の配線アルゴリズムから、より探索範囲が広い配線アルゴリズムに切り替え（ステップＳ１８０９）、ステップＳ１８０２に移行する。配線アルゴリズムを切り替えることにより、概略配線経路Ｒｃの生成を高速に実行することができる。
【０１０１】
一方、未選択の配線アルゴリズムがない場合（ステップＳ１８０８：Ｎｏ）、またはステップＳ１８０５においてＣｉ＜Ｃthの場合（ステップＳ１８０５：Ｙｅｓ）、ネット番号ｉをインクリメントし（ステップＳ１８１０）、ネット番号ｉが最終ネットＮｎのネット番号ｎより大きいか否かを判定する（ステップＳ１８１１）。
【０１０２】
ｉ＞ｎでない場合（ステップＳ１８１１：Ｎｏ）、ステップＳ１８０２に移行する。一方、ｉ＞ｎの場合（ステップＳ１８１１：Ｙｅｓ）、概略配線経路Ｒｃが生成される。そして、この概略配線経路Ｒｃに関する配線リソース使用率ｇｒ_ｋを算出し（ステップＳ１８１２）、配線混雑度マップ１１００を生成する（ステップＳ１８１３）。また、配線混雑度に関する改善指標を出力する（ステップＳ１８１４）。
【０１０３】
そして、クリティカルネットに関する改善指標出力処理を実行する（ステップＳ１８１５）。ここで、クリティカルネットに関する改善指標出力処理（ステップＳ１８１５）についての具体的な処理手順に説明する。図１９は、クリティカルネットに関する改善指標出力処理についての具体的な処理手順を示すフローチャートである。図１９において、クリティカルネットが入力されなかった場合（ステップＳ１９０１：Ｎｏ）、一連の処理を終了する。一方、クリティカルネットが入力された場合（ステップＳ１９０１：Ｙｅｓ）、図１２の（ａ）に示したように、クリティカルネットの端子を囲む最小矩形Ｓ１を生成する（ステップＳ１９０２）
【０１０４】
そして、図１２の（ｂ）に示したように、最小矩形Ｓ１を拡大して拡大矩形Ｓ２を生成する（ステップＳ１９０３）。そして、クリティカルネットの配線経路がすべて拡大矩形ＳＳ２に包含されているか否かを判定する（ステップＳ１９０４）。すべて包含されている場合（ステップＳ１９０４：Ｙｅｓ）、改善指標Ａ：『特定の層を優先して配線させる』を出力する（ステップＳ１９０５）。
【０１０５】
一方、すべて包含されていない場合（ステップＳ１９０４：Ｎｏ）、迂回が解消する可能性あるか否かを判定する（ステップＳ１９０６）。具体的には、たとえば、拡大矩形Ｓ２の面積の５０％以上が混雑領域であれば、『混雑領域を通過させれば迂回が解消する可能性が高い』と判定する。一方、拡大矩形Ｓ２の面積の５０％以上が障害物により通過できない領域であれば、『混雑領域を通過させても迂回が残る可能性が高い』と判定する。
【０１０６】
これにより、『混雑領域を通過させれば迂回が解消する可能性が高い』と判定された場合（ステップＳ１９０６：Ｙｅｓ）、改善指標Ｂ：『他のネットより優先して混雑領域を通過させる』を出力する（ステップＳ１９０７）。一方、『混雑領域を通過させても迂回が残る可能性が高い』と判定された場合（ステップＳ１９０６：Ｎｏ）、改善指標Ａを出力する（ステップＳ１９０５）。
【０１０７】
また、ステップＳ１９０５またはステップＳ１９０７のあと、混雑領域上のネットから非クリティカルネットが抽出された場合（ステップＳ１９０８：Ｙｅｓ）、改善指標Ｃ：『混雑領域を迂回可能である』を出力し（ステップＳ１９０９）、一連の処理を終了する。一方、非クリティカルネットが抽出されなかった場合（ステップＳ１９０８：Ｎｏ）、一連の処理を終了する。
【０１０８】
以上説明したように、この発明の実施の形態にかかる設計支援装置２００、設計支援方法、設計支援プログラムおよび記録媒体によれば、ＬＳＩのレイアウト設計において、フロアプランの的確な改善指標を早期に提示することにより、手戻りの多発を抑制し、設計期間の短縮化および設計品質の向上を図ることができる。
【０１０９】
なお、本実施の形態で説明した設計支援方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１１０】
（付記１）設計対象回路に関する回路情報を取得する取得手段と、
前記取得手段によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出する配線長下限総和／配線リソース算出手段と、
前記配線長下限総和／配線リソース算出手段によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断する判断手段と、
を備えることを特徴とする設計支援装置。
【０１１１】
（付記２）前記判断手段によって配線収束可能であると判断された場合、前記チップデータ上に、前記ネットの配線経路を生成する配線経路生成手段と、
前記配線経路生成手段によって生成された配線経路と、前記配線リソースとに基づいて、前記配線経路に関する配線リソース使用率を算出する配線リソース使用率算出手段と、を備え、
前記判断手段は、
前記配線リソース使用率算出手段によって算出された配線リソース使用率に基づいて、前記ネットの配線収束可能性を判断することを特徴とする付記１に記載の設計支援装置。
【０１１２】
（付記３）前記判断手段によって配線収束可能であると判断された場合、前記配線経路を最適化する配線経路最適化手段を備え、
前記配線リソース使用率算出手段は、
前記配線経路最適化手段によって最適化された配線経路（以下、「最適化配線経路」という）と、前記配線リソースとに基づいて、前記最適化配線経路に関する配線リソース使用率を算出し、
前記判断手段は、
前記配線リソース使用率算出手段によって算出された前記最適化配線経路に関する配線リソース使用率に基づいて、前記ネットの配線収束可能性を判断することを特徴とする付記２に記載の設計支援装置。
【０１１３】
（付記４）前記判断手段によって配線収束不可能であると判断された場合、前記ネットの配線収束可能性に関する改善情報を生成する改善情報生成手段を備えることを特徴とする付記１〜３のいずれか一つに記載の設計支援装置。
【０１１４】
（付記５）前記改善情報生成手段は、
前記判断手段によって配線収束不可能であると判断された配線経路を最適化することにより、概略配線経路を生成する概略配線経路生成手段を備え、
前記概略配線経路生成手段によって生成された概略配線経路を前記改善情報として出力することを特徴とする付記４に記載の設計支援装置。
【０１１５】
（付記６）前記配線リソース使用率算出手段は、
前記概略配線経路と、前記配線リソースとに基づいて、前記概略配線経路に関する配線リソース使用率を算出し、
前記改善情報生成手段は、
前記概略配線経路に関する配線リソース使用率に基づいて、前記概略配線経路の混雑度をあらわす配線混雑度マップを生成する配線混雑度マップ生成手段を備え、
前記配線混雑度マップ生成手段によって生成された配線混雑度マップを前記改善情報として出力することを特徴とする付記５に記載の設計支援装置。
【０１１６】
（付記７）前記改善情報生成手段は、
前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付ける入力手段と、
前記概略配線経路に関する配線リソース使用率に基づいて、前記概略配線経路がマッピングされた前記チップデータ上の配線混雑領域を検出する検出手段と、
前記検出手段によって検出された配線混雑領域の中から、前記入力手段によって入力されたクリティカルネットではないネット（以下、「非クリティカルネット」という）を抽出する抽出手段と、を備え、
前記抽出手段によって抽出された非クリティカルネットに関する改善指標を、前記改善情報として出力することを特徴とする付記６に記載の設計支援装置。
【０１１７】
（付記８）前記改善情報生成手段は、
前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付ける入力手段と、
前記入力手段によって入力されたクリティカルネットの配線経路が迂回経路か否かを判定する迂回判定手段と、を備え、
前記迂回判定手段によって判定された判定結果に基づいて、前記クリティカルネットに関する改善指標を、前記改善情報として出力することを特徴とする付記５または６に記載の設計支援装置。
【０１１８】
（付記９）前記判断手段によって配線収束可能であると判断された場合、前記最適化配線経路を前記ネットの概略配線経路として出力することを特徴とする付記３に記載の設計支援装置。
【０１１９】
（付記１０）前記改善情報生成手段は、
前記最適化配線経路に関する配線リソース使用率に基づいて、前記最適化配線経路の混雑度をあらわす配線混雑度マップを生成する配線混雑度マップ生成手段を備え、
前記配線混雑度マップ生成手段によって生成された配線混雑度マップを前記改善情報として出力することを特徴とする付記９に記載の設計支援装置。
【０１２０】
（付記１１）前記ネットをタイミング解析することによって得られるクリティカルネットの入力を受け付ける入力手段と、
前記入力手段によって入力されたクリティカルネットに関する改善指標を生成する改善指標生成手段と、
を備えることを特徴とする付記９または１０に記載の設計支援装置。
【０１２１】
（付記１２）設計対象回路に関する回路情報を取得する取得工程と、
前記取得工程によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出する配線長下限総和／配線リソース算出工程と、
前記配線長下限総和／配線リソース算出工程によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断する判断工程と、
を含んだことを特徴とする設計支援方法。
【０１２２】
（付記１３）設計対象回路に関する回路情報を取得させる取得工程と、
前記取得工程によって取得された回路情報に含まれているネットの配線長下限の総和と、前記回路情報に含まれている前記設計対象回路内の障害物に関するデータがマッピングされたチップデータの配線リソースとを算出させる配線長下限総和／配線リソース算出工程と、
前記配線長下限総和／配線リソース算出工程によって算出された配線長下限の総和と配線リソースとに基づいて、前記チップデータにマッピングされる前記ネットの配線収束可能性を判断させる判断工程と、
をコンピュータに実行させることを特徴とする設計支援プログラム。
【０１２３】
（付記１４）付記１３に記載の設計支援プログラムを記録したコンピュータに読み取り可能な記録媒体。
【産業上の利用可能性】
【０１２４】
以上のように、本発明にかかる設計支援装置、設計支援方法、設計支援プログラムおよび記録媒体は、ＬＳＩのレイアウト設計に有用であり、特に、レイアウト設計の見積もり処理に適している。
【図面の簡単な説明】
【０１２５】
【図１】この発明の実施の形態にかかる設計支援装置のハードウェア構成を示すブロック図である。
【図２】この発明の実施の形態にかかる設計支援装置の機能的構成を示すブロック図である。
【図３】この発明の実施の形態にかかるチップデータを示す説明図である。
【図４】この発明の実施の形態にかかるバウンディングボックスを示す説明図である。
【図５】ｘ方向のチップデータを示す説明図である。
【図６】ｙ方向のチップデータを示す説明図である。
【図７】配線経路（初期経路）がマッピングされたチップデータを示す説明図である。
【図８】容量あふれグローバルセルを有するチップデータを示す説明図である。
【図９】改善情報生成部の具体的な機能的構成を示すブロック図である。
【図１０】概略配線経路生成部によって生成された概略配線経路を有するチップデータの一例を示す説明図である。
【図１１】配線混雑度マップ生成部によって生成された配線混雑度マップの一例を示す説明図である。
【図１２】ネットの配線経路を示す説明図である。
【図１３】この発明の実施の形態にかかる設計支援処理手順を示すフローチャートである。
【図１４】前処理（ステップＳ１３０２）の具体的な処理手順を示すフローチャートである。
【図１５】初期経路生成処理（ステップＳ１３０３）の具体的な処理手順を示すフローチャートである。
【図１６】最適化処理（ステップＳ１３０４）の具体的な処理手順を示すフローチャート（その１）である。
【図１７】最適化処理（ステップＳ１３０４）の具体的な処理手順を示すフローチャート（その２）である。
【図１８】概略配線経路生成処理手順を示すフローチャートである。
【図１９】クリティカルネットに関する改善指標出力処理についての具体的な処理手順を示すフローチャートである。
【符号の説明】
【０１２６】
２００  設計支援装置
２０１  取得部
２０２  配線長下限総和／配線リソース算出部
２０３  判断部
２０４  初期配線経路生成部
２０５  配線リソース使用率算出部
２０６  配線経路最適化部
２０７  改善情報生成部
２１０  回路情報
３００（３００ｘ，３００ｙ）  チップデータ
９０１  入力部
９０２  概略配線経路生成部
９０３  配線混雑度マップ生成部
９０４  迂回判定部
９０５  改善指標出力部
９０６  検出部
９０７  抽出部
１１００  配線混雑度マップ
【図１】
2006268477.tif 000004
【図２】
2006268477.tif 000005
【図３】
2006268477.tif 000006
【図４】
2006268477.tif 000007
【図５】
2006268477.tif 000008
【図６】
2006268477.tif 000009
【図７】
2006268477.tif 000010
【図８】
2006268477.tif 000011
【図９】
2006268477.tif 000012
【図１０】
2006268477.tif 000013
【図１１】
2006268477.tif 000014
【図１２】
2006268477.tif 000015
【図１３】
2006268477.tif 000016
【図１４】
2006268477.tif 000017
【図１５】
2006268477.tif 000018
【図１６】
2006268477.tif 000019
【図１７】
2006268477.tif 000020
【図１８】
2006268477.tif 000021
【図１９】
2006268477.tif 000022