a packing algorithm for non-manhattan hexagon/triangle placement design by using an adaptive o-tree representation
A non-Manhattan Hexagon/Triangle Placement (HTP for short) paradigm is proposed in the present paper. Main feature of this paradigm lies in adapting to the Y- architecture which is one of the promising non-Manhattan VLSI circuit layout architectures. Aim of the HTP is to place a set of equilateral triangles with given size onto a hexagonal chip with maximal chip area usage. Based on the O-tree representation, some adaptive packing rules are adopted to develop an effective placement algorithm for solving the HTP problem in BBL mode. Two examples with benchmark data transformed from the Manhattan BBL mode placement (ami33/49) are presented to justify the feasibility and effectiveness of our algorithms. Experiment results demonstrate that the chip area usage of 94\% is achieved through simulated annealing optimization.
placement o-tree representation y- architecture non-manhattan layout vlsi circuit physical design diagonal wiring