Fast priority determination circuit with rotating priority

Abstract

The invention describes a system for and a method of creating and using dependencies to determine the order of servicing transaction requests in a multiple queue environment. When more than one outstanding transaction affects the same memory location, dependencies are established to ensure the correct sequencing of the competing transactions. In a preferred embodiment the dependency is configured to ensure that, as each request is inserted, other outstanding requests are checked to determine if the same memory location is accessed. If the same memory location is affected, a dependency is created which ensures the youngest queue entry which is present at the time the check is made occurs before the present outstanding request.

1. A method of providing ordered access to a memory, comprising the steps of:
 comparing an address of an incoming transaction with the address of each pending transaction to create an original match vector indicating sequencing requirements between said incoming transaction and said pending transactions, said original match vector including a bit corresponding to a result of each comparison;  
 forming an image of said original match vector and concatenating said image of said original match vector with said original match vector to form an extended match vector;  
 receiving a value which indicates the relative age of said pending transaction;  
 generating a counter mask from said value;  
 generating masked match bits with a logic operation on said extended match vector and said counter mask;  
 identifying one of said masked match bits based on a predetermined criteria;  
 setting remaining ones of said match bits to a first predetermined logic value to provide an applied mask; and  
 logically combining a first segment of said applied mask with a second segment of said applied mask to identify at most one of said pending transactions required to be completed prior to allowing said incoming transaction to be processed.  
 
     
     
       2. The method of  claim 1  wherein said address of said pending transaction and said address of said incoming transaction comprise portions of respective memory addresses. 
     
     
       3. The method of  claim 1  wherein said image is a duplicate of said original match vector. 
     
     
       4. The method of  claim 1  wherein the value is a counter value indicating a position of a rotating queue. 
     
     
       5. The method of  claim 1  wherein said counter mask is generated using a look-up structure. 
     
     
       6. The method of  claim 1  wherein said counter mask is generated using decoding logic. 
     
     
       7. The method of  claim 1  wherein said logic operation is a logic AND operation. 
     
     
       8. The method of  claim 1  wherein said predetermined criteria includes scanning said masked match bits in a predetermined direction to identify a first occurrence of a first bit having a second predetermined logic value opposite said first predetermined logic value. 
     
     
       9. The method of  claim 1  wherein said memory is one of a register file, a cache, a main memory, a tape drive, or a disk storage. 
     
     
       10. A memory-access ordering apparatus comprising:
 a comparator which compares an address of an incoming transaction with the address of each pending transaction and creates an original match vector indicating sequencing requirements between said incoming transaction and said pending transactions, said original match vector including a bit corresponding to a result of each comparison;  
 an extended match vector formed by concatenating an image of said original match vector with said original match vector;  
 a value which indicates the relative age of said pending transaction;  
 a counter mask generated from said value;  
 masked match bits generated with a logic operation on said extended match vector and said counter mask;  
 a predetermined criteria used to identify one of said masked match bits;  
 an applied mask formed by setting remaining ones of said match bits to a first predetermined logic value; and  
 an identification of at most one of said pending transactions required to be completed prior to allowing said incoming transaction to be processed identified by logically combining a first segment of said applied mask with a second segment of said applied mask.  
 
     
     
       11. The apparatus of  claim 10  wherein said address of said pending transaction and said address of said incoming transaction comprise portions of respective memory addresses. 
     
     
       12. The apparatus of  claim 10  wherein said image is a duplicate of said original match vector. 
     
     
       13. The apparatus of  claim 10  wherein the value is a counter value indicating a position of a rotating queue. 
     
     
       14. The apparatus of  claim 10  wherein said counter mask is generated using a look-up structure. 
     
     
       15. The apparatus of  claim 10  wherein said counter mask is generate using decoding logic. 
     
     
       16. The apparatus of  claim 10  wherein said logic operation is a logic AND operation. 
     
     
       17. The apparatus of  claim 10  wherein said predetermined criteria includes scanning said masked match bits in a predetermined direction to identify a first occurrence of a first bit having a second predetermined logic value opposite said first predetermined logic value. 
     
     
       18. The apparatus of  claim 10  wherein said memory is one of a register file, a cache, a main memory, a tape drive, or a disk storage.