Parallel Computing: Doing Multiple Things at Once

Parallel computing is the use of multiple processing elements simultaneously to solve a computational problem. Instead of executing instructions one at a time (sequential computing), parallel computing breaks a problem into parts that can be solved concurrently. This approach has become increasingly important as processor speeds have hit physical limits and performance gains now come from adding more cores rather than making individual cores faster. Understanding parallel computing is essential for the AP CSP exam and for modern programming.

Why Parallel Computing?

For decades, computer processors became faster through a phenomenon described by Moore's Law: the number of transistors on a chip doubles approximately every two years. This allowed programmers to write sequential programs and rely on hardware improvements for performance gains. However, physical limits (like heat dissipation and power consumption) have made it increasingly difficult to continue increasing clock speeds.

The solution was to add multiple processor cores to a single chip. A multi-core processor can execute multiple instructions simultaneously, one per core. This shift from faster single cores to more cores has fundamentally changed how software is designed. Programs that take advantage of multiple cores can run significantly faster than sequential programs on the same hardware.

Types of Parallelism

Bit-level parallelism increases the number of bits the processor can handle in a single operation. Moving from 8-bit to 16-bit to 32-bit to 64-bit processors allowed larger data types and larger address spaces. Instruction-level parallelism allows a processor to execute multiple instructions from the same program simultaneously through techniques like pipelining and superscalar execution.

Task-level parallelism (or thread-level parallelism) allows different tasks or threads to execute simultaneously on different cores. This is the most common form of parallelism in modern programming. Data parallelism splits a large dataset across multiple processors, each of which processes its portion simultaneously. This is the basis of map-reduce frameworks and GPU computing.

Concurrency vs. Parallelism

Concurrency and parallelism are related but distinct concepts. Concurrency is the ability to handle multiple tasks by interleaving their execution (switching between them rapidly). Parallelism is the ability to execute multiple tasks simultaneously (at the same instant). A single-core processor can achieve concurrency through time-slicing but cannot achieve true parallelism. A multi-core processor can achieve both.

Concurrent programming involves writing programs that can make progress on multiple tasks during overlapping time periods. This is essential for responsive user interfaces, efficient I/O handling, and server applications that serve multiple clients. Parallel programming involves splitting a computation across multiple cores to speed it up. This is essential for scientific computing, data processing, and graphics rendering.

Challenges of Parallel Computing

Race conditions occur when multiple threads access shared data simultaneously, and the result depends on the order of access. For example, two threads incrementing the same counter might both read the value 5, both increment it to 6, and both write 6, when the correct result should be 7. Race conditions are among the most difficult bugs to find and fix because they may only occur under specific timing conditions.

Deadlock occurs when two or more threads are waiting for each other to release resources, and none can proceed. Thread A holds resource 1 and waits for resource 2, while thread B holds resource 2 and waits for resource 1. Neither can proceed, and the program is stuck. Deadlock is difficult to detect because it depends on the timing of thread execution.

Amdahl's Law describes the theoretical speedup of a parallel program. It states that the maximum speedup is limited by the sequential portion of the program. If 90% of a program can be parallelized, the maximum speedup with infinite processors is 10x, because the remaining 10% must execute sequentially. This law highlights the importance of minimizing sequential bottlenecks in parallel programs.

Parallel Computing in Practice

Modern computers are inherently parallel. Your computer has a multi-core CPU, a GPU with thousands of cores, and multiple devices (network card, disk controller, graphics card) that operate independently. Operating systems use parallelism to run multiple programs simultaneously, manage I/O devices, and handle user interactions while performing background tasks.

Web servers use parallelism to serve thousands of clients simultaneously. Each client request is handled by a separate thread, allowing the server to process multiple requests at the same time. Database systems use parallelism to execute multiple queries simultaneously and to speed up large data processing operations.

Parallel Computing on the AP CSP Exam

The AP CSP curriculum covers parallel and distributed computing as part of the Big Idea on the Internet. You should understand the difference between sequential and parallel processing, the benefits and challenges of parallelism, and how parallel computing is used in real-world applications. You should be able to identify situations where parallel computing is beneficial and explain why parallel algorithms can be faster than sequential ones.