代写DEE3519、C/C++设计编程代写

日期：2023-06-19 10:27

National Yang Ming Chiao Tung University DEE3519: EDA Algorithms and Implementation

Assignment #4: SAT-Based Path-Delay-Fault ATPG

(Due Date: 2023/06/08 23:59)

Introduction:

ATPG (Automatic Test Pattern Generation/Generator) is an electronic design

automation method used to find an input sequence (or test vectors/test pattern) that,

when applied to a digital circuit, we are able to distinguish between the correct circuit

behavior and the faulty circuit behavior caused by defects.

A path-delay-fault ATPG generates a vector pair (v1, v2) to creates a transition at the

beginning of the target path P. Then the corresponding transition is propagated

through target path P. Different off-input assignments can result in different path

sensitization criterion. Figure 1 shows the basic idea of path sensitization.

An efficient circuit-SAT solver (CSAT) [1][2] is utilized as the fundamental engine of

this path-delay-fault ATPG (KF-ATPG).

Objective:

In this assignment, you are asked to write a C++ program to perform Circuit-SAT

based ATPG, and generate the test patterns for path-delay-faults.

A Quick Start to KF-ATPG:

(1) kai_main.cpp: the main flow is implemented in this part, including input files

parsing and creating an instance of a CSAT solver.

(2) kai_objective.cpp & kai_objective.h: these are the program files you need to

finish. The functions BuildFromPath_R () and BuildFromPath_NR() will receive

a target path pointer, and you need to give appropriate constraint settings for each

gate along the path in order to propagate the transition state toward primary

output through the path. Also, don’t forget to create the transition at the

beginning of the target path as well.

National Yang Ming Chiao Tung University DEE3519: EDA Algorithms and Implementation

E

F

0

(3) example/: 2 exemplary test cases are given under this directory, which can be

used to test your program.

Implementation Details:

(1) Controlling Values and Non-Controlling Values

A controlling value at a gate input is the value that determines the output value of

that gate irrespective of the other input value. The opposite of controlling value

is non-controlling value. For example, the controlling value of an and gate is 0;

the controlling value of an or gate is 1.

0 1

1

X X

Gate Type

Controlling Value

(CV)

Non-Controlling Value

(NCV)

AND 0 1

OR 1 0

(2) On-input and off-input

A signal is an on-input of path P if it is on P. A signal is an off-input of path P if

it is an input to a gate on P but not an on-input.

A

B

C G Target path

D

Target path A→E→G

On-input A, E, G

Off-input B, F

(3) Timeframe

Transition Type

Logic value at

Timeframe 0

Logic value at

Timeframe 1

Rising(0→1) 0 1

Falling(1→0) 1 0

National Yang Ming Chiao Tung University DEE3519: EDA Algorithms and Implementation

(4) Robust Test(R) vs. Non-Robust Test(NR)

Robust Test Non-Robust Test

Definition

Guarantee to detect the delay

fault on the target path. Fault

detected or not is independent of

all other delays in the circuit.

The detectability of a fault

under a non-robust criterion

depends on the arrival time of

input pins.

Example

on

off

A

B

C

on

off

A

B

C

Case 1

Both inputs

have

delay fault

A

B

C

Clock period

A

B

C

Clock period

Result

Rising transition on A is

successfully propagated

through C

Falling transition on A is failed

to propagate through C

Case 2

Only oninput has

delay fault

A

B

C

Clock period

A

B

C

Clock period

Result

Rising transition on A is

successfully propagated

through C

Falling transition on A is

successfully propagated

through C

Case 3

Only offinput has

delay fault

A

B

C

Clock period

A

B

C

Clock period

result

Rising transition on A is

successfully propagated

through C

Falling transition on A is failed

to propagate through C

National Yang Ming Chiao Tung University DEE3519: EDA Algorithms and Implementation

Summary

Rising transition on A is

detectable in every case. By

applying this vector(A:01,

B:01), we are running a robust

test.

Falling transition on A is

detectable only in case 2. By

applying this vector(A:10,

B:01), we are running a nonrobust test.

The definition of robust/non-robust test may look a bit complicated, but here you got

a table which sums up all the situations you will encounter. You can easily determine

what value to apply on on-input/off-input by looking up the table below.

On-input transition

Off-input assignments

Robust(R) Non-Robust(NR)

cv → ncv x → ncv x → ncv

ncv → cv ncv → ncv x → ncv

(5) Input files

For each case, you got 2 files as input, which are xxx.bench and xxx.path_not.

(1)xxx.bench: this is a netlist file of a combination circuit.

(2)xxx.path_not: this file indicate the path being targeted. Each path starts with

a primary input and ends wih a primary output. The R/F in the front of each path

indicates the transition state of the primary input gate. R represents rising and F

represents falling. transition state of the primary input gate

primary input primary output

→Path 1

→Path 2

→Path 10

For example, we want to generate the test patterns in order to detect these 10 ……..

National Yang Ming Chiao Tung University DEE3519: EDA Algorithms and Implementation

path delay faults. So we need 10 pairs of input vectors, one for each path.

Language:

C++.

Platform:

You may develop your software on UNIX/Linux.

Usage:

Compile: $ make

Clean up: $ make clean

Execution: $ ./KF_ATPG

-atpg [testing type, R or NR]

-cir example/[testbench file, ex. xxx.bench]

-path_not example/[path file, ex. xxx.path_not]

-output [output patterns generated by ATPG, name it as xxx.pttn]

Exmale: $ ./KF_ATPG -atpg NR -cir example/c17.bench -path_not

example/c17.path_not -output c17.pttn

Submission

Please compress all of your source code into a zip file and name it by your student ID.

For example, “311510168.zip”. Then upload the compressed file to the new E3

website by the deadline (2023/06/08 23:59).

Grading policy:

(1) Example case correctness (60%)

(2) Hidden case correctness (40%)

Delay Penalty:

 Within 1 day: score * 0.8

 Within 2 days: score * 0.7

 Within 3 days: score * 0.6

 More than 3 days: score = 0

Reference:

[1] Feng Lu, Li-C.Wang, Kwang-Ting Cheng, and R. C.-Y. Huang, A Circuit SAT

Solver With Signal Correlation Guilded Learning. Proc. Design Automation and

Test in Europe (DATE), 2003

[2] Feng Lu, L.-C. Wang, K.-T. Cheng, J. Moondanos and Z. Hanna, A Signal

Correlation Guided ATPG Solver and Its Applications for Solving Difficult

Industrial Cases. Proc. Design Automation Conference (DAC), 2003