隨著技術節點和異質整合（heterogeneous integration）的演進，封裝設計變得日益複雜。為了最佳化時序性能和信號完整性 （signal
integrity），必須使用不同間距值區分幾何相鄰網路對，這稱為成對
間距約束（paired-spacing constraint）。本文提出了首個考慮到成對間距約束的自由分配封裝繞線（free-assignment package routing）算法流程。為了最小化繞線資源需求和繞線總長，我們提出了基於動態規劃的繞線排序方法，以最大化相同/相似間距規則的網路數目並使其相鄰。此外，我們通過一個巧妙設計的模型，優雅地解決了自由分配繞線問題，該模型涉及最小成本最大流 （minimum-cost maximum-flow）問題。實驗結果顯示，所提出的方法能夠在對業界修改過的測試資料中實現 100％的繞線能力。相比之下，即使對經典模型進行簡單修改，使其能夠考慮成對間距限制，其繞線能力也
會明顯降低。
關鍵詞：成對間距，封裝繞線，網路排序最佳化，自由分配封裝繞
線

Package design has become increasingly complex with the evolution of technology nodes and heterogeneous integration. To optimize timing performance and signal integrity, it is essential to separate different pairs of geometrically adjacent nets with distinct spacing values, which is referred to as the paired-spacing constraint. This paper presents the first free-assignment package routing algorithm flow considering the paired-spacing constraint. To minimize the routing resource demand and overall wirelength, we propose a dynamic programming-based net ordering method to maximize the number of nets with the same/similar spacing rules
positioned next to each other. In addition, the free-assignment routing problem is elegantly solved with a minimum-cost maximum-flow problem on a delicately designed graph model. Experimental results show that the proposed flow can achieve 100% routability for the adopted industrial-modified benchmarks. In contrast, even with modifications to superficially consider paired spacings, a classic model experiences significant routability degradation.
Keywords: paired-spacing, package routing, net ordering optimization, freeassignment package routing

Bibliography
[1] H.-C. Lee, Y.-W. Chang, and P.-W. Lee, “Recent research development in flipchip routing,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design (ICCAD),Nov. 2010, pp. 404–410.
[2] J.-W. Fang, C.-H. Hsu, and Y.-W. Chang, “An integer-linearprogrammingbased routing algorithm for flip-chip designs,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 28, no. 1, pp. 98–110, Jan. 2009.
[3] C.-W. Lin, P.-W. Lee, Y.-W. Chang, C.-F. Shen, and W.-C. Tseng,“An efficient
pre-assignment routing algorithm for flip-chip designs,”IEEE Trans. C omput.- Aided Design Integr. Circuits Syst., vol. 31, no. 6, pp. 878–889, Jun. 2012.
[4] H.-T. Wen, Y.-J. Cai, Y. Hsu, and Y.-W. Chang, “Via-Based Redistribution
Layer Routing for InFO Packages with Irregular Pad Structures,” in Proc. of
DAC, San Francisco, CA, July 2020, pp. 1–6.
[5] J.-W. Fang, I.-J. Lin, P.-H. Yuh, Y.-W. Chang, and J.-H. Wang, “A Routing
Algorithm for Flip-Chip Design,” in Proc. of ICCAD, San Jose, CA, November
2005, pp. 752–757.
[6] J.-W. Fang and Y.-W. Chang, “Area-I/O flip-chip routing for chip-package
co-design,” in Proc. of IEEE/ACM ICCAD, 2008, pp. 518–522.
[7] J.-W. Fang, M. D. F. Wong, and Y.-W. Chang, “Flip-Chip Routing with Unified Area-I/O Pad Assignments for Package-Board Co-Design,” in Proc. of DAC, San Francisco, CA, July 2009, pp. 336–339.
[8] B.-Q. Lin, T.-C. Lin, and Y.-W. Chang, “Redistribution Layer Routing for
Integrated Fan-Out Wafer-Level Chip-Scale Packages,” in Proc. of ICCAD,
Austin, TX, November 2016, pp. 1–8.
[9] H.-T. Wen, Y.-J. Cai, Y. Hsu, and Y.-W. Chang, “Via-Based Redistribution
Layer Routing for InFO Packages with Irregular Pad Structures,” IEEE Trans.
Comput. Aided Des. Integr. 2022
[10] T. Yan and M. D. F. Wong. ”Correctly modeling the diagonal capacity in escape routing”. Ieee Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(2):285–293, 2012.
[11] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
[12] J. H. Lau, “Recent advances and trends in multiple system and heterogeneous integration with TSV-less interposers,” IEEE Trans. Compon., Packag., Manuf. Technol., vol. 12, no. 8, pp. 1271–1281, Aug. 2022,
[13] C.-F. Tseng, C.-S. Liu, C.-H. We, and D. Yu, “InFO (wafer level integrated
fan-out) technology,” in Proc. IEEE ECTC, 2016, pp. 1–6.
[14] S.-P. Jeng et al., “Integrated fan-out packages,” U.S. Patent 10 347 574, Mar.28, 2019.
[15] T.-C.Lin,D.Merrill,Y.-Y.Wu, C.Holtz, and C.-K.Cheng,“A unified printed circuit board routing algorithm with complicated constraints and differential
pairs,”26th Asia and South Pacific Design Automation Conf.,2021.
[16] Y.-J. Cai, Y. Hsu, and Y.-W. Chang, “Simultaneous Pre- and Free-Assignment Routing for Multiple Redistribution Layers with Irregular Vias,” in Proc. of DAC, San Francisco, CA, December 2021, pp. 1147–1152.
[17] Y.-T Chen, Y.-W. Chang, ”Obstacle-Avoiding Multiple Redistribution Layer Routing with Irregular Structures*,” in Proc. IEEE/ACM Int. Conf. Comput.- Aided Design (ICCAD), Nov. 2022.
[18] Gillies, S., and others. (2007). Shapely: manipulation and analysis of geometric objects. Retrieved from ”https://github.com/Toblerity/Shapely”