Parallelization method, parallelization tool, and in-vehicle device
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.
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 and included in different tasks to access the same resource to a same core of the multi-core microcomputer to prevent from generating an interference among the multiple cores so that the plurality of the unit processes includes an intra-core exclusion process,
wherein
the interference is caused by the same resource commonly accessed by the multiple tasks; and
the intra-core exclusion process is a process that performs a task interruption prohibition, and a task interruption permission.
2. The parallelization method of claim 1 , wherein
the allocation procedure adds another 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 and included in different tasks to access the same resource to a same core of the multi-core microcomputer to prevent from generating an interference among the multiple cores so that the plurality of the unit processes includes an intra-core exclusion process,
wherein
the interference is caused by the same resource commonly accessed by the multiple tasks; and
the intra-core exclusion process is a process that performs a task interruption prohibition, and a task interruption permission.
7. The parallelization tool of claim 6 , wherein
the allocator adds another 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) allocate the extracted plural unit processes included in different tasks to access the same resource to the same core of the multi-core microcomputer to prevent from generating an interference among the multiple cores so that the plurality of the unit processes includes an intra-core exclusion process,
the interference is caused by the same resource commonly accessed by the multiple tasks; and
the intra-core exclusion process is a process that performs a task interruption prohibition, and a task interruption permission, 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 cores.