Error detection/correction and fault detection/recovery – Pulse or data error handling – Memory testing
Reexamination Certificate
1999-11-15
2002-06-18
Tu, Christine T. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Memory testing
C714S763000, C714S800000
Reexamination Certificate
active
06408409
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to communication of digital data. More specifically, the present invention relates to a method and an apparatus for detecting underflow or overflow conditions within a ring buffer.
2. Related Art
As data transfer rates within computer systems continue to increase, it is becoming harder to coordinate the sending and receiving of data between computer system components. Data is typically transferred between computer system components under control of a global clock signal that is used to control when data is sent and received.
As clock frequencies are increased to provide faster data transfer rates, clock skew can become a significant problem. Clock skew causes a global clock signal to arrive at various computer system components at different and unpredictable times. Hence, a first component that sends data to a second component cannot be certain when the data will be latched by the second component. Clock skew is especially significant between computer system components that are located on different modules or on different chips.
One way to remedy some of the communication problems involved in transferring data between computer system components is to buffer data transfers between computer system components using a FIFO that is implemented as a ring buffer. A ring buffer typically includes an array of data entries as well as a read pointer and a write pointer. As data arrives at the ring buffer, it is stored in the ring buffer using the write pointer to advance through the array and store consecutive data items in consecutive locations in the array. When the write pointer reaches the end of the array it wraps around to the beginning. On the receiving side, the read pointer is used to retrieve consecutive data items from the array.
Unfortunately, a ring buffer can be prone to overflow and underflow errors. An overflow error occurs when the array becomes full and write pointer advances through the read pointer, causing data to be overwritten before it can be read. An underflow error occurs when the array becomes empty and the read pointer advances through the write pointer and reads entries before they are written.
Flow errors, such as underflow errors or overflow errors, typically cannot be detected by examining data as it is received. Conventional error detecting and error correcting techniques (such as error correcting codes and error detecting codes) are able to detect when one or more bits in a data word are changed during a data transfer. However, they cannot detect when an entire data word is substituted as the result of an overflow or an underflow error.
In a particularly versatile implementation, write pointer logic uses a clock associated with the data arriving from a remote source, while read pointer logic uses a local clock. The use of multiple clocks makes flow error detection particularly difficult.
What is needed is a method and an apparatus that allows overflow and underflow errors to be detected by examining data that is received at the end of a data transfer process.
SUMMARY
One embodiment of the present invention provides a system for detecting underflow and overflow errors arising within a ring buffer. When the system receives a data word to be transferred through the ring buffer, the system generates a flow indicator value to be stored with the data word in the ring buffer. This flow indicator value contains information that facilitates determining if an underflow has occurred while reading from the ring buffer, or if an overflow has occurred while writing to the ring buffer. Next, the system writes the data word along with the flow indicator value into an entry in the ring buffer. At a later time, the system reads the entry from the ring buffer and generates a predicted flow indicator value. The system compares the flow indicator value read from the ring buffer with the predicted flow indicator value. If the flow indicator value differs from the predicted flow indicator value, the system generates an error signal indicating that an underflow or an overflow has occurred.
In one embodiment of the present invention, the flow indicator value periodically changes, so that a predictably different flow indicator value is written into the entry in the ring buffer upon successive write operations to the entry. This predictably different flow indicator value allows the system to detect an underflow condition or an overflow condition by comparing the flow indicator value with the predicted flow indicator value. If the flow indicator value read from the ring buffer differs from the predicted flow indicator value, an underflow condition or overflow condition has occurred.
In one embodiment of the present invention, the flow indicator value includes a single bit that changes every time a write pointer for the ring buffer reaches a maximum value.
In one embodiment of the present invention, the flow indicator value is encoded as changes between even and odd parity within a parity bit in the data word.
In one embodiment of the present invention, the ring buffer is of odd size and the flow indicator value is a single bit that alternates between zero and one on successive write operations.
In one embodiment of the present invention, the flow indicator value is encoded as changes between even and odd parity in a parity bit in the data word. Furthermore, the ring buffer is of odd size and the parity bit alternates between even and odd parity on successive write operations.
In one embodiment of the present invention, the flow indicator value further includes a flow direction indicator that allows an underflow error to be differentiated from an overflow error.
REFERENCES:
patent: 4692893 (1987-09-01), Casper
patent: 5208810 (1993-05-01), Park
patent: 5469545 (1995-11-01), Vanbuskirk et al.
patent: 5581705 (1996-12-01), Passint et al.
patent: 5732286 (1998-03-01), Leger
patent: 5765187 (1998-06-01), Shimizu et al.
patent: 5884099 (1999-03-01), Klingelhofer
patent: 5898893 (1999-04-01), Alfke
patent: 5978868 (1999-11-01), Maas
patent: 6212161 (2001-04-01), Regula
patent: 6233675 (2001-05-01), Munson et al.
patent: 0 185 924 (1985-11-01), None
Castel-Branco, L.; Nunes, M.S., ‘Clock recovery for circuit emulation services over ATM’, Proceedings of the International IFIP-IEEE Conference on Broadband Communications, 1996. Global Infrastructure for the Information Age, 1996, pp. 617-625.*
IBM Technical Disclosure Bulletin entitled “Highly Reliable Data Buffer which Provides for Both One-and Two-Byte Operations,” by D.J. Lang and R.G. Nelson, vol. 23, No. 3, Aug. 1980.
IBM Technical Disclosure Bulletin entitled “Efficient Dual-Port First-In, First-Out Buffer with an Overrun and Underrun Detection Scheme,” vol. 23, No. 12, May 1991.
IBM Technical Disclosure Bulletin entitled “Error Detection Method for Ram with Stuck Output Latches,” vol. 23, No. 7, Dec. 1990.
Phelps Andrew E.
Williams Emrys J.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Torres Joseph D.
Tu Christine T.
LandOfFree
Method and apparatus for ring buffer flow error detection 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 ring buffer flow error detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for ring buffer flow error detection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2949911