Timing optimization of FPGA placements by logic replication

ABSTRACT

Logic replication for placement level timing optimization is studied in the context of FPGAs. We make the observation that critical paths are dominated by interconnect delay and are frequently highly circuitous. We propose a systematic replication technique to "straighten" such paths. The resulting algorithm has several components: cell selection, slot selection for a duplicate cell, fanout partitioning and placement legalization. This algorithm is described and promising preliminary experimental results are reported with up to 29% improvement in critical path delay.

REFERENCES

• 1: L.T. Liu, M.T. Kuo, C.K. Cheng, and T.C. Hu. A Replication Cut for Two-Way Partitioning, IEEE Trans. on CAD, 1995
• 2: James Hwang , Abbas El Gamal, Optimal replication for min-cut partitioning, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.432-435, November 1992, Santa Clara, California, United States
• 3: W. K. Mak and D. F. Wong. Minimum replication min-cut partitioning. IEEE Transactions on CAD,. October 1997
• 4: C. Kring and A. Newton. A cell-Replicating Approach to Mincut-Based Circuit Partitioning. ICCAD 1991
• 5: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 6: J. Lillis, C.-K. Cheng, T.-T. Y. Lin. Algorithms for Optimal Introduction of Redundant Logic for Timing and Area Optimization. Proc. IEEE International Symposium on Circuits and Systems, 1996
• 7: Ankur Srivastava , Ryan Kastner , Majid Sarrafzadeh, Timing driven gate duplication: complexity issues and algorithms, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Sung Woo Hur , John Lillis, Mongrel: hybrid techniques for standard cell placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 9: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 10: Wilsin Gosti , Amit Narayan , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Wireplanning in logic synthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.26-33, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288556]
• 11: Wilsin Gosti , Sunil P. Khatri , Alberto L. Sangiovanni-Vincentelli, Addressing the timing closure problem by integrating logic optimization and placement, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: Ingmar Neumann , Dominik Stoffel , Hendrik Hartje , Wolfgang Kunz, Cell replication and redundancy elimination during placement for cycle time optimization, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.25-30, November 07-11, 1999, San Jose, California, United States

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
logic replication, placement, programmable logic, timing optimization