# US 8,572,353 B1 · Condensed router headers with low latency output port calculation

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

- Number: US 8,572,353 B1
- Document ID: US8572353B1
- Status: Granted
- Kind: B1
- Application number: 12/886,366
- Filed: 2010-09-20
- Granted: 2013-10-29
- Earliest claimed: 2009-09-21
- Assignees: Tilera Corporation
- Applicants: Ian Rudolf Bratt; Carl G. Ramey; Matthew Mattina
- Inventors: Ian Rudolf Bratt; Carl G. Ramey; Matthew Mattina
- Web page: https://patentgrep.com/patent/US8572353B1

## CPC

- G06F 9/4825: {Interrupt from clock, e.g. time of day}
- G06F 9/3004: {to perform operations on memory}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5022: {Mechanisms to release resources}
- G06F 9/544: {Buffers; Shared memory; Pipes}
- G06F 12/00: Accessing, addressing or allocating within memory systems or architectures (digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06)
- G06F 12/02: Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00)
- G06F 12/0806: Multiuser, multiprocessor or multiprocessing cache systems
- G06F 12/0815: Cache consistency protocols
- G06F 12/0844: Multiple simultaneous or quasi-simultaneous cache accessing
- G06F 12/0848: {Partitioned cache, e.g. separate instruction and operand caches}
- G06F 12/0855: Overlapped cache accessing, e.g. pipeline (G06F12/0846 takes precedence)
- G06F 12/0864: using pseudo-associative means, e.g. set-associative or hashing
- G06F 12/0888: using selective caching, e.g. bypass
- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 12/10: Address translation
- G06F 12/1027: using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
- G06F 12/12: Replacement control
- G06F 12/121: using replacement algorithms
- G06F 12/122: of the least frequently used [LFU] type, e.g. with individual count value
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
- G06F 13/4068: {Electrical coupling}
- G06F 13/4221: {being an input/output bus, e.g. ISA bus, EISA bus, PCI bus, SCSI bus}
- G06F 15/16: Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs {(coordinating program control therefor G06F9/52; in regulating and control system G05B)}
- G06F 15/8023: {Two dimensional arrays, e.g. mesh, torus}
- G06F 21/79: in semiconductor storage media, e.g. directly-addressable memories
- H04L 45/08: {Learning-based routing, e.g. using neural networks or artificial intelligence}
- H04L 45/28: using route fault recovery
- H04L 47/83: based on usage prediction
- H04L 49/109: Integrated on microchip, e.g. switch-on-chip
- G06F 11/1482: using middleware or operating system [OS] functionalities
- G06F 12/0808: with cache invalidating means (G06F12/0815 takes precedence)
- G06F 2212/452: Instruction code
- G06F 2212/502: using adaptive policy
- G06F 2212/601: Reconfiguration of cache memory
- G06F 2212/6032: Way prediction in set-associative cache
- G06F 2212/621: Coherency control relating to peripheral accessing, e.g. from DMA or I/O device
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Communicating among cores in a computing system comprising a plurality of cores, each core comprising a processor and a switch, includes: routing a packet from an origin core to a destination core over a route including multiple cores; and at each core in the route before the destination core, routing the packet to the next core in the route according to a respective symbol in a sequence of multiple symbols. The respective symbol has a first symbol value indicating a single likely direction and the respective symbol has a second symbol value indicating multiple less likely directions.

## Claims

### Claim 1

A method for communicating among cores in a multi-core processor device that comprises a plurality of cores, each core comprising a processor and a switch, the method comprising:
routing a packet that includes a header and payload from an origin core to a destination core over a route including multiple cores in the multi-core processor device; and
at each core in the route before the destination core, routing the packet to the next core in the route according to a value of a respective symbol in a sequence of multiple symbols in the header, with the respective symbol having a first symbol value indicating a single likely direction, and the respective symbol having a second, different symbol value indicating routing according to at least one of multiple less likely routing directions.

### Claim 2 (depends on 1)

The method of claim 1, further comprising, at a core in the route that routes the packet according to a respective symbol having the second symbol value, determining in which of the multiple less likely directions the packet is to be routed based on information in the packet.

### Claim 3 (depends on 2)

The method of claim 2, wherein the information in the packet comprises a sequence of direction fields each indicating one of the multiple less likely directions.

### Claim 4 (depends on 3)

The method of claim 3, wherein the sequence of direction fields includes a corresponding direction fields for each symbol in the sequence of symbols having the second symbol value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the plurality of cores are connected over a mesh network in which neighboring cores in the mesh network are connected by a communication link, and at least some of the cores include links in opposite directions that provide a route through the core in a straight direction through the core.

### Claim 6 (depends on 5)

The method of claim 5, wherein routing the packet received at a given core in the route from the previous core in the route to the next core in the route according to a respective symbol having the first symbol value comprises routing the packet in a straight direction through the given core.

### Claim 7 (depends on 5)

The method of claim 5, wherein at least some of the cores include four links in four directions that provide the route through the core in a straight direction through the core, a route through the core in right turn direction through the core, and a route through the core in a left turn direction through the core.

### Claim 8 (depends on 7)

The method of claim 7, wherein routing the packet received at a given core in the route from the previous core in the route to the next core in the route according to a respective symbol having the second symbol value comprises routing the packet in either a left turn or right turn direction through the given core based on information in the packet.

### Claim 9 (depends on 1)

The method of claim 1, wherein each symbol in the sequence of symbols is a Boolean symbol and the first symbol value is a first value of the Boolean symbol and the second symbol value is a second value of the Boolean symbol.

### Claim 10 (depends on 9)

The method of claim 9, wherein each symbol in the sequence of symbols is stored in a bit of a bit vector.

### Claim 11

A computer program product tangibly stored on a computer-readable hardware storage device, the computer program for communicating among cores in a multi-core processor device that comprises a plurality of cores, each core comprising a processor and a switch, the computer program including instructions for causing the computing system to:
route a packet that includes a header and payload from an origin core to a destination core over a route including multiple cores in the multi-core processor device; and
at each core in the route before the destination core, route the packet to the next core in the route according to a value of a respective symbol in a sequence of multiple symbols in the header, with the respective symbol having a first symbol value indicating a single likely direction and the respective symbol having a second, different symbol value indicating routing according to at least one of multiple less likely routing directions.

### Claim 12

A computing system, comprising:
a multi-core processor device that comprises a plurality of cores, with each of the cores comprising a switch and a processor, and with at least some of the processors configured to:
route a packet that includes a header and payload from an origin core to a destination core over a route including multiple cores in the multi-core processor device; and
at each core in the route before the destination core, route the packet to the next core in the route according to a value of a respective symbol in a sequence of multiple symbols in the header, with the respective symbol having a first symbol value indicating a single likely direction and the respective symbol having a second, different symbol value indicating routing according to at least one of multiple less likely routing directions.

### Claim 13 (depends on 11)

The computer program product of claim 11, further comprising instructions to:
determine in which of the multiple less likely directions the packet is to be routed based on information in the packet.

### Claim 14 (depends on 12)

The computer program product of claim 12, wherein the information in the packet comprises a sequence of direction fields each indicating one of the multiple less likely directions and the sequence of direction fields includes a corresponding direction fields for each symbol in the sequence of symbols having the second symbol value.

### Claim 15 (depends on 11)

The computer program product of claim 11, wherein at least some of the cores include four links in four directions, and execution of the instructions provide the route through the core in a straight direction through the core, a route through the core in right turn direction through the core, and a route through the core in a left turn direction through the core.

### Claim 16 (depends on 11)

The computer program product of claim 11, wherein each symbol in the sequence of symbols is a Boolean symbol and the first symbol value is a first value of the Boolean symbol and the second symbol value is a second value of the Boolean symbol.

### Claim 17 (depends on 15)

The computer program product of claim 15, wherein each symbol in the sequence of symbols is stored in a bit of a bit vector.

### Claim 18 (depends on 12)

The system of claim 12, further configured to, at a core in the route that routes the packet according to a respective symbol having the second symbol value, determine in which of the multiple less likely directions the packet is to be routed based on information in the packet.

### Claim 19 (depends on 18)

The system of claim 18, wherein the information in the packet comprises a sequence of direction fields each indicating one of the multiple less likely directions.

### Claim 20 (depends on 19)

The system of claim 19, wherein the sequence of direction fields includes a corresponding direction fields for each symbol in the sequence of symbols having the second symbol value.

### Claim 21 (depends on 12)

The system of claim 12, wherein the plurality of cores are connected over a mesh network in which neighboring cores in the mesh network are connected by a communication link, and at least some of the cores include links in opposite directions that provide a route through the core in a straight direction through the core.

### Claim 22 (depends on 21)

The system of claim 21, wherein routing the packet received at a given core in the route from the previous core in the route to the next core in the route according to a respective symbol having the first symbol value comprises routing the packet in a straight direction through the given core.

### Claim 23 (depends on 22)

The system of claim 22, wherein at least some of the cores include four links in four directions that provide the route through the core in a straight direction through the core, a route through the core in right turn direction through the core, and a route through the core in a left turn direction through the core.

### Claim 24 (depends on 23)

The system of claim 23, wherein routing the packet received at a given core in the route from the previous core in the route to the next core in the route according to a respective symbol having the second symbol value comprises routing the packet in either a left turn or right turn direction through the given core based on information in the packet.

### Claim 25 (depends on 12)

The system of claim 12, wherein each symbol in the sequence of symbols is a Boolean symbol and the first symbol value is a first value of the Boolean symbol and the second symbol value is a second value of the Boolean symbol.

### Claim 26 (depends on 25)

The system of claim 25, wherein each symbol in the sequence of symbols is stored in a bit of a bit vector.