Research On The Path Selection For Small Delay Defects Test Based On Topology Of Circuit

With the development of manufacturing technologies,more and more transistorsare being picked into chips with ever increasing operating frequencies for higherfunctional density.Nanometer-scaletechnology poses new challenges for both designand test engineers,because scalingtechnologies bring about increasingmanufacturing-related defects. The shrinking of technology has introduced morevariation to designs and hasmade design features more probabilistic, and theimperfect manufactering process could easily introduce small delay defects(SDDs) tochips. Further more, increaseing crosstalk caused byon-chip coupling capacitancesbecause of long interconnects,and power noise caused by scaled power supplyvoltagesalso introduce the extra delay to the chips which could cause the chipsfailures.As technology scales to45nm and below, testing for SDDsis necessary toensure the quality and reliability of high-performance integratedcircuits.So it iscritical to select appropriate test paths for SDD test.However, the characteristic of the size of SDD,which is much smaller thanoperating clock cycle，brings about difficuity for testing. In this paper, based on thepeculiarity that SDD is more sensitive to long paths, algorithms is proposed to searchcritical paths for SDD test in the topological graph which is transferred byintegratedcircuits.To begin with, greedy algorithms including DFS and BFS which is used in thestatic timing analysis in EDA,is used to select to critical paths in integratedcircuitsfor SDD test. However, critical paths selection in circuits is a NP-hard problem,inorder to solve the poor efficiency of greedyalgorithms,three methods are proposed toimprove the efficiency.Heuristicalgorithm,ant colony optimization, is proposed toimprove the efficiency of selecting critical paths for SDDs guaranteeing highprecise.Further on, theefficiency of ACO in SDD test paths selection is moreimproved by the critical nodes selection which is acquired by adpatting the PageRankand HITSRank to circuit topological graph. At last, a algorithm dividing the circuitinto several parts by critial nodes in circuits is proposed to reduce the size of theproblem, which also improve the efficiency of selecting critical paths for SDD test.