Optimization of Test and Design-for-Testability Solutions for Many-Core System-on-Chip Designs

With the continuous scaling of transistors to smaller dimensions, it has now become feasible to pack billions of transistors in a single chip. However, interconnect does not scale as well as transistors; hence a significant amount of research is focused today on finding viable alternatives to bus-based interconnects. Coupled with the problem of increasing interconnect delay is the challenge to contain the power footprint. A network-on-chip (NOC) interconnect fabric can alleviate many of these problems, and is therefore viewed as a promising interconnect paradigm of the future. In addition, NOC building blocks consist of reusable components and require minimal design effort in building a large and complex system. In addition to NOCs, 3D integration technology using through-silicon-vias (TSVs) can also alleviate the problems caused by long global interconnects and it offers more innovative design choices compared to traditional 2D integrated circuits (ICs).

Regardless of the choice of interconnect fabric, testing continues to pose a significant challenge. New optimization methods for designing the test-access mechanism (TAM) and minimizing test time are needed. On-chip routing protocols guided by network topology and traffic congestion constraints open new avenues for research in optimizing test-data delivery in NOCs. The thesis describes algorithms for test-data delivery optimization in NOC designs with hundreds of cores, where the NOC is used as a TAM. First, an algorithm based on subset-sum formulation to solve the test-delivery problem in NOCs with arbitrary topology is presented. For the important class of NOCs with a grid topology, the optimization problem is modeled as an NOC partitioning problem and solved using dynamic programming in pseudo-polynomial time. Both the proposed methods yield high-quality results and are scalable to large SOCs with many cores.

Since the proposed methods involve concurrent testing of multiple cores, high power consumption may limit its adoptability in practice; therefore, the thesis also discusses a scheduling algorithm under power constraints using the same dynamic-programming framework. By leveraging the capability of modern multicast routers, the homogeneity of cores is exploited to further minimize test time in such large SOCs.

Three-dimensional (3D) stacking of ICs using through-silicon-vias (TSVs) is a promising integration platform for next-generation ICs. Several complex manufacturing steps involved in the fabrication of 3D-stacked ICs make these chips susceptible to defects. In the scenario where die yields are low, stacking of untested dies further reduces overall yield, and thereby reduces profitability. Moreover, testing at every stage of 3D integration may result in prohibitive test cost. Despite the benefits offered by 3D integration, test cost remains a major concern. The tests have to be inserted at appropriate places in the 3D integration flow. Automated tools are needed to analyze and understand test flows and achieve the desired goal. The thesis describes a generic cost model to account for various test costs involved in 3D integration and formalize the study of test flows as a search problem to minimize the overall cost. An algorithm based on A* to obtain an optimal test flow is presented. Adopting a formal approach to solving the cost-minimization problem provides useful insights that cannot be derived via selective enumeration of a smaller number of candidate test flows.

In 3D-stacked ICs, inaccessibility of TSVs prior to bonding makes it difficult to test the combinational logic between scan flip-flops and TSVs at a pre-bond stage. Addition of wrapper cells on both ends of a TSV solves the testability problem, but at the cost of area overhead, increased latency and performance degradation. The thesis builds on prior work to reuse existing scan flip flops and shows that the general problem of minimizing the wrapper cells is equivalent to the graph-theoretic minimum clique-partitioning problem, and is therefore NP-hard. Efficient heuristic methods are adopted to solve the problem. The proposed methods incorporate a timing-guided and layout-aware approach to address practical timing considerations that were overlooked in prior work. Extensions are also made to post-bond testing stages.

Finally, the thesis describes an end-to-end design of a built-in self-test (BIST) infrastructure for 3D-stacked ICs that facilitates the use of BIST at multiple stages of 3D integration. The proposed BIST design is distributed, reusable, and reconfigurable, hence it is attractive for both pre-bond and post-bond testing. Architectural support for incorporating a static BIST schedule is also provided. Furthermore, two algorithms based on 2D bin packing problem to minimize test time under BIST-resource and power constraints are presented.

In summary, the thesis targets important optimization problems related to test-delivery in manycore SOCs that are assembled using a scalable and flexible integration platform. The proposed research has led to theoretical insights, simulation results, and a set of test and design-for-test methods to make testing effective and feasible from a cost perspective.