CS612 Problem Set #3

In this assignment, you will integrate transformations for locality enhancement into a SUIF1 compiler pass and evaluate the performance of the compiler-generated code.  For this assignment you will need the SUIF Transform Library which is contained in the baseparsuif package, available on the SUIF1 website.

1.  Code Transformations

Create a SUIF1 pass to do all of the following:

• Compute the locality matrix for a perfectly nested loop.  In addition to dependence vectors, your locality matrix should contain vectors for spatial locality and for read reuse locality as explained in class.  Note:  You may use any outside tools you wish, or write your own, to do the linear algebra involved (basis of a null space, etc.).  One tool you might decide to use is the Alpha Calculator.
• From the locality matrix and the dependence matrix, generate a transformation matrix as described in class.  Application of the transformation matrix should:
  • perform height reduction
  • make as many inner loops fully permutable as possible
• Apply the transformation using the SUIF transform library routine unimodular_transform.
• Fully tile the permuted loop nest using the SUIF transform library routine tile_transform.  Use tiles that have the same length (say K) in all dimensions (convert K to the parameters needed by tile_transform in your code).

2.  Code Testing

Compile the supplied C code file with SUIF (integrating your pass, using no other optimizations) and gcc.  Using the UNIX time command (see man page for usage) compare the running times of the resulting programs.  Test you code for several values of K.

3. Tile size selection [**OPTIONAL**]

For extra credit, you may also design and implement a tile size selection algorithm.  Here are some resources to help you get started.

• Stephanie Coleman and Kathryn S. McKinley. Tile Size Selection Using Cache Organization and Data Layout 
• Wei Li. Compiler Cache Optimizations for Banded Matrix Problems 
• Wei Li. Transformations for Cache Locality (Ch 5 of PhD Thesis)

The amount of extra credit that you will be awarded will be based upon the sophistication of the algorithm.

What you must submit:

• Source code for your SUIF pass
• SUIF output C code for the supplied program for some value of K
• A graph of running time as function of K (use K=N for no optimization), or source code and a description of your tile size selection algorithm.

Hints:

• Read the transform library documentation and source code before beginning to see what tools are available.

Last Updated: Wednesday, March 06, 2002 02:50:37 PM