Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping
Abstract
In this paper, an iterative technology mapping tool called IMap is
presented. It supports depth-oriented (area is a secondary objective),
area-oriented (depth is a secondary objective), and duplication-free
mapping modes. The edge delay model (as opposed to the more commonly
used unit delay model) is used throughout. Two new heuristics are used
to obtain area reductions over previously published methods. The first
heuristic predicts the e®ects of various mapping decisions on the area
of the final solution and the second heuristic bounds the depth of the
mapping solution at each node. In depth-oriented mode, when targeting
5-LUTs, IMap obtains depth optimal solutions that are 44:4%, 19:4%,
and 5% smaller than those produced by FlowMap, CutMap, and DAOMap,
respectively. Targeting the same LUT size in area-oriented mode, IMap
obtains solutions that are 17:5% and 9:4% smaller than those produced
by duplication-free mapping and ZMap, respectively. IMap is also shown
to be highly e±cient. Runtime improvements of between 2:3x and 82x
are obtained over existing algorithms when targeting 5-LUTs. Area and
runtime results comparing IMap to the other mappers when targeting
4-LUTs and 6-LUTs are also presented.
Reference
Valavan Manohararajah, Stephen D. Brown, and Zvonko G. Vranesic, "Heuristics for Area Minimization in LUT-Based FPGA Technology Mapping", IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, Vol. 25, No. 11, November 2006, pp. 2331-2340.
(Download Full Paper)