# US 8,789,031 B2 · Software constructed strands for execution on a multi-core architecture

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

- Number: US 8,789,031 B2
- Document ID: US8789031B2
- Status: Granted
- Kind: B2
- Application number: 11/901,644
- Filed: 2007-09-18
- Published: 2009-03-19
- Granted: 2014-07-22
- Earliest claimed: 2007-09-18
- Assignees: Intel Corporation
- Applicants: Wei Liu; Lixin Su; Youfeng Wu; Herbert Hum
- Inventors: Wei Liu; Lixin Su; Youfeng Wu; Herbert Hum
- Web page: https://patentgrep.com/patent/US8789031B2

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

In one embodiment, the present invention includes a software-controlled method of forming instruction strands. The software may include instructions to obtain code of a superblock including a plurality of basic blocks, build a dependency directed acyclic graph (DAG) for the code, sort nodes coupled by edges of the dependency DAG into a topological order, form strands from the nodes based on hardware constraints, rule constraints, and scheduling constraints, and generate executable code for the strands and store the executable code in a storage. Other embodiments are described and claimed.

## Claims

### Claim 1

At least one non-transitory storage medium having instructions stored thereon for causing a system to:
obtain code of a superblock;
build a directed acyclic graph (DAG);
sort a plurality of nodes of the DAG into a topological order;
form a plurality of strands from the plurality of nodes based on at least one of hardware constraints, rule constraints, and scheduling constraints, each of the strands including at least one node and the hardware constraints corresponding to micro-architectural features of a many-core processor;
identify from the plurality of strands a potential strand, wherein the potential strand violates one of the rule constraints, and then duplicating at least one of the nodes;
after the duplicating, form a first strand that includes the potential strand and a second strand that includes at least one of the duplicated nodes but not the potential strand; and
generate executable code for the first and second strands and store the executable code in a storage.

### Claim 2 (depends on 1)

The at least one medium of claim 1, comprising instructions to generate the executable code using a compiler or dynamic optimizer.

### Claim 3 (depends on 1)

The at least one medium of claim 1 comprising instructions to optimize at least some of the plurality of strands, which comprises converting branches within the at least some strands into assertions and inserting a non-strand version of recovery code if a misspeculation occurs.

### Claim 4 (depends on 1)

The at least one medium of claim 1, wherein the instructions to generate the executable code include instructions to insert a strand instruction having a plurality of arguments into an instruction stream, each of the plurality of arguments to identify a strand length of one or more instructions following the strand instruction, wherein a sum of the plurality of arguments is related to the number of the one or more following instructions.

### Claim 5 (depends on 1)

The at least one medium of claim 1, comprising instructions to execute the plurality of strands on the many-core processor.

### Claim 6

An article comprising a non-transitory machine-accessible medium including instructions that when executed cause a system to:
obtain code of a superblock including a plurality of basic blocks in a compiler;
build a dependency directed acyclic graph (DAG) for the code;
sort a plurality of nodes coupled by edges of the dependency DAG into a topological order, each node representing an instruction and each edge representing a dependency between instructions;
form a plurality of strands from the plurality of nodes based on at least one of hardware constraints of a multi-core processor of the system, rule constraints, and scheduling constraints, each of the strands including at least one node;
identify from the plurality of strands a potential strand, wherein the potential strand violates one of the rule constraints, and duplicate at least one of the nodes after identifying the potential strand;
form a first strand from the potential strand and form a second strand including at least one of the duplicated nodes but not the potential strand;
optimize at least some of the plurality of strands by conversion of branches within the at least some strands into assertions and insert a non-strand version of recovery code if a misspeculation occurs; and
generate executable code for each of the first and second strands and store the executable code in a storage of the system.

### Claim 7 (depends on 1)

The at least one medium of claim 1, wherein each of the first and second strands have duplicated nodes.

### Claim 8 (depends on 1)

The at least one medium of claim 1, comprising instructions to execute the first and second strands on the many-core processor.

### Claim 9 (depends on 6)

The article of claim 6, further comprising instructions that when executed cause the system to execute the first and second strands on a many-core processor.