Guard Mechanism and Principles

Background

In the current framework, the dynamic dimension in the input and output shapes of an operator is usually represented by -1. However, only limited information can be expressed using this method. In this context, symbols (such as s0 and s1) are used to represent unknown dimensions. Compared with -1, these symbols can express more information. As shown in the following figure, after the input shapes of Data0, Data1, and Data2 are symbolized, the output shape of Add can also be expressed by symbols. In this way, the output shape of the next node Mul can be computed. Compared with shape -1, the output shape of Mul can express more information.

Figure 1 Symbolization example

However, the current symbolic expression may encounter problems in the following two scenarios:

• Symbolic shapes to be verified by Assert

  During symbol inference of some operators, strict verification is required for some dimensions. For example, in the following figure, the input symbol s1 of the Matmul operator must be equal to s2. If they are not equal, undefined behavior (such as out-of-bounds or error reporting) occurs during the execution of the Matmul operator.

  Figure 2 Symbolic shape to be verified by Assert
  
• Broadcast scenario

  Broadcast is required for the computation of some operators (such as Add and Mul). Below is an example.

  Figure 3 Broadcast scenario
  

  In this scenario, s1 and s3 are symbols. The magnitude relationship between s1 and s3 cannot be determined during symbolic inference. In addition, broadcast is supported only in the following three cases. In addition, the specific branch to be executed cannot be determined during compilation. If the branch conditions are not met during execution, undefined behavior (such as out-of-bounds or error reporting) may occur.

  

To cope with the preceding two problems, the concept of Guard is introduced. The guard mechanism is used to express the direct relationships between symbols. For example, in the preceding broadcast scenario, the symbol relationship expression s1 == s3 can be used to indicate that the current broadcast path is s1 == s3. Subsequent symbol inference is performed based on this path. During execution, if the value of the symbol does not meet the s1==s3 condition, the current model compilation result cannot be directly used. In this case, you need to recompile the model. This is one of the application scenarios of Guard.

Hint Value

Before learning the guard principles, you need to understand what is a hint value. The hint value is passed by a user during online execution. Generally, the hint value is the input shape (the shape is known) passed by the user during the current iteration execution. The following figure shows an example.

Figure 4 Hint value diagram

Certain dimensions of Data0, Data1, and Data2 in a model are unknown. However, during iteration execution, a user passes the input tensor with static shapes. These shapes can be used as references for symbol guard during build. For example, for the build of the preceding graph, the shape of Data0 is [2, 3, 4, 2], the shape of Data1 i s [2, 3, 1, 2], and the shape of Data2 is [2, 3, 1, 2]. During model compilation, the hint value of s0 is 2, the hint value of s1 is 3, the hint value of s2 is 4, the hint value of s3 is 2, and the hint value of s4 is 1. Generally, each symbol has a hint value, and the guard mechanism is implemented based on these hint values. Guard is classified into expect_guard and assert_guard depending on functions.

• expect_guard: indicates the relationship that symbols must meet for the model to be executed. It is mainly used for branch verification. If the conditions for the guard are not met, model recompilation is triggered.
• assert_guard: indicates the strict verification of symbols. If the symbols do not meet the conditions for the guard, the model cannot be executed although it is recompiled. As a result, the process is interrupted and an error is reported.

Basic Principles of Guard

The guard mechanism is implemented based on the symbol relationship expression (for example, s0 == s1), which is used to express the magnitude relationship between two symbol operation expressions. The guard mechanism is implemented at the graph level. Once such a guard is generated during graph build, the input symbol value must meet the expression when the graph build result is executed. Otherwise, the execution fails.

1. Guard generation

   The preceding hint values are required for the generation. The values of symbols are unknown and cannot be directly compared. Each symbol has a hint value. During build, if you need to determine whether a symbol relationship expression is valid, you can use the hint value for computation. For example:

   If you want to verify whether s0 + s1 is equal to s2, you can substitute the hint values into the expression, instead of comparing them directly. For example, if the hint value of s0 is 2, the hint value of s1 is 3, and the hint value of s2 is 5, s0 + s1 is equal to s2, and the guard of s0 + s1 == s2 can be generated. On the contrary, if the hint value of s0 changes to 3, s0 + s1 is not equal to s2, and the guard of s0 + s1 != s2 needs to be generated. These guards will be stored in the build results of a graph, and their lifecycle is consistent with that of the graph.

2. Methods of using the generated guard in the execution phase

   Assume that a guard of s0 + s1 == s2 is generated in the build phase. Note that the guard is generated based on the iteration input value during build. In this case, if the model uses a dynamic shape, the symbol value will change in subsequent iterations. For example, the model (with the input Data0:-1,-1; Data1:-1,-1) is executed. After the input shape of the model is symbolized, it becomes Data0:s0,s1; Data1:s2,s3. If the model is executed online:

   1. Step 0: Alignment is required for graph build. The execution input shape is Data0:2,3; Data1:5,2. For graph build, the hint value of s0 is 2, the hint value of s1 is 3, the hint value of s2 is 5, and the hint value of s3 is 2. In this case, in the build state, a guard of s0 + s1 == s2 is generated based on the symbol hint value of the current step, and is stored in the graph build result.
   2. Step 1: If the execution input shape remains unchanged, the guard generated in step 0 can pass the verification, and the graph build result of step 0 can be directly executed.
   3. Step 2: Assume that the input shape changes to Data0:3,4; Data1:7,2. In this case, the symbol value of s0 changes to 3, that of s1 changes to 4, and that of s2 changes to 7. Although the symbol values change, the guard of s0 + s1 == s2 still holds true. Therefore, the graph build result of step 0 can still be directly executed.
   4. Step 3: Assume that the input shape changes to Data0:5,4; Data1:7,2. In this case, the symbol value of s0 changes to 5, and the guard of s0 + s1 == s2 is false, which means that the guard conditions are not met. Therefore, the graph build result of step 0 cannot be used. The model needs to be recompiled based on the input value of the current step.

Guard Application Scenarios

After understanding what a guard is, when do you need one?

• Broadcast scenario

  The most common application scenario of the guard mechanism is broadcast. Whether broadcast needs to be performed cannot be determined based on the symbol itself. To address this, the guard function is provided. The following uses the Add operator as an example.

  Figure 5 Guard application scenario 1
  

  The output of the current Add operation may be as follows:

  • When s0 == s1, the output shape of the Add operator is [s0, 2].
  • When s0 == 1, the output shape of the Add operator is [s1, 2] (the dimension of 1 needs to be broadcast).
  • When s1 == 1, the output shape of the Add operator is [s0, 2].

  Therefore, a guard can be generated based on the hint values of s0 and s1, and the generated guard can be used to determine the output shape of the Add operator. For example:

  • If the hint values of s0 and s1 are both 2, the Add operator's symbol inference function needs to generate an expect_guard of s0 == s1, and the output shape is [s0, 2].
  • When the hint value of s0 is 1 and that of s1 is 2, the symbol inference function of the Add operator needs to generate an expect_guard of s0==1, and the output shape of the Add operator is [s1, 2].
  • When the hint value of s0 is 2 and that of s1 is 1, the symbol inference function of the Add operator needs to generate an expect_guard of s1==1, and the output shape of the Add operator is [s0, 2].

  In addition, if the input shape changes during subsequent iteration execution, the current guard is not met, and the model needs to be recompiled.

• Strict shape verification

  For certain operators, there are constraints on the input shapes. In this case, assert_guard is required. For example, the Matmul operator in the following figure requires that the first dimension of the 0th input be equal to the 0th dimension of the first input. Otherwise, the operator cannot perform computation. Therefore, the input symbol s1 must be equal to s2. In the build phase, the assert_guard of s1==s2 is generated based on the hint values of s1 and s2. If the hint values of s1 and s2 do not meet the guard conditions, the program reports an error and exits.

  Figure 6 Guard application scenario 2
  
• Exact division check

  In addition to the preceding two application scenarios, some operators, such as the Reshape operator, need to check whether the shapes support exact division. For example, in the following figure, the shape of one input of Reshape is [s0, s1], and the shape of the other input is [2] and the value of a const is [2, -1]. In this case, if the assert_guard (Mod(s0*s1,2) == 0) is met, the Reshape can be computed. If it is not met, the Reshape cannot be computed.

  Figure 7 Guard application scenario 3
  
• Boundary check

  The guard mechanism can also be used to control whether the symbol value of an operator can be kept within a certain range. For example, in the following figure, the input x of the Slice operator has a shape of [s0, s1], the offset value is [2], and the size value is 2. Because the offset value needs to be within the range of [0, s0], the assert_guard of 2 <= s0 needs to be generated.

  Figure 8 Guard application scenario 4
  

Guard Derivative Capabilities

After a guard is generated through symbol inference, the following additional functions can be provided based on the guard:

• Symbol simplification

  The preceding guard capabilities can help simplify symbols. For example, if there is a guard of s2==s0+s1, s0+s1 can be used to replace s2. In addition, the symbol equivalence and union-find set functions are supported. For example, if there are two guards (s2==s0+s1 and s0==2), s2 can be simplified to 2 + s1.

• StaticCheck function

  In the build phase, some symbols need to be statically compared based on the existing symbol guard relationship. Therefore, the StaticCheck function is provided for symbolization. The static_check API is called to:

  1. Check whether the relational expression is a constant expression. If it is, the judgment result is returned.
  2. If the expression is not a constant expression, it checks whether the guard exists. If it does, the guard result is returned. If it does not, false is returned.