Optimality and Stability Study of Timing-Driven Placement Algorithms

ABSTRACT

This work studies the optimality and stability of timing-drivenplacement algorithms. The contributions of this work include twoparts: 1) We develop an algorithm for generating synthetic examples with known optimal delay for timing driven placement(T-PEKO). The examples generated by our algorithm can closelymatch the characteristics of real circuits. 2) Using these syntheticexamples with known optimal solutions, we studied the optimalityof several timing-driven placement algorithms for FPGAs by comparing their solutions with the optimal solutions, and their stability by varying the number of longest paths in the examples. Our study shows that with a single longest path, the delay produced by these algorithms is from 10% to 18% longer than the optima on the average, and from 34% to 53% longer in the worst case. Furthermore, their solution quality deteriorates as the number of longest paths increases. For examples with more than 5 longest paths, their delay is from 23% to 35% longer than the optima on the average, and is from 41% to 48% longer in the worst case.

References

1. {1} C. Chang, J. Cong, and M. Xie, "Optimality and scalability study of existing placement algorithms," in Proc. Asia South Pacific Design Automation Conference, pp. 621 - 627, 2003.
2. {2} J. Cong, M. Romesis, and M. Xie, "Optimality, scalability and stability study of partitioning and placement algorithms," in Proc. International Symposium on Physical Design, pp. 88 -94, 2003.
3. {3} M. Jackson and E. S. Kuh, "Performance-driven placement of cell based IC's," in Proc. Design Automation Conf., pp. 370-375, 1989.
4. {4} A. Srinivasan, K. Chaudhary, and E. S. Kuh, "RITUAL: A performance driven placement for small-cell ICs," in Proc. Int. Conf. on Computer Aided Design, pp. 48-51, 1991.
5. {5} T. Hamada, C. K. Cheng, and P. M. Chau, "Prime: a timing-driven placement tool using a piecewise linear resistive network approach," in Proc. Design Automation Conf., pp. 531- 536, 1993.
6. {6} A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F. Jukl, P. Kozak, and M. Wiesel, "Chip layout optimization using critical path weighting," in Proc. Design Automation Conf., pp. 133-136, 1984.
7. {7} R. Nair, C. L. Berman, P. Hauge, and E. J. Yoffa, "Generation of performance constraints for layout," IEEE Trans. on Computer-Aided Design, vol. 8, no. 8, pp. 860-874, 1989.
8. {8} R. S. Tsay and J. Koehl, "An analytic net weighting approach for performance optimization in circuit placement," in Proc. Design Automation Conf., pp. 620-625, 1991.
9. {9} H. Eisenmann and F. M. Johannes, "Generic global placement and floorplanning," in Proc. Design Automation Conf., pp. 269-274, 1998.
10. {10} M. Hutton, J. P. Grossman, J. Rose, and D. Corneil, "Characterization and parameterized random generation of digital circuits," in Proc. Design Automation Conf., pp. 94-99, ACM Press, 1996.
11. {11} P. Verplaetse, D. Stroobandt, and J. Van Campenhout, "Synthetic benchmark circuits for timing-driven physical design applications," in Proc. International Conference on VLSI, pp. 31-37, CSREA Press, 2002.
12. {12} W. C. Elmore, "The Transient Response of Damped Linear Networks," Journal of Applied Physics, vol. 19, pp. 55-63, 1948.
13. {13} J. Cong, and D. Pan, "Interconnect delay estimation models for synthesis and design planning," in Asia Pacific Design Automation Conference, pp. 97-100, 1999.
14. {14} R. Hitchcock, G. Smith, and D. Cheng, "Timing Analysis of Computer Hardware," IBM J. Res. Develop., vol. 26, pp. 100-108, 1982.
15. {15} Xilinx Inc., Virtex 2.5V FPGA Complete Data Sheet (all four Modules).
16. {16} A. Marquardt, V. Betz, and J. Rose, "Timing-driven placement for FPGAs," in Proc. of the ACM/SIGDA international symposium on Field programmable gate arrays, pp. 203- 213, ACM Press, 2000.
17. {17} http://cadlab.cs.ucla.edu/~pubbench/tpeko.htm.
18. {18} V. Betz and J. Rose, "VPR: A New Packing, Placement and Routing Tool for FPGA Research," in Proc. of Seventh International Workshop on Field-Programmable Logic and Applications , pp. 213-222, 1997.
19. {19} V. Betz, J. Rose, and A. Marquardt, Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Publishers, 1999.
20. {20} http://www.eecg.toronto.edu/~vaghn/vpr/vpr.html.
21. {21} T. Kong, "A novel net weighting algorithm for timing-driven placement," in Proc. Intl. Conf. on Computer-Aided Design, pp. 172-176, 2002.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • Buses and high-speed links

  • Very large scale integration design

    • Application-specific VLSI designs

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms