Simultaneous timing-driven placement and duplication

ABSTRACT

Logic duplication is an effective method for improving circuit performance. In this paper we present an algorithm named SPD that performs simultaneous placement and duplication to minimize the longest path delay. We introduce the notion of feasible region and super feasible region to improve the critical path monotonicity from a global perspective. We introduce a constrained gain graph to perform optimal incremental legalization under complex constraints. We also formulate a timing-constrained global redundancy removal problem and propose a heuristic solution. Our SPD algorithm outperforms the state-of-the-art FPGA placement flow (T-VPack + VPR) with an average reduction of up to 27% in longest path estimate delay and 18% in routed delay. The increase in overall runtime is less than 2% and the increase in area is less than 1%.

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: 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
• 3: G. Chen and J. Cong, "Simultaneous Timing Driven Clustering and Placement for FPGAs," Proc. International Conference on Field Programmable Logic and Its Applications, Antwerp, Belgium, pp. 158--167, August 2004.
• 4: J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," IEEE Trans. on Computer-Aided Design, vol. 13, no. 1, pp. 1--12, January 1994.
• 5: 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]
• 6: 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
• 7: Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774597]
• 8: J. Lillis, C.-K. Cheng and T.-T. Y. Lin, "Algorithms for Optimal Introduction of Redundant Logic for Timing and Area Optimization," Proc. IEEE International Symposium on Circuits and Systems, pp. 196--201, 1996.
• 9: Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
• 10: 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]
• 11: 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
• 12: E. Sentovich, K. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. Stephan, R. Brayton and A. Sangiovanni-Vincentelli, "SIS: A System for Sequential Circuit Synthesis," Electronics Research Laboratory, Memorandum No. UCB/ERL M92/41, 1992.
• 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
• 14: http://www.eecg.toronton.edu/~vaughn/challenge/challenge.html, "The FPGA Place-and-Route Challenge".

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, legalization, logic duplication, redundancy removal, timing-driven placement