Parallel, Vector and Heterogeneous Architectures

Introduction and Context

Modern applications rarely execute efficiently on a single general-purpose processor. Scientific simulation, artificial intelligence, multimedia processing, search, large-scale analytics, and cloud services expose millions or billions of operations that may be performed concurrently. Advanced computer architecture therefore studies not only how to make one instruction execute faster, but also how to organize many processing elements, data paths, memories, and specialized accelerators so that useful work is performed simultaneously.

Three related architectural ideas are central:

• Parallel architectures execute multiple operations, instructions, threads, or tasks concurrently.
• Vector architectures apply one instruction to a sequence of data elements.
• Heterogeneous architectures combine different processor types, such as CPUs, GPUs, vector engines, and application-specific accelerators.

These approaches are complementary rather than mutually exclusive. A contemporary system may contain multicore CPUs, vector instruction units, GPUs, neural-processing units, high-bandwidth memory, and network interfaces, all cooperating through a software-managed execution model.

Learning Objectives

After completing this chapter, a student should be able to:

1. Explain the principles and classifications of parallel, vector, and heterogeneous architectures.
2. Analyze speedup, efficiency, scalability, and the limits imposed by sequential work.
3. Distinguish task, data, instruction-level, thread-level, and pipeline parallelism.
4. Describe SIMD, vector-register, GPU, multicore, manycore, and accelerator organizations.
5. Select suitable architectures and programming models for representative workloads.
6. Identify bottlenecks involving memory, communication, synchronization, load balance, and programmability.
7. Evaluate a heterogeneous architecture using performance, energy, cost, and portability criteria.

1. Dimensions of Parallelism

Parallelism can be classified according to the granularity and nature of the work.

1.1 Instruction-level parallelism

Instruction-level parallelism (ILP) exists when independent instructions from one thread can overlap. Superscalar issue, out-of-order execution, speculative execution, and pipelining exploit ILP. ILP is relatively fine-grained and is usually discovered by hardware, although compilers also reorder instructions.

ILP is limited by true data dependencies, control dependencies, finite instruction windows, branch uncertainty, and memory latency. Increasing issue width does not guarantee proportional performance because the available independent work may be insufficient.

1.2 Data-level parallelism

Data-level parallelism (DLP) occurs when the same operation is applied independently to many data items. Adding two arrays element by element is a typical example. SIMD and vector processors exploit DLP by representing multiple elements in registers and applying one operation to all lanes.

1.3 Thread-level and task parallelism

Thread-level parallelism (TLP) executes multiple instruction streams concurrently. Task parallelism divides a computation into distinct activities, possibly with different code paths. For example, one task may read data, another may transform it, and a third may compress results.

Task parallelism is often more flexible than SIMD but usually incurs greater scheduling and communication overhead. The best decomposition depends on task size, dependency structure, and hardware resources.

1.4 Pipeline parallelism

A computation can be divided into stages. While one item is processed by stage 2, the next item can be processed by stage 1. After the pipeline is filled, throughput is approximately determined by the slowest stage. Pipeline parallelism is common in processors, multimedia systems, networking, and deep-learning inference.

2. Models for Parallel Performance

2.1 Speedup and efficiency

Let T₁ be the execution time on one reference processor and T_p the execution time using p processing elements. The speedup is

where both times refer to the same workload and system conditions. The parallel efficiency is

Efficiency is dimensionless and lies at or below 1 in an idealized model. In practice, values may be below 1 because of synchronization, communication, imbalance, serial work, and measurement overhead. A speedup greater than p can occasionally appear because the parallel execution uses a larger cache or a different algorithm; this is called superlinear speedup and does not contradict the definition, but it requires careful experimental interpretation.

2.2 Amdahl’s law

Suppose fraction f of a program’s execution time is inherently serial and fraction 1-f can be accelerated by p processors. Under fixed-workload assumptions, the idealized speedup is

Here, 0 ≤ f ≤ 1, p ≥ 1, and the parallel portion is assumed to divide perfectly with no communication or synchronization cost. As p approaches infinity, the maximum speedup approaches 1/f. Thus, a 5% serial fraction limits ideal speedup to 20, regardless of the number of processors.

A more realistic model includes overhead o(p) measured as a fraction of the serial reference time:

The overhead may include thread creation, communication, synchronization, memory contention, and reduction operations.

2.3 Gustafson’s law

Amdahl’s law assumes a fixed problem size. In scientific and engineering practice, users often increase the problem size as more processors become available. If s is the fraction of the parallel execution time spent in serial work on p processors, scaled speedup is modeled as

This model emphasizes that parallel systems can solve larger problems within a similar elapsed time, provided the serial component does not grow excessively.

Worked Example: Amdahl’s Law

A workload has a serial fraction of 0.08 and is executed on 16 processors. The ideal speedup is

S_A(16) = 1/(0.08 + 0.92/16)

0.92/16 = 0.0575, so the denominator is 0.1375 and

S_A(16) ≈ 7.27.

Efficiency is approximately 7.27/16 = 0.454, or 45.4%. The result demonstrates why adding processors can produce disappointing returns even when the parallel portion is large.

3. Parallel Architecture Organizations

3.1 Shared-memory multiprocessors

In a shared-memory system, processors address a common logical memory space. A shared-memory multiprocessor may be:

• Uniform memory access (UMA): approximately equal access time for all processors.
• Non-uniform memory access (NUMA): local memory is faster than remote memory, although all memory remains addressable.

NUMA systems scale better in many cases, but software must consider data placement. Poor placement can cause remote-memory traffic and reduce performance.

3.2 Cache coherence and consistency

When multiple processors cache the same memory block, updates must be coordinated. Cache coherence concerns whether all processors eventually observe compatible values for a particular memory location. Protocols such as MSI, MESI, and MOESI use states and coherence messages to maintain this property.

Memory consistency defines the ordering rules visible to software across different memory locations. Coherence does not by itself specify a complete ordering of all loads and stores. Weak or relaxed consistency models permit more hardware reordering and require synchronization operations, such as locks, barriers, fences, or atomic instructions, when ordering matters.

3.3 Distributed-memory systems

In distributed-memory systems, each node has private memory and communicates explicitly through messages. Clusters and supercomputers commonly use this model. Distributed memory scales to large installations because memory and communication hardware can be added with nodes, but programmers must manage data distribution, communication, and failure of components.

A common programming model is MPI. Its performance depends on message size, network latency, bandwidth, topology, and collective-operation algorithms.

3.4 Flynn’s taxonomy

Flynn’s taxonomy classifies systems by instruction streams and data streams:

The taxonomy is useful historically, but modern systems often combine categories. A GPU may execute a common instruction over many lanes while containing multiple independent scheduling units; a CPU may simultaneously exploit scalar ILP, SIMD, and multithreading.

4. Vector and SIMD Architectures

4.1 Vector processing

A vector processor operates on vectors rather than only scalar values. A vector instruction specifies an operation and a vector length, and the hardware applies that operation across lanes. Vector registers may hold multiple elements, while vector load and store mechanisms move contiguous or strided data between memory and registers.

Important vector features include:

• Vector length: number of active elements in an operation.
• Masking: enables or disables selected lanes, supporting conditional computation.
• Stride: spacing between successive memory elements.
• Gather/scatter: loads or stores elements at noncontiguous addresses.
• Chaining: permits a dependent vector instruction to begin before the entire producer vector has completed.
• Reduction: combines vector elements, such as summation or maximum.

Vector architectures are especially effective when operations are regular, data-parallel, and sufficiently large to amortize instruction and setup costs.

4.2 Fixed-width SIMD extensions

SIMD extensions place several scalar elements in a fixed-width register. For example, a 256-bit register can contain eight 32-bit elements. One instruction may add the corresponding elements of two registers. The number of elements is

where W is register width in bits, b is element width in bits, and L is the number of lanes. This ideal lane count assumes all bits are used for identical elements and ignores masking or implementation-specific constraints.

Fixed-width SIMD offers high throughput but can be sensitive to alignment, remainder elements, branches, and data layout. Compilers may automatically vectorize loops when they can prove that iterations are independent and memory accesses are safe.

4.3 Vectorization example

Consider

C[i] = A[i] + αB[i]

for i = 0, …, n-1, where arrays do not overlap and α is a scalar. The loop has DLP because each iteration reads independent elements and writes a distinct element. A vector implementation loads groups of elements from A and B, broadcasts α, performs vector multiply-add operations, and stores the result. If n is not a multiple of the vector length, masking or a scalar cleanup loop handles the remainder.

The operation count is approximately 2n floating-point operations: one multiplication and one addition per element. However, performance may be limited by memory bandwidth rather than arithmetic throughput.

4.4 Roofline reasoning

The arithmetic intensity of a kernel is

where F is the number of arithmetic operations and Q is the number of bytes transferred between the relevant memory level and processor. If peak compute performance is P_peak operations per second and sustainable memory bandwidth is B bytes per second, an ideal upper bound is

The equation assumes a defined memory level, sustainable bandwidth, and operations counted consistently. A low-intensity vector addition is often bandwidth-bound; increasing arithmetic units alone may therefore have little effect.

5. GPUs and Manycore Processors

Graphics processing units are throughput-oriented processors designed to execute very large numbers of lightweight threads. A GPU commonly groups threads into warps or wavefronts that execute a common instruction path. If threads in a group follow different branches, execution may be serialized; this is called control-flow divergence.

GPUs achieve high throughput through:

• many arithmetic lanes;
• hardware thread scheduling;
• high-bandwidth global memory;
• programmer-visible memory hierarchies;
• shared or local on-chip memories;
• massive concurrency to hide latency.

A GPU is not automatically faster than a CPU. Performance depends on sufficient parallelism, regular memory access, manageable divergence, data-transfer costs, and an appropriate kernel decomposition. Irregular graph algorithms, small sequential tasks, and pointer-heavy workloads may favor CPUs or specialized designs.

6. Heterogeneous Architectures

A heterogeneous system contains processing elements with different instruction sets, performance characteristics, memory spaces, or energy profiles. A typical platform may include CPU cores for control-intensive code, GPUs for large data-parallel kernels, and an NPU for matrix operations in machine learning.

6.1 CPU–accelerator interaction

A heterogeneous computation typically follows these stages:

1. Partition the application into kernels or tasks.
2. Select a processor for each part.
3. Establish data ownership and placement.
4. Transfer or map data when necessary.
5. Launch the kernel or task.
6. Synchronize only where dependencies require it.
7. Collect results and balance future work.

The total time is not simply the sum of processor execution times. It may include launch latency, data movement, synchronization, and contention. A useful abstract model is

where terms must be defined for a particular execution schedule. If CPU and accelerator work overlap, the relevant critical-path time may instead resemble the maximum of concurrent phases plus unavoidable dependencies.

6.2 Unified and discrete memory

In a discrete CPU–GPU system, accelerator memory is physically separate. Data transfers over an interconnect can dominate execution for small kernels. Unified virtual addressing can simplify pointer management, but it does not necessarily eliminate physical movement or synchronization costs.

Shared physical memory may reduce copying, yet it introduces competition for bandwidth and more complex coherence or consistency behavior. High-bandwidth memory improves throughput for bandwidth-intensive kernels, but capacity and cost remain constraints.

6.3 Heterogeneous programming models

Common approaches include:

• OpenMP: shared-memory parallelism with compiler directives and target offload features.
• MPI: explicit message passing for distributed-memory systems.
• CUDA and similar kernel models: explicit GPU thread and memory programming.
• SYCL and other single-source models: C++-oriented heterogeneous programming.
• Task runtimes: dependency-aware scheduling across CPUs and accelerators.

Portability is not identical to performance portability. A program may run on many devices while obtaining excellent performance on only one. Abstraction layers reduce programming effort but may hide data movement or produce suboptimal mappings.

7. Mapping, Scheduling, and Synchronization

Parallel performance depends on mapping work to resources. Static scheduling assigns work before execution and is effective when tasks have predictable costs. Dynamic scheduling assigns work at runtime and handles imbalance better, but scheduling itself adds overhead.

Amdahl’s law describes limits from serial work, while load imbalance describes unequal distribution of parallel work. If processor execution times are t₁, t₂, …, t_p, the parallel phase completes no sooner than

Ignoring communication, ideal equal distribution gives approximately T_work/p. The difference between actual completion time and this ideal is an imbalance cost.

Synchronization mechanisms include locks, barriers, atomics, reductions, and transactional techniques. Excessive locking causes contention; insufficient synchronization causes races. A data race occurs when conflicting accesses are not ordered according to the programming model and at least one access is a write.

False sharing is a performance problem in which independent variables used by different threads occupy the same cache line. Updates then cause unnecessary coherence traffic. Padding, data layout changes, or ownership partitioning can reduce it.

8. Memory, Communication, and Scalability Challenges

8.1 The memory wall

Processor arithmetic capability has often grown faster than latency improvement in main memory. Consequently, cache locality, blocking, prefetching, data reuse, and memory placement are central to parallel design. A blocked matrix multiplication reuses tiles in fast memory, reducing repeated transfers from slower memory.

8.2 Communication costs

A simplified message-transfer model is

where α is startup latency in seconds, m is message size in bytes, and β is bandwidth in bytes per second. The model assumes a single message path and excludes contention, routing, protocol effects, and overlap. It shows why many small messages are expensive and why aggregation can help.

8.3 Scalability types

• Strong scaling: fixed total problem size while processor count increases.
• Weak scaling: problem size grows with processor count so work per processor remains approximately constant.
• Embarrassingly parallel: little or no communication, such as independent Monte Carlo trials.
• Irregular parallelism: changing workloads or data-dependent dependencies, such as graph traversal.

A scalable design must address not only processor count but also memory capacity, network topology, software overhead, and fault management.

9. Case Study: Heterogeneous Image-Analysis Pipeline

This is an illustrative case study.

Background

A medical-imaging service processes high-resolution scans. The pipeline performs image decoding, noise reduction, convolutional feature extraction, and report preparation. The service must deliver predictable latency while controlling energy consumption.

Problem

A CPU-only implementation is easy to maintain but has insufficient throughput during peak demand. Moving the entire pipeline to a GPU is unattractive because decoding and report preparation contain branches, while feature extraction is highly data-parallel. Images also vary in size, creating load imbalance.

Analysis

Profiling identifies convolution as the dominant arithmetic workload. It has regular tensor operations and high DLP, making it suitable for a GPU or neural accelerator. Decoding is control-intensive and remains on CPU cores. The transfer cost is significant for small images, so batches are formed when latency requirements allow. The system uses pinned buffers and asynchronous transfers to overlap CPU preparation, device execution, and result retrieval.

Approach

A task runtime represents each image as a dependency graph:

• CPU task: decode and validate input.
• Accelerator task: denoise and perform convolutional inference.
• CPU task: post-process, apply policy checks, and generate metadata.

A bounded queue prevents uncontrolled batching from violating latency objectives. Measurements record end-to-end latency, device utilization, transfer time, energy per image, and error rates. Results are checked against a CPU reference implementation on selected inputs to detect numerical or synchronization errors.

Outcome

The heterogeneous design improves throughput when batches are large enough to amortize transfers. For small isolated images, CPU execution may be competitive because launch and transfer overheads dominate. The final policy therefore uses a size-based dispatch rule rather than sending every job to the accelerator.

Learning points

1. Kernel speed is not the same as application speed.
2. Data movement must be included in performance models.
3. Different pipeline stages may require different processors.
4. Dispatch policies should be measured under realistic workload distributions.
5. Numerical validation, privacy controls, and predictable latency are as important as throughput in a medical context.

10. Evaluation and Best Practices

A rigorous evaluation should report workload, input size, compiler and library versions, processor configuration, thread count, memory placement, warm-up policy, and statistical treatment of repeated measurements. Wall-clock time, throughput, speedup, efficiency, bandwidth, energy, and tail latency may all be relevant.

Recommended practices include:

• profile before parallelizing;
• expose sufficient coarse-grained parallel work;
• minimize synchronization and data movement;
• use locality-aware data layouts;
• verify race freedom and numerical reproducibility requirements;
• benchmark representative, not only ideal, inputs;
• separate kernel performance from end-to-end performance;
• select hardware according to workload characteristics;
• use portable abstractions where appropriate, but inspect generated code and transfers;
• document affinity, placement, and scheduling assumptions.

Ethical, governance, and security considerations

Heterogeneous and parallel systems raise governance issues beyond speed. Accelerators may process personal, medical, or financial data, requiring access control, encryption, retention policies, and auditable execution. Shared accelerators can create side channels through timing, caches, or memory reuse. Multi-tenant cloud operators should isolate workloads and clear sensitive buffers. AI accelerators also require validation of numerical behavior, model drift, fairness, and explainability appropriate to the application. Energy consumption and embodied hardware cost should be included in architectural decisions.

11. Contemporary Directions

Current research explores chiplet-based processors, coherent CPU–accelerator fabrics, processing-in-memory, reconfigurable logic, sparse and approximate computation, near-data processing, and domain-specific architectures. Machine-learning workloads motivate tensor units that perform matrix multiply-accumulate operations with high energy efficiency. At the same time, irregular applications motivate architectures with flexible synchronization, larger memory capacity, and improved graph processing.

Important research questions include how to program diverse devices without losing performance, how to schedule under power and thermal limits, how to guarantee timing for safety-critical systems, and how to make numerical approximation observable and controllable. Future systems are likely to be increasingly heterogeneous, making architecture–compiler–runtime co-design essential.

Chapter Summary

Parallel architecture increases performance by executing independent work concurrently, but speedup is constrained by serial execution, overhead, imbalance, memory behavior, and communication. Amdahl’s law is useful for fixed workloads, while Gustafson’s law explains the value of scaling problem size. Shared-memory systems require attention to coherence, consistency, synchronization, and NUMA placement; distributed-memory systems require explicit communication and data distribution.

Vector and SIMD architectures exploit data-level parallelism through lanes, masks, vector lengths, and regular memory access. Their performance is often governed by arithmetic intensity and memory bandwidth, as expressed by roofline reasoning. GPUs and manycore processors provide massive throughput but are sensitive to divergence, irregular access, and kernel granularity.

Heterogeneous systems combine CPUs, GPUs, vector engines, and specialized accelerators. Successful designs partition work according to computational structure, account for transfer and synchronization costs, and evaluate end-to-end behavior. Professional practice requires measurement, correctness validation, security, energy awareness, and workload-specific hardware selection.

Key Terms

Parallelism: Concurrent execution of multiple operations or activities.

Instruction-level parallelism: Overlap among independent instructions in one thread.

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

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

SIMD: Single instruction, multiple data execution.

Vector processor: Processor that applies instructions to sequences of data elements.

Speedup: Ratio of reference execution time to parallel execution time.

Efficiency: Speedup divided by the number of processing elements.

Amdahl’s law: Fixed-workload speedup model limited by serial execution.

Gustafson’s law: Scaled-workload speedup model.

Cache coherence: Agreement about values of a particular memory location across caches.

Memory consistency: Rules governing the visible ordering of memory operations.

NUMA: Non-uniform memory access in which locality affects access time.

GPU: Throughput-oriented manycore processor designed for massive concurrency.

Heterogeneous architecture: System containing different types of processing elements.

Arithmetic intensity: Operations performed per byte transferred.

Roofline model: Performance bound based on compute capability and bandwidth.

False sharing: Unnecessary coherence traffic caused by independent data sharing a cache line.

Load imbalance: Unequal distribution of work among processing elements.

Data race: Unordered conflicting concurrent accesses involving at least one write.

Review Questions

Short Answer Questions

1. Define data-level parallelism and give one example.
2. Distinguish cache coherence from memory consistency.
3. What is the purpose of masking in vector execution?
4. State two reasons why GPU execution may not outperform CPU execution.
5. Define strong scaling and weak scaling.

Long Answer Questions

1. Explain Amdahl’s law, derive its limiting speedup, and discuss its assumptions.
2. Compare shared-memory and distributed-memory architectures with respect to programming, scalability, and communication.
3. Describe the organization and performance characteristics of vector processors and fixed-width SIMD units.
4. Explain how memory hierarchy and arithmetic intensity influence parallel application performance.
5. Discuss the architecture, programming, and governance challenges of heterogeneous CPU–accelerator systems.

Analytical / Application Questions

1. A program contains a 12% serial fraction and runs on 24 processors. Calculate ideal Amdahl speedup and efficiency. Interpret the result.
2. A GPU kernel performs 4,000 million operations and transfers 20,000 million bytes. Compute arithmetic intensity and explain whether increasing peak arithmetic throughput alone is likely to help.
3. Design a CPU–GPU mapping for a video-processing pipeline containing decoding, convolution, irregular object tracking, and final encoding. Justify placement, data movement, and scheduling decisions.

Multiple Choice Questions with Answers

Question 1

A workload has a serial fraction of 0.05. What is its ideal maximum speedup as the processor count approaches infinity?

A. 5

B. 10

C. 20

D. 50

Correct Answer: C. 20

Question 2

Which characteristic most directly indicates data-level parallelism?

A. Independent loop iterations applying the same operation

B. A single branch with unpredictable control flow

C. A lock protecting a shared counter

D. A sequential pointer chain

Correct Answer: A. Independent loop iterations applying the same operation

Question 3

In a NUMA system, which access is generally fastest?

A. Access to a remote node’s memory

B. Access to local memory attached to the requesting processor

C. Access through a network filesystem

D. Access to uncached persistent storage

Correct Answer: B. Access to local memory attached to the requesting processor

Question 4

What does SIMD mean?

A. Single instruction, multiple data

B. Single instruction, minimum data

C. Separate instructions, multiple devices

D. Scheduled instruction, memory-dependent

Correct Answer: A. Single instruction, multiple data

Question 5

A 256-bit SIMD register contains 32-bit elements. Ignoring masks and implementation constraints, how many elements fit in the register?

A. 4

B. 8

C. 16

D. 32

Correct Answer: B. 8

Question 6

Which situation is most likely to reduce GPU efficiency through control-flow divergence?

A. All threads execute identical instructions

B. Threads in an execution group take different branches

C. Data is stored contiguously

D. A kernel has sufficient independent work

Correct Answer: B. Threads in an execution group take different branches

Question 7

In the simplified message model T_message = α + m/β, what does α represent?

A. Message size

B. Arithmetic intensity

C. Startup latency

D. Processor count

Correct Answer: C. Startup latency

Question 8

A kernel performs 2,000 operations and transfers 500 bytes. What is its arithmetic intensity?

A. 0.25 operations/byte

B. 2 operations/byte

C. 4 operations/byte

D. 10 operations/byte

Correct Answer: C. 4 operations/byte

Question 9

Which problem is a typical consequence of false sharing?

A. Unnecessary cache-coherence traffic

B. Elimination of all data dependencies

C. Infinite memory bandwidth

D. Guaranteed deterministic scheduling

Correct Answer: A. Unnecessary cache-coherence traffic

Question 10

Why might a heterogeneous system keep image decoding on the CPU while sending convolution to a GPU?

A. Decoding is always more arithmetic-intensive than convolution

B. Convolution is commonly regular and data-parallel, while decoding may be control-intensive

C. GPUs cannot execute multiplication

D. CPUs cannot perform input/output

Correct Answer: B. Convolution is commonly regular and data-parallel, while decoding may be control-intensive