Friday, April 21, 2023

CIRCULAR QUEUE implementation in System Verilog


NOTE:

Print Statements are implemented on every function call.

The Read pointer in dequeue is incremented by one, if not empty before the print.

Same is the case for write pointer.


In this setup, I used the MSB of wr_ptr and rd_ptr to represent a rollover of the memory ( array ).This in turn is used to generate the FULL and EMPTY signals.


 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class circular_queue;
  parameter int N = 5;
  parameter int WIDTH = 3;
  
  int arr[N];
  bit isFull;
  bit isEmpty;
  bit [WIDTH:0] wr_ptr; //clog2 ??
  bit [WIDTH:0] rd_ptr;
  
  extern function new();
  extern function void enqueue(int val);
  extern function int dequeue();
  extern function int peek();  
  
endclass: circular_queue
    
    function circular_queue::new();
      isEmpty = 1;
      isFull = 0;
    endfunction: new
    
    function void circular_queue::enqueue(int val);
      if(!isFull) begin
        isEmpty     = 0;
        arr[wr_ptr[WIDTH-1:0]] = val;
        wr_ptr[WIDTH-1:0] = (wr_ptr[WIDTH-1:0]+1) % N;
        wr_ptr[WIDTH] = wr_ptr[WIDTH-1:0] == 0 ? ~wr_ptr[WIDTH] : wr_ptr[WIDTH];
      end
      isFull = ( wr_ptr[WIDTH-1:0] == rd_ptr[WIDTH-1:0] && wr_ptr[WIDTH]!=rd_ptr[WIDTH]) ? 1 : 0;
      $display("ENQUEUE:: WR_PTR:%d RD_PTR:%d VAL:%02d ARR:%p FULL:%d EMPTY:%d",wr_ptr[WIDTH-1:0],rd_ptr[WIDTH-1:0],val,arr,isFull,isEmpty);
    endfunction: enqueue
    
    function int circular_queue::dequeue();
      int val;
      if(!isEmpty) begin
        isFull = 0;
        val = arr[rd_ptr[WIDTH-1:0]];
        rd_ptr[WIDTH-1:0] = (rd_ptr[WIDTH-1:0]+1) % N;
        rd_ptr[WIDTH] = rd_ptr[WIDTH-1:0] == 0 ? ~rd_ptr[WIDTH] : rd_ptr[WIDTH]; 
      end
      isEmpty = ( wr_ptr[WIDTH-1:0] == rd_ptr[WIDTH-1:0] && wr_ptr[WIDTH]==rd_ptr[WIDTH]) ? 1 : 0;
      $display("DEQUEUE:: WR_PTR:%d RD_PTR:%d VAL:%02d ARR:%p FULL:%d EMPTY:%d",wr_ptr[WIDTH-1:0],rd_ptr[WIDTH-1:0],val,arr,isFull,isEmpty);
      return val;
    endfunction: dequeue
    
    function int circular_queue::peek();
      int val;
      if(!isEmpty)
      val = arr[rd_ptr];
      $display("PEEK   :: WR_PTR:%d RD_PTR:%d VAL:%02d ARR:%p FULL:%d EMPTY:%d",wr_ptr[WIDTH-1:0],rd_ptr[WIDTH-1:0],val,arr,isFull,isEmpty);
      return val;
    endfunction: peek
    
module top;
  circular_queue cq;
  
  initial begin
    int wr_val;
    int rd_val;
    
    cq = new;
    repeat(4) begin
      wr_val = $urandom_range(1,100);
      cq.enqueue(wr_val);
    end
    repeat(20) begin
      randcase
      	2 : begin
          wr_val = $urandom_range(1,100);
          cq.enqueue(wr_val);
        end
        2 : begin
          rd_val = cq.dequeue();
        end
        1 : begin
          rd_val = cq.peek();
        end
      endcase
    end
  end
endmodule: top


> OUTPUT::

Chronologic VCS simulator copyright 1991-2021
Contains Synopsys proprietary information.
Compiler version S-2021.09; Runtime version S-2021.09; Apr 22 02:40 2023
ENQUEUE:: WR_PTR:1 RD_PTR:0 VAL:39 ARR:'{39, 0, 0, 0, 0} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:2 RD_PTR:0 VAL:61 ARR:'{39, 61, 0, 0, 0} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:3 RD_PTR:0 VAL:74 ARR:'{39, 61, 74, 0, 0} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:4 RD_PTR:0 VAL:71 ARR:'{39, 61, 74, 71, 0} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:4 RD_PTR:1 VAL:39 ARR:'{39, 61, 74, 71, 0} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:0 RD_PTR:1 VAL:97 ARR:'{39, 61, 74, 71, 97} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:1 RD_PTR:1 VAL:23 ARR:'{23, 61, 74, 71, 97} FULL:1 EMPTY:0
PEEK :: WR_PTR:1 RD_PTR:1 VAL:61 ARR:'{23, 61, 74, 71, 97} FULL:1 EMPTY:0
ENQUEUE:: WR_PTR:1 RD_PTR:1 VAL:91 ARR:'{23, 61, 74, 71, 97} FULL:1 EMPTY:0
DEQUEUE:: WR_PTR:1 RD_PTR:2 VAL:61 ARR:'{23, 61, 74, 71, 97} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:2 RD_PTR:2 VAL:58 ARR:'{23, 58, 74, 71, 97} FULL:1 EMPTY:0
DEQUEUE:: WR_PTR:2 RD_PTR:3 VAL:74 ARR:'{23, 58, 74, 71, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:2 RD_PTR:4 VAL:71 ARR:'{23, 58, 74, 71, 97} FULL:0 EMPTY:0
PEEK :: WR_PTR:2 RD_PTR:4 VAL:97 ARR:'{23, 58, 74, 71, 97} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:3 RD_PTR:4 VAL:27 ARR:'{23, 58, 27, 71, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:3 RD_PTR:0 VAL:97 ARR:'{23, 58, 27, 71, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:3 RD_PTR:1 VAL:23 ARR:'{23, 58, 27, 71, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:3 RD_PTR:2 VAL:58 ARR:'{23, 58, 27, 71, 97} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:4 RD_PTR:2 VAL:20 ARR:'{23, 58, 27, 20, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:4 RD_PTR:3 VAL:27 ARR:'{23, 58, 27, 20, 97} FULL:0 EMPTY:0
DEQUEUE:: WR_PTR:4 RD_PTR:4 VAL:20 ARR:'{23, 58, 27, 20, 97} FULL:0 EMPTY:1
DEQUEUE:: WR_PTR:4 RD_PTR:4 VAL:00 ARR:'{23, 58, 27, 20, 97} FULL:0 EMPTY:1
ENQUEUE:: WR_PTR:0 RD_PTR:4 VAL:06 ARR:'{23, 58, 27, 20, 6} FULL:0 EMPTY:0
ENQUEUE:: WR_PTR:1 RD_PTR:4 VAL:73 ARR:'{73, 58, 27, 20, 6} FULL:0 EMPTY:0
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.700 seconds; Data structure size: 0.0Mb
Sat Apr 22 02:40:54 2023

Pavan at
Labels: , , , , , , , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

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; param...