Generics in hardware description language

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?

Solution

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):

Tree circuit on Quartus RTL Viewer