CMSC 433, Fall 2010
Programming Language Technologies and Paradigms
- 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
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
- 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
- 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,
- 20 Sep, JCIP chapters 3 and 4. Examples used in
- 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
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
(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:
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.
"chunks" the units of work but executes them sequentially.
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.
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.
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
- 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
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
- 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.
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
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
- 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,
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
- 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.