Mapping for better than worst-case delays in LUT-based FPGA designs

ABSTRACT

Current advances in chip design and manufacturing have allowed IC manufacturing to approach the nanometer range. As the feature size scales down, greater variability is experienced, forcing designers to reduce performance requirements in order to reserve larger margins. Better than worst-case design can be used to address the variability problem, as well as breaking the performance limit set by the worst-case delay in the conventional design style, even without the consideration of delay variation. In this paper we will present a novel methodology for measuring and optimizing the performance of circuits to operate with the clock period smaller than the worst-case delay. We also develop a novel technology mapping algorithm that optimizes circuits under such a metric. Using our novel mapping algorithm named BTWMap (Better Than Worst-case Mapper) and its area-optimized version named BTWMap+area, we are able to improve the overall circuit latency by 13% and 11%, respectively

REFERENCES

• 1: Todd Austin , Valeria Bertacco , David Blaauw , Trevor Mudge, Opportunities and challenges for better than worst-case design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120878]
• 2: Todd Austin , Valeria Bertacco, Deployment of Better Than Worst-Case Design: Solutions and Needs, Proceedings of the 2005 International Conference on Computer Design, p.550-558, October 02-05, 2005 [doi>10.1109/ICCD.2005.43]
• 3: Michel R. C. M. Berkelaar , Jochen A. G. Jess, Gate sizing in MOS digital circuits with linear programming, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 4: Sanjukta Bhanja , N. Ranganathan, Swtiching activity estimation of VLSI circuits using Bayesian networks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.4, p.558-567, August 2003 [doi>10.1109/TVLSI.2003.816144]
• 5: Stephen P. Boyd , Seung-Jean Kim , Dinesh D. Patil , Mark A. Horowitz, Digital Circuit Optimization via Geometric Programming, Operations Research, v.53 n.6, p.899-932, November-December 2005 [doi>10.1287/opre.1050.0254]
• 6: 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]
• 7: J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs," IEEE Trans. Computer-Aided Design, pp. 1--12, 1994.
• 8: Jason Cong , John Peck , Yuzheng Ding, RASP: a general logic synthesis system for SRAM-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.137-143, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228390]
• 9: Jason Cong , Chang Wu , Yuzheng Ding, Cut ranking and pruning: enabling a general and efficient FPGA mapping solution, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.29-35, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296425]
• 10: Gregory F. Cooper, The computational complexity of probabilistic inference using Bayesian belief networks (research note), Artificial Intelligence, v.42 n.2-3, p.393-405, March 1990 [doi>10.1016/0004-3702(90)90060-D]
• 11: K. De and P. Banerjee, "PREST: A System for Logic Partitioning and Resynthesis for Testability," IEEE Transactions on Very Large Scale 1ntegration (VLSI) Systems, vol. 1, no. 4, pp. 514--525, Dec. 1993.
• 12: Dan Ernst , Nam Sung Kim , Shidhartha Das , Sanjay Pant , Rajeev Rao , Toan Pham , Conrad Ziesler , David Blaauw , Todd Austin , Krisztian Flautner , Trevor Mudge, Razor: A Low-Power Pipeline Based on Circuit-Level Timing Speculation, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.7, December 03-05, 2003
• 13: V. Manohararajah, S.D. Brown, and Z.G. Vranesic, "Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping," IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, vol. 25, no. 11, pp. 2331--2340, Nov. 2006.
• 14: A. Saldanha , A. R. Wang , R. K. Brayton , A. L. Sangiovanni-Vincentelli, Multi-level logic simplification using don't cares and filters, Proceedings of the 26th ACM/IEEE conference on Design automation, p.277-282, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74429]
• 15: W. Shi and Z. Li, "A fast algorithm for optimal buffer insertion," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 6, pp. 879--891, June 2005.
• 16: Berkeley Logic Synthesis and Verification Group, "ABC: A System for Sequential Synthesis and Verification," http://www.eecs.berkeley.edu/~alanmi/abc/

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA lookup table, better than worst-case, logic synthesis, razor, simulation, switching probabilities, technology mapping