Parallel and Distributed Computation

8/26/2019

Opening Discussion

• Who’s teaching the class anyway?
• How I’m planning to proceed.

Terminology

• Concurrent - Computations scheduled to occur at intervals.
• Parallel - Multiple things actually happening at the same time.
• Multi-processing - Separate processes don’t share memory.
• Multi-threaded - Threads of execution do share memory.
• Distributed - Things running on different computers.
• Message Passing - Communication between processes/threads with messages.

Playing with Threads

• We can do most of the things that I care about with my CS2 starter project.
• https://github.com/MarkCLewis/CS2InClassStarter
• Clone or download this into a proper place.
• Let’s make sure it compiles with sbt.
• Then we can open the directory in VS Code.

Problems with Threads

• Multiprocessing is simple and generally handled by the OS. Just run a lot of things at once.
• Solving a single problem requires some level of communication. On a single machine this is done most commonly with multithreading.
• Do you recall the primary problems associated with multithreading?
• What are they?
• What causes each one?
• How can we get around them?

Solving Race Conditions

• Two or more threads accessing the same resource (normally memory) when at least one is changing it causes race conditions.
• The result of a calculation can vary based on thread scheduling or other things that appear random.
• Often creates Heisen-bugs
• Solutions:
• Immutable data - ideal when it works
• Synchronization - locks, mutexes, and other structures to control when threads execute
• Atomics - use lock-free mechanisms that are still thread safe

Deadlock

• Introducing locks can lead to a different problem. Threads can sit there waiting for an event that will never happen.
• This can happen in lots of different ways.
• Two threads set two locks in different orders.
• Something happens to a thread that causes it to not reach a critical point.
• Solutions:
• Try not to lock. Be very careful when you do.
• Use libraries that make it so you don’t have to do your own locking.

Lock-Free Parallel Computing

• Test-and-set or compare-and-swap atomic operations.
• This is how the members of the java.concurrent.atomic package work.
• Note that operations get repeated until they work. This is still generally faster than actually using a lock.

Parallel Loops

• Lots of operations are data parallel.
• Lots of languages/language extensions that are built for parallel processing include some way to run loops in parallel.
• Scala has parallel collections.
• Java has parallel streams.
• OpenMP parallel loops in C/C++.

Futures and Promises

• Common approach for avoiding race conditions and deadlock.
• Futures are objects that represent the result of a calculation that might not have completed yet.
• Promises are associated with futures and a promise is fulfilled to give a value to a future.
• JavaScript was created by people who simply have no idea.
• Composable futures use functional techniques to string together calculations.

Profiling and Measurement

• The goal of parallel is generally speed.
• Like all optimization, the only way to know if it helped is to get profiling information.
• https://www.mkyong.com/java/java-jmh-benchmark-tutorial/