Apparatus and method for data partition and allocation in heterogeneous multi-processor environment

Patent metadata

Field	Value
Publication number	US-9612867-B2
Application number	US-201113197664-A
Country	US
Kind code	B2
Filing date	Aug 3, 2011
Priority date	Nov 23, 2010
Publication date	Apr 4, 2017
Grant date	Apr 4, 2017

Abstract

An apparatus for data processing in a heterogeneous multi-processor environment are provided. The apparatus including an analysis unit configured to analyze 1) operations to be run in connection with data processing and 2) types and a number of processors available for the data processing, a partition unit configured to dynamically partition data into a plurality of data regions having different sizes based on the analyzed operations and operation-specific processor priority information, which is stored in advance of running the operations, and a scheduling unit configured to perform scheduling by allocating operations to be run in the data regions between the available processors.

First claim

What is claimed is:

1. An apparatus for optimizing data processing in a heterogeneous multi-processor environment, the apparatus comprising:
an optimizing processor comprising
an analyzer configured to analyze
operations to be run in connection with data processing, by putting on hold operations called over a predetermined period of time, and monitoring the called operations for the predetermined period of time,
a processor type of each processor available for the data processing among processors in the heterogeneous multi-processor environment, and
a quantity of the processors available for the data processing;

a partitioner configured to dynamically partition data into data regions having different sizes, based on the analyzed operations and operation-specific processor priority information, wherein the operation-specific processor priority information is stored in advance of running the operations; and
a scheduler configured to perform scheduling, by allocating operations to be run in the data regions between the processors available for the data processing.

2. The apparatus of claim 1 , wherein the operation-specific processor priority information comprises priority levels of the processors available for the data processing, to run each operation at high speed.

3. The apparatus of claim 1 , wherein the scheduler is further configured to manage the operations to be run in the data regions by placing the operations to be run in the data regions in a queue.

4. The apparatus of claim 3 , wherein the scheduler is further configured to place first in the queue, operations to be run in data regions having an operation dependency therebetween, regardless of a sequence between the data regions.

5. The apparatus of claim 4 , wherein the scheduler is further configured to place first in the queue operations to be run in data regions having an operation dependency therebetween that is higher than other data regions.

6. The apparatus of claim 1 , wherein the partitioner is further configured to preliminarily partition the data into preliminary data regions and incorporate preliminary data regions, whose size is less than a predetermined size, with their neighboring preliminary data regions.

7. The apparatus of claim 6 , wherein the partitioner is further configured to determine a direction in which to partition the data, in response to the data being two-dimensional or higher-dimensional.

8. The apparatus of claim 6 , wherein the partitioner is further configured to additionally partition each data region, whose size is greater than a predetermined size, into smaller data regions.

9. The apparatus of claim 1 , wherein the data regions comprise at least one data region with data for more than one operation.

10. An apparatus for optimizing data processing in a heterogeneous multi-processor environment, the apparatus comprising:
an optimizing processor comprising:
an analyzer configured to analyze operations to be run in connection with data processing, to analyze a processor type of each processor available for the data processing among processors in the heterogeneous multi-processor environment, and to analyze a quantity of the processors available for the data processing;
a partitioner configured to
dynamically partition data into data regions having different sizes, based on the analyzed operations and operation-specific processor priority information, wherein the operation-specific processor priority information is stored in advance of running the operations, and
determine a direction in which to partition the data, in response to the data is two-dimensional or higher-dimensional, wherein the direction in which to partition the data is a direction that produces a smallest quotient when dividing a total quantity of operations to be run by a quantity of data regions; and

a scheduler configured to perform scheduling, by allocating operations to be run in the data regions between the processors available for the data processing.

11. A method of optimizing data processing in a heterogeneous multi-processor environment, the method comprising:
analyzing, in an optimizing processor,
operations to be run in connection with data processing, by putting on hold operations called over a predetermined period of time, and monitoring the called operations for the predetermined period of time,
a processor type of each processor available for the data processing among processors in the heterogeneous multi-processor environment, and
a quantity of the processors available for the data processing;

dynamically partitioning data into data regions having different sizes, based on the analyzed operations and operation-specific processor priority information, wherein the operation-specific processor priority information is stored in advance of running the operations; and
performing scheduling, by allocating operations to be run in the data regions between the processors available for the data processing.

12. The method of claim 11 , wherein the operation-specific processor priority information comprises priority levels of the processors available for the data processing, to run each operation at high speed.

13. The method of claim 11 , wherein the performing scheduling comprises managing the operations to be run in the data regions by placing the operations to be run in the data regions in a queue.

14. The method of claim 13 , wherein the performing scheduling further comprises placing first in the queue operations to be run in data regions having an operation dependency therebetween, regardless of a sequence between the data regions.

15. The method of claim 14 , wherein the performing scheduling further comprises placing first in the queue operations to be run in data regions having an operation dependency therebetween that is higher than other data regions.

16. The method of claim 11 , wherein the dynamically partitioning the data comprises preliminarily partitioning the data into preliminary data regions and incorporating preliminary data regions, whose size is less than a predetermined size, with their neighboring preliminary data regions.

17. The method of claim 16 , wherein the dynamically partitioning the data further comprises determining a direction in which to partition the data, in response to the data being two-dimensional or higher-dimensional.

18. The method of claim 16 , wherein the dynamically partitioning the data further comprises additionally partitioning each data region, whose size is greater than a predetermined size, into smaller data regions.

19. A method of optimizing data processing in a heterogeneous multi-processor environment, the method comprising:
analyzing, in an optimizing processor,
operations to be run in connection with data processing,
a processor type of each processor available for the data processing among processors in the heterogeneous multi-processor environment, and
a quantity of the processors available for the data processing;

dynamically partitioning data into data regions having different sizes, based on the analyzed operations and operation-specific processor priority information, wherein the operation-specific processor priority information is stored in advance of running the operations,
wherein the dynamically partitioning the data comprises determining a direction in which to partition the data, in response to the data being two-dimensional or higher-dimensional, and
wherein the direction in which to partition the data is a direction that produces a smallest quotient when dividing a total q

Assignees

• Chung Hee-Jin
• Baik Hyun-Ki
• Kim Jae-Won
• Joung Gyong-Jin
• Samsung Electronics Co Ltd

Inventors

• Chung Hee-Jin
• Baik Hyun-Ki
• Kim Jae-Won
• Joung Gyong-Jin

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F2209/483

  Multiproc · CPC title