導電性パスの分散自動ルーティング
サーバコンピュータは、ＰＣＢ設計のためのマスターデータベースを維持し、ＰＣＢ設計のコピーが、複数のクライアントコンピュータに提供される。サーバは、接続がルート決定される必要がある異なるピンペアを各クライアントに割り当てる。クライアントが割り当てられたルーティングタスクを完了させると、それは、サーバがそれに割り当てられたピンペアについてクライアントにより検出されたルートによりＰＣＢマスター設計を更新するよう要求する。リクエストの転送後、クライアントは、検出されたルートを反映させるようＰＣＢ設計のコピーを更新しない。代わりに、クライアントは、サーバによるピンペアの割当て前に占有されている状態にそれのコピーを戻す。検出されたルートをサーバが実装したという通知を受信すると、クライアントは、当該ルートを含むよう設計のコピーを更新する。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［関連出願の相互参照］
本出願は、参照することにより含まれる、２００３年１１月２１日に出願された米国仮出願第６０／５２３，６９７号「Ａ Ｒｅｖｏｌｕｔｉｏｎａｒｙ Ｄｅｓｉｇｎ Ｔｅｃｈｎｏｌｏｇｙ」の優先権を主張する。
［発明の技術分野］
本発明は、電子設計自動化ツールの技術分野に関する。より詳細には、本発明の実施例は、プリント基板（ＰＣＢ）設計におけるトレースのルーティングを含む電子回路の導電性パスのルーティングに関する。
［発明の背景］
電子回路は、典型的には、レジスタ、集積回路（ＩＣ）、キャパシタ、ダイオード、トランジスタなどの多数の電子コンポーネントを有する。各コンポーネントは、当該コンポーネントがあるタイプの電気コンダクタにより１以上の他のコンポーネントに電気的に接続される接続ポイント（又はピン）を有する。プリント基板（ＰＣＢ）上の回路では、コンポーネントピンは、基板上（内）の導電性ストリップ（又はトレース）と接続される。多くのケースにおいて、電気回路はまず概略図により記述される。この概略は、通常は記号表示されたコンポーネント間を結ぶラインにより相互接続される従来技術による記号（レジスタについてはジグザグのライン、ＩＣについては矩形のボックスなど）として回路コンポーネントを示す。概略図に与えられるコンポーネントと、当該コンポーネント間の必要な電気的接続に基づき、ＰＣＢ上の物理コンポーネントの構成（又は配置）が決定される。その後、電気的に接続される必要があるピンのペア間でトレースがルーティングされる。
【０００２】
電子回路がより複雑になるに従い、当該回路のＰＣＢの設計はより困難なものとなる。この複雑さのため、多くの設計者がしばしば同一のＰＣＢ設計について作業する。参照することによりここに含まれる、米国特許第６，７０８，３１３号「Ｐａｒａｌｌｅｌ Ｅｌｅｃｔｒｏｎｉｃ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ：Ｓｈａｒｅｄ Ｓｉｍｕｌｔａｎｅｏｕｓ Ｅｄｉｔｉｎｇ」は、複数の設計者が同一のＰＣＢ設計について同時に作業することを可能にするシステム及び方法を記載している。ここで使用される「設計者」とは、人間の設計者と設計機能を実行するソフトウェアアプリケーションの両方を含む。少なくとも一実施例では、サーバコンピュータはＰＣＢ設計を維持し、当該設計のコピーが複数のクライアントコンピュータに配置される。各クライアントは、ＰＣＢ設計の全体を閲覧することができる。クラインと側で当該設計が編集されると、この編集は設計を編集するリクエストとしてサーバに送信される。サーバが設計基準チェック（ＤＲＣ）を実行し、リクエストされた編集が他の編集とコンフリクトしない、又はＰＣＢ設計に課された制約（トレース間の最小セパレーションなど）に違反していないことを確認した後、サーバは、リクエストされた編集を当該設計に適用する。適用された編集は、その後、クライアント側におけるＰＣＢ設計コピーの更新のため、クライアントに配信される。
【０００３】
複数の設計者が同一のＰＣＢ設計について同時に作業するときでさえ、この処理は大変時間のかかるものとなりうる。設計処理の最も時間を要する点の１つは、電子コンポーネント間の導電性パスのルーティングである。接続ラインが頻繁に交差している概略図では、ＰＣＢ上のトレースの交差は短絡又は他の望ましくない結果をもたらしうる。回路のすべてのコンポーネントが基板上のある位置に割り当てられると（配置されると）、所望の電子接続のみが生成されるように、ピン間の接続がルーティングされる必要がある。一部のケースでは、ＰＣＢは相互に接続される必要がある数百又は数千のピンを有するかもしれない。ある接続について与えられたルートは、しばしば他の接続のための利用可能なルートを排除する。ルート決定される接続が多くなるほど、利用可能なルーティングスペースは少なくなり、残りの接続をルート決定する作業はより困難となる。マルチレイヤＰＣＢは、接続をルート決定するためのスペースをより多く提供することにより上記問題を解消するものであるが、この作業は極めて複雑なものである。しばしば、多数の接続が、以前にルート決定された接続が「取り除かれ（ｒｉｐｐｅｄ ｕｐ）」、再ルート決定される必要があることが検出される前に、ルート決定される。
【０００４】
人間の設計者によるＰＣＢの手動によるルート決定は、大変大きな作業時間を要するため、ルーティング処理を自動化する（「自動ルーティング」）ための多数のアルゴリズムが作成されてきた。しかしながら、適度な複雑さの回路についてでさえ、既存のアルゴリズムはＰＣＢ全体をルート決定するのに極めて多くの時間を要する。実際、ＰＣＢ設計者が仕事時間の終わりに自動ルーティングプログラムをスタートさせ、プログラムを一晩中実行させることが通常である。このような大きな実行時間に対する１つの可能な解決策は、複数のコンピュータ間にルーティングタスクを分散させることである。集積回路（ＩＣ）の設計に用いられるルーティングプログラムは、予め分散環境において動作するよう変換されていた。しかしながら、ＰＣＢのルーティング問題は、ＩＣルーティングに係るものとは全く異なるものである。例えば、ＩＣの機能コンポーネントは、しばしばトレースが基盤の幅全体及び／又は長さ全体にわたることが必要であるＰＣＢよりも、より局所化される傾向にある。この局所性の欠落は、ＰＣＢのルーティング設計の領域の割当てを困難にすると共に、異なる設計者（人間又は自動化の何れでも）によりルート決定される各セクションを結合させるとき問題を生じさせる。ＩＣの各要素は、同一サイズに近いものとなる傾向があり（少なくともトランジスタレベルでは）、しばしばチップの異なるレベルにおける導電性パスの接続に関するコストは大きなものではない。他方、ＰＣＢ上に配置される各コンポーネントは、広範なサイズを有し、このサイズ範囲はルーティング問題を複雑化しうる。さらに、製造コストはしばしば、異なるＰＣＢレイヤ上のトレースを接続する「ビア」を最小限に抑えるよう要求する。上記及び他の理由のため、ＩＣ設計に用いられる分散自動ルーティングアプローチは、ＰＣＢ設計において限定的な価値しか有さない。実際、分散ＰＣＢ自動ルーティングは、新たなタイプのルーティングアルゴリズムがまず開発されることを要求し、既存のルーティングアルゴリズムが１つのＰＣＢをルート決定するのに複数のコンピュータにより効果的には利用することができないと、多くが考えている。
［発明の概要］
本発明の実施例は、自動ルーティングがより迅速に実行されることを可能にし、ＰＣＢ設計のルートが既存のルーティングアルゴリズムを利用して複数のコンピュータにより生成されることを可能にする。少なくとも一部の実施例では、サーバコンピュータは、ＰＣＢ設計のためのマスターデータベースを維持する。このデータベースは、回路コンポーネントとそれらの配置に関する情報、ＰＣＢ設計の設計基準及び他の各種情報を有する。ＰＣＢ設計のコピーが、複数のクライアントコンピュータに提供される。概略的な電子回路（又はそのための他の設計データ）が、接続される必要がある回路コンポーネントピンのすべてのペアのリストを生成するのに利用される。このリスト（又はネットリスト）は、サーバによりソートされる。各クライアントについて、サーバは接続がルート決定される必要がある異なるピンペアを割り当てる。クライアントが与えられたピンペアについて割り当てられたルーティングタスクを完了すると、結果をサーバに転送する。特に、クライアントは、サーバがＰＣＢマスターデザインを、クライアントがそれの割り当てられたピンペアについて求めたルートにより更新することを要求する。編集リクエストを転送した後、クライアントは、当該編集を反映させるため、ＰＣＢ設計のそれのコピーを更新しない。代わりに、クライアントは、サーバによるピンペアの割当て前に占有されていた状態にそれのコピーを返す。
【０００５】
少なくとも第１実施例では、本発明は、プリント基板（ＰＣＢ）の導電性パスをルート決定する方法を有する。当該方法は、コンポーネントピンペアを２つのピンの間に導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれに割り当てることからなる。本方法はまた、各クライアントから当該クライアントの割り当てられたピンペアを接続する導電性パスの提起されたルートを受信することからなる。当該ルートは、マスターＰＣＢ設計に含められ、本方法の各ステップが繰り返される。第２実施例は、第１実施例の方法を実行するための命令を含むマシーン可読媒体を含む。
【０００６】
少なくとも第２実施例では、本発明は、プリント基板（ＰＣＢ）の導電性パスをルート決定する他の方法を有する。本方法は、接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを含む。本方法はさらに、特定されたピン間の導電性パスのルートを自動検出し、検出されたルートを提起する編集リクエストを送信し、提起されたルートがＰＣＢ設計に含まれることの表示を受信することからなる。当該表示の受信後、ＰＣＢ設計のローカルコピーが、検出されたルートを含むよう更新される。第４実施例は、第３実施例の方法を実行するための命令を含むマシーン可読媒体を含む。
【０００７】
本発明の上記及び他の特徴及び効果は、添付された図面と共に以下の好適な実施例の詳細な説明から容易に明らかとなり、十分理解されるであろう。
［好適実施例の詳細な説明］
少なくとも一部の実施例は、従来の自動ルーティングアルゴリズムを実行する複数のコンピュータ間のＰＣＢ設計の自動ルーティングを分散化する。予備的なテスト処理は、大きく複雑なＰＣＢをルーティングするとき、コンピュータの個数に対して約０．７５のパフォーマンスレシオとなる。言い換えると、４つのクライアントコンピュータを用いてＰＣＢをルート決定する場合、ＰＣＢは、１つのコンピュータを用いてルート決定する場合より約３倍速くルート決定される。少なくとも一部の実施例では、サーバコンピュータは、ＰＣＢ設計のためのマスターデータベースを維持する。このデータベースは、回路コンポーネントとそれらの配置に関する情報、ＰＣＢ設計の設計基準及び他の各種情報を有する。ＰＣＢ設計のコピーが複数のクライアントコンピュータに提供される。概略的な電子回路（又はそれについての他の設計データ）が、電気的に接続される必要がある回路コンポーネントピンのすべてのペアのリストを生成するのに利用される。このリスト（又はネットリスト）、その後サーバにソートされる。各クライアントについて、サーバは、接続がルート決定される必要がある異なるピンペアを割り当てる。クライアントが与えられたピンペアについて割り当てられたルーティングタスクを完了させると、それは結果をサーバに転送する。特に、クライアントは、サーバがクライアントがそれの割り当てられたピンペアについて検出したルートによりＰＣＢマスター設計を更新することをリクエストする。編集リクエストを転送した後、クライアントは、編集を反映させるためのＰＣＢ設計のそれのコピーを更新しない。代わりに、クライアントは、それのコピーをサーバによるピンペアの割当て前に占有されている状態に返す。
【０００８】
クライアントから編集リクエストを受信した後、サーバは、要求元のクライアントにより検出されたルートについて設計基準チェック（ＤＲＣ）を実行する。当該ルートがＤＲＣをパスすると、サーバは、当該ルートを含めるよう編集リクエストをマスター設計に適用する。サーバは、新たなルートを反映させるため、すべてのクライアントにそれらのＰＣＢ設計のコピーを変更するよう更新を転送する。サーバはまた、新たに適用されたルートを検出したクライアントに新たなピンペアを割り当てる。編集リクエストがＤＲＣを満たしていない場合、サーバは、ＰＣＢマスター設計を更新しない。代わりに、サーバは、当該リクエストを送信したクライアントに前に割り当てられたピンペアのルート決定を再試行し、又は他のピンペアをルート決定するよう指示する。本発明のさらなる特徴及び追加的な実施例が、以下において説明される。
【０００９】
図１は、ネットワーク接続されたコンピュータシステムにより実現される本発明の一例を示すブロック図である。サーバ２は、マスターＰＣＢ設計３を維持し、複数のクライアントコンピュータ５、６及び７へのピンペア割当てをネットワーク８を介し通信する。クライアント５、６及び７のそれぞれは、ＰＣＢ設計３のコピーを維持する。しかしながら、以下でより詳細に説明されるように、各クライアントにより維持されるＰＣＢ設計３のコピーは、同一でなくてもよく、サーバ２がＰＣＢ設計３に実装したすべての変更を反映していないかもしれない。３つのクライアントのみが示されているが、他の多数のクライアントコンピュータが、同様にしてサーバ２とネットワーク接続することが可能である。各クライアント５、６及び７において、ＰＣＢコンポーネントのピン間の接続をルート決定するアプリケーションプログラムが実行されている。クライアント５、６及び７上の自動ルーティングソフトウェアは、サーバ２と協調して実行するよう変更される従来技術による各種自動ルーティングプログラムの何れかとすることができる（例えば、ＡＵＴＯＡＣＴＩＶＥ位置及びルート編集環境又はオレゴン州のＷｉｌｓｏｎｖｉｌｌｅのＭｅｎｔｏｒ Ｇｒａｐｈｉｃｓ Ｃｏｒｐｏｒａｔｉｏｎから利用可能なＢＬＡＺＥＲＯＵＴＥＲ自動ルーティングソフトウェアなど）。特に、以下でより詳細に説明されるように、サーバ２は、ピンペア間の接続をルート決定するため、各クライアントにピンペアを割当て、さらにルート決定された接続が許容又は拒絶されるか否かクライアントに指示する。サーバ２からの指示に基づき、クライアント５、５及び７は、既知のルーティングアルゴリズムを利用して、ＰＣＢ設計３の各部分をルート決定する。一部の実施例では、クライアント５、６及び７のすべてが、同一の自動ルーティングソフトウェアを有するとは限らない。
【００１０】
サーバ２は、データベース９からＰＣＢ設計３にアクセスする。データベース９は、サーバ２の一部（サーバ２のハードドライブなど）であってもよく、またサーバ２の近隣に配置されてもよく、またサーバ２から遠隔に配置されてもよい。実際、データベース９は、クライアント５、６又は７の１つに物理的に配置されてもよい。サーバ２とクライアント５、６及び７は、従来技術によるコンピュータである。それぞれは、例えば、１以上のプロセッサ、不揮発性ストレージ（ハードディスクドライブなど）、揮発性メモリ（ＲＡＭなど）及び当該技術分野において周知な他の要素を有する。サーバ２とクライアント５、６及び７は、様々なオペレーティングシステムソフトウェアの何れかを利用するものであってもよい、コンピュータ間のネットワーク接続の詳細は、同様に当該技術分野において知られたものであり、ここでは説明されない。特に、サーバ２は、クライアント５、６又は７より大きな処理能力を有する必要はない。
【００１１】
図２は、本発明の実施例をさらに示すのに用いられるＰＣＢ設計３の一部のブロック図である。図２に示されるように、各種電子コンポーネントの位置が基盤１０にマップ（又は配置）されている。例えば、集積回路ＩＣ１とＩＣ２の位置は、大きな正方形として示されている。メモリチップＭ１の位置は、大きな長方形として示されている。レジスタＲ１とＲ２は、より小さな長方形として示されている。図２の各コンポーネントとは、１以上の導電性トレースが接続される２以上のピン（大きなドットとして示される）を有する。これらのピンのいくつかは、以降の図面に対応するようラベル付けされている（２１ａ、２１ｂなど）。図２のＰＣＢは両面基板である。言い換えると、ＰＣＢは、基板の両側に形成されるトレースを有し、このとき、反対側のトレースは「ビア」（すなわち、トレースを接続するため基板に貫通され、その後導電性物質により充填された開口）を用いて接続される。基板の反対側のトレースは、図面では垂直方向に配置され、以降の図面では破線により示される。基板の前面のトレースは、水平方向に配置され、実践により示される。上述のように、ＰＣＢ設計３は、ＰＣＢ設計が生成されている回路の一部しか有さない。これは、本発明の実施例の説明を簡単化するためのものである。実際的には、完全な回路はしばしばはるかに複雑であり、数百のコンポーネントと数百又は数千のピンを有するかもしれない。図２に示されるコンポーネントは、単なる具体例であり、本発明は当該コンポーネントの個数、タイプ又は構成に限定されるものではない。同様に本発明はまた、１つのサイドにしかトレースを有しないＰＣＢと共に、２以上のトレースレイヤを有するＰＣＢにも適用可能である。
【００１２】
上述のように、ネットリストが、ＰＣＢ上の回路について生成される。このリストは、回路から概略的又は他の方法により構成可能であり、接続される必要がある各ピンペアを特定する。図３は、図２のＰＣＢ設計３に対応するネットリスト１１の一部を示す。図３に示されるように、ピン２１ａ（ＩＣ１に配置される）は、ピン２１ｂ（ＩＣ２に配置される）に接続される必要がある。同様に、ピン２２ａと２２ｂ（それぞれＩＣ１とＩＣ２に配置される）とピン２３ａと２３ｂ（それぞれＩＣ２とＭ１に配置される）が接続される。
【００１３】
図４は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションの始まりを概略的に示す。図４に示されるように、サーバ２は、マスターＰＣＢ設計３を維持する。設計３は、すべてのコンポーネントの位置と、サーバ２が設計３に実装したすべてのルート決定された接続とを有する。図４は自動ルーティングセッションの始まりに対応しているため、サーバ２は、まだルート決定されたピン接続を設計３に実装していない。サーバ２はさらに、自動ルーティングセッションに参加するクライアントコンピュータの情報を維持する。各クライアントについて、サーバ２は、当該クライアントにまだ与えられていない中断中の設計更新を追跡する（更新キュー）。サーバ２はさらに、自動ルーティングのため各クライアントに割り当てられた現在のピンペアと、割り当てられた自動ルーティングタスクの各クライアントの進捗状況に関する他の各種情報を追跡する。図４〜１２の例では、３つのクライアント（５、６及び７）しか示されていないが、異なる個数のクライアントを含めることができる。
【００１４】
図５は、図４の自動ルーティングセッションの以降の時点を示す。特に、サーバ２は、初期的にはルート決定のため、あるピンペアを各クライアントコンピュータに割り当てている。具体的には、サーバ２は、ピンペア２１ａ−２１ｂをクライアント５に、ピンペア２２ａ−２２ｂをクライアント６に、ピンペア２３ａ−２３ｂをクライアント７に割り当てている。クライアント７は、ピン２３ａと２３ｂとの間の接続をルート決定している。図６に示されるように、その後、クライアント７は編集リクエストをサーバ２に転送する。転送された編集リクエストは、クライアント７により求められたピン２３ａと２３ｂの間のルートを含む。編集リクエストをサーバ２に転送した後、クライアント７は、ピン２３ａ−２３ｂのルート決定前の状態にＰＣＢ設計のコピーを返し、サーバ２からのさらなる指示を待機する。
【００１５】
図７において、サーバ２は、クライアント７から編集リクエストを受信し、クライアント７が設計３に追加しようとするルートに対し設計基準チェック（ＤＲＣ）を実行した。特に、サーバ２は、提起されたルートが設計３に以前に追加された他のルートとコンフリクトしているか、又はＰＣＢ設計に対して確定された基準に違反しているか判断する。例えば、ある基準は、製造不具合により発生する短絡の可能性を最小限にするため、ＰＣＢ上のトレースが最小距離だけ分離されることを要求するかもしれない。クライアント７からの編集リクエストに含まれる提起されたルートがＤＲＣをパスした後、サーバ２は当該編集を設計３に適用する。その後、サーバ２は、ルート決定のため、クライアント７に新たなピンペアを割当て、ピン２３ａと２３ｂの間の新たなルートを反映させるため、すべてのクライアントが設計３のコピーを更新するよう更新メッセージを用意する。
【００１６】
サーバ２２は、各クライアントの更新キューに更新メッセージを配置する。少なくとも一部の実施例では、サーバ２は、当該クライアントがアイドル状態であるまで更新をクライアントに送信しない。例えば、クライアント７は、サーバ２が新たなピンペア割当てを転送するのを待機している。サーバ２が新たなピンペア割当てをクライアント７に転送すると、サーバ２はまた、提起されたルート２３ａ−２３ｂを設計３のクライアント７のコピーに含めるようクライアント７に指示する更新を転送する。このようにして、クライアント７は、それの新たなルーティングタスク中に、この新たに含められたルートを考慮することができる。サーバ２が提起されたルート２３ａ−２３ｂを拒絶し、クライアント７へのピンペア２３ａ−２３ｂの初期的な割当て時点と拒絶を通知する時点との間に更新が生成された場合、サーバ２は、提起されたルート２３ａ−２３ｂが拒絶されたことを通知し、クライアント７に再試行するよう指示するメッセージにより、これらの仮の更新をクライアント７に送信する。例えば、クライアント５又は６は、クライアント７の前にルーティングタスクを完了し、クライアント７により提起されたルートとコンフリクトするルートを生成したかもしれない。
【００１７】
図８は、図４において開始された自動ルーティングセッション中のさらなる以降の時点を示す。当該時点において、サーバ２は、ピンペア２１ａ−２１ｂ、２２ａ−２２ｂ、２３ａ−２３ｂ、２４ａ−２４ｂ、２５ａ−２５ｂ及び２６ａ−２６ｂのルートを設計３に実装した。クライアント７は、ピンペア２４ａ−２４ｂの間の接続をちょうどルート決定したところであり、クライアント５と６はそれぞれ、ピンペア２７ａ−２７ｂと２８ａ−２８ｂをルート決定しようとしている。サーバ２がピンペア２４ａ−２４ｂをクライアント７に割り当てた時点から、クライアント５は、ピンペア２５ａ−２５ｂを接続するルートを提起する編集リクエストをサーバ２に送信し、サーバ２は当該ルートを受け入れる。同じ期間中、クライアント６は、ピンペア２６ａ−２６ｂを接続するルートを提起する編集リクエストをサーバ２に送信し、サーバ２はまた当該ルートを受け入れる。サーバ２がピンペア２５ａ−２５ｂのルートを受け入れると、サーバ２は更新リクエストを準備し、それを各クライアントの更新キューに配置する。この更新は、新たなピンペア割当て（２７ａ−２７ｂ）と共にクライアント５に送信されたが、何れもルート決定割当てによりビジー状態であったため、クライアント６又は７には送信されなかった。サーバ２は以降においてクライアント６により提起されたピンペア２６ａ−２６ｂのルートを受け入れたとき、サーバ２は、当該ルートに対する他の更新リクエストを準備し、それを各クライアントの更新キューに配置する。その後、クライアント５はピンペア２７ａ−２７ｂをルート決定するのにビジー状態であり、クライアント７は依然としてピンペア２４ａ−２４ｂをルート決定するのにビジー状態であったため、更新はクライアント５又は７には送信されなかった。しかしながら、ピンペア２５ａ−２５ｂと２６ａ−２６ｂのルートの更新は、新たなピンペア割当て（２８ａ−２８ｂ）と共にクライアント６に送信された。従って、クライアント７がピンペア２４ａ−２４ｂのルートを検出した時点では、クライアント７はそれの更新キューに２つの更新を有し、クライアント５はそれの更新キューに１つの更新を有し、クライアント６はそれの更新キューに更新を有しない。同様に、クライアント７は、設計３に実装されたピンペア２５ａ−２５ｂと２６ａ−２６ｂのルートを知ることなく、ピンペア２４ａ−２４ｂをルート決定した。
【００１８】
図９において、クライアント７は、提起された２４ａ−２４ｂの接続ルートに対する更新リクエストを転送した。サーバ２がピンペア２４ａ−２４ｂを接続する提起されたルートに対してＤＲＣを実行すると、サーバ２は、基準違反を検出する。特に、図１０及び１０Ａにより詳細に示されるように、提起された２４ａ−２４ｂのルートは、ピン２５ａ−２５ｂのルートに近すぎる。図１０では、トレースは実線又は破線として示される。トレース間の最小クリアランスは、各トレースの周囲の斜線領域として表される。基板の同一サイドの２つのトレースの斜線領域がオーバーラップする場合（又は２以上のレベルを有する基板についての同一レベル上で）、これらのトレースは近すぎる。図１０に示されるように、図１０Ａの拡大図により詳細に示されるように、提起されたルート２４ａ−２４ｂのクリアランスゾーンの水平部分は、前に実装された２５ａ−２５ｂルートのクリアランスゾーンの水平部分とオーバーラップする。従って、サーバ２は、ピン２４ａ−２４ｂを接続する提起されたルートを拒絶する。このとき、サーバ２は、クライアント７の更新キューの（ピンペア２５ａ−２５ｂ及び２６ａ−２６ｂの）更新と共に、拒絶メッセージをクライアント７に送信する（図１１）。その後、クライアント７は、新たなルートを検出する（図１２）。特に、この新たなルートは、２つの水平セクションと２つの垂直セクションを有するため、追加的なビアを要する。図１２には図示されていないが、クライアント７は、その後第２のルートに対するその後の編集リクエストを転送する。
【００１９】
すべてのピンペアがルート決定されるまで、又は他の停止状態に到達するまで、図４〜９に示されるプロセスは続けられる。例えば、１以上のクライアントは、あるピンペアが現在の設計基準及び以前に実装されたルートに基づきルート決定できないと通知するかもしれない。一部のケースでは、接続のルート決定ができないことは、クライアントが指定された期間内に当該接続をルート決定しないことに基づくものであるかもしれない。ルート決定できない接続の接続数に応じて、設計者は、設計基準及び／又は以前のルートを調整することによりこれらの接続を手作業によりルート決定するかもしれない。決定不能な接続数が十分大きなものであり、あるいはその問題が他のルート及び／又は設計基準を調整することによっては解決できない場合、１以上のコンポーネントを移動させる必要があり、ルート決定プロセスは繰り返される。
【００２０】
本発明の他の実施例では、サーバ２は、ネットリストを介し複数のパスを実行する。第１パスでは、サーバ２は、クライアント５、６及び７がビアを用いることなくピンペア接続をルート決定することを要求する。サーバ２は、第１パス中にネットリストのすべてのピンペアを検索する（又は後述されるように、ビアなしにおそらくルート決定可能なすべてのペアを検索する）。各ピンペアについて、サーバ２は、クライアントの１つから接続ルートを取得するか、又は当該接続がビアなしにルート決定することは不可能であるという表示を取得する。あるピンペアの接続がビアなしにルート決定することができない場合、当該ピンペアのルート決定は、ネットリストの次のパスまで保留される。ネットリストの第２パスでは、サーバ２は、１つのビアしか用いることなくクライアントが接続をルート決定するよう要求する。サーバ２は、再びネットリストのすべてのピンペアを検索し（又は後述されるように、１つのみのビアでおそらくルート決定なすべてのペアを検索し）、クライアントの１つから各ペアのルート決定が不可能であるとの旨又はルートの何れかを取得する。１つのみのペアを用いてはルート決定不可能なピンペア接続は、次のパスまで再び保留される。第３パスでは、サーバ２は、クライアントが２つのビアを用いて接続をルート決定することを可能にする。サーバ２は再び、ネットリストのすべてのピンペアを検索し（又は２つのビアのみでおそらくルート決定可能なすべてのペアを検索し）、各ペアについて１つのクライアントからのルート決定が不可能であるとの旨又はルートの何れかを取得し、次のパスまでルート決定が不可能な接続を保留する。サーバ２は、すべての接続がルート決定されるまで、又は他の停止状態に到達するまで、追加的な個数のビアについてパスを実行し続ける。
【００２１】
各パスの内部に、サーバ２は複数のベース上でピンペアを割り当てる。まず、サーバ２は、より短い接続を要求するピンペアを割り当てる前に、より長い接続を要求するピンペアを割り当てる。言い換えると、サーバ２は、各ペア内のピンの間の距離に基づきピンペアをソートし、距離について降順にピンペアを割り当てる。一部の実施例では、サーバ２はさらに、ピンペアの相対位置に基づきピンペアをソートする。特に、同一の一般的分離距離を有するピンペアの複数のグループについて、サーバ２は、最も少なくしかオーバーラップしないピンペアを割り当てる。このことは、接続対象となるピンを有する３つのレジスタ（Ｒ）、メモリチップ（Ｍ）及び２つの集積回路（ＩＣ）を示す図１３に示される。ピン４１ａ及び４１ｂと、ピン４２ａ及び４２ｂと、ピン４３ａ及び４３ｂを接続する要求は、図１３の回路のネットリストに含まれる。ピン４１ａと４１ｂの間の距離は、ピン４２ａと４２ｂの間の距離に等しく、またピン４３ａと４３ｂの間の距離に等しい。図１３の上記ピンペアのそれぞれについて、各ペアのピンは対角的なノードに配置されるような長方形が示される。４３ａ−４３ｂの長方形は、４１ａ−４１ｂの長方形に若干オーバーラップしている。４２ａ−４２ｂの長方形は、より大きく４１ａ−４１ｂの長方形にオーバーラップしている。４３ａ−４３ｂの長方形は４１ａ−４１ｂの長方形とあまりオーバーラップしていないため、ピン４１ａ−４１ｂと４３ａ−４３ｂについて同時にルート決定される接続がコンフリクトする可能性は低い。他方、ピン４１ａ−４１ｂと４２ａ−４２ｂについて同時にルート決定される接続がコンフリクトする可能性は高い。従って、サーバ２は、ピン４１ａ−４１ｂを１つのクライアントに、４３ａ−４３ｂを他のクライアントにそれぞれ割当て、ピン４１ａ−４１ｂをルート決定しながら、ピン４２ａ−４２ｂを割り当てることを回避する。
【００２２】
実際に、図１３と同一の分離距離を有するピンペアが複数存在することはないかもしれない。しかしながら、分離に基づきピンペアをソートした後、サーバ２は、一部の実施例では、距離によりランク付けされたペアのリストのある範囲内のピンペアの間のオーバーラップの量をチェックするよう構成される。図１４は、少なくとも一部の実施例において、サーバ２が（図１５のネットリストを用いて）どのようにしてこのチェックを実行するかについての一例を示すフローチャートである。図１５のネットリストは、分離距離の降順によりピンペアをリストする。言い換えると、ピンペアｎ−４のピンはペアｎ−３のピンより離れており、ペアｎ−３のピンはさらにペアｎ−２のピンより離れているなどである。図１４及び１５において、サーバは、ピンペアｎとピンペアｎ−２を各自の第１及び第２クライアントに以前に割り当てており、現在はあるピンペアを第３クライアントに割り当てている。サーバは、ピンペアｎ−４、ｎ−３又はｎ−１をまだ割り当てていない。前のピンペア割当てを行うとき、これらのピンペアについて描かれる長方形は、他のピンペアの長方形よりすでに割り当てられたピンペアの長方形とより大きくオーバーラップしている。ブロック１０１（図１４）から始まり、サーバは、現在割り当てられているピンペア長方形といくつかの候補ピンペアの間のオーバーラップを評価する。特に、サーバは、ピンペアｎ−４、ｎ−３及びｎ−１のそれぞれの長方形が、ピンペアｎの長方形とピンペアｎ−２の長方形とオーバーラップしている量を計算する。その後、サーバは、サーバがＸ個の候補ピンペアについて計算する実行完了するまで、ピンペアｎ＋１、ｎ＋２、ｎ＋３などについて同じ計算を実行する。Ｘの値は、予め設定された値とすることができ、又は自動ルーティングセッション中に他の条件に基づき可変とすることも可能である。候補ピンペアのオーバーラップを計算した後、ブロック１０３において、サーバは、何れの候補ピンペアが現在割り当てられているピンペアと最小のオーバーラップを有しているか決定する。具体的には、サーバは、各候補ピンペアがピンペアｎとオーバーラップしている量を、同じ候補ピンペアがピンペアｎ−２とオーバーラップしている量に追加する。ブロック１０５において、最小の合計されたオーバーラップを有するピンペアが、第３クライアントに割り当てられる。
【００２３】
図１４のアルゴリズムに対する多数の変形が、他の実施例において利用されている。例えば、現在割り当てられているピンペアの最小合計オーバーラップを有するピンペアを単に割り当てる代わりに、サーバはさらに、あるピンペアが現在割り当てられているピンペノ何れとも所定量以上はオーバーラップしていないことを要求することができる。他の実施例では、以前に無視されたピンペアは（ｎ−４、ｎ−３及びｎ−１など）優先され、及び／又は所定の回数以上無視されると自動的に選択される。本発明の範囲内において、多数の他の変形が可能である。
【００２４】
一部の実施例では、サーバ２はまた、ある個数のビアを用いてルート決定を求めるネットリストのパスを行う前に、何れのピンペアが当該ビア制限を満たすことができないか判断する。（図１３の回路コンポーネントを生成する）図１６に示されるように、一部のピンペア（ピン４４ａ−４４ｂ、４８ａ−４８ｂなど）は、ターン（ｔｕｒｎ）を有しないルートにより潜在的に接続可能である。これらのピンがターンを有しないルートと接続することが可能である場合、ビアは必要ではないかもしれない。従って、これらのピンペアは、第１パス中のルート決定のため割当て可能である。他のピンペア（ピン４５ａ−４５ｂなど）は、少なくとも１つのターンと、従って少なくとも１つのビアを有するルートを要求するであろう。これらのピンペアはビアを用いることなくルート決定するよう制限されるクライアントによってはルート決定することはできないため、第２パスまでこれらのピンペアは保留される。一部のピンペア（ピン４６ａ−４６ｂ、４７ａ−４７ｂなど）は、少なくとも２つのターンを有し、従って少なくとも２つのビアを有するルートを要求し、このため、第３パスまで自動的に保留されるであろう。より複雑な設計では、さらに大きな最小ターン数を有するルートを有するピンペアが存在するかもしれない。
【００２５】
他の実施例では、ピンペア間の接続は、ＰＣＢの１つのレイヤ上で方向を変更することが許されるかもしれない。言い換えると、トレースがピン４９ａから延びることにより示されるように、いくつかのトレースは、他のレベルのトレースと接続することなく、従って、ビアを利用することなくターンすることが許されるかもしれない。当該実施例では、このようなトレースは、予め特定することができ（例えば、ある領域にあるコンポーネントについて、あるピンのこのようなトレースを可能にするなど）、適当なパスに含めることができる。
【００２６】
図１７は、本発明の少なくとも一部の実施例により、サーバからの分散自動ルーティングセッションを制御する方法のフローチャートである。ブロック２０１において、サーバは、プリント基板上に配置されるべき回路の電気設計を受信する。この電気設計は、接続されるべきすべてのピンペアを示すネットリストと、ＰＣＢ上のコンポーネントの配置を含む。ブロック２０３において、サーバはピンペアをソートする。一部の実施例では、上述されるように、サーバは接続対象のピンの間の距離に基づきピンペアをソートする。サーバはまた、１つのビア、又は２つのビアなどを用いることなく接続可能なピンなど、他のベースについてソートするかもしれない。ブロック２０５において、サーバは、パスカウンター（ｐ）を「０」に設定する。ブロック２０７において、サーバはパス０を開始する。当該パス中、サーバは、ビアを用いることなくピン間の接続をクライアントにルート決定するよう要求するであろう。ブロック２０９において、サーバは、クライアントへの割当てのためピンペアを選択する。初期的には、サーバは、ネットリストの最初のピンペアを単に選ぶことによりピンペアを選択する。最初のピンペアが割り当てられた後、サーバは前に割り当てられたピンペアとのオーバーラップ及び距離に基づくと共に（図１４及び１５について説明されるように）、あるピンペアが現在のビア制限を用いて接続可能であるかに基づき（例えば、パス０にはビアはなく、パス１には１つのビアなど）、以降のピンペアを選択する。ブロック２１１において、サーバは、選択されたピンペアをクライアントに割当て、割り当てられたピンペアを当該クライアントの更新キューの更新と共に転送する（初期的には更新は存在しない）。ブロック２１３において、サーバは、ピンペアに割り当てられていない他の何れかのクライアントが存在しないか判断する。存在する場合、サーバはブロック２０９に戻って、次のクライアントのピンペアを選択肢、ブロック２１１において当該割当てを転送する。ブロック２１３において、ピンペアが割り当てられる必要があるクライアントがもはや存在しない場合（「ｎｏ」ブランチ）、サーバは、ブロック２１５に移行する。ブロック２１５において、サーバは、クライアントが当該クライアントの割り当てられたピンペアの提起されたルートを含む編集リクエストを提出するか（編集）、又は割り当てられたピンペアが接続不可（エラー）であることを示すまで待機する。
【００２７】
クライアントは、それ自体、割り当てられたピンペアが現在のビア制限を用いてルート決定することができないことを示すことによって、エラーを提出するようにしてもよい。クライアントはまた、所定時間以上接続をルート決定しようとした場合、エラーを提出するようにしてもよい。サーバはまた、クライアントにタイムアウトエラーを生成するようにしてもよい。エラーが発生すると、サーバはブロック２１７に移行する。ブロック２７１において、サーバは、現在のビア制限のためルート決定することができないか判断する。そうである場合（ピンペアが現在ルート決定できないため、「ｎｏ」ブランチ）、又はピンペアが現在のパスにおいて最大数のエラーを前に生成してしまっている場合（拒絶が最大値未満でない）、サーバはブロック２１９に移行する。ブロック２１９において、ピンペアは以降のパスに保留される。その後、サーバはブロック２２７に移行し、現在のパスに残りのピンペアがあるか判断する。そうである場合、サーバは保留されたピンペアをルート決定できないクライアントの他のピンペアの選択のため、ブロック２０９に移行する。そうでない場合、サーバは後述されるブロック２０３に移行する。
【００２８】
ブロック２１５で通知されるエラーが、ビア制限により生じたものではなく、ピンペアが現在のビアにおいて最大回数拒絶されていない場合、サーバは、ブロック２１７において「ｙｅｓ」ブランチを選択する。例えば、一部のピンペアがルート決定された後、あるクライアントは前にルート決定された接続を知ることなく接続をルート決定するかもしれない。この場合、現在のビア制限を用いて接続をルート決定することが依然として可能であるかもしれない。従って、ブロック２２１において、サーバは、当該クライアントの更新キューの更新と、現在のピンペアのルート決定を再試行する指示（すなわち、ピンペアの再割当て）を送信する。ブロック２２１から、サーバはブロック２１５に戻り、他の編集又はエラー報告を待機する。
【００２９】
サーバがブロック２１５において編集リクエストを受信した場合、サーバは、ブロック２２３に戻り、提起されたルートについて設計基準チェック（ＤＲＣ）を実行する。提起されたルートがＤＲＣを満たしていない場合（「不成功（ｆａｉｌ）」ブランチ）、サーバはブロック２２５に移行する。ブロック２２５において、サーバは、ピンペアが現在パス中に最大回数未満しかＤＲＣに失敗していないか判断する。そうである場合（「ｙｅｓ」ブランチ）、サーバは、ブロック２２１に移行し、更新がクライアントに送信され、クライアントは再試行するよう指示される。現在パス中のピンペアのＤＲＣの失敗回数が最大数未満でない場合（「ｎｏ」ブランチ）、サーバはブロック２１９に移行し、ピンペアが以降のパスに保留され、その後ブロック２２７に移行する。
【００３０】
提起されたルートがブロック２２３においてＤＲＣをパスすると（「成功（ｐａｓｓ）ブランチ」ブランチ）、サーバは、ブロック２２９においてマスターＰＣＢ設計に当該ルートを実装する。サーバはまた、新たに実装されたルートを反映する更新を生成し、各クライアントのキューに更新を配置する。その後、サーバはブロック２３１に移行し、現在のパスに残りのピンペアがないか判断する。そうである場合、サーバはブロック２０９に移行し、実装されたルートを提供するクライアントのため他のピンペアを選択する。そうでない場合、サーバはブロック２３３に移行する。ブロック２３３において、サーバは、ネットリストの他のパスを実行するか判断する。例えば、設計基準は、何れの状況においても指定された個数のビアより多く有するルートが存在しないことを要求するかもしれない。サーバが当該指定された個数プラスビアのないルートには１つのパスに等しいパス数を実行した後、サーバはもはやパスを生成しない。このような場合、サーバはブロック２３３の「ｎｏ」ブランチからブロック２３７に移行する。ブロック２３７において、サーバは、何れのピンペア（存在すれば）がルート決定されていないか示すレポートを生成し、その後、ルーティングセッションを終了する。さらなるパスがネットリストにおいて生成される場合（ブロック２３３の「ｙｅｓ」ブランチ）、サーバは、ブロック２３５においてパスカウンターｐをインクリメントし、その後、ブロック２０７に戻り、新たなパスを開始する。次のパス中、クライアントは、ｐ個のビアを用いてピンペアをルート決定するよう指示される。
【００３１】
一般には、ＤＲＣを実行し、サーバにより実行される他のタスクを実行するのに必要な処理時間は、１つのピンペアをルート決定するのにクライアントにより必要とされる時間よりはるかに少ない。従って、サーバはしばしば、クライアントより大きな処理パワーを必要としなくなる。複数の編集リクエストが素早く連続的にクライアントから到達する場合（図１７のブロック２１５）、当該編集リクエストはキュー可能であり、ＦＩＦＯベースによりサーバにより処理可能となる。
【００３２】
図１８は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションによりクライアントを実行する方法のフローチャートである。ブロック３０１から始まり、クライアントはサーバから指示を受信する。これらの指示は、新たなピン割当てかもしれないし、あるいはピンペアのルート決定を再試行する指示であるかもしれない（すなわち、ピンペアの再割当て）。クライアントはまた、サーバにより可能な接続に介される制限を受信し（ビア制限など）、またクライアントにより維持されるＰＣＢ設計のコピーの１以上の更新を受信するようにしてもよい。ブロック３０３において、ブロック３０１において受信した更新が（存在する場合）、ＰＣＢ設計のクライアントコピーに適用される。ブロック３０５において、クライアントは、割り当てられたピンペアを接続するルートを検出するため、１以上のルーティングアルゴリズムの利用を開始する。これらのルーティングアルゴリズムに基づき、クライアントは、ルートを検出するか、あるいはピン間の接続が検出不可であると判断する（現在のビア制限のためなど）。一部の実施例では、クライアントはまた、所定時間後に接続をルート決定することを停止し、必要となる時間に基づきルート決定することができないと通知するよう構成されてもよい。ブロック３０５から、クライアントはブロック３０７に移行する。ブロック３０５においてクライアントが割り当てられたピンペアのルートを検出した場合、クライアントは、「ｙｅｓ」ブランチによりブロック３０９に移行する。ブロック３０９において、クライアントは、検出されたルートを含む編集リクエストをサーバに転送する。ブロック３１１において、クライアントは、ブロック３０５の前であって、ブロック３０３の後にＰＣＢ設計のそれのコピーを当該コピーの状態に戻す。ブロック３１１から、クライアントは、ブロック３１５に戻り、サーバからのさらなる指示を待機する。クライアントがブロック３０５において割り当てられたピンペアのルートを検出することができなかった（又はタイムアウトとなった）場合、クライアントは、「ｎｏ」ブランチによりブロック３０７からブロック３１３に移行する。ブロック３１３において、クライアントは、ピンペア接続をルート決定することができないことを通知する。その後、クライアントはさらなる指示を待機するためブロック３１５に移行する。
【００３３】
一部の実施例では、図１９に示されるように、サーバは、ルート決定のため同一のピンペア（ｙａ−ｙｂ）を複数のクライアントに割り当てるようにしてもよい。一部のケースでは、ルーティングセッションは、ほとんど完了し、ルート決定されていないピンペアよりクライアントの方が多くなるかもしれない。他のケースでは、比較のため他のルートを展開することが望ましいかもしれない。ピンペア接続をルート決定するのに要する処理時間は、より多くのピン接続が追加されるに従って、大きく増加しうる。より多くのクライアントが同じルーティング問題を解こうとする場合、解は潜在的により速く検出されるかもしれない。これについて、図１９に示されるように、クライアントには、同じピンペアをルート決定するための異なるパラメータが与えられているかもしれない。一例として、１つのクライアントは必要に応じて多数のビアを利用することが許され、他のクライアントは１つのＰＣＢレイヤを占有する多方向トレースを利用することが許されているかもしれない（すなわち、ビアを利用することなく方向を変更する）。他の例として、１つのクライアントは、ルートの一部を削除し、再ルート決定することが許され、他のクライアントは、他のルート部分を削除し、再ルート決定することが許されているかもしれない。また、クライアントには異なるコンポーネント配置、異なるルーティングスキーム、異なる接続スケジュール又は他の異なるパラメータを有するルーティング割当てが与えられてもよい。さらなる他の実施例では、ピンペアをルート決定するクライアントには、労力の重複を回避するため、同じピンペアを他のクライアントがルート決定することによりしさされるルートがアドバイスされる。同一のピンペアをルート決定するクライアントの状況は、例えば、何れのルーティングパラメータがより迅速な進捗を可能にするか判断するためなどに監視されてもよい。
【００３４】
本発明を実行する複数の例が説明されたが、当業者は、添付された請求項に与えられる本発明の趣旨及び範囲内に属する上述の例の変形及び並び替えが多数存在するということは理解するであろう。上述のアルゴリズム、システム構成及び他の特徴は、単なる例にすぎない。多数の他のアルゴリズム、構成及び特徴と同様に、上述のアルゴリズム、システム及び特徴の変更は本発明の範囲内に属する。例えば、上述の実施例は、１つのピンペアを各クライアントコンピュータに割り当てるが、本発明はこのような実施例に限定されるものではない。他の実施例では、サーバは、あるクライアントに対する自動ルーティング割当てに２つの（又はそれ以上の）ピンペアを含むかもしれない。その後、クライアントは、これらのピンペアの一部又はすべてについての提起されたルートを返す。従って、以下の請求項の単数形の使用は、排他的に解釈されるべきではない（例えば、「ある」とは、「唯一」を意味するものではない）。他の例として、２つのピンの間のルートを検出するクライアントコンピュータは、編集リクエストをサーバに転送するとすぐに、ＰＣＢ設計のそれのコピーを以前の状態に戻す必要はない。代わりに、クライアントは、それの検出したルートが残ることを許容することが可能であり、サーバが検出されたルートを拒絶した場合、クライアントは、拒絶を受信すると、検出されたルートを削除することができる。さらに、ここで使用される（請求項を含む）「プロセッサ」という表現は、単一のプロセッサに限定されず、相互に関連する処理機能を共に実行するよう協調する複数のプロセッサを含むものであってもよい。
【図面の簡単な説明】
【００３５】
【図１】図１は、本発明の少なくとも一部の特徴が実現される計算システムのブロック図である。
【図２】図２は、ＰＣＢ設計の一部のブロック図である。
【図３】図３は、図２のＰＣＢ設計のネットリストである。
【図４】図４は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションの始めを概略図により示す。
【図５】図５は、図４の自動ルーティングセッションの以降の時点を示す。
【図６】図６は、図４の自動ルーティングセッションの以降の時点を示す。
【図７】図７は、図４の自動ルーティングセッションの以降の時点を示す。
【図８】図８は、図４の自動ルーティングセッションの以降の時点を示す。
【図９】図９は、図４の自動ルーティングセッションの以降の時点を示す。
【図１０】図１０は、提起されたピン接続ルートの設計基準違反を示す。
【図１０Ａ】図１０Ａは、提起されたピン接続ルートの設計基準違反を示す。
【図１１】図１１は、図４の自動ルーティングセッションのさらなる以降の時点を示す。
【図１２】図１２は、図４の自動ルーティングセッションのさらなる以降の時点を示す。
【図１３】図１３は、相対位置によるピンペアの分類を示す。
【図１４】図１４は、少なくとも一部の実施例によるピンペア間のオーバーラップ量をチェックするアルゴリズムを示すフローチャートである。
【図１５】図１５は、分離距離の降順によるピンペアを有するネットリストを示す。
【図１６】図１６は、最小のビアによるピンペアの分類を示す。
【図１７】図１７は、本発明の少なくとも一部の実施例によるサーバからの分散自動ルーティングセッションを制御する方法のフローチャートである。
【図１８】図１８は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションにおいてクライアントを実行する方法のフローチャートである。
【図１９】図１９は、本発明の少なくとも一部の実施例による複数のクライアントへの同一のピンペアの割当てを示す。
【発明の詳細な説明】
【０００１】
［関連出願の相互参照］
本出願は、参照することにより含まれる、２００３年１１月２１日に出願された米国仮出願第６０／５２３，６９７号「Ａ Ｒｅｖｏｌｕｔｉｏｎａｒｙ Ｄｅｓｉｇｎ Ｔｅｃｈｎｏｌｏｇｙ」の優先権を主張する。
［発明の技術分野］
本発明は、電子設計自動化ツールの技術分野に関する。より詳細には、本発明の実施例は、プリント基板（ＰＣＢ）設計におけるトレースのルーティングを含む電子回路の導電性パスのルーティングに関する。
［発明の背景］
電子回路は、典型的には、レジスタ、集積回路（ＩＣ）、キャパシタ、ダイオード、トランジスタなどの多数の電子コンポーネントを有する。各コンポーネントは、当該コンポーネントがあるタイプの電気コンダクタにより１以上の他のコンポーネントに電気的に接続される接続ポイント（又はピン）を有する。プリント基板（ＰＣＢ）上の回路では、コンポーネントピンは、基板上（内）の導電性ストリップ（又はトレース）と接続される。多くのケースにおいて、電気回路はまず概略図により記述される。この概略は、通常は記号表示されたコンポーネント間を結ぶラインにより相互接続される従来技術による記号（レジスタについてはジグザグのライン、ＩＣについては矩形のボックスなど）として回路コンポーネントを示す。概略図に与えられるコンポーネントと、当該コンポーネント間の必要な電気的接続に基づき、ＰＣＢ上の物理コンポーネントの構成（又は配置）が決定される。その後、電気的に接続される必要があるピンのペア間でトレースがルーティングされる。
【０００２】
電子回路がより複雑になるに従い、当該回路のＰＣＢの設計はより困難なものとなる。この複雑さのため、多くの設計者がしばしば同一のＰＣＢ設計について作業する。参照することによりここに含まれる、米国特許第６，７０８，３１３号「Ｐａｒａｌｌｅｌ Ｅｌｅｃｔｒｏｎｉｃ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ：Ｓｈａｒｅｄ Ｓｉｍｕｌｔａｎｅｏｕｓ Ｅｄｉｔｉｎｇ」は、複数の設計者が同一のＰＣＢ設計について同時に作業することを可能にするシステム及び方法を記載している。ここで使用される「設計者」とは、人間の設計者と設計機能を実行するソフトウェアアプリケーションの両方を含む。少なくとも一実施例では、サーバコンピュータはＰＣＢ設計を維持し、当該設計のコピーが複数のクライアントコンピュータに配置される。各クライアントは、ＰＣＢ設計の全体を閲覧することができる。クラインと側で当該設計が編集されると、この編集は設計を編集するリクエストとしてサーバに送信される。サーバが設計基準チェック（ＤＲＣ）を実行し、リクエストされた編集が他の編集とコンフリクトしない、又はＰＣＢ設計に課された制約（トレース間の最小セパレーションなど）に違反していないことを確認した後、サーバは、リクエストされた編集を当該設計に適用する。適用された編集は、その後、クライアント側におけるＰＣＢ設計コピーの更新のため、クライアントに配信される。
【０００３】
複数の設計者が同一のＰＣＢ設計について同時に作業するときでさえ、この処理は大変時間のかかるものとなりうる。設計処理の最も時間を要する点の１つは、電子コンポーネント間の導電性パスのルーティングである。接続ラインが頻繁に交差している概略図では、ＰＣＢ上のトレースの交差は短絡又は他の望ましくない結果をもたらしうる。回路のすべてのコンポーネントが基板上のある位置に割り当てられると（配置されると）、所望の電子接続のみが生成されるように、ピン間の接続がルーティングされる必要がある。一部のケースでは、ＰＣＢは相互に接続される必要がある数百又は数千のピンを有するかもしれない。ある接続について与えられたルートは、しばしば他の接続のための利用可能なルートを排除する。ルート決定される接続が多くなるほど、利用可能なルーティングスペースは少なくなり、残りの接続をルート決定する作業はより困難となる。マルチレイヤＰＣＢは、接続をルート決定するためのスペースをより多く提供することにより上記問題を解消するものであるが、この作業は極めて複雑なものである。しばしば、多数の接続が、以前にルート決定された接続が「取り除かれ（ｒｉｐｐｅｄ ｕｐ）」、再ルート決定される必要があることが検出される前に、ルート決定される。
【０００４】
人間の設計者によるＰＣＢの手動によるルート決定は、大変大きな作業時間を要するため、ルーティング処理を自動化する（「自動ルーティング」）ための多数のアルゴリズムが作成されてきた。しかしながら、適度な複雑さの回路についてでさえ、既存のアルゴリズムはＰＣＢ全体をルート決定するのに極めて多くの時間を要する。実際、ＰＣＢ設計者が仕事時間の終わりに自動ルーティングプログラムをスタートさせ、プログラムを一晩中実行させることが通常である。このような大きな実行時間に対する１つの可能な解決策は、複数のコンピュータ間にルーティングタスクを分散させることである。集積回路（ＩＣ）の設計に用いられるルーティングプログラムは、予め分散環境において動作するよう変換されていた。しかしながら、ＰＣＢのルーティング問題は、ＩＣルーティングに係るものとは全く異なるものである。例えば、ＩＣの機能コンポーネントは、しばしばトレースが基盤の幅全体及び／又は長さ全体にわたることが必要であるＰＣＢよりも、より局所化される傾向にある。この局所性の欠落は、ＰＣＢのルーティング設計の領域の割当てを困難にすると共に、異なる設計者（人間又は自動化の何れでも）によりルート決定される各セクションを結合させるとき問題を生じさせる。ＩＣの各要素は、同一サイズに近いものとなる傾向があり（少なくともトランジスタレベルでは）、しばしばチップの異なるレベルにおける導電性パスの接続に関するコストは大きなものではない。他方、ＰＣＢ上に配置される各コンポーネントは、広範なサイズを有し、このサイズ範囲はルーティング問題を複雑化しうる。さらに、製造コストはしばしば、異なるＰＣＢレイヤ上のトレースを接続する「ビア」を最小限に抑えるよう要求する。上記及び他の理由のため、ＩＣ設計に用いられる分散自動ルーティングアプローチは、ＰＣＢ設計において限定的な価値しか有さない。実際、分散ＰＣＢ自動ルーティングは、新たなタイプのルーティングアルゴリズムがまず開発されることを要求し、既存のルーティングアルゴリズムが１つのＰＣＢをルート決定するのに複数のコンピュータにより効果的には利用することができないと、多くが考えている。
［発明の概要］
本発明の実施例は、自動ルーティングがより迅速に実行されることを可能にし、ＰＣＢ設計のルートが既存のルーティングアルゴリズムを利用して複数のコンピュータにより生成されることを可能にする。少なくとも一部の実施例では、サーバコンピュータは、ＰＣＢ設計のためのマスターデータベースを維持する。このデータベースは、回路コンポーネントとそれらの配置に関する情報、ＰＣＢ設計の設計基準及び他の各種情報を有する。ＰＣＢ設計のコピーが、複数のクライアントコンピュータに提供される。概略的な電子回路（又はそのための他の設計データ）が、接続される必要がある回路コンポーネントピンのすべてのペアのリストを生成するのに利用される。このリスト（又はネットリスト）は、サーバによりソートされる。各クライアントについて、サーバは接続がルート決定される必要がある異なるピンペアを割り当てる。クライアントが与えられたピンペアについて割り当てられたルーティングタスクを完了すると、結果をサーバに転送する。特に、クライアントは、サーバがＰＣＢマスターデザインを、クライアントがそれの割り当てられたピンペアについて求めたルートにより更新することを要求する。編集リクエストを転送した後、クライアントは、当該編集を反映させるため、ＰＣＢ設計のそれのコピーを更新しない。代わりに、クライアントは、サーバによるピンペアの割当て前に占有されていた状態にそれのコピーを返す。
【０００５】
少なくとも第１実施例では、本発明は、プリント基板（ＰＣＢ）の導電性パスをルート決定する方法を有する。当該方法は、コンポーネントピンペアを２つのピンの間に導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれに割り当てることからなる。本方法はまた、各クライアントから当該クライアントの割り当てられたピンペアを接続する導電性パスの提起されたルートを受信することからなる。当該ルートは、マスターＰＣＢ設計に含められ、本方法の各ステップが繰り返される。第２実施例は、第１実施例の方法を実行するための命令を含むマシーン可読媒体を含む。
【０００６】
少なくとも第２実施例では、本発明は、プリント基板（ＰＣＢ）の導電性パスをルート決定する他の方法を有する。本方法は、接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを含む。本方法はさらに、特定されたピン間の導電性パスのルートを自動検出し、検出されたルートを提起する編集リクエストを送信し、提起されたルートがＰＣＢ設計に含まれることの表示を受信することからなる。当該表示の受信後、ＰＣＢ設計のローカルコピーが、検出されたルートを含むよう更新される。第４実施例は、第３実施例の方法を実行するための命令を含むマシーン可読媒体を含む。
【０００７】
本発明の上記及び他の特徴及び効果は、添付された図面と共に以下の好適な実施例の詳細な説明から容易に明らかとなり、十分理解されるであろう。
［好適実施例の詳細な説明］
少なくとも一部の実施例は、従来の自動ルーティングアルゴリズムを実行する複数のコンピュータ間のＰＣＢ設計の自動ルーティングを分散化する。予備的なテスト処理は、大きく複雑なＰＣＢをルーティングするとき、コンピュータの個数に対して約０．７５のパフォーマンスレシオとなる。言い換えると、４つのクライアントコンピュータを用いてＰＣＢをルート決定する場合、ＰＣＢは、１つのコンピュータを用いてルート決定する場合より約３倍速くルート決定される。少なくとも一部の実施例では、サーバコンピュータは、ＰＣＢ設計のためのマスターデータベースを維持する。このデータベースは、回路コンポーネントとそれらの配置に関する情報、ＰＣＢ設計の設計基準及び他の各種情報を有する。ＰＣＢ設計のコピーが複数のクライアントコンピュータに提供される。概略的な電子回路（又はそれについての他の設計データ）が、電気的に接続される必要がある回路コンポーネントピンのすべてのペアのリストを生成するのに利用される。このリスト（又はネットリスト）、その後サーバにソートされる。各クライアントについて、サーバは、接続がルート決定される必要がある異なるピンペアを割り当てる。クライアントが与えられたピンペアについて割り当てられたルーティングタスクを完了させると、それは結果をサーバに転送する。特に、クライアントは、サーバがクライアントがそれの割り当てられたピンペアについて検出したルートによりＰＣＢマスター設計を更新することをリクエストする。編集リクエストを転送した後、クライアントは、編集を反映させるためのＰＣＢ設計のそれのコピーを更新しない。代わりに、クライアントは、それのコピーをサーバによるピンペアの割当て前に占有されている状態に返す。
【０００８】
クライアントから編集リクエストを受信した後、サーバは、要求元のクライアントにより検出されたルートについて設計基準チェック（ＤＲＣ）を実行する。当該ルートがＤＲＣをパスすると、サーバは、当該ルートを含めるよう編集リクエストをマスター設計に適用する。サーバは、新たなルートを反映させるため、すべてのクライアントにそれらのＰＣＢ設計のコピーを変更するよう更新を転送する。サーバはまた、新たに適用されたルートを検出したクライアントに新たなピンペアを割り当てる。編集リクエストがＤＲＣを満たしていない場合、サーバは、ＰＣＢマスター設計を更新しない。代わりに、サーバは、当該リクエストを送信したクライアントに前に割り当てられたピンペアのルート決定を再試行し、又は他のピンペアをルート決定するよう指示する。本発明のさらなる特徴及び追加的な実施例が、以下において説明される。
【０００９】
図１は、ネットワーク接続されたコンピュータシステムにより実現される本発明の一例を示すブロック図である。サーバ２は、マスターＰＣＢ設計３を維持し、複数のクライアントコンピュータ５、６及び７へのピンペア割当てをネットワーク８を介し通信する。クライアント５、６及び７のそれぞれは、ＰＣＢ設計３のコピーを維持する。しかしながら、以下でより詳細に説明されるように、各クライアントにより維持されるＰＣＢ設計３のコピーは、同一でなくてもよく、サーバ２がＰＣＢ設計３に実装したすべての変更を反映していないかもしれない。３つのクライアントのみが示されているが、他の多数のクライアントコンピュータが、同様にしてサーバ２とネットワーク接続することが可能である。各クライアント５、６及び７において、ＰＣＢコンポーネントのピン間の接続をルート決定するアプリケーションプログラムが実行されている。クライアント５、６及び７上の自動ルーティングソフトウェアは、サーバ２と協調して実行するよう変更される従来技術による各種自動ルーティングプログラムの何れかとすることができる（例えば、ＡＵＴＯＡＣＴＩＶＥ位置及びルート編集環境又はオレゴン州のＷｉｌｓｏｎｖｉｌｌｅのＭｅｎｔｏｒ Ｇｒａｐｈｉｃｓ Ｃｏｒｐｏｒａｔｉｏｎから利用可能なＢＬＡＺＥＲＯＵＴＥＲ自動ルーティングソフトウェアなど）。特に、以下でより詳細に説明されるように、サーバ２は、ピンペア間の接続をルート決定するため、各クライアントにピンペアを割当て、さらにルート決定された接続が許容又は拒絶されるか否かクライアントに指示する。サーバ２からの指示に基づき、クライアント５、５及び７は、既知のルーティングアルゴリズムを利用して、ＰＣＢ設計３の各部分をルート決定する。一部の実施例では、クライアント５、６及び７のすべてが、同一の自動ルーティングソフトウェアを有するとは限らない。
【００１０】
サーバ２は、データベース９からＰＣＢ設計３にアクセスする。データベース９は、サーバ２の一部（サーバ２のハードドライブなど）であってもよく、またサーバ２の近隣に配置されてもよく、またサーバ２から遠隔に配置されてもよい。実際、データベース９は、クライアント５、６又は７の１つに物理的に配置されてもよい。サーバ２とクライアント５、６及び７は、従来技術によるコンピュータである。それぞれは、例えば、１以上のプロセッサ、不揮発性ストレージ（ハードディスクドライブなど）、揮発性メモリ（ＲＡＭなど）及び当該技術分野において周知な他の要素を有する。サーバ２とクライアント５、６及び７は、様々なオペレーティングシステムソフトウェアの何れかを利用するものであってもよい、コンピュータ間のネットワーク接続の詳細は、同様に当該技術分野において知られたものであり、ここでは説明されない。特に、サーバ２は、クライアント５、６又は７より大きな処理能力を有する必要はない。
【００１１】
図２は、本発明の実施例をさらに示すのに用いられるＰＣＢ設計３の一部のブロック図である。図２に示されるように、各種電子コンポーネントの位置が基盤１０にマップ（又は配置）されている。例えば、集積回路ＩＣ１とＩＣ２の位置は、大きな正方形として示されている。メモリチップＭ１の位置は、大きな長方形として示されている。レジスタＲ１とＲ２は、より小さな長方形として示されている。図２の各コンポーネントとは、１以上の導電性トレースが接続される２以上のピン（大きなドットとして示される）を有する。これらのピンのいくつかは、以降の図面に対応するようラベル付けされている（２１ａ、２１ｂなど）。図２のＰＣＢは両面基板である。言い換えると、ＰＣＢは、基板の両側に形成されるトレースを有し、このとき、反対側のトレースは「ビア」（すなわち、トレースを接続するため基板に貫通され、その後導電性物質により充填された開口）を用いて接続される。基板の反対側のトレースは、図面では垂直方向に配置され、以降の図面では破線により示される。基板の前面のトレースは、水平方向に配置され、実践により示される。上述のように、ＰＣＢ設計３は、ＰＣＢ設計が生成されている回路の一部しか有さない。これは、本発明の実施例の説明を簡単化するためのものである。実際的には、完全な回路はしばしばはるかに複雑であり、数百のコンポーネントと数百又は数千のピンを有するかもしれない。図２に示されるコンポーネントは、単なる具体例であり、本発明は当該コンポーネントの個数、タイプ又は構成に限定されるものではない。同様に本発明はまた、１つのサイドにしかトレースを有しないＰＣＢと共に、２以上のトレースレイヤを有するＰＣＢにも適用可能である。
【００１２】
上述のように、ネットリストが、ＰＣＢ上の回路について生成される。このリストは、回路から概略的又は他の方法により構成可能であり、接続される必要がある各ピンペアを特定する。図３は、図２のＰＣＢ設計３に対応するネットリスト１１の一部を示す。図３に示されるように、ピン２１ａ（ＩＣ１に配置される）は、ピン２１ｂ（ＩＣ２に配置される）に接続される必要がある。同様に、ピン２２ａと２２ｂ（それぞれＩＣ１とＩＣ２に配置される）とピン２３ａと２３ｂ（それぞれＩＣ２とＭ１に配置される）が接続される。
【００１３】
図４は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションの始まりを概略的に示す。図４に示されるように、サーバ２は、マスターＰＣＢ設計３を維持する。設計３は、すべてのコンポーネントの位置と、サーバ２が設計３に実装したすべてのルート決定された接続とを有する。図４は自動ルーティングセッションの始まりに対応しているため、サーバ２は、まだルート決定されたピン接続を設計３に実装していない。サーバ２はさらに、自動ルーティングセッションに参加するクライアントコンピュータの情報を維持する。各クライアントについて、サーバ２は、当該クライアントにまだ与えられていない中断中の設計更新を追跡する（更新キュー）。サーバ２はさらに、自動ルーティングのため各クライアントに割り当てられた現在のピンペアと、割り当てられた自動ルーティングタスクの各クライアントの進捗状況に関する他の各種情報を追跡する。図４〜１２の例では、３つのクライアント（５、６及び７）しか示されていないが、異なる個数のクライアントを含めることができる。
【００１４】
図５は、図４の自動ルーティングセッションの以降の時点を示す。特に、サーバ２は、初期的にはルート決定のため、あるピンペアを各クライアントコンピュータに割り当てている。具体的には、サーバ２は、ピンペア２１ａ−２１ｂをクライアント５に、ピンペア２２ａ−２２ｂをクライアント６に、ピンペア２３ａ−２３ｂをクライアント７に割り当てている。クライアント７は、ピン２３ａと２３ｂとの間の接続をルート決定している。図６に示されるように、その後、クライアント７は編集リクエストをサーバ２に転送する。転送された編集リクエストは、クライアント７により求められたピン２３ａと２３ｂの間のルートを含む。編集リクエストをサーバ２に転送した後、クライアント７は、ピン２３ａ−２３ｂのルート決定前の状態にＰＣＢ設計のコピーを返し、サーバ２からのさらなる指示を待機する。
【００１５】
図７において、サーバ２は、クライアント７から編集リクエストを受信し、クライアント７が設計３に追加しようとするルートに対し設計基準チェック（ＤＲＣ）を実行した。特に、サーバ２は、提起されたルートが設計３に以前に追加された他のルートとコンフリクトしているか、又はＰＣＢ設計に対して確定された基準に違反しているか判断する。例えば、ある基準は、製造不具合により発生する短絡の可能性を最小限にするため、ＰＣＢ上のトレースが最小距離だけ分離されることを要求するかもしれない。クライアント７からの編集リクエストに含まれる提起されたルートがＤＲＣをパスした後、サーバ２は当該編集を設計３に適用する。その後、サーバ２は、ルート決定のため、クライアント７に新たなピンペアを割当て、ピン２３ａと２３ｂの間の新たなルートを反映させるため、すべてのクライアントが設計３のコピーを更新するよう更新メッセージを用意する。
【００１６】
サーバ２２は、各クライアントの更新キューに更新メッセージを配置する。少なくとも一部の実施例では、サーバ２は、当該クライアントがアイドル状態であるまで更新をクライアントに送信しない。例えば、クライアント７は、サーバ２が新たなピンペア割当てを転送するのを待機している。サーバ２が新たなピンペア割当てをクライアント７に転送すると、サーバ２はまた、提起されたルート２３ａ−２３ｂを設計３のクライアント７のコピーに含めるようクライアント７に指示する更新を転送する。このようにして、クライアント７は、それの新たなルーティングタスク中に、この新たに含められたルートを考慮することができる。サーバ２が提起されたルート２３ａ−２３ｂを拒絶し、クライアント７へのピンペア２３ａ−２３ｂの初期的な割当て時点と拒絶を通知する時点との間に更新が生成された場合、サーバ２は、提起されたルート２３ａ−２３ｂが拒絶されたことを通知し、クライアント７に再試行するよう指示するメッセージにより、これらの仮の更新をクライアント７に送信する。例えば、クライアント５又は６は、クライアント７の前にルーティングタスクを完了し、クライアント７により提起されたルートとコンフリクトするルートを生成したかもしれない。
【００１７】
図８は、図４において開始された自動ルーティングセッション中のさらなる以降の時点を示す。当該時点において、サーバ２は、ピンペア２１ａ−２１ｂ、２２ａ−２２ｂ、２３ａ−２３ｂ、２４ａ−２４ｂ、２５ａ−２５ｂ及び２６ａ−２６ｂのルートを設計３に実装した。クライアント７は、ピンペア２４ａ−２４ｂの間の接続をちょうどルート決定したところであり、クライアント５と６はそれぞれ、ピンペア２７ａ−２７ｂと２８ａ−２８ｂをルート決定しようとしている。サーバ２がピンペア２４ａ−２４ｂをクライアント７に割り当てた時点から、クライアント５は、ピンペア２５ａ−２５ｂを接続するルートを提起する編集リクエストをサーバ２に送信し、サーバ２は当該ルートを受け入れる。同じ期間中、クライアント６は、ピンペア２６ａ−２６ｂを接続するルートを提起する編集リクエストをサーバ２に送信し、サーバ２はまた当該ルートを受け入れる。サーバ２がピンペア２５ａ−２５ｂのルートを受け入れると、サーバ２は更新リクエストを準備し、それを各クライアントの更新キューに配置する。この更新は、新たなピンペア割当て（２７ａ−２７ｂ）と共にクライアント５に送信されたが、何れもルート決定割当てによりビジー状態であったため、クライアント６又は７には送信されなかった。サーバ２は以降においてクライアント６により提起されたピンペア２６ａ−２６ｂのルートを受け入れたとき、サーバ２は、当該ルートに対する他の更新リクエストを準備し、それを各クライアントの更新キューに配置する。その後、クライアント５はピンペア２７ａ−２７ｂをルート決定するのにビジー状態であり、クライアント７は依然としてピンペア２４ａ−２４ｂをルート決定するのにビジー状態であったため、更新はクライアント５又は７には送信されなかった。しかしながら、ピンペア２５ａ−２５ｂと２６ａ−２６ｂのルートの更新は、新たなピンペア割当て（２８ａ−２８ｂ）と共にクライアント６に送信された。従って、クライアント７がピンペア２４ａ−２４ｂのルートを検出した時点では、クライアント７はそれの更新キューに２つの更新を有し、クライアント５はそれの更新キューに１つの更新を有し、クライアント６はそれの更新キューに更新を有しない。同様に、クライアント７は、設計３に実装されたピンペア２５ａ−２５ｂと２６ａ−２６ｂのルートを知ることなく、ピンペア２４ａ−２４ｂをルート決定した。
【００１８】
図９において、クライアント７は、提起された２４ａ−２４ｂの接続ルートに対する更新リクエストを転送した。サーバ２がピンペア２４ａ−２４ｂを接続する提起されたルートに対してＤＲＣを実行すると、サーバ２は、基準違反を検出する。特に、図１０及び１０Ａにより詳細に示されるように、提起された２４ａ−２４ｂのルートは、ピン２５ａ−２５ｂのルートに近すぎる。図１０では、トレースは実線又は破線として示される。トレース間の最小クリアランスは、各トレースの周囲の斜線領域として表される。基板の同一サイドの２つのトレースの斜線領域がオーバーラップする場合（又は２以上のレベルを有する基板についての同一レベル上で）、これらのトレースは近すぎる。図１０に示されるように、図１０Ａの拡大図により詳細に示されるように、提起されたルート２４ａ−２４ｂのクリアランスゾーンの水平部分は、前に実装された２５ａ−２５ｂルートのクリアランスゾーンの水平部分とオーバーラップする。従って、サーバ２は、ピン２４ａ−２４ｂを接続する提起されたルートを拒絶する。このとき、サーバ２は、クライアント７の更新キューの（ピンペア２５ａ−２５ｂ及び２６ａ−２６ｂの）更新と共に、拒絶メッセージをクライアント７に送信する（図１１）。その後、クライアント７は、新たなルートを検出する（図１２）。特に、この新たなルートは、２つの水平セクションと２つの垂直セクションを有するため、追加的なビアを要する。図１２には図示されていないが、クライアント７は、その後第２のルートに対するその後の編集リクエストを転送する。
【００１９】
すべてのピンペアがルート決定されるまで、又は他の停止状態に到達するまで、図４〜９に示されるプロセスは続けられる。例えば、１以上のクライアントは、あるピンペアが現在の設計基準及び以前に実装されたルートに基づきルート決定できないと通知するかもしれない。一部のケースでは、接続のルート決定ができないことは、クライアントが指定された期間内に当該接続をルート決定しないことに基づくものであるかもしれない。ルート決定できない接続の接続数に応じて、設計者は、設計基準及び／又は以前のルートを調整することによりこれらの接続を手作業によりルート決定するかもしれない。決定不能な接続数が十分大きなものであり、あるいはその問題が他のルート及び／又は設計基準を調整することによっては解決できない場合、１以上のコンポーネントを移動させる必要があり、ルート決定プロセスは繰り返される。
【００２０】
本発明の他の実施例では、サーバ２は、ネットリストを介し複数のパスを実行する。第１パスでは、サーバ２は、クライアント５、６及び７がビアを用いることなくピンペア接続をルート決定することを要求する。サーバ２は、第１パス中にネットリストのすべてのピンペアを検索する（又は後述されるように、ビアなしにおそらくルート決定可能なすべてのペアを検索する）。各ピンペアについて、サーバ２は、クライアントの１つから接続ルートを取得するか、又は当該接続がビアなしにルート決定することは不可能であるという表示を取得する。あるピンペアの接続がビアなしにルート決定することができない場合、当該ピンペアのルート決定は、ネットリストの次のパスまで保留される。ネットリストの第２パスでは、サーバ２は、１つのビアしか用いることなくクライアントが接続をルート決定するよう要求する。サーバ２は、再びネットリストのすべてのピンペアを検索し（又は後述されるように、１つのみのビアでおそらくルート決定なすべてのペアを検索し）、クライアントの１つから各ペアのルート決定が不可能であるとの旨又はルートの何れかを取得する。１つのみのペアを用いてはルート決定不可能なピンペア接続は、次のパスまで再び保留される。第３パスでは、サーバ２は、クライアントが２つのビアを用いて接続をルート決定することを可能にする。サーバ２は再び、ネットリストのすべてのピンペアを検索し（又は２つのビアのみでおそらくルート決定可能なすべてのペアを検索し）、各ペアについて１つのクライアントからのルート決定が不可能であるとの旨又はルートの何れかを取得し、次のパスまでルート決定が不可能な接続を保留する。サーバ２は、すべての接続がルート決定されるまで、又は他の停止状態に到達するまで、追加的な個数のビアについてパスを実行し続ける。
【００２１】
各パスの内部に、サーバ２は複数のベース上でピンペアを割り当てる。まず、サーバ２は、より短い接続を要求するピンペアを割り当てる前に、より長い接続を要求するピンペアを割り当てる。言い換えると、サーバ２は、各ペア内のピンの間の距離に基づきピンペアをソートし、距離について降順にピンペアを割り当てる。一部の実施例では、サーバ２はさらに、ピンペアの相対位置に基づきピンペアをソートする。特に、同一の一般的分離距離を有するピンペアの複数のグループについて、サーバ２は、最も少なくしかオーバーラップしないピンペアを割り当てる。このことは、接続対象となるピンを有する３つのレジスタ（Ｒ）、メモリチップ（Ｍ）及び２つの集積回路（ＩＣ）を示す図１３に示される。ピン４１ａ及び４１ｂと、ピン４２ａ及び４２ｂと、ピン４３ａ及び４３ｂを接続する要求は、図１３の回路のネットリストに含まれる。ピン４１ａと４１ｂの間の距離は、ピン４２ａと４２ｂの間の距離に等しく、またピン４３ａと４３ｂの間の距離に等しい。図１３の上記ピンペアのそれぞれについて、各ペアのピンは対角的なノードに配置されるような長方形が示される。４３ａ−４３ｂの長方形は、４１ａ−４１ｂの長方形に若干オーバーラップしている。４２ａ−４２ｂの長方形は、より大きく４１ａ−４１ｂの長方形にオーバーラップしている。４３ａ−４３ｂの長方形は４１ａ−４１ｂの長方形とあまりオーバーラップしていないため、ピン４１ａ−４１ｂと４３ａ−４３ｂについて同時にルート決定される接続がコンフリクトする可能性は低い。他方、ピン４１ａ−４１ｂと４２ａ−４２ｂについて同時にルート決定される接続がコンフリクトする可能性は高い。従って、サーバ２は、ピン４１ａ−４１ｂを１つのクライアントに、４３ａ−４３ｂを他のクライアントにそれぞれ割当て、ピン４１ａ−４１ｂをルート決定しながら、ピン４２ａ−４２ｂを割り当てることを回避する。
【００２２】
実際に、図１３と同一の分離距離を有するピンペアが複数存在することはないかもしれない。しかしながら、分離に基づきピンペアをソートした後、サーバ２は、一部の実施例では、距離によりランク付けされたペアのリストのある範囲内のピンペアの間のオーバーラップの量をチェックするよう構成される。図１４は、少なくとも一部の実施例において、サーバ２が（図１５のネットリストを用いて）どのようにしてこのチェックを実行するかについての一例を示すフローチャートである。図１５のネットリストは、分離距離の降順によりピンペアをリストする。言い換えると、ピンペアｎ−４のピンはペアｎ−３のピンより離れており、ペアｎ−３のピンはさらにペアｎ−２のピンより離れているなどである。図１４及び１５において、サーバは、ピンペアｎとピンペアｎ−２を各自の第１及び第２クライアントに以前に割り当てており、現在はあるピンペアを第３クライアントに割り当てている。サーバは、ピンペアｎ−４、ｎ−３又はｎ−１をまだ割り当てていない。前のピンペア割当てを行うとき、これらのピンペアについて描かれる長方形は、他のピンペアの長方形よりすでに割り当てられたピンペアの長方形とより大きくオーバーラップしている。ブロック１０１（図１４）から始まり、サーバは、現在割り当てられているピンペア長方形といくつかの候補ピンペアの間のオーバーラップを評価する。特に、サーバは、ピンペアｎ−４、ｎ−３及びｎ−１のそれぞれの長方形が、ピンペアｎの長方形とピンペアｎ−２の長方形とオーバーラップしている量を計算する。その後、サーバは、サーバがＸ個の候補ピンペアについて計算する実行完了するまで、ピンペアｎ＋１、ｎ＋２、ｎ＋３などについて同じ計算を実行する。Ｘの値は、予め設定された値とすることができ、又は自動ルーティングセッション中に他の条件に基づき可変とすることも可能である。候補ピンペアのオーバーラップを計算した後、ブロック１０３において、サーバは、何れの候補ピンペアが現在割り当てられているピンペアと最小のオーバーラップを有しているか決定する。具体的には、サーバは、各候補ピンペアがピンペアｎとオーバーラップしている量を、同じ候補ピンペアがピンペアｎ−２とオーバーラップしている量に追加する。ブロック１０５において、最小の合計されたオーバーラップを有するピンペアが、第３クライアントに割り当てられる。
【００２３】
図１４のアルゴリズムに対する多数の変形が、他の実施例において利用されている。例えば、現在割り当てられているピンペアの最小合計オーバーラップを有するピンペアを単に割り当てる代わりに、サーバはさらに、あるピンペアが現在割り当てられているピンペノ何れとも所定量以上はオーバーラップしていないことを要求することができる。他の実施例では、以前に無視されたピンペアは（ｎ−４、ｎ−３及びｎ−１など）優先され、及び／又は所定の回数以上無視されると自動的に選択される。本発明の範囲内において、多数の他の変形が可能である。
【００２４】
一部の実施例では、サーバ２はまた、ある個数のビアを用いてルート決定を求めるネットリストのパスを行う前に、何れのピンペアが当該ビア制限を満たすことができないか判断する。（図１３の回路コンポーネントを生成する）図１６に示されるように、一部のピンペア（ピン４４ａ−４４ｂ、４８ａ−４８ｂなど）は、ターン（ｔｕｒｎ）を有しないルートにより潜在的に接続可能である。これらのピンがターンを有しないルートと接続することが可能である場合、ビアは必要ではないかもしれない。従って、これらのピンペアは、第１パス中のルート決定のため割当て可能である。他のピンペア（ピン４５ａ−４５ｂなど）は、少なくとも１つのターンと、従って少なくとも１つのビアを有するルートを要求するであろう。これらのピンペアはビアを用いることなくルート決定するよう制限されるクライアントによってはルート決定することはできないため、第２パスまでこれらのピンペアは保留される。一部のピンペア（ピン４６ａ−４６ｂ、４７ａ−４７ｂなど）は、少なくとも２つのターンを有し、従って少なくとも２つのビアを有するルートを要求し、このため、第３パスまで自動的に保留されるであろう。より複雑な設計では、さらに大きな最小ターン数を有するルートを有するピンペアが存在するかもしれない。
【００２５】
他の実施例では、ピンペア間の接続は、ＰＣＢの１つのレイヤ上で方向を変更することが許されるかもしれない。言い換えると、トレースがピン４９ａから延びることにより示されるように、いくつかのトレースは、他のレベルのトレースと接続することなく、従って、ビアを利用することなくターンすることが許されるかもしれない。当該実施例では、このようなトレースは、予め特定することができ（例えば、ある領域にあるコンポーネントについて、あるピンのこのようなトレースを可能にするなど）、適当なパスに含めることができる。
【００２６】
図１７は、本発明の少なくとも一部の実施例により、サーバからの分散自動ルーティングセッションを制御する方法のフローチャートである。ブロック２０１において、サーバは、プリント基板上に配置されるべき回路の電気設計を受信する。この電気設計は、接続されるべきすべてのピンペアを示すネットリストと、ＰＣＢ上のコンポーネントの配置を含む。ブロック２０３において、サーバはピンペアをソートする。一部の実施例では、上述されるように、サーバは接続対象のピンの間の距離に基づきピンペアをソートする。サーバはまた、１つのビア、又は２つのビアなどを用いることなく接続可能なピンなど、他のベースについてソートするかもしれない。ブロック２０５において、サーバは、パスカウンター（ｐ）を「０」に設定する。ブロック２０７において、サーバはパス０を開始する。当該パス中、サーバは、ビアを用いることなくピン間の接続をクライアントにルート決定するよう要求するであろう。ブロック２０９において、サーバは、クライアントへの割当てのためピンペアを選択する。初期的には、サーバは、ネットリストの最初のピンペアを単に選ぶことによりピンペアを選択する。最初のピンペアが割り当てられた後、サーバは前に割り当てられたピンペアとのオーバーラップ及び距離に基づくと共に（図１４及び１５について説明されるように）、あるピンペアが現在のビア制限を用いて接続可能であるかに基づき（例えば、パス０にはビアはなく、パス１には１つのビアなど）、以降のピンペアを選択する。ブロック２１１において、サーバは、選択されたピンペアをクライアントに割当て、割り当てられたピンペアを当該クライアントの更新キューの更新と共に転送する（初期的には更新は存在しない）。ブロック２１３において、サーバは、ピンペアに割り当てられていない他の何れかのクライアントが存在しないか判断する。存在する場合、サーバはブロック２０９に戻って、次のクライアントのピンペアを選択肢、ブロック２１１において当該割当てを転送する。ブロック２１３において、ピンペアが割り当てられる必要があるクライアントがもはや存在しない場合（「ｎｏ」ブランチ）、サーバは、ブロック２１５に移行する。ブロック２１５において、サーバは、クライアントが当該クライアントの割り当てられたピンペアの提起されたルートを含む編集リクエストを提出するか（編集）、又は割り当てられたピンペアが接続不可（エラー）であることを示すまで待機する。
【００２７】
クライアントは、それ自体、割り当てられたピンペアが現在のビア制限を用いてルート決定することができないことを示すことによって、エラーを提出するようにしてもよい。クライアントはまた、所定時間以上接続をルート決定しようとした場合、エラーを提出するようにしてもよい。サーバはまた、クライアントにタイムアウトエラーを生成するようにしてもよい。エラーが発生すると、サーバはブロック２１７に移行する。ブロック２７１において、サーバは、現在のビア制限のためルート決定することができないか判断する。そうである場合（ピンペアが現在ルート決定できないため、「ｎｏ」ブランチ）、又はピンペアが現在のパスにおいて最大数のエラーを前に生成してしまっている場合（拒絶が最大値未満でない）、サーバはブロック２１９に移行する。ブロック２１９において、ピンペアは以降のパスに保留される。その後、サーバはブロック２２７に移行し、現在のパスに残りのピンペアがあるか判断する。そうである場合、サーバは保留されたピンペアをルート決定できないクライアントの他のピンペアの選択のため、ブロック２０９に移行する。そうでない場合、サーバは後述されるブロック２０３に移行する。
【００２８】
ブロック２１５で通知されるエラーが、ビア制限により生じたものではなく、ピンペアが現在のビアにおいて最大回数拒絶されていない場合、サーバは、ブロック２１７において「ｙｅｓ」ブランチを選択する。例えば、一部のピンペアがルート決定された後、あるクライアントは前にルート決定された接続を知ることなく接続をルート決定するかもしれない。この場合、現在のビア制限を用いて接続をルート決定することが依然として可能であるかもしれない。従って、ブロック２２１において、サーバは、当該クライアントの更新キューの更新と、現在のピンペアのルート決定を再試行する指示（すなわち、ピンペアの再割当て）を送信する。ブロック２２１から、サーバはブロック２１５に戻り、他の編集又はエラー報告を待機する。
【００２９】
サーバがブロック２１５において編集リクエストを受信した場合、サーバは、ブロック２２３に戻り、提起されたルートについて設計基準チェック（ＤＲＣ）を実行する。提起されたルートがＤＲＣを満たしていない場合（「不成功（ｆａｉｌ）」ブランチ）、サーバはブロック２２５に移行する。ブロック２２５において、サーバは、ピンペアが現在パス中に最大回数未満しかＤＲＣに失敗していないか判断する。そうである場合（「ｙｅｓ」ブランチ）、サーバは、ブロック２２１に移行し、更新がクライアントに送信され、クライアントは再試行するよう指示される。現在パス中のピンペアのＤＲＣの失敗回数が最大数未満でない場合（「ｎｏ」ブランチ）、サーバはブロック２１９に移行し、ピンペアが以降のパスに保留され、その後ブロック２２７に移行する。
【００３０】
提起されたルートがブロック２２３においてＤＲＣをパスすると（「成功（ｐａｓｓ）ブランチ」ブランチ）、サーバは、ブロック２２９においてマスターＰＣＢ設計に当該ルートを実装する。サーバはまた、新たに実装されたルートを反映する更新を生成し、各クライアントのキューに更新を配置する。その後、サーバはブロック２３１に移行し、現在のパスに残りのピンペアがないか判断する。そうである場合、サーバはブロック２０９に移行し、実装されたルートを提供するクライアントのため他のピンペアを選択する。そうでない場合、サーバはブロック２３３に移行する。ブロック２３３において、サーバは、ネットリストの他のパスを実行するか判断する。例えば、設計基準は、何れの状況においても指定された個数のビアより多く有するルートが存在しないことを要求するかもしれない。サーバが当該指定された個数プラスビアのないルートには１つのパスに等しいパス数を実行した後、サーバはもはやパスを生成しない。このような場合、サーバはブロック２３３の「ｎｏ」ブランチからブロック２３７に移行する。ブロック２３７において、サーバは、何れのピンペア（存在すれば）がルート決定されていないか示すレポートを生成し、その後、ルーティングセッションを終了する。さらなるパスがネットリストにおいて生成される場合（ブロック２３３の「ｙｅｓ」ブランチ）、サーバは、ブロック２３５においてパスカウンターｐをインクリメントし、その後、ブロック２０７に戻り、新たなパスを開始する。次のパス中、クライアントは、ｐ個のビアを用いてピンペアをルート決定するよう指示される。
【００３１】
一般には、ＤＲＣを実行し、サーバにより実行される他のタスクを実行するのに必要な処理時間は、１つのピンペアをルート決定するのにクライアントにより必要とされる時間よりはるかに少ない。従って、サーバはしばしば、クライアントより大きな処理パワーを必要としなくなる。複数の編集リクエストが素早く連続的にクライアントから到達する場合（図１７のブロック２１５）、当該編集リクエストはキュー可能であり、ＦＩＦＯベースによりサーバにより処理可能となる。
【００３２】
図１８は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションによりクライアントを実行する方法のフローチャートである。ブロック３０１から始まり、クライアントはサーバから指示を受信する。これらの指示は、新たなピン割当てかもしれないし、あるいはピンペアのルート決定を再試行する指示であるかもしれない（すなわち、ピンペアの再割当て）。クライアントはまた、サーバにより可能な接続に介される制限を受信し（ビア制限など）、またクライアントにより維持されるＰＣＢ設計のコピーの１以上の更新を受信するようにしてもよい。ブロック３０３において、ブロック３０１において受信した更新が（存在する場合）、ＰＣＢ設計のクライアントコピーに適用される。ブロック３０５において、クライアントは、割り当てられたピンペアを接続するルートを検出するため、１以上のルーティングアルゴリズムの利用を開始する。これらのルーティングアルゴリズムに基づき、クライアントは、ルートを検出するか、あるいはピン間の接続が検出不可であると判断する（現在のビア制限のためなど）。一部の実施例では、クライアントはまた、所定時間後に接続をルート決定することを停止し、必要となる時間に基づきルート決定することができないと通知するよう構成されてもよい。ブロック３０５から、クライアントはブロック３０７に移行する。ブロック３０５においてクライアントが割り当てられたピンペアのルートを検出した場合、クライアントは、「ｙｅｓ」ブランチによりブロック３０９に移行する。ブロック３０９において、クライアントは、検出されたルートを含む編集リクエストをサーバに転送する。ブロック３１１において、クライアントは、ブロック３０５の前であって、ブロック３０３の後にＰＣＢ設計のそれのコピーを当該コピーの状態に戻す。ブロック３１１から、クライアントは、ブロック３１５に戻り、サーバからのさらなる指示を待機する。クライアントがブロック３０５において割り当てられたピンペアのルートを検出することができなかった（又はタイムアウトとなった）場合、クライアントは、「ｎｏ」ブランチによりブロック３０７からブロック３１３に移行する。ブロック３１３において、クライアントは、ピンペア接続をルート決定することができないことを通知する。その後、クライアントはさらなる指示を待機するためブロック３１５に移行する。
【００３３】
一部の実施例では、図１９に示されるように、サーバは、ルート決定のため同一のピンペア（ｙａ−ｙｂ）を複数のクライアントに割り当てるようにしてもよい。一部のケースでは、ルーティングセッションは、ほとんど完了し、ルート決定されていないピンペアよりクライアントの方が多くなるかもしれない。他のケースでは、比較のため他のルートを展開することが望ましいかもしれない。ピンペア接続をルート決定するのに要する処理時間は、より多くのピン接続が追加されるに従って、大きく増加しうる。より多くのクライアントが同じルーティング問題を解こうとする場合、解は潜在的により速く検出されるかもしれない。これについて、図１９に示されるように、クライアントには、同じピンペアをルート決定するための異なるパラメータが与えられているかもしれない。一例として、１つのクライアントは必要に応じて多数のビアを利用することが許され、他のクライアントは１つのＰＣＢレイヤを占有する多方向トレースを利用することが許されているかもしれない（すなわち、ビアを利用することなく方向を変更する）。他の例として、１つのクライアントは、ルートの一部を削除し、再ルート決定することが許され、他のクライアントは、他のルート部分を削除し、再ルート決定することが許されているかもしれない。また、クライアントには異なるコンポーネント配置、異なるルーティングスキーム、異なる接続スケジュール又は他の異なるパラメータを有するルーティング割当てが与えられてもよい。さらなる他の実施例では、ピンペアをルート決定するクライアントには、労力の重複を回避するため、同じピンペアを他のクライアントがルート決定することによりしさされるルートがアドバイスされる。同一のピンペアをルート決定するクライアントの状況は、例えば、何れのルーティングパラメータがより迅速な進捗を可能にするか判断するためなどに監視されてもよい。
【００３４】
本発明を実行する複数の例が説明されたが、当業者は、添付された請求項に与えられる本発明の趣旨及び範囲内に属する上述の例の変形及び並び替えが多数存在するということは理解するであろう。上述のアルゴリズム、システム構成及び他の特徴は、単なる例にすぎない。多数の他のアルゴリズム、構成及び特徴と同様に、上述のアルゴリズム、システム及び特徴の変更は本発明の範囲内に属する。例えば、上述の実施例は、１つのピンペアを各クライアントコンピュータに割り当てるが、本発明はこのような実施例に限定されるものではない。他の実施例では、サーバは、あるクライアントに対する自動ルーティング割当てに２つの（又はそれ以上の）ピンペアを含むかもしれない。その後、クライアントは、これらのピンペアの一部又はすべてについての提起されたルートを返す。従って、以下の請求項の単数形の使用は、排他的に解釈されるべきではない（例えば、「ある」とは、「唯一」を意味するものではない）。他の例として、２つのピンの間のルートを検出するクライアントコンピュータは、編集リクエストをサーバに転送するとすぐに、ＰＣＢ設計のそれのコピーを以前の状態に戻す必要はない。代わりに、クライアントは、それの検出したルートが残ることを許容することが可能であり、サーバが検出されたルートを拒絶した場合、クライアントは、拒絶を受信すると、検出されたルートを削除することができる。さらに、ここで使用される（請求項を含む）「プロセッサ」という表現は、単一のプロセッサに限定されず、相互に関連する処理機能を共に実行するよう協調する複数のプロセッサを含むものであってもよい。
【図面の簡単な説明】
【００３５】
【図１】図１は、本発明の少なくとも一部の特徴が実現される計算システムのブロック図である。
【図２】図２は、ＰＣＢ設計の一部のブロック図である。
【図３】図３は、図２のＰＣＢ設計のネットリストである。
【図４】図４は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションの始めを概略図により示す。
【図５】図５は、図４の自動ルーティングセッションの以降の時点を示す。
【図６】図６は、図４の自動ルーティングセッションの以降の時点を示す。
【図７】図７は、図４の自動ルーティングセッションの以降の時点を示す。
【図８】図８は、図４の自動ルーティングセッションの以降の時点を示す。
【図９】図９は、図４の自動ルーティングセッションの以降の時点を示す。
【図１０】図１０は、提起されたピン接続ルートの設計基準違反を示す。
【図１０Ａ】図１０Ａは、提起されたピン接続ルートの設計基準違反を示す。
【図１１】図１１は、図４の自動ルーティングセッションのさらなる以降の時点を示す。
【図１２】図１２は、図４の自動ルーティングセッションのさらなる以降の時点を示す。
【図１３】図１３は、相対位置によるピンペアの分類を示す。
【図１４】図１４は、少なくとも一部の実施例によるピンペア間のオーバーラップ量をチェックするアルゴリズムを示すフローチャートである。
【図１５】図１５は、分離距離の降順によるピンペアを有するネットリストを示す。
【図１６】図１６は、最小のビアによるピンペアの分類を示す。
【図１７】図１７は、本発明の少なくとも一部の実施例によるサーバからの分散自動ルーティングセッションを制御する方法のフローチャートである。
【図１８】図１８は、本発明の少なくとも一部の実施例による分散自動ルーティングセッションにおいてクライアントを実行する方法のフローチャートである。
【図１９】図１９は、本発明の少なくとも一部の実施例による複数のクライアントへの同一のピンペアの割当てを示す。
【特許請求の範囲】
【請求項１】
プリント基板（ＰＣＢ）の導電性パスをルート決定する方法であって、
（ａ）２つのコンポーネントピンの間の導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれにコンポーネントピンペアを割り当てるステップと、
（ｂ）各クライアントから、該クライアントに割り当てられたピンペアを接続する導電性パスの提起されたルートを受け付けるステップと、
（ｃ）前記提起されたルートをマスターＰＣＢ設計に実装するステップと、
（ｄ）前記ステップ（ａ）〜（ｃ）を繰り返すステップと、
から構成されることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
（ｅ）前記複数のクライアントに更新メッセージを転送するステップを有し、
前記更新メッセージは、提起されたルートのＰＣＢ設計のマスターコピーへの実装を示し、前記複数のクライアントが該クライアントにより維持されるＰＣＢ設計のローカルコピーに前記実装されたルートを含めることを認めるものであることを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記ステップ（ｅ）は、クライアントが該クライアントによって前に提起された実装されたルートを該クライアントのローカルＰＣＢ設計コピーに含めることを認める更新メッセージを前記クライアントに転送するステップを有することを特徴とする方法。
【請求項４】
請求項１記載の方法であって、さらに、
（ｅ）提起されたルートを前記マスターＰＣＢ設計に実装することにより、前記ルートの実装を示す更新を生成するステップと、
（ｆ）クライアントが割り当てられたピンペアをルート決定していないとき、前記クライアントに前記更新を転送するステップと、
を有することを特徴とする方法。
【請求項５】
請求項４記載の方法であって、
前記ステップ（ｅ）は、複数の提起されたルートのそれぞれを前記ＰＣＢマスター設計コピーに実装することにより、別の更新メッセージを生成し、
前記ステップ（ｅ）はさらに、前記複数のクライアントの更新キューに各更新を配置し、
前記ステップ（ｆ）は、前記クライアントが割り当てられたピンペアを現在ルート決定していないとき、前記更新キューのコンテンツを転送する、
ことを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ｄ）は、前記リストを介し複数のパスにおいて前記ステップ（ａ）〜（ｃ）を繰り返す、
ことを特徴とする方法。
【請求項７】
請求項６記載の方法であって、
前記ステップ（ａ）は、前記リストを介した１つのパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する制限を課し、
前記ステップ（ａ）はさらに、前記リストを介した以降のパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する異なる制限を課す、
ことを特徴とする方法。
【請求項８】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項９】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、
前記ステップ（ａ）はさらに、異なるピンペアのピン位置から構成されるポリゴン間のオーバーラップ量に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１１】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１２】
請求項１記載の方法であって、
前記ステップ（ａ）は、コンポーネントピンペアを前記複数のクライアントの第１クライアントに、前記同一のコンポーネントピンペアを前記複数のクライアントの第２クライアントに、前記第１及び第２クライアントが、割り当てられるピンペアのピンの間の導電性パスを同時にルート決定するよう割り当てることを特徴とする方法。
【請求項１３】
請求項１２記載の方法であって、
前記ステップ（ａ）は、第１ルーティングパラメータにより前記ピンペアを前記第１クライアントに割当て、第２ルーティングパラメータにより前記ピンペアを前記第２クライアントに割当てることを特徴とする方法。
【請求項１４】
プリント基板（ＰＣＢ）の導電性パスをルート決定する方法であって、
（ａ）接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを受け付けるステップと、
（ｂ）前記特定されたピンの間の導電性パスのルートを自動検出するステップと、
（ｃ）前記検出されたルートを提起する編集リクエストを送信するステップと、
（ｄ）前記提起されたルートがＰＣＢ設計に実装されている表示を受け付けるステップと、
（ｅ）前記表示の受信後、前記ＰＣＢ設計のローカルコピーを前記検出されたルートを含むよう更新するステップと、
から構成されることを特徴とする方法。
【請求項１５】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記ステップ（ｉ）において提起されたルートが前記ＰＣＢ設計に実装される表示を受け付けるステップと、
（ｊ）前記ステップ（ｉ）の表示の受信後、前記ＰＣＢ設計のローカルコピーを前記ステップ（ｇ）において検出されたルートを含むよう更新するステップと、
を有することを特徴とする方法。
【請求項１６】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の他のルートを検出する指示を受け付けるステップと、
（ｊ）前記第２ピンペア割当てのピンの間の第２ルートを自動検出するステップと、
（ｋ）前記第２ルートを提起する編集リクエストを送信するステップと、
を有することを特徴とする方法。
【請求項１７】
請求項１４記載の方法であって、
前記ステップ（ｄ）は、前記ステップ（ａ）〜（ｅ）を実行するコンピュータ以外の１以上のコンピュータにより検出される他のルートが前記ＰＣＢ設計に実装されるという１以上の表示を受け付け、
前記ステップ（ｅ）は、前記ＰＣＢ設計のローカルコピーを前記他のルートを含むよう更新する、
ことを特徴とする方法。
【請求項１８】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間にルート決定された導電性パスに許されるビアの個数に対する制限の表示を受け付けるステップと、
（ｈ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の接続をルート決定することが不可能であるという表示を送信するステップと、
を有することを特徴とする方法。
【請求項１９】
命令シーケンスを表すデータを格納するマシーン可読媒体であって、
前記命令シーケンスは、プロセッサにより実行時に、
（ａ）２つのコンポーネントピンの間の導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれにコンポーネントピンペアを割り当てるステップと、
（ｂ）各クライアントから、該クライアントに割り当てられたピンペアを接続する導電性パスの提起されたルートを受け付けるステップと、
（ｃ）前記提起されたルートをマスターＰＣＢ設計に実装するステップと、
（ｄ）前記ステップ（ａ）〜（ｃ）を繰り返すステップと、
を前記プロセッサに実行させることを特徴とする媒体。
【請求項２０】
請求項１９記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｅ）前記複数のクライアントに更新メッセージを転送するステップを有し、
前記更新メッセージは、提起されたルートのＰＣＢ設計のマスターコピーへの実装を示し、前記複数のクライアントが該クライアントにより維持されるＰＣＢ設計のローカルコピーに前記実装されたルートを含めることを認めるものであることを特徴とする媒体。
【請求項２１】
請求項２０記載のマシーン可読媒体であって、
前記ステップ（ｅ）は、クライアントが該クライアントによって前に提起された実装されたルートを該クライアントのローカルＰＣＢ設計コピーに含めることを認める更新メッセージを前記クライアントに転送するステップを有することを特徴とする媒体。
【請求項２２】
請求項１９記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｅ）提起されたルートを前記マスターＰＣＢ設計に実装することにより、前記ルートの実装を示す更新を生成するステップと、
（ｆ）クライアントが割り当てられたピンペアをルート決定していないとき、前記クライアントに前記更新を転送するステップと、
を有することを特徴とする媒体。
【請求項２３】
請求項２２記載のマシーン可読媒体であって、
前記ステップ（ｅ）は、複数の提起されたルートのそれぞれを前記ＰＣＢマスター設計コピーに実装することにより、別の更新メッセージを生成し、
前記ステップ（ｅ）はさらに、前記複数のクライアントの更新キューに各更新を配置し、
前記ステップ（ｆ）は、前記クライアントが割り当てられたピンペアを現在ルート決定していないとき、前記更新キューのコンテンツを転送する、
ことを特徴とする媒体。
【請求項２４】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ｄ）は、前記リストを介し複数のパスにおいて前記ステップ（ａ）〜（ｃ）を繰り返す、
ことを特徴とする媒体。
【請求項２５】
請求項２４記載のマシーン可読媒体であって、
前記ステップ（ａ）は、前記リストを介した１つのパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する制限を課し、
前記ステップ（ａ）はさらに、前記リストを介した以降のパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する異なる制限を課す、
ことを特徴とする媒体。
【請求項２６】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２７】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２８】
請求項２７記載のマシーン可読媒体であって、
前記ステップ（ａ）はさらに、異なるピンペアのピン位置から構成されるポリゴン間のオーバーラップ量に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２９】
請求項２７記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項３０】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、コンポーネントピンペアを前記複数のクライアントの第１クライアントに、前記同一のコンポーネントピンペアを前記複数のクライアントの第２クライアントに、前記第１及び第２クライアントが、割り当てられるピンペアのピンの間の導電性パスを同時にルート決定するよう割り当てることを特徴とする媒体。
【請求項３１】
請求項３０記載のマシーン可読媒体であって、
前記ステップ（ａ）は、第１ルーティングパラメータにより前記ピンペアを前記第１クライアントに割当て、第２ルーティングパラメータにより前記ピンペアを前記第２クライアントに割当てることを特徴とする媒体。
【請求項３２】
命令シーケンスを表すデータを格納するマシーン可読媒体であって、
前記命令シーケンスは、プロセッサにより実行時に、
（ａ）接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを受け付けるステップと、
（ｂ）前記特定されたピンの間の導電性パスのルートを自動検出するステップと、
（ｃ）前記検出されたルートを提起する編集リクエストを送信するステップと、
（ｄ）前記提起されたルートがＰＣＢ設計に実装されている表示を受け付けるステップと、
（ｅ）前記表示の受信後、前記ＰＣＢ設計のローカルコピーを前記検出されたルートを含むよう更新するステップと、
を前記プロセッサに実行させることを特徴とする媒体。
【請求項３３】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記ステップ（ｉ）において提起されたルートが前記ＰＣＢ設計に実装される表示を受け付けるステップと、
（ｊ）前記ステップ（ｉ）の表示の受信後、前記ＰＣＢ設計のローカルコピーを前記ステップ（ｇ）において検出されたルートを含むよう更新するステップと、
を有することを特徴とする媒体。
【請求項３４】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の他のルートを検出する指示を受け付けるステップと、
（ｊ）前記第２ピンペア割当てのピンの間の第２ルートを自動検出するステップと、
（ｋ）前記第２ルートを提起する編集リクエストを送信するステップと、
を有することを特徴とする媒体。
【請求項３５】
請求項３２記載のマシーン可読媒体であって、
前記ステップ（ｄ）は、前記ステップ（ａ）〜（ｅ）を実行するコンピュータ以外の１以上のコンピュータにより検出される他のルートが前記ＰＣＢ設計に実装されるという１以上の表示を受け付け、
前記ステップ（ｅ）は、前記ＰＣＢ設計のローカルコピーを前記他のルートを含むよう更新する、
ことを特徴とする媒体。
【請求項３６】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間にルート決定された導電性パスに許されるビアの個数に対する制限の表示を受け付けるステップと、
（ｈ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の接続をルート決定することが不可能であるという表示を送信するステップと、
を有することを特徴とする媒体。
【請求項１】
プリント基板（ＰＣＢ）の導電性パスをルート決定する方法であって、
（ａ）２つのコンポーネントピンの間の導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれにコンポーネントピンペアを割り当てるステップと、
（ｂ）各クライアントから、該クライアントに割り当てられたピンペアを接続する導電性パスの提起されたルートを受け付けるステップと、
（ｃ）前記提起されたルートをマスターＰＣＢ設計に実装するステップと、
（ｄ）前記ステップ（ａ）〜（ｃ）を繰り返すステップと、
から構成されることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、さらに、
（ｅ）前記複数のクライアントに更新メッセージを転送するステップを有し、
前記更新メッセージは、提起されたルートのＰＣＢ設計のマスターコピーへの実装を示し、前記複数のクライアントが該クライアントにより維持されるＰＣＢ設計のローカルコピーに前記実装されたルートを含めることを認めるものであることを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記ステップ（ｅ）は、クライアントが該クライアントによって前に提起された実装されたルートを該クライアントのローカルＰＣＢ設計コピーに含めることを認める更新メッセージを前記クライアントに転送するステップを有することを特徴とする方法。
【請求項４】
請求項１記載の方法であって、さらに、
（ｅ）提起されたルートを前記マスターＰＣＢ設計に実装することにより、前記ルートの実装を示す更新を生成するステップと、
（ｆ）クライアントが割り当てられたピンペアをルート決定していないとき、前記クライアントに前記更新を転送するステップと、
を有することを特徴とする方法。
【請求項５】
請求項４記載の方法であって、
前記ステップ（ｅ）は、複数の提起されたルートのそれぞれを前記ＰＣＢマスター設計コピーに実装することにより、別の更新メッセージを生成し、
前記ステップ（ｅ）はさらに、前記複数のクライアントの更新キューに各更新を配置し、
前記ステップ（ｆ）は、前記クライアントが割り当てられたピンペアを現在ルート決定していないとき、前記更新キューのコンテンツを転送する、
ことを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ｄ）は、前記リストを介し複数のパスにおいて前記ステップ（ａ）〜（ｃ）を繰り返す、
ことを特徴とする方法。
【請求項７】
請求項６記載の方法であって、
前記ステップ（ａ）は、前記リストを介した１つのパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する制限を課し、
前記ステップ（ａ）はさらに、前記リストを介した以降のパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する異なる制限を課す、
ことを特徴とする方法。
【請求項８】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項９】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、
前記ステップ（ａ）はさらに、異なるピンペアのピン位置から構成されるポリゴン間のオーバーラップ量に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１１】
請求項１記載の方法であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする方法。
【請求項１２】
請求項１記載の方法であって、
前記ステップ（ａ）は、コンポーネントピンペアを前記複数のクライアントの第１クライアントに、前記同一のコンポーネントピンペアを前記複数のクライアントの第２クライアントに、前記第１及び第２クライアントが、割り当てられるピンペアのピンの間の導電性パスを同時にルート決定するよう割り当てることを特徴とする方法。
【請求項１３】
請求項１２記載の方法であって、
前記ステップ（ａ）は、第１ルーティングパラメータにより前記ピンペアを前記第１クライアントに割当て、第２ルーティングパラメータにより前記ピンペアを前記第２クライアントに割当てることを特徴とする方法。
【請求項１４】
プリント基板（ＰＣＢ）の導電性パスをルート決定する方法であって、
（ａ）接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを受け付けるステップと、
（ｂ）前記特定されたピンの間の導電性パスのルートを自動検出するステップと、
（ｃ）前記検出されたルートを提起する編集リクエストを送信するステップと、
（ｄ）前記提起されたルートがＰＣＢ設計に実装されている表示を受け付けるステップと、
（ｅ）前記表示の受信後、前記ＰＣＢ設計のローカルコピーを前記検出されたルートを含むよう更新するステップと、
から構成されることを特徴とする方法。
【請求項１５】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記ステップ（ｉ）において提起されたルートが前記ＰＣＢ設計に実装される表示を受け付けるステップと、
（ｊ）前記ステップ（ｉ）の表示の受信後、前記ＰＣＢ設計のローカルコピーを前記ステップ（ｇ）において検出されたルートを含むよう更新するステップと、
を有することを特徴とする方法。
【請求項１６】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の他のルートを検出する指示を受け付けるステップと、
（ｊ）前記第２ピンペア割当てのピンの間の第２ルートを自動検出するステップと、
（ｋ）前記第２ルートを提起する編集リクエストを送信するステップと、
を有することを特徴とする方法。
【請求項１７】
請求項１４記載の方法であって、
前記ステップ（ｄ）は、前記ステップ（ａ）〜（ｅ）を実行するコンピュータ以外の１以上のコンピュータにより検出される他のルートが前記ＰＣＢ設計に実装されるという１以上の表示を受け付け、
前記ステップ（ｅ）は、前記ＰＣＢ設計のローカルコピーを前記他のルートを含むよう更新する、
ことを特徴とする方法。
【請求項１８】
請求項１４記載の方法であって、さらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間にルート決定された導電性パスに許されるビアの個数に対する制限の表示を受け付けるステップと、
（ｈ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の接続をルート決定することが不可能であるという表示を送信するステップと、
を有することを特徴とする方法。
【請求項１９】
命令シーケンスを表すデータを格納するマシーン可読媒体であって、
前記命令シーケンスは、プロセッサにより実行時に、
（ａ）２つのコンポーネントピンの間の導電性パスを自動的にルート決定するよう構成される複数のクライアントコンピュータのそれぞれにコンポーネントピンペアを割り当てるステップと、
（ｂ）各クライアントから、該クライアントに割り当てられたピンペアを接続する導電性パスの提起されたルートを受け付けるステップと、
（ｃ）前記提起されたルートをマスターＰＣＢ設計に実装するステップと、
（ｄ）前記ステップ（ａ）〜（ｃ）を繰り返すステップと、
を前記プロセッサに実行させることを特徴とする媒体。
【請求項２０】
請求項１９記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｅ）前記複数のクライアントに更新メッセージを転送するステップを有し、
前記更新メッセージは、提起されたルートのＰＣＢ設計のマスターコピーへの実装を示し、前記複数のクライアントが該クライアントにより維持されるＰＣＢ設計のローカルコピーに前記実装されたルートを含めることを認めるものであることを特徴とする媒体。
【請求項２１】
請求項２０記載のマシーン可読媒体であって、
前記ステップ（ｅ）は、クライアントが該クライアントによって前に提起された実装されたルートを該クライアントのローカルＰＣＢ設計コピーに含めることを認める更新メッセージを前記クライアントに転送するステップを有することを特徴とする媒体。
【請求項２２】
請求項１９記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｅ）提起されたルートを前記マスターＰＣＢ設計に実装することにより、前記ルートの実装を示す更新を生成するステップと、
（ｆ）クライアントが割り当てられたピンペアをルート決定していないとき、前記クライアントに前記更新を転送するステップと、
を有することを特徴とする媒体。
【請求項２３】
請求項２２記載のマシーン可読媒体であって、
前記ステップ（ｅ）は、複数の提起されたルートのそれぞれを前記ＰＣＢマスター設計コピーに実装することにより、別の更新メッセージを生成し、
前記ステップ（ｅ）はさらに、前記複数のクライアントの更新キューに各更新を配置し、
前記ステップ（ｆ）は、前記クライアントが割り当てられたピンペアを現在ルート決定していないとき、前記更新キューのコンテンツを転送する、
ことを特徴とする媒体。
【請求項２４】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ｄ）は、前記リストを介し複数のパスにおいて前記ステップ（ａ）〜（ｃ）を繰り返す、
ことを特徴とする媒体。
【請求項２５】
請求項２４記載のマシーン可読媒体であって、
前記ステップ（ａ）は、前記リストを介した１つのパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する制限を課し、
前記ステップ（ａ）はさらに、前記リストを介した以降のパス中に、クライアントに割り当てられたピンペアをルート決定するよう指示し、提起されたルートに許されているビアの個数に対する異なる制限を課す、
ことを特徴とする媒体。
【請求項２６】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２７】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２８】
請求項２７記載のマシーン可読媒体であって、
前記ステップ（ａ）はさらに、異なるピンペアのピン位置から構成されるポリゴン間のオーバーラップ量に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項２９】
請求項２７記載のマシーン可読媒体であって、
前記ステップ（ａ）は、電子回路のコンポーネントピンペアのリストからコンポーネントピンペアを割当て、
前記ステップ（ａ）はさらに、前記ピンペア内のピンを分離する距離に少なくとも部分的に基づき、前記リストからピンペアを割り当て、
前記ステップ（ａ）はさらに、異なるピンペアの相対位置に少なくとも部分的に基づき、前記リストからピンペアを割り当てる、
ことを特徴とする媒体。
【請求項３０】
請求項１９記載のマシーン可読媒体であって、
前記ステップ（ａ）は、コンポーネントピンペアを前記複数のクライアントの第１クライアントに、前記同一のコンポーネントピンペアを前記複数のクライアントの第２クライアントに、前記第１及び第２クライアントが、割り当てられるピンペアのピンの間の導電性パスを同時にルート決定するよう割り当てることを特徴とする媒体。
【請求項３１】
請求項３０記載のマシーン可読媒体であって、
前記ステップ（ａ）は、第１ルーティングパラメータにより前記ピンペアを前記第１クライアントに割当て、第２ルーティングパラメータにより前記ピンペアを前記第２クライアントに割当てることを特徴とする媒体。
【請求項３２】
命令シーケンスを表すデータを格納するマシーン可読媒体であって、
前記命令シーケンスは、プロセッサにより実行時に、
（ａ）接続する導電性パスがルート決定される電子回路の１以上のコンポーネントのピンを特定するピンペア割当てを受け付けるステップと、
（ｂ）前記特定されたピンの間の導電性パスのルートを自動検出するステップと、
（ｃ）前記検出されたルートを提起する編集リクエストを送信するステップと、
（ｄ）前記提起されたルートがＰＣＢ設計に実装されている表示を受け付けるステップと、
（ｅ）前記表示の受信後、前記ＰＣＢ設計のローカルコピーを前記検出されたルートを含むよう更新するステップと、
を前記プロセッサに実行させることを特徴とする媒体。
【請求項３３】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記ステップ（ｉ）において提起されたルートが前記ＰＣＢ設計に実装される表示を受け付けるステップと、
（ｊ）前記ステップ（ｉ）の表示の受信後、前記ＰＣＢ設計のローカルコピーを前記ステップ（ｇ）において検出されたルートを含むよう更新するステップと、
を有することを特徴とする媒体。
【請求項３４】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｈ）前記ステップ（ｇ）において検出されたルートを提起する編集リクエストを送信するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の他のルートを検出する指示を受け付けるステップと、
（ｊ）前記第２ピンペア割当てのピンの間の第２ルートを自動検出するステップと、
（ｋ）前記第２ルートを提起する編集リクエストを送信するステップと、
を有することを特徴とする媒体。
【請求項３５】
請求項３２記載のマシーン可読媒体であって、
前記ステップ（ｄ）は、前記ステップ（ａ）〜（ｅ）を実行するコンピュータ以外の１以上のコンピュータにより検出される他のルートが前記ＰＣＢ設計に実装されるという１以上の表示を受け付け、
前記ステップ（ｅ）は、前記ＰＣＢ設計のローカルコピーを前記他のルートを含むよう更新する、
ことを特徴とする媒体。
【請求項３６】
請求項３２記載のマシーン可読媒体であって、
前記命令シーケンスはさらに、
（ｆ）前記ステップ（ｄ）の表示の受信後、前記回路の１以上のコンポーネントのピンを特定する第２ピンペア割当てを受け付けるステップと、
（ｇ）前記第２ピンペア割当てのピンの間にルート決定された導電性パスに許されるビアの個数に対する制限の表示を受け付けるステップと、
（ｈ）前記第２ピンペア割当てのピンの間の導電性パスのルートを自動検出するステップと、
（ｉ）前記第２ピンペア割当てのピンの間の接続をルート決定することが不可能であるという表示を送信するステップと、
を有することを特徴とする媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１０Ａ】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１０Ａ】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公表番号】特表２００８−５０７００２（Ｐ２００８−５０７００２Ａ）
【公表日】平成２０年３月６日（２００８．３．６）
【国際特許分類】
【出願番号】特願２００６−５４１２３５（Ｐ２００６−５４１２３５）
【出願日】平成１６年１１月１７日（２００４．１１．１７）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０３７１８３
【国際公開番号】ＷＯ２００５／０５２７３０
【国際公開日】平成１７年６月９日（２００５．６．９）
【出願人】（５００２４１８６０）メンター・グラフィクス・コーポレーション (42)
【Ｆターム（参考）】
【公表日】平成２０年３月６日（２００８．３．６）
【国際特許分類】
【出願日】平成１６年１１月１７日（２００４．１１．１７）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０３７１８３
【国際公開番号】ＷＯ２００５／０５２７３０
【国際公開日】平成１７年６月９日（２００５．６．９）
【出願人】（５００２４１８６０）メンター・グラフィクス・コーポレーション (42)
【Ｆターム（参考）】
[ Back to top ]