2層BGAパッケージにおける配線混雑度低減のための詳細ビア配置手法

摘要

BGAパッケージはチップとプリント基板の大量の接続を実現できるが，異なる層間の高密度な配線パターンを接続するために多くの障害物を避けた上で適切な位置にビアを配置することが求められるなど，配線設計には多大な時間を要しており，その自動化が望まれている．本稿では，与えられた概略配線パターンに応じて両層のデザインルールを満たした詳細配線パターンを得るために，動的計画法に基づいた詳細ビア配置手法を提案し，配置されたビアの列数に対してほぼ線形時間で最適な詳細ビア配置が求められることを示す．%A BGA package realizes a lot of connections between a chip and a printed board. The quality of routing design obtained by manual is high, but it takes much time since it must take a lot of constraints into account. For example, vias must be arranged in appropriate positions so that they connect high-density routings between different layers while avoiding obstacles. Therefore, BGA package routing automation is required in industry. In this paper, we propose a detail via arrangement method that derives detailed routing patterns that satisfy the design rule of both layers from global routing patterns. Our proposed method is based on a dynamic programming. We show that our proposed method obtains an optimum detail via arrangement in almost linear time in terms of the number of rows of vias.