Scalable round-robin arbiter tree for round-robin arbitration
AssigneeMicrosoft Technology Licensing, LLC
InventorsShu-Yi Yu, Nicolas Mellis
Life of this patent
Estimating the term…
Abstract
The methods and systems may provide a scalable round-robin arbiter tree that performs round-robin arbitration for a plurality of requests received from a set of requestors. The round-robin arbiter may stack a plurality of round-robin cells in stages where an output of a first stage of round-robin cells is an input to a next stage of round-robin cells. The round-robin arbiter may transform an arbitration state at each stage of the arbitration and propagate the arbitration state into the next stage for arbitration. The arbitration state from the final stage round-robin cell is fed back to the first stage of the round-robin cells and used in a subsequent arbitration round.
Claims17
A method for round-robin arbitration implemented by a round-robin arbiter, comprising:
- receiving, at the round-robin arbiter, an arbitration state and a first group of requests from a first set of requestors for the round-robin arbitration, wherein the arbitration state indicates one round-robin cell of the one or more round-robin cells with a high priority;
- determining a preliminary winning request of the first group of requests using one or more round-robin cells in a first stage of the round-robin arbiter;
- outputting an intermediate arbitration state based on the first stage of the round-robin arbiter;
- determining a winning request based on the preliminary winning request and the intermediate arbitration state using a single round-robin cell in a second stage of the round-robin arbiter;
- updating the arbitration state based on the winning request;
- and
- starting a new round of arbitration for the first group of requests from the first set of requestors based on the arbitration state using the one or more round-robin cells in the first stage of the round-robin arbiter.
A round-robin arbiter, comprising:
- a plurality of round-robin cells that receive a plurality of requests from a set of requestors for round-robin arbitration and identify a winning request of the plurality of requests based on the round-robin arbitration;
- a plurality of stages with a plurality of round-robin cells in communication with each other, wherein an output of a first stage of round-robin cells is an input to a next stage of round-robin cells;
- and
- a state component in communication with the plurality of round-robin cells that maintains an arbitration state for the round-robin arbiter, wherein the arbitration state is updated based on the winning request by shifting the arbitration state to a next round-robin cell of the plurality of round-robin cells and the arbitration state is propagated between the plurality of stages.
A round-robin cell for use with a round-robin arbiter, comprising:
- a plurality of flip flops;
- a plurality of muxes;
- a plurality of priority encoders;
- a plurality of logic gates;
- and
- a set of state flip flops,
- wherein the plurality of flip flops, the plurality of muxes, the plurality of priority encoders, the plurality of the logic gates, and the set of state flip flops are placed in an order in communication with each other and operable to:
- receive a plurality of requests and an arbitration state of the round-robin cell, wherein the arbitration state indicates that the round-robin cell starts an arbitration round for the plurality of requests;
- identify a winning request of the plurality of requests by determining whether the plurality of requests include at least one high priority request and outputting the at least one high priority request as the winning request;
- update the arbitration state of the round-robin cell;
- and
- propagate the arbitration state to a next stage in the arbitration round.
Dependencies are inferred from the claim text.