Parallelization method, parallelization tool, and in-vehicle device

Patent metadata

Field	Value
Publication number	US-10228948-B2
Application number	US-201715614771-A
Country	US
Kind code	B2
Filing date	Jun 6, 2017
Priority date	Jun 13, 2016
Publication date	Mar 12, 2019
Grant date	Mar 12, 2019

Abstract

A computer obtains invalidation information that shows ignorable data dependency relationships from among a plurality of data dependency relationships, and extracts a synchronous-dependent relationship from among the ignorable data dependency relationships that are shown as a write-write to the same data by the invalidation information. Then, the computer generates a parallel program for maximizing the number of parallelized macro tasks by ignoring other data dependency relationships other than the extracted synchronous-dependent relationship while preventing simultaneous write to the same data by two macro tasks having the synchronous-dependent relationship.

First claim

What is claimed is:

1. A parallelization method for generating a parallel program for a multi-core microcomputer, (i) based on a single program for a single-core microcomputer and (ii-a) by performing a data dependency analysis about data dependency relationships among unit processes of the single program respectively accessing a same data and (ii-b) by parallelizing parallelizable unit processes of the single program, the parallelization method comprising:
an extraction procedure (i) obtaining invalidation information indicative of an ignorable relationship among a plurality of the data dependency relationships, and (ii) extracting from the invalidation information a write-write data dependency relationship showing an access to the same data as a synchronous-dependent relationship; and
a generation procedure generating the parallel program for parallelizing a maximum number of the parallelizable unit processes, while preventing data abnormality by (a) ignoring other data dependency relationships other than the synchronous-dependent relationship, and (b) preventing simultaneous execution of the two unit processes having the synchronous-dependent relationship.

2. The parallelization method of claim 1 , wherein
the extraction procedure (i) obtains contemporaneously mandatory information that shows, from among a plurality of data, a specific data that must abide by a control restriction on a timing of write and read, and (ii) extracts, from among the data dependency relationships shown by the invalidation information, a data dependency relationship including the write and read of the specific data that is shown by the contemporaneously mandatory information, the extracted data dependency relationship extracted as the synchronous-dependent relationship, and
the generation procedure (iii) ignores, from among the data dependency relationships shown by the invalidation information, the data dependency relationship that is not extracted by the extraction procedure, and (iv) generates the parallel program that achieves the maximum number of parallelization of the unit processes while (a) preventing simultaneous write to the same data by the two unit processes having the synchronous-dependent relationship and (b) maintaining the control restriction on the timing.

3. The parallelization method of claim 1 , wherein
the generation procedure generates the parallel program by either maintaining or reversing a processing order of the two unit processes relative to the processing order of the two unit processes in the single program.

4. The parallelization method of claim 1 , wherein
the extraction procedure exhaustively generates, for all of the extracted synchronous-dependent relationships, data dependency patterns by either maintaining or reversing a processing order of the two unit processes relative to the processing order of the two unit processes in the single program.

5. The parallelization method of claim 4 further comprising, in the generation procedure:
a calculation procedure calculating a degree of parallelization for each of a plurality of scheduling results based on a scheduling of each of the generated data dependency patterns; and
a determination procedure generating the parallel program with the number of parallelized unit processes maximized by adopting a scheduling result that has a maximum degree of parallelization calculated by the calculation procedure.

6. The parallelization method of claim 1 , wherein
the plurality of unit processes of the single program are divisible in terms of dividing into a plurality of function groups, and
the invalidation information shows, as the ignorable relationship, the data dependency relationship among the unit processes that are divided into respectively different function groups.

7. A parallelization tool comprising:
a processor and a memory, the processor executes instructions in the memory to
generate a parallel program for a multi-core microcomputer, (i) based on a single program for a single-core microcomputer and (ii-a) by performing a data dependency analysis about data dependency relationships among unit processes of the single program respectively accessing a same data and (ii-b) by parallelizing parallelizable unit processes of the single program;
(i) obtain invalidation information indicative of an ignorable relationship among a plurality of the data dependency relationships and (ii) extract from the invalidation information a write-write data dependency relationship showing an access to the same data as a synchronous-dependent relationship; and
generate the parallel program for parallelizing a maximum number of the parallelizable unit processes while preventing data abnormality by (i) ignoring other data dependency relationships other than the synchronous-dependent relationship and (ii) preventing simultaneous execution of the two unit processes having the synchronous-dependent relationship.

8. The parallelization tool of claim 7 , wherein the processor is further configured to
(i) obtain contemporaneously mandatory information that shows, from among a plurality of data, a specific data that must abide by a control restriction on a timing of write and read, and (ii) extract, from among the data dependency relationships shown by the invalidation information, a data dependency relationship including the write and read of the specific data that is shown by the contemporaneously mandatory information, the extracted data dependency relationship extracted as the synchronous-dependent relationship, and
(iii) ignore, from among the data dependency relationships shown by the invalidation information, the data dependency relationship that is not extracted, and (iv) generate the parallel program that achieves the maximum number of parallelization of the unit processes while (a) preventing simultaneous write to the same data by the two unit processes having the synchronous-dependent relationship and (b) maintaining the control restriction on the timing.

9. The parallelization tool of claim 7 , wherein the processor is further configured to
generate the parallel program by either maintaining or reversing a processing order of the two unit processes relative to the processing order of the two unit processes in the single program.

10. The parallelization tool of claim 7 , wherein the processor is further configured to
exhaustively generate, for all of the extracted synchronous-dependent relationships, data dependency patterns by either maintaining or reversing a processing order of the two unit processes relative to the processing order of the two unit processes in the single program.

11. The parallelization tool of claim 10 , wherein the processor is further configured to
calculate a degree of parallelization for each of a plurality of scheduling results based on a scheduling of each of the generated data dependency patterns; and
generate the parallel program with the number of parallelized unit processes maximized by adopting a scheduling result that has a maximum degree of parallelization which is calculated.

12. The parallelization tool of claim 7 , wherein the plurality of unit processes of the single program are divisible in terms of dividing into a plurality of function groups, and the invalidation information shows, as the ignorable relationship, the data dependency relationship among the unit processes that are divided into respectively different function groups.

13. An in-vehicle device comprising:
a multi-core microcomputer having a plurality of cores; and
a parallel program having, based on a plurality of unit processes of a single program for a single-core microcomputer, the plurality

Assignees

• Denso Corp

Inventors

• Mineda Kenichi

Classifications

• G06F8/456

  Parallelism detection · CPC title

• G06F9/46

  Multiprogramming arrangements · CPC title

• G06F9/3838

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F9/38 Primary

  Concurrent instruction execution, e.g. pipeline or look ahead · CPC title