JPH09232434A - 自動引き剥がし再配線方法 - Google Patents

Abstract

(57)【要約】 【課題】半導体集積回路のレイアウト設計において、信
号端子を自動配線する際に、任意の配線方法で生じた未
配線の追加配線を、高速に行う。 【解決手段】既配線の周辺、及び、既配線上に線分を生
成する。生成した線分を用い、他の既配線との重複を許
して未配線ネットの配線経路を探索する。配線経路の探
索方法には、線分探索法を用いる。その際、他の既配線
との重複を最小にするために、既配線上に生成した線分
を選択する際には、１本をＮ本と数える。重複する配線
をすべて引き剥がし、空き領域に線分を生成する。次
に、引き剥がしたネットの再配線経路を、線分探索法を
用いて求める。すべての引き剥がしたネットの再配線経
路が求まれば、未配線ネットの配線経路を確定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は半導体集積回路のレ
イアウト設計における自動配線方法に関する。

【０００２】

【従来の技術】従来、半導体集積回路の自動配線方法と
して、迷路法や線分探索法が用いられている。

【０００３】迷路法は、配線領域を格子状のマス目に区
切り、各マス目に整数値のコストを与え、そのコストの
総和が最小になるように端子間の配線経路を探索する方
法である。迷路法は、配線の長さが最小になる配線経路
を求めることができる長所を持つ。しかし同時に、配線
領域すべてに対してマス目を持つ必要があり、必要メモ
リ量、及び、処理時間が非常に大きくなるという欠点を
持つ。

【０００４】線分探索法は、配線領域内に配線経路の候
補となる線分を発生し、線分数が最小になるように端子
間の配線経路を探索する方法である。迷路法に比べ、配
線長が長くなる傾向があるが、処理時間が少なく、メモ
リ量も小さいため、大規模な半導体集積回路の自動配線
に多く用いられている。

【０００５】いずれの方法も、配線を行う信号に順番を
設け、一つ一つの信号を順に配線してゆく。そのため、
順番が後の信号は、先に行われた配線（以下これを既配
線と呼ぶ）が障害となって配線できなくなる場合が生じ
る。これを未配線と呼ぶ。未配線を解消するために、障
害となる配線を引き剥がし、未配線信号の追加配線を行
った後に、引き剥がした信号の再配線を行う方法が一般
的に行われている。

【０００６】これまで、迷路法を用いた引き剥がし再配
線方法については、いくつかの方法が考案されている
（例えば、特願昭62−296674号明細書）。それらの手法
では、引き剥がしの対象となる配線を探索するため、ま
ず、既配線との重複を許して配線を行う。重複する配線
が最小になるように、既配線上のマス目のコストを、既
配線のないマス目よりも大きく設定する。そして、通常
の迷路法と同様に、コストの総和が最小になるように配
線経路を求める。求まった配線経路と重複する配線を引
き剥がした後に、引き剥がした信号について重複を許さ
ずに再配線を行う。この方法は、最初に未配線信号の配
線経路を完全に求めるため、未配線信号の追加が保証さ
れる。

【０００７】また、重複を許す配線経路を、迷路法を用
いずに簡単に求める方法が、特願平4−15733号明細書で
報告されている。この方法では、未配線の信号につい
て、対話的に配線経路を指定する。そして、与えられた
経路にある一定の幅を持たせた概略的な経路を自動で生
成する。概略的な経路内で、最短の経路をとるパターン
を複数通り作成し、その内から、既配線との重複が最も
少ないものを選択する。

【０００８】

【発明が解決しようとする課題】上述した従来技術の
内、迷路法を用いたものは、最も引き剥がす配線の少な
い配線経路を求めることができる。しかし、重複を許す
配線経路探索の処理時間の増大が実用上の問題となる。
通常の配線経路探索では、既配線の存在しない領域のみ
を対象にするのに比べ、既配線上も探索対象とすること
が、処理時間の増大を招く。また、迷路法を用いずに、
簡易的に重複する配線経路を求める方法は、重複を許す
配線経路探索の処理時間は少ないが、配線パターンが最
短経路に限定されているため、引き剥がす配線が多くな
る傾向がある。そのため、引き剥がした信号の再配線処
理時間が増大し、また、再配線に失敗しやすくなる。そ
こで、これらの問題を解決するため、引き剥がす配線を
最小とし、かつ、処理時間の少ない引き剥がし再配線方
法が必要となった。

【０００９】

【課題を解決するための手段】互いに配線で結ぶべき信
号端子の集合をネットと呼ぶ。あるネットの集合を、任
意の配線方法により配線した後に生じた未配線ネットに
ついて、以下の方法で追加配線を行う。

【００１０】まず、既配線の周辺、及び、既配線上に、
線分を生成する。線分は、線分探索法で経路探索する際
に、配線経路の候補となる。既配線の周辺に生成する線
分は、設計ルールで許される範囲で、最も既配線に近
い、上，下，左，右の位置に生成し、他の既配線と重複
しない範囲まで延長する。ここで設計ルールとは、半導
体製造技術の制約から決められるもので、各配線間に許
される最小間隔のことである。既配線上に生成する線分
は、既配線と同一座標上に生成し、他の既配線と重複し
ない範囲まで延長する。以下では、既配線の周辺に生成
する線分を重複を許さない線分，既配線上に生成する線
分を重複を許す線分と呼ぶ。

【００１１】次に、すべての未配線ネットについて、以
下の処理を実行する。

【００１２】まず、生成した線分を用いて、未配線ネッ
トの配線経路を探索する。探索手段には線分探索法を用
い、他の既配線との重複を許した配線経路を求める。こ
の時、他の既配線との重複を最小とするために、重複を
許した線分を選択する際には、１本をＮ本と数える。Ｎ
は、重複を許さない配線経路探索の際に選択する線分数
よりも十分大きい整数である。線分探索法は、選択する
線分の数が最小になるように配線経路を求める方法であ
るから、Ｎが通常の配線経路探索の時に比べて十分大き
ければ、求める配線経路は既配線との重複が最小にな
る。もし、配線経路が見つからなければ、次の未配線ネ
ットの処理に移る。

【００１３】次に、求まった配線経路と重複する配線を
すべて引き剥がす。配線を引き剥がして空いた領域に
は、配線と同一座標上に沿って、他の既配線と重複しな
い範囲まで延長した、重複を許さない線分を生成する。

【００１４】次に、引き剥がした配線のネットについ
て、他の既配線との重複を許さない配線経路を求める。
配線経路探索手段には、通常の線分探索法を用い、重複
を許した線分は選択しない。引き剥がしたネットの配線
経路がすべて求まれば、未配線ネットの配線経路を確定
する。もし、配線経路の見つからないネットがあれば、
線分、及び、既配線の状態を、重複を許した配線を行う
前の状態に回復する。さらに、配線経路の見つからなか
ったネットの、元の配線経路上の、重複を許した線分を
削除する。そして再び、重複を許した配線経路探索処理
に戻って、処理を繰り返す。同一未配線ネットに対する
繰り返しは、引き剥がしネットの再配線がすべて成功す
るか、または、重複を許した配線経路が見つからなくな
るまで、または、あらかじめ指定された回数に達するま
で行う。

【００１５】

【発明の実施の形態】図２を用いて、配線モデル、及
び、初期配線を行った後に生じる未配線の例を説明す
る。黒丸２０２〜２１３は、配線で接続すべき信号端子
を示している。各端子の内の、同一ネットの端子を、配
線領域２０１の中で配線しなければならない。端子２０
３と端子２０６、及び、端子２０４と端子２１１、及
び、端子205と端子２０７、及び、端子２０８と端子２
１０、及び、端子２０９と端子２１２、及び、端子２０
２と端子２１３は、それぞれ同一ネットである。

【００１６】これらの内、端子２０４と端子２１１のネ
ットは、未配線となっている。それ以外の信号端子を接
続している実線２１４〜２１８が、配線を表す。端子２
０３と端子２０６は配線２１４によって接続される。端
子２０５と端子２０７は配線２１５によって接続され
る。端子２０８と端子２１０は配線２１６によって接続
される。端子２０９と端子２１２は配線２１７によって
接続される。端子２０２と端子２１３は配線２１８によ
って接続される。

【００１７】水平方向の配線と垂直方向の配線は、配線
層が異なるため、異なるネットの配線が交差することが
できる。例えば、配線２１４と、配線２１５は、互いに
交差している。しかし、異なるネットが同一方向で重な
ることはできない。例えば、配線２１７と配線２１８の
水平方向の配線が、互いに重なることはできない。ま
た、ネットが異なり、かつ、同一方向の配線どうしは、
設計ルールで決められた最小間隔をあけなければならな
い。この例では、例えば、配線２１７と配線218の水平
方向の配線間隔、及び、端子２１２と端子２１３から垂
直に伸びる配線の間隔が、最小間隔を表している。端子
２０４と端子２１１のネットは、配線216、または配線
２１７、または配線２１８が障害となって、配線するこ
とができない。

【００１８】以下では、図２の未配線を例にとり、引き
剥がし再配線方法について、図１の流れ図に沿って説明
する。

【００１９】まず、配線領域２０１の中に、配線経路探
索で用いるための線分を生成する（１０１）。線分は、
既配線（２１４〜２１８）の周辺に重複を許さない線分
を、及び、既配線（２１４〜２１８）上に重複を許す線
分を生成する。既配線（２１４〜２１８）周辺に生成し
た線分３０１〜３１１を図３（ａ）に示す。既配線の周
辺に生成する線分は、設計ルールで許される範囲で、最
も既配線に近い、上，下，左，右の位置に生成し、他の
既配線と重複しない範囲まで延長する。例えば、配線２
１４の内の水平方向の配線の上に、線分３０１を生成す
る。線分３０１は、配線２１８の手前まで延長される。
生成した線分３０１〜３１１には、コスト１を与える。

【００２０】既配線（２１４〜２１８）上に生成した線
分３１２〜３２１を図３（ｂ）に示す。既配線上に生成
する線分は、既配線と同一座標上に生成し、他の既配線
と重複しない範囲まで延長する。例えば、配線２１４の
内の水平方向の配線と同一座標上に線分３１４を生成す
る。線分３１４は、配線２１７の手前まで延長される。
生成した線分３１２〜３２１には、コストＮを与える
が、ここではＮ＝１０とする。

【００２１】未配線ネットの追加処理は、ループ１０２
の内側で実行し、未配線ネット数だけ繰り返す。ループ
１０２の内側では、まず、変数ＮＬＯＯＰに０をセット
する（１０３）。変数ＮＬＯＯＰは、一つの未配線ネッ
トについて行った引き剥がし再配線処理の実行回数を表
す。変数ＮＬＯＯＰが指定回数以下であれば(１０４)、
変数ＮＬＯＯＰをカウントアップ（１０５）した後、対
象としている未配線ネットの引き剥がし再配線処理に移
る。

【００２２】まず、対象としている未配線ネットについ
て、他の既配線との重複を許した配線経路を求める（１
０６）。図４及び図６を用いて、重複を許した配線経路
探索方法について説明する。図６は一般的な線分探索法
の配線経路探索手順を示している。図４（ａ）は、探索
で用いるすべての線分（３０１〜３２１，４０１，４０
２）を表している。これらの内、線分３０１〜３２１
は、図３で生成したものと同じである。線分４０１と線
分４０２は、配線対象となる端子２０４、及び、端子２
１１から発生し、他の既配線と重複しない範囲で延長し
たものである。

【００２３】端子から発生する線分は、各ネット毎に配
線経路探索を行う直前に生成し（６１０）、配線経路探
索を終えた後に削除される（６１１）。通常の線分探索
法では、配線すべき端子の両方から探索を進めるが、こ
こでは説明を簡略にするために、端子２０４からのみ探
索した場合の探索手順について説明する。探索を開始す
る端子２０４に接続する線分４０１を、開始線分と呼
び、探索目標となる端子２１１に接続する線分４０２を
目標線分と呼ぶ。

【００２４】まず、すべての線分に対応する選択済フラ
グ、及び、探索コストを設け、これに０を設定する（６
０１）。また、選択済線分集合をφに初期設定する(６
０１)。選択済フラグに１が設定された線分は、配線経
路探索の過程ですでに選択されたことを表す。探索コス
トは、どの線分から優先的に探索を進めるかを判定する
ためのもので、線分を生成した際に与えたコストとは別
に、探索中に設定する。最初に開始線分４０１を選択
し、これに探索コスト０を与え、探索線分集合に加え
る。線分４０１、及び、以後、選択された線分には、選
択済フラグに１を与え、再度選択されることがないよう
にする。配線経路が探索されるか、または、探索線分集
合がφでない（６０３）間、以下の探索処理を行う。

【００２５】まず、探索線分集合の内から、最も探索コ
ストの小さいものを選択し、探索線分集合から削除する
（６０４）。選択した線分をＳと表記する。最初は、線
分４０１のみが含まれるので、これを選択する。次に、
選択した線分４０１と交差する線分３０１，３１１，３
１２，３１４，３１５を探索する（６０５）。探索した
線分中に、目標線分が含まれるかを判定し（６０６）、
含まれなければ、交差線分の選択済フラグに１を設定す
る（６０８）。

【００２６】そして、交差線分の探索コストを計算し、
交差線分に与えた後、探索線分集合に加える（６０
９）。探索コストは、線分Ｓの探索コストに交差線分が
持つコストを加えることにより計算する。この場合、線
分３０１と線分３１１には、探索コスト１が与えられ
る。線分３１２，３１４，３１５には、探索コスト１０
が与えられる。そして、処理６０４に戻り、処理６０６
の判定が偽であるか、または、処理６０３の判定が真で
ある間、処理６０４〜６０９を実行する。

【００２７】上記の探索処理により、目標線分４０２に
到達するまでの探索経過を、図７にグラフで示す。各頂
点は、線分３０１〜３２１，４０１，４０２に対応す
る。また、頂点どうしを接続する辺は、交差線分の探索
順序を示している。辺の下位の頂点に対応する線分は、
辺の上位の頂点に対応する線分の交差線分探索により探
索されたことを表している。また、頂点の中の値は、各
線分の探索コストを示している。探索コストの小さい順
に交差線分を探索するので、交差線分の探索は、線分４
０１，線分３０１，線分３１１，線分３０３，線分３０
４，線分３０５，線分３０６，線分３０９，線分３１２
の順に行われる。そして、線分３１２の交差線分探索の
時に、目標線分４０２に到達する。目標線分４０２に到
達した後、配線経路を求めるために、目標線分４０２か
ら開始線分４０１に向けて、グラフの頂点を逆探索する
（６０７）。

【００２８】図４（ｂ）に、逆探索により求まった線分
４０２，３１２，４０１を示す。求まった線分４０２，
３１２，４０１の交点をたどることにより、配線経路４
０３が求まる。配線経路４０３は、配線２１８とのみ重
複しており、既配線との重複が最も少ない配線経路の内
の一つである。

【００２９】重複を許した配線経路が求まらなければ
（１１４）、次の未配線追加処理に行く（１１５）。求
まれば、重複する配線をすべて引き剥がす（１０７）。
引き剥がして空いた領域には、重複を許さない線分を生
成する（１０７）。

【００３０】図５（ａ）に、配線４０３追加した後に、
重複する配線２１８を引き剥がし、空いた領域に線分５
０１，５０２，５０３を生成した結果を示す。

【００３１】次に、引き剥がしたネットについて、重複
を許さない配線経路探索を行う（１０８，１０９）。配
線経路探索方法は、図６に示す通常の線分探索法を用い
る。図５（ａ）の状態から、端子２０２と端子２１３の
ネットの配線経路探索を行った結果を、図５（ｂ）に示
す。

【００３２】引き剥がしたネットの配線経路がすべて求
まれば(１１０)、配線経路を確定し、次の未配線追加処
理に行く(１１１)。もし、配線経路の求まらないネット
があれば、重複を許した配線経路を引き剥がし、既配
線、及び、線分を、処理１０６を行う前の状態に回復す
る（１１２）。そして、処理１０９において配線経路の
求まらなかったネットの配線上の、重複を許す線分を削
除する（１１３）。これは、次に重複を許した配線経路
探索（１０６）を行う際に、処理１０９において配線経
路が求まらなかったネットと再び重複することのないよ
うにするためである。そして、ＮＬＯＯＰが指定回数を
超えていなければ（１０４）、ＮＬＯＯＰをカウントア
ップした後（１０５）、再び処理１０６〜１１５を実行
する。

【００３３】

【発明の効果】本発明の引き剥がし再配線方法では、配
線経路探索に線分探索法を用いている。線分探索法は、
類似する配線経路探索方法である迷路法に比べ、より高
速に配線経路を求めることができる。引き剥がし再配線
では、引き剥がす配線のパターンを数多く試行すること
が、未配線追加の成功につながる。しかし、従来知られ
ている引き剥がし再配線方法では、迷路法を用いて配線
経路探索を行っているため、多くの引き剥がしパターン
を試行すると処理時間が実用範囲を超えてしまい、未配
線追加を行うことができない場合があった。本発明の引
き剥がし再配線方法は、大規模回路においても、未配線
追加を実用時間内に行うことが可能である。本発明をプ
ログラム化し、１０万ゲート規模の回路の未配線追加に
適用したところ、未配線１１９ネットを、ＥＷＳを用い
て約１０時間ですべて追加することができた。

【図面の簡単な説明】

【図１】本発明における引き剥がし再配線処理の流れの
フローチャート。

【図２】未配線例の説明図。

【図３】既配線周辺、及び、既配線上での線分生成方法
の説明図。

【図４】重複を許した配線経路探索方法の説明図。

【図５】引き剥がしたネットの再配線方法の説明図。

【図６】線分探索法の処理の流れのフローチャート。

【図７】重複を許した配線経路を探索する際の、交差線
分の探索順序の説明図。

【符号の説明】

１０１〜１１５…引き剥がし再配線処理の手順、２０１
…配線領域、２０２〜２１３…信号端子、２１４〜２１
８…配線、３０１〜３１１…重複を許さない線分、３１
２〜３２１…重複を許す線分、４０１〜４０２…信号端
子から発生した線分、４０３…重複を許した配線、５０
１〜５０３…重複する配線を引き剥がした後の空き領域
に生成した線分、５０４…引き剥がしたネットの再配
線、６０１〜６１１…線分探索法の手順。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 服部 俊洋 東京都小平市上水本町５丁目20番１号 株 式会社日立製作所半導体事業部内

Claims (1)

【特許請求の範囲】
1. 【請求項１】半導体集積回路の、ある信号を配線する際
   に、他の配線済の信号の配線が障害となって配線できな
   い場合、障害となる配線を引き剥がして配線を行う自動
   引き剥がし再配線方法において、引き剥がす配線を探索
   するために配線済の信号の配線上に線分を生成する処理
   と、生成した線分を用いて配線済の信号の配線と重複す
   ることを許して配線を行う処理と、重複する配線を引き
   剥がす処理と、引き剥がした配線の信号を再配線する処
   理と、引き剥がした配線の信号が配線できない場合、引
   き剥がした配線を元に戻し、配線上の線分を修正した後
   に、他の引き剥がすための配線を探索する処理を含むこ
   とを特徴とする自動引き剥がし再配線方法。