Wikipedia defines the FIFO in electronics as under:

FIFOs are commonly used in electronic circuits for buffering and flow control which is from hardware to software. In its hardware form, a FIFO primarily consists of a set of read and write pointers, storage and control logic.

I understand in hardware what is storage and what is control logic. But in this definition I don't understand the meaning of read and write pointers
Is this simply a kind of Program Counter?

A FIFO is a First In First Out memory. You can think of data being shifted in one end and shifted out the other, with the amount of data in the FIFO being allowed to grow up to some maximum limit.

However, actually shifting data around in memory is costly to do in hardware. A better way is to use a memory more normally but make it look like a circular buffer by manipulation of the next address to write to and read from. These addresses live in separate registers, and are often called the read pointer and the write pointer.

Here is a illustration of the state for a simple FIFO using a 8-word memory:

The next incoming word will be written to the empty word at address 1 (the value of the write pointer), then the write pointer incremented to 2. The next read request will fetch the word at 5 (the value of the read pointer), then the read pointer is incremented by 1. In this example, the addresses are automatically circular if the pointers are 3 bits wide. Adding 1 to 7 yields 0 in 3-bit unsigned math.

Complete FIFO systems need ways to indentify the full and empty conditions. There are various schemes for this. A separate register could be used to keep track of how many words are in the FIFO, which is 4 in the snapshot shown above.

A useful scheme for a firmware implementation is to compare the read and write pointers. You could, for example, decide that both pointers equal is FIFO empty, and write one behind read (after wrapping) is FIFO full. Note that such schemes will leave one word of the FIFO unused. You end up spending a piece of state somewhere to allow detection of full and empty, whether that's a separate register or a unusable word in the FIFO. The advantage of this scheme is that reads and writes can happen independently without conflict, so such a FIFO doesn't need a mutex between reading and writing. For example, you don't have to disable interrupts when reading because no harm is done if a interrupt routine pushes a word onto the FIFO while foreground code is trying to read.

  • This is what I was looking for- excellent explanation indeed!! – gpuguy Jan 22 '14 at 15:05
  • I'm having a bit of trouble with the last sentence. It seems that to avoid having to disable the interrupt where the write occurs, the comparison of pointers for the read would have to be accomplished in a single instruction and the increment of the read pointer (after the read) would also have to be accomplished with a single instruction. For an 8-bit processor, this would likely require the array to be 256 bytes. Any masking of the pointers (or checking and correcting for overflow) would require additional instructions during which the interrupt must not occur. Am I wrong? – Tut Jan 23 '14 at 11:40
  • @Tut: Yes, incrementing and reading the pointers would need to be atomic operations in that case. Usually the hardware guarantees that. On a 8 bit machine, you'd generally not want to use more RAM than 256 locations for the FIFO anyway. On a 16 bit machine you get 64k. The point is that writing and reading the FIFO don't have to be atomic with updating the pointers, as long as the pointers are updated after the read or write. This is not true of other schemes to track FIFO full/empty. – Olin Lathrop Jan 23 '14 at 12:41
  • Ahhh! I think I see the way. I was concerned that the pointers would have to be updated in a single instruction, but that could be accomplished if the new pointer value is calculated into a separate variable and then transferred to the actual pointer with a single instruction ... thanks! – Tut Jan 23 '14 at 12:55
  • As you said both read pointer and write pointer are incremented after respective read and write operation. That means both pointer values should be same for both full and empty condition. Then how we can distinguish between full and empty condition? – tollin jose May 4 '16 at 12:49

Olin's answer covers it completely.

I just want to add that in digital HW, FIFOs are often used in order to transfer multi-bit data between asynchronous clock domains (Clock Domain Crossing - CDC). This topic might be of no interest to you right now (it is kind of an advanced one), but I think it should be covered for completeness.

These special FIFOs are called asynchronous (async) FIFOs, and while they are similar in structure to basic FIFOs, there are two key additions:

  • Read/write ointers are converted into Gray Code before being transferred between asynchronous clock domains
  • The converted values are synchronized to the destination domain's clock using synchronizers

This scheme ensures that multi-bit data will be transferred without metastability issues and avoiding data corruption due to independent synchronization of bits.

A logical structure of async FIFO: enter image description here

A program counter tracks the last instruction executed in a program. In a FIFO, the read and write pointers track the last bit or byte last read or written. So, they are similar concepts, but for different things.

The concept is not so difficult if you strip away the jargon. If someone gave you a long list of numbers and asked you to read them in order, you might put your finger on the page to help track your place. Your finger is a read counter.

  • I'm not sure why you keep using the word "last". In most ISAs, the PC points to the next instruction to be executed, and in most FIFOs, the read and write pointers point to the next positions to be read and written, respectively. – Dave Tweed Jan 22 '14 at 14:41
  • @DaveTweed whether it's the "last" or the "next" depends on exactly when in the instruction cycle you look. – Phil Frost Jan 22 '14 at 15:23

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.