(57)【要約】  電子回路を製造するために幾何学的レイアウトデザインデータを処理するための方法およびシステムを提供する。本方法は、１以上のデータフォーマットファイルから幾何学的レイアウトデザインデータを抽出するステップを実行する。そして、本方法は、１以上のデータフォーマットファイルから抽出された幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離するステップを実行する。そして、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して少なくとも１つの所定の演算が実行される。
2009516876.tif 000002
【特許請求の範囲】
【請求項１】
電子回路を製造するために幾何学的レイアウトデザインデータを処理するための方法であって、
少なくとも１つの入力データフォーマットファイルから前記幾何学的レイアウトデザインデータを抽出するステップと、
前記少なくとも１つの入力データフォーマットファイルから抽出された前記幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離するステップと、
前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータの少なくとも１つのデータに対して、少なくとも１つの所定の演算を実行するステップと
を含んでなる方法。
【請求項２】
前記幾何学的レイアウトデザインデータを分離するステップは、
データベースの構造コンポーネントに前記構造データを格納し、
前記データベースの空間コンポーネントに前記空間データを格納し、
前記データベースのＲＡＷジオメトリコンポーネントに前記ＲＡＷジオメトリデータを格納する、
ことを含むものである請求項１に記載の方法。
【請求項３】
前記構造データは、階層表現、ハイブリッド型階層表現、フラット表現、およびハイブリッド型フラット表現の少なくとも１つの表現として表されるものである請求項１に記載の方法。
【請求項４】
前記階層表現、前記ハイブリッド型階層表現、および前記ハイブリッド型フラット表現の各表現はトップセルを含む第１の複数のセルを含み、該トップセルは、前記ハイブリッド型フラット表現および前記ハイブリッド型階層表現の各表現においては前記複数のセルの各セルの親であり、前記階層表現においては前記複数のセルの各セルの親または祖先である請求項３に記載の方法。
【請求項５】
前記データベースの前記ＲＡＷジオメトリコンポーネントは０個以上の幾何学図形を含み、前記階層表現におけるセルは、
前記データベースの前記ＲＡＷジオメトリコンポーネントを指し示す第１のポインタと、
０個以上の子供セルと、
各子供セルの各インスタンスのアドレスと
の少なくとも１つを含むものである請求項４に記載の方法。
【請求項６】
前記データベースの前記ＲＡＷジオメトリコンポーネントは０個以上の幾何学図形を含み、前記構造データの前記ハイブリッド型階層表現におけるセルは、
前記データベースの前記ＲＡＷジオメトリコンポーネントを指し示す第２のポインタと、
当該セルの各インスタンスのアドレスを生成するために使用される情報を含む列挙型データ構造と
を含むものである請求項４に記載の方法。
【請求項７】
前記ハイブリッド型階層表現は、前記セルの前記列挙型データ構造に対してイテレーションを実行して当該セルの各インスタンスのアドレスを生成する反復アルゴリズムを含むものである請求項６に記載の方法。
【請求項８】
前記列挙型データ構造はＤＡＧ（有向非巡回グラフ）の部分集合であるＰＤＡＧ（部分有向非巡回グラフ）であって、前記セルの該ＰＤＡＧは、当該セルの各祖先と、該ＤＡＧにおける祖先同士の各ペア間の各既存リンクと、該ＤＡＧにおける当該セルと当該セルの各親との間の各既存リンクとを含むものである請求項６に記載の方法。
【請求項９】
前記データベースの前記ＲＡＷジオメトリコンポーネントは０個以上の幾何学図形を含み、前記構造データの前記ハイブリッド型フラット表現における前記セルは前記データベースの前記ＲＡＷジオメトリコンポーネントを指し示す第３のポインタを含むものである請求項４に記載の方法。
【請求項１０】
前記ハイブリッド型フラット表現におけるトップセルはセル集合に属する各セルの各インスタンスに対応する境界ボックスに対応する情報を含み、該セル集合に属する各セルの第３のポインタは当該セルに対応する１以上の幾何学図形のアドレスを含むものである請求項９に記載の方法。
【請求項１１】
前記階層表現は、第１の所定のアルゴリズムを用いて前記ハイブリッド型階層表現へと変換されるものである請求項３に記載の方法。
【請求項１２】
前記データベースの前記ＲＡＷジオメトリコンポーネントは０個以上の幾何学図形を含み、前記構造データの前記フラット表現は前記データベースの前記ＲＡＷジオメトリコンポーネントを指し示す第４のポインタを含むトップセルを含むものである請求項３に記載の方法。
【請求項１３】
前記ハイブリッド型階層表現は、第２の所定のアルゴリズムを用いて前記ハイブリッド型フラット表現へと変換されるものである請求項３に記載の方法。
【請求項１４】
前記階層表現は、第３の所定のアルゴリズムを用いて前記ハイブリッド型フラット表現へと変換されるものである請求項３に記載の方法。
【請求項１５】
前記空間データは、空間表現の集合からの少なくとも１つの空間表現を用いて表されるものである請求項２に記載の方法。
【請求項１６】
前記ＲＡＷジオメトリデータは、複数のプリミティブな幾何学図形、座標表現方法、および複数のユーザ指定プロパティの各々を用いて表される請求項１に記載の方法。
【請求項１７】
少なくとも１つの所定の演算を実行するステップは、
ａ）（ｉ）前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータの少なくとも１つのデータに対して前記少なくとも１つの所定の演算を実行した少なくとも１つの結果と、（ｉｉ）前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータとの少なくともどちらか一方を集約し、
ｂ）少なくとも１つの出力データフォーマットファイルに前記集約された結果を格納する、
ことを含むものである請求項１に記載の方法。
【請求項１８】
レイアウト後ＥＤＡ（電子設計自動化）アプリケーションを開発するためのアプリケーションであって、
ａ）少なくとも１つの入力データフォーマットファイルから抽出された幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離するための分離モジュールと、
ｂ）前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータの少なくとも１つデータに対して各ライブラリが実行される、少なくとも１つの所定の演算に対応するライブラリ集合と
を含んでなる、レイアウト後ＥＤＡアプリケーションを開発するためのアプリケーション。
【請求項１９】
ａ）データベースの構造コンポーネントに前記構造データを格納し、
ｂ）前記データベースの空間コンポーネントに前記空間データを格納し、
ｃ）前記データベースのＲＡＷジオメトリコンポーネントに前記ＲＡＷジオメトリデータを格納する、
ためのデータベースモジュールを更に含むものである、請求項１８に記載のアプリケーション。
【請求項２０】
ａ）前記構造データの各表現ごとに、前記構造コンポーネントは第１のＡＰＩ（アプリケーション・プログラミング・インタフェース）を通じて前記空間コンポーネントおよび前記ＲＡＷジオメトリコンポーネントの各コンポーネントと通信し、
ｂ）前記空間データの各表現ごとに、前記空間コンポーネントは第２のＡＰＩを通じて前記構造コンポーネントおよび前記ＲＡＷジオメトリコンポーネントの各コンポーネントと通信し、
ｃ）前記ＲＡＷジオメトリデータの各表現ごとに、前記ＲＡＷジオメトリコンポーネントは第３のＡＰＩを通じて前記構造コンポーネントおよび前記空間コンポーネントの各コンポーネントと通信する、
ことを特徴とする、請求項１９に記載のアプリケーション。
【請求項２１】
前記レイアウト後ＥＤＡアプリケーションによってロードされたライブラリは、前記レイアウト後ＥＤＡアプリケーションが、前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータの少なくとも１つのデータに対して少なくとも１つの演算を実行できるようにするものである、請求項１８に記載のアプリケーション。
【請求項２２】
ａ）（ｉ）前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータの少なくとも１つのデータに対して前記少なくとも１つの所定の演算を実行した、少なくとも１つの結果と、（ｉｉ）前記構造データ、前記空間データ、および前記ＲＡＷジオメトリデータとの少なくともいずれか一方を集約するための集約モジュールと、
ｂ）少なくとも１つの入力データフォーマットファイルから前記幾何学的レイアウトデザインデータを抽出するためのリーダと、
ｃ）少なくとも１つの出力データフォーマットファイルに前記集約された結果を書き込むためのライタと
を更に含むものである、請求項１８に記載のアプリケーション。
【請求項２３】
前記ライブラリ集合に属する各ライブラリは、事前にコンパイルされたオブジェクトコードライブラリである、請求項１８に記載のアプリケーション。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本願は２００５年７月２１日に出願されたインド国特許出願番号第９７５／ＣＨＥ／２００５号「Methodology for post-layout EDA application development toolkit」と関連のある完全な特許出願である。
【０００２】
［技術分野］
本発明は電子設計自動化（ＥＤＡ：Electronic Design Automation）技術に関する。より具体的には、本発明はレイアウト後ＥＤＡアプリケーションを開発するための技術に関する。
【背景技術】
【０００３】
電子回路の設計製造プロセスは、大きく分けて２つの段階、例えばレイアウト前設計段階とレイアウト後設計段階とに分けることができる。電子回路の設計製造プロセスの例としては、限定はされないが、ＩＣ（Integrated Circuits）、ＰＣＢ（Printed circuit Boards）、ＭＥＭＳ（Micro Electro Mechanical Systems）、ＭＣＭ（Multi-Chip Modules）などの設計製造プロセスが挙げられる。レイアウト前設計段階では、回路デザインは、物理的レイアウトデータ（physical layout data）へと変換される。物理的レイアウトデータは、電子回路の設計に使用される、電子回路上の回路素子の物理的な位置の詳細を含む。その後、レイアウト後設計段階では、物理的レイアウトデータは、電子回路の製造に使用される幾何学的レイアウトデザインデータ（geometric layout design data）へと変換される。この幾何学的レイアウトデザインデータは多数のデータフォーマットファイル（data-format files）に作成保存される。入出力データフォーマットファイルの例としては、限定はされないが、ＧＤＳＩＩ（登録商標）（Graphic Data System-II）データフォーマットファイル、ＯＡＳＩＳ（Open Artwork System Interchange Standard）、ＭＥＢＥＳ（登録商標）、ＪＥＯＬ（登録商標）、ＶＳＢ−１１／１２（登録商標）、ＯＡＳＩＳ−ＶＳＢ（登録商標）、Ｇｅｒｂｅｒ（登録商標）、ＬＥＦ（登録商標）／ＤＥＦ（登録商標）（Library Exchange Format/ Design Exchange Format）、そのほか幾何学的レイアウトデザインデータを記述する専用のデータフォーマットファイルが挙げられる。
【０００４】
レイアウト後設計段階では、大きな幾何学的レイアウトデザインデータが処理される。加えて、レイアウト後設計段階は電子回路の製造前の最後の段階であることから、従って幾何学的レイアウトデザインデータに対して正確で効率的な演算が実行されることが不可欠である。レイアウト後ＥＤＡアプリケーションは幾何学的レイアウトデザインデータを処理するために使用される。レイアウト後ＥＤＡアプリケーションは幾何学的レイアウトデザインデータを処理するための複数のコンポーネントを含む。複数のコンポーネントとしては、限定はされないが、データ構造、演算、外部インタフェースなどが挙げられる。レイアウト後ＥＤＡアプリケーションは、データフォーマットファイルとターゲットアプリケーション利用に基づいて、レイアウト後ＥＤＡアプリケーションの各コンポーネントごとに新しいコードを書くことより、カスタム設計することができる。ターゲットアプリケーション利用の例としては、限定はされないが、ＭＤＰ（Mask Data Preparation）、ＤＲＣ（Design Rule Checker）、ＯＰＣ（Optical Proximity Collection）、ＲＥＴ（Resolution Enhancement Techniques）、ＣＡＡ（Critical Area Analysis）、ＤＭＦ（Dummy Metal Filling）、ＭＩ（Mask Inspection）、ＭＲＣ（Mask/Manufacturing Rule Checker）、ＳＤ（Silicon Debugging）、ＣＡＤ（Compute Aided Design）Navigation、ＬＶ（Layout Viewers）、ＬＡ（Layout Analysis）およびＦＡ（Failure Analysis）などが挙げられる。このおかげでデータフォーマットファイルとレイアウト後ＥＤＡアプリケーションのターゲットアプリケーションに対してレイアウト後ＥＤＡアプリケーションの効率の高いパフォーマンスが可能となる。加えて、レイアウト後ＥＤＡアプリケーションは既存のレイアウト後ＥＤＡアプリケーションの１以上のコンポーネントを使用して開発することができる。このおかげで努力達成安定度およびパフォーマンスの両面で低減したコストで安定したレイアウト後ＥＤＡアプリケーションの開発が可能となる。しかしながら、幾何学的レイアウトデザインデータを高いパフォーマンスで既存のレイアウト後ＥＤＡアプリケーションの１以上のコンポーネントを使用することなく効率的に処理することができる安定したレイアウト後ＥＤＡアプリケーションを開発するのには長い期間が必要である。
【０００５】
一部のデザインデータベース、例えばＯｐｅｎＡｃｃｅｓｓ（登録商標）およびＭｉｌｋｙＷａｙ（登録商標）は、ＡＰＩ（Application Programming Interfaces）を通じて、複数のレイアウト後ＥＤＡアプリケーションとの相互運用が可能である。これらのデザインデータベースのおかげで、レイアウト後ＥＤＡアプリケーションの開発者達は、デザインデータベースを１以上のカスタム設計レイアウト後ＥＤＡアプリケーションに組み込むためのＡＰＩを書くことができる。
【０００６】
さらに、デザインデータベースとデータフォーマットファイルは幾何学的レイアウトデザインデータをフラット表現（flat representation）と階層表現（hierarchical representation）の一方または両方で格納する。フラット表現は幾何学的レイアウトデザインデータの各幾何学図形を列挙する。これは演算を実行するための大きな実行時間メモリと格納するためのオンディスクメモリを必要とする。階層表現は複数のセル（cell）を含む。階層表現におけるセルはゼロ個以上のセルとゼロ個以上の幾何学図形へのリファレンスを含む。階層表現を利用することで、幾何学的レイアウトデザインデータを格納するのに必要なメモリ空間が減少する。しかしながら、階層表現において一部の演算、限定はされないが例えば空間演算を実行することは、実行が複雑であり、計算コストが掛かる可能性がある。
【０００７】
そのため、複数のデータフォーマットファイルとインタフェースをとる（読み出し／書き込み）ことができる安定的であり効率の高いレイアウト後ＥＤＡアプリケーション開発用プラットフォーム／ツールキットが必要とされている。さらに、異なるターゲットアプリケーションが効率的かつ迅速に開発できるように、メモリをあまり必要とせず様々な演算（限定はされないが、例えば、空間演算）を効率的に実行するのに適した幾何学的レイアウトデザインデータのデータ表現が必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の１つの目標は、レイアウト後ＥＤＡアプリケーションを開発するための方法およびシステムを提供することにある。
【０００９】
本発明のもう１つの目標は、幾何学的レイアウトデザインデータを処理するための方法およびシステムを提供することにある。
【００１０】
本発明の更にもう１つの目標は、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに幾何学的レイアウトデザインデータを分離することにある。
【００１１】
本発明の更にもう１つの目標は、より少ないメモリ空間を使用するとともに効率の高い演算性能を可能とする構造データを表現するための表現方法を実現する、方法およびシステムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明は、上記目標を達成するため、電子回路を製造するために幾何学的レイアウトデザインデータを処理するための方法およびシステムを提供する。本方法は、１以上のデータフォーマットファイルから幾何学的レイアウトデザインデータを抽出するステップを実行する。本方法は、１以上のデータフォーマットファイルから抽出された幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離するステップを更に実行する。その後、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して、１以上の所定の演算が実行される。
【００１３】
以下、本発明の好ましい実施形態による、レイアウト後ＥＤＡアプリケーションを開発するための方法およびシステムを、添付図面を参照して詳細に説明する。これらの説明と添付図面から、当業者であれば、本発明の方法およびシステムが上記の課題を解決し、いくつもの利点を実現することは容易に理解できるであろう。なお、添付図面全体を通して同一または類似の構成要素には同一の参照符号が付されている。
【発明を実施するための最良の形態】
【００１４】
本発明の実施形態を詳しく説明する前に、これらの実施形態が、主にレイアウト後ＥＤＡアプリケーションを開発するための方法ステップとシステムコンポーネントの組み合わせから成ることに気付くべきである。そのため、システムコンポーネントおよび方法ステップは、添付図面において慣用記号を使って適所に表示されており、そこには本明細書の説明の恩恵に浴した当業者にとって非常に明らかな細かな部分によって実施形態の本開示の妨げとならぬよう、本発明の実施形態を理解する上で関係のある部分のみが詳細に描かれている。従って、説明を簡単かつ明確にするために、商業的に実現可能な形態において有用または必要な一般的なよく理解された構成要素はこれがあるために本発明の様々な実施形態を示す上で障害となる場合には、それらを省略して見やすくするために描かれないことがあることが理解されるであろう。
【００１５】
第１および第２やトップおよびボトムなどの相対的な用語は、ある１つのエンティティもしくはアクションを別のエンティティもしくはアクションと区別するためだけに、必ずしもそれらのエンティティもしくはアクションの間の実際の相互関係もしくは順序を何ら要求もしくは示唆せずに、使用されることがある。“〜を具備する（comprise）”、“〜を具備している（comprising）”、“〜を有する（have）”、“〜を有していている（having）”、“〜を（要素として）含む（include）”、“〜を（要素として）含んでいる（including）”、“〜を包含する（contain）”、“〜を包含している（containing）”およびそれらの変形表現は、他の要素の存在を排除しない非排他的な包含関係をカバーすることを意図して用いられる。例えば、明示的に列挙された構成要素を具備する、有する、含む、包含する方法（プロセスまたはメソッド）、物品、装置もしくはシステムは、明示的に列挙されていない他の構成要素あるいは当該方法、物品、装置もしくはシステムに特有な他の構成要素も含みうる。“ある（不定冠詞ａ）〜を具備する”、“ある（ａ）〜を有する”、“ある（ａ）〜を含む”、“ある（ａ）〜を包含する”といった表現の目的語として取り扱われた構成要素は、その構成要素を具備する、有する、含む、または包含する当該方法、物品、装置もしくはシステムに更なる制約なしにその構成要素と同一の追加要素が存在することを排除しない。“ある（a or an）〜”という表現は特に明示的な断りがなければ１以上（の要素）を意味する。ある特定の方法により“構成された（configured）”装置（device）または構造（structure）は、少なくともその方法により構成されるが、列挙されていない様々な方法により構成されることもある。
【００１６】
本発明の様々な実施形態は、レイアウト後ＥＤＡアプリケーション（post-layout EDA applications）を開発するための方法およびシステムを提供する。本方法においてはまず１以上の入力データフォーマットファイル（input data-format files）から幾何学的レイアウトデザインデータ（geometrical layout design data）が抽出される。その後、幾何学的レイアウトデザインデータは、構造データ（structural data）、空間データ（spatial data）、およびＲＡＷジオメトリデータ（raw-geometry data）の１以上のデータに分離される。そして、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して、１以上の所定の演算が実行される。１以上の所定の演算としては、限定はされないがブール演算（Boolean operations）、例えば、ＡＮＤ、ＯＲ、ＸＯＲ、ＳＵＢＴＲＡＣＴ、およびＮＯＴが挙げられる。その後、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行された結果は、１以上の出力データフォーマットファイル（output data-format files）に格納することができる。
【００１７】
図１は、本発明が機能する環境１００を例示するブロック図である。環境１００は、レイアウト後ＥＤＡアプリケーション１０２、入力データフォーマットファイル１０４、および入力データフォーマットファイル１０６を含む。当業者にとっては、環境１００が３以上の入力データフォーマットファイルを含みうることは明らかであろう。環境１００は入力データフォーマットファイル１０４と入力データフォーマットファイル１０６との一方または両方と通信して幾何学的レイアウトデザインデータを抽出する。その後、レイアウト後ＥＤＡアプリケーション１０２は、入力データフォーマットファイル１０４と入力データフォーマットファイル１０６との一方または両方から抽出された幾何学的レイアウトデザインデータに対して１以上の所定の演算を実行し、電子回路を製造するのに適したその電子回路のレイアウトデザインを生成する。構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行された結果は、出力データフォーマットファイル１０８および出力データフォーマットファイル１１０の一方または両方に格納することができる。当業者にとっては、環境１００が３以上の出力データフォーマットファイルを含みうることは明らかであろう。
【００１８】
図２は、本発明の実施の一形態による、幾何学的レイアウトデザインデータを処理するための方法のフローチャートである。ステップ２０２において、１以上の入力データフォーマットファイルから幾何学的レイアウトデザインデータが抽出される。その後、ステップ２０４において、幾何学的レイアウトデザインデータは、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離される。
【００１９】
幾何学的レイアウトデザインデータを分離した後、構造データは、データベースの構造コンポーネント（structural component）に格納される。空間データは、データベースの空間コンポーネント（spatial component）に格納される。ＲＡＷジオメトリデータは、データベースのＲＡＷジオメトリコンポーネント（raw-geometry component）に格納される。これについては、図３に関連して更に説明される。
【００２０】
構造データは、階層表現（hierarchical representation）、ハイブリッド型階層表現（hybrid-hierarchical representation）、ハブリッド型フラット表現（hybrid-flat representation）の１以上の表現として表される。階層表現、ハイブリッド型階層表現、およびハブリッド型フラット表現の各表現は複数のセルから構成される。複数のセルはトップセル（top cell）を含む。ハイブリッド型階層表現およびハブリッド型フラット表現の各表現において、トップセルは、複数のセルにおける各セルの親（parent）である。しかしながら、階層表現では、トップセルは、複数のセルにおける各セルの親（parent）または（祖父母以上の）先祖（ancestor）である。本発明の実施の一形態において、複数のセルは、トップのダミーセルを追加的に含みうる。トップのダミーセルは、それに対応する幾何学的図形（geometrical figures）を含まない。さらに、トップのダミーセルは、トップセルの１つのインスタンス（instance）のアドレスを含む。この場合、階層表現、ハイブリッド型階層表現、およびハブリッド型フラット表現の１つの表現において、トップセルは、トップのダミーセルの子供セルでありうる。
【００２１】
構造データの階層表現におけるセル（cell）は、データベースのＲＡＷジオメトリデータベースコンポーネントを指し示す第１のポインタ（pointer）を含む。この第１のポインタは、ＲＡＷジオメトリコンポーネントへのリンクまたはリファレンスでありうる。データベースのＲＡＷジオメトリコンポーネントは、０個以上の幾何学図形（geometric figures）を含む。第１のポインタは、データベースのＲＡＷジオメトリコンポーネントに格納された当該セルに対応する幾何学図形のアドレスを含む。そのため、第１のポインタは、当該セルに対応する幾何学図形にアクセスするために使用される。当該セルは、０個以上の子供セルを更に含む。加えて、当該セルは、各子供セルの各インスタンスのアドレスを含みうる。各インスタンスのアドレスは、当該セルから各子供セルの各インスタンスまで縦走するために利用される。本発明の実施の一形態によれば、繰り返しパタンを有する各子供セルのインスタンスのアドレスは、アドレスの１次元アレイまたは２次元アレイとして格納することができる。本発明の別の実施形態では、各子供セルのインスタンスのアドレスは、当該セルにアドレスリストとして格納することができる。１以上のセル同士の間の階層関係は、有向非巡回グラフ（ＤＡＧ：Directed Acyclic Graph）データ構造によって表現することができる。
【００２２】
構造データの階層表現は、第１の所定のアルゴリズムを用いて構造データのハイブリッド型階層表現へと変換される。ハイブリッド型階層表現におけるセルは、データベースのＲＡＷジオメトリコンポーネントを指し示す第２のポインタを含む。第２のポインタは、ＲＡＷジオメトリコンポーネントの中の当該セルに対応する０個以上の幾何学図形のアドレスを含む。当該セルは、列挙型データ構造（enumeration data structure）を更に含む。列挙型データ構造は、トップセルにおける当該セルの各インスタンスのアドレスを生成するために使用される情報を含む。本発明の実施の一形態において、セルの列挙型データ構造は、ＰＤＡＧ（Partial DAG）である。セルのＰＤＡＧは、ＤＡＧの部分集合であり、当該セルの各先祖、ＤＡＧにおける先祖同士の各ペアを結ぶ各既存リンク、およびＤＡＧにおける当該セルと当該セルの親との間を結ぶ各既存リンクを含む。これについては、図５に関連して更に説明される。本発明の別の実施形態では、列挙型データ構造は、トップセルに関する当該セルの各インスタンスのアドレスのリストであり、ＬＩＳＴデータ構造として実装される。
【００２３】
ハイブリッド型階層表現は、反復アルゴリズム（iterator algorithm）を更に含む。反復アルゴリズムは、セルの列挙型データ構造に対してイテレーション（iteration）を実行し、当該セルの各インスタンスのアドレスを生成する。反復アルゴリムは、列挙型データ構造の表現に依存する。例えば、セルに対応する列挙型データ構造が当該セルの各インスタンスのアドレスのリストをＬＩＳＴデータ構造で格納する場合、対応する反復アルゴリズムは、ＬＩＳＴデータ構造を順次に縦走して当該セルの各インスタンスのアドレスを生成することができる。同様に、別の例では、セルに対応する列挙型データ構造がＰＤＡＧデータ構造を通じて当該セルの各インスタンスのアドレスを格納する場合、対応する反復アルゴリズムは、ＰＤＡＧデータ構造を階層的に縦走して当該セルの各インスタンスのアドレスを生成する。
【００２４】
構造データの階層表現は、第２の所定のアルゴリズムを用いてハイブリッド型フラット表現（hybrid-flat representation）へと変換することができる。本発明の実施の一形態において、ハイブリッド型階層表現は、第３の所定のアルゴリムを用いてハイブリッド型フラット表現へと変換することができる。ハイブリッド型フラット表現におけるセルは、データベースのＲＡＷジオメトリコンポーネントを指し示す第３のポインタを含む。第３のポインタは、ＲＡＷジオメトリコンポーネントの中の当該セルに対応する０個以上の幾何学図形のアドレスを含む。ハイブリッド型フラット表現におけるトップセルは、セル集合に属する各セルの各インスタンスに対応する境界ボックス（bounding box）に対応する情報を含む。前記セル集合に属する各セルの第３のポインタは、ＲＡＷジオメトリコンポーネントの中の当該セルに対応する１以上の幾何学図形のアドレスを含む。
【００２５】
セルのインスタンスに対応する境界ボックスは、当該セルに対応する各幾何学図形を囲い込む最小矩形である。当該セルのインスタンスの境界ボックスは、トップセルの中でその境界ボックスの対角線の両端点の座標によって表すことができる。境界ボックス内の各幾何学図形の空間情報は、データベースの空間コンポーネントの中に、対角線の端点の座標からの相対座標で格納される。そのため、対角線の端点の座標は、当該セルのインスタンスに対応する各幾何学図形の空間情報を決定するために使用されることがある。これについては、図６に関連して更に説明される。
【００２６】
ハイブリッド型フラット表現は、第４の所定のアルゴリズムを用いて構造データのフラット表現へと変換することができる。構造データのフラット表現はトップセルを含む。トップセルは、データベースのＲＡＷジオメトリコンポーネントを指し示す第４のポインタを含む。第４のポインタは、データベースのＲＡＷジオメトリコンポーネントの中の各幾何学図形のアドレスを含む。本発明の実施の一形態において、階層表現とハイブリッド型階層表現の各表現は、構造データのフラット表現に直接変換することができる。
【００２７】
空間データは、セル内の各幾何学図形の空間情報を格納する。空間データは、空間表現の集合からの１以上の空間表現を用いて表される。空間表現の集合は、限定はされないが、Ｘ／Ｙソート済みエッジ表現（x/y sorted edge representation）、ボロノイ図（Voronoi diagrams）、四分木（Quad trees）および八分木（Oct trees）を含みうる。これについては、図７に関連して更に説明される。さらに、ＲＡＷジオメトリデータは、幾何学的レイアウトデザインで使用される幾何学図形を格納する。ＲＡＷジオメトリデータは、複数の幾何学図形、座標表現方法、および複数のユーザ指定プロパティの各々を用いて表される。複数の幾何学図形としては、限定はされないが、正方形（squares）、長方形（rectangles）、三角形（triangles）、マンハッタン型多角形（Manhattan polygon）、任意角多角形（any-angle polygons）、アイランド（islands）、および台形（trapezoids）などが挙げられる。複数の幾何学図形の座標は、データタイプからのデータタイプの１つの集合を用いて表すことができる。データタイプとしては、限定はされないが、short、integer、long、およびdoubleが挙げられる。ＲＡＷジオメトリデータの表現にユーザ指定データを含めるために複数のユーザ指定プロパティが幾何学図形に加えられることがある。複数のユーザ指定プロパティの例としては、限定はされないが、色、レイヤ、ネット名、および電気特性が挙げられる。これについては、図７に関連して更に詳しく説明される。
【００２８】
その後、ステップ２０６において、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行される。所定の演算の例としては、限定はされないが、ブール演算（例えば、ＡＮＤ、ＯＲ、ＸＯＲ、ＳＵＢＴＲＡＣＴ、およびＮＯＴ）、幾何学的レイアウトデザイン上のウィンドウクエリー（window query）、および幾何学的レイアウトデザイン上の近傍クエリー（neighborhood query）などが挙げられる。分離されたデータは、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して実行される演算に基づいて表される。例えば、構造データは、セル単位演算（cell-wise operations）にハイブリッド型階層表現を用いて表される。同様に、空間データは、ラインスウィープ演算（line sweep operations）にＸ／Ｙソート済みエッジ表現を用いて表される。代わりに、空間データは、近傍クエリー演算にボロノイ図表現を用いて表される。ＲＡＷジオメトリデータは、ブール演算に台形表現を用いて表される。代わりに、ＲＡＷジオメトリデータは、サイジング演算（sizing operations）にアイランド表現を用いて表される。構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行された後、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行された１以上の結果が集約結果を生成するために集約される。集約結果は、次に１以上の出力データフォーマットファイルに格納されることがある。これについては、図３を参照して更に説明される。
【００２９】
図３は、本発明の実施の一形態による、データの流れを示すフロー図である。ステップ３０２において、１以上の入力ファイルから幾何学的レイアウトデザインデータが抽出される。これについては、図２との関連で詳しく説明されている。その後、ステップ３０４において、幾何学的レイアウトデザインデータは、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離される。これについては、図２との関連で詳しく説明されている。
【００３０】
幾何学的レイアウトデザインデータを分離した後、ステップ３０６において、構造データはデータベースの構造コンポーネントに格納される。構造データは、階層表現、ハイブリッド型階層表現、フラット表現およびハイブリッド型フラット表現の１以上の表現を用いて格納される。これについては、図２との関連で詳しく説明されている。本発明の実施の一形態において、構造データは、構造データベースに格納される。ステップ３０８において、空間データは、データベースの空間コンポーネントに格納される。空間データは、Ｘ／Ｙソート済みエッジ表現（X/Y sorted edge representation）、ボロノイ図（Voronoi diagrams）、四分木（Quad trees）および八分木（Oct trees）の１以上の表現を用いて格納される。当業者であれば、本発明は、空間データを格納するためのデータ構造の上記列挙された例に限定されないことは理解されよう。本発明の実施の一形態において、空間データは空間データベースに格納される。ステップ３１０において、ＲＡＷジオメトリデータは、データベースのＲＡＷジオメトリコンポーネントに格納される。ＲＡＷジオメトリデータは、複数の幾何学図形、座標表現方法、および複数のユーザ指定プロパティの１以上を用いて格納される。これについては、図２との関連で説明されている。本発明の実施の一形態において、ＲＡＷジオメトリデータは、ＲＡＷジオメトリデータベースに格納される。
【００３１】
そして、ステップ３１２において、１以上の所定の演算が、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して実行される。これについては、図２との関連で詳しく説明されている。ステップ３１４において、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算が実行された１以上の結果が集約結果を生成するために集約される。構造データ、空間データ、およびＲＡＷジオメトリデータは集約結果を生成するために集約することができる。その後、ステップ３１６において、集約結果は、１以上の出力データフォーマットファイルに格納される。
【００３２】
図４は、複数のセルを含む構造データの階層表現４００を示すブロック図である。複数のセルは、セル４０２、セル４０４、セル４０６、およびセル４０８を含む。セル４０２はトップセルである。そのため、セル４０２は、セル４０４の親（parent）であり、セル４０６とセル４０８のそれぞれの先祖（ancestor）である。セル４０２は、インスタンス（instance）を有する。セル４０２のインスタンスは、セル４０４の第１のインスタンスのアドレスと、セル４０４の第２のインスタンスのアドレスを含む。加えて、セル４０２のインスタンスは、ＲＡＷジオメトリコンポーネントの中の、セル４０２に対応するゼロ個以上の幾何学図形のアドレスを有するポインタを含む。さらに、セル４０４は、セル４０６とセル４０８の各セルの親である。そのため、セル４０４の各インスタンスは、セル４０６の２つのインスタンスのアドレスと、セル４０８の１つのインスタンスのアドレスを含む。セル４０４の第１のインスタンスは、セル４０６の第１のインスタンスと、セル４０６の第２のインスタンスと、セル４０８の第１のインスタンスの親である。そのため、セル４０４の第１のインスタンスは、セル４０６の第１のインスタンスのアドレスと、セル４０６の第２のインスタンスのアドレスと、セル４０８の第１のインスタンスのアドレスを含む。さらに、セル４０４の第２のインスタンスは、セル４０６の第３のインスタンスと、セル４０６の第４のインスタンスと、セル４０８の第２のインスタンスの親である。そのため、セル４０４の第２のインスタンスは、セル４０６の第３のインスタンスのアドレスと、セル４０６の第４のインスタンスのアドレスと、セル４０８の第２のインスタンスのアドレスを含む。加えて、セル４０４の各インスタンスは、ＲＡＷジオメトリコンポーネントの中の、セル４０４に対応するゼロ個以上の幾何学図形を指し示すポインタを含む。
【００３３】
さらに、セル４０６の各インスタンスは、ＲＡＷジオメトリコンポーネントに格納されたセル４０６に対応するゼロ個以上の幾何学図形を指し示すポインタを含む。加えて、セル４０８の各インスタンスは、ＲＡＷジオメトリコンポーネントの中の、セル４０８に対応するゼロ個以上の幾何学図形を指し示すポインタを含む。
【００３４】
図５は、本発明の実施の一形態として、複数のセルと、セル５０４の列挙型データ構造５０２と、セル５０８の列挙型データ構造５０６と、セル５１２の列挙型データ構造５１０とを含むハイブリッド型階層表現５００を示すブロック図である。ハイブリッド型階層表現５００は、第１の所定のアルゴリズムを用いて階層表現４００から生成される。ハイブリッド型階層表現５００における複数のセルは、セル４０２に対応するセル５１４と、セル４０４に対応するセル５０４と、セル４０６に対応するセル５０８と、セル４０８に対応するセル５１２とを含む。列挙型データ構造５０２はセル５０４のＰＤＡＧを表し、列挙型データ構造５０６はセル５０８のＰＤＡＧを表し、列挙型データ構造５１０はセル５１２のＰＤＡＧを表す。ハイブリッド型階層表現５００において、セル５１４はトップセルである。セル５１４は、トップダミーセル（top dummy cell）の子供でありうる。トップダミーセルは、それに対応する幾何学図形を含まない。さらに、トップダミーセルは、セル５１４の１つのインスタンスのアドレスを含む。そのため、セル５１４は、セル５０４、セル５０８、およびセル５１２のそれぞれのセルの親である。幾何学的レイアウトデザインにおけるセル５１４の原点の縦座標は１００であり、セル５１４の原点の横座標は１００である。そのため、セル５１４の原点の座標は幾何学的レイアウトデザインにおいて（１００，１００）と表される。さらに、セル５１４は、セル５０４の２つのインスタンスを有する。セル５０４の第１のインスタンスの原点の絶対座標は（１５０，１５０）であり、セル５０４の第２のインスタンスの原点の絶対座標は（１７０，１７０）である。
【００３５】
セル５０４は、ハイブリッド型階層表現５００において列挙型データ構造５０２を更に含む。列挙型データ構造５０２は、リスト５１６とリスト５１８を含む。リスト５１６は、セル５１４の原点（１００，１００）を含む。さらに、リスト５１８は、セル５０４の各インスタンスの原点をセル５１４に関する相対座標で含む。従って、リスト５１８は、セル５０４の第１のインスタンスの原点を（５０，５０）として含み、セル５０４の第２のインスタンスの原点を（７０，７０）として含む。これらは、セル５１４の原点に関する相対座標である。
【００３６】
さらに、セル５０４の第１のインスタンスとセル５０４の第２のインスタンスの各インスタンスは、セル５０８の２つのインスタンスとセル５１２の１つのインスタンスを含む。そのため、セル５０４の第１のインスタンスとセル５０４の第２のインスタンスの各インスタンスは、セル５０８の第１のインスタンスとセル５０８の第２のインスタンスを含む。セル５０４の第１のインスタンスにおけるセル５０８の第１のインスタンスの原点の絶対座標は（１６０，１６０）であり、セル５０４の第１のインスタンスにおけるセル５０８の第２のインスタンスの原点の絶対座標は（１７０，１７０）である。さらに、セル５０４の第２のインスタンスにおけるセル５０８の第１のインスタンスの原点の絶対座標は（１８０，１８０）であり、セル５０４の第２のインスタンスにおけるセル５０８の第２のインスタンスの原点の絶対座標は（１９０，１９０）である。
【００３７】
セル５０８は、ハイブリッド型階層表現５００において列挙型データ構造５０６を更に含む。列挙型データ構造５０６は、リスト５２０とリスト５２２とリスト５２４を含む。リスト５２０は、セル５１４の原点（１００，１００）を含む。さらに、リスト５２２は、セル５０４の各インスタンスの原点をセル５１４に関する相対座標で含む。そのため、リスト５２２は、セル５０４の第１のインスタンスの原点を（５０，５０）として含み、セル５０４の第２のインスタンスの原点を（７０，７０）として含む。さらに、リスト５２４はセル５０８の第１のインスタンスの原点とセル５０８の第２のインスタンスの原点をセル５０４に関する相対座標で含む。そのため、リスト５２４は、セル５０８の第１のインスタンスの原点を（１０，１０）として含み、セル５０８の第２のインスタンスの原点を（２０，２０）として含む。
【００３８】
さらに、セル５０４の第１のインスタンスとセル５０４の第２のインスタンスは、それぞれセル５１２の１つのインスタンスを含む。セル５０４の第１のインスタンスにおけるセル５１２のインスタンスの原点の絶対座標は（１９５，１９５）であり、セル５０４の第２のインスタンスにおけるセル５１２のインスタンスの原点の絶対座標は（２１５，２１５）である。
【００３９】
セル５１２は、ハイブリッド型階層表現５００において列挙型データ構造５１０を更に含む。列挙型データ構造５１０は、リスト５２６とリスト５２８とリスト５３０を含む。リスト５２６は、セル５１４の原点（１００，１００）を含む。さらに、リスト５２８は、セル５０４の各インスタンスの原点をセル５１４に関する相対座標で含む。そのため、リスト５２８は、セル５０４の第１のインスタンスの原点を（５０，５０）として含み、セル５０４の第２のインスタンスの原点を（７０，７０）として含む。さらに、リスト５３０は、セル５１２のインスタンスの原点をセル５０４に関する相対座標で含む。そのため、リスト５３０は、セル５１２のインスタンスの原点を（４５，４５）として含む。
【００４０】
例示的な本実施形態において、ハイブリッド型階層表現４００上でセル単位の演算（cell-wise operation）が実行される。セル単位の演算をセル５１２で実行しなければならない場合、反復アルゴリズムは、列挙型データ構造５１０に作用し、リスト５２６、リスト５２８およびリスト５３０を用いてセル５１２のインスタンスの原点の絶対座標を計算する。セル５０４の第１のインスタンスにおけるセル５１２のインスタンスの場合、反復アルゴリズムは、リスト５２６に格納されたセル５１４のインスタンスの原点（１００，１００）と、リスト５２８に格納されたセル５０４の第１のインスタンスの原点（５０，５０）と、リスト５３０に格納されたセル５１２のインスタンスの原点（４５，４５）とを加えて、セル５０４の第１のインスタンスにおけるセル５１２のインスタンスの絶対座標（１９５，１９５）を生成する。同様に、セル５０４の第２のインスタンスにおけるセル５１２のインスタンスの場合、反復アルゴリズムは、リスト５２６に格納されたセル５１４のインスタンスの原点（１００，１００）と、リスト５２８に格納されたセル５０４の第２のインスタンスの原点（７０，７０）と、リスト５３０に格納されたセル５１２のインスタンスの原点（４５，４５）とを加えて、セル５０４の第２のインスタンスにおけるセル５１２のインスタンスの絶対座標（２１５，２１５）を生成する。
【００４１】
図６は、本発明の例示的な実施の一形態による、構造データのハイブリッド型フラット表現（hybrid-flat representation）における第１のセルに対応する境界ボックス（bounding box）６００のブロック図である。第１のセルはトップセルである。さらに、第１のセルは第２のセルの２つのインスタンス、幾何学図形６０２と幾何学図形６０４の親である。そのため、境界ボックス６００は、第２のセルの第１のインスタンスに対応する境界ボックス６０６と、第２のセルの第２のインスタンスに対応する境界ボックス６０８と、幾何学図形６０２と、幾何学図形６０４を含む。
【００４２】
ハイブリッド型フラット表現において、セルのインスタンスの境界ボックスは、トップセルにおいて境界ボックスの対角線の両端点の座標で表される。従って、境界ボックス６００はトップセルに対応する。境界ボックスは、トップセルにおいてポイント６１０の絶対座標（１１０，１１０）とポイント６１２の絶対座標（１３５，１３５）として表される。同様に、境界ボックス６０６は、トップセルにおいてポイント６１４の絶対座標（１１１，１１１）とポイント６１６の絶対座標（１２０，１２０）として表される。加えて、境界ボックス６０８は、トップセルにおいてポイント６１８の絶対座標（１２１，１２１）とポイント６２０の絶対座標（１３０，１３０）として表される。さらに、境界ボックス内の各幾何学図形の空間情報は、データベースの空間コンポーネントの中に境界ボックスの対角線の端点の座標に関する相対座標で格納される。そのため、幾何学図形６０２と幾何学図形６０４の空間情報は、データベースの空間コンポーネントの中にポイント６１０とポイント６１２に関する相対座標で格納される。ポイント６２２の絶対座標は（１１０，１３１）として表され、これは境界ボックス６００に関する相対座標（０，２１）として格納される。同様に、絶対座標（１２９，１１０）として表されるポイント６２４は、境界ボックス６００に関する相対座標（１９，０）として格納される。
【００４３】
例示的な本実施形態では、幾何学的レイアウトデザインデータに対してウィンドウクエリー（window query operation）が実行される。ウィンドウクエリーのクエリーウィンドウ（query window）６２６が幾何学図形６０２と重なると、ポイント６１０の絶対座標とポイント６２２相対座標を加えることによってポイント６２２が読み出される。その結果、ポイント６２２は絶対座標（１１０，１３１）として読み出される。
【００４４】
図７は、本発明の実施の一形態による、レイアウト後ＥＤＡアプリケーションを開発するためのアプリケーション７００を示すブロック図である。アプリケーション７００は、分離モジュール（segregating module）７０２と、ライブラリセット（ライブラリ集合）７０４を含む。分離モジュール７０２は、リーダ（reader）７０６と通信する。リーダ７０６は、１以上の入力データフォーマットファイルから幾何学的レイアウトデザインデータを抽出する。その後、分離モジュール７０２は、１以上の入力データフォーマットファイルから抽出された幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離する。これについては、図２に関連して説明されている。幾何学的レイアウトデザインデータを分離した後、データベースモジュール７０８は、データベース７１２の構造コンポーネント７１０に構造データを格納し、データベース７１２の空間コンポーネント７１４に空間データを格納し、データベース７１２のＲＡＷジオメトリコンポーネント７１６にＲＡＷジオメトリデータを格納する。これについては、図３に関連して説明されている。
【００４５】
構造データの各表現ごとに、構造コンポーネント７１０は、空間コンポーネント７１４とＲＡＷジオメトリコンポーネント７１６の各コンポーネントと第１のＡＰＩ（Application Programming Interface）を介して通信（データのやり取り）する。同様に、空間データの各表現ごとに、空間コンポーネント７１４は、構造コンポーネント７１０とＲＡＷジオメトリコンポーネント７１６の各コンポーネントと第２のＡＰＩを介して通信する。さらに、ＲＡＷジオメトリデータの各表現ごとに、ＲＡＷジオメトリコンポーネント７１６は、構造コンポーネント７１０と空間コンポーネント７１４の各コンポーネントと第３のＡＰＩを介して通信する。これによりアプリケーション７００のモジュール性が保証される。
【００４６】
本発明の実施の一形態において、第１のＡＰＩと第２のＡＰＩと第３のＡＰＩの各ＡＰＩのおかげで、データベースモジュール７０８とデータベース７１２は、構造データ、空間データ、およびＲＡＷジオメトリデータの各データの１以上の表現における整合性を維持することができる。例えば、空間データは、ボロノイ図（Voronoi diagrams）と四分木（Quad-tree）の各表現を用いて表される。この場合、１以上の変更が空間データのボロノイ図表現において行われる場合、データベースモジュール７０８は、空間データの整合性を維持するために、データベース７１２における空間データコンポーネント７１４の四分木表現を変更する。
【００４７】
分離された幾何学的レイアウトデザインデータを格納した後、レイアウト後ＥＤＡアプリケーションは、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して、１以上の所定の演算を実行する。レイアウト後ＥＤＡアプリケーションは、ライブラリセット７０４から１以上のライブラリをロードすることによって１以上の所定の演算を実行する。ライブラリセット７０４内のライブラリは１以上の所定の演算に対応する。ライブラリセット７０４内の各ライブラリは事前にコンパイルされたオブジェクトコードライブラリである。これについては、図２との関連で説明されている。本発明の実施の一形態において、ライブラリセット７０４と両立するユーザによって開発されたライブラリがライブラリセット７０４に追加されることがある。
【００４８】
１以上の所定の演算を実行した後、集約モジュール７１８は、構造データ、空間データ、およびＲＡＷジオメトリデータの１以上のデータに対して１以上の所定の演算を実行した１以上の結果を集約して、集約された結果を生成する。集約モジュール７１８は、構造データ、空間データ、およびＲＡＷジオメトリデータを集約して、集約結果を生成することができる。その後、集約モジュール７１８は、ライタ（writer）７２０と通信する。ライタ７２０は、集約結果を１以上の出力データフォーマットファイルに書き込む。
【００４９】
本発明の様々な実施形態は、レイアウト後ＥＤＡアプリケーションを開発するための方法およびシステムを提供する。このようにして開発されたレイアウト後ＥＤＡアプリケーションは、幾何学的レイアウトデザインデータを、構造データ、空間データ、およびＲＡＷジオメトリデータの各データに分離する。これにより、構造データ、空間データ、およびＲＡＷジオメトリデータの各データが容易に利用できることから、幾何学的レイアウトデザインデータに対する効率の高いレイアウト後演算が可能となる。加えて、構造データ、空間データ、およびＲＡＷジオメトリデータの各データの１以上の表現は、実行する演算に応じて使用することができる。構造データ、空間データ、およびＲＡＷジオメトリデータの各データを表現するために使用する表現は、実行時間またはコンパイル時間に選択することができる。加えて、１以上のデータ表現同士の間のデータ整合性が維持される。さらに、本発明の様々な実施形態は、使用するメモリ空間が少なくて済み効率の高い演算性能を可能にするデータ表現方法を提供する。
【００５０】
上記の説明では、本発明の特定の実施形態について説明してきた。しかしながら、当業者であれば、特許請求の範囲の請求項によって確定される本発明の範囲内において、上記実施形態の様々な変形および変更が可能であることは理解されよう。従って、本明細書および図面は制約目的ではなく説明目的で提供されていると解すべきであり、全ての斯かる変更および変形は本発明の範囲内に含まれることを意図している。本発明の利益、利点、課題解決方法、および任意の利益、利点、または解決方法をもたらすまたはより顕著にすることがある任意の要素は、特許請求の範囲の請求項のいずれかまたは全ての重要、必要、または不可欠な特徴もしくは要素と解すべきではない。
【図面の簡単な説明】
【００５１】
【図１】本発明が機能する環境（の一例）を示すブロック図である。
【図２】本発明の実施の一形態による、幾何学的レイアウトデザインデータを処理するための方法のフロー図である。
【図３】本発明の実施の一形態による、データの流れを示すフロー図である。
【図４】複数のセルを含む構造データの階層表現を示すブロック図である。
【図５】本発明の実施の一形態による、複数のセル、第１のセルの列挙型データ構造、第２のセルの列挙型データ構造、および第３のセルの列挙型データ構造を含むハイブリッド型階層表現を示すブロック図である。
【図６】本発明の実施の一形態による、構造データのハイブリッド型フラット表現における第１のセルに対応する境界ボックスを示すブロック図である。
【図７】本発明の実施の一形態による、レイアウト後ＥＤＡアプリケーションを開発するためのアプリケーションを示すブロック図である。
【図１】
2009516876.tif 000003
【図２】
2009516876.tif 000004
【図３】
2009516876.tif 000005
【図４】
2009516876.tif 000006
【図５】
2009516876.tif 000007
【図６】
2009516876.tif 000008
【図７】
2009516876.tif 000009