CS612 Homework #3

Due date: April 14th, 2005

In this assignment, you will integrate transformations for locality enhancement into a BCCK compiler pass and evaluate the performance of the compiler-generated code. You should use the updated version of the BCCK. Read these notes very carefully!!!

1. Code Transformations

Create a BCCK pass to convert a perfectly-nested loop nest to a fully-permutable loop nest if possible, using the algorithm described in class. To keep matters simple, you do not need to implement height reduction.

• Compute the dependence matrix for the perfectly nested loop. You may use any outside tools you wish, or write your own, to do the linear algebra involved.
• From the dependence matrix, generate a transformation matrix as described in class.  Remember that the transformation is driven by the goal of eliminating all negative entries in the dependence matrix if possible. If there are negative direction entries in one or more vectors, the transformation should make as many inner loops fully permutable as possible.
• Extract a unimodular transformation from the resulting transformation matrix, using the factorization to pseudo-Hermite normal form described in class. You can use the routine we have supplied for performing this factorization.
• Apply the transformation using the BCCK transform library routine ILP.Utils.UnimodularTransform.
• Tile the fully-permutable loop nest using the BCCK transform library routine X.ForStatement.Tile.  Use tiles that have the same length (say N_B) in all dimensions (convert N_B to the parameters needed by tile_transform in your code).

To find a good value for N_B, self-tuning systems like Atlas use a simple search strategy: generate code for different N_B values, run them on the machine, and choose the one that performs best (for details, see Yotov et al. PLDI'03). Invent a search strategy of your choice, and implement it. One possibility is to perform exhaustive search within some interval; for example, you can use the size of the cache determined by running a micro-benchmark to find an upper bound for tile size. Note that the optimal value of  N_B may be different for different loop nests.

Compile the supplied C code file with your tiling transformation and without. Compare the running times of the resulting programs. 

2. Tiling for the register file (MMM only)

Tiling for the register file is no different than tiling for the cache, except that you need to unroll the code for the register tile completely and assign array elements to scalar variables, as compilers rarely (if not never) are able to allocate registers to array subscripts. This technique, known as scalarization is described in more detail in many papers; here is one. This paper gives a general algorithm for scalarization, but for this assignment, you should think about what you need to handle just MMM, and implement only that. 

Note that because registers are few in comparisons to the capacity of the L1 data cache, it is usually not optimal to use square tiles for that level of the memory hierarchy (see Yotov et al. PLDI'03).

Implement loop unrolling and scalarization passes for BCCK. Using a search strategy, explore different register tile sizes. The use of register tiling may change the best value of N_B for L1 cache tiling from the previous step, so your search strategy should search for the best value of N_B as well as the best register tile.

What you must submit:

• Source code for your BCCK passes
• C code generated by your tiling transformation for the supplied program.
• A graph of running time as function of N_B (use N_B=N for no optimization).
• Indicate which value of N_B and the size of the register tile as well as other parameters your search strategy chose. 

Last Updated: Monday, March 28, 2005 01:09:32 PM