We need a FIFO when we are transferring data from a faster clock domain to a slower clock domain. The FIFO keeps the data stored until the receiving domain is ready to read it so that there is no loos of data being transferred. If we know the frequency of both the domains and the size of data being transferred (burst size), it is fairly an easy affair to calculate the FIFO size required using unitary method.
I always refer to this PDF, which I consider to be the holy grail of the FIFO Depth calculation questions. 90% of the time this PDF will be enough for you to solve any kind of depth calculation question. In this article, I am going to talk about the rest of the 10%. There are few questions, the format of which deviates from the questions mentioned in the PDF and they can really catch you off-guard if you are not prepared for it. Let us see them.
One thing you always need to keep in mind is the burst size. It is not possible to solve these kinds of problems without the knowledge of burst size. Burst size is basically gaps in data being written. As the receiving domain is reading slow, we should give it some time to read the old data before writing the new data. If burst size is not mentioned in the question, the first step should be to calculate the burst size itself. There will be enough parameters given in the problem to do the same. If the interviewer says there is no burst size and that the data is coming continuously, then he just made the solution easier for you. You will need an infinite depth FIFO in that case because it will be impossible to store all the data if it is coming continuously without gaps. The receiving domain just cannot read the data fast enough and hence at some point of time, any size of FIFO will not be enough.
Question Type 1
There is one such question mentioned in the above PDF in question number 9. Although in the question, the burst size is mentioned, the final answer will be the same even if it was not provided. Using only the writing data and outgoing data values provided in the question, we can come up with the worst case burst size to be 160, like the PDF author already did. I am mentioning this because a similar question can be asked in an interview without providing the burst size info, and you should be able to solve it after this information.
Question Type 2
A producer can produce up to 2 writes per 10 cycles, while reader can read up to 10 reads in 40 cycles. What should be the FIFO depth to avoid bubbles?
For these types of questions, we already know that we must consider the worst case for both reads and writes. The worst case for write being writing as early as possible and worst case for read being reading as late as possible. We also see that the gaps in data being written are there are it is not a case of continuous writing.
If we consider the read condition given in the question, the worst case scenario would be reading in the last 12 cycles of the 40 cycles (cycles 29-40).
For write, the worst case scenario would be writing the 2 data in the beginning of the 10 write cycle (cycle 1 and 2).
Now, we see that we are starting reading only in the 39th cycle, and till that time we have already written 6 data (in cycles 1, 2, 11, 12, 21 & 22). The data which will be written in cycle 31 and 32 would be read as soon as it is written. This means that we are not able to read only 6 data in time, and we need to store that data.
This means that the FIFO depth should be 6.
Question Type 3
Write side writes 18 bits/cycle with a frequency of 60 MHz.
Read side reads 20 bits/cycle with a frequency of 36 MHz.
Burst size is 100. Calculate FIFO Depth.
In this question, with read and write frequency, the number of bits being written and read is also given. So, we need to calculate the FIFO depth in terms of the number of bits it needs to store to avoid missing any data. Let us see how to do that.
For a 100 burst size, writes in one cycle (1/60 us) = 100 * 18 = 1800 bits
Reads in the same time (calculated using conventional method) = (100 * 36) / 60 = 60 reads = 60 * 20 bits = 1200 bits
This means that we are not able to read (1800 – 1200 =) 600 bits in a given time and hence the FIFO Depth should be 600 bits.
These were the three unique questions that I wanted to share with you. It is pretty easy once you get the hang of it. I also think that it’s a very important topic as I have seen these get asked in pretty much every company including FAANG.
See you in the next article!