隨著積體電路技術的快速演進，PCB(Printed Circuit Board，印刷電路板)電路設計複雜度顯著的增加，現今一個密集的 PCB 板涵蓋了數以千計的接腳(Pin)和信號線(Signal nets)，這麼多的數量讓手動設計PCB 板變得很耗時，特別是在繞線的階段。而匯流排繞線也就是需要指派全部的匯流排到繞線層然後有架構的在每一層繞線，同時也要滿足一些限制，這部分是整個 PCB 繞線最困難的。此外，在 PCB 板的匯流排結構中，時間限制時常被考慮到，也就是匯流排所有的位元(Bit)需要有大約相同的繞線長度，所以長度匹配的議題也是需要的考量。另外，在先進的技術節點中，繞線軌道被用來遵守設計規則和幫助光罩的著色。在這篇論文中，我們提出了一個精緻的匯流排繞線，可以最佳化可繞線性，線長還有長度匹配的議題，同時考慮了軌道資源，障礙物和其他設計限制。實驗果顯示我們提出的演算法流程可以在繞線損失總和、最短最長的線長差距勝過其他篇匯流排繞線。

Due to rapid advance of the IC technology, design complexity is dramatically increasing in printed circuit boards (PCBs). Nowadays, a dense PCB contains
thousands of pins and signal nets, such huge net counts make manual design of
PCBs an extremely time-consuming task especially in the routing phase. Bus routing, which consists of assigning all the buses to the routing layers and topologically routing them on each layer while satisfying some constraints, is one of the most difficult steps in PCB routing. Besides, timing constraints are commonly concerned on PCB bus structure, where all bits of buses are highly preferred to have approximately same length, so that length-matching issue is often requested. In advanced technology nodes, moreover, routing tracks are provided to help router adhere to design rules and help mask coloring. In this thesis, we develop a sophisticated bus router which optimizes routability, wirelength, as well as length-matching while simultaneously considering track resources, obstacles, and other design constraints. Experimental results show that the proposed algorithm flow can outperform the state-of-the-art bus routers [18] [19] in terms of the total routing cost and the min-max length difference for the benchmarks provided by 2018 CAD contest at ICCAD[17].

[1] T. Yan, Q. Ma, and M. D. F. Wong, “Advances in PCB Routing,” IPSJ Trans.
System LSI Design Methodology, vol. 5, pp. 14–22, 2012.
[2] S. Pasricha, N. Dutt, E. Bozorgzadeh and M. Ben-Romdhane, “Floorplan
aware automated synthesis of bus-based communication architectures,” Proc.
Design Automation Conference, 2005.
[3] H. Xiang, X. Tang, and M. D. F. Wong, “Bus-driven floorplanning,” IEEE
Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 23, no.
11, 2004, pp. 1522-1530.
[4] T. Ma and E. F. Y. Young, “TCG-based multi-bend bus driven floorplanning,”
Proc. Asia and South Pacific Design Automation Conference, 2008.
[5] T. Yan and M. D. F. Wong, “Untangling twisted nets for bus routing,” Proc.
International Conference on Computed-Aided Design, 2007.
[6] J.-T. Yan, “Efficient layer assignment of bus-oriented nets in high-speed PCB
designs,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Sys
tems, vol. 35, no. 8, pp. 1332–1344, 2016.
[7] M. Lie and C.S. Horng, “A bus router for IC layout,” Proc. Design Automation
Conference, 1982.
[8] J.-T. Yan and Z.-W. Chen, “Obstacle-Aware Length-Matching Bus Routing,”
Proc. International Conference on Physical Design, 2011.
[9] G. Persky and L. V. Tran, “Topological routing of multi-bit data buses,” Proc.
Design Automation Conference, 1984.
[10] H. Kong, T. Yan, and M. D. F. Wong, “Automatic bus planner for dense
PCBs,” Proc. Design Automation Conference, 2009.
[11] P. -C. Wu, Q. Ma, and M. D. F. Wong, “An ILP-based Automatic Bus Planner
for Dense PCBs,” Proc. Asia and South Pacific Design Automation Conference,
2013.
[12] D. Liu, V. Livramento, S. Chowdhury, D. Ding, H. Vo, A. Sharma and David
Z. Pan “Streak: Synergistic topology generation and route synthesis for on
chip performance-critical signal groups,” Proc. Design Automation Conference,
2017.
[13] Y.-L. Li, J.-Y. Li, and W.-B. Chen, “An efficient tile-based ECO router us
ing routing graph reduction and enhanced global routing flow,” IEEE Trans.
Computer-Aided Design of Integrated Circuits and Systems, vol. 26, no. 2, pp.
345–358, 2007.
[14] J. Cong, J. Fang, and K.-Y. Khoo, “DUNE-a multilayer gridless routing sys
tem,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems,
vol. 20, no. 5, pp. 633–647, 2001.
[15] J. Cong, J. Fang, M. Xie, and Y. Zhang, “MARS-A Multilevel Full-Chip
Gridless Routing System,” IEEE Trans. Computer-Aided Design of Integrated
Circuits and Systems, vol. 24, no. 3, pp. 382–394, 2005.
[16] J. Cong, J. Fang, M. Xie, and Y. Zhang, “T. H. Cormen, C. E. Leiserson and
R. L. Rivest,” Introduction to Algorithms, MIT Press, 2000.
[17] A. Liao, H.-Y. Chang, O. Chi, and J. Wang, “ CAD contest in obstacle-aware
on-Track bus routing and benchmark suite,” Proc. ICCAD, 2018.
[18] J. Chen, J.Liu, G. Chen, D. Zheng and E. F. Y. Young, “MARCH: MAze
Routing Under a Concurrent and Hierarchical Scheme for Buses,” Proc. DAC,
2019.
[19] C.-H. Hsu, S.-C.Hung, H. Chen, F.-K. Sun and Y.-W Chang, “A DAG-Based
Algorithm for Obstacle-Aware Topology-Matching On-Track Bus Routing,”
Proc. DAC, 2019.