(57)【要約】【課題】  平面上に複数の矩形要素を配置する際の対称配置制約及び相対位置関係に係る制約（sequence-pair制約）を共に満たす最適配置解を求める。【解決手段】  データ／操作指示入力部３０１からの入力によって、矩形要素集合取得・保持部３０２が、複数の矩形要素のそれぞれの識別情報と、各矩形要素の高さ及び幅の値を取得、保持する。また、seq-pair制約条件取得・設定部３０３は、これらの複数の矩形要素の相対位置関係を示す制約条件を取得し、これらの制約条件を線形の制約式に変換する。また、対称配置制約条件取得・設定部３０４は、矩形要素の対称配置制約条件を取得し、この対称配置制約条件を線形の制約式に変換する。そして、線形計画法演算部３０５が、相対位置関係に基づく制約式、及び対称配置制約条件に基づく制約式を使用して、線形計画法による演算を行い、平面上に複数の矩形要素を最密に配置する際の各矩形要素の配置位置を決定する。【選択図】  図３
2006309748.tif 000002
【特許請求の範囲】
【請求項１】
平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置方法であって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得ステップと、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得ステップと、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得ステップと、
前記矩形要素集合取得ステップで取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算ステップと、
前記線形計画法演算ステップにおける前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力ステップとを、
有する矩形要素配置方法。
【請求項２】
前記線形計画法演算ステップにおける前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知ステップを有する請求項１に記載の矩形要素配置方法。
【請求項３】
平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置装置であって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得手段と、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得手段と、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得手段と、
前記矩形要素集合取得手段で取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算手段と、
前記線形計画法演算手段における前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力手段とを、
有する矩形要素配置装置。
【請求項４】
前記線形計画法演算手段における前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知手段を有する請求項３に記載の矩形要素配置装置。
【請求項５】
平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置方法をコンピュータによって実行させるための矩形要素配置用プログラムであって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得ステップと、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得ステップと、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得ステップと、
前記矩形要素集合取得ステップで取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算ステップと、
前記線形計画法演算ステップにおける前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力ステップとを、
有する矩形要素配置方法をコンピュータによって実行させるための矩形要素配置用プログラム。
【請求項６】
前記線形計画法演算ステップにおける前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知ステップを有する矩形要素配置方法をコンピュータによって実行させるための請求項５に記載の矩形要素配置用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平面上に複数の矩形要素（以下、モジュールと記載することもある）を最密に配置する際のレイアウト設計を行うための矩形要素配置方法及び矩形要素配置装置並びに矩形要素配置用プログラムに関し、特に、アナログＩＣのレイアウト設計を行うための矩形要素配置方法及び矩形要素配置装置並びに矩形要素配置用プログラムに関する。なお、本明細書では、矩形とは、長方形及び正方形を含む直角四辺形を指す。
【背景技術】
【０００２】
従来、ＩＣチップ上に様々な回路を最密に配置するための配置位置を決定する方法として、例えば、特許文献１、２や非特許文献１に開示されているｓｅｑｕｅｎｃｅ−ｐａｉｒ（シーケンスペア、以下ｓｅｑ−ｐａｉｒとも記載する）と呼ばれる概念を用いた方法が知られている。なお、ｓｅｑ−ｐａｉｒは、どんな矩形パッキングでも表現可能であるという特徴を有する。
【０００３】
ｓｅｑ−ｐａｉｒでは、ｎ個の矩形要素の相対位置関係を、矩形要素名の順列Γ+及びΓ-の対により、（Γ+，Γ-）の形で表す。ここで、Γ+（ｉ）はΓ+中で第ｉ番目の矩形を指し、Γ+-1（ａ）はΓ+中で矩形要素ａが左から何番目かを指すものと定義すする。Γ-についても同様である。なお、当然、ｎ個の矩形要素の配置について（ｎ！）2通りの表現がある。
【０００４】
また、ｓｅｑ−ｐａｉｒでは、矩形要素対の相対位置関係を、以下に示す「上下左右制約」として表す。Γ+とΓ-で共にａがｂの前にあるとき、すなわちΓ+-1（ａ）＜Γ+-1（ｂ）かつΓ--1（ａ）＜Γ--1（ｂ）であるとき、矩形ａは矩形ｂの上に位置する。また、Γ+ではａがｂの前にありΓ-ではａがｂの後ろにあるとき、すなわちΓ+-1（ａ）＜Γ+-1（ｂ）かつΓ--1（ａ）＞Γ--1（ｂ）であるとき、矩形ａは矩形ｂの上に位置する。例えば、ｓｅｑ−ｐａｉｒ（ｂlｂrｃａlｄａr；ａlｃｂlｂrｄａr）は図８に図示されているような相対位置関係を表す。
【０００５】
一方、高性能アナログＩＣにおけるレイアウト設計では、しばしば指定されたいくつかのモジュール対を線対称に配置配線する必要がある。その理由は、モジュールやそれと接続する配線のレイアウト、及びそれによって生ずる寄生素子（レイアウト設計時には予測が困難な相互作用によって発生する寄生キャパシタ、寄生インダクタ、寄生抵抗など）の整合を取ることで、オフセット電圧が高くなることや、電源電圧変動比（ＰＳＲＲ）の低下を避けるためである。また、熱に敏感なモジュール対においては熱の影響により生ずる不要な発振を避けるためにも、発熱の大きいモジュールに対して対称配置することで熱の影響のバランスを取るべきである。このように、指定されたモジュール対を線対称に配置しなければならないという制約を対称配置制約と呼ぶ。
【０００６】
対称配置制約は、複数のモジュール対からなる対称集合により表され、その中の各モジュール対を、共通の垂直な軸（ｙ軸に平行な軸）又は水平な軸（ｘ軸に平行な軸）に対して線対称になるように配置する制約である。また、対称集合には、１つのモジュールを対称軸に対して対称に配置する制約が課せられた自己対称モジュールが含まれる場合もある。これはたとえば、対称軸のｘ座標にその中心を合わせなければならないモジュールである。なお、対称集合は１つとは限らず、各々の対称集合ごとに１本の水平又は垂直な軸に対して対称に、その集合に含まれるモジュール対が配置される。
【０００７】
垂直な対称軸に対して、対称に配置するモジュール対の左のモジュールを左モジュール、右のモジュールを右モジュールと呼び、それぞれａl、ａrのように添え字ｌ（「エル」）、ｒを付けて表す。また、水平な対称軸に対して、対称に配置するモジュール対の上のモジュールを上モジュール、下のモジュールを下モジュールと呼び、それぞれａu、ａbのように添え字ｕ、ｂを付けて表す。また、対称軸に対して対称に配置する制約が課せられた自己対称モジュールに関しては、ｂsのように添え字ｓを付けて表す。また、対称集合は対称に配置するモジュール対を括弧でまとめ、｛（ａl，ａr），ｂs｝のように表記する。そして、対称集合を列挙することで対称配置制約を表現する。
【０００８】
これまで、アナログＩＣ設計では人手による設計が主流であったが、近年では、矩形配置表現とシミュレーテッドアニーリング（ＳＡ：Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）法とを組み合わせた自動配置手法に対し、対称配置制約を課して準最適な配置を得る手法（例えば特許文献３や非特許文献２を参照）が提案されている。
【０００９】
また、特許文献３や非特許文献２では、与えられた対称配置制約と、モジュール配置表現方法であるｓｅｑ−ｐａｉｒが示唆する制約（ｓｅｑ−ｐａｉｒ制約）とを共に満たす配置が存在することの必要十分条件は、各対称集合が式（１）を満たすことであると記載されている。
【００１０】
Γ+-1（ｘ）＜Γ+-1（ｙ）
⇔Γ--1（ｓｙｍ（ｙ））＜Γ--1（ｓｙｍ（ｘ））      ・・・（１）
【００１１】
なお、ｓｙｍ（ｘ）は、あるモジュールｘに対して対称に配置されるべきモジュールを表しており、対称軸が垂直線である場合には、上記の式（１）は、下記の式（２）のように表される。
【００１２】
Γ+-1（ｘl）＜Γ+-1（ｙl）
⇔Γ--1（ｙr）＜Γ--1（ｘr）      ・・・（２）
【００１３】
そして、特許文献３や非特許文献２では、この必要十分条件を満たすｓｅｑ−ｐａｉｒ（ｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒと呼ばれている）をあらかじめ選択し、このｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒのみを対象としてＳＡ法を用いて探索を行うことにより、対称配置制約を満たす準最適なモジュール配置解を得る方法が提案されている。
【００１４】
また、さらに特許文献３及び非特許文献２の考え方に基づいて、ｓｅｑ−ｐａｉｒを高速にデコードするＦＡＳＴ−ＳＰ（ＦＡＳＴ  Ｓｅｑｕｅｎｃｅ−Ｐａｉｒ）を用いた手法、ｓｅｑ−ｐａｉｒよりも高速にデコード可能な矩形配置表現であるＯ−ｔｒｅｅ（Ｏｒｄｅｒｅｄ−ｔｒｅｅ）を用いた手法（非特許文献３参照）、Ｏ−ｔｒｅｅを２分木にしただけのＢ*−ｔｒｅｅ（Ｂｉｎａｒｙ−ｔｒｅｅ）を用いた手法（非特許文献４、５、６参照）、平衡木の１つである赤黒木を用いた手法（非特許文献７、８参照）が提案されている。
【００１５】
一方、非特許文献９には、線形計画法を用いてｓｅｑ−ｐａｉｒ制約を解くことによって、ｓｅｑ−ｐａｉｒ制約を満たす最適なモジュール配置解を得る手法が開示されている。
【特許文献１】特開平９−１０８９３３号公報
【特許文献２】特開平９−１０８９３４号公報
【特許文献３】米国特許６５５００４６号
【非特許文献１】Ｈ．  Ｍｕｒａｔａ，  Ｋ．  Ｆｕｊｉｙｏｓｈｉ，  Ｓ．  Ｎａｋａｔａｋｅ  ａｎｄ  Ｙ．  Ｋａｊｉｔａｎｉ，  “Ｒｅｃｔａｎｇｌｅ−ｐａｃｋｉｎｇ−ｂａｓｅｄ  ｍｏｄｕｌｅ  ｐｌａｃｅｍｅｎｔ”，  Ｐｒｏｃ．  ＩＥＥＥ  ＩＣＣＡＤ，  ｐｐ．４７２−４７９，  １９９５．
【非特許文献２】Ｆ．  Ｂａｌａｓａ  ａｎｄ  Ｌ．  Ｌａｍｐａｅｒｔ，  “Ｓｙｍｍｅｔｒｙ  ｗｉｔｈｉｎ  ｔｈｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｉｎ  ｔｈｅ  ｃｏｎｔｅｘｔ  ｏｆ  ｐｌａｃｅｍｅｎｔ  ｆｏｒ  ａｎａｌｏｇ  ｄｅｓｉｇｎ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ＣＡＤ，  ｖｏｌ．１９，  ｎｏ．７，  ｐｐ．７２１−７３１，  ２０００．
【非特許文献３】Ｙ．  Ｐａｎｇ，  Ｆ．  Ｂａｌａｓａ，  Ｋ．  Ｌａｍｐａｅｒｔ  ａｎｄ  Ｃ．−Ｋ．  Ｃｈｅｎｇ，  “Ｂｌｏｃｋ  ｐｌａｃｅｍｅｎｔ  ｗｉｔｈ  ｓｙｍｍｅｔｒｙ  ｃｏｎｓｔｒａｉｎｔｓ  ｂａｓｅｄ  ｏｎ  ｔｈｅ  Ｏ−ｔｒｅｅ  ｎｏｎ−ｓｌｉｃｉｎｇ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ”，  Ｐｒｏｃ．ＤＡＣ，  ｐｐ．４６４−４６７，  ２０００．
【非特許文献４】Ｆ．  Ｂａｌａｓａ，  Ｓ．Ｃ．  Ｍａｒｕｖａｄａ  ａｎｄ  Ｋ．  Ｋｒｉｓｈｎａｍｏｏｒｔｈｙ，  “Ｏｎ  ｔｈｅ  ｅｘｐｌｏｒａｔｉｏｎ  ｏｆ  ｔｈｅ  ｓｏｌｕｔｉｏｎ  ｓｐａｃｅ  ｉｎ  ａｎａｌｏｇ  ｐｌａｃｅｍｅｎｔ  ｗｉｔｈ  ｓｙｍｍｅｔｒｙ  ｃｏｎｓｔｒａｉｎｔｓ”，  ＩＥＥＥ  Ｔｒａｎｓ．  ＣＡＤ，  ｖｏｌ．２３，  ｎｏ．２，  ｐｐ．１７７−１９１，  ２００４．
【非特許文献５】Ｆ．  Ｂａｌａｓａ  ａｎｄ  Ｓ．Ｃ．  Ｍａｒｕｖａｄａ，  “Ｕｓｉｎｇ  ｎｏｎ−ｓｌｉｃｉｎｇ  ｔｏｐｏｌｏｇｉｃａｌ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｏｒ  ａｎａｌｏｇ  ｐｌａｃｅｍｅｎｔ”  ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｆｕｎｄａｍｅｎｔａｌｓ，  ｖｏｌ．Ｅ８４−Ａ，  ｎｏ．１１，  ｐｐ．２７８５−２７９２，  ２００１．
【非特許文献６】Ｆ．  Ｂａｌａｓａ，  Ｓ．Ｃ．  Ｍａｒｕｖａｄａ  ａｎｄ  Ｋ．  Ｋｒｉｓｈｎａｍｏｏｒｔｈｙ，  “Ｅｆｆｉｃｉｅｎｔ  ｓｏｌｕｔｉｏｎ  ｓｐａｃｅ  ｅｘｐｌｏｒａｔｉｏｎ  ｂａｓｅｄ  ｏｎ  ｓｅｇｍｅｎｔ  ｔｒｅｅｓ  ｉｎ  ａｎａｌｏｇ  ｐｌａｃｅｍｅｎｔ  ｗｉｔｈ  ｓｙｍｍｅｔｒｙ  ｃｏｎｓｔｒａｉｎｔｓ”  Ｐｒｏｃ．  ＩＣＣＡＤ，  ｐｐ．４９７−５０２，  ２００２．
【非特許文献７】Ｓ．Ｃ．  Ｍａｒｕｖａｄａ，  Ｋ．  Ｋｒｉｓｈｎａｍｏｏｒｔｈｙ，  Ｓ．  Ａｎｎｏｊｖａｌａ  ａｎｄ  Ｆ．  Ｂａｌａｓａ，  “Ｐｌａｃｅｍｅｎｔ  ｗｉｔｈ  ｓｙｍｍｅｔｒｙ  ｃｏｎｓｔｒａｉｎｔｓ  ｆｏｒ  ａｎａｌｏｇ  ｌａｙｏｕｔ  ｕｓｉｎｇ  ｒｅｄ−ｂｌａｃｋ  ｔｒｅｅｓ”  Ｐｒｏｃ．  ＩＳＣＡＳ２００３，  ｐｐ．Ｖ−４８９−Ｖ−４９２，  ２００３．
【非特許文献８】Ｓ．Ｃ．  Ｍａｒｕｖａｄａ，  Ｋ．  Ｋｒｉｓｈｎａｍｏｏｒｔｈｙ，    Ｆ．  Ｂａｌａｓａ  ａｎｄ  Ｌ．Ｍ．  Ｉｏｎｅｓｃｕ，  “Ｒｅｄ−ｂｌａｃｋ  ｉｎｔｅｒｖａｌ  ｔｒｅｅｓ  ｉｎ  ｄｅｖｉｃｅ−ｌｅｖｅｌ  ａｎａｌｏｇ  ｐｌａｃｅｍｅｎｔ”  ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｆｕｎｄａｍｅｎｔａｌｓ，  Ｖｏｌ．Ｅ８６−Ａ，  ｎｏ．１２，  ｐｐ．３１２７−３１３５，  ２００３．
【非特許文献９】Ｊａｅ−Ｇｏｎ  Ｋｉｍ  ａｎｄ  Ｙｅｏｎｇ−Ｄａｅ  Ｋｉｍ，  “Ａ  ｌｉｎｅａｒ  ｐｒｏｇｒａｍｍｉｎｇ−ｂａｓｅｄ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｆｌｏｏｒｐｌａｎｎｉｎｇ  ｉｎ  ＶＬＳＩ  ｄｅｓｉｇｎ”，  ＩＥＥＥ  Ｔｒａｎｓ．ＣＡＤ，  ｖｏｌ．２２，  ｎｏ．５，  ｐｐ５８４−５９２，  ２００３．
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、特許文献３や非特許文献２には、下記の４つの問題点（Ａ）〜（Ｄ）が存在する。以下、問題点（Ａ）〜（Ｄ）を順に説明する。
【００１７】
（Ａ）ｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒの妥当性
上述のように、特許文献３や非特許文献２に開示されている技術によれば、ｓｅｑ−ｐａｉｒ制約及び対称配置制約の両方を満たす配置が存在するための必要十分条件は、式（１）や式（２）によって表される。
【００１８】
しかしながら、対称集合｛（ａl，ａr），（ｂl，ｂr）｝で表される対称配置制約を満たす最適なモジュール配置は図８に図示されている配置のみであり、この配置に対応するｓｅｑ−ｐａｉｒはｓｅｑ−ｐａｉｒ（ｂlｂrｃａlｄａr；ａlｃｂlｂrｄａr）だけである。このｓｅｑ−ｐａｉｒは、Γ+-1（ｂl）＜Γ+-1（ａl）ではあるが、Γ--1（ａr）＜Γ--1（ｂr）ではなく、式（１）や式（２）を満たしていない。したがって、式（１）や式（２）は、ｓｅｑ−ｐａｉｒ制約及び対称配置制約の両方を満たす配置が存在するための十分条件ではあるかもしれないが、必要条件ではない。
【００１９】
特許文献３や非特許文献２に開示されている技術では、あらかじめ式（１）や式（２）に基づいてｓｅｑ−ｐａｉｒの選択を行った後に、選択されたｓｅｑ−ｐａｉｒ（すなわち、ｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒ）に関してのみＳＡ法による探索が行われるので、ｓｅｑ−ｐａｉｒ制約及び対称配置制約の両方を満たす最密配置解が見落とされてしまう可能性があるという問題点がある。
【００２０】
（Ｂ）ｘ座標決定アルゴリズム
また、特許文献３や非特許文献２に開示されている技術に係るｘ座標決定アルゴリズムは、対称軸が垂直軸（ｙ軸に平行な軸）である対称集合が１つの場合にのみ対応している。このｘ座標決定アルゴリズムでは、モジュールの幅、対称配置制約、ｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒが入力される。そして、最初にｓｅｑ−ｐａｉｒに基づいて左詰めにｘ座標を求め、対称配置制約によって規定されている対称に配置すべきモジュール対に関して、左モジュールの左辺ｘ座標と右モジュールの右辺ｘ座標との中心のｘ座標（左モジュールの左辺ｘ座標及び右モジュールの右辺ｘ座標の両方から等距離となるｘ座標）、及び自己対称モジュールの中心のｘ座標のうちの最も大きいものを対称軸のｘ座標と決める。
【００２１】
その後、右モジュール及び自己対称モジュールをΓ+順に１つずつ、右に移動することによって上記の対称軸に対して線対称となる場合に移動し、また、このモジュールの移動に伴って、ｓｅｑ−ｐａｉｒ制約により移動するモジュールよりも右にあると制約されているモジュールも、すべて同じ距離だけ移動させる。次に、左モジュールをΓ+の逆順に１つずつ、上記の対称軸に対して線対称となる位置まで移動し、ｓｅｑ−ｐａｉｒ制約により移動するモジュールよりも左にあると制約されているモジュールも、すべて同じ距離だけ移動させる。
【００２２】
しかしながら、このｘ座標決定アルゴリズムに、例えば、すべて同じサイズの正方形モジュールの集合｛ａs，ｂl，ｂr，ｃl，ｃr｝と対称配置制約｛ａs，（ｂl，ｂr），（ｃl，ｃr）｝、そしてｓｅｑ−ｐａｉｒ（ｂlａsｃlｃrｂr；ｂlｃlｃrａsｂr）を入力した場合には、まずｓｅｑ−ｐａｉｒに基づいて左詰めにｘ座標が求められた後、ｃlとｃrとの中心のｘ座標が対称軸の座標として選択され、図９（Ａ）に図示される配置となる。
【００２３】
そして、この対称軸に関して線対称となるように自己対称モジュールａsが右に移動するが、このとき、ｓｅｑ−ｐａｉｒによってａsよりも右にあると制約されているｂrも同じ距離だけ右に移動されてしまい、その結果、図９（Ｂ）に図示される配置となってしまう。さらに、ｂrとの対称性が満たされるようにｂlも左に移動するため、図９（Ｄ）に図示される最密な配置よりも幅の広がった図９（Ｃ）に図示される配置が導かれてしまう。このように、特許文献３や非特許文献２に開示されている技術に係るｘ座標決定アルゴリズムは、必ずしも対称配置制約及びｓｅｑ−ｐａｉｒ制約の下で最密な配置を導くことができるとは限らないという問題点がある。
【００２４】
（Ｃ）ｙ座標決定アルゴリズム
また、特許文献３や非特許文献２に開示されている技術に係るｙ座標決定アルゴリズムも、上記のｘ座標決定アルゴリズムと同様に、対称軸が水平軸（ｘ軸に平行な軸）である対称集合が１つの場合にのみ対応している。このｙ座標決定アルゴリズムでは、モジュールの高さ、対称配置制約、ｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒが入力される。そして、ｓｅｑ−ｐａｉｒに基づいて、Γ+の逆順にモジュールのｙ座標を１つずつ決定していくが、対称に配置すべきモジュール対の一方（すなわち、左モジュール若しくは右モジュール）のｙ座標が決定された場合には、対となる他方のモジュールのｙ座標も同一の値とする。
【００２５】
このｙ座標決定アルゴリズムに、例えば、対称配置制約｛（ａl，ａr）｝とｓｅｑ−ｐａｉｒ（ａlｂｃａr；ｂａlａrｃ）とを入力すると、まずａrのｙ座標が決定される。このとき、ａlのｙ座標もａrのｙ座標と同じｙ座標となる。なお、図１０（Ａ）に示すように、ｓｅｑ−ｐａｉｒ制約によってａrの上にはｃが存在する。その後、ｂのｙ座標を決定し、図１０（Ｂ）に示すように、ｓｅｑ−ｐａｉｒ制約に基づいてｂ上にａlを配置してから、ａrのｙ座標をａlのｙ座標と同じにする。しかしながら、ａrの上にはｃが存在しており、その結果、図１０（Ｃ）に示すように、ｃとａrとが重なった配置が導かれることになる。このように、図１０（Ｄ）に示されている配置が可能であるにもかかわらず、特許文献３や非特許文献２に開示されている技術に係るｙ座標決定アルゴリズムによれば、図１０（Ｃ）に示されている配置が導かれることとなり、ｓｅｑ−ｐａｉｒの制約を満たさない配置を導いたり、モジュール同士が重なり合ってしまう配置を導いたりするという問題点がある。
【００２６】
（Ｄ）対称集合が複数存在する場合
対称集合が複数存在する場合については、特許文献３や非特許文献２では簡単に拡張できるとだけ記載されている。しかしながら、例えば対称配置制約｛（ａl1，ａr1）｝及び｛（ｂl2，ｂr2）｝をｓｅｑ−ｐａｉｒ（ａl1ｂl2ｂr2ａr1；ｂl2ａl1ａr1ｂr2）に基づいて配置しようとすると、このｓｅｑ−ｐａｉｒはそれぞれの対称集合についてｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒであるが、ａl1の下にｂl2が、ａr1の上にｂr2が制約され、ｓｅｑ−ｐａｉｒ制約と対称配置制約とを同時に満たすことができない。特許文献３や非特許文献２では、このような配置不可能なｓｅｑ−ｐａｉｒの存在については何も記載されていないという問題点がある。上記のような配置不可能な例に対しては、配置不可能であると出力されるべきである。なお、本明細書では、それぞれ異なる対称軸を有する複数の対称集合が存在する場合の対称配置制約を、上記の対称配置制約｛（ａl1，ａr1）｝及び｛（ｂl2，ｂr2）｝のように、対称集合の列挙によって表記する。
【００２７】
以上のように、特許文献３や非特許文献２に開示されている技術は、モジュールが重なってしまったり、全体の幅が広がって最密な配置を得ることができなかったり、表現できない配置が存在したりするなどの数多くの欠陥が存在している。したがって、特許文献３や非特許文献２に開示されている技術によって得られた配置をそのままＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）やＶＬＳＩ（Ｖｅｒｙ  Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）のレイアウト設計に適用した場合には、チップ面積や配線長の増大を招くことになり、レイアウト設計上、望ましくない結果が得られてしまうことになる。
【００２８】
また、非特許文献３〜８に開示されている技術は、いずれも特許文献３や非特許文献２に開示されている技術に基づいて、効率的かつ迅速な処理を図るものであり、上述の問題点（Ａ）〜（Ｄ）の解決は行われていない。
【００２９】
また、非特許文献９に開示されている技術では、対称配置制約に関しては全く考慮されておらず、仮に、特許文献３や非特許文献２に開示されている技術と組み合わせて対称配置制約を考慮した配置の導出を行った場合でも、例えば、特許文献３や非特許文献２に開示されている技術に係るｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒがあらかじめ選択される時点で、最密配置解が見落とされてしまう可能性が発生してしまい、対称配置制約及びｓｅｑ−ｐａｉｒ制約を共に満たす最適配置解を見つけるために十分なアルゴリズムを実現することはできない。
【００３０】
上記の問題点に鑑み、本発明は、対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることが可能な矩形要素配置方法及び矩形要素配置装置並びに矩形要素配置用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３１】
上記目的を達成するため、本発明によれば、たとえばアナログＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：集積回路）のレイアウト設計において、矩形要素に関する所定の対称配置制約及び所定の相対位置関係に係る制約を同時に満たす最密な配置を、線形計画法を利用して得ることが可能となる。さらに、本発明によれば、矩形要素に関する所定の対称配置制約及び所定の相対位置関係に係る制約を同時に満たす解が存在しない場合には、その旨を通知することが可能となる。
【００３２】
すなわち、上記目的を達成するため、本発明の矩形要素配置方法によれば、
（１）「平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置方法であって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得ステップと、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得ステップと、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得ステップと、
前記矩形要素集合取得ステップで取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算ステップと、
前記線形計画法演算ステップにおける前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力ステップとを、
有する矩形要素配置方法。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることが可能となる。
本発明では、周知手法、たとえば従属変数の消去や式の消去により、前記線形計画法演算ステップにおける演算量を削減することは容易である。具体的には、本発明では、矩形要素の組み合わせ（すなわち、「ｓｅｑ−ｐａｉｒ」）の全てについて、線形計画法による演算を行うことができる。
また、奥田等による、“対称性保持の制約を扱えるレイアウトコンパクションアルゴリズム”（電子情報通信学会論文誌（Ａ），Ｖｏｌ．Ｊ７０−Ａ，Ｎｏ．３，ｐｐ．５３６−５４３，１９９０）に開示の手法を適用して、簡易化制約グラフを得ておき、対称性を持つｓｅｑ−ｐａｉｒのみを、線形計画法の演算対象とすることができる。簡易化制約グラフは、その都度求めることもできるし、予めデータベース化しておくこともできる。これにより簡易化制約グラフおける節点についての経路長が他の節点を経由する経路長と同じ長さの経路となったときは、線形計画法における連立式のうちの１つまたは２つ以上を省略する演算を行うことができる。
線形計画法では、ｓｅｑ−ｐａｉｒから得られる不等式と対称配置制約から得られる等式とからなる連立式を解くことで、最密配置解を算出するので、対称性を持つｓｅｑ−ｐａｉｒのみを線形計画法の演算対象とすることで、連立式の個数を削減できるケースが多くなる。すなわち、対称配置制約から得られる対応式を、前記対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせの一方の矩形に対応する変数、および前記自己対称となる前記矩形要素に対応する変数についてまとめることができる。まとめた式を、ｓｅｑ−ｐａｉｒから得られた不等式に代入することにより、線形計画法における連立式のうちのさらに１つまたは２つ以上を省略する演算を行うこともできる。さらに等式の数だけ、変数も省略することができる。
【００３３】
また、本発明の矩形要素配置方法によれば、上記の矩形要素配置方法に加えて、
（２）「前記線形計画法演算ステップにおける前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知ステップを有する矩形要素配置方法。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす矩形要素の配置が不可能な旨を通知することが可能となる。
【００３４】
上記目的を達成するため、本発明の矩形要素配置装置によれば、
（３）「平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置装置であって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得手段と、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得手段と、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得手段と、
前記矩形要素集合取得手段で取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算手段と、
前記線形計画法演算手段における前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力手段とを、
有する矩形要素配置装置。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることが可能となる。
【００３５】
また、本発明の矩形要素配置装置によれば、上記の矩形要素配置装置に加えて、
（４）「前記線形計画法演算手段における前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知手段を有する矩形要素配置装置。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす矩形要素の配置が不可能な旨を通知することが可能となる。
【００３６】
上記目的を達成するため、本発明の矩形要素配置用プログラムによれば、
（５）「平面上における複数の矩形要素の配置が最密となるように、前記複数の矩形要素のそれぞれの配置位置を決定する矩形要素配置方法をコンピュータによって実行させるための矩形要素配置用プログラムであって、
前記平面上に配置する前記複数の矩形要素の集合を取得する矩形要素集合取得ステップと、
前記複数の矩形要素のそれぞれに関して、左右方向及び上下方向の位置関係が記述された相対位置関係に係る制約条件を取得する相対位置関係制約条件取得ステップと、
前記複数の矩形要素のうち、対称軸を挟んで前記左右方向又は前記上下方向に対称となる前記矩形要素の組み合わせ、又は対称軸を挟んで自己対称となる前記矩形要素が記述された対称配置制約に係る制約条件を取得する対称配置制約条件取得ステップと、
前記矩形要素集合取得ステップで取得された前記複数の矩形要素の集合に対して、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件を課して、線形計画法による演算を行う線形計画法演算ステップと、
前記線形計画法演算ステップにおける前記演算によって得られた最適解を、前記平面上における前記複数の矩形要素の配置の最密配置解として出力する最密配置解出力ステップとを、
有する矩形要素配置方法をコンピュータによって実行させるための矩形要素配置用プログラム。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることが可能となる。
【００３７】
また、本発明の矩形要素配置用プログラムによれば、上記の矩形要素配置用プログラムに加えて、
（６）「前記線形計画法演算ステップにおける前記演算によって解が得られなかった場合には、前記相対位置関係に係る制約条件及び前記対称配置制約に係る制約条件の両方を満たす前記平面上における前記複数の矩形要素の配置が存在しない旨を出力する配置不可能通知ステップを有する矩形要素配置方法をコンピュータによって実行させるための矩形要素配置用プログラム。」が提供される。
この構成により、対称配置制約及び相対位置関係に係る制約を共に満たす矩形要素の配置が不可能な旨を通知することが可能となる。
【発明の効果】
【００３８】
本発明は、上記の構成を有しており、平面上に複数の矩形要素を配置する際の対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることができるという効果を有している。
また、本発明は、対称配置制約及び相対位置関係に係る制約を共に満たす矩形要素の配置が不可能な場合には、その旨を通知することができるという効果を有している。
【発明を実施するための最良の形態】
【００３９】
《第１実施形態》
以下、図面を参照しながら、本発明の第１実施形態について説明する。
まず、図１を参照しながら、本発明の適用が可能なＬＳＩの製造工程について説明する。図１は、本発明の実施の形態に係るＬＳＩの製造工程の一例を示すフローチャートである。なお、ＶＬＳＩの製造工程も、図１に図示されているＬＳＩの製造工程と同一である。
【００４０】
ＬＳＩは、設計から出荷までの製造工程において、ＣＡＤ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）によるＬＳＩ設計工程（ステップＳ１０）、半導体素子の加工を実際に行うＬＳＩプロセス（ステップＳ２０）、加工後のＬＳＩの実装及びテストを行うＬＳＩ実装・テスト工程（ステップＳ３０）の３つの工程を経て製造される。
【００４１】
ＬＳＩ設計工程（Ｓ１０）は、製造するＬＳＩ全体の機能や性能などの構成を決定する機能設計（ステップＳ１１）、機能設計で決められた機能を電気的な流れで具体的に表現した基本論理回路の組み合わせを決定するとともに、基本論理回路を構成する最適な半導体（セル）の構成を決定する論理回路設計（ステップＳ１２）、論理回路設計によって得られたセルの組み合わせをチップ上に効率的にレイアウト（配置）するとともに、回路間の接続を決定するレイアウト設計（ステップＳ１３）を有している。なお、このＬＳＩ設計工程は、現在、ＣＡＤなどのコンピュータを利用した省力化及び迅速化が進んでいる。
【００４２】
また、ステップＳ１３のレイアウト設計では、通常、各セルの配置処理、概略配線処理、詳細配線処理の各手順が行われる。本発明は、このレイアウト設計の各セルの配置処理に適用され、チップ内のセルの配置の最適化を実現するために、各セルを表す複数のモジュールの配置が最密となる最密配置解の計算が行われる。
【００４３】
また、ＬＳＩプロセス（Ｓ２０）は、レイアウト設計により生成されたレイアウトに基づくマスクパターン生成（ステップＳ２１）、生成されたマスクパターンに基づくウェハ加工を行うウェハプロセス（ステップＳ２２）を有している。
【００４４】
また、ＬＳＩ実装・テスト工程（Ｓ３０）は、ウェハに作り込まれたＬＳＩの検査を行うウェハプロービング（ステップＳ３１）、各ＬＳＩチップのダイシング、ボンディング、モールディング処理を行う実装組み立て（ステップＳ３２）、最終的に生成されたＬＳＩの信頼性のテスト（ステップＳ３３）を有しており、以上の処理を経て生成されたＬＳＩが商品として出荷される。
【００４５】
上述のように、本発明にかかる矩形要素配置は、特に、ＬＳＩの製造工程において、コンピュータにより行われる。次に、図２を参照しながら、本発明を実現することが可能なコンピュータの構成の一例について説明する。図２は、本発明の実施の形態において使用されるハードウェア構成の一例を示す図である。
【００４６】
図２には、演算処理や制御処理などを行うＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央演算制御装置）２０１、データを一時的に記憶するためのＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などのメモリ２０２、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ：陰極線管）ディスプレイや液晶ディスプレイなどの情報を視覚的に表示するためのディスプレイ２０３、キーボードやマウスなどの操作やユーザ指示情報などの入力を行う操作入力部２０４、様々なデジタルデータを格納するためのハードディスク２０５、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）内に記憶されているデータの読み取りを行うためのＣＤ−ＲＯＭドライブ２０６、ネットワークを介して、サーバやその他のネットワークに接続する通信装置との通信を行うためのネットワークカードドライブ２０７が、バス２０８によって接続されている状態が図示されている。
【００４７】
また、ハードディスク２０５には、ソフトウェア及びハードウェアの管理を行い、アプリケーションによる利用を可能とするための基本ソフトウェアであるＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ：オペレーティングシステム）２０５１、本発明に係る動作アルゴリズムが記述されている矩形要素配置用プログラム２０５２などが格納されている。なお、これらのオペレーティングシステム２０５１及び矩形要素配置用プログラム２０５２は、ＣＰＵ２０１によって実行される。
【００４８】
ＣＰＵ２０１、メモリ２０２、ディスプレイ２０３、操作入力部２０４、ハードディスク２０５、ＣＤ−ＲＯＭドライブ２０６、ネットワークカードドライブ２０７が、バス２０８によって接続されている上述のハードウェア構成は、例えば、汎用のＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）などによって実現可能であり、また、本発明に係る処理に特化した装置が実現されてもよい。
【００４９】
また、例えば、ハードディスク２０５にＬＳＩ設計工程を実行するためのＣＡＤ用プログラムが格納されており、上述のハードウェア構成によってＣＡＤ装置が実現されてもよく、さらに、本発明に係る矩形要素配置用プログラム２０５２が、ＣＡＤ用プログラムの一部を構成しており、矩形要素配置用プログラム２０５２によって、ＬＳＩ設計工程における複数のモジュールの最密配置解の導出が行われるようにしてもよい。
【００５０】
また、ＣＤ−ＲＯＭドライブ２０６とＣＤ−ＲＯＭとの組み合わせ以外にも、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）読み取り用ドライブとＤＶＤとの組み合わせを始めとして、様々な記憶媒体読み取り装置及び記憶媒体を使用することが可能である。また、ネットワークカードドライブ２０７を用いて、ネットワークに接続されている所定の通信装置内に格納されている制御プログラムやデータを取得することも可能である。
【００５１】
また、図３は、本発明の実施の形態における矩形要素配置装置の一例を示す機能ブロック図である。図３には、例えば、図２に示すハードウェア構成によって実現される本発明に係る矩形要素配置装置の機能が模式的に図示されている。なお、図３に図示されている矩形要素配置装置の機能は、例えば、矩形要素配置用プログラム２０５２がＣＰＵ２０１によって実行されることによって実現される。
【００５２】
図３に図示されている矩形要素配置装置は、データ／操作指示入力部３０１、矩形要素集合取得・保持部３０２、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３、対称配置制約条件取得・設定部３０４、線形計画法演算部３０５、演算結果判断部３０６、最密配置解出力部３０７、配置不可能通知部３０８、データ出力部３０９を有している。なお、矩形要素配置装置は、矩形要素配置装置全体の動作を制御するための制御部も有しているが、ここでは図示省略する。
【００５３】
データ／操作指示入力部３０１は、平面上に配置すべき複数の矩形要素（モジュール）に係るデータ、複数のモジュールに関するｓｅｑ−ｐａｉｒ制約条件に係るデータ、複数のモジュールに関する対称配置制約条件に係るデータなどのモジュールの配置位置を決定するために必要な各種データや、ユーザによる演算開始指示などを受ける機能を有している。なお、このデータ／操作指示入力部３０１によって実現される機能は、外部から情報を受ける機能であり、例えば、図２に図示されている操作入力部２０４、ＣＤ−ＲＯＭドライブ２０６、ネットワークカードドライブ２０７などによって実現可能である。
【００５４】
また、矩形要素集合取得・保持部３０２は、データ／操作指示入力部３０１から入力された平面上に配置すべき複数のモジュールに係るデータを取得して保持する機能を有している。矩形要素集合取得・保持部３０２によって保持されるデータは、例えば、複数のモジュールのそれぞれを識別するための識別情報と、各モジュールの矩形の高さ及び幅を示す値とのセット（モジュールの識別情報，高さ，幅）である。
【００５５】
また、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３は、データ／操作指示入力部３０１から入力された複数のモジュールに関するｓｅｑ−ｐａｉｒ制約条件に係るデータを取得し、これらのデータを後述の線形計画法演算部３０５で処理可能な制約式によって表すための機能を有している。
【００５６】
例えば、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３は、「ｂはａの右」（すなわち、Γ+-1（ａ）＜Γ+-1（ｂ）かつΓ--1（ａ）＜Γ--1（ｂ））というｓｅｑ−ｐａｉｒ制約を受けた場合に、矩形要素集合取得・保持部３０２からモジュールａの幅ｗｉｄｔｈ（ａ）を取得して、このｓｅｑ−ｐａｉｒ制約を下記の式（３）の制約式に変換する。
【００５７】
ｘ（ａ）＋ｗｉｄｔｈ（ａ）≦ｘ（ｂ）      ・・・（３）
【００５８】
なお、ｘ（ａ）はモジュールａの左辺ｘ座標、ｘ（ｂ）はモジュールｂの左辺ｘ座標を表している。
【００５９】
また、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３は、「ｂはａの右」であり、「ｃはｂの右」であるというｓｅｑ−ｐａｉｒ制約から得られる「ｃはａの右」であるという推移的な制約については、制約式への変換を省略することが可能であり、この結果、冗長な制約式を低減することが可能である。また、上述では、ｘ方向に関するｓｅｑ−ｐａｉｒ制約を制約式に変換する一例について説明したが、ｙ方向に関しても同様に、制約式に変換することが可能である。
【００６０】
また、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３は、後述の線形計画法演算部３０５における線形計画法の演算の際の目的関数を得るために、ｓｅｑ−ｐａｉｒ制約条件を示すΓ+及びΓ-に対して、例えば幅がゼロである仮想モジュールを加える。
【００６１】
また、対称配置制約条件取得・設定部３０４は、データ／操作指示入力部３０１から入力された複数のモジュールに関する対称配置制約条件に係るデータを取得し、これらのデータを後述の線形計画法演算部３０５で処理可能な制約式によって表すための機能を有している。
【００６２】
例えば、対称配置制約条件取得・設定部３０４は、「ａlとａrは垂直な対称軸に対称な対をなしている」（すなわち、｛（ａl，ａr）｝）という対称配置制約を受けた場合に、矩形要素集合取得・保持部３０２からモジュールａlの幅ｗｉｄｔｈ（ａl）を取得して、この対称配置制約を下記の式（４）及び式（５）の制約式に変換する。
【００６３】
ａｘｉｓx−｛ｘ（ａl）＋ｗｉｄｔｈ（ａl）｝
＝ｘ（ａr）−ａｘｉｓx      ・・・（４）
ｙ（ａl）＝ｙ（ａr）      ・・・（５）
【００６４】
なお、ｘ（ａl）はモジュールａlの左辺ｘ座標、ｘ（ａr）はモジュールａrの左辺ｘ座標、ａｘｉｓxはａlとａrの対称軸のｘ座標を表しており、ｙ（ａl）はモジュールａlの下辺ｙ座標、ｘ（ａr）はモジュールａrの下辺ｙ座標を表している。
【００６５】
また、例えば、対称配置制約条件取得・設定部３０４は、「ａsは自己対称である」という対称配置制約を受けた場合に、矩形要素集合取得・保持部３０２からモジュールａsの幅ｗｉｄｔｈ（ａs）を取得して、この対称配置制約を下記の式（６）の制約式に変換する。
【００６６】
２ｘ（ａs）＋ｗｉｄｔｈ（ａs）＝２ａｘｉｓx      ・・・（６）
【００６７】
なお、ｘ（ａs）はモジュールａsの左辺ｘ座標、ａｘｉｓxはａsの自己対称軸のｘ座標を表している。
【００６８】
また、上述では、ｘ方向に関する対称配置制約を制約式に変換する一例について説明したが、ｙ方向に関しても同様に、制約式に変換することが可能である。
【００６９】
また、線形計画法演算部３０５は、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３においてｓｅｑ−ｐａｉｒ制約から得られた制約式や、対称配置制約条件取得・設定部３０４において対称配置制約から得られた制約式を受け、これらの制約式に対して所定の目的関数（例えば、上述のｘ（ｓｉｎｋ＿ｘ））を最小とする解を線形計画法によって演算する機能を有している。
【００７０】
なお、この線形計画法による演算の結果、各モジュールの左辺ｘ座標及び対称軸のｘ座標や、各モジュールの下辺ｙ座標及び対称軸のｙ座標によって表されるモジュールの最密配置解が得られる場合がある一方、これらの解の一部又は全部の解が得られず、モジュールの配置が不可能であるという結果が得られる場合もある。
【００７１】
また、演算結果判断部３０６は、上述のように、線形計画法による演算でモジュールの最密配置解が得られたか、あるいはモジュールの配置が不可能であるという結果が得られたかを判断する機能を有している。演算結果判断部３０６は、線形計画法による演算でモジュールの最密配置解が得られた場合には、線形計画法による演算結果を最密配置解出力部３０７に渡し、モジュールの配置が不可能であるという結果が得られた場合には、その旨を配置不可能通知部３０８に通知する。
【００７２】
また、最密配置解出力部３０７は、モジュールの最密配置解を演算結果判断部３０６から受けて、その最密配置解をデータ出力部３０９から出力するためのデータに加工する機能を有している。なお、最密配置解は、各モジュールが配置されるべきｘ座標及びｙ座標をそのまま出力してもよく、さらに、最密配置解を反映して各モジュールを所定の座標上に配置した視覚的なモジュール表示データとして出力してもよい。
【００７３】
また、配置不可能通知部３０８は、モジュールの配置が不可能であるという結果を演算結果判断部３０６から受けた場合に、例えば、「このｓｅｑ−ｐａｉｒ制約及び対称配置制約を同時に満たす配置は存在しません」などの報知を行うためのデータを出力する機能を有している。
【００７４】
また、データ出力部３０９は、最密配置解出力部３０７又は配置不可能通知部３０８から受けたデータを外部に出力する機能を有している。なお、このデータ出力部３０９によって実現される機能は、外部に対して情報を出力する機能であり、例えば、図２に図示されているディスプレイ２０３やネットワークカードドライブ２０７などによって実現可能である。
【００７５】
次に、図４を参照しながら、本発明の実施の形態における矩形要素配置に係る動作の一例について説明する。図４は、本発明の実施の形態における矩形要素配置に係る動作の一例を示すフローチャートである。なお、ここでは、図３に図示されている矩形要素配置装置によって矩形要素配置に係る動作が実行されている場合について説明する。
【００７６】
まず、矩形要素配置装置には配置を行うモジュールの集合（各モジュールを識別するための識別情報と、各モジュールの高さ及び幅を示す値）が入力され、その結果、矩形要素集合取得・保持部３０２に、配置を行うモジュールの集合が準備される（ステップＳ４０１）。なお、このとき、各モジュールに対して、配置位置を示す座標変数（例えば、各モジュールの左辺ｘ座標及び下辺ｙ座標）が設定される。
【００７７】
続いて、矩形要素配置装置にはｓｅｑ−ｐａｉｒ制約が入力され、その結果、ｓｅｑ−ｐａｉｒ制約条件取得・設定部３０３に、ｓｅｑ−ｐａｉｒ制約条件に係る制約式が設定される（ステップＳ４０２）。なお、このとき、例えば、ｘ方向の座標を決定するときには、ｓｅｑ−ｐａｉｒ制約条件を示すΓ+及びΓ-の末尾に仮想モジュールｓｉｎｋ＿ｘを挿入し、ｙ方向の座標を決定するときには、Γ+の先頭及びΓ-の末尾にｓｉｎ＿ｙを挿入する。
【００７８】
さらに、矩形要素配置装置には対称配置制約が入力され、その結果、対称配置制約条件取得・設定部３０４に、対称配置制約条件に係る制約式が設定される（ステップＳ４０３）。なお、本発明の実施の形態では、ステップＳ４０２においてｓｅｑ−ｐａｉｒ制約条件に係る制約式を設定した後に、ステップＳ４０３において対称配置制約条件に係る制約式を設定しているが、先に対称配置制約条件に係る制約式を設定した後に、ｓｅｑ−ｐａｉｒ制約条件に係る制約式を設定してもよい。
【００７９】
そして、上記のｓｅｑ−ｐａｉｒ制約条件に係る制約式、及び対称配置制約条件に係る制約式に基づいて、線形計画法演算部３０５が、所定の目的関数を最適化するモジュールの最密配置解の導出を行う（ステップＳ４０４）。線形計画法演算部３０５は、例えば最も右に位置するｓｉｎｋ＿ｘを左詰めすることによってモジュールの最密化が行われることを考慮して、ｓｉｎｋ＿ｘのｘ座標であるｘ（ｓｉｎｋ＿ｘ）の最小化を目的とした線形計画法による演算を行い、その結果、最密な配置を実現するための各モジュールの左辺ｘ座標を求める。なお、このようにして導出された最密配置解において、仮想モジュールｓｉｎｋ＿ｘは、ｘ方向に最密化されたモジュール全体の幅を示している。
【００８０】
また、上述のようにｘ方向に関して最密な配置を実現する左辺ｘ座標を求めた後、ｙ方向に関しても同様の処理を行って、各モジュールの下辺ｙ座標を求める。ｙ方向に関しては、線形計画法演算部３０５は、例えば最も上に位置するｓｉｎｋ＿ｙを下詰めすることによってモジュールの最密化が行われることを考慮して、ｓｉｎｋ＿ｙのｙ座標であるｙ（ｓｉｎｋ＿ｙ）の最小化を目的とした線形計画法による演算を行う。このとき、線形計画法による演算によって導出された最密配置解において、仮想モジュールｓｉｎｋ＿ｙは、ｙ方向に最密化されたモジュール全体の高さを示している。なお、上述の動作では、ｘ方向に関する最密配置解を求めた後に、ｙ方向に関する最密配置解を求めているが、ｙ方向に関する最密配置解を先に求めた後に、ｘ方向に関する最密配置解を求めてもよい。
【００８１】
ステップＳ４０４における最密配置解の結果は、演算結果判断部３０６に供給され、最密配置解が得られたか、あるいは解が存在しなかったかの判断が行われる（ステップＳ４０５）。そして、最密配置解が得られた場合には、最密配置解出力部３０７において最密配置解は出力データに加工され、データ出力部３０９を通じて外部に出力される（ステップＳ４０６）。一方、解が存在せず、モジュールの配置が不可能であるという結果が得られた場合には、配置不可能通知部３０８において、入力されたｓｅｑ−ｐａｉｒ制約及び対称配置制約を同時に満たす配置が存在しない旨を報知するためのデータが、データ出力部３０９を通じて外部に出力される（ステップＳ４０７）。
【００８２】
また、以下に、上述の本発明の実施の形態における矩形要素配置に係る動作の具体例について説明する。なお、この具体例では、後述の図５に図示されているように、７つのモジュールに関して２つの対称軸（第１対称軸及び第２対称軸）を有する最密配置解が最終的に得られる。
【００８３】
ここでは、まず、矩形要素配置装置に、高さ及び幅が共に２である正方形モジュール（２×２の正方形モジュール）だけからなる集合｛ａl，ａr，ｂs，ｃ，ｄb，ｄu，ｅs｝、対称配置制約｛（ａl，ａr），ｂs｝及び｛（ｄu，ｄb），ｅs｝、ｓｅｑ−ｐａｉｒ制約（ｂsａlａrｃｄuｄbｅs；ａlａrｂsｃｄbｄuｅs）が入力される。
【００８４】
ｘ方向に関して、ｓｅｑ−ｐａｉｒ制約から得られる線形の制約式は下記の通りである。
【００８５】
ｘ（ｅs）＋２−ｘ（ｓｉｎｋ＿ｘ）≦０
ｘ（ｄb）＋２−ｘ（ｅs）≦０
ｘ（ｄu）＋２−ｘ（ｅs）≦０
ｘ（ｃ）＋２−ｘ（ｄu）≦０
ｘ（ｃ）＋２−ｘ（ｄb）≦０
ｘ（ａr）＋２−ｘ（ｃ）≦０
ｘ（ａl）＋２−ｘ（ａr）≦０
ｘ（ｂs）＋２−ｘ（ｃ）≦０
【００８６】
一方、対称配置制約｛（ａl，ａr），ｂs｝の対称軸（第１対称軸）をａｘｉｓ1とすると、ａｘｉｓ1は垂直線なので、下記の式が得られる。
２ａｘｉｓ1−ｘ（ｂs）−２＝０
２ａｘｉｓ1−ｘ（ａl）−２−ｘ（ａr）＝０
【００８７】
また、対称配置制約｛（ｄu，ｄb），ｅs｝の対称軸（第２対称軸）をａｘｉｓ2とすると、ａｘｉｓ2は水平線なので、下記の式が得られる。
ｙ（ｄu）−ｙ（ｄb）＝０
【００８８】
そして、上記の制約式に対して、ｓｉｎｋ＿ｘのｘ座標を最小とし、これらの制約式を線形計画法で解き、各モジュールの左辺ｘ座標、及び第１対称軸のｘ座標を求める。また、ｙ座標についても同様に、各モジュールの下辺ｙ座標、及び第２対称軸のｙ座標を求める。
【００８９】
この結果、図５に図示されているような７つのモジュールに係る最密な配置が得られる。図５は、本発明の実施の形態における矩形要素配置に係る動作の具体例で得られる最密配置解の配置を示す図である。
【００９０】
図５に図示されている配置では、各モジュールの左辺ｘ座標及び下辺ｙ座標は、ｂs（１，２）、ａl（０，０）、ａr（２，０）、ｃ（４，０）、ｄu（６，２）、ｄb（６，０）、ｅs（８，１）であり、対称軸の座標は、ａｘｉｓ1のｘ座標が２、ａｘｉｓ2のｙ座標が２である。なお、仮想モジュールｓｉｎｋ＿ｘの値は１０となり（すなわち、モジュール全体の幅は１０）、ｓｉｎｋ＿ｙの値は４となる（すなわち、モジュール全体の高さは４）。
【００９１】
次に、本発明の実施の形態における矩形要素配置装置に配置不可能な条件が入力された場合について説明する。本発明の実施の形態における矩形要素配置装置は、配置不可能な条件が入力された場合には、その条件から最密配置解の導出を行うことが不可能である旨を正しく判断することが可能である。すなわち、本発明の実施の形態における矩形要素配置装置に、例えば、特許文献３や非特許文献２に記載されているｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒの条件を満たす対称配置制約｛ａl1，ａr1｝及び｛ｂl2，ｂr2｝と、ｓｅｑ−ｐａｉｒ制約（ａl1ｂl2ｂr2ａr1；ｂl2ａl1ａr1ｂr2）とを入力した場合には、ｘ方向に関しては座標（解）を得ることができるが、ｙ方向に関しては解が得られない。その結果、矩形要素配置装置からは、「このｓｅｑ−ｐａｉｒ制約及び対称配置制約を同時に満たす配置は存在しません」などの報知が行われ、ユーザは、入力されたｓｅｑ−ｐａｉｒ制約及び対称配置制約を同時に満たす配置がない旨を明確に確認することが可能となる。
【００９２】
なお、上述の実施の形態では、矩形配置表現方法としてｓｅｑｕｅｎｃｅ−ｐａｉｒを利用する場合について説明したが、ｓｅｑｕｅｎｃｅ−ｐａｉｒ以外の任意の矩形配置表現方法に関しても、本発明は適用可能である。
【００９３】
なお、上述の実施の形態では、本発明をアナログＩＣのレイアウト設計に適用した場合に関して説明を行ったが、本発明は、この適用に限定されるものではない。すなわち、例えば、タイルやパッチワークキルトなどの配置位置を決定するためのデザインに係る技術分野などにも、本発明は適用可能である。
【００９４】
また、本発明は、その目的と利点を損なうことのない適宜の変形を含み、さらに、上述の実施の形態に示した数値による限定は受けない。
《第２実施形態》
【００９５】
たとえば、より最密なパッキングを行うために、線形計画法における変数の数や連立式の数を削減することは容易である。
以下、図面を参照しながら、変数の数や連立式の数を削減する本発明の第２実施形態について説明する。
具体的には、ｘ方向について考えると、シーケンスペアの制約に基づき、「ａはｂの左」という制約から、モジュールａの左辺ｘ座標をｘ（ａ），幅をｗ（ａ）とすると、
ｘ（ａ）＋ｗ（ａ）≦ｘ（ｂ）
を得る。なお、「ａはｂの左」かつ「ｂはｃの左」と制約されているとき、シーケンスペアの定義から、必ず「ａはｃの左」という制約が得られるが、後者から得られる制約式である、ｘ（ａ）＋ｗ（ａ）≦ｘ（ｃ）は、前の２つから得られる制約式、ｘ（ａ）＋ｗ（ａ）≦ｘ（ｂ）と、ｘ（ｂ）＋ｗ（ｂ）≦ｘ（ｃ）とから求められることから不要であり、したがって、高速化のために省略することができる。
【００９６】
対称配置制約を制約式に変換する場合、モジュールａlとモジュールａrが垂直軸に対して対称なモジュール対であるなら、ｘ方向についての制約式は、対称軸のｘ座標をＡｘｉｓxとすると、
Ａｘｉｓx−（ｘ（ａl）＋ｗ（ａl））
＝ｘ（ａr）−Ａｘｉｓx
となる。
ｙ方向については、
ｙ（ａl）＝ｙ（ａr）
となる。
自己対称モジュールａsについては、ｘ方向についての制約式は、
Ａｘｉｓx−（ｘ（ａs）＋ｗ（ａs））＝ｘ（ａs）−Ａｘｉｓx
となる。この場合、ｙ方向については、制約式は得られない。
【００９７】
以上の手順で得られた制約式を線形計画法によって解くことで、チップ等の最小の縦幅と横幅を求めることができる。
具体的には、対称なモジュールのソースとシンクに対応する節点間の全ての最長パスを求めて記録しておき、その１つずつについて、他の節点を経由して同じ長さ以下の経路となったなら不要であると判定する。この場合には、予め多数の制約グラフを仮想作成することができる。この方法により、結果取得がＯ（ｓ3）時間で可能となる。なお、簡易制約グラフをデータベース化しておき、これから最長パスを求めるようにしてもよい。
更に、対称モジュールに対応する節点とソース点とシンク点には、制約枝が不要な対が多いことを利用し、得られる制約式の数をｅとしてＯ（ｓｅ）時間で必要か不要かを判定することができる。
最長パスを求め、必要であれば制約式を出力するためのアルゴリズム（計算複雑度がＯ（ｓｎｌｏｇｌｏｇｎ＋ｓｅ））を以下に示す。
【００９８】
【表１】
2006309748.tif 000003
【００９９】
例えば、シーケンスペア（ａlｂsｃａr；ａlｃｂsａr）と、対称軸が垂直線である対称配置制約｛（ａl，ａr），ｂs｝、モジュールの幅としてｗ（ａl）＝１、ｗ（ａr）＝１、ｗ（ｂs）＝１、ｗ（ｃ）＝３が与えられたとする（図６参照）。
ｘ方向について、下記の制約式集合〔Ｉ〕、
０≦ｘ（ａl）
ｘ（ａl）＋１≦ｘ（ｂs）
ｘ（ａl）＋１≦ｘ（ｃ）
ｘ（ｂs）＋１≦ｘ（ａr）
ｘ（ｃ）＋３≦ｘ（ａr）
ｘ（ａr）＋１≦ｘ（ｓｉｎｋ）
Ａｘｉｓx−ｘ（ａl）＝（ｘ（ａr）＋１）−Ａｘｉｓx
Ａｘｉｓx−ｘ（ｂs）＝（ｘ（ｂs）＋１）−Ａｘｉｓx
と、変数６個、制約式８個の制約式の集合が得られる。
【０１００】
これに対して、上に示したアルゴリズムでは、下記の制約式集合〔ＩＩ〕、
０≦ｘ（ａl）
ｘ（ａl）＋１≦ｘ（ｂs）
ｘ（ａl）＋４≦ｘ（ａr）
ｘ（ｂs）＋１≦ｘ（ａr）
ｘ（ａr）＋１≦ｘ（ｓｉｎｋ）
Ａｘｉｓx−ｘ（ａl）＝（ｘ（ａr）＋１）−Ａｘｉｓx      ・・・（７）
Ａｘｉｓx−ｘ（ｂs）＝（ｘ（ｂs）＋１）−Ａｘｉｓx      ・・・（８）
のように、変数５個、制約式７個の制約式の集合を得ることができ、変数１個、制約式１個を減少させることができる。
【０１０１】
この制約式集合をｘ方向、ｙ方向について求め、線形計画法でそれらを解くことで、全体の幅と高さを求め、配置面積を求めることができる。従属変数の代入による消去は、以下のようにして行われる。
対称配置制約から得られる制約式は等式で表され、対称軸と対称対との距離が等しいことを表す。
ここで、等式で表される制約式を右モジュール、もしくは自己対称モジュールに対応する変数でまとめ、他の制約式に代入することで、変数の数、および制約式の数を減らすことができる。
【０１０２】
例えば、対称配置制約から得られる制約式（７），（８）を右モジュールおよび、自己対称モジュールに対応する変数についてまとめた、
ｘ（ａr）＝２＊Ａｘｉｓx−（ｘ（ａl）＋１）
ｘ（ｂs）＝Ａｘｉｓx−０．５
を制約式集合〔ＩＩ〕に代入すると、
０≦ｘ（ａl）
ｘ（ａl）−Ａｘｉｓx≦−１．５      ・・・（９）
ｘ（ａl）−Ａｘｉｓx≦−２．５      ・・・（１０）
ｘ（ａl）−Ａｘｉｓx≦−１．５      ・・・（１１）
２×Ａｘｉｓx−（ｘ（ａl）＋１）≦ｘ（ｓｉｎｋ）・・・（１２）
となり、変数変数２個、制約式２個がさらに減少する。
【０１０３】
また、上の制約式集合の中で（１０）があれば、（９），（１０）は冗長であり、不要である。
この様な冗長な制約式を除去することで、更に制約式の数を減らすことができる。
上の例は、冗長な制約式を除去することで最終的に、
０≦ｘ（ａl）
ｘ（ａl）−Ａｘｉｓx≦−２．５
２×Ａｘｉｓx−（ｘ（ａl）＋１）＋１≦ｘ（ｓｉｎｋ）
となり、変数３個、制約式３個の制約式集合が得られ、制約式２個がさらに減少した。
《ＳＡ法による配置実験》
【０１０４】
提案手法がどれほど高速化したかを確認するために、ｓｅｑ−ｐａｉｒにおいてランダムに選んだ二つのモジュールをΓ+とΓ-の両方、またはいずれか片方で交換したものを隣接解として、提案手法をＳＡ法に組み込み計算機に実装した。
（手法１）第１実施形態における手法
（手法２）第２実施形態において簡易化制約グラフを使った手法
（手法３）第２実施形態においてさらに連立式や変数を削減した手法
線形計画法を解く手法としては単体法（ｓｉｍｐｌｅｘ法）を用いた。入力として、適当に作成した、対称軸が垂直線のみで、モジュール数、対称制約数の異なる５種類のモジュール集合を、初期温度と終了温度と探索回数を揃えて、解を得るまでの所要時間を比較した実験結果を表２に示す。
【０１０５】
【表２】
2006309748.tif 000004
【０１０６】
表２から、代入によって変数と制約式を減少させる手法では、処理時間が２倍から４．５倍ほど速くなっていることがわかる。
また、入力ＢおよびＣは核問題を考慮しただけでは，さほど速くなっていないが、これは、対称モジュールの数が多い程、線形計画法で解く変数の数が増えてしまい、遅くなるからである。
提案手法が非常に高速化しているのは、ｙ座標をグラフを用いて得ると共に、ｙ方向制約グラフからその解がインフィージブルと判断した場合に、線形計画法を使うことなく、次の隣接解を生成し線形計画法を用いる回数が減少しているためである。
【０１０７】
また、与えられた対称配置制約とモジュールのサイズから準最適な配置を探索するために上記の手法３のプログラムで配置実験を行った。
準最適従来手法に示されている図から抽出した、垂直軸についての３つの対称集合（対称対４，対称対６，対称対２自己対称１）を含んだ６５個のモジュール集合を入力とし、内部クロック３．２ＧＨｚのマイクロプロセッサの計算機を用いて６５３．６秒で得られた。
【０１０８】
パッキング率（配置面積／各モジュール面積の合計）が１０８．８％の配置を図６に示す。
この入力データは準最適従来手法と同様のものである。
なお、準最適従来手法では、パッキング率１０３％の配置をおよそ７分で求めており、この実験から、提案手法が非常に高速に、密に詰まった配置を得ることが可能であると分かった。
提案手法をＳＡ法に組み込んでの配置実験結果（計算時間６５３．６秒，パッキング率１０８．８％）を図７に示す。
【０１０９】
本発明は、平面上に複数の矩形要素を配置する際の対称配置制約及び相対位置関係に係る制約を共に満たす最適配置解を求めることができるという効果を有しており、平面上に複数の矩形要素を最密に配置する際のレイアウト設計に関する技術分野に適用可能であり、特に、アナログＩＣのレイアウト設計に関する技術分野に適用可能である。
【図面の簡単な説明】
【０１１０】
【図１】本発明の第１実施形態に係るＬＳＩの製造工程の一例を示すフローチャートである。
【図２】本発明の第１実施形態において使用されるハードウェア構成の一例を示す図である。
【図３】本発明の第１実施形態における矩形要素配置装置の一例を示す機能ブロック図である。
【図４】本発明の第１実施形態における矩形要素配置に係る動作の一例を示すフローチャートである。
【図５】本発明の第１実施形態における矩形要素配置に係る動作の具体例で得られる最密配置解の配置を示す図である。
【図６】本発明の第２実施の形態における矩形要素配置に係る動作の具体例で得られる最密配置解の配置を示す図である。
【図７】本発明の実施形態における配置実験結果を示すレイアウト設計図である。
【図８】従来の技術のｓｙｍｍｅｔｒｉｃ  ｆｅａｓｉｂｌｅ  ｓｅｑｕｅｎｃｅ−ｐａｉｒに関する問題点を説明するための図である。
【図９】（Ａ）〜（Ｄ）は従来の技術のｘ座標決定アルゴリズムに関する問題点を説明するための図である。
【図１０】（Ａ）〜（Ｄ）は従来の技術のｙ座標決定アルゴリズムに関する問題点を説明するための図である。
【符号の説明】
【０１１１】
２０１  ＣＰＵ
２０２  メモリ
２０３  ディスプレイ
２０４  操作入力部
２０５  ハードディスク
２０６  ＣＤ−ＲＯＭドライブ
２０７  ネットワークカードドライブ
２０８  バス
３０１  データ／操作指示入力部
３０２  矩形要素集合取得・保持部
３０３  ｓｅｑ−ｐａｉｒ制約条件取得・設定部
３０４  対称配置制約条件取得・設定部
３０５  線形計画法演算部
３０６  演算結果判断部
３０７  最密配置解出力部
３０８  配置不可能通知部
３０９  データ出力部
２０５１  ＯＳ（オペレーティングシステム）
２０５２  矩形要素配置用プログラム
【図１】
2006309748.tif 000005
【図２】
2006309748.tif 000006
【図３】
2006309748.tif 000007
【図４】
2006309748.tif 000008
【図５】
2006309748.tif 000009
【図６】
2006309748.tif 000010
【図８】
2006309748.tif 000011
【図９】
2006309748.tif 000012
【図１０】
2006309748.tif 000013
【図７】
2006309748.tif 000014