The Algorithms For The 2D Rectangle Packing Problem And The VLSI Floorplanning Problem

As NP-hard problems' solution spaces growing exponentially with the increase of the scale of data,there is no exact algorithm of polynomial time complexity for them unless P=NP.And designing heuristic algorithms and approximation algorithms,which can effectively solve the NP-hard problems in a limited time,have become a key issue in the modern computer science.The 2D rectangle packing problem is a classic NP-hard problem,the research on designing heuristic algorithms for it can inspire the solving of the other NP-hard problems,and has a profound theoretical significance.As an industrial propagation problem of the 2D rectangle packing problem,floorplanning is a key step in the Very Large Scale Integration(VLSI)design,the research on the floorplanning can promote the development of the VLSI industry.The thesis organically combines the research on the 2D rectangle packing problem and the research on the floorplanning,and proposes heuristic algorithms for three kinds of 2D rectangle packing problems and two kinds of floorplanning problems.The main work and achievement are as follows.(1)For the knapsack problem and the area minimization problem in the 2D rectangle packing,we design a Least Injury First algorithm(LIF)and a Dynamic Reduction Algorithm(DRA)respectively.We propose an injury degree metric to evaluate the possible negative impact for the candidate placement.LIF is a greedy construction method,which implements the placement with the minimum injury degree iteratively to construct the layout.Different from the knapsack problem,the area minimization problem is required to use the smallest sheet to place all the rectangles.By constructing a set of sheets dynamically,DRA transforms the solving of an area minimization problem into the solving of a set of knapsack problems,and uses LIF to solve the generated knapsack problems.DRA is tested on 15 typical benchmarks for the area minimization problem,DRA succeeds in improving 8 and matching 3 best known results.(2)For the 2D soft rectangle packing problem and the fixed-outline floorplanning with soft modules problem,we design an Iterative Merging Packing algorithm(IMP)and an Iterative Merging Packing based Hierarchical Partitioning algorithm(IMP-HP)respectively.IMP is an original algorithm for the problem with zero deadspace.First,similarly to the construction of the Huffman tree,IMP merges all the rectangles into a final composite rectangle in a bottom-up order by iteratively merging two rectangles with the smallest areas into a composite rectangle.Then,it shapes and places each pair of sibling rectangles based on the dimensions and position of their composite rectangle in an up-bottom order.We prove that IMP can guarantee feasible layout(layout with all the rectangles are legally placed)under some conditions,which are more relaxed as compared with a well-known Zero-Dead-Space(ZDS)packing algorithm.Based on a novel deadspace assignment strategy,we then extend IMP to solve the problem having deadspace.IMP-HP adopts a hierarchical partitioning framework,it uses the hypergraph partitioning tool hMetis to partition the given problem into a set of sub-problems,and adopts IMP to solve the sub-problems.By relaxing the hard modules in the 18 IBM-HB benchmarks having aspect ratio 1 as soft modules,18 IBM-SHB benchmarks are obtained.The comparisons with two typical algorithms PATOMA and DeFer show that IMP outperforms PATOMA and DeFer by reducing the average wirelength by4.1% and 4.0% respectively,and succeeds in improving 10 benchmarks.(3)For the fixed-outline floorplanning with mixed modules problem,we design a QuasiNewton based Floorplanner(QNF).QNF consists of three parts: the rough distribution,the local optimization and the refined distribution.The rough distribution uses hMetis to recursively partition the given problem until all the sub-problems contain only one module,place each module onto the corresponding sub-outline,and a uniform distributed layout with short wirelength is obtained finally.The local legalization adopts an elastic potential energy that we proposed to evaluate the overlaps among modules and the extent that modules exceed the outline,and it uses a Quasi-Newton method L-BFGS-B to optimize the elastic potential energy to shift and shape modules,such that the layout obtained by rough distribution can be transformed into a legal one.When the layout obtained by the rough distribution can not be legalized by the local optimization,the refined distribution is called to generate a layout with modules distributed more uniformly,and uses the local optimization to legalize the layout then.The refined distribution first fixes the super large modules onto the outline,and then distributes the unfixed modules to the remaining spaces on the outline.The proposed algorithm is tested on 54 IBM-HB benchmarks,it can solve 51 legally,and succeeds in improving35.Compared with the two most effective algorithms DeFer and F-FM,IMP-HP reduces the average wirelength by 6.3% and 2.3% respectively.To sum up,the performance of the proposed algorithms for the 2D rectangle packing problem and the floorplanning match or outperform the performance of the best algorithms in the areas.Moreover,the proposed floorplanning algorithms meet the requirement of industrial applications.