ポテンシャル法を用いたBGA配線手法

摘要

近年のLSIチップの大規模化，高集積化に伴い，パッケージのピン数も増加してきている．その増加に対応するため，Ball Grid Array (BGA)と呼ばれるパッケージが広く利用されている．しかし，このBGAにおける配線設計は複雑化しており，従来の手設計による手法では設計が不可能となっている．本稿では，一層BGAパッケージ配線におけるPads on the In-most (PoI)モデルに着目する．そのモデルにおいて，各ボールへのネット割り当てが未定である場合に対し，各ボール間の配線数が制約として与えられているときの配線長最小化を総ボール間配線数最小化問題として定義する．この問題に対し，平面配線の位相情報の表現手法であるポテンシャル法の利用を検討した．ポテンシャル法による配線では，各ボールにポテンシャルと呼ばれる順序関係をno-saddle制約の下で割り当てることにより，ボールからの配線経路が一意に定まる．このポテンシャルの割り当てを発見的に行なうアルゴリズムを提案する．また，ポテンシャル法のSimulated Annealing法による実装を行ない，提案アルゴリズムとの比較を行なった．そして，実験により，提案手法の有効性を確認した．