Overflow/Underflow detection for elastic buffer

• US 4,692,894 A
• Filed: 12/18/1984
• Issued: 09/08/1987
• Est. Priority Date: 12/18/1984
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Bemis, Gerald L.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Lacasse, Randy W.
• Application Number:
  US06/683,434
• Time in Patent Office: 994 Days
• Field of Search: 364/200, 364/900, 370/84
• US Class Current: 710/57
• CPC Class Codes: G06F 2205/123 Contention resolution, i.e. resolving conflicts between simultaneous read and write operations
• CPC Class Codes: G06F 5/12 Means for monitoring the fill level; Means for resolving contention, i.e. conflicts between simultaneous enqueue and dequeue operations
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: H04L 25/05 Electric or magnetic storage of signals before transmitting or retransmitting for changing the transmission rate

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.

Claims

1. 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.

2. An elastic buffer according to claim 1 wherein each of said plurality of flag means further receives a signal at a reset terminal and responsive thereto generates said flag signal (Fn) at said second predetermined level, said read/write select means further generates said plurality of third read select signals each conducted to a predetermined one of said flag means reset terminal, and each said overflow/underflow logic means further generates an overflow/underflow signal when said predetermined one of said plurality of write select signals is received and said predetermined one of said plurality of third read select signal is received.

3. An elastic buffer according to claim 2 wherein each said flag means comprises a flip-flop having a set terminal receiving said predetermined write select signal, having a reset terminal comprising said flag means reset terminal, and output terminal generating said flag (Fn) signal and a data terminal connected to said output terminal, and wherein each said overflow/underflow logic means comprises:

a first AND gate receiving at a first input said predetermined one of said write select signals and at a second input said flag (Fn) signal generated by said flip-flop, and generating therefrom a true signal;

a second AND gate receiving at a first input the complement of said flag (Fn) signal generated by said flip-flop and a second input said predetermined one of said second read select signals, and generating therefrom a true signal; and

an OR gate receiving at a first input said signal generated by said first AND gate and at a second input said signal generated by said second AND gate, and generating therefrom said signals generated by said overflow/logic means.

4. An elastic buffer according to claim 1 or claim 2 further including overflow/underflow control means receiving said signals generated by said plurality of overflow/underflow logic means, receiving a clock signal having a period extended with respect to that of said source clock signal, and said stored data signals generated by said plurality of addressable storage means for generating said stable buffer overflow/underflow signal, said overflow/underflow control means comprising:

means receiving said signals generated by said plurality of overflow/underflow logic means for generating therefrom a buffer overflow/underflow signal if at least one of said received signals indicates a write overflow, read underflow or overflow/underflow condition;

a first OR gate having a plurality of first inputs and second inputs receiving at a predetermined one of said first inputs a predetermined one of said stored data signals, at a predetermined one of said second inputs the complement of said predetermined stored data signal and generating therefrom true and complemented signals;

a first AND gate receiving at a first input the complement of said true signal generated by said first OR gate, at a second input the complement of said complemented signal generated by said first OR gate and at a third input said buffer overflow/underflow signal and generating therefrom a true signal; and

means receiving said extended clock signal and said signal generated by said AND gate, generating therefrom said stable buffer overflow/underflow signal.

5. An elastic buffer according to claim 4 wherein said stable buffer overflow/underflow signal generating means comprises:

a second OR gate receiving at a first input said signal generated by said first AND gate and having a second input, and generating therefrom a true signal;

a second AND gate receiving at a first input said signal generated by said second OR gate and having a second input, and generating therefrom a true signal;

said signal conducted to said second input of said second OR gate;

a first D-type flip-flop receiving at a data (D) input said signal generated by said second AND gate, receiving at a clock input said extended clock signal, and generating therefrom at a true (Q) output a signal indicative of the applied data signal at the most-recently received clock; and

a second D-type flip-flop receiving at a data (D) input said signal generated by said first flip-flop, receiving at a clock input said extended clock signal, and generating therefrom at a true (Q) output a signal indicative of the applied data signal at the most-recently received clock, and at a complemented (˜

Q) output a signal the complement of said signal generated at a said true output, said complemented signal conducted to said second input of said second AND gate;

wherein said stable buffer overflow/underflow signal is generated at said true output of said second flip-flop.

6. An elastic buffer according to claim 1 wherein said plurality of storage means have addreses arranged in a linear numerical order, a currently-read storage means having an adjacent storage means corresponding to a storage means last-read, said second plurality of read select signals corresponding to said currently-read storage means and said first plurality of read select signals corresponding to said last-read storage means.

7. 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.

8. An overflow/underflow detection method according to claim 7 further including the steps:

(d) generating an elastic buffer idle signal when all said signals indicative of said stored data of said plurality of storage means are at a first predetermined level;

(e) generating an elastic buffer quiet signal when said signals indicative of said stored data of said plurality of storage means are at a second predetermined level;

(f) generating a buffer overflow/underflow signal when at least one of said signals is generated at step (a), step (b) or step (c) for any of said plurality of storage means; and

(g) generating a stable buffer overflow/underflow signal when said elastic buffer idle signal and said elastic buffer quiet signal are not generated and said buffer overflow/underflow signal is generated.

9. An overflow/underflow detection method according to claim 28 wherein said elastic buffer has a source of timing clock signals having a predetermined period and wherein step (g) comprises the steps:

(g1) generating a signal when said elastic buffer idle signal and said elastic buffer quiet signal are not generated and said buffer overflow/underflow signal is generated;

(g2) holding said signal generated at step (g1) for a period greater than said timing clock signal; and

(g3) generating said stable buffer overflow/underflow signal generated at step (g1).