(57)【要約】【課題】半導体集積回路の配線設計において、配線領域上の配線要求群に対して配線経路探索を効率的に行う半導体集積回路設計装置を提供する。【解決手段】チップ情報記憶部１９により、ネットリスト及び配線格子情報が記憶される。配線要求クラスタリング部１２により、配線要求クラスタが生成される。配線格子クラスタリング部１３により、配線格子クラスタが生成される。配線経路探索繰返し手段（配線経路探索部１４、配線要求クラスタ分解部１５、経路探索終了条件判定部１６、配線格子クラスタ分解部１７、配線格子レベル判定部１８）により、配線要求クラスタに対する配線経路探索が配線格子クラスタ上で行われ、配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索が、配線経路探索用の配線格子が最細粒度配線格子のレベルに分解されるまで繰り返される。【選択図】図１
2011257885.tif 000002
【特許請求の範囲】
【請求項１】
設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を記憶する記憶装置と、
該記憶装置に記憶されている前記ネットリストに対応した配線要求のクラスタリングを、前記配線格子のクラスタリング状況に応じて階層的に行って配線要求クラスタを生成する配線要求クラスタリング手段と、
前記記憶装置に記憶されている前記配線格子情報に対応した前記配線格子のクラスタリングを階層的に行って配線格子クラスタを生成する配線格子クラスタリング手段とを有する半導体集積回路設計装置であって、
前記配線要求クラスタに対する配線経路探索を前記配線格子クラスタ上で行い、前記配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索を、配線経路探索用の前記配線格子が最細粒度配線格子のレベルに分解されるまで繰り返す配線経路探索繰返し手段が設けられていることを特徴とする半導体集積回路設計装置。
【請求項２】
前記配線経路探索繰返し手段は、
前記配線要求クラスタに対する前記配線経路探索を前記配線格子クラスタ上で行う配線経路探索手段と、
該配線経路探索手段で前記配線要求クラスタに対する前記配線経路探索が成功したか否かを判断する経路探索終了条件判定手段と、
前記配線経路探索手段で前記配線経路探索に失敗した場合、失敗した前記配線要求に対して、配線要求の１階層分解を行う配線要求クラスタ分解手段と、
前記配線経路探索用の前記配線格子が前記最細粒度配線格子のレベルに分解されているか否かを判定する配線格子レベル判定手段と、
現在の配線格子が前記最細粒度配線格子レベルでない場合、前記配線格子クラスタを１階層分解する配線格子クラスタ分解手段とを備えてなることを特徴とする請求項１記載の半導体集積回路設計装置。
【請求項３】
前記配線要求クラスタリング手段は、
接続要求のある端子集合の分布が現在の配線格子単位で同一である配線要求の集合を１つにまとめることにより、前記配線要求クラスタを生成する構成とされ、
前記配線要求クラスタ分解手段は、
前記配線要求クラスタリング手段による前記配線要求クラスタの生成過程を逆にたどることにより、前記配線要求の１階層分解を行う構成とされていることを特徴とする請求項２記載の半導体集積回路設計装置。
【請求項４】
前記経路探索終了条件判定手段は、
前記配線要求に含まれる全ての接続要求端子を接続する配線経路を発見することができた場合に、前記配線経路探索が成功したことを判定する構成とされていることを特徴とする請求項２又は３記載の半導体集積回路設計装置。
【請求項５】
前記配線格子クラスタリング手段は、
隣接する所定数の配線格子を一つの配線格子にまとめることにより前記配線格子クラスタを生成する構成とされ、
前記配線格子クラスタ分解手段は、
前記配線格子クラスタリング手段による前記配線格子クラスタの生成過程を逆にたどることにより、前記配線格子クラスタを１階層分解する構成とされていることを特徴とする請求項２、３又は４記載の半導体集積回路設計装置。
【請求項６】
設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を記憶する記憶装置と、
該記憶装置に記憶されている前記ネットリストに対応した配線要求のクラスタリングを、前記配線格子のクラスタリング状況に応じて階層的に行って配線要求クラスタを生成する配線要求クラスタリング手段と、
前記記憶装置に記憶されている前記配線格子情報に対応した前記配線格子のクラスタリングを階層的に行って配線格子クラスタを生成する配線格子クラスタリング手段とを有する半導体集積回路設計装置に用いられる配線設計方法であって、
配線経路探索繰返し手段が、前記配線要求クラスタに対する配線経路探索を前記配線格子クラスタ上で行い、前記配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索を、配線経路探索用の前記配線格子が最細粒度配線格子のレベルに分解されるまで繰り返す配線経路探索繰返し処理を行うことを特徴とする配線設計方法。
【請求項７】
コンピュータを、請求項１乃至５のいずれか一に記載の半導体集積回路設計装置として機能させることを特徴とする配線設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半導体集積回路設計装置、該設計装置に用いられる配線設計方法及び配線設計プログラムに係り、特に、半導体集積回路の配線設計を行うときに、配線領域上の配線要求群に対して配線経路探索を行う場合に用いて好適な半導体集積回路設計装置、該設計装置に用いられる配線設計方法及び配線設計プログラムに関する。
【背景技術】
【０００２】
半導体集積回路の設計では、内部回路の接続状態を表すデータにより、ネットリストが構成される。ネットリストは、論理演算や論理値保持を行うブロックと、同ブロックの端子間を接続するネット（又は、配線要求という）との集合で構成されている。そして、ネットリストに基づいて、ブロックが設計対象領域に配置され、次に、ブロック端子間の各ネットに対して配線経路が決定される。ここで、ブロックを配置する位置の決定を配置設計、及び、ネットの配線経路の決定を配線設計という。現在の大規模な半導体集積回路のネットリストでは、一千万を超える配線要求が１チップ上に存在するが、この膨大な数の配線要求に対応して配線経路を効率よく決定するために、配線設計は、概略配線処理及び詳細配線処理の２段階に分けて行われる。
【０００３】
概略配線処理では、たとえば、設計対象領域を大まかな格子に分割し、この格子を単位とする配線経路が決定される。また、詳細配線処理では、概略配線処理で決定された配線経路がカバーする格子内で実際の配線格子に相当する粒度（最細粒度の配線格子上）で配線経路が決定される。これにより、設計対象領域全体を対象として細粒度の配線経路探索を行う必要がなくなる、すなわち、経路探索範囲を概略配線処理が決定した格子内に限定して、詳細配線経路探索を行うことが可能となるため、配線経路探索処理が効率化される。ここで、配線格子の各境界には、通過できる配線の本数が制約として設定されるが、この本数を、配線通過容量という。概略配線処理では、各格子境界を通過する配線数が境界の配線通過容量以下になるように配線経路が割り当てられる。このため、詳細配線処理は、各境界の配線通過容量が“１”である概略配線処理と捉えることもできる。
【０００４】
この種の関連する半導体集積回路の配線処理は、たとえば図１４に示すものがある。
図１４（ａ）に示すように、配線領域に４本の配線要求（ネットＮＲ）が存在している。この場合、最細粒度の配線格子は、４×４である。まず、概略配線処理では、図１４（ｂ）に示すように、２×２の配線格子ＮＧ上で概略配線経路ＮＣが決定される。この場合、各境界の配線通過容量は“２”となっている。次に、詳細配線処理では、図１４（ｃ）に示すように、４×４の配線格子ＮＢ上で、概略配線が割り当てた格子内に探索範囲を限定して、詳細配線経路ＮＤの探索を行う。この場合、各境界の配線通過容量は“１”となっている。上記概略配線処理を多階層化する技術としては、たとえば、非特許文献１に記載されたものがある。この非特許文献１では、概略配線処理を多階層化する技術について記載され、この技術では、概略配線処理での配線格子の粒度が、たとえばＶ形又はΛ形の多階層化配線処理フローに基づいて段階的に変化する。
【０００５】
また、特許文献１に記載された配線設計支援方法では、プリント基板の配線設計を行う場合に、特定の信号群の配線遅延を揃えるなどの目的で、配線要求がクラスタリングされて処理される。すなわち、図１５（ａ）に示すように、複数の配線要求のクラスタリングにより配線要求クラスタＲＣが生成され、配線要求数が“４”となっている。次に、図１５（ｂ）に示すように、生成された配線要求クラスタＲＣに対する配線要求クラスタ経路ＲＥが決定され、最後に、図１５（ｃ）に示すように、配線要求クラスタＲＣが分解されて、各配線要求に対する詳細配線経路ＲＤが決定される。これらの詳細配線経路ＲＤの決定時に、配線要求クラスタ経路情報を利用することにより、クラスタリングされた配線要求群に対する配線経路をまとめて制御することが可能となる。
【０００６】
また、特許文献２に記載された半導体集積回路のレイアウト設計方法では、配置領域上に互いに間隔をおいて配置された機能ブロック及び入出力ブロックにおける各ブロック同士の間の配線領域に、互いに隣接する一対のトラック又はカラムに挟まれた領域からなる配線グリッド領域が形成される。配線グリッド領域を配線領域とみなす迷路法を用いて、各ブロック間の配線領域上の配線経路が探索される。このとき、回路接続情報に基づいて、配線グリッド領域の各単位配線領域を通過する配線又はヴィアが占有するトラックが、配線グリッド領域と対応する配線計数領域の各単位配線計数領域ごとに計数されて保持される。この計数値を用いて、ブロック間の配線領域に必要な配線領域幅が見積もられる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−２４３２３０号公報
【特許文献２】特開２０００−３４９１５６号公報
【非特許文献】
【０００８】
【非特許文献１】T.-C.Chen,Y.-W.Chang,andS.-C.Lin,“A Novel Framework for Multilevel Full-ChipGridless Routing ”in Proc.IEEE/ACM Asia SouthPacificDesign Automation conference,Jan.2006,pp.636-641
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上記関連技術では、次のような課題があった。
すなわち、図１４に示す配線処理における多階層化では、配線領域が階層的に分割処理されるが、配線要求は１本毎に個別に扱っているため、配線経路を探索する回数を削減することができず、配線要求数が増大した場合に、処理時間も比例して増加する可能性がある。また、バスなどの配線要求群の配線経路をまとめて制御することが困難である。
【００１０】
また、特許文献１に記載された配線設計支援方法では、配線経路の探索処理が領域的に階層化されていないので、１つの配線経路の探索処理に時間がかかる可能性がある。また、クラスタリング対象とする配線要求の集合は、人手で指定する必要があり、半導体集積回路のような膨大な数の配線要求がある場合には、適切にクラスタリングすることが困難になるという課題がある。
【００１１】
特許文献２に記載されたレイアウト設計方法では、迷路法を用いて各ブロック間の配線領域上の配線経路が探索され、ブロック間の配線領域幅の見積もりが短期間に高精度で行われるが、この発明とは構成や処理方法が異なる。
【００１２】
この発明は、上述の事情に鑑みてなされたもので、配線領域上の配線要求群に対して配線経路探索を効率的に行う半導体集積回路設計装置、該設計装置に用いられる配線設計方法及び配線設計プログラムを提供することを目的としている。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、この発明の第１の構成は、設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を記憶する記憶装置と、該記憶装置に記憶されている前記ネットリストに対応した配線要求のクラスタリングを、前記配線格子のクラスタリング状況に応じて階層的に行って配線要求クラスタを生成する配線要求クラスタリング手段と、前記記憶装置に記憶されている前記配線格子情報に対応した前記配線格子のクラスタリングを階層的に行って配線格子クラスタを生成する配線格子クラスタリング手段とを有する半導体集積回路設計装置に係り、前記配線要求クラスタに対する配線経路探索を前記配線格子クラスタ上で行い、前記配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索を、配線経路探索用の前記配線格子が最細粒度配線格子のレベルに分解されるまで繰り返す配線経路探索繰返し手段が設けられていることを特徴としている。
【００１４】
この発明の第２の構成は、設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を記憶する記憶装置と、該記憶装置に記憶されている前記ネットリストに対応した配線要求のクラスタリングを、前記配線格子のクラスタリング状況に応じて階層的に行って配線要求クラスタを生成する配線要求クラスタリング手段と、前記記憶装置に記憶されている前記配線格子情報に対応した前記配線格子のクラスタリングを階層的に行って配線格子クラスタを生成する配線格子クラスタリング手段とを有する半導体集積回路設計装置に用いられる配線設計方法に係り、配線経路探索繰返し手段が、前記配線要求クラスタに対する配線経路探索を前記配線格子クラスタ上で行い、前記配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索を、配線経路探索用の前記配線格子が最細粒度配線格子のレベルに分解されるまで繰り返す配線経路探索繰返し処理を行うことを特徴としている。
【発明の効果】
【００１５】
この発明の構成によれば、半導体集積回路の配線設計において、配線領域上の配線要求群に対して配線経路探索を効率的に行う半導体集積回路設計装置を提供することができる。
【図面の簡単な説明】
【００１６】
【図１】この発明の一実施形態である半導体集積回路設計装置の要部の構成を示すブロック図である。
【図２】図１の半導体集積回路配線設計装置１０を構成するコンピュータの要部の電気的構成を示すブロック図である。
【図３】図１の半導体集積回路配線設計装置に用いられる配線設計方法を示すフローチャートである。
【図４】配線要求及び初期の配線格子の例を示す図である。
【図５】第１階層の配線要求クラスタリングの例を示す図である。
【図６】第１階層の配線格子クラスタリングの例を示す図である。
【図７】第２階層の配線要求クラスタリングの例を示す図である。
【図８】経路探索が失敗する例を示す図である。
【図９】第２階層における配線要求の分解の例を示す図である。
【図１０】第２階層で経路探索が成功する例を示す図である。
【図１１】第２階層における配線格子クラスタ分解の例を示す図である。
【図１２】第１階層における配線要求クラスタ分解の例を示す図である。
【図１３】第１階層における配線経路探索結果の例を示す図である。
【図１４】関連する半導体集積回路の配線処理を示す図である。
【図１５】特許文献１に記載された配線設計支援方法を示す図である。
【発明を実施するための形態】
【００１７】
上記配線経路探索繰返し手段（配線経路探索部、配線要求クラスタ分解部、経路探索終了条件判定部、配線格子クラスタ分解部、配線格子レベル判定部）が、上記配線要求クラスタに対する上記配線経路探索を上記配線格子クラスタ上で行う配線経路探索手段（配線経路探索部）と、該配線経路探索手段（配線経路探索部）で上記配線要求クラスタに対する上記配線経路探索が成功したか否かを判断する経路探索終了条件判定手段（経路探索終了条件判定部）と、上記配線経路探索手段（配線経路探索部）で上記配線経路探索に失敗した場合、失敗した上記配線要求に対して、配線要求の１階層分解を行う配線要求クラスタ分解手段（配線要求クラスタ分解部）と、配線経路探索用の上記配線格子が上記最細粒度配線格子のレベルに分解されているか否かを判定する配線格子レベル判定手段（配線格子レベル判定部）と、現在の配線格子が上記最細粒度配線格子レベルでない場合、上記配線格子クラスタを１階層分解する配線格子クラスタ分解手段（配線格子クラスタ分解部）とを備える半導体集積回路設計装置を実現する。
【００１８】
また、上記配線要求クラスタリング手段（配線要求クラスタリング部）は、接続要求のある端子集合の分布が現在の配線格子単位で同一である配線要求の集合を１つにまとめることにより、上記配線要求クラスタを生成する構成とされ、上記配線要求クラスタ分解手段（配線要求クラスタ分解部）は、上記配線要求クラスタリング手段（配線要求クラスタリング部）による上記配線要求クラスタの生成過程を逆にたどることにより、上記配線要求の１階層分解を行う構成とされている。また、上記経路探索終了条件判定手段（経路探索終了条件判定部）は、上記配線要求に含まれる全ての接続要求端子を接続する配線経路を発見することができた場合に、上記配線経路探索が成功したことを判定する構成とされている。
【００１９】
また、上記配線格子クラスタリング手段（配線格子クラスタリング部）は、隣接する所定数の配線格子を一つの配線格子にまとめることにより上記配線格子クラスタを生成する構成とされ、上記配線格子クラスタ分解手段（配線格子クラスタ分解部）は、上記配線格子クラスタリング手段（配線格子クラスタリング部）による上記配線格子クラスタの生成過程を逆にたどることにより、上記配線格子クラスタを１階層分解する構成とされている。
【実施形態】
【００２０】
図１は、この発明の一実施形態である半導体集積回路設計装置の要部の構成を示すブロック図である。
この形態の半導体集積回路設計装置は、同図に示すように、半導体集積回路配線設計装置１０であり、チップ情報受付部１１と、配線要求クラスタリング部１２と、配線格子クラスタリング部１３と、配線経路探索部１４と、配線要求クラスタ分解部１５と、経路探索終了条件判定部１６と、配線格子クラスタ分解部１７と、配線格子レベル判定部１８と、チップ情報記憶部１９とから構成されている。チップ情報受付部１１は、チップ情報を受け付けてチップ情報記憶部１９に記憶させる。チップ情報は、設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を有している。チップ情報記憶部１９は、たとえば、ＲＡＭ（Random Access Memory）などで構成され、チップ情報を記憶する。
【００２１】
配線要求クラスタリング部１２は、チップ情報記憶部１９に記憶されているネットリストの上記接続状態に対応した配線要求のクラスタリングを、上記配線格子のクラスタリング状況に応じて階層的に行って配線要求クラスタを生成する。この場合、配線要求クラスタリング部１２は、接続要求のある端子集合の分布が現在の配線格子単位で見て完全に同一である配線要求の集合を一つにまとめることにより、配線要求クラスタを生成する。これにより生成された配線要求クラスタは、次回の配線要求クラスタリングの対象要素となる。
【００２２】
また、配線要求クラスタリング部１２は、一つのクラスタリングに含まれる配線要求数が大きくなりすぎ、問題が生じる場合は、その数に上限を与え、クラスタリングサイズの制限を行う。また、配線要求クラスタリング部１２は、クラスタリング対象を選択する際、論理情報などを基に、配線経路が近くなることが望ましい配線要求群を優先してクラスタリング対象とすることもある。配線格子クラスタリング部１３は、チップ情報記憶部１９に記憶されている配線格子情報に対応した配線格子のクラスタリングを階層的に行って配線格子クラスタを生成する。この場合、配線格子クラスタリング部１３は、隣接する所定数の配線格子（たとえば、隣接する２×２の配線格子）を一つの配線格子にまとめることにより配線格子クラスタを生成する。これにより生成された配線格子クラスタは、次回の配線格子クラスタリングの対象要素となる。
【００２３】
配線経路探索部１４は、上記配線要求クラスタに対する配線経路探索を上記配線格子クラスタ上で行う。配線格子クラスタの各境界を通過できる配線経路の数には限界（配線通過容量）があり、配線経路の数が配線通過容量を超えた場合に、配線経路探索の失敗が発生する。経路探索終了条件判定部１６は、上記配線要求クラスタに対する配線経路探索が成功したか否かを判断する。この場合、経路探索終了条件判定部１６は、上記配線要求に含まれる全ての接続要求端子を接続する配線経路を発見することができた場合に、上記配線経路探索が成功したことを判定する。配線要求クラスタ分解部１５は、配線経路探索部１４で配線経路探索に失敗した場合、失敗した配線要求に対して、配線要求の１階層分解を行う。特に、この実施形態では、配線要求クラスタ分解部１５は、配線要求クラスタリング部１２による配線要求クラスタの生成過程を逆にたどることにより、上記配線要求の１階層分解を行う。
【００２４】
配線格子レベル判定部１８は、配線経路探索用の配線格子が予め設定されている最細粒度配線格子のレベルに分解されているか否かを判定する。最細粒度とは、チップ情報受付部１１が受け付けたチップ情報に含まれる配線格子の粒度を示す。配線格子クラスタ分解部１７は、現在の配線格子が最細粒度配線格子レベルでない場合、上記配線格子クラスタを１階層分解する。特に、この実施形態では、配線格子クラスタ分解部１７は、配線格子クラスタリング部１３による上記配線格子クラスタの生成過程を逆にたどることにより、上記配線格子クラスタを１階層分解する。上記配線経路探索部１４、配線要求クラスタ分解部１５、経路探索終了条件判定部１６、配線格子クラスタ分解部１７及び配線格子レベル判定部１８により、配線経路探索繰返し手段が構成されている。この配線経路探索繰返し手段は、上記配線要求クラスタに対する配線経路探索を上記配線格子クラスタ上で行い、上記配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索を、配線経路探索用の前記配線格子が最細粒度配線格子のレベルに分解されるまで繰り返す。なお、この半導体集積回路配線設計装置１０は、専用ＩＣなどのハードウエアで構成することができるが、一般的なコンピュータにより構成することもできる。
【００２５】
図２は、図１の半導体集積回路配線設計装置１０を構成するコンピュータの要部の電気的構成を示すブロック図である。
このコンピュータは、図２に示すように、入出力部２１と、表示部２２と、メモリ２３と、ＣＰＵ（Central Processing Unit）２４と、記憶ユニット２５と、バス２６とから構成されている。バス２６は、上記各部を接続する。入出力部２１は、ネットワークなどに接続するためのインタフェースである。表示部２２は、液晶表示装置などで構成され、各種の表示を行う。メモリ２３は、ＲＯＭ（Read Only Memory）やＲＡＭなどで構成される記憶装置である。ＣＰＵ２４は、コンピュータの制御装置としての機能を有している。記憶ユニット２５は、ハードディスクなどで構成され、配線設計プログラムを格納する。このコンピュータでは、ＣＰＵ２４により、記憶ユニット２５に記憶されている配線設計プログラムがメモリ２３に読み出されて実行されることにより、図１中の各部の機能が同メモリ２３上に構築されて制御される。
【００２６】
図３は、図１の半導体集積回路配線設計装置に用いられる配線設計方法を示すフローチャート、図４は、配線要求及び初期の配線格子の例を示す図、図５は、第１階層の配線要求クラスタリングの例を示す図、図６は、第１階層の配線格子クラスタリングの例を示す図、図７は、第２階層の配線要求クラスタリングの例を示す図、図８は、経路探索が失敗する例を示す図、図９は、第２階層における配線要求の分解の例を示す図、図１０は、第２階層で経路探索が成功する例を示す図、図１１は、第２階層における配線格子クラスタ分解の例を示す図、図１２は、第１階層における配線要求クラスタ分解の例を示す図、及び図１３が、第１階層における配線経路探索結果の例を示す図である。
これらの図を参照して、この形態の半導体集積回路配線設計装置に用いられる配線設計方法の処理内容について説明する。
【００２７】
この半導体集積回路配線設計装置１０では、記憶装置（チップ情報記憶部１９）により、設計対象となる半導体集積回路の内部回路の接続状態を表すネットリスト及び設計対象領域を分割するための配線格子を表す配線格子情報を有するチップ情報が記憶される。配線要求クラスタリング手段（配線要求クラスタリング部１２）により、記憶装置（チップ情報記憶部１９）に記憶されているネットリストの上記接続状態に対応した配線要求のクラスタリングが上記配線格子のクラスタリング状況に応じて階層的に行われて配線要求クラスタが生成される。配線格子クラスタリング手段（配線格子クラスタリング部１３）により、記憶装置（チップ情報記憶部１９）に記憶されている上記配線格子情報に対応した配線格子のクラスタリングが階層的に行われて配線格子クラスタが生成される。
【００２８】
配線経路探索繰返し手段（配線経路探索部１４、配線要求クラスタ分解部１５、経路探索終了条件判定部１６、配線格子クラスタ分解部１７、配線格子レベル判定部１８）により、上記配線要求クラスタに対する配線経路探索が上記配線格子クラスタ上で行われ、配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索が、配線経路探索用の配線格子が最細粒度配線格子のレベルに分解されるまで繰り返される（配線経路探索繰返し処理）。
【００２９】
すなわち、図３に示すように、ネットリストと配線格子とを含む半導体集積回路のチップ情報がチップ情報記憶部１９に記憶される（ステップＡ１）。ネットリストに含まれる配線要求の配線格子クラスタリング状況に応じた配線要求クラスタリング部１２によるクラスタリング（ステップＡ２）と、チップ情報に含まれる配線格子の配線格子クラスタリング部１３によるクラスタリング（ステップＡ３）とが、階層的に繰り返し行われる。配線経路探索部１４により、クラスタリングされた各配線要求に対する配線経路探索が、クラスタリングされた配線格子上で行われ（ステップＡ４）、経路探索終了条件判定部１６により、配線経路探索が成功したか否かが判定される（ステップＡ５）。配線経路探索に失敗したクラスタ配線要求に対しては（ステップＡ５，Ｎ）、配線要求クラスタ分解部１５により配線要求の１階層分解が行われ（ステップＡ６）、再度ステップＡ４に戻り、配線要求クラスタ分解により生じた各配線要求の配線経路探索を再度行う処理が全ての配線要求クラスタ（ネットクラスタ）に対して繰り返される。
【００３０】
現在の経路探索用の配線格子クラスタでの、全ての配線要求クラスタの配線経路探索が終了した後（ステップＡ５，Ｙ）、配線格子レベル判定部１８により、現在の経路探索用の配線格子が最細粒度の配線格子レベルまで分解されているか否かが判定され（ステップＡ７）、最細粒度の配線格子レベルまで分解されている場合、終了する（Ａ７，Ｙ）。一方、現在の配線格子が最細粒度の配線格子レベルではない場合、配線格子クラスタ分解部１７により、階層的にクラスタリングされた配線格子が１階層分解され（ステップＡ８）、配線格子クラスタに合わせて、各配線要求クラスタの１階層分解が行われた後（ステップＡ９）、現在のクラスタ配線格子上で、再度、各クラスタ配線要求の配線経路探索が行われ（ステップＡ４）、上記配線格子クラスタの分解、配線要求クラスタの分解及び配線経路探索が、経路探索用の配線格子が最細粒度配線格子レベルに分解されるまで、繰り返される（ステップＡ４乃至ステップＡ９）。なお、ここで、ステップＡ２とステップＡ３の繰り返しを“ボトムアップクラスタリング処理”（ステップＡ２１）、及び、ステップＡ４からステップＡ９までの繰返しを“トップダウンクラスタ分解処理”（ステップＡ２２）という。
【００３１】
図１中のステップＡ１でチップ情報記憶部１９に入力されたチップ情報は、図４に示すように、配線要求ＮＲ及び初期の配線格子ＮＧであり、たとえば４本の配線要求が４×４の配線格子上に定義されている。ステップＡ２で配線要求クラスタリング部１２により行われる第１階層の配線要求クラスタリングは、接続要求のある端子集合の分布が現在の配線格子単位で完全に同一である配線要求の集合を一つにまとめることにより行われる。この場合、図５に示すように、配線要求［１］，［２］及び配線要求［３］，［４］が、それぞれ、配線格子単位で接続端子部分が完全に同一であるため、それぞれクラスタリングされている。また、同一格子内にある接続端子は接続端子クラスタＴＣとなり、配線要求は、該当のクラスタが含む配線要求数（［２］）を付属情報としてもつ配線要求クラスタＲＣとなる。これにより生成された配線要求クラスタは、次回の配線要求クラスタリングの対象要素となる。
【００３２】
ステップＡ３で配線格子クラスタリング部１３により行われる第１階層の配線格子クラスタリングでは、図６に示すように、図５中の隣接する２×２の配線格子が一つの配線格子にまとめられ、４×４の配線格子が２×２の配線格子にクラスタリングされて配線格子クラスタＧＣが生成される。これにより生成された配線格子クラスタＧＣは、次回の配線格子クラスタリングの対象要素となる。上記ステップＡ２とステップＡ３とは、前回のクラスタリング結果に基づいて繰り返し実行される。ステップＡ２で配線要求クラスタリング部１２により行われる第２階層の配線要求クラスタリングでは、図７に示すように、配線要求［１］，［２］，［３］，［４］がクラスタリングされ、一つのネットにまとめられている。この配線要求クラスタには、クラスタが含む元の配線要求数“４”が付随している。これらの配線要求及び配線格子の階層的クラスタリングは、配線格子数が十分小さくなるまで繰り返される。
【００３３】
ステップＡ４で配線経路探索部１４により配線経路探索が行われ、次に、ステップＡ５で経路探索終了条件判定部１６により、上記クラスタリングされた配線要求の配線経路探索が成功したか否かが判断される。この場合、配線要求に含まれる全ての接続要求端子を接続する配線経路が発見された場合に、配線経路探索が成功したと判定される。たとえば、図７に示す配線要求クラスタの配線経路探索は失敗している。その理由は、図８に示すように、配線要求クラスタは４つの配線要求からなっているが、配線格子クラスタの各境界は、配線通過容量ＢＰが［２］であり、２つの配線経路までしか通過できないことによる。
【００３４】
ステップＡ６で配線要求クラスタ分解部１５により行われる第２階層における配線要求の分解では、階層的にクラスタリングされた配線要求が１階層分解される。このクラスタ分解は、配線要求クラスタリング部１２での配線要求クラスタ生成過程を逆にたどることにより行われる。この場合、図９に示すように、図８の配線要求クラスタが１階層分解される。そして、ステップＡ４に戻り、配線経路探索部１４により、現在の配線要求クラスタに対する配線経路探索が現在の配線格子クラスタ上で、再度行われる。次に、経路探索終了条件判定部１６により、クラスタリングされた配線要求の配線経路探索が成功したか否かが判断される（ステップＡ５）。この結果、図９の配線要求クラスタの第２階層での配線経路探索は、成功と判定される。その理由は、図１０に示すように、各配線要求クラスタは２つの配線要求からなり、配線格子クラスタの各境界の配線通過容量が［２］であるためである。この図１０では、配線経路探索により発見された配線要求クラスタ経路ＲＨが表示されている。ここでは、現在の経路探索用の配線格子クラスタでの、全ての配線要求クラスタの配線経路探索が終了している。
【００３５】
ステップＡ７で配線格子レベル判定部１８により行われる判定では、図１０での配線格子クラスタが最細粒度レベルまで分解されていないため、配線格子クラスタ分解部１７により、図１１に示すように、第２階層における配線格子クラスタが１階層分解される（ステップＡ８）。ステップＡ４で配線経路探索部１４により行われる探索では、現在のクラスタ配線格子上で、再度、各クラスタ配線要求の配線経路探索が行われる。図１１では、各配線格子境界の配線境界容量を満たす配線経路が発見されないため、配線要求クラスタ分解部１５により、階層的にクラスタリングされている配線要求が、図１２に示すように１階層分解され（ステップＡ６）、同図１２の配線要求に対して、配線経路探索が再度行われる（ステップＡ４）。
【００３６】
このときの配線経路探索では、探索範囲が、上位階層で発見された経路がカバーする格子に限定して行われる。このため、経路探索処理にかかる時間が短縮される。このため、図１３に示すように、配線格子の配線通過容量を満たす配線経路が発見され、第１階層における配線経路探索の結果が得られる。次に、配線格子レベル判定部１８により、配線経路探索用の配線格子が、最細粒度の配線格子レベルまで分解されているか否かが判断され（ステップＡ７）、図１３では、配線格子クラスタが最細粒度レベルまで分解されているため、処理が終了する。
【００３７】
以上のように、この実施形態では、配線経路探索繰返し手段（配線経路探索部１４、配線要求クラスタ分解部１５、経路探索終了条件判定部１６、配線格子クラスタ分解部１７、配線格子レベル判定部１８）により、配線要求クラスタの分解、配線格子クラスタの分解及び配線経路探索が、配線経路探索用の配線格子が最細粒度配線格子のレベルに分解されるまで繰り返されるので、配線経路探索が効率的に行われ、処理時間が低減される。
【００３８】
以上、この発明の実施形態を図面により詳述してきたが、具体的な構成は同実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更などがあっても、この発明に含まれる。
たとえば、チップ情報記憶部１９で記憶するチップ情報は、あらかじめ、他の記録媒体からのコピーやユーザの入力操作などにより、記憶させておくようにしても良い。また、配線通過容量や配線要求数は、上記実施形態の値に限定されない。
【産業上の利用可能性】
【００３９】
この発明は、半導体集積回路の配線設計時に配線領域上の配線要求群に対して配線経路探索を行う半導体集積回路設計装置全般に適用できる。
【符号の説明】
【００４０】
１０      半導体集積回路配線設計装置（半導体集積回路設計装置）
１２      配線要求クラスタリング部（配線要求クラスタリング手段）
１３      配線格子クラスタリング部（配線格子クラスタリング手段）
１４      配線経路探索部（配線経路探索手段、配線経路探索繰返し手段の一部）
１５      配線要求クラスタ分解部（配線要求クラスタ分解手段、配線経路探索繰返し手段の一部）
１６      経路探索終了条件判定部（経路探索終了条件判定手段、配線経路探索繰返し手段の一部）
１７      配線格子クラスタ分解部（配線格子クラスタ分解手段、配線経路探索繰返し手段の一部）
１８      配線格子レベル判定部（配線格子レベル判定手段、配線経路探索繰返し手段の一部）
１９      チップ情報記憶部
【図１】
2011257885.tif 000003
【図２】
2011257885.tif 000004
【図３】
2011257885.tif 000005
【図４】
2011257885.tif 000006
【図５】
2011257885.tif 000007
【図６】
2011257885.tif 000008
【図７】
2011257885.tif 000009
【図８】
2011257885.tif 000010
【図９】
2011257885.tif 000011
【図１０】
2011257885.tif 000012
【図１１】
2011257885.tif 000013
【図１２】
2011257885.tif 000014
【図１３】
2011257885.tif 000015
【図１４】
2011257885.tif 000016
【図１５】
2011257885.tif 000017