28 Oct Random Stability

DUT(design under test)의 크기와 복잡도가 점점 더 커짐에 따라 directed test 대비 random test 기반 검증이 더욱 중요한 역할을 맡고 있다. 이러한 constrained random verification을 통해서 보다 빠르고 효율적으로 DUT의 bug를 발견할 것으로 기대하기 때문이다.

하지만 한 가지 고려해야 하는 사항이 있다. 바로 재현가능성(reproducibility)이다. 예를 들어 nightly regression 동안 발견된 bug가 fix 되었다면, 이후 동일한 test stimulus를 재현함으로써 제대로 fix 된 것이 맞는지 확인할 필요가 있다는 뜻이다. 하지만 bug가 발견되고 fix 되기까지는 보통 RTL과 testbench가 지속적으로 업데이트 되기 마련이고, 그 과정에서 동일한 seed로 simulation을 하여도 동일한 test stimulus가 생성되지 않아 재현할 수 없는 경우도 존재한다. 이와 관련된 SystemVerilog의 속성을 바로 random stability라고 한다. 이를 통해 어떤 경우에 재현이 불가능하며 어떻게 하면 재현이 가능한 상태를 유지할 수 있는지 등에 대해 알아보자.

Initialization RNG

SystemVerilog의 structural element, 즉, module, interface, program, package는 모두 initialization RNG(random number generator)라는 것을 갖는다. Initialization RNG는 simulator의 command line 옵션으로 전달되는 seed에 의해 결정되며, structural element 내에서 thread 또는 object를 생성할 때 사용된다. Cadence Xcelium의 경우 -svseed, Synopsys VCS의 경우 +ntb_random_seed, Siemens Questa의 경우 -sv_seed 옵션이 사용된다.

RNG는 기본적으로 deterministic 특성을 가진다. 즉, seed가 정해지면 RNG는 항상 동일한 random sequence를 생성한다. 이는 random stability를 위한 매우 중요한 특성이다. 설명의 편의를 위해 seed가 S₀일 때, initialization RNG는 S₁, S₂, S₃, …의 순서로 random sequence를 생성한다고 가정한다.

Hierarchical Seeding

SystemVerilog에서 thread는 각각의 독립적인 RNG를 갖는다. 다시 말하면 module과 같은 structural element에서 always block, initial block 등에 의해 새로운 thread가 생성되면 각 thread는 자신의 고유 RNG를 가지게 되며 이 RNG는 해당 thread가 생성된 structural element의 다음 random 값을 seed로 초기화된다. 예를 들어 아래 그림의 첫 번째 module에서 가장 먼저 생성된 thread가 always block일 경우 해당 thread의 RNG는 S₁을 seed로 한다. 이후 생성된 initial block은 그 다음 random 값인 S₂를 seed로 하는 RNG를 갖는다. 만약 initial block에서 fork–join을 통해 또 새로운 두 개의 thread를 생성하는 경우 역시 그 다음 random 값인 S_3, S₄ 순으로 RNG의 seed가 결정된다. 두 번째 module에서도 thread 생성 순서에 따라 S_1, S₂ 순으로 seed가 사용된다. SystemVerilog의 이러한 seeding 방식을 hierarchical seeding이라고 부른다.

Object 역시 thread와 마찬가지의 seeding 방식을 따른다. new를 통해 생성된 object의 RNG는 object가 속한 thread가 생성될 때 사용된 seed의 다음 random 값을 seed로 사용한다.

단, SystemVerilog LRM에 기술된 hierarchical seeding 방식에 대한 내용은 모호한 부분이 있어 실제 EDA vendor별로 simulator를 구현하는 방식에도 차이가 존재한다. 따라서 LRM 해석 방식에 따른 차이는 배제하고 hierarchical seeding에 대한 개념적 이해가 가능한 수준으로 작성하였음에 유의하자. 참고로 아래 첨부된 simulation log는 모두 Cadence Xcelium 기반으로 얻은 결과다.

Thread Stability and Object Stability

위에서 언급한 바와 같이 thread는 각각의 독립적인 RNG를 가지므로 thread 생성 순서와 $urandom, $urandom_range 등에 의한 random number generation 순서를 변경하지 않으면 thread stability를 유지할 수 있다. 마찬가지로 object도 각각의 독립적인 RNG를 가지므로 object와 thread 생성 순서 그리고 randomize에 의한 random number generation 순서를 변경하지 않으면 object stability를 유지할 수 있다.

먼저 아래의 간단한 예제를 살펴보자. Example 1-1에서는 세 개의 thread를 생성하고 각 thread 내에서 random number generation을 수행한다. Example 1-2에서는 하나의 thread를 추가함으로써 thread 생성 순서에 변화가 발생하였다. Thread 생성 순서가 변화되었으므로 각 thread RNG의 seed가 변경되고 그에 따라 출력되는 결과값 역시 변경되는 것을 확인할 수 있다. 자세히 보면 마치 결과값이 shift 된 것처럼 나타나는데 이는 새롭게 추가된 thread에 의해 해당 initialization RNG가 한 번 소모되었기 때문이다. 참고로 각 thread는 동일 시간에 처리된다고 생각되지만 실제로는 순차적으로 처리되며 처리 순서는 simulator별로 상이할 수 있다.

// Example 1-1
module top;

  initial $display("#1 %h", $urandom());
  initial $display("#2 %h", $urandom());
  initial $display("#3 %h", $urandom());

endmodule: top

#1 889db611
#2 96fe402d
#3 83231206

// Example 1-2
module top;

  initial $display("oops"); // added
  initial $display("#1 %h", $urandom());
  initial $display("#2 %h", $urandom());
  initial $display("#3 %h", $urandom());

endmodule: top

oops
#1 96fe402d
#2 83231206
#3 161e432c

다음 예제에서는 한 module 내에서 두 개의 thread가 생성되며 각 thread 내에서 세 개의 변수에 random 값을 할당 후 결과값을 출력한다. Example 2-2가 Example 2-1과 다른 점은 첫 번째 initial block 시작 시점에 추가적으로 random number generation이 수행된다는 점이다. Thread 내에서 random number generation 순서가 변경되었기 때문에 변수 a, b, c의 값이 변경되었음을 확인할 수 있다. 이는 변수 oops의 의해 thread RNG가 한 번 소모되었기 때문이며 변수 oops를 출력해본다면 889db611의 값을 가질 것이다. 반면 나머지 thread의 경우 이에 영향을 받지 않고 x, y, z의 값이 동일하게 출력된다.

// Example 2-1
module top;
  
  int a, b, c;
  int x, y, z;
  
  // thread
  initial begin
    a = $urandom();
    b = $urandom();
    c = $urandom();
    $display("a = %h / b = %h / c = %h", a, b, c);
  end
  
  // another thread
  initial begin
    x = $urandom();
    y = $urandom();
    z = $urandom();
    $display("x = %h / y = %h / z = %h", x, y, z);
  end
  
endmodule: top

a = 889db611 / b = 1dd8bf3b / c = a572204a
x = 96fe402d / y = 10f79f21 / z = c64e608c

// Example 2-2
module top;
  
  int oops;
  int a, b, c;
  int x, y, z;
  
  // thread
  initial begin
    oops = $urandom(); // added
    a = $urandom();
    b = $urandom();
    c = $urandom();
    $display("a = %h / b = %h / c = %h", a, b, c);
  end
  
  // another thread
  initial begin
    x = $urandom();
    y = $urandom();
    z = $urandom();
    $display("x = %h / y = %h / z = %h", x, y, z);
  end
  
endmodule: top

a = 1dd8bf3b / b = a572204a / c = 6705a5ce
x = 96fe402d / y = 10f79f21 / z = c64e608c

Manual Seeding

Thread/object 생성 순서, random number generation 수행 순서를 변경하지 않음으로써 random stability를 유지할 수도 있지만 이를 항상 지키는 것은 쉽지 않다. 많은 사람이 함께 testbench를 개발하는 큰 프로젝트의 경우 특히 어려운 일이다. Random stability를 유지하는 또 하나의 방법으로 manual seeding 방식이 있다. 각 thread RNG와 object RNG의 seed를 직접 설정하는 방식이며 srandom 또는 set_randstate에 의해 설정 가능하다. get_randstate와 set_randstate에 대한 내용은 생략한다.

module top;
  
  class C;
  endclass: C
  
  C c;
  
  initial begin
    process::self.srandom(100); // manual seeding a thread
  end
  
  initial begin
    c = new();
    c.srandom(200); // manual seeding an object
  end
  
endmodule: top

Random Stability in UVM

UVM은 기본적으로 random stability 향상을 위해 SystemVerilog seeding 방식을 사용하지 않고 자체 UVM seeding 방식을 사용한다. Seeding 방식은 use_uvm_seeding 변수를 설정함으로써 control 가능하다.

virtual class uvm_object extends uvm_void;

  // ...

  // Group: Seeding

  // Variable: use_uvm_seeding
  //
  // This bit enables or disables the UVM seeding mechanism. It globally affects
  // the operation of the reseed method. 
  //
  // When enabled, UVM-based objects are seeded based on their type and full
  // hierarchical name rather than allocation order. This improves random
  // stability for objects whose instance names are unique across each type.
  // The <uvm_component> class is an example of a type that has a unique
  // instance name.

  static bit use_uvm_seeding = 1;

  // ...
    
endclass

UVM seeding 방식을 사용하는 경우 reseed 함수로 call 되어 각 component, sequence, sequence item의 type, full instance hierarchy name 그리고 global seed 정보를 입력으로 하는 hashing algorithm을 통해 각각의 unique seed 생성 후 manual seeding을 수행한다. 따라서 thread, component, sequence, sequence item 등의 순서에 영향을 최소화 할 수 있다.

function void uvm_object::reseed ();
  if(use_uvm_seeding)
    this.srandom(uvm_create_random_seed(get_type_name(), get_full_name()));
endfunction

function int unsigned uvm_create_random_seed ( string type_id, string inst_id="" );
  uvm_seed_map seed_map;

  if(inst_id == "")
    inst_id = "__global__";

  if(!uvm_random_seed_table_lookup.exists(inst_id))
    uvm_random_seed_table_lookup[inst_id] = new;
  seed_map = uvm_random_seed_table_lookup[inst_id];

  type_id = {uvm_instance_scope(),type_id};

  if(!seed_map.seed_table.exists(type_id)) begin
    seed_map.seed_table[type_id] = uvm_oneway_hash ({type_id,"::",inst_id}, uvm_global_random_seed);
  end
  if (!seed_map.count.exists(type_id)) begin
    seed_map.count[type_id] = 0;
  end

  //can't just increment, otherwise too much chance for collision, so 
  //randomize the seed using the last seed as the seed value. Check if
  //the seed has been used before and if so increment it.
  seed_map.seed_table[type_id] = seed_map.seed_table[type_id]+seed_map.count[type_id]; 
  seed_map.count[type_id]++;
  
  return seed_map.seed_table[type_id];
endfunction

하지만 UVM seeding 방식도 완벽하지는 않다. 예를 들어 component의 class name 또는 instance name을 변경하게 되면 hashing algorithm의 입력이 바뀌므로 seed가 영향을 받게 된다. 뿐만 아니라, UVM 버전에 따라 random stability 관련 문제가 있는 부분도 존재한다.

References

• http://ieeexplore.ieee.org/document/8299595
• http://staging.doulos.com/knowhow/systemverilog/random-stability-in-systemverilog/
• https://www.systemverilog.io/random-stability
• https://s3.amazonaws.com/verificationacademy-news/DVCon2012/Papers/MGC_DVCon_12_UVM_Random_Stability_Don%27t_Leave_it_to_Chance.pdf
• https://iksciting.com/random-vs-urandom/