An approach to placement-coupled logic replication

ABSTRACT

We present a set of techniques for placement-coupled, timing-driven logic replication. Two components are at the core of the approach. First is an algorithm for optimal timing-driven fanin tree embedding; the algorithm is very general in that it can easily incorporate complex objective functions (e.g., placement costs) and can perform embedding on any graph-based target. Second we introduce the Replication Tree which allows us to induce large fanin trees from a given circuit which can then be optimized by the embedder. We have built an optimization engine around these two ideas and report promising results for the FPGA domain including clock period reductions of up to 36% compared with a timing-driven placement from VPR [12] and almost double the average improvement of local replication from [1]. These results are achieved with modest area and runtime overhead.

REFERENCES

• 1: Giancarlo Beraudo , John Lillis, Timing optimization of FPGA placements by logic replication, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775885]
• 2: 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]
• 3: 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
• 4: Srinivas Devadas , Abhijit Ghosh , Kurt Keutzer, Logic synthesis, McGraw-Hill, Inc., New York, NY, 1994
• 5: Miloš Hrkić , John Lillis, S-Tree: a technique for buffered routing tree synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514066]
• 6: M. Hrkić, J. Lillis, "Buffer Tree Synthesis With Consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost, Congestion and Blockages," IEEE Transactions on CAD, 2003.
• 7: 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
• 8: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• 9: 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.
• 10: L.T. Liu, M.T. Kuo, C.K. Cheng, T.C. Hu, "A Replication Cut for Two-Way Partitioning," IEEE Transactions on CAD, 1995.
• 11: W.K. Mak, D.F. Wong, "Minimum Replication Min-Cut Partitioning," IEEE Transactions on CAD, October 1997.
• 12: 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]
• 13: 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

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