クロックツリー設計装置及びクロックツリー設計方法
【課題】クロックレイテンシを最小にする条件下において、クロックスキュー及びバッファ数を比較的少なくする。
【解決手段】実施形態のクロックツリー設計装置は、ターゲットシンクからのマンハッタン距離と最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、等距離点の集合のうちパス設定ブロック領域内でクロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、クロックソースから分岐点までのパス設定ブロック領域内にターゲットシンクと最遠シンクとの共有パスを設定すると共に、分岐点からターゲットシンクまでのクロックパス及び分岐点から最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部とを具備する。
【解決手段】実施形態のクロックツリー設計装置は、ターゲットシンクからのマンハッタン距離と最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、等距離点の集合のうちパス設定ブロック領域内でクロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、クロックソースから分岐点までのパス設定ブロック領域内にターゲットシンクと最遠シンクとの共有パスを設定すると共に、分岐点からターゲットシンクまでのクロックパス及び分岐点から最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、クロックツリー設計装置及びクロックツリー設計方法に関する
【背景技術】
【０００２】
従来、ＬＳＩにおけるクロック分配方式として、クロックツリー方式がある。クロックツリーのレイアウト設計においては、クロックレイテンシ、バッファ数、クロックスキュー等を考慮した設計を行う必要がある。
【０００３】
Ｈツリー方式は、クロックの供給先であるシンク（ｓｉｎｋ）同士の重心にクロックパス（以下、単にパスともいう）を設定するものである。Ｈツリー方式は、各シンクまでのパスとして共有パスが多く用いられるのでバッファ数削減、ＯＣＶマージンの削減の観点から優れている。また、Ｈツリー方式は、各シンクへのパス長が等しくなることが多く、クロックスキューの観点からも優れている。
【０００４】
また、クロックレイテンシの観点からは、クロックソースから最も遠い距離のシンク（以下、最遠シンクという）までのクロックパス長は短い方がよい。しかしながら、Ｈツリー方式では、クロックパスは必ず２シンク間の重心を通るように設定されることから、クロックレイテンシが比較的大きくなることがある。
【０００５】
クロックレイテンシを最小にするようにクロックツリーを設計する方法として、クロックソースから最遠シンクまでの距離がマンハッタン距離となることのみを条件に、クロックソースと最遠シンク間にクロックパスを設定する方法が考えられる。
【０００６】
しかしながら、この方法では、クロックソースと最遠シンク以外のシンクとの間のパスの最適化が困難であり、バッファ数、ＯＣＶ（on-chip variation）マージン及びスキューが増大する可能性がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−７５００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態は、クロックレイテンシを最小にする条件下において、共有パスのパス長を比較的長くして、クロックスキュー及びバッファ数を比較的少なくすることができるクロックツリー設計装置及びクロックツリー設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
実施形態のクロックツリー設計装置は、クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部とを具備する。
【図面の簡単な説明】
【００１０】
【図１】本発明の第１の実施の形態に係るクロックツリー設計装置を示すブロック図。
【図２】クロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図。
【図３】クロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図。
【図４】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図５】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図６】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図７】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図８】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図９】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１０】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１１】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１２】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１３】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１４】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１５】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１６】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１７】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１８】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１９】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２０】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２１】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２２】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２３】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２４】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２５】クロックツリー設計の全体の動作を示すフローチャート。
【図２６】図２５中の分岐点及びパス設定フローを示すフローチャート。
【図２７】本発明の第２の実施の形態を示す説明図。
【図２８】本発明の第２の実施の形態を示す説明図。
【図２９】本発明の第２の実施の形態を示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。
【００１２】
（第１の実施の形態）
図１は本発明の第１の実施の形態に係るクロックツリー設計装置を示すブロック図である。
【００１３】
先ず、図２及び図２４を参照して、本実施の形態におけるクロックツリー設計方法について説明する。図２及び図３はクロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図である。なお、図２ではクロックが供給されるフリップフロップＦの信号ピンをシンクとする。
【００１４】
図２（ａ），（ｂ）はクロックレイテンシとパスとの関係を示している。図２（ａ），（ｂ）は夫々クロックソースＳｏとシンクＳｉ１との間に設定されたクロックパスＰ１，Ｐ２を示している。パスＰ１のパス長はマンハッタン距離に等しく、パスＰ２はパスの一部が平行な部分を有しているので、マンハッタン距離よりも長い。クロックレイテンシの観点からは、図２（ａ）のように最遠シンクまでのパスのパス長が短いことが望ましい。
【００１５】
図２（ｃ），（ｄ）はバッファ数及びＯＣＶマージンとパスとの関係を示している。図２（ｃ），（ｄ）はクロックソースＳｏとシンクＳｉ２，Ｓｉ３との間に設定されたクロックパスＰ３〜Ｐ７を示している。図２（ｃ）においては、クロックソースＳｏからシンクＳｉ２，Ｓｉ３までのパスＰ３〜Ｐ５のうち、パスＰ３は共有パスである。図２（ｄ）においては、クロックソースＳｏからシンクＳｉ２，Ｓｉ３までのパスＰ６，Ｐ７は独立したパスであり、共有パスは存在しない。バッファ数及びＯＣＶマージンの観点からは、図２（ｃ）のように共有パスを設けた方が望ましい。
【００１６】
図２（ｅ），（ｆ）はクロックスキューとパスとの関係を示している。図２（ｅ），（ｆ）はクロックソースＳｏとシンクＳｉ４，Ｓｉ５との間に設定されたクロックパスＰ８〜Ｐ１０を示している。図２（ｅ），（ｆ）はクロックスキューが生じていない例を示しており、図２（ｅ）ではパスＰ８，Ｐ９のパス長を同一にすることによりクロックスキューが発生しないようにしているのに対し、図２（ｆ）ではパスＰ８上のバッファ数よりもパスＰ１０上のバッファ数を増やすことで、クロックスキューが発生しないようにしている。
【００１７】
クロックスキューを小さくするためにバッファを挿入する手法を採用した場合には、微細プロセスでの遅延ばらつきや電源電圧の低下の影響を受け、チップのコンディションによっては、バッファ挿入によってかえってスキューが大きくなってしまうことがある。従って、クロックスキューの観点からは、図２（ｅ）のように各シンクまでの距離は等しい方がよい。
【００１８】
このように、クロックレイテンシの観点からは、最遠シンクまでのパスのパス長が短いことが望ましく、バッファ数及びＯＣＶマージンの観点からは、長い共有パスを設けた方が望ましく、クロックスキューの観点からは、各シンクまでのパス長を等しくした方が望ましい。
【００１９】
図３は複数の四角の枠によって各シンクＳｉを示しており、クロックソースＳｏと最遠シンクＳｉｆとの間のパスを太線によって示している。図３（ａ）はＨツリー方式を示しており、各シンクＳｉを結ぶ線によってパスＰを示している。各パスＰは、２つのシンク間の重心を通るように設計されていることから、最遠シンクＳｉｆまでのパスＰｍには平行な部分が形成されて、マンハッタン距離よりも長いパス長を有する。即ち、Ｈツリー方式では、最遠シンクまでのパス長が長くなり、クロックレイテンシが大きくなることがあるという欠点がある。
【００２０】
一方、図３（ｂ）は、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長がマンハッタン距離となるようにパスを設定する例を示している。太線の四角の枠内を通り平行な部分が形成されなければ、どのようなパスを採用しても、最遠シンクＳｉｆまでのパス長を最短にすることができる。
【００２１】
しかしながら、図３（ｂ）の方法では、他のシンクに対するパスを最適化することはできず、バッファ数やクロックスキュー等の観点では不利である。
【００２２】
そこで、本実施の形態においては、図４〜図２４に示すクロックツリー設計方法を採用することにより、クロックレイテンシを最小にしつつ、各シンク間の共有パスを増大させ、各シンク間のパス長を等しくする。これにより、クロックレイテンシ、バッファ数、クロックスキュー及びＯＣＶマージン等を最適化したクロックツリーの生成を可能にする。
【００２３】
本実施の形態においては、クロックレイテンシを最小にするために、最遠シンクＳｉｆまでのパスを優先するようにパスの決定を行う。また、共有パスを増やすために、クロックソースからなるべく離れた位置までを共有パスを用い、共有パスの終端を分岐点として分岐点から各シンクまでのパスを形成する。分岐点から各シンクまでのパス同士を等しい長さに設定するように、分岐点の位置を決定する。
【００２４】
図４はクロックツリー設計対象の回路レイアウトの一例を示している。図５〜図２４は図４と同一の回路レイアウトを示している。図４乃至図２４において、塗りつぶした四角の枠はクロックソースを示し、白抜きの四角の枠は回路レイアウト内で同時にクロックを供給したい（クロックレイテンシを一致させる）シンクを示し、斜線を施した四角の枠は最遠シンクを示している。図４〜図２４の破線は回路上に配線可能な配線パターンの方向を示している。図４〜図２４の例では、水平及び垂直方向に所定の配線ピッチで、配線パターンを形成可能であることを示している。なお、図４〜図２４において決定したパスは太線にて示している。
【００２５】
先ず、クロックレイテンシを最小にするために、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長を最短、即ち、マンハッタン距離とするパスの候補を求める。クロックソースＳｏと最遠シンクＳｉｆとのパス長をマンハッタン距離とするパスは複数有る。図５はそのうちの３つのパスＰｆを太線にて示している。即ち、クロックソースＳｏ及び最遠シンクＳｉｆの位置を対角の頂点とする長方形で囲まれた領域（斜線部）Ｂ１内において、平行なパスを形成しないようにパスを設定すればよい。このように、斜線部の領域は、２点間のパス長をマンハッタン距離に設定可能なパスが存在する領域（以下、パス設定ブロック領域という）である。
【００２６】
いま、例えば、図６に示すように、１つのシンクを選択して、パスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆからのマンハッタン距離とターゲットシンクＳｉｔからのマンハッタン距離とが等距離となる点の軌跡ＴＡ１を求める。なお、図６以降の図ではこの点を白抜きの丸印によって示している。軌跡ＴＡ１の一部は、図７に示すように、パス設定ブロック領域Ｂ１内に存在している。
【００２７】
本実施の形態においては、図８に示すように、この等距離の点の軌跡ＴＡ１のうち、パス設定ブロック領域Ｂ１内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ１とする。本実施の形態においては、分岐点Ｔ１を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とし、クロックソースＳｏから分岐点Ｔ１までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ１までの共有パスの候補は、図９の斜線部に示すパス設定ブロック領域Ｂ２内に設定する。これにより、クロックソースＳｏから分岐点Ｔ１までのパスのパス長を、クロックソースＳｏと分岐点Ｔ１とを対角の頂点とする長方形により規程されるマンハッタン距離にすることができ、クロックソースＳｏから分岐点Ｔ１までのパスのパス長を最短にすることができる。
【００２８】
図１０に示すように、分岐点Ｔ１から最遠シンクＳｉｆまでのパスＰｆと分岐点Ｔ１からターゲットシンクＳｉｔまでのパスＰｔ１とを決定する。これらのパスＰｆ，Ｐｔ１のパス長をマンハッタン距離に設定することで、パスＰｆ，Ｐｔ１のパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ１までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００２９】
図１１乃至図１７は最遠シンクＳｉｆからのマンハッタン距離とターゲートシンクＳｉｔからのマンハッタン距離とが等距離となる点の軌跡を求める方法を説明するための説明図である。
【００３０】
図１１の網線は配線グリッドを示している。図１１のグリッド上の黒丸は、等距離点の軌跡を求めようとする２つのシンクの位置Ａ，Ｂを示している。先ず、図１２に示すように、位置Ａ，Ｂの中点の位置Ｃにおけるグリッド（黒丸）を求める。２点Ａ，Ｂ間の水平方向及び垂直方向のグリッド数が奇数個の場合には、中点の位置Ｃはグリッド上に位置しない。この場合には、例えば、中点の位置Ｃを半グリッド分移動させることで、中点の位置Ｃをグリッド上に位置させる。或いは、予め、各シンクの位置を、シンク同士の間に偶数個のグリッドが配置されるように設定する等の方法を採用する。
【００３１】
次に、配線グリッドを中点Ｃのグリッドを原点とする直交座標と考え、線分ＡＢが通過しない象限上に、中点Ｃのグリッドからｘ，ｙ方向の両方向に位置が変化するようにグリッド上に白抜きで示す点（以下、仮の中点という）をとる。この仮の中点は、点Ａからの距離と点Ｂからの距離とが等距離（マンハッタン距離）となる点を求めるためのものであり、点Ａ，Ｂからの各距離が、ｘ方向について小さくなった場合にはｙ方向について大きくなるようにし、ｘ方向について大きくなった場合にはｙ方向について小さくなるようにしたものである。
【００３２】
しかし、図１３に示すように、点Ａ，Ｂを対角の頂点とする長方形の領域Ｒ１の領域外にとった仮の中点は、点Ａ，Ｂからのマンハッタン距離が相互に異なる。点Ａ，Ｂからのマンハッタン距離が等しくなる中点は、領域Ｒ１端部の仮の中点からｘ方向又はｙ方向に延出したグリッド上に存在する。
【００３３】
図１４はこうして求めた等距離となる点の軌跡ＴＡを示している。なお、中点がｘ，ｙ方向のいずれに延出したグリッド上に存在するかは、領域Ｒ１のｘ方向のサイズとｙ方向のサイズとに依存し、図１４のようにｙ方向のサイズがｘ方向よりも大きい場合には、ｘ方向上に中点が存在し、図１５に示すように、ｙ方向のサイズがｘ方向よりも小さい場合には、ｙ方向上に中点が存在する。
【００３４】
また、図１６に示すように、領域Ｒ１のｘ，ｙ方向のサイズが等しい場合には、仮の中点が中点となる。また、図１７に示すように、２点Ａ，Ｂのｘ座標又はｙ座標の一方が同一ならば、直線ＡＢの垂直２等分線上のグリッドが等距離となる点の軌跡である。
【００３５】
以後、同様の手法によって、各シンクまでのパスを決定する。
【００３６】
例えば、図１８に示すように、１つのシンクを選択してパスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆとターゲットシンクＳｉｔとの間で、マンハッタン距離が等距離となる点の軌跡ＴＡ２を求める。軌跡ＴＡ２の一部は、図１８に示すように、パス設定ブロック領域Ｂ２内に存在している。
【００３７】
次に、図１９に示すように、この等距離の点の軌跡ＴＡ２のうち、パス設定ブロック領域Ｂ２内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ２とする。この分岐点Ｔ２を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とする。クロックソースＳｏから分岐点Ｔ２までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ２までの共有パスの候補は、図１９の斜線部に示すパス設定ブロック領域Ｂ３内に設定する。これにより、クロックソースＳｏから分岐点Ｔ２までのパスのパス長を最短にすることができる。
【００３８】
図２０に示すように、パス長がマンハッタン距離となるように、分岐点Ｔ２からターゲットシンクＳｉｔまでのパスＰｔ２を決定する。なお、分岐点Ｔ２と分岐点Ｔ１との間のパスは、図２０に示すように、パス設定ブロック領域Ｂ２中の一部の領域Ｂ２’に設定される。
【００３９】
分岐点Ｔ２から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでの各パスのパス長をマンハッタン距離に設定することで、これらのパスのパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ２までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００４０】
同様にして、次に設定するターゲットシンクＳｉｔまでのパスを決定する。
【００４１】
図２１に示すように、残りの１つのシンクをパスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆとターゲットシンクＳｉｔとの間で、マンハッタン距離が等距離となる点の軌跡ＴＡ３を求める。軌跡ＴＡ３の一部は、図２１に示すように、パス設定ブロック領域Ｂ３内に存在している。
【００４２】
次に、図２２に示すように、この等距離の点の軌跡ＴＡ３のうち、パス設定ブロック領域Ｂ３内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ３とする。この分岐点Ｔ３を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とする。クロックソースＳｏから分岐点Ｔ３までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ２までの共有パスの候補は、図２２の斜線部に示すパス設定ブロック領域Ｂ４内に設定する。これにより、クロックソースＳｏから分岐点Ｔ３までのパスのパス長を最短にすることができる。
【００４３】
図２３に示すように、パス長がマンハッタン距離となるように、分岐点Ｔ３からターゲットシンクＳｉｔまでのパスＰｔ３を決定する。なお、分岐点Ｔ３と分岐点Ｔ２との間のパスは、図２３に示すように、パス設定ブロック領域Ｂ３中の一部の領域Ｂ３’に設定される。
【００４４】
分岐点Ｔ３から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでの各パスのパス長をマンハッタン距離に設定することで、これらのパスのパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ３までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００４５】
最後に、パス設定ブロック領域Ｂ４内でパス長がマンハッタン距離となるようにクロックソースＳｏから分岐点Ｔ３までのパスを設定する。例えば、図２４では、パス設定ブロック領域Ｂ４の一部の領域Ｂ４’に共有パスＰｃを設定した例を示している。
【００４６】
結局、図４〜図２４の例は、最遠シンクＳｉｆを含む全てのシンクＳｉにおいて、クロックソースＳｏからのパスは、最短で且つ等距離であり、比較的長い共有パスが設定されている。
【００４７】
図１において、クロックツリー設計装置１には、各種情報を記憶するメモリ１１〜１５が設けられている。シンク及び配線情報メモリ１１は、クロックツリー設計対象の回路レイアウト中に設けられるクロックソースＳｏ、各シンクＳｉ、最遠シンクＳｉｆ及び配線に関する情報（以下、シンク及び配線情報という）が記憶されている。例えば、シンク及び配線情報としては、クロックソースＳｏ、各シンクＳｉ、最遠シンクＳｉｆ及び配線の位置に関する情報や、配線グリッドの単位の情報等が含まれる。なお、本実施の形態においては、クロックソースＳｏ、シンクＳｉ及び最遠シンクＳｉｆは、クロックの入出力端を構成するピンを示しているものとする。また、ピンのサイズや配線の幅等は無視できるものとする。
【００４８】
処理順情報メモリ１２には、各シンクＳｉのうちのいずれのシンクをターゲットシンクＳｉｔとするかを順次示す情報（処理順情報）を記憶する。図４乃至図２４の例は一例であり、ターゲットシンクＳｉｔとする順番が異なれば、設計されるクロックツリーも異なる。本実施の形態においては、処理順は既に決定されており、処理順情報を読出すことで、決定された処理順で順次処理が行われるものとして説明する。
【００４９】
なお、処理順は、クロックツリーの生成に大きな影響を与える。処理順の決定には多く処理が必要であると予想される。そこで、例えば、いくつかの処理順を決定しておき、上述した図４〜図２４の手法に従ったクロックツリーの生成結果から、最適なクロックツリーを選択するようにしてもよい。
【００５０】
なお、より長い共有パスを設定するためには、クロックソースＳｏと最遠シンクＳｉｆとを対角の頂点とする長方形で規定されるパス設定ブロック領域の外にあるシンクを内にあるシンクよりも先に処理した方がよい。
【００５１】
制御部１０はメモリ１１〜１５の書込み及び読出しを制御すると共に、各部を制御してクロックツリーを設計する。
【００５２】
パス設定ブロック設定部２１は、制御部１０を介してメモリ１１からのシンク及び配線情報が与えられて、パス設定ブロック領域を設定し、パス設定ブロック領域情報を出力する。このパス設定ブロック領域情報は、制御部１０を介してパス設定ブロック領域情報メモリ１３に与えられる。パス設定ブロック領域情報メモリ１３は、２点間のパス設定ブロック領域に関する情報を記憶する。
【００５３】
また、分岐点情報メモリ１４は、後述する分岐点設定部２４から制御部１０を介して分岐点情報が与えられて記憶する。パス設定ブロック設定部２１は、制御部１０を介して分岐点情報も与えられ、クロックソースＳｏと分岐点との間のパス設定ブロック領域も設定して、パス設定ブロック領域情報として出力し、記憶させるようになっている。
【００５４】
制御部１０は、処理順情報メモリ１２からの処理順情報に基づいて、シンク及び配線情報メモリ１１から、最遠シンクＳｉｆ及びターゲットシンクＳｉｔに関してシンク及び配線情報をマンハッタン距離算出部２２に与えることができる。マンハッタン距離算出部２２は、制御部１０によって指定された２点のマンハッタン距離を算出する。マンハッタン距離算出部２２の算出結果は制御部１０を介して等距離点集合算出部２３に供給され、等距離点集合算出部２３は、２点からのマンハッタン距離が等しくなる、等距離点の集合を求める。なお、等距離点の集合は、厳密には配線上に存在しないこともある。そこで、等距離点集合算出部２３は、配線に関する情報を用いることで、例えば、最も近い配線上に等距離点が存在するように補正した等距離点集合を求める。
【００５５】
分岐点設定部２４は、制御部１０を介して等距離点集合の情報、パス設定ブロック領域情報、シンク及び配線情報が与えられて、パス設定ブロック領域内において、クロックソースＳｏから最も遠い距離に位置する分岐点を求める。分岐点設定部２４により設定された分岐点の情報は、分岐点情報として分岐点情報メモリ１４に与えられて記憶される。
【００５６】
パス設定部２５は、シンク及び配線情報、分岐点情報、パス設定ブロック領域情報が与えられて、分岐点からターゲットシンクＳｉｔ及び最遠シンクＳｉｆまでのパス及びソースＳｏから分岐点までのパスを設定する。パス設定部２５によって設定されたクロックパスに関する情報は、パス設定情報メモリ１５に与えられる。こうして、パス設定情報メモリ１５にクロックツリー設計によって設計されたクロックツリーに関するパス設定情報が記憶される。
【００５７】
なお、図１のクロックツリー設計装置は、ＣＰＵ、メモリ及び入出力装置を備えたコンピュータによって実現可能である。
【００５８】
次に、このように構成された実施の形態の動作について図２５及び図２６を参照して説明する。図２５はクロックツリー設計の全体の動作を示すフローチャートであり、図２６は図２５中の分岐点及びパス設定フローを示すフローチャートである。
【００５９】
図２５のステップＳ１において、制御部１０はメモリ１１，１２からシンク及び配線情報と処理順情報とを読み出す。制御部１０は、ステップＳ２において、処理順情報に基づいてターゲットシンクＳｉｔを決定する。次いで、制御部１０は、各部を制御して、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスの分岐点を決定して、分岐点から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでのパスを決定する（ステップＳ３）。
【００６０】
制御部１０は、ステップＳ４において、全てのシンクＳｉについてパスの決定を行ったか否かを判定し、行っていない場合には、処理をステップＳ２に戻して、分岐点及びパスの設定処理を繰り返す。
【００６１】
制御部１０は、分岐点を決定するために、図２６のステップＳ１１において、マンハッタン距離算出部２２によって、最遠シンクＳｉｆとターゲットシンクＳｉｔとの間のマンハッタン距離を算出させる。等距離点集合算出部２３は、制御部１０に制御されて、等距離点の軌跡を算出する（ステップＳ１２）。
【００６２】
分岐点設定部２４は、パス設定ブロック領域内で、クロックソースＳｏからの距離が最も遠い等距離点を分岐点に設定する（ステップＳ１３）。なお、最初のターゲットシンクＳｉｔに対する処理時には、パス設定ブロック設定部２１によって、クロックソースＳｏと最遠シンクＳｉｆとを夫々対角の頂点とする長方形がパス設定ブロック領域として設定されている。
【００６３】
ステップＳ１３の処理によって、例えば、図８，図１９，図２２の各最遠シンクＳｉｆとターゲットシンクＳｉｔとについて分岐点Ｔ１〜Ｔ３が決定される。
【００６４】
次のステップＳ１４では、パス設定ブロック設定部２１によって、クロックソースＳｏとステップＳ１４で求められた分岐点とを対角の頂点とする長方形を新たなパス設定ブロック領域として設定する。
【００６５】
パス設定部２５は、ステップＳ１５において、ステップＳ１４で求めた分岐点から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでのパスを決定する。
【００６６】
パス設定部２５は、分岐点から全てのターゲットシンクＳｉｔまでのパスを決定すると、最後に、クロックソースＳｏから最後に求めた分岐点までのパスを決定する。
【００６７】
なお、次に分岐点を決定する処理を行う必要がない場合には、ステップＳ１４におけるパス設定ブロック領域の設定処理は不要である。
【００６８】
このように本実施の形態においては、クロックレイテンシを最小にする条件化において、最遠シンクとターゲットシンクとの間の等距離点でクロックソースから最も遠い点を分岐点に決定し、分岐点を通過するパスを決定する。クロックソースから分岐点までは共有パスとなり、共有パスを増大させることができる。また、分岐点からのパスのパス長は等しく、レイテンシを最小にしながら、共有パスを増大させ、各シンクまでのパス長を等しくすることができる。これにより、クロックレイテンシを最小にしながら、共有パスのパス長を最長にし、クロックスキュー及びバッファ数を最小にすることができる。パスの配線長を等長にすることができるので、ばらつきに対するスキューの増大を抑制することが可能となる。
【００６９】
（第２の実施の形態）
図２７及び図２８は本発明の第２の実施の形態を示す説明図である。本実施の形態のハードウェア構成は図１の実施の形態と同様である。本実施の形態においては、分岐点及びパスの決定方法のみが第１の実施の形態と異なる。
【００７０】
図２７は図２４の回路レイアウト上の３つのシンク（Ｓｉ１〜Ｓｉ３）の外にもう１つのシンクＳｉ４が存在する場合の例を示している。シンクＳｉ４は、シンクＳｉ３の近傍に配置されており、図２７の例は、このシンクＳｉ４をターゲットシンクＳｉｔに設定し、このターゲットシンクＳｉｔについて、第１の実施の形態において説明した手法によって、分岐点及びパスを決定した例を示している。図２７の例では、ターゲットシンクＳｉ４には、クロックソースＳｏからパスＰｃ、分岐点Ｔ３及びパスＰｔ４’を介してクロックが供給される。
【００７１】
即ち、第１の実施の形態においては、最遠シンクＳｉｆとターゲットシンクＳｉｔとを、分岐点の設定に用いるシンクの組と考えて、このシンクの組における等距離点上に分岐点を決定した。しかしながら、図２７の例では、シンクＳｉ４はシンクＳｉ３の近傍に配置されているにも拘わらず、分岐点がシンクＳｉ２，Ｓｉ４から比較的離間しており、共有パスは比較的短い。
【００７２】
そこで、本実施の形態においては、パスが既に決定された任意のシンクを、ターゲットシンクＳｉｔと共に分岐点を求めるためのシンク（以下、ペアシンクという）とすると共に、クロックソースＳｏに代えて分岐点の１つを擬似的にクロックソース（以下、疑似ソースという）とすることで、共有パスを長くする分岐点を決定するようになっている。
【００７３】
第１の実施の形態に従ってパスが決定されたシンクＳｉとクロックソースＳｏとを結ぶパスのパス長は、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長と同一である。従って、クロックレイテンシを一致させるシンクの組として、最遠シンクＳｉｆに代えてパスが決定されたシンクをペアシンクとして用いることができる。
【００７４】
図２８にこの例を示しており、最遠シンクＳｉｆに代えて、ターゲットシンクＳｉｔ近傍のシンクＳｉ２をターゲットシンクＳｉｔへのパスの分岐点を求めるための組のペアシンクとする。また、ターゲットシンクＳｉｔに近い距離の分岐点Ｔ２を疑似ソースＳｏｐとする。
【００７５】
次にこのように構成された実施の形態の動作について図２９のフローチャートを参照して説明する。図２９において図２５と同一の手順には同一符号を付して説明を省略する。
【００７６】
本実施の形態においては、ステップＳ２の次に、ステップＳ２１及びステップＳ２２の処理が追加された点が図２５のフローと異なるのみである。分岐点及びパス設定処理は、図２６のフローに従って行われることは、第１の実施の形態と同様である。
【００７７】
本実施の形態においては、ステップＳ２において、ターゲットが決定されると、次のステップＳ２１において、制御部１０は、ターゲットシンクＳｉｔへの分岐点を求めるためのシンクの組を決定する。第１の実施の形態においては、常に最遠シンクＳｉｆを用いた。これに対し、本実施の形態においては、制御部１０は、ターゲットシンクＳｉｔ近傍のシンク、図２８の例では、シンクＳｉ２を分岐点を求めるためのペアシンクとする。
【００７８】
次いで、制御部１０は、クロックソースＳｏに代えて、疑似ソースＳｏｐを決定する。例えば、制御部１０は、疑似ソースＳｏｐとして、ターゲットシンクＳｉｔに最も近い位置の分岐点、図２８では分岐点Ｔ２を決定する。
【００７９】
以後の処理は第１の実施の形態と同様である。即ち、図２６のステップＳ１１において、ペアシンクＳｉ２とターゲットシンクＳｉｔとの間のマンハッタン距離が求められ、マンハッタン距離が等距離となる点の軌跡が求められる（ステップＳ１２）。
【００８０】
次に、ステップＳ１３において、疑似ソースＳｏｐ（分岐点Ｔ２）とペアシンクＳｉ２とを対角の頂点とする長方形で与えられるパス設定ブロック領域内で、疑似ソースＳｏｐから最も離れた位置の等距離点を分岐点（図２８の分岐点Ｔ４）とする。次に、パス長がマンハッタン距離となるように、分岐点Ｔ４からターゲットシンクＳｉｔまでのパスＰｔ４を決定する。
【００８１】
なお、次に分岐点を決定する処理を行う必要がない場合には、ステップＳ１４におけるパス設定ブロック領域の設定処理は不要である。
【００８２】
図２７と図２８の比較から明らかなように、本実施の形態においては、第１の実施の形態に比べて、共有パスのパス長は長くなる。
【００８３】
このように本実施の形態においては、分岐点を求めるためのシンクの組をターゲットシンクの位置に応じて決定すると共に、分岐点を決定するためのパス設定ブロック領域の一端となるクロックソースに代えて分岐点の位置の疑似ソースを用いることによって、共有パスのパス長を長くすることができるという利点がある。
【００８４】
なお、上記各実施の形態のクロックツリー設計装置の機能は、制御部をＣＰＵによって構成し、ＣＰＵによってソフトウェアプログラムを実行することで実現可能である。例えば、パス設定ブロック領域の設定、マンハッタン距離の算出、等距離点集合の算出、分岐点の設定及びパス設定は、コンピュータを用いたソフトウェアプログラムによって実現可能である。
【符号の説明】
【００８５】
１…クロックツリー設計装置、１０…制御部、１１…シンク及び配線情報メモリ、１２…処理順情報メモリ、１３…パス設定ブロック領域情報メモリ、１４…分岐点情報メモリ、１５…パス設定情報メモリ、２１…パス設定ブロック設定部、２２…マンハッタン距離算出部、２３…等距離点集合算出部、２４…分岐点設定部、２５…パス設定部。
【技術分野】
【０００１】
本発明の実施形態は、クロックツリー設計装置及びクロックツリー設計方法に関する
【背景技術】
【０００２】
従来、ＬＳＩにおけるクロック分配方式として、クロックツリー方式がある。クロックツリーのレイアウト設計においては、クロックレイテンシ、バッファ数、クロックスキュー等を考慮した設計を行う必要がある。
【０００３】
Ｈツリー方式は、クロックの供給先であるシンク（ｓｉｎｋ）同士の重心にクロックパス（以下、単にパスともいう）を設定するものである。Ｈツリー方式は、各シンクまでのパスとして共有パスが多く用いられるのでバッファ数削減、ＯＣＶマージンの削減の観点から優れている。また、Ｈツリー方式は、各シンクへのパス長が等しくなることが多く、クロックスキューの観点からも優れている。
【０００４】
また、クロックレイテンシの観点からは、クロックソースから最も遠い距離のシンク（以下、最遠シンクという）までのクロックパス長は短い方がよい。しかしながら、Ｈツリー方式では、クロックパスは必ず２シンク間の重心を通るように設定されることから、クロックレイテンシが比較的大きくなることがある。
【０００５】
クロックレイテンシを最小にするようにクロックツリーを設計する方法として、クロックソースから最遠シンクまでの距離がマンハッタン距離となることのみを条件に、クロックソースと最遠シンク間にクロックパスを設定する方法が考えられる。
【０００６】
しかしながら、この方法では、クロックソースと最遠シンク以外のシンクとの間のパスの最適化が困難であり、バッファ数、ＯＣＶ（on-chip variation）マージン及びスキューが増大する可能性がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−７５００号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態は、クロックレイテンシを最小にする条件下において、共有パスのパス長を比較的長くして、クロックスキュー及びバッファ数を比較的少なくすることができるクロックツリー設計装置及びクロックツリー設計方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
実施形態のクロックツリー設計装置は、クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部とを具備する。
【図面の簡単な説明】
【００１０】
【図１】本発明の第１の実施の形態に係るクロックツリー設計装置を示すブロック図。
【図２】クロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図。
【図３】クロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図。
【図４】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図５】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図６】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図７】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図８】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図９】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１０】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１１】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１２】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１３】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１４】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１５】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１６】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１７】等距離となる点の軌跡を求める方法を説明するための説明図。
【図１８】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図１９】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２０】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２１】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２２】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２３】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２４】本実施の形態におけるクロックツリー設計方法を説明するための説明図。
【図２５】クロックツリー設計の全体の動作を示すフローチャート。
【図２６】図２５中の分岐点及びパス設定フローを示すフローチャート。
【図２７】本発明の第２の実施の形態を示す説明図。
【図２８】本発明の第２の実施の形態を示す説明図。
【図２９】本発明の第２の実施の形態を示すフローチャート。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。
【００１２】
（第１の実施の形態）
図１は本発明の第１の実施の形態に係るクロックツリー設計装置を示すブロック図である。
【００１３】
先ず、図２及び図２４を参照して、本実施の形態におけるクロックツリー設計方法について説明する。図２及び図３はクロックレイテンシ、バッファ数、クロックスキューとクロックツリーとの関係を示す説明図である。なお、図２ではクロックが供給されるフリップフロップＦの信号ピンをシンクとする。
【００１４】
図２（ａ），（ｂ）はクロックレイテンシとパスとの関係を示している。図２（ａ），（ｂ）は夫々クロックソースＳｏとシンクＳｉ１との間に設定されたクロックパスＰ１，Ｐ２を示している。パスＰ１のパス長はマンハッタン距離に等しく、パスＰ２はパスの一部が平行な部分を有しているので、マンハッタン距離よりも長い。クロックレイテンシの観点からは、図２（ａ）のように最遠シンクまでのパスのパス長が短いことが望ましい。
【００１５】
図２（ｃ），（ｄ）はバッファ数及びＯＣＶマージンとパスとの関係を示している。図２（ｃ），（ｄ）はクロックソースＳｏとシンクＳｉ２，Ｓｉ３との間に設定されたクロックパスＰ３〜Ｐ７を示している。図２（ｃ）においては、クロックソースＳｏからシンクＳｉ２，Ｓｉ３までのパスＰ３〜Ｐ５のうち、パスＰ３は共有パスである。図２（ｄ）においては、クロックソースＳｏからシンクＳｉ２，Ｓｉ３までのパスＰ６，Ｐ７は独立したパスであり、共有パスは存在しない。バッファ数及びＯＣＶマージンの観点からは、図２（ｃ）のように共有パスを設けた方が望ましい。
【００１６】
図２（ｅ），（ｆ）はクロックスキューとパスとの関係を示している。図２（ｅ），（ｆ）はクロックソースＳｏとシンクＳｉ４，Ｓｉ５との間に設定されたクロックパスＰ８〜Ｐ１０を示している。図２（ｅ），（ｆ）はクロックスキューが生じていない例を示しており、図２（ｅ）ではパスＰ８，Ｐ９のパス長を同一にすることによりクロックスキューが発生しないようにしているのに対し、図２（ｆ）ではパスＰ８上のバッファ数よりもパスＰ１０上のバッファ数を増やすことで、クロックスキューが発生しないようにしている。
【００１７】
クロックスキューを小さくするためにバッファを挿入する手法を採用した場合には、微細プロセスでの遅延ばらつきや電源電圧の低下の影響を受け、チップのコンディションによっては、バッファ挿入によってかえってスキューが大きくなってしまうことがある。従って、クロックスキューの観点からは、図２（ｅ）のように各シンクまでの距離は等しい方がよい。
【００１８】
このように、クロックレイテンシの観点からは、最遠シンクまでのパスのパス長が短いことが望ましく、バッファ数及びＯＣＶマージンの観点からは、長い共有パスを設けた方が望ましく、クロックスキューの観点からは、各シンクまでのパス長を等しくした方が望ましい。
【００１９】
図３は複数の四角の枠によって各シンクＳｉを示しており、クロックソースＳｏと最遠シンクＳｉｆとの間のパスを太線によって示している。図３（ａ）はＨツリー方式を示しており、各シンクＳｉを結ぶ線によってパスＰを示している。各パスＰは、２つのシンク間の重心を通るように設計されていることから、最遠シンクＳｉｆまでのパスＰｍには平行な部分が形成されて、マンハッタン距離よりも長いパス長を有する。即ち、Ｈツリー方式では、最遠シンクまでのパス長が長くなり、クロックレイテンシが大きくなることがあるという欠点がある。
【００２０】
一方、図３（ｂ）は、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長がマンハッタン距離となるようにパスを設定する例を示している。太線の四角の枠内を通り平行な部分が形成されなければ、どのようなパスを採用しても、最遠シンクＳｉｆまでのパス長を最短にすることができる。
【００２１】
しかしながら、図３（ｂ）の方法では、他のシンクに対するパスを最適化することはできず、バッファ数やクロックスキュー等の観点では不利である。
【００２２】
そこで、本実施の形態においては、図４〜図２４に示すクロックツリー設計方法を採用することにより、クロックレイテンシを最小にしつつ、各シンク間の共有パスを増大させ、各シンク間のパス長を等しくする。これにより、クロックレイテンシ、バッファ数、クロックスキュー及びＯＣＶマージン等を最適化したクロックツリーの生成を可能にする。
【００２３】
本実施の形態においては、クロックレイテンシを最小にするために、最遠シンクＳｉｆまでのパスを優先するようにパスの決定を行う。また、共有パスを増やすために、クロックソースからなるべく離れた位置までを共有パスを用い、共有パスの終端を分岐点として分岐点から各シンクまでのパスを形成する。分岐点から各シンクまでのパス同士を等しい長さに設定するように、分岐点の位置を決定する。
【００２４】
図４はクロックツリー設計対象の回路レイアウトの一例を示している。図５〜図２４は図４と同一の回路レイアウトを示している。図４乃至図２４において、塗りつぶした四角の枠はクロックソースを示し、白抜きの四角の枠は回路レイアウト内で同時にクロックを供給したい（クロックレイテンシを一致させる）シンクを示し、斜線を施した四角の枠は最遠シンクを示している。図４〜図２４の破線は回路上に配線可能な配線パターンの方向を示している。図４〜図２４の例では、水平及び垂直方向に所定の配線ピッチで、配線パターンを形成可能であることを示している。なお、図４〜図２４において決定したパスは太線にて示している。
【００２５】
先ず、クロックレイテンシを最小にするために、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長を最短、即ち、マンハッタン距離とするパスの候補を求める。クロックソースＳｏと最遠シンクＳｉｆとのパス長をマンハッタン距離とするパスは複数有る。図５はそのうちの３つのパスＰｆを太線にて示している。即ち、クロックソースＳｏ及び最遠シンクＳｉｆの位置を対角の頂点とする長方形で囲まれた領域（斜線部）Ｂ１内において、平行なパスを形成しないようにパスを設定すればよい。このように、斜線部の領域は、２点間のパス長をマンハッタン距離に設定可能なパスが存在する領域（以下、パス設定ブロック領域という）である。
【００２６】
いま、例えば、図６に示すように、１つのシンクを選択して、パスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆからのマンハッタン距離とターゲットシンクＳｉｔからのマンハッタン距離とが等距離となる点の軌跡ＴＡ１を求める。なお、図６以降の図ではこの点を白抜きの丸印によって示している。軌跡ＴＡ１の一部は、図７に示すように、パス設定ブロック領域Ｂ１内に存在している。
【００２７】
本実施の形態においては、図８に示すように、この等距離の点の軌跡ＴＡ１のうち、パス設定ブロック領域Ｂ１内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ１とする。本実施の形態においては、分岐点Ｔ１を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とし、クロックソースＳｏから分岐点Ｔ１までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ１までの共有パスの候補は、図９の斜線部に示すパス設定ブロック領域Ｂ２内に設定する。これにより、クロックソースＳｏから分岐点Ｔ１までのパスのパス長を、クロックソースＳｏと分岐点Ｔ１とを対角の頂点とする長方形により規程されるマンハッタン距離にすることができ、クロックソースＳｏから分岐点Ｔ１までのパスのパス長を最短にすることができる。
【００２８】
図１０に示すように、分岐点Ｔ１から最遠シンクＳｉｆまでのパスＰｆと分岐点Ｔ１からターゲットシンクＳｉｔまでのパスＰｔ１とを決定する。これらのパスＰｆ，Ｐｔ１のパス長をマンハッタン距離に設定することで、パスＰｆ，Ｐｔ１のパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ１までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００２９】
図１１乃至図１７は最遠シンクＳｉｆからのマンハッタン距離とターゲートシンクＳｉｔからのマンハッタン距離とが等距離となる点の軌跡を求める方法を説明するための説明図である。
【００３０】
図１１の網線は配線グリッドを示している。図１１のグリッド上の黒丸は、等距離点の軌跡を求めようとする２つのシンクの位置Ａ，Ｂを示している。先ず、図１２に示すように、位置Ａ，Ｂの中点の位置Ｃにおけるグリッド（黒丸）を求める。２点Ａ，Ｂ間の水平方向及び垂直方向のグリッド数が奇数個の場合には、中点の位置Ｃはグリッド上に位置しない。この場合には、例えば、中点の位置Ｃを半グリッド分移動させることで、中点の位置Ｃをグリッド上に位置させる。或いは、予め、各シンクの位置を、シンク同士の間に偶数個のグリッドが配置されるように設定する等の方法を採用する。
【００３１】
次に、配線グリッドを中点Ｃのグリッドを原点とする直交座標と考え、線分ＡＢが通過しない象限上に、中点Ｃのグリッドからｘ，ｙ方向の両方向に位置が変化するようにグリッド上に白抜きで示す点（以下、仮の中点という）をとる。この仮の中点は、点Ａからの距離と点Ｂからの距離とが等距離（マンハッタン距離）となる点を求めるためのものであり、点Ａ，Ｂからの各距離が、ｘ方向について小さくなった場合にはｙ方向について大きくなるようにし、ｘ方向について大きくなった場合にはｙ方向について小さくなるようにしたものである。
【００３２】
しかし、図１３に示すように、点Ａ，Ｂを対角の頂点とする長方形の領域Ｒ１の領域外にとった仮の中点は、点Ａ，Ｂからのマンハッタン距離が相互に異なる。点Ａ，Ｂからのマンハッタン距離が等しくなる中点は、領域Ｒ１端部の仮の中点からｘ方向又はｙ方向に延出したグリッド上に存在する。
【００３３】
図１４はこうして求めた等距離となる点の軌跡ＴＡを示している。なお、中点がｘ，ｙ方向のいずれに延出したグリッド上に存在するかは、領域Ｒ１のｘ方向のサイズとｙ方向のサイズとに依存し、図１４のようにｙ方向のサイズがｘ方向よりも大きい場合には、ｘ方向上に中点が存在し、図１５に示すように、ｙ方向のサイズがｘ方向よりも小さい場合には、ｙ方向上に中点が存在する。
【００３４】
また、図１６に示すように、領域Ｒ１のｘ，ｙ方向のサイズが等しい場合には、仮の中点が中点となる。また、図１７に示すように、２点Ａ，Ｂのｘ座標又はｙ座標の一方が同一ならば、直線ＡＢの垂直２等分線上のグリッドが等距離となる点の軌跡である。
【００３５】
以後、同様の手法によって、各シンクまでのパスを決定する。
【００３６】
例えば、図１８に示すように、１つのシンクを選択してパスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆとターゲットシンクＳｉｔとの間で、マンハッタン距離が等距離となる点の軌跡ＴＡ２を求める。軌跡ＴＡ２の一部は、図１８に示すように、パス設定ブロック領域Ｂ２内に存在している。
【００３７】
次に、図１９に示すように、この等距離の点の軌跡ＴＡ２のうち、パス設定ブロック領域Ｂ２内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ２とする。この分岐点Ｔ２を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とする。クロックソースＳｏから分岐点Ｔ２までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ２までの共有パスの候補は、図１９の斜線部に示すパス設定ブロック領域Ｂ３内に設定する。これにより、クロックソースＳｏから分岐点Ｔ２までのパスのパス長を最短にすることができる。
【００３８】
図２０に示すように、パス長がマンハッタン距離となるように、分岐点Ｔ２からターゲットシンクＳｉｔまでのパスＰｔ２を決定する。なお、分岐点Ｔ２と分岐点Ｔ１との間のパスは、図２０に示すように、パス設定ブロック領域Ｂ２中の一部の領域Ｂ２’に設定される。
【００３９】
分岐点Ｔ２から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでの各パスのパス長をマンハッタン距離に設定することで、これらのパスのパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ２までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００４０】
同様にして、次に設定するターゲットシンクＳｉｔまでのパスを決定する。
【００４１】
図２１に示すように、残りの１つのシンクをパスを設定するターゲットシンクＳｉｔとする。最遠シンクＳｉｆとターゲットシンクＳｉｔとの間で、マンハッタン距離が等距離となる点の軌跡ＴＡ３を求める。軌跡ＴＡ３の一部は、図２１に示すように、パス設定ブロック領域Ｂ３内に存在している。
【００４２】
次に、図２２に示すように、この等距離の点の軌跡ＴＡ３のうち、パス設定ブロック領域Ｂ３内でクロックソースＳｏからの距離が最も遠い位置の点（斜線）を分岐点Ｔ３とする。この分岐点Ｔ３を、クロックソースＳｏから最遠シンクＳｉｆまでのパスと、クロックソースＳｏからターゲットシンクＳｉｔまでのパスとが分岐する点とする。クロックソースＳｏから分岐点Ｔ３までのパスは、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスとする。クロックソースＳｏから分岐点Ｔ２までの共有パスの候補は、図２２の斜線部に示すパス設定ブロック領域Ｂ４内に設定する。これにより、クロックソースＳｏから分岐点Ｔ３までのパスのパス長を最短にすることができる。
【００４３】
図２３に示すように、パス長がマンハッタン距離となるように、分岐点Ｔ３からターゲットシンクＳｉｔまでのパスＰｔ３を決定する。なお、分岐点Ｔ３と分岐点Ｔ２との間のパスは、図２３に示すように、パス設定ブロック領域Ｂ３中の一部の領域Ｂ３’に設定される。
【００４４】
分岐点Ｔ３から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでの各パスのパス長をマンハッタン距離に設定することで、これらのパスのパス長は最短で且つ同一となる。クロックソースＳｏから分岐点Ｔ３までは共有パスを用いるので、クロックソースＳｏから最遠シンクＳｉｆまでのパスとクロックソースＳｏからターゲットシンクＳｉｔまでのパスとは、最短で且つ同一長であり、しかも共有パスの長さは最長である。
【００４５】
最後に、パス設定ブロック領域Ｂ４内でパス長がマンハッタン距離となるようにクロックソースＳｏから分岐点Ｔ３までのパスを設定する。例えば、図２４では、パス設定ブロック領域Ｂ４の一部の領域Ｂ４’に共有パスＰｃを設定した例を示している。
【００４６】
結局、図４〜図２４の例は、最遠シンクＳｉｆを含む全てのシンクＳｉにおいて、クロックソースＳｏからのパスは、最短で且つ等距離であり、比較的長い共有パスが設定されている。
【００４７】
図１において、クロックツリー設計装置１には、各種情報を記憶するメモリ１１〜１５が設けられている。シンク及び配線情報メモリ１１は、クロックツリー設計対象の回路レイアウト中に設けられるクロックソースＳｏ、各シンクＳｉ、最遠シンクＳｉｆ及び配線に関する情報（以下、シンク及び配線情報という）が記憶されている。例えば、シンク及び配線情報としては、クロックソースＳｏ、各シンクＳｉ、最遠シンクＳｉｆ及び配線の位置に関する情報や、配線グリッドの単位の情報等が含まれる。なお、本実施の形態においては、クロックソースＳｏ、シンクＳｉ及び最遠シンクＳｉｆは、クロックの入出力端を構成するピンを示しているものとする。また、ピンのサイズや配線の幅等は無視できるものとする。
【００４８】
処理順情報メモリ１２には、各シンクＳｉのうちのいずれのシンクをターゲットシンクＳｉｔとするかを順次示す情報（処理順情報）を記憶する。図４乃至図２４の例は一例であり、ターゲットシンクＳｉｔとする順番が異なれば、設計されるクロックツリーも異なる。本実施の形態においては、処理順は既に決定されており、処理順情報を読出すことで、決定された処理順で順次処理が行われるものとして説明する。
【００４９】
なお、処理順は、クロックツリーの生成に大きな影響を与える。処理順の決定には多く処理が必要であると予想される。そこで、例えば、いくつかの処理順を決定しておき、上述した図４〜図２４の手法に従ったクロックツリーの生成結果から、最適なクロックツリーを選択するようにしてもよい。
【００５０】
なお、より長い共有パスを設定するためには、クロックソースＳｏと最遠シンクＳｉｆとを対角の頂点とする長方形で規定されるパス設定ブロック領域の外にあるシンクを内にあるシンクよりも先に処理した方がよい。
【００５１】
制御部１０はメモリ１１〜１５の書込み及び読出しを制御すると共に、各部を制御してクロックツリーを設計する。
【００５２】
パス設定ブロック設定部２１は、制御部１０を介してメモリ１１からのシンク及び配線情報が与えられて、パス設定ブロック領域を設定し、パス設定ブロック領域情報を出力する。このパス設定ブロック領域情報は、制御部１０を介してパス設定ブロック領域情報メモリ１３に与えられる。パス設定ブロック領域情報メモリ１３は、２点間のパス設定ブロック領域に関する情報を記憶する。
【００５３】
また、分岐点情報メモリ１４は、後述する分岐点設定部２４から制御部１０を介して分岐点情報が与えられて記憶する。パス設定ブロック設定部２１は、制御部１０を介して分岐点情報も与えられ、クロックソースＳｏと分岐点との間のパス設定ブロック領域も設定して、パス設定ブロック領域情報として出力し、記憶させるようになっている。
【００５４】
制御部１０は、処理順情報メモリ１２からの処理順情報に基づいて、シンク及び配線情報メモリ１１から、最遠シンクＳｉｆ及びターゲットシンクＳｉｔに関してシンク及び配線情報をマンハッタン距離算出部２２に与えることができる。マンハッタン距離算出部２２は、制御部１０によって指定された２点のマンハッタン距離を算出する。マンハッタン距離算出部２２の算出結果は制御部１０を介して等距離点集合算出部２３に供給され、等距離点集合算出部２３は、２点からのマンハッタン距離が等しくなる、等距離点の集合を求める。なお、等距離点の集合は、厳密には配線上に存在しないこともある。そこで、等距離点集合算出部２３は、配線に関する情報を用いることで、例えば、最も近い配線上に等距離点が存在するように補正した等距離点集合を求める。
【００５５】
分岐点設定部２４は、制御部１０を介して等距離点集合の情報、パス設定ブロック領域情報、シンク及び配線情報が与えられて、パス設定ブロック領域内において、クロックソースＳｏから最も遠い距離に位置する分岐点を求める。分岐点設定部２４により設定された分岐点の情報は、分岐点情報として分岐点情報メモリ１４に与えられて記憶される。
【００５６】
パス設定部２５は、シンク及び配線情報、分岐点情報、パス設定ブロック領域情報が与えられて、分岐点からターゲットシンクＳｉｔ及び最遠シンクＳｉｆまでのパス及びソースＳｏから分岐点までのパスを設定する。パス設定部２５によって設定されたクロックパスに関する情報は、パス設定情報メモリ１５に与えられる。こうして、パス設定情報メモリ１５にクロックツリー設計によって設計されたクロックツリーに関するパス設定情報が記憶される。
【００５７】
なお、図１のクロックツリー設計装置は、ＣＰＵ、メモリ及び入出力装置を備えたコンピュータによって実現可能である。
【００５８】
次に、このように構成された実施の形態の動作について図２５及び図２６を参照して説明する。図２５はクロックツリー設計の全体の動作を示すフローチャートであり、図２６は図２５中の分岐点及びパス設定フローを示すフローチャートである。
【００５９】
図２５のステップＳ１において、制御部１０はメモリ１１，１２からシンク及び配線情報と処理順情報とを読み出す。制御部１０は、ステップＳ２において、処理順情報に基づいてターゲットシンクＳｉｔを決定する。次いで、制御部１０は、各部を制御して、最遠シンクＳｉｆとターゲットシンクＳｉｔとの共有パスの分岐点を決定して、分岐点から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでのパスを決定する（ステップＳ３）。
【００６０】
制御部１０は、ステップＳ４において、全てのシンクＳｉについてパスの決定を行ったか否かを判定し、行っていない場合には、処理をステップＳ２に戻して、分岐点及びパスの設定処理を繰り返す。
【００６１】
制御部１０は、分岐点を決定するために、図２６のステップＳ１１において、マンハッタン距離算出部２２によって、最遠シンクＳｉｆとターゲットシンクＳｉｔとの間のマンハッタン距離を算出させる。等距離点集合算出部２３は、制御部１０に制御されて、等距離点の軌跡を算出する（ステップＳ１２）。
【００６２】
分岐点設定部２４は、パス設定ブロック領域内で、クロックソースＳｏからの距離が最も遠い等距離点を分岐点に設定する（ステップＳ１３）。なお、最初のターゲットシンクＳｉｔに対する処理時には、パス設定ブロック設定部２１によって、クロックソースＳｏと最遠シンクＳｉｆとを夫々対角の頂点とする長方形がパス設定ブロック領域として設定されている。
【００６３】
ステップＳ１３の処理によって、例えば、図８，図１９，図２２の各最遠シンクＳｉｆとターゲットシンクＳｉｔとについて分岐点Ｔ１〜Ｔ３が決定される。
【００６４】
次のステップＳ１４では、パス設定ブロック設定部２１によって、クロックソースＳｏとステップＳ１４で求められた分岐点とを対角の頂点とする長方形を新たなパス設定ブロック領域として設定する。
【００６５】
パス設定部２５は、ステップＳ１５において、ステップＳ１４で求めた分岐点から最遠シンクＳｉｆ及びターゲットシンクＳｉｔまでのパスを決定する。
【００６６】
パス設定部２５は、分岐点から全てのターゲットシンクＳｉｔまでのパスを決定すると、最後に、クロックソースＳｏから最後に求めた分岐点までのパスを決定する。
【００６７】
なお、次に分岐点を決定する処理を行う必要がない場合には、ステップＳ１４におけるパス設定ブロック領域の設定処理は不要である。
【００６８】
このように本実施の形態においては、クロックレイテンシを最小にする条件化において、最遠シンクとターゲットシンクとの間の等距離点でクロックソースから最も遠い点を分岐点に決定し、分岐点を通過するパスを決定する。クロックソースから分岐点までは共有パスとなり、共有パスを増大させることができる。また、分岐点からのパスのパス長は等しく、レイテンシを最小にしながら、共有パスを増大させ、各シンクまでのパス長を等しくすることができる。これにより、クロックレイテンシを最小にしながら、共有パスのパス長を最長にし、クロックスキュー及びバッファ数を最小にすることができる。パスの配線長を等長にすることができるので、ばらつきに対するスキューの増大を抑制することが可能となる。
【００６９】
（第２の実施の形態）
図２７及び図２８は本発明の第２の実施の形態を示す説明図である。本実施の形態のハードウェア構成は図１の実施の形態と同様である。本実施の形態においては、分岐点及びパスの決定方法のみが第１の実施の形態と異なる。
【００７０】
図２７は図２４の回路レイアウト上の３つのシンク（Ｓｉ１〜Ｓｉ３）の外にもう１つのシンクＳｉ４が存在する場合の例を示している。シンクＳｉ４は、シンクＳｉ３の近傍に配置されており、図２７の例は、このシンクＳｉ４をターゲットシンクＳｉｔに設定し、このターゲットシンクＳｉｔについて、第１の実施の形態において説明した手法によって、分岐点及びパスを決定した例を示している。図２７の例では、ターゲットシンクＳｉ４には、クロックソースＳｏからパスＰｃ、分岐点Ｔ３及びパスＰｔ４’を介してクロックが供給される。
【００７１】
即ち、第１の実施の形態においては、最遠シンクＳｉｆとターゲットシンクＳｉｔとを、分岐点の設定に用いるシンクの組と考えて、このシンクの組における等距離点上に分岐点を決定した。しかしながら、図２７の例では、シンクＳｉ４はシンクＳｉ３の近傍に配置されているにも拘わらず、分岐点がシンクＳｉ２，Ｓｉ４から比較的離間しており、共有パスは比較的短い。
【００７２】
そこで、本実施の形態においては、パスが既に決定された任意のシンクを、ターゲットシンクＳｉｔと共に分岐点を求めるためのシンク（以下、ペアシンクという）とすると共に、クロックソースＳｏに代えて分岐点の１つを擬似的にクロックソース（以下、疑似ソースという）とすることで、共有パスを長くする分岐点を決定するようになっている。
【００７３】
第１の実施の形態に従ってパスが決定されたシンクＳｉとクロックソースＳｏとを結ぶパスのパス長は、クロックソースＳｏと最遠シンクＳｉｆまでのパスのパス長と同一である。従って、クロックレイテンシを一致させるシンクの組として、最遠シンクＳｉｆに代えてパスが決定されたシンクをペアシンクとして用いることができる。
【００７４】
図２８にこの例を示しており、最遠シンクＳｉｆに代えて、ターゲットシンクＳｉｔ近傍のシンクＳｉ２をターゲットシンクＳｉｔへのパスの分岐点を求めるための組のペアシンクとする。また、ターゲットシンクＳｉｔに近い距離の分岐点Ｔ２を疑似ソースＳｏｐとする。
【００７５】
次にこのように構成された実施の形態の動作について図２９のフローチャートを参照して説明する。図２９において図２５と同一の手順には同一符号を付して説明を省略する。
【００７６】
本実施の形態においては、ステップＳ２の次に、ステップＳ２１及びステップＳ２２の処理が追加された点が図２５のフローと異なるのみである。分岐点及びパス設定処理は、図２６のフローに従って行われることは、第１の実施の形態と同様である。
【００７７】
本実施の形態においては、ステップＳ２において、ターゲットが決定されると、次のステップＳ２１において、制御部１０は、ターゲットシンクＳｉｔへの分岐点を求めるためのシンクの組を決定する。第１の実施の形態においては、常に最遠シンクＳｉｆを用いた。これに対し、本実施の形態においては、制御部１０は、ターゲットシンクＳｉｔ近傍のシンク、図２８の例では、シンクＳｉ２を分岐点を求めるためのペアシンクとする。
【００７８】
次いで、制御部１０は、クロックソースＳｏに代えて、疑似ソースＳｏｐを決定する。例えば、制御部１０は、疑似ソースＳｏｐとして、ターゲットシンクＳｉｔに最も近い位置の分岐点、図２８では分岐点Ｔ２を決定する。
【００７９】
以後の処理は第１の実施の形態と同様である。即ち、図２６のステップＳ１１において、ペアシンクＳｉ２とターゲットシンクＳｉｔとの間のマンハッタン距離が求められ、マンハッタン距離が等距離となる点の軌跡が求められる（ステップＳ１２）。
【００８０】
次に、ステップＳ１３において、疑似ソースＳｏｐ（分岐点Ｔ２）とペアシンクＳｉ２とを対角の頂点とする長方形で与えられるパス設定ブロック領域内で、疑似ソースＳｏｐから最も離れた位置の等距離点を分岐点（図２８の分岐点Ｔ４）とする。次に、パス長がマンハッタン距離となるように、分岐点Ｔ４からターゲットシンクＳｉｔまでのパスＰｔ４を決定する。
【００８１】
なお、次に分岐点を決定する処理を行う必要がない場合には、ステップＳ１４におけるパス設定ブロック領域の設定処理は不要である。
【００８２】
図２７と図２８の比較から明らかなように、本実施の形態においては、第１の実施の形態に比べて、共有パスのパス長は長くなる。
【００８３】
このように本実施の形態においては、分岐点を求めるためのシンクの組をターゲットシンクの位置に応じて決定すると共に、分岐点を決定するためのパス設定ブロック領域の一端となるクロックソースに代えて分岐点の位置の疑似ソースを用いることによって、共有パスのパス長を長くすることができるという利点がある。
【００８４】
なお、上記各実施の形態のクロックツリー設計装置の機能は、制御部をＣＰＵによって構成し、ＣＰＵによってソフトウェアプログラムを実行することで実現可能である。例えば、パス設定ブロック領域の設定、マンハッタン距離の算出、等距離点集合の算出、分岐点の設定及びパス設定は、コンピュータを用いたソフトウェアプログラムによって実現可能である。
【符号の説明】
【００８５】
１…クロックツリー設計装置、１０…制御部、１１…シンク及び配線情報メモリ、１２…処理順情報メモリ、１３…パス設定ブロック領域情報メモリ、１４…分岐点情報メモリ、１５…パス設定情報メモリ、２１…パス設定ブロック設定部、２２…マンハッタン距離算出部、２３…等距離点集合算出部、２４…分岐点設定部、２５…パス設定部。
【特許請求の範囲】
【請求項１】
クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、
クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、
前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、
前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部と
を具備することを特徴とするクロックツリー設計装置。
【請求項２】
前記パス設定ブロック設定部は、前記ターゲットシンクが切換る毎に、前記クロックソースと前記分岐点とを対角の頂点とする長方形の領域を前記パス設定ブロック領域に設定する
ことを特徴とする請求項１に記載のクロックツリー設計装置。
【請求項３】
前記等距離点集合算出部は、前記パス設定部によってクロックパスが設定されたシンクをペアシンクとし、前記最遠シンクに代えて前記ペアシンクからのマンハッタン距離と前記ターゲットシンクからのマンハッタン距離とが等しくなる前記等距離点の集合を求める
ことを特徴とする請求項１に記載のクロックツリー設計装置。
【請求項４】
クロックツリー設計装置を用いて、
クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求め、
クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定し、
前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とし、
前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定する
ことを特徴とするクロックツリー設計方法。
【請求項５】
前記クロックツリー設計装置を用いて、
前記パス設定ブロック領域を、前記ターゲットシンクが切換る毎に、前記クロックソースと前記分岐点とを対角の頂点とする長方形の領域に設定する
ことを特徴とする請求項４に記載のクロックツリー設計方法。
【請求項１】
クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求める等距離点集合算出部と、
クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定するパス設定ブロック設定部と、
前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とする分岐点設定部と、
前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定するパス設定部と
を具備することを特徴とするクロックツリー設計装置。
【請求項２】
前記パス設定ブロック設定部は、前記ターゲットシンクが切換る毎に、前記クロックソースと前記分岐点とを対角の頂点とする長方形の領域を前記パス設定ブロック領域に設定する
ことを特徴とする請求項１に記載のクロックツリー設計装置。
【請求項３】
前記等距離点集合算出部は、前記パス設定部によってクロックパスが設定されたシンクをペアシンクとし、前記最遠シンクに代えて前記ペアシンクからのマンハッタン距離と前記ターゲットシンクからのマンハッタン距離とが等しくなる前記等距離点の集合を求める
ことを特徴とする請求項１に記載のクロックツリー設計装置。
【請求項４】
クロックツリー設計装置を用いて、
クロックレイテンシを一致させるべき一群のシンクから順次選択されるターゲットシンクからのマンハッタン距離と前記一群のシンクのうちクロックソースから最も遠い距離に位置する最遠シンクからのマンハッタン距離とが等しくなる等距離点の集合を求め、
クロックパスが存在しうる領域であって、前記クロックパスのパス長を最短のマンハッタン距離にするパス設定ブロック領域を設定し、
前記等距離点の集合のうち前記パス設定ブロック領域内で前記クロックソースから最も遠い距離の点を分岐点とし、
前記クロックソースから前記分岐点までの前記パス設定ブロック領域内に前記ターゲットシンクと前記最遠シンクとの共有パスを設定すると共に、前記分岐点から前記ターゲットシンクまでのクロックパス及び前記分岐点から前記最遠シンクまでのクロックパスをパス長が最短のマンハッタン距離となるように設定する
ことを特徴とするクロックツリー設計方法。
【請求項５】
前記クロックツリー設計装置を用いて、
前記パス設定ブロック領域を、前記ターゲットシンクが切換る毎に、前記クロックソースと前記分岐点とを対角の頂点とする長方形の領域に設定する
ことを特徴とする請求項４に記載のクロックツリー設計方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１２−１９４８８８（Ｐ２０１２−１９４８８８Ａ）
【公開日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願番号】特願２０１１−５９４５４（Ｐ２０１１−５９４５４）
【出願日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願日】平成２３年３月１７日（２０１１．３．１７）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]