From 741ac1f1eb26e4ee44212a9c91b4b33ca4b9fb5f Mon Sep 17 00:00:00 2001 From: Francis Russell Date: Mon, 30 Jan 2012 18:53:26 +0000 Subject: [PATCH] More updates to notes. --- NOTES | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) diff --git a/NOTES b/NOTES index bb30b8e..b1d891f 100644 --- a/NOTES +++ b/NOTES @@ -73,3 +73,44 @@ extends reduced. 8. Nodes access data by providing index bindings for all indices they destroy. 9. Nodes set data by providing index bindings for all indices they create. + +Case Study +---------- + +An inner product between an entirely dense 3D data-set and one stored in PPD format. + +1. Let's say that an inner product doesn't entirely destroy its indices. + +2. Instead, the indices it produces are a composite of its input indices. + +3. Now both inputs generate indices that are not destroyed (sort of). + +4. We can now fuse provided that we can generate loops for the fused +iteration. + +4. However, we only fuse on common prefixes, but the Function Set +has the PPD-iteration loop as its outermost loop. + +5. We chose the common-prefix law in order to avoid redundant +computation of values, but the PPD loop doesn't do this. The subsets the +PPD loop iterates over are disjoint. + +6. Both block matrices and the PPD-representation have these external +sorts of indices. Both iterate over disjoint subsets of the data. It +would be nice to have more examples to fully characterise them. + +7. So when are we allowed to move the PPD iteration loop? Why is this +such an issue? If in the integrals_kinetic example, we were able to move +the PPD iteration loop outside our assignment loop (fixed # of PPDs per +sphere), it would destroy everything. Clearly, it must be constrained +somehow. + +8. The work by Kotlyar et al. focusses on how to construct the set of +tuples required for iterations, but now how they are to be reduced. The +PPD-loop cannot be moved because the reductions are non-trivial for a +number of the quantum chemistry operators (e.g. FFT). + +9. All loop re-arrangements must respect two restrictions: + - Loops cannot move outside the loops they depend on (the obvious one). + - Loops cannot move above a node that destroys them. Why? + It represents some form of implicit reduction over that index? -- 2.47.3