4. Parallel Computing Models and Algorithm Design

Introduction and Context

High-performance computing (HPC) is not achieved merely by purchasing faster processors. Its effectiveness depends on expressing computational work in a form that can be executed concurrently, assigning that work intelligently to processing resources, and controlling the costs of communication, synchronization, memory access, and coordination. Parallel algorithm design is therefore a central intellectual activity in data science and HPC.

A sequential algorithm presents one logical stream of operations. A parallel algorithm identifies operations that can proceed simultaneously, determines the relationships among them, and maps them onto processors, cores, threads, accelerators, or distributed machines. This transformation is not automatic. Some problems contain substantial inherent parallelism, while others are constrained by dependencies or irregular workloads. A successful design must therefore balance theoretical speedup with practical concerns such as memory hierarchy, network latency, fault tolerance, programmability, and energy consumption.

This chapter develops the principal models and design decisions used in parallel computing. It focuses on task and data parallelism, decomposition, mapping, granularity, dependencies, synchronization, communication, load balancing, and work–span analysis. These ideas provide a foundation for later study of shared-memory programming, message passing, GPU computing, distributed data processing, and parallel performance evaluation.

Learning Objectives

After studying this chapter, students should be able to:

1. Distinguish task parallelism from data parallelism and select an appropriate model for a problem.

2. Decompose algorithms into tasks or data partitions while preserving correctness.

3. Analyse dependencies, communication, synchronization, granularity, and load balance.

4. Apply work–span analysis and related speedup bounds to parallel algorithms.

5. Design scalable strategies for common data-science workloads.

6. Evaluate trade-offs involving performance, portability, cost, maintainability, and reliability.

A Vocabulary for Parallel Algorithm Design

A parallelism opportunity exists when two or more operations can execute concurrently without changing the required result. Concurrency refers to the logical existence of overlapping activities; parallel execution refers to their simultaneous execution on different hardware resources. These concepts are related but not identical: a system may support concurrency even when only one processor is available through time sharing.

A task is a unit of work that can be scheduled independently or as part of a dependency graph. Data parallelism applies the same operation to multiple data elements or partitions. Task parallelism assigns different operations, often with different functions, to concurrent workers. Pipeline parallelism divides a computation into stages so that different inputs occupy different stages simultaneously.

A dependency is a requirement that one operation obtain data or a condition from another operation. A directed acyclic graph (DAG) represents tasks as vertices and dependencies as edges. The critical path is the longest dependency path in the DAG. Its length, called the span, limits the shortest possible execution time under an ideal unlimited-processor assumption.

Decomposition divides a problem into components. Mapping assigns those components to processing resources. Granularity describes the amount of computation per parallel unit. Fine-grained work creates many scheduling opportunities but may incur excessive coordination overhead; coarse-grained work reduces overhead but can limit flexibility and load balance.

Load balancing attempts to distribute work so that processors remain productively occupied. Synchronization coordinates concurrent activities, while communication transfers data or control information among them. Contention occurs when workers compete for a shared resource, such as a memory bus, lock, cache, or network link.

Models of Parallelism

Data Parallelism

In data parallelism, the same operation is performed on separate portions of a dataset. For example, each element of a vector may be multiplied by a constant, or each image pixel may undergo the same transformation. If the operation on one element does not depend on another, the data can be partitioned among workers with little coordination.

Data parallelism is particularly suitable for vector and matrix operations, image processing, statistical transformations, and many stages of machine-learning pipelines. Its major advantages are regularity, simple reasoning, and efficient use of SIMD instructions and GPUs. Its limitations arise when data elements have unequal workloads, irregular memory access, or strong inter-element dependencies.

Consider vector addition:

`C[i] = A[i] + B[i]`

Each output element depends only on `A[i]` and `B[i]`, so the array can be divided into contiguous blocks, cyclic portions, or tiles. Contiguous blocks often improve cache locality, whereas cyclic assignment may improve balance when the cost of processing elements varies periodically.

Task Parallelism

Task parallelism exposes different operations that may execute concurrently. In a data-analytics workflow, one task may parse input, another may build an index, and another may compute summary statistics. In a recursive algorithm, each subproblem can become a task whose execution is governed by a task graph.

Task parallelism is useful when operations differ in function or when a computation has an irregular structure. However, tasks may have unequal duration, and the runtime must manage dependencies and scheduling. Excessively small tasks can cause scheduling overhead, while excessively large tasks reduce available parallelism.

Pipeline Parallelism

Pipeline parallelism organizes work into stages. A streaming application might contain stages for reading records, parsing them, transforming fields, and writing results. Once the pipeline is full, several records can be processed simultaneously, one in each stage.

The throughput of a pipeline is constrained by its slowest stage. Buffers between stages absorb temporary differences in processing speed, but they also consume memory and can introduce latency. Pipeline design must therefore consider both throughput and end-to-end response time.

Hybrid Parallelism

Real applications frequently combine models. A distributed machine-learning system may use data parallelism across nodes, task parallelism among preprocessing stages, and thread-level parallelism within each node. Hybrid designs can exploit hardware effectively, but they increase the complexity of performance analysis and debugging.

From Problem to Parallel Algorithm

Decomposition

Decomposition is the first major design decision. A problem may be decomposed by data, function, or recursive structure. Data decomposition divides a dataset into regions; functional decomposition separates distinct operations; recursive decomposition repeatedly divides a problem into smaller instances.

A good decomposition should expose sufficient parallelism, preserve locality, minimize communication, and permit independent progress. It must also preserve the semantics of the original algorithm. Decomposing a computation simply because its code contains several functions can be misleading if those functions are tightly dependent.

For a two-dimensional image, decomposition into rectangular tiles is often effective because neighbouring pixels are close in memory and most operations require only local neighbourhood information. For a graph, however, partitions may have irregular boundaries and widely distributed edges, making communication and balance more difficult.

Dependency Analysis

Dependencies determine which operations may safely overlap. A read-after-write dependency occurs when an operation must read a value produced by another operation. A write-after-read dependency occurs when a later write must not occur before an earlier read. A write-after-write dependency requires an ordering between competing updates.

The dependency graph should be simplified where possible. For example, reductions such as summation have an associative structure that permits a tree of partial sums rather than a sequential chain. Floating-point addition is not perfectly associative, however, so a parallel reduction may produce slightly different rounding results. Numerical reproducibility may require a fixed reduction tree or compensated arithmetic.

Mapping and Scheduling

After decomposition, units of work must be mapped to resources. Static mapping assigns work before execution. It has low runtime overhead and is effective when workloads are predictable. Dynamic mapping assigns work as processors become available. It adapts to irregular workloads but requires scheduling overhead and may reduce locality.

Common strategies include block mapping, cyclic mapping, block-cyclic mapping, work queues, and work stealing. Block mapping gives each worker a contiguous region. Cyclic mapping distributes successive units among workers and can smooth variation. Block-cyclic mapping combines locality with improved balance and is widely used in dense linear algebra.

Work stealing allows an idle worker to take tasks from another worker's queue. It is effective for irregular recursive computations, although task movement can harm locality and create synchronization costs.

Granularity

Granularity is the ratio between useful computation and management overhead. If a task performs only a few instructions but requires queue operations, synchronization, and data transfer, parallel execution may be slower than sequential execution. If each task is too large, processors may become idle near the end of the computation.

Granularity is often adjusted hierarchically. A large dataset may be partitioned across nodes, each node may divide its portion among threads, and each thread may use vector instructions on small contiguous chunks. This hierarchical approach matches the levels of modern hardware while avoiding an excessive number of globally managed tasks.

Communication and Synchronization

Communication is often more expensive than arithmetic. In shared memory, communication may involve cache coherence and memory traffic. In distributed memory, it involves message latency, bandwidth, serialization, and network contention. An algorithm that minimizes arithmetic operations may nevertheless perform poorly if it repeatedly transfers data.

Communication can be reduced by increasing data locality, reusing values in caches, aggregating messages, and choosing decompositions that minimize boundary exchange. In matrix multiplication, tiling allows a block of data to be reused many times after it has been loaded into fast memory. In stencil computations, each process exchanges only boundary or halo values with neighbouring processes.

Synchronization establishes an ordering or coordination point. A barrier forces participating workers to wait until all have arrived. Locks provide mutual exclusion but may cause blocking, contention, and deadlock. Atomic operations update shared values indivisibly and are useful for counters and some reductions. Collective operations, such as broadcast, scatter, gather, and reduction, provide structured communication in distributed systems.

Synchronization should be used only where correctness requires it. Unnecessary barriers convert independent work into serialized phases. A safer design often uses immutable data, ownership rules, local accumulation followed by reduction, or message passing rather than unrestricted shared updates.

Work–Span Analysis and Scalability

Work–span analysis provides a machine-independent way to reason about parallel algorithms. Work, written `T1`, is the total number of operations performed by the algorithm on one processor. Span, written `T∞`, is the length of the longest chain of dependent operations. With `P` processors, an ideal lower bound is:

`TP ≥ max(T1/P, T∞)`

The first term expresses limited total work; the second expresses the critical-path limitation. The parallelism available in the computation is approximately:

`T1 / T∞`

If the number of processors greatly exceeds this value, additional processors cannot provide proportional speedup. A related upper bound is Brent's theorem, which states informally that a computation can often be scheduled in approximately `T1/P + T∞` time, ignoring machine-specific overheads.

For a balanced binary tree reduction of `n` values, the work is `O(n)` and the span is `O(log n)`. A sequential reduction has the same work but span `O(n)`. Thus the tree structure exposes much more parallelism. For a prefix sum, work-efficient algorithms also achieve `O(n)` work and `O(log n)` span, although their implementation requires careful handling of upsweep and downsweep phases.

Work–span analysis does not replace benchmarking. It generally omits cache effects, communication, synchronization costs, memory capacity, and unequal task sizes. Nevertheless, it reveals whether poor performance is caused by insufficient algorithmic parallelism or by implementation overhead.

Designing Common Parallel Patterns

A map applies an independent function to every element. It is usually highly parallel and benefits from contiguous partitioning and vectorization. A reduce combines many values into one result. Tree reductions shorten the critical path but require attention to associativity, numerical accuracy, and synchronization.

A scan computes all prefix results, such as cumulative sums. It is more difficult than a reduction because each output depends on earlier values, but tree-based methods provide logarithmic span. A stencil updates each point from a fixed neighbourhood. It is data parallel, but each iteration typically requires halo exchange and may need global synchronization between time steps.

A divide-and-conquer algorithm recursively creates subproblems. Parallelism is often abundant near the upper levels, while tasks become too small near the leaves. A cutoff threshold is therefore used: above the threshold, subproblems become tasks; below it, sequential computation avoids scheduling overhead.

A producer–consumer pattern separates generation from processing using a bounded queue. It is useful for streaming and pipelines, but the queue must be sized carefully. An unbounded queue risks memory exhaustion, while a very small queue can cause unnecessary blocking.

Applied Scenario: Parallel Fraud-Detection Feature Generation

Background

Consider an illustrative financial-services platform that processes millions of transaction records each day. For every transaction, the system computes features such as customer history, merchant frequency, rolling averages, and geographic distance. These features are later used by a fraud-classification model.

Situation and Problem

The original implementation processes records sequentially. Runtime increases sharply during peak periods, and simply adding workers produces limited improvement because multiple stages repeatedly access shared customer histories and because some customers have far more transactions than others.

Analysis

The workload contains both data and task parallelism. Feature calculations for unrelated transactions can often proceed concurrently, but transactions belonging to the same customer may require ordered updates. The customer-history structure is also a shared resource. A naive global lock would serialize much of the computation. In addition, partitioning solely by transaction count would be unbalanced because feature complexity varies by customer and time window.

Approach

The design first partitions records by customer or customer group, preserving the locality of stateful history. Each partition becomes a coarse-grained task. Within a partition, independent feature calculations use data parallelism, while ordered updates are performed locally. A final stage combines partition-level outputs.

Dynamic scheduling is used because partitions differ in size. Rather than updating a global feature table, workers maintain local state and periodically merge results. The system applies a bounded pipeline: ingestion, partitioning, feature computation, and model scoring operate concurrently. Monitoring records task duration, queue length, memory use, and communication volume.

Outcome

The design improves scalability because it reduces global contention, increases locality, and assigns work according to actual task cost. It also makes correctness easier to reason about: ordering constraints are explicit within partitions, while independent partitions proceed concurrently. The main remaining limitation is skew. A small number of exceptionally active customers may still create long-running partitions, requiring adaptive repartitioning or splitting of state with carefully defined ordering semantics.

Learning Points

The scenario illustrates that parallelism is not obtained by placing a loop inside a parallel construct. The designer must identify dependencies, choose an ownership strategy for shared state, select an appropriate granularity, and measure imbalance. It also demonstrates why data partitioning and task scheduling are closely related design decisions.

Challenges, Risks, and Common Mistakes

A common mistake is parallelizing a loop whose iterations share mutable state. This can produce races, lost updates, or nondeterministic results. Another mistake is assuming that more workers always improve performance. Once memory bandwidth, synchronization, or the critical path becomes dominant, additional workers may have little effect or may reduce performance.

False sharing occurs when independent variables used by different threads occupy the same cache line, causing unnecessary coherence traffic. Oversubscription occurs when more software threads are created than the hardware can efficiently execute. Both problems can be detected through profiling and hardware-performance counters.

Irregular data structures create challenges for both balance and locality. Graph algorithms, sparse matrices, and recursive search often need dynamic scheduling. However, dynamic scheduling can introduce nondeterminism, complicate debugging, and make results less reproducible.

Numerical algorithms require special care. Different execution orders can change floating-point results, particularly in reductions. Exact reproducibility may be essential in scientific, financial, or regulated applications. The design may need deterministic task ordering, stable reduction trees, interval methods, or explicit error analysis.

Deadlock is another risk in communication-heavy programs. It can arise when processes wait for messages that cannot be sent because each is waiting for another process. Consistent communication ordering, nonblocking operations used correctly, and structured collective operations reduce this risk.

Professional and Governance Considerations

Parallel systems should be designed with observability and accountability. Performance claims should be supported by reproducible benchmarks that specify input size, hardware, software versions, processor count, and measurement method. In production, monitoring should identify queue delays, failed tasks, stragglers, data-transfer volume, and resource saturation.

For data-science workloads, governance also includes protection of sensitive data during distributed processing. Partitioning should not unintentionally expose personal information, and logs should avoid recording confidential values. Access controls, encryption in transit, and appropriate retention policies remain necessary even when the primary goal is performance.

Energy efficiency is a professional concern. An algorithm with slightly lower peak speed may consume substantially less energy if it reduces data movement or avoids unnecessary synchronization. Sustainable HPC therefore considers energy per completed workload, not only elapsed time.

Current Developments and Best Practices

Modern systems increasingly combine CPUs, GPUs, specialized accelerators, high-bandwidth memory, and distributed storage. Algorithm designers must make parallelism explicit at several levels and move data carefully between memory spaces. Portable programming models seek to express computation once while allowing different back ends to target CPUs, GPUs, or clusters.

Task-based runtimes increasingly use dependency-aware scheduling, work stealing, and performance feedback. Distributed data frameworks provide partitioning, fault recovery, and data-local scheduling, but their abstractions do not eliminate the need to understand communication and skew.

Recommended practice is to begin with a correct sequential specification, identify dependencies, estimate work and span, choose a decomposition that preserves locality, and then introduce parallel execution incrementally. Measure at realistic data sizes. Compare strong scaling, where the problem size is fixed, with weak scaling, where the workload per processor remains approximately constant. Profile before optimizing, and treat communication and synchronization as first-class costs.

Chapter Summary

Parallel algorithm design transforms a sequential problem into coordinated concurrent work. Data parallelism applies similar operations to separate data, while task parallelism executes different operations or irregular subproblems. Decomposition exposes work; mapping assigns it to resources; granularity controls the balance between useful computation and management overhead.

Dependencies determine legal execution order, and DAGs make these relationships explicit. Communication transfers data among workers, while synchronization coordinates shared progress; both can limit scalability. Work–span analysis estimates the limits imposed by total work and the critical path. Effective algorithms combine suitable decomposition, locality, load balancing, controlled synchronization, and awareness of hardware characteristics.

In professional practice, scalability must be evaluated together with correctness, numerical reproducibility, observability, security, maintainability, cost, and energy use. Parallelism is therefore not simply a programming feature; it is a design discipline linking algorithms, architectures, data organization, and operational requirements.

Key Terms

Parallelism: The ability to perform multiple operations concurrently.

Concurrency: The logical overlap of multiple activities, whether or not they execute simultaneously.

Data parallelism: Applying the same operation to multiple data elements or partitions.

Task parallelism: Executing distinct tasks concurrently.

Pipeline parallelism: Overlapping different stages of processing for different inputs.

Decomposition: Dividing a problem into computational units.

Mapping: Assigning computational units to processing resources.

Granularity: The amount of computation contained in one parallel unit.

Dependency: A relationship requiring one operation to precede another.

DAG: A directed acyclic graph representing tasks and their dependencies.

Work: The total operations performed by a computation.

Span: The length of the longest dependency chain.

Critical path: The dependency path that determines the minimum possible parallel execution time.

Synchronization: Coordination that controls the relative progress of workers.

Communication: Transfer of data or control information among workers.

Load balancing: Distribution of work to keep processing resources similarly occupied.

Locality: The tendency to reuse nearby data and reduce costly movement.

Reduction: Combining multiple values into one result.

Work stealing: A scheduling method in which idle workers obtain tasks from busy workers.

False sharing: Performance loss caused by independent variables sharing a cache line.

Review Questions

Short Answer Questions

1. Distinguish concurrency from parallel execution.

2. What is the difference between data parallelism and task parallelism?

3. Define work and span in a parallel computation.

4. Why can excessive synchronization reduce scalability?

5. What is the purpose of a halo exchange in a stencil computation?

Long Answer Questions

1. Explain the stages of decomposition, mapping, scheduling, and execution in parallel algorithm design.

2. Discuss how granularity affects overhead, load balance, and scalability.

3. Explain dependency graphs and critical paths using a parallel reduction as an example.

4. Compare static scheduling, dynamic scheduling, and work stealing.

5. Discuss the relationship between communication, locality, synchronization, and performance.

Analytical / Application Questions

1. A computation performs `1,000` units of work and has a span of `100` units. Estimate the ideal lower-bound execution time on 20 processors and explain which limitation dominates.

2. Design a parallel strategy for processing a large image with a neighbourhood-based filter. Identify decomposition, communication, synchronization, and load-balancing decisions.

3. A transaction-processing workload contains a few extremely large customer partitions. Explain why block partitioning may fail and propose a strategy that improves balance without violating per-customer ordering requirements.

22. Multiple Choice Questions with Answers

Question 1

Which situation is most naturally suited to data parallelism?

A. Executing parsing, indexing, and reporting as separate stages

B. Applying the same transformation independently to every image pixel

C. Scheduling recursive tasks with unequal execution times

D. Coordinating producer and consumer processes

Correct Answer: B. Applying the same transformation independently to every image pixel

Question 2

In work–span analysis, what does the span represent?

A. The total number of operations

B. The average task size

C. The longest chain of dependent operations

D. The number of processors used

Correct Answer: C. The longest chain of dependent operations

Question 3

Why may dynamic scheduling be preferred for an irregular workload?

A. It eliminates all communication

B. It adapts assignment as task durations become evident

C. It guarantees perfect cache locality

D. It removes all synchronization costs

Correct Answer: B. It adapts assignment as task durations become evident

Question 4

A parallel reduction of n values using a balanced tree generally has which work and span?

A. O(log n) work and O(n) span

B. O(n) work and O(log n) span

C. O(n²) work and O(1) span

D. O(1) work and O(n) span

Correct Answer: B. O(n) work and O(log n) span

Question 5

Which design most directly reduces contention on a shared accumulator?

A. Using local accumulators followed by a final reduction

B. Adding a global barrier after every operation

C. Increasing the number of global locks

D. Assigning all updates to one processor

Correct Answer: A. Using local accumulators followed by a final reduction

Question 6

If a parallel algorithm has work T1 = 1,000 and span T∞ = 100, what is the ideal lower bound on execution time with 20 processors?

A. 20 units

B. 50 units

C. 100 units

D. 1,100 units

Correct Answer: C. 100 units

Question 7

What is the principal risk of using tasks that are too fine-grained?

A. Insufficient available parallelism

B. Excessive scheduling and synchronization overhead

C. Guaranteed numerical instability

D. Elimination of data locality in every case

Correct Answer: B. Excessive scheduling and synchronization overhead

Question 8

In a stencil computation distributed across processes, halo exchange is used primarily to:

A. Replicate the complete dataset on every process

B. Exchange boundary data needed by neighbouring partitions

C. Replace all synchronization with random scheduling

D. Convert task parallelism into pipeline parallelism

Correct Answer: B. Exchange boundary data needed by neighbouring partitions

Question 9

Which statement best describes false sharing?

A. Two processes receive identical input data

B. Independent variables on the same cache line cause coherence traffic

C. A task is copied to two worker queues

D. A reduction produces two mathematically equal results

Correct Answer: B. Independent variables on the same cache line cause coherence traffic

Question 10

A pipeline's steady-state throughput is principally limited by:

A. The fastest stage

B. The number of input records only

C. The slowest stage

D. The number of output formats

Correct Answer: C. The slowest stage