Method for Assigning Priority to Read and Write Requests Received Closely in Time

This invention relates in general to first-in, first-out (FIFO) memories, and in particular concerns an arbiter and method for assigning priority to read and write requests relating to FIFO memories.

First-in, first-out (FIFO) memories are typically used to control data communication from a relatively fast electronic device, such as a microprocessor, to a relatively slower device such as a terminal. Typical FIFO memories have a plurality of cells arranged in rows and columns. A read counter is used to address a location in the memory to be read, and a write counter is used to point to a location into which data is to be written. The read counter is incremented to a next read location responsive to the receipt of read request that originates from one of the devices to which it is connected. The write counter is incremented responsive to the receipt of a write request that originates from the other of the connected devices.

In a previously developed FIFO design, an up/down counter is used to count the difference between the number of read requests and write requests received by the read and write counters. These read and write requests are generated asynchronously. A problem has occurred in accurately recording the above-described difference when the write and read requests arrive closely or simultaneously in time. Without somehow regulating these requests, there is a danger that only one will be recorded and the other lost.

A need has therefore arisen for an arbiter between external read and write signals that will decide which of the signals is to be given priority while storing the other for use to actuate a subsequent operation.

According to one aspect of the invention, an arbiter receives read and write requests and selectively processes these requests for application to a sequential memory unit. The arbiter includes a read circuit for storing a read request and outputting a read signal responsive thereto. A write circuit is provided for storing a write request and to output a write signal responsive thereto. A decision circuit of the arbiter includes a read disabler for disabling the read circuit from outputting the read signal responsive to the decision circuit receiving the write request before the read request. The decision circuit further has a write disabler for disabling the write circuit from outputting a write signal responsive to the decision circuit receiving the read request before the write request. In the event that the read request and the write request are received closely or simultaneously in time, the first of the read and write requests is processed and the second of the write and read requests is processed only after the completion of the processing of the first of the requests.

According to another aspect of the invention, an arbiter is provided for determining the priority between a read request and a write request received closely in time. A read circuit of the arbiter receives a read request and is operable to store a read state and to generate a read clock pulse responsive thereto. A write circuit receives a write request and is operable to store a write state and to generate a write clock pulse responsive thereto. A decision circuit is provided that also receives the write request and the read request. A read disabler of the decision circuit disables the transmission of the read clock pulse responsive to the decision circuit receiving the write request before the read request. A write disabler disables the transmission of the write clock pulse responsive to the direction circuit receiving the read request before the write request. A read/write signal generator of the decision circuit generates a write signal in response to a write request. The arbiter has two outputs. A read/write or UP/DOWN signal is coupled to the read/write signal generator, and outputs a first value corresponding to a read operation or a second value corresponding to a write operation. The second output is a clock output that generates a clock pulse responsive either to the read clock pulse output from the read circuit or the write clock pulse output from the write circuit.

A principle advantage of the invention is that read and write requests received nearly simultaneously will be preserved and processed such that both will be sensed by any device receiving the read/write signal and the clock signal. In the illustrated embodiment where the arbiter is used to supply the signals to an up/down counter, the up/down counter will therefore record both a write request and a read request. The up/down counter is therefore capable of keeping an accurate record of the difference between write and read requests so that memory capacity status flags may be generated at the appropriate points. Other advantages of the invention are conferred by the fact that the arbiter is relatively fast and does not depend upon a clock for its operation. The write/read signal and the clock signal may therefore be generated in real time.

Further aspects of the invention and their advantages are described in the following detailed description in conjunction with the appended drawings, in which:

FIG. 1 is a schematic electrical block diagram of an up/down counter and flag generator circuit incorporating the arbiter of the invention;

FIG. 2 is a simplified schematic block diagram 10 of the arbiter shown in FIG. 1; and

FIG. 3 is a detailed schematic electrical diagram of a preferred arbiter according to the invention.

FIG. 1 is a schematic block electrical diagram of internal flag-generating circuitry according to the invention. This internal flag generating circuitry includes an up/down counter 10 which receives as inputs a plurality of lines WQ0-WQ8 from a write counter (not shown). This write counter, which for example may be a 9-bit binary counter, determines the address location into which data will next be written within an associated FIFO memory (not shown). A read counter (not shown) is provided to determine the location in the FIFO memory from which data is to be read.

Up/down counter 10 records the difference between the read counter and the write counter responsive to signals on input lines 11 and 13. A bivalent signal is input on UPDN or read/write signal line 11 into up/down counter 10. In the illustrated embodiment, a high value of UPDN indicates a write request, and a low value thereof inidcates a read request. Line 13 (WRCLK) supplies a clock pluse that indicates the pesent occurrence of either a write request or a read request, depending on the current value of line 11.

Up/down counter 10 is operable to output a multi-bit signal on lines B0-B8 that indicates how much capacity of the FIFO memory is being used. For example, where the FIFO memory is empty, the signals on lines B0-B8 will all be logic zeros.

Lines B0-B8 are output from up/down counter 10 to a predecoder 12 that is operable to decode each of a plurality of boundary values that are in turn used for the generation of a plurality of internal flags. In the illustrated embodiment, an "empty down" or ED signal is generated on a line 14 from predecoder 12 and is input into a CEMPTY flag generator 16. An "empty up" or EU siganl is generated on an output line 18 and is input into CEMPTY flag generator 16 and also into a CFULL flag generator 20. A "full down" (FD) signal happens to be the same as EU or "empty up". A "full up" (FU) signal is output on a line 22 and is input into CFULL flag generator 20. A "half full up" (HFU) signal is output on a line 24 and is input into a CHF flag generator 26. Finally, a "half full down" (HFD) signal is output from predecoder 12 on a line 28 to CHF flag generator 26.

Each of the signals ED, EU, FU, HFD and HFU are generated respective to a certain value appearing on input signals B0-B8. For example, the "ED" signal is generated responsive to lines B0-B8 inputting 000000010. This corresponds to the FIFO memory being in the condition EMPTY+2, or where only two cells in the memory contain data. A signal is input on EU line 18 when input lines B0-B8 input 000000000, corresponding to a completely EMPTY condition of the FIFO. The ED signal on line 14 and the EU on line 18 are input into flag generator 16 to generate a CEMPTY flag that will be generated when the FIFO memory is in an EMPTY +1 condition.

An FU signal is generated on output line 22 when B0-B8 input 111111110, indicating an ALMOST FULL-1 condition in the FIFO. Flag generator 20 generates the CFULL internal flag when the FIFO memory is 111111111, indicating an ALMOST FULL condition. Therefore, the other boundary condition used to generate this flag is an FD signal on line 18, corresponding to a completely FULL memory.

The HFD signal on line 28 goes high responsive to lines B0-B8 inputting 100000001, coresponding to a HALF FULL +1 condition in the FIFO. The HFU signal on line 24 goes high responsive to B0-B8 inputting 011111111, corresponding to a HALF FULL -1 condition in the FIFO. The HFD and HFU boundary signals are used by flag generator 26 to generate the CHF flag when the memory is exactly HAFL FULL.

UPDN line 11 and clock line 13 are connected to each of flag generators 16, 20 and 26. Flag generators 16, 20 and 26 each use the signals on these lines to set the respective flags on the CEMPTY, CHF and CFULL lines.

A retransmit circuit 30 receives a retransmit signal RETRAN on a line 32 and a master reset signal RSTB on line 34. Responsive to the receipt of a high RETRAN signal on line 32, retransmit circuit 30 will first generate a reset signal on an RT1 output line 38, and after a predetermined delay will generate a pulse on an RT2 output line 36. RT1 and RT2 lines 38 and 36 are connected to up/down counter 10, CHF flag generator 26, CFULL flag generator 20 and CEMPTY flay generator 16. Responsive to high signal on master reset line 34, retransmit circuit 30 will only generate a high signal on RT1 line 38.

The RETRAN signal is sent into the FIFO from a connected reading device (not shown) so that the data just transmitted can be transmitted again. This can happen where the first transmission of the data was garbled or where it is desired to fetch the data several times in sequence. As above noted, up/down counter 10 is operable to store the difference between the write counter and the read counter, thus giving a measure of how full the FIFO memory is.

The RETRAN signal input on line 32 is also used to reset the read counter (not shown) to 0. After a RETRAN signal, the data will be read from the FIFO (not shown) from its 0 location sequentially upward until empty.

Up-down counter 10 increments or decrements according to the signals received on up/down input line 11 and read/write clock (WRCLK) input line 13. When WRCLK line 13 is high and the UPDN signal on line 11 is high, the up/down counter 10 will increment by 1. If the clock signal on WRCLK line 13 is high and the UPDN signal is low, the up/down counter will decrement by 1. In this manner, the difference between the write counter (not shown) and the read counter (not shown) is kept track of. The difference is stored in binary form in a plurality of flip flops (not shown) internal to up/down counter 10.

When the read counter is reset to zero responsive to a RETRAN signal, the actual difference between the value of the read counter and the value of the write counter will not be correctly represented in up/down counter 10. Therefore, responsive to a RETRAN signal, retransmit circuit 30 will generate a high pulse on an RT1 line 38. RT1 line 38 acts to reset each of the flip flops (not shown) within up/down counter 10 to zero. Shortly thereafter, a high pulse on an RT2 line 36 is generated by retransmit circuit 30. This high pulse on RT2 line 36 is transmitted to counter 10 to enable each flip flop therein to receive a corresponding bit value from a respective write control line WQn. Since the address represented on WQ0-WQ8 is the address registered in the write counter, and since at this time the read counter has been reset to 0, the write counter address is equal to the difference between the write counter address and the read counter address. Therefore, up/down counter 10 is able to continue to correctly keep track of the difference between the read counter and the write counter.

Write counter lines WQ0-WQ8 are also directly fed into a preload decoder 44. Preload decoder 44 has a WE output 46, a WF output 48, and a WHF output 50. WE will be high responsive to WQ0-WQ8 being 000000001. Line 46 is connected to CEMPTY flag generator 16, and a CEMPTY flag will be generated responsive to high signal on WE line 46 during a retransmit condition.

WF line 48 is connected to CEFULL flag generator 20. Responsive to WQ0-WQ8 inputting 111111111 into preload decoder 44, the signal on WF line 48 will be high. This in turn actuates flag generator 20 to generate a CFULL flag during a retransmit condition.

WHF line 50 is connected to CHF flag generator 26. Responsive to WQ0-WQ8 inputting 100000000 into decoder 44, WHF line 50 will be high, actuating flag generator 26 to generate a CHF flag during a retransmit condition.

As previously explained, up/down counter 10 increments or decrements responsive to signals on UPDN line 11 and read/write clock line 13. These lines in turn are ouptuts of an arbiter circuit 52. Arbiter circuit 52 receives as inputs a READ request line 54 and a WRITE request line 56. It also receives master reset line 34. As wil be explained in more detail below, arbiter circuit 52 determines the priority between conflicting read and write request signals received on lines 54 and 56. After determining the priority between the read and write operations, it will generate a clock pulse on WRCLK line 13 and the appropriate value on UPDN line 11. If read and write requests are received on lines 54 and 56 at close to the same time, arbiter 52 will actuate up/down counter 10 to first increment and then decrement, or vice versa, sequentially.

RT1 line 38 is input to each of flag generators 16, 20 and 26 and is used as a reset line. RT2 line 36 is input into generators 16, 20 and 26 and is used as a preload enable line.

The illustrated embodiment has an up/down counter 10 with nine bits B0-B8. It will be understood that the number of bits can be easily expanded or contracted without departing from the scope of the invention. Further, while three flag generators have been shown, less than these number of flags may be generated where the flags are not necessary, or other flags can be easily generated to represent any level of use of the FIFO capacity.

Referring now to FIG. 2, a simplified schematic diagram of arbiter 52 is shown. Arbiter 52 is comprised of three main logic blocks: a write circuit 58, a read circuit 60 and a decision-maker logic block 62. Functionally, write circuit 58 is a logic block which recognizes the occurrence of a write request on line 56 and stores a "write" state responsive thereto. Similarly, read circuit 60 operates to recognize a read request input on line 54 and store such a read signal. The decision-maker 62 detects the occurrence of both the read and write requests and is operable to assign the priority of execution of these requests.

As previously described in conjunction with FIG. 1, when arbiter 52 receives a write request on line 56, it will normally generate a high clock pulse at the WRCLK output 13 and also a high state on UPDN or read/write signal line 11. If a read request is received, arbiter 52 normally produces a positive clock pulse at the clock output 13 accompained by a low value at UPDN output 11. When one request signal reaches arbiter 52 while the other is in processing, the signal that is the last to arrive has to wait until the completion of the first-to-arrive signal. When both a read request and a write request arrive almost at the same instant, decision-maker 62 decides the priority and allows only one input to actuate the generation of clock and UPDN outputs. Upon completion of the processing of the higher priority request, the other lower priority can start.

This is accomplished through a write disable output 64 that is output from decision-maker 62 to write circuit 58. Similarly, decision-maker block 62 outputs a read signal on line 66 to read circuit 60. Write circuit 58 is disabled through line 64 from outputting a write clock signal on its output 68 (FIG. 3), and read circuit 60 is disabled by a signal on line 66 from outputting a read clock on its output 70 (FIG. 3). The non-priority request is stored in circuit 58 or 60 until a disabling signal is no longer present on a respective line 64 or 66, at which time the non-priority request will actuate an appropriate clock signal from the circuit where it is stored.

Referring next to FIG. 3, a detailed electrical schematic diagram of a preferred embodiment of arbiter 52 is illustrated. The approximate boundaries of write circuit 58, deciision-maker 62 and read circuit 60, as represented in FIG. 2, are respectively shown in FIG. 3 by the dashed line boxes 58, 62 and 60. A write request signal is input on line 56 to each of a pair of rising edge detectors 80 and 82. The output of edge detector 80 is used as an input to the remainder of write circuit 58, while the output of edge detector 82 is used as in input to the remainder of decision-maker block 62.

In other embodiments, a falling edge may be input on lines 56 and 54 to indicate respective WRITE and READ operations, in which case falling-edge detectors would be used.

Similarly, read request line 54 is input to an edge detector 84 and an edge detector 86. Each edge detector 80-86 is operable to detect a rising edge on write line 56 or read line 54. When such a rising edge is detected, each edge detector 80-86 is operable to output a negative pulse at its output.

Referring particularly to edge detector 80, and output line 88 thereof is connected to the gate of a p-channel transistor 90, which is a portion of a write latch indicated generally at 92. A negative pulse on line 88 is operable to connect a latch node 94 at the source of transistor 90 to VCC, thereby storing a logic "1" at node 94. Node 94 is connected to an input of an inverter 96, which in turn has an output connected to a write latch output node 98. Node 98 serves as an input to a second inverter 100 that has an output connected back to node 94. The pair of inverters 96 and 100 therefore serve as a latch that stores one state at node 94 and a second, opposite state at node 98. In the instance where node 94 store a logic "1 ", node 98 stores a logic "0".

In the read circuit, rising edge detector 86 similarly has an output 102 that is connected to the input of a latch indicated generally at 104. Line 102 is connected to the gate of a P-channel transistor 106. The current path of P-channel transistor 106 can be actuated to connect VCC to a read latch node 108. Node 108 is connected through a first inverter 110 to a node 112. Node 112 is in turn connected to the input of a second inverter 114. The output of node 114 is connected back to node 108.

As to the second pair of edge detectors, rising edge detector 82 has an output 116 connected to a first input of a NAND gate 118. Rising edge detector 84 similarly has an output 120 that is connected to a first input of a NAND gate 122.

The output node 98 of wire latch 92 is connected through a line 124 to the input of a delay gate 126. The output of delay gate 126 is connected through a line 128 to a second input of NAND gate 118. Similarly, the output node 112 of read latch 104 is connected through a line 130 to an input of a delay gate 132. The output of delay gate 132 is connected to a node 134, which in turn is connected to an input of an inverter 136. Node 134 is further connected to a second input of NAND gate 122.

The output of inverter 136 is connected to a falling-edge detector 138. Falling edge detector 138 has an output 140 that is connected to the gate of an n-channel reset transistor 142. N-channel transistor 142 is a portion of a read/write signal latch indicated generally at 144. Falling-edge detector 138 is operable to generate a positive pulse on its output 140. This in turn operates reset transistor 142 to connect a read/write latch node 146 to ground. Node 146 is connected to an input of a first inverter 148, which in turn has an output that is connected to a second read/write signal latch node 150. Node 150 is in turn connected to the input of an inverter 152 that has an output connected back to latch node 146. Nodes 146 and 150 will therefore store opposite states.

Serving as a WRITE request input of decision-making block 62, NAND gate 118 has an output 154 that is connected to the input of an inverter 156. The output of inverter 156 is connected by a line 157 to the input of a NAND gate 158. Serving as the READ request input of decision block 62, the output of NAND gate 122 is connected through a line 160 to a second input of NAND gate 158.

The output of NAND gate 158 is connected through line 162 to the gate of a p-channel transistor 164. A low state on line 162 will therefore cause transistor 164 to connect node 146 to VCC, thereby causing a high state to be stored at latch node 146 and a low state at latch node 150.

Output node 98 of write latch 92 is connected to the input of a delay gate 166. The output of delay gate 166 is connected through a line 168 to a first input of a disabling NOR gate 170. Somewhat similarly, output node 112 of read latch 104 is connected through a line 172 to an inverter 174. The output of inverter 174 is connected through a line 176 to a node 178. Node 178 is connected to a first input of a disabling NAND gate 180, and is further connected to a first input of an UPDN output NAND gate 182.

Inside read/write signal latch 144, latch node 150 is connected to the input of an inverter 184. The output of inverter 184 is in turn connected through a line 186 to a read/write signal node 188. Node 188 is connected through line 64 to a second input of disabling NOR gate 170, through line 66 to a second input of disabling NAND gate 180, and through line 192 to a second input of UPDN NAND gate 182.

The output of write-disabling NOR gate 170 is connected to a write clock signal node 196. Node 196 is in turn connected to an input of an inverter 198, and further through a line 200 back to an input of a delay gate 202. The output of delay gate 202 is connected through a line 204 to the gate of an n-channel reset transistor 206. N-channel transistor 206 is operable to reset write latch node 94 to ground. In the other branch, the output of inverter 198 is connected by line 68 to a first input of a write/read clock output NAND gate 208.

The output of read disabling NAND gate 180 is connected to a read clock signal node 210, which in turn is connected to an input of a delay gate 212. The output of delay gate 212 is connected via read clock line 70 to a second input of write/read output NAND gate 208. Read clock signal node 210 is also connected through a line 214 back to the input of an inverter 216. Inverter 216 has an output connected through a line 218 to the gate of an n-channel reset transistor 220. N-channel transistor 220 is operable to reset read latch node 108 to ground upon the receipt of a high state on line 218.

Master reset line 34 is connected to the gate of an n-channel reset transistor 224 inside read latch 104, the gate of an n-channel reset transistor 226 in read/write signal latch 144, and to the gate of n-channel reset transistor 228 inside write latch 92. A high pulse on reset line 34 operates to reset each of latch nodes 108, 94 and 146 to ground.

In operation, suppose that a positive-going pulse is received on input write request line 56. Rising edge detector 80 will output a low pulse on line 88 responsive to sensing the positive transition on line 56. This in turn will cause a high state to be stored at write latch node 94, and therefore a zero state to exist at write latch output node 98.

Read latch 104 behaves in a similar manner to write latch 92. Responsive to a positive-going edge on read request line 54, rising edge detector 86 wil output a negative pulse on output line 102, thereby causing latch node 108 to store a high state and latch node 112 to store a low state.

Read/write signal latch 144 behaves in a manner somewhat similar to write latch 92 and read latch 104. A high state at node 157, in combination with a high state on line 160, causes arbiter NAND gate 158 to output a low state on line 162. This low state causes a high state to be stored at latch node 146. A low state will therefore be stored at latch node 150. Unlike latches 92 and 104, the low state at node 150 is inverted through inverter 184, and is output as a high state at read/write signal node 188.

A low state at node 188 (the reset condition) enables NOR gate 170 through line 64 and disables NAND gate 180 through line 66. If there is a rising edge at the write request input 56, rising edge detector 80 will detect this transition and generate a negative pulse on line 88 to write latch 92. Write latch output node 98 will therefore be low. This low state will be propagated through line 124, delay gate 126 after a predetermined delay, and line 128 to the second input of NAND gate 118. Therefore, the node 157 will stay low. A low at node 157 disables arbiter NAND gate 158 and prevents any read request from interrupting a current write operation.

Simultaneously with this action, rising edge detector 82 detects the same transition of the write input 56 and sets its output 116 low. Since one input of NAND gate 118 is low, its output will be high at 154, and node 157 wil be low. This happens before the other input 128 of NAND gate 118 goes low, and therefore speeds the acquisition by node 157 of a low state.

The output 116 of detector 82 will go high after a predetermined delay. The write request is however preserved by the apperance of a low state on node 128, which in turn is generated by detector 80 and the circuitry thereafter. Therefore, if a write request is forced to wait, it will be preserved for as long as necessary.

Read/write signal node 188 is meanwhile enabling NOR gate 170 due to its low state. The low state at write latch output node 98 will be propagated through delay gate 166 after a predetermined delay. This low state will then appear at input 168 of NOR gate 170. The low state at input 168 in combination with the low state on input line 64 causes NOR gate 170 to output a high state to write clock node 196. The high state at node 196 will be inverted through gate 198 to a low state on line 68, which in turn will cause a high state on write/read output clock line 13.

In the meantime, the high state at write clock node 196 will be propagated after a predetermined delay back through delay gate 202 to the gate of reset transistor 206, resetting latch 92 to ground. Responsive to resetting latch 92, the read/write clock output 13 will go low and node 157 will go high, thereby concluding the write processing. The UPDN or read/write signal output line 11 stays high during the above operation to indicate a write request.

If a rising edge is detected on read input line 54, rising edge detectors 84 and 86 and read latch 104 operate in the same manner as rising edge detectors 82 and 80 and write latch 92 operate in response to a rising edge of a write request input on line 56. The rising edge at read input line 54 will eventually result in a high state on read line 160. This effectively requests decision-maker 62 to do a read enable. However, if a write request signal is already in processing, node 157 will have been set low and will act to disable arbiter NAND gate 158 from propagating the read request signal. In this case, a high read request at node 160 cannot get the attention of read/write signal latch 144. Therefore, read latch 104 operates to latch the read request and waits until arbiter gate 158 is enabled.

Upon completion of the conflicting write command, node 157 wil go high, thus enabling arbiter gate 158. Both high inputs of NAND gate 158 will generate a low state on output line 162, thereby latching a high state at latch node 146, a low state at latch node 150 nd a high state at read/write signal node 188. A high state at node 188 disables NOR gate 170. Therefore, if there is a write request received at this moment, latch 92 is prevented from sending a stored write request to write clock node 196. Further, since the signal is not propagated through to node 196, the write latch 92 cannot be reset as long as the NOR gate is disabled through a high state at its input 64. The write request in effect has to wait until the read has been completed.

A high at node 188 also enables NAND gate 180. Therefore, a low experienced at read latch output node 112 sets the up/down output line 11 low to indicate a read request. In the meantime, the low state at read clock node 210 is propagated and inverter back through inverter 216 after a predetermined delay, and becomes a high state on line 218. A high state online 218 operates reset read latch node 108 to ground. This completes the read processing and returns arbiter 52 back to its original status.

The connection between node 178 and up/down signal output NAND gate 182 is a speed-up path that pulls the UPDN output 11 high before read/write signal node 188 does. This prevents a long delay path through delay gate 132, inverter 136, descending edge detector 138 and latch 144.

The determined delays of delay gates 126, 202, 166, 136, 174, 132, 221 and 216 are adjusted to adjust the time relationship between inputs and outputs, between the clock output 13 and the UPDN output 11, and between consecutive clock outputs appearing at clock output 13.

The time boundary between awarding priority to a write request in view of a near-simultaneous read request, or vice versa, is established as follows. If a read request is received before a write request, write/read signal node 188 will disable write NOR gate 170 and will enable read NAND gate 180. As the write request becomes closer in time to the read request, the low pulse from arbiter gate 158 will weaken until read/write signal latch 144 will no longer "flip" to store a "read signal" state.

In summary, an arbiter for setting priority between received read requests and write request for use in a FIFO memory has been shown. The arbiter is also useful in other sequential memories, such as last-in, first-out (LIFO) or stack memories. The arbiter effectively stores write and read requests that appear at its inputs simultaneously or near-simultaneously, and assigns the priority between these requests. While one request is being carried out, the other is stored such that both may be correctly processed. In the illustrated embodiment, write/read clock and up/down pulses are generated to operate an up/down counter and a set of flag generators.

While an illustrated embodiment and its advantages have been described in the above detailed description, the invention is not limited thereto but only by the spirit and scop of the appended claims.