Parallelization method, parallelization tool, and in-vehicle apparatus

Patent metadata

Field	Value
Publication number	US-10296316-B2
Application number	US-201615350368-A
Country	US
Kind code	B2
Filing date	Nov 14, 2016
Priority date	Dec 10, 2015
Publication date	May 21, 2019
Grant date	May 21, 2019

Abstract

A method is for generating a parallel program for a multicore microcomputer from processes in a single program for a single core. The method includes extraction procedure, association procedure, and analysis procedure. The extraction procedure extracts (i) an extracted address of an accessed data item, which is among data items stored in a storage area together with the processes and accessed when each process is executed and (ii) an extracted symbol name of the accessed data item. The association procedure associates an associated address in the storage area storing the accessed data item of the extracted symbol name with the extracted symbol name. The analysis procedure analyzes a dependency between each process based on the extracted address and the associated address, and determines that two processes accessing an identical address have a dependency while determining that two processes not accessing an identical address have no dependency.

First claim

What is claimed is:

1. A parallelization method comprising:
determining, in response to starting to generate a parallel program, whether an accessed data item is a first data item that has a symbol name or a second data item that does not have a symbol name,
the accessed data item being among a plurality of data items that are stored in a storage area together with a plurality of processes, the first data item and the second data item being included to be simultaneously coexisting in the plurality of data items,
the accessed data item being accessed when each process among the plurality of processes is executed,
the plurality of processes being in a single program for a single core microcomputer having one core;

in response to the accessed data item being determined to be the second data item, (i) extracting an extracted address, the extracted address being an address location, in the storage area, at which the second data item is stored;
in response to the accessed data item being determined to be the first data item,
(i) extracting, as an extracted symbol name, the symbol name of the first data item; and
(ii) associating an associated address with the extracted symbol name by replacing the extracted symbol name with the associated address, the associated address being an address location, in the storage area, at which the first data item is stored;

performing an analysis procedure including
analyzing a dependency between, of the plurality of processes, a first process and a second process, to determine parallelizable processes from the plurality of processes, by determining whether or not a first address in the storage area accessed by the first process is identical to a second address in the storage area accessed by the second process,
the first address being either the extracted address or the associated address, the second address being either the extracted address or the associated address,

determining that the first process and the second process have the dependency in response to the first address being identical to the second address, and
determining that the first process and the second process fail to have the dependency in response to the first address failing to be identical to the second address;

scheduling each of the plurality of processes based on results of determining the dependency; and
generating the parallel program parallelized for a multicore microcomputer having a plurality of cores based on results of the scheduling,
wherein:
the parallel program allocates the plurality of processes to the plurality of cores respectively; and
a subject core that is any one of the cores of the multicore microcomputer executes any process that is allocated to the subject core itself.

2. The parallelization method according to claim 1 , wherein
either the extracted address or the associated address upon which the dependency is analyzed includes an address in a register of the storage area.

3. The parallelization method according to claim 1 , wherein
either the extracted address or the associated address upon which the dependency is analyzed includes an address in a result of compile of the single program and address mapping of each data item.

4. The parallelization method according to claim 1 , wherein
the plurality of processes are a plurality of macro tasks.

5. The parallelization method according to claim 1 , wherein
the storage area is provided as a memory space.

6. The parallelization method according to claim 1 , wherein
the extracted address and the extracted symbol name are extracted from the plurality of data items that are stored in the storage area.

7. A parallelization tool comprising:
a processor and a memory, the processor executes instructions in the memory to
determine, in response to starting to generate a parallel program, whether an accessed data item is a first data item that has a symbol name or a second data item that does not have a symbol name,
the accessed data item being among a plurality of data items that are stored in a storage area together with a plurality of processes, the first data item and the second data item being included to be simultaneously coexisting in the plurality of data items,
the accessed data item being accessed when each process among the plurality of processes is executed,
the plurality of processes being in a single program for a single core microcomputer having one core;

in response to the accessed data item being determined to be the second data item, (i) extract an extracted address, the extracted address being an address location, in the storage area, at which the second data item is stored; and
in response to the accessed data item being determined to be the first data item,
(i) extract, as an extracted symbol name, the symbol name of the first data item; and
(ii) associate an associated address with the extracted symbol name by replacing the extracted symbol name with the associated address, the associated address being an address location, in the storage area, at which the first data item is stored;

perform an analysis procedure including to
analyze a dependency between, of the plurality of processes, a first process and a second process, to determine parallelizable processes from the plurality of processes, by determining whether or not a first address in the storage area accessed by the first process is identical to a second address in the storage area accessed by the second process,
the first address being either the extracted address or the associated address, the second address being either the extracted address or the associated address,

determine that the first process and the second process have the dependency in response to the first address being identical to the second address, and
determine that the first process and the second process fail to have the dependency in response to the first address failing to be identical to the second address;

schedule each of the plurality of processes based on results of determining the dependency; and
generate the parallel program parallelized for a multicore microcomputer having a plurality of cores based on results of scheduling the plurality of processes,

wherein
the parallel program allocates the plurality of processes to the plurality of cores respectively; and
a subject core that is any one of the cores of the multicore microcomputer executes any process that is allocated to the subject core itself.

8. The parallelization tool according to claim 7 , wherein
either the extracted address or the associated address upon which the dependency is analyzed includes an address in a register of the storage area.

9. The parallelization tool according to claim 7 , wherein
either the extracted address or the associated address upon which the dependency is analyzed includes an address in a result of compile of the single program and address mapping of each data item.

10. The parallelization tool according to claim 7 , wherein
the plurality of processes are a plurality of macro tasks.

11. The parallelization tool according to claim 7 , wherein
the storage area is provided as a memory space.

12. The parallelization tool according to claim 7 , wherein
the extracted address and the extracted symbol name are extracted from the plurality of data items that are stored in the storage area.

13. An in-vehicle apparatus comprising:
a multicore microcomputer; and
a parallel program, the parallel program being generated by a processor and a memory storing instructions, the processor executes instructions in the memory to:
determine, in response to starting to generate the parallel pro

Assignees

• Denso Corp

Inventors

• Mineda Kenichi

Classifications

• G06F8/456 Primary

  Parallelism detection · CPC title