Timing constraint-driven technology mapping for FPGAs considering false paths and multi-clock domains

ABSTRACT

Modern FPGA chips contain multiple dedicated clocking networks, because nearly all real designs contain multiple clock domains. In this paper, we present an FPGA technology mapping algorithm targeting designs with multi-clock domains such as those containing multi-clocks, multi-cycle paths, and false paths. We use timing constraints to handle these unique clocking issues. We work on timing constraint graphs and process multiple arrival/required times for each node in the gate-level netlist. We also recognize and process constraint conflicts efficiently. Our algorithm produces a mapped circuit with the optimal mapping depth under timing constraints. To the best of our knowledge, this is the first FPGA mapping algorithm working with multi-clock domains. Experiments show that our algorithm is able to improve circuit performance by 16.8% on average after placement and routing for a set of benchmarks with multi-cycle paths, comparing to a previously published depth-optimal algorithm that does not consider multi-cycle paths.

REFERENCES

• 1: Mike Hutton , David Karchmer , Bryan Archell , Jason Govig, Efficient static timing analysis and applications using edge masks, 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.1046215]
• 2: J. Benkoski et al. Timing verification using statically sensitizable paths. TCAD, 9(10):1073--1084, 1990.
• 3: D. H. Du , S. H. Yen , S. Ghanta, On the general false path problem in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.555-560, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74475]
• 4: S. Perremans , L. Claesen , H. De Man, Static timing analysis of dynamically sensitizable paths, Proceedings of the 26th ACM/IEEE conference on Design automation, p.568-573, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74477]
• 5: P. C. McGeer , R. K. Brayton, Efficient algorithms for computing the longest viable path in a combinational network, Proceedings of the 26th ACM/IEEE conference on Design automation, p.561-567, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74476]
• 6: D. Brand and V. S. Iyengar. Timing analysis using functional analysis. Technical report, BM Thomas J. Watson Res. Center, 1986.
• 7: H.-C. Chen and D. H. C. Du. Path sensitization in critical path problem. TCAD, 12(2):196--207, 1993.
• 8: Anurag P. Gupta , Daniel P. Siewiorek, Automated multi-cycle symbolic timing verification of microprocessor-based designs, Proceedings of the 31st annual conference on Design automation, p.113-119, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196299]
• 9: Kazuhiro Nakamura , Kazuyoshi Takagi , Shinji Kimura , Katsumasa Watanabe, Waiting false path analysis of sequential logic circuits for performance optimization, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.392-395, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289059]
• 10: Kazuhiro Nakamura , Shinji Maruoka , Shinji Kimura , Katsumasa Watanabe, Multi-clock path analysis using propositional satisfiability, Proceedings of the 2000 conference on Asia South Pacific design automation, p.81-86, January 2000, Yokohama, Japan [doi>10.1145/368434.368533]
• 11: Krishna P. Belkhale , Alexander J. Suess, Timing analysis with known false sub graphs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.736-740, November 05-09, 1995, San Jose, California, United States
• 12: Eugene Goldberg , Alexander Saldanha, Timing Analysis with Implicitly Specified False Paths, Proceedings of the 13th International Conference on VLSI Design, p.518, January 04-07, 2000
• 13: David Blaauw , Rajendran Panda , Abhijit Das, Removing user specified false paths from timing graphs, Proceedings of the 37th conference on Design automation, p.270-273, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337417]
• 14: Shuo Zhou , Bo Yao , Hongyu Chen , Yi Zhu , Chung-Kuan Cheng , Mike Hutton, Efficient static timing analysis using a unified framework for false paths and multi-cycle paths, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118317]
• 15: Altera StratixII Device. {online}http://www.altera.com/products/devices/stratix2/st2-index.jsp
• 16: Altera Quartus II Software. {online}http://www.altera.com/products/software/products/quartus2/qts-index.html
• 17: Xilinx ISE Software. {online}http://www.xilinx.com/ise/logicdesign_prod/foundation.htm
• 18: D. Chen , J. Cong, DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.752-759, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382677]
• 19: Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, November 09-13, 2003 [doi>10.1109/ICCAD.2003.106]
• 20: V. Manohararajah, S. D. Brown, and Z. G. Vranesic. Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping. TCAD, 25(11):2331--2340, 2006.
• 21: A. Mishchenko, S. Chatterjee, and R. K. Brayton. Improvements to Technology Mapping for LUT-Based FPGAs. TCAD, 26(2):240--253, 2007.
• 22: P. Ashar, S. Dey, and S. Malik. Exploiting multicycle false paths in the performance optimization of sequential logic circuits. TCAD, 14(9):1067--1075, 1995.