Placement-driven technology mapping for LUT-based FPGAs

ABSTRACT

In this paper, we study the problem of placement-driven technology mapping for table-lookup based FPGA architectures to optimize circuit performance. Early work on technology mapping for FPGAs such as Chortle-d[14] and Flowmap[3] aim to optimize the depth of the mapped solution without consideration of interconnect delay. Later works such as Flowmap-d[7], Bias-Clus[4] and EdgeMap consider interconnect delays during mapping, but do not take into consideration the effects of their mapping solution on the final placement. Our work focuses on the interaction between the mapping and placement stages. First, the interconnect delay information is estimated from the placement, and used during the labeling process. A placement-based mapping solution which considers both global cell congestion and local cell congestion is then developed. Finally, a legalization step and detailed placement is performed to realize the design. We have implemented our algorithm in a LUT based FPGA technology mapping package named PDM (Placement-Driven Mapping) and tested the implementation on a set of MCNC benchmarks. We use the tool VPR[1][2] for placement and routing of the mapped netlist. Experimental results show the longest path delay on a set of large MCNC benchmarks decreased by 12.3% on the average.

REFERENCES

• 1: 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]
• 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: Jason Cong , Yuzheng Ding, An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.48-53, November 1992, Santa Clara, California, United States
• 4: A. Mathur and C. L. Liu. "Performance-driven technology mapping for lookup-table based FPGAs using the general delay model," Proceedings of International ACM/SIGDA Workshop on FPGAs, Feb 1994.
• 5: Jinan Lou , Amir H. Salek , Massoud Pedram, An exact solution to simultaneous technology mapping and linear placement problem, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.671-675, November 09-13, 1997, San Jose, California, United States
• 6: J. Cong and Y. Ding, "On area/depth trade-off in LUT-based FPGA technology mapping," IEEE Transactions on VLSI Systems, Vol. 2, June 1994.
• 7: J. Cong, Y. Ding, T. Gao and K. C. Chen, "LUT-based FPGA technology mapping under arbitrary net-delay model," Computers and Graphics, vol. 18, no. 4, pp. 507--516, 1994.
• 8: Jason Cong , Yean-Yow Hwang, Simultaneous depth and area minimization in LUT-based FPGA mapping, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.68-74, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201322]
• 9: Honghua Yang , D. F. Wong, Edge-map: optimal performance driven technology mapping for iterative LUT based FPGA designs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.150-155, November 06-10, 1994, San Jose, California, United States
• 10: 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]
• 11: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton and A. Sangiovanni-Vincentelli, "SIS: A system for sequential circuit synthesis", Memorandum No. UCB/ERL M92/41, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, May 1992.
• 12: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 13: Kuang-Chien Chen , Jason Cong , Yuzheng Ding , Andrew B. Kahng , Peter Trajmar, DAG-Map: Graph-Based FPGA Technology Mapping for Delay Optimization, IEEE Design & Test, v.9 n.3, p.7-20, July 1992 [doi>10.1109/54.156154]
• 14: R. J. Francis, J. Rose and Z. Vranesic, "Technology mapping of lookup table-based FPGAs for performance," Proceedings of IEEE International Conference on CAD, pp. 568--571, Nov. 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA synthesis, logic re-synthesis, mapping