From fb4a986a99d2e0dfb052e9f600991c5cf6dd7fcb Mon Sep 17 00:00:00 2001 From: Francis Russell Date: Wed, 22 Feb 2012 15:22:17 +0000 Subject: [PATCH] Add notes on expression strategy. --- docs/expression_strategy.txt | 60 ++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 docs/expression_strategy.txt diff --git a/docs/expression_strategy.txt b/docs/expression_strategy.txt new file mode 100644 index 0000000..66ddf7d --- /dev/null +++ b/docs/expression_strategy.txt @@ -0,0 +1,60 @@ +Sources provide : + - An access expression + - Expressions for computing offsets (i.e. in physical space) + - Quantifiers across loop index + - Predicates on the ranges of their operands + - Predicates on the sizes of their operands + +The implementation of an inner product: + - We need an intermediate buffer. + - Must be unique in all enclosing indices. + - Must be unique in all indices except one being reduced. + - Output is the iteration over the resulting buffer. + +The instantiation of intermediate buffers: + - There is a two-way dependence between buffers and code making this tricky. + - Can we generate code with no-buffers? + - Yes, we can always recompute, except for cases where buffers are explicit. + - Can we generate code with all buffers? + - Yes, slow as a dog and horribly memory inefficient. + - What are buffers anyway? + - Explicit names for values. + - Helpful for reductions such as inner products. + - Helpful for black box handling of FFTs. + - Buffers can provide an iteration context. + - When do we want to instantiate buffers? + - Anywhere they are instantiated explicitly. + - Whenever an expression could be subject to loop-invariant code motion. + +Code generation strategy: + - Input is set of predicates and quantified expressions + - FFT is equivalent to IO in a monadic context? + - We need to be able to explicitly represent buffers in our input thanks to black boxes. + - Expressions have an associated set of indices required to uniquely identify their value. + - Assignment results in fictional expression? + - What is the dimensionality of the FFT expression? + - Do we treat the FFT-buffer as special buffer sized value? + - Better to try to pretend it's a value with special independent dense-ranged iteration indices? + - IO is the assignment operation. + - Assignment is the guarantee a certain set of operations *will* be executed. + - Do we need to handle reduction explicitly in our tree? + +Our database: + - Some form of quantifier (how close to a loop body this is, is uncertain). At least an index. + - Predicates on the range of derived expressions. + - Predicates on the lower and upper bounds of loop indices. + - How do we distinguish predicates which are given from those that must be satisfied? + +Code generation: + - Input a set of quantified expressions. + - Try to move redundant expressions outward. + - Move overly quantified expressions to temporary variables. + - Fused loop generation: + - We need to explicitly handle the different cases. + - We look for expressions located in contexts in which we have a loop variable binding. + - In the dense case, we can explicitly index the loop since our transformation is invertible. + +Handling assignments: + - The integrals_kinetic assignment is tricky since we only want to handle values in the sparsity pattern. + - Correct iteration over non-zero values is preferable + -- 2.47.3