Patent ID: 11934835
Assignee: EMMTRIX TECHNOLOGIES GMBH
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A computer-implemented method for validation of correct derivation of a parallel program from a sequential program for deployment of the parallel program to a plurality of processing units, the method comprising:
computing, from code of the sequential program, a first control flow graph representing all paths that can be traversed through an execution of the sequential program, and determining dependencies within the first control flow graph, wherein a particular dependency between two statements involves a first statement and a second statement wherein the second statement depends on a result of the first statement;
computing, from the code of the parallel program, further control flow graphs with a further control flow graph for each thread or process of the parallel program, with each thread or process having its own entry point and running independently, the further control flow graphs representing all paths that can be traversed through the execution of the parallel program, and determining dependencies within the further control flow graphs;
checking if the derived parallel program and the sequential program are semantically equivalent by comparing the respective control flow graphs and dependencies to prove either:
that each relevant statement in the parallel program corresponds to an identical statement in the sequential program, wherein a relevant statement in the parallel program is any statement which is not only employed to synchronize control flow or exchange data, and wherein a sequential statement in the sequential program is identical to a parallelized statement in the parallel program if the sequential statement and parallelized statement:
perform a same calculation,
have corresponding dependencies in that, for a dependency of the sequential statement on a further sequential statement, and a corresponding dependency of the parallelized statement on a further parallelized statement, the further sequential statement corresponds to the further parallelized statement;

or:
that output data of the sequential program and the parallel program are computed by identical instructions, wherein two instructions are identical if:

both instructions perform the same calculation,
both instructions are executed under same conditions,
input data of both instructions are computed by identical instructions or correspond to identical input data of the sequential program and the parallel program; and
if the derived parallel program and the sequential program are semantically equivalent, setting a correct derivation state for the parallel program, which qualifies the parallel program for deployment.