Exam 1 topics

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides) for use as a reference during the exam.

Students should be able to…

• Write code, debug code, predict output, or otherwise demonstrate fluency with threaded programming in Java.
• Formulate a problem as a fork/join problem, both in the abstract as well as in Java using both regular threads as well as the ForkJoin library.
• Discuss and consider how one chooses how many threads to use in solving a problem.
• Use, justify, and evaluate tradeoffs involved regarding a sequential cutoff.
• Define and measure work, span, speedup, and parallelism in general as well as for specific problems.
• Analyze in a big-O sense the above metrics for ForkJoin, or for other sorts of situations as specified.
• State, interpret, derive, and/or evaluate Amdahl's Law and Gustafson's Law in general or for specific problems.
• Code, trace, and/or interpret parallel prefix sum. Be able to demonstrate how it works. Derive, justify, or analyze big-O complexity for it.
• Code, trace, and/or interpret parallel pack. Be able to demonstrate how it works. Derive, justify, or analyze big-O complexity for it.
• Code, trace, and/or interpret parallel quicksort. Be able to demonstrate how it works. Derive, justify, or analyze big-O complexity for it, at least at a high level.
• Define mutual exclusion, critical section. Interpret an interleaving schedule, or produce one to demonstrate a particular issue with provided code.
• Use locks in Java via synchronized blocks or methods. Demonstrate fluency with how they work.
• Define and distinguish data races and bad interleavings.
• Demonstrate and justify how data races can lead to buggy code.
• Analyze the impact of potential code reordering as well as processor caching on a particular program.
• Define what volatile does, and successfully use it as needed.
• Define deadlocks, detect them in code, interpret or create a schedule demonstrating if a deadlock can occur in a particular program. Rewrite code to avoid deadlocks.
• Define and interpret reentrant locks, reader/writer locks and condition variables (wait/notify). Be able to predict the output, or be able to write, pseudocode that uses them.
• Explain and justify the value of software transactional memory. Answer specific questions about how STM is being implemented in our assignment, and why. Define and distinguish between lazy vs. eager STM.