(57)【要約】複数の点（Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９）を中心点（Ｃ）へルーティングするために、各点を各象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）の範囲内に配置されている組にそれぞれグループ化する。各点を、各点と中心点によって区画されている長方形の範囲内で最短マンハッタン長を有する他の任意の点へマンハッタンルーティングした結果、複数の点のうち少なくとも１つを含む各象限における少なくとも１つの仮の終点が得られる。この少なくとも１つの仮の終点を互いにマンハッタンルーティングした結果、複数の点のうち少なくとも１つを含む各象限において確定終点（ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４）がそれぞれ得られる。各確定終点を、最短化されたルーティング長で中心点へルーティングする。
2008544369.tif 000002
【特許請求の範囲】
【請求項１】
複数の点（Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９）を中心点（Ｃ）へルーティングする方法であって、
Ａ．前記複数の点を少なくとも１つの象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）の各々の範囲内に配置されているそれぞれの組にグループ化するステップと、
Ｂ．各点を、各点と前記中心点によって区画された長方形内にある最短マンハッタン長を有する他の任意の点へマンハッタンルーティングして、前記点のうち少なくとも１つを含む象限における少なくとも１つの仮の終点を得るステップとを含む、方法。
【請求項２】
Ｃ．前記少なくとも１つの仮の終点を互いにマンハッタンルーティングして、前記点のうち少なくとも１つを含む象限において前記中心点に最も近い確定終点（ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４）がさらに得るステップと、
ステップＢ及びステップＣを行うことにより、前記少なくとも１つの象限の各々に対して確定終点をそれぞれ得るステップとをさらに含む、請求項１記載の方法。
【請求項３】
ステップＢ及びステップＣを前記少なくとも１つの象限の各々に対して並行して行う、請求項２記載の方法。
【請求項４】
各確定終点を前記中心点へマンハッタンルーティングするステップをさらに含む、請求項２記載の方法。
【請求項５】
前記点のうち少なくとも１つを含む各象限における前記少なくとも１つの仮の終点を互いにルーティングし、かつ、各確定終点を前記中心点へルーティングするための、最短化されたルーティング長を決定するステップをさらに含み、
前記点の各々は集積回路（２３０）の対応するノードであり、前記中心点は前記集積回路に対する信号源の位置である、請求項４記載の方法。
【請求項６】
各々が集積回路（２３０）のノードである複数の点（Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９）と、
各々の範囲内に配置されているそれぞれの組にグループ化されている前記点を有する少なくとも１つの象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）と、
各点と中心点（Ｃ）によって区画された長方形内にある最短マンハッタン長を有する他の任意の点へ配線した結果、前記点のうち少なくとも１つを含む象限における少なくとも１つの仮の終点が得られる、各点間のマンハッタン配線（２５２，２５４）を備えた集積回路（２３０）。
【請求項７】
前記少なくとも１つの象限は、所定のグリッドによって区画されている４つの象限と前記集積回路に対してあらかじめ設定されている前記中心点とから構成されている、請求項６記載の集積回路。
【請求項８】
前記中心点は前記集積回路に対する信号源の位置である、請求項７記載の集積回路。
【請求項９】
前記点のうち少なくとも１つを含む各象限において少なくとも１つの仮の終点間で配線した結果、前記中心点に最も近い確定終点（ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４）がそれぞれ得られるマンハッタン配線をさらに備えた請求項６記載の集積回路。
【請求項１０】
前記中心点へ配線する各確定終点間のマンハッタン配線をさらに備えており、前記点のうち少なくとも１つを含む各象限における前記少なくとも１つの仮の終点間でのマンハッタン配線および前記中心点へ配線する各確定終点間のマンハッタン配線の距離は最短化されたルーティング長である、請求項９記載の集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般的にはルーティング技術に関し、より詳細には、例えば、集積回路の配線において適用される、各点を最短化されたマンハッタン長で中心点へルーティングすることに関する。
【背景技術】
【０００２】
幾何学的照合アルゴリズム（ｇｅｏｍｅｔｒｉｃ  ｍａｔｃｈｉｎｇ  ａｌｇｏｒｉｔｈｍ）や荷重中心アルゴリズム（ｗｅｉｇｈｅｄ  ｃｅｎｔｅｒ  ａｌｇｏｒｉｔｈｍ）に基づいたルーティング方法等の従来のルーティング方法は、複数の点の各々に対する遅延を均一にしようとしている。このように遅延を均一化することは、各点に到達する信号のスキューを最小限にするのに効果的である。
【０００３】
図１Ａは、例えばクロック信号等の共通の信号を受信するための複数の点Ｐ１，Ｐ２，Ｐ３，Ｐ４を有する集積回路１０２を示したものである。これらの点Ｐ１，Ｐ２，Ｐ３，Ｐ４は、共通のクロック信号を入力する集積回路１０２のノードの位置を表している。
【０００４】
図１Ｂに示すように、幾何学的照合アルゴリズムでは、第１のセグメント１０４を最も近い２点Ｐ１，Ｐ２の間に引き、第２のセグメント１０６を最も近い２点Ｐ３，Ｐ４の間に引く。さらに、第３のセグメント１０８をセグメント１０４及びセグメント１０６の各中点の間に引く。
【０００５】
このようなセグメント１０４，１０６，１０８は点Ｐ１，Ｐ２，Ｐ３，Ｐ４間の配線を示している。共通の信号を第３のセグメント１０８に沿って点１１０に接続すると、このような点１１０から点Ｐ１，Ｐ２，Ｐ３，Ｐ４の各点への遅延が等しくなる。例えば、セグメント１０４とセグメント１０６の長さが等しい場合には、点１１０はセグメント１０８の中点である。そうでない場合は、点１１０からセグメント１１０に沿ってセグメント１０４あるいはセグメント１０６までの距離が点Ｐ１，Ｐ２，Ｐ３，Ｐ４の各々に対して等しくなるまで、点１１０の位置をセグメント１１０の長さに沿って調整する。
【０００６】
その結果、共通の信号が点１１０で入力されると、等しい遅延で、すなわち最小化されたスキューで点Ｐ１，Ｐ２，Ｐ３，Ｐ４の各々に到達する。幾何学的照合アルゴリズムや荷重中心アルゴリズム等の従来のルーティング方法は、集積回路の各点への配線距離を均一にしようとしているが、集積回路の各点への配線長を最短化しようとはしていない。しかし、集積回路の中には、配線長を最短化することが重要になる可能性のあるものもある。例えば、配線長を最短化することは、集積回路の面積、複雑性及び信号遅延を最小限にするために重要である場合もある。
【発明の開示】
【０００７】
従って、本発明の一態様によれば、複数の点を最短化された距離で中心点へルーティングする。
【０００８】
本発明の包括的な態様では、複数の点を、それら複数の点のうち少なくとも１つを含む少なくとも１つの象限の各々の範囲内に配置されているそれぞれの組にグループ化する。さらに、各々の点を、当該点と中心点によって区画された長方形内にある最短マンハッタン長を有する他の任意の点へマンハッタンルーティングした結果、複数の点のうち少なくとも１つを含む象限における少なくとも１つの仮の終点が得られる
【０００９】
本発明のさらなる態様では、象限内の少なくとも１つの仮の終点を互いにマンハッタンルーティングした結果、中心点に最も近い確定終点が得られる。
【００１０】
本発明の一実施形態において、このようなステップを各象限に対して行うことにより、各点のうち少なくとも１つを含む各象限に対してそれぞれの確定終点を決定する。例えば、このようなステップを、少なくとも１つの象限の各々に対して並行して行う。
【００１１】
本発明の別の態様では、各確定終点を中心点へマンハッタンルーティングする。
【００１２】
本発明のさらなる態様では、象限における少なくとも１つの仮の終点を互いにルーティングし、かつ、各確定終点を中心点へルーティングするための、最短化されたルーティング長を決定する。
【００１３】
本発明の一実施形態において、データプロセッサ及びメモリ装置を用いて、各点の中心点へのルーティング経路を決定するこのような処理を自動化する。
【００１４】
本発明を用いることで、集積回路内の配線に特に有益である場合もある。その場合、各点はそれぞれ集積回路のノードであり、中心点は集積回路に対する信号源の位置である。しかし、各点を最短化された距離で中心点へルーティングすることが要求される他の用途に本発明を用いてもよい。
【００１５】
本発明のこれらの特長及び他の特長、またこれらの効果及び他の効果は、添付図面とともに提示されている以下の本発明の詳細な説明を検討することでより理解されるであろう。
【００１６】
本明細書にて参照している図は、説明を分かり易くするために描かれたものであり、必ずしも縮尺どおりに描かれたものではない。図１，２，３，４，５，６，７，８，９において、同様の参照符号を有する要素は同様の構造及び機能を有する要素を示している。
【発明を実施するための最良の形態】
【００１７】
図２に示すように、コンピュータシステム２０２は、本発明のある実施形態に係るメモリ装置２０４およびルーティング処理を行うデータプロセッサ２０６を有している。コンピュータシステム内のメモリ装置やデータプロセッサはそれぞれ、エレクトロニクス技術に関する当業者には公知である。
【００１８】
本発明のある実施形態によれば、メモリ装置２０４は命令シーケンスを自身に（例えば、ソフトウェアアプリケーションの形で）記憶している。このようなソフトウェアアプリケーションとしては、ＣＡＤ（ｃｏｍｐｕｔｅｒ  ａｓｓｉｓｔｅｄ  ｄｅｓｉｇｎ：コンピュータ支援設計）ルーティングアプリケーション等であってもよい。データプロセッサ２０６がメモリ装置２０４内に記憶した命令シーケンスを実行すると、データプロセッサ２０６が、図３のフローチャートにある、複数の点を中心点へルーティングする各ステップを実行する。
【００１９】
図２及び図３に示すように、データプロセッサ２０６は、所定の中心点がある所定のグリッド上に配置された複数の点からなるデータファイルを入力する（図３のステップ２１２）。図４に示すように、データファイルを集積回路２３０のイメージから生成してもよい。その場合、複数の点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９は集積回路２３０の各ノードを表しており、中心点Ｃは集積回路２３０のこのようなノードに接続される信号源の位置を示している。
【００２０】
集積回路２３０のグリッドは集積回路２３０のレイアウト制約に支配されている。例えば、集積回路２３０のレイアウトにおける配線といったオブジェクトは、集積回路２３０のこのようなグリッドに平行に配置されるように制約されることもある。縦線２３２及び横線２３４は、集積回路２３０のイメージにおけるグリッドの例である。
【００２１】
図２、図３、及び図５に示すように、次に、データプロセッサ２０６は、集積回路２３０のイメージから４つの象限Ｑ１，Ｑ２，Ｑ３，Ｑ４を決定する（図３のステップ２１４）。図５に示すように、Ｙ軸２４２及びＸ軸２４４は中心点Ｃを通って描かれている。中心点Ｃを通るＹ軸２４２は縦グリッド線２３２に平行になるように制約されており、中心点Ｃを通るＸ軸２４４は横グリッド線２３４に平行になるように制約されている。
【００２２】
第１象限Ｑ１はこのＹ軸２４２及びＸ軸２４４の右上、第２象限Ｑ２はこのＹ軸２４２及びＸ軸２４４の左上を指す。同様に、第３象限Ｑ３はこのＹ軸２４２及びＸ軸２４４の左下、第４象限Ｑ４はこのＹ軸２４２及びＸ軸２４４の右下を指す。
【００２３】
データプロセッサ２０６はさらに、点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９を、各象限Ｑ１，Ｑ２，Ｑ３，Ｑ４の範囲内に配置されたそれぞれの組にグループ化する（図３のステップ２１６）。図５に示すように、点Ｐ１は第１象限Ｑ１内に配置されている第１の組を構成する。点Ｐ２，Ｐ３，Ｐ４は第２象限Ｑ２内に配置されている第２の組を構成する。点Ｐ５は第３象限Ｑ３内に配置されている第３の組を構成する。点Ｐ６，Ｐ７，Ｐ８，Ｐ９は第４象限Ｑ４内に配置されている第４の組を構成する。
【００２４】
点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９のうちの少なくとも１つの点を含む各象限に対して、データプロセッサ２０６は各点を、各点と中心点によって区画された長方形の範囲内で最短マンハッタン長を有する他の任意の点へマンハッタンルーティングする（図３のステップ２１８）。集積回路２３０上のあらゆる配線は、Ｘ軸２４４もしくはＹ軸２４２に平行になるように制約されている。このようなＸ軸２４４もしくはＹ軸２４２に平行なルーティングを「マンハッタンルーティング」と称する。Ｘ軸２４４及び／またはＹ軸２４２に平行な任意のルーティング長の合計を「マンハッタン長」と称する。マンハッタン長はルーティング長の一例である。マンハッタンルーティング及びマンハッタン長はそれぞれ、集積回路技術に関する当業者には公知のものである。
【００２５】
図３及び図６に示すように、図３におけるこのようなステップ２１８の場合、点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９の各々と中心点Ｃとがそれぞれ、図６の点線で描かれているような長方形を区画する。ある一点に対する長方形内にあらゆる点が配置されている場合、この点はその長方形内において最も近い点へマンハッタンルーティングされていることになる。
【００２６】
第１象限Ｑ１において、点Ｐ１に対する長方形内に他の点はない。よって、点Ｐ１自身がそのまま第１象限Ｑ１内の仮の終点になる。第２象限Ｑ２では、点Ｐ２，Ｐ３，Ｐ４の各々に対する長方形内に他の点はない。よって、各点Ｐ２，Ｐ３，Ｐ４自身がそれぞれ、そのまま第２象限内の仮の終点になる。第３象限Ｑ３では、点Ｐ５に対する長方形内に他の点はない。よって、点Ｐ５自身がそのまま第３象限Ｑ３内の仮の終点になる。
【００２７】
第４象限Ｑ４では、点Ｐ９に対する長方形内に点Ｐ６，Ｐ７，Ｐ８が配置されている。これら点Ｐ６，Ｐ７，Ｐ８のうち、点Ｐ８が点Ｐ９からのマンハッタン長が最も短い。よって、図６及び図７に示すように、点Ｐ８は、マンハッタンルーティング経路２５２で点Ｐ９へマンハッタンルーティングされる。
【００２８】
図６の第４象限Ｑ４ではさらに、点Ｐ８に対する長方形内に点Ｐ７が配置されている。よって、図６及び図７に示すように、点Ｐ７はマンハッタンルーティング経路２５４で点Ｐ８へマンハッタンルーティングされる。点Ｐ８，Ｐ９が少なくとも１つの別の点へルーティングされているので、このような点Ｐ８，Ｐ９の中心点Ｃへのルーティングは、点Ｐ７の中心点Ｃへのルーティングを通じて保証されている。従って、点Ｐ８，Ｐ９はもはや中心点Ｃへのルーティングが必要であるとは見なされない。
【００２９】
また、点Ｐ７は点Ｐ８，Ｐ９よりも中心点Ｃへのマンハッタン長が短いので、点Ｐ７，Ｐ６がそのまま第４象限Ｑ４内の仮の終点になる。点Ｐ６，Ｐ７の各々に対する長方形内に他の点はない。よって、点Ｐ６，Ｐ７はそのまま第４象限Ｑ４内の仮の終点になる。
【００３０】
図３のステップ２１８において、点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９のうちの少なくとも１つの点を含む各象限に対して少なくとも１つの仮の終点を決定した後、データプロセッサ２０６は、最短化されたマンハッタン長を有する各象限において、このような少なくとも１つの仮の終点を互いにマンハッタンルーティングする。このような各象限における少なくとも１つの仮の終点に対するマンハッタンルーティングの結果、各象限において中心点Ｃに最も近い確定終点がそれぞれ得られる（図３のステップ２２０）。
【００３１】
第１象限Ｑ１及び第３象限Ｑ３はそれぞれ、仮の終点としてたった１つの点Ｐ１及び点Ｐ５を含む。よって、点Ｐ１が第１象限Ｑ１に対する第１確定終点ＥＰ１となり、点Ｐ５が第３象限Ｑ３に対する第３確定終点ＥＰ３となる。
【００３２】
第２象限Ｑ２では、仮の終点Ｐ２，Ｐ３，Ｐ４の間の最短化されたマンハッタン長でのマンハッタンルーティング経路を、これらの点Ｐ２，Ｐ３，Ｐ４の各長方形の一部分に沿って決定する。第１ルーティングセグメント２６２によって、点Ｐ２を第２確定終点ＥＰ２へマンハッタンルーティングし、また、第２ルーティングセグメント２６４によって、点Ｐ４を第２確定終点ＥＰ２へマンハッタンルーティングする。
【００３３】
さらに、第３ルーティングセグメント２６６によって、点Ｐ３を第１ルーティングセグメント２６２へマンハッタンルーティングする。なお、第３ルーティングセグメント２６６は第４のルーティングセグメント２６８よりも短いので、第４ルーティングセグメント２６８（図８の点線で示されている）から第２ルーティングセグメント２６４への経路よりも第３ルーティングセグメント２６６が選択されている。第２象限Ｑ２において、第２確定終点ＥＰ２は点Ｐ２，Ｐ３，Ｐ４よりも中心点Ｃに近い。
【００３４】
第４象限Ｑ４では、仮の終点Ｐ６，Ｐ７の間の最短化されたマンハッタン長でのマンハッタンルーティング経路を、これらの点Ｐ６，Ｐ７の各長方形の一部分に沿って決定する。第５ルーティングセグメント２７２によって、点Ｐ６を第４確定終点ＥＰ４へマンハッタンルーティングし、第６ルーティングセグメント２７４によって、点Ｐ７を第４確定終点ＥＰ４へマンハッタンルーティングする。
【００３５】
各象限Ｑ１，Ｑ２，Ｑ３，Ｑ４において確定終点ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４をそれぞれ決定した後、データプロセッサ２０６によって、これらの確定終点ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４を最短化されたマンハッタン長で中心点Ｃへマンハッタンルーティングする（図３のステップ２２２）。例えば、データプロセッサ２０６によって、確定終点ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４の中心点Ｃへの全ての実行可能なマンハッタンルーティング経路を決定する。
【００３６】
さらに、データプロセッサ２０６はどのマンハッタンルーティングが結果的に最短マンハッタン長になるかを決定する。図８及び図９の例では、縦方向ルーティングセグメント２８２（図３の太線で示されている）を、Ｙ軸２４２に沿って確定終点ＥＰ１，ＥＰ３の各Ｙ成分の間に引いている。
【００３７】
さらに、第１横方向ルーティングセグメント２８４を第２確定終点ＥＰ２から縦方向ルーティングセグメント２８２へと引いている。同様に、第２横方向ルーティングセグメント２８６を第１確定終点ＥＰ１から縦方向ルーティングセグメント２８２へ引いている。また、第３横方向ルーティングセグメント２８８を第３確定終点ＥＰ３から縦方向ルーティングセグメント２８２へ引いている。そして、第４横方向ルーティングセグメント２９０を第４確定終点ＥＰ４から縦方向ルーティングセグメント２８２へ引いている。
【００３８】
このようにして、点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９の各々を最短化されたマンハッタン長で中心点Ｃへマンハッタンルーティングしている。集積回路において配線を施す場合、図９の各ルーティングセグメントは配線セグメントを表している。このような最短化されたルーティングは、集積回路２３０の面積、複雑性及び信号遅延を小さくするのに効果的である。本発明の一実施形態において、データプロセッサ２０６は、図３のステップ２１８とステップ２２０を、点Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９のうち少なくとも１つを含む象限Ｑ１，Ｑ２，Ｑ３，Ｑ４の各々に対して並行してより速い処理時間で行う。
【００３９】
上述の内容は、もっぱら例示を目的とするものであり、限定を意図するものではない。例えば、本発明は集積回路２３０の配線に関して説明及び図示されてきた。しかしながら、本発明を、各点を最短化された距離で中心点へルーティングすることが望まれる他のあらゆる用途に用いてもよい。また、本明細書にて図示及び説明された各点のいかなる数及び位置も例示のみを目的とするものであり、各点においてあらゆる数及び位置に対して本発明を用いてもよい。さらに、本発明を、ある用途において不可欠と考えられる点のあらゆる部分集合に対してルーティング長を最短化するために用いてもよい。
【００４０】
本発明は、添付の特許請求の範囲において定義されるもの、およびその均等物によってのみ限定されるものである。
【図面の簡単な説明】
【００４１】
【図１Ａ】従来技術に係る、共通の信号を複数の点へ遅延を均一化した状態で接続するための幾何学的照合アルゴリズム。
【図１Ｂ】従来技術に係る、共通の信号を複数の点へ遅延を均一化した状態で接続するための幾何学的照合アルゴリズム。
【図２】本発明のある実施形態に係る、複数の点を最短化された距離で中心点にルーティングするステップを行うデータプロセッサを含むコンピュータシステム。
【図３】本発明のある実施形態に係る、図２のデータプロセッサによって実施されるステップのフローチャート。
【図４】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図５】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図６】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図７】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図８】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図９】本発明のある実施形態に係るルーティングであり、図３のフローチャートの各ステップ中において、複数の点を互いに段階的にルーティングし、最終的には中心点へと向かうルーティング。
【図１Ａ】
2008544369.tif 000003
【図１Ｂ】
2008544369.tif 000004
【図２】
2008544369.tif 000005
【図３】
2008544369.tif 000006
【図４】
2008544369.tif 000007
【図５】
2008544369.tif 000008
【図６】
2008544369.tif 000009
【図７】
2008544369.tif 000010
【図８】
2008544369.tif 000011
【図９】
2008544369.tif 000012
【手続補正書】
【提出日】平成19年10月19日(2007.10.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の点（Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９）を中心点（Ｃ）へルーティングする方法であって、
Ａ．前記中心点（Ｃ）と所定のグリッド（２３２，２３４）によって区画された４つの象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）を形成するステップと、
Ｂ．前記複数の点を前記象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）の各々の範囲内に配置されているそれぞれの組にグループ化するステップと、
Ｃ．前記点の各々と前記象限の境界（２４２，２４４）からそれぞれの長方形を区画するステップと、
Ｄ．第１の点（Ｐ７，Ｐ８）が第２の点（Ｐ８，Ｐ９）に対する前記長方形の範囲内にある場合には、前記第１の点を前記第２の点へマンハッタンルーティングすることにより、前記象限の各々に対する少なくとも１つの仮の終点からなる組を、前記点の各々に対して定義するステップと、
Ｅ．前記象限の各々において前記仮の終点からなる組をマンハッタンルーティングすることにより、前記象限の各々に対する確定終点（ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４）をそれぞれ形成するステップと、
Ｆ．各確定終点を前記中心点へマンハッタンルーティングするステップとを含み、
前記第１の点は、前記第２の点に対する前記長方形の範囲内に配置されているあらゆる点からなる組の中で前記第２の点への距離が最短マンハッタン長である、ところの方法。
【請求項２】
前記確定終点を前記象限の各々に対して並行して決定する、請求項１記載の方法。
【請求項３】
各確定終点を最短化されたルーティング長で前記中心点へマンハッタンルーティングする、請求項１記載の方法。
【請求項４】
前記仮の終点からなる組を、前記象限の各々の範囲内で最短化されたルーティング長でそれぞれマンハッタンルーティングし、前記複数の点の各々は集積回路（２３０）の対応するノードであり、前記中心点は前記集積回路に対する信号源の位置である、請求項１記載の方法。
【請求項５】
各々が集積回路（２３０）のノードである複数の点（Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８，Ｐ９）と、
所定のグリッドと前記集積回路に対する信号源の位置である中心点（Ｃ）から構成されており、各象限内に配置されているそれぞれの組にグループ化されている前記複数の点を有する象限（Ｑ１，Ｑ２，Ｑ３，Ｑ４）と、
前記複数のノードのうちの各ノードに対して、第１の点（Ｐ７，Ｐ８）が第２の点（Ｐ８，Ｐ９）と前記象限の境界によって区画された長方形の範囲内にある場合には、前記第１の点を前記第２の点へ配線することにより、前記象限の各々に対する少なくとも１つの仮の終点からなる組を、前記複数の点の各々に対して定義するマンハッタン配線（２５２，２５４）と、
前記象限の各々における前記仮の終点からなる組の間で配線することにより、前記象限の各々に対する確定終点（ＥＰ１，ＥＰ２，ＥＰ３，ＥＰ４）をそれぞれ形成するマンハッタン配線と、
各確定終点と前記中心点との間のマンハッタン配線を備えており、
前記第１の点は、前記第２の点に対する前記長方形の範囲内に配置されているあらゆる点からなる組の中で前記第２の点への距離が最短マンハッタン長である集積回路（２３０）。
【請求項６】
前記各確定終点から前記中心点へのマンハッタン配線の距離は最短化されたルーティング長である、請求項５記載の集積回路。
【請求項７】
前記仮の終点からなる組の間のマンハッタン配線の距離は最短化されたルーティング長である、請求項５記載の集積回路。
【国際調査報告】
2008544369.tif 000013
2008544369.tif 000014
2008544369.tif 000015
2008544369.tif 000016