Parallelization compiling method, parallelization compiler, and vehicular device

Patent metadata

Field	Value
Publication number	US-10228923-B2
Application number	US-201615083502-A
Country	US
Kind code	B2
Filing date	Mar 29, 2016
Priority date	Mar 31, 2015
Publication date	Mar 12, 2019
Grant date	Mar 12, 2019

Abstract

A parallelization compiling method for generating a segmented program from a sequential program, in which multiple macro tasks are included and at least two of the macro tasks have a data dependency relationship with one another, includes determining an existence of invalidation information for invalidating at least a part of the data dependency relationship between the at least two of the plurality of macro tasks before compiling the sequential program into the segmented program, and generating the segmented program by compiling the sequential program into the segmented program with reference to a determination result of the existence of the invalidation information. When the invalidation information is determined to exist, the at least a part of the data dependency relationship is invalidated before the compiling of the sequential program into the segmented program.

First claim

What is claimed is:

1. A parallelization compiling method for generating a segmented program, which is executable by a multi-core processor, from a sequential program, which is executable by a single-core processor, by parallelizing the sequential program, wherein the sequential program includes a plurality of macro tasks and at least two of the plurality of macro tasks have a data dependency relationship with one another,
the parallelization compiling method comprising:
determining an existence of invalidation information for invalidating at least a part of the data dependency relationship between the at least two of the plurality of macro tasks before compiling the sequential program into the segmented program;
generating the segmented program by compiling the sequential program into the segmented program with reference to a determination result of the existence of the invalidation information, wherein, when the invalidation information is determined to exist, the at least a part of the data dependency relationship is invalidated before the compiling of the sequential program into the segmented program; and
assigning another two of the plurality of macro tasks to a same core of the multi-core processor in the compiling of the sequential program into the segmented program in response to a determination that the another two of the plurality of macro tasks have a data dependency relationship that cannot be invalidated by the invalidation information, wherein
each of the plurality of macro tasks includes a series of procedures that include various operations, assignments, branching processing, and function calls.

2. The parallelization compiling method according to claim 1 , further comprising:
determining whether the at least two of the plurality of macro tasks, which are determined to have the invalidation information, mutually have a dependency of a process synchronization timing when the existence of the invalidation information is determined, wherein,
when determining that the at least two of the plurality of macro tasks mutually have the dependency of the process synchronization timing, the segmented program is compiled to maintain the dependency of the process synchronization timing by adjusting respective execution time of the at least two of the plurality of macro tasks during the generating of the segmented program.

3. The parallelization compiling method according to claim 2 , wherein,
during the generating of the segmented program, the respective execution time of the at least two of the plurality of macro tasks are adjusted to satisfy a predetermined standard for generating the segmented program and maintain the dependency of the process synchronization timing.

4. The parallelization compiling method according to claim 1 , further comprising:
determining whether the at least two of the plurality of macro tasks, which are determined to have the invalidation information, mutually have a dependency of a process synchronization timing when the existence of the invalidation information is determined, wherein,
when determining that the at least two of the plurality of macro tasks mutually have the dependency of the process synchronization timing, the segmented program is compiled to maintain the dependency of the process synchronization timing by reversing the data dependency relationship of the at least two of the plurality of macro tasks during the generating of the segmented program.

5. The parallelization compiling method according to claim 1 , further comprising:
in a case where (i) the existence of the invalidation information is determined and (ii) a first macro task included in the at least two of the plurality of macro tasks, which are determined to have the invalidation information, has had a data dependency relationship with another macro task but no longer has the data dependency relationship with the another macro task by newly having the data dependency relationship with a second macro task included in the at least two of the plurality of macro tasks, determining whether the data dependency relationship with the another macro task is eliminated, wherein,
during the generating of the segmented program, the data dependency relationship between the another macro task and the first macro task is recovered in compiling of the segmented program.

6. The parallelization compiling method of claim 1 , wherein
the assigning of the another two of the plurality of macro tasks to the same core and the generating of the segmented program in which the data dependency relationship is invalidated accelerates processing of the plurality of macro tasks by executing the plurality of macro tasks independently without considering a processing state of other cores of the multi-processor cores.

7. A parallelization compiler stored in a non-transitory tangible computer readable storage medium as a program product, wherein the parallelization compiler generates a segmented program, which is executable by a multi-core processor, from a sequential program, which is executable by a single-core processor, by parallelizing the sequential program and the sequential program includes a plurality of macro tasks and at least two of the plurality of macro tasks have a data dependency relationship with one another,
the parallelization compiler comprising instructions to be executed by a parallelization compiling device, the instructions for implementing:
determining an existence of invalidation information for invalidating at least a part of the data dependency relationship between the at least two of the plurality of macro tasks before compiling the sequential program into the segmented program;
generating the segmented program by compiling the sequential program into the segmented program with reference to a determination result of the existence of the invalidation information, wherein, when the invalidation information is determined to exist, the at least a part of the data dependency relationship is invalidated before the compiling of the sequential program into the segmented program; and
assigning another two of the plurality of macro tasks to a same core of the multi-core processor in the compiling of the sequential program into the segmented program in response to a determination that the another two of the plurality of macro tasks have a data dependency relationship that cannot be invalidated by the invalidation information, wherein
each of the plurality of macro tasks includes a series of procedures that include various operations, assignments, branching processing, and function calls.

8. The parallelization compiler according to claim 7 , further comprising:
an instruction to be executed by the parallelization compiling device and the instruction for determining whether the at least two of the plurality of macro tasks, which are determined to have the invalidation information, mutually have a dependency of a process synchronization timing when the existence of the invalidation information is determined, wherein,
when determining that the at least two of the plurality of macro tasks mutually have the dependency of the process synchronization timing, the segmented program is compiled to maintain the dependency of the process synchronization timing by adjusting respective execution time of the at least two of the plurality of macro tasks during the generating of the segmented program.

9. The parallelization compiler according to claim 8 , wherein,
during the generating of the segmented program, the respective execution time of the at least two of the plurality of macro tasks are adjusted to satisfy a predetermined standard for generating the segmented program and maintain the dependency of the process synchronization timing.

Assignees

• Denso Corp
• Univ Waseda

Inventors

• Yatou Yoshihiro
• Suzuki Noriyuki
• Mineda Kenichi
• Kasahara Hironori
• Kimura Keiji
• Mikami Hiroki
• Umeda Dan

Classifications

• G06F8/458 Primary

  Synchronisation, e.g. post-wait, barriers, locks (synchronisation among tasks G06F9/52) · CPC title

• G06F8/456

  Parallelism detection · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/454

  Consistency (cache consistency protocols in hierarchically structured memory systems G06F12/0815) · CPC title

• G06F9/52

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title