# US 2008/0313621 A1 · Scalar code reduction using shortest path routing

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

- Number: US 2008/0313621 A1
- Document ID: US20080313621A1
- Status: Published application
- Kind: A1
- Application number: 11/763,990
- Filed: 2007-06-15
- Published: 2008-12-18
- Earliest claimed: 2007-06-15
- Assignees: Cray Inc.
- Inventors: James C. Beyer
- Web page: https://patentgrep.com/patent/US20080313621A1

## CPC

- G06F 8/4441: {Reducing the execution time required by the program code}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

This document discusses, among other things, a system and method computing the shortest path expression in a loop having a plurality of expressions. Candidate expressions in the loop are identified and partitioned into sets. A cost matrix is computed as a function of the sets. Paths are found through the cost matrix and, if there are cycles in the paths, the cycles are broken. One or more shortest path expressions are generated as a function of the paths and one or more of the expressions in the loop are replaced with the shortest path expressions.

## Claims

### Claim 1

In a compiler, a method of computing the shortest path expression in a loop having a plurality of expressions, comprising:
identifying candidate expressions from the plurality of loop expressions;
partitioning candidate expressions into sets, including a first set;
computing a cost matrix as a function of the sets;
finding one or more paths through the cost matrix;
detecting cycles in the paths;
if there are cycles in the paths, breaking the cycles;
generating one or more shortest path expressions as a function of the paths; and
replacing one or more of the expressions in the loop with the shortest path expressions.

### Claim 2 (depends on 1)

The method of claim 1, wherein the sets involve a particular induction variable, object base and offset.

### Claim 3 (depends on 1)

The method of claim 1, wherein computing a cost matrix includes subtracting each of the expressions within the first set from all of the other expressions in the first set.

### Claim 4 (depends on 3)

The method of claim 3, wherein finding one or more paths includes selecting paths through the cost matrix which produce the lowest cost for each expression.

### Claim 5 (depends on 1)

The method of claim 1, wherein finding one or more paths includes selecting paths through the cost matrix which produce the lowest cost for each expression.

### Claim 6 (depends on 1)

A computer-readable medium comprising instructions which, when executed on a computer, execute the method of claim 1.

### Claim 7

A computer, comprising:
a processor;
a data source; and
a compiler executing within the computer, wherein the compiler reads source code from the data source, wherein the source code includes a loop having a plurality of expressions, wherein the compiler identifies candidate expressions from the plurality of loop expressions, partitions candidate expressions into sets, computes a cost matrix as a function of the sets, finds paths through the cost matrix, detects cycles in the paths, breaks any cycles, generates one or more shortest path expressions as a function of the paths, and replaces one or more of the expressions in the loop with the shortest path expressions.

### Claim 8 (depends on 7)

The method of claim 7, wherein the sets involve a particular induction variable, object base and offset.

### Claim 9 (depends on 7)

The method of claim 7, wherein the sets include a first set and wherein the compiler computes a cost matrix by subtracting each of the expressions within the first set from all of the other expressions in the first set.

### Claim 10 (depends on 7)

The method of claim 7, wherein the compiler selects paths through the cost matrix which produce the lowest cost for each expression.
