Monday, August 11, 2008

What is a Race ? How to avoid it ?

In this topic, i would like to address races, their causes, implications &
preventions.

Definition : A Race condition occurs when two or more processes attempt to
access a target simultaneously.

Types of Races
I) Races in UDPs
II) Loops
III) Contention races

I) Races in UDPs
Race condition in UDP is caused by 2 conflicting rows in the table

Example :

primitive udp(q, a, b);
output q;
input a, b;
reg q;
table // a b : q : q+
r 0 : 0 : 0 ;
0 r : 0 : 1 ;
endtable
endprimitive

Solution :
These kind of races are uncommon. Most of the UDPs used in the ASIC
design comes from ASIC library vendor, So refer to your library vendor
about this problem or another strategy is to combine the conflicting rows
into a single row

II) Races in LOOPS
Races in loops can further be simplified into

a) Combinational Loops
b) Data Loops
c) Simulation Loops


Combinational Loop is a path in the code, that feeds back upon itself, yet
has no state devices in the path.

Example:

module CMBLOP (o, a, b, c);
output o;
input a, b, c;
reg o;
wire m = a | o;
wire n = b | m;
always @(c or n)
o = c | n;
endmodule

Solution :
There is no fixed rule to actually break the combinational loop, a
detailed understanding has to be required before breaking the loop. If
there is no problem with the functionality, insert a Flop in between the
feeback path. Remember all the combinational path have to broken for the
timing purpose.


A Data loop is a path in the design that feeds back upon itself between two or
more processes and has one or more latches in its path.

Example:

module DATLOP;
reg q, d, e;

always @ (e or d) //latch
if (e)
q = d;

always @ (q)
d = ~q;

endmodule // DATLOP

Designer has take outmost care to avoid such things as it can lead to
infinte loop if the enable is made continuously high. A detailed
understanding of the functionality is required to break the loop.

A simulation loop is one where there is no data flow between two or more
processes but there is a simulation feedback path.

Example.

module SIMLOP;
wire a, c;
reg b;

always @ (a or c) begin
b = a;
end

assign c = b;

endmodule



III) Contention Races

Verilog has a special provision for concurrent processes. Two different simulators
can simulate two concurrent processes in a different order. Because of this
ambiguity, you may get different simulation behavior from different simulators
for the same Verilog description.

A contention race occurs when the order of execution of multiple concurrent
Verilog processes can affect the simulation behavior.

Most races are not found until the Verilog description is ported to a different
Verilog simulator, or they are never found, even after synthesis. Discovering
the unstable behavior after the chip is fabricated is very expensive.

There are two reasons why a simulator cannot find races
i) A simulator usually has a fixed scheduling mechanism; when two processes are
in the event queue, one is always executed before the other. However, the real
chip performs all the computation in parallel; hence, one process may or may
not be executed before the other.
ii) A simulator does the simulation according to the test vectors. If the test
vectors do not include the case that will result in the race, the simulator has
no way to discover it.


A race occurs when two or more processes attempt to access a target simultaneously.
Different types of races are
i) Write – Write
ii) Read – Write
iii) Trigger propagation races

i) Write - Write Contention Race

Example

module wr_wr_race (clk, a, b); //Write – Write Race
input clk,b;
output a;
wire d1, d2;
reg c1, c2, a;

always @(posedge clk) c1 = b;
always @(posedge clk) c2 = ~b;
assign d1 = c1;assign d2 = c2;
always @(d1) a = d1;
always @(d2) a = d2;

endmodule

Solution :
Write-Write Race are type of bus contention.Usually, write-write races
are resolved by combining the writes into single process.

ii) Read - Write Contention Race

Read-write races occur when two concurrent processes attempt to access the same
register. One process is trying to write a new value into the register and the
other process is trying to read a value out of the register.

Example :

always @(posedge clk) /* write process */
status_reg = new_val;
always @(posedge clk) /* read process */
status_output = status_reg;

Solution :
Use of non-blocking statement instead of blocking statements.

iii) Trigger Propagation Race

A trigger propagation race involves three processes. The first two processes
are concurrent and their order of execution is indeterminate. The third process
is sensitive to two signals. Each of these two signals are assigned in one of
the first two processes.

Example :

// process 1
always @(posedge clk)
if (condition1) a = 1'b1;
// process 2
always @(posedge clk)
if (condition2) b = 1'b1;
// process 3
always @(a or b)
if(a || b) count = count + 1;



"Guidelines for Avoiding Race Conditions:[1]"
1. If a register is declared outside of the always or initial block, assign to it using a nonblocking
assignment. Reserve the blocking assignment for registers local to the block.
2. Assign to a register from a single always or initial block.
3. Use continuous assignments to drive inout pins only. Do not use them to model internal
conbinational functions. Prefer sequential code instead.
4. Do not assign any value at time 0.


[1] Janick Bergeron, Writing Testbenches, Functional Verification of HDL Models, Kluwer
Academic Publishers, 2000, pg. 147. (flawed race avoidance guidelines)


No comments: