Parallel, Multicore and Heterogeneous Systems

Introduction

The performance of a computer system is no longer improved primarily by increasing the clock frequency of one processor core. Physical limits such as power consumption, heat dissipation, signal delay, and transistor leakage have encouraged designers to place multiple processing elements in one system. Modern computers therefore combine multicore CPUs, simultaneous multithreading, shared-memory subsystems, graphics processing units (GPUs), and application-specific accelerators.

Parallel architecture allows several operations to be performed at the same time. However, simply adding processors does not guarantee proportional performance improvement. Programs contain sequential sections, communication overhead, synchronization delays, memory bottlenecks, and workload imbalance. Effective system design requires understanding both the hardware and the structure of the workload.

This chapter examines the principles of multicore and heterogeneous systems, including shared memory, cache coherence, GPUs, accelerators, scalability, performance laws, and architecture selection.

Learning Objectives

After studying this chapter, you should be able to:

1. Explain multicore processors and simultaneous multithreading.
2. Distinguish instruction-level, thread-level, and data-level parallelism.
3. Describe shared-memory organization and cache-coherence protocols.
4. Explain the operation and suitable applications of GPUs and accelerators.
5. Estimate parallel speedup, efficiency, and scalability limits.
6. Select an appropriate architecture for a compute-intensive application.
7. Identify practical, economic, security, and energy-related trade-offs in parallel systems.

1. Forms of Parallelism

Parallelism is the use of multiple computational activities during the execution of a program. It occurs at several levels.

1.1 Instruction-level parallelism

Instruction-level parallelism (ILP) allows a processor to execute or begin several independent instructions during overlapping clock cycles. Pipelining, superscalar issue, out-of-order execution, branch prediction, and speculative execution exploit ILP. ILP is largely managed by hardware and is usually transparent to the programmer.

ILP is limited when instructions depend on one another. For example, an instruction that uses the result of a previous instruction cannot be completed before that result is available. Branches and memory delays also restrict useful overlap.

1.2 Data-level parallelism

Data-level parallelism (DLP) applies one operation to many data items. SIMD (single instruction, multiple data) extensions execute the same instruction on a vector of values. Vector units are effective for image processing, numerical arrays, signal processing, and machine-learning kernels.

1.3 Thread-level parallelism

Thread-level parallelism (TLP) executes independent instruction streams, called threads, concurrently. Threads may run on different cores or share a core through simultaneous multithreading (SMT). TLP is useful when a problem can be divided into tasks that perform relatively independent work.

1.4 Task and pipeline parallelism

In task parallelism, different workers perform different functions. In a web server, one thread may accept connections while others process requests. In pipeline parallelism, stages operate concurrently on different items. A video-processing pipeline might decode one frame, filter another, and encode a third at the same time.

Parallelism must be distinguished from concurrency. Concurrency means that multiple activities make progress during the same period; parallelism means that activities actually execute simultaneously on separate hardware resources.

2. Multicore Processor Organization

A multicore processor contains two or more processing cores in one package or system-on-chip. Each core normally contains an arithmetic and logic unit, registers, control logic, and one or more private caches. Cores may share higher-level caches, memory controllers, interconnects, and main memory.

A typical organization includes:

• private level-one instruction and data caches;
• private or shared level-two caches;
• a shared last-level cache;
• an interconnection network or bus;
• memory controllers;
• input/output and accelerator interfaces.

The exact organization varies. A mobile system-on-chip may combine high-performance CPU cores, energy-efficient CPU cores, a GPU, a neural-processing unit, media engines, and memory controllers on one silicon device.

2.1 Symmetric and asymmetric multicore systems

In a symmetric multiprocessor, cores have broadly similar capabilities and the operating system can schedule a thread on any core. This simplifies programming and scheduling.

An asymmetric or heterogeneous multicore system contains cores with different performance and power characteristics. A common design combines high-performance cores with smaller efficiency cores. The operating system or runtime system attempts to place urgent, computation-intensive work on fast cores and background work on efficient cores.

This arrangement improves energy efficiency but creates scheduling complexity. Moving a thread between core types can affect cache locality, execution time, thermal behavior, and responsiveness.

2.2 Simultaneous multithreading

Simultaneous multithreading allows one physical core to maintain the architectural state of multiple hardware threads. Instructions from different threads may be issued in the same cycle when execution resources are available.

SMT improves utilization when one thread is stalled by a cache miss, branch delay, or dependency. It does not create another complete physical core. Threads still compete for execution units, cache capacity, translation buffers, memory bandwidth, and power.

Consequently, SMT performance depends on workload combination. Two compute-heavy threads may interfere with each other, whereas a compute-heavy thread paired with a memory-stalled thread may use the core more effectively. Security concerns also arise because threads sharing microarchitectural resources may infer information through timing or resource contention. Systems handling sensitive workloads may disable SMT or apply strict scheduling and isolation policies.

3. Shared-Memory Systems

In a shared-memory system, multiple processors can access a common address space. A thread can read or write memory using ordinary load and store instructions, although synchronization mechanisms are required when data are shared.

3.1 UMA and NUMA

Uniform memory access (UMA) provides approximately equal access time from every processor to every memory location. Small symmetric multiprocessors often approximate UMA.

Non-uniform memory access (NUMA) divides memory among nodes. A processor accesses its local memory faster than memory attached to another node. NUMA can scale better than a single shared-memory bus, but software and operating-system policies must preserve locality.

A NUMA-aware application attempts to place data near the threads that use it. Poor placement can cause remote-memory traffic, increased latency, and saturation of interconnect links.

3.2 Synchronization

When several threads access shared data, synchronization is necessary whenever at least one access modifies the data and the accesses can overlap. Common mechanisms include mutexes, semaphores, barriers, read-write locks, atomic instructions, and lock-free algorithms.

A critical section is a region that must be executed by only one thread at a time. Excessive locking reduces parallelism. Incorrect synchronization can produce a race condition, deadlock, livelock, or inconsistent view of memory.

A barrier requires participating threads to reach a point before any of them proceeds. Barriers are useful in iterative numerical algorithms but may be expensive when threads arrive at different times.

3.3 Memory consistency

Cache coherence answers whether different caches eventually agree about the value of a memory location. Memory consistency specifies the order in which memory operations become visible to processors. These are related but distinct concepts.

A program may be cache coherent yet still require memory-ordering operations to ensure that one thread observes another thread's writes in the intended order. High-level language memory models and atomic operations provide programmer-visible rules for this behavior.

4. Cache Coherence

Each core may hold a private copy of a cache line. If one core modifies its copy while another retains an old copy, the system must prevent the second core from using stale data. Cache-coherence protocols coordinate these copies.

4.1 Write-invalidate and write-update

In a write-invalidate protocol, a processor that writes a cache line invalidates other cached copies. Other processors must obtain the new line before reading it. This reduces repeated broadcasts when a processor performs several writes.

In a write-update protocol, a write sends the new value to other caches. This may be useful when many processors read the updated value, but it can generate substantial communication traffic.

Most general-purpose multicore systems use variants of write-invalidate protocols.

4.2 MESI states

The MESI protocol assigns each cache line one of four states:

For example, if a line is Shared in two caches and one core writes to it, the protocol invalidates the other copy and changes the writer's state to Modified. A later read by the other core causes a coherence transaction and may force the modified data to be supplied.

Coherence traffic is especially costly when multiple cores repeatedly update different variables located on the same cache line. This is called false sharing. The variables are logically independent, but the cache system treats the entire line as one unit. Padding, alignment, and data restructuring can reduce false sharing.

4.3 Coherence scalability

A snooping protocol allows caches to monitor a shared bus, but a bus becomes a bottleneck as the number of cores increases. Directory-based protocols record which caches hold each line and send messages only to relevant participants. Directories require storage and management overhead but are more scalable in large systems.

5. Parallel Performance and Scalability

The performance of a parallel application should be evaluated using more than raw execution time. Important measures include speedup, efficiency, throughput, latency, scalability, energy consumption, and cost.

If T₁ is the execution time on one processing element and T_p is the execution time on p processing elements, speedup is:

Efficiency is speedup per processing element:

Here, p is a positive integer and the times must use the same unit. Ideal speedup is S(p) = p, giving efficiency of 1, but communication, synchronization, serial work, and imbalance normally make efficiency less than 1.

5.1 Amdahl's law

Amdahl's law estimates the maximum speedup when a fixed fraction of a program is serial. If s is the serial fraction and the remaining fraction is perfectly parallelizable, then:

The assumptions are that the serial fraction cannot be parallelized, the parallel fraction divides evenly, and overhead is ignored. As p approaches infinity, the limiting speedup is:

For example, if 10% of execution is serial, the theoretical limit is 10×, regardless of how many processors are added. With 8 processors:

S(8) = 1/(0.10 + 0.90/8) = 1/0.2125 ≈ 4.71

The corresponding efficiency is approximately 4.71/8 ≈ 0.589, or 58.9%.

5.2 Gustafson's law

Amdahl's law holds the problem size constant. In practice, users may solve larger problems when more processors are available. Gustafson's law models scaled speedup. If s is the measured serial fraction of a parallel execution on p processors, scaled speedup is:

This assumes the parallel workload grows while the serial component remains relatively fixed. The two laws answer different questions: Amdahl's law concerns a fixed-size problem, while Gustafson's law concerns a scaled workload.

5.3 Other scalability limits

Parallel performance is limited by:

• insufficient independent work;
• load imbalance;
• synchronization and locking;
• communication latency and bandwidth;
• cache misses and memory bandwidth;
• thread creation and scheduling overhead;
• contention for shared resources;
• thermal and power limits;
• algorithmic dependencies.

A useful practical rule is to optimize the algorithm and data movement before merely increasing the thread count.

6. GPUs and Data-Parallel Processors

A GPU is designed to execute a large number of similar operations on many data elements. Unlike a conventional CPU, which emphasizes low latency and flexible control flow, a GPU emphasizes high throughput.

GPU programming commonly follows a kernel model. The host CPU launches a kernel, and many lightweight GPU threads execute instances of that kernel. Threads are grouped into blocks or workgroups, and blocks are scheduled on multiprocessors. Threads in a group can often cooperate through fast local or shared memory and synchronization barriers.

GPU execution is most effective when:

• many independent data elements undergo similar operations;
• control flow is regular;
• memory accesses are coalesced or otherwise efficient;
• enough work exists to occupy the device;
• data-transfer costs are small compared with computation.

Examples include matrix operations, image filtering, physical simulation, cryptographic workloads, and neural-network inference.

GPU performance can decline because of branch divergence, irregular memory access, insufficient occupancy, limited device memory, or repeated transfers between CPU and GPU memory. A GPU is not automatically faster than a CPU; the workload must match its execution model.

7. Accelerators and Heterogeneous Computing

An accelerator is a specialized processing element designed to perform a class of operations more efficiently than a general-purpose CPU. Examples include GPUs, digital signal processors, video codecs, field-programmable gate arrays (FPGAs), tensor-processing units, cryptographic engines, and network accelerators.

A heterogeneous system combines different processor types. The CPU commonly performs operating-system functions, control-intensive work, and orchestration. An accelerator performs selected kernels with high arithmetic intensity or regular parallel structure.

7.1 Selection criteria

Architecture selection should consider:

FPGAs can provide highly customized pipelines and low latency but usually require more hardware-design expertise. GPUs offer excellent throughput for regular data-parallel work. CPUs are preferable for irregular control flow, small workloads, operating-system services, and applications whose data transfer would dominate execution.

7.2 Compute intensity and the roofline perspective

Performance is often bounded either by computation or by memory movement. Arithmetic intensity is the number of arithmetic operations performed per byte transferred from a relevant memory level:

where I is arithmetic intensity in operations per byte, F is the number of arithmetic operations, and B is the number of bytes transferred. The units are operations/byte.

A simplified performance bound is:

where P is achievable performance, P_peak is peak computational throughput, and BW is sustainable memory bandwidth in bytes per second. The product I × BW has units of operations per second. This model assumes that computation and data transfer are the dominant constraints and ignores many overheads such as latency, synchronization, and instruction inefficiency.

An application with low arithmetic intensity is memory-bound; increasing arithmetic units may provide little benefit. An application with high arithmetic intensity may be compute-bound and can benefit from a faster accelerator.

8. Programming and System Software Considerations

Parallel hardware requires software support. Operating systems schedule threads, manage processor affinity, handle interrupts, allocate memory, and expose synchronization primitives. Compilers may automatically vectorize loops, reorder independent operations, and generate multithreaded code, although programmer annotations or libraries are often needed.

Common programming approaches include:

• shared-memory threads using APIs such as POSIX threads or OpenMP;
• message passing for distributed-memory systems;
• GPU kernel frameworks;
• vectorized numerical libraries;
• task-based runtimes that schedule dependencies dynamically.

A robust parallel program should identify independent work, minimize shared mutable state, use appropriate synchronization, preserve locality, and measure actual performance. Profilers should distinguish CPU time, waiting time, cache misses, branch behavior, memory bandwidth, GPU occupancy, and data-transfer overhead.

Correctness must be established before optimization. A program that runs quickly but produces nondeterministic results is not successful. Testing should include repeated executions, stress conditions, race detection, boundary cases, and numerical-error analysis where floating-point operations are reordered.

9. Applied Case: Choosing an Architecture for Image Analysis

Background

Consider an illustrative image-analysis service that applies a convolution filter and classification model to thousands of independent images. Each image can be processed independently, but the pixels within each image also provide substantial data-level parallelism.

Problem

The initial CPU implementation processes images correctly but cannot meet the required throughput. Engineers must decide whether to add CPU cores, use SIMD instructions, deploy a GPU, or adopt a specialized inference accelerator.

Analysis

The filtering and matrix operations have high regularity and substantial arithmetic intensity. They can be divided across images, rows, channels, and matrix tiles. The classification model also uses operations for which optimized GPU and accelerator libraries are available.

However, images arrive in small batches. If each batch is copied separately to a discrete GPU, transfer latency may offset computational gains. A system with integrated graphics or a local accelerator may therefore be preferable. If latency for one image is more important than aggregate throughput, a CPU with vector instructions may be competitive.

Approach

The team measures:

1. CPU execution time and vectorization efficiency;
2. memory bandwidth and cache behavior;
3. transfer time between host and accelerator;
4. GPU kernel occupancy and branch divergence;
5. throughput, tail latency, power, and cost.

They then redesign the pipeline to batch requests, reuse allocated buffers, keep intermediate data on the accelerator, and overlap data transfer with computation. CPU threads handle input, scheduling, and post-processing, while the accelerator performs filtering and inference.

Outcome

For large batches, the GPU provides much higher throughput. For single-image requests, the optimized CPU path provides lower latency. The final system uses a hybrid policy: small urgent requests use CPU SIMD execution, while queued batches use the accelerator.

Learning points

The best architecture depends on workload size, regularity, data movement, latency requirements, software support, and energy limits. Benchmarking the complete pipeline is more reliable than comparing the peak specifications of processors.

10. Challenges, Governance, and Contemporary Developments

Parallel systems introduce technical and organizational risks. Nondeterministic execution can make bugs difficult to reproduce. Shared caches and speculative execution may create side-channel vulnerabilities. Resource oversubscription can reduce performance in virtualized or cloud environments. Accelerator dependence may create portability and supplier risks.

Security controls include process isolation, careful scheduling, cache-partitioning techniques, constant-time implementations for sensitive algorithms, firmware updates, and access control for accelerator devices. In safety-critical systems, deterministic timing, fault containment, verification, and traceability may be more important than maximum throughput.

Energy efficiency is increasingly central. A system should be evaluated using performance per watt and, where appropriate, energy per completed task. Dynamic voltage and frequency scaling, power-aware scheduling, efficient data movement, and workload consolidation can reduce energy use.

Contemporary systems increasingly combine CPUs, GPUs, AI accelerators, high-bandwidth memory, chiplet-based designs, and advanced interconnects. The trend is toward specialization, but general-purpose programmability remains essential. Portable programming models and standardized intermediate representations are therefore important for avoiding dependence on one processor vendor.

Best Practices for Parallel System Design

1. Begin with workload characterization rather than hardware preference.
2. Expose genuine parallelism in the algorithm.
3. Minimize communication, synchronization, and data copying.
4. Keep related data close to the threads that use it.
5. Avoid false sharing and excessive lock contention.
6. Use batching when it improves accelerator utilization.
7. Measure complete application performance, not peak device throughput alone.
8. Test correctness under different thread counts and schedules.
9. Include power, cost, maintainability, and portability in architecture decisions.
10. Apply security isolation when threads or tenants may share hardware resources.

Chapter Summary

Multicore and heterogeneous systems improve performance by exploiting instruction-, data-, thread-, and task-level parallelism. Multicore processors provide multiple physical execution contexts, while SMT allows several hardware threads to share one core. Shared-memory systems simplify communication but require synchronization, coherent caches, and appropriate memory-ordering rules.

Cache-coherence protocols such as MESI maintain consistent cache-line states. False sharing and coherence traffic can limit scalability. Amdahl's law demonstrates the effect of serial work on fixed-size problems, while Gustafson's law models scaled workloads. Speedup and efficiency are useful but must be interpreted alongside memory bandwidth, communication, imbalance, power, and latency.

GPUs and other accelerators are effective for regular, high-throughput workloads. CPUs remain valuable for irregular control flow, low-latency tasks, and system coordination. The roofline perspective emphasizes that performance may be limited by computation or data movement. Successful architecture selection therefore matches hardware to workload structure, software capabilities, service requirements, security constraints, and energy objectives.

Key Terms

Multicore processor: A processor containing multiple independent processing cores.

Simultaneous multithreading: A technique that allows multiple hardware threads to issue instructions through one physical core.

Instruction-level parallelism: Overlap among independent instructions within a thread.

Data-level parallelism: Applying the same operation to multiple data elements.

Thread-level parallelism: Concurrent execution of multiple instruction streams.

Shared memory: A memory address space accessible by multiple processors or threads.

UMA: Uniform memory access, in which memory access time is approximately equal for processors.

NUMA: Non-uniform memory access, in which local memory is faster than remote memory.

Cache coherence: Coordination that ensures cached copies of a memory location do not produce incorrect stale results.

MESI: A cache-coherence protocol with Modified, Exclusive, Shared, and Invalid states.

False sharing: Performance loss caused when independent variables occupy the same cache line.

Synchronization: Coordination that controls the ordering or mutual exclusion of concurrent activities.

Speedup: The ratio of serial or baseline execution time to parallel execution time.

Efficiency: Speedup divided by the number of processing elements.

Amdahl's law: A model of fixed-workload speedup limited by serial execution.

GPU: A throughput-oriented processor designed for highly parallel operations.

Accelerator: Specialized hardware designed to execute particular workloads efficiently.

Arithmetic intensity: Arithmetic operations performed per byte of data transferred.

Heterogeneous system: A system combining different processor or accelerator types.

Load imbalance: Unequal distribution of work that leaves some processing elements idle.

Review Questions

Short Answer Questions

1. What is the difference between concurrency and parallelism?
2. Why can SMT improve utilization without providing the performance of a complete additional core?
3. What problem does cache coherence solve?
4. Define false sharing and state one method of reducing it.
5. What is arithmetic intensity?

Long Answer Questions

1. Explain the organization of a multicore processor, including private caches, shared caches, memory controllers, and interconnects.
2. Describe the MESI protocol and explain how a write to a Shared cache line affects other caches.
3. Compare UMA and NUMA systems, including their performance and programming implications.
4. Explain why GPUs are effective for regular data-parallel workloads but less effective for irregular control flow.
5. Discuss the technical and non-technical criteria that should guide the selection of a CPU, GPU, FPGA, or other accelerator.

Analytical / Application Questions

1. A program has a serial fraction of 0.20. Using Amdahl's law, calculate its theoretical speedup on 4 processors and its limiting speedup as the processor count approaches infinity. Interpret the results.
2. An image-processing kernel performs 600 million arithmetic operations and transfers 200 million bytes from the relevant memory level. Calculate its arithmetic intensity and explain whether increasing memory bandwidth could improve performance.
3. A service receives both individual low-latency requests and large batches of independent numerical jobs. Design a scheduling policy using CPUs and an accelerator, and justify it using workload structure, data-transfer overhead, latency, throughput, and energy considerations.

Multiple Choice Questions with Answers

Question 1

Which form of parallelism applies one instruction to multiple data elements?

A. Instruction-level parallelism

B. Data-level parallelism

C. Task serialization

D. Memory virtualization

Correct Answer: B. Data-level parallelism

Question 2

What is the principal purpose of a cache-coherence protocol?

A. To increase disk capacity

B. To schedule operating-system processes

C. To coordinate cached copies of shared data

D. To convert scalar instructions into branch instructions

Correct Answer: C. To coordinate cached copies of shared data

Question 3

A program has a serial fraction of 0.10. What is its theoretical limiting speedup as the number of processors becomes very large?

A. 2×

B. 5×

C. 10×

D. 100×

Correct Answer: C. 10×

Question 4

Which MESI state indicates that a cache has the only copy of a line and that the line differs from main memory?

A. Modified

B. Exclusive

C. Shared

D. Invalid

Correct Answer: A. Modified

Question 5

Which workload is generally most suitable for a GPU?

A. A small program dominated by unpredictable branches

B. A highly regular operation applied independently to millions of data elements

C. An operating-system interrupt handler requiring minimum scheduling overhead

D. A sequential algorithm with strong loop-carried dependencies

Correct Answer: B. A highly regular operation applied independently to millions of data elements

Question 6

What is a common effect of false sharing?

A. Reduced coherence traffic

B. Improved cache capacity

C. Unnecessary invalidation and coherence traffic

D. Automatic elimination of synchronization

Correct Answer: C. Unnecessary invalidation and coherence traffic

Question 7

A kernel performs 900 operations and transfers 300 bytes. What is its arithmetic intensity?

A. 0.33 operations/byte

B. 3 operations/byte

C. 270 operations/byte

D. 1,200 operations/byte

Correct Answer: B. 3 operations/byte

Question 8

Which statement best describes NUMA memory?

A. Every processor accesses every memory location with exactly equal latency

B. Only one processor can access memory

C. Local memory is generally faster to access than remote memory

D. Caches are not used

Correct Answer: C. Local memory is generally faster to access than remote memory

Question 9

Why might adding more cores fail to produce proportional speedup?

A. All programs automatically become serial

B. Serial work, synchronization, communication, and memory bottlenecks remain

C. More cores always reduce clock frequency to zero

D. Cache coherence eliminates all parallel execution

Correct Answer: B. Serial work, synchronization, communication, and memory bottlenecks remain

Question 10

Which architecture is often appropriate for a workload requiring a customized low-latency pipeline and frequent hardware-level specialization?

A. FPGA

B. Magnetic disk

C. Single-port printer controller

D. Basic text terminal

Correct Answer: A. FPGA