Exact tree-based FPGA technology mapping for logic blocks with independent LUTs

ABSTRACT

The logic blocks (CLBs) of a lookup table (LUT) based FPGA consist of one or more LUTs, possibly of different sizes. In this paper, we focus on technology mapping for CLBs with several independent LUTs of two different sizes (called ICLBs). The Actel ES6500 family is an example of a class of commercially available ICLBs. Given a tree network with n nodes, the only previously known approach for minimum area tree-based mapping to ICLBs was a heuristic with running time &THgr;(nd+1, where d is the maximum indegree of any node. We give an O(n3) time exact algorithm for mapping a given tree network, an improvement over this heuristic in terms of run time and the solution quality. For general networks, an effective strategy is to break it into trees and combine them. We also give an O(n3) exact algorithm for combining the optimal solutions to these trees, under the condition that LUTs do not go across trees. The method can be extended to solve mapping onto CLBs that can be configured into different ICLBs, (e.g. Xilinx' XC4000E).

REFERENCES

• 1: Actel. Actel's Reprogrammable SPGAs. Preliminary Advance Information, Oct. 1996.
• 2: Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996 [doi>10.1145/233539.233540]
• 3: A. Fanahi and M. Sarrafzadeh. Complexity of the lookuptable minimization problem for FPGA technology mapping. IEEE Trans. CAD/ICAS, 13( 11):1319-1332, 1994.
• 4: Robert Francis , Jonathan Rose , Zvonko Vranesic, Chortle-crf: Fast technology mapping for lookup table-based FPGAs, Proceedings of the 28th conference on ACM/IEEE design automation, p.227-233, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127670]
• 5: d He and d Rose. Technology mapping for heterogeneous FPGAs. In Proc. of A CM/SIGDA Intl. Workshop on FP- GAs, 1994.
• 6: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 7: M. Korupolu , K. K. Lee , D. F. Wong, FPGA Technology Mapping Using Logic Blocks with Independent LUTs, University of Texas at Austin, Austin, TX, 1998
• 8: Shashidhar Thakur , D. F. Wong, Simultaneous area and delay minimum K-LUT mapping for K-exact networks, Integration, the VLSI Journal, v.20 n.3, p.287-302, July 1996 [doi>10.1016/0167-9260(96)00004-1]
• 9: Xilinx, XCa000E and XC4000X Series (EX/XL) Field Programmable Gate Arrays. data sheet, drm 1997.
• 10: S. Zhang, Michael D. Miller, and Jon C. Muzio. Notes on Complexity of the Lookup-Table Minimization Problem for Flea Technology Mapping. IEEE Trans. CAD/ICAS, 15(12):1588-1590, De~ 1996.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Measurement, Performance, Theory