US 8,429,663 B2Granted

Allocating task groups to processor cores based on number of task allocated per core, tolerable execution time, distance between cores, core coordinates, performance and disposition pattern

AssigneeNEC Corporation

InventorsMasamichi Takagi, Masayuki Mizuno, Hiroaki Inoue

Life of this patent

Estimating the term…

Loading patent…

Abstract

Even if a multiprocessor includes an uneven performance core, an inoperative core or a core that does not satisfy such a performance as designed but if the contrivance of task allocation can satisfy the requirement of an application to be executed, the multiple processors are shipped. In a task group allocation method for allocating, to a processor having a plurality of cores, task groups included in an application for the processor to execute, a calculation section measures performances and disposition patterns of the cores, generates a restricting condition associating the measured performances and disposition patterns of the cores with information indicating whether the application can be executed, and, with reference to the restricting condition, reallocates to the cores, the task groups that have previously been allocated to the cores.

Claims16

Dependent claims

A task group allocation method that allocates, to a processor having a plurality of cores, task groups included in an application executed by the processor, comprising:

a step of measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores after manufacture and before shipment of a chip including the processor or measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores when a breakdown is detected by zero-performance of the chip at time of use of the chip;
a step of generating a restricting condition that associates the measured core performances and core disposition patterns with information indicating whether the application can be executed;
a step of, with reference to the restricting condition, reallocating, to the cores, the task groups in an order specified in the application that have previously been allocated to the cores;
a step of creating equations each describing a condition that one task group is allocated to only one core;
a step of creating equations each describing a condition that a number of task groups to be allocated to one core is zero or one;
a step of creating equations each representing a coordinate of each core;
a step of creating equations each representing a distance between cores;
a step of creating equations each describing that the sum of terms, indicating a completion time of a task group plus a communication time between two task groups, obtained by multiplying a parameter indicating to which core a task is allocated by a predetermined multiplier is not larger than a maximum tolerable finish time in each communication between task groups;
and
a step of simultaneously solving the above equations so as to determine a core to which each task group is allocated.

7 more elements

A task group allocation device that allocates, to a processor having a plurality of cores, task groups included in an application executed by the processor, comprising:

a hardware-implemented unit for measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores after manufacture and before shipment of a chip including the processor or measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores when a breakdown is detected by zero-performance of the chip at time of use of the chip, for generating a restricting condition that associates the measured core performances and core disposition patterns with information indicating whether the application can be executed;
a hardware-implemented unit for reallocating, to the cores, the task groups in an order specified in the application that have previously been allocated to the cores, with reference to the restricting condition;
a hardware-implemented unit for creating equations each describing a condition that one task group is allocated to only one core;
a hardware-implemented unit for creating equations each describing a condition that a number of task groups to be allocated to one core is zero or one;
a hardware-implemented unit for creating equations each representing a coordinate of each core;
a hardware-implemented unit for creating equations each representing a distance between cores;
a hardware-implemented unit for creating equations each describing that the sum of terms, indicating a completion time of a task group plus a communication time between two task groups, obtained by multiplying parameter indicating to which core a task is allocated by a predetermined multiplier is not larger than a maximum tolerable finish time in each communication between task groups;
and
a hardware-implemented unit for simultaneously solving the above equations so as to determine a core to which each task group is allocated.

6 more elements

A non-transitory computer-readable medium, on which a task group program is recorded, said program causing a computer to function as a task group allocation device that allocates, to a processor having a plurality of cores, task groups included in an application executed by the processor, said task group allocation device comprising:

a unit for measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores after manufacture and before shipment of a chip including the processor or measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores when a breakdown is detected by zero-performance of the chip at time of use of the chip, generating a restricting condition that associates the measured core performances and core disposition patterns with information indicating whether the application can be executed;
and
a unit for reallocating, to the cores, the task groups in an order specified in the application that have previously been allocated to the cores, with reference to the restricting condition;
a unit for creating equations each describing a condition that one task group is allocated to only one core;
a unit for creating equations each describing a condition that a number of task groups to be allocated to one core is zero or one;
a unit for creating equations each presenting a coordinate of each core;
a unit for creating equations each representing a distance between cores;
a unit for creating equations each describing that the sum of terms, indicating a completion time of a task group plus a communication time between two task groups, obtained by multiplying a parameter indicating to which core a task is allocated by a predetermined multiplier is not larger than a maximum tolerable finish time in each communication between task groups;
and
a unit for simultaneously solving the above equations so as to determine a core to which each task group is allocated.

7 more elements

A processor comprising the task group allocation device that allocates, to a processor having a plurality of cores, task groups included in an application executed by the processor, comprising:

a hardware-implemented unit for measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores after manufacture and before shipment of a chip including the processor or measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores when a breakdown is detected by zero-performance of the chip at time of use of the chip, for generating a restricting condition that associates the measured core performances and core disposition patterns with information indicating whether the application can be executed;
a hardware-implemented unit for reallocating, to the cores, the task groups in an order specified in the application that have previously been allocated to the cores with reference to the restricting condition;
a hardware-implemented unit for creating equations each describing a condition that one task group is allocated to only one core;
a hardware-implemented unit for creating equations each describing a condition that a number of task groups to be allocated to one core is zero or one;
a hardware-implemented unit for creating equations each representing a coordinate of each core;
a hardware-implemented unit for creating equations each representing a distance between cores;
a hardware-implemented unit for creating equations each describing that the sum of terms, indicating a completion time of a task group plus a communication time between two task groups, obtained by multiplying parameter indicating to which core a task is allocated by a predetermined multiplier is not larger than a maximum tolerable finish time in each communication between task groups;
and
a hardware-implemented unit for simultaneously solving the above equations so as to determine a core to which each task group is allocated.

6 more elements

A computer comprising the task group allocation device that allocates, to a processor having a plurality of cores, task groups included in an application executed by the processor, comprising:

a hardware-implemented unit for measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores after manufacture and before shipment of a chip including the processor or measuring performances of the cores and disposition patterns, inherent to the manufacturing, of the cores when a breakdown is detected by zero-performance of the chip at time of use of the chip, for generating a restricting condition that associates the measured core performances and core disposition patterns with information indicating whether the application can be executed;
a hardware-implemented unit for reallocating, to the cores, the task groups in an order specified in the application that have previously been allocated to the cores, with reference to the restricting condition;
a hardware-implemented unit for creating equations each describing a condition that one task group is allocated to only one core;
a hardware-implemented unit for creating equations each describing a condition that a number of task groups to be allocated to one core is zero or one;
a hardware-implemented unit for creating equations each representing a coordinate of each core;
a hardware-implemented unit for creating equations each representing a distance between cores;
a hardware-implemented unit for creating equations each describing that the sum of terms, indicating a completion time of a task group plus a communication time between two task groups, obtained by multiplying parameter indicating to which core a task is allocated by a predetermined multiplier is not larger than a maximum tolerable finish time in each communication between task groups;
and
a hardware-implemented unit for simultaneously solving the above equations so as to determine a core to which each task group is allocated.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 12/529,367Filed 5 Feb 2008
Priority: JP 2007-0528412 Mar 2007
Published: US 2010/0100886 A122 Apr 2010
Granted: 23 Apr 2013
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 9/5027
To service a request: the resource being a machine, e.g. CPUs, Servers, Terminals
G06F 11/1428
Reconfiguring to eliminate the error: with loss of hardware functionality
G06F 11/3419
For performance assessment: by assessing time
G06F 11/3433
For performance assessment: for load management