Parallelization method, parallelization tool, and in-vehicle device

Patent metadata

Field	Value
Publication number	US-2017364341-A1
Application number	US-201715617038-A
Country	US
Kind code	A1
Filing date	Jun 8, 2017
Priority date	Jun 21, 2016
Publication date	Dec 21, 2017
Grant date	—

Abstract

A computer generates a parallel program, based on an analysis of a single program that includes a plurality of tasks written for a single-core microcomputer, by parallelizing parallelizable tasks for a multi-core processor having multiple cores. The computer includes a macro task (MT) group extractor that analyzes, or finds, a commonly-accessed resource commonly accessed by the plurality of tasks, and extracts a plurality of MTs showing access to such commonly-accessed resource. Then, the computer uses an allocation restriction determiner to allocate the extracted plural MTs to the same core in the multi-core processor. By devising a parallelization method described above, an overhead in an execution time of the parallel program by the multi-core processor is reduced, and an in-vehicle device is enabled to execute each of the MTs in the program optimally.

First claim

What is claimed is:

1 . A parallelization method that generates a parallel program for a multi-core microcomputer having multiple cores, the parallel program parallelizing parallelizable unit processes based on (i) an analysis of a single program for a single-core microcomputer that includes multiple tasks, and (ii) a dependency relationship derived from the analysis and indicative of an access to a same resource from the unit processes, the parallelization method comprising:
an extraction procedure extracting a plurality of the unit processes accessing the same resource based on an analysis of the same resource commonly accessed by the multiple tasks; and an allocation procedure allocating the plurality of the unit processes extracted by the extraction procedure to a same core of the multi-core microcomputer.

2 . The parallelization method of claim 1 , wherein
the allocation procedure adds an intra-core exclusion process to the plurality of the unit processes that have been extracted by the extraction procedure, and have been allocated to a same core of the multi-core microcomputer.

3 . The parallelization method of claim 1 , wherein
the allocation procedure allocates the plurality of the unit processes extracted by the extraction procedure to different cores of the multi-core microcomputer, when the plurality of the unit processes extracted by the extraction procedure cannot be allocated to the same core of the multi-core microcomputer, and the parallelization method further comprises an addition procedure adding an inter-core exclusion process that prevents an access to the same resource from the different cores that respectively execute each of the plurality of the unit processes in case that the allocation procedure has allocated the plurality of the unit processes extracted by the extraction procedure to the different cores of the multi-core microcomputer.

4 . The parallelization method of claim 1 , wherein
the allocation procedure allocates the plurality of the unit processes extracted by the extraction procedure to different cores of the multi-core microcomputer, when the plurality of the unit processes extracted by the extraction procedure cannot be allocated to the same core of the multi-core microcomputer, and the parallelization method further comprises an interruption procedure adding an interruption process that prevents an access to the same resource from the different cores that respectively execute each of the plurality of the unit processes, by interrupting rest of the plurality of the unit processes during the access to the same resource by one of the plurality of the unit processes, when the allocation procedure allocates the plurality of the unit processes extracted by the extraction procedure to the different cores of the multi-core microcomputer.

5 . The parallelization method of claim 1 , wherein
core allocation information indicative of allocation destination of each of the plurality of the unit processes of the single program is obtained to allocate the plurality of the unit processes to the multiple cores of the multi-core microcomputer, and the allocation procedure prioritizes the core allocation information in allocating the plurality of the unit processes to specified cores, and allocates the plurality of the unit processes extracted by the extraction procedure to the same core of the multi-core microcomputer.

6 . A parallelization tool including a computer for generating a parallel program by parallelizing parallelizable unit processes for a multi-core microcomputer having multiple cores based on a dependency relationship indicative of an access to a same resource from plural unit processes of a single program, according to an analysis of a single program including multiple tasks for a single-core microcomputer, the parallelization tool comprising:
an extractor extracting a plurality of the unit processes accessing the same resource based on an analysis of the same resource commonly accessed by the multiple tasks; and an allocator allocating the plurality of the unit processes extracted by the extractor to a same core of the multi-core microcomputer.

7 . The parallelization tool of claim 6 , wherein
the allocator adds an intra-core exclusion process to the plurality of the unit processes that have been extracted by the extractor, and have been allocated to the same core of the multi-core microcomputer.

8 . The parallelization tool of claim 6 , wherein
the allocator allocates the plurality of the unit processes extracted by the extractor to different cores of the multi-core microcomputer, when the plurality of the unit processes extracted by the extractor cannot be allocated to the same core of the multi-core microcomputer, and the parallelization device further comprises an adder adding an inter-core exclusion process that prevents an access to the same resource from the different cores that respectively execute the plurality of the unit processes in case that the allocator has allocated the plurality of the unit processes extracted by the extractor to the different cores of the multi-core microcomputer.

9 . The parallelization tool of claim 6 , wherein
the allocator allocates the plurality of the unit processes extracted by the extractor to different cores of the multi-core microcomputer, when the plurality of the unit processes extracted by the extractor cannot be allocated to the same core of the multi-core microcomputer, and the parallelization tool further comprises an interrupter adding an interruption process that prevents an access to the same resource from the different cores that respectively execute each of the plurality of the unit processes by interrupting rest of the plurality of the unit processes during the access to the same resource by one of the plurality of the unit processes, when the allocator allocates the plurality of the unit processes extracted by the extractor to the different cores of the multi-core microcomputer.

10 . The parallelization tool of claim 6 , wherein
core allocation information indicative of allocation destination of each of the plurality of the unit processes of the single program is obtained by the computer to allocate the plurality of the unit processes to the multiple cores of the multi-core microcomputer, and the allocator prioritizes the core allocation information in allocating the plurality of the unit processes to specified cores, and allocates the plurality of the unit processes extracted by the extractor to the same core of the multi-core microcomputer.

11 . An in-vehicle device comprising:
a multi-core microcomputer having multiple cores; and a parallel program parallelizing a plurality of unit process in a single program for a single-core microcomputer, the single program including/processing multiple tasks by a single core, wherein the parallel program is configured to (a) parallelize the multiple tasks by parallelizing a plurality of parallelizable unit processes based on a data dependency indicative of an access to a same resource from plural unit processes of the single program, according to an analysis of the single program including the multiple tasks for the single-core microcomputer, (b) extract the plural unit processes extracted based on indication of an access to the commonly-accessed resource, by analyzing a commonly-accessed resource commonly accessed from the multiple tasks, and (c) allocates the extracted plural unit processes to the same core of the multi-core microcomputer, and the multi-core microcomputer is configured to execute the parallel program by using the multiple cores to respectively execute the unit processes assigned to the multiple core

Assignees

• Denso Corp

Inventors

• Mineda Kenichi

Classifications

• G06F8/451

  Code distribution (considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083) · CPC title

• G06F9/4881

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

• G06F8/456

  Parallelism detection · CPC title

• G06F9/5005

  to service a request · CPC title

• G06F8/45 Primary

  Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions · CPC title