JPH03190300A - 半導体装置の配線方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 半導体装置の配線方法に関し、 人手介入を減らし、高い配線率で高速な配線処理を行う
半導体装置の配線方法を目的とし、複数組存在する配線
区間の出発点から目的点までの区間距離をそれぞれ検出
し、該区間距離に基づいて配線区間から配線順序を決定
する順序決定ステップと、該順序決定ステップによって
決定された順序に従い、前記配線区間の出発点から目的
点までの配線経路を決定する経路決定ステップとからな
り、前記順序決定ステップは、前記配線区間の区間距離
が短い順に配線順序を決定し、前記経路決定ステップに
よる配線経路の決定が所定条件に合わない場合、該所定
条件に合わない配線区間の配線順序を繰り上げて、再び
配線順序の決定を行い、前記経路決定ステップは、出発
点から目的点まで、水平または垂直方向に所定長の仮線
分を引き、該仮線分の途中に障害物が存在するとき、障
害物から一定距離離れた障害物の手前位置まで仮線分を
引く第１の補助ステップと、前記障害物の手前位置から
該障害物が途切れる位置まで、障害物から一定距離離れ
て水平または垂直方向に仮線分を引き、該仮線分の途中
に障害物が存在するとき、障害物から一定距離離れた障
害物の手前位置まで仮線分を引く第２の補助ステップと
からなり、該第１、第２の補助ステップは、水平または
垂直のどちらの方向に対しても仮線分を引（ことが可能
な選択点にある場合、常にいずれか一方向を選択し、選
択の結果、第１、第２の補助ステップによって引かれた
仮線分が所定の条件から外れるとき、再び前記選択点に
戻り、他方向を選択して配線経路を決定するように構成
する。

〔産業上の利用分野〕

本発明は、半導体装置の配線方法に係り、詳しくは、単
層プリント配線板の自動設計の分野に用いて好適な、高
い配線率で高速な配線処理を行う半導体装置の配線方法
に関する。

近年、設計期間の短縮、設計品質の向上、設計工数の削
減等を図るため、プリント配線板の自動設計が盛んに行
われている。中でも、設計者の負担を減らすために設計
工数を削減することが要求されており、この設計工数の
削減を図るため半導体装置の配線方法が数多く開発され
ている。

そして、半導体装置の配線においては、結線できる割合
、すなわち配線率を高くし、短い時間で配線処理できる
ことが必要とされている。

〔従来の技術〕

従来のこの種の半導体装置の配線方法としては、例えば
、プリント配線板に自動的に配線するものがある。この
方法は、複数組の配線区間の配線順序を決定する順序決
定ステップと、この順序決定ステップによって決定され
た配線区間の出発点と目的点との配線経路を決定する経
路決定ステップとの２つのステップからなっている。

順序決定ステップによる配線順序の決定方法は、例えば
、配線区間の短い順に配線順序を決定する最短順序法や
、配線区間の長い順に配線順序を決定する最長順序法等
がある。

最短順序法は高い配線率を得るのに有利であり、最長順
序法は未結線部分ができたとき、人手による修正が容易
であるという長所があり、一般に配線順序の決定方法は
、高い配線率を得るために最短順序法に固定されている
。

また、経路決定ステップによる配線経路の決定方法（以
下、経路探索方法という）は、例えば、演算時間が短く
、高速な配線処理が可能な線分探索法や、複雑な経路に
おいても最短経路で配線経路を探索できる迷路法等があ
る。

線分探索法による配線経路の決定方法は第５図（ａ）に
示す。この図において、Ａは出発点、Ｂは目的点、１０
１ａ、　１０１ｂは障害物、Ｓは配線経路である。まず
、出発点Ａと目的点Ｂとを通る水平の仮線分を引き、こ
の仮線分をレベルＯ線分（図中、実線で示す）とし、さ
らに、これらのレベル０線分に垂直な仮線分をレベル１
線分（図中、短波線で示す）として引く。以下、同様な
操作を繰り返し、１つずつ大きくしたレベルの仮線分（
図中、長波線で示す）を引き、出発点Ａと目的点Ｂとの
２点からの仮線分同士が交わるまで処理を行う。

仮線分が交差した場合、この交差した点から仮線分を逆
にたどることによって、同図（ｂ）に示すように、配線
経路Ｓを見い出す方法である。すなわち、仮線分のデー
タをもつだけで処理が可能であるので、記憶容量が少な
くて済み、演算時間も短くて済む。しかし、線分探索法
においては、レベルが大きくなるにしたがって仮線分の
本数が指数関数的に増加し、これらの仮線分の間の組み
合わせから交点を求めることは容易でない。そこで、線
分探索法を実際に用いるにはレベルの上限を決める必要
があり、複雑な経路の場合は配線経路を見い出せないと
いう短所がある。

迷路法による配線経路の決定方法は第６図（ａ）〜（ｄ
）に示す。この図において、Ａは出発点、Ｂは目的点、
１０１ｃは障害物、Ｓは配線経路である。

まず、配線区間を格子状に分割し、同図（ａ）に示すよ
うに、出発点Ａに隣接する格子にラベル１を付ける。次
に、同図（ｂ）に示すように、ラベル１の格子に隣接す
る格子にラベル２を付け、以下、同図（ｃ）に示すよう
に、同様な操作を繰り返し、ラベルが目的点Ｂに到達す
るまでラベルの番号を１つずつ増やしてラベル付けを行
う。そして、同図（ｄ）に示すように、ラベルが目的点
Ｂまで達したとき、このラベルが付けられた格子を番号
順にたどることで、配線経路Ｓを見い出すことができる
。すなわち、見つけられた経路は最短経路になっており
、経路が存在する場合は必ず配線経路Ｓを見い出すこと
ができる。しかし、迷路法においては、格子数分に相当
する多くの記憶容量と長い演算時間とを要するため、迷
路法を実際に用いるには配線区間を限定しなければなら
ないという短所がある。

したがって、線分探索法と迷路法との各経路探索方法は
各々重大な短所をもっており、どちらか一方だけを限定
して用いるわけにはいかない。そこで、一般に経路探索
方法は、配線処理の前段において可能な限り線分探索法
を用い、残りの配線処理に迷路法を用いている。

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

しかしながら、このような従来の半導体装置の配線方法
にあっては、順序決定ステップと経路決定ステップとの
各ステップにおいてそれぞれ以下に述べるような問題点
があった。

順序決定ステップでは、最短順序法で固定されていたた
め、配線順序は一方的に配線区間の短い順に決定されて
おり、配線順序に対して融通性に劣っていた。すなわち
、−度配線が行われると通常、引き直しや削除、修正等
はなされないため、配線順序が固定されるということは
、適切な配線順序でないとき、配線率の低下を招くとい
う問題点があった。

また、経路決定ステップにおいては、線分検索法と迷路
法との組み合わせにより行っているので、これら線分検
索法と迷路法との配線処理ルーチンを複数用意しなけれ
ばならない。すなわち、設計者が経験に基づき、処理状
況に応じてどの配線処理ルーチンを走らせるかを決定す
るようなシステム構成としたり、処理の途中で人手介入
による既配線の削除や修正を行い、再び処理に戻るよう
なシステム構成とする必要があった。したがって、人手
介入により配線処理時間の短縮化が妨げられるという問
題点があった。

そこで本発明は、人手介入を減らし、高い配線率で高速
な配線処理を行う半導体装置の配線方法を提供すること
を目的としている。

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

本発明による半導体装置の配線方法は上記目的を達成す
るため、複数組存在する配線区間の出発点から目的点ま
での区間距離をそれぞれ検出し、該区間距離に基づいて
配線区間から配線順序を決定する順序決定ステップと、
該順序決定ステップによって決定された順序に従い、前
記配線区間の出発点から目的点までの配線経路を決定す
る経路決定ステップとからなり、前記順序決定ステップ
は、前記配線区間の区間距離が短い順に配線順序を決定
し、前記経路決定ステップによる配線経路の決定が所定
条件に合わない場合、該所定条件に合わない配線区間の
配線順序を繰り上げて、再び配線順序の決定を行い、前
記経路決定ステップは、出発点から目的点まで、水平ま
たは垂直方向に所定長の仮線分を引き、該仮線分の途中
に障害物が存在するとき、障害物から一定距離離れた障
害物の手前位置まで仮線分を引く第１の補助ステップと
、前記障害物の手前位置から該障害物が途切れる位置ま
で、障害物から一定距離離れて水平または垂直方向に仮
線分を引き、該仮線分の途中に障害物が存在するとき、
障害物から一定距離離れた障害物の手前位置まで仮線分
を引く第２の補助ステップとからなり、該第１、第２の
補助ステップは、水平または垂直のどちらの方向に対し
ても仮線分を引くことが可能な選択点にある場合、常に
いずれか一方向を選択し、選択の結果、第１、第２の補
助ステップによって引かれた仮線分が所定の条件、から
外れるとき、再び前記選択点に戻り、他方向を選択して
配線経路を決定するようにしている。

〔作用〕

本発明では、順序決定ステップで１度決定された配線順
序であっても、経路決定ステップによる配線経路の決定
が所定条件に合わない場合、この所定条件に合わない配
線区間の配線順序が繰り上げられて、再び配線順序の決
定が行われる。

したがって、配線順序が固定されることなく動的に決定
され、融通性に冨んだ配線順序決定がなされる。

また、経路決定ステップで決定された配線が所定の条件
から外れている場合、残された配線可能な経路がなくな
るまで配線がやり直される。

したがって、人手介入に顧ることなく配線処理が実行さ
れる。

〔実施例〕

以下、本発明を図面に基づいて説明する。

第１〜４図は本発明に係る半導体装置の配線方法の一実
施例を示す図である。

第１図は本配線方式を実現するための装置の全体構成図
であり、この図において、１は配線順序を決定する順序
決定ステップの処理を行う順序決定手段、２は順序決定
手段１によって決定された配線順序に従い、配線経路を
決定する経路決定ステップの処理を行う経路決定手段で
あり、この経路決定手段２は第１の補助ステップの処理
を行う第１の配線部３と、第２の補助ステップの処理を
行う第２の配線部４とからなり、さらに、第１の配線部
３、第２の配線部４はそれぞれＸ方向処理部３ａ、４ａ
　％　Ｘ方向処理部３ｂ、４ｂから構成されている。

第１の配線部３、第２の配線部４の具体的な処理内容は
第２図に示す。なお、第２図において使用される図記号
の意味は、同図中に記す。ここで、第１の配線部３のＸ
方向処理部３ａは、単層のプリント基板の水平方向（Ｘ
方向）に所定長の仮線分を引き、この仮線分の途中に障
害物が存在するとき、障害物から一定距離離れた障害物
の手前位置まで仮線分を引く関数■の処理を行い、同様
にＸ方向処理部３ｂは、単層のプリント基板の垂直方向
（Ｘ方向）に所定長の仮線分を引き、この仮線分の途中
に障害物が存在するとき、障害物から一定距離離れた障
害物の手前位置まで仮線分を引く関数■の処理を行う。

そして、第２の配線部４のＸ方向処理部４ａは、障害物
の手前位置から障害物が途切れるまで、障害物から一定
距離離れて水平方向（Ｘ方向）に仮線分を引き、この仮
線分の途中に障害物が存在するとき、障害物から一定距
離離れた障害物の手前位置まで仮線分を引く関数■の処
理を行い、同様にＸ方向処理部４ｂは、障害物の手前位
置から障害物が途切れるまで、障害物から一定距離離れ
て垂直方向（Ｘ方向）に仮線分を引き、この仮線分の途
中に障害物が存在するとき、障害物から一定距離離れた
障害物の手前位置まで仮線分を引く関数■の処理を行う
。これらの関数Ｉ〜■の処理はＸ方向、Ｘ方向に対して
それぞれ正方向、負方向に２種類の処理があり、正方向
の関数を関数１４．関数■゛、、関数１”、関数■゛、
負方向の関数を関数Ｉ−、関数■−２関数■−２関数■
−と表わし、正方向の処理は負方向の処理よりも優先度
を高くしている。そして、関数■および関数■の起動に
よる配線処理後は関数■または関数■を起動し、逆に、
関数■および関数■の起動による配線処理後は関数Ｉま
たは関数■を起動するようになっており、関数Ｉ、ＩＩ
は関数■、■よりも優先度を高くしている。

以上の構成において、順序決定手段ｌは、外部から入力
される複数組の配線区間データの中から区間距離を算出
して検出し、この区間距離の短い順に配線区間の並べ替
え処理（以下、ソートという）を行う。そして、ソート
された配線区間の順序を経路決定手段２に送り、この経
路決定手段２は順序決定手段１から送られた配線順序に
基づいて第１、第２の配線部３，４により配線経路を決
定し、実行部（図示せず）により配線処理を行う。

次に、作用を説明する。

まず、順序決定手段１による配線順序の決定は、外部か
ら順序決定手段１に入力された複数組の配線区間データ
、障害物データ等により、複数組の配線区間の出発点Ｐ
ｓ＝　（Ｘｓ　、　Ｙｓ）から目的点Ｐｅ＝　（Ｘｅ。

Ｙｅ）までの区間距離（＝■π−Ｘｓ）　”＋　（Ｙｅ
−π五）がそれぞれ順序決定手段１によって算出されて
検出され、この区間距離が短い順に配線順序が決定され
る。

ここで、区間距離の短い順にＡ、Ｂ、Ｃ，Ｄ。

Ｅの５つの配線区間が存在する場合を仮定すると、順序
決定手段１によって最初に配線順序がＡ、　Ｂ。

Ｃ，Ｄ、Ｅの順に決定される。そして、順序決定手段１
によって決定された配線順序のデータは、この順序決定
手段１から経路決定手段２に送られ、経路決定手段２に
よってＡ、Ｂ、Ｃ，Ｄ、Ｅの順序に配線処理が行われる
。このＡ、　Ｂ、　Ｃ，Ｄ。

Ｅの順序に配線処理が行われる過程を第３図の配線順序
の決定過程を示すツリー図に基づいて説明する。この図
において、実線は実行された手順を示し、破線は実行さ
れなかった手順を示す。

図中、処理（１）〜（３）に示すように、配線Ａ−Ｃの
処理が行われ、経路決定手段２によって配線りの処理（
処理（４））ができなかった場合、経路決定手段２から
順序決定手段１にステータスとして例えば−ｌを返すこ
とにより経路決定手段２による配線の失敗が順序決定手
段１に認識され、この順序決定手段１によって、失敗し
た配線りと、この配線りの前の配線Ｃとの配線順序が替
えられ配線りの順序が繰り上げられる。そして、配線Ｂ
の処理から配線りの処理（処理（５））が行われ、経路
決定手段２によって配線Ｃの処理（処理（６））ができ
なかった場合、今度は失敗した配線Ｃと、この配線Ｃの
前の配＆’Ｈ３との配線順序が替えられ配線Ｃの順序が
繰り上げられる。以下、同様に処理（７）〜（１２）が
繰り返される。第３図においては、処理（１２）で全部
の結線が終わり、処理が終了される。

すなわち、経路決定手段２において１＆ｌｌの配線区間
の結線ができない場合、所定の条件に合致するまで再帰
的な後戻り処理（以下、バンクトランクという）が行わ
れる。

したがって、配線順序が固定されることによって配線率
が低下することを防止できる。

次に、経路決定手段２による配線経路の決定は、順序決
定手段１から入力される配線順序に従い、配線区間デー
タ、障害物データ等により、第２図に示すような４つの
関数による処理が動的に起動されて、その配線区間の出
発点から目的点までの区間の配線処理がなされるもので
あり、具体的には第４図（ａ）〜（ｑ）の１組の２点間
の配線過程を示すツリー図に基づいて説明する。この図
において、Ｐｓは出発点、Ｐｅは目的点、１０．１１は
障害物、Ｓは配線経路である。

この経路決定手段２の処理によってバンクトランクが行
われる条件は、発生させる仮線分の本数がＮ（この場合
、Ｎ＝４）を越えた場合、障害物が今回の配線処理で引
かれた配線経路であった場合、および、過去に失敗した
経路を再び通る場合の３つの場合である。

初期設定が同図（ａ）に示され、関数ｌ゛が起動されて
出発点Ｐｓから目的点Ｐｅに水平方向（Ｘ方向）の仮線
分が引かれる。この場合、障害物１１が存在するので関
数ドによって障害物１１から一定距離離れた障害物ＩＩ
の手前位置まで仮線分が引かれる（処理■）。次に、同
図（ｂ）に示すように、関数■゛が起動されて障害物１
１０手前位置から障害物１１が途切れる位置まで障害物
１１から一定距離離れて垂直方向（ｙ方向）の仮線分が
引かれる（処理■）。そしてさらに、同図（ｃ）に示す
ように、関数ビが起動され（処理■）、この場合も同図
（ｄ）に示すように障害物１０が存在するので、関数■
゛によって障害物１０の手前位置まで仮線分が引かれる
（処理■）。この仮線分が引かれた位置の正方向は障害
物１０が存在するので、次は関数■−が同図（ｅ）に示
すように、起動される（処理■）。

ここで、Ｎ＝５となり、仮線分の本数が４を越えるため
、同図（ｄ）　、　（ｅ）の過程で引かれた仮線分が削
除され、最も近い選択点である同図（ｃ）の位置までバ
ンクトラックが行われる。以下、同様にして処理■〜［
相］が行われ、目的点Ｐｅに達する。そして、１組の配
線区間の結線が終了したとき、さらに選択点が残されて
いても経路探索を終了し、次の紐の経路探索が行われる
。全ての手順に失敗した場合、この組の配線経路が全て
削除され、順序決定手段１に配線が失敗した旨を伝える
ためのステータスが返される。これによって、この配線
区間の配線順序が順序決定手段１により早められて処理
が行われる。

したがって、処理の途中で人手介入による既配線の削除
や修正を行うことが不要となり、人手介入による配線処
理時間の短縮化が図れる。

なお、本実施例においては、経路決定手段２の処理によ
ってバックトラックが行われる条件として仮線分の本数
がＮ＝４を越えた場合としているが、これに限らず、種
々の条件によって任意に選択可能であることはいうまで
もない。

〔発明の効果〕

本発明によれば、配線処理の途中に人手が介入すること
がないので、人手介入による処理の低下を抑えることが
できるとともに、配線の過程においてＡＩ的な手法を取
り入れてバックトラックを行うことで、高い配線率を得
ることができる。

したがって、高い配線率で高速な配線処理を行うことが
できる。

【図面の簡単な説明】

第１〜４図は本発明に係る半導体装置の配線方法を実現
する装置の一実施例を示す図であり、第１図はその全体
構成図、 第２図はその経路決定ステップでの処理内容を示す図、 第３図はその配線順序の決定過程を示すツリー図、 第４図はその経路探索の決定過程を示すツリー図、 第５図は従来の線分探索法による配線経路の決定方法を
示す図、 第６図は従来の迷路法による配線経路の決定方法を示す
図である。 ３・・・・・・第１の配線部（第１の補助ステップ）、
３ａ・・・・・・Ｘ方向処理部、 ３ｂ・・・・・・Ｘ方向処理部、 ４・・・・・・第２の配線部（第２の補、助ステップ）
、４ａ・・・・・・Ｘ方向処理部、 ４ｂ・・・・・・Ｘ方向処理部。 １・・・・・・順序決定手段（順序決定ステップ）、２
・・・・・・経路決定手段（経路決定ステップ）、レベ
ル０線分 一一一一一一一レベル１線分 一一一一一レベル２線分 （６） 従来の線分探索法による配線経路の決定方法を示す図第
５図

Claims (1)

1. 【特許請求の範囲】 　複数組存在する配線区間の出発点から目的点までの区
   間距離をそれぞれ検出し、該区間距離に基づいて配線区
   間から配線順序を決定する順序決定ステップと、 該順序決定ステップによって決定された順序に従い、前
   記配線区間の出発点から目的点までの配線経路を決定す
   る経路決定ステップとからなり、前記順序決定ステップ
   は、前記配線区間の区間距離が短い順に配線順序を決定
   し、前記経路決定ステップによる配線経路の決定が所定
   条件に合わない場合、該所定条件に合わない配線区間の
   配線順序を繰り上げて、再び配線順序の決定を行い、前
   記経路決定ステップは、出発点から目的点まで、水平ま
   たは垂直方向に所定長の仮線分を引き、該仮線分の途中
   に障害物が存在するとき、障害物から一定距離離れた障
   害物の手前位置まで仮線分を引く第１の補助ステップと
   、 前記障害物の手前位置から該障害物が途切れる位置まで
   、障害物から一定距離離れて水平または垂直方向に仮線
   分を引き、該仮線分の途中に障害物が存在するとき、障
   害物から一定距離離れた障害物の手前位置まで仮線分を
   引く第２の補助ステップとからなり、 該第１、第２の補助ステップは、水平または垂直のどち
   らの方向に対しても仮線分を引くことが可能な選択点に
   ある場合、常にいずれか一方向を選択し、選択の結果、
   第１、第２の補助ステップによって引かれた仮線分が所
   定の条件から外れるとき、再び前記選択点に戻り、他方
   向を選択して配線経路を決定することを特徴とする半導
   体装置の配線方法。