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

摘要

近年のLSIチップの大規模化，高集積化に伴い．パッケージのピン数も増加してきている．その増加に対応するため，BallGridArray（BGA）と呼ばれるパッケージが広く利用されている．しかし，このBGAにおける配線設計は複雑化しており，従来の手設計による手法では設計が不可椎となっている．本稿では，一層BGAパッケージ配線におけるPadso－1t?ほI－＝r10日t（Pol）モデルに着目する．そのモデルにおいて，各ボールへのネット割り当てが未定である場合に射し，各ボール間の配線数が制約として与えられているときの配線長最小化を総ポール間配線数最′」、化問題として定義する．この間題に対し，平面配線の位相情報の表現手法であるポテンシャル法の利用を検討した．ポテンシャル法による配線では，各ボールにポテンシャルと呼ばれる順序関係をmかSaddle制約の下で割り当てることにより，ボールからの配線経路が一意に定まる．このポテンシャルの割り当てを発見的に行なうアルゴリズムを提案する．また，ポテンシャル法のS血Iul札Le（1Anne乱1ing掛こよる実装を行ない，提案アルゴリズムとの比較を行なった．そして，実験により，確実手法の有効性を確認した．