相對於應用在數位積體電路上的電源與接地線繞線，類比積體電路上面的研究仍尚未成熟。傳統的類比電路電源與接地線繞線是使用人工的方式並且採用貪婪策略來進行繞線。然而，隨著類比積體電路設計規模越來越大，導致設計者在繞線過程中需要花費更多的時間，並使得以往所採取的貪婪策略變得十分沒有效率。此外，由於導線寬度的不足，過量的電流密度將導致類比電路上導線的電子漂移現象，而產生斷路和短路的情況，這將可能導致晶片的永久性故障。而導線過細，導致電阻上升的情況，將產生嚴重的電壓降情形，將導致類比電路的供電不足而促使性能下降，甚至導致功能錯誤。因此，在繞現階段必須考慮電流密度和導線電阻。在本篇論文中提出了一種自動化類比電路上的電源與接地線繞線器，並且同時考量電子漂移與電壓降的情況。在全面繞線階段，我們將電流考量避免電子漂移的直線史坦納樹問題，轉換成運輸問題，並計算出一個最佳解的最小線路面積繞線結果。根據最佳結果，我們將電線合併，用以提高可繞度及減輕擠塞情況。這個電線合併的步驟將釋放更多的可繞線區域;將提供更大的繞線區域，使我們在之後為了減少電壓降而採取的線寬拓展方式中，得到幫助。最後，在細部繞線步驟，我們求得一個可行的繞線解，之後使用線寬拓展方法來減少電壓降的情況。實驗結果證明的我們提出的方法可快速且有效率的求得繞線結果。

Compared with the Power/Ground (P/G) routing in digital ICs, the P/G routing in analog ICs has not yet been well researched. Traditional P/G routing in analog ICs adopts greedy strategies to route nets by analog designers. However, the growing scale of analog ICs leads human designers to cause a lot of time in the routing procedure and makes the greedy strategies ineffective. Furthermore, due to insufficient wire widths, the critical excessive current densities in analog ICs can cause a wire open and short (voids and hillocks) by electromigration. It may lead to the permanent failure of a circuit. And the finite resistance has detrimental impacts in the form of IR-drop; it would cause the analog ICs with insufficient power supply to decrease the performance or even lead the functional errors. Therefore, it is desirable to consider current densities and wire resistance in the routing stage. In this paper, an automatic analog P/G router considering electromigration and IR-drop is proposed. In the global routing stage, we model current-driven electromigration-aware rectilinear Steiner tree (CDEARST) problem as a transportation formulation and obtain an optimal solution with the minimum wire area. Based on the optimal solution, we bundle the wires to enhance the routability and alleviate congestions. The bundling step would free more routable areas; it helped us to expand the wire width for resistance decreasing and IR-drop reducing. Finally, in the detailed routing step, we obtain a routing solution and then wire width extension method is adopted to reduce IR-drop. Experimental results prove the effectiveness and efficiency of our algorithm.

[1] J. R. Black, "Electromigration - A Brief Survey and Some Recent Results." IEEE Trans Electron Devices, v16, no. 4, pp. 338-347, 1969.

[2] T. H. Cormen, C. E. Leiserson, R. E. Rivest, and C. Stein. "Introduction to Algorithms, 2nd ed.," MIT Press, 2001.

[3] R. Dutta, M. Marek-Sadowska, "Automatic Sizing of Power/Ground (P/G) Networks in VLSI." Proc. Design Automation Conference, pp.783-786, 1989.

[4] J.-M. Ho, G. Vijayan, C. K. Wong "New Algorithms for the Rectilinear Steiner Tree Problem." IEEE Trans. Computer-Aided Design, vol.9, no.2, pp. 185-193, 1990.

[5] I. H.-R. Jiang, H.-Y. Chang, C.-L. Chang, "Optimal Wiring Topology for Electromigration Avoidance Considering Multiple Layers and Obstacles." Proc. International Symposium on Physical Design, pp. 177-184,2010.

[6] J. Lienig, "Introduction to Electromigration-Aware Physical Design." Proc. International Symposium on Physical Design, pp. 39-46, 2006.

[7] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, "Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs," IEEE Trans. Computer-Aided Design, vol.27, no.4, pp. 643-653, 2008.

[8] J. Lienig and G. Jerke, "Current-Driven Wire Planning for Electromigration Avoidance in Analog Circuits." Proc. Asia and South paci c Design Automation Conference, pp. 783-788, 2003.

[9] E. J. Russell, "Extension of Dantzig's Algorithm to Finding an Initial Near-Optimal Basis for the Transportation Problem," Operations Reach,
vol.17, pp. 187-191, 1969.

[10] J. M. S. Silva, J. R. Phillips, L. M. Silveira, "Efficient Representation
and Analysis of Power Grids." Proc. Design, automation and test in Europe Conference, pp. 420-425, 2008.

[11] A. Todri, M. Marek-Sadowska, S.-C. Chang, "Analysis and Optimization of Power-Gated ICs with Multiple Power Gating Con gurations." Proc. International conference on Computer-aided design, pp. 783-790, 2007.

[12] W. L. Winston, "Operations Reserach Applications and Algorithms, 4th ed.," Thomsom Brooks/Cole, 2004.

[13] J.-T. Yan and Z.-W. Chen, "Electromigration-Aware Rectilinear Steiner Tree Construction for Analog Circuits," Proc. Asia Paci c Conference on Circuits and Systems, pp. 1692-1695, 2008.