In this project, we study partially-dependent functional decomposition.
We present a necessary and sufficient condition for its existence and develop
new algorithms to compute such decompositions. We apply our results to
logic synthesis and technology mapping for LUT-based FPGAs, in particular,
Xilinx XC4000 FPGAs.
The logic units (called CLB) in Xilinx XC4000 FPGA consist of interconnected
non-homogeneous LUTs which can implement functions of up to 9 inputs. The
matching of functions to the Xilinx XC4000 FPGA logic units can be achieved
by partially-dependent decomposition of the functions. We develop a new
mapping algorithm named PDDMAP which uses CLBs to cover critical paths
for depth minimization and LUTs to cover non-critical nodes for area minimization,
respectively.
On average, PDDMAP is able to reduce the mapping depth by 13% with only
1% of area overhead comparing to FlowMap followed by the CLB packing procedure
match_4k. We also develop a post-mapping procedure named PDDSYN which resynthesizes
mapping solutions to reduce the mapping area. On average, PDDSYN is able
to improve PDDMAP mapping solutions by 5% in depth and 7% in area, and
achieves 8% smaller depth and 11% smaller area comparing to FlowSyn followed
by match_4k.
|