CS2013 View
This view classifies PDC unplugged activities by their associated Knowledge Units (KU) and Learning Outcomes (LO) as specified by the ACM/IEEE Computer Science Curricula 2013 (CS2013) Parallel and Distributed (PD) knowledge area. CS2013 recommends coverage of all LOs in Core Tier 1, and at least 80% of coverage of LOs in Core Tier 2, and a "significant" level of cover of elective LOs. The following table from CS2013 gives an outline of topic coverage over the different KUs:
| Core-Tier1 hours | Core-Tier2 hours | Electives? | |
|---|---|---|---|
| PD/Parallelism Fundamentals | 2 | N | |
| PD/Parallel Decomposition | 1 | 3 | N |
| PD/Communication and Coordination | 1 | 3 | Y |
| PD/Parallel Algorithms, Analysis, and Programming | 3 | Y | |
| PD/Parallel Architecture | 1 | 1 | Y |
| PD/Parallel Performance | Y | ||
| PD/Distributed Systems | Y | ||
| PD/Cloud Computing | Y | ||
| PD/Formal Models and Semantics | Y |
Parallelism Fundamentals (2 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| 1. Distinguish using computational resources for a faster answer from managing efficient access to a shared resource. [Familiarity] | MoreProcessorsNotAlwaysBetter; See All (1) |
| 2. Distinguish multiple sufficient programming constructs for synchronization that may be inter-implementable but have complementary advantages. [Familiarity] | ArrayAddition; See All (1) |
| 3. Distinguish data races from higher level races. [Familiarity] |
Parallel Decomposition (21 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Core Tier 1 | |
| 1. Explain why synchronization is necessary in a specific parallel program. [Usage] | SurvivorAnalogy; PlantingTrees; See All (8) |
| 2. Identify opportunities to partition a serial program into independent parallel modules. [Familiarity] | PlantingTrees; ArrayAddition; See All (14) |
| Core Tier 2 | |
| 3. Write a correct and scalable parallel algorithm. [Usage] | PlantingTrees; See All (1) |
| 4. Parallelize an algorithm by applying task-based decomposition. [Usage] | PlantingTrees; StuffingEnvelopes; See All (7) |
| 5. Parallelize an algorithm by applying data-parallel decomposition. [Usage] | PlantingTrees; StuffingEnvelopes; See All (6) |
| 6. Write a program using actors and/or reactive processes. [Usage] |
Communication and Coordination (9 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Core Tier 1 | |
| 1. Use mutual exclusion to avoid a given race condition. [Usage] | SurvivorAnalogy; ArrayAddition; See All (4) |
| 2. Give an example of an ordering of accesses among concurrent activities (e.g., program with a data race) that is not sequentially consistent. [Familiarity] | ArrayAddition; ConcertTickets; See All (5) |
| Core Tier 2 | |
| 3. Give an example of a scenario in which blocking message sends can deadlock. [Usage] | OrangeGame; See All (1) |
| 4. Explain when and why multicast or event-based messaging can be preferable to alternatives. [Familiarity] | |
| 5. Write a program that correctly terminates when all of a set of concurrent tasks have completed. [Usage] | ArrayAddition; ConcertTickets; See All (3) |
| 6. Use a properly synchronized queue to buffer data passed among activities. [Usage] | |
| 7. Explain why checks for preconditions, and actions based on these checks, must share the same unit of atomicity to be effective. [Familiarity] | ConcertTickets; See All (1) |
| 8. Write a test program that can reveal a concurrent programming error; for example, missing an update when two activities both try to increment a variable. [Usage] | ArrayAddition; ParallelGarbageCollection; See All (4) |
| 9. Describe at least one design technique for avoiding liveness failures in programs using multiple locks or semaphores. [Familiarity] | |
| 10. Describe the relative merits of optimistic versus conservative concurrency control under different rates of contention among updates. [Familiarity] | |
| 11. Give an example of a scenario in which an attempted optimistic update may never complete. [Familiarity] | |
| Elective | 12. Use semaphores or condition variables to block threads until a necessary precondition holds. [Usage] |
Parallel Algorithms, Analysis, & Programming ( 12 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Core Tier 2 | |
| 1. Define "critical path", "work", and "span". [Familiarity] | |
| 2. Compute the work and span, and determine the critical path with respect to a parallel execution diagram. [Usage] | |
| 3. Define "speed-up" and explain the notion of an algorithm's scalability in this regard. [Familiarity] | ParallelAddition; FindSmallestCard; See All (5) |
| 4. Identify independent tasks in a program that may be parallelized. [Usage] | PlantingTrees; ArrayAddition; See All (11) |
| 5. Characterize features of a workload that allow or prevent it from being naturally parallelized. [Familiarity] | PlantingTrees; StuffingEnvelopes; See All (3) |
| 6. Implement a parallel divide-and-conquer (and/or graph algorithm) and empirically measure its performance relative to its sequential analog. | ParallelAddition; FindSmallestCard; See All (3) |
| 7. Decompose a problem (e.g., counting the number of occurrences of some word in a document) via map and reduce operations. | |
| Elective | |
| 8. Provide an example of a problem that fits the producer-consumer paradigm. [Familiarity] | |
| 9. Give examples of problems where pipelining would be an effective means of parallelization. [Familiarity] | PlantingTrees; StuffingEnvelopes; See All (4) |
| 10. Implement a parallel matrix algorithm. [Usage] | MatrixAddition; See All (1) |
| 11. Identify issues that arise in producer-consumer algorithms and mechanisms that may be used for addressing them. [Familiarity] |
Parallel Architecture (9 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Core Tier 1 | |
| 1. Explain the differences between shared and distributed memory. [Familiarity] [Core-Tier2] | DesertIslandsAnalogy; JigsawPuzzle; See All (5) |
| Core Tier 2 | |
| 2. Describe the SMP architecture and note its key features. [Familiarity] | CompanyAnalogy; See All (1) |
| 3. Characterize the kinds of tasks that are a natural match for SIMD machines. [Familiarity] | CoinFlip; DesertIslandsAnalogy; See All (2) |
| Elective | |
| 4. Describe the advantages and limitations of GPUs vs. CPUs. [Familiarity] | CoinFlip; DesertIslandsAnalogy; See All (2) |
| 5. Explain the features of each classification in Flynn's taxonomy. [Familiarity] | DesertIslandsAnalogy; See All (1) |
| 6. Describe assembly-level support for atomic operations. [Familiarity] | |
| 7. Describe the challenges in maintaining cache coherence. [Familiarity] | KitchenAnalogy; See All (1) |
| 8. Describe the key performance challenges in different memory and distributed system topologies. [Familiarity] | LongDistancePhoneCall; DesertIslandsAnalogy; See All (4) |
Parallel Performance (10 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Elective | |
| 1. Detect and correct a load imbalance. [Usage] | PlantingTrees; FindOldestPenny; See All (6) |
| 2. Calculate the implications of Amdahl's law for a particular parallel algorithm (cross-reference SF/Evaluation for Amdahl's Law). [Usage] | MoreProcessorsNotAlwaysBetter; FindOldestPenny; See All (4) |
| 3. Describe how data distribution/layout can affect an algorithm's communication costs. [Familiarity] | DesertIslandsAnalogy; JigsawPuzzle; See All (5) |
| 4. Detect and correct an instance of false sharing. [Usage] | KitchenAnalogy; See All (1) |
| 5. Explain the impact of scheduling on parallel performance. [Familiarity] | JigsawPuzzle; See All (1) |
| 6. Explain performance impacts of data locality. [Familiarity] | KitchenAnalogy; See All (1) |
| 7. Explain the impact and trade-off related to power usage on parallel performance. [Familiarity] |
Distributed Systems (2 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Elective | |
| 1. Distinguish network faults from other kinds of failures. [Familiarity] | |
| 2. Explain why synchronization constructs such as simple locks are not useful in the presence of distributed faults. [Familiarity] | |
| 3. Write a program that performs any required marshaling and conversion into message units, such as packets, to communicate interesting data between two hosts. [Usage] | |
| 4. Measure the observed throughput and response latency across hosts in a given network. [Usage] | |
| 5. Explain why no distributed system can be simultaneously consistent, available, and partition tolerant. [Familiarity] | |
| 6. Implement a simple server -- for example, a spell checking service. [Usage] | |
| 7. Explain the tradeoffs among overhead, scalability, and fault tolerance when choosing a stateful v. stateless design for a given service. [Familiarity] | |
| 8. Describe the scalability challenges associated with a service growing to accommodate many clients, as well as those associated with a service only transiently having many clients. [Familiarity] | |
| 9. Give examples of problems for which consensus algorithms such as leader election are required. [Usage] | StabalizingLeaderElection; ByzantineGenerals; See All (2) |
Cloud Computing (3 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Elective | |
| 1. Discuss the importance of elasticity and resource management in cloud computing. [Familiarity] | |
| 2. Explain strategies to synchronize a common view of shared data across a collection of devices.[Familiarity] | StabalizingLeaderElection; ConcertTickets; See All (3) |
| 3. Explain the advantages and disadvantages of using virtualized infrastructure. [Familiarity] | |
| 4. Deploy an application that uses cloud infrastructure for computing and/or data resources. [Usage] | |
| 5. Appropriately partition an application between a client and resources. [Usage] |
Formal Models and Semantics (1 Activities )
| Learning Outcome | Unplugged Activities |
|---|---|
| Elective | |
| 1. Model a concurrent process using a formal model, such as pi-calculus. [Usage] | |
| 2. Explain the characteristics of a particular formal parallel model. [Familiarity] | |
| 3. Formally model a shared memory system to show if it is consistent. [Usage] | |
| 4. Use a model to show progress guarantees in a parallel algorithm. [Usage] | |
| 5. Use formal techniques to show that a parallel algorithm is correct with respect to a safety or liveness property. [Usage] | |
| 6. Decide if a specific execution is linearizable or not. [Usage] | NondeterministicSorting; See All (1) |