Method and apparatus for a high efficiency two-stage rotating priority arbiter with predictable arbitration latency

A method comprising:

• performing a first stage arbitration of a plurality of target requests issued by a plurality of masters in a cluster, each target request corresponding to a command a master wishes to send to one of a plurality of targets, each target comprising a shared resource that is operatively coupled to the cluster via a command bus interconnect, the first stage arbitration being performed by a cluster arbiter that produces a cluster winning target request through use of a rotating priority arbitration scheme under which targets are cyclically reprioritized in a predefined order;
• concurrently performing the foregoing first stage arbitration operation for target requests issued by masters in a plurality of respective clusters to produce a plurality of cluster winning target requests produced by respective first stage arbiters;
• performing a second stage arbitration of the plurality of cluster winning target requests via a target arbiter to produce a target request winner;
• generating a target grant identifying a winning target request and passing the target grant back to the master from which the corresponding target request originated;
• and
• arbitrating the command bus interconnect to transfer a command from the master from which the target request originated to the target identified in the target request,
• wherein the predefined order used to prioritize targets for a given cluster arbiter is offset from the predefined order used for each other cluster arbiter for a given cycle.

A network device, comprising:

• a network processor including,
• a plurality of microengines, configured in a plurality of clusters;
• a plurality of targets, each target comprising a sharable resource that is accessible to the plurality of microengines, the targets including a media switch fabric interface and a Peripheral Component Interconnect (PCI) Express interface;
• a chassis command bus interconnect, comprising a plurality of sets of bus lines connected between the plurality of clusters and the plurality of targets, the sets of bus lines forming a cross-bar interconnects including a plurality of target multiplexers coupled to respective targets;
• and
• a two-stage arbiter, operatively coupled to the targets, target multiplexers, and clusters, to arbitrate access to the command bus to facilitate transfer of target requests issued from the plurality of masters to the plurality of targets via the chassis command bus interconnect, the two-stage arbiter including a first stage comprising a cluster arbiter employing a rotating priority arbitration scheme under which target requests are prioritized on a rotating basis and the prioritization order of for each cluster arbiter is offset from the prioritization order of the other cluster arbiters for a given cycle;
• a media switch fabric, including cross-over connections between a plurality of input/output (I/O) ports via which packets are received at and forwarded from, coupled to the media switch fabric interface;
• and
• a PCI Express-compliant device, coupled to the PCI Express interface.