Due date: Tuesday, March 8, 2005 - In class
Introduction
In this assignment, you will use the Bernoulli Compiler Construction Kit (BCCK) compiler test-bed and the OMEGA library to perform dependence analysis. The objective of the assignment is to get you started on working with BCCK and OMEGA, and to familiarize you with dependence abstractions.
There are two parts to the assignment. In the first part, you must compute dependence vectors for a few simple loop nests by invoking the Omega calculator. This part does not require you to use BCCK. In the second part, you must use BCCK to extract extract systems of dependence constraints from a small C program and use the Omega library to compute dependence vectors from these constraints.
1. Dependence Analysis using the Omega Calculator
For each of the loop nests given below, write down the dependence systems (sets of integer linear inequalities) for computing flow, anti, and output dependences. Your dependence systems must include inequalities generated from loop bounds. Enter these systems by hand into the Omega Calculator (Win32/Cygwin binary available here), and compute dependence distance/direction vectors.
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
for(int k=0; k<N; ++k)
A[i][k] = B[i][j] * C[j][k];
for(int i=0; i<N; ++i)
for(int j=i; j<N; ++j)
A[j] = A[2i+1];
for(int i=0; i<N; ++i)
for(int j=0; j<i; ++j)
for(int k=i; k<N; ++k)
A[i][j] = A[i][j-4] * A[k][i-1];
for(int i=0; i<100; ++i)
x[i+100] = 2*x[i]
for(int i=0; i<100; ++i)
x[i+100] = 2*x[i+1]
Hint: Put all your queries in a file and pipe that file through the Omega Calculator.
C:\oc> notepad hw2_1.oc C:\oc> .\bin\oc.exe < hw2_1.oc
Turn in the dependence systems, the queries submitted to Omega, and the dependence vectors computed in this manner.
For the second loop nest, graph the iteration space and use arrows to show the dependences between the iterations.
2. Using BCCK
The BCCK system is a compiler toolkit written in C# that compiles C programs to an intermediate format on which analysis and optimizations can be performed. In the problem, you will download and install BCCK on your machine.
The source code is available from here. A patch that will allow you to run the toolkit with Visual Studio .NET 2003 is avaliable here. If you are looking for the easiest way to get BCCK running, opt out for the Windows + Visual Studio.NET option below. To compile BCCK on your machine,
Windows: As a student in a CS course you are entitled to a free copy of Microsoft Visual Studio .NET. Computer Science PhD students can get this through MSDNAA. If you are not sure what this is, ask in Upson 311. Other students can get an account to the CS Undergraduate Lab, where there is a distribution of it on the network drives and CD burners. To build BCCK either,
Linux: BCCK is currently being ported to Portable.NET, which will allow it to run on different unix systems. At this point BCCK can be compiled and used under Linux using the Microsoft Shared Source Distribution of .NET (code named Rotor), ported to Linux by Macadamian (http://www.macadamian.com/products/sscli/index.html). If you want to experiment with this, we will do our best to answer any questions you might have along the way.
FreeBSD: It should be possible to use the BCCK under FreeBSD using Rotor. Again, we will do our best to answer any questions you might have along the way.
Note: The Mono and Portable.NET C# compilers do not currently compile the BCCK.
Run BCC.exe on the "C/Samples/cs612/test.c". The output should be,
Function: test1 Function: test2 Function: test3 Function: test4 Function: test5 Done!
Make sure that you have this working before continuing to 3.
3. Dependence Analysis using BCCK and the Omega Library
The file "BCC/DependenceAnalysis.cs" is skeleton for doing dependence analysis using BCCK. Using the techniques presented in class, add code to DependenceAnalysis.cs to compute distance and direction vectors.
Run your compiler on "test.c". Turn in your code, and the dependence vectors produced by your compiler.
Here is additional documentation that you might find useful,
Some C# pointers,