# US 9,436,511 B2 · Full exploitation of parallel processors for data processing

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

- Number: US 9,436,511 B2
- Document ID: US9436511B2
- Status: Granted
- Kind: B2
- Application number: 14/623,919
- Filed: 2015-02-17
- Published: 2015-08-20
- Granted: 2016-09-06
- Earliest claimed: 2012-01-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Michael Hirsch; Shmuel T. Klein; Yair Toaff
- Web page: https://patentgrep.com/patent/US9436511B2

## CPC

- G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
- G06F 16/2272: {Management thereof}
- G06F 2209/485: Resource constraint
- G06F 2209/5012: Processor sets
- G06F 2209/506: Constraint
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Exemplary method, system, and computer program product embodiments for full exploitation of parallel processors for data processing are provided. In one embodiment, by way of example only, a set of parallel processors is partitioned into disjoint subsets according to indices of the set of the parallel processors. The size of each of the disjoint subsets corresponds to a number of processors assigned to the processing of the data chunks at one of the layers. Each of the processors are assigned to different layers in different data chunks such that each of processors are busy and the data chunks are fully processed within a number of the time steps equal to the number of the layers. A transition function is devised from the indices of the set of the parallel processors at one time steps to the indices of the set of the parallel processors at a following time step.

## Claims

### Claim 1

A method for full exploitation, after a plurality of initialization steps, of a set of a plurality of parallel processors to perform a task on a sequence of data chunks by a processor device in a computing environment, wherein each of the data chunks are processed in several time steps and by a plurality of layers with the plurality of layers being dealt with by at least one of a plurality of processors at each of the time steps, the method comprising:
partitioning the set of the plurality of parallel processors into disjoint subsets according to indices of the set of the plurality of parallel processors such that wherein,
the plurality of parallel processors are partitioned in accordance with one or more of a plurality of constraints;
the number of the plurality of parallel processors that are available is n=2d−1, where d is the number of the plurality of layers, n is the number of the plurality of parallel processors, and 2d−1 is also equal to n=(2d)−1, and
a size of each of the disjoint subsets corresponds to a number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers;
partitioning the task into the plurality of layers independent of partitioning the set of the plurality of parallel processors;
assigning each of the plurality of processors to the plurality of layers of the task according to the partitioning of the task such that each of the plurality of processors are busy and each of the data chunks are fully processed within a number of the time steps equal to the number of the plurality of layers, wherein the number of the plurality of parallel processors assigned to the processing of the data chunks at one of the plurality of layers is smaller than the number of the plurality of parallel processors assigned to the processing of the data chunks at a preceding one of the plurality of layers; and
selecting and using one of a plurality of constraints for restricting any one of the plurality of parallel processors to always work on the same one of the plurality of layers or, for each of the plurality of layers except for a first layer, to always work on a same data chunk as in each of the previous layers; wherein
the number of the plurality of parallel processors that are available is n=2d−1, where d is the number of the plurality of layers and n is the number of the plurality of parallel processors and 2d−1 is also equal to n=(2d)−1,
the number of the plurality of processors assigned to level 0 is n=2d−1, and
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers which is not the first is half of the number of the plurality of processors assigned to the processing of the data chunks at the previous one of the plurality of layers.

### Claim 2 (depends on 1)

The method of claim 1, further including:
processing each one of the data chunks within a number of time steps equal to a number of the plurality of layers; and
devising a transition function from the indices of the set of the plurality of parallel processors at one of the time steps to the indices of the set of the plurality of parallel processors at a following time step, wherein the transition function is consistent with the assigning.

### Claim 3 (depends on 2)

The method of claim 2, further including, subjecting the transition function to the plurality of constraints.

### Claim 4 (depends on 3)

The method of claim 3, wherein the plurality of constraints include restricting at least one of the plurality of processors at each of the time steps to the same one of the plurality of layers that is assigned for the processing of the data chunks.

### Claim 5 (depends on 3)

The method of claim 3, wherein the plurality of constraints include restricting the set of the plurality of parallel processors that is assigned to the processing of the data chunks at one of the plurality of layers which is not the first to be a subset of the set of the plurality of parallel processors assigned to the processing of the data chunks at previous one of the plurality of layers.

### Claim 6 (depends on 1)

The method of claim 1, wherein, if at least one of the plurality of processors, at each of the time steps, is restricted to being assigned to the same one of the plurality of layers for processing of the data chunks:
the plurality of parallel processors are indexed sets by the integers 0 to 2n−2,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i ones.

### Claim 7 (depends on 1)

The method of claim 1, further including, for each of the plurality of layers except a first one of the plurality of layers, restricting each one of the plurality of processors to the processing of a same data chunk of a previous layers of the plurality of layers, wherein:
the plurality of parallel processors are indexed sets by the integers 1 to 2n−1,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i zeros.

### Claim 8 (depends on 2)

The method of claim 2, further including, in conjunction with the devising, choosing the transition function as applying a cyclical shift by at least one bit to the left to a standard binary representation of the indices of the plurality of processors.

### Claim 9

A system for full exploitation, after a plurality of initialization steps, of a set of a plurality of parallel processors to perform a task on a sequence of data chunks in a computing environment, wherein each of the data chunks are processed in several time steps and by a plurality of layers with the plurality of layers being dealt with by at least one of a plurality of processors at each of the time steps, the system comprising:
a processor device operable in the computing environment, wherein the processor device is adapted for:
partitioning the set of the plurality of parallel processors into disjoint subsets according to indices of the set of the plurality of parallel processors wherein,
the plurality of parallel processors are partitioned in accordance with one or more of a plurality of constraints,
the number of the plurality of parallel processors that are available is n=2d−1, where d is the number of the plurality of layers, n is the number of the plurality of parallel processors, and 2d−1 is also equal to n=(2d)−1, and
a size of each of the disjoint subsets corresponds to a number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers;
partitioning the task into the plurality of layers independent of partitioning the set of the plurality of parallel processors,
assigning each of the plurality of processors to the plurality of layers of the task according to the partitioning of the task such that each of the plurality of processors are busy and each of the data chunks are fully processed within a number of the time steps equal to the number of the plurality of layers, wherein the number of the plurality of parallel processors assigned to the processing of the data chunks at one of the plurality of layers is smaller than the number of the plurality of parallel processors assigned to the processing of the data chunks at a preceding one of the plurality of layers, and
selecting and using one of a plurality of constraints for restricting any one of the plurality of parallel processors to always work on the same one of the plurality of layers or, for each of the plurality of layers except for a first layer, to always work on a same data chunk as in each of the previous layers; wherein
the number of the plurality of parallel processors that are available is n=2d−1, where d is the number of the plurality of layers and n is the number of the plurality of parallel processors and 2d−1 is also equal to n=(2d)−1,
the number of the plurality of processors assigned to level 0 is n=2d−1, and
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers which is not the first is half of the number of the plurality of processors assigned to the processing of the data chunks at the previous one of the plurality of layers.

### Claim 10 (depends on 9)

The system of claim 9, wherein the processor device is further adapted for:
processing each one of the data chunks within a number of time steps equal to a number of the plurality of layers; and
devising a transition function from the indices of the set of the plurality of parallel processors at one of the time steps to the indices of the set of the plurality of parallel processors at a following time step, wherein the transition function is consistent with the assigning.

### Claim 11 (depends on 10)

The system of claim 10, wherein the processor device is further adapted for subjecting the transition function to the plurality of constraints.

### Claim 12 (depends on 11)

The system of claim 11, wherein the plurality of constraints include restricting at least one of the plurality of processors at each of the time steps to the same one of the plurality of layers that is assigned for the processing of the data chunks.

### Claim 13 (depends on 11)

The system of claim 11, wherein the plurality of constraints include restricting the set of the plurality of parallel processors that is assigned to the processing of the data chunks at one of the plurality of layers which is not the first to be a subset of the set of the plurality of parallel processors assigned to the processing of the data chunks at previous one of the plurality of layers.

### Claim 14 (depends on 9)

The system of claim 9, wherein, if at least one of the plurality of processors, at each of the time steps, is restricted to being assigned to the same one of the plurality of layers for processing of the data chunks:
the plurality of parallel processors are indexed sets by the integers 0 to 2n−2,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i ones.

### Claim 15 (depends on 9)

The system of claim 9, further including, for each of the plurality of layers except a first one of the plurality of layers, restricting each one of the plurality of processors to the processing of a same data chunk of a previous layers of the plurality of layers, wherein:
the plurality of parallel processors are indexed sets by the integers 1 to 2n−1,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i zeros.

### Claim 16 (depends on 10)

The system of claim 10, wherein the processor device is further adapted for, in conjunction with the devising, choosing the transition function as applying a cyclical shift by at least one bit to the left to a standard binary representation of the indices of the plurality of processors.

### Claim 17

A computer program product for full exploitation, after a plurality of initialization steps, of a set of a plurality of parallel processors to perform a task on a sequence of data chunks by a processor device in a computing storage environment, wherein each of the data chunks are processed in several time steps and by a plurality of layers with the plurality of layers being dealt with by at least one of a plurality of processors at each of the time steps, the computer program product comprising a non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:
a first executable portion for partitioning the set of the plurality of parallel processors into disjoint subsets, according to indices of the set of the plurality of parallel processors such that a size of each of the disjoint subsets corresponds to a number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers;
a second executable portion for partitioning the task into the plurality of layers independent of partitioning the set of the plurality of parallel processors;
a third executable portion for assigning each of the plurality of processors to the plurality of layers of the task according to the partitioning of the task such that each of the plurality of processors are busy and each of the data chunks are fully processed within a number of the time steps equal to the number of the plurality of layers, wherein the number of the plurality of parallel processors assigned to the processing of the data chunks at one of the plurality of layers is smaller than the number of the plurality of processors assigned to the processing of the data chunks at a preceding one of the plurality of layers; and
a fourth executable portion for selecting and using one of a plurality of constraints for restricting any one of the plurality of parallel processors to always work on the same one of the plurality of layers or, for each of the plurality of layers except for a first layer, to always work on a same data chunk as in each of the previous layers; wherein
the number of the plurality of parallel processors that are available is n=2d−1, where d is the number of the plurality of layers and n is the number of the plurality of parallel processors and 2d−1 is also equal to n=(2d)−1,
the number of the plurality of processors assigned to level 0 is n=2d−1, and
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers which is not the first is half of the number of the plurality of processors assigned to the processing of the data chunks at the previous one of the plurality of layers.

### Claim 18 (depends on 17)

The computer program product of claim 17, further including
a fifth executable portion for processing each one of the data chunks within a number of time steps equal to a number of the plurality of layers; and
a sixth executable portion for devising a transition function from the indices of the set of the plurality of parallel processors at one of the time steps to the indices of the set of the plurality of parallel processors at a following time step, wherein the transition function is consistent with the assigning.

### Claim 19 (depends on 18)

The computer program product of claim 18, further including a seventh executable portion subjecting the transition function to the plurality of constraints.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the plurality of constraints include restricting at least one of the plurality of processors at each of the time steps to the same one of the plurality of layers that is assigned for the processing of the data chunks.

### Claim 21 (depends on 19)

The computer program product of claim 19, wherein the plurality of constraints include restricting the set of the plurality of parallel processors that is assigned to the processing of the data chunks at one of the plurality of layers which is not the first to be a subset of the set of the plurality of parallel processors assigned to the processing of the data chunks at previous one of the plurality of layers.

### Claim 22 (depends on 17)

The computer program product of claim 17, wherein, if at least one of the plurality of processors, at each of the time steps, is restricted to being assigned to the same one of the plurality of layers for processing of the data chunks:
the plurality of parallel processors are indexed sets by the integers 0 to 2n−2,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i ones.

### Claim 23 (depends on 17)

The computer program product of claim 17, further including, for each of the plurality of layers except a first one of the plurality of layers, a fifth executable portion for restricting each one of the plurality of processors to the processing of a same data chunk of a previous layers of the plurality of layers, wherein
the plurality of parallel processors are indexed sets by the integers 1 to 2n−1,
the number of the plurality of processors assigned to the processing of the data chunks at one of the plurality of layers indexed i, for i=0, 1, . . . , d−1 is n/2i, and
the indices of the plurality of parallel processors of n/2i are n/2i numbers that have a standard binary representation of length d+1 ending in 0 followed by i zeros.

### Claim 24 (depends on 18)

The computer program product of claim 18, further including a seventh executable portion for, in conjunction with the devising, choosing the transition function as applying a cyclical shift by at least one bit to the left to a standard binary representation of the indices of the plurality of processors.