Lectures

• 30 Aug, Overview; Java Concurrency in Practice (JCIP): Chap 1
  
• 1 Sep, Thread safety (JCIP Chap 2).
  We went over an example of a buggy Prime number finder, PrimeBuggy.java. The fixed version is Prime.java. During the discussion we agreed that we might avoid the use of synchronized by having each thread have its own copy of the primes array, and have the main thread combine the results. We worked out these solutions in a later lecture, see below.
• 6 Sep, Labor day, no class
  
• 8 Sep, JCIP, Chap 3.
  Project 1 is posted
  We discussed atomicity in conjunction with the Prime.java example, and explained why avoiding data races is a good idea in general, but not sufficient to ensure correctness. We discussed the notion of visibility in multi-threaded programs; while it is easy to think about sequentially-consistent orders, in practice, program events are ordered according to the happens-before relation. We went over the NoVisibility.java example from the text.
  
• 13 Sep, JCIP, Chap 12.
  In-class exercise Eclipse project skeleton. Information about the MultithreadedTC testing package. Here are the JavaOne slides we briefly covered in lecture. The solutions are here: MTCLockTest.java, MTCLockTest2.java, TestAtomicInt.java.
  
• 15 Sep, Safe publication: we saw an example, Pairs.java, in which an object reference is not safely published (the constructor may still be running when the currPair reference becomes visible to other threads). We also discussed using thread-local variables and the java.lang.ThreadLocal class as a means to avoid synchronization in PrimeAlt.java and PrimeThreadLocal.java, respectively.
  
• 20 Sep, JCIP chapters 3 and 4. Examples used in class NumberRange.java and NumberRangeBadDelegate.java
  
• 22 Sep, JCIP chapter 5. Here are the JavaOne slides we used in class (some of the slides we didn't cover, but will in a future lecture).
• 27 Sep, JCIP chapter 6. We referred to some of the above JavaOne slides.
  Project 2 is posted
  mmult.zip is the in-class exercise; here are some slides about it, and here is a series of solutions: mmult-solution.zip. Finally, here is an alternative parallelization of prime finding: PrimeParallel.java.
• 29 Sep, JCIP chapter 6, exercise in parallelization on WordCount.java (note that this file more intelligently uses a StringBuffer, in contrast to the one we started with in class). We referred to these slides to identify the kinds of parallelism. We went over this design recipe. We developed versions of word counting as follows:
  • WordCountTransition.java "chunks" the units of work but executes them sequentially.
  • WordCountParallelBad.java performs the units of work in parallel using a thread pool, and synchronizing on the map when updating it. The overhead from synchronization becomes prohibitive.
  • WordCountParallel.java uses a ConcurrentHashMap to avoid the synchronization overhead, and it performs much better, but it must be clever about updating the counts to avoid read-modify-write atomicity violations.
  • WordCountParallelAtomicInt.java uses an AtomicInteger in the range of the map to avoid these problems, as suggested by someone in class. We use same AtomicInteger once it is added to the table, and modify it in place.
  Here is a transcript of runs on my machine that shows the performance of each approach. This comes from my 8-core, 16 GB-of-RAM Mac Pro.
• 4 Oct Went through a design recipe for allowing your program to use Futures (described in Chapters 5 and 6 in the text). Here is the recipe. Here is an example: started with ArrayAverage.java (which computes the average of a large array), then blocked up the work in ArrayAverageChunk.java, and finally parallelized these chunks using Futures in ArrayAverageParallel.java.
• 6 Oct Completed JCIP Chap. 7, started JCIP Chap. 8.
• 11 Oct Midterm 1 sample questions and answers
  Finished JCIP Chap 8, with particular emphasis on the puzzle solving framework. We also went over these slides on Fork-Join parallelism. The example from the slides, fully implemented, is in the files MaxProblem.java and MaxSolver.java (the latter has a main method you can run); you will need to download the jsr166y.jar library from Doug Lea's concurrency interest page (which contains API documentation) and include it in your classpath; e.g., add it to your Eclipse project as an external library.
• 13 Oct Exam review
• 18 Oct Midterm 1 (solutions)
  
• 20 Oct JCIP Chap 10. Went over deadlock example from book; runnable code in deadlock.tgz. To run this, unpack it, and compile and execute the class net.jcip.examples.DemonstrateDeadlock. If you pass it no arguments, it will deadlock quickly. If you pass it the argument "ok" it should avoid deadlock by forcing a lock ordering, as we discussed in class.
• 25 Oct JCIP Chap 11; slides. Discussed various performance measures, focusing on the distinction between parallelizable, and serial work. Discussed Amdahl's law, and considered how to compute the F parameter by observing parallel performance; did so with a modified version of word counting (in which all file reading happens before parallel counting) in WordCountParallelScale.java. Compared two implementations of a striped-lock-based HashMap. StripedMapBad.java keeps a running count of the size of the HashMap, but this is bad because it serializes all writing threads, and may result in a Deadlock. The more naive approach in StripedMap.java, while doing more serial work, may actually perform better due to reduced synchronization. The best solution may be to maintain a striped counter, and then add these up, as in StripedMapBest.java.
• 1 Nov JCIP Chap 15 on non-blocking synchronization. Examples: nonBlockingExamples.tgz. Lecture slides, and trace run of ConcurrentQueue.put. Here is the original Michael and Scott paper on a non-blocking queue.
• 3 Nov Introduction to Erlang. Required reading: Erlang by Joe Armstrong. I would also recommend the Erlang tutorial.
  The Erlang language is freely available; you can also download an Eclipse plugin for Erlang development. Erlang has been installed on the Linuxlab machines, if you have trouble installing it on your laptop/desktop. Here is the Erlang manual, and in particular Erlang standard library documentation.
• 8 Nov Erlang for Concurrent Programming, by Jim Larson (Google). We went over the programs sequence1.erl, server.erl, and sequence2.erl that appear in the paper. We also considered a faulty implementation of sequence1.erl that has an atomicity violation (in the paper, this example uses the server framework, but in class we coded it up directly). We also constructed a semaphore in Erlang, which examplifies synchronizing messages from different process, as in this join.erl example.
• 10 Nov Project 4 is posted
  We went over the basic design of project 4 in class and all of the skeleton code that's provided with it, covering several Erlang language features and libraries along the way. We also reimplemented semaphore to be cancelable, and showed how to construct from it a Blocking queue (in blockingqueue.erl). Finally we measured process creation times (see processes.erl) and found them to be really small!
• 15 Nov Midterm 2 study questions are now available.
  We went over the generalization of the receive primitive that includes a timout. Some examples are in receivemod.erl; a function countdown timer (execute the given function after the given timeout) is defined in stimer.erl. Next, we considered a parallel version of the well-known map function, in pmap.erl, which we ran using the ptests.erl module, invoked from the runtests script (which you could run on Linuxlab); it runs the Erlang interpreter with an increasing number of OS threads at its disposal. (If you want to run from erl, just invoke ptests:runtests(1,N) for the number of OS threads you started erl to use).
• 17 Nov Went over mapreduce, in Erlang: test_mapreduce.erl, phofs.erl, and lib_find.erl. Here is a description Google's mapreduce architecture, and the slides we used in class.
• 20 Nov (Updated) Solutions to midterm 2 study questions are now available.
  
• 22 Nov Midterm 2
• 24 Nov Went over the answers to midterm 2
• 29 Nov Guest lecture: Victor Luchangco
• 1 Dec distributed computing
• 6 Dec Dynamic Software Updating
• 8 Dec Code updating in Erlang (this is a .zip file containing the examples we went over in class), and distributed programming and error handling in Erlang.

Web Accessibility