This shows you the differences between two versions of the page.
— |
reduction_tutorial [2017/04/19 13:31] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | =====Reduction Transformations===== | ||
+ | This tutorial covers transformations on reductions. | ||
+ | ====Simplifying Reductions==== | ||
+ | Simplifying Reductions takes a reduction and reuse vector as inputs. The reductions must be in a " | ||
+ | |||
+ | The command for simplifying reductions has the following signature: | ||
+ | SimplifyingReduction(program, | ||
+ | |||
+ | The following in an example, using an input alphabets where simplifying reductions is already applicable. | ||
+ | <sxh alphabets; gutter: | ||
+ | affine SRExample {N|N>0} | ||
+ | given | ||
+ | int X {i|0< | ||
+ | returns | ||
+ | int Y {i|0< | ||
+ | through | ||
+ | Y[i] = reduce(+, (i, | ||
+ | . | ||
+ | </ | ||
+ | The original program has a reduction that computes, for each '' | ||
+ | |||
+ | The reuse vector to be exploited is specified by comma delimited string. | ||
+ | <sxh cs; gutter: | ||
+ | prog = ReadAlphabets(" | ||
+ | system = " | ||
+ | AShow(prog); | ||
+ | SimplifyingReduction(prog, | ||
+ | Normalize(prog); | ||
+ | AShow(prog); | ||
+ | </ | ||
+ | The resulting alphabets program is shown below. | ||
+ | <sxh alphabets; gutter: | ||
+ | Y[i] = case | ||
+ | {|i== 0} : reduce(+, (i, | ||
+ | | ||
+ | esac; | ||
+ | </ | ||
+ | The branch '' | ||
+ | The other branch '' | ||
+ | ====Normalize Reduction==== | ||
+ | In some cases, the reduction you wish to simplify may not be in Normalized form. For example, the following is an Alphabets program with nested reductions. | ||
+ | The inner reduction computes the prefix sum, and it can be simplified like the above example, but there is also an outer reduction that takes the max of the prefix sums. | ||
+ | |||
+ | <sxh alphabets; gutter: | ||
+ | affine NRExample {N|N>0} | ||
+ | given | ||
+ | int X {i|0< | ||
+ | returns | ||
+ | int Y; | ||
+ | through | ||
+ | Y[] = reduce(max, [i], {|0< | ||
+ | . | ||
+ | </ | ||
+ | NormalizeReduction is a transformation that transforms reductions that are not in normalized form into normalized reductions. | ||
+ | <sxh cs; gutter: | ||
+ | prog = ReadAlphabets(" | ||
+ | system = " | ||
+ | AShow(prog); | ||
+ | NormalizeReduction(prog, | ||
+ | AShow(prog); | ||
+ | </ | ||
+ | In the resulting code, the body of the outer reduction is replaced with a new variable. | ||
+ | |||
+ | This process is necessary for SimplifingReduction, | ||
+ | <sxh alphabets; gutter: | ||
+ | Y[] = reduce(max, (i->), {|i>= 0 && N-i-1>= 0} : NR_Y); | ||
+ | NR_Y[i] = reduce(+, (i, | ||
+ | </ | ||
+ | ====Reduction Decomposition==== | ||
+ | In some cases, reduction must be decomposed into reductions of lower dimensions before SimplifyingReduction is possible. The following is one such example. | ||
+ | |||
+ | The body of the reduction here has a 3D domain. | ||
+ | <sxh alphabets; gutter: | ||
+ | affine RDExample {N|N>2} | ||
+ | given | ||
+ | int X {j, | ||
+ | returns | ||
+ | int Y {i|0< | ||
+ | through | ||
+ | Y[i] = reduce(max, [j,k], {|0< | ||
+ | . | ||
+ | </ | ||
+ | Even with an operator that does not have an inverse, one dimension of reuse can still be exploited in the above example. The domain that is shrinking (= the source of the need for subtract) is the '' | ||
+ | |||
+ | The command ReductionDecomposition takes two functions that serve as new projection function for each reductions resulting from the decomposition. The first function composed with the second one should be equal to the projection function of the original reduction. For this example, we would like to make the reduction along the '' | ||
+ | <sxh cs; gutter: | ||
+ | prog = ReadAlphabets(" | ||
+ | system = " | ||
+ | AShow(prog); | ||
+ | ReductionDecomposition(prog, | ||
+ | AShow(prog); | ||
+ | NormalizeReduction(prog, | ||
+ | SimplifyingReduction(prog, | ||
+ | Normalize(prog); | ||
+ | AShow(prog); | ||
+ | </ | ||
+ | After the decomposition, | ||
+ | |||
+ | The second argument given to the ReductionDecomposition command is the nodeID corresponding to the reduction. For now, interpret it as "1st system, 1st equation, 1st expression", | ||
+ | <sxh alphabets; gutter: | ||
+ | Y[i] = reduce(max, (i, | ||
+ | </ | ||
+ | ====FactorOutFromReduction==== | ||
+ | FactorOutFromReduction is a transformation that factorizes expressions inside reduction. | ||
+ | This step may expose more opportunities for applying SimplifyingReduction. | ||
+ | Because the expression inside a reduction can form arbitrary sub-tree, the target expression must be specified with the nodeID like in the previous example. | ||
+ | |||
+ | In the following example program, adding values of '' | ||
+ | However, the value of '' | ||
+ | This reuse can be exploited by taking advantage of the distributive property (addition is distributive over max). | ||
+ | <sxh alphabets; gutter: | ||
+ | affine FactorizeExample {N|N>0} | ||
+ | given | ||
+ | int A,B {i|0< | ||
+ | returns | ||
+ | int X {i|0< | ||
+ | through | ||
+ | X[i] = reduce(max, | ||
+ | . | ||
+ | </ | ||
+ | |||
+ | The following script uses the FactorOutFromReduction command and specify VariableExpression '' | ||
+ | <sxh cs; gutter: | ||
+ | prog = ReadAlphabets(" | ||
+ | AShow(prog); | ||
+ | FactorOutFromReduction(prog, | ||
+ | Normalize(prog); | ||
+ | AShow(prog); | ||
+ | </ | ||
+ | After the transformation, | ||
+ | Addition of '' | ||
+ | Variable '' | ||
+ | This reuse can now be exploited because the access to '' | ||
+ | <sxh alphabets; gutter: | ||
+ | X[i] = {|N-i-1> | ||
+ | </ | ||
+ | |||
+ | Using other transformations covered in this tutorial, the sequence of transformations from factoring out '' | ||
+ | <sxh cs; gutter: | ||
+ | prog = ReadAlphabets(" | ||
+ | system = " | ||
+ | AShow(prog); | ||
+ | FactorOutFromReduction(prog, | ||
+ | Normalize(prog); | ||
+ | AShow(prog); | ||
+ | NormalizeReduction(prog, | ||
+ | SimplifyingReduction(prog, | ||
+ | Normalize(prog); | ||
+ | AShow(prog); | ||
+ | </ | ||
+ | Now the program is simplified (although it has many more lines of code). | ||
+ | <sxh alphabets; gutter: | ||
+ | |||
+ | X[i] = {|N-i-1> | ||
+ | NR_X[i] = case | ||
+ | {|i== 0} : reduce(max, (i, | ||
+ | {|i-1>= 0} : (reduce(max, | ||
+ | esac; | ||
+ | </ | ||
+ | ====How to Specify an Expression in AST==== | ||
+ | In the previous examples, nodeID was used to specify the target expression. For transformations that can be applied to expressions that may be in arbitrary locations, simply specifying the target system or variable may not be enough. | ||
+ | |||
+ | The nodeID is a vector of integers that uniquely identifies expressions in Alphabets program. It mostly corresponds to the xth branch to traverse in the AST. PrintAST can be used to find the nodeID for every Expression in the AST. You could also traverse the AST yourself, which may be a good way for simple programs like the above example. | ||
+ | |||
+ | The following is the output of PrintAST for reduction decomposition example (initial state). | ||
+ | <sxh alphabets; gutter: | ||
+ | _Program | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | The following is the output of PrintAST for factor out example (initial state). | ||
+ | <sxh alphabets; gutter: | ||
+ | _AffineSystem | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | | ||
+ | </ | ||