Partially-dependent functional decomposition with applications in FPGA synthesis and mapping
Jason Cong, Yean-Yow Hwang · 1997
In this paper, we give a necessary and sufficient condition for the existence of partially-dependent functional decomposition and develop new algorithms to compute such decompositions. We apply our method to the synthesis and mapping for Xilinx XC4000 FPGA's which contain non-uniform sizes of LUT's in its architecture. We develop a new mapping algorithm named PDDMAP which uses CLB's to cover nodes on critical paths for depth minimization and uses LUT's to cover non-critical nodes for area minimization. On average, PDDMAP is able to reduce the depth by 13%with only 1% of increase in area comparing to the results by FlowMap followed by a CLB generation procedure match_4k. We also develop a post-mapping procedure named PDDSYN which resynthesizes mapping solutionsto reduce the mapping area. On average, PDDSYN is able to improve PDDMAP mapping solutions by 5% in depth and 7% in CLB count, and achieves 8% smaller depth and 11% fewer CLB count comparing to FlowSyn followed by match-4k.