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

クロストークを回避する配置評価の検討
A Study of Cross-Talk Free Cost Function for Placement
吉田 佑馬

豊永 昌彦

Yuma Yoshida

Masahiko Toyonaga

高知大学理学部数理情報科学科
Faculty of Science, Kochi University

あらましら高性能な情報機器でも高価であれば，市場で普及

情報化社会の進展に伴い，より安価で高性能な電することは困難である．これより，市場では情報機器に子機器が市場で求められ，その重要部品である LSI 製

使われる，高性能で安価な電子機器が求められてい造の微細化が進められている．一方，LSI 製造の微細る．高性能化の要望を受けて，電子機器の重要な部

化は，クロストークや電圧降下など様々な物理現象を品の一つである LSI の微細化が進められている．
LSI とは，シリコン基盤の上に多数の素子を配置して顕在化して不良品問題を起こす．
本論文は，配線パターンに起因して生じるクロストー

情報処理機能を実装させたものである． LSI は，CPU

ク問題に注目し，その回避設計技術の提案を行うもの（Central Processing Unit；中央演算処理装置）やメモリ，である．

周辺機器制御または音声や画像の処理など様々な用

従来のクロストーク回避はレイアウト設計における配途で電子機器において使われている．LSI を微細化す

線段階が主であった．しかし，配線密度が高い近年のることは，LSI の中で信号を伝える距離を縮め高速化･LSI 設計において十分回避できない場合がある．本論

低消費電力化を図り，直接 LSI の小型化に繋がるなど文で著者は新たな配置設計でクロストーク回避を提案

高性能化に有効である．

する．提案手法は，配置評価関数に特定配線間にかしかし，微細化による LSI 内のスペースの縮小によかわる素子配置を分離するためのペナルティ関数を導って，次のような物理現象が顕在化する．すなわち，配入するものである．

線間隔が小さくなり隣接する配線間で相互作用するク

簡単な配置問題で本手法を評価したところ，総配線

ロストーク現象，製造された配線幅が場所によってばら長への影響が 10％程度で，クロストーク問題となる配つく製造ばらつきの問題，電子の移動に伴う金属原子

線間を完全に分離できる結果が確認された．

の移動で配線が断線するエレクトロ・マイグレーション問題などが挙げられる．

1． まえがき

このような微細化に伴う現象は LSI の多くの不良品

電子機器の高性能化は，近年の情報化社会の基盤を生み出し，開発コストや製造コストを圧迫する．したになっている．そのため電子機器の高速化，低消費電

がってこれらの問題を防止する新たな設計技術の確力化，小型化など様々な高性能化が市場から求めら立が急がれる．

れている．つまり，高性能な情報機器を市場に普及さこれらのうちクロストーク現象の原因は，特定の 2 信せることが，情報化社会の進展に繋がる．しかし，いく号間の配線パターンが長距離にわたり隣接することで，
1

対面する金属板とみなせる配線の間に寄生する電荷えることで，相互の配線にかかわる素子を２次元的に容量である．クロストークとは，この配線間の寄生電荷分離した配置を求めるものである．

容量を通じて，それぞれの配線の信号を相互に影響新たに構築したクロストーク回避配置評価関数を用を受けて回路の動作不良を起こす現象を指す．

いて，簡単な配置実験をおこなって評価したところ，総膨大な素子設計をおこなう LSI 設計は，仕様設計，

配線長への影響が 10％程度で，特定の２つの信号に機能設計，ゲートレベル設計，トランジスタレベル設計，かかわる素子群を分離した配置結果が確認された．こレイアウト設計の段階に分業化されている．このなかで，れにより，製造コストを圧迫する不良品を防ぎ，高性能

クロストーク現象は，配線製造に直結するレイアウト設

な電子機器をより安価にできることが期待できる．

計の影響が最も大きい．

以下，本論文の構成を説明する．

そこで本論文では，LSI 設計の中でクロストーク回避

次の第 2 章において，クロストーク問題全体についのためレイアウト設計段階の技術を議論する．

て述べる．第 3 章において，提案法であるクロストーク

レイアウト設計は，さらに詳細に配置段階と配線段回避配置法について述べる．第 4 章において，提案法階で構成されている．

の効果または性能を調べる実験について述べる．第 5配置設計は，全体の素子の回路上の位置を決め，章で本論文のまとめを，第 6 章で本論文作成における次の配線設計は配置された素子間の端子間の配線経謝辞を述べる．

路パターンを決定する．
クロストーク現象に直接かかわる配線パターンにつ2． クロストーク問題

いて従来からクロストーク回避方法が提案されてきた．

2．1．クロストーク現象

特に，寄生容量を削減するために隣接し並走する配クロストークとは，電話などにおいて信号が入り混じる

線パターンを引き離した新たなパターンに再設計する現象をいう．LSI において，クロストーク現象が顕著に方法が中心［2］となっている．

なると，回路の演算や回路間の入出力信号が正しく伝播できなくなり，回路の動作不良の原因となってしま

直接的で修正箇所も少ないため，この方法は有効

う．

であるが，一方で高密度な配線を要する LSI では，回

クロストーク現象の影響は，デジタル信号の周期が避するための配線領域が十分に確保することが難しい

短くなればなるほど，また配線間の寄生容量が大きくため使えない．

なるほど大きくなる．

著者は，このような問題を解決するため配置設計に注目する．すなわち，もし配置でクロストーク回避が出

2．2．寄生容量と信号の関係来れば，配線密度の影響を受けずクロストーク回避が

図 1 は面積 S の金属面が距離ｄ離れて平行に向かできる．そこで配置段階からクロストーク回避をおこなう

い合った電荷容量における物理量の関係を説明した方法を新たな技術の構築を検討した．

図である．電荷容量 C の大きさは，

本論文で考案した配置手法は，従来の配置モデル
で用いる配線長推定モデルに，特定の二つの信号の

C＝eS/d

配線パターンが「隣接」するときに別にペナルティを加

-2-

(1)

としてあらわせる．ここで e は，誘電率である．誘電率とは，電荷の集まりやすさの目安で，物質により決まる定
数である．

d

S

S

図 2.配線断面図d
C= e S/d

もし 2 つの信号配線が長距離に渡って隣接して並走したとすると，その対面する面積 S は大きい．さらに

図 1. 金属板による電荷容量（コンデンサ）

微細化によって対面する距離ｄも小さい．
このように広い S と短い d となる配線間には，式(1)

いま，ある回路中の配線間にコンデンサが挿入されで表された電荷容量 C をもつコンデンサが寄生してしたとすると，コンデンサ両端が断線していても，コンデ

まい，クロストークが生じる可能性をもつ．

ンサ容量 C に比例した電荷量だけ電流が流れる．
LSI において，配線が分離されていても，配線間の2．4．従来のクロストーク回避法

寄生容量が増すと，一部の配線間で電流が流れてし

クロストーク現象を回避するには，配線間距離 d を広まいクロストーク現象が発生する．

く開けて C を小さくする，あるいは，そもそも配線間が直接対面しないように，電源やアースにつながる別の2．3．微細化による配線の現状

配線を挿入しておけばよく（シールド），これらはすでに微細化により，ナノレベルに達する LSI チップに形提案されている．

成される配線の断面を模式的に図 2 に示す．

それぞれの方法について図 3 を用いて説明する．図

図 2 に示すように，配線断面の縦横比は，縦方向が3(a)は，対面する配線間の距離を広げる方法により得極端に高い．これは，信号の伝播時間が配線抵抗にられた配線を示す．クロストーク現象の大小は，配線経比例することから，断面積をできるだけ広く確保するた路が決まるまでわからないため，一度配線してみて，めである．

対象となる配線パターンを引き剥がして再配線されて一方，これは隣接する配線間の対面する面積を広くいる．［4］，［5］してしまう．

図 3(b)は，シールドによる方法を示した図である．先ほどの再配線だけではなく，中央に白抜きの配線で示した電源あるいはアース配線を挿入するものである．これにより先ほど対面していた配線は，分離され相互の信号の影響は受けない．これらは主に設計者による手-3-

作業で行われる．

ためには，新たな評価関数の定式化が必要である．
以下，一般的な配置評価関数について説明し，その後に著者の考案したクロストーク回避配置評価関数
について述べる．

(1) 配置評価関数

d

d

d

d

配置問題は ，配置設計の後に 続く配線設計が100％の結線と回路面積を有効に利用するための配置位置を決定する問題である．以下のようにして定式：シールド配線(a)配線の間隔をあける化することができる．

(b)シールド効果を目指す

図 3. 従来のクロストーク回避例
配置問題
1) ネットリストで与えられた全ての素子全てを重複す

図 3 からわかるように，いずれのクロストーク回避配線法も配線領域を拡大しなければならないため，他のることなく配置領域内に割り付ける．

配線で使う領域を狭めてしまう．場合によっては全配

2) 配線設計が容易となる配置を導出する．

線を 100%接続するための領域が確保できなくなる場
従来の配置手法のほとんどが配置評価関数として合も生じる．

「推定総配線長」を採用している．

配線技術のみによるクロストーク回避策の限界を超

これを最小化して配線が短くなると，2)の配線設計えた技術が望まれる．

が容易化できるからである．
最 も 一 般 的 な 配 線 長 推 定 モ デ ル と し て MBB

3． クロストーク回避配置法(Minimum Bounding Box)が用いられる．

そこで著者は、配置設計におけるクロストーク回避

MBB とは，配線に関わる端子位置が作る最小矩形策について検討する．以後の議論において，クロスト
ークを引き起こす可能性のある信号の配線組をクロストのことで，MBB の半周囲長を推定配線長とする．

ークペアネット（ペアネット）と呼ぶことにする．

具体的に推定配線法 L は式(2)で求める[3]．

いま，クロストーク現象を引き起こす原因となる幾つLMBB (i )L net

かのペアネットに関係する素子群を特定できたとする．

(2)

i N

もし，これらの素子群が，配置設計において相互に離

ここで，LMBB は，ある信号 net の配線対象となる全れた位置に配置されれば，配線設計においてペアネての端子（terminal）の位置（あるいは信号 i に関係するットの配線経路が隣接することや，長距離にわたり並素子位置）を包含した最小矩形 MBB の半周囲長であ走することもなくなり，クロストーク発生を回避することがる．これを，図 4 に模式的に示す．

できる．
特定のペアネットの素子を分離する配置問題を解く-4-と呼び，灰色で示した． ペアネットの Overlap Area のterminal

高さを ho(i,j)，幅を wo(i,j)とする．また，図 5 では ho(i,j)と wo(i,j)に，それぞれ を 足しあわすことで OverlaphmArea を拡げている． はペアネットを引き離す指標である．ペアネットの MBB が重複しなかったとしても，隣接wm

していれば向かい合う面を通る配線がクロストークを引き起こす可能性がある．これより，ペアネットの MBB が図 4. 配線長推定モデル

十分に離れた結果を求めるため を 導入した．図 (b)
いま最小矩形の高さを hm,，幅を wm としたとき，に示すような，ペアネットが以上離れた場合に，ペア

LMBB= hm,+wm

ネット重複領域 Oarea は 0 になる．

として表すことができる．

この Overlap Area の大小により，ペアネットの配線経回路の推定総配線長 Lnet は，全信号数 N について

路の分離の程度を，次のように数値化できる．Overlap

回路の全信号 i の LMBB をすべて足し合わせたものでArea の ho(i,j)+
と wo(i,j)+ を足し合わせ，ペアネット

ある．

重複領域 Oarea(i,j)とする．
Oarea(i,j)=( ho(i,j)+
)+(wo(i,j)+)(2) クロストーク評価関数

この Oarea(i,j)が，あるペアネットの配線経路の分離の程ペアネットを分離する配置のための配置評価関数は，次のような定式化により求めた．

度を表す．Oarea(i,j)=0 ならばペアネットは離れている．

MBB(i)
MBB(j)

クロストーク回避配置問題
1) ネットリストで与えられた全ての素子全てを重複す

Overlap
Area for(i,j)

ることなく配置領域内に割り付ける．
2) 配線設計が容易となる配置を導出する．

ho(i,j)+wo(i,j)+3) クロストーク現象で不都合となる複数の信号（ペア(a) ペアネット重複領域 Oarea(i,j)≠0

ネット群）群が相互に交差しない配置を導出する．

MBB(i)
ここでペアネットの２つの MBB の重なる範囲をそれMBB(j)

ぞれの配線経路の範囲と仮定する．また，ペアネットのMBB が重なる範囲をペアネット重複領域 Oarea と呼ぶことにする．
図 5 は，ペアネット重複領域 Oarea を説明したものであ(b) ペアネット重複領域 Oarea(i,j)=0

る．ペアネットのそれぞれの信号 i と j の MBB を２つの図 5. クロストーク評価モデル

破線による矩形で示した．
ペアネットの MBB が重なった部分は，Overlap Area
-5-

全ネット中のペアネット（Nx）について Overlap Area

提案法では，これをクロストーク違反値 Cover とすることの Oarea(i,j)を総和し，重み付け因子ｗを掛け合わせてにした．

クロストーク違反値 Cover とする．重みｗを 0 としたなら

クロストーク違反を反映させた配置評価関数を Ccost
として式(3)に示す．

ばクロストーク違反値は 0 である．

Cover

Oarea(i, j) w

Ccost

(3)

Lnet Cover(4)(i , j ) Nx

この Ccost を評価値とすることにより，総配線長とペア
本評価関数は，クロストーク現象の緩和を目的としてネットのクロストーク違反値の両方を評価した配置解をいる．もし，ペアネットが分離されていてクロストークのえることが期待できる．

影響が小さいならば，従来の総配線長最小化となる配置結果が導き出されなければならない．

(3) Simulated Annealing 法による配置プログラム

このようにペアネットの配線が長距離間並走しない

以上の評価関数から最適解を導くためにシミュレー

ほど Overlap Area が小さい場合には，ペアネット重複

テッドアニーリング（SA）法を用いた．

領域 Oarea は 0 となるべきである．

シミュレーテッドアニーリング（SA）法とは，最適化手

これを実現するために，式(3)を場合分けにより 0 と法の１つで，汎用の確率的アルゴリズムである．

するステップ関数 θ(x)を用いる．ステップ関数とは，図SA 法のアルゴリズムを以下に示す．

6 に示すように引数 x が 0 未満で 0，それ以上で 1 となる関数である．

procedure simulated-annealing {T = Ts;while (Te <T ) {step=0;while (step < Nmax ) {cost1 = cost_func();/*セル交換前の配線長を計算*/
random_cell_exchange();/*無作為に二つのセルを交換*/
cost2 = cost_func();/*セル交換後の配線長を計算*/
if (cost2<cost1 || exp(-(cost2-cost1)/T) > rand()) {/*配線長の評価*/
accept the exchange;/*交換後のセル配置を採用*/} else {reject the exchange;/*交換前のセル配置を採用*/}
step++;}
T=T*Cooling;/*温度の冷却*/}}0 ( x 0)x

1 ( x 0)1x0

図 6. ステップ関数

いま，ペアネットでクロストークが起こらない程度の
Oarea の値の上限を Llim とする．ステップ関数としてこれを式(3)に乗じ，式(3)’とする．

Cover{Oarea (i, j )Oarea (i, j ) Llim } w (3)’( i , j ) Nx

図 7. シミュレーテドアニーリング法-6-

4． 実験

ここで，cost1 は現配置の評価関数値，cost2 は変更候

(1) ベンチマーク回路と実験条件

補の評価関数値である．また，セルとは，配置解を構

クロストーク回避を含む配置評価関数式(4)の有効成する素子を指す．変更候補は，たとえばセル２つを性について検証するための実験を行う．特に，新たな無作為に選び，セルの配置位置を交換して作り出せる．

評価を追加したことによる総配線長への影響について

さらに，Ts は初期温度，Te は終了温度で，Nmax は温も詳細を調べ，その実用性について検討する．

度 T における平衡状態までの本アルゴリズムのループ

配置ベンチマーク回路としては，30×30 のサイズの，回数，Cooling は熱平衡到達後に移る新たな温度と現４方向に結線された簡単な回路を用いている．

在の温度 T と冷却率（ 0 < Cooling < 1 ）である．

また，ペアネットは，これに 4 端子ネットを２つ追加し無作為に作った配置変更候補で評価値が改善された．

るときはその配置が採用される．また，評価値が改善さ

ベンチマーク回路の素子と接続の様子を図 8 に示れない場合には，以下式(5)の確率で受け入れる．Rす．図中，小さな正方形が接続するべき端子があるセは 0 から 1 までの乱数で， E は配置変更候補との評

ル，薄く見える線が格子状の接続配線であり．濃く見価値差である．

える実線(二重線)と破線の正方形が 4 端子のペアネッ
トの MBB である．ペアネットのそれぞれの端子は，そexp(- E/T) > R(5)

れぞれの MBB の四角に置かれている．また，ペアネッ
トはこの回路のほぼ全域で重複している． このベンチ式４に見られるように SA 法は，単に評価値が改善さ

マーク回路は図 8 が厳密解であるので，このとき総配れる解のみを検索するだけではなく，改善されない解線長は最小となる．

も確率的に採用するしくみをもっている．この確率は温度Ｔで徐々に変わる．
超高温で exp(- E/T)は，ほぼ 1 に近くなるため評価
値によらずにすべての変更候補の配置が採用される．
一方，超低温では exp(- E/T)の値は，評価値が改善されるとき（ E＜0）のみ，式 4 の左辺は無限大となり変更候補が採用される．
処理に十分時間をかければ必ず最適解に収束する
ことが保障されている．

図 8. ベンチマーク回路-7-

今回の実験では，評価関数(3)’の Llim を十分に小さめ，ペアネットは一切考慮されず総配線長のみの最小な値 4 とする．また，評価関数(3)’の Oarea(i,j)の中の の化を目指した結果である．このとき，実線と破線で示し値を 1 とする．

たペアネットの MBB は完全に重なってしまっている．

シミュレーテッドアニーリング（SA）法の配置は C 言

このとき，ペアネットは，最大配置領域の半周囲長程語(Cygwin)で実装し，条件は以下の通りとした．

度まで隣接して並走する可能性があり，クロストーク現・初期温度 Ts100

象を起こす危険性をもつ．

・終了温度 Te0.001

一方，図 10(b)のように w の値が 3.0 になると，ペア・冷却率 Cooling

0.99

ネットは，完全に分離されておりペアネットが互いに隣・平衡繰り返し数 Nmax 要素数×10

接し，並走することはないことが分かる．さらに，Llim を

ま た ， 実 験 機 と し て AMD Athlon(tm) XP 2500 +

十分小さくし，評価関数(3)’の Oarea(i,j)の中の の値を1.83GHz 1.21 GB RAM を使用した．

1 とし重複領域を広げていたため，実線と破線の矩形
領域間に 1 グリッド以上の距離が出来ている．

(2) 重み w によるペアネット分離の傾向

前節のベンチマーク回路を用いて，式(2)の重み付

表 1 総配線長と重複の Llim と w 依存性け因子 w を様々に変化させた(0〜10，0.5 刻み)ときのクロストーク回避評価関数による配置改善を行う．
実 験 の 結 果 得 ら れ た 総 配 線 長 (Lengthcost) とOverlap Area の重複長(Cross _cost：Cover/w)を表 1 および図 9 に示す．
Overlap Area 評価の重み w=2.5-3.0 の範囲で，重複領域長＝0 である．つまり指定したペアネットの推定配線領域である MBB は，互いに完全に分離している．
また，w=3.0~10.0 のときの総配線長の平均は，w = 0.0（クロストーク回避をしない場合）と比べて 10％程度増加している．
w = 0.0 のとき，およびペアネットの MBB が分離する
w=3.0 のときの配置結果を図 10(a)(b)にそれぞれ示す．
ペアネットの１つは実線，もう１つは破線で MBB を示している．
図 10(a)では，式(2)の重み付け因子 w が 0 であるた

-8-

Llim
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4

w
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
7.0
7.5
8.0
8.5
9.0
9.5
10.0

Lengthcost
2379
2491
2323
2439
2303
2433
2571
2632
2677
2671
2588
2625
2691
2640
2652
2590
2573
2576
2642
2703
2683

Closs̲cost
57.0
57.0
57.0
57.0
57.0
57.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

2700

50.0

2600

40.0

2500

30.0

2400

20.0

2300

10.0

2200

0.0

Closs̲cost

60.0

0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
6.5
7.0
7.5
8.0
8.5
9.0
9.5
10.0

Lengthcost

2800

w
Lengthcost

Closs̲cost

図 9. 総配線長とクロストーク違反面積の遷移

提案法の効果をより示すため，もう一つ実験を行っ化が進んでいる．微細化により，今まで考慮する必要た．図 8 のベンチマーク回路に，同様にほぼ全域で重のなかった物理現象が顕在化してきている．本論文は，複するようなペアネットを 3 組追加し，新たなベンチマ

その物理現象の中のクロストークに注目し，レイアウト

ーク回路とする．つまり，4 組のペアネットに対し，提案設計におけるクロストーク回避を目的にした．

法によるクロストーク回避を試みる．シュミレーテッドア

従来のクロストーク回避法では回避しきれない場合

ニーリング，Llim，
，w は今までの実験と同じ条件であがあるため，新たにレイアウト設計の配置段階でのクロる．

ストーク回避法を提案した．提案法はクロストーク回避

実験の結果の一例を図 11 に示す．ペアネットが入りのために，ある二つの信号の配線領域を引き離す配乱れていて見にくいので，太さ，パターンなど様々な置評価法である．格子状に接続配線を持つ簡単な配線でペアネットを表した．これは，見やすさを追求した

置問題に，一組の重複領域最大のペアネットを追加しだけのもので，ペアネットの形や広がりには関係ない．

たベンチマーク回路に，提案法による配置改善を実行

様々な太さとパターンの線の中で，同じ線の組それぞした．結果，総配線長増 10%程度で重複領域を完全

れが，4 組のペアネットの MBB である．

に解消できることがわかった．

図 11 より，それぞれの同じ線の組が 1 グリッド以上離今後，より実際的な配置問題においての効果を調れていることが分かる．これより，提案法は多数のペア

べる予定である．

ネットに対しても，完全にクロストークを回避できること
6． 謝辞が分かった．

この論文を作成するにあたり，指導または多くの助
5． まとめ

言をしてくださった豊永昌彦教授に深く感謝致します．

近年，情報機器の性能向上を目指し，LSI の微細また，研究議論に参加して下さった同研究室のニエテ-9-イエンさん，板東修司さんにも同様に深く感謝致しま

参考文献

す．
［1］ 吉田佑馬，ニエテイエン，板東修司，豊永昌彦，「クロストークを回避する配置評価の検討」，電気関係
学会四国支部連合大会，2007［2］ Di Wu, et al, “Layer Assignment for Crosstalk
Risk Minimization,” ASP-DAC 2004, pp. 159 – 162,
2004.
［3］ Jiri Soukup, “Circuit-Layout,” Proc. of the IEEE,
Vol.69, No.10, pp.1281-1304, Oct.1981.
［4］谷本俊介，山本雄輝，豊永昌彦，「クロストーク回避を目指した一配線手法」，電気関係学会四国支部
連合大会，2006(a) 総配線長のみを評価値とした配置結果（w = 0.0）

［5］竹谷啓，張汎，豊永昌彦，「クロストーク回避迷路
配線の一手法」，電気関係学会四国支部連合大会，
2007

提案法による配置結果（w = 3.0）
図 10.

ペアネットの配置改善結果の比較

図 11．ペアネット 4 組の配置結果（w = 3.0）
- 10 -