High-speed starvation-free arbiter system, rotating-priority arbiter, and two-stage arbitration method

Abstract

A two-stage arbiter system comprises a first-stage arbiter to grant a request to one of a plurality of requesters in accordance with a first arbitration scheme and a second-stage arbiter to grant one of the remaining requests in accordance with a second arbitration scheme. The first arbitration scheme may be a fast arbitration scheme such as a fixed-priority scheme, and the second arbitration scheme may be a rotating priority-based arbitration scheme or a least-recently-granted arbitration scheme. The first-stage arbiter may operate in a first pipelined stage, and the second-stage arbiter may operate in a second pipelined stage. Two-stage arbitration may help improve access of lower-priority requestors in a pipelined system. In one embodiment, a rotating-priority arbitrator includes a pseudo-random number generator to generate an amount for rotating priorities prior to arbitration. The rotating-priority arbiter may use either a counter or linear-feedback shift register to rotate priorities of requests.

1 . A rotating-priority arbiter comprising: 
 priority-shifting circuitry to shift priorities of requests in a non-uniform manner;    arbiter circuitry to receive the shifted requests and to grant one of the requests; and    priority-restoring circuitry to restore an association between the requests and the granted requests.    
   
   
       2 . The arbiter of  claim 1  further comprising: 
 a counter to generate a rotate amount, the priority-shifting to rotate the order of the requests in a first direction by the rotate amount, the priority-restoring circuitry to rotate the order of grants by the rotate amount in a direction opposite the first direction to restore the association between the requests and the grant; and    divide-by circuitry to divide a clock rate and provide an arbitration rate to the counter for use in generating the rotate amount.    
   
   
       3 . The arbiter of  claim 1  further comprising a pseudo-random number generator to generate a pseudo-random number for use by the priority-shifting circuitry in shifting the priorities.  
   
   
       4 . The arbiter of  claim 3  wherein the pseudo-random number generator is comprised of a linear-feedback shift register to generate the pseudo-random number, and 
 wherein the arbiter further comprises a serial-in, parallel-out shift register to receive serial bits from the pseudo-random number generator and to provide a parallel output to the priority-shifting circuitry.    
   
   
       5 . A method of performing rotating-priority arbitration comprising: 
 priority-shifting requests to shift priorities of requests in a non-uniform manner;    receiving the shifted requests;    granting one of the shifted requests; and    restoring an association between the requests and the grants.    
   
   
       6 . The method of  claim 5  wherein priority-shifting comprises rotating the order of the requests in a first direction, and 
 wherein restoring comprises rotating an order of grants by a rotate amount in a direction opposite the first direction to restore the association between the requests and the grants, and    wherein the method further comprises dividing a clock rate to provide an arbitration rate for use in generating the rotate amount.    
   
   
       7 . The method of  claim 5  further comprising generating a pseudo-random number for use in priority-shifting the requests.  
   
   
       8 . The method of  claim 7  wherein generating the pseudo-random number comprises using a linear-feedback shift register, and 
 wherein the method further comprise receiving serial bits from the linear-feedback shift register and providing a parallel output.