More Web Proxy on the site http://driver.im/

Article

Free access

RISA: accurate and efficient placement routability modeling

Author:

Chih-Liang Eric ChengAuthors Info & Claims

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

Pages 690 - 695

Published: 06 November 1994 Publication History

Abstract

The prevalence of net list synthesis tools raises great concern on routability of cell placement created with state-of-the-art placement techniques. In this paper, an accurate and efficient placement routability modeling technique is proposed and incorporated into the prevailing simulated annealing approach. This accurate and efficient modeling is based on the supply versus demand analysis of routing resource over an array of regions on a chip. Vertical and horizontal routability is analyzed separately due to the bias of routing resource in multiple-metal-layer ASIC designs. A special technique on net bounding box partitioning is also proposed and critical to the accuracy of this modeling at the presence of mega cells, which tend to cause local routing congestion. By incorporating this efficient modeling into the cost function of simulated annealing, experiments conducted on small to large industrial designs indicate that placement routability evaluated with a global router is greatly improved as a result of the proposed accurate modeling.

References

[1]

U. Lauther, "A Min-cut Placement Algorithm for General Cell Assemblies Based on a Graph Representation", Proceedings of DAC, ppl-10, 1979

Digital Library

[2]

R.-S. Tsay, E. Kuh, and C.-E Hsu, "PROUD: A Sea-of-gates Placement Algorithm", IEEE Design & Test of Computers, pp44-56, 1988

Digital Library

[3]

J.M. Kleinhans, G. Sigl, and F.M. Johannes, "GORDIAN: A New Global Optimization Rectangle Dissection Method for Cell Placement", IEEE International Conf. on CAD, pp427-432, 1988

[4]

W.-J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE International Conf. on CAD, pp170-177, 1993

Digital Library

[5]

M. Burstein and S.J. Hong, "Hierarchical VLSI Layout: Simultaneous Placement and Wiring of Gate Arrays" In VLSI 1983, pp45-60, 1983

[6]

S. Mayrhofer and U. Lauther, "Congestion-Driven Placement Using a New Multi-partitioning Heuristic", IEEE International Conf. on CAD, pp332-335, 1990

[7]

R.-S Tsay, and S.C. Chang, "Early Wirability Checking and 2-D Congestion-Driven Circuit Placement", IEEE International Conf. on ASIC, 1992

[8]

Bryan Preas & Michael Lorenzetti, "Physical Design Automation of VLSI Systems", 1988, pp.96-97.

[9]

W.-J. Sun & C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE International Conference on CAD, 1993, pp.170-177

Digital Library

[10]

J. Soukup, "Circuit Layout", Proceedings of the IEEE, Vol.69, No.10, Oct. 1981.

[11]

G. Persky, "PRO - An Automatic String Placement Program for Polycell Layout", IEEE Proceedings of the 13th DAC., p.353-361, 1977

Digital Library

[12]

E G. Karger & M. Malek."Formulation of Component Placement as a Constrained Optimization Problem", Proceedings of the ICCAD., p.814-819, 1984

[13]

J. Jung, S. Goto & H. Hirayama, "A New Approach to the Twodimensional Placement of Wire Congestion in Master-Slice LSI Layout Design", Trans. Inst. of Electronics and Communications Engineers of Japan, vol J64-A, No.l, p55-62, 1981

[14]

S. Goto & T. Mitsuda, "Partitioning, Assignment and Placement", Advances in CAD for VLSI, Vol. 4: Layout Design and Verification, T. Ohtsuki, ed., Amsterdam, the Netherlands, North Holland, Chapter 5, 1986.

[15]

Y.-C. Wei, "Circuit Partitioning and its Applications to VLSI Designs", Ph.D Thesis, UCSD CSE Dept.,September 1990.

Digital Library

Cited By

Kahng AMoyes CVenkatesh SWang LChu CBustany I(2018)Wot the LProceedings of the 2018 International Symposium on Physical Design10.1145/3177540.3178238(2-9)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3177540.3178238
Chen GPui CChow WLam KKuang JYoung EYu B(2018)RippleFPGAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277805837:10(2022-2035)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2778058
Asghar AParvez H(2016)An improved diffusion based placement algorithm for reducing interconnect demand in congested regions of FPGAsInternational Journal of Reconfigurable Computing10.1155/2015/7560142015(8-8)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2015/756014
Show More Cited By

Index Terms

RISA: accurate and efficient placement routability modeling
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

GPlace3.0: Routability-Driven Analytic Placer for UltraScale FPGA Architectures

Optimizing for routability during FPGA placement is becoming increasingly important, as failure to spread and resolve congestion hotspots throughout the chip, especially in the case of large designs, may result in placements that either cannot be routed ...
MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation Conference

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
696
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)6

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kahng AMoyes CVenkatesh SWang LChu CBustany I(2018)Wot the LProceedings of the 2018 International Symposium on Physical Design10.1145/3177540.3178238(2-9)Online publication date: 25-Mar-2018
https://dl.acm.org/doi/10.1145/3177540.3178238
Chen GPui CChow WLam KKuang JYoung EYu B(2018)RippleFPGAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.277805837:10(2022-2035)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TCAD.2017.2778058
Asghar AParvez H(2016)An improved diffusion based placement algorithm for reducing interconnect demand in congested regions of FPGAsInternational Journal of Reconfigurable Computing10.1155/2015/7560142015(8-8)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2015/756014
Su JTu THe L(2016)A quantum annealing approach for boolean satisfiability problemProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2897973(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2897973
Yu YHe LChen DGreene J(2016)FPGA Power Estimation Using Automatic Feature Selection (Abstract Only)Proceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847327(282-282)Online publication date: 21-Feb-2016
https://dl.acm.org/doi/10.1145/2847263.2847327
Chen YChen SChang YChang Y(2014)Efficient and effective packing and analytical placement for large-scale heterogeneous FPGAsProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691497(647-654)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691497
Hahn Pereira ABetz VBetz VConstantinides G(2014)Cad and routing architecture for interposer-based multi-FPGA systemsProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554776(75-84)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554776
Liu HRajavel SAkoglu A(2013)Integration of Net-Length Factor with Timing- and Routability-Driven Clustering AlgorithmsACM Transactions on Reconfigurable Technology and Systems10.1145/25173246:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2517324
Das JWilton S(2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
https://dl.acm.org/doi/10.1145/2499625.2499627
Lin TBanerjee PChang Y(2013)An efficient and effective analytical placer for FPGAsProceedings of the 50th Annual Design Automation Conference10.1145/2463209.2488746(1-6)Online publication date: 29-May-2013
https://dl.acm.org/doi/10.1145/2463209.2488746
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents