US 2014/0237195 A1 · N-DIMENSIONAL COLLAPSIBLE FIFO

Abstract

A system and method for efficient dynamic utilization of shared resources. A computing system includes a shared data structure accessed by multiple requestors. Both indications of access requests and indices pointing to entries within the data structure are stored in storage buffers. Each storage buffer maintains at a selected end an oldest stored indication of an access request from a respective requestor. Each storage buffer stores information for the respective requestor in an in-order contiguous manner beginning at the selected end. The indices stored in a given storage buffer are updated responsive to allocating new data or deallocating stored data in the shared data structure. Entries in a storage buffer are deallocated in any order and remaining entries are collapsed toward the selected end to eliminate gaps left by the deallocated entry.

Claims20

Dependent claims

An apparatus comprising:

a plurality of requestors configured to generate access requests for data;
a shared data structure comprising a first plurality of entries, each entry configured to store data for a respective one of the plurality of requestors;
a plurality of buffers, each comprising a respective second plurality of entries, wherein each buffer of the plurality of buffers is configured to:
store indications of access requests from a given requestor of the plurality of requestors in an in-order contiguous manner beginning at a first end;
store indices pointing to entries of the first plurality of entries in the shared data structure associated with the access requests from the given requestor;
and
maintain an oldest stored indication of an access request from the given requestor at the first end.

4 more elements

Dependencies are inferred from the claim text.

N-dimensional collapsible fifo

Life of this patent

N-dimensional collapsible fifo

Life of this patent

Abstract

Claims20