Potential-NRG: placement with incomplete data

ABSTRACT

T raditional placement problems are studied under a fully specified cell library and a complete netlist. Ho w ev er, in the first, e.g., 2 years of a 2-3 year microprocessor design cycle, the detailed netlist is una vailable. F or area and performance estimation, layout must nev ertheless be done with incomplete information. Another source of incompleteness comes from reuse of instances from earlier design generations; these instances and their parameters will c hange as the project evolves. The problem of placement with incomplete data (PID) can be abstracted as ha ving to place a circuit when pn% of the nets are missing. The key challenge in PID is how to add missing cells and nets. In this paper, tw o “patc hing-methods” for adding missing nets and cells are proposed. The methods are called abstraction and fusion. Experimental results are v ery in teresting and illurstrative. First, they sho w that PID is a difficult problem and an arbitrary (and perhaps intuitiv ely sound) method may not produce high-quality results. Experiments verify that the abstraction method is a very good predictor and that fusion is not because circuits produced by abstraction attain much of the properties of the original circuits. Summary Table 3 in Section 4 shows that when a circuit has 10% incompleteness, abstraction can predict the final total wirelength with an error of 5.8%, while fusion has a 67.8% error in predicting the wirelength in the same circuit.

REFERENCES

• 1: Hart Anway , Greg Farnham , Rebecca Reid, PLINT layout system for VLSI chips, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.449-452, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317927]
• 2: Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
• 3: M. A. Breuer. "Min-cut Placement". d Design Automation amrl Fault-Tolerant Computing, 1(4):343- 382, 1977.
• 4: C.K. Cheng and E. S. Kuh. "Module Placement Based on Resistive Network Optimization". IEEE Transactions on Computer Aided Design, 3(3):218 225, 1984.
• 5: 3,. E. Dunlop and B. W. KerniOan. "A Procedure for Placement of Standard Cell VLSI Circuits". IEEE Transactions on Computer Aided Design, 4( 1):92-98, January 1985.
• 6: C. P. Hsu , B. N. Tien , K. Chow , R. A. Perry , J. Tang, ALPS2: a standard cell layout system for double-layer metal technology, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.443-448, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317926]
• 7: Majid Sarrafzadeh , Maogang Wang, NRG: global and detailed placement, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.532-537, November 09-13, 1997, San Jose, California, United States
• 8: C. Sechen. VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, B. V., Deveuter, 'lhe Netherlands, 1988.
• 9: Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  C. Computer Systems Organization

  J. Computer Applications

General Terms:
Design, Experimentation, Measurement, Performance, Theory

Keywords:
congestion, global routing, quadratic placement, relaxed pins, routing models, supply-demand