JPH07202000A - 並列処理によるｌｓｉ配線方式 - Google Patents

Abstract

(57)【要約】 【目的】本発明は、並列計算機またはネットワークによ
って結合された複数の計算機を用いて並列に配線処理を
行うことにより、ＬＳＩの配線問題を高速に解く並列処
理によるＬＳＩ配線方式を提供することを目的としてい
る。 【構成】配線領域を互いに独立に配線することのできる
領域に分割し、各領域に含まれるネットの配線経路を探
索する処理を部分問題とし、これらの部分問題を並列計
算機のプロセッサまたはネットワークで結合された複数
の計算機によって独立にかつ並列に処理する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、並列計算機またはネッ
トワークによって結合された複数の計算機を用いてＬＳ
Ｉ（大規模集積回路）の配線問題を並列処理により高速
に解き、ＬＳＩ配線を行う、並列処理によるＬＳＩ配線
方式に関する。

【０００２】

【従来の技術】ＬＳＩの配線問題としては、配線したい
回路の構成要素のチップ上の位置が与えられ、電気的に
同電位となるべき端子の組（以後これをネットと呼ぶ）
の集合が与えられたとき、電気的および物理的条件を満
たしながら、全てのネットの配線経路を決定することに
ある。通常、チップ上に仮想的な２次元の格子を設定
し、全ての配線はその格子上を通るものとし、異なるネ
ットの配線が重ならないように、各ネットの配線経路を
求める問題として扱われる。

【０００３】従来の代表的な手法として迷路法が知られ
ている。これは、ネット中の１つの端子を出発点とし
て、その端子のある格子点から出発して、隣接する格子
点のうち配線可能な領域にある格子の全てに順次ラベル
を書き込み、目標点に到達するか、ラベルが付けられな
くなるまで繰り返すアルゴリズムである。この手法は２
端子間の配線については、経路が存在すれば必ずそれを
見つけ出し、しかもその経路は最短であることが保証さ
れているという特徴がある。

【０００４】しかし、迷路法は１つ１つの配線を逐次的
に処理するアルゴリズムであるため、配線領域が広く、
かつ配線本数が膨大なＬＳＩでは、全ての配線を完了す
るためには多大な処理時間を要する。また、配線するネ
ットの順序が悪いと、配線不能となるネットが増大する
場合があるが、配線不能になるネット数を最小限に抑え
る適切な配線順序の決定は、対象とする個々の回路や配
線条件に依存するため、一般的な指針を作るのは困難で
ある。そのため、通常は、一旦配線処理を行い、配線不
能となった配線が生じた場合には、人手により配線経路
の修正を行うか、あるいは自動引剥し再配線手法が用い
られる。前者は後者よりも最終的により品質の高い配線
が得られるが、大規模なＬＳＩの配線では非効率的であ
り、多少品質は落ちるが、実用的には後者の手段が用い
られるのが通常である。しかし、後者についてもＬＳＩ
の規模が増大するにつれてその処理時間が膨大となると
いった問題が有る。

【０００５】

【発明が解決しようとする課題】以上のようにＬＳＩの
配線問題を従来手法で解く場合には、配線が逐次的とな
るため膨大な処理時間を要し、またネットの配線順序に
より配線不能なネットが増大する場合が有ると言った問
題点がある。

【０００６】本発明は、上記問題を解決するために達成
され、並列計算機ないしはネットワークによって結合さ
れた複数の計算機を用いて並列に配線処理を行うことに
より、ＬＳＩの配線問題を高速に解く並列処理によるＬ
ＳＩ配線方式を提供することを目的としている。

【０００７】

【課題を解決するための手段】本発明によると、ＬＳＩ
の配線問題を互いに独立な部分問題に分割し、それを並
列計算機の各プロセッサないしはネットワークで結合さ
れた複数の計算機で並列に解くことにより、高速かつ高
品質な解を得ることができる、並列処理によるＬＳＩ配
線方式を提供する。

【０００８】また、複数のプロセッサを使うことにより
従来より更に大規模な問題を解くことができる並列処理
によるＬＳＩ配線方式を提供する。即ち、配線領域を互
いに独立に配線することのできる領域に分割し、各領域
に含まれるネットの配線経路を探索する処理を部分問題
とし、それらを並列計算機の各プロセッサ上ないしはネ
ットワークで結合された複数の計算機上で、独立にかつ
並列に処理するＬＳＩ配線方式を提供する。

【０００９】

【作用】本発明によれば、配線領域の分割により各配線
処理を並列に取り扱うため、大幅な高速化を達成するこ
とができる。また、配線順序を予め設定する必要がな
く、しかも、従来方式よりも高品質な配線が得られる。

【００１０】

【実施例】以下に、本発明の一実施例を説明する。

【００１１】まず、配線問題を各プロセッサあるいは各
計算機で独立に処理できる部分問題に分割する方法を述
べる。独立に処理できる部分問題に分割するとは、配線
領域を互いに独立に配線経路の探索が可能となるような
部分領域に分割することである。この部分領域は基本的
には図２に示すようなネットの端子を頂点に持つ矩形領
域である。即ち、図２において、８および９をネットの
端子とするとき、このネットの基本的な部分領域は１０
に示す矩形領域である。

【００１２】ネットは基本的には２つの端子の組として
与えられるが、一般には、２つ以上の端子の組として与
えられることが有る。前者を２端子ネット、後者を多端
子ネットと呼ぶことにする。多端子ネットは一般性を失
うことなく全て２端子ネットに分解することができ、こ
こでは、簡単の為に全てのネットは２端子ネットとして
与えられるものとする。従って、ネットのデータは２端
子の格子点位置の組として与えられる。格子点位置は、
例えば格子の１方向をｘ軸方向、他方向をｙ軸方向と
し、適当な位置を原点として、格子間隔を単位とする座
標として表現することができる。そして上記の矩形領域
１０のデータは、例えばｘ座標値の最小値、最大値、ｙ
座標値の最小値、最大値の組として表現することができ
る。

【００１３】一般に、この矩形領域１０は隣接するネッ
トと互いに重なりあうことが多く、それらの重なりあっ
た領域は相互に独立に扱えない領域となる。そこで、こ
の重なりあった領域を更に分割して独立に扱えるように
する。分割の仕方は各ネットの端子の位置関係により、
大きく２種類に分類される。１つは、一方のネットが独
占する仕方、他の１つは、ネット間で分割する仕方であ
る。また、前者と後者についても、その独占のさせ方あ
るいは分割の方法により、それぞれ更に２つに分類され
る。

【００１４】図３は、重なりあった領域を一方の領域に
独占させる一形態を示している。このような例では、全
体が領域１１に内包されているネットに、重なりあった
領域１２を独占させる。即ち、当該ネットは、自己の基
本矩形領域全てを配線領域として与えられる。

【００１５】図４は、重なりあった領域を一方の領域に
独占させる他の一形態を示している。このような例で
は、領域１４を基本矩形領域として持つ、１端子が他方
の領域１３に内包されているネットに、領域１３と領域
１４の重なりあった領域を独占させる。言い替えれば、
１つでも端子が他方の領域に内包されていれば、そのネ
ットに重なりあった領域を独占させる。

【００１６】図５は、重なりあった領域を一方領域に独
占させるもう１つの形態を示している。このような例で
は、領域１５および１６のどちらのネットに重なりあっ
た領域を独占させるかは一意ではないが、多層配線なら
ば、例えば層毎に縦方向あるいは横方向のどちらかを優
先するように決める。他方は、未配線ネットとして残
し、次のサイクルで処理する。

【００１７】図６は、重なりあった領域を更に分割して
独立に扱えるようにする一形態を示している。このよう
な例では、２ネットの領域１７および１８の重なりあう
２つの交点を通る直線１９で分割する。

【００１８】図７は、重なりあった領域を更に分割して
独立に扱えるようにするもう１つの形態を示している。
このような例では、領域２０および２１の２ネットの向
かい合う２頂点を通る直線２２で分割する。

【００１９】このようにして各ネットの基本的な部分配
線領域である矩形領域について、周辺のネットの領域と
の重なりを調べ、他のネットに独占させる部分、分割し
て与える部分をそれぞれ自己の部分配線領域から除外し
てゆく。こうして矩形領域の重なる全ての周辺のネット
について以上の処理が済んだ後に残された領域は、他の
ネットの配線処理とは独立に扱える領域となる。

【００２０】このようにして得られた、他と独立な部分
配線領域内での配線経路探索は、並列計算機の各プロセ
ッサ上またはネットワークで結合された複数の計算機上
で全く独立に処理ができるため高い並列性が得らる。

【００２１】図１に示すフローチャートを参照して、本
発明の手法を用いた並列処理によるＬＳＩ配線方法を説
明する。

【００２２】ステップ１において、各プロセッサまたは
計算機はネットデータを得る。ここで、ネットデータに
は配線すべきネットのデータおよび配線禁止領域などの
チップ面上での制約条件、並びに２サイクル目以降で
は、配線が終ったネットの経路情報を含むものとする。
ステップ２おいて、各プロセッサまたは計算機は自分の
担当するネットを認識する。ステップ３において、各プ
ロセッサまたは計算機は自分の担当するネットの配線領
域を決める。

【００２３】上述した部分配線領域の分割規則は、各々
のネットについて独立に分割処理を行っても相互に矛盾
しないように取り決められており、このような規則を用
いることにより、この分割処理も各プロセッサまたは計
算機上で並列に、かつ独立に処理することができる。ス
テップ４においては、ステップ３で決められた部分配線
領域内での配線経路を探索する。この場合、各ネット毎
に割り当てられた部分配線領域内での配線経路の探索
は、他のネットの探索とは独立に行えるので、ネット毎
に並列に、かつ独立に処理可能である。ステップ５にお
いて、各プロセッサまたは計算機での配線処理の結果が
集計される。ステップ６において、未配線のネットを調
べる。ステップ６において、もし未配線のネットが残っ
ていれば、ステップ７において、配線済みのネットの経
路をネットデータに反映させ、未配線ネットに関して
は、ステップ１に戻ってさらに上記とほぼ同じ処理を繰
り返す。 ただし、２サイクル目以降では、配線領域の
分割割当て処理が１サイクル目とは部分的に異なり、必
要があれば、障害物を回避するように基本の矩形領域を
拡張する。同時に周辺の未配線ネットの内、その拡張に
より影響がでるネットがあれば、それを担当するプロセ
ッサまたは計算機にその旨を通知する処理が加わる。ス
テップ１からステップ５までの処理を１回以上行い、ス
テップ６において、もし未配線のネットが無くなれば、
配線処理は終了である。

【００２４】上記のようにステップ１からステップ５ま
での処理に、各サイクル毎に少しづつ異なったヒューリ
スティクスに基づいた処理を追加してゆくことによって
配線処理をより効率的に行わせることも有効である。ま
た、未配線のネットのうち、上記のような基本の矩形領
域の拡大が配線領域内で不十分になったネットについて
は、配線不能なネットとして配線処理を終了させるか、
あるいは既に配線されたネットを引き剥して、再度、異
なる割り当て規則で配線領域を求めることも有効であ
る。

【００２５】

【発明の効果】以上に述べたように、本発明によれば、
ＬＳＩの配線領域を部分領域に分割し、それらの部分領
域を並列計算機の複数のプロセッサ、ないしはネットワ
ークによって結合された複数の計算機に独立に解かせる
ことにより、大規模なＬＳＩの配線問題を高速に解くこ
とができ、従来手法に比べて、予め配線順序を設定する
必要がなく、しかも高品質な配線を高速に行うことがで
きる。

【図面の簡単な説明】

【図１】本発明の一実施例に従った並列処理による配線
方式を説明するためのフローチャート図。

【図２】基本となる部分配線領域

【図３】重なり領域を占有させる第１の例を示す図。

【図４】重なり領域を占有させる第２の例を示す図。

【図５】重なり領域を占有させる第３の例を示す図。

【図６】重なり領域を分割させる第１の例を示す図。

【図７】重なり領域を分割させる第２の例を示す図。

【符合の簡単な説明】

８…ネットの端子、９…ネットの端子、１０…基本的な
部分配線領域、１１…他のネットを内包するネット、１
２…内包されているネット、１３…他のネットの端子を
内包するネット、１４…ネットの１端子が内包されてい
るネット、１５…交差する一方のネット、１６…交差す
る他方のネット、１７…一部重なる一方のネット、１８
…一部重なる他方のネット、１９…２つの配線領域の２
つの交点を通る直線、２０…他方のネットの１端子を内
包した一方のネット、２１…他方のネットの１端子を内
包した他方のネット、２２…２ネットの向かい合う２つ
の端子を通る直線。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 ２次元の配線格子上で複数の配線経路を
   求めるＬＳＩの配線方式において、配線領域が互いに独
   立となるようにネット毎に配線領域を分割する行程と、
   分割された各領域内でのネットの配線処理を処理単位と
   し、これらネットを、並列計算機の複数のプロセッサま
   たはネットワークで結合された複数の計算機に分配し、
   並列処理による高速配線を行う行程とを含むことを特徴
   とするＬＳＩ配線方式。
2. 【請求項２】 前記分割する行程は、複数のネットの端
   点を頂点とする矩形領域の重なった領域を、予め決めら
   れた規則に従い、どのネットの配線領域に割り当てるか
   を決定する行程を有することを特徴とする請求項１記載
   の配線方式。
3. 【請求項３】 前記分割する行程は、複数のネットの端
   点を頂点とする矩形領域の重なった領域を、予め決めら
   れた規則に従って分割してネットに割り当てる行程を有
   することを特徴とする請求項１記載の配線方式。