Matrix Multiply

CMSC 483/691c, Parallel Programming

Project 1: Basic Matrix Multiply

The Project

You are to write an mpl program that

Reads an n by n integer matrix A, of size up to 64 x 64, stored in ascii form in the file "A.mat" with one row per text line,
Copies A to the upper left-hand corner of the PE array, one value per PE,
Computes A^k, where k is specified as an optional command line argument which defaults to n, and
Writes out A^k in the ascii file "B.mat", in the same format in which it was read, and prints the total DPU time (not counting i/o time) involved in the computation to stdout.

Discussion

A detailed 3 x 3 example of the "in place" SIMD matrix multiply algorithm is available, with rotations and active sets marked at each stage. You should not use too much extra storage in computing A^k; in particular, do not try and store an entire matrix column on a single PE. An example program reduce.m shows how to use the library routines that return total DPU time.

Examples of routines to read and write ascii matrix files can be found in ~motteler/bp/dpuio.m on nibbles4. You do not have to use the "mat" array structure used there, which is more general than necessary for this project. Note that the dpuio.m routines are very slow, and you should not include the ascii read and write times in your calculation of total DPU time. (The dpuio.m routines were only intended for testing parts of the production bp code; there is a much faster set of i/o routines in feio.m which run on the "front end" machine.)

You don't have to check for bad input data, invalid command lines, or integer overflow. I will supply data that doesn't overflow 32 bit integers when k is less than or equal to n.

Test data

Sample test data is provided. This is a tar file, which contains a 4x4 array a4 in a4.mat, with a4^2 in a4_2.mat, and a4^4 in a4_4.mat, and a 64x64 array a64 in a64.mat, with a64^2 in a64_2.mat, and a64^64 in a64_64.mat.

What to turn in

For this first project, use email to submit a single mpl source file. Make sure that your name and "project 1" are at the top of the file. At the beginning of your comments you should also mention: (1) if your project works correctly, and (2) your DPU time on the A64.mat test data.

Grading

See the General information about projects. About 60% of your grade is based on how well your code works, with the remainder of the points divided between design and documentation. Projects are due by midnight of the assigned date; there is a 5% bonus for each day a project is turned in early (for up to two days early), and a 5% penalty for each day the project is turned in late.