(57)【要約】      （修正有）【課題】階層データ構造におけるセルの評価方法の提示。【解決手段】データ構造におけるセルの階層効果を判定する手法を設ける。該階層効果は、データ構造を使ってタスクを実行するのにセルの利用がどの程度効果的かを示すものである。データ構造を使ってタスクを実行するのにどのセルが利用されるべきかを判定するよう、データ構造中の全てのセルの階層効果を判定する手法を更に設ける。【選択図】図６
2004303234.tif 000002
【特許請求の範囲】
【請求項１】
データ構造中のセルを評価する方法であって：
１つ以上の成分を含むセルを定義する工程；
前記データ構造中の前記定義セルの発生数を判定する工程；
前記データ構造中の前記定義セルの各発生の各成分に操作を行うことによってタスクを実行することから得られるフラット・リソース値を判定する工程；
第１操作を単一定義セルの各成分に行うこと、及び
第２操作を前記データ構造中に発生する各定義セルに、前記第１操作を前記単一定義セルの各成分に行うことから得られた結果を用いて行うこと、
によって前記タスクを実行することから得られる階層リソース値を判定する工程；及び
前記定義セルの階層効果を、前記階層リソース値を前記フラット・リソース値と比較することによって、判定する工程；
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、更に：
前記フラット・リソース値を、前記タスクを実行するのに前記データ構造の各基本素子に行われる操作の総数として、判定する工程；及び
前記階層リソース値を、前記定義セルを用いて前記タスクを実行するのに前記データ構造に行われる操作の前記総数として、判定する工程；
を有することを特徴とする方法。
【請求項３】
請求項１記載の方法であって、更に：
前記フラット・リソース値を、前記タスクの、前記データ構造中の前記定義セルの各発生の各成分に行われる操作の総数として、判定する工程；及び
前記階層リソース値を、前記単一定義セルの各成分への第１操作の総数と前記データ構造中に発生する前記定義セルに行われる第２操作の総数として、判定する工程；
を有することを特徴とする方法。
【請求項４】
請求項１記載の方法であって、更に：
前記定義セルの前記階層効果を、前記階層リソース値の前記フラット・リソース値に対するパーセンテージ値として、判定する工程；
を有することを特徴とする方法。
【請求項５】
請求項１記載の方法であって、更に：
前記定義セルの前記階層効果を絶対的階層効果として、前記セルを、前記データ構造の要素のみを含めるよう定義することによって、判定する工程；
を有することを特徴とする方法。
【請求項６】
請求項１記載の方法であって、更に：
前記定義セルの前記階層効果を累積階層効果として、前記データ構造の少なくとも他の１つのセルを含めるよう前記セルを定義することによって、判定する工程；
を有することを特徴とする方法。
【請求項７】
請求項１記載の方法であって、前記定義セルを定義する基準が前記データ構造に備え付けられていることを特徴とする方法。
【請求項８】
請求項１記載の方法であって、前記データ構造が電子回路の構造を記述するデータ構造であることを特徴とする方法。
【請求項９】
請求項８記載の方法であって、前記データ構造がネットリストのリスティングであることを特徴とする方法。
【請求項１０】
請求項８記載の方法であって、更に：
前記定義セルの前記階層効果を、他のデータ構造における突合セルを識別するよう、利用する工程；
を有することを特徴とする方法。
【請求項１１】
タスクを実行するのに操作を行うデータ構造中のセルを選択する方法であって：
データ構造中のセルの群を定義する第１工程；
前記群中の前記セル全部について、
前記データ構造中の各セルの発生数を判定して、
成分操作を前記群中の各セルの各成分に行うこと、及び
セル操作を前記群中の各セルに、前記成分操作を前記セルの各成分に行うことから得られた結果を用いて、行うこと、
によってタスクを実行することから得られる総累積リソース値を判定する、第２工程；
各選択セルについて、
成分操作を前記セルの各成分に行うこと、及び
セル操作を前記データ構造中に発生する各セルに、前記成分操作を前記セルの各成分に行うことから得られた結果を用いて、行うこと、
によってタスクを実行することから得られる、選択セルの累積階層リソース値を判定する第３工程；
前記選択セルについて前記総累積リソース値と前記累積階層リソース値との関係に基づいて削減値を判定する第４工程；
前記削減値が閾値を超える場合、
前記群中の各非選択セルについて、
成分操作を前記セルの各成分に行うこと、及び
前記データ構造中に発生する各セルにセル操作を、前記成分操作を前記セルの各成分に行うことから得られた結果を用いて、行うこと、
によってタスクを実行することから得られる累積階層効果ランキングを、判定して、
最高累積階層効果ランキングを有する前記セルを選択し、かつ、第３工程乃至第５工程を繰り返す、第５工程；及び
前記タスクを、前記選択セルを用いて、実行する第６工程；
を有することを特徴とする方法。
【請求項１２】
請求項１１記載の方法であって、更に：
前記総累積リソース値を、前記データ構造中で定義された各セルを用いて前記タスクを実行するよう前記データ構造に行われる操作の総数として、判定する工程；及び
前記累積階層リソース値を、前記選択セルを用いて前記タスクを実行するよう前記データ構造に行われる操作の総数として、判定する工程；
を有することを特徴とする方法。
【請求項１３】
請求項１１記載の方法であって、更に：
前記累積階層リソース値を、
前記定義セルについて、前記定義セルの各成分への第１操作の総数、前記データ構造中に発生する前記定義セルの各発生に行われる第２操作の総数、及び
選択セルの各発生について、前記選択セルの各成分への第１操作の総数、及び前記データ構造中に発生する前記選択セルの各発生に行われる第２操作の総数、
の和として、判定する工程；
を有する方法。
【請求項１４】
請求項１１記載の方法であって、更に：
前記削減値を、以下の式：
削減値＝１００ｘ（（累積階層リソース値−総累積リソース値）／累積階層リソース値）
によって、判定する工程；
を有することを特徴とする方法。
【請求項１５】
請求項１１記載の方法であって、前記データ構造は電子回路の構造を記述するデータ構造であることを特徴とする方法。
【請求項１６】
請求項１５記載の方法であって、前記データ構造はネットリストのリスティングであることを特徴とする方法。
【請求項１７】
請求項１１記載の方法であって、前記定義セルを定義する基準は前記データ構造に備え付けられていることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層データ構造におけるセルの評価に関する。本発明の種々の実施例は特に、回路配置図用データ構造と回路概略図用データ構造とを比較するのに用いられるセルの効果の判定への適合性を有する。
【背景技術】
【０００２】
コンピュータが精巧になるにつれ、それらのコンピュータによって利用し得るデータ構造は大型化している。例えば、マイクロプロセッサのような、今までのものと違った集積回路の設計は何百万ものトランジスタ及び他の電気素子を、論理回路、記憶回路、プログラム可能なフィールド・アレイ、あるいは他の回路素子の中に構成することを含み得る。コンピュータがこれらの大規模データ構造をより容易に処理することを可能にする（とともに、利用者がよりよくデータ構造を理解することを可能にする）ために、大規模データ構造はよく、セルの階層編成に分割されている。したがって、上記の例においては、単一の記憶回路を構成しているトランジスタ全てを単一のセルに分類し得る。そうすることによって、個々のトランジスタ各々を列挙する必要なしで、記憶素子を構成するトランジスタ群が一単位として、集合的に参照され、かつ、操作されることを可能にする。例えば、今までのものと違った集積回路の設計を含むデータ構造を生成する場合、設計者は、単に、所望の記憶装置を表すセルに対応するデータについての単一の参照を一回の操作で加えることが、記憶素子を構成する各々のトランジスタについてのデータを個々に加える必要なしで、可能になる。
【０００３】
一般にセルに分割されたデータ構造において、セルは階層的に配置される。最下位のセルはデータ構造の基本要素のみを含み得る。中位のセルはその場合１つ以上の低位セルを含み得、高位のセルは、その場合１つ以上の中位セルを含み得る、などである。更に、いくつかのデータ構造においては、セルは１つ以上の下位セルをデータ構造の基本要素に加えて含み得る。したがって、上記の例においては、レジスタを表すデータのセルは記憶回路を表すデータのセルのいくつかのインスタンス、種々の論理素子を表すデータの異なったセルのいくつかのインスタンス、及び特定用途の接続回路を表す要素データを含み得る。同様に、メモリアレイを表すデータのセルは、レジスタを表すデータのセルのいくつかのインスタンスを、特別用途の接続回路を表す要素データとともに、含み得る。
【０００４】
データ構造をセルに分割することによってより効率的に、かつ、より少ないリソースにてデータ構造を使ってタスクを実行し得る。例えば、集積回路の概略図を定義するデータ構造は、集積回路を形成するのに必要な材質の配置図を定義する、対応するデータ構造に変換されなくてはならない。概略図（すなわち、「ソース」情報）を記述するデータ構造を材質の配置図を記述するデータ構造に変換する過程においては、しかしながら、エラーがもたらされる可能性がある。したがって、実動ラン、すなわち、変換された配置図データ構造に基づいた集積回路の製造を行うのに多額を費やす前に、配置図データ構造は元の概略図データ構造と注意深く比較される。両方のデータ構造をセル階層に分けることなく、両方のデータ構造の要素毎の比較を行わなければならない。多数のトランジスタを有する、超大規模集積回路においては、そのような比較は、実際の役に立つには長すぎる。しかしながら、両方のデータ構造をセルに分割することによって、配置図データ構造の正確性を確認するのにより少ないデータ単位の比較で済むことが可能になる。したがって、当該比較は、より速く、かつ、より少ない処理リソースを用いて行い得る。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
データ構造におけるセルの利用によって、より効率的にデータ構造を使ってタスクを実行することが可能となり得る一方、セルの利用自体がタスクの実行においてエラーをもたらし得る。したがって、上記の例では、概略図データ構造におけるセルが、不注意にも、配置図データ構造における誤ったセル（すなわち、概略図データ構造におけるセルに対応することが企図されていないセル）と比較された場合、当該比較タスクによって誤って、概略図データ構造と配置図データ構造との要素毎比較によって回避される、エラーが明らかにされる。当業者にはわかるように、いくつかのセルの利用は比較における処理オーバヘッドあるいはメモリ使用量を低減するのに非常に効果的であるものの、他のセルの利用は処理オーバヘッドあるいはメモリ使用量にはあまり影響がないかもしれない。通常は、しかしながら、比較演算のような、タスクを実行するのにどのセルを利用するのが有用であるかを判定するのは困難である。
【課題を解決するための手段】
【０００６】
好都合にも、本発明の種々の実施例はデータ構造を使ってタスクを実行するのにどのくらいセルの利用が効果的であるかを示す階層効果を設ける。本発明の種々の実施例によれば、セルの階層効果はまず、データ構造を使ってデータ構造中の個々の要素各々に操作を行うことによってタスクを実行するのに必要な操作数を判定することによって得られる。次に、セルの個々の成分各々に操作を実行し、それから、データ構造中に発生するそのセルの各インスタンスに必要な操作を実行することによってタスクを実行する、のに必要な操作数が判定される。これらの操作数の対比は、例えば、セルを用いてタスクを実行することによって得ることが可能な効率向上を示す、パーセント値、として都合よく定量化し得る。
【０００７】
本発明の更に他の実施例は、データ構造を使ってタスクを実行するようどのセルを利用すべきかを判定するのに、データ構造における全てのセルの階層効果を得ることを可能にする。これらの実施例では、データ構造中の選択セル各々の階層効果が判定され、タスクを実行するようデータ構造中のセル全てを用いて得られる効率と対比される。したがって、選択セルを用いる階層効果と全てのセルを用いる効果とを対比させることによって得られる削減値は、残りの、非選択セルを用いることによって得ることが可能な削減量である。当該削減値が閾値を超えている場合は、最高累積階層効率を有するセルがタスクを実行するのに利用される選択セルのリストに加えられる。この処理は、タスクを実行するのに選択されたセル各々を考慮して、更に繰り返される。選択セルが当該閾値を超える削減値を設けない場合は、選択セルがタスクを行うのに利用される一方、他の残りのセル全て（すなわち、非選択セル）はタスクを実行するのに利用されない。
【発明を実施するための最良の形態】
【０００８】
本発明のよりよい理解を設けるよう、本発明の種々の実施例を、集積回路の元の概略図を記述するデータ構造と集積回路を実現する材質の配置を記述するデータ構造との比較に関して説明する。したがって、概略図のデータ構造と配置図データ構造との比較処理の簡単な説明を本発明の種々の実施例を実現し得る一動作環境の例とともに記述する。本発明の種々の実施例によるセルの階層効果の判定を次に説明し、概略図データ構造と配置図データ構造とを比較するような、タスクを実行するのに利用すべきセルはどれかを判定することに階層効果を適用することについても説明する。
【実施例】
【０００９】
（概略図と配置図のデータ構造）
次に図１を参照すると、図１は簡単な電子回路１０１を表す概略図を示す。図１からわかるように、回路１０１は、（コネクション端点「１」と名付けられた）ドレイン１０５、（コネクション端点「２」と名付けられた）ゲート１０７、及び（コネクション端点「３」と名付けられた）ソース１０９を有する、電界効果トランジスタ１０３を含む。回路１０１は電界効果トランジスタ１０３と更に（コネクション端点「３」にて接続された）第２電界効果トランジスタ１１１を含む。電界効果トランジスタ１１１は（コネクション端点「３」と名付けられた）ドレイン１１３、（コネクション端点「４」と名付けられた）ゲート１１５、及び（コネクション端点「５」と名付けられた）ソース１１７を含む。
【００１０】
図１に表された種の概略図は、回路の動作を理解するうえで有用な反面、集積回路を実際に作製するのには直接利用し得ない。その代わりに、回路配置図は回路概略図に基づいて作成される。配置図は回路の実際の構造を形成する材質の配置に対応する多角形を定義する。配置図はその場合は、例えば、回路の構造の製造用の１つ以上のリソグラフ画像を形成するのに用い得る。
【００１１】
例えば、図２は図１に表される電子回路１０１を物理的に実現する例示的配置図２０１を示す。したがって、配置図２０１は電界効果トランジスタ１０３に対応する電界効果トランジスタ２０３、及び電界効果トランジスタ１１１に対応する電界効果トランジスタ２１１を含む。トランジスタ２０３はドレイン１０５を形成するのに用いられる要素の配置を示す多角形２０５、ゲート１０７を形成するのに用いられる材質の配置図に対応する多角形２０７、及びソース１０９を形成するのに用いられる材質の配置図に対応する多角形２０９を含む。同様に、トランジスタ２１１はドレイン１１３を形成するのに用いられる材質の配置図を示す多角形２１３、ゲート１１５を形成するのに用いられる材質の配置図に相当する多角形２１５、及びソース１１７を形成するのに用いられる材質の配置図に相当する多角形２１７を含む。
【００１２】
当業者はよくわかるように、図１に示された種の概略図及び図２にて示された種の配置図は簡単な電子素子を理解するのに有用で有り得る一方、大規模集積回路を記述するのに効果的に用いるには非効率的すぎる。その代わりに、概略図と配置図との両方に表される情報を記述するのに種々のデータ構造が用いられる。時には「ネットリスト」と呼ばれる、一種のデータ構造の例を以下に表す：
Ｍ１    １      ２      ３      Ｐ
Ｍ２    ３      ４      ５      Ｎ
ネットリストの第１行は電界効果トランジスタ１０３を素子Ｍ１として定義し、このトランジスタはＰ型トランジスタであることを示す。更にトランジスタ１０３のドレイン１０５はコネクション端点「１」に接続され、ゲート１０７はコネクション端点「２」に接続され、ソース１０９はコネクション端点「３」に接続される。ネットリストの第２行は第２電界効果トランジスタ１１１をＭ２と呼び、このトランジスタがＮ型トランジスタであることを示す。ネットリストの第２行は更に電界効果トランジスタ１１１のドレイン１１３が更にコネクション端点「３」（と、したがって電界効果トランジスタ１０３のソース１０９にも）接続され、ゲート１１５がコネクション端点「４」に接続され、ソース１１７がコネクション端点「５」に接続されていることを示す。したがって、ネットリストは図１に表される概略図において定義される回路１０１の適切な特性を識別する。
【００１３】
同様に、回路配置図中に示される情報を記述するのにさまざまなデータ構造の種別を用い得る。例えば、回路配置図に定義された多角形情報を記述するにはＧＤＳＩＩデータ・フォーマットが用いられる。この種のデータ・フォーマットは、例えば、配置図中に定義された多角形に相当する材質構造を生成するフォトリソグラフィ装置によって自動的に利用し得る。当業者にはよくわかるように、配置図に表される情報は上記のようなネットリストに変換し得る。配置図のネットリストは、例えば、ＧＤＳＩＩフォーマットから変換し得る。
【００１４】
（配置図と概略図との比較）
したがって、回路の機能を設計するには概略図を利用し得、その場合、回路を作製するよう、配置図が概略図から形成される。配置図は一般に元の概略図から形成される一方、配置図はしかしながら概略図とは有意な差異を含み得る。例えば、配置図を作成する場合、集積回路の表面積の利用の最適化を図るよう配置図に種々の変更を行ない得る。回路の最終配置図はしたがって、元の概略図において企図された動作とは異なった動作をさせるエラーを含み得る。したがって、集積回路を実際に作製するのに配置図を用いる前に、配置図が正確であることを確実にするよう、配置図の最終版が、当該最終版が基にする元の概略図とチェックされる。例えば、上述のように、ＧＤＳＩＩフォーマットによる最終配置図はネットリスト・フォーマットに変換し得、元の概略図を記述するネットリストと比較される。
【００１５】
今日の集積回路の規模の観点からは、しかしながら、概略図ネットリストの各要素と、対応する配置図ネットリストの各要素を比較するのは非常に困難である。例えば、プログラム可能なマイクロプロセッサを形成する集積回路は何億ものトランジスタを含み得る。各トランジスタのネットリスト・データを比較するには、その場合、完了するのに非現実的な時間とリソースの使用を必要とする。その代わりに、概略図ネットリストと配置図ネットリストは両方とも、異なったレベルの再発セルを含む階層構造に編成される。すなわち、特定の配置において繰り返し発生する素子は、セルと呼ばれる、一単位にまとめ得る。
【００１６】
例えば、素子群が記憶回路を形成するよう規則正しく編成されている場合、これらはセルにまとめ得る。その場合、セルは記憶回路の各素子を比較するよりも、概略図ネットリストと配置図ネットリストとの比較用一データ単位として用い得る。特に、概略図ネットリストと配置図ネットリストとを比較するタスクを実行する場合、概略図ネットリスト中のセルの成分を配置図ネットリスト中の対応するセルの成分と比較し得る。成分が同等の場合、セルはその後同等のものとして処理し得る。したがって、セルが配置図のネットリストに再発する毎に、概略図ネットリストとは再び比較されない。
【００１７】
セル自体が他のセルを含んで、階層データ構造を形成することがある。例えば、図３は（セル「Ｚ」と名付けられた）セル３０１を示す。セル３０１は、今度は（セル「Ａ」と名付けられた）セル３０３の複数のインスタンス及び（セル「Ｂ」と名付けられた）セル３０５の単一インスタンスを含む。セル「Ａ」に対応する例示的ネットリストは以下のように表される：
．ｓｕｂｃｋｔ      Ａ      １      ２
Ｍ１      １        ３      ４      Ｐ
Ｍ２      ４        ５      ２      Ｎ
．ｅｎｄ
したがって、ネットリストは、コネクション端点１及び２に接続されていて、端点１、３、及び４に接続があるＰ型トランジスタを有し、端点４、５、及び２に接続があるＮ型トランジスタを有するようにセル「Ａ」を定義する。
【００１８】
同様に、セル「Ａ」を組み入れたセル「Ｚ」に対応する例示的ネットリストを以下に表す。
【００１９】
．ｓｕｂｃｋｔ      Ｚ    １０    ２０    ３０    ４０
Ｘ１      １０      ２０    Ａ
Ｘ２      ２０      ３０    Ａ
Ｘ３      ３０      ４０    Ｂ
：
：
．ｅｎｄ
したがって、このネットリストはセル「Ｚ」がコネクション端点１０、２０、３０及び４０にて接続を有するよう定義している。該ネットリストは更にセル「Ｚ」の第１成分を端点１０及び２０にて接続を有するセル「Ａ」のインスタンスとして、セル「Ｚ」の第２成分を端点２０及び３０にて接続を有するセル「Ａ」のインスタンスとして、かつ、セル「Ｚ」の第３成分を、端点３０及び４０にて接続を有するセル「Ｂ」のインスタンスとして定義している。
【００２０】
セル構造を明らかにするよう、データ構造の階層配列によって更に小さい部分に細分し得ない、データ構造の一部分を呼ぶのに、「要素」又は「基本素子」の語を以下に用いる。その場合、「セル」の語はデータ構造の階層配列によって更に小さい部分に細分し得るデータ構造のいずれかの部分を呼ぶのに用いる。「成分」の語はその場合、「セル」、及び「要素」又は「基本素子」の両方を呼ぶのに包括的に用いられる。したがって、セルの成分は、１つ以上の他のセル、１つ以上の基本素子、又は両方の組み合わせで有り得る。
【００２１】
セルの利用が、配置図ネットリスト（又は他のデータ構造）と概略図ネットリストとを比較するのに必要な比較操作数を実質的に削減し得る一方、比較するセルを最初に決定しなければならない。すなわち、概略図ネットリストと配置図ネットリスト中の、（「ｈ−セル」又は「ｈ−セル」対と呼ばれる）対応するセル対を、比較する以前に最初に、比較タスクの正確性の観点から、明確化しなければならない。
【００２２】
ｈ−セル対はさまざまなやり方で選択し得る。例えば、配置図ネットリストは元の概略図から導き得るので、概略図ネットリストと配置図ネットリスト中のネットリスト対応セルは同一又は類似の名称を共有し得る。代わりに、ｈ−セル対は利用者によって指定し得る。ｈ−セル対を指定するこの手法は、例えば、利用者が、概略図データ構造、配置図データ構造、又は両方を生成するよう、標準セル手法を用いた場合に有用であり得る。更に、発見的方法を、概略図データ構造と配置図データ構造との間のｈ−セル対を突合するよう、利用し得る。例えば、概略図データ構造と配置図データ構造とがちょうど５２３のインスタンスを有するセルを含む場合、それらのセルはおそらく同等で、したがってｈ−セル対として指定し得る。
【００２３】
セルの利用によって概略図ネットリストと配置図ネットリストとを比較するうえでの処理オーバヘッドを実質的に低減し得る一方、不正確なｈ−セル対の選択によって比較タスクに有意なエラーを引き起こし得る。例えば、概略図ネットリストにおけるセルが、配置図ネットリスト中の非同等セルとのｈ−セル対の一部分として誤って示された場合、比較タスクは、セルが同等ではないことを示すエラーを設けるであろう。利用者は、しかしながら、配置図ネットリストが実際にエラーを含んでいたのでエラーが引き起こされたのか、若しくは二つのセルが実は同等でなく比較すべきでなかったので、エラーが引き起こされたのかを判定することは不可能である。したがって、その場合、各セルの成分は、より高位の親セルに関して成分毎にて比較されなければならない。セルは同等ではないので、親セルはおそらく同様に、同等ではなく、したがって他の更に高位の親セルがもしあれば、成分毎に比較する必要がある。このセルを拡張する処理は比較タスクが非現実的に長くなるまで続け得る。
【００２４】
したがって、概略図ネットリストを配置図ネットリストと比較するタスクを実行する場合、比較処理において実質的な削減を設けるｈ−セル対のみを利用するだけが望ましい。比較処理において実質的な削減を設けないｈ−セル対は、該ｈ−セル対が、実際に、同等ではない場合に不正確なエラーを引き起こすのを回避するよう、成分毎に比較し得る。本発明の種々の実施例はデータ構造におけるセルの階層効果値を判定し得るのが好都合である。その場合、相対的に高い階層効果値を有するセルを、配置図ネットリストと概略図ネットリストとを比較するような、所望のタスクに利用し得る。十分に高い階層効果値を有しないそれらのセルは所望のタスクを実行する場合には無視し得る。
【００２５】
（動作環境）
当業者にはよくわかるように、セルの階層効果の判定及び利用はソリッド・ステート回路のような、電子回路を用いて行ない得る。本発明の種々の実施例は、しかしながら、プログラム可能な演算素子にて実行される、ソフトウェア・プログラム・モジュールのような、コンピュータによって実行可能な命令、によって実現し得る。本発明のこれらの実施例はソフトウェアを用いて実現することが可能なので、本発明のそのような実施例が用いられる、代表的なプログラム可能なコンピュータ・システムの構成部分及び動作を最初に説明する。特に、プログラム可能なコンピュータの構成部分及び動作を、図４を参照して説明する。この動作環境は適切な動作環境の一例に過ぎないが、本発明の利用又は機能の範囲への制限を示唆することを企図するものではない。
【００２６】
図４では、コンピュータ４０１は、集積回路に実装されたマイクロプロセッサのような、プログラム可能な処理装置４０３を有する。コンピュータ４０１は更に複数の入出力装置４０５及び記憶装置４０７を有し得る。入出力装置４０５は利用者から入力データを受ける、若しくは、利用者に出力データを設ける、いかなる装置をも含み得る。入力装置は、例えば、利用者から入力情報を受ける、キーボード、マイクロフォン、スキャナ及びポインティング・デバイスを含み得る。出力装置はその場合、表示モニタ、スピーカ、プリンタ及び触覚フィードバック装置を含み得る。これらの装置及びそれらの接続は周知のものであり、ここでは詳細について説明しない。
【００２７】
記憶装置４０７は同様に、処理装置４０３によって、直接的に若しくは間接的にアクセスし得る、コンピュータが判読可能な媒体のいかなる組み合わせを用いても実現し得る。コンピュータが判読可能な媒体は、例えば、読み込み書き込み記憶装置（ＲＡＭ）、読み取り専用記憶装置（ＲＯＭ）、電気的に消去書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリ微小回路素子、ＣＤ−ＲＯＭディスク、ディジタル・ビデオ・ディスク（ＤＶＤ）、及び他の光記憶装置を含み得る。コンピュータが判読可能な媒体は更に、磁気カセット、磁気テープ、磁気ディスク及び他の磁気記憶装置、穿孔媒体、ホログラフィック記憶装置、及び所望の情報を記憶するのに用い得る他のいかなる媒体をも含み得る。
【００２８】
本発明の種々の実施例によれば、コンピュータ４０１は更に、他のコンピュータとデータを交換する１つ以上のインタフェース装置４０９を含み得る。該インタフェース装置４０９は、例えば、モデム、有線ネットワーク・カード、無線ネットワーク・カード、及び１つ以上のコンピュータと通信し合う他のいかなる、適切な装置をも含み得る。処理装置４０３、入出力装置４０５、記憶装置４０７及び利用者インタフェース装置４０９は各々、データ・バス４１１を用いて相互接続し得る。当業者にはよくわかるように、データ・バス４１１は適切なバス構造であれば、いかなる種別のものを用いても実現し得る。
【００２９】
（セルの階層効果の判定）
図５Ａ及び図５Ｂを参照すると、これらの図は本発明の種々の実施例によって、回路ネットリストにおけるセルの階層効果を算定する方法を表す流れ図である。この方法の利用については図６を参照して説明する。図６は、セル６０３、セル６０５、及びセル６０７のいくつかのインスタンスを含む、データ構造６０１を示す。特に、データ構造６０１はセル６０３の１０，０００のインスタンスを含む。セル６０３の各インスタンス自体は１０，０００の基本素子を含む。データ構造６０１は次にセル６０５の５０のインスタンスを含み、セル６０５自体の各インスタンスは７０の基本素子を含む。データ構造６０１は更にセル６０７の３つのインスタンスを含み、それ自体は２００の基本素子を含む。したがって、データ構造６０１は１００，０００，０００の基本素子をセル６０３に含み、３５００の基本素子をセル６０５に含み、６００の基本素子をセル６０７に含み、合わせると１００，００４，１００の基本素子になる。
【００３０】
次に図５に戻ると、セル６０３−６０７各々の階層効果の判定を次に説明する。最初に、工程５０１では、セルは１つ以上の成分を含むものとして定義される。示された実施例においては、セル６０３−６０７各々は基本素子のみを含む。したがって、この例にて判定された階層効果は絶対的階層効果となる。すなわち、絶対的階層効果とはデータ構造において他にセルが存在しないことを前提とした、セルの階層効果のことである。以下に詳説するように、セルの累積階層効果も更に判定し得る。セルの累積階層効果とはデータ構造を使ってタスクを実行するうえで１つ以上のセルの影響を考慮した、セルの階層効果のことである。前述のように、セル６０３の定義は１０，０００の基本素子を含む。セル６０５の定義はその場合、７０の基本素子を含む一方、セル６０７の定義は２００の基本素子を含む。
【００３１】
次に、工程５０３では、データ構造におけるセルの発生数が判定される。更に上記のように、セル６０３はデータ構造６０１において１０，０００回発生する。セル６０５はデータ構造６０１で５０回発生する一方、セル６０７はデータ構造６０１で３回しか発生しない。工程５０５では、データ構造のフラット・リソース値（この例では、データ構造６０１）が次に判定される。図示された実施例は配置図ネットリストと概略図ネットリストとの比較に関するものなので、この例におけるデータ構造のフラット・リソース値は、データ構造６０１と、セルの利用を伴わない対応データ構造とを比較するのに必要となる比較操作数に基づいて判定し得る。したがって、データ構造６０１を成分毎に比較するのに必要な比較操作総数はデータ構造６０１に含まれる基本素子数である、１００，００４，１００になる。
【００３２】
工程５０７においては、セルの階層リソース値が次に判定される。この値は、例えば、セルの各成分に操作を行い、更にデータ構造６０１におけるセルの各インスタンスに操作を行って所望のタスクを実行するのに必要な操作数を判定することによって入手し得る。したがって、図示された実施例においては、セルの階層リソース値は、セルの各成分を比較するのに必要な操作数と、データ構造６０１におけるセルの各インスタンスを比較するのに必要な操作数とを加算することによって判定される。さらに、図示された実施例におけるセルについて判定された階層リソース値は、データ構造全体にタスクを行うのに必要な操作総数に基づいているので、セルの内部と外部との両方の成分を考慮に入れている。
【００３３】
特に、工程５０７においては、特定のセルの階層リソース値は、例えば、セルの各成分に操作を実行し、次にセルにない各成分に操作を実行し、今度は集合したデータ構造中のそのセルの各インスタンスに操作を実行することによって、所望のタスクを実行するのに必要な操作数を判定することによって入手される。したがって、図示した実施例では、データ構造６０１におけるセルの階層リソース値は、その特定のセルの各成分を比較するのに必要な操作数を、その特定のセルにないデータ構造６０１の各要素を比較するのに必要な操作数とデータ構造におけるその特定のセルの各インスタンスを比較するのに必要な操作数に加算することによって判定される。
【００３４】
例えば、セル６０３を用いてデータ構造６０１に比較タスクを実行するには２４，１００の操作を必要とする。特に、セル６０５における基本素子各々を比較するには３５００の成分比較操作を必要とし、セル６０７における各基本素子を比較するには６００の成分比較操作を必要とする。単一セル６０３のみを比較するには、１０，０００の成分比較操作が必要になる。データ構造６０１における各セル６０３はその場合他のセルと直接比較し得、更に１０，０００のセル比較操作が必要となり、合わせて２４，１００の操作になる。
【００３５】
一方、セル６０５のみを用いてデータ構造６０１に比較タスクを実行するのには１００，０００，７２０の比較操作を必要とする。特に、１００，０００，０００の成分比較操作がセル６０３における基本素子各々を比較するのに必要である一方、セル６０７における基本素子各々を比較するには６００の成分比較操作を必要とする。単一セル６０５のみを比較するには７０の成分比較操作が必要になる。その場合、データ構造６０１におけるセル６０５の各発生を比較するには更に５０のセル比較操作を必要とし、合わせて１００，０００，７２０の比較操作になる。同様に、セル６０７のみを用いてデータ構造６０１に比較タスクを実行するには１００，００３，７０３の比較操作が必要になる。セル６０３における基本素子を比較するには１００，０００，０００の成分比較操作が必要になる一方、基本素子とセル６０５とを比較するには３５００の成分比較操作を必要とする。単一セル６０７における各成分を比較するには２００の成分比較操作を必要とする。セル６０７の各インスタンスはその場合、３つのセル比較操作を用いて比較され、合わせて１００，００３，７０３の比較操作になる。
【００３６】
最後に、工程５０９では、セルの階層効果を判定するよう、階層リソース値がフラット・リソース値と対比される。例えば、セルの階層効果は、セルを全く用いないでタスクを実行する代わりにセルを用いて得られる操作削減パーセント値であり得る。特に、階層効果は以下の式によって算定し得る：
階層効果値＝１００−（１００ｘ階層リソース値／フラット・リソース値）
したがって、上記の例では、セル６０３の階層効果は９９．９７６％になる。セル６０５はその場合０．００３３８％になる一方、セル６０７の階層効果は０．００３９７％のみとなる。したがって、セルの階層効果に基づいて、タスクを実行するようセル６０３のみを利用することによって時間及び処理リソースの実質的な削減を設ける。
【００３７】
しかしながら、階層リソース値とフラット・リソース値とを対比するには他の手法も用い得ることを理解すべきである。例えば、階層リソース値とフラット・リソース値との比率（又はフラット・リソース値と階層リソース値との比率）をセルの階層効果値として用い得る。代わりに、フラット・リソース値と階層リソース値との差異をセルの階層効果値として用い得る。階層リソース値とフラット・リソース値との関係を数量化する更に他の手法が、前記説明から当業者には更に分かるものである。
【００３８】
上記の本発明の実施例はデータ構造全体にタスクを実行するのに必要な操作総数に基づいてセルの階層効果を判定する一方、セルを用いることによって得られる操作数の削減のみに基づいてセルの階層効果を判定し得ることも特筆する。したがって、これらの実施例はデータ構造にタスクを実行するのに必要な、セルの外の成分に行われる操作数を考慮していない。
【００３９】
更に、本発明の種々の実施例は他の基準を用いてセルの階層効果を判定し得る。例えば、本発明の実施例のいくつかは、セルを用いてタスクを実行するのに必要な記憶容量とセルを用いずにタスクを実行するのに必要な記憶容量との対比に基づいた、セルの階層効果を判定し得る。当然、セルの階層効果を判定する他の所望の基準も更に利用し得る。
【００４０】
したがって、セルの階層効果を判定する種々の実施例はセルを用いて獲得し得る便益の数量化可能な判定を利用者に設ける。セルの階層効果は、例えば、そのｈ−セルの同等物を識別するのに用い得る。例えば、概略図データ構造におけるセルの階層効果が対応する配置図データ構造におけるセルの階層効果と突合する場合、それらのセルをｈ−セル対として比較し得る。以下に詳説するように、セルの階層効果は更に配置図データ構造を概略図データ構造と比較するのにｈ−セル対を利用するかどうかを判定するのに用い得る。好都合にも、タスクを実行するのにｈ−セル対全体を用いるかどうかを判定するのにｈ−セル対の何れかのセルの階層効果を利用し得る。
【００４１】
（タスクを実行するのに利用するセルの判定）
セルの階層効果が判定されると、該セルの階層効果は、データ構造にタスクを実行する場合に利用するのに十分高い階層効果をどのセルが有するかを選択するのに用い得る。図７はデータ構造にタスクを実行する場合に、階層データ構造中のどのセルを利用すべきかを決定するツール７０１を示すものである。特に、ツール７０１はセル階層効果ランキング・モジュール７０３及び総階層効果判定モジュール７０５を含む。以下に詳説するように、セル階層効果ランキング・モジュール７０３はタスクが実行されるデータ構造を含むデータ構造入力７０７を受ける。セル階層効果ランキング・モジュール７０３は次に入力データ構造における各セルの階層効果ランキングを判定する。以下に更に詳説するように、総階層効果判定モジュール７０５はセル階層効果ランキング・モジュール７０３によって設けられたランキングに基づいた入力データ構造の種々のセルを用いて総階層効果を判定する。セル階層効果ランキング・モジュール７０３と総階層効果判定モジュール７０５とは、データ構造を使ってタスクを実行するのに用いられる、選択セルのリスト７０９が入手されるまでデータを交換し続ける。
【００４２】
ツール７０１の動作は図８Ａ−８Ｃに表される流れ図及び図９と１０に示されるデータ構造を参照して詳説する。以下に詳説されるように、図９は複数のセル６０３−９０７を有するデータ構造を図で表すものである。さらに、これらのセルのうちの１つ、セル９０３自体は、図１０に表されるように、複数の下位セル１００１からできている。最初に、工程８０１では、セル階層効果ランキング・モジュール７０３がデータ構造９０１におけるセル群を定義する。次に、工程８０３では、セル階層効果ランキング・モジュールはデータ構造９０１における各セルの発生数を判定する。次に図９によれば、データ構造９０１はセル９０３、９０５、及び９０７を含む。特に、データ構造９０１はセル９０３の１００のインスタンスを含み、該インスタンス各々は、今度は１，０００，０００の基本素子を含み、合わせて１００，０００，０００の基本素子になる。データ構造９０１は更にセル９０５の５０のインスタンスを含み、それらの各々は７０の基本素子を含み、合わせて３５００の基本素子となり、セル９０７の３つのインスタンスは、それらの各々が２００の基本素子を含み、合わせて６００の基本素子になる。したがって、データ構造９０１における基本素子を全て比較するのに必要な成分比較操作総数は１００，００４，１００になる。
【００４３】
工程８０５では、総階層効果判定モジュール７０５はデータ構造９０１の総累積リソース値を判定する。すなわち、総階層効果判定モジュール７０５はデータ構造９０１における全てのセルを用いて所望のタスクを実行することに関係する総累積リソース値を判定する。図９に表される例では、総累積リソース値は２４２３になる。特に、単一セル１００１のみを比較するには１０００の成分比較を必要とし、その場合、セル９０３における各セル１００１は１，０００のセル比較操作を用いて比較し得、合わせて２，０００の操作になる。セル９０３の各インスタンスは、今度は更に１００のセル比較操作によって比較され、操作数は合わせて２，１００となる。単一セル９０５のみを比較するには７０の成分比較操作を必要とする。その場合、更に５０のセル比較操作がデータ構造９０１におけるセル９０５の各発生を比較するのに必要になる。単一セル９０７において各成分を比較するには２００の成分比較操作を必要とする。セル９０７の各インスタンスは次に３つのセル比較操作を用いて比較し得、操作数合計は２４２３になる。
【００４４】
次に、工程８０７においては、セル階層効果ランキング・モジュール７０３は選択セルの累積階層リソース値を判定する。処理のこの段階において、セルは選択されない。したがって、選択セルの累積階層リソース値はデータ構造９０１における基本素子全てを比較するのに必要な成分比較操作数と同一で、上記のように、１００，００４，１００になる。
【００４５】
次に、工程８０９では、総階層効果判定モジュール７０５は選択セルの階層累積リソース値を総累積リソース値と対比することによって削減値を判定する。この実施例においては、総累積リソース値は以下の式によって判定される：
削減値＝１００ｘ（（累積階層リソース値−総累積リソース値）／累積階層リソース値）。
【００４６】
したがって、初期の削減値は１００ｘ（（１００，００４，１００−２４２３）／（１００，００４，１００）＝９９．９９７５％となる。したがって、これはデータ構造における残りのセルを全て用いることによって獲得し得る更なる削減である。
【００４７】
次に、工程８１１では、総階層効果判定モジュール７０５は判定された削減値を所望の閾値と比較し、タスクを実行するデータ構造における残りの非選択セルを用いて設けられる累積削減は十分に高いかどうかを判定する。該削減値が閾値を超えない場合（すなわち、最低の削減が、データ構造における残りの非選択セルを用いることによって獲得し得ない場合）、セルを選択する処理は終結し、工程８１３にてタスクが実行される。図示された実施例においては、閾値は３０％であるので、初期の削減値は閾値を越えるのに十分高い。したがって、セルを選択する処理は、最高累積階層効果ランキングを有する非選択セルが識別される、工程８１５に続く。
【００４８】
最高累積階層効果ランキングを有する非選択セルを判定するのに、セル階層効果ランキング・モジュール７０３はデータ構造９０１における各セルの累積階層リソース値を判定し得る。未だ全くセルが選択されていないので、各セルの累積階層リソース値は各セルの絶対的階層リソース値と同一になる。したがって、セル９０３を用いてデータ構造９０１に比較タスクを実行するには１，００４，２００操作を必要とし、セル９０３には１，００４，２００の累積階層リソース値を与える。特に、３５００の比較操作が、セル９０５における基本素子各々を比較するのに必要になり、セル９０７における基本素子各々を比較するには６００の成分比較操作が必要になる。単一セル９０３のみを比較するには、１，０００，０００成分比較操作が必要になり、データ構造６０１の各セル９０３は更に他のセルと直接比較し得、更にはセル比較操作が１００のみ必要になり、合わせて１，００４，２００の操作になる。
【００４９】
セル９０５のみを用いてデータ構造９０１に比較タスクを実行するには１００，０００，７２０の比較操作を必要とする。特に、１００，０００，０００の成分比較操作がセル９０３における基本素子各々を比較するのに必要になる一方、セル９０７における基本素子の各々を比較するには６００の成分比較操作が必要になる。単一セル９０５のみを比較するには７０の成分比較が必要になる。データ構造９０１においてセル９０５の各発生を比較するには更に５０のセル比較操作がその場合必要になり、合わせて１００，０００，７２０の比較操作総数を設ける。セル９０７のみを用いてデータ構造９０１に比較タスクを実行するにはその場合１００，００３，７０３比較操作が必要になる。再びセル９０３の基本素子を比較するには１００，０００，０００の成分比較操作を必要とする一方、基本素子とセル９０５とを比較する場合には３５００の成分比較操作を必要とする。単一セル９０７における各成分を比較するには２００の成分比較操作を必要とする。セル９０７の各インスタンスはそうすると３つのセル比較操作を用いて比較され得、合わせて１００，００３，７０３の比較操作になる。
【００５０】
図１０に表されるように、セル９０３はセル１００１の１０００のインスタンスに分割し得、各々は１，０００の基本素子を含む。したがって、このセルの階層効果ランキングも考慮されなければならない。セル９０１に比較タスクを実行するようセル１００１が利用される場合、１０５，１００比較操作が必要になる。上記のように、セル９０５における基本素子各々を比較するには３５００の成分比較操作が必要になり、セル９０７における基本素子各々を比較するには６００の成分比較操作が必要になる。各セル９０３は１，０００のセル１００１を含み、データ構造９０１は１００のセル９０３を含み、合わせて１００，０００のセル１００１になる。単一セル１００１のみを比較するには、１，０００の成分比較操作が必要になり、合わせて１０５，１００の操作が必要になる。
【００５１】
したがって、セル９０３は９８．９９％の絶対的階層効果値を有する一方、セル９０５の絶対的階層効果値は０．００３３８％になる。同様に、セル９０７の絶対的階層効果値は０．０００３９７％である一方、セル１００１の絶対的階層効果値は９９．８９％になる。したがって、セル１００１はデータ構造９０１の全てのセルのうち、最高の累積（及び絶対的）階層効果ランキングを有する。したがって、工程８１７においては、セル１００１は選択セルのリストに加えられる。
【００５２】
上記の例においては、上記階層効果値は最高階層効果ランキングを有するセルを判定するのに用いたことを特筆する。しかしながら、最高階層効果ランキングを有するセルを判定するのに他の値を利用し得ることを特筆する。例えば、本発明の実施例のいくつかは、最高階層効果ランキングを有するセルは各セルの累積階層リソース値を用いて識別し得る。したがって、最低階層リソース値を有するセルは最高階層効果ランキングを有するセルとして識別される。
【００５３】
次に工程８０７に戻り、総階層効果判定モジュールは選択セル（この例においては、セル１００１）の累積階層リソース値を判定する。したがって、工程８０７を繰り返す場合、データ構造９０１の総累積リソース値は１０５，１００となる。特に、１，０００の成分比較操作が、セル１００１の単一インスタンスにおける基本素子を比較するのに必要になり、次に１００，０００のセル比較操作が、データ構造９０１におけるセル１００１の発生の全てを比較するのに必要になる。他の３５００及び６００の成分比較操作が今度はセル９０５と９０７各々にある基本素子を比較するのに必要になり、合わせて１０５，１００の操作になる。
【００５４】
次に、工程８０９を繰り返すことによって、総階層効果判定モジュール７０５は総累積リソース値を選択セルの階層累積リソース値と対比することによって削減値を判定する。この実施例においては、削減値は再び、以下の式によって判定される：
（削減値）＝１００Ｘ（（累積階層リソース値−総累積リソース値）／累積階層リソース値）。
【００５５】
したがって、セル１００１を用いる際の累積削減値は１００Ｘ（（１０５，１００−２４２３）／１０５，１００）＝９７．６９％
になる。したがって、これはセル１００１を用いることに加えてデータ構造における残りの全てのセルを用いることによって獲得し得る更なる削減である。
【００５６】
次に、工程８１１においては、この削減値は再び、３０％の閾値を超えるものと判定される。したがって、工程８１５においては、セル階層効果ランキング・モジュール７０３は最高の累積階層効果ランキングを有する非選択セルを判定する。したがって、セル９０３の累積階層リソース値は６，２００になる。特に、１，０００の成分比較操作が、セル１００１の１インスタンスにおける全ての基本素子を比較するのに必要になり、別の１０００のセル比較操作がセル９０３の単一インスタンスにおける全てのセル１００１を比較するのに必要になる。データ構造９０１においてセル９０３の全てのインスタンスを比較するには１００のセル比較操作のみが必要になり、合わせて２１００の操作になる。上記のように、セル９０５とセル９０７各々における基本素子を比較するには３５００と６００の成分比較操作が必要になり、合わせて６２００の操作になる。同様の分析を用いれば、セル９０５の累積階層リソース値は１０１，７２９になる一方、セル９０７の累積階層リソース値は１０４，７０３になる。したがって、セル９０３の累積階層効果値は９４．１％になる一方、セル９０３及び９０５の累積階層効果値は各々、３．２％及び０．３７７％になる。したがって、工程８１７が繰り返されると、セル９０３が選択される。
【００５７】
工程８０７に戻ると選択セルの累積階層リソース値は６２００になる。次に工程８０９が再び繰り返されるとセル９０３を用いる場合に得られる削減値は１００Ｘ（（６２００−２４２３）／６２００）＝６０．９１％になる。再び、この値は工程８１１において３０％の閾値よりも高いものと判定されるため、セル階層効果ランキング・モジュール７０３は工程８１５において最高累積階層効果ランキングを有する残りの非選択セルを判定する。
【００５８】
タスクを実行するのにセル９０５と９０７との何れを利用すべきかを判定する処理が再び繰り返される場合、累積リソース値は６２００になる。セル９０５の累積階層リソース値はそうすると２８２０になる一方、セル９０７の累積階層リソース値は５８０３になる。したがって、セル９０５の累積階層効果値は５４．５％になる一方、セル９０７の累積階層効果値は６．４％になり、セル９０５に最高階層効果ランキングを与える。したがって、工程８１７においては、セル９０５が選択される。工程８０７に戻ると、セル階層効果ランキング・モジュール７０３は選択セルの累積階層リソース値が２８２０であることを判定する。したがって、セル９０５の累積階層リソース値が次にデータ構造９０１の総累積リソース値と対比された場合、削減値は、１００Ｘ（（２８２０−２４２３）／２８２０）＝１４．０７％になる。
【００５９】
この値は工程８１３においては３０％の閾値を下回るものと判定されるため、更なるセルは選択されない。その代わりに、工程８１３において、所望のタスクは選択セル（この例においては、セル１００１、９０３及び９０５）を用いて実行される。
【００６０】
したがって、本発明の種々の実施例は階層データ構造におけるどのセルが、データ構造を使った所望のタスクを実行するのに最も効果的であるかを判定する手法を設けるものである。したがって、本発明の実施例は、概略図データ構造と配置図データ構造のどのｈ−セル対を、概略図データ構造と配置図データ構造とを比較するのに利用すべきかを判定するのに利用し得るものである。
【００６１】
本発明は現時の好適実施形態を含む特定例に関して説明したが、当業者には、本発明の特許請求の範囲にて記載された本発明の精神及び範囲に収まる、上記のシステム及び手法の数々の変形例及び置換があることがわかるものである。
【図面の簡単な説明】
【００６２】
【図１】回路の概略図である。
【図２】図１に表された回路に対応する配置図である。
【図３】データ構造がいかにして階層配列を有し得るかの例を表した図である。
【図４】本発明の種々の実施例を実現するのに用い得るプログラム可能なコンピュータの一実施例である。
【図５Ａ】本発明の種々の実施例による、データ構造におけるセルの階層効果を判定する方法を説明した流れ図である。
【図５Ｂ】本発明の種々の実施例による、データ構造におけるセルの階層効果を判定する方法を説明した流れ図である。
【図６】階層配列を有するデータ構造を示した図である。
【図７】配置図データ構造と概略図データ構造とを比較する場合にｈ−セル対の利用を判定するツールを示した図である。
【図８Ａ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図８Ｂ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図８Ｃ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図９】階層配列を有するデータ構造を示した図である。
【図１０】階層配列を有するデータ構造を示した図である。
【図１】
2004303234.tif 000003
【図２】
2004303234.tif 000004
【図３】
2004303234.tif 000005
【図４】
2004303234.tif 000006
【図５Ａ】
2004303234.tif 000007
【図５Ｂ】
2004303234.tif 000008
【図６】
2004303234.tif 000009
【図７】
2004303234.tif 000010
【図８Ａ】
2004303234.tif 000011
【図８Ｂ】
2004303234.tif 000012
【図８Ｃ】
2004303234.tif 000013
【図９】
2004303234.tif 000014
【図１０】
2004303234.tif 000015
【手続補正書】
【提出日】平成16年3月26日(2004.3.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層データ構造におけるセルの評価に関する。本発明の種々の実施例は特に、回路配置図用データ構造と回路概略図用データ構造とを比較するのに用いられるセルの効果の判定への適合性を有する。
【背景技術】
【０００２】
コンピュータが精巧になるにつれ、それらのコンピュータによって利用し得るデータ構造は大型化している。例えば、マイクロプロセッサのような、今までのものと違った集積回路の設計は何百万ものトランジスタ及び他の電気素子を、論理回路、記憶回路、プログラム可能なフィールド・アレイ、あるいは他の回路素子の中に構成することを含み得る。コンピュータがこれらの大規模データ構造をより容易に処理することを可能にする（とともに、利用者がよりよくデータ構造を理解することを可能にする）ために、大規模データ構造はよく、セルの階層編成に分割されている。したがって、上記の例においては、単一の記憶回路を構成しているトランジスタ全てを単一のセルに分類し得る。そうすることによって、個々のトランジスタ各々を列挙する必要なしで、記憶素子を構成するトランジスタ群が一単位として、集合的に参照され、かつ、操作されることを可能にする。例えば、今までのものと違った集積回路の設計を含むデータ構造を生成する場合、設計者は、単に、所望の記憶装置を表すセルに対応するデータについての単一の参照を一回の操作で加えることが、記憶素子を構成する各々のトランジスタについてのデータを個々に加える必要なしで、可能になる。
【０００３】
一般にセルに分割されたデータ構造において、セルは階層的に配置される。最下位のセルはデータ構造の基本要素のみを含み得る。中位のセルはその場合１つ以上の低位セルを含み得、高位のセルは、その場合１つ以上の中位セルを含み得る、などである。更に、いくつかのデータ構造においては、セルは１つ以上の下位セルをデータ構造の基本要素に加えて含み得る。したがって、上記の例においては、レジスタを表すデータのセルは記憶回路を表すデータのセルのいくつかのインスタンス、種々の論理素子を表すデータの異なったセルのいくつかのインスタンス、及び特定用途の接続回路を表す要素データを含み得る。同様に、メモリアレイを表すデータのセルは、レジスタを表すデータのセルのいくつかのインスタンスを、特別用途の接続回路を表す要素データとともに、含み得る。
【０００４】
データ構造をセルに分割することによってより効率的に、かつ、より少ないリソースにてデータ構造を使ってタスクを実行し得る。例えば、集積回路の概略図を定義するデータ構造は、集積回路を形成するのに必要な材質の配置図を定義する、対応するデータ構造に変換されなくてはならない。概略図（すなわち、「ソース」情報）を記述するデータ構造を材質の配置図を記述するデータ構造に変換する過程においては、しかしながら、エラーがもたらされる可能性がある。したがって、実動ラン、すなわち、変換された配置図データ構造に基づいた集積回路の製造を行うのに多額を費やす前に、配置図データ構造は元の概略図データ構造と注意深く比較される。両方のデータ構造をセル階層に分けることなく、両方のデータ構造の要素毎の比較を行わなければならない。多数のトランジスタを有する、超大規模集積回路においては、そのような比較は、実際の役に立つには長すぎる。しかしながら、両方のデータ構造をセルに分割することによって、配置図データ構造の正確性を確認するのにより少ないデータ単位の比較で済むことが可能になる。したがって、当該比較は、より速く、かつ、より少ない処理リソースを用いて行い得る。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
データ構造におけるセルの利用によって、より効率的にデータ構造を使ってタスクを実行することが可能となり得る一方、セルの利用自体がタスクの実行においてエラーをもたらし得る。したがって、上記の例では、概略図データ構造におけるセルが、不注意にも、配置図データ構造における誤ったセル（すなわち、概略図データ構造におけるセルに対応することが企図されていないセル）と比較された場合、当該比較タスクによって誤って、概略図データ構造と配置図データ構造との要素毎比較によって回避される、エラーが明らかにされる。当業者にはわかるように、いくつかのセルの利用は比較における処理オーバヘッドあるいはメモリ使用量を低減するのに非常に効果的であるものの、他のセルの利用は処理オーバヘッドあるいはメモリ使用量にはあまり影響がないかもしれない。通常は、しかしながら、比較演算のような、タスクを実行するのにどのセルを利用するのが有用であるかを判定するのは困難である。
【課題を解決するための手段】
【０００６】
好都合にも、本発明の種々の実施例はデータ構造を使ってタスクを実行するのにどのくらいセルの利用が効果的であるかを示す階層効果を設ける。本発明の種々の実施例によれば、セルの階層効果はまず、データ構造を使ってデータ構造中の個々の要素各々に操作を行うことによってタスクを実行するのに必要な操作数を判定することによって得られる。次に、セルの個々の成分各々に操作を実行し、それから、データ構造中に発生するそのセルの各インスタンスに必要な操作を実行することによってタスクを実行する、のに必要な操作数が判定される。これらの操作数の対比は、例えば、セルを用いてタスクを実行することによって得ることが可能な効率向上を示す、パーセント値、として都合よく定量化し得る。
【０００７】
本発明の更に他の実施例は、データ構造を使ってタスクを実行するようどのセルを利用すべきかを判定するのに、データ構造における全てのセルの階層効果を得ることを可能にする。これらの実施例では、データ構造中の選択セル各々の階層効果が判定され、タスクを実行するようデータ構造中のセル全てを用いて得られる効率と対比される。したがって、選択セルを用いる階層効果と全てのセルを用いる効果とを対比させることによって得られる削減値は、残りの、非選択セルを用いることによって得ることが可能な削減量である。当該削減値が閾値を超えている場合は、最高累積階層効率を有するセルがタスクを実行するのに利用される選択セルのリストに加えられる。この処理は、タスクを実行するのに選択されたセル各々を考慮して、更に繰り返される。選択セルが当該閾値を超える削減値を設けない場合は、選択セルがタスクを行うのに利用される一方、他の残りのセル全て（すなわち、非選択セル）はタスクを実行するのに利用されない。
【発明を実施するための最良の形態】
【０００８】
本発明のよりよい理解を設けるよう、本発明の種々の実施例を、集積回路の元の概略図を記述するデータ構造と集積回路を実現する材質の配置を記述するデータ構造との比較に関して説明する。したがって、概略図のデータ構造と配置図データ構造との比較処理の簡単な説明を本発明の種々の実施例を実現し得る一動作環境の例とともに記述する。本発明の種々の実施例によるセルの階層効果の判定を次に説明し、概略図データ構造と配置図データ構造とを比較するような、タスクを実行するのに利用すべきセルはどれかを判定することに階層効果を適用することについても説明する。
【実施例】
【０００９】
（概略図と配置図のデータ構造）
次に図１を参照すると、図１は簡単な電子回路１０１を表す概略図を示す。図１からわかるように、回路１０１は、（コネクション端点「１」と名付けられた）ドレイン１０５、（コネクション端点「２」と名付けられた）ゲート１０７、及び（コネクション端点「３」と名付けられた）ソース１０９を有する、電界効果トランジスタ１０３を含む。回路１０１は電界効果トランジスタ１０３と更に（コネクション端点「３」にて接続された）第２電界効果トランジスタ１１１を含む。電界効果トランジスタ１１１は（コネクション端点「３」と名付けられた）ドレイン１１３、（コネクション端点「４」と名付けられた）ゲート１１５、及び（コネクション端点「５」と名付けられた）ソース１１７を含む。
【００１０】
図１に表された種の概略図は、回路の動作を理解するうえで有用な反面、集積回路を実際に作製するのには直接利用し得ない。その代わりに、回路配置図は回路概略図に基づいて作成される。配置図は回路の実際の構造を形成する材質の配置に対応する多角形を定義する。配置図はその場合は、例えば、回路の構造の製造用の１つ以上のリソグラフ画像を形成するのに用い得る。
【００１１】
例えば、図２は図１に表される電子回路１０１を物理的に実現する例示的配置図２０１を示す。したがって、配置図２０１は電界効果トランジスタ１０３に対応する電界効果トランジスタ２０３、及び電界効果トランジスタ１１１に対応する電界効果トランジスタ２１１を含む。トランジスタ２０３はドレイン１０５を形成するのに用いられる要素の配置を示す多角形２０５、ゲート１０７を形成するのに用いられる材質の配置図に対応する多角形２０７、及びソース１０９を形成するのに用いられる材質の配置図に対応する多角形２０９を含む。同様に、トランジスタ２１１はドレイン１１３を形成するのに用いられる材質の配置図を示す多角形２１３、ゲート１１５を形成するのに用いられる材質の配置図に相当する多角形２１５、及びソース１１７を形成するのに用いられる材質の配置図に相当する多角形２１７を含む。
【００１２】
当業者はよくわかるように、図１に示された種の概略図及び図２にて示された種の配置図は簡単な電子素子を理解するのに有用で有り得る一方、大規模集積回路を記述するのに効果的に用いるには非効率的すぎる。その代わりに、概略図と配置図との両方に表される情報を記述するのに種々のデータ構造が用いられる。時には「ネットリスト」と呼ばれる、一種のデータ構造の例を以下に表す：
Ｍ１    １      ２      ３      Ｐ
Ｍ２    ３      ４      ５      Ｎ
ネットリストの第１行は電界効果トランジスタ１０３を素子Ｍ１として定義し、このトランジスタはＰ型トランジスタであることを示す。更にトランジスタ１０３のドレイン１０５はコネクション端点「１」に接続され、ゲート１０７はコネクション端点「２」に接続され、ソース１０９はコネクション端点「３」に接続される。ネットリストの第２行は第２電界効果トランジスタ１１１をＭ２と呼び、このトランジスタがＮ型トランジスタであることを示す。ネットリストの第２行は更に電界効果トランジスタ１１１のドレイン１１３が更にコネクション端点「３」（と、したがって電界効果トランジスタ１０３のソース１０９にも）接続され、ゲート１１５がコネクション端点「４」に接続され、ソース１１７がコネクション端点「５」に接続されていることを示す。したがって、ネットリストは図１に表される概略図において定義される回路１０１の適切な特性を識別する。
【００１３】
同様に、回路配置図中に示される情報を記述するのにさまざまなデータ構造の種別を用い得る。例えば、回路配置図に定義された多角形情報を記述するにはＧＤＳＩＩデータ・フォーマットが用いられる。この種のデータ・フォーマットは、例えば、配置図中に定義された多角形に相当する材質構造を生成するフォトリソグラフィ装置によって自動的に利用し得る。当業者にはよくわかるように、配置図に表される情報は上記のようなネットリストに変換し得る。配置図のネットリストは、例えば、ＧＤＳＩＩフォーマットから変換し得る。
【００１４】
（配置図と概略図との比較）
したがって、回路の機能を設計するには概略図を利用し得、その場合、回路を作製するよう、配置図が概略図から形成される。配置図は一般に元の概略図から形成される一方、配置図はしかしながら概略図とは有意な差異を含み得る。例えば、配置図を作成する場合、集積回路の表面積の利用の最適化を図るよう配置図に種々の変更を行ない得る。回路の最終配置図はしたがって、元の概略図において企図された動作とは異なった動作をさせるエラーを含み得る。したがって、集積回路を実際に作製するのに配置図を用いる前に、配置図が正確であることを確実にするよう、配置図の最終版が、当該最終版が基にする元の概略図とチェックされる。例えば、上述のように、ＧＤＳＩＩフォーマットによる最終配置図はネットリスト・フォーマットに変換し得、元の概略図を記述するネットリストと比較される。
【００１５】
今日の集積回路の規模の観点からは、しかしながら、概略図ネットリストの各要素と、対応する配置図ネットリストの各要素を比較するのは非常に困難である。例えば、プログラム可能なマイクロプロセッサを形成する集積回路は何億ものトランジスタを含み得る。各トランジスタのネットリスト・データを比較するには、その場合、完了するのに非現実的な時間とリソースの使用を必要とする。その代わりに、概略図ネットリストと配置図ネットリストは両方とも、異なったレベルの再発セルを含む階層構造に編成される。すなわち、特定の配置において繰り返し発生する素子は、セルと呼ばれる、一単位にまとめ得る。
【００１６】
例えば、素子群が記憶回路を形成するよう規則正しく編成されている場合、これらはセルにまとめ得る。その場合、セルは記憶回路の各素子を比較するよりも、概略図ネットリストと配置図ネットリストとの比較用一データ単位として用い得る。特に、概略図ネットリストと配置図ネットリストとを比較するタスクを実行する場合、概略図ネットリスト中のセルの成分を配置図ネットリスト中の対応するセルの成分と比較し得る。成分が同等の場合、セルはその後同等のものとして処理し得る。したがって、セルが配置図のネットリストに再発する毎に、概略図ネットリストとは再び比較されない。
【００１７】
セル自体が他のセルを含んで、階層データ構造を形成することがある。例えば、図３は（セル「Ｚ」と名付けられた）セル３０１を示す。セル３０１は、今度は（セル「Ａ」と名付けられた）セル３０３の複数のインスタンス及び（セル「Ｂ」と名付けられた）セル３０５の単一インスタンスを含む。セル「Ａ」に対応する例示的ネットリストは以下のように表される：
．ｓｕｂｃｋｔ      Ａ      １      ２
Ｍ１      １        ３      ４      Ｐ
Ｍ２      ４        ５      ２      Ｎ
．ｅｎｄ
したがって、ネットリストは、コネクション端点１及び２に接続されていて、端点１、３、及び４に接続があるＰ型トランジスタを有し、端点４、５、及び２に接続があるＮ型トランジスタを有するようにセル「Ａ」を定義する。
【００１８】
同様に、セル「Ａ」を組み入れたセル「Ｚ」に対応する例示的ネットリストを以下に表す。
【００１９】
．ｓｕｂｃｋｔ      Ｚ    １０    ２０    ３０    ４０
Ｘ１      １０      ２０    Ａ
Ｘ２      ２０      ３０    Ａ
Ｘ３      ３０      ４０    Ｂ
：
：
．ｅｎｄ
したがって、このネットリストはセル「Ｚ」がコネクション端点１０、２０、３０及び４０にて接続を有するよう定義している。該ネットリストは更にセル「Ｚ」の第１成分を端点１０及び２０にて接続を有するセル「Ａ」のインスタンスとして、セル「Ｚ」の第２成分を端点２０及び３０にて接続を有するセル「Ａ」のインスタンスとして、かつ、セル「Ｚ」の第３成分を、端点３０及び４０にて接続を有するセル「Ｂ」のインスタンスとして定義している。
【００２０】
セル構造を明らかにするよう、データ構造の階層配列によって更に小さい部分に細分し得ない、データ構造の一部分を呼ぶのに、「要素」又は「基本素子」の語を以下に用いる。その場合、「セル」の語はデータ構造の階層配列によって更に小さい部分に細分し得るデータ構造のいずれかの部分を呼ぶのに用いる。「成分」の語はその場合、「セル」、及び「要素」又は「基本素子」の両方を呼ぶのに包括的に用いられる。したがって、セルの成分は、１つ以上の他のセル、１つ以上の基本素子、又は両方の組み合わせで有り得る。
【００２１】
セルの利用が、配置図ネットリスト（又は他のデータ構造）と概略図ネットリストとを比較するのに必要な比較操作数を実質的に削減し得る一方、比較するセルを最初に決定しなければならない。すなわち、概略図ネットリストと配置図ネットリスト中の、（「ｈ−セル」又は「ｈ−セル」対と呼ばれる）対応するセル対を、比較する以前に最初に、比較タスクの正確性の観点から、明確化しなければならない。
【００２２】
ｈ−セル対はさまざまなやり方で選択し得る。例えば、配置図ネットリストは元の概略図から導き得るので、概略図ネットリストと配置図ネットリスト中のネットリスト対応セルは同一又は類似の名称を共有し得る。代わりに、ｈ−セル対は利用者によって指定し得る。ｈ−セル対を指定するこの手法は、例えば、利用者が、概略図データ構造、配置図データ構造、又は両方を生成するよう、標準セル手法を用いた場合に有用であり得る。更に、発見的方法を、概略図データ構造と配置図データ構造との間のｈ−セル対を突合するよう、利用し得る。例えば、概略図データ構造と配置図データ構造とがちょうど５２３のインスタンスを有するセルを含む場合、それらのセルはおそらく同等で、したがってｈ−セル対として指定し得る。
【００２３】
セルの利用によって概略図ネットリストと配置図ネットリストとを比較するうえでの処理オーバヘッドを実質的に低減し得る一方、不正確なｈ−セル対の選択によって比較タスクに有意なエラーを引き起こし得る。例えば、概略図ネットリストにおけるセルが、配置図ネットリスト中の非同等セルとのｈ−セル対の一部分として誤って示された場合、比較タスクは、セルが同等ではないことを示すエラーを設けるであろう。利用者は、しかしながら、配置図ネットリストが実際にエラーを含んでいたのでエラーが引き起こされたのか、若しくは二つのセルが実は同等でなく比較すべきでなかったので、エラーが引き起こされたのかを判定することは不可能である。したがって、その場合、各セルの成分は、より高位の親セルに関して成分毎にて比較されなければならない。セルは同等ではないので、親セルはおそらく同様に、同等ではなく、したがって他の更に高位の親セルがもしあれば、成分毎に比較する必要がある。このセルを拡張する処理は比較タスクが非現実的に長くなるまで続け得る。
【００２４】
したがって、概略図ネットリストを配置図ネットリストと比較するタスクを実行する場合、比較処理において実質的な削減を設けるｈ−セル対のみを利用するだけが望ましい。比較処理において実質的な削減を設けないｈ−セル対は、該ｈ−セル対が、実際に、同等ではない場合に不正確なエラーを引き起こすのを回避するよう、成分毎に比較し得る。本発明の種々の実施例はデータ構造におけるセルの階層効果値を判定し得るのが好都合である。その場合、相対的に高い階層効果値を有するセルを、配置図ネットリストと概略図ネットリストとを比較するような、所望のタスクに利用し得る。十分に高い階層効果値を有しないそれらのセルは所望のタスクを実行する場合には無視し得る。
【００２５】
（動作環境）
当業者にはよくわかるように、セルの階層効果の判定及び利用はソリッド・ステート回路のような、電子回路を用いて行ない得る。本発明の種々の実施例は、しかしながら、プログラム可能な演算素子にて実行される、ソフトウェア・プログラム・モジュールのような、コンピュータによって実行可能な命令、によって実現し得る。本発明のこれらの実施例はソフトウェアを用いて実現することが可能なので、本発明のそのような実施例が用いられる、代表的なプログラム可能なコンピュータ・システムの構成部分及び動作を最初に説明する。特に、プログラム可能なコンピュータの構成部分及び動作を、図４を参照して説明する。この動作環境は適切な動作環境の一例に過ぎないが、本発明の利用又は機能の範囲への制限を示唆することを企図するものではない。
【００２６】
図４では、コンピュータ４０１は、集積回路に実装されたマイクロプロセッサのような、プログラム可能な処理装置４０３を有する。コンピュータ４０１は更に複数の入出力装置４０５及び記憶装置４０７を有し得る。入出力装置４０５は利用者から入力データを受ける、若しくは、利用者に出力データを設ける、いかなる装置をも含み得る。入力装置は、例えば、利用者から入力情報を受ける、キーボード、マイクロフォン、スキャナ及びポインティング・デバイスを含み得る。出力装置はその場合、表示モニタ、スピーカ、プリンタ及び触覚フィードバック装置を含み得る。これらの装置及びそれらの接続は周知のものであり、ここでは詳細について説明しない。
【００２７】
記憶装置４０７は同様に、処理装置４０３によって、直接的に若しくは間接的にアクセスし得る、コンピュータが判読可能な媒体のいかなる組み合わせを用いても実現し得る。コンピュータが判読可能な媒体は、例えば、読み込み書き込み記憶装置（ＲＡＭ）、読み取り専用記憶装置（ＲＯＭ）、電気的に消去書き込み可能ＲＯＭ（ＥＥＰＲＯＭ）、フラッシュ・メモリ微小回路素子、ＣＤ−ＲＯＭディスク、ディジタル・ビデオ・ディスク（ＤＶＤ）、及び他の光記憶装置を含み得る。コンピュータが判読可能な媒体は更に、磁気カセット、磁気テープ、磁気ディスク及び他の磁気記憶装置、穿孔媒体、ホログラフィック記憶装置、及び所望の情報を記憶するのに用い得る他のいかなる媒体をも含み得る。
【００２８】
本発明の種々の実施例によれば、コンピュータ４０１は更に、他のコンピュータとデータを交換する１つ以上のインタフェース装置４０９を含み得る。該インタフェース装置４０９は、例えば、モデム、有線ネットワーク・カード、無線ネットワーク・カード、及び１つ以上のコンピュータと通信し合う他のいかなる、適切な装置をも含み得る。処理装置４０３、入出力装置４０５、記憶装置４０７及び利用者インタフェース装置４０９は各々、データ・バス４１１を用いて相互接続し得る。当業者にはよくわかるように、データ・バス４１１は適切なバス構造であれば、いかなる種別のものを用いても実現し得る。
【００２９】
（セルの階層効果の判定）
図５Ａ及び図５Ｂを参照すると、これらの図は本発明の種々の実施例によって、回路ネットリストにおけるセルの階層効果を算定する方法を表す流れ図である。この方法の利用については図６を参照して説明する。図６は、セル６０３、セル６０５、及びセル６０７のいくつかのインスタンスを含む、データ構造６０１を示す。特に、データ構造６０１はセル６０３の１０，０００のインスタンスを含む。セル６０３の各インスタンス自体は１０，０００の基本素子を含む。データ構造６０１は次にセル６０５の５０のインスタンスを含み、セル６０５自体の各インスタンスは７０の基本素子を含む。データ構造６０１は更にセル６０７の３つのインスタンスを含み、それ自体は２００の基本素子を含む。したがって、データ構造６０１は１００，０００，０００の基本素子をセル６０３に含み、３５００の基本素子をセル６０５に含み、６００の基本素子をセル６０７に含み、合わせると１００，００４，１００の基本素子になる。
【００３０】
次に図５に戻ると、セル６０３−６０７各々の階層効果の判定を次に説明する。最初に、工程５０１では、セルは１つ以上の成分を含むものとして定義される。示された実施例においては、セル６０３−６０７各々は基本素子のみを含む。したがって、この例にて判定された階層効果は絶対的階層効果となる。すなわち、絶対的階層効果とはデータ構造において他にセルが存在しないことを前提とした、セルの階層効果のことである。以下に詳説するように、セルの累積階層効果も更に判定し得る。セルの累積階層効果とはデータ構造を使ってタスクを実行するうえで１つ以上のセルの影響を考慮した、セルの階層効果のことである。前述のように、セル６０３の定義は１０，０００の基本素子を含む。セル６０５の定義はその場合、７０の基本素子を含む一方、セル６０７の定義は２００の基本素子を含む。
【００３１】
次に、工程５０３では、データ構造におけるセルの発生数が判定される。更に上記のように、セル６０３はデータ構造６０１において１０，０００回発生する。セル６０５はデータ構造６０１で５０回発生する一方、セル６０７はデータ構造６０１で３回しか発生しない。工程５０５では、データ構造のフラット・リソース値（この例では、データ構造６０１）が次に判定される。図示された実施例は配置図ネットリストと概略図ネットリストとの比較に関するものなので、この例におけるデータ構造のフラット・リソース値は、データ構造６０１と、セルの利用を伴わない対応データ構造とを比較するのに必要となる比較操作数に基づいて判定し得る。したがって、データ構造６０１を成分毎に比較するのに必要な比較操作総数はデータ構造６０１に含まれる基本素子数である、１００，００４，１００になる。
【００３２】
工程５０７においては、セルの階層リソース値が次に判定される。この値は、例えば、セルの各成分に操作を行い、更にデータ構造６０１におけるセルの各インスタンスに操作を行って所望のタスクを実行するのに必要な操作数を判定することによって入手し得る。したがって、図示された実施例においては、セルの階層リソース値は、セルの各成分を比較するのに必要な操作数と、データ構造６０１におけるセルの各インスタンスを比較するのに必要な操作数とを加算することによって判定される。さらに、図示された実施例におけるセルについて判定された階層リソース値は、データ構造全体にタスクを行うのに必要な操作総数に基づいているので、セルの内部と外部との両方の成分を考慮に入れている。
【００３３】
特に、工程５０７においては、特定のセルの階層リソース値は、例えば、セルの各成分に操作を実行し、次にセルにない各成分に操作を実行し、今度は集合したデータ構造中のそのセルの各インスタンスに操作を実行することによって、所望のタスクを実行するのに必要な操作数を判定することによって入手される。したがって、図示した実施例では、データ構造６０１におけるセルの階層リソース値は、その特定のセルの各成分を比較するのに必要な操作数を、その特定のセルにないデータ構造６０１の各要素を比較するのに必要な操作数とデータ構造におけるその特定のセルの各インスタンスを比較するのに必要な操作数に加算することによって判定される。
【００３４】
例えば、セル６０３を用いてデータ構造６０１に比較タスクを実行するには２４，１００の操作を必要とする。特に、セル６０５における基本素子各々を比較するには３５００の成分比較操作を必要とし、セル６０７における各基本素子を比較するには６００の成分比較操作を必要とする。単一セル６０３のみを比較するには、１０，０００の成分比較操作が必要になる。データ構造６０１における各セル６０３はその場合他のセルと直接比較し得、更に１０，０００のセル比較操作が必要となり、合わせて２４，１００の操作になる。
【００３５】
一方、セル６０５のみを用いてデータ構造６０１に比較タスクを実行するのには１００，０００，７２０の比較操作を必要とする。特に、１００，０００，０００の成分比較操作がセル６０３における基本素子各々を比較するのに必要である一方、セル６０７における基本素子各々を比較するには６００の成分比較操作を必要とする。単一セル６０５のみを比較するには７０の成分比較操作が必要になる。その場合、データ構造６０１におけるセル６０５の各発生を比較するには更に５０のセル比較操作を必要とし、合わせて１００，０００，７２０の比較操作になる。同様に、セル６０７のみを用いてデータ構造６０１に比較タスクを実行するには１００，００３，７０３の比較操作が必要になる。セル６０３における基本素子を比較するには１００，０００，０００の成分比較操作が必要になる一方、基本素子とセル６０５とを比較するには３５００の成分比較操作を必要とする。単一セル６０７における各成分を比較するには２００の成分比較操作を必要とする。セル６０７の各インスタンスはその場合、３つのセル比較操作を用いて比較され、合わせて１００，００３，７０３の比較操作になる。
【００３６】
最後に、工程５０９では、セルの階層効果を判定するよう、階層リソース値がフラット・リソース値と対比される。例えば、セルの階層効果は、セルを全く用いないでタスクを実行する代わりにセルを用いて得られる操作削減パーセント値であり得る。特に、階層効果は以下の式によって算定し得る：
階層効果値＝１００−（１００ｘ階層リソース値／フラット・リソース値）
したがって、上記の例では、セル６０３の階層効果は９９．９７６％になる。セル６０５はその場合０．００３３８％になる一方、セル６０７の階層効果は０．００３９７％のみとなる。したがって、セルの階層効果に基づいて、タスクを実行するようセル６０３のみを利用することによって時間及び処理リソースの実質的な削減を設ける。
【００３７】
しかしながら、階層リソース値とフラット・リソース値とを対比するには他の手法も用い得ることを理解すべきである。例えば、階層リソース値とフラット・リソース値との比率（又はフラット・リソース値と階層リソース値との比率）をセルの階層効果値として用い得る。代わりに、フラット・リソース値と階層リソース値との差異をセルの階層効果値として用い得る。階層リソース値とフラット・リソース値との関係を数量化する更に他の手法が、前記説明から当業者には更に分かるものである。
【００３８】
上記の本発明の実施例はデータ構造全体にタスクを実行するのに必要な操作総数に基づいてセルの階層効果を判定する一方、セルを用いることによって得られる操作数の削減のみに基づいてセルの階層効果を判定し得ることも特筆する。したがって、これらの実施例はデータ構造にタスクを実行するのに必要な、セルの外の成分に行われる操作数を考慮していない。
【００３９】
更に、本発明の種々の実施例は他の基準を用いてセルの階層効果を判定し得る。例えば、本発明の実施例のいくつかは、セルを用いてタスクを実行するのに必要な記憶容量とセルを用いずにタスクを実行するのに必要な記憶容量との対比に基づいた、セルの階層効果を判定し得る。当然、セルの階層効果を判定する他の所望の基準も更に利用し得る。
【００４０】
したがって、セルの階層効果を判定する種々の実施例はセルを用いて獲得し得る便益の数量化可能な判定を利用者に設ける。セルの階層効果は、例えば、そのｈ−セルの同等物を識別するのに用い得る。例えば、概略図データ構造におけるセルの階層効果が対応する配置図データ構造におけるセルの階層効果と突合する場合、それらのセルをｈ−セル対として比較し得る。以下に詳説するように、セルの階層効果は更に配置図データ構造を概略図データ構造と比較するのにｈ−セル対を利用するかどうかを判定するのに用い得る。好都合にも、タスクを実行するのにｈ−セル対全体を用いるかどうかを判定するのにｈ−セル対の何れかのセルの階層効果を利用し得る。
【００４１】
（タスクを実行するのに利用するセルの判定）
セルの階層効果が判定されると、該セルの階層効果は、データ構造にタスクを実行する場合に利用するのに十分高い階層効果をどのセルが有するかを選択するのに用い得る。図７はデータ構造にタスクを実行する場合に、階層データ構造中のどのセルを利用すべきかを決定するツール７０１を示すものである。特に、ツール７０１はセル階層効果ランキング・モジュール７０３及び総階層効果判定モジュール７０５を含む。以下に詳説するように、セル階層効果ランキング・モジュール７０３はタスクが実行されるデータ構造を含むデータ構造入力７０７を受ける。セル階層効果ランキング・モジュール７０３は次に入力データ構造における各セルの階層効果ランキングを判定する。以下に更に詳説するように、総階層効果判定モジュール７０５はセル階層効果ランキング・モジュール７０３によって設けられたランキングに基づいた入力データ構造の種々のセルを用いて総階層効果を判定する。セル階層効果ランキング・モジュール７０３と総階層効果判定モジュール７０５とは、データ構造を使ってタスクを実行するのに用いられる、選択セルのリスト７０９が入手されるまでデータを交換し続ける。
【００４２】
ツール７０１の動作は図８Ａ−８Ｃに表される流れ図及び図９と１０に示されるデータ構造を参照して詳説する。以下に詳説されるように、図９は複数のセル６０３−９０７を有するデータ構造を図で表すものである。さらに、これらのセルのうちの１つ、セル９０３自体は、図１０に表されるように、複数の下位セル１００１からできている。最初に、工程８０１では、セル階層効果ランキング・モジュール７０３がデータ構造９０１におけるセル群を定義する。次に、工程８０３では、セル階層効果ランキング・モジュールはデータ構造９０１における各セルの発生数を判定する。次に図９によれば、データ構造９０１はセル９０３、９０５、及び９０７を含む。特に、データ構造９０１はセル９０３の１００のインスタンスを含み、該インスタンス各々は、今度は１，０００，０００の基本素子を含み、合わせて１００，０００，０００の基本素子になる。データ構造９０１は更にセル９０５の５０のインスタンスを含み、それらの各々は７０の基本素子を含み、合わせて３５００の基本素子となり、セル９０７の３つのインスタンスは、それらの各々が２００の基本素子を含み、合わせて６００の基本素子になる。したがって、データ構造９０１における基本素子を全て比較するのに必要な成分比較操作総数は１００，００４，１００になる。
【００４３】
工程８０５では、総階層効果判定モジュール７０５はデータ構造９０１の総累積リソース値を判定する。すなわち、総階層効果判定モジュール７０５はデータ構造９０１における全てのセルを用いて所望のタスクを実行することに関係する総累積リソース値を判定する。図９に表される例では、総累積リソース値は２４２３になる。特に、単一セル１００１のみを比較するには１０００の成分比較を必要とし、その場合、セル９０３における各セル１００１は１，０００のセル比較操作を用いて比較し得、合わせて２，０００の操作になる。セル９０３の各インスタンスは、今度は更に１００のセル比較操作によって比較され、操作数は合わせて２，１００となる。単一セル９０５のみを比較するには７０の成分比較操作を必要とする。その場合、更に５０のセル比較操作がデータ構造９０１におけるセル９０５の各発生を比較するのに必要になる。単一セル９０７において各成分を比較するには２００の成分比較操作を必要とする。セル９０７の各インスタンスは次に３つのセル比較操作を用いて比較し得、操作数合計は２４２３になる。
【００４４】
次に、工程８０７においては、セル階層効果ランキング・モジュール７０３は選択セルの累積階層リソース値を判定する。処理のこの段階において、セルは選択されない。したがって、選択セルの累積階層リソース値はデータ構造９０１における基本素子全てを比較するのに必要な成分比較操作数と同一で、上記のように、１００，００４，１００になる。
【００４５】
次に、工程８０９では、総階層効果判定モジュール７０５は選択セルの階層累積リソース値を総累積リソース値と対比することによって削減値を判定する。この実施例においては、総累積リソース値は以下の式によって判定される：
削減値＝１００ｘ（（累積階層リソース値−総累積リソース値）／累積階層リソース値）。
【００４６】
したがって、初期の削減値は１００ｘ（（１００，００４，１００−２４２３）／（１００，００４，１００）＝９９．９９７５％となる。したがって、これはデータ構造における残りのセルを全て用いることによって獲得し得る更なる削減である。
【００４７】
次に、工程８１１では、総階層効果判定モジュール７０５は判定された削減値を所望の閾値と比較し、タスクを実行するデータ構造における残りの非選択セルを用いて設けられる累積削減は十分に高いかどうかを判定する。該削減値が閾値を超えない場合（すなわち、最低の削減が、データ構造における残りの非選択セルを用いることによって獲得し得ない場合）、セルを選択する処理は終結し、工程８１３にてタスクが実行される。図示された実施例においては、閾値は３０％であるので、初期の削減値は閾値を越えるのに十分高い。したがって、セルを選択する処理は、最高累積階層効果ランキングを有する非選択セルが識別される、工程８１５に続く。
【００４８】
最高累積階層効果ランキングを有する非選択セルを判定するのに、セル階層効果ランキング・モジュール７０３はデータ構造９０１における各セルの累積階層リソース値を判定し得る。未だ全くセルが選択されていないので、各セルの累積階層リソース値は各セルの絶対的階層リソース値と同一になる。したがって、セル９０３を用いてデータ構造９０１に比較タスクを実行するには１，００４，２００操作を必要とし、セル９０３には１，００４，２００の累積階層リソース値を与える。特に、３５００の比較操作が、セル９０５における基本素子各々を比較するのに必要になり、セル９０７における基本素子各々を比較するには６００の成分比較操作が必要になる。単一セル９０３のみを比較するには、１，０００，０００成分比較操作が必要になり、データ構造６０１の各セル９０３は更に他のセルと直接比較し得、更にはセル比較操作が１００のみ必要になり、合わせて１，００４，２００の操作になる。
【００４９】
セル９０５のみを用いてデータ構造９０１に比較タスクを実行するには１００，０００，７２０の比較操作を必要とする。特に、１００，０００，０００の成分比較操作がセル９０３における基本素子各々を比較するのに必要になる一方、セル９０７における基本素子の各々を比較するには６００の成分比較操作が必要になる。単一セル９０５のみを比較するには７０の成分比較が必要になる。データ構造９０１においてセル９０５の各発生を比較するには更に５０のセル比較操作がその場合必要になり、合わせて１００，０００，７２０の比較操作総数を設ける。セル９０７のみを用いてデータ構造９０１に比較タスクを実行するにはその場合１００，００３，７０３比較操作が必要になる。再びセル９０３の基本素子を比較するには１００，０００，０００の成分比較操作を必要とする一方、基本素子とセル９０５とを比較する場合には３５００の成分比較操作を必要とする。単一セル９０７における各成分を比較するには２００の成分比較操作を必要とする。セル９０７の各インスタンスはそうすると３つのセル比較操作を用いて比較され得、合わせて１００，００３，７０３の比較操作になる。
【００５０】
図１０に表されるように、セル９０３はセル１００１の１０００のインスタンスに分割し得、各々は１，０００の基本素子を含む。したがって、このセルの階層効果ランキングも考慮されなければならない。セル９０１に比較タスクを実行するようセル１００１が利用される場合、１０５，１００比較操作が必要になる。上記のように、セル９０５における基本素子各々を比較するには３５００の成分比較操作が必要になり、セル９０７における基本素子各々を比較するには６００の成分比較操作が必要になる。各セル９０３は１，０００のセル１００１を含み、データ構造９０１は１００のセル９０３を含み、合わせて１００，０００のセル１００１になる。単一セル１００１のみを比較するには、１，０００の成分比較操作が必要になり、合わせて１０５，１００の操作が必要になる。
【００５１】
したがって、セル９０３は９８．９９％の絶対的階層効果値を有する一方、セル９０５の絶対的階層効果値は０．００３３８％になる。同様に、セル９０７の絶対的階層効果値は０．０００３９７％である一方、セル１００１の絶対的階層効果値は９９．８９％になる。したがって、セル１００１はデータ構造９０１の全てのセルのうち、最高の累積（及び絶対的）階層効果ランキングを有する。したがって、工程８１７においては、セル１００１は選択セルのリストに加えられる。
【００５２】
上記の例においては、上記階層効果値は最高階層効果ランキングを有するセルを判定するのに用いたことを特筆する。しかしながら、最高階層効果ランキングを有するセルを判定するのに他の値を利用し得ることを特筆する。例えば、本発明の実施例のいくつかは、最高階層効果ランキングを有するセルは各セルの累積階層リソース値を用いて識別し得る。したがって、最低階層リソース値を有するセルは最高階層効果ランキングを有するセルとして識別される。
【００５３】
次に工程８０７に戻り、総階層効果判定モジュールは選択セル（この例においては、セル１００１）の累積階層リソース値を判定する。したがって、工程８０７を繰り返す場合、データ構造９０１の総累積リソース値は１０５，１００となる。特に、１，０００の成分比較操作が、セル１００１の単一インスタンスにおける基本素子を比較するのに必要になり、次に１００，０００のセル比較操作が、データ構造９０１におけるセル１００１の発生の全てを比較するのに必要になる。他の３５００及び６００の成分比較操作が今度はセル９０５と９０７各々にある基本素子を比較するのに必要になり、合わせて１０５，１００の操作になる。
【００５４】
次に、工程８０９を繰り返すことによって、総階層効果判定モジュール７０５は総累積リソース値を選択セルの階層累積リソース値と対比することによって削減値を判定する。この実施例においては、削減値は再び、以下の式によって判定される：
（削減値）＝１００Ｘ（（累積階層リソース値−総累積リソース値）／累積階層リソース値）。
【００５５】
したがって、セル１００１を用いる際の累積削減値は１００Ｘ（（１０５，１００−２４２３）／１０５，１００）＝９７．６９％
になる。したがって、これはセル１００１を用いることに加えてデータ構造における残りの全てのセルを用いることによって獲得し得る更なる削減である。
【００５６】
次に、工程８１１においては、この削減値は再び、３０％の閾値を超えるものと判定される。したがって、工程８１５においては、セル階層効果ランキング・モジュール７０３は最高の累積階層効果ランキングを有する非選択セルを判定する。したがって、セル９０３の累積階層リソース値は６，２００になる。特に、１，０００の成分比較操作が、セル１００１の１インスタンスにおける全ての基本素子を比較するのに必要になり、別の１０００のセル比較操作がセル９０３の単一インスタンスにおける全てのセル１００１を比較するのに必要になる。データ構造９０１においてセル９０３の全てのインスタンスを比較するには１００のセル比較操作のみが必要になり、合わせて２１００の操作になる。上記のように、セル９０５とセル９０７各々における基本素子を比較するには３５００と６００の成分比較操作が必要になり、合わせて６２００の操作になる。同様の分析を用いれば、セル９０５の累積階層リソース値は１０１，７２９になる一方、セル９０７の累積階層リソース値は１０４，７０３になる。したがって、セル９０３の累積階層効果値は９４．１％になる一方、セル９０３及び９０５の累積階層効果値は各々、３．２％及び０．３７７％になる。したがって、工程８１７が繰り返されると、セル９０３が選択される。
【００５７】
工程８０７に戻ると選択セルの累積階層リソース値は６２００になる。次に工程８０９が再び繰り返されるとセル９０３を用いる場合に得られる削減値は１００Ｘ（（６２００−２４２３）／６２００）＝６０．９１％になる。再び、この値は工程８１１において３０％の閾値よりも高いものと判定されるため、セル階層効果ランキング・モジュール７０３は工程８１５において最高累積階層効果ランキングを有する残りの非選択セルを判定する。
【００５８】
タスクを実行するのにセル９０５と９０７との何れを利用すべきかを判定する処理が再び繰り返される場合、累積リソース値は６２００になる。セル９０５の累積階層リソース値はそうすると２８２０になる一方、セル９０７の累積階層リソース値は５８０３になる。したがって、セル９０５の累積階層効果値は５４．５％になる一方、セル９０７の累積階層効果値は６．４％になり、セル９０５に最高階層効果ランキングを与える。したがって、工程８１７においては、セル９０５が選択される。工程８０７に戻ると、セル階層効果ランキング・モジュール７０３は選択セルの累積階層リソース値が２８２０であることを判定する。したがって、セル９０５の累積階層リソース値が次にデータ構造９０１の総累積リソース値と対比された場合、削減値は、１００Ｘ（（２８２０−２４２３）／２８２０）＝１４．０７％になる。
【００５９】
この値は工程８１３においては３０％の閾値を下回るものと判定されるため、更なるセルは選択されない。その代わりに、工程８１３において、所望のタスクは選択セル（この例においては、セル１００１、９０３及び９０５）を用いて実行される。
【００６０】
したがって、本発明の種々の実施例は階層データ構造におけるどのセルが、データ構造を使った所望のタスクを実行するのに最も効果的であるかを判定する手法を設けるものである。したがって、本発明の実施例は、概略図データ構造と配置図データ構造のどのｈ−セル対を、概略図データ構造と配置図データ構造とを比較するのに利用すべきかを判定するのに利用し得るものである。
【００６１】
本発明は現時の好適実施形態を含む特定例に関して説明したが、当業者には、本発明の特許請求の範囲にて記載された本発明の精神及び範囲に収まる、上記のシステム及び手法の数々の変形例及び置換があることがわかるものである。
【図面の簡単な説明】
【００６２】
【図１】回路の概略図である。
【図２】図１に表された回路に対応する配置図である。
【図３】データ構造がいかにして階層配列を有し得るかの例を表した図である。
【図４】本発明の種々の実施例を実現するのに用い得るプログラム可能なコンピュータの一実施例である。
【図５Ａ】本発明の種々の実施例による、データ構造におけるセルの階層効果を判定する方法を説明した流れ図である。
【図５Ｂ】本発明の種々の実施例による、データ構造におけるセルの階層効果を判定する方法を説明した流れ図である。
【図６】階層配列を有するデータ構造を示した図である。
【図７】配置図データ構造と概略図データ構造とを比較する場合にｈ−セル対の利用を判定するツールを示した図である。
【図８Ａ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図８Ｂ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図８Ｃ】本発明の種々の実施例によって、配置図データ構造と回路図データ構造とを比較するのに用い得るｈ−セル対の利用を判定する方法を示した図である。
【図９】階層配列を有するデータ構造を示した図である。
【図１０】階層配列を有するデータ構造を示した図である。
【符号の説明】
【００６３】
１      コネクション端点
２      コネクション端点
３      コネクション端点
４      コネクション端点
５      コネクション端点
１０１  電子回路
１０３  電界効果トランジスタ
１０５  ドレイン
１０７  ゲート
１０９  ソース
１１１  電界効果トランジスタ
１１３  ドレイン
１１５  ゲート
１１７  ソース
２０１  配置図
２０３  電界効果トランジスタ
２０５  多角形
２０７  多角形
２０９  多角形
２１１  トランジスタ
２１３  多角形
２１５  多角形
２１７  多角形
３０１  セル
３０３  セル
３０５  セル
４０１  コンピュータ
４１１  データ・バス
７０１  ツール