由於有繞線資源的限制以及逐漸增加的設計規則，工程變更命令
的繞線工作是一個複雜且困難的工作，並且往往在較晚的設計階段
有被應用在最佳化電路的雜音與延遲的需求。在工程變更命令的繞
線過程之後，電路的佈局往往會因為金屬層被重繞的工程變更命令
線路使用到而改變，進而導致遮罩的重新製造並造成極高的成本花
費。然而，目前卻沒有任何工程變更命令的繞線器將繞線的重點著重
在繞線時使用到的層數。因此，我們提出了一個三階段的工程變更命
令繞線流程，並且能夠在考量將使用的層數最小化的情況下將所有
的工程變更命令線路同時繞線。　首先，針對每個工程變更命令線路
有效率的產生許多估計的繞線路徑，並且使用了一個整數線性規劃
的模組去對這些估計的繞線路徑以最小化改變的遮罩層數量為目的
去做選擇。此外，為了能夠更加減少改變的遮罩層數量，我們應用了
一個最小成本最大流量演算法來更加改善整數線性規劃的繞線結果。
實驗結果顯示我們提出的工程變更命令繞線流程能夠有效的減少繞
現實改變的遮罩層數量，並且以可接受的線長以及孔數的增加數量
完成所有工程變更命令線路的繞線。

Engineering Change Order (ECO) routing, which is a complicated and difficult
task due to limited routing resource and increasing design rules, is requested in
later design stage for the purpose of delay and noise optimization. After ECO routing
procedure, layout may be changed since layers are used by the re-routed ECO
nets and cause the mask re-spin which leads to an extremely high cost. However,
there is no existing ECO router focuses on minimizing the number of used layers.
Therefore, this thesis presents a three-stage ECO routing flow which can simultaneously
route all ECO nets while considering routing layer minimization. Initially,
several routing paths for each ECO net are efficiently estimated and an Integer
Linear Programming (ILP) model is developed to simultaneously determine the
routing path of each ECO net to minimize the number of changed masks. Moreover,
a Minimum-Cost-Maximum-Flow (MCMF) algorithm is applied to further
reduce the number of changed masks. Experimental results demonstrate that our
proposed ECO routing flow can effectively reduce the number of changed masks
with acceptable increasing wirelength and via count.

[1] L. Behjat and A. Chiang. Fast integer linear programming based models
for VLSI global routing. In IEEE International Symposium on Circuits and
Systems, pages 6238–6243, 2005.
[2] L. Behjat, A. Chiang, L. Rakai, and J. Li. An effective congestion-based integer
programming model for VLSI global routing. In Electrical and Computer
Engineering, 2008. CCECE 2008. Canadian Conference on, pages 931–936,
2008.
[3] J. Cong, J. Fang, and K.-Y. Khoo. An implicit connection graph maze routing
algorithm for ECO routing. In IEEE/ACM International Conference on
Computer-Aided Design, pages 163–167, 1999.
[4] J. Cong, J. Fang, and K.-Y. Khoo. DUNE: A multi-layer gridless routing
system with wire planning. In IEEE/ACM International Conference on
Computer-Aided Design, page 12, 2000.
[5] S.-Y. Fang, T.-F. Chien, and Y.-W. Chang. Redundant-wires-aware ECO
timing and mask cost optimization. In IEEE/ACM International Conference
on Computer-Aided Design, pages 381–386, 2010.
[6] http://www-01.ibm.com/software/integration/optimization/.
[7] C. Inc. SoC Encounter. [Online]. Available: http://www.cadence.com/products/
di/soc_encounter.
[8] Y.-L. Li, C. H.-Y., and L. C.-T. NEMO: A new implicit-connection-craphbased
gridless router with multilayer planes and pseudo tile propagation.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems, 26(4):705–718, 2007.
[9] Y.-L. Li, J.-Y. Li, and W.-B. Chen. An Efficient Tile-Based ECO Router
Using Routing Graph Reduction and Enhanced Global Routing Flow. IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems,
26(2):345–358, 2007.
[10] Y.-H. Lin, Y.-J. Lo, J.-S. Tong, W.-H. Liu, and Y.-L. Li. Topology-aware
buffer insertion and GPU-based massively parallel rerouting for ECO timing
optimization. In ACM/IEEE Asia and South Pacific Design Automation
Conference, pages 437–442, 2012.
[11] C.-H. Liu, I.-C. Chen, and D. T. Lee. An efficient algorithm for multi-layer
obstacle-avoiding rectilinear Steiner tree construction. In ACM/IEEE Design
Automation Conference, pages 613–622, 2012.
[12] J. K. Ousterhout. Corner Stitching: A Data-Structuring Technique for VLSI
Layout Tools. IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 3(1):87–100, 1984.
[13] Reports of the International Technology Roadmap for Semiconductors,. 2012,
http://www.itrs.net/.
[14] H. Shojaei, A. Davoodi, and P. Ramanathan. Confidentiality Preserving Integer
Programming for global routing. In Design Automation Conference
(DAC), 2012 49th ACM/EDAC/IEEE, pages 709–716, 2012.
[15] S. Q. Zheng, J. S. Lim, and S. S. Iyengar. Finding obstacle-avoiding shortest
paths using implicit connection graphs. IEEE Transactions on Computer-
Aided Design of Integrated Circuits and Systems, 15(1):103–110, 1996.
32