# US 2026/0236242 A1 · Optimization device and optimization method

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

- Number: US 2026/0236242 A1
- Document ID: US20260236242A1
- Status: Published application
- Kind: A1
- Application number: 19/441,977
- Filed: 2026-01-07
- Published: 2026-08-13
- Earliest claimed: 2025-02-10
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Toshiyuki ICHIBA
- Web page: https://patentgrep.com/patent/US20260236242A1

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 8/443: {Optimisation}
- G06F 8/4452: {Software pipelining}
- G06F 8/452: {Loops}
- G06F 8/456: {Parallelism detection}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An optimization device includes a processor configured to generate a first DFG corresponding to a first loop and a second DFG corresponding to a second loop for a program in which an incomplete nested loop in which a first arithmetic operation result for each loop of the first loop is sequentially used in an arithmetic operation for each loop of the second loop of a second layer included in the first loop of a first layer is present, and arrange a first data transfer node between an output portion of the first arithmetic operation result in the first DFG and an input portion of the first arithmetic operation result in the second DFG, connect the first DFG and the second DFG by the first data transfer node, and generate a third DFG of the program.

## Claims

### Claim 1

An optimization device comprising:
a processor configured to:
generate a first DFG corresponding to a first loop and a second DFG corresponding to a second loop for a program in which an incomplete nested loop in which a first arithmetic operation result for each loop of the first loop is sequentially used in an arithmetic operation for each loop of the second loop of a second layer included in the first loop of a first layer is present; and
arrange a first data transfer node between an output portion of the first arithmetic operation result in the first DFG and an input portion of the first arithmetic operation result in the second DFG, the first data transfer node holding the first arithmetic operation result output from the first DFG, updating the held first arithmetic operation result, and outputting the held first arithmetic operation result to the second DFG, connect the first DFG and the second DFG by the first data transfer node, and generate a third DFG of the program.

### Claim 2 (depends on 1)

The optimization device according to claim 1, wherein the processor is further configured to determine whether the program includes the incomplete nested loop,
wherein the processor is configured to generate the first DFG and the second DFG when the program is determined to include the incomplete nested loop.

### Claim 3 (depends on 1)

The optimization device according to claim 1, wherein the processor is configured to generate a third DFG including the first data transfer node to which timing information is input and which updates the first arithmetic operation result held based on the timing information.

### Claim 4 (depends on 3)

The optimization device according to claim 3 wherein the processor is configured to generate the third DFG including the first data transfer node that updates the held first arithmetic operation result when the flag indicating the holding or update is input as the timing information and the flag indicating the update is input.

### Claim 5 (depends on 3)

The optimization device according to claim 3, wherein the processor is configured to generate the third DFG including the first data transfer node that updates the held first arithmetic operation result when the information indicating a data holding period is input as the timing information and the data holding period has elapsed.

### Claim 6 (depends on 1)

The optimization device according to claim 1, wherein the processor is further configured to map the third DFG generated by the DFG connection unit to a CGRA.

### Claim 7 (depends on 1)

The optimization device according to claim 1, wherein
the processor is configured to:
generate a first individual DFG for each of first processes as the first DFG when a plurality of the first processes are executed in parallel in the first loop, and generates a second individual DFG for each of second processes as the second DFG when a plurality of the second processes are executed in parallel in the second loop, and
connect each of the first individual DFGs and the second DFG when the first individual DFG is generated, and connect each of the first DFG and the second individual DFG to generate a third DFG of the program when the second individual DFG is generated.

### Claim 8 (depends on 1)

The optimization device according to claim 1, wherein
the processor is configured to:
in a case where a third loop of a third layer included in the second loop is present, generate a third DFG corresponding to the third loop, and
arrange a second data transfer node that holds a second arithmetic operation result output from the second DFG, updates the held second arithmetic operation result, and outputs the held second arithmetic operation result to the third DFG between an output portion of the second arithmetic operation result in the second DFG and an input portion of the second arithmetic operation result in the third DFG, connect the second DFG and the third DFG by the second data transfer node, and generate the third DFG.

### Claim 9

An optimization method comprising:
generating a first DFG corresponding to a first loop and a second DFG corresponding to a second loop for a program in which an incomplete nested loop in which a first arithmetic operation result for each loop of the first loop is sequentially used in an arithmetic operation for each loop of the second loop of a second layer included in the first loop of a first layer is present; and
arranging a first data transfer node between an output portion of the first arithmetic operation result in the first DFG and an input portion of the first arithmetic operation result in the second DFG, the first data transfer node holding the first arithmetic operation result output from the first DFG, updating the held first arithmetic operation result, and outputting the held first arithmetic operation result to the second DFG, connecting the first DFG and the second DFG by the first data transfer node, and generating a third DFG of the program, using a processor.
