クロック信号供給回路の設計方法、情報処理装置およびプログラム
【課題】半導体集積回路におけるクロック信号の供給において、回路全体を通しクロックラインを短縮し得る構成を提供することを目的とする。
【解決手段】回路素子のグループ間で回路素子の交換、移動を実行し、当該実行の前後でグループごとに回路素子の位置と中心位置との距離の合計し更に全グループについて合計した値が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化を実行する構成である。
【解決手段】回路素子のグループ間で回路素子の交換、移動を実行し、当該実行の前後でグループごとに回路素子の位置と中心位置との距離の合計し更に全グループについて合計した値が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化を実行する構成である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はクロック信号供給回路の設計方法、情報処理装置およびプログラムに係り、特に一のクロックバッファによってクロック信号が供給される回路素子のグループ分けの方法に関する。なおクロックバッファとは、クロック信号を中継する機能を有するバッファを意味する（以下同様）。
【背景技術】
【０００２】
半導体集積回路において、フリップフロップ等の回路素子に対し、クロックバッファを用いてクロック信号を供給する。この場合、一のクロックバッファによってクロック信号が供給される回路素子のグループを形成する。なお以下の説明において「グループ」とは一のクロックバッファによってクロック信号が供給される回路素子のグループを意味し、そのようなグループを形成することをグループ分けあるいはグループ化と称する。
【特許文献１】特開２００７−２７８４１号公報
【特許文献２】特開２００７−１２８４２９号公報
【特許文献３】特開平７−１３４６２６号公報
【特許文献４】特開平１１−２１４５１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
効果的なグループ分けを行い得るクロック信号供給回路の設計方法を提供することが目的である。
【課題を解決するための手段】
【０００４】
クロック信号供給回路の設計方法では以下に示す最適化を行う。すなわちグループ間で回路素子の交換および移動のうちの少なくとも何れか一方を実行する。そして各グループの中心位置と当該グループ内の各回路素子との間の距離を合計する。更に当該グループごとの合計を全グループにつき合計する。そして全グループのついての合計が減少する場合に前記交換および移動のうちの少なくとも何れか一方の実行後のグループを維持する。他方全グループのついての合計が減少しない場合には前記交換および移動のうちの少なくとも何れか一方の実行前のグループを維持する。そして当該最適化を反復する。結果的に得られた各グループにつき、当該グループの中心位置にクロックバッファを設け、グループ内の各回路素子にクロック信号を供給する。
【発明の効果】
【０００５】
クロック信号供給回路の設計方法において、上記最適化では各グループの中心位置と当該グループ内の各回路素子との間の距離を合計の全グループのついての合計が減少する場合に前記交換および移動のうちの少なくとも何れか一方の実行後のグループを維持する。他方全グループのついての合計が減少しない場合には前記交換および移動のうちの少なくとも何れか一方の実行前のグループを維持する。更に最適化を反復する。このため、全グループを通し、各グループのクロックバッファから各回路素子までの距離が効果的に短縮される。
【発明を実施するための最良の形態】
【０００６】
例えばフリップフロップのセットアップタイミング、ホールドタイミングの条件を満たすためにはクロックスキューを小さくする必要がある。なおクロックスキューとは、例えばクロック信号がフリップフロップに供給される際にフリップフロップ間で生ずる遅延差を意味する（以下同様）。またクロックバッファは動作率が高いため、回路全体の消費電力の削減のため設置個数を少なくすることが望ましい。
【０００７】
またクロックバッファからフリップフロップ等の回路素子までの配線長を短縮し、そのばらつきを低減することが望ましい。またクロックバッファのファンアウトを一定数以下とすることが望ましい。なおクロックバッファのファンアウトとは、クロックバッファを用いてクロック信号を供給する際、一のクロックバッファによってクロック信号が供給される回路素子の個数を意味する（以下同様）。また許容ファンアウトとは、ファンアウトの許容値を意味する（以下同様）。またクロックドメインごとにグループ化を行う必要がある。
【０００８】
実施例によるクロック信号供給回路の設計方法では、半導体集積回路の回路設計において、回路に含まれる各フリップフロップに対しクロック信号を供給する際、最初にいわゆるH型クロックツリーを作成する。ここでＨ型クロックツリーとはフリップフロップ等の回路素子にクロック信号を供給するための配線経路の構造である（以下同様）。そして上記Ｈ型クロックツリーの末端から各フリップフロップまでをクロックバッファを介してクロックラインで接続する。ここでクロックラインとはクロック信号を供給する配線を意味する（以下同様）。より具体的には、回路に含まれるフリップフロップをグループ化し、各グループに対し一のクロックバッファを割り当て、Ｈ型クロックツリーの末端から各クロックバッファに対しクロックラインを接続する。また各クロックバッファから該当するグループに属するフリップフロップとの間もクロックラインで接続する。その結果、Ｈ型クロックツリーの末端から、各クロックバッファを介し、それぞれのフリップフロップにクロックラインが接続される。その結果、同クロックラインを通じてクロック信号がそれぞれのフリップフロップに供給される。
【０００９】
実施例では上記グループ化を行う際、最初に仮のグループ化（以下初期グループ化と称する）を行い、初期グループ化で得られたグループに対し後述する最適化を反復して行う。最適化とは、グループ間のフリップフロップの交換や移動を含む。更に前記交換や移動のたび、各グループの中心位置と当該グループに属するフリップフロップとの間の距離の合計を計算し、更にグループごとの合計を全グループについて合計する。全グループについての合計が減少する場合に、上記グループ間のフリップフロップの交換や移動後のグループを維持する。全グループについての合計が減少しない場合には、上記グループ間のフリップフロップの交換や移動前のグループを維持する。また最適化は、一定の条件を満たす場合に行うグループ同士の結合を含む。そして上記最適化を反復して行う。
【００１０】
各グループの中心位置には、当該グループに属するフリップフロップに対しクロック信号を供給するクロックバッファが設けられる。したがって各グループの中心位置と当該グループに属するフリップフロップとの間の距離が短いほど、クロックバッファから各フリップフロップに接続するクロックラインが短い。その結果クロックスキューを低減することもできる。
【００１１】
上記の如く最適化を反復して行うことにより最適なグループ化を行うことができる。その結果高周波数の領域(GHz帯等)において、クロックスキューを効果的に低減し得るフリップフロップのグループ化を行える。
【００１２】
上記最適化の動作は、当該動作をコンピュータに実行させるためのプログラムにより自動化し得る。すなわち上記最適化のための一連の手続きをアルゴリズムとして規定し、プログラム化する。ここで当該プログラムによる処理量は取り扱うフリップフロップの個数に対し線形で増加する。したがって処理量が現実的な程度に収まり、その際に必要とされるメモリの記憶領域も現実的な程度に収まるように上記プログラムを提供し得る。ここで上記最適化を反復して実行する場合、上記各グループの中心位置と当該グループに属するフリップフロップとの間の距離の合計の更にグループごとの合計は、上記反復に対し、収束する。
【００１３】
図１は実施例のクロック信号供給回路の設計方法におけるデータの流れを説明するための図である。
【００１４】
図１中、設計者は半導体集積回路のネットリスト１，レイアウトデータ２に加え、最適化の実行に係るエリアの定義、許容ファンアウトおよび反復回数等のパラメータ３を設定する。
【００１５】
上記ネットリスト１，レイアウトデータ２およびパラメータ３は、コンピュータにおいて、前記プログラムにしたがって、記憶装置からＣＰＵによって読み込まれ（４）、ＣＰＵによりグループ化（５）がなされる。すなわちコンピュータはプログラムにしたがって上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップをグループ化する。ここでは上記最適化が適宜反復して実行され、最適なグループ化がなされる。そしてグループ化で得られたグループに基づきコンピュータにより、ネットリストおよびレイアウトデータ上、クロックバッファの挿入およびクロックラインの接続がなされる。なおクロックバッファの挿入およびクロックラインの接続については図１４とともに後述する。そしてクロックバッファの挿入およびクロックラインの接続がなされた状態のネットリスト７およびレイアウトデータ８がＣＰＵにより記憶装置に書き込まれる（６）。またこの場合、別途上記グループ化の内容を示す情報「グループデータ」９もＣＰＵにより記憶装置に書き込まれる。設計者はグループデータ９を見てグループ化の内容をマニュアルで編集することができる。
【００１６】
このように設計者により編集されたグループデータをコンピュータに入力することにより、同編集後のグループデータがＣＰＵにより記憶装置から読み取られ（４）、同編集後のグループデータに基づいてクロックバッファの挿入およびクロックラインの接続がなされる。そしてこの場合もクロックバッファの挿入およびクロックラインの接続がなされたネットリスト７およびレイアウトデータ８がＣＰＵにより記憶装置に書き込まれる（６）。
【００１７】
図２は上記実施例によるクロック信号供給回路の設計方法をコンピュータで実現するためのプログラムのアルゴリズムの大略の流れを説明するため図である。
【００１８】
同アルゴリズムは、初期グループ化Ｓ１００，最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００を含む。これらＳ１００、Ｓ２００，Ｓ３００，Ｓ４００の手順を実行後、終了判定Ｓ５００が実行される。終了判定Ｓ５００では、一定の条件を満たす場合には図２に示される一連の手順の終了を決定する。一定の条件を満たさない場合には再度上記最適化１、２，３（Ｓ２００，Ｓ３００，Ｓ４００）の各手順が反復される。
【００１９】
図３は上記初期グループ化Ｓ１００の詳細を説明するための図である。
【００２０】
図３中、ステップＳ１０１にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップから一のフリップフロップを選択する。この選択の順序は例えばネットリスト上の番号による。ステップＳ１０２にて、既にグループが存在するか否かを判定する。初期段階ではグループは存在しないため（ＮＯ），ステップＳ１０６に移行する。ステップＳ１０６にて、当該一のフリップフロップが属するグループを設定する。そしてステップＳ１０７にて、当該一のフリップフロップの位置に基づき、回路のレイアウト上で当該グループのエリアを設定する。
【００２１】
次にステップＳ１０８にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０１で既に選択されたかを判定する。ここで上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが選択された場合とは、上記全てのフリップフロップが、ステップＳ１０６で設定されたグループに属する場合を意味する。回路に含まれる全てのフリップフリップがステップＳ１０１で選択されてはいなかった場合、ステップＳ１０１に戻る。
【００２２】
ステップＳ１０１にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップから、上記一のフリップフロップ以外の他のフリップフロップを選択する。次にステップＳ１０２にて、既にグループが存在するか否かを判定する。ここでは既に上記ステップＳ１０６でグループが設けられている（ＹＥＳ）。このためステップＳ１０３に移行する。なおここで、ステップＳ１０６にて新たなグループが作成された直後のステップＳ１０２においては、当該新たなグループが選択される。また、直前のステップＳ１０３，Ｓ１０４がともにＹＥＳであり、ステップＳ１０５で処理中のフリップフロップが当該グループに追加された場合においても、その直後のステップＳ１０２では当該グループが選択される。他方、直前のステップＳ１０３あるいはＳ１０４の結果がＮＯとなり、その結果次のステップＳ１０５にて現在処理中のフリップフロップを当該グループに追加することができない場合の直後のステップＳ１０２では、当該グループ以外の既存のグループが選択される。
【００２３】
次にステップＳ１０３にて、ステップＳ１０１で選択されたフリップフロップが、ステップＳ１０２にて選択されたグループにつき、ステップＳ１０７で設定されたエリア内に位置するか否かを判定する。エリア内に位置する場合、次にステップＳ１０４にて、前記選択されたグループにつき、ステップＳ１０６で設定されたグループに属するフリップフロップの個数が、上記パラメータ３に含まれる許容ファンアウト以内か否かを判定する。許容ファンアウト以内であれば（ＹＥＳ）、ステップＳ１０５にて、ステップＳ１０１で選択されたフリップフロップを、ステップＳ１０６で当該グループに追加する。そしてステップＳ１０７にて、当該グループに属するフリップフロップの位置に基づき、当該グループのエリアを更新する。
【００２４】
その後ステップＳ１０８にて再び上記の如く、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０１で選択されたかを判定する。回路に含まれる全てのフリップフリップがステップＳ１０１で選択されてはいなかった場合、ステップＳ１０１に戻る。以降ステップＳ１０１，Ｓ１０２，Ｓ１０３，Ｓ１０４，Ｓ１０５、Ｓ１０７、Ｓ１０８のループを反復実施する。
【００２５】
但し当該反復実施において、ステップＳ１０１では、前回までのステップＳ１０１にて既に選択されたフリップフロップ以外のフリップフロップをその都度選択する。またステップＳ１０３において使用されるエリアは、直前のステップＳ１０７で更新後のエリアである。
【００２６】
また上記反復実施の間、ステップＳ１０３にて、直前のステップＳ１０１で選択されたフリップフロップが直前のステップＳ１０７で更新後の、当該グループのエリア内に位置しない場合（ＮＯ）、ステップＳ１０２に戻る。そこで、上記の如く、当該グループ以外のグループを新たに選択し、当該新たな選択に係るグループにつき、ステップＳ１０３以降の動作を行う。同様にステップＳ１０４にて、当該グループに属するフリップフロップの個数が許容ファンアウトを超過する場合、ステップＳ１０２に戻る。そこで、上記の如く、当該グループ以外のグループを新たに選択し、当該新たな選択に係るグループにつき、ステップＳ１０３以降の動作を行う。またこのようにしてステップＳ１０２にてグループが順次選択された結果、現に存在する全てのグループの各々についてのステップＳ１０３以降の動作が既に終了しており、新たに選択するグループが存在しない場合（ＮＯ）、ステップＳ１０６に移行する。ステップＳ１０６にて、直前のステップＳ１０１で選択されたフリップフリップにつき新たなグループを作成する。そして当該新たなグループにつき、ステップＳ１０７以降の動作を行う。
【００２７】
このようにして、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０６で設定された何れかのグループに属するようになる。
【００２８】
図４Ａ乃至４Ｇとともに、図３とともに上述した初期グループ化Ｓ１００の動作の具体例を説明する。
【００２９】
図４Ａの例は、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップとして、図示の如く、番号１乃至１９を有する計１９個のフリップフロップが含まれる。
【００３０】
図４Ｂでは、番号１のフリップフロップが選択され、当該フリップフロップが属するグループとしてグループ１、Ｇ１が設定されている。またグループ１、Ｇ１に対するエリアとして、エリア１、Ａ１が設定されている。この例の場合、エリアはグループの中心を中心とする一定サイズの正方形として得られる。グループの中心は、グループに属するフリップフロップのｘ、ｙ各座標の最大値および最小値のそれぞれの中心のｘ、ｙ座標の位置である。エリアの決定方法に関し、図５Ａ，５Ｂとともに後述する。
【００３１】
図４Ｃは、番号１乃至８までの計８個のフリップフリップが処理された状態を示す。なおこの例の場合、上記許容ファンアウトとして８が設定されている。また図３のステップＳ１０１におけるフリップフロップの選択は、各フリップフロップの番号順になされるものとする。また図３のＳ１０７でエリア内に位置するか否かを判定する場合、当該エリア内に処理対象のフリップフロップがその一部分でも含まれていれば当該フリップフロップは当該エリアに位置すると判定する。その結果、番号１乃至８迄のフリップフロップの各々は、図３のステップＳ１０３，Ｓ１０４の条件を満たし、ステップＳ１０５でグループ１、Ｇ１に追加される。その結果図４Ｃに示されるように、番号１乃至８のフリップフロップはグループ１、Ｇ１に属することになる。
【００３２】
なおエリア１、Ａ１は、このようにして対応するグループ１、Ｇ１に属するフリップフロップが増加するごとにステップＳ１０７で更新される。図４Ｃの場合、グループ１、Ｇ１には番号１乃至８の計８個のフリップフリップが属するため、同８個のフリップフリップが属するグループ１，Ｇ１の中心を中心とする一定のサイズの正方形としてエリア１、Ａ１が更新される。その結果、図４Ｂに示す、番号１のフリップフロップのみがグループ１、Ｇ１に属する場合のエリア１、Ａ１に対し、図４Ｃの状態では、エリア１、Ａ１が更新され、右方向にずれて設定されている。次にステップＳ１０８にて未だ全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みではないため、ステップＳ１０１に戻る。
【００３３】
ステップＳ１０１にて、次の番号９のフリップフロップが選択される。次にステップＳ１０２にて、上記処理中のグループ１，Ｇ１が選択される。図４Ｄは上記番号９のフリップフロップが処理された状態を示す。ここでは、上記の如く許容ファンアウトは８なので、番号９のフリップフロップの場合、ステップＳ１０４からステップＳ１０２に移行する。ステップＳ１０２にて他のグループが存在するか否かを判定する。この場合当該グループ１、Ｇ１意外にグループは存在しない。このため次にステップＳ１０６に移行し、上記処理中の番号９のフリップフロップにつき新たなグループ２，Ｇ２を作成する。次にエリア２（図４Ｄでは省略）が設定される（ステップＳ１０７）。
【００３４】
図４Ｅは、引き続き番号１０乃至１５のフリップフロップが順次処理された後の状態を示す。この状態では、グループ２、Ｇ２には番号９乃至１５の計７個のフリップフロップが属し、同７個のフリップフロップが属するグループ２，Ｇ２の中心を中心とする一定サイズの正方形としてエリア２、Ａ２が設定されている。また上記７個は許容ファンアウト８以内である。
【００３５】
図４Ｆは、引き続き番号１６のフリップフロップが処理された後の状態を示す。番号１６のフリップフロップは上記グループ２、Ｇ２のエリア２、Ａ２内に位置しないため、ステップＳ１０３からステップＳ１０２に移行する、ステップＳ１０２では、他のグループとして、グループ１，Ｇ１が選択される。しかしながら当該番号１６のフリップフロップは上記グループ１，Ｇ１のエリアＡ１に含まれない。そこでステップＳ１０３からステップＳ１０２に移行する。ステップＳ１０２にて、他には未処理のグループは存在しないため、ステップＳ１０６に移行する。ステップＳ１０６にて、当該番号１６のフリップフロップにつき新たなグループ３、Ｇ３が設定され、エリア３、Ａ３が設定されている（ステップＳ１０７）。次にステップＳ１０８にて、未だ全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みではないため、ステップＳ１０１に戻る。
【００３６】
図４Ｇは、引き続き番号１７乃至１９のフリップフロップが順次処理された後の状態を示す。この状態では、グループ３、Ｇ３には番号１６乃至１９の計４個のフリップフロップが属し、同４個のフリップフロップが属するグループ３，Ｇ３の中心を中心とする一定サイズの正方形としてエリア３、Ａ３が設定されている。また上記４個は許容ファンアウト８以内である。この状態では、ステップＳ１０８にて、回路に含まれる全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みであるため、図２の初期グループ化Ｓ１００が終了する。
【００３７】
次に図５Ａ，５Ｂとともに、グループのエリアの決め方について説明する。
【００３８】
図５Ａに示す如く、クロックバッファＢが許容ファンアウト８のフリップフロップＦＦ（以下単にフリップフロップと称する）にクロック信号を供給する場合を想定する。そしてフリップフロップが最も密に配置された領域より大きくなるように、当該グループの中心からのノルムを決定する。この場合、当該決定されたノルムの範囲としてエリアの最小サイズを得る。
【００３９】
更にまた図５Ｂに示される如く、上記同様、クロックバッファＢが許容ファンアウト８のフリップフロップにクロック信号を供給する場合を想定する。そしてこの場合、距離が長くなりすぎる(クロックスキューが大きくなる)領域より小さくなるようにノルムを決定する。そして当該決定されたノルムの範囲としてエリアの最大サイズを得る。エリアのサイズとして、上記最小サイズと最大サイズとの間の何れかのサイズを選ぶことができる。
【００４０】
また上記の如く、グループに属するフリップフロップが変動してグループが変化すると、当該グループの中心の座標が変化する。そのため、グループが変化するたびにエリアを再計算して更新する。
【００４１】
以下に実施例に適用可能な様々なノルムの例を示す。
・グループのエリアの領域を規程するもののうちの一のものとしてのユークリッドノルムを以下に示す。
【００４２】
【数１】
ここでｘ１＝ｘ、ｘ２＝ｙとした場合、このノルムの範囲はユークリッド距離が一定の値の範囲となり、したがって円形の範囲となる。
・グループのエリアの領域を規程するもののうちの他の一のものとしての最大値ノルムを以下に示す。
【００４３】
【数２】
ここでｘ１＝ｘ、ｘ２＝ｙとした場合、このノルムの範囲はｘ、ｙの各々の値の最大値が一定の値の範囲となり、したがって正方形の範囲となる。
・グループのエリアの領域を規程するもののうちの更に他の一のものとしてのp次平均ノルムを以下に示す。
【００４４】
【数３】
ここでｘ１＝ｘ、ｘ２＝ｙとし、更にｐが１の場合、このノルムの範囲はｘ、ｙの合計が一定の値の範囲となり、したがって菱形の範囲となる。
【００４５】
上記図４Ａ乃至４Ｇの例の場合および以下に述べる例の場合、上記の如く、ｘ、ｙ座標の各々においてグループに属する全てのフリップフロップの最大座標および最小座標の中間の座標の位置をグループの中心とする。そして当該グループの中心からのノルムを上記図５Ａ、５Ｂとともに述べた条件で決定する。そしてこのようにして決定されたノルムの範囲としてエリアを得る。図４Ａ乃至４Ｇの例の場合および以下に述べる例の場合、上記最大値ノルムが使用され、上記グループの中心を中心とする正方形のエリアが決定される。
【００４６】
次に上記最適化１（交換）および最適化２（移動）について詳細に説明する。
【００４７】
図６Ａ，６Ｂは上記した初期グループ化Ｓ１００によって得られたグループの例を示す。
【００４８】
図６Ａに示す如く、この例の場合、計２０個のフリップフロップが３個のグループ、グループ１乃至３、Ｇ１、Ｇ２，Ｇ３にグループ化されている。また図６Ａには、これらグループ１乃至３、Ｇ１、Ｇ２，Ｇ３のそれぞれのエリア１乃至３、Ａ１，Ａ２，Ａ３が示されている。この例の場合、図６Ｂに示されるように、グループ１、Ｇ１には８個のフリップフロップが属し、グループ２、Ｇ２には８個のフリップフリップが属し、グループ３、Ｇ３には４個のフリップフロップが属する。この例の場合も許容ファンアウトは８とされている。また図６Ａに示される如く、上記エリア１乃至３、Ａ１，Ａ２，Ａ３は相互の重複している。図６Ａ，６Ｂ中、Ｃ１乃至Ｃ３は、それぞれグループ１乃至３、Ｇ１，Ｇ２，Ｇ３の中心を示している。したがって図６Ａ，６Ｂに示されるグループの場合、グループ１、Ｇ１に属する８個のフリップフリップにつき、その中心Ｃ１にクロックバッファが配置される。したがってグループ１、Ｇ１に属する８個のフリップフリップの各々に対し、その中心Ｃ１に配置されるクロックバッファによりクロック信号が供給されることになる。その際のクロックラインＬ１，Ｌ２，Ｌ３は図６Ａ，６Ｂに示される如く、配線長がいわゆるマンハッタン距離となるように接続される。なおクロックラインの接続の方法は上記マンハッタン距離となるような接続する場合に限られず、半導体集積回路に対し適用するテクノロジーに応じ適宜変更され得る。
【００４９】
次にこのようなグループに対し、最適化１（交換）を行う場合の例につき、図７Ａ乃至７Ｄともに詳細に説明する。
【００５０】
図７Ａは上記図６Ｂと同様のグループ化の状態を示す。ここで最適化１（交換）Ｓ２００として、図７Ａ中、グループ１、Ｇ１に属する８個のフリップフロップのうち、右上の２個のフリップフロップＡをグループ２、Ｇ２に移す。また同時に、上記２個のフリップフロップＡと交換に、グループ２、Ｇ２に属する８個のフリップフリップのうち、左下の２このフリップフロップＢをグループ１、Ｇ１に移す。その結果、図７Ｂに示す如くのグループに変化する。
【００５１】
以下に図７Ａの状態と図７Ｂの状態とを、クロックバッファと各フリップフロップとの間のクロックラインの長さについて比較する。ここで図７Ｂの場合、図７Ａの状態に対しグループが変化しているため、図７Ｂに示される変化後のグループの中心Ｃ１，Ｃ２，Ｃ３の位置は、変化前と異なっている。そして図７Ｂの場合、上記変化後のグループの中心Ｃ１，Ｃ２、Ｃ３にクロックバッファが配置され、当該クロックバッファから対応するグループに属する各フリップフロップに対しクロックラインが接続される。その場合のクロックラインＬ１，Ｌ２，Ｌ３が図７Ｂに示されている。図７ＡのクロックラインＬ１，Ｌ２，Ｌ３と比較すると、明らかに図７Ｂの方がクロックラインの総長が短縮されていることが分かる。
【００５２】
図７Ｃは上記最適化１（交換）Ｓ２００における動作の流れを説明するための図である。
【００５３】
図７Ｃ中、ステップＳ２０１にて、上記初期グループ化Ｓ１００の手順で生成されたグループから、２個のグループの組み合わせを抽出する。あるいは後述する最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の反復の際、前回の最適化３（結合）の結果得られたグループから２個のグループを抽出する。ステップＳ２０２にて、当該抽出に係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ２０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ２０２を実行する。
【００５４】
他方、ステップＳ２０２にて、当該抽出に係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ２０３にて、当該２個のグループ間で、それぞれのグループに属するフリップフロップ同士の交換を試みる。そして当該フリップフリップ同士の交換後の状態につき、各グループにおいて、当該グループの中心と、同グループに属するフリップフロップとの間のマンハッタン距離の合計を計算する。ここで得られるグループごとのマンハッタン距離の合計は、各グループのコスト（あるいは評価指標値）の一例として使用される。なお後述するように、当該コストは上記マンハッタン距離によるものの例に限られない。更に各グループのコストを全てのグループについて合計する。当該全てのグループについて求めた合計を全体のコストと称する。なおコストを求める方法につき後述する。
【００５５】
ステップＳ２０３では、上記交換の前後で全体のコストを比較し、当該交換の結果全体のコストが減少する場合、当該交換後のグループを維持する。ここでこのようにグループ間でフリップフロップ同士を交換すると、各グループに属するフリップフロップのうち当該交換に係るフリップフロップは交換以前のフリップフロップとは異なるものとなる。このようにグループに属するフリップフロップのうちの少なくともその一部のフリップフロップがそれ以前のものとは異なるものとなることを、「グループが変化する」と称する。同様に、グループに属するフリップフロップのうちの少なくともその一部のフリップフロップが他のグループに移動することにより減少する場合も「グループが変化する」と称する。同様に他のグループからフリップフロップが移動してくることにより当該グループに属するフリップフロップが増加する場合も「グループが変化する」と称する。このようにグループが変化した後の当該グループのコストを求める場合、予め当該グループの中心を、当該変化後のグループの中心に更新した上でコストを求める。
【００５６】
図７Ｃの説明に戻り、ステップＳ２０３にて、当該交換の結果全体のコストが減少しない場合、当該交換前のグループを維持する。このような動作を、それぞれが異なるグループに属する全てのフリップフロップ同士の組み合わせにつき一組ずつ順次反復して行う。そしてその都度、全体のコストが減少する場合には該当する交換後のグループを維持し、減少しない場合には交換前のグループを維持する。
【００５７】
このようにして上記２個のグループについてステップＳ２０３が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ２０４）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ２０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ２０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ２０４のＹＥＳ）、最適化１（交換）を終了する。
【００５８】
このようにしてステップＳ２０１にて全てのグループの組み合わせが順次抽出され、それぞれの組み合わせに対し順次ステップＳ２０２，Ｓ２０３が実行される。
【００５９】
図７Ｄは図７Ａの例に対し上記最適化１（交換）Ｓ２００を行う場合の、グループ１，２、Ｇ１，Ｇ２間でフリップフロップの交換を試みる方法について説明するための図である。上記の如く図７Ａの例の場合、グループ１，２の各々には許容ファンアウトである８個のフリップフリップが属する。したがって交換を試みるフリップフリップの組み合わせの数は、８×８＝６４であり、６４通りである。これら６４通りの各々につき、順次上記交換を試み、各グループの中心を更新した上で交換前後で全体のコストを比較する。その結果全体のコストが減少すれば当該交換後のグループを維持し、減少しなければ交換前のグループを維持する。このような動作を６４回反復する。実際に当該６４通りの反復を行った結果は以下の通りである。
【００６０】
すなわち、上記の如くグループ１，２、Ｇ１，Ｇ２間でフリップフロップＡ，Ｂの交換を行った場合全体のコストが減少する。他方、グループ１，３、Ｇ１，Ｇ３間およびグループ２，３、Ｇ２，Ｇ３間でフリップフロップの交換を行っても全体のコストは減少しない。その結果、このように図７Ａの例において上記図７Ｃとともに上述の最適化１（交換）Ｓ２００を行った結果、図７Ｂに示す如く、グループ１，２、Ｇ１，Ｇ２間でフリップフロップＡ，Ｂの交換のみが行われた状態のグループが得られる。
【００６１】
次に図８Ａ〜８Ｄとともに、最適化２（移動）Ｓ３００につき詳細な説明を行う。
【００６２】
図８Ａは図７Ｂの状態、すなわち上記７Ａのグループに対し上記最適化１（交換）が実行された状態を示す。ここで図８Ａの状態でグループ１、２，３、Ｇ１，Ｇ２，Ｇ３は、相互にそのエリアが重なり合っているものとする。この例の場合、例えば図８Ｂに示す如く、グループ２、Ｇ２に属する２つのフリップフロップＤのうちの何れか一個をグループ３、Ｇ３に移動した場合、全体のコストが最も減少する。すなわち、図８Ａのグループにおいて考え得るグループ間のフリップフロップの移動の全ての場合を試み、各場合についてグループの中心を更新した上で全体のコストの変化量を記憶装置に記憶しておく。このようにして記憶された、移動を試みた各場合の全体のコストの変化量のうち、最も減少量の大きい場合を得る。そして当該最も減少量の多い場合の移動のみを実際に行う。図８Ａ，８Ｂの場合、上記２このフリップフロップＤのうちの１個のフリップフリップの移動が上記最も減少量の多い場合に該当する。ここで図２とともに上記したように、最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００および最適化３（結合）は、終了判定Ｓ５００の結果が「一連の手順を反復する」であった場合、再度反復される。図８Ａ，８Ｂの場合、このように最適化２（移動）Ｓ３００が反復された場合を想定している。当該反復に係る最適化２（移動）Ｓ３００において、上記２このフリップフロップＤのうちの他の１個のフリップフリップの移動が上記最も減少量の多い場合に該当する。その結果、当該反復による２回の最適化２（移動）の各々の回において、上記２このフリップフロップＤの各々が、上記最も減少量の多い場合に該当し、当該移動が実際に行われる。
【００６３】
他方、図８Ｂに示す如く、グループ２、Ｇ２からグループ１、Ｇ１へのフリップフリップの移動を想定した場合、グループ１、Ｇ１に属するフリップフリップの個数は８個であり、既に許容ファンアウトに至っている。上記の如くグループ２、Ｇ２からグループ１、Ｇ１へのフリップフリップの移動を行った場合、グループ１、Ｇ１に属するフリップフロップの総数が９となってしまい、許容ファンアウト８を超えてしまう。したがってこのような移動は実際には行われない。
【００６４】
図８Ｃは上記の如くグループ２，３、Ｇ２，Ｇ３間で、最適化２（移動）Ｓ３００を試みる方法について説明するための図である。図８Ａの場合、グループ２、Ｇ２には計８個のフリップフリップが属し、グループ３、Ｇ３には計４個のフリップフロップが属する。この場合、グループ２に属する８個のフリップフロップの各々につき、グループ３への移動を試み、その都度各グループの中心を更新したうえで全体のコストを得、全体のコストの変化量を記憶装置に記憶しておく。他方、グループ３に属するフリップフリップをグループ２に移動することを想定すると、その場合、グループ２に属するフリップフリップの総数が９となり許容ファンアウト８を超える。したがってグループ３からグループ２への移動は実際には行われない。このようにして記憶された、各移動の場合の全体のコストの変化量を相互比較し、減少量が最も大きい場合の移動のみを実際に行い、それ以外の移動は実際には行わない。
【００６５】
図８Ｄは上記最適化２（移動）Ｓ３００における動作の流れを説明するための図である。
【００６６】
図８Ｄ中、ステップＳ３０１にて、前記最適化１（交換）の結果得られたグループから２個のグループの組み合わせを抽出する。ステップＳ３０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ３０１に戻り、他の２個のグループの組み合わせの抽出を新たに行い、当該新たな抽出に係るグループにつき、ステップＳ３０２を実行する。
【００６７】
他方、ステップＳ３０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ３０３にて、当該２個のグループ間で、それぞれのグループに属するフリップフロップの移動を試みる。そして当該フリップフリップの移動後の状態につき、各グループの中心を更新した上で全体のコストを求める。そして上記移動の前後で全体のコストを比較し、その都度コストの変化量を記憶装置に記憶しておく。このような動作を上記２個のグループの間で考え得る全てのフリップフロップの移動の場合について試み、それぞれの場合における全体のコストの変化量を記憶装置に記憶する。ここで上記の如く、少なくとも一方のグループに属するフリップフリップの総数が既に許容ファンアウト８に達している場合、当該グループに対するフリップフロップの移動は行わない。そしてステップＳ３０４にて、このようにして記憶された各移動の場合の全体のコストの変化量を相互に比較し、最も減少量の大きい場合の移動のみを実際に行い、他の場合の移動は行わない。
【００６８】
このようにして上記２個のグループについてステップＳ３０４が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ３０５）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ３０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ３０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ３０５のＹＥＳ）、最適化２（移動）を終了する。
【００６９】
このようにしてステップＳ３０１にて全てのグループの組み合わせが順次抽出され、ステップＳ３０２の条件を満たす全てのグループの組み合わせに対し順次ステップＳ３０３，Ｓ３０４が実行される。
【００７０】
図８Ａのグループに対し、上記図８Ｄとともに上述した最適化２（移動）Ｓ３００が実施された結果、上記の如く、グループ２、Ｇ２に属する２個のフリップフロップＤのうちの一個がグループ３、Ｇ３に移動される。そして最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００が反復され、当該反復に係る最適化２（移動）にて、今度はグループ２、Ｇ２に属する２個のフリップフロップＤのうちの他の一個がグループ３、Ｇ３に移動される。その結果図８Ｂに示される状態、すなわち結果的にグループ２、Ｇ２に属する２個のフリップフロップＤがグループ３、Ｇ３に移動される。なおこの場合、前記最適化３（結合）においては後述する結合を実行する条件が満たされず、実際には結合が行われなかったものとする。また前記反復に係る最適化１（交換）においても、交換により全体のコストが減少する場合が存在せず、実際には交換が行われなかったものとする。したがって最初の最適化２（移動）Ｓ３００と前記反復に係る２度目の最適化２（移動）Ｓ３００との間で実行される前記最適化３（結合）Ｓ４００および前記反復に係る最適化１（交換）Ｓ２００においては何らグループが変化しなかった場合を想定している。
【００７１】
図９は図８Ｂと同じ状態を示しており、上記最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００の効果について説明するための図である。
【００７２】
図９の状態を最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前の状態、すなわち図７Ａのグループの状態と比較する。図７Ａのグループの状態において図７Ａ中、例えばグループ１、Ｇ１を着目する。この場合、グループ１、Ｇ１には２個のフリップフロップＡが属しており、これらを含む計８個のフリップフリップは図７Ａ中、横方向に比較的広く分散している。この状態では図７Ａに示す如く、当該グループ１の中心Ｃ１にクロックバッファを設け、当該クロックバッファから当該８個のフリップフロップに対し配線長がマンハッタン距離をなすようにクロックラインＬ１を接続することになる。他方、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行後の状態、すなわち図９では同図中、グループ１、Ｇ１には２個のフリップフロップＡの代わりに、元はグループ２、Ｇ２に属していたフリップフロップＢが属している。その結果、これらを含む計８個のフリップフリップは図９、横方向において、比較的集中している。この状態では図９に示す如く、当該グループ１の中心Ｃ１にクロックバッファを設け、当該クロックバッファから当該８個のフリップフロップに対し配線長がマンハッタン距離をなすようにクロックラインＬ１を接続することになる。図７ＡにおけるクロックラインＬ１と図９におけるクロックラインＬ１とを比較すると、図９のクロックラインＬ１の総長の方が明らかに短縮されていることが分かる。同様な点はグループ２、Ｇ２のくロックラインＬ２についても言える。
【００７３】
次にグループ２，３、Ｇ２，Ｇ３につき、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前後の状態、すなわち図７Ａと図９の状態を相互に比較する。最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前にグループ２、Ｇ２に属していた２個のフリップフロップＤが、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行後にはグループ３、Ｇ３に属している。その結果グループ３についてのみ着目すると、グループ３に属するフリップフロップの総数が４から６に増加した分、クロックラインＬ３の総長は増加している。しかしながら同時にグループ２、Ｇ２について着目すると、上記の如くフリップフロップＢがフリップフロップＡと交換されたことに加え、フリップフロップＤがグループ３、Ｇ３に移動されている。その結果、図９の状態では、グループ２、Ｇ２に属する計６個のフリップフロップは、図９の横方向において比較して集中しており、その結果クロックラインＬ２は図７Ａの状態に比して大幅に短縮されている。その結果、全グループ１，２，３、Ｇ１，Ｇ２，Ｇ３を通じ、各グループのクロックラインＬ１，Ｌ２，Ｌ３の総長の合計は、図７Ａの状態に比し、図９の状態の方が明らかに短縮されている。
【００７４】
上記の如く、最適化１（交換）Ｓ２００の場合、図７ＣのステップＳ２０３にて、全体のコストが下がる場合にのみ実際にグループ間のフリップフロップの交換を行う。また、最適化２（移動）Ｓ３００の場合、図８ＤのステップＳ３０４にて全体のコストが最も下がる場合にのみ、グループ間の移動を行う。その結果図７Ａ，図９とともに上述の如く、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行により、全てのグループを通じ、クロックラインの総長の合計を短縮できる。
【００７５】
更に各グループのファンアウトに着目した場合、図７Ａの場合にはグループ１，２，３、Ｇ１，Ｇ２，Ｇ３のそれぞれのファンアウトが８，８，４である。これに対し、図９の場合にはグループ１，２，３、Ｇ１，Ｇ２，Ｇ３のファンアウトはそれぞれ８，６，６となっている。図７Ａの場合最大ファンアウト８と最小ファンアウト４との差が４であるのに対し、図９の場合は最大ファンアウト８と最小ファンアウト６との差が２である。よってファンアウトのバラツキが低減されている。
【００７６】
図１０Ａ乃至１０Ｃとともに上記最適化３（結合）Ｓ４００につき詳細に説明する。
【００７７】
図１０Ａは、上記最適化２（移動）Ｓ３００の結果得られたグループの例を示す。同図の例では回路には計２０個のフリップフロップが含まれ、グループ１、Ｇ１には４個のフリップフロップが属し、グループ２、Ｇ２にも４個のフリップフロップが属する。またグループ３、Ｇ３には８個のフリップフリップが属し、グループ４、Ｇ４には４個のフリップフロップが属する。更に図１０Ａの場合、グループ１，２の間で、各々のグループに属するフリップフロップが、他のグループのエリア内に位置するものとする。すなわちグループ１に属する４個のフリップフロップは、グループ２のエリア内に位置するものとする。同様にグループ２に属する４個のフリップフロップは、グループ１のエリア内に位置するものとする。このような関係はグループ３，４との間でも成立するものとする。すなわち、グループ３に属する８個のフリップフロップは、グループ４のエリア内に位置するものとする。同様にグループ４に属する４個のフリップフロップは、グループ３のエリア内に位置するものとする。
【００７８】
このように２個のグループが以下の関係を有する際、当該関係を「互いのフリップフリップが互いのエリアに含まれる関係」と称する。すなわち一のグループに属する全てのフリップフロップが他の一のグループのエリア内に位置し、前記他の一のグループに属する全てのフリップフロップが前記一のグループのエリア内に位置する関係である。
【００７９】
ここで最適化３（結合）Ｓ４００では、互いのフリップフリップが互いのエリアに含まれる関係を有するグループ１，２、Ｇ１，Ｇ２の間、およびグループ３，４、Ｇ３，Ｇ４の間の各々につき、以下の動作を行う。すなわち２個のグループのファンアウトを合計した場合に許容ファンアウト以内である場合、当該２個のグループを結合して１個のグループとなるようにグループの変更を行う。上記の如く、フリップフロップにクロック信号を供給する際、各グループに一のクロックバッファを設ける。上記の如くグループ同士の結合を行うことにより、回路に含まれるフリップフロップが属するグループの総数が減少する。その結果回路全体を通じ、使用するクロックバッファの数が減少する。その結果消費電力を低減させることができる。
【００８０】
図１０Ａの例の場合、まずグループ１，２、Ｇ１，Ｇ２の間では、上記の如く、各グループに属するフリップフロップの数は４であり、すなわちファンアウトが４である。したがってグループ１，２のファンアウトを合計すると８となり、許容ファンアウト８以内に収まっている。したがって図１０Ｂに示される如く、グループ１，２を結合する。他方グループ３，４の間では、上記の如く、各グループに属するフリップフロップの数はそれぞれ８、４であり、すなわちファンアウトがそれぞれ８，４である。したがってグループ３，４のファンアウトを合計すると１２となり、許容ファンアウト８を超える。したがって図１０Ｂに示される如く、グループ３，４を結合することはしない。
【００８１】
図１０Ｃは最適化３（結合）Ｓ４００の動作の流れを説明するための図である。
【００８２】
図１０Ｃ中、ステップＳ４０１にて、前記最適化２（移動）Ｓ３００の結果得られたグループから２個のグループの組み合わせを抽出する。ステップＳ４０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。
【００８３】
他方、ステップＳ４０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ４０３にて、当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有するか否かを判定する。当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有さない場合、ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有する場合、ステップＳ４０４を実行する。
【００８４】
ステップＳ４０４では、当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まるか否かを判定する。当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まらない場合ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まる場合、ステップＳ４０５を実行する。ステップＳ４０５では、当該２個のグループを結合し、１個のグループとする。このようにして上記２個のグループについてステップＳ４０５が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ４０６）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ４０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ４０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ４０６のＹＥＳ）、最適化３（結合）を終了する。
【００８５】
このようにしてステップＳ４０１にて全てのグループの組み合わせが順次抽出され、各々の組み合わせに係る２個のグループに対し、上記同様、ステップＳ４０２以降の動作を実行する。
【００８６】
次に図１１とともに、図２に示す終了判定Ｓ５００につき説明を行う。
【００８７】
終了判定Ｓ５００では、以下の条件１あるいは条件２を満たす場合に収束したと判断し、一連の手順を終了する。すなわち最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行を終了し、図２の処理を終了する。
【００８８】
条件１：
以下の全ての条件１）、２）、３）が満たされる：
１）最適化１（交換）Ｓ２００の前後で全体のコストが一定であり減少しない。
【００８９】
２）最適化２（移動）Ｓ３００の前後で全体のコストが一定であり減少しない。
【００９０】
３）最適化３（結合）Ｓ４００の前後で全体のコストが一定であり減少しない。
【００９１】
条件２：
最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の回数ｎが所定回数に至った。
【００９２】
図１２Ａ、１２Ｂ，１２Ｃ、１２Ｄとともに、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の例につき説明する。
【００９３】
図１２Ａは初期グループ化Ｓ１００によってグループ１，２，３、Ｇ１，Ｇ２，Ｇ３が得られた状態を示す。図１２Ａに示す如く、グループ１、Ｇ１には８個のフリップフロップが属し、グループ２、Ｇ２には８個のフリップフリップが属し、グループ３、Ｇ３には６個のフリップフロップが属する。
【００９４】
最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の各々では、グループ１と２、Ｇ１，Ｇ２，グループ１と３、Ｇ１，Ｇ３、グループ２と３、Ｇ２，Ｇ３の順番で処理を行うものとする。
【００９５】
図１２Ａの状態ではグループ１と２では、相互のエリア１と２、Ａ１，Ａ２が重なっていない。したがって最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００のいずれにおいても処理対象とならない（図７Ｃ中、ステップＳ２０２のＮＯ、図８Ｄ中、ステップＳ３０２のＮＯ、図１０Ｃ中、ステップＳ４０２のＮＯ）。他方グループ２と３では、相互のエリア２と３、Ａ２，Ａ３が重なっている。したがって最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００のいずれにおいても処理対象となる（図７Ｃ中、ステップＳ２０２のＹＥＳ、図８Ｄ中、ステップＳ３０２のＹＥＳ、図１０Ｃ中、ステップＳ４０２のＹＥＳ）。この例の場合、図１２Ｂに示される如く、最適化２（移動）Ｓ３００の反復により、グループ２から２個のフリップフリップＥがグループ３に移動されたものと想定する。
【００９６】
上記グループ２、Ｇ２からグループ３、Ｇ３への２個のフリップフロップＥの移動の結果、図１２Ｃに示す如く、グループ２，３の各々に属するフリップフロップが変化する。その結果図１２Ｃに示す如く、各グループ２，３の中心Ｃ２，Ｃ３が変化する。例えばグループ２、Ｇ２の場合上記の如く、右端部に有ったフリップフリップＥがグループ３、Ｇ３へ移動している。その結果グループ２には６個のフリップフロップが残る。当該残った６個のフリップフロップの中心は、前記移動前の８個のフリップフロップの場合の中心に対し、左側に移動している。したがってグループ２の中心Ｃ２はこれに対応して左側に移動する。ここでグループ２のエリア２、Ａ２は上記の如く、当該グループの中心Ｃ２を中心とする一定サイズの正方形である。上記の如くグループ２の中心Ｃ２の左側の移動により、エリア２、Ａ２もこれに対応して左側に移動する（図１２Ｃ参照）。
【００９７】
その結果図１２Ｃに示す如く、グループ１と２との間で、相互にエリア１と２、Ａ１，Ａ２とが重なる。この状態で最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００を実行した場合、上記図１２Ａの場合と異なり、グループ１と２との間が処理対象となる（図７Ｃ中、ステップＳ２０２のＹＥＳ、図８Ｄ中、ステップＳ３０２のＹＥＳ、図１０Ｃ中、ステップＳ４０２のＹＥＳ）。その結果図１２Ｄに示す如く、例えば最適化２（移動）Ｓ３００において、グループ１、Ｇ１のフリップフロップＦがグループ２、Ｇ２に移動される。
【００９８】
このように実施例のクロック信号供給回路の設計方法によれば、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行においてグループが変化すると、それに対応してそのエリアが変化する。エリアが変化すると、当初重なっていなかったグループ相互でエリアが重なり合う場合がある。そのような場合、当初はエリアの重なりが無くグループ相互間が最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の処理対象外であったものが、新たに処理対象となる。その結果最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の処理対象範囲が広がり、より効果的な最適化が期待できる。
【００９９】
図１３とともに、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の追加的な条件について述べる。
【０１００】
すなわち、前回の最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行において、ある組み合わせに係るグループ間ではフリップフロップの交換も移動も実際には行われず、当該グループが変化しなかった場合を想定する。そのような場合、当該グループ間ではそれ以降、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００を行わないものとすることができる。そのようにすることによって、該当する組み合わせに係るグループは処理対象外となる．その結果以後該当する組み合わせに係るグループについての処理が実行されないため、処理量が削減できる。
【０１０１】
図１４とともに、上記終了判定Ｓ５００にて「一連の手順を終了する」旨の判定がなされた以後の動作につき説明する。
【０１０２】
各グループ１，２，３、Ｇ１，Ｇ２，Ｇ３のそれぞれの中心Ｃ１，Ｃ２，Ｃ３にクロックバッファＢ１，Ｂ２，Ｂ３を挿入する。次にクロックバッファＢ１，Ｂ２、Ｂ３から、それぞれのグループ１，２，３のフリップフロップに対し、クロックラインＬ１，Ｌ２，Ｌ３を接続する。そしてクロックバッファＢ１，Ｂ２，Ｂ３から、最も近いＨ型ツリーの末端ＢにクロックラインＬ０を接続する。その結果Ｈ型ツリーの末端Ｂに、各クロックバッファＢ１，Ｂ２，Ｂ３を介し、各グループ１，２，３に属するフリップフロップがクロックラインＬ０，Ｌ１，Ｌ２，Ｌ３により接続される。
【０１０３】
以下に上記コストを求める方法につき、数式を使用した説明を行う。
【０１０４】
グループの中心の座標は以下の数式で得られる。
【０１０５】
Xg = ( Xfmax + Xfmin ) / 2
Yg = ( Yfmax + Yfmin ) / 2
ここでＸｆｍａｘ，Ｘｆｍｉｎは、それぞれグループ内のフリップフロップの最大ｘ座標、最小ｘ座標をそれぞれ示す。同様にＹｆｍａｘ，Ｙｆｍｉｎは、それぞれグループ内のフリップフロップの最大ｙ座標、最小ｙ座標をそれぞれ示す。
【０１０６】
各グループのコストは以下の数式で得られる。
【０１０７】
Cg = Σ( | Xf - Xg | + | Yf - Yg | )
ここでグループのコストは上記の如く、グループの中心からフリップフリップまでのマンハッタン距離の総和である。マンハッタン距離はクロックラインの配線長に対応するため、グループのコストは当該グループに属するフリップフロップに係るクロックラインの総配線長に対応する。
【０１０８】
全体のコストは以下の数式で得られる。
【０１０９】
C = ΣCg
上記最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００におけるコストの変化量は以下の数式で得られる。
【０１１０】
ΔC = { Cia + Cja } − { Cib + Cjb }
= { Σ( | Xf - Xia | + | Yf - Yia | ) + Σ( | Xf - Xja | + | Yf - Yja | ) } -
{ Σ( | Xf - Xib | + | Yf - Yib | ) + Σ( | Xf - Xjb | + | Yf - Yjb | ) }
ここで
C:コスト
f: フリップフリップの識別番号
Ｃｇにおけるg:グループの識別番号
Xf:フリップフリップのｘ座標
Yf:フリップフリップのｙ座標
Xg:グループの中心のｘ座標
Yg:グループの中心のｙ座標
またi, jは交換・移動の対象となるグループの組み合わせにおける各グループの識別番号を示し、aは交換・移動後、bは交換・移動前であることを示す。
【０１１１】
上記各グループのコストＣｇ（すなわち評価指標値）としては上記の例、すなわち
マンハッタン距離：Cg = Σ( | Xf - Xg | + | Yf - Yg | )
によるものに限られず、例えば以下に示すユークリッド距離、総配線長、容量および遅延等のうちのいずれか一のものによるものとすることができる。
【０１１２】
１．ユークリッド距離：Cg = Σ{ ( Xf - Xg ) + ( Yf - Yg ) }
２．総配線長：Cg = クロックバッファから各フリップフロップまでの総配線長
３．容量(負荷)：Cg = クロックバッファのゲート容量+ 配線容量+ 各フリップフロップのクロック入力ピン容量
４．遅延：Cg = クロックバッファから各フリップフロップのクロック入力ピンまでの遅延の合計
以下に図１とともに、実施例のクロック信号供給回路の設計方法をプログラムで実現する際の処理の概要を述べる。
【０１１３】
図１に示される如くネットリスト(周知のVerilog, VHDL等)１が記憶装置からＣＰＵに読み込まれ、ＣＰＵは当該ネットリスト１からフリップフロップのインスタンスを抽出する（図１中、データリード４）。またＣＰＵは抽出されたフリップフロップをグループ化する（図１中、フリップフロップのグループ化５）。またＣＰＵはグループ化で得られたグループに対し、ネットリスト上で、図１４とともに上述の如くクロックバッファを挿入し、クロックラインを接続する。そしてＣＰＵは、このようにクロックバッファが挿入され、クロックラインが接続された状態のネットリスト７を記憶装置に書き込む（図１中、データライト６）。
【０１１４】
同様に図１に示される如く、レイアウトデータ(DEF or PKIT等)２が記憶装置からＣＰＵに読み込まれ、ＣＰＵは当該レイアウトデータ２から上記フリップフロップのインスタンスの座標を抽出する（図１中、データリード４）。そしてＣＰＵは抽出された座標に基づいて上記グループ化を行う（図１中、フリップフロップのグループ化５）。またＣＰＵはグループ化で得られたグループに対し、レイアウトデータ上で、図１４とともに上述の如くクロックバッファを配置し、クロックラインを配置する。そしてＣＰＵはこのようにクロックバッファが配置され、クロックラインが配置された状態のレイアウトデータ８を記憶装置に書き込む（図１中、データライト６）。
【０１１５】
また設計者はコンピュータに対し、コマンドラインの形態で各種のパラメータ３を入力する。当該各種のパラメータは図１とともに上記の如く、エリアの定義（すなわちエリアの決定方法）、許容ファンアウト、図２に示す最適化１〜３（Ｓ２００〜Ｓ４００）の反復回数ｎ等を含む。上記エリアの決定方法とは、例えば上記の如く、最大値ノルムを使用して一定サイズの正方形のエリアを得る方法である。
【０１１６】
また上記ＣＰＵは、グループ化５の結果得られるグループを示すデータファイル９を記憶装置に書き込む。このデータファイル９には各グループに属するフリップフロップを示す情報が含まれ、例えば周知のＣＳＶ（Ｃｏｍｍａ Ｓｅｐａｒａｔｅｄ Ｖａｌｕｅ ｆｏｒｍａｔ）形式のファイルとされる。
【０１１７】
実施例のクロック信号供給回路の設計方法によれば、以下の効果が得られる。
【０１１８】
１）クロックバッファからのクロックラインの配線長を短縮し、そのバラツキを低減することが可能である。
【０１１９】
２）クロックバッファごとのファンアウトのバラツキを低減可能である。
【０１２０】
３）クロックバッファの個数を削減可能である。
【０１２１】
４）半導体集積回路において、局所的ではなく、全体的にクロックスキューを改善し得る。
【０１２２】
５）プログラム言語で記述することができる。また、現実的な計算量、現実的な記憶領域でグループ化を実施することができる。これはエリアが重なり合うグループ間のみが最適化の処理対象となるため、処理量は処理対象のフリップフロップの個数に対し線形に増加するにすぎない。またコストが減少する場合にグループの変更を実施するため、コストは単調に減少する。
【０１２３】
このように実施例のクロック信号供給回路の設計方法によれば、半導体集積回路におけるクロックスキューを低減し得るクロック信号供給回路の設計方法を自動化し得る。
【０１２４】
図１５とともに実施例のクロック信号供給回路の設計方法を適用可能な半導体集積回路の例について説明する。
【０１２５】
図１５は実施例のクロック信号供給回路の設計方法を適用可能な半導体集積回路の例としての、ＤＩＭＭ（Ｄｕａｌ Ｉｎｌｉｎｅ Ｍｅｍｏｒｙ Ｍｏｄｕｌｅ）を制御するメモリコントローラを示す。当該メモリコントローラの動作周波数は例えばＧＨｚのオーダーを超えるものとされる。
【０１２６】
出願人は図１５とともに上記したメモリコントローラの回路設計において、実施例のクロック信号供給回路の設計方法を実行した。より具体的には、同方法をプログラムで実現し、クロックバッファの挿入およびクロックラインの接続に係る回路設計を自動化して実施した。
【０１２７】
その結果フリップフロップ間のクロックスキューを低減することができた。またセットアップタイミング、ホールドタイミング等に係る設計作業を容易に成しえた。また自動化により、グループ化、ゲートエントリ、スキュー調整、タイミング調整、配置等の工数を削減できた。したがってＬＳＩ開発期間の短縮、開発コストの削減が可能な点が確認できた。
【０１２８】
図１６は実施例のクロック信号供給回路の設計方法をプログラムで実現する場合に使用可能なコンピュータの構成を説明するためのブロック図である。
【０１２９】
図１６に示すごとく、同コンピュータ５００は、与えられたプログラムを構成する命令を実行することによって様々な動作を実行するためのＣＰＵ５０１と、キーボード、マウス等よりなり設計者が操作内容又はデータを入力するための操作部５０２とを有する。またコンピュータ５００は、設計者にＣＰＵ５０１による処理経過、処理結果等を表示するＣＲＴ、液晶表示器等よりなる表示部５０３を有する。またコンピュータ５００は、ＲＯＭ、ＲＡＭ等よりなりＣＰＵ５０４が実行するプログラム、データ等を記憶したり作業領域として使用される上記記憶装置としてのメモリ５０４を有する。またコンピュータ５００は，プログラム、データ等を格納する上記記憶装置としてのハードディスク装置５０５を有する。またコンピュータ５００は、上記記憶装置としてのＣＤ−ＲＯＭ５０７を媒介として外部からプログラムをロードしたりデータをロードするためのＣＤ−ＲＯＭドライブ５０６を有する。またコンピュータ５００は、インターネット、ＬＡＮ等の通信網５０９を介して外部サーバからプログラムをダウンロード等するためのモデム５０８を有する。
【０１３０】
コンピュータ５００はＣＤ−ＲＯＭ５０７を媒介として、あるいは通信ネットワーク５０９を媒介として、上述の実施例のクロック信号供給回路の設計方法をＣＰＵ５０１に実行させるためのプログラムをロードあるいはダウンロードする。そしてこれをハードディスク装置５０５にインストールし、適宜メモリ５０４にロードしてＣＰＵ５０１が実行する。その結果、同コンピュータ５００により実施例のクロック信号供給回路の設計方法が自動的に実行される。
【０１３１】
なお実施例のクロック信号供給回路の設計方法は上記の如くフリップフロップにクロック信号を供給する回路の設計方法に限られず、他の回路素子にクロック信号を供給する回路の設計方法にも同様に適用可能である。
【０１３２】
また実施例のクロック信号供給回路の設計方法では、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００を当該順番に実施するものとして説明した。しかしながら最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の実行の順序はこの順序に限られず、他の順序で実行してもよい。
【０１３３】
また最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の全てを実行するように説明した。しかしながら、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の計３種の最適化のうちの少なくとも一種の最適化のみを実行するようにしてもよい。
【０１３４】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
演算手段がクロック信号の供給される複数の回路素子の回路データを記憶装置から読み込む段階と、
演算手段が前記複数の回路素子をグループ分けする段階と、
演算手段がグループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する段階とを有するクロック信号供給回路の設計方法であって、
前記各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号を供給することを特徴とするクロック信号供給回路の設計方法。
（付記２）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
付記１に記載のクロック信号供給回路の設計方法。
（付記３）
前記グループ分けする段階は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする付記１に記載のクロック信号供給回路の設計方法。
（付記４）
前記最適化段階では更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記３に記載のクロック信号供給回路の設計方法。
（付記５）
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記３または４に記載のクロック信号供給回路の設計方法。
（付記６）
コンピュータに、クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該グループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復させるプログラム。
（付記７）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
請求項６に記載のプログラム。
（付記８）
更にコンピュータに、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得る段階を実行させることを特徴とする請求項６に記載のプログラム。
（付記９）
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記８に記載のプログラム。
（付記１０）
前記交換段階では、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階では、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記８または９に記載のプログラム。
（付記１１）
クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該複数のグループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくとも何れかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する演算手段を有し、
前記最適化段階の反復の結果得られる各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号が供給されることを特徴とする情報処理装置。
（付記１２）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
請求項１１に記載の情報処理装置。
（付記１３）
更に前記演算手段は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１１に記載の情報処理装置。
（付記１４）
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記１３に記載の情報処理装置。
（付記１５）
前記交換段階では、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階では、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記１３または１４に記載の情報処理装置。
【図面の簡単な説明】
【０１３５】
【図１】実施例によるクロック信号供給回路の設計方法のデータの流れを示す図である。
【図２】図１中、フリップフロップのグループ化の基本的なアルゴリズムの流れを示す図である。
【図３】図２中、初期グループ化の動作の流れを示す図である。
【図４Ａ】初期グループ化の動作を説明するための図（その１）である。
【図４Ｂ】初期グループ化の動作を説明するための図（その２）である。
【図４Ｃ】初期グループ化の動作を説明するための図（その３）である。
【図４Ｄ】初期グループ化の動作を説明するための図（その４）である。
【図４Ｅ】初期グループ化の動作を説明するための図（その５）である。
【図４Ｆ】初期グループ化の動作を説明するための図（その６）である。
【図４Ｇ】初期グループ化の動作を説明するための図（その７）である。
【図５Ａ】初期グループ化におけるグループのエリアの決め方について説明するための図（その１）である。
【図５Ｂ】初期グループ化におけるグループのエリアの決め方について説明するための図（その２）である。
【図６Ａ】初期グループ化を実行後の状態の例を示す図（その１）である。
【図６Ｂ】初期グループ化を実行後の状態の例を示す図（その２）である。
【図７Ａ】最適化１（交換）について説明するための図（その１）である。
【図７Ｂ】最適化１（交換）について説明するための図（その２）である。
【図７Ｃ】最適化１（交換）について説明するための図（その３）である。
【図７Ｄ】最適化１（交換）について説明するための図（その４）である。
【図８Ａ】最適化２（移動）について説明するための図（その１）である。
【図８Ｂ】最適化２（移動）について説明するための図（その２）である。
【図８Ｃ】最適化２（移動）について説明するための図（その３）である。
【図８Ｄ】最適化２（移動）について説明するための図（その４）である。
【図９】最適化１，最適化２を実行後の状態の例を示す図である。
【図１０Ａ】最適化３（結合）について説明するための図（その１）である。
【図１０Ｂ】最適化３（結合）について説明するための図（その２）である。
【図１０Ｃ】最適化３（結合）について説明するための図（その３）である。
【図１１】フリップフロップのグループ化における収束の判定について説明するための図である。
【図１２Ａ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その１）である。
【図１２Ｂ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その２）である。
【図１２Ｃ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その３）である。
【図１２Ｄ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その４）である。
【図１３】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その５）である。
【図１４】クロックバッファの挿入、クロックラインの接続について説明するための図である。
【図１５】実施例の効果の検証について説明するための図である。
【図１６】実施例によるクロック信号供給回路の設計方法をコンピュータで実現する場合について説明するための図である。
【符号の説明】
【０１３６】
５０１ ＣＰＵ
５０２ 操作部
５０３ 表示部
５０４ メモリ（記憶装置）
５０５ ＨＤＤ（記憶装置）
５０６ ＣＤ−ＲＯＭドライブ
５０７ ＣＤ―ＲＯＭ（記憶装置）
５０８ モデム
５０９ 通信網
ＦＦ フリップフロップ
Ｇ１，Ｇ２，Ｇ３，... グループ
Ａ１，Ａ２，Ａ３，... エリア
Ｃ１，Ｃ２，Ｃ３，．． グループの中心
Ｂ１，Ｂ２，Ｂ３，... クロックバッファ
Ｌ０，Ｌ１，Ｌ２，Ｌ３，... クロックライン
【技術分野】
【０００１】
本発明はクロック信号供給回路の設計方法、情報処理装置およびプログラムに係り、特に一のクロックバッファによってクロック信号が供給される回路素子のグループ分けの方法に関する。なおクロックバッファとは、クロック信号を中継する機能を有するバッファを意味する（以下同様）。
【背景技術】
【０００２】
半導体集積回路において、フリップフロップ等の回路素子に対し、クロックバッファを用いてクロック信号を供給する。この場合、一のクロックバッファによってクロック信号が供給される回路素子のグループを形成する。なお以下の説明において「グループ」とは一のクロックバッファによってクロック信号が供給される回路素子のグループを意味し、そのようなグループを形成することをグループ分けあるいはグループ化と称する。
【特許文献１】特開２００７−２７８４１号公報
【特許文献２】特開２００７−１２８４２９号公報
【特許文献３】特開平７−１３４６２６号公報
【特許文献４】特開平１１−２１４５１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
効果的なグループ分けを行い得るクロック信号供給回路の設計方法を提供することが目的である。
【課題を解決するための手段】
【０００４】
クロック信号供給回路の設計方法では以下に示す最適化を行う。すなわちグループ間で回路素子の交換および移動のうちの少なくとも何れか一方を実行する。そして各グループの中心位置と当該グループ内の各回路素子との間の距離を合計する。更に当該グループごとの合計を全グループにつき合計する。そして全グループのついての合計が減少する場合に前記交換および移動のうちの少なくとも何れか一方の実行後のグループを維持する。他方全グループのついての合計が減少しない場合には前記交換および移動のうちの少なくとも何れか一方の実行前のグループを維持する。そして当該最適化を反復する。結果的に得られた各グループにつき、当該グループの中心位置にクロックバッファを設け、グループ内の各回路素子にクロック信号を供給する。
【発明の効果】
【０００５】
クロック信号供給回路の設計方法において、上記最適化では各グループの中心位置と当該グループ内の各回路素子との間の距離を合計の全グループのついての合計が減少する場合に前記交換および移動のうちの少なくとも何れか一方の実行後のグループを維持する。他方全グループのついての合計が減少しない場合には前記交換および移動のうちの少なくとも何れか一方の実行前のグループを維持する。更に最適化を反復する。このため、全グループを通し、各グループのクロックバッファから各回路素子までの距離が効果的に短縮される。
【発明を実施するための最良の形態】
【０００６】
例えばフリップフロップのセットアップタイミング、ホールドタイミングの条件を満たすためにはクロックスキューを小さくする必要がある。なおクロックスキューとは、例えばクロック信号がフリップフロップに供給される際にフリップフロップ間で生ずる遅延差を意味する（以下同様）。またクロックバッファは動作率が高いため、回路全体の消費電力の削減のため設置個数を少なくすることが望ましい。
【０００７】
またクロックバッファからフリップフロップ等の回路素子までの配線長を短縮し、そのばらつきを低減することが望ましい。またクロックバッファのファンアウトを一定数以下とすることが望ましい。なおクロックバッファのファンアウトとは、クロックバッファを用いてクロック信号を供給する際、一のクロックバッファによってクロック信号が供給される回路素子の個数を意味する（以下同様）。また許容ファンアウトとは、ファンアウトの許容値を意味する（以下同様）。またクロックドメインごとにグループ化を行う必要がある。
【０００８】
実施例によるクロック信号供給回路の設計方法では、半導体集積回路の回路設計において、回路に含まれる各フリップフロップに対しクロック信号を供給する際、最初にいわゆるH型クロックツリーを作成する。ここでＨ型クロックツリーとはフリップフロップ等の回路素子にクロック信号を供給するための配線経路の構造である（以下同様）。そして上記Ｈ型クロックツリーの末端から各フリップフロップまでをクロックバッファを介してクロックラインで接続する。ここでクロックラインとはクロック信号を供給する配線を意味する（以下同様）。より具体的には、回路に含まれるフリップフロップをグループ化し、各グループに対し一のクロックバッファを割り当て、Ｈ型クロックツリーの末端から各クロックバッファに対しクロックラインを接続する。また各クロックバッファから該当するグループに属するフリップフロップとの間もクロックラインで接続する。その結果、Ｈ型クロックツリーの末端から、各クロックバッファを介し、それぞれのフリップフロップにクロックラインが接続される。その結果、同クロックラインを通じてクロック信号がそれぞれのフリップフロップに供給される。
【０００９】
実施例では上記グループ化を行う際、最初に仮のグループ化（以下初期グループ化と称する）を行い、初期グループ化で得られたグループに対し後述する最適化を反復して行う。最適化とは、グループ間のフリップフロップの交換や移動を含む。更に前記交換や移動のたび、各グループの中心位置と当該グループに属するフリップフロップとの間の距離の合計を計算し、更にグループごとの合計を全グループについて合計する。全グループについての合計が減少する場合に、上記グループ間のフリップフロップの交換や移動後のグループを維持する。全グループについての合計が減少しない場合には、上記グループ間のフリップフロップの交換や移動前のグループを維持する。また最適化は、一定の条件を満たす場合に行うグループ同士の結合を含む。そして上記最適化を反復して行う。
【００１０】
各グループの中心位置には、当該グループに属するフリップフロップに対しクロック信号を供給するクロックバッファが設けられる。したがって各グループの中心位置と当該グループに属するフリップフロップとの間の距離が短いほど、クロックバッファから各フリップフロップに接続するクロックラインが短い。その結果クロックスキューを低減することもできる。
【００１１】
上記の如く最適化を反復して行うことにより最適なグループ化を行うことができる。その結果高周波数の領域(GHz帯等)において、クロックスキューを効果的に低減し得るフリップフロップのグループ化を行える。
【００１２】
上記最適化の動作は、当該動作をコンピュータに実行させるためのプログラムにより自動化し得る。すなわち上記最適化のための一連の手続きをアルゴリズムとして規定し、プログラム化する。ここで当該プログラムによる処理量は取り扱うフリップフロップの個数に対し線形で増加する。したがって処理量が現実的な程度に収まり、その際に必要とされるメモリの記憶領域も現実的な程度に収まるように上記プログラムを提供し得る。ここで上記最適化を反復して実行する場合、上記各グループの中心位置と当該グループに属するフリップフロップとの間の距離の合計の更にグループごとの合計は、上記反復に対し、収束する。
【００１３】
図１は実施例のクロック信号供給回路の設計方法におけるデータの流れを説明するための図である。
【００１４】
図１中、設計者は半導体集積回路のネットリスト１，レイアウトデータ２に加え、最適化の実行に係るエリアの定義、許容ファンアウトおよび反復回数等のパラメータ３を設定する。
【００１５】
上記ネットリスト１，レイアウトデータ２およびパラメータ３は、コンピュータにおいて、前記プログラムにしたがって、記憶装置からＣＰＵによって読み込まれ（４）、ＣＰＵによりグループ化（５）がなされる。すなわちコンピュータはプログラムにしたがって上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップをグループ化する。ここでは上記最適化が適宜反復して実行され、最適なグループ化がなされる。そしてグループ化で得られたグループに基づきコンピュータにより、ネットリストおよびレイアウトデータ上、クロックバッファの挿入およびクロックラインの接続がなされる。なおクロックバッファの挿入およびクロックラインの接続については図１４とともに後述する。そしてクロックバッファの挿入およびクロックラインの接続がなされた状態のネットリスト７およびレイアウトデータ８がＣＰＵにより記憶装置に書き込まれる（６）。またこの場合、別途上記グループ化の内容を示す情報「グループデータ」９もＣＰＵにより記憶装置に書き込まれる。設計者はグループデータ９を見てグループ化の内容をマニュアルで編集することができる。
【００１６】
このように設計者により編集されたグループデータをコンピュータに入力することにより、同編集後のグループデータがＣＰＵにより記憶装置から読み取られ（４）、同編集後のグループデータに基づいてクロックバッファの挿入およびクロックラインの接続がなされる。そしてこの場合もクロックバッファの挿入およびクロックラインの接続がなされたネットリスト７およびレイアウトデータ８がＣＰＵにより記憶装置に書き込まれる（６）。
【００１７】
図２は上記実施例によるクロック信号供給回路の設計方法をコンピュータで実現するためのプログラムのアルゴリズムの大略の流れを説明するため図である。
【００１８】
同アルゴリズムは、初期グループ化Ｓ１００，最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００を含む。これらＳ１００、Ｓ２００，Ｓ３００，Ｓ４００の手順を実行後、終了判定Ｓ５００が実行される。終了判定Ｓ５００では、一定の条件を満たす場合には図２に示される一連の手順の終了を決定する。一定の条件を満たさない場合には再度上記最適化１、２，３（Ｓ２００，Ｓ３００，Ｓ４００）の各手順が反復される。
【００１９】
図３は上記初期グループ化Ｓ１００の詳細を説明するための図である。
【００２０】
図３中、ステップＳ１０１にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップから一のフリップフロップを選択する。この選択の順序は例えばネットリスト上の番号による。ステップＳ１０２にて、既にグループが存在するか否かを判定する。初期段階ではグループは存在しないため（ＮＯ），ステップＳ１０６に移行する。ステップＳ１０６にて、当該一のフリップフロップが属するグループを設定する。そしてステップＳ１０７にて、当該一のフリップフロップの位置に基づき、回路のレイアウト上で当該グループのエリアを設定する。
【００２１】
次にステップＳ１０８にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０１で既に選択されたかを判定する。ここで上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが選択された場合とは、上記全てのフリップフロップが、ステップＳ１０６で設定されたグループに属する場合を意味する。回路に含まれる全てのフリップフリップがステップＳ１０１で選択されてはいなかった場合、ステップＳ１０１に戻る。
【００２２】
ステップＳ１０１にて、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップから、上記一のフリップフロップ以外の他のフリップフロップを選択する。次にステップＳ１０２にて、既にグループが存在するか否かを判定する。ここでは既に上記ステップＳ１０６でグループが設けられている（ＹＥＳ）。このためステップＳ１０３に移行する。なおここで、ステップＳ１０６にて新たなグループが作成された直後のステップＳ１０２においては、当該新たなグループが選択される。また、直前のステップＳ１０３，Ｓ１０４がともにＹＥＳであり、ステップＳ１０５で処理中のフリップフロップが当該グループに追加された場合においても、その直後のステップＳ１０２では当該グループが選択される。他方、直前のステップＳ１０３あるいはＳ１０４の結果がＮＯとなり、その結果次のステップＳ１０５にて現在処理中のフリップフロップを当該グループに追加することができない場合の直後のステップＳ１０２では、当該グループ以外の既存のグループが選択される。
【００２３】
次にステップＳ１０３にて、ステップＳ１０１で選択されたフリップフロップが、ステップＳ１０２にて選択されたグループにつき、ステップＳ１０７で設定されたエリア内に位置するか否かを判定する。エリア内に位置する場合、次にステップＳ１０４にて、前記選択されたグループにつき、ステップＳ１０６で設定されたグループに属するフリップフロップの個数が、上記パラメータ３に含まれる許容ファンアウト以内か否かを判定する。許容ファンアウト以内であれば（ＹＥＳ）、ステップＳ１０５にて、ステップＳ１０１で選択されたフリップフロップを、ステップＳ１０６で当該グループに追加する。そしてステップＳ１０７にて、当該グループに属するフリップフロップの位置に基づき、当該グループのエリアを更新する。
【００２４】
その後ステップＳ１０８にて再び上記の如く、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０１で選択されたかを判定する。回路に含まれる全てのフリップフリップがステップＳ１０１で選択されてはいなかった場合、ステップＳ１０１に戻る。以降ステップＳ１０１，Ｓ１０２，Ｓ１０３，Ｓ１０４，Ｓ１０５、Ｓ１０７、Ｓ１０８のループを反復実施する。
【００２５】
但し当該反復実施において、ステップＳ１０１では、前回までのステップＳ１０１にて既に選択されたフリップフロップ以外のフリップフロップをその都度選択する。またステップＳ１０３において使用されるエリアは、直前のステップＳ１０７で更新後のエリアである。
【００２６】
また上記反復実施の間、ステップＳ１０３にて、直前のステップＳ１０１で選択されたフリップフロップが直前のステップＳ１０７で更新後の、当該グループのエリア内に位置しない場合（ＮＯ）、ステップＳ１０２に戻る。そこで、上記の如く、当該グループ以外のグループを新たに選択し、当該新たな選択に係るグループにつき、ステップＳ１０３以降の動作を行う。同様にステップＳ１０４にて、当該グループに属するフリップフロップの個数が許容ファンアウトを超過する場合、ステップＳ１０２に戻る。そこで、上記の如く、当該グループ以外のグループを新たに選択し、当該新たな選択に係るグループにつき、ステップＳ１０３以降の動作を行う。またこのようにしてステップＳ１０２にてグループが順次選択された結果、現に存在する全てのグループの各々についてのステップＳ１０３以降の動作が既に終了しており、新たに選択するグループが存在しない場合（ＮＯ）、ステップＳ１０６に移行する。ステップＳ１０６にて、直前のステップＳ１０１で選択されたフリップフリップにつき新たなグループを作成する。そして当該新たなグループにつき、ステップＳ１０７以降の動作を行う。
【００２７】
このようにして、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップの全てが、ステップＳ１０６で設定された何れかのグループに属するようになる。
【００２８】
図４Ａ乃至４Ｇとともに、図３とともに上述した初期グループ化Ｓ１００の動作の具体例を説明する。
【００２９】
図４Ａの例は、上記ネットリスト１およびレイアウトデータ２に含まれるフリップフロップとして、図示の如く、番号１乃至１９を有する計１９個のフリップフロップが含まれる。
【００３０】
図４Ｂでは、番号１のフリップフロップが選択され、当該フリップフロップが属するグループとしてグループ１、Ｇ１が設定されている。またグループ１、Ｇ１に対するエリアとして、エリア１、Ａ１が設定されている。この例の場合、エリアはグループの中心を中心とする一定サイズの正方形として得られる。グループの中心は、グループに属するフリップフロップのｘ、ｙ各座標の最大値および最小値のそれぞれの中心のｘ、ｙ座標の位置である。エリアの決定方法に関し、図５Ａ，５Ｂとともに後述する。
【００３１】
図４Ｃは、番号１乃至８までの計８個のフリップフリップが処理された状態を示す。なおこの例の場合、上記許容ファンアウトとして８が設定されている。また図３のステップＳ１０１におけるフリップフロップの選択は、各フリップフロップの番号順になされるものとする。また図３のＳ１０７でエリア内に位置するか否かを判定する場合、当該エリア内に処理対象のフリップフロップがその一部分でも含まれていれば当該フリップフロップは当該エリアに位置すると判定する。その結果、番号１乃至８迄のフリップフロップの各々は、図３のステップＳ１０３，Ｓ１０４の条件を満たし、ステップＳ１０５でグループ１、Ｇ１に追加される。その結果図４Ｃに示されるように、番号１乃至８のフリップフロップはグループ１、Ｇ１に属することになる。
【００３２】
なおエリア１、Ａ１は、このようにして対応するグループ１、Ｇ１に属するフリップフロップが増加するごとにステップＳ１０７で更新される。図４Ｃの場合、グループ１、Ｇ１には番号１乃至８の計８個のフリップフリップが属するため、同８個のフリップフリップが属するグループ１，Ｇ１の中心を中心とする一定のサイズの正方形としてエリア１、Ａ１が更新される。その結果、図４Ｂに示す、番号１のフリップフロップのみがグループ１、Ｇ１に属する場合のエリア１、Ａ１に対し、図４Ｃの状態では、エリア１、Ａ１が更新され、右方向にずれて設定されている。次にステップＳ１０８にて未だ全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みではないため、ステップＳ１０１に戻る。
【００３３】
ステップＳ１０１にて、次の番号９のフリップフロップが選択される。次にステップＳ１０２にて、上記処理中のグループ１，Ｇ１が選択される。図４Ｄは上記番号９のフリップフロップが処理された状態を示す。ここでは、上記の如く許容ファンアウトは８なので、番号９のフリップフロップの場合、ステップＳ１０４からステップＳ１０２に移行する。ステップＳ１０２にて他のグループが存在するか否かを判定する。この場合当該グループ１、Ｇ１意外にグループは存在しない。このため次にステップＳ１０６に移行し、上記処理中の番号９のフリップフロップにつき新たなグループ２，Ｇ２を作成する。次にエリア２（図４Ｄでは省略）が設定される（ステップＳ１０７）。
【００３４】
図４Ｅは、引き続き番号１０乃至１５のフリップフロップが順次処理された後の状態を示す。この状態では、グループ２、Ｇ２には番号９乃至１５の計７個のフリップフロップが属し、同７個のフリップフロップが属するグループ２，Ｇ２の中心を中心とする一定サイズの正方形としてエリア２、Ａ２が設定されている。また上記７個は許容ファンアウト８以内である。
【００３５】
図４Ｆは、引き続き番号１６のフリップフロップが処理された後の状態を示す。番号１６のフリップフロップは上記グループ２、Ｇ２のエリア２、Ａ２内に位置しないため、ステップＳ１０３からステップＳ１０２に移行する、ステップＳ１０２では、他のグループとして、グループ１，Ｇ１が選択される。しかしながら当該番号１６のフリップフロップは上記グループ１，Ｇ１のエリアＡ１に含まれない。そこでステップＳ１０３からステップＳ１０２に移行する。ステップＳ１０２にて、他には未処理のグループは存在しないため、ステップＳ１０６に移行する。ステップＳ１０６にて、当該番号１６のフリップフロップにつき新たなグループ３、Ｇ３が設定され、エリア３、Ａ３が設定されている（ステップＳ１０７）。次にステップＳ１０８にて、未だ全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みではないため、ステップＳ１０１に戻る。
【００３６】
図４Ｇは、引き続き番号１７乃至１９のフリップフロップが順次処理された後の状態を示す。この状態では、グループ３、Ｇ３には番号１６乃至１９の計４個のフリップフロップが属し、同４個のフリップフロップが属するグループ３，Ｇ３の中心を中心とする一定サイズの正方形としてエリア３、Ａ３が設定されている。また上記４個は許容ファンアウト８以内である。この状態では、ステップＳ１０８にて、回路に含まれる全てのフリップフロップ、すなわち番号１乃至１９の計１９個のフリップフロップが処理済みであるため、図２の初期グループ化Ｓ１００が終了する。
【００３７】
次に図５Ａ，５Ｂとともに、グループのエリアの決め方について説明する。
【００３８】
図５Ａに示す如く、クロックバッファＢが許容ファンアウト８のフリップフロップＦＦ（以下単にフリップフロップと称する）にクロック信号を供給する場合を想定する。そしてフリップフロップが最も密に配置された領域より大きくなるように、当該グループの中心からのノルムを決定する。この場合、当該決定されたノルムの範囲としてエリアの最小サイズを得る。
【００３９】
更にまた図５Ｂに示される如く、上記同様、クロックバッファＢが許容ファンアウト８のフリップフロップにクロック信号を供給する場合を想定する。そしてこの場合、距離が長くなりすぎる(クロックスキューが大きくなる)領域より小さくなるようにノルムを決定する。そして当該決定されたノルムの範囲としてエリアの最大サイズを得る。エリアのサイズとして、上記最小サイズと最大サイズとの間の何れかのサイズを選ぶことができる。
【００４０】
また上記の如く、グループに属するフリップフロップが変動してグループが変化すると、当該グループの中心の座標が変化する。そのため、グループが変化するたびにエリアを再計算して更新する。
【００４１】
以下に実施例に適用可能な様々なノルムの例を示す。
・グループのエリアの領域を規程するもののうちの一のものとしてのユークリッドノルムを以下に示す。
【００４２】
【数１】
ここでｘ１＝ｘ、ｘ２＝ｙとした場合、このノルムの範囲はユークリッド距離が一定の値の範囲となり、したがって円形の範囲となる。
・グループのエリアの領域を規程するもののうちの他の一のものとしての最大値ノルムを以下に示す。
【００４３】
【数２】
ここでｘ１＝ｘ、ｘ２＝ｙとした場合、このノルムの範囲はｘ、ｙの各々の値の最大値が一定の値の範囲となり、したがって正方形の範囲となる。
・グループのエリアの領域を規程するもののうちの更に他の一のものとしてのp次平均ノルムを以下に示す。
【００４４】
【数３】
ここでｘ１＝ｘ、ｘ２＝ｙとし、更にｐが１の場合、このノルムの範囲はｘ、ｙの合計が一定の値の範囲となり、したがって菱形の範囲となる。
【００４５】
上記図４Ａ乃至４Ｇの例の場合および以下に述べる例の場合、上記の如く、ｘ、ｙ座標の各々においてグループに属する全てのフリップフロップの最大座標および最小座標の中間の座標の位置をグループの中心とする。そして当該グループの中心からのノルムを上記図５Ａ、５Ｂとともに述べた条件で決定する。そしてこのようにして決定されたノルムの範囲としてエリアを得る。図４Ａ乃至４Ｇの例の場合および以下に述べる例の場合、上記最大値ノルムが使用され、上記グループの中心を中心とする正方形のエリアが決定される。
【００４６】
次に上記最適化１（交換）および最適化２（移動）について詳細に説明する。
【００４７】
図６Ａ，６Ｂは上記した初期グループ化Ｓ１００によって得られたグループの例を示す。
【００４８】
図６Ａに示す如く、この例の場合、計２０個のフリップフロップが３個のグループ、グループ１乃至３、Ｇ１、Ｇ２，Ｇ３にグループ化されている。また図６Ａには、これらグループ１乃至３、Ｇ１、Ｇ２，Ｇ３のそれぞれのエリア１乃至３、Ａ１，Ａ２，Ａ３が示されている。この例の場合、図６Ｂに示されるように、グループ１、Ｇ１には８個のフリップフロップが属し、グループ２、Ｇ２には８個のフリップフリップが属し、グループ３、Ｇ３には４個のフリップフロップが属する。この例の場合も許容ファンアウトは８とされている。また図６Ａに示される如く、上記エリア１乃至３、Ａ１，Ａ２，Ａ３は相互の重複している。図６Ａ，６Ｂ中、Ｃ１乃至Ｃ３は、それぞれグループ１乃至３、Ｇ１，Ｇ２，Ｇ３の中心を示している。したがって図６Ａ，６Ｂに示されるグループの場合、グループ１、Ｇ１に属する８個のフリップフリップにつき、その中心Ｃ１にクロックバッファが配置される。したがってグループ１、Ｇ１に属する８個のフリップフリップの各々に対し、その中心Ｃ１に配置されるクロックバッファによりクロック信号が供給されることになる。その際のクロックラインＬ１，Ｌ２，Ｌ３は図６Ａ，６Ｂに示される如く、配線長がいわゆるマンハッタン距離となるように接続される。なおクロックラインの接続の方法は上記マンハッタン距離となるような接続する場合に限られず、半導体集積回路に対し適用するテクノロジーに応じ適宜変更され得る。
【００４９】
次にこのようなグループに対し、最適化１（交換）を行う場合の例につき、図７Ａ乃至７Ｄともに詳細に説明する。
【００５０】
図７Ａは上記図６Ｂと同様のグループ化の状態を示す。ここで最適化１（交換）Ｓ２００として、図７Ａ中、グループ１、Ｇ１に属する８個のフリップフロップのうち、右上の２個のフリップフロップＡをグループ２、Ｇ２に移す。また同時に、上記２個のフリップフロップＡと交換に、グループ２、Ｇ２に属する８個のフリップフリップのうち、左下の２このフリップフロップＢをグループ１、Ｇ１に移す。その結果、図７Ｂに示す如くのグループに変化する。
【００５１】
以下に図７Ａの状態と図７Ｂの状態とを、クロックバッファと各フリップフロップとの間のクロックラインの長さについて比較する。ここで図７Ｂの場合、図７Ａの状態に対しグループが変化しているため、図７Ｂに示される変化後のグループの中心Ｃ１，Ｃ２，Ｃ３の位置は、変化前と異なっている。そして図７Ｂの場合、上記変化後のグループの中心Ｃ１，Ｃ２、Ｃ３にクロックバッファが配置され、当該クロックバッファから対応するグループに属する各フリップフロップに対しクロックラインが接続される。その場合のクロックラインＬ１，Ｌ２，Ｌ３が図７Ｂに示されている。図７ＡのクロックラインＬ１，Ｌ２，Ｌ３と比較すると、明らかに図７Ｂの方がクロックラインの総長が短縮されていることが分かる。
【００５２】
図７Ｃは上記最適化１（交換）Ｓ２００における動作の流れを説明するための図である。
【００５３】
図７Ｃ中、ステップＳ２０１にて、上記初期グループ化Ｓ１００の手順で生成されたグループから、２個のグループの組み合わせを抽出する。あるいは後述する最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の反復の際、前回の最適化３（結合）の結果得られたグループから２個のグループを抽出する。ステップＳ２０２にて、当該抽出に係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ２０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ２０２を実行する。
【００５４】
他方、ステップＳ２０２にて、当該抽出に係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ２０３にて、当該２個のグループ間で、それぞれのグループに属するフリップフロップ同士の交換を試みる。そして当該フリップフリップ同士の交換後の状態につき、各グループにおいて、当該グループの中心と、同グループに属するフリップフロップとの間のマンハッタン距離の合計を計算する。ここで得られるグループごとのマンハッタン距離の合計は、各グループのコスト（あるいは評価指標値）の一例として使用される。なお後述するように、当該コストは上記マンハッタン距離によるものの例に限られない。更に各グループのコストを全てのグループについて合計する。当該全てのグループについて求めた合計を全体のコストと称する。なおコストを求める方法につき後述する。
【００５５】
ステップＳ２０３では、上記交換の前後で全体のコストを比較し、当該交換の結果全体のコストが減少する場合、当該交換後のグループを維持する。ここでこのようにグループ間でフリップフロップ同士を交換すると、各グループに属するフリップフロップのうち当該交換に係るフリップフロップは交換以前のフリップフロップとは異なるものとなる。このようにグループに属するフリップフロップのうちの少なくともその一部のフリップフロップがそれ以前のものとは異なるものとなることを、「グループが変化する」と称する。同様に、グループに属するフリップフロップのうちの少なくともその一部のフリップフロップが他のグループに移動することにより減少する場合も「グループが変化する」と称する。同様に他のグループからフリップフロップが移動してくることにより当該グループに属するフリップフロップが増加する場合も「グループが変化する」と称する。このようにグループが変化した後の当該グループのコストを求める場合、予め当該グループの中心を、当該変化後のグループの中心に更新した上でコストを求める。
【００５６】
図７Ｃの説明に戻り、ステップＳ２０３にて、当該交換の結果全体のコストが減少しない場合、当該交換前のグループを維持する。このような動作を、それぞれが異なるグループに属する全てのフリップフロップ同士の組み合わせにつき一組ずつ順次反復して行う。そしてその都度、全体のコストが減少する場合には該当する交換後のグループを維持し、減少しない場合には交換前のグループを維持する。
【００５７】
このようにして上記２個のグループについてステップＳ２０３が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ２０４）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ２０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ２０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ２０４のＹＥＳ）、最適化１（交換）を終了する。
【００５８】
このようにしてステップＳ２０１にて全てのグループの組み合わせが順次抽出され、それぞれの組み合わせに対し順次ステップＳ２０２，Ｓ２０３が実行される。
【００５９】
図７Ｄは図７Ａの例に対し上記最適化１（交換）Ｓ２００を行う場合の、グループ１，２、Ｇ１，Ｇ２間でフリップフロップの交換を試みる方法について説明するための図である。上記の如く図７Ａの例の場合、グループ１，２の各々には許容ファンアウトである８個のフリップフリップが属する。したがって交換を試みるフリップフリップの組み合わせの数は、８×８＝６４であり、６４通りである。これら６４通りの各々につき、順次上記交換を試み、各グループの中心を更新した上で交換前後で全体のコストを比較する。その結果全体のコストが減少すれば当該交換後のグループを維持し、減少しなければ交換前のグループを維持する。このような動作を６４回反復する。実際に当該６４通りの反復を行った結果は以下の通りである。
【００６０】
すなわち、上記の如くグループ１，２、Ｇ１，Ｇ２間でフリップフロップＡ，Ｂの交換を行った場合全体のコストが減少する。他方、グループ１，３、Ｇ１，Ｇ３間およびグループ２，３、Ｇ２，Ｇ３間でフリップフロップの交換を行っても全体のコストは減少しない。その結果、このように図７Ａの例において上記図７Ｃとともに上述の最適化１（交換）Ｓ２００を行った結果、図７Ｂに示す如く、グループ１，２、Ｇ１，Ｇ２間でフリップフロップＡ，Ｂの交換のみが行われた状態のグループが得られる。
【００６１】
次に図８Ａ〜８Ｄとともに、最適化２（移動）Ｓ３００につき詳細な説明を行う。
【００６２】
図８Ａは図７Ｂの状態、すなわち上記７Ａのグループに対し上記最適化１（交換）が実行された状態を示す。ここで図８Ａの状態でグループ１、２，３、Ｇ１，Ｇ２，Ｇ３は、相互にそのエリアが重なり合っているものとする。この例の場合、例えば図８Ｂに示す如く、グループ２、Ｇ２に属する２つのフリップフロップＤのうちの何れか一個をグループ３、Ｇ３に移動した場合、全体のコストが最も減少する。すなわち、図８Ａのグループにおいて考え得るグループ間のフリップフロップの移動の全ての場合を試み、各場合についてグループの中心を更新した上で全体のコストの変化量を記憶装置に記憶しておく。このようにして記憶された、移動を試みた各場合の全体のコストの変化量のうち、最も減少量の大きい場合を得る。そして当該最も減少量の多い場合の移動のみを実際に行う。図８Ａ，８Ｂの場合、上記２このフリップフロップＤのうちの１個のフリップフリップの移動が上記最も減少量の多い場合に該当する。ここで図２とともに上記したように、最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００および最適化３（結合）は、終了判定Ｓ５００の結果が「一連の手順を反復する」であった場合、再度反復される。図８Ａ，８Ｂの場合、このように最適化２（移動）Ｓ３００が反復された場合を想定している。当該反復に係る最適化２（移動）Ｓ３００において、上記２このフリップフロップＤのうちの他の１個のフリップフリップの移動が上記最も減少量の多い場合に該当する。その結果、当該反復による２回の最適化２（移動）の各々の回において、上記２このフリップフロップＤの各々が、上記最も減少量の多い場合に該当し、当該移動が実際に行われる。
【００６３】
他方、図８Ｂに示す如く、グループ２、Ｇ２からグループ１、Ｇ１へのフリップフリップの移動を想定した場合、グループ１、Ｇ１に属するフリップフリップの個数は８個であり、既に許容ファンアウトに至っている。上記の如くグループ２、Ｇ２からグループ１、Ｇ１へのフリップフリップの移動を行った場合、グループ１、Ｇ１に属するフリップフロップの総数が９となってしまい、許容ファンアウト８を超えてしまう。したがってこのような移動は実際には行われない。
【００６４】
図８Ｃは上記の如くグループ２，３、Ｇ２，Ｇ３間で、最適化２（移動）Ｓ３００を試みる方法について説明するための図である。図８Ａの場合、グループ２、Ｇ２には計８個のフリップフリップが属し、グループ３、Ｇ３には計４個のフリップフロップが属する。この場合、グループ２に属する８個のフリップフロップの各々につき、グループ３への移動を試み、その都度各グループの中心を更新したうえで全体のコストを得、全体のコストの変化量を記憶装置に記憶しておく。他方、グループ３に属するフリップフリップをグループ２に移動することを想定すると、その場合、グループ２に属するフリップフリップの総数が９となり許容ファンアウト８を超える。したがってグループ３からグループ２への移動は実際には行われない。このようにして記憶された、各移動の場合の全体のコストの変化量を相互比較し、減少量が最も大きい場合の移動のみを実際に行い、それ以外の移動は実際には行わない。
【００６５】
図８Ｄは上記最適化２（移動）Ｓ３００における動作の流れを説明するための図である。
【００６６】
図８Ｄ中、ステップＳ３０１にて、前記最適化１（交換）の結果得られたグループから２個のグループの組み合わせを抽出する。ステップＳ３０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ３０１に戻り、他の２個のグループの組み合わせの抽出を新たに行い、当該新たな抽出に係るグループにつき、ステップＳ３０２を実行する。
【００６７】
他方、ステップＳ３０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ３０３にて、当該２個のグループ間で、それぞれのグループに属するフリップフロップの移動を試みる。そして当該フリップフリップの移動後の状態につき、各グループの中心を更新した上で全体のコストを求める。そして上記移動の前後で全体のコストを比較し、その都度コストの変化量を記憶装置に記憶しておく。このような動作を上記２個のグループの間で考え得る全てのフリップフロップの移動の場合について試み、それぞれの場合における全体のコストの変化量を記憶装置に記憶する。ここで上記の如く、少なくとも一方のグループに属するフリップフリップの総数が既に許容ファンアウト８に達している場合、当該グループに対するフリップフロップの移動は行わない。そしてステップＳ３０４にて、このようにして記憶された各移動の場合の全体のコストの変化量を相互に比較し、最も減少量の大きい場合の移動のみを実際に行い、他の場合の移動は行わない。
【００６８】
このようにして上記２個のグループについてステップＳ３０４が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ３０５）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ３０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ３０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ３０５のＹＥＳ）、最適化２（移動）を終了する。
【００６９】
このようにしてステップＳ３０１にて全てのグループの組み合わせが順次抽出され、ステップＳ３０２の条件を満たす全てのグループの組み合わせに対し順次ステップＳ３０３，Ｓ３０４が実行される。
【００７０】
図８Ａのグループに対し、上記図８Ｄとともに上述した最適化２（移動）Ｓ３００が実施された結果、上記の如く、グループ２、Ｇ２に属する２個のフリップフロップＤのうちの一個がグループ３、Ｇ３に移動される。そして最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００が反復され、当該反復に係る最適化２（移動）にて、今度はグループ２、Ｇ２に属する２個のフリップフロップＤのうちの他の一個がグループ３、Ｇ３に移動される。その結果図８Ｂに示される状態、すなわち結果的にグループ２、Ｇ２に属する２個のフリップフロップＤがグループ３、Ｇ３に移動される。なおこの場合、前記最適化３（結合）においては後述する結合を実行する条件が満たされず、実際には結合が行われなかったものとする。また前記反復に係る最適化１（交換）においても、交換により全体のコストが減少する場合が存在せず、実際には交換が行われなかったものとする。したがって最初の最適化２（移動）Ｓ３００と前記反復に係る２度目の最適化２（移動）Ｓ３００との間で実行される前記最適化３（結合）Ｓ４００および前記反復に係る最適化１（交換）Ｓ２００においては何らグループが変化しなかった場合を想定している。
【００７１】
図９は図８Ｂと同じ状態を示しており、上記最適化１（交換）Ｓ２００、最適化２（移動）Ｓ３００の効果について説明するための図である。
【００７２】
図９の状態を最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前の状態、すなわち図７Ａのグループの状態と比較する。図７Ａのグループの状態において図７Ａ中、例えばグループ１、Ｇ１を着目する。この場合、グループ１、Ｇ１には２個のフリップフロップＡが属しており、これらを含む計８個のフリップフリップは図７Ａ中、横方向に比較的広く分散している。この状態では図７Ａに示す如く、当該グループ１の中心Ｃ１にクロックバッファを設け、当該クロックバッファから当該８個のフリップフロップに対し配線長がマンハッタン距離をなすようにクロックラインＬ１を接続することになる。他方、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行後の状態、すなわち図９では同図中、グループ１、Ｇ１には２個のフリップフロップＡの代わりに、元はグループ２、Ｇ２に属していたフリップフロップＢが属している。その結果、これらを含む計８個のフリップフリップは図９、横方向において、比較的集中している。この状態では図９に示す如く、当該グループ１の中心Ｃ１にクロックバッファを設け、当該クロックバッファから当該８個のフリップフロップに対し配線長がマンハッタン距離をなすようにクロックラインＬ１を接続することになる。図７ＡにおけるクロックラインＬ１と図９におけるクロックラインＬ１とを比較すると、図９のクロックラインＬ１の総長の方が明らかに短縮されていることが分かる。同様な点はグループ２、Ｇ２のくロックラインＬ２についても言える。
【００７３】
次にグループ２，３、Ｇ２，Ｇ３につき、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前後の状態、すなわち図７Ａと図９の状態を相互に比較する。最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行前にグループ２、Ｇ２に属していた２個のフリップフロップＤが、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行後にはグループ３、Ｇ３に属している。その結果グループ３についてのみ着目すると、グループ３に属するフリップフロップの総数が４から６に増加した分、クロックラインＬ３の総長は増加している。しかしながら同時にグループ２、Ｇ２について着目すると、上記の如くフリップフロップＢがフリップフロップＡと交換されたことに加え、フリップフロップＤがグループ３、Ｇ３に移動されている。その結果、図９の状態では、グループ２、Ｇ２に属する計６個のフリップフロップは、図９の横方向において比較して集中しており、その結果クロックラインＬ２は図７Ａの状態に比して大幅に短縮されている。その結果、全グループ１，２，３、Ｇ１，Ｇ２，Ｇ３を通じ、各グループのクロックラインＬ１，Ｌ２，Ｌ３の総長の合計は、図７Ａの状態に比し、図９の状態の方が明らかに短縮されている。
【００７４】
上記の如く、最適化１（交換）Ｓ２００の場合、図７ＣのステップＳ２０３にて、全体のコストが下がる場合にのみ実際にグループ間のフリップフロップの交換を行う。また、最適化２（移動）Ｓ３００の場合、図８ＤのステップＳ３０４にて全体のコストが最も下がる場合にのみ、グループ間の移動を行う。その結果図７Ａ，図９とともに上述の如く、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００の実行により、全てのグループを通じ、クロックラインの総長の合計を短縮できる。
【００７５】
更に各グループのファンアウトに着目した場合、図７Ａの場合にはグループ１，２，３、Ｇ１，Ｇ２，Ｇ３のそれぞれのファンアウトが８，８，４である。これに対し、図９の場合にはグループ１，２，３、Ｇ１，Ｇ２，Ｇ３のファンアウトはそれぞれ８，６，６となっている。図７Ａの場合最大ファンアウト８と最小ファンアウト４との差が４であるのに対し、図９の場合は最大ファンアウト８と最小ファンアウト６との差が２である。よってファンアウトのバラツキが低減されている。
【００７６】
図１０Ａ乃至１０Ｃとともに上記最適化３（結合）Ｓ４００につき詳細に説明する。
【００７７】
図１０Ａは、上記最適化２（移動）Ｓ３００の結果得られたグループの例を示す。同図の例では回路には計２０個のフリップフロップが含まれ、グループ１、Ｇ１には４個のフリップフロップが属し、グループ２、Ｇ２にも４個のフリップフロップが属する。またグループ３、Ｇ３には８個のフリップフリップが属し、グループ４、Ｇ４には４個のフリップフロップが属する。更に図１０Ａの場合、グループ１，２の間で、各々のグループに属するフリップフロップが、他のグループのエリア内に位置するものとする。すなわちグループ１に属する４個のフリップフロップは、グループ２のエリア内に位置するものとする。同様にグループ２に属する４個のフリップフロップは、グループ１のエリア内に位置するものとする。このような関係はグループ３，４との間でも成立するものとする。すなわち、グループ３に属する８個のフリップフロップは、グループ４のエリア内に位置するものとする。同様にグループ４に属する４個のフリップフロップは、グループ３のエリア内に位置するものとする。
【００７８】
このように２個のグループが以下の関係を有する際、当該関係を「互いのフリップフリップが互いのエリアに含まれる関係」と称する。すなわち一のグループに属する全てのフリップフロップが他の一のグループのエリア内に位置し、前記他の一のグループに属する全てのフリップフロップが前記一のグループのエリア内に位置する関係である。
【００７９】
ここで最適化３（結合）Ｓ４００では、互いのフリップフリップが互いのエリアに含まれる関係を有するグループ１，２、Ｇ１，Ｇ２の間、およびグループ３，４、Ｇ３，Ｇ４の間の各々につき、以下の動作を行う。すなわち２個のグループのファンアウトを合計した場合に許容ファンアウト以内である場合、当該２個のグループを結合して１個のグループとなるようにグループの変更を行う。上記の如く、フリップフロップにクロック信号を供給する際、各グループに一のクロックバッファを設ける。上記の如くグループ同士の結合を行うことにより、回路に含まれるフリップフロップが属するグループの総数が減少する。その結果回路全体を通じ、使用するクロックバッファの数が減少する。その結果消費電力を低減させることができる。
【００８０】
図１０Ａの例の場合、まずグループ１，２、Ｇ１，Ｇ２の間では、上記の如く、各グループに属するフリップフロップの数は４であり、すなわちファンアウトが４である。したがってグループ１，２のファンアウトを合計すると８となり、許容ファンアウト８以内に収まっている。したがって図１０Ｂに示される如く、グループ１，２を結合する。他方グループ３，４の間では、上記の如く、各グループに属するフリップフロップの数はそれぞれ８、４であり、すなわちファンアウトがそれぞれ８，４である。したがってグループ３，４のファンアウトを合計すると１２となり、許容ファンアウト８を超える。したがって図１０Ｂに示される如く、グループ３，４を結合することはしない。
【００８１】
図１０Ｃは最適化３（結合）Ｓ４００の動作の流れを説明するための図である。
【００８２】
図１０Ｃ中、ステップＳ４０１にて、前記最適化２（移動）Ｓ３００の結果得られたグループから２個のグループの組み合わせを抽出する。ステップＳ４０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合うか否かを判定する。重なり合わない場合、ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。
【００８３】
他方、ステップＳ４０２にて、当該組み合わせに係る２個のグループの、それぞれのエリアが重なり合う場合、ステップＳ４０３にて、当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有するか否かを判定する。当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有さない場合、ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。当該２個のグループが互いのフリップフリップが互いのエリアに含まれる関係を有する場合、ステップＳ４０４を実行する。
【００８４】
ステップＳ４０４では、当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まるか否かを判定する。当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まらない場合ステップＳ４０１に戻り、他の２個のグループの組み合わせの新たな抽出を行い当該新たな抽出に係る２個のグループにつきステップＳ４０２以降を実行する。当該２個のグループのそれぞれのファンアウトの合計が許容ファンアウト以内に収まる場合、ステップＳ４０５を実行する。ステップＳ４０５では、当該２個のグループを結合し、１個のグループとする。このようにして上記２個のグループについてステップＳ４０５が終了した後、全てのグループの組み合わせの抽出が済んだか否かを判定する（ステップＳ４０６）。全てのグループの組み合わせの抽出が済んでいなかった場合（ＮＯ）、ステップＳ４０１に戻り、更に他の組み合わせに係る２個のグループの新たな抽出を行い、当該新たな抽出に係る２個のグループにつきステップＳ４０２を実行する。全てのグループの組み合わせの抽出が済んだ場合（ステップＳ４０６のＹＥＳ）、最適化３（結合）を終了する。
【００８５】
このようにしてステップＳ４０１にて全てのグループの組み合わせが順次抽出され、各々の組み合わせに係る２個のグループに対し、上記同様、ステップＳ４０２以降の動作を実行する。
【００８６】
次に図１１とともに、図２に示す終了判定Ｓ５００につき説明を行う。
【００８７】
終了判定Ｓ５００では、以下の条件１あるいは条件２を満たす場合に収束したと判断し、一連の手順を終了する。すなわち最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行を終了し、図２の処理を終了する。
【００８８】
条件１：
以下の全ての条件１）、２）、３）が満たされる：
１）最適化１（交換）Ｓ２００の前後で全体のコストが一定であり減少しない。
【００８９】
２）最適化２（移動）Ｓ３００の前後で全体のコストが一定であり減少しない。
【００９０】
３）最適化３（結合）Ｓ４００の前後で全体のコストが一定であり減少しない。
【００９１】
条件２：
最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の回数ｎが所定回数に至った。
【００９２】
図１２Ａ、１２Ｂ，１２Ｃ、１２Ｄとともに、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の例につき説明する。
【００９３】
図１２Ａは初期グループ化Ｓ１００によってグループ１，２，３、Ｇ１，Ｇ２，Ｇ３が得られた状態を示す。図１２Ａに示す如く、グループ１、Ｇ１には８個のフリップフロップが属し、グループ２、Ｇ２には８個のフリップフリップが属し、グループ３、Ｇ３には６個のフリップフロップが属する。
【００９４】
最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の各々では、グループ１と２、Ｇ１，Ｇ２，グループ１と３、Ｇ１，Ｇ３、グループ２と３、Ｇ２，Ｇ３の順番で処理を行うものとする。
【００９５】
図１２Ａの状態ではグループ１と２では、相互のエリア１と２、Ａ１，Ａ２が重なっていない。したがって最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００のいずれにおいても処理対象とならない（図７Ｃ中、ステップＳ２０２のＮＯ、図８Ｄ中、ステップＳ３０２のＮＯ、図１０Ｃ中、ステップＳ４０２のＮＯ）。他方グループ２と３では、相互のエリア２と３、Ａ２，Ａ３が重なっている。したがって最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００のいずれにおいても処理対象となる（図７Ｃ中、ステップＳ２０２のＹＥＳ、図８Ｄ中、ステップＳ３０２のＹＥＳ、図１０Ｃ中、ステップＳ４０２のＹＥＳ）。この例の場合、図１２Ｂに示される如く、最適化２（移動）Ｓ３００の反復により、グループ２から２個のフリップフリップＥがグループ３に移動されたものと想定する。
【００９６】
上記グループ２、Ｇ２からグループ３、Ｇ３への２個のフリップフロップＥの移動の結果、図１２Ｃに示す如く、グループ２，３の各々に属するフリップフロップが変化する。その結果図１２Ｃに示す如く、各グループ２，３の中心Ｃ２，Ｃ３が変化する。例えばグループ２、Ｇ２の場合上記の如く、右端部に有ったフリップフリップＥがグループ３、Ｇ３へ移動している。その結果グループ２には６個のフリップフロップが残る。当該残った６個のフリップフロップの中心は、前記移動前の８個のフリップフロップの場合の中心に対し、左側に移動している。したがってグループ２の中心Ｃ２はこれに対応して左側に移動する。ここでグループ２のエリア２、Ａ２は上記の如く、当該グループの中心Ｃ２を中心とする一定サイズの正方形である。上記の如くグループ２の中心Ｃ２の左側の移動により、エリア２、Ａ２もこれに対応して左側に移動する（図１２Ｃ参照）。
【００９７】
その結果図１２Ｃに示す如く、グループ１と２との間で、相互にエリア１と２、Ａ１，Ａ２とが重なる。この状態で最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００を実行した場合、上記図１２Ａの場合と異なり、グループ１と２との間が処理対象となる（図７Ｃ中、ステップＳ２０２のＹＥＳ、図８Ｄ中、ステップＳ３０２のＹＥＳ、図１０Ｃ中、ステップＳ４０２のＹＥＳ）。その結果図１２Ｄに示す如く、例えば最適化２（移動）Ｓ３００において、グループ１、Ｇ１のフリップフロップＦがグループ２、Ｇ２に移動される。
【００９８】
このように実施例のクロック信号供給回路の設計方法によれば、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行においてグループが変化すると、それに対応してそのエリアが変化する。エリアが変化すると、当初重なっていなかったグループ相互でエリアが重なり合う場合がある。そのような場合、当初はエリアの重なりが無くグループ相互間が最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の処理対象外であったものが、新たに処理対象となる。その結果最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の処理対象範囲が広がり、より効果的な最適化が期待できる。
【００９９】
図１３とともに、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の反復の追加的な条件について述べる。
【０１００】
すなわち、前回の最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００の実行において、ある組み合わせに係るグループ間ではフリップフロップの交換も移動も実際には行われず、当該グループが変化しなかった場合を想定する。そのような場合、当該グループ間ではそれ以降、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００，最適化３（結合）Ｓ４００を行わないものとすることができる。そのようにすることによって、該当する組み合わせに係るグループは処理対象外となる．その結果以後該当する組み合わせに係るグループについての処理が実行されないため、処理量が削減できる。
【０１０１】
図１４とともに、上記終了判定Ｓ５００にて「一連の手順を終了する」旨の判定がなされた以後の動作につき説明する。
【０１０２】
各グループ１，２，３、Ｇ１，Ｇ２，Ｇ３のそれぞれの中心Ｃ１，Ｃ２，Ｃ３にクロックバッファＢ１，Ｂ２，Ｂ３を挿入する。次にクロックバッファＢ１，Ｂ２、Ｂ３から、それぞれのグループ１，２，３のフリップフロップに対し、クロックラインＬ１，Ｌ２，Ｌ３を接続する。そしてクロックバッファＢ１，Ｂ２，Ｂ３から、最も近いＨ型ツリーの末端ＢにクロックラインＬ０を接続する。その結果Ｈ型ツリーの末端Ｂに、各クロックバッファＢ１，Ｂ２，Ｂ３を介し、各グループ１，２，３に属するフリップフロップがクロックラインＬ０，Ｌ１，Ｌ２，Ｌ３により接続される。
【０１０３】
以下に上記コストを求める方法につき、数式を使用した説明を行う。
【０１０４】
グループの中心の座標は以下の数式で得られる。
【０１０５】
Xg = ( Xfmax + Xfmin ) / 2
Yg = ( Yfmax + Yfmin ) / 2
ここでＸｆｍａｘ，Ｘｆｍｉｎは、それぞれグループ内のフリップフロップの最大ｘ座標、最小ｘ座標をそれぞれ示す。同様にＹｆｍａｘ，Ｙｆｍｉｎは、それぞれグループ内のフリップフロップの最大ｙ座標、最小ｙ座標をそれぞれ示す。
【０１０６】
各グループのコストは以下の数式で得られる。
【０１０７】
Cg = Σ( | Xf - Xg | + | Yf - Yg | )
ここでグループのコストは上記の如く、グループの中心からフリップフリップまでのマンハッタン距離の総和である。マンハッタン距離はクロックラインの配線長に対応するため、グループのコストは当該グループに属するフリップフロップに係るクロックラインの総配線長に対応する。
【０１０８】
全体のコストは以下の数式で得られる。
【０１０９】
C = ΣCg
上記最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００におけるコストの変化量は以下の数式で得られる。
【０１１０】
ΔC = { Cia + Cja } − { Cib + Cjb }
= { Σ( | Xf - Xia | + | Yf - Yia | ) + Σ( | Xf - Xja | + | Yf - Yja | ) } -
{ Σ( | Xf - Xib | + | Yf - Yib | ) + Σ( | Xf - Xjb | + | Yf - Yjb | ) }
ここで
C:コスト
f: フリップフリップの識別番号
Ｃｇにおけるg:グループの識別番号
Xf:フリップフリップのｘ座標
Yf:フリップフリップのｙ座標
Xg:グループの中心のｘ座標
Yg:グループの中心のｙ座標
またi, jは交換・移動の対象となるグループの組み合わせにおける各グループの識別番号を示し、aは交換・移動後、bは交換・移動前であることを示す。
【０１１１】
上記各グループのコストＣｇ（すなわち評価指標値）としては上記の例、すなわち
マンハッタン距離：Cg = Σ( | Xf - Xg | + | Yf - Yg | )
によるものに限られず、例えば以下に示すユークリッド距離、総配線長、容量および遅延等のうちのいずれか一のものによるものとすることができる。
【０１１２】
１．ユークリッド距離：Cg = Σ{ ( Xf - Xg ) + ( Yf - Yg ) }
２．総配線長：Cg = クロックバッファから各フリップフロップまでの総配線長
３．容量(負荷)：Cg = クロックバッファのゲート容量+ 配線容量+ 各フリップフロップのクロック入力ピン容量
４．遅延：Cg = クロックバッファから各フリップフロップのクロック入力ピンまでの遅延の合計
以下に図１とともに、実施例のクロック信号供給回路の設計方法をプログラムで実現する際の処理の概要を述べる。
【０１１３】
図１に示される如くネットリスト(周知のVerilog, VHDL等)１が記憶装置からＣＰＵに読み込まれ、ＣＰＵは当該ネットリスト１からフリップフロップのインスタンスを抽出する（図１中、データリード４）。またＣＰＵは抽出されたフリップフロップをグループ化する（図１中、フリップフロップのグループ化５）。またＣＰＵはグループ化で得られたグループに対し、ネットリスト上で、図１４とともに上述の如くクロックバッファを挿入し、クロックラインを接続する。そしてＣＰＵは、このようにクロックバッファが挿入され、クロックラインが接続された状態のネットリスト７を記憶装置に書き込む（図１中、データライト６）。
【０１１４】
同様に図１に示される如く、レイアウトデータ(DEF or PKIT等)２が記憶装置からＣＰＵに読み込まれ、ＣＰＵは当該レイアウトデータ２から上記フリップフロップのインスタンスの座標を抽出する（図１中、データリード４）。そしてＣＰＵは抽出された座標に基づいて上記グループ化を行う（図１中、フリップフロップのグループ化５）。またＣＰＵはグループ化で得られたグループに対し、レイアウトデータ上で、図１４とともに上述の如くクロックバッファを配置し、クロックラインを配置する。そしてＣＰＵはこのようにクロックバッファが配置され、クロックラインが配置された状態のレイアウトデータ８を記憶装置に書き込む（図１中、データライト６）。
【０１１５】
また設計者はコンピュータに対し、コマンドラインの形態で各種のパラメータ３を入力する。当該各種のパラメータは図１とともに上記の如く、エリアの定義（すなわちエリアの決定方法）、許容ファンアウト、図２に示す最適化１〜３（Ｓ２００〜Ｓ４００）の反復回数ｎ等を含む。上記エリアの決定方法とは、例えば上記の如く、最大値ノルムを使用して一定サイズの正方形のエリアを得る方法である。
【０１１６】
また上記ＣＰＵは、グループ化５の結果得られるグループを示すデータファイル９を記憶装置に書き込む。このデータファイル９には各グループに属するフリップフロップを示す情報が含まれ、例えば周知のＣＳＶ（Ｃｏｍｍａ Ｓｅｐａｒａｔｅｄ Ｖａｌｕｅ ｆｏｒｍａｔ）形式のファイルとされる。
【０１１７】
実施例のクロック信号供給回路の設計方法によれば、以下の効果が得られる。
【０１１８】
１）クロックバッファからのクロックラインの配線長を短縮し、そのバラツキを低減することが可能である。
【０１１９】
２）クロックバッファごとのファンアウトのバラツキを低減可能である。
【０１２０】
３）クロックバッファの個数を削減可能である。
【０１２１】
４）半導体集積回路において、局所的ではなく、全体的にクロックスキューを改善し得る。
【０１２２】
５）プログラム言語で記述することができる。また、現実的な計算量、現実的な記憶領域でグループ化を実施することができる。これはエリアが重なり合うグループ間のみが最適化の処理対象となるため、処理量は処理対象のフリップフロップの個数に対し線形に増加するにすぎない。またコストが減少する場合にグループの変更を実施するため、コストは単調に減少する。
【０１２３】
このように実施例のクロック信号供給回路の設計方法によれば、半導体集積回路におけるクロックスキューを低減し得るクロック信号供給回路の設計方法を自動化し得る。
【０１２４】
図１５とともに実施例のクロック信号供給回路の設計方法を適用可能な半導体集積回路の例について説明する。
【０１２５】
図１５は実施例のクロック信号供給回路の設計方法を適用可能な半導体集積回路の例としての、ＤＩＭＭ（Ｄｕａｌ Ｉｎｌｉｎｅ Ｍｅｍｏｒｙ Ｍｏｄｕｌｅ）を制御するメモリコントローラを示す。当該メモリコントローラの動作周波数は例えばＧＨｚのオーダーを超えるものとされる。
【０１２６】
出願人は図１５とともに上記したメモリコントローラの回路設計において、実施例のクロック信号供給回路の設計方法を実行した。より具体的には、同方法をプログラムで実現し、クロックバッファの挿入およびクロックラインの接続に係る回路設計を自動化して実施した。
【０１２７】
その結果フリップフロップ間のクロックスキューを低減することができた。またセットアップタイミング、ホールドタイミング等に係る設計作業を容易に成しえた。また自動化により、グループ化、ゲートエントリ、スキュー調整、タイミング調整、配置等の工数を削減できた。したがってＬＳＩ開発期間の短縮、開発コストの削減が可能な点が確認できた。
【０１２８】
図１６は実施例のクロック信号供給回路の設計方法をプログラムで実現する場合に使用可能なコンピュータの構成を説明するためのブロック図である。
【０１２９】
図１６に示すごとく、同コンピュータ５００は、与えられたプログラムを構成する命令を実行することによって様々な動作を実行するためのＣＰＵ５０１と、キーボード、マウス等よりなり設計者が操作内容又はデータを入力するための操作部５０２とを有する。またコンピュータ５００は、設計者にＣＰＵ５０１による処理経過、処理結果等を表示するＣＲＴ、液晶表示器等よりなる表示部５０３を有する。またコンピュータ５００は、ＲＯＭ、ＲＡＭ等よりなりＣＰＵ５０４が実行するプログラム、データ等を記憶したり作業領域として使用される上記記憶装置としてのメモリ５０４を有する。またコンピュータ５００は，プログラム、データ等を格納する上記記憶装置としてのハードディスク装置５０５を有する。またコンピュータ５００は、上記記憶装置としてのＣＤ−ＲＯＭ５０７を媒介として外部からプログラムをロードしたりデータをロードするためのＣＤ−ＲＯＭドライブ５０６を有する。またコンピュータ５００は、インターネット、ＬＡＮ等の通信網５０９を介して外部サーバからプログラムをダウンロード等するためのモデム５０８を有する。
【０１３０】
コンピュータ５００はＣＤ−ＲＯＭ５０７を媒介として、あるいは通信ネットワーク５０９を媒介として、上述の実施例のクロック信号供給回路の設計方法をＣＰＵ５０１に実行させるためのプログラムをロードあるいはダウンロードする。そしてこれをハードディスク装置５０５にインストールし、適宜メモリ５０４にロードしてＣＰＵ５０１が実行する。その結果、同コンピュータ５００により実施例のクロック信号供給回路の設計方法が自動的に実行される。
【０１３１】
なお実施例のクロック信号供給回路の設計方法は上記の如くフリップフロップにクロック信号を供給する回路の設計方法に限られず、他の回路素子にクロック信号を供給する回路の設計方法にも同様に適用可能である。
【０１３２】
また実施例のクロック信号供給回路の設計方法では、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００を当該順番に実施するものとして説明した。しかしながら最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の実行の順序はこの順序に限られず、他の順序で実行してもよい。
【０１３３】
また最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の全てを実行するように説明した。しかしながら、最適化１（交換）Ｓ２００，最適化２（移動）Ｓ３００および最適化３（結合）Ｓ４００の計３種の最適化のうちの少なくとも一種の最適化のみを実行するようにしてもよい。
【０１３４】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
演算手段がクロック信号の供給される複数の回路素子の回路データを記憶装置から読み込む段階と、
演算手段が前記複数の回路素子をグループ分けする段階と、
演算手段がグループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する段階とを有するクロック信号供給回路の設計方法であって、
前記各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号を供給することを特徴とするクロック信号供給回路の設計方法。
（付記２）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
付記１に記載のクロック信号供給回路の設計方法。
（付記３）
前記グループ分けする段階は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする付記１に記載のクロック信号供給回路の設計方法。
（付記４）
前記最適化段階では更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記３に記載のクロック信号供給回路の設計方法。
（付記５）
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記３または４に記載のクロック信号供給回路の設計方法。
（付記６）
コンピュータに、クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該グループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復させるプログラム。
（付記７）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
請求項６に記載のプログラム。
（付記８）
更にコンピュータに、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得る段階を実行させることを特徴とする請求項６に記載のプログラム。
（付記９）
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記８に記載のプログラム。
（付記１０）
前記交換段階では、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階では、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記８または９に記載のプログラム。
（付記１１）
クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該複数のグループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくとも何れかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する演算手段を有し、
前記最適化段階の反復の結果得られる各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号が供給されることを特徴とする情報処理装置。
（付記１２）
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループに属する各回路素子にクロック信号を供給するクロックバッファから各回路素子までの総配線長、当該グループにおける前記クロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれかとされる
請求項１１に記載の情報処理装置。
（付記１３）
更に前記演算手段は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１１に記載の情報処理装置。
（付記１４）
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする付記１３に記載の情報処理装置。
（付記１５）
前記交換段階では、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階では、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする付記１３または１４に記載の情報処理装置。
【図面の簡単な説明】
【０１３５】
【図１】実施例によるクロック信号供給回路の設計方法のデータの流れを示す図である。
【図２】図１中、フリップフロップのグループ化の基本的なアルゴリズムの流れを示す図である。
【図３】図２中、初期グループ化の動作の流れを示す図である。
【図４Ａ】初期グループ化の動作を説明するための図（その１）である。
【図４Ｂ】初期グループ化の動作を説明するための図（その２）である。
【図４Ｃ】初期グループ化の動作を説明するための図（その３）である。
【図４Ｄ】初期グループ化の動作を説明するための図（その４）である。
【図４Ｅ】初期グループ化の動作を説明するための図（その５）である。
【図４Ｆ】初期グループ化の動作を説明するための図（その６）である。
【図４Ｇ】初期グループ化の動作を説明するための図（その７）である。
【図５Ａ】初期グループ化におけるグループのエリアの決め方について説明するための図（その１）である。
【図５Ｂ】初期グループ化におけるグループのエリアの決め方について説明するための図（その２）である。
【図６Ａ】初期グループ化を実行後の状態の例を示す図（その１）である。
【図６Ｂ】初期グループ化を実行後の状態の例を示す図（その２）である。
【図７Ａ】最適化１（交換）について説明するための図（その１）である。
【図７Ｂ】最適化１（交換）について説明するための図（その２）である。
【図７Ｃ】最適化１（交換）について説明するための図（その３）である。
【図７Ｄ】最適化１（交換）について説明するための図（その４）である。
【図８Ａ】最適化２（移動）について説明するための図（その１）である。
【図８Ｂ】最適化２（移動）について説明するための図（その２）である。
【図８Ｃ】最適化２（移動）について説明するための図（その３）である。
【図８Ｄ】最適化２（移動）について説明するための図（その４）である。
【図９】最適化１，最適化２を実行後の状態の例を示す図である。
【図１０Ａ】最適化３（結合）について説明するための図（その１）である。
【図１０Ｂ】最適化３（結合）について説明するための図（その２）である。
【図１０Ｃ】最適化３（結合）について説明するための図（その３）である。
【図１１】フリップフロップのグループ化における収束の判定について説明するための図である。
【図１２Ａ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その１）である。
【図１２Ｂ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その２）である。
【図１２Ｃ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その３）である。
【図１２Ｄ】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その４）である。
【図１３】最適化１，最適化２，最適化３を反復する場合の例について説明するための図（その５）である。
【図１４】クロックバッファの挿入、クロックラインの接続について説明するための図である。
【図１５】実施例の効果の検証について説明するための図である。
【図１６】実施例によるクロック信号供給回路の設計方法をコンピュータで実現する場合について説明するための図である。
【符号の説明】
【０１３６】
５０１ ＣＰＵ
５０２ 操作部
５０３ 表示部
５０４ メモリ（記憶装置）
５０５ ＨＤＤ（記憶装置）
５０６ ＣＤ−ＲＯＭドライブ
５０７ ＣＤ―ＲＯＭ（記憶装置）
５０８ モデム
５０９ 通信網
ＦＦ フリップフロップ
Ｇ１，Ｇ２，Ｇ３，... グループ
Ａ１，Ａ２，Ａ３，... エリア
Ｃ１，Ｃ２，Ｃ３，．． グループの中心
Ｂ１，Ｂ２，Ｂ３，... クロックバッファ
Ｌ０，Ｌ１，Ｌ２，Ｌ３，... クロックライン
【特許請求の範囲】
【請求項１】
演算手段がクロック信号の供給される複数の回路素子の回路データを記憶装置から読み込む段階と、
演算手段が前記複数の回路素子をグループ分けする段階と、
演算手段がグループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する段階とを有するクロック信号供給回路の設計方法であって、
前記各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号を供給することを特徴とするクロック信号供給回路の設計方法。
【請求項２】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項１に記載のクロック信号供給回路の設計方法。
【請求項３】
前記グループ分けする段階は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１に記載のクロック信号供給回路の設計方法。
【請求項４】
前記最適化段階では更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項３に記載のクロック信号供給回路の設計方法。
【請求項５】
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする請求項３または４記載のクロック信号供給回路の設計方法。
【請求項６】
コンピュータに、クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該グループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復させるプログラム。
【請求項７】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項６に記載のプログラム。
【請求項８】
更にコンピュータに、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得る段階を実行させることを特徴とする請求項６に記載のプログラム。
【請求項９】
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項８に記載のプログラム。
【請求項１０】
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする請求項８または９に記載のプログラム。
【請求項１１】
クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該複数のグループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくとも何れかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する演算手段を有し、
前記最適化段階の反復の結果得られる各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号が供給されることを特徴とする情報処理装置。
【請求項１２】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項１１に記載の情報処理装置。
【請求項１３】
更に前記演算手段は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１１に記載の情報処理装置。
【請求項１４】
前記演算手段は前記最適化段階にて更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項１３に記載のクロック信号供給回路の設計方法。
【請求項１】
演算手段がクロック信号の供給される複数の回路素子の回路データを記憶装置から読み込む段階と、
演算手段が前記複数の回路素子をグループ分けする段階と、
演算手段がグループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する段階とを有するクロック信号供給回路の設計方法であって、
前記各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号を供給することを特徴とするクロック信号供給回路の設計方法。
【請求項２】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項１に記載のクロック信号供給回路の設計方法。
【請求項３】
前記グループ分けする段階は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１に記載のクロック信号供給回路の設計方法。
【請求項４】
前記最適化段階では更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項３に記載のクロック信号供給回路の設計方法。
【請求項５】
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする請求項３または４記載のクロック信号供給回路の設計方法。
【請求項６】
コンピュータに、クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該グループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくともいずれかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復させるプログラム。
【請求項７】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項６に記載のプログラム。
【請求項８】
更にコンピュータに、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得る段階を実行させることを特徴とする請求項６に記載のプログラム。
【請求項９】
前記最適化段階では更に、２つのグループの回路素子が互いに相手側のエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項８に記載のプログラム。
【請求項１０】
前記交換段階は、対象となる２つのグループのエリア同士が重なり合いかつ交換の結果前記全グループについての合計が減少する場合当該交換後のグループを維持し、当該交換後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新し、
前記移動段階は、対象となる２つのグループのエリア同士が重なり合いかつ移動後の結果前記全グループについての合計が最も減少する場合当該移動後のグループを維持し、当該移動後の各グループに属する回路素子の位置に基づいて各グループのエリアを更新することを特徴とする請求項８または９に記載のプログラム。
【請求項１１】
クロック信号の供給が行われる複数の回路素子をグループに分けて得られた当該複数のグループに対し、グループ間で回路素子の交換を行う交換段階およびグループ間で回路素子の移動を行う移動段階のうちの少なくとも何れかを実行し、当該実行の前後で各グループにつき当該グループの評価指標値を算出し当該算出されたグループごとの評価指標値を全グループについて合計し当該全グループについての合計が減少する場合には当該実行後のグループを維持し減少しない場合には当該実行前のグループを維持する最適化段階を反復する演算手段を有し、
前記最適化段階の反復の結果得られる各グループに属する回路素子に対し一のクロックバッファを用いてクロック信号が供給されることを特徴とする情報処理装置。
【請求項１２】
前記評価指標値は、当該グループに属する各回路素子の位置と当該グループの中心位置との間のマンハッタン距離の合計、当該グループに属する各回路素子の位置と当該グループの中心位置との間のユークリッド距離の合計、当該グループのクロックバッファから各回路素子までの総配線長、当該グループのクロックバッファのゲート容量、当該クロックバッファから各回路素子までの配線の容量および各回路素子のクロック信号入力端子の容量の合計並びに当該グループのクロックバッファから各回路素子のクロック信号入力端子までの遅延の合計のうちのいずれか一のものとされる
請求項１１に記載の情報処理装置。
【請求項１３】
更に前記演算手段は、前記複数の回路素子のうちから一の回路素子を選択し、未だグループが存在しない場合には当該一の回路素子が属するグループを設け、当該一の回路素子の位置に基づき当該一の回路素子を含むエリアを決定し、既にグループが存在する場合であって、前記一の回路素子が当該グループの前記エリア内に位置し、当該グループに属する回路素子の数が許容ファンアウト以内であれば、前記一の回路素子を当該グループに追加し、当該グループに属する回路素子の位置に基づいて前記エリアを更新する段階を、前記複数の回路素子のうち未だ選択されていない回路素子が無くなるまで反復することにより前記複数のグループを得ることを特徴とする請求項１１に記載の情報処理装置。
【請求項１４】
前記演算手段は前記最適化段階にて更に、２つのグループの回路素子が互いに相手のグループのエリアに含まれかつ当該２つのグループに属する回路素子の個数が前記許容ファンアウト以内の場合に、当該２つのグループ同士を結合して一のグループとする結合段階を実行することを特徴とする請求項１３に記載のクロック信号供給回路の設計方法。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【図４Ｅ】
【図４Ｆ】
【図４Ｇ】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１２Ｄ】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図４Ｄ】
【図４Ｅ】
【図４Ｆ】
【図４Ｇ】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１２Ｃ】
【図１２Ｄ】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１０−８６２８４（Ｐ２０１０−８６２８４Ａ）
【公開日】平成２２年４月１５日（２０１０．４．１５）
【国際特許分類】
【出願番号】特願２００８−２５４６３４（Ｐ２００８−２５４６３４）
【出願日】平成２０年９月３０日（２００８．９．３０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２２年４月１５日（２０１０．４．１５）
【国際特許分類】
【出願日】平成２０年９月３０日（２００８．９．３０）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]