# US 2012/0254491 A1 · Priority arbitration control within interconnect circuitry

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

- Number: US 2012/0254491 A1
- Document ID: US20120254491A1
- Status: Published application
- Kind: A1
- Application number: 13/438,920
- Filed: 2012-04-04
- Published: 2012-10-04
- Earliest claimed: 2009-02-13
- Assignees: The Regents of the University of Michigan
- Inventors: Sudhir Kumar SATPATHY; David Theodor Blaauw; Dennis Michael Sylvester; Trevor N. Mudge
- Web page: https://patentgrep.com/patent/US20120254491A1

## CPC

- G11C 7/10: Input/output [I/O] data interface arrangements, e.g. I/O data control circuits, I/O data buffers
- G06F 13/4022: {using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence)}
- G11C 7/1012: {Data reordering during input/output, e.g. crossbars, layers of multiplexers, shifting or rotating}
- H03K 17/693: Switching arrangements with several input- or output-terminals, e.g. multiplexers, distributors (logic circuits H03K19/00; code converters H03M5/00, H03M7/00)
- G06F 2213/0038: System on Chip
- G11C: STATIC STORES (semiconductor memory devices H10B)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M)

## Abstract

Interconnect circuitry 2 has a plurality of data source circuits 8 connected to respective input paths 4 and a plurality of data destination circuits 10 connected to respective output paths 6. Connection cells 12 provide selective connections between input paths 4 and output paths 6. Arbitration circuitry 26 provides adaptive priority arbitration between overlapping requests received at different input paths. Priority bits 16 within a matrix of priority bit 46 for each output path 10 are used to represent the priority relationships between different input paths which compete for access to that output path 10. Update operations are applied on a per row or per column basis within the matrix to implement update schemes such as least recently granted, most recently granted, round robin, reversal, swap, selective least recently granted, selective most recently granted etc.

## Claims

### Claim 1

Interconnect circuitry for connecting a plurality of data source circuits and a plurality of data destination circuits, said interconnect circuitry comprising:
a plurality of input paths each configured to connect to a respective one of said plurality of data sources;
a plurality of output paths each configured to connect to a respective one of said plurality of data destinations and selectively to connect to one of said plurality of input paths; and
an arbitration circuit associated with one of said plurality of output paths and configured to arbitrate between overlapping connection requests to said one of said plurality of output paths received from said plurality of input paths; wherein
said arbitration circuit stores a matrix of priority bits having a plurality of rows of priority bits and a plurality of columns of priority bits, each intersecting pair of a given row of said plurality of rows of priority bits and a given column of said plurality of columns of priority bits representing priority information for a given input path as:
(i) which of said plurality of input paths have a lower priority than said given input path; and
(ii) which of said plurality of input paths have a higher priority than said given input path; and
said arbitration circuit is configured to perform a priority update upon said matrix by performing one or more update operations each acting upon one of:
(i) a selected row of said plurality of rows of priority bits; and
(ii) a selected column of said plurality of columns of priority bits.

### Claim 2 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said one or more update operations include one or more of:
setting all priority bits within said selected row to a first value;
setting all priority bits within said selected column to a first value;
setting all priority bits within said selected row to a second value;
setting all priority bits within said selected column second value;
overriding, for all priority bits within said selected row, any changes made by another update operation;
overriding, for all priority bits within said selected column, any changes made by another update operation;
swapping priority bits within said selected row with corresponding priority bits within another row of said plurality of rows of priority bits; and
swapping priority bits within said selected column with corresponding priority bits within another column of said plurality of columns of priority bits.

### Claim 3 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a least recently granted scheme when said given input path has most recently been granted access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that none of said input paths have a lower priority than said given input path; and
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that all of said input paths have a higher priority than said given input path.

### Claim 4 (depends on 3)

Interconnect circuitry as claimed in claim 3, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path; and
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
said update operations performed upon said given row and said given column are:
resetting all bits within said given row to indicate that none of said plurality of input paths have a lower priority than said given input path; and
setting all bits within said given column to indicate that all of said plurality of input paths have a higher priority than said given input path.

### Claim 5 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a most recently granted scheme when said given input path has most recently been granted access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that all of said input paths have a lower priority than said given input path; and
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that none of said input paths have a higher priority than said given input path.

### Claim 6 (depends on 5)

Interconnect circuitry as claimed in claim 5, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path; and
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
said update operations performed upon said given row and said given column are:
setting all bits within said given row to indicate that all of said plurality of input paths have a lower priority than said given input path; and
resetting all bits within said given column to indicate that none of said plurality of input paths have a higher priority than said given input path.

### Claim 7 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with an incremental round robin scheme when said given input path has a current highest priority for access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that none of said input paths have a lower priority than said given input path; and
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that all of said input paths have a higher priority than said given input path.

### Claim 8 (depends on 7)

Interconnect circuitry as claimed in claim 7, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path; and
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
said update operations performed upon said given row and said given column are:
resetting all bits within said given row to indicate that none of said plurality of input paths have a lower priority than said given input path; and
setting all bits within said given column to indicate that all of said plurality of input paths have a higher priority than said given input path.

### Claim 9 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with an decremental round robin scheme when said given input path has a current lowest priority for access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that all of said input paths have a lower priority than said given input path; and
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that none of said input paths have a higher priority than said given input path.

### Claim 10 (depends on 9)

Interconnect circuitry as claimed in claim 9, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path; and
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
said update operations performed upon said given row and said given column are:
setting all bits within said given row to indicate that all of said plurality of input paths have a lower priority than said given input path; and
resetting all bits within said given column to indicate that none of said plurality of input paths have a higher priority than said given input path.

### Claim 11 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a priority swap scheme when said given input path and another input path associated with another row of said plurality of rows of priority bits and another column of said plurality of columns of priority bits are to swap priorities by performing update operations upon said given row and said given column such that said that:
all priority bits within said given row swap with corresponding priority bits within said another row; and
all priority bits within said given column swap with corresponding priority bits within said another column.

### Claim 12 (depends on 11)

Interconnect circuitry as claimed in claim 11, wherein:
priority bits outside of intersections of said given row and said another row with said given column and said another column are swapped between rows maintaining column position and are swapped between columns maintaining row position; and
priority bits inside of intersections of said given row and said another row with said given column and said another column are swapped between rows and swapped between columns.

### Claim 13 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a reversing scheme by performing update operations that invert values of all said priority bits within said matrix of priority bits.

### Claim 14 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a selective least recently granted scheme when said given input path has most recently been granted access to said one of said plurality of output paths and a lowest priority input path has a lowest priority for gaining access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that none of said input paths have a lower priority than said given input path;
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that all of said input paths have a higher priority than said given input path; and
overriding all changes to priority bits for said lowest priority input path which indicate which of said plurality of input paths have a higher priority than said lowest priority input path.

### Claim 15 (depends on 14)

Interconnect circuitry as claimed in claim 14, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path;
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
(iii) a lowest priority column indicates none of said plurality of input paths have a lower priority that said lowest priority input path; and
said update operations performed upon said given row and said given column are:
resetting all bits within said given row to indicate that none of said plurality of input paths have a lower priority than said given input path;
setting all bits within said given column to indicate that all of said plurality of input paths have a higher priority than said given input path; and
overriding all changes to priority bits within said lowest priority column.

### Claim 16 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said priority update performs arbitration in accordance with a selective most recently granted scheme when said given input path has most recently been granted access to said one of said plurality of output paths and a highest priority input path has a highest priority for gaining access to said one of said plurality of output paths by performing update operations upon said given row and said given column such that said that:
all priority bits which indicate which of said plurality of input paths have a lower priority than said given input path are set to indicate that all of said input paths have a lower priority than said given input path;
all priority bits which indicate which of said plurality of input paths have a higher priority than said given input path are set to indicate that none of said input paths have a higher priority than said given input path; and
overriding all changes to priority bits for said highest priority input path which indicate which of said plurality of input paths have a higher priority than said lowest priority input path.

### Claim 17 (depends on 16)

Interconnect circuitry as claimed in claim 16, wherein:
(i) said given row indicates which of said plurality of input paths have a higher priority than said given input path;
(ii) said given column indicates which of said plurality of input paths have a lower priority than said given input path; and
(iii) a highest priority column indicates none of said plurality of input paths have a lower priority that said lowest priority input path; and
said update operations performed upon said given row and said given column are:
setting all bits within said given row to indicate that all of said plurality of input paths have a lower priority than said given input path;
resetting all bits within said given column to indicate that none of said plurality of input paths have a higher priority than said given input path; and
overriding all changes to priority bits within said highest priority column.

### Claim 18 (depends on 1)

Interconnect circuitry as claimed in claim 1, comprising a plurality of said arbitration circuits, each arbitration circuitry associated with a respective one of said plurality of output paths.

### Claim 19 (depends on 1)

Interconnect circuitry as claimed in claim 1, wherein said arbitration circuit is configured to select which priority update to perform from among a plurality of different priority update schemes.

### Claim 20 (depends on 19)

Interconnect circuitry as claimed in claim 19, wherein said arbitration circuit dynamically selects which priority update to perform in dependence upon a current processing state of said plurality of data source circuits and said plurality of data destination circuits.

### Claim 21

Interconnect circuitry for connecting a plurality of data source circuits and a plurality of data destination circuits, said interconnect circuitry comprising:
a plurality of input paths each configured to connect to a respective one of said plurality of data sources;
a plurality of output paths each configured to connect to a respective one of said plurality of data destinations and selectively to connect to one of said plurality of input paths; and
arbitration means, associated with one of said plurality of output paths, for arbitrating between overlapping connection requests to said one of said plurality of output paths received from said plurality of input paths; wherein
said arbitration means stores a matrix of priority bits having a plurality of rows of priority bits and a plurality of columns of priority bits, each intersecting pair of a given row of said plurality of rows of priority bits and a given column of said plurality of columns of priority bits representing priority information for a given input path as:
(i) which of said plurality of input paths have a lower priority than said given input path; and
(ii) which of said plurality of input paths have a higher priority than said given input path; and
said arbitration means is configured to perform a priority update upon said matrix by performing one or more update operations each acting upon one of:
(i) a selected row of said plurality of rows of priority bits; and
(ii) a selected column of said plurality of columns of priority bits.

### Claim 22

A method of connecting a plurality of data source circuits and a plurality of data destination circuits using interconnect circuitry, said method comprising the steps of:
connecting a plurality of input paths to a respective one of said plurality of data sources;
connecting a plurality of output paths to a respective one of said plurality of data destinations;
selectively connecting one of said plurality of output paths to one of said plurality of input paths; and
arbitrating between overlapping connection requests to said one of said plurality of output paths received from said plurality of input paths; wherein said arbitrating includes:
storing a matrix of priority bits having a plurality of rows of priority bits and a plurality of columns of priority bits, each intersecting pair of a given row of said plurality of rows of priority bits and a given column of said plurality of columns of priority bits representing priority information for a given input path as:
(i) which of said plurality of input paths have a lower priority than said given input path; and
(ii) which of said plurality of input paths have a higher priority than said given input path; and
performing a priority update upon said matrix by performing one or more update operations each acting upon one of:
(i) a selected row of said plurality of rows of priority bits; and
(ii) a selected column of said plurality of columns of priority bits.
