Tallinn University
of Technology
DEPARTMENT OF COMPUTER
ENGINEERING
Chair for Computer Hardware
and Diagnostics
Research
Results (2000 - 2007)
Head of the Chair: Prof.
Raimund Ubar
The main research results obtained in the
recent years by the staff and students at the chair belong to the following
fields of Digital Design and Test:
Research results during 1992-1999
Diagnostic Modeling of
Digital Systems
A lot of
scientific interests of our research group has been devoted to the investigations
of decision diagrams as mathematical models for diagnostic simulation of
digital circuits and systems. In this field of basic research, our department
has a pioneering position with introducing Structurally Synthesized Binary
Decision Diagrams (SSBDD) as a special class of BDDs for logic level diagnostic
modeling of digital systems, and generalizing the BDDs for using at higher
level abstractions of digital systems [13].
The main
difference of SSBDDs compared to the traditional BDDs is in the novelty of
representing in BDDs the structural properties of logic circuits along their
functions. Differently from BDDs, which are generated by Shannon’s expansion,
SSBDDs are generated by a superposition procedure directly from the circuit
description which allowed to represent in the model one-to-one mapping between
the fault sites in circuit and nodes in SSBDDs. A formal definition of SSBDDs
is given in [9]. Optimization possibilities of SSBDDs are discussed in [8].
Promising results have been obtained by SSBDDs in logic simulation [5,6,8],
timing and delay simulation [4], design error diagnosis [1], and in test
generation [10 ].
A uniform
multi-level model for digital systems based on DDs as an extension and
generalization of the BDDs has been also developed by the group [11-15]. The DD
model allowed us to develop efficient methods for simulating digital systems in
a very fast way by uniform algorithms at different logic, RTL, ISA or
behavioral levels [2,3].
References:
1.
A.Jutman, R.Ubar. Design Error Diagnosis in Digital Circuits with
Stuck-at Fault Model. Journal of Microelectronics Reliability. Pergamon Press,
Vol. 40, No 2, 2000, pp.307-320.
2.
R.Ubar, A.Morawiec, J.Raik. Cycle-Based Simulation Algorithms for
Digital Systems Using High-Level Decision Diagrams. IEEE Proc. of Design Automation and Test in Europe.
Paris, March 27-30, 2000, pp. 743.
3.
R.Ubar, A.Morawiec, J.Raik. Back-Tracing and Event-Driven Techniques in
High-Level Simulation with Decision Diagrams. IEEE ISCAS’2000 Conference,
Geneva, May 28-31, 2000, Vol. 1, pp. 208-211.
4.
A.Jutman, R.Ubar. Application of Structurally Synthesized Binary
Decision Diagrams for Timing Simulation of Digital Circuits. Proceedings of the
Estonian Academy of Sciences, No 7/4, 2001, pp.269-288.
5.
A.Jutman, J.Raik, R.Ubar. On Efficient Logic-Level Simulation of Digital
Circuits Represented by the SSBDD Model. 23rd Int. Conf. on Microelectronics.
Nis, Yugoslavia, May 12-15 2002, Vol.2, pp.621-624.
6.
A. Jutman, J. Raik, R. Ubar. SSBDDs: Advantageous Model and Efficient
Algorithms for Digital Circuit Modeling, Simulation & Test. 5th Int.
Workshop on Boolean Problems. Freiberg, Germany, September 19-20, 2002,
pp.157-166.
7.
R.Ubar. Decision Diagrams and Digital Test. Proc. of the 6th
International Workshop on Electronics, Control, Measurement and Signals,
Liberec, Czechia, June 2-4, 2003, pp.266-273 (Invited plenary paper).
8.
R.Ubar, T.Vassiljeva, J.Raik, A.Jutman, M.Tombak, A.Peder. Optimization
of Structurally Synthesized BDDs. The 4th IASTED International Conference on
Modelling, Simulation and Optimization, Kauai, Hawaii, USA, August 17-19, 2004,
pp.234-240.
9.
A.Jutman, A.Peder, J.Raik, M.Tombak, R.Ubar. Structurally Synthesized
Binary Decision Diagrams. 6th International Workshop on Boolean Problems,
Freiberg, Germany, Sept. 2004, pp.271-278.
10.
A.Matrosova, A.Pleshkov, R.Ubar. Construction of the Tests of
Combinational Circuit Failures by Analyzing the Orthogonal Disjunctive Normal
Forms Represented by the Alternative Graphs. J. of Automation and Remote
Control. Publisher: Springer Science & Business Media B.V., 66 (2), 2005,
pp. 313-327.
11.
R.Ubar. Decision Diagrams and Digital Test. 41th International
Conference on Microelectronics, Devices and Materials – MIDEM 2005, Ribno at
Bled, Slovenia, Sept. 14.-16, 2005, pp.15-26. Invited plenary paper.
12.
R.Ubar. Decision Diagrams and Digital Test. Informacije MIDEM-Journal of
Microelectronics Electronic Components and Materials, 35(4), 2005, pp.187 -
195.
13.
O.Novak, E.Gramatova, R.Ubar. Handbook of Electronic Testing. CTU
Printhouse, Prague, 2005, 400 p.
14.
R.Ubar, T.Evartson, M.Kruus, H.Lensen, J.Raik. Diagnostic Modelling of
Digital Systems with Multi-Level Decision Diagrams. Proc. of the 17th IASTED
International Conference on Modelling and Simulation. Montreal, May 24.-26,
2006, pp. 207-212.
15. R.Ubar, J.Raik, H.Kruus,
H.Lensen, T.Evartson. Diagnostic Modelling of Digital Systems with Binary and
High-Level Decision Diagrams. In “Progress in Industrial Mathematics at ECMI
2006”, Series: Mathematics in Industry, Subseries: The European Consortium for
Mathematics in Industry , Vol. 12, 2007.
A new methodology of probabilistic analysis of CMOS
physical defects in integrated circuits [IC] for defect-oriented testing is
proposed [1]. The methodology is based on identification and estimation of the
probabilities of defects resulting from spot defects. To reduce the complexity
of simulation transistor level defects, a uniform functional fault model was
proposed for mapping physical defects to logic level [2,3]. The defects can be
modeled by Boolean differential equations which solutions represent the defect
activization conditions. The functional fault model can be regarded as a
general interface for mapping faults from one system level to another, helping
to carry out hierarchical test generation or hierarchical fault simulation in
digital systems.
A special IC DefSim embedded into a research
environment was developed for investigating CMOS physical defects (opens and
shorts) in real conditions [4,5]. The defects are physically implemented in
silicon in a big variety of locations inside a set of digital standard cells
and small circuits. Two measurement methods are supported: voltage and IDDQ
test.
The possibilities to represent high-level faults in
decision diagrams used for test generation are investigated in [6-8]. A new
class of sequentially untestable high-level faults was defined, called register
input logic stuck-on faults [7]. We showed that it is possible to identify
easily such faults from the register-transfer level description of the circuit.
We proved also by experiments that the considered faults form a large subclass
of all the untested faults.
References:
1. M.Blyzniuk, I.Kazymyra, W.Kuzmicz, W.A.Pleskacz,
J.Raik, R.Ubar. Probabilistic Analysis of CMOS Physical Defects in VLSI
Circuits for Test Coverage Improvements. Journal of Microelectronics
Reliability. Pergamon Press. Vol
41/12, Dec. 2001, pp 2023-2040.
2. R.Ubar. Mapping Physical Defects to Logic Level for
Defect Oriented Testing. Proc. Of International Symposium on Signals, Circuits
and Systems – SCS 2003, Vol. 2, Iasi, Romania, July 10-11, 2003, pp.453-456.
3. O.Novak, E.Gramatova, R.Ubar. Handbook of Electronic
Testing. CTU Printhouse, Prague, 2005, 400 p.
4. W.A.Pleskacz, T.Borejko, A.Walkanis, V.Stopjakova,
A.Jutman, R.Ubar. DefSim: CMOS Defects on Chip for Research and Education. 7th
IEEE Latin-American Test Workshop, March 26-29, 2006, Buenos Aires, Argentina,
pp.74-79.
5. T.Borejko, A.Jutman, W.Pleskacz, R.Ubar. DefSim:
Measurement Environment for CMOS Defects. Proc. 25th International Conference
on Microelectronics - MIEL, Vol. 2, Belgrade, Serbia and Montenegro, 14-17 May
2006, pp.679-682.
6. J.Raik, R.Ubar. T.Viilukas. High-Level Decision
Diagram based Fault Models for Targeting FSMs. Proceedings of the 9th IEEE
EUROMICRO Conference on Digital Systems Design DSD2006, Katvat, Croatia, 2006,
pp.353-358.
7. J.Raik, R.Ubar, A.Krivenko, M.Kruus. Hierarchical
Identification of Untestable Faults in Sequential Circuits. Proc. of 10th IEEE
EUROMICRO Conference on Digital System Design - DSD 2007, Lübeck, Germany,
August 27 - 31, 2007, pp.668-671.
8. J.Raik, R.Ubar, T.Viilukas, M.Jenihhin. Mixed
Hierarchical-Functional Fault Models for Targeting Sequential Cores. Journal of
Systems Architecture, 2007.
A novel hierarchical approach to test pattern
generation for sequential circuits described by mixed-level decision diagrams
(DD) was developed [1,2]. Both, data and control parts of the design are
handled in a uniform manner. The method combines deterministic and
simulation-based techniques. To improve the efficiency of searching test
patterns several improvements were developed like driving search by genetic
algorithms [3], using testability guidance [4], and introducing a new type of
functional fault model [5]. Based on the efficient use of low- and high-level
DDs, a very fast register transfer level (RTL) test generator DECIDER [1,2,6]
has been developed. It was shown that the proposed DD-based approach cn be used
also in higher than RTL like behavioral or instruction set architectural levels
[7]. A pure functional test generation method for finite state machines based
on the description of solely state transistion diagrams (STD) ws developed. The
method guarantees testing of all stuck-at faults in a two-level implementation
of the sum-of-product forms of the next state logic and the output logic
created from STD.
References:
1. J.Raik, R.Ubar. Fast Test Pattern Generation for
Sequential Circuits Using Decision Diagram Representations. Journal of
Electronic Testing: Theory and Applications. Kluwer Academic Publishers. Vol.
16, No. 3, pp. 213-226, 2000.
2. R.Ubar, J.Raik. Efficient Hierarchical Approach to
Test Generation for Digital Systems. 1st Int. Symp. on Quality of Electronic
Design, San Jose, California, March 20-22, 2000, pp. 189-195.
3. E.Ivask, J.Raik, R.Ubar. Fault Oriented Test Pattern
Generator for Sequential Circuits Using Genetic Algorithms. 7th Baltic
Electronics Conference, Tallinn, October 8-11, 2000, pp.129-132.
4. R.Ubar, J.Raik, T.Nõmmeots. Testability Guided
Hierarchical Test Generation with Decision Diagrams. 20th IEEE Conference
NORCHIP’2002, Copenhagen, Denmark, November 11-12, 2002, pp.265-271.
5. J.Raik, R.Ubar. Enhancing Hierarchical ATPG with a
Functional Fault Model for Multiplexers. 7th IEEE Workshop on Design and Diagnostics
of Electronic Circuits and Systems – DDECS 2004. Stara Lesna, Slovakia, April
18-21, 2004, pp. 219-222.
6. J.Raik, A.Krivenko, R.Ubar. Comparative Analysis of
Sequential Circuit Test Generation Approaches. Proc. of the 9th Biennial Baltic
Electronics Conference, Oct. 3-6, 2004, Tallinn, pp.225-228.
7. G.Jervan, R.Ubar, Z.Peng, P.Eles. Test Generation: A
Hierarchical Approach. In “System-level Test and Validation of
Hardware/Software Systems” by M.Sonza Reorda, Z.Peng, M.Violante. Springer
Series in Advanced Microelectronics, Vol.17, 2005, pp. 63-77.
8. R.Ubar, M.Brik, A.Jutman, J.Raik, T.Bengtsson,
S.Kumar. Functional Test Generation for Finite State Machines. Baltic
Electronics Conference. Laulasmaa, Oct. 2006, pp.205-208.
Verification and Error Diagnosis
In the field of design error diagnosis, a new
conception and method was developed, which allows to adopt in a straightforward
way the methods and tools of fault diagnosis used in hardware testing for the
use in design error diagnosis [1-2]. The main original features of the method
are: hierarchical approach, based on using structurally synthesized BDDs and
the idea of mapping stuck-at fault diagnosis into the final localization of the
design error. A new approach for design error diagnosis was developed that does
not exploit error models [3]. Based on diagnostic pre-analysis of the circuit,
a subcircuit suspected to be erroneous is extracted. Opposite to other known
works, re-synthesis of the subcircuit need not be applied to the whole function
of the erroneous internal signal in terms of primary inputs, it may stop at
arbitrary nodes inside the circuit. As the result the speed of rectification
can be significantly increased
The research group has participated in verification
related research in the framework of European 6th FP STREP project VERTIGO
(2006-2008) and in the national Development Center programme (2004-2007). The
international research partners include universities of Verona, Southampton and
Linköping. As a result of these projects, High-level Decision Diagram (HLDD)
based modeling for verification of register-transfer and system level digital
systems has been developed [4,5]. Efficient methods for code coverage analysis
and assertion checking [5] using HLDDs have been introduced.
References:
1. R.Ubar, D.Borrione. Design Error Diagnosis in Digital
Circuits without Error Model. In VLSI: Systems on Chip, Kluwer Academic
Publishers, 2000, pp.281-292.
2. A.Jutman, R.Ubar. Design Error Diagnosis in Digital
Circuits with Stuck-at Fault Model. Journal of Microelectronics Reliability.
Pergamon Press, Vol. 40, No 2, 2000, pp.307-320.
3. R.Ubar. Design Error Diagnosis with Resynthesis in
Combinational Circuits. Journal of Electronic Testing: Theory and Applications
19, 73-82, 2003. Kluwer Academic Publishers.
4. G.Guglielmo, F.Fummi, M.Jenihhin, G.Pravadelli,
J.Raik, R.Ubar. On the Combined Use of HLDDs and EFSMs for Functional ATPG.
EWDTS, Jerevan, 2007, pp.503-508.
5. M.Jenihhin, J.Raik, A.Chepurov, R.Ubar. Assertion
Checking with PSL and High-Level Decision Diagrams. Diggest of Papers IEEE 8th
Workshop on RTL and High Level Testing - WRTLT'07. Beijing, P.R.China, Oct.
12-13, 2007, pp.105-110.
Several methods for static compaction of sequential
circuit tests divided into independent test sequences have been developed and
investigated [1-5]. A novel
technique was proposed that implements effective representation of fault
matrices by weighted bipartite graphs [2]. In [3] three approaches genetic,
greedy and branch-and-bound algorithms were compared and discussed. It was
shown how to prune the search space by using dominant relationships of faults
and sequences. A method based on the branch-and-bound approach was
proposed in [4,5]. It includes a
preprocessing step for determining the set of essential vectors. The search
space was drastically reduced, and the proposed method offers significantly
faster performance than earlier genetic algorithm based and general-purpose
Boolean optimization methods.
The previous methods have scalability problems with
the bigger benchmarks. We have introduced a set of novel techniques speeding up
compaction for the larger tasks [6]. The new approach is based on enhanced
implication procedures and ranking of decisions during branch-and-bound search.
The experiments demonstrated improvement in orders of magnitude for designs
that exceed thousand logic gates.
References:
1. J.Raik, A.Jutman, R.Ubar. Fast and Efficient Static
Compaction of Test Sequences Based on Greedy Algorithms. Design and Diagnostics
of Electronic Circuits and Systems – DDECS‘2001, Györ, Hungary, April 18-20,
2001, pp.117-122.
2. J.Raik, A.Jutman, R.Ubar. Fast Static Compaction of
Test Sequences Using Implications and Greedy Search. Digest of European Test
Workshop, Stockholm, May 29 – June 1, 20001, pp. 207-210.
3. J.Raik, A.Jutman, R.Ubar. Fast Static Compaction of
Tests Composed of Independent Sequences: Basic Properties and Comparison of
Methods. Proc. of the 9th IEEE International Conference on Electronics,
Circuits and Systems – ICECS’2002 Vol. II. Dubrovnik, Croatia, September 15-18,
2002, pp.445-448.
4. J.Raik, A.Jutman, R.Ubar. Exact Static Compaction of
Sequential Circuit Tests using branch-and-bound and Search State Registration,
IEEE European Test Workshop, Corfu, Greece, May 26-29, 2002.
5. J.Raik, A.Jutman, R.Ubar. Exact Static Compaction of
Independent Test Sequences. Proceedings, BEC-2002, Tallinn, October 6-9, 2002,
pp.315-318.
6. I.Aleksejev, J.Raik, A.Jutman, R.Ubar. A Scalable
Static Test Set Compaction Method for Sequential Circuits. LATW’2008.
Submitted.
A new method for hierarchical fault simulation based
on multi-level Decision Diagrams (DD) was developed [1-2]. We suppose that a
register transfer (RT) level information along with gate-level descriptions for
blocks of the RT level structure are available. Decision diagrams (DDs) are
exploited as a uniform model for describing circuits at these representation
levels. The approach proposed allows to reduce time expenses in the comparison
to traditional gate-level fault simulation approach.
New gate-level fault simulation algorithms have been
developed and investigated in [3-7]. As the basis for simulation, structurally
synthesized BDDs were used to substitute the gate-level description with a
higher macro-level network model. Converting gate-level circuits to the
macro-level is accompanied with fault collapsing. As the result, the complexity
of the model was reduced. In [3] deductive and concurrent methods were
investigated, and the speed of simulation compared to the gate-level was
increased. In [4-5] a novel parallel fault analysis method for SSBDDs was
developed. For the faults at fanout stems a new full Boolean differential based
parallel fault analysis algorithm was proposed. The algorithm is equivalent to
exact critical path tracing. Because of the parallelism and higher abstraction
level modeling the speed of analysis is considerably increased. Experimental data showed that by the new method
considerable speed up has been achieved compared to the popular commercial
tools and other exact critical path tracing methods. In [6] additional
improvements were introduced to improve the calculation model. A new method for
topological analysis was suggested in [7] to generate an optimized model for
backtracing of faults to minimize the repeated calculations because of the
reconvergent fanouts. The speed of the fault analysis in several times
outperforms the speed of the current state-of-the-art commercial fault
simulators
References:
1. R.Ubar, J.Raik, E.Ivask, M.Brik. Multi-Level Fault
Simulation of Digital Systems on Decision Diagrams. IEEE Workshop on Electronic
Design, Test and Applications – DELTA’02, Christchurch, New Zealand, 29-31
January 2002, pp.86-91.
2. R.Ubar, J.Raik, B.Klüver. Algorithms for hierarchical
fault simulation in digital systems. Proc. of the 10th Int. Conf. MIXDES 2003,
Lodz, June 26-28, 2003, pp.530-535.
3. J.Raik, R.Ubar, S.Devadze, A.Jutman. Efficient
Single-Pattern Fault Simulation on Structurally Synthesized BDDs. Lecture Notes
in Computer Science, Vol. 3463, Springer Verlag, Berlin, Heidelberg, New York
2005, pp. 332-344.
4. S.Devadze, J.Raik, A.Jutman, R.Ubar. Fault Simulation
with Parallel Critical Path Tracing for Combinational Circuits Using
Structurally Synthesized BDDs. 7th IEEE Latin-American Test Workshop, March
26-29, 2006, Buenos Aires, Argentina, pp.97-102.
5. R.Ubar, S.Devadze, J.Raik, A.Jutman. Ultra Fast
Parallel Fault Analysis on Structural BDDs. 12th IEEE European Test Symposium –
ETS 2007, Freiburg, Germany, May 20-24, 2007, pp.131-136.
6. R.Ubar, S.Devadze, J.Raik, A.Jutman. Parallel Fault
Backtracing for Calculation of Fault Coverage. International Conference on
Microelectronics, Devices and Materials MIDEM, Workshop on electronic testing.
Bled, Slovenia, September 12-14, 2007, pp.165-170.
7. R.Ubar, S.Devadze, J.Raik, A.Jutman. Fast Fault
Simulation in Digital Circuits with Scan Path. 13th Asia and South Pacific
Design Automation Conference – ASP-DAC, Seoul, Korea, Jan. 21-24, 2008.
Timing Simulation and Delay Test
Meeting timing requirements is an important
constraint imposed on highly integrated circuits, and the verification of
timing of a circuit before manufacturing is one of the critical tasks to be
solved by CAD tools. A new approach and the implementation of several
algorithms to speed up gate-level timing simulation was proposed in [1,2].
Instead of gate delays, path delays for tree-like subcircuits (macros) are
used. Therefore timing waveforms are calculated not for all internal nodes of
the gate-level circuit but only for outputs of macros. The macros are
represented by structurally synthesized BDDs (SSBDD) which enable a fast
computation of delays for macros. In [3] it was shown that the speed-up of
timing simulation is directly proportional to the average size of macros in the
circuit. In [4,5] a macro level
method for delay fault simulation was proposed which outperformed the
performance of the gate-level analog.
Testing of high density System-on-Chips (SoC)
operating at high clock speeds is an important but difficult problem. Many faults,
like delay faults, in such sub-micron chips may only appear when the chip works
at normal operating speed and can only be detected by at-speed testing. We have
proposed a methodology for at-speed testing delay faults in links connecting
two distinct clock domains in a SoC [6-7]. Since most Network-on-Chip (NoC)
systems are built with GALS principles, this method is directly useable for
testing NoC interconnects. We give an analytical analysis about the efficiency
of the method. Our method is conservative and may label a very small percentage
of good chips as faulty. However, this fault detection error can be made
arbitrarily small. We also proposed a simple digital hardware structure for the
transmitter and receiver ends of the link under test to detect delay faults. It
is possible to extend our method to combine it with functional testing of the
link and adapt it for on-line testing.
References:
1. R.Ubar, A.Jutman, Z.Peng. Improving the Efficiency of
Timing Simulation in Digital Circuits by Using Structurally Synthesized BDDs.
IEEE Norchip conference, Turku, November 7-8, 2000, pp.254-261.
2. A.Jutman, R.Ubar, Z.Peng. Algorithms for Speeding-Up
Timing Simulation of Digital Circuits. DATE, Munich, March 13-16, 2001,
pp.460-465.
3. A.Jutman, R.Ubar. Application of Structurally
Synthesized Binary Decision Diagrams for Timing Simulation of Digital Circuits.
Proceedings of the Estonian Academy of Sciences, No 7/4, 2001, pp.269-288.
4. R.Ubar, A.Jutman. BEC: Increasing the Speed of Delay Simulation in Digital Circuits.
7th Baltic Electronics Conference, Tallinn, October 8-11, 2000, pp.31-34.
5. R.Ubar, A.Jutman, Z.Peng. Improving the Efficiency of
Timing Simulation in Digital Circuits by Using Structurally Synthesized BDDs.
IEEE Norchip conference, Turku, November 7-8, 2000, pp.254-261.
6. T.Bengtsson, A.Jutman, S.Kumar, R.Ubar. Delay Testing
of Asynchronous NOC Interconnects. 12th International Conference Mixed Design
of Integrated Circuits and Systems Kraków, 22-25 June 2005, pp.419-424.
7. T.Bengtsson, A.Jutman, S.Kumar, Z.Peng, R.Ubar.
Off-line Testing of Delay Faults in NoC Interconnects. Proceedings of the 9th
IEEE EUROMICRO Conference on Digital Systems Design DSD2006, Katvat, Croatia,
2006, pp.677-680.
As the complexity of digital systems continues to
increase, the traditional low level diagnostic analysis methods have become
obsolete. Other approaches based mainly on higher level functional and
behavioral methods are gaining more popularity. However, the trend towards
higher level modeling moves us even more away from the real life of defects
and, hence, from accuracy of testing. To handle adequately defects in
deep-submicron technologies, new fault models and defect-oriented test methods
should be used. On the other hand, the defect-orientation is increasing even
more the complexity. To get out from the deadlock, the two opposite trends –
high-level modeling and defect-orientation – should be combined into
hierarchical approaches. The advantage of hierarchical approaches compared to
high-level functional modeling lies in the possibility of constructing test
plans on higher levels, and modeling faults on more detailed lower levels.
A new approach to defect-oriented fault simulation
has been developed, based on mapping the physical defects into higher level
constraints [1,2,4]. Based on the defect-oriented simulation tool, a random
defect-oriented test generator was developed [3,5] which allowed to improve the
test quality compared to the classical stuck-et fault approaches.
A method was developed for deterministic test pattern
generation using a uniform functional fault model for combinational circuits
[6]. The fault model allows to represent arbitrary physical defects in
components and defects in the communication network of components by the same
technique. The possibility of detecting the bridging faults that via feedback
transform combinational circuit into sequential one is also created. A method
is proposed which allows to find the types of faults that may occur in a real
circuit, to determine their probabilities and to use this information to guide
the test generation process. The method was implemented as the defect-oriented
deterministic test generation tool DOT [7]. The first time, a method and tool
is available for proving redundancy of physical defects, which allows to
evaluate the quality of tests more adequately compared to existing tools. The
new functional fault model used in the tool creates a simple conception and
basis for hierarchical defect oriented test, and couold be generalized also for
using at higher levels.
Shorts inside the routing network can show sequential
behaviour. The proposed test pattern generator DOT is also able to find tests
for such kind of defects. As the effort to test sequential defects can vary
from short to short, a new testability analysis was developed [8]. Based on
this analysis a redesign of the circuit layout is proposed. This “layout for
testability” approach is therefore a defect oriented equivalent for “design for
testability” methods. In [9] it was shown that nearly all bridging faults can
be tested by a simple and robust one-pattern logic test [10].
References:
1. M.Blyzniuk, FT.Cibakova, E.Gramatova, W.Kuzmicz,
M.Lobur, W.Pleskacz, J.Raik, R.Ubar. Hierarchical Defect-Oriented Fault
Simulation for Digital Circuits. IEEE European Test Workshop, Cascais,
Portugal, Mai 23-26, 2000, pp.151-156.
2. R.Ubar, W.Kuzmicz, W.Pleskacz, J.Raik.
Defect-Oriented Fault Simulation and Test Generation in Digital Circuits. 2nd
Int. Symp. on Quality of Electronic Design, San Jose, California, March 26-28,
2001, pp.365-371.
3. T.Cibakova, M.Fischerova, E.Gramatova, W.Kuzmicz,
W.Pleskacz, J.Raik, R.Ubar. Defect-Oriented Test Generation Using Probabilistic
Estimation. MIXDES’01, Zakopane, Poland, June 21-23, 2001, pp.131-136.
4. W.Kuzmicz, W.Pleskacz, J.Raik, R.Ubar. Module Level
Defect Simulation in Digital Circuits. Proceedings of the Estonian Academy of
Sciences, No 7/4, 2001, pp.253-268.
5. T.Cibáková, M.Fischerová, E.Gramatová, W.Kuzmicz,
W.Pleskacz, J.Raik, R.Ubar. Hierarchical Test Generation for Combinational
Circuits with Real Defects Coverage. Pergamon Press. Journal of
Microelectronics Reliability, Vol. 42, 2002, pp.1141-1149.
6. J.Raik, R.Ubar, J.Sudbrock, W.Kuzmicz, W.Pleskacz.
Deterministic Defect-Oriented Test Generation for Digital Circuits. 6th IEEE
Latin-American Test Workshop – LATW2005, March 30 – April 2, 2005, Salvador,
Bahia, Brazil, pp.325-330.
7. J.Raik, R.Ubar, J.Sudbrock, W.Kuzmicz, W.Pleskacz.
DOT: New Deterministic Defect-Oriented ATPG Tool. Proc. of 10th IEEE European
Test Symposium, May 22-25, 2005, Tallinn, pp.96-101.
8. J.Sudbrock, J.Raik, R.Ubar, W.Kuzmicz, W.Pleskacz.
Defect-Oriented Test- and Layout-Generation for Standard-Cell ASIC Designs. 8th
Euromicro conference on Digital Systems Design DSD2005. Porto, Aug.30 – Sept.
3, 2005, pp.79-82.
9. M.Jenihhin, J.Raik, R.Ubar, W.A.Pleskacz, M.Rakowski.
Layout to Logic Defect Analysis for Hierarchical Test Generation. The 10th IEEE
Workshop on Design and Diagnostics of Electronic Circuits and Systems - DDECS
2007. Krakow, Poland, April 11-13, 2007, pp.35-40.
A general approach is presented for calculation
controllabilities and observabilities of signals at gate- and register transfer
levels [1,2]. The methods and algorithms are based on using multi-level
decision diagrams. On the gate-level the circuit is represented hierarchically
as a network of macros (subcircuits) where to each macro a structurally
synthesized BDD (SSBDD) corresponds. Differently to traditional testability calculation
approaches, no libraries of controllability and observability models
(calculation rules) for network components (macros) are needed. A generic
procedure is given to calculate testability values for arbitrary macro.
Heuristic and probabilistic measures are calculated by uniform path tracing
procedures on SSBDDs. The procedure takes into account the correlation of
probabilities, and increases the accuracy of calculating signal probabilities
compared to the gate-level methods.
The proposed method was generalized for calculating
testability measures on the register transfer level [3,6]. Previously, these
measures have been successfully used in high-level synthesis, test synthesis
and sequential circuits test generation at the gate-level. However, solutions
implementing such measures in RTL test generation were missing. A method was
proposed and implemented for testability guided RT-level test generation [4,7].
Experiments were carried out in order to evaluate to what extent testability
analysis influences test generation at the RT-level. The experiments showed
remarkable improvement in test quality.
A new low area overhead Designfor-Testability (DfT)
technique for Built-In Self-Test (BIST) of sequential circuits was developed in
[5]. The technique is based on making the status signals entering the control
part controllable during the test mode. This requires a simple controller to
manipulate these signals in order to force the device under test to traverse
all the branches in the FSM state transition graph. Experimental results showed
that the number of signals to be controlled (usually 1-2 bits), and thus the
extra silicon area, is very low. In addition, the experiments showed that the
optimal BIST solution for a design is highly dependent on its testability
characteristics. New BIST related DfT methods were proposed also in [8.]
References:
1. R.Ubar, J.Heinlaid, L.Raun. Improved Testability
Calculation for Digital Circuits. 19th IEEE Conference NORCHIP’2001, Stockholm,
Sweden, pp.264-270.
2. R.Ubar. Testability Calculation for Digital Circuits
with Decision Diagrams. 3rd IEEE Latin-American Test Workshop – LATW’2002,
Montevideo, Uruguay, February 10-13, 2002, pp.137-143.
3. T.Nõmmeots, J.Raik, R.Ubar. Testability Analysis for
Efficient Register-Transfer Level Test Generation. Proc. of the 9th Int. Conf.
MIXDES 2002, Wroclaw, June 20-22, 2002, pp.555-558.
4. J.Raik, T.Nõmmeots, R.Ubar. New Method of Testability
Calculation to Guide RT-Level Test Generation. Proc. of 4th IEEE Latin-American
Test Workshop – LATW2003, Natal, Brazil, February 16-19, 2003, pp.46-51.
5. J.Raik, R.Raidma, R.Ubar. Explorations in Low Area
Overhead DfT Techniques for Sequential BIST. 21st IEEE Conference NORCHIP’2003,
Riga, Latvia, November 10-11, 2003, pp.220-223.
6. J.Raik, V.Govind, R.Ubar. RT-Level Test Point
Insertion for Sequential Circuits. Proc. of the IEEE 1st International Workshop on Testability
Assessment – IWoTA-2004, Rennes, Nov.2, 2004, pp.34-40. IEEE Catalog Number
04EX983, ISBN 0-7803-8851-8.
7. J.Raik, T.Nõmmeots, R.Ubar. A New Testability
Calculation Method to Guide RTL Test Generation. Journal of Electronic Testing:
Theory and Applications – JETTA. Springer Science + Business Media, Inc. 21,
pp.73-84, 2005.
8. G.Jervan, R.Ubar, Z.Peng, P.Eles. An Approach to
System Level DFT. In “System-level Test and Validation of Hardware/Software
Systems” by M.Sonza Reorda, Z.Peng, M.Violante. Springer Series in Advanced
Microelectronics, Vol.17, 2005, pp. 91-118.
Due to the requirements for the Automatic Test Equipment
(ATE) speed and memory, the ATE-based test solution may not always be
affordable in terms of cost and accuracy. Therefore, in order to apply at-speed
tests and to keep the test costs under control, on-chip, Built-In Self-Test
(BIST) solutions are becoming a mainstream technology for testing complex
electronic systems.
Different test scenarios are possible, while using
BIST. Sometimes the embedded cores may be tested using only internally
generated pseudorandom test patterns. Due to several reasons, like very long
test sequences, and random pattern resistant faults, this approach may not
always be efficient.
One solution to this problem is to complement
pseudorandom test patterns with deterministic test patterns, applied from the
on-chip memory or, in special situations, from the ATE. This approach is
usually referred to as hybrid BIST. One of the important parameters influencing
the efficiency of a hybrid BIST approach is the ratio of pseudorandom and
deterministic test patterns in the final test set. As the amount of resources
on the chip is limited, the final test set has to be designed in such a way
that the deterministic patterns fit into the on-chip memory. At the same time
the testing time must be minimized in order to reduce testing cost and
time-to-market.
In self-test, a close cooperation between TTU and
Linköping University, Sweden has given several original results in the area of
optimizing hybrid BIST. A novel method for fast cost estimation for variations
of test processes with complex structure was proposed [1,2]. Based of the fast
cost estimation method, two algorithms were proposed and compared to find the
optimal balance between pseudorandom and stored test patterns to perform self
test with minimum time and memory, without losing test quality [3,4]. To speed
up the optimization procedure, a Tabu search based method was proposed for
finding the global cost minimum without calculating the full cost curve. The
proposed algorithms may be used
for both software and harware implementations of the hybrid BIST. The
new methods were then generalized for multi-core systems with STUMPS
architecture [5,6,13,14], and extended for optimizing parallel testing in a
test pattern broadcasting mode [7]. A technique was developed to find the
optimum hybrid BIST solution so that the total energy is minimized and the
memory requirements for the deterministic test set are met without sacrificing
test quality [10,11]. An efficient iterative algorithm was proposed based on a
method for fast estimation of candidate solutions that enables considerable
reduction of the computation time.
A conception of hybrid functional BIST to combine the
functional routines carried out in digital systems with deterministic test
patterns was developed [8]. In the first test phase only the functional
resources of a system are used for testing purposes. A response compressor like
signature analyzer is used to monitor the process. To quarantee a high fault
coverage, the second phase of the test is used as well, which consists additional
test patterns for testing random-pattern-resistant faults. A method is proposed
to find the tradeoff between the functional test and deterministic test parts
is presented [9].
Two methods were developed for optimization of hybrid
BIST test sessions based on reseeding. The first one is based on a genetic
algorithm {[12] and the second one uses greedy aapproaach [15].
References:
1. G.Jervan, Z.Peng, R.Ubar. Test Cost Minimization for
Hybrid BIST. IEEE Int. Symp. on Defect and Fault Tolerance in VLSI Systems.
Tokio, October 25-28, 2000, pp.283-291.
2. R.Ubar, G.Jervan, Z.Peng, E.Orasson, R.Raidma. Fast
Test Cost Calculation for Hybrid BIST in Digital Systems. Proc. of EUROMICRO
Symposium on Digital Systems Design, Warsaw, September 4-6, 2001, pp.318-325.
3. H.Kruus, R.Ubar, G.Jervan, Z.Peng. Using Tabu Search
Method for Optimizing the Cost of Hybrid BIST. XVI Conference on Design of
Circuits and Integrated Systems, Porto, Portugal, Nov. 20-23, 2001, pp.445-450.
4. G.Jervan, H.Kruus, Z.Peng, R.Ubar. About Cost
Optimization of Hybrid BIST in Digital Systems. 3rd IEEE Int. Symp. on Quality
of Electronic Design, San Jose, California, March 18-20, 2002, pp.273-279.
5. G.Jervan, P.Eles, Z.Peng, R.Ubar, M.Jenihhin. Hybrid
BIST Time Minimization for Core-Based Systems with STUMPS Architecture. 18th
Int. Symposium on Defect and Fault Tolerance in VLSI Systems. Cambridge, MA,
USA, November 3-5, 2003.
6. G.Jervan, P.Eles, Z.Peng, R.Ubar, M.Jenihhin. Test
Time Minimization for Hybrid BIST of Core-Based Systems. Asian Test Symposium
2003, Xi’an, China, November 17-19, 2003, pp. 318-323.
7. R.Ubar, M.Jenihhin, G.Jervan, Z.Peng. Hybrid BIST
Optimization for Core-Based Systems with Test Pattern Broadcasting. 2nd IEEE
Int. Workshop on Electronic Design, Test and Applications – DELTA’04, Perth, Australia,
28-30 January 2004, pp.3-8.
8. R.Ubar, N.Mazurova, J.Smahtina, E.Orasson, J.Raik.
HyFBIST: Hybrid Functional Built-In Self-Test in Microprogrammed Data-Paths of
Digital Systems. Int. Conference MIXDES, Szczecin, June 24-26, 2004,
pp.497-502.
9. N.Mazurova, J.Smahtina, R.Ubar. Hybrid Functional
BIST for Digital Systems. Proc. of the 9th Biennial Baltic Electronics
Conference, Oct. 3-6, 2004, Tallinn, pp.205-208.
10. R.Ubar, T.Shchenova, G.Jervan, Z.Peng. Energy
Minimization for Hybrid BIST in a System-on-Chip Test Environment. Proc. of
10th IEEE European Test Symposium, May 22-25, 2005, Tallinn, pp.2-7.
11. G.Jervan, Z.Peng, T.Shchenova, R.Ubar. A Hybrid BIST
Energy Minimization Technique for SoC Testing. IEE Proceedings on Computers
& Digital Techniques, July 2006, Vol. 153, Issue 4, pp.208-216.
12. J.Aleksejev, A.Jutman, R.Ubar. LFSR Polynomial and
Seed Selection Using Genetic Algorithm. Baltic Electronics Conference.
Laulasmaa, Oct. 2006, pp.179-182.
13. G.Jervan, R.Ubar, Z.Peng. Hybrid BIST Methodology for
Testing Core-Based Systems. Proc. of the Estonian Academy of Sciences.
Engineering, 12 (2/3), 2006, pp.300-322
14. G.Jervan, P.Eles, Z.Peng, R.Ubar, M.Jenihhin. Test
Time Minimization for Hybrid BIST of Core-Based Systems. J. of Computer Science
and Technology. Nov. 2006, Vol. 21, No. 6, pp. 907-912.
15. G.Jervan, H.Kruus, E.Orasson, R.Ubar. Hybrid BIST
Optimization Using Reseeding and Test Set Compaction. Proc. of 10th IEEE
EUROMICRO Conference on Digital System Design - DSD 2007, Lübeck, Germany,
August 27 - 31, 2007, pp.596-603.
Three directions in this field has been followed:
design error diagnosis, NoC diagnosis and embedded diagnosis based on BIST
environments. A new approach was developed for removing design errors from
digital circuits, which does not use any error model [1]. Combinational
circuits or circuits with scan-paths are here considered. Based on a diagnostic
pre-analysis of the circuit, a subcircuit suspected to be erroneous is
extracted and the rectified. Opposite to the known works, re-synthesis of the
subcircuit needs not be applied to the whole function of the erroneous internal
signal in terms of primary inputs, it may stop at arbitrary nodes inside the
circuit. More methods are presented in the verificaation section of this page.
A novel concept of diagnosing faulty links in NoC
designs was proposed in [2,3]. The method is based on functional fault models
and it implements packet address driven test configurations. The main novelty
is to extend the use of test configurations for diagnosis purposes and to
propose a method for locating faults in the NoC interconnection infrastructure.
Additionally, a new concept of functional switch faults, called link faults, is
introduced. The approach is well scalable (complexity is square root of the number
of switches) and it is capable of unambigously pinpointing the faulty links
inside the switching network.
Instead of the known approach based on a simple
bisection of patterns in pseudorandom test sequences, we proposed a novel bisection
procedure where the diagnostic weight of test patterns is taken into account
[4,5]. Another novelty is the sequential nature of the procedure which allows
pruning the search space. Opposite to the classical approach which targets all
failing patterns, in the proposed method not all of such patterns are needed to
be fixed for diagnosis. This allows to trade-off the speed of diagnosis with
diagnostic resolution. To improve the diagnostic resolution the use of multiple
signature analyzers was proposed [6]. A method was developed to partition a
single signature analyzer into a set of multiple independent analyzers, and the
algorithms were given to synthesize an optimal interface between the outputs of
the circuit under test and the analyzers [7,8]. The proposed method was
compared with three known fault diagnosis methods: classical Binary Search
based on patterns bisection, Doubling and Jumping. Experimental results
demonstrated the advantages of the proposed method compared to the previous
ones.
References:
1. R.Ubar. Design Error Diagnosis in Scan-Path Designs.
2nd Latin-American Test Workshop. Cancun, Mexico, February 11-14, 2001, pp.
162-168.
2. J.Raik, V.Govind, R.Ubar. An External Diagnosis
method for Network-on-a-Chip. IEEE/ACM Design Automation and Test in Europe
Workshop on Diagnostic Services in Networks-on-Chips. April 16-20, 2006, Nice,
France.
3. J.Raik, R.Ubar, V.Govind. Test Configurations for
Diagnosing Faulty Links in NoC Switches. 12th IEEE European Test Symposium –
ETS 2007, Freiburg, Germany, May 20-24, 2007, pp.29-34.
4. R.Ubar, S.Kostin, J.Raik. Fault Diagnosis in the BIST
Environment Based on Bisection of Detected Faults. 8th IEEE Latin-American Test
Workshop - LATW2007, Cuzco, Peru, March 11-14, 2007, pp.1-6.
5. R.Ubar, S.Kostin, J.Raik, T.Evartson, H.Lensen. Fault
Diagnosis in Integrated Circuits with BIST. Proc. of 10th IEEE EUROMICRO
Conference on Digital System Design - DSD 2007, Lübeck, Germany, August 27 -
31, 2007, pp.604-610.
6. R.Ubar, S.Kostin, J.Raik, M.Kruus. Experimental
Comparison of Different Diagnosis Algorithms in the BIST Environment. IASTED
Conference on Applied Simulation and Modelling - ASM 2007, ACTA Press, August
29-31, 2007, Palma de Mallorca, Spain, pp.271-276.
7. R.Ubar, S.Kostin, J.Raik. Built-In Self-Diagnosis
with Multiple Signature Analyzers in Digital Systems. 9th IEEE Latin-American
Test Workshop – LATW 2008, Puebla, Mexico, Feb. 17-20, 2008. Submitted.
8. R.Ubar, S.Kostin, J.Raik. Embedded Fault Diagnosis in
Digital Systems with BIST. Journal of Microprocessors and Microsystems.
Submitted.
Rapid advances in deep submicron and
nanotechnologies, as well as in design automation are enabling engineers to
design more complex integrated circuits (IC) and driving them toward new design
paradigms like Systems-on-Chip (SoC), and Networks-on-Chip (NoC) [1,2]. NoC has
become a state-of-the-art interconnect solution between cores in SoC designs.
We have developed a novel conception for autonomous at-speed testing of NoC
interconnect. It is based on recently proposed very efficient design of test
pattern generation and response analysis hardware, which allows detection and
diagnosis of both static and dynamic faults upon interconnects between chips in
a multi-chip environment. In [3,4] we describe a new testing paradigm adapted
to synchronous NoC and present its general structure. It is shown that this
paradigm brings a high level of universality, scalability, and configuration
independence into at-speed testing and diagnosis of NoC interconnect.
Small dimensions and high frequencies of chips of
today make crosstalk related malfunctioning more important to consider than
ever before. This is a reason why at-speed testing of cross talk induced logic
and delay faults in core based SoCs, is becoming very important. Closely packed
buses interconnecting cores are generally laid out on many interconnect layers
to minimize area and delay. Aggressor-victim model is often used to represent
the effect of crosstalk due to influence of one wire on the other. We have
proposed an efficient method and corresponding BIST hardware for at-speed
testing of such faults [5]. The proposed BIST hardware is programmable and can
provide the trade-off between test speed and test quality. In [6] we propose a
methodology for at-speed testing of glitch faults in links connecting two
distinct clock domains in a SoC or a NoC system. The basic idea is to try to
create conditions using maximum number of aggressors to induce a glitch in the
link to be tested for faults and use a latch to record this glitch.
The previous works on testing NoCs have been mainly
based on general purpose Design-for-Testability (DfT) approaches and there is a
lack of test algorithms dedicated to on-chip networks. We developed a generic
parametrizable VHDL description of a deflecting NoC switch, and synthesized for
research purposes a benchmark family of 8 switches representing different
possible architecture configurations [6]. We created also a scalable testbench
providing high-fault coverage test patterns for network implementations based
on this switch. A well-scalable external test method, where insertion of
wrappers and scan paths will not be required was developed [7]. The method is
based on functional fault models, which target single stuck-at faults in the
network switches. Furthermore, 100 per cent of delay faults, opens and shorts
between adjacent interconnection lines are additionally covered by the method.
The approach allows to reach higher fault coverages in comparison to the recent
DfT based solutions.
References:
1. T.Hollstein, Z.Peng, R.Ubar, M.Glesner. Challenges
for Future System-on-Chip Design. Proceedings of European Conference on Circuit
Theory and Design. Part III. Espoo, Finland, August 28-31, 2001, pp.173-176.
2. R.Ubar, J.Raik. Testing Strategies for Networks on
Chip. In “Networks on Chip” by A.Jantsch, H.Tenhunen. Kluwer Academic
Publishers, 2003, pp. 131-152.
3. A.Jutman, R.Ubar, J.Raik. Generic Interconnect BIST
for Network-on-Chip. Proc. of IEEE Design and Diagnostics of Electronic
Circuits and Systems Workshop. Sopron, April 13-16, 2005, pp.224-227.
4. A.Jutman, R.Ubar, J.Raik. New Built-In Self-Test
Scheme for SoC Interconnect. 9th World Multi-Conference on Systemics,
Cybernetics and Informatics. July 10-13, 2005, Orlando, Florida, USA, vol.4,
pp.19-24.
5. T.Bengtsson, A.Jutman, R.Ubar, S.Kumar. A method for
crosstalk fault detection in on-chip Buses. IEEE NORCHIP Conference, Oulu,
Finland, Nov. 21-22, 2005, pp.285-288.
6. V.Govind, J.Raik, R.Ubar. A Generic Synthesizable NoC
Switch with Scalable Testbench. Baltic Electronics Conference. Laulasmaa, Oct.
2006, pp.91-94.
7. V.Govind, J.Raik, R.Ubar. An External Test Approach
for Network-on-Chip Switches. IEEE Asian test Symposium. 2006, Fukuoka, Japan,
pp.437-442.
8. T.Bengtsson, S.Kumar, A.Jutman, R.Ubar. Off-line
Testing of Crosstalk Induced Glitch Faults in NoC Interconnects. 24th IEEE
Norchip Conference, Linköping, Nov. 20-21, 2006, pp.221-226.
9. G.Jervan, T.Shchenova, R.Ubar (2006). Hybrid BIST
Scheduling for NoC-Based SoCs. 24th IEEE Norchip Conference, Linköping, Nov.
20-21, 2006, pp.141-144.
Dependable systems are designed with fault tolerance
features to first, detect errors and then to mask or recover from the effects
of those errors. Thus, testing of these features is extremely important in understanding
how dependable the systems are with the incorporated fault tolerance mechanisms
and in gaining insight into the success of error detection and recovery. Fault
injection is a means to effectively test and stress the error handling and
fault tolerance mechanisms, so that the system behavior can be studied prior to
their actual deployment. However, there exists a problem of selecting faults to
be injected. Erroneous responses in a system do not necessarily lead to a
failure at the application level, even when the discrepancy with the nominal
behavior has a long duration. Fault analysis in the complete system is
therefore required to discriminate real failure conditions from non-critical
errors. Such an analysis is very difficult to carry out on the execution-based
models using languages like VHDL, Verilog, System C.
We have developed a new hierarchical multi-level
technique for malicious fault list generation for evaluating the fault
tolerance [1,2]. For the description of the system three levels are exploited:
behavioral, functional signal path and structural gate-network levels, whereas
at each level the model of decision diagrams and uniform fault analysis
procedures are used. Malicious faults are found by top-down technique, keeping
the complexity of candidate fault sets at each level as low as possible.
References:
1. R.Ubar, G.Jervan, J.Raik, M.Jenihhin, P.Ellervee.
Dependability Evaluation in Fault-Tolerant Systems with High-Level Decision
Diagrams. Proceedings of the 52. International Scientific Colloquium, Vol. II,
Ilmenau, Sept. 10-13, 2007, pp.147-152.
2. R.Ubar, S.Devadze, M.Jenihhin, J.Raik, G.Jervan,
P.Ellervee. Hierarchical Calculation of Malicious Faults for Evaluating the
Fault-Tolerance. 4th IEEE International Symposium on Electronic Design, Test
& Applications – DELTA 2008, Hong Kong, January 23-25, 2008.
Reconfigurable Hardware Applications
Fault simulation is the most often used way of
digital analysis and there exist many techniques to speed up simulation.
Efficient fault simulation algorithms for combinational circuits are known
already for decades. However, it is the large sequential designs whose fault
grading run times could be measured in years that drive the need for faster
implementation, e.g. by hardware emulation. At the same time, reconfigurable
hardware, e.g., FPGAs, has been found useful as a system-modeling environment.
The availability of large devices allows implementing not only the circuit
under test with fault models but also the whole test bench on a single reconfigurable
device.
The papers [1-5] describe our work on developing a
very fast approach and implementation to emulate fault simulation of sequential circuits on FPGAs. To study
the possibility of replacing fault simulation with emulation, we first had to
solve some essential issues how to represent the faults in a synthesizable
circuit, how to feed the test vectors into the circuit, and how to read and/or
analyze the results of emulation. Then we created the experimental environment
and performed experiments with some benchmark circuits. The experiments showed
that for circuits and/or applications that require large numbers of test
vectors, it is beneficial to replace simulation with emulation. Compared to SW
based solutions the speed of fault simulation increased more than 200 times.
More work is needed to integrate the hardware part
with the software part of the test generation environment. In addition to
merely increasing the speed of fault simulation, the idea proposed in this
paper can be used for selecting optimal Built-In Self-Test (BIST) structures.
References:
1. J.Raik, P.Ellervee, V.Tihhomirov, R.Ubar. Fast Fault
Emulation for Synchronous Sequential Circuits. 2nd East-West Design & Test
Workshop EWDTW-2004, Alushta 23-26, 2004, pp.35-40.
2. P.Ellervee, J.Raik, V.Tihhomirov, R.Ubar. FPGA Based
Fault Emulation of Synchronous Sequential Circuits. Proc. of the 22nd IEEE
Norchip Conference, Oslo, November 8-9, 2004, pp.59-62.
3. J.Raik, P.Ellervee, V.Tihhomirov, R.Ubar. Improved
Fault Emulation for Synchronous Sequential Circuits. 8th Euromicro conference
on Digital Systems Design DSD2005. Porto, Aug.30 – Sept. 3, 2005, pp.72-78.
4. P.Ellervee, J.Raik, K.Tammemäe, R.Ubar. Environment
for FPGA Based Fault Emulation. Proc. of the Estonian Academy of Sciences.
Engineering 12 (2/3), pp.323-335.
5. P.Ellervee, J.Raik, R.Ubar, K.Tammemäe. FPGA-Based
Fault Emulation of Synchronous Sequential Circuits. IEE Proceedings on
Computers & Digital Techniques. Vol.1, Issue 2, pp.70-76, March 2007.
Collaborative Internet-Based Design and Test
In cooperation with Fraunhofer Institute of
Integrated Circuits in Germany we have developed an environment for an
Internet-based co-operation in the field of design and test of digital systems
as the demonstrator of the EU project VILAB [1-6]. A VLSI design flow is
combined with an Internet-based hierarchical automated test pattern generation
(ATPG). A novel hierarchical ATPG driven by testability measures was included
into the design and test flow. Both, the register-transfer (RT) and the gate
level descriptions are used, and decision diagrams are exploited as a uniform
model for describing systems at both levels, for calculating testability
measures and for test generation. The ATPG and testability analyzer can be run
at geographically different places (at partners of the VILAB project) under the
virtual environment MOSCITO developed at Fraunhofer Institute. The interfaces
between the integrated tools and also the commercial design tools were
developed and implemented. The functionality of the integrated design and test
system was verified in several co-operative experiments over Internet by
partners in different geographical sites. The experimental results have shown
the advantages of using structural tests generated by ATPG compared to using
functional test sequences created by designers.
References:
1. A.Schneider, E.Ivask, P.Mikloš, J.Raik, K.H.Diener,
R.Ubar, T.Cibáková, E.Gramatová. Internet-based Collaborative Test Generation
with MOSCITO. IEEE Proc. of Design
Automation and Test in Europe – DATE’02. Paris, March 4-8, 2002, pp. 221-226.
2. A.Schneider, K.-H.Diener, E.Ivask, R.Ubar,
E.Gramatova, T.Hollstein, W.Pleskacz, W.Kuzmicz, Z.Peng. Integrated Design and
Test Generation Under Internet Based Environment MOSCITO. EUROMICRO Conference,
September 3-6, 2002, pp. 187-194.
3. A.Schneider, K.-H.Diener, E.Ivask, R.Ubar,
E.Gramatova, M.Fisherova, W.Pleskacz, W.Kuzmicz. Defect-Oriented Test
Generation and Fault Simulation in the Environment of MOSCITO. Proceedings,
BEC-2002, Tallinn, October 6-9, 2002, pp.303-306.
4. A.Schneider, K.-H.Diener, J.Raik, R.Ubar, G.Jervan,
Z.Peng, T.Hollstein, M.Glesner. High-Level Synthesis and Test in the
MOSCITO-Based Virtual Laboratory. Proc. BEC-2002, Tallinn, October 6-9, 2002,
pp.287-290.
5. A.Schneider, K.-H.Diener, G.Elst, E.Ivask, J.Raik,
R.Ubar. Internet-Based Testability-Driven Test Generation in the Virtual
Environment MOSCITO. Proc. IFIP Conference on IP Based SOC Design, Grenoble,
France, October 30-31, 2002, pp.357-362.
6. E. Ivask, J. Raik, R. Ubar, A. Schneider. WEB-Based
Environment: Remote Use of Digital Electronics Test Tools. In “Virtual
Enterprises and Collaborative Networks”, Kluwer Academic Publishers, 2004, pp.
435-442.
To support teaching and research oriented laboratory training
we have created a homogeneous e-learning environment for studying the test and
diagnostics of digital systems. It consists of a set of tools (“interactive
modules”) targeted to e-learning for teaching logic level test generation and
fault diagnosis in digital circuits [1,3], higher (register transfer) level
functional test programming and analysis [2,10], decign for testability and
built-in self-testing conceptions [2,9,11], boundary scan standard and board
testing issues [4,6,7], as well as physical defect analysis in integrated
circuits and defect-oriented test [12]. The tools are available and open for
use over Internet [8].
The tools support different university courses on
computer engineering, switching and automata theories, digital electronics and
design for testability to learn by hands-on excercises test and fault diagnosis
related topics. A big reservoir of examples and the possibility to set up
interesting engineering problems like how to generate test patterns for a
digital circuit, or how to locate a faulty gate in the circuit makes the
learning process more interesting and allows learning at an individual depth
and duration. The interactive modules are focused on easy action and reaction,
learning by doing, a game-like use, and fostering students in critical
thinking, problem solving skills and creativity.
References:
1. R.Ubar, H.-D.Wuttke. The DILDIS-Project – Using
Applets for More Demonstrative Lectures in Digital Systems Design and Test.
Proceedings of the 31st ASEE/IEEE Frontiers in Education Conference, FIE’2001,
Oct. 10-13, 2001, Reno, NV, USA, pp.SIE-2-7.
2. S.Devadze, A.Jutman, A.Sudnitson, R.Ubar,
H.-D.Wuttke. Teaching Digital RT-Level Self-Test Using a Java Applet. 20th IEEE
Conference NORCHIP’2002, Copenhagen, Denmark, November 11-12, 2002, pp.322-328.
3. R.Ubar, E.Orasson. E-Learning tool and Exercises for
Teaching Digital Test. Proc.of 2nd IEEE Conf. on Signals, Systems, Decision and
Information Technology. Sousse, Tunisia, March 26-28, 2003, CIT-6, pp.1-6.
4. A.Jutman, A.Sudnitsõn, R.Ubar. Web-Based Applet for
Teaching Boundary Scan standard IEEE 1149.1. Proc. of the 10th Int. Conf.
MIXDES 2003, Lodz, June 26-28, 2003, pp.584-589 (Best Paper Award).
5. V.Vislogubov, A.Jutman, H.Kruus, E.Orasson, J.Raik,
R.Ubar. Diagnostic Software with WEB Interface for Teaching Purposes. Proc. of
the 9th Biennial Baltic Electronics Conference, Oct. 3-6, 2004, Tallinn,
pp.255-258.
6. A.Jutman, R.Ubar, V.Rosin. A Software System fror
IEEE 1149.1 Boundary Scan Design, Simulation and Demonstration. IEEE European Board
Test Workshop, Tallinn, May 25-26, 2005, http://www.dft.co.uk/EBTW2005/PAPERS/.
7. A.Jutman, V.Rosin, A.Sudnitson, R.Ubar, H.-D.Wuttke A
System for Teaching Basic and Advanced Topics of IEEE 1149.1 Boundary Scan
Standard. EAEEIE, June 2005. Best Paper Award.
8. A.Jutman, J.Raik, R.Ubar, V.Vislogubov. An
Educational Environment for Digital Testing: Hardware, Tools, and Web-based
Runtime Platform. 8th Euromicro conference on Digital Systems Design DSD2005.
Porto, Aug.30 – Sept. 3, 2005, pp.412-419.
9. A.Jutman, A.Tsertov, R.Ubar. A Tool for Advanced
learning of LFSR-based Testing Principles. Baltic Electronics Conference.
Laulasmaa, Oct. 2006, pp.175-178.
10. R.Ubar, A.Jutman, M.Kruus, E.Orasson, S.Devadze,
H.-D.Wuttke. Learning Digital Test and Diagnostics via Internet. International
Journal of Emerging Technologies in Learning. International Journal of Online
Engineering, Vol.3, No.1, pp.1-9, 2007.
11. A.Jutman, A.Tsertov, A.Tsepurov, I.Aleksejev, R.Ubar,
H.-D.Wuttke, “BIST Analyzer: a Training Platform for SoC Testing” in Proc. of
Frontiers in Education Conference (FIE’07), Milwaukee, Wisconsin, USA, October
10-13, 2007.
12. W.Pleskacz, T.Borejko, A.Walkanis, V.Stopjakova,
A.Jutman, R.Ubar. CMOS Defects Analysis using DefSim Measurement Environment.
Informal Digest of Papers of the 11th IEEE European Test Symposium,
Southampton, UK, May 22-25, 2006, pp.241-246
Our research group has been very active in
international organizational work, we belong to the steering or program
committees of about 25-30 conferences ioncluding DATE,VTS, ETS, ISQED, EDCC,
EUROMICRO, DDECS a.o. We have been the main organizer of more than 10
international conferences and workshops, such as IEEE European Test Symposium
(ETS) [4], European Board Test Workshop [4], IEEE East-West Design & Test
Symposium (EWDTS) [1,3], Norchip Conference, and others. Belonging to the
committee of EAEEIE we took part in the action of the EU project THEIERE to
carry out a study about curricula
available in Europe in electrical and information engineering and reflections
on the Bologna-RMD process [2]. Overviews about the reserch activities, results
and successes are presented in [5-7].
References:
1. V.Hahanov, R.Ubar. First East-West Design and Test
Conference. IEEE Design & Test, Nov.-Dec 2003, pp.103.
2. R.Ubar, E.Rüstern, M.Kruus. EE: Eesti (Estonia) in
“Towards the Harmonization of Electrical and Information Engineering Education
in Europe”, Lisboa-Nancy 2003, Ed. EAEEIE, 2003, pp.67-74.
3. V.Hahanov, R.Ubar. 2nd IEEE EastWest Design &
Test Workshop. IEEE Journal of Design & Test of Computers, Nov.-Dec 2004,
pp.594.
4. R.Ubar, P.Prinetto, J.Raik. 10th IEEE European Test
Symposion. IEEE Journal of Design & Test of Computers, Sept.-Oct, 2005,
pp.480-481.
5. M.Kruus, R.Ubar. Success Story of the Computer Engineering
Department at the Tallinn University of Technology in EU Projects. The
Parliament Magazine. No. 234, 13. Nov. 2006, pp.33.
6. R.Ubar, J.Raik, A.Jutman, P.Ellervee. Digital
Electronics Design and Test at Computer Engineering Department of Tallinn University
of Technology. The House Magazine. The Parlamentary Weekly, No 1198, Vol.32,
Dec.11, 2006, pp.42.
7. R.Ubar, M.Kruus, T.Rang. Electronics Design and Test.
Public Service Review: European Union, Issue 13, 2007, p.52-53.
Research results in 1992 - 1999
The main research results obtained in the years (1992-1999) by the staff and students at the chair belong to the following fields of Digital Design and Test:
1. Decision Diagrams in Test Synthesis and Diagnosis of
Digital Systems
A new approach based on decision diagrams (DD)
to create algorithms and tools for automated test design and fault diagnosis
for digital systems was developed.
DDs were proposed the first time for test
generation under the name of alternative graphs (AG) in [8].
Unlike the traditional binary decision diagrams
(BDD), a special class of structurally synthesized BDDs (SSBDD) support test
design for gate-level structural faults (whereas BDDs can help only getting
functional tests with uncertain quality for the given implementation).
DDs serve as a mathematical basis for solving a
wide spectrum of test design tasks, resulting in a uniform model and a
restricted set of standardized procedures (horizontal universality). They also
allow a uniform approach to test design at different system levels (vertical
universality).
DD-approach made it possible to describe a wide
class of digital circuits and systems on mixed logical and functional levels.
This class contains random logic, traditionally treated at the gate level, as
well as digital systems like microprocessors, controllers etc., traditionally
described at the procedural or RTL levels.
On the basis of the proposed DD-description, a
general fault model for digital systems was developed. The proposed model
covers in a uniform way a wide class of faults at different system
representation levels (stuck-at faults, opens, shorts, functionality faults,
different functional faults introduced specially for microprocessors, or for
VHDL designs). The model defined on DDs can be regarded as a generalization of
the classical gate-level stuck-at fault model.
References:
2. New Test Generation Methods
2.1. Hierarchical Test Synthesis for
Digital Systems.
On the basis of generalization of DDs, new test
generation methods for complex multi-level systems have been developed.
Differently from known methods both, higher and
lower design abstraction levels, and both, control and data paths are handled
by uniform fault models and procedures. Joint formal basis for gate- and higher
level descriptions allowed to adopt and generalize gate-level methods to higher
level ones, and to increase the test generation efficiency.
A novel conception of mixed level combining of
deterministic and random techniques in test generation is introduced. On the
RT-level, deterministic path activating is combined with random techniques used
in constraints solving. The gate-level local test patterns for components are
randomly generated driven by high-level constraints and partial path activation
solutions. The technique of mixing deterministic and random approaches allows
more efficiently handle high-level constraints while deriving local test
patterns for components.
Top-down and bottom-up approaches are combined in
the same framework which allows to increase the efficiency of the test
generation for a broader class of digital systems.
The new hierarchical test generator shows the
highest speed compared to the known generators for a given set of
internationally recognized benchmark circuits [7].
The dramatic increase in the speed of test
generation was reached by simplifying the fault propagation procedure, which in
some cases may lead to a lower fault coverage. For the given bechmark circuits,
however, the loss in fault coverage was minimal.
References:
2.2. Test Generation for
Finite State Machines
A new multi-level solution of automated test
pattern generation (ATPG) and fault diagnosis in finite state machines based on
DDs was developed. For the description of functions, structure and faults in
FSM, three levels are used: functional level (state transition diagrams),
logical or signal-path level and gate level. For all these levels, uniform
description language, uniform fault model and uniform procedures for ATPG and
test analysis were developed. This uniformity allows easily to move and carry
partial results from level to level when solving the tasks mentioned.
The ATPG approach proposed allows to solve the
inconsistencies of signals by backtracking at the level where signals were
assigned without crossing level borders. This helps to reduce search area, and
the complexity of test generation for sequential circuits is reduced nearly to
the complexity of the combinational circuits.
References:
2.3. Functional Test
Generation for Microprocessors
High level approach is used, which makes the
solution independent of internal circuit details. This independence is
important to designers of microprocessor-based systems, where main sources of
information are user manuals. The task of input data preparation can be
distributed between different experts with different skills: a designer
produces the description of the system, a test programmer prepares subroutine
templates for the test equipment, and a test expert should create local test
data for testing functions (if the gate-level implementation of these functions
is known, the local test data can be generated automatically).
The methods developed are uniform for different
levels of hierarchy, for example, for behavioral (instruction sets or
procedural descriptions), functional (macrocomponent netlists), or for
logical (gate netlists) levels.
The the following advantages were obtained:
independency of tests from the given tester, reduced memory cost because of
concisely structured tests, and reduced time cost for loading test data which
allows to increase the throughput of tester.
References:
2.4. Gate-Level Test
Generation
A novel low.level test generation approach was
developed based on structurally synthesized BDDs (SSBDD) which provide a
compact representation of gate-level circuits, unlike traditional BDDs they
support directly gate-level faults.
Traditional PODEM test generation algorithm was
implemented on SSBDDs, which showed higher speed than earlier gate-level PODEM
implementations.
References:
3. New Approaches to Fault Simulation
3.1. High Level Fault Simulation
A new conceptual approach based on high-level
decision diagrams for simulation of digital systems was developed. DDs allow to
uniformly describe a wide class of digital systems on mixed logical and
functional levels. This class contains random logic, traditionally treated at
the gate level, as well as complex digital circuits like microprocessors,
controllers etc., traditionally described at the procedural or RTL levels.
Unlike the HDL-based descriptions, DDs give an excellent formal basis for
diagnostic analysis of digital systems, and allow to create more efficient CAD
tools than event-driven HDL-based simulators for functional simulation as well
as for fault analysis and testing purposes. Due to the fact that only a part of
DDs should be traced during simulation and due to neglecting the time specific
information inherent in HDL descriptions, the speed of simulation on DDs can be
drastically increased in comparison to traditional event-driven simulators.
The research has been carried out in a close
cooperation with Laboratories CSI and TIMA in Grenoble, France.
References:
3.2. Fault Simulation at
the Gate Level
A new method was developed for fault analysis
based on combining the parallel backward critical path tracing inside fanout
free regions (FFR) with parallel forward critical path tracing between FFRs for
FFR stem fault analysis. The detectability of all given faults is calculated by
one simulation pass simultaneously for N test patterns, where N is the length
of the computer word. Because of reducing the complexity of the network model
to be analysed and because of the fault collapsing on FFR paths to only two
representative faults, the efficiency of the simulation rises and the capacity
of the memory needed reduces, compared to the known gate- or macro-level
approaches.
References:
3.3. Dynamic Simulation
Methods
A new efficient multi-valued simulation
approach for combinational or scan-path circuits for delay fault analysis,
hazard detection or dynamic test analysis was developed. Its basic idea is
substituting the traditional gate-level waveform calculation by nested Boolean
differential calculus on structurally synthesized BDDs. Introducing SSBDDs
allows to reduce the complexity of the model by replacing low-level
two-input-gate networks with higher macro-level representations. It is not
needed to create for each new macro-block a separate dedicated multi-valued
model. Instead, from the gate-level description automatically a
SSBDD-representation will be created, where a single general procedure for all
types of macros will be used. Experimental results showed the efficiency of the
new approach, compared to the traditional gate-level simulation. The efficiency
of simulation is increasing with increasing the number of levels in the
gate-level circuit.
References:
4. New Methods for Estimating Fault-Tolerance of Systems
A new technique was developed to select
malicious faults for dependability validation of fault-tolerant systems. A
high-level fault analysis method based on decision diagrams is applied. Thanks
to the generality of DDs, the present approach is independent from the fault
model. This independence allows easy introduction of hierarchy and multilevel
fault handling.
The main idea of the approach is to carry out
fault analysis and malicious fault list generation at a higher behavioral level
where the complexity of the model is low. The high-level reduced fault list
will be translated then into a lower-level fault list. In such a way, low-level
fault analysis in low-level circuit descriptions can be avoided.
Differently from the known method based on
using data flow diagrams where only data fault analysis is possible, the new
method is more general, and allows explicit handling in a uniform way of both
data and control faults.
Instead of expanding the full explicit data
flow whose size can explode, fault tracing is carried out on the compressed
high-level DD-model to build up a fault tree.
A new result is also integration of different
methods for fault collapsing. On a simple high-level example it was shown that
the new method allowed to reduce the malicious fault candidate list more than 4
times for control faults and more than twice for data faults.
The research has been carried out in a close
cooperation with the research group of prof. Prinetto at Politechnico di
Torino, Italy.
References:
5. Verification and Design Error Diagnosis
A new approach is presented to automatically
diagnose single gate design errors in combinational circuits. The main original
feature of the method is the idea of mapping stuck-at fault diagnosis results
into the final localization of the design error. This allows to use the test
patterns and fault tables generated by traditional stuck-at fault test
generators to produce design error diagnosis.
The other important features of the approach
are: hierarchical approach, based on using structurally synthesized BDDs, and
the use of very powerful error detection and fault localization procedures
based on SSBDDs.
The future research in this field is directed
to the case of multiple design errors and to the case of complex gates. The use
of word level DDs seems to be very efficient in design error diagnosis at
higher functional levels like RTL or behavioral ones.
The research is carried out in a close
cooperation with the research group of prof. Borrione at the TIMA Laboratory in
Grenoble, France.
References:
A new technique for calculating the
testability measures of combinational circuits represented by structurally
synthesized BDDs is presented. The following advantages of the technique can be
outlined: 1) instead of gate-level, higher macro-level is considered which
reduces the complexity of the model; 2) no libraries of controllability and
observability models for macros are needed; 3) a generic procedure developed
for SSBDDs can be used for different testability measures defined either in
probabilistic or heuristic ways; 4) the proposed method has overcome the
problem of reconvergent fanouts at the subcircuit (macro) level, which allows
to calculate exact probabilities by a simple cumulative procedure.
The new technique to testability analysis is
applicable for sequential and combinational circuits specified at higher
functional levels. The primary use of the developed testability measures will
be in the evaluation of various designs in the early de-sign phase. Since the
measures are defined at the higher level compared to the gate level, they can
be used early in the design process, before the final implementation is
available. The new technique developed is based on DDs which allow a uniform
representation of both combinational and sequential circuits. Known methods for
testability calculation are based on different models for these types of
circuits, in particular, BDDs for combinational circuits and state tables for
sequential circuits, and therefore they require different techniques and
algorithms for calculation. Another advantage of new algorithms is the
generality in regard to different testability measures.
This research is currently carried on in a
close cooperation with prof. Zebo Peng at Linköping University, Sweden.
References:
7. Development of CAD Software for Automatization of Test Design
On the mathematical basis of structurally
synthesized BDDs a set of new algorithms and CAD tools for solving test design
tasks on the logical level representation of digital circuits has been
developed and implemented in a software system Turbo-Tester.
The software package consists of the following tools:
test pattern generation for circuits with scan-path (deterministic, random and
genetic approaches), test quality analysis for stuck-at and delay faults (fault
simulation and parallel critical path tracing method), multivalued simulation
(for hazard analysis and dynamic testing), fault grading (for estimating the
quality of random testing and Built-In Self-Test architectures – BILBO,
Circular Self Test Path). The package has been introduced into the university
teaching, it has been used in teaching in Estonia, Finland and Sweden.
References:
8.
Development activities in microelectronics design
8.1. CC – a cryptographical module for
digital communications.
8.2. Digital Encryption Standard
Macroblock – a design for an ASIC (contract with Fincitec OY Finland).
References:
9. Software Developed in the Laboratory
a) Tools for test generation and fault analysis dor digital circuits and systems
b) Converters
c) Libraries
d) Scripts for synthesis