Memoirs of the Faculty of Science
Kochi University (Information Science)
Vol.29 (2008), No.8

二分木と三分木のクロックツリーの回路規模に関する研究
A Study of Scales of Binary and Triplet Clock Tree Circuits
下川 遥香

豊永 昌彦

Haruka Shimokawa

Masahiko Toyonaga

高知大学理学部数理情報科学科
Faculty of Science, Kochi University
あらましップに遅延差なく供給するクロック回路を前提と高度情報化社会の推進によって，コア LSI は，大している．

規模化と高速化を要求されている．しかし LSI のク

一方，同期式回路ではクロック回路はほぼ常時動

ロック周波数の高まりは消費電力を増大させてし作し続ける．そのため，クロック回路で消費されるまうため，今後の LSI 設計ではより小規模なクロッ電力も多く，LSI 全体の半分を占めているといわれク回路の生成が重要となる．ている．

クロック回路規模は配線と素子の総和で決まる．

ところでクロック回路の設計で，遅延差無く各フ従って回路規模を縮小するには配線長・分木点数・リップフロップに信号を供給するためには配線長段数を削減しなければならい．の均等化が必須でなる．そのため，従来のクロック

著者は本論文においてクロック分木数を増やし設計法では，信号遅延の調整を容易にするため，２て従来の二分木と二分木以上の分木数をもつクロ

つのフリップフロップ端子毎に均等配線を構成す

ック回路の規模の面からの優位性について定量的る二分木のクロック構造が使われてきた．ここで分な比較をおこなった．端子をランダムに配した簡単

木数とは，端子間の配線長を均等化して同時に複数なベンチマークデータで評価したところ，三分木がへ信号を送るための端子のまとまりの数である．

二分木に比べて規模を約 7％削減できた．三分木ク

著者は，クロック回路規模の削減方法の検討に際ロック回路により総量が減ると安価・小型化が期待して，これらの分木数に着目する．より多数の分木できる．

数による高次の木構造が有利と思われるためである．
そこで本論文では，まずクロック分木数について

1

はじめに二分木と二分木以上の分木の回路量を比較してみ近年の情報化の進歩に伴い，電子機器で使われるた． その結果，二分木より三分木が配線長と段数コア LSI の大規模化と高速化が市場から要求されで最大 20％程度削減できることがわかった．すなている．

わち，クロック回路の消費電力の全回路に占め割合

これらの LSI の多くは演算速度をクロック信号を 50％としたとき，全消費電力 10％を削減するこで制御する同期式回路設計方式が採用されている．とに相当する．三分木によるクロック回路は，低消同期式回路設計は，クロック信号を全フリップフロ費電力を目指す LSI において有力であることがわ
2かった．

等化した回路がつくるものである． クロック木の以下本論文の構成は，2 章でクロックについて分分木点の素子としてはバッファ回路（信号を強める木数と段数の関係について説明をおこなう．3 章は， 回路）が用いられる．なお，スキューとはクロック
2 分木，3 分木について生成アルゴリズムの説明を

到達時間の差のことを指す． グリッド網方式より行う．4 章では，2 分木と 3 分木のクロックの配線消費電力は少なくなるが，回路規模が増大すると段長，段数の比較を 100x100〜400x400 の配線領域に数が増え，調整する配線長も巨大化してしまう。[4]端子 50〜400 個ランダムに配置した回路を作成して実験をおこなった結果と考察を紹介する．5 章で，本論文では，ゼロスキュークロック方式，すなわち分木により信号遅延を均等化する回路について本論文をまとめる．

その削減方法を検討する．

2クロック構造
2.2 ｎ分木のクロック構造

2.1 クロックとは枝をｎ本ずつとりまとめて構成した木をｎ分木

クロックは信号処理を正しくおこなうためにタという．

イミングを合わせる周期的な信号である．
LSI では，演算回路の出力は，いったんフリップｎ分木を作るには，ｎ個の端子をグループ化してフロップに記憶され，クロック信号のタイミングで分木点で取りまとめ，再度分木点を端子とみなして次の演算入力へと送られる． これにより，処理結ｎ個の端子をくり返しグループ化して作ることが果を正しく次の処理へ伝えることができる．この回できる．
図を使って，ｎ＝２の場合の木構成の手順を説明

路方式を同期設計方式と呼び，デジタル信号処理のする．図 1(a)は，ランダムに置かれた 12 個のフリ回路で主流となっている．

ップフロップの端子を□で示したものである．

クロック回路の構成としてクロック・グリッド網方式がある．これは，あらかじめチップ全体に広げ

まず，最近接している端子 n=２を図 1(a)の A おたグリッド網配線を巨大なトランジスタで強引によび B のペアとすると，これらを１組としてグル同時駆動させる方法である．しかし，その配線規模ープにまとめたものを C とする(図 1(b)参照）．
上位の端子 C は，A，B から均等な位置に置く．

や駆動するトランジスタが巨大となる為，消費電力このようにして，下位の全端子から最隣接するｎ個は多大となってしまう． [4]のグループをつくり，各グループに上位端子を生成

一般的なクロック回路は，信号源を根として，根しておく．

から葉（フリップフロップ端子）まで木構造（クロック木）により構成するゼロスキュークロックツ

上位端子群についても，同様に，ｎ個の最隣接端リー方式が使われている．信号の遅延は配線長の遅子をグループにしてさらに上位の端子を構成してれと素子の遅れで決まるので，クロック信号を全フいく．これを繰り返すことにより，もし上位の端子リップフロップ端子まで同時に伝えるため，クロッがたかだか 1 つになったなら，クロック木の構成をク木の根から各葉までの段数，枝の長さはすべて均出力して処理は終了する．

-2-

以上のようにして得られたｎ分木構造について，上位の端子について先ほどのグループ生成を繰

各グループ内の端子を直線で結んだものを図 1(c)り返すことで上位の端子がたかだか１つになったに示す．ｎ＝２で端子総数が 12 個である本例では，ところで，クロック木を出力して処理は終了する．

分木点数が 10 点となっている．

三分木構造では，分木点数が 6 点となっている．

AABDCB(a)端子群(a)三端子グループの生成ACBCA
B(b)ペアの生成(b)A三分木構造図 2．三分木のクロック生成例
B

このように，クロック木の分木点の数はｎによって変わる．すなわち，(1) より小さなｎのｎ分木では，分木点の数（素子数）が多くなる．
（先ほどの例では端子数 12 個につ(c)二分木構造

いて，二分木が 10 点，三分木が 6 点である）(2)ｎ分木で段数が少ないほど配線長が短い．
（先ほ図 1．二分木のクロック生成例

どの端子数 12 個で二分木では 4 段，三分木では 3

参考のためｎ＝３の三分木構造についても同様段であるが，各段を結ぶ配線数そのものが減っていに図で示しておく，最近接となる３端子 A,B,C のる）

グループ D を作り（図 2(a)）．次にグループ D において A，B，C から均等な位置に上位で扱うグルー

2.3 分木数ｎと分木点数の関係

プ D の端子を１つ作る．
-3-以上の例図で見られた傾向について，分木数ｎを・nS ≒ 255 のとき使って計算により見積もることができる．

分木点数

いま分木数をｎ，全フリップフロップ端子数を N100とすると，分木点数 S は，80
分木点数nN N
n n2．．．．
1 2 3 ..... N nn60
40
2001Nn221n．．．．
2.....

345
分木数．．．．

図 4．各分岐数に対する分木点数の値

1

図 3．分木点数生成

図 4 から計算上二分木から三分木にすることで，
図 3 のように分木点数 99 個が 49 個まで分木点数が 50％程度削N N, ... と１になるまで分木点数はn n2減される可能性が期待できることができる．一方，生成される．

それ以上の分木数の改善効果は，32%以下である．

式に表すと，
N1nS1nNN1n11n21n1n1121n21n...

2...

1n2.4 分木数ｎと段数の関係

log n N 1ｎと段数の関係も計算により見積もることができる．分木数をｎとし，端子数 N とすると，ｎ個log n Nずつの端子グループを生成するので，log n N 11n1Nn11nlog n N1n
図 5．端子グループ生成となり，実際に数値を入れて計算すると，分木数を2〜5 とし，端子数 N を 100 設定すると以下の結果

図 5 より段数は log n N となり，分木数ｎが大きいとなる．

ほど段数が削減されていることは，実際に数値を入・n2 のときS ≒ 99

れて計算して確かめられる．すなわち，分木数を 2・n3 のとき

S ≒ 49〜5 とし，端子数 N を 100 設定すると以下の結果と・n4 のとき

S ≒ 33なる．

-4-

端子２つの場合のダイヤモンド型探索について，
・ log 2 100 ≒ 6.7

途中の段階を含めて図 7 に 6 段階の図で示す．
まず，端子番号 1，2 を配線領域におく（図 7.1）．

・ log 3 100 ≒ 4.0

次に，周囲に１グリッドずつダイヤモンド型を広げ

・ log 4 100 ≒ 3.3る（図 7.2）．
これを繰り返していく（図 7.3，図 7.4）．

・ log 5 100 ≒ 2.9

両端子のダイヤモンド領域が接した様子を図 7.5 に示す．図 7.5 の段階で，１，２が最寄のペアである段数の変化ことがわかるのでペアリングする．さらに，両端子765
段 4数3210の中間点を上位の端子３として設定する．（図 7.6）
さらに上位の端子で繰り返すことで，二分木が生成できる．
2345分木数

図 6．各分岐数に対する段数の値

図 6 から計算上二分木から三分木にすることで，約7 段構成のクロック回路が，約 4 段構成のクロック回路まで段数が 40％程度削減される可能性が見ら* * * * * * * * * ******1** 1 1 1**
1**2*
*2 2 2**2** * * * * * * * * *(1) 端子の配置(2)周囲への探索* * * * * * * * * **1** 1 1 1*
* 1 1 1 1*
* 1 1 1**12*
*2 2 2 **2 2 2 2 2**
2 2 2 *
* * * * * * * * * *れる．しかし，三分木より上では，20％以下しか削減されない．

3* * * * * * * * * ********
1******2**** * * * * * * * * *二分木と三分木の生成法
前章でｎ分木における分木点数と段数でみられた傾向が実際のクロック回路でも成立するかどうかについて，実際に木を構成することにより実験的(3)探索の継続１に確認する．

* * * * * * * * * ** 1 1 1 1*
* 1 1 1 1 1*
* 1 1 1 1 1 12** 1 1 1 1 12 2 2 ** 1 1 1 12 2 2 2 ** 1 1 12 2 2 2 2 **12 2 2 2 2 2 **2 2 2 2 2 ** * * * * * * * * *3.1 端子周囲の探索（ダイヤモンド型探索）
二分木の生成のために，最隣接する端子ペアの探索を行う．まず，各端子から周囲に各端子の番号をラベル付けし，これを繰り返す（ダイヤモンド型の端子領域を広げる）．異なる端子のダイヤモンド領域が重複したものを最隣接ペアとして見つけ出す(5)2 端子の接触ことができる．
-5-* * * * * * * * * ** 1 1 1*
* 1 1 1 1*
* 1 1 1 1 1*
* 1 1 1 12** 1 1 12 2 2**
12 2 2 2 2*
*2 2 2 2 2 2*
*2 2 2 2 2*
* * * * * * * * * *(4)探索の継続２* * * * * * * * * ******1****
3****
2***
* * * * * * * * * *(6)上位端子の設定

図 7．ダイヤモンド探索

繰り返す．
なお端子数が奇数になる場合，端子をすべてペア以上のアルゴリズムは以下のとおりである．にすることができないが，その場合は，端子レベルを 1 あげることで，次の階層でペア生成する．

Binary Tree{if(map[x][y]!=BLANK){

3.2 三分木生成法

t2 = map[x][y];二分木とほぼ同様に三分木の生成方法について

if(wt[t].p==OFF&&wt[t2].p==OFF){maxwt++;

説明する．三分木では，3 つの端子についてダイヤchuoyer(t,t2,&wt[maxwt].x,&wt[maxwt].y);wt[maxwt].level=wt[t].level+1;

モンド探索し，ぶつかったものをグループとする．

wt[maxwt].cn=2;

アルゴリズムは以下のとおりである．

wt[t].p=maxwt; wt[t2].p=maxwt;
delmap(t); delmap(t2);

Triplet Tree{}if(map[x][y]!=BLANK){} else {t2 = map[x][y];map[x][y]=t;if(wt[t].p==OFF && wt[t2].p==OFF) {}maxwt++;}

chuoyer(t,t2,&wt[maxwt].x,&wt[maxwt].y);wt[maxwt].level=wt[t].level+1;

t,t2 がぶつかった端子番号である．t が map[x][y]wt[maxwt].cn=2;
wt[t].p=maxwt; wt[t2].p=maxwt;の領域内で空白以外にぶつかれば，端子番号 t2 を} else if(wt[t2].p==OFF) {記憶する．もし両方に親がいない場合であれば，2wt[t2].p=wt[t].p; wt[wt[t].p].cn++;

分木を生成することができるので，最大端子数+1} else {wt[t].p=wt[t2].p; wt[wt[t].p].cn++;を行い新たな親端子の番号を設定する．wt[ ]は端子}である．chuoyer( )で t,t2 の(x,y)座標の中間値を計if(wt[wt[t].p].cn>2) {算し，この座標を親端子の座標とする．またこの座

for(i=1;i<=maxwt;i++) {標は階層毎にペア生成が完了したら，再度親の座標if(wt[i].p==wt[t].p) delmap(i);}を割当てする．その時は，子の座標を全て足し，子}の数で割ったものを親座標とする．これは二分木生} else {成よりも三分木生成に有利である．座標を設定すれ

map[x][y]=t;}ば，親のレベルを子のレベルより１上げ，子の数を}2 とする．t,t2 の親を設定し，二分木よりこれ以上ペア生成をする必要はないので，delmap( )でマッt,t2 がぶつかった端子番号である．t が map[x][y]プ上から t,t2 を削除する．またぶつからなかった場の領域内で空白以外にぶつかれば，端子番号 t2 を合そのままにし再度ダイヤモンド型領域を広げて記憶する．もし両方に親がいない場合であれば，ペいく．ペア生成はその階層で端子数が 1 になるまでアを生成することができるので，最大端子数+1 を-6-

行い新たな親端子の番号を設定する．wt[ ]は端子で(1) level 0ある．chuoyer( )で t,t2 の(x,y)座標の中間値を計算

最初に端子を配置する．端子の位置は図 8 のように，し，この座標を親端子の座標とする．座標を設定す比較するためお互い同じ配置とする．

れば，親のレベルを子のレベルより１上げ，子の数を 2 とする．t,t2 の親を設定する．三分木なので，(2) level 0最寄の端子をグループ化する．図 9 の三分木で端子また繰り返し，グループ生成を行う．次に t に親がグループが 1 の単独である端子が存在するが，これいて t2 に親がいない場合 t2 の親を t の親と同じに以上グループ生成はできないのでそのままにしてする．そして t の子の数を増やす．また t2 に親がおく．

いて t に親がいない場合 t の親を t2 の親と同じにする．そして t の子の数を増やす．もし t の子の数が2 より多くなれば，三分木生成は完了しているので，その端子を delmap( )より削除する．ぶつかりあわなければそのままにし再度ダイヤモンド型領域を広げていく．グループ生成はその階層で端子数が 1二分木三分木になるまで繰り返す．
図 9．グループ生成

親の座標は階層毎にグループ生成が完了したら，再度親の座標を割当てする．その時は，子の座標を全(3) level 0て足し，子の数で割ったものを親座標とする．

グループ化した端子の中間点を親として上の階層

なお三分木であるので，端子数が３のべき乗でなに設定する．図 9 の三分木でグループが１である単い場合，端子をすべてグループにすることができな独の端子が存在したが，その端子は次の階層でグルいが，その場合は，端子レベルを 1 あげることで，ープ化させるので，そのまま階層を 1 あげる．

次の階層でグループ生成する．

level0 で親端子は上の階層に設定してあるので，本来は存在していないが，中間点に配置したことを証明するため，図 10 より親端子の色を黒で設定して3.3 二分木と三分木の比較ある．今後黒で表記した端子は上の階層で設定した概念的な図で，二分木と三分木の生成の過程を比較端子として表す．

する．この図では端子数を 16 と設定する．

二分木
二分木

三分木

三分木

図 10．親端子設定
図 8．初期配置(level 0)-7-

グループ化し親端子を設定する．図 14 のように三(4) level 0→level 1

分木グループの端子が２である場合，二分木生成とグループ化と親端子の設定が全て終了すれば，次の同様に中間点に親を設定する．

階層にあがる．
（図 11）

二分木

二分木

三分木

三分木

図 14．親端子設定

図 11．level 1(8) level2→level3(5) level 1

グループ化と親端子の設定が全て終了すれば，次のグループ化し，図 12 のように親端子を設定する．

階層にあがる．図 15 の三分木は端子数が 1 となったので，グループ生成は終了となる．

二分木

三分木

図 12．親端子設定

二分木

三分木

図 15．level3(9) level3(6) level 1→level 2グループ化し親端子を設定する．（図 16）

グループ化と親端子が全て終了すれば，次の階層にあがる．
（図 13）

二分木

三分木

図 16．親端子設定
二分木

三分木

図 13．level 2(10) level3→level4
グループ化と親端子が全て終了し，図 17 の二分木

(7) level2-8-

も端子数が 1 となったので，両方のグループ生成は細配線もすっきりして見える．より詳しい結果を実終了する．

験で紹介する．

4実験
最初にレイアウト領域と端子数を設定し，配置に関しては乱数を用いてランダムに配置する．そこで配置による配線長の変化と二分木と三分木のクロ二分木

ック構造について総配線長と段数を比較する実験

三分木

図 17．端子生成終了を行った． Cygwin の c 言語で実装した．

(11)概念図グループ生成を行った結果，このような木構造とな

4.1 ランダム配置の端子生成る．
（図 18）

端子の配置は乱数を使用し，ランダムに行っている．配置によって総配線長はどうなるか確認した．
レイアウト領域 100×100 と 200×200，端子数 100 と200 で乱数を 1〜50 を 10 毎に設定した．テストデータの概要を表 1 と表 2 に示す．
表 1．テストデータによる分木数毎の配線長の比較(サイズ 100x100，端子数 100)
図 18．概念図
Btree
Ttree

11641
1349

1015461395

2016641494

3016481368

4016761363

501512
1437

Av16151401

図 19 はレイアウト領域 100×100，端子数 100 で行い，配線は豊永研究室の配線ツールを利用している．

表 2．テストデータによる分木数毎の配線長の比較(サイズ 200x200，端子数 200)

実際の配線は以下のようになる．

Btree
Ttree

14674
4101

1047224001

2047194030

3050424063

4050414040

5048074030

Av48344044

B-tree は二分木，T-tree は三分木，1〜50 は設定した乱数である．結果は２つのクロック構造において，端子の配置が変化しても総配線長はほぼ等しいことがわかる．よって配置は総配線長に影響しないこ(a)二分木とがわかった．

（b）三分木図 19. クロック木の詳細配線(サイズ 100x100，端子数 100)

4.2 配線長・分木点数と段数実際比較すると，三分木の方が段数も少なく，詳２つのクロック構造について，総配線長および段数-9-（階層数)を調べる実験をおこなった．ベンチマー
ク用の端子データは，レイアウト領域 100×100〜400×400 の 4 種類の規模に対して端子数 50〜400 を50 毎に配置した．総配線長は表３〜6 となる．

表 3．総配線長比較 (サイズ 100x100)

#term

Btree

Ttree

lengthdiff(%)

501083982

9.3%

100

1641

1349 17.8%

150

2002

1743 12.9%

200

2368

1917 19.0%

250

2751

2262 17.8%

300

2999

2430 19.0%

350

3180

2718 14.5%

400

3512

2965 15.6%

#term

Btree

Ttree

lengthdiff(%)

50

3262

2938

9.9%

100

5341

4125 22.8%

150

5894

5305 10.0%

200

6927

6116 11.7%

250

8051

6655 17.3%

300

8896

7525 15.4%

350

9679

8023 17.1%

400 10762

8983 16.5%

表 6．総配線長比較

表 4．総配線長比較 (サイズ 200x200）(サイズ 400x400）
lengthdiff(%)

#term

Btree

Ttree

50

4168

3523 15.5%

10063435506 13.2%

150

8486

6901 18.7%

20098397812 20.6%

250 10574

8924 15.6%

300 11400

9652 15.3%

350 12893 10590 17.9%

lengthdiff(%)

#term

Btree

Ttree

50

1916

1697 11.4%

100

3111

2882

15040483484 13.9%

20046744101 12.3%

250

5432

4518 16.8%

300

5981

5008 16.3%

配線長は削減されており，7.4%〜最大 20.6%の削減

35067245421 19.4%率が見られた．また総配線長はレイアウト領域と端

400

7018

6046 13.9%

子数によって左右されることがわかった．

7.4%

400 14107 11285 20.0%#term は端子数，length diff は総配線長の削減率となる．
結果は全てにおいて二分木より三分木の方が総次に分木点数の結果を表 7〜11 に述べる．element
表 5．総配線長比較 (サイズ 300x300)

diff は分木点数の削減率である．
実際の分木点数は二分木の場合全て同じ結果になった．三分木もほぼ同様の結果となっている．
二分木に比べ三分木の分木点数は削減できており，30％以上の削減率が見られた．

表 7．分木点数比較 (理論値)- 10 -

#term

Btree

Ttree

50

49

100

element

elementdiff(%)

#term

Btree

Ttree

24

51.0%

50

49

31

36.7%

99

49

50.5%

100

99

65

34.3%

150

149

74

50.3%

150

149

84

43.6%

200

199

99

50.3%

200

199

129

35.2%

250

249

124

50.2%

250

249

157

36.9%

300

299

149

50.2%

300

299

190

36.5%

350

349

17450.1%

350

349

229

34.4%

400

399

199

50.1%

400

399

254

36.3%

表 8．分木点数比較

表 11．分木点数比較(サイズ 100x100)
elementdiff(%)(サイズ 400x400）
element

#term

Btree

Ttree

38.8%

50

49

34

30.6%

61

38.4%

100

99

61

38.4%

149

90

39.6%

150

149

100

32.9%

200

199

129

35.2%

200

199

122

38.7%

250

249

155

37.8%

250

249

162

34.9%

300

299

183

38.8%

300

299

188

37.1%

350

349

218

37.5%

350

349

216

38.1%

400

399

248

37.8%

400

399

246

38.3%

#term

Btree

Ttree

50

49

30100

99

150

表 9．分木点数比較

diff(%)(サイズ 200x200）
elementdiff(%)

表 3 の最初にある理論値は章 2.3 で計算した結果である。比較すると二分木は全て同じであり，三分#term

Btree

Ttree

50

493136.7%

10099

6534.3%150

149

9238.3%るので多少理論値通りに 50％も削減することはで

200

199

124

37.7%

きなかったが，それを踏まえて考えると理論値に近250

249

156

37.3%

く，削減率は高いことがわかる．

300

299

186

37.8%

350

349

210

39.8%

400

399

24039.8%

diff(%)

木に関しては 20〜30％程度違いがあるが，本研究で使用した三分木は二分木や単独になる場合があ

分木点数は規模の濃淡によらず,端子数のみ関係があることがわかった．最後に段数の結果を表 12に述べる．calculation は理論的に計算した値（理論表 10．分木点数比較(サイズ 300x300)値）である．実際の段数は全てにおいて同様の結果となった．しかし Ttree でレイアウト領域 300×300，端 子 数 400 の 時に 段 数 が７ ， レイ ア ウト 領 域
400×400，端子数 150 の時に段数が７となった．
- 11 -

本手法の三分木は二分木を生成して三分木を生謝辞

成し，三分木になれない端子は次の階層へあげる手

本論文の作成にあたって，ご指導頂きました豊永法を用いているので，それが影響されていると考え昌彦先生に深く敬意を表し，深く感謝致します．まられる．

た協力して頂いた同研究室の海老江 光さん，吉田段数の削減は二分木に比べ三分木は理論値が 2.3

祐馬さんをはじめ，同研究室の方々に感謝致します．

〜3.5 段，実際の段数は 2〜3 段削減された．よって実際の段数は理論値とほぼ同等の結果が出ていると言えそうである．

参考文献

表 12．段数比較#term Btree Ttree[1]海老江光，下川遥香，豊永昌彦，“三分木に基づCalculation

くクロック配線の一手法”，電気関係学会四国支部

Btree Ttree

50

645.7

3.4

100756.7

4.0

150

85 (6)

7.3

4.4

200

86

7.7

4.6

Li,“Combinatorial Algorithms for Fast Clock Mesh

250

86

8.0

4.8

Optimization”ICCAD’06,November5-9,2006,San Jose,

300

968.3

5.0CA

350

968.3

5.0

[3] Moses Charikar, Jon Kleinberg, Ravi Kumar,

400

96 (7)

8.7

5.2

連合大会，2007，1-5[2]Ganesh Venkataraman, Zhuo Feng, Jiang Hu, Peng

Sridhar Rajagopalan, Amit Sahai, Andrew Tomkins,“Minimizing wirelength in zero and bounded skew

5まとめclock trees” Proc. of 10th ACM-SIAM Symposium on

実験から従来の二分木構造のクロック回路に対して，三分木構造では 2〜3 段の段数削減が期待でDiscrete Algorithms, pp.177-284, 1999.
[4]コンピューターの構成と設計 第２版

き，理論値とほぼ同等な削減ができることがわかっ

ジョン・L・へネシー

た．そして分木点数も 30％以上削減でき，理論値ソンに近い削減率が見られることがわかった．また端子の位置のばらつきによらず，10〜20%の配線長削減が期待できる．よって二分木より三分木の方がクロック回路規模が縮小でき，消費電力の削減に有益であると思われる．
今後の課題としては三分木以上におけるクロック木の実装方法の更なる検討が必要である．

- 12 -

日経出版

ディビット・A・パター

1999 年．