Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1999-05-07
2003-01-28
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C710S033000, C710S065000, C710S305000, C710S310000
Reexamination Certificate
active
06513105
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to computer systems and, more particularly, to an improvement in buffered communications with a host processor. A major objective of the invention is to reduce the processing overhead involved in servicing a RAM-based FIFO buffering data transfers between a host processor and a remote communications device.
Much of modern progress is associated with advances in computer technology. Computers have advanced from 8-bit processors performing a few million operations per second, to 16-bit processors performing tens of millions of operations per second, and to 32-bit and beyond processors performing hundreds of millions of operations per second. As computers have become more powerful, the tasks they perform have diversified. To perform these tasks, various types of peripherals, e.g., printers, modems, scanners, pointing devices, and keyboards are connected to computers.
In many cases, for example with modems, the rate at which data is transferred falls far below the rate at which a host processor can process data. To more fully utilize available computer power, communications with the host processor are typically buffered. Thus, when a host processor is to transmit (“write”) data, it transfers the data quickly to a buffer. The remote device then reads the data from the buffer at its own, typically relatively slow, rate, while the host processor attends to other tasks. When the buffer is empty or nearly empty, the buffer notifies the host processor, which can then supply a next packet of data. Likewise, data transferred from a remote device to a host processor can be buffered. The buffer can be filled slowly. Once the buffer contains a useful amount of data, it can be transferred to (“read” by) the processor rapidly.
Typically, such buffers transmit first the data that is received first. In other words, they are first-in-first-out (FIFO) devices. A typical FIFO implementation includes a random access memory (RAM) array, in which data is stored at consecutive address locations. A read pointer is, typically, a register that indicates the memory location of the oldest received data that has not yet been read; in the case of a read operation, the read register is incremented each time the contents of the memory location is read. Likewise, a write pointer points to a memory location following that most recently written to; in the case of a write operation, the write pointer is incremented each time data is stored in a FIFO memory location.
Reads begin at the location indicated by the read pointer, while writes begin at the location indicated by the write pointer. The difference in the addresses associated with the read and write pointers indicates the amount of data stored in the FIFO. (The difference is calculated modulo the number of FIFO memory locations to accommodate wrapping of data from the highest to lowest addresses.)
In the case of a serial remote device, such as those using a Universal Asynchronous Receiver Transmitter (UART), data is transmitted between the FIFO and the remote device one-bit at a time. Typically, a shift register groups the bits into bytes (groups of eight bits). When the shift register is full, the data can be output in parallel to a byte-wide memory location. It should be noted that such FIFOs are not limited to serial remote devices; for example, byte-wide parallel communications with a remote device are provided for—eliminating the need for an input shift register.
Clearly, this grouping of bits can be applied for whatever data width is associated with the FIFO. U.S. Pat. No. 5,673,396 to Smolansky et al. discloses a FIFO in which this width is selectable so that a tradeoff can be made between the number of memory locations and the amount of data that can be stored per memory location.
The communications path between the FIFO and the host processor is typically parallel. For example, byte-wide data busses carry stored data one byte at a time between the processor and the FIFO. Typically, a read FIFO transmits interrupts to a processor to indicate when it is empty, has any data, has a meaningful amount of data, is almost full, and is full. The processor can then inquire of the FIFO the actual amount of data stored and initiate a transfer of the data. Once the transfer is complete, the host processor can return to whatever task it was attending to before the transfer while the remote device begins to refill the FIFO.
The transfer between the FIFO and the host processor takes place at a much higher rate than does the transfer between the FIFO and the remote device. For this reason, the transfers occupy only a small portion of the host processor's duty cycle. The remaining portion of the duty cycle can be utilized for other tasks. Of course, any available capacity is readily consumed by other tasks assumed by the computer. From the perspectives of these tasks, any servicing of the FIFO can appear as a performance limitation. What is needed is a system that minimizes the performance impairment due to the servicing of a communications FIFO.
SUMMARY OF THE INVENTION
The present invention provides for dynamically varying the widths of synchronous read and write transfers between a host processor and a FIFO during the course of a data transfer procedure. (Herein, a “transfer procedure” refers to a transfer of data that coexists in the FIFO either at the beginning or at the end of the procedure.) The FIFO can have a minimum transfer width, a maximum transfer width, and, optionally, one or more intermediate transfer widths. Preferably, all transfer widths are integer multiples of the minimum transfer width. The dynamic change allows remainders data to be transferred efficiently. This is not the case for the non-dynamic storage width variation disclosed in U.S. Pat. No. 5,673,396 (which varies storage width, but not during a data transfer procedure).
Preferably, maximum-width transfers are implemented until there is insufficient data for a maximum-width transfer. Any remainder is then transferred using lesser-width transfers. For example, if the FIFO permits only quadlet (four-byte) and singlet (one-byte) synchronous transfers, quadlet transfers can be implemented until there are fewer than four bytes of data left to be transferred; any remainder is transferred using singlet transfers. If the FIFO also permits doublet (two-byte) transfers, such a transfer can be used whenever the remainder equals two or three bytes. If triplet (three-byte) transfers are permitted in addition to quadlet, doublet, and singlet, only one remainder transfer is required for each transfer procedure. The various alternatives involve a tradeoff between the maximum number of transfers that might be required for a transfer procedure and complexity of the FIFO.
In the case of a write operation, the processor “knows” the amount of data to be transferred and thus can arrange the data optimally into maximum width, intermediate width and minimum width groups. In the case of a read operation, the processor can access a register in the FIFO that indicates the amount of data to be read so that the data can be grouped optimally. The processor determines the width of each transfer. For example, this can be done by assigning each transfer width to a different memory-mapped IO address associated with the FIFO. The FIFO is designed to set the transfer width according to the address asserted by the processor.
The FIFO increments a pointer in association with each transfer. A write pointer is incremented during a write operation, and a read pointer is incremented during a read operation. The amount of the increment is dependent on the transfer mode. A unit increment corresponds to a minimum-width transfer. The ratio of the actual transfer width to the minimum transfer width determines the multiple of the unit for incrementing the pointers in the various transfer modes. Thus, the appropriate pointer is incremented four units for each quadlet (four-byte) transfer for a FIFO with a singlet (one-byte) minimum transfer width.
The FIFO control logic res
Chace Christian P.
Kim Matthew
Koninklijke Philips Electronics , N.V.
Zawilski Peter
LandOfFree
FIFO system with variable-width interface to host processor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with FIFO system with variable-width interface to host processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FIFO system with variable-width interface to host processor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3037893