looking for feedback about an address encoder design in SystemVerilog

[m.donies]

Hello,

I am a student in digital electronic and, for a part of my master thesis, I have designed a synthesizable N to M address encoder (sources below) in SystemVerilog. The simulation is correct and I am going to test it on FPGA.
Before that, I have done some researches on the web to find a typical solution to solve this problem, but i haven't found any pertinent solutions.
So, I am looking for feedback about this design.

My design have a lot of additional registers and the combinational circuit has a stairs structure because i need to manage the N (address_in) and the M (address_out) parameters. So i guess, it's possible to improve that.

I have published my code and the testbench on Github at this address : https://github.com/marxys/address_encoder.

Can someone give me a feedback and some advices about improvements possibilities ?

Thank you for considering my request,
Martin

---

Code Verilog - [expand]
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//
//  Author : Martin Donies
//
//
//                    GNU GENERAL PUBLIC LICENSE
//                       Version 2, June 1991
//
// Copyright (C) 1989, 1991 Free Software Foundation, Inc., <http://fsf.org/>
// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
// Everyone is permitted to copy and distribute verbatim copies
// of this license document, but changing it is not allowed.  
 
    // ## PARAMETERS ##
    //
    // input_width      : the size of the global address
    // output_width     : the size of the local address and obviously 2^output_width = length of the associative array
    //
    // ## INPUT/OUTPUT ##
    //
    // we               : write enable to add the addr_in on the associative array and get an associated local address
    // clear            : remove the given addr_out from the associative array.
    // addr_in          : global address given to get the local address or the encoded address
    // addr_out         : the local or the encoded address. valid only if ~not_selected & ~address_conflict == 1; 
    // not_selected     : signal to know if addr_in is not found
    // address_conflict : signal to know if addr_in is found more than once 
    // free_space       : signal to know if it's possible to store a new address on the associative array
    //
 
module address_mem_encoder  #(  
        parameter int unsigned output_width = 3,
        parameter int unsigned input_width  = 16
    )(   
        input   logic                       clock, reset, we, clear,
        input   logic [input_width-1:0]     addr_in,
        output  logic [output_width-1:0]    addr_out,
        output  logic                       not_selected, address_conflict, free_space
    );
 
    // ## Combinational search ##
    //
    // sel              : indicate if the address is stored on position i 
    // sel_vector       : propagate sel from 0 to output_width
    // conflict_vector  : detect if more than one sel (if |conflict_vector == 1) -> there is a conflict
    // used_vector      : determine used registers to know if we have to compare addr_in with the stored address
    // addr_out_comb    : propagade the founded address from [0] -> [2^output_width]
    // task_lookup_reg  : registers to store all global addresses. 
    //
    // ## Sequencial write ##
    //
    // init             : indicate initialization phase. This phase use 2^output_width cycles.
    // pos_vector       : contain all free register, it's a fifo register
    // pos              : address of the first empty slot
    // start_ptr        : pointer to the first element in the fifo register pos_vector
    // end_ptr          : pointer to the last element +1 in the fifo register pos_vector
    // pos_start_ptr    :
    // pos_end_ptr      : like start_ptr and end_ptr with the overflow bit to keep start_ptr < end_ptr
    // 
 
    logic                          init, end_init;
    logic [output_width-1:0]       pos, start_ptr, end_ptr;
    logic [output_width-1:0]       pos_vector[2**output_width-1:0];
    logic [output_width:0]         pos_start_ptr, pos_end_ptr;
    wire  [2**output_width-1:0]    sel_vector;
    wire  [2**output_width-2:0]    conflict_vector, sel;
    logic [2**output_width-1:0]    used_vector;
 
    wire  [2**output_width-1:0]    addr_out_comb[2**output_width-1:0];
    logic [input_width-1:0]        task_lookup_reg[2**output_width-1:0];
 
    assign start_ptr    = pos_start_ptr[output_width-1:0];
    assign end_ptr      = pos_end_ptr[output_width-1:0];
    assign pos          = pos_vector[start_ptr];
    assign end_init     = &end_ptr;
 
    // reset overflow bit of pos_start_ptr and pos_end_ptr when start_ptr return to the position 0
    always_ff @(negedge clock)
        if(pos_start_ptr[output_width] & pos_end_ptr[output_width])
            begin
                pos_start_ptr[output_width] <= 1'd0;
                pos_end_ptr[output_width]   <= 1'd0;
            end
 
    always_ff @(negedge clock) 
        if (reset) begin
            used_vector                 <= 1'd0;
            init                        <= 1'd1;
            pos_start_ptr               <= {output_width{1'd0}};
            pos_end_ptr                 <= {output_width{1'd0}};
        end
        // store a global address to the first free position if free_space and not init
        else if (we & free_space & ~init) begin
            used_vector[pos]            <= 1'd1;
            task_lookup_reg[pos]        <= addr_in;
            pos_start_ptr               <= pos_start_ptr + 1'd1; 
        end
        // clear a global address
        else if (clear & ~init) begin
            used_vector[addr_out]       <= 1'd0;
            task_lookup_reg[addr_out]   <= {input_width{1'd0}};
            pos_vector[end_ptr]         <= addr_out;
            pos_end_ptr                 <= pos_end_ptr + 1'd1;
        end
        // write all local address to the pos_vector
        else if (init) begin
            init                        <= ~end_init;
            pos_vector[end_ptr]         <= pos_end_ptr[output_width-1:0];
            pos_end_ptr                 <= pos_end_ptr + 1'd1;
            task_lookup_reg[end_ptr]    <= {input_width{1'd0}};
        end
 
    // search the given global address throw the registers
 
            assign sel_vector[0]    = used_vector[0] & (addr_in == task_lookup_reg[0]);
            assign addr_out_comb[0] = {output_width{1'd0}};
            genvar i;
            generate
            for(i=0; i < 2**output_width-1; i=i+1)
                begin
                    assign sel[i]               = used_vector[i+1] && (addr_in == task_lookup_reg[i+1]);
                    assign sel_vector[i+1]      = sel[i] | sel_vector[i];
                    assign addr_out_comb[i+1]   = addr_out_comb[i] | (sel[i] ? i+1 : {output_width{1'd0}});
                    assign conflict_vector[i]   = sel_vector[i] & sel[i];
                end
            endgenerate
    
 
    assign addr_out             = addr_out_comb[2**output_width-1];
    assign not_selected         = ~|sel_vector;
    assign address_conflict     = |conflict_vector;
    assign free_space           = ~&used_vector;
 
endmodule

---

 

[TrickyDicky]

My Comments:
1. Why have you used the negedge of the clock? it is more usual to use the posedge. It would mean this block would not be usuable by the majority of designs.
2. I would rather the addr_out is registered. This means other users dont need to worry about the combinatorial path delay in to their logic.
3. Have you tried synthesising this in various expected design examples to give an idea of resource usage and potential fmax? Have you tried it through various vendors tools - mainly Xilinx and Altera?

 

[m.donies]

Firstly, thank you for your quick response.

My Comments:
1. Why have you used the negedge of the clock? it is more usual to use the posedge. It would mean this block would not be usuable by the majority of designs.

I do that to be sure that the trigger work even if the address_in is trigged by the posedge of the clock, but i dont already have inserted this block on my global design. So it may change.

2. I would rather the addr_out is registered. This means other users dont need to worry about the combinatorial path delay in to their logic.

Thank you, I m going to change that directly.

3. Have you tried synthesising this in various expected design examples to give an idea of resource usage and potential fmax? Have you tried it through various vendors tools - mainly Xilinx and Altera?

No, I am going to try it on Cyclone 5 with Altera. I will test performance later because it's a little part of my work (before I was hoping to find a reliable implementation because i believed it's a common circuit for implementing cache system) and i want to validate all my design before testing all bottleneck. But I will comeback later with these results.


Theoretically, de number of stages is proportional to 2^output_width, so i dont expect good performances for fmax. But like i said, I don't know how to change this "stairs structure" to a better solution using generate technique.
I will try to assign the wires vectors with a "pyramid" structure to get a number of stages proportional to log(2^output_with) but is a little improvement regarding to all of the additional registers and the complete search circuit.

 

[TrickyDicky]

Firstly, thank you for your quick response.


I do that to be sure that the trigger work even if the address_in is trigged by the posedge of the clock, but i dont already have inserted this block on my global design. So it may change.
.

This is poor design practice. You need the entire design on the same edge, or you make timing analysis much harder. You're basically halving the allowed time from one register (on pos edge) to the next (on neg edge). Everything needs to be on the same edge, which is usually the rising edge (I ave never used the neg edge, or seen a design that uses the neg edge)