32 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법이주환외 논문 2009-46SD-3-5 고속고장진단을위해고장후보정렬과테스트패턴정렬을 이용한고장탈락방법 (A Fault Dropping Technique with Fault Candidate Ordering and Test Pattern Ordering for Fast Fault Diagnosis ) 이주환 *, 임요섭 *, 김홍식 **, 강성호 *** * (Joohwan Lee, Yoseop Lim, Hongsik Kim, and Sungho Kang ) 요 약 한제품을만들어시장에내놓는데걸리는시간이짧아짐에따라고속고장진단의필요성이커지고있다. 본논문에서는고속고장진단을위하여정렬된고장후보목록과정렬된테스트패턴을사용하여고장점수를기준으로고장탈락을시키는방법을제안한다. 제안하는고장탈락방법은고장시뮬레이션과매칭알고리듬을기반으로하는모든고장진단에적용할수있다. 완전주사 ISCAS 89 벤치마크회로를이용한실험결과는정렬된고장후보목록및정렬된테스트패턴을적용한고장탈락방법의효율성을보여준다. Abstract In order to reduce time-to-market, the demand for fast fault diagnosis has been increased. In this paper, a fault dropping technique with fault candidate ordering and test pattern ordering for fast fault diagnosis is proposed. Experimental results using the full-scanned ISCAS 89 benchmark circuits show the efficiency of the fault dropping technique with fault candidate ordering and test pattern ordering. Keywords : Fault dropping, Fault candidate ordering, Test pattern ordering, Fault diagnosis, Fault simulation Ⅰ. 서론 VLSI (very large scale integration) 회로와디지털시스템의복잡도가나날이증가하고크기가줄어듦에따라서, 고집적회로의고장분석 (fault analysis) 이점점더어려워지고있다. 따라서고장진단 (fault diagnosis) 의중요성이꾸준히늘어나고있으며, 빠르게변화하는시장의요구를만족시키기위해서는짧은시간안에고장진단이이루어져야한다. 고장진단을위해고장시뮬레이션 (fault simulation) * 학생회원, ** 정회원, *** 평생회원, 연세대학교전기전자공학과 (Department of Electrical and Electronic Engineering, Yonsei University) 접수일자 : 2008년12월16일, 수정완료일 :2009년2월20일 을기반으로한방법이널리사용되고있으며, 이러한고장진단시간의대부분은고장시뮬레이션의수행을위해사용된다. 그러므로고장시뮬레이션의수행시간을줄이는것은고장을빠르게진단할수있도록해준다. 같은회로를대상으로했을경우에, 고장시뮬레이션의수행시간은테스트패턴 (test pattern) 수와고장후보 (fault candidate) 수의곱에비례하여결정된다. 고속고장진단을통해짧은시간안에고장진단이수행될때에도일정수준이상의정확한고장진단결과가보장되어야한다. 고장시뮬레이션을이용하여정확한고장진단을수행하기위해서는적절한매칭알고리듬 (matching algorithm) [1] 을이용하여각고장후보들에대해동일한횟수의비교가이루어져야한다. 왜냐하면해당고장에대해매칭알고리듬을적용하여고 (248)
2009 년 3 월전자공학회논문지제 46 권 SD 편제 3 호 33 장점수를결정하고이를바탕으로실제고장일확률이높은고장후보순위를결정하기때문이다. 그리고무엇보다도동일한횟수의비교를통해올바른비교결과를위한공정성을확보할수있다. 또한동순위고장후보의개수를줄이기위해서는고장을전파하는테스트패턴뿐만이아니라고장을전파하지않는나머지테스트패턴의정보를이용하여고장진단의고장분해도 (fault resolution) 를향상시키는것이필요하다. 따라서테스트패턴의수를임의로변경하는것은고장진단결과에좋지않은영향을미치기때문에고장시뮬레이션의실행시간을변화시키기위한시도에서제외한다. 고장후보수를줄이기위해서다양한 [2~3] 방법이제안되었다. 임계경로추적방법 [2] 은고장이전파된주출력단과고장을전파한테스트패턴을이용하여고장시뮬레이션을수행하기전에고장후보의수를줄였으며, 다른방법 [3] 은고장시뮬레이션을수행하는과정중에고장후보의수를줄였다. 하지만, 이 [3] 와같은방법은테스트대상회로내의고장유무를판별할수는있지만, 고장의위치와종류를밝혀내는고장진단을수행할수는없다. 따라서고장진단이가능하도록고장후보수를줄여주는방법으로고장탈락 (fault dropping) 방법 [4] 이제안되었다. 고장을정렬하여사용하는것을통해고장시뮬레이션의성능을향상시킨방법 [5] 이연구되었다. 본논문에서는원활한고장진단성능의비교를위해서병렬고장시뮬레이션을이용한다. 이에따라적은시간부담을가지며큰효과를나타내는깊이우선탐색방식을응용한고장후보정렬방법을사용한다. 사용하는고장탈락방법은고장시뮬레이션과매칭알고리듬을수행하는과정중에일어난다. 테스트대상회로의고장시뮬레이션을수행하기위해서는테스트패턴이필요하며, 테스트패턴의특성을이용하여적절한형태로정렬한후에사용 [6] 하면보다향상된고장진단결과를얻을수있다. 따라서고장탈락방법에적합한방식으로정렬된최대의정보를가지는테스트패턴을우선적으로사용한다. 고장시뮬레이션을사용하는다수의고장진단방법 [7~9] 이제안되었다. 고장후보정렬및테스트패턴정렬을적용한고장탈락방법은고장시뮬레이션과매칭알고리듬에기반을둔어떠한고장진단에도사용가능하다. 그러므로고장후보정렬및테스트패턴정렬방법은기존고장진단의성능을쉽게향상시킬수있다. 본논문에서는고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법을제안한다. 제안하는고장탈락방법은매칭알고리듬을사용하여고장시뮬레이션수행중에고장을탈락시켜고장진단의수행시간을줄인다. 본논문의구성은다음과같다. Ⅱ장에서는고장시뮬레이션에기반을둔일반적인고장진단방법과고장점수결정을위한매칭알고리듬및고장점수를이용한고장탈락방법에대해기술한다. 또한, 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용하는방법을제안한다. Ⅲ장에서는제안하는방법의효율성을실험을통해제시한다. 그리고 Ⅳ장에서결론을맺는다. Ⅱ. 본론 1. 고장시뮬레이션기반의고장진단고장진단의목적은회로에존재하는고장의위치와종류를밝혀내는것이다. 고장시뮬레이션을사용하는고장진단의일반적인진행과정은다음과같다. 고장진단은대상회로, 테스트패턴, 고장기록을필수요소로준비하고가능하다면고장리스트도준비하여시작한다. 고장시뮬레이션할고장후보수를줄이기위해회로자체의구조정보를이용한등가고장중첩 (equivalent fault collapsing) 및고장기록과고장을전파하는테스트패턴을이용한임계경로추적 (critical path tracing) 방법을사용한다. 추려진고장후보중에서고장목표 (target-fault) 를선택하여고장시뮬레이션을수행하며, 적절한매칭알고리듬을이용해해당고장에대한고장점수를결정한다. 일련의과정을거친고장은고장리스트에서삭제되며, 고장리스트에고장후보가더이상존재하지않을때까지고장시뮬레이션과매칭알고리듬적용의과정을반복한다. 모든고장에대해고장점수가결정되면고장점수를기준으로내림차순정렬을실시한다. 정렬된결과는고장일확률이높은순서와같으며, 이것이고장진단의출력결과값이된다. 고장시뮬레이션을사용하는고장진단과정의수행시간은고장시뮬레이션의계산량에의해결정된다. 한번에하나의고장을시뮬레이션할때의계산량은테스트대상회로의크기, 테스트패턴의수그리고고장후보의수에대략적으로비례한다. 고장후보의수는개 (249)
34 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법이주환외 략적으로테스트대상회로의크기에비례하기때문에, p 개의테스트패턴과 n 개의게이트로이루어진회로의고장시뮬레이션에대한전체시간복잡도는 O(pn 2 ) 로나타낼수있다. 그러므로테스트대상회로의크기가커질수록고장진단을수행하는시간은비약적으로길어지게되며, 이를줄일수있는방법이필요하다. 2. 고장점수결정을위한매칭알고리듬매칭알고리듬은고장진단의결과에직접적인영향을주기때문에적절한매칭알고리듬의사용은매우중요하다. 고장진단을위한최적의매칭알고리듬 [1] 을찾기위해가산계산 (positive calculation), 감산계산 (negative calculation), 잠재적으로검출되는출력 (potentially detected output), 완전일치출력 (perfect match), 비교기준선정 (criterion output) 그리고가중치적용 (weight change) 과같은필수적인요소들을고려하였다. 이러한결과를바탕으로최적의매칭알고리듬을결정하였으며, 그림 1에고장진단에사용하는점수계산을위한매칭알고리듬을나타내었다. 3. 고장점수를이용한고장탈락방법테스트는고장의유무만을판단하기에, 고장이검출되면그즉시고장탈락이일어난다. 하지만, 고장진단은고장의유무만을판별하는것이아니라고장의위치와종류를밝혀내야하기때문에, 고장을한번검출했다고해서테스트과정에서와같이고장을탈락시킬수없다. 고속고장진단을위해제안된고장탈락방법 [4] 은고장시뮬레이션과매칭알고리듬을교대로이용하며누적되는고장점수의특징을이용하여고장을탈락시킨다. 즉, 고장점수가현저히낮은고장후보를실제고장일확률이낮다고가정하고고장진단과정중에탈락시켜고장진단을빠르게수행한다. 고속고장진단을위해제안된고장탈락방법 [4] 은병렬고장시뮬레이션을사용하였다. 고장탈락방법을적용하기위해서특별히병렬고장시뮬레이션을사용해야하는것은아니며, 고장시뮬레이션및매칭알고리듬을기반으로하는고장진단이라면고장시뮬레이션의방법에상관없이고장탈락방법을적용할수있다. 비교실험및개념정립의필요성때문에본논문에서도병렬고장시뮬레이션을사용하도록하겠다. 고장탈락기법을통해고속고장진단을실시할수있으며, if (the observed signature is a faulty signature) if (the candidate signature is a faulty signature) if (the observed outputs are equal to the candidate outputs) /* perfect match */ score[current fault] += number of outputs else if (the observed outputs are not equal to the candidate outputs) /* positive & negative match */ score[current fault] += number of simultaneously erroneous outputs score[current fault] -= number of separately erroneous outputs else if (the candidate signature is not a faulty signature) /* negative 1 match */ score[current fault] -= number of observed erroneous outputs else if (the observed signature is not a faulty signature) if (the candidate signature is a faulty signature) /* negative 2 match */ score[current fault] -= number of candidate erroneous outputs 그림 1. 고장점수계산을위한매칭알고리듬의의사 코드 Fig. 1. The pseudo code for fault score calculation of matching algorithm. 제안하는정렬된고장후보목록의사용및정렬된테스트패턴을사용함으로써보다고속의고장진단을구현할수있다. 4. 고속고장진단을위해제안하는고장탈락방법 가. 정렬된고장후보목록의사용 고속고장진단을위한고장탈락방법은동시에수행하는모든고장후보에대해서고장탈락이일어나야고장진단과정이중단된다. 하나의고장후보라도고장탈락이되지않고남아있다면, 고장시뮬레이션및매칭알고리듬의적용이계속되어야한다. 따라서동시에수행되는모든고장후보가빠르게고장탈락될수록고장진단시간을단축시킬수있다. (250)
2009 년 3 월전자공학회논문지제 46 권 SD 편제 3 호 35 (a) 그림 2. 개략적인고장후보선택순서 (a) 깊이우선 탐색응용, (b) 넓이우선탐색응용 Fig. 2. The order of selecting fault candidate (a) The application of depth-first search, (b) The application of breadth-first search. 하지만, 각고장후보별고장탈락시기는각기다르다. 고장점수가매우낮은음의값을가져야만고장탈락조건을만족시키는데, 이때필요한테스트패턴의수는같지않다. 따라서고속고장진단을위해서는되도록비슷한성향을보이는고장후보들을함께묶어서고장시뮬레이션및매칭알고리듬을수행하는것이 효과적이며, 고장진단의조기중단이가능할것이다. 즉, 고장후보를적절한규칙으로정렬시켜사용하는것이고장진단을더욱빠르게할수있다. 실제결함과고장시뮬레이션에서고장영향은주입력단에서주출력단으로전파된다. 또한, 하나의고장영향의결과와해당고장이전파되는경로상에존재하는다른고장후보들에의한고장영향결과는유사한경 향을보인다. 그러므로고속고장진단을위한고장후보묶음의선택은임계경로추적방식에서처럼깊이우선탐색방법을따르는것이효과적일것이다. 그러므로모든고장후보가가능한같은시기에고장탈락을일으켜빠른고장진단을수행할수있도록하기위해서그림 2의 (a) 와같이깊이우선탐색방법을응용하여정렬한고장후보목록을적용한다. 그리고깊이우선탐색방법의효율성을증명하기위해그림 2 의 (b) 와같이같은레벨내의고장을우선적으로선택하는넓이우선탐색방법을응용하여대조군으로사용한다. 깊이우선탐색방법과넓이우선탐색방법의효율성은실험결과에서확인해보도록한다. 나. 정렬된테스트패턴의사용 고장탈락은주어진테스트패턴을순서대로이용하여고장시뮬레이션및매칭알고리듬을수행하며일어난다. 각각의테스트패턴은검출할수있는고장후보 (b) 가다르기때문에, 고장탈락을적용한고장진단의성능은적절한방식으로정렬된테스트패턴을사용하는것에의해서향상되어질수있다. 테스트패턴의정렬을위해다음의세가지측정기준을고려하였다. 테스트패턴검출력 (Pattern ability : PA) PA는테스트패턴에의해서검출할수있는후보고장의수를나타낸다. 고장빈도 (Fault frequency : FF) FF는해당고장후보를검출하는테스트패턴의수를나타낸다. 고장빈도의합 (FF-sum) FF-sum은 FF 값의합을나타낸다. 단, 테스트패턴이검출할수있는고장후보의 FF 값들의합으로만 FF-sum 값을계산한다. 고속고장진단을위해서중간값 (mid-point) 의 PA 값을가지는테스트패턴을우선적으로사용하는테스트패턴정렬알고리듬을제안한다. 고장의검출유무가고장진단을위한정보의한종류로고려되고그정보의양이충분하다면, 고장진단의성능은더욱향상될것이다. 높은 PA 값을가지는테스트패턴은많은 수의고장후보를검출할수있고, 낮은 PA 값을가지는테스트패턴은적은수의고장후보를검출할수있다. 그러나높은 PA 값을가지고있으며, 다수의고장을검출하는테스트패턴이가장많은정보를가지고있는것은아니다. 왜냐하면, 모든고장을검출하는테스트패턴을사용하였을경우엔실제고장이아닐확률 Assign the PA pattern number to the current pattern. Begin Initialize PA for each pattern & FF for each fault. Find the mid-point PA. Is the number of the midpoint PA equal to one? Find the minimum FF-sum among the mid-point PA. Select the first minimum FFsum pattern. Assign the selected pattern number to the current pattern. Store the current pattern. Remove the stored current pattern. Modify the value of FF. Are there any remaining patterns? 그림 3. 테스트패턴정렬알고리듬 Fig. 3. The algorithm for ordering test pattern. End (251)
36 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법이주환외 이높은고장후보를확실하게구분해낼수없기때문이다. 반면에중간값의 PA 값을가지는테스트패턴을이용하면절반의고장후보에대해서는계속고장진단을수행하고나머지절반의고장후보에대해서는고장탈락을일으키도록결정을내리기가용이하다. 그러므로고장탈락을신속히수행하기위해서는, 가장높은 PA 값을가지는테스트패턴보다는중간값의 PA 값을가지는테스트패턴을우선적으로사용해야한다. 동일한 PA 값을가지는테스트패턴이있다면, 어떤테스트패턴을우선적으로선택해사용해야할지를결정해야한다. 이런경우에, 최소의 FF-sum 값을가지는테스트패턴을사용하는방법을제안한다. 낮은 FF-sum 값을가지는테스트패턴은비교적드물게검출되는고장후보를검출하는것을의미하기때문에, 다른경우보다높은고장검출율을짧은시간안에얻을수있다. 테스트패턴정렬알고리듬을그림 3에블록다이어그램으로표현하였다. 알고리듬을시작하기에앞서각테스트패턴에대한 PA 값과각고장후보에대한 FF 값을계산하여초기화한다. 그다음에계산된 PA 값중에서, 중간값의 PA 값을찾는다. 만약중간값의 PA 값을가지는테스트패턴의수가하나라면, 해당테스트패턴을선택한다. 반면에, 중간값의 PA 값을가지는테스트패턴의수가하나보다많다면, 최소의 FF-sum 값을가지는테스트패턴을우선적으로선택한다. 선택된테스트패턴은삭제되기전에저장되고, PA 값과 FF 값은새롭게갱신된다. 이와같은과정을남은테스트 Start Netlist / Ordered test pattern Fail log / Fault list Collapse equivalent faults Apply critical path tracing Sort faults using depth-first search Faults remain? Select target-faults Patterns remain? Do partial fault simulation Apply matching algorithm Remove selected pattern Is score reasonable? Remove selected faults Restore patterns Sort faults with scores Report the results of fault diagnosis 그림 4. 제안하는고장탈락방법을이용한고장진단 과정 Fig. 4. The procedure of fault diagnosis based on fault simulation. End 패턴이없을때까지반복한다. 고장탈락을이용한고장진단은더나은성능을위하여정렬된테스트패턴을적용하여수행될수있다. 고장탈락방법에제안하는정렬된고장후보목록및정렬된테스트패턴을적용한고속고장진단과정을그림 4에나타내었다. 그림 4의음영으로나타낸곳이기존고장진단과정과다른차이점이있는부분이다. 테스트패턴은중간값을이용한방법으로미리정렬한후준비하고고장후보목록은고장시뮬레이션을수행하기전에정렬시켜야한다. 그리고고장탈락방법을사용하여고장시뮬레이션및매칭알고리듬을적용한다. Ⅲ. 실험본논문에서제안한고속고장진단을위해고장후보정렬과테스트패턴정렬을적용한고장탈락방법의성능을검증하기위해여러가지경우에대한고장진단결과를비교하였다. 완전주사 (full scan) 형태로합성한 ISCAS 89 벤치마크를실험회로로사용하였고, 테스트패턴은 TetraMax [10] 를이용하여생성했다. 결함이있는회로를설정하기위하여, 각각 1개에서 3개의고장을무작위로선정한후실험회로에삽입하여각고장의개수별대상회로당 30개씩의고장회로를생성했다. 고장기록은주어진테스트패턴으로고장회로를고장시뮬레이션한고장응답과정상회로의결과를비교하여생성했다. 제안된기법의성능평가를위해기존논문 [1] 과비교하는방식을채택하였다. 기존논문 [1] 은고장진단을위해병렬고장진단시뮬레이션을사용하였으며, 본논문에서도병렬고장시뮬레이션과매칭알고리듬을이용하여고장진단을수행했다. 모든실험은 SUN Fire 880 서버에서수행했다. 고장진단의결과는 FHR (first hit rank) 과 CPU (CPU time) 값으로표 1과표 2에정리하였다. FHR은실제고장을찾을때까지조사해야하는고장후보수의평균값을그리고 CPU는전체고장진단을수행할때걸린총시간의평균값을나타낸다. 표 1과표 2에서 1개에서 3개까지의서로다른고장개수가삽입된세가지경우를각각 10개의회로에대하여고려하였다. 표 1에서는고장의개수와회로별로기존논문 [1] 의결과값과넓이우선정렬방식을응용하여고장탈락을수행한방법및깊이우선정렬방식을응용하여고장 (252)
2009 년 3 월전자공학회논문지제 46 권 SD 편제 3 호 37 표 1. 정렬된고장후보목록을사용하여고장탈락방법을적용한고장진단결과 Table 1. The result of fault diagnosis using fault dropping technique with fault candidate ordering. 1 fault 2 faults 3 faults Circuit [1] BF DF [1] BF DF [1] BF DF FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) s1196 1.00 0.98 1.00 0.88 1.00 0.73 1.03 1.57 1.03 1.13 1.03 0.96 1.03 2.05 1.27 1.23 1.20 1.05 s1238 1.00 0.94 1.00 0.88 1.00 0.76 1.00 1.58 1.03 1.25 1.00 1.02 1.00 2.07 1.30 1.42 3.23 1.19 s1488 1.00 1.32 1.00 0.99 1.00 0.82 1.03 1.92 2.23 1.30 1.07 1.05 1.03 2.36 5.77 1.27 5.33 1.06 s1494 1.00 1.48 1.00 1.13 1.00 0.91 1.00 2.12 2.43 1.36 1.37 1.08 1.00 2.68 3.80 1.46 2.63 1.19 s5378 1.00 5.54 1.00 3.87 1.00 3.44 1.00 7.89 1.53 5.30 1.17 4.63 1.00 11.94 1.43 6.95 1.23 5.83 s9234 1.00 8.55 1.00 5.94 1.00 5.51 1.00 18.39 1.07 8.40 1.03 7.55 1.23 26.85 1.77 9.73 1.87 8.70 s13207 1.00 22.35 1.00 13.18 1.00 12.46 1.17 31.95 1.37 15.19 2.93 13.36 1.00 47.59 1.53 20.58 3.43 18.14 s15850 1.00 14.84 1.00 10.78 1.00 10.13 1.30 44.41 1.33 20.07 1.40 19.06 1.30 53.76 1.40 22.53 1.37 20.45 s35932 1.00 10.36 1.00 9.45 1.00 9.03 1.00 12.89 1.17 12.07 1.00 11.00 1.00 16.39 2.37 13.24 4.97 12.09 s38584 1.00 81.01 1.00 60.97 1.00 54.46 1.00 168.10 3.10 75.93 2.30 68.72 1.00 227.05 2.27 85.36 2.40 78.31 표 2. 세가지테스트패턴정렬방식을사용하여고장탈락방법을적용한고장진단결과 Table 2. The result of fault diagnosis using fault dropping technique with test pattern ordering. 1 fault 2 faults 3 faults Circuit max mid min max mid min max mid min FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) FHR CPU(s) s1196 1.00 0.75 1.00 0.73 1.00 0.73 1.27 1.00 1.03 0.92 2.37 0.91 1.50 1.15 1.43 1.07 2.63 1.04 s1238 1.00 0.76 1.00 0.76 1.00 0.80 1.00 1.00 1.00 1.07 2.87 1.09 1.17 1.18 1.10 1.27 3.53 1.22 s1488 1.00 0.82 1.00 0.85 1.00 0.83 1.07 1.04 1.17 1.10 1.03 0.98 1.30 1.13 1.30 1.16 2.43 0.99 s1494 1.00 0.87 1.00 0.91 1.00 0.89 1.37 1.12 1.40 1.15 1.00 1.11 6.57 1.24 2.70 1.23 1.23 1.24 s5378 1.00 3.56 1.00 3.65 1.00 3.57 1.23 4.42 1.20 4.68 3.63 4.44 2.90 5.72 1.13 6.04 3.67 5.53 s9234 1.00 5.54 1.00 5.51 1.00 5.50 1.00 7.53 1.03 7.50 1.03 7.65 1.27 9.30 1.87 8.67 1.87 9.06 s13207 1.00 12.45 1.00 12.59 1.00 12.85 1.03 15.13 1.03 14.32 3.10 13.24 1.03 19.80 1.87 17.49 3.40 17.07 s15850 1.00 9.78 1.00 9.36 1.00 9.50 1.33 18.67 1.40 18.03 1.33 20.90 1.37 19.49 1.33 18.48 1.40 19.30 s35932 1.00 9.19 1.00 9.06 1.00 8.87 1.13 11.09 1.17 11.00 1.33 10.74 1.17 12.84 2.67 12.50 3.13 11.98 s38584 1.00 54.46 1.00 53.18 1.00 54.96 1.33 67.21 2.43 65.38 2.33 69.26 2.07 80.70 2.37 76.67 1.63 78.63 탈락을수행한방법을비교하였다. 각각의방법은 [1], BF 및 DF로나타내었다. 표 2에서는깊이우선탐색방법을응용한고장탈락방법을기반으로테스트패턴의정렬방식을다르게적용하여고장진단한결과를보였다. PA 값이가장큰테스트패턴을우선적으로사용한방법을 max로나타내었으며, PA 값이가장작은테스트패턴을먼저적용한방법을 min으로표시하였다. 그리고중간값의 PA를사용하는제안하는테스트패턴정렬방법을 mid로나타내었다. 표 1과표 2를바탕으로고장탈락방법, 정렬된고장후보목록및정렬된테스트패턴의사용의성능을평가하겠다. 1. 고장탈락방법의성능평가고장탈락방법자체의성능을평가하기위해서고장탈락방법을적용하지않은고장진단시간결과와고장탈락방법만을적용한고장진단시간결과를비교하였다. 두가지방법모두응용된넓이우선탐색방법을적용하여고장진단을수행했으며, 테스트패턴은 TetraMax에서생성된패턴을그대로사용하였다. 비교논문 [1] 에서와같이고장탈락을적용하였을경우에많게는 64% 그리고적게는 6% 의시간절감효과를얻을수있다. 그리고고장진단시간을평균 36% 단축시킬수있다. 2. 정렬된고장후보목록을사용한고장탈락방법의성능평가깊이우선탐색방식과넓이우선탐색방식을응용하여적용한고장탈락방법의비교결과를그림 5에나타내었다. 각각의정렬된고장후보목록을고장탈락방법에적용하였으며테스트패턴은 TetraMax에서생성된패턴을수정없이사용하였다. 그림 5에서비교기준값은넓이우선탐색방식이며, 고장진단의시간결과비교값이 1보다작을수록깊이우선탐색방법이고장진단시간단축에효과적인것을의미한다. 깊이우선탐색방식을응용하여고장탈락을적용한고장진단은넓이우선탐색방식을응용하여적용한경우보다크게는 24% 적게는 4% 의시간절감효과를얻을수있다. 그리고고장진단시간을평균 12% 단축시킬수있다. (253)
38 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법이주환외 그림 5. 두가지고장후보정렬방식을사용하여고장 탈락방법을적용한고장진단시간결과비교 Fig. 5. The CPU time ratio of the case of depth-first search : the case of breadth-first search (DF/BF). 그림 7. 중간값을이용해정렬한테스트패턴을사용한 고장진단정확도결과비교 Fig. 7. The comparison of accuracy for fault diagnosis using test pattern ordering (mid). 3. 정렬된테스트패턴을사용한고장탈락방법의성능평가표 2에서로다른방식으로정렬한테스트패턴을사용한고장진단결과를나타냈다. 각방식을비교해보면, 중간값의 PA 값을가지는테스트패턴을우선적으로사용하는것이가장우수한성능을보인다. 중간값의 PA 값을가지는테스트패턴이고장진단시간결과에주는영향을그림 6에나타내었다. 비교의기준이되는고장진단시간결과값은 TetraMax로생성한테스트패턴을이용했으며, 비교값이 1보다작을수록고장진단시간이단축되는것을의미한다. 중간값을이용한테스트패턴정렬방법은테스트패턴정렬방법을사용하지않았을경우보다 10% 에서 -10% 의고장진단시간단축효과를나타내며, 평균적으로 1% 그림 6. 중간값을이용해정렬한테스트패턴을사용한 고장진단시간결과비교 Fig. 6. The CPU time ratio of the case of mid-point : the case of no test pattern ordering (mid/df). 그림 8. 깊이우선탐색을응용하여정렬한고장후보 목록과중간값을이용하여정렬한테스트패턴을사용하여고장탈락방법을적용한고장진단시간결과비교 Fig. 8. The CPU time ratio of the proposed case : the previous case (mid/[1]). 증가하는결과를보인다. 하지만, 회로의크기가커질수록시간단축의효과가점점향상되는것을알수있다. 또한, 중간값을이용해정렬한테스트패턴을이용할경우에그림 7과같이고장진단정확도가향상되는것을확인할수있다. 그림 7의가로축은실험회로를나타내고세로축은고장진단의정확도인 FHR 값을의미한다. 하나의고장이삽입된경우는그림 7에표시하지않았다. 왜냐하면중간값을이용해서테스트패턴을정렬해서사용한경우 (mid) 와그렇지않은경우모두 FHR 1인정확한고장진단을수행하기때문이다. 하지만삽입된고장의수가두개인경우와세개인경우에는중간값을이용하여테스트패턴을정렬하였을때그렇지않았던때보다각각 10%, 36% 의고장진단성능의향상을나타낸다. 따라서고장탈락을위해정렬된테스트패턴을사용하는것은고장진단시간의단축 (254)
2009 년 3 월전자공학회논문지제 46 권 SD 편제 3 호 39 효과는물론고장진단의정확도를높여준다. 제안하는고장후보정렬방식과테스트패턴정렬방법을모두적용한고장탈락을사용하는고속고장진단방법의시간결과를그림 8에서비교하였다. 제안하는고속고장진단은기존의방법과비교해서최대 68% 에서최소 13% 의시간절감효과를나타내었으며, 평균 43% 의고장진단시간을단축시킨다. Ⅳ. 결론본논문에서는고속고장진단을위하여깊이우선방식을이용하여정렬한고장후보목록과중간값의 PA 값을가지는테스트패턴을우선적으로사용하여고장점수를기준으로고장탈락을시키는방법을제안하였다. 고장탈락방법은전체고장진단의수행시간을평균 36% 줄여주며, 정렬된고장후보목록과정렬된테스트패턴을사용함으로써고장진단성능을보다향상시킬수있다. 정렬된고장후보목록과정렬된테스트패턴을추가적으로사용함에따라, 수행시간이평균 12% 정도더향상될뿐만아니라고장진단의정확도가평균 23% 증가한다. 테스트대상회로의크기가증가할수록고장탈락에의한단축효과가크게나타남에따라고장진단의수행시간이줄어드는것을확인할수있다. 또한, 회로에존재하는고장의수가많을수록, 제안하는고속고장진단방법이효율적임을확인할수있다. 제안하는정렬된고장후보목록과정렬된테스트패턴을사용한고장탈락기법은기존의고장진단방법과비교하여평균 43% 줄어든고장진단수행시간을나타내므로빠르게변화하는시장에대응하는적절한수단이될수있다. fault analysis, in Transactions on Computers, pp. 98-103, 1994. [4] J. Lee, Y. Lim and S. Kang, A fault dropping technique using fault scores for fast fault diagnosis, in Proceedings of Korea Test Conference, 2007. [5] I. Pomeranz and S. M. Reddy, The accidental detection index as a fault ordering heuristic for full-scan circuits, in Proceedings of Design, Automation and Test in Europe, pp. 1008-1013, 2005. [6] H. D. Schnurmann, E. Lindbloom and R. G. Carpenter, The weighted random test-pattern generator, in Transactions on Computers, Vol. C-24, pp. 695-700, 1975. [7] K. Shigeta and T. Ishiyama, An improved fault diagnosis algorithm based on path tracing with dynamic circuit extraction, in Proceedings of International Test Conference, pp. 235-244, 2000. [8] V. C. Vimjam and M. S. Hsiao, Efficient fault collapsing via generalized dominance relations, in Proceedings of VLSI Test Symposium, 2006. [9] H. K. Lee and D. S. Ha, HOPE: an efficient parallel fault simulator for synchronous sequential circuits, in Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, pp. 1048-1058, 1996. [10] TetraMax Reference Manual. Release 2004. 12, Synopsys Inc., Mountain View, CA, 2001. 참고문헌 [1] J. Lee, Y. Lim, H. Cho and S. Kang, An accurate matching algorithm with essential factors for fault diagnosis, in Proceedings of International SoC design Conference, pp. 301-304, 2006. [2] P. R. Menon, Y. Levendel and M. Abramovici, Critical path tracing in sequential circuits, in Proceedings of International Conference on Computer-Aided Design, pp. 162-165, 1988. [3] Y. Karkouri, E. M. Aboulhamid, E. Cerny and A. Verreault, Use of fault dropping for multiple (255)
40 고속고장진단을위해고장후보정렬과테스트패턴정렬을이용한고장탈락방법이주환외 저자소개 이주환 ( 학생회원 ) 2003 년연세대학교전기전자공학과학사졸업. 2005 년연세대학교전기전자공학과석사졸업. 2009 년현재연세대학교전기전자공학과박사과정. < 주관심분야 : SoC 설계, Diagnosis, BIRA, CAD, DFT> 김홍식 ( 정회원 ) 1997 년연세대학교전기공학과학사졸업. 1999 년연세대학교전기및컴퓨터공학과석사졸업. 2004 년연세대학교전기전자공학과박사졸업. 2004 년 ~2005 년 Virginia 공대박사후연구원. 2006 년삼성전자시스템 LSI 사업부책임연구원. 2009 년현재연세대학교 TMS 사업단연구교수. < 주관심분야 : SoC 설계, 테스트 > 임요섭 ( 학생회원 ) 2004 년연세대학교전기전자공학과학사졸업. 2006 년연세대학교전기전자공학과석사졸업. 2009 년현재연세대학교전기전자공학과박사과정. < 주관심분야 : Diagnosis, CAD, DFT> 강성호 ( 평생회원 ) 1986 년서울대학교제어계측공학과학사졸업. 1988 년 The University of Texas, Austin 전기및컴퓨터공학과석사졸업. 1992 년 The University of Texas, Austin 전기및컴퓨터공학과박사졸업. 1992 년미국 Schlumberger Inc. 연구원. 1994 년 Motorola Inc. 선임연구원. 2009 년현재연세대학교전기전자공학과교수. < 주관심분야 : SoC 설계, SoC 테스트 > (256)