Loop - 1 vs 11

Files changed (1) hide show
  1. Loop1 → Loop11 +43 -23
Loop1 → Loop11 RENAMED
@@ -1 +1 @@
1
1
  Generic Looping construct. This loop has multiple termination conditions:
2
2
  1) Trip count. Iteration count specified at runtime. Set by
3
3
  specifying the input M. Optional. Set to empty string to omit.
4
4
  Note that a static trip count (specified at graph construction time) can be
5
5
  specified by passing in a constant node for input M.
6
6
  2) Loop termination condition. This is an input to the op that determines
7
7
  whether to run the first iteration and also a loop-carried dependency for
8
8
  the body graph. The body graph must yield a value for the condition variable,
9
9
  whether this input is provided or not.
10
10
  This table summarizes the operating modes of this operator with equivalent
11
11
  C-style code:
12
12
  Operator inputs defined as (max_trip_count, condition_var).
13
13
  input ("", ""):
14
14
  for (int i=0; ; ++i) {
15
15
  cond = ... // Note this value is ignored, but is required in the body
16
16
  }
17
17
  input ("", cond) // Note this is analogous to a while loop
18
18
  bool cond = ...;
19
19
  for (int i=0; cond; ++i) {
20
20
  cond = ...;
21
21
  }
22
22
  input ("", 1) // Note this is analogous to a do-while loop
23
23
  bool cond = true
24
24
  for (int i=0; cond; ++i) {
25
25
  cond = ...;
26
26
  }
27
27
  input (trip_count, "") // Note this is analogous to a for loop
28
28
  int trip_count = ...
29
29
  for (int i=0; i < trip_count; ++i) {
30
30
  cond = ...; // ignored
31
31
  }
32
32
  input (trip_count, cond)
33
33
  int trip_count = ...;
34
34
  bool cond = ...;
35
35
  for (int i=0; i < trip_count && cond; ++i) {
36
36
  cond = ...;
37
37
  }
38
38
  *Sample usage - cond as well as trip count*
39
39
  graph predict-net {
40
40
  %a = Constant[value = <Scalar Tensor [3]>]()
41
41
  %b = Constant[value = <Scalar Tensor [6]>]()
42
42
  %keepgoing = Constant[value = <Scalar Tensor [1]>]()
43
43
  %max_trip_count = Constant[value = <Scalar Tensor [10]>]()
44
44
  %keepgoing_out, %b_out, %user_defined_vals = Loop[body = <graph body-net>](%max_trip_count, %keepgoing, %b)
45
45
  return
46
46
  }
47
47
  graph body-net (
48
- %i[INT32, scalar]
48
+ %i[INT32, scalar] // iteration number
49
- %keepgoing[BOOL, scalar]
49
+ %keepgoing_in[BOOL, scalar] // incoming loop-termination-condition; not used
50
- %b[INT32, scalar]
50
+ %b_in[INT32, scalar] // incoming value of loop-carried-dependency b
51
51
  ) {
52
- %my_local = Add(%a, %b)
52
+ %my_local = Add(%a, %b_in)
53
- %b_out = Sub(%a, %b)
53
+ %b_out = Sub(%a, %b_in) // outgoing value of loop-carried-dependency b
54
- %keepgoing_out = Greater(%my_local, %b_out)
54
+ %keepgoing_out = Greater(%my_local, %b_out) // outgoing loop-termination-condition
55
- %user_defined_vals = Add(%b, %b)
55
+ %user_defined_val = Add(%b_in, %b_in) // scan-output value to be accumulated
56
- return %keepgoing_out, %b_out, %user_defined_vals
56
+ return %keepgoing_out, %b_out, %user_defined_val
57
57
  }
58
58
  *Sample equivalent C code*
59
59
  {
60
60
  /* User-defined code (enclosing scope) */
61
61
  int a = 3, b = 6;
62
62
  bool keepgoing = true; // Analogous to input cond
63
63
  /* End user-defined code */
64
64
  /* Implicitly-defined code */
65
65
  const int max_trip_count = 10; // Analogous to input M
66
66
  int user_defined_vals[]; // Imagine this is resizable
67
67
  /* End implicitly-defined code */
68
+ /* initialize loop-carried variables and scan-output variables */
69
+ bool keepgoing_out = keepgoing
70
+ int b_out = b
71
+
68
- for (int i=0; i < max_trip_count && keepgoing; ++i) {
72
+ for (int i=0; i < max_trip_count && keepgoing_out; ++i) {
73
+ /* Implicitly-defined code: bind actual parameter values
74
+ to formal parameter variables of loop-body */
75
+ bool keepgoing_in = keepgoing_out;
76
+ bool b_in = b_out;
77
+
69
78
  /* User-defined code (loop body) */
70
- int my_local = a + b; // Reading values in the enclosing scope is fine
79
+ int my_local = a + b_in; // Reading value "a" from the enclosing scope is fine
80
+ b_out = a - b_in;
71
- b = a - b; // writes fine if we specify b as a loop-carried dependency
81
+ keepgoing_out = my_local > b_out;
72
- keepgoing = my_local > b; // keepgoing is a loop-carried dependency
82
+ user_defined_val = b_in + b_in; // b_in and b_out are different variables
73
- user_defined_vals[i] = b + b;
74
83
  /* End user-defined code */
84
+
85
+ /* Implicitly defined-code */
86
+ user_defined_vals[i] = user_defined_val // accumulate scan-output values
75
87
  }
76
- // my_local = 123; // Can't do this. my_local was defined in the body
88
+ // int t = my_local; // Can't do this. my_local is not accessible here.
77
- // These below values are live-out from the loop and therefore accessible
89
+ // The values below are bound to the output variables of the loop and therefore accessible
78
- b_out; user_defined_vals; keepgoing_out;
90
+ // b_out; user_defined_vals; keepgoing_out;
79
91
  }
80
92
  There are several things of note in this code snippet:
81
- 1) Values from the enclosing scope (i.e. variable a here) are in scope and can
93
+ 1) Values from the enclosing scope (i.e. variable "a" here) are in scope and can
82
94
  be referenced in the inputs of the loop.
83
- 2) Any variables which you wish to make available in the enclosing scope (i.e.
95
+ 2) Any values computed in the loop body that needs to be used in a subsequent
96
+ iteration or after the loop are modelled using a pair of variables in the loop-body,
97
+ consisting of an input variable (eg., b_in) and an output variable (eg., b_out).
84
- the variables b and keepgoing) must be declared as either loop-carried
98
+ These are referred to as loop-carried dependences. The loop operation node
85
- dependencies (both at the op inputs and output and at the body net input and
99
+ supplies the input value of the input variable for the first iteration, and
100
+ returns the output value of the output variable produced by the final
101
+ iteration.
102
+ 3) Scan_output variables are used to implicitly concatenate values computed across
103
+ all the iterations. In the above example, the value of user_defined_val computed
104
+ over all iterations are concatenated and returned as the value of user_defined_vals
86
- output) or scan_outputs.
105
+ after the loop.
87
- 3) Values created in the body cannot be accessed in the enclosing scope.
106
+ 4) Values created in the body cannot be accessed in the enclosing scope,
107
+ except using the mechanism described above.
88
108
  Note that the semantics of this op support "diagonal" or "wavefront" execution.
89
109
  (See Step 3 here for an example:
90
110
  https://devblogs.nvidia.com/optimizing-recurrent-neural-networks-cudnn-5/).
91
111
  Frontends should emit multi-layer RNNs as a series of While operators (with
92
112
  time being the inner looping dimension), with each successive layer consuming
93
113
  the scan_outputs from the previous layer, possibly going through several
94
114
  point-wise operators (e.g. dropout, residual connections, linear layer).
95
115
  **Attributes**
96
116
  * **body** (required):
97
117
  The graph run each iteration. It has 2+N inputs: (iteration_num,
98
118
  condition, loop carried dependencies...). It has 1+N+K outputs:
99
119
  (condition, loop carried dependencies..., scan_outputs...). Each
100
120
  scan_output is created by concatenating the value of the specified
101
121
  output value at the end of each iteration of the loop. It is an
102
122
  error if the dimensions or data type of these scan_outputs change
103
123
  across loop iterations.
104
124
  **Inputs**
105
- Between 3 and 2147483647 inputs.
125
+ Between 2 and 2147483647 inputs.
106
126
  * **M** (optional, heterogeneous) - **I**:
107
127
  A maximum trip-count for the loop specified at runtime. Optional.
108
128
  Pass empty string to skip.
109
129
  * **cond** (optional, heterogeneous) - **B**:
110
130
  A boolean termination condition. Optional. Pass empty string to
111
131
  skip.
112
132
  * **v_initial** (variadic) - **V**:
113
133
  The initial values of any loop-carried dependencies (values that
114
134
  change across loop iterations)
115
135
  **Outputs**
116
136
  Between 1 and 2147483647 outputs.
117
137
  * **v_final_and_scan_outputs** (variadic) - **V**:
118
138
  Final N loop carried dependency values then K scan_outputs
119
139
  **Type Constraints**
120
140
  * **V** in (
121
141
  tensor(bool),
122
142
  tensor(complex128),
123
143
  tensor(complex64),
124
144
  tensor(double),
125
145
  tensor(float),
126
146
  tensor(float16),
127
147
  tensor(int16),
128
148
  tensor(int32),
129
149
  tensor(int64),
130
150
  tensor(int8),
131
151
  tensor(string),
132
152
  tensor(uint16),
133
153
  tensor(uint32),
134
154
  tensor(uint64),
135
155
  tensor(uint8)
136
156
  ):
137
157
  All Tensor types
138
158
  * **I** in (
139
159
  tensor(int64)
140
160
  ):
141
161
  tensor of int64, which should be a scalar.
142
162
  * **B** in (
143
163
  tensor(bool)
144
164
  ):
145
165
  tensor of bool, which should be a scalar.