IEEE/ACM International Conference on Computer-Aided Design · 1992 · 127 citations · 17 references
EngineeringComputer EngineeringComputer ScienceField-programmable Gate ArraysOptimizationReconfigurable ComputingConfigurable Logic BlocksField-programmable Gate Array ArchitectureFpga ArchitectureLookup TablesNetwork Flow AlgorithmsTiming AnalysisDelay OptimizationDepth ReductionLookup Table ArchitecturesLut Size OptimizationMinimum CutNetwork Flow ProblemsPolynomial-time AlgorithmsPolynomial-time Reductions
Presents a polynomial time technology mapping algorithm, called Flow-Map, that optimally solves the lookup-table (LUT)-based field-programmable gate array (FPGA) technology mapping problem for depth minimization for general Boolean networks. This theoretical breakthrough makes a sharp contrast with the fact that the conventional technology mapping problem in library-based designs is NP-hard. A key step in Flow-Map is to compute a minimum height K-feasible cut in a network, solved by network flow computation. The algorithm also effectively minimizes the number of LUTs by maximizing the volume of each cut and by several postprocessing operations. The Flow-Map algorithm was tested on a a set of benchmarks and achieved reductions of both the network depth and the number of LUTs in mapping solutions as compared with previous algorithms.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
17
Improved logic synthesis algorithms for table look up architectures
Rajeev Murgai, Narendra Shenoy, Robert K. Brayton et al. · 2002 · 209 citations