-
Notifications
You must be signed in to change notification settings - Fork 0
AMT Data Structure
The complete data structure consists of a set of nested AMT nodes starting with the root node as well as some information regarding the global environment.
- root: A main mapping node defining the root node of the AMT
- GlobalVariableTable: The symbol table containing the global variables
- functionTable: The symbol table containing the function definitions spanning their individual sub-trees
- defaultDevice: The device targeted for sequential execution
- globalAssignments: A list of initialization expressions for the global variables
The mapping node is the basic node defining the information for most of the subsequent nodes. Depending on the data accesses all nodes can define a set of necessary data placements, which needs to be present before the node can be executed, and a set of output data placements, defining all the data places changed by this node.
- children: An ordered list of child nodes defining the children of this node. The order of these nodes defines the order of execution.
- parent: The mapping node containing this nodes as one of its children. Function nodes do not have a parent node, since they always define the root of a partial AMT.
- variableTable: A hashmap defining the symbol table for all variables accessible in this scope.
- inputElements: The set of data elements read within this node.
- outputElements: The set of data elements written to within this node.
- inputAccesses: A set of access patterns for the read accesses within this node.
- outputAccesses: A set of access patterns for the write accesses within this node.
A node defining a set of branches. All child nodes defined by this node are branch case mappings. No additional parameters are defined for this node.
A branch case mapping defines a single branch as part of the branch mapping.
- condition: An expression node defining the condition for entering this branch, if no condition is defined a pure else branch is defined.
A call mapping defines a function call within the AMT. They provide the key to access the corresponding function node. The input and output parameters for an individual function call are defined within the corresponding expression.
- parameterCount: The number of arguments defined for this function call.
- functionIdentifier: The name (key) of the function to be called.
- callExpression: A data element containing the partial expression only specifying the function call and its parameters.
- callCount: The number of times the visitor has passed this function call.
The complex expression mapping defines a single expression with potentially nested function calls. This nodes is always used when either only a single expression is applicable or the expression contains function call, spanning a sub-tree.
- expression: The expression defining this node.
The for each loop mapping defines a loop which iterates over all elements of a given array.
- loopControlVariable: The data element used to identify the current element of the loop iteration.
- generationRandomIndex: A random string used to avoid overloading of variable names for the generated code.
- parsedList: The array to be iterated over.
The for loop mapping defines a for loop within the computation.
- initExpression: The expression defining the first value of the loop iteration
- controlExpression: The expression defining the limit for the loop iteration
- updateExpression: The expression defining the update rule after each loop iteration
- loopControlVariable: The data element used to define the loop iteration
The jump label mapping defines a label for a corresponding jump statement to avoid side effects while inlining function calls.
- label: The label defining the goto statement. This label needs to be identical to at least one label defined within a jump statement.
The jump statement mapping can replace a return node from the APT, if the surrounding function node is inlined.
- closingVars: The data elements needing to be deallocated before leaving the function scope.
- resultExpression: The expression defined by the replaced return node within the APT.
- label: The label defining the jump destination.
- outputData: The data element saving the inlined result.
A return mapping defines the end of a function and the specification of the return value.
- result: An expression defining the result of the local computation.
The simple expression mapping defines a set of expression without any nested function calls. This node does not have any child nodes.
- expressionList: A list of expressions contained in this node.
The while loop mapping defines a computation which is performed as long as a given expression is fulfilled.
- condition: An complex expression node defining the expression which needs to hold before each iteration.
The main mapping is a unique function node within the AMT, which defines the root of the complete AMT. No additional parameters are necessary.
The definition of a sequential function is stored within a serial mapping.
- returnType: The data type of the function output
- isList: True, iff the function returns an array data structure
- shape: The number of elements contained within each dimension of the output. The shape of a function is defined by its output. For functions where the shape of the output depends on the input, please use parallel patterns to avoid certain implications.
Parallel Mappings define an abstract class covering the function nodes for all parallel patterns.
- returnElement: The return element defines the output data used within the parallel pattern.
The dynamic programming mapping specifies the definition of a dynamic programming recursion within the AMT.
- dimension: The dimensionality of the used data structure. Currently only a dimension of 2 is supported.
A map mapping defines a specific map pattern within the AMT. Its children define the computation necessary to define a single iteration of the map pattern. No further parameters are necessary.
A reduce mapping defines a specific reduction pattern within the AMT. Its children define the computation necessary to define a single iteration of the reduction pattern as well as the recombination of the result.
- combinerFunction: The operation used to recombine the partial results.
A recursion mapping defines a specific recursion within the AMT. Its descendants can contain this pattern the same node again. Therefore, it is necessary for the visitor to not fully traverse this node. No further parameters are necessary.
The stencil mapping defines a specific stencil pattern within the AMT. Its children define a single iteration of the inner most loop of the stencil pattern.
- dimension: The dimensionality of the stencil operation. This also corresponds to the number of nested loops in a regular implementation. E.g., a dimensionality of 1 is equivalent to the map pattern.
Parallel call nodes define the entrypoint for parallel patterns.
The parallel call mapping are the basic implementation of the parallel call node.
- startIndex: The first iteration for each of the dimensions.
- numIterations: The number of iterations for each of the dimensions.
- definition: A complex expression mapping defining the call expression
- executor: The target processor.
- numThreads: The number of threads used on the target processor.
- dynamicProgrammingBarrier: A barrier used to synchronize the DP iterations, iff the call node corresponds to a DP function.
- dynamicProgrammingTransfers: A set of data transfers necessary for each of the DP iterations.
- group: A group of parallel call nodes corresponding to the same original APT node.
The serialized parallel call mapping corresponds to a parallel call to be executed sequentially. This node extends the basic parallel call mapping and does not introduce additional parameters.
The reduction call mapping covers the definition of parallel reduction computations. This node is used to define the initial computation of the partial reduction, as well as the recombination of the partial results.
- isOnlyCombiner: True, iff the call is only used to recombine partial results.
- tempInput: The temporary partial results used for the recombination.
- tempOutput: The temporary partial results provided by the current computation.
- numBlocks: The number of GPU blocks when computing on a GPU.
- onGPU: True, iff the call should be computed on a GPU.
The GPU parallel call mapping is defined to compute on a GPU.
- numBlocks: The number of GPU blocks used for the computation.
- threadsPerBlock: The number of threads to be used for each GPU block.
The fused parallel call mapping defines a pipeline optimization. It only extends the mapping node and has a set of parallel calls as its children performing on the same target processor with the same number of threads. Due to the inherent data dependency between the children, synchronization between them is not necessary.
The barrier mapping defines the synchronization mechanism used for the AMT. The synchronization can be used by either specifying the target processors or a set of parallel groups.
- barrier: Set of parallel groups to be synchronized.
- barrierProc: A set of target processors to be synchronized.
- groupBased: True, iff the barrier is based on parallel groups.
The data movement mapping defines a data movement for a single data element.
- Sender: A set of data placement to send the data from.
- Receiver: A set of data placement to send the data to.