Modeling layout tools to derive forward estimates of area and delay at the RTL level

ABSTRACT

Forward estimates of area and delay facilitate effective decision-making when searching the solution space of digital designs. Current estimation techniques focus on modeling the layout result and fail to deliver timely or accurate estimates. This paper presents a novel approach to deriving these area and delay estimates at the RTL level by modeling the layout tool, rather than the layout result. This approach uses machine learning techniques to capture the relationships between general design features (i.e., topology, connectivity, common input, and common output) and layout concepts (i.e., relative placement). Experiments illustrate the formulation of the training set for machine learning in this domain, and also show how we can derive different tool models. Finally, they show how we can use the resultant model to derive forward estimates of area and delay in real-world designs.

REFERENCES

• 1: BREUER, M. 1977. Min-cut placement. J. Des. Autom. Fault-Tolerant Comput., 343-362.
• 2: BUCHANAN, B. AND SHORTLIFFE, E. 1984. Rule-Based Expert Systems. Addison-Wesley, Reading, MA.
• 3: HAKIMI, S. 1971. Steiner's problem in graphs and its implications. Networks 1, 113-133.
• 4: HSIEH, Y. -W. 1992. Architectural synthesis via VHDL. Master's Thesis. University of Pittsburgh, Pittsburgh, PA.
• 5: M. J. Irwin , R. M. Owens, A comparison of four two-dimensional gate matrix layout tools, Proceedings of the 26th ACM/IEEE conference on Design automation, p.698-701, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74507]
• 6: JAIN, R., PARKER, A. C., AND PARK, N. 1992. Predicting system-level area and delay for pipelined and non-pipelined designs. IEEE Trans. Comput.-Aided Des. 12, 8 (Aug.).
• 7: Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
• 8: Soohong Kim, CMOS VLSI layout synthesis for circuit performance, Pennsylvania State University, University Park, PA, 1992
• 9: KNAPP, D.W. 1992. FASOLT: A program for feedback-driven data-path optimization. IEEE Trans. Comput.-Aided Des. 11, 6 (June), 677-695.
• 10: KURDAHI, F. J. AND PARKER, A. C. 1989. Techniques for area estimation of VLSI layouts. IEEE Trans. Comput.-Aided Des. 8, 1 (Jan.), 81-92.
• 11: LANDMAN, B. AND RUSSO, R. 1971. On a pin versus block relationship for partition of logic graphs. IEEE Trans. Comput. C-20 (Apr.).
• 12: U. Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Papers on Twenty-five years of electronic design automation, p.182-191, June 1988 [doi>10.1145/62882.62901]
• 13: Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: Mehrdad Nourani , Christos Papachristou, A layout estimation algorithm for RTL datapaths, Proceedings of the 30th international conference on Design automation, p.285-291, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164895]
• 15: John Foster Provost, Policies for the selection of bias in inductive machine learning, University of Pittsburgh, Pittsburgh, PA, 1992
• 16: RAMACHANDRAN, C. AND KURDAHI, F.g. 1992a. TELE: A timing evaluator using layout estimation for high level applications. In Proceedings of the European Conference on Design Automation (EDAC '92, Brussels, Belgium, Mar. 16 - 19), IEEE Computer Society Press, Los Alamitos, CA, 137-141.
• 17: Champaka Ramachandran , Fadi J. Kurdahi, Combined topological and functionality based delay estimation using a layout-driven approach for high level applications, Proceedings of the conference on European design automation, p.72-78, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 18: C. Ramachandran , F. J. Kurdahi , D. D. Gajski , A. C.-H. Wu , V. Chaiyakul, Accurate layout area and delay modeling for system level design, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.355-361, November 1992, Santa Clara, California, United States
• 19: RUTENBAR, R.A. 1989. Simulated annealing algorithms: An overview. IEEE Circ. Dev. 5, 1 (Jan.), 19-26.
• 20: TERMAN, C. 1983. Simulation tools for digital LSI design. Ph.D. Dissertation. MIT Laboratory for Computer Science, Cambridge, MA.
• 21: Sholom M. Weiss , Casimir A. Kulikowski, Computer systems that learn: classification and prediction methods from statistics, neural nets, machine learning, and expert systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning
  I.6 SIMULATION AND MODELING

General Terms:
Design

Keywords:
VLSI CAD, estimation, estimation techniques, layout, machine learning