High Performance Computing in C/C++

Course Material

The Introduction to C Notes are intended to provide an introduction to the C language for use in this course. The slides from the lectures will be available for download from here after each lecture:

  1. The C Abstract Machine Model
  2. C Flow Control
  3. The Evolution of High Performance Computers
  4. Memory Models for HPC
  5. Common C Programming Errors
  6. Debugging C Code
  7. Models of Concurrency
  8. Threads in C. This lecture used a parallel quicksort as an example. Try downloading the source and seeing how it performs in different situations and on different hardware. See if you can modify the code to make it faster.
  9. Synchronising threads
  10. Introduction to Erlang: A Language For Message-Passing Concurrency. This lecture showed a simple Fibonacci sequence generator, and a Quicksort implementaiton in Erlang. Try using this test program to see how the serial and parallel versions compare on your computer.
  11. Lock Freedom
  12. Transactional Memory
  13. C++ Introduction
  14. More C++

C library function documentation can be found by checking the UNIX manual, via the man command. Unfortunately, the documentation on GNU/Linux is incredibly badly written. If you are unfortunate enough to be using GNU/Linux, consider using the FreeBSD online man page viewer instead.

Assessment

This course is assessed by three programming assignments and an essay. Grades for marked coursework are available online. The second coursework has now been marked. The final marks (pending review by the examiners' meeting) marks for the course are now available.

Coursework 1: 10%

Coursework 1 is intended to assess your ability to write simple C code, including dynamic memory allocation.

Clarification of part 2: Exactly how you calculate the averate (mean, median, or mode), or whether you track the number of guesses required to win, or the number of games lost between each win, is not important. You will be assessed on your use of malloc(), realloc(), and free() when recording the score data after each game, not on your ability to calculate averages.

This coursework is intended to be easy, and to give students some practice writing C before the more complex assignments. Each question is graded on a pass/fail basis, so your result will be either 0%, 50%, or 100% for this coursework. Any student who does not get 100% should expect to spend some private study time catching up with the rest of the class.

Coursework 2: 30%

Coursework 2 is intended to assess your ability to write more complex C code, including multiple compilation units and abstract data types. It is also intended to test your ability to conform to a published set of coding conventions - you will be penalised if your code does not use the simple conventions specified in the assignment.

This coursework is intended to be harder. All of the parts of C that you are required to use to solve it are provided in the hand-out notes, although the algorithms will require some creativity on your part.

When testing the code, you may encounter some strange results with command lines like ./bigintmaths 1234567890123456782 * 47. This is because the shell treats * as a special character, and expands it. If you are invoking the program from the shell, then you will need to escape it, for example by typing: ./bigintmaths 1234567890123456782 '*' 47

Hints

Your solution is only expected to handle unsigned (i.e. positive) integers. If it correctly handles negative integers, there are some bonus marks available, but a perfect solution without support for negative integers is still worth 100%.

Coursework 3: 10%

Coursework 3 is an open ended task testing your ability to optimise C code. A working solution is relatively easy, but marks abouve 40% are only awarded for fast solutions. A fast solution will require some of the techniques discussed in the lectures.

Performance

To receive more than 70% for Coursework 3, you will need to produce an implementation that performs faster than my sample solution (which still contains quite a few missed optimisation opportunities). The tests will be done with a set of random inputs. For reference, you can try comparing your version against these numbers:

$ time ./factorise 10001233012300011231234
2
3
379
87421
50309188877221

real	0m6.704s
$ time ./factorise 100012330123
100012330123

real	0m0.345s
$ time ./factorise 50309188877221
50309188877221

real	0m6.407s
		

All timeing results - including the final assessment - are on one of the Linux lab machines, with a 3GHz Core 2 Duo CPU.

Coursework 4: 50%

Coursework 4 is an essay. Submissions should be in PDF format - submissions in any other format will be ignored. Assessment is based on the knowledge that you display of the chosen subject. If you are not a native English speaker, then state this at the top of the essay, otherwise you will be penalised for poor use of English.

Note For Windows Users

If you are trying to do the coursework on Windows, you are making life very difficult for yourself. All code submissions are expected to work on the Linux lab machines. At the very least, you should test your code there.

If you insist on working on Windows, then I suggest that you either install Cygwin, which gives a vaguely UNIX-like environment for Windows. Alternatively, use PuTTY to connect remotely to the Linux lab machines.

Any coursework that contains Windowsisms and does not work on the Linux lab machines will be considered non-working, even if it works on Windows.