CSC 2/458: Parallel and Distributed Systems

Spring 2008.

Assignment 1: pthreads

The purpose of this assignment is to give you some general experience in writing shared memory programs using the standard pthreads library package.  For more information on pthreads, you may want to consult the pthreads man page and the tutorial from Lawrence Livermore National Lab.  On the man page, you will see that Sun provides somewhat more extensive facilities for its threads package, but these are not portable across platforms. 

Part I (before the start of class on Monday 28 Jan. [but not to be handed in]):

Log on to our smaller SunFire machine, sync.cs.rochester.edu and set up your account.  Create a program that launches t threads that print their thread id and halt.  (Please do not use the larger machine, swym; it’s being used fairly heavily for research experiments.) 

Part II (by 5:00pm, Friday 1 Feb.):

Extend your program to have the threads share a counter.  Have each thread increment the counter i times

Try each option with varying numbers of threads, both greater and fewer than the number of processors in the machine.  (To find out how many processors there are, run psrinfo -v).  Report final counter values and execution times.  Try any other tests that occur to you.  Explain your results (in writing). 

To simplify testing of your code, please write your program to take the number of threads t and the number of iterations i as command-line arguments, specified with “-t t” and “-i i” (in either order).  If the arguments are not specified, use t = 4 and i = 10,000. 

Be sure to include a README.pdf file that explains what you did and what you learned.  It should include your timing results and analysis of the various locks.  We will be grading the assignment on a roughly equal mixture of completeness and correctness; programming style; and quality of write-up. 

Part III (by 5pm, Friday 8 Feb.):

Use the infrastructure you built for Part II to test concurrent queue algorithms.  Specifically, have each thread run a loop in which it repeatedly enqueues data to, or dequeues from (with 50-50 probability), a shared queue.  Implement the queue four different ways:

As described in the linked sources above, be sure to use “counted pointers” to avoid the ABA problem.  Also, to avoid “polluting” your results with the overhead of memory management (the standard malloc and free don’t scale well), you should have each thread pre-allocate its own supply of nodes, which it can keep on a private list when they are not in the queue.  Finally, to avoid pollution from calls to the pseudo-random (the standard rand isn’t even thread-safe), you should pre-generate enough random bits to drive the choice between enqueueing and dequeueing for the entire test run.  Be sure to use a barrier (described in the notes below) to “synch up” your threads after this setup is complete, and before starting the timing run. 

As in Part II, your README.pdf file should contain a detailed description of the experiments you ran, graphs of the results, and discussion that explains those results—why they look the way they do.

Notes


Last Change: 31 January 2008 / Michael Scott's email address