INTRODUCTION
Complexity and the need to achieve faster throughput further increases the complexity of finite state machines (FSM) of serial protocols like USB, PCIe, Ethernet, OTN, etc. These complex FSMs contain a large number of states, transition conditions, timeout mechanisms, and relevant behavior of the design in each respective state. FSMs are a source of functional bugs in any protocol. It is a very tough job to functionally verify a FSM in each of its state transition conditions and corner scenarios.
The purpose of this article is to share a strategy on how to verify any simple or complex FSM in an organized, robust, manageable, and efficient way. To verify such FSMs thoroughly we need random scenarios that cover all the possible state transition conditions, corner and boundary conditions, and relevant functional behavior. For that, we require a strong base entity that helps to generate random scenarios to cover all FSM entry-exit conditions and erroneous scenarios easily. This base entity also helps to choose a random FSM path to reach your expected states and perform various error operations.
This article describes an approach to develop an organized base entity that produces random scenarios to minimize verification time and effort during test case implementation.
DIFFICULTIES FACED IN COMPLEX FSM VERIFICATION
- Cover all possible FSM entry-exit path
- Create strong architecture which reduces scenario generation effort
- Cover all possible state conditions and poison scenarios
- Place the protocol checks for each random and timeout scenario
- Find RTL corner bugs
- Reduce effort of test case creation and debug
WHAT IS A BASE ENTITY?
There are generally two major scenarios to verify in any complex FSM:
- FSM entry-exit conditions
- State packet error and timeout conditions
Many times, it is desirable to perform a certain set of operations to reach the expected state and execute the relevant scenario. We do this using a base entity that uses data encapsulation and abstraction provided by SystemVerilog OOP. This base class contains all FSM state transition flow generic methods which cover all the difficulties described above and help to create any complex scenario with minimal effort.
Advantages:
- Generic approach easily applies to any FSM architecture
- Cover all FSM entry-exit conditions
- Reusable and easy to maintain
- Organized structure which helps for future expansion
- Random generation helps to achieve ~95% coverage rapidly
PREFACE
A complex RTL has to consist of many different algorithms, which need to be verified using test bench components. But this article only talks about the FSM verification strategy. The basic testbench components which are required to verify the FSM are shown in figure 1. It also represents complex FSM state transition paths and conditions.
 |
Figure 1
DUT (FSM): Device under test (DUT) represents actual RTL which make up the different feature modules based on the application. FSM is a sub-unit or main component in the DUT. It is the key component which helps to achieve design functionality. It is designed in different styles, states and output encoding conditions based on requirements.
VIP: Verification IP (VIP) is a pre-built protocol set of code that is used for verification. It is connected with the DUT through an interface and provides an appropriate response. It contains a stimulus sequence, set of checks, coverage, and other things related to the protocol.
Reference Model: The reference model is a mimic version of the RTL and is an important element in the testbench. It observes the same traffic as the DUT, behaves as per the specification, and also predicts the possible state transitions. The model is aware of the DUT’s FSM state behavior and related parameters. It achieves this goal by continuously monitoring the DUT’s interface signals and comparing the DUT’s internal state transition with the predicted value.
Scenario Base Entity: The scenario base entity is represented as a parent class for all scenario generators. We will explain the base entity generation strategy and generic methods in this article. It simplifies the FSM’s verification and reduces the effort for difficult scenario generation.
BASE ENTITY DEVELOPMENT
The primary component of any FSM design is its state and transition condition. The FSM diagram shown in figure 1 consists of seven states (S1-S7) and 13 forward-backward state transition conditions (C12, C41, etc.). This section explains the base entity development strategy using the above FSM diagram as a reference. But it can be applied to any kind of FSM.
A base class system typically consists of generic variables and methods which simplify child scenarios generation. In FSM verification scenarios, there are multiple ways to reach any expected state and perform a set of operations. As per the above example, to reach the S6 state out of three paths ([1] S1->S2->S3->S6; [2] S1->S3->S6; [3] S1->S4->S6), the system can choose any random path. In the same way, the base entity helps the system to reach an expected state using a random path from all possible path combinations. Base classes not only help to reach an expected state, but also checks a set of conditions between transition paths from source to destination. The set of conditions contains timeout checks, deadlock conditions, wrong state transition, and the DUT status value of a particular state.
It distributes transition paths based on states and defines SystemVerilog enumerated data types for the specific state transition that has multiple entry paths to reach. Also, it defines the initiate state entry method which executes a set of stimuli to reach an expected state via the selected path. All state-wise entry methods are handled by one centralized method. The child only needs to randomize the base property and access this centralized method to reach the expected state. All other checks will be handled by the base.
This organized architecture also helps to accommodate future development. In this strategy, the whole state transition implementation load is distributed per states. So if one or more states are added in the future, we can achieve the desired functionality with minimal base updates. Here only two major updates are required to settle new states. The first change is to add a new initiate state entry method, as defined above. The second change is to update the centralized method which handles all state-wise entry methods. The third change could be to update timers as per new state requirement.
The following code snippet explains the base class development strategy for our example FSM.
class base entity:
// State enumeration
typedef {S, S2, S3, S4, S5, S6, S7} state_enum;
// Take entry enum for the specific state which has multiple conditions to reach.
typedef {C13, C23} S3_entry_enum;
typedef {C36, C46} S6_entry_enum;
...
// Defined final state until that base class choose a random path.
rand state_enum expected_entry_state;
rand S3_entry_enum S3_entry;
rand S6_entry_enum S6_entry;
// ----------------------------
// Generic Methods
// ----------------------------
// It is a main FSM state transition method which helps extended(chid) class to
// reach expected state.
// It takes help from other state entry methods to achieve expected state
// through a random path.
task initial_state_transition (state_enum expected _ entry state ) ;
case (expected_entry_state )
...
S3 : initiate_S3 entry (S3_entry_enum S3_entry );
...
S6 : initiate_S6 entry (S6_entry_enum S6_entry );
...
endcase
endtask
/ / Using a random path initiate S3 state entry process.
task initiate_S3_entry (S3_entry_enum S3_entry);
case (S3_entry)
C13 : initiate_S1_entry (S1_entry_enum S1_entry);
C23 : initiate_S2_entry (S2_entry_enum S2_entry);
endcase
endtask
// Using a random path initiate S6 state entry process.
task initiate_S6_entry (S6_entry_enum S6_entry);
case (S6_entry)
C36 : initiate_S3_entry (S3_entry_enum S3_entry);
C46 : initiate_S4_entry (S4_entry_enum S4_entry);
endcase
endtask
// The single path S12 path is only applicable for S2 entry.
task initiate_S2_entry (S2_entry_enum S2_entry);
fork
S2_perform_set_of_operations ();
S2_timeout_and_condition_check ();
join
endtask
endclass |
FSM SCENARIO GENERATOR
From the previous section, we saw that the base entity creates a strong background for the scenario generator. Now the generator's responsibility is to use the appropriate base methods and create scenarios as per the requirement. We can list FSM verification scenarios in two major categories, defined as follows:
- Normal state transition entry-exit condition: This scenario covers all of the FSM’s entry-exit paths and state transition conditions. It also covers all state-related packet transmissions and error conditions which are ignored by the DUT. Test case pass criteria should be no errors reported by the reference model or VIP.
- Packet error injection and state timeout: In this type of scenario, the generator injects errors in the state packet using an error injection mechanism. It also blocks packet transmission to check the DUT’s state timeout value. Test case pass criteria is both DUT and reference model moves to the same state after timeout.
First of all, we discussed the normal scenario generation using a base entity. It is very easy to generate such scenarios with the help of base generic methods and variables. It is only required to select the operational state and next expected state in the generator. Systems reach the operational state using the base class “state entry initiate” method, at which point it performs state related operations. After completion of state operation base moves to the RTL’s next state transition check. It compares RTL actual with expected state transitions to make the test case final decision.
The most difficult task in FSM verification is identifying erroneous scenarios. It is very tough to generate such scenarios for all state packets and timers without the help of a strong background and an organized structure. Many testbench components closely work together to inject suitable packet errors to check the RTL’s behavior. The required components include a base entity, error injection mechanism, reference model, interrupt monitor, and test case checks.
Proper work distribution among all these components will make this task easy. The base class should bring up the proper state and situation in which the generator can easily run the error operation. It also helps to continuously monitor the RTL status and state timer. If it detects the wrong situation or state transition, it suddenly stops simulation by displaying the proper error.
Each transaction engine has a list of all supported error types: generator randomize packet error type from the list as per state requirement and hand over to error injection engine. In the error injection engine we can consider the call-back or driver which have the capability for poison insertion in the transaction. It modifies transaction and drives on the interface.
The reference model plays a vital role in the test- bench in terms of bug identification and coverage generation. It closely works with RTL and also refers to the same interface which the RTL has. It follows a protocol rule for each input transaction and predicts the RTL state transition. It compares actual RTL behavior with the predicted behavior and identifies RTL hidden bugs. It also gathers RTL stimulus and response information for coverage generation.
The following code snippet explains the generator development strategy.
class scenario_generator extends base_entity;
typedef {C12, C13, C14, C23, C35, C36, C46, C57, C67, C41, C52, C64,}
state_transition_condition_enum;
// Defined operational state until that base class choose a random path.
rand state_enum operational_entry_state;
// Defined final goal state which expected after accomplished state condition.
rand state_enum next_expected_state;
// It randomly chooses state conditions for selected operational state.
rand state_transition_condition_enume state_transition-condition;
// Constraints are used to select the next expected state with help of
// operational state and the related transition condition.
constraint c_operational_state {S2, S3, S4, S5, S6, S7}
constraint c_next_state { ...
(operational_entry_state == S6 && state_transition_condition == C67) ->
(next_expected_state == S7);
(operational_entry_state == S6 && state_transition_condition == C64) ->
(next_expected_state == S4);
... }
// ---------------------------
// Methods
// ---------------------------
// Common generator method which is used to create any type of scenarios.
task generator (state_enum expected_entry_state);
// Execute base method to reach at operational state.
initial_state_transition (operational_entry_state);
// It is used to perform any kind of operation
// (Normal, Erroneous) based on scenario needs.
perform_state_operation (operational_entry_state, state-transition_condition);
// Check FSM transition in the next expected state.
wait_for_next_state (next_expected_state);
endtask
endclass |
CONCLUSION
Initial development efforts are required to make a stable FSM base entity and the reference model. However, once the model is robust, generated random scenarios open a lot of mismatch between the RTL and reference model, which helps to discover many RTL issues. Random path selection approaches help to identify state-dependent hidden bugs. While the whole strategy is very effective and fast to find RTL bugs of complex FSMs, we can use this approach to verify any kind of state machine. We used this approach to verify a complex LTSSM state machine, which was used in serial protocols like USBX.0 and PCIeGenX.0. Up to now more than 20 LTSSM bugs have been found in pre-verified DUTs. Also, we achieved more than 90% coverage with only 10 random test cases.
Back to Top
