Cited By
View all- Wu MChen HJou J(2011)Mixed non-rectangular block packing for non-Manhattan layout architectures2011 12th International Symposium on Quality Electronic Design10.1109/ISQED.2011.5770734(1-6)Online publication date: Mar-2011
X-architecture placement based on effective wire models
Pages 87 - 94
Abstract
In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the XHPWL model, and the X-Steiner wirelength (XStWL) model. For min-cut partitioning placement, we propose a generalized net-weighting method that can exactly model the wirelength after partitioning by the net weight. The net-weighting method is general and can be incorporated into any wire models such as the XHPWL and XStWL models. For analytical placement, we smooth the XHPWL function using log-sum-exp functions to facilitate analytical placement. Our study shows that both the XHPWL model and the XStWL model can reduce the X wirelength. In particular, our results reveal the effectiveness of the X architecture on wirelength reduction during placement and thus the importance of the study on the X-placement algorithms, which is different from the results given in the previous work that the X-architecture placement might not improve the X-routing wirelength over the Manhattan-architecture placement.
References
[1]
S. N. Adya, M. C. Yildiz, I. L. Markov, P. G. Villarrubia, P. N. Parakh, and P. H. Madden. Benchmarking for large-scale placement and beyond. IEEE Trans. Computer-Aided Design, 23(4):472--487, 2004.
[2]
A. R. Agnihotri, S. Ono, and P. H. Madden. Recursive bisection placement: Feng Shui 5.0 implementation details. In Proceedings of ACM International Symposium on Physical Design, pages 230--232, San Francisco, CA, Apr. 2005.
[3]
C. J. Alpert, J.-H. Huang, and A. B. Kahng. Multilevel circuit partitioning. IEEE Trans. Computer-Aided Design, 17(8):655--667, Aug. 1998.
[4]
Z. Cao, T. Jing, Y. Hu, Y. Shi, X. Hong, X. Hu, and G. Yan. DraXRouter: global routing in X-architecture with dynamic resource assignment. In Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, pages 618--623, Yokohama, Japan, Jan. 2006.
[5]
T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie. mPL6: Enhanced multilevel mixed-size placement. In Proceedings of ACM International Symposium on Physical Design, pages 212--214, San Jose, CA, Apr. 2006.
[6]
T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In Proceedings of ACM International Symposium on Physical Design, pages 185--192, San Francisco, CA, Apr. 2005.
[7]
H. Chen, C.-K. Cheng, A. B. Kahng, I. Mandoiu, and Q. Wang. Estimation of wirelength reduction for λ-geometry vs. Manhattan placement and routing. In Proceedings of System Level Interconnect Prediction Workshop, pages 71--76, Monterey, CA, Apr. 2003.
[8]
T.-C. Chen, Y.-W. Chang, and S.-C. Lin. IMF: Interconnect-driven multilevel floorplanning for large-scale building-module designs. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 159--164, San Jose, CA, Nov. 2005.
[9]
T.-C. Chen, T.-C. Hsu, Z.-W. Jiang, and Y.-W. Chang. NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs. In Proceedings of ACM International Symposium on Physical Design, pages 236--238, San Francisco, CA, Apr. 2005.
[10]
T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, and Y.-W. Chang. A high-quality mixed-size analytical placer considering preplaced blocks and density constraints. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, Nov. 2006.
[11]
H. Eisenmann and F. M. Johannes. Generic global placement and floorplanning. In Proceedings of ACM/IEEE Design Automation Conference, pages 269--274, June 1998.
[12]
C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proceedings of ACM/IEEE Design Automation Conference, pages 175--181, 1982.
[13]
T.-Y. Ho, C.-F. Chang, Y.-W. Chang, and S.-J. Chen. Multilevel full-chip routing for the X-based architecture. In Proceedings of ACM/IEEE Design Automation Conference, pages 597--602, Anaheim, CA, June 2005.
[14]
A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Trans. Computer-Aided Design, 24(5), May 2005.
[15]
A. B. Kahng and Q. Wang. A faster implementation of APlace. In Proceedings of ACM International Symposium on Physical Design, pages 218--220, San Jose, CA, Apr. 2006.
[16]
G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. In Proceedings of ACM/IEEE Design Automation Conference, pages 343--348, New Orleans, LA, June 1999.
[17]
B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49:291--307, Feb. 1970.
[18]
M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. Gordian: VLSI placement by quadratic programming and slicing optimization. IEEE Trans. Computer-Aided Design, 10(3):356--365, 1991.
[19]
W. C. Naylor, R. Donelly, and L. Sha. US patent 6,301,693: Non-linear optimization system and method for wire length and dealy optimization for an automatic electric circuit placer. 2001.
[20]
S. Ono, S. Tilak, and P. H. Madden. Bisection based placement for the X architecture. In Proceedings of IEEE/ACM Asia South Pacific Design Automation Conference, Yokohama, Japan, Jan. 2007 (to appear).
[21]
J. Roy, D. Papa, A. Ng, and I. Markov. Satisfying whitespace requirements in top-down placement. In Proceedings of ACM International Symposium on Physical Design, pages 206--208, San Jose, CA, Apr. 2006.
[22]
J. A. Roy, J. F. Lu, and I. L. Markov. Seeing the forest and the trees: Steiner wirelength optimization in placement. In Proceedings of ACM International Symposium on Physical Design, San Francisco, CA, Apr. 2005.
[23]
N. Selvakkumaran and G. Karypis. Theto - a fast and high-quality paritioning driven global placer. Technical Report 03-46, Dept of Computer Science and Engineering, Univeristy of Minnesota, Nov. 2003.
[24]
N. Selvakkumaran and G. Karypis. Theto - a fast and high-quality paritioning driven placement tool. Technical Report 04-40, Dept of Computer Science and Engineering, Univeristy of Minnesota, Oct. 2004.
[25]
T. Taghavi, X. Yang, B.-K. Choi, M. Wang, and M. Sarrafzadeh. Dragon2006: Blockage-aware congestion-controlling mixed-size placer. In Proceedings of ACM International Symposium on Physical Design, pages 209--211, San Jose, CA, Apr. 2006.
[26]
S. L. Teig. The X architecture: not your father's diagonal wiring. In Proceedings of System Level Interconnect Prediction Workshop, pages 33--38, San Diego, CA, Apr. 2002.
[27]
S. L. Teig and J. L. Ganley. US patent 6,848,091: Partitioning placement method and apparatus. 2002.
Index Terms
- X-architecture placement based on effective wire models
Recommendations
Effective Wire Models for X-Architecture Placement
In this paper, we derive the X-half-perimeter wirelength (XHPWL) model for X-architecture placement and explore the effects of three different wire models on X-architecture placement, including the Manhattan-half-perimeter wirelength (MHPWL) model, the ...
Seeing the forest and the trees: Steiner wirelength optimization in placemen
ISPD '06: Proceedings of the 2006 international symposium on Physical designWe show how to optimize Steiner-tree Wirelength (StWL) in global and detail placement without a significant runtime penalty, making the use of Half-Perimeter Wirelength unnecessary. Given that StWL correlates with Routed Wirelength (rWL) much better ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation ConferenceWe present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Comments
Information & Contributors
Information
Published In
March 2007
206 pages
Copyright © 2007 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 March 2007
Check for updates
Author Tags
Qualifiers
- Article
Conference
Acceptance Rates
Overall Acceptance Rate 62 of 172 submissions, 36%
Upcoming Conference
ISPD '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 260Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)1
Reflects downloads up to 14 Sep 2024
Other Metrics
Citations
Cited By
View all- Wu MChen HJou J(2011)Mixed non-rectangular block packing for non-Manhattan layout architectures2011 12th International Symposium on Quality Electronic Design10.1109/ISQED.2011.5770734(1-6)Online publication date: Mar-2011
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in