Look into performance improvements to readback implementation

[rskvprd]

Problem
I had timing and resource utilisation issues with large register map. Significant part of the logic utilisation and timing issues was in readback logic.

Solution
But when i changed implementation from Flat 1-hot array then OR reduce¹ to Flat case statement¹ (in fact, i've generated big if..else..else..else statement), utilisation was significantly reduced and timing issue was fixed.

Proposal
It would be nice to have option like --readback-mux-impl with options like orreduce and case for designs with low budget/large regmaps

Footnotes

1. See readback-mux devnotes ↩ ↩²

[amykyta3]

I will look into optimizing the readback implementation.

Can you share what technology this is for? (FPGA or ASIC)
Generally OR-reduction trees optimize very well, but perhaps this needs to be studied further. I would prefer to find a good all-around solution rather than introducing mode switches.

[rskvprd]

It was Xilinx FPGA

[amykyta3]

I did some utilization benchmarks using Vivado synthesis on an UltraScale device, comparing several readback implementation styles.

testcases.zip

For a 64 x 8 bit register array, reducing to an 8 bit output scales as follows:

• OR-reduction using strobes (current strategy): 245 LUTs
• Directly indexing (as discussed in LUT decrease when moving to cpuif indexing for readback #189): 136 LUTs
• Unrolled as a flat case statement: 136 LUTs
• Series of if() statements in an always block (similar to address decode): 136 LUTs

So clearly my initial intuition was wrong, and I literally chose the worst option 😆

Interestingly the last option infers the exact same logic as a case statement (I had always assumed this would infer some sort of priority coding). Given the architecture used in this tool, this makes it the most scalable option by all accounts since it synthesizes most efficiently, and also avoids the need to unroll arrays for case statements.

Implementing the readback retiming stage will have to work slightly differently - rather than inserting it at the midpoint of the OR-reduction tree, it will bisect the cpuif_addr bits. For register files with no gaps, this is equivalent, but for designs with non-uniform distributions of registers, this will be unable to re-balance the address range as effectively. Given this is more of an edge case, I think that is acceptable.

[davekeeshan]

• Unrolled as a flat case statement: 136 LUTs

• Series of if() statements in an always block (similar to address decode): 136 LUTs

I looked at this before, I suspect that xilinx cheats here, it has some special compiler feature that looks and tries to resolve a big if statement into a case statement, based on some heuristic consistency. I imagine that you can't take it to the bank that any other synthesis compiler would do the same thing (they might). I wonder what yosys does here in terms of numbers ...

I noticed that xilinx cheats in a few places, how it uses variables inside a clocked process, like an incrementer, they seem to be a little generous.

[amykyta3]

Implemented. Will be in next release

[sbaillou]

Hi @amykyta3 ,

My initial intuition would also have been that the OR-reduction is better for synthesis.

For a 64 x 8 bit register array, reducing to an 8 bit output scales as follows:

• OR-reduction using strobes (current strategy): 245 LUTs
• Directly indexing (as discussed in
• Unrolled as a flat case statement: 136 LUTs
• Series of if() statements in an always block (similar to address decode): 136 LUTs

Did you also run a similar experiment with ASIC synthesis flows? Because I'm slightly worried this new approach is well optimized for FPGAs, but not ASICs.

EDIT: I ran your testcases through Genus, and the timing is roughly identical in all 4 implementations.

However, the area of the if_compare implementation ends up being slightly larger than the others:

Implementation	Area
direct_idx	508.951 µm²
if_compare	522.353 µm²
or_reduce	500.699 µm²
unrolled_case	508.951 µm²

[Blebowski]

Hi,

I think the if-else-if is dangerous. In case of DC, the default translation to "G-tech" creates long logic chain in such case, while case is natively "parallel logic". Sure, the tool is likely able to recognize it, and parallelize it. However, if you have big design, with dozens of register maps, thousands of registers, it is extra work the tool needs to do, and could spend the run-time elsewhere.

I generally had the experience of "writing prioritized selection logic usually performs worse than the parallel". Couple of designers I worked with had similar experience.

I know it is extra effort / maintenance cost to have configurability in this case, but I would very much welcome if this could be chosen by a switch. The numbers above speak for themselves, basic Genus synthesis has 4 % higher area for the if-else than for the OR.
And I am not sure all industry tools will have the magical Xilinx parallelization pass...

[amykyta3]

Thanks @sbaillou for running a comparison in Genus. I was really hoping to not have to support multiple different readback implementations, but that may be necessary in the end.
By any chance, do you know if the std cell library you were targeting include native MUX cells? Most modern libraries do, but want to be sure.

@Blebowski is your comment about DC anecdotal? Or were you able to run the same testcases with Design Compiler? Would be valuable to make a direct comparison here similar to what @sbaillou did.