Advanced Pairwise Merging Algorithm for VLSI Floorplanning

Introduction

This paper concerns the problem of determining optimal placement of rectangular blocks within a rectangular area known as the packing or cutting-stock problem. This problem arises at then floorplanning stage of VLSI design.

Assume that one is given n different types of rectangular blocks R0, R1, … Rn ? 1, where Ri is rectangle hi x wi. The goal is to find non-overlapping placement of the blocks within rectangular area A so that uncovered part of the area is as small as possible. The rectangle A is referred to as target area. Without loss of generality one can assume that a block of any type Ri can fit in the target area. This problem is referred to as packing problem. The problem is also known as cutting stock problem. (It can be easily reformulated as problem of cutting rectangular sheet of material into rectangular pieces. We will use this name to refer to the problem as well.)