ATPG BASED TECHNIQUE TO IDENTIFY ILLEGAL STATES

Get Complete Project Material File(s) Now! »

Chapter 3 ATPG Based Technique to Identify Illegal States

Motivation

Guided Simulation experiments in [1] conducted on the Apoptosis model have shown to reach very few states for some proteins as clear from the data of individual proteins in Table 1-1. For example, as few as 11 states have been hit and remaining 245 states are still unknown for BAD_mito. For other proteins like BCL2, tBID_mito and tBID_BCL2, more than 50% of the states are still in the unknown category. So it is an indicative of the fact that the unknown states might be illegal, or if they are reachable, they are very hard states to reach.
In an effort to prove that these states are illegal, we investigate an ATPG technique modified to find illegal states. ATPG has been used earlier to identify illegal states quickly as shown in [34]. The idea is to employ a low-cost combinational ATPG to identify unreachable partial-states among groups of related flip-flops.

Overall Framework

Combinational ATPG algorithms can always be applied on an unrolled sequential circuit when they are considered as Iterative Logic Arrays. We first look at some of the fundamentals of identifying illegal states by looking at the combinations of certain group of flip-flops and then identifying the combinations not appearing in this set. Illegal state can also be explained in terms of n-Cycle-unreachable states. An n-Cycle-unreachable state is defined as a state that cannot be reached from any state in n cycles [34]. And if state is n-cycle-unreachable then it is also (n+1)-cycle-unreachable. Consider a framework in which the circuit has been unrolled for k timeframes as shown in Figure 2-3. Keeping this in mind, we explain our framework below.

Specifics of the Combinational ATPG application on ILA

The first thing to note is that the Pseudo Primary Inputs (PPIs) are unconstrained. This means that any state combination is possible at the PPIs. In case the sequential circuit has n primary inputs and m flip-flops, a k-frame ILA will have (k*n + primary inputs. Our aim is to keep the PPIs as unspecified throughout our simulation so that any illegal states at the PPO we learn will be true illegal states and not the illegal state with respect to the image of certain starting state. Another main attribute of this approach is that we need to explore the complete input space. If we do not explore the input space completely, and then learn the illegal states by elimination (a technique which we explain next), there might be some input combinations ignored which would have been able to reach some states now falsely considered as illegal.

Learning Illegal States by Elimination

In the Figure 3-2, we have given an example of complete input space exploration of depth 3 and then analyzing the state values at the leaves of the free BDD built during input enumeration. Keep in mind that the PPIs are left unconstrained. This means that all the states are possible at that initial boundary and hence states that are not visited at the PPOs via this complete input space enumeration are definitely illegal. Another important point to note is that since we are enumerating the complete input space of a certain depth, it becomes infeasible to enumerate the input space of all the inputs. Consider the Apoptosis circuit as an example which has 8 primary inputs. If we perform this experiment on an ILA of 6 timeframes of Apoptosis model, the number of primary inputs to enumerate is 48 which provide an input space of 2⁴⁸ which makes it impractical. So we have to select a proper set of inputs, not too large a number, and enumerate those inputs. This is the reason we also see some don’t-care values (‘x’) in the states at the leaves of the Free BDD.
As an example, consider the following scenario where the state we see is x1x1 at one of the leaves of the BDD. We expand it to mark all the states contained in this cube. Hence, x1x1 expands to 4 states: 0101, 0111, 1101 and 1111. This approach ensures that we conservatively mark all states marked as potentially reachable/legal. But indeed, there can be cases when a state that is illegal might be marked as visited because of the expansion of ‘x’s in the states.

Details on Maximum Decision Level

Considering the Apoptosis circuit for this kind of experiment, there are 64 PPI in the ILA of k time frames. And if we fix 24 as the Maximum Decision Level (MDL), then all the remaining primary inputs of the ILA (k*n – 24) will be having a logic value of ‘x’. We cannot really increase MDL beyond this point because it causes an exponential increase in the input space. A MDL value of 24 means there are 16 million input vectors (and 16 million leaves) for logic simulation and that is somewhat manageable.
Now in order to obtain maximum specified state bits at the Free BDD leaves, we need to heuristically select 24 primary inputs. SCOAP values [35] are a good metric to pick that set. We perform this experiment for a particular set of flip-flops as the target state set to consider. Usually, in a circuit where there is no high level information or where there is no clear partition of the state set, MLP procedure [36] is used to have a fairly good partition of flip-flops where the state variables in each partition have high correlation. This procedure computes the input support for flip-flops and clusters the ones with closer supports. In the case of Apoptosis model, we have a clear picture of the state partition in the form of proteins. Hence, we target these state partitions in the form of proteins to analyze.

Selection of a set of primary inputs in ILA for a particular protein

In order to select 24 (MDL) primary inputs for our target proteins, we use the SCOAP values. To calculate the SCOAP value for a particular protein flip-flops, we assign very high observability values to all other flip-flops and zero observability is assigned to the target flip-flops. Note that observability value of zero means that the signal is completely observable. Since observability values are calculated from outputs towards the inputs, we proceed in a levelized manner to calculate the observability values of the inputs.
It is desirable to obtain the observability values of inputs in such a way that there is a group of inputs having low observability values preferably that number of inputs being near to the MDL and rest of the inputs have high observability values, as shown in Figur,3-4. This simply means that the input set for which we will explore complete input space will consist of the inputs having low observability values (low observability value means the signal is very observable) and we need to pick up MDL number of such inputs.

CHAPTER 1 INTRODUCTION
1.1 FINITE STATE TRANSITION SYSTEM MODELING OF APOPTOSIS
1.2 PREVIOUS RESULTS OF APOPTOSIS MODEL ANALYSIS
1.3 OUR CONTRIBUTIONS
1.4 ORGANIZATION
CHAPTER 2 BACKGROUND
2.1 FSM
2.2 SAT (SATISFIABILITY).
2.3 ATPG
2.4MODEL CHECKING
2.5 IMAGE AND PREIMAGE COMPUTATION
CHAPTER 3 ATPG BASED TECHNIQUE TO IDENTIFY ILLEGAL STATES
3.1MOTIVATION
3.2 OVERALL FRAMEWORK
3.3 COMPLETE INPUT SPACE ENUMERATION AT CUT-SET BOUNDARY
3.4 RESULTS
CHAPTER 4 SAT BASED TECHNIQUE TO IDENTIFY ILLEGAL STATES
4.1MOTIVATION
4.2 GENERAL FRAMEWORK OVERVIEW
4.3 STUDY OF PROTEIN COMBINATIONS
4.4 AN INCREMENTAL APPROACH TO CALCULATE ILLEGAL STATES
4.5 RESULTS
CHAPTER 5 CONCLUSION
BIBLIOGRAPHY
GET THE COMPLETE PROJECT
Identification and Analysis of Illegal States in the Apoptotic Discrete Transition System Model using ATPG and SAT-based Techniques