Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2001-03-19
2004-02-17
Huynh, Kim (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S057000, C365S189050, C370S229000
Reexamination Certificate
active
06694389
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data transmission, and in particular to a method and apparatus for analyzing the flow of data through one or more buffers.
2. Background Art
In electronic systems, data items are transmitted between data producers and data receivers. A first-in-first-out (FIFO) buffer is commonly used between such producers and receivers. It is desirable to ensure that the FIFO buffer does not become full (congested) or empty (starved) during the transmission. Thus, the state of the FIFO is monitored, which enables the data producer and data receiver to modify their transfer rates to avoid filling or emptying the queue. Prior art monitoring schemes are undesirable for use with ripple FIFO buffers. A ripple FIFO buffer is comprised of a plurality of FIFO buffers connected in series. This problem can be better understood by a review of data transmission.
Data Transmission
When data is transmitted from a data producer to a data receiver, problems arise when the data producer's clock speed is different from the data receiver's clock speed. The clock speed regulates how fast the device can execute commands. If the data producer's clock speed is faster than the data receiver's clock speed, the data receiver may be unable to process the data as quickly as it is sent. Thus, some data items in the transmission may be lost.
Buffers
A buffer is a space in a computer's memory where data is temporarily stored. One use of a buffer is to prevent data loss due to differing clock speeds of separate computers attempting to exchange data. The data producer sends data items to the buffer. The buffer stores the data items until the data receiver is ready to receive more of the transmission. The buffer's clock speed is typically at least as fast as the clock speeds of both the data producer and the data receiver. Thus, no data is lost as a result of differing clock cycles.
Additionally, data transmissions typically occur in bursts. Without buffers, the data producer and data receiver must devote some or all of their resources to handling the data transmissions as they happen. As a result, the data producer and data receiver experience gaps of time where resources are available to handle data transmission, but no transmission exists. Additionally, the data producer and data receiver experience times where resources are not available to handle data transmission, but a transmission must occur. Buffers allow the data producer and the data receiver to schedule the transmission to take advantage of the times when resources are available.
FIG. 1
illustrates the operation of a buffer for a data transmission. At step
100
, it is determined whether the data producer sent a data item. If the data producer sent a data item, at step
110
, the item is stored in the buffer and the process moves on to step
120
. If the data producer did not send a data item, the process moves directly to step
120
. At step
120
, it is determined whether the data receiver requested a data item. If the data receiver requested a data item, at step
130
, the buffer sends a data item to the data receiver and the process repeats at step
100
. If the data receiver did not request a data item, the process repeats at step
100
.
FIFO Buffers
First-in-first-out (FIFO) buffers ensure the data items are received by the data receiver in the same order they are sent by the data producer. A FIFO buffer always sends the oldest data item in the buffer to the data receiver first.
FIG. 2
illustrates the operation of a FIFO buffer. At step
200
, it is determined whether the data producer sent a data item. If the data producer sent a data item, at step
210
, the item is stored in the FIFO buffer and the process moves on to step
220
. If the data producer did not send a data item, the process moves directly to step
220
. At step
220
, it is determined whether the data receiver requested a data item. If the data receiver did not request a data item, the process repeats at step
200
. If the data receiver requested a data item, at step
230
, the FIFO buffer locates the oldest data item in the FIFO buffer. At step
240
, the FIFO buffer sends the oldest data item to the data receiver and the process repeats at step
200
.
Ring FIFO Buffers
Conventional FIFO buffers are typically implemented using a ring buffer. A ring buffer has an amount of storage space, a read pointer and a write pointer. A pointer is a location in a computer's memory that contains another memory location where data can be obtained or stored. As data items are added to the buffer, the write pointer is incremented to the next open position corresponding to the location in the computer's memory where the next data item in the buffer will be stored. Similarly, as data items are sent to the data receiver, the read pointer is incremented. Once a pointer reaches the end of the buffer, it repeats at the beginning of the buffer.
FIG. 3
illustrates a ring FIFO buffer. Data Items A(
300
), B(
310
) and C(
320
) are stored in the buffer in locations 1 (
330
), 2 (
340
) and 3 (
350
) respectively. The write pointer (
360
) points at location 4 (
370
). The read pointer (
380
) points at location 1. Locations 4 and 5 (
390
) are empty.
Ripple FIFO Buffers
A ripple FIFO buffer is comprised of a plurality of FIFO buffers connected in series.
FIG. 4
illustrates a ripple FIFO buffer. The ripple FIFO buffer (
400
) is comprised sub-buffers 1 (
410
), 2 (
420
) and 3 (
430
). A data item (
440
) sent by the data producer (
450
) to the data receiver (
460
) would first pass through sub-buffer 1. Then, the data item would pass through sub-buffer 2. Next, the data item would pass through sub-buffer 3 before being sent to the data receiver.
If the data transfers between sub-buffers are not regulated by a clock, the buffer is termed an “asynchronous ripple FIFO buffer.” Ripple FIFO sub-buffers implemented with asynchronous building blocks are very fast relative to clock cycles of typical data producers and data receivers. Thus, asynchronous ripple FIFO buffers can be embedded in clocked systems. The clock signal of the data producer or data receiver can be used to generate a request to the asynchronous ripple FIFO buffer.
To allow maximum flexibility to deal with bursts at the data sender or data receiver, it is desirable that the FIFO buffer be kept neither completely full nor completely empty. Half full may be a desirable state, where the is sufficient room to store a data sender burst and sufficient data stored to satisfy a data receiver burst. In one method, if the FIFO buffer is greater than half full, the FIFO buffer is becoming congested. If the FIFO buffer is less than half full, the FIFO buffer is becoming starved.
In another method, some point other than half full is the boundary between becoming congested and becoming starved in a FIFO buffer. In yet another method, a range of fullness is defined as the boundary. For example, a FIFO buffer may only be considered becoming starved when it is less than one third full while it is only considered becoming congested when it is greater than two thirds full. An important concern is to avoid overflow or underflow.
It is important to ensure there is space available at the input end of the asynchronous ripple FIFO buffer whenever the data producer wishes to insert a data item. The situation where no space is available when the data producer attempts to insert a data item is termed “overflow.”
Additionally, it is important to ensure there is always a data item available at the output end of the asynchronous ripple FIFO buffer whenever the data receiver wishes to receive a data item. The situation where no data item is available when the data receiver attempts to remove a data item is termed “underflow.”
Flow Control
In a conventional system, each end of a FIFO buffer operates in a different local clock domain. In some designs the two clocks are mesochronous. Mesochronous clocks have the same frequency but an unknown ph
Coates William S.
Greenstreet Mark R.
Huynh Kim
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for data flow analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for data flow analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for data flow analysis will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335579