US 5,384,744 AGrant
Look Ahead Flag for FIFO
Issue Date:1995-01-24
•8 Claims
•5 Drawing Sheets
Abstract
The invention provides fast generation of flag signals for devices such as a first-in first-out buffers by looking ahead and predetermining flag signals for future possible states of the device. Predetermining flag signals does not delay flag output because the required calculations are completed before the flag signal is needed. The flag signal can be changed when needed as quickly as a multiplexer can switch from an old flag signal to a predetermined flag signal. The switching time of a multiplexer is shorter than the comparator delays in prior art flag generators.
Metadata
Assignee
- Paradigm Technology, Inc.
Inventor
- Tsu-Wei F. Lee
Application Information
Application Number:US 9811583
Filing Date:1992-11-23
Priority Date:1992-11-23
Art Unit:251
Classifications
IPC:
G11C 700
Field of Search:
365340307377221;236;239;189.02;189.07146.223439
Patent Drawings (5 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to the setting of flag signals which indicate the status of a device such as an first-in first-out buffer.
2. Description of Related Art
A first-in first-out (FIFO) buffer often is useful between devices with different clock frequencies. In typical operation of a FIFO, a first device, such as micro-processor writes to the FIFO buffer and a second device, such as a peripheral or a second microprocessor, reads from the FIFO buffer. Each device reads or writes according to its own clock. Because two different clocks control the timing of read and write operations, the buffer handles the operations asynchronously, and the devices may write then read with a very short time separation.
To maximize data flow the FIFO buffer must be ready to respond to the next operation quickly. Any processing time required between one operation and a subsequent operation can delay the subsequent operation and slow the rate of data flow through the buffer. In particular, the time that the buffer takes to recalculate status flags after an action by one processor tends to slows down the buffer.
FIG. 1 show a typical application of a FIFO buffer 103. The FIFO buffer 103 holds data that is written to the buffer 103 by a first device 101 and read from the buffer 103 by a second device 102. Besides holding the data, the buffer 103 sends flag signals to the attached devices 101 and 102. For example the buffer 103 could send a full signal to the first device on a flag line 106 when the buffer is full, or could send an empty signal to the second device 102 on line 107 when the buffer is empty.
When the first device 101 has data to write to the buffer 103, the first device 101 checks for the full flag signal on line 106. If the flag signal indicates the buffer 103 is full the first device 101 must wait before sending data to buffer 103. If the buffer 103 is not full the first device 101 asserts data signals to the data lines 104 and sends a write clock or control signal to the buffer 103 on a line 108. The buffer 103 stores the data in a memory location pointed to by a write pointer and then increments the write pointer.
When data is in the buffer 103 the buffer 103 clears the empty signal on line 107, which indicates to the second device 102 that data is available to be read from the buffer 103. The second device 102 sends a clock or control signal to the buffer 103 on line 109, and the buffer 103 asserts to data lines 105 the data pointed to by a read pointer. After the second device 102 reads the data, the buffer 103 increments the read pointer.
With this architecture if the read pointer and the write pointer point to the same location then the FIFO buffer is either empty or full. It is full if enough data has been written so that the write pointer has just incremented to equal the read pointer. It is empty if the read pointer has just incremented to equal the write pointer. The FIFO buffer needs to signal these two conditions to the devices connected to the buffer.
When the two devices connected to a FIFO buffer do not have synchronized clocks, reads and writes to the buffer occur asynchronously, so the read pointer and write pointer change asynchronously. Still, when one of the devices connected to the buffer takes an action, the various status flags need to be changed to reflect the new values of the pointers. The devices connected to the buffer either wait while the new flags are calculated or take actions based on incorrect flags. The speed of the FIFO buffer, therefore, may be limited by the speed of flag output. If the speed of the flag output is improved then the speed of the FIFO can be improved.
In a FIFO buffer, flag output is normally generated from the values of the two pointers. For example, immediately after a device writes data to the buffer the read pointer may point to location i and the write pointer may point to location j. The full flag needs to be activated if the two pointers point to the same location, i.e. i=j. In typical prior art architecture, the FIFO buffer would compare the two pointer values and generate the flag signal for the connected device to act on. The connected devices normally have to wait the time it takes a comparator to generate the flag signal. Accordingly, a need exists to reduce or eliminate this wait and thereby speed up the operation of the system including the FIFO buffer.
Summary of the Invention
Embodiments of the present invention speed up a flag output from a FIFO buffer by looking ahead and predetermining possible new flag signals. When the state of the FIFO buffer changes, the buffer switches the flag output from the old signal to one of the predetermined flag signals. The FIFO buffer is ready to handle data as soon as the flag output is switched. Generally, switching time is considerably shorter than the time for a comparator to calculate a new flag value. The faster response decreases the time that flag signals incorrectly indicate the state of the FIFO buffer. Calculating all possible next flag signals does not delay device actions because the possible flag signals are calculated ahead of time.
Embodiments of the invention described in detail below include a look ahead signal generator which generates four flags signals. One of the flag signals is the current flag signal corresponding to the current state of the FIFO buffer. The other three signals correspond to possible states that the buffer would have after one read, or one write, or one read and one write. These three states are the only states that can be reached by read and/or write operations within a time interval less than the shortest clock period of devices attached to the buffer. Any other state of the buffer takes more than a clock period to reach.
For example to reach the state that occurs after two writes takes at least one clock period of the device writing to the buffer. The buffer cannot predict when a write will occur. However, because write operations are controlled by the clock of the writing device, after a first write operation occurs, a second write operation comes at the soonest in the next clock cycle of the writing device. The flag generator uses the time between the first write and the second write to predetermine the flag corresponding to the state the buffer would have after the second write.
The four flag signals are connected to the inputs of a signal selector. In some embodiments, the signal selector is just a multiplexer. The signal selector chooses the flag signal corresponding to the current state of the FIFO buffer as an output signal. When a device reads or writes to the buffer the multiplexer passes the predetermined flag signal corresponding to the new current state of the FIFO buffer. The flag generator then calculates possible new flag signals based on the new current state. Since the previously generated possible states includes all of the states that could be reached within the shortest clock period of a device attached to the FIFO buffer, the flag generator has at least a clock cycle to calculate new possible flag signals. The flag signals change as quickly as the signal selector can select an output signal.
The look ahead signal generator in some embodiments of the invention employs a method which quickly determines half full, almost full, or almost empty flags. Half full flags and almost full flags indicate whether the buffer is more than half full or is almost full. Almost empty flags indicate whether the buffer is almost empty. The method does a single subtraction of the current value of the read pointer from the current value of the write pointer. The values of the status flags for the current state of the buffer and the three possible new states are generated relying on the arithmatic relationships between the possible pointer values.
This invention will be more fully understood in light of the following detailed description taken together with the drawings.
Brief Description of the Drawings
FIG. 1 shows a diagram of a typical FIFO buffer attached to two devices.
FIG. 2 shows a block diagram of an embodiment of a look ahead signal generator.
FIG. 3 is a timing diagram showing signals that control the operation of the look ahead signal generator of FIG. 2 and the signal selector of FIG. 5.
FIG. 4 shows a circuit diagram which may be used to generate signals REVEN and RODD from a read clock signal or WEVEN and WODD from a write clock signal.
FIG. 5 shows a circuit diagram of a signal selector which takes the form of a multiplexer that may be use in conjunction with the circuit of FIG. 2.
FIG. 6 shows a circuit diagram of a portion of a look ahead signal generator used to generate flags indicating that the difference between the read and the write pointer values is greater than a constant C.
Detailed Description of the Preferred Embodiments
Embodiments of the invention described here provide fast generation of flag signals by predetermining a set of possible flag signals for possible future states and switching to the appropriate predetermined signal when the state changes. An embodiment of the invention can be used with the FIFO buffer described above to generate the flag signals for a current state and for future possible states.
One way to name the states of a FIFO buffer is by the values of the read and the write pointers. If the current value of the read pointer is i and the current value of the write pointer is j, the current state of the buffer can be referred to as (i,j).
The look ahead signal generator generates a flag signal for the current state (i,j) and for three possible new states (i,j+1), (i+1,j), and (i+1,j+1). These are the four states that can be reached in less than a clock cycle as described above and therefore need to be generated ahead of time to prevent delays.
Another way to name the four states is according to whether the read pointer and write pointer values are even or odd. Flag signals can be generated for the four states (even read, even write), (odd read, odd write), (even read, odd write), and (odd read, odd write). Any of these four state could be the current state depending on the values of i and j. If i and j are both even then the current state (i,j) is (even read, even write), (i,j+1) is (even read, odd write), (i+1, j) is (odd read, even write), and (i+1,j+1) is (odd read, odd write). If i and j are both odd the current state (i,j) is (odd read, odd write), etc.
FIG. 2 shows a circuit diagram of part of a look ahead signal generator used to generate either a full flag signal or an empty flag signal. The circuit shown generates flag signals EQE and EQO for the states (even read, even write) and (odd read, odd write). The flag signals for (even read, odd write) and (odd read, even write) are always low in the full flag or empty flag case because an even number can never equal an odd number.
An even read counter 204 holds an even value corresponding to either i or i+1. If i is even, read counter 204 holds the value i. If i is odd, read counter 204 holds the value i+1. An odd read counter 203 holds an odd value corresponding to i+1 or i (if i is odd, counter 203 holds i; if i is even, counter 203 holds i+1). In the same way, an even write counter 202 holds an even value corresponding to j or j+1 and an odd write counter 201 holds an odd value corresponding to j+1 or j.
Comparator 205 compares the value in the even read counter 204 to the value in the even write counter 202 and generates the flag signal EQE for the state (even read, even write). Comparator 206 similarly compares the values in the odd read counter 203 to the value in the odd write counter 201 and generates the flag signal EQO for the state (odd read, odd write). Again, no calculation is necessary for the state (even read, odd write) or (odd read, even write) because an even value can never equal an odd value, and the flags for (even read, odd write) or (odd read, even write) should never indicate a full or empty buffer.
Each of the counters 201-204 increments by 2 every time the counter is clocked. This keeps even counts even and odd counts odd. FIG. 3 shows a voltage verses time plot for a number of clock signals. A write clock signal is generated by the device that writes to the buffer. The buffer latches data from the data lines and increments the write pointer on the rising edge of the write clock signal. A read clock signal controls the reading of data by the second device. On a rising edge of the read clock signal the buffer increments the read pointer. REVEN (RODD) is a signal that is high when the value held in the read pointer is even (odd). WEVEN (WODD) is a signal that is high when the value held in the write pointer is even (odd) .
The signals REVEN and RODD may be easily generated from the read clock signal using a D flip-flop 401 as shown in FIG. 4. The read clock signal is asserted to lead 402 and produces signals REVEN and RODD on leads 404 and 403. WEVEN and WODD are generated from the write clock signal in the same fashion using a structure the same as that shown in FIG. 4.
Again considering FIG. 3, on every rising edge of the read clock the read pointer increments and the signal REVEN changes voltage level. Initially REVEN is high, and the read pointer value is zero. Every time a read is done REVEN alternates between high and low, and the value of the read pointer alternates between even and odd. Thus, as stated above, signal REVEN indicates if the read counter is even. Similarly, RODD indicates if the read counter is odd, and WEVEN and WODD indicates if the write counter is even and odd.
At start up of the buffer both pointer values are zero. Signals REVEN and WEVEN are high. Signals RODD and WODD are low. The even read counter 204, the odd read counter 203, the even write counter 202, and the odd write counter 201 hold values 0, 1, 0, and 1 respectively. The flag signal EQE indicates the read and write pointers are equal for the (even read, even write) state, and the flag signal EQO indicates the read and write pointers are equal for the (odd read, odd write) state.
If a write operation is performed just after start up the current state goes from (even read, even write) to (even read, odd write), and a signal selector switches the current flag output as will be described below. In FIG. 3, the rising edge 301 of the write clock signal signals a write operation. Signal WEVEN drops to low and signal WODD rises to high. The rising edge 303 of signal WODD clocks the even write counter 202 and the even write counter 202 increments by 2. As a result the even read counter 204, odd read counter 203, the even write counter 202, and the odd write counter 201 hold values 0, 1, 2, and 1 respectively. The comparator 205 now compares 0 and 2 and drops the EQE signal to low indicating the flag signal for (even read, even write) state.
There is a comparator delay time before the flag signal for (even read, even write) is ready. But the (even read, even write) flag is not needed immediately because the current values of the read and write pointers are 0 and 1. The current flag signal is the (even read, odd write) signal which was predetermined and is ready. The (even read, even write) signal would only be needed after a second write operation. Because successive write operations are separated in time by at least one clock cycle of the writing device there is time for the comparator to complete its operation.
The next write operation causes the odd write counter to increment by 2, from 1 to 3. Subsequent write operations alternate between causing the even write and the odd write counter to increment by 2. Read operations cause exactly analogous increments of the even read and odd read counters.
The outputs signals EQE for the (even read, even write) state, EQO for the (odd read, odd write) state, and permanently low signals for (even read, odd write) and (odd read, even write) are input into a multiplexer which selects the correct signal for flag output. FIG. 5 shows a circuit diagram of a signal selector which in this embodiment is a typical multiplexer that uses the signals REVEN, RODD, WEVEN, and WODD to select the correct flag signal.
In FIG. 5 a NAND gate 501 and an inverter 502 activate pass gate 503 thereby making a signal FLAG equal to the signal EQE when both the read pointer and the write pointer are even. NAND gate 510 and an inverter 511 activate pass gate 512 thereby making a signal FLAG equal to the signal EQO when both the read pointer and the write pointer are odd. When the read pointer is odd and the write pointer is even output from NAND gate 504 is low, output from inverter 505 is high, and n channel transistor 506 switches on. The output signal FLAG is set to a reference voltage GND. Similarly NAND gate 507, inverter 508, and n channel transistor 509 set the signal FLAG to low when the read pointer is even and the write pointer is odd.
The signal flag is set whenever the read pointer and write pointer are equal. Making the signal FLAG an empty flag or a full flag requires additional circuitry that can be coupled to the FLAG output lead. There are many known ways to make the additional circuitry. One way is to combine the signal FLAG with a half full flag through a AND gate for a full flag or a NAND gate for an empty flag. If the buffer is at least half full and the pointers are equal then the buffer is full. If the buffer is less than half full and the pointers are equal then the buffer is empty. Additional circuitry could alternatively check if the last operation was a write. If the last operation was a write to the buffer then there is data in the buffer. The read and write pointer being equal indicates the buffer is full, and the full flag should be set. Otherwise, the last operation must have been a read which emptied the buffer and the empty flag should be set.
Embodiments of the invention may also be used to generate flag signals that are set whenever the difference between the write pointer value and the read pointer value is less than, less than or equal to, greater than, greater than or equal to, or equal to any fixed value. For example a half full flag may be set whenever the buffer is more than half full, or an almost full flag may be set when the buffer is 90% full, or an almost empty flag may be set if the buffer is less than 10% full. To generate these flags a flag generator needs to compare the difference between the pointer values to the fixed value.
For a half full flag or an almost full flag, if i and j are the current values of the read and write pointer, a flag needs to be set if j-i is greater than a value C. For look ahead the current state and three possible future states need to be considered. The look ahead signal generator must determine if j-(i+1), (j+1)-i, and (j+1)-(i+1) are greater than C. Clearly, j-i=(j+1)-(i+1) so states (i,j) and (i+1,j+1) always have the same flag signal, and only three states need to be considered. One method to calculate these flags is to do three multibit subtractions followed by three comparisons to C.
Another method only requires a single multibit subtraction. The subtraction calculates a number X=j-i then relies on the relation (j+1)-i>j-i >j-(i+1), and the fact that all four states have the same flag signal unless j-i=C or j-i=C+i. If j-i=C then the flag is not set for state (i,j) or state (i+1,j), but would be set for state (i,j+1). If j-i=C+1 the flag for states (i,j) and (i,j+1) would be set but the flags for (i+1,j) would not be set.
The look ahead signal generator of FIG. 6 generates the four flag signals f.sub.ij, f.sub.ij+1, f.sub.i+1j, F.sub.i+1j+1 for the states (i,j), (i,j+1), (i+1,j) and (i+1,j+l). These four flag signal are for input into a signal selector which selects a correct predetermined flag signal as the new output flag when the state of the buffer changes.
As shown in FIG. 6, the current flag value may be used in the calculation of flags of the next set of possible states. In the look ahead method the flag for the current state (i,j) is predetermined and therefore available.
XNOR gates 605-608 compare signals representing a four bit binary representation of C with the binary representation of X=j-i. The signals for C.sub.0 -C.sub.3 are either VCC or are ground and can be hard wired for a fixed value of C or can be a programmable value read from a memory. The signals X.sub.0 -X.sub.3 come from a subtractor that subtracts i from j. The output signal from XNOR gate 605 is high if two binary digits X.sub.0 and C.sub.0 are equal, both low or both high. An output signal f.sub.1 from AND gate 604 is high only if all the binary digits are equal.
The logic circuit of FIG. 6 assumes that C and X are four bit numbers. If C and X contain more than four bits then more XNOR gates are needed, and the number of inputs of the AND gate 604 and NAND gate 603 need to be increased. The rest of the circuit remains unchanged.
OR gate 601 sets the signal f.sub.ij+1 high if f.sub.ij is high or if f.sub.1 is high. That the flag signal is correct is shown by simple relationships, if j-i>C then (j+1)-i>C or if j-i=C then (j+1)-i=C+i>C.
The inputs signals on the XNOR gates 609-612 are binary digits of X and (C+1). The output signal f.sub.2 of NAND gate 603 is high unless X=C+1. AND gate 602 sets flag signal f.sub.i+1j high if f.sub.ij is high and X does not equal C+1. Again arithmatic relationships show that this is the correct logic. If j-i=C+1>C then j-(i+1)=C and is not greater than C, but if j-i>C and j-i does not equal C+1 then j-i>C+1, because j-i is an integer, and j-(i+1)=(j-i)-1>(C+1)=1=C.
Although the above paragraphs dealt with a flag such as an half full or almost full flag that was set when the difference between pointers is greater than some value C, the technique applies to flags that are set when the difference between pointer values is greater than or equal to, less than, or less than or equal to a value C. The "greater than or equal to C" flags are equivalent to "greater than C-1" flags, since pointer are integer values. The "less than C" flags such as an almost empty flag can be generated by inverting the value of "greater than C-1" flag.
The look ahead circuits and methods described above have mostly been described in connection with a FIFO buffer. It should be apparent that the invention can be more generally applied to other systems that need to generate status flags.
Although the present invention has been described in detail, the description is only illustrative and not limiting. Other embodiments of this invention will be obvious in view of this disclosure to those skilled in the relevant arts.
Claims
I claim:
1. An apparatus for providing a flag signal indicating a status of a FIFO buffer to a device communicating data through the FIFO buffer, the apparatus comprising: a look ahead signal generator having a plurality of output leads, the look ahead signal generator generating a plurality of possible flag signals one on each of the plurality of output leads, each of the possible flag signals corresponding to a possible state of the FIFO buffer and indicating the status of the FIFO buffer if the FIFO buffer is in the corresponding state; and a signal selector having a plurality of input leads and an output lead, the output lead carrying the flag signal provided to the device communicating data through the FIFO buffer the plurality of input leads of the signal selector being electrically coupled to the plurality of output leads of the look ahead signal generator, the signal selector setting the flag signal on the output lead of the signal selector by selecting one of the possible flag signals generated by the look ahead signal generator.
2. The apparatus of claim 1, wherein the plurality of output leads of the look ahead signal generator provide signals including a flag signal indicating the current status of the FIFO buffer, a possible flag signal indicating the status the FIFO buffer would have after a single write operation, a possible flag signal indicating the status the FIFO buffer would have after a single read operation, and a possible flag signal indicating the status the FIFO buffer would have after a single write operation and a single read operation.
3. The apparatus of claim 1, further comprising a read pointer and a write pointer, the read pointer storing a read pointer value indicating a location in the FIFO buffer where data may be read next, the write pointer storing a write pointer value indicating a location in the FIFO buffer where data may be written next.
4. The apparatus of claim 3, wherein the look ahead signal generator further comprises: a plurality of read counters, each read counter having a plurality of output leads and a clock lead, the plurality of output leads of each read counter providing signals that represent a possible read pointer value; a plurality of write counters, each write counter having a plurality of output leads and a clock lead, the plurality of output leads of each write counter providing signals that represent a possible write pointer value; and a plurality of comparison circuits, each comparison circuit having a first plurality of input leads, a second plurality of input leads, and an output lead, the first plurality of input leads of each comparison circuit being connected to the output leads of one of the plurality of read counters, the second plurality of input leads of each comparison circuit being connected to the output leads of one of the plurality of write counters, the output leads of the plurality of comparison circuits being the output leads of the look ahead signal generator, each comparison circuit providing on the output lead of the comparison circuit a possible flag signal which indicates the status that the FIFO buffer bas if the read pointer value equals the value provided by the connected read counter and the write pointer value equals the value provided by the connected write counter.
5. The apparatus of claim 4, wherein the signal selector further comprises a multiplexer having an output lead, a plurality of select leads, and a plurality of input leads, the plurality of input leads of the multiplexer being the input leads of the signal selector, the output lead of the multiplexer being the output lead of the signal selector.
6. The apparatus of claim 5, further comprising a clock signal generator having a plurality of output leads connected to the clock leads of the plurality of read counters, the clock leads of the plurality of write counters, and the plurality of select leads of the multiplexer, the clock signal generator generating signals which select the flag signal from the plurality of possible flag signals at the input leads of the multiplexer and cause the counters to increment.
7. The apparatus of claim 6, wherein: the plurality of read counters comprises a read odd counter and a read even counter; the plurality of write counters comprises a write odd counter and a write even counter; the plurality of comparison circuits comprise an even-even comparator and an odd-odd comparator, the read even counter and write even counter being connected to the even-even comparator, the read odd counter and write odd counter being connected to the odd-odd comparator, the possible flag signal provided by the even-even comparator indicating if the value in the even read counter equals the value in the even write counter, the possible flag signal provided by the odd-odd comparator indicating if the value in the odd read counter equals the value in the odd write counter; and the plurality of output leads of the clock signal generator comprising a read even lead connected to the clock lead of the read odd counter and connected to a select lead of the plurality of select leads of the multiplexer, a read odd lead connected to the clock lead of the read even counter and a select lead of the plurality of select leads of the multiplexer, a write even lead connected to the clock lead of the odd write counter and a select lead of the plurality of select leads of the multiplexer, and a write odd lead connected to the clock lead of the even write counter and a select lead of the plurality of select leads of the multiplexer, the signals generated by the clock signal generator causing the read even counter to increment by two when the read pointer value changes from even to odd, causing the read odd counter to increment by two when the read pointer value changes from odd to even, causing the write even counter to increment by two when the write pointer value changes from even to odd, and causing the write odd counter to increment by two when the write pointer value changes from odd to even.
8. A circuit for setting a flag signal which indicates whether a read pointer value in a FIFO buffer equals a write pointer value in the FIFO buffer, the circuit comprising: a first, a second, a third, and a fourth counters, each counter storing a count which increments by two when the counter is triggered; a signal generator which generates a first signal indicating whether the read pointer value is even or odd and a second signal indicating whether the write pointer value is even or odd, wherein the first counter is triggered when the first signal changes to indicate the read pointer value is odd, the second counter is triggered when the first signal changes to indicate the read pointer value is even, the third counter is triggered when the second signal changes to indicate the write pointer value is odd, and the fourth counter is triggered when the second signal changes to indicate the write pointer value is even; a first comparator coupled to the first and third counters and providing an output signal indicating whether the count in the first counter equals the count in the third counter; a second comparator coupled to the second and fourth counters and providing an output signal indicating whether the count in the second counter equals the count in the fourth counter; and a selection circuit which sets the flag signal equal to the output signal of the first comparator when the first signal indicates the read pointer value is even and the second signal indicates the write pointer value is even and sets the flag signal equal to the output signal of the second comparator when the first signal indicates the read pointer value is odd and the second signal indicates the write pointer value is odd.