com.nicta.scoobi.impl.plan.comp
Optimiser
add a map to output values to non-filled sink nodes if there are some
collect all the sinks in the computation graph
collect all the sinks in the computation graph
all the strategies to apply, in sequence
compute the children of a node.
compute the children of a node.
This is similar to calling the initTree method on the node but this stores the information as an attribute instead of storing it as a tree. This is a way to avoid conflicts if we have 2 processes trying to initialise the same graph
Combine nodes which are not the output of a GroupByKey must be transformed to a ParallelDo
compute all the descendents of a node They are all the recursive children reachable from this node
compute all the descendents of a node They are all the recursive children reachable from this node
duplicate the whole graph by copying all nodes
this attribute stores the fact that a Sink has received data
this attribute stores the fact that a Sink has received data
true if a given Sink has already received data
initialise the parent/child relationship recursively from node s
initialise the parent/child relationship recursively from node s
compute the inputs of a given node For a ParallelDo node this does not consider its environment
compute the inputs of a given node For a ParallelDo node this does not consider its environment
return true if a CompNode has a cycle in its graph, this will be detected by Kiama throwing an exception when fetching the descendents of a node
return true if a CompNode has a cycle in its graph, this will be detected by Kiama throwing an exception when fetching the descendents of a node
true if a node is used at most once
true if a node is used at most once
mark a sink as filled so it doesn't have to be recomputed
mark a sink as filled so it doesn't have to be recomputed
true if this parallelDo must be read ==> can't be fused
true if a process node has been filled
Optimise a set of CompNodes, starting from the set of outputs
Nested ParallelDos must be fused but only if pd1 is not used anywhere else.
Nested ParallelDos must be fused but only if pd1 is not used anywhere else.
We use somebu to fuse the nodes "bottom-up" starting from all leaves of the tree at the same time
pd1 @ ParallelDo | pd2 @ ParallelDo
This rule is repeated until nothing can be fused anymore
compute the parent of a node.
compute the parent of a node. This relationship is actually maintained while getting the children of a node if the parent node has not been set while recursing for children, then it is None
compute the parents of a node, that is all the chain of parents from this node up to the root of the graph
compute the parents of a node, that is all the chain of parents from this node up to the root of the graph
reinitialise all the attributes related to a node, starting from all the parent/children relationships
reinitialise all the attributes related to a node, starting from all the parent/children relationships
reset the attributes, then recreate the parent/children relationships recursively
apply a traversal strategy but make sure that:
apply a traversal strategy but make sure that:
- after each pass the tree is reset in terms of attributable relationships and uses - the strategy to execute is memoised, i.e. if a node has already been processed its result must be reused this ensures that rewritten shared nodes are not duplicated
reinit usages
reinit usages
the root of the graph, computed from a given node
the root of the graph, computed from a given node
compute all the indirect uses of a given node, that is all the nodes which have this node as a descendent
compute all the indirect uses of a given node, that is all the nodes which have this node as a descendent
remove nodes from the tree based on a predicate
the nodes which have this node as a direct child
the nodes which have this node as a direct child
for efficiency, this uses a table of all the nodes using a given one, computed from the root
compute all the nodes which use a given node as an environment
compute all the nodes which use a given node as an environment
Optimiser for the CompNode graph
It uses the [Kiama](http://code.google.com/p/kiama) rewriting library by defining Strategies for traversing the graph and rules to rewrite it. Usually the rules are applied in a top-down fashion at every node where they can be applied (using the
everywherestrategy).