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

Patent metadata

Field	Value
Publication number	US-10564949-B2
Application number	US-201414492899-A
Country	US
Kind code	B2
Filing date	Sep 22, 2014
Priority date	Sep 20, 2013
Publication date	Feb 18, 2020
Grant date	Feb 18, 2020

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 method of specifying event-driven tasks (EDTs) for an EDT-based runtime system comprising a plurality of processing units, the method comprising:
for an EDT structure corresponding to a loop structure in code to be executed using an EDT-based runtime system, determining by a compiler executed on a processor a dependency relation expressing one or more dependencies between a pair of EDT instances, wherein:
a first EDT instance and a second EDT instance in the pair is to be executed using the plurality of processing units of the runtime system,
the first EDT instance corresponds to a first node of the EDT structure and the second EDT instance corresponds to a second node of the EDT structure or a node of another different EDT structure,
the one or more dependencies cause an operation associated with the second instance to wait for completion of an operation associated with the first instance,
the determination of the dependency relation is 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 multi-dimensional set of iterations, and
the dependency relation enables the runtime system to determine the one or more dependencies between the first and second EDT instances during execution of EDTs associated with the EDT structure, without needing evaluation of dependences via a loop nest resulting from a projection operation and, instead, via the type of the loop structure and the union of the iteration domains.

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 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, a 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.

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 structure as a parent

Assignees

• Reservoir Labs Inc

Inventors

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

Classifications

• G06F2209/5017

  Task decomposition · CPC title

• G06F8/452 Primary

  Loops · CPC title

• G06F2209/483

  Multiproc · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title