A crash course on the fundamentals of
concurrent and parallel execution.
Programmers must design our software to take advantage of parallel execution.
These terms are often confused but have distinct meanings:
Concurrency provides a way to structure a solution that may (but not necessarily) have tasks executed in parallel.
Modern computers achieve parallelism through multiple layers of hardware:
Multiple processing units on a single chip that can execute instructions independently.
Each core has:
Some architectures (like Intel's Hyperthreading) allow a single physical core to appear as multiple logical cores by:
When multiple threads access shared resources, we need to implement protection mechanisms:
A block of code where multiple threads might access shared resources. Synchronization primitives must adhere to:
Tools for implementing mutual exclusion:
Specialized data structures designed to handle concurrent access:
// Example: Thread-safe Counter
class AtomicCounter {
private atomic<int> value = 0;
int increment() {
return ++value; // Atomic operation
}
int get() {
return value; // Atomic read
}
}Reuse a fixed number of threads to execute multiple tasks, avoiding the overhead of thread creation:
// Conceptual thread pool
ThreadPool pool = new ThreadPool(4); // 4 worker threads
pool.submit(task1);
pool.submit(task2);
// Tasks execute concurrently on available threadsRecursively breaks down a problem into sub-problems that are solved in parallel:
Result solve(Problem p) {
if (p is small)
return solveDirectly(p);
else {
split p into subproblems p1, p2
fork task to solve(p1)
fork task to solve(p2)
join results
return combined result
}
}Separates the tasks of producing and consuming data with a shared buffer:
Describes the theoretical speedup in latency of the execution of a task at fixed workload:
Speedup = 1 / ((1 - p) + p/n)
Where:
p = portion of the program that can be parallelized
n = number of processors
1-p = portion that cannot be parallelizedThis formula gives us a ballpark computation of what kind of speedup we can expect. The key insight: if a significant portion of your program cannot be parallelized, adding more processors will have diminishing returns.
Parallel bugs are notoriously difficult to find and fix because they:
Parallel programming presents both challenges and opportunities. The transition from sequential to parallel thinking requires:
As we continue to approach the physical limits of processor speed, the importance of effective parallel programming will only increase. The fundamental challenge remains: how to divide problems into independent tasks that can be executed simultaneously without excessive communication or synchronization overhead.
Adding parallelism to an existing sequential program is often more difficult than designing for parallelism from the beginning.
The less data shared between threads, the fewer synchronization points required and the more scalable your solution will be.
Whenever possible, use well-tested libraries and frameworks that handle the low-level details of parallelism for you:
Parallel bugs may only appear when actually running on multiple cores. Be sure to test on machines with varying numbers of cores.
Always measure the performance of your parallel code. Sometimes, the overhead of parallelism can outweigh the benefits for small workloads.
// Example: Good practice for thread safety
// Immutable objects are inherently thread-safe
class Point {
private final int x;
private final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() { return x; }
public int getY() { return y; }
// Creates a new object rather than modifying
public Point translate(int dx, int dy) {
return new Point(x + dx, y + dy);
}
}