1

Sri Raghavendra Educational Institutions Society (R)

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

Sri Krishna Institute of Technology

www.skit.org.in

Prepared by:

Latha

​

Course: Parallel Computing

​

Department: Computer Science &Engineering

Course Code: BCS702 | Semester: VII | Credits: 04

Teaching Hours: 3:0:2:0 | CIE Marks: 50 | SEE Marks: 50

2

Vision of CSE Dept.

To be in the frontier of Computer Science & Engineering and to create Technically competent graduates with ethical, moral values committed to meet Industry and Societal needs.

Mission of CSE Dept.

M1: To produce ethical, motivated, and skilled engineers through theoretical knowledge and practical applications.

M2: Inculcate problem solving and team building skills and promote lifelong learning with a sense of social responsibilities.

M3:To facilitate functional ambience for research, consultancy and entrepreneurship.

Course Objectives

Explore Parallel Programming

Understand the fundamental need for parallel programming in modern computing

MIMD Systems

Explain how to parallelize applications on Multiple Instruction, Multiple Data systems

MPI Library

Demonstrate how to apply Message Passing Interface library to parallelize suitable programs

OpenMP

Demonstrate how to apply OpenMP pragma and directives to parallelize suitable programs

CUDA Programming

Demonstrate how to design CUDA programs for GPU-based parallel computing

Classification of Parallel Computers

Flynn's Taxonomy

Based on instruction and data streams:

• SIMD: Single Instruction, Multiple Data

• MIMD: Multiple Instruction, Multiple Data

Memory Architecture

Based on memory access:

• Shared Memory: Cores share common memory

• Distributed Memory: Each core has private memory

SIMD Systems

Single Instruction, Multiple Data systems apply the same instruction simultaneously to multiple data streams.

Control Unit

One control unit broadcasts instructions to multiple datapaths

Multiple Datapaths

Each datapath either executes the instruction on its data or remains idle

Data Parallelism

Ideal for operations on large data arrays (e.g., vector addition)

Modern implementations include vector processors and GPUs, which are highly efficient for data-parallel problems but struggle with other types of parallelism.

Parallel Execution: SIMD applies the same instrExample: For auction (addition) to multiple data elements simultaneously.

loop x[i] += y[i];, SIMD can process several x and y values at once.

• Full Utilization: If there are n datapaths for n elements, each datapath handles one element, and the whole loop runs in one parallel step.
• Partial Utilization: If there are fewer datapaths (m < n), elements are processed in blocks of size m.
• Example: With m = 4 datapaths and n = 15 elements → execution occurs in blocks:
• Block 1: Elements 0–3
• Block 2: Elements 4–7
• Block 3: Elements 8–11
• Block 4: Elements 12–14
• Inefficiency Issue: In the last block, not all data paths may be used → some stay idle, reducing efficiency.

Vector Processors

Operates on arrays/vectors (not individual scalars like CPUs).

• Vector Registers: Store multiple operands and process all elements simultaneously (length 4–256 typical).
• Vectorized & Pipelined Units: Apply same operation across vector elements, following SIMD model.
• Vector Instructions: Perform operations on entire vectors (one load-add-store per block), far more efficient than scalar CPUs.
• Interleaved Memory: Multiple banks allow parallel memory access with minimal delay.
• Strided Access & Scatter/Gather: Specialized hardware supports accessing data at fixed intervals or irregular positions efficiently.

Advantages: High memory bandwidth, efficient data use, compiler support for auto-vectorization.

Limitations: Struggles with irregular data, limited scalability by vector length, expensive for long vectors, commodity systems support only short vectors.

Graphics Processing Units

Graphics Pipeline: Converts objects (points, lines, triangles) into pixels; programmable via short parallel shader functions.

• Parallelism: GPUs use SIMD parallelism with many datapaths (128+ per core).
• High Data Movement: Processing large images requires high bandwidth & hardware multithreading to avoid stalls.
• Thread Management: Can suspend/store hundreds of threads per executing thread.
• Performance Note: Excellent for large workloads, but less efficient on smaller problems.
• Hybrid Model: Combine SIMD within cores + MIMD across cores.
• Memory Models: Use shared, distributed, or hybrid memory architectures.
• HPC Use: Widely applied in AI, simulations, and scientific computing via CUDA, OpenCL, etc.

Prof. Latha, Dept of CS&E

9

Key Characteristics of MIMD

• Multiple instruction streams running on multiple data streams
• Independent processing units with own control unit and datapath
• Asynchronous operation - processors work at their own pace
• More flexible than SIMD but more complex to program
• 2 main types of MIMD systems
1. shared-memory systems
2. distributed-memory systems

MIMD Systems

shared-memory systems v/s distributed-memory systems

Prof. Latha, Dept of CS&E

11

In shared-memory systems, multiple processors are connected to a common memory through an interconnection network, allowing each processor to access any memory location. Communication between processors typically occurs implicitly by accessing shared data structures.

Distributed-memory systems pair each processor with its own private memory, and these processor-memory pairs communicate explicitly over a network. Communication usually involves sending messages or using special functions to access another processor’s memory

UMA and NUMA multicore system of Shared Memory Model

Prof. Latha, Dept of CS&E

12

Distributed-Memory Systems

• Clusters are the most common type: built from standard computers (nodes) connected via networks (e.g., Ethernet).
• Each node is usually a shared-memory system with multicore processors.
• Such systems are called hybrids since they combine shared-memory within nodes and distributed-memory across nodes.
• Grids connect geographically dispersed computers to act as one distributed-memory system, often with heterogeneous hardware.

Prof. Latha, Dept of CS&E

13

Importance of Interconnects

• Crucial for performance in both memory access systems.
• Even with fast processors/memory, a slow interconnect can become a bottleneck for parallel programs.

Shared-Memory Interconnects

• Earlier systems used a bus:
• Shared communication lines
• Simple and cost-effective.
• Limitations of buses:
• As the number of devices increases, contention increases.
• Leads to performance degradation due to memory access delays.
• Modern systems use switched interconnects:
• More scalable.
• Efficient for handling larger processor counts.

Prof. Latha, Dept of CS&E

14

Switched Interconnects

• Use switches to control data flow between devices.
• Allow for efficient and organized communication.
• Example: Crossbar switch – simple yet powerful.

Crossbar Structure

• Cores/Memory modules: Represented as squares.
• Switches: Shown as circles.
• Links: Bidirectional communication lines.

Conflict and Access

• If there are at least as many memory modules as processors, conflicts occur only when two processors try to access the same memory module simultaneously.
• Fig. 1.5(c) shows an example with no conflicts:
• P1 → M4 (write)
• P2 → M3 (read)
• P3 → M1 (read)
• P4 → M2 (write)

Performance and Cost Tradeoff

• Crossbars enable simultaneous communication between multiple devices.
• Much faster than bus-based systems.
• Drawback: Higher cost due to more switches and links, especially in larger systems.

15

Simultaneous memory accesses by the processors

Distributed-memory interconnects

Distributed interconnects are of two types:

1. Direct interconnects – Each switch connects directly to a processor-memory unit, and switches are interconnected to form the network.
2. Indirect interconnects – Connections between processors occur through intermediate switches in a multistage structure.

​

Examples of Direct Interconnects

1. Ring Topology
• Each switch is connected in a circular manner.
• Switch-to-switch links: For p processors, there are p links (e.g., 3 in the figure).
• Pros:
1. Better than a simple bus. 2. Multiple communications can occur simultaneously.
• Cons:
• Communication delays occur if some processors must wait for others.

16

A ring

Two-Dimensional Toroidal Mesh

• Switches are arranged in a grid, with wrap-around connections forming a torus.
• Switch-to-switch links: For p processors, requires 2p links (e.g., 18 in the figure).
• Pros:
• Higher number of simultaneous communication paths.
• Reduces congestion compared to a ring.
• Cons:
• More expensive (each switch handles 5 links instead of 3).

​

In short:

• Ring = simple, cheaper, but limited performance.
• Toroidal Mesh = complex, costlier, but supports more parallel communication.

​

17

A toroidal mesh

Bisection

Bisection width:

• Defined as the minimum number of links that must be removed to split the network into two equal halves.
• For a square 2D toroidal mesh with p = q^2 (q even), this is achieved by cutting the middle and wraparound horizontal links.
• Result: Bisection width => 2 where q = 2 √p.

Bisection bandwidth:

• Refers to the total bandwidth of the links connecting two halves of a network.
• Example: In a ring where each link has 1 Gbps bandwidth, the bisection bandwidth = 2 Gbps (2000 Mbps).

Key distinction:

• Bisection width = number of links cut.�Bisection bandwidth = total data transfer rate of those cut links.

18

Fig 1.7 (a): Only two communications can take place between the halves

Fig 1.7 (b): Four simultaneous connections can take place.

Fully connected network

• Ideal direct interconnect where each switch is directly linked to every other switch.
• It has a high bisection width of p²/4, offering maximum communication capacity.
• However, it becomes impractical for large systems, as it requires p²/2−p/2 links and each switch must support p connections.
• As a result, it is considered more of a theoretical benchmark

19

Hypercube

The hypercube is a highly connected direct interconnect, implemented in real systems.

🔹 Structure of a Hypercube

• 1-D hypercube = 2 nodes connected by 1 link.
• 2-D hypercube (square) = 4 nodes, each connected to 2 others.
• 3-D hypercube (cube) = 8 nodes, each connected to 3 others.
• In general, a d-dimensional hypercube has: p = 2ᵈ nodes�Each node has degree d = log₂(p) connections.

🔹 Bisection Width of Hypercube

• To bisect the network into two equal halves, you must cut p/2 links.
• So, bisection width = p/2, much higher than:

Ring → 2 2D Mesh → √p�Hypercube → p/2 (scales linearly with number of nodes!)

​

👉 This means the hypercube supports far more simultaneous cross-network communications than rings/meshes.

​

20

(a) One (b) two and (c) three-dimensional hypercubes

Indirect interconnects

Indirect interconnects - switches may not be directly linked to processors.

• These networks are typically illustrated with unidirectional links, where each processor has one outgoing and one incoming link connected to a switching network.

Examples of simple indirect interconnects

• Crossbar and omega networks are common.
• In a distributed-memory crossbar, unidirectional links allow for structured data flow between processors.
• As long as no two processors try to send data to the same destination simultaneously, all processors can communicate with others in parallel, maximizing throughput.

​

21

A generic indirect network.

A crossbar interconnect for distributed-memory.

omega network

it is composed of multiple two-by-two crossbar switches but it does not support all communications simultaneously.

For instance, if processor 0 sends data to processor 6, processor 1 cannot concurrently send data to processor 7.

omega network is more cost-efficient, requiring only 1/2plog2(p) of the 2X2 crossbar switches, totaling 2plog2(p) switches—significantly fewer than the p^2 switches used in a full crossbar.

Latency and bandwidth

Latency is the time delay between the start of transmission and the arrival of the first byte at the destination

bandwidth refers to the rate at which data is received after the first byte.

Together, these factors determine the total time to send a message of n bytes across an interconnect with latency l seconds and bandwidth b bytes per second.

message transmission time = l + n/b

22

Mindmap of interconnects

23

Cache Coherence

• When multiple cores in a multiprocessor system have their own caches, they may hold copies of the same memory block - cache coherence problem

eg. The shared variable x is initialized to 2, while y0 (Core 0), y1, and z1 (Core 1) are private variables owned by their respective cores.

• At time 0, both cores read from x: Core 0 sets y0 = x, so y0 becomes 2. Core 1 sets y1 = 3 * x, so y1 becomes 6 (3 × 2).
• At time 1, Core 0 updates x = 7. This change may only reflect in Core 0’s cache, depending on the cache behavior.
• At time 2, Core 1 computes z1 = 4 * x. However, since it may still have the old value of x = 2 cached, z1 could become 8 (4 × 2), instead of the expected 28 (4 × 7).If one processor updates its cache copy, the others may have stale (outdated) values.

24

25

Cache coherence protocols

Cache coherence protocols ensure all caches see a consistent view of memory.

1. Snooping Cache Coherence
2. directory-based coherence protocols.

​

26

Snooping Cache Coherence

• Snooping is a hardware-based cache coherence mechanism where all caches "listen" (snoop) on a common communication medium (like a system bus) to monitor read/write transactions.
• All processors are connected to a Shared Bus or Interconnect and Every cache controller monitors (snoops) bus traffic.
• Read Miss: If a cache misses, it broadcasts a read request on the bus. Other caches snoop and, if they have the data, may supply it.

27

• Write: When a processor writes, it broadcasts this on the bus. Other caches snoop and either:
• Invalidate their copies (Write-Invalidate protocol) Or
• update their copies (Write-Update protocol)

Snooping Cache Coherence

• Snooping works with both write-through and write-back caches:
• in write-through, updates are visible through regular memory writes;
• in write-back, extra communication is required since changes stay in cache until explicitly written back to memory.
• Broadcasting becomes inefficient as system size grows.
• Performance degrades with increasing cores (scalability issue).
• Works well for small shared-bus multiprocessors, but not scalable

28

Directory-based cache coherence

• Directory is often distributed (each memory module manages its own lines).

​

• Read operation → directory records which cores cache the line.

​

• Write operation → directory invalidates copies in other caches before update.

​

• Avoids broadcasting → improves efficiency in large-scale multiprocessors.

29

30

False Sharing

• CPU caches operate at the granularity of cache lines not individual variables..
• Suppose we have m iterations of a loop and core_count cores. Each core gets about m / core_count iterations in parallel program
• Eg: Assume Number of cores: 2 and Array size: m = 8 doubles. Each double is 8 bytes, Hence no. of Cache line size: 64 bytes. so array y[8] occupies exactly 1 cache line.
• Problem:� Even if Core 0 updates y[0..3] and Core 1 updates y[4..7], all elements still map to the same cache line.
• When Core 0 writes to its part, the cache line in Core 1 becomes invalid.
• Then Core 1 must fetch the updated line before writing to its own elements.
• This back-and-forth invalidation causes excessive memory traffic.

31

• Definition of false sharing :�a situation where different cores modify independent variables, but since those variables reside in the same cache line, the hardware treats them as shared, causing unnecessary cache coherence operations.
• Impact:
• Performance degradation (extra cache misses, memory traffic).
• Appears as if cores are sharing data, but in reality, they are only sharing a cache lines

32

Shared-Memory Programming

• Shared variables: Accessible by all threads.
• Private variables: Local to a single thread.
• Communication: Happens implicitly through shared variables rather than explicitly (as in message-passing models).

Dynamic Threads

• Model: Master thread + worker threads (created on demand).
• Process:
• Master thread receives work requests (e.g., from a network).
• A worker thread is forked to handle each request.
• Worker completes the task, then terminates and rejoins the master.
• Advantages:
• Efficient use of resources—threads exist only while active.
• Flexible, as the number of threads adapts to workload.
• Disadvantages:
• Overhead from frequent creation and destruction of threads.

33

Static Threads

• Model: All threads created once after setup.
• Process:
• Threads remain alive until all work is done.
• After completion, they rejoin the master thread.
• Master handles cleanup (e.g., freeing memory).
• Advantages:
• Avoids repeated overhead of thread creation/termination.
• Can achieve better performance if resources are sufficient.
• Matches distributed-memory programming models more closely.
• Disadvantages:
• Less resource-efficient—idle threads still occupy memory/CPU resources.

Nondeterminism

• In MIMD (Multiple Instruction, Multiple Data) systems, each processor runs its own instruction stream independently.
• Since threads don’t execute in lockstep, the exact timing of loads, computations and stores can differ from one run to another.
• This means that even with the same input, the output may vary, depending on how instructions interleave across threads.

Example: Shared variable update

Suppose we have:

• Shared variable: x = 0
• Thread 0: my_val = 7
• Thread 1: my_val = 19

Both threads execute and after completion of instruction:

• Thread 0: my_val = 7
• Thread 1: my_val = 19

34

• Thread 1: my_val = 19
• Thread 0: my_val = 7

Race Conditions and Synchronization in Shared-Memory Systems

Parallel Access to a Shared Variable

Scenario: Core 0 and Core 1 both attempt to update the same shared variable x concurrently.Each core uses its own private value (my_val) in the update.

Operation Sequence:

Each core executes the following steps:

Load x.

Load my_val.

Compute x + my_val.

Store the result back into x.

Although these steps appear independent, both cores affect the same memory location.

35

Race Condition

When two or more threads concurrently access and modify a shared resource, the result depends on the unpredictable order of execution.

Both threads read x = 0 before writing.

Depending on timing, the final value of x could be 7 or 19, instead of the correct 26.

This loss of updates is a classic race condition.

Ensuring Correctness

• Atomicity

The operation x += my_val must be atomic: No other thread can access or modify x until the update completes.

• Critical Section

A block of code that must not be executed by more than one thread at a time. Eg: placing x += my_val inside a critical section ensures correct results.

• Mutual Exclusion (Mutex)

A mutex (mutual exclusion lock) enforces that only one thread can enter the critical section at a time.

• Locking mechanism:

Thread acquires the lock before entering and Thread releases the lock after completing the update.

• System Support

Mutexes are supported at both the hardware and operating system levels.

It is the programmer’s responsibility to use synchronization constructs to avoid race conditions.

36

Distributed Memory Systems and Message-Passing Model

In distributed memory system, each processor (core) has its own private memory.

No direct access to another processor’s memory (communication is explicit) since processors may be located on entirely different machines, connected by a network. Hence Parallelism is achieved by running separate processes

👉 This is why frameworks like MPI are necessary—

they let independent processes talk to each other.

• Processes are identified by ranks: 0 through p−1, where p is the total number of processes.
• Send/Receive are the fundamental operations:
• Send(buffer, type, count, destination_rank)
• Receive(buffer, type, count, source_rank)
• SPMD (Single Program Multiple Data) model:
• All processes run the same program, but branch execution depending on my_rank.

37

Example: only process 1 sends a message, only process 0 receives

char message[100];

my_rank = Get_rank();

​

if (my_rank == 1) {

sprintf(message, "Greetings from process 1");

Send(message, MSG_CHAR, 100, 0); // send to rank 0

}

else if (my_rank == 0) {

Receive(message, MSG_CHAR, 100, 1); // receive from rank 1

printf("Process 0 > Received: %s\n", message);

}

Blocking vs Non-blocking Communication

• Blocking Send: the sender waits until the receiver has started receiving.
• Buffered Send: sender copies the message into an internal buffer and can proceed immediately.
• Blocking Receive: the receiver waits until the full message arrives.
• Non-blocking versions (Isend, Irecv in MPI): let processes continue working while communication is in progress.

Message-passing APIs (like MPI) provide:

• Collective communication:
• Broadcast : one-to-all
• Scatter/Gather : one-to-many or many-to-one
• Reduce : combine results (e.g., sum, min, max) across processes
• Process management: grouping processes, synchronizing, etc.
• Support for complex datatypes: not just raw arrays, but structured data.

38

Advantages and Challenges

​

✅ Advantages:

• Works on clusters and supercomputers (scales across thousands of machines).
• Makes parallelism possible when memory is physically separate.

⚠️ Challenges:

• Programmer effort is high—you must explicitly decide:
• What data goes to which process,
• When to send/receive,
• How to minimize communication cost.
• Often requires rewriting code rather than small modifications.

This is why MPI is sometimes called the assembly language of parallel programming.

39

One-Sided Communication

In Message Passing system/ (Send/Receive): Both processes, sending and receiving process must participate explicitly. Eg: Process 0 calls Send, Process 1 calls Receive. Synchronization is “built-in” because both sides must act.

In One-sided (RMA): Only one process initiates communication-Eg. Process 0 can directly read from or write to memory belonging to Process

✅ Advantages

• Reduces synchronization overhead (no matching receive needed).
• Fewer function calls.
• Can improve performance on systems with special hardware (e.g., RDMA in InfiniBand networks).

⚠️ Drawbacks

• Requires careful synchronization to avoid race conditions.
• More difficult to program correctly and debug.
• Polling can negate the performance benefits

40

Partitioned global address space languages

• Many programmers prefer shared-memory programming over message-passing or one-sided communication, so several groups are working on languages that bring shared-memory features to distributed-memory systems.
• This approach is complex
• Simply treating all memory in a distributed system as one large shared memory would lead to poor or unpredictable performance. This is because a process might access either local memory, which is fast, or remote memory, which can be hundreds or thousands of times slower.
• Efficient use of such systems requires careful management of where and how memory is accessed.

Partitioned Global Address Space (PGAS) languages offer

• features similar to shared-memory programming but give the programmer more control over data placement.
• Private variables are stored in the local memory of the core running the process, helping to reduce unnecessary remote memory access.
• Additionally, the programmer can explicitly define how shared data structures, such as arrays, are distributed across processes local memories.

41

42

43

44

45

https://mapify.so/share-link/1qHgZs6lAK

​

46