Parallel CAD Algorithms and Hardware Security for VLSI Systems

As integration scales to the 20nm regime and below, the integrated circuit (IC) design has seen the billion transistor counts. For instance, the latest Pascal GPU using 16nm FinFET technology from Nvidia has 150 billion transistors. As a result, it becomes very challenging to verify those billion-transistor chips and there is an urgent need to develop advanced and parallel simulation technique. On the other hand, the counterfeit ICs have become a major security threat for commercial and mission-critical systems. In addition to the huge economic impacts, they post significant security and safety threats on those systems. The objective of this thesis is to develop new techniques to address above two tough issues encountered in VLSI research: new fast parallel circuit simulation and potential solutions to mitigate the counterfeit IC problem.To accelerate the circuit simulation, we study several important linear algebra operations in simulation steps, such as sparse matrix-vector multiplication (SpMV), direct linear LU factorization and iterative general minimum residual linear solver. Parallel computing such as general purpose GPU programs are good solutions for improving performance of these operations. We apply GPU for these tasks and attain impressive speedup over traditional or CPU methods. All algorithms and implementations are demonstrated with representative numerical experiments and thorough comparisons among different methods and platforms.For various types of counterfeit ICs - recycled, remarked, cloned, out-of-spec, and over-produced, we propose a multi-functional on-chip sensor and post-authentication policy for detecting and preventing them. Especially for recycled ICs, we propose two kinds of aging sensors, which are based on electromigration (EM)-induced aging effects and ring oscillator (RO)-based frequency aging effects. These two aging sensors can effectively detect chip usage time for both short and long periods. Simulated results show the advantage of the proposed multi-purpose sensor against the existing on-chip sensors in terms of functionality, detection coverage and usage time estimation range and accuracy