Denser packings obtained in o(n log log n) time

The placement problem is that of packing a set of rectangles into a minimum–area enclosing rectangle. Since it is difficult to optimize directly on a placement, a number of topological representations have been presented in the literature. One of the most successful is the sequence pair representation. As opposed to previous papers using sequence pair, we do not make use of the corresponding constraint graph, but interpret the sequences as a packing order in a constructive algorithm. All placements generated are semi–normalized, i.e., each module is moved as far left and down as possible according to the current packing contour. It is shown that the two interpretations are equivalent for any minimum–area placement, and for a given sequence pair the new interpretation results in a placement using no more area than the constraint graph interpretation. The transformation runs in O(nlog log n) time and it is able to handle various constraints on the location of modules. Computational results based on a simulated–annealing framework show that the algorithm is able to improve significantly on the best found solutions for benchmark very large–scale integrated (VLSI) circuit design problems using less than ten seconds of CPU time. For large packing problems it is able to find solutions quickly that waste no more than 3%–5% of the space.