Floorplanning And Fault Tolerance TSV Planning For Three Dimensional Integrated Circuits

The three dimensional integrated circuit(3D IC)technology involves the vertical stacking of multiple dies,which are connected by through silicon vias(TSVs),achieving a significant reduction in chip area and interconnect delay.Besides,3D IC also offers the potential for heterogeneous integration,which is essential for More than Moore(MtM)technology.Although 3D IC technology has many advantages,it is also associated with some critical challenges.Due to the vertical stacking of blocks,3D IC increases the complexity of the chip design.In addition,yield of TSVs is limited under current manufacturing process.Motivated by the above arguments,this dissertation focuses on floorplanning algorithm,thermal analysis model,and TSV fault tolerance design.3D IC floorplanning is an NP-hard problem,and many intelligent optimization al-gorithms are widely adopted in 3D IC floorplanning problem because of their efficient solution space search strategy.In order to make full use of the global search of ant sys-tem algorithm and the local search characteristics of simulated annealing algorithm,a two-phase algorithm combining the ant system algorithm and simulated annealing algo-rithm is proposed in this dissertation to effectively handle 3D IC floorplanning.Exper-imental results show that,compared with the previous 3D IC floorplanning work,the proposed two-phase algorithm can reduce TSVs number by 3.51%on average.Besides,compared with the previous 2D IC floorplaning work based on ant system algorithm,the proposed two-phase algorithm can reduce wirelength by 3.72%on average with short runtime.To reduce the thermal analysis time during floorplanning,in this dissertation,a fast thermal analysis model for fixed-outline 3D IC floorplanning is proposed.The thermal profile of each block placed on different positions is first simulated before floorplanning.Then based on the simulated thermal profiles and coordinates of blocks,bilinear inter-polation is adopted to quickly estimate the temperature during floorplanning.Given a multi-layer floorplan result,TSVs are assigned by a heuristic method,which combines the shortest path and min-cost-max-flow,with minimization of wirelength and chip tem-perature.Experimental results show that,compared with the superposition of thermal profiles method,the proposed thermal model can reduce low peak temperature value by 7.18%on average.Besides,the runtime of the proposed thermal analysis method is far less than the superposition of thermal profiles method.In order to enhance the chip yield,in this dissertation,a TSV multiple fault toler-ance structure generation method for regular TSV group is first proposed,which takes clustered TSV defect distribution into account.The proposed framework mainly con-sists of four stages:1)a convex-cost flow based model for functional TSV allocation considering the fault clustering;2)a top-down globally partitioning combined with a bottom-up locally merging to partition functional TSVs into groups;3)the min cost max flow algorithm for spare TSV allocation;4)an integer linear programming based model to form a multiple fault-tolerance structure.Besides an adaptive TSV fault tol-erance structure generation method for irregular TSV group is also proposed,including three stages:1)the maximum number of tolerant faults calculation based on the max-flow algorithm;2)the min-cut bi-partitioning algorithm to partition functional TSVs into groups;3)an integer linear programming formulation and an efficient min cost max flow based heuristic method in generating the adaptive TSV fault tolerance struc-ture generation.Experimental results show that,the proposed repair framework can improve the yield with minimum hardware cost and multiplexer delay overhead.