Least Recently Used(LRU) algorithm implementation in Hardware

LRU algorithm is one of the most commonly used cache page replacement algorithms. It’s often easy to imagine the implementation of LRU using linked list structure in software but hardware implementation could be tricky and requires some thoughtful analysis. Here I have made an attempt to put together steps of matrix method of LRU implementation in Hardware which could eventually be translated to code in Verilog or VHDL

Matrix implementation requires n*n matrix for n location cache i.e 4*4 memory(16 Flipflops) for 4 location cache. The algorithm should track all the locations as it gets updated and should output the least recently used location (or index of cache).

Let’s start with simple 4 location cache and then generalize the solution for n location cache.

4 location cache with each location of 8 bits:

4 * 4 matrix to store the history and help calculate the least recently used location in cache

Total of 16 Flipflops for 4 location cache 

We would save the information of relative age of each location with respect to other

Say    A > B   =>  A is older than B

          A > C   => A is older than C

Let’s represent this in the matrix as below:

Diagonal is always 1 as it tries to compare same elements like A vs A, B vs B etc

Also it’s easy to see that A is older than B  =  ! (B is older than A)

(A > B) =  !(B>A)

With the above logic, matrix would look like below:

It’s easy to see that left half of matrix across diagonal is exactly opposite to right half.

Right half of the matrix would entirely be enough to get the age relation between cache locations

Steps:

1) Initialize the matrix to any known value. Say D > C > B > A

     i.e, D is the oldest and A is newest location

Note that diagonal value is always one

2) If location I is accessed then row I is set to zero and column I is set to one except for diagonal. 
     Update the matrix every time cache is accessed

3) Oldest location will be the location for which 'AND' of each column is equal to 1

     i.e,  &[columns of location]==1

It’s turns out to be true to D as all of its columns has 1

Let’s take an example and see if this works

Say order of access of cache is C,B,D,A è oldest location at the end of this should be C

a) Initialization to D > C > B > A

    b) C is accessed  => C is the most recent. Change all of c rows to zeros and columns to one

All of D columns are one and D should be the oldest at this point of time.

From above matrix, we can also derive that

 A > B = 0 , A > C =1, A > D = 0 , B > C =1 , B > D = 0 , C > D = 0 
   => C < A < B < D

    c) B is accessed. i.e, C followed by B. Change all B rows to zeros and B columns to ones

   New matrix would be as below:

D is the oldest as all of it’s columns are 1

    d) D is accessed. C followed by B followed by D. Change all B rows to zero and B columns to one

  New matrix:

A is the oldest and least recently used

     e) A is accessed. i.e, C followed by B followed by D followed by A

C column is all one and hence the oldest as expected

Avoiding race around in Assertions

I have been coding assertions a lot recently to verify certain functionality at SOC/block level. I ended up with some false failures in regressions mainly due to Systemverilog race around and I could not find good online guidelines to avoid such conditions. After researching, I am putting up some learnings here and many of these directions are directly coming from CummingsSNUG2006Boston_SystemVerilog_Events paper.

Broadly assertions can be classified into 2 categories

1. Concurrent Assertions – describes logic behavior of signals that spans over time
2. Immediate Assertions – describes logic behavior of signals at an instant of time

Understanding SystemVerilog Scheduling semantics is crucial to understand simulation induced Race around conditions. I am summarizing some important aspects below:

Simulators simulate the Testbench based on IEEE Scheduling Semantics of SystemVerilog. A single and smallest timeslot can be visualized to have many regions as shown below 

Event Regions Diagram in SV(Picture taken from CummingsSNUG2006Boston_SystemVerilog_Events Paper)

Each of the regions(like preponed, active, observed, reactive) is associated with specific functionality.

Assertions are passive and they do not drive any stimulus into the design. If proper coding guidelines for RTL/Testbench are followed, we should not see any race around conditions.

Race around in Concurrent Assertions

All the signals in concurrent assertions are sampled in the preponed region before the clocking event. Values do not change in the preponed region(Read-only region) and hence sampled values of signals do not change during that particular time step of evaluation(in the observed region) multiple times. Hence if RTL/Testbench guidelines are followed, there is no special care to be taken while writing concurrent assertions as it is inherently protected.

Also, note that if ‘event.triggered’ is used in assertion then the current value(during that timestep) of the event is used for evaluation in the observed region. ‘triggered’ is a property of an event – evaluation do not happen until the statement is executed. If the event is getting updated in active region then triggered property will be a new value when evaluated in the observed region

Race around in Immediate Assertions

Simple immediate assertions are part of sequential statements (Ex part of ‘always’ construct) and their sampling & triggering depends on where they get executed.

If you observe the Event region, certain signals may get evaluated twice or more depending on when/if the value gets updated and hence might result in simulator seeing 2 or more values in one single time step although one values eventually settles. This could be one source of a possible misfire of immediate assertion. Signal value getting updated twice in a single step and during these scenarios $display prints 2 values of the same variable while $monitor/$strobe which executes in Postponed region prints only one value.

Looking at the possibility of assertions action block triggering twice or more than in immediate assertion, Systemverilog committee came up with a "final" deferred assertion to execute in the "postponed" region which is the last region before advancing time and all the values are settled to their final value. 

There 2 kinds of deferred assertions in SystemVerilog

1.  Observed deferred assertion –

·         Evaluation of immediate assertion is postponed to observed region.

·         Problem of glitch still exists if one decides to use program block which might      trigger loop back from reactive to active and multiple execution

·         Use #0 after assert keyword

Ex

assert_check: assert #0 (cs == 2'b00 && enable==1’b1) else $error ("cs and enable are in wrong combination");

2. Final deferred assertion

·         Evaluation of immediate assertion is postponed to postponed region

·         Works for all kinds of situation and most recommended

·         Use final keyword after assert keyword

Ex:

assert_check: assert final (cs == 2'b00 && enable==1’b1) else $error ("cs and enable are in wrong combination");

Binding in Systemverilog

Assertions are written both by design engineers and verification engineers depending on what is being checked and wherein the design hierarchy. If Assertions reside inside design modules which are going to be synthesized then these assertions which solely meant for checking/verification have to be enclosed inside compilation directives like ifdef so they can be hidden from Synthesis tools. As an alternative, Systemverilog provides bind feature which allows specific modules which contain all the assertions to be bound during elaboration. This feature essentially instantiates assertion module inside design module and all the assertions behave as if they reside inside the design. This enables engineers to keep verification code separate from design code.

Syntax:

bind <target RTL module> [:<name of the target instances>] <assertion module> <binding instance name> (<port list>);

where
[<name of target instance>] is optional. If nothing is specified, binding is done on all the target RTL module instances

<assertion module> is the module which contains all the assertion code.

<port list> is the port connections from target RTL module to assertion module.

Assertion module is like any other module. Keep below points in mind:

• Define all the inputs required for assertions as input ports.
• No outputs from assertion module as it is strictly not for driving anything into the design
• Input Port names can be name. If you decide to keep the same port names as the net name of target design module then you while binding .* would automap the connections. Connect by name if the input port name is different from the net in the target design module
• If any internal probes from instances below target design module are required for the assertion then same can be made as input to the assertion module and passed as an argument while making assign hierarchical probing at the target module. This should be avoided for any synthesizable block and usage is mostly intended for bmod assertions which requires internal probing

Ex:
Binding to all modules with name module_name:
bind module_name inst2_assert inst2a(.mode(mode_value),
                                                               .order(order)
                                                             );


Binding to the specific instance with name inst2 (Instance binding):
bind module_name:inst2 inst2_assert inst2a(.mode(mode_value),
                                                                       .order(order)
                                                                       );

Ex:

Enabling and Disabling Assertions

Many times, assertions need to be disabled based on the test or during the simulation. For example,   some assertions are not really valid before reset(not counting disable iff feature of assertion property) and you might want to switch off those assertions. Similarly, the case when there is mode transition you might want to switch off certain assertions till transition is complete and then re-enable.

There are different methods to enable and disable assertions. Below explanation summarizes it

1) Use of $assertoff and $asserton system Verilog tasks

$assertoff is used to switch off assertions. We can use this systemverilog task anywhere in the testbench like classes, modules etc including UVM tests, sequences, driver, initial block of a module.

Syntax:

$assertoff[("levels" [,"hierarchical path to instance of modules or assertions "];

Where

"levels" is an optional argument which specifies the hierarchy levels below the instance name(next optional argument)

"hierarchical path to an instance of modules or assertions"> is an optional argument indicating an instance of module or assertions to be turned off

Ex- let's say,  top is the name of the top level of the testbench in which design instance mydut is instantiated. Design instance has fsm_logic instance.

$assertoff(0,top);

Level 0 => All assertions in module top and below in the hierarchy to be turned off. This essentially switches off all the assertions inside the design as the module top is the top of the testbench including the ones inside mydut and fsm_logic

$assertoff(1,top.mydut);

Level 1 => only assertions in module instance mydut will be turned off while assertions in other instances will continue to fire.

$assertoff(2,top);

Level 2 => Assertions in instance top module and one level below top module(mydut is the only module instance inside top) will be turned off.
$assertoff with no arguments turns off all assertions in all modules.
You can switch of specific assertions inside the module if the assertion has name
Ex:
Dummy property will fail if it ever fires. It is coded to fire in the first rising clock.

Use $asserton similarly with the same syntax as $assertoff

Problem with this method of enabling or disabling
• It requires the hierarchical path to module or assertion and is very painful as we go up in integration.
• Nonreusable as the hierarchy might change anytime


2) Use of Verilog Attributes to create Assertion categories and switch on/off assertions based on vendor-specific nonstandard system tasks

Attributes were created in Verilog 2001 as a way to define and attach some characteristics for tool specific usage.

Ex: While inserting DFT Mux called VISA by specific visa tool, it inserts ports with tool attribute with tool specific number
Syntax:

(* [=] *)

Where [=] is the name assigned to attribute. This constant can be string or number or both.

Simulation Vendors like Synopsis VCS provide many nonstandard tasks which will enable us with the capability to disable or enable these tool-specific features. We can categorize assertions then use these nonstandard tasks to disable or enable assertions

Ex:

(* category = 6 *)
category_example:assert property(check_something);

I have used VCS tool for simulation and hence these examples are going to be specific to VCS while the same concept can be used elsewhere with the similar approach

VCS Specific Tasks:

   Stops all assertions associated with the specified category level (an unsigned integer from 0 to 2^24– 1):

$ova_category_stop([Category number]);

  Starts all assertions associated with the specified category:

$ova_category_start([Category number]):

Note that these tasks can be used anywhere including UVM sequences, test or driver etc

The category attribute, along with $ova_category_stop and $testplusargs arguments can be used enable or disable assertions.
lets rewrite the assertion in one of the design example above with added category:

(*category=1501*)
DUMMY_ASSERT : assert property (p_dummy) `uvm_info(""design_module"", "DUMMY", UVM_HIGH) else `uvm_error("design_module", $sformatf("p_dummy failed"))

Call below function before the simulation starts anywhere in _test_base or test

function void check4sva_argument();

    int sva_category;

    if($value$plusargs("sva_disable_category_number=%0d", sva_category))

    begin

        $ova_category_stop(sva_category);

        `uvm_info(get_type_name( ), $sformatf("Turning off SVA Category=%0d",sva_category), UVM_LOW)

    end

endfunction

Formalizing SVA Categories:

There are many DUTs which might want to take benefit of this feature and the same testbench might get integrated at SOC level for reuse purpose.  There is a quite a possibility of different testbenchs end up using the same category number for different assertions which might result in a clash and hence false pass. Therefore, Formalization of these categories is must.