# US 2004/0210696 A1 · Method and apparatus for round robin resource arbitration

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0210696 A1
- Document ID: US20040210696A1
- Status: Published application
- Kind: A1
- Application number: 10/418,624
- Filed: 2003-04-18
- Published: 2004-10-21
- Earliest claimed: 2003-04-18
- Inventors: Michael J. Meyer; Drew Wingard; Wolf-Dietrich Weber
- Web page: https://patentgrep.com/patent/US20040210696A1

## CPC

- G06F 13/37: using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method and apparatus for a round robin resource arbitration scheme is described. An apparatus to provide round robin token arbitration comprises at least two token arbiters, each token arbiter associated with a node to which at least two sub-trees are connected, each sub-tree comprising a token arbiter or a finite state machine requestor.

## Claims

### Claim 1

An apparatus to provide round robin token arbitration comprising:
at least two token arbiters, each token arbiter associated with a node to which at least two sub-trees are connected, each sub-tree comprising a token arbiter or a requestor.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein each token arbiter has three connectors designed to receive sub-trees.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein each arbiter has one local connection designed to receive a requester.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein each arbiter includes a local connection, a right connection, and a left connection.

### Claim 5 (depends on 4)

The apparatus of claim 4, wherein request priority is: local, right, and left.

### Claim 6 (depends on 1)

The apparatus of claim 1, wherein each arbiter includes:
outputs of Grant signals to each connector designed to receive a sub-tree;
an input of a pair of signals, Generate (G) and Propagate (P), from each of the sub-trees, indicating a current state of the sub-tree.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein each non-root arbiter further includes:
an input of a root grant signal indicating that a token has been granted to the arbiter; and
an output upstream of a pair of signals, G and P, indicating a current state of the arbiter.

### Claim 8 (depends on 6)

The apparatus of claim 6, wherein the states indicated by the pair of signals comprise:
NoToken state indicating that the sub-tree does not have a token and does not want the token;
WantToken state indicating that the sub-tree wants the token; and
GenToken state indicating that the sub-tree has the token.

### Claim 9 (depends on 1)

The apparatus of claim 1, wherein a requestor has a finite state machine requestor with three states:
NoToken state indicating that the finite state machine requestor does not have a token and does not want the token;
WantToken state indicating that the finite state machine requestor wants the token; and
GenToken state indicating that the finite state machine requester has the token.

### Claim 10 (depends on 9)

The apparatus of claim 9, wherein the finite state machine requestor has an additional state of:
Preempted state indicating that the finite state machine requestor has the token, but that the round robin arbitration has been preempted by a higher priority arbitration.

### Claim 11 (depends on 1)

The apparatus of claim 1, wherein the arbiters and requesters are laid out in a tree structure.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein the tree structure is structured to minimize a maximum distance from the root to a furthest leaf node.

### Claim 13 (depends on 1)

A machine-readable medium having stored thereon information representing the apparatus of claim 1.

### Claim 14

An arbiter for a system-on-a-chip (SOC) comprising:
a root token arbiter having at least two downstream connectors to receive sub-trees;
a token arbiter coupled to one of the connectors of the root token arbiter, the token arbiter having at least two downstream connectors to receive sub-trees;
wherein each sub-tree comprises a token arbiter or a requestor.

### Claim 15 (depends on 14)

The arbiter of claim 14, wherein each downstream connector includes the signals:
output signal Grant indicating that the sub-tree coupled to the connector has been granted the token;
a pair of input signals Generate (G) and Propagate (P) indicating a status of the sub-tree coupled to the token.

### Claim 16 (depends on 15)

The arbiter of claim 15, wherein each token arbiter further comprises an upstream connector.

### Claim 17 (depends on 16)

The arbiter of claim 16, wherein the upstream connector comprises:
a pair of output signals Generate (G) and Propagate (P) indicating the status of the token arbiter upstream; and
an input signal RootGrant indicating that the token arbiter has been granted the token.

### Claim 18 (depends on 14)

The arbiter of claim 14, wherein buffered signals are output to the sub-trees coupled to the token arbiter.

### Claim 19 (depends on 18)

The arbiter of claim 18, wherein the buffered signals are buffered using a high-powered buffers or inverters that drive the output of the token arbiter.

### Claim 20

An arbiter comprising:
a first token arbiter to receive a local requester and at least a second token arbiter;
a second token arbiter coupled to the first token arbiter, the second token arbiter to receive at least two requesters.

### Claim 21 (depends on 20)

The arbiter of claim 20, wherein one of the at least two requesters is a local requestor.

### Claim 22 (depends on 20)

The arbiter of claim 20, wherein one of the at least two requestors is a remote requestor.

### Claim 23 (depends on 22)

The arbiter of claim 22, wherein the remote requestor is coupled to the second token arbiter through a third token arbiter.

### Claim 24

A system-on-a-chip (SOC) comprising:
a plurality of logical units;
a shared resource accessed by the plurality of logical units;
an arbitration logic to arbitration the shared resource, the arbitration logic comprising:
a finite state machine associated with each of the plurality of logical units, to generate requests for the shared resource and indicate to the logical unit when the shared resource is available for use;
the finite state machines tied together in a tree structure using token arbiters, each token arbiter having associated with it at least two sub-trees, a sub-tree comprising the finite state machine or another token arbiter.

### Claim 25 (depends on 24)

A machine-readable medium having stored thereon information representing the apparatus of claim 24.

### Claim 26

A tree-structured arbiter comprising:
a plurality of finite state machines comprising leaf nodes of the tree-structured arbiter, each finite state machine associated with a requestor, the finite state machine passing a state upstream with a two-wire connection;
a plurality of token arbiters comprising a root node and branch nodes, a token arbiter to receive a two-wire connection from a finite state machine, the token arbiter to determine when to grant the token to the finite state machine.

### Claim 27 (depends on 26)

The arbiter of claim 26, wherein a token arbiter has a finite state machine coupled to the token arbiter.

### Claim 28 (depends on 26)

The arbiter of claim 26, wherein a token arbiter has a daughter token arbiter coupled to it, the daughter token arbiter passing a two-wire connection to the token arbiter indicating a state of a sub-tree of the daughter arbiter.
