A Multilevel Multilayer Partitioning Algorithm For Three Dimensional Integrated Circuits

Yu Cheng Hu,  Yin Lin Chung,  Mely Chen Chi
Chung Yuan Christian University


We propose a multilevel multilayer partitioning algorithm for 3D ICs application. The algorithm is based on a multilevel framework to coarsen the netlist successively to reduce the problem size effectively. The objective is to minimize the total number of Through Silicon Via (TSV) and the chip area. The chip area is the number of layer multiplied by the largest area among all layers in the chip. We utilize a FM-like data structure and identify eight critical net distributions such that after a cell move, the program can update gains very effectively. Experimental results show that our multilevel multilayer partitioning algorithm can effectively produce good results with small numbers of TSV, area overhead, and area coefficient of variation for the tested industrial cases. The average area overhead is only 1.84% that shows the average white space is very small. The average area coefficient of variation is only 2.61% that shows the area distribution of all layers is very uniform. The results of the proposed algorithm achieves the best average value for both number of TSV and chip area, compared to the results of all the participating teams in “Design Partition for 3D ICs” problem in the IC/CAD 2009 contest in Taiwan.