Outline for CS202xPD Parallel and Distributed Programming

Extracted from PDOverview

	CS Core hours	KA Core hours	Includes Electives
PD/Fundamentals	2		N
PD/Execution	2		Y
PD/Communication	2		Y
PD/Specification and Analysis			Y
PD/Implementation			Y
PD/Applications			Y

PD/Fundamentals [Note: Xrefs with SF]

Forms and styles: Declarative, procedural, reactive (event-driven), distributed
Properties: Nondeterminism; Emulation and scheduling, Communication, consensus, correctness, resources.
Metrics: Throughput, responsiveness, availability, latency, resource usage, communication costs, waiting and rate control, energy

PD/Execution [Note: Xrefs with PL]

Parallelizable actions: granularity, functional forms, sessions, services, atomicity.
Activation: Internal CPU data parallelism, Heterogeneous data parallelism, task parallelism, Actors, Clusters, Distributed systems, Emerging technologies
Sequencing Actions: Clocks. Counters and virtual clocks. Consensus, Dataflow and continuations. joins and Futures, collectors.
Exceptions and failures. Handlers, detection, timeouts, fault tolerance.
Control structures: Loops, recursion, nested parallelism, pipelines, series-parallel loops

PD/Communication

Channels [Note: Many Xrefs to NC]
- Topologies: Unicast (one-to-one, aka point-to-point), Multicast (one-to-many, aka multiplexers, publishers; groups). Mailbox (many-to-one, aka demultiplexers, collectors, selectors). Switches (many-to-many, aka buses, crossbars).
- Security: integrity, privacy, authentication, authorization.
- Performance Characteristics: Latency, Bandwidth (throughput), Contention (Congestion) Responsiveness. (liveness).
- Policies and protocols: Endpoints, Sessions, Buffering, Saturation (waiting vs dropping), Rate control.
- Data: Formats, marshaling, encryption, integrity checking, compressIon.
Shared Memory
- Memory Consistency: Bitwise Atomicity limits, Coherence, Local ordering.
- Memory locality: caches, false-sharing
- Preventing Data races: Atomic updates, Enforced ordering, locks, transactions, channels
- Coordination: State-based, data structures, synchronizers, completions

Data Stores [Note: Xrefs with IM]
- Categories: Shared memory, owned, sharded, replicated, immutable, versioned
- Atomicity: transactions, concurrent reads, locks
- Consistency and consensus protocols: atomicity, coherence, causal ordering, conflict resolution/eventual consistency, example protocols (paxos, raft)
- Security and trust: Byzantine failures, trust, proof of work and alternatives

PD/Specification and analysis [note: SE Xrefs]

Specifying behavior: Sequential specs, linearizability; protocol specs, safety, liveness, program logics, spec languages such as TLA
Characterizing errors: data races, check-then-act, deadlocks, tools
Performance
- Throughput (scalability): dag model analysis: work/span, Amdahl’s law; factoring in overhead, waiting/contention, communication, data movement, locality, resource management, scheduling
- Latency: waiting, faults, fairness
- Resource consumption (Energy): work efficiency, utilization, communication complexity

PD/Implementation [Note: Xrefs with SF, OS]

Placement and Scheduling
- centralized, decentralized, priorities, metrics, latency
Resource Management
- Management of serially reusable exclusively held resources. Locks, semaphores, sessions. Policies including load balancing and fairness.
- Sharable resources. Reference use counts, garbage collection.
- Preemptable resources. Eviction, context-switching, task scheduling.
- Exhaustion handling. Elasticity, cancellation, termination,

PD/Applications

Domain-specific algorithms and techniques in:

Linear Algebra: Matrix operations, numerical precision/stability, applications in data analytics and machine learning
Graphs, search, and combinatorics: Marking, edge-parallelization, bounding, speculation,
Modeling and simulation: differential equations; randomization, N-body problems
Logic: SAT, concurrent logic programming
Graphics: Transforms, …