Techniques for improved placement-coupled logic replication

ABSTRACT

Several recent papers have utilized logic replication driven by placement-level timing analysis for improving clock period (e.g., [1], [8], [18], and [2]). All of these papers demonstrated, through various optimization strategies, the potential of the basic technique of replication. In this paper we propose a number of techniques aimed at more fully realizing this potential within the framework employed in [8]. As reported in [7], there are situations in which the approach of [8] fails to yield significant additional improvement due largely to the effects of reconvergence in the netlist. We suggest the use of rectilinear Steiner arborescence embedding as a tool for overcoming this limitation. We also propose techniques for fanout partitioning and cell relocation which are cognizant of both wirelength and timing impact for improved solution quality. We report the effect of other techniques including new replication cost computation, lower-bounding of achievable clock period, and wirelength estimation. We have implemented and experimented with these techniques in FPGA domain. In many cases we were able to approach a fixed flip-flop lower-bound on achievable clock period. Promising experimental results are reported with average 17.4% (up to 39.9%) delay reduction compared with the timing-driven placement from VPR[16] and average 9.3% (up to 37.2%) reduction compared with the basic fanin tree embedder from [8].

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: Miloš Hrkić , Miloš Hrkić , John Lillis , Giancarlo Beraudo, An approach to placement-coupled logic replication, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996761]
• 3: 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]
• 4: M. Hrkić and J. Lillis, "Addressing the Effects of Reconvergence on Placement-Coupled Logic Replication," IWLS, 2004.
• 5: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 6: A. Kahng and G. Robins, "On optimal Interconnections for VLSI," Kluwer Academic Publishers, 1995.
• 7: S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, "The Rectilinear Steiner Arborescence Problem," Algorithmica, 1992.
• 8: L. T. Liu, M. T. Kuo, C. K. Cheng, and T. C. Hu, "A Replication Cut for Two-Way Partitioning," IEEE Transaction on CAD, 1995.
• 9: W. K. Mak and D. F. Wong, "Minimum replication min-cut partitioning," IEEE Transaction on CAD, 1997.
• 10: J. Lillis, C.-K. Cheng, and T.-T Y. Lin, "Algorithms for Optimal Introduction of Redundant Logic for Timing and Area Optimization," IEEE ISCAD, 1995.
• 11: 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
• 12: 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]
• 13: 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
• 14: Yuji Kukimoto , Robert K. Brayton , Prashant Sawkar, Delay-optimal technology mapping by DAG covering, Proceedings of the 35th annual conference on Design automation, p.348-351, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277142]
• 15: 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]
• 16: Karl Schabas , Stephen D. Brown, Using logic duplication to improve performance in FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611838]
• 17: Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046200]
• 18: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 19: S.-W. Hur, A. Jagannathan, and J. Lillis, "Timing-Driven Maze Routing," IEEE Transaction on CAD, 2000.

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