(57)【要約】【課題】メガマクロブロックとの重なりが少ないクロック構造を広い解空間において効率良く探索できるようにすること。【解決手段】チップ情報に含まれるチップ領域を覆う格子を設定する格子設定部と、チップ領域の中心から格子の各セルの中心へクロック信号を分配するクロック構造であってチップ領域を格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する候補線分生成部と、チップ領域の分割方向及び分割順序を節点及び枝として有する２分木を生成する２分木生成部と、候補線分に設定された重みの総和である目的関数が最小となるように２分木の各節点の分割方向を選択する分割方向選択部と、各節点の分割方向が選択された２分木によって表されるクロック構造を生成するクロック構造生成部と、を有する。【選択図】図１
2011238011.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路のチップ領域を覆う格子を設定する格子設定部と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する候補線分生成部と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する２分木生成部と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する分割方向選択部と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成するクロック構造生成部と、を備えていることを特徴とする半導体集積回路設計装置。
【請求項２】
前記チップ領域に配置されたメガマクロブロックと前記候補線分との重なり量を求め、求めた重なり量に応じた重みを前記候補線分の重みとして設定する重み設定部をさらに備えていることを特徴とする、請求項１に記載の半導体集積回路設計装置。
【請求項３】
前記メガマクロブロックを前記チップ領域に配置するブロック配置部をさらに備えていることを特徴とする、請求項２に記載の半導体集積回路設計装置。
【請求項４】
前記メガマクロブロックの複数の配置のうちの前記目的関数が最小となる配置を選択するブロック配置選択部をさらに備えていることを特徴とする、請求項２又は３に記載の半導体集積回路設計装置。
【請求項５】
前記２分木は、前記チップ領域の分割に相当する節点と、該分割の順序に相当する枝とを有することを特徴とする、請求項１乃至４のいずれか１項に記載の半導体集積回路設計装置。
【請求項６】
前記候補線分生成部は、前記クロック信号を分配するクロック構造のうちの対称性を有するクロック構造を構成する線分の候補を、前記候補線分として生成することを特徴とする、請求項１乃至５のいずれか１項に記載の半導体集積回路設計装置。
【請求項７】
前記チップ領域を含むチップ情報を保持する記憶部をさらに備えていることを特徴とする、請求項１乃至６のいずれか１項に記載の半導体集積回路設計装置。
【請求項８】
前記チップ情報は、クロックネットとメガマクロブロックを含む半導体集積回路に関するチップ情報であることを特徴とする、請求項７に記載の半導体集積回路設計装置。
【請求項９】
コンピュータが、半導体集積回路のチップ領域を覆う格子を設定する工程と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する工程と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する工程と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する工程と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成する工程と、含むことを特徴とする半導体集積回路設計方法。
【請求項１０】
半導体集積回路のチップ領域を覆う格子を設定する処理と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する処理と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する処理と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する処理と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成する処理と、をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路を設計するための半導体集積回路設計装置、半導体集積回路設計方法及びプログラムに関し、特に、半導体集積回路のフロアプランとクロック構造を設計するための半導体集積回路設計装置、半導体集積回路設計方法及びプログラムに関する。
【背景技術】
【０００２】
同期式半導体集積回路は、演算及び演算の制御を行うための論理素子（論理セル又は論理ゲートともいう。）と、論理素子群の動作の同期を取るための順序回路素子（クロック素子又はフリップフロップともいう。）を有する。
【０００３】
各フリップフロップには、単一のクロック供給源（クロックソースともいう。）から周期的に発振するクロック信号を供給される。フリップフロップは、クロック信号の立ち上がり又は立下りに応じて、フリップフロップが保持しているデータを論理素子群に供給する。論理素子は、供給されたデータを入力として演算及び演算の制御を行い、その結果をフリップフロップに保存する。以上の処理は、周期的に変化するクロック信号の立ち上がり又は立下りに応じて繰り返される。
【０００４】
同期式回路を正常なタイミングで動作させるために理想的なクロック信号分配回路の配置配線は、半導体基板上のいずれの場所においても同一のクロック信号波形が得られることである。しかし、実際には、クロック信号を引き回す配線、及び、接続されているセルの配置によって、クロック信号が到着する時間はフリップフロップごとに異なる。
【０００５】
フリップフロップの中で、クロック信号が最も早く到達する時刻と、クロック信号が最も遅く到着する時刻との差をクロックスキュー（クロック信号到着時間差）という。クロックスキューが大きい場合には、回路が正常に動作しなくなる。したがって、クロック分配回路の配置配線においては、可能な限りクロックスキューを小さくすることが要求される。
【０００６】
図１２は、クロック分配回路の配置配線例を示す。図１２（ａ）は、クロック信号の供給先である末端セル１１１とクロックドライバセル１１２が示されている。図１２（ｂ）を参照すると、クロックドライバセル１１２からクロック信号の供給先である末端セル１１１へクロック信号を分配するためのレイアウトが行われている。クロック供給先の分布範囲が広い場合には、クロック信号の波形鈍りを抑えるために、クロック配線上に中継バッファ１１３を挿入する必要がある。なお、クロック信号の供給先である末端セル１１１は、フリップフロップのみならず、バッファも含む。
【０００７】
特許文献１において、クロックスキューを最小化するクロック信号分配方法が記載されている。特許文献１に記載された方法では、クロック分配回路を構築する際、末端セルから順に、ボトムアップ的に２分木を構成し、スキューがゼロとなるように（この状態を「ゼロスキュー」という。）２分木を生成する。この処理を末端セル１１１から順にクロックドライバセル１１２まで繰り返すことにより、図１２（ｂ）に示すクロック分配回路の配置配線を生成する。なお、図１２（ｃ）は、特許文献１に記載された方法によるクロック分配レイアウトの途中経過を示す。
【０００８】
近年、半導体製造プロセスの微細化により、製造バラツキによる遅延バラツキ問題が深刻となってきている。これに伴い、クロックスキューを最小化することが、さらに困難となってきている。製造バラツキ問題が深刻な半導体集積回路に対するクロック設計においては、製造バラツキの影響を最小化するために、クロックドライバセル１１２から各末端セル１１１への配線経路長、並びに、配線経路上の中継バッファ１１３の種類及び中継バッファ１１３が駆動する配線の容量が同一となるように、クロック信号を分配する配線のレイアウトを行なうことが好ましい。
【０００９】
以下では、クロック信号を分配する配線を「クロック構造」という。また、クロックドライバセル１１２から各末端セル１１１への配線経路長、並びに、配線経路上の中継バッファ１１３の種類及び中継バッファ１１３が駆動する配線の容量が同一となるようにレイアウトされたクロック構造を、「対称性を有するクロック構造」という。
【００１０】
図１３は、対称性を有するクロック構造の例を示す。図１２と同様に、クロックドライバセル１１２から末端セル１１１まで、中継バッファ１１３を介してクロック信号が分配されている。
【００１１】
なお、特許文献２において、製造バラツキ耐性を強化するために、特許文献１に記載された方法を拡張した方法が記載されている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平０５−０５４１００号公報
【特許文献２】特開２００７−１２３３３６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
特許文献２に記載された、ボトムアップ的に２分木を構成するゼロスキュー併合を繰り返す方法によると、対称性を有するクロック構造が生成されることが保証されない。特許文献２に記載された方法によると、製造バラツキによる遅延バラツキ問題の深刻化が進む最先端の半導体プロセスを用いて、実際のデバイス上でのクロックスキューが最小となるクロックレイアウトを生成することは困難となる。
【００１４】
上述のように、高性能な半導体集積回路を設計するには、クロックスキューを削減することが重要となる。すなわち、図１３に示したように、対称性を有するクロック構造を生成することが望まれる。しかし、実際の半導体レイアウト設計では、メモリ等のメガマクロブロックが障害となり、対称性を有するクロック構造を実現することが困難となる。
【００１５】
例えば、通常の半導体設計におけるフロアプランでは、図１４に示すように、メガマクロブロック６１が配置されている。多数のメガマクロブロック６１を含むフロアプランに対して、対称性を有するクロック構造のレイアウトを行おうとすると、図１４に示したように、メガマクロブロック６１と配線との間に重なりが生じる。しかし、メガマクロブロック６１上にはバッファを配置することはできないため、配線上に中継バッファ１１３を配置する際に、配置場所が制約される。
【００１６】
したがって、中継バッファ１１３の配置を含めて対称性を有するクロック構造を生成するには、メガマクロブロック６１との重なりが可能な限り少ない配線経路を実現する必要がある。メガマクロブロック６１との重なりが少ない配線経路を実現するには、図１３に示した単純なクロック構造に限らず、図１４の配線パタンと組み合わせた図１５に示すようなクロック構造も含むクロック構造の解空間を探索することが好ましい。
【００１７】
しかし、対称性を有するクロック構造を採用する場合には、クロック構造を決定した後、クロック構造に合わせてメモリの配置を含むフロアプランニングを行う方法、又は、フロアプランに合わせてクロック構造を微修正する方法が一般的である。すなわち、図１５に示した構造を含む、広いクロック構造の解空間を効率良く探索する方法は知られていない。
【００１８】
そこで、メガマクロブロックとの重なりが少ないクロック構造を広い解空間において効率良く探索できるようにすることが課題となる。本発明の目的は、かかる課題を解決する半導体集積回路設計装置、半導体集積回路設計方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
本発明の第１の視点に係る半導体集積回路設計装置は、
半導体集積回路のチップ領域を覆う格子を設定する格子設定部と、
チップ領域の中心から格子の各セルの中心へクロック信号を分配するクロック構造であって、チップ領域を格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する候補線分生成部と、
チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、上記クロック構造を表す２分木を生成する２分木生成部と、
候補線分に設定された重みの総和である目的関数が最小となるように、２分木の各節点の分割方向を選択する分割方向選択部と、
各節点の分割方向が選択された２分木によって表されるクロック構造を生成するクロック構造生成部と、を有する。
【００２０】
本発明の第２の視点に係る半導体集積回路設計方法は、
コンピュータが、半導体集積回路のチップ領域を覆う格子を設定する工程と、
チップ領域の中心から格子の各セルの中心へクロック信号を分配するクロック構造であって、チップ領域を格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する工程と、
チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、上記クロック構造を表す２分木を生成する工程と、
候補線分に設定された重みの総和である目的関数が最小となるように、２分木の各節点の分割方向を選択する工程と、
各節点の分割方向が選択された２分木によって表されるクロック構造を生成する工程と、含む。
【００２１】
本発明の第３の視点に係るプログラムは、
半導体集積回路のチップ領域を覆う格子を設定する処理と、
チップ領域の中心から格子の各セルの中心へクロック信号を分配するクロック構造であって、チップ領域を格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する処理と、
チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、上記クロック構造を表す２分木を生成する処理と、
候補線分に設定された重みの総和である目的関数が最小となるように、２分木の各節点の分割方向を選択する処理と、
各節点の分割方向が選択された２分木によって表されるクロック構造を生成する処理と、をコンピュータに実行させる。
【発明の効果】
【００２２】
本発明に係る半導体集積回路設計装置、半導体集積回路設計方法及びプログラムによると、メガマクロブロックとの重なりが少ないクロック構造を広い解空間において効率良く探索することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１の実施形態に係る半導体集積回路設計装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態に係る半導体集積回路設計装置の構成を示すブロック図である。
【図３】コンピュータの構成を一例として示すブロック図である。
【図４】本発明の第２の実施形態に係る半導体集積回路設計装置の動作を示すフローチャートである。
【図５】本発明の第２の実施形態に係る半導体集積回路設計装置の格子設定部によって設定された格子を一例として示す図である。
【図６】本発明の第２の実施形態に係る半導体集積回路設計装置の候補線分生成部よって生成された候補線分を一例として示す図である。
【図７】本発明の第２の実施形態に係る半導体集積回路設計装置の２分木生成部によって生成された２分木を一例として示す図である。
【図８】本発明の第２の実施形態に係る半導体集積回路設計装置のブロック配置部によって生成されたフロアプラン候補を一例として示す図である。
【図９】本発明の第２の実施形態に係る半導体集積回路設計装置の重み設定部による重み割り当てについて説明するための図である。
【図１０】本発明の第２の実施形態に係る半導体集積回路設計装置の分割方向選択部によって選択された分割方向を一例として示す図である。
【図１１】本発明の第２の実施形態に係る半導体集積回路設計装置のクロック構造生成部によって生成された対称性を有するクロック構造を一例として示す図である。
【図１２】クロック分配問題と従来技術によるクロック構造を一例として示す図である。
【図１３】対称性を有するクロック構造の例を示す図である。
【図１４】メガマクロブロックと重なりの多いクロック構造を一例として示す図である。
【図１５】メガマクロブロックと重なりのないクロック構造を一例として示す図である。
【発明を実施するための形態】
【００２４】
本発明の第１の展開形態によると、上記第１の視点に係る半導体集積回路設計装置が提供される。
【００２５】
本発明の第２の展開形態によると、チップ領域に配置されたメガマクロブロックと候補線分との重なり量を求め、求めた重なり量に応じた重みを候補線分の重みとして設定する重み設定部をさらに有する、半導体集積回路設計装置が提供される。
【００２６】
本発明の第３の展開形態によると、メガマクロブロックをチップ領域に配置するブロック配置部をさらに有する、半導体集積回路設計装置が提供される。
【００２７】
本発明の第４の展開形態によると、メガマクロブロックの複数の配置のうちの目的関数（ないし評価関数）が最小となる配置を選択するブロック配置選択部をさらに有する、半導体集積回路設計装置が提供される。
【００２８】
本発明の第５の展開形態によると、上記２分木は、チップ領域の分割に相当する節点と、当該分割の順序に相当する枝とを有する、半導体集積回路設計装置が提供される。
【００２９】
本発明の第６の展開形態によると、候補線分生成部は、クロック信号を分配するクロック構造のうちの対称性を有するクロック構造を構成する線分の候補を、候補線分として生成する、半導体集積回路設計装置が提供される。
【００３０】
本発明の第７の展開形態によると、チップ領域を含むチップ情報を保持する記憶部をさらに有する、半導体集積回路設計装置が提供される。
【００３１】
本発明の第８の展開形態によると、チップ情報は、クロックネットとメガマクロブロックを含む半導体集積回路に関するチップ情報である、半導体集積回路設計装置が提供される。
【００３２】
本発明の第９の展開形態によると、上記第２の視点に係る半導体集積回路設計方法が提供される。
【００３３】
本発明の第１０の展開形態によると、上記第３の視点に係るプログラムが提供される。
【００３４】
本発明によれば、対称性を有するクロック構造の解空間を表現した２分木上で、メガマクロブロック配置位置を考慮したクロック構造の探索を効率的に行うことが可能になる。また、クロック構造の探索とフロアプラン候補の列挙を組み合わせることにより、目的関数が最良となるクロック構造とフロアプラン構造の組み合わせの広範囲かつ効率的な探索も可能となる。
【００３５】
以下、本発明の実施形態について、図面を参照して説明する。なお、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００３６】
（実施形態１）
本発明の第１の実施形態に係る半導体集積回路設計装置について、図面を参照して説明する。図１は、本実施形態に係る半導体集積回路設計装置２００の構成を示すブロック図である。
【００３７】
図１を参照すると、半導体集積回路設計装置２００は、格子設定部１０２、候補線分生成部１０３、２分木生成部１０４、分割方向選択部１０７及びクロック構造生成部１０８を有する。
【００３８】
格子設定部１０２は、半導体集積回路のチップ領域を覆う格子を設定する。
【００３９】
候補線分生成部１０３は、チップ領域の中心から格子の各セルの中心へクロック信号を分配するクロック構造であって、チップ領域を格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を、候補線分として生成する。
【００４０】
２分木生成部１０４は、チップ領域の分割方向及び分割順序を節点及び枝として有し、上記クロック構造を表す２分木を生成する。
【００４１】
分割方向選択部１０７は、候補線分に設定された重みの総和である目的関数が最小となるように、２分木の各節点の分割方向を選択する。
【００４２】
上記の候補線分の重みは、一例として、チップ領域に配置されたメガマクロブロックと候補線分との重なり量に応じた重みでとしてもよい。
【００４３】
クロック構造生成部１０８は、各接点の分割方向が選択された２分木によって表されるクロック構造を生成する。
【００４４】
また、メガマクロブロックの複数の配置のうちの上記目的関数が最小となる配置を選択するようにしてもよい。
【００４５】
本実施形態の半導体集積回路設計装置２００によれば、対称性を有するクロック構造の解空間を表現する２分木上で、メガマクロブロックとの重なりが少ないクロック構造を効率よく探索することができる。
【００４６】
（実施形態２）
本発明の第２の実施形態に係る半導体集積回路設計装置について、図面を参照して説明する。図２は、本実施形態に係る半導体集積回路設計装置１００の構成を示すブロック図である。
【００４７】
図２を参照すると、半導体集積回路設計装置１００は、記憶部９０、チップ情報受付部１０１、格子設定部１０２、候補線分生成部１０３、２分木生成部１０４、ブロック配置部１０５、重み設定部１０６、分割方向選択部１０７、クロック構造生成部１０８及びブロック配置選択部１０９を有する。
【００４８】
記憶部９０は、クロックネットとメガマクロブロックを含む半導体集積回路のチップ情報を記憶する。
【００４９】
格子設定部１０２は、チップ情報に含まれるチップ領域を覆う格子を設定する。
【００５０】
候補線分生成部１０３は、チップ領域中心から格子の各中心へクロック信号を分配する対称性を有する配線を構成する線分の候補を候補線分として生成する。
【００５１】
２分木生成部１０４は、チップ領域を、格子に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック構造の集合を表現する２分木を、各分割に対応する節点と、前記節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する。
【００５２】
ブロック配置部１０５は、各メガマクロブロックの配置位置候補をフロアプラン候補として生成する。
【００５３】
重み設定部１０６は、生成された各候補線分について、配置されたメガマクロブロックとの重なり量の計算を行い、重なり量を該候補線分の重みとして設定する。
【００５４】
分割方向選択部１０７は、各節点の分割方向に対応して候補線分に割当られた重みの総和を目的関数として、目的関数が最小となるように、２分木の各節点に割り当てられた分割方向を選択する。
【００５５】
クロック構造生成部１０８は、２分木の各節点に割り当てられた分割方向に対応するクロック構造を、フロアプラン候補に対するクロック構造として生成する。
【００５６】
ブロック配置選択部１０９は、生成されたすべてのフロアプランとクロック構造の対の集合の中から、目的関数が最良となるフロアプランとクロック構造の組み合わせを解として選択する。
【００５７】
記憶部９０は、格子設定部１０２からクブロック配置選択部１０９までの各部と接続されている。各部で生成された生成データ、計算された計算結果及び評価された評価結果は、記憶部９０に記録される。
【００５８】
また、各部で生成されたデータを記憶部９０に記憶するとともに、各部で計算に必要とされるデータを記憶部９０から読み出すようにしてもよい。なお、各部で計算に必要とされるデータを、このデータを生成した構成要素から受け取るようにしてもよい。また、計算に必要とされるデータの一部を、このデータを生成した構成要素から受けるとともに、それ以外のデータを記憶部９０から読み出すようにしてもよい。
【００５９】
例えば、候補線分生成部１０３は、格子設定部１０２で生成された格子を、記憶部９０から読み出すようにしてもよいし、格子設定部１０２から受けるようにしてもよいし、データの一部を格子設定部１０２から受けるとともに、それ以外のデータを記憶部９０から読み出すようにしてもよい。
【００６０】
図２では、格子設定部１０２からブロック配置選択部１０９までが、一方向の矢印で接続されているが、必ずデータが矢印の方向に送られることを意味するものでなく、記憶部９０を介してデータが送られる場合もある。
【００６１】
また、格子設定部１０２で用いられるチップ領域のデータは、記憶部９０を介さずに、直接、チップ情報受付部１０１から受けてもよい。
【００６２】
半導体集積回路設計装置１００は、一例として、専用ＩＣ等のハードウエアによって構成することができる。また、半導体集積回路設計装置１００は、制御装置、記憶装置、入力装置及び表示装置を有するコンピュータにより構成することもできる。
【００６３】
図３は、コンピュータの構成を一例として示すブロック図である。図３を参照すると、コンピュータは、入出力部１１０１、表示部１１０２、メモリ１１０３、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１０４、及び記憶部１１０５を有し、これらの各部はバス１１０６を介して接続されている。
【００６４】
図２に示した各部は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などの記憶装置上に構築され、記憶装置に格納されたプログラムにより動作する制御装置によって制御されるようにしてもよい。
【００６５】
すなわち、半導体集積回路設計装置１００の構成要素は、コンピュータの制御装置であるＣＰＵ１１０４、ＲＯＭ、ＲＡＭ等の記憶装置であるメモリ１１０３、メモリにロードされた図２の構成要素を実現するプログラム、そのプログラムを格納するハードディスク等の記憶部１１０５、液晶ディスプレイ等の表示部１１０２、ネットワーク接続用インタフェース等の入出力部１１０１、これらの各部を接続するバス１１０６によって、ハードウエアとソフトウエアの組合せとして実現しうる。
【００６６】
記憶部９０は、設計対象となる半導体集積回路チップのクロック素子と、メモリブロック、ＩＰブロック等のメガマクロブロックを含むゲートレベル又はＲＴ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ）レベルのネットリストに関する情報（チップ情報）を記憶する。
【００６７】
チップ情報受付部１０１は、上記チップ情報を受け付け、記憶部９０に記録する。チップ情報受付部１０１は、例えば、半導体集積回路設計装置１００の入出力インタフェース（非図示）を介して、各種記録媒体若しくは記憶装置、又はネットワークを介して接続された他の装置からデータを受け付けるようにしてもよい。なお、チップ情報受付部１０１は、ユーザの操作により入力されたデータを受け付けるようにしてもよい。
【００６８】
記憶部９０の情報は、チップ情報を受け付ける都度更新する必要はなく、記憶部９０にすでに記録されているチップ情報を利用するようにしてもよい。
【００６９】
格子設定部１０２は、前記チップ情報に含まれるチップ領域を覆う格子を設定する。格子数は、例えば、２ｘ２、４ｘ４、８ｘ８のように、縦方向及び横方向の格子数の組み合わせによって指定することができる。
【００７０】
候補線分生成部１０３は、チップ領域の中心から格子の各セルの中心へクロック信号を分配する配線を構成する線分の候補を候補線分として生成する。ここで、配線は対称性を有する配線であることが好ましい。
【００７１】
２分木生成部１０４は、チップ領域を、格子のセルの境界に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック構造の集合を表現する２分木を、各分割に対応する節点と、前記節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する。各分割の方向は、対応する節点に付随する情報（「属性」という。）として保持される。
【００７２】
ブロック配置部１０５は、メガマクロブロックの配置位置候補をフロアプラン候補として生成する。フロアプラン候補を生成するには、一例として、ＣＡＤベンダ等によって提供された既存のフロアプラン生成ツールを用いることができる。
【００７３】
重み設定部１０６は、生成された各候補線分について、配置されたメガマクロブロックとの重なり量の計算を行い、重なり量を各候補線分の重みとして設定する。
【００７４】
分割方向選択部１０７は、各節点の分割方向に対応する前記生成された候補線分の重みの総和を目的関数として、目的関数が最小となるように、２分木の各節点に割り当てられた分割方向を選択する。重みの総和（すなわち目的関数）が最小となる分割方向を選択するには、一例として、シミュレーテッドアニーリング（Ｓｉｍｕｌａｔｅｄ  Ａｎｎｅａｌｉｎｇ）のような最適化アルゴリズムを適用することができる。
【００７５】
クロック構造生成部１０８は、２分木の各節点に割り当てられた分割方向に対応するクロック構造を、フロアプラン候補に対するクロック構造として生成する。
【００７６】
ブロック配置選択部１０９は、生成されたすべてのフロアプランとクロック構造の対集合の中から、目的関数が最小となるフロアプランとクロック構造の組み合わせを解として選択する。
【００７７】
本実施形態の半導体集積回路設計装置１００において、ＣＰＵ１１０４が、記憶部（ハードディスク等）１１０５に記録されたプログラムをメモリ１１０３に読み出して実行することにより、図２の各部の各機能を実現することができる。
【００７８】
このように構成された本実施形態の半導体集積回路設計装置１００の動作について、以下に説明する。図４は、本実施形態に係る半導体集積回路装置１００の動作を示すフローチャートである。
【００７９】
図４を参照すると、まず、記憶部９０は、クロックネットとメガマクロブロックを含む半導体集積回路のチップ情報を記憶する（ステップＳ１０１）。
【００８０】
次に、格子設定部１０２は、チップ情報に含まれるチップ領域を覆う格子を設定する（ステップＳ１０２）。
【００８１】
次に、候補線分生成部１０３は、チップ領域中心から格子の各中心へクロック信号を分配する対称性を有する配線を構成する線分の候補を候補線分として生成する（ステップＳ１０３）。
【００８２】
次に、２分木生成部１０４は、チップ領域を、格子に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック構造の集合を表現する２分木を、各分割に対応する節点と、節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する（ステップＳ１０４）。
【００８３】
次に、ブロック配置部１０５は、メガマクロブロックの配置位置候補をフロアプラン候補として生成する（ステップＳ１０５）。
【００８４】
次に、重み設定部１０６は、生成された各候補線分について、配置されたメガマクロブロックとの重なり量の計算を行い、重なり量を当該候補線分の重みとして設定する（ステップＳ１０６）。
【００８５】
次に、分割方向選択部１０７は、各節点の分割方向に対応して候補線分に割り当てられた重みの総和を目的関数として、目的関数が最小となるように、２分木の各節点に割り当てられた分割方向を、縦方向又は横方向のいずれかから選択する（ステップＳ１０７）。
【００８６】
次に、クロック構造生成部１０８は、２分木の各節点に割り当てられた分割方向に対応するクロック構造を、フロアプラン候補に対するクロック構造として生成する（ステップＳ１０８）。
【００８７】
次に、ブロック配置選択部１０９は、生成されたすべてのフロアプランとクロック構造の対集合の中から、目的関数が最良となるフロアプランとクロック構造の組み合わせを、解として選択する（ステップＳ１０９）。
【実施例】
【００８８】
具体的な実施例に基づいて、上記第２の実施形態に係る半導体集積回路設計装置１００の動作について説明する。図５〜図１１は、本実施例について説明するための図である。
【００８９】
図４を参照すると、チップ情報受付部１０１は、設計対象となる半導体集積回路チップのクロックネットとメガマクロブロックを含むゲートレベル又はＲＴ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ）レベルのネットリストに関する情報（チップ情報）の入力を受け付け、記憶部９０に記録する（ステップＳ１０１）。
【００９０】
次に、格子設定部１０２は、上記チップ情報に含まれるチップ領域を覆う格子を設定する（ステップＳ１０２）。
【００９１】
図５は、格子設定部１０２によって設定された格子を一例として示す図である。図５を参照すると、４×４の格子３１が示されている。
【００９２】
次に、候補線分生成部１０３は、チップ領域中心から格子の各中心へクロック信号を分配する対称性を有する配線構造を構成する線分の候補を候補線分として生成する（ステップＳ１０３）。
【００９３】
図６（ａ）、（ｂ）は、候補線分生成部１０３によって生成された候補線分を一例として示す図である。図６（ａ）は、４×４の格子３１に対して生成された横方向の候補線分４１、４２を示す。図６（ｂ）は、４×４の格子３１に対して生成された縦方向の候補線分４３、４４を示す。
【００９４】
候補線分４１〜４４は、それぞれ、チップ領域の中心から格子３１の各セルの中心へクロック信号を分配するクロック構造を構成する線分の候補である。クロック構造は、候補線分４１〜４４の中から選択された線分の組み合わせとして構成することができる。
【００９５】
図６（ａ）を参照すると、候補線分４１は、チップ領域を横方向に２分割したときに、分割された左右の領域にクロック信号を分配する配線として用いることができる。また、候補線分４２は、左右に分割された領域を、横方向にさらに２分割したときに、分割された左右の領域にクロック信号を分配する配線として用いることができる。
【００９６】
図６（ｂ）を参照すると、候補線分４３は、チップ領域を縦方向に２分割したときに、分割された上下の領域にクロック信号を分配する配線として用いることができる。また、候補線分４４は、上下に分割された領域を、縦方向にさらに２分割したときに、分割された左右の領域にクロック信号を分配する配線として用いることができる。
【００９７】
次に、２分木生成部１０４は、チップ情報受付部１０１が入力したチップ領域を、格子設定部１０２が設定した格子に沿って、縦方向又は横方向に２分割することを再帰的に繰り返すことによって生成されるクロック構造の集合を表現する２分木を生成する（ステップＳ１０４）。
【００９８】
２分木生成部１０４は、各分割に対応する節点と、節点の間に分割順序の親子関係に対応する枝とを設けることによって、２分木を生成する。また、２分木の各節点は、対応する分割方向（縦方向又は横方向）を付随情報（ないし属性）として保持する。
【００９９】
図７は、２分木生成部１０４によって生成された２分木を一例として示す図である。図７は、４ｘ４格子に対するクロック構造の解空間を表現する２分木を示す。ここで、節点５１は、分割方向に対応する。節点５１に付随する属性Ｈは横方向の分割を示し、属性Ｖは縦方向の分割を示す。
【０１００】
この段階（ステップＳ１０４）では、分割方向が選択されていないため、各節点には、両方の属性、すなわち、属性Ｈ及び属性Ｖが付随している。分割レベル５３〜５６は、分割の順序を示す。分割は再帰的に繰り返されるため、分割レベル５３〜５６は分割の順序を示している。分割レベル５３〜５６は、それぞれ、レベル１〜４の分割と方向を示す。枝５２は、分割の順序関係を示す。
【０１０１】
次に、ブロック配置部１０５は、各メガマクロブロックの配置位置の候補をフロアプラン候補として生成する（ステップＳ１０５）。
【０１０２】
図８は、ブロック配置部１０５によって生成されたフロアプラン候補を一例として示す図である。図８を参照すると、７つのメガマクロブロック６１のフロアプランが示されている。
【０１０３】
次に、重み設定部１０６は、候補線分生成部１０３が生成した候補線分４１、４２と、ブロック配置部１０５が生成したメガマクロブロック６１との間の重なり量を求め、求めた重なり量に応じて各候補線分の重みを設定する（ステップＳ１０６）。
【０１０４】
図９は、重み設定部１０６による重み割り当てについて説明するための図である。図９を参照すると、候補線分７１はメガマクロブロック６１と重なっていないことから、例えば、重みとしてゼロが割り当てられる。一方、候補線分７２はメガマクロブロック６１と重なっていることから、候補線分７２とメガマクロブロック６１との重なり量（長さ、面積等）に応じた重みが候補線分７２に割り当てられる。
【０１０５】
次に、分割方向選択部１０７は、各節点の分割方向に対応して候補線分に割り当てられた重みの総和を目的関数として、目的関数が最小となるように、２分木の各節点に割り当てられた分割方向（縦方向又は横方向）を選択する（ステップＳ１０７）。
【０１０６】
図１０は、分割方向選択部１０７によって選択された分割方向を一例として示す図である。図１０を参照すると、図７に示したクロック構造の解空間を表現する２分木の各節点に対する分割方向の割り当てが示されている。図１０において、各分割に対応する節点５１に割り当てられたＨ又はＶは、分割方向を示している。Ｈは横方向の分割を示し、Ｖは縦方向の分割を示す。
【０１０７】
ルート節点から、分割の順序関係を示す枝をたどりながら、レベル（５３から５６）毎に、各節点への分割方向の割り当てを繰り返す処理を、シミュレーテッドアニーリング等の最適化アルゴリズムに基づいて行なうことによって、図１０に示した分割方向の割り当てが得られる。
【０１０８】
次に、クロック構造生成部１０８は、２分木の各節点に割り当てられた分割方向に対応するクロック構造を、ブロック配置部１０５によって生成されたフロアプラン候補に対するクロック構造として生成する（ステップＳ１０８）。
【０１０９】
図１１は、クロック構造生成部１０８によって生成された対称クロック構造を一例として示す図である。図１１を参照すると、図１０に示した分割方向の割り当て結果から導出されるクロック構造が示されている。分割方向９１は、各線分に対応する分割レベルと方向を示す。すなわち、分割方向９１の数字は分割レベルを示し、Ｈ又はＶは分割方向を示す。
【０１１０】
次に、ブロック配置選択部１０９は、前記生成されたすべてのフロアプランとクロック構造の対の集合の中から、目的関数が最小となるとフロアプランとクロック構造の組み合わせを解として選択する（ステップＳ１０９）。
【０１１１】
例えば、図１１に示したフロアプランとクロック構造に対する目的関数が最小となる場合には、ブロック配置選択部１０９は、図１１に示したフロアプランとクロック構造の組み合わせを最終的な解として選択する。
【０１１２】
上記のステップＳ１０１〜Ｓ１０９までの処理は逐次的に実行される。なお、ステップＳ１０３及びステップＳ１０４の処理は、並行して実行してもよいし、逆の順序に実行してもよい。
【０１１３】
本実施形態の半導体集積回路設計装置及び設計方法によれば、対称性を有するクロック構造の解空間を表現する２分木上で、メガマクロブロック配置位置を考慮した配線構造の探索を効率的に行うことができる。また、この配線構造の探索とフロアプラン候補の列挙を組み合わせることにより、任意の目的関数が最良となるクロック構造とフロアプラン構造の組み合わせを、広範囲かつ効率的に探索することができる。
【０１１４】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態及び実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【０１１５】
本発明は、クロック分配回路及びメガマクロブロックを含む半導体集積回路の配置配線を行う設計装置、設計方法及びプログラムに適用しうる。
【０１１６】
なお、上記実施形態の一部又は全部は、以下の付記として記載することができるものであるが、これらに限定されるものではない。
【０１１７】
（付記１）半導体集積回路のチップ領域を覆う格子を設定する格子設定部と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する候補線分生成部と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する２分木生成部と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する分割方向選択部と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成するクロック構造生成部と、を備えていることを特徴とする半導体集積回路設計装置。
【０１１８】
（付記２）前記チップ領域に配置されたメガマクロブロックと前記候補線分との重なり量を求め、求めた重なり量に応じた重みを前記候補線分の重みとして設定する重み設定部をさらに備えていることを特徴とする、付記１に記載の半導体集積回路設計装置。
【０１１９】
（付記３）前記メガマクロブロックを前記チップ領域に配置するブロック配置部をさらに備えていることを特徴とする、付記２に記載の半導体集積回路設計装置。
【０１２０】
（付記４）前記メガマクロブロックの複数の配置のうちの前記目的関数が最小となる配置を選択するブロック配置選択部をさらに備えていることを特徴とする、付記２又は３に記載の半導体集積回路設計装置。
【０１２１】
（付記５）前記２分木は、前記チップ領域の分割に相当する節点と、該分割の順序に相当する枝とを有することを特徴とする、付記１乃至４のいずれか一に記載の半導体集積回路設計装置。
【０１２２】
（付記６）前記候補線分生成部は、前記クロック信号を分配するクロック構造のうちの対称性を有するクロック構造を構成する線分の候補を、前記候補線分として生成することを特徴とする、付記１乃至５のいずれか一に記載の半導体集積回路設計装置。
【０１２３】
（付記７）前記チップ領域を含むチップ情報を保持する記憶部をさらに備えていることを特徴とする、付記１乃至６のいずれか一に記載の半導体集積回路設計装置。
【０１２４】
（付記８）前記チップ情報は、クロックネットとメガマクロブロックを含む半導体集積回路に関するチップ情報であることを特徴とする、付記７に記載の半導体集積回路設計装置。
【０１２５】
（付記９）クロックネットとメガマクロブロックを含む半導体集積回路のチップ情報を記憶する記憶部と、
前記チップ情報に含まれるチップ領域を覆う格子を設定する格子設定部と、
前記チップ領域の中心から格子の各中心へクロック信号を分配する対称性を有するクロック構造の構成要素となる線分の候補を候補線分として列挙する候補線分生成部と、
前記チップ領域を、前記格子に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック分配構造の集合を表現する２分木を、前記各分割に対応する節点と、前記節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する２分木生成部と、
各節点の分割方向に対応して候補線分に割り当てられた重みの総和を目的関数として、該目的関数が最小となるように、前記２分木の各節点に割り当てられた分割方向を選択する分割方向選択部と、
前記２分木の各節点に割り当てられた分割方向に対応するクロック構造を生成するクロック構造生成部と、を備えていることを特徴とする半導体集積回路設計装置。
【０１２６】
（付記１０）前記メガマクロブロックの配置位置候補、すなわち、フロアプラン候補、を生成するブロック配置部と、
前記列挙された各クロック分配線分候補について、前記配置されたメガマクロブロックとの重なり量の計算を行い、前記重なり量を該候補線分の重みとして設定する重み設定部と、をさらに備えていることを特徴とする、付記９に記載の半導体集積回路設計装置。
【０１２７】
（付記１１）複数のフロアプラン候補を生成し、前記生成された全てのフロアプランとクロック構造の対集合の中から、前記クロック構造目的関数が最良となるフロアプランとクロック構造の組み合わせを、解として選択するブロック配置選択部をさらに備えていることを特徴とする、付記９又は１０に記載の半導体集積回路設計装置。
【０１２８】
（付記１２）コンピュータが、半導体集積回路のチップ領域を覆う格子を設定する工程と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する工程と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する工程と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する工程と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成する工程と、含むことを特徴とする半導体集積回路設計方法。
【０１２９】
（付記１３）クロックネットとメガマクロブロックを含む半導体集積回路のチップ情報を記憶する工程と、
前記チップ情報に含まれるチップ領域を覆う格子を設定する工程と、
チップ領域中心から格子の各中心へクロック信号を分配する対称性を有するクロック構造の構成要素となる線分の候補を候補線分として列挙する工程と、
前記チップ領域を、前記格子に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック分配構造の集合を表現する２分木を、前記各分割に対応する節点と、前記節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する工程と、
各節点の分割方向に対応して候補線分に割り当てられた重みの総和を目的関数として、該目的関数が最小となるように、前記２分木の各節点に割り当てられた分割方向を選択する工程と、
前記２分木の各節点に割り当てられた分割方向に対応するクロック構造を生成する工程と、を含むことを特徴とする半導体集積回路設計方法。
【０１３０】
（付記１４）前記メガマクロブロックの配置位置候補、すなわち、フロアプラン候補、を生成し、前記列挙された各クロック分配線分候補について、前記配置されたメガマクロブロックとの重なり量の計算を行う工程と、
前記重なり量を該候補線分の重みとして設定する工程と、をさらに含むことを特徴とする、付記１３に記載の半導体集積回路設計方法。
【０１３１】
（付記１５）複数のフロアプランを生成し、前記生成された全てのフロアプランとクロック構造の対集合の中から、前記クロック構造目的関数が最良となるフロアプランとクロック構造の組み合わせを、解として選択する工程をさらに含むことを特徴とする、付記１３又は１４に記載の半導体集積回路設計方法。
【０１３２】
（付記１６）半導体集積回路のチップ領域を覆う格子を設定する処理と、
前記チップ領域の中心から前記格子の各セルの中心へクロック信号を分配するクロック構造であって、前記チップ領域を前記格子に含まれるセルの境界に沿って縦方向又は横方向に２分割することを再帰的に繰り返すことにより生成されたクロック構造を構成する線分の候補を候補線分として生成する処理と、
前記チップ領域の分割方向及び分割順序をそれぞれ節点及び枝として有し、前記クロック構造を表す２分木を生成する処理と、
前記候補線分に設定された重みの総和である目的関数が最小となるように、前記２分木の各節点の分割方向を選択する処理と、
各節点の分割方向が選択された前記２分木によって表されるクロック構造を生成する処理と、をコンピュータに実行させることを特徴とするプログラム。
【０１３３】
（付記１７）クロックネットとメガマクロブロックを含む半導体集積回路のチップ情報を記憶する処理と、
前記チップ情報に含まれるチップ領域を覆う格子を設定する処理と、
チップ領域中心から格子の各中心へクロック信号を分配する対称性を有するクロック構造の構成要素となる線分の候補を候補線分として列挙する処理と、
前記チップ領域を、前記格子に沿って、縦又は横に２分割することを再帰的に繰り返すことによって生成されるクロック分配構造の集合を表現する２分木を、前記各分割に対応する節点と、前記節点の間に分割順序の親子関係に対応する枝とを設けることによって生成する処理と、
各節点の分割方向に対応して候補線分に割り当てられた重みの総和を目的関数として、該目的関数が最小となるように、前記２分木の各節点に割り当てられた分割方向を選択する処理と、
前記２分木の各節点に割り当てられた分割方向に対応するクロック構造を生成する処理と、をコンピュータに実行させることを特徴とするプログラム。
【０１３４】
（付記１８）前記メガマクロブロックの配置位置候補、すなわち、フロアプラン候補、を生成する処理と、
前記列挙された各クロック分配線分候補について、前記配置されたメガマクロブロックとの重なり量の計算を行う処理と、
前記重なり量を該候補線分の重みとして設定する処理と、をさらにコンピュータに実行させることを特徴とする、付記１７に記載のプログラム。
【０１３５】
（付記１９）複数のフロアプランを生成し、前記生成された全てのフロアプランとクロック構造の対集合の中から、前記クロック構造目的関数が最良となるフロアプランとクロック構造の組み合わせを、解として選択する処理をさらにコンピュータに実行させることを特徴とする、付記１７又は１８に記載のプログラム。
【符号の説明】
【０１３６】
３１    格子
４１、４２、４３、４４、７１、７２    候補線分
５１    節点
５２    枝
５３〜５６  分割レベル
６１    メガマクロブロック
９０、１１０５    記憶部
９１    分割方向
１００、２００    半導体集積回路設計装置
１０１    チップ情報受付部
１０２    格子設定部
１０３    候補線分生成部
１０４    ２分木生成部
１０５    ブロック配置部
１０６    重み設定部
１０７    分割方向選択部
１０８    クロック構造生成部
１０９    ブロック配置選択部
１１１    末端セル
１１２    クロックドライバセル
１１３    中継バッファ
１１０１    入出力部
１１０２    表示部
１１０３    メモリ
１１０４    ＣＰＵ
１１０６    バス
【図１】
2011238011.tif 000003
【図２】
2011238011.tif 000004
【図３】
2011238011.tif 000005
【図４】
2011238011.tif 000006
【図５】
2011238011.tif 000007
【図６】
2011238011.tif 000008
【図７】
2011238011.tif 000009
【図８】
2011238011.tif 000010
【図９】
2011238011.tif 000011
【図１０】
2011238011.tif 000012
【図１１】
2011238011.tif 000013
【図１２】
2011238011.tif 000014
【図１３】
2011238011.tif 000015
【図１４】
2011238011.tif 000016
【図１５】
2011238011.tif 000017