Patent ID: 6892278

Claim:
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 each cell in the linear array operates asynchronously with respect to other non-neighboring cell in the linear array; wherein a given cell in the interior of the linear array is configured to asynchronously coordinate operations with only a preceding cell in the linear array and a subsequent cell in the linear array without relying on external controls and, more specifically, is configured to receive get and put calls from the preceding cell in the linear array, and to make get and put calls to the 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; and wherein inter-cell communications between the plurality of cells take place asynchronously without reference to a system clock signal.