Graph Lowering Implementation

Graph Lowering traverses operators in a graph and calls the lowering function of each operator in sequence. If an operator does not have a lowering function, the default lowering function is executed.

The following is an example of the operator lowering function prototype. After an operator node in a GE graph is input, the function returns whether the lowering is successful, completes the scalar expression of the node internally, and stores the result in the attribute.

ge::graphStatus(const NodePtr &node);

Graph Lowering consists of three steps:

Call the lowering function of each node in sequence to obtain the corresponding loop expression.
Derive the index and range in the loop expression to express the view class in the intermediate process to the movement mode of the input data.
Generate an AscGraph of a set of axes based on the index and range information derived from the loop expression.

After the lowering function of a node is called, the node type is not immediately converted into the AscBackend fusion node type. Instead, each output tensor of the node is associated with a KernelBox object. KernelBox is used to express the computation process of the output tensor of an operator. The core part is defined as follows:

class KernelBox {
  public:
   bool IsExternKernel() const; // Whether the type is Extern (that is, the original GE IR is required for implementation). If the value is true, the original GE IR is used for implementation.
    // Process the behavior of loading an element from the KernelBox. For the KernelBox of the Extern or Realize type, data is directly loaded from the output anchor. For the KernelBox that can be further fused, the internal computation process is returned.
   LoopVar Load() const;
   // Perform the Realize operation, that is, generate an AscBackend node for the KernelBox. If the value is true, fusion is allowed.
   void Realize(bool persistent = true); 
 };

Single Output and Multiple References

For an operator with a single output and multiple references, the loading modes of the output may be different for multiple computations. Graph Lowering performs lowering based on recomputation. That is, for a node that can be further fused, if its output is used by multiple nodes, for example, for the first Abs in the following example, the KernelBox corresponding to each node that uses the output contains the computation of the first Abs. Recomputation can be used in the scenario where the same data is transferred in different modes.

Common Subexpression Elimination (CSE) is a common optimization technology used in compiler optimization, code generation, and mathematical computation. Its core objective is to identify and reuse duplicate subexpressions in expressions to reduce redundant computation and improve efficiency.

Figure 1 Single-output and multi-reference process

Fusion and Fusion Termination Policies

The following describes the current fusion scope control policies for determining whether to perform fusion and terminate fusion during lowering.

The type of KernelBox is Reduction.
The total number of Loop nodes in KernelBox exceeds the threshold of 64.
The number of Load nodes in KernelBox exceeds the threshold of 4.
KernelBox is used as the input of a node on which lowering cannot be performed (triggered in the default lowering function).
The node to which KernelBox belongs contains input or output control edges (accurate control information for cross-node fusion will be lost).
The stream label of the node to which KernelBox belongs is inconsistent with that of the node using KernelBox as the input. (If either of them is not marked, they are considered to be consistent.)
The Realize operation is performed immediately when the Exp operator is encountered.
Operators with different cores in the core control scope are not fused to the same fused operator.
Inputs that are not used are realized in advance. For example, Zeroslike.
If the operator has the _super_kernel_scope attribute, fusion is skipped.
If the operator has the _disable_autofuse_scope attribute, lowering is skipped.
The actual attribute is inconsistent with the operator IR.
If the dtype verification of the operator is not supported, fusion is skipped.
Fusion is skipped for pure scalar graphs (limited to a single Ascbackend).

For operators that do not support lowering, the default lowering implementation is called. The default lowering function is used to complete the following two actions:

Realize the KernelBox corresponding to all input anchors and terminate fusion.
Set the KernelBox corresponding to the output anchor of the node to the KernelBox of the ExternKernel type.

Currently, the default lowering implementation is used in the following three scenarios, and the processing methods are the same:

The node cannot be expressed by lowering.
The node can be expressed by lowering, but the expression is not implemented.
The node can be expressed by lowering and the expression has been implemented. However, the expression result is invalid because there is no unsigned inference result.

When writing the lowering implementation for a node, you do not need to consider whether there is a symbolic result because the check is performed by the loop function. Regardless of the specific situation, the KernelBox after lowering is consistent and is of the ExternKernel type.

Fusion Rollback Policies

Rollback refers to how to roll back the AscBackend fusion node to the original node for execution when the performance of the generated AscBackend fusion node is lower than that of the original node in the lowering phase because the specific CanFuse/Schedule/Codegen capability is not perceived. The current rollback policies are as follows:

If the number of original GE IR nodes corresponding to the AscBackend fusion node is less than the threshold (the current threshold is 2), the AscBackend fusion node is rolled back to the original node for execution.

Parent topic: Lowering