JP2931683B2

JP2931683B2 - 自動配線処理におけるラベル付け方式

Info

Publication number: JP2931683B2
Application number: JP3044690A
Authority: JP
Inventors: 秀樹三渡; 薫河村; 由江大木
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1991-03-11
Filing date: 1991-03-11
Publication date: 1999-08-09
Anticipated expiration: 2014-08-09
Also published as: JPH04281571A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、自動配線処理における
ラベル付け方式に関し、特に自動配線の対象であるプリ
ント基板やＬＳＩ等の配線平面をｍ×ｎ（ｍ，ｎは整
数）の格子からなる複数のウィンドウに分割し、各格子
には配線部分として用いられることについての重みを与
えて、この重みを加味したうえでの隣接格子に対するラ
ベル付けを前記ウィンドウの単位で、出発点のウィンド
ウから順次行ない、このラベル付けの結果に基づいて出
発点，目的点それぞれの端子間の配線経路を求めていく
場合のラベル付け方式に関する。

【０００２】このような自動配線処理は計算機を用いて
行なわれるが、最近では、プリント基板やＬＳＩ等が高
密度化されていることもあって、配線経路決定までの要
処理時間の短縮化を図ることがより必要となっている。
本発明は、このような要処理時間の短縮化の要請に応え
るためのラベル付け方式に関する。

【従来の技術】

【０００３】従来の、ラベル付けの結果に基づいて端子
間の配線経路を求めていく手法である迷路法を、図６〜
図10を用いて説明する。図６において、Ａ′，Ｂ′は自
動配線処理の対象となっている端子対であり、Ａ′は出
発点，Ｂ′は目的点である。そして、この両点が格子上
に載るように、プリント基板やＬＳＩ等の自動配線対象
平面は格子状に分割されており、また網掛けした部分は
配線パタ−ンを引くことができない禁止領域である。

【０００４】図６(a) は、自動配線対象平面の各格子が
配線部分として用いられることについての重みを示す説
明図であり、その数値が小さいほど配線パタ−ンとして
優先的に用いることができる格子であることを表してい
る。この重みは、既設の配線パタ−ンとの位置関係や、
以降の配線を行なうときの困難性などに基づき、予め決
められている。

【０００５】ここで、隣接格子にラベル付けを行なう能
力を備えた能動格子は最初Ａ′点のみであり、先ずＡ′
点から、この格子の東西南北に隣接する４つの格子にラ
ベル付け、すなわちＡ点自体のラベル値（重み）に隣接
格子それぞれの重みを加えた値をその隣接格子にふるこ
とが行なわれる。

【０００６】そして、次の２ステップ目では、図６(b)
のように、１ステップ目でラベル付けが行なわれた格子
（○印で囲んだ数字の部分）が能動格子となって、これ
らの能動格子から矢印の方向にラベル付けが行なわれ、
新たに５つの隣接格子にラベル値がふられることにな
る。

【０００７】また、このときの格子Ｅ，Ｆへのラベル付
けのように、隣接する複数の格子からのラベル付けが可
能なときは値の小さい方のラベル値がふられることにな
る。例えば、格子Ｅの場合、北側の格子からのラベル付
けによるラベル値は「７」，東側の格子からのラベル付
けによるラベル値は「８」となり、前者のラベル値がふ
られている。

【０００８】以下、同じ手順でラベル付けが行なわれ、
６ステップ目のラベル付けが終了した時点でのラベル状
態は図６(c) のようになる。なお、○印で囲んだ数字の
部分は次のステップへの能動格子であり、例えば５ステ
ップ目のラベル付けで「17」のラベル値がふられている
格子Ｇは、次の７ステップ目における西側の能動格子Ｈ
からのラベル付けにより「16」のラベル値に更新され
る。

【０００９】図６(d) は、９ステップ目のラベル付けが
終了した状態であり、このとき目的点Ｂ′に始めてラベ
ル値「22」がふられる。ここで、能動格子（○印で囲ん
だ数字の部分）の中、右上部分の格子Ｉ，Ｊそれぞれの
ラベル値は目的点Ｂのラベル値「22」より小さく、これ
らの格子からの新たなラベル付けによって目的点Ｂ′の
ラベル値が「22」より小さい値に更新される可能性があ
るため、以降も、格子Ｉ，Ｊそれぞれからのラベル付け
は続行される。

【００１０】そして、目的点Ｂのラベル値が、より小さ
い値に更新される可能性がなくなった図６(e) の状態で
ラベル付けは終了し、続いて、目的点Ｂ′から出発点
Ａ′に向かって、ラベル値の小さくなる隣接格子を順次
たどることによりＡ′とＢ′との間の配線経路を決定し
ている。

【００１１】このような迷路法においては、全処理時間
の70〜80％をラベル付けに要しており、また図６(d) の
ように目的点Ｂ′にラベル値がふられてからも以降のラ
ベル付けを続行することが必要な場合もあるため、専用
のハードウェアを用いて自動配線処理の高速化を図るこ
とが提案されている。

【００１２】以下、図７〜図10を参照して、この専用の
ハードウェアを用いた自動配線処理について説明する。
図７(a) はｍ×ｎ（ｍ，ｎは整数）の格子からなる複数
のウィンドウに分割された配線平面を、図７(b) はこの
配線平面における各格子の重みを、図８はこの配線平面
にラベル付けを実行していく自動配線処理専用のハード
ウェアの概要を、図９はこのハードウェアの一部である
複数のＰＥ（プロッセッサエレメント）それぞれが持つ
データ内容を、また図10はこのハードウェアにより図７
(a) の配線平面をラベル付けしていく様子を示してい
る。なお、このＰＥ（プロッセッサエレメント）の構成
については特開平２−８１２５８号公報で開示されてい
る。

【００１３】ここで、自動配線の対象である配線平面の
各格子には配線部分として用いられることについての重
みが設定されており、ラベル付けは複数のＰＥによって
このウィンドウを単位にして実行される。すなわち、複
数のＰＥは、所定のウィンドウのラベル付けが終了して
から、次の処理対象である隣接ウィンドウのラベル付け
が実行される。

【００１４】図８において、５はプロセッサアレイで、
それぞれが各ウィンドウの１つの格子を担当するプロッ
セッサエレメント（ＰＥ１〜ＰＥ９）からなっており、
例えば、ウィンドウ０のラベル付けの場合、ＰＥ５が格
子Ａ（出発点）を、ＰＥ３が格子Ｊを担当する。また、
３はこれらのＰＥを制御するためのコントローラ，11は
このコントローラに実装されたＰＥ制御メモリである。

【００１５】ここで、各ＰＥは、担当する格子に隣接す
る東西南北の格子を担当するＰＥのそれぞれと通信路を
介して接続されており、例えばＰＥ１はＰＥ２，ＰＥ４
の外にＰＥ３とＰＥ７にも接続されている。そして、コ
ントローラ３とプロセッサアレイ５との間にも通信路が
設けられており、ＰＥ制御用メモリ11と各ＰＥとの間
で、ラベル付けのためのデ−タ分配やラベル値などのデ
−タ収集を行えるようになっている。また、コントロー
ラ３はこれらのデ−タ分配，デ−タ収集の制御や、全Ｐ
Ｅで実行する演算の制御を行なっている。

【００１６】このように、コントローラ３は、プロセッ
サアレイ５に、ラベル付けの出発点や目的点を設定し、
また各ＰＥにウィンドウを指示してそのラベル付けを実
行させ、当該ウィンドウ内でのラベル値の更新がなくな
ったことを判定してから次のラベル付けを実行するウィ
ンドウを指示している。なお、ウィンドウの切り換えは
ＰＥ内メモリのベースアドレスの設定によって行われ
る。

【００１７】そして、各ＰＥのメモリが持つ図９のデー
タの中、「ｗｉｎｄｏｗｎｕｍｂｅｒ」，「ｔａｒｇｅ
ｔＬａｂｅｌ」および「ｎＬａｂｅｌ」は各ウィンドウ
に共通なワーク用のデータであり、その他のものはウィ
ンドウ毎のデータである。

【００１８】また、括弧内の数字はウィンドウ番号を示
しており、例えば「ｎＷｉｎｄｏｗ（０）」は、ウィン
ドウ０の北側に隣接するウィンドウ番号「３」であり、
ＰＥ１のメモリでの「ｃｏｓｔ（２）」は、ウィンドウ
２でＰＥ１が担当する格子Ｌの重み「４」である。

【００１９】また、「ｓｔａｒｔＦｌａｇ」については
ウィンドウ０の出発点Ａを担当するＰＥ５のメモリの
「ｓｔａｒｔＦｌａｇ（０）」のみが「１」になり、
「ｔａｒｇｅｔＦｌａｇ」についてはウィンドウ２の目
的点Ｂを担当するＰＥ６のメモリの「ｔａｒｇｅｔＦｌ
ａｇ（２）」のみが「１」になっている。

【００２０】次に、この専用ハードウェアにより図７
(a) の配線平面をラベル付けしていく様子を、図10を用
いて説明する。図において、Ａは出発点を、Ｂは目的点
を、網掛けした部分はその時点での能動格子を、また矢
印は最小のラベル値を与えるラベルが伝わってきた方向
を示している。そして、イベント・キュー４は、次にラ
ベル付けを行なうウィンドウのウィンドウ番号を格納す
るためにＰＥ制御用メモリ11に設けられた領域であり、
このイベント・キューには、右側を先頭にして、ウィン
ドウ番号が小さい方から順に格納されている。

【００２１】図10(b) は、ウィンドウ０のラベル付けが
終了した状態を示しており、イベント・キューには、次
のラベル付けの対象であるウィンドウ、すなわちウィン
ドウ０の能動格子に隣接したウィンドウ１とウィンドウ
３のウィンドウ番号が格納されている。

【００２２】図10(c) は、このウィンドウ１とウィンド
ウ３のラベル付けが終了した状態を示しており、イベン
ト・キューには、次のラベル付けの対象であるウィンド
ウ０，ウィンドウ２およびウィンドウ４のウィンドウ番
号が格納されている。なお、すでにラベル付けが行なわ
れたウィンドウ０が次のラベル付けの対象になっている
のは、ウィンドウ３中の右下のラベル値「15」の能動格
子が、その南側に隣接するウィンドウ０中の（この能動
格子との間で、南北方向の矢印がついていない）格子の
ラベル値を更新する可能性が存在するためである。

【００２３】図10(d) は、このウィンドウ０，ウィンド
ウ２およびウィンドウ４のラベル付けが終了した状態を
示しており、イベント・キューには、次のラベル付けの
対象であるウィンドウ１，ウィンドウ３およびウィンド
ウ５のウィンドウ番号が格納されている。ここで、ウィ
ンドウ３とウィンドウ５が次のラベル付け処理の対象に
なっているのは、図10(c) の場合と同様な理由のためで
ある。

【００２４】また、この段階で目的点Ｂにラベル値「3
0」がふられているが、ウィンドウ４の能動格子のラベ
ル値がウィンドウ５を介して伝わることにより目的点Ｂ
のラベル値がより小さい値に更新される可能性があるた
め、以降のラベル付け処理を実行している。このとき、
ウィンドウ２の右上，右下の格子Ｍ，Ｎは、それぞれの
ラベル値「31」が目的点Ｂのラベル値「30」より大きく
なっており、能動格子ではない。

【００２５】図10(e) は、このウィンドウ１，ウィンド
ウ３およびウィンドウ５のラベル付けが終了した状態を
示しており、イベント・キューには、次のラベル付けの
対象であるウィンドウ２およびウィンドウ４のウィンド
ウ番号が格納されている。

【００２６】図10(f) は、すべてのラベル付け処理が終
了した状態、すなわち能動格子がなくなり、またイベン
ト・キューは空になった状態を示している。なお、ウィ
ンドウ２の両下隅の格子Ｐ，Ｑは、それぞれのラベル値
を更新しても目的点Ｂのラベル値よりも大きな値になる
ため、図10(e) のままになっている。

【００２７】

【発明が解決しようとする課題】以上の、専用ハードウ
ェアによるウィンドウ単位のラベル付けの場合にも、６
つのウィンドウに対してウィンドウの切り換えが11回に
も及び、依然として要処理時間が長いという問題点があ
った。

【００２８】そこで、本発明では、イベント・キューに
複数個のウィンドウ番号が入っているときには、それぞ
れのウィンドウ番号のウィンドウに伝わってくるラベル
値の中で最も小さいもののウィンドウのみについてのラ
ベル付けを実行することにより、いったんラベル付けを
行なったウィンドウについて再度のラベル付けが実行さ
れ、より小さいラベル値に更新されるといったことが生
じるのをできるだけ少なくして、ラベル付けに要する時
間の短縮化を図ることを目的とする。

【００２９】

【課題を解決するための手段】本発明は、ｍ×ｎ（ｍ，
ｎは整数）の格子からなる複数のウィンドウに分割さ
れ、前記格子のそれぞれには配線部分として用いられる
ことについての重みが設定されている配線平面に対し、
この重みを加味したうえでの隣接格子に対するラベル付
けを前記ウィンドウの単位で、出発点のウィンドウから
順次行なっていく方式において、次のラベル付けの対象
となる隣接ウィンドウが複数個あるとき、ラベル付け処
理が終了したウィンドウの能動格子から伝わっていくラ
ベル値が最も小さい隣接ウィンドウのみに次のラベル付
け処理を行ない、いったんラベル付け処理が終了したウ
ィンドウのラベル値が再度のラベル付け処理によってよ
り小さいラベル値に更新されるといったケースが発生す
ることを少なくしたものである。

【００３０】図１は、本発明の原理説明図である。図に
おいて、１は、配線平面デ−タであり、ｍ×ｎ（ｍ，ｎ
は整数）の格子からなる複数のウィンドウに分割された
配線平面における各ウィンドウの隣接関係などを示すデ
−タからなっている。

【００３１】２は、重みデ−タであり、配線平面の各格
子に設定されている、配線部分として用いられることに
ついての重みからなっている。

【００３２】３は、コントローラであり、配線平面デー
タ１，重みデータ２や、次のラベル付けに用いる能動格
子のラベル値などをプロセッサアレイ５に送り、ラベル
付けの終了した能動格子のラベル値や当該能動格子の隣
接ウィンドウのウィンドウ番号などをプロセッサアレイ
５から受け、またプロセッサアレイ５で実行する演算の
制御を行なう。

【００３３】４は、イベント・キューであり、プロセッ
サアレイ５から送られてくるウィンドウ番号と、このウ
ィンドウ番号に対応する（このウィンドウにラベル値を
伝えてくる能動格子の）ラベル値の中の最小のものとが
組になって格納される。

【００３４】５は、プロセッサアレイであり、それぞれ
が１つの格子を担当するｍ×ｎ個のプロセッサエレメン
トから構成され、隣接格子を担当するプロセッサエレメ
ント同士は通信路を介して接続されており、コントロー
ラ３から指示されるウィンドウの各格子についてのラベ
ル付けを実行する。

【００３５】そして、本発明のラベル付け処理の基本的
な手順は次のようになっている。すなわち、コントロ
ーラ３は、プロセッサアレイ５に出発点のウィンドウの
ウィンドウ番号を送って最初にラベル付けを実行するウ
ィンドウを指示する。

【００３６】プロセッサアレイ５の各プロセッサエレ
メントは、指示されたウィンドウについて、従来と同様
なラベル付けを、ラベル値が伝わっていく隣接格子のそ
れぞれに順次実行する。

【００３７】プロセッサアレイ５は、隣接ウィンドウ
にラベル値を伝えることができる能動格子のラベル値
と、このウィンドウ番号とをコントローラ３に順次送信
する。なお、このラベル値が、その時点での目的点のラ
ベル値以上のものであるときには、これらのデータをコ
ントローラ３へ送信しないか、送信したとしてもコント
ローラ３の方で無効データとして取り扱うようにしてい
る。これは、このラベル値を用いて以降のラベル付けを
実行しても、目的点のラベル値がより小さな値に更新さ
れる可能性がないからである。

【００３８】コントローラ３は、コントローラ３から
の新たな内容の送信がなくなったことを確認して、送ら
れてきたウィンドウ番号と、これに対応するラベル値の
中の最小のものとを組にしてイベント・キューに加え
る。

【００３９】コントローラ３は、イベント・キューに
ウィンドウ番号のデ−タが残っているかどうかを判断
し、「YES」の場合はラベル付けを終了し、「NO」の場
合は次のステップに進む。

【００４０】イベント・キューに入っているラベル値
の中の最小のものと組になっているウィンドウ番号を取
り出してプロセッサアレイ５に送り、次にラベル付けを
行なうウィンドウを指示し、かつこの組のデ−タをイベ
ント・キューから削除して、ステップに戻る。といっ
た基本的手順により、次にラベル付けの対象となるウィ
ンドウが複数ある場合には、その中の特定のウィンドウ
のみのラベル付けを実行している。

【００４１】なお、ステップにおいて、プロセッサア
レイ５に送られなかったデ−タの中で、ラベル値が（こ
の時点での）目的点のラベル値以上となっている組のも
のについてもイベント・キューから削除するようにして
もよい。これは、これらのラベル値に基づく以降のラベ
ル付けを行なっても、目的点のラベル値がより小さい値
に更新される可能性がないからである。

【００４２】

【作用】このように、ラベル付けが終了したウィンドウ
の能動格子のラベル値を伝えることができる隣接ウィン
ドウが複数あるときには、従来のようにこれらすべての
ウィンドウについてのラベル付けを実行するのではな
く、所定のルールにしたがって指示される一つのウィン
ドウのみに対してラベル付けを実行するようにしてい
る。

【００４３】そして、このルールは、隣接ウィンドウの
中、ラベル値が最も小さい能動格子に隣接するものを選
択することであるから、この選択されたウィンドウにラ
ベル付けを実行した後で他のウィンドウから伝わってく
るラベル値で再びラベル付けを実行して、この選択ウィ
ンドウのラベル値がより小さな値に更新されるといった
ケースが生じる率は低いものとなり、全体のラベル付け
が終了するまでに必要なウィンドウの切り換え回数を減
らすことができる。

【００４４】以下、このラベル付けの様子を、図２〜図
３を用いて説明する。ここで、Ａは出発点、Ｂは目的
点、網掛け部分は能動格子であり、各格子の重みについ
ては図８と同じ内容に設定されている。また、各ウィン
ドウ番号の右側の数字は、そのウィンドウに隣接する能
動格子のラベル値の中の最小のものであり、これらは１
組のデ−タを構成している。そして、各組のデ−タは、
この右側の数字を小さい順に並べ換えて小さいほうをイ
ベント・キュー４の先頭に入れるといったルールにした
がって格納されており、次のラベル付けは、このイベン
ト・キュー４の先頭（右側）に格納されているウィンド
ウ番号のウィンドウについてのみ行なわれる。

【００４５】図２(a) は、初期状態を示しており、イベ
ント・キュー４には、最初にラベル付けを実行する出発
点Ａのウィンドウ０と、この出発点Ａの重み「１」とが
格納されている。

【００４６】図２(b) は、ウィンドウ０のラベル付けが
終了した状態を示しており、先のウィンドウ０の「０−
１」のデータは削除されている。そして、イベント・キ
ューには、このウィンドウ０に隣接するウィンドウのウ
ィンドウ番号「１」，「３」とそれぞれの最小ラベル値
「13」，「２」とを組にしたデ−タが、前記ルールにし
たがってウィンドウ３の「３−２」の組を先頭にして格
納されている。

【００４７】ここで、ウィンドウ３が先頭になっている
のは、このウィンドウ３に隣接する能動格子のラベル値
の最小値「２」がウィンドウ１に隣接する能動格子のラ
ベル値の最小値「13」よりも小さいからである。

【００４８】以下、同じようにしてイベント・キューの
先頭ウィンドウに対するラベル付けが順次実行されてい
く。

【００４９】図２(c) は、ウィンドウ３のラベル付けが
終了した状態を示しており、先のウィンドウ３の「３−
２」のデータは削除されている。そして、イベント・キ
ューには、このウィンドウ３に隣接する、ウィンドウ０
とウィンドウ４についてのデ−タが新たに加えられ、３
組のデ−タがウィンドウ４の「４−５」の組を先頭にし
て格納されている。

【００５０】ここで、ウィンドウ０についてのデ−タが
新たに加えられているのは、ウィンドウ３の右下のラベ
ル値「15」の能動格子からラベル値がウィンドウ０に伝
わってこのウィンドウのラベル付けを実行することが可
能なためである。

【００５１】図２(d) は、ウィンドウ４のラベル付けが
終了した状態を示しており、先のウィンドウ４の「４−
５」のデータは削除されている。そして、イベント・キ
ューには、このウィンドウ４に隣接する、ウィンドウ
１，ウィンドウ３およびウィンドウ５についてのデ−タ
が新たに加えられ、５組のデ−タがウィンドウ５の「５
−８」の組を先頭にして格納されている。

【００５２】ここで、ウィンドウ３に対しては、ウィン
ドウ４の左側の格子の中、まだウィンドウ３との間で矢
印の付いていない下側のラベル値「18」の格子のみがラ
ベル付けを行なう能力を持った能動状態となっており、
またウィンドウ１については、北側の隣接格子の最小ラ
ベル値「17」の組のデ−タと、西側の隣接格子の最小ラ
ベル値「13」の組のデ−タとがイベント・キューに格納
されることになる。

【００５３】図２(e) は、ウィンドウ５のラベル付けが
終了した状態を示しており、先のウィンドウ５の「５−
８」のデータは削除されている。そして、イベント・キ
ューには、このウィンドウ５に隣接する、ウィンドウ２
とウィンドウ４についてのデ−タが新たに加えられ、６
組のデ−タがウィンドウ２の「２−11」の組を先頭にし
て格納されている

【００５４】図２(f) は、ウィンドウ２のラベル付けが
終了した状態を示しており、先のウィンドウ２の「２−
11」のデータは削除されているこのとき、目的点Ｂにラ
ベル値「14」がふられることになり、またラベル付け後
の値がこの「14」より大きくなる下側両隅の格子Ｒ，Ｓ
には、ラベル値はふられれない。

【００５５】そして、イベント・キューには、新たにデ
ータが加えられることはないが、５組のデ−タ（ウィン
ドウ１については、対応するウィンドウが異なる２組の
デ−タ）が残っており、続いてこれらの４つのウィンド
ウについてのラベル付けが行われる。

【００５６】図３(a) は、すべてのラベル付け処理が終
了した状態、すなわち能動格子がなくなり、イベント・
キューのデ−タがなくなったが状態を示している。この
とき、ラベル付け後の値が目的点Ｂのラベル値「14」よ
り大きくなるウィンドウ１の各格子にはラベル値がふら
れていない。

【００５７】なお、図２(f) の状態において、目的点Ｂ
のラベル値「14」以上のラベル値を以降のラベル付けに
用いても、目的点Ｂのラベル値がより小さい値に更新さ
れる可能性はないので、ウィンドウ０とウィンドウ３に
対するラベル付けは省略してもよい。この場合、ウィン
ドウ３の「３ー18」，ウィンドウ１の「１ー17」および
ウィンドウ０の「０ー15」の３組のデ−タはイベント・
キューから削除され、イベント・キューの状態は図３
(b) のようになる。

【００５８】このように、ラベル付けの対象となるウィ
ンドウの合計数は、図２(f) のイベント・キュー状態か
ら終了する場合で９個、図３(b) のイベント・キューの
状態から終了する場合で７個となり、いずれの場合も従
来の11個に比べて少なくなっている。

【００５９】

【実施例】以下，図４および図５を用いて本発明の実施
例を説明する。ここで、コントローラ，各プロセッサエ
レメント（ＰＥ），配線平面および各格子の重みなどに
ついては図７〜図９の場合と同じ構成になっている。

【００６０】図４は、コントローラ３の動作手順を示す
フローである。すなわち、′イベント・キュー４に、
出発点のウィンドウ番号「１」と、この出発点の重み
「１」を加え、次のステップに進む。

【００６１】′イベント・キュー４の先頭データを取
り出してプロセッサアレイ５に送り、次にラベル付けを
実行するウィンドウを各プロセッサエレメントに指示し
て、次のステップに進む。

【００６２】′プロセッサアレイ５から送られてく
る、各格子のラベル値が新たな値に更新されなくなくな
ったのを確認して、次のステップに進む。

【００６３】′各ＰＥから送られてきたラベル値を対
応するウィンドウ番号ごとのグループにし、それぞれの
グループの中で最小のラベル値とウィンドウ番号とを組
にしたデ−タを作成して、次のステップに進む。

【００６４】′この（最小）ラベル値とウィンドウ番
号とからなるデ−タをイベント・キュー４に加え、次の
ステップに進む。

【００６５】′イベント・キュー４に残っていたデー
タおよび新たに加えられたデータに対してラベル値をキ
ーにしたソートを行い、次のステップに進む。なお、こ
のソートにより、ラベル値とウィンドウ番号とを組にし
た各デ−タは、そのラベル値が小さい順に先頭から並べ
られる。

【００６６】′このソートされたラベル値と、その時
点での目的点のラベル値「ｔａｒｇｅｔＬａｂｅｌ」と
を比較し、「前者≧後者」の関係にある組のデータをイ
ベント・キュー４から削除する。なお、「ｔａｒｇｅｔ
Ｌａｂｅｌ」の初期値は無限大に設定されている。

【００６７】′イベント・キュー４のデータがなくな
ったかどうかを判断し、「YES」の場合はプロセッサア
レイ５に対する制御を終了し、「NO」の場合はステップ
′に戻る。といった手順により、各ＰＥの動作を制御
している。なお、以上の手順において、ステップ′と
ステップ′は順序を逆にしてもよい。

【００６８】一方、各ＰＥでのラベル計算の手順は図５
のようになっている。なお、各ＰＥでのラベル計算は、
コントローラにより指示される単一ウィンドウの各格子
に対し繰り返し行なわれている。

【００６９】すなわち、（1)コントローラにより、ラベ
ル付けを実行するウィンドウ番号，最初は出発点Ａのウ
ィンドウ番号「０」が設定される。

【００７０】（2)各ＰＥのメモリに対するラベル付けの
ための初期値設定を行なう。すなわち、目的点Ｂのラベ
ル値を無限大にし、ウィンドウ０〜５のそれぞれで各Ｐ
Ｅが担当する格子への、隣接格子からのラベル入力はな
く、またこれらの担当格子自体のラベル値は無限大にし
ている。。

【００７１】（3)以後のラベル計算に進むかどうかを判
定している。例えば、ウィンドウ０において、ＰＥ２が
担当する、出発点Ａからその北側隣接格子Ｔへのラベル
付けの場合には、ｌａｂｅｌ（０）およびｔａｒｇｅｔ
Ｌａｂｅｌの値は無限大、ｎＬａｂｅｌの値は出発点Ａ
のラベル値「１」、ｃｏｓｔ（０）の値は「１」である
から、この判定条件を満たして以後のラベル計算に進
み、ＰＥ２のｌａｂｅｌ（０）の値は無限大から「２」
に更新されるが、ＰＥ３が担当する、格子Ｕからその北
側隣接格子Ｖへのラベル付けの場合には、ｌａｂｅｌ
（０）の値は「14」、ｎＬａｂｅｌの値は格子Ｕのラベ
ル値「13」、ｃｏｓｔ（０）の値は「12」であるから、
この判定条件の１番目の不等式を満たさなくなって以後
のラベル計算には進まず、ＰＥ３のｌａｂｅｌ（０）の
値は更新されない〔図２(a),(b) 、図８参照〕。

【００７２】また、例えば、ウィンドウ２において、Ｐ
Ｅ７が担当する、格子Ｗからその西側隣接格子Ｒへのラ
ベル付けの場合には、ｔａｒｇｅｔＬａｂｅｌの値は
「14」、ｎＬａｂｅｌの値は格子Ｗのラベル値「14」、
ｃｏｓｔ（２）の値は「４」であるから、この判定条件
の２番目の不等式を満たさなくなって以後のラベル計算
には進まない〔図２(f) 、図８参照〕。

【００７３】（4)担当格子のラベル値を、隣接格子から
伝わってきたラベル値に自らの重みを加えた値で更新す
る。例えば、先の格子Ｔのラベル値を無限大から「２」
に更新する。

【００７４】（5)担当格子にどちらの方向からラベル値
が伝わってきたかを示す方位データを加える。例えば、
格子Ｔへのラベル付けのように南側の隣接格子Ａからの
ラベル入力があった場合には、ＰＥ２のメモリのｄｉｒ
Ｓ（０）の値を「１」にする。

【００７５】（6)方位データが「０」のままになってい
る隣接格子、すなわちラベル入力元の格子を除いた隣接
格子に、担当格子のその時点でのラベル値を通信路を介
して伝える。

【００７６】（7)担当格子のｔａｒｇｅｔＦｌａｇが
「１」のときは、ｔａｒｇｅｔＬａｂｅｌの値を担当格
子のラベル値で更新し、またｔａｒｇｅｔＦｌａｇが
「０」のときは、ｔａｒｇｅｔＬａｂｅｌの値を更新し
ないで、次のステップに進む。

【００７７】（8)担当格子が他のウィンドウに隣接して
いるときは、そのウィンドウ番号と担当格子のラベル値
とをコントローラに伝え、また隣接してないときは担当
格子のラベル値をコントローラに伝えることなしに、ス
テップ（2)に戻る。といった並列処理を、各ＰＥはウィ
ンドウ単位で繰り返し実行している。

【００７８】このように、コントローラから指示された
あるウィンドウのラベル付けにおいて、担当格子が、隣
接するウィンドウへラベル値を伝えることができる能動
状態となった各ＰＥはこの担当格子のラベル値と、隣接
するウィンドウ番号とをコントローラに送っている。

【００７９】そして、これらのデータの更新が起きなく
なった時点で、コントローラはラベル値の最も小さいウ
ィンドウ番号を各ＰＥに送って、これを受けたＰＥ側で
はこのウィンドウのラベル付けに移っていく。また、こ
のウィンドウに伝えられる、隣接ウィンドウの能動格子
の各ラベル値もＰＥ側に送られて次の隣接ウィンドウへ
のラベル付けに用いられる。

【００８０】以上の説明では、ウィンドウの数を６個，
各ウィンドウの格子数を９個としているが、実際の自動
配線処理においては、例えば80（10×８）個のウィンド
ウで各ウィンドウの格子数が16384(128 ×128)個の配線
平面が用いられている。

【００８１】

【発明の効果】本発明は、自動配線処理の対象である配
線平面をｍ×ｎ（ｍ，ｎは整数）の格子からなるウィン
ドウに分割し、出発点からの、各格子の重みを加味した
ラベル付けをこのウィンドウ単位で行なっていく場合に
おいて、ラベル付けが終了したウィンドウの能動格子の
ラベル値を伝えることができる複数の隣接ウィンドウの
中、その時点での最小のラベル値が伝わっていくウィン
ドウだけに次のラベル付けを行なうようにし、いったん
ラベル値がふられた後で再びラベル付けが実行されてよ
り小さいラベル値に更新されるといったことが生じる率
を減らしているので、ラベル付けの対象になるウィンド
ウの延べ数を少なくして自動配線全体の要処理時間の短
縮化を図ることができる。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】本発明のラベル付けの様子を示す説明図（その
１）である。

【図３】本発明のラベル付けの様子を示す説明図（その
２）である。

【図４】本発明の、コントローラの動作手順を示すフロ
ーである。

【図５】本発明の、各プロセッサエレメント（ＰＥ）の
動作手順を示すフローである。

【図６】従来の、重みを加味した迷路法（その１）によ
るラベル付けの様子を示す説明図である。

【図７】ｍ×ｎ（ｍ，ｎは整数）の格子からなる複数の
ウィンドウに分割された配線平面、および各格子の重み
を示す説明図である。

【図８】図７のウィンドウ単位でラベル付けを実行して
いく、自動配線処理専用のハードウェアの概要を示す説
明図である。

【図９】複数のＰＥ（プロッセッサエレメント）それぞ
れが持つデータ内容を示す説明図である。

【図10】図７の配線平面における、従来の、重みを加味
した迷路法（その２）によるラベル付けの様子を示す説
明図である。

【符号の説明】

１配線平面デ−タ２重みデ−タ３コントローラ（ＰＥ制御装置）４イベント・キュー５プロセッサ・アレイ

フロントページの続き (56)参考文献特開昭60−144867（ＪＰ，Ａ) 特開昭62−80757（ＪＰ，Ａ) 特開昭63−15367（ＪＰ，Ａ) 特開平２−17576（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 17/50 G06F 15/16 H01L 21/82

Claims

(57)【特許請求の範囲】

【請求項１】ｍ×ｎ（ｍ，ｎは整数）の格子からなる
複数のウィンドウに分割され、当該格子のそれぞれには
配線部分として用いられることについての重みが設定さ
れている配線平面に対し、イベント・キューを持つコン
トローラと、それぞれが前記ウィンドウの格子を１対１
の対応関係で担当するとともに、隣接格子を担当するも
の同士が通信路で接続されたｍ×ｎ個のプロセッサエレ
メントを持つプロセッサアレイとを用いて、前記コント
ローラから指示されるウィンドウについての、前記重み
を加味したうえでの隣接格子に対するラベル付けを、出
発点のウィンドウから前記プロセッサアレイにより順次
行ない、このラベル付けの結果に基づいて出発点と目的
点との間の配線経路を求めていく自動配線処理における
ラベル付け方式において、各ウィンドウの隣接関係など
を示す配線平面データおよび各格子の重みデータが与え
られている前記プロセッサアレイは、指示されたウィン
ドウの各格子に対する前記ラベル付けを繰り返し実行し
ながら、隣接ウィンドウにラベル値を伝えることができ
る能動格子のそれぞれのラベル値と、この隣接ウィンド
ウのウィンドウ番号とを、前記コントローラに送り、前
記コントローラは、所定の時点で、この送られてきたウ
ィンドウ番号と、当該ウィンドウ番号に対応するラベル
値の中の最小のものとを組にしたデータを前記イベント
・キューに加え、続いてこのイベント・キューに入って
いるラベル値の中の最小のものと組になっているウィン
ドウ番号を前記プロセッサに送って、このウィンドウ番
号で特定されるウィンドウのみが次のラベル付けの対象
であることを指示するとともに、このウィンドウ番号の
組のデータを前記イベント・キューから削除するといっ
た処理を繰り返し、目的点のラベル値がより小さな値で
更新されなくなるまでラベル付けを実行するようにした
ことを特徴とする自動配線処理におけるラベル付け方
式。
【請求項２】前記コントローラは、前記イベント・キ
ューに入っているラベル値とウィンドウ番号との組の中
で、そのラベル値が目的点のラベル値以上になっている
組についても前記イベント・キューから削除するように
したことを特徴とする請求項１記載の自動配線処理にお
けるラベル付け方式。