JPH04501475A - 保持体上にモジュールを配置するための方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 保持体上にモジュールを配置するための方法本発明は、モジュールの寸法を含ん でいるモジュールリストおよびモジュールの接続を含んでいるネットリストの使 用のもとに、１つの保持体上にモジュールを配！するための方法に関する。

１つの保持体上にモジュールを、たとえば１つのチップ上にゲートアレイ、標準 セル、マクロセルを、または導体板上にビルディングブロックを配置するための 方法は知られている。従来の技術に対する例としてはシー・ケイ・チェノおよヒ イー・ニス・クー著「抵抗ネットワーク最適化に基づくモジュール配置ＪＩＥＥ Ｅ論文集、計算機援用設計績、第ＣＡＤ−３巻、１９８４年、第２１８〜２２５ 頁、ケイ・エム・ジャスト、ジェー・エム・クラインハンスおよびエフ・エム・ ヨハネス著「標準セルレイアウトに対する相対的配置および輸送問題」デザイン −オートメーシッンーコンフエシンス、１９８６Ｌ第３０８〜３１３７Ｘｊ）＜ 参照される。これらの文献には、モジュールをそれらの相互の相対的位置で先ず 保持体の上に配置し、次いで保持体の上のそれらの最終的な位置を指定する方法 が示されている。出発点は回路のトポロジー、すなわちどのように複数個のモジ ュールが互いに接続されているかを示す回路図である。その場合配置の課題は、 これらのモジュールをそれらの接続の考慮のもとに最適に１つの保持体、たとえ ば１つのチップの上に配置することである。配置方法は詳細に前記文献に記載さ れており、それらが参照される。

公知の方法は先ずモジュール相互の相対的配置に努めている。そのために個々の モジュールの座標は、モジュールの重心が予め定められた点、たとえば配置面の 配列に対して予定されている面の中心座標に位置するように計算される。モジュ ールの座標は、互いに接続されているモジュールの間隔の関数が極小にされる最 適化問題を解くことによりめられる。この最適化問題の解は、モジュールをでき るかぎり均等に分布して配置面上に位置させる付随条件の考慮のもとに行われる 。モジュールの最終的で重なりのない位置の決定は相対的配置の終了後に行われ る。その際に相対的配置の情報が利用される。

本発明の課題は、予め製造されたモジュールを１つの保持体の上に配置するため の別の方法を提供することである。

この課題は冒頭に記載した種類の方法において、請求の範囲１の特徴部分により 解決される。

こうして本方法は１つの配置領域上のモジエールのグローバル配置と後続の仕切 りとの繰り返しから成っており、その際にこれらのステップは、分割により定め られた各部分９Ｉ域が最大で予め定められた数のモジュールを含むようになるま で繰力返される。グローバル配置は部分領域のなかのモジュールの配列により、 部分領域に割り当てられたモジュールの重心がこれらの部分領域の中心座標に位 置するように行われる。この際に、公知の方法との相違点として、すべての部分 領域のすべてのモジエールの配列が同時に計算される０部分領域は配置領域また は部分領域の仕切りにより達成され、その際に仕切りにより得られた部分領域に 選択可能な数のモジュールが対応付けられ、また仕切りにより得られた部分領域 の大きさは割り当てられたモジュールに関係して決定される。

配置領域または部分領域の分割は水平または垂直の切断線により行われるのが目 的にかなっている。その場合、部分領域へのモジュールの割り当てに対しては単 に、先のグローバル配置からのそれらのＸまたはｙ座標に従ったモジュールの分 類が必要である。仕切りが分割すべき領域の二分割から成っていることは目的に かなっている。

グローバル配置および仕切りの繰り返しは、各部分領域のなかにただ１つのモジ ュールだけが配列されるまで続けられ得る。しがし、この繰り返しが、各部分　 。

領域のなかに最大で予め定められた数のモジュール、たとえば８つのモジュール が含まれるときに中止されることは有利である。その場合、最適化ステップによ りモジュールの最終的配列が最適な面別用のもとに行われ得る。このステップは 、ｋ個のモジュールまでを有する部分領域のすべての可能な分割がグローバル配 置の結果の利用のもとに決定され、またビルディングブロックの配置に対する部 分面のその際に見い出された寸法が形状関数にまとめられることにあってよい、 このステップはすべてのこのような部分領域に対して行われ得る。これらの部分 領域の形状関数の加算によりすべての許容されるモジュール配置の寸法が計算さ れ得る。

本発明の他の実施態様は請求の範囲２以下にあげられている。

本発明による方法は、種りの寸法のモジュールが重なりなしに１つの平面内に配 置可能であり、その際にモジュールの１つの部分の場所に対する有利な条件が考 慮されるという利点を有する０本方法はモジュールの与えられた群の間の間隔の 関数およびモジュール配置の全面積に関する配置を最適化する。

本方法は特に、電気回路のレイアウト設計の際のモジュール（セル、ビルディン グブロック）の配置、すなわち平らな場所的配列への回路の与えられた関数記述 の変換を行う目的に役立つ、その際にモジュールの寸法はモジエールリストのな かに指定されている。関数記述は、モジュール間隔の最小化の際に考慮されるべ きすべてのモジュールが示されているネットリストとして与えられている。

本方法は標準セル、マクロセル、ゲートアレイおよびシーオプゲートテクノロジ ーでの集積されたセル回路のレイアウト設計に対しても導体板上へのビルディン グブロックの配置に対しても適している。

以下、図面に示されている実施例により本発明を一層詳細に説明する。

第１図は回路図の一例、 第２図は第１の通過の際の配置領域内のモジエールの配列、第３図は第２の通過 の際のモジュールの配置を有する配置領域、第４図は第３の通過後の同じ図、 第５図は配置領域上のモジエールの最終的配置、第６図はモジュールのｘＳｙ座 標の説明図、第７図は本方法の進行ダイアグラムである。

本方法により解決されるべき問題は、たとえば第１図に示されているような回路 図をたとえばチップ上の回路のレイアウトに変換することにある。第１図には単 に少数のモジエールを有する回路図の原理が示されている。モジュールは大文字 で示されている。それらはたとえばセルライブラリのセルであってよい０個々の モジュールは互いに接続されており、その際に第１図中には接続が簡単化されて 示されている。モジュールの接続は信号とも呼ばれる。

モジュールの寸法はモジュールリストのなかに、またモジュールの接続はネット リストのなかに含まれている。モジュールリストおよびネットリストは予め定め られており、また保持体、たとえばチップ上へのモジュールの配置のために使用 される。

モジュールの配置は第７図による進行ダイアグラムに相応して行われる。そこに 示されているように、本方法は一連の交互のステップ、すなわちグローバル配Ｉ Ｓ１および仕切りＳ２から成っている。この一連の交互のステップは、仕切りに より生ずるモジュールの部分集合がもはや予め定め得る数のモジュールよりも多 いモジニールを含んでいないときに終了する０本方法は、好適には配置領域の生 じた部分領域がすべての可能なモジュール配列の評価により改善され、その際に モジュールの座標とならんでその回転位置も決定される最適化ステップＳ３によ り終了すると良い。

グローバル配Ｉにより、関数的な回路記述から付随条件を有する連続的な最適化 問題の定式化および解によりグローバルな最適なモジュール配列、すなわちすべ てのモジュールに対する最適な場所的隣接関係を計算することができる。その際 にすべてのモジュールは重なりのない配列が得られるま同時に行われる。

最初の方法ステップＳＯではすべてのモジエールＭ、が分割されない集合に対応 付けられる。その際にネットリスト、すなわち間隔関数が最小化されるべきであ るすべての重み付は可能なモジュール群（ネット）のリストが与えられている。

モジュールリストのなかにはさらにすべてのモジュールＭの寸法および接続座標 、予め定められた位置を有するモジュール（固定されたモジュール）の幾何学的 場所ならびに配置領域が与えられている。さらに与えられた付随条件を守るべき である。

第２図にはたとえば保持体ＴＲの一部であってよい配置領域がＰＬで示されてい る。配置ｆ　９Ｍ域ＰＬの上にモジュールＭが配列される。モジュールは可動で あってよく、またはモジュールは固定された位置を有してよい、可動モジュール はＭ。

で、また固定されたモジュールはＭｙで示されている。第２図は、たとえば周縁 に固定されたモジュールはＭ、として端子（パッド）を、また配置領域ＰＬのな かに可動モジュールＭ１、たとえばセルを存する１つのチップを示す。可動モジ ュールＭ、は大文字で示されている。

モジュールリストおよびネットリストから、すべての予め配置されないモジュー ルＭ１に対する幾何学的場所が計算される。この問題は知られており、たとえば 冒頭に記載した文献に示されている０問題は下記の数学的モデルにより記述され る。

ベクトルＸおよびｙの未知の座標を が極小になるように、またｒの配置領域または部分領域ＰＬＴの各々に対して付 随条件 が１≦ｒ≦已に対して守られるように決定する。

使用される式記号は下記の意味を存する。

ｍ　モジュール番号 ｎ　ネット番号 Ｍ−（・・・９ｍ、・・・）　モジエール番号の集合Ｎ−（・・・、ｎ、・・・ ）　ネット番号の集合Ｍ、ＣＭ　可動モジュールの集合 Ｍ、ＣＭ　固定されたモジュールの集合ｂ　可動モジュールの数 ｆ　固定されたモジュールの数 Ｘ−（・・・Ｘ、・・・Ｘ、・・・）　すべてのネットおよびモジュールのＸ座 標のベクトルｙ＝（・・・ｙｌｌ・・・ｙ、・・・）　すべてのネットおよびモ ジュールのＸ座標のベクトルｕｌｌｌｌ　モジュールｍへのネットｎの接続のＸ 座標■、　モジュールｍへのネットｎの接続のｙ座標ｔ−＋−＝１　ネットｎが モジュールｍに接続されている場合０　ネットｎがモジュールｍに接続されてい ない場合Ｗ、　ネットｎの重み係数 Ｆ、　モジュールｍの面需要 ｒ　配置領域ＰＬまたは部分領域ＰＬＴの番号Ｍｒ−Ｃ−Ｍ、　付随条件ｒが適 用されるモジュールの集合Ｘ、、Ｙ、　第ｒ配置領域ＰＬ、ＰＬＴの中心座標Ｒ 部分領域ＰＬＴＯ数 弐１には、接続されるネットからのモジュールの間隔、ずなわちＸ＠−Ｘｎ、Ｙ ｍ　Ｖｎが含まれており、その際にｕ１１１１％　Ｖ−によりなお、ネットがモ ジュールの中心にではなくその接続点に通ずることが考慮される。このことはた とえばモジュールＭ、が座標系内に示されている第６図かられかる。モジュール の中心はｘ、Ｘ座標により決定され、モジエールの端子の位置はモジュール中心 点に関係づけられた座標ｕ、ｖにより決定される。接続はモジュールの端子に通 ずるので、モジュールの中心座標の間の間隔は相応に補整されなければならない 。

重み係数Ｗによりネットの意味が決定され得る。ｔ、を用いて、ネットがモジエ ールに接続されているか否かが示される。

レイアウト設計に対して、いわゆる端子（パッド）の場所を配置領域ＰＬの周縁 に固定的に予め定めるのではなく、それらを４つの周縁の１つに対応付け、また 左または右の端子に対してそのＸ座標を、また上および下端子に対してそのＸ座 標を計算することは宥和である。

残糸１を用いてモジュールの座標が計算される。具象的にこの系はばね定数を有 する弾性ばねにより接続されている質点の系としても解釈され得る。その際にば ね定数は、当該のモジュールと結びつけられているふノドの重みに相応する。

こうして残糸１の解はすべてのモジュールＭ、の計算に通ずる。その重心はいま 配置領域ＰＬの特定の点に割り当てられなければならない、この理由から、配置 領域ＰＬの中心座標Ｘｒ、ｙｒを示す付随条件である式２がたてられる０残糸１ の解が付随条件２の考慮のもとに行われると、モジュールの重心はこの中心座標 上に置かれる。

第２図から配置領域ＰＬのなかの可動モジュールＭ、の位置が生ずる。モジュー ルは中心座［Ｘ、　、Ｙ、の周りに配列されている。

配置領域ＰＬに対する付随条件２の注意のもとに残糸１を解くためのより詳細な 説明は冒頭に記載したジャストの著書に示されている。使用される問題式表現は 目的関数の凸性のためにより多くの線形付随条件２の存在の際にも、一義的なグ ローバル最適条件が存在することを保証する。解は、たとえばピー・イージル、 ダブリュ・マレイ・エム・エッチ・ライト著「実際的最適化」アカデミツクプレ ス、ロンドン、１９８１年に記載されているように、効率的に二乗最適化の問題 の処理のための公知のアルゴリズムを用いて取得され得る。

第７図によれば、モジュールが配置領域ＰＬ上に式１．２に関係して配置されて いるステップＳｌにステップＳ２が続いている。いま配置領域ＰＬが分割される ものとする（第２図中に切断線ＳＬにより示されている）、すなわち、仕切りス テップでは、１つのモジュールが配列され得る領域は常にさらに制限される。

繰り返される仕切りステップの結果は方法終了時に、配置すべきモジュールとま さに同数の長方形への仕切り面の完全な分解に、従ってまた許容し得る配置に通 ずる。これは一時的なグローバル配置とは、モジュールが重なりなしにまた付属 の設計様式の規定に従って配列されることにより、相違する。

配置領域ＰＬ、ＰＬＴは幅、高さ、面積、中心座標およびこの領域内に配置され るべきモジュールの集合により記述されている。

ステップＳ２が最初に行われるときには、全配置面である配置領域ＰＬで、また この配置領域内に配列されるすべての可動モジュールＭ、の集合で開始される。

仕切りはいま２つのサブステップから成っている。

１、モジュール集合Ｍ、が部分集合に分割される０分割はグローバル配置ステッ プの際に計算されたネット長さに関する極小を表すモジュール座標ｘ、ｙに基づ いて行われる。これは水平または垂直切断線ＳＬにおいてモジュールのｙまたは Ｘ座標による分類および２つまたはそれ以上の部分集合への相応の分割により達 成される０分解が切断線ＳＬにより切断されるネットの数に関連して決定される べきであれば、切断線の付近のモジュールへの追加的なＭｉｎ−Ｃｕｔ原理の応 用も可能である。Ｍｉｎ−Ｃｕｔ原理はたとえばニー・ラウサー著「グラフ表示 に基づく一般的セルアセンブリに対するｍ１ｎ−ｃｕｔ配置アルゴリズム」デザ インーオートメーシッンーコンフエシンス、１９７９年、第１〜１０頁に記載す れている。

第２図による実施例では二分割が切断線ＳＬにより垂直方向に行われる。この場 合、二分割により達成される各部分領域ＰＬＴにできるかぎり同数のモジュール を対応付けることは目的にかなっている０部分領域ＰＬＴへのモジエールの対応 付けは第２図による実施例ではモジュールのＸ座標により行われ得る。たとえば 低いＸ座標を有するモジュールは左の部分領域に、またより高いＸ座標を有する モジュールは右の部分領域に割り当てられ得る。

２、配置領域ＰＬは配置領域を完全にまた付属のモジュール部分集合の面に比べ て覆う重ならない部分領域ＰＬＴに分解される。このことは通常、第２図中の破 線ＳＬが移動すべきであることに通ずる。水平の切断の場合には部分領域の高さ ｈｌ　゛およびり、、＃は下記のように選定される。

その際にＦ、′は部分領域ｒ′のなかのモジエールｍ′の面積であり、Ｆ、’は 他の部分領域ｒ″のなかのモジュールｍ′の面積である。この仕切りステップに より発生される部分領域ＰＬＴへの仕切り領域ＰＬの分解はいわゆるスライシン グ構造を生じ、これは後で説明する回置適化の前提条件であり、またレイアウト 設計の際に接続ネットのその後の製作に特によ（適している。

ステップＳ２の寞行後に再びグローバル仕切りステップＳ１が実行される。すな わち残糸１が新たに、ただし今度は新しい付随条件、詳細には各部分領域ＰＬＴ に対する付随条件の考慮のもとに計算される。すなわち中心座標Ｘ、およびＹ。

がいま、仕切り領域の切断により達成される部分領域ＰＬＴに関連付けられてい る。実施例では２つの部分領域であったから、いま２つの付随条件が残糸１の計 算の際に守られなければならない０式系１の計算は同時にすべてのモジュールに 対して行われ、また各部分領域ＰＬＴに対して別々には実行されない、ステップ Ｓ１（グローバル配置）の結果は第３図に示されている。この図かられかるよう に、いまやモジュールの一部は左の部分領域ＰＬＴＩに、また一部は右の部分領 域ＰＬＴ２に対応付けられている。各部分領域ＰＬＴの内側で、割り当てられた モジエールはその中心座標の周りにグループ化されている。モジュールの文字に より、どのように個々のモジエールの重心が部分領域ＰＬＴのなかで第２図の出 発点から移動しているかが認識される。

グローバル配置ステップ３１に、上記の規則に従って同様に仕切りステップＳ２ が続く、そのために各部分領域ＰＬＴＩ、ＰＬＴ２はそれぞれ切断線ＳＬ２、Ｓ Ｌ３により分割され、また新たに得られた部分領域に、グローバル仕切りの際に 得られた座標に関係して個々のモジュールが割り当てられる０部分領域の面の大 きさは再びこれらの部分領域に割り当てられたモジュールの面に比べて決定され る。

ステップＳ２に再びグローバル配置ステップｓ１が続く、すなわち残糸ｌがいま や新しい付随条件の考慮のもとに解かれる。これまでの部分領域のそのつどの二 分割の際には４つの付随条件を守る必要がある。この計算の結果は第４図に示さ れている。グローバル配置に続いて再び仕切り（ステップＳ２）が行われる。

グローバル配置Ｓ１および仕切りＳ２のステップは、各部分領域に対して最大で なお１つのモジュールが残っているかぎり、もしくは部分領域あたり最大でｋの モジュールが予定されているかぎり繰り返される。にはたとえば８であってよい 、後者の場合には、モジエールの最終的な配列を、最適な面別用が努められるス テップＳ３で実行することが必要である。

第２図ないし第５図の実施例ではたとえば第４図に通じたステップによりグロー バル配置および仕切りの継続が中断され、また第５図から生ずるモジュールの最 終的位置がステップＳ３でめられる。

最適化ステップＳ３の開始時に所与の配置領域の分解は、各部分領域に最大で予 め定められた数にのモジュールが対応付けられているように行われている。最適 化ステップで、達成されるスライシング構造の面別用はローカルにもグローバル にも改善される。

最大でに個のモジュールを有する各部分領域ＰＬＴのローカル最適化のために、 この部分領域のすべての可能な分解が決定され、またモジエールが生じた部分面 に対応付けられる。この最適化の際にグローバル配置の結果が考慮され、従って 最適化のための費用が減ぜられる。各分解およびモジュール対応付けに対して、 モジュールが重なりなしに配置され得る最小の長方形領域の寸法がスライシング ′ｆ７７図 国際調査報告 国際調査報告 ＤＥ　８９００６８８ Ｓ＾　３１９１２

Claims (12)

【特許請求の範囲】
1. １．モジュールの寸法を含んでいるモジュールリストおよびモジュールの接続を 含んでいるネットリストの使用のもとに１つの保持体（ＴＲ）の上にモジュール （Ｍ）を配置するための方法において、ａ）すべての可動モジュール（Ｍｂ）が 保持体（ＴＲ）の配置領域（ＰＬ）の上にグローバル配置により、モジュールの 重心が配置領域の予め定められた点（Ｘｒ、Ｙｒ）の上に位置するように配列さ れ、またすべての固定されたモジュール（Ｍｆ）が配置領域の周縁に配列され、 ｂ）配置領域が部分領域（ＰＬＴ）に分割され（仕切られ）、その際にｂ１）ス テップａ）で決定されたモジュールの位置に基づいてこれらが部分領域（ＰＬＴ ）に対応付けられ、 ｂ２）部分領域の大きさが部分領域のなかに配列すべきモジュールに比較して決 定され、 ｃ）モジュール（Ｍ）がグローバル配置で部分領域（ＰＬＴ）のなかに、その重 心がそれぞれ対応付けられている部分領域の予め定められた点（Ｘｒ、Ｙｒ）の 上に位置するように配列され、 ｄ）部分領域が別の部分領域に分割され、その場合にｄ１）ステップｃ）で決定 されたモジュールの位置に基づいてこれらが別の部分領域（ＰＬＴ）に対応付け られ ｄ２）また別の部分領域の大きさが別の部分領域のなかに配列すべきモジュール に比較して決定され、 ｅ）ステップｃ）およびｄ）が、各部分領域にｋ個のモジュールが対応付けられ るまで繰り返される ことを特徴とする保持体上にモジュールを配置するための方法。
2. ２．配置領域および部分領域の予め定められた点がそれらの中心座標（Ｘｒ、Ｙ ｒ）であることを特徴とする請求の範囲１記載の方法。
3. ３．グローバル配置のためにモジュールのｘ、ｙ座標が同時に▲数式、化学式、 表等があります▼ が極小になり、また配置領域（ＰＬ）または各部分領域（ＰＬＴ）に対して付随 条件 ▲数式、化学式、表等があります▼および▲数式、化学式、表等があります▼ １≦ｒ≦Ｒに対して ここで ｍ　　　　　　　　　　　　　モジュール番号ｎ　　　　　　　　　　　　　ネ ット番号Ｍ＝（・・・，ｍ，・・・）　モジュール番号の集合Ｎ＝（・・・，ｎ ，・・・）　ネット番号の集合ＭｂＣＭ　　　　　　　　　　可動モジュールの 集合ＭｆＣＭ　　　　　　　　　　固定されたモジュールの集合ｂ　　　　　　 　　　　　　　可動モジュールの数ｆ　　　　　　　　　　　　　固定されたモ ジュールの数ｘ＝（・・・ｘｎ・・・ｘｍ・・・）すべてのネットおよびモジュ ールのｘ座標のベクトルｙ＝（・・・ｙｎ・・・ｙｍ・・・）すべてのネットお よびモジュールのｙ座標のベクトルｕｎｍ　　　　　　　　　　　モジュールｍ へのネットｎの接続のｘ座標Ｖｎｍ　　　　　　　　　　　モジュールｍへのネ ットｎの接続のｙ座標ｔｎｍ＝１　　　　　　　　　ネットｎがモジュールｍに 接続されている場合　　　　０　　　　　　　　　ネットｎがモジュールｍに接 続されていない場合Ｗｎ　　　　　　　　　　　　ネットｎの重み係数Ｆｍ　　 　　　　　　　　　　モジュールｍの面需要ｒ　　　　　　　　　　　　　配置 領域ＰＬまたは部分領域ＰＬＴの番号Ｍｒ■Ｍｂ　　　　　　　　　付随条件ｒ が適用されるモジュールの集合Ｘｒ，Ｙｒ　　　　　　　　　第ｒ配置領域ＰＬ 、ＰＬＴの中心座標Ｒ　　　　　　　　　　　　　部分領域ＰＬＴの数が守られ るように決定されることを特徴とする請求の範囲２記載の方法。
4. ４．固定されるモジュール（Ｍｆ）が配置領域（ＰＬ）の周縁においてｘまたは ｙ方向に移動可能であることを特徴とする請求の範囲３記載の方法。
5. ５．部分領域（ＰＬＴ）へのモジュール（Ｍ）の割り当てがそのｘ、ｙ座標によ るモジュールの分類により行われることを特徴とする請求の範囲４記載の方法。
6. ６．配置領域および部分領域の分割が水平および垂直切断線（ＳＬ）により行わ れ、また切断により達成される部分領域にモジュール部分集合（Ｍｒ）が割り当 てられることを特徴とする請求の範囲５記載の方法。
7. ７．各領域の二分割がそれぞれ仕切りの際に行われることを特徴とする請求の範 囲６記載の方法。
8. ８．対応付けられている接続が切断線（ＳＬ）を超過するモジュール（Ｍ）が部 分領域（ＰＬＴ）にＭｉｎ−Ｃｕｔ原理の追加的な応用のもとに対応付けられる ことを特徴とする請求の範囲７記載の方法。
9. ９．グローバル配置および仕切りが、各部分領域のなかに１つのモジュール（Ｍ ）（ｋ−１）が配列されているときに終了されることを特徴とする請求の範囲１ ないし８の１つに記載の方法。
10. １０．最適な面利用がグローバル配置の結果の利用のもとにｋまでのモジュール （Ｍ）を有する部分領域（ＰＬＴ）のすべての可能な分割の決定により行われる ことを特徴とする請求の範囲１ないし８の１つに記載の方法。
11. １１．部分領域（ＰＬＴ）のなかのモジュール（Ｍ）の配列が、各部分領域に対 してすべての可能な分解が決定され、またモジュールが生じた部分面に対応付け られ、各分解およびモジュール対応付けに対して，モジュールが重なりなしに配 置され得る最小の長方形の領域の寸法が計算され、かつ部分面の種々の可能な寸 法が形状関数にまとめられ、またこれがすべての部分領域（ＰＬＴ）に対して実 行され、かつすべての部分領域の形状関数の加算によりすべての許容されるモジ ュール配列の寸法が計算されることにより最適化されることを特徴とする請求の 範囲１０記載の方法。
12. １２．モジュールの回転位置が最適化されることを特徴とする請求の範囲１１記 載の方法。