Timing-driven X-architecture routing tree construction among rectangular and non-rectangular obstacles
Abstract
In this paper, we formulate a new X-architecture routing problem in presence of non-rectangular obstacles, and propose an X-architecture timing-driven routing algorithm to minimize the maximum source-to-sink delay and the total wirelength simultaneously. First, a spanning graph is constructed by the terminals and the corners of the obstacles. A minimal spanning tree is then produced by performing searching algorithm to the spanning graph. The feasible X-architecture is constructed by transforming all slant edges of the minimal spanning tree. For the initial X-architecture routing tree, the delay of source-to-terminal is estimated by the modified Elmore delay model. According to the user defined delay threshold, an efficient rerouting algorithm is used to fix the timing violated nets. The critical terminals iteratively are rerouted by splitting two sub-trees and merging into one tree. Compared to the routing result without rerouting, the maximum source-to-sink delay is improved by 49.1% and only 2.5% of additional total wirlength is increased.
References
[1]
C. Chiang, Q. Su, and C.S. Chiang, "Wirelength Reduction by Using Diagonal Wire," in Proc. of ACM Great Lakes Symposium on VLSI, pp.104-107, 2003.
[2]
C.S. Coulston, "Constructing Exact Octagonal Steiner Minimal Trees," in Proc. of ACM Great Lakes Symposium on VLSI, pp.1-6, 2003.
[3]
C.M. Ko, Y.J. Huang, S.L. Fu, M.H. Guo, "MCM Placement Based on Multi-objective Optimization Approach," in WSEAS Transactions on Circuits and Systems, 2006, pp.753-758.
[4]
W. C. Elmore, "The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers," Journal of Applied Physics, Vol. 19, pp.55-63, 1948.
[5]
Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu and G. Yan, "An O(n log n) Algorithm for Obstacle-Avoiding Routing Tree Construction in the λ-Geometry Plane," in Proc. of ACM/IEEE International Symposium on Physical Design, pp. 48-55, 2005.
[6]
T.Y. Ho, C.F. Chang, Y.W. Chang, and S.J. Chen, "Multilevel Full-Chip Routing for the X-based Architecture," in Proc. of ACM/IEEE Design Automation Conference, pp. 597-602, 2005.
[7]
J. Hu and S. Sapatnekar, "A Timing- Constrained Algorithm for Simultaneous Global Routing of Multiple Nets," in Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp. 99-103, 2000.
[8]
H.H. Huang, T.F. Chiu, Y.C. Lin and T.M Hsieh, "Large-Scale Timing-Driven Rectilinear Steiner Tree Construction in Presence of Obstacles," in Proc. of IEEE International Midwest Symposium on Circuits and Systems, 2007.
[9]
H.H. Huang, H.Y. Huang, D.J. Huang and T.M. Hsieh, "An Obstacle-Avoiding Efficient Rectilinear Steiner Tree Construction," in WSEAS Transactions on Circuits and Systems, 2006, pp.1775-1782.
[10]
A.B. Kahng, I.I. Mandoiu and A.Z. Zelikovsky, "Highly Scalable Algorithm for Rectilinear and Octilinear Steiner Trees," in Proc. of ACM/IEEE Asia South Pacific Design Automation Conference, pp.827-833, 2003.
[11]
S. Lee and Martin D.F. Wong, "Timing-Driven Routing for FPGAs Based on Lagrangian Relaxation," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 506-511, 2003.
[12]
C.W. Lin, S.Y. Chen, C.F. Li, Y.W. Chang, and C.L. Yang, "Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction," in Proc. of ACM International Symposium on Physical Design, pp. 127-134, 2007.
[13]
S.P. Lin and Y. W. Chang, "A Novel Framework for Multilevel Routing Considering Routability and Performance," in Proc. of IEEE/ACM International Conference on Computer-Aided Design, pp. 44-50, 2002.
[14]
Y.C. Lin, H.H. Huang, C.C. Lin and T.M. Hsieh, "Optimal Assignment Approach for Low Power under Dual Voltages," in WSEAS Transactions on Circuits and System, 2008, pp.728-737.
[15]
M. Pan and C. Chu, "A Novel Performance-Driven Topology Design Algorithm," in Proc. of ACM/IEEE Asia and South Pacific Design Automation Conference, pp. 244-249, 2007.
[16]
Z. Shen, C.N. Chu and Y.M. Li, "Efficient Rectilinear Steiner Tree Construction with Rectilinear Blockages," in Proc. of IEEE International Conference on Computer Design, pp. 38-44, 2005.
[17]
W.X. Shen, Yici Ca, Jiang Hu, X.L. Hong, Bing Lu, "High Performance Clock Routing in X-architecture" in Proc. of IEEE International Symposium on Circuits and Systems, pp. 2081-2084, 2006.
[18]
S. Teig, "The X Architecture: Not Your Father's Diagonal Wiring," ACM International Workshop on System-Level Interconnect Prediction, pp. 33-37, 2002.
[19]
P.C. Wu, J.R. Gao and T.C. Wang, "A Fast and Stable Algorithm for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction," in Proc. of Asia and South Pacific Design Automation Conference, pp. 262-267, 2007.
[20]
Q. Zhu, H. Zhou, T. Jing, X.L. Hong, and Y. Yang, "Spanning Graph-Based Nonrectilinear Steiner Tree Algorithms," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp.1066-1075, 2005.
Recommendations
Timing-driven non-rectangular obstacles-avoiding routing algorithm for the X-architecture
IMCAS'09: Proceedings of the 8th WSEAS international conference on Instrumentation, measurement, circuits and systemsThis study formulates a novel timing-driven rectangular and non-rectangular obstacle-avoiding X-based Steiner minimal tree (TNOA-XSMT) problem. The problem is first studied in the literature, and solved by using a timing-driven routing algorithm. The ...
Multi-layer rectangular/non-rectangular bstacles-avoiding X-architecture router
ICC'08: Proceedings of the 12th WSEAS international conference on CircuitsDue to emerging DSM effects, routing has been a very important topic in current design flow. Currently there are three issues. One, the traditional Manhattan routing has longer length and larger delay than X-architecture routing. Second, in multilayer ...
A multi-layer obstacles-avoiding router using X-architecture
In recent years, scaling down device dimension or utilizing novel crystallization technologies provide the opportunity of applying much more devices to integrated circuit fabrication. Due to emerging DSM effects, the research about routing has drawn ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
World Scientific and Engineering Academy and Society (WSEAS)
Stevens Point, Wisconsin, United States
Publication History
Published: 01 June 2009
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in