Data Structures I - NTIN066 - Winter Semester 2015/2016 - 4th homework

Deadline: 22nd December 2015.
How to submit: As an attachment of email to ds1@kam.mff.cuni.cz.

The rules

All the code which you submit must be original created by you without any external "inspiration".
Do not share your solution with anyone else so that your code does not become someone else's "inspiration". The only exception to this rule is submitting the assignment.
Feel free to discuss the homework and possible approaches with others. However, you should observe the above rules about not sharing any code. That is, discussion is fine as long as you write your own code by yourself!
Your solution should be written in either C/C++ (recommended), Java or C#.
Use only standard constructs of your programming language. Do not use any special library functions. The code dealing with the data structure has to be written solely by you.
Solutions deviating from the above rules will not be accepted.

The description of the problem

Implement the efficient cache-oblivious algorithm for transposing matrices NxN whose elements are 32-bits integers.

Measure the time for one transposition for N = 64, 69, 75, 80, 87, 92, 101, 109, 119, 128, 139, 150, 161, 174, 189, 203, 220, 237, 256, 280, 300, 322, 352, 378, 406, 442. 476, 512, 552, 598, 645, 705, 760, 812, 878, 960, 1024. Compare time with the direct transposition by definition. Repeat the measurement so that the result is accurate.

Write a report containing

a plot of measured results (time for a single transposition versus the size of a matrix),
parameters of the testing computer (processor type and the size of cache) and
explanations of all results

Submitting your solution

Send an e-mail with subject of the form 'HW4-55973318' (i.e., HW4-student ID) with the following attachments:

source code used to get your results (in case it consists of multiple files, please use ZIP or TAR to pack them),
a PDF with plots and comments.

The body of your e-mail shall have the following form:

Name: Jirka Fink
Pseudonym for web results: Guybrush Threepwood
Tutorial section: Monday-12:20-odd

Voluntary extension of the homework

If you are interested in cache-oblivious algorithms, you can also modify your program so that it prints out swapped elements instead of actual swapping. Then, pass this output to our cache simulator to determine number of page faults of an idealized cache as presented during the lecture (full associativity, LRU strategy).

Download the simulator and start it with the following parameters:

B – size of a page;
C – number of pages in the cache.

The simulator reads commands for transposing matrix on the standard input. Every row has one of the following forms:

N n – initialize a matrix n×n
X r₁ s₁ r₂ s₂ – swap elements (r₁,s₁) and (r₂,s₂), assuming that coordinates are numbered from 0 to n-1
E – terminates the transposition

The output of the simulator is a text file describing results of the experiment:

Elements: the number of elements of the matrix
Accesses: the number of memory accesses
Misses: the number of memory transfers from the main memory to the cache
Missed-bytes: the total number of elements loaded to the cache

We recommend to experiment the following parameters of cache:

Size of one page [B]	Number of pages	Size of cache [B]
64	64	4096
64	1024	65536
64	4096	262144
512	512	262144
4096	64	262144

The simulator expects that matrix is stored by rows and the first row starts on a beginning of a page.