JPH0212918A

JPH0212918A - 半導体集積回路の配線方法

Info

Publication number: JPH0212918A
Application number: JP16431588A
Authority: JP
Inventors: Yasuo Matsuda; 松田　庸雄
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1988-06-30
Filing date: 1988-06-30
Publication date: 1990-01-17

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、半導体集積回路の配線方法に関し、特に電子
計算機を用いた自動配線処理に関する。

〔従来の技術〕

半導体集積回路の配線設計の計算機による自動化は、近
年顕著なる進歩を見せており、集積回路のチップ上の配
線設計は高速に、かつ高信頼度に実行可能となっている
。しかしながら、現在の自動化の難点として、周辺回路
への配線設計が挙げられる。一般に集積回路のチップは
、第５図（ａ）、（ｂ）に示すように、所望の論理機能
を実現するための複数の内部ブロック１７とそれらの間
を接続するための配線領域からなる内部領域１２と、チ
ップと外部とのインタフェースをとるための、パッドを
含む入出力回路ブロック１８からなる外部領域１９から
なる。内部領域１２の端子１０はその周辺上に存在し、
外部領域１９の端子１０’は外部領域の内側の境界（外
部領域辺）１１上にある。内部領域と外部領域の間の領
域１３を周辺配線領域と呼び、この領域内で内・外部領
域間の配線が接続される。この様な周辺配線領域内の配
線設計を電子計算機により自動化する方法として、従来
チャネル配線手法と迷路法が用いられている。チャネル
配線手法は、周辺配線領域１３を第６図（ａ）に示すよ
うに４つのチャネル領域（以下チャネルと略記）３０，
３１゜３２．３３に分け、各チャネル毎に配線径路１６
を決定して配線を行なうもので非常に効率良く設計でき
る。しかしながら、第６図（ｂ）のように、チャネルコ
ーナ部の外部領域側の２辺に端子１０が存在する場合、
この手法は適用できないことがわかっている。この場合
コーナ部だけを取り出した領域（スイッチボックス領域
と呼ぶ）３４に特殊なルールを適用する。

第７図を用いて説明する。図中において今接続すべきネ
ットをａ、ｂ、ｃとし、同一文字をもっている端子間を
接続するものとする。まずチャネル３０及び３３が配線
され、次にスイッチボックス領域内の配線が行なわれる
（第７図（ａ））。

簡単のために一層配線の例を示している。ここで、問題
となるのは、チャネル３０及び３３内での配線は自由に
行なわれるので、ａ、ｂ、ｃのネットの配線が、スイッ
チボックス領域３４に接する位置が前もって判らないこ
とである０例えば第７図の（ｂ）のように配線されると
、ネットａは未配線が残ってしまう。これは、本来連続
領域である周辺配線領域を、複数のチャネルとスイッチ
ボックス領域に分割して扱うために生じている。このよ
うな欠点のないのが迷路法である。この迷路法は、チッ
プ全面の座標点の状態をグリッドマツプと呼ばれるデー
タ構造に格納しておき、各信号線の配線を行う際グリッ
ド・マツプの座標点の状態を確認しながら径路を見つけ
る方法である。しかしながら、この方法はグリッドマツ
プを格納する記憶領域が非常に大きくなり、かつ、チッ
プ全面を探索するため非常に計算機時間も膨大となる。

これは、第５図（ｂ）でも明らかなように、周辺配線領
域は面積としては非常に狭い領域にもかかわらず、チッ
プ全面の状態を記憶しているためである。

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

上述した従来の配線手法は、周辺配線領域を複数の配線
領域に分割するために分割された領域間に不都合が生じ
たり、本来周辺配線領域だけを扱うべきところをチップ
全体として扱わざるを得ないため膨大な計算機時間や記
憶容量を必要とするという欠点がある。

本発明は、本来扱うべき周辺配線領域を分解することな
く、しかも周辺配線領域だけを扱って配線径路を決定し
、上述の問題点を解決することを目的としている。

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

本発明の半導体集積回路の配線方法は、周辺上に端子位
置をもつ第１の領域内に周辺上に端子位置をもつ第２の
領域が完全に包合されるように配置された２つの領域の
差集合領域（第３の領域）を抽出する工程と、第３の領
域を矩形領域に変換する工程と、矩形領域内にて配線径
路を決定する工程と、矩形領域にて決定された配線径路
を第３の領域内の座標系に変換する工程とを有する構成
となっている。

〔実施例１〕次に本発明について図面を参照して説明する。

第１図は本発明の一実施例のフローチャート図である。

領域抽出処理１は、与えられた２つの矩形領域（チップ
の内部領域（第２の領域）と、外部領域の内側の辺で囲
まれる領域（第１の領域）からその差集合の領域（周辺
配線領域（第３の領域））を抽出する処理を行い、矩形
変換処理２は周辺配線領域を矩形領域に変換する処理を
行い、配線領域３は変換された矩形領域内ですべての信
号線の配線径路を決定し、座標変換処理４は、求められ
た配線径路を元の周辺配線領域内の座標系に変換する。

このフローチャートに従う処理の概念図を第２図に示す
。まず、第２図（ａ）に示すような２矩形領域（内部領
域１２と外部領域辺１１で囲まれた領域）が与えられる
と領域抽出処理１により第２図（ｂ）の周辺配線領域１
３を計算する。次に周辺配線領域１３を、左下点を出発
し、下辺→右辺→上辺→左辺の順序に連続領域となるよ
うな矩形領域１４を矩形変換処理２により求める（第２
図（Ｃ））、次に、矩形領域１４内で配線処理３により
配線径路１５を決定した後（第２図（ｄ））、第２図（
ｅ）のように配線結果の元の周辺領域１３への逆変換を
座標変換処理４により行う。

領域抽出処理１と矩形変換処理２にグいて第３図を用い
て詳細に説明する。外部領域の横辺の長さをＸ、縦辺の
長さをＹとし、内部領域の横辺の長さをＸ、縦辺の長さ
をｙとする。領域抽出処理１では、外部領域の配線原点
（第３図（ａ）左下点座標）を（０，Ｏ）とし、内部領
域の配置座標（外部領域の配置原点（０，Ｏ）に対する
相対座標）として（Ｘｉ　、　Ｙｔ　）が与えられたと
き、外部領域及び内部領域の４隅の座標を決定すると共
に、各端子位置の座標を決定する。外部領域に関しては
、入力された座標をそのまま用い、内部領域については
内部領域の原点座標（左下点）からの座標（ｓ、ｔ）を
（ｓ＋Ｘ１　、ｔ＋Ｙ１　）に変換することで容易に得
ることが出きる。したがって、内部領域の右上面（Ｘ２
．Ｙ２）は（Ｘ１＋ｘ、Ｙｌ　＋ｙ）となる。この結果
（第３図（ａ））を入力として次に矩形変換処理２を実
行する。第３図（ａ）に示す如く、周辺配線領域１３の
４隅から内部領域１２の４隅に対角線上に分割線２０を
入れる。左下隅の分割線を左端として、分割された周辺
領域を下辺、右辺、上辺、左辺の順に、周辺配線領域の
外側の線が一直線上になるように並らべる。そして隣接
する分割領域の同一座標（分割線上の座標）点間に同一
座標ポインタ２１を記述する。これにより、与えられた
周辺配線領域をあたなも連続した矩形領域１４として扱
うことができる。本例では簡単のため周辺配線領域の幅
を４辺とも同一の幅ａとして説明している。この矩形変
換時に各端子座標も第３図（ｂ）のように変換される。

この変換は容易に実現できる。この領域内で配線処理３
が配線した結果を第３図（Ｃ）に示す。この配線処理は
従来のチャネル配線法や迷路法で容易に実現できる。最
後に第３図（ｃ）の配線径路１５を第３図（ａ＞に示す
配線径路１６に座標変換処理４を行うが、これは矩形変
換処理２の端子座標変換の逆変換を行うもので、容易に
実現できる。

〔実施例２〕第４図は本発明の実施例２を示す。処理フローは実施例
１の第１図と同じであるが、実施例１と異なるのは、第
４図（ａ）に示すように周辺配線領域１３の各辺の幅を
任意にしたことで、実施例１の処理フローと同一でより
一般的な周辺配線領域を扱えるようにしたものである。

この場合、矩形変換処理２により生成される周辺配線領
域が第４図（ｂ）に示すように複合矩形領域２２となる
。この複合矩形領域２２を得た後は実施例１と同様にし
て複合矩形領域２２に配線処理を施し、第４図（ｃ）の
結果を得た後、これを座標変換処理により最終結果を得
る。

〔発明の効果〕

以上説明したように本発明は、周辺配線領域を連続な矩
形領域として扱うことができるため、分割して扱うこと
により生ずる不都合を避けると共に、扱うデータ規模を
大幅に減少することができ、ひいては高速処理を可能に
する。

尚、実施例では第１．第２の領域はいずれも矩形の場合
について説明したが、第１．第２の領域が任意の多角形
であっても本質的には何ら変るところがなく、本発明が
適用できる。

【図面の簡単な説明】

第１図は本発明の処理のフローチャート図、第２図は処
理の概念図、第３図は実施例１の座標変換方法を説明す
る詳細図、第４図は実施例２の座標変換方法を説明する
詳細図、第５図は集積回路チップの構造図、第６図及び
第７図は従来の配線方法を示した図である。１・・・領域抽出処理、２・・・矩形変換処理、３・・
・配線処理、４・・・座標変換処理、１０・・・端子、
１１・・・外部領域辺、１２・・・内部領域、１３・・
・周辺配線領域、１４・・・矩形領域、１５．１６・・
・配線径路、１７・・・内部ブロック、１８・・・入出
力回路ブロック、１９・・・外部領域、２０・・・分割
線、２１・・・同一座標ポインタ、２２・・・複合矩形
領域、３０・・・チャネル、３１・・・チャネル、３２
・・・チャネル、３３・・・チャネル、３４・・・スイ
ッチボックス領域。

Claims

【特許請求の範囲】

周辺上に端子位置をもつ第１の領域内に周辺上に端子位
置をもつ第２の領域が完全に包含されるように配置され
た前記２つの領域の差集合となる第３の領域を抽出する
工程と、前記第３の領域を矩形領域に変換する工程と、
前記矩形領域内にて配線径路を決定する工程と、決定さ
れた配線路を前記矩形領域の座標系から前記第３の領域
内の座標系に変換する工程とを備えていることを特徴と
する半導体集積回路の配線方法。