Modern computer systems often improve performance by doing more than one piece of work at the same time. Instead of depending entirely on a single processing unit to execute every operation sequentially, a computer can divide a workload among multiple processing units. This approach is known as parallel processing.
Parallel processing is an important concept in Computer Organization and Architecture because it explains how computers can execute multiple operations simultaneously. It is used in multicore processors, multiprocessor systems, graphics processors, scientific computing, servers, artificial intelligence, image processing, and many other applications.
The basic idea is simple: if a problem can be divided into independent parts, different processing units can work on those parts at the same time. However, parallel processing is not simply a matter of adding more processors. Communication between processors, synchronization, memory access, workload distribution, and dependencies between operations can all affect the actual performance improvement.
In this chapter, we will study the basic concept of parallel processing, multiprocessing, multicore processors, Flynn's classification, SIMD and MIMD architectures, parallel speedup, and the major challenges involved in designing parallel systems.
Parallel processing is a method of computation in which multiple processing units perform multiple parts of a workload at the same time. A large problem is divided into smaller tasks, and those tasks are assigned to different processing units whenever they can be executed independently.
The processing units may be separate processors, multiple cores within one processor, or specialized computing units such as those found in GPUs. The exact architecture depends on the type of parallelism being used.
Suppose a program has to process four independent image files. Sequential approach: Processor | +-- Image 1 +-- Image 2 +-- Image 3 +-- Image 4 Each image is processed one after another. Parallel approach: Processor 1 ---> Image 1 Processor 2 ---> Image 2 Processor 3 ---> Image 3 Processor 4 ---> Image 4 The four processing tasks can execute simultaneously.
If the four tasks require approximately the same amount of computation and have little interaction with one another, parallel execution can significantly reduce the total completion time.
The difference between sequential and parallel processing becomes clearer when the same workload is divided into independent tasks.
| Feature | Sequential Processing | Parallel Processing |
|---|---|---|
| Execution | Tasks are primarily executed one after another. | Multiple tasks may execute simultaneously. |
| Processing Units | Can operate with a single processing unit. | Uses multiple processing units or parallel execution resources. |
| Work Distribution | Limited distribution of work. | Work can be divided among processing units. |
| Best suited for | Tasks with strong sequential dependencies. | Independent or partially independent workloads. |
| Potential Performance | Limited by the speed of sequential execution. | Can provide significant speedup when sufficient parallelism exists. |
Increasing the clock frequency of a processor was historically an important way to improve performance. However, increasing frequency also increases power consumption and heat generation. Processor design therefore increasingly relies on techniques such as multiple cores and specialized parallel execution units.
Parallel processing provides another way to increase computational throughput: instead of requiring one processing unit to perform every operation faster, several processing units can perform different operations at the same time.
For example, a modern computer may simultaneously perform video decoding, web browsing, background file operations, and application calculations using different execution resources.
Parallel processing is particularly useful when a problem contains many independent operations. Examples include processing large datasets, rendering graphics, performing scientific calculations, and serving multiple independent requests on a server.
Multiprocessing refers to a computer system that uses two or more processors to execute computational work. The processors cooperate within the same computer system and may share memory and other system resources.
Each processor can execute instructions independently. The operating system can distribute processes or threads among the available processors according to workload and scheduling requirements.
A server receives several independent requests: Request A ---> Processor 1 Request B ---> Processor 2 Request C ---> Processor 3 Request D ---> Processor 4 Different processors can work on different requests at the same time.
Multiprocessing is especially useful in servers and high-performance systems where many computational tasks need to be handled concurrently.
In Symmetric Multiprocessing (SMP), processors generally have equal status and can execute operating-system and application tasks. They typically share access to the main memory and other system resources.
In Asymmetric Multiprocessing (AMP), processors may have different responsibilities. One processor may control certain system operations while other processors perform assigned computational tasks.
A multicore processor contains two or more processing cores on a single processor chip. Each core can execute instructions independently, allowing several instruction streams to progress simultaneously.
For example, a quad-core processor has four processing cores. The operating system can schedule different threads or processes on different cores.
Multicore CPU
+-----------------------+
| |
| Core 1 Core 2 |
| |
| Core 3 Core 4 |
| |
+-----------------------+
Although the cores can execute independently, they may share resources such as cache levels, memory interfaces, and other parts of the processor architecture. Consequently, simply having more cores does not guarantee a proportional increase in application performance.
| Feature | Multiprocessing | Multicore Processing |
|---|---|---|
| Basic Idea | Uses multiple processor units in a computer system. | Uses multiple processing cores within a processor chip. |
| Physical Arrangement | May involve multiple physical CPU packages. | Multiple cores are integrated into one CPU package or chip. |
| Resource Sharing | Processors may share system memory and other resources. | Cores can share caches, memory interfaces, and other chip resources. |
| Common Usage | Servers and high-performance systems. | Desktop computers, laptops, smartphones, and servers. |
Parallel processing can appear at different levels of a computer system. Two important forms are instruction-level parallelism and data-level parallelism.
Instruction-level parallelism allows multiple independent instructions to be processed during overlapping periods of execution. Techniques such as pipelining, superscalar execution, and out-of-order execution can exploit this type of parallelism.
Data-level parallelism occurs when the same operation needs to be performed on many different data elements. A processor can apply one operation to several values simultaneously using vector or SIMD instructions.
Suppose we have: A = [10, 20, 30, 40] and we want to add 5 to every element. Result: [15, 25, 35, 45] Instead of treating every element separately, a SIMD operation can process several elements with the same instruction.
Flynn's classification is a well-known method for categorizing computer architectures according to the number of instruction streams and data streams they handle.
The four categories are SISD, SIMD, MISD, and MIMD.
| Type | Full Form | Basic Idea |
|---|---|---|
| SISD | Single Instruction, Single Data | One instruction stream operates on one data stream. |
| SIMD | Single Instruction, Multiple Data | One instruction is applied to multiple data elements. |
| MISD | Multiple Instruction, Single Data | Multiple instruction streams operate on a single data stream. |
| MIMD | Multiple Instruction, Multiple Data | Multiple instruction streams operate on multiple data streams. |
SISD represents the traditional sequential processing model. A single processing unit executes one instruction stream and works on one data stream at a time.
Instruction Stream
|
v
+---------+
|Processor|
+---------+
|
v
Data Stream
A simple single-core processor executing a conventional sequential program can be considered an example of the SISD model, although modern processors often contain additional mechanisms that make the simple classification less exact.
SIMD allows one instruction to operate on multiple data elements simultaneously. This is particularly effective when the same operation must be repeated across a large collection of values.
One Instruction
|
+-----------+-----------+
| | |
v v v
Data 1 Data 2 Data 3
| | |
+-----------+-----------+
|
Result
For example, an image contains thousands or millions of pixels. If the same mathematical operation needs to be applied to every pixel, SIMD can process multiple pixel values together.
SIMD techniques are also commonly used for vector arithmetic, multimedia processing, scientific calculations, and other workloads containing repetitive operations.
MISD represents a model in which multiple instruction streams operate on the same data stream. This architecture is much less common than SIMD and MIMD in general-purpose computing.
MISD is primarily useful as a theoretical classification and can also be associated with certain specialized or fault-tolerant processing arrangements where multiple computations are performed on the same input.
MIMD allows multiple processing units to execute different instructions on different data sets. Each processing unit can work independently, making MIMD highly flexible.
Processor 1 ---> Instruction A ---> Data A Processor 2 ---> Instruction B ---> Data B Processor 3 ---> Instruction C ---> Data C Processor 4 ---> Instruction D ---> Data D
Most modern multicore general-purpose systems can broadly be associated with the MIMD category because different cores can execute different instruction streams on different data at the same time.
| Feature | SIMD | MIMD |
|---|---|---|
| Instruction Streams | Single | Multiple |
| Data Streams | Multiple | Multiple |
| Operation | Same instruction applied to multiple data items. | Different instruction streams can operate on different data. |
| Best Suited For | Highly repetitive data-oriented calculations. | Independent and varied computational tasks. |
| Example | Applying the same mathematical operation to many pixels. | Different CPU cores running different program threads. |
Parallel processing and pipelining both improve processor performance, but they do so in different ways.
Pipelining divides instruction execution into stages and overlaps those stages for different instructions. At a particular moment, different instructions may occupy different pipeline stages within the processor.
Parallel processing, in contrast, uses multiple processing resources to execute multiple pieces of work simultaneously.
| Feature | Pipelining | Parallel Processing |
|---|---|---|
| Main Idea | Overlap stages of instruction execution. | Execute multiple pieces of work simultaneously. |
| Primary Resource | Pipeline stages within a processor. | Multiple cores, processors, or execution units. |
| Goal | Improve instruction throughput. | Increase computational throughput using parallel resources. |
| Example | Fetch one instruction while another is being decoded. | Two CPU cores execute different threads simultaneously. |
One of the most important questions in parallel processing is how much faster a program becomes when additional processing resources are introduced.
A commonly used measure is speedup.
Speedup = Time required for sequential execution
---------------------------------------
Time required for parallel execution
For example, suppose a task takes 100 seconds using one processing unit and 30 seconds using multiple processing units.
Speedup = 100 / 30
≈ 3.33
Therefore, the parallel implementation provides a speedup of approximately 3.33 times for that particular workload and system configuration.
The speedup is usually less than the number of processing units because some parts of the program may remain sequential and because parallel execution introduces communication and coordination overhead.
A major limitation of parallel processing is that a program may contain a portion that cannot be executed in parallel. Amdahl's Law describes how this sequential portion limits the maximum theoretical speedup obtained from parallel execution.
If a fraction of a program can be parallelized while another fraction must remain sequential, adding more processors eventually produces diminishing returns because the sequential portion still has to be completed by the system.
For example, if 90% of a workload can theoretically be parallelized but 10% must remain sequential, increasing the number of processors cannot make the entire program infinitely fast. The sequential 10% remains a fundamental limit.
This principle is important when evaluating claims about the performance benefits of adding more CPU cores.
Designing an efficient parallel program is more complicated than simply dividing work between processors. Several factors can reduce the expected performance improvement.
One operation may depend on the result of another operation. When this happens, the dependent operation cannot begin until the required result is available.
Task A | v Task B | v Task C
These dependencies restrict the amount of useful parallelism available.
When several processing units access shared data, they may need to coordinate their operations. Synchronization mechanisms prevent conflicting updates and help maintain correct program results.
Parallel tasks may need to exchange information. Transferring data between processing units consumes time and system resources, reducing some of the benefit obtained from parallel execution.
The workload should be distributed reasonably evenly. If one processing unit receives a much larger task than the others, the remaining units may finish early and remain idle while waiting.
Poor Load Distribution: Core 1 ---> Large Task Core 2 ---> Small Task Core 3 ---> Small Task Core 4 ---> Small Task Core 2, 3 and 4 may become idle while Core 1 continues working.
Multiple processing units may compete for access to shared memory. If memory bandwidth cannot supply data quickly enough, additional processors may provide little extra performance.
Parallel processing is useful whenever a workload contains enough independent computation. Common applications include:
| Advantages | Limitations |
|---|---|
| Can reduce execution time for workloads containing independent tasks. | Sequential portions of a program limit maximum speedup. |
| Allows multiple CPU cores or processors to be used efficiently. | Synchronization and communication introduce overhead. |
| Useful for large computational workloads and data-intensive applications. | Uneven workload distribution can leave some processing units idle. |
| Can increase system throughput by processing multiple tasks simultaneously. | Shared memory and bandwidth can become bottlenecks. |
Parallel processing is a computing technique in which multiple processing resources work on different parts of a workload at the same time.
Multiprocessing is the use of multiple processors in a computer system so that computational tasks can be executed using more than one processing unit.
A multicore processor contains multiple independent processing cores within a single processor chip or package.
Flynn's classification categorizes computer architectures according to the number of instruction streams and data streams they process. Its four categories are SISD, SIMD, MISD, and MIMD.
SIMD stands for Single Instruction, Multiple Data. It applies one instruction to multiple data elements, making it useful for repetitive data-processing operations.
MIMD stands for Multiple Instruction, Multiple Data. It allows different processing units to execute different instruction streams on different data.
Some portions of a program may be sequential, and parallel execution introduces overhead from synchronization, communication, memory access, and workload management. These factors limit the actual speedup.
Speedup is the ratio of the execution time of a sequential implementation to the execution time of its parallel implementation.
Amdahl's Law describes the theoretical limit on parallel speedup caused by the portion of a program that cannot be parallelized.
Parallel processing is a fundamental technique for improving computational performance by allowing multiple processing resources to work on different parts of a workload simultaneously. It can be implemented using multiple processors, multicore CPUs, vector or SIMD operations, and other specialized processing architectures.
Flynn's classification provides a useful way to understand processor architectures through four categories: SISD, SIMD, MISD, and MIMD. Among these, SIMD is particularly suitable for applying the same operation to many data elements, while MIMD provides the flexibility required by many modern multicore and multiprocessor systems.
The actual benefit of parallel processing depends on how much of a workload can be executed independently. Data dependencies, synchronization, communication overhead, load imbalance, and memory limitations can reduce performance gains. Amdahl's Law further demonstrates that a sequential portion of a program places a fundamental limit on overall speedup.
Understanding parallel processing provides an important foundation for studying modern multicore processors, GPU computing, high-performance computing, and advanced processor architectures.