Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

6.4    SELF-TIMED FIRST-IN FIRST-OUT BUFFER

The principles of self-timed systems have been known for many years, but such systems are rarely implemented because of their complex hardware, despite the advantages of flexible data rates and the avoidance of metastability problems. The self-timed environment prototypes (STEPs) are a collection of primitives used for implementing self-timed systems. The example discussed here was proposed by Sutherland [Suther89]. Many computing applications use a first in, first out (FIFO) buffer, often implemented as a simple circular queue. This is a memory structure that will hold a sequence of data, and output it in the same order as entered. To build a circular-queue FIFO in a synchronous environment, one must use memory elements that are addressed by two counters acting as pointers. The “in” pointer indicates the address to be filled next, while the “out” pointer identifies the first location to be read. The state of the FIFO, full or empty, is calculated by subtracting “out” from “in”. FIFO control is complicated by synchronization issues and may be unreliable if the FIFO filling and FIFO emptying processes are asynchronous. Sutherland’s self-timed FIFO design is entirely different. The basic operation resembles flow through a pipeline. Data are written to one end and read out from the other. The state of each memory location is either full or empty. If a location is empty, it will pass data through. However, if it is full, it will maintain ...