JPH0262676A - 概略配線装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はＬＳＩ自動レイアウトの概略配線装置に関し、
特にＬＳＩ内の概略配線を高密度化する概略配線装置に
関する。

〔従来の技術〕

従来、ＬＳＩの概略配線を行なう場合、配線すべき要素
（配線ネット）を１本ずつ取り出し、逐次その配線経路
を決定する方式が取られていた。

［文献　神戸、他：　“ア・プレイスメント・アルゴリ
ズム・フォー・ポリセル・エルニスアイ・アンド・イッ
ツ・工ヴアリュエーション”（ＡＰｌａｃｅｍｅｎｔ　
　ＡＩｇｏｒｉｔ、ｈｍ　　ｆｏｒ　　Ｐｏ１ｙｃｅｌ
ｌ　　ＬＳＩ　　ａｎｄ　　ｉｔｓ　　Ｅｖａｌｕａｔ
ｉｏｎ）、昭和５７年プロシーディング・デザイン・オ
ートメーション・コンファレンス（Ｐｒｏｃ。

Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ　Ｃｏｎｆｅｒｅ
ｎｃｅ）コ〔発明が解決しようとする課題〕 ＬＳＩ自動レイアウトにおける概略配線とは、第２図に
示す通り、ＬＳＩのセル領域とその間の配線要求（配線
ネット）が与えられたとき、それらの配線要求を満たす
配線経路を決定する事である。

従来の手法では、配線ネットを１本ずつ順に処理するた
め、配線の順序によっては、先に引いた配線（例えば、
第２図におけるネット１）が後がら引こうとする配線（
同図、ネット２）の障害となり、ＬＳＩのチップ面積を
増加させるという問題点を有していた。

本発明の目的は二局所的°な配線の１手法であるチャネ
ル配線手法［文献　吉相：　゛″エヒイシエントアルゴ
リズム・フォー・チャネル・ルーティング’　　（Ｅｆ
ｆｉｃｉｅｎｔ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｃｈ
ａｎｎｅｌ　Ｒｏｕｔｉｎｇ）　、昭和５７年アイ・イ
ー・イー・イー・トランザクション・コンピュータ・エ
イディト・デザイン・ボリウム・シー・ニー・デイ−１
ナンバー　１　（ＩＥＥＥ　Ｔｒａｎｓ、　Ｃｏｍｐｕ
ｔｅｒ−Ａｉｄｅｄ　Ｄｅｓｉｇｎ、Ｖｏｌ。

ＣＡＤ−Ｉ　Ｎｏ、１）　］を応用する事により、配線
ネットの処理をまとめて行うことによって高密度な配線
を実現する概略配線装置を提供することにある。

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

本発明の概略配線装置は、ネット接続情報を格納するネ
ット接続情報記憶装置と、セル領域間の相対位置関係を
格納するセル領域相対位置記憶装置と、上下制約グラフ
を格納する上下制約グラフ記憶装置と、チャネル配線ア
ルゴリズムを実行するチャネル配線処理装置と、・前記
各装置を用いてＬＳＩ内の配線を実行する制約装置を含
んで構成される事を特徴とする。

〔作用〕

一般に、配線ネット２個以上の端子を接続するが、ここ
では、各配線ネットは２端子を結ぶよう分解されている
ものとする。また、各ネットはセル上を垂直方向に自由
に通過できるものとする。

このようなネット集合を、Ｎ＝　＋ｎｌ　ｌ　ｎｚ・・
・）とし、ネットｎ１の接続する端子が属するセルの行
番号をｌｉ、ｕｉ（ｌｉ≦ｕｉ）とする。

このとき、次の条件を満たす各ネットの水平成分の通過
する配線チャネルｃｉを決定する。

条件１：１ｉ＝ｕｉのとき１１≦ｃｉ≦ｕｉ＋条件２：
Ｉｉ＜ｕｉのとき１１＋１≦ｃｉ≦Ｕ〔実施例〕 次に、本発明について図面を参照して説明する。

第１図は本発明の概略配線装置の一実施例を示すブロッ
ク図である。

同図において、ネット接続情報記憶装置１（装置１）は
ネット接続情報を、セル領域相対位置記憶装置２（装置
２）はセル領域間の相対位置関係をそれぞれ格納する。

上下制約グラフ記憶装置３は、上下制約グラフを格納す
る。チャネル配線処理装置４は、チャネル配線アルゴリ
ズムを実行する。制約装置５は、前記各装置を用いてＬ
ＳＩ内の配線を実行する。

上下制約グラフの内容を第３図、第４図を用いて説明す
る。このグラフの各ノードは、セル領域または配線ネッ
トの水平成分に対応する。また、ノードｉからノードｊ
に向うアークは、ノードｉがノードｊより上部に位置す
る事をしめす。

第３図の例では、ネットａは上記条件２に該当し、チャ
ネル領域ｊからｉの間で配線されるため、上下制約グラ
フ上では、セル領域ｉに対応するノードからネットａに
対応するノートに向かう枝およびネットａに対応するノ
ードからセル領域ｋに対応するノードに向う技がつけら
れている。

同様に、ネットｂについては、条件１に該当するためネ
ットｂに関して２本の枝がつけられている。

続いて、本発明の概略配線装置の動作を説明する。

ステップ１：各配線ネット、セル領域相対位置を装置１
、装置２にそれぞれ読み込む。

ステップ２：装置１、装置２の内容から上下制約グラフ
を製作する。

ステップ３：上記、上下制約グラフにたいして、チャネ
ル配線処理装置よりチャネル配線アルゴリズムを適用し
、各ネットの水平線分を配線するチャネル領域を計算す
る。

ステップ４：各ネットの水平線分の通過するチャネル領
域およびそのネットの接続するセル領域の間にネットの
垂直成分を配線する。

〔発明の効果〕

以上述べたとおり、チャネル配線アルゴリズムを用いる
事により、上記条件１．２を満たし、がつ高密度な配線
を実現する効果がある。

【図面の簡単な説明】

第１図は本発明の概略配、線装置の一実施例を示すブロ
ック図、第２図はセル領域、配線チャネルおよび配線ネ
ットの説明図、第３図および第４図は上下制約グラフの
説明図である。 １・・・ネット接続情報記憶装置、２・・・セル領域相
対位置記憶装置、３・・・上下制約グラフ記憶装置、４
・・・チャネル配線処理装置、５・・・制御装置。

Claims (1)

【特許請求の範囲】
1. ネット接続情報を格納するネット接続情報記憶装置と、
   セル領域間の相対位値関係を格納するセル領域相対位置
   記憶装置と、上下制約グラフを格納する上下制約グラフ
   記憶装置と、チャネル配線アルゴリズムを実行するチャ
   ネル配線処理装置と、前記各装置を用いてＬＳＩ内の配
   線を実行する制約装置を含んで構成される事を特徴とす
   る概略配線装置。