Short and long term fair shuffling for crossbar switch arbiter
AssigneePMC-Sierra, Inc.
InventorCostas Calamvokis
Life of this patent
Estimating the term…
Abstract
A method and system including a short and long term fair shuffling procedure in an arbitration algorithm for a crossbar switch. The shuffling algorithm is deterministic, rather than random, in nature. The shuffling sequence is chosen to ensure a high level of short-term fairness. To ensure long-term fairness, all permutations are eventually used. Both row (input) and column (output) shufflers are used to shuffle priorities of requests. In a preferred embodiment, permuters and shifters are utilized in the shuffler circuits.
Claims4
A method for allocating paths disposed between sources and destinations and through a crossbar switch, the method comprising:
- shuffling of an assignment of the destinations across a first dimension of the crossbar switch;
- shuffling of an assignment of the sources across a second dimension of the crossbar switch;
- and
- performing a wrapped wave front arbitration across the crossbar switch to allocate the paths through the crossbar switch,
- wherein said shuffling achieves both short and long term fairness in allocation,
- wherein said shuffling a comprises deterministic shuffling, and wherein said shuffling of the assignment of the destinations comprises permutation of the assignment of the destinations across the first dimension.
Dependencies are inferred from the claim text.