Category Archives: Randomization

Constrained Random Using Code Patterns

Having functions that do randomization is not constrained random. Instead, OSVVM creates a constrained random test environment by using code patterns in conjunction with randomization. This post shows a number of code patterns.

Weighted Sequences

The following example uses DistInt to generate the first test sequence 70% of the time, the second 20%, and the third 10%.

variable RV : RandomPType ;
. . . 
StimGen : while TestActive loop     -- Repeat until done
  case RV.DistInt( (7, 2, 1) ) is   
    when 0 =>  -- Normal Handling   -- 70%
       . . . 
    when 1 =>  -- Error Case 1      -- 20%
       . . . 
    when 2 =>  -- Error Case 2      -- 10%
       . . . 
    when others =>  
      report "DistInt" severity failure ;  -- Signal bug in DistInt
  end case ; 
end loop ;

Randomizing a Sequence Order

The following code segment generates the transactions for writing to DMA_WORD_COUNT, DMA_ADDR_HI, and DMA_ADDR_LO in a random order that is different every time this code segment is run. The sequence finishes with a write to DMA_CTRL. When DistInt is called with a weight of 0, the corresponding value does not get generated. Hence by initializing all of the weights to 1 and then setting it to 0 when it is selected, each case target only occurs once. The “for loop” loops three times to allow each transaction to be selected.

variable RV : RandomPType ;
. . . 
Wt0 := 1;  Wt1 := 1;  Wt2 := 1;  -- Initial Weights

for i in 1 to 3 loop             -- Loop 1x per transaction

  case RV.DistInt( (Wt0, Wt1, Wt2) ) is  -- Select transaction

    when 0 =>                    -- Transaction 0
      CpuWrite(CpuRec, DMA_WORD_COUNT, DmaWcIn);  
      Wt0 := 0 ;                 -- remove from randomization

    when 1 =>                    -- Transaction 1 
      CpuWrite(CpuRec, DMA_ADDR_HI, DmaAddrHiIn); 
      Wt1 := 0 ;                 -- remove from randomization

    when 2 =>                    -- Transaction 2 
      CpuWrite(CpuRec, DMA_ADDR_LO, DmaAddrLoIn); 
      Wt2 := 0 ;                 -- remove from randomization

    when others =>   report "DistInt" severity failure ;

  end case ; 
end loop ;

CpuWrite(CpuRec, DMA_CTRL, START_DMA or DmaCycle);

Non-repeating Values

The following code segment uses an exclude list to keep from repeating the last value.  When passing an integer value to an integer_vector parameter, an aggregate using named association “(0=> LastDataInt)” is used to denote a single element array. During the first execution of this process, LastDataInt has the value integer’left (a very small number), which is outside the range 0 to 255, and as a result, has no impact on the randomization.

RandomGenProc : process
  variable RV : RandomPType ; 
  variable DataInt, LastDataInt : integer ;
begin
  . . .  
  DataInt := RV.RandInt(0, 255, (0 => LastDataInt)) ; 

  LastDataInt := DataInt;
  . . .

The following code segment uses an exclude list to keep from repeating the four previous values.

RandProc : process
  variable RV : RandomPtype ; 
  variable DataInt : integer ; 
  variable Prev4DataInt : integer_vector(3 downto 0) := (others => integer'low) ;
begin
  . . .  
  DataInt := RV.RandInt(0, 100, Prev4DataInt) ; 

  Prev4DataInt := Prev4DataInt(2 downto 0) & DataInt ; 
  . . .

Randomization and Heuristics

Some test cases use heuristics to generate an appropriate sequence of actions. The following test generates random traffic to the FIFO by using heuristics (guesses) at length of bursts of data and delays between bursts of data.

variable RV : RandomPType ; 
. . .  
TxStimGen : while TestActive loop  
  -- Burst between 1 and 10 values
  BurstLen := RV.RandInt(Min => 1, Max => 10);
  for i in 1 to BurstLen loop 
    DataSent := DataSent + 1 ; 
    WriteToFifo(DataSent) ; 
  end loop ;
  --  Delay between bursts: (BurstLen <=3: 1-6, >3: 3-10) 
  if BurstLen <= 3 then 
    BurstDelay := RV.RandInt(1, 6) ;  -- small burst, small delay
  else
    BurstDelay := RV.RandInt(3, 10) ; -- bigger burst, bugger delay
  end if ; 
  wait for BurstDelay * tperiod_Clk - tpd ;
  wait until Clk = '1' ;
end loop TxStimGen ;

Summary

In OSVVM, code patterns plus calls to randomization functions are used to create a constrained random test.  While OSVVM does not provide a solver, using code does an adequate job for constrained random.

In fact, most constrained random tests are problematically slow.  This occurs because randomization is only uniform over large quantities of randomizations.  Verification on the other hand typically only requires 1 or 2 of each unique test sequence.   As a result, using randomization to generate N unique test cases requires O(N*Log N) randomizations.

To avoid generating “log N” extra test cases, OSVVM uses Intelligent Coverage™ randomization as its primary method of randomization. Intelligent Coverage™ is an Intelligent Testbench methodology that can does a random walk across the functional coverage model. As a result, closure of the functional coverage model using Intelligent Coverage is significantly faster than constrained random – even if using a constraint solver.  For more see blog post, “Intelligent Coverage basics.”

RandomPkg Usage Basics: Protected Types, Seeds, and Randomization

The Basics

RandomPkg implements its randomization capability using a protected type, named RandomPType. Using a protected type allows the seed to be stored internal to the protected type, which in turn allows randomization to be done using functions.

To use RandomPkg, first you must reference the OSVVM library and RandomPkg as shown below.

library osvvm ; 
    use osvvm.RandomPkg.all ; 
entity tb is 

To do randomization, a process must declare its own local randomization variable as shown below.

UartTxProc : process
  variable RV : RandomPType ;   -- randomization variable
begin

Each process doing randomization needs its own randomization variable with a unique seed value. One easy way to do this is to name the process and use RV’instance_name (or RV’path_name) as a parameter to InitSeed. Using the instance_name or path_name gives each seeds a unique name – even when there are multiple instances of a stimulus generation component.

RV.InitSeed (RV'instance_name)  ; 

Randomization is done with one of the overloaded functions, such as RandInt.

RandInt := RV.RandInt(0, 255) ;

Putting all of the pieces together results in the following process.

UartTxProc : process
  variable RV : RandomPType ;                   -- protected type from RandomPkg
begin
  RV.InitSeed (RV'instance_name)  ;              -- Generate initial seeds
  for i in 0 to 255*6 loop 
    do_transaction(…, RV.RandInt(0, 255), …) ;  -- random value between 0 and 255

Note the calls to protected type methods (subprograms) include the protected type variable (RV) within the call (such as RV.RandInt(0, 255)).

Seeds and Repeatability

RandomPkg uses ieee.math_real.uniform as its basis for randomization. With uniform (or any other pseudo random sequence generator), when the same seed value is used, the same sequence, and hence, the same test is produced. This is an important fact for testing since when we fix a bug, we need to repeat the same sequence to verify the bug has been fixed.

On the other hand, we do not want two processes to repeat the same values and/or sequences when testing. Hence, we need to ensure that each process has its own randomization variable and is initialized with a unique seed value.

Stability and Random Variables

Stability is about being able rerun a test and get the exact same results. Stability is essential.

When each process has its own local variable for randomization, then each process will always produce the same sequence and the test will be stable.

On the other hand, if the randomization object is a shared variable and it is shared by many separate processes, the test will not be stable. In this case, two or more processes can randomize a value during the same delta cycle. Hence if process execution order were to change, the order of randomization would change, the randomized values would change, and the test would change. Process execution order within a given delta cycle is not defined by the language and can change due to compilation or optimization. Hence, in this situation, fixing a bug can result in the test producing different stimulus.

OSVVM Randomization: Normal, Poisson, FavorBig, FavorSmall distributions

Most of the randomizations in RandomPkg are based on a uniform distributions. RandomPkg also supports the distributions, normal, poisson, FavorBig and FavorSmall. The following is the overloading for these functions.

-- Generate values, each with an equal probability
impure function Uniform (Min, Max : in real) return real ;
impure function Uniform (Min, Max : integer) return integer ;
impure function Uniform (Min, Max : integer ; Exclude: integer_vector) return integer ;

-- Generate more small numbers than big
impure function FavorSmall (Min, Max : real) return real ;
impure function FavorSmall (Min, Max : integer) return integer ;
impure function FavorSmall(Min, Max: integer; Exclude: integer_vector) return integer ;

-- Generate more big numbers than small
impure function FavorBig (Min, Max : real) return real ;
impure function FavorBig (Min, Max : integer) return integer ;
impure function FavorBig (Min, Max : integer ; Exclude: integer_vector) return integer ;

-- Generate normal = gaussian distribution
impure function Normal (Mean, StdDeviation : real) return real ;
impure function Normal (Mean, StdDeviation, Min, Max : real) return real ;
impure function Normal (
      Mean          : real ;
      StdDeviation  : real ;
      Min           : integer ;
      Max           : integer ;
      Exclude       : integer_vector := NULL_INTV
) return integer ;

-- Generate poisson distribution
impure function Poisson (Mean : real) return real ;
impure function Poisson (Mean, Min, Max : real) return real ;
impure function Poisson (
      Mean          : real ;
      Min           : integer ;
      Max           : integer ;
      Exclude       : integer_vector := NULL_INTV
) return integer ;

The package also provides experimental mechanisms for changing the distributions used with functions RandInt, RandSlv, RandUnsigned, and RandSigned.

Weighted Randomization

1. Simple Weighting

A weighted distribution randomly generates a value (within a predetermined range) a specified percentage of the time. DistInt is a weighted distribution that specifies a weight and uses the corresponding index value of the weight as the value to be selected for randomization. Hence, the input to DistInt is an integer_vector of weights. The return value is the index of the selected weight. For a literal value, it will return a value from 0 to N-1 where N is the number of weights specified. The frequency that each value will occur is weight/(sum of weights). As a result, in the following call to DistInt the likelihood of a 1 to occur is 7/10 times or 70%. The likelihood of 3 is 20% and 5 is 10%.

variable RV : RandomPType ;
variable DataInt1, DataInt2 : integer ; 
. . . 
DataInt1 := RV.DistInt( (7, 2, 1) ) ;

Weighted distributions also support an exclude vector. The following code excludes the last value generated:

. . .
DataInt2 := RV.DistInt( (1, 2, 4, 8, 16, 32), (1 => DataInt2)) ;

2. Weights plus Values

DistIntVal allows the specification of a value and a weight. DistValInt is called with an array of value pairs. The first item in the pair is the value and the second is the weight. The frequency that each value will occur is weight/(sum of weights). As a result, in the following call to DistValInt, the likelihood of a 0 is 70%, 1 is 20% and 2 is 10%.

variable RV : RandomPType ;
variable DataInt1, DataInt2 : integer ; 
. . . 
-- Generate 1 70%,  3 20%, and 5 10% of the time
DataInt1 := RV.DistValInt(  ((1, 7), (3, 2), (5, 1)) ) ;
. . . 
-- Generate 1, 3, 5, 7 each 25% of the time and skip the previously generated value.
DataInt2 := RV.DistValInt(  ((1, 25), (3, 25), (5, 25), (7, 25)), (1 => DataInt2) ) ;

Basic Randomization in OSVVM

1. Randomizing Integers

The basic randomization generates an integer value that is either within some range or within a set of values. The set of values and exclude values are all of type integer_vector (defined in VHDL-2008). The examples below show the basic randomization overloading. When a value of integer_vector is specifed, the extra set of parentheses denote that it is an aggregate value.

RandomGenProc : process
  variable RV      : RandomPType ;         -- protected type from RandomPkg
  variable DataInt : integer ;
begin
  RV.InitSeed (RV'instance_name)  ;         -- Generate initial seeds

  -- Generate a value in range 0 to 255
  DataInt := RV.RandInt(0, 255) ; 
  . . . 
  -- Generate a value in range 1 to 9 except exclude values 2,4,6,8
  DataInt := RV.RandInt(1, 9, (2,4,6,8)) ; 
  . . . 
  -- Generate a value in set 1,3,5,7,9
  DataInt := RV.RandInt( (1,3,7,9) ) ;  -- note two sets of parens required
  . . . 
  -- Generate a value in set 1,3,5,7,9 except exclude values 3,7
  DataInt := RV.RandInt((1,3,7,9), (3,7) ) ; 

The overloading for the RandInt functions is as follows.

impure function RandInt (Min, Max : integer) return integer ;
impure function RandInt (Min, Max: integer; Exclude: integer_vector) 
    return integer ;
impure function RandInt ( A : integer_vector ) return integer ;
impure function RandInt ( A : integer_vector; Exclude: integer_vector) 
    return integer ;

2. Randomizing std_logic_vector, unsigned and signed

These same functions are available for types std_logic_vector(RandSlv), unsigned (RandUnsigned) and signed (RandSigned). Note that parameter values are still specified as integers and there is an additional value used to specify the size of the value to generate. For example, the following call to RandSlv defines the array size to be 8 bits.

process
  variable DataSlv : std_logic_vector(7 downto 0) ;
begin
  . . . 
  -- Generate a value in range 0 to 255
  DataSlv := RV.RandSlv(0, 255, 8) ; 
  . . . 
  -- Generate a value in range 1 to 9 except exclude values 2,4,6,8
  DataSlv := RV.RandSlv(1, 9, (2,4,6,8), 8) ; 
  -- Generate a value in set 1,3,5,7,9
  DataSlv := RV.RandSlv( (1,3,7,9), 8 ) ;  -- note two sets of parens required
  . . . 
  -- Generate a value in set 1,3,5,7,9 except exclude values 3,7
  DataSlv := RV.RandSlv((1,3,7,9), (3,7), 8 ) ; 

The overloading for RandSlv is as shown below. RandUnsigned and RandSigned have the same overloading.

impure function RandSlv (Min, Max, Size : natural) return std_logic_vector ; 
impure function RandSlv (Min, Max : natural ; Exclude: integer_vector ; Size : natural)  return std_logic_vector ;
impure function RandSlv 
    (A: integer_vector ; size : natural ) return std_logic_vector ;
impure function RandSlv (A: integer_vector ; Exclude: integer_vector ; Size : natural)  return std_logic_vector ;

3. Randomizing Real

The function, RandReal supports randomization for type real. The function with a range, like the procedure Uniform, never generates its end values. RandReal has the following overloading:

impure function RandReal ( Min, Max : real ) return real ;
impure function RandReal ( A : real_vector ) return real ;
impure function RandReal ( A, Exclude : real_vector ) return real ;

4. Randomizing Time

The function, RandTime supports randomization for type time. RandTime supports the same overloading as RandInt. These are shown below:

impure function RandTime (Min, Max : time ; Unit : time := ns) return time ;
impure function RandTime 
   (Min, Max : time ; Exclude : time_vector ; Unit : time := ns) return time ;
impure function RandTime (A : time_vector) return time ;
impure function RandTime (A, Exclude : time_vector) return time ;

OSVVM™ Webinar + World Tour Dates

Webinar Thursday June 26, 2014
OSVVM provides functional coverage and randomization utilities that layer on top of your transaction level modeling (tlm) based VHDL testbench. Using these you can create either basic Constrained Random tests or more advanced Intelligent Coverage based Random tests.  This simplified approach allows you to utilize advanced randomization techniques when you need them and easily mix advanced randomization techniques with directed, algorithmic, and file-based test generation techniques.  Best of all, OSVVM is free and works in most VHDL simulators.

Europe Session 3-4 pm CEST 6-7 am PDT 9-10 am EDT Enroll with Aldec
US Session 11 am-12 Noon PDT 2-3 pm EDT 8-9 pm CEST Enroll with Aldec
 

OSVVM World Tour Dates
VHDL Testbenches and Verification – OSVVM+ Boot Camp
Learn the latest VHDL verification techniques including transaction level modeling (tlm), self-checking, scoreboards, memory modeling, functional coverage, directed, algorithmic, constrained random, and intelligent testbench test generation. Create a VHDL testbench environment that is competitive with other verification languages, such as SystemVerilog or ‘e’. Our techniques work on VHDL simulators without additional licenses and are accessible to RTL engineers.

July 14-18 Munich, Germany Enroll with eVision Systems
July 21-25 Bracknell, UK Enroll with FirstEDA
August 18-22 and September 2-5 online class Enroll with SynthWorks
August 25-29 Portland, OR (Tigard/Tualatin) Enroll with SynthWorks
September 15-19 Gothenburg, Sweden Enroll with FirstEDA
October 20-24 Bracknell, UK Enroll with FirstEDA
October 27-31 and November 10-14 online class Enroll with SynthWorks
November 17-21 Baltimore, MD (BWI Area) Enroll with SynthWorks
December 1-5 and December 17-21 online class Enroll with SynthWorks
 

Presented by:
Jim Lewis, SynthWorks VHDL Training Expert, IEEE 1076 Working Group Chair, and OSVVM Chief Architect

OSVVM’s Intelligent Coverage is 5X or More Faster than SystemVerilog’s Constrained Random

If the measure of test case generation was a large number of well randomized test cases, SystemVerilog and UVM would be on par with VHDL’s OSVVM.  However the true measure of test case generation is functional coverage closure – all test cases identified in the test plan are done.  Functional coverage closure is a big challenge for constrained random approaches to verification as used in SystemVerilog or ‘e’.  On the other hand, functional coverage closure is the focus of OSVVM’s Intelligent Coverage™.   This article takes a look at why Constrained Random has challenges and how Intelligent Coverage solves it.

1. Constrained Random Repeats Test Cases

In my post, Functional Coverage Made Easy with VHDL’s OSVVM, we used randomization with a uniform distribution (shown below) to select the register pairs for the ALU. Constrained random at its best produces a uniform distribution. As a result, this example is a best case model of constrained random tests.

Src1 := RV.RandInt(0, 7) ; -- Uniform Randomization
Src2 := RV.RandInt(0, 7) ;

The problem with constrained random testbenches is that they repeat some test cases before generating all test cases. In general to generate N cases, it takes “N * log N” randomizations. The “log N” represents repeated test cases and significantly adds to simulation run times. Ideally we would like to run only N test cases.

Running the previous ALU testbench, we get the following coverage matrix when the code completes. Note that some case were generated 10 time before all were done at least 1 time. It took 315 randomizations to generate all 64 unique pairs. This is slightly less than 5X more iterations than the 64 in the ideal case. This correlates well with theory as 315 is approximately 64 * log(64). By changing the seed value, the exact number of randomizations may increase or decrease but this would be a silly way to try to reduce the number of iterations a test runs.

UniformCoverage

2. Intelligent Coverage

“Intelligent Coverage” is a coverage driven randomization approach that randomly selects a hole in the functional coverage and passes it to the stimulus generation process. Using “Intelligent Coverage” allows the stimulus generation to focus on missing coverage and reduces the number of test cases generated to approach the ideal of N randomizations to generate N test cases.

Lets return to the ALU example. The Intelligent Coverage methodology starts by writing functional coverage. We did this in the previous example too. Next preliminary stimulus is generated by randomizing using the functional coverage model. In this example, we will replace the call to RandInt (uniform randomization) with a call to RandCovPoint (one of the Intelligent Coverage randomization methods). This is shown below. In this case, Src1 and Src2 are used directly in the test, so we are done.

architecture Test3 of tb is
  shared variable ACov : CovPType ;  -- Declare 
begin
  TestProc : process 
    variable RV : RandomPType ;
    variable Src1, Src2 : integer ;
  begin
    -- create coverage model
    ACov.AddCross( GenBin(0,7), GenBin(0,7) );  -- Model

    while not ACov.IsCovered loop    -- Done?
      (Src1, Src2) := ACov.RandCovPoint ; -- Intelligent Coverage Randomization

      DoAluOp(TRec, Src1, Src2) ;    -- Transaction
      ACov.ICover( (Src1, Src2) ) ;  -- Accumulate
    end loop ;

    ACov.WriteBin ;  -- Report 
    EndStatus(. . . ) ;   
  end process ;

When randomizing across a cross coverage model, the output of RandCovPoint is an integer_vector. Instead of using the separate integers, Src1 and Src2, it is also possible to use an integer_vector as shown below.

variable Src : integer_vector(1 to 2) ;
. . . 
Src := ACov.RandCovPoint ;      -- Intelligent Coverage Randomization

The process is not always this easy. Sometimes the value out of RandCovPoint will need to be further shaped by the stimulus generation process.  We do this in our VHDL Testbenches and Verification class.

The Intelligent Coverage methodology works now and works with your current testbench approach. You can adopt this methodology incrementally. Add functional coverage today to make sure you are executing all of your test plan. For the tests that need help, use the Intelligent Coverage.

3. Intelligent Testbenches in SystemVerilog

With SystemVerilog you can certainly buy a simulator that implements Intelligent Testbenches. However, this is a signification upgrade, so it will cost. In addition using an intelligent testbench tool tends to require vendor specific coding – so you are locked into a particular vendor.

On the other hand, with VHDL’s OSVVM, the Intelligent Testbench capability is built into the functional coverage modeling.  It is free.  All of the customizations to the randomization are done by writing VHDL code and initiating transactions.

4. References

Here are a couple of articles on Intelligent Testbench approaches that also remove or reduce the repetition of test cases. However, these solutions are not free like OSVVM.

Wally Rhines. From Volume to Velocity. DVCon Keynote March 2011

Mark Olen. Intelligent Testbench Automation Delivers 10X to 100X Faster Functional Verification. Verification Horizons Blog June 2011

Brian Bailey. Enough of the sideshows – it’s time for some real advancement in functional verification! EDA DesignLine Blog May 2012

OSVVM, VHDL’s Leading-Edge Verification Methodology

At its lowest level, Open Source VHDL Verification Methodology (OSVVM) is a set of VHDL packages that simplify implementation of functional coverage and randomization.  OSVVM uses these packages to create an Intelligent Coverage verification methodology that is a step ahead of other verification methodologies, such as SystemVerilog’s UVM.

Continues on the OSVVM static page:  http://www.synthworks.com/blog/osvvm/