CS560 Alpha and Equational Programming: getting started
Introduction
The purpose of this exercise is for you to learn how to write polyhedral
equational programs in Alpha, how to use the AlphaZ systems and run such
programs.
Problem 1
Start with the program for Pascal's triangle that was developed in class (or
with the one in the Pascal directory when you check out AlphaZ) and complete
it. Extend the definition of the program so that it returns the binomial
coefficients for n, and also the first n Fibonacci numbers. In
order to do this, you will need to understand how to write reductions in
Alpha, and the LU Decomposition tutorial off the AlphaZ wiki will be useful to
do this. Don't worry if you don't get it right away (it will be explained in
class on Tuesday) but continue with the rest of the assignment.
Problem 2
In this problem you will understand the relation between the number of points
in a polyhedron (it's "volume") and the asymptotic computational complexity of
equational programs.
Write an Alpha program to compute the n-th Fibonacci number using the
standard definition. It should have no input variable, and should return a
single scalar (i.e., a zero-dimensional variable). Change the data-type of
the variables to float or double in order to avoid integer
overflow. Now determine the execution times of the two programs for reasonably
large values of N, plot this on a log-log scale and determine the asymptotic
complexity of the two programs.
Modify the C code generated by AlphaZ for the second (standard) Fibonacci
program as follows. Replace the evaluation function called by the wrapper by
the following simple recursive definition.
float fib(int n){
if (0<=n && n<= 1) return 1.;
else return fib(n-1) + fib(n-2);
Experimentally determine the complexity of this program and report it.
Problem 3
Redo Problem 1, but now using Blaise Pascal's original description of the
table: the domain of the variable T should be {i,j | 0 <= (i,j)
<= i+j <= N}. The trick now is to determine the correct way to describe
the reduction. For this, you may find it useful to draw out the triangle on a
paper, and draw the lines connecting the points be accumulated to produce the
answer. The equation for this line should give you an idea about how to write
the reduction.
You will turn in only a tarball of your code including the generated files
(using the same structure as in AlphaZ (a set of directories for the different
Alpha programs, and one (under test-out) for the generated (and modified) C
code. Separately, you will also turn in a pdf report documenting your
experiments and results.
Except as otherwise noted, the content of this presentation is licensed under
the Creative Commons Attribution 2.5 license.
Last updated February 2013