[SOLVED] Synchronous FIFO sizing issue

[promach]

May I know why assign full = (count == SIZE[ADDR_WIDTH:0]); won't work ?

 

[ads-ee]

It does work but requires and extra counter and compare logic to do so, whereas using the addresses directly only requires different compare logic and does not require an extra counter.

If you need the write or read counts then using a depth counter is convenient, but not actually necessary as you can compute the depth used by subtracting the write and read address pointers.

 

[TrickyDicky]

You still didn't really explain why you are doing this. There will be N address bits, giving 2^N locations. Not using all the Locations just means you need more logic to guard against using the extra space. usually you just difference read and wr addresses to get the fill level.

 

[promach]

usually you just difference read and wr addresses to get the fill level.

I have already tried your suggestion. It will only work with power-of-two size, but not with non-power-of-two size.

There is reason. Try to do the read address and write address on a piece of paper, and you will see why.

 

[FvM]

There is reason. Try to do the read address and write address on a piece of paper, and you will see why.

You are right. Isn't it so that the whole problem of adapting the FIFO code to non power of two size can be solved with pencil and paper and a bit of thinking?

 

[ads-ee]

I don't understand why you need a non-power of two sized FIFO, it doesn't even make any sense to do so.

Any RAM in an FPGA has a power of 2 depth and using it for a FIFO will use all the addresses you specify for use. If you restrict to less than a power of 2 then you use every address in the RAM except the addresses between your restricted depth and the power of 2 depth, which is just wasting the resources of the FPGA as they are naturally available but not used by your design.

If you think you can use the left over resources for something else then you are mistaken.

So far you haven't made a case for why having a FIFO of 5000 entries is preferred over one with 8192 entries. A 1,048,576 entry FIFO could be used in the same place as a 16 deep FIFO and would have identical behavior, as long as the 16 deep FIFO never goes full.

As for the address calculation for depth. Why don't you try using an example with a limited number of addresses and see what happens to the calculation when it wraps for a range that is less than a power of 2. Hint: Think about what increasing the bit width of the address does for the address calculations (was done in previous code snippets), what does the 1 in write pointer 1000 mean in a full condition where the read pointer is at 0000?

 

[promach]

I have finished all the design code modification for non-power-of-two fifo size. They passed both BMC basecase and cover() checks.

However, why this line number 391 failed for induction in formal verification ?

 

[ads-ee]

it fails because the calculation is incorrect.
that is not how the count depth is determined using the write and read pointers to a non-power of 2 depth FIFO. See my previous post.

 

[promach]

it fails because the calculation is incorrect.

No, induction failed because of insufficient assert().

The calculation is correct because it had passed BMC basecase in formal verification.

 

[ads-ee]

wr_addr - rd_addr - ((1 << ADDR_WIDTH) - SIZE)

for a 4-bit address and read and write pointers 2 away from each other.

for a size of 16
0001 - 1111 - 10000 + 10000
1 - 15 - 16 + 16 = -14 which is wrong.

for a size of 10
0001 - 1001 -10000 +1010
1-9-16+10 = -14 which is wrong

Notice the error is the same regardless of the size of the FIFO. The calculation is a modulo problem and has to be treated as such.

 

[promach]

count is of unsigned wire type. There is no -14 in hardware verilog.

Check your calculation again.

 

[ads-ee]

count is of unsigned wire type. There is no -14 in hardware verilog.

Check your calculation again.

My bad didn't convert to 2's comp afterwards.

But the calculation is simpler if you just use wr_ptr - rd_ptr + SIZE. That extra 1 << ADDR_WIDTH is just adding extra calculations to roll the binary count over a second time.

--- Updated Aug 19, 2020 ---

But I still don't see the point of "throwing away" (1 << ADDR_WIDTH) - SIZE of the RAM just to make it artifically smaller when it doesn't matter if a FIFO is larger.

 

[promach]

But the calculation is simpler if you just use wr_ptr - rd_ptr + SIZE. That extra 1 << ADDR_WIDTH is just adding extra calculations to roll the binary count over a second time.

no, using simpler version won't work because you are thinking count as fifo address, instead of scalar number.

Note that this non-power-of-two fifo has its own specific purpose/niche

 

[TrickyDicky]

So specific, that I've never seen or heard of one before, ever. Mostly because its wasteful and no saving over a power of 2 ram in either fpga or Asic. Can you please explain why you need it?

 

[ads-ee]

no, using simpler version won't work because you are thinking count as fifo address, instead of scalar number.

Huh!?
The difference between the two pointer IS a scalar count value and are not FIFO addresses. The simpler version computes the exact same value without double overflowing the bit width.

Note that this non-power-of-two fifo has its own specific purpose/niche

What is this some sort of "clever" double buffering scheme using FIFOs as the fixed size buffers? If that is the case it would be better if you just implement a double buffer RAM, which would also probably use less logic resources.

A FIFO naturally uses up what ever RAM it is given as the read/write pointer addresses follow each other through the RAM addresses. Having 100, 1000, 128, 1024, 4000, 8192, etc locations has no bearing on the behavior of a FIFO (other than when overflow occurs if you don't read it).

 

[vGoodtimes]

I've used non-power-of-two sizes in the past. not sure if I needed it for fifos specifically though. The goal is space savings when you know the max data size is a bit more than a power of two. this is more true if you know the max size is something like 33334 entries. suddenly the big fifo doubles in size if you keep power of two sizing. I could also see this coming up in channelized fifos and of course any dynamically sized fifo.

 

[ads-ee]

I've used non-power-of-two sizes in the past. not sure if I needed it for fifos specifically though. The goal is space savings when you know the max data size is a bit more than a power of two. this is more true if you know the max size is something like 33334 entries. suddenly the big fifo doubles in size if you keep power of two sizing. I could also see this coming up in channelized fifos and of course any dynamically sized fifo.

You are referring to a FIFO that requires a non-power of 2 number of RAM blocks to implement.

Okay that does benefit from not using the entire range of addresses. In the cases I've needed something like this I found that the FIFO was better implemented with the power of 2 as the performance of the non-power of 2 was worse as there had to be an extra mux on the output to multiplex all the RAM blocks that are implemented in parallel.

Of course in your example of 33334 entries you are out of luck as that is larger than most FPGAs RAM blocks even if they are configured as x1, so you are stuck with a mux no matter what you do.