An asynchronous first in first out memory device eliminates the need for synchronizers. The device includes pipeline of data registers. The data registers include a first register to accept data writes of data and a last register data reads. Each register has an enable input to indicate a full condition allowing a read and an empty condition allowing a write. A bubble inserter circuit inserts a bubble in the first register to prevent a completely empty condition for all registers. Controllers are associated with each register to allow the bubble or written data to be passed from the first register to the last register. A near empty detect circuit is coupled to the registers to determine a nearly empty condition of the pipeline. An arbiter determines whether a data write proceeds or a bubble insertion proceeds for the first register when the plurality of registers is near empty.

TECHNICAL FIELD

The present disclosure relates generally to data registers and more specifically to use of FIFO circuits for memory operations.

BACKGROUND

Use of (first in first out) FIFO memory registers in digital designs for buffering and flow control has been widespread for many years. The emergence of system on chip (SOC) and networks on chip (NOC) for internal connections have made it imperative to ensure correct flow of data across the chip or die. The various computing components in such networks are often synchronized on different clocks. Thus data transfer in such systems requires an asynchronous first in first out (FIFO) register to assist in transferring data between differently clocked components.

An asynchronous FIFO refers to a FIFO design where data values are written sequentially into a FIFO buffer using one clock domain, and the data values are sequentially read from the same FIFO buffer using another clock domain, where the two clock domains are asynchronous to each other. The first in first out (FIFO) buffer serves as a memory buffer between two asynchronous devices each with simultaneous write and read access to and from the FIFO. The accesses are independent of one another. Data written into a FIFO is sequentially read out in a pipelined manner. Thus the first data word written into a FIFO will be the first data word that is read out. The fundamental architecture of a FIFO has a write port, a read port, and memory locations. Each port has its own associated pointer that points to a location in memory. After a reset, both write and read pointers will be at the first memory location within the FIFO where the memory registers are empty. When the write address register again reaches the read address register, the FIFO registers are full. Every write operation will cause the write pointer to increment to the next address in memory thus filling registers, while every read operation will increment the read pointer to the next memory location as each register is emptied.

In order to synchronize read and write operations, a synchronizer circuit is used for the comparison of the addresses of the pointers. Such a comparison will determine whether the FIFO is empty or full and thus whether either read or write operations may be performed respectively. A synchronizer includes logic devices such as flip flops that compare the addresses of data on the read and write side. Such circuits trade off latency for reliability. Reliability requires more stages of flip flop circuits, but increases the latency of the synchronization since the address comparisons must flow through each flip flop stage. In a conventional FIFO, the status signals (or addresses from which they are generated) must pass through synchronizers before usage in the receiving clock domain. The stage count in these synchronizers determines their latency/reliability trade-off.

One common technique for designing an asynchronous FIFO is to use Gray code pointers that are synchronized into the opposite clock domain before generating synchronous FIFO full or empty status signals. One Gray code counter style uses a single set of flip-flops as the Gray code register. While transferring pointer information between independent clock domains in an asynchronous FIFO, each bit, new or old of the pointer, needs to be sent. If more than one bit in the multi-bit pointer is changing at the sampling point, an incorrect binary value can be propagated. By guaranteeing that only one bit can be changing, Gray codes guarantee that the only possible sampled values are the new or old multi-bit value, ensuring reliable flag information indicating whether the read and write registers are full or empty.

This design requires a multi-bit synchronizer in each port, to make the other port's address register usable. This synchronizer is large, since many bits need to be simultaneously synchronized, and these bits may need to be converted to and from Gray code in order for the synchronization to be well-behaved. This synchronizer also sits in a fixed location in the design, resulting in a fixed latency/reliability tradeoff. This tradeoff is a consequence of the fact that the more time a synchronizer has, the more latency it injects into the surrounding system, and the more reliable is its operation.

SUMMARY

One example is a first in first out (FIFO) memory device that includes an extra bit for each register in a pipeline to indicate the insertion of a bubble thereby preventing the FIFO from ever being in a completely empty state and eliminating the need for synchronization circuitry. The FIFO memory device includes a pipeline of registers that include a first register accepting data from a write device at a first clock speed and a last register that allows a device to read data at a second different clock speed. The FIFO memory device has a near empty detect circuit that will cause a bubble inserter circuit to insert a bubble in the first register and set a flag in the extra bit indicating a bubble. This requires no synchronization between the read and write devices since if the clock speeds for the read devices are faster, the read can always be performed since the registers will never be empty with the bubbles. The read operation is not performed for registers having the bit indicating a bubble. Since the FIFO is never empty, no synchronization is required, thereby reducing latency required by synchronization circuits in known FIFO registers.

Additional aspects will be apparent to those of ordinary skill in the art in view of the detailed description of various embodiments, which is made with reference to the drawings, a brief description of which is provided below.

DETAILED DESCRIPTION

An illustrative example of a computing system that includes data exchange in an integrated circuit component die is a programmable logic device (PLD)100in accordance with an embodiment is shown inFIG. 1. The programmable logic device100has input/output circuitry110for driving signals off of device100and for receiving signals from other devices via input/output pins120. Interconnection resources115such as global and local vertical and horizontal conductive lines and buses may be used to route signals on device100.

Input/output circuitry110includes conventional input/output circuitry, serial data transceiver circuitry, differential receiver and transmitter circuitry, or other circuitry used to connect one integrated circuit to another integrated circuit.

Interconnection resources115include conductive lines and programmable connections between respective conductive lines and are therefore sometimes referred to as programmable interconnects115.

Programmable logic region140may include programmable components such as digital signal processing circuitry, storage circuitry, arithmetic circuitry, or other combinational and sequential logic circuitry such as configurable register circuitry. As an example, the configurable register circuitry may operate as a conventional register. Alternatively, the configurable register circuitry may operate as a register with error detection and error correction capabilities.

The programmable logic region140may be configured to perform a custom logic function. The programmable logic region140may also include specialized blocks that perform a given application and have limited configurability. For example, the programmable logic region140may include specialized blocks such as configurable storage blocks, configurable processing blocks, programmable phase-locked loop circuitry, programmable delay-locked loop circuitry, or other specialized blocks with possibly limited configurability. The programmable interconnects115may also be considered to be a type of programmable logic region140.

Programmable logic device100contains programmable memory elements130. Memory elements130can be loaded with configuration data (also called programming data) using pins120and input/output circuitry110. Once loaded, the memory elements each provide a corresponding static control signal that controls the operation of an associated logic component in programmable logic region140. In a typical scenario, the outputs of the loaded memory elements130are applied to the gates of metal-oxide-semiconductor transistors in programmable logic region140to turn certain transistors on or off and thereby configure the logic in programmable logic region140and routing paths. Programmable logic circuit elements that may be controlled in this way include parts of multiplexers (e.g., multiplexers used for forming routing paths in programmable interconnects115), look-up tables, logic arrays, AND, OR, NAND, and NOR logic gates, pass gates, etc.

Memory elements130may use any suitable volatile and/or non-volatile memory structures such as random-access-memory (RAM) cells, fuses, antifuses, programmable read-only-memory memory cells, mask-programmed and laser-programmed structures, combinations of these structures, etc. Because memory elements130are loaded with configuration data during programming, memory elements130are sometimes referred to as configuration memory, configuration RAM (CRAM), or programmable memory elements.

The circuitry of device100may be organized using any suitable architecture. As an example, the logic of programmable logic device100may be organized in a series of rows and columns of larger programmable logic regions each of which contains multiple smaller logic regions. The smaller regions may be, for example, regions of logic that are sometimes referred to as logic elements (LEs), each containing a look-up table, one or more registers, and programmable multiplexer circuitry. The smaller regions may also be, for example, regions of logic that are sometimes referred to as adaptive logic modules (ALMs), configurable logic blocks (CLBs), slice, half-slice, etc. Each adaptive logic module may include a pair of adders, a pair of associated registers and a look-up table or other block of shared combinational logic (i.e., resources from a pair of LEs—sometimes referred to as adaptive logic elements or ALEs in this context). The larger regions may be, for example, logic array blocks (LABs) or logic clusters of regions of logic containing for example multiple logic elements or multiple ALMs.

During device programming, configuration data is loaded into device100that configures the programmable logic regions140so that their logic resources perform desired logic functions. For example, the configuration data may configure a portion of the configurable register circuitry to operate as a conventional register. If desired, the configuration data may configure some of the configurable register circuitry to operate as a register with error detection and error correction capabilities.

Frequently a FIFO memory device is inserted simply to compensate for an unknown phase relationship between a sending device and a receiver device in systems with multiple devices exchanging data such as the PLD100inFIG. 1. Another common case is a source-synchronous link where sender and receiver device clocks ultimately derive from the same clock source but with an unknown phase in each case. A simpler FIFO memory device without synchronization circuits may be used in this case.

FIG. 2is a block diagram of a pipeline-based self-stuffing FIFO memory device200augmented with self-stuffing circuitry to insert bubbles and thereby eliminate the need for synchronization circuits. A bubble is a set of dummy values that substitute for actual data such as the data stored in the respective register from a previous write that has already been read. The FIFO200includes a series of registers202,204,206, and208, which are arranged in a pipeline to pass data written to the first register202by a write device to the second register204and in sequence to the last register208for reads by a read device. In this example, write or transmitter devices that are clocked from a first clock write to the first memory register202while other read or receiver devices that are clocked from a second different clock read from the last register208. The registers202and208are accessed by a data input bus210and a data output bus212respectively.

Each of the registers202,204,206, and208has an associated one bit latch222,224,226, and228. As will be explained below, the one bit latches222,224,226, and228indicate whether a bubble has been inserted in the particular associated register. Although there are four registers in this example, it is to be understood that there can be any number of registers in the FIFO200. Each of the registers202,204,206, and208and their associated one bit latches222,224,226, and228are controlled by a corresponding latch controller circuit232,234,236, and238. Each of the latch controller circuits such as the latch controller circuit232has an enable output E, a receiver port L and a transmitter port R. As shown inFIG. 2, signals may be passed from the transmitter port R of one controller such as the controller232to the receiver port L of the next controller234when writes are performed in sequence for each corresponding register in the pipeline. Correspondingly, when reads are performed, signals may be passed from the receiver port L of one controller such as the controller238to the transmitter port R of the next controller236in the pipeline. The latch controller for each register and one bit latch receives read and write requests and controls whether the corresponding register and one bit latch is enabled (respective inputs E1-E4on registers202,204,206, and208and latches222,224,226, and228) thereby allowing data to be written or not enabled, indicating the register has stored data to be read. Specifically, when a register such as the register208has been read, its controller such as the controller238then changes its enable input (E4) to allow data from either the write device or the previous register to be written.

A near empty detect circuit240is coupled to the enable outputs of the latch controllers232,234,236, and238in this example. A self-stuffing circuit or bubble inserter circuit250is coupled to the first one bit latch222and first latch controller232. The FIFO200in this example operates assuming that the clock regulating the devices writing data into the first register202of the FIFO200operate at the same or lower speed as the clock regulating the devices reading the data and thus the FIFO200might become empty. To compensate for this possibility, the bubble inserter circuit250may insert “bubbles” in the first register202, which is pipelined to the other registers204,206, and208, as needed if the FIFO200falls too far below half-full and thereby avoids the use of synchronization circuits to detect a completely physically empty condition in the FIFO200.

As shown inFIG. 2, the near empty detect circuit240has inputs for each of the enable state signals for the registers202,204,206, and208that are controlled from the latch controllers232,234,236, and238. The bubble inserter circuit250includes a write handshake connection252and a jam input254. The bubble inserter250includes a write handshake connection256and a bubble flag output258. The write enable handshake connection256outputs a signal that is coupled to receiver L port of each of the latch controllers232,234,236, and238in succession and thus enables the corresponding registers202,204,206, and208to receive data to be written from the data input bus210and be pipelined through the registers202,204,206, and208by each of the successive controllers232,234,236, and238outputting an enable signal over the E outputs to the enable inputs E1-E4. The signal from the receiver L port causes each successive controller to send the signal through the transmitter R port to the receiver L port of the next controller. The controllers232,234,236, and238also enable the corresponding one bit latches222,224,226, and228to write the zero to indicate the presence of a bubble. The bubble flag output258is coupled to the first one bit latch222. As explained below, the bubble flag output258stores a zero in the enabled one bit latch222to indicate the presence of a bubble stored in the respective register202. As the bubble is propagated through the pipeline of registers204,206and208, the zero is passed to each successive one bit latch224,226, and228, respectively, to indicate the presence of the bubble. Reading the last register208is accomplished from the output data bus212and is triggered by a read handshake connection260. A successful read causes data in each proceeding register to be written into the next register in the pipeline. In the case of a bubble, the zero in the last one bit latch228will indicate a bubble and therefore the read device does not read the bubble from the last register208.

The basic set of registers202,204,206, and208inFIG. 2has a very desirable property that if the entirety of registers are initialized to be half-full (e.g., every other register stage contains data), and its endpoint clocks have the same frequency, then it will never become empty or full and the reads and writes will never need to be synchronized since a read or write can always occur in the registers202,204,206, and208. This is true even if the endpoint clocks have an unknown (but still fixed) phase relationship.

In operation of the FIFO memory device200inFIG. 2, the clock of the write device is always at the same or lower rate than the clock of the read device. In this manner, there will never be a situation where data is overwritten in registers that have not been read. If a write request signal is received from the write handshake connection252, the bubble inserter250will send a write enable signal over the write handshake connection256. The latch controller232will enable the register202to accept data from the data input bus210by sending an enable high signal to the register202to enable input E1. In this case, since a real data word is written, the bubble flag output258sets the latch222high to indicate that real data is now stored in the register202.

In the case of a read request, a downstream consumer asserts the read signal on the read handshake connection260low to the transmitter R port of the rightmost latch controller238. The read signal is held low and sent to each of the successive latch controllers236,234, and232in succession from the receiver L port of the controller to the transmitter R port of the next controller. On receiving the read signal, the respective latch controllers,238,236,234, and232cause a low enable signal to be sent to the respective registers208,206,204and202. Since the enable signal is low for the register208from the latch controller238, the data in the register208may be read and output on the data output bus212. After the data is read from the register208, the read handshake connection260returns high and the enable signal is set high for the register208by the rightmost latch controller238, which allows data to be written from the register206to the register208. This process repeats for each preceding register thereby moving data or bubbles through the pipeline of registers202,204,206, and208. The first register202therefore will eventually be physically empty (having neither data nor a bubble) at the end of the process. If the latch228is set low for the last register208, a bubble is stored in the register208and the read device will receive no valid data. However, the process will continue to pipeline other data through the registers202,204,206, and208to result in an empty first register202.

The near empty detect circuit240detects whether there is a near empty condition, which is defined as having less than two of the registers202,204,206, and208full. This detection occurs to prevent a situation where all of the registers202,204,206, and208are empty. The near empty detect circuit240will detect such a near empty situation and send a jam output signal to the jam input254of the bubble inserter250. The bubble inserter250will “insert” a bubble into the first register202and set the bubble flag in the latch222low to indicate that a bubble is stored in the first register202. The bubble is simply a dummy data value in lieu of actual data that will be ignored by the read device and therefore simply uses whatever values are in the register202as the “insert” of the bubble. The bubble is thus added to the sequence of data moving through the registers and is written to the register204in sequence as data is moved through the pipeline of registers202,204,206, and208. The bubble functions to prevent an empty situation and therefore eliminates the need to synchronize the read operation with the write operation. As the bubble is passed through the pipeline of registers202,204,206, and208, the bubble flag is passed through to the respective latches222,224,226, and228.

FIG. 3Ais a circuit diagram of a transition-signaling-based version of a latch controller circuit300, which may be used for the latch controller circuit232inFIG. 2to control writing of data to the register204from the corresponding register202. The latch controller circuit300includes a D-latch302and an exclusive OR gate304. The latch controller circuit300includes a request input312and a request output314. The latch controller circuit300has an acknowledge input316and a corresponding acknowledge output318. An enable output320is coupled to the respective register to send an enable signal to allow the data in the register to be written to. This enable output is level-sensitive and active-high, but all other inputs and outputs use transition-signaling. With transition-signaling, an event is indicated by the signal changing value, but the value itself doesn't matter.

When a request transition is received for a write operation on the register on the request input312, the request is passed along via the D-latch302to the request output314, which passes the request along to the next controller. The request output314also alters one of the inputs of the XOR gate304. The output of the XOR gate304will thus fall from high to low and clear the enable signal of the corresponding register via the enable output320to direct the register to latch the waiting data. The output of the XOR gate304is also connected to the enable input of the D-latch302and the fall of the output of the XOR gate304will disconnect the output of the D-latch302from the D input, until the controlled register's contents are later read out.

The output of the D-latch302also is sent back over the acknowledge output318to indicate that the write request has been received. When the request transition is received by the last latch controller238, an acknowledge signal is sent to the acknowledge input316, which is connected to the other input of the XOR gate304and the enable output320is set high to enable a write to the register, since the next register has acknowledged absorbing its contents, and to allow the register to be newly written to. The D-latch302is made transparent by the high output of the XOR gate304. The latch controller circuit300inFIG. 3Asuffers from extra latency as it requires all signals to be passed through the XOR gate304and the latch subcircuits.

FIG. 3Bis a circuit diagram of another example of a latch controller circuit350such as the latch controller circuit232inFIG. 2. The controller inFIG. 3Auses transition-signaling, butFIG. 3Buses level-sensitive pulse-signaling, also called four-phase signaling, but it does so over a shared wire so the same number of transitions is needed. The controller inFIG. 3Balso has less latency since it uses simpler components, and is therefore implemented in the memory device200inFIG. 2. With reference toFIG. 2, the latch controller350includes a receiver pin352(L) and a transmitter pin354(R). The receiver pin352is coupled to the write enable output256from the bubble inserter circuit250inFIG. 2assuming the controller350is the first controller232for the leftmost register202inFIG. 2, while the transmitter pin354(R) is coupled to the receiver pin L of the next latch controller234in sequence. The latch controller circuit350includes an enable output356(E) that is coupled to both the enable input of corresponding register and one bit latch and an input of the near empty detect circuit240inFIG. 2.

The latch controller350is a single-wire level-sensitive design henceforth to be indicated by the circle symbol representing the latch controller232shown inFIG. 2. The latch controller350includes an input receiver/converter circuit362(on the left ofFIG. 3B) and an output converter/transmitter364(on the right ofFIG. 3B). The inputs to a NAND gate366are the signals from the receiver and transmitter inputs352and354. The NAND gate366has one output coupled to an inverter368. The NAND gate366and inverter368constitute a coordination/synchronization circuit between the receiver and transmitter circuits362and364.

The input receiver circuit362includes a PFET370that has a gate coupled to the input signal from the receiver input pin352through an inverter372. The PFET370and the inverter372form the cycle in a half-latch circuit that holds the left receiver input352high. The receiver/converter circuit362includes a PFET374that is in series with the PFET370and has a gate coupled to the inverted output of the NAND gate366. An NFET376is coupled in series with the PFET374and has a gate coupled to the output of the inverter368. Thus, the PFET374functions as a tri-state control that disconnects the half latch when the NFET376is conducting, which avoids contention. The left receiver pin352is held in the low state by the half-latch in the previous latch controller to the left of the latch controller350if the latch controller350is one of the intermediate latch controllers such as the latch controller234inFIG. 2.

The right output half364includes an NFET380having a gate coupled to the right transmitter pin354through an inverter382. The NFET380and inverter382form the cycle in the half latch holding the right transmitter pin354low. An NFET384is coupled in series with the NFET380and has a gate coupled to the output of the NAND gate366. The NFET384functions as a tri-state control, which disconnects the half latch circuit when the output driver through the transmitter pin354is conducting via the PFET386, thereby avoiding contention. The right transmitter pin354is held in the high state by the half-latch in the next latch controller to the right of the latch controller350. The PFET386is coupled in series with the NFET384and is controlled by the output of the NAND gate366, which is coupled to the gate of the PFET386. The enable output356is the inverted state of the right transmitter pin354as it is the output of the inverter382.

In this example, the latch controller350is used for the latch controllers inFIG. 2such as the latch controller232. Thus, each pair of right-going request signals and left-going acknowledge signals are replaced by a single bidirectional wire in the form of the receiver pin (L)352and the transmitter pin (R)354. The controller circuit350inFIG. 3Bincludes the receiver/converter362, the converter/transmitter364, and the coordination/synchronization circuitry (NAND gate366and inverter368) in between the converters362and364. The “converter” refers to the conversion between a single bidirectional wire and a pair of unidirectional wires.

When a write request is sent by the bubble inserter circuit250, the high signal is received in the receiver pin352. The high input signal is inverted by the inverter372and turns on the PFET370. This is the half-latch on the receiver side holding the input signal high as long as required and until disconnected. The high signal is also input to one of the inputs of the NAND gate366, which will produce a low signal when the other input coupled to the transmitter pin354through the inverter382is or later becomes low. The low signal from the NAND gate366is inverted by the inverter368and turns off the PFET374, disconnected the half-latch from the receiver pin352. When a read request is received from the transmitter pin354, the output of the NAND gate366turns low. The low output from the NAND gate366is inverted by the inverter368and turns on the NFET376. The NFET376thus pulls the receiver pin352low. This functions as a “self-reset” of the request on receiver pin352, as well as an acknowledgment to the upstream circuit doing the write.

The low output from the NAND gate366also turns off the NFET380, disconnecting the half latch formed by inverter382and NFET380, which (depending on its state) may be holding the transmitter pin354low, and turns on the PFET386. The now high signal at pin354is inverted by the inverter382and provides a low signal to NAND gate366. The inverted signal from the inverter382also is the output enable signal from the enable output356, which enables the corresponding register to accept a read.

A high state on the transmitter pin354indicates that there is data in the register to be read. The signal is inverted by the inverter382, which causes a low input to be sent to the NAND gate366. The inverted signal from the inverter382also sets the enable output356low and prevents any writing to the register. This low value causes the output of the NAND gate366to be high, which turns on the NFET384, reconnecting the half latch on the transmitter pin354to maintain its current high level, and turns off the PFET386, which previously pulled the transmitter pin354high to indicate new data in this state. This prepares the circuit for a subsequent read request to read the data now in the stage.

FIG. 4Ais a circuit diagram of an example bubble inserter circuit250inFIG. 2. The bubble inserter circuit250, shown inFIG. 4A, includes a single-wire receiver/converter410, a single-wire converter/transmitter412, and an arbiter414between the receiver410and transmitter412. A latch420is coupled to the arbiter414to hold the results of the arbitration. An input latch422holds the value of the jam input signal from the jam input254.

Similar to the latch controller350inFIG. 3B, the receiver/converter410reads the signal from the write handshake connection252. The signal is fed into an inverter440, which is coupled to a PFET442. The PFET442is wired in series with a PFET444and an NFET446. The PFET442and PFET444form a half latch to hold the write handshake connection252high. The NFET446allows the reset of the write handshake connection252when the write has occurred.

The converter/transmitter412includes an inverter450having an input coupled to the write handshake connection256. A PFET452is wired in series with an NFET454and another NFET456. The PFET452and the NFET454are controlled by a NOR gate464. The NFET456is part of the half latch also built from the inverter450. The gate of the NFET456is coupled to the output of the inverter450. The half latch holds the write handshake connection256low after the downstream stage pulls it low to acknowledge receipt of the data read.

The arbiter414includes a first input430that reflects a write request and a second input432that reflects a jam request. The arbiter414includes a first output434that grants a write request from the write handshake connection252inFIG. 2and a second output436that grants the jam request from the jam input254. The arbiter414decides which request wins, assuming a jam request and a write request are received simultaneously. In this example, the arbiter414has unbounded computation time to determine whether to write new data or insert a bubble. The outputs434and436are each coupled to one input of a pair of AND gates460and462. The outputs of the AND gates460and462are coupled to the NOR gate464, which has an output coupled to the gates of the PFET452and the NFET454.

As explained above, when new conventional data is received to be written into the FIFO200, the write handshake connection252is set high, while when a bubble is required the jam input254is set high by the near empty detect circuit240inFIG. 2. When a write request is received, the signal is sent to the input430of the arbiter414and a high signal is output from the output434. When the write request is received first, a subsequent jam request on the jam input254is initially ignored and held in the latch422connected to the second input432until the first input430receives a low signal. The high signal from the output434is input to the AND gate462. The second input of the AND gate462is the inverted signal of the write handshake connection256. The write handshake connection is low and thus a high signal is output from the AND gate462, which causes a low output from the NOR gate464. The low output from the NOR gate464turns off the NFET454and turns on the PFET452thus pulling the write handshake connection256high, which is passed to the latch controller232. The output of the AND gate462is also coupled to the S input of the latch420, which outputs a high signal on the bubble flag output258and causes the bubble bit flag output to be high, which is stored in the latch222and therefore indicates that the register202has real data. The output of the AND gate462is also coupled to the gates of the NFET446and the PFET444, which pull the write handshake connection252low to acknowledge the write.

After the write handshake connection256goes high, the output is inverted by the inverter450, which turns the input to the AND gate462low thereby causing the output of the NOR gate to go high, turning on the NFET454, turning off the PFET452and turning on the NFET456via the inverter450, thus allowing the write handshake connection256to be pulled low when the downstream logic acknowledges reading the data just written.

If a near empty condition of the pipeline of registers202,204,206, and208is detected by the near empty detection circuit240, the jam input254is set high, which is input to the S input of the latch422and output as a high signal to the input432of the arbiter414. The arbiter414causes the second output436to be high. When the jam request is received, any subsequent write signal is ignored and the arbiter414holds the first output434low until the second input432returns to low. The second output436is coupled to one input of the AND gate460. The other input of the AND gate460is coupled to the write handshake connection256, which is low and is inverted by the inverter450to cause a high signal to be input to the AND gate460. The output of the AND gate460is therefore high and is coupled to the NOR gate464, which outputs a low signal. The low output from the NOR gate464turns off the NFET454and turns on the PFET452thus pulling the write handshake connection256high, which is passed to the latch controller232. The output of the AND gate460is also coupled to the R input of the latch420and causes the bubble bit flag output to be low reflecting the low output of the AND gate462, which is output over the bubble flag output258and stored in the latch222inFIG. 2indicating that the register202has stored a bubble. Similar to the write operation, the write handshake connection256will be pulled low again by the downstream circuit acknowledging reading the bubble just written and the bubble inserter250is ready for the next action.

Since new data may arrive for writing from the sending devices on the left of the FIFO200inFIG. 2at any time, the arbiter414is required to decide if the pipeline will insert a new data word or a bubble into the register202, since these two events are asynchronous with respect to each other. If both a write request and a jam request occur simultaneously, the arbiter414decides which request should be performed first and suspends the other request until the first request is completed.

As explained above, since the inputs of the AND gates460and462are coupled to the inverter450, which inverts the signal from the write handshake connection256, the AND gates460and462prevent the arbitration decision from propagating right until the transmitter412is ready to send an event through the write handshake connection256. The outputs of the AND gates460and462and the NOR gate464produce a request to the pipeline of registers and controllers in the FIFO200to accept a new entry through the signal output over the write enable output256. The RS latch420remembers the result of the arbitration, and its output is sent to the bubble flag output258to set the extra bit stored in the latch222representing whether real data or a bubble is written into the first register202. As explained above, if new data is written to the first register202, the output of the RS latch420is set to a one and sent through the bubble flag output258to set the latch222as a one. If a bubble is inserted, the output of the RS latch420is set to low and sent through the V output258to set the bubble flag as a low.

FIG. 4Bshows an alternate hold circuit for the RS type latch422of the bubble inserter circuit250inFIG. 4A. The latch422inFIG. 4Ais replaced by a D flip flop470shown inFIG. 4B. As shown inFIG. 4B, the jam input254is connected to the clock input474. The reset input472of the D latch470is coupled to the output of the AND gate460inFIG. 4A. The D input is tied high, while the Q pin476is coupled to the second input432of the arbitration circuit414.

The circuit that includes the RS latch422inFIG. 4Abehaves properly only if the “jam” signal is removed quickly. The circuit using the D latch470shown inFIG. 4Bresponds only to the rising edge of the signal on the jam signal input254and doesn't care when it is removed. The circuit with the D latch470thus can tolerate a wider range of circuit possibilities for the near empty detect circuit240, which generates the “jam” signal.

FIG. 5shows an example of the near empty detect circuit500such as the near empty detect circuit240inFIG. 2. The near-empty-detect circuit240may be implemented in a number of ways. It could directly monitor the state of the latch enables generated by the latch controllers such as the latch controller232inFIG. 2. In order to tolerate wide variations in pulse timing, it should check for the near-empty condition by checking that at least two latch enables of the registers are asserted, as shown in the example near empty detect circuit500inFIG. 5. The near empty detect circuit500includes an OR gate502that has an output504that is coupled to the jam input254inFIG. 2. The inputs of the OR gate502are coupled to the outputs of respective AND gates510,512,514,516,518, and520. The AND gates all have inputs that are coupled to the enable outputs from the controllers232,234,236, and238to the enable inputs E1-E4of the respective registers202,204,206, and208inFIG. 2. For example, the AND gate510has a first input coupled to the enable input E1of the register202and a second input coupled to the enable input E2of the register204. Thus, each of the AND gates510,512,514,516,518, and520have a unique set of two of the enable inputs E1-E4from the registers202,204,206, and208. If no two latch enables are asserted, indicating that at least two of the registers are empty, the output of the OR gate502sends a high signal to the jam input254to trigger the insertion of a bubble as explained above.

Another more general and robust technique would be to count the transitions on the latch controller handshaking pulses just before and after data is written to the pipeline of registers and if the difference between these two counts is in a certain range the pipeline registers are near-empty. Thus, the near empty detect circuit240inFIG. 2includes inputs from the lines between the latch controllers232,234,236, and238. Another variation of the near empty detect circuit240is programmable in order to select between different latencies and arbiter reliabilities.

The latency and reliability of the entire FIFO200can be altered by changing the near-empty-detect circuit240. If near empty detect circuit240requests a new bubble whenever the pipeline occupancy falls below two, for example, then that means any new arriving data will have at least two items in the pipeline before it, possibly all bubbles, and thus the latency of this data through the pipeline cannot be less than two. This also means that the arbiter414in the bubble inserter circuit250always has two clock cycles to make its decision (since it takes that many clock cycles to empty the pipeline), which is important since the decision could be delayed if the arbiter414internally enters metastability and this requires a certain amount of time to resolve.

FIG. 6is an example of a FIFO memory device600that uses protocol converters and gating circuitry to ensure that reads are not enabled unless the register pipeline is not completely empty. In the FIFO600, the clock rate of the write devices is slower than the clock rate of the read devices, and thus there may be an empty condition in the pipeline of registers without the bubble inserter circuitry. Similar to the FIFO200inFIG. 2, the FIFO600includes a series of registers602in a pipeline, bubble bit latches604, and latch controllers606. The FIFO600includes a bubble insert circuit608and a near empty detect circuit610. Data is written into the registers602from an input databus612and read from the registers from an output databus614. A write is initiated from a write request input616and reads are initiated from a read request input618. A not empty condition for the registers602is indicated by a read valid output620. A not full condition is indicated by a write valid output622that is permanently tied high.

A first protocol converter630is connected to the bubble insert circuit608. Another protocol converter632is connected to the read enable input618. When a write request is received on the write enable input616, the signal is sent to the input of an AND gate634. The other input of the AND gate634is coupled to the write ready output622that is tied high at all times. The write signal is sent to the protocol converter630, which is clocked the same as the devices writing to the FIFO600. The protocol converter630sends the high signal to the bubble insert circuit608to initiate the write to the first register602when the register is enabled. The near empty detect circuit610may send a jam signal to the bubble insert circuit608indicating the registers602are almost empty resulting in the insertion of a bubble in order to keep the registers602from being empty.

Similarly, when a read is requested, a signal is sent to the read enable input618. The signal is input to one input of an AND gate636. The other input of the AND gate636is coupled to the read valid output620, which will be high when the registers602are not entirely empty thereby allowing a read to occur. The output of the AND gate636is coupled to one input of an OR gate638. The other input of the OR gate638is inverted from the read valid output620. The output of the OR gate638sends a high signal to the enable input of the protocol converter632exactly when a read is requested and valid, or there is a bubble in the register pipeline. The protocol converter632is clocked by the same clock for devices reading from the FIFO600. The protocol converter632will output a signal to the last latch controller606to request a read of the last register602in the pipeline.

FIG. 7Ashows an example clocked protocol to handshake protocol converter700that converts clocked signals to the handshaking protocol such as the protocol converter630inFIG. 6. The protocol converter700includes a D-flip-flop702having an input coupled to an inverter704. The output of the flip-flop is coupled to a half latch converter transmitter circuit exactly the same as that shown in the right ofFIG. 3B. The output of the flip-flop702is coupled to the gates of a PFET706and an NFET708. The PFET706and the NFET708are wired in series with an NFET710. The gate of the NFET710is coupled to an inverter712. An enable input720takes a high signal clocked by the writing device. The high signal is inverted by the inverter704and output as a low signal from the D flip-flop702. The low is sent to the gates of the PFET706and NFET708to pull write handshake connection722high. The write handshake connection722provides a connection point using the handshaking protocol of the written to devices to the right ofFIG. 7A. The write handshake connection722is inverted by the inverter712producing a low signal to the set input to remove the low signal in the D flip-flop702.

FIG. 7Bshows an example handshake protocol to clocked protocol converter750that converts handshaking signals to clocked signals such as the protocol converter632inFIG. 6. The converter750includes a D flip-flop752, which feeds the Q output to one input of a NAND gate754. The handshake signal is coupled to an inverter756, which is coupled to the gate of the PFET760. The output of the NAND gate754is inverted by an inverter758, which has an output coupled to the gates of a PFET762and an NFET764. The PFET762is wired in series to a PFET760. As shown inFIGS. 7A and 7B, the protocol converters700and750contain the converter/transmitter and receiver/converter sub-blocks exactly the same as the blocks364and362, respectively, in the controller350inFIG. 3B.

When a signal is received by an input770such as to enable a read such as that for the protocol converter632inFIG. 6, the high signal is input to the flip-flop752. The resulting high output of the flip-flop752is coupled to the NAND gate754, which results in a low output, which is inverted by the inverter758and turns the PFET762off and the NFET764on. This pulls the handshake connection772low to indicate to the upstream circuit that the read request has absorbed the read data.

When the handshake connection772goes high, the other input of the NAND gate754goes high and thereby pulls the handshake connection772low again. The output of the handshake connection772is also coupled to the inverter756, which inverts the high signal and turns on the PFET760, in order to retain the high signal in this half latch configuration. This pulls the handshake connection772low to indicate to the upstream circuit that the read request has absorbed the read data.

FIG. 8shows an example of a self-stuffing pipeline-based FIFO memory device800with empty and full arbitration. The memory device800operates similarly to the memory device600shown inFIG. 6except a backwards-flowing credit path has been added. In the FIFO800, the clock rates for the devices requesting reads and writes of data may be at different rates. Thus, if the rate of the clock for the writing devices is faster, there may be a full state of the register pipeline but if the clock rate of the reading devices is faster as above there may be an empty state. The need to synchronize the FIFO800regardless of the different read and write clock speeds is eliminated by adding a reverse path using the same technique of bubble insertion and arbitration described above. Similar to the FIFO memory device200inFIG. 2, the FIFO memory device800includes a series of registers802, bubble bit latches804, and latch controllers806. The FIFO800includes a bubble inserter circuit808and a near empty detect circuit810. Data is written into the registers802from an input data bus812and read from the registers from an output data bus814. Data writes to the first register802is initiated from a request signal on a write enable input816and data reads from the last register802are initiated from a request signal to a read enable input818. A write ready output820indicates that the pipeline is not full and thus a write may be initiated. A read ready output822indicates that the pipeline is not completely empty and a read may be initiated.

In the FIFO800, a secondary, reversed sequence of latch controllers824,826,828, and830has been added, which indicate the granting of a “credit to transmit” to the write devices by the data receiver. The latch controllers824,826,828, and830are connected to and enable a pipeline of one bit credit latches832,834,836, and838. A bubble inserter840is coupled to a near full detect circuit842. The bubble inserter840inserts a credit in the first latch832when the registers802are nearly full. The credit is inserted whenever one of registers802becomes newly empty in order to prevent the registers802from being completely full. The credit is thus pipelined down the latches832,834,836, and838to the last one bit latch838. The one bit credit latches each convey credit data in the opposite direction of the registers802, and with surrounding circuitry interpreting a second FIFO of the one bit credit latches832,834,836, and838as containing credits, and uses them to prevent over-run in the registers802. Similar to the bubble inserter explained above, the bubble inserter840includes an arbiter to arbitrate between when the near full detect circuit842indicates a bubble needs to be inserted occurs simultaneously with a read request from the read enable input818.

The controllers824,826,828, and830do not need to control latches, since the presence of a credit or bubble is all that is required. After the arbitration in the bubble inserter840, however, it is necessary to know if the pipeline contains real credits or bubble credits, so the single bit latches832,834,836, and838along the bottom, which store that indicator, need to be controlled. Just as the forward data-path is widened to include a bit for the bubble flag, the reverse credit-path is widened from zero width to a one-bit pipeline of one bit latches832,834,836, and838. The bits in the reverse credit-path allow the avoidance of a completely full condition of the registers802in the pipeline and thereby obviate the need for a synchronizer.

The FIFO800also includes two protocol converters850and852that convert signals from a device clock to handshaking signals for the controller and bubble inserter circuitry. The first protocol converter850is coupled to the bubble inserter circuit808and includes an input that is coupled to an output of an AND gate854. The inputs of the AND gate854are coupled to the write enable input816and the write ready output820, which will be explained below.

The second protocol converter852is coupled from the output of the bubble insert circuit840. The input of the protocol converter852is coupled to the output of an AND gate856. The first input of the AND gate856is coupled to the read enable line818and the other input is coupled to the read ready output822.

The FIFO800also includes two protocol converters860and862that convert read and write requests, respectively, to handshaking signals for the controllers and the bubble inserter circuitry. The first protocol converter860is coupled to the R pin of the last controller806. The input of the protocol converter860is coupled to the output of an OR gate864. The inputs of the OR gate864are coupled to the transmission/read valid (not empty) input822and the output of the AND gate856. Thus, a read request through the read enable input818will not be initiated until the pipeline is not empty as indicated by the read valid input822from the last bubble flag latch804.

The other protocol converter862has an output coupled to the latch controller830. The input of the protocol converter862is coupled to the output of an OR gate866. The inputs of the OR gate866are the transmit ready input820and the output of the AND gate854. Thus, a write request through the write enable input816will not be initiated until the pipeline is not full as indicated by the write valid input820from the last credit flag latch838.

The FIFO800allows arbitration of full pipeline situations that prevent a write to the registers802. If a read enable is received on the read enable input818, it is coupled to the input of the AND gate856. The other input of the AND gate856is coupled to the output of the last latch804, which will only allow the output signal of the AND gate856to go high when the last register has real data to be read and thus the bubble flag stored in the last latch804is a one. The read enable signal thus is fed into the protocol converter852, which conveys the enable signal to the bubble inserter circuit840, which indicates that a credit has occurred. As shown inFIG. 8, the protocol converter852is clocked at the same rate as the devices making the read request. The bubble inserter circuit840converts the enable request into a credit signal for the latch832. The output of the AND gate856also is coupled to one input of the OR gate864. The other input of the OR gate864is coupled to the bubble flag value of the last latch804. The output of the OR gate864is coupled to the enable input of the protocol converter860. The protocol converter860is clocked at the same rate as the devices that make the read request. The protocol converter860sends an acknowledge signal to the chain of latch controllers806and eventually to the bubble inserter circuit808. In this manner, the read enable signal is converted to the timing of the registers and only sent when there is not an empty condition in the registers802.

Similarly, when a write request is received on the write request input816, the signal is connected to one of the inputs of the AND gate854. The other input of the AND gate854is coupled to the write ready output820, which is the value of the last one bit latch838. If the value of the latch832is high, it indicates that the corresponding register is empty and ready to be written to. The output of the AND gate854is coupled to the enable input of the protocol converter850, which is clocked at the rate of the devices requesting writes. The output of the protocol converter850is coupled to the write handshaking connection of the bubble inserter circuit808, which initiates the writing of data from the data input bus812.

The handshaking-based FIFO800inFIG. 8includes core conversion circuitry to convert between the handshaking-based signaling in the core and conventional synchronous clocking in the write and read interfaces. This conversion circuitry includes four protocol converters850,852,860, and862and four qualifying gates854,856,864, and866. As explained above, the pipeline of latches832,834,836, and838in combination with the near full detector842will insert the appropriate numbers of real credits and bubble credits, which will prevent the additional writes that would make the registers802entirely full.

While the present principles have been described with reference to one or more particular examples, those skilled in the art will recognize that many changes can be made thereto without departing from the spirit and scope of the disclosure. Each of these examples and obvious variations thereof is contemplated as falling within the spirit and scope of the disclosure, which is set forth in the following claims.