(57)【要約】【課題】  より規則的に並んだレイアウトを得ることによって、回路特性や配線性に優れたレイアウトを得ることができるようにすること。【解決手段】  ＣＰＵ１０１は、磁気ディスク記憶部１０４に記憶されたアレイ、ロウ等の規則構造情報を参照すると共にレイアウト図形情報、ネットリスト情報及び制約情報を用いて、集積回路のレイアウトにおける規則構造を抽出して評価し、前記規則構造の評価を考慮して、前記レイアウト図形情報、ネットリスト情報等を用いて、集積回路のレイアウトを最適化する。【選択図】  図１
2008140011.tif 000002
【特許請求の範囲】
【請求項１】
集積回路の設計に必要な設計情報を記憶する記憶手段と、
レイアウトにおける規則構造を抽出して前記レイアウトの規則性の評価を行う評価手段と、
前記設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、
前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化することを特徴とする集積回路設計装置。
【請求項２】
前記設計情報には、前記規則構造を表す規則性情報、レイアウト図形情報、ネットリスト情報、制約情報及びコスト情報が含まれ、
前記評価手段は、前記規則性情報を参照すると共に前記レイアウト図形情報、ネットリスト情報及び制約情報を用いて、前記規則構造を抽出して前記規則性の評価を行い、
前記最適化手段は、前記制約情報に含まれる制約を満足させると共に前記評価手段による規則性の評価を考慮して、前記レイアウト図形情報、ネットリスト情報及びコスト情報を用いて、前記集積回路のレイアウトを最適化することを特徴とする請求項１記載の集積回路設計装置。
【請求項３】
前記評価手段は、トポロジ的な規則構造及び物理的な規則構造に基づいて前記規則性の評価を行うことを特徴とする請求項２記載の集積回路設計装置。
【請求項４】
前記規則構造にはアレイ、ロウ、スライス、ルーム、オブジェクトの中の少なくとも１つが含まれて成り、
前記評価手段は、トポロジ的な規則構造に基づく規則性の評価を行う場合、前記規則構造の中の少なくとも１つの規則構造に基づいて評価を行うことを特徴とする請求項３記載の集積回路設計装置。
【請求項５】
前記評価手段は、物理的な規則構造に基づく規則性の評価を行う場合、局所詰め込み値及び局所均一値に基づいて評価を行うことを特徴とする請求項４記載の集積回路設計装置。
【請求項６】
コンピュータを、
レイアウトにおける規則構造を抽出して前記レイアウトの規則性の評価を行う評価手段と、
記憶手段に記憶された集積回路の設計に必要な設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、
前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化するように機能させることを特徴とする集積回路設計用プログラム。
【請求項７】
前記設計情報には、前記規則構造を表す規則性情報、レイアウト図形情報、ネットリスト情報、制約情報及びコスト情報が含まれ、
前記評価手段は、前記規則性情報を参照すると共に前記レイアウト図形情報、ネットリスト情報及び制約情報を用いて、前記規則構造を抽出して前記規則性の評価を行い、
前記最適化手段は、前記制約情報に含まれる制約を満足させると共に前記評価手段による規則性の評価を考慮して、前記レイアウト図形情報、ネットリスト情報及びコスト情報を用いて、前記集積回路のレイアウトを最適化するようにコンピュータを機能させることを特徴とする請求項６記載の集積回路設計用プログラム。
【請求項８】
前記評価手段は、トポロジ的な規則構造及び物理的な規則構造に基づいて前記規則性の評価を行うようにコンピュータを機能させることを特徴とする請求項７記載の集積回路設計用プログラム。
【請求項９】
前記規則構造にはアレイ、ロウ、スライス、ルーム、オブジェクトの中の少なくとも１つが含まれて成り、
前記評価手段は、トポロジ的な規則構造に基づく規則性の評価を行う場合、前記規則構造の中の少なくとも１つの規則構造に基づいて評価を行うようにコンピュータを機能させることを特徴とする請求項８記載の集積回路設計用プログラム。
【請求項１０】
前記評価手段は、物理的な規則構造に基づく規則性の評価を行う場合、局所詰め込み値及び局所均一値に基づいて評価を行うようにコンピュータを機能させることを特徴とする請求項８記載の集積回路設計用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路における回路要素のレイアウト設計等を行う集積回路設計装置、及び、コンピュータに実行させることによって前記集積回路設計装置を構築するのに適したプログラムに関する。
【背景技術】
【０００２】
従来から、ＬＳＩ（Large Scale Integrated Circuit）等の半導体集積回路において、回路要素に相当する図形データのレイアウト設計を行うために、集積回路設計装置が利用されている（例えば、特許文献１〜特許文献３参照）。
従来のレイアウト手法は、集積回路設計装置内部で、半導体集積回路の面積や配線長が各々最小になるようにレイアウトを行うようにしている。
【０００３】
さらに、その上で、回路要素のペア性や、シンメトリ性、要素の辺のアライメント性などの制約を付加することで、アナログ設計者が設計した場合と同様のレイアウトを自動生成するように構成されている。
これにより、より規則的に並んだレイアウトを得ることによって、良好な回路特性、配線が容易等の良好な配線性を持つレイアウト結果を得るようにしている。
【０００４】
しかしながら前記従来の手法では、付加的な制約がつけられていない回路要素については、かならずしも規則的に並ぶ保証がなく、もし保証するために全ての回路要素に制約をつけようとすると、制約の矛盾が起きたり、あるいは制約を付加する手間が極めて煩雑になるという問題がある。また、全ての回路要素が規則的に並ぶような制約を付加することは困難という問題がある。特にこれらの問題は、回路要素の大きさが不揃いなアナログ集積回路の設計において顕著である。
したがって、半導体集積回路設計装置によって自動で生成されたレイアウトでは、良好な回路特性を得ることができず又、良好な配線を容易に行うことが困難であり、レイアウト設計者に受け入れられないことが多いという問題がある。
【０００５】
【特許文献１】特開２００４−２３４４５０号公報
【特許文献２】特開２００５−０６２９４３号公報
【特許文献３】特開２００５−２６７２９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
本発明は、より規則的に並んだレイアウトを得ることによって、回路特性や配線性が優れたレイアウトを得ることができるようにすることを課題としている。
また、本発明は、コンピュータを用いて前記集積回路設計装置を構築するのに好適な集積回路設計用プログラムを提供することを課題としている。
【課題を解決するための手段】
【０００７】
本発明によれば、集積回路の設計に必要な設計情報を記憶する記憶手段と、レイアウトにおける規則構造を抽出して、レイアウトの規則性の評価を行う評価手段と、前記設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化することを特徴とする集積回路設計装置が提供される。
【０００８】
評価手段は、レイアウトにおける規則構造を抽出して前記レイアウトの規則性の評価を行う。最適化手段は、前記設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化する。
【０００９】
ここで、前記設計情報には、前記規則構造を表す規則性情報、レイアウト図形情報、ネットリスト情報、制約情報及びコスト情報が含まれ、前記評価手段は、前記規則性情報を参照すると共に前記レイアウト図形情報、ネットリスト情報及び制約情報を用いて、前記規則構造を抽出して前記規則性の評価を行い、前記最適化手段は、前記制約情報に含まれる制約を満足させると共に前記評価手段による規則性の評価を考慮して、前記レイアウト図形情報、ネットリスト情報及びコスト情報を用いて、前記集積回路のレイアウトを最適化するように構成してもよい。
【００１０】
また、前記評価手段は、トポロジ的な規則構造及び物理的な規則構造に基づいて前記規則性の評価を行うように構成してもよい。
また、前記規則構造にはアレイ、ロウ、スライス、ルーム、オブジェクトの中の少なくとも１つが含まれて成り、前記評価手段は、トポロジ的な規則構造に基づく規則性の評価を行う場合、前記規則構造の中の少なくとも１つの規則構造に基づいて評価を行うように構成してもよい。
【００１１】
また、前記評価手段は、物理的な規則構造に基づく規則性の評価を行う場合、局所詰め込み値及び局所均一値に基づいて評価を行うように構成してもよい。
また、本発明によれば、コンピュータを、レイアウトにおける規則構造を抽出して前記レイアウトの規則性の評価を行う評価手段と、記憶手段に記憶された集積回路の設計に必要な設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化するように機能させることを特徴とする集積回路設計用プログラムが提供される。
【００１２】
コンピュータは、集積回路設計用プログラムを実行することにより、レイアウトにおける規則構造を抽出して前記レイアウトの規則性の評価を行う評価手段と、記憶手段に記憶された集積回路の設計に必要な設計情報に基づいて集積回路のレイアウトを最適化する最適化手段とを備え、前記最適化手段は、前記評価手段による規則性の評価を考慮して、前記集積回路のレイアウトを最適化するように機能する。
【００１３】
ここで、前記設計情報には、前記規則構造を表す規則性情報、レイアウト図形情報、ネットリスト情報、制約情報及びコスト情報が含まれ、前記評価手段は、前記規則性情報を参照すると共に前記レイアウト図形情報、ネットリスト情報及び制約情報を用いて、前記規則構造を抽出して前記規則性の評価を行い、前記最適化手段は、前記制約情報に含まれる制約を満足させると共に前記評価手段による規則性の評価を考慮して、前記レイアウト図形情報、ネットリスト情報及びコスト情報を用いて、前記集積回路のレイアウトを最適化するようにコンピュータを機能させるよう前記集積回路設計用プログラムを構成してもよい。
【００１４】
また、前記評価手段は、トポロジ的な規則構造及び物理的な規則構造に基づいて前記規則性の評価を行うようにコンピュータを機能させるよう前記集積回路設計用プログラムを構成してもよい。
また、前記規則構造にはアレイ、ロウ、スライス、ルーム、オブジェクトの中の少なくとも１つが含まれて成り、前記評価手段は、トポロジ的な規則構造に基づく規則性の評価を行う場合、前記規則構造の中の少なくとも１つの規則構造に基づいて評価を行うようにコンピュータを機能させるよう前記集積回路設計用プログラムを構成してもよい。
【００１５】
また、前記評価手段は、物理的な規則構造に基づく規則性の評価を行う場合、局所詰め込み値及び局所均一値に基づいて評価を行うようにコンピュータを機能させるよう前記集積回路設計用プログラムを構成してもよい。
【発明の効果】
【００１６】
本発明に係る集積回路設計装置によれば、より規則的に並んだレイアウトを得ることによって、回路特性や配線性に優れたレイアウトを得ることができる。
また、外部から明示的な制約を指定せずに、内部的にレイアウトの規則性を考慮することで、最小限の付加的な制約で規則的なレイアウトを得ることが可能になり、結果として、歩留まり、マッチング特性、配線性等の向上が可能になる。
また、本発明に係る集積回路設計用プログラムは、コンピュータを用いて前記集積回路設計装置を構築することが可能になる。
【発明を実施するための最良の形態】
【００１７】
図１は、本発明の実施の形態に係る集積回路設計装置のブロック図である。
図１において、集積回路設計装置１００は、中央処理装置（ＣＰＵ）１０１、キーボードやマウス等によって構成された入力部１０２、液晶表示器等によって構成された表示部１０３、外部記憶装置を構成する磁気ディスク記憶部１０４、主記憶装置等を構成する半導体メモリ１１０を備えている。
【００１８】
磁気ディスク記憶部１０４内には、半導体集積回路を構成するデバイス（回路素子）や前記デバイスの集まりであるセル等の回路要素の形状及びその名称を対応付けた情報（レイアウト図形情報）を複数種類記憶したレイアウト図形情報記憶部１０５、ネットリスト情報（結線情報）を記憶したネットリスト情報記憶部１０６、複数のデバイスやセルによって構成されるクラスタ等の回路要素の定義や各回路要素の位置関係等の制約を表す情報である制約情報を記憶した制約情報記憶部１０７、コストとして評価する項目に関する情報（コスト情報）を記憶したコスト情報記憶部１０８、レイアウトの規則性を評価するために使用する規則性を持つ構造の情報（規則構造情報）を記憶した規則構造情報記憶部１０９が設けられている。
【００１９】
前記レイアウト図形情報には、ネットリストを構成するインスタンス（単一又は複数の回路素子（セルやデバイス）によって構成される、１つのまとまった単位の回路要素である。ブロックと称する場合もある。）の形状（枠）の情報が含まれている。
また、前記制約情報は回路要素のレイアウトを行う際に必ず満たす必要のある条件を表す情報（制約）であり、前記制約情報には、複数のデバイスやセルによって構成される回路要素を定義した情報（例えば、クラスタ、ペア、シンメトリ）や、各回路要素の位置関係の制約（例えば、複数の回路要素の水平位置関係の制約や垂直位置関係の制約）を表す情報等のレイアウト時に満たすべき情報が含まれている。
【００２０】
また、前記コスト情報には、面積や配線長等のコスト評価の対象とする項目の情報が含まれている。
また、前記規則構造情報には、規則性を評価するための基準となる、インスタンスの配置構造の種類が記憶されている。本実施の形態では、後述するようなアレイ、ロウ等の規則的な配置構造を定義した情報が含まれている。
前記レイアウト図形情報、ネットリスト情報、制約情報、コスト情報及び規則構造情報は設計情報を構成している。
【００２１】
磁気ディスク記憶部１０４は、ＣＰＵ１０１が実行する集積回路設計用プログラムも記憶しており、ＣＰＵ１０１は前記プログラムを実行することにより、後述する処理を行う。
ここで、ＣＰＵ１０１は、レイアウトの位相的表現からレイアウトにおける規則構造を抽出しレイアウトの規則構造をレイアウトの最適化指標として評価する評価手段、及び、レイアウトの最適化を行う最適化手段を構成している。前記最適化手段は、レイアウト最適化を行う際に、制約等の必ず満足すべき条件を満たした上で、位相構造の最適化を行い、これを反映して物理構造（例えば、面積や配線長）の最適化を行う。
【００２２】
レイアウト図形情報記憶部１０５は回路要素のレイアウト図形情報を記憶するレイアウト図形情報記憶手段を構成し、ネットリスト情報記憶部１０６はネットリスト情報を記憶したネットリスト情報記憶手段を構成し、制約情報記憶部１０７は制約情報記憶手段を構成し、コスト情報記憶部１０８はコスト情報記憶手段を構成し、規則構造情報記憶部１０９は規則構造情報記憶手段を構成している。
また、入力部１０２は入力手段を構成し、表示部１０３は表示手段を構成し又、磁気ディスク記憶部１０４及びメモリ１１０は記憶手段を構成している。
【００２３】
図２〜図７は、本発明の実施の形態において、レイアウトの規則性を評価するために用いる規則構造の例を示す図である。
ここで、レイアウトの規則性とは、個々のインスタンスあるいは複数のインスタンス群が一定の規則でレイアウトされている状態をいう。
例えば、規則性の例として、個々のインスタンスあるいは複数のインスタンス群に対しての、インスタンスのレイアウトの縦及び／又は横方向の整列性（整列性）、インスタンスのレイアウトの回転方向の方向性（方向性）、インスタンスのレイアウトの対称性（Ｘ軸対称、Ｙ軸対称、原点対称）（対称性）の３つがある。
【００２４】
ＬＳＩの特性上、これらを揃えるあるいは所定配置に指定することが、製造歩留まりの観点から好ましく、特にアナログ要素ではトランジスタのマッチング特性が向上する。また、各回路要素間を配線接続する場合に、配線の容易性等の配線性が向上する。
本実施の形態では、前記３つの規則性の要素（整列性、方向性、対称性）を、レイアウトトポロジとして下記の規則構造に類型化することによって、レイアウトの規則性の評価を可能にしている。
【００２５】
（ｉ）アレイ（Ａｒｒａｙ）
図２に示すように、複数のインスタンスが、マトリクス状にレイアウトされた状態であり、縦及び横が各々同一のピッチ、間隔でレイアウトされている状態である。図２には、９（３×３）個のインスタンス１〜９がアレイ構造にレイアウトされている例を示している。
【００２６】
（ｉｉ）ロウ（列並び：Ｒｏｗ）
図３に示すように、複数のインスタンスが、縦又は横が同一ピッチ、同一間隔でレイアウトされている状態である。図３には、複数のインスタンス１〜８が、縦方向が同一ピッチ、同一間隔でレイアウトされており、縦方向３段のロウ構造のレイアウト例を示している。
【００２７】
（ｉｉｉ）スライス（Ｓｌｉｃｅ）
図４に示すように、任意のインスタンスを直線によって２分割できるようにレイアウトされている状態である。図４には、インスタンス１、２とインスタンス３、４とを横線によって２分割できるように配置されたスライス構造の例を示している。
【００２８】
（ｉｖ）ルーム（Ｒｏｏｍ）
図５に示すように、破線で示すように所定領域を複数の矩形領域（ルーム）に分割し、前記各矩形領域に空きが生じないように、前記各矩形領域に１つのインスタンスを配置した状態であり、スライスを包含する概念である。図５には、所定領域を５つの矩形領域に分割し、各矩形領域内に１つのインスタンス１〜５を配置したルーム構造の例を示している。
【００２９】
（ｖ）オブジェクト（Ｏｂｊｅｃｔ）
図６に示すように、任意のコンパクションを行った後のレイアウト状態であり、各インスタンス１〜４が任意の座標を持つ状態である。
ここで、前記５種類のレイアウトトポロジ（ｉ）〜（ｖ）は、アレイ、ロウ、スライス、ルーム、オブジェクトの順で、規則性の観点からの優先度が低くなる（アレイ＞ロウ＞スライス＞ルーム＞オブジェクト）ように設定している。前記優先度に対応する評価値を予め設定しておくことにより、規則性の評価を数値化することができる。
尚、前記規則構造以外にも、図７に示す規則構造「シンメトリ（Ｓｙｍｍｅｔｒｙ）」のように、複数のインスタンス１〜５が線対称になるように配置した状態も含めるようにしてもよい。
【００３０】
図８及び図９は、本発明の実施の形態に係る集積回路設計装置１００の動作を示すフローチャートである。
図１０は、物理的な構造評価値の１つである局所詰め込み値（局所への詰め込み具合の指標となる値）を説明するための図である。図１０において、局所詰め込み値は、局所配置の詰め込み率を向上させるためのコストである。局所詰め込み値は、「ブロック１〜８の面積の総和／ブロック１〜８を囲む最小矩形１００１の面積」である。局所詰め込み値は、値が大きいほど空き領域が多いことを示しており、局所詰め込み値が大きいほど、コストが高くなる。
【００３１】
図１１は、物理的な構造評価値の１つである局所均一値（ロウにおける均一性の指標となる値）を説明するための図である。
ロウは複数のブロックがマトリクス的に配置された構造であり、水平方向のロウの場合は、各段のブロックの高さは同じであるが、ブロックの幅は異なる。各段でのブロックの幅の最大幅と最小幅の差を、全ての段で加算したものを評価して数値化し（この値を局所均一値という。）、前記局所均一値が小さい程、均一なロウであると判断する。縦方向のロウの場合も、前記同様にして局所均一値を求めて均一性を評価する。
【００３２】
例えば図１１において、局所均一値は、水平方向ロウのブロックの幅を均一にするためのコストであり、局所均一値は、「（ブロック１〜４の最大幅−最小幅）＋（ブロック５〜８の最大幅−最小幅）」である。
また、図１２〜図１４は、本発明の実施の形態に係る集積回路設計装置１００において、最適化処理の例を示す図である。
【００３３】
以下、図１〜図１４を用いて、本発明の実施の形態に係る集積回路設計装置及び集積回路設計用プログラムについて詳細に説明する。
先ず、ユーザ（例えば、半導体集積回路の設計者）が入力部１０２を操作して設計処理開始の指示を入力すると、ＣＰＵ１０１は、磁気ディスク記憶部１０４に記憶しておいた前記集積回路設計用プログラム及び設計情報をメモリ１１０に読み込み、前記集積回路設計用プログラムを実行することにより、入力部１０２からの入力に応じた処理を行うことができる状態になる。
【００３４】
即ち、ＣＰＵ１０１は、レイアウト図形情報記憶部１０５からレイアウト図形情報を、ネットリスト情報記憶部１０６からネットリスト情報を、コスト情報記憶部１０８からコスト情報を、規則構造情報記憶部１０９から規則構造情報を読み込んで、メモリ１１０に入力する（ステップＳ８０１）。ここで、ネットリストは階層構造でもよい。
また、ＣＰＵ１０１は、制約情報記憶部１０７から制約情報を読み込んでメモリ１１０に入力する（ステップＳ８０２）。
【００３５】
本実施の形態では、シーケンスペア法を用いて、規則性構造の評価や配置改善を行うようにしているため、ＣＰＵ１０１は、前記制約情報の制約を位相関係に変換した後（ステップＳ８０３）、規則性情報を参照すると共に前記レイアウト図形情報、ネットリスト情報及び制約情報を用いて、前記制約を満足するように、レイアウトの最適化を行うために配置改善処理を行う（ステップＳ８０４）。
【００３６】
処理ステップＳ８０４の配置改善処理では図９に示す処理が行われる。即ち、ＣＰＵ１０１は先ず、処理ステップＳ８０２で入力した制約を満たす初期解（レイアウトモデル）Ｘを作成する（図９のステップＳ９０１）。前記初期解Ｘは前記制約を満たす任意の解である。
次にＣＰＵ１０１は、処理ステップＳ９０１で得られた解Ｘに対してトポロジ的な変更やトポロジを保持してのブロック交換を行うことによって、新しい解Ｘ’（レイアウトモデル）の作成を行う（ステップＳ９０２）。
【００３７】
ここで、「トポロジ的」とは、任意のレイアウト対の関係を「上下関係」、もしくは「左右関係」のどちらかの位置関係（位相関係）によって表現することを意味しており、レイアウト全体のブロック位置関係を物理的に表現するのではなく、トポロジによって表現することである。
【００３８】
この表現方法には、たとえばＢＳＧ法（Bounded-Sliceline Grid）、シーケンスペア法（Sequence-Pair）、オーツリー法（O-Tree）、 ビーツリー法（B*-Tree）、ＴＣＧ−Ｓ法等の既知の方法があるが、本実施の形態では、シーケンスペア法でのアルゴリズムを例に説明する。
次にＣＰＵ１０１は、前記解Ｘ’に関して、前記トポロジ的な表現からレイアウトの規則性を抽出することにより、トポロジ的な構造評価値を算出する（ステップＳ９０３）。
【００３９】
以下に一例として、シーペンスペア法を用いて、アレイ、ロウ及びシンメトリを抽出する手法を示すが、シーケンスペア法では、ブロックレイアウトにおいて、左上方向に、他のブロックに接触せずに取り出す順番を考える場合、これを「左上列」と呼ぶ。同様に、左下方向に取り出す順を「左下列」と呼ぶ。この左上列と左下列の対がシーケンスペアに対応する。また、左上列を１、２、３、・・・と連続昇順の番号でブロック名を置き換えたときに対応する左下列がシングルシーケンス（Single-Sequence）に対応する。
【００４０】
先ず、アレイ及びロウレイアウトトポロジ構造（位相構造）の抽出を行う場合には、あるブロックレイアウト、もしくは部分レイアウトに着目する。そのレイアウトのシングルシーケンス表記に従い、要素番号が、連続、かつ昇順（以下、連続昇順）になっている場合は、そのレイアウトは水平方向の１列のレイアウトトポロジに対応していると判断できる（以下、水平１列レイアウト）。また、要素番号が、連続、かつ降順（以下、連続降順）になっている場合は、そのレイアウトは垂直方向の１列のレイアウトトポロジに対応していると判断できる（以下、垂直１列レイアウト）。
【００４１】
さらに、これらの水平１列レイアウトをそれぞれ１ブロックに置き換える。そのレイアウトにおいて、上記と同様の手順で、連続降順となる列を抽出したとき、そのレイアウトは、水平列を積み重ねた多段ロウのレイアウトトポロジに対応していると判断できる。
同様に、垂直１列レイアウトをそれぞれ１ブロックに置き換え、そのレイアウトにおいて、連続昇順となる列を抽出したとき、そのレイアウト、垂直列を複数段積み重ねた多段ロウのレイアウトトポロジに対応していると判断できる。
【００４２】
以上のすべての手順は、ブロック数に応じた数の処理を行うことにより実行可能である。
特殊な場合として、積み重ねられた水平１列レイアウトがすべて同じブロック数をもつとき、アレイレイアウトトポロジに対応していると判断できる。同様に、積み重ねられた垂直１列レイアウトがすべて同じブロック数をもつとき、アレイレイアウトトポロジに対応していると判断できる。
【００４３】
また、シンメトリトポロジの抽出を行う場合には、あるブロックレイアウト、もしくは部分レイアウトに着目し、そのレイアウトから抽出したシングルシーケンスと、そのレイアウトを水平方向にＹ軸反転したレイアウトから抽出したシングルシーケンスが同一であるとき、このレイアウトは、完全水平対称トポロジを持つと判断できる。同様に、そのブロックレイアウトから抽出したシングルシーケンスと、そのレイアウトを垂直方向にＸ軸反転したレイアウトから抽出したシングルシーケンスが同一であるとき、レイアウトは、完全垂直対称トポロジを持つと判断できる。
【００４４】
次に、ＣＰＵ１０１は、規則性の評価を行う場合、例えば次のようにして行う。
先ず、ＣＰＵ１０１は、下記のトポロジカル構造評価値及び物理的な構造評価値をコンパクション前（具体的な座標値が確定する前）に算出する。
（１）トポロジ的な構造評価値の算出
（ａ）アレイトポロジ構造を構成しているブロック数と、各トポロジの行数と列数の比（アスペクト）とから、アスペクトが１に近いアレイの数に比例して大きくなるように算出した値
【００４５】
（ｂ）ロウトポロジを構成しているブロック数とアスペクトとから、アスペクトが１に近いロウの数に比例して大きくなるように算出した値
（ｃ）自己シンメトリ（自分自身に対称）以外の対称トポロジを構成しているブロック数に比例するように算出した値
（（ａ）＋（ｂ）＋（ｃ））の値をトポロジ的な構造評価値とする。
【００４６】
（２）物理的な構造評価値の算出（ステップＳ９０４）
（ｄ）局所詰め込み値の算出
前記（１）のブロックに対して、「各ブロックの面積の総和／各ブロックを囲む最小矩形の面積」を局所詰め込み値として求める。これにより詰め込み具合を算出する（値が大きいほど空き領域が多く、コストが高い）。
【００４７】
（ｅ）局所均一値の算出
各段でのブロックの幅の最大幅と最小幅の差を、全ての段で加算したものを評価して数値化することにより、局所均一値を算出する。
ここでは、前記（１）の複数列に対して、各列のブロックの最大、最小幅の差を総計したものが大きいほど、均一でなく、コストが高くなる。
（（ｄ）+（ｅ））の値を物理的な構造評価値とする。
【００４８】
次に、ＣＰＵ１０１は、コストの要素である配線長及び面積を算出する（ステップＳ９０５）。
次に、ＣＰＵ１０１は、処理ステップＳ９０２で作成した解Ｘ’が制約を満たすか否かを判断し、解Ｘが制約を満足する場合には解Ｘ’と解Ｘとのコスト比較を行い、より適した方の解を選択する（ステップＳ９０６）。
【００４９】
ここで使用するコスト及び制約は次の通りである。
（Ａ）制約
制約は必ず守るべき条件であり、例えばブロックの隣接制約や、具体的なブロック名を指定したシンメトリ制約、あるいは寄生成分（抵抗、容量）などの影響を考慮した制約などがあり、これらは、具体的な座標値を求めるコンパクションの前後で、制約をチェックし、許容解か否かを判断する。
【００５０】
（Ｂ）コンパクション前のトポロジカル構造評価値、物理的な構造評価値のコスト
このコストは、処理ステップＳ９０３、Ｓ９０４で算出された構造評価値に基づくコストであり、これらは前記（Ａ）の制約で明示的に指定されたブロック以外にも適応される。即ち、このコストは、外部から制約として指定されていない場合でも、自動的に算出される。
（Ｃ）コンパクション後の面積、配線長などのコスト
このコストは、一般的なブロックの実座標値が確定した後に評価されるコストであり、面積最小、配線長（総配線、特定配線を含む）最小を目標とする。
【００５１】
ＣＰＵ１０１は、前記（Ａ）の制約を守りつつ、前記（Ｂ）、（Ｃ）のコストを最適化（例えば最小化）するようにして、レイアウトを最適化する。
即ち、ＣＰＵ１０１は、処理ステップＳ９０６において、新たな解Ｘ’が制約を満たし、且つ、新たな解Ｘ’と解Ｘのコスト比較を行うことによって解Ｘ’のコストが解Ｘのコストよりも小さいか否かを判断する。
【００５２】
ＣＰＵ１０１は、新たな解Ｘ’が制約を満たし、且つ、解Ｘよりもコストが小さいと判断すると、解を解Ｘから解Ｘ’に更新した後（ステップＳ９０７）、配置改善の終了条件が満たされたか否かを判断する（ステップＳ９０８）。
前記配置改善の終了条件としては、例えば、最適化手法がＳＡ（Simulated Anneiling）法の場合には温度が所定温度（例えば、１００度から０度まで）、遺伝的アルゴリズム（ＧＡ）法の場合には世代数等である。
【００５３】
一方、ＣＰＵ１０１は、処理ステップＳ９０６において、新たな解Ｘ’が制約を満たさないと判断した場合や、解Ｘ’が解Ｘよりもコストが小さくないと判断した場合、直ちに処理ステップＳ９０８に移行する。
ＣＰＵ１０１は、処理ステップＳ９０８において、配置改善の終了条件が満たされていないと判断した場合には処理ステップＳ９０２に戻って前記処理を繰り返し、配置改善の終了条件が満たされたと判断した場合には、得られた集積回路のレイアウトのデータを磁気ディスク記憶部１０４に記憶し、表示部１０３あるいは外部の装置に出力する（ステップＳ８０５）。
【００５４】
このようにして、前記項目（Ａ）、（Ｂ）、（Ｃ）の複合的な制約、コストを最適化アルゴリズムの中で調整することで、従来の集積回路設計装置において用いていた項目（Ａ）、（Ｃ）に加えて、（Ｂ）の規則性を考慮したレイアウト結果を得ることができる。
前記の如くして行った最適化処理の一例を図１２〜図１４に沿って説明する。
【００５５】
図１２は、複数のブロックａ〜ｄの配置を行った最初の状態（初期状態）を示す図である。図１２の初期状態は、複数のブロックａ〜ｄが配置された最初の状態であり、アレイ構造の個数（アレイ数）は０であり又、物理的な総配線長は２．５である。双矢印線は物理的な配線であり、これらの配線の合計が総配線長である。本例における最適化処理の目標は、アレイのコストの最小化（即ち、アレイ数の最大化）及び物理的な総配線長であるコストの最小化である。
【００５６】
図１３は、図１２の状態から、トポロジ最適化によってアレイ構造が形成された状態を示している。ここで、アレイ数は１であり、総配線長は４である。但し、総配線長は必ずしも最適化されたものではない。
図１４は、図１３の状態から変化して、トポロジのコストが劣化しないという制約の下で、物理的なコストを最適化した状態を示している。ここで、アレイ数は１、総配線長は２が得られており、アレイ数の最大化及び物理的総配線長のコストの最小化が実現されている。
【００５７】
このようにして、前記（Ａ）、（Ｂ）、（Ｃ）の複合的な制約、コストを最適化アルゴリズムの中で調整することで、前記（Ｂ）の規則性を考慮したレイアウト結果を得ることができる。即ち、コスト計算に際して、規則性の観点からコストを補正するように処理することにより、高い規則性を有するレイアウトの場合、よりコストを小さくすることができる。
【００５８】
以上述べたように、本発明の実施の形態に係る集積回路設計装置は、レイアウトの位相的表現からレイアウトにおける規則構造を抽出し、前記抽出したレイアウトの規則構造をレイアウトの最適化指標として評価し、レイアウト最適化を行う際に、位相構造と物理構造（面積や配線長等のコスト）の最適化を行うようにしている。
即ち、ＣＰＵ１０１は、磁気ディスク記憶部１０４の規則構造情報記憶部１０７に記憶された規則構造情報を参照すると共にレイアウト図形情報、ネットリスト情報及び制約情報を用いてレイアウトにおける規則構造を抽出し、前記規則構造を評価し、前記評価を考慮して、レイアウト図形情報、ネットリスト情報等の設計情報を用いて最適化した集積回路のレイアウトを得るようにしている。
【００５９】
したがって、より規則的に並んだレイアウトを得ることによって、良好な回路特性を持ち又、総配線長の短い良好な配線性を持つレイアウト結果を得ることが可能になる。
また、レイアウト最適化処理において、新たに規則性の指標を組み込みことで、明示的なアライメントなどの制約がなくとも、レイアウト結果が自動的に、アレイ、ロウ、スライス等の規則構造を考慮するようになり、これに従来の面積や配線長のコスト、及び、ペア性、シンメトリ性などの付加的な制約を合わせて自動レイアウトを行うことで、よりアナログ設計者の望む、規則的な、いわばきれいなレイアウトを得ることが可能になる。
【００６０】
また、外部から明示的な制約を指定せずに、内部で規則性を考慮することで、最小限の付加的な制約を用いて、自動レイアウト結果が規則的なレイアウト結果となる。その結果として、歩留まりの向上や良好なマッチング特性を得ることが可能になり、さらには  短く単純な配線によって各回路要素を接続できるため、各回路要素を適切な配線によって容易に接続できる等の配線性が向上し、レイアウト設計効率が向上するという効果を奏する。
【００６１】
アナログ半導体集積回路のみならずデジタル半導体集積回路の設計にも良好に適用可能であるが、特にアナログ半導体集積回路において優れたレイアウト結果を得ることができる。
また、本発明の実施の形態に係る集積回路設計用プログラムをコンピュータに実行させることにより、コンピュータを用いて前記集積回路設計装置を構築することが可能になる。
【００６２】
尚、トポロジ的な規則構造の評価を行って評価値を算出する場合、アレイ、ロウ、スライス、ルーム、オブジェクトの中の少なくとも１つを評価して評価値を算出するように構成してもよい。
また、物理的な規則構造の評価を行って評価値を算出する場合、局所詰め込み値及び局所均一値の中の少なくとも１つを評価して評価値を算出するように構成してもよい。
【産業上の利用可能性】
【００６３】
アナログ半導体集積回路やデジタル半導体集積回路の設計を行う集積回路設計装置に適用可能である。また、コンピュータをアナログ半導体集積回路やデジタル半導体集積回路の設計を行う集積回路設計装置として機能させるプログラムに適用可能である。
【図面の簡単な説明】
【００６４】
【図１】本発明の実施の形態に係る集積回路設計装置のブロック図である。
【図２】本発明の実施の形態において使用する規則構造の例を示す図である。
【図３】本発明の実施の形態において使用する規則構造の例を示す図である。
【図４】本発明の実施の形態において使用する規則構造の例を示す図である。
【図５】本発明の実施の形態において使用する規則構造の例を示す図である。
【図６】本発明の実施の形態において使用する規則構造の例を示す図である。
【図７】本発明の実施の形態において使用する規則構造の例を示す図である。
【図８】本発明の実施の形態に係る集積回路設計装置の動作を示すフローチャートである。
【図９】本発明の実施の形態に係る集積回路設計装置の動作を示すフローチャートである。
【図１０】本発明の実施の形態における局所詰め込み値を説明する図である。
【図１１】本発明の実施の形態における局所均一値を説明する図である。
【図１２】本発明の実施の形態に係る集積回路設計装置における最適化処理を示す図である。
【図１３】本発明の実施の形態に係る集積回路設計装置における最適化処理を示す図である。
【図１４】本発明の実施の形態に係る集積回路設計装置における最適化処理を示す図である。
【符号の説明】
【００６５】
１００・・・集積回路設計装置
１０１・・・評価手段及びレイアウトの最適化を行う最適化手段を構成するＣＰＵ
１０２・・・入力手段を構成する入力部
１０３・・・表示手段を構成する表示部
１０４・・・記憶手段を構成する磁気ディスク記憶部
１０５・・・レイアウト図形情報記憶手段を構成するレイアウト図形情報記憶部
１０６・・・ネットリスト情報記憶手段を構成するネットリスト情報記憶部
１０７・・・制約情報記憶手段を構成する制約情報記憶部
１０８・・・コスト情報記憶手段を構成するコスト情報記憶部
１０９・・・規則構造情報記憶手段を構成する規則構造情報記憶部
１１０・・・記憶手段を構成する半導体メモリ
１００１・・・最小矩形
【図１】
2008140011.tif 000003
【図２】
2008140011.tif 000004
【図３】
2008140011.tif 000005
【図４】
2008140011.tif 000006
【図５】
2008140011.tif 000007
【図６】
2008140011.tif 000008
【図７】
2008140011.tif 000009
【図８】
2008140011.tif 000010
【図９】
2008140011.tif 000011
【図１０】
2008140011.tif 000012
【図１１】
2008140011.tif 000013
【図１２】
2008140011.tif 000014
【図１３】
2008140011.tif 000015
【図１４】
2008140011.tif 000016