DocumentCode :
424371
Title :
DAOmap: a depth-optimal area optimization mapping algorithm for FPGA designs
Author :
Chen, Deming ; Cong, Jason
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fYear :
2004
fDate :
7-11 Nov. 2004
Firstpage :
752
Lastpage :
759
Abstract :
In This work we study the technology mapping problem for FPGA architectures to minimize chip area, or the total number of lookup tables (LUTs) of the mapped design, under the chip performance constraint. This is a well-studied topic and a very difficult task (NP-hard). The contributions of This work are as follows: (i) we consider the potential node duplications during the cut enumeration/generation procedure so the mapping costs encoded in the cuts drive the area-optimization objective more effectively; (ii) after the timing constraint is determined, we will relax the non-critical paths by searching the solution space considering both local and global optimality information to minimize mapping area; (iii) an iterative cut selection procedure is carried out that further explores and perturbs the solution space to improve solution quality. We guarantee optimal mapping depth under the unit delay model. Experimental results show that our mapping algorithm, named DAOmap, produces significant quality and runtime improvements. Compared to the state-of-the-art depth-optimal, area minimization mapping algorithm CutMap (Cong and Hwan, 1995), DAOmap is 16.02% better on area and runs 24.2X faster on average when both algorithms are mapping to FPGAs using LUTs of five inputs. LUTs of other inputs are also used for comparisons.
Keywords :
circuit complexity; field programmable gate arrays; logic design; minimisation; table lookup; CutMap; DAOmap; FPGA design; area minimization; chip performance constraint; depth-optimal area optimization mapping algorithm; iterative cut selection procedure; lookup tables; timing constraint; Algorithm design and analysis; Cost function; Delay; Design optimization; Field programmable gate arrays; Iterative algorithms; Minimization methods; Runtime; Table lookup; Timing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Aided Design, 2004. ICCAD-2004. IEEE/ACM International Conference on
ISSN :
1092-3152
Print_ISBN :
0-7803-8702-3
Type :
conf
DOI :
10.1109/ICCAD.2004.1382677
Filename :
1382677
Link To Document :
بازگشت