Study On Optimization Theoretical Analysis And Methods Of Design For Testability In SoC

With the advent of the new information age, manufacturing technology of integratedcircuit is developing dramatically. We have entered the nanometer era from micron era,which makes VLSI manufacturing capacity improve rapidly. However, IC design levelcould not keep up with the development of manufacturing technology. This forms acontradiction, which is called “the difference of scissors”. The contradiction has becomean obstacle for the development of IC industry. The modular design, which is called "IPcore reuse", can solve the critical problem by improving design efficiency and reducingthe complexity of the design. Therefore, it can greatly improve the design capabilities ofdesigners. Modern electronics market demands fast time to market, low power, goodportability and low test costs. Because IP core reuse can significantly improve theefficiency of product development, we could integrate various IP cores verified into asystem on chip(So C) based on the actual needs. It is because the So C can reduce timeto market and achieve low power consumption and excellent portability that makes So Cwidely applied to modern electronic products. As far as the national strategic level isconcerned, it has become a key component. Although IP core reuse methods could solvethe contradiction between manufacturing technology and design capabilities, at thesame time, it also brings new challenges in test issues, such as the increasing difficultyof the test and rapid growth of the test cost. Therefore, how to reduce the test cost bydesign for testability optimization method has become a key issue.The dissertation aims to carry out design for testability using the optimization method based on swarm intelligence to reduce So C test cost. The research topics are mainly about wrapper scan chain balance design, three-dimensional multi-objective wrapper scan chain optimization issues and test scheduling for three-dimensional stacked So C based on hard dies. The main work of this dissertation is supported by the National Natural Science Foundation “So C test scheduling based on quantum algorithm”(No. 60766001), Guangxi Key Laboratory of Automatic Detection Technology and Instrument Fund “three-dimensional So C design for testability and optimization methods”(No. YQ14110). Analysis and optimization theory methods are studied in scan-oriented design for testability. The main topics and research achievements are as follows.1. Balance optimization methods of wrapper scan chains are studied. Problem description of wrapper scan chains design is built. By analysis of the BFD(Best Fit Decreasing) method, MVA(Mean Value Approximation) method and MVAR(Mean Value Allowance Residue), major shortcomings of current methods are found. A wrapper scan chain balance algorithm based on BBO(Biogeography Based Optimization) is proposed. After setting the maximum emigration rate, immigration rate the maximum mutation probability, population size, maximum iterations, the problem size and the number of wrapper scan chain, the migration operation and mutation operation are carried out. Within the maximum iterations, wrapper scan chain balance design is achieved, to minimize the test time of the IP core. In the dissertation, typical IP modules in ITC’02 Test benchmarks are adopted. Compared to BFD algorithm, the experimental results show that the proposed algorithm can obtain further reduced wrapper scan chain, thus shortening the test time.2. The complexity analysis of the BBO algorithm using the convergence rate is studied, and lower bound of the mean value of the first time to reach the target subspace for the wrapper scan chain design is analyzed. Since BBO method originates in the migratory nature of biological mechanisms, including the complex stochastic behavior, so its theoretical analysis is very difficult and rigorous theoretical foundation is still relatively scarce. A Markov chain model of BBO algorithm is built, and the population sequence of BBO algorithm is proved to be an absorbing Markov chain. Convergence feature of the BBO algorithm is analyzed. There were no reports of methods of theoretical analysis of the complexity of the lower bound for the wrapper scan chain design. To solve this problem, a complexity analysis method of the BBO algorithm for wrapper scan chain optimization is proposed, by uncovering the relationship between the convergence rate of the BBO algorithm and the mean value of the first time to reach the target subspace, which provides a theoretical guarantee for the wrapper scan chain design.3. In order to reduce test cost and expense, we propose an OBBO(Opposition-based learning and Biogeography Based Optimization) algorithm and designs wrapper scan chains for the IP(Intellectual Property) using OBBO algorithm, which can make the test time of IP be minimum.The new method is a random optimization algorithm which combines BBO(Biogeography Based Optimization) algorithm with OBL(Opposition-based learning). By using migration operation, mutation operation and OBL operation, we achieve a balance between different wrapper chains so that we can shorten the wrapper scan chain which is longest. Experimental results show its efficiency.4. Optimization design of three-dimensional test wrapper scan chain is studied. Problem description of three-dimensional wrapper scan chain design is established. The population sequence of MOFA(Multi-Objective Firefly Algorithm) is proved to be an absorbing Markov chain, and the convergence of MOFA is analyzed. Three-dimensional test wrapper scan chain design based on MODE(Muti-Objective Differential Evolution) and MOFA are proposed respectively, making the wrapper scan chain equalization and using the least resources of TSV(Through Silicon Vias), to achieve the minimal test time of IP core and the minimal TSV costs. The proposed algorithm is based on swarm intelligence to achieve multi-objective optimization of three-dimensional wrapper scan chain. In the dissertation, typical IP cores in ITC’02 Test benchmarks are selected as experimental subjects. Experimental results show that the proposed algorithm can get a better Pateto optimal solution set, compared to NSGAII(Nondominated Sorting Genetic Algorithm II).5. Test scheduling of three-dimensional stacked So C is studied. Problem description of test scheduling of three-dimensional stacked So C is built first. The basic GWO is easy to fall into local optimum and stagnation as it performs attack behavior. While DE algorithm has a strong search capability, therefore a HGWO algorithm(Hybridizing Grey Wolf Optimization) is proposed by hybridizing the DE algorithm with the GWO, to update the gray wolf Alpha, Beta and Delta, so that the GWO could escape from local optima. The proposed algorithm is verified with twenty three standard test functions widely used, which could be grouped into unimodal benchmark functions, multimodal benchmark functions and fixed dimension multimodal benchmark functions. The mathematical model of test scheduling of three-dimensional stacked So C is created. To reduce test time, test scheduling of three-dimensional stacked So C based on the HGWO algorithm is proposed. Experimental results show the superiority of the proposed...