A graph-theoretic approach for minimizing the number of wrapper cells for pre-bond testing of 3D-stacked ICs

Three-dimensional (3D) stacking of ICs using through-silicon-vias (TSVs) is a promising integration platform for next-generation ICs. Since TSVs are not fully accessible prior to bonding, it is difficult to test the combinational logic between scan flip-flops and TSVs at a pre-bond stage. In order to increase testability, it has been advocated that wrapper cells be added at both ends of a TSV. However, a drawback of wrapper cells is that they incur area overhead and lead to higher latency and performance degradation on functional paths. Prior work proposed the reuse of scan cells to achieve high testability, thereby reducing the number of wrapper cells that need to be inserted; however, practical timing considerations were overlooked and the number of inserted wrapper cells was still high. We show that the general problem of minimizing the wrapper cells is equivalent to the graph-theoretic minimum clique-partitioning problem, and is therefore NP-hard. We adopt efficient heuristic methods to solve the problem and describe a timing-guided and layout-aware solution. We also evaluate the heuristic methods using an exact solution technique based on integer linear programming. Results are presented for 3D-stack implementations of the ITC´99 and the OpenCore benchmark circuits.