[Polly] Update the documentation on how the packing transformation is implemented

[gareevroman]

Summary

Add a simple example to update the documentation on how the packing transformation is implemented.

[gareevroman]

Why is the _access_ relation mapping to a 9 dimensional space. You talk about a _schedule_ here, right?

Right.

The access relation seems to implement a modulo constraint. It probably is easier to read if we write the modulo explicitly. I suggest to just submit a patch with this comment, then Michael and me can read over it and see if we still have some comments.

I've updated it.

Thanks for the comments!

[Meinersbur]

lib/Transform/ScheduleOptimizer.cpp

840–845 ↗

(On Diff #82220)

This is a mouthful to read and I cannot take any additional information from it. If show this here to illustrate the space of these isl_maps, I'd suggest to shorten it to something like { Domain[] -> Element[] } and { Domain[] -> Scatter[] } like I often do for DeLICM when the spaces are not obvious.

If it is for showing a numerical example, this is way to complicated. It would be better if you would construct an illustrative example by hand that only contains the relevant parts instead of dumping something from a test case.

850–852 ↗

(On Diff #82220)

How did we get to this?

{ Stmt_for_body6[i0, i1, i2] -> [o0, o1, o2] ... } is a scatter function as taken by setNewAccessRelation(), but the phrase uses the term "access location" which I would be something like { Stmt_for_body6[] -> MemRef_CopyA[] }.

853 ↗

(On Diff #82220)

setNewAccessRelation is only the setter method updating the data, about as interesting as MA->NewAccessRelation = NewAccessRelation. It would be more interesting who calls it.

[grosser]

Hi Roman, it might make sense to update this according to what we now have in our paper.

lib/Transform/ScheduleOptimizer.cpp

837 ↗

(On Diff #82220)

access relation

840–845 ↗

(On Diff #82220)

Hi Roman,

AFAIR the access functions in this comment can indeed be further simplified, no?

[Meinersbur]

lib/Transform/ScheduleOptimizer.cpp

850–852 ↗

(On Diff #82220)

I mixed up something here. It has the space of a scatter function, but probably only the target array (eg. Packed_A) is missing here (and setNewAccessRelation() does not accept scatter functions)

[gareevroman]

Thanks for the comments! I'll try to address them soon.

[gareevroman]

Update according to the comments.

This is a mouthful to read and I cannot take any additional information from it. If show this here to illustrate the space of these isl_maps, I'd suggest to shorten it to something like { Domain[] -> Element[] } and { Domain[] -> Scatter[] } like I often do for DeLICM when the spaces are not obvious.

I've tried to simplify the scheduling function and access relations. What do you think about it?

[grosser]

Perfect!

polly/trunk/lib/Transform/ScheduleOptimizer.cpp

createExtensionNode(__isl_take isl_schedule_node *Node,
   auto *NewNode = isl_schedule_node_from_extension(Extension);
   return isl_schedule_node_graft_before(Node, NewNode);
 }
 
 /// Apply the packing transformation.
 ///
 /// The packing transformation can be described as a data-layout
 /// transformation that requires to introduce a new array, copy data
-/// to the array, and change memory access locations of the compute kernel
-/// to reference the array.
+/// to the array, and change memory access locations to reference the array.
+/// It can be used to ensure that elements of the new array are read in-stride
+/// access, aligned to cache lines boundaries, and preloaded into certain cache
+/// levels.
+///
+/// As an example let us consider the packing of the array A that would help
+/// to read its elements with in-stride access. An access to the array A
+/// is represented by an access relation that has the form
+/// S[i, j, k] -> A[i, k]. The scheduling function of the SCoP statement S has
+/// the form S[i,j, k] -> [floor((j mod Nc) / Nr), floor((i mod Mc) / Mr),
+/// k mod Kc, j mod Nr, i mod Mr].
+///
+/// To ensure that elements of the array A are read in-stride access, we add
+/// a new array Packed_A[Mc/Mr][Kc][Mr] to the SCoP, using
+/// Scop::createScopArrayInfo, change the access relation
+/// S[i, j, k] -> A[i, k] to
+/// S[i, j, k] -> Packed_A[floor((i mod Mc) / Mr), k mod Kc, i mod Mr], using
+/// MemoryAccess::setNewAccessRelation, and copy the data to the array, using
+/// the copy statement created by Scop::addScopStmt.
 ///
 /// @param Node The schedule node to be optimized.
 /// @param MapOldIndVar The relation, which maps original induction variables
 ///                     to the ones, which are produced by schedule
 ///                     transformations.
 /// @param MicroParams, MacroParams Parameters of the BLIS kernel
 ///                                 to be taken into account.
 /// @return The optimized schedule node.