Reduction of Power Consumption in FPGAs - An Overview <s> b) Packing <s> VLSI netlist partitioning has been addressed chiefly by iterative methods (e.g. Kernighan-Lin and Fiduccia-Mattheyses) and spectral methods (e.g. Hagen-Kahng). Iterative methods are the de facto industry standard, but suffer diminished stability and solution quality when instances grow large. Spectral methods have achieved high-quality solutions, particularly for the ratio cut objective, but suffer excessive memory requirements and the inability to capture practical constraints (preplacements, variable module areas, etc.). This work develops a new approach to Fiduccia-Mattheyses (FM)-based iterative partitioning. We combine two concepts: (1) problem reduction using clustering and the two-phase FM methodology and (2) adaptive multistart, i.e. the intelligent selection of starting points for the iterative optimization, based on the results of previous optimizations. The resulting clustered adaptive multistart (CAMS) methodology substantially improves upon previous partitioning results in the literature, for both unit module areas and actual module areas, and for both the min-cut bisection and minimum ratio cut objectives. The CAMS method is surprisingly fast and has very stable solution quality, even for large benchmark instances. It has been applied as the basis of a clustering methodology within an industry placement tool. <s> BIB001 </s> Reduction of Power Consumption in FPGAs - An Overview <s> b) Packing <s> Top-down partitioning has focused on minimum cut or ratio cut objectives, while bottom-up clustering has focused on density-based objectives. In seeking a more unified perspective, we propose a new sum of densities measure for multi-way circuit decomposition, where the density of a subhypergraph is the ratio of the number of edges to the number of nodes in the subhypergraph. Finding a k-way partition that maximizes the sum of k subhypergraph densities is NP-hard, but an efficient flow-based method can find the optimal (maximum-density) subhypergraph in a given hypergraph. Based on this method, we develop a heuristic which in practice has less than 10% error from an optimal sum of densities decomposition. Other results suggest that density-based heuristics can capture cut-based objectives, whereas the converse would seem difficult. > <s> BIB002
The packing phase converts the netlist of LUTs and flip-flops into a netlist of logic locks. The input netlist is converted into clusters of logic blocks that can be mapped into the physical logic blocks of the FPGA. Most packing algorithms minimize the number of resulting logic blocks, the number of connections between them, and/or the delay along the critical path. The packing algorithm has to consider the physical limitations of the actual logic blocks of the FPGA in terms of the maximum number of LUTs in a logic block and the number of distinct input signals and clocks a logic block has. Packing algorithms can be categorized as either bottom-up [14, 18, 19, and 20] or top-down BIB001 BIB002 . Bottom-up packing algorithms build each cluster individually around a seed LUT until the cluster is full. However, top-down packing approaches partition the LUTs into clusters by successive circuit subdivision. Bottom-up algorithms are much faster and simpler than top-down approaches because they only consider local connections. However, this comes at the expense of solution quality.