Adder Tree Placement

I think there is a relatively smart way of adding the relatively placement primitives to your hdl code using vhdl generate command. If you separate the multi-input adder from the coefficient/input multipliers, you can code a reusable macro for this purpose. I think this might even possible with verilog-2001 but I haven't tried yet.

It's still difficult, even if your tool supports Verilog-2001. VHDL is still the better language if you are 'calculating' your placement.

Regards, Allan

I've tried to work this issue some in the past. Since you're using Xilinx, the adders are vertical structures that occupy half a CLB allowing 2 adders per CLB column. The final adder has two inputs that come from smaller adder trees to the right and left for minimum propagation. I ended up going into the FPGA Editor to try different configurations to come up with the "optimum" delay. Most architectures like inputs that are one or two columns away with a feedback within a column sometimes producing better, sometimes worse delays compared to the adjacent column.

Proper timing constraints would *ideally* give you the nice, right/left distributed adders.where bits at the same level are in the same CLB row across the adders. The P&R tool tends to be a little less precise but might be coerced into giving proper results with better constraints than I've developed. For the extremely tight designs I tend to RLOC the adders. It's a pain in Verilog but I haven't had to RLOC more than one or two moderately sized adder trees.

Well, if you must use a tree (more on that in a minute), then your best bet is to include RLOCs for the adders. You get reasonable performance by placing the first level in every other slice column and then placing the next levels in every other vacant column until you reach the root. "Reasonable" depends on the depth of the tree and your clock speed of course. It starts losing performance at 3 levels or so, because of the progressively longer routes. You can make up the speed by adding pipeline registers at the cost of real-estate.

--

--Ray Andraka, P.E. President, the Andraka Consulting Group, Inc.

"They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759

Thanks for this input. I certainly don't want to try to use FPGA editor to experiment with different configurations, so this is helpful.

At one point I tried to put the whole tree in a single row like you suggest, but one problem with that is that the adder inputs come from BRAMs, which are in a long column. I guess I could register the BRAM outputs (a second time) to get all the signals to a single row, where the tree would lie.

-Kevin

Your suggestion on tree layout is exactly what I was looking for. It seems my tree that is floorplanned like a tree isn't the best plan.

You are right about the transpose FIR architecture, though. I have become convinced that that is the best choice because of the ease of layout. I will be able to place the adders right next to the BRAMs in the column and the datapaths will be nice and short.

-Kevin

--

--Ray Andraka, P.E. President, the Andraka Consulting Group, Inc.

"They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759