JP7635751B2 - Ｃａｄ上のパーツの自動配置方法及び自動配置プログラム - Google Patents

Description

本開示は、ＣＡＤ上のパーツの自動配置方法及び自動配置プログラムに関し、より詳しくは、半導体チップの配置エリアに半導体チップを構成する複数種類のパーツを自動で配置するものに関する。

半導体装置の製造工程において、半導体基板へのパターンの転写には写真製版技術が用いられる。写真製版技術では、半導体基板上に塗布された感光材料に対して、フォトマスク越しに光を照射する。フォトマスクには、半導体チップのパターンが描かれており、フォトマスクの作成にはＣＡＤツールとも称されるＣＡＤ装置が用いられる。ＣＡＤ装置を用いて作成されるフォトマスクのＣＡＤ図は、階層構造を持つ。即ち、半導体チップを構成する複数種のパーツが配置されたファイルと、各種のパーツが夫々描かれるファイルとに分けることで、半導体装置の全体像を容易に管理できるようにしている。

電力制御用の半導体装置として、パワーデバイスが知られている。パワーデバイスでは、大電流を制御するために、セルと呼ばれるトランジスタが並列接続するように多数配置されている。セルの配置数は、例えば、数百万個に及ぶ。パワーデバイス用のＣＡＤ図では、半導体チップの配置エリアに、パーツが隙間なく配置されている。パーツを隙間なく適所に配置することは、ＣＡＤ装置の描画面におけるパーツの自動配置により実現する。

下記特許文献１には、半導体集積回路の自動設計方法が開示されている。

特開２０１６－１０５２３４号公報

パーツの自動配置方法として、マップ方式を採用することが考えられる。マップ方式では、配置マップをプログラムに読み込ませた上で、図３４に示すように、固定パーツＰＴｆｘと称される半導体チップの構成パーツが設けられる領域と、調整パーツＰＴａｊが設けられる、図中にハッチングで示す寸法調整領域とを設けることで、チップサイズが調整される。マップ方式では、固定パーツＰＴｆｘと調整パーツＰＴａｊとを識別する必要があるため、ユーザーの条件設定数（条件設定量ともいう）が増える。同一種類のパーツＰＴｆｘを配置する場合でも、パーツ分の座標設定が必要である。なお、アレイを使用する場合でも、縦横のアレイ数の設定が必要である。また、回転・反転設定が座標に紐づくため、図中にＲ１で示す四隅に同一の固定パーツＰＴｆｘが配置される場合でも、座標毎に回転・反転方向が異なると、ユーザーによる条件設定数が増えてしまう。

他の自動配置方法として、マップを用いずに自由に配置する自由配置方式を採用することが考えられる。自由配置方式では、パーツの配置未済を識別するため、例えば、図３５に示すようなメッシュＭｓを設けて配置座標が予め設定される。然し、パワーデバイス用の半導体チップのサイズは数ｃｍに及ぶのに対して、配置座標の間隔は０．１μm以下である。この場合、メッシュＭｓに１０^１０個以上の配置座標を設定する必要があるため、ＣＡＤ装置に対してメモリ容量を含めた計算負荷が大きくなる。

本開示は、上述のような課題を解決するためになされたもので、ユーザーによる条件設定数が少なく、計算負荷の小さい半導体チップ用パーツの自動配置方法及び自動配置プログラムを提供することを目的とする。

本開示に係るＣＡＤ上のパーツ自動配置方法は、複数種類のパーツをＣＡＤツール上の配置エリアに自動で配置するＣＡＤ上のパーツの自動配置方法であり、配置エリアの互いに直交する二方向をＸ方向及びＹ方向とし、複数種類のパーツが、Ｘ方向またはＹ方向に平行な辺を有する矩形である。ＣＡＤ上のパーツ配置方法は、パーツの種類毎に設定される、パーツに隣接して配置することが許可されるパーツの種類を示すパーツ境界条件を取得するパーツ条件取得工程と、パーツの種類毎に設定される、配置エリアへの配置順を取得するパーツ配置順取得工程と、配置エリアの終端を示す線であるエリア終端線とＸ方向またはＹ方向に平行な境界線が配置され、境界線により隔てられる二つの領域に配置されているパーツを示す境界線境界条件を取得する境界線取得工程と、パーツに対して設定されたパーツ境界条件と配置エリアに配置された境界線に対して設定された境界線境界条件とを比較し、一致したときにパーツを配置するパーツ配置工程と、パーツ配置工程でパーツを配置後、境界線及び境界線境界条件を更新する境界線更新工程と、パーツ配置工程と境界線更新工程とを繰り返し実行する第一の繰り返し工程と、パーツの境界条件と境界線との一致が不可能である場合に、配置するパーツの種類を配置順が次であるパーツに変更するパーツ種類変更工程と、配置順に従って、パーツ配置工程と境界線更新工程と第一の繰り返し工程とパーツ種類変更工程とを繰り返し実行する第二の繰り返し工程と、を有する。

本開示に係るＣＡＤ上のパーツ自動配置プログラムは、複数種類のパーツをＣＡＤツール上の配置エリアに自動で配置するものであり、配置エリアの互いに直交する二方向をＸ方向及びＹ方向とし、複数種類のパーツが、Ｘ方向またはＹ方向に平行な辺を有する矩形である。自動配置プログラムは、コンピュータに、パーツの種類毎に設定される、パーツに隣接して配置することが許可されるパーツの種類を示すパーツ境界条件を取得するパーツ条件取得ステップと、パーツの種類毎に設定される、配置エリアへの配置順を取得するパーツ配置順取得ステップと、配置エリアの終端を示す線であるエリア終端線とＸ方向またはＹ方向に平行な境界線が配置され、境界線により隔てられる二つの領域に配置されているパーツを示す境界線境界条件を取得する境界線取得ステップと、パーツに対して設定されたパーツ境界条件と配置エリアに配置された境界線に対して設定された境界線境界条件とを比較し、一致したときにパーツを配置するパーツ配置ステップと、パーツ配置工程で配置したパーツの辺と重複した境界線を消去し、境界線と重複しないパーツの辺に新たな境界線及び境界線境界条件を設定する境界線更新ステップと、パーツ配置ステップと境界線更新ステップとを繰り返し実行する第一の繰り返しステップと、パーツの境界条件と境界線との一致が不可能である場合に、配置するパーツの種類を配置順が次であるパーツに変更するパーツ種類変更ステップと、配置順に従って、パーツ配置ステップと境界線更新ステップと第一の繰り返しステップとパーツ種類変更ステップとを繰り返し実行する第二の繰り返しステップと、を実行させる。

本開示によれば、境界条件を利用してパーツを自動配置するため、ユーザーによる条件設定数を減らすことができる。しかも、メッシュを用いるのではなく、境界線を用いてパーツの配置未済を識別することができるため、メモリの削減を含めて計算負荷が小さくて済む。

実施の形態１による半導体チップ用パーツの自動配置方法で配置されるパーツに設定される境界条件を説明する模式図である。 実施の形態１による半導体チップ用パーツの自動配置方法でパーツが配置される半導体チップの配置エリアを説明する模式図である。 パーツをオフセット配置する例を示す模式図である。 パーツの配置例を示す模式図である。 パーツの配置例を示す模式図である。 ユーザーによりＸＹ座標が指定されている場合のパーツの配置例を示す模式図である。 ユーザーによりＸ座標またはＹ座標が指定されている場合のパーツの配置例を示す模式図である。 パーツの配置例を示す模式図である。 パーツの配置例を示す模式図である。 パーツの配置例を示す模式図である。 パーツＰＴａの境界条件と一致する境界線群の候補を示す模式図である。 境界線の更新を説明する模式図である。 仮配置エリアＡｔを制限する場合を示す模式図である。 パーツのストレッチを説明する模式図である。 パーツの連動を説明する模式図である。 パーツを配置したブロックの配置例を示す模式図である。 パーツをマスターマスク配置する例を示す模式図である。 配置エリアがポリゴンである場合を示す模式図である。 パーツの配置後または配置途中で空白領域を取得する例を示す模式図である。 実施の形態１による半導体チップ用パーツの自動配置方法を実施するＣＡＤ装置のハードウェア構成図である。 実施の形態１による半導体チップ用パーツの自動配置方法のメイン処理を示すフローチャートである。 初期設定処理を示すフローチャートである。 パーツ候補抽出処理を示すフローチャートである。 境界配置処理を示すフローチャートである。 境界線評価処理を示すフローチャートである。 配置処理を示すフローチャートである。 仮配置前処理を示すフローチャートである。 座標配置処理を示すフローチャートである。 ライン配置処理を示すフローチャートである。 仮配置後処理を示すフローチャートである。 終了処理を示すフローチャートである。 変形例による半導体チップ用パーツの自動配置方法のメイン処理を示すフローチャートである。 パーツ候補抽出処理を示すフローチャートである。 マップ方式を用いてパーツを自動配置する例を説明する模式図である。 自由配置方式で用いられるメッシュの一例を示す模式図である。

以下、図面を参照して実施の形態について説明する。各図において共通または対応する要素には、同一の符号を付して、説明を簡略化または省略する。

実施の形態１．
図１～図３１を参照して、ダイシングラインＤＬの内側に設定される半導体チップの配置エリアＡＣに複数種類のパーツを配置する場合を例に、実施の形態１による半導体チップ用パーツの自動配置方法を説明する。以下においては、配置エリアＡＣの互いに直交する二方向をＸ方向及びＹ方向とする。図１中の左側をＸ方向左側、右側をＸ方向右側、上側をＹ方向上側、下側をＹ方向下側とする。各種類のパーツは、Ｘ方向またはＹ方向に平行な四つの辺ＸＬｐ０，ＹＬｐ１，Ｘｌｐ１，ＹＬｐ０を有する矩形である。矩形には、長方形と正方形の両方が含まれる。

（ユーザーによる事前準備）
半導体チップ用パーツの自動配置方法を実行する前に、ユーザーは、パーツＣＡＤファイルと、パーツ設定ファイルと、コマンドファイルと、必要に応じて後述するストレッチ設定ファイルとを準備する。これらのファイルは、後述するＣＡＤ装置１のメモリ１００ｂに記録される。

パーツＣＡＤファイルは、配置する各種のパーツＰＴが描かれたファイルである。

パーツ設定ファイルは、パーツＣＡＤファイルに対応させて、パーツＰＴの種類毎に作成される。パーツ設定ファイルには、図１に示すように、パーツＰＴの座標Ｘｍｉｎ，Ｙｍｉｎ，Ｘｍａｘ，Ｙｍａｘに加えて、パーツＰＴの全ての辺ＸＬｐ０，ＹＬｐ１，Ｘｌｐ１，ＹＬｐ０に対して夫々設定される第一の境界条件ＢＢ，ＢＲ，ＢＴ，ＢＬと、全てのコーナーＣ０～Ｃ３に対して夫々設定される第二の境界条件ＢＣ０，ＢＣ１，ＢＣ２，ＢＣ３と、パーツＰＴの配置時に許可される回転角を示す回転条件と、を含む。パーツＰＴに設定されるこれら第一の境界条件、第二の境界条件及び回転条件を、まとめてパーツ境界条件と称する。

第一の境界条件は、Ｘ方向またはＹ方向に平行な各辺Ｌｐ０，ＹＬｐ１，ＸＬｐ１，ＹＬｐ０に隣接させて配置することが許可されるパーツＰＴの種類を示す。第二の境界条件は、各コーナーＣ０～Ｃ３に夫々対角方向に隣接させて配置することが許可されるパーツＰＴの種類を示す。なお、パーツＰＴの種類には、隣接配置できないことも含まれる。また、パーツ境界条件は、パーツＰＴを配置するために必要な境界条件であり、パーツＰＴを配置した後の境界条件を設定する必要はない。

ここで、第一の境界条件として、下辺ＸＬｐ０に対して設定されるものを例に説明すると、下辺ＸＬｐ０のＹ方向上側にはパーツＰＴ自体と重なるため、パーツＰＴを隣接させて配置することができない。一方、下辺ＸＬｐ０のＹ方向下側には隣接させてパーツＰＴを配置することが許可される。このため、下辺ＸＬｐ０に対する第一の境界条件として、下境界条件ＢＢが設定される。同様に、右辺ＹＬｐ１に対しては右境界条件ＢＲが設定され、上辺ＸＬｐ１に対しては上境界条件ＢＴが設定され、左辺ＹＬｐ０に対しては左境界条件ＢＬが設定される。

また、第二の境界条件として、左下コーナーＣ０に対して設定されるものを例に説明すると、左下コーナーＣ０と対角で向かい合う右上コーナーＣ２との対角方向のうち、右上コーナーＣ２とは反対側の左斜め下方向に隣接させてパーツＰＴを配置することが許可される。このため、左下コーナーＣ０に対する第二の境界条件として、左斜め下境界条件ＢＣ０が設定される。同様に、右下コーナーＣ１に対しては右斜め下境界条件ＢＣ１が設定され、右上コーナーＣ２に対しては右斜め上境界条件ＢＣ２が設定され、左上コーナーＣ３に対しては左斜め上境界条件ＢＣ３が設定される。

また、回転条件として、回転角が設定される。回転角は、時計回りまたは反時計回りにおいて、例えば、９０度の倍数により表すことができる。なお、既述のマップ方式では、配置座標であるＸ座標及びＹ座標並びに回転角の３条件をコーナー毎に設定する必要があり、４つのコーナーにパーツＰＴを配置する場合にはユーザーによる条件設定数は１２個となる。それに対して、本実施の形態では、ユーザーによる条件設定数は、２つの第一の境界条件と１つの回転条件の計３つで済む。

コマンドファイルには、チップ描画サイズ、パーツの配置順、境界線、配置オプション、領域指定などのコマンドが設定されている。コマンドは、後述するＣＡＤ装置１に装備されているプログラム言語を用いて記述され得る。

チップ描画サイズとは、図２に示すように、半導体チップを構成する複数種のパーツＰＴが配置される配置エリアＡＣのＸ方向及びＹ方向の長さである。パーツの種類の配置順は、例えば、サイズの大きいパーツから小さいパーツに設定したり、パーツの機能に基づいて設定したりすることが可能である。境界線として、配置エリアＡＣの終端を示す線であるエリア終端線、即ち、ダイシングラインＤＬとＸ方向またはＹ方向に平行に配置される４本の境界線ＸＬａ０，ＹＬａ１，ＸＬａ１，ＹＬａ０が設定されている。各境界線ＸＬａ０，ＹＬａ１，ＸＬａ１，ＹＬａ０には、その境界線により隔てられる二つの領域が、パーツＰＴの配置エリア外であることを示す第三の境界条件が設定されている。第三の境界条件は、境界線境界条件とも称する。Ｙ軸方向上側の境界線ＸＬａ１を例に説明すると、境界線ＸＬａ１で隔てられる上側及び下側の領域のうち、上側の領域には初期設定としてダイシングラインＤＬが配置されているため、境界線ＸＬａ１の上側の領域はパーツＰＴを配置することができない配置エリア外である。このため、境界線ＸＬａ１に対する第三の境界条件として、上境界条件ＢＴが設定される。同様に、境界線ＸＬａ０に対しては下境界条件ＢＢが設定され、境界線ＹＬａ１に対しては右境界条件ＢＲが設定され、境界線ＹＬａ０に対しては左境界条件ＢＬが設定される。なお、境界線境界条件とも称される第三の境界条件としては、境界線により隔てられる二つの領域に配置されているパーツＰＴの有無及び種類を示すものであってもよい。

配置オプションは、座標配置オプション、ライン配置オプション、オフセット配置オプション等を含む。座標配置オプションでは、パーツを配置する２座標（Ｘ，Ｙ座標）が記述されている。ライン配置オプションでは、パーツを配置するライン端ＹＬｅ（図８（ａ）参照）や、Ｘ座標（Ｘ＝Ｘａ）とＹ座標（Ｙ＝Ｙａ）のうちの１座標（図８（ｂ）参照）が記述されている。ラインオフセット配置オプションでは、例えば、パーツＰＴと境界線との間の隙間であるＸ方向及びＹ方向のオフセット量Ｘ０，Ｘ１，Ｙ０，Ｙ１が記述されている。本実施の形態では、複数種類のパーツを隙間なく配置すること、つまり、パーツを境界線に隣接させて配置することを前提としているが、これに限定されない。デバイスに応じて、例えば、図３に示すように、故意に隙間を存してオフセット配置することもできる。また、１つのパーツの配置位置を、他のパーツが配置された境界線からずらすこともできる。

ＣＡＤツールとしてのＣＡＤ装置１の描画面にてパーツＰＴを自動配置するのに際しては、ユーザーによって事前準備されたパーツＣＡＤファイル、パーツ設定ファイル、コマンドファイル、ストレッチ設定ファイルが、ＣＡＤ装置１のメモリ１００ｂから読み出され、取得される（パーツ条件取得工程、パーツ配置順取得工程、境界線取得工程）。

なお、ＣＡＤ装置１が、過去にパーツを配置済みのＣＡＤファイルから、パーツ設定ファイルを作成することもできる。この場合、ＣＡＤ装置１が、パーツＰＴの名前または種類、パーツの配置座標、回転・反転情報、ストレッチ情報と、パーツのサイズ情報とを取得できるように構成する必要がある。

次に、以下の手順により、パーツが自動配置される（パーツ配置工程）。即ち、パーツ配置工程では、配置順が先である第一の種類のパーツ（以下、単に「パーツ」ともいう）ＰＴａに対して設定されたパーツ境界条件と、配置エリアＡＣに配置された境界線に対して設定された境界線境界条件とを比較する。具体的には、パーツＰＴａに対して設定された第一の境界条件及び第二の境界条件と、境界線に対して設定された第三の境界条件とを比較する。配置エリアＡＣには、同一種類のパーツＰＴａが既に配置されている場合を例に説明する。ここで、パーツＰＴａを配置可能な境界条件の一致条件として、図４～図８に示す例を挙げることができる。

図４に示す例では、パーツＰＴａに対して設定された第一の境界条件ＢＢ，ＢＴと、境界線ＸＬａ０に対して設定された第三の境界条件ＢＢ及び境界線ＹＬａ２に対して設定された第三の境界条件ＢＬが一致するため、これら２つの境界線ＸＬａ０，ＹＬａ２と接するようにパーツＰＴａが配置される。

図５に示す例では、パーツＰＴａに対して設定された第二の境界条件ＢＣ０と、２本の境界線ＹＬａ２，ＸＬａ２に対して設定された第三の境界条件ＢＬ，ＢＢが一致（実質的に一致）するため、これら２つの境界線ＹＬａ２，ＸＬａ２が形成する頂点と接するようにパーツＰＴａが配置される。

図６に示す例では、ユーザーが配置オプションとしての座標配置オプションで、ＸＹ座標を指定している。この場合、指定された座標（Ｘ，Ｙ）にパーツＰＴａがオフセット配置される。

図７に示す例では、パーツＰＴａに対して設定された第一の境界条件ＢＢと、１本の境界線ＸＬａ０に対して設定された第三の境界条件ＢＢが一致し、ユーザーがＸ座標（Ｘ＝Ｘａ）を指定している。この場合、境界線ＸＬａ０と接し、且つ、指定されたＸ座標（Ｘ＝Ｘａ）にパーツＰＴａが配置される。なお、Ｘ座標に代えてＹ座標が指定されている場合も同様に、パーツＰＴａを配置し得る。

図８（ａ）に示す例では、パーツＰＴａに対して設定された第一の境界条件ＢＬと、１本の境界線ＹＬａ０に対して設定された第三の境界条件ＢＬが一致し、ユーザーが配置オプションとしてのライン配置オプションで、ライン端ＹＬｅを指定している。この場合、境界線ＹＬａ０と接し、且つ、指定されたライン端ＹＬｅにパーツＰＴａが配置される。また、図８（ｂ）に示す例では、パーツＰＴａに対して設定された第一の境界条件ＢＬと、１本の境界線ＹＬａ０に対して設定された第三の境界条件ＢＬが一致し、ユーザーが配置オプションとしてのライン配置オプションで、Ｙ座標（Ｙ＝Ｙａ）を指定している。この場合、境界線ＹＬａ０と接し、且つ、指定されたＹ座標（Ｙ＝Ｙａ）にパーツＰＴａが配置される。

ここで、パーツＰＴａと２本の境界線ＸＬａ，ＹＬａに設定された境界条件が一致する場合、一致した境界の場所により、図９及び図１０に示す８通りに分けることができる。パーツＰＴａに設定されたパーツ境界条件に応じて、パーツＰＴａを配置可能なパターンが異なる。

図９（ａ）に示す例では、境界線ＸＬａの最小値ＸｍｉｎとＹＬａの最小値Ｙｍｉｎが一致している。図９（ｂ）に示す例では、境界線ＸＬａの最大値ＸｍａｘとＹＬａの最小値Ｙｍｉｎが一致している。図９（ｃ）に示す例では、境界線ＸＬａの最大値ＸｍａｘとＹＬａの最大値Ｙｍａｘが一致している。図９（ｄ）に示す例では、境界線ＸＬａの最小値ＸｍｉｎとＹＬａの最大値Ｙｍａｘが一致している。図１０（ａ）に示す例では、境界線ＸＬａの最大値ＸｍａｘとＹＬａの最大値Ｙｍａｘが一致している。図１０（ｂ）に示す例では、境界線ＸＬａの最小値ＸｍｉｎとＹＬａの最大値Ｙｍａｘが一致している。図１０（ｃ）に示す例では、境界線ＸＬａの最小値ＸｍｉｎとＹＬａの最小値Ｙｍｉｎが一致している。図１０（ｄ）に示す例では、境界線ＸＬａの最大値ＸｍａｘとＹＬａの最小値Ｙｍｉｎが一致している。

パーツＰＴａに設定された第一の境界条件または第三の境界条件からどの配置パターンが可能であるかを調べ、可能な配置パターン毎に以下の操作を行うようにする。即ち、先ず、図１１（ａ）に示すように、パーツＰＴａのパーツ境界条件と一致するＸＬａ群及びＹＬａ群の候補を検索する。次に、図１１（ｂ）に示すように、ＸＬａとＹＬａの始点及び終点が、図９及び図１０に示す例に一致すると、パーツＰＴａの配置が可能となる。なお、図１１（ｃ）に示すように、パーツＰＴａ内に、ＹＬａまたはＸＬａが存在する場合、パーツＰＴａの配置を中止する。

パーツＰＴａの配置が終了すると、パーツＰＴａの配置により新しくできた境界線を評価し、図１２に示すように、境界線を更新する（境界線更新工程）。なお、図４及び図５に示す例においても同様に、境界線が更新されている。

パーツＰＴａの配置により新しくできた境界線が、既に存在する境界線と重複する場合、図１２において破線で示す重複部分の境界線を消去する。境界線を全て消去した場合には、その消去した境界線の番号ＹＬａ１が空くため、空き番号ＹＬａ１を新たに生成した次の境界線に割り当てる。このように境界線の番号をリサイクルすることで、メモリを節約できると共に計算負荷を小さくできる。パーツＰＴａの配置前後において境界線が連続する場合、図１２（ｂ）に示すように境界条件が一致する場合には、境界線ＸＬａ１を延長する。一方、図１２（ｃ）に示す例では、図１２（ｂ）と同様の配置であるが、境界線ＸＬａ１に設定された境界条件と、境界線ＸＬａ２に設定された境界条件が一致しない場合には、境界線ＸＬａ１を延長するのではなく、新たなＸＬａ２を生成する。

以上説明した手順で、パーツ配置工程と境界線更新工程とを繰り返し実行する（第一の繰り返し工程）。そして、パーツＰＴａに対して設定されたパーツ境界条件と境界線に対して設定された境界線境界条件との一致が不可能である場合、つまり、第一の種類のパーツＰＴａを配置できなくなると、パーツの種類を配置順が次である第二の種類のパーツＰＴｂに変更する（パーツ種類変更工程）。

コマンドファイルに記述された配置順に従って、パーツ配置工程と、境界線更新工程と、第一の繰り返し工程と、パーツ種類変更工程とを繰り返し実行する（第二の繰り返し工程）。これにより、配置エリアＡＣに複数種のパーツＰＴを配置することができる。

このように、境界条件を利用してパーツを自動配置するため、ユーザーによる条件設定数を減らすことができる。しかも、メッシュＭｓを用いるのではなく、境界線を用いてパーツの配置未済を識別することができるため、メモリの削減を含めて計算負荷が小さくて済む。また、パーツＰＴの配置を繰り返し実行する間、境界線ＸＬａ，ＹＬａの消去及び生成を繰り返して更新することで、新規境界線を生成し続ける場合と比べて境界線の配列数を大幅に減少させることができる。これにより、メモリの削減を含めた計算負荷の減少を図ることができる。

ところで、回路の断線を防ぐためには、上述したオフセット配置を除き、配置エリアＡＣに隙間なくパーツを配置することが望ましい。一方、パーツ間の隙間がパーツ配置後に判明した場合、パーツを再配置したのでは時間のロスが大きい。また、既述のマップ方式のように調整パーツＰＴａｊを配置する方法では、ユーザーによる座標設定量が増えてしまう。

そこで、本実施の形態では、パーツを配置するのに先立ち、パーツの仮配置を行う（仮配置工程）。ここで、パーツの仮配置とは、パーツ自体を仮配置するのではなく、パーツを仮配置したと仮定して境界線の更新を行うことであり、パーツ配置工程の如くパーツ自在を仮配置する場合と比較して、仮配置に要する時間を短縮することができ、計算負荷を小さくすることが可能となる。仮配置に要する時間をさらに短縮するため、図１３に示すように、仮配置エリアＡｔを配置エリアＡＣよりも小さく制限してもよい。また、仮配置エリアＡｔを配置エリアＡＣに設定し、配置エリアＡＣ全体に亘って境界線の更新を行ってもよい。

仮配置では、境界線の更新により生じた隙間Ｇｐまたはその関数を求める。求めた隙間Ｇｐを無くすように、つまり、隙間無くパーツを配置するように、ストレッチラインＬｓが設けられている。後述するように、ストレッチラインＬｓを初期値から最大値ｍａｘ側または最小値ｍｉｎ側に設定することで、パーツの寸法を伸縮（ストレッチ）可能になっている。パーツを仮配置したと仮定して境界線の更新を進め、境界線がクロスする直前の隙間Ｇｐをストレッチ寸法とする。そして、ストレッチラインＬｓを図１４（ａ）に示す初期値から図１４（ｂ）に示すように最大値ｍａｘ側に設定することで、パーツ配置工程で配置されるパーツＰＴａの隙間Ｇｐを埋めることができる。これとは逆に、ストレッチラインＬｓを図１４（ｃ）に示すように最小値ｍｉｎ側に設定することで、隙間Ｇｐを広げ、広げた隙間に別のパーツを配置することもできる。なお、ストレッチ方向は上下方向に限定されず、左右方向でもよく、上下方向と左右方向の両方とすることもできる。ストレッチ方向が上下方向と左右方向の両方である場合には、上下方向用のストレッチラインと左右方向用のストレッチラインを設ければよい。さらに、パーツＰＴａのストレッチは、図１５（ａ）に示すようにパーツＰＴａ内で連動させてもよく、図１５（ｂ）に示すようにパーツＰＴａ，ＰＴａ間で連動させてもよい。

境界線の更新手順としては、上述したパーツ配置と同様の手順を用いることができる。これにより、パーツ配置手順を境界線の更新に最大限流用することができ、汎用性を高めることができる。さらに、半導体チップの全体配置を把握することなく仮配置を行うことができる。しかも、仮配置工程では、仮配置用の境界線のみが更新されるため、パーツの情報を残さずに済み、結果として、計算負荷を小さくすることができる。

なお、本実施形態では、矩形の配置エリアＡＣにパーツを配置する場合について説明したが、これに限定されない。パワーデバイスには、ＲＣ－ＩＧＢＴを構成するＩＧＢＴとダイオードのように周期構造を持つデバイスを持つものがある。例えば、図１６（ａ）に示すように、複数個のパーツＰＴａ，ＰＴｂが配置された複数のブロックＢｋ１，Ｂｋ２をＸ方向及びＹ方向の少なくとも一方に配置してもよい。この場合、上述した手順により各パーツＰＴａ，ＰＴｂを配置して各ブロックＢｋ１，Ｂｋ２を作成した後、改めて各ブロックＢｋ１，Ｂｋ２に境界条件を設定することで実現することができる。また、図１６（ｂ）に示すように、複数のブロックＢｋ１，Ｂｋ２をＸ方向及びＹ方向に直交する方向に重ねて配置してもよく、複数回実行したものを重ね書きすることにより実現することができる。これによれば、重ね書きやブロック化されたパーツが配置された半導体チップを作成することができる。なお、並設または重ねるブロックＢｋ１，Ｂｋ２のサイズは、同じであってもよいし、異なっていてもよい。

また、配置エリアＡＣの形状は、矩形に限定されず、例えば、図１７に示すマスターマスクのような円形、図１８に示すポリゴンであってもよい。配置エリアＡＣの形状は、コマンドファイルに領域設定として記述することができる。図１７に示すマスターマスクに配置する場合、円の中心にパーツＰＴａを２座標配置した後、この中心のＸ座標及びＹ座標のうちの一つの座標と一つの境界条件とを用いて十字にパーツＰＴを配置し、残りの部分に二つの境界条件を用いてパーツＰＴを配置する。また、図１８に示す円弧を含むコーナー部分に配置する場合、配置エリアＡＣを円の第一象限に設定し、第一の種類のパーツＰＴａを二つの境界条件を用いて配置する。このとき、配置エリアＡＣのうちの領域Ｒ１に限定する。領域Ｒ１は、周縁から所定長さの外周領域Ｒ２よりも内側の領域である。続いて、領域Ｒ１に第二の種類のパーツＰＴｂを二つの境界条件を用いて配置する。本実施の形態では、これらのパーツＰＴａ，ＰＴｂの自動配置までを行うことができる。それ以降は、配置エリアＡＣからパーツＰＴａ，ＰＴｂを除いた空白領域であるポリゴンＰＧを生成し、最後にポリゴンＰＧと領域Ｒ２の論理積により、ポリゴン形状を用いた構造体を生成し得る。このように円弧等が関連する複雑な形状の配置エリアＡＣへのパーツＰＴａ，ＰＴｂの配置が可能である。また、外周領域Ｒ２は、パーツを配置する途中で得られる境界線に沿った形状であるため、配置前に配置エリアＡＣを決定することができない。そこで、配置エリアＡＣは、パーツの配置途中や配置完了後の境界線によって画成される例えばポリゴンのようなものを取得するように構成してもよい。

また、パワーデバイスでは、並列に配置したＩＧＢＴ等の素子（セル）のゲート材料であるポリシリコンにより発生するスイッチング遅延を緩和するため、図１９（ａ）に示すように、配置エリアＡＣであるセル配置領域を等分割するようにゲートライナーＧＬを配置する場合がある。ゲートライナーＧＬは、例えば、アルミとポリシリコンで構成される。半導体チップは、異物の付着による配線のショートを防ぐために、ＳｉＯ_２等からなる保護膜によりチップ表面が覆われ、ワイヤボンディング部分のみが表面に露出する構造となっている。ここで、パワーデバイスでは、ワイヤボンディング数が多いため、図１９（ｂ）に示すように、保護膜Ｆｐは、セル配置領域の境界線と酷似した形状を有する。保護膜Ｆｐは、即ち、セル配置領域であるワイヤボンディング領域は、外形線の情報を用いて、図１９（ｃ）に示すように空白領域Ｒｂとして把握することができる。パーツＰＴの配置完了後にセル配置領域の境界線を得ることはできないが、配置途中に境界線で空白領域Ｒｂを把握することができる。ゲートライナーＧＬや保護膜Ｆｐの描画に必要な情報は、ユーザーがセル配置直前の境界線の情報を取得し、取得した情報をコマンドに反映させることで得られる。セル配置領域の境界線を取得する機能は、ＣＡＤ装置１内でモジュール化することが好ましい。このモジュールには、境界線の情報を取得する機能に加えて、取得した境界線を自由にオフセットした上でポリゴン構造体を描画する機能を持たせるようにする。これにより、境界線の情報がコマンドファイルとして利用可能な変数の形で出力することができる。

次に、図２０を参照して、ＣＡＤ上のパーツ自動配置方法を実施するＣＡＤ装置１を説明する。図２０は、実施の形態１によるＣＡＤ上のパーツ自動配置方法を実施するＣＡＤ装置１のハードウェア構成図である。ＣＡＤ装置１は、ＣＡＤ上のパーツ自動配置プログラムを実行可能なコンピュータに相当し、処理回路により実現し得る。例えば、処理回路は、少なくとも１つのプロセッサ１００ａと少なくとも１つのメモリ１００ｂとを備える。例えば、処理回路は、少なくとも１つの専用のハードウェア２００を備える。

処理回路が少なくとも１つのプロセッサ１００ａと少なくとも１つのメモリ１００ｂとを備える場合、ＣＡＤ上のパーツ自動配置装置の各機能は、ソフトウェア、ファームウェア、またはソフトウェアとファームウェアとの組み合わせで実現される。ソフトウェアおよびファームウェアの少なくとも一方は、プログラムとして記述される。ソフトウェアおよびファームウェアの少なくとも一方は、少なくとも１つのメモリ１００ｂに格納される。少なくとも１つのプロセッサ１００ａは、少なくとも１つのメモリ１００ｂに記憶されたプログラムを読み出して実行する。少なくとも１つのプロセッサ１００ａは、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、ＤＳＰともいう。例えば、少なくとも１つのメモリ１００ｂは、ＲＡＭ、ＲＯＭ、フラッシュメモリ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等の、不揮発性または揮発性の半導体メモリ、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等である。

処理回路が少なくとも１つの専用のハードウェア２００を備える場合、処理回路は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ、ＦＰＧＡ、またはこれらの組み合わせで実現される。例えば、パーツ自動配置装置の各機能は、それぞれ処理回路で実現される。パーツ自動配置装置の各機能について、一部を専用のハードウェア２００で実現し、他部をソフトウェアまたはファームウェアで実現してもよい。

図２１は、実施の形態１によるＣＡＤ上のパーツ自動配置方法のメイン処理を示すフローチャートである。図２１には、ＣＡＤ装置１のメインの動作が示される。

先ず、ステップＳ１１において、初期設定処理が実行される。初期設定処理では、図２２に示すサブルーチンが起動され、ユーザーにより事前に準備された複数種類のパーツの配置順を取得する（ステップＳ１１０）。ステップＳ１１０は、パーツ配置順取得工程に相当する。

続いて、パーツ設定ファイルを取得する（ステップＳ１１１）。ステップＳ１１１は、パーツ条件取得工程に相当する。なお、第一及び第二の境界条件は、パーツＰＴを配置するために必要なものであり、パーツＰＴを配置した後の境界条件を設定する必要はない。

次に、パーツＰＴのサイズを取得する（ステップＳ１１２）。パーツＰＴのサイズは、ＣＡＤ装置１が持つパーツ外形線出力機能により得られるものであってもよい。この場合、ユーザーが、パーツＰＴのサイズを事前に設定することを省略することができる。ステップＳ１１３で次の配置順のパーツが無いと判別されるまで、即ち、全種類のパーツＰＴについて、ステップＳ１１１，Ｓ１１２が繰り返し実行される。

次に、複数種類のパーツのＣＡＤファイルであるパーツＣＡＤファイルを取得する（ステップＳ１１４）。次に、境界線が保存されており、ロード可能か否かを判別し（ステップＳ１１５）、ロード可能である場合、境界線をロードする（ステップＳ１１６）。ロードできない場合、境界線を初期設定する（ステップＳ１１７）。初期設定では、配置エリアＡＣのエリア終端線であるダイシングラインＤＬに平行に配置される４本の境界線が設定され得る。その後、パーツのストレッチに関する情報であるストレッチ情報が保存されており、ロード可能か否かを判別し（ステップＳ１１８）、ロード可能である場合、ストレッチ情報をロードし（ステップＳ１１９）。ロードできない場合、ストレッチ情報を初期設定する（ステップＳ１２０）。

初期設定処理を終了すると、配置オプション処理を実行する（ステップＳ１２）。配置オプション処理では、図２３に示すサブルーチンが起動され、配置オプションが設定されえているか否かを判別する（ステップＳ１２１）。配置オプションが設定されていない場合、境界配置処理を実行する（ステップＳ１２２）。

境界配置処理では、図２４に示すサブルーチンが起動され、境界線を設定し（ステップＳ１３１）、回転条件に従い回転・反転を行う（ステップＳ１３２）。その後、境界条件が一致するか否かを判別する（ステップＳ１３３）。境界条件が一致する場合、配置フラグをＯＮにする（ステップＳ１３４）。その後、境界線評価処理を実行する（ステップＳ１３５）。

境界線評価処理では、図２５に示すサブルーチンが起動され、交差する境界線があるか否かを判別する（ステップＳ１４１）。交差する境界線がある場合には、配置フラグをＯＦＦし（ステップＳ１４２）、境界線評価処理を終了する。交差する境界線が無い場合には、重複する境界線の処理を行い（ステップＳ１４３）、連続する境界線の処理を行い（ステップＳ１４４）、境界線の空き番号があるか否かを判別する（ステップＳ１４５）。空き番号がある場合には、境界線に空き番号を割り当てる（ステップＳ１４６）。空き番号が無い場合、境界線に新規番号を割り当て（ステップＳ１４７）、境界線評価処理を終了する。

境界線評価処理の終了後、仮配置フラグがＯＮであるか否かを判別する（ステップＳ１３６）。仮配置フラグがＯＦＦである場合、配置処理を実行する（ステップＳ１３７）。

配置処理では、図２６に示すサブルーチンが起動され、配置フラグがＯＮであるか否かを判別する（ステップＳ１５１）。配置フラグがＯＦＦである場合、配置処理を終了する。配置フラグがＯＮである場合、ストレッチの設定が無いか否かを判別し（ステップＳ１５２）、ストレッチの設定が無い場合、パーツをストレッチせずに配置し（ステップＳ１５３）、配置処理を終了する。一方、ストレッチの設定がある場合、ストレッチ寸法が設定済みか否かを判別する（ステップＳ１５４）。ストレッチ寸法が設定済みである場合、パーツをストレッチし、ストレッチさせたパーツを配置し（ステップＳ１５５）、配置処理を終了する。

配置処理が終了すると、次に配置するパーツがなくなるまでステップＳ１３１～Ｓ１３７の処理を繰り返す（ステップＳ１３８）。

上記ステップ１５４でストレッチ寸法が設定されていないと判別された場合、仮配置前処理を実行する（ステップＳ１５６）。

仮配置前処理では、図２７に示すサブルーチンが起動され、仮配置起動時の状況を保存し（ステップＳ１５７）、仮配置フラグをＯＮし（ステップＳ１５８）、仮配置指定領域への配置に切り替える（ステップＳ１５９）。

上記ステップＳ１３６で仮配置フラグがＯＮであると判別された場合、ステップＳ１３８に移行し、パーツの配置と同様のルーチンに従い、パーツの仮配置が行われる。このパーツの仮配置は、上述したように、パーツ自体を仮配置するのではなく、パーツを仮配置したと仮定して境界線の更新を行うことである。

上記ステップＳ１２１で配置オプションが設定されていると判別された場合、座標配置オプション設定があるか否かを判別し（ステップＳ１２３）、座標配置オプション設定がある場合、座標配置処理を実行する（ステップＳ１２４）。

座標配置処理では、図２８に示すサブルーチンが起動され、２座標（Ｘ，Ｙ座標）が指定されているか否かを判別する（ステップＳ１６１）。２座標が指定されていない場合、即ち、１座標が設定されている場合、ライン配置処理を実行する（ステップＳ１６２）。

ライン配置処理では、図２９に示すサブルーチンが起動され、配置方式が座標指定配置であるか否かを判別する（ステップＳ１７１）。座標指定配置でない場合、即ち、ライン端配置である場合、上記境界配置処理を実行し（ステップＳ１７２）、ライン配置処理を終了する。座標指定配置である場合、配置フラグをＯＮにし（ステップＳ１７３）、上記境界線評価処理を実行する（ステップＳ１７４）。その後、仮配置フラグがＯＮか否かを判別し（ステップＳ１７５）、仮配置フラグがＯＮである場合には、ライン配置処理を終了する。仮配置フラグがＯＦＦである場合には、上記配置処理を実行し（ステップＳ１７６）、ライン配置処理を終了する。

上記ステップＳ１６１で２座標が指定されていると判別された場合、配置フラグをＯＮにし（ステップＳ１６３）、上記境界配置処理を実行する（ステップＳ１６４）。その後、仮配置フラグがＯＮか否かを判別し（ステップＳ１６５）、仮配置フラグがＯＮである場合には、座標配置処理を終了する。仮配置フラグがＯＦＦである場合には、上記配置処理を実行し（ステップＳ１６６）、座標配置処理を終了する。

配置オプション処理が終了すると、次のパーツ配置順番があるか否かを判別し（ステップＳ１３）。次のパーツ配置順番がある場合、ステップＳ１２に戻る。一方、次のパーツ配置順番がない場合、仮配置フラグがＯＮであるか否かを判別する（ステップＳ１４）。仮配置フラグがＯＮの場合、仮配置後処理を実行する（ステップＳ１５）。

仮配置後処理では、図３０に示すサブルーチンが起動され、仮配置後の余白である隙間Ｇｐを評価し（ステップＳ１８１）、該当パーツのストレッチ寸法を設定し（ステップＳ１８２）、仮配置フラグをＯＦＦにする（ステップＳ１８３）。その後、仮配置起動時の状態に復帰し（ステップＳ１８４）、仮配置後処理を終了する。

上記ステップＳ１４で仮配置フラグがＯＦＦであると判別された場合、終了処理を実行する（ステップＳ１６）。

終了処理では、図３１に示すサブルーチンが起動され、境界線の情報を保存し（ステップＳ１８５）、ストレッチ情報を保存する（ステップＳ１８６）。その後、終了処理を終了する。

次に、半導体チップの配置エリアＡＣの終端を示す線であるエリア終端線を境界線として取得すると共に、境界線に対して設定される第三の境界条件を取得する（ステップＳ１１４）。ステップＳ１１４は、境界線取得工程に相当する。

本実施の形態によれば、境界条件を利用してパーツを自動配置するため、ユーザーによる座標設定量を減らすことができる。しかも、メッシュＭｓを用いるのではなく、境界線を用いてパーツの配置未済を識別することができるため、メモリの削減を含めて計算負荷が小さくて済む。

なお、パーツ配置順番の指定が無くてもよい。この場合、図３２に示すように、上記初期設定処理を実行した後、パーツ候補抽出処理を実行する（ステップＳ１７）。
パーツ候補抽出処理では、図３３に示すサブルーチンが起動され、全境界線の境界条件の種類をリスト化し（Ｓ１８７）、境界線の境界条件リストにある境界条件を含むパーツをリスト化する（ステップＳ１８８）。ステップＳ１８８では、パーツ候補が作成される。その後、上記配置オプション処理を実行する（ステップＳ１２）。

ＡＣ…配置エリア、 ＢＢ，ＢＲ，ＢＴ，ＢＬ…第一の境界条件，第三の境界条件、 ＢＣ０，ＢＣ１，ＢＣ２，ＢＣ３…第二の境界条件、 ＰＴ，ＰＴａ，ＰＴｂ…パーツ、 ＸＬｐ０，ＹＬｐ１，Ｘｌｐ１，ＹＬｐ０…辺、 Ｃ０～Ｃ３…コーナー

Claims (9)

1. 複数種類のパーツをＣＡＤツール上の配置エリアに自動で配置するＣＡＤ上のパーツの自動配置方法であって、
   前記配置エリアの互いに直交する二方向をＸ方向及びＹ方向とし、前記複数種類のパーツが、Ｘ方向またはＹ方向に平行な辺を有する矩形であるものにおいて、
   前記パーツの種類毎に設定される、前記パーツに隣接して配置することが許可される前記パーツの種類を示すパーツ境界条件を取得するパーツ条件取得工程と、
   前記パーツの種類毎に設定される、前記配置エリアへの配置順を取得するパーツ配置順取得工程と、
   前記配置エリアの終端を示す線であるエリア終端線とＸ方向またはＹ方向に平行な境界線が配置され、前記境界線により隔てられる二つの領域に配置されている前記パーツを示す境界線境界条件を取得する境界線取得工程と、
   前記パーツに対して設定された前記パーツ境界条件と前記配置エリアに配置された前記境界線に対して設定された前記境界線境界条件とを比較し、一致したときに前記パーツを配置するパーツ配置工程と、
   前記パーツ配置工程で前記パーツを配置後、前記境界線及び前記境界線境界条件を更新する境界線更新工程と、
   前記パーツ配置工程と前記境界線更新工程とを繰り返し実行する第一の繰り返し工程と、
   前記パーツの境界条件と前記境界線との一致が不可能である場合に、配置するパーツの種類を前記配置順が次である前記パーツに変更するパーツ種類変更工程と、
   前記配置順に従って、前記パーツ配置工程と前記境界線更新工程と前記第一の繰り返し工程と前記パーツ種類変更工程とを繰り返し実行する第二の繰り返し工程と、を有するＣＡＤ上のパーツ自動配置方法。
2. 前記請求項１に記載のＣＡＤ上のパーツ自動配置方法を実施する前に、前記パーツを配置したと仮定して前記境界線の更新を行う仮配置工程を更に有し、前記仮配置工程は、
   請求項１に記載のＣＡＤ上のパーツ自動配置方法に従って前記パーツを配置したと仮定して前記境界線の更新を行うことで仮配置を行う工程と、
   前記仮配置後の前記境界線から前記仮配置がされていない隙間領域の寸法を算出し、前記隙間領域がなくなるように前記パーツの寸法を調整する工程と、を有する請求項１に記載のＣＡＤ上のパーツ自動配置方法。
3. 前記パーツ境界条件は、前記パーツの各辺に夫々隣接して配置することが許可される前記パーツの種類を示す第一の境界条件と、前記パーツの各コーナーに夫々対角方向に隣接して配置することが許可される前記パーツの種類を示す第二の境界条件と、前記パーツの配置時に許可される回転角を示す回転条件とを含み、
   前記境界線境界条件は、前記境界線により隔てられる二つの領域に配置されている前記パーツの有無及び種類を示す、または、前記二つの領域が前記パーツの配置エリア外であることを示す第三の境界条件を含む請求項１または請求項２に記載のＣＡＤ上のパーツ自動配置方法。
4. 前記パーツ配置工程において、前記パーツの前記第一の境界条件及び前記第二の境界条件と前記境界線の前記第三の境界条件とを比較し、前記パーツの二つの辺の前記第一の境界条件と二つの前記境界線の前記第三の境界条件とが一致したときに前記パーツを一致した二つの前記境界線に接するように配置し、または、前記パーツの前記第二の境界条件と二つの前記境界線の前記第三の境界条件とが一致したときに前記パーツを前記コーナーが一致した二つの前記境界線が形成する頂点に接するように配置し、
   前記境界線更新工程において、配置した前記パーツの辺と重複した前記境界線を消去し、前記境界線と重複しない前記パーツの辺に新たな前記境界線及び前記第三の境界条件を設定する請求項３に記載のＣＡＤ上のパーツ自動配置方法。
5. 請求項１または請求項２に記載のＣＡＤ上のパーツ自動配置方法により前記パーツが配置された複数のブロックをＸ方向及びＹ方向の少なくとも一方に配置する、または、前記複数のブロックをＸ方向及びＹ方向に直交する方向に重ねて配置する請求項１または請求項２に記載のＣＡＤ上のパーツ自動配置方法。
6. 前記配置エリアはポリゴン形状である請求項１または請求項２に記載のＣＡＤ上のパーツ自動配置方法。
7. 前記ポリゴン形状は、前記パーツの配置途中や配置完了後の前記境界線によって画成される請求項６に記載のＣＡＤ上のパーツ自動配置方法。
8. 前記パーツ境界条件は、過去に作成された前記パーツの配置データから自動で設定される請求項１に記載のＣＡＤ上のパーツ自動配置方法。
9. 複数種類のパーツをＣＡＤツール上の配置エリアに自動で配置するＣＡＤ上のパーツの自動配置プログラムであって、前記配置エリアの互いに直交する二方向をＸ方向及びＹ方向とし、前記複数種類のパーツが、Ｘ方向またはＹ方向に平行な辺を有する矩形であるものにおいて、
   コンピュータに、
   前記パーツの種類毎に設定される、前記パーツに隣接して配置することが許可される前記パーツの種類を示すパーツ境界条件を取得するパーツ条件取得ステップと、
   前記パーツの種類毎に設定される、前記配置エリアへの配置順を取得するパーツ配置順取得ステップと、
   前記配置エリアの終端を示す線であるエリア終端線とＸ方向またはＹ方向に平行な境界線が配置され、前記境界線により隔てられる二つの領域に配置されている前記パーツを示す境界線境界条件を取得する境界線取得ステップと、
   前記パーツに対して設定された前記パーツ境界条件と前記配置エリアに配置された前記境界線に対して設定された前記境界線境界条件とを比較し、一致したときに前記パーツを配置するパーツ配置ステップと、
   前記パーツ配置ステップで配置した前記パーツの辺と重複した前記境界線を消去し、前記境界線と重複しない前記パーツの辺に新たな前記境界線及び前記境界線境界条件を設定する境界線更新ステップと、
   前記パーツ配置ステップと前記境界線更新ステップとを繰り返し実行する第一の繰り返しステップと、
   前記パーツの境界条件と前記境界線との一致が不可能である場合に、配置するパーツの種類を前記配置順が次である前記パーツに変更するパーツ種類変更ステップと、
   前記配置順に従って、前記パーツ配置ステップと前記境界線更新ステップと前記第一の繰り返しステップと前記パーツ種類変更ステップとを繰り返し実行する第二の繰り返しステップと、を実行させるＣＡＤ上のパーツ自動配置プログラム。

Images