JPH03225941A - レイアウト設計方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の目的〕 （産業上の利用分野） 本発明は、集積回路におけるレイアウト設計方法に関す
る。

（従来の技術） 集積回路のレイアウト設計処理の技術として、例えば配
置処理としては、Ｍ、Ａ、Ｂｒｅｙｅｒ“Ｍｉｎ−Ｃｕ
ｔＰ１ａｃｅｗ＋ｅｎｔ”、Ｊｏｕｒｎａｌ　ｏｆ　Ｄ
ｅＳｉｎｇ　Ａｕｔｏｍａｔｉｏｎ　ａｎｄＦａｕｌｔ
−Ｔｏｌｅｒａｎｔ　Ｃｏｍｐｕｔｉｎｑ、０ｃｔｏｂ
ｅｒ　１９７７、ｐｐ、３４３−３６２．配線処理とし
てはＨａｓｉｍｏｔｏ、　Ａ、、　ａｎｄ　Ｊ。

５ｔｅａｖｅｎｓ、“Ｗｉｒｅ　ｒｏｕｔｉｎｇ　ｂｙ
　ｏｐｒｉｍｉｚｉｎｇ　ｃｈａｎｎｅｌａｓｓｉｇｎ
ｍｅｎｔ　ｗｈｉｔｈｉｓ　ｌａｒｇｅ　ａｐｅｒｔｕ
ｒｅｓ、”ｉｎ　Ｐｒｏｃ。

８ｔｈ　Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ　Ｗｏｒ
ｋｓｈｏｐ　１９７１．ｐｐ、１５５−１６３、などが
知られている。従来技術におけるレイアウト設計では、
これらの配置処理、配線処理が個々に独立した方法とし
て、明確に分離されている。それらの処理はたいへん優
れているものであるが、従来技術による処理フローでは
、各処理が独立しているため、個別の問題に対する解を
ただ積み重ねていくだけとなり、たとえ個々の処理が最
適な解を算出するものであっても最終的な結果で最適な
レイアウト結果を得ることができない。

例えば、スタンダードセル方式による集積回路の自動設
計方式では、回路素子の配置が終了した後に、回路素子
を移動させることによって配線が通過できる領域を確保
することを行なう。この処理は、場合によっては、配置
処理によって得られた回路素子の最適な位置関係を壊す
ことになる。

レイアウト設計における目的の一つに集積度の向上が上
げられるが、この目的を達することと、単にチップ領域
の面積が最小になるように回路素子を配置することとは
異なる。最終的にはチップ領域内には回路素子端子間を
接続する配線を構成する必要があるため、配置処理にお
いては端子間の配線を十分考慮したものでなければなら
ない。

上に挙げた例では、配線処理において回路素子を移動さ
せる必要が生じたならば、本来ならば、配置処理を再び
行なわなければならない。しかし、３− 各処理が完全に独立している処理フローでは配置と配線
の２つの処理を繰り返し行なうとは困難である。従来技
術では、配置、配線に処理を融合し、繰り返し行ないな
がらレイアウト設計を進めて行く方法は明示されていな
い。

（発明が解決しようとする課題） 集積回路の集積度を向上させるために様々な技術が提案
されている。しかし、従来技術によるレイアウト設計の
処理フローは、配置、概略配線、詳細配線の各処理が個
々に独立したものであった。

このような処理フローでは、たとえ個々の処理が最適な
解を導出する方法であっても最終的なレイアウト結果に
おいて最適な解を得ることは困難である。本発明は、従
来独立して行なわれてきた処理を平行して行なうレイア
ウト設計方法を提案することを目的としている。

〔発明の構成〕

（課題を解決するための手段） 本発明は上記事情に鑑みて為されたもので、回路素子を
チップ領域内の複数の帯状領域に配置４− し回路素子端子の結線要求を満たす配線を決定する際に
、前記チップ領域内に回路素子の配置・配線が決定され
た配置・配線決定領域と未だ回路素子の配置・配線が決
定されていない配置・配線未決定領域を持ち、配置・配
線決定領域の配置・配線情報をもとにして配置・配線未
決定領域の回路素子の概略配置を修正し、配置・配線未
決定領域内に帯状領域の長手方向と直交する方向に複数
の帯状領域に渡る配置・配線予定領域を決定し、この配
置・配線予定領域内の回路素子の詳細配置を決定すると
共に、配置・配線予定領域内の回路素子間の配線を決定
し、配置・配線決定領域及び詳細配置及び配線が決定さ
れた配置・配線予定領域を新たに配置・配線決定領域と
して登録更新することを特徴とするレイアウト設計方法
を提供するものである。

（作用） この発明はレイアウト設計を行なう際にチップ領域を幾
つかの小領域に分割し、この小領域の左の列から右の列
へと回路素子の詳細な配置と配線を同時に進め、チップ
全体のレイアラ１〜処理を完成させて行くことでレイア
ウト設計における配置、配線処理を平行処理が可能とな
る。

（実施例） 以下、本発明の実施例を図面を交えながら説明していく
。

まず、本実施例で用いる言葉の定義を行なう。

・セル：チップ上に配置されたセル間を配線することで
目的の回路を構成する。配線とセルを接続する端子は配
線層の第２層目におかれる。セル上の配線層は、第２層
目だけを利用することができ、配線を通過させることが
できる領域とできない領域を含む。

・チップ領域：集積回路のチップ領域は回路素子が帯状
に配置されたＮ個のセル行から構成する。

・小領域二本発明では、第４図に示すようにチップ領域
に（ト１）本の垂直方向のカットライン１３Ｖ（ｋ）、
　ｋ＝１〜Ｍ−１と（Ｎ−１）本の水平方向のカットラ
インｈ（Ｉ）、Ｉ＝ｔ〜Ｎ−１を引くことによりチップ
領域をＭＸＮ個の矩形領域に分割する。この矩形領域を
ｇ（ｉ、ｊ）、ｉ＝１〜Ｍ、ｊ＝１〜Ｎで表わし、小領
域と呼ぶ、ｉは列番号、ｊは行番号である。ここでＮは
、チップ領域のセル行数である。

小領域には、分割されたセル行を含む。そのセル行を構
成するセル集合をｓ　（ｉ、ｊ）で表わす。ただし、本
発明による処理によってセル位置は刻々と変動するため
、ここで言うところのセル行は個々のセルの詳細な位置
が決定されているものではない。小領域の詳細な説明図
を第５図に示す。小領域ｇ　（ｉｔｊ）の左のカットラ
イン１７をｖ（ｉ、ｊ）、右のカットライン１８をｖ（
ｉ、ｊ＋１）、上のカットライン１９をｈ　（ｉ、ｊ＋
　１　）、下のカットライン２０をｈ（ｉ、ｊ）とする
。ｒ　（ｉｔｊ）は、小領域ｇ　（ｔｅｊ）が含む分割
されたセル行である。

・スルー配線：　ｈ　ｂ＋Ｊ）を通過しｓ　（ｉ、ｊ）
のセルと接続せずにｈ（ｉｌｊ＋　Ｉ　Ｌ　ｖ　（ＩＩ
ｊ）　＋　ｖ　ｂａｊ＋　１）を通過する配線。小領域
ｇ（ＩＩｊ）を通過するスルー配線の緩和をｔｈ（ｘｔ
ｊ）で表わす。スルー配線は、ｒ　（ＩＩｊ）のセル上
を通過する。

・スル一端子：セル上にスルー配線を通過させ７− るために、処理の便宜上、セル上にスルー配線を通過さ
せることができる領域に仮想的に設けた端子。本発明に
おける処理では、スルー配線はセル上を通過するときに
、−度この仮想的な端子に接続してから通過する。スル
一端子は常に１本のスルー配線とのみ接続し、他の配線
と接続することはない。

・スルーセル：スルー配線を通過させるための仮想的な
セル。スルー配線を通過させる領域を確保するために、
セル行の任意の位置に挿入する。

スルーセルは、スル一端子を１個だけもつセルで、集積
回路の電気的構成には、なにも関与しない。

・スルー容量：小領域ｇ（ｉ、ｊ）を通過することので
きるスルー配線の本数の上限。セル集合ｓ（ｉ。

ｊ）のセルのスル一端子の総和で表わされる。

・チャネル配線：小領域ｇ（ｉ、ｊ）を通過する配線で
スルー配線以外の配線、ｇ（ｉ、ｊ）を通過するチャネ
ル配線の総和をｃｈ（ｘ、ｊ）で表わす。

・ウィンドウ、確定領域、不確定領域二本発明による方
法では、配線ステップとセル位置の修正８− のステップを同時に行なうためにウィンドウと言う概念
を用いる。ウィンドウは、チップ領域をセル行と垂直に
設けられた長方形の領域であり、Ｍ個の小領域から構成
される。第４図に示す例では、ウィンドウ１０は小領域
ｇ　（１１ｊ）　＋　ｊ＝　１〜Ｎで構成されている。

このウィンドウを第２図、第３図に示すように、チップ
領域の左端から右端に移動させながらセル位置の修正と
配線を平行して行なう。ウィンドウより左の領域ではセ
ルの位置、配線が決定されている。この領域を確定領域
１１とよぶ。ウィンドウより右の領域ではセルの位置、
配線は未定の状態である。この領域を不確定領域１２と
よぶ。確定領域の配線結果により不確定領域内のセル位
置の修正を行ない、この配置結果よりウィンドウ内の配
線を行なう。

第１図は、本発明の一実施例を示す処理フローを示した
図である。

本発明では、まず集積回路を構成するセルの接続データ
ー（ネットリスト）及び規定セル行数Ｎを入力として受
は取り初期データーを作成する。

次に、この初期データーの作成方法の一例（ω〜■）を
示す。

■　従来技術による配置処理によりＮ行のセル行からな
る、配置データーを作成する。

■　チップ領域に、（ト１）本の垂直方向のカットライ
ン、及び（Ｎ−１）本の水平方向のカットラインを入れ
ることによりＭＸＮ個の小領域ｇ　（ｉｅｊ）　ｒｉ＝
１〜Ｍ、ｊ＝１〜Ｎに分割する。

■　これらの小領域ｇ　（ＩＩｊ）に含まれたセルをセ
ル集合ｓ　（ＩＩｊ）とする。

この初期データーを受けてチップ領域のレイアウト設計
を幾つかのレベルに分けて行なう。なお、本実施例にお
ける例では、処理は１からＭレベルの処理に分けてレイ
アウト設計を行なうことになる。それぞれのレベルの処
理において次に示すプロセスを実行する。

■　不確定領域内の小領域に含まれるセル集合の再構成
を行なう２゜（配置修正） ■　不確定領域の左端の一列の小領域を覆うウィンドウ
を形成する。

■　ウィンドウを通過する配線をウィンドウ内の小領域
に割り当てる３゜（概略配線）（へ）　ウィンドウ内の
セル行を構成する４゜（詳細配置） ■　ウィンドウ内のチャネルの配線を行なう５゜（詳細
配線） ０　ウィンドウより右の領域を不確定領域とする６゜不
確定領域が存在しなければ処理を終了する。

以下、各ステップの詳細な説明を行なう。なお、ここで
にレベルまで処理が進んでいるものとして説明する。す
なわち、・カットラインＶ　（ｋ）より左の領域が確定
領域であり、右の領域が不確定領域である。確定領域は
小領域ｇ　（ｉ、ｊ）＋　ｉ　＝　１〜に−１゜ｊ＝１
〜Ｎで構成され、不確定領域は小領域ｇ（ｂａｊ）　ｖ
　１　＝　ｋ−Ｍ　ｔ　ｊ＝　１〜Ｎで構成されている
。

また確定領域内の配置、配線は完了している。ウィンド
ウＷ（ｋ）は小領域ｇ（ｋ＋ｊ）、ｊ　＝　１〜Ｎで構
成されている。

く配置修正〉 １− このプロセスでは不確定領域内の配置修正を行なう。

今、ｋレベルの処理を行なうとする。このときｌｋ）　
１５より右の領域が不確定領域１２となる。不確定領域
は、小領域ｇ（ｉＪ、１＝に−Ｍｌ　、ｊ＝１〜Ｎから
構成されている。小領域ｇ　（１＋ｊ）に割り付けられ
たセル集合をｓ（ｉ、ｊ）とする。ｇ　ｂａｊ）　＊ｉ
＝１〜Ｍを通過し、ｓ　（ｉ、Ｉ）　、　ｉ　＝　１〜
Ｍ内のどのセルにも接続されない配線の総和をＴＨ（Ｉ
）とする。

ＴＩ（（Ｉ）＝　　Σｔｈ（ｉ、Ｉ） ｉ＝１ である。ｇ　（ｘｓＩ）　ｖ　ｉ＝　１〜Ｎを通過する
配線の総和をＣＨ（Ｉ）とする。

ＣＨ（Ｉ）＝　Σｏｈ（Ｉ、ｊ） −１ である。この２つの値を減少させるように不確定領域内
のセルの配置修正を行なう。確定領域の配線は完了して
いるので、確定領域の配線情報を不確定領域の配置修正
に反映させることができる。

１２− 配置修正プロセスの処理のフローを第２１図に示す。こ
のプロセスは、次の［配線修正操作１］と［配線修正操
作２］からなる。

［配置修正操作１］ ■　小領域ｇ　（ｉｒｊ）のセル集合Ｓ（ｉ、ｊ）と小
領域ｇ　（ｂａｊ　＋　１）のｓ（ｉ、ｊ＋１）とを合
成し１つのセル集合ｓ　（ｉ、ｊ）（ｂａｊ　＋１）を
つくる。

■　セル集合ｓ　（ｘｙｊ）　（Ｌｊ＋　１）を２つの
セル集合ｓ’（ｂａｊ）とｓ（ｉ、ｊ＋１）に分割する
。ここでｓ　（ｉｔｊ）は小領域ｇ　（ｉｙｊ）に新た
に含まれるセル集合、ｓ’　（ｌｙｊ＋　１）は小領域
ｇ　（１９ｊ＋　１）に新たに含まれるセル集合である
。分割の指標は、 評価関数： ＴＨ（ｉ）＋ＴＨ（ｊ＋１）→ｗｉｎ　（ＴＨ（ｉ）＋
ＴＨ（ｊ＋１）　　を最小にする。） ｌｅｎ（ｉ、ｊ）−１ｅｎ（ｉ、ｊ＋１）ｌ−＋ｍｉｎ
　（ｌｌｅｎ（ｉ、ｊ）　−１Ｏｎ（ｉ＋ｊ＋　１）ｌ
を最小にする。）を用いる。なお、ｇ（ｘｙｊ）に含ま
れるセルの長さの総和をＪａｎ（ｉ、ｊ）としている。

■　セル集合ｓ’　（１１ｊ）をｓ　ｂａｊ）として登
録する。

セル集合ｓ’（ｉ、ｊ＋１）をｓ（ｉ、ｊ＋１）として
登録する。

［配置修正操作２］ ■　小領域ｇ（ｉ、ｊ）のセル集合Ｓ　（Ｘ＋ｊ）と小
領域ｇ（ｉ＋１．ｊ）のｓ（ｉ、ｊ＋１）とを合成し１
つのセル集合ｓ　（ｉ、ｊ）（ｉ＋Ｌｊ）をつくる。

■　セル集合ｓ　（ｘｔｊ）　（１＋１．ｊ）を２つの
セル集合”　（ｘｔｊ）とｓ’（ｉ＋１．ｊ）に分割す
る。ここでｓ’（１゜ｊ）は小領域ｇ　（Ｌｊ）に新た
に含まれるセル集合、ｓ’（ｉ＋１．ｊ）は小領域ｇ（
ｉ＋１−ｊ）に新たに含まれるセル集合である。分割の
指標は、 評価関数： ＣＨ（ｉ）　＋ＣＨ（ｉ＋　１）→ｗｉｎ１１ｅｎ（ｉ
、ｊ）−１ｅｎ（ｉ＋１．ｊ）→ｌｌｌ１ｎを用いる。

■　セル集合ｓ’　（ｂａｊ）をｓ　（１ｒｊ）として
登録する。

セル集合ｓ’　（ｉ＋　１．Ｊ）をｓ（ｉ＋１ｔｊ）と
して登録する。

配置修正プロセスは、第２１図に示すように上記の［配
置修正操作１］と［配置修正操作２］を評価関数の改善
が無くなるまでｉ　＝　ｋ−Ｍ、　ｊ　＝　１〜Ｎの小
領域に対し繰り返し行なう。

〈概略配線〉 このプロセスでは、配線の概略の経路を決定する。ｋレ
ベルの処理では、小領域ｇ　（ｘ、ｊ）　ｉ＝に−Ｍ、
ｊ＝１〜Ｎで構成される不確定領域を対象にして概略配
線処理を行なう。ここで言うところの概略図配線処理と
は、セルがどの小領域に属しているか、と言う情報のみ
にもとづいて、各配線が通過する小領域（概略経路）を
決定する処理である。

ｋレベルの概略配線処理にでは、ｋ−ルベルまでの処理
によって確定領域内の配置、配線は完了している。従っ
て、Ｖ　（ｋ）を通過して確定領域から不確定領域に入
力してくる配線は、求められている。これらの配線のな
かで、Ｖ（ｋｌｊ）を通過して小領域ｇ（Ｌｊ）に入力
してくる配線の集合をｄ（ｋ、ｊ）とする。

このプロセスでは、不確定領域内の小領域ｇｃｉ＊Ｊ）
　ｙ　１　”　ｋ−Ｍ　ｐ　Ｊ　＝　１〜Ｎを通過する
配線数が均一になるように、ｄ（ｋ、ｊ）、ｊ＝１〜Ｎ
と５（ＬＪＬｉ　＝　ｋ　−Ｍ　、　ｊ　＝　ｉ　＝　
Ｎに含まれるセルとの間の５− 概略経路、及びｓ（ｉ、ｊ）、　ｉ　＝　ｋ＝Ｍ、　ｊ
　＝　ｉ　−Ｎに含まれるセル間の概略経路を求めるこ
とを目的としている。しかし、本発明による処理フロー
では、ｋ＋ルベル以降の処理により、ｇｃｉ＋ｊ）、ｉ
＝に＋１〜Ｍ、ｊ＝１〜Ｎの各小領域のセル集合ｓ　（
ｉ。

ｊ）は変動する。そのため、ｋレベルの概略配線処理で
構成した概略経路は、ｋ＋ルベル以降の処理により崩れ
てしまうものである。従って、不確定領域内の全てのセ
ル間の概略経路を、このプロセスで求めることは、処理
効率の点から必ずしも得策ではない。以下に示す概略配
線処理方法の一例は、ウィンドウＷ（ｋ）にのみ注力し
たものである。

第２２図に本実施例における概略配線処理のフローを示
す。このプロセスは、［概略配線操作１］と［概略配線
操作２］の２つの操作から構成される。第２３図に［概
略配線処理２］の処理フローを示す。

ｋレベルの概略配線処理では、 ・ｄ　（ｋｌｊ）　ｔ　Ｊ　＝　１〜ＮとＳ（ｋ、ｊ）
、ｊ＝１〜Ｎに含まれるセルとの間の概略経路、 １６− ・ｄ（ｋ、ｊ）、ｊ＝１〜Ｎと５（ＬｊＬ　ｉ＝に＋１
〜Ｎ　＋　Ｊ　＝　１〜Ｎに含まれるセルとの概略経路
、・ｓ（ｋ、ｊ）　ｌ　ｊ＝　１〜Ｎに含まれるセルと
の間の概略経路、 ・ｓ　（ｋｔｊＬ　ｊ　＝　１−Ｎとｓ　（１＋Ｊ）　
ｔ　ｘ　＝　１〜に＋１〜Ｍ、ｊ＝１〜Ｎに含まれるセ
ル間の概略経路、 を求める。ｓ　（ｉ、ｊ）、　ｉ　＝に＋１〜Ｍ、　ｊ
　＝　１〜Ｎに含まれるセル間の概略経路は求めない。

すなわち、１個以上のセルが５（ＬｊＬ　ｊ＝１〜Ｎに
属しているネットと、１個以上のセルが５（ｌｙｊＬ　
ｌ＝１〜に−１に属し、かつ、１個以上のセルがｓ（ｉ
。

ｊＬ　ｉ＝に−Ｍ、ｊ＝１〜Ｎに属しているネットが、
ｋレベルにおける処理の対象となる。

また、対象となるネットにおいて、２個以上のセルが５
（ＬｊＬ　ｊ＝に＋１〜Ｍに含まれている場合（すなわ
ち、２個以上のセルが不確定領域からウィンドウを除い
た領域に含まれている場合）は、これらのセルの中から
１個だけ選んでｄ　（ｋ、ｊ）及ＴＪ’ｓ（ｋ、ｊ）の
セルとの間の概略経路を求める。セルを選ぶ場合の指標
としてはマンハッタン長を用い、ｓ　（ｋ、ｊ）　ｔ　
ｊ＝　１〜Ｎに属するセル（すなわち、ウィンドウに含
まれるセル）とマンハッタン長が最も近いセルを選ぶ。

ここで言うマンハッタン長とは、２個のセルを頂点に持
つ矩形の縦、横の辺の長さの和で表わす長さである。マ
ンハッタン長が同じセルが２個以上存在するときは、こ
れらのセルの中から水平方向の距離が最も短い小領域に
属するセルを選ぶ。

次にこのプロセスの各操作の詳細を述べる。

［概略配線操作１］ この操作で対象とする概略経路は接続するセルの位置関
係で一意的に定まるものである。次に概略経路が一意的
に決まる。セルの位置関係を示す。

ｄ（ｋ、Ｉ）。

満たすもの。

（イ）Ｉ＞ｎかつｍ＝ｋ。

（ロ）Ｉｎｎかつｍ＝ｋ。

（ハ）Ｉ＝ｎかつｍ≧に０ Ｉ＝１−Ｎとｓ（ｍ、ｎ）が次の関係を・ｓ　（ｋ、、
：＋）とｓ　（ｋ、ｎ）が次の関係を満たすもの。

（ニ）Ｉ＜ｎ。

（ホ）Ｉ）ｎ。

上記の条件を満たすセルについて、下記に示すパターン
の概略経路を割り当てる。概略経路の例を第６図から第
８図に示す。

（ａ）　ｄ　（ｋ、Ｉ）とｓ　（ｍ、ｎ）との概略配線
。

Ｉ）ｎ、ｍ＝にの場合：ｖ（ｋ、Ｉ）およびｈ（ｋ＋ｊ
Ｌｊ＝ｎ＋１〜工を経過する経路。

Ｉ＜ｎ、ｍ≦にの場合：ｖ（ｋ、Ｉ）およびｈ（ｋ、ｊ
）。

ｊ＝Ｉ＋１〜ｎを経過する経路（第７図）。

Ｉ＝ｎ、ｍ＝にの場合：　ｖ（ｉｔＩＬ　ｉ＝に−ｎを
経過する経路（第８図）。

（ｂ）　ｓ　（ｋ、Ｉ）とｓ　（ｋ、ｎ）との概略配線
（第６図）。

Ｉ　＞　ｎの場合”　ｈ　（ｋ、ｊ）　ｌ　ｊ＝ｎ　＋
　１〜Ｉを通過する経路。

Ｉ　＜　ｎの場合：ｈ（ｋ、ｊ）、ｊ＝■＋１〜ｎを通
過する経路。

［概略配線操作２コ この操作では［概略配線処理１］で未処理と１９− したセルを対象とする。概略経路は一意的には定まらず
、幾つかのパターンを持つ。下にそのパターンを示す。

第９図から第１３図に概略経路の例を示す。

（ａ）　　ｄ　（ｋ、Ｉ）とｓ　（ｉ、ｎ）＋　　ｉ　
＝に＋１〜Ｍとの概略配線。

・Ｉ　＞　ｎの場合（第１１図）： Ｖ（ＬＩＬ　ｖ（ｋ＋１．Ｉ）＋　”・ｌ　Ｖ（１＋Ｉ
Ｌ１１（１＋ＩＬｈ　（ｉｌＩ−１）、−１ｈ（１，ｎ
＋１）を通過する経路。

ｖ（ｋ、Ｉ）、　ｈ（ｋ、Ｉ）、　ｖ（ｋ＋１．　ｌ−
１）、　ｖ（ｋ＋２゜■−１）　ｌ　”’　ｔ　Ｖ　（
ＩＩＩ−ＩＬｈ（１＊ｌ−１）ｔ　ｈ　（１＋ｌ−２）
＋　”’ｖ（ｋ、Ｉ）、　　ｈ（ｋ；Ｉ）、　　ｈ（ｋ
、ＩＩＩ）、−、ｈ（ｋ、ｎ＋１）。

ｖ（ｋ＋１．ｎ）、・・・、　ｖ　（ｉ、ｎ）を通過す
る経路。一般的に（ｎ−１＋１）種類の概略配線のパタ
ーンがある。

・Ｉ　＜　ｎの場合： Ｖ（ｋｔＩＬ　ｖ（ｋ＋１．Ｉ）ｌ−Ｉ　Ｖ（ｉｔＩＬ
　ｈ（ｉｌＩＬｈ　ｂｔ’ｒ　＋　ＬＬ”’ｔｈ（１＋
ｎ）を通過する経路。

ｖ（ｋ、Ｉ）、　ｈ（ｋ、ＩＩＩ）、　ｖ（ｋ＋’ｌ、
　ＩＩＩ）、　ｖ（ｋ＋２．　ＩＩＩ）、・・・、　ｖ
（ｉ、ＩＩＩ）、　ｈ（ｉ、Ｉ＋２）、　ｈ（ｉ。

Ｉ＋３）、・・・ｔ　ｈ　（ｉｅｎ）を通過する経路。

２０ ｖ（ｋ、Ｉ）、　　ｈ（ｋ、ＩＩＩ）、　　ｈ（ｋ、Ｉ
＋２）、・＝、ｈ（ｋ、ｎ）。

ｖ　（ｋ　＋１　＋　ｎ）　＋・・・、　ｖ　（ｉ、ｎ
）を通過する経路。一般的に（Ｉ−ｎ＋　１　）種類の
概略配線のパターンがある。

（ｄ）　　ｓ　（ｋ、Ｉ）とｓ　（ｉｔｎＬ　ｉ　＝に
＋ｔ−Ｍ　との概略配線。

Ｉ＞ｍの場合（第１０図）： ｖ（ｋ＋１．　■）ｌ”’ｔ　Ｖ（１，ＩＬ　ｈ（ｘ、
Ｉ）、　ｈ（ｘ、ｌ−１）、・・・ｅ　ｈ　（ｉ、ｎ＋
１）を通過する経路。

ｈ（ｋ、Ｉ）、　ｖ（ｋ＋１．ｌ−１）、　ｖ（ｋ＋２
．ｌ−１）、−、ｖ（ｉ、ｌ−１）、　ｈ（ｉ、ｌ−１
）ｌ　ｈ（ｉｌｌ−２）ｌ−＝ｌｈ（ｉｌｎ＋１）を通
過する経路。

ｈ（ｋ、Ｉ）、　ｈ（ｋ、ｌ−１）、・＝、ｈ（ｋ、ｍ
＋１）、　ｖ（ｋ＋１゜ｎＬ・・・ｌ　Ｖ　（ｉｌｎ）
を通過する経路。一般的に（ｎ−１＋１）種類の概略配
線のパターンがある。

・Ｉ　＜　ｎの場合： ｖ（ｋ＋１．　ＩＬ”’ｔ　ｖ（４Ｊ）ｙ　ｈ（ｘ、Ｉ
）、　ｈ（ｘ＋工＋１）、・・・、　ｈ　（ｉ、ｎ）を
通過する経路。

ｈ（ｋ、ＩＩＩ）、ｖ（ｋ＋１．ＩＩＩ）、ｖ（ｋ＋２
．ＩＩＩ）。

−、ｖ（ｉ、ＩＩＩ）、ｈ（ｉ、１＋２）、ｈ（ＬＩ＋
３）、・、ｈ（ｉ、ｎ）を通過する経路。

ｈ　（ｋ、Ｉ　＋１）−ｈ　（ｋ、Ｉ　＋　２Ｌ□＝−
ｈ　（ｋ９ｍ）、ｖ　（ｋ＋１、ｎ）、・・・、　ｖ　
（ｉ、ｎ）を通過する経路。一般的に（１−ｎ＋１）種
類の概略配線のパターンがある。

・Ｉ＝ｎの場合（第９図）　： ｖ（ｋ＋１．Ｉ）、　ｖ（ｋ＋２．Ｉ）、−、ｖ（ｉ、
Ｉ）を通過する経路。

ｈ（ｋ、Ｉ）、　ｖ（ｋ＋１．ｌ−１）、　ｖ（ｋ＋２
．ｌ−１）、−、ｖ（ｉ、ｌ−１）、　ｈ（ｉ、ｌ−１
）を通過する経路。

上記の２種類のパターンがある。

（ｃ）　ｓ（ｋ、Ｉ）とｓ（ｋ、Ｉ）との概略配線。

小領域ｇ（ｋ、Ｉ）　２１内で配線する（第１２図）。

小領域ｇ（ｋ、ｌ−１）　２２を経由して配線する（第
１３図）。

［概略配線操作２］では、次の評価関数を最小にするよ
うに概略経路の繰り返し改善を行なう。

評価関数の改善が行なわれなくなれば処理は終了する。

概略配線の評価関数： ｔｈ（ｋ、ｊ）　：　ｈ（Ｌｊ）を通過しｓ　（ｋ、ｊ
）のセルと接続しない配線の総数。

ｃｈ（ｋｔｊ）　：　ｇ　（ｋ、ｊ）を通過する配線の
総数。

く詳細配置〉 このプロセスでは、セル集合ｓ　（ｋｔｊＬ　ｊ＝１〜
Ｎ（すなわち、ウィンドウＷ（ｋ）内のセル集合）の詳
細な配置、スルーセルの挿入、スルー配線へのスル一端
子の割り付けを行なう。ここでの目的は、各チャネルに
おいて配線に使用するトラック数が最小になるようなセ
ル行をウィンドウＷ（ｋ）内に構成することである。こ
のプロセスの処理フローを第２４図に示す。詳細配置の
プロセスは、［詳細配置操作１］、［詳細配置操作２］
、［詳細配置操作３］の３つの操作からなる。

今、ｋレベルの処理を行なう場合を考える。各操作の詳
細を以下に示す。

［詳細配置操作１］ この操作では、後の処理の初期配置を行なう。

処理は、ウィンドウ内の各セル行ごとに独立に行ない、
セル行間の相関関係は考慮しない。

２３− セル集合ｓ（ｋｌｊ）を下記に示す３個の集合に分けて
セル行に配置する。

（ａ）セル集合ｓ（ｋ、ｊ）において、ｖ　（ｋ）を通
過する配線とのみ接続するセルの集合を５（ｋｌｊ）と
する。

（ｂ）セル集合５（ｋｌｊ）において、ｖ（ｋ＋１）を
通過する配線とのみ接続するセルの集合を５ｒ（ｋ、ｊ
）とする。

（ｃ）セル集合ｓ（ｋ、ｊ）から５ｉ（ｋ＋ｘＬ　５ｒ
（ｋｔｊ）を除いた集合をｓｍ（ｋ、ｊ）とする。

上記の３個の集合を次のように配置する。

（ａ）　５ｌ（ｋ、ｊ）のセルは、セル行３３ｒ（ｋ、
ｊ）の左に位置するように配置する。

（ｂ）　５ｒ（ｋ、ｊ）のセルは、セル行ｒ（Ｌｊ）の
右に位置するように配置する。

（ｃ）　ｓｍ（ｋ、ｊ）のセルは、セル行ｒ（Ｌｊ）の
中央に位置するように配置する。

第１４図に、これらのセル集合の配置位置の相対的な関
係を示す。５ｌ（ｋ、ｊ）は３０の位置に、５ｒ（ｋ、
ｊ）は３１の位置に、ｓｍ（Ｌｊ）は３２の位置に配置
される。

ただし、後の［詳細配置操作３］で配置改善を２４ 行なうので、それぞれのセルの詳細なＸ座標は簡単に決
める。

［詳細配置操作２］ この操作では、スルー配線４０に対してスルー端子４１
を割り当る処理、及びスルーセルの挿入の処理を行なう
。ここでの目的は、詳細な配線を行なったときに使用す
るトラック数が少なくなるようなセル配置が得られるよ
うに、スル一端子をスルー配線に割り当てること、及び
、必要に応じてスルーセルをセル行に対して挿入するこ
とである。

従来技術では、セルの詳細な配置が終了してからスルー
配線がその上に通過するセルを決定する処理や、スルー
セルの挿入の処理を行なう。しかし、本発明では、スル
ー配線がどのセル上を通過するか、と言うこと、及び、
スルーセルの挿入するか否か、と言うことをあらかじめ
決定しておいてからセルの詳細な配置を行なう。このこ
とによりスルーセルの挿入によるセル位置のずれによる
弊害を防ぐことができ、また、スルー配線を考慮したセ
ル配置が可能となる。

ここで、次の条件を満たすセルからなる集合をｓｎ＋’
（ｋ、ｊ）とする。セル集合Ｓ（ｋ、ｊ）に属するセル
において、セル上にスルー配線を通過させることができ
る領域を持ち、接続する配線がＶ　（ｋ）とＶ（ｋ＋１
）を通過するものだけであり、かつ、Ｖ　（ｋ）を通過
する配線の総数とＶ（ｋ＋１）を通過する配線の総数が
同一である。

ｓｍ’　（ｋ、ｊ）のセル上のスル一端子を゛′優先ス
ルー端子４２”と呼ぶことにする。スルー配線には、″
優先スル一端子″を優先して割り当てる。なぜなら、ｓ
ｍ’　（ｋ、ｊ）に属するセルは、セル行ｒ　（ｋｌｊ
）のどの位置に配置されても、ウィンドウ内で使用する
トラック長に変化を与えない。従って、スル一端子に接
続したスルー配線が使用するトラック長のみを最小にす
るようにセルを配置すればよいことになる。簡単な例を
第１７図、第１８図に示す。

これらはウィンドウ内の隣接する２つのセル行表わした
概略図である。この図において４２は優先スル一端子、
４０はスルー配線である。この場合、４４のセル位置を
第１７図に示す位置から第１８図に示す位置に移動させ
ることだけで、ウィンドウ内で使用するトラック長を削
減することができる。第１５図、第１６図にスルー配線
を優先スル一端子以外のスル一端子に接続した場合の例
を示す。この場合、４３のセルを第１５図に示す位置か
ら第１６図に示す位置へと移動することだけではウィン
ドウ内で使用するトラック長の削減には必ずしも貢献し
ない。

この例で示すように優先スル一端子以外のスルー端子を
スルー配線に割り当てた場合、ウィンドウ内の使用トラ
ック長を削減する処理の手間が複雑になる。

次の（ト）〜（３）のステップで処理を行なう。

■　スルー配線を１本選ぶ。

■　スルー配線が通過するセル行から１個ずつスル一端
子を取りだし、割り当てる。

割り当ては、次の条件下で行なう。

（ａ）優先スル一端子の中で未使用のものがあれば、そ
れを優先して割り当てる。もし未使用ものがなければ、
ｓｌＩ′（ｋ、ｊ）以外のセル上のスルーセルを割り当
てる。もし未使用のスル一端子７− が全くなければセル行ｒ　（ｋ、ｊ）にスルーセルを挿
入し、スルーセル上のスル一端子を割り当てる。後の［
詳細配置操作３］で配置位置の改善を行なうのでスルー
セルのＸ座標は簡単に決める。

（ｂ）セル行ｒ　（ｋｔｊ−１）又はｒ（ｋ、ｊ＋１）
に割り当てられたスル一端子が優先スル一端子でなく、
かつ、ｒ　（ｋ、ｊ）に未詳の優先スル一端子がなけれ
ば、ｒ（ｋ、ｊ）にスルーセルを挿入し、スルーセル上
のスル一端子を割り当てる。後の［詳細配置操作３］で
配置位置の改善を行なうのでスルーセルのＸ座標は簡単
に決める。

（３）スルー配線に割り付けられたスル一端子は使用済
みとして登録し、他のスルー配線には割り付けない・ 以上の処理を全てのスルー配線に対し行なう。

［詳細配置操作３］ この操作では、ウィンドウ内のセル行の仮装配線長を最
小にするようにセル配置の改善を行なう。

ここで言う仮想配線長とは、第１９図、第２０図に示２
８− す如く配線１本に対してトラック１本を割り当てた時の
トラック長である。また、スルー配線は、［詳細配置処
理２］で仮想端子に割り当てられているので、一般の配
線と同一に扱う。

配置改善の評価関数として次のものを用いる。

Ｉ　（ｉ、ｘ）　　：チャネルｉに属する配線Ｘの仮想
線長・ 配置改善の処理は、この評価関数が最小になるようにセ
ルを移動することで行なう。ただしセルは同一のセル行
内のみで移動可能とする。異なるセル行に移動すること
はしない。また、セルの移動は、ウィンドウ内で閉じて
いる。

例えば文献二゛′標準セル方式ＶＬＳＩの配置手法とそ
の評価″″、小沢時典他、電子通信学会論文誌、’８４
／１０　Ｖｏｌ、Ｊ６７　　Ｄ　Ｎ＋１１０．　ｐｐ、
１１２３−１１３０に示されているような従来行なわれ
ている配置改善では、各セル行を独立に処理するために
、セル行間の配線を評価することができない。本来なら
ば、全てのセル行を一度に扱いセル行間の配線も含めた
評価でセル配置を行なった方が良好な配置結果を得るこ
とができるはずだが、問題が大きくなりすぎるために全
てのセル行を一度に扱うことは困難である。しかし、本
発明に示す方法では一度に扱うセルはウィンドウに含ま
れているものだけなので、セル行を全て同時に処理して
も問題が大きくなりすぎることはない。このためセル行
間の配線も考慮することができる。

本発明では、次のω〜（０に示すペア交換法を利用した
方法で配置改善を行なう。第２５図にその処理フローを
示す。なお、第１９図、第２０図に処理の例を示す。第
２０図は、第１９図に示すセルＡ５０とセルＢ５１を交
換することにより評価関数が減少したことを示す例の図
である。

■　ウィンドウ内のセル列の中から、セル列をランダム
に選ぶ。今選ばれたセル列をｒ　（ｋｌｊ）とする。

（２１ｒ（ｋ、ｊ）の中からランダムにセルを２個選ぶ
。そのセルをｓｌ、　ｓ２とする。

■　ｓｌ、　ｓ２の位置を交換する。交換後のセル行を
ｒ′（ｋｔｊ）とする７９゜ （イ）　セルの交換後の評価関数を計算する。

■　セルの交換によって評価関数が減少していればｒ　
’　（ｋｌｊ）→ｒ（ｋ、ｊ）とする。増大していれば
ｓｌと８２の位置を元にもどす。

０（１）〜０の処理を評価関数の改善が見られなくなる
まで繰り返す。

〈詳細配線〉 このプロセスではウィンドウ内のセル間の配線を行なう
。ウィンドウ内のスルー位置は“スルーの位置決めプロ
セス”で決定されているので、配線は各チャネルごとに
独立して行なうことができる。ただしウィンドウの左端
Ｖ（ｋ）までの配線は終了しているのでＶ（ｋ）からチ
ャネル配線を続行し、ウィンドウ右端Ｖ（ｋ＋１）まで
行なうことになる。モデルとしては、３方向の端子の位
置が固定で１方向の端子位置が不固定の領域に対する配
線問題となる。このような領域に対する配線手法として
種々のものが考えられるが、本実施例では１− ’ｇｒｅｅｄｙ’　ｒｏｕｔｅｒと呼ばれる手法を用い
る。この手法の詳細はＲｅｖｅｓｔ、　Ｒ，Ｌ、、ａｎ
ｄ　Ｃ，Ｍ、Ｆｉｄｕｃｃｉａ、　Ａ’ｇｒｅｅｄｙ’
　ｃｈａｎｎｅｌ　ｒｏｕｔｅｒ　ｉｎ　Ｐｒｏｃ、　
１９ｔｈ　ＤｅｓｉｇｎＡｕｔｏｍａｔｉｏｎ　Ｃｏｎ
ｆ、、　ｐｐ、４７５−４８１．　Ｊｕｎｅ　１９８２
．に示されている。上記文献の手法は、１個のチャネル
を対象にし、チャネルを左から右ヘスイープラインを移
動させながら（スイープラインより左の領域の配線を完
了させながら）配線をおこなう。

従って、本発明のウィンドウ内の配線では、チャネルの
配線がｌｋ）　１５まで完了している。すなわちＶ　（
ｋ）までスイープラインが移動し終わっていると考え、
さらにＶ（ｋ＋１）１６までスイープラインを移動させ
ると考えることによって’ｇｒｅｅｄｙ’ｒｏｕｔｅｒ
を利用することができる。

〔発明の効果〕

以上説明したように、本発明によれば配置、配線処理を
平行して行なうことが可能となり、より集積度の高いレ
イアウト結果を得ることができる。

【図面の簡単な説明】 ３２− 第１図は本発明の一実施例の処理フローを示す図、第２
図は本発明によるレイアウト設計を説明するための図、
第３図は第２図よりさらに処理が進んだ状態を示す図、
第４図はチップ領域の分割を説明するための図、第５図
は小領域を説明するための図、第６図〜第１３図は概略
配線の経路を説明するための図、第１４図は初期配置を
説明するための図、第１５図〜第１８図はスルー配線に
スルー端子を割り付ける処理を説明するための図、第１
９図、第２０図はセル間の仮想配線及びセルの配置改善
処理を説明するための図、第２１図は配置修正処理の処
理フローを示す図、第２２図は概略配線処理の処理フロ
ーを示す図、第２３図は概略配線処理における繰り返し
改善部の処理フローを示す図、第２４図は詳細配置処理
の処理フローを示す図、第２５図は詳細配線処理の繰り
返し改善部の処理フローを示す図である。 図において、 １０・・・ウィンドウ、　　　１１・・・確定領域、１
２・・・不確定領域、　　　１３・・・カットライン、
１４・・・小領域、 ４０・・・スルー配線、 ４１・・・スル一端子、 ４２・・・優先スル一端子。

Claims (1)

【特許請求の範囲】
1. 回路素子をチップ領域内の複数の帯状領域に配置し回路
   素子端子の結線要求を満たす配線を決定する際に、前記
   チップ領域内に前記回路素子の配置・配線が決定された
   配置・配線決定領域と未だ回路素子の配置・配線が決定
   されていない配置・配線未決定領域を持ち、前記配置・
   配線決定領域の配置・配線情報をもとにして前記配置・
   配線未決定領域の回路素子の概略配置を修正し、前記配
   置・配線未決定領域内に前記帯状領域の長手方向と直交
   する方向に前記複数の帯状領域に渡る配置・配線予定領
   域を決定し、この配置・配線予定領域内の前記回路素子
   の詳細配置を決定すると共に、前記配置・配線予定領域
   内の前記回路素子間の配線を決定し、配置・配線決定領
   域及び詳細配置及び配線が決定された前記配置・配線予
   定領域を新たに配置・配線決定領域として登録更新する
   ことを特徴とするレイアウト設計方法。