System and method for generation of event driven, tuple-space based programs

Patent metadata

Field	Value
Publication number	US-11789769-B2
Application number	US-202016791361-A
Country	US
Kind code	B2
Filing date	Feb 14, 2020
Priority date	Sep 20, 2013
Publication date	Oct 17, 2023
Grant date	Oct 17, 2023

Abstract

In a system for automatic generation of event-driven, tuple-space based programs from a sequential specification, a hierarchical mapping solution can target different runtimes relying on event-driven tasks (EDTs). The solution uses loop types to encode short, transitive relations among EDTs that can be evaluated efficiently at runtime. Specifically, permutable loops translate immediately into conservative point-to-point synchronizations of distance one. A runtime-agnostic which can be used to target the transformed code to different runtimes.

First claim

Accordingly, we claim:

1. A processor-implemented method of specifying relocatable event-driven tasks (EDTs) for a dynamic adaptive EDT-based runtime, the method comprising:
for an EDT structure corresponding to a loop structure in code to be executed using the EDT-based runtime, determining, by the processor, one or more dependencies between a pair of EDT instances, a first EDT instance corresponding to a first node of the EDT structure and a second EDT instance corresponding to a second node of the EDT structure or a third node of another different EDT structure, and the determination of the dependencies being based on, at least: (i) a type of the loop structure, and (ii) a union of respective individual iteration domains of one or more statements from the loop structure that are associated with the first and second EDT instances, each iteration domain comprising a respective ordered set of iterations
generating code for the specified dynamic adaptive EDT-based runtime based on the determined dependencies;
retargeting, by the processor, the code to the specified dynamic adaptive EDT-based runtime;
spawning, in the specified dynamic adaptive EDT-based runtime, tasks facilitated by the code; and
executing the tasks by one or more workers within the specified dynamic adaptive EDT-based runtime.

2. The method of claim 1 , wherein the EDT-based runtime comprises at least one of SWARM, OCR, and CnC.

3. The method of claim 1 , wherein the EDT structure comprises a tuple comprising: (a) a unique identifier, and (b) start and stop levels associated with the corresponding loop structure.

4. The method of claim 3 , wherein:
the code comprises a loop nest, and the loop nest comprises the loop structure corresponding to the EDT structure and another loop structure corresponding to a different EDT structure; and
the start level corresponds to a depth of the other loop structure, and the stop level corresponds to a depth of the loop structure corresponding to the EDT structure.

5. The method of claim 3 , wherein:
the code comprises a loop nest, and the loop nest comprises the loop structure corresponding to the EDT structure; and
the stop level corresponds to a depth of the loop structure corresponding to the EDT structure.

6. The method of claim 3 , wherein determination of a dependency within the one or more dependencies is further based on the start and stop levels in the tuple.

7. The method of claim 1 , further comprising generating the union of respective individual iteration domains of the one or more statements associated with the loop structure.

8. The method of claim 1 , further comprising:
synthesizing by the processor an EDT-instance generation statement causing the EDT-based runtime to spawn a plurality of EDT instances, all instances corresponding to the EDT structure.

9. The method of claim 1 , further comprising synthesizing at least one dependency statement specifying at least one of the one or more dependencies, if the at least one dependency is determined to exist between the pair of instances.

10. The method of claim 9 , wherein:
the type of the loop structure corresponding to the EDT structure is sequential; and the at least one dependency statement comprises a first dependency statement and a second dependency statement, wherein:
the first dependency statement causes a dummy task to wait for completion of all operations that correspond to the one or more statements associated with the loop structure and that are designated to a first EDT instance of the pair; and
the second dependency statement causes all operations that correspond to the one or more statements associated with the loop structure and that are designated to a second EDT instance of the pair to wait for completion of the dummy task.

11. The method of claim 9 , wherein:
the type of the loop structure corresponding to the EDT structure is a permutable, the loop structure comprising an n 1 d-dimensional loop nest comprising n d permutable loops;
at least one antecedent instance in each of the n d dimensions, and at least one subsequence instance are associated with the EDT structure; and
the dependency statement causes operations designated to the subsequent instance to wait for completion of all operations that are designated to at most one antecedent instance in each of one or more of the n d dimensions.

12. The method of claim 9 , wherein:
the second instance corresponds to the other different EDT structure, having associated therewith another different loop structure;
the union of respective iteration domains further comprises respective iteration domains of one or more statements associated with the other loop structure; and
the at least one dependency statement causes a task associated with the first instance to wait for completion of at least one operation that correspond to the one or more statements associated with the other loop structure and that is designated to the second EDT instance.

13. The method of claim 9 , wherein synthesis of the at least one dependency statement comprises deriving by the processor a templated task tag comprising a tuple comprising: (a) a unique identifier, and (b) start and stop levels associated with the corresponding loop structure.

14. The method of claim 13 , wherein the derivation of the templated task tag comprises:
computing a number of dimensions (n d ) of loops causing iteration of statements associated with the loop structure corresponding to the EDT structure; and
generating a statement for computing a number of iterations based on respective bounds of a loop in each dimension.

15. The method of claim 1 , further comprising:
marking by the processor, one or more loop nodes in a tree of nested loops representing loops in the code, based on at least one of: (i) a type of the loop, (ii) a position of the loop within the tree of nested loops, and (iii) user specification.

16. The method of claim 15 , wherein the type of the loop is sequential.

17. The method of claim 15 , wherein the position of the loop within the tree of nested loops comprises one of: (i) a loop at tile granularity, and (ii) a loop having a sibling in the tree of nested loops.

18. The method of claim 15 , wherein:
the type of the loop is permutable; and
a parent of the loop is within a different band; and
the parent is unmarked.

19. The method of claim 15 , further comprising:
constructing by the processor a tree of EDT structures comprising the EDT structure, each node in the tree of EDT structures representing a different EDT structure corresponding to a respective marked loop node in the tree of nested loops.

20. The method of claim 15 , further comprising:
constructing, by the processor, the tree of nested loops representing loops in the code, each loop node in the tree of nested loops corresponding to a different loop in the code. code.

21. The method of claim 20 , further comprising transforming loops in the code.

22. The method of claim 20 , further comprising tiling loops in the code.

23. The method of claim 1 , further comprising designating the EDT structure as a parent EDT structure and extracting by the processor from the parent EDT structure a child-EDT structure, the child-EDT structure being associated with a child loop structure that excludes at least one loop from the loop structure associated with the parent EDT structure, wherein:
the first instance of pair of instances corresponds to the child-EDT structure; a

Assignees

• Qualcomm Technologies Inc
• Qualcomm Inc

Inventors

• Baskaran Muthu M
• Henretty Thomas
• Langston M H
• Lethin Richard A
• Meister Benoit J
• Vasilache Nicolas T
• Wohlford David E

Classifications

• G06F9/4843 Primary

  by program, e.g. task dispatcher, supervisor, operating system · CPC title

• G06F8/45 Primary

  Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions · CPC title