An improved graph-based FPGA technology mapping algorithm for delay optimization

A graph-based technology mapping algorithm, called DAG-Map, for delay optimization in lookup-table-based field programmable gate array (FPGA) designs is presented. The algorithm carries out technology mapping and delay optimization on the entire Boolean network, instead of decomposing it into fanout-free trees and mapping each tree separately as in most previous algorithms. As a preprocessing step, a general algorithm that transforms an arbitrary n-input network into a two-input network with only O(1) factor increase in the network depth is introduced. Also presented is a graph-matching-based technique used as a postprocessing step which optimizes the area without increasing the delay. The DAG-Map algorithm was tested on the MCNC logic synthesis benchmarks. Compared with previous algorithms, it reduces both the network depth and the number of lookup-tables.< >