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

摘要

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