Timing closure based on physical hierarchy

ABSTRACT

In this paper, we shall present the progress and results of the ongoing project at UCLA on synthesis and optimization under physical hierarchy. First, we shall motivate our approach by pointing out the limitations of the existing approach to interconnect planning based on early RTL floorplanning following logic hierarchy. Then, we shall discuss the technical challenges for synthesis under the physical hierarchy, including handling high computational complexity from the flattened logic hierarchy, needs of retiming and pipelining over global interconnects, and extension of existing synthesis operations. Finally, we shall outline our approaches to overcome these technical challenges.

REFERENCES

• 1: Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 1999.
• 2: Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 1997.
• 3: Cong, J., He, L., Koh, C.-K., Pan, D. Z., and Yuan, X. Tree-Repeater-Interconnect-Optimization Package (TRIO), 1999, http://cadlab.cs.ucla.edu/~trio.
• 4: Cong, J. An Interconnect-centric Design Flow for Nanometer Technologies, in Proceedings of the IEEE, vol. 89, 505--527, April 2001.
• 5: Brandt, A., Multi-level Adaptive Solution to Boundary Value Problems, Mathematics of Computation, vol.31, no.138, 333--390, 1977.
• 6: Briggs, W., A Multigrid Tutorial, SIAM, 1987.
• 7: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.69-79, March 1999 [doi>10.1109/92.748202]
• 8: Jason Cong , Sung Kyu Lim , Chang Wu, Performance driven multi-level and multiway partitioning with retiming, Proceedings of the 37th conference on Design automation, p.274-279, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337418]
• 9: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: Kleinhans, J., Sigl, G., Johannes, F., and Antreich, K. GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.10, March 1991.
• 11: Chin-Chih Chang , Jason Cong , Zhigang (David) Pan, Physical hierarchy generation with routing congestion control, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505399]
• 12: Pan, P., Karandikar, A. K., and Liu, C.-L. Optimal Clock Period Clustering for Sequential Circuits with Retiming, IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 489--498, 1998.
• 13: Jason Cong , Sung Kyu Lim, Physical planning with retiming, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 14: Cong, J., and Ding, Y. On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping, IEEE Trans. on VLSI Systems, vol. 2, no. 2, 137--148, June 1994.
• 15: Honghua Yang , D. F. Wong, Edge-map: optimal performance driven technology mapping for iterative LUT based FPGA designs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.150-155, November 06-10, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
interconnect optimization, interconnect planning, logic hierarchy, multilevel optimization, physical hierarchy, retiming and pipelining, sequential arrival time, timing closure