Mixed-Crossing-Avoided Escape Routing of Mixed-Pattern Signals on Staggered-Pin-Array PCBs
Mixed-Crossing-Avoided Escape Routing of Mixed-Pattern Signals on Staggered-Pin-Array PCBs
复制标题
DOI：
10.1109/tcad.2014.2301676
复制
发表时间：
2014-04
影响因子：
2.9
通讯作者：
Kan Wang;Sheqin Dong;Huaxi Wang;Qian Chen;Tao Lin
中科院分区：
文献类型：
--
作者：
Kan Wang;Sheqin Dong;Huaxi Wang;Qian Chen;Tao Lin
逃逸布线已成为高速PCB布线中的一个关键问题。之前的大多数工作都关注差分对逸出路由或单信号逸出路由，但很少有人将它们放在一起考虑。本文提出了一种有效的三阶段算法来解决差分对和单信号（混合模式信号）的逃逸路由问题。首先，对差分对进行预处理，以减少问题的复杂性。然后，一个统一的ILP模型来制定的问题，并提出了一种新的布尔编码驱动的算法，以避免混合交叉。最后，提出了一种基于切片的方法来修剪变量，提高算法的速度。实验结果表明，该方法是非常有效的。对于单模式的逃逸布线，该方法可以在短时间内解决所有测试用例，并减少导线长度和芯片面积分别为16.1%和15.5%。对于混合模式的逃逸布线，它可以提高布线能力的17.5%，减少了14.1%的线长相比，一个两阶段的方法。同时，该方法在导线长度增加不大的情况下，可以有效地避免混合交叉。此外，基于切片的加速策略，该方法可以减少76.7%的求解时间。
Escape routing has become a critical issue in high-speed PCB routing. Most of the previous work paid attention to either differential-pair escape routing or single-signal escape routing, but few considered them together. In this paper, a significant three-stage algorithm is proposed to solve the problem of escape routing of both differential pairs and single signals (mixed-pattern signals). First, differential pairs are preconditioned to reduce the complication of the problem. Then, a unified ILP model is used to formulate the problem and a novel Boolean coding-driven algorithm is proposed to avoid mixed crossings. Finally, a slice-based method is presented to prune the variables and speed up the algorithm. Experimental results show that the proposed method is very effective. For single-pattern escape routing, it can solve all the test cases in short time and reduce wire length and chip area by 16.1% and 15.5%, respectively. For mixed-pattern escape routing, it can increase the routability by 17.5% and reduce the wire length by 14.1% compared to a two-stage method. At the same time, the proposed method can effectively avoid mixed crossings with only a little increase on wire length. Furthermore, with slice-based speedup strategy, the method can reduce the solving time by 76.7%.