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

Deadline: 22nd December 2015.
How to submit: As an attachment of email to

The rules

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

Submitting your solution

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

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:

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

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

We recommend to experiment the following parameters of cache:

Size of one page [B]Number of pagesSize of cache [B]

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