Does Your Design Meet Its Specs? Introduction to Hardware Design Verification

This chapter is from the book

Hardware Design Verification: Simulation and Formal Method-Based Approaches

Learn More Buy

This chapter is from the book

This chapter is from the book 

Hardware Design Verification: Simulation and Formal Method-Based Approaches

Learn More Buy

1.6 A Quick Overview of Verilog Scheduling and Execution Semantics

On the assumption that you have a good understanding of Verilog, we will not review the general syntax of Verilog. However, we will review the more advanced features of the language—namely, scheduling and execution semantics—they appear in various places throughout this book. If you are well versed in Verilog, you can skip this section.

1.6.1 Concurrent Processes

Verilog is a parallel hardware descriptive language. It differs from a software language such as C/C++ in that it models concurrency of hardware. Components in a circuit always execute in parallel, whereas a software program executes one statement at time—in a serial fashion. To model hardware concurrency, Verilog uses two types of data structures: continuous assignment and procedural block. A continuous assignment executes whenever a variable in the right side of the assignment changes. As the name implies, a continuous assignment continuously watches changes of variables on the right side and updates the left-side variables whenever changes occur. This behavior is consistent with that of a gate, which propagates inputs to outputs whenever inputs change. An example of a continuous assignment is shown here. The value of v is updated whenever the value of x, y, or z changes:

assign v = x + y + z;

A procedural block consists of statements called procedural statements. Procedural statements are executed sequentially, like statements in a software program, when the block is triggered. A procedure block has a sensitivity list containing a list of signals, along with the signals' change polarity. If a signal on a sensitivity changes according to its prescribed polarity, the procedural block is triggered. On the other hand, if a signal changes that is not on the sensitivity list but is present in the right-hand side of some procedural statements of the block, the procedural statements will not be updated. An example of a procedural block is shown here:

always @(posedge c or d) begin
   v = c + d + e;
   w = m - n;
end

The signals on the sensitivity list are c and d. The polarity for c is positive edge, and no polarity is specified for d, which by default means either positive or negative edge. This block is executed whenever a positive event occurs at c. A positive edge is one of the following: a change from 0 to 1, X, or Z; or from X or Z to 1. The block is also triggered when an event occurs at d, positive or negative edge. A negative edge is one of the following: a change from 1 to either 0, X, or Z; or from X or Z to 0. Changes on variables e, m, or n will not cause the block to execute because these three variables are not on the sensitivity list.

In a way, a procedural block is a generalization of a continuous assignment: Any variable change on the right side of a continuous assignment triggers evaluation, whereas in a procedural block only changes in the variables on the sensitivity list can trigger evaluation, and the changes must conform to the polarity specification. Any continuous assignment can be rewritten as a procedural block, but not vice versa. The following procedural block and continuous assignment are equivalent:

// continuous assignment
assign v = x + y + z;

// equivalent procedural block
always @(x or y or z)
   v = x + y + z;

However, there is no equivalent continuous assignment for the following procedural block, because rising or falling changes are not distinguished in continuous assignment:

always @(posedge x)
   y = x;

1.6.2 Nondeterminism

When multiple processes execute simultaneously, a natural question to ask is how these processes are scheduled. When multiple processes are triggered at the same time, the order in which the processes are executed is not specified by Institute of Electrical and Electronics Engineers (IEEE) standards. Thus, it is arbitrary and it varies from simulator to simulator. This phenomenon is called nondeterminism. Let's look at two common cases of nondeterminism that are caused by the same root cause but that manifest in different ways.

The first case arises when multiple statements execute in zero time, and there are several legitimate orders in which these statements can execute. Furthermore, the order in which they execute affects the results. Therefore, a different order of execution gives different but correct results. Execution in zero time means that the statements are evaluated without advancing simulation time. Consider the following statements:

always @(d)
   q = d;

assign q = ~d;

These two processes, one procedural block and one continuous assignment, are scheduled to execute at the same time when variable d changes. Because the order in which they execute is not specified by the IEEE standard, two possible orders are possible. If the always block is evaluated first, variable q is assigned the new value of d by the always block. Then the continuous assignment is executed. It assigns the complement of the new value of d to variable q. If the continuous assignment is evaluated first, q gets the complement of the new value of d. Then the procedural assignment assigns the new value (uncomplemented) to q. Therefore, the two orders produce opposite results. This is a manifestation of nondeterminism.

Another well-known example of nondeterminism of the first type occurs often in RTL code. The following D-flip-flop (DFF) module uses a blocking assignment and causes nondeterminism when the DFFs are instantiated in a chain:

module DFF (clk, q, d);
input clk,  d;
output q;
reg q;

always @(posedge clk)
   q = d; // source of the problem

endmodule

module DFF_chain;

DFF dff1(clk, q1, d1); // DFF1
DFF dff2(clk, q2, q1); // DFF2

endmodule

When the positive edge of clk arrives, either DFF instance can be evaluated first. If dff1 executes first, q1 is updated with the value of d1. Then dff2 executes and makes q2 the value of q1. Therefore, in this order, q2 gets the latest value of d1. On the other hand, if dff2 is evaluated first, q2 gets the value of q1 before q1 is updated with the value of d1. Either order of execution is correct, and thus both values of q2 are correct. Therefore, q2 may differ from simulator to simulator.

A remedy to this race problem is to change the blocking assignment to a nonblocking assignment. Scheduling of nonblocking assignments samples the values of the variables on the right-hand side at the moment the nonblocking assignment is encountered, and assigns the result to the left-side variable at the end of the current simulation time (for example, after all blocking assignments are evaluated). A more in-depth discussion of scheduling order is presented in the section "Scheduling Semantics." If we change the blocking assignment to a nonblocking assignment, the output of dff1 always gets the updated value of d1, whereas that of dff2 always gets the preupdated value of q1, regardless of the order in which they are evaluated.

Nonblocking assignment does not eliminate all nondeterminism or race problems. The following simple code contains a race problem even though both assignments are nonblocking. The reason is that both assignments to variable x occur at the end of the current simulation time and the order that x gets assigned is unspecified in IEEE standards. The two orders produce different values of x and both values of x are correct:

always @(posedge clk)
begin
   x <= 1'b0;
   x <= 1'b1;
end

The second case of nondeterminism arises from interleaving procedural statements in blocks executed at the same time. When two procedural blocks are scheduled at the same time, there is no guarantee that all statements in a block finish before the statements in the other block begin. In fact, the statements from the two blocks can execute in any interleaving order. Consider the following two blocks:

always @(posedge clk) // always block1
begin
   x = 1'b0;
   y = x;
end

always @(posedge clk) // always block2
begin
   x = 1'b1;
end

Both always blocks are triggered when a positive edge of clk arrives. One interleaving order is

x = 1'b0;
y = x;
x = 1'b1;

In this case, y gets 0.

Another interleaving order is

x = 1'b0;
x = 1'b1;
y = x;

In this case, y gets 1.

There is no simple fix for this nondeterminism. The designer has to reexamine the functionality the code is supposed to implement and, more often than not, nondeterminism is not inherent in the functionality but is introduced during the implementation process.

1.6.3 Scheduling Semantics

Having discussed nondeterminism, it is natural for us to examine the scheduling semantics in Verilog (that is, the order in which events are scheduled to execute). Events at simulation time are stratified into five layers of events in the order of processing:

1. Active
2. Inactive
3. Nonblocking assign update
4. Monitor
5. Future events

Active events at the same simulation time are processed in an arbitrary order. An example of an active event is a blocking assignment. The processing of all the active events is called a simulation cycle.

Inactive events are processed only after all active events have been processed. An example of an inactive event is an explicit zero-delay assignment, such as #0 x = y, which occurs at the current simulation time but is processed after all active events at the current simulation time have been processed.

A nonblocking assignment executes in two steps. First, it samples the values of the right-side variables. Then it updates the values to the left-side variables. The sampling step of a nonblocking assignment is an active event and thus is executed at the moment the nonblocking statement is encountered. A nonblocking assign update event is the updating step of a nonblocking assignment and is executed only after both active and inactive events at the current simulation time have been processed.

Monitor events are the execution of system tasks $monitor and $strobe, which are executed as the last events at the current simulation time to capture steady values of variables at the current simulation time. Finally, events that are to occur in the future are the future events.