Generics in hardware description language

Question

I'm fairly new to HD description languages. I'm finding it a bit hard to change my C-ish programming skills, and I'm looking for a little guaidance to help my throw the following problem.

I want to implement a full tree, that its inner nodes are different than its leaves. The number of the leaves is generic (asuming there is 2^k leaves so the tree can be full)

Each inner node is a component made out of a simple combinational circuit.

The leaves are synchronized with a clock, and are connected to the next leaf (breaking the tree structures - and forming something like a shift register)

This means that my design has to have a generic number of components that is connected according to the number of leaves.

While this could be solved recursivly in no time in C-based languages. I can't grasp the idea of solving it in HDL, since this generic form is different than n-bit input signals...

My implementation must be synthesizable, so SystemVerilog can't shine in this area :(

Is it possible to implement the described problem while keeping my code synthesizable? can anyone guide me throw this or point me to a good reference regarding this topic?

Answer 1

I'll try to provide an answer that allows you to build a generic tree, without recursion, based only on the tree height provided as a generic at compile time. The code itself looks a bit tricky for my taste; however, the principles behind the solution are straigthforward. Here's an outline of the solution:

• Imagine your nodes will be placed on a grid, with dimensions V=TREE_HEIGHT+1 and H=2**TREE_HEIGHT (see the ASCII-gram below). Then, all you need is an algorithm to populate the grid with nodes, and to make the right input and output connections.
• To connect one level of the tree to the next, you can use a bidimensional array of size TREE_HEIGHT x 2**TREE_HEIGHT (see line 63 in the code example below).
• To instantiate the nodes, use two nested loops (for-generate in VHDL, see lines 68-69). You will not populate all nodes; for a given row at depth=i, only 2**(i-1) nodes are needed (line 71).
• You can instantiate different entities for internal and leaf nodes. Just check whether the current value of i equals TREE_HEIGHT (lines 74 and 84).
• Finally, you just need to connect the layers of the tree. The arithmetic is a bit tricky, but once you get it right you're done (lines 78-80).
• Count on your synthesis tool to remove the unused wires.

Here's a poor rendition of the "grid" for HEIGHT=2:

             j = 1           j = 2           j = 3           j = 4      
       +---------------+---------------+---------------+---------------+
i = 1  | Root Node     |    (empty)    |    (empty)    |    (empty)    |
       +---------------+---------------+---------------+---------------+
i = 2  | Internal Node | Internal Node |    (empty)    |    (empty)    |
       +---------------+---------------+---------------+---------------+
i = 3  | Internal Node | Internal Node | Internal Node | Internal Node |
       +---------------+---------------+---------------+---------------+

Here's the code example:

/*  1 */  package tree_types_pkg is
/*  2 */      -- define a data type for the input and output values at each node
/*  3 */      subtype tree_data_type is integer range 0 to 255;
/*  4 */      -- define a vector type to propagate the output of a tree level to the next
/*  5 */      type layer_to_layer_channel_type is array (natural range <>) of tree_data_type;
/*  6 */  end;
/*  7 */  --------------------------------------------------------------------------------
/*  8 */  use work.tree_types_pkg.all;
/*  9 */
/* 10 */  entity internal_node is
/* 11 */      generic (
/* 12 */          TREE_HEIGHT: integer := 3
/* 13 */      );
/* 14 */      port (
/* 15 */          x: in integer range 1 to 2**TREE_HEIGHT;
/* 16 */          y: in integer range 1 to TREE_HEIGHT;
/* 17 */          input: in tree_data_type;
/* 18 */          output_left: out tree_data_type;
/* 19 */          output_right: out tree_data_type
/* 20 */      );
/* 21 */  end;
/* 22 */
/* 23 */  architecture rtl of internal_node is begin
/* 24 */      -- perform some calculation at the node
/* 25 */      output_left <= input + x * y;
/* 26 */      output_right <= input - x * y;
/* 27 */  end;
/* 28 */  --------------------------------------------------------------------------------
/* 29 */  use work.tree_types_pkg.all;
/* 20 */
/* 31 */  entity leaf_node is
/* 32 */      generic (
/* 33 */          TREE_HEIGHT: integer := 3
/* 34 */      );
/* 35 */      port (
/* 36 */          x: in integer range 1 to 2**TREE_HEIGHT;
/* 37 */          y: in integer range 1 to TREE_HEIGHT;
/* 38 */          input: in tree_data_type;
/* 39 */          output: out tree_data_type
/* 30 */      );
/* 41 */  end;
/* 42 */
/* 43 */  architecture rtl of leaf_node is begin
/* 44 */      -- perform some calculation at the node
/* 45 */      output <= input + x * y;
/* 46 */  end;
/* 47 */  --------------------------------------------------------------------------------
/* 48 */  use work.tree_types_pkg.all;
/* 49 */
/* 50 */  entity dirtybit_binary_tree is
/* 51 */      generic (
/* 52 */          TREE_HEIGHT: integer := 4
/* 53 */      );
/* 54 */      port (
/* 55 */          tree_input: in tree_data_type;
/* 56 */          tree_outputs: out layer_to_layer_channel_type(1 to 2**TREE_HEIGHT)
/* 57 */      );
/* 58 */  end;
/* 59 */
/* 60 */  architecture behavior of dirtybit_binary_tree is
/* 61 */      constant LEAF_NODES_COUNT: integer := 2**TREE_HEIGHT;
/* 62 */      type channel_array_type is array (natural range <>) of layer_to_layer_channel_type;
/* 63 */      signal connections: channel_array_type(1 to TREE_HEIGHT)(1 to LEAF_NODES_COUNT);
/* 64 */  begin
/* 65 */
/* 66 */      connections(1)(1) <= tree_input;
/* 67 */
/* 68 */      grid_y: for i in 1 to TREE_HEIGHT generate
/* 69 */          grid_x: for j in 1 to LEAF_NODES_COUNT generate
/* 70 */
/* 71 */              instantiate_nodes: if j <= 2**(i-1) generate
/* 72 */
/* 73 */                  internal_nodes: if (i /= TREE_HEIGHT) generate
/* 74 */                      internal_node: entity work.internal_node 
/* 75 */                          generic map (TREE_HEIGHT => TREE_HEIGHT)
/* 76 */                          port map (
/* 77 */                              x => j,
/* 78 */                              y => i,
/* 79 */                              input        => connections(i)(j),
/* 80 */                              output_left  => connections(i+1)((j-1)*i+1),
/* 81 */                              output_right => connections(i+1)((j-1)*i+2)
/* 82 */                          );
/* 83 */                  end generate;
/* 84 */
/* 85 */                  leaf_nodes: if (i = TREE_HEIGHT) generate
/* 86 */                      leaf_node: entity work.leaf_node 
/* 87 */                          generic map (TREE_HEIGHT => TREE_HEIGHT)
/* 88 */                          port map (
/* 89 */                              x => j,
/* 90 */                              y => i,
/* 91 */                              input  => connections(i)(j),
/* 92 */                              output => tree_outputs(j)
/* 93 */                          );
/* 94 */                  end generate;
/* 95 */
/* 96 */              end generate;
/* 97 */
/* 98 */          end generate;
/* 99 */      end generate;
/* 100 */
/* 101 */ end;

Finally, here's what the synthesized circuit looks like on Quartus 12.1 (RTL Viewer):

Answer 2

You can write a recursive algorithm in VHDL that is executed during elaboration, and which then defines the hardware structure to be synthesised, via the generate statement. You can almost do this in Verilog, which has had automatic functions since 2001, but they're not fully automatic, and I don't think I've seen any usable synthesisable examples of this sort of thing in Verilog.

Post some pseudo-C so that we can see what you want.

EDIT See this paper: it describes the recursive generation of a fat tree structure in VHDL. This is handled entirely by recursive component instantiation, rather than by using a recursive algorithm to pre-define the structure.

Answer 3

You probably want to look at how to use a generate statement in VHDL. Use of a generate statement with a for statement will generate as many components as you need.

It is a requirement though that the total number of leaves be known when the FPGA is built. You cannot dynamically create leaves.

Answer 4

Verilog (or VHDL) generate statements can be used to create a scalable system, but the amount of hardware implied is fixed at compile time. You can not on the fly change how much hardware there is. Links for Verilog generate one, two.

Short example, wiring up multiple wires to an inverter

parameter DATA_W = 4;
parameter DEPTH  = 8;

wire [DATA_W-1:0] data   [0:DEPTH-1];
wire [DATA_W-1:0] data_n [0:DEPTH-1];

genvar index;  
generate  
  for (index=0; index < DEPTH; index=index+1) begin: gen_code_label  
    inv #(
      .WIDTH  ( DATA_W        ) 
    ) inv_i0 (  
      .rx     ( data[index]   ), // input  
      .tx     ( data_n[index] ), // output   
    );  
  end  
endgenerate 

I find generates little hard to follow sometimes, especially if using to wire up a lot of hardware, they also introduce another level of hierarchy, which is often undesired.

For scalable template code I use erb (ruby), using the gem ruby-it.
Disclaimer I wrote the gem to make doing this easier.

Another question showing use of erb.

Answer 5

There's no reason why recursion doesn't work in HDLs. VHDL's generate statement can be used to recursively instantiate entities quite happily. Bear in mind that you need to know how deep the recursion is at compile-time, as the hardware is created up-front. But that's not actually so different to making sure you have enough stack-space in a software context - it's just enforced, rather than implied (with the option of exciting stack-smashing bugs if you get it wrong :)