FIFO

Introduction to FIFO

In the computer, the first-in first-out queue is a traditional sequential execution method. The first-entered instruction is completed and retired first, followed by the second instruction (the instruction is the program code that the computer responds to the user's operation, for the user Is transparent). As shown in Figure 1, when the CPU is too late to respond to all instructions in a certain period of time, the instructions will be arranged in the FIFO queue. For example, the 0th instruction enters the queue first, followed by the 1st instruction, the 2nd instruction. When the CPU After the current instruction is completed, instruction 0 will be taken out of the queue and executed first. At this time, instruction 1 will take over the position of instruction 0. Similarly, instructions 2 and 3. will move forward one position, so explain Are you clear?

FIFO is the simplest in the queue mechanism. There are FIFO queues on each interface. On the surface, FIFO queues do not provide any QoS (Quality of Service) guarantees. Even many people think that FIFO is not one in the strict sense. This kind of queue technology is not the case. FIFO is the basis of other queues. FIFO also affects the key indicators for measuring QoS: packet discard, delay, and jitter. Since there is only one queue, naturally there is no need to consider how to classify the complex traffic of the packets, nor how to take the next packet, how much to take, and because the packets are taken in order, the FIFO does not need to reorder the packets. Simplifying these implementations actually improves the guarantee for packet latency.

FIFO is concerned about the length of the queue. The length of the queue will affect the delay, jitter, and packet loss rate. Because the queue length is limited, it may be filled, which involves the discarding principle of the mechanism. A common drop principle is called the Tail Drop mechanism. Simply put, if the queue is full, subsequent incoming packets are discarded, and there is no mechanism to ensure that subsequent packets can squeeze out packets already in the queue. In this mechanism, if a longer queue length is defined, the queue is not easy to fill up, and fewer packets are dropped. However, if the queue length is too long, there will be a problem of delay. In general, delay The increase in will cause the jitter to increase. If a shorter queue is defined, the problem of delay can be solved, but the number of packets with Tail Drop becomes more.

Brief introduction of FIFO queue principle

The FIFO queue does not classify the packets. When the speed at which the packets enter the interface is faster than the speed at which the interface can be sent, the FIFO allows the packets to enter the queue according to the order in which the packets arrive at the interface. At the same time, the FIFO allows the packets to enter at the exit of the queue. The order of the team is to leave the team. The advanced messages will be sent out first, and the later messages will be sent out later.

The FIFO queue has the advantages of simple processing and low overhead. However, FIFO does not distinguish message types and adopts a best-effort forwarding mode, so that the delay of time-sensitive real-time applications (such as VoIP) cannot be guaranteed, and the bandwidth of critical services cannot be guaranteed.

Use FIFO

FIFO is generally used for data transmission between different clock domains. For example, one end of the FIFO is AD data acquisition, and the other end is the PCI bus of the computer. Assuming that the AD acquisition rate is 16-bit 100K SPS, then the amount of data per second is 100K ×16bit=1.6Mbps, and the PCI bus speed is 33MHz, the bus width is 32bit, and its maximum transmission rate is 1056Mbps. FIFO can be used as a data buffer between two different clock domains. In addition, FIFO can be used for data interfaces with different widths, such as 8-bit data output of the single-chip microcomputer, and 16-bit data input of the DSP. The FIFO can be used to match the data when the microcomputer is connected to the DSP.

Important parameters

FIFO width: the WIDTH that is often seen in English materials, it refers to the data bits of a FIFO read and write operation, just like the MCU has 8 and 16 bits, ARM32 bits, etc., the width of the FIFO is in a single chip The finished IC is fixed and optional. If you use FPGA to implement a FIFO yourself, the data bit, that is, the width can be defined by yourself.

　　 FIFO depth: THE DEEPTH, which refers to how many N-bit data the FIFO can store (if the width is N). Such as an 8-bit FIFO, if the depth is 8, it can store 8 8-bit data, and the depth is 12, it can store 12 8-bit data. The depth of the FIFO can be large or small. Personally think that the calculation of the FIFO depth There is no one fixed formula. In the actual work of FIFO, the full/empty flag of its data can control the continued writing or reading of data. In a specific application, it is impossible to accurately calculate the required FIFO depth from some parameters. This is feasible in the ideal state where the write speed is greater than the read speed, but the FIFO depth used in practice is often greater than the calculated value. . Generally speaking, according to the specific conditions of the circuit, it is enough to estimate a rough width and depth in consideration of system performance and FIFO cost. For applications where the write speed is slower than the read speed, the depth of the FIFO is determined by those specific requirements based on the data structure read and the data read.

　　Full flag: A signal sent by the FIFO status circuit when the FIFO is full or about to be full, to prevent the FIFO write operation from continuing to write data to the FIFO and causing overflow (overflow).

　　Empty flag: A signal sent by the FIFO status circuit when the FIFO is empty or about to be empty, to prevent the FIFO read operation from continuing to read data from the FIFO and causing invalid data read (underflow).

　　 Read clock: The clock followed by the read operation, and reads data temporarily at each clock edge.

　　 Write clock: The clock followed by the write operation, and data is temporarily written at each clock edge.

　　Read pointer: point to the next readout address. Add 1 automatically after reading.

　　 Write pointer: Point to the next address to be written, and add 1 automatically after writing.

　　Reading and writing pointer is actually the address of reading and writing, but this address cannot be selected arbitrarily, but continuous.

　　4. FIFO classification

　　 According to the clock domain where FIFO works, FIFO can be divided into synchronous FIFO and asynchronous FIFO. Synchronous FIFO means that the read clock and write clock are the same clock. Read and write operations occur at the same time when the clock edge comes. Asynchronous FIFO means that the read and write clocks are inconsistent, and the read and write clocks are independent of each other.

　　5. Difficulties in FIFO design

　　The difficulty of FIFO design is how to judge the empty/full state of FIFO. In order to ensure the correct writing or reading of data without overflow or empty reading, it must be ensured that the FIFO cannot be written when it is full. The read operation cannot be performed in the empty state. How to judge the full/empty of FIFO becomes the core problem of FIFO design. Since the synchronous FIFO is rarely used, only the problem of the empty/full flag of the asynchronous FIFO is described here.

　　In the design of the flip-flop, it is inevitable that it will encounter the problem of metastable state (the metastable state is not introduced here, you can check the relevant information). In circuits involving flip-flops, the metastable state cannot be completely eliminated, and we can only find a way to minimize the probability of its occurrence. One method is to use Gray code. The Gray code is converted by only one bit between two adjacent symbols (the binary code is in many cases that many symbols change simultaneously). This will avoid metastability when the counter is synchronized with the clock. However, Gray code has a disadvantage that it can only define a depth of 2^n, and cannot define the depth of the FIFO as arbitrarily as a binary code, because Gray code must loop through a 2^n, otherwise it cannot guarantee the two adjacent symbols. The condition differs by one bit, so it is not a real Gray code. The second is to use redundant triggers. Assuming that the probability of a metastable state of a trigger is P, then the probability of metastable state of two cascaded triggers is the square of P. But this will increase the delay. The occurrence of metastability will cause an error in the FIFO, and the address pointer sampled by the read/write clock will be different from the real value, which will result in the wrong address being written or read. Due to the effect of delay, the generation of the empty/full flag does not necessarily appear when the FIFO is really empty/full. The empty/full flag may appear before the FIFO is empty/full. This is not bad, as long as there is no overflow or underflow in the FIFO.

　　Many articles about FIFO are actually discussing different algorithms of empty/full flag.

　　　 In Vijay A. Nebhrajani's "Asynchronous FIFO Structure", the author proposes two algorithms for FIFO empty/full flags.

　　 The first algorithm: construct a FIFO with a pointer width of N+1 and a depth of 2^N bytes (for convenient comparison, the Gray code pointer is converted into a binary pointer). When the highest bit in the binary code of the pointer is inconsistent and the other N bits are equal, the FIFO is full (in Clifford E. Cummings' article, the gray code indicates that the first two bits are not the same, and the last two LSBs are the same, which is full. It is the same as the MSB which is replaced by the binary representation. When the pointers are exactly equal, the FIFO is empty. This may not be easy to see. Let me give an example to illustrate: how a FIFO with a depth of 8 bytes works (using a pointer that has been converted to binary). FIFO_WIDTH=8, FIFO_DEPTH= 2^N = 8, N=3, the pointer width is N+1=4. Initially both rd_ptr_bin and wr_ptr_bin are "0000". At this time, 8 bytes of data are written in the FIFO. wr_ptr_bin = "1000", rd_ptr_bin = "0000". Of course, this is the full condition. Now, suppose that the read operation is performed 8 times, so that rd_ptr_bin = "1000", which is the null condition. The other 8 write operations will make wr_ptr_bin equal to "0000", but rd_ptr_bin is still equal to "1000", so the FIFO is full.

　　 Obviously the starting pointer need not be "0000". Suppose it is "0100" and the FIFO is empty, then 8 bytes will make wr_ptr_bin = "1100", and rd_ptr_bin is still "0100". This again shows that the FIFO is full.

Vijay A. Nebhrajani's "Asynchronous FIFO Structure" article explains how to use Gray code to set the empty and full conditions, but did not explain why the depth of 8 FIFO read and write pointers use 3+1 bit Gray Code to achieve, while the Gray code of 3+1 bits can represent a depth of 16 bits, while the real FIFO only has 8 bits, what is going on? This problem is explained in the article by Clifford E. Cummings. The three-bit Gray code can represent the depth of 8 bits. If one bit is the most MSB, the gray code composed of this bit and the other three bits does not represent the new address, that is, 0100 of the gray code represents 7, and 1100 still represents 7, except that the Gray code enters a loop with a MSB of 1 after a loop with a MSB of 0, and then enters a loop with an MSB of 0. The other three-digit codes are still Gray codes, but This brings about a problem. After the cycle of 0100 is completed, it enters 1000. Two of them have changed instead of one. Therefore, the addition of one MSB makes the code in two places: 0100~1000, From 1100 to 0000, two symbols change, so the code is not a true Gray code. The increased MSB is to realize the calculation of the empty and full flag. Vijay A. Nebhrajani's article converts Gray code to binary, and then converts Gray code to propose empty and full conditions, only two conversions, and Clifford E. Cummings' article directly obtains empty and full conditions under Gray code conditions. In fact, the two are the same, but the implementation is different.

　　 The second algorithm: STYLE#2 mentioned in Clifford E. Cummings' article. It divides the FIFO address into 4 parts. Each part uses the MSB 00, 01, 11, and 10 of the upper two bits to determine whether the FIFO is going full or going empty. If the MSB of the upper two bits of the write pointer is less than the MSB of the upper two bits of the read pointer, the FIFO is "almost full".

　　 If the MSB of the upper two bits of the write pointer is greater than the MSB of the upper two bits of the read pointer, the FIFO is "almost empty."

　　 In Vijay A. Nebhrajani's "Asynchronous FIFO Structure" part three article also mentioned a method, that is, direction signs and thresholds. 75% of the FIFO capacity is set as the upper limit, and 25% of the FIFO capacity is set as the lower limit. When the direction sign exceeds the threshold, the full/empty sign is output, which is similar to STYLE #2 mentioned in Clifford E. Cummings' article. They are all conservative empty judgments. In fact, at this time, the output empty and full flag FIFO is not necessarily really empty/full.

　　 Having said that, we have clearly seen that the most critical thing in FIFO design is that different algorithms for generating empty/full flags produce different FIFOs. But whether it is accurate empty or conservative empty full is to ensure the reliability of FIFO work.