19

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020

TEST TIME OPTIMIZATION BY REVISITING NOTES IN

VLSI BIST TECHNIQUE

H. Sribhuvaneshwari

Research scholar, ECE Department, Kalasalingam Academy of Research and Education,

Krishnankoil, Tamilnadu, (India).

E-mail: havisriece@gmail.com ORCID: https://orcid.org/0000-0002-4804-4171

K. Suthendran

HoD/ IT Department, Kalasalingam Academy of Research and Education,

Krishnankoil, Tamilnadu, (India).

E-mail: k.suthendran@klu.ac.in ORCID: https://orcid.org/0000-0002-7030-4398

Recepción:

05/12/2019

Aceptación:

08/01/2020

Publicación:

23/03/2020

Citación sugerida:

Sribhuvaneshwari, H., y Suthendran, K. (2020). Test Time Optimization by Revisiting Notes in VLSI

BIST Technique. 3C Tecnología. Glosas de innovación aplicadas a la pyme. Edición Especial, Marzo 2020, 19-33.

http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Suggested citation:

Sribhuvaneshwari, H., & Suthendran, K. (2020). Test Time Optimization by Revisiting Notes in VLSI

BIST Technique. 3C Tecnología. Glosas de innovación aplicadas a la pyme. Edición Especial, Marzo 2020, 19-33.

http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

20 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020

ABSTRACT

An eective method for test time minimization in Built In Self Test (BIST) using graph

theory concept with revisiting of node is incorporated in this article. Here the shortest

Hamiltonian path of ISCAS89 benchmark circuit s396 is taken as an example. Minimum

spanning tree with revisiting nodes is applied for s386 circuit that optimizes the time cycle

for testing. Result shows that minimum spanning tree with revisiting the nodes will reduce

the time cycle without compromising the test quality. Hence an eective testing is achieved

using graphical approach.

KEYWORDS

BIST, Shortest Hamiltonian path, Revisiting node, Test time.

21 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254 – 4143 Edición Especial Special Issue Marzo 2020

1. INTRODUCTION

In this super fast technical generation the growth of technology is massive in both technical

and product aspect. Testing is an essential part which deals with the quality of the product

before a microelectronic product is launched in the market where BIST is a testing scheme

that is capable of nding faults in integrated circuits (ICs) to make faster testing at less-

expensive with low power constraints (Girard, Nicolici, & Wen, 2010). It plays a vital role

in electronic industry because a device that needs to be tested at higher level (levels being:

Chip – board – system – system in eld) costs 10 time (and possibly more) that of cost of

testing it a lower level. Digital testing is declared as testing a digital circuit to validate that it

performs the particular logic functions and in appropriate time. In case of VLSI testing, it

is not of much concern as how many chips are binned as awed; rather important is how

many awed chips are binned as normal. So, trade and industry expects “VLSI testing”

is to result in an accuracy of perfect chips with its functionality. Optimized test time and

scheming test power are contradictory targets and therefore optimization of testing for both

attributes is challenging. This topic has been addressed in the recent literature (Nicolici

& Al-Hashimi, 2003; Sakurai & Newton, 1990; Shanmugasundaram & Agrawal, 2011;

Shanmugasundaram & Agrawal, 2012; Gogoi & Kalita, 2014; Venkataramani, Sindia, &

Agrawal, 2014). The BIST vectors are speedy than ATE in terms of application time,

thus follow-on improvement in test time with low power (Larsson, 2006). The test vector

application time ratio between ATE and BIST is represented by “α”. If α= 100 than the

application time of a vector in ATE is 100 times longer than the vector application of

BIST (where α >1).The total time required for test is equivalent to the addition of required

number of time cycles to travel from source node to destination.

2. PRIOR WORK

A modern approach is introduced to minimize the test time for power constrained tests

(Biswas, Das, & Petriu, 2006; Das et al., 2008; Shanmugasundaram & Agrawal, 2011, 2012)

implements a monitor to observe the movement in the scan chain of a built-in self-test

(BIST). According to the switching activity the test clock frequency varies from high to low

both the parameters are inversely proportional i.e., test clock frequency raise if there is low

switching activity in the scan chain else falls. This approach attains 20-50% reduction in test

22 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

time of BIST circuits with a little area overhead. Reusable scan chains (Lai, Kung, & Lin,

1993) and pattern overlapping (Zhou, Ye, Li, Wu, & Ke, 2009; Bryant, 1986; Tehranipoor,

Nourani, & Chakrabarty, 2005; Chloupek, Novak, & Jenicek, 2012; Chloupek, Novak, &

Jenicek, 2012; Alpert et al., 2018) eradicates unwanted scan chain operations using patterns

that bear a resemblance to the previous pattern, so the number of scan shifting is minimized.

Hence high reduction is achieved on availability of such patterns. The single xed order

twisted ring-counter design proposed in (Tharakan & Mathew, 2015) drops down the test

application cycle with multiple programmable twisted-ring counters (PTRC). Huge number

of unique test patterns based on the stipulation of recongurable run-time programmable

multiple twisted-ring-counter is anticipated which is an on-chip test generation scheme.

Spontaneous strategy is implemented in (Bhakthavatchalu, Krishnan, Vineeth, & Devi,

2014) select the best possible seed and the quantity of the irregular test examples to be

produced which reduces the testing time signicantly. LFSR reseeding strategies proposed

in (Kim & Kang, 2006; Chandra & Chakrabarty, 2003; Pathak & Pathak, 2016) are broadly

received in rationale BIST to improve fault perceptibility and abbreviate test application

time for incorporated circuits.

Test comes about on ISCAS and expansive ITC circuits appear that the exhibited procedure

can accomplish 100 % fault scope with short test time by utilizing just 0.23 –2.75% of inside

nets. Test application time optimization in accumulator-based test-pattern generation is

projected in (Magos, Voyiatzis, & Tarnick, 2010; Voyiatzis, 2005, 2006, 2008; Manich,

Garcia-Deiros, & Figueras, 2007; Liang, Zhang, You, Li, & Hosam, 2013). The problem of

eciently generating test patterns which is used in nding the shortest Hamiltonian path in

an associated CUT’s directed graph that results tremendously low demand for hardware.

Usage of accumulator structure is the better solution to the problem of minimizing the

number of cycles needed for generating a set of deterministic test patterns in a novel test

pattern generation. Further enhancement can be concentrated in terms of minimizing

larger search space and the exact computation of the shortest Hamiltonian path in the test-

pattern graph. Revisiting nodes can reduce the test application time.

23 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

3. TEST PATTERN SELECTION

All VLSI chips after the manufacturing process are applied for fault analysis, in such a case

it is not possible of generating all the test vectors, at the same time dierent patterns detects

the same fault which increases the complexity of test vector and its storage requirement.

For C17 benchmark circuit the following six test patterns are high in terms of fault coverage

which is shown in Table 1. These patterns are considered as node here.

T=[T[1],T[2],T[3],T[4],T[5],T[6]]=T[0,11,14,17,28,31]

Table 1. Test vector set of s396 circuit.

Test Vector Inputs [6:0]

T1 0000101

T2 0000110

T3 0001011

T4 0001110

T5 0010101

T6 1010000

The odd value sequence of (31,3) is {0,3,6,9,12,15,18,21,24,27,30,2,5,8,11,14,17,20,23,26

,29,1,4,7,10,13,16,19,22,25,28,31}. Likewise it is preceded for all possible combination i.e.,

(31, n). Here n is the odd numbers in-between (1 to 31). In Table 2 decimal representation

of the test vectors are given in rst row, column and their location are given in 5*5 matrix

forms. Matrix size is equivalent to the number of test vectors in the test vector set of the

concern circuit test pattern’00000’ is negligible, so ve test patterns are taken for calculation.

(2

n

+1) & (2

n

+3) sequence i.e., 3, 5,9,17 & 5, 7, 11, 19 is calculated by means of Hamiltonian

distance.

4. DEFINITIONS

Let k is the input to the particular circuit then 2

k

test vectors are required to test the circuit.

Test vector set is derived by ltering the high fault coverage test vectors from the actual

number of test vectors (here BIST analysis & diagnosis tool is used lter six high fault

coverage test vectors of s396 benchmark circuit). In order to avoid the problem called

pattern minimization a technique is carried to compare the entire test vector set based on

the fault detection ability, if many test vectors detects the same fault with one bit variation in

24 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

the test vector sequence than that place is lled with ‘x’, by this method here six test vectors

are found as essential for ISCAS89 s396 benchmark circuit. When 128 test vectors are

optimized to six test vectors then the test time eectively reduced to the minimum. For this

s396 circuit 128 test vectors are required to test the circuit then six test vectors are ltered

by using BISTAD tool. A test vector set T is given below:

T=[T[1],T[2],T[3],T[4],T[5],T[6]]=T[5,6,11,14,21,88]

These six test vectors are considered as node here, all odd value from 0 to 127 are taken

in account to formulate the sequence. The odd value sequence of (127,3) is {0,3,6,9,12,15

,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99,1

02,105,108,111,114,117,120,123,126,1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52

,55,58,61,64,67,70,73,76,79,82,85,88,91,94,97,100,103,106,109,112,115,118,121,124,12

7,2,5,8,11,14,17,20,23,26,29,32,35,38,41,44,47,50,53,56,59,62,65,68,71,74,77,80,83,86,8

9,92,95,98,101,104,107,110,113,116,119,122,125}.Likewise it is preceded for all possible

combination i.e., (127, n). Here n is the odd numbers in-between (0 to 127) because k =

128. In Table 2 decimal representation of the test vectors are given in rst row, column and

their location are given in 6*6 matrix forms. Matrix size is equivalent to the number of test

vectors in the test vector set of the concern circuit. In general for k inputs 2

k

-1 matrix are

required to derive A

min

and A

vec

matrix. A

min

and Avec are derived by nding the minimum

values of a particular point for example all matrix value of 6 to 11 are compared and got

1 as minimum value which is taken for A

min

and the corresponding matrix value A5 is the

A

vec

value. Addend patterns are in the form of 2

n

+1 i.e., 2

1

+1=3, 2

2

+1=5,… if the addend

patterns are in the form of 2

n

+1 then 3,5,9,17,33 and 65 are its test pattern set.

5. PROPOSED METHOD

In this paper minimum spanning tree is introduced rather than Hamiltonian path

(Hamiltonian path is a path which visits each vertex exactly once and also returns to

the starting vertex) in the graphical construction of the c17 & s386 benchmark circuit.

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a

tree is minimal. Addend patterns are in the form of 2

n

+1 & 2

n

+ 3 are taken to compare

the Hamiltonian path time and minimum spanning tree time cycles.

25 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Table 2. Amin of c17 circuit with respect to (2n + 1) test patterns.

Amin 11 14 17 28 31

11 x 1 2 1 3

14 10 x 1 5 1

17 5 11 X 14 5

28 5 1 4 x 1

31 15 6 2 11 x

Figure 1. Hamiltonian path of c17 with Addend patterns are in the form of (2

n

+ 1).

Figure 2. Minimum spanning tree of c17 with Addend patterns are in the form of (2

n

+ 1).

The shortest Hamiltonian path for c17 circuit is 28 14 31 17 11 (1, 1, 2, 5) with

corresponding weights and its total weight is 9 but in case of minimum spanning tree 4 time

cycle are required (Figure 1 & 2). For Addend patterns are in the form of 2

n

+ 3 and the

Hamiltonian path through 1728 113114 and their corresponding weights are (1, 2,

4, 3) totally 10 time cycles are involved whereas in minimum spanning tree with revisiting

it is reduced to 7 which denotes that 14 times cycles (Figure 3 & 4) are required for testing.

Table 3. Amin of c17 circuit with respect to (2n + 3) test patterns.

Amin 11 14 17 28 31

11 x 14 9 10 4

14 4 x 13 2 10

17 5 5 x 1 2

28 2 10 4 X 13

31 2 3 11 5 x

26 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Figure 3. Hamiltonian path of c17 with Addend patterns are in the form of (2

n

+ 3).

Figure 4. Minimum spanning tree of c17 with Addend patterns are in the form of (2

n

+ 3).

Table 4. Test vector set of s396 circuit.

Test Vector Inputs [6:0]

T1 0000101

T2 0000110

T3 0001011

T4 0001110

T5 0010101

T6 1010000

Revisiting can reduce the testing time, here s396 benchmark circuit is taken as example

which deals with 7 inputs and therefore 2

k

test vectors are required to test the circuit i.e., 128

test vectors. A

min

and A

vec

are tabulated to derive the s396 circuit’s graphical representation.

All odd value sequence from 0 to 127 is taken in account for A

min

and Avec calculation.

The shortest Hamiltonian path for s396 circuit is 6 21 88 5 1114 (1, 5, 3, 2,

1) with corresponding weights and its total weight is 12 but in case of minimum spanning

tree 11 time cycle are required (Figure 2). Figure 3 shows the graphical representation of

s386 circuit where A

min

& Avec are derived with the consolidation of 64 matrices (all odd

sequence from 0 to 127).

27 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Figure 5. Graphical representation of s396 circuit.

Table 5. A

min

of s386 circuit with respect to (2

n

+ 1) test patterns.

A

min

5 6 11 14 21 88

5 x 43 2 1 16 19

6 15 x 1 8 3 7

11 42 27 x 1 2 37

14 7 24 25 x 15 2

21 48 41 22 57 x 3

88 5 46 3 6 21 x

28 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Table 6. A

min

of s386 circuit with respect to (2

n

+ 3) test patterns.

A

min

5 6 11 14 21 88

5 x 11 2 53 48 17

6 21 x 1 24 3 6

11 46 73 x 33 2 7

14 13 24 23 x 1 30

21 16 59 18 11 x 1

88 9 58 49 18 27 x

Figure 6. Hamiltonian path of s386 with Addend patterns are in the form of (2

n

+ 1).

Figure 7. Minimized time spanning tree of s396 with Addend patterns are in the form of (2

n

+ 1).

For Addend patterns are in the form of 2

n

+ 3 the Hamiltonian path through 1421

885611 and their corresponding weights are (1, 1, 9, 11, 1) totally 23 time cycles

are involved whereas in minimum spanning tree with revisiting it is reduced to 14 which

denotes that 14 times cycles (Figure 3) are required for testing.

Figure 8. Hamiltonian path of s386 with Addend patterns are in the form of (2

n

+ 3).

Figure 9. Minimized time spanning tree of s396 with Addend patterns are in the form of (2

n

+ 3).

29 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

6. COMPARISON

Benchmark circuit

Addend pattern

form

Hamiltonian path Time cycle

requirement

Minimum spanning tree Time

cycle requirement

C17

2

n

+ 1 9 4

2

n

+ 3 10 7

S386

2

n

+ 1 12 11

2

n

+ 3 23 14

Table 7. Comparison table for time cycle involvement in Hamiltonian path, minimum spanning tree with revisiting

nodes.

Figure 10. Graph for time cycle involvement in Hamiltonian path, minimum spanning tree with revisiting nodes.

7. CONCLUSION

In this paper we have presented a graph theory concept called minimum spanning tree

with revisiting nodes instead of Hamiltonian path for c17 & s396 benchmark circuit which

results in optimized test time. Result shows that minimum spanning tree with revisiting

the nodes will reduce the time cycle for testing. The above mentioned Table 7 & Figure 10

shows that minimum spanning tree eectively reduces the number of test time cycles for

testing. In future it can be implemented to test nano memories.

30 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

REFERENCES

Alpert, C. J., Chow, W. K., Han, K., Kahng, A. B., Li, Z., Liu, D., & Venkatesh, S.

(2018, March). Prim-Dijkstra Revisited: Achieving Superior Timing-driven Routing

Trees. In Proceedings of the 2018 International Symposium on Physical Design (pp. 10-17).

ACM.

Bhakthavatchalu, R., Krishnan, S., Vineeth, V., & Devi, M. N. (2014, July).

Deterministic seed selection and pattern reduction in Logic BIST. In 18th International

Symposium on VLSI Design and Test (pp. 1-2). IEEE.

Biswas, S., Das, S. R., & Petriu, E. M. (2006). Space compactor design in VLSI

circuits based on graph theoretic concepts. IEEE Transactions on Instrumentation and

Measurement, 55(4), 1106-1118. https://doi.org/10.1109/TIM.2006.876523

Bryant, R. E. (1986). Graph-based algorithms for boolean function manipulation. IEEE

Transactions on Computers, 100(8), 677-691. https://doi.org/10.1109/TC.1986.1676819

Chandra, A., & Chakrabarty, K. (2003). A unied approach to reduce SOC test data

volume, scan power and testing time. IEEE transactions on computer-aided design of integrated

circuits and systems, 22(3), 352-363. https://doi.org/10.1109/TCAD.2002.807895

Chloupek, M., Novak, O., & Jenicek, J. (2012, April). On test time reduction using

pattern overlapping, broadcasting and on-chip decompression. In 2012 IEEE

15th International Symposium on Design and Diagnostics of Electronic Circuits & Systems

(DDECS) (pp. 300-305). IEEE.

Chloupek, M., Novak, O., & Jenicek, J. (2012, April). On test time reduction using

pattern overlapping, broadcasting and on-chip decompression. In 2012 IEEE

15th International Symposium on Design and Diagnostics of Electronic Circuits & Systems

(DDECS) (pp. 300-305). IEEE.

Das, S. R., Hossain, A., Biswas, S., Petriu, E. M., Assaf, M. H., Jone, W. B., &

Sahinoglu, M. (2008). On a new graph theory approach to designing zero-aliasing

space compressors for built-in self-testing. IEEE Transactions on Instrumentation and

Measurement, 57(10), 2146-2168. https://doi.org/10.1109/TIM.2007.910004

31 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Flores, P., Neto, H., Chakrabarty, K., & Marques-Silva, J. (1999, May). Test pattern

generation for width compression in BIST. In ISCAS’99. Proceedings of the 1999 IEEE

International Symposium on Circuits and Systems VLSI (Cat. No. 99CH36349) (Vol. 1, pp.

114-118). IEEE.

Girard, P., Nicolici, N., & Wen, X. (Eds.). (2010). Power-aware testing and test strategies for

low power devices. Springer Science & Business Media.

Gogoi, B., & Kalita, B. (2014). Algorithm to color a Circuit Dual Hypergraph for VLSI

Circuit. International Journal of Computer Science and Information Technologies, 5(4), 5047-

5052. http://ijcsit.com/docs/Volume%205/vol5issue04/ijcsit2014050447.pdf

Kim, H. S., & Kang, S. (2006). Increasing encoding eciency of LFSR reseeding-based

test compression. IEEE Transactions on Computer-Aided Design of Integrated Circuits and

Systems, 25(5), 913-917. https://doi.org/10.1109/TCAD.2005.855977

Lai, W. J., Kung, C. P., & Lin, C. S. (1993, February). Test time reduction in scan designed

circuits. In 1993 European Conference on Design Automation with the European Event in ASIC

Design (pp. 489-493). IEEE.

Larsson, E. (2006). Introduction to advanced system-on-chip test design and optimization (Vol. 29).

Springer Science & Business Media.

Liang, W., Zhang, D., You, Z., Li, W., & Hosam, O. (2013). A survey of techniques for

VLSI IP protection. Information Technology Journal, 12(12), 2324-2332. https://

doi.org/10.3923/itj.2013.2324.2332

Lien, W. C., Lee, K. J., Hsieh, T. Y., & Chakrabarty, K. (2014). Ecient LFSR

reseeding based on internal-response feedback. Journal of Electronic Testing, 30(6), 673-

685. https://doi.org/10.1007/s10836-014-5482-4

Magos, D., Voyiatzis, I., & Tarnick, S. (2010). An Accumulator—Based Test-Per-Clock

Scheme. IEEE Transactions on Very Large Scale Integration (VLSI). Systems, 19(6),

1090-1094. https://doi.org/10.1109/TVLSI.2010.2043452

32 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Manich, S., Garcia-Deiros, L., & Figueras, J. (2007). Minimizing test time in arithmetic

test-pattern generators with constrained memory resources. IEEE Transactions on

Computer-Aided Design of Integrated Circuits and Systems, 26(11), 2046-2058. https://doi.

org/10.1109/TCAD.2007.906465

Nicolici, N., & Al-Hashimi, B. (2003). Power-constrained testing of VLSI circuits (p. 178).

Kluwer Academic Publishers.

Pathak, V. K., & Pathak, V. K. (2016). Design of Input Vector Monitoring

Concurrent BIST based Architecture for 4-Bit Multiplier. International

Journal of Computer Applications, 153(5), 19-24. https://pdfs.semanticscholar.

org/9c0e/229b71f418dabcb96b54af0e8474116c9370.pdf

Sakurai, T., & Newton, A. R. (1990). Alpha-power law MOSFET model and its

applications to CMOS inverter delay and other formulas. IEEE Journal of solid-state

circuits, 25(2), 584-594. https://doi.org/10.1109/4.52187

Shanmugasundaram, P., & Agrawal, V. D. (2011, May). Dynamic scan clock control

for test time reduction maintaining peak power limit. In 29th VLSI Test Symposium (pp.

248-253). IEEE.

Shanmugasundaram, P., & Agrawal, V. D. (2012, January). Externally tested scan

circuit with built-in activity monitor and adaptive test clock. In 2012 25th International

Conference on VLSI Design (pp. 448-453). IEEE.

Tehranipoor, M., Nourani, M., & Chakrabarty, K. (2005). Nine-coded compression

technique for testing embedded cores in SoCs. IEEE transactions on very large scale integration

(VLSI) systems, 13(6), 719-731. https://doi.org/10.1109/TVLSI.2005.844311

Tharakan, A. S., & Mathew, B. K. (2015). Design and Implementation of an On-Chip

Test Generation Scheme Based on Recongurable Run-Time Programmable and

Multiple Twisted-Ring Counters. Procedia Computer Science, 46, 1409-1416. https://

doi.org/10.1016/j.procs.2015.02.059

33 http://doi.org/10.17993/3ctecno.2020.specialissue4.19-33

Venkataramani, P., Sindia, S., & Agrawal, V. D. (2014). A test time theorem and its

applications. Journal of Electronic Testing, 30(2), 229-236. https://doi.org/10.1007/

s10836-014-5447-7

Voyiatzis, I. (2005). Test vector embedding into accumulator-generated sequences: A

linear-time solution. IEEE Transactions on Computers, 54(4), 476-484. https://doi.

org/10.1109/TC.2005.69

Voyiatzis, I. (2006, September). Accumulator-based compression in symmetric transparent

RAM BIST. In International Conference on Design and Test of Integrated Systems in Nanoscale

Technology, 2006. DTIS 2006. (pp. 273-278). IEEE.

Voyiatzis, I. (2008, March). On reducing aliasing in accumulator-based compaction.

In 2008 3rd International Conference on Design and Technology of Integrated Systems in Nanoscale

Era (pp. 1-12). IEEE.

Zhou, B., Ye, Y. Z., Li, Z. L., Wu, X. C., & Ke, R. (2009, March). A new low power

test pattern generator using a variable-length ring counter. In 2009 10th International

Symposium on Quality Electronic Design (pp. 248-252). IEEE.