(57)【特許請求の範囲】
【請求項１】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割ステップと、該セグメント分割ステップで得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定ステップと、該等ディレイ分岐セグメント決定ステップで求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定ステップとをそなえて構成され、該等ディレイ分岐セグメント決定ステップにおける上記の第１〜第４ディレイ時間が、
【数１】
0004268694.tif 000019
により求められ、該等ディレイ分岐点決定ステップにおける該等ディレイ分岐点が、
【数２】
0004268694.tif 000020
により求められることを特徴とする、配線処理方法。
【請求項２】
該セグメント分割ステップにおいて設定される該分岐点が、該配線上の物理的な分岐点であることを特徴とする、請求項１記載の配線処理方法。
【請求項３】
該セグメント分割ステップにおいて設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であることを特徴とする、請求項１記載の配線処理方法。
【請求項４】
該セグメント分割ステップにおいて求められる該セグメントがシングルΠ型回路で評価されることを特徴とする、請求項１記載の配線処理方法。
【請求項５】
クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割ステップと、該セグメント分割ステップで得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定ステップと、該プロパゲーションディレイ時間決定ステップで求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整ステップとをそなえて構成され、該セグメント分割ステップにおいて設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であり、該セグメント分割ステップにおいて求められる該セグメントがシングルΠ型回路で評価されることを特徴とする、配線処理方法。
【請求項６】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割ステップと、該第１セグメント分割ステップで得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定ステップと、該等ディレイ分岐セグメント決定ステップで求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定ステップと、該等ディレイ分岐点決定ステップで求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定ステップと、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割ステップと、該第２セグメント分割ステップで得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定ステップと、該ディレイ時間決定ステップで求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定ステップで求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整ステップとをそなえて構成されたことを特徴とする、配線処理方法。
【請求項７】
該配線長調整ステップにて、該第５ディレイ時間と該プロパゲーションディレイ時間と該外部クロック源取込み部での外部クロックディレイ時間とを加算した時間と、設定時間とを比較した比較結果に基づいて、セグメント単位で配線長が調整されることを特徴とする、請求項６記載の配線処理方法。
【請求項８】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、該セグメント分割処理部で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定処理部と、該等ディレイ分岐セグメント決定処理部で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部とをそなえて構成され、該等ディレイ分岐セグメント決定処理部が上記の第１〜第４ディレイ時間を、
【数３】
0004268694.tif 000021
により求め、該等ディレイ分岐点決定処理部における該等ディレイ分岐点を、
【数４】
0004268694.tif 000022
により求めることを特徴とする、配線処理装置。
【請求項９】
クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、該セグメント分割処理部で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、該プロパゲーションディレイ時間決定処理部で求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成され、該セグメント分割処理部において設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であり、該セグメント分割処理部において求められる該セグメントがシングルΠ型回路で評価されることを特徴とすることを特徴とする、配線処理装置。
【請求項１０】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割処理部と、該第１セグメント分割処理部で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定処理部と、該等ディレイ分岐セグメント決定処理部で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部と、該等ディレイ分岐点決定処理部で求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定処理部と、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割処理部と、該第２セグメント分割処理部で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、該ディレイ時間決定処理部で求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定処理部で求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成されたことを特徴とする、配線処理装置。
【請求項１１】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割手順と、該セグメント分割手順で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定手順と、該等ディレイ分岐セグメント決定手順で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順とを、コンピュータに実行させ、該等ディレイ分岐セグメント決定手順における上記の第１〜第４ディレイ時間が、
【数５】
0004268694.tif 000023
により求められ、該等ディレイ分岐点決定手順における該等ディレイ分岐点が、
【数６】
0004268694.tif 000024
により求められるよう該コンピュータに実行させるための配線処理プログラムを記録したことを特徴とする、配線処理プログラム用記録媒体。
【請求項１２】
クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割手順と、該セグメント分割手順で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、該プロパゲーションディレイ時間決定手順で求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させ、該セグメント分割手順において設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であり、該セグメント分割手順において求められる該セグメントがシングルΠ型回路で評価されるよう該コンピュータに実行させるための配線処理プログラムを記録したことを特徴とする、配線処理プログラム用記録媒体。
【請求項１３】
クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割手順と、該第１セグメント分割手順で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定手順と、該等ディレイ分岐セグメント決定手順で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順と、該等ディレイ分岐点決定手順で求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定手順と、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割手順と、該第２セグメント分割手順で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、該ディレイ時間決定手順で求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定手順で求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させるための配線処理プログラムを記録したことを特徴とする、配線処理プログラム用記録媒体。
【発明の詳細な説明】
【０００１】
（目次）
発明の属する技術分野
従来の技術（図３２〜図３６）
発明が解決しようとする課題（図３４）
課題を解決するための手段
発明の実施の形態
（ａ）本発明の一実施形態にかかる会話型回路設計装置の構成の説明（図１，図２）
（ｂ）本発明の一実施形態にかかる会話型回路設計装置による配線処理方法の説明
（ｂ１）クロックスキューを低減させるための配線処理方法の第１の態様の説明（図３〜図８）
（ｂ２）クロックスキューを低減させるための配線処理方法の第２の態様の説明（図９〜図１４）
（ｂ３）クロックスキューを低減させるための配線処理方法の第３の態様の説明（図１５，図１６）
（ｂ４）配線経路を決定するための配線処理方法の第１の態様の説明（図１７〜図２４）
（ｂ５）配線経路を決定するための配線処理方法の第２の態様の説明（図２５〜図２８）
（ｂ６）配線経路を決定するための配線処理方法の第３の態様の説明（図２９〜図３１）
発明の効果
【０００２】
【発明の属する技術分野】
本発明は、計算機支援設計システム（ＣＡＤ；computer aided design ）において、大規模集積回路（ＬＳＩ；large scale integration)の設計の際に用いて好適な、配線処理方法及び配線処理装置並びに配線処理プログラム用記録媒体に関する。
【０００３】
例えばクロック同期式回路におけるクロック分配回路上の各クロックネットにおいては、クロック発生回路（ドライバ）から各クロック受信回路（レシーバ）へのディレイ時間（クロックの伝搬遅延時間）を等しくする、即ち、クロックの伝搬遅延時間の差分であるクロックスキューを小さくすることは、クロック分配回路の動作を安定させるために非常に重要な技術である。即ち、クロックスキューが大きいと、各クロックネットにおいては各レシーバが同期動作を行なうことができなくなるため、クロック分配回路のクロックスキューを低減する必要がある。
【０００４】
また、ＬＳＩにおいては、処理の高速化を図るために、ＬＳＩ上の各回路を接続する配線長の最小化及び配線性を向上させる必要もある。
この際に、配線を行なう前段階で配線可能性を見積もり、この配線可能性により各回路の配置の改善や配線領域の最適化を行なうことも考えられる。
特に、現在では、配線対象が巨大化しているため、早い段階での配線可能性の算出及び評価が必要とされている。
【０００５】
【従来の技術】
クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させるための配線処理方法は、これまでに数多く報告されている。
以下では、クロックスキューを低減させるための配線処理方法のうちで、代表的な方法であるＩＢＭによる方法について説明する。なお、この方法は、「Ren-Song Tsay,“Exact zero skew",Proc.IEEE Int.Conference on CAD,pp336-339,1991」に詳細に記載されている。
【０００６】
ここで、このクロックスキューを低減させるための配線処理方法を説明するにあたり、まず、クロック同期式回路におけるクロック分配回路上のクロックネットにおけるクロック・トリーの構成を図３４に示す。
クロック・トリー１３０は、図３４に示すように、レシーバ（クロック受信回路）１１２とワイヤ１１８からなるサブ・クロック・トリーと、レシーバ（クロック受信回路）１１５とワイヤ１２１からなるサブ・クロック・トリーとが、等ディレイ分岐点（タッピングポイント：tapping point ）ｘを介して接続されることにより構成されている。
【０００７】
即ち、クロック・トリー１３０においては、図３４においては図示しないドライバ（クロック発生回路）からのクロックが、等ディレイ分岐点ｘを介してレシーバ１１２，１１５に供給されるようになっている。
ここで、レシーバ１１２は、フリップフロップ回路（時定数ｔ1 ）１１３とコンデンサ（容量Ｃ1 ）１１４とをそなえて構成され、レシーバ１１５は、フリップフロップ回路（時定数ｔ2 ）１１６とコンデンサ（容量Ｃ2 ）１１７とをそなえて構成されている。
【０００８】
また、ワイヤ１１８は、１つの抵抗（抵抗値ｒ1 ）１１９と２つのコンデンサ（容量ｃ1 ／２）１２０からなるΠ型ＲＣ回路により構成されている。
さらに、ワイヤ１２１も、ワイヤ１１８と同様に１つの抵抗（抵抗値ｒ2 ）１２２と２つのコンデンサ（容量ｃ2 ／２）１２３からなるΠ型ＲＣ回路により構成されている。
【０００９】
ここで、図３４において、レシーバ１１２，１１５間を接続する配線を１つのΠ型ＲＣ回路で表す理由について説明する。
まず、１つのサブ・クロック・トリーについて着目して考える。
図３２は、バッファ付きクロック・トリーをモデル化して示したものであり、バッファ付きクロック・トリー１００は、図３２に示すように、ドライバとしてのクロック発生回路（クロックソース；clock source）１０１と、レシーバとしてのクロック受信回路（ラッチ；latch ）１０３とがバッファ（buffer）１０２を介して接続されることにより構成されたものである。
【００１０】
ここで、クロックソース１０１とバッファ１０２とはワイヤ（wire）１０４により接続され、バッファ１０２とラッチ１０３とはワイヤ（wire）１０５により接続されている。
このバッファ付きクロック・トリー１００は、詳細には、図３３に示すような構成を有している。
【００１１】
クロックソース１０１は抵抗（抵抗値ｒs ）１０６をそなえており、バッファ１０２はディレイ回路（内部ディレイ時間ｄb ）１１１，抵抗（抵抗値ｒb ）１０７及びコンデンサ（容量ｃb ）１０９をそなえており、ラッチ１０３はコンデンサ（容量ｃ1 ）１１０をそなえている。
ここで、クロックソース１０１からラッチ１０３までのディレイ時間としては、バッファ１０２のディレイ回路１１１による内部ディレイ時間ｄb のほか、ワイヤ１０４，１０５の配線抵抗によるディレイ時間等が考えられる。
【００１２】
このうち、配線抵抗については、近年の半導体微細加工技術の進歩によるトランジスタサイズ及び配線断面積の減少ため、無視することができなくなっている。
そこで、ディレイ時間の予測精度上、ワイヤ１０４，１０５を、分布定数回路として扱うことが必要となっており、この分布定数回路を模式化した集中定数回路として、ワイヤ１０４，１０５を、図３３に示すように、それぞれ１つの抵抗（抵抗値ｒs ）１０６と２つのコンデンサ（容量ｃ1 ／２）１０８からなるΠ型ＲＣ回路で評価する考え方が一般的となっている。
【００１３】
ところで、等ディレイ分岐点ｘは、前述したように、図３４においては図示しないドライバ（クロック発生回路）からのクロックが入力される点である。
この図３４に示すクロック・トリー１３０においては、等ディレイ分岐点ｘの位置により、クロック・トリー１３０の２つのサブ・クロック・トリーにおけるクロックスキューが変化するため、クロック・トリー１３０におけるクロックスキューを低減させるには、等ディレイ分岐点ｘの位置の設定を正確に行なうことが必要となる。
【００１４】
ここで、２つのサブ・クロック・トリー間の配線における等ディレイ分岐点ｘの決定方法（zero-skew-merge ) について説明すると、この等ディレイ分岐点ｘは、次式を満たすことが知られている。
ｒ1 （ｃ1 ／２＋Ｃ1 ）＋ｔ1 ＝ｒ2 （ｃ2 ／２＋Ｃ2 ）＋ｔ2 
このとき、
Ｌ：２つのサブ・クロック・トリー間の線長
α：線路の単位長当たりの抵抗
β：線路の単位長当たりの容量
とすると、等ディレイ分岐点ｘは、
ｘ＝〔（ｔ2 −ｔ1 ）＋αＬ（Ｃ2 ＋βＬ／２）〕／〔αＬ（βＬ＋Ｃ1 ＋Ｃ2 ）〕
により決定することができる。
【００１５】
ところで、ＬＳＩ上の各回路は、自動配線において探索された最適な配線経路により接続される。
自動配線において配線経路を探索する方法は、これまで数多く報告されているが、以下では、線分探索法の一種である三上・田淵による方法（三上・田淵法）について説明する。
【００１６】
ここで、線分探索法とは、垂直又は水平の探針を次々に発生することにより配線経路を探索する方法であり、少ない記憶容量で高速処理できる利点がある。
三上・田淵法では、図３５に示すように、まず探索の開始点Ｓ及び探索の終了点Ｔからレベル０の仮線分を水平方向に発生し、これらの仮線分が重複しない場合には、続いてレベル０の仮線分に垂直に交わるレベル１の仮線分を発生する。
【００１７】
そして、これらのステップを繰り返し、両側からの仮線分が交差したときには、交差した仮線分を逆探索することにより、例えば図３６に示すような配線経路を見つけることができる。
この三上・田淵法では、配線経路が存在する場合は必ずその配線経路を見つけることができるが、レベルが増すに伴って加速度的に仮線分数が増すことから、最悪の場合は格子点の数に等しい仮線分を調べることになる。このため、通常は仮線分のレベル数を例えば２又は３に限定して用いている。
【００１８】
【発明が解決しようとする課題】
しかしながら、図３４に示すようなクロック・トリー１３０においては、前述したようにワイヤ１１８，１２１を、それぞれシングルΠ型ＲＣ回路（Π型ＲＣモデル）で評価している。
これは、等ディレイ分岐点ｘを決定する際に、等ディレイ分岐点ｘの両側の配線における単位グリッド当たりの抵抗及び容量が場所によらず等しいと仮定しているからである。
【００１９】
ところが、現実には、単位グリッド当たりの抵抗及び容量が場所によらず等しいということはありえないため、ワイヤ１１８，１２１を複数のセグメントに分割することにより直列Π型ＲＣ回路（直列Π型ＲＣモデル）で評価して、等ディレイ分岐点ｘを決定する必要があるという課題がある。
また、図３４に示すようなクロック・トリー１３０においては、等ディレイ分岐点ｘを決定する際に、より現実に即したものとするために、図示しないクロック発生回路に負荷がつくことにより増加するゲートディレイ（外部クロックディレイ時間；extra-source gate delay ）を考慮しながら、クロック発生回路から各クロック受信回路までのディレイ時間を目的値に設定する必要があるという課題もある。
【００２０】
さらに、前述したような、自動配線において配線経路を探索する方法の１つである三上・田淵法においては、同レベルの各仮線分（探索線分）の処理は相互に影響を及ぼさないため、各探索線分の処理を並列に実行することができれば探索処理の高速化が可能である。
また、この三上・田淵法では、一度探索された点は再度探索されることはないため、最適な配線経路が探索される前に最適でない配線経路が探索された場合には、最適ではない配線経路が選択されてしまうという課題がある。
【００２１】
このため、複数の配線経路を探索できるようにして、その中から最適な配線経路を選択する方法が必要である。
さらに、前述したように、ＬＳＩにおいては、配線を行なう前段階で配線可能性を見積もることができれば、この配線可能性により各回路の配置の改善や配線領域の最適化を行なうことも考えられる。
【００２２】
しかしながら、各回路の配置終了時に配線対象の配線可能性を知ることは困難であるため、配線を行なうまでは配線可能性を知ることができないという課題がある。
本発明は、このような課題に鑑み創案されたもので、ＣＡＤにおいて、ＬＳＩの設計の際に用いて好適な配線処理方法であって、具体的には、正確に等ディレイ分岐点を決定したり外部クロックディレイ時間を考慮することによりクロック分配回路のクロックスキューを低減させ、配線経路の探索における各探索線分の処理を並列に実行できるようにして処理の高速化を図り、最適な配線経路を選択できるようにしてＬＳＩ上の各回路を接続する配線長の最小化及び配線性を向上させ、配線を行なう前段階で配線可能性を見積もることにより各回路の配置の改善や配線領域の最適化を行なえるようにした、配線処理方法及び配線処理装置を提供することを目的とするとともに、更にはこのような配線処理を行なうための手順をコンピュータに実行させるための配線処理プログラムを記録した配線処理プログラム用記録媒体を提供することを目的とする。
【００２３】
【課題を解決するための手段】
このため、本発明の配線処理方法は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割ステップと、該セグメント分割ステップで得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定ステップと、該等ディレイ分岐セグメント決定ステップで求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定ステップとをそなえて構成され、該等ディレイ分岐セグメント決定ステップにおける上記の第１〜第４ディレイ時間が、
【数７】
0004268694.tif 000002
により求められ、該等ディレイ分岐点決定ステップにおける該等ディレイ分岐点が、
【数８】
0004268694.tif 000003
により求められることを特徴としている（請求項１）。
【００２４】
ここで、該セグメント分割ステップにおいて設定される該分岐点は、該配線上の物理的な分岐点であってもよく（請求項２）、該セグメント分割ステップにおいて設定される該分岐点は、該配線の単位長当たりのインピーダンスが変化する点であってもよい（請求項３）。
また、該セグメント分割ステップにおいて求められる該セグメントはシングルΠ型回路で評価することができる（請求項４）。
【００２７】
さらに、本発明の配線処理方法は、クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割ステップと、該セグメント分割ステップで得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定ステップと、該プロパゲーションディレイ時間決定ステップで求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整ステップとをそなえて構成されたことを特徴としている（請求項５）。
【００２８】
ここで、該セグメント分割ステップにおいて設定される該分岐点は、該配線の単位長当たりのインピーダンスが変化する点であり（請求項５）。また、該セグメント分割ステップにおいて求められる該セグメントはシングルΠ型回路で評価される（請求項５）。さらに、本発明の配線処理方法は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割ステップと、該第１セグメント分割ステップで得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定ステップと、該等ディレイ分岐セグメント決定ステップで求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定ステップと、該等ディレイ分岐点決定ステップで求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定ステップと、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割ステップと、該第２セグメント分割ステップで得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定ステップと、該ディレイ時間決定ステップで求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定ステップで求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整ステップとをそなえて構成されたことを特徴としている（請求項６）。
【００２９】
ここで、該配線長調整ステップにて、該第５ディレイ時間と該プロパゲーションディレイ時間と該外部クロック源取込み部での外部クロックディレイ時間とを加算した時間と、設定時間とを比較した比較結果に基づいて、セグメント単位で配線長を調整してもよい（請求項７）。また、本発明に関連する配線処理方法は、回路基板上の配線についての配線経路を決定するに際し、予め、該配線の最小ピッチを単位として、配線領域を格子状に分割し、格子点が該配線に使用可能であるかどうかを示す使用可能フラグと、格子点に探索線分が到着したことを示す到着状況フラグと、格子点に探索線分が到着した方向を示す到着方向フラグとを用意した状態で、該到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、該使用可能フラグが使用可能状態を示しており、且つ、該到着状況フラグが探索線分未到着を示している場合に、該隣接格子点の該到着状況フラグを探索線分到着を示す状態にするともに、該隣接格子点の該到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行し、更に該隣接格子点フラグ処理手順を、各探索線分について、該到着状況フラグを探索線分到着を示す状態にするような格子点がなくなるまで、繰り返して実行する前方探索処理ステップと、該前方探索処理ステップの後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、配線経路を検索する後方探索処理ステップとをそなえて構成されていることを特徴としている。
【００３０】
さらに、本発明に関連する配線処理方法は、回路基板上の配線についての配線経路を決定するに際し、予め、該配線の最小ピッチを単位として、配線領域を格子状に分割し、格子点に探索線分が到着した方向を示す到着方向フラグを用意した状態で、各格子点について、該到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく前方探索処理ステップと、該前方探索処理ステップの後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、複数の配線経路を検索する後方探索処理ステップと、該後方探索処理ステップで得られた複数の配線経路から最適な配線経路を決定する最適配線経路決定ステップとをそなえて構成されていることを特徴としている。
【００３１】
また、本発明に関連する配線処理方法は、回路基板上の回路についての配置を決定する回路配置決定ステップと、該回路配置決定ステップにて、該回路についての配置を決定した後に、該回路を接続する配線の総配線長をＬとし、該配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを該配線についての配線混雑度として評価する配線混雑度評価ステップとそなえて構成されていることを特徴としている。
【００３２】
さらに、本発明の配線処理装置は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、該セグメント分割処理部で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定処理部と、該等ディレイ分岐セグメント決定処理部で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部とをそなえて構成され、該等ディレイ分岐セグメント決定処理部が上記の第１〜第４ディレイ時間を、
【数９】
0004268694.tif 000004
により求め、該等ディレイ分岐点決定処理部における該等ディレイ分岐点を、
【数１０】
0004268694.tif 000005
により求めることを特徴としている（請求項８）。
【００３３】
また、本発明の配線処理装置は、クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、該セグメント分割処理部で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、該プロパゲーションディレイ時間決定処理部で求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成され、該セグメント分割処理部において設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であり、該セグメント分割処理部において求められる該セグメントがシングルΠ型回路で評価されることを特徴としている（請求項９）。
【００３４】
さらに、本発明の配線処理装置は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割処理部と、該第１セグメント分割処理部で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定処理部と、該等ディレイ分岐セグメント決定処理部で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部と、該等ディレイ分岐点決定処理部で求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定処理部と、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割処理部と、該第２セグメント分割処理部で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、該ディレイ時間決定処理部で求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定処理部で求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成されたことを特徴としている（請求項１０）。
【００３５】
また、本発明に関連する配線処理装置は、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた格子点に探索線分が到着したことを示す到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、格子点が該配線に使用可能であるかどうかを示す使用可能フラグが使用可能状態を示しており、且つ、該到着状況フラグが探索線分未到着を示している場合に、該隣接格子点の該到着状況フラグを探索線分到着を示す状態にするともに、該隣接格子点において、該隣接格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行し、更に該隣接格子点フラグ処理手順を、各探索線分について、該到着状況フラグを探索線分到着を示す状態にするような格子点がなくなるまで、繰り返して実行する前方探索処理を行なう前方探索処理部と、該前方探索処理部における該前方探索処理の後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、配線経路を検索する後方探索処理を行なう後方探索処理部とをそなえて構成されたことを特徴としている。
【００３６】
さらに、本発明に関連する配線処理装置は、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、該格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく前方探索処理部と、該前方探索処理部における該前方探索の後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、複数の配線経路を検索する後方探索処理部と、該後方探索処理部で得られた複数の配線経路から最適な配線経路を決定する最適配線経路決定処理部とをそなえて構成されたことを特徴としている。
【００３７】
また、本発明に関連する配線処理装置は、回路基板上の回路についての配置を決定する回路配置決定処理部と、該回路配置決定処理部にて、該回路についての配置を決定した後に、該回路を接続する配線の総配線長をＬとし、該配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを該配線についての配線混雑度として評価する配線混雑度評価処理部とをそなえて構成されたことを特徴としている。
【００３８】
さらに、本発明の配線処理プログラム用記録媒体は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割手順と、該セグメント分割手順で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定手順と、該等ディレイ分岐セグメント決定手順で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順とを、コンピュータに実行させ、該等ディレイ分岐セグメント決定手順における上記の第１〜第４ディレイ時間が、
【数１１】
0004268694.tif 000006
により求められ、該等ディレイ分岐点決定手順における該等ディレイ分岐点が、
【数１２】
0004268694.tif 000007
により求められるよう該コンピュータに実行させるための配線処理プログラムを記録したことを特徴としている（請求項１１）。
【００３９】
また、本発明の配線処理プログラム用記録媒体は、クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割手順と、該セグメント分割手順で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、該プロパゲーションディレイ時間決定手順で求められた該配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、該セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させ、該セグメント分割手順において設定される該分岐点が、該配線の単位長当たりのインピーダンスが変化する点であり、該セグメント分割手順において求められる該セグメントがシングルΠ型回路で評価されるよう該コンピュータに実行させるための配線処理プログラムを記録したことを特徴としている（請求項１２）。
【００４０】
さらに、本発明の配線処理プログラム用記録媒体は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割手順と、該第１セグメント分割手順で得られたセグメントについて、該セグメントの一端に位置する一分岐点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、該一分岐点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、該セグメントの他端に位置する他分岐点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、該他分岐点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する等ディレイ分岐セグメント決定手順と、該等ディレイ分岐セグメント決定手順で求められた該等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順と、該等ディレイ分岐点決定手順で求められた該等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定手順と、該等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割手順と、該第２セグメント分割手順で得られた各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、該ディレイ時間決定手順で求められた該等ディレイ分岐点から各レシーバへの該第５ディレイ時間と該プロパゲーションディレイ時間決定手順で求められた該配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させるための配線処理プログラムを記録したことを特徴としている（請求項１３）。
【００４１】
また、本発明に関連する配線処理プログラム用記録媒体は、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた格子点に探索線分が到着したことを示す到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、格子点が該配線に使用可能であるかどうかを示す使用可能フラグが使用可能状態を示しており、且つ、該到着状況フラグが探索線分未到着を示している場合に、該隣接格子点の該到着状況フラグを探索線分到着を示す状態にするともに、該隣接格子点において、該隣接格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行し、更に該隣接格子点フラグ処理手順を、各探索線分について、該到着状況フラグを探索線分到着を示す状態にするような格子点がなくなるまで、繰り返して実行する前方探索処理手順と、該前方探索処理手順の後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、配線経路を検索する後方探索処理手順とを、コンピュータに実行させるための配線処理プログラムを記録したことを特徴としている。
【００４２】
さらに、本発明に関連する配線処理プログラム用記録媒体は、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、該格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく前方探索処理手順と、該前方探索処理手順の後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、複数の配線経路を検索する後方探索処理手順と、該後方探索処理手順で得られた複数の配線経路から最適な配線経路を決定する最適配線経路決定手順とを、コンピュータに実行させるための配線処理プログラムを記録したことを特徴としている。
【００４３】
また、本発明に関連する配線処理プログラム用記録媒体は、回路基板上の配線の総配線長をＬとし、該配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを該配線についての配線混雑度として評価する配線混雑度評価手順をコンピュータに実行させるための配線処理プログラムを記録したことを特徴としている。
【００４４】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
（ａ）本発明の一実施形態にかかる会話型回路設計装置の構成の説明
図１は本発明の一実施形態にかかる配線処理装置としての会話型回路設計装置の構成を示すブロック図である。
【００４５】
この図１に示す会話型回路設計装置１において、３は各種回路設計過程や各回路を接続する配線経路等を表示する表示部、４はこの表示部３上における表示状態を制御する表示制御部、７は表示部３上の表示データを参照し設計者がその表示データに対する応答情報を入力するキーボード，マウス等の入力部である。
５は外部ファイル書込部で、この外部ファイル書込部５は、入力部７からの指示に応じて、表示制御部４により表示部３に表示された配線経路図等を外部ファイル５Ａに書き込むものである。
【００４６】
また、６は印字部で、この印字部６は、入力部７からの指示に応じて、表示制御部４により表示部３に表示された配線経路図等を所定の記録用紙に印字出力するものである。
さらに、８はハードディスクで、このハードディスク８は、会話型回路設計装置１が各種回路設計の際に用いる一切の情報（論理回路情報やレイアウト情報等）を記録するものであるとともに、後述する（ｂ）において詳細に説明するような各種の配線処理方法を実現するための手順を会話型回路設計装置１に実行させるための配線処理プログラム（配線処理ソフトウエア）を記録するものであり、本実施形態においては配線処理プログラム用記録媒体として機能するものである。
【００４７】
また、２は会話型回路設計装置１を構成する各部を統括的に管理するためのＣＰＵである。
なお、表示制御部４の機能は、具体的には、ＣＰＵ２がハードディスク８に格納されたプログラム（ソフトウエア）を実行することにより実現されるものであるが、図１においては、その機能を明確にすべく、表示制御部４をブロック化して示している。
【００４８】
従って、本実施形態にかかる会話型回路設計装置１は、ＣＰＵ２，表示部３，外部ファイル書込部５，印字部６，入力部７，ハードディスク８等を有する一般的な計算機システム（コンピュータ；図２参照）を用いて実現することが可能である。なお、図２において、９はコンピュータ本体である。
（ｂ）本発明の一実施形態にかかる会話型回路設計装置による配線処理方法の説明
（ｂ１）クロックスキューを低減させるための配線処理方法の第１の態様の説明
本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させるための配線処理方法の第１の態様について説明する。
【００４９】
ここで、本態様を説明するにあたり、まず、クロック同期式回路におけるクロック分配回路上のクロックネットのクロック・トリーの構成を図５及び図６に示す。
クロック・トリー３０は、図６に示すように、レシーバ（クロック受信回路）３１とワイヤ３７からなるサブ・クロック・トリーと、レシーバ（クロック受信回路）３４とワイヤ４０からなるサブ・クロック・トリーとが、等ディレイ分岐点（タッピングポイント：tapping point ）ｘを介して接続されることにより構成されている。
【００５０】
即ち、クロック・トリー３０においては、図６においては図示しないドライバ（クロック発生回路）からのクロックが、等ディレイ分岐点ｘを介してレシーバ３１，３４に供給されるようになっている。
ここで、レシーバ３１は、フリップフロップ回路（時定数ｔA ）３２とコンデンサ（容量ＣA ）３３とをそなえて構成され、レシーバ３４は、フリップフロップ回路（時定数ｔB ）３５とコンデンサ（容量ＣB ）３６とをそなえて構成されている。
【００５１】
また、ワイヤ３７は、後述するような理由から、１つの抵抗（抵抗値ｒ1 ）３８と２つのコンデンサ（容量ｃ1 ／２）３９からなるΠ型ＲＣ回路（即ちセグメント４３）を複数そなえて構成されている。
さらに、ワイヤ４０も、ワイヤ３７と同様に、後述するような理由から、１つの抵抗（抵抗値ｒ2 ）４１と２つのコンデンサ（容量ｃ2 ／２）４２からなるΠ型ＲＣ回路（即ちセグメント４３）を複数そなえて構成されている。
【００５２】
なお、この図６では、ワイヤ３７，４０におけるΠ型ＲＣ回路（セグメント４３）をそれぞれ１つしか図示しておらず、その他のセグメント４３については図示を省略している。
また、図５では、ワイヤ３７，４０の図示を省略しているが、レシーバ３１，３４間の配線における複数のセグメントを符号４３で示している（図５の網かけ部）。
【００５３】
ところで、図６に示す等ディレイ分岐点ｘは、前述したように、図６では図示しないドライバ（クロック発生回路）からのクロックが入力される点である。
この図６に示すクロック・トリー３０においては、等ディレイ分岐点ｘの位置により、クロック・トリー３０の２つのサブ・クロック・トリーにおけるクロックスキューが変化するため、クロック・トリー３０におけるクロックスキューを低減させるには、等ディレイ分岐点ｘの位置の設定を正確に行なうことが必要となる。
【００５４】
ここで、２つのサブ・クロック・トリー間の配線における等ディレイ分岐点ｘの決定方法（zero-skew-merge ) について説明する。
本態様における等ディレイ分岐点ｘを決定するための配線処理方法は、図７に示すように、セグメント分割ステップ（ステップＳ１），等ディレイ分岐セグメント決定ステップ（ステップＳ２）及び等ディレイ分岐点決定ステップ（ステップＳ３）をそなえて構成されている。
【００５５】
セグメント分割ステップ（ステップＳ１）は、例えば図５に示すように、レシーバ３１，３４間を接続する配線について、少なくとも２個以上の分割点（分岐点）Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４３に分割するステップである。
ここで、レシーバ３１，３４間を接続する配線（図６に示すワイヤ３７，４０）を複数のセグメント４３に分割する理由について説明する。
【００５６】
まず、１つのサブ・クロック・トリーについて着目して考える。
図３は、バッファ付きクロック・トリーをモデル化して示したものであり、バッファ付きクロック・トリー１０は、図３に示すように、ドライバとしてのクロック発生回路（クロックソース；clock source）１１と、レシーバとしてのクロック受信回路（ラッチ；latch ）１３とがバッファ（buffer）１２を介して接続されることにより構成されたものである。
【００５７】
ここで、クロックソース１１とバッファ１２とはワイヤ（wire）１４により接続され、バッファ１２とラッチ１３とはワイヤ（wire）１５により接続されている。
このバッファ付きクロック・トリー１０は、詳細には、図４に示すような構成を有している。
【００５８】
クロックソース１１は抵抗（抵抗値ｒs ）１６をそなえており、バッファ１２はディレイ回路（内部ディレイ時間ｄb ）１９，抵抗（抵抗値ｒb ）１７及びコンデンサ（容量ｃb ）１８をそなえており、ラッチ１３はコンデンサ（容量ｃ1 ）２０をそなえている。
ここで、クロックソース１１からラッチ１３までのディレイ時間としては、図３３を用いて前述したように、バッファ１２のディレイ回路１９による内部ディレイ時間ｄb のほか、ワイヤ１４，１５の配線抵抗によるディレイ時間等が考えられる。
【００５９】
このうち、配線抵抗については、近年の半導体微細加工技術の進歩によるトランジスタサイズ及び配線断面積の減少ため、無視することができなくなっているため、ディレイ時間の予測精度上、ワイヤ１４，１５を、分布定数回路として扱うことが必要となっている。
前述した図３３に示すようなバッファ付きクロック・トリー１００においては、この分布定数回路を模式化した集中定数回路として、ワイヤ１０４，１０５を、それぞれ１つのΠ型ＲＣ回路（シングルΠ型ＲＣモデル）で評価しているが、本態様においては、配線（ワイヤ１４，１５）における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮するために、ワイヤ１４，１５を複数のセグメント４３に分割することにより複数のΠ型ＲＣ回路で評価しているのである。
【００６０】
なお、ワイヤ１４は、図４に示すように、１つの抵抗（抵抗値ｒ1 …ｒk ）２１Ａと２つのコンデンサ〔容量（ｃ1 ／２）…（ｃk ／２）〕２１ＢからなるΠ型ＲＣ回路（即ちセグメント）２１を複数そなえて構成され、ワイヤ１５は、図４に示すように、１つの抵抗（抵抗値ｒm …ｒn ）２２Ａと２つのコンデンサ〔容量（ｃm ／２）…（ｃn ／２）〕２２ＢからなるΠ型ＲＣ回路（即ちセグメント）２２を複数そなえて構成されている。
【００６１】
ここで、このセグメント分割ステップ（ステップＳ１）においては、図５に示すレシーバ３１，３４間を接続する配線は、具体的には以下のような条件の分割点Ｐ1 ，…，Ｐn+1 でセグメント４３に分割される。
（１）レシーバ３１，３４間を接続する配線上の物理的な分岐点。
ここで、物理的な分岐点とは配線の層が変わる点であり、例えば図５では分割点Ｐ4 ，Ｐ7 がこの点に当たる。
【００６２】
（２）レシーバ３１，３４間を接続する配線の単位長当たりのインピーダンスが変化する点。
ここで、配線の単位長当たりのインピーダンスは、配線の層が変わると変化するが、配線の層が変わらなくても変化することがあるため（配線の下層に電源が配置される場合等）、配線の単位長当たりのインピーダンスが変化する点を分割点とすることが有効となる。なお、インピーダンスは抵抗または容量である。
【００６３】
（３）セグメント４３の長さがある決められた長さｓ（任意の定数）を超える点。
ここで、セグメント長ｓは、経験的に求められる長さである。
上述した（１）〜（３）のいずれかに該当する分割点Ｐ1 ，…，Ｐn+1 において分割された各セグメント４３は、上述したように、それぞれ１つのΠ型ＲＣモデルで評価される。
【００６４】
また、等ディレイ分岐セグメント決定ステップ（ステップＳ２）は、セグメント分割ステップ（ステップＳ１）で得られたセグメント４３について、等ディレイ分岐点ｘが存在するセグメント４３を、等ディレイ分岐セグメントとして決定するステップである。
具体的には、この等ディレイ分岐セグメント決定ステップ（ステップＳ２）においては、セグメント４３の一端に位置する一分割点Ｐk から上記２つのレシーバ３１，３４のうちの一方のレシーバ（図５では次段のゲートＡと接続されるレシーバ３１）へのディレイ時間が、第１ディレイ時間〔Delay （Ｐk →Ａ）〕として求められるとともに、一分割点Ｐk から上記２つのレシーバ３１，３４のうちの他方のレシーバ（図５では次段のゲートＢと接続されるレシーバ３４）へのディレイ時間が、第２ディレイ時間〔Delay （Ｐk →Ｂ）〕として求められる。
【００６５】
そして、これらの第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕とが比較される。
さらに、セグメント４３の他端に位置する他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの一方のレシーバへのディレイ時間が、第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕として求められるとともに、他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの他方のレシーバへのディレイ時間が、第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕として求められる。
【００６６】
そして、これらの第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕とが比較される。
さらに、上記の第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕との大小関係と、上記の第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕との大小関係とが反転するセグメント４３が、等ディレイ分岐点ｘが存在する等ディレイ分岐セグメントとして決定される。
【００６７】
即ち、この等ディレイ分岐セグメント決定ステップ（ステップＳ２）は、分割点Ｐ1 〜Ｐn+1 の中から２分法により、
Delay （Ｐk →Ａ）    ≦  Delay （Ｐk →Ｂ）
Delay （Ｐk+1 →Ａ）  ≧  Delay （Ｐk+1 →Ｂ）
となる条件を満たす分割点Ｐk ，Ｐk+1 を求めるステップであり、等ディレイ分岐セグメントは、分割点Ｐk ，Ｐk+1 間のセグメント（セグメントＰk Ｐk+1 ）となる。
【００６８】
ここで、上記の第１ディレイ時間〔Delay （Ｐk →Ａ）〕，第２ディレイ時間〔Delay （Ｐk →Ｂ）〕，第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕，第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕は、等ディレイ分岐セグメントにおける抵抗の抵抗値をｒk , 等ディレイ分岐セグメントにおけるコンデンサの容量をｃk とすると、次式により求めることができる。
【００６９】
【数１３】
0004268694.tif 000008
さらに、等ディレイ分岐点決定ステップ（ステップＳ３）は、等ディレイ分岐セグメント決定ステップ（ステップＳ２）で求められた等ディレイ分岐セグメント中で等ディレイ分岐点ｘを求めるステップである。この等ディレイ分岐点決定ステップ（ステップＳ３）においては、図６に示すように、分割点Ｐk からゲートＡまでをサブ・クロック・トリーＡとしてｔA とＣA が計算されるとともに、分割点Ｐk+1 からゲートＢまでをサブ・クロック・トリーＢとしてｔB とＣB が計算される。
【００７０】
ここで、
ＣA ：分割点Ｐk からゲートＡまでの容量の合計
ＣB ：分割点Ｐk+1 からゲートＢまでの容量の合計
ｔA ：分割点Ｐk からゲートＡまでの配線ディレイ
ｔB ：分割点Ｐk+1 からゲートＢまでの配線ディレイ
である。
【００７１】
そして、分割点Ｐk から分割点Ｐk+1 までは単位長当たりの容量及び抵抗が同じ区間であるので、従来技術であるＩＢＭによる方法と同様に、等ディレイ分岐点ｘは、次式により決定することができる。
【００７２】
【数１４】
0004268694.tif 000009
ここで、上述したような各ステップ（ステップＳ１〜Ｓ３）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２図１参照）が、図８に示すようなセグメント分割処理部Ａ１，等ディレイ分岐セグメント決定処理部Ａ２及び等ディレイ分岐点決定処理部Ａ３に相当する機能を有することにより実行される。
【００７３】
セグメント分割処理部Ａ１は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ３１，３４間を接続する配線について、少なくとも２個以上の分割点Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４３に分割する処理を行なうものである。
また、等ディレイ分岐セグメント決定処理部Ａ２は、セグメント分割処理部Ａ１で得られたセグメント４３について、等ディレイ分岐点ｘが存在するセグメント４３を、等ディレイ分岐セグメントとして決定する処理を行なうものである。
【００７４】
具体的には、この等ディレイ分岐セグメント決定処理部Ａ２は、セグメント４３の一端に位置する一分割点Ｐk から上記２つのレシーバ３１，３４のうちの一方のレシーバ（図５では次段のゲートＡと接続されるレシーバ３１）への第１ディレイ時間〔Delay （Ｐk →Ａ）〕と、一分割点Ｐk から上記２つのレシーバ３１，３４のうちの他方のレシーバ（図５では次段のゲートＢと接続されるレシーバ３４）への第２ディレイ時間〔Delay （Ｐk →Ｂ）〕とを比較するとともに、セグメントの他端に位置する他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの一方のレシーバへの第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と、他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの他方のレシーバへの第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕とを比較し、上記の第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕との大小関係と上記の第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕との大小関係とが反転するセグメント４３を等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する処理を行なうものである。
【００７５】
さらに、等ディレイ分岐点決定処理部Ａ３は、等ディレイ分岐セグメント決定処理部Ａ２で求められた等ディレイ分岐セグメント中で等ディレイ分岐点ｘを求める処理を行なうものである。
そして、実際には、このような各処理部Ａ１〜Ａ３に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
【００７６】
ここで、本態様における配線処理プログラムは、セグメント分割手順，等ディレイ分岐セグメント決定手順及び等ディレイ分岐点決定手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
セグメント分割手順は、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ３１，３４間を接続する配線について、少なくとも２個以上の分割点Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４３に分割する手順である。
【００７７】
また、等ディレイ分岐セグメント決定手順は、セグメント分割手順で得られたセグメント４３について、等ディレイ分岐点ｘが存在するセグメント４３を、等ディレイ分岐セグメントとして決定する手順である。
具体的には、この等ディレイ分岐セグメント決定手順は、セグメント４３の一端に位置する一分割点Ｐk から上記２つのレシーバ３１，３４のうちの一方のレシーバ（図５では次段のゲートＡと接続されるレシーバ３１）への第１ディレイ時間〔Delay （Ｐk →Ａ）〕と、一分割点Ｐk から上記２つのレシーバ３１，３４のうちの他方のレシーバ（図５では次段のゲートＢと接続されるレシーバ３４）への第２ディレイ時間〔Delay （Ｐk →Ｂ）〕とを比較するとともに、セグメントの他端に位置する他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの一方のレシーバへの第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と、他分割点Ｐk+1 から上記２つのレシーバ３１，３４のうちの他方のレシーバへの第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕とを比較し、上記の第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕との大小関係と上記の第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕との大小関係とが反転するセグメント４３を等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する手順である。
【００７８】
さらに、等ディレイ分岐点決定手順は、等ディレイ分岐セグメント決定手順で求められた等ディレイ分岐セグメント中で等ディレイ分岐点ｘを求める手順である。
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においては、以下のように動作することにより、２つのサブ・クロック・トリー間の配線における等ディレイ分岐点ｘが決定される。
【００７９】
即ち、会話型回路設計装置１においては、セグメント分割ステップ（ステップＳ１）により、レシーバ３１，３４間を接続する配線が、少なくとも２個以上の分割点Ｐ1 ，…，Ｐn+1 が設定されることにより、少なくとも３個以上のセグメント４３に分割される。
続いて、等ディレイ分岐セグメント決定ステップ（ステップＳ２）により、セグメント分割ステップ（ステップＳ１）で得られたセグメント４３について、前述したように第１〜第４ディレイ時間〔それぞれDelay （Ｐk →Ａ），〔Delay （Ｐk →Ｂ），Delay （Ｐk+1 →Ａ），Delay （Ｐk+1 →Ｂ）〕が求められ、第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕とが比較されるとともに、第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕とが比較される。
【００８０】
そして、第１ディレイ時間〔Delay （Ｐk →Ａ）〕と第２ディレイ時間〔Delay （Ｐk →Ｂ）〕との大小関係と、上記の第３ディレイ時間〔Delay （Ｐk+1 →Ａ）〕と第４ディレイ時間〔Delay （Ｐk+1 →Ｂ）〕との大小関係とが反転するセグメント４３が、等ディレイ分岐点ｘが存在する等ディレイ分岐セグメントとして決定される。
【００８１】
さらに、等ディレイ分岐点決定ステップ（ステップＳ３）により、等ディレイ分岐セグメント決定ステップ（ステップＳ２）で求められた等ディレイ分岐セグメント中で等ディレイ分岐点ｘが決定される。
このように、本発明の一実施形態にかかる会話型回路設計装置１におけるクロックスキューを低減させるための配線処理方法の第１の態様によれば、クロック同期式回路におけるクロック分配回路上の各クロックネットにおいて、レシーバ３１，３４間を接続する配線を複数のセグメント４３に分割して複数のシングルΠ型ＲＣ回路で評価することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮することができるため、レシーバ３１，３４間を接続する配線における等ディレイ分岐点ｘを正確に決定することができる。
【００８２】
また、分割点Ｐ1 ，…，Ｐn+1 を、（１）レシーバ３１，３４間を接続する配線上の物理的な分岐点，（２）レシーバ３１，３４間を接続する配線の単位長当たりのインピーダンスが変化する点，（３）セグメント４３の長さがある決められた長さｓ（任意の定数）を超える点，のいずれかとすることにより、各クロックネットの状態に応じた分割点Ｐ1 ，…，Ｐn+1 を設定することができ、等ディレイ分岐点ｘをより正確に決定することができる。
【００８３】
そして、このように等ディレイ分岐点ｘを正確に決定することができることにより、ドライバ（図６では図示せず）からレシーバ３１，３４までのディレイ時間を等しくすることができ、これにより、各クロックネットのクロック・トリー３０におけるクロックスキューを低減させることができる。
（ｂ２）クロックスキューを低減させるための配線処理方法の第２の態様の説明
さらに、本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させるための配線処理方法の第２の態様について説明する。
【００８４】
クロックスキューを低減させるための配線処理方法の第２の態様においては、各レシーバ間を接続する配線における等ディレイ分岐点を決定する際に、クロック発生回路であるドライバに負荷がつくことにより増加するゲートディレイ（外部クロックディレイ時間；extra-source gate delay ）を考慮するために、この等ディレイ分岐点とドライバ出力点（外部クロック源取込み部）との間の配線長を調整して、ドライバから各レシーバまでのディレイ時間を目的値に設定することにより、効果的に各クロックネットにおけるクロックスキューを低減させる方法について説明する。
【００８５】
図９は、ドライバ（クロック発生回路）４５Ａ及びクロック・トリー４５Ｂからなるクロックネット４４の構成を模式的に示す図である。
ここで、クロックネット４４は、クロック同期式回路におけるクロック分配回路上にあり、クロック・トリー４５Ｂは、複数のクロック・トリー（図５及び図６の符号３０参照）をそなえて構成されている。
【００８６】
即ち、この図９は、複数のレシーバ（図５及び図６の符号３１，３４参照）間の配線を完了してクロック・トリーを形成し、更にこのように形成された複数のクロック・トリー間の配線を完了してクロック・トリー４５Ｂを形成した後、このクロック・トリー４５Ｂの等ディレイ分岐点（レシーバ間の配線の最終の等ディレイ分岐点）Ｑとドライバ出力点（外部クロック源取込み部）Ｐとの間を最短配線により接続した様子を示している。
【００８７】
本態様においては、クロック・トリー４５Ｂにおいて正確に等ディレイ分岐点Ｑを決定した後に、前述のごとくドライバ出力点Ｐからクロック・トリー４５Ｂにおける各レシーバまでのディレイ時間が予め設定した時間となるようにするために、等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線の長さを調整するようになっている。
【００８８】
ここで、本態様における配線処理方法は、図１３に示すように、第１セグメント分割ステップ（ステップＳ４），等ディレイ分岐セグメント決定ステップ（ステップＳ５），等ディレイ分岐点決定ステップ（ステップＳ６），ディレイ時間決定ステップ（ステップＳ７），第２セグメント分割ステップ（ステップＳ８），プロパゲーションディレイ時間決定ステップ（ステップＳ９）及び配線長調整ステップ（ステップＳ１０）をそなえて構成されている。
【００８９】
第１セグメント分割ステップ（ステップＳ４）は、クロックネット４４のクロック・トリー４５Ｂにおける２つのレシーバ間を接続する配線（これは前述の図５に示すものと同様である）について、少なくとも２個以上の分割点（分岐点）を設定することにより、少なくとも３個以上のセグメントに分割するステップである。
【００９０】
本態様においても、前述の場合と同様に、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮するために、クロックネット４４における２つのレシーバ間を接続する配線を複数のセグメントに分割して、複数のΠ型ＲＣ回路（図６の符号４３参照）で評価している。
なお、図９においては、クロック・トリー４５Ｂにおける分割点及びセグメントの図示は省略している。
【００９１】
また、分割点は、前述の場合と同様に、（１）レシーバ間を接続する配線上の物理的な分岐点，（２）レシーバ間を接続する配線の単位長当たりのインピーダンスが変化する点，（３）セグメントの長さがある決められた長さｓ（任意の定数）を超える点，のいずれかである。
さらに、等ディレイ分岐セグメント決定ステップ（ステップＳ５）は、第１セグメント分割ステップ（ステップＳ４）で得られたセグメントについて、等ディレイ分岐点Ｑが存在するセグメントを、等ディレイ分岐セグメントとして決定するステップである。
【００９２】
具体的には、この等ディレイ分岐セグメント決定ステップ（ステップＳ５）は、前述の場合と同様に、セグメントの一端に位置する一分割点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、一分割点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、セグメントの他端に位置する他分割点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、他分割点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点Ｑが存在する等ディレイ分岐セグメントとして決定するステップである。
【００９３】
なお、上記の第１〜第４ディレイ時間についても、（ｂ１）にて前述した場合と同様にして求めることができる〔それぞれ前述の、Delay （Ｐk →Ａ），Delay （Ｐk →Ｂ），Delay （Ｐk+1 →Ａ），Delay （Ｐk+1 →Ｂ）参照〕。
また、等ディレイ分岐点決定ステップ（ステップＳ６）は、等ディレイ分岐セグメント決定ステップ（ステップＳ５）で求められた等ディレイ分岐セグメント中で等ディレイ分岐点Ｑを求めるステップである。
【００９４】
なお、この等ディレイ分岐点Ｑについても、（ｂ１）にて前述した場合と同様にして求めることができる。
さらに、ディレイ時間決定ステップ（ステップＳ７）は、等ディレイ分岐点決定ステップ（ステップＳ６）で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR を求めるステップである。
【００９５】
即ち、この第５ディレイ時間ｔR は、図１０に示すように、クロック・トリー４５Ｂにおける等ディレイ分岐点Ｑから各レシーバへのディレイ時間である。
ここで、第５ディレイ時間ｔR は、
0004268694.tif 000010
により求めることができる。
【００９６】
また、第２セグメント分割ステップ（ステップＳ８）は、図９に示すように、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線について、少なくとも２個以上の分割点（分岐点）Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４６に分割するステップである。
本態様においても、前述の場合と同様に、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮するために、等ディレイ分岐点Ｑ，ドライバ出力点Ｐ間を接続する配線を複数のセグメント４６に分割して、複数のΠ型ＲＣ回路（図１０参照）で評価している。
【００９７】
この第２セグメント分割ステップ（ステップＳ８）においては、等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線は、具体的には以下のような条件の分割点Ｐ1 ，…，Ｐn+1 でセグメント４６に分割される。
（１）等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線の単位長当たりのインピーダンスが変化する点。
【００９８】
ここで、配線の単位長当たりのインピーダンスは、前述したように、配線の層が変わると変化するが、配線の層が変わらなくても変化することがあるため、配線の単位長当たりのインピーダンスが変化する点を分割点とすることが有効となる。なお、インピーダンスは抵抗または容量である。
（２）セグメント４６の長さがある決められた長さｓ（任意の定数）を超える点。
【００９９】
ここで、セグメント長ｓは、経験的に求められる長さである。
上述した（１），（２）のいずれかに該当する分割点Ｐ1 ，…，Ｐn+1 において分割された各セグメント４６は、図１０に示すように、１つの抵抗（抵抗値Ｒａ1 …Ｒａn ）４８と２つのコンデンサ〔容量（Ｃａ1 ／２）…（Ｃａn ／２）〕４７からなるΠ型ＲＣ回路（Π型ＲＣモデル）で評価される。
【０１００】
さらに、プロパゲーションディレイ時間決定ステップ（ステップＳ９）は、第２セグメント分割ステップ（ステップＳ８）で得られた各セグメント４６毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間（propagation delay ）ｔPQを求めるステップである。
ここで、プロパゲーションディレイ時間ｔPQは、
【０１０１】
【数１５】
0004268694.tif 000011
により求めることができる。また、配線長調整ステップ（ステップＳ１０）は、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整するステップである。
【０１０２】
ここで、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕は、ディレイ時間決定ステップ（ステップＳ７）で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR ，プロパゲーションディレイ時間決定ステップ（ステップＳ９）で求められた配線のプロパゲーションディレイ時間ｔPQ及びドライバ出力点Ｐでの外部クロックディレイ時間（extra-source gate delay ）ｔLOADを加算した時間である。
【０１０３】
即ち、図１０に示すように、クロック・トリー４５Ｂにおける等ディレイ分岐点Ｑから各レシーバまでのディレイ時間（第５ディレイ時間）をｔR ，等ディレイ分岐点Ｑから各レシーバまでの容量の合計をＣR とすると、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕は次式により求められる。
【０１０４】
Delay （Ｐ→各レシーバ）  ≒  ｔLOAD＋ｔ PQ ＋ｔ R
ここで、外部クロックディレイ時間（extra source gate delay ）ｔLOADについて、図１２を用いて説明すると、ドライバ（SOURCE）とレシーバ（LOAD）との間の配線におけるディレイ時間ＴINTERCONNECT delayは、
0004268694.tif 000012
である。
【０１０５】
なお、
ＴAB（０）：アンローデッド・ソース・ゲートからのディレイ時間
（delay through an unloaded source gate ）
ＴAB（Ｌ）：長さＬのインターコネクト・ネットによりロードされた同一ソース・ゲートからのディレイ時間
（delay through the same source gate loaded
by an interconnect net of length L）
である。
【０１０６】
そして、上記の式における〔ＴAB（Ｌ）−ＴAB（０）〕が、外部クロックディレイ時間ｔLOADを表わしている。
ここで、配線長調整ステップ（ステップＳ１０）においては、図９，図１０に示す分割点Ｐ1 でのｔLOADを求めるために、分割点Ｐ1 から見たアドミッタンス算出用のｙ１，ｙ２，ｙ３が計算される。
【０１０７】
即ち、分割点Ｐ1 でのｔLOADは、分割点Ｐ1 から見たアドミッタンス算出用のｙ１，ｙ２，ｙ３という式を計算し、これら３つの式を用いて所定の計算（この内容の詳細は本態様とは特に関係しない）を行なうことにより求めることができる。
即ち、ｔLOADは、
ｔLOAD＝Ｆ（ｙ１，ｙ２，ｙ３）
である。
【０１０８】
本実施形態において、アドミッタンス算出用のｙ１，ｙ２，ｙ３の計算は、「P.R.O'Brien and T.L.Savarino,“Modeling the Driving-Point Characteristics of Resistive Interconnect for Accurate Delay Estimation,IEEE Intl.Conference on CAD,pp512-515,1989 」に記載された方法に基づいて行なわれる。
ここで、ｙ１，ｙ２，ｙ３を求めるための、一般的な配線モデルの一例を図１１に示す。
【０１０９】
図１１において、４９はコンデンサ，５０は抵抗，５１はドライバ又はレシーバの出力ピンであり、Ｐ1 〜Ｐ9 は分割点である。
以下に、分割点Ｐ1 から見たアドミッタンス算出用のｙ１，ｙ２，ｙ３の算出方法を示す。
まず、ラプラス変換式をｙi （ｓ）で示し、レシーバ側からドライバ側へラプラス変換式を求めると、
0004268694.tif 000013
となる。
【０１１０】
そして、このｙ1 （ｓ）を、ラプラス表現の３次近似を行なうと、
ｙ1 （ｓ）  ＝  ｙ１・ｓ＋ｙ２・ｓ2 ＋ｙ３・ｓ3 
となるため、この式の係数ｙ１，ｙ２，ｙ３が求められる。
このようにして、配線長調整ステップ（ステップＳ１０）においては、前述の式により計算されたドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕と、予め設定された時間γとを比較して、この比較結果に基づいて、セグメント単位で等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線長が調整されるのである。
【０１１１】
なお、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕が、初めから予め設定された時間γを超えている場合には、ドライバ４５Ａやクロック・トリー４５Ｂ（図９，図１０参照）の配置変更を行なった後に、再度等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線長が調整される。
【０１１２】
具体的には、以下のように配置変更や配線長調整が行なわれる。
Delay （Ｐ→各レシーバ）  ＞  γ  ならば配置変更
Delay （Ｐ→各レシーバ）  ＝  γ  ならば終了
Delay （Ｐ→各レシーバ）  ＜  γ  ならば配線長調整
なお、配線長の調整は、分割点Ｐ1 と分割点Ｐ2 との間で行なう必要がある。
【０１１３】
ここで、分割点Ｐ1 と分割点Ｐ2 との間の最短の実配線長をＬLOWER とすると、分割点Ｐ1 と分割点Ｐ2 での配線の単位長当たりの抵抗α及び容量βは、以下のようになる。
α＝Ｒａ1 ／ＬLOWER 
β＝Ｃａ1 ／ＬLOWER 
そして、分割点Ｐ1 と分割点Ｐ2 との間で配線長の調整により新たに引かれる配線においては、上記のα，βを使用して、
Delay （Ｐ→各レシーバ）  ＝  γ
となるための分割点Ｐ1 と分割点Ｐ2 との間の配線長Ｌは、
ＬLOWER   ＜  Ｌ  ＜  ＬUPPER 
の範囲にある。
【０１１４】
ここで、ＬUPPER は、許容される最長の実配線長であり、ＬUPPER を求めるためには、図１１に示すドライバの出力ピン５１と分割点Ｐ1 との間に長さｓ〔これはラプラス変換式ｙi （ｓ）のｓとは無関係である〕のセグメントをひとつずつ挿入していき、その度毎に新たなｙ１，ｙ２，ｙ３を求めて、ｔLOADを求めていくことになる。
【０１１５】
ＬUPPER は、以下のような再帰的計算により求めることができる。
ｔ0 ＝ｔPQ＋ｔR 
【０１１６】
【数１６】
0004268694.tif 000014
Ｌ0 ＝ＬLOWER
ｙ１0 ＝ｙ１
ｙ２0 ＝ｙ２
ｙ３0 ＝ｙ３
ｔi ＝ｔi-1 ＋αｓ（βｓ／２＋Ｃi-1 ）
Ｃi ＝Ｃi-1 ＋βｓ
Ｌi ＝Ｌi-1 ＋ｓ
ここで、P.R.O'Brien and T.L.Savarinoの文献を参照すると、
ｙ１i ＝ｆ（ｙ１i-1 ）
ｙ２i ＝ｇ（ｙ１i-1 ，ｙ２i-1 ）
ｙ３i ＝ｈ（ｙ１i-1 ，ｙ２i-1 ，ｙ３i-1 ）
これにより、
ｔLOAD＝Ｆ（ｙ１i ，ｙ２i ，ｙ３i ）
ここで、
ｔi ＋ｔLOAD＞γ
とはじめてなったときのｓ・ｉ＋ＬLOWER の値をＬUPPER とし、Ｌi-1 値を新たにＬLOWER とする。なお、ｓは自然数であるが、５０くらいが適当であると考えられる。
【０１１７】
さらに、ｓ・（ｉ−１）＋ＬLOWER とＬUPPER との間で２分法により、分割点Ｐ1 と分割点Ｐ2 との間の配線長Ｌを決定しながら、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕が計算され、これにより、ディレイ時間が設定時間γとなる配線長Ｌが決定される。
即ち、ドライバの出力ピン５１と分割点Ｐ1 との間に長さｓのセグメントを順次挿入したと仮定し、ドライバ出力点Ｐ（図９，図１０参照）から各レシーバまでのディレイ時間が設定値γを超えるまで計算を続けると、この設定値γを超えたときは、全体としてはｓ・ｉ（ｉは繰り返し回数）の長さのセグメントを挿入したことになる。
【０１１８】
そこで、ディレイ時間が設定値γとなる配線長Ｌは、
〔ｓ・（ｉ−１）＋ＬUPPER 〕  ＜  Ｌ  ＜  （ｓ・ｉ＋ＬUPPER ）
となるため、２分法により設定値γとなる配線長Ｌを求めることができる。
そして、分割点Ｐ1 と分割点Ｐ2 との間の配線を削除して、配線長Ｌで再配線を行なう。
【０１１９】
ここで、上述したような各ステップ（ステップＳ４〜Ｓ１０）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２（図１参照）が、図１４に示すような第１セグメント分割処理部Ａ４，等ディレイ分岐セグメント決定処理部Ａ５，等ディレイ分岐点決定処理部Ａ６，ディレイ時間決定処理部Ａ７，第２セグメント分割処理部Ａ８，プロパゲーションディレイ時間決定処理部Ａ９及び配線長調整処理部Ａ１０に相当する機能を有することにより実行される。
【０１２０】
第１セグメント分割処理部Ａ４は、クロック同期式回路におけるクロック分配回路上のクロックネット４４における２つのレシーバ間を接続する配線について、少なくとも２個以上の分岐点を設定することにより、少なくとも３個以上のセグメントに分割する処理を行なうものである。
また、等ディレイ分岐セグメント決定処理部Ａ５は、第１セグメント分割処理部Ａ４で得られたセグメントについて、セグメントの一端に位置する一分割点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、一分割点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、セグメントの他端に位置する他分割点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、他分割点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する処理を行なうものである。
【０１２１】
さらに、等ディレイ分岐点決定処理部Ａ６は、等ディレイ分岐セグメント決定処理部Ａ５で求められた等ディレイ分岐セグメント中で等ディレイ分岐点Ｑを求める処理を行なうものである。
また、ディレイ時間決定処理部Ａ７は、等ディレイ分岐点決定処理部Ａ６で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR を求める処理を行なうものである。
【０１２２】
さらに、第２セグメント分割処理部Ａ８は、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線について、少なくとも２個以上の分割点Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４６に分割する処理を行なうものである。
また、プロパゲーションディレイ時間決定処理部Ａ９は、第２セグメント分割処理部Ａ８で得られた各セグメント４６毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間ｔPQを求める処理を行なうものである。
【０１２３】
さらに、配線長調整処理部Ａ１０は、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕、即ち、ディレイ時間決定処理部Ａ７で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR ，プロパゲーションディレイ時間決定処理部Ａ９で求められた配線のプロパゲーションディレイ時間ｔPQ及びドライバ出力点Ｐでの外部クロックディレイ時間ｔLOADを加算した時間と、設定時間γとを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する処理を行なうものである。
【０１２４】
そして、実際には、このような各処理部Ａ４〜Ａ１０に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
ここで、本態様における配線処理プログラムは、第１セグメント分割手順，等ディレイ分岐セグメント決定手順，等ディレイ分岐点決定手順，ディレイ時間決定手順，第２セグメント分割手順，プロパゲーションディレイ時間決定手順及び配線長調整手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
【０１２５】
第１セグメント分割手順は、クロック同期式回路におけるクロック分配回路上のクロックネット４４における２つのレシーバ間を接続する配線について、少なくとも２個以上の分岐点を設定することにより、少なくとも３個以上のセグメントに分割する手順である。
また、等ディレイ分岐セグメント決定手順は、第１セグメント分割手順で得られたセグメントについて、セグメントの一端に位置する一分割点から上記２つのレシーバのうちの一方のレシーバへの第１ディレイ時間と、一分割点から上記２つのレシーバのうちの他方のレシーバへの第２ディレイ時間とを比較するとともに、セグメントの他端に位置する他分割点から上記２つのレシーバのうちの一方のレシーバへの第３ディレイ時間と、他分割点から上記２つのレシーバのうちの他方のレシーバへの第４ディレイ時間とを比較し、上記の第１ディレイ時間と第２ディレイ時間との大小関係と上記の第３ディレイ時間と第４ディレイ時間との大小関係とが反転するセグメントを等ディレイ分岐点が存在する等ディレイ分岐セグメントとして決定する手順である。
【０１２６】
さらに、等ディレイ分岐点決定手順は、等ディレイ分岐セグメント決定手順で求められた等ディレイ分岐セグメント中で等ディレイ分岐点Ｑを求める手順である。
また、ディレイ時間決定手順は、等ディレイ分岐点決定手順で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR を求める手順である。
【０１２７】
さらに、第２セグメント分割手順は、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線について、少なくとも２個以上の分割点Ｐ1 ，…，Ｐn+1 を設定することにより、少なくとも３個以上のセグメント４６に分割する手順である。
また、プロパゲーションディレイ時間決定手順は、第２セグメント分割手順で得られた各セグメント４６毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間ｔPQを求める手順である。
【０１２８】
さらに、配線長調整手順は、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕、即ち、ディレイ時間決定手順で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR ，プロパゲーションディレイ時間決定手順で求められた配線のプロパゲーションディレイ時間ｔPQ及びドライバ出力点Ｐでの外部クロックディレイ時間ｔLOADを加算した時間と、設定時間γとを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する手順である。
【０１２９】
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においては、以下のように動作することにより、等ディレイ分岐点Ｑが決定され、等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線長が調整される。
即ち、会話型回路設計装置１においては、第１セグメント分割ステップ（ステップＳ４）により、クロックネット４４における２つのレシーバ間を接続する配線が、少なくとも２個以上の分割点が設定されることにより、少なくとも３個以上のセグメントに分割される。
【０１３０】
続いて、等ディレイ分岐セグメント決定ステップ（ステップＳ５）により、第１セグメント分割ステップ（ステップＳ４）で得られたセグメントについて、等ディレイ分岐点Ｑが存在するセグメントが、等ディレイ分岐セグメントとして決定され、等ディレイ分岐点決定ステップ（ステップＳ６）により、等ディレイ分岐セグメント決定ステップ（ステップＳ５）で求められた等ディレイ分岐セグメント中で等ディレイ分岐点Ｑが決定される。
【０１３１】
また、ディレイ時間決定ステップ（ステップＳ７）により、等ディレイ分岐点決定ステップ（ステップＳ６）で求められた等ディレイ分岐点Ｑから各レシーバへの第５ディレイ時間ｔR が求められる。
さらに、第２セグメント分割ステップ（ステップＳ８）により、図９に示すように、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線が、少なくとも２個以上の分割点（分岐点）Ｐ1 ，…，Ｐn+1 が設定されることにより、少なくとも３個以上のセグメント４６に分割される。
【０１３２】
続いて、プロパゲーションディレイ時間決定ステップ（ステップＳ９）により、第２セグメント分割ステップ（ステップＳ８）で得られた各セグメント４６毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間ｔPQが求められる。
さらに、配線長調整ステップ（ステップＳ１０）により、ドライバ出力点Ｐ（図９，図１０参照）から各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕と、設定時間γとが比較される。
【０１３３】
例えば、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕が、初めから予め設定された時間γを超えている場合〔即ち、Delay （Ｐ→各レシーバ）  ＞  γ  〕には、ドライバ４５Ａやクロック・トリー４５Ｂ（図９，図１０参照）の配置変更が行なわれる。
また、ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕が、予め設定された時間γ未満である場合〔即ち、Delay （Ｐ→各レシーバ）  ＜  γ  〕には、分割点Ｐ1 と分割点Ｐ2 との間に長さｓのセグメントを順次挿入したと仮定しその都度ドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕が計算される。
【０１３４】
このドライバ出力点Ｐから各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕の計算は、当該ディレイ時間が設定値γを超えるまで継続され、その結果、２分法により設定値γとなる分割点Ｐ1 ，Ｐ2 間の配線長Ｌが求められ、これにより等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線長が調整される。
【０１３５】
このように、本発明の一実施形態にかかる会話型回路設計装置１におけるクロックスキューを低減させるための配線処理方法の第２の態様によれば、クロック同期式回路におけるクロック分配回路上の各クロックネット４４において、クロック・トリー４５Ｂにおけるレシーバ間を接続する配線を複数のセグメントに分割して複数のシングルΠ型ＲＣ回路で評価することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮することができるため、レシーバ間を接続する配線における等ディレイ分岐点Ｑを正確に決定することができる。
【０１３６】
また、このとき、分割点を、（１）レシーバ間を接続する配線上の物理的な分岐点，（２）レシーバ間を接続する配線の単位長当たりのインピーダンスが変化する点，（３）セグメントの長さがある決められた長さｓ（任意の定数）を超える点，のいずれかとすることにより、各クロックネット４４の状態に応じた分割点を設定することができ、等ディレイ分岐点Ｑをより正確に決定することができる。
【０１３７】
さらに、図９に示すように、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線を、複数のセグメント４６に分割して複数のシングルΠ型ＲＣ回路で評価することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮することができ、このとき、分割点Ｐ1 ，…，Ｐn+1 を、（１）等ディレイ分岐点Ｑとドライバ出力点Ｐとの間の配線の単位長当たりのインピーダンスが変化する点，（２）セグメント４６の長さがある決められた長さｓ（任意の定数）を超える点のいずれかとすることにより、各クロックネット４４の状態に応じた分割点Ｐ1 ，…，Ｐn+1 を設定することができる。
【０１３８】
また、クロックネット４４において、ドライバ出力点Ｐからクロック・トリー４５Ｂにおける各レシーバまでのディレイ時間〔Delay （Ｐ→各レシーバ）〕と、設定時間とを比較して、この比較結果に基づいて、等ディレイ分岐点Ｑからドライバ出力点Ｐへ至る配線についてセグメント単位で配線長を調整することにより、ドライバ４５Ａに負荷がつくことにより増加する外部クロックディレイ時間を考慮しながら、クロックネット４４におけるドライバ４５Ａからクロック・トリー４５Ｂにおける各レシーバまでのディレイ時間を等しくすることができ、これにより、クロックネット４４のクロック・トリー４５Ｂにおけるクロックスキューを更に効果的に低減させることができる。
（ｂ３）クロックスキューを低減させるための配線処理方法の第３の態様の説明
また、本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させるための配線処理方法の第３の態様について説明する。
【０１３９】
クロックスキューを低減させるための配線処理方法の第３の態様においては、クロック同期式回路におけるクロック分配回路上の各クロックネットにおいて、各レシーバ間を接続する配線における等ディレイ分岐点が予め正確に決定されている場合には、この等ディレイ分岐点とドライバ出力点（外部クロック源取込み部）との間の配線長を調整するだけで、ドライバに負荷がつくことにより増加する外部クロックディレイ時間を考慮しながら、クロックネットにおけるクロックスキューを低減させることができる。
【０１４０】
本態様における配線処理方法は、図１５に示すように、セグメント分割ステップ（ステップＳ１１），プロパゲーションディレイ時間決定ステップ（ステップＳ１２）及び配線長調整ステップ（ステップＳ１３）をそなえて構成されている。
ここで、セグメント分割ステップ（ステップＳ１１）は、等ディレイ分岐点とドライバ出力点との間の配線について、少なくとも２個以上の分割点を設定することにより、少なくとも３個以上のセグメントに分割するステップである。
【０１４１】
このセグメント分割ステップ（ステップＳ１１）は、前述の図１３における第２セグメント分割ステップ（ステップＳ８）と同様のステップである。
また、プロパゲーションディレイ時間決定ステップ（ステップＳ１２）は、セグメント分割ステップ（ステップＳ１１）で得られた各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求めるステップである。
【０１４２】
このプロパゲーションディレイ時間決定ステップ（ステップＳ１２）は、前述の図１３におけるプロパゲーションディレイ時間決定ステップ（ステップＳ９）と同様のステップである。
さらに、配線長調整ステップ（ステップＳ１３）は、プロパゲーションディレイ時間決定ステップ（ステップＳ１２）で求められた配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整するステップである。
【０１４３】
この配線長調整ステップ（ステップＳ１３）は、前述の図１３における配線長調整ステップ（ステップＳ１０）と同様のステップである。
ここで、上述したような各ステップ（ステップＳ１１〜Ｓ１３）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２（図１参照）が、図１６に示すようなセグメント分割処理部Ａ１１，プロパゲーションディレイ時間決定処理部Ａ１２及び配線長調整処理部Ａ１３に相当する機能を有することにより実行される。
【０１４４】
セグメント分割処理部Ａ１１は、クロック同期式回路におけるクロック分配回路上の配線について、少なくとも２個以上の分岐点を設定することにより、少なくとも３個以上のセグメントに分割する処理を行なうものである。
また、プロパゲーションディレイ時間決定処理部Ａ１２は、セグメント分割処理部Ａ１１で得られた各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求める処理を行なうものである。
【０１４５】
さらに、配線長調整処理部Ａ１３は、プロパゲーションディレイ時間決定処理部Ａ１２で求められた配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する処理を行なうものである。
そして、実際には、このような各処理部Ａ１１〜Ａ１３に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
【０１４６】
ここで、本態様における配線処理プログラムは、セグメント分割手順，プロパゲーションディレイ時間決定手順及び配線長調整手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
セグメント分割手順は、クロック同期式回路におけるクロック分配回路上の配線について、少なくとも２個以上の分岐点を設定することにより、少なくとも３個以上のセグメントに分割する手順である。
【０１４７】
また、プロパゲーションディレイ時間決定手順は、セグメント分割手順で得られた各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求める手順である。
さらに、配線長調整手順は、プロパゲーションディレイ時間決定手順で求められた配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する手順である。
【０１４８】
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においても、図１５に示す各ステップ（ステップＳ１１〜Ｓ１３）により、図１３に示す各ステップ（ステップＳ８〜Ｓ１０）と同様の動作が行なわれることにより、等ディレイ分岐点とドライバ出力点との間の配線長が調整される。
このようにしても、クロックネットにおけるドライバから各レシーバまでのディレイ時間を等しくすることができ、ドライバに負荷がつくことにより増加する外部クロックディレイ時間を考慮しながら、クロックネットのクロック・トリーにおけるクロックスキューを効果的に低減させることができる。
【０１４９】
（ｂ４）配線経路を決定するための配線処理方法の第１の態様の説明
さらに、本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、ＬＳＩ上の各回路を接続する際に最適な配線経路を決定するための配線処理方法の第１の態様について説明する。
前述のごとく、ＬＳＩ上の各回路は、自動配線において探索された最適な配線経路により接続される。
【０１５０】
ここで、本態様における配線経路の決定方法について説明する。
本態様における配線経路を決定するための配線処理方法は、図２３に示すように、前方探索処理ステップ（ステップＳ１４）及び後方探索処理ステップ（ステップＳ１６）をそなえて構成されている。
まず、本態様においては、回路基板上の配線についての配線経路を決定するに際し、予め、図１，図２に示す会話型回路計算装置１のハードディスク８か、又は図示しないメモリに、使用可能フラグ，到着状況フラグ及び到着方向フラグが用意される。
【０１５１】
ここで、使用可能フラグは、配線の最小ピッチを単位として、配線領域を格子状に分割し、格子点が配線に使用可能であるかどうかを示すフラグであり、例えば図１８（ｂ）に示すように、格子点が配線に使用可能である場合には“１”が設定され、格子点が配線に使用不可である場合には“０”が設定される。
また、到着状況フラグは、格子点に探索線分が到着したことを示すフラグであり、例えば図１８（ｃ）に示すように、格子点に探索線分が到着した場合には到着済を示す“１”が設定され、格子点に探索線分が到着していない場合には未到着を示す“０”が設定される。
【０１５２】
なお、使用可能フラグ及び到達状況フラグは、配線層毎に各１ビットずつ用意される。
さらに、到着方向フラグは、格子点に探索線分が到着した方向を示すフラグであり、配線層に毎に数ビット用意される。
例えば、１層配線においては、使用可能フラグ及び到達状況フラグが各１ビット用意される。
【０１５３】
また、Ｘ軸を水平方向，Ｙ軸を垂直方向と定義すると、到着方向フラグとしては、到達方向がＸ軸方向かＹ軸方向かを示すＸＹ方向フラグ〔例えば図１８（ｄ）参照〕が１ビット用意されるとともに、到達方向が正方向が負方向かを示す正負方向フラグ〔例えば図１８（ｅ）参照〕が１ビット用意される。
なお、ＸＹ方向フラグは、例えば図１８（ｄ）に示すように、到達方向がＸ軸方向である場合には“１”が設定され、到達方向がＹ軸方向である場合には“０”が設定される。
【０１５４】
また、正負方向フラグは、例えば図１８（ｅ）に示すように、到達方向が正方向である場合には“１”が設定され、到達方向が負方向である場合には“０”が設定される。
ここで、上述した使用可能フラグ，到着状況フラグ及び到着方向フラグは、後述にて詳述する前方探索処理ステップ（ステップＳ１４）における線分探索のための演算を並列処理にて行なうために、例えば図１７に示すように、メモリ等におけるバイトアドレス及びビット数がそのまま格子点の座標を表すようなテーブル形式により構成されている。
【０１５５】
即ち、本態様においては、前方探索処理ステップ（ステップＳ１４）における線分探索のための演算を並列的に行なえるようにするために、各格子点を１ビットで表わし、各フラグを図１７に示すような形式にて構成している。
ここで、図１７に示すテーブル５２は、当該演算をＹ軸方向に対して１ワードずつ並列処理（図１７に示す例では並列度８）にて行なえるように構成されている。
【０１５６】
なお、図１７に示すテーブル５２をＸ軸とＹ軸とを入れ換えた形式により構成して、このようなテーブルにより各フラグを保持すれば、当該演算をＸ軸方向に対して１ワードずつ並列処理にて行なえるようにすることもできる。
本態様における配線処理方法について説明すると、前方探索処理ステップ（ステップＳ１４）は、隣接格子点フラグ処理手順Ｓ１５を並列的に実行するステップである。
【０１５７】
ここで、隣接格子点フラグ処理手順Ｓ１５は、到着状況フラグが“１”である格子点に隣接する隣接格子点について、使用可能フラグが“１”であり、且つ、到着状況フラグが“０”である場合に、隣接格子点の到着状況フラグを“１”にするような演算を行なうともに、隣接格子点の到着方向フラグにその探索方向を表示させる（即ち、その探索方向に応じて、ＸＹ方向フラグ及び正負方向フラグを“１”又は“０”に設定する）ような処理手順である。
【０１５８】
さらに、この前方探索処理ステップ（ステップＳ１４）は、この隣接格子点フラグ処理手順Ｓ１５を、各探索線分について、到着状況フラグが“１”である格子点がなくなるまで、繰り返して実行することにより、順次線分を発生させていくステップである。
また、後方探索処理ステップ（ステップＳ１６）は、前方探索処理ステップ（ステップＳ１４）において、探索の終了点を示す格子点の到着状況フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、探索の終了点を示す格子点から探索の開始点を示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、最適な配線経路を検索するステップである。
【０１５９】
ここで、上述したような各ステップ（ステップＳ１４，Ｓ１６）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２（図１参照）が、図２４に示すような前方探索処理部Ａ１４及び後方探索処理部Ａ１６に相当する機能を有することにより実行される。
前方探索処理部Ａ１４は、隣接格子点フラグ処理部Ａ１５をそなえ、この隣接格子点フラグ処理部Ａ１５により、前述した隣接格子点フラグ処理手順Ｓ１５を並列的に実行するものであり、更に、この隣接格子点フラグ処理手順Ｓ１５を、各探索線分について、到着状況フラグが“１”である格子点がなくなるまで、繰り返して実行することにより、順次線分を発生させていく前方探索処理を行なうものである。
【０１６０】
また、後方探索処理部Ａ１６は、前方探索処理部Ａ１４において探索の終了点を示す格子点の到着状況フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、探索の終了点を示す格子点から探索の開始点を示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、最適な配線経路を検索する後方探索処理を行なうものである。
【０１６１】
そして、実際には、このような各処理部Ａ１４，Ａ１６に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
ここで、本態様における配線処理プログラムは、前方探索処理手順及び後方探索処理手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
【０１６２】
前方探索処理手順は、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた格子点に探索線分が到着したことを示す到着状況フラグが“１”である格子点に隣接する隣接格子点について、格子点が配線に使用可能であるかどうかを示す使用可能フラグが“１”であり、且つ、到着状況フラグが“０”である場合に、隣接格子点の到着状況フラグを“１”にするような演算を行なうともに、隣接格子点において、隣接格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を表示させる（即ち、その探索方向に応じて、ＸＹ方向フラグ及び正負方向フラグを“１”又は“０”に設定する）隣接格子点フラグ処理手順Ｓ１５（図２３参照）を並列的に実行する手順であり、更にこの隣接格子点フラグ処理手順を、各探索線分について、到着状況フラグが“１”である格子点がなくなるまで、繰り返して実行することにより、順次線分を発生させていく手順である。
【０１６３】
また、後方探索処理手順は、前方探索処理手順において探索の終了点を示す格子点の到着状況フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、探索の終了点を示す格子点から探索の開始点を示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、最適な配線経路を検索する手順である。
【０１６４】
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においては、以下のように動作することにより、配線経路が検索され、最適な配線経路が決定される。
以下では、図１８（ａ）に示すような回路基板上の配線についての配線経路を決定する場合について説明する。
【０１６５】
ここで、図１８（ａ）は、回路基板の初期状態（配線経路の決定前の状態）を示す図であり、この図１８（ａ）においては、探索の開始点をＳで示すとともに、探索の終了点をＴで示している。なお、図１８（ａ）においては、各回路の存在等による回路基板上の配線禁止領域を実線で示している。
この図１８（ａ）に示す回路基板の初期状態時の使用可能フラグ，到達状況フラグ，ＸＹ方向フラグ及び正負方向フラグを、それぞれ図１８（ｂ）〜図１８（ｅ）に示す。
【０１６６】
なお、図１８（ｂ）〜図１８（ｅ）においては、フラグが“１”である格子点を網かけで示す。図１８（ｂ）に示すように、初期状態時には、開始点Ｓの到達状況フラグが“１”にされている。
会話型回路設計装置１においては、まず、前方探索処理ステップ（ステップＳ１４）により、到達状況フラグが“１”である格子点に対し、その格子点の探索方向に隣接する格子点の使用可能フラグが“１”であり到達状況フラグが“０”である場合には、隣接格子点の到達状況フラグが“１”に設定されるとともに探索方向が到達方向フラグに記録される。
【０１６７】
前方探索処理ステップ（ステップＳ１４）においては、上述の動作が、各探索線分について到達状況フラグが“１”になる格子点がなくなるまで行なわれる。
即ち、図１８（ａ）に示すような回路基板上の配線についての配線経路を決定する際には、図１９（ａ）に示すように、まず、演算により開始点ＳからＸ軸方向に検索線分を発生する（検索レベル１）。なお、このときの使用可能フラグ，到達状況フラグ，ＸＹ方向フラグ及び正負方向フラグは、それぞれ図１９（ｂ）〜図１９（ｅ）に示すようになる。
【０１６８】
続いて、図２０（ａ）に示すように、上述の検索レベル１で発生した検索線分から、Ｙ軸方向に検索線分を発生する（検索レベル２）。この検索レベル２や以下の検索レベル（検索レベル３，４）において、各検索線分の発生を並列的に行なうようにすれば、処理速度を向上させることができる。なお、このときの使用可能フラグ，到達状況フラグ，ＸＹ方向フラグ及び正負方向フラグは、それぞれ図２０（ｂ）〜図２０（ｅ）に示すようになる。
【０１６９】
さらに、図２１（ａ）に示すように、上述の検索レベル２で発生した検索線分から、Ｘ軸方向に検索線分を発生する（検索レベル３）。なお、このときの使用可能フラグ，到達状況フラグ，ＸＹ方向フラグ及び正負方向フラグは、それぞれ図２１（ｂ）〜図２１（ｅ）に示すようになる。
また、図２２（ａ）に示すように、上述の検索レベル３で発生した検索線分から、Ｙ軸方向に検索線分を発生する（検索レベル４）。なお、このときの使用可能フラグ，到達状況フラグ，ＸＹ方向フラグ及び正負方向フラグは、それぞれ図２２（ｂ）〜図２２（ｅ）に示すようになる。
【０１７０】
そして、検索線分が終了点Ｔに到達した後、後方探索処理ステップ（ステップＳ１６）により、図２２（ｆ）に示すように、終了点Ｔから開始点Ｓまで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、最適な配線経路を決定することができる。
このように、本発明の一実施形態にかかる会話型回路設計装置１における配線経路を決定するための配線処理方法の第１の態様によれば、各格子点の使用可能フラグ，到着状況フラグ及び到着方向フラグを、例えば図１７に示すように、メモリ等におけるバイトアドレス及びビット数がそのまま格子点の座標を表すように構成することにより、前方探索処理ステップ（ステップＳ１４）における演算を並列処理にて高速に行なうことができるようになるため、配線経路の探索に要する時間を大幅に短縮することができる。
【０１７１】
（ｂ５）配線経路を決定するための配線処理方法の第２の態様の説明
続いて、本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、ＬＳＩ上の各回路を接続する際に最適な配線経路を決定するための配線処理方法の第２の態様について説明する。
ここで、本態様における配線経路を決定するための配線処理方法は、図２７に示すように、前方探索処理ステップ（ステップＳ１７），後方探索処理ステップ（ステップＳ１８）及び最適配線経路決定ステップ（ステップＳ１９）をそなえて構成されている。
【０１７２】
まず、本態様においては、回路基板上の配線についての配線経路を決定するに際し、予め、図１，図２に示す会話型回路計算装置１のハードディスク８か、又は図示しないメモリに、到着方向フラグが用意される。
ここで、到着方向フラグは、配線の最小ピッチを単位として、配線領域を格子状に分割し、格子点に探索線分が到着した方向を示すフラグである。
【０１７３】
この到着方向フラグとしては、各方向毎に、各格子点について探索線分が到達したことを“１”で示すフラグが１ビットずつ用意される。
例えば、１層配線においては、Ｘ軸を水平方向にＹ軸を垂直方向に定義し、Ｘ軸の正方向，Ｘ軸の負方向，Ｙ軸の正方向，Ｙ軸の負方向の各々についてフラグが用意される。
【０１７４】
ここで、複数の配線経路の探索が許されない場合には、配線経路として、先に検索された配線経路〔例えば図２５（ａ）に示す例では、終了点Ｔの左側から到達した配線経路〕が選択されるため、図２５（ｂ）に示すように、最適ではない配線経路が選択される可能性がある。
このため、本実施形態においては、配線経路として、例えば図２６（ａ）に示すように複数の配線経路を探索して、複数の配線経路の中から最適な配線経路〔例えば図２６（ｂ）に示す例では、配線長が最短となる配線経路〕を選択できるようにするために、到着方向フラグを、各方向から探索線分が到達したことを示す４種類のフラグにより構成している。
【０１７５】
ここで、前方探索処理ステップ（ステップＳ１７）は、例えば図２６（ａ）に示すような回路基板上の配線についての配線経路を決定する際に、各格子点について、到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていくステップである。
即ち、前方探索処理ステップ（ステップＳ１７）においては、各格子点について、複数の方向から探索線分が到達した場合には、その方向に対応する到着方向フラグが“１”に設定される。
【０１７６】
また、後方探索処理ステップ（ステップＳ１８）は、前方探索処理ステップ（ステップＳ１７）において探索の終了点を示す格子点の到着方向フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、例えば図２６（ａ）に示すように、探索の終了点Ｔを示す格子点から探索の開始点Ｓを示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、複数の配線経路〔図２６（ａ）では４通りの配線経路〕を検索するステップである。
【０１７７】
さらに、最適配線経路決定ステップ（ステップＳ１９）は、後方探索処理ステップ（ステップＳ１８）で得られた複数の配線経路の配線長又は配線コストを求めることにより、例えば図２６（ｂ）に示すように、最適な配線経路を決定するステップである。
具体的には、この最適配線経路決定ステップ（ステップＳ１９）においては、配線長又は配線コストが最小である配線経路が最適な配線経路であると決定される。
【０１７８】
ここで、上述したような各ステップ（ステップＳ１７〜Ｓ１９）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２（図１参照）が、図２８に示すような前方探索処理部Ａ１７，後方探索処理部Ａ１８及び最適配線経路決定処理部Ａ１９に相当する機能を有することにより実行される。
前方探索処理部Ａ１７は、例えば図２６（ａ）に示すような回路基板上の配線についての配線経路を決定する際に、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なうものである。
【０１７９】
また、後方探索処理部Ａ１８は、前方探索処理部Ａ１７において探索の終了点を示す格子点の到着方向フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、例えば図２６（ａ）に示すように、探索の終了点Ｔを示す格子点から探索の開始点Ｓを示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、複数の配線経路〔図２６（ａ）では４通りの配線経路〕を検索する処理を行なうものである。
【０１８０】
さらに、最適配線経路決定処理部Ａ１９は、後方探索処理部Ａ１８で得られた複数の配線経路の配線長又は配線コストを求めることにより、例えば図２６（ｂ）に示すように、配線長又は配線コストが最小である配線経路を最適な配線経路として決定する処理を行なうものである。
そして、実際には、このような各処理部Ａ１７〜Ａ１９に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
【０１８１】
ここで、本態様における配線処理プログラムは、前方探索処理手順，後方探索処理手順及び最適配線経路決定手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
前方探索処理手順は、例えば図２６（ａ）に示すような回路基板上の配線についての配線経路を決定する際に、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく手順である。
【０１８２】
また、後方探索処理手順は、前方探索処理手順において探索の終了点を示す格子点の到着方向フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、例えば図２６（ａ）に示すように、探索の終了点Ｔを示す格子点から探索の開始点Ｓを示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、複数の配線経路〔図２６（ａ）では４通りの配線経路〕を検索する手順である。
【０１８３】
さらに、最適配線経路決定手順は、後方探索処理手順で得られた複数の配線経路の配線長又は配線コストを求めることにより、例えば図２６（ｂ）に示すように、配線長又は配線コストが最小である配線経路を最適な配線経路として決定する手順である。
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においては、以下のように動作することにより、配線経路が検索され、最適な配線経路が決定される。
【０１８４】
会話型回路設計装置１においては、まず、前方探索処理ステップ（ステップＳ１７）により、各格子点について、複数の方向から探索線分が到達した場合には、その方向に対応する到着方向フラグが“１”に設定されながら、前方探索が行なわれる。
そして、前方探索処理ステップ（ステップＳ１７）において探索の終了点を示す格子点の到着方向フラグが“１”となった後に（即ち探索線分が終了点まで到達した後に）、後方探索処理ステップ（ステップＳ１８）により、例えば図２６（ａ）に示すように、探索の終了点Ｔを示す格子点から探索の開始点Ｓを示す格子点まで、到着方向フラグに従って配線経路をさかのぼって逆探索することにより、複数の配線経路が検索される。
【０１８５】
例えば、図２６（ａ）に示すような回路基板上の配線についての配線経路を決定する際には、後方探索処理ステップ（ステップＳ１８）においては、到着方向フラグに従って配線経路を逆探索することにより、４通りの配線経路が検索される。
さらに、後方探索処理ステップ（ステップＳ１８）において、複数の配線経路が検索されると、最適配線経路決定ステップ（ステップＳ１９）により、この複数の配線経路から、例えば図２６（ｂ）に示すように、最適な配線経路が決定される。
【０１８６】
例えば、図２６（ａ）に示すような回路基板上の配線についての配線経路を決定する際には、最適配線経路決定ステップ（ステップＳ１９）においては、後方探索処理ステップ（ステップＳ１８）で得られた各々の配線経路について、配線長を求めることにより配線長が最短である配線経路が決定される。
このように、本発明の一実施形態にかかる会話型回路設計装置１における配線経路を決定するための配線処理方法の第２の態様によれば、到着方向フラグが、格子点に探索線分が到着した方向を示すように構成される（具体的には、到着方向フラグが格子点に対して各方向から探索線分が到達したことを示す４種類のフラグにより構成される）ことにより、配線経路として複数の配線経路を探索してその中から最適な配線経路を選択することができるため、配線長を最小化して配線性を向上させることが可能となる。
【０１８７】
なお、配線領域を小領域に分割した場合の各分割領域の配線混雑度，複数の配線層をもつ場合の各配線層のディレイ値等に基づいて、各格子点毎に配線コストを設定すれば、上述した最適配線経路決定ステップ（ステップＳ１９）において、配線性や回路の性能まで考慮した最適の経路を決定することができる。
（ｂ６）配線経路を決定するための配線処理方法の第３の態様の説明
さらに、本発明の一実施形態にかかる会話型回路設計装置１における配線処理方法として、ＬＳＩ上の各回路を接続する際に最適な配線経路を決定するための配線処理方法の第３の態様について説明する。
【０１８８】
ここで、本態様においては、最適な配線経路を決定するために、各回路の配置終了段階において、配線を行なう前に配線可能性として配線混雑度を見積もり、この配線混雑度による評価に応じて、回路配置の修正を適宜行なう方法について説明する。
本態様における配線経路を決定するための配線処理方法は、図３０に示すように、回路配置決定ステップ（ステップＳ２０），配線混雑度評価ステップ（ステップＳ２１）及び回路配置修正ステップ（ステップＳ２２）をそなえて構成されている。
【０１８９】
ここで、回路配置決定ステップ（ステップＳ２０）は、回路基板上の回路についての配置を決定するステップである。この回路配置決定ステップ（ステップＳ２０）においては、従来よりの方法等により回路基板上の回路についての配置が決定される。
また、配線混雑度評価ステップ（ステップＳ２１）は、回路配置決定ステップ（ステップＳ２０）にて、回路についての配置を決定した後に、回路を接続する配線についての配線混雑度を求めることにより、回路配置決定ステップ（ステップＳ２０）にて決定された回路配置についての評価を行なうステップである。
【０１９０】
ここで、配線混雑度評価ステップ（ステップＳ２１）における配線混雑度評価方法について説明する。
まず、図２９に示すような配線により構成されるネットが、配線領域における点を占有する確率について考える。
ネットが配線領域における点を占有する確率は、配線されるネットの端子（図２９では端子を●で示す）を包含する最小矩形の面積Ｓ，ネットの論長ｌを用いて表現することができる。
【０１９１】
即ち、面積Ｓi の矩形内の点を、論長ｌi のネットｉが占める確率ｐi は、
ｐi ＝ｌi ／Ｓi 
であると仮定する。
ここで、各ネットの論長ｌi を合計したものを総配線長Ｌとすると、総配線長Ｌは次式のように定義される。
【０１９２】
【数１７】
0004268694.tif 000015
一方で、各ネットの重複（重なり）を許した場合の配線に使用される点の数Ｇは、「１つのネットだけが点を使用する確率」＋「２つのネットだけが点を使用する確率」＋「３つのネットだけが点を使用する確率」＋…＋「全ネットが点を使用する確率」を、全配線領域に包含される点について合計することで計算できる。
【０１９３】
ここで、「１つのネットだけが点を使用する確率」は、次式により求めることができる。
【０１９４】
【数１８】
0004268694.tif 000016
また、「２つのネットだけが点を使用する確率」は、次式により求めることができる。
【０１９５】
【数１９】
0004268694.tif 000017
以下、同様にして、「ｎのネットだけが点を使用する確率」は、
【０１９６】
【数２０】
0004268694.tif 000018
により求めることができる。ここで、論長ｌi のネットｉが占める確率ｐi は、１と比較して小さい値であると考えられ、ｎが大きくなるに従って「ｎのネットだけが点を使用する確率」は急速に収束するものと考えられる。
【０１９７】
このため、適当なネット数までの値を用いることにより、使用される点の数Ｇを近似することができる。
ところで、総配線長Ｌが等しければ、使用される点の数Ｇが少ない方が配線混雑度が大きいと考えることができることから、配線混雑度の評価値として、
（Ｌ−Ｇ）／Ｌ
を考える。
【０１９８】
また、総配線長Ｌは、
Ｌ＝１×「１つのネットだけが点を使用する確率」＋…＋「全ネット数」×「全ネットが点を使用する確率」
とも表現することができるため、上記の式を使用して、論長ｌi のネットｉが占める確率ｐi が４つ以上積算される項を無視して計算すると、
Ｌ−Ｇ＝Σ〔（１／２）Ｔ12＋（１／２）Ｔ1 Ｔ2 −（１／２）Ｔ2 −（１／６）Ｔ13−（１／３）Ｔ3 〕
（Σは配線領域の全点における和）
但し、Ｔ1 ＝Σｐi ，Ｔ2 ＝Σ（ｐi 2 ），Ｔ3 ＝Σ（ｐi 3 ）
となる。
【０１９９】
これにより、各ネットのある点を占める確率の積の和を用いて、（Ｌ−Ｇ）を計算することができる。
以上より、配線可能性をはかる配線混雑度を評価する値として、（Ｌ−Ｇ）／Ｌが計算される。
このように、配線混雑度評価ステップ（ステップＳ２１）においては、回路配置決定ステップ（ステップＳ２０）にて回路についての配置を決定した後に、回路を接続する配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価することにより、回路配置決定ステップ（ステップＳ２０）にて決定された回路配置についての評価が行なわれるのである。
【０２００】
ところで、回路配置修正ステップ（ステップＳ２２）は、配線混雑度評価ステップ（ステップＳ２１）にて配線混雑度を求めて回路配置についての評価を行なった後に、配線混雑度による評価に応じて回路配置を修正することにより、各回路の配置の改善や配線領域の最適化を行なうステップである。この回路配置修正ステップ（ステップＳ２２）においては、従来よりの方法等により各回路の配置の改善や配線領域の最適化が行なわれる。
【０２０１】
なお、会話型回路設計装置１においては、回路配置修正ステップ（ステップＳ２２）により、回路配置が適宜修正された後に、最適な配線経路での配線処理が行なわれるようになっている。
ここで、上述したような各ステップ（ステップＳ２０〜Ｓ２２）からなる配線処理方法は、会話型回路設計装置１のＣＰＵ２（図１参照）が、図３１に示すような回路配置決定処理部Ａ２０，配線混雑度評価処理部Ａ２１及び回路配置修正処理部Ａ２２に相当する機能を有することにより実行される。
【０２０２】
回路配置決定処理部Ａ２０は、回路基板上の回路についての配置を決定する処理を行なうものである。
また、配線混雑度評価処理部Ａ２１は、回路配置決定処理部Ａ２０にて回路についての配置を決定した後に、回路を接続する配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価することにより、回路配置決定処理部Ａ２０にて決定された回路配置についての評価する処理を行なうものである。
【０２０３】
さらに、回路配置修正処理部Ａ２２は、配線混雑度評価処理部Ａ２１にて配線混雑度を求めて回路配置についての評価を行なった後に、配線混雑度による評価に応じて回路配置を修正することにより、各回路の配置の改善や配線領域の最適化を行なうものである。
そして、実際には、このような各処理部Ａ２０〜Ａ２２に相当する機能は、後述するような各手順を、会話型回路設計装置１のＣＰＵ２に実行させるための配線処理プログラムをハードディスク８に格納することにより実現することができる。
【０２０４】
ここで、本態様における配線処理プログラムは、回路配置決定手順，配線混雑度評価手順及び回路配置修正手順を、会話型回路設計装置１に実行させるためのソフトウェアである。
回路配置決定手順は、回路基板上の回路についての配置を決定する手順である。
【０２０５】
また、配線混雑度評価手順は、回路配置決定手順にて回路についての配置を決定した後に、回路を接続する配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価することにより、回路配置決定手順にて決定された回路配置についての評価を行なう手順である。
【０２０６】
さらに、回路配置修正手順は、配線混雑度評価手順にて配線混雑度を求めて回路配置についての評価を行なった後に、配線混雑度による評価に応じて回路配置を修正することにより、各回路の配置の改善や配線領域の最適化を行なう手順である。
上述の構成により、本発明の一実施形態にかかる会話型回路設計装置１においては、以下のように動作することにより、回路配置が決定され、その決定された回路配置が配線混雑度により評価され、配線混雑度による評価に応じて回路配置が修正される。
【０２０７】
会話型回路設計装置１においては、まず、回路配置決定ステップ（ステップＳ２０）により、回路基板上の回路についての配置が決定される。
続いて、回路配置決定ステップ（ステップＳ２０）にて、回路についての配置が決定されると、配線混雑度評価ステップ（ステップＳ２１）により、回路を接続する配線についての配線混雑度が求められ、この配線混雑度に基づいて、回路配置決定ステップ（ステップＳ２０）にて決定された回路配置についての評価が行なわれる。
【０２０８】
さらに、配線混雑度評価ステップ（ステップＳ２１）での配線混雑度による評価に応じて、回路配置修正ステップ（ステップＳ２２）により、回路配置の修正が適宜行なわれる。
そして、会話型回路設計装置１においては、回路配置修正ステップ（ステップＳ２２）により、回路配置が適宜修正された後に、最適な配線経路での配線処理が行なわれる。
【０２０９】
このように、本発明の一実施形態にかかる会話型回路設計装置１における配線経路を決定するための配線処理方法の第３の態様によれば、各回路の配置終了段階において、配線を行なう前に配線可能性として配線混雑度を見積もり、この配線混雑度による評価に応じて回路配置の修正を適宜行なうことにより、最適な配線経路を決定することができる。
【０２１０】
また、この配線混雑度を評価する値（Ｌ−Ｇ）／Ｌを算出することにより、各回路の配置終了段階において、配線を行なう前に配線可能性を見積もることができるため、配線対象の巨大化に伴い要求されている早い段階での配線可能性の算出及び評価が可能となる。
さらに、この配線混雑度を評価する値（Ｌ−Ｇ）／Ｌに基づいて、回路配置の修正を行なうことにより、配線領域の最適化を適切に行なうことができる。
【０２１１】
【発明の効果】
以上詳述したように、本発明の配線処理方法によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、３個以上のセグメントに分割して等ディレイ分岐点を求めることにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項１〜４）。
【０２１２】
また、本発明の配線処理方法によれば、クロック同期式回路におけるクロック分配回路上の配線について、３個以上のセグメントに分割してセグメント単位で配線長を調整することにより、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項５）。
【０２１３】
さらに、本発明の配線処理方法によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、３個以上のセグメントに分割して等ディレイ分岐点を求めるとともに、この等ディレイ分岐点から外部クロック源取込み部へ至る配線について、３個以上のセグメントに分割してセグメント単位で配線長を調整することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができるとともに、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを効果的に低減させることができる利点がある（請求項６，７）。
【０２１４】
また、本発明に関連する配線処理方法によれば、回路基板上の配線についての配線経路を決定するに際し、予め使用可能フラグ，到着状況フラグ及び到着方向フラグを用意した状態で、到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、使用可能フラグが使用可能状態を示しており、且つ、到着状況フラグが探索線分未到着を示している場合に、隣接格子点の到着状況フラグを探索線分到着を示す状態にするともに、隣接格子点の到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行することにより、前方探索処理ステップにおける演算を並列処理にて高速に行なうことができるため、配線経路の探索に要する時間を大幅に短縮することができる利点がある。
【０２１５】
さらに、本発明に関連する配線処理方法によれば、回路基板上の配線についての配線経路を決定するに際し、予め到着方向フラグを用意した状態で、各格子点について、到着方向フラグにその探索方向を複数表示させることにより、配線経路として複数の配線経路を探索してその中から最適な配線経路を選択することができるため、配線長を最小化して配線性を向上させることができる利点がある。
【０２１６】
また、本発明に関連する配線処理方法によれば、回路についての配置を決定した後に、回路を接続する配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価する配線混雑度評価ステップとそなえて構成されることにより、各回路の配置終了段階において、配線を行なう前に配線可能性として配線混雑度を見積もることができるため、配線対象の巨大化に伴い要求されている早い段階での配線可能性の算出及び評価が可能となる利点がある。
【０２１７】
さらに、本発明の配線処理装置によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、等ディレイ分岐点が存在する等ディレイ分岐セグメントを決定する等ディレイ分岐セグメント決定処理部と、等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部とをそなえて構成されることにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項８）。
【０２１８】
また、本発明の配線処理装置によれば、クロック同期式回路におけるクロック分配回路上の配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割するセグメント分割処理部と、各セグメント毎のディレイ時間を考慮した該配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成されることにより、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項９）。
【０２１９】
さらに、本発明の配線処理装置によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第１セグメント分割処理部と、等ディレイ分岐点が存在する等ディレイ分岐セグメントを決定する等ディレイ分岐セグメント決定処理部と、等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定処理部と、等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定処理部と、等ディレイ分岐点から外部クロック源取込み部へ至る配線について、２個以上の分岐点を設定することにより、３個以上のセグメントに分割する第２セグメント分割処理部と、各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定処理部と、等ディレイ分岐点から各レシーバへの第５ディレイ時間と配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整処理部とをそなえて構成されることにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができるとともに、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを効果的に低減させることができる利点がある（請求項１０）。
【０２２０】
また、本発明に関連する配線処理装置によれば、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた格子点に探索線分が到着したことを示す到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、格子点が配線に使用可能であるかどうかを示す使用可能フラグが使用可能状態を示しており、且つ、到着状況フラグが探索線分未到着を示している場合に、隣接格子点の到着状況フラグを探索線分到着を示す状態にするともに、隣接格子点において、隣接格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行し、更に隣接格子点フラグ処理手順を、各探索線分について、到着状況フラグを探索線分到着を示す状態にするような格子点がなくなるまで、繰り返して実行する前方探索処理を行なう前方探索処理部と、前方探索処理の後に、所望の格子点から到着方向フラグに従って、配線経路をさかのぼっていくことにより、配線経路を検索する後方探索処理を行なう後方探索処理部とをそなえて構成されることにより、前方探索処理における演算を並列処理にて高速に行なうことができるため、配線経路の探索に要する時間を大幅に短縮することができる利点がある。
【０２２１】
さらに、本発明に関連する配線処理装置によれば、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく前方探索処理部と、前方探索の後に、所望の格子点から該到着方向フラグに従って、配線経路をさかのぼっていくことにより、複数の配線経路を検索する後方探索処理部と、複数の配線経路から最適な配線経路を決定する最適配線経路決定処理部とをそなえて構成されることにより、配線経路として複数の配線経路を探索してその中から最適な配線経路を選択することができるため、配線長を最小化して配線性を向上させることができる利点がある。
【０２２２】
また、本発明に関連する配線処理装置によれば、回路基板上の回路についての配置を決定する回路配置決定処理部と、回路についての配置を決定した後に、回路を接続する配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価する配線混雑度評価処理部とをそなえて構成されることにより、各回路の配置終了段階において、配線を行なう前に配線可能性として配線混雑度を見積もることができるため、配線対象の巨大化に伴い要求されている早い段階での配線可能性の算出及び評価が可能となる利点がある。
【０２２３】
さらに、本発明の配線処理プログラム用記録媒体によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、３個以上のセグメントに分割するセグメント分割手順と、等ディレイ分岐点が存在する等ディレイ分岐セグメントを決定する等ディレイ分岐セグメント決定手順と、等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順とを、コンピュータに実行させるための配線処理プログラムを記録することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項１１）。
【０２２４】
また、本発明の配線処理プログラム用記録媒体によれば、クロック同期式回路におけるクロック分配回路上の配線について、３個以上のセグメントに分割するセグメント分割手順と、各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、配線のプロパゲーションディレイ時間と設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させるための配線処理プログラムを記録することにより、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを低減させることができる利点がある（請求項１２）。
【０２２５】
さらに、本発明の配線処理プログラム用記録媒体によれば、クロック同期式回路におけるクロック分配回路上のクロックネットにおける２つのレシーバ間を接続する配線について、３個以上のセグメントに分割する第１セグメント分割手順と、等ディレイ分岐点が存在する等ディレイ分岐セグメントを決定する等ディレイ分岐セグメント決定手順と、等ディレイ分岐セグメント中で等ディレイ分岐点を求める等ディレイ分岐点決定手順と、等ディレイ分岐点から各レシーバへの第５ディレイ時間を求めるディレイ時間決定手順と、等ディレイ分岐点から外部クロック源取込み部へ至る配線について、３個以上のセグメントに分割する第２セグメント分割手順と、各セグメント毎のディレイ時間を考慮した配線のプロパゲーションディレイ時間を求めるプロパゲーションディレイ時間決定手順と、等ディレイ分岐点から各レシーバへの第５ディレイ時間と配線のプロパゲーションディレイ時間とを加算した時間と、設定時間とを比較して、この比較結果に基づいて、セグメント単位で配線長を調整する配線長調整手順とを、コンピュータに実行させるための配線処理プログラムを記録することにより、配線における単位グリッド当たりの抵抗及び容量が場所によらず等しくないことを考慮して等ディレイ分岐点を正確に決定することができるとともに、外部クロックディレイ時間を考慮して各レシーバまでのディレイ時間を等しくすることができ、これにより、クロック同期式回路におけるクロックの伝搬遅延時間（ディレイ時間）の差分であるクロックスキューを効果的に低減させることができる利点がある（請求項１３）。
【０２２６】
また、本発明に関連する配線処理プログラム用記録媒体によれば、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた格子点に探索線分が到着したことを示す到着状況フラグが探索線分到着を示している格子点に隣接する隣接格子点について、格子点が配線に使用可能であるかどうかを示す使用可能フラグが使用可能状態を示しており、且つ、到着状況フラグが探索線分未到着を示している場合に、隣接格子点の到着状況フラグを探索線分到着を示す状態にするともに、隣接格子点において、隣接格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を表示させる隣接格子点フラグ処理手順を並列的に実行し、更に隣接格子点フラグ処理手順を、各探索線分について、到着状況フラグを探索線分到着を示す状態にするような格子点がなくなるまで、繰り返して実行する前方探索処理手順と、前方探索処理手順の後に、所望の格子点から到着方向フラグに従って、配線経路をさかのぼっていくことにより、配線経路を検索する後方探索処理手順とを、コンピュータに実行させるための配線処理プログラムを記録することにより、前方探索処理手順における演算を並列処理にて高速に行なうことができるため、配線経路の探索に要する時間を大幅に短縮することができる利点がある。
【０２２７】
さらに、本発明に関連する配線処理プログラム用記録媒体によれば、回路基板上の配線の最小ピッチを単位とし配線領域を格子状に分割して得られた各格子点について、格子点に探索線分が到着した方向を示す到着方向フラグにその探索方向を複数表示させながら、前方探索を行なっていく前方探索処理手順と、前方探索処理手順の後に、所望の格子点から到着方向フラグに従って、配線経路をさかのぼっていくことにより、複数の配線経路を検索する後方探索処理手順と、後方探索処理手順で得られた複数の配線経路から最適な配線経路を決定する最適配線経路決定手順とを、コンピュータに実行させるための配線処理プログラムを記録することにより、配線経路として複数の配線経路を探索してその中から最適な配線経路を選択することができるため、配線長を最小化して配線性を向上させることができる利点がある。
【０２２８】
また、本発明に関連する配線処理プログラム用記録媒体によれば、回路基板上の配線の総配線長をＬとし、配線に使用される点の数をＧとして、（Ｌ−Ｇ）／Ｌを配線についての配線混雑度として評価する配線混雑度評価手順をコンピュータに実行させるための配線処理プログラムを記録することにより、各回路の配置終了段階において、配線を行なう前に配線可能性として配線混雑度を見積もることができるため、配線対象の巨大化に伴い要求されている早い段階での配線可能性の算出及び評価が可能となる利点がある。
【図面の簡単な説明】
【図１】本発明の一実施形態にかかる会話型回路設計装置の構成を示すブロック図である。
【図２】本発明の一実施形態にかかる会話型回路設計装置の全体構成を示す図である。
【図３】本発明のクロックスキューを低減させるための配線処理方法の第１の態様におけるバッファ付きクロック・トリーをモデル化して示す図である。
【図４】本発明のクロックスキューを低減させるための配線処理方法の第１の態様におけるバッファ付きクロック・トリーの要部構成を示す図である。
【図５】本発明のクロックスキューを低減させるための配線処理方法の第１の態様におけるクロック分配回路上のクロックネットのクロック・トリーの構成を模式的に示す図である。
【図６】本発明のクロックスキューを低減させるための配線処理方法の第１の態様におけるクロック分配回路上のクロックネットのクロック・トリーの構成を模式的に示す図である。
【図７】本発明のクロックスキューを低減させるための配線処理方法の第１の態様を説明するためのフローチャートである。
【図８】本発明のクロックスキューを低減させるための配線処理装置の第１の態様を説明するための機能ブロック図である。
【図９】本発明のクロックスキューを低減させるための配線処理方法の第２の態様におけるクロック分配回路上のクロックネットの構成を模式的に示す図である。
【図１０】本発明のクロックスキューを低減させるための配線処理方法の第２の態様におけるクロック分配回路上のクロックネットの構成を模式的に示す図である。
【図１１】アドミッタンス算出用のｙ１，ｙ２，ｙ３の算出方法を説明するための図である。
【図１２】外部クロックディレイ時間を説明するための図である。
【図１３】本発明のクロックスキューを低減させるための配線処理方法の第２の態様を説明するためのフローチャートである。
【図１４】本発明のクロックスキューを低減させるための配線処理装置の第２の態様を説明するための機能ブロック図である。
【図１５】本発明のクロックスキューを低減させるための配線処理方法の第３の態様を説明するためのフローチャートである。
【図１６】本発明のクロックスキューを低減させるための配線処理装置の第３の態様を説明するための機能ブロック図である。
【図１７】使用可能フラグ，到着状況フラグ及び到着方向フラグの構成を説明するための図である。
【図１８】（ａ）〜（ｅ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第１の態様を説明するための図である。
【図１９】（ａ）〜（ｅ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第１の態様を説明するための図である。
【図２０】（ａ）〜（ｅ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第１の態様を説明するための図である。
【図２１】（ａ）〜（ｅ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第１の態様を説明するための図である。
【図２２】（ａ）〜（ｆ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第１の態様を説明するための図である。
【図２３】本発明の配線経路を決定するための配線処理方法の第１の態様を説明するためのフローチャートである。
【図２４】本発明の配線経路を決定するための配線処理装置の第１の態様を説明するための機能ブロック図である。
【図２５】（ａ），（ｂ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第２の態様を説明するための図である。
【図２６】（ａ），（ｂ）はそれぞれ、本発明の配線経路を決定するための配線処理方法の第２の態様を説明するための図である。
【図２７】本発明の配線経路を決定するための配線処理方法の第２の態様を説明するためのフローチャートである。
【図２８】本発明の配線経路を決定するための配線処理装置の第２の態様を説明するための機能ブロック図である。
【図２９】本発明の配線経路を決定するための配線処理方法の第３の態様を説明するための図である。
【図３０】本発明の配線経路を決定するための配線処理方法の第３の態様を説明するためのフローチャートである。
【図３１】本発明の配線経路を決定するための配線処理装置の第３の態様を説明するための機能ブロック図である。
【図３２】バッファ付きクロック・トリーをモデル化して示す図である。
【図３３】バッファ付きクロック・トリーの要部構成を示す図である。
【図３４】２つのサブ・クロック・トリーからなるクロック・トリーの構成を示す図である。
【図３５】自動配線において配線経路を探索する方法を説明するための図である。
【図３６】自動配線において配線経路を探索する方法を説明するための図である。
【符号の説明】
１  会話型回路設計装置（配線処理装置）
２  ＣＰＵ
３  表示部
４  表示制御部
５  外部ファイル書込部
５Ａ  外部ファイル
６  印字部
７  入力部
８  ハードディスク（配線処理プログラム用記録媒体）
９  コンピュータ本体
１０  バッファ付きクロック・トリー
１１  クロック発生回路（クロックソース）
１２  バッファ
１３  クロック受信回路（ラッチ）
１４，１５  ワイヤ
１６，１７  抵抗
１８，２０  コンデンサ
１９  ディレイ回路
２１，２２  Π型ＲＣ回路（セグメント）
２１Ａ，２２Ａ  抵抗
２１Ｂ，２２Ｂ  コンデンサ
３０  クロック・トリー
３１，３４  レシーバ（クロック受信回路）
３２，３５  フリップフロップ回路
３３，３６  コンデンサ
３７，４０  ワイヤ
３８，４１  抵抗
３９，４２  コンデンサ
４３  セグメント
４４  クロックネット
４５Ａ  ドライバ（クロック発生回路）
４５Ｂ  クロック・トリー
４６  セグメント
４７，４９  コンデンサ
４８，５０  抵抗
５１  出力ピン
５２  テーブル
１００  バッファ付きクロック・トリー
１０１  クロック発生回路（クロックソース）
１０２  バッファ
１０３  クロック受信回路（ラッチ）
１０４，１０５  ワイヤ
１０６，１０７  抵抗
１０８，１０９，１１０  コンデンサ
１１１  ディレイ回路
１１２，１１５  レシーバ（クロック受信回路）
１１３，１１６  フリップフロップ回路
１１４，１１７  コンデンサ
１１８，１２１  ワイヤ
１１９，１２２  抵抗
１２０，１２３  コンデンサ
Ａ１  セグメント分割処理部
Ａ２  等ディレイ分岐セグメント決定処理部
Ａ３  等ディレイ分岐点決定処理部
Ａ４  第１セグメント分割処理部
Ａ５  等ディレイ分岐セグメント決定処理部
Ａ６  等ディレイ分岐点決定処理部
Ａ７  ディレイ時間決定処理部
Ａ８  第２セグメント分割処理部
Ａ９  プロパゲーションディレイ時間決定処理部
Ａ１０  配線長調整処理部
Ａ１１  セグメント分割処理部
Ａ１２  プロパゲーションディレイ時間決定処理部
Ａ１３  配線長調整処理部
Ａ１４  前方探索処理部
Ａ１５  隣接格子点フラグ処理部
Ａ１６  後方探索処理部
Ａ１７  前方探索処理部
Ａ１８  後方探索処理部
Ａ１９  最適配線経路決定処理部
Ａ２０  回路配置決定処理部
Ａ２１  配線混雑度評価処理部
Ａ２２  回路配置修正処理部
【図１】
0004268694.tif 000025
【図２】
0004268694.tif 000026
【図３】
0004268694.tif 000027
【図４】
0004268694.tif 000028
【図５】
0004268694.tif 000029
【図６】
0004268694.tif 000030
【図７】
0004268694.tif 000031
【図８】
0004268694.tif 000032
【図９】
0004268694.tif 000033
【図１０】
0004268694.tif 000034
【図１１】
0004268694.tif 000035
【図１２】
0004268694.tif 000036
【図１３】
0004268694.tif 000037
【図１４】
0004268694.tif 000038
【図１５】
0004268694.tif 000039
【図１６】
0004268694.tif 000040
【図１７】
0004268694.tif 000041
【図１８】
0004268694.tif 000042
【図１９】
0004268694.tif 000043
【図２０】
0004268694.tif 000044
【図２１】
0004268694.tif 000045
【図２２】
0004268694.tif 000046
【図２３】
0004268694.tif 000047
【図２４】
0004268694.tif 000048
【図２５】
0004268694.tif 000049
【図２６】
0004268694.tif 000050
【図２７】
0004268694.tif 000051
【図２８】
0004268694.tif 000052
【図２９】
0004268694.tif 000053
【図３０】
0004268694.tif 000054
【図３１】
0004268694.tif 000055
【図３２】
0004268694.tif 000056
【図３３】
0004268694.tif 000057
【図３４】
0004268694.tif 000058
【図３５】
0004268694.tif 000059
【図３６】
0004268694.tif 000060