(57)【要約】【課題】初期レイアウトにおけるブロックの配置上の制約を反映したシーケンス・ペアを抽出することが可能なシーケンス・ペア作成技術を提供する。【解決手段】ブロック集合Bに属する各ブロックbiのサイズ情報並びにブロック配置情報を記憶するブロック配置記憶手段５を有し、ブロックbiの順列P，Mの対であるシーケンス・ペア（P，M）の作成装置１において、順列P，Mにおける２つのブロック間の順序関係であって、ブロック配置情報及びサイズ情報から抽出される各ブロック間の配置制約から導出される二項関係を、ブロック配置情報及びサイズ情報に従って決定する二項関係決定手段９、及び二項関係決定手段９により決定されるすべての二項関係を満たすように、ブロック配置情報及びサイズ情報に基づいて順列P，Mにおける全順序関係を決定する全順序関係決定手段１１を備える。【選択図】        図１
2006099416.tif 000002
【特許請求の範囲】
【請求項１】
幅及び高さが与えられたN（≧２）個の矩形のブロックの集合（以下、「ブロック集合」という。）Bに属する各ブロックbi（i＝１，…，N）の幅w（bi）及び高さh（bi）の情報（以下、「サイズ情報」という。）、並びに前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロックbi（i＝１，…，N）の位置座標（x（bi），y（bi））からなるブロック配置情報を記憶するブロック配置記憶手段を有し、
それぞれが独立な前記ブロック集合Bに属するブロックbi（i＝１，…，N）の順列P及びMの対であって、前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロック間の位置関係を特定するシーケンス・ペア（P，M）の作成を行うシーケンス・ペア作成装置であって、
前記順列P，Mにおける２つのブロックbi，bj（∈B）間の順序関係であって、前記ブロック配置情報及びサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約から導出される関係である二項関係pord（bi，bj），mord（bi，bj）を、前記ブロック配置情報及びサイズ情報に従って決定する二項関係決定手段と、
前記二項関係決定手段により決定されるすべての二項関係pord（bi，bj），mord（bi，bj）（ｂｉ，ｂｊ∈Ｂ）を満たすように、前記ブロック配置情報及びサイズ情報に基づいて前記順列P，Mにおけるブロックの全順序関係を決定する全順序関係決定手段と、
を備えていることを特徴とするシーケンス・ペア作成装置。
【請求項２】
前記二項関係決定手段は、
前記ブロック配置記憶手段に記憶された２つのブロックbi，bj（∈B）の位置座標（x（bi），y（bi）），（x（bj），y（bj））、幅w（bi），w（bj）、及び高さh（bi），h（bj）を参照することにより、
ブロックbi及びブロックbjの垂直方向（以下、「y方向」という。）の辺のy座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjの水平方向（以下、「x方向」という。）に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の左右関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定し、
ブロックbi及びブロックbjのx方向の辺のx座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjのy方向に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の上下関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する離反制約抽出手段
を備えていることを特徴とする請求項１記載のシーケンス・ペア作成装置。
【請求項３】
前記二項関係決定手段は、
前記ブロック配置記憶手段に記憶されたブロック集合Bの部分集合Bk（⊆B）に属する各ブロックbi（∈Bk）に対して、それらのブロックの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）が課せられている場合、前記各ブロックbi（∈Bk）の位置座標の上下関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直共線制約抽出手段
を備えていることを特徴とする請求項１記載のシーケンス・ペア作成装置。
【請求項４】
前記二項関係決定手段は、
前記ブロック配置記憶手段に記憶されたブロック集合Bの部分集合Bkに属する各ブロックに対して、それらのブロックの上辺又は下辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）が課せられている場合、前記部分集合Bkに属する各ブロックbi（∈Bk）の位置座標の左右関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平共線制約抽出手段
を備えていることを特徴とする請求項１記載のシーケンス・ペア作成装置。
【請求項５】
前記二項関係決定手段は、
前記ブロック配置記憶手段に記憶されたブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して水平方向の対称位置に配置する制約（以下、「水平対称制約（horizontal symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の左右関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平対称制約抽出手段
を備えていることを特徴とする請求項１記載のシーケンス・ペア作成装置。
【請求項６】
前記二項関係決定手段は、
前記ブロック配置記憶手段に記憶されたブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して垂直方向の対称位置に配置する制約（以下、「垂直対称制約（vertical symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の上下関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直対称制約抽出手段
を備えていることを特徴とする請求項１記載のシーケンス・ペア作成装置。
【請求項７】
前記二項関係決定手段は、
前記ブロック集合Bに属する３つのブロックbi，bj，bkについて、二項関係pord（bi，bj），pord（bj，bk）が決定され且つ二項関係pord（bi，bk）が未決定の場合、二項関係pord（bi，bj），pord（bj，bk）から二項関係pord（bi，bk）を推移的に決定し、
二項関係mord（bi，bj），mord（bj，bk）が決定され且つ二項関係mord（bi，bk）が未決定の場合、二項関係mord（bi，bj），mord（bj，bk）から二項関係mord（bi，bk）を推移的に決定する二項関係推移決定手段
を備えていることを特徴とする請求項１乃至６の何れか一に記載のシーケンス・ペア作成装置。
【請求項８】
前記二項関係決定手段は、
前記ブロック集合Bに属する２つのブロックbi，bjについて、ブロックbiがブロックbjの左にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝１，mord（bi，bj）＝１に決定し、ブロックbiがブロックbjの下にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝０，mord（bi，bj）＝１に決定するものであり、
前記全順序関係決定手段は、
順列Pにおける順序が未決定のブロックの集合Bn（⊆B）に属するブロックbi（∈Bn）について、集合Bnに属する当該ブロックbi以外のすべてのブロックbj（∈Bn）との間の２項順序関係pord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bs（⊆Bn）とし、
集合Bsに属するブロックbiのうち、集合Bsに属する当該ブロックbi以外のすべてのブロックbj（∈Bs）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Pに左から詰めて並べる
という操作を繰り返すことにより、順列Pにおける各ブロックの順序を、左から順次決定するP順序決定手段と、
順列Mにおける順序が未決定のブロックの集合Bm（⊆B）に属するブロックbi（∈Bm）について、集合Bmに属する当該ブロックbi以外のすべてのブロックbj（∈Bm）との間の２項順序関係mord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bt（⊆Bm）とし、
集合Btに属するブロックbiのうち、集合Btに属する当該ブロックbi以外のすべてのブロックbj（∈Bt）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Mに左から詰めて並べる
という操作を繰り返すことにより、順列Mにおける各ブロックの順序を、左から順次決定するM順序決定手段と、
を備えていることを特徴とする請求項１乃至７の何れか一記載のシーケンス・ペア作成装置。
【請求項９】
前記ブロック配置記憶手段に記憶された前記ブロック集合Bに属するブロックに重なりがある場合、重なった２つのブロックの何れか一方又は両方の幅又は高さを短縮することにより、ブロック間の重なりのないブロック配置情報及びサイズ情報を生成する重なり除去手段を備え、
前記全順序関係決定手段は、前記二項関係決定手段により決定された二項関係pord（bi，bj），mord（bi，bj）を満たすように、前記重なり除去手段により生成されたブロック間の重なりのないブロック配置情報及びサイズ情報に従って前記順列P，Mにおけるブロックの全順序関係を決定すること
を特徴とする請求項１乃至８の何れか一に記載のシーケンス・ペア作成装置。
【請求項１０】
形状が与えられたN（≧２）個の矩形のブロックの集合（以下、「ブロック集合」という。）Bに属する各ブロックbi（i＝１，…，N）の幅w（bi）及び高さh（bi）の情報（以下、「サイズ情報」という。）、及び前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロックbi（i＝１，…，N）の位置座標（x（bi），y（bi））からなるブロック配置情報に基づき、
前記ブロック集合Bに属するブロックbi（i＝１，…，N）の順列P及びMの対であって、前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロック間の位置関係を特定するシーケンス・ペア（P，M）の作成を行うシーケンス・ペア作成方法であって、
前記順列P及びMにおける２つのブロックbi，bj（∈B）間の順序関係であって、前記ブロック配置情報及び各ブロックのサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約から導出される関係である二項関係pord（bi，bj），mord（bi，bj）を、前記ブロック配置情報及び各ブロックのサイズ情報に従って決定する二項関係決定ステップと、
前記二項関係決定ステップで決定されるすべての二項関係pord（bi，bj），mord（bi，bj）（ｂｉ，ｂｊ∈Ｂ）を満たすように、前記ブロック配置情報及び各ブロックのサイズ情報に基づいて前記順列P及びMにおける各ブロックの全順序関係を決定する全順序関係決定ステップと、
を有することを特徴とするシーケンス・ペア作成方法。
【請求項１１】
前記二項関係決定ステップにおいて、
前記ブロック集合Bに属する２つのブロックbi，bj（∈B）の位置座標（x（bi），y（bi）），（x（bj），y（bj））、幅w（bi），w（bj）、及び高さh（bi），h（bj）を参照することにより、
ブロックbi及びブロックbjの垂直方向（以下、「y方向」という。）の辺のy座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjの水平方向（以下、「x方向」という。）に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の左右関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定し、
ブロックbi及びブロックbjのx方向に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjのy方向に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の上下関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する離反制約抽出ステップ
を有していることを特徴とする請求項１０記載のシーケンス・ペア作成方法。
【請求項１２】
前記二項関係決定ステップにおいて、
前記ブロック集合Bの部分集合Bk（⊆B）に属する各ブロックbi（∈Bk）に対して、それらのブロックの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）が課せられている場合、前記各ブロックbi（∈Bk）の位置座標の上下関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直共線制約抽出ステップ
を有していることを特徴とする請求項１０記載のシーケンス・ペア作成方法。
【請求項１３】
前記二項関係決定ステップにおいて、
前記ブロック集合Bの部分集合Bkに属する各ブロックに対して、それらのブロックの上辺又は下辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）が課せられている場合、前記部分集合Bkに属する各ブロックbi（∈Bk）の位置座標の左右関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平共線制約抽出ステップ
を有していることを特徴とする請求項１０記載のシーケンス・ペア作成方法。
【請求項１４】
前記二項関係決定ステップにおいて、
前記ブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して水平方向の対称位置に配置する制約（以下、「水平対称制約（horizontal symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の左右関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平対称制約抽出ステップ
を有していることを特徴とする請求項１０記載のシーケンス・ペア作成方法。
【請求項１５】
前記二項関係決定ステップにおいて、
前記ブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して垂直方向の対称位置に配置する制約（以下、「垂直対称制約（vertical symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の上下関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直対称制約抽出ステップ
を有していることを特徴とする請求項１０記載のシーケンス・ペア作成方法。
【請求項１６】
前記二項関係決定ステップにおいて、
前記ブロック集合Bに属する３つのブロックbi，bj，bkについて、二項関係pord（bi，bj），pord（bj，bk）が決定され且つ二項関係pord（bi，bk）が未決定の場合、二項関係pord（bi，bj），pord（bj，bk）から二項関係pord（bi，bk）を推移的に決定し、
二項関係mord（bi，bj），mord（bj，bk）が決定され且つ二項関係mord（bi，bk）が未決定の場合、二項関係mord（bi，bj），mord（bj，bk）から二項関係mord（bi，bk）を推移的に決定する二項関係推移決定ステップ
を有していることを特徴とする請求項１０乃至１５の何れか一に記載のシーケンス・ペア作成方法。
【請求項１７】
前記二項関係決定ステップにおいては、
前記ブロック集合Bに属する２つのブロックbi，bjについて、ブロックbiがブロックbjの左にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝１，mord（bi，bj）＝１に決定し、ブロックbiがブロックbjの下にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝０，mord（bi，bj）＝１に決定し、
前記全順序関係決定ステップにおいて、
順列Pにおける順序が未決定のブロックの集合Bn（⊆B）に属するブロックbi（∈Bn）について、集合Bnに属する当該ブロックbi以外のすべてのブロックbj（∈Bn）との間の２項順序関係pord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bs（⊆Bn）とし、
集合Bsに属するブロックbiのうち、集合Bsに属する当該ブロックbi以外のすべてのブロックbj（∈Bs）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Pに左から詰めて並べる
という操作を繰り返すことにより、順列Pにおける各ブロックの順序を、左から順次決定するP順序決定ステップと、
順列Mにおける順序が未決定のブロックの集合Bm（⊆B）に属するブロックbi（∈Bm）について、集合Bmに属する当該ブロックbi以外のすべてのブロックbj（∈Bm）との間の２項順序関係mord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bt（⊆Bm）とし、
集合Btに属するブロックbiのうち、集合Btに属する当該ブロックbi以外のすべてのブロックbj（∈Bt）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Mに左から詰めて並べる
という操作を繰り返すことにより、順列Mにおける各ブロックの順序を、左から順次決定するM順序決定ステップと、
を備えていることを特徴とする請求項１０乃至１６の何れか一に記載のシーケンス・ペア作成方法。
【請求項１８】
前記ブロック集合Bに属するブロックに重なりがある場合、重なった２つのブロックの何れか一方又は両方の幅又は高さを短縮することにより、ブロック間の重なりのないブロック配置情報及びサイズ情報を生成する重なり除去ステップを備え、
前記全順序関係決定ステップにおいては、前記二項関係決定ステップにおいて決定された二項関係pord（bi，bj），mord（bi，bj）を満たすように、前記重なり除去ステップにおいて生成されたブロック間の重なりのないブロック配置情報及びサイズ情報に従って前記順列P，Mにおけるブロックの全順序関係を決定すること
を特徴とする請求項１０乃至１７の何れか一に記載のシーケンス・ペア作成方法。
【請求項１９】
請求項１０乃至１８のシーケンス・ペア作成方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意のサイズの矩形モジュールを重なりなくチップに配置する矩形パッキングを最適化する一方法であるシーケンス・ペア法で使用されるシーケンス・ペアを作成する技術に関する。
【背景技術】
【０００２】
VLSIレイアウト設計において、最初の最も重要な設計過程はモジュールの配置（placement）である。VLSIのチップ上に回路ブロック（以下、単に「ブロック」という。）単位でモジュールを置く位置を指定する設計過程はフロアプラン（floorplan）と呼ばれる。フロアプランにおいては、ブロックを可能な限り小さい領域に納めることにより、チップ内における信号遅延を一定限度に納め回路の高速化が可能となり、またVLSIの小型化、製造コストの低減等も可能となる。このように、チップ配置を最適化してチップ面積を圧縮することを、コンパクションという。
【０００３】
任意サイズの矩形ブロックを幾つか与え、それらを最小の矩形境界の中にブロック同士が互いに重なり合わないように配置する問題は、矩形パッキング問題（rectangle packing problem：以下、「RP」という。）として知られている。高さと幅が実数で与えられたm個の矩形ブロックの集合をMとする。Mの「パッキング（packing）」とは、各ブロックの重なりのない配置をいう。パッキングの最小の矩形境界のことを「チップ（chip）」と呼ぶ。RPとは、チップの面積が最小となるMのパッキングを見つける問題である。また、「フロアプラン」とは、チップCを、高々１つのブロックが含まれる部屋（room）と呼ばれる矩形領域に分割することであると定義される。
【０００４】
フロアプランの本質は、このRPを解くことにある。しかし、VLSIレイアウト設計では、配置すべきブロックの個数が多いため、人手でブロック配置を行うと必ずしも最適な配置が求まらず、しかも時間がかかる。従って、VLSIレイアウト設計のフロアプランを行うCAD装置等においては、RPを効率よく解くアルゴリズムが必要とされる。
【０００５】
ところで、RPはNP困難（NP-hard）であることが知られている。しかも、各ブロックの高さと幅は連続的な実数値を採るため、RPは単純な組み合わせ最適化問題でもない。従って、RPを解く場合、通常は組み合わせ探索（combinational search）のような反復的なアプローチが採られる。
【０００６】
組み合わせ探索においては、構造を規定する符号の集合である解空間（solution space）を定義する。解空間に属するある符号に対してパッキングが存在する場合、その符号は実行可能（feasible）であるという。実行可能な各符号の評価は、その符号に対応するパッキングのチップ面積を評価することによって行われる。組み合わせ探索では、パッキングが最もよい評価となる実現可能な符号を探索する。
【０００７】
組み合わせ探索によってすべての符号を探索すれば、最適なパッキングを求めることができる。しかしながら、ブロックの数が多数ある場合には、探索範囲は極めて大きくなり現実的ではない。従って、通常は発見的探索（heuristic search）法が採られる。発見的探索法を採る場合、効率的な探索を行うためには、どのような解空間を選択するかが重要となる。効率的な探索を行うためには、解空間はP許容（P-admissible）であることが必要とされる。P許容な解空間とは、以下の４つの条件を満たす解空間をいう：（１）解空間は有限であること。（２）すべての解は実行可能であること。（３）各符号の評価は多項式時間で可能であり、従って、各符号に対応するパッキングも実現できること。（４）RPの最適解となるパッキングは、解空間における最もよい評価の符号に一致すること。
【０００８】
P許容な解空間を与える極めて効率的な解空間として、各符号をブロック名の順列の対であるシーケンス・ペア（sequence-pair）で表したものが知られている（特許文献１，２，非特許文献１，２参照）。この解空間の特徴は、以下の通りである：（１）ブロック名の順列の対だけで表されるので、組み合わせ数は（n！）２である。（２）どのようなパッキングでも表現可能であり、勿論、最小面積解も表現可能であることが証明されている。（３）すべてのシーケンス・ペアがパッキングを表す（実行可能な符号のみを含む）。以下、フロアプランナによるシーケンス・ペアを用いたRPの解法について概説する。
【０００９】
シーケンス・ペアを用いた方法（以下、「シーケンス・ペア法」という。）では、まず初期条件として、最適化を行う前のブロック配置（パッキング）が与えられる。この初期のブロック配置は、CAD装置等により、設計者が初期レイアウトを作成しこの初期レイアウト内の回路素子や配線を矩形近似する等によって与えられる。そして、フロアプランナは、まず与えられた初期のブロック配置からシーケンス・ペアを抽出する。次に、フロアプランナは、抽出された初期のシーケンス・ペアを初期状態として、発見的探索法（例えば、焼きなまし法（Simulated Annealing method）等）により組み合わせ探索を行い、最適なシーケンス・ペアを探索する。このとき、シーケンス・ペアの最適性を判定する評価値として、各シーケンス・ペアに対応するチップ面積が用いられる。そして、最後に、フロアプランナは、評価値が最適となるシーケンス・ペアに対応するパッキングを、最適なパッキングとして出力する。
【００１０】
〔１〕パッキングからシーケンス・ペアの抽出
まず、パッキングからシーケンス・ペアの抽出を説明する（非特許文献１参照）。
チップC上のパッキングをΠと記す。上述のように、フロアプランとは、チップCを、高々１つのブロックが含まれる部屋に分割することをいう。１つのブロックも含まれない部屋は「空（empty）である」という。チップCの４つの辺を含む各部屋の境界を構成する線分を切断線分（cutting-seg）という。図１２は６つのブロックのあるパッキングΠのフロアプランを表したものである。a〜dがブロックであり、点線が切断線分を表している。
【００１１】
パッキングΠにおいて、空でない各部屋の中心にペブル（pebble）pを置く。ペブルpを、その部屋の一辺をなす切断線分にぶつかるまで右に移動させる。次に、ペブルpが切断線分にぶつかると、今度は当該切断線分の上方でT字状に直交する切断線分にぶつかるまで、ペブルpを上向きに移動させる。次に、ペブルpが切断線分にぶつかると、今度は当該切断線分の右方でT字状に直交する切断線分にぶつかるまで、ペブルpを右向きに移動させる。以下同様に、チップの右上隅にペブルpが到達するまで、ペブルpを上、右、上、…のように移動させる。このようにして得られるペブルpの軌跡を「右上軌跡（right-up locus）」という。同様に、「上左軌跡（up-left locus）」、「左下軌跡（left-down locus）」、「下右軌跡（down-right locus）」を定義する。図１３は、図１２のパッキングΠにおいて、ブロックdに対する右上軌跡、上左軌跡、左下軌跡、及び下右軌跡を表す。以下では、ブロックxの右上軌跡、上左軌跡、左下軌跡、及び下右軌跡を、それぞれRU（x），UL（x），LD（x），DR（x）と記す。
【００１２】
あるブロックxの左下軌跡と右上軌跡との和を「正軌跡（positive locus）」という。また、ブロックxの上左軌跡と下右軌跡との和を「負軌跡（negative locus）」という。パッキングΠが与えられると、１つのブロックに対して１つの正軌跡及び負軌跡が一意的に定まる。従って、以下ではそれぞれの正軌跡と負軌跡は、ブロック名により参照する。図１４は、図１２のパッキングΠに対する正軌跡（a）及び負軌跡（b）を表した図である。
【００１３】
このとき、次の定理が成り立つことが証明できる：『（定理１）すべての正軌跡は互いに交差しない。同様に、すべての負軌跡は互いに交差しない。』この定理１により、m本の正軌跡、負軌跡には、それぞれ線形順序関係があることが分かる。そこで、正軌跡はチップCの左上から右下に向けて順序づけることとし、負軌跡はチップCの左下から右上に向けて順序づけることとする。正軌跡、負軌跡の順列を、それぞれP，Mと記す。各軌跡は、ブロック名によって一意的に特定される。従って、P，Mはモジュール名の順列として表すことができる。このようにして得られるモジュール名の順列の対（P，M）を「シーケンス・ペア」と定義する。例えば、図１４においては、順列P，Mは、それぞれ、P＝（abdecf），M＝（cbfade）と表される。
【００１４】
以上のようなパッキングΠをシーケンス・ペアに対応させる操作を「グリッティング（gridding）」といい、Gridding(Π)と記す。Gridding(Π)＝（P，M）である。
【００１５】
ブロック集合BのパッキングΠに対応するシーケンス・ペアが与えられた場合、ブロック集合Bに属する任意の２つのブロックx，x’に対して、以下の４つのBの部分集合Maa（x），Mbb（x），Mba（x），Mab（x）が固有に定まる：
【００１６】
【数１】
2006099416.tif 000003
【００１７】
例えば、図１２のパッキングから得られるシーケンス・ペア（P，M）＝（abdecf，cbfade）に対して、ブロックbに対する４つの部分集合は、Maa（b）＝｛d，e，f｝，Mbb（b）＝φ，Mba（b）＝｛a｝，Mab（b）＝｛c｝である。また、各ブロック間には、次のような双対関係（dual relation）が成立する：
【００１８】
【数２】
2006099416.tif 000004
ブロックxの左辺がブロックx’の右辺よりも右であれば、xはx’の「右に」あるという。同様に、２つのブロック間の「左に」、「上に」、「下に」の関係も定義される。このとき、次の定理が成り立つことが証明されている：『（定理２）Gridding(Π)＝（P，M）とする。Πにおいて、x’∈Maa（x）ならばx’はxの右にある。同様に、x’∈Mbb（x）ならばx’はxの左にある。x’∈Mab（x）ならばx’はxの下にある。x’∈Mba（x）ならばx’はxの上にある。』
【００１９】
〔２〕シーケンス・ペアからパッキングの生成
シーケンス・ペアが抽出されると、このシーケンス・ペアにおいてブロックの並べ替えを行うことによって、最適なパッキングを探索する。探索は、焼きなまし法等の発見的方法を使用するのが効率的である。この際、シーケンス・ペアの並べ替えにより得られる各パッキングの評価を行う場合、シーケンス・ペアからパッキングを生成する必要がある。シーケンス・ペアからパッキングを生成する方法については、非特許文献１や特許文献１などで述べられているが、簡単に概説しておく。
【００２０】
まず、シーケンス・ペア（P，M）から次のような幾何学的制約が導かれる：
（１）『任意の２つのブロックx，x’に対して、x’∈Maa（x）ならば、Πにおいてx’はxの右、x’∈Mbb（x）ならば、x’はxの左になければならない。』
（２）『任意の２つのブロックx，x’に対して、x’∈Mab（x）ならば、x’はxの下、x’∈Mba（x）ならば、x’はxの上になければならない。』
かかる幾何学的制約を満たすΠを（P，M）パッキングと呼ぶ。非特許文献１においては、すべてのシーケンス・ペア（P，M）に対して（P，M）パッキングが存在することが証明されている。図１５に、（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングを示す。
【００２１】
次に、ブロック集合Bの（P，M）パッキングのうち、チップ面積が最小となるパッキングを求める方法を説明する。このようなパッキングを(P，M)-optimalと呼ぶ。(P，M)-optimalは、接点に重みづけがされた有向無閉路グラフに対して、最長路アルゴリズムを適用することによってO（m２）回の計算で得られる。
【００２２】
まず、シーケンス・ペア（P，M）の幾何学的制約（１）から、水平制約グラフGH＝（V，E）を次のように定義する：
【００２３】
【数３】
2006099416.tif 000005
【００２４】
ここで、V，V１，V２は節点の集合、E，E１，E２は枝の集合である。s，tは、それぞれ、涌出点（source）及び吸収点（sink）を表し、iはそれ以外の水平制約グラフGHの節点を表す。ш(x)は節点xの重みを表す。w(xi)はブロックxiの幅を表す。
【００２５】
垂直制約グラフGVは、幾何学的制約（２）の上下の位置関係と各ブロックx（∈B）の高さh(x)に基づいて同様に定義する。図１６は（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングの（a）水平制約グラフ、及び（b）垂直制約グラフである。何れのグラフも有向閉路を含まない。また、各ブロックの対（xi，xj）に対して、GH又はGVの何れか一方に辺が存在し、両方に辺が存在することはない。従って、各ブロックのx座標とy座標は、配置の制約を満たしつつ独立に決定することができ、その結果、重なりのないブロック配置が得られる。各モジュールxi（∈B）のx座標及びy座標は、それぞれ、グラフGH，GV内の涌出点sと節点iとの間の最長路（路上の節点の重みの和が最大の路）における節点i以外の節点の重みの和として決定される。同様に、チップの高さと幅は、それぞれ、グラフGH，GV内の涌出点sと吸収点tとの間の最長路における節点の重みの和として決定される。チップの幅と高さとは独立に最小化することができ、その結果得られるパッキングは(P，M)-optimalである。図１７は最長路計算の結果得られたブロック配置の一例を示している。
【特許文献１】特開平９−１０８９３４号公報
【特許文献２】特開平９−１０８９３３号公報
【非特許文献１】H.Murata, K.Fujiyoshi, S.Nakatake, and Y.Kajitani, "VLSI module placement based on rectangle-packing by the sequence pair," IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, Vol.15, No.12, pp.1518-1524, 1996.
【非特許文献２】Y.Kubo, S.Nakatake, Y.Kajitani, and M.Kawakita, "Explicit Expression and Simultaneous Optimization of Placement and Routing for Analog IC Layouts," Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference 2002, pp.467-472, 2002.
【発明の開示】
【発明が解決しようとする課題】
【００２６】
上述のように、従来のVLSIのコンパクションにおける幾何学的制約の抽出は、基本的には、初期レイアウトとして与えられた回路素子や配線を矩形近似し、それらの矩形状のブロックの上下左右の位置関係を抽出することによりなされる。この場合、ブロック同士に重なりがある場合には、ブロックの形状と初期の位置座標から判断し、初期レイアウト上での各ブロックのおよその位置関係を維持するように、各ブロックの上下左右の位置関係を抽出して初期のシーケンス・ペアを決定する必要がある。この決定次第では、配線の結線を切断してしまったり、回路性能を著しく低下させてしまったりする場合がある。
【００２７】
また、レイアウト設計においては、設計規則により各ブロック間に所定のクリアランスをとることが要求される。かかる設計規則による制約が課せられた場合、初期のシーケンス・ペアを決定する際にも設計規則を考慮して決定する必要が生じる。
【００２８】
更に、回路性能を向上させるため、一連の回路素子を直線上に配置したり、幾つかの回路素子を対称に配置したりするように要求される場合も多い。従って、この場合、初期レイアウトにおける幾つかのブロックの直線的配列の制約や対称配置の制約を保存するように、初期のシーケンス・ペアを決定する必要がある。
【００２９】
しかしながら、上述のように、従来の方法では、初期のパッキングからシーケンス・ペアの抽出する際に、各ブロック間の具体的な配置制約に関する情報は捨象され、上に述べた各種の制約は考慮されない。従って、必ずしも設計規則の制約や回路性能向上を図るための制約を満たすコンパクションができないという問題がある。
【００３０】
そこで、本発明の目的は、与えられたブロック配置から、初期レイアウトにおけるブロックの配置上の制約を反映したシーケンス・ペアを抽出することが可能なシーケンス・ペア作成技術を提供することにある。
【課題を解決するための手段】
【００３１】
本発明に係るシーケンス・ペア作成装置の第１の構成は、幅及び高さが与えられたN（≧２）個の矩形のブロックの集合（以下、「ブロック集合」という。）Bに属する各ブロックbi（i＝１，…，N）の幅w（bi）及び高さh（bi）の情報（以下、「サイズ情報」という。）、並びに前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロックbi（i＝１，…，N）の位置座標（x（bi），y（bi））からなるブロック配置情報を記憶するブロック配置記憶手段を有し、それぞれが独立な前記ブロック集合Bに属するブロックbi（i＝１，…，N）の順列P及びMの対であって、前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロック間の位置関係を特定するシーケンス・ペア（P，M）の作成を行うシーケンス・ペア作成装置であって、前記順列P，Mにおける２つのブロックbi，bj（∈B）間の順序関係であって、前記ブロック配置情報及びサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約から導出される関係である二項関係pord（bi，bj），mord（bi，bj）を、前記ブロック配置情報及びサイズ情報に従って決定する二項関係決定手段と、前記二項関係決定手段により決定されるすべての二項関係pord（bi，bj），mord（bi，bj）（bi，bj∈B）を満たすように、前記ブロック配置情報及びサイズ情報に基づいて前記順列P，Mにおけるブロックの全順序関係を決定する全順序関係決定手段とを備えていることを特徴とする。
【００３２】
この構成により、二項関係決定手段が、ブロック配置情報及びサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約を、２つのブロック間の二項関係pord（bi，bj），mord（bi，bj）として抽出する。全順序関係決定手段は、すべての二項関係pord（bi，bj），mord（bi，bj）（bi，bj∈B）を満たすように、順列P，Mにおけるブロックの全順序関係を決定する。従って、これによって得られるシーケンス・ペア（P，M）は、上記の各ブロック間の配置制約が取り込まれたものとなる。
【００３３】
従って、各ブロック間の配置制約が取り込まれたシーケンス・ペア（P，M）に基づいて、チップ上への各ブロックのパッキングを行えば、配置制約を充足する最適パッキングを行うことが可能となる。
【００３４】
この場合、シーケンス・ペア（P，M）の作成時に各ブロック間の配置制約を取り込むのではなく、一旦、各ブロック間の配置制約を２つのブロック間の二項関係pord（bi，bj），mord（bi，bj）として抽象化して抽出し、抽出された二項関係pord（bi，bj），mord（bi，bj）を各順列P，Mの全順序決定時に取り込む。従って、順列P，Mへの各ブロック間の配置制約の取り込みが容易であり、少ない計算量で実行することが可能となる。
【００３５】
本発明に係るシーケンス・ペア作成装置の第２の構成は、前記第１の構成において、前記二項関係決定手段は、前記ブロック配置記憶手段に記憶された２つのブロックbi，bj（∈B）の位置座標（x（bi），y（bi）），（x（bj），y（bj））、幅w（bi），w（bj）、及び高さh（bi），h（bj）を参照することにより、ブロックbi及びブロックbjの垂直方向（以下、「y方向」という。）の辺のy座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjの水平方向（以下、「x方向」という。）に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の左右関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定し、ブロックbi及びブロックbjのx方向の辺のx座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjのy方向に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の上下関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する離反制約抽出手段を備えていることを特徴とする。ここで、「クリアランス」とは、許容される二つのブロック間の距離の最小値をいう。
【００３６】
この構成によれば、離反制約抽出手段は、２つのブロックbi，bj間で、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報において、x方向のクリアランスがありy方向のクリアランスがない場合には、ブロックbi，bjは左右の順序関係があると判断する。そして、ブロックbi，bjの位置座標の左右関係に従って二項関係pord（bi，bj），mord（bi，bj）を決定する。
【００３７】
一方、離反制約抽出手段は、２つのブロックbi，bj間で、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報において、y方向のクリアランスがありx方向のクリアランスがない場合には、ブロックbi，bjは上下の順序関係があると判断する。そして、ブロックbi，bjの位置座標の上下関係に従って二項関係pord（bi，bj），mord（bi，bj）を決定する。
【００３８】
これにより、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報において、設計基準を満たして配置されているブロックの順序関係を抽出し、その順序関係をシーケンス・ペアに反映させることが可能となる。
【００３９】
本発明に係るシーケンス・ペア作成装置の第３の構成は、前記第１の構成において、前記二項関係決定手段は、前記ブロック配置記憶手段に記憶されたブロック集合Bの部分集合Bk（⊆B）に属する各ブロックbi（∈Bk）に対して、それらのブロックの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）が課せられている場合、前記各ブロックbi（∈Bk）の位置座標の上下関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直共線制約抽出手段を備えていることを特徴とする。
【００４０】
この構成によれば、垂直共線制約抽出手段は、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報から抽出され、又は設計者によって外部から入力される垂直共線制約に従って、二項関係pord（bi，bj），mord（bi，bj）を決定する。全順序関係決定手段は、この二項関係を満たす順列P，Mの全順序関係を決定する。これにより、初期のブロック配置で与えられた垂直共線制約、又は設計者によって外部入力により与えられた垂直共線制約をシーケンス・ペアに反映させることが可能となる。
【００４１】
ここで、ブロックの「代表点」とは、そのブロックの位置を代表する点である。代表点は、通常はブロックの重心点とされるが、それに限られるものではない。
【００４２】
本発明に係るシーケンス・ペア作成装置の第４の構成は、前記第１の構成において、前記二項関係決定手段は、前記ブロック配置記憶手段に記憶されたブロック集合Bの部分集合Bkに属する各ブロックに対して、それらのブロックの上辺又は下辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）が課せられている場合、前記部分集合Bkに属する各ブロックbi（∈Bk）の位置座標の左右関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平共線制約抽出手段を備えていることを特徴とする。
【００４３】
この構成によれば、垂直共線制約抽出手段は、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報から抽出され、又は設計者によって外部から入力される水平共線制約に従って、二項関係pord（bi，bj），mord（bi，bj）を決定する。全順序関係決定手段は、この二項関係を満たす順列P，Mの全順序関係を決定する。これにより、初期のブロック配置で与えられた水平共線制約、又は設計者によって外部入力により与えられた水平共線制約をシーケンス・ペアに反映させることが可能となる。
【００４４】
本発明に係るシーケンス・ペア作成装置の第５の構成は、前記第１の構成において、前記二項関係決定手段は、前記ブロック配置記憶手段に記憶されたブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して水平方向の対称位置に配置する制約（以下、「水平対称制約（horizontal symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の左右関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平対称制約抽出手段を備えていることを特徴とする。
【００４５】
この構成によれば、垂直共線制約抽出手段は、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報から抽出され、又は設計者によって外部から入力される水平対称制約に従って、二項関係pord（bi，bj），mord（bi，bj）を決定する。全順序関係決定手段は、この二項関係を満たす順列P，Mの全順序関係を決定する。これにより、初期のブロック配置で与えられた水平対称制約、又は設計者によって外部入力により与えられた水平対称制約をシーケンス・ペアに反映させることが可能となる。
【００４６】
本発明に係るシーケンス・ペア作成装置の第６の構成は、前記第１の構成において、前記二項関係決定手段は、前記ブロック配置記憶手段に記憶されたブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して垂直方向の対称位置に配置する制約（以下、「垂直対称制約（vertical symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の上下関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直対称制約抽出手段を備えていることを特徴とする。
【００４７】
この構成によれば、垂直共線制約抽出手段は、ブロック配置記憶手段に記憶されたブロック配置情報及びサイズ情報から抽出され、又は設計者によって外部から入力される垂直対称制約に従って、二項関係pord（bi，bj），mord（bi，bj）を決定する。全順序関係決定手段は、この二項関係を満たす順列P，Mの全順序関係を決定する。これにより、初期のブロック配置で与えられた垂直対称制約、又は設計者によって外部入力により与えられた垂直対称制約をシーケンス・ペアに反映させることが可能となる。
【００４８】
本発明に係るシーケンス・ペア作成装置の第７の構成は、前記第１乃至６の何れか一の構成において、前記二項関係決定手段は、前記ブロック集合Bに属する３つのブロックbi，bj，bkについて、二項関係pord（bi，bj），pord（bj，bk）が決定され且つ二項関係pord（bi，bk）が未決定の場合、二項関係pord（bi，bj），pord（bj，bk）から二項関係pord（bi，bk）を推移的に決定し、二項関係mord（bi，bj），mord（bj，bk）が決定され且つ二項関係mord（bi，bk）が未決定の場合、二項関係mord（bi，bj），mord（bj，bk）から二項関係mord（bi，bk）を推移的に決定する二項関係推移決定手段を備えていることを特徴とする。
【００４９】
この構成により、離反制約、水平共線制約、垂直共線制約、水平対称制約、垂直対称制約等の各種制約により二項関係pord（bi，bj），pord（bj，bk）（又はmord（bi，bj），mord（bj，bk））が与えられた場合、二項関係推移決定手段は、二項関係pord（bi，bk）（又はmord（bi，bk））を推移的に無矛盾となるように決定する。これにより、全順序関係決定手段は、ブロックbi，bj，bk間の順序関係が無矛盾となるように、順列P，Mの全順序関係を決定することができる。
【００５０】
本発明に係るシーケンス・ペア作成装置の第８の構成は、前記第１乃至７の何れか一の構成において、前記二項関係決定手段は、前記ブロック集合Bに属する２つのブロックbi，bjについて、ブロックbiがブロックbjの左にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝１，mord（bi，bj）＝１に決定し、ブロックbiがブロックbjの下にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝０，mord（bi，bj）＝１に決定するものであり、前記全順序関係決定手段は、順列Pにおける順序が未決定のブロックの集合Bn（⊆B）に属するブロックbi（∈Bn）について、集合Bnに属する当該ブロックbi以外のすべてのブロックbj（∈Bn）との間の二項関係pord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bs（⊆Bn）とし、集合Bsに属するブロックbiのうち、集合Bsに属する当該ブロックbi以外のすべてのブロックbj（∈Bs）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Pに左から詰めて並べるという操作を繰り返すことにより、順列Pにおける各ブロックの順序を、左から順次決定するP順序決定手段と、順列Mにおける順序が未決定のブロックの集合Bm（⊆B）に属するブロックbi（∈Bm）について、集合Bmに属する当該ブロックbi以外のすべてのブロックbj（∈Bm）との間の二項関係mord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bt（⊆Bm）とし、集合Btに属するブロックbiのうち、集合Btに属する当該ブロックbi以外のすべてのブロックbj（∈Bt）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Mに左から詰めて並べるという操作を繰り返すことにより、順列Mにおける各ブロックの順序を、左から順次決定するM順序決定手段とを備えていることを特徴とする。
【００５１】
この構成により、全順序関係決定手段は、二項関係pord（bi，bj），mord（bi，bj）より、順列P，Mにおけるブロックbi，bjの順序関係を一意的決定することができる。従って、離反制約、水平共線制約、垂直共線制約、水平対称制約、垂直対称制約等の各種制約をシーケンス・ペアに反映させることが可能となる。
【００５２】
本発明に係るシーケンス・ペア作成装置の第９の構成は、前記第１乃至８の何れか一の構成において、前記ブロック配置記憶手段に記憶された前記ブロック集合Bに属するブロックに重なりがある場合、重なった２つのブロックの何れか一方又は両方の幅又は高さを短縮することにより、ブロック間の重なりのないブロック配置情報及びサイズ情報を生成する重なり除去手段を備え、前記全順序関係決定手段は、前記二項関係決定手段により決定された二項関係pord（bi，bj），mord（bi，bj）を満たすように、前記重なり除去手段により生成されたブロック間の重なりのないブロック配置情報及びサイズ情報に従って前記順列P，Mにおけるブロックの全順序関係を決定することを特徴とする。
【００５３】
この構成によれば、初期に与えられたブロック配置において、ブロック間に重なりがある場合、重なり除去手段がその重なりを除去する。そして、全順序関係決定手段は、重なりのないブロック配置を用いてシーケンス・ペアを生成する。これにより、ブロック同士の重なりによってブロック間の順序関係が決定できないという事態が生じることを回避することができる。
【００５４】
本発明に係るシーケンス・ペア作成方法の第１の構成は、形状が与えられたN（≧２）個の矩形のブロックの集合（以下、「ブロック集合」という。）Bに属する各ブロックbi（i＝１，…，N）の幅w（bi）及び高さh（bi）の情報（以下、「サイズ情報」という。）、及び前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロックbi（i＝１，…，N）の位置座標（x（bi），y（bi））からなるブロック配置情報に基づき、前記ブロック集合Bに属するブロックbi（i＝１，…，N）の順列P及びMの対であって、前記ブロック集合Bに属するすべてのブロックをチップ上に配置する場合の各ブロック間の位置関係を特定するシーケンス・ペア（P，M）の作成を行うシーケンス・ペア作成方法であって、前記順列P及びMにおける２つのブロックbi，bj（∈B）間の順序関係であって、前記ブロック配置情報及び各ブロックのサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約から導出される関係である二項関係pord（bi，bj），mord（bi，bj）を、前記ブロック配置情報及び各ブロックのサイズ情報に従って決定する二項関係決定ステップと、前記二項関係決定ステップで決定されるすべての二項関係pord（bi，bj），mord（bi，bj）（bi，bj∈B）を満たすように、前記ブロック配置情報及び各ブロックのサイズ情報に基づいて前記順列P及びMにおける各ブロックの全順序関係を決定する全順序関係決定ステップとを有することを特徴とする。
【００５５】
本発明に係るシーケンス・ペア作成方法の第２の構成は、前記第１の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bに属する２つのブロックbi，bj（∈B）の位置座標（x（bi），y（bi）），（x（bj），y（bj））、幅w（bi），w（bj）、及び高さh（bi），h（bj）を参照することにより、ブロックbi及びブロックbjの垂直方向（以下、「y方向」という。）の辺のy座標に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjの水平方向（以下、「x方向」という。）に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の左右関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定し、ブロックbi及びブロックbjのx方向に０以上の所定幅のクリアランスがなく、且つブロックbi及びブロックbjのy方向に０以上の所定幅のクリアランスがある場合、ブロックbi，bjの位置座標の上下関係に従ってブロックbiとブロックbjとの間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する離反制約抽出ステップを有していることを特徴とする。
【００５６】
本発明に係るシーケンス・ペア作成方法の第３の構成は、前記第１の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bの部分集合Bk（⊆B）に属する各ブロックbi（∈Bk）に対して、それらのブロックの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）が課せられている場合、前記各ブロックbi（∈Bk）の位置座標の上下関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直共線制約抽出ステップを有していることを特徴とする。
【００５７】
本発明に係るシーケンス・ペア作成方法の第４の構成は、前記第１の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bの部分集合Bkに属する各ブロックに対して、それらのブロックの上辺又は下辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）が課せられている場合、前記部分集合Bkに属する各ブロックbi（∈Bk）の位置座標の左右関係に従って、前記部分集合Bkに属する２つのブロックbi，bj間の順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平共線制約抽出ステップを有していることを特徴とする。
【００５８】
本発明に係るシーケンス・ペア作成方法の第５の構成は、前記第１の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して水平方向の対称位置に配置する制約（以下、「水平対称制約（horizontal symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の左右関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する水平対称制約抽出ステップを有していることを特徴とする。
【００５９】
本発明に係るシーケンス・ペア作成方法の第６の構成は、前記第１の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bに属する３つのブロックbi，bj，bkに対して、ブロックbi及びブロックbkをブロックbjに対して垂直方向の対称位置に配置する制約（以下、「垂直対称制約（vertical symmetrical constraint）」という。）が課せられている場合、ブロックbi及びブロックbkについて、両ブロックの位置座標の上下関係に従って、順列P，Mにおける二項関係pord（bi，bj），mord（bi，bj）を決定する垂直対称制約抽出ステップを有していることを特徴とする。
【００６０】
本発明に係るシーケンス・ペア作成方法の第７の構成は、前記第１乃至６の何れか一の構成において、前記二項関係決定ステップにおいて、前記ブロック集合Bに属する３つのブロックbi，bj，bkについて、二項関係pord（bi，bj），pord（bj，bk）が決定され且つ二項関係pord（bi，bk）が未決定の場合、二項関係pord（bi，bj），pord（bj，bk）から二項関係pord（bi，bk）を推移的に決定し、二項関係mord（bi，bj），mord（bj，bk）が決定され且つ二項関係mord（bi，bk）が未決定の場合、二項関係mord（bi，bj），mord（bj，bk）から二項関係mord（bi，bk）を推移的に決定する二項関係推移決定ステップを有していることを特徴とする。
【００６１】
本発明に係るシーケンス・ペア作成方法の第８の構成は、前記第１乃至７の何れか一の構成において、前記二項関係決定ステップにおいては、前記ブロック集合Bに属する２つのブロックbi，bjについて、ブロックbiがブロックbjの左にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝１，mord（bi，bj）＝１に決定し、ブロックbiがブロックbjの下にある場合には順列P，Mにおける二項関係をpord（bi，bj）＝０，mord（bi，bj）＝１に決定し、前記全順序関係決定ステップにおいて、順列Pにおける順序が未決定のブロックの集合Bn（⊆B）に属するブロックbi（∈Bn）について、集合Bnに属する当該ブロックbi以外のすべてのブロックbj（∈Bn）との間の二項関係pord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bs（⊆Bn）とし、集合Bsに属するブロックbiのうち、集合Bsに属する当該ブロックbi以外のすべてのブロックbj（∈Bs）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Pに左から詰めて並べるという操作を繰り返すことにより、順列Pにおける各ブロックの順序を、左から順次決定するP順序決定ステップと、順列Mにおける順序が未決定のブロックの集合Bm（⊆B）に属するブロックbi（∈Bm）について、集合Bmに属する当該ブロックbi以外のすべてのブロックbj（∈Bm）との間の二項関係mord（bi，bj）が１でないものを抽出し、抽出されたブロックの集合を集合Bt（⊆Bm）とし、集合Btに属するブロックbiのうち、集合Btに属する当該ブロックbi以外のすべてのブロックbj（∈Bt）に対して、当該ブロックbiの右辺がブロックbjの左辺よりも左又は共線位置にあるもの、若しくは当該ブロックbiの下辺がブロックbjの上辺よりも上にあるものを選択し、選択された当該ブロックbiを順列Mに左から詰めて並べるという操作を繰り返すことにより、順列Mにおける各ブロックの順序を、左から順次決定するM順序決定ステップとを備えていることを特徴とする。
【００６２】
本発明に係るシーケンス・ペア作成方法の第９の構成は、前記第１乃至８の何れか一の構成において、前記ブロック集合Bに属するブロックに重なりがある場合、重なった２つのブロックの何れか一方又は両方の幅又は高さを短縮することにより、ブロック間の重なりのないブロック配置情報及びサイズ情報を生成する重なり除去ステップを備え、前記全順序関係決定ステップにおいては、前記二項関係決定ステップにおいて決定された二項関係pord（bi，bj），mord（bi，bj）を満たすように、前記重なり除去ステップにおいて生成されたブロック間の重なりのないブロック配置情報及びサイズ情報に従って前記順列P，Mにおけるブロックの全順序関係を決定することを特徴とする。
【００６３】
本発明に係るプログラムは、前記第１乃至第９の構成のシーケンス・ペア作成方法をコンピュータに実行させることを特徴とする。
【発明の効果】
【００６４】
以上のように、本発明によれば、二項関係決定手段により各ブロック間の配置制約を２つのブロック間の二項関係pord（bi，bj），mord（bi，bj）として抽出し、全順序関係決定手段は、この二項関係pord（bi，bj），mord（bi，bj）をすべて満たすように各順列P，Mの全順序を決定する。これにより、少ない計算量で、各ブロック間の配置制約を取り込んだ順列P，Mを生成することが可能となる。
【発明を実施するための最良の形態】
【００６５】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００６６】
図１は、本発明の実施例１に係るシーケンス・ペア作成装置の構成を表す図である。シーケンス・ペア作成装置１は、入力部２、表示部３、中央演算装置４、ブロック配置記憶手段５、配置制約記憶手段６、二項関係記憶手段７、及びシーケンス・ペア記憶手段８を備えている。
【００６７】
入力部２は、設計者が初期のブロック配置情報やサイズ情報、各種制約に関する情報等を入力する部分である。表示部３は、ディスプレイやプリンタ等であり、ブロック配置情報やシーケンス・ペアの情報を出力する。中央演算装置４は、初期のブロック配置情報、サイズ情報、及び各種制約の情報から、シーケンス・ペアを作成する演算処理を行う。
【００６８】
ブロック配置記憶手段５は、入力部２から入力されるブロック配置情報及びサイズ情報を一時的に記憶する。以下では、ブロック配置記憶手段５に保存されるブロック配置情報に含まれるブロックの集合をBと記す。配置制約記憶手段６は、入力部２から各種制約の情報が入力された場合にはそれを記憶する。二項関係記憶手段７は、中央演算装置４によりブロック配置情報及びサイズ情報から各種制約に基づいて決定されるブロック間の二項関係の情報を記憶する。シーケンス・ペア記憶手段８は、中央演算装置４においてブロック配置情報及びサイズ情報から抽出されるシーケンス・ペアを記憶する。
【００６９】
中央演算装置４は、二項関係決定手段９、重なり除去手段１０、及び全順序関係決定手段１１を備えている。これらは、入力部２からプログラムをロードすることによって機能的モジュールとして構成される。
【００７０】
二項関係決定手段９は、ブロック配置記憶手段５に記憶されたブロック配置に含まれる各ブロックの二項関係pord（bi，bj），mord（bi，bj）を、ブロック配置情報及びサイズ情報に従って決定する。ここで、二項関係pord（bi，bj），mord（bi，bj）は、作成するシーケンス・ペア（P，M）の各順列P，Mにおける２つのブロックbi，bj（∈B）間の順序関係であって、ブロック配置情報及びサイズ情報から抽出され又は外部入力により指定される各ブロック間の配置制約から導出される関係をいう。
【００７１】
二項関係決定手段９は、更に、離反制約抽出手段１２、垂直共線制約抽出手段１３、水平共線制約抽出手段１４、水平対称制約抽出手段１５、垂直対称制約抽出手段１６、及び二項関係推移決定手段１７の部分構成を備えている。
【００７２】
離反制約抽出手段１２は、ブロック配置情報及びサイズ情報から、離反制約を満たすブロック対を抽出し、そのブロック対に対する順列P，Mにおける二項関係を決定する。尚、離反制約については、後で詳細に説明する。
【００７３】
垂直共線制約抽出手段１３及び水平共線制約抽出手段１４は、ブロック配置情報及びサイズ情報から抽出され、又は設計者によって入力部２から入力される垂直共線制約，水平共線制約に従って、当該制約の対称となるブロックについての順列P，Mにおける二項関係を決定する。尚、垂直共線制約及び水平共線制約については、後で詳細に説明する。
【００７４】
水平対称制約抽出手段１５及び垂直対称制約抽出手段１６は、ブロック配置情報及びサイズ情報から抽出され、又は設計者によって入力部２から入力される垂直対称制約，水平対称制約に従って、当該制約の対称となるブロックについての順列P，Mにおける二項関係を決定する。尚、垂直対称制約及び水平対称制約については、後で詳細に説明する。
【００７５】
これらの各制約抽出手段により抽出される順列P，Mにおけるブロック間の二項関係は、二項関係記憶手段７に保存される。二項関係推移決定手段１７は、二項関係記憶手段７に保存された二項関係に基づいて、二項関係が未決定のブロック対に関して推移的に二項関係が決定できるものについて二項関係を決定する。
【００７６】
重なり除去手段１０は、ブロック配置記憶手段５に記憶されたブロック配置Φにおいてブロック集合Bに属するブロックに重なりがある場合、重なった２つのブロックの何れか一方又は両方の幅又は高さを短縮することにより、ブロック間の重なりのないブロック配置情報及びサイズ情報（パッキングΠ）を生成する。
【００７７】
全順序関係決定手段１１は、二項関係決定手段９により決定されるすべての二項関係pord（bi，bj），mord（bi，bj）（bi，bj∈B）を満たすように、重なり除去手段１０による重なり除去がされたブロック配置情報及びサイズ情報（パッキングΠ）に基づいて順列P，Mにおけるブロックの全順序関係を決定する。
【００７８】
全順序関係決定手段１１は、更に、P順序決定手段１８及びM順序決定手段１９の部分構成を備えている。P順序決定手段１８及びM順序決定手段１９は、それぞれ、シーケンス・ペアの順列P及び順列Mにおけるブロックの全順序決定処理を行う。
【００７９】
以上のように構成された本実施例に係るシーケンス・ペア作成装置１について、以下その動作を説明する。
【００８０】
まず、本発明の実施例１に係るシーケンス・ペア作成装置によるシーケンス・ペアの作成方法の全体の流れを図２に示す。最初に、設計者によって、入力部２を介してブロック配置記憶手段５に初期のブロック配置情報及び各ブロックのサイズ情報が入力される（Ｓ１）。また、このとき、設計者は、必要に応じて、特定のブロック間の各種制約（ブロック間のクリアランスや垂直共線制約等）を入力部２から入力する。入力された各種制約は、配置制約記憶手段６に格納される。
【００８１】
次に、二項関係決定手段９は、ブロック配置記憶手段５に保存されているブロック配置情報及びサイズ情報から、各種制約により導出されるシーケンス・ペア（P，M）の順列P，Mにおけるブロック対間の二項関係を抽出し、抽出された二項関係を二項関係記憶手段７に保存する（Ｓ２）。
【００８２】
次いで、重なり除去手段１０は、ブロック配置記憶手段５に保存されているブロック配置情報及びサイズ情報から、重なりのあるブロック対を探索し、重なりを除去する処理を行う。この重なり除去処理がされたブロック配置情報及びサイズ情報は、全順序関係決定手段１１に出力される（Ｓ３）。
【００８３】
最後に、全順序関係決定手段１１において、P順序決定手段１８により順列Pの全順序の確定処理が行われる（Ｓ４）。また、M順序決定手段１９により順列Mの全順序の確定処理が行われる（Ｓ５）。これにより、シーケンス・ペア（P，M）が確定する。確定したシーケンス・ペア（P，M）は、シーケンス・ペア記憶手段８に出力され、ここに保存される。
【００８４】
以上がシーケンス・ペア方法の全体的な処理の流れであるが、以下、主要な各ステップにおける演算処理に関して詳細に説明する。
【００８５】
〔１〕準備
最初に、以下の説明で使用する各用語の定義を述べる。ブロック配置記憶手段５に記憶されている初期のブロック配置に含まれるすべてのブロック集合をB＝｛b１，b２，…，bN｝と記す。Nはブロック集合Bの全ブロック数である。各ブロックは矩形である。ブロックbi（∈B）の位置を特定する座標（位置座標）を（x（bi），y（bi））と記す。ここでは、各ブロックの位置座標は当該ブロックの左下の座標を表すものとする。ブロック配置情報は、各ブロックの位置座標の集合｛（x（bi），y（bi））｜∀bi∈B｝により与えられる。また、ブロックbi（∈B）の幅をw（bi）、高さをh（bi）と記す。各ブロックのサイズ情報は、各ブロックの幅と高さの組の集合｛（w（bi），h（bi））｜∀bi∈B｝により与えられる。
【００８６】
〔１−１〕各種制約の定義
（１）離反制約
離反制約とは、ブロック集合Bに属する任意の２つのブロックbi，bjの対（bi，bj）に対し、ブロック間の間隔（クリアランス）が所定の値以上でなければならないとする制約をいう。x（bi）＜x（bj）の場合、水平方向の離反制約は次のように表される：
【００８７】
【数４】
2006099416.tif 000006
同様に、y（bi）＜y（bj）の場合、水平方向の離反制約は次のように表される：
【００８８】
【数５】
2006099416.tif 000007
【００８９】
離反制約は、設計仕様から課される制約である。すなわち、チップ上において、各素子ブロック間での絶縁性を確保するために、所定の距離のクリアランスを確保することが要求される。離反制約は、ブロックの初期配置Φにおいてクリアランスを確保して配置されているブロックを抽出し、そのクリアランスによる配置関係をシーケンス・ペアに保存させるために課される。
【００９０】
具体的に、離反制約を図３の例を用いて説明する。ブロックb０に注目する。図３（a）において、ブロックb０に対して式（８）の水平方向の離反制約を満たすブロックは、b4，b６，b７，b８，b9である。また、図３（b）において、ブロックb０に対して式（９）の垂直方向の離反制約を満たすブロックは、b1，b７，b８，b９，b１０である。
【００９１】
（２）共線制約
共線制約とは、ブロック集合Bのある部分集合Bk（∈B）に対して、部分集合Bk（⊆B）内のすべてのブロックbi（∈Bk）について上下左右の何れかの辺若しくは代表点を一直線上に揃える制約をいう。上辺又は下辺若しくは代表点を水平直線上に揃える制約を水平共線制約、左辺又は右辺若しくは代表点を垂直直線上に揃える制約を垂直共線制約という。また、部分集合Bk（∈B）に属する各ブロックに対して、左辺を揃えるようにブロックを配置する共線制約をALIGNL(Bk)、下辺を揃えるようにブロックを配置する共線制約をALIGNB(Bk)、右辺を揃えるようにブロックを配置する共線制約をALIGNR(Bk)、上辺を揃えるようにブロックを配置する共線制約をALIGNT(Bk)と記す。部分集合Bk（∈B）に属する各ブロックに対して、代表点を水平直線上に揃えるようにブロックを配置する共線制約をALIGNCH(Bk)、代表点を垂直直線上に揃えるようにブロックを配置する共線制約をALIGNCV(Bk)と記す。
【００９２】
共線制約は、チップ上に部品を配置する場合において、同様の回路構造が繰り返して並べられているような場合に、各構造を直線上に整列するように部品配置を行うために課せられる制約である。
【００９３】
具体的に、共線制約を図４の例を用いて説明する。図４（a）において、４つのブロックb１，b２，b３，b４は左辺が一直線上に揃えられている。従って、図４（a）の４つのブロックの集合Bk＝｛b１，b２，b３，b４｝は、共線制約ALIGNL(Bk)が課されている。また、図４（b）において、４つのブロックb１，b２，b３，b４は下辺が一直線上に揃えられている。従って、図４（b）の４つのブロックの集合Bk＝｛b１，b２，b３，b４｝は、共線制約ALIGNB(Bk)が課されている。
【００９４】
（３）対称制約
対称制約とは、ブロック集合Bに属する３つのブロックbi，bj，bk（∈B）に対して、bjを中心として左右方向又は上下方向にbi及びbjを対称に配置する制約をいう。左右方向の対称制約を水平対称制約といい、SYMMH(bi, bj, bk)と記す。上下方向の対称制約を垂直対称制約といい、SYMMV(bi, bj, bk)と記す。図５（a）は、水平対称制約SYMMH(bi, bj, bk)の一例を示しており、図５（b）は、垂直対称制約SYMMV(bi, bj, bk)の一例を示している。
【００９５】
x（bi）＜x（bj）＜x（bk）の場合、水平対称制約は次のように表される：
【００９６】
【数６】
2006099416.tif 000008
【００９７】
y（bi）＜y（bj）＜y（bk）の場合、垂直対称制約は次のように表される：
【００９８】
【数７】
2006099416.tif 000009
【００９９】
対称制約は、例えば、MOSトランジスタで構成される差動増幅回路のように、チップ上に部品を対称に配置する必要がある場合に課される制約である。
【０１００】
〔１−２〕シーケンス・ペア
ブロック集合Bに属するブロック間の左右関係及び上下関係を非特許文献１と同様に次のように定義する：
【０１０１】
（１）左右関係
ブロック集合Bに属する任意の２つのブロックbi，bjの対（bi，bj）について、関係x（bi）＋w（bi）≦x（bj）が成り立つとき、ブロックbiはブロックbjの左にある（又は、ブロックbjはブロックbiの右にある）という。
【０１０２】
（２）上下関係
ブロック集合Bに属する任意の２つのブロックbi，bjの対（bi，bj）について、関係y（bi）＋h（bi）≦y（bj）が成り立つとき、ブロックbiはブロックbjの下にある（又は、ブロックbjはブロックbiの上にある）という。
【０１０３】
また、シーケンス・ペアについても、非特許文献１と同様に次のように定義する：
【０１０４】
（３）シーケンス・ペア
N個のブロックからなるブロック集合B＝｛b１，b２，…，bN｝が与えられたとする。集合Bのすべてのブロックの順列（sequence）である２つのブロック順列をP＝（p１，p２，…，pN）（∀pi∈B）及びM＝（m１，m２，…，mN）（∀mi∈B）と記す。このとき、２つの順列の対（P，M）をシーケンス・ペアという。
【０１０５】
（４）ブロック配置のシーケンス・ペア
順列Pにおけるブロックbi（∈B）の順序をα（bi）、順列Mにおけるブロックbi（∈B）の順序をβ（bi）と記す。すなわち、
【０１０６】
【数８】
2006099416.tif 000010
である。
【０１０７】
あるブロック配置において、ブロックの順列P，Mが、
（a）α（bi）＜α（bj）∧β（bi）＜β（bj）のとき、biはbjの左にある（bjはbiの右にある）、
（b）α（bi）＞α（bj）∧β（bi）＜β（bj）のとき、biはbjの下にある（bjはbiの上にある）、
という関係を満たしている場合、シーケンス・ペア（P，M）を、このブロック配置のシーケンス・ペアという。
【０１０８】
〔２〕二項関係の抽出処理
次に、図２のステップS２における２項順序の抽出処理について説明する。ここで、順列P，Mにおける二項関係は、それぞれ、次のように定義される変数pord（bi，bj），mord（bi，bj）により表される：
【０１０９】
【数９】
2006099416.tif 000011
【０１１０】
図６は、二項関係決定手段９による二項関係の抽出処理の手順を示すフローチャートである。まず、離反制約抽出手段１２により離反制約から決まる二項関係pord，mordの抽出が行われ、抽出された二項関係pord，mordは二項関係記憶手段７に記憶される（Ｓ１０）。次いで、垂直共線制約抽出手段１３及び水平共線制約抽出手段１４により、垂直共線制約，水平共線制約から決まる二項関係pord，mordの抽出が行われ、抽出された二項関係pord，mordは二項関係記憶手段７に記憶される（Ｓ１１）。次いで、水平対称制約抽出手段１５及び垂直対称制約抽出手段１６により、水平対称制約，垂直対称制約から決まる二項関係pord，mordの抽出が行われ、抽出された二項関係pord，mordは二項関係記憶手段７に記憶される（Ｓ１２）。最後に、二項関係推移決定手段１７が、未だ決定されていないブロック間の二項関係のうち、二項関係記憶手段７に保存された各ブロック間の二項関係に基づき推移的に決定することができる二項関係を決定し、二項関係記憶手段７に保存する（Ｓ１３）。これらの各ステップにおける演算処理は、具体的には次のようにして実行される。
【０１１１】
〔２−１〕離反制約からの二項関係の抽出（Ｓ１０）
まず、離反制約抽出手段１２は、ブロック配置記憶手段５に記憶されている２つのブロックbi，bjを選択し、それらの位置座標（x（bi），y（bi）），（x（bj），y（bj））及びサイズ（w（bi），h（bi）），（w（bj），h（bj））を読み出す。また、ブロックbi，bj間のクリアランスDh（bi，bj），Dv（bi，bj）を配置制約記憶手段６から読み出す。尚、Dh（bi，bj），Dv（bi，bj）は、０以上の値が設定されている。また、これらのクリアランスの値は、すべてのブロック対について一定としてもよい。
【０１１２】
次に、離反制約抽出手段１２は、ブロック対（bi，bj）に対して次の関係が成立するか否かを検査する：
【０１１３】
【数１０】
2006099416.tif 000012
【０１１４】
式（１５）の関係が成立するとき、「biはbjの左にある」と決定し、
【０１１５】
【数１１】
2006099416.tif 000013
のように順序を確定する。すなわち、離反制約抽出手段１２は、順列P，Mにおけるbiとbjの二項関係を、
【０１１６】
【数１２】
2006099416.tif 000014
と決定し、これを二項関係記憶手段７に保存する。例えば、図３の例では、離反制約抽出手段１２は、ブロックb0に対して、「b6，b7，b8はb0の左にある」と決定する。
【０１１７】
同様に、離反制約抽出手段１２は、ブロック対（bi，bj）に対して次の関係が成立するか否かを検査する：
【０１１８】
【数１３】
2006099416.tif 000015
【０１１９】
式（１８）の関係が成立するとき、「biはbjの下にある」と決定し、
【０１２０】
【数１４】
2006099416.tif 000016
のように順序を確定する。すなわち、離反制約抽出手段１２は、順列P，Mにおけるbiとbjの二項関係を、
【０１２１】
【数１５】
2006099416.tif 000017
と決定し、これを二項関係記憶手段７に保存する。例えば、図３の例では、離反制約抽出手段１２は、ブロックb0に対して、「b7，b8，b9，b10はb0の下にある」と決定する。
【０１２２】
〔２−２〕共線制約からの二項関係の抽出（Ｓ１１）
垂直共線制約抽出手段１３及び水平共線制約抽出手段１４は、ブロック配置記憶手段５に記憶されたブロック集合Bの中から、一辺又はブロックの代表点が水平又は垂直直線上に並べられた一連のブロック群を抽出し、これを共線制約が課せられる部分集合Bk（⊆B）とする。また、設計者により共線制約が課せられる部分集合Bk（⊆B）が予め指定されている場合には、その部分集合Bkを配置制約記憶手段６から読み出す。
【０１２３】
次に、垂直共線制約抽出手段１３及び水平共線制約抽出手段１４は、部分集合Bkにおいて、Bkに属する各ブロックbi（i＝１，２，…，Nk）をx（bi）が小さい順に整列する。以下、この整列を行ったときのブロックbiの順序をxord（bi）と記す。同様に、部分集合Bkにおいて、Bkに属する各ブロックbi（i＝１，２，…，Nk）をy（bi）が小さい順に整列する。以下、この整列を行ったときのブロックbiの順序をyord（bi）と記す。
【０１２４】
（１）部分集合Bkに対してALIGNL(Bk)又はALIGNR(Bk)若しくはALIGNCV(Bk)が与えられている場合、垂直共線制約抽出手段１３は、Bkに属する各ブロック対（bi，bj）について、yord（bi）＜yord（bj）ならば、「biはbjの下にある」と決定し、
【０１２５】
【数１６】
2006099416.tif 000018
のように順序を確定する。すなわち、垂直共線制約抽出手段１３は、順列P，Mにおけるbiとbjの二項関係を、
【０１２６】
【数１７】
2006099416.tif 000019
と決定し、これを二項関係記憶手段７に保存する。
【０１２７】
（２）部分集合Bkに対してALIGNB(Bk)又はALIGNT(Bk)若しくはALIGNCH(Bk)が与えられている場合、水平共線制約抽出手段１４は、Bkに属する各ブロック対（bi，bj）について、xord（bi）＜xord（bj）ならば、「biはbjの左にある」と決定し、
【０１２８】
【数１８】
2006099416.tif 000020
のように順序を確定する。すなわち、水平共線制約抽出手段１４は、順列P，Mにおけるbiとbjの二項関係を、
【０１２９】
【数１９】
2006099416.tif 000021
と決定し、これを二項関係記憶手段７に保存する。
【０１３０】
〔２−３〕対称制約からの二項関係の抽出（Ｓ１２）
水平対称制約抽出手段１５及び垂直対称制約抽出手段１６は、ブロック配置記憶手段５に記憶されたブロック集合Bの中から、左右方向又は上下方向に対称に並べられた３つのブロック群を抽出し、これを対称制約が課せられるブロックbi，bj，bk（∈B）とする。また、設計者により対称制約が課せられた３つのブロックbi，bj，bk（∈B）が予め指定されている場合には、そのブロックbi，bj，bkを配置制約記憶手段６から読み出す。
【０１３１】
水平対称制約抽出手段１５及び垂直対称制約抽出手段１６による対称制約に基づく二項関係の決定は次のようにして実行される。
【０１３２】
（１）ブロックbi，bj，bk（x（bi）＜x（bj）＜x（bk））に対してSYMMH(bi, bj, bk)が与えられた場合、水平対称制約抽出手段１５は、「biはbkの左にある」と決定し、
【０１３３】
【数２０】
2006099416.tif 000022
のように順序を確定する。すなわち、水平対称制約抽出手段１５は、順列P，Mにおけるbiとbkの二項関係を、
【０１３４】
【数２１】
2006099416.tif 000023
と決定し、これを二項関係記憶手段７に保存する。
【０１３５】
（２）ブロックbi，bj，bk（y（bi）＜y（bj）＜y（bk））に対してSYMMV(bi, bj, bk)が与えられた場合、垂直対称制約抽出手段１６は、「biはbkの下にある」と決定し、
【０１３６】
【数２２】
2006099416.tif 000024
のように順序を確定する。すなわち、垂直対称制約抽出手段１６は、順列P，Mにおけるbiとbkの二項関係を、
【０１３７】
【数２３】
2006099416.tif 000025
と決定し、これを二項関係記憶手段７に保存する。
【０１３８】
〔２−４〕二項関係の推移的確定（Ｓ１３）
二項関係推移決定手段１７は、二項関係記憶手段７に保存されている確定した二項関係から推移的に確定することが可能な二項関係を確定する。これは、例えば次のようにして行われる。
【０１３９】
３つのブロックbi，bj，bkに対して、bi，bj及びbj，bkの順列Pにおける二項関係がpord（bi，bj）＝１ ∧ pord（bj，bk）＝１のように確定していたとする。このとき、bi，bkの順列Pにおける二項関係が推移的に確定し、pord（bi，bk）＝１と決定される。
【０１４０】
同様に、３つのブロックbi，bj，bkに対して、bi，bj及びbj，bkの順列Mにおける二項関係がmord（bi，bj）＝１ ∧ mord（bj，bk）＝１のように確定していたならば、bi，bkの順列Mにおける二項関係はmord（bi，bk）＝１と決定される。
【０１４１】
〔３〕ブロック外形の重なりの除去処理
次に、図２のステップS３におけるブロック外形の重なりの除去処理について説明する。重なり除去処理では、初期値として与えられたブロック配置Φにおいて、Φに含まれるブロックに重なりがある場合、そのブロックの形状を小さく変形することによって、Φのブロック同士の重なりを除去し、重なりのないブロック配置であるパッキングΠを生成する。
【０１４２】
このような重なり除去処理を行う理由は、〔背景技術〕の欄で説明したように、シーケンス・ペアは重なりのないブロック配置（パッキングΠ）に対して、ブロック間の順序づけを行うことにより得られるものであるため、ブロック間の重なりがあると各ブロックの順序づけが不能となるからである。
【０１４３】
図７は、ブロック外形の重なりの除去処理の流れを表すフローチャートである。まず、重なり除去手段１０は、ブロック配置記憶手段５から、検査対象のブロック対bi，bjを選択して読み出す（Ｓ２０）。そして、ブロックbi，bjにブロックの重なりがあるか否かを検査する。ブロックの重なりがある場合には、重なりのあるブロックbi，bjを縮小し、重なりを除去する（Ｓ２２）。一方、重なりがない場合には何もしない。そして、すべてのブロック対についての検査が終わるまで（Ｓ２３）、ステップS２０〜S２２を繰り返す。
【０１４４】
以下、ステップS２２における処理について具体的に説明するが、その前に、ブロックの重なり方については、次のように定義しておく。
【０１４５】
（１）ブロック集合Bに属するブロック対（bi，bj）に対して、次の関係の何れかが成り立つとき、ブロックbiとブロックbjは「角部が重なる」という：
【０１４６】
【数２４】
2006099416.tif 000026
【０１４７】
【数２５】
2006099416.tif 000027
図８（a）は、角部が重なったブロックbi，bjの一例を示している。
【０１４８】
（２）ブロック集合Bに属するブロック対（bi，bj）に対して、次の関係が成り立つとき、ブロックbjはブロックbiに「含まれる」という：
【０１４９】
【数２６】
2006099416.tif 000028
【０１５０】
図８（b）は、ブロックbjがブロックbiに含まれている例を示す。
【０１５１】
（３）ブロック集合Bに属するブロック対（bi，bj）に対して、次の関係が成り立つとき、ブロックbiとブロックbjは「交差する」という：
【０１５２】
【数２７】
2006099416.tif 000029
【０１５３】
〔３−１〕ブロックの角部が重なる場合の重なり除去処理
２つのブロックbi，bjの角部が重なっている場合の重なり除去処理は次のように行われる。まず、ブロックbi，bjの外形の重なりの水平方向の長さをdx、垂直方向の長さをdyとする。図９（a）にdx，dyの具体的な例を示す。
【０１５４】
（１）dx＜dyの場合、ブロックbi，bjの重なりがなくなるように、bi，bjの水平方向の長さを、それぞれdx／２ずつ短くする。例えば、x（bi）＜x（bj）ならば、biの外形の幅をw’（bi）＝w（bi）−dx／２、bjの外形の左下隅のx座標をx’（bj）＝x（bj）＋dx／２、bjの外形の幅をw’（bj）＝w（bj）−dx／２とする。図９（b）に、dx＜dyの場合の重なり除去処理の一例を示す。
【０１５５】
（２）dy＜dxの場合、ブロックbi，bjの重なりがなくなるように、bi，bjの垂直方向の長さを、それぞれdy／２ずつ短くする。例えば、y（bi）＜y（bj）ならば、biの外形の高さをh’（bi）＝h（bi）−dy／２、bjの外形の左下隅のy座標をy’（bj）＝y（bj）＋dy／２、bjの外形の高さをh’（bj）＝h（bj）−dy／２とする。
【０１５６】
〔３−２〕ブロックが包含関係にある場合及び交差する場合の重なり除去処理
２つのブロックbi，bjが包含関係にある場合及び交差する場合の重なり除去処理は次のように行われる。まず、重なり除去手段は、ブロックbi，bjについて次の４つの値を計算する：
【０１５７】
【数２８】
2006099416.tif 000030
【０１５８】
次に、dx１，dx２，dy１，dy２のうち、dx１又はdx２が最小となる場合には、ブロックbi，bjの重なりがなくなるまで、水平方向にbi又はbjの幅を小さくする。例えば、初期配置Φにおいて図１０（a）のようにブロックbi，bjが配置されていたとする。図１０（a）において、min（dx１，dx２，dy１，dy２）＝dx１である。このとき、biの幅はw’（bi）＝max（０，w（bi）−dx１／２）に変更され、bjの幅はw’（bj）＝max（０，w（bj）−dx1／２）に変更される。図１０（b）は図１０（a）のブロックbi，bjに対して重なり除去処理を行った結果を表している。
【０１５９】
尚、初期のブロック配置Φにおいて、図１０（c）に示すようにw（bj）＜dx１／２の場合もあり得る。この場合、w’（bj）＝max（０，w（bj）−dx1／２）＝０となる。このようにブロックbjの幅が０となった場合、そのブロックの位置は、dx１を測る基準となったブロックbiの辺の位置まで移動される。図１０（d）にその様子を示す。
【０１６０】
dy１又はdy２が最小となる場合には、同様に、ブロックbi，bjの重なりがなくなるまで、垂直方向にbi又はbjの高さを小さくする。例えば、min(dx1,dx2,dy1,dy2)=dy1のときは、biの高さはh’（bi）＝max（０，h（bi）−dy１／２）に変更され、bjの高さはh’（bj）＝max（０，h（bj）−dy1／２）に変更される。尚、変更後のブロックの高さが０となる場合の処理も、dx１又はdx２が最小となる場合と同様である。
【０１６１】
〔４〕全順序関係確定処理
最後に、図２のステップS４，S５における全順序関係確定処理について説明する。全順序関係確定処理は、順列Pと順列Mについて独立に行われる。
【０１６２】
〔４−１〕順列Pの全順序確定処理
図１１は、順列Pの全順序確定処理の流れを示すフローチャートである。この処理では、P順序決定手段１８は、順列Pの先頭からブロックの順序を確定していく。ここで、順列Pにおいてブロックbi（∈B）の順序が確定しているか否かを表す変数として、次のように定義される変数fixp（bi）を用いる：
【０１６３】
【数２９】
2006099416.tif 000031
また、以下では、順列Pにおける確定済みのブロック数をNpと記す。
【０１６４】
まず、P順序決定手段１８は、すべての変数fixp（bi）（∀bi∈B）を０に初期化するとともに、Npを０に初期化する（Ｓ３０）。
【０１６５】
次に、現時点でP順序未確定（fixp（bk）＝０）のブロックbkであって、当該bk以外のP順序未確定（fixp（bj）＝０）のすべてのブロックbj（∈B）に対して、二項関係pord（bj，bi）が１ではないブロックbkを抽出する（Ｓ３１）。以下、このようなブロックbkの集合をBs（⊆B）と記す。
【０１６６】
次に、P順序決定手段１８は、ブロック集合Bに属し、P順序未確定（fixp（bj）＝０）であるすべてのブロックbjに対して、x（bi）＋w（bi）≦x（bj）又はy（bi）＞y（bj）＋h（bj）を満たすブロックbiを、集合Bsの中から抽出する（Ｓ３２）。
【０１６７】
そして、抽出されたブロックbiの順序を、順列PのNp＋１番目に確定する（α（bi）＝Np＋１とする）とともに、fixp（bi）を１に設定する（Ｓ３３）。
【０１６８】
以上のステップS３１〜S３３までの処理を、ブロック集合Bに属するすべてのブロックの順列Pにおける順序が確定するまで繰り返す（Ｓ３４）。
【０１６９】
〔４−２〕順列Mの全順序確定処理
M順序決定手段１９による順列Mの全順序確定処理も、順列Pの全順序確定処理と同様に行う。すなわち、この処理でも、M順序決定手段１９は、順列Mの先頭からブロックの順序を確定していく。ここでも、順列Mにおいてブロックbi（∈B）の順序が確定しているか否かを表す変数として、次のように定義される変数fixm（bi）を用いる：
【０１７０】
【数３０】
2006099416.tif 000032
また、順列Mにおける確定済みのブロック数をNmと記す。
【０１７１】
まず、M順序決定手段１９は、すべての変数fixm（bi）（∀bi∈B）を０に初期化するとともに、Nmを０に初期化する。次に、現時点でM順序未確定のブロックbkであって、当該bk以外のM順序未確定のすべてのブロックbj（∈B）に対して、二項関係mord（bj，bi）が１ではないブロックbkを抽出する（このようなブロックbkの集合をBs（⊆B）と記す）。次に、ブロック集合Bに属し、M順序未確定のすべてのブロックbjに対して、x（bi）＋w（bi）≦x（bj）又はy（bi）＞y（bj）＋h（bj）を満たすブロックbiを、集合Bsの中から抽出する。そして、抽出されたブロックbiの順序を、順列MのNm＋１番目に確定する（β（bi）＝Nm＋１とする）とともに、fixm（bi）を１に設定する。
【０１７２】
以上の処理を、ブロック集合Bに属するすべてのブロックの順列Mにおける順序が確定するまで繰り返す。これにより、各種制約に基づく順列P，Mにおける二項関係をすべて満たすシーケンス・ペア（P，M）を作成することができる。
【図面の簡単な説明】
【０１７３】
【図１】本発明の実施例１に係るシーケンス・ペア作成装置の構成を表す図である。
【図２】本発明の実施例１に係るシーケンス・ペア作成装置によるシーケンス・ペアの作成方法の全体の流れを表すフローチャートである。
【図３】離反制約の例を示す図である。
【図４】共線制約の例を示す図である。
【図５】対称制約の例を示す図である。
【図６】二項関係決定手段９による二項関係の抽出処理の手順を示すフローチャートである。
【図７】ブロック外形の重なりの除去処理の流れを表すフローチャートである。
【図８】ブロックの重なりの例を表す図である。
【図９】ブロックの角部が重なる場合の重なり除去処理の例を表す図である。
【図１０】ブロックが包含関係にある場合の重なり除去処理の例を表す図である。
【図１１】順列Pの全順序確定処理の流れを示すフローチャートである。
【図１２】６つのブロックのあるパッキングΠのフロアプランを表したものである。
【図１３】図１２のパッキングΠにおいて、ブロックdに対する右上軌跡、上左軌跡、左下軌跡、及び下右軌跡を表す図である。
【図１４】図１２のパッキングΠに対する正軌跡（a）及び負軌跡（b）を表した図である。
【図１５】（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングである。
【図１６】（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングの（a）水平制約グラフ、及び（b）垂直制約グラフである。
【図１７】最長路計算の結果得られたブロック配置の一例である。
【符号の説明】
【０１７４】
１  シーケンス・ペア作成装置
２  入力部
３  表示部
４  中央演算装置
５  ブロック配置記憶手段
６  配置制約記憶手段
７  二項関係記憶手段
８  シーケンス・ペア記憶手段
９  二項関係決定手段
１０  重なり除去手段
１１  全順序関係決定手段
１２  離反制約抽出手段
１３  垂直共線制約抽出手段
１４  水平共線制約抽出手段
１５  水平対称制約抽出手段
１６  垂直対称制約抽出手段
１７  二項関係推移決定手段
１８  P順序関係決定手段
１９  M順序関係決定手段
【図１】
2006099416.tif 000033
【図２】
2006099416.tif 000034
【図３】
2006099416.tif 000035
【図４】
2006099416.tif 000036
【図５】
2006099416.tif 000037
【図６】
2006099416.tif 000038
【図７】
2006099416.tif 000039
【図８】
2006099416.tif 000040
【図９】
2006099416.tif 000041
【図１０】
2006099416.tif 000042
【図１１】
2006099416.tif 000043
【図１２】
2006099416.tif 000044
【図１３】
2006099416.tif 000045
【図１４】
2006099416.tif 000046
【図１５】
2006099416.tif 000047
【図１６】
2006099416.tif 000048
【図１７】
2006099416.tif 000049