Gate Matrix Layout Synthesis with Two-Dimensional Folding

We have developed a gate matrix layout synthesis tool which utilizes folding technique on both rows and columns. The conventional interval graph model and the recently proposed dynamic net-list representation can not fully depict circuit schematics such as inter-net connections. The incomplete representations may mislead the search process for an optimal solution during the layout partitioning and the gate ordering phases. We propose a new graph-based model called hierarchical dynamic net-list to improve the schematic representation. Based on the new model, the folded layout area in the partitioning phase can be more accurately estimated. The new gate ordering algorithm proposed by us also takes the advantages of the hierarchical dynamic net-list model to handle the gate placement in the folded layouts. The experimental results show 12% to 15% improvement in layout area for small circuits and 30% improvement for a large circuit.