Self-stuffing multi-clock FIFO requiring no synchronizers

1. An asynchronous first in first out memory device comprising:

a plurality of data registers arranged in a pipeline, the plurality of data registers including a first register to accept writing of data from a write device and a last register to allow reading of data by a read device, each register having an enable input to indicate a full condition allowing a read of the register and an empty condition allowing a write to the register, the plurality of data registers allowing data to be passed in sequence from the first register to the last register;

a bubble inserter circuit to cause a bubble that is a dummy data value instead of actual data to be stored in the first register to prevent a completely empty condition for all of the data registers;

a latch to store a bit received from the bubble inserter circuit that indicates whether the first register is storing the bubble or the actual data;

a near empty detect circuit coupled to the plurality of data registers to determine a nearly empty condition of the plurality of data registers; and

wherein the bubble inserter circuit includes an arbiter, the arbiter determining whether a data write proceeds or a bubble insertion proceeds for the first register when the plurality of data registers is near empty as determined by the near empty detect circuit.

2. The memory device of claim 1 , further comprising a plurality of controllers, each associated to a respective register of the plurality of registers via the enable input, the plurality of controllers allowing the bubble or written data to be passed from the first register to the last register.

3. The memory device of claim 2 , wherein the controllers each include half latch circuitry to hold a request signal and an acknowledgement circuit to send an acknowledge output signal in one clock cycle.

4. The memory device of claim 1 , wherein the clock rate of the write device is the same or lower than the clock rate of the read device.

5. The memory device of claim 1 , wherein the bubble inserter circuit sets an indication that the first register is storing a bubble by changing the bit stored in the latch, and wherein the bit is passed in sequence with the bubble from the latch to additional latches, and wherein the read device ignores the contents of the last register in response to a read request, if the last register contains a bubble.

6. The memory device of claim 1 , wherein the near-empty-detect circuit is programmable in order to select between different latencies and arbiter reliabilities.

7. The memory device of claim 1 , further comprising:

a credit pipeline including a plurality of credit latches, the credit pipeline including a first latch corresponding to the last register and a last latch corresponding to the first register, wherein a credit is written to the first latch when a read is made from the last register;

a second bubble inserter coupled to the first credit latch;

a nearly full detect circuit coupled to the plurality of credit latches, the nearly full detect circuit inserting a bubble credit into the first credit latch when the credit latches are nearly empty; and

wherein the clock rate of the read device is at a slower clock rate than the write device.

8. A method of using a first in first out memory device having a plurality of registers arranged in a pipeline including a first register to accept a data write from a write device and a last register to allow a data read by a read device, each register having an empty condition and a full condition, the method comprising:

determining whether the plurality of registers are in a near empty state;

causing a bubble of replacement dummy values instead of actual data to be stored in the first register to avoid an empty state in the plurality of registers;

setting a bubble bit associated with the first register to indicate that a bubble is stored in the first register;

pipelining the bubble and bubble bit to the next register of the plurality of registers in response to a read request until the bubble reaches the last register;

receiving a read request to read data in the last register;

reading the bubble bit associated with the last register; and

ignoring the contents of the last register in response to the read request if the last register contains a bubble.

9. The method of claim 8 , further comprising:

receiving a write request;

determining whether the write request and determination of a near empty state occurs simultaneously;

arbitrating between the write request and the insertion of a bubble;

writing data to the first register if the arbitration proceeds with the write request; and

delaying the writing of the data to the first register until the bubble is inserted if the arbitration proceeds with the bubble insertion.

10. The method of claim 8 , wherein the clock rate of the write device is the same or lower than the clock rate of the read device.

11. The method of claim 9 , wherein the arbitration has unbounded computation time to determine whether to write the data or insert a bubble.

12. The method of claim 8 , wherein a plurality of bubble bits each corresponding to one of the plurality of registers is provided, and wherein an indication is made that the first register is storing a bubble by changing the bubble bit.

13. The method of claim 8 , wherein the near empty condition is programmable in order to select between different latencies.

14. The method of claim 9 , wherein the near empty condition is programmable in order to select between different reliabilities of the arbitrating.

15. The method of claim 8 , further comprising:

writing a credit in to the first register of a plurality of credit latches when a read is made from the last register, wherein the plurality of credit latches are in a pipeline including a first credit latch corresponding to the last register and a last latch corresponding to the first register;

inserting a bubble credit into the first credit latch when the credit latches are nearly empty; and

wherein the clock rate of the read device is at a slower clock rate than the write device.

16. A computational system comprising:

a write device being clocked at a first clock rate;

a read device being clocked at a second clock rate; and

an asynchronous first in first out memory device coupled to the write device and the read device, the memory device including:

a plurality of data registers arranged in a pipeline, the plurality of data registers including a first register to accept writing of data from the write device and a last register to allow reading of data by the read device, each register having an enable input to indicate a full condition allowing a read of the register and an empty condition allowing a write to the register, the plurality of data registers allowing data to be passed in sequence from the first register to the last register;

a bubble inserter circuit to cause a bubble that is a dummy data value instead of actual data to be stored in the first register to prevent a completely empty condition for all of the data registers;

a near empty detect circuit coupled to the plurality of data registers to determine a nearly empty condition of the plurality of data registers; and

a latch to store a bit received from the bubble inserter circuit that indicates whether the first register is storing the bubble or the actual data,

wherein the bubble inserter circuit includes an arbiter, the arbiter determining whether a data write proceeds or a bubble insertion proceeds for the first register when the plurality of data registers is near empty as determined by the near empty detect circuit.

17. The computational system of claim 16 , wherein the asynchronous first in first out memory device further comprises:

a plurality of controllers, each associated to a respective data register of the plurality of data registers via the enable input, the plurality of controllers allowing the bubble or written data to be passed from the first register to the last register,

wherein the controllers each include half latch circuitry to hold a request signal and an acknowledgement circuit to send an acknowledge output signal in one clock cycle.

18. The computational system of claim 16 , wherein the arbiter has unbounded computation time to determine whether to write new data or insert the bubble.

19. The computational system of claim 16 , wherein

the bubble inserter circuit sets an indication that the first register is storing a bubble by changing the bit stored in the latch, and wherein the bit is passed in sequence with the bubble from the latch to additional latches, and wherein the read device ignores the contents of the last register in response to a read request, if the last register contains a bubble.

20. An asynchronous first in first out memory device comprising:

a plurality of data registers arranged in a pipeline, the plurality of data registers including a first register to accept writing of data from a write device and a last register to allow reading of data by a read device, each register having an enable input to indicate a full condition allowing a read of the register and an empty condition allowing a write to the register, the plurality of data registers allowing data to be passed in sequence from the first register to the last register;

a bubble inserter circuit to cause a bubble that is a dummy data value instead of actual data to be stored in the first register to prevent a completely empty condition for all of the data registers;

a near empty detect circuit coupled to the plurality of data registers to determine a nearly empty condition of the plurality of data registers; and

wherein the bubble inserter circuit includes an arbiter, the arbiter determining whether a data write proceeds or a bubble insertion proceeds for the first register when the plurality of data registers is near empty as determined by the near empty detect circuit, and

wherein the arbiter has unbounded computation time to determine whether to write new data or insert the bubble.