EngineeringComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureField-programmable Gate ArraysConfigurable Logic BlocksField-programmable Gate Array ArchitectureFpga ArchitectureLogic SynthesisArea EfficiencyArea-efficient Fpga ArchitectureComputational Complexity Of AlgorithmsHardware MappingHeterogeneous Fpga ArchitecturesLookup Table ArchitecturesMapping AlgorithmsScalability
Cut enumeration is a common approach used in a number of FPGA synthesis and mapping algorithms for consideration of various possible LUT implementations at each node in a circuit. Such an approach is very general and flexible, but often suffers high computational complexity and poor scalability. In this paper, we develop several efficient and effective techniques on cut enumeration, ranking and pruning. These techniques lead to much better runtime and scalability of the cut-enumeration based algorithms; they can also be used to compute a tight lower-bound on the size of an area-minimum mapping solution. For area-oriented FPGA mapping, experimental results show that the new techniques lead to over 160X speed-up over the original optimal duplication-free mapping algorithm, achieve mapping solutions with 5-21% smaller area for heterogeneous FPGAs compared to those by Chortle-crf, MIS-pga-new, and TOS-TUM, yet with over 100X speed-up over MIS-pganew and TOS-TUM.
9
Improved logic synthesis algorithms for table look up architectures
Rajeev Murgai, Narendra Shenoy, Robert K. Brayton et al. · 2002 · 209 citations