Embeding pipeline stages to a recursive adder tree code

Joined
Sep 24, 2011
Messages
2
Reaction score
0
Hello all,

I have written, synthesized and tested (behavioral simulation) a generic adder tree that receives a bit string of arbitrary length and computes the sum of all bits. I have used a recursive function. My code is the following:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity AdderTree is
Generic (InputStringSize : integer := 80;
OutputWidth : integer := 7);
Port ( BitString : in STD_LOGIC_VECTOR (InputStringSize-1 downto 0);
Sum : out STD_LOGIC_VECTOR (OutputWidth-1 downto 0);
Clk : in STD_LOGIC);
end AdderTree;

architecture Behavioral of AdderTree is

function adder_tree (BitStr : unsigned; iter : integer) return unsigned is
variable result: unsigned (OutputWidth-iter-1 downto 0):=(others=>'0');
variable bitstring_tmp : unsigned(BitStr'length-1 downto 0):=(others=>'0');
begin
bitstring_tmp:=BitStr;
if BitStr'length = 2 then
result:=('0' & bitstring_tmp(1 downto 1)) + ('0' & bitstring_tmp(0 downto 0));
elsif BitStr'length = 1 then
result:=bitstring_tmp(0 downto 0);
else
if (BitStr'length/=3) then
result:=('0' & adder_tree(bitstring_tmp(BitStr'length-1 downto BitStr'length/2),iter+1)) + ('0' & adder_tree(bitstring_tmp((BitStr'length/2)-1 downto 0),iter+1));
else
result:=(adder_tree(bitstring_tmp(BitStr'length-1 downto BitStr'length/2),iter)) + ('0' & adder_tree(bitstring_tmp((BitStr'length/2)-1 downto 0),iter+1));
end if;
end if;
return result;
end adder_tree;

begin

Sum<=std_logic_vector(adder_tree(unsigned(BitString),0));

end Behavioral;

Problem is that such a combinatorial design has high latency, limiting my clock in the rest of my design. To reduce it, I would like to add pipeline stages, but I don't know how exactly to do it, given the code above. Functions are c like sequential structures so I don't know how to add flip flops. I have thought of constructing the adder tree in parts, calling the function as many times as my pipeline stages and squeeze ffs in between but I would like to know if there is a better/easier solution. Thanks in advance.

ps: I'm using Xilinx ISE.
 
Joined
Jun 2, 2011
Messages
10
Reaction score
0
I think you will get maximum performance with Xilinx Core generator.
http://www.xilinx.com/support/documentation/ip_documentation/addsub_ds214.pdf
If you want to keep it parameric, try to add input or output flip-flops.You can do it externallly to your entity.
Synth. tool will likely distribute the logic between registers to obtain max frequency so you dont need to split your algorithm manually.
I guess ISE does it (http://www.synthworks.com/papers/VHDL_RTL_Pipelined_Multiplier_MAPLD_2002_S_BW.pdf) slide #7.

input ->| FF | -> | Your Logic | -> | FF | ->... -> | FF | -> output
 
Last edited:
Joined
Jan 29, 2009
Messages
152
Reaction score
0
I think you can do this by having the recursion on entity level instead of function level.
In order to do this,
  • Move the code outside the function, into the architecture body
  • Replace variables with signals
  • use if-generate statements instead of (sequencial) if statements
  • instantiate recursively: instantiating AdderTree with adjusted input vector

Now, if done correctly, at this point the code should yield exactly the same netlist.


However, now a pipeline can be introduced (again using if-generate statements if required for fine-tuning)
 
Joined
Sep 24, 2011
Messages
2
Reaction score
0
Thanks for your replies. I was feeling lazy so I trusted XST to add the pipeline stages. My clock frequency went to 72MHz from 23Mhz. I'll keep your advice in mind jorris I haven't though of that (always thought recursion as having to call some function). I don't feel too comfortable using functions and procedures in vhdl anyways.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top