JPH11296560A

JPH11296560A - 配線設計装置およびその方法

Info

Publication number: JPH11296560A
Application number: JP10069677A
Authority: JP
Inventors: Hiroyuki Matsumoto; 本浩之松; Minoru Katsumata; 又実勝; Kazuhiko Hirayama; 山和彦平
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1998-03-19
Filing date: 1998-03-19
Publication date: 1999-10-29
Anticipated expiration: 2018-03-19
Also published as: JP3184796B2; US6510544B1

Abstract

(57)【要約】【課題】デザインルールを守り、かつ、局所的な配線集
中を抑えて配線設計を行なうことができる配線設計装置
およびその方法を提供する。【解決手段】配線設計ソフトウェア３は、デザイン情報
を読み込み、解析して配線問題を作成し、半導体パッケ
ージのボンディグパッドおよびピンを互いに対応付ける
(S102,S104)。次に、経路の監視に用いる監視辺Ｅを任
意のシンク要素および配線禁止領域の間に作成する(S10
6,S108)。次に、ダイクストラ法等により配線経路の探
索を交差を許して行ない、監視辺Ｅと交差する場合には
候補経路の長さを係数Ｗにより重み付けした評価値を算
出し、評価値が最低の値をとる候補経路を部分経路とし
て選択する(S110)。最後に、配線結果を出力する(S11
2)。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、例えば、半導体チップ
に設けられたボンディングパッドと、半導体パッケージ
に設けられたピン（端子）との間で最適な配線の経路を
設計する配線設計装置およびその方法に関する。

【０００２】

【従来の技術】電子機器に用いられるプリント基板の配
線、あるいは、半導体チップのボンディングパットと半
導体パッケージのピン（端子）との間等の配線設計を、
自動的または半自動的に行なう配線設計装置が、「特開
平５−１４３６８９号公報（文献１）」等に開示されて
いる。これらの従来技術を用いると、半導体パッケージ
の配線等を、ピンの間隔およびピンの間に占める配線幅
の上限等を示すデザインルールに従って、自動的または
半自動的に行なうことができる。

【０００３】しかしながら、これらの従来技術による配
線設計の結果には、部品の配置およびピンの位置関係等
の条件に起因して、局所的な配線の集中が含まれてしま
うことがある。局所的な配線集中は、製品の電気的特性
を低下させることがあるので、解消されなければならな
い。このような配線集中を解消するためには、人手によ
る配線の修正あるいは部品配置等の変更等の方法が従
来、採られていた。

【０００４】

【発明が解決しようとする課題】本発明は、上述した従
来技術の問題点に鑑みてなされたものであり、デザイン
ルールを守り、しかも、局所的な配線集中を含まない配
線設計を、自動的に行なうことができ、人手による配線
および部品配置の修正を不要にする配線設計装置および
その方法を提供することを目的とする。

【０００５】また、本発明は、部品配置および相互に接
続されるピンの位置関係等のネット情報によらず、デザ
インルールを守り、かつ、局所的な配線集中を抑えて配
線設計を行なうことができる配線設計装置およびその方
法を提供することを目的とする。

【０００６】

【課題を達成するための手段】［配線設計装置］上記目
的を達成するために、本発明にかかる配線設計装置は、
１つの面上に設けられた複数の端点同士を、前記面上の
配線禁止領域以外を通る経路で接続する配線を設計する
配線設計装置であって、前記端点および前記面上の配線
禁止領域（要素）の任意の２つの間それぞれに仮想的な
配線密度監視用の辺（監視辺）を作成する監視辺作成手
段と、前記監視辺それぞれと交差する配線の幅に基づい
て、前記端点同士を接続する配線の経路（配線経路）を
設計する配線設計手段とを有する。

【０００７】好適には、前記配線設計手段は、少なくと
も前記要素の間隔、前記要素の間に占める前記配線の幅
の割合（配線密度）、前記要素間隔前記配線の間隔およ
び前記配線の幅を示すデザインルールに従って配線経路
を作成する。

【０００８】好適には、前記配線設計手段は、前記配線
それぞれが始まる端点から、前記配線それぞれが終わる
端点まで、前記配線それぞれの経路を１つ以上に分けた
部分（部分経路）ごとに、前記デザインルールに従って
前記配線それぞれの経路を順次、探索し、１つ以上の前
記部分経路の候補（候補経路）を作成する候補経路作成
手段と、作成された前記候補経路それぞれの経路長と、
前記候補経路と交差する監視辺の配線密度とに基づい
て、前記候補経路それぞれの経路長が長ければ長いほ
ど、前記候補経路それぞれが交差する前記監視辺と交差
する配線の幅が広ければ広いほど大きな値をとる前記候
補経路それぞれの経路長評価値を算出する経路長評価手
段と、作成された前記候補経路の内、算出された前記経
路長評価値が最小になるいずれかを前記部分経路として
選択する経路選択手段と、選択された前記部分経路を接
続して、前記配線それぞれの経路を設計する部分経路接
続手段とを有する。

【０００９】好適には、前記経路長評価手段は、作成さ
れた前記候補経路それぞれと交差する前記監視辺の配線
密度が大きければ大きいほど大きい値をとる重み付け係
数と、前記候補経路それぞれの経路長とを乗算して、前
記経路長評価値を算出する。

【００１０】好適には、前記候補経路作成手段は、他の
配線経路との交差を許して前記候補経路を作成し、前記
経路長評価算出手段は、交差を許して作成された前記候
補経路の経路長評価値を算出し、前記経路選択手段は、
選択した前記部分経路と他の配線経路とが交差する場
合、交差が解消するように選択した前記部分経路と他の
配線経路とを変更する。

【００１１】［配線設計装置の作用］本発明にかかる配
線設計装置は、監視辺上の配線密度を考慮して配線経路
を導出することにより、例えば、半導体チップのボンデ
ィングパッドと、半導体パッケージのピン（端子）との
間を、半導体パッケージの配線禁止領域を避け、デザイ
ンルールを守り、しかも、配線の局所的集中を抑えつ
つ、半導体パッケージの配線面上を通る経路で接続する
配線を設計する。以下、半導体チップのピンと半導体パ
ッケージの（端子）ピンとの接続を例として説明する。

【００１２】［監視辺作成手段］監視辺作成手段は、例
えば、半導体パッケージの配線面の内、経験的に配線が
集中しがちな部分、例えばピングリッドアレイのピンの
配列の角の部分に配置された隣接する端子ピンの間、あ
るいは、隣接するピンと禁止領域との間に、配線集中が
発生しているか否かを判定するために用いる仮想的な辺
（監視辺）を作成する。

【００１３】［配線設計手段］配線設計手段は、半導体
パッケージのピンと半導体チップのボンディングパッド
との接続関係を示すデザイン情報、および、ピンおよび
禁止領域（これらをまとめて要素とも記す）の２つの間
の配線密度（要素の間隔に占める配線幅）に基づいて、
ボンディングパッドから順次、部分経路を伸ばす。さら
に、配線設計手段は、監視辺上の配線密度を緩和するよ
うに部分経路を順次、選択し、ピンとボンディングパッ
ドとの間の配線経路を設計する。

【００１４】［候補経路設計手段］配線設計手段におい
て、候補経路設計手段は、例えば、デザインルールに従
って、ダイクストラ(Dijkstra)法等の探索アルゴリズム
により、配線の始点から終点に向けて、節点と次の節点
とを繋ぎ得る経路の候補を、他の配線との交差を許して
１つ以上、作成する。つまり、候補経路設計手段は、順
次、ボンディングパッドから最初の節点まで、節点から
次の節点まで、あるいは、節点からピンまでをつなく経
路を可能なかぎり多く作成し、これらを候補経路とす
る。

【００１５】［経路長評価手段］経路長評価手段は、候
補経路が監視辺と交差しない場合には、その候補経路の
長さをそのまま経路長評価値とし、候補経路が監視辺と
交差する場合には、それまでに監視辺を交差する経路を
通るように引かれた配線の監視辺における配線密度に応
じた係数を、その候補経路の長さに乗算して経路評価値
とする。例えば、経路長評価手段は、他に全く配線が交
差しない監視辺と候補経路が交差した場合には係数を１
とし、配線密度が５０％以上の監視辺と候補経路が交差
した場合には係数を１０とするなど、候補経路の長さが
ければ長いほど、また、候補経路と交差する監視辺の配
線密度が高ければ高いほど高い値をとる経路評価値を算
出する。

【００１６】［経路選択手段］経路選択手段は、最も経
路評価値が低い値をとる候補経路を、その節点（ピン，
ボンディングパッド）間における部分経路として選択す
る。つまり、経路選択手段は、長さが短く、かつ、配線
密度が低い監視辺を通る候補経路をその区間における部
分経路として選択し、異常に長い候補経路、および、長
さが短くても局所的に配線が集中している部分を通る部
分経路を排除することにより、配線長と配線密度との最
適化を図る。さらに、経路選択手段は、選択した候補経
路が他の配線と交差している場合には、この交差を解消
しうるようにデザイン情報を自動的に修正する。

【００１７】［配線設計方法］また、本発明にかかる配
線設計方法は、１つの面上に設けられた複数の端点同士
を、前記面上の配線禁止領域以外を通る経路で接続する
配線を設計する配線設計方法であって、前記端点および
前記面上の配線禁止領域（要素）の任意の２つの間それ
ぞれに仮想的な配線密度監視用の辺（監視辺）を作成
し、少なくとも前記要素の間隔、前記要素の間隔に占め
る前記配線の幅の割合（配線密度）、前記要素間隔前記
配線の間隔および前記配線の幅を示すデザインルールに
従って、前記配線それぞれが始まる端点から、前記配線
それぞれが終わる端点まで、前記配線それぞれの経路を
１つ以上に分けた部分（部分経路）ごとに、前記配線そ
れぞれの経路を順次、探索し、１つ以上の前記部分経路
の候補（候補経路）を作成し、作成された前記候補経路
それぞれの経路長と、前記候補経路と交差する監視辺の
配線密度とに基づいて、前記候補経路それぞれの経路長
が長ければ長いほど、前記候補経路それぞれが交差する
前記監視辺と交差する配線の幅が広ければ広いほど大き
な値をとる前記候補経路それぞれの経路長評価値を算出
し、作成された前記候補経路の内、算出された前記経路
長評価値が最小になるいずれかを前記部分経路として選
択し、選択された前記部分経路を接続して、前記配線そ
れぞれの経路を設計する。

【００１８】［記録媒体］また、本発明にかかる記録媒
体は、１つの面上に設けられた複数の端点同士を、前記
面上の配線禁止領域以外を通る経路で接続する配線を設
計するプログラムであって、前記端点および前記面上の
配線禁止領域（要素）の任意の２つの間それぞれに仮想
的な配線密度監視用の辺（監視辺）を作成する監視辺作
成ステップと、前記監視辺それぞれと交差する配線の幅
に基づいて、前記端点同士を接続する配線の経路（配線
経路）を設計する配線設計ステップとを含むプログラム
を記録する。

【００１９】

【発明の実施の形態】以下、本発明の実施形態を説明す
る。なお、以下、本発明を半導体パッケージの配線に応
用する場合を例として説明するが、本発明はこれ以外
に、プリント基板の設計等、広い用途に応用可能であ
る。

【００２０】［コンピュータネットワーク１］以下、本
発明にかかる配線設計方法および配線判定方法が適応さ
れるコンピュータネットワーク１を説明する。図１は、
本発明が適応されるコンピュータネットワーク１の構成
を例示する図である。図１に示すように、コンピュータ
ネットワーク１は、ｎ台のクライアントコンピュータ１
０、通信回線１８およびサーバコンピュータ２０から構
成される（但し、図１はｎ＝１の場合を例示）。

【００２１】図２は、図１に示したクライアントコンピ
ュータ１０とサーバコンピュータ２０との間の機能分担
を例示する図である。また、図２に例示するように、コ
ンピュータネットワーク１において、クライアントコン
ピュータ１０は、半導体チップの設計を行なうＣＡＤ(c
omputer aided design)ソフトウェア１２０を実行し、
サーバコンピュータ２０は、半導体チップのボンディン
グパッドと半導体パッケージのピンとの間の配線を設計
する配線設計ソフトウェア３を実行する。なお、本発明
にかかる配線設計方法は、図２に例示した構成の他、同
一のコンピュータが、ＣＡＤソフトウェア１２０と配線
設計ソフトウェア３とを実行する構成によっても実現さ
れうる。

【００２２】コンピュータネットワーク１は、これらの
構成部分により、半導体チップのボンディングパッドの
位置を示す情報（パッド位置情報）、半導体パッケージ
の端子（ピン）の位置を示す情報（ピン位置情報）、ボ
ンディングパッドとピンとの接続関係を示す情報（配線
情報）、および、半導体パッケージの配線面において、
配線を通すことが禁じられる領域（配線禁止領域）を示
す情報（配線禁止領域情報）に基づいて、ボンディング
パッドとピンとの間を、配線長がなるべく短くなり、し
かも、配線が局所的に集中しないような経路で接続する
配線を設計する。なお、以下、パッド位置情報、ピン位
置情報および配線情報を総称して、「デザイン情報」と
も記す。なお、デザイン情報は、例えば、下表１に示す
ような形式で、配線（ＮＥＴ）と、ボンディングパッド
（Ｐａｄ）と、ピン（Ｐｉｎ）とを対応付けたデータ構
造をとる。

【００２３】

【表１】（表１：デザイン情報の例）ＮＥＴ−Ａ，Ｐａｄ１，Ｐｉｎ２０ＮＥＴ−Ｂ，Ｐａｄ１３，Ｐｉｎ４ＮＥＴ−Ｃ，Ｐａｄ２５，Ｐｉｎ１５ＮＥＴ−Ｄ，Ｐａｄ１１，Ｐｉｎ９４・・

【００２４】［通信回線１８］通信回線１８は、データ
通信が可能なＬＡＮ、データ専用回線、ＩＳＤＮ回線あ
るいは電話回線等あって、クライアントコンピュータ１
０とサーバコンピュータ２０との間でデータを伝送す
る。

【００２５】［クライアントコンピュータ１０］クライ
アントコンピュータ１０は、図１に示すように、コンピ
ュータ本体１００、ＣＲＴ表示装置あるいは液晶表示装
置等のディスプレイ装置１０２、入力装置１０４、プリ
ンタ装置およびプロッタ装置等を含む出力装置１１０、
ハードディスク装置あるいは光磁気（ＭＯ）ディスク装
置等の記憶装置１１２、および、通信装置１１４から構
成される。

【００２６】［入力装置１０４］入力装置１０４は、キ
ーボード１０６およびマウス１０８等を含み、ユーザの
操作に応じて半導体回路の設計あるいは設計変更に必要
な情報、および、半導体パッケージのピン配置に関する
情報を受け入れ、コンピュータ本体１００に対して出力
する。

【００２７】［記憶装置１１２］記憶装置１１２は、図
２に示したＣＡＤソフトウェア１２０、入力装置１０４
を介して入力された情報、ＣＡＤソフトウェア１２０に
より設計された半導体回路を示す情報、設計した半導体
回路を実際の半導体チップとして実現した場合の回路配
置およびボンディングパッドの配置を示す情報、およ
び、サーバコンピュータ２０から伝送されてきた半導体
チップのピンとボンディングパッドとの間の配線を示す
情報等のデータを記憶し、記憶したデータを、要求に応
じてコンピュータ本体１００に対して出力する。

【００２８】［通信装置１１４］通信装置１１４は、イ
−サネットアダプタ、トークンリングアダプタ、ＦＤＤ
Ｉ、ＴＡ(terminal adapter)あるいはモデム等であっ
て、コンピュータ本体１００の制御に従って、通信回線
１８を介して、クライアントコンピュータ１０とサーバ
コンピュータ２０との間のデータ伝送を行なう。

【００２９】［コンピュータ本体１００］コンピュータ
本体１００は、ＣＰＵ、メモリおよびこれらの周辺回路
等から構成され、いわゆるパーソナルコンピュータある
いはワークステーションとしての機能を有し、クライア
ントコンピュータ１０の各構成部分を制御する。

【００３０】［ＣＡＤソフトウェア１２０の処理］ま
た、コンピュータ本体１００は、図２に示したＣＡＤソ
フトウェア１２０を記憶装置１１２からメモリにロード
して実行し、以下の各処理を行なう。コンピュータ本体
１００は、入力装置１０４を介して入力された半導体回
路の設計に必要な情報に基づいて半導体回路を設計し、
さらに、設計した半導体回路の回路配置およびボンディ
ングパッドの配置を設計し、ディスプレイ装置１０２、
出力装置１１０および記憶装置１１２に対して出力す
る。

【００３１】また、コンピュータ本体１００は、設計し
た半導体回路のボンディングパッドの配置、および、ボ
ンディングパッドそれぞれを、半導体パッケージのピン
のいずれに接続するか等を示すデザイン情報を生成し、
サーバコンピュータ２０に対して伝送する（デザイン情
報生成処理）。また、コンピュータ本体１００は、サー
バコンピュータ２０から入力された半導体パッケージの
ピンとビンディングパッドとの間の配線結果をディスプ
レイ装置１０２等に表示してユーザに示す。

【００３２】なお、ディスプレイ装置１０２等に表示さ
れた配線結果が、ピンとボンディングパッドとの間を交
差なく全て配線できない（結線解がない）等の失敗に終
わった場合には、ユーザは、半導体回路およびボンディ
ングパッドの配置を変更し、配線の不正を解消するため
に、入力装置１０４を操作して設計変更情報の入力を行
なう。コンピュータ本体１００は、ユーザが入力した設
計変更情報に基づいて、半導体回路、および／または、
その回路およびボンディングパッドの配置を設計変更
し、さらに、設計結果に基づいて新たなデザイン情報を
生成し、新たなデザイン情報をサーバコンピュータ２０
に対して出力する。

【００３３】［サーバコンピュータ２０］サーバコンピ
ュータ２０は、図１に示すように、コンピュータ本体２
００、記憶装置２０２および通信装置２０４から構成さ
れる。

【００３４】［記憶装置２０２］記憶装置２０２は、図
２に示した配線設計ソフトウェア３、半導体チップのボ
ンディングパッドと半導体パッケージのピンとの間の配
線の設計に必要な情報、および、配線結果等を示すデー
タを記憶し、記憶したデータを、要求に応じてコンピュ
ータ本体２００に対して出力する。

【００３５】［通信装置２０４］通信装置２０４は、通
信装置１１４と同様に、コンピュータ本体２００の制御
に従って、通信回線１８を介して、クライアントコンピ
ュータ１０とサーバコンピュータ２０との間のデータ伝
送を行なう。

【００３６】［コンピュータ本体２００］コンピュータ
本体２００は、コンピュータ本体１００と同様にＣＰ
Ｕ、メモリおよびこれらの周辺回路等から構成され、サ
ーバコンピュータ２０の各構成部分を制御する。

【００３７】［配線設計ソフトウェア３の処理］また、
コンピュータ本体２００は、図２に示した配線設計ソフ
トウェア３を記憶装置２０２からメモリにロードして実
行し、以下に説明するように、クライアントコンピュー
タ１０側から伝送されてきたデザイン情報に基づいて、
半導体チップのボンディングパッドそれぞれと、半導体
パッケージのピンそれぞれとを接続する配線を設計す
る。

【００３８】また、コンピュータ本体２００は、接続解
の有無、どのような不正な配線の有無および不正な配線
が、いずれのボンディングパッドとピンとの間に生じる
か等を示すデータを生成し、配線結果としてクライアン
トコンピュータ１０に対して出力する。

【００３９】図３は、図２に示した配線設計ソフトウェ
ア３の処理を示すフローチャートである。図３に示すよ
うに、ステップ１０２（Ｓ１０２）において、配線設計
ソフトウェア３は、コンピュータ本体２００がクライア
ントコンピュータ１０から受信したデザイン情報を読み
込む。

【００４０】ステップ１０４（Ｓ１０４）において、配
線設計ソフトウェア３は、読み込んだデザイン情報を解
析し、ボンディングパッドおよびピンを半導体パッケー
ジの配線面上の点に置き換え、これらの位置関係を示す
データ（以下、このデータを、配線設計ソフトウェア３
が解いて接続解を求める問題として捉えて、「配線問
題」とも記す）を作成する。

【００４１】図４は、図３に示したソース要素・シンク
要素の分類および対応付け処理（Ｓ１０６）を例示する
図である。ステップ１０６（Ｓ１０６；図３）におい
て、配線設計ソフトウェア３は、図４の左側に示すよう
に、配線問題の半導体パッケージ上のボンディグパッド
およびピンに対応する点を、それぞれ、配線が引き出さ
れるソース要素、および、ソース要素の周囲に位置し
［例えば、半導体パッケージがピングリッドアレイ（Ｐ
ＧＡ）の場合］、ピンに対応する点を、配線が引き込ま
れるシンク要素に分類し、さらに、図４の右側に示すよ
うに、相互に接続されるソース要素とシンク要素とを対
応付けて順次、取り出して記憶する。

【００４２】なお、このソース要素およびシンク要素の
名称は便宜的なものであって、上記とは逆に、ボンディ
ングパッドおよびピンに対応する点を、それぞれシンク
要素およびソース要素と名付けてもよい。また、シンク
要素，ソース要素の名称は、信号の方向と、なんら関係
ない。また、ソース要素およびシンク要素の分類は、ク
ライアントコンピュータ１０側で行なうようにしてもよ
く、さらに、配線設計ソフトウェア３が、Ｓ１０６の処
理において、クライアントコンピュータ１０側で行なわ
れた分類を修正するようにしてもよい。

【００４３】図５は、図３に示した監視辺Ｅの作成処理
を例示する図である。なお、図５において、白丸はシン
ク要素を示し、黒丸は配線禁止領域を示し、点線は配線
経路探索中の配線を示し、"CROSS"は監視辺Ｅと配線と
が交差していることを示す。

【００４４】ステップ１０８（Ｓ１０８；図３）におい
て、配線設計ソフトウェア３は、図５に例示するよう
に、配線の局所的な集中を回避するために、配線経路の
監視に用いる仮想的な辺（監視辺Ｅ）を１つ以上、任意
の２つのシンク要素の間それぞれ、および／または、任
意のシンク要素と配線禁止領域との間に作成する。な
お、監視辺Ｅを全ての隣接する要素の間に作成する必要
はなく、例えば、半導体パッケージの配線面において経
験上、配線が集中しやすいことが判明している部分、お
よび、高い周波数の信号が通る配線が多く、配線集中が
半導体装置の性能を低下させやすい部分等に配置された
隣接する２つのシンク要素および配線禁止領域（これら
を総称して単に要素とも記す）間に作成するとよい。ま
た、監視辺Ｅは、経路探索で使用する探索グラフ、ある
いは、配線設計の結果について容量チェックを行なうた
めに用いられるデータ等で代用することも可能である。

【００４５】監視辺Ｅが満たすべき条件をまとめると、
下表に示す通りとなる。

【００４６】

【表２】（表２：監視辺Ｅが満たすべき条件) (1)監視辺Ｅは、長さを持つ (2)監視辺Ｅの両端には２つの要素が、個別に識別可能
に位置する。 (3)監視辺Ｅの両端には、配線経路の探索処理に利用可
能なデザインルールが設定されている。 (4)配線経路探索処理において、監視辺Ｅと部分経路と
が交差するか否かを判定することができる。 (5)部分経路を選択する際に、監視辺Ｅと交差する配線
の幅(複数の配線が交差する場合には配線の幅の総和)を
利用することができる。

【００４７】ステップ１１０（Ｓ１１０；図３）におい
て、配線設計ソフトウェア３は互いに対応するソース要
素とシンク要素との間をそれぞれ接続する配線を設計す
る（ネット発生）。なお、Ｓ１１０の処理において、全
てのソース要素とシンク要素との接続が終了した場合、
および、デザインルールに従った配線が導出できなかっ
たときには、処理を終了し、その旨を示す情報をクライ
アントコンピュータ１０に対して出力する。

【００４８】図６および図７を参照してネット発生処理
をさらに説明する。図６は、図３に示したネット発生処
理（Ｓ１１０）を示すフローチャートである。図７は、
図６に示した交差を許す重み付け探索処理（Ｓ１２２）
を示すフローチャートである。

【００４９】図６に示すように、ステップ１２０（Ｓ１
２０）において、配線設計ソフトウェア３は、監視辺Ｅ
に関する情報、つまり、Ｓ１０８の処理において作成さ
れた監視辺Ｅそれぞれと、いずれの配線とが交差するか
等を示す情報を初期化する。

【００５０】ステップ１２２（Ｓ１２２）において、配
線設計ソフトウェア３は、図７に示す交差を許す重み付
け探索処理を行なう。

【００５１】ここで、以下の説明を明確化するために、
節点、部分経路および候補経路を説明する。節点とは、
例えば、配線の経路を探索するときに、半導体パッケー
ジに仮想的に作成される矩形の格子メッシュの格子辺と
配線経路との交点として定義される。配線設計ソフトウ
ェア３における配線経路の探索は、まず、ソース要素
（半導体チップのボンディングパッド）と最も近い格子
辺上とを結ぶ１つ以上の配線経路を探索し、さらに、格
子辺上の節点から最も近い他の格子辺上の節点へと配線
経路を順次、伸ばすように探索し、最後に、シンク要素
から最も近い格子辺上の節点からシンク要素への配線経
路を探索することにより行なわれる。このように、節点
は配線経路の探索において重要な役割を果たす。

【００５２】また、ソース要素と節点、節点同士、およ
び、節点とシンク要素とを接続する配線経路それぞれを
部分経路と呼び、また、実際に部分経路と選択されるか
否かを問わず、部分経路となりうる配線経路として探索
された配線経路を部分経路と呼ぶ。

【００５３】ステップ１４０（Ｓ１４０）において、配
線設計ソフトウェア３は、最後にソース要素と接続され
た節点（最新の節点）と、配線容量の条件を満たして接
続可能な次の節点があるか否かを判断する。接続可能な
節点がある場合には、配線容量がデザインルールを満た
すか否かのチェックを行なうダイクストラ法等を用い
て、最新の節点と次の節点とを接続し得るあらゆる経路
を探索してＳ１４２の処理に進み、接続可能な節点がな
い場合には処理を終了し、次の配線の経路探索処理に進
む。なお、格子メッシュと配線との交点を節点としたダ
イクストラ法を適用することにより、効率よく最短経路
探索を行なうことができる。また、この時に既に探索済
みとなっている他の配線経路と、新たに探索された配線
経路との交差は許されうる。

【００５４】ステップ１４２（Ｓ１４２）において、配
線設計ソフトウェア３は、Ｓ１４０の処理において探索
された候補経路のいずれかと監視辺Ｅとが交差するか否
かを判断し、交差しない場合にはＳ１５２の処理に進
み、交差する場合にはＳ１４４の処理に進む。

【００５５】ステップ１４４（Ｓ１４４）において、配
線設計ソフトウェア３は、処理の対象となっている配線
と、Ｓ１４２の処理において交差が判定された監視辺Ｅ
と交差する他の配線の幅の総和が、監視辺Ｅの長さに占
める割合（配線密度）に応じた重み付け係数Ｗを導出す
る。

【００５６】なお、重み付け係数Ｗの値は、１以上の実
数であって、候補経路と交差する監視辺の配線密度が高
ければ高いほど大きい値をとる。また、配線設計ソフト
ウェア３は、例えば、配線密度を所定の関数に代入する
ことにより導出しても、あるいは、予め実験等により、
各配線密度の値に対して最適な値として求められた重み
付け係数Ｗと配線密度の値とを対応付けたテーブルを参
照することにより導出してもよい。この重み付け係数と
配線密度とのテーブルを下表に例示する。この重み付け
係数は、デザイン情報によって最適値が異なることが予
想されるので、配線問題の内容あるいは処理結果に応じ
て重み付け係数も変更できるようにしておくことが好ま
しい。

【００５７】

【表３】（表３：重み付け係数と配線密度との対応テーブル）監視辺Ｅ上の配線密度（％）：重み付け係数Ｗ（倍）０（以上）〜５０（未満）：１５０〜７０：５７０〜８０：１０８０〜９０：２０９０〜１００：４０１００：当該監視辺上を配線不可能と判定する

【００５８】ステップ１４６（Ｓ１４６）において、配
線設計ソフトウェア３は、候補経路の長さとＳ１４４に
おいて導出された重み付け係数Ｗとを乗算することによ
り、その候補経路の経路長評価値を算出する。

【００５９】ステップ１４８（Ｓ１４８）において、配
線設計ソフトウェア３は、監視辺と交差しない候補経路
の長さをそのまま経路長評価値とする。

【００６０】ステップ１５０（Ｓ１５０）において、配
線設計ソフトウェア３は、最新の節点と次の節点の間に
探索された全ての候補経路について配線長評価値を算出
したか否かを判断し、全ての候補経路について配線長評
価値を算出した場合にはＳ１５２の処理に進み、これ以
外の場合にはＳ１４２の処理に戻る。

【００６１】ステップ１５２（Ｓ１５２）において、配
線設計ソフトウェア３は、Ｓ１４６までの処理におい
て、配線評価値が最低の値をとる候補経路を選択し、最
新の節点と次の節点との間の部分経路とし、この処理ル
ープにおける「次の節点」を次回の処理ループにおける
「最新の節点」としてＳ１４０の処理に進む。

【００６２】以上説明した重み付け探索処理を、図８〜
図１０を参照してさらに説明する。図８〜図１０は、図
６および図７に示した重み付け探索処理（Ｓ１２２）の
処理を例示する第１〜第３の図である。以下、図８に例
示するように、Ｓ１４０（図７）の処理において、最新
の節点ｓからシンク要素Ｎまで、交差を許す配線経路探
索により２つの候補経路Ａ，Ｂが探索され、候補経路
Ａ，Ｂが、同じ長さの監視辺Ｅ１，Ｅ２にそれぞれ交差
している場合を具体例とする。

【００６３】図８を参照してわかるように、候補経路Ａ
は候補経路Ｂに比べて短いが、候補経路Ｂが交差する監
視経路Ｅ２に既に交差している配線は１本であるのに対
し、候補経路Ａが交差する監視辺Ｅ１には既に２本の配
線が交差している。このような場合に、図９に示すよう
に、Ｓ１２２の処理において、単純に長さが短い候補経
路Ａを部分経路として選択すると、監視経路Ｅ２と交差
する配線は１本だけであるのに対し、監視経路Ｅ１と交
差する配線は３本となり、局所的な配線の集中が発生す
る。

【００６４】一方、図１０に示すように、Ｓ１２２の処
理において、候補経路Ｂを部分経路として選択すると、
候補経路Ａを選択した場合に比べて配線長は少し長くな
るものの、配線の集中を防ぐことができるので、この部
分の電気的特性を全体として向上させることができる。
つまり、Ｓ１４６（図７）において、候補経路の長さ
に、この候補経路と交差する監視辺の配線密度が高けれ
ば高いほど値が大きくなる重み付け係数Ｗを乗算して重
み付けし、Ｓ１５２の処理において、重み付けした配線
長評価値が最小となる候補経路を部分経路として選択す
ることにより、配線の長さと配線密度の両方を最適化す
ることができる。

【００６５】再び図６を参照する。ステップ１２４（Ｓ
１２４；図６）において、配線設計ソフトウェア３は、
Ｓ１２２の処理において、互いに対応するソース要素と
シンク要素との間の配線を導出できたか否かを判断す
る。配線を導出できた場合にはＳ１２６の処理に進み、
導出できなかった場合にはその旨をクライアントコンピ
ュータ１０に対して通知し、処理を終了する。

【００６６】図１１は、図６に示した配線の交差の解消
の処理（Ｓ１２４）を例示する図である。ステップ１２
６（Ｓ１２６；図６）において、配線設計ソフトウェア
３は、図１１に示すように、配線の交差を解消する。Ｓ
１２２の処理においては、交差を許して配線経路を探索
するため、図１１の中央に点線で例示するように、互い
に対応するソース要素Ａとシンク要素ａとを結ぶ配線
が、他の配線と交差した状態で導出される。このように
交差した配線を、図１１の左側に示すように交点それぞ
れにおいて分離し、図１１右側に示すように交差を解消
した配線を得る。

【００６７】図１２を参照してさらに配線の交差の解消
方法を説明する。図１２は、図１１に示した配線の交差
部分を拡大して例示する図である。図１２の左側に例示
するように、Ｓ１２２の処理において、ソース要素（節
点）Ａとシンク要素（節点）ｂとを接続する配線Ａｂ
と、ソース要素（節点）Ｂとシンク要素（節点）ａとを
接続する配線Ｂａとが交差節点で交差している場合、配
線設計ソフトウェア３は、これらのいずれかの配線が、
経路の進行方向（ソース要素からシンク要素の方向）沿
って、いずれの方向に抜けていくかをテストする。

【００６８】配線設計ソフトウェア３は、例えば、図１
２の左側に例示する場合において、配線Ａｂが交差節点
に対して右から左に抜けていると判定すると、配線設計
ソフトウェア３は、図１２の右側に例示するように、交
差節点を分離し、配線経路の入れ替えを行なって配線の
交差を解消する。従って、配線Ａｂ，Ｂａは、それぞれ
配線Ａａ，Ｂｂに変更される。

【００６９】ステップ１２８（Ｓ１２８）において、配
線設計ソフトウェア３は、Ｓ１２６における配線の交差
の解消処理によって変更された配線と、いずれの監視辺
とが交差するかを検出し、配線と監視辺との交差の状態
を示す交差情報を更新する。

【００７０】ステップ１３０（Ｓ１３０）において、配
線設計ソフトウェア３は、ソース要素およびシンク要素
のいずれかの全てに対して処理が終了し、残りの要素が
空であるか否かを判断し、要素が空である場合には配線
設計処理が終了したことをクライアントコンピュータ１
０に通知し、処理を終了してＳ１１２（図３）の処理に
戻り、これ以外の場合にはＳ１２２の処理に戻る。

【００７１】再び図３を参照する。ステップ１１２（Ｓ
１１２）において、配線設計ソフトウェア３は、以上の
処理により得られた配線設計の結果をクライアントコン
ピュータ１０に対して出力する。

【００７２】［コンピュータネットワーク１の動作］以
下、コンピュータネットワーク１の動作を説明する。ユ
ーザは、クライアントコンピュータ１０（図１）を操作
し、半導体チップのボンディングパッドと半導体パッケ
ージのピンとを対応付けて、デザイン情報を作成する。
デザイン情報の作成が終了すると、ユーザはデザイン情
報をサーバコンピュータ２０に対して送信し、配線設計
ソフトウェア３を起動させて配線設計を行なわせる。

【００７３】配線設計ソフトウェア３は、クライアント
コンピュータ１０から送られてきたデザイン情報を読み
込み（図３，Ｓ１０２）、読み込んだデザイン情報を解
析し、配線問題を作成する（図３，Ｓ１０４）。次に、
配線設計ソフトウェア３は、配線問題の半導体パッケー
ジ上のボンディグパッドおよびピンを、それぞれソース
要素およびシンク要素（図４）に分類し、互いに対応付
けて記憶する（図３，Ｓ１０６）。

【００７４】次に、配線設計ソフトウェア３は、配線経
路の監視に用いる仮想的な辺（監視辺Ｅ；図５）を１つ
以上、任意の２つのシンク要素の間それぞれ、および／
または、任意のシンク要素と配線禁止領域との間に作成
する（図３，Ｓ１０８）。

【００７５】次に、配線設計ソフトウェア３は、監視辺
Ｅに関する情報を初期化し（図３，Ｓ１１０；図６，Ｓ
１２０）、交差を許す重み付け探索処理を行なう（図６
および図７，Ｓ１２２）。次に、配線設計ソフトウェア
３は、最新の節点と次の節点があるか否かを判断し、接
続可能な節点がある場合には、配線容量チェック付きの
ダイクストラ法等を用いて候補経路を探索し、接続可能
な節点がない場合には処理を終了し、次の配線の経路探
索処理に進む（図７，Ｓ１４０）。

【００７６】次に、配線設計ソフトウェア３は、探索さ
れた候補経路のいずれかと監視辺Ｅとが交差するか否か
を判断し、交差する場合には候補経路の長さを重み付け
係数Ｗにより重み付けした経路長評価値を算出し（図
７，Ｓ１４４，Ｓ１４６）、交差しない場合には候補経
路の長さそのものを経路長評価値とする（図７，Ｓ１４
８）。次に、配線設計ソフトウェア３は、最新の節点と
次の節点との間の候補経路に対する処理を終了したか否
かを判断し（Ｓ１５０）、終了した場合には、配線評価
値が最低の値をとる候補経路を部分経路として選択する
（図７，Ｓ１５２：図８〜図１０）。

【００７７】次に、配線設計ソフトウェア３は、ソース
要素とシンク要素との間の配線を導出できたか否かを判
断し、導出できた場合には、配線の交差を解消し、監視
辺と配線経路との交差情報を更新する（図６，Ｓ１２
６，Ｓ１２８；図１１および図１２）、導出できなかっ
た場合にはその旨をクライアントコンピュータ１０に対
して通知し、処理を終了する（図６，Ｓ１２４）。最後
に、配線設計ソフトウェア３は、ソース要素およびシン
ク要素の全てに対して処理が終了したか否かを判断し、
終了した場合には、配線設計処理が終了したことをクラ
イアントコンピュータ１０に通知して配線結果をクライ
アントコンピュータ１０に対して送信し（図３，Ｓ１１
２）、終了しない場合には、交差を許す重み付け探索処
理（図６，Ｓ１２２）に戻る（図６，Ｓ１３０）。

【００７８】以上説明したように、本発明にかかる配線
設計方法は、従来のダイクストラ法等を用いた配線設計
方法に簡単な重み付け処理等を追加するだけで、配線の
局所的な集中を抑制することができ、しかも、大量のデ
ータを追加する必要がないので、従来の配線設計装置へ
の実装が容易である。また、本発明にかかる配線設計方
法においては、従来の配線設計方法に簡単な重み付け処
理等が追加されるだけなので、従来の配線設計方法に比
べても処理時間が殆ど変わらない。また、本発明にかか
る配線設計方法において、重み付け係数Ｗを処理結果等
に応じて調整可能にすると、配線長と配線密度とをより
最適な状態にすることができる。

【００７９】

【発明の効果】以上説明したように本発明によれば、デ
ザインルールを守り、しかも、局所的な配線集中を含ま
ない配線設計を、自動的に行なうことができ、しかも、
人手による配線および部品配置の修正を不要にすること
ができる。

【００８０】また、本発明によれば、部品配置および相
互に接続されるピンの位置関係等のネット情報によら
ず、デザインルールを守り、かつ、局所的な配線集中を
抑えて配線設計を行なうことができる。

【図面の簡単な説明】

【図１】本発明が適応されるコンピュータネットワーク
の構成を例示する図である。

【図２】図１に示したクライアントコンピュータとサー
バコンピュータとの間の機能分担を例示する図である。

【図３】図２に示した配線設計ソフトウェアの処理を示
すフローチャートである。

【図４】図３に示したソース要素・シンク要素の分類お
よび対応付け処理（Ｓ１０６）を例示する図である。

【図５】図３に示した監視辺Ｅの作成処理を例示する図
である。

【図６】図３に示したネット発生処理（Ｓ１１０）を示
すフローチャートである。

【図７】図６に示した交差を許す重み付け探索処理（Ｓ
１２２）を示すフローチャートである。

【図８】図６および図７に示した重み付け探索処理（Ｓ
１２２）の処理を例示する第１の図である。

【図９】図６および図７に示した重み付け探索処理（Ｓ
１２２）の処理を例示する第２の図である。

【図１０】図６および図７に示した重み付け探索処理
（Ｓ１２２）の処理を例示する第３の図である。

【図１１】図６に示した配線の交差の解消の処理（Ｓ１
２４）を例示する図である。

【図１２】図１１に示した配線の交差部分を拡大して例
示する図である。

【符号の説明】

１・・・コンピュータネットワーク１０・・・クライアントコンピュータ１００・・・コンピュータ本体１０２・・・ディスプレイ装置１０４・・・入力装置１０６・・・キーボード１０８・・・マウス１１０・・・出力装置１１２・・・記憶装置１１４・・・通信装置１２０・・・ＣＡＤソフトウェア１８・・・通信回線２０・・・サーバコンピュータ２００・・・コンピュータ本体２０２・・・記憶装置２０４・・・通信装置３・・・配線設計ソフトウェア

───────────────────────────────────────────────────── フロントページの続き (72)発明者勝又実神奈川県大和市下鶴間1623番地14 日本アイ・ビー・エム株式会社大和事業所内 (72)発明者平山和彦神奈川県大和市下鶴間1623番地14 日本アイ・ビー・エム株式会社大和事業所内

Claims

【特許請求の範囲】

【請求項１】１つの面上に設けられた複数の端点同士
を、前記面上の配線禁止領域以外を通る経路で接続する
配線を設計する配線設計装置であって、前記端点および前記面上の配線禁止領域（要素）の任意
の２つの間それぞれに仮想的な配線密度監視用の辺（監
視辺）を作成する監視辺作成手段と、前記監視辺それぞれと交差する配線の幅に基づいて、前
記端点同士を接続する配線の経路（配線経路）を設計す
る配線設計手段とを有する配線設計装置。
【請求項２】前記配線設計手段は、少なくとも前記要素
の間隔、前記要素の間に占める前記配線の幅の割合（配
線密度）、前記要素間隔前記配線の間隔および前記配線
の幅を示すデザインルールに従って配線経路を作成する
請求項１に記載の配線設計装置。
【請求項３】前記配線設計手段は、前記配線それぞれが始まる端点から、前記配線それぞれ
が終わる端点まで、前記配線それぞれの経路を１つ以上
に分けた部分（部分経路）ごとに、前記デザインルール
に従って前記配線それぞれの経路を順次、探索し、１つ
以上の前記部分経路の候補（候補経路）を作成する候補
経路作成手段と、作成された前記候補経路それぞれの経路長と、前記候補
経路と交差する監視辺の配線密度とに基づいて、前記候
補経路それぞれの経路長が長ければ長いほど、前記候補
経路それぞれが交差する前記監視辺と交差する配線の幅
が広ければ広いほど大きな値をとる前記候補経路それぞ
れの経路長評価値を算出する経路長評価手段と、作成された前記候補経路の内、算出された前記経路長評
価値が最小になるいずれかを前記部分経路として選択す
る経路選択手段と、選択された前記部分経路を接続して、前記配線それぞれ
の経路を設計する部分経路接続手段とを有する請求項２
に記載の配線設計装置。
【請求項４】前記経路長評価手段は、作成された前記候
補経路それぞれと交差する前記監視辺の配線密度が大き
ければ大きいほど大きい値をとる重み付け係数と、前記
候補経路それぞれの経路長とを乗算して、前記経路長評
価値を算出する請求項３に記載の配線設計装置。
【請求項５】前記候補経路作成手段は、他の配線経路と
の交差を許して前記候補経路を作成し、前記経路長評価算出手段は、交差を許して作成された前
記候補経路の経路長評価値を算出し、前記経路選択手段は、選択した前記部分経路と他の配線
経路とが交差する場合、交差が解消するように選択した
前記部分経路と他の配線経路とを変更する請求項３に記
載の配線設計装置。
【請求項６】１つの面上に設けられた複数の端点同士
を、前記面上の配線禁止領域以外を通る経路で接続する
配線を設計する配線設計方法であって、前記端点および前記面上の配線禁止領域（要素）の任意
の２つの間それぞれに仮想的な配線密度監視用の辺（監
視辺）を作成し、少なくとも前記要素の間隔、前記要素の間隔に占める前
記配線の幅の割合（配線密度）、前記要素間隔前記配線
の間隔および前記配線の幅を示すデザインルールに従っ
て、前記配線それぞれが始まる端点から、前記配線それ
ぞれが終わる端点まで、前記配線それぞれの経路を１つ
以上に分けた部分（部分経路）ごとに、前記配線それぞ
れの経路を順次、探索し、１つ以上の前記部分経路の候
補（候補経路）を作成し、作成された前記候補経路それぞれの経路長と、前記候補
経路と交差する監視辺の配線密度とに基づいて、前記候
補経路それぞれの経路長が長ければ長いほど、前記候補
経路それぞれが交差する前記監視辺と交差する配線の幅
が広ければ広いほど大きな値をとる前記候補経路それぞ
れの経路長評価値を算出し、作成された前記候補経路の内、算出された前記経路長評
価値が最小になるいずれかを前記部分経路として選択
し、選択された前記部分経路を接続して、前記配線それぞれ
の経路を設計する請求項２に記載の配線設計方法。
【請求項７】１つの面上に設けられた複数の端点同士
を、前記面上の配線禁止領域以外を通る経路で接続する
配線を設計するプログラムであって、前記端点および前記面上の配線禁止領域（要素）の任意
の２つの間それぞれに仮想的な配線密度監視用の辺（監
視辺）を作成する監視辺作成ステップと、前記監視辺それぞれと交差する配線の幅に基づいて、前
記端点同士を接続する配線の経路（配線経路）を設計す
る配線設計ステップとを含むプログラムを記録した記録
媒体。
【請求項８】前記配線設計ステップにおいて、少なくと
も前記要素の間隔、前記要素の間隔に占める前記配線の
幅の割合（配線密度）、前記要素間隔前記配線の間隔お
よび前記配線の幅を示すデザインルールに従って配線経
路を作成する処理を行なうプログラムを記録した請求項
７に記載の記録媒体。
【請求項９】前記配線設計ステップにおいて、前記配線それぞれが始まる端点から、前記配線それぞれ
が終わる端点まで、前記配線それぞれの経路を１つ以上
に分けた部分（部分経路）ごとに、前記デザインルール
に従って前記配線それぞれの経路を順次、探索し、１つ
以上の前記部分経路の候補（候補経路）を作成する候補
経路作成処理と、作成された前記候補経路それぞれの経路長と、前記候補
経路と交差する監視辺の配線密度とに基づいて、前記候
補経路それぞれの経路長が長ければ長いほど、前記候補
経路それぞれが交差する前記監視辺と交差する配線の幅
が広ければ広いほど大きな値をとる前記候補経路それぞ
れの経路長評価値を算出する経路長評価処理と、作成された前記候補経路の内、算出された前記経路長評
価値が最小になるいずれかを前記部分経路として選択す
る経路選択処理と、選択された前記部分経路を接続して、前記配線それぞれ
の経路を設計する部分経路接続処理とを行なうプログラ
ムを記録した請求項８に記載の記録媒体。
【請求項１０】前記経路長評価ステップにおいて、作成
された前記候補経路それぞれと交差する前記監視辺の配
線密度が大きければ大きいほど大きい値をとる重み付け
係数と、前記候補経路それぞれの経路長とを乗算して、
前記経路長評価値を算出する処理を行なうプログラムを
記録した請求項８に記載の記録媒体。
【請求項１１】前記候補経路作成ステップにおいて、他
の配線経路との交差を許して前記候補経路を作成する処
理と、前記経路長評価算出ステップにおいて、交差を許して作
成された前記候補経路の経路長評価値を算出する処理
と、前記経路選択ステップにおいて、選択した前記部分経路
と他の配線経路とが交差する場合、交差が解消するよう
に選択した前記部分経路と他の配線経路とを変更する処
理とを行なうプログラムを記録した請求項８に記載の記
録媒体。