(57)【要約】【課題】部品の近接性や相対位置に関する制約を生成し、それらの制約を満たすことにより回路図に近く、狭領域に配置されるレイアウト作成装置を提供する。【解決手段】回路図データから、当該回路図データに含まれる各部品のブロックをレイアウト平面上に配置するレイアウト作成装置１において、シーケンス・ペア（Ｐ，Ｍ）の生成を行うシーケンス・ペア生成手段４、シーケンス・ペア（Ｐ，Ｍ）により指定された位置関係を満たすように、すべてのブロックｂｉをレイアウト平面上に配置することで、レイアウト・データを生成するブロック配置手段９を備える。シーケンス・ペア生成手段４は、回路図平面上の各部品の座標点の位置関係に基づいて各部品に対応するブロックのシーケンス・ペア（Ｐ，Ｍ）の生成を行う。【選択図】        図１
2006146333.tif 000002
【特許請求の範囲】
【請求項１】
複数の部品、各部品間を接続するネット、並びに各部品及び各ネットの平面上の位置情報を有する回路図データから、当該回路図データに含まれる部品の集合（以下、「部品集合」という。）Cに属する各部品ci（i＝１，…，N）のレイアウトであるブロックbiをレイアウト平面上に配置し、当該回路図データに対応するレイアウト・データを作成するレイアウト作成装置であって、
それぞれが独立なブロックbi（i＝１，…，N）の順列P及びMの対であって、全ての前記ブロックをレイアウト平面上に配置する場合の各ブロックの位置関係を（数１）に従って特定するシーケンス・ペア（P，M）の生成を行うシーケンス・ペア生成手段と、
前記シーケンス・ペア生成手段が生成するシーケンス・ペア（P，M）により指定された位置関係を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することで、レイアウト・データを生成するブロック配置手段と、
を備え、
前記シーケンス・ペア生成手段は、前記回路図データに含まれる各部品ciを回路図平面上において代表点（xsch（ci），ysch（ci））で置き換え、回路図平面上におけるこれらの代表点（xsch（ci），ysch（ci））の位置関係に基づいて各部品ciに対応するブロックbiのシーケンス・ペア（P，M）の生成を行うことを特徴とするレイアウト作成装置。
【数１】
2006146333.tif 000016
【請求項２】
前記シーケンス・ペア生成手段は、
前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、
部品cjの回路図平面上の代表点の座標（以下、「回路図平面上の座標」という。）（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおける前記部品cjに対するブロックbjの順序α（bj）（以下同様に、順列Pにおけるブロックbxの順序をα（bx）と記す。）を前記部品ciに対するブロックbiの順序α（bi）よりも後とし、順列Mにおけるブロックbjの順序β（bj）（以下同様に、順列Mにおけるブロックbxの順序をβ（bx）と記す。）をブロックbiの順序β（bi）よりも後とするとともに、
前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおけるブロックbjの順序α（bj）をブロックbiの順序α（bi）よりも前とし、順列Mにおけるブロックbjの順序β（bj）をブロックbiの順序β（bi）よりも後とするように各順列P，Mについて各ブロックの整列を行うことによりシーケンス・ペア（P，M）の生成を行うこと
を特徴とする請求項１記載のレイアウト作成装置。
【請求項３】
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品ci，cjの回路図平面上の座標（xsch（ci），ysch（ci）），（xsch（cj），ysch（cj））の位置関係に基づいて、前記部品ci，cjに対応するブロックbi，bjのレイアウト平面上における配置制約a（bi，bj）を設定する配置制約設定手段を備え、
前記ブロック配置手段は、前記シーケンス・ペア生成手段が生成するシーケンス・ペア（P，M）により指定された位置関係を満たし、且つ前記配置制約設定手段により設定される配置制約を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することでレイアウト・データを生成すること
を特徴とする請求項１又は２記載のレイアウト作成装置。
【請求項４】
前記配置制約設定手段は、
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における−４５度より大きく４５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＜α（bk）＜α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの下辺又は上辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）を設定する水平共線制約設定手段
を備えていることを特徴とする請求項３記載のレイアウト作成装置。
【請求項５】
前記配置制約設定手段は、
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度より大きく１３５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＞α（bk）＞α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）を設定する垂直共線制約設定手段
を備えていることを特徴とする請求項３記載のレイアウト作成装置。
【請求項６】
前記ブロック配置手段は、
順列M（又はP）の順位に従って、順次ブロックbiを選択する配置ブロック選択手段と、
前記配置ブロック選択手段により選択されたブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合、当該配置制約a（bi，bj）に従って当該ブロックbj又は前記ブロックbiの位置を移動させる配置制約処理手段と、
前記配置制約処理手段により前記ブロックbiについての配置制約がすべて満たされた後に、前記ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、前記ブロックbiに対してシーケンス・ペア（P，M）により（数１）により指定される前記ブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させるブロック配置移動手段と、
を備えていることを特徴とする請求項３乃至５の何れか一に記載のレイアウト作成装置。
【請求項７】
前記配置ブロック選択手段により選択されたブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合において、当該ブロックbjの順列M（又はP）における順位β（bj）（又はα（bj））が、前記ブロックbiの順列M（又はP）における順位β（bi）（又はα（bi））よりも前である場合、前記配置ブロック選択手段が選択するブロックの順列M（又はP）の順位を順位β（bj）（又はα（bj））に戻す選択順位引戻手段と、
前記各配置制約a（bi，bj）に対して、当該配置制約a（bi，bj）が前記配置制約処理手段により参照された回数を計数する制約参照計数手段と、
前記配置制約処理手段により参照された回数が所定の回数に達した配置制約a（bi，bj）を削除する配置制約削除手段と、
を備えていることを特徴とする請求項６記載のレイアウト作成装置。
【請求項８】
前記各配置制約a（bi，bj）により配置制約されるブロック対（bi，bj）間を接続するネットに対して、配置制約の必要性を表す優先順位を設定する優先順位設定手段を備え、
前記配置制約削除手段は、前記配置制約処理手段により参照された回数が所定の回数に達した配置制約a（bi，bj）について、前記優先順位設定手段により設定された優先順位が最も低いものを削除すること
を特徴とする請求項７記載のレイアウト作成装置。
【請求項９】
複数の部品、各部品間を接続するネット、並びに各部品及び各ネットの平面上の位置情報を有する回路図データから、当該回路図データに含まれる部品の集合（以下、「部品集合」という。）Cに属する各部品ci（i＝１，…，N）のレイアウトであるブロックbiをレイアウト平面上に配置し、当該回路図データに対応するレイアウト・データを作成するレイアウト作成方法であって、
それぞれが独立なブロックbi（i＝１，…，N）の順列P及びMの対であって、全ての前記ブロックをレイアウト平面上に配置する場合の各ブロックの位置関係を（数２）に従って特定するシーケンス・ペア（P，M）の生成を行うシーケンス・ペア生成ステップと、
生成された前記シーケンス・ペア（P，M）により指定される位置関係を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することで、レイアウト・データを生成するブロック配置ステップと、
を有しており、
前記シーケンス・ペア生成ステップにおいて、前記回路図データに含まれる各部品ciを回路図平面上において代表点（xsch（ci），ysch（ci））で置き換え、回路図平面上におけるこれらの代表点（xsch（ci），ysch（ci））の位置関係に基づいて各部品ciに対応するブロックbiのシーケンス・ペア（P，M）の生成を行うことを特徴とするレイアウト作成方法。
【数２】
2006146333.tif 000017
【請求項１０】
前記シーケンス・ペア生成ステップにおいて、
前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、
前記部品cjの回路図平面上の代表点の座標（以下、「回路図平面上の座標」という。）（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおける前記部品cjに対するブロックbjの順序α（bj）（以下同様に、順列Pにおけるブロックbxの順序をα（bx）と記す。）を前記部品ciに対するブロックbiの順序α（bi）よりも後とし、順列Mにおけるブロックbjの順序β（bj）（以下同様に、順列Mにおけるブロックbxの順序をβ（bx）と記す。）をブロックbiの順序β（bi）よりも後とするとともに、
前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおけるブロックbjの順序α（bj）をブロックbiの順序α（bi）よりも前とし、順列Mにおけるブロックbjの順序β（bj）をブロックbiの順序β（bi）よりも後とするように各順列P，Mについて各ブロックの整列を行うことによりシーケンス・ペア（P，M）の生成を行うこと
を特徴とする請求項９記載のレイアウト作成方法。
【請求項１１】
前記シーケンス・ペア生成ステップの後に、
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品ci，cjの回路図平面上の座標（xsch（ci），ysch（ci）），（xsch（cj），ysch（cj））の位置関係に基づいて、前記部品ci，cjに対応するブロックbi，bjのレイアウト平面上における配置制約a（bi，bj）を設定する配置制約設定ステップを備え、
前記ブロック配置ステップにおいては、前記シーケンス・ペア生成ステップにおいて生成されるシーケンス・ペア（P，M）により指定された位置関係を満たし、且つ前記配置制約設定ステップにおいて設定される配置制約を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することでレイアウト・データを生成すること
を特徴とする請求項９又は１０記載のレイアウト作成方法。
【請求項１２】
前記配置制約設定ステップにおいて、
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における−４５度より大きく４５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＜α（bk）＜α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの下辺又は上辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）を設定する水平共線制約設定ステップ
を有していることを特徴とする請求項１１記載のレイアウト作成方法。
【請求項１３】
前記配置制約設定ステップにおいて、
ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度より大きく１３５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＞α（bk）＞α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）を設定する垂直共線制約設定ステップ
を有していることを特徴とする請求項１１記載のレイアウト作成方法。
【請求項１４】
前記ブロック配置ステップにおいて、
順列M（又はP）の順位に従って、順次ブロックbiを選択する配置ブロック選択ステップと、
前記配置ブロック選択ステップで選択されるブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合、当該配置制約a（bi，bj）に従って当該ブロックbj又は前記ブロックbiの位置を移動させる配置制約処理ステップと、
前記配置制約処理ステップにおいて前記ブロックbiについての配置制約がすべて満たされた後に、前記ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、前記ブロックbiに対してシーケンス・ペア（P，M）により（数２）により指定される前記ブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させるブロック配置移動ステップと、
を有していることを特徴とする請求項１１乃至１３の何れか一に記載のレイアウト作成方法。
【請求項１５】
前記配置ブロック選択ステップにおいて選択されるブロックbiについて、他のブロックbkとの配置制約a（bi，bj）が設定されている場合において、当該ブロックbjの順列M（又はP）における順位β（bj）（又はα（bj））が、前記ブロックbiの順列M（又はP）における順位β（bi）（又はα（bi））よりも前である場合、前記配置ブロック選択ステップにおいて選択されるブロックの順列M（又はP）の順位を順位β（bj）（又はα（bj））に戻す選択順位引戻ステップと、
前記各配置制約a（bi，bj）に対して、当該配置制約a（bi，bj）が前記配置制約処理ステップにおいて参照された回数を計数する制約参照計数ステップと、
前記配置制約処理ステップにおいて参照された回数が所定の回数に達した配置制約a（bi，bj）を削除する配置制約削除ステップと、
を有していることを特徴とする請求項１４記載のレイアウト作成方法。
【請求項１６】
前記各配置制約a（bi，bj）により配置制約されるブロック対（bi，bj）間を接続するネットに対して、配置制約の必要性を表す優先順位を設定する優先順位設定ステップを有し、
前記配置制約削除ステップにおいては、前記配置制約処理ステップにおいて参照された回数が所定の回数に達した配置制約a（bi，bj）について、前記優先順位設定ステップにおいて設定された優先順位が最も低いものを削除すること
を特徴とする請求項１５記載のレイアウト作成方法。
【請求項１７】
請求項９乃至１６のレイアウト作成方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路のレイアウトの自動作成に使用されるレイアウト作成技術に関し、特に、回路図から得られる各部品の位置関係を反映させたレイアウト配置を得ることが可能なレイアウト作成技術に関する。
【背景技術】
【０００２】
近年の集積回路の大規模化、高集積化に伴い、特にアナログ集積回路の設計は、高性能な集積回路を設計する上でのボトルネックとなりつつある。その理由の一つは、半導体集積回路の設計には、設計自動化ツールが用いられるのが一般化してきているが、アナログ・セルのレイアウトを自動的に設計する設計ツールは、まだ十分なものが開発されてはいないことにある。
【０００３】
集積回路が微細化されると、集積回路を構成する部品や配線のレイアウト上の配置関係が回路全体の電気的特性に与える影響が顕在化する。従って、自動設計ツールを使用してレイアウト設計を行う場合、自動作成されるマスク図版に、レイアウト上の制約を正しく反映させる必要がある。
【０００４】
また、一般に、回路図における各デバイスの配置は、度々、望ましいレイアウト構成を反映していることが多いという事実が知られている。例えば、差動アンプなどは、一般に回路図上ではトランジスタの対が線対称な位置に配置されるが、レイアウト構成においてもこれらのトランジスタは線対称に配置するのが望ましい。従って、回路図から抽出されるデバイスの配置情報をできる限りレイアウト上の部品配置に反映させることが望ましい。
【０００５】
このような回路図上の部品配置を考慮したマスク図版の設計を行うレイアウト作成装置としては、特許文献１又は非特許文献１に記載のものが公知である。図２１に、従来のレイアウト作成装置のシステムブロック図を示す（非特許文献１参照）。特許文献１又は非特許文献１に記載の従来のレイアウト作成装置１０１は、関係記注（relationship annotation）モジュール１０２、デバイス生成（device generation）モジュール１０３、配置（placement）モジュール１０４、及びルーティング（routing）モジュール１０５の４つの主要なモジュールを備えた構成を有する。
【０００６】
まず、設計者は、回路図エディタを用いて回路図（schematic）１０６を作成する。次に、設計者は、関係記注モジュール１０２を用いて、作成した回路図内に部品配置上の制約（関連づけられた部品との配置関係）を記注する。ここで、回路図内の各部品は、整合（matches）、Xの鏡映（mirrors in X）、及びYの鏡映（mirrors in Y）の３つの関係が記注される。
【０００７】
整合とは、同じ配置方位を有し、物理的位置が近接し、同じxy座標を有することを表す配置関係である。Xの鏡映とは、X軸に対して軸対象な配置方位を有し、物理的位置が近接し、同じx座標を有することを表す配置関係である。Yの鏡映とは、Y軸に対して軸対象な配置方位を有し、物理的位置が近接し、同じy座標を有することを表す配置関係である。
【０００８】
各部品は、それが関係づけられた部品にポインタにより記注される。これにより、関係づけられた部品のリストが作成される。図２２は関係づけられた部品のリスト構造の一例を示した図である。各部品に対して、エレメント・フィールド（element field）が用意されている。エレメント・フィールドは、部品名（component）プロパティ、関係（relationship）プロパティ、及び"related_to"プロパティから構成されている。部品名プロパティには、部品名が格納される。関係プロパティには、関連づけられた部品との配置関係、すなわち、「整合」、「Xの鏡映」、又は「Yの鏡映」、若しくは「NULL」の何れかが格納される。"related_to"プロパティには、関係づけられた部品へのポインタが格納される。"related_to"プロパティを持たない部品を「葉節点（leaf node）」という。
【０００９】
葉節点に対しては、固定した配置方位（例えば、０°）が与えられる。葉節点以外の各部品の配置方位は、リスト内の"related_to"プロパティによるリンクを辿って葉節点に到達するまでトラバースすることによって決定される。
【００１０】
例えば、図２２において、Q３の配置方位は０°である。Q２の配置方位は、Q３に対して「Yの鏡映」から算出される。Q４の配置方位は、Q３に対して「Xの鏡映」から算出される。また、Q１の配置方位は、Q３に対して「Yの鏡映」の後「Xの鏡映」から算出される。その結果、Q１〜Q４の部品の配置関係は、例えば、図２３のように決定される。
【００１１】
設計者により記注された部品配置上の制約は、例えば、図２４のように、回路図上にグラフィックスで表示される。すなわち、使用者は、回路図を見ながら、各部品のレイアウト上の配置制約に対する指示を指定することが可能となる。
【００１２】
デバイス生成モジュール１０３は、各部品のエレメント・フィールドの部品名プロパティを参照し、ユーザ定義のマクロ・ルーチンを実行し、各部品に対するマスク図版を生成する。このとき、デバイス生成モジュール１０３は、部品名の参照指示子接頭辞（reference designator prefix）により特定される部品タイプのマクロを選択し実行する。ここで、参照指示子接頭辞とは、例えば、抵抗に対する「R」、トランジスタに対する「Q」のような、部品の種類に対応して与えられる接頭辞をいう。各部品に対するマスク図版の情報は、デバイス原図ライブラリ（device artwork library）１０７に格納される。
【００１３】
次に、配置モジュール１０４は、デバイス原図ライブラリ１０７に保存された図版を使用して、関係記注モジュールに記注された配置関係と、回路図上の各部品の位置関係を考慮しながら、各部品のレイアウト上の配置を決定する。この方法は、回路図位置法（schematic position method）と呼ばれる。
【００１４】
配置モジュール１０４は、まず、配置する部品を、次のようなグラフ表現により、配置グループに分ける：
（１）V＝｛vi｝はオブジェクト（部品）の集合。
（２）Eは有向枝の集合。ここで、viの"related_to"リンクがvjを指すならば、eijは、viからvjへの有向枝とする。
（３）G＝（V，E）は互いに非連結な有向グラフの集合。
これらのグラフを「配置グループ」と呼ぶ。
【００１５】
回路図位置法では、レイアウトにおける部品間の相対位置を、回路図中に描かれている部品間の相対位置と同じにする。これにより、設計者は、物理的なレイアウト配置を考慮しながら回路図を作成することができる。
【００１６】
具体的には、関係づけられた部品の配置グループにおいて、当該配置グループ内の部品dに対して、部品dのレイアウト平面上の目標座標（xt，yt）は次の式により計算される：
【００１７】
【数１】
2006146333.tif 000003
【００１８】
また、各グループがレイアウト配置される前に、各グループ内の部品は、記注された部品間の配置関係の制約を満たすために、他のグループとは独立に（数２）に示されたアルゴリズム１に従って配置される。更に、全ての配置グループをレイアウト内に配置する手順は、（数３）に示されたアルゴリズム２によって実行される：
【００１９】
【数２】
2006146333.tif 000004
【００２０】
【数３】
2006146333.tif 000005
【００２１】
以上のようにして、各部品の配置が行われると、最後にルーティング・モジュール１０５が、シンボリック・ワイヤ法やポリゴン・パス法を使って配線の引き回しを行い、レイアウト設計が完了する。
【特許文献１】米国特許第５，３０３，１６１号明細書
【特許文献２】特開平９−１０８９３４号公報
【非特許文献１】S. W. Mehranfar, "A Technology-Independent Approach to Custom Analog Cell Generation", IEEE Transaction on Solid-State Circuit, Vol.26, No.3, pp.386-393, 1991.
【非特許文献２】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.
【発明の開示】
【発明が解決しようとする課題】
【００２２】
近年では、特に、半導体集積回路の需要が高まり、一層の設計期間の短縮を目的とした自動設計の導入が求められている。一方、自動設計した集積回路の回路性能についても高い品質が要求されている。回路性能の品質は、部品／ブロック配置の品質に依るとことが大きい。
【００２３】
上記従来のレイアウト作成装置では、回路図の配置を反映したレイアウト配置を作成することが可能となるため、回路の設計者は、回路図を作成した時点で、その回路における各部品のレイアウト上の配置関係をレイアウト配置設計に反映させることが可能となる。従って、高性能の半導体集積回路を設計することを容易化するのに役立つ。
【００２４】
しかしながら、上記従来のレイアウト作成装置では、部品及びブロック同士が重なることがないレイアウト配置は得られるが、各ブロックができるだけ小さい領域に配置されるようなレイアウト配置を得ることはできない。従って、作成されるレイアウト配置は、隙間が多く、半導体集積回路の高集積化を図る上で問題がある。
【００２５】
ところで、回路性能の善し悪しを部品／ブロック配置で評価する方法は従来から研究されているが、現在のところ、標準的に利用できる評価関数を定式化するところまでは至っていない。そこで、上述のように、通常は、回路設計者の作成する回路図に近いレイアウト配置が高品質な回路性能を持つという経験則がいわれている。しかしながら、部品／ブロック配置において、回路図と部品／ブロック配置の”近さ”を定量的な評価関数として規定することは、回路性能を定式化することと同様に難しい。
【００２６】
そこで、本発明の目的は、評価関数を用いず、部品／ブロックの近接性や相対位置に関する制約を生成し、それらの制約を満たすことにより回路図に近いレイアウト配置であって、各ブロックができるだけ小さい領域に配置されるようなレイアウト配置の圧縮（コンパクション）が容易な形式の初期配置を与えることが可能なレイアウト作成装置を提供することにある。
【課題を解決するための手段】
【００２７】
本発明に係るレイアウト作成装置の第１の構成は、複数の部品、各部品間を接続するネット、並びに各部品及び各ネットの平面上の位置情報を有する回路図データから、当該回路図データに含まれる部品の集合（以下、「部品集合」という。）Cに属する各部品ci（i＝１，…，N）のレイアウトであるブロックbiをレイアウト平面上に配置し、当該回路図データに対応するレイアウト・データを作成するレイアウト作成装置であって、それぞれが独立なブロックbi（i＝１，…，N）の順列P及びMの対であって、全ての前記ブロックをレイアウト平面上に配置する場合の各ブロックの位置関係を（数４）に従って特定するシーケンス・ペア（P，M）の生成を行うシーケンス・ペア生成手段と、前記シーケンス・ペア生成手段が生成するシーケンス・ペア（P，M）により指定された位置関係を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することで、レイアウト・データを生成するブロック配置手段とを備え、前記シーケンス・ペア生成手段は、前記回路図データに含まれる各部品ciを回路図平面上において代表点（xsch（ci），ysch（ci））で置き換え、回路図平面上におけるこれらの代表点（xsch（ci），ysch（ci））の位置関係に基づいて各部品ciに対応するブロックbiのシーケンス・ペア（P，M）の生成を行うことを特徴とする。
【００２８】
【数４】
2006146333.tif 000006
【００２９】
この構成により、回路図平面における各部品間の位置関係は、シーケンス・ペア生成手段によりシーケンス・ペアとして抽出される。そして、抽出されたシーケンス・ペアを用いて、ブロック配置手段が各部品に対応するブロックをレイアウト平面上に配置する。これにより、回路図から抽出された各部品間の位置関係は、レイアウト平面上の各ブロック間の位置関係に反映される。
【００３０】
また、生成されるシーケンス・ペアを初期配置として、ヒューリスティックな方法（例えば、焼きなまし法（Simulated Annealing method）等）を用いて圧縮（コンパクション）処理を行うことは容易である。従って、各ブロックができるだけ小さい領域に配置されるレイアウト配置の圧縮が容易となる。
【００３１】
尚、シーケンス・ペアに関しては、特許文献２や非特許文献２に記載されているが、後で詳細に説明する。
【００３２】
本発明に係るレイアウト作成装置の第２の構成は、上記第１の構成において、前記シーケンス・ペア生成手段は、前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、部品cjの回路図平面上の代表点の座標（以下、「回路図平面上の座標」という。）（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおける前記部品cjに対するブロックbjの順序α（bj）（以下同様に、順列Pにおけるブロックbxの順序をα（bx）と記す。）を前記部品ciに対するブロックbiの順序α（bi）よりも後とし、順列Mにおけるブロックbjの順序β（bj）（以下同様に、順列Mにおけるブロックbxの順序をβ（bx）と記す。）をブロックbiの順序β（bi）よりも後とするとともに、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおけるブロックbjの順序α（bj）をブロックbiの順序α（bi）よりも前とし、順列Mにおけるブロックbjの順序β（bj）をブロックbiの順序β（bi）よりも後とするように各順列P，Mについて各ブロックの整列を行うことによりシーケンス・ペア（P，M）の生成を行うことを特徴とする。
【００３３】
このように、回路図上の各部品を点と見なし、回路図に対して４５度及び−４５度の傾斜座標軸を基準として各部品の左右関係、上下関係を抽出することにより、回路図から各部品の位置関係をシーケンス・ペアとして抽出することが可能となる。
【００３４】
本発明に係るレイアウト作成装置の第３の構成は、上記第１又は２の構成において、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品ci，cjの回路図平面上の座標（xsch（ci），ysch（ci）），（xsch（cj），ysch（cj））の位置関係に基づいて、前記部品ci，cjに対応するブロックbi，bjのレイアウト平面上における配置制約a（bi，bj）を設定する配置制約設定手段を備え、前記ブロック配置手段は、前記シーケンス・ペア生成手段が生成するシーケンス・ペア（P，M）により指定された位置関係を満たし、且つ前記配置制約設定手段により設定される配置制約を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することでレイアウト・データを生成することを特徴とする。
【００３５】
シーケンス・ペアでは、回路図上における各部品間の相対的な位置関係は抽出されるが、その位置関係は抽象化された位置関係、すなわち、一方の部品を原点とする（P，M）平面において、４５度及び−４５度の傾きを持ったP軸及びM軸により４分割される（P，M）平面のどの象限に他方の部品が存在するかという情報である。従って、回路図に含まれている、例えば、２つの部品を共線上に配置するといった、より具体的な位置関係を表す情報は捨象されている。
【００３６】
そこで、配置制約設定手段が、部品ci，cjの回路図平面上の座標（xsch（ci），ysch（ci）），（xsch（cj），ysch（cj））の位置関係に基づいて、部品ci，cjに対応するブロックbi，bjのレイアウト平面上における配置制約a（bi，bj）を設定することにより、上述のような、シーケンス・ペアで捨象されたより具体的な位置関係が抽出される。そして、ブロック配置手段により、かかる位置関係も反映したレイアウト平面上のブロック配置を生成することが可能となる。
【００３７】
本発明に係るレイアウト作成装置の第４の構成は、上記第３の構成において、前記配置制約設定手段は、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における−４５度より大きく４５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＜α（bk）＜α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの下辺又は上辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）を設定する水平共線制約設定手段を備えていることを特徴とする。
【００３８】
この構成により、水平共線制約設定手段は、２つの部品を水平共線上に配置するといった水平共線制約を、配置制約a（bi，bj）として回路図から抽出する。これにより、回路図に含まれる水平共線制約を、部品のブロックのレイアウト平面上への配置に反映させることが可能となる。
【００３９】
ここで、ブロックの「代表点」とは、そのブロックの位置を代表する点である。代表点は、通常はブロックの重心点とされるが、それに限られるものではない。
【００４０】
本発明に係るレイアウト作成装置の第５の構成は、上記第３の構成において、前記配置制約設定手段は、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度より大きく１３５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＞α（bk）＞α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）を設定する垂直共線制約設定手段を備えていることを特徴とする。
【００４１】
この構成により、垂直共線制約設定手段は、２つの部品を垂直共線上に配置するといった垂直共線制約を、配置制約a（bi，bj）として回路図から抽出する。これにより、回路図に含まれる垂直共線制約を、部品のブロックのレイアウト平面上への配置に反映させることが可能となる。
【００４２】
本発明に係るレイアウト作成装置の第６の構成は、上記第３乃至５の何れか一の構成において、前記ブロック配置手段は、順列M（又はP）の順位に従って、順次ブロックbiを選択する配置ブロック選択手段と、前記配置ブロック選択手段により選択されたブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合、当該配置制約a（bi，bj）に従って当該ブロックbj又は前記ブロックbiの位置を移動させる配置制約処理手段と、前記配置制約処理手段により前記ブロックbiについての配置制約がすべて満たされた後に、前記ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、前記ブロックbiに対してシーケンス・ペア（P，M）により（数４）により指定される前記ブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させるブロック配置移動手段と、を備えていることを特徴とする。
【００４３】
この構成により、シーケンス・ペア（P，M）と、各ブロック間の配置制約a（bi，bj）により、次のようにしてレイアウト平面上のブロック配置が構成される：
まず、初期配置として各ブロックに適当な位置を与えておいて、
（１）配置ブロック選択手段が、順列M（又はP）の順位に従って、ブロックbiを選択する；
（２）ブロックbiに配置制約a（bi，bj）が設定されていれば、配置制約処理手段は、その配置制約a（bi，bj）に従ってブロックbi又はbjを移動させる；
（３）ブロックbiに設定された配置制約a（bi，bj）の全てに対して配置制約処理手段による移動処理が終わった後、ブロック配置移動手段は、ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、ブロックbiに対してシーケンス・ペア（P，M）により（数４）により指定されるブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させる。
【００４４】
この処理によって、配置制約手段は、各ブロック間の配置制約を満たし、シーケンス・ペア（P，M）により指定されるブロック間の配置関係に従ったブロック配置を行うことが可能となる。
【００４５】
本発明に係るレイアウト作成装置の第７の構成は、上記第６の構成において、前記配置ブロック選択手段により選択されたブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合において、当該ブロックbjの順列M（又はP）における順位β（bj）（又はα（bj））が、前記ブロックbiの順列M（又はP）における順位β（bi）（又はα（bi））よりも前である場合、前記配置ブロック選択手段が選択するブロックの順列M（又はP）の順位を順位β（bj）（又はα（bj））に戻す選択順位引戻手段と、前記各配置制約a（bi，bj）に対して、当該配置制約a（bi，bj）が前記配置制約処理手段により参照された回数を計数する制約参照計数手段と、前記配置制約処理手段により参照された回数が所定の回数に達した配置制約a（bi，bj）を削除する配置制約削除手段と、を備えていることを特徴とする。
【００４６】
この構成により、シーケンス・ペア（P，M）と、各ブロック間の配置制約a（bi，bj）により、次のようにしてレイアウト平面上のブロック配置が構成される：
まず、初期配置として各ブロックに適当な位置を与えておいて、
（１）配置ブロック選択手段が、順列M（又はP）の順位に従って、ブロックbiを選択する；
（２）ブロックbiに配置制約a（bi，bj）が設定されていれば、配置制約処理手段は、その配置制約a（bi，bj）に従ってブロックbi又はbjを移動させる。このとき、制約参照計数手段は、各配置制約a（bi，bj）が参照された回数を計数する；
（３）ブロックbiに設定された配置制約a（bi，bj）のうちで、β（bj）＜β（bi）（又はα（bj）＜α（bi））となる配置制約がある場合、選択順位引戻手段が、配置ブロック選択手段のブロック選択順位をβ（bj）（又はα（bj））に引き戻し、（１），（２）の処理を繰り返す。また、参照された回数が所定の回数に達した配置制約が現れた場合、配置制約削除手段はその配置制約を削除する；
（４）ブロックbiに設定された配置制約a（bi，bj）の全てに対して配置制約処理手段による移動処理が終わった後、ブロック配置移動手段は、ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、ブロックbiに対してシーケンス・ペア（P，M）により（数４）により指定されるブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させる。
【００４７】
この処理によって、配置制約手段は、各ブロック間の配置制約を満たし、シーケンス・ペア（P，M）により指定されるブロック間の配置関係に従ったブロック配置を行うことが可能となる。また、回路図から自動抽出された配置制約に矛盾が存在する場合には、矛盾がある一群の配置制約が循環的に参照され続けることとなる。この場合、制約参照計数手段が各配置制約の参照回数を計数し、一定以上参照されると配置制約削除手段がその配置制約を削除することで、自動的に矛盾が解消される。
【００４８】
本発明に係るレイアウト作成装置の第８の構成は、上記第７の構成において、前記各配置制約a（bi，bj）により配置制約されるブロック対（bi，bj）間を接続するネットに対して、配置制約の必要性を表す優先順位を設定する優先順位設定手段を備え、前記配置制約削除手段は、前記配置制約処理手段により参照された回数が所定の回数に達した配置制約a（bi，bj）について、前記優先順位設定手段により設定された優先順位が最も低いものを削除することを特徴とする。
【００４９】
このように、ブロック対（bi，bj）間のネットに優先順位をつけておき、配置制約削除手段が矛盾がある配置制約を削除する際には優先順位が低いネットに対する配置制約を削除することで、より最適化されたレイアウト配置を得ることが可能となる。
【００５０】
ここで、「優先順位」は、そのネットが他の部品の電気的特性に及ぼす影響が大きい順に高い優先順位を与えることが好ましい。例えば、アナログ回路の場合には、ネットを流れる電流のより大きい方が優先順位をより高くし、ネットを流れる信号振幅がより大きい方がより優先順位を高くするといったことが考えられる。また、デジタル回路の場合には、信号遅延の余裕度が小さいネットほどより優先順位を高くするといったことが考えられる。優先順位設定手段が優先順位を設定する方法としては、ユーザにより入力された優先順位を設定する方法や、アナログ回路シミュレータによる直流解析・小信号解析の結果又はデジタル回路シミュレータによるタイミング解析の結果を参照して自動的に優先順位を各ネットに付与する方法等を用いることができる。
【００５１】
本発明に係るレイアウト作成方法の第１の構成は、複数の部品、各部品間を接続するネット、並びに各部品及び各ネットの平面上の位置情報を有する回路図データから、当該回路図データに含まれる部品の集合（以下、「部品集合」という。）Cに属する各部品ci（i＝１，…，N）のレイアウトであるブロックbiをレイアウト平面上に配置し、当該回路図データに対応するレイアウト・データを作成するレイアウト作成方法であって、それぞれが独立なブロックbi（i＝１，…，N）の順列P及びMの対であって、全ての前記ブロックをレイアウト平面上に配置する場合の各ブロックの位置関係を（数５）に従って特定するシーケンス・ペア（P，M）の生成を行うシーケンス・ペア生成ステップと、生成された前記シーケンス・ペア（P，M）により指定される位置関係を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することで、レイアウト・データを生成するブロック配置ステップと、を有しており、前記シーケンス・ペア生成ステップにおいて、前記回路図データに含まれる各部品ciを回路図平面上において代表点（xsch（ci），ysch（ci））で置き換え、回路図平面上におけるこれらの代表点（xsch（ci），ysch（ci））の位置関係に基づいて各部品ciに対応するブロックbiのシーケンス・ペア（P，M）の生成を行うことを特徴とする。
【００５２】
【数５】
2006146333.tif 000007
【００５３】
本発明に係るレイアウト作成方法の第２の構成は、上記第１の構成において、前記シーケンス・ペア生成ステップにおいて、前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の代表点の座標（以下、「回路図平面上の座標」という。）（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおける前記部品cjに対するブロックbjの順序α（bj）（以下同様に、順列Pにおけるブロックbxの順序をα（bx）と記す。）を前記部品ciに対するブロックbiの順序α（bi）よりも後とし、順列Mにおけるブロックbjの順序β（bj）（以下同様に、順列Mにおけるブロックbxの順序をβ（bx）と記す。）をブロックbiの順序β（bi）よりも後とするとともに、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度及び−４５度の勾配を持つ２本の半直線に挟まれる領域内に属する場合、順列Pにおけるブロックbjの順序α（bj）をブロックbiの順序α（bi）よりも前とし、順列Mにおけるブロックbjの順序β（bj）をブロックbiの順序β（bi）よりも後とするように各順列P，Mについて各ブロックの整列を行うことによりシーケンス・ペア（P，M）の生成を行うことを特徴とする。
【００５４】
本発明に係るレイアウト作成方法の第３の構成は、上記第１又は２の構成において、前記シーケンス・ペア生成ステップの後に、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品ci，cjの回路図平面上の座標（xsch（ci），ysch（ci）），（xsch（cj），ysch（cj））の位置関係に基づいて、前記部品ci，cjに対応するブロックbi，bjのレイアウト平面上における配置制約a（bi，bj）を設定する配置制約設定ステップを備え、前記ブロック配置ステップにおいては、前記シーケンス・ペア生成ステップにおいて生成されるシーケンス・ペア（P，M）により指定された位置関係を満たし、且つ前記配置制約設定ステップにおいて設定される配置制約を満たすように、すべてのブロックbi（i＝１，…，N）をレイアウト平面上に配置することでレイアウト・データを生成することを特徴とする。
【００５５】
本発明に係るレイアウト作成方法の第４の構成は、上記第３の構成において、前記配置制約設定ステップにおいて、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の右側半平面における−４５度より大きく４５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＜α（bk）＜α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの下辺又は上辺若しくは代表点を水平直線上に揃える配置制約（以下、「水平共線制約（horizontal collinear constraint）」という。）を設定する水平共線制約設定ステップを有していることを特徴とする。
【００５６】
本発明に係るレイアウト作成方法の第５の構成は、上記第３の構成において、前記配置制約設定ステップにおいて、ネットで接続された前記部品集合Cに属する任意の２つの部品ci，cj（∈C）について、前記部品cjの回路図平面上の座標（xsch（cj），ysch（cj））が、前記部品ciの回路図平面上の座標（xsch（ci），ysch（ci））の上側半平面における４５度より大きく１３５度未満の所定の角度の正負の勾配を持つ２本の半直線に挟まれる領域内に属し、且つ、順列Pにおけるブロックbi，bjの順序α（bi），α（bj）及び順列Mにおけるブロックbi，bjの順序β（bi），β（bj）に対してα（bi）＞α（bk）＞α（bj）且つβ（bi）＜β（bk）＜β（bj）となるブロックbkが存在しない場合、ブロックbiとブロックbjの左辺又は右辺若しくは代表点を垂直直線上に揃える配置制約（以下、「垂直共線制約（vertical collinear constraint）」という。）を設定する垂直共線制約設定ステップを有していることを特徴とする。
【００５７】
本発明に係るレイアウト作成方法の第６の構成は、上記第３乃至５の何れか一の構成において、前記ブロック配置ステップにおいて、順列M（又はP）の順位に従って、順次ブロックbiを選択する配置ブロック選択ステップと、前記配置ブロック選択ステップで選択されるブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合、当該配置制約a（bi，bj）に従って当該ブロックbj又は前記ブロックbiの位置を移動させる配置制約処理ステップと、前記配置制約処理ステップにおいて前記ブロックbiについての配置制約がすべて満たされた後に、前記ブロックbiよりも順列M（又はP）の順位が後である全てのブロックについて、前記ブロックbiに対してシーケンス・ペア（P，M）により（数５）により指定される前記ブロックbiに対する位置関係が満たされるようにその位置又は前記ブロックbiの位置を移動させるブロック配置移動ステップと、を有していることを特徴とする。
【００５８】
本発明に係るレイアウト作成方法の第７の構成は、上記第６の構成において、前記配置ブロック選択ステップにおいて選択されるブロックbiについて、他のブロックbjとの配置制約a（bi，bj）が設定されている場合において、当該ブロックbjの順列M（又はP）における順位β（bj）（又はα（bj））が、前記ブロックbiの順列M（又はP）における順位β（bi）（又はα（bi））よりも前である場合、前記配置ブロック選択ステップにおいて選択されるブロックの順列M（又はP）の順位を順位β（bj）（又はα（bj））に戻す選択順位引戻ステップと、前記各配置制約a（bi，bj）に対して、当該配置制約a（bi，bj）が前記配置制約処理ステップにおいて参照された回数を計数する制約参照計数ステップと、前記配置制約処理ステップにおいて参照された回数が所定の回数に達した配置制約a（bi，bj）を削除する配置制約削除ステップと、を有していることを特徴とする。
【００５９】
本発明に係るレイアウト作成方法の第８の構成は、上記第７の構成において、前記各配置制約a（bi，bj）により配置制約されるブロック対（bi，bj）間を接続するネットに対して、配置制約の必要性を表す優先順位を設定する優先順位設定ステップを有し、前記配置制約削除ステップにおいては、前記配置制約処理ステップにおいて参照された回数が所定の回数に達した配置制約a（bi，bj）について、前記優先順位設定ステップにおいて設定された優先順位が最も低いものを削除することを特徴とする。
【００６０】
本発明に係るプログラムは、上記第１乃至８の何れか一のレイアウト作成方法をコンピュータに実行させることを特徴としている。
【発明の効果】
【００６１】
以上のように、本発明によれば、回路図平面における各部品間の位置関係は、シーケンス・ペア生成手段によりシーケンス・ペアとして抽出され、このシーケンス・ペアを用いて、ブロック配置手段が各部品に対応するブロックをレイアウト平面上に配置する。これにより、回路図から抽出された各部品間の位置関係は、レイアウト平面上の各ブロック間の位置関係に反映される。これにより、回路図に近いレイアウト配置を得ることができる。
【００６２】
また、生成されるシーケンス・ペアを初期配置として、焼きなまし法等のヒューリスティックな方法を用いて圧縮処理を行うことは容易である。すなわち、各ブロックができるだけ小さい領域に配置されるようなレイアウト配置の圧縮が容易な形式の初期配置を与えることが可能となる。
【発明を実施するための最良の形態】
【００６３】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００６４】
図１は、本発明の実施例１に係るレイアウト作成装置の構成を表すブロック図である。レイアウト作成装置１は、回路図データ記憶手段２、部品レイアウト・ライブラリ３、シーケンス・ペア生成手段４、シーケンス・ペア記憶手段５、配置制約設定手段６、配置制約記憶手段７、優先順位決定手段８、ブロック配置手段９、ブロック配置記憶手段１０、及びシーケンス・ペア圧縮処理手段１１を備えている。
【００６５】
ユーザにより入力される回路図データ２０は、回路図データ記憶手段２に一時的に保存される。ここで、回路図データ２０には、複数の部品、各部品間を接続するネット、並びに各部品及び各ネットの回路図平面上の位置情報が含まれている。
【００６６】
部品レイアウト・ライブラリ３には、ユーザにより入力される各部品のレイアウト・データが含まれている。一般に部品レイアウト・データは、複数のレイヤにわたる複雑な形状であるが、レイアウト作成装置１は、これらの部品レイアウト・データを矩形で近似する。そして、部品レイアウト・ライブラリ３には、矩形近似された各ブロックの高さ及び幅が保存されている。
【００６７】
シーケンス・ペア生成手段４は、回路図データ記憶手段２に記憶された回路図データ２０に基づき、シーケンス・ペア（P，M）を作成する。作成されたシーケンス・ペア（P，M）は、シーケンス・ペア記憶手段５に保存される。
配置制約設定手段６は、シーケンス・ペア記憶手段５に保存されているシーケンス・ペア（P，M）を参照して、回路図データ記憶手段２に記憶されている回路図データから、各部品間の配置制約を抽出する。本実施例においては、配置制約設定手段６は、水平共線制約設定手段１２及び垂直共線制約設定手段１３を備えている。水平共線制約設定手段１２は、回路図データ２０から水平共線制約を抽出する。垂直共線制約設定手段１３は、回路図データ２０から垂直共線制約を抽出する。抽出された各種配置制約は、配置制約記憶手段７に保存される。
【００６８】
優先順位決定手段８は、配置制約記憶手段７に保存された各配置制約によって関係づけられるブロック対を接続するネットに対して、優先順位を設定する。このとき、優先順位決定手段８は、アナログ回路シミュレータ２２により回路図データ２０に基づき直流解析，小信号解析により得られる各ネットの電流値，小信号振幅等、又はデジタル回路シミュレータ２３により得られる各ネットの遅延の余裕度に基づいて、各ネットの優先順位を決定する。
【００６９】
ブロック配置手段９は、シーケンス・ペア記憶手段５に記憶されたシーケンス・ペア（P，M）及び配置制約記憶手段７に記憶された各部品間の配置制約、並びに部品レイアウト・ライブラリ３に記憶された各部品の幅及び高さの情報に基づき、各ブロックをレイアウト平面上に配置する。そして、得られた各ブロックのレイアウト配置は、初期配置としてブロック配置記憶手段１０に保存される。
【００７０】
ブロック配置手段９は、配置ブロック選択手段１４、配置制約処理手段１５、制約参照計数手段１６、選択順位引戻手段１７、配置制約削除手段１８、及びブロック配置移動手段１９を備えている。
【００７１】
配置ブロック選択手段１４は、順列Mの順位に従って、順次ブロックbiを選択する。配置制約処理手段１５は、選択されたブロックbiについて、他のブロックbjとの間の配置制約a（bi，bj）が設定されている場合には、当該配置制約a（bi，bj）に従ってブロックbi又はbjを移動させる処理を行う。制約参照計数手段１６は、配置制約処理手段１５によって各配置制約が参照された回数を計数する。選択順位引戻手段１７は、選択されたブロックbiに対して、当該ブロックbiと配置制約a（bi，bj）が設定されているブロックbjであって、順列Mにおける順位β（bj）がブロックbiの順位β（bi）よりも前のものがあった場合に、次に配置ブロック選択手段１４が参照するブロックの順列Mの順位をβ（bj）に再設定する処理を行う。配置制約削除手段１８は、各配置制約が参照された回数が所定の回数を超えた場合、それらの配置制約のうち、その配置制約に対応するネットの優先順位が最も低いものを削除する処理を行う。
【００７２】
ブロック配置移動手段１９は、選択されたブロックbiについて、配置制約処理手段１５により配置制約が全て満たされた場合に、順列Mにおける順位が後である全てのブロックについて、ブロックbiに対してシーケンス・ペアにより指定される位置関係が満たされるように、レイアウト平面上での位置を移動する処理を行う。
【００７３】
シーケンス・ペア圧縮処理手段１１は、ブロック配置記憶手段１０に保存されている各ブロックのレイアウト配置（初期配置）に基づいて、シーケンス・ペア法に基づく圧縮処理を行う。圧縮処理された各ブロックのレイアウト配置は、再びブロック配置記憶手段１０に保存され、ブロック配置レイアウト・データ２４として出力される。
【００７４】
尚、これらレイアウト作成装置１の各構成は、実際には、コンピュータにプログラムをロードして実行することによって、機能モジュールとして実現される。
【００７５】
以上のように構成された本実施例に係るレイアウト作成装置１について、以下その動作を説明する。説明の順序としては、まず、ここで使用する用語の定義を行い、次に、シーケンス・ペア法の概略について説明し、その後動作の詳細及び具体例を述べる。
【００７６】
〔１〕用語の定義
〔定義１〕（回路）
部品（ランドを含む。）をci（iは部品を特定する添字。）と記し、部品の集合（以下、「部品集合（set of component）」という。）をC＝｛c１，c２，…，cN｝と記す。Nは部品の総数である。部品集合Cの部分集合Ck（⊆C）に属する各部品間を接続する接続線を「ネット（net）」といい、nk＝n（Ck）（kはネットを特定する添字。）と記す。特に、部品ciとcjとの間を接続するネットをn（ci，cj）と記す。ネットの集合（以下、「ネット集合（set of nets）」という。）をNET＝｛n１，n２，…，nNnet｝と記す。Nnetはネットの総数である。部品集合C及びネット集合NETの組（C，NET）を「回路（circuit）」といい、K＝（C，NET）と記す。  （定義終り）
【００７７】
〔定義２〕（回路図平面）
回路Kを構成する部品及びネットを、図形記号により２次元平面上に表した図面を「回路図（schematic）」という。回路図が表された平面を「回路図平面」といい、SCHと記す。回路図平面SCHにおける部品ci（∈C）の座標を（xsch（ci），ysch（ci））と記す。  （定義終り）
【００７８】
〔定義３〕（ネットリスト）
ある回路Kにおいて、回路Kの部品間の接続状態を表現したデータを「ネットリスト（net list）」といい、NLと記す。  （定義終り）
【００７９】
〔定義４〕（ブロック集合）
ある回路Kにおける各部品ciのレイアウトを矩形で表現したものを「ブロック（block）」といい、biと記す。N個のブロックbi（i＝１，…，N）を考える。ブロックbiの集合を「ブロック集合（set of block）」といい、B＝｛b１，b２，…，bN｝と記す。ブロックbiの幅及び高さを、それぞれw（bi），h（bi）と記す。ブロック集合Bは部品集合Cに一対一対応する。すなわち、ブロック集合Bに属するブロックbiは、部品集合Cに属する部品ciに対応する。  （定義終り）
【００８０】
〔定義５〕（レイアウト平面）
ブロックが配置される平面を「レイアウト平面」という。レイアウト平面上におけるブロックbiの左下隅座標をそのブロックbiの「位置座標」といい、（x（bi），y（bi））と記す。  （定義終り）
【００８１】
〔定義６〕（左右（水平）順序）
ブロック集合Bに属する任意の２つのブロックbi，bjの対（bi，bj）について、関係x（bi）＋w（bi）≦x（bj）が成り立つとき、ブロックbiはブロックbjの「左にある（"left to"）」（又は、ブロックbjはブロックbiの「右にある（"right to"）」）という。  （定義終り）
【００８２】
〔定義７〕（上下（垂直）順序）
ブロック集合Bに属する任意の２つのブロックbi，bjの対（bi，bj）について、関係y（bi）＋h（bi）≦y（bj）が成り立つとき、ブロックbiはブロックbjの「下にある（"below"）」（又は、ブロックbjはブロックbiの「上にある（"above"）」）という。  （定義終り）
【００８３】
〔定義８〕（シーケンス・ペア）
N個のブロックを元とするブロック集合B＝｛b１，b２，…，bN｝が与えられたとする。ブロック集合Bの全ての元の順列である２つの順列をP＝（p１，p２，…，pN）（∀pi∈B）及びM＝（m１，m２，…，mN）（∀mi∈B）と記す。このとき、２つの順列P，Mの対（P，M）を「シーケンス・ペア（sequence pair）」という。  
（定義終り）
【００８４】
〔定義９〕（ブロック配置のシーケンス・ペア）
ブロックbi（∈B）の順列Pにおける順序をα（bi）、ブロックbiの順列Mにおける順序をβ（bi）と記す。pα（bi）＝bi，mβ（bi）＝biである。あるブロック配置において、順列P，Mが次の条件を満たしている場合、このシーケンス・ペア（P，M）を、この「ブロック配置のシーケンス・ペア」という：
【００８５】
【数６】
2006146333.tif 000008
（定義終り）
【００８６】
〔定義１０〕（共線制約）
ブロック集合Bの或る部分集合Bk（Bk⊆B）に対して、当該部分集合Bk内の全てのブロックbi（∈Bk）について、上下左右の何れかの辺又は代表点を垂直又は水平直線上に揃えるという制約を「共線制約（collinear(align) constraint）」という。
（１）部分集合Bk内の全てのブロックbi（∈Bk）について、左辺を揃えるようにブロックを配置する共線制約をALIGNL（Bk）と記す。
（２）部分集合Bk内の全てのブロックbi（∈Bk）について、下辺を揃えるようにブロックを配置する共線制約をALIGNB（Bk）と記す。
（３）部分集合Bk内の全てのブロックbi（∈Bk）について、右辺を揃えるようにブロックを配置する共線制約をALIGNR（Bk）と記す。
（４）部分集合Bk内の全てのブロックbi（∈Bk）について、上辺を揃えるようにブロックを配置する共線制約をALIGNT（Bk）と記す。
（５）部分集合Bk内の全てのブロックbi（∈Bk）について、代表点を水平直線上に揃えるようにブロックを配置する共線制約をALIGNCH（Bk）と記す。
（６）部分集合Bk内の全てのブロックbi（∈Bk）について、代表点を垂直直線上に揃えるようにブロックを配置する共線制約をALIGNCV（Bk）と記す。
（定義終り）
【００８７】
尚、以下の説明においては、ALIGNCH（Bk）及びALIGNCV（Bk）における代表点は、ブロックの重心点であるとする。
【００８８】
〔２〕シーケンス・ペア法
次に、シーケンス・ペア法による圧縮処理について説明する。シーケンス・ペア法による圧縮処理は、特許文献２及び非特許文献２等において既に公知であるため、ここでは、その概要を簡単に述べる。
【００８９】
シーケンス・ペア法による圧縮処理は、与えられた初期のシーケンス・ペアに基づき、焼きなまし法のようなヒューリスティックな方法で（P，M）解空間の探索を行うことにより最適なパッキングΠを見つけ出すことによって行われる。ここで、ブロック集合Bの「パッキング（packing）」とは、各ブロックの重なりのない配置をいう。
【００９０】
この際、シーケンス・ペアの並べ替えにより得られる各パッキングの評価を行う場合、シーケンス・ペアからパッキングを生成する必要がある。そこで、シーケンス・ペアからパッキングを生成する方法について概説する。
【００９１】
まず、シーケンス・ペア（P，M）が与えられた場合、ブロック集合Bに属する任意のブロックbi（∈B）に対して、以下の４つのBの部分集合Maa（bi），Mbb（bi），Mba（bi），Mab（bi）が固有に定まる：
【００９２】
【数７】
2006146333.tif 000009
【００９３】
これらの部分集合Maa（bi），Mbb（bi），Mba（bi），Mab（bi）に対して、次のような幾何学的制約が導かれる：
【００９４】
（１）『任意の２つのブロックbi，bj（∈B）に対して、bj∈Maa（bi）ならば、Πにおいてbjはbiの右、bj∈Mbb（bi）ならば、bjはbiの左になければならない。』
【００９５】
（２）『任意の２つのブロックbi，bj（∈B）に対して、bj∈Mab（bi）ならば、bjはbiの下、bj∈Mba（bi）ならば、bjはbiの上になければならない。』
かかる幾何学的制約を満たすΠを（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）を次のように定義する：
【００９８】
【数８】
2006146333.tif 000010
【００９９】
ここで、V，V１，V２は節点の集合、E，E１，E２は枝の集合である。s，tは、それぞれ、涌出点（source）及び吸収点（sink）を表し、iはそれ以外の水平制約グラフGHの節点を表す。ш(x)は節点xの重みを表す。w(bk)はブロックbkの幅を表す。
【０１００】
垂直制約グラフGVは、幾何学的制約（２）の上下の位置関係と各ブロックbi（∈B）の高さh(bi)に基づいて同様に定義する。図３は（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングの（a）水平制約グラフ、及び（b）垂直制約グラフである。何れのグラフも有向閉路を含まない。また、各ブロックの対（bi，bj）に対して、GH又はGVの何れか一方に辺が存在し、両方に辺が存在することはない。従って、各ブロックのx座標とy座標は、配置の制約を満たしつつ独立に決定することができ、その結果、重なりのないブロック配置が得られる。各モジュールbi（∈B）のx座標及びy座標は、それぞれ、グラフGH，GV内の涌出点sと節点iとの間の最長路（路上の節点の重みの和が最大の路）における節点i以外の節点の重みの和として決定される。同様に、チップの高さと幅は、それぞれ、グラフGH，GV内の涌出点sと吸収点tとの間の最長路における節点の重みの和として決定される。チップの幅と高さとは独立に最小化することができ、その結果得られるパッキングは(P，M)-optimalである。図４は最長路計算の結果得られたブロック配置の一例を示している。
【０１０１】
〔３〕レイアウト作成装置１の動作の詳細
〔３−１〕処理全体の流れ
図５は、実施例１に係るレイアウト作成装置１によるレイアウト作成方法の全体の流れを表すフローチャートである。
【０１０２】
まず、ユーザは、回路図データ２０（ネットリストNLを含む。）及び部品レイアウト・データ２１を入力し、回路図データ記憶手段２，部品レイアウト・ライブラリ３に保存する（S１）。回路図データ２０には、ブロック集合B、ネットリストNL、及び、各部品と各ネットの回路図平面上の配置情報が含まれている。部品レイアウト・データ２１には、部品集合Bに属する各部品biの幅w（bi）及び高さh（bi）が含まれている。
【０１０３】
次に、シーケンス・ペア生成手段４は、回路図データ記憶手段２に保存されている回路図からシーケンス・ペア（P，M）を生成し、シーケンス・ペア記憶手段５に保存するシーケンス・ペアの抽出処理を行う（S２）。次に、配置制約設定手段６は、シーケンス・ペア記憶手段５に保存されたシーケンス・ペアを参照して、回路図データ記憶手段２に保存されている回路図から共線制約の抽出処理を行う（S３）。次に、優先順位決定手段８は、回路図に含まれる各ネットに対して、優先順位の作成処理を行う（S４）。
【０１０４】
次に、ブロック配置手段９は、シーケンス・ペア記憶手段５に保存されたシーケンス・ペア、並びに配置制約記憶手段７に記憶された配置制約及び各ネットの優先順位に基づいて、冗長な共線制約の削除と配置圧縮処理を行う（S５）。これにより得られるレイアウト平面上のブロック配置は、初期配置としてブロック配置記憶手段１０に保存される。
【０１０５】
次に、シーケンス・ペア圧縮処理手段１１は、上述したシーケンス・ペア法を用いて、ブロック配置記憶手段１０に保存されているレイアウト平面上のブロックの初期配置に対しブロック配置の圧縮処理を行う（S６）。これにより圧縮されたブロック配置は、初期配置としてブロック配置記憶手段１０に保存される。最後に、ブロック配置記憶手段１０に保存された圧縮されたブロック配置が出力される（S７）。
【０１０６】
以下、上記レイアウト作成方法における重要な処理について詳細に説明する。
【０１０７】
〔３−２〕シーケンス・ペアの抽出処理
まず、シーケンス・ペア生成手段４は、ブロック集合Bに属するすべてのブロックbi（∈B）の順列P，Mの初期値を適当に与える。
【０１０８】
次に、シーケンス・ペア生成手段４は、部品集合Cに属する各部品ci（∈C）について、回路図平面SCH上における代表点の座標（xsch（ci），ysch（ci））を抽出する。例えば、回路図データ記憶手段２に格納されている回路図が図６のような回路図であったとする。まず、各部品を代表点で置きかえると図７のようになる。図７においては、「●」で示された点が各部品の代表点を表し、各代表点間を接続する線分はネットを表している。
【０１０９】
最後に、シーケンス・ペア生成手段４は、抽出した部品の座標（xsch（ci），ysch（ci））に基づいて、以下のような条件下でブロックbi（∈B）の順列P，Mの整列を行うことによって、シーケンス・ペアP，Mを作成する：
【０１１０】
【数９】
2006146333.tif 000011
【０１１１】
この処理を、図６の回路図を例にとって具体的に説明すれば次のようになる。例えば、部品Q３について考える。部品Q３について、（数９）の条件１を満たす部品は、回路図平面上の部品Q３の位置に対して右側半平面における４５°及び−４５°の勾配を持つ２本の半直線に挟まれた領域内にある部品である。すなわち、図８において斜線で示された領域内にある部品（R１，C１，LO＿I１，LO＿I２，OUT１，OUT２，及びL＿I）である。従って、これらの部品の順列Pにおける順位は、部品Q３の順位よりも後となる。また、これらの部品の順列Mにおける順位は、部品Q３の順位よりも後となる。
【０１１２】
一方、部品Q３について、（数９）の条件２を満たす部品は、回路図平面上の部品Q３の位置に対して上側半平面における４５°及び−４５°の勾配を持つ２本の半直線に挟まれた領域内にある部品である。すなわち、図９において斜線で示された領域内にある部品（R１，R２，Q１，Q２，Q５，及びVCC）である。従って、これらの部品の順列Pにおける順位は、部品Q３の順位よりも前となる。また、これらの部品の順列Mにおける順位は、部品Q３の順位よりも後となる。
【０１１３】
順列P，Mの整列は、通常のソート・アルゴリズムを使用して実行される。これにより、回路図における各部品ci（∈C）の位置関係はシーケンス・ペア（P，M）に取り込まれる。
【０１１４】
〔３−３〕共線制約の抽出処理
まず、配置制約設定手段６には、所定の角度パラメータθ（０°＜θ＜４５°）の値が与えられる。θの値は固定値としてもよいが、ユーザにより変更可能な値としてもよい。通常はθ＝５°〜１０°程度に設定することが好ましい。
【０１１５】
次に、水平共線制約設定手段１２は、部品集合Cに属する各部品の対（ci，cj）について、次の条件１〜３が満たされているか否かを判定する：
【０１１６】
【数１０】
2006146333.tif 000012
【０１１７】
部品の対（ci，cj）が上記条件１〜３を満たす場合には、ALIGNB（bi，bj）を設定し、配置制約記憶手段７に保存する。
【０１１８】
また、垂直共線制約設定手段１３は、部品集合Cに属する各部品の対（ci，cj）について、上記条件１，２及び次の条件４が満たされているか否かを判定する：
【０１１９】
【数１１】
2006146333.tif 000013
【０１２０】
部品の対（ci，cj）が上記条件１，２，４を満たす場合には、ALIGNL（bi，bj）を設定し、配置制約記憶手段７に保存する。
【０１２１】
この処理の意味を図６の回路図を例にとって具体的に説明する。例えば、図６の部品Q１０に着目した場合、部品Q１０に対して上記条件３を満たす部品は、回路図平面上の部品Q１０の位置に対して右側半平面におけるθ及び−θの勾配を持つ２本の半直線に挟まれた領域内にある部品である。すなわち、図１０に示したように、部品Q７及び部品OUT２がこの条件を満たす。更に、条件１，２を課した場合、部品Q１０に対して全ての条件を満たす部品はQ７であることが分かる。従って、ALIGNB（Q１０，Q７）が設定される。
【０１２２】
同様に、部品Q１０に対して上記条件４を満たす部品は、回路図平面上の部品Q１０の位置に対して右側半平面におけるθ及び−θの勾配を持つ２本の半直線に挟まれた領域内にある部品である。すなわち、図１０に示したように、部品R２，Q６，Q９がこの条件を満たす。更に、条件１，２を課した場合、部品Q１０に対して全ての条件を満たす部品はQ９であることが分かる。従って、ALIGNL（Q10，Q9）が設定される。
【０１２３】
このようにして、回路図における部品の共線位置関係が、ALIGNB（bi，bj）及びALIGNL（bi，bk）として抽出される。尚、ALIGNB（bi，bj）及びALIGNL（bi，bk）の代わりにALIGNT（bi，bj），ALIGNCH（bi，bj）及びALIGNR（bi，bk），ALIGNCV（bi，bj）を用いてもよい。
【０１２４】
〔３−４〕優先順位の作成処理
優先順位は、各部品間を接続するネットについて設定される。図１１は、アナログ回路における共線制約の優先順位の決定方法の一例を表すフローチャートである。
【０１２５】
まず、前提条件として、回路図データ２０に基づいて、アナログ回路シミュレータ２２によりこの回路の直流解析、及び小信号解析が既に実施されており、各ネットの電流値及び小信号振幅の値が算出されているものとする。
【０１２６】
優先順位決定手段８は、まず、各共線制約ak=ALIGNχ(bi, bj)について、akに対するネットnk(bi, bj)の電流値の大きい順に整列する（S１１）。ここで、χはB,T,CH,L,R,CVの何れかを表す。次に、優先順位決定手段８は、各共線制約akのうち、akに対するネットnk(bi, bj)の電流値が同じものについては、ネットnk(bi, bj)の小信号振幅が大きい順に整列する（S１２）。次に、優先順位決定手段８は、各共線制約akのうち、akに対するネットnk(bi, bj)の電流値及び小信号振幅が同じものについては、bi, bjの位置の共線制約からの外れ距離が小さい順に整列する（S１３）。最後に、優先順位決定手段８は、上記ステップS１１〜S１３で整列された順番に、共線制約akの優先順位を付与する（S１４）。これらの優先順位は、共線制約akとともに配置制約記憶手段７に保存される。
【０１２７】
また、図１２は、デジタル回路における共線制約の優先順位の決定方法の一例を表すフローチャートである。
【０１２８】
まず、前提条件として、回路図データ２０に基づいて、デジタル回路シミュレータ２３によりこの回路のタイミング解析が既に実施されており、各ネットの遅延の余裕度の値が算出されているものとする。
【０１２９】
優先順位決定手段８は、まず、各共線制約ak=ALIGNχ(bi, bj)について、akに対するネットnk(bi, bj)の遅延の余裕度の大きい順に整列する（S２１）。ここで、χはB,T,CH,L,R,CVの何れかを表す。次に、優先順位決定手段８は、各共線制約akのうち、akに対するネットnk(bi, bj)の遅延の余裕度が同じものについては、bi, bjの位置の共線制約からの外れ距離が小さい順に整列する（S２２）。最後に、優先順位決定手段８は、上記ステップS２１，S２２で整列された順番に、共線制約akの優先順位を付与する（S２３）。これらの優先順位は、共線制約akとともに配置制約記憶手段７に保存される。
【０１３０】
〔３−５〕冗長な共線制約の削除と配置圧縮処理
〔３−５−１〕全体の処理の流れ
図１３は、ブロック配置手段９による冗長な共線制約の削除と配置圧縮処理の全体の流れを表すフローチャートである。まず、ブロック配置手段９は、後述する配置圧縮処理を実行する（S３１）。配置圧縮処理の結果、冗長な共線制約akがあると、当該共線制約akを含む一群の共線制約｛ak｝が何度も（無限循環的に）参照されるため、それら共線制約ak（∈｛ak｝）の参照回数c（ak）は予め設定された閾値cmaxに達する。
【０１３１】
そこで、ブロック配置手段９は、参照回数c（ak）が閾値cmaxに達した共線制約があるか否かを検査し（S３２）、ある場合には、閾値cmaxに達した一群の共線制約｛ak｝のなかで最も優先順位が低いものを削除する（S３３）。そして、冗長な共線制約を１つだけ削除した状態で、再びステップS３１に戻る。
【０１３２】
これにより、冗長な共線制約が存在すればそれは順次削除されてゆき、最後に冗長性が削除された共線制約のみが残る。ステップS３２で、参照回数c（ak）が閾値cmaxに達した共線制約がなくなった時点で処理を終了する。
【０１３３】
〔３−５−２〕配置圧縮処理
次に、図１３のステップS３１における配置圧縮処理について詳細に説明する。図１４〜図１６は、配置圧縮処理の流れを表すフローチャートである。まず、ブロック配置手段９は、全ブロックbi (∀bi∈B)の位置座標を（０，０）に初期化する（S４１）。これにより、例えば、図１７（a）に示したように、全てのブロックはレイアウト平面の左下隅の原点位置に重ねて配置された状態となる。
【０１３４】
そして、ブロック配置手段９は、全ブロックbi (∀bi∈B)の配置を未決定とする（S４２）。ここで、ブロック配置手段９は、ブロックbiの配置が決定されたか否かを表示するフラグとして変数fixxy（bi）を有している。fixxy（bi）＝０のときはブロックbiの配置は未決定、fixxy（bi）＝１のときはブロックbiの配置は決定済みを表す。ステップS４２において、全てのfixxy（bi）(∀bi∈B)は０に初期化される。更に、制約参照計数手段１６は、全ての共線制約ALIGN(ak)の参照回数c(ak)を０に初期化する（S４３）。
【０１３５】
次に、配置ブロック選択手段１４は、参照する順列Mのブロックの順位を表す変数iを１に初期化する（S４４）。
【０１３６】
次に、配置ブロック選択手段１４は、順列Mのブロックmi (∈B)を選択し、ブロックmiの配置を決定済み（fixxy(mi)=1）とする（S４５）。
【０１３７】
次いで、配置制約処理手段１５は、ブロック集合Bから、ブロックmi以外の１つのブロックbk（≠mi）を選択する（S４６）。そして、ブロックmiとブロックbkの間に次の関係が成り立つか否か、すなわち配置制約が存在するか否かを検査する（S４７）：
【０１３８】
【数１２】
2006146333.tif 000014
ここで、∃xF(x)は、F(x)であるxが存在する（存在作用素）ことを表す。
【０１３９】
関係式（７）が成り立つ場合、制約参照計数手段１６は、ブロックmiとブロックbkの間の配置制約akの参照回数c（ak）を１だけ増加させる（S４８）。その結果、c（ak）が閾値cmaxに達した場合には、ステップS５５に移る。c（ak）が閾値cmaxより小さければ、配置制約処理手段１５は、ブロックmi，bkのレイアウト平面上の座標（x（mi），y（mi）），（x（bk），y（bk））を検査し、共線制約akが充足されているかどうかを調べる（S５０）。共線制約akが充足されていれば、ステップS５５に移る。共線制約akが充足されていなければ、配置制約処理手段１５は、ブロックmi，bkが共線制約を満たすように、次の手順に従って何れか一方のブロックを移動する：
【０１４０】
【数１３】
2006146333.tif 000015
【０１４１】
ここで、ブロックbkの順列Mにおける順序β（bk）がブロックmiの順列Mにおける順序iよりも後であれば（S５２）、ステップS５５に移行する。一方、β（bk）＜iの場合には（S５２）、選択順位引戻手段１７は、系列Mのブロックbk及びブロックbkよりも順位が後の全てのブロックbj(β(bk) ≦ j )を配置未決定(fixxy(bj)=0)とする（S５３）。そして、iをβ(bk)とし、ステップS４５に戻る。
【０１４２】
ステップS５５においては、配置制約処理手段１５は、mi以外の全てのブロックbkを選択したか否かを判定する（S５５）。まだ未選択のものがあれば、ステップS４６に戻る。全て選択された場合には、ステップS５６に移行する。
【０１４３】
ステップS５６において、ブロック配置移動手段１９は、配置未決定のブロックbj (fixxy(bi)=0)を選択する（S５６）。
【０１４４】
そして、選択したブロックbjの順列Pにおける順位α（bj）がブロックmiの順列Pにおける順位α（mi）よりも前（α(bj)＜α(mi)）であれば（S５７）、ブロックbjのy座標y（bj）をmax(y(bj), y(mi)+h(mi))とする（S５８）。そうでなければ、ブロックbjのx座標x（bj）をmax(x(bj), x(mi)+w(mi))とする（S５９）。
【０１４５】
そして、全ての配置未決定ブロックbjについての処理が終わるまで（S６０）、ステップS５６〜S５９を繰り返す。
【０１４６】
全ての配置未決定ブロックbjについてステップS５６〜S５９の処理が終わると（S６０）、配置ブロック選択手段１４はi＝Nか否かを判定する（S６１）。i＝Nの場合には、配置圧縮処理を終了する。i＜Nの場合には、配置ブロック選択手段１４はiを１だけ増加させて、ステップS４５に戻る。
【０１４７】
以上の処理の結果、ブロック集合Bの全てのブロックの初期配置が確定する。確定した初期配置は、ブロック配置記憶手段１０に保存される。
【０１４８】
尚、以上の配置圧縮処理をわかりやすく説明するため、図１７に配置圧縮処理の一例を示した。図１７においては、ブロックb１〜b４の配置を行う。シーケンス・ペア（P，M）は、P＝（３，１，２，４），M＝（１，２，３，４）が与えられているとする。初期状態では図１７（a）の状態にある。
【０１４９】
まず、順列Mの１番目のブロックb１について配置圧縮処理を行うと、各ブロックの配置は図１７（b）のようになる。さらに、順列Mの２番目のブロックb２について配置圧縮処理を行うと、各ブロックの配置は図１７（c）のようになる。以下、順列Mの３番目のブロックb３、順列Mの４番目のブロックb４について配置圧縮処理を行っても各ブロックの配置は図１７（c）の状態に維持される。
【０１５０】
尚、この場合において、仮に共線制約としてALIGNT（２，４）が課されている場合、順列Mの２番目のブロックb２について配置圧縮処理が終了した段階で、各ブロックの配置は図１７（d）のようになる。
【０１５１】
〔４〕具体例
最後に、実際に本実施例に係るレイアウト作成装置１により、図６の回路図のブロック配置を行った例を図１８に示す。図１８は、ブロック配置手段９により出力される初期配置である。この初期配置に基づき、シーケンス・ペア圧縮処理手段１１によって配置圧縮処理を行うと、図１９のようなレイアウト配置が得られる。
【０１５２】
一方、比較例として、初期配置を行わずに、従来の方法でブロック配置を行った一例を図２０に示す。図１９と図２０を比べると、本実施例に係るレイアウト作成装置１は、初期配置を行ってからシーケンス・ペア圧縮処理手段１１による配置圧縮処理を実行することにより、より望ましいレイアウト配置が得られることが分かる。
【図面の簡単な説明】
【０１５３】
【図１】本発明の実施例１に係るレイアウト作成装置の構成を表すブロック図である。
【図２】（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングを示す図である。
【図３】（P，M）＝（abdecf，cbfade）に対応する（P，M）パッキングの（a）水平制約グラフ、及び（b）垂直制約グラフである。
【図４】最長路計算の結果得られたブロック配置の一例を示す図である。
【図５】実施例１に係るレイアウト作成装置１によるレイアウト作成方法の全体の流れを表すフローチャートである。
【図６】回路図データ記憶手段２に格納されている回路図の一例である。
【図７】図６の回路図の各部品を代表点で表した図である。
【図８】回路図からのシーケンス・ペアの抽出方法を説明する図である。
【図９】回路図からのシーケンス・ペアの抽出方法を説明する図である。
【図１０】回路図からの共線制約の抽出方法を説明する図である。
【図１１】アナログ回路における共線制約の優先順位の決定方法の一例を表すフローチャートである。
【図１２】デジタル回路における共線制約の優先順位の決定方法の一例を表すフローチャートである。
【図１３】ブロック配置手段９による冗長な共線制約の削除と配置圧縮処理の全体の流れを表すフローチャートである。
【図１４】配置圧縮処理の流れを表すフローチャートである。
【図１５】配置圧縮処理の流れを表すフローチャートである。
【図１６】配置圧縮処理の流れを表すフローチャートである。
【図１７】配置圧縮処理の一例を示す図である。
【図１８】図６の回路図のブロック配置を行った例である。
【図１９】図１８の初期配置に基づき、シーケンス・ペア圧縮処理手段１１によって配置圧縮処理を行った結果である。
【図２０】図６の回路図のブロック配置を、初期配置を行わずに、従来の方法でブロック配置を行った一例である。
【図２１】従来のレイアウト作成装置のシステムブロック図である。
【図２２】関係づけられた部品のリスト構造の一例を示した図である。
【図２３】図２２の部品のリストから生成される部品の配置関係を表す図である。
【図２４】設計者により部品配置上の制約が記注された回路図の例である。
【符号の説明】
【０１５４】
１  レイアウト作成装置
２  回路図データ記憶手段
３  部品レイアウト・ライブラリ
４  シーケンス・ペア生成手段
５  シーケンス・ペア記憶手段
６  配置制約設定手段
７  配置制約記憶手段
８  優先順位決定手段
９  ブロック配置手段
１０  ブロック配置記憶手段
１１  シーケンス・ペア圧縮処理手段
１２  水平共線制約設定手段
１３  垂直共線制約設定手段
１４  配置ブロック選択手段
１５  配置制約処理手段
１６  制約参照計数手段
１７  選択順位引戻手段
１８  配置制約削除手段
１９  ブロック配置移動手段
２０  回路図データ
２１  部品レイアウト・データ
２２  アナログ回路シミュレータ
２３  デジタル回路シミュレータ
２４  ブロック配置レイアウト・データ
【図１】
2006146333.tif 000018
【図２】
2006146333.tif 000019
【図３】
2006146333.tif 000020
【図４】
2006146333.tif 000021
【図５】
2006146333.tif 000022
【図６】
2006146333.tif 000023
【図７】
2006146333.tif 000024
【図８】
2006146333.tif 000025
【図９】
2006146333.tif 000026
【図１０】
2006146333.tif 000027
【図１１】
2006146333.tif 000028
【図１２】
2006146333.tif 000029
【図１３】
2006146333.tif 000030
【図１４】
2006146333.tif 000031
【図１５】
2006146333.tif 000032
【図１６】
2006146333.tif 000033
【図１７】
2006146333.tif 000034
【図１８】
2006146333.tif 000035
【図１９】
2006146333.tif 000036
【図２０】
2006146333.tif 000037
【図２１】
2006146333.tif 000038
【図２２】
2006146333.tif 000039
【図２３】
2006146333.tif 000040
【図２４】
2006146333.tif 000041