JPH01308046A - 半導体集積回路装置の配線方法 - Google Patents
半導体集積回路装置の配線方法Info
- Publication number
- JPH01308046A JPH01308046A JP63138444A JP13844488A JPH01308046A JP H01308046 A JPH01308046 A JP H01308046A JP 63138444 A JP63138444 A JP 63138444A JP 13844488 A JP13844488 A JP 13844488A JP H01308046 A JPH01308046 A JP H01308046A
- Authority
- JP
- Japan
- Prior art keywords
- edge
- terminal
- edges
- terminals
- wiring
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の目的〕
（産業上の利用分野）
本発明は、ポリセル方式の論理ブロックの内部レイアウ
トにおいて、ポリセル間結線径路をコンピュータを用い
た自動処理により決定する半導体集積回路装置の配線方
法に関する。
トにおいて、ポリセル間結線径路をコンピュータを用い
た自動処理により決定する半導体集積回路装置の配線方
法に関する。
（従来の技術）
ポリセル方式による半導体集積回路チップの概１ＩＩ８
構成を第７図に示す。チップ上は、素子領域である複数
のセル４が配列されたセル行】と、チャネルと呼ばれる
各セル行間にある配線領域２と、および周辺に設けられ
た入出力回路領域３とに分けられる。
構成を第７図に示す。チップ上は、素子領域である複数
のセル４が配列されたセル行】と、チャネルと呼ばれる
各セル行間にある配線領域２と、および周辺に設けられ
た入出力回路領域３とに分けられる。
この様なポリセル方式半導体集積回路装置において、コ
ンピュータを用いた自動配線処理により配線レイアウト
を決定するときには、配線領域の面積を最小にし、きた
各配線長を最小にすることが目標となる。一般的に配線
処理は大きく２つに分かれ、端子の引き出し方向や、セ
ル行をまたぐ配線（スルー配線）の選択を含む大まかな
配線径路の決定を行なう概略配線処理と、４！［配線の
情報に基づいて、実際に配線線分の割り付けを行なう詳
細配線処理からなる。この２つの処理のうち、集積度の
観点から大きな影響を与えるのは概略配線処理の方であ
る。従って、効率のよい配線を行なえるようセル端子か
らの配線方向の決定をしながら概略径路を決定すること
が重要である。
ンピュータを用いた自動配線処理により配線レイアウト
を決定するときには、配線領域の面積を最小にし、きた
各配線長を最小にすることが目標となる。一般的に配線
処理は大きく２つに分かれ、端子の引き出し方向や、セ
ル行をまたぐ配線（スルー配線）の選択を含む大まかな
配線径路の決定を行なう概略配線処理と、４！［配線の
情報に基づいて、実際に配線線分の割り付けを行なう詳
細配線処理からなる。この２つの処理のうち、集積度の
観点から大きな影響を与えるのは概略配線処理の方であ
る。従って、効率のよい配線を行なえるようセル端子か
らの配線方向の決定をしながら概略径路を決定すること
が重要である。
ところで、従来の概略配線処理におけるセル端子の引き
出し方向の決定では、ネットグラフを作成して極大木（
ＳｐａｎｎｉｎＨＴｒｅｅ）を作成することにより行な
うものが多い。このネットグラフ−にでの極大木作成の
例として、ネットグラフを構成する各エツジに重みを与
え１重みの小さいものから処理を行なう方法がある（文
献二に、Ａｏｓｈｉｍａ ＆ ＩＥ。
出し方向の決定では、ネットグラフを作成して極大木（
ＳｐａｎｎｉｎＨＴｒｅｅ）を作成することにより行な
うものが多い。このネットグラフ−にでの極大木作成の
例として、ネットグラフを構成する各エツジに重みを与
え１重みの小さいものから処理を行なう方法がある（文
献二に、Ａｏｓｈｉｍａ ＆ ＩＥ。
Ｓ、Ｋｕｌ＋、 ”ＭＵＬＴＩ−ＣＨＡＮＮ［ＥＬ Ｏ
ＰＴＩＭＩＺＡＴＩＯＮ ＩＮ ＧＡＴＥ−ＡＲＲＡＹ
ＬＳＴ ＬＡＹＯＵＴ” １９８３．ＩＥＥＥ）。こ
の方法では、同一ネットの端子で、チャネル毎に端子の
Ｘ座標の近いもの回申を結ぶエツジを左から右に張って
いくことによりグラフを作り各エツジには重みを与える
。この時、張られたエツジの情報を基に極大木作成処理
ではエツジの重みの小さいものから順番にエツジと端子
を選び冗長なエツジは削除し、全ての端子が接続された
ら処理を終了する。
ＰＴＩＭＩＺＡＴＩＯＮ ＩＮ ＧＡＴＥ−ＡＲＲＡＹ
ＬＳＴ ＬＡＹＯＵＴ” １９８３．ＩＥＥＥ）。こ
の方法では、同一ネットの端子で、チャネル毎に端子の
Ｘ座標の近いもの回申を結ぶエツジを左から右に張って
いくことによりグラフを作り各エツジには重みを与える
。この時、張られたエツジの情報を基に極大木作成処理
ではエツジの重みの小さいものから順番にエツジと端子
を選び冗長なエツジは削除し、全ての端子が接続された
ら処理を終了する。
しかし、この方法では、信号の流れを考えておらず、ま
た、エツジの重みの小さいものから処理を行なうため、
連続してエツジを選ぶとは限らず。
た、エツジの重みの小さいものから処理を行なうため、
連続してエツジを選ぶとは限らず。
全体的に最適に近い配線径路は得られにくい。
（発明が解決しようとする課題）
以りの様に、従来の方式では、エツジの重みのみ考慮し
て処理を行なうため、第６図に示したような配線イメー
ジでのΔ−りとＤ−Ｇ、または、ＤＧとＧ−Ｊのように
セル行をはさんでの幹線重複が起こり、結果的に配線長
を長くシ、配腺領域を増してしまい集積度の低下を招く
という問題があった。
て処理を行なうため、第６図に示したような配線イメー
ジでのΔ−りとＤ−Ｇ、または、ＤＧとＧ−Ｊのように
セル行をはさんでの幹線重複が起こり、結果的に配線長
を長くシ、配腺領域を増してしまい集積度の低下を招く
という問題があった。
（課題を解決するための手段）
本発明では、概略配線でセル端子の配線引き出し方向を
決めるに際し、各端子間を接続するエツジをチャネル毎
に抽出し、さらにセル行１−を通過するエツジも設ける
。また、エツジを選んで端子の決定を行なっていくν１
程で、不要となった端子、およびエツジを遂次消去し、
それに伴なって新たにエツジを発生させる。
決めるに際し、各端子間を接続するエツジをチャネル毎
に抽出し、さらにセル行１−を通過するエツジも設ける
。また、エツジを選んで端子の決定を行なっていくν１
程で、不要となった端子、およびエツジを遂次消去し、
それに伴なって新たにエツジを発生させる。
（作用）
本発明によれば、ネットグラフヒのエツジを動的に追加
削除しながら配線径路を決めるため、無駄な幹線を生じ
させないように端子引き出し方向を決定することができ
る。
削除しながら配線径路を決めるため、無駄な幹線を生じ
させないように端子引き出し方向を決定することができ
る。
（実施例）
以下５本発明の詳細な説明する。第１図に本発明のフロ
ーチャートを示す。スタート後、同一ネットの全ての端
子に対し、チャネル毎に、そのチャネルの左の端子から
順にＸ座標の一番近い端子にエツジを張ってい＜ （Ａ
ｌ、Ａ２）。次に出力力端子の面しているチャネルの１
つ下と一ヒのチャネルをサーチして、 ｆｈｘ座標の
近い端子とエツジを張る（Ａ３）。このエツジは、セル
行上を通力１°コ１するエツジ（以下スルーエツジ）で
ある。ここまでの処理で初期のネットグラフが作成され
る。
ーチャートを示す。スタート後、同一ネットの全ての端
子に対し、チャネル毎に、そのチャネルの左の端子から
順にＸ座標の一番近い端子にエツジを張ってい＜ （Ａ
ｌ、Ａ２）。次に出力力端子の面しているチャネルの１
つ下と一ヒのチャネルをサーチして、 ｆｈｘ座標の
近い端子とエツジを張る（Ａ３）。このエツジは、セル
行上を通力１°コ１するエツジ（以下スルーエツジ）で
ある。ここまでの処理で初期のネットグラフが作成され
る。
続いて端子の引き出し方向の決定の処理に移る。
信号は一般的には１つの出力端子から多くの入力端子へ
と伝播していくので、出力端子を始点として決める（Ａ
４）。次に始点の端子を頂点として持つエツジのうち評
価値（重み）、一番車さいものを選ぶ（Ａ５）。そのエ
ツジを選んだことにより、別チャネルに引き出していた
エツジ、および、端子を削除し、削除したことにより接
続のないエツジが出る場合があるため、全て新しくエツ
ジを張り替えて、新しいネットグラフを作成する（八６
）。
と伝播していくので、出力端子を始点として決める（Ａ
４）。次に始点の端子を頂点として持つエツジのうち評
価値（重み）、一番車さいものを選ぶ（Ａ５）。そのエ
ツジを選んだことにより、別チャネルに引き出していた
エツジ、および、端子を削除し、削除したことにより接
続のないエツジが出る場合があるため、全て新しくエツ
ジを張り替えて、新しいネットグラフを作成する（八６
）。
エツジが新しく張り替えられた結果、エツジが残ってい
る時（まだ引き出し方向が未決定の端子がある時）（Ａ
８）は、既に決定した端子と接続しているエツジをサー
チして次の処理のエツジをもつ候補の端子としくＡ ９
）、そのエツジが存在する時はＡ５へ行き」−記の処
理を繰り返す。なお、エツジが新しく張られた結果、エ
ツジが残っていない時（全ての端子の引き出し方向が決
定したとき）には終了（ＥＮＤ）となる。
る時（まだ引き出し方向が未決定の端子がある時）（Ａ
８）は、既に決定した端子と接続しているエツジをサー
チして次の処理のエツジをもつ候補の端子としくＡ ９
）、そのエツジが存在する時はＡ５へ行き」−記の処
理を繰り返す。なお、エツジが新しく張られた結果、エ
ツジが残っていない時（全ての端子の引き出し方向が決
定したとき）には終了（ＥＮＤ）となる。
次に八６の処理についてさらに詳しく説明する。
第２図は端子引き出し方向が決定した時の不要な端子・
エツジの消去、およびエツジの張り替えのためのフロー
を示す。
エツジの消去、およびエツジの張り替えのためのフロー
を示す。
スタート後、まづ選ばれた端子の種類をサーチしくＰｌ
）、出力端子の場合には、別チャネルに引き出した選ば
れた端子と電気的に等価な端子を削除せず（Ｐ２）、出
力端子でない場合には削除する（Ｐ３）。続いてスルー
エツジを全て消去し、端子の引き出し方向決定処理のＡ
ｌ、Ａ２同様に残った端子の新たなエツジを張る（Ｐ４
）。次に前に選ばれた端子の在るチャネルの１つ下と上
のチャネルをサーチし、その端子と一番Ｘ座標の近い端
子との間にスルーエツジを張る（Ｐ５）。新しく張った
スルーエツジの端子と、それ以前に張ったスルーエツジ
の端子をサーチしくＰ６）、スルーエツジを張った先の
端子が同一の端子だったら評価値を比較し、評価値の良
い方のスルーエツジを残しくＰｌ）、同一の端子でない
場合には、新しく張ったスルーエツジも残しくＰ８）、
処理を終了する。
）、出力端子の場合には、別チャネルに引き出した選ば
れた端子と電気的に等価な端子を削除せず（Ｐ２）、出
力端子でない場合には削除する（Ｐ３）。続いてスルー
エツジを全て消去し、端子の引き出し方向決定処理のＡ
ｌ、Ａ２同様に残った端子の新たなエツジを張る（Ｐ４
）。次に前に選ばれた端子の在るチャネルの１つ下と上
のチャネルをサーチし、その端子と一番Ｘ座標の近い端
子との間にスルーエツジを張る（Ｐ５）。新しく張った
スルーエツジの端子と、それ以前に張ったスルーエツジ
の端子をサーチしくＰ６）、スルーエツジを張った先の
端子が同一の端子だったら評価値を比較し、評価値の良
い方のスルーエツジを残しくＰｌ）、同一の端子でない
場合には、新しく張ったスルーエツジも残しくＰ８）、
処理を終了する。
本発明の具体的な実施例を第３図〜第５図を用いて説明
する。
する。
第３図は同一ネットのセル行ヒの端子位置を示す図であ
る。第３図において、Ａ−ａ、Ｂ−ｂ、・・・は電気的
に等価な端子を示しており、Ｄ−ｄが出力端子とする。
る。第３図において、Ａ−ａ、Ｂ−ｂ、・・・は電気的
に等価な端子を示しており、Ｄ−ｄが出力端子とする。
第５図（ａ）はネットグラフ作成時の各エツジとその情
報（端子、端子存在チャネル。
報（端子、端子存在チャネル。
評価値）を表しており、第５図（ｂ）は各端子の対応と
、端子の引き出し方向のＬ下に引き出せるかの可否（双
方向の有無）ｔｘ座標、引き出し方向を表している。
、端子の引き出し方向のＬ下に引き出せるかの可否（双
方向の有無）ｔｘ座標、引き出し方向を表している。
第５図の情報より、フローに沿って第３図の端子の引き
出し方向の決定を行なうと、最初に端子りが選ばれ（Ａ
４）、端子りに接続のあるエツジのうち評価値の小さい
エツジ■が選ばれる（八６）。
出し方向の決定を行なうと、最初に端子りが選ばれ（Ａ
４）、端子りに接続のあるエツジのうち評価値の小さい
エツジ■が選ばれる（八６）。
その結果、端子Ｃが消え、新しいエツジが張られる（Ａ
７）。エツジはまだ残っているので、候補のエツジをサ
ーチしくＡ９）、処理を繰り返す６その結果の配線イメ
ージが第４図である。この図が示すように本発明では幹
線長の増加を抑えることができる。
７）。エツジはまだ残っているので、候補のエツジをサ
ーチしくＡ９）、処理を繰り返す６その結果の配線イメ
ージが第４図である。この図が示すように本発明では幹
線長の増加を抑えることができる。
以上述べたように本発明によれば、各ネットの出力端子
を始点として信号の流れに沿ってエツジを決定していく
点、スルーエツジを導入した点。
を始点として信号の流れに沿ってエツジを決定していく
点、スルーエツジを導入した点。
および、不要な端子を遂次消去するようにした点により
、幹線長の増大を抑えることができ、その結果、チップ
の集積度の向ｌ−を図ることができる。
、幹線長の増大を抑えることができ、その結果、チップ
の集積度の向ｌ−を図ることができる。
第１図は本発明の一実施例の処理フローを示す図、第２
図は第１図の不要な端子・エツジ削除およびエツジ張り
替えの部分の処理フローを示す図、第３図乃至第５図は
具体的な実施例でネットグラフの作成および端子引き出
し方向の決定を説明するための図、第６図は従来の方式
による配線イメージの図、第７図はポリセル方式半導体
集積回路チップの概略構成を示す図である。 １・・・セル行 ２・・・配線領域３・・・入
出力端子並びに入出力回路領域４ ・・・セル 代理人 弁理士 則 近 憲 佑 同 松山光之 第１図 第２図 第３図 第４図 （ＣＬ） 第５図 第６図 Ｊ 第７図
図は第１図の不要な端子・エツジ削除およびエツジ張り
替えの部分の処理フローを示す図、第３図乃至第５図は
具体的な実施例でネットグラフの作成および端子引き出
し方向の決定を説明するための図、第６図は従来の方式
による配線イメージの図、第７図はポリセル方式半導体
集積回路チップの概略構成を示す図である。 １・・・セル行 ２・・・配線領域３・・・入
出力端子並びに入出力回路領域４ ・・・セル 代理人 弁理士 則 近 憲 佑 同 松山光之 第１図 第２図 第３図 第４図 （ＣＬ） 第５図 第６図 Ｊ 第７図
Claims (1)
- 半導体基板に能動素子を備えたポリセルを並べてセル
行を構成し、セル行を複数個配列し集積して、その間に
必要に応じた配線パターンを施して所望の回路動作を実
現するポリセル方式の集積回路装置において、各ネット
の概略配線で径路の決定を行なうに際し、ネット毎に引
き出し方向未定の全ての端子をノードとするエッジをチ
ャネル毎にセル行方向の最近接端子間に張り、さらに、
出力端子にセル行をまたいでセル行方向の最近接の端子
とのエッジを張ることで初期のネットグラフを構成し、
そのネットグラフより、出力端子の端子をノードとする
エッジを選び、１つのエッジを決定する度に、不要とな
った端子、エッジを消去し、新しいエッジを追加張りか
えを行ない新しいネットグラフを構成し直し、既に決定
しているエッジのノードである端子を次のエッジ選択の
候補とし、エッジを選ぶ処理を行ない極大木を作成して
いき、最終的に残った極大木を概略配線として決定する
ことを特徴とする半導体集積回路装置の配線方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63138444A JPH01308046A (ja) | 1988-06-07 | 1988-06-07 | 半導体集積回路装置の配線方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63138444A JPH01308046A (ja) | 1988-06-07 | 1988-06-07 | 半導体集積回路装置の配線方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH01308046A true JPH01308046A (ja) | 1989-12-12 |
Family
ID=15222143
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63138444A Pending JPH01308046A (ja) | 1988-06-07 | 1988-06-07 | 半導体集積回路装置の配線方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH01308046A (ja) |
-
1988
- 1988-06-07 JP JP63138444A patent/JPH01308046A/ja active Pending
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5072402A (en) | Routing system and method for integrated circuits | |
| KR100201979B1 (ko) | 배선경로 처리방법과 배선경로 처리시스템 및 반도체집적회로 장치 | |
| US6353918B1 (en) | Interconnection routing system | |
| US5065355A (en) | Automatic routing method for LSI | |
| US4903214A (en) | Method for wiring semiconductor integrated circuit device | |
| JPH07319951A (ja) | 自動配線方法 | |
| Suaris et al. | A quadrisection-based combined place and route scheme for standard cells | |
| US6442740B1 (en) | Clock signal analysis device and clock signal analysis method | |
| US6766502B1 (en) | Method and apparatus for routing using deferred merging | |
| Bar-Yehuda et al. | Depth-first-search and dynamic programming algorithms for efficient CMOS cell generation | |
| US5701255A (en) | Cell generation method and cell generation system | |
| JPH01308046A (ja) | 半導体集積回路装置の配線方法 | |
| KR100576987B1 (ko) | 전자 소자 및 전자 장치의 설계 및 제조 방법 | |
| Kao et al. | Cross point assignment with global rerouting for general-architecture designs | |
| Wang et al. | Performance-driven interconnect global routing | |
| JPH03225862A (ja) | 電源幹線のレイアウト方法 | |
| Wu et al. | Antenna avoidance in layer assignment | |
| US11544438B2 (en) | Superconductive circuit splitter placement | |
| Venkataraman et al. | Determination of yield bounds prior to routing | |
| US20040153987A1 (en) | Method and system for connecting computer-generated rectangles | |
| JP3208014B2 (ja) | 配線経路調査装置および配線経路調査方法 | |
| JP3512757B2 (ja) | レイアウト設計における最適化方法 | |
| Hoffmann | Towards optimizing global MinCut partitioning | |
| JP2581401B2 (ja) | 集積回路配線装置及び方法 | |
| JPH0474454A (ja) | 半導体装置の配線方法 |