JPH05151316A

JPH05151316A - 配線経路決定方法

Info

Publication number: JPH05151316A
Application number: JP3310364A
Authority: JP
Inventors: Toshiyuki Shibuya; 利行澁谷
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1991-11-26
Filing date: 1991-11-26
Publication date: 1993-06-18

Abstract

(57)【要約】【目的】ＶＬＳＩやプリント板等において、複数の回
路素子の端子と、１つの端子との接続経路を決定するた
めの配線経路決定方法に関し、２端子間に障害物が存在
しても、等距離又は等遅延の経路を決定することを目的
とする。【構成】複数の回路素子２ａ〜２ｄの各々の入力端子
と、１つの端子３とを配線するための経路を決定するた
め、該一対の入力端子の最短等距離点を接続点として求
める配線経路決定方法において、配線領域をグリッドに
分割し、該一対の入力端子の位置するソースグリッドか
ら、各々順次障害物として設定されていない隣接するグ
リッドに、該ソースを識別しうるようにラベルを広げて
いき、該一対の入力端子の位置するグリッドからのラベ
ルが、最初に同時に付られたグリッドを、該一対の入力
端子の最短等距離点として求める。

Description

【発明の詳細な説明】

【０００１】（目次）産業上の利用分野従来の技術（図１３）発明が解決しようとする課題課題を解決するための手段（図１）作用実施例 (a) 第１の実施例の説明（図２乃至図４） (b) 第２の実施例の説明（図５乃至図６） (c) 第１の実施例の説明（図７乃至図８） (d) 第１の実施例の説明（図９乃至図１０） (e) 第１の実施例の説明（図１１乃至図１２） (f) 他の実施例の説明発明の効果

【０００２】

【産業上の利用分野】本発明は、ＶＬＳＩやプリント板
等において、複数の回路素子の端子と、１つの端子との
接続経路を決定するための配線経路決定方法に関する。

【０００３】最近の回路技術の進歩に伴い、プリント
板、ＶＬＳＩのシステムクロックは、急速に向上してい
る。このシステムクロックを決める要因は、システムク
ロックのサイクルをＴ、ｓをクロックスキュー、ｄｍａ
ｘをデータの遅延の最大値、Ｔ０をデータのセットアッ
プ等の時間とすると、下記式で示される。

【０００４】Ｔ＝ｓ＋ｄｍａｘ＋Ｔ０このことから、クロックスキューｓを最小とすること
と、最大データ遅延ｄｍａｘを小さくすることが、シス
テムクロックを高くするために必要である。

【０００５】このクロックスキューｓを最小とするに
は、クロック入力端子から各回路素子のクロック端子へ
の配線長を同一とすれば良く、最大データ遅延量ｄｍａ
ｘを小さくするには、配線長を最短とすれば良く、これ
を自動レイアウト処理する技術が求められる。

【０００６】

【従来の技術】図１３は従来技術の説明図である。図１
３（Ａ）に示すように、ＬＳＩ（又はプリント板）１
に、クロックで動作する複数のフリップフロップ２ａ〜
２ｄが設けられ、クロック入力端子３から各フリップフ
ロップ２ａ〜２ｄのクロック端子ＣＬに、クロックを供
給するための配線経路は、クロック入力端子３と、各フ
リップフロップ２ａ〜２ｄのクロック端子ＣＬとを接続
する経路を形成すれば良い。

【０００７】しかし、単に接続すると、クロック入力端
子３から各フリップフロップ２ａ〜２ｄのクロック端子
ＣＬまでの距離が異なり、クロックスキューが大きくな
る。このため、図１３（Ｂ）に示すように、フリップフ
ロップ２ａ、２ｂのクロック端子ＣＬとの等距離中間点
Ｓ１（１）、フリップフロップ２ｃ、２ｄのクロック端
子ＣＬとの等距離中間点Ｓ１（２）を求め、等距離中間
点Ｓ１（１）、Ｓ１（２）の等距離中間点Ｓ２（１）を
求め、クロック入力端子３と、各フリップフロップ２ａ
〜２ｄのクロック端子ＣＬとを、この等距離中間点Ｓ１
（１）、Ｓ１（２）、Ｓ２（１）を介しツリー状に接続
すれば、クロック入力端子３から各フリップフロップ２
ａ〜２ｄのクロック端子ＣＬまでの距離が同一となり、
クロックスキューが小さくできる。

【０００８】この方法として、２端子間の中間点を、マ
ンハッタン距離で求める方法がとられていた。即ち、結
線すべき任意の２つのクロック端子からの等距離点は、
マンハッタン距離が等しい点を選び、結線すべき２端子
の選択方法は、マンハッタン距離の近いものからペアを
選び、任意の点の２端子から等距離の点を、更に等距離
になるように、ツリー状に繋いでゆき、クロック入力端
子３から全てのクロック端子ＣＬが等距離になるように
配線を行う。

【０００９】

【発明が解決しようとする課題】しかしながら、従来技
術では、次の問題があった。マンハッタン距離による方法では、単に２端子間の距
離を求めるため、クロック端子ＣＬと中間点との間に、
障害物（他の回路素子等）が何もなければ問題はない
が、障害物が存在すると、配線経路はその障害物を迂回
しなければならず、配線長が長くなり、マンハッタン距
離による見積りとの誤差が生じて、実配線長が短いかど
うかは、実際に配線してみないと判らない。

【００１０】正確にクロックスキューを見積もるとな
ると、配線長のみでは不十分であり、配線の太さや、ド
ライブされるクロック端子の容量によって、同じ長さの
配線長でも、遅延時間が異なり、このような遅延時間を
考慮して、経路を決定できない。

【００１１】従って、本発明は、２端子間に障害物が存
在しても、等距離の経路を決定することができる配線経
路決定方法を提供することを目的とする。又、本発明
は、遅延時間を考慮した、等遅延の経路を決定すること
ができる配線経路決定方法を提供することを目的とす
る。

【００１２】

【課題を解決するための手段】図１は本発明の原理図で
ある。本発明の請求項１は、複数の回路素子２ａ〜２ｄ
の各々の入力端子と、１つの端子３とを配線するための
経路を決定するため、該一対の入力端子の最短等距離点
を接続点として求める配線経路決定方法において、配線
領域をグリッドに分割し、該一対の入力端子の位置する
ソースグリッドから、各々順次障害物として設定されて
いない隣接するグリッドに、該ソースを識別しうるよう
にラベルを広げていき、該一対の入力端子の位置するグ
リッドからのラベルが、最初に同時に付られたグリッド
を、該一対の入力端子の最短等距離点として求めること
を特徴とする。

【００１３】本発明の請求項２は、複数の回路素子２ａ
〜２ｄの各々の入力端子と、１つの端子３とを配線する
ための経路を決定するため、該一対の入力端子の最短等
距離点を接続点として求める配線経路決定方法におい
て、配線領域をグリッドに分割し、該複数の入力端子の
位置するソースグリッドから、各々順次障害物として設
定されていない隣接するグリッドに、該ソースを識別し
うるようにラベルを広げていき、２つのソースグリッド
からのラベルが、最初に同時に付られたグリッドを求
め、該グリッドを最短等距離点とし、該グリッドに付さ
れたラベルの２つのソースグリッドをペアとすることを
特徴とする。

【００１４】本発明の請求項３は、請求項１又は２にお
いて、前記最短等距離点をソースグリッドとし、該ソー
スグリッドから、各々順次障害物として設定されていな
い隣接するグリッドに、該ソースを識別しうるようにラ
ベルを広げていき、２つのソースグリッドからのラベル
が、最初に同時に付られたグリッドを、該２つのソース
グリッドからの最短等距離点として求めることを特徴と
する。

【００１５】本発明の請求項４は、請求項３において、
前記入力端子から前記最短等距離点まで、又は前の最短
等距離点から現最短等距離点までの距離に応じて、前記
ソースグリッドからラベリングを開始するタイミングを
ずらしたことを特徴とする。

【００１６】本発明の請求項５は、複数の回路素子２ａ
〜２ｄの各々の入力端子と、１つの端子３とを配線する
ための経路を決定するため、該一対の入力端子の最短同
遅延点を接続点として求める配線経路決定方法におい
て、配線領域をグリッドに分割し、該複数の入力端子の
位置するソースグリッドから、各々順次障害物として設
定されていない隣接するグリッドに、該回路素子２ａ〜
２ｄの遅延時間をラベル値として、ラベルを広げてい
き、各グリッドの２つのソースグリッドからのラベル値
の差を求め、該差が零又は最小のグリッドの最短同遅延
点として求めることを特徴とする。

【００１７】本発明の請求項６は、複数の回路素子２ａ
〜２ｄの各々の入力端子と、１つの端子３とを配線する
ための経路を決定するため、該一対の入力端子の最短同
遅延点を接続点として求める配線経路決定方法におい
て、配線領域をグリッドに分割し、該複数の入力端子の
位置するソースグリッドから、各々順次障害物として設
定されていない隣接するグリッドに、該回路素子２ａ〜
２ｄの遅延時間をラベル値として、ラベルを広げてい
き、各グリッドのソースグリッドからのラベル値間の差
を求め、該差が零又は最小のグリッドを最短同遅延点と
し、該グリッドの差が零又は最小の２つのソースグリッ
ドをペアとすることを特徴とする。

【００１８】本発明の請求項７は、請求項５又は６にお
いて、前記最短同遅延点をソースグリッドとし、該ソー
スグリッドから、各々順次障害物として設定されていな
い隣接するグリッドに、該回路素子２ａ〜２ｄの遅延時
間をラベル値として、ラベルを広げていき、各グリッド
のソースグリッドからのラベル値間の差を求め、該差が
零又は最小のグリッドを最短同遅延点とし、該グリッド
の差が零又は最小の２つのソースグリッドをペアとする
ことを特徴とする。

【００１９】本発明の請求項８は、請求項７において、
前記入力端子から前記最短同遅延点まで、又は前の最短
同遅延点から現最短同遅延点までの遅延時間に応じて、
前記ソースグリッドからラベリングを開始するタイミン
グをずらしたことを特徴とする。

【００２０】本発明の請求項９は、請求項１又は２又は
３又は４又は５又は６又は７又は８において、前記グリ
ッドを、並列計算機のプロセッサにマッピングして、前
記グリッドの動作を前記プロセッサが実行することを特
徴とする。

【００２１】本発明の請求項１０は、請求項１又は２又
は３又は４又は５又は６又は７又は８又は９において、
前記回路素子２ａ〜２ｄの入力端子が、クロック端子で
あり、前記端子が、クロック入力端子であり、前記配線
回路がクロックの配線経路であることを特徴とする。

【００２２】

【作用】本発明の請求項１では、配線領域をグリッドに
分割し、該一対の入力端子の位置するソースグリッドか
ら、各々順次障害物として設定されていない隣接するグ
リッドに、該ソースを識別しうるようにラベルを広げて
いくことより、ソースから各方向に仮想的に配線をして
いく。

【００２３】そして、該一対の入力端子の位置するグリ
ッドからのラベルが、最初に同時に付られたグリッド
が、最短等距離点であり、これを一対の入力端子の最短
等距離点として、障害物が存在しても、最短等距離点を
求めることができ、クロックスキューと、最大データ遅
延量を最小にした経路を決定できる。

【００２４】本発明の請求項２では、配線領域をグリッ
ドに分割し、該複数の入力端子の位置するソースグリッ
ドから、各々順次障害物として設定されていない隣接す
るグリッドに、該ソースを識別しうるようにラベルを広
げていくことより、複数のペアの決定していないソース
から各方向に仮想的に配線をしていく。

【００２５】そして、２つのソースグリッドからのラベ
ルが、最初に同時に付られたグリッドがあるペアの最短
等距離点であり、該グリッドに付られたラベルの２つの
ソースグリッドをペアと判り、グリッドのペアと、その
等距離点が同時に決定でき、クロックスキューと、最大
データ遅延量を最小にした経路を決定できる。

【００２６】本発明の請求項３では、前記最短等距離点
をソースグリッドとし、該ソースグリッドから、各々順
次障害物として設定されていない隣接するグリッドに、
該ソースを識別しうるようにラベルを広げていき、２つ
のソースグリッドからのラベルが、最初に同時に付られ
たグリッドを、該２つのソースグリッドからの最短等距
離点として求めることを繰り返して、端子３までの最短
等距離経路を連続的に決定できる。

【００２７】本発明の請求項４では、１対の最短等距離
点の次の最短等距離点を求めるのに、１対の最短等距離
点がソースからの距離が異なると、１対の最短等距離点
の最短等距離点を求めても、ソースから見ると、最短等
距離点とはならない。

【００２８】そこで、前記入力端子から前記最短等距離
点まで、又は前の最短等距離点から現最短等距離点まで
の距離に応じて、前記ソースグリッドからラベリングを
開始するタイミングをずらすことにより、同一の手法で
ソースからの最短等距離点を求めることができる。

【００２９】本発明の請求項５では、配線領域をグリッ
ドに分割し、該複数の入力端子の位置するソースグリッ
ドから、各々順次障害物として設定されていない隣接す
るグリッドに、該回路素子２ａ〜２ｄの遅延時間をラベ
ル値として、ラベルを広げていくことより、ソースから
各方向に仮想的に遅延時間を含む配線をしていく。

【００３０】そして、各グリッドの２つのソースグリッ
ドからのラベル値の差を求め、該差が零又は最小のグリ
ッドを最短同遅延点として求めることができ、遅延があ
っても、クロックスキューと、最大データ遅延量を最小
にした経路を決定できる。

【００３１】本発明の請求項６では、配線領域をグリッ
ドに分割し、該複数の入力端子の位置するソースグリッ
ドから、各々順次障害物として設定されていない隣接す
るグリッドに、該回路素子２ａ〜２ｄの遅延時間をラベ
ル値として、ラベルを広げていくことより、ペアの決定
してない全てのソースから各方向に仮想的に遅延時間を
含む配線をしていく。

【００３２】そして、各グリッドのソースグリッドから
のラベル値間の差を求め、該差が零又は最小のグリッド
を最短同遅延点とし、該グリッドの差が零又は最小の２
つのソースグリッドをペアとすることにより、遅延があ
っても、クロックスキューと、最大データ遅延量を最小
にした経路を決定できる。

【００３３】本発明の請求項７では、前記最短同遅延点
をソースグリッドとし、該ソースグリッドから、各々順
次障害物として設定されていない隣接するグリッドに、
該回路素子２ａ〜２ｄの遅延時間をラベル値として、ラ
ベルを広げていき、各グリッドのソースグリッドからの
ラベル値間の差を求め、該差が零又は最小のグリッドを
最短同遅延点とし、該グリッドの差が零又は最小の２つ
のソースグリッドをペアとすることにより、端子３まで
の最短同遅延経路を連続的に決定できる。

【００３４】本発明の請求項８では、一対の最短同遅延
点の次の最短同遅延点を求めるのに、一対の最短同遅延
点がソースからの遅延時間が異なると、一対の最短同遅
延時間の最短同遅延点を求めても、ソースから見ると、
最短同遅延点とはならない。

【００３５】そこで、前記入力端子から前記最短同遅延
点まで、又は前の最短同遅延点から現最短同遅延点まで
の遅延時間に応じて、前記ソースグリッドからラベリン
グを開始するタイミングをずらした。

【００３６】本発明の請求項９では、前記グリッドを、
並列計算機のプロセッサにマッピングして、前記グリッ
ドの動作を前記プロセッサが実行するようにして、ラベ
リング処理を並列に実行し、かかる処理を高速に容易に
実行できるようにした。

【００３７】本発明の請求項１０では、前記回路素子２
ａ〜２ｄの入力端子が、クロック端子であり、前記端子
が、クロック入力端子であり、前記配線経路がクロック
の配線経路であるため、クロックスキューと、最大デー
タ遅延量を最小にした配線経路を決定できる。

【００３８】

【実施例】

(a) 第１の実施例の説明図２は本発明の第１実施例構成図である。

【００３９】図２（Ａ）に示すように、ＬＳＩ（又はプ
リント板）１の配線領域を、ｍ×ｎの格子状のグリッド
に分割する。このグリッドを、図２（Ｂ）に示すよう
に、ｍ×ｎの格子状に接続されたプロセッサ５１１〜５
ｍｎの各プロセッサにマッピング（受け持つ）させる。

【００４０】各プロセッサ５１１〜５ｍｎは、コントロ
ーラ（ホスト計算機）４に接続され、互いに隣接間通信
でき、配置をするのに十分なラベリングプレーンの情報
を記憶できるだけのローカルメモリを持っている。

【００４１】コントローラ４は、全プロセッサからの値
を、収集演算でき、各プロセッサに放送することもでき
る。このような並列計算機のもとで、グリッドの１つ１
つを、格子状に接続した並列計算機のプロセッサにマッ
ピングする。

【００４２】各プロセッサは、自分が受け持っているグ
リッドから隣接するプロセッサが受け持っているグリッ
ドまでの配線長又は遅延を計算して、隣接間通信を用い
て隣接するプロセッサに知らせる。

【００４３】このことを繰り返して、ソースからターゲ
ットまでの距離、又は配線による遅延を高速に計算する
ことができる。各プロセッサは、グリッドのデータとし
て、図２（Ｃ）に示すように、障害物であることを示す
禁止フラグｉｎｈｉｂｉｔと、フラグＡと、フラグＢと
を持っている。

【００４４】図３は本発明の第１の実施例処理フロー
図、図４は本発明の第１の実施例動作説明図である。コントローラ４は、全てのグリッド（プロセッサ）の
フラグＡ、Ｂを「０」に初期化し、クロック端子Ａの位
置のグリッドのフラグＡを「１」にセットし、クロック
端子Ｂの位置のグリッドのフラグＢを「１」にセット
し、障害物の位置のグリッドの禁止フラグを「１」にセ
ットする。

【００４５】この初期状態の各グリッド（プロセッサ）
のフラグＡ、Ｂの状態は、図４（Ａ）に示す通りであ
り、障害物はないものとしてある。ラベリングを開始し、フラグＡの値が「１」のグリッ
ド（プロセッサ）は、隣接する禁止フラグが「０」のグ
リッド（プロセッサ）のフラグＡを「１」にし、フラグ
Ｂの値が「１」のグリッド（プロセッサ）は、隣接する
禁止フラグが「０」のグリッド（プロセッサ）のフラグ
Ｂを「１」にする。

【００４６】これにより、各グリッド（プロセッサ）の
フラグＡ、Ｂの状態は、図４（Ｂ）に変化する。このフラグＡ、Ｂの両方が、最初に「１」となったグ
リッドが、最短の等距離点であり、各グリッド（プロセ
ッサ）は、フラグＡ、Ｂの両方が、「１」となると、コ
ントローラ４に通知する。

【００４７】従って、コントローラ４は、プロセッサか
ら通知があるかを判定し、通知がないと、フラグＡ、Ｂ
の両方が「１」のグリッドが無いとして、ステップに
戻り、通知があると、フラグＡ、Ｂの両方が「１」のグ
リッドがあると判定する。

【００４８】この時の、各グリッド（プロセッサ）のフ
ラグＡ、Ｂの状態は、図４（Ｃ）の如くなる。コントローラ４は、通知を受け、フラグＡ、Ｂの両方
が「１」のグリッドが複数あると、図４（Ｄ）に示すよ
うに、その中の任意のものを選び、中間点とする。

【００４９】即ち、コントローラ４は、通知をしたプロ
セッサを認識し、そのグリッド位置を、中間点座標と
し、ソースを、クロック端子Ａ、Ｂとして格納する。こ
れを全クロック端子に実行し、各中間点Ｓ１を求め、中
間点Ｓ１をソースとし、次の中間点Ｓ２を求め、繰り返
せば、クロック入力端子３までの配線経路が得られる。

【００５０】このようにして、クロック端子等のソース
からラベルを広げることにより、実際の配線を仮想的
に、グリッド上で実行するので、障害物があっても、そ
れを迂回した最短の等距離点が得られ、クロックスキュ
ーと、最大データ遅延時間を小さい配線経路を決定で
き、システムクロックを高速にできる。

【００５１】(b) 第２の実施例の説明図５は本発明の第２の実施例説明図、図６は本発明の第
２の実施例動作説明図であり、図２（Ａ）、（Ｂ）の構
成を前提とする。

【００５２】この例では、配線プレーンに、障害物が存
在する場合には、物理的に近いもの同士が必ずしも、配
線長が近いとは限らず、最短の配線長で結線できるクロ
ック端子のペアを選ぶには、実際に配線してみないと分
からない。

【００５３】そこで、配線すべき候補となっているクロ
ック端子の全てから一斉にラベルを広げて、配線長が最
短のペアを選択するようにしている。図５（Ａ）に示す
ように、各グリッドのデータは、禁止フラグｉｎｈｉｂ
ｉｔと、フラグ０〜Ｎとを有する。

【００５４】次に、図５（Ｂ）により、ラベリング処理
について説明する。コントローラ４は、全てのグリッド（プロセッサ）の
フラグ０〜Ｎを「０」に初期化し、クロック端子ｉの位
置のグリッドのフラグｉを「１」にセットし、障害物の
位置のグリッドの禁止フラグを「１」にセットする。

【００５５】この初期状態の各グリッド（プロセッサ）
のフラグの状態は、図６（Ａ）に示す通りであり、障害
物はないものとしてある。ラベリングを開始し、フラグ０〜Ｎのいずれかの値が
「１」のグリッド（プロセッサ）は、隣接する禁止フラ
グが「０」のグリッド（プロセッサ）の同一のインデッ
クスのフラグを「１」にする。

【００５６】これにより、各グリッド（プロセッサ）の
フラグの状態は、図６（Ｂ）に変化する。各グリッド（プロセッサ）は、フラグ１〜Ｎの２つ以
上が、「１」となると、コントローラ４に通知する。

【００５７】従って、コントローラ４は、プロセッサか
ら通知があるかを判定し、通知がないと、フラグ１〜Ｎ
の２つ以上が「１」のグリッドが無いとして、ステップ
に戻り、通知があると、フラグ１〜Ｎの２つの以上が
「１」のグリッドがあると判定する。

【００５８】この時の、各グリッド（プロセッサ）のフ
ラグの状態は、図６（Ｃ）の如くなる。コントローラ４は、通知を受けると、１〜Ｎの２つ以
上が「１」のグリッドが複数あると、図６（Ｄ）に示す
ように、その中の任意のものを選び、中間点とする。

【００５９】即ち、コントローラ４は、通知をしたプロ
セッサを認識し、そのグリッド位置を、中間点座標とす
る。そして、そのグリッドで、フラグ１〜Ｎの値が、３
つ以上「１」となっていると、３つ以上のソースからの
等距離点のため、その中から任意の２つのソース（端
子）を選び、ペアとする。

【００６０】これを全クロック端子に実行し、各中間
点Ｓ１を求めれば、ペアの決定してない候補端子のペア
と、中間点が得られる。更に、中間点Ｓ１をソースと
し、次の中間点Ｓ２を求め、繰り返せば、クロック入力
端子３までの配線経路が得られる。

【００６１】このようにして、クロック端子等のソース
からラベルを広げることにより、実際の配線を仮想的
に、グリッド上で実行するので、障害物があっても、そ
れを迂回した最短の等距離点と、そのソース対が得ら
れ、クロックスキューと、最大データ遅延時間を小さい
配線経路を決定でき、システムクロックを高速にでき
る。

【００６２】(c) 第３の実施例の説明図７は本発明の第３の実施例説明図、図８は本発明の第
３の実施例動作説明図であり、図２（Ａ）、（Ｂ）の構
成を前提とする。

【００６３】この例では、図５のクロック端子の中間点
を求める方法を用いて、連続的に次の段階の中間点を求
め、クロック入力端子３までのツリー状の経路を決定す
るものである。

【００６４】このため、コントローラ４に、図７（Ａ）
に示すような中間点の管理データを設定し、この管理デ
ータは、グリッド上の位置データ（Ｘ、Ｙ）と、ソース
の情報１、２とを有する。

【００６５】図７（Ｂ）により動作を説明する。コントローラ４は、メモリ内の集合Ｔに、図８（Ｂ）
に示すように、結線すべき全てのクロック端子（図８
（Ａ）では、クロック端子〜）を要素に加えて、集
合Ｓ０を「Ｔ」、集合Ｓ１を「０」とし、ｉを「０」と
する。

【００６６】集合Ｓｉに対し、図５のラベリングによ
る中間点探索処理を行い、求まった中間点を、集合Ｓｉ
＋１に加え、新中間点のソースを、図８（Ｂ）に示すよ
うに、集合Ｕに移し、管理データとして、新中間点の座
標（Ｘ、Ｙ）と、その２つのソースを格納する。

【００６７】コントローラ４は、集合Ｓｉが「０」に
なったかを判定し、「０」でなければ、全ての集合Ｓｉ
の中間点が探索されていないので、ステップに戻る。一方、集合Ｓｉが「０」であれば、集合Ｓｉの全ての
中間点が探索されたので、次の中間点の集合Ｓｉ＋１の
要素数が「１」かを判定する。

【００６８】次の中間点の集合Ｓｉ＋１の要素数が
「１」でなければ、２つ以上の中間点があるため、次の
中間点の探索のため、ｉをｉ＋１に更新して、ステップ
に戻り、次の中間点の集合Ｓｉ＋１の要素数が「１」
であれば、最終の中間点のため、終了する。

【００６９】このようにして、図８（Ａ）に示すよう
に、クロック端子〜を集合Ｔ（Ｓ０）とし、クロッ
ク端子、の中間点Ｓ１（１）を探索し、集合Ｕに登
録し、クロック端子、の中間点Ｓ１（２）を探索
し、集合Ｕに登録し、集合Ｓ０の処理を終了し、集合Ｓ
１の処理に移り、中間点Ｓ１（１）と、Ｓ１（２）の中
間点Ｓ２を探索し、集合Ｓ２が１つのため、最終の中間
点として、終了する。

【００７０】これにより、図８（Ｂ）に示すように、ク
ロック端子と、各段階の中間点のデータが得られる。 (d) 第４の実施例の説明図９は本発明の第４の実施例説明図、図１０は本発明の
第４の実施例動作説明図であり、図２（Ａ）、（Ｂ）の
構成を前提とする。

【００７１】この実施例は、第３の実施例において、中
間点Ｓ１（１）と中間点Ｓ１（２）との中間点Ｓ２を求
めるのに、クロック端子、から中間点Ｓ１（１）ま
での距離と、クロック端子、から中間点Ｓ１（２）
までの距離とが異なると、中間点Ｓ１（１）と中間点Ｓ
１（２）との中間の点Ｓ２を求めても、クロック端子
、、、から中間点Ｓ２までの距離が等しくなら
ない。

【００７２】このため、クロック端子、から中間点
Ｓ１（１）までの距離と、クロック端子、から中間
点Ｓ１（２）までの距離との違いを考慮して、ラベリン
グを行って、中間点Ｓ２を求める。

【００７３】即ち、図９（Ａ）に示すように、中間点の
管理データを、図７（Ａ）のものに加え、クロック端子
からの距離を含ませる。次に、図９（Ｂ）により、ラベ
リング処理について説明する。

【００７４】コントローラ４は、中間点Ｓ１が求まる
と、全てのグリッド（プロセッサ）のフラグ０〜Ｎを
「０」に初期化し、ｓｔａｒｔＮＯを「０」とし、中間
点の集合Ｓｉの要素の中でクロックからの距離の最大値
を求め、ｍａｘＣｌｏｃｋとし、中間点ｋの位置のグリ
ッドのフラグｋを「１」にセットし、障害物の位置のグ
リッドの禁止フラグを「１」にセットする。

【００７５】ラベリングを開始し、クロック端子から
の距離が、ｓｔａｒｔＮＯよりも小さいかを判定し、小
さいグリッドに対し、フラグ０〜Ｎのいずれかの値が
「１」のグリッド（プロセッサ）は、隣接する禁止フラ
グが「０」のグリッド（プロセッサ）の同一のインデッ
クスのフラグを「１」にする。

【００７６】各グリッド（プロセッサ）は、フラグ１
〜Ｎの２つ以上が、「１」となると、コントローラ４に
通知する。従って、コントローラ４は、プロセッサから
通知があるかを判定し、通知がないと、フラグ１〜Ｎの
２つ以上が「１」のグリッドが無いとして、ｓｔａｒｔ
ＮＯを、ｓｔａｒｔＮＯ＋１として、ステップに戻
り、通知があると、フラグ１〜Ｎの２つ以上が「１」の
グリッドがあると判定する。

【００７７】コントローラ４は、通知を受けると、１
〜Ｎの２つ以上が「１」のグリッドが複数あると、その
中の任意のものを選び、中間点とする。即ち、コントロ
ーラ４は、通知をしたプロセッサを認識し、そのグリッ
ド位置を、中間点座標とする。

【００７８】そして、そのグリッドで、フラグ１〜Ｎの
値が、３つ以上「１」となっていると、３つ以上のソー
スからの等距離点のため、その中から任意の２つのソー
ス（端子）を選び、ペアとする。

【００７９】これを全中間点に実行し、各中間点Ｓ２を
求めれば、ペアの決定してない候補端子のペアと、クロ
ック端子から等距離の中間点Ｓ２が得られる。更に、中
間点Ｓ２をソースとし、次の中間点Ｓ３を求め、繰り返
せば、クロック入力端子３までの配線経路が得られる。

【００８０】これを、図１０（Ａ）、（Ｂ）で説明する
と、中間点Ｓ１（１）のクロック端子、からの距離
は「３」であり、中間点Ｓ１（２）のクロック端子、
からの距離は「４」であるから、ｓｔａｒｔＮＯが
「４」となると、中間点Ｓ１（１）からラベルが付ら
れ、ｓｔａｒｔＮＯが「５」となると、中間点Ｓ１
（１）とＳ１（２）の両方からラベルが付られて、中間
点Ｓ２が求まる。

【００８１】従って、クロック端子からの距離が短い中
間点から、差だけラベルが付られ後、全中間点から一斉
にラベルが付られる。即ち、距離の差だけずらして、ラ
ベリングを行うことにより、距離の差を吸収し、クロッ
ク端子から見て、等距離の中間点が得られる。

【００８２】(e) 第５の実施例の説明図１１は本発明の第５の実施例説明図、図１２は本発明
の第５の実施例動作説明図であり、図２（Ａ）、（Ｂ）
の構成を前提とする。

【００８３】この実施例では、第１の実施例では、回路
素子の容量によるクロックの遅延が同一のものとして説
明したが、回路素子の容量等により、回路素子毎に遅延
量が異なることがある。

【００８４】このような場合には、遅延量を考慮したラ
ベリングを行わないと、クロックの到達時間が同一とな
らない。そこで、遅延時間を考慮したラベリングを行う
ため、各プロセッサは、グリッドのデータとして、図１
１（Ａ）に示すように、障害物であることを示す禁止フ
ラグｉｎｈｉｂｉｔと、フラグＡと、フラグＢと、クロ
ック端子Ａからの遅延時間ｄｅｌａｙＡと、クロック端
子Ｂからの遅延時間ｄｅｌａｙＢとを持っている。

【００８５】図１１（Ｂ）により、ラベリング処理を説
明する。コントローラ４は、全てのグリッド（プロセッサ）の
フラグＡ、Ｂを「０」に、遅延時間ｄｅｌａｙＡ、Ｂを
「０」に初期化し、クロック端子Ａの位置のグリッドの
フラグＡを「１」にセットし、クロック端子Ｂの位置の
グリッドのフラグＢを「１」にセットし、障害物の位置
のグリッドの禁止フラグを「１」にセットする。

【００８６】この初期状態の各グリッド（プロセッサ）
のフラグＡ、Ｂの状態は、図１２（Ａ）に示す通りであ
り、障害物はないものとしてある。両方の端子Ａ、Ｂに対して、グリッド当たりの遅延時
間を計算し、グリッドＡ、Ｂの遅延時間ｄｅｌａｙＡ、
Ｂにセットする。

【００８７】ラベリングを開始し、フラグＡの値が
「１」のグリッド（プロセッサ）は、隣接する禁止フラ
グが「０」のグリッド（プロセッサ）のフラグＡを
「１」にし、ｄｅｌａｙＡの値が「０」より大きいと、
隣接するグリッドの遅延時間を計算し、隣接するグリッ
ドのｄｅｌａｙＡにセットする。

【００８８】フラグＢの値が「１」のグリッド（プロ
セッサ）は、隣接する禁止フラグが「０」のグリッド
（プロセッサ）のフラグＢを「１」にし、ｄｅｌａｙＢ
の値が「０」より大きいと、隣接するグリッドの遅延時
間を計算し、隣接するグリッドのｄｅｌａｙＢにセット
する。

【００８９】これにより、各グリッド（プロセッサ）の
フラグＡ、Ｂの状態は、図１２（Ｂ）に変化する。コントローラ４は、全てのグリッドにラベルが広がっ
たかを判定し、広がっていなければ、ステップに戻
り、広がっていると、ラベリングを終了し、各グリッド
が計算したｄｅｌａｙＡと、ｄｅｌａｙＢとの差を受
け、その中から差が零又は所定値αより小さいグリッド
を探す。

【００９０】差が零又は所定値αより小さいグリッドが
あると、その中から遅延時間の最も小さいものを選び、
中間点とする。図１２で説明すると、ｄｅｌａｙＡを
「１０」、ｄｅｌａｙＢを「２０」とすると、図１２
（Ｂ）に示すように、グリッドＡからは、隣接グリッド
のｄｅｌａｙＡに「１０」が書き込まれ、グリッドＢか
らは、隣接グリッドのｄｅｌａｙＢに「２０」が書き込
まれ、以降隣接グリッドのｄｅｌａｙＡ、Ｂに、「１
０」、「２０」加算して書き込まれる。

【００９１】従って、全グリッドにラベリングされる
と、図１２（Ｃ）の如くなり、図１２（Ｄ）のように、
ｄｅｌａｙＡが「７０」、ｄｅｌａｙＢが「６０」のグ
リッドが、遅延時間最小のグリッドとして選ばれ、この
内の１つが最短同遅延点とされる。

【００９２】このようにして、回路素子の遅延時間が異
なっても、同遅延時間点を求めることができ、クロック
スキューが最小で、最大データ遅延時間が最小の同遅延
時間点が得られる。

【００９３】(f) 他の実施例の説明上述の実施例の他に、本発明は、次のような変形が可能
である。上述の第５の実施例では、Ａ、Ｂの２点を対象として
いるが、第２の実施例のように、候補クロック端子点か
ら一斉に同様の遅延量のラベルを広げて、同遅延時間点
と、そのペアを求めることもできる。

【００９４】同様に、第５の実施例に、第３の実施例
の手法を用いて、連続的に、各段階の同遅延時間点を求
めることもでき、第４の実施例の手法を用いて、同遅延
点の遅延時間を異ならせて、次の同遅延点を求めること
もできる。

【００９５】並列計算機で実施して、ラベリング処理
の高速化を達成しているが、汎用計算機で実行するた
め、グリッドをメモリに割りつけ、１つまたはこれ以上
のプロセッサでメモリのリード／ライト処理により実行
すれば、より簡易に実現でき、汎用性を持たせることが
できる。

【００９６】クロック信号の並列配線について説明し
たが、複数の回路素子に同時入力すべきデータ等の他の
信号に適用しても良く、ＬＳＩの他に、プリント板等の
配線レイアウト設計にも適用できる。

【００９７】以上、本発明を実施例により説明したが、
本発明の主旨の範囲内で種々の変形が可能であり、これ
らを本発明の範囲から排除するものではない。

【００９８】

【発明の効果】以上説明したように、本発明によれば、
次の効果を奏する。複数の回路素子と、１つの端子とを配線する経路を決
定するに当たり、配線領域をグリッドに分割し、接続す
べき位置のグリッドからラベルを広げて、仮想的な配線
を行い、グリッドのラベル状態から等伝播時間の中間点
を得るので、障害物があっても、最短の等伝播時間の中
間点を得ることができる。

【００９９】従って、信号のスキューが最小にでき、
システムの性能を向上できる。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明の第１の実施例構成図である。

【図３】本発明の第１の実施例処理フロー図である。

【図４】本発明の第１の実施例動作説明図である。

【図５】本発明の第２の実施例説明図である。

【図６】本発明の第２の実施例動作説明図である。

【図７】本発明の第３の実施例説明図である。

【図８】本発明の第３の実施例動作説明図である。

【図９】本発明の第４実施例説明図である。

【図１０】本発明の第４の実施例動作説明図である。

【図１１】本発明の第５の実施例説明図である。

【図１２】本発明の第５の実施例動作説明図である。

【図１３】従来技術の説明図である。

【符号の説明】

１ＬＳＩ（プリント板）２ａ〜２ｄ回路素子（フリップフロップ）３クロック入力端子ＣＬクロック端子

Claims

【特許請求の範囲】

【請求項１】複数の回路素子（２ａ〜２ｄ）の各々の
入力端子と、１つの端子（３）とを配線するための経路
を決定するため、該一対の入力端子の最短等距離点を接
続点として求める配線経路決定方法において、配線領域をグリッドに分割し、該一対の入力端子の位置
するソースグリッドから、各々順次障害物として設定さ
れていない隣接するグリッドに、該ソースを識別しうる
ようにラベルを広げていき、該一対の入力端子の位置するグリッドからのラベルが、
最初に同時に付られたグリッドを、該一対の入力端子の
最短等距離点として求めることを特徴とする配線経路決
定方法。
【請求項２】複数の回路素子（２ａ〜２ｄ）の各々の
入力端子と、１つの端子（３）とを配線するための経路
を決定するため、該一対の入力端子の最短等距離点を接
続点として求める配線経路決定方法において、配線領域をグリッドに分割し、該複数の入力端子の位置
するソースグリッドから、各々順次障害物として設定さ
れていない隣接するグリッドに、該ソースを識別しうる
ようにラベルを広げていき、２つのソースグリッドからのラベルが、最初に同時に付
られたグリッドを求め、該グリッドを最短等距離点と
し、該グリッドに付されたラベルの２つのソースグリッ
ドをペアとすることを特徴とする配線経路決定方法。
【請求項３】前記最短等距離点をソースグリッドと
し、該ソースグリッドから、各々順次障害物として設定
されていない隣接するグリッドに、該ソースを識別しう
るようにラベルを広げていき、２つのソースグリッドか
らのラベルが、最初に同時に付られたグリッドを、該２
つのソースグリッドからの最短等距離点として求めるこ
とを特徴とする請求項１又は２の配線経路決定方法。
【請求項４】前記入力端子から前記最短等距離点ま
で、又は前の最短等距離点から現最短等距離点までの距
離に応じて、前記ソースグリッドからラベリングを開始
するタイミングをずらしたことを特徴とする請求項３の
配線経路決定方法。
【請求項５】複数の回路素子（２ａ〜２ｄ）の各々の
入力端子と、１つの端子（３）とを配線するための経路
を決定するため、該一対の入力端子の最短同遅延点を接
続点として求める配線経路決定方法において、配線領域をグリッドに分割し、該複数の入力端子の位置
するソースグリッドから、各々順次障害物として設定さ
れていない隣接するグリッドに、該回路素子（２ａ〜２
ｄ）の遅延時間をラベル値として、ラベルを広げてい
き、各グリッドの２つのソースグリッドからのラベル値の差
を求め、該差が零又は最小のグリッドの最短同遅延点と
して求めることを特徴とする配線経路決定方法。
【請求項６】複数の回路素子（２ａ〜２ｄ）の各々の
入力端子と、１つの端子（３）とを配線するための経路
を決定するため、該一対の入力端子の最短同遅延点を接
続点として求める配線経路決定方法において、配線領域をグリッドに分割し、該複数の入力端子の位置
するソースグリッドから、各々順次障害物として設定さ
れていない隣接するグリッドに、該回路素子（２ａ〜２
ｄ）の遅延時間をラベル値として、ラベルを広げてい
き、各グリッドのソースグリッドからのラベル値間の差を求
め、該差が零又は最小のグリッドを最短同遅延点とし、
該グリッドの差が零又は最小の２つのソースグリッドを
ペアとすることを特徴とする配線経路決定方法。
【請求項７】前記最短同遅延点をソースグリッドと
し、該ソースグリッドから、各々順次障害物として設定
されていない隣接するグリッドに、該回路素子（２ａ〜
２ｄ）の遅延時間をラベル値として、ラベルを広げてい
き、各グリッドのソースグリッドからのラベル値間の差を求
め、該差が零又は最小のグリッドを最短同遅延点とし、
該グリッドの差が零又は最小の２つのソースグリッドを
ペアとすることを特徴とする請求項５又は６の配線経路
決定方法。
【請求項８】前記入力端子から前記最短同遅延点ま
で、又は前の最短同遅延点から現最短同遅延点までの遅
延時間に応じて、前記ソースグリッドからラベリングを
開始するタイミングをずらしたことを特徴とする請求項
７の配線経路決定方法。
【請求項９】前記グリッドを、並列計算機のプロセッ
サにマッピングして、前記グリッドの動作を前記プロセ
ッサが実行することを特徴とする請求項１又は２又は３
又は４又は５又は６又は７又は８の配線経路決定方法。
【請求項１０】前記回路素子（２ａ〜２ｄ）の入力端
子が、クロック端子であり、前記端子が、クロック入力
端子であり、前記配線回路がクロックの配線経路である
ことを特徴とする請求項１又は２又は３又は４又は５又
は６又は７又は８又は９の配線経路決定方法。