Layer Assignment of Buses and Nets With Via-Count Constraint in High-Speed PCB Designs

It is necessary for cost consideration to minimize the number of the used layers in a high-speed printed circuit board (PCB) design. In this paper, any independent net cannot be treated as a bus-oriented net in a high-speed PCB design because of no timing-matching constraint on an independent net. Any independent net in a high-speed PCB design can be modeled to obey the via-count constraint as the maximum number of the permitted vias for signal integrity. Clearly, the introduction of the permitted vias onto the independent nets can lead to the reduction on the number of the used layers in a high-speed PCB design. Given a set of bus-oriented nets and a set of independent nets with a via-count constraint in a high-speed PCB design, by introducing virtual vias onto independent nets and eliminating redundant vias on any used layer, a generalized algorithm can be proposed to minimize the number of the used layers with satisfying the via-count constraint on any independent net and assign the given bus-oriented nets and the separated segments inside the given independent nets onto the used layers. Compared with Yan’s algorithm with no via introduction on independent nets, the experimental results show that our proposed algorithm with ${c_{\max } = 1}$ , ${c_{\max } = 2}$ , ${c_{\max } = 3}$ , ${c_{\max } = 4}$ , and ${c_{\max } = 5}$ use reasonable CPU time to insert permitted vias to reduce 2.1, 2.8, 3.8, 4.4, and 4.6 used layers on the average for ten tested examples, respectively. Compared with a two-phase algorithm with via introduction on independent nets, the experimental results show that our proposed algorithm with ${c_{\max } = 1}$ , ${c_{\max } = 2}$ , ${c_{\max } = 3}$ , ${c_{\max } = 4}$ , and ${c_{\max } = 5}$ use less CPU time to reduce 1.6, 1.7, 1.7, 1.6, and 1.5 used layers on the average with increasing 13.3%, 16.3%, 10.6%, 4.2%, and 2.6% of the total used vias on the independent nets for ten tested examples, respectively.