Mixed non-rectangular block packing for non-Manhattan layout architectures

Non-Manhattan structures, such as the X and Y architectures, propose different flavors in reducing the use of physical resources, such as total wirelength and number of vias. However, in order to take full advantage of these structures, we need to develop new tools for these architectures, especially for early stages in physical design. In this paper, we propose the packing algorithm with isosceles right triangular and trapezoidal blocks using the B^*-tree representation. Our approach can be further applied to packing with any block which can be divided into rectangles and isosceles right triangles. Experimental results based on the modified MCNC benchmarks show that the average area usage is above 95% and the run time of our proposed algorithm is comparable when performing rectangular and non-rectangular block packing with original B^*-tree.