Designing asynchronous FIFO with odd number depth

[fragnen]

Let me clarify more.

I need an asynchronous FIFO to store data and it should be minimum of depth 33. Even an asynchronous FIFO of depth 34 will solve my problem, but I cannot even waste area by increasing the depth to 34. So definitely I want depth of 33 to save area. Hope it clarifies the requirements.

 

[std_match]

Let me clarify more.

I need an asynchronous FIFO to store data and it should be minimum of depth 33. Even an asynchronous FIFO of depth 34 will solve my problem, but I cannot even waste area by increasing the depth to 34. So definitely I want depth of 33 to save area. Hope it clarifies the requirements.

But what is the FIFO width? How much extra space is needed if going to a 64 word memory?
You will "waste" some space for the more complicated logic if you have a depth that isn't a power of 2.

If you really need depth 33 I think you should use "real" pointers 0-32 for accessing the memory and "virtual" pointers 0-63 for full/empty detection.
By having double virtual read pointers (with one initialized to 33) or subtracting 31 from a single virtual read pointer, you can calculate empty/full.

Some signals and code fragments, VHDL style:

---

Code VHDL - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
signal real_write_ptr         : unsigned(5 downto 0); -- used range = 0-32
signal real_read_ptr          : unsigned(5 downto 0); -- used range = 0-32
signal virtual_write_ptr      : unsigned(5 downto 0); -- used range = 0-63
signal virtual_read_pointer_1 : unsigned(5 downto 0); -- used range = 0-63, for empty detection
signal virtual_read_pointer_2 : unsigned(5 downto 0); -- used range = 0-63, for full detection
 
 
-- write pointer handling (in a write clock process)
  -- increment write pointers
  if real_write_ptr = 32 then
    real_write_ptr <= (others => '0'); -- wrap from 32 to 0
  else
    real_write_ptr <= real_write_ptr + 1;
  end if;
  virtual_write_ptr <= virtual_write_ptr + 1;
 
  -- reset
  real_write_ptr : <= (others => '0'); -- used range = 0-32, initial value = 0
  virtual_write_ptr <= (others => '0'); -- used range = 0-63, initial value = 0
 
 
 
-- read pointer handling (in a read clock process)
  -- increment read pointers
  if real_read_ptr = 32 then
    real_read_ptr <= (others => '0'); -- wrap from 32 to 0
  else
    real_read_ptr <= real_read_ptr + 1;
  end if;
  virtual_read_ptr_1 <= virtual_read_ptr_1 + 1;
  virtual_read_ptr_2 <= virtual_read_ptr_2 + 1;
 
  -- reset
  real_read_ptr <= (others => '0'); -- used range = 0-32, initial value = 0
  virtual_read_pointer_1 <= (others => '0'); -- used range = 0-63, initial value = 0, for empty detection
  virtual_read_pointer_2 <= to_unsigned(33, 6); -- used range = 0-63, initial value = 33, for full detection 
 
 
 
-- The wanted empty/full conditions
empty <= '1' when virtual_write_ptr_read_domain = virtual_read_ptr_1 else '0'; -- write pointer transferred to the read domain
full <= '1' when virtual_write_ptr = virtual_read_ptr_2_write_domain else '0'; -- read pointer transferred to the write domain
 
-- The virtual pointers are transferred between clock domains using Gray coding
-- The actual read/write operations on the memory use the "real" pointers
-- Instead of having a separate signal for read pointer 2, it can be created by subtracting 31 from read pointer 1

---

For general info about asynchronous FIFO implementations, see this paper:

http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO2.pdf

 

[ads-ee]

Thread was to design an asynchronous FIFO with odd number of depth. For example to design a FIFO of depth 33 where we do not want to design the asynchronous FIFO of depth 34 and use it for depth 33. We want to save area so that if my requirement was up to depth 33 , we shall design uptown depth 33 only and not at all uptown depth 34 as we want to save area and not to loose area for an extra 34th location. Hope it clarifies the question in the thread.

Target is not to design an asynchronous FIFO of depth 34 and then derive an asynchronous FIFO of depth 33 as it waste the area for the 34th location.

Unlike others, I clearly understood that your "odd" FIFO was a FIFO with an odd number (as in not even) of locations and didn't mean you had a non-power of 2 "oddly sized" FIFO. As I've previously mentioned you can't perform gray-code on an odd number of addresses. You could come up with a custom scheme to do so with an even number of addresses.

I'm assuming this is a homework assignment from a teacher that has no real world experience as it is pointless to design something like this odd numbered depth FIFO that doesn't have any real world usefulness.

If the memory is only 33 locations then you have to have RAM addresses (pointers) that are 6-bits not 5-bits and what happens if a pointer exceeds the physical RAM depth? The RAM would have to be either built with logic to detect out of bound addresses or you need logic external to detect and abort any out of bound reads/writes to the RAM.

If I needed a FIFO that had a depth of 33 because of say 32 would overflow but 33 would not and I couldn't use a larger RAM in the design, then I would use a 32 deep RAM to implement the FIFO and add an additional register for the 33rd FIFO location. The RAM portion of the FIFO as it's a power of 2 uses a standard FIFO design and the extra register and flag logic resides outside the FIFO and manages the use of the register and indicating when the RAM FIFO is full and that external register has data to generate the 33 deep FIFO full indication. There is a limit on how many extra locations you can add using this register expansion as the area required by flip-flops is much greater than the area of a bit in a RAM array.

I recall having to do this kind of thing on some really old FPGAs due to the extremely poor clock to out of the RAM blocks that were more than 2/3 of our clock period. So we added an output register to the FIFO design that increased the size of our FIFOs by 1 extra location that had a much lower Tco.

 

[dpaul]

I guess the OP is asking this from an ASIC design point of view where there is nothing called dedicated block RAMs. So a front end ASIC design engineer strives to write the RTL with min resource usage in mind, be it for FIFO memory blocks are FIFO read/write logic.

I need an asynchronous FIFO to store data and it should be minimum of depth 33. Even an asynchronous FIFO of depth 34 will solve my problem, but I cannot even waste area by increasing the depth to 34. So definitely I want depth of 33 to save area.

But having a depth of 34 when 33 is really used in the design, is "no cardinal sin", IF YOUR FIFO WIDTH IS NOT SIGNIFICANTLY LARGE. But then you have REPEATEDLY failed to provide us info on the FIFO width. In a design team your manager will not pull you up for for the "one extra depth"!

I also have the feeling that you are not doing practical design.
Just try this (if you understand what I am saying) - Keeping all other design parameters same, synthesize your design with the FIFO depth 33 (I dont care how your achieve it) and note down the total resource usage. Next use a FIFO depth of 34, again keeping all other parts of the design same and synthesize your design to get the total resource usage. Compare both the resource usage.

 

[fragnen]

This problem has application. Once you design an async FIFO taking a DPRAM having 33 rows then you save an area of 1 ore as you are not using a DPRAM of row size 34 as you are avoiding designing an asynchronous FIFO with depth 34 as you only require depth 33. Are not you saving an area here?

If you have requirement of 50 such odd depth asynchronous FIFO you will save more area. Is not it ?

The specification for the problem along with the clarification is sufficient and does not need to include the width of the FIFO. But for high width this will save area also if design happens with the same methodology described above using a DPRAM of odd numbered row size where the row size is equal to the odd depth of the FIFO.

The adding of an external register as the 33th row along with usung a DPRAM having 32 bit may not save area as it was pointed out in this thread that area of a bit cell is smaller than a flip flop and hence we can implement the asynchronous FIFO with a DPRAM having row size of 34 and designing the asynchronous FIFO with depth 34 instead of 33 as an asynchronous FIFO with depth of 34 will worh as we only need depth of 33. Please review my comments and provide feedback.

 

[dpaul]

Please review my comments and provide feedback.

Did you read the *last paragraph* of my last comment? Do you have anything to say about it?

You still do not say anything about the FIFO width!
Can you show me a design (need to be your own, you can also point me to any external link) where all the FIFOs used are ALWAYS of odd depth?

The specification for the problem along with the clarification is sufficient and does not need to include the width of the FIFO.

Wrong!!!
If you are talking about resource saving how can you ignore the FIFO width? This is a very fundamental thing.
Do you really have a background in Electrical Engineering?

Enough info has been provided to you by many users to get going. If you do not have anything new to say, I do not want to waste any time arguing with you.

And please, do not repeat the same things again and again like a parrot!

 

[KlausST]

Hi,

I agree with dpaul.
Your requirement seem to be random. Maybe from your teacher, maybe from yourself.
You give no exact definitions, nor explanations.
And you ignore any argument from an experienced expert.
This is not motivating.

You may implement any size of FIFO...and you may do this without gray code (I'v never seen software that uses gray coded pointers). It's just a question of timing and implementation.

For synchronizing you may add signals as you like: ready_to_read for example. So all the FiFO logic and pointers may be within one clock domain.

So what exactly do you want (that you can accept)? Don't expect code without pay.

Klaus

 

[FvM]

Domain crossing FIFOs mostly use gray coded memory pointers to communicate the fill level between both sides. The method is simple and fast.

I don't recognize that the attempt to design a none power-of-two sized FIFO is more than a stupid exercise, but nevertheless ads-ee sketched an elegant way to design it. So you have two options: use less effective none gray code method for pointer synchronisation, or a combination of power-of-two sized DCFIFO and "odd" sized SDFIFO, respectively single register.

 

[ads-ee]

ads-ee sketched an elegant way to design it. So you have two options: use less effective none gray code method for pointer synchronisation, or a combination of power-of-two sized DCFIFO and "odd" sized SDFIFO, respectively single register.

I wonder if you considered the added register hack or the rolling buffer using a larger RAM the elegant approach ;-)

I'm not sure what the limitations on RAM sizes in an ASIC are (haven't worked on ASICs for decades), but is going from say a 33 deep RAM to a 64 deep RAM going to be such a huge die real estate problem? Besides that if you really need to optimize the size it is almost always better to cascade a FIFO with another FIFO.

e.g. say you need 33 you could just cascade a 32 deep FIFO with a 2 deep FIFO or a 4 deep FIFO.

With a FIFO it's almost always a good idea to have some extra headroom and not design it for the absolute minimum size. Designing for minimum size pretty much guarantees future problems possibly including field returns.

 

[FvM]

I mean, the register hack is an elegant solution within the assumptions of the question, but not in an objective sense.

 

[ThisIsNotSam]

I'm not sure what the limitations on RAM sizes in an ASIC are (haven't worked on ASICs for decades), but is going from say a 33 deep RAM to a 64 deep RAM going to be such a huge die real estate problem? Besides that if you really need to optimize the size it is almost always better to cascade a FIFO with another FIFO.

most SRAM compilers will generate the same block whether you want 33 or 64. In this specific case of 33, it would be a good idea to let the RAM handle 32 elements and the 33rd you do with logic. The wr/rd/full/empty pointer logic is nearly identical anyway.

 

[ads-ee]

most SRAM compilers will generate the same block whether you want 33 or 64. In this specific case of 33, it would be a good idea to let the RAM handle 32 elements and the 33rd you do with logic. The wr/rd/full/empty pointer logic is nearly identical anyway.

The point I was making is that they wouldn't be able to get any savings by having a RAM that is 33 vs 64 as I thought the underlying RAM would always be 64. Also how much of a die real estate impact would there be between adding logic for the extra 33rd entry vs using a larger RAM for the FIFO.

Which I why I mentioned in post #29 using logic to create the 33rd element of such a FIFO.

 

[ThisIsNotSam]

The point I was making is that they wouldn't be able to get any savings by having a RAM that is 33 vs 64 as I thought the underlying RAM would always be 64. Also how much of a die real estate impact would there be between adding logic for the extra 33rd entry vs using a larger RAM for the FIFO.

Which I why I mentioned in post #29 using logic to create the 33rd element of such a FIFO.

agreed, shrinking from 64 to 33 can have zero impact depending on how the compiler behaves.