hyped.core.optim module¶

Module for Data Flow Graph Optimization.

This module provides an optimizer for data flow graphs, which applies various optimization techniques to improve program efficiency and reduce redundant computations.

The optimizer module includes methods for optimizing data flow graphs, such as:

Prune Redundant Nodes: The optimizer prunes the data flow graph, removing nodes that do not contribute to producing the desired output.
Constant Expression Evaluation: Pre-computes the constant partition of the graph, which consists solely of constant values and has no dependencies on other parts of the graph, and replaces these constants with their computed values.
Common Subexpression Elimination (CSE): Identifies and eliminates redundant computations by recognizing and reusing common subexpressions in the data flow graph.
Constant Folding/Propagation: Evaluates constant expressions at compile time and replaces them with their computed values to simplify the data flow graph.

The DataFlowGraphOptimizer class within this module provides these optimization methods, which can be applied individually or in combination to optimize a given data flow graph.

class hyped.core.optim.DataFlowGraphOptimizer[source]¶

Bases: object

Optimizer for Data Flow Graphs.

This optimizer applies several optimization techniques to the given data flow graph in order to improve its efficiency and reduce redundant computations. The optimization steps include:

Prune Unnecessary Nodes
Constant Expressions Evaluation
Common Subexpression Elimination (CSE)
Constant Folding/Propagation

Note the difference between constant expression evaluation and constant folding. Constant expression evaluation focuses on evaluating the constant partition of the graph, which consists solely of constant values and has no dependencies on other parts of the graph. In contrast, constant folding aims to simplify expressions that include both constant and non-constant values by precomputing the constant parts of these expressions.

apply_accessed_fields(graph: DataFlowGraph) → None[source]¶

Restrict the source feature type to only the accessed fields.

This function retrieves the portion of the source node’s data type that is explicitly accessed or utilized within the data flow graph. It represents the subset of features or fields from the source data type that are directly referenced by downstream nodes in the graph. Any features in the source data type that are not accessed remain excluded from this subset.

The source feature of the data flow graph is updated to the accessed sub-feature.

Parameters:: graph (DataFlowGraph) – The data flow graph to be optimized.

constant_evaluation(graph: DataFlowGraph, leaf_nodes: set[str]) → DataFlowGraph[source]¶

Pre-computes the constant partition of the data flow graph.

This method evaluates the constant partition of the data flow graph, which is self-contained and has no outside dependencies. It creates a new graph from this partition, collects all outputs, and executes them using a data flow executor. The evaluated constants are then re-inserted into the main graph with their computed values.

Consider the following example:

x, y = 1, 2
z = x + y

After applying constant evaluation, the above is expression is precomputed to

z = 3

Parameters:

graph (DataFlowGraph) – The data flow graph to be optimized.
leaf_nodes (set[NodeId]) – The leaf nodes, ensured to be present in the optimized graph.

Returns:

The optimized data flow graph with evaluated constants.

Return type:

DataFlowGraph

constant_folding(graph: DataFlowGraph) → DataFlowGraph[source]¶

Performs constant folding optimization on the data flow graph.

Constant folding is an optimization technique used to evaluate constant expressions at compile time and replace them with their computed values. This method traverses the data flow graph and identifies expressions involving constants that can be evaluated statically. It then replaces these expressions with their computed values, eliminating redundant computations and simplifying the graph.

Consider the following example:

z = x + (-y)

After applying constant folding optimization, the expression is simpified to

z = x - y

Parameters:: graph (DataFlowGraph) – The data flow graph to be optimized.
Returns:: The optimized data flow graph after constant folding.
Return type:: DataFlowGraph

cse(graph: DataFlowGraph) → tuple[DataFlowGraph, dict[str, str]][source]¶

Performs Common Subexpression Elimination (CSE) on the data flow graph.

This method performs Common Subexpression Elimination (CSE) on the given data flow graph. It optimizes the graph by identifying and eliminating redundant computations.

Consider the following data flow graph:

x = a + b
y = c * d
z = a + b

After applying Common Subexpression Elimination (CSE), the redundant computation a + b is eliminated, resulting in the following optimized graph:

x = a + b
y = c * d
z = x

The node IDs before and after optimization are mapped as follows: {0: 0, 1: 1, 2: 0}

Parameters:

graph (DataFlowGraph) – The data flow graph.

Returns:

The optimized data flow graph and a mapping: of node IDs before and after optimization.

Return type:

DataFlowGraph, dict[NodeId, NodeId]]

optimize(graph: DataFlowGraph, leaf_nodes: set[str]) → DataFlowGraph[source]¶

Optimizes the data flow graph for a specified set of leaf nodes.

Parameters:

graph (DataFlowGraph) – The data flow graph.
leaf_nodes (set[NodeId]) – Set of leaf node IDs.

Returns:

The optimized data flow graph.

Return type:

DataFlowGraph

Raises:

AssertionError – If not all leaf nodes are contained in the optimized graph.