Skip Navigation CECS Home | ANU Home | Search ANU

Introduction to Computer Systems

Assignment 3 Specification - Matrix Transpose

The aim of this assignment is to give you some experience in programming and optimizing for a particular architecture. This assignment also aims to give you some practice in scientific report writing.

The basic part of the assignment aims to be simple enough for most students to be able to complete in less then 5 hours.

The assignment will be marked out of 100. And is worth 10% of the final mark. A late penalty of 10% per day applies (these are working days and apply from after the assignment is collected. The assignment will be collected some time after noon on the Friday. Also note this penalty is caped so it does not take your final mark below 40 out of 100. Assignment work will not be accepted after the last day of semester. Extensions are possible in documented exceptional cases (e.g. medical certificate).

Architecture

You can choose any architecture that has a c compiler and you can execute code on (avoid common loggin servers like partch). The idea is not to find an architecture that gives the highest performance, but to understand the characteristics of the one that you have chosen. By default just use a computer in the CSIT labs. Provide a short summary of the system you are using. This summary should include at least: cpu, clock rate, memory size, memory type, and L1/L2 cache size and type.

Transpose

Matrix transpose is a relative simple operation, however, as the matrices get large this operation becomes memory intensive. Moreover the simple implementation can produce a large number of cache misses this will slow the entire operation down considerably. In this assignment your task is to write the code for matrix transpose along with the code that will evaluate its performance (in terms of time) for different matrix sizes. Evaluate the time performance (on the architecture of your choosing) for different matrix sizes and include this evaluation in a graph in your report. The x-axis of the graph should be matrix size (use a logarithmic scale) and the y-axis time (give a value that is normalized which is the time taken per matrix element for the transpose). The report should provide an explanation of your graph.

For uniformity make the matrices square and contain doubles. Start with having the dimensions be powers of 2. i.e. the matrices would be 2x2, 4x4, 8x8, 16x16, 32x32, 64x64, ... You may then wish to add extra points to expore any interesting shifts or jumps.

(optional) Modify your transpose implementation with an aim to improve the performance. Conduct a similar evaluation, to that which you did with your basic implementation, on your improved version. Include these results within the graph in your report. You may wish to report the results of different parameter settings.

Report

The report must be at most 2 pages and contain the following:

• A title.
• Your name and student id.
• Abstract - Overview of what you did and your main findings.
• Experimental Set up - explain and justify the approach used for timing the transpose on different matrices. Also provide an overview of the architecture you have used.
• Transpose approach - give the algorithm and any optional improvements used for calculating the transpose.
• Results & Discussion - The graph of your findings along with an explanation and discussion of the results.
• References

In-addition to the main 2 page report you may attach appendices. Please include as one of the appendices the source code of your implementation.

Use a 2-column report format with a 10 point Times-Roman font. The appendices may be single column. The report must be in pdf format that is viewable on the lab machines.

Marking

Marks will be given based on:

• The approach taken in gathering results along with the justification for the approach used.
• The transpose implementation and any improvements made to the implementation.
• The reporting of the results along with the discussion.
• The clarity of the report.
• The formating of the report (this includes the formating of the main graph).

Individual Assignment

This is an individual assignment. You may help each other, however, the final submission must be original and your own work. Take care not to give parts of your solution to other students.

Assignment Submission

The assignment must be submitted via a computer in the CSIT labs (or remotely via ssh to "partch" or one of our servers). To submit the assignment use the following command:

submit comp2300 ass3 report.pdf

A few hits for submission:

• Don't have spaces in your file names. (the submit program does not like them!)
• Copy the files to your home directory, rather, than having them mounted on a USB drive.
• You may submit as many times as you like, I will mark the most recent one that is not late.
• If you are in comp6300 then use comp6300 rather then comp2300 in the command.