US 4,692,894 AGranted

Overflow/Underflow detection for elastic buffer

AssigneeAdvanced Micro Devices, Inc.

InventorGerald L. Bemis

Life of this patent

Estimating the term…

Loading patent…

Abstract

An elastic buffer includes a memory array for storing received data, each location within the array having an associated cell storing a flag indicative of the most-recently performed (i.e., read or write) on the associated memory location. A potential write overflow of the memory is detected whenever a write attampt is made to a location whose flag indicates a write was most-recently performed. A potential read underflow is detected whenever a read attempt is made to a location when the flag associated with the location next to be read indicates a read was most recently performed. Also, a potential write operation of a memory location prior to the completion of a read on the next location within the array are also generates an overflow/underflow condition. Metastable logic state conditions within the array are avoided because the potential overflow/underflow conditions take cognizance of the finite propogation and setting times of signals within the array. The overflow/underflow signals generated within the array are provided to circuitry which controls the issuance of the underflow/overflow signal by the array. This circuitry includes a circuit which provides an extended time window to allow full decay or setting of any metastable signal applied thereto. The control circuitry ensures that an overflow/underflow detection signal issues only when data is in transit through the buffer.

Claims9

Dependent claims

An elastic buffer receiving a first data stream at a first predetermined rate, converting said first data stream to a second data stream at a second predetermined rate, and providing said second stream, said elastic buffer generating a stable buffer overflow/underflow signal, said elastic buffer comprising:

a source of clock signals;
means for generating a plurality of first and a plurality of second read select signals and a plurality of write select signals;
a plurality of addressable storage means connected to said read/write select means each for storing said received data when a predetermined one of said first plurality of read signals is received and for generating signals indicative of said stored data when a predetermined one of said plurality of write signals is received;
wherein said plurality of addressable storage means have addresses arranged in linear numerical order, a currently-read storage means having adjacent storage means corresponding to a storage means last-read and to a storage means next-to-be-read, a second plurality of read select signals corresponding to said currently-read storage means, a first plurality of read select signals corresponding to said last-read storage means, and a third plurality of read select signals corresponding to said next-to-be-read storage means;
a plurality of addressable means connected to said read/write select means and each connected to a predetermined one of said plurality of addressable storage means for generating a bi-level flag signal (Fn) indicative of whether a read or a write was most recently performed on said storage means connected to said flag means;
and
means for generating said stable buffer overflow/underflow signal including a plurality of overflow/underflow logic means each receiving said flag (Fn) signal from a predetermined one of said flag means, a predetermined one of said plurality of first read signals and a predetermined one of said plurality of second read signals, and a predetermined one of said write signals for generating a write overflow signal when said flag Fn signal is at a first predetermined level and said write signal is received, and, for generating a read underflow signal when said flag F signal is at a second predetermined level and said second read select signal is received.

4 more elements

A method of detecting potential overflow/underflow in an elastic buffer receiving a first data stream at a first predetermined rate, converting said first data stream to a second data stream at a second predetermined rate, and providing said second stream, said elastic buffer including means for generating a plurality of first, a plurality of second and a plurality of third read select signals and a plurality of write select signals;

a plurality of addressable storage means connected to said read/write select means each for storing said received data when a predetermined one of said first plurality of read signals is received and for generating a signal indicative of said stored data when a predetermined one of said plurality of write signals is received;
wherein said plurality of addressable storage means have addresses arranged in linear numerical order, a currently-read storage means having adjacent storage means corresponding to a storage means last-read and to a storage means next-to-be-read, said second plurality of read select signals corresponding to said currentlyread storage means, said first plurality of read select signals corresponding to said last-read storage means, and said third plurality of read select signals corresponding to said next-to-be-read storage means;
a plurality of addressable means connected to said read/write select means and each connected to a predetermined one of said plurality of addressable storage means for generating a bi-level flag signal (Fn) indicative of whether a read or a write was most recently performed on said storage means connected to said flag means, comprising the steps of:
(a) generating a write overflow signal when said write select signal is received at one of said addressable storage means and said flag signal Fn is at a first predetermined level;
(b) generating a read underflow signal when said second read select signal is received at one of said addressable storage means and said flag signal Fn is at a second predetermined level;
and
(c) generating an overflow/underflow signal when said third read select signal is received at one of said addressable storage means and said predetermined one of said plurality of write select signals and said predetermined one of said plurality of said third read select signals is received.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 06/683,434Filed 18 Dec 1984
Granted: 8 Sep 1987
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 5/14
Means for monitoring the fill level; Means for resolving contention, i.e. conflicts between simultaneous enqueue and dequeue operations: for…
G06F 5/12
Having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access…
H04L 25/05
Details ; arrangements for supplying electrical power along data transmission lines: electric or magnetic storage of signals before transmitting…
G06F 2205/123
Indexing scheme relating to groups G06F5/12 - G06F5/14: contention resolution, i.e. resolving conflicts between simultaneous read and write operations