PDC CS Core – CS2023

PDC-A: Programs and Execution

Definitions and properties
1. Parallelizable actions
  1. Including closures, functions, and services
  2. Composite actions; sessions, tasks; scopes
  3. Naming or identifying actions as parties (for example thread IDs)
  4. Impact of granularity and overhead
2. Ordering among actions; happens-before relations
  1. Relaxing ordering constraints permits nondeterministic execution of the series/parallel directed acyclic graphs representing program components
3. Independence: determining when ordering doesn’t matter, in terms of commutativity, dependencies, preconditions
4. Consistency: Agreement about values and predicates; races, atomicity, consensus
5. Ensuring ordering when necessary in parallel programs
  1. For example locking, safe publication
  2. Communication among parties may impose ordering among their actions. As in: sending a message happens before receiving it
6. Places: Physical devices executing parallel actions (parties)
  1. Hardware components, remote hosts
  2. Places may support multiple parties (in sequence or schedule)
  3. Parties may include external and human users
  4. May include scheduling, time-slicing and emulation of multiple parallel actions by fewer processors
7. Faults arising from failures in parties or communication
  1. Failures may be due to untrusted parties and protocols not under the control of the program or administrative domain
  2. Degree of fault tolerance may be a design choice
Starting parallel actions
1. Placement: arranging that the action be performed (eventually) by a designated party
  1. Details range from hardwiring to configuration scripts, or relying on automated provisioning and management by platforms
  2. Establishing communication and resource management
2. Procedural: Enabling multiple actions to start at a given program point
  1. For example, starting new threads
  2. May be contained in a scope ending when all complete
3. Reactive: Enabling upon an event
  1. For example, installing event handlers
  2. Less control of when actions begin or end
4. Dependent: Enabling upon completion of others
  1. For example, sequencing

PDC-B: Communication

Fundamentals
1. Media
  1. Varieties: channels (message passing or IO), shared memory, heterogeneous, data stores
  2. Reliance on the availability and nature of underlying hardware, connectivity, and protocols; language support, emulation
2. Channels
  1. Explicit party-to-party communication; naming
  2. APIs: sockets, architectural and language-based channel constructs
3. Memory
  1. Architectures in which parties directly communicate only with memory at given addresses
  2. Consistency: Bitwise atomicity limits, coherence, local ordering
  3. Memory hierarchies, locality: caches, latency, false-sharing
  4. Heterogeneous Memory using multiple memory stores, with explicit data transfer across them; for example, GPU local and shared memory, DMA
  5. Multiple layers of sharing domains, scopes and caches
4. Data Stores
  1. Cooperatively maintained structured data implementing maps, sets, and related ADTs
  2. Varieties: Owned, shared, sharded, replicated, immutable, versioned
Programming with communication
1. Using channel, socket, and/or remote procedure call APIs
2. Using shared memory constructs in a given language

PDC-C: Coordination

Fundamentals
1. Dependent actions
  1. Execution control when one activity’s initiation or progress depends on actions of others
  2. Completion-based: Barriers, joins
  3. Data-enabled: Produce-Consumer designs
  4. Condition-based: Polling, retrying, backoffs, helping, suspension, queueing, signaling, timeouts
  5. Reactive: enabling and triggering continuations
2. Progress
  1. Dependency cycles and deadlock; monotonicity of conditions
3. Atomicity
  1. Atomic instructions, enforced local access orderings
  2. Locks and mutual exclusion
  3. Deadlock avoidance: ordering, coarsening, randomized retries; encapsulation via lock managers
  4. Common errors: failing to lock or unlock when necessary, holding locks while invoking unknown operations, deadlock
4. Programming with coordination
  1. Controlling termination
  2. Using locks, barriers, and other synchronizers in a given language; maintaining liveness without introducing races
  3. Using transactional APIs in a given framework

PDC-D: Software Engineering

Safety, liveness and performance requirements
1. Temporal logic constructs to express “always” and “eventually”
2. Metrics for throughput, responsiveness, latency, availability, energy consumption, scalability, resource usage, communication costs, waiting and rate control, fairness; service level agreements
Identifying, testing for, and repairing violations
1. Common forms of errors: failure to ensure necessary ordering (race errors), atomicity (including check-then-act errors), or termination (livelock)..

PDC-E: Algorithms and Application Domains

Expressing and implementing parallel and distributed algorithms
1. Implementing concepts in given languages and frameworks to initiate activities (for example threads), use shared memory constructs, and channel, socket, and/or remote procedure call APIs
Survey:

Category	Typical Execution agents	Typical Communication mechanisms	Typical Algorithmic domains	Typical Engineering goals
Multicore	threads	Shared memory, Atomics, locks	Resource management, data processing	throughput, latency, energy
Reactive	Handlers, threads	IO Channels	Services, real-time	latency
Data parallel	GPU, SIMD, accelerators, hybrid	Heterogeneous memory	Linear algebra, graphics, data analysis	throughput, energy
Cluster	Managed hosts	Sockets, Message channels	Simulation, data analysis	throughput
Cloud	Provisioned hosts	Service APIs	Web applications	scalability
Open Distributed	Autonomous hosts	Sockets, Data stores	Fault tolerant data stores and services	reliability