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.
