WireMap: FPGA Technology Mapping for Improved Routability and Enhanced LUT Merging

ABSTRACT

This article presents a new technology mapper, WireMap. The mapper uses an edge flow heuristic to improve the routability of a mapped design. The heuristic is applied during the iterative mapping optimization to reduce the total number of pin-to-pin connections (or edges). On academic benchmark (ISCAS, MCNC, and ITC designs), the average edge reduction of 9.3% is achieved while maintaining depth and LUT count compared to state-of-the-art technology mapping. Placing and routing the resulting netlists leads to an 8.5% reduction in the total wirelength, a 6.0% reduction in minimum channel width, and a 2.3% reduction in critical path delay. This technique is applied in the Xilinx ISE Design tool to evaluate its effect on industrial Virtex5 circuits. In a set of 20 large designs, we find the edge reduction is 6.8% while total wirelength measured in the placer is reduced by 3.6%. Applying WireMap has an additional advantage of reducing an average number of inputs of LUTs without increasing the total LUT count and depth. The percentages of 5- and 6-LUTs in a typical design are reduced, while the percentages of 2-, 3-, and 4-LUTs are increased. These smaller LUTs can be merged into pairs and implemented using the dual-output LUT structure found in commercial FPGAs. For academic benchmarks, WireMap leads to 9.4% fewer dual-output LUTs after merging. For the industrial designs, WireMap leads to 6.3% fewer dual-output Virtex5 LUTs.

REFERENCES

• 1: Taneem Ahmed , Paul D. Kundarewich , Jason H. Anderson , Brad L. Taylor , Rajat Aggarwal, Architecture-specific packing for virtex-5 FPGAs, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA [doi>10.1145/1344671.1344675]
• 2: Altera. 2008. Stratix III device handbook. http://www.altera.com/literature/hb/stx3/stratix3_handbook.pdf.
• 3: Altera. 2004. Improving FPGA performance and area using an adaptive logic module. http://www.altera.com/literature/cp/cp-01004.pdf.
• 4: Berkeley Logic Synthesis and Verification Group. 2007. ABC: A system for sequential synthesis and verification, release 61225. http://www.eecs.berkeley.edu/~alanmi/abc/.
• 5: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 6: S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA
• 7: 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]
• 8: Cong, J. and Ding, Y. 1994. FlowMap: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs. IEEE Trans. Comput.-Aided Des. 13, 1, 1--12.
• 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: Gupta, S., Anderson, A., Farragher, L., and Wang, Q. 2007. CAD techniques for power optimization in Virtex-5 FPGAs. In Proceedings of the Custom Integrated Circuits Conference. 85--88.
• 11: Andrew B. Kahng , Sherief Reda, A tale of two nets: studies of wirelength progression in physical design, Proceedings of the 2006 international workshop on System-level interconnect prediction, March 04-05, 2006, Munich, Germany [doi>10.1145/1117278.1117282]
• 12: Lehman, E., Watanabe, Y., Grodstein, J., and Harkness, H. 1997. Logic decomposition during technology mapping. IEEE Trans. Comput.-Aided Des. 16, 8, 813--833.
• 13: Manohararajah, V., Brown, S. D., and Vranesic, Z. G. 2004. Heuristics for area minimization in LUT-based FPGA technology mapping. In Proceedings of the International Workshop on Logic and Synthesis (IWLS’04). 14--21.
• 14: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, Improvements to technology mapping for LUT-based FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117208]
• 15: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, DAG-aware AIG rewriting a fresh look at combinational logic synthesis, Proceedings of the 43rd annual Design Automation Conference, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147048]
• 16: Mishchenko, A., Brayton, R., Jiang, J.-H. R., and Jang, S. 2007a. SAT-Based logic optimization and resynthesis. In Proceedings of the International Workshop on Logic and Synthesis (IWLS’07). 358--364.
• 17: Alan Mishchenko , Sungmin Cho , Satrajit Chatterjee , Robert Brayton, Combinational and sequential mapping with priority cuts, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 18: Rajeev Murgai , Yoshihito Nishizaki , Narendra Shenoy , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, Logic synthesis for programmable gate arrays, Proceedings of the 27th ACM/IEEE Design Automation Conference, p.620-625, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123421]
• 19: Peichen Pan , Chih-Chang Lin, A new retiming-based technology mapping algorithm for LUT-based FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.35-42, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275118]
• 20: Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. R., Brayton, R., and Sangiovanni-Vincentelli, A. 1992. SIS: A system for sequential circuit synthesis. Memo. UCB/ERL M92/41, Department of Electrical Engineering and Computer Science, University of California, Berkeley. May.
• 21: Xilinx. 2006. Achieving higher system performance with the Virtex-5 family of FPGAs. http://www.xilinx.com/support/documentation/white_papers/wp245.pdf.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA, area flow, cut enumeration, edge flow, technology mapping