COSC441 Assignment 1, 2017

The purpose of this assignment is to get you to create some very simple threaded programs.

If you write these programs in C you will be able to use the kind of interface described in lecture 3, and it will be less effort than using most other languages. However, you may use Java.

• Write a program to add up the integers 1 to 1,000,000 ten thousand times, accumulating the answer in a static signed long long int (that's for C, for Java use static long) and print the answer. The correct answer is 5000005000000000.

  Measure how long this takes (both CPU time and real time).

  Q. Sorry if this sounds silly, but I suppose we should turn off compiler optimisations for the assignments?

  A. This is an excellent question. The answer is no. Remember what I said in the lectures? The compiler is allowed to transform your program in seriously strange ways as long as the observable behaviour is unchanged. Several modern compilers analyse linear progressions quite cleverly in order to detect

  • might we need a bounds check here?
  • are these assignments to array elements independent?

  With optimisation, I actually get
  0.000 user + 0.000 system = 0.000 total in 0.005 real seconds.

  Again, remember what I said in the lectures? You can disable optimisation for a specific variable using ‘volatile’. Adding that to the declaration of the total produces this time, still with -O3 optimisation:
  22.220 user + 0.020 system = 22.240 total in 22.308 real seconds.

  Here's another approach, which lets the compiler optimise somewhat, but hides what's going on.

  1. Declare an array of 1,000,000 integers.
  2. Fill it with the numbers 1 to 1,000,000 in any order.
  3. Shuffle it at random. See the Fisher-Yates shuffle at Wikipedia for a good algorithm. I use that a lot.
  4. Initialise the global variable.
  5. Do 1,000 times:
  6.     Add each element of the array to the global variable.

  Doing it that way, I get these times:
  2.600 user + 0.030 system = 2.630 total in 2.757 real seconds.

  That tells us that we have successfully hidden the linear progression from the compiler, so it's not eliminating most of the program, but also that it is working with a local copy of the global total, not going to memory every time. (And the difference between 2.6 seconds and 22.2 seconds tells you a lot about the cost of memory.)

  Q. Also, is it OK to use "time" for cpu/real timings?

  By doing

  #include <time.h>
  clock_t t0, t1;
  set up the array;
  t0 = clock();
  compute the total;
  t1 = clock();
  print total and (t1-t0)/CLOCKS_PER_SEC;
  

  you can measure the part of the program you care about and skip the rest; using the time(1) command will measure everything, including starting the program, dynamic linking, and printing. On the other hand, time(1) gives you real time and clock(3C) does not.

• Write another version of the program that divides the work between N threads, where N is supplied on the command line. The declaration of the total should be changed to static volatile signed long long int but adding should still be done by total += x.

  Measure how long this takes (both CPU time and real time) for N = 1 to 8. Do you still get the correct answer?

• Write a third version of the program identical to the second except that the total variable is protected by a mutex. In Java, the mutex can be any object you like; it does not matter.

  Measure how long this takes (both CPU time and real time). Do you get the correct answer now?

• Write a fourth version of the program that uses atomic_fetch_add (if available) to update an atomic counter, or on a Macintosh or other BSD system uses OSAtomicAdd64Barrier (see 'man atomic') to do atomic adds. If you use Java, you'll want java.util.concurrent.atomic.AtomicLong

  Measure how long this takes (both CPU time and real time) for N = 1 to 8. Do you still get the correct answer?

Submit your assignment within two weeks by sending an e-mail message to ok@cs.otago.ac.nz with the subject "COSC441 Assignment 1" and a .tgz file containing exactly five files:

• single.c — the first version
• thread.c — the second version
• mutex.c — the third version
• atomic.c — the fourth version
• report.txt — a plain text report

The report must contain your name (not login account) and student number.

It should contain your measured times in a table

It should contain your commentary on what you found.