Constraint to have N elements distributed in M bins

Code to distribute N elements into M bins, you add unique keyword to have each bin will have unique number of elements.

class test;
  parameter int M = 5;
  parameter int N = 100;
  rand bit[31:0] arr[M];
  
  constraint c_arr { arr.sum() == N; foreach(arr[i]) { arr[i] inside {[0:N-1]}; } unique {arr}; }
  
  function void post_randomize();
    foreach(arr[i])
    $display("Array[%01d]:%02d\n",i,arr[i]);
  endfunction
  
endclass

module top;
  test t;
  
  initial begin
    t = new;
    void'(t.randomize());
  end
endmodule

RESULT:

Compiler version U-2023.03-SP2_Full64; Runtime version U-2023.03-SP2_Full64; Sep 17 10:38 2024
Array[0]:23

Array[1]:01

Array[2]:10

Array[3]:11

Array[4]:15

Array[5]:21

Array[6]:14

Array[7]:03

Array[8]:02

Array[9]:00

V C S S i m u l a t i o n R e p o r t
Time: 0 ns
CPU Time: 0.430 seconds; Data structure size: 0.0Mb
Tue Sep 17 10:38:13 2024

KNIGHT TOUR in System Verilog

Following is the SV code for knight tour. On each randomisation, we get the next position of knight.

The concept is simple, based on which we derived the constraints.

1. knight should operate within boundaries of the chess board.
2. knight can move on any direction if it does not violate point (1).
3. The position of the knight can be taken as row, col.
4. At best it can move in 8 directions
1. If row is incremented/decremented by 2 positions, column can move 1 position from the latest row pos.
2. If row is incremented/decremented by 1 position, column can move 2 position from the latest row pos.
5. The position is calculated based on the board length, current row and column.

NOTE:

I'll check if we can walk with the knight on the chess board without repeating the same chess square again.

I doubt that there might some limitations to achieve this.

I'll  update on it, as and when I get some clues ...

CODE:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

class knight_walk; parameter int N = 5; int row; int col; rand int next_row; rand int next_col; rand int pos; function new (); row = $urandom_range(0,N-1); col = $urandom_range(0,N-1); pos = N*row + col; $display(" INITIAL POS:%0d ROW:%0d COL:%0d",pos,row,col); endfunction constraint c_knight { solve next_row before next_col; next_row inside { row+2,row-2,row+1,row-1 }; next_col inside { col+2,col-2,col+1,col-1 }; next_row inside {[0:4]}; next_col inside {[0:4]}; if( next_row inside {row+2,row-2} ) { next_col inside {col+1,col-1}; } else { next_col inside {col+2,col-2}; } } function void post_randomize(); row = next_row; col = next_col; pos = row*N+col; $display("POST_RANDOMIZE:: POS:%0d ROW:%0d COL:%0d",pos,row,col); endfunction endclass: knight_walk module top; knight_walk chess; initial begin chess = new; repeat(4) void'(chess.randomize()); end endmodule: top

RESULTS:

Compiler version S-2021.09; Runtime version S-2021.09; Apr 22 04:34 2023
INITIAL POS:3 ROW:0 COL:3
POST_RANDOMIZE:: POS:12 ROW:2 COL:2
POST_RANDOMIZE:: POS:19 ROW:3 COL:4
POST_RANDOMIZE:: POS:8 ROW:1 COL:3
POST_RANDOMIZE:: POS:1 ROW:0 COL:1
POST_RANDOMIZE:: POS:8 ROW:1 COL:3
POST_RANDOMIZE:: POS:1 ROW:0 COL:1
POST_RANDOMIZE:: POS:8 ROW:1 COL:3
POST_RANDOMIZE:: POS:1 ROW:0 COL:1
POST_RANDOMIZE:: POS:8 ROW:1 COL:3
POST_RANDOMIZE:: POS:11 ROW:2 COL:1
V C S S i m u l a t i o n R e p o r t

SELECTING NON-OVERLAPPING MEMORY BANKS FROM A MEMORY

 PROBLEM STATEMENT:

• Suppose you have a memory of depth = 100, you are tasked to generate 4 memory banks of size =10.
• Condition, memory banks must be non-overlapping.

ANALYSIS:

1. The trick here is not get carried by the simplicity of the question and start coding away.
2. The question though sounds easy at first, will get complicated when you start coding the constraints.
3. We should first start with marking boundary for the banks
4. In this case we started with first bank and made sure that the start address is always between 0-60
5. why 60 ? The answer is simple, memory depth is 100, number of banks are 4, and size of each bank is 10. Therefore if the start address of first bank is <= 60, we can have rest of the banks in the other remaining locations. There won't be an overflow.
6. Once the start address of first bank is generated, it is easy to mark the end address, start_address+bank_size-1
7. The start address for the second bank must be greater than the end address of first bank and the range must be between 0:70. Reason? Similar to point (5).
8. The other 2 banks follow the suite.
9. Now comes the question of limiting the position of each bank, first bank always occupy the lower locations and last one will occupy higher locations.
10. This can be solved by simply shuffling the queue/array in which we store the start_address during post_randomization().
11. There can be many other ways to write the constraint, but I found this quite simple and will not stress of the constraint solver.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

class mem_banks; parameter MEMORY = 100; parameter BANK_SIZE = 10; parameter NO_OF_BANKS = 4; rand bit [31:0] addr_min[NO_OF_BANKS]; rand bit [31:0] addr_max[NO_OF_BANKS]; int total_mem = BANK_SIZE * NO_OF_BANKS; constraint a_addr { foreach (addr_min[i]) { if(i==0) addr_min[i] inside {[0:(MEMORY-total_mem)]}; else { addr_min[i] inside {[0:(MEMORY-total_mem)+(BANK_SIZE*i)]}; addr_min[i] > addr_max[i-1]; } addr_max[i] == addr_min[i]+BANK_SIZE-1; } } function void post_randomize(); addr_min.shuffle(); foreach(addr_min[i]) $display("ADDR_MIN:%d ADDR_MAX:%d",addr_min[i],addr_min[i]+BANK_SIZE-1); endfunction: post_randomize endclass: mem_banks module top; mem_banks m; initial begin m = new; repeat(2) begin void'(m.randomize()); $display("======================================"); end end endmodule: top

RESULTS:

Chronologic VCS simulator copyright 1991-2021
Contains Synopsys proprietary information.
Compiler version S-2021.09; Runtime version S-2021.09; Jan 26 09:47 2023
ADDR_MIN: 5 ADDR_MAX: 14
ADDR_MIN: 69 ADDR_MAX: 78
ADDR_MIN: 39 ADDR_MAX: 48
ADDR_MIN: 15 ADDR_MAX: 24
======================================
ADDR_MIN: 90 ADDR_MAX: 99
ADDR_MIN: 40 ADDR_MAX: 49
ADDR_MIN: 63 ADDR_MAX: 72
ADDR_MIN: 13 ADDR_MAX: 22
======================================
V C S S i m u l a t i o n R e p o r t
Time: 0 ns
CPU Time: 0.480 seconds; Data structure size: 0.0Mb
Thu Jan 26 09:47:17 2023