米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 松下電器産業株式会社

発明の名称 自動配線方法および自動配線装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平7−219988
公開日 平成7年(1995)8月18日
出願番号 特願平6−11719
出願日 平成6年(1994)2月3日
代理人 【弁理士】
【氏名又は名称】中島 司朗
発明者 齊藤 義行
要約 目的
高速に高品質かつ高配線率の配線を行なえる自動配線方法および自動配線装置を提供する。

構成
遺伝子テーブル作成部2は、遺伝子を遺伝子テーブルに登録する。個体発生部3は、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する。評価部4は、個体発生部3により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する。収束判定部5は、評価部4により算出された適合値に基づいて個体の進化が収束したか否かを判断する。交叉部6は、収束判定部5により個体の進化が収束していないと判断されたときに、評価部4により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成する。
特許請求の範囲
【請求項1】 プリント基板や半導体の電子回路のネットを自動配線する自動配線方法であって、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成ステップと、各ネットについて1つの遺伝子を前記遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生ステップと、前記個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価ステップと、前記評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定ステップと、前記収束判定ステップにおいて個体の進化が収束していないと判断されたときに、前記評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成して前記評価ステップに戻る交叉ステップと、を実行し、前記収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とすることを特徴とする自動配線方法。
【請求項2】プリント基板や半導体の電子回路のネットを自動配線する自動配線装置であって、接続情報などの配線設計に必要な情報を格納している記憶部と、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成部と、各ネットについて1つの遺伝子を前記遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生部と、前記個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価部と、前記評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定部と、前記収束判定部により個体の進化が収束していないと判断されたときに、前記評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成して前記評価部に渡す交叉部と、を備え、前記収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする構成としたことを特徴とする自動配線装置。
【請求項3】 プリント基板や半導体の電子回路のネットを自動配線する自動配線方法であって、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成ステップと、各ネットについて1つの遺伝子を前記遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生ステップと、前記個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価ステップと、前記評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定ステップと、前記収束判定ステップにおいて個体の進化が収束していないと判断されたときに、前記評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成する交叉ステップと、前記交叉ステップにおいて作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて前記評価ステップに戻る突然変異ステップと、を実行し、前記収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とすることを特徴とする自動配線方法。
【請求項4】プリント基板や半導体の電子回路のネットを自動配線する自動配線装置であって、接続情報などの配線設計に必要な情報を格納している記憶部と、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成部と、各ネットについて1つの遺伝子を前記遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生部と、前記個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価部と、前記評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定部と、前記収束判定部により個体の進化が収束していないと判断されたときに、前記評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成する交叉部と、前記交叉部により作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて前記評価部に渡す突然変異部と、を備え、前記収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする構成としたことを特徴とする自動配線装置。
【請求項5】評価ステップ、収束判定ステップ、交叉ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更ステップを実行することを特徴とする請求項1に記載の自動配線方法。
【請求項6】評価部、収束判定部、交叉部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更部を備えた請求項2に記載の自動配線装置。
【請求項7】評価ステップ、収束判定ステップ、交叉ステップ、突然変異ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更ステップを実行することを特徴とする請求項3に記載の自動配線方法。
【請求項8】評価部、収束判定部、交叉部、突然変異部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更部を備えた請求項4に記載の自動配線装置。
【請求項9】遺伝子テーブル作成ステップにおいて、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成することを特徴とする請求項1または請求項3または請求項5または請求項7に記載の自動配線方法。
【請求項10】遺伝子テーブル作成部が、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成する構成としたことを特徴とする請求項2または請求項4または請求項6または請求項8に記載の自動配線装置。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、プリント基板や半導体などの電子回路の設計において、ネットの配線を自動的に決定する自動配線方法および自動配線装置に関するものである。
【0002】
【従来の技術】近年、CAD(Computer Aided Design )の普及によりプリント基板や半導体などの電子回路の配線を自動的に決定する自動配線装置が利用されている。このような自動配線装置においては、例えば「超LSICADの基礎(オーム社)」の第5章に記載されているような迷路法、線分探索法、チャネル配線法といった配線手法が採用されているが、ネット1つずつについて配線経路を求めていくため、配線率が悪かったり、処理時間が長くなったり、高配線率を達成するが配線結果の質が悪かったりする。従って、自動配線装置による自動配線の終了後に少なからず配線パターンの修正が必要であった。
【0003】そのような場合、従来はCADの対話処理機能を用いて人手で修正を行っていた。すなわち、一旦自動配線されたネットの中で引き回しパターンが良くないものや極端に配線長が長いものを取り除いた後、再度配線し直すのである。
【0004】
【発明が解決しようとする課題】しかし上記従来の自動配線装置では、自動配線の終了後にCADの対話処理機能を用いて人手で修正を行っていたので、一旦配線されたパターンを取り除く分の工数が増加するだけでなく、修正が必要な配線パターンの周囲の配線パターンも同時に修正しないとパターン修正が行なえない場合が多く、自動配線を行なうメリットが少ないという課題があった。
【0005】本発明はかかる事情に鑑みて成されたものであり、高速に高品質かつ高配線率の配線を行なえる自動配線方法および自動配線装置を提供することを目的とする。
【0006】
【課題を解決するための手段】請求項1の発明は、プリント基板や半導体の電子回路のネットを自動配線する自動配線方法であって、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成ステップと、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生ステップと、個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価ステップと、評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定ステップと、収束判定ステップにおいて個体の進化が収束していないと判断されたときに、評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成して評価ステップに戻る交叉ステップと、を実行し、収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とすることを特徴としている。
【0007】請求項2の発明は、プリント基板や半導体の電子回路のネットを自動配線する自動配線装置であって、接続情報などの配線設計に必要な情報を格納している記憶部と、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成部と、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生部と、個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価部と、評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定部と、収束判定部により個体の進化が収束していないと判断されたときに、評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成して評価部に渡す交叉部と、を備え、収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする構成としたことを特徴としている。
【0008】請求項3の発明は、プリント基板や半導体の電子回路のネットを自動配線する自動配線方法であって、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成ステップと、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生ステップと、個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価ステップと、評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定ステップと、収束判定ステップにおいて個体の進化が収束していないと判断されたときに、評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成する交叉ステップと、交叉ステップにおいて作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて評価ステップに戻る突然変異ステップと、を実行し、収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とすることを特徴としている。
【0009】請求項4の発明は、プリント基板や半導体の電子回路のネットを自動配線する自動配線装置であって、接続情報などの配線設計に必要な情報を格納している記憶部と、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成部と、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生部と、個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価部と、評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定部と、収束判定部により個体の進化が収束していないと判断されたときに、評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成する交叉部と、交叉部により作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて評価部に渡す突然変異部と、を備え、収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする構成としたことを特徴としている。
【0010】請求項5の発明は、評価ステップ、収束判定ステップ、交叉ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更ステップを実行することを特徴としている。請求項6の発明は、評価部、収束判定部、交叉部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更部を備えたことを特徴としている。
【0011】請求項7の発明は、評価ステップ、収束判定ステップ、交叉ステップ、突然変異ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更ステップを実行することを特徴としている。請求項8の発明は、評価部、収束判定部、交叉部、突然変異部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更部を備えたことを特徴としている。
【0012】請求項9の発明は、遺伝子テーブル作成ステップにおいて、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成することを特徴としている。請求項10の発明は、遺伝子テーブル作成部が、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成する構成としたことを特徴としている。
【0013】
【作用】請求項1の発明においては、遺伝子テーブル作成ステップで、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録し、個体発生ステップで、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成し、評価ステップで、個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出し、収束判定ステップで、評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断し、収束判定ステップにおいて個体の進化が収束していないと判断されたときに、交叉ステップで、評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成して評価ステップに戻る。そして、収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする。
【0014】請求項2の発明において、記憶部は、接続情報などの配線設計に必要な情報を格納している。遺伝子テーブル作成部は、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する。個体発生部は、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する。評価部は、個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する。収束判定部は、評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する。交叉部は、収束判定部により個体の進化が収束していないと判断されたときに、評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成して評価部に渡す。そして、収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする。
【0015】請求項3の発明においては、遺伝子テーブル作成ステップで、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録し、個体発生ステップで、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成し、評価ステップで、個体発生ステップにおいて作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出し、収束判定ステップで、評価ステップにおいて算出された適合値に基づいて個体の進化が収束したか否かを判断し、交叉ステップで、収束判定ステップにおいて個体の進化が収束していないと判断されたときに、評価ステップにおいて算出された適合値に基づいて個体内の遺伝子の交換を行なうことにより次世代の個体を作成し、突然変異ステップで、交叉ステップにおいて作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて評価ステップに戻る。そして、収束判定ステップにおいて収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする。
【0016】請求項4の発明において、記憶部は、接続情報などの配線設計に必要な情報を格納している。遺伝子テーブル作成部は、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する。個体発生部は、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する。評価部は、個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する。収束判定部は、評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する。交叉部は、収束判定部により個体の進化が収束していないと判断されたときに、評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成する。突然変異部は、交叉部により作成された次世代の個体に対して、指定された確率で遺伝子内のビットを反転させて評価部に渡す。そして、収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする。
【0017】請求項5の発明においては、評価ステップ、収束判定ステップ、交叉ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル変更ステップで、遺伝子テーブル内の配線経路候補を新たに書き換える。請求項6の発明において、遺伝子テーブル変更部は、評価部、収束判定部、交叉部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える。
【0018】請求項7の発明においては、評価ステップ、収束判定ステップ、交叉ステップ、突然変異ステップを繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル変更ステップで、遺伝子テーブル内の配線経路候補を新たに書き換える。請求項8の発明において、遺伝子テーブル変更部は、評価部、収束判定部、交叉部、突然変異部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える。
【0019】請求項9の発明においては、遺伝子テーブル作成ステップにおいて、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成する。請求項10の発明において、遺伝子テーブル作成部は、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成する。
【0020】
【実施例】以下、本発明の実施例を図面を用いて詳細に説明する。
(実施例1)図1は本発明の実施例1における自動配線装置の構成図で、この自動配線装置は、記憶部1と、遺伝子テーブル作成部2と、個体発生部3と、評価部4と、収束判定部5と、交叉部6と、突然変異部7とを備えている。記憶部1は、接続情報などの配線設計に必要な情報を格納している。遺伝子テーブル作成部2は、接続すべきネットについて複数の配線経路候補を求めてそれら各々にラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する。個体発生部3は、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する。評価部4は、個体発生部3により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する。収束判定部5は、評価部4により算出された適合値の中で最高値が指定値を超えているか否かにより個体の進化が収束したか否かを判断し、収束したと判断した場合は、存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果として出力する。交叉部6は、収束判定部5により個体の進化が収束していないと判断されたときに、評価部4により算出された適合値に基づいて個体内の遺伝子の交換を行ない、次世代の個体を作成する。突然変異部7は、交叉部6により作成された新世代の個体内の遺伝子を指定された確率でビット反転させる。
【0021】図2は上記自動配線装置の動作を説明する説明図で、上記自動配線装置は、遺伝子テーブル作成ステップと、固体発生ステップと、評価ステップと、収束判定ステップとを実行し、個体の進化が収束すれば処理を終了する。個体の進化が収束しなければ、交叉ステップと、突然変異ステップとを実行し、評価ステップに戻る。
【0022】すなわち、遺伝子テーブル作成ステップにおいては、遺伝子テーブル作成部2が、先ず、接続すべきネットについて配線経路候補を探索する。次に、配線経路候補にラベルを与える。次に、ラベルを2値化して遺伝子とする。次に、遺伝子を配線経路と共に遺伝子テーブルに登録する。指定された数だけ、上記の配線経路候補の探索、ラベル付与、ラベルの2値化、遺伝子テーブルへの登録を繰り返す。このとき、ラベルが重複しないようにする。このような操作をネット全てについて行ない、遺伝子テーブルを作成する。
【0023】個体発生ステップにおいては、個体発生部3が、先ず、接続すべきネットについて、遺伝子テーブルから遺伝子をランダムに1つ選択する。全てのネットについて1つずつ遺伝子を選択すれば、それらの遺伝子を連ねて0と1とからなる1個の数値列(以下「第一世代の個体」という)とする。個体数が指定された数(以下「人口」という)に達するまで同じように繰り返す。
【0024】評価ステップにおいては、評価部4が、先ず、1つの個体に注目し、例えば下記数1の評価関数に従って適合値を算出する。全ての個体について適合値を算出するまで繰り返す。
【0025】
【数1】

収束判定ステップにおいては、収束判定部5が、先ず、評価ステップにおいて評価部4により算出された適合値のうち、最大値が指定された値を超えているか否かにより、個体の進化が進化が収束したか否かを判断する。いずれかの個体の適合値が指定値を超えている場合は収束したと判断し、最大の適合値を持つ個体の遺伝子が表す配線経路を配線結果として出力し、自動配線を終了する。
【0026】いずれの個体の適合値も指定値を超えていなければ、交叉ステップにおいて、交叉部6が、先ず、全個体の適合値の平均値を算出する。次に、適合値が平均値以下の個体を削除する。すなわち、それらの個体は自然淘汰されたことになる。次に、残った個体からランダムに個体を2つ選択して親とする。次に、ランダムに交叉点を設定し、交叉を行なって次世代の個体(以下「子」という)を作成する。上記の親の選択から交叉までを子が人口に達するまで繰り返す。
【0027】なお、本実施例1では自然淘汰の基準として平均値を用いているが、平均値に限るものではなく、適合値が悪い個体が淘汰されるのであれば、中間値や加重平均値などを用いてもよい。突然変異ステップにおいては、突然変異部7が、先ず、交叉ステップにおいて交叉部6により作成された個体全てについて、順に1〜Nの乱数を発生させる。ここでNは突然変異を起こす確率の逆数であり、確率が100分の1であればN=100となる。そして、発生させた乱数がNと等しい個体について突然変異点をランダムに設定し、0→1、1→0のビット反転を行なう。そして評価ステップに戻る。なお、本実施例1では突然変異の発生確率を達成するために上記の方法を用いているが、確率が達成されるのであれば他の方法を用いてもよい。
【0028】次に、上記自動配線装置の動作の要点を具体的に説明する。図3は配線すべき回路の一部を拡大した平面図であり、部品番号IC1の部品11の8番ピンと部品番号IC2の部品12の3番ピンとをネットNET1により接続し、部品11の5番ピンと部品12の1番ピンとをネットNET2により接続し、部品11の4番ピンと部品12の5番ピンとをネットNET3により接続するものとする。
【0029】図4は接続すべきネットのリストの説明図であり、記憶部1に記憶されている。NET1、NET2、NET3はネット名を表し、IC1(8)−IC2(3)は部品番号IC1の部品11の8番ピンと部品番号IC2の部品12の3番ピンとを接続しなければならないことを表している。また、(1,25.40,25.40)−(1,50.80,22.86)は、部品11の8番ピンが第1層の座標(25.40,25.40)にあり、部品12の3番ピンが第1層の座標(50.80,22.86)にあることを表している。
【0030】図5および図6は遺伝子テーブル作成ステップにおいて遺伝子テーブル作成部2により探索される配線経路候補の説明図であり、両面基板に図3の回路が実装された場合の、ネットNET1の配線経路候補の例を示している。部品11および部品12は、部品面13と半田面14とを有する両面基板の部品面13に配置されている。図5の例では、部品面13内でビアを用いない2回の折れ曲がりの配線経路候補が探索されており、部品11の8番ピン15と部品12の3番ピン16とが箔17により接続される。図6の例では、ビア19,20,21,22を用いた2回の折れ曲がりの配線経路候補が探索されており、部品11の8番ピン15と部品12の3番ピン16とは、ビア19,20,21,22を介して箔18により接続される。
【0031】図7〜図9は遺伝子テーブル作成部2により作成された遺伝子テーブルの説明図で、この例では各ネットについてそれぞれ16通りの配線経路候補を登録するため、ラベルすなわち遺伝子は4ビットで、値は0000h〜1111hとなっている。ネットNET1のラベルすなわち遺伝子0000,0001に登録されている配線経路候補は図5,図6に示した経路にそれぞれ対応している。また座標は(層数,X座標,Y座標)で表している。
【0032】なお、配線経路候補は幾通りでも良く、その数にあわせてラベルすなわち遺伝子のビット数を変更してやればよい。また、遺伝子テーブルの形態も図示したものに限らず、ネット名、ラベルすなわち遺伝子、配線経路候補がわかるものであればよい。図10は個体発生ステップにおいて個体発生部3により作成された個体の説明図で、ここでいう個体とは、遺伝子をネット数分だけ連ねたものである。図に示した個体は各ネットについて0〜遺伝子数(16)までのランダム値を発生させ、それらを2値化して連ねて作成している。個体数に制限はないが、少な過ぎると良い結果が得られず、多過ぎると収束までに時間がかかる。
【0033】上記数1は評価ステップにおいて評価部4が使用する評価関数の一具体例であり、数1において未配線ネット数とは、各個体の遺伝子を配線経路に戻したときに重なりが生じて配線できないネット数である。α,β,γ,δはそれぞれ未配線ネット数、配線長、ビア数、折れ曲がり数の重み付けを行なうための係数である。図10の個体1,3についてネット1、ネット2、ネット3に関する部分だけを考えると、個体1では未配線ネット数=1、配線長=115.58、ビア数=0、折れ曲がり数=7となり、個体3では未配線ネット数=0、配線長=115.58、ビア数=2、折れ曲がり数=7となる。係数の決定には特に制限はなく、例えばβを大きくすると配線長が短い配線結果が得られ、γを大きくするとビアが少ない配線結果が得らる。
【0034】なお、評価ステップにおいて評価部4が用いる評価関数には制限はなく、さらに項目を付け足してもよいし、削除してもよい。図11および図12は交叉ステップにおいて交叉部6が実行する交叉の説明図で、図11は交叉点が1点、図12は交叉点が2点の場合を表している。図では交叉点が1点および2点の場合を示したが、さらに交叉点を増やしてもよい。交叉の手順としては、先ず親となる個体を2つ選択する。親の選択は、例えば適合値の平均値などの指定値以上の適合値である個体からのみ行ない、次世代の個体がより優秀になるようにする。次に図11あるいは図12のように交叉点を決めて交叉を行ない、次世代の個体を2つ作成する。以下、親の選択と交叉とを、個体数が指定個体数すなわち人口に達するまで繰り返す。
【0035】図13は突然変異ステップにおいて突然変異部7により実行された突然変異の説明図で、図11あるいは図12のように交叉ステップにおいて交叉部6により作成された次世代の個体に対し、指定された確率で図に示したようなビット反転の突然変異を発生させる。例えば確率を1%とすると、人口が100の場合1個の個体に突然変異が発生することになる。なお、突然変異を発生させる個体、発生する点はランダムに選択する。
【0036】図14は配線結果の説明図で、図3の回路の配線結果である。なお上記実施例1では、突然変異部7を設けて突然変異ステップを実行したが、突然変異部7は必ずしも設ける必要はない。このように、全体の配線経路を同時に考慮し、また配線長、ビア数、折れ曲がり数といった配線の品質も考慮しながら自動配線を行なうので、配線率が高く、高速かつ高品質の自動配線結果を得ることができ、自動配線後の人手による修正の工数を大幅に削減できる。
(実施例2)図15は本発明の実施例2における自動配線装置の構成図で、この自動配線装置は、記憶部31と、遺伝子テーブル作成部32と、個体発生部33と、評価部34と、収束判定部35と、交叉部36と、突然変異部37と、遺伝子テーブル変更部38とを備えている。記憶部31は、接続情報などの配線設計に必要な情報を格納している。遺伝子テーブル作成部32は、接続すべきネットについて複数の配線経路候補を求めてそれら各々にラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する。個体発生部33は、各ネットについて1つの遺伝子を遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する。評価部34は、個体発生部33により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する。収束判定部35は、評価部34により算出された適合値の中で最高値が指定値を超えているか否かにより個体の進化が収束したか否かを判断し、収束したと判断した場合は、存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果として出力する。交叉部36は、収束判定部35により個体の進化が収束していないと判断されたときに、評価部34により算出された適合値に基づいて個体内の遺伝子の交換を行ない、次世代の個体を作成する。突然変異部37は、交叉部36により作成された新世代の個体内の遺伝子を指定された確率でビット反転させる。
【0037】図16は本発明の実施例2における自動配線装置の動作を説明する説明図で、遺伝子テーブル作成ステップ、個体発生ステップ、評価ステップ、交叉ステップ、突然変異ステップの動作は図2の場合と同様である。この実施例2の自動配線装置は、進化の世代数、すなわち評価ステップから突然変異ステップまでの繰り返し数が指定された最大値を超えた場合、遺伝子テーブル書き換えステップを実行し、個体発生ステップに戻る。すなわち遺伝子テーブル書き換えステップにおいては、遺伝子テーブル変更部38が、遺伝子テーブルの配線経路候補から半数の候補を選択し、経路候補を探索し直し、遺伝子テーブルを修正する。
【0038】上記実施例2では、進化が収束しない候補がすべて悪いという考えのもとで、半数のみを書き換えたが、全てを書き換えてもよいし、別の割合いで書換えを行なってもよい。このように、良い結果が得られない場合でも別な角度から自動配線を進めるので、より良い自動配線結果を得ることができ、自動配線後の人手による修正の工数を一層削減することができる。
(実施例3)図17〜図19は本発明の実施例3の自動配線装置により採用される遺伝子テーブルの説明図で、自動配線装置の構成は図1と同様であり、自動配線装置の動作は図2と同様である。すなわちこの実施例3の自動配線装置の遺伝子テーブル作成部2は、配線長が短い、ビアが少ない、折れ曲がり数が少ないといった優先度が高い配線経路候補に与える遺伝子を2倍にして、他の配線経路候補に比べて2倍の出現確率となるようにする。
【0039】なお、具体的な数値を優先度として与え、優先度の高い配線経路候補が優先的に選ばれるような優先度の与え方をしてもよい。また、実施例2の自動配線装置に実施例3の遺伝子テーブルを採用してもよい。このように、クロックラインや高速信号線といった重要な信号線の配線パターンを予め優先させた上で全てのネットを同等に扱って自動配線を行なうことができる。したがって、高速に高品質の自動配線結果を得ることができ、自動配線後の人手による修正の工数を一層削減することができる。
【0040】
【発明の効果】以上説明したように本発明によれば、プリント基板や半導体の電子回路のネットを自動配線する自動配線装置であって、接続情報などの配線設計に必要な情報を格納している記憶部と、接続すべきネットに対して複数の配線経路候補を求めてラベルを与え、それらラベルを2値化して遺伝子とし、それら遺伝子を遺伝子テーブルに登録する遺伝子テーブル作成部と、各ネットについて1つの遺伝子を前記遺伝子テーブルからランダムに選択して組み合わせた第一世代の個体を複数個作成する個体発生部と、個体発生部により作成された各個体について、配線経路が重複して実際には配線できないネット数、総配線長、ビア数、折れ曲がり数を調べて適合値を算出する評価部と、評価部により算出された適合値に基づいて個体の進化が収束したか否かを判断する収束判定部と、収束判定部により個体の進化が収束していないと判断されたときに、前記評価部により算出された適合値に基づいて個体内の遺伝子の交換を行ない次世代の個体を作成して前記評価部に渡す交叉部と、を備え、前記収束判定部により収束したと判断されたときに存在する個体の中で最も適合値が良い個体の遺伝子が表すラベルを持つ配線経路を配線結果とする構成としたので、全体の配線経路を同時に考慮し、また配線長、ビア数、折れ曲がり数といった配線の品質も考慮しながら自動配線を行なうことから、配線率が高く、高速かつ高品質の自動配線結果を得ることができ、自動配線後の人手による修正の工数を大幅に削減できる。
【0041】また、評価部、収束判定部、交叉部がそれぞれの動作を繰り返し行なって指定された世代まで個体を進化させても進化が収束しない場合に、遺伝子テーブル内の配線経路候補を新たに書き換える遺伝子テーブル変更部を備えれば、高速に自動配線できる利点を活かし、良い結果が得られない場合でも別な角度から自動配線を進めることができることから、より良い自動配線結果を得ることができ、自動配線後の人手による修正の工数を一層削減できる。
【0042】また、遺伝子テーブル作成部が、各配線経路候補の配線長、ビア数、折れ曲がり数を考慮して優先度を付けた遺伝子テーブルを作成する構成とすれば、クロックラインや高速信号線といった重要な信号線の配線パターンを予め優先させた上ですべてのネットを同等に扱って自動配線を行なうことができ、高速に高品質の自動配線結果を得ることができることから、自動配線後の人手による修正の工数を一層削減できる。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013