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 2N
PD/Parallel Decomposition13N
PD/Communication and Coordination13Y
PD/Parallel Algorithms, Analysis, and Programming3Y
PD/Parallel Architecture11Y
PD/Parallel PerformanceY
PD/Distributed SystemsY
PD/Cloud ComputingY
PD/Formal Models and SemanticsY

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]
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.
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)
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
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
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
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
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)