CS 560 HW4: Moving on with Alpha
Introduction
The purpose of this exercise is for you to (i) continue developing Alpha
programs, (ii) reinforce the ideas that the volume of polyhedra correspond to
the asymptotic complexity, (this time to study the effects of constant
factors), (iii) start getting familiar with the powerful static analysis that
AlphaZ does (it essentially guarantees that your program will never throw an
out-of-bound exception). You will also sharpen your mathematical reasoning
skills to develop/derive algorithms, and start understanding what it means to
manipulate polyhedra and affine functions.
Problem 1
If you haven't done so yet, work your way through the LUD Tutorial off the
AlphaZ wiki. When you encounter the "teaching moment" please email Sanjay
with the symptom, and/or how you fixed the problem.
Part 2: Please be ready to discuss this in the next class.
When you fixed the problem, did you modify only one of the reductions or both
of them. Why/why not?
Problem 2
Part 1 Start with a simple one-liner program for square
matrix multiplication that returns C=AB. Modify it (simply change the domains
of the declarations of the input variables) so that it now handles the case
when A is lower triangular, and B is upper triangular. Generate the C code
and empirically measure the complexity of the program. Deduce and report a
formula for the complexity (the constant factor is important). Compare this
complexity with that of the original program for full matric
multiplication.
Part 2: Modify the program once again, so that this time A is
upper triangular and B is lower triangular.
Again, empirically measure the execution times and deduce the complexity of
the generated program, and compare it with the previous two programs.
Problem 3 You are given a square, upper triangular matrix, U.
Part 1:Using mathematical reasoning as in the foundation
notes and in class, systematically derive the equational program to invert the
matrix [Hint: the inverse is known to also be upper triangular]. This is a
paper an pencil exercise, and you will need to come up with a proof. It may
be helpful if you show write the equations for the different regions of the
identity matrix (on and off-diagonal) and simplify them like in the above
examples.
Part 2: Next, write the Alphabets program for this, use AlphaZ
to generate the corresponding C program, and validate it.
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.
Last updated February 2013