1. Field of the Invention
The present invention relates generally to computer systems, and more particularly to a system and method for implementing flow control in computer systems.
2. Related Art
As is well known, a central processing unit (CPU) often interacts with input/output (I/O) devices via programmed input/output (PIO) instructions. For example, a CPU may send a read PIO instruction to an I/O device when it wishes the I/O device to read data from a location. The CPU may send a write PIO instruction to an I/O device when it wishes the I/O device to write data a location.
A CPU sends a PIO instruction to an I/O device via a bus. Conventionally, the I/O device has a first-in first-out (FIFO) buffer for storing PIO instructions received from the CPU. When the I/O device is ready to process a PIO instruction, the I/O device extracts a PIO instruction from the FIFO buffer. Then, the I/O device processes the extracted PIO instruction.
As will be appreciated, the size of the FIFO buffer in the I/O device is finite. Also, the CPU may send PIO instructions to the I/O device at a rate faster than the rate at which the I/O device can process the PIO instructions. This represents a problem, since the CPU may attempt to send additional PIO instructions to the I/O device after the I/O device's FIFO buffer is full. This is called the flow control problem.
A first conventional solution to the flow control problem involves an acknowledgment (Ack), negative acknowledgment (Nack) handshaking scheme. In the first conventional solution, the I/O device sends an Ack signal to the CPU when it has received and stored a PIO instruction in its FIFO buffer (that is, when there is room in the I/O device's FIFO buffer to store the PIO instruction received from the CPU). The I/O device sends a Nack signal to the CPU when it has received and discarded a PIO instruction (that is, when there is not enough room in the I/O device's FIFO buffer to store the PIO instruction received from the CPU). When the CPU receives a Nack signal from the I/O device, the CPU resends the PIO instruction to the I/O device at a later time.
The first conventional solution is flawed because it reduces the effective throughput of the bus. This is the case, since the first conventional solution requires the I/O device to transmit Ack and Nack signals to the CPU, and since it requires the CPU to retransmit PIO instructions when it receives a Nack signal from the I/O device. The transmission of these messages over the bus (particularly the retransmission of PIO instructions from the CPU to I/O devices) represents overhead that results in reducing the effective throughput of the bus.
A second conventional solution to the flow control problem requires that the I/O device transmit a "buffer full" message to the CPU when its FIFO buffer is full. The I/O device transmits a "buffer not full" message to the CPU when its FIFO buffer is not full. When the CPU receives a "buffer full" message, the CPU discontinues sending PIO instructions to the I/O device, and does not begin sending more PIO instructions to the I/O device until it receives a "buffer not full" message from the I/O device.
The second conventional solution solves the problem of the first conventional solution, since the second conventional solution does not require the CPU to retransmit PIO instructions to I/O devices. However, the second conventional solution suffers from a latency problem.
As will be appreciated, a certain amount of time passes between the transmission of a "buffer full" message by the I/O device, and the receipt of the "buffer full" message by the CPU. During this time, the CPU may send one or more PIO instructions to the I/O device. The I/O device must have room in its FIFO buffer to store these PIO instructions (otherwise, the second conventional solution would not represent a complete solution to the flow control problem).
Most conventional systems solve this "latency" problem by having the I/O device send the "buffer full" message when its FIFO buffer is only partially full. The remaining capacity (also called "slack") of the FIFO buffer is used to accommodate any PIO instructions sent by the CPU after the transmission of the "buffer full" message. This solution is flawed, however, since it solves the latency problem at the expense of storage capacity of the I/O device's FIFO buffer. That is, this solution is flawed because the I/O device regularly cannot use the complete capacity of its FIFO buffer to store PIO instructions. This is the case, since a portion of the FIFO buffer must be reserved for PIO instructions sent by the CPU after the transmission of the "buffer full" message (this reserved portion of the FIFO buffer is called latency overhead).
A third conventional solution to the flow control problem requires that the I/O device transmit a "Request for PIO instruction" message to the CPU when it wants the CPU to transmit a PIO instruction. When the CPU receives the "Request for PIO instruction" message, the CPU sends a PIO instruction to the I/O device. The third conventional solution is flawed, however, since it results in a great deal of latency between when the CPU receives a PIO instruction (from a client process, for example), and when the CPU transmits the PIO instruction to the I/O device. This is the case, since the CPU must wait until it receives a "Request for PIO instruction" message to send a PIO instruction.