Designing a First-In, First-Out (FIFO) Buffer

The goal of this post is to discuss communication from three external systems to a single FIFO buffer, which must track overflows and underflows. The FIFO is designed to handle 8 data words on port 1 or port 2, then transmit the output to port 3. Port 1 and port 2 use a sender originated protocol and wait for the FIFO to acknowledge before transmission. Port 3 uses a receiver originated protocol and requested data from the FIFO.

High Level Architecture

With regards to the architecture used in the FIFO, 8 8 bit registers were used to hold each word supplied in on ports 1 and 2. There is a multiplexer, which is used to select between port 1 and port 2 as inputs into each of the registers. The decoded write pointer determines which register should be clocked to take in the latest value. As for the output, an output register was used, which was a fed the output from another multiplexer which selected which register to grab the output from.

External system 1 and external system 2 were designed using a sender originated protocol, whereas external system 3 uses receiver originated protocol. These systems were trivial to design. Within the 8 byte FIFO, port 1 and port 2 were modified sender originated protocol receivers, which make a token request to an arbiter. Next the control for port 3 was designed based on a modified receiver originated protocol sender to also function with token requests. Finally an arbiter was designed to handle and prioritize all of the token requests. The arbiter responds with a grant signal to the three ports. Only one grant signal is high at any point in time from the arbiter, controlling access to the shared resource.

FIFO Datapath

In the architecture above, 8 8-bit registers were used to act as a FIFO. An 8-bit output register was also used to stabilize the outputs being written to port 3. A multiplexer was used to control what was written to the output register. Another multiplexer was used to switch between applying port 1 and port 2 to the FIFO.

The critical path of this system is from the mux controlling inputs to the output register. The first multiplexer takes 3Δ, the register will take 1Δ, followed by another multiplexer, thus another 3Δ. This then is put into a register, so another delay of 1Δ occurs. The total delay of the circuit is 8Δ.

External System 1/2:

Control for External System 1/2

Output = {dready, wr}, Start State = A



External System 3:

Control for External System 3

Output = {dreq, rd}, Start State = A



Port 1:

Control for Port 1

Output = {treq1, dack1, rd1}, Start State = A



Port 2:

Control for Port 2

Output = {treq2, dack2, rd2}, Start State = A



Port 3:

Control for Port 3

Outputs = {treq3, dready3, wr}, Start State = A



Arbiter:

Arbiter for Port 1

Outputs = {tg3, tg2, tg1}, Start State = A
Where tgrant3 = tg3&~tg2&~tg1, tgrant2 = tg2&~tg3&~tg1, tgrant1 = tg1&~tg2&~tg3



Due to the lack of combinational logic within the architecture, there is no good way to improve the speed of the system, especially since pipelining is not possible. As for the throughput, slight changes to the arbiter could be made to enable more data through the system, by allowing both port 3 and either port 1 or 2 to access the FIFO at the same time. This would be feasible since these tasks are completely independent of each other. Using the improved approach, when the token is granted to port 1, and the system is waiting for data to be ready, port 3 could still read data from the FIFO, by granting a separate token.

proj3A.dat:

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50



proj3B.dat:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51



Simulation Results