(57)【要約】      （修正有）【課題】既存の単一のレベルのスパイン配線技法は通常、一度に単一のネットの配線を実行する。その結果として、集積回路の配線は部分最適となることが多い。従来の配線解決策に比して、総配線長、伝搬遅延、スキュー時間などの１または複数の因子が改善されている、改良されたスパイン配線技法を提供する。【解決手段】マルチレベルのスパイン配線は、１セットのピンを含むネットの仕様の受信に応じて、ネットを配線するための第１の配線が作成され、ネットを含むピンのセットは、コスト関数に少なくとも部分的に基づいて１または複数のグループに分割され、第１の配線に接続する第２の配線が、ネットの各グループに対して作成され、そのグループの第２の配線に各ピンを接続する第３の配線が、ネットの各グループの各ピンに対して作成される。【選択図】図２Ｂ
2012118986.tif 000002
【特許請求の範囲】
【請求項１】
ネットを配線する方法であって、
１セットのピンのセットを含むネットの仕様を受信し、
前記ネットを配線するために第１の配線を作成し、
前記ネットを構成する前記ピンのセットをコスト関数に少なくとも部分的に基づいて前記ネットを構成する前記ピンのセットを１または複数のグループに分割し、
前記ネットの各グループに対して、前記第１の配線に接続する第２の配線を作成し、
前記ネットの各グループの各ピンに対して、前記ピンを前記グループの前記第２の配線に接続する第３の配線を作成すること、を備える方法。
【請求項２】
前記ネットは、集積回路の一部である請求項１に記載の方法。
【請求項３】
前記第１の配線、各グループに関連する前記第２の配線および各ピンに関連する前記第３の配線は、前記ネットを配線するために使用される請求項１に記載の方法。
【請求項４】
前記第１の配線は、前記ネットのメインスパインを含む請求項１に記載の方法。
【請求項５】
前記ネットを構成する前記ピンのセットを１または複数のグループに分割することは、前記第１の配線の位置に少なくとも部分的に基づく請求項１に記載の方法。
【請求項６】
各グループのピンが前記第１の配線と同じ側に配置される請求項１に記載の方法。
【請求項７】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項１に記載の方法。
【請求項８】
前記ネットを構成する前記ピンのセットを１または複数のグループに分割することは、ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムまたはｋ−ｍｅｄｉａｎ法クラスタリングアルゴリズムに少なくとも部分的に基づいて分割することを備える請求項１に記載の方法。
【請求項９】
前記第２の配線は、前記ネットの第２のレベルのスパインを備える請求項１に記載の方法。
【請求項１０】
前記第１の配線および前記第２の配線が実質的に直交するよう配置されている請求項１に記載の方法。
【請求項１１】
ネットを配線するシステムであって、
１セットのピンのセットを含むネットの仕様を受信し、
前記ネットを配線するために第１の配線を作成し、
前記ネットを構成する前記ピンのセットをコスト関数に少なくとも部分的に基づいて１または複数のグループに分割し、
前記ネットの各グループに対して、前記第１の配線に接続する第２の配線を作成し、
前記ネットの各グループの各ピンに対して、前記ピンを前記グループの前記第２の配線に接続する第３の配線を作成するように構成されるプロセッサと、
前記プロセッサに接続され、前記プロセッサに命令を提供するように構成されるメモリと、を備えるシステム。
【請求項１２】
前記ネットを配線するために、前記第１の配線、各グループに関連する前記第２の配線および各ピンに関連する前記第３の配線を使用する請求項１１に記載のシステム。
【請求項１３】
前記第１の配線は、前記ネットのメインスパインを含む請求項１１に記載のシステム。
【請求項１４】
前記ネットを構成する前記ピンのセットは、前記第１の配線に少なくとも部分的に基づいて１または複数のグループに分割される請求項１１に記載のシステム。
【請求項１５】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項１１に記載のシステム。
【請求項１６】
前記ネットを構成する前記ピンのセットを１または複数のグループに分割することは、ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムまたはｋ−ｍｅｄｉａｎ法クラスタリングアルゴリズムに少なくとも部分的に基づいて分割されることを備える請求項１１に記載のシステム。
【請求項１７】
前記第２の配線は、前記ネットの第２のレベルのスパインを備える請求項１１に記載のシステム。
【請求項１８】
前記第１の配線および前記第２の配線が実質的に直交するよう配置されている請求項１１に記載のシステム。
【請求項１９】
ネットを配線するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、コンピュータ読み込み可能な記憶媒体に実装され、
１セットのピンのセットを含むネットの仕様を受信し、
前記ネットを配線するために第１の配線を作成し、
前記ネットを構成する前記ピンのセットをコスト関数に少なくとも部分的に基づいて１または複数のグループに分割し、
前記ネットの各グループに対して、前記第１の配線に接続する第２の配線を作成し、
前記ネットの各グループの各ピンに対して、前記ピンを前記グループの前記第２の配線に接続する第３の配線を作成する計算機命令を備えるコンピュータプログラム製品。
【請求項２０】
前記ネットを配線するために、前記第１の配線、各グループに関連する前記第２の配線および各ピンに関連する前記第３の配線を使用する請求項１９に記載のコンピュータプログラム製品。
【請求項２１】
前記第１の配線は、前記ネットのメインスパインを含む請求項１９に記載のコンピュータプログラム製品。
【請求項２２】
前記ネットを構成する前記ピンのセットは、前記第１の配線に、少なくとも部分的に基づいて１または複数のグループに分割される請求項１９に記載のコンピュータプログラム製品。
【請求項２３】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項１９に記載のコンピュータプログラム製品。
【請求項２４】
前記第２の配線は、前記ネットの第２のレベルのスパインを備える請求項１９に記載のコンピュータプログラム製品。
【請求項２５】
前記第１の配線および前記第２の配線が実質的に直交するよう配置されている請求項１９に記載のコンピュータプログラム製品。
【請求項２６】
複数のネットを配線するための方法であって、
複数のネットの仕様を受信し、
メインスパインに利用可能な配線トラックの１セットの仕様を受信し、
コスト関数に少なくとも部分的に基づいて、前記複数のネットそれぞれにメインスパイン配線トラックを割り当て、
前記複数のネットそれぞれに割り当てられる前記メインスパイン配線トラックにメインスパイン配線を作成することを備える方法。
【請求項２７】
前記複数のネットは、集積回路を含む請求項２６に記載の方法。
【請求項２８】
コスト関数に少なくとも部分的に基づいて前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づく請求項２６に記載の方法。
【請求項２９】
コスト関数に少なくとも部分的に基づいて前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づいており、１または複数の利用可能な前記メインスパイン配線トラックが、各ネットについて考慮される、請求項２６に記載の方法。
【請求項３０】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項２６に記載の方法。
【請求項３１】
前記コスト関数は、第１のコスト関数を含み、前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、第２のコスト関数に少なくとも部分的に基づいて、各ネットに関連するピンを１または複数のグループに分割することを備える請求項２６の方法。
【請求項３２】
前記第２のコスト関数は、配線長に少なくとも部分的に基づく請求項３１に記載の方法。
【請求項３３】
前記第１コスト関数は、前記第２のコスト関数を含む請求項３１に記載の方法。
【請求項３４】
各ネットに関連するピンを１または複数グループに分割することは、前記ネットに割り当てられる前記メインスパイン配線トラックの位置に少なくとも部分的に基づく請求項３１に記載の方法。
【請求項３５】
各グループのピンは、対応するネットのメインスパインと同じ側に配置される請求項３１に記載の方法。
【請求項３６】
各ネットに関連するピンを１または複数のグループに分割することは、ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムまたはｋ−ｍｅｄｉａｎ法クラスタリングアルゴリズムに少なくとも部分的に基づいて分割されることを備える請求項３１に記載の方法。
【請求項３７】
第２のレベルのスパインに利用可能な配線トラックの１セットの仕様を受信し、第３のコスト関数に少なくとも部分的に基づいて、各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てることをさらに備える請求項３１に記載の方法。
【請求項３８】
前記第３のコスト関数は、配線長に少なくとも部分的に基づく請求項３７に記載の方法。
【請求項３９】
第３のコスト関数に少なくとも部分的に基づいて各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づく請求項３７に記載の方法。
【請求項４０】
第３のコスト関数に少なくとも部分的に基づいて各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づいており、１または複数の利用可能な前記第２のレベルのスパイン配線トラックが各グループにについて考慮される、請求項３７に記載の方法。
【請求項４１】
各グループの前記第２のレベルのスパイン配線トラックに、第２のレベルのスパイン配線を作成することをさらに備える請求項３７に記載の方法。
【請求項４２】
各グループの各ピンと前記グループに関連する第２のレベルのスパイン配線との間の配線を作成することをさらに備える請求項４１に記載の方法。
【請求項４３】
前記第１のコスト関数、前記第２のコスト関数および前記第３のコスト関数の１または複数が同じである請求項３７に記載の方法。
【請求項４４】
前記第２のレベルのスパイン配線トラックが、前記メインスパイン配線トラックと実質的に直交するよう配置されている請求項３７に記載の方法。
【請求項４５】
複数のネットを配線するためのシステムであって、
複数のネットの仕様を受信し、
メインスパインに利用可能な配線トラックの１セットの仕様を受信し、
コスト関数に少なくとも部分的に基づいて、前記複数のネットそれぞれにメインスパイン配線トラックを割り当て、
前記複数のネットそれぞれに割り当てられたメインスパイン配線トラックにメインスパイン配線を作成するように構成されるプロセッサと、
前記プロセッサに接続して、前記プロセッサに命令を提供するように構成されるメモリと、を備えるシステム。
【請求項４６】
コスト関数に少なくとも部分的に基づいて、前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づいており、利用可能な前記メインスパイン配線トラックの１または複数が、各ネットにについて考慮される、請求項４５に記載のシステム方法。
【請求項４７】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項４５に記載のシステム。
【請求項４８】
前記コスト関数は、第１のコスト関数を含み、前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、第２のコスト関数に少なくとも部分的に基づいて各ネットに関連するピンを１または複数のグループに分割することを備える請求項４５に記載のシステム。
【請求項４９】
前記第２のコスト関数は、配線長に少なくとも部分的に基づく請求項４８に記載のシステム。
【請求項５０】
前記第１のコスト関数は、前記第２のコスト関数を備える請求項４８に記載のシステム。
【請求項５１】
前記プロセッサは、第２のレベルのスパインに利用可能な配線トラックの１セットの仕様を受信し、第３のコスト関数に少なくとも部分的に基づいて、各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てるように構成される請求項４８に記載のシステム。
【請求項５２】
前記第３のコスト関数は、配線長に少なくとも部分的に基づく請求項５１に記載のシステム。
【請求項５３】
第３のコスト関数に少なくとも部分的に基づいて、各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てることは、線形割当問題に対する解決策に基づいており、利用可能な第２のレベルのスパイン配線トラックの１または複数が、各グループにについて考慮される、請求項５１に記載のシステム。
【請求項５４】
前記プロセッサは、各グループに割り当てられた前記第２のレベルのスパイン配線トラックに、第２のレベルのスパイン配線を作成するようにさらに構成される請求項５１に記載のシステム。
【請求項５５】
前記プロセッサは、各グループの各ピンと前記グループに関連する第２のレベルのスパイン配線との間の配線を作成するようにさらに構成される請求項５４に記載のシステム。
【請求項５６】
前記第１のコスト関数、前記第２のコスト関数および前記第３のコスト関数の１または複数が同じである請求項５１に記載のシステム。
【請求項５７】
前記第２のレベルのスパイン配線トラックが、メインスパイン配線トラックと実質的に直交するよう配置されている請求項５１に記載のシステム。
【請求項５８】
複数のネットを配線するためのコンピュータプログラム製品であって、前記コンピュータプログラム製品は、コンピュータが読み込み可能な記憶媒体に実装され、
複数のネットの仕様を受信し、
メインスパインに利用可能な配線トラックの１セットの仕様を受信し、
コスト関数に少なくとも部分的に基づいて、前記複数のネットそれぞれにメインスパイン配線トラックを割り当て、
前記複数のネットそれぞれに割り当てられた前記メインスパイン配線トラックにメインスパイン配線を作成する計算機命令を備えるコンピュータプログラム製品。
【請求項５９】
前記コスト関数は、配線長に少なくとも部分的に基づく請求項５８に記載のコンピュータプログラム製品。
【請求項６０】
コスト関数は第１のコスト関数を含み、第２のコスト関数に少なくとも部分的に基づいて、前記複数のネットそれぞれにメインスパイン配線トラックを割り当てることは、各ネットに関連するピンを１または複数のグループに分割することを備える請求項５８に記載のコンピュータプログラム製品。
【請求項６１】
前記第２のコスト関数は、配線長に少なくとも部分的に基づく請求項６０に記載のコンピュータプログラム製品。
【請求項６２】
第２のレベルのスパインに利用可能な配線トラックの１セットの仕様を受信し、第３のコスト関数に少なくとも部分的に基づいて、各ネットの各グループに第２のレベルのスパイン配線トラックを割り当てる計算機命令をさらに備える請求項６０に記載のコンピュータプログラム製品。
【請求項６３】
前記第３のコスト関数は、配線長に少なくとも部分的に基づく請求項６２に記載のコンピュータプログラム製品。
【請求項６４】
各グループに割り当てられた前記第２のレベルのスパイン配線トラックに、第２のレベルのスパイン配線を作成する計算機命令をさらに備える請求項６２に記載のコンピュータプログラム製品。
【請求項６５】
各グループの各ピンと前記グループに関連する第２のレベルのスパイン配線との間の配線を作成する計算機命令をさらに備える請求項６４に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【背景技術】
【０００１】
［関連出願の相互参照］
本出願は、２０１０年１１月２９日出願の発明の名称を「ＴＷＯ−ＬＥＶＥＬ  ＳＰＩＮＥ  ＲＯＵＴＩＮＧ」とする米国仮特許出願第６１／４１７，８３９号、ならびにこの出願に基づく優先権を主張する２０１１年１１月４日出願の発明の名称を「ＭＵＬＴＩＰＬＥ  ＬＥＶＥＬ  ＳＰＩＮＥ  ＲＯＵＴＩＮＧ」とする米国特許出願第１３／２８９，９６３号および２０１１年１１月４日出願の発明の名称を「ＭＵＬＴＩＰＬＥ  ＬＥＶＥＬ  ＳＰＩＮＥ  ＲＯＵＴＩＮＧ」とする米国特許出願第１３／２８９，９６５号の優先権を主張し、これらの内容全体を参照によって本願明細書に引用した。
【０００２】
既存の単一のレベルのスパイン配線技法は通常、一度に単一のネットの配線を実行する。その結果として、集積回路の配線は部分最適となることが多い。改良されたスパイン配線技法が有用であると考えられる。
【０００３】
本発明のさまざまな実施形態を以下の詳しい記載および添付図面に開示する。
【図面の簡単な説明】
【０００４】
【図１】単一のネットに関する典型的な従来技術のスパイン配線による結果を示す図である。
【図２Ａ】単一のネットに関する２つのレベルのスパイン配線の実施形態を示す図である。
【図２Ｂ】ネットを配線する手順の実施形態を示すフローチャートである。
【図３】配線計画を作成する手順の実施形態を示すフローチャートである。
【図４】ネットに対するメインスパイントラック割当を求めるのに使用されるマトリクスの実施形態を示す図である。
【図５】ネットのグループに対する２つのレベルのスパイントラック割当を求めるのに使用されるマトリクスの実施形態を示す図である。
【発明を実施するための形態】
【０００５】
本発明は、プロセス、装置、システム、物質組成、コンピュータ読み込み可能な記憶媒体に実装したコンピュータプログラム製品、および／または、プロセッサに接続したメモリに格納された命令および／またはプロセッサに接続したメモリから提供される命令を実行するように構成されるプロセッサなどの多くの方法で実装することができる。本願明細書では、これらの実装形態、または、本発明が取りうるその他の形態を技法と呼ぶ。一般に、開示する処理ステップの順序は、本発明の範囲内で変更することができる。別途記載のない限り、タスクを実行するように構成されると記載するプロセッサやメモリなどの構成部品は、所定の時間にタスクを実行するために一時的に構成される一般的な構成部品として、あるいは、タスクを実行するように製造される特定の構成部品として実装されうる。本願明細書で使用するように、用語「プロセッサ」は、計算機プログラム命令などのデータを処理するように構成される１または複数の装置、回路および／またはプロセッシングコアを示す。
【０００６】
以下に、本発明の１または複数の実施形態を、本発明の原理を示す添付図面と共に詳しく説明する。本発明は、そのような実施形態に関連して記載されるが、本発明はいかなる実施形態にも限定されない。本発明の範囲は、本願特許請求の範囲によってのみ限定され、本発明は多数の代替手段、改変例および均等物を含む。本発明を詳しく理解するために、以下の記載において多数の具体例を詳細に記載する。これらの具体例は、例示目的として示し、本発明は、これらの具体的な内容の一部または全体がなくても実施することができる。明確にするため、本発明に関する技術分野で知られている専門的なデータは、詳細に記載していないが、本発明は無用に不明瞭とはならない。
【０００７】
一般に、集積回路設計のネットは、駆動セルから受信セルまで信号を搬送する配線接続を含む。ネットリストは、集積回路設計でネットを含む出力ピンの位置を指定し、出力ピンの位置は通常、配線前に確定される。配線時にネットを含む出力ピンを配線することは、ネットの実装形態を定義する。特定のネットに関連する出力ピンおよび／または配線接続は、集積回路設計の１または複数の（金属）層全体に分散する可能性がある。
【０００８】
集積回路設計の配線には、さまざまな技法および設計が存在する。スパイン配線は、フィッシュボーン配線としても知られており、他の配線技法より多くの利点を備えている。たとえば、スパイン配線は、相互接続部のビアおよびジョグを減少でき、タイミング遅延および信号品位などの因子に関して、配線品質を改善することができる。
【０００９】
既存のスパイン配線技法では、集積回路設計を含む複数のネットのそれぞれへのメインスパインの割当は通常、一度に１つのネットに対して逐次実行される。そのような場合には、ネットはその重要順に基づいて順位付けされ、メインスパインが割り当てられる発見的手法を使用してもよい。既存のスパイン配線技法は通常、単一のレベルのスパイン配線を含む。図１は、単一のネット１００に関する典型的な従来技術のスパイン配線による結果を示す。本実施例では、メインスパイン１０２は水平に配線される。特定のネット１００に関してメインスパイン１０２が選択されると、ネットの各ピン（図１に丸円で示す）は、ステッチングスパイン１０４などのステッチングスパインによって直接メインスパイン１０２に接続される。
【００１０】
本願明細書に、改良されたスパイン配線技法を開示する。いくつかの実施形態では、マルチレベルのスパイン配線が使用される。すなわち、単一のレベル以上のスパイン配線が使用される。いくつかの実施形態で、ネットおよび／またはそのグループのスパインの割当を少なくとも部分的に最適化する複数のネットを配線するための体系的手法が使用されている。１または複数の開示する技法を使用して、従来の配線解決策に比して、総配線長、伝搬遅延、スキュー時間などの１または複数の因子が改善されている改良した集積回路トポロジーを実現してもよく、提供する実施例のいくつかには、スパインの水平および／または垂直な配線を記載しているが、本願明細書に開示する技法は、スパインの他の向きにも同じように使用してもよい。本願明細書には２つのレベルのスパイン配線は提供する実施例のいくつかに記載するが、開示する技法はスパイン配線の任意の数のレベルに同じように増加させてもよい。
【００１１】
図２Ａは、単一のネット２００に関する２つのレベルのスパイン配線の実施形態を示す。本実施例では、メインスパイン２０２は水平方向に配線される。しかし、ネット２００のピン（図２Ａに丸円で示す）は、メインスパイン２０２に直接接続されない。その代わりに、ネット２００のピンは、グループに分割され、第２のレベルのスパイン２０４〜２０８は、各グループによって共有される。本実施例では、第２のスパイン２０４〜２０８は、メインスパイン２０２に対して実質的に垂直に、あるいは、直交するように配線される。特に、第２のレベルのスパイン２０４は、ピン２１０〜２１４を含むグループに割り当てられ、第２のレベルのスパイン２０６は、ピン２１６〜２２２を含むグループに割り当てられ、第２のレベルのスパイン２０８はピン２２４〜２３０を含むグループに割り当てられる。ネット２００の各ピン２１０〜２３０は、そのグループに割り当てられた第２のレベルのスパイン２０４〜２０８に接続される。本実施例では、メインスパイン２０２は水平であり、第２のレベルのスパイン２０４〜２０８は垂直であるが、他の実施態様では、メインスパインは垂直であってもよく、第２のレベルのスパインは水平であってもよい。
【００１２】
一般に、ネットの総配線長は、全スパインの配線長と、ネットを含むピンを対応するスパインに接続する配線長とを合計して算出される。たとえば、２つのレベルのスパイン配線に関しては、ネットの総配線長は、メインスパインの長さ、第２のレベルの全スパインの長さおよびネットを含む各ピンから対応する第２のレベルのスパインまでの長さを合計して算出される。図２Ａのネット２００に関しては、たとえば、ネット２００の総配線長は、メインスパイン２０２の長さ、第２のレベルのスパイン２０４〜２０８の長さ、各ピン２１０〜２１４と第２のレベルのスパイン２０４との間の長さ、各ピン２１６〜２２２と第２のレベルのスパイン２０６との間の長さおよび各ピン２２４〜２３０と第２のレベルのスパイン２０８との間の長さの合計である。
【００１３】
図２Ａに関して記載するように、いくつかの実施形態では、ネットを含むピンは１または複数のグループに分割される。ピンは、ネットの総配線長を最小にするようにグループに分割することができる。１または複数の適切な統計的技法を使用して、ネットを含むピンをグループに分割してもよい。たとえば、ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムは、ピンをグループに分割するのに使用される。ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムでは、所定のｎ個の測定値のセット（ｘ１、ｘ２、…、ｘｎ）（各測定値はｄ次元ベクトルを含む）が、以下の方程式によって得られるクラスタ内の二乗和を最小にするようにｋ≦ｎ個のセットＳ＝（Ｓ１、Ｓ２、…、Ｓｋ）に分割される（式中μｉは、Ｓｉ内の点の平均である）。
【００１４】
【数１】
2012118986.tif 000003
【００１５】
スパイン配線に関して、ネットのピンの配置は、配線前に確定されており、測定値のセットを含む。この場合には、各測定値または各ピンの位置は、ピンが直接接続されるスパインに対してピンの位置を特定する値を含む一次元ベクトル（つまりｄは１）を含む。メインスパインが水平である図２Ａの実施例では、垂直な第２のレベルのスパインの最適なｘ座標を求めるためには、ピンのｘ座標のみを対象とする必要がある。一方、メインスパインが垂直である実施態様では、水平な第２のレベルのスパインの最適なｙ座標を求めるためには、ピンのｙ座標のみを対象とする必要がある。
【００１６】
いくつかの実施形態では、ネットを含むピンは、改変したｋ−ｍｅａｎｓ法クラスタリングアルゴリズムに基づいてグループに分割される。そのようなアルゴリズムは、経験的または発見的に少なくとも部分的に決定してもよい。場合によっては、たとえば、平均値の代わりに中央値を使用することによって、および／または、各グループ内のピンは全て、メインスパインの同じ側に位置するように、つまり、メインスパインの反対側のピンが、同一グループに分割しないようにグループに分割することによって、総配線長に関して良好な結果を得ることが可能である。そのような場合、ピンの分割問題は、各グループのピンがメインスパインの同じ側に配置されるように、メインスパインに対するピンの配置が考慮されるという制約のある一次元ｋ−ｍｅｄｉａｎ法クラスタリング問題としてモデル化される。この問題を解決するために、ロイドアルゴリズムなどの１または複数の周知の統計的アルゴリズムを使用してもよい。いくつかの実施形態では、最適なグループ数を見つけるために、全数検索を実行し、ｋは１〜ピンの数まで変化する。そのような場合、ｋが１であればネットのピンは全て１つのグループに分けられ、ｋがピンの数であればネットの各ピンはそれぞれの異なるグループに分類される。
【００１７】
図２Ｂは、ネットを配線するための処理の実施態様を示すフローチャートである。いくつかの実施形態では、処理２３２が図２Ａのネット２００の２つのレベルのスパイン配線を作成するのに使用される。処理２３２は、ネットの仕様を受信するステップ２３４で開始する。いくつかの実施形態では、ネットの仕様は、ネットを含むピンのセットの場所または位置を含む。いくつかの実施形態では、その仕様はネットリストおよび／または配置システムの出力を含む。ステップ２３６では、このネットに関してメインスパインが作成される。たとえば、メインスパイン配線が作成される。いくつかの実施形態では、ステップ２３６は、メインスパインに対して、複数の利用可能なメインスパイントラックからトラックを選択することを含む。ステップ２３８では、ネットを含むピンのセットは、コスト関数に少なくとも部分的に基づいて１または複数のグループに分割される。ピンの分割は、ｋ−ｍｅａｎｓ法クラスタリングアルゴリズムまたはｋ−ｍｅｄｉａｎ法クラスタリングアルゴリズムなどの統計的アルゴリズムに少なくとも部分的に基づいてもよい。いくつかの実施形態では、コスト関数は、配線長に少なくとも部分的に基づいている。ピンは、たとえば、各グループのピンがメインスパインの同じ側に配置されるように、メインスパインの位置に基づいて分割してもよい。ステップ２４０では、ネットの各グループに対してメインスパインに接続する第２のレベルのスパインが作成される。たとえば、第２のレベルのスパイン配線が作成される。いくつかの実施形態では、第２のレベルのスパインの場所または位置が、ステップ２３８のピンの分割に少なくとも部分的に基づいている。同じように、ステップ２３８のピンの分割は、第２のレベルのスパインに対する利用可能なトラックに少なくとも部分的に基づいてもよい。いくつかの実施形態では、ステップ２４０は、複数の利用可能な第２のレベルのスパイントラックから第２のレベルのスパイントラックを選択することを含む。ステップ２４２では、ネットの各グループの各ピンは、グループの第２のレベルのスパインに接続される。いくつかの実施形態では、さまざまな因子（たとえば、位置を変更できない既存の構成要素または構造、設計ルールの制限など）が、メインスパイン配線、第２のレベルのスパイン配線および第２のレベルの関連するスパインにピンを接続する配線の位置および場所を制約しうる。
【００１８】
図３は、配線計画を作成する処理の実施形態を示すフローチャートである。たとえば、プロセス３００は、集積回路またはその一部の配線計画を作成するために使用してもよい。すなわち、処理３００は、たとえば、可能な範囲内でネットのセットの総配線長を最小限に抑えるように、スパインの１または複数のレベルに位置を割り当てることによって、複数のネットを系統的に配線するのに使用してもよい。処理３００は、複数のネットの仕様を受信するステップ３０２で開始する。複数のネットは、集積回路設計またはその一部を含む。複数のネットの仕様は、ネットリストおよび／または配置システムの出力を含む場合もある。ステップ３０４では、メインスパインが割り当てることが可能なトラックのセットの仕様を受信する。トラックのセットの位置は、設計ルールおよび／またはユーザー仕様に基づいてもよい。
【００１９】
ステップ３０２で配線するネットのセットと、ステップ３０４でメインスパインを割り当てることが可能なトラックのセットとが与えられると、メインスパイントラックは、ステップ３０６でネットの各セットに割り当てられる。各メインスパイントラックは、多くとも単一ネットに割り当てられる。メインスパイントラックは、たとえば、可能な範囲内にネットのセットの総配線長を最小限に抑えるコスト関数に少なくとも部分的に基づいてネットに割り当てられる。いくつかの実施形態では、メインスパイントラックの少なくとも一部のそれぞれに対するネットの総配線長が計算され、その計算に基づいて最適なトラック割当が選択される。たとえばＮ個のネットを１セット配線する必要があり、メインスパインをＭ個の選択可能なトラックに割り当てることができる場合、場合によっては、Ｎ×Ｍのマトリクスが作成され、エントリーが特定のトラックに割り当てた特定のネットの総配線長を表す。そのような場合、全ネットの総コスト（たとえば総配線長）を最小にするトラック割当を選択することができる。
【００２０】
いくつかの実施形態では、特定のトラックに関してネットの総配線長を計算することは、最初に上記したピンの分割技法を使用してトラックの場所または位置に基づく最適なグループ数にネットのピンを分割することを含む。すなわち、異なるメインスパイントラックに関するネットの相対的なピンの位置は、メインスパイントラックの場所または位置に依存することから、同じピンの分割は、異なるメインスパイントラックに対して最適ではなく、適用すらできない可能性がある。たとえば、１つのメインスパイントラックの特定の側に配置されるネットのいくつかのピンは、異なるメインスパイントラックの反対側に配置してもよい。そのように、利用可能なメインスパイントラックのそれぞれに対して、あるいは、少なくともその一部に対して、総配線長のさらに精確な予測値を得るために、グループへのピンの分割を実行する必要がありうる。さらに、算出される総配線長は、ピンの分割に関する上記のアルゴリズムを使用して求められる最適な第２のレベルのスパインの場所または位置に基づく予測値を含んでもよい。実際の総配線長は、設計において第２のレベルのスパインの利用可能な位置に対する制限に基づいて異なる可能性がある。
【００２１】
図４は、ネットに割り当てるメインスパイントラックを求めるために使用するマトリクスの実施形態を示す。本実施例では、マトリクス４００の各行は、ネットに対応し、マトリクス４００の各列は選択可能なメインスパイントラックに対応する。マトリクス４００は、３つの選択可能なメインスパイントラック（すなわち、Ｔ１、Ｔ２およびＴ３）に関する２つのネット（すなわち、ｎｅｔ１およびｎｅｔ２）の総配線長エントリーを含む。いくつかの実施態様では、１または複数の総配線長エントリーは、推量である。図に示すように、トラックＴ１をｎｅｔ１に割り当てた場合、総配線長は５００であり、トラックＴ２をｎｅｔ１に割り当てた場合、総配線長は６００であり、トラックＴ３をｎｅｔ１に割り当てた場合、総配線長は４００となる。同じように、トラックＴ１、Ｔ２およびＴ３をｎｅｔ２に割り当てた場合、総配線長はそれぞれ、３００、７００および４００となる。本実施例では、最適の割当は、トラックＴ３をｎｅｔ１に、かつ、トラックＴ１をｎｅｔ２に割り当てることであり、総配線長は７００（つまり、４００＋３００）となる。
【００２２】
数学的には、マトリクス４００などのマトリクスを使用して、ネットの割当に対する最適のトラックを求めるという問題は、線形割当問題としてモデル化することができ、周知のアルゴリズムのうちいずれか１または複数を使用して、線形割当問題を解決することができる。たとえば、マトリクス４００などの構造を有するマトリクスに関しては、線形割当問題は、次のように形式的に定義することができる。Ｒ行およびＣ列を有するマトリクスの場合、マトリクスの全行に関するＭ（ｒ，ｃ）の合計が最小になるように各行ｒに対して一意の列ｃを求める。ただし、Ｍ（ｒ，ｃ）はマトリクスのｒ行目のｃ列目の値を示す。このような線形割当問題を解決するには、各トラックが多くとも単一のネットに割り当てられるように、ネットに対する最適なトラック割当を求めることが必要となる。そのような線形割当問題を解決することは、ネットに対してメインスパイントラックを割り当てることを含む。メインスパイントラックが、処理３００のステップ３０６でネットに割り当てられると、そのトラックに対する最適のピンが分割され、これによりネットに対するグループ数および第２のレベルのスパイン数は既知となる。
【００２３】
図３の処理３００のステップ３０８では、第２のレベルのスパインを割り当てることが可能な１セットのトラックのセットの仕様を受信する。トラックのセットの位置は、設計ルールおよび／またはユーザー仕様に基づいてもよい。いくつかの実施形態では、第２のレベルのスパインは、メインスパインに対して実質的に垂直または直交する位置にある。ステップ３１０では、第２のレベルのスパイントラックは、各ネットの各グループに割り当てられる。メインスパイントラックの割当方法と同じような系統的手法は、第２のレベルのスパイントラックをネットのグループに割り当てるのに使用してもよい。すなわち、第２のレベルのスパイントラックは、たとえば、可能な範囲内でネットのセットの総配線長を最小限に抑えるコスト関数に少なくとも部分的に基づいてグループに割り当ててもよい。所定のメインスパイントラック割当に対する各ネットの最適なピンの分割は、ステップ３０６時に求めた時点で既知となる。しかし、ピンの分割またはグループ分けは、たとえば第２のレベルのスパイントラックの実際に利用可能な場所または位置に基づいて、ステップ３１０で更新してもよい。第２のレベルのスパインには、ピンの分割の各グループが割り当てられる。このためｋ個の第２のレベルのスパインがｋ個のグループからなるピンの分割に必要である。対象とするネットの全セットが、合計Ｋ個のグループからなる場合、ネットのセットに対してＫ個の第２のレベルのスパインが必要となる。
【００２４】
いくつかの実施形態では、第２のレベルのスパインにグループのピンを接続し、その第２のレベルのスパインを関連するネットのメインスパインに接続するのに必要な総配線長は、第２のレベルのスパイントラックの少なくとも一部それぞれのグループに対して算出され、最適な第２のレベルのスパイントラックの割当は、そのような計算に基づいて選択される。たとえば、対象とするネットの全セットに関して、Ｋ個のグループが存在し、第２のレベルのスパインをＴ個の選択可能なトラックに割り当てることができる場合、場合によってはＫ×Ｔの行列が作成され、エントリーが特定の第２のレベルのスパイントラックに割り当てられる特定のグループの総配線長を表す。そのような場合、全グループの総コスト（たとえば総配線長）を最小限にするトラック割当を選択してもよい。
【００２５】
図５は、図４のネットのグループの第２のレベルのスパイントラックの割当を求めるのに使用されるマトリクスの実施形態を示す。本実施例では、マトリクス５００の各行はネットのグループに対応し、マトリクス５００の各列は選択可能な第２のレベルのスパイントラックに対応する。図４に関して記載したように、ｎｅｔ１およびｎｅｔ２のメインスパインを割り当てた後、マトリクス５００に示すように、ｎｅｔ１のピンは、３つのグループ（すなわち、ｎｅｔ１．ｇ１、ｎｅｔ１．ｇ２およびｎｅｔ１．ｇ３）に分割され、ｎｅｔ２のピンは、２つのグループ（すなわち、ｎｅｔ２．ｇ１とｎｅｔ２．ｇ２）に分割される。マトリクス５００は、６つの第２のレベルの選択可能なスパイントラック（すなわち、Ｔ１、Ｔ２、Ｔ３、Ｔ４、Ｔ５およびＴ６）に関して、５つのグループ（すなわち、ｎｅｔ１．ｇ１、ｎｅｔ１．ｇ２、ｎｅｔ１．ｇ３、ｎｅｔ２．ｇ１およびｎｅｔ２．ｇ２）それぞれの配線長エントリーを含む。メインスパイン割当問題と同じように、第２のレベルのスパイン割当問題は、線形割当問題としてモデル化し、周知のアルゴリズムうちのいずれか１または複数を使用して、線形割当問題を解決することができる。そのような問題の最適な解決法は、ネットのセットに対する総配線長を最小にする第２のレベルのスパイントラック割当をもたらす。図５の実施例に関して、最適解は、次のトラック割当、Ｔ４のｎｅｔ１．ｇ１（配線長＝３０）、Ｔ２のｎｅｔ１．ｇ２（配線長＝３０）、ｎｅｔ１．ｇ３のＴ５（配線長＝５０）、Ｔ１のｎｅｔ２．ｇ１（配線長＝４０）およびＴ６のｎｅｔ２．ｇ２（配線長＝４０）を含む。
【００２６】
図３の処理３００のステップ３１２では、配線計画は、スパインおよびピンを配線することによって作成される。メインスパインは、ステップ３０６のトラック割当の結果に基づいて作成され、第２のレベルのスパインは、ステップ３１０のトラック割当の結果に基づいて作成され、各ピンは、ステップ３１２で対応する第２のレベルのスパインに配線または接続され、配線計画を作成する。
【００２７】
記載するように、開示する技法は、改良した集積回路トポロジーを実現するように、配線資源の消費を最適化するか、あるいは、少なくともその消費を減らすか最小限にするように、集積回路またはその一部のスパインの位置を割り当てるために系統的に使用してもよい。開示する技法は、設計に関する総配線長、伝搬遅延、スキュー時間などを減少させたり、最小限にするために使用してもよい。２つのレベルのスパイン配線は、図２〜５の実施例に記載しているが、開示する技法は、さまざまなレベルのスパイン配線に関して類似して使用してもよい。さらに、開示する技法は、集積回路全体またはその一部を最適化するのに使用してもよい。
【００２８】
上記の実施態様は、理解を容易にする目的で詳細に説明しているが、本発明は、これに限定されない。本発明を実装する数多くの代替的方法が存在する。開示する実施形態は、説明を目的とし、限定することを意図していない。
【図１】
2012118986.tif 000004
【図２Ａ】
2012118986.tif 000005
【図２Ｂ】
2012118986.tif 000006
【図３】
2012118986.tif 000007
【図４】
2012118986.tif 000008
【図５】
2012118986.tif 000009
【外国語明細書】
2012118986000001.pdf