Decomposition strategies and their performance in FPGA-based technology mapping

Henry Selvaraj , Mirosława Nowicka , Tadeusz Łuba


Existing FPGA-oriented algorithms can be divided into two categories: minimising the number of LUTs in the solution (MIS-pga, Trade, and ASYL); and minimising the delay in the solution (DAG-Map, SWEEP, and Flow-map). Several algorithms have been implemented with both area and delay minimisation versions, for example MIS-pga and ASYL. Two collaborating groups from Warsaw University of Technology, Poland and Monash University, Australia have developed decomposition theory and procedures for single and multiple-output Boolean functions. These include a balanced decomposition algorithm which applies either parallel or serial decomposition at each phase of the synthesis process. The algorithm has been implemented in an experimental logic synthesis tool DEMAIN. Recent tests on MCNC and industrial benchmarks show that DEMAIN produces much more economical designs than major FPGA vendors software
Author Henry Selvaraj
Henry Selvaraj,,
, Mirosława Nowicka IT
Mirosława Nowicka,,
- The Institute of Telecommunications
, Tadeusz Łuba IT
Tadeusz Łuba,,
- The Institute of Telecommunications
Book , 1998 Eleventh International Conference on VLSI Design, 1998. Proceedings, 1998
Keywords in Englishbalanced decomposition algorithm, benchmark testing, Boolean functions, circuit CAD, collaboration, Computer industry, decomposition strategies, Delay, Demain, field programmable gate arrays, FPGA-based technology mapping, FPGA-oriented algorithms, Industrial economics, Logic, logic CAD, logic synthesis tool, minimisation of switching nets, Minimization methods, multiple-output Boolean functions, parallel decomposition, serial decomposition, single-output Boolean functions, Software testing, table lookup
Score (nominal)1
Citation count*2 (2015-04-29)
Share Share

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.