The memory devices discussed thus far are essentially linear arrays of bitssurrounded by a minimal quantity of interface logic to move bits between theport(s) and the array. First-in-?rst-out (FIFO) memories are special-purposedevices that implement a basic queue structure that has broad application incomputer and communications architecture. Unlike other memory devices,a typical FIFO has two unidirectional ports without address inputs: one forwriting and another for reading. As the name implies, the ?rst data written isthe ?rst read, and the last data written is the last read. A FIFO is not a randomaccess memory but a sequential access memory. Therefore, unlike a conventionalmemory, once a data element has been read once, it cannot be read again,because the next read will return the next data element written to the FIFO.By their nature, FIFOs are subject to over?ow and under?ow conditions.Their ?nite size, often referred to as depth, means that they can ?ll up if readsdo not occur to empty data that has already been written. An over?ow occurswhen an attempt is made to write new data to a full FIFO. Similarly, an emptyFIFO has no data to provide on a read request, which results in an under?ow.
A FIFO is created by surrounding a dual-port memory array generally SRAM,but DRAM could be made to work as well for certain applications with a writepointer, a read pointer, and control logic as shown in Fig. 4.18.
FIGURE 4.18 Basic FIFO architecture.
A FIFO is not addressed in a linear fashion; rather, it is made to form a continuousring of mem- ory that is addressed by the two internal pointers. The fullness of theFIFO is determined not by the absolute values of the pointers but by their relativevalues. An empty FIFO begins with its read and write pointers set to the samevalue. As entries are written, the write pointer increments. As entries are read,the read pointer increments as well. If the read pointer ever catches up to thewrite pointer such that the two match, the FIFO is empty again. If the read pointerfails to advance, the write pointer will eventually wrap around the end of thememory array and become equal to the read pointer. At this point, the FIFO isfull and cannot accept any more data until reading resumes. Full and empty ?agsare generated by the FIFO to provide status to the writing and reading logic.Some FIFOs contain more detailed fullness status, such as signals that representprogrammable fullness thresholds.
The interfaces of a FIFO can be asynchronous (no clock) or synchronous(with a clock). If syn- chronous, the two ports can be designed to operate witha common clock or different clocks. אל על- though older asynchronous FIFOs arestill manufactured, synchronous FIFOs are now more common. SynchronousFIFOs have the advantage of improved interface timing, because ?ops placedat a devices inputs and outputs reduce timing requirements to the familiar setup,hold, and clock-to-out speci?cations. Without such a registered interface,timing speci?cations become a function of the devices internal logic paths.
One common role that a FIFO ?lls is in clock domain crossing. In such anapplication, there is a need to communicate a series of data values from ablock of logic operating on one clock to another block operating on a differentclock. Exchanging data between clock domains requires special attention,because there is normally no way to perform a conventional timing analysisacross two differ- ent clocks to guarantee adequate setup and hold times atthe destination ?ops. Either an asynchronous FIFO or a dual-clock synchronousFIFO can be used to solve this problem, as shown in Fig. 4.19.
The dual-port memory at the heart of the FIFO is an asynchronous elementthat can be accessed by the logic operating in either clock domain. A dual-clocksynchronous FIFO is designed to handle arbitrary differences in the clocksbetween the two halves of the device. When one or more bytes are writtenon clock A, the write-pointer information is carried safely across to the clockB domain within the FIFO via inter-clock domain synchronization logic. Thisenables the read-control inter- face to determine that there is data waiting tobe read. Logic on clock B can read this data long after it has been safelywritten into the memory array and allowed to settle to a stable state.
Another common application for a FIFO is rate matching where a particulardata source is bursty and the data consumer accepts data at a more regular rate.One example is a situation where a se- quence of data is stored in DRAM andneeds to be read out and sent over a communications interface one byte at a time.The DRAM is shared with a CPU that competes with the communicationsinterface for memory bandwidth. It is known that DRAMs are most ef?cientwhen operated in a page-mode burst. Therefore, rather than perform acomplete read-transaction each time a single byte is needed for thecommunications interface, a burst of data can be read and stored in a FIFO.Each time the interface is ready for a new byte, it reads it from the FIFO.In this case, only a single-clock FIFO is required, because these devicesoperate on a common clock domain. To keep this process running smoothly,control logic is needed to watch the state of the FIFO and perform a new burstread from DRAM when the FIFO begins to run low on data. This scheme isillustrated in Fig. 4.20.
FIGURE 4.19 Clock domain crossing with synchronous FIFO.
For data-rate matching to work properly, the average bandwidth over time ofthe input and output ports of the FIFO must be equal, because FIFO capacity is?nite. If data is continuously written faster than it can be read, the FIFO willeventually over?ow and lose data. Conversely, if data is continuously read fasterthan it can be written, the FIFO will under?ow and cause invalid bytes to beinserted into the outgoing data stream. The depth of a FIFO indicates how largea read/write rate disparity can be tolerated without data loss. This disparity isexpressed as the product of rate mismatch and time. A small mismatch can betolerated for a longer time, and a greater rate disparity can be tolerated fora shorter time.
In the rate-matching example, a large rate disparity of brief duration is balancedby a small rate disparity of longer duration. When the DRAM is read, a burstof data is suddenly written into the FIFO, creating a temporarily large ratedisparity. Over time, the communications interface reads one byte at a time whileno writes are taking place, thereby compensating with a small disparity over time.
DRAM reads to re?ll the FIFO must be carefully timed to simultaneously preventover?ow and under?ow conditions. A threshold of FIFO fullness needs to beestablished below which a DRAM read is triggered. This threshold must guaranteethat there is suf?cient space available in the FIFO to accept a full DRAM burst,avoiding an over?ow. It must also guarantee that under the worst-case responsetime of the DRAM, enough data exists in the FIFO to satisfy the communicationsinterface, avoiding an under?ow. In most systems, the time between issuing aDRAM read request and actu- ally getting the data is variable. This variabilityis due to contention with other requesters (e.g., the CPU) and waiting foroverhead operations (e.g., refresh) to complete.
FIGURE 4.20 Synchronous FIFO application: data rate matching.
על ידי : E-book Complete_Digital_Design
