Queue circuit and method for memory arbitration employing same
AssigneeSilicon Graphics, Inc.
InventorWilliam A. Huffman
Life of this patent
Estimating the term…
Abstract
A memory access arbitration scheme is provided where transactions to a shared memory are stored in an arbitration queue. A collapsible queuing structure and method are provided, such that once a transaction is serviced, higher order entries ripple down in the queue to make room for new entries while maintaining an oldest to newest relationship among the queue entries. A queuing circuit having a plurality of registers interconnected by 2:1 multiplexers is also provided. The circuit is arranged such that each register receives either its own current contents or the contents of a higher order register during each register write cycle.
Claims15
A method of managing an arbitration queue having a plurality of queue entries comprising:
- introducing entries into the queue at a first, highest order queue location;
- determining if lower order queue locations are available;
- if lower order queue locations are available, moving all higher order queue location contents to an adjacent lower order queue location per cycle until all lower order locations are filled;
- evaluating each entry with respect to a cache to determine whether a hit, miss, or victim cache state is applied to each entry;
- storing an appropriate cache state in each entry;
- associating each entry after placement in the queue to one of a plurality of groups, each of the plurality of groups having a different transaction parameter criteria;
- determining which particular one of the plurality of groups to service based on the transaction parameter criteria;
- servicing a particular entry in the particular one of the plurality of groups based on servicing criteria and its associated cache state;
- and
- moving all higher order queue entries, with respect to the particular entry being serviced, to an adjacent lower order location in the queue.
A computer system comprising:
- a distributed shared memory system;
- a plurality of processors generating transactions to said distributed shared memory system;
- and
- a memory interface interposed between said distributed shared memory system and said plurality of processors, said memory interface having cache memory, a collapsible arbitration queue having a plurality of entry locations, and a memory arbitration processor for servicing transactions from said plurality of processors, the memory arbitration processor performing a memory arbitration scheme comprising:
- placing transactions as entries in the arbitration queue;
- evaluating each entry with respect to a cache to determine whether a hit, miss, or victim cache state is applied to each entry;
- storing an appropriate cache state in each entry;
- associating entries after placement in the arbitration queue to one of a plurality of groups, each of the plurality of groups having a different transaction parameter criteria;
- determining which particular one of the plurality of groups to service based on the transaction parameter criteria;
- servicing a particular entry of the particular one of the plurality of groups based on its associated cache state;
- marking a location of the particular entry in the arbitration queue as idle;
- and
- collapsing the arbitration queue by bringing all higher order entries into adjacent lower order locations in the queue to fill the idle location.
Dependencies are inferred from the claim text.