Parallel computing: solve parts of a problem together

Discover how programs use multiple cores and processors, how to divide work safely, why parallel speedup has limits, and how to measure whether parallelism helps.

Concurrency and parallelism

Concurrency means multiple tasks make progress during overlapping periods. Parallelism means multiple computations run at the same time on separate execution units. A single processor can provide concurrency by switching between tasks; multiple cores can execute tasks in parallel.

Parallelism is a way to improve throughput or reduce the time for a large computation, but not every problem can be divided efficiently. Tasks must have enough independent work to offset the cost of creating workers, sharing or copying data, coordinating results, and communicating between processors.

Many applications use concurrency to remain responsive without aiming to finish one calculation faster. A user interface can handle input while another task downloads data. Parallel computing specifically uses multiple processing resources to perform computation simultaneously, though the two concepts often appear together.

Parallel hardware

Modern computers contain multiple CPU cores, and each core can execute instructions. Some processors support hardware threads that share parts of a core. A system can also use multiple machines connected by a network, or a graphics processing unit with many parallel arithmetic units.

Shared-memory systems let processors access a common address space, though caches and synchronization affect how changes become visible. Distributed-memory systems give each machine its own memory; processors exchange data by messages. A cluster combines many computers, so network latency and failure become part of the computation.

Architecture	Memory model	Important cost
Multicore CPU	Usually shared address space	Synchronization and memory contention
GPU	Many parallel lanes with device memory	Data transfer and workload divergence
Compute cluster	Separate memory per node	Network communication and coordination
Cloud workers	Independent instances and services	Provisioning, data movement, and reliability

Each architecture has a different balance of computation, memory, and communication. A method that works well on one machine may perform poorly when moved to a cluster if it requires frequent data exchange.

Task and data parallelism

Task parallelism runs different tasks at the same time. A media application might decode audio while rendering video. Data parallelism applies the same operation to many independent data items, such as transforming every pixel in an image.

A pipeline divides work into stages. One stage can process item B while the next processes item A. Pipelining increases throughput when stages have balanced work, but the slowest stage limits the rate.

Map and reduce pattern

A map-reduce style calculation applies a mapping function to independent pieces, then combines partial answers. For a sum, each worker sums a portion and a final step adds those partial sums. This works because addition can be grouped without changing the result, subject to numeric precision and overflow rules.

partial_sums = parallel_map(sum, chunks)
total = sum(partial_sums)

The pattern is not automatically efficient: creating many tiny chunks increases scheduling overhead, while a few huge chunks can leave workers idle. Choose chunk sizes that balance overhead and load, and account for any operation that cannot safely be combined in arbitrary order.

Dependencies and dividing work

Before parallelizing an algorithm, identify which steps depend on earlier results. If each item can be processed independently, the work may be parallelizable. If every step needs the previous step's result, there may be limited parallelism unless the problem can be reformulated.

A dependency graph represents tasks as nodes and prerequisites as directed edges. Tasks with no unmet dependencies can run concurrently. The longest dependency chain is the critical path and places a lower bound on completion time, even if unlimited processors are available.

Worked example: sum a large list

To sum a list, divide it into chunks. Each worker calculates a local sum; a final reduction adds the local sums. Work is divided, but the final combine and scheduling have overhead. For a short list, a single loop is usually faster and simpler.

If the list changes while workers are reading it, the result may be inconsistent or unsafe. The input should remain stable during the computation or use a well-defined synchronization or snapshot strategy. Dividing the list also needs to account for uneven sizes and errors in individual tasks.

Load balancing

Workers finish at different times when task sizes vary. Static assignment gives each worker a fixed portion; dynamic scheduling assigns new work as workers become free. Dynamic scheduling can balance irregular tasks but adds coordination overhead and may harm locality if data moves between workers.

Shared state and synchronization

Parallel tasks can communicate through shared memory or messages. Shared memory is convenient but creates risks when multiple tasks read and write the same values. A race condition occurs when the result depends on the timing or interleaving of operations.

For example, two workers incrementing one shared counter may both read the same old value and overwrite each other's updates. A lock can protect the increment, but making every operation use one lock can serialize the work and remove most speedup.

• Mutex: grants exclusive access to a protected region.
• Atomic operation: performs a small update as one indivisible operation.
• Barrier: makes participants wait until a phase is complete.
• Message passing: exchanges data without directly sharing mutable state.

Deadlocks can occur when tasks wait on locks in conflicting orders. Data races can occur when shared data is accessed without the synchronization required by the language or runtime. Prefer clear ownership and immutable inputs where possible, and use concurrency tools supported by the language.

Synchronization must also establish when writes become visible to other tasks. A correct-looking lock-free algorithm can still be wrong if it assumes memory visibility the platform does not guarantee. Use documented primitives rather than relying on timing or testing on one machine.

Speedup and Amdahl's law

Speedup compares the time for a task on one processor with its time on multiple processors. If a fraction P of work can run in parallel and the rest 1 - P is serial, idealized speedup on N processors is bounded by Amdahl's law:

speedup(N) = 1 / ((1 - P) + P / N)

If 80% of a program is parallelizable, even infinitely many processors give a maximum speedup of 5 under this simplified model. The serial portion remains a bottleneck. Real systems also have task creation, synchronization, memory, and communication overhead, so actual speedup is lower.

Strong scaling asks how a fixed problem speeds up with more processors. Weak scaling asks whether the system handles proportionally larger work as processors are added. These answer different questions; a program can scale well under one measure and poorly under the other.

Parallel efficiency is speedup divided by processor count. Low efficiency can indicate a serial bottleneck, imbalanced work, communication overhead, or contention. Measure the complete application rather than a small isolated loop if users care about end-to-end time.

Memory, locality, and communication

Processors are fast, but moving data can be expensive. Cache locality improves when a worker reuses nearby data. Assigning adjacent chunks to the same worker can reduce cache misses, while frequent migration or scattered memory access can undermine parallel computation.

False sharing can occur when different workers update separate variables that happen to occupy the same cache line. The variables are logically independent, but cache coherence causes unnecessary communication and slows the program.

On clusters, network communication is usually much slower than local memory access. A distributed algorithm should minimize messages, batch data where sensible, and balance local computation with communication. Sending every intermediate result to a central coordinator can become a bottleneck.

Memory bandwidth is also limited. Adding processors does not help if all of them compete to read from memory faster than the system can supply data. Algorithms that perform useful work per byte moved can scale better than those that repeatedly stream large arrays.

GPUs and specialized parallelism

A GPU is designed to perform many similar operations in parallel. This makes GPUs effective for graphics, scientific computing, machine learning, and other data-parallel workloads. A workload with irregular branching or frequent CPU-GPU transfers may not benefit.

GPU programming commonly launches groups of many lightweight threads over data. Threads in a group may execute most efficiently when they follow similar paths and access memory in coordinated patterns. Divergent branches and scattered memory access can reduce throughput.

Moving data between host memory and device memory has a cost. Batch operations and reuse data on the GPU when possible. For small inputs, the transfer and launch overhead can exceed the computation saved. Benchmark with realistic data and include setup costs.

Correctness and measurement

Parallel bugs can be intermittent because they depend on timing. Run tests repeatedly, vary worker counts, and test small inputs that expose edge cases such as empty chunks, one item, and uneven divisions. Compare results with a simple trusted sequential implementation.

Benchmark only after checking correctness. Warm-up, compiler optimization, background work, cache state, and timer resolution can distort results. Use repeated measurements, report the environment, and compare the full workload rather than selecting the best single run.

Tools such as thread sanitizers, profilers, and tracing can help identify races, contention, and idle workers. A clean tool run is evidence, not proof: tools cover particular behaviors and may not reproduce every production timing scenario.

A compact glossary

Concurrency

Overlapping progress of multiple tasks.

Parallelism

Simultaneous execution of multiple computations.

Race condition

Behavior that depends on the timing or order of concurrent operations.

Critical path

The longest chain of dependent tasks that constrains completion time.

Speedup

Sequential execution time divided by parallel execution time.

False sharing

Unnecessary cache-coherence traffic from independent data on the same cache line.

References and further reading

1. Peter Pacheco. An Introduction to Parallel Programming. Morgan Kaufmann, 2011. Publisher information.
2. Lawrence Snyder. Introduction to the Programming of Parallel Computers. Author resources.
3. OpenMP Architecture Review Board. OpenMP API Specification. Specifications.
4. NVIDIA. CUDA C++ Programming Guide. Documentation.

Try it yourself

1. Divide an image-processing task among workers and identify which data each worker needs.
2. Use Amdahl's law to estimate the maximum speedup if 90% of a task is parallelizable.
3. Explain how two threads can lose an increment to a shared counter.
4. Why might a GPU be slower than a CPU for a tiny input?
5. Describe one benchmark condition that could make parallel code appear faster than it really is.

Remember: parallelism helps only when work can be divided efficiently and coordination costs do not outweigh the gain.