(57)【要約】【目的】バッファメモリのメモリ容量を超えないブロックサイズを取得する方法を提供することを目的とする。【構成】描画データの分割領域サイズの取得方法は、描画データを入力する工程（Ｓ２０２）と、描画領域をブロックサイズの複数の分割領域に分割する工程（Ｓ２０８）と、セル毎に、クワッドツリーの該当する要素にセル内の図形のデータ量を格納する工程（Ｓ２１６）と、図形のデータ量を該当するブロック領域に分配する工程（Ｓ２２０）と、ブロック領域毎に、分配された図形のデータ量を累積加算する工程（Ｓ２２２）と、累積加算データ量がメモリ容量以下かどうかを判定する工程（Ｓ２２６）と、判定の結果、メモリ容量以下でない場合に、ブロックサイズを小さくし、新たなブロックサイズをフィードバックする工程（Ｓ２２８）と、メモリ容量以下となるブロックサイズを出力する工程（Ｓ２３０）と、を備えたことを特徴とする。【選択図】図１
2010050187.tif 000002
【特許請求の範囲】
【請求項１】
荷電粒子ビームを用いて試料にパターンを描画するための描画データを入力する工程と、
所定の分割領域サイズを入力し、前記描画データに定義される描画領域を前記所定の分割領域サイズの複数の分割領域に分割する工程と、
前記描画データに定義される少なくとも１つの図形から構成されるセル毎に、クワッドツリーの該当する要素に前記セル内の図形のデータ量を格納する工程と、
分割領域毎に、前記クワッドツリーの各要素に格納された図形のデータ量を該当する分割領域に分配する工程と、
分割領域毎に、分配された図形のデータ量を累積加算する工程と、
分割領域毎に、累積加算された累積加算データ量が所定のメモリ容量以下かどうかを判定する工程と、
判定の結果、すべての分割領域について前記累積加算データ量が所定のメモリ容量以下でない場合に、前記所定の分割領域サイズを小さくし、前記描画領域を前記複数の分割領域に分割する工程へと小さくなった新たな所定の分割領域サイズをフィードバックする工程と、
判定の結果、すべての分割領域について前記累積加算データ量が所定のメモリ容量以下となる場合に、判定の際に前記複数の分割領域のサイズとなった所定の分割領域サイズを出力する工程と、
を備えたことを特徴とする描画データの分割領域サイズの取得方法。
【請求項２】
前記図形のデータ量は、図形が分割される確率に基づく図形個数期待値を用いた図形種ごとの演算式により求める各図形の図形個数に１つの図形あたりの単位データ量を乗じて求めることを特徴とする請求項１記載の描画データの分割領域サイズの取得方法。
【請求項３】
前記図形のデータ量は、図形の重心位置に対応する前記クワッドツリーの要素に格納されることを特徴とする請求項１又は２記載の描画データの分割領域サイズの取得方法。
【請求項４】
前記描画データに定義される少なくとも１つの図形により構成されるセルを互いに重なり部分を持って分割する複数の小領域における前記重なり部分のサイズ（２ｆ）以下のサイズの図形は前記サイズについての前記図形個数期待値が１になり、
前記重なり部分のサイズ（２ｆ）と前記小領域のサイズ（Ｓ）との中間のサイズの図形は図形サイズ（Ｌ）を用いて表すと前記サイズについての前記図形個数期待値が１＋（Ｌ−２ｆ）／Ｓになり、
図形サイズ（Ｌ）と２以上の整数（ｎ）とを用いて表すと（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲に入るサイズの図形は前記サイズについての前記図形個数期待値がｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）になることを特徴とする請求項１〜３いずれか記載の描画データの分割領域サイズの取得方法。
【請求項５】
荷電粒子ビームを用いて試料にパターンを描画するための描画データを入力して記憶する記憶部と、
所定の分割領域サイズを入力し、前記描画データに定義される描画領域を前記所定の分割領域サイズの複数の分割領域に分割する分割部と、
前記描画データに定義される少なくとも１つの図形から構成されるセル毎に、クワッドツリーの該当する要素に前記セル内の図形のデータ量を格納する格納処理部と、
分割領域毎に、前記クワッドツリーの各要素に格納された図形のデータ量を該当する分割領域に分配する分配部と、
分割領域毎に、分配された図形のデータ量を累積加算する累積加算部と、
分割領域毎に、累積加算された累積加算データ量が所定のメモリ容量以下かどうかを判定する判定部と、
判定の結果、すべての分割領域について前記累積加算データ量が所定のメモリ容量以下でない場合に、前記所定の分割領域サイズを小さくし、前記分割部へと小さくなった新たな所定の分割領域サイズをフィードバックするサイズ縮小部と、
判定の結果、すべての分割領域について前記累積加算データ量が所定のメモリ容量以下となる場合に、判定の際に前記複数の分割領域のサイズとなった所定の分割領域サイズを出力する出力部と、
を備えたことを特徴とする描画データの分割領域サイズの取得装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、描画データの分割領域サイズの取得方法及び描画データの分割領域サイズの取得装置に関する。例えば、電子ビームを用いて試料に所定のパターンを描画する描画装置で使用する描画データの分割領域サイズの取得方法および装置に関する。
【背景技術】
【０００２】
半導体デバイスの微細化の進展を担うリソグラフィ技術は半導体製造プロセスのなかでも唯一パターンを生成する極めて重要なプロセスである。近年、ＬＳＩの高集積化に伴い、半導体デバイスに要求される回路線幅は年々微細化されてきている。これらの半導体デバイスへ所望の回路パターンを形成するためには、高精度の原画パターン（レチクル或いはマスクともいう。）が必要となる。ここで、電子線（電子ビーム）描画技術は本質的に優れた解像性を有しており、高精度の原画パターンの生産に用いられる。
【０００３】
図１７は、従来の可変成形型電子線描画装置の動作を説明するための概念図である。
可変成形型電子線（ＥＢ：Ｅｌｅｃｔｒｏｎ  ｂｅａｍ）描画装置は、以下のように動作する。第１のアパーチャ４１０には、電子線３３０を成形するための矩形例えば長方形の開口４１１が形成されている。また、第２のアパーチャ４２０には、開口４１１を通過した電子線３３０を所望の矩形形状に成形するための可変成形開口４２１が形成されている。荷電粒子ソース４３０から照射され、開口４１１を通過した電子線３３０は、偏向器により偏向される。そして、可変成形開口４２１の一部を通過して、ステージ上に搭載された試料３４０に照射される。また、ステージは、描画中、所定の一方向（例えば、Ｘ方向とする）に連続的に移動する。すなわち、開口４１１と可変成形開口４２１との両方を通過できる矩形形状が、連続的に移動するステージ上に搭載された試料３４０の描画領域に描画される。開口４１１と可変成形開口４２１との両方を通過させ、任意形状を作成する方式を可変成形方式という。
【０００４】
かかる電子ビーム描画を行なうにあたり、まず、半導体集積回路のレイアウトが設計される。そして、パターンレイアウトが定義されたレイアウトデータ（設計データ）が生成される。そして、レイアウトデータが変換され、電子線描画装置に適応した描画データが生成される。そして、描画データは、描画装置に入力され、複数のデータ処理の後、描画する際のショットデータとして生成される（例えば、特許文献１参照）。そして、このショットデータに従って描画処理が行なわれる。描画装置内でのこれらの動作はリアルタイムで進んでいく。ここで、描画装置内では、複数のデータ処理を行う際に、描画領域を複数のブロック領域に分割して、ブロック領域毎に分散してデータ処理を行っている。そして、描画データがブロック領域毎に展開されていき、ショットデータが生成される前のブロック領域毎の中間データが生成されることになる。かかるブロック領域毎の中間データは、バッファメモリに一時的に格納されることになる。昨今のパターンの微細化に伴い、データ量は増加している。特に、クリティカルレイヤーのデータ量は膨大である。あるブロック領域についてこのようなデータ量の大きい中間データが生成されるとバッファメモリのメモリ容量を超えてしまい、バッファオーバーフローといった演算処理エラーを引き起こしてしまう。演算処理エラーが生じると描画ができなくなってしまい、描画中のマスクは廃棄されてしまうことになるといった問題があった。
【特許文献１】特開２００７−１２８９３３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述したように、あるブロック領域についてこのようなデータ量の大きい中間データが生成されるとバッファメモリのメモリ容量を超えてしまい、バッファオーバーフローといった演算処理エラーを引き起こしてしまう。これを回避するためには、ブロック領域のサイズを小さくしてブロック領域数を増やせばよいことになるが、不必要に小さいサイズでブロック領域を設定してしまうと、各データを処理する際のオーバーヘッド時間がブロック領域を増やした分だけ余計にかかってしまい演算処理にかかる時間が増大してしまう。演算処理にかかる時間が増大してしまうと実際の描画処理が演算処理の結果を待たなくてはならないため描画時間全体が増加してしまい、スループットが劣化してしまう。そのため、かかるバッファメモリのメモリ容量を超えないが不必要に小さくならないサイズのブロック領域になるようにブロック領域サイズを描画装置に設定することが望ましい。しかしながら、その手法は従来確立されていなかった。また、描画装置内でブロック領域毎の中間データのデータ量を得るには入力された描画データに対して数多くの演算処理を行なった後でなければ得られない。そのため、実描画の前にビームを照射しない空描画を行なってブロック領域毎の中間データのデータ量を演算し、バッファメモリの容量と比較することも装置の機能上は可能かもしれないが数多くの演算処理を行なければならない点に代わりはなく時間が長くかかってしまう。さらに、最適なブロック領域が見つかるまで、空描画を行なってブロック領域毎の中間データのデータ量を得ることを繰り返すことになりますます時間が長くかかってしまう。
【０００６】
そこで、本発明は、かかる問題を克服すべく、バッファメモリのメモリ容量を超えないが不必要に小さくならない分割領域サイズを取得する方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一態様の描画データの分割領域サイズの取得方法は、
荷電粒子ビームを用いて試料にパターンを描画するための描画データを入力する工程と、
所定の分割領域サイズを入力し、描画データに定義される描画領域を所定の分割領域サイズの複数の分割領域に分割する工程と、
描画データに定義される少なくとも１つの図形から構成されるセル毎に、クワッドツリーの該当する要素にセル内の図形のデータ量を格納する工程と、
分割領域毎に、クワッドツリーの各要素に格納された図形のデータ量を該当する分割領域に分配する工程と、
分割領域毎に、分配された図形のデータ量を累積加算する工程と、
分割領域毎に、累積加算された累積加算データ量が所定のメモリ容量以下かどうかを判定する工程と、
判定の結果、すべての分割領域について累積加算データ量が所定のメモリ容量以下でない場合に、所定の分割領域サイズを小さくし、描画領域を複数の分割領域に分割する工程へと小さくなった新たな所定の分割領域サイズをフィードバックする工程と、
判定の結果、すべての分割領域について累積加算データ量が所定のメモリ容量以下となる場合に、判定の際に複数の分割領域のサイズとなった所定の分割領域サイズを出力する工程と、
を備えたことを特徴とする描画データの分割領域サイズの取得方法。
【０００８】
セル毎に、クワッドツリーを構成することで、セルが分割領域に跨った場合でも図形のデータ量を該当する分割領域に分配することができる。さらに、クワッドツリーに図形のデータ量を格納しておくことで、分割領域サイズを縮小した場合でも改めて図形のデータ量を演算し直す必要がない。
【０００９】
また、図形のデータ量は、図形が分割される確率に基づく図形個数期待値を用いた図形種ごとの演算式により求める各図形の図形個数に１つの図形あたりの単位データ量を乗じて求めると好適である。
【００１０】
また、図形のデータ量は、図形の重心位置に対応する前記クワッドツリーの要素に格納されると好適である。
【００１１】
また、描画データに定義される少なくとも１つの図形により構成されるセルを互いに重なり部分を持って分割する複数の小領域における重なり部分のサイズ（２ｆ）以下のサイズの図形は該当サイズについての図形個数期待値が１になり、
重なり部分のサイズ（２ｆ）と小領域のサイズ（Ｓ）との中間のサイズの図形は図形サイズ（Ｌ）を用いて表すと該当サイズについての図形個数期待値が１＋（Ｌ−２ｆ）／Ｓになり、
図形サイズ（Ｌ）と２以上の整数（ｎ）とを用いて表すと（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲に入るサイズの図形は該当サイズについての図形個数期待値がｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）になると好適である。
【００１２】
本発明の一態様の描画データの分割領域サイズの取得装置は、
荷電粒子ビームを用いて試料にパターンを描画するための描画データを入力して記憶する記憶部と、
所定の分割領域サイズを入力し、描画データに定義される描画領域を所定の分割領域サイズの複数の分割領域に分割する分割部と、
描画データに定義される少なくとも１つの図形から構成されるセル毎に、クワッドツリーの該当する要素にセル内の図形のデータ量を格納する格納処理部と、
分割領域毎に、クワッドツリーの各要素に格納された図形のデータ量を該当する分割領域に分配する分配部と、
分割領域毎に、分配された図形のデータ量を累積加算する累積加算部と、
分割領域毎に、累積加算された累積加算データ量が所定のメモリ容量以下かどうかを判定する判定部と、
判定の結果、すべての分割領域について累積加算データ量が所定のメモリ容量以下でない場合に、所定の分割領域サイズを小さくし、分割部へと小さくなった新たな所定の分割領域サイズをフィードバックするサイズ縮小部と、
判定の結果、すべての分割領域について累積加算データ量が所定のメモリ容量以下となる場合に、判定の際に複数の分割領域のサイズとなった所定の分割領域サイズを出力する出力部と、
を備えたことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、バッファメモリのメモリ容量を超えないが不必要に小さくならない分割領域サイズを取得することができる。その結果、描画装置において、バッファオーバーフローといった演算処理エラーを引き起こしてしまうことを回避することができる。
【発明を実施するための最良の形態】
【００１４】
以下、実施の形態では、荷電粒子ビームの一例として、電子ビームを用いた構成について説明する。但し、荷電粒子ビームは、電子ビームに限るものではなく、イオンビーム等の荷電粒子を用いたビームでも構わない。また、荷電粒子ビーム装置の一例として、荷電粒子ビーム描画装置、特に、可変成形型の電子ビーム描画装置について説明する。
【００１５】
実施の形態１．
上述したように、電子ビーム描画を行なうにあたっては、まず、半導体集積回路のレイアウトが設計される。そして、パターンレイアウトが定義されたレイアウトデータ（設計データ）が生成される。そして、レイアウトデータが変換され、描画装置に適応した描画データが生成される。そして、描画データは、描画装置に入力される。描画装置内では、複数のデータ処理の後、描画する際のショットデータとして生成される。そして、ショットデータに基づいてパターンが試料に描画される。実施の形態１では、描画データが描画装置に入力される前、或いは並行して、描画データの最適な分割領域サイズ（ブロックサイズ）を描画装置外のオフラインで演算により求める。
【００１６】
図１は、実施の形態１における描画データの分割領域サイズの取得方法の要部工程を示すフローチャート図である。図１において、実施の形態１における描画データの分割領域サイズの取得方法は、入力／記憶工程（Ｓ２０２）と、マージ処理工程（Ｓ２０４）と、チップ毎のセル抽出工程（Ｓ２０６）と、ブロック分割工程（Ｓ２０８）と、図形数見積り工程（Ｓ２１０）と、図形データ量見積り工程（Ｓ２１２）と、重心演算工程（Ｓ２１４）と、図形データ量格納工程（Ｓ２１６）と、判定工程（Ｓ２１８）と、データ量分配工程（Ｓ２２０）と、ブロック毎のデータ量見積り工程（Ｓ２２２）と、データ量リスト作成工程（Ｓ２２４）と、判定工程（Ｓ２２６）と、ブロックサイズ縮小工程（Ｓ２２８）と、出力工程（Ｓ２３０）という一連の工程を実施する。
【００１７】
図２は、実施の形態１における描画データの階層構造の一例を示す図である。
描画データでは、描画領域が、チップ１０の層、チップ領域を例えばｙ方向に向かって短冊状に仮想分割したストライプ２０の層、ストライプ２０を分割したブロック３０の層、少なくとも１つ以上の図形で構成されるセル３２の層、セル３２を分割したクラスタ３４の層、クラスタ３４内に配置され、セル３２を構成する図形３６（パターン）の層といった一連の複数の内部構成単位ごとに階層化されている。また、１つの試料の描画領域に対して複数のチップがレイアウトされていることが一般的である。そのため、後述するマージ処理部において、チップマージ処理が行なわれ、図２に示すようなマージ後の階層が構成される。尚、ここではストライプ２０についてチップ領域を例えばｙ方向に向かって短冊状に分割した領域としてあるが、これは一例であり、描画面と平行しｙ方向と直交するｘ方向に分割する場合もありうる。或いは描画面と平行するその他の方向であっても構わない。
【００１８】
図３は、実施の形態１における描画データの分割領域サイズの取得装置の構成を示す概念図である。
図３において、描画データの分割領域サイズの取得装置１００は、制御計算機１１０、メモリ１４０、外部インターフェース（Ｉ／Ｆ）１４２、及び磁気ディスク装置１４４を備えている。制御計算機１１０、メモリ１４０、外部Ｉ／Ｆ１４２、及び磁気ディスク装置１４４は、互いに図示しないバスにより接続されている。制御計算機１１０内では、入力部１１１、マージ処理部１１２、セル抽出部１１４、分割部１１６、図形数見積り部１１８、図形データ量見積り部１２０、重心演算部１２２、図形データ量格納部１２４、判定部１２６、分配部１２８、ブロックデータ量見積り部１３０、リスト作成部１３２、判定部１３４、ブロックサイズ縮小部１３６、及び出力部１３８が配置されている。磁気ディスク装置１４４及びメモリ１４０は、記憶部或いは記憶装置の一例となる。外部Ｉ／Ｆ１４２は、入力部或いは出力部の一例にもなる。
【００１９】
ここで、入力部１１１、マージ処理部１１２、セル抽出部１１４、分割部１１６、図形数見積り部１１８、図形データ量見積り部１２０、重心演算部１２２、図形データ量格納部１２４、判定部１２６、分配部１２８、ブロックデータ量見積り部１３０、リスト作成部１３２、判定部１３４、ブロックサイズ縮小部１３６、及び出力部１３８は、ソフトウェアによる各処理機能として構成してもよい。或いは、入力部１１１、マージ処理部１１２、セル抽出部１１４、分割部１１６、図形数見積り部１１８、図形データ量見積り部１２０、重心演算部１２２、図形データ量格納部１２４、判定部１２６、分配部１２８、ブロックデータ量見積り部１３０、リスト作成部１３２、判定部１３４、ブロックサイズ縮小部１３６、及び出力部１３８の各構成を電気的な回路によるハードウェアにより構成してもよい。或いは、電気的な回路によるハードウェアとソフトウェアとの組合せにより実施させても構わない。或いは、かかるハードウェアとファームウェアとの組合せでも構わない。また、ソフトウェアにより、或いはソフトウェアとの組合せにより実施させる場合には、処理を実行する計算機に入力される情報或いは演算処理中及び処理後の各情報はその都度メモリ１４０に記憶される。
【００２０】
図３では、本実施の形態１を説明する上で必要な構成部分について記載している。分割領域サイズの取得装置１００にとって、通常、必要なその他の構成が含まれても構わないことは言うまでもない。
【００２１】
Ｓ（ステップ）２０２において、入力／記憶工程として、入力部１１１は、電子ビームを用いて試料にパターンを描画するための描画データを外部Ｉ／Ｆ１４２を介して外部から入力し、磁気ディスク装置１４４に記憶する。１つのマスク基板には、通常、複数のチップのパターンが描画される。そのため、描画データは、通常、複数のチップデータファイルから構成される。
【００２２】
Ｓ２０４において、マージ処理工程として、マージ処理部１１２は、磁気ディスク装置１４４から描画データを読み出し、複数のチップのうち、チップ間の距離が所定のサイズよりも狭いチップ同士についてマージ処理を行う。
【００２３】
Ｓ２０６において、チップ毎のセル抽出工程として、セル抽出部１１４は、マージ後の各チップについて、チップ毎に、描画データに定義されるセルデータから各チップ内に配置されるセルを抽出する。図２に示したように、描画データは階層構造を持って定義されており、それぞれの階層の配置位置、サイズ、階層関係等が描画データに定義される。よって、描画データから各チップに配置されるセルを抽出することができる。
【００２４】
Ｓ２０８において、ブロック分割工程として、分割部１１６は、外部からブロックサイズＢ１（所定の分割領域サイズ）を入力し、上述したセル抽出工程（Ｓ２０６）と並列に、描画データに定義される描画領域をブロックサイズの複数のブロック（分割領域）に分割する。ここでは、並列処理となっているが、セル抽出工程（Ｓ２０６）と直列に処理するように構成しても構わない。外部Ｉ／Ｆ１４２、或いは図示しないキーボード（Ｋ／Ｂ）やマウス等を介して外部から入力（設定）されたブロックサイズは、磁気ディスク装置１４４に記憶される。
【００２５】
Ｓ２１０において、図形数見積り工程として、図形数見積り部１１８は、抽出されたセル毎に、セル内に配置される図形数を見積もる。描画装置では、図２に示したクラスタ３４（小領域）内に収まるように各図形が分割される。そのため、分割によって当初の描画データ内に定義された図形数よりもその数が増えることになる。１つの図形を定義するためのデータ量は一定であるので図形数が増えるとその分だけデータ量も増えることになる。そこで、図形数見積り部１１８は、クラスタのサイズやマージンサイズ等の情報を入力して、分割後の図形数を確率に基づいて導かれる分割後の図形個数期待値を用いて見積もる。クラスタのサイズやマージンサイズ等の情報は、外部Ｉ／Ｆ１４２、或いは図示しないキーボード（Ｋ／Ｂ）やマウス等を介して外部から入力（設定）されればよい。
【００２６】
図４は、実施の形態１におけるクラスタ領域の一例を示す概念図である。図４において、縦横の幅（Ｓ）の複数のクラスタ３４が、互いに重なりながら配置するように定義される。各クラスタ３４では、点線で示す図形のカットライン４０から外側にマージン４２が付され、各クラスタ３４の領域は、各辺についてマージン４２のマージン幅（ｆ）が付加されたクラスタ境界４４で囲まれた領域となる。そして、各クラスタ３４は、隣り合うクラスタ３４とマージン幅（ｆ）の２倍の重なり幅（２ｆ）（重なり部分のサイズ）で互いに重なるように定義される。幅（Ｓ）は、例えば、１２．８μｍ或いは６．４μｍで設定される。マージン幅（ｆ）は、例えば、０．８μｍで設定される。
【００２７】
図５は、実施の形態１におけるクラスタ領域内に配置され得る図形の一例を示す概念図である。図５に示すように、クラスタ領域内には、ある方向のサイズが、重なり幅（２ｆ）以下のサイズの図形５２、重なり幅（２ｆ）とクラスタのサイズ（Ｓ）との中間のサイズの図形５４、及びクラスタのサイズ（Ｓ）以上の図形５６とが配置され得る。重なり幅（２ｆ）以下のサイズの図形５２については、分割すると小さすぎて描画できない微小図形となる（スリバーが生じる）おそれがあるのでたとえカットライン４０を跨っていたとしても分割しない。図形５２が図５に示す位置の場合、図形５２は左側のクラスタに定義されることになる。また、重なり幅（２ｆ）とクラスタのサイズ（Ｓ）との中間のサイズの図形５４については、分割される場合と分割されない場合とが生じ得る。図形５４が図５に示す位置の場合、図形５４はカットライン４０で分割されて左右のクラスタに分かれて定義されることになる。また、クラスタのサイズ（Ｓ）以上の図形５６については必ず分割される。図形５６が図５に示す位置の場合、図形５６は３つのカットライン４０で分割されて左端部は図示しない左側のクラスタに、右端部は図示しない右側のクラスタに、２つの中央部は、それぞれが位置するクラスタに分かれて定義されることになる。そこで、各条件について、分割を見積もる図形サイズについての分割される確率を求める。その際、分割を見積もる図形のサイズを（Ｌ）とする。後述するように、分割の対象となる図形サイズは一方向だけではないが、内容を理解しやすくするために、ここでは一方向のサイズについて説明する。
【００２８】
（１）Ｌ≦２ｆの範囲の場合
重なり幅（２ｆ）以下のサイズ（Ｌ）の図形５２が分割される確率は、上述したように分割されないので０となる。
（２）２ｆ＜Ｌ＜Ｓの範囲の場合
重なり幅（２ｆ）とクラスタのサイズ（Ｓ）との中間のサイズの図形５４が分割される確率は、最大２個に分割され得るので、（Ｌ−２ｆ）／Ｓで定義することができる。分割される確率＝１−分割されない確率＝１−（２ｆ／／Ｓ＋（Ｓ−Ｌ）／Ｓ）＝（Ｌ−２ｆ）／Ｓという式の展開により導くことができる。
（３）（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）
図形のサイズ（Ｌ）は無限ではないので、クラスタのサイズ（Ｓ）以上であり、かつ、（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲になる場合について示す。図５では、一例として、２つのクラスタよりも大きく３つのクラスタよりも小さい場合（ｎ＝３の場合）が示されている。かかる場合には必ず分割されるが、今度は何個に分割されるのかが問題となる。そこで、（ｎ＋１）個に分割される確率を用いる。（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲となるサイズの図形５６が（ｎ＋１）個に分割される確率は、（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）で定義することができる。（ｎ＋１）個に分割される確率は、１−（（ｎ＋１）個に分割されない確率）から導くことができる。
【００２９】
以上説明した各範囲の確率から導かれる、分割を見積もる図形サイズについての図形個数期待値は、以下のようになる。
（１）Ｌ≦２ｆの範囲の場合
重なり幅（２ｆ）以下のサイズ（Ｌ）の図形５２は、確率が０であるので分割されず、その図形のまま（１個のまま）であるので、図形個数期待値は１と定義することができる。
（２）２ｆ＜Ｌ＜Ｓの範囲の場合
重なり幅（２ｆ）とクラスタのサイズ（Ｓ）との中間のサイズの図形５４は、確率が（Ｌ−２ｆ）／Ｓで定義され、最大２個に分割され得るので、図形個数期待値は１＋（Ｌ−２ｆ）／Ｓと定義することができる。図形個数期待値は、（１個のままの確率）×１＋（２個に分割される確率）×２で求めることができる。
（３）（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）
（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲に入るサイズの図形５６は、（ｎ＋１）個に分割される確率が（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）で定義され、最大（ｎ＋１）個に分割され得るので、図形個数期待値がｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。図形個数期待値は、（（ｎ＋１）個に分割されない確率）×ｎ＋（（ｎ＋１）個に分割される確率）×（ｎ＋１）で求めることができる。
【００３０】
ここで、図形のサイズは一方向だけではないので、各サイズについて、上述した図形個数期待値で分割され得る。そして、１つの図形としての分割され得る図形個数期待値は、図形種によって以下のように定義することができる。
【００３１】
図６は、実施の形態１における長方形の図形個数期待値を説明するための概念図である。図６において、長方形或いは正方形は、横サイズ（Ｘ方向サイズ）ＬＸと縦サイズ（Ｙ方向サイズ）ＬＹで定義される。そして、１つの長方形或いは正方形の全体の図形個数期待値ＮＴＯＴＡＬは、図６に示すように、Ｘ方向サイズの図形個数期待値ＮＤ（ＬＸ）とＹ方向サイズの図形個数期待値ＮＤ（ＬＹ）との積で定義することができる。
【００３２】
Ｘ方向サイズの図形個数期待値ＮＤ（ＬＸ）は、上述したように、（１）ＬＸ≦２ｆの範囲の場合、図形個数期待値ＮＤ（ＬＸ）＝１と定義することができる。（２）２ｆ＜ＬＸ＜Ｓの範囲の場合、図形個数期待値ＮＤ（ＬＸ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦ＬＸ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（ＬＸ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００３３】
Ｙ方向サイズの図形個数期待値ＮＤ（ＬＹ）も、上述したように、（１）ＬＹ≦２ｆの範囲の場合、図形個数期待値ＮＤ（ＬＹ）＝１と定義することができる。（２）２ｆ＜ＬＹ＜Ｓの範囲の場合、図形個数期待値ＮＤ（ＬＹ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦ＬＹ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（ＬＹ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００３４】
図７は、実施の形態１における直角二等辺三角形の図形個数期待値を説明するための概念図である。図７において、直角二等辺三角形は、直角を挟む二辺のサイズＬで定義される。そして、１つの直角二等辺三角形の全体の図形個数期待値ＮＴＯＴＡＬは、図７に示すように、直角を挟む二辺の一方のサイズの図形個数期待値ＮＤ（Ｌ）と他方のサイズの図形個数期待値ＮＤ（Ｌ）に補正値１を加算した値との積の１／２で定義することができる。直角二等辺三角形が分割されない場合の個数は１なので、図形個数期待値ＮＴＯＴＡＬが１より小さくなることはあり得ない。そのため、補正値１を加算することで１より小さくなることを防止することができる。
【００３５】
直角を挟む二辺のサイズＬの図形個数期待値ＮＤ（Ｌ）は、上述したように、（１）Ｌ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｌ）＝１と定義することができる。（２）２ｆ＜Ｌ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｌ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｌ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｌ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００３６】
図８は、実施の形態１における台形の図形個数期待値を説明するための概念図である。図８（ａ）では、上下の辺が平行であり、高さをＨ、平行な２辺の長辺のサイズをＷ、短辺のサイズをＷ−Ｈとする台形を示している。図８（ｂ）は左右の辺が平行あり、高さをＨ、平行な２辺の長辺のサイズをＷ、短辺のサイズをＷ−Ｈとする台形を示している。そして、かかる１つの台形の全体の図形個数期待値ＮＴＯＴＡＬは、図８に示すように、平行な２辺の長辺のサイズＷの図形個数期待値ＮＤ（Ｗ）と高さＨの図形個数期待値ＮＤ（Ｈ）との積から、高さＨの図形個数期待値ＮＤ（Ｈ）と高さＨの図形個数期待値ＮＤ（Ｈ）から補正値１を引いた値との積の１／２を引いた差分で定義することができる。台形についても分割されない場合の個数は１なので、図形個数期待値ＮＴＯＴＡＬが１より小さくなることはあり得ない。そのため、補正値１を引くことで１より小さくなることを防止することができる。
【００３７】
２辺の長辺のサイズＷの図形個数期待値ＮＤ（Ｗ）は、上述したように、（１）Ｗ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｗ）＝１と定義することができる。（２）２ｆ＜Ｗ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｗ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｗ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｗ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００３８】
高さＨの図形個数期待値ＮＤ（Ｈ）も、上述したように、（１）Ｈ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１と定義することができる。（２）２ｆ＜Ｈ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｈ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｈ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００３９】
図９は、実施の形態１における等脚台形と二等辺三角形の図形個数期待値を説明するための概念図である。図９（ａ）（ｂ）では、二等辺ではない残りの辺のサイズをＨ、かかる残りの辺からの高さをＨとする二等辺三角形を示している。図９（ａ）では頂点が横向き、図９（ｂ）では頂点が上向きの場合を示している。図９（ｃ）（ｄ）では、高さをＨ、平行な２辺の長辺のサイズをＷ、短辺のサイズをＷ−２Ｈとする等脚台形を示している。図９（ｃ）では、左右の辺が平行である場合を示している。図９（ｄ）では、上下の辺が平行である場合を示している。そして、かかる１つの等脚台形或いは二等辺三角形の全体の図形個数期待値ＮＴＯＴＡＬは、図９に示すように、サイズＷの図形個数期待値ＮＤ（Ｗ）とサイズＨの図形個数期待値ＮＤ（Ｈ）との積から、サイズＨの図形個数期待値ＮＤ（Ｈ）とサイズＨの図形個数期待値ＮＤ（Ｈ）から補正値１を引いた値との積を引いた差分で定義することができる。かかる等脚台形或いは二等辺三角形についても分割されない場合の個数は１なので、図形個数期待値ＮＴＯＴＡＬが１より小さくなることはあり得ない。そのため、補正値１を引くことで１より小さくなることを防止することができる。
【００４０】
サイズＷの図形個数期待値ＮＤ（Ｗ）は、上述したように、（１）Ｗ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｗ）＝１と定義することができる。（２）２ｆ＜Ｗ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｗ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｗ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｗ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００４１】
サイズＨの図形個数期待値ＮＤ（Ｈ）も、上述したように、（１）Ｈ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１と定義することができる。（２）２ｆ＜Ｈ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｈ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｈ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００４２】
図１０は、実施の形態１における平行四辺形の図形個数期待値を説明するための概念図である。図１０（ａ）では、上下の辺が平行であり、高さをＨ、平行な２辺のサイズをＷとする平行四辺形を示している。図１０（ｂ）では、左右の辺が平行であり、高さをＨ、平行な２辺のサイズをＷとする平行四辺形を示している。そして、かかる１つの平行四辺形の全体の図形個数期待値ＮＴＯＴＡＬは、図１０に示すように、サイズＨの図形個数期待値ＮＤ（Ｈ）とサイズＷとサイズＨの和の図形個数期待値ＮＤ（Ｗ＋Ｈ）との積から、サイズＨの図形個数期待値ＮＤ（Ｈ）とサイズＨの図形個数期待値ＮＤ（Ｈ）から補正値１を引いた値との積を引いた差分で定義することができる。かかる平行四辺形についても分割されない場合の個数は１なので、図形個数期待値ＮＴＯＴＡＬが１より小さくなることはあり得ない。そのため、補正値１を引くことで１より小さくなることを防止することができる。
【００４３】
サイズＨの図形個数期待値ＮＤ（Ｈ）も、上述したように、（１）Ｈ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１と定義することができる。（２）２ｆ＜Ｈ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｈ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｈ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｈ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００４４】
サイズＷとサイズＨの和の図形個数期待値ＮＤ（Ｗ＋Ｈ）も、上述したように、（１）Ｗ＋Ｈ≦２ｆの範囲の場合、図形個数期待値ＮＤ（Ｗ＋Ｈ）＝１と定義することができる。（２）２ｆ＜Ｗ＋Ｈ＜Ｓの範囲の場合、図形個数期待値ＮＤ（Ｗ＋Ｈ）＝１＋（Ｌ−２ｆ）／Ｓと定義することができる。（３）（ｎ−１）Ｓ≦Ｗ＋Ｈ＜ｎＳの範囲の場合（但し、ｎは２以上の整数）、図形個数期待値ＮＤ（Ｗ＋Ｈ）＝ｎ＋（Ｌ−２ｆ）／（ｎＳ−（ｎ−１）×２ｆ）と定義することができる。
【００４５】
以上のようにして、図形数見積り部１１８は、抽出されたセル毎に、セル内に配置される各図形について、図形個数期待値ＮＴＯＴＡＬを計算し、その合計を分割後の図形数と見積もる。
【００４６】
Ｓ２１２において、図形データ量見積り工程として、図形データ量見積り部１２０は、図形毎に、前工程で求められた該当するセル内の分割後の図形数（図形個数期待値ＮＴＯＴＡＬ）に１図形あたりのデータ量を乗じて、図形毎の図形データ量を見積もる。例えば、１図形を定義するにあたり１６バイトのデータ量とする。
【００４７】
Ｓ２１４において、重心演算工程として、重心演算部１２２は、分割前の各図形の重心位置を演算する。描画データには、各図形の図形種、基準位置座標及び図形サイズが定義されているので、かかる情報から各図形の重心位置を演算することができる。
【００４８】
Ｓ２１６において、図形データ量格納工程として、図形データ量格納部１２４は、見積もった各図形データ量を該当するクワッドツリー（四分木）の要素に格納する。
【００４９】
図１１は、実施の形態１におけるクワッドツリーの一例を示す図である。図１１において、クワッドツリーは、ルート７０を基点にして、４分割した第２層目の要素となる北西（ＮＷ）７２、北東（ＮＥ）７４、南西（ＳＷ）７６、及び南東（ＳＥ）７８が並列に連なる。そして、第２層目の各要素を基点にして、４分割した第３層目の要素となる北西（ＮＷ）８２、北東（ＮＥ）８４、南西（ＳＷ）８６、及び南東（ＳＥ）８８が並列にそれぞれ連なる。最終層の要素がクラスタ３４のサイズになるまでこれを繰り返すことでクワッドツリーを構成する。
【００５０】
図１２は、図１１のクワッドツリーの各要素の領域の一例を示す図である。図１２において、まず、ルート７０はセル３２領域に相当する領域とする。ルート７０を縦横に２分割ずつすることで、ルート７０が４分割された各領域を第２層目の要素となる北西（ＮＷ）７２、北東（ＮＥ）７４、南西（ＳＷ）７６、及び南東（ＳＥ）７８の各領域とする。それぞれの配置位置は、図１２に向かって上方を北として、それぞれの要素が対応する領域とすればよい。そして、北西（ＮＷ）７２を縦横に２分割ずつすることで、ＮＷ７２が４分割された各領域を第３層目の要素となる北西（ＮＷ）８２ａ、北東（ＮＥ）８４ａ、南西（ＳＷ）８６ａ、及び南東（ＳＥ）８８ａの各領域とする。同様に、北東（ＮＥ）７４を縦横に２分割ずつすることで、ＮＥ７４が４分割された各領域を第３層目の要素となる北西（ＮＷ）８２ｂ、北東（ＮＥ）８４ｂ、南西（ＳＷ）８６ｂ、及び南東（ＳＥ）８８ｂの各領域とする。同様に、南西（ＳＷ）７６を縦横に２分割ずつすることで、ＳＷ７６が４分割された各領域を第３層目の要素となる北西（ＮＷ）８２ｃ、北東（ＮＥ）８４ｃ、南西（ＳＷ）８６ｃ、及び南東（ＳＥ）８８ｃの各領域とする。同様に、南東（ＳＥ）７８を縦横に２分割ずつすることで、ＳＥ７８が４分割された各領域を第３層目の要素となる北西（ＮＷ）８２ｄ、北東（ＮＥ）８４ｄ、南西（ＳＷ）８６ｄ、及び南東（ＳＥ）８８ｄの各領域とする。図１１及び図１２では、第３層までしか示していないが、クラスタサイズになるまで、階層を細分化する。以上のように構成されたクワッドツリーに対し、各図形の見積もった図形データ量を、クワッドツリーの最下層、すなわち、クラスタサイズの層における当該図形の重心位置に該当する要素に格納する。抽出されたセル内の全ての図形について、同様に、見積もった図形データ量を、クワッドツリーの最下層、すなわち、クラスタサイズの層における当該図形の重心位置に該当する要素に格納する。このように、セル毎に、クワッドツリーを構成して、セル内の各図形データを格納する。
【００５１】
そして、上層の要素には、かかる要素に連なる１つ下層の要素内に格納される図形データ量の合計が格納される。例えば、ある図形の図形データ量が北西（ＮＷ）８２ａに格納され、別の図形の図形データ量が北東（ＮＥ）８４ａに格納された場合、１つ上層の北西（ＮＷ）７２には、北西（ＮＷ）８２ａに格納された図形データ量と北東（ＮＥ）８４ａに格納された図形データ量との合計が格納される。同様に、北東（ＮＥ）７４にある図形データ量の合計が格納されている場合に、ルート７０には、北西（ＮＷ）７２に格納された図形データ量と北東（ＮＥ）７４に格納された図形データ量との合計が格納される。このように、各階層の各要素には、その要素に連なる１つ下の階層の要素に格納されたデータ量の合計が格納される。
【００５２】
図１３は、実施の形態１におけるセルサイズとクワッドツリーへの格納状態との関係の一例を示す図である。図１３（ａ）において、例えば、セル３２が、クワッドツリーのルート７０として設定した領域のうち、西側半分の大きさであった場合、クワッドツリーに格納される図形データ量についても、図１３（ｂ）に示すように、第２層目の北西（ＮＷ）７２と南西（ＳＷ）７６に連なる最終階層にしか格納されない。その際、格納されない要素については、別のデータで満たすのではなく、φ（ＮＵＬＬ）データとすることで、それ以下の層を作らないように構成する。このように構成することで、クワッドツリー全体のデータ量を小さくすることができる。図１３では、第２層目でφデータの要素が生じた例について示したが、これに限るものではなく、格納される図形データが存在しない階層の要素が生じた時点でφデータとし、それ以下の層を作らないように構成すればよいことは言うまでもない。
【００５３】
Ｓ２１８において、判定工程として、判定部１２６は、すべてのセルについて各図形の図形データ量の見積りが終了しているかどうかを判定する。まだ、終了しておらず、セルが残っている場合にはＳ２０６に戻る。そして、すべてのセル内の図形について図形データ量の見積りが終了するまでＳ２０６〜Ｓ２１８を繰り返す。
【００５４】
Ｓ２２０において、データ量分配工程として、分配部１２８は、ブロック分割工程（Ｓ２０８）で分割されたブロック領域毎に、該当する図形データ量を分配する。例えば、セル全体が１つのブロック領域内に納まる場合には、そのセルについて作成されたクワッドツリーのルート７０内に格納された図形データ量を分配すればよい。セルの基準位置の座標によりどのブロック領域に配置されるかが決定されればよい。また、セルが複数のブロック領域に跨る場合には、それぞれのブロック領域の境界でどちらのブロック領域に属するかを判定できるクワッドツリーの階層で、各要素内に格納された図形データ量を属するブロック領域に分配すればよい。その際、クワッドツリーの要素の基準位置の座標が属するブロック領域に図形データ量を分配すると好適である。基準位置としては、例えば、要素が示す領域の左下の角を用いると好適である。クワッドツリーを作成しているので、セルがブロックを跨った場合でも容易に図形データ量を該当するブロック領域に分配することができる。
【００５５】
Ｓ２２２において、ブロック毎のデータ量見積り工程として、ブロックデータ量見積り部１３０は、分割されたブロック領域毎に、各ブロック領域に分配された図形のデータ量を累積加算して、各ブロック領域内に配置される図形の累積加算データ量を見積もる。
【００５６】
以上のように、描画データに定義された図形が分割される確率に基づいて導かれる分割後の図形個数期待値を用いて、各分割領域内に配置される図形のデータ量が見積もられる。その際、データ量は、図形個数期待値ＮＤを用いた図形種ごとの演算式により求める各図形の図形個数ＮＴＯＴＡＬに１つの図形あたりの単位データ量を乗じた値を該当するブロック領域に累積加算して求める。
【００５７】
Ｓ２２４において、データ量リスト作成工程として、リスト作成部１３２は、ブロック領域毎のデータ量リストを作成する。
【００５８】
図１４は、実施の形態１におけるデータ量リストの一例を示す図である。図１１に示すように、リスト作成部１３２は、ブロック座標（Ｘ，Ｙ）とデータ量（バイト）とを対応させたデータ量リスト６０を作成する。データ量リスト６０には、マージ処理後のチップ毎に、各チップ内の全てのブロック領域について、対応するデータ量が記録される。データ量リスト６０は、磁気ディスク装置１４４に格納される。
【００５９】
Ｓ２２６において、判定工程として、判定部１３４は、ブロック領域毎に、データ量ｄが所定のメモリ容量Ｍ以下かどうかを判定する。この判定に際し、判定部１３４は、磁気ディスク装置１４４に格納されたデータ量リスト６０を参照し、対応するブロック領域のデータ量を読み出せばよい。そして、チップ毎にチップ内の全てのブロック領域のデータ量ｄが所定のメモリ容量Ｍ以下とならない場合にはブロックサイズ縮小工程（Ｓ２２２）に進む。チップ毎にチップ内の全てのブロック領域のデータ量ｄが所定のメモリ容量Ｍ以下となる場合には出力工程（Ｓ２２４）に進む。
【００６０】
Ｓ２２８において、ブロックサイズ縮小工程として、ブロックサイズ縮小部１３６は、判定工程（Ｓ２２０）での判定の結果、すべてのブロック領域についてデータ量ｄが所定のメモリ容量Ｍ以下でない場合に、現在設定されているブロックサイズ（分割領域サイズ）を小さくし、描画領域を複数の分割領域に分割するブロック分割工程（Ｓ２０８）へと小さくなった新たなブロックサイズＢｉをフィードバックする。例えば、ブロックサイズを現在設定されているブロックサイズの縦横１／２に縮小する。なお、ここでは、ブロックサイズ縮小部１３６が自動的にブロックサイズを小さくしているが、これに限るものではなく、図示しないモニタ或いは外部Ｉ／Ｆ１４２を介してユーザが判定の結果を得て、ユーザがブロックサイズを小さくして分割領域サイズの取得装置１００に再設定してもよい。
【００６１】
そして、ブロック分割工程（Ｓ２０８）において、分割部１１６は、フィードバック或いは再設定されたブロックサイズＢｉを入力し、描画データに定義される描画領域を新たなブロックサイズの複数のブロック領域（分割領域）に分割し直す。そして、データ量分配工程（Ｓ２２０）〜判定工程（Ｓ２２６）を繰り返す。そして、判定工程（Ｓ２２６）での判定の結果、すべてのブロック領域についてデータ量ｄが所定のメモリ容量Ｍ以下でない場合に、現在設定されているブロックサイズ（分割領域サイズ）を小さくし、描画領域を複数の分割領域に分割するブロック分割工程（Ｓ２０８）へと小さくなった新たなブロックサイズＢｉをフィードバックする。このように、すべてのブロック領域についてデータ量ｄが所定のメモリ容量Ｍ以下になるまで、ブロックサイズ縮小工程（Ｓ２２８）とブロック分割工程（Ｓ２０８）とデータ量分配工程（Ｓ２２０）〜判定工程（Ｓ２２６）とを繰り返す。
【００６２】
各チップ内の各図形の図形データ量は、すでにクワッドツリー内に格納されているので、ブロックサイズを縮小する場合でも、データ量分配工程（Ｓ２２０）においてすでにクワッドツリー内に格納されている各図形の図形データ量を用いればよい。そのため、ブロックサイズを縮小してブロック毎のデータ量見積り直す場合でも、チップ毎のセル抽出工程（Ｓ２０６）から判定工程（Ｓ２１８）の各工程を繰り返さずに済ますことができる。
【００６３】
Ｓ２３０において、出力工程として、出力部１３８は、判定工程（Ｓ２２６）での判定の結果、すべてのブロック領域についてデータ量ｄが所定のメモリ容量Ｍ以下となる場合に、判定の際に複数のブロック領域のサイズとなったブロックサイズＢｉを出力する。最終的なブロックサイズＢｉは、磁気ディスク装置１４４に格納されると共に、外部Ｉ／Ｆ１４２を介して、描画装置へと出力される。また、ブロック毎のデータ量も出力するとさらに好適である。例えば、データ量リスト６０を出力すると好適である。
【００６４】
図１５は、実施の形態１における図形数の見積り誤差とデータ量とバッファメモリのメモリ容量との関係の一例を示す図である。図１５に示すように、データ量が大きくなるにしたがい図形数の見積もり誤差は急激に減少する。見積り方法において、ランダムな大きさの図形がランダムに配置されていることを仮定とすると、サンプル数を増やせば増やすほど、中心極限定理により正規分布に従い、且つ分布の幅は狭まる。以上のように、描画データの最適なブロックサイズの取得にあたって、描画データに定義された図形が分割される確率に基づいて導かれる分割後の図形個数期待値を用いることが有効である。
【００６５】
図１６は、実施の形態１における描画装置内でのデータ処理の流れを示すフローチャート図である。上述したように、電子ビーム描画を行なうにあたっては、まず、半導体集積回路のレイアウトが設計される。そして、パターンレイアウトが定義されたレイアウトデータ（設計データ）が生成される。そして、レイアウトデータが変換され、描画装置に適応した描画データが生成される。そして、描画データは、描画装置に入力される。描画装置内では、磁気ディスク装置３１０に描画データが格納される。そして、後述するように複数のデータ処理の後、描画する際のショットデータとして生成される。
【００６６】
データ処理工程（Ｓ１０２）として、磁気ディスク装置３１０から複数のチップのそれぞれの描画データを読み出し、入力する。そして、描画領域内に再配置して、チップマージ処理を行なう。そして、処理が実行された後の描画データは、磁気ディスク装置３１２に格納される。
【００６７】
ブロック分割工程（Ｓ１０４）として、上段の工程でデータ処理された描画データを展開して、チップ或いは各ストライプを複数のブロック領域に仮想分割する。この際、実施の形態１における描画データのブロックサイズ取得方法によって既にバッファ容量を超えない最適なブロックサイズが求まっているので、描画装置にはこのブロックサイズが設定される。そして、設定されたブロックサイズで複数のブロック領域に仮想分割することになる。
【００６８】
セル配置工程（Ｓ１０６）として、描画データをさらに展開して、各ブロック内にレイアウトされたセルを配置する。
【００６９】
クラスタ分割工程（Ｓ１０８）として、描画データをさらに展開して、各セルを複数のクラスタに仮想分割する。
【００７０】
パターン分割工程（Ｓ１１０）として、描画データをさらに展開して、各クラスタ３４を各クラスタ内にレイアウトされた複数の図形（パターン）に分割する。
【００７１】
フォーマット変換工程（Ｓ１２０）として、描画データに定義されるデータを変換する。描画データをフォーマット変換することで、ショットデータへと変換される前段階となる中間データを生成する。そして、中間データはバッファメモリ３１４に一時的に格納される。ここで、実施の形態１では、既にバッファメモリ３１４のメモリ容量を超えないようにブロックサイズを指定しているので、バッファオーバーフローといった演算処理エラーを引き起こしてしまうことを防止することができる。その結果、演算処理エラーが生じて描画ができなくなってしまうといった不具合を防止することができる。
【００７２】
ショットデータ生成工程（Ｓ１２２）として、バッファメモリ３１４から中間データを読み出し、ショットデータを生成する。以上のようにして生成されたショットデータは磁気ディスク装置３１６に格納される。
【００７３】
そして、描画装置は、以上のように生成されたショットデータにより制御された電子ビームを用いて以下のように試料にパターンを描画する。
【００７４】
以上のように、実施の形態１における描画データの分割領域サイズの取得方法およびその装置によれば、バッファメモリ３１４のメモリ容量を超えないようにブロックサイズを簡易に取得することができる。実施の形態１のように、図形が分割される確率に基づく図形個数期待値を用いて、図形個数を見積もることで、描画装置内で実行されるデータ処理のような実際にクラスタ分割や図形分割の各処理を行わずに処理できるので、より高速にブロック領域のデータ量を見積もることができる。また、実施の形態１では、自動的に最適なブロックサイズを取得することができる。
【００７５】
以上、具体例を参照しつつ実施の形態について説明した。しかし、本発明は、これらの具体例に限定されるものではない。
【００７６】
また、装置構成や制御手法等、本発明の説明に直接必要しない部分等については記載を省略したが、必要とされる装置構成や制御手法を適宜選択して用いることができる。例えば、描画データの分割領域サイズの取得装置１００を制御する制御部構成や描画装置の構成については、記載を省略したが、必要とされる構成等を適宜選択して用いることは言うまでもない。
【００７７】
その他、本発明の要素を具備し、当業者が適宜設計変更しうる全ての描画データの分割領域サイズの取得方法及び描画データの分割領域サイズの取得装置は、本発明の範囲に包含される。
【図面の簡単な説明】
【００７８】
【図１】実施の形態１における描画データの分割領域サイズの取得方法の要部工程を示すフローチャート図である。
【図２】実施の形態１における描画データの階層構造の一例を示す図である。
【図３】実施の形態１における描画データの分割領域サイズの取得装置の構成を示す概念図である。
【図４】実施の形態１におけるクラスタ領域の一例を示す概念図である。
【図５】実施の形態１におけるクラスタ領域内に配置され得る図形の一例を示す概念図である。
【図６】実施の形態１における長方形の図形個数期待値を説明するための概念図である。
【図７】実施の形態１における直角二等辺三角形の図形個数期待値を説明するための概念図である。
【図８】実施の形態１における台形の図形個数期待値を説明するための概念図である。
【図９】実施の形態１における等脚台形と二等辺三角形の図形個数期待値を説明するための概念図である。
【図１０】実施の形態１における平行四辺形の図形個数期待値を説明するための概念図である。
【図１１】実施の形態１におけるクワッドツリーの一例を示す図である。
【図１２】図１１のクワッドツリーの各要素の領域の一例を示す図である。
【図１３】実施の形態１におけるセルサイズとクワッドツリーへの格納状態との関係の一例を示す図である。
【図１４】実施の形態１におけるデータ量リストの一例を示す図である。
【図１５】実施の形態１における図形数の見積り誤差とデータ量とバッファメモリのメモリ容量との関係の一例を示す図である。
【図１６】実施の形態１における描画装置内でのデータ処理の流れを示すフローチャート図である。
【図１７】従来の可変成形型電子線描画装置の動作を説明するための概念図である。
【符号の説明】
【００７９】
１０  チップ
１２  中間データ
２０  ストライプ
３０  ブロック
３２  セル
３４  クラスタ
３６  図形
４０  カットライン
４２  マージン
４４  クラスタ境界
５２，５４，５６  図形
６０  データ量リスト
７０  ルート
７２，８２  ＮＷ
７４，８４  ＮＥ
７６，８６  ＳＷ
７８，８８  ＳＥ
１００  分割領域サイズの取得装置
１１０  制御計算機
１１１  入力部
１１２  マージ処理部
１１４  セル抽出部
１１６  分割部
１１８  図形数見積り部
１２０  図形データ量見積り部
１２２  重心演算部
１２４  図形データ量格納部
１２６，１３４  判定部
１２８  分配部
１３０  ブロックデータ量見積り部
１３２  リスト作成部
１３６  ブロックサイズ縮小部
１３８  出力部
１４０  メモリ
１４２  外部Ｉ／Ｆ
１４４，３１０，３１２，３１６  磁気ディスク装置
３１４  バッファメモリ
３３０  電子線
３４０  試料
４１０  第１のアパーチャ
４２０  第２のアパーチャ
４１１  開口
４２１  可変成形開口
４３０  荷電粒子ソース
【図１】
2010050187.tif 000003
【図２】
2010050187.tif 000004
【図３】
2010050187.tif 000005
【図４】
2010050187.tif 000006
【図５】
2010050187.tif 000007
【図６】
2010050187.tif 000008
【図７】
2010050187.tif 000009
【図８】
2010050187.tif 000010
【図９】
2010050187.tif 000011
【図１０】
2010050187.tif 000012
【図１１】
2010050187.tif 000013
【図１２】
2010050187.tif 000014
【図１３】
2010050187.tif 000015
【図１４】
2010050187.tif 000016
【図１５】
2010050187.tif 000017
【図１６】
2010050187.tif 000018
【図１７】
2010050187.tif 000019