# US 2010/0138810 A1 · Paralleling processing method, system and program

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

- Number: US 2010/0138810 A1
- Document ID: US20100138810A1
- Status: Published application
- Kind: A1
- Application number: 12/629,114
- Filed: 2009-12-02
- Published: 2010-06-03
- Earliest claimed: 2008-12-03
- Assignees: International Business Machines Corporation
- Inventors: Hideaki Komatsu; Arquimedes Martinez Canedo; Takeo Yoshizawa
- Web page: https://patentgrep.com/patent/US20100138810A1

## CPC

- G06F 8/30: Creation or generation of source code
- G06F 8/456: {Parallelism detection}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Paralleling processing system and method. When clusters are formed based on strongly connected components, a single cluster (fat cluster) having at least a predetermined number of blocks, or an expected processing time exceeding a predetermined threshold, is formed. The fat cluster is subjected to an unrolling process to make multiple copies of the processing of the fat cluster and to assign the copies to individual processors. Processing of the fat cluster is executed by the multiple processor devices in a pipelined manner. If a fat cluster to be iteratively executed cannot be executed in the pipelined manner because a processing result of an nth iteration of the fat cluster depends on a processing result of a preceding iteration of the fat cluster an input value needed for execution of the fat cluster is generated based on a certain prediction, and the fat cluster is speculatively executed.

## Claims

### Claim 1

A computer implemented code generating method generating codes to be assigned to, and executed in parallel by, individual processor devices in a multiprocessor system, the method comprising the steps of:
receiving source code of a program, the source code including a plurality of blocks connected one to another;
clustering the blocks by detecting a strongly connected component;
unrolling clusters to find a cluster that exceeds a predetermined threshold;
making at least one copy of the cluster found in the unrolling step; and
providing a process flow in which the cluster and the at least one copy of the cluster together form parallelized pipelines.

### Claim 2 (depends on 1)

The code generating method according to claim 1, wherein the step of clustering includes a step of merging clusters to reduce communication cost when the clusters are assigned to the processors.

### Claim 3 (depends on 1)

The code generating method according to claim 1, wherein the predetermined threshold is the number of blocks in the cluster.

### Claim 4 (depends on 1)

The code generating method according to claim 1, wherein the predetermined threshold is the processing time expected for the cluster.

### Claim 5

A paralleling execution method for causing processing to be assigned to, and executed in parallel by, individual processor devices in a multiprocessor computer system, the method comprising the steps of:
receiving source code of a program representing the processing, the source code including a plurality of blocks connected one to another;
clustering the blocks by detecting a strongly connected component;
unrolling clusters to find a cluster that exceeds a predetermined threshold;
making at least one copy of the cluster found in the unrolling step;
providing a process flow in which the cluster and the at least one copy of the cluster together form parallelized pipelines;
generating a code for each of the clusters;
compiling the codes to obtain executable codes; and
causing the executable codes to be assigned to and executed by individual processors on a runtime environment.

### Claim 6 (depends on 5)

The paralleling execution method according to claim 5, wherein the step of clustering includes a step of merging clusters to reduce a communication cost required when the clusters are assigned to the processors.

### Claim 7 (depends on 5)

The paralleling execution method according to claim 5, wherein the predetermined threshold is the number of blocks in the cluster.

### Claim 8 (depends on 5)

The paralleling execution method according to claim 5, wherein the predetermined threshold is the processing time expected for the cluster.

### Claim 9

A paralleling execution system for causing processing to be assigned to, and executed in parallel by, individual processor devices in a multiprocessor system, the paralleling execution system comprising:
storage means for storing source code of a program representing the processing, the source code including a plurality of blocks connected one to another;
clustering means for clustering the blocks by detecting a strongly connected component;
cluster unrolling means for (i) finding a cluster that exceeds a predetermined threshold, (ii) making at least one copy of the cluster thus found, and (iii) providing a process flow in which the cluster and the at least one copy of the cluster together form parallelized pipelines;
means for generating a code for each of the clusters;
a compiler for compiling the codes to obtain executable codes, respectively; and
means for causing the executable codes to be assigned to and executed by individual processors in a runtime environment.

### Claim 10 (depends on 9)

The paralleling execution system according to claim 9, wherein the clustering means comprises means for merging clusters to reduce communication cost when the clusters are assigned to the processors.

### Claim 11 (depends on 9)

The paralleling execution system according to claim 9, wherein the predetermined threshold is the number of blocks in the cluster.

### Claim 12 (depends on 9)

The paralleling execution system according to claim 9, wherein the predetermined threshold is the processing time expected for the cluster.

### Claim 13

A computer readable article of manufacture tangibly embodying a computer readable code generating program which, when executed through processing of a computer to generate codes to be assigned to, and executed in parallel by, individual processor devices in a multiprocessor system, causes the computer to execute the steps of:
receiving source code of a program, the source code including a plurality of blocks connected one to another;
clustering the blocks by detecting a strongly connected component;
unrolling clusters to find a cluster that exceeds a predetermined threshold;
making at least one copy of the cluster found in the unrolling step; and
providing a process flow in which the cluster and the at least one copy of the cluster together form parallelized pipelines.

### Claim 14 (depends on 13)

The article of manufacture according to claim 13, wherein the step of clustering comprises a step of merging clusters to reduce communication cost when the clusters are assigned to the processors.

### Claim 15 (depends on 13)

The article of manufacture according to claim 13, wherein the predetermined threshold is the number of blocks in the cluster.

### Claim 16 (depends on 13)

The article of manufacture according to claim 13, wherein the predetermined threshold is a processing time expected for the cluster.

### Claim 17

A computer readable article of manufacture tangibly embodying a computer readable paralleling execution program which, when executed, causes processing to be assigned to, and executed in parallel by, individual processor devices in a multiprocessor system, by causing the multiprocessor system to execute the steps of:
receiving source code of a program representing the processing, the source code including a plurality of blocks connected one to another;
clustering the blocks by detecting a strongly connected component;
unrolling clusters to find a cluster that exceeds a predetermined threshold;
making at least one copy of the cluster found in the unrolling step;
providing a process flow in which the cluster and the at least one copy of the cluster together form parallelized pipelines;
generating a code for each of the clusters;
compiling the codes to obtain executable codes, and causing the executable codes to be assigned to and executed by the individual processors in a runtime environment.

### Claim 18 (depends on 17)

The article of manufacture according to claim 17, wherein the step of clustering further comprises a step of merging clusters to reduce a communication cost required when the clusters are assigned to the processors.

### Claim 19 (depends on 17)

The article of manufacture according to claim 17, wherein the predetermined threshold is the number of blocks in the cluster.

### Claim 20 (depends on 17)

The article of manufacture according to claim 17, wherein the predetermined threshold is a processing time expected for the cluster.
