Method and apparatus for efficiently implementing a last-in first-out buffer

• US 20030172231A1
• Filed: 03/05/2002
• Published: 09/11/2003
• Est. Priority Date: 03/05/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ebergen, Josephus C.
• Granted Patent: US 6,892,278 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 7/78 for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor

Abstract

One embodiment of the present invention provides a system that implements a last-in first-out buffer. The system includes a plurality of cells arranged in a linear array to form the last-in first-out buffer, wherein a given cell in the interior of the linear array is configured to receive get and put calls from a preceding cell in the linear array, and to make get and put calls to a subsequent cell in the linear array. If the given cell contains no data items, the given cell is configured to make a get call to retrieve a data item from the subsequent cell. In this way the data item becomes available in the given cell to immediately satisfy a subsequent get call to the given cell without having to wait for the data item to propagate to the given cell from subsequent cells in the linear array. If the given cell contains no space for additional data items, the given cell is configured to make a put call to transfer a data item to the subsequent cell. In this way, space becomes available in the given cell to immediately satisfy a subsequent put call to the given cell without having to wait for data in the given cell to propagate to subsequent cells in the linear array.

Claims

1. An apparatus that implements a last-in first-out buffer, comprising:

a plurality of cells arranged in a linear array to form the last-in first-out buffer;

wherein a given cell in the interior of the linear array is configured to receive get and put calls from a preceding cell in the linear array, and to make get and put calls to a subsequent cell in the linear array;

wherein if the given cell contains no data items, the given cell is configured to make a get call to retrieve a data item from the subsequent cell, whereby the data item becomes available in the given cell to immediately satisfy a subsequent get call to the given cell from the preceding cell without having to wait for the data item to propagate to the given cell from subsequent cells in the linear array; and

wherein if the given cell contains no space for additional data items, the given cell is configured to make a put call to transfer a data item to the subsequent cell, whereby space becomes available in the given cell to immediately satisfy a subsequent put call to the given cell from the preceding cell without having to wait for data in the given cell to propagate to subsequent cells in the linear array.

2. The apparatus of claim 1, wherein communications between the plurality of cells take place asynchronously without reference to a system clock signal.

3. The apparatus of claim 1, wherein the given cell includes:

a master location for storing a data item; and

a slave location for temporarily storing a new data item during a put operation to the given cell until a preexisting data item in the master location can be moved to the subsequent cell to make room for the new data item.

4. The apparatus of claim 1, wherein the given cell includes a first location and a second location for storing data items.

5. The apparatus of claim 1, wherein the given cell includes a first location, a second location and a third location for storing data items.

6. The apparatus of claim 1, wherein the given cell includes more than three locations for storing data items.

7. The apparatus of claim 1, wherein each cell in the linear array includes circuitry to determine if all subsequent cells in the linear array are completely full.

8. The apparatus of claim 1, wherein each cell in the linear array includes circuitry to determine if all subsequent cells in the linear array are empty.

9. An apparatus that implements a last-in first-out buffer, comprising:

a plurality of cells arranged in a linear array to form the last-in first-out buffer;

wherein a given cell in the interior of the linear array is configured to receive get and put calls from a preceding cell in the linear array, and to make get and put calls to a subsequent cell in the linear array;

wherein if the given cell contains no data items, the given cell is configured to make a get call to retrieve a data item from the subsequent cell, whereby the data item becomes available in the given cell to immediately satisfy a subsequent get call to the given cell from the preceding cell without having to wait for the data item to propagate to the given cell from subsequent cells in the linear array;

wherein if the given cell contains no space for additional data items, the given cell is configured to make a put call to transfer a data item to the subsequent cell, whereby space becomes available in the given cell to immediately satisfy a subsequent put call to the given cell from the preceding cell without having to wait for data in the given cell to propagate to subsequent cells in the linear array;

wherein communications between the plurality of cells take place asynchronously without reference to a system clock signal;

wherein each cell in the linear array includes circuitry to determine if all subsequent cells in the linear array are completely full; and

wherein each cell in the linear array includes circuitry to determine if all subsequent cells in the linear array are empty.

10. The apparatus of claim 9, wherein the given cell includes:

a master location for storing a data item; and

a slave location for temporarily storing a new data item during a put operation to the given cell until a preexisting data item in the master location can be moved to the subsequent cell to make room for the new data item.

11. The apparatus of claim 9, wherein the given cell includes a first location and a second location for storing data items.

12. The apparatus of claim 9, wherein the given cell includes a first location, a second location and a third location for storing data items.

13. The apparatus of claim 9, wherein the given cell includes more than three locations for storing data items.

14. A method for implementing a last-in first-out buffer, wherein the method operates within a plurality of cells arranged in a linear array to form the last-in first-out buffer, wherein a given cell in the interior of the linear array is configured to receive get and put calls from a preceding cell in the linear array, and to make get and put calls to a subsequent cell in the linear array, the method comprising:

making a get call from the given cell to retrieve a data item from the subsequent cell if the given cell contains no data items, whereby the data item becomes available in the given cell to immediately satisfy a subsequent get call to the given cell without having to wait for the data item to propagate to the given cell from subsequent cells in the linear array; and

making a put call from the given cell to transfer a data item to the subsequent cell if the given cell contains no space for additional data items, whereby space becomes available in the given cell to immediately satisfy a subsequent put call to the given cell without having to wait for data in the given cell to propagate to subsequent cells in the linear array.

15. The method of claim 14, wherein communications between the plurality of cells take place asynchronously without reference to a system clock signal.

16. The method of claim 14,

wherein the given cell includes a master location and a slave location for storing data items;

and

wherein during a put operation to the given cell involving a new data item, the new data item is temporarily stored in the slave location until a preexisting data item in the master location can be moved to the subsequent cell to make room for the new data item.

17. The method of claim 14, wherein the given cell includes a first location and a second location for storing data items.

18. The method of claim 14, wherein the given cell includes a first location, a second location and a third location for storing data items.

19. The method of claim 14, wherein the given cell includes more than three locations for storing data items.

20. The method of claim 14, further comprising monitoring signals from subsequent cells in the linear array to determine if the subsequent cells are completely full.

21. The method of claim 14, further comprising monitoring signals from subsequent cells in the linear array to determine if all the subsequent cells are empty.