DAG-Map: graph-based FPGA technology mapping for delay optimization
- 1 September 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Design & Test of Computers
- Vol. 9 (3) , 7-20
- https://doi.org/10.1109/54.156154
Abstract
A graph-based technology-mapping package for delay optimization in lookup-table-based field programmable gate array (FPGA) designs is presented. The algorithm, DAG-Map, carries out technology mapping and delay optimization on the entire Boolean network, instead of decomposing it into fan-out-free trees. As a preprocessing phase of DAG-Map, a general algorithm called DMIG, which transforms an arbitrary n-node network into a two-input network with only an O(1) factor increase in network depth, is introduced. A matching-based technique that minimizes area without increasing network delay, and is used in the postprocessing phase of DAG-Map is discussed. DAG-Map is compared with previous FPGA mapping algorithms on a set of logic synthesis benchmarks. The experimental results show that, on average, DAG-Map reduces both network delay and the number of look-up tables.<>Keywords
This publication has 17 references indexed in Scilit:
- Improved logic synthesis algorithms for table look up architecturesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Performance directed synthesis for table look up programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A heuristic method for FPGA technology mapping based on the edge visibilityPublished by Association for Computing Machinery (ACM) ,1991
- A CAD system for the design of field programmable gate arraysPublished by Association for Computing Machinery (ACM) ,1991
- MIS: A Multiple-Level Logic Optimization SystemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- DAGON: technology binding and local optimization by DAG matchingPublished by Association for Computing Machinery (ACM) ,1987
- Bounding Fan-out in Logical NetworksJournal of the ACM, 1984
- Module Clustering to Minimize Delay in Digital NetworksIEEE Transactions on Computers, 1969
- Minimization Over Boolean GraphsIBM Journal of Research and Development, 1962
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952