JPH01123368A - レイアウトコンパクション方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔手肌　　要〕 大規模集積回路等における回路要素の配置設計に関し、 同一回路を反復して多数敷き詰めたパターンの圧縮化処
理を合理化することを目的とし、入力図形を中心セルと
しこれに隣接する上下左右のセルの図形データを発生ず
る隣接セル発生部と、入力図形及び隣接セル発生部の発
生した各セルの各図形要素を節点とし予め設定された図
形要素間の距離制約を枝とする制約条件枝を生成する制
約条件生成部と、制約条件生成部の生成した制約条件を
満たす範囲でセル内図形要素の配置を発生して面積計算
部に渡しその結果を評価して最適な候補を出力する最適
化計算部と、最適化計算部から渡された配置について制
約条件生成部の生成した制約条件枝を用い（左セルの一
つの図形要素から右セルの同一図形要素への距離の最大
値）×（下セルの一つの図形要素から上セルの同一図形
要素への距離の最大値）を計算する面積計算部を備え、
与えられた入力図形を反復して多数敷き詰めたパターン
の配置の圧縮化処理を実行するよう構成する。

〔産業上の利用分野〕

本発明はＣＡＤ　（計算機援用設計）に係わり、特にＬ
ＳＩの設計に用いられるレイアウトコンパクション方式
に関する。

ＬＳＩの設計においては、限られた面積内に如何に多く
の機能要素を収容するかが設計上の最も重要なポイント
の一つである。そこで、要素間の距離制約（ある要素Ａ
とある要素８間の距離は一定値Ｃより近づけてはならな
いという回路設計上の制約）を満たしながらレイアウト
を最適に圧縮するのがレイアウトコンパクションである
。

メモリのセルのように同一の要素が反復して平面に敷き
詰められるようなパターンの場合は、従来のレイアウト
コンパクション方式では最適な結果が得られない場合が
あり、対策が要望されている。

〔従来の技術〕

従来のレイアウトコンパクション方式は、第５図に示す
ように、与えられた回路を囲む矩形領域の寸法を最小に
するよう動作する。

即ち、まず同図（ａ）に示すように、与えられた回路を
囲む矩形枠を想定し、矩形枠の左辺をｌ、右辺をｒ、上
辺をｔ、下辺をｂとする。図において、図形要素ＸＩ、
Ｘ２．Ｘ３．Ｘ４中の「・」は図形要素の代表点（基準
点）を示す。

次に同図（ｂ）に示すように、左辺！、右辺ｒと回路の
各図形Ｏｆ、Ｘ２．）ｌ、Ｘ４　）についてグラフの節
点を設定し、当該図形要素間の水平方向距離制約（ｙ＋
、　ｙ２．　ｙ３．ｙａ、−・・）を枝とするようなグ
ラフを図形要素の可能な全ての配置について作成する。

次いで、同様に、同図（Ｃ）に示すように、上辺し、下
辺すと各図形について節点を設定し、各図形要素間の垂
直方向距離制約（ｚ　１．　Ｚ　２．　Ｚ　３．　Ｚ　
ｎ、−）を技としてグラフを作成する。

一つの配置についてグラフの辺２から辺ｒに至る枝の合
計距離の最大値を！ｒとし、辺ｔから辺すに至る技の合
計距離の最大値をｔｂとする。

このグラフについて、回路の面積、即ちグラフ上の距ｉ
［ｉ！、ｒとｔｂとの積を評価関数としてこれを最小と
する最適化問題を解くことにより回路要素配置のコンパ
クションの解が得られるものである。

このように従来のコンパクション方式では、メモリの１
セルのように平面充填的に反復して用いられるパターン
に対しても、同様に、矩形領域として面積が最小になる
ようにしか動作しない。

〔発明が解決しようとする問題点〕

例えば、第６図（ａ）に示すような形のセルは、同図ら
）に示すように敷き詰めることにより全体として最小の
面積になるのであるが、従来のコンパクタを使用した場
合は、同図（Ｃ）に示すように、単位セルの外接矩形の
最小化を行うため、全体として見ると、無駄領域を生ず
ることになる。

これが原因で、コンパクションプログラムを繰返しパタ
ーンに適用することが困難となっている。

本発明は、このような従来の問題点を解消したレイアウ
トコンパクション方式を提供しようとするものである。

〔問題点を解決するための手段〕

第１図は、本発明のレイアウトコンパクション方式の原
理ブロック図を示す。

図において、■は隣接セル発生部であり、人力図形を中
心セルとしこれに隣接する上下左右のセルの図形データ
を発生する。

２は制約条件生成部であり、人力図形及び隣接セル発生
部１の発生した各セルの各図形要素を節点とし予め設定
された図形要素間の距離制約を枝とする制約条件枝を生
成する。

３は最適化計算部であり、制約条件生成部２の生成した
制約条件を満たず範囲でセル内図形要素の配置を発生し
て面積計算部４に渡しその結果を評価して最適な候補を
出力する。

４は面積計算部であり、最適化計算部３から渡された配
置について制約条件生成部２の生成した制約条件枝を用
い（左セルの一つの図形要素から右セルの同一図形要素
への距離の最大値）×（下セルの一つの図形要素から上
セルの同一図形要素への距離の最大値）を計算する。

〔作　用〕

本発明では、従来方式のように矩形枠を用いず、与えら
れた回路（入力図形）を中心セルとし、これと同じ図形
を上下左右に並べて、これらのセル図形間でコンパクシ
ダン処理を行う。

まず、隣接セル発生部１は入力図形を中心セルＣとして
、第２図に示すように、これと同一の図形を上下左右に
発生し、４つの隣接セルＬ、Ｒ。

Ｔ、Ｂとして並べる。

制約条件生成部２は、それぞれのセル内の各図形要素を
節点とし予め規定しである図形要素間の距離制約を技と
してセル内図形要素相互間制約条件枝を生成する０次い
で、中心セルと隣接セルの各図形要素間にも制約条件枝
を生成する。

最適化計算部３は、セル内各図形要素の配置をセル内図
形要素相互間の制約条件を満たす範囲で変更し、面積計
算部４へ渡す。

面積計算部４は、渡されたセル内配置について、制約条
件生成部２の生成した制約条件枝を用いて次の計算を行
う。即ち、セルＬの一つの図形要素（例えばＸｌ）から
セルＬの同一の図形要素（ＸＩ）への距離を計算し、全
図形要素（Ｘｌ、Ｘ２．Ｘ３）についての距離のうちの
最大のものを選び、これをＨとする。同様に、セルＢの
図形要素からセルＴの同一の図形要素への距離を計算し
、最大のものを選びこれをＶとする。次に、ＨＸ　Ｖを
計算して、最適化計算部３へ渡す。

最適化計算部３は、面積計算部４から渡されたＨＸＶＯ
値のうち最小の値を記憶しておく。このようにして各配
置について計算した結果、ＨＸ　Ｖの最小値を示した配
置が、最適配置として出力される。

この配置におけるセル間水平間隔はＩ（／２であり、垂
直間隔はＶ／２である。

〔実施例〕

以下第３図及び第４図に示す実施例により、本発明をさ
らに具体的に説明する。

第３図は、本発明の一実施例の構成を示すブロック図で
ある。

１は隣接セル発生部であり、コピー作成部１１が入力図
形１０をコピーして隣接セル図形り、Ｒ，Ｔ。

Ｂ　（１２）を発生する。

２は制約条件生成部であり、制約条件生成部２２が入力
図形１０および隣接セル図形１２について、予め設定し
である制約条件データ２１に基づいて、節点テーブル２
３および枝テーブル２４を生成する。

３は最適化計算部であり、セル内配置発生部３１が入力
図形１０及び技テーブル２４を参照してセル内図形要素
間制約条件枝を満たす範囲で変更配置を発生して面積計
算部４へ渡す。

最小値格納部３２は面積計算部４からの計算結果を既に
格納しである現在までの最小値と比較し、小さい方の値
を、付随データ（配置番号及びセル間間隔）格納する。

評価部３３は最小値格納部３２の格納する面積値を評価
し、セル内配置発生部３１に配置発生の継続又は停止を
指示し、終了すれば最小面積の配置データ及びセル間間
隔データを出力する。

第４図は、本発明の一実施例における制約条件枝のデー
タ構造を示す図である。

４は面積計算部であり、距離計算部４・ｌが入力図形Ｉ
Ｏ及びセル内配置発生部３Ｉの発生した配置について、
節点テーブル２３および技テーブル３４に基づいて、（
セルＬ中の図形ＸからセルＲ中の図形Ｘへの距離）の全
Ｘに関する最大値、及び（セルＢ中の図形ＸからセルＴ
中の図形Ｘへの距離）の全Ｘに関する最大値を計算する
。

面積計算部４２は距離計算部４１の計算した距離を乗算
し面積を算出して最適化計算部３の最小値格納部３２へ
渡す。

第４図（ａ）は節点テーブルであり、各図形要素ごとに
、その名称、図形データへのポインタ（アドレス）、こ
れを使用した枝テーブルへのポインタを格納する。

同図（ｂ）は水平方向技テーブルであり、各水平方向制
約条件枝ごとに、その左節点へのポインタ、右節点への
ポインタ、制約距離値、その他の付随データを格納する
。

同図（Ｃ）は垂直方向技テーブルであり、同様に各垂直
方向条件技ごとに、下節点へのポインタ、上節点へのポ
インタ、制約距離値、その他の付随データを格納する。

〔発明の効果〕

以上説明のように本発明によれば、レイアウトコンパク
ションプログラムを容易に敷詰めパターンに対して適用
することが可能となり、メモリ等を含むＬＳＩ設計の所
要時間の短縮に寄与する効果はきわめて大きい。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の詳細な説明する図、 第３図は本発明の一実施例の構成を示すプロ・ンク図、 第４図は本発明の一実施例における制約条件枝のデータ
構造を示す図、 第５図は従来方式のレイアウトコンパクションを示す図
、 第６図は敷詰めパターンのコンパクションを説明する図
である。 図面において、 ■は隣接セル発生部、　　２は制約条件生成部、３は最
適化計算部、　　　４は面積計算部、１０は入力図形、
　　　　　１工はコピー作成部、１２は隣接セル図形、
　　　２１は制約条件データ、２２は制約条件核生成部
、　２３は節点テーブル、２４は技テーブル、　　　　
３１はセル内配置発生部、３２は最小値格納部、　　　
３３は評価部、４１は距離計算部、　　　　４２は面積
計算部、をそれぞれ示す。 本発明の原理ブロック図 第１図 本発明の一実施例の構成を示すブロック図水平技テーブ
ル　　　　　　　　　　　　　　　　垂直技テーブル（
ｂ）　　　　　　　　　　　　　　　　　　　　　　　
（ｃ）本発明の一実茄そりにおける制約条件枝のデータ
構造を示す図第　　　４　　　図 従来方式のレイアウトコンパクシランを示す図第　　５
　　図

Claims (1)

1. 【特許請求の範囲】 大規模集積回路等における回路要素の配置設計において
   、 入力図形を中心セルとしこれに隣接する上下左右のセル
   の図形データを発生する隣接セル発生部（１）と、 入力図形及び隣接セル発生部（１）の発生した各セルの
   各図形要素を節点とし予め設定された図形要素間の距離
   制約を枝とする制約条件枝を生成する制約条件生成部（
   ２）と、 制約条件生成部（２）の生成した制約条件を満たす範囲
   でセル内図形要素の配置を発生して面積計算部（４）に
   渡しその結果を評価して最適な候補を出力する最適化計
   算部（３）と、 最適化計算部（３）から渡された配置について制約条件
   生成部（２）の生成した制約条件枝を用い（左セルの一
   つの図形要素から右セルの同一図形要素への距離の最大
   値）×（下セルの一つの図形要素から上セルの同一図形
   要素への距離の最大値）を計算する面積計算部（４）を
   備え、 与えられた入力図形を反復して多数敷き詰めたパターン
   の配置の圧縮化処理を実行するよう構成したことを特徴
   とするレイアウトコンパクション方式。