(57)【特許請求の範囲】
【請求項１】
一方向に延在する複数のトラックパターンが前記一方向に交差する交差方向に所定のピッチで配置された複数の基本ブロックパターンを配線領域内で連結して、トラックパターンが連結された複数の平行配線パターンを生成する平行配線パターン生成工程と、
トラックパターンを通る配線経路を、異なる配線経路の経路端部が同じトラックパターン内に配置されないように生成する配線経路の生成工程と、
前記経路端部が配置されたトラックパターンのトラックパターン終端部および当該トラックパターンのトラックパターン始端部に連結された隣接トラックパターンのトラックパターン終端部のうちの前記配線経路が通らないトラックパターン終端部を切り欠く切り欠き工程と、
前記トラックパターン終端部の切り欠き工程の後に、前記配線領域内の前記基本ブロックパターンに対応するブロックパターン識別子と当該基本ブロックパターンの配置位置とを有する配線パターンデータを生成する配線パターンデータの生成工程とを有し、
前記ブロックパターン識別子は、前記基本ブロックパターンに含まれるトラックパターンのトラックパターン終端部を切り欠いて生成される互いに異なる複数の切り欠きブロックパターンおよびトラックパターン終端部が切り欠かれていない前記基本ブロックパターンのいずれかに対応付けられている
配線パターンデータの生成方法。
【請求項２】
請求項１に記載の配線パターンデータの生成方法において、
更に、切り欠かれた前記トラックパターン終端部と前記経路端部との間のダングリング配線長が許容値を超える場合に、当該トラックパターン終端部と前記経路端部の間のダングリング配線中間部を切り欠く工程を有し、
前記配線データの生成工程は、更に、前記ダングリング配線中間部が切り欠かれた前記基本ブロックパターンを前記交差方向に横断し前記ダングリング配線中間部に前記配線経路の反対側から接する第１の端辺と前記第１の端辺に対向し当該基本ブロックパターンに接する第２の端辺とを有する切り取り枠内の部分ブロックパターンを当該基本ブロックパターンから切り取り、切り取られた前記部分ブロックパターンに対応する部分ブロックパターン識別子と当該部分ブロックパターンの位置とを有する配線パターンデータを生成し、
前記部分ブロックパターン識別子は、前記部分ブロックパターンに前記トラックパターン終端部側の領域がマッチングする前記切り欠きブロックパターンに対応していることを
特徴とする配線パターンデータの生成方法。
【請求項３】
請求項２に記載の配線パターンデータの生成方法において、
切り取られる前記トラックパターン中間部は、前記許容値に応じた所定の位置にあることを
特徴とする配線パターンデータの生成方法。
【請求項４】
請求項１乃至３のいずれか１項に記載の配線パターンデータの生成方法において、更に、前記所定のピッチを設計で許される最小ピッチの２倍以上に設定し、
前記配線経路が通っている経路トラックパターンの間および前記経路トラックパターンに接するトラックパターンの間にそれぞれ第１の増設トラックパターンおよび前記第１の増設トラックパターンに接する第２の増設トラックパターンが介在するように、前記基本ブロックパターンを配置する工程と、
前記第１の増設トラックパターンおよび前記第２の増設トラックパターンを通り、前記経路トラックパターンを迂回する迂回経路を生成する工程を有し、
前記切り欠き工程は、更に、前記迂回経路が通る前記第１の増設トラックパターンおよび当該第１の増設トラックパターンに接する前記第２の増設トラックパターンのトラック終端部のうちの前記迂回経路が通らないトラックパターン終端部を切り欠くことを
特徴とする配線パターンデータの生成方法。
【請求項５】
請求項１乃至４のいずれか１項に記載の配線パターンデータの生成方法において、
更に、前記基本ブロックパターンより広く前記配線経路が通らない無効領域内のトラックパターンを削除し、前記基本ブロックパターンより広いダミーパターンを前記無効領域内に配置するダミーパターン配置工程を有し、
前記配線パターンデータの生成工程では、更に、前記ダミーパターンに対応するブロックパターン識別子と当該ダミーパターンの配置位置とを有する配線パターンデータを生成することを
特徴とする配線パターンデータの生成方法。
【請求項６】
請求項１乃至５のいずれか１項に記載の配線パターンデータの生成方法において、
前記平行配線パターンの生成工程は、第１の方向に延在する複数の第１のトラックパターンが第２の方向に前記所定のピッチで配置された複数の第１の基本ブロックパターンを第１の配線パターン形成面内の配線領域内で連結して複数の第１の平行配線パターンを生成し、前記第２の方向に延在する複数の第２のトラックパターンが前記第１の方向に前記所定のピッチで配置された複数の第２の基本ブロックパターンを前記第１の配線パターン形成面に積層される第２の配線パターン形成面内の配線領域で連結して複数の第２の平行配線パターンを生成し、
前記配線経路の生成工程は、更に、前記第１のトラックパターンと前記第２のトラックパターンが交差する格子点に接続ビアパターンを配置して、第１のトラックパターンに配置された第１の経路端部と第２のトラックパターンに配置された第２の経路端部を接続し、
前記配線パターンデータの生成工程は、前記接続ビアパターンが前記格子点に配置されたビアパターン配置面をサブフィールドごとに分割し、分割されたビアパターン配置面のサブフィールドパターンに対応するビアブロックパターン識別子と当該サブフィールドパターンの位置とを有する接続ビアデータを生成することを
特徴とする配線データの生成方法。
【請求項７】
請求項６に記載の配線パターンデータの生成方法において、
前記サブフィールドは、並列配置された所定数のトラックパターン上の格子点を有する領域であり、
前記ビアブロックパターン識別子は、前記サブフィールド内の前記格子点にビアパターンを配置することで生成される互いに異なる複数のビアブロックパターンのいずれかに対応付けられていることを
特徴とする配線パターンデータの生成方法。
【請求項８】
請求項７に記載の配線パターンデータの生成方法において、
前記複数のビアブロックパターンは、トラックパターンごとに所定数以下のビアパターンを有することを
特徴とする配線データの生成方法。
【請求項９】
請求項６乃至８のいずれか１項に記載の配線パターンデータの生成方法において、
前記第１のトラックパターンおよび前記第２のトラックパターンの一方は、前記格子点から突出する突出部を有し、
前記配線経路の生成工程は、前記格子点と当該格子点から突出する突出部に接続ビアパターンを配置し、前記第１の経路端部と前記第２の経路端部を接続ビアパターンで接続することを
特徴とする配線データの生成方法。
【請求項１０】
配線パターンデータの生成方法をコンピュータに実行させるプログラムであって、
前記配線パターンデータの生成方法は、
一方向に延在する複数のトラックパターンが前記一方向に交差する交差方向に所定のピッチで配置された複数の基本ブロックパターンを配線領域内で連結して、トラックパターンが連結された複数の平行配線パターンを生成する平行配線パターン生成工程と、
トラックパターンを通る配線経路を、異なる前記配線経路の経路端部が同じトラックパターン内に配置されないように生成する配線経路の生成工程と、
前記経路端部が配置されたトラックパターンのトラックパターン終端部および当該トラックパターンのトラックパターン始端部に連結された隣接トラックパターンのトラックパターン終端部のうちの前記配線経路が通らないトラックパターン終端部を切り欠く切り欠き工程と、
前記トラックパターン終端部の切り欠き工程の後に、前記配線領域内の前記基本ブロックパターンに対応するブロックパターン識別子と当該基本ブロックパターンの配置位置とを有する配線パターンデータを生成する配線パターンデータの生成工程とを有し、
前記ブロックパターン識別子は、前記基本ブロックパターンに含まれるトラックパターンのトラックパターン終端部を切り欠いて生成される互いに異なる複数の切り欠きブロックパターンおよびトラックパターン終端部が切り欠かれていない前記基本ブロックパターンのいずれかに対応付けられている
配線パターンデータ生成方法プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配線パターンデータの生成方法に関する。
【背景技術】
【０００２】
半導体集積回路（Integrated Circuit; 以下、ICと呼ぶ）の製造工程では、半導体基板上に形成したレジスト膜を露光して、所望のパターン（形状）をレジスト膜に転写する。
【０００３】
レジスト膜の露光方法の一つに、電子ビーム露光法がある。電子ビーム露光法としては、可変矩形ビームでパターンを１つ１つ塗りつぶしていく可変矩形描画(Variable Shaped Beam; VSB)法がよく知られている。しかし、ＶＳＢ法には、露光回数が多くなるため、スループットが低いという問題点がある。
【０００４】
そこで、この問題を解決するために、キャラクタープロジェクション（Character Projection；以下、CPと呼ぶ）法が開発された。ＣＰ法では、ブロックマスクを通して電子ビームをレジスト膜に照射することで、ブロックマスクの開口部の形状（以下、ブロックマスクパターン）をレジスト膜に転写する。従って、１回の電子ビーム露光で所定の領域（例えば、一辺が１μｍの矩形領域）内のパターンが一括形成されるので、スループットが向上する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１２９２６５号公報
【特許文献２】特許第３８８６６９５号公報
【特許文献３】特開２００３−１７３８８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＩＣのレイアウトパターンには、ゲート回路やメモリセル等のセルパターンとセルパターンを接続する配線パターン（複数の配線全体の形状）が含まれている。複数の異なるセルパターンから、共通のパターンを抽出することは容易である。従って、セルパターンから抽出したパターンをブロックマスクパターンとすることで、セルパターンに対するスループットが高くなる。
【０００７】
一方、配線パターンの形状は多様であり、複数の配線パターンから共通のパターンを抽出することは困難である。このため、配線パターンの電子ビーム露光には、ＶＳＢ法が用いられている。
【０００８】
このため、電子ビーム露光法には、配線パターンに対するスループットが低いという問題がある。
【課題を解決するための手段】
【０００９】
上記の問題を解決するために、本方法の一観点によれば、一方向に延在する複数のトラックパターンが前記一方向に交差する交差方向に所定のピッチで配置された複数の基本ブロックパターンを配線領域内で連結して、トラックパターンが連結された複数の平行配線パターンを生成する平行配線パターン生成工程と、トラックパターンを通る配線経路を、異なる配線経路の経路端部が同じトラックパターン内に配置されないように生成する配線経路の生成工程と、前記経路端部が配置されたトラックパターンのトラックパターン終端部および当該トラックパターンのトラックパターン始端部に連結された隣接トラックパターンのトラックパターン終端部のうちの前記配線経路が通らないトラックパターン終端部を切り欠く切り欠き工程と、前記トラックパターン終端部の切り欠き工程の後に、前記配線領域内の前記基本ブロックパターンに対応するブロックパターン識別子と当該基本ブロックパターンの配置位置とを有する配線パターンデータを生成する配線パターンデータの生成工程とを有し、前記ブロックパターン識別子は、前記基本ブロックパターンに含まれるトラックパターンのトラックパターン終端部を切り欠いて生成される互いに異なる複数の切り欠きブロックパターンおよびトラックパターン終端部が切り欠かれていない前記基本ブロックパターンのいずれかに対応付けられている配線パターンデータの生成方法が提供される。 
【発明の効果】
【００１０】
本実施の形態によれば、配線パターンに対する電子ビーム露光のスループットが高くなる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１で生成される配線パターンデータを用いて、配線パターンをレジスト膜に描画する電子ビーム露光装置の構成図である。
【図２】ブロックマスクの平面図である。
【図３】ブロックエリアの平面図である。
【図４】実施の形態１の配線パターンデータの生成方法を実行する配線パターンデータ生成装置の構成図である。
【図５】実施の形態1の配線パターンデータの生成方法のフローチャートである。
【図６】平行配線パターンの生成工程により生成される複数の平行配線パターンの一例である。
【図７】配線領域に配置される基本ブロックパターンの一例である。
【図８】第２の平行配線パターンの一例である。
【図９】配線経路の生成工程のフローチャートである。
【図１０】配線経路の生成工程を説明するパターン図である。
【図１１】配線経路の生成工程を説明するパターン図である。
【図１２】接続ビアパターンの配置位置を説明する図である。
【図１３】トラックパターン終端部の切り欠き工程を説明する図である。
【図１４】トラックパターン終端部の切り欠き工程を説明する図である。
【図１５】ブロックパターン識別子を説明する図である。
【図１６】配線パターンデータのデータ構造を示す図である。
【図１７】実施の形態２の配線パターンの生成方法のフローチャートである。
【図１８】ダングリング配線長の短縮工程のフローチャートである。
【図１９】ダングリング配線長の短縮工程を説明するパターン図である。
【図２０】ダングリング配線長の短縮工程を説明するパターン図である。
【図２１】実施の形態２の配線データの生成工程を説明するパターン図である。
【図２２】実施の形態２の配線データの生成工程を説明するパターン図である。
【図２３】実施の形態２の配線パターンデータの一例である。
【図２４】実施の形態３の配線経路の生成工程のフローチャートである。
【図２５】トラック増設および迂回経路探索工程のフローチャートである。
【図２６】トラック増設および迂回経路探索工程を説明するパターン図である。
【図２７】トラック増設および迂回経路探索工程を説明するパターン図である。
【図２８】実施の形態４の配線パターンの生成方法を説明するパターン図である。
【図２９】ダミーパターンを説明するパターン図である。
【図３０】論理ゲートの外部接続端子とトラックパターンの関係を説明する図である。
【図３１】実施の形態５の接続ビアデータの生成方法を説明するパターン図である。
【図３２】接続ビアデータのデータ構造を示す図である。
【図３３】実施の形態６の配線経路の生成工程を説明するパターン図である。
【図３４】実施の形態６の配線経路の生成工程を説明するパターン図である。
【発明を実施するための形態】
【００１２】
以下、図面にしたがって本発明の実施の形態について説明する。但し、本発明の技術的範囲はこれらの実施の形態に限定されず、特許請求の範囲に記載された事項とその均等物まで及ぶものである。尚、図面が異なっても対応する部分には同一符号を付し、その説明を省略する。
【００１３】
（実施の形態１）
図１は、本実施の形態で生成する配線パターンデータに基づいて、配線パターン（複数の配線全体の形状）をレジスト膜１４に描画する電子ビーム露光装置２の構成図である。
【００１４】
図１に示すように、本実施の形態の電子ビーム露光装置２は、電子銃４、コリメート磁気レンズ６ａ、第１のアパーチャ８ａ、第１の偏向器１０ａ、第２のアパーチャ８ｂ、および第２の偏向器１０ｂを有している。第１のアパーチャ８ａおよび第２のアパーチャ８ｂの開口部の形状は、矩形である。
【００１５】
更に、電子ビーム露光装置２は、ブロックマスク１２、フォーカシング磁気レンズ６ｂ、第３の偏向器１０ｃ、および可動ステージ１８を有している。可動ステージ１８には、レジスト膜１４が形成された半導体基板１６が載置される。
【００１６】
電子銃４から放射された電子ビーム２０は、コリメート磁気レンズ６ａにより平行ビームに変換される。平行ビームに変換された電子ビーム２０は、第１のアパーチャ８ａ、第１の偏向器１０ａ、および第２のアパーチャ８ｂにより、ブロックマスクパターンと同程度のサイズを有する矩形ビームに成形される。矩形ビームの一辺は、例えば１.０〜１.５μｍである。
【００１７】
その後、電子ビーム２０は、第２の偏向器１０ｂにより、ブロックマスク１２に設けられたブロック（所定の形状を有する開口部が設けられた領域）に照射される。ブロックマスク１２を透過した電子ビーム２０はフォーカシング磁気レンズ６ｂと第３の偏向器１０ｃにより、レジスト膜１４の所定の領域に結像される。これにより、ブロックマスクパターンがレジスト膜１４に転写される。
【００１８】
この露光プロセスの繰り返しにより、ＩＣレイアウトパターンの大部分がレジスト膜１４に転写される。ブロックマスクパターンの転写で形成できない部分は、ＶＳＢ法により描画される。
【００１９】
電子ビーム露光装置２による露光工程は、露光制御装置（図示せず）により制御される。露光工程の制御は、記録媒体（図示せず）に記録された露光データに基づいて行われる。露光データは、ＩＣレイアウトデータに基づいて生成される。このＩＣレイアウトデータは、本実施の形態で生成する配線パターンデータおよび接続ビアデータを有している。
【００２０】
レジスト膜１４は、例えばポジ型レジストである。ポジ型レジスト膜に転写される配線パターンは、ダマシン法による配線形成に適している。一方、ネガ型レジスト膜に転写される配線パターンは、非ダマシン法による配線形成に適している。したがって、非ダマシン法による配線形成では、レジスト膜１４としてネガ型レジスト膜が用いられる。
【００２１】
図２は、ブロックマスク１２の平面図である。ブロックマスク１２の平面形状は、例えば１辺が５ｃｍ程度の正方形である。図２に示すように、ブロックマスク１２には、複数のブロックエリア２２が設けられている。図３は、ブロックエリア２２の平面図である。
【００２２】
ブロックエリア２２は、例えば対角線が４.４ｍｍ程度の矩形領域である。ブロックエリア２２の中心部には、図３に示すように、複数のブロック２４が設けられている。ブロック２４は、例えば一辺が１.０μｍ×１.０μｍ程度の矩形領域である。ブロック２４には、露光パターンに対応する開口部が設けられている。
【００２３】
各ブロックエリア２２には、ＩＣレイアウトパターンが有する層（例えば、ゲート層、配線層、ビア層）ごとに、それぞれの層の描画に用いられるブロックが設けられる。各ブロックエリア２２には、例えば４０００個程度のブロック２４が設けられる。ブロックエリア２２の四隅には、矩形スリット２６が設けられる。この矩形スリット２６は、露光位置の位置合わせおよびＶＳＢ法による可変矩形パターンの生成に用いられる。
【００２４】
図４は、本実施の形態の配線パターンデータの生成方法を実行するコンピュータ２８の構成図である。図４に示すように、コンピュータ２８は、ＣＰＵ（Central Processing Unit）２８ａ、ＲＯＭ（Read Only Memory）２８ｂ、およびＲＡＭ（Random Access Memory）２８ｃを有している。更に、コンピュータ２８は、第１のＨＤＤ（Hard Disk Drive）２８ｄ、第２のＨＤＤ２８ｅ、ＧＢ（Graphics Board）２８ｆ、Ｉ／Ｆ（Interface）２８ｇ、バス２８ｈ、入力装置２８ｉ、および表示装置２８ｊを有している。
【００２５】
ＣＰＵ２８ａは、コンピュータ２８の各ハードウエアを制御するプロセッサである。ＣＰＵ２８ａは、第１のハードディスク２８ｄに記録されたプログラムをＲＡＭ２８ｃにロードし、ロードされたプログラムを実行する。
【００２６】
第１のハードディスク２８ｄには、本実施の形態の配線パターンデータの生成方法をコンピュータ２８に実行させる配線パターンデータ生成プログラム３０が記録されている。この配線パターンデータ生成プログラム３０を実行することで、コンピュータ２８は配線パターンデータ生成装置になる。第１のハードディスク２８ｄには、論理合成プログラム（図示せず）や配置配線プログラム（Position & Route プログラム）３１など配線パターンデータ生成プログラム３０を支援するプログラムも記録されている。
【００２７】
ＲＯＭ２８ｂには、ＣＰＵ２８ａが実行する基本的なプログラム等が記録されている。ＲＡＭ２８ｃには、プログラム以外にも、ＣＰＵ２８ａが各種演算処理を実行する際に、演算途中のデータが一時的に記録される。
【００２８】
第２のハードディスク２８ｅには、後述するブロックパターン・データベース３２とスタンダードセル・ライブラリ３４が記録されている。スタンダードセル・ライブラリ３４には、スタンダードセル（標準的な機能を有する回路）の機能やスタンダードセルのセルパターン（回路パターン）が記録されている。
【００２９】
ＧＢ２８ｆは、ＣＰＵ２８ａから受け取った命令に従って描画処理を実行し、得られた画像データを映像信号に変換して表示装置２８ｊ供給する。Ｉ／Ｆ２８ｇは、入力装置２８ｉに入力されたデータの表現形式を変更してＣＰＵ２８ａ等に送出する。
【００３０】
バス２８ｈには、ＣＰＵ２８ａ、ＲＯＭ２８ｂ、ＲＡＭ２８ｃ、第１のＨＤＤ２８ｄ、第２のＨＤＤ２８ｅ、ＧＢ２８ｆ、およびＩ／Ｆ２８ｇが接続されている。これらハードウエアの間のデータの受け渡しは、バス２８ｈを介して行われえる。
【００３１】
表示装置２８ｊは、例えばＬＣＤ（Liquid Crystal Display）モニタであり、ＧＢ２８ｆが供給する映像信号を表示する。入力装置２８ｉは、例えばキーボードやマウスを有しており、ユーザの操作に応じてデータを生成して、Ｉ／Ｆ（Interface）２８ｇに供給する。
【００３２】
ＲＡＭ２８ｃにロードされた論理合成プログラム（図示せず）が起動されると、コンピュータ２８は、ＩＣの仕様を論理式で記述する。更に、コンピュータ２８は、記述された論理式をネットリストに変換する。
【００３３】
配置配線プログラム３１が起動されると、コンピュータ２８は、ネットリストにしたがって、スタンダードセル・ライブラリ３４に登録されたセルパターンをセルパターン配置面に配置する。
【００３４】
スタンダードセル・ライブラリ３４には、論理ゲート、メモリセル、および周辺回路などのセルパターン（回路パターン）が登録されている。セルパターンは、複数のパターン層が積層された立体構造を有している。
【００３５】
一つ論理ゲートの層数は少数である。従って、論理ゲートに対するセルパターンは、略全てセルパターン専用のセルパターン配置面（ゲート層）に配置することができる。
【００３６】
一方、メモリや周辺器回路の層数は多数である。このため、メモリや周辺器回路のセルパターンの一部は、配線パターン形成面（配線層）にも配置される。
【００３７】
コンピュータ２８は、メモリや周辺器回路のセルパターンが配置される領域を避けて、配線パターン形成面に配線領域を設定する。この配線領域に、配線パターンが形成される。
【００３８】
その後、配線データ生成プログラム３０が起動され、コンピュータ２８は、本実施の形態の配線パターンデータの生成方法を実行する。
【００３９】
図５は、本実施の形態の配線パターンデータの生成方法のフローチャートである。図５に示すように、配線パターンデータの生成方法は、平行配線パターンの生成工程（Ｓ２）、配線経路の生成工程（Ｓ４）、トラックパターン終端部の切り欠き工程（Ｓ６）、接続完了判定工程（Ｓ８）、および配線パターンデータの生成工程（Ｓ１０）を有している。
【００４０】
―平行配線パターンの生成工程（Ｓ２）―
図６は、平行配線パターンの生成工程（Ｓ２）により生成される複数の平行配線パターン３６の一例である。図７は、配線領域３８に配置される基本ブロックパターン４０の一例である。
【００４１】
基本ブロックパターン４０は、図７に示すように、一方向４２に延在する複数のトラックパターン（ストライプ状のパターン）４４を有している。これらのトラックパターン４４は、一方向４２に交差（好ましくは、直交）する交差方向４６に所定のピッチＰで配置されている。尚、破線４８は、基本ブロックパターン４０の外縁を示している。
【００４２】
コンピュータ２８は、図６に示すように、これら複数の基本ブロックパターン４０を配線パターン形成面３７内の配線領域３８内で連結して、トラックパターン４４が連結された複数の平行配線パターン３６を生成する。更に、コンピュータ２８は、配線パターン形成面３７（以下、第１の配線パターン形成面と呼ぶ）に積層される第２の配線パターン形成面にも複数の第２の平行配線パターンを生成する。第１の配線パターン形成面および第２の配線パターン形成面は、それぞれＩＣが有する立体配線の下部配線層および上部配線層に対応している。
【００４３】
以下、第１の配線パターン形成面に生成される平行配線パターン３７ａを、第１の平行配線パターンと呼ぶ。第１の配線パターン形成面３７ａに設けられる配線領域を、第１の配線領域と呼ぶ。また、第１の配線領域３８ａ内で連結される基本ブロックパターンを、第１の基本ブロックパターンと呼ぶ。第１の基本ブロックパターンが有するトラックパターンを、第１のトラックパターンと呼ぶ。
【００４４】
図８は、第２の平行配線パターンの一例である。コンピュータ２８は、図８に示すように、第２の基本ブロックパターン４０ｂを、第２の配線パターン形成面３７ｂ内の第２の配線領域３８ｂで連結して、複数の第２の平行配線パターン３６ｂを生成する。
【００４５】
第１の配線領域３８ａおよび第２の配線領域３８ｂは、好ましくは同一の形状および同一のサイズを有し、第１の配線パターン形成面３８ａおよび第２の配線パターン形成面３８ｂ内の同じ位置に配置される。
【００４６】
図６に示すように、第１の基本ブロックパターン４０ａには、第１の方向５０に延在する複数の第１のトラックパターン４４ａが第２の方向（好ましくは、第１の方向に直交する方向）５２に所定のピッチＰで配置されている。一方、第２の基本ブロックパターン４０ｂには、第２の方向５２に延在する複数の第２のトラックパターン４４ｂが第１の方向５０に所定のピッチＰで配置されている。
【００４７】
ところで、コンピュータ２８は、トラックパターン４４および基本ブロックパターン４０を図形データとして取り扱う。例えば、トラックパターン４４は、その頂点座標の集まりとして取り扱われる。したがって、基本ブロックパターン４０は、それぞれのトラックパターンに対応する複数の頂点座標の集まりとして取り扱われる。
【００４８】
今、図７に示すように、基本ブロックパターン４０の左下の頂点座標Ｏを原点（０ｎｍ，０ｎｍ）とする。また、トラックパターン４４の長さおよび幅を、それぞれ１μｍおよび２８ｎｍとする。また、トラックパターンのピッチＰを、１１２ｎｍ（＝２８ｎｍ×４）とする。
【００４９】
この場合、一番下のトラックパターン４４Ａは、４つの頂点座標、ａ１（０ｎｍ，４２ｎｍ）、ａ２（１，０００ｎｍ，４２ｎｍ）、ａ３（１，０００ｎｍ，７０ｎｍ）、およびａ４（０ｎｍ，７０ｎｍ）の集まりとして取り扱われる。下から２番目のトラックパターン４４Ｂの図形データは、４つの頂点座標、（０ｎｍ，１５４ｎｍ）、（１，０００ｎｍ，１５４ｎｍ）、（１，０００ｎｍ，１８２ｎｍ）、および（０ｎｍ，１８２ｎｍ）の集まりとして取り扱われる。
【００５０】
基本ブロックパターン４０は、このような４つの頂点座標の集まりとして取り扱われる。トラックパターンおよび基本ブロックパターンに対する処理（配置、切り欠き、切り取り）は、このような画像データに対して実行される。
【００５１】
―配線経路の生成工程（Ｓ４）―
図９は、配線経路の生成工程（Ｓ４）のフローチャートである。図１０及び１１は、配線経路の生成工程を説明するパターン図である。
【００５２】
図１０には、第１の配線領域３８ａに生成される第１の配線経路５４ａが示されている。図１１には、第２の配線領域３８ｂに生成される第２の配線経路５４ｂが示されている。
【００５３】
図９に示すように、配線経路の生成工程（Ｓ４）は、検索対象端子の設定工程（Ｓ１２）、接続経路の探索工程（Ｓ１４）、経路探索の成否判定工程（Ｓ１６）、および経路未確定フラグオン工程（Ｓ１８）を有している。
【００５４】
―検索対象端子の設定工程（Ｓ１２）―
コンピュータ２８は、セルパターンをセルパターン配置面および／または配線パターン形成面に配置する際、セルパターンの外部端子パターン（又は、この外部端子パターンにビアパターンを介して接続されたビア端子パターン）を配線パターン形成面に配置する。これらの端子パターン（外部端子パターン、ビア端子パターン）は、例えばＶＳＢ法で配線領域外に形成される配線パターンにより平行配線パターン３６ａ,３６ｂの端部に接続される。或いは、これらの端子パターンは、平行配線パターン３６ａ,３６ｂ内に直接設けられる。
【００５５】
コンピュータ２８は、配線領域外の配線パターンと平行配線パターン３６ａ,３６ｂの接続点および平行配線パターン３６ａ,３６ｂに直接設けられる端子パターンから、複数の端子パターン５６ａ,５６ｂ（以下、検索対象端子点と呼ぶ）を順次選択する。検索対象端子点の選択は、ネットリストに定められた端子間の接続に基づいて行われる。
【００５６】
図１０では、第１の配線領域３８ａの左端に配置された第１のトラックパターン４４ａの一端に設けられた接続点が、第１の検索対象端子点５６ａとして選択されている。また、図１１では、第２の配線領域３８ｂの下端に配置された第２のトラックパターン４４ｂの一端に設けられた接続点が、第２の検索対象端子点５６ｂとして選択されている。
【００５７】
検索対象端子の設定工程（Ｓ１２）については、実施の形態４でより具体的に説明する。
【００５８】
―接続経路の探索工程（Ｓ１４）―
次に、コンピュータ２８は、選択された検索対象端子点５６ａ,５６ｂを、トラックパターン４４ａ,４４ｂを通って接続する接続経路６０を探索する。この時、コンピュータ２８は、接続経路６０の一部または全部として、図１０及び１１に示すように、トラックパターン４４ａ,４４ｂを通る配線経路(配線パターン内経路）５４ａ,５４ｂを生成する。
【００５９】
例えば、第１の検索対象端子点５６ａに接続された第１の配線経路５４ａ（図１０）と、第２の検索対象端子点５６ｂに接続された第２の配線経路５４ｂ（図１１）が生成される。接続経路の探索は、配置配線プログラムが備えている経路探索ツールと略同じ手順で実行される。
【００６０】
配線経路を生成する時、コンピュータ２８は、異なる配線経路（例えば、第１の配線経路５４ａと第３の配線経路５４ｃ）の経路端部が同じトラックパターン内に配置されないように、配線経路５４ａ,５４ｂを生成する。
【００６１】
尚、図１０には、参考のため、第２の配線経路５４ｂが破線で示されている。同様に、図１１には、第１の配線経路５４ａが破線で示されている。
【００６２】
コンピュータ２８は、検索対象端子点を接続する接続経路の探索に成功すると、配線経路の生成工程を終了する（Ｓ１７）。一方、接続経路の探索に失敗すると、経路未確定フラグをＯＮにして配線データの生成を中止する（Ｓ１９）。
【００６３】
図１０及び１１に示すように、接続経路６０が複数の配線パターン形成面に跨る場合には、コンピュータ２８は、第１の配線経路５４ａの第１の経路端部５８ａと第２の配線経路５４ｂの第２の経路端部５８ｂを接続する接続ビアパターンを生成する。
【００６４】
図１２は、接続ビアパターンの配置位置を説明する図である。第１の配線パターン形成面３７ａ及び第２の配線パターン形成面３７ｂは、それぞれ立体配線の下部配線層および上部配線層に対応している。したがって、第１の配線パターン形成面内の位置と第２の配線パターン形成面内の位置は一対一に対応している。
【００６５】
各配線パターン形成面内の対応する位置同士が重なるように、第１の配線パターン形成面３７ａと第２の配線パターン形成面３７ｂを重ねると、第１のトラックパターン４４ａと第２のトラックパターン４４ｂが交差する複数の格子点６２が生成される。第１の経路端部５８ａと第２の経路端部５８ｂを接続する接続ビアは、これら複数の格子点６２のいずれかに配置される。
【００６６】
ところで、格子点６２は、第１の配線パターン形成面３７ａ、第２の配線パターン形成面３７ｂ、および第１の配線パターン形成面３７ａと第２の配線パターン形成面３７ｂの間に配置されるビアパターン配置面それぞれに存在する。
【００６７】
このビアパターン配置面内の格子点に、接続ビアパターンは配置される。格子点に接続ビアが配置されたビアパターン配置面が、ＩＣレイアウトパターンのビア層パターンである。
【００６８】
以上の例では、接続経路６０は複数の配線経路を有している。しかし、検索対象端子点５６ａ,５６ｂが一つの平行配線パターン上に設けられる場合には、検索対象端子点間の接続経路と配線経路は一致する。
【００６９】
―トラックパターン終端部の切り欠き工程（Ｓ６）―
図１３及び１４は、トラックパターン終端部の切り欠き工程を説明する図である。図１３には、経路端部５８が配置された基本ブロックパターン４０ｃが示されている。この基本ブロックパターン４０ｃは、図１０に示す基本ブロックパターン４０Ｃに対応している。
【００７０】
図１４には、経路端部５８が配置された基本ブロックパターン４０ｄとこの基本ブロックパターン４０ｄに隣接する基本ブロックパターン４０ｅが示されている。図１３の基本ブロックパターン４０ｃでは、配線経路５４がトラックパターン始端部６６ａを通っている。一方、図１４の基本ブロックパターン４０ｄでは、配線経路５４がトラックパターン終端部６４ｂを通っている。図１４の基本ブロックパターン４０ｄは、図１０の右下端の基本ブロックパターン４０Ｄに対応している。尚、トラックパターン始端部とは、トラックパターンが延在する方向（延在方向）の起点側のトラックパターン端部である。トラックパターン終端部とは、トラックパターンの延在方向の終点側に位置するトラックパターン端部である。
【００７１】
コンピュータ２８は、図１３及び１４に示すように、経路端部５８が配置されたトラックパターン４４ｃ,４４ｄのトラックパターン終端部６４ａ,６４ｂのうちの配線経路５４が通らないトラックパターン終端部６４ａを切り欠く。経路端部５８は、例えば図１０及び１１示す第１の経路端部５８ａおよび第２の経路端部５８ｂである。配線経路５４は、例えば図１０及び１１示す第１の経路５４ａおよび第２の５４ｂである。切り欠く部分の幅は、例えば、トラックパターン４４ｃの幅である。
【００７２】
或いは、コンピュータ２８は、図１４に示すように、経路端部５８が配置されたトラックパターン４４ｄのトラックパターン始端部６６ｂに連結された隣接トラックパターン４４ｅのトラックパターン終端部のうちの配線経路５４が通らないトラックパターン終端部６４ｃを切り欠く。
【００７３】
図１３及び１４には、一方向（例えば、第１の方向５０）に延在するトラックパターンに関する切り欠き工程（Ｓ６）の説明図である。この一方向とは異なる方向（例えば、第２の方向５２）に延在するトラックパターンに対しても、同様の工程が行われる。以下の工程においても、同じである。
【００７４】
これらのトラックパターン終端部の切り欠き処理により、配線経路５４ａ,５４ｂが通るトラックパターンは、配線経路５４ａ,５４ｂが通らないトラックパターン（以下、非通トラックパターンと呼ぶ）から分離される。その結果、接続経路６０は、非通トラックパターンから分離される。これにより、検索対象端子点５６ａ,５６ｂを接続する配線パターンが生成される。
【００７５】
―接続完了判定工程（Ｓ８）―
ネットリストには、所定の端子（例えば、セルパターンの外部端子）が接続されるように定められている。コンピュータ２８は、この所定の端子が一または複数の配線経路（配線パターン内経路）を介して接続されるように、配線経路の生成工程（Ｓ４）およびトラックパターン終端部の切り欠き工程（Ｓ６）を実行する。
【００７６】
この際、コンピュータ２８は、トラックパターン終端部の切り欠き工程（Ｓ６）が終了するたびに、新たに配線経路５４が通ったトラックパターンの占有フラッグをＯＮにする。占有フラッグは、接続経路の探索工程（Ｓ１４）で接続経路を探索する際に、未使用のトラックパターン（別の配線経路が通っていないトラックパターン）を検出するために用いられる。
【００７７】
図５に示すように、コンピュータ２８は、ネットリストに定められた未接続の端子があると判断すると、未接続の端子に対して、配線経路の生成工程（Ｓ４）およびトラックパターン終端部の切り欠き工程（Ｓ６）を実行する（Ｓ８→Ｓ４→Ｓ６）。一方、コンピュータ２８は、ネットリストに定められた所定の端子全てに対する接続が完了したと判断すると、配線パターンデータの生成工程（Ｓ１０）に進む（Ｓ８→Ｓ１０）。
【００７８】
―配線パターンデータの生成工程（Ｓ１０）―
次に、コンピュータ２８は、配線領域内（３８ａ,３８ｂ）の各基本ブロックパターンに対応するブロックパターン識別子と各基本ブロックパターンの配置位置とを有する配線パターンデータを生成する（Ｓ１０）。
【００７９】
図１５は、ブロックパターン識別子を説明する図である。図１６は、配線パターンデータ７４のデータ構造を示す図である。
【００８０】
ブロックパターン・データベース３２には、後述する欠きブロックパターン６８とそのブロックパターン識別子が、対応付けられて記録されている。更に、ブロックパターン・データベース３２（図４参照）には、トラックパターン終端部が切り欠かれていない基本ブロックパターン（図７）とそのブロックパターン識別子が、対応付けられて記録されている。すなわち、ブロックパターン識別子は、互いに異なる複数の切り欠きブロックパターン６８およびトラックパターン終端部が切り欠かれていない基本ブロックパターンのいずれかに対応付けられている。
【００８１】
切り欠きブロックパターンは、例えば図１５（ａ）〜（ｃ）に示すように、基本ブロックパターン４０に含まれるトラックパターン４４のトラックパターン終端部６４を切り欠いて生成される互いに異なる複数の切りブロックパターンである。
【００８２】
尚、図１５には、一方向（例えば、第１の方向５０）に延在するトラックパターンを有する切り欠きブロックパターンが示されている。この一方向とは異なる方向（例えば、第２の方向５２）に延在するトラックパターンを有する切り欠きブロックパターンも、同様に生成される。
【００８３】
コンピュータ２８は、トラックパターン終端部の切り欠き工程（Ｓ６）後に、ブロックパターン・データベース３２から、配線領域３８ａ,３８ｂ内の各基本ブロックパターンに対応するブロックパターン識別子７０を抽出する。この時、各基本ブロックパターンにマッチングする切り欠きパターン６８のブロックパターン識別子７０が抽出される。次に、コンピュータ２８は、抽出したブロックパターン識別子７０と基本ブロックパターンの配置位置とを有する配線パターンデータ７４を生成する（Ｓ１０）。
【００８４】
尚、基本ブロックパターンの配置位置は、例えば基本ブロックパターンの左下の頂点座標で表される。抽出されるブロックパターン識別子７０には、パターン終端部が切り欠かれていない基本ブロックパターンのブロックパターン識別子も含まれる。
【００８５】
図１６に示す例では、ブロックパターン識別子７０と配線領域内の基本ブロックパターンの配置位置７２を有するレコードが、第１配線層セル（ディレクトリ）に記録される。
【００８６】
更に、コンピュータ２８は、接続ビアパターンが格子点に配置されたビアパターン配置面（ビア層パターン）をサブフィールドごとに分割し、分割されたビアパターン配置面のパターン（以下、サブフィールドパターンと呼ぶ）に対応するビアブロックパターン識別子とこのサブフィールドパターンの位置とを有する接続ビアデータを生成する。接続ビアデータについては、実施の形態５で詳しく説明する。
【００８７】
配線パターンデータおよび接続ビアデータは、ＩＣレイアウトデータの一部として例えば第１のＨＤＤ２８ｄに記録される。ＩＣレイアウトデータには、セルパターンデータも格納される。ＩＣレイアウトデータおよび接続ビアデータについては、実施の形態５で詳しく説明する。
【００８８】
ところで、図１５に示す切り欠きブロックパターン６８に含まれるトラックパターンは、５本である。したがって、図１５の切り欠きブロックパターン６８には、３１通り（＝２５−１）のバリエーションが存在する。この程度のバリエーションに対ｚするブロックを、ブロックエリア２２（図３参照）を設けることは容易である。
【００８９】
トラックパターンの数が増えると、切り欠きブロックパターンのバリエーションも増える。例えば、トラックパターンが１２本の場合、切り欠きブロックパターンのバリエーション数は４０９５通り（＝２１２−１）である。標準的なブロックエリア２２に含まるブロック数は４，０００程度なので、トラックパターンが１２本に増えても切り欠きブロックパターンに対するブロックを全てブロックエリア２２に設けることは容易である。
【００９０】
そこで、本実施の形態では、切り欠きブロックパターン６８と同一形状の開口部を有するブロックをブロックマスクエリア２２に設け、各ブロックのブロック識別子として、ブロックパターン識別子７０を用いる。
【００９１】
すると、配線パターンデータ７４が、ブロック識別子とブロックの露光位置を有する露光データになる。従って、配線パターンデータ７４を用いて電子ビーム露光を行うとことで、配線領域３８ａ,３８ｂ内の配線パターンがレジスト膜１４に転写される。同様に、接続ビアデータを露光データとして用いことで、ビア層パターンがレジスト膜１４に転写される。
【００９２】
このように本実施の形態では、切り欠きブロックパターン６８および／または基本ブロックパターン４０を一括露光することで、配線パターンをレジスト膜１４に転写する。したがって、本実施の形態によれば、配線パターンに対する電子ビーム露光のスループットが高くなる。
【００９３】
尚、図１０及び１１に示す接続経路６０は、２つの検索対象端子点を接続する経路である。しかし、接続経路６０は、３つ以上の検索対象端子点を接続する経路であってもよい。
【００９４】
（実施の形態２）
図１７は、本実施の形態の配線データの生成方法のフローチャートである。
【００９５】
図１７に示すように、本実施の形態の配線データの生成方法は、図５を参照して説明した実施の形態１の「トラックパターン終端部の切り欠き工程（Ｓ６）」と「接続完了判定工程（Ｓ８）」の間に、「ダングリング配線長の調整工程（Ｓ２０）」を有している。そして、「配線パターンデータの生成工程（Ｓ１０Ａ）」では、ダングリング配線長が調整された配線パターンに対して配線パターンデータが生成される。尚、実施の形態１と共通する部分については、説明を省略する。
【００９６】
―ダングリング配線長の調整工程（Ｓ２０）―
図１８は、ダングリング配線長の調整工程（Ｓ２０）のフローチャートである。図１９及び２０は、ダングリング配線長の調整工程（Ｓ２０）を説明するパターン図である。
【００９７】
コンピュータ２８は、「トラックパターン終端部の切り欠き工程（Ｓ６）」の実行後、図１９に示すように、切り欠かれたトラックパターン終端部６４ａとこのトラックパターン終端部６４ａに対応する経路端部５８との間のダングリング配線長Ｌｄ０が許容値（例えば、トラックパターン長の半分）を超えるかを判定する（Ｓ２２）。ダングリング配線長Ｌｄ０の許容値は、トラックパターン終端部で発生する反射波の大きさ等により定められる。
【００９８】
ダングリング配線長Ｌｄ０が許容値以下の場合、コンピュータ２８は、ダングリング配線長の調整工程（Ｓ２０）を終了する（Ｓ２６）。ダングリング配線長Ｌｄ０が許容値を超える場合には、図２０に示すように、トラックパターン終端部６４ａと経路端部５８の間のダングリング配線中間部７６を切り欠く（Ｓ２４）。
【００９９】
この時、切り欠かれる部分７７と経路端部５８の間のダングリング配線長Ｌｄ１が許容値以下になるように、ダングリング配線中間部（例えば、トラックパターン４４の中央部）７６が切り欠かれる。
【０１００】
―配線データの生成工程（Ｓ１０Ａ）―
図２１及び２２は、配線データの生成工程（Ｓ１０Ａ）を説明するパターン図である。コンピュータ２８は、まず図２１に示すように、ダングリング配線中間部７６が切り欠かれた基本ブロックパターン４０ｆから切り取り枠７８内のパターン（以下、部分ブロックパターンと呼ぶ）を切り取る。
【０１０１】
図２１に示すように、切り取り枠７８は、第１の端辺８０ａと第１の端辺８０ａに対向する第２の端辺８０ｂとを有している。第１の端辺８０ａは、基本ブロックパターン４０ｆをその交差方向４６（図７参照）に横断し、切り欠かれたダングリング配線中間部７６に配線経路５４の反対側から接する辺である。第２の端辺８０ｂは、第１の端辺８０ａに対向し基本ブロックパターン４０ｆに接する辺である。
【０１０２】
図２２（ａ）には、基本ブロックパターン４０ｆから切り取られた部分ブロックパターン８６の一例が示されている。図２２（ｂ）には、この部分ブロックパターン８６に対応する切り欠きブロックパターン６８ａが示されている。
【０１０３】
図２２（ａ）の部分ブロックパターン８６は、図２２（ｂ）に示す切り欠きブロックパターン６８ａのブロックパターン終端部６４側の領域８２（以下、終端部側領域と呼ぶ）にマッチングしている。このように、部分ブロックパターン８６は、いずれかの切り欠きブロックパターン６８ａの終端部側領域８２にマッチングする。
【０１０４】
そこで、「配線データの生成工程（Ｓ１０Ａ）」では、切り取られた部分ブロックパターン８６及びこの部分ブロックパターン８６に終端部側領域８２がマッチングする切り欠きブロックパターンの双方に対応する部分ブロックパターン識別子を用いて、配線パターンデータを生成する。
【０１０５】
図２３は、本実施の形態の配線パターンデータ７４ａの一例である。配線パターンデータ７４ａは、実施の形態１の配線パターンデータ７４（図１６）と同様に、配線領域３８内の基本ブロックパターンに対応するブロックパターン識別子７０とこの基本ブロックパターンの配置位置７２を有している。
【０１０６】
配線パターンデータ７４ａは、更に、部分ブロックパターン８６に対応する部分ブロックパターン識別子７０ａと部分ブロックパターン８６の配置位置７２ａとを有している。
【０１０７】
部分ブロックパターン識別子７０ａは、部分ブロックパターン８６および部分ブロックパターン８６に終端部側領域８２がマッチングする切り欠きブロックパターンに対応している。例えば、部分ブロックパターン識別子「ＣＰ２＿ＨＤ］は、図２２（ａ）に示す部分ブロックパターン８６および図２２（ｂ）に示す切り欠きブロックパターン６８ａに対応している。
【０１０８】
コンピュータ２８は、ブロックパターン・データベース３２を検索して、部分ブロックパターン８６に終端部側領域８２がマッチングする切り欠きブロックパターン６８ａを検出する。更に、コンピュータ２８は、検出した切り欠きブロックパターン６８ａのブロックパターン識別子ＣＰ２を抽出し、抽出したブロックパターン識別子の末尾に付加記号「＿ＨＤ］を付加する。これにより、部分ブロックパターン識別子が生成される。生成された部分ブロックパターン識別子に対応する切り欠きブロックパターン識別子は、部分ブロックパターン識別子から付加記号「＿ＨＤ］を削除することで容易に得られる。
【０１０９】
本実施の形態の配線データを用いる電子ビーム露光では、部分ブロックパターン識別子７０ａに対応する切り欠きブロックパターン６８ａに切り取り枠７８に対応する矩形ビームが照射されて、部分ブロックパターン８６がレジスト膜１４に転写される。
【０１１０】
この時、矩形ビームに照射される領域は、切り欠きブロックパターン６８ａの終端部側領域８２である。同様に、切り取り枠７８外の領域８４（図２１参照）も、切り欠きブロックパターン６８ａに矩形ビームが照射されることで、レジスト膜１４に転写される。
【０１１１】
図２０および２１に示す例では、切り取られるダングリング配線中間部７６は、トラックパターン４４の中央に位置している。しかし、ダングリング配線中間部７６の位置は、トラックパターン４４の中央に限られない。例えば、ダングリング配線長の許容値がトラックパターン長の１／４の場合には、切り取られるダングリング配線中間部７６の位置としては、トラックパターンを４等分する３つの位置が好ましい。
【０１１２】
このように、切り取られるトラックパターン中間部７６は、許容値に応じた所定の位置に設定することが好ましい。このように切り取られるトラックパターン中間部７６の位置を限定することで、部分ブロックパターンのバリエーション数が少なくなる。
【０１１３】
尚、以上の例では、部分ブロックパターン識別子は、切り欠きブロックパターンに直接対応付けられている。しかし、部分ブロックパターン識別子は、例えば部分ブロックパターン識別子とブロックパターン識別子を対応付ける対応表を介して、切り欠きブロックパターンに対応付けられてもよい。
【０１１４】
（実施の形態３）
本実施の形態の配線データの生成方法は、配線経路の生成工程（Ｓ４）およびトラックパターン終端部の切り欠き工程（Ｓ６）以外は、図５に示す実施の形態１の配線データの生成方法と略同じである。図２４は、本実施の形態の配線経路の生成工程のフローチャートである。
【０１１５】
図２４に示すように、本実施の形態の配線経路の生成工程は、実施の形態１の配線経路の生成工程（図９参照）の「経路探索の成否判定工程（Ｓ１６）」と「経路未確定フラグＯＮ工程（Ｓ１８）」の間に追加された工程を有している。尚、実施の形態１と共通する部分については、説明を省略する。追加された工程は、図２４に示すように、「トラック増設および迂回経路探索工程（Ｓ３０）」と「経路探索の成否判定工程（Ｓ３６）」である。
【０１１６】
―トラック増設および迂回経路探索工程（Ｓ３０）―
図２５は、トラック増設および迂回経路探索工程（Ｓ３０）のフローチャートである。図２６及び２７は、トラック増設および迂回経路探索工程（Ｓ３０）を説明するパターン図である。
【０１１７】
接続経路の探索（Ｓ１４）の失敗は、トラックパターンが先に生成された配線経路により使用されている基本ブロックパターンで起きやすい。このよう場合、コンピュータ２８は、例えば図２６に示すように、トラックパターンが全て使用されている基本ブロックパターン４０ｇに対して、基本ブロックパターン４０Ａを、例えば半ピッチ（＝Ｐ/２）ずらして配置する。
【０１１８】
すなわち、コンピュータ２８は、配線経路５４が既に通っているトラックパターン（以下、経路トラックパターンと呼ぶ）４４ｆのピッチ（すなわち、トラックパターン４４のピッチＰ）を設計で許される最小ピッチの２倍以上に設定し、その間にトラックパターン（以下、第１の増設トラックパターンと呼ぶ）４４ｈが介在するように、基本ブロックパターン４０Ａを配置する（Ｓ３２）。基本ブロックパターン４０Ａは、トラックパターン終端部が切り欠かれていない基本ブロックパターンである。
【０１１９】
尚、トラックパターン４４ｆのピッチＰが広くなると配線密度が低くなり、集積回路の集積度が低下する。従って、トラックパターン４４ｆのピッチは、設計で許される最小ピッチの４倍以下が好ましい。
【０１２０】
同様に、コンピュータ２８は、経路トラックパターン４４ｆに接するトラックパターン４４ｇの間にもトラックパターン（以下、第２の増設トラックパターンと呼ぶ）４４ｉが介在するように、基本ブロックパターン４０Ｂを配置する（Ｓ３２）。
【０１２１】
トラックパターン４４ｇは、例えば、途中まで生成された接続経路側のトラックパターンである。第２のトラックパターン４４ｉは、第１の増設トラックパターン４４ｈに接するトラックパターンである。基本ブロックパターン４０Ｂは、基本ブロックパターン４０Ａと同様、トラックパターン終端部が切り欠かれていない基本ブロックパターンである。
【０１２２】
ここで、トラックパターン４４ｆを有するブロックパターン（基本ブロックパターン４０ｇ）内のトラックパターンの本数および間隔と、トラックパターン４４ｈ、４４ｉを有するブロックパターン（基本ブロックパターン４０Ａ,４０Ｂ）内のトラックパターンの本数および間隔は等しい。したがって、トラックが増設されたレイアウトパターンを基本ブロックパターン４０および切り欠きブロックパターン６８を用いて描画することが可能であり、ブロックマスクに搭載されるブロックパターンの数を半分に節約することができる。
【０１２３】
次に、コンピュータ２８は、図２７に示すように、第１のトラックパターン４４ｈおよび第２のトラックパターン４４ｉを通って、経路トラックパターン４４ｆを迂回する接続経路（以下、迂回経路と呼ぶ）８８を探索する（Ｓ３４）。図２７に示す迂回経路８８のうちの破線で示された部分は、別の配線パターン形成面（例えば、第２の配線パターン形成面）に設けられた配線経路である。異なる配線パターン形成面に設けられる配線経路の経路端部は、接続ビアパターンにより接続される。
【０１２４】
経路探索に成功した場合に、経路トラックパターン４４ｆを迂回する迂回経路８８が生成される。経路探索に失敗した場合には、経路トラックパターン４４ｆを迂回する迂回経路８８が生成されない。
【０１２５】
コンピュータ２８は、接続経路の探索に成功すると、図２４に示すように、迂回経路の探索工程を終了する（Ｓ３６→Ｓ１７）。迂回経路の探索に失敗すると、コンピュータ２８は、経路未確定フラグをＯＮし、配線パターンデータの生成を終了する（Ｓ３６→Ｓ１８→Ｓ１９）。
【０１２６】
―トラックパターン終端部の切り欠き工程―
コンピュータ２８は、実施の形態１で説明したトラック終端部の切り欠き工程（Ｓ６）と同様、配線経路５４の経路端部５８が配置されたトラックパターンまたはその隣接トラックパターンのトラック終端部６４ａ６,４ｂを切り欠く（図１３及び１４参照）。更に、コンピュータ２８は、迂回経路８８が通る第１の増設トラックパターン４４Ｈおよびこの第１の増設トラックパターン４４Ｈに接する第２の増設トラックパターン４４Ｉの終端部のうちの迂回経路８８が通らないトラックパターン終端部６４ｄを切り欠く。
【０１２７】
本実施の形態によれば、トラックパターンが大部分使用されていている領域でも、配線経路が生成される。
【０１２８】
（実施の形態４）
図２８は、本実施の形態の「配線パターンデータの生成方法」を説明するパターン図である。本実施の形態では、実施の形態１の接続完了判定工程（Ｓ８）と配線パターンの生成工程（Ｓ１０）の間に、ダミーパターン配置工程を有している。
【０１２９】
図２８（ａ）には、「平行配線の生成工程（Ｓ２）」〜「接続完了判定工程（Ｓ８）」により配線パターン形成面３７に生成される配線パターン９２の一例が示されている。
【０１３０】
図２８（ａ）の空白領域（以下、メモリ領域と呼ぶ）９４は、メモリのセルパターン（図示せず）が配置された領域である。配線パターン９２の外側の領域は、周辺回路のセルパターンが配置される領域である。
【０１３１】
図２８（ａ）に示すように、配線パターン形成面３７には、配線経路が通らない無効領域９６が広範囲に亘って発生する場合がある。
【０１３２】
無効領域９６内の配線パターンは、ＣＭＰ（Chemical Mechanical Polishing）によるエッチング斑の防止には役立つ。しかし、無効領域内の配線パターンを、サイズが小さい基本ブロックパターンを用いてレジスト膜に転写することは非効率である。
【０１３３】
そこで、本実施の形態では、基本ブロックパターン４０よりサイズが大きいダミーパターンを用いて、無効領域内の配線パターンを生成する。
【０１３４】
図２８（ｂ）に示すように、コンピュータ２８は、まず基本ブロックパターン４０より広く配線経路が通らない無効領域９６内のトラックパターンを削除する。
【０１３５】
その後、図２８（ｃ）に示すように、コンピュータ２８は、この無効領域内に基本ブロックパターン４０より広いダミーパターン９８を配置する。この時、無効領域内になるべく空白領域が生じないようにする。
【０１３６】
「配線パターンデータの生成工程（Ｓ１０）」では、コンピュータ２８は、実施の形態１と同様に配線データを生成し、更に、ダミーパターン９８のパターン識別子とダミーパターン９８の配置位置とを有する配線データを生成する。
【０１３７】
図２９は、ダミーパターン９８を説明するパターン図である。
【０１３８】
図２９（ａ）には、ダミーパターン９８が示されている。図２９（ｂ）には、基本ブロックパターン４０が示されている。ダミーパターン９８は、図２９（ａ）に示すように、例えば１：１のライン＆スペースパターン（すなわち、複数の平行配線パターン）である。
【０１３９】
基本ブロックパターン４０の一辺は、例えば１μｍである。一方、ダミーパターン９４の一辺は、例えば１．５μｍである。この場合、ダミーパターン９８の面積（＝１．５μｍ×１．５μｍ）は、基本ブロックパターン４０の面積（＝１μｍ×１μｍ）の２倍以上である。従って、ダミーパターン９８を無効領域９６に配置すると、電子ビーム露光の露光回数が半分以下になる。
【０１４０】
ダミーパターン９８のサイズとしては、電子ビーム露光装置２が生成する最大の矩形電子ビームと同じサイズが好ましい。
【０１４１】
ところで、メモリセルの外部端子パターン（以下、メモリ端子パターンと呼ぶ）は、メモリ領域９４に設けられる。配線パターン９２内の平行配線パターンとメモリ端子パターンは、ＶＳＢ法で形成される配線パターンにより接続される。この配線パターンと平行配線パターンの接続点が、検索対象端子点５６ａ,５６ｂとして選択される（図１０および１１参照）。
【０１４２】
図３０は、論理ゲートの外部端子パターンとトラックパターンの関係を説明する図である。図３０には、論理ゲートのセルパターン１００（以下、ゲートパターンと呼ぶ）および基本ブロックパターン４０が示されている。
【０１４３】
ゲートパターン１００は、配線パターン形成面の下方に設けられるセルパターン配置面に配置される。このため、ゲートパターン１００の外部端子パターン（以下、ゲート端子と呼ぶ）１０２は、図３０に示すように、ビアパターン（図示せず）を介してトラックパターン４４に接続される。このビアパターンとトラックパターン４４の接続点も、検索対象端子点として選択される。ゲート端子パターン１０２は、トラックパターン４４上に直接設けられることもある。この場合は、ゲート端子パターン１０２が、検索対象端子点として選択される。
【０１４４】
（実施の形態５）
実施の形態１で説明したように、配線パターンデータの生成工程（Ｓ１０）では、配線パターンデータおよび接続ビアデータが生成される。しかし、実施の形態１では、接続ビアデータの生成方法については詳しく説明しなかった。本実施の形態では、接続ビアデータの生成方法の一例を詳しく説明する。
【０１４５】
図３１は、接続ビアデータの生成方法を説明するパターン図である。図３２は、接続ビアデータ１１６のデータ構造を示す図である。
【０１４６】
実施の形態１で説明したように、複数の配線パターン形成面に跨って接続経路が探索されると、接続ビアパターンが生成される。図３１に示すように、接続ビアパターン１０４はビアパターン配置面内の格子点６２に配置される。
【０１４７】
その後、コンピュータ２８は、接続ビアパターンがその格子点に配置されたビアパターン配置面１０６をサブフィールド１０８ごとに分割する。コンピュータ２８は、図３２に示すように、分割されたビアパターン配置面のパターン（以下、サブフィールドパターンと呼ぶ）１１０に対応するビアブロックパターン識別子１１２およびサブフィールドパターン１１０の位置１１４とを有する接続ビアデータ１１６を生成する。
【０１４８】
図３２に示す接続ビアデータでは、ビアブロックパターン識別子１１２とサブフィールドパターン１１０の位置１１４を有するレコードが、第１ビア層セル（ディレクトリ）に格納される。この接続ビアデータ１１６および配線パターンデータ７４（図１６）は、ＩＣレイアウトデータの一部として、例えば第１のＨＤＤ２８ｄに記録される。ＩＣレイアウトデータには、セルパターンデータも記録される。セルパターンデータは、セルパターン識別子とセルパターンの配置位置を有するデータである。
【０１４９】
サブフィールド１０８としては、基本ブロックパターンより狭い領域が好ましい。例えば、サブフィールド１０８としては、２〜４本のトラックパターンを囲う程度の領域が好ましい。具体的には、サブフィールドとしては、並列配置された所定数（例えば、１〜６本）のトラックパターン（例えば、第２の方向５２に延在するトラックパターン４４ｂ）上の格子点を有する領域が好ましい。
【０１５０】
ビアブロックパターン識別子１１２は、このようなサブフィールド１１０内の格子点６２にビアパターン１０４を配置することで生成される互いに異なる複数のビアブロックパターンのいずれかに対応付けられている。
【０１５１】
ところで、殆どのＩＣレイアウトパターンでは、１トラックパターン当たりのビアパターンの数は高々１つ程度ある。したがって、ビアブロックパターンとしては、１トラックパターンごとに所定数以下（例えば、一つ以下）のビアパターンを有することが好ましい。
【０１５２】
トラックパターンの長さが一般的なブロックパターンのサイズ（１.０〜１．５μｍ程度）の範囲内にある場合、回路接続には、１トラックパターン当たり１箇所程度のコンタクトポイントで十分である。このため、１トラックパターン当たりのビアパターンの数を所定数以下にすることで、ビアブロックパターンのバリエーション数を抑制しながらサブフィールドのサイズを大きくすることが可能になる。このため、ビアブロックパターンの種類を増やさずに描画図形数（すなわち、露光回数）を減らすことが可能となる。
【０１５３】
このようなビアブロックパターンに対して、サブフィールドパターン１１０が一トラックパターン当たり複数のビアパターンを有する場合がある。この場合、コンピュータ２８は、サブフィールドパターンに最もマッチングするビアブロックパターンの識別子をサブフィールドパターン１１０に対応させる。そして、コンピュータ２８は、このビアブロックパターンの識別子とサブフィールドパターン１１０の位置を有する第１の接続ビアデータを生成する。
【０１５４】
次に、コンピュータ２８は、最もマッチングするビアブロックパターンに含まれないサブフィールド１１０内の接続ビア（以下、残存ビアパターンと呼ぶ）を単一ビアパターンの識別子に対応させる。コンピュータ２８は、単一ビアパターンの識別子と残存ビアパターンの位置を有する第２の接続ビアデータを生成する。
【０１５５】
サブフィールドパターンは、第１の接続ビアデータおよび第２の接続ビアデータそれぞれに基づく電子ビーム露光により、レジスト膜に転写される。
【０１５６】
（実施の形態６）
図３３及び３４は、本実施の形態の配線パターンデータの生成方法を説明するパターン図である。実施の形態１および５と共通する部分については、説明を省略する。
【０１５７】
実施の形態１乃至５では、単一ビアパターンにより、第１の配線経路５４ａの経路端部５８ａと第２の配線経路５４ｂの経路端部５８ｂが接続される。
【０１５８】
一方、本実施の形態では、二重ビアパターンにより、第１の配線経路と第２の配線経路が接続される。
【０１５９】
図３３に示すように、第１のトラックパターン４４ａおよび第２のトラックパターン４４ｂの一方１１８（例えば、第２のトラックパターン）は、格子点６２から突出する突出部１２０を有している。
【０１６０】
図３４に示すように、コンピュータ２８は、格子点６２とこの格子点６２から突出する突出部１２０に接続ビアパターン１０４を配置して、第１の配線経路５４ａの経路端部と第２の配線経路５４ｂの経路端部を接続する。これにより、第１の配線経路５４ａと第２の配線経路５４ｂが二重ビアパターンにより接続される。
【０１６１】
尚、図３３のトラックパターン１１８を有する基本ブロックパターンは、格子点６２の数から明らかなように、１２本のトラックパターンを有している。
【０１６２】
ところで、実施の形態１乃至６では、コンピュータ２８が、配線データの生成方法を実行する。しかし、実施の形態１乃至６で説明した配線データの生成方法の一部または全部は、人間により実行されてもよい。
【０１６３】
実施の形態１乃至４の基本ブロックパターンは、５本のトラックパターンを有している。しかし、基本ブロックパターンが有するトラックパターンの数は、５つには限らない。基本ブロックパターンが有するトラックパターンの数は、例えば、２〜２０本でもよい。
【０１６４】
実施の形態２乃至６には、実施の形態１の配線データの生成方法に追加することが好まし工程が示されている。これらの工程は、組み合わせてされて実施の形態１の配線データの生成方法に追加されてもよい。
【０１６５】
従来のＥＤＡ（Electronic Design Automation）ツールにより配線パターンがランダムに決められる物理レイアウトパターンを一旦生成し、このレイアウトパターン内に認識される数少ない繰り返し性に基づいてブロックパターンを形成することも考えられる。しかし、ロジック回路のランダムな配線の繰り返し性は極めて薄いので、このようなブロックパターンを用いても殆ど図形圧縮効果は得らない。
【０１６６】
ＣＰ方式の電子ビーム露光法において描画図形数を圧縮するためには、許容される範囲内でなるべくブロックパターンのサイズを大きくし、かつブロックエリア内に設けることのできるブロック数（高々４０００程度）の範囲内にブロックパターンの種類数を納めることが好ましい。
【０１６７】
実施の形態１乃至６によれば、ランダムな配線パターンの描画図形数が大幅に削減でき、電子ビーム露光のスループットを高めることができる。すなわち、実施の形態１乃至６によれば、描画可能な最大電子ビーム（例えば、一辺が１.0〜1.5μm程度の矩形ビーム）に近いサイズを有し且つ必要最小限のブロックパターンによって全ての配線レイアウトパターンが生成されるので、理想に近い図形削減が実現される。
【符号の説明】
【０１６８】
３６・・・平行配線パターン
３７・・・配線パターン形成面
３８・・・配線領域
４０・・・基本ブロックパターン
４２・・・一方向
４４・・・トラックパターン
４６・・・交差方向
５０・・・第１の方向
５２・・・第２の方向
５４ａ・・・第１の配線経路
５４ｂ・・・第２の配線経路
５６ａ,５６ｂ・・・検索対象端子点
５８,５８ａ,５８ａ・・・経路端部
６０・・・接続経路
６２・・・格子点
６４ａ,６４ｂ・・・トラックパターン終端部
６６・・・トラックパターン始端部
６８・・・切り欠きブロックパターン
７０・・・ブロックパターン識別子
７２・・・配置位置
７４・・・配線パターンデータ
７６・・・ダングリング配線中間部
７８・・・切り取り枠
８６・・・部分ブロックパターン
９８・・・ダミーパターン
１０６・・・ビアパターン配置面
１０８・・・サブフィールド
１１２・・・ビアブロックパターン識別子
【図１】
0005708330.tif 000002
【図２】
0005708330.tif 000003
【図３】
0005708330.tif 000004
【図４】
0005708330.tif 000005
【図５】
0005708330.tif 000006
【図６】
0005708330.tif 000007
【図７】
0005708330.tif 000008
【図８】
0005708330.tif 000009
【図９】
0005708330.tif 000010
【図１０】
0005708330.tif 000011
【図１１】
0005708330.tif 000012
【図１２】
0005708330.tif 000013
【図１３】
0005708330.tif 000014
【図１４】
0005708330.tif 000015
【図１５】
0005708330.tif 000016
【図１６】
0005708330.tif 000017
【図１７】
0005708330.tif 000018
【図１８】
0005708330.tif 000019
【図１９】
0005708330.tif 000020
【図２０】
0005708330.tif 000021
【図２１】
0005708330.tif 000022
【図２２】
0005708330.tif 000023
【図２３】
0005708330.tif 000024
【図２４】
0005708330.tif 000025
【図２５】
0005708330.tif 000026
【図２６】
0005708330.tif 000027
【図２７】
0005708330.tif 000028
【図２８】
0005708330.tif 000029
【図２９】
0005708330.tif 000030
【図３０】
0005708330.tif 000031
【図３１】
0005708330.tif 000032
【図３２】
0005708330.tif 000033
【図３３】
0005708330.tif 000034
【図３４】
0005708330.tif 000035