USING IF-THEN-ELSE DAGS TO DO TECHNOLOGY MAPPING FOR FIELD-PROGRAMMABLE GATE ARRAYS
Kevin J. Karplus · 1990
This paper presents two new algorithms for doing mapping from multi-level logic to field-programmable gate arrays. One algorithm, Xmap, is for mapping to table-lookup gates (for example, the Xilinx chip); the other, Amap, is for mapping to selector-based architectures (for example, the Actel chip). Mapping to the Actel architecture can also be achieved by mapping to 3-input tables, and replacing them with equivalent Actel cells (XAmap). The algorithms are based on an if-then-else DAG representation of the functions. The technology mappers differ from previous mappers in that the circuit is not decomposed into fan-out-free trees. The gate counts and CPU time are compared with three previous mappers for these architectures: misII, Chortle, and mis-pga. The Xmap algorithm for table-lookup architectures gets 7\% fewer cells than Chortle, 11\% fewer than misII, and 14\% fewer than mis-pga, and is 4.5 times faster than Chortle, 17 times faster than misII, and at least 150 times faster than mis-pga. The Amap algorithm for Actel cells use 6\% fewer cells than misII and about 8\% more cells than the best achieved by mis-pga, and is at least 25 times as fast as misII and at least 586 times as fast as mis-pga.