Tab 1

PARALLEL COMPUTING:
TYPES OF PROCESSORS:

Class #02: Introduction to Parallel and Distributed

Computing
🔸 Memory Segments:

● Local Variables are made in the stack segment

● Global Variables are made in the data segment

🔹 These are important because:

● The stack segment is used for function calls, temporary data, and local variables.
● The data segment stores static/global variables and is initialized when the program
starts.

🖥️CISC Architecture Diagram Explanation:

📍Components:
 1. Processor:
o CU (Control Unit): Controls instruction execution.
o Register File:
▪ IR: Instruction Register

▪ AX, DX: General-purpose registers

RR2: Another register (could be custom-named)
▪
o Registers temporarily hold data and operands.
2. RAM (Memory):
o Contains:
▪ CS (Code Segment)

▪ Data Segment → Global Variables

Stack Segment → Local Variables
▪
o Code and data are fetched from here.
3. Data Flow:
o Instructions are fetched from memory (CS)
o Operands (data) are fetched from data/stack segments
o Data is moved into registers → operation performed → result stored

🔎 CISC Instruction Format:

● Opcode tells what operation to do (e.g., ADD, MOV)

● Operands can be immediate values, memory addresses, or registers
● CISC allows complex instructions like memory-to-memory operations

Working Example:

You are trying to compute a = b + c

CISC Instructions:
Key Points:

● You can access memory directly in arithmetic operations

● Fewer instructions, but each one may take multiple clock cycles
● Ideal for fewer lines of code, but slower execution per instruction

RISC Architecture Section:

🔹 Explanation:

"At any cost we have to move data in register to perform operation."

🧠 Meaning:

● RISC strictly follows the Load/Store Architecture

● You cannot perform operations directly on memory
● You must first load data into registers, then perform operations.

❌ Not Allowed in RISC:

This would try to add a memory value directly — illegal in RISC.

RISC Way:

If you want to add value from memory:

RISC vs CISC Architecture in Parallel Computing

🔸 1. Basic Definition

2. Working & Parallelism

✅ RISC:

● Uses simple instructions that execute in one clock cycle.

● Encourages instruction-level parallelism (ILP) because instructions are uniform and easily
pipelined.
● Each instruction typically does one task (e.g., load, store, add).

📌 Example: To multiply two numbers and store the result:

Each instruction is simple and can be pipelined for parallel execution.

RISC: One Instruction per Cycle

🔧 How It Works:

● RISC instructions are very simple (e.g., add, load, store).

● Each instruction is designed to complete in exactly one clock cycle.

● Instructions are uniform in size and format, making them easy to decode and pipeline.

📦 Breakdown:

Each instruction does only one thing, so the CPU can:

1. Fetch the instruction

2. Decode it quickly
3. Execute it in one cycle

🔄 This allows pipelining: while instruction 1 is executing, instruction 2 can be decoded, and instruction 3
can be fetched — all happening in parallel in different CPU stages.

Real-Life Analogy
Imagine a factory:
 ● RISC: Each worker does one small job (like screw in a bolt), quickly and in sync on an
assembly line. Tasks can overlap across workers.

Problem: Understanding “Why CISC Is Difficult to Pipeline

(Parallelize)”
In RISC
🔹 Instructions (Each does one thing):

Each instruction is simple, has a fixed format, and can be broken into stages (Fetch → Decode
→ Execute → Memory → Write Back), so they are perfect for pipelining.

🔄 While instruction 1 is executing, instruction 2 is decoding, and instruction 3 is fetching.

📈 Result: Smooth, predictable, efficient use of hardware — easy parallelism

CISC:
● Uses complex instructions that can perform multiple operations.

● Harder to pipeline because instructions vary in length and complexity.

● Parallel execution is more difficult due to instruction dependencies.

Understanding Instruction Execution: Clock Cycles

CISC: Multiple Cycles per Instruction
🔧 How It Works:

● CISC instructions are complex — they can do multiple things at once (e.g., load, add, and store).

● These require micro-operations internally, which are broken down and executed over several
cycles.

📦 Breakdown:

A single instruction like ADD A, B might involve:

1. Fetch instruction
2. Decode (more complex than RISC)
3. Load memory location A
4. Load memory location B
5. Add values
6. Store result back

Each of these steps can take one or more clock cycles.

🧪 Example in CISC:

Looks short, but takes multiple clock cycles internally due to complexity.

Real-Life Analogy
CISC: One worker tries to do the whole job (assemble the whole product), taking longer and holding up
the line.

Problem: Understanding “Why CISC Is Difficult to Pipeline

(Parallelize)”
In CISC
🔹 Same task in one complex instruction:
Sounds simple, but under the hood, the CPU must:

1. Fetch the instruction

2. Decode it (this is tricky: how many operands? what type? memory or register?)
3. Determine memory access for A and B
4. Load values from memory
5. Perform multiplication
6. Store result back to memory C

🔸 Problem:

● Instruction length and format vary → Decoding is slower and less predictable

● Multiple operations inside one instruction → Must be broken into micro-operations (called
microcode)
● CPU can’t pipeline well because:
o It can’t start executing the next instruction until it finishes all steps of the current one
o Dependencies between the stages are too tight
o Variable instruction time = Pipeline stalls (bubbles)

Flynn’s taxonomy:
Parallel computing is a computing where the jobs are broken into discrete parts that can be
executed concurrently. Each part is further broken down to a series of instructions. Instructions
from each part execute simultaneously on different CPUs. Parallel systems deal with the
simultaneous use of multiple computer resources that can include a single computer with
multiple processors, a number of computers connected by a network to form a parallel
processing cluster or a combination of both.

Parallel systems are more difficult to program than computers with a single processor because
the architecture of parallel computers varies accordingly and the processes of multiple CPUs
must be coordinated and synchronized.
The crux of parallel processing are CPUs. Based on the number of instruction and data streams
that can be processed simultaneously, computing systems are classified into four major
categories:

Flynn’s classification –

Single-instruction, single-data (SISD) systems –

An SISD computing system is a uniprocessor machine which is capable of executing a single
instruction, operating on a single data stream. In SISD, machine instructions are processed in a
sequential manner and computers adopting this model are popularly called sequential
computers. Most conventional computers have SISD architecture. All the instructions and data
to be processed have to be stored in primary memory.
The speed of the processing element in the SISD model is limited(dependent) by the rate at
which the computer can transfer information internally. Dominant representative SISD systems
are IBM PC, workstations.

Single-instruction, multiple-data (SIMD) systems –

An SIMD system is a multiprocessor machine capable of executing the same instruction on all
the CPUs but operating on different data streams. Machines based on an SIMD model are well
suited to scientific computing since they involve lots of vector and matrix operations. So that
the information can be passed to all the processing elements (PEs) organized data elements of
vectors can be divided into multiple sets(N-sets for N PE systems) and each PE can process one
data set.

Dominant representative SIMD systems is Cray’s vector processing machine.

Multiple-instruction, single-data (MISD) systems –

An MISD computing system is a multiprocessor machine capable of executing different
instructions on different PEs but all of them operating on the same dataset .
Example Z = sin(x)+cos(x)+tan(x)

The system performs different operations on the same data set. Machines built using the MISD
model are not useful in most of the application, a few machines are built, but none of them are
available commercially.

Multiple-instruction, multiple-data (MIMD)

systems –
An MIMD system is a multiprocessor machine which is capable of executing multiple
instructions on multiple data sets. Each PE in the MIMD model has separate instruction and
data streams; therefore machines built using this model are capable to any kind of application.
Unlike SIMD and MISD machines, PEs in MIMD machines work asynchronously.

MIMD machines are broadly categorized into shared-memory MIMD and distributed-memory
MIMD based on the way PEs are coupled to the main memory.

In the shared memory MIMD model (tightly coupled multiprocessor systems), all the PEs are
connected to a single global memory and they all have access to it. The communication
between PEs in this model takes place through the shared memory, modification of the data
stored in the global memory by one PE is visible to all other PEs. Dominant representative
shared memory MIMD systems are Silicon Graphics machines and Sun/IBM’s SMP (Symmetric
Multi-Processing).

In Distributed memory MIMD machines (loosely coupled multiprocessor systems) all PEs have a
local memory. The communication between PEs in this model takes place through the
interconnection network (the inter process communication channel, or IPC). The network
connecting PEs can be configured to tree, mesh or in accordance with the requirement.

The shared-memory MIMD architecture is easier to program but is less tolerant to failures and
harder to extend with respect to the distributed memory MIMD model. Failures in a shared-
memory MIMD affect the entire system, whereas this is not the case of the distributed model,
in which each of the PEs can be easily isolated. Moreover, shared memory MIMD architectures
are less likely to scale because the addition of more PEs leads to memory contention. This is a
situation that does not happen in the case of distributed memory, in which each PE has its own
memory. As a result of practical outcomes and user’s requirement , distributed memory MIMD
architecture is superior to the other existing models.
🧠 1. Instruction and Data Stream Classifications (Flynn’s Taxonomy):

These are basic models of how instructions and data are handled in computer systems.

✅ SISD (Single Instruction, Single Data)

● Executes one instruction on one data at a time.

● Classic sequential architecture (e.g., traditional computers).

● Example: CISC (Complex Instruction Set Computing) architecture.

✅ SIMD (Single Instruction, Multiple Data)

● Executes one instruction on multiple data in parallel.

● Used in vector processors and array processors.

● Common in GPU operations.

● Good for data-parallel tasks like image processing.

✅ MISD (Multiple Instruction, Single Data)

● Executes multiple instructions on the same data.

● Rarely used in practice, more of a theoretical model.

● Could be used in fault-tolerant systems.

✅ MIMD (Multiple Instruction, Multiple Data)

● Multiple processors execute different instructions on different data independently.

● Most modern multicore processors and distributed systems follow this model.

🔁 2. Multitasking vs. Multithreading:

● Multitasking: Running multiple programs at the same time.

● Multithreading: A single program performing multiple tasks (threads) simultaneously.

● Every program is single-threaded by default.

🧩 3. Diagrams Explanation:
▶️SISD Diagram:

● Flow: CU (Control Unit) → ALU (Arithmetic Logic Unit) → Memory

● It represents the linear data flow of a simple CPU.

▶️SIMD Diagrams:

● Vector Processor: One CU controls multiple processing elements (P).

● Array Processor: A more distributed version, each P can work semi-independently.

💻 4. Key Statements in a Program:

These are types of instructions executed by the processor:

● Control Statements – if, loops (e.g., if, for, while)

● I/O Statements – read/write from input/output

● Arithmetic Statements – e.g., a = b + c

● Register File Statements – moving data between CPU registers

🧠 5. Memory & Data Flow:

● RAM ↔ I/O – Interaction between memory and input/output devices.

● Register File ↔ RAM – Processor loads/stores data between fast-access registers and main
memory.
● ALU ← Register File – Data used in computations is fetched from registers.

🖥️6. MIMD Architecture Deep Dive:

✅ SM (Shared Memory)

● Multiple processors share the same memory.

● Good for multi-threaded applications.

● Data transmission within computer.

✅ DM (Distributed Memory)

● Each processor has its own memory.

● Communication happens via network.

● Used in clusters and grids.

📌 Clusters vs Grids:

● Cluster: Group of dedicated computers tightly connected.

● Grid: Group of non-dedicated systems, possibly geographically distributed.

🧠 7. Important Final Note:

● CPU design is based on SIMD architecture for efficient parallel processing.

1) Multitasking Systems & System API for Multiprogramming

🔹 Multitasking:

● Definition: The ability of an operating system to execute multiple tasks (processes) at the same
time.
● Each task is given a time slice by the CPU scheduler to execute.

● Example: You can play music while browsing the internet.

 Key Component:

● Time-sharing: This is the mechanism that enables multitasking by giving each process a
small time slice or quantum of the CPU, then switching to another process.
● Hardware Considerations: For multitasking to work effectively, the hardware needs to
support fast switching between tasks. This may include things like a multi-core processor
or efficient memory management systems.

 Limitations of Multitasking:

● Multitasking relies heavily on I/O (input/output) operations, so tasks that are CPU-
intensive may not benefit from multitasking in the same way.
● If multiple tasks demand too much CPU time, the system may become slower, especially
if there is insufficient memory or processing power
🔹 Types:
🟩 1. Preemptive Multitasking
✅ Definition:

The OS takes control of the CPU and decides when to pause (preempt) a running task and switch to
another.

Tasks don’t get to decide when to stop — the OS can interrupt any task and switch to another at any
time.

🧠 How it works:

● OS uses a timer to give each task a time slice (e.g., 100ms).

● When the time is up, it pauses the current task and switches to the next.

● Ensures fair usage of the CPU for all tasks.

📱 Real-Life Example:

Imagine you are in a classroom, and the teacher allows each student 1 minute to speak. After 1 minute,
the teacher says “Next!” even if the student isn’t finished. That’s preemptive.

💻 Code Example (Concept in C-like Pseudocode):

c
CopyEdit
while (1) {
run_task_1();
run_task_2();
}

But with preemptive multitasking, the OS automatically switches between these tasks without waiting
for one to finish.

OS handles like this:

● Start task 1 ➡ interrupt after 100ms ➡ switch to task 2 ➡ repeat

🟨 2. Cooperative Multitasking
✅ Definition:

Here, each task must give up control voluntarily — the OS won’t interrupt it. If one task misbehaves or
takes too long, others have to wait.
The responsibility to share the CPU lies with the running tasks.

🧠 How it works:

● A task runs and must call a function like yield() to let others run.

● If it never calls yield(), no other task gets to run = bad!

📱 Real-Life Example:

You're in a group meeting, and you politely let someone else speak when you're done. No one forces
you to stop. That’s cooperative.

💻 Code Example (Concept):

c
CopyEdit
void task1() {
while (1) {
doWork();
yield(); // Giving control to other task
}
}

void task2() {
while (1) {
doWork();
yield(); // Giving control to other task
}
}

Here, each task must call yield() or similar to allow others to run.

 Preemptive = OS interrupts tasks automatically → smoother multitasking.

 Cooperative = Tasks must behave well and yield control → can cause freezes if not careful.

🟣 Multiprogramming = Multiple Programs in Memory

➤ Only one is running at a time, others are waiting.

● It was used in older systems.

● CPU switches when one program is waiting (like waiting for input/output).

● Helps better CPU usage.

📖 Example:
You open MS Word, Paint, and Calculator.
Only one runs at a time. If Word is waiting for something (like you typing), the CPU works on Paint.

🧠 Think of it like:
🎂 Chef cooking 3 dishes, but only 1 stove. When one dish is boiling, chef switches to another dish.

🔵 Multitasking = Multiple Tasks Happening Together

➤ CPU switches tasks very fast, so it feels like all are running at once.

● Modern systems do this.

● Uses time-sharing — each program gets a tiny amount of time.

📖 Example:
You’re typing in Word, listening to music, and downloading a file.
All seem to be working at the same time, thanks to fast switching.

🧠 Think of it like:
🎂 Chef switches between dishes very fast, so it feels like all are being cooked together.

🧠 First, Let’s Understand a Process's Memory Layout

When a program runs, it is loaded into memory. That memory is usually divided into segments:

Segment What It Contains

Code
The actual code (instructions) of the program
Segment

Data
Global and static variables
Segment

Heap Dynamically allocated memory (malloc /

Segment new)

Stack Function call stack (local variables, return

Segment addr)

✅ In Multiprogramming (Multiple Processes)

Each process has its own separate memory.
➡️That means:
 ● ❌ They do NOT share code, data, stack, or heap by default.

● Each process has its own copy of everything.

🔐 Memory isolation:

● Good for security and stability.

● But if they want to communicate, they must use Inter-Process Communication (IPC) like:
o Shared memory (shmget())
o Pipes
o Sockets

2) Multithreading Systems & System APIs for Thread Management

🔹 Multithreading:

● Definition: Multiple threads (smaller units of a process) run concurrently within the same
process.
● Threads share memory and resources, making communication faster.

● Example: In a web server, one thread handles each client.

🔹 Benefits:

● Efficient use of CPU

● Faster context switching compared to processes

● Shared memory space for easier data exchange

Challenges with Multithreading:

● Synchronization Issues: Since threads share memory, access to shared resources must
be synchronized to avoid conflicts (like race conditions or deadlocks).
● Complexity: Managing threads requires more careful planning to avoid bugs like
deadlocks, where two or more threads are waiting for each other indefinitely.

Concurrency vs Parallelism:

● Concurrency is when multiple tasks are making progress at the same time, but not necessarily
simultaneously. In multitasking, this is often achieved by switching between tasks so quickly that
it seems as if they’re running together.
 ● Parallelism involves truly simultaneous execution of tasks, typically on multiple CPU cores or
processors.

🔁 "Making a Clone of the Server" — What It Means

When the document says:

"A clone of the server is made and then clients are assigned to each server..."

it doesn't literally mean copying the whole physical server — instead, it refers to creating a new thread
or process for each client connection.

💡 Translation:

● The main server (called the main thread) keeps listening for incoming client connections.

● As soon as a new client connects, the server creates a new thread (a clone in a programming
sense) to handle that specific client.
● The main server goes back to listening for the next client.

📦 So What Happens Exactly?

Let’s break it into steps:

1. Start the main server: It opens a socket and waits for client connections.
2. Client connects: A user sends a request (like opening a chat).
3. Server spawns a thread: The server creates a new thread (a lightweight “clone”) for that client.
4. Thread handles the client: That thread talks to the client, receives/sends data.
5. Main server stays free: The original server thread is ready to accept the next client.

🔹 System APIs for Thread Management:

Most systems use the POSIX thread (pthreads) library. Important functions:

● pthread_create(): Create a new thread

● pthread_exit(): Terminate a thread

● pthread_join(): Wait for a thread to finish

● pthread_mutex_lock() / unlock(): Handle critical sections

✅ In Multithreading (Multiple Threads in One Process)

All threads belong to the same process.

➡️That means:

Memory Shared by
Notes
Area Threads?

Code
✅ Yes All threads run the same code
Segment

Data
✅ Yes Global/static variables are shared
Segment

Heap Dynamically allocated memory is

✅ Yes
Segment shared

Stack
❌ No Each thread has its own stack
Segment

🧠 Why separate stacks?

Because:

● Each thread can have its own function calls and local variables.

● Keeps thread execution independent.

● 📌 Summary Table
Area of Shared in Shared in
Memory Multithreading Multiprogramming
Code Segment ✅ Yes ❌ No
Data Segment ✅ Yes ❌ No
Heap ✅ Yes ❌ No
Stack ❌ No (one per thread) ❌ No
🧪 Example:
Let’s say you write a C program with:

c
CopyEdit
int globalVar = 10; // in Data Segment

void* myThread(void* arg) {

int localVar = 5; // in Stack
globalVar += 1;
printf("Local: %d, Global: %d\n", localVar, globalVar);
}
 ● globalVar is shared among threads

● localVar is different for every thread

✅ So in simple terms:

● Processes (multiprogramming): Each is like a separate person with their own home and kitchen.

● Threads (multithreading): Like multiple people in the same house, sharing kitchen and living
room, but having their own bedrooms (stack).

3) Multiprocessing Systems & Shared Memory Architecture

🔹 Multiprocessing:

● Definition: A system with two or more CPUs working simultaneously.

● Each processor can execute one process or thread.

● Helps with true parallelism.

🔹 Types

🟢 1. Symmetric Multiprocessing (SMP)

✅ Definition:

All processors are equal. They share the same memory, same I/O, and run any task.

📚 Example in real life:

Imagine a team of chefs 🍳🍳 working in the same kitchen, with the same tools and same recipe book.
Each chef can cook any dish — they are equal and help each other.

🧠 What they share:

● ✅ Code Segment

● ✅ Data Segment (global/static)

● ✅ Heap

● ✅ I/O devices

● ❌ Stack (each thread/core has its own)

💻 Example (concept in code):

c
CopyEdit
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

int sharedCounter = 0; // Shared data segment

void* worker(void* arg) {

for (int i = 0; i < 5; i++) {
sharedCounter++; // All threads access this
printf("CPU %ld incremented counter to %d\n", (long)arg,
sharedCounter);
sleep(1);
}
return NULL;
}

int main() {
pthread_t cpu1, cpu2;

pthread_create(&cpu1, NULL, worker, (void*)1);

pthread_create(&cpu2, NULL, worker, (void*)2);

pthread_join(cpu1, NULL);
pthread_join(cpu2, NULL);
return 0;
}
🔍 Summary:

● Any CPU can do any task.

● All CPUs share memory and I/O.

● Used in modern OS: Windows, Linux, macOS.

🟡 2. Asymmetric Multiprocessing (AMP)

✅ Definition:

Each processor is assigned a specific task.

Usually, one CPU (called the master) controls others (called slaves).

📚 Example in real life:

One head chef 👨‍🍳 gives tasks to helper chefs.

One cooks rice, another chops veggies.
They may not even use the same kitchen section.

🧠 What they share:

 ● May not share memory in the same way.

● Each processor may have its own memory (private stack/data).

● Communication happens through messages or shared memory segments (like mailboxes).

💻 Example (conceptual logic):

c
CopyEdit
// Master assigns tasks
void masterCPU() {
printf("Master assigning task to CPU 2\n");
// Tell CPU 2 to run function
}

// CPU 2 runs specific function only

void cpu2_worker() {
// Only runs task it's told to
printf("CPU 2 doing its assigned job\n");
}

In embedded systems or RTOS (Real-Time OS), you may see this:

● CPU 0 → handles OS

● CPU 1 → handles networking

● CPU 2 → handles sensors

They don't share the same heap or data — they communicate with message passing or shared memory
regions.

✅ Summary Table:
Feature SMP (Symmetric) AMP (Asymmetric)

CPU equality All CPUs are equal One master, others are workers

Task
Any CPU can do any task Specific task assigned to each CPU
distribution

Memory Shared memory May have separate memory

Communicatio
Direct memory access Message passing or shared memory
n

Complexity Easier (uniform) More complex task control

Desktops, servers, Embedded systems, RTOS (e.g.,

Used in
smartphones robots)
Shared Memory Architecture:

● All CPUs/cores share a common memory space.

● Used for fast inter-process communication (IPC).

● Requires synchronization (like semaphores or mutexes) to avoid conflicts.

🔹 APIs for Shared Memory:

● shmget(): Create a shared memory segment.

● shmat(): Attach shared memory to address space.

● shmdt(): Detach shared memory.

● shmctl(): Control operations on shared memory.

Single Tasking:

● Definition: Single-tasking refers to the execution of one task at a time. It is the basic form of
computing where only one process runs on the CPU. Each process must finish before the next
one starts.
● Example: When you're working on a computer, and you're using a word processor, you're
focused only on that task until you decide to switch to another program.

Slide 1: Title Slide

Title: Concurrency Control

Presented by: Dr. Muhammad Saeed
This sets the topic and presenter of the module.

Slide 2: Outlines

This slide lists what the presentation will cover:

● What is Concurrency?

● Why Concurrency is required?

● Levels of Concurrency:
o Computer Hardware
o Operating System
o Software/Algorithms
● How to Achieve Concurrency:
o Multi-Programming
 o Multithreading
o Multiprocessing
● Issues with Concurrency:
o Data Inconsistency / Coherency
● Solutions:
o Mutual Exclusion
o Synchronization
o Deadlock and its Solutions
● Summary

Slide 3: What is Concurrency?

● Oxford Definition: The fact of two or more events or circumstances happening or existing at the
same time.
● Computing Definition: The ability to execute more than one program or task simultaneously.
o Concurrency is essentially about multiple tasks being handled at the same time, which
improves performance and efficiency.

Slide 4: Why Concurrency is Required?

● The real world involves multiple independent actors interacting with each other.

● In computing, this translates into parallel tasks that need coordination.

● Examples:
o Software Engineering: Gantt Charts show overlapping tasks.
o Expression Parsing: Mathematical expressions like ((x + y) * (a - b))^2 have
independent subexpressions that can be computed concurrently.
o Client/Server Computing: Clients and servers operate independently but interact.

Slide 5: Levels of Concurrency

Concurrency exists at multiple levels:

1. Hardware Level: Processors and cores inside computers.

2. Operating System Level: Processes and threads managed by the OS.
3. Software Level: Applications like client/server systems that are designed for concurrent
execution.

Slide 6: Concurrency in Computer Hardware

 ● Based on Flynn’s Taxonomy:
o SISD: Single Instruction, Single Data
o SIMD: Single Instruction, Multiple Data (e.g., GPUs, vector processors)
o MIMD: Multiple Instruction, Multiple Data
▪ Shared Memory: Used in symmetric multiprocessing systems.
▪ Distributed Memory: Found in cluster and grid computing setups.

Slide 7: Concurrency in Operating Systems

● Single-User vs Multi-User: Number of users supported.

● Single-tasking vs Multi-tasking: One vs multiple tasks at a time.

● Multi-tasking vs Multi-threading: Multiple applications vs multiple threads in the same app.

● Multi-threading vs Multi-processing: Threads share memory; processes do not.

● APIs:
o fork() for creating processes.
o pthread_create() for creating threads.

Slide 8: Concurrency in Software/Algorithms

● Types of Applications:
o Client/Server
o Peer-to-Peer
● Types of Algorithms:
o Sequential: Runs one task at a time.
o Parallel: Tasks run simultaneously (e.g., on GPU or with multiprocessing).
o Distributed: Runs on separate machines connected over a network.

Slide 9: Summary

● Concurrency enables multiple tasks to run at the same time.

● It can be achieved at:

o Hardware level using multiple cores or systems.
o OS level with multi-threading or multi-processing.
o Software level using proper design patterns and models.
● Key techniques include:
o Multi-programming
o Multi-threading
 o Multi-processing
● Concurrency introduces issues like data inconsistency, which are addressed through:
o Mutual Exclusion
o Synchronization
o Deadlock Handling

Slide 3: Multitasking vs. Multithreading

● Multitasking: Running multiple processes concurrently.

● Multithreading: Running multiple threads within a single process.

👉 Threads are lighter, faster, and share memory—ideal for parallel tasks in the same app.

• Thread is an independent path of execution

• In a multi-threaded program, each thread has its own PC, register (context),
stack, but it shares the process’s address space
• Think of it as multiple workers (threads) working on different tasks, but all within the same
building (process).
• #include <stdio.h>
• int main(int argc, char *argv[])
• {
• printf("hello world\n");
•
• return 0;

A basic C program with just a main() function — this is single-threaded, with only the main
thread running.

🔹 Slides 6–7: Threads vs. Processes

Similarities:

● Both can run independently.

Differences:

● Threads share address space, processes don’t.

● Switching between threads is faster than between processes.

● Threads use Thread Control Blocks (TCBs) instead of Process Control Blocks (PCBs).
🧵 Single-threaded Program

Imagine your program is a small shop. In a single-threaded setup:

♂️One worker (thread)

🏪 One shop (memory space)

Only one person can work in the shop at a time. That worker:

● Has their own notebook (stack) for keeping notes (function calls, variables)

● Uses the entire shop (memory/address space) freely

No one else is using the space, so there’s no confusion or conflict.

Why This Matters

✅ Advantage:
Threads can communicate quickly by reading/writing to the same memory without asking the
manager (operating system).

❗ Danger:
If two threads try to grab the same tool at the same time, things can go wrong — this is where
race conditions happen.
Slide 9: Why Multithreading?

✅ Why Use Threads?

1. ⚡ Parallelism

● Threads allow multiple parts of a program to run at the same time.

● On multi-core CPUs, this means you can assign one thread per core and get tasks done faster.

Imagine splitting a big job (like sorting a massive list) into smaller tasks and having multiple people
(threads) do each part simultaneously.

2. ⏳ Blocking I/O

● When a program waits for input/output (like reading a file or waiting for user input), it stops
doing other work — this is called blocking.
● If you use threads, only that one thread is blocked, while others can keep working!

Example: While one thread waits for a file to download, another can keep updating the UI.

3. 💸 Cost Efficiency

● You could do the same thing using multiple processes, but:

o Processes require more memory
o Process switching is slower
● Threads share memory, so they’re much faster and lighter.
🧠 Real-World Uses
● Web servers: Handle thousands of users at once, each with their own thread.

● Databases: Perform complex queries, indexing, and caching using multiple threads in parallel.

● 🔹 Slide 10: Thread vs. Process Creation Time

● Creating and managing threads is much faster than doing the same with processes —
useful for high-performance systems like web servers or databases.

Slide 11: Benefits of Threads

● Faster creation and termination

● Faster switching between threads

● Lower memory use (shared memory, files)

● No kernel needed for inter-thread communication

Thread Function
c
Copy code
void *mythread(void* args) {
print(“%s\n”, (char*) args);
return NULL;
}

● This is the function run by each thread.

● args is a pointer to whatever argument you pass when starting the thread (in this case, a string
like "A" or "B").
● It prints the string and returns.

🧠 Think of this as:

Each thread will run mythread() and print its assigned letter.

🧠 Main Function
c
Copy code
int main(int argc, char *argv[]) {
pthread_t p1, p2;
printf("main begin\n");
Pthread_create(&p1, NULL, mythread, "A");
 Pthread_create(&p2, NULL, mythread, "B");
Pthread_join(p1, NULL);
Pthread_join(p2, NULL);
printf("main end\n");
return 0;
}
🧾 What’s happening:

1. pthread_t p1, p2;

o Declares two thread IDs (p1 and p2).
2. printf("main begin\n");
o Print that the program has started.
3. Pthread_create(...)
o Creates two threads:
▪ p1 runs mythread with "A" as input.

▪ p2 runs mythread with "B" as input.

o These use a likely wrapper macro Pthread_create which includes error checking.
4. Pthread_join(p1, NULL); and Pthread_join(p2, NULL);
o Wait for both threads to finish before continuing.
5. printf("main end\n");
o Print that the main program has ended.

🖨️Expected Output (Order May Vary)

css
Copy code
main begin
A
B
main end

OR

css
Copy code
main begin
B
A
main end

Since threads run concurrently, A and B can appear in any order.

CPU Scheduling Output

• Output is dependent on which thread is created and which is

scheduled first on the CPU
PRAM :

🔍 Context:

This is a broadcast algorithm — it means one processor (P1) has a value x, and the goal is to send
(broadcast) x to all other processors (P2, P3, ..., Pn) using EREW PRAM model where:

● Exclusive Read (ER): No two processors can read from the same memory location at the same
time.
● Exclusive Write (EW): No two processors can write to the same memory location at the same
time.

📋 Step-by-Step Breakdown (based on image):

(a) Initial state:

● Only P1 has the value x in its private memory and writes it to L[1] (shared memory location 1).

● L[1] ← y where y = x.
(b) Iteration 1 (i = 0):

● 2^i = 1

● Loop goes from j = 2 to j = 2 (just 1 processor).

● P2 gets x from L[1] and writes it to its private memory y, and stores it in L[2].

(c) Iteration 2 (i = 1):

● 2^i = 2

● Loop from j = 3 to 4

● P3 reads from L[1], P4 reads from L[2]

● Both get x and store it in their private memory and L[j].

(d) Iteration 3 (i = 2):

● 2^i = 4

● Loop from j = 5 to 8

● P5-P8 read from L[1]–L[4] respectively

● This pattern ensures no memory location is accessed by multiple processors at the same time
(hence, EREW is maintained).

🧠 What's the key idea?

It's doing doubling each time — kind of like:

● First P1 → P2

● Then P1, P2 → P3, P4

● Then P1–P4 → P5–P8

... and so on.

At each stage, the number of processors who have x doubles, and each processor uses a different
memory location to ensure no conflicts.

Time Complexity:

● The loop runs from i = 0 to log(p) - 1 → O(log p) time

 ● Each step is done in parallel, so it's fast!

💡 Real-Life Analogy:

Imagine a rumor (value x) spreading in a classroom, but with a rule:

● One person tells one new person at a time (no double whispering allowed).

● Each round doubles how many people know the rumor.

● So it spreads to the whole class very quickly, even with the rule.
▶️Iteration 1 (i = 1):

● 2⁰ + 1 = 2, so j from 2 to 8

● Update: A[j] = A[j] + A[j - 1]

So:

● A[2] ← A[2] + A[1]

 ● A[3] ← A[3] + A[2]

● A[4] ← A[4] + A[3]

● ...

● A[8] ← A[8] + A[7]

These are handled by processors P₂ to P₈ (as shown on right of the diagram).

🟦 First Row in Diagram: You see arrows coming from A[j-1] to A[j].

▶️Iteration 2 (i = 2):

● 2¹ + 1 = 3, so j from 3 to 8

● Update: A[j] = A[j] + A[j - 2]

So:

● A[3] ← A[3] + A[1]

● A[4] ← A[4] + A[2]

● ...

● A[8] ← A[8] + A[6]

🟦 Second Row in Diagram shows these steps.

▶️Iteration 3 (i = 3):

● 2² + 1 = 5, so j from 5 to 8

● Update: A[j] = A[j] + A[j - 4]

So:

● A[5] ← A[5] + A[1]

● A[6] ← A[6] + A[2]

● A[7] ← A[7] + A[3]

● A[8] ← A[8] + A[4]

🟦 Third Row in Diagram shows this.

🧠 What’s the Final Result?

At the end of all iterations:

● A[1] = A[1]

● A[2] = A[1] + A[2]

● A[3] = A[1] + A[2] + A[3]

● ...

● A[8] = A[1] + A[2] + ... + A[8]

Each A[j] now holds the sum of all previous elements, i.e., partial sum

📘 Algorithm: AllSums_EREW
plaintext
CopyEdit
for i = 1 to log n do
🔹 What this means:

We repeat the steps for i = 1 to log(n).

If n = 8, then log2(8) = 3. So we loop i = 1, 2, 3.

👉 Each i controls how far back we look in the array while adding values.

plaintext
CopyEdit
forall Pj, where 2^(i-1) + 1 ≤ j ≤ n do in parallel
🔹 What this means:

For each index j in the array starting from 2^(i-1) + 1 to n,

we assign a processor Pj to do the task.

✅ "in parallel" means all these processors work together at the same time!

j
2^(i-1) +
rang
1
e

2 to
2
8

3 to
3
8
 j
2^(i-1) +
rang
1
e

5 to
35 8

plaintext
CopyEdit
A[j] ← A[j] + A[j - 2^(i-1)]
🔹 What this means:

Each processor adds a value from earlier in the array to A[j].

💡 Example for i = 2:

plaintext
CopyEdit
A[3] = A[3] + A[1]
A[4] = A[4] + A[2]
A[5] = A[5] + A[3]
...

The distance 2^(i-1) is how far back in the array you look.

plaintextsymm
CopyEdit
endfor
endfor
🔹 What this means:

● Finish the loop for all j values in current i step

● Then move to next i

Repeat until i = log(n) is finished.

💡 What is MPI?

MPI stands for Message Passing Interface.

It is a standard/library used for parallel programming, especially on distributed systems (like clusters or
supercomputers).

📦 In Simple Words:
Imagine you have many computers (or many cores in a computer), and you want them to work together
on one big problem.

MPI lets them:

● 📤 Send messages to each other (like "Hey, here's some data!")

● 📥 Receive messages from each other (like "Thanks! Here's my result.")

● ✅ Work in coordination, sharing results, data, or tasks.

✳️1. MPI_Reduce Function

int MPI_Reduce(void* sendbuf, void* recvbuf, int count,

MPI_Datatype datatype, MPI_Op op,

int root, MPI_Comm comm);

🔍 Explanation:

● Used to combine values from all processes into a single result at one root process.

● Typical operations: MPI_SUM, MPI_MAX, MPI_MIN, etc.

🧩 Parameters:

● sendbuf: Data to send (local process).

● recvbuf: Where to store the final result (only at root).

● count: Number of elements to reduce.

● datatype: Type of elements (MPI_INT, MPI_FLOAT, etc.).

● op: Operation to perform (sum, max, etc.).

● root: Process rank that receives the result.

● comm: Communicator (usually MPI_COMM_WORLD).

✅ Example:

If 4 processes each have:

makefile

Copy code

P0: 1

P1: 2

P2: 3
P3: 4

Using MPI_SUM with root = 0 → recvbuf on P0 will be 10.

✳️2. Root Definition

int root → root where data has to be received

● Only the process with rank = root will store the final reduced result.

● Other processes won’t have it in recvbuf.

✳️3. Difference: Reduce vs AllReduce

Operation Root Needed? Who Gets Result?

Reduce Yes Only root

AllReduc No All processes

e

✳️4. MPI_Scan (Prefix Reduce)

🔍 Explanation:

● Performs a cumulative operation up to each process.

● Useful in pipeline or staged processing.

✅ Example:
Processes have values: [1, 2, 3, 4]

Then:

● P0: 1

● P1: 1+2 = 3

● P2: 1+2+3 = 6

● P3: 1+2+3+4 = 10

Each process gets the sum of all values before and including itself.

🟨 1. What is MPI_Scatter?
🔸 Concept:

Imagine you are a teacher and you have 4 question papers (A, B, C, D).
You want to give one paper to each of your 4 students (P0, P1, P2, P3).

That’s what MPI_Scatter does!

✅ In MPI:

● One process (usually P0) has a big array or data.

● This process sends out chunks of the data to all processes including itself.

📦 So:

● P0 sends A to P0

● P0 sends B to P1
 ● P0 sends C to P2

● P0 sends D to P3

Each process now has one piece of the original data.

🟩 2. What is MPI_Gather?
🔸 Concept:

Now suppose each student (P0 to P3) has solved their question paper and want to give it back to the
teacher (P0).

That’s what MPI_Gather does!

✅ In MPI:

● All processes send their result back to one process (usually P0).

● P0 collects all the pieces and reconstructs the full data.

📦 So:

● P0 sends A to P0

● P1 sends B to P0

● P2 sends C to P0

● P3 sends D to P0

Now P0 again has all 4: A B C D

✅ Now let’s go step-by-step through your diagram:

🔴 PART 1: Scatter + Gather (Top block)

Before Scatter:
P0: A B C D
P1:
P2:
P3:
📤 Step 1: SCATTER (left to middle)

● P0 gives 1 item to each process

P0: A
P1: B
P2: C
P3: D

Each process now holds its assigned chunk.

📥 Step 2: GATHER (middle to right)

● All processes send their piece back to P0.

After Gather (at P0):

P0: A B C D

So now P0 has the original array reconstructed.

🔵 PART 2: AllGather (Middle block)

Before:
P0: A
P1: B
P2: C
P3: D
📤 MPI_Allgather: Every process sends its value to all others

After:
P0: A B C D
P1: A B C D
P2: A B C D
P3: A B C D

Everyone has the full data!

🟣 PART 3: AllToAll (Bottom block)

Each process has a row of 4 items to share:

Before:
P0: A0 A1 A2 A3
P1: B0 B1 B2 B3
P2: C0 C1 C2 C3
P3: D0 D1 D2 D3

🔄 Now, each process sends one column to every other process.

After MPI_Alltoall:

Each process now has:

P0: A0 B0 C0 D0 ← first column from each row

P1: A1 B1 C1 D1 ← second column from each row
P2: A2 B2 C2 D2 ← third column from each row
P3: A3 B3 C3 D3 ← fourth column from each row

So it's a matrix transpose-like communication: rows turn into columns.

🧠 Final Analogy Recap:

MPI
Real-life Analogy
Function

Scatter Teacher giving one sheet to each student

Gather Students giving sheets back to teacher

Allgather Everyone shares their sheet with everyone

Everyone gives each part to everyone else (total

Alltoall
exchange)

🌐 In MPI (Message Passing Interface):

📥 MPI_Recv — Blocking Receive

This waits for the message to arrive completely before the program can move to the next line.

● It blocks the execution of the receiving process until:

o A message is received from the sender.
o The message is copied into the receiver's buffer.

✅ Think of it like this:

You're waiting at the door for a delivery. You can't do anything else until the delivery arrives.

🔁 Understanding Synchronization in MPI_Send and MPI_Recv

Let's revisit this simple diagram:

perl

Copy code

P0 P1

| send |

| ------> |

| | recv

✅ Case: When P1 is already waiting (blocking MPI_Recv)

● P1 has called MPI_Recv and is waiting to receive a message.

● P0 then calls MPI_Send — the message is transferred, and both processes synchronize at that
point.

💡 Why is this synchronized?

● Both processes are "ready" to interact — P1 is waiting for data, and P0 is sending it.

● Both calls are blocking (in standard MPI), so they will pause until the message transfer
completes.

● Neither process moves forward until the communication is done.

❌ Case: When P1 is not ready (no MPI_Recv yet)

Now imagine:

objectivec

Copy code

P0 calls MPI_Send
BUT

P1 has not yet called MPI_Recv

🔥 What happens?

● Depending on MPI's buffering mode, one of two things can happen:

1. Small messages (may be buffered):

○ MPI temporarily stores the message.

○ P0 might not block and continues execution.

○ Synchronization does not occur yet — P1 will later call MPI_Recv.

2. Large messages (no space to buffer):

○ MPI_Send blocks — it waits for P1 to call MPI_Recv.

○ P0 cannot proceed → forced synchronization.

💡 This is not guaranteed synchronization because:

● MPI behavior depends on the size of the message and internal buffering.
pa

✳️2. Creating Groups

-np 10 means launching 10 processes in MPI.

Cluster View:
Copy code

0 1 2

3 4 5

6 7 8

→ These 10 processes will be used for grouping or communication.

✳️3. Using Set Operations (Groups)

You can form new groups of processes using:

● Inclusion: Specify which process ranks to include.

● Exclusion: Specify which ranks to exclude.

✅ Example:

● Want to create a group with processes 0, 2, 4:

Copy code

MPI_Group_incl(old_group, 3, [0,2,4], &new_group);

✅ Page 4: Group Creation, Exclusion,

Communicators
✳️1. Group Creation with MPI_Group_incl()

Copy code

MPI_Group_incl(existing_group, size, ranks[], &new_group);

🔍 Explanation:

● existing_group: Source group (usually from MPI_COMM_WORLD).

● size: How many processes to include.

● ranks[]: Array of ranks to include.

● new_group: Output handle for new group.

✳️2. By Exclusion

● Like inclusion, but specify which process ranks not to include.

● Useful when the group to exclude is smaller.

✳️3. Using Ranges

“We can tell if either group is even or odd.”

● You can create groups based on even or odd process IDs using range operations or loops.

✅ Example:

Copy code

// Create group of even ranks: 0, 2, 4, ...

It looks like you meant "MPI_Cart_create is used for?" — I’ve got you!

👉 MPI_Cart_create is used in MPI (Message Passing Interface) to create a Cartesian

topology for processes.

✅ In simple terms:

MPI_Cart_create helps arrange processes in a grid-like structure (like 2D or 3D) so you can
work with neighbors easily — super useful for problems in scientific computing like matrix
operations, fluid dynamics, simulations, etc.

💡 Why use it?

● Makes it easier to find neighboring processes.

● Reduces errors when writing complex communication patterns.
● Optimizes communication paths for structured data.

💻 Basic Example:

MPI_Comm cart_comm;
int dims[2] = {4, 4}; // 4x4 grid
int periods[2] = {0, 0}; // No wrap-around
int reorder = 1;

MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cart_comm);

This creates a 4x4 2D Cartesian grid of processes.

If you want, I can show you a full example or break down each parameter! Want me to?

🌍 MPI_COMM_WORLD is the default communicator in MPI.

When you start an MPI program, all processes are automatically part of MPI_COMM_WORLD. It’s
like the "global group chat" for your entire MPI program.
💡 What does it do?

● Allows all processes to communicate with each other.

● Used in basic MPI functions like MPI_Send, MPI_Recv, MPI_Bcast, etc.
● It’s your starting point before creating more specific communicators (like with
MPI_Cart_create or MPI_Comm_split).

📦 Example:

MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

● rank gives you the ID of the current process.

● size tells you the total number of processes.

💡 What are Communicators in MPI?

A communicator in MPI is like a communication group or a channel that defines:

1. Which processes can talk to each other

2. How they can communicate (context)
3. 💡 Why is MPI_Cart_rank used?
4. When you create a Cartesian topology with MPI_Cart_create, each process is placed in
a grid — and each position has coordinates like (x, y) or (i, j).
5. But MPI doesn't use coordinates directly for communication — it still uses ranks
(process IDs).
6. So MPI_Cart_rank helps you:
7. 👉 Convert grid coordinates → process rank
So you can send and receive messages using the correct process ID.
8. 💡 Why is MPI_Cart_coords used?
9. After you create a Cartesian topology with MPI_Cart_create, MPI assigns ranks to
processes — but sometimes you want to know:
10. 👉 "Where am I in the grid?"
11. That’s exactly what MPI_Cart_coords answers.
12. It converts a process’s rank → coordinates in the grid.

📌 Topic: Virtual Topologies in MPI

Virtual topologies = Logical arrangement of tasks (processes) inside a communicator.

This lets you structure your processes like a grid (Cartesian) rather than just treating them as a flat list of
ranks.

💡 Cartesian Topology (n-dimensional grid)

👉 MPI_Cart_create(oldcomm, ndims, sizeofdims, periods, mapping, newcom);

● Creates a Cartesian grid of processes.

● oldcomm: existing communicator (usually MPI_COMM_WORLD).

● ndims: number of dimensions (e.g., 2 for a 2D grid).

● sizeofdims: array of grid sizes in each dimension ([rows, columns]).

● periods: array that says whether the grid wraps around in each dimension (1 = yes, 0 =
no).
● mapping: allows MPI to reorder ranks (1 = allow, 0 = don't allow).

● newcom: the new communicator with the grid structure.

👉 MPI_Cart_rank(communicator, coordinates, &rank);

● Converts coordinates → process rank.

● If you know the coordinates, this gives you the corresponding rank.

👉 MPI_Cart_coords(communicator, rank, ndims, &coords);

● Converts rank → coordinates.

● If you know the rank, this tells you the process's grid location.

💡 Example Explained Line by Line

2 x 3 Grid

A grid of 2 rows and 3 columns:

[0,0] [0,1] [0,2]

[1,0] [1,1] [1,2]
Total processes = 6.

MPI_Comm gridcomm;

Declares a new communicator to hold the Cartesian grid.

int sizeofdims[2] ➡ [0]=2 & [1]=3

Sets the grid size:

● Dimension 0 (rows) = 2.

● Dimension 1 (columns) = 3.

int periods[2] ➡ [0]=0 & [1]=0

No wrap-around in either dimension:

● 0 means: no periodic boundary — the grid has clear edges.

int mapping = 0

Tells MPI:

● Do not reorder process ranks.

● Keep ranks the same as assigned in MPI_COMM_WORLD if possible.

MPI_Cart_create(MPI_WORLD_COMM, 2, sizeofdims, periods, mapping, &gridcomm);

Creates the Cartesian communicator:

● Based on MPI_WORLD_COMM.

● 2 dimensions (2D grid).

● Grid size as defined (2x3).

● No wrap-around.

● No rank reordering.

● Stores the result in gridcomm.

✅ Summary:

● You’re creating a 2x3 grid.

● Each process will have a rank and coordinates.

● MPI_Cart_rank and MPI_Cart_coords let you map between rank and grid position.

● Communication becomes much easier for structured problems like matrices, image filters, and
simulations.

If you want, I can show you a full runnable code example using this exact setup!
Want me to write one for you?

4o
You said:
`periods`: array that says whether the grid **wraps around** in each dimension (`1 = yes`, `0 =
no`).

📌 What is periods in MPI_Cart_create?

The periods array controls whether your grid is:

● Connected at the edges like a circle (wrap-around)

or
● Disconnected at the edges like a flat grid (no wrap-around).

🧠 Simple Meaning:

● periods[dimension] = 0 → No wrap-around.
Edges have no neighbors beyond the border.
● periods[dimension] = 1 → Wrap-around is enabled.
The grid "loops around" like a torus — the last process is connected back to the first one.

💡 Example:
Let’s say you have a 2 x 3 Grid like this:

Row: 2
Column: 3
🔸 If periods[0] = 0 and periods[1] = 0

No wrap-around in both rows and columns.

[0,0] — [0,1] — [0,2]

| | |
[1,0] — [1,1] — [1,2]

● Edge cells have no neighbor outside the boundary.

● If you're at [0,2] — no neighbor to the right.

● If you're at [1,0] — no neighbor to the left.

🔸 If periods[0] = 1 and periods[1] = 1

Wrap-around enabled for both rows and columns.

Now the grid behaves like this:

css
CopyEdit
[0,0] ⇄ [0,1] ⇄ [0,2]
↑ ↓ ↑ ↓ ↑ ↓
[1,0] ⇄ [1,1] ⇄ [1,2]

● If you move right from [0,2], you end up at [0,0].

● If you move down from [1,0], you end up at [0,0].

It’s like turning your flat grid into a doughnut shape (torus).

💡 Why is this useful?

● For some scientific simulations (e.g., physics, weather, fluid flow) the world is modeled as a
continuous loop.
● Periodic boundaries avoid “edge effects.”

✅ Summary Table:
 Value of Meaning Behavior
periods[]
Edge cells have no extra
0 No wrap-around (flat grid)
neighbor.

Wrap-around enabled
1 Edges connect back around.
(circular/torus)

So when you write:

int periods[2] = {0, 0};

You’re saying:
❌ No wrap-around in rows.
❌ No wrap-around in columns.

📌 Graph Topology Idea

Unlike Cartesian grids (like a chessboard),

Graph topology lets you arrange processes freely like a network or map — no fixed rows or columns!

The drawing on the left shows:

6 nodes: [0,1,2,3,4,5]
Connections: As shown by the lines.

💡 Code Breakdown
MPI_Comm graphcomm;

Declares a communicator to store the graph structure.

int nodes = 6;

Defines the total number of processes (or "nodes") = 6.

int index[6] = {2, 5, 8, 12, 14, 16};

The index array tells how many neighbors each node has.

👉 It’s a cumulative count.

No Cumulative Edge
Meaning
de Index

Node 0 has neighbors stored in edges[0] to

0 2
edges[1].

1 5 Node 1 has neighbors in edges[2] to edges[4].

2 8 Node 2 has neighbors in edges[5] to edges[7].

3 12 Node 3 has neighbors in edges[8] to edges[11].

4 14 Node 4 has neighbors in edges[12] to edges[13].

5 16 Node 5 has neighbors in edges[14] to edges[15].

int edges[16] = {1,2, 0,3,4, 0,3,5, 1,2,4,5, 1,3, 2,3};

This holds the actual neighbors for all nodes, one after another.

Example:

● Node 0's neighbors: edges[0] to edges[1] → {1, 2}

● Node 1's neighbors: edges[2] to edges[4] → {0, 3, 4}

● Node 2's neighbors: edges[5] to edges[7] → {0, 3, 5}

● Node 3's neighbors: edges[8] to edges[11] → {1, 2, 4, 5}

● Node 4's neighbors: edges[12] to edges[13] → {1, 3}

● Node 5's neighbors: edges[14] to edges[15] → {2, 3}

🧠 What is index[] doing?

Imagine you have:

 ● 6 houses (nodes) numbered from 0 to 5.
● Each house is connected to other houses by roads (edges).

But to tell MPI "which house is connected to which," you need to give two pieces of
information:

💡 1️⃣ edges[]

This list stores the neighbors (connections) for all the houses — one after another.

But... how does MPI know:

● which neighbor belongs to which house?

That’s where index[] helps.

💡 2️⃣ index[]

This array tells MPI where to stop for each house's neighbor list inside edges[].

It’s like marking the end of the list for each house!

🔍 Example:
diff
CopyEdit
index[6] = {2, 5, 8, 12, 14, 16}

It tells MPI:

Node Look in edges[]

to Meaning
(House) from
0 edges[0]
edges[1 Node 0 is connected to edges[0] and
] edges[1] neighbors.
edges[4
1 edges[2]
] Node 1 is connected to edges[2] to edges[4].
edges[7
2 edges[5]
] Node 2 is connected to edges[5] to edges[7].
3 edges[8] edges[1 Node 3 is connected to edges[8] to
 Node Look in edges[]
to Meaning
(House) from
1] edges[11].
4 edges[12]
edges[1 Node 4 is connected to edges[12] to
3] edges[13].
5 edges[14]
edges[1 Node 5 is connected to edges[14] to
5] edges[15].

✅ So in easy words:

● The index[] array tells where each house's (node's) neighbor list ends in the edges[]
list.
● MPI uses it to understand which neighbors belong to which node.

int mapping = 0;

Tells MPI:

● 0 = Do not reorder ranks.

Ranks stay the same unless reordering is necessary.

MPI_Graph_create(MPI_WORLD_COMM, nodes, index, edges, mapping, &graphcomm);

This creates the graph topology:

● Takes MPI_WORLD_COMM as the base.

● nodes = number of processes.

● index and edges = describe the connection graph.

● mapping controls whether MPI can reorder processes.

● graphcomm will store the new communicator.

📘 OpenMP Detailed Notes

✅ Definition of OpenMP
OpenMP (Open Multi-Processing) is:

● A parallel programming model designed for shared-memory systems.

● It allows developers to write parallel code using a simple and flexible syntax.

● OpenMP is based on:

○ Compiler directives (e.g., #pragma),

○ Runtime library routines,

○ Environment variables to control parallel behavior.

✅ Why Use OpenMP?

● Ease of Implementation:

○ Makes parallelizing loops and tasks straightforward.

● Portability:
 ○ Code written with OpenMP is platform-independent with minimal modifications
needed.

● Efficiency:

○ Helps in efficient use of CPU cores on modern processors by running code in parallel.

✅ Basic Components of OpenMP

1. Compiler Directives:

○ Specl
ial instructions for the compiler to parallelize code.

○ Syntax: #pragma is used for OpenMP directives.

■ Example: #pragma omp parallel

2. Runtime Functions:

○ Control and query the behavior of parallel execution.

○ Common functions:

■ omp_get_thread_num() – gets the ID of the current thread.

■ omp_set_num_threads(n) – sets the number of threads.

3. Environment Variables:

○ Control OpenMP settings at runtime.

○ Example:

■ OMP_NUM_THREADS – sets the number of threads used by the program.

💡 What Are Environment Variables in OpenMP?

In OpenMP, environment variables are special settings outside the code that help you control how the
program runs at runtime (when the program is running). You can set them without changing the code.

🔧 What Does OMP_NUM_THREADS Do?

OMP_NUM_THREADS is an environment variable used to tell OpenMP how many threads to use when
running your parallel code.

● Think of threads like workers. If you say, "Use 4 workers", OpenMP will create 4 threads.

● You set this before running your program.

📌 Example: Using OMP_NUM_THREADS

If you run your program from a terminal or command line:

bash

Copy code

export OMP_NUM_THREADS=4 # This tells OpenMP: "Use 4 threads"

./my_program # Now run your compiled OpenMP program

Inside your C code, you just use:

Copy code

#pragma omp parallel

printf("Hello from thread %d\n", omp_get_thread_num());

You don’t need to set the thread count in your code if you're using OMP_NUM_THREADS from outside.

🤔 Why Use Environment Variables?

● Convenient: You don’t need to change and recompile your code to change thread count.
 ● Flexible: You can easily test performance using 2, 4, 8 threads, etc.

● Clean: Keeps your code simple while allowing control from outside.

✅ Parallel Regions in OpenMP

● A parallel region is a block of code that will be executed by multiple threads simultaneously.

● Declared using: #pragma omp parallel

🔷 Example:

Copy code

#include <stdio.h>

#include <omp.h>

int main() {

#pragma omp parallel

printf("Hello, World! from thread %d\n",

omp_get_thread_num());

return 0;

}
 ● Output: The statement inside will be printed by multiple threads.

● omp_get_thread_num() helps identify which thread is executing the statement.

✅ Controlling the Number of Threads

● You can control how many threads OpenMP uses in two main ways:

1. Environment Variable:

■ Set the variable OMP_NUM_THREADS before running the program.

2. Runtime Function:

■ Use omp_set_num_threads(n) in the code.

🔷 Example:

Copy code

#include <stdio.h>

#include <omp.h>

int main() {

omp_set_num_threads(4); // Set number of threads to 4

#pragma omp parallel

printf("Thread %d is working\n", omp_get_thread_num());

}
 return 0;

● This sets the number of threads to 4 at runtime and prints a message from each.

📘 Detailed Notes: Parallelizing Loops with

OpenMP

✅ Definition: What is Loop Parallelization?

Loop parallelization means breaking up loop iterations so that multiple threads can run them at the
same time. OpenMP allows this using the #pragma omp parallel for directive.

✅ For Loop Parallelization in OpenMP

● The directive #pragma omp parallel for allows parallel execution of for loops.

● OpenMP automatically divides loop iterations among available threads.

🔷 Example:
c

CopyEdit

#pragma omp parallel for

for (int i = 0; i < N; i++) {

// Loop body

}
🔷 Full Example Using 4 Threads:
c

CopyEdit

omp_set_num_threads(4); // Use 4 threads

#pragma omp parallel for

for (int i = 0; i < N; i++) {

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

● Each thread will handle a portion of the loop.

● Efficient for independent iterations (no data sharing between iterations).

✅ Reduction in OpenMP
🔍 Definition:
A reduction operation allows each thread to maintain its own private copy of a variable, and combine
them at the end using an operation (like +, *, etc.).

🔷 Example:
c

CopyEdit

int sum = 0;

#pragma omp parallel for reduction(+:sum)

for (int i = 0; i < N; i++) {

 sum += arr[i];

● Each thread computes its own partial sum.

● All partial sums are added together at the end.

🔷 Full Example:
c

CopyEdit

int N = 100000;

int arr[N], sum = 0;

for (int i = 0; i < N; i++):

arr[i] = 1;

omp_set_num_threads(4);

#pragma omp parallel for reduction(+:sum)

for (int i = 0; i < N; i++) {

sum += arr[i];

printf("Sum: %d\n", sum);

⚠️Loop-Carried Dependencies
❗ Definition:
A loop-carried dependency occurs when one iteration depends on the result of a previous one.

🔷 Example With Dependency:

c

CopyEdit

int N = 10;

int arr[N];

arr[0] = 1;

#pragma omp parallel for

for (int i = 1; i < N; i++) {

arr[i] = arr[i - 1] + 1; // Depends on previous iteration

🛑 This will not work correctly in parallel because:

● Threads will try to access arr[i - 1] before it's computed.

✅ Synchronization for Dependent Loops

🔒 How to Handle Dependencies?

● Use **critical** or **atomic** OpenMP directives.

● These ensure only one thread modifies shared data at a time.

🔷 Fixed Version Using critical:

c
CopyEdit

#pragma omp parallel for

for (int i = 1; i < N; i++) {

#pragma omp critical

arr[i] = arr[i - 1] + 1;

● The #pragma omp critical makes the block thread-safe.

● Only one thread at a time enters the critical section.

OpenMP works primarily on MIMD (Multiple Instruction, Multiple Data) architectures,

and can also run on SISD systems (as single-threaded code).

🔒 1. #pragma omp critical

● Ensures only one thread at a time can execute the entire block of code.

● Can be used for any kind of operation, not just arithmetic.

✅ Example:

CopyEdit

#pragma omp critical

arr[i] = arr[i - 1] + 1;

● Useful for complex operations, multiple statements, or function calls.

 ● Slower than atomic due to larger locking overhead.

⚡ 2. #pragma omp atomic

● Only works for simple, single memory operations, usually arithmetic or

assignment.

● More efficient than critical because it’s faster and lighter.

✅ Example:

CopyEdit

#pragma omp atomic

sum += arr[i];

● Can't wrap multiple statements.

● Ideal for simple increment/decrement/add/assign operations.

🧵 OpenMP Loop Scheduling – Detailed Notes

✅ Definition: Loop Scheduling in OpenMP

Loop scheduling in OpenMP refers to how iterations of a loop are distributed among
available threads. The goal is to ensure efficient parallel execution by balancing the
workload across threads.

OpenMP provides multiple scheduling strategies to control this distribution:

● Static Scheduling

● Dynamic Scheduling
 ● Guided Scheduling (mentioned but not elaborated on in the slides)

📌 1. Static Scheduling (Default)

🔹 Definition:

Static scheduling assigns a fixed block of loop iterations to each thread before
execution begins.

🔹 How it works:

● Iterations are divided equally and consecutively among threads.

● Once a thread gets its assigned iterations, it executes them without further
coordination.

🔹 Example:

If:

● Threads = 4

● Iterations (N) = 12

Then the assignment would be:

● Thread 0 → Iterations 0-2

● Thread 1 → Iterations 3-5

● Thread 2 → Iterations 6-8

● Thread 3 → Iterations 9-11

🔹 Code Snippet:

c
Copy code

#pragma omp parallel for

for (int i = 0; i < N; i++) {

sum += arr[i];

📌 2. Dynamic Scheduling
🔹 Definition:

Dynamic scheduling assigns a chunk of iterations to a thread. When a thread finishes its
current chunk, it requests another. This continues until all iterations are processed.

🔹 How it works:

● Useful when iteration workloads vary.

● Threads that finish early can take on more work → better load balancing.

🔹 Code Snippet:

Copy code

#pragma omp parallel for schedule(dynamic, chunk_size)

for (int i = 0; i < N; i++) {

sum += arr[i];

}
🔹 Real-life Example (from slides):

For:

● Threads = 4

● N = 25

● Chunk size = 3

Thread Iterations Chunk Breakdown

Assigned

Thread 0, 1, 2, 12, 13, 14, Chunk 1 (0–2), Chunk 5 (12–14), Chunk 9

0 24 (24)

Thread 3, 4, 5, 15, 16, 17 Chunk 2 (3–5), Chunk 6 (15–17)

1

Thread 6, 7, 8, 18, 19, 20 Chunk 3 (6–8), Chunk 7 (18–20)

2

Thread 9, 10, 11, 21, 22, Chunk 4 (9–11), Chunk 8 (21–23)

3 23

Threads pick up new chunks dynamically after finishing the previous one.

🆚 Static vs Dynamic Scheduling – Summary Table

Feature Static Scheduling Dynamic Scheduling

Assignment Before loop starts During execution (on demand)

Time
 Flexibility Low (fixed) High (adaptive to runtime behavior)

Best For Uniform iteration Uneven or unpredictable workloads

workloads

Overhead Lower (less coordination Higher (threads must coordinate for

needed) new chunks)

Load Balancing May be poor if tasks vary in Better load balancing

time

📘 OpenMP Concepts: Private and Shared Variables, Protection

Techniques, and Summation Example

🔹 1. Private and Shared Variables in OpenMP

🔸 Shared Variables

● A shared variable is accessible by all threads in the team.

● The initial value is set before the parallel region begins.

● Threads can modify shared variables during execution.

● Race conditions can occur if multiple threads try to modify the variable simultaneously.

Example:

Copy code

int shared_var = 0;

#pragma omp parallel shared(shared_var)

{

shared_var += 1; // All threads attempt to update this variable

📝 Line-by-Line Explanation:

🔹 int shared_var = 0;

● This declares an integer variable named shared_var and initializes it to 0.

● This variable is shared, meaning all threads in the parallel region will access and modify the
same memory location.

🔹 #pragma omp parallel shared(shared_var)

● This directive tells the compiler to start a parallel region using OpenMP.

● All threads spawned by OpenMP will run the code inside the block.

● The variable shared_var is explicitly declared as shared, so each thread will refer to the same
copy of it.

🔹 shared_var += 1;

● Each thread executes this line and increments the shared_var by 1.

● However, since shared_var is shared and multiple threads are modifying it simultaneously,
this causes a race condition.

🔸 Private Variables

● A private variable is unique to each thread.

● Each thread gets its own copy of the private variable.

● Value is undefined at the beginning unless explicitly initialized.

● Modifications to private variables do not affect other threads.

Example:
c

Copy code

int shared_var = 0;

int private_var = 0;

#pragma omp parallel private(private_var) shared(shared_var)

int thread_id = omp_get_thread_num();

private_var = thread_id; // Each thread gets its own copy

shared_var += 1;

printf("Thread %d: private_var = %d, shared_var = %d\n",

thread_id, private_var, shared_var);

🔍 Explanation:

🔸 int shared_var = 0;

● This is a shared variable, initialized to 0.

● All threads will access and modify this same variable.

🔸 int private_var = 0;

● This is declared before the parallel region, but will be treated as private in the parallel block.

🔸 #pragma omp parallel private(private_var) shared(shared_var)

● This starts a parallel region.

● private_var is private: each thread gets its own copy, which is not initialized unless done
explicitly.
 ● shared_var is shared: all threads access and modify the same memory location.

🔸 Inside the parallel block:

➤ int thread_id = omp_get_thread_num();

● Gets the ID of the current thread.

● For example, if there are 4 threads, IDs will be 0, 1, 2, 3.

➤ private_var = thread_id;

● Sets each thread’s private copy of private_var to its own thread ID.

➤ shared_var += 1;

● Each thread increments the shared variable by 1.

● Since there is no protection, this causes a race condition — the final result may not be equal to
the number of threads.

➤ printf(...)

● Prints the current thread's ID, its private variable value (which is the same as the thread ID), and
the current shared variable value.

🔹 What does "not initialized" mean in this context?

When OpenMP gives each thread its own private copy of a variable (like private_var), that copy is
created without a value unless you explicitly assign one inside the parallel block. Even though
private_var was initialized to 0 before the parallel block, the private clause causes each thread to
create a new copy, and that new copy is not given the value 0. Its value is undefined — it could be
anything (junk from memory).

🔹 2. Protection Techniques in OpenMP

To avoid race conditions when using shared variables, OpenMP provides the following mechanisms:
🔸 Critical Section

● Ensures that only one thread executes a code block at a time.

● Protects shared variables from concurrent access.

Syntax:

Copy code

#pragma omp critical

// Code that only one thread can execute at a time

Example:

Copy code

int shared_var = 0;

#pragma omp parallel shared(shared_var)

#pragma omp critical

shared_var += 1; // Safe modification

printf("Thread %d: shared_var = %d\n", omp_get_thread_num(),

shared_var);
}

🔸 Atomic Operation

● Allows operations like addition/subtraction to be performed atomically.

● Avoids race conditions without locking the entire block.

Syntax:

Copy code

#pragma omp atomic

shared_var += 1;

Example:

Copy code

int shared_var = 0;

#pragma omp parallel shared(shared_var)

#pragma omp atomic

shared_var += 1;

printf("Thread %d: shared_var = %d\n", omp_get_thread_num(),

shared_var);

}
🔹 3. Example: Sum of First N Numbers using OpenMP
Problem:

Compute the sum of numbers from 1 to N using parallel processing.

Code Example with Atomic Operation:

Copy code

int N = 100; // Sum first 100 numbers

int sum = 0;

#pragma omp parallel for shared(sum)

for (int i = 1; i <= N; i++) {

#pragma omp atomic

sum += i;

printf("Final sum = %d\n", sum);

Code Example with Critical Section:

Copy code

#pragma omp parallel for shared(sum)

for (int i = 1; i <= N; i++) {

#pragma omp critical

 {

sum += i;

🆚 private(var) vs reduction(+:var)
Feature private(var) reduction(+:var)

Purpose Creates a separate copy of a Performs a thread-local computation, then

variable for each thread combines results into a final shared value at the
end

Initial Value Undefined unless explicitly Automatically initialized to 0 (for +, or identity

initialized value for other operators)

Combining You must manually combine OpenMP automatically combines values from
Values results if needed each thread using the given operator (+, *, max,
etc.)

Shared Final You need to manually store a Final result is automatically stored in the original
Result final result in a shared variable variable after parallel region

Typical Use Use for temporary variables or Use for tasks like summing, multiplying,
Case intermediate calculations min/max, etc. across threads

📘 Notes on Cache Coherency in Multi-Processor

Systems (with OpenMP)

🔹 What is Cache Coherency?

✅ Definition:
Cache coherency refers to the consistency of data stored in local caches of multiple processors (cores)
that share the same main memory. It ensures that all processors have a consistent view of memory.

⚠️Cache Coherency Problem:

● Each processor core may have its own local cache.

● If multiple threads are running on different cores and access the same memory location,
inconsistency may occur:

○ If one thread updates a value in its local cache, others may still see the old value from
their cache.

○ This leads to data inconsistency and incorrect behavior.

🔧 Solution: Cache Coherence Protocols

Modern systems use cache coherence protocols to maintain consistency. One such protocol is:

● MESI Protocol:

○ Modified

○ Exclusive

○ Shared

○ Invalid
These states define how a memory block is shared or updated between caches.

OpenMP does not directly manage cache coherency. Instead, it relies on the system’s
hardware and memory consistency model.

🔁 Flush Operations in OpenMP

✅ Definition:

flush is a directive in OpenMP that forces memory updates to be visible to all threads by
synchronizing the thread’s view of memory with main memory.
🔍 Purpose:
● It ensures that shared variables are correctly updated and visible across all threads.

● Some OpenMP implementations may automatically handle flushing, but #pragma omp
flush gives explicit control.

🔄 Behavior of flush Directive

📌 Key Points:
● Ensures memory consistency across threads and caches.

● Helps manage cache coherency at the thread level when updating shared variables.

● When a thread executes flush(var), it:

○ Makes the most recent value of var visible to other threads.

○ Forces it to read/write to memory rather than just working in cache.

🧪 Code Example Explanation

c

CopyEdit

int shared_var = 0;

#pragma omp parallel shared(shared_var)

int local = shared_var; // Thread reads shared_var

local += 1; // Simulate some local computation

 #pragma omp flush(shared_var) // Ensure memory is synced before
writing

shared_var = local; // Write back to shared_var

printf("Thread %d: shared_var = %d\n", omp_get_thread_num(),

shared_var);

🚫 The Example You Referred To:

c

CopyEdit

int local = shared_var;

local += 1;

#pragma omp flush(shared_var)

shared_var = local;

❓Problem with flushing before write:

If you flush before writing, it only guarantees that your reads are up-to-date — it doesn’t guarantee the
write that follows will be visible to other threads.

So yes — if you want the write to be seen by others, you should flush after writing.

🔁 Summary:
Purpose Where to Place flush(var)

To read the latest value Before reading

To make your write visible After writing

 To ensure full sync Before and/or after critical ops

🔎 Step-by-Step:

1. Each thread reads shared_var into a local variable.

2. It modifies the local value.

3. #pragma omp flush(shared_var) ensures:

○ The memory system syncs this variable.

○ Any future access by other threads will see the updated value.

4. Threads write back their results and print them.

🔧 Example: Cache Coherency Problem Without Flush

c

CopyEdit

#include <stdio.h>

#include <omp.h>

int shared_var = 0;

int main() {

#pragma omp parallel num_threads(2) shared(shared_var)

int thread_id = omp_get_thread_num();

if (thread_id == 0) {
 shared_var = 10; // Thread 0 updates shared_var

// Not flushing here — thread 1 might not see this change

if (thread_id == 1) {

// No flush — might still see old value (0)

printf("Thread 1 sees shared_var = %d\n", shared_var);

return 0;

❗ Problem:

● Thread 0 updates shared_var to 10.

● Thread 1 might still read 0, because the cache hasn't been synchronized — classic cache
coherency issue.

✅ Solution: Use #pragma omp flush(shared_var)

c

CopyEdit

#include <stdio.h>

#include <omp.h>
int shared_var = 0;

int main() {

#pragma omp parallel num_threads(2) shared(shared_var)

int thread_id = omp_get_thread_num();

if (thread_id == 0) {

shared_var = 10;

#pragma omp flush(shared_var) // Make change visible to

all threads

if (thread_id == 1) {

#pragma omp flush(shared_var) // Ensure it sees the

updated value

printf("Thread 1 sees shared_var = %d\n", shared_var);

return 0;

✅ Output:
java
CopyEdit

Thread 1 sees shared_var = 10

Now both threads see consistent data, thanks to the flush directive.

Basic GPU Architecture

● Multi-core chip: A GPU consists of multiple cores. These cores are essentially smaller processing
units within the chip that can perform tasks concurrently. Unlike CPUs, which have fewer cores
optimized for general tasks, GPUs are designed with hundreds or thousands of cores, making
them ideal for parallel processing tasks, like rendering graphics.

● SIMD (Single Instruction, Multiple Data): This refers to the ability of a GPU core to perform the
same operation on multiple pieces of data at once. In simpler terms, SIMD allows the GPU to
apply the same instruction (e.g., adding a number) to many data points simultaneously. This is
why GPUs are so efficient for tasks like image rendering, where the same operation needs to be
applied to many pixels.

● Multi-threaded execution: A single GPU core can run multiple threads at the same time,
enhancing its performance by allowing multiple calculations to happen concurrently.

● Memory (DDR5 DRAM): The GPU uses a high-speed memory called DDR5 DRAM to store the
data it needs for rendering. This memory is much faster than regular system memory (RAM),
providing the necessary bandwidth for fast data retrieval.

How to Explain a System (Step 1: Describe the Entities)

● Step 1: When explaining a system, start by identifying the things (entities) the system
manipulates. In simpler terms, think about the nouns in the system. For example, in a graphics
system, these could be vertices, pixels, or fragments.

Real-time Graphics Primitives (Entities)

● Vertices: These are points in space (3D coordinates). A set of these vertices forms shapes (like
triangles), and the GPU uses these to render 3D objects.

● Primitives: A primitive is a basic graphical shape, like triangles, points, or lines, created using
vertices. These are the building blocks of all 3D shapes in graphics rendering.
 ● Fragments: Once the 3D shapes (primitives) are processed, they are broken down into smaller
pieces, called fragments. Each fragment corresponds to a pixel in the final image.

● Pixels: The final output of the graphics pipeline. Once fragments are processed, they become
pixels in the final image displayed on your screen.

How to Explain a System (Step 2: Describe Operations)

● Step 2: After identifying the entities (things), the next step is to explain the operations (or verbs)
that the system performs on these entities. For example, you may explain how the system
processes vertices to form primitives or how fragments are processed to create pixels.

Rendering a Picture: Step-by-Step

Rendering is the process of turning 3D data into a 2D image. Here's the breakdown of each step:

1. Step 1: Vertex Generation

○ Input: A list of vertices in 3D space. These are points like v0, v1, v2, etc. that define the
shape of 3D objects.

○ These vertices are organized into triangles (each set of three vertices forms a triangle).

2. Step 2: Project the Vertices onto the Screen

○ Given a camera's position, the system computes where the 3D vertices should appear
on the 2D screen.

○ This step transforms 3D points into 2D points (projecting them to fit the screen view).

3. Step 3: Group Vertices into Primitives

○ The system groups the projected vertices into primitives (e.g., triangles).

○ Each primitive will later become a section of the final image.

4. Step 4: Fragment Generation (Rasterization)

○ The system generates fragments for each pixel that overlaps a primitive. These
fragments will later be used to calculate the color of pixels.

5. Step 5: Fragment Processing

 ○ Each fragment is processed to determine its color. This depends on factors like lighting,
material properties, and shading.

6. Step 6: Pixel Operations

○ The final fragments are compared, and the closest fragment to the camera is kept. This
determines which fragments will contribute to the final image, creating the visual
output on the screen.

Fragment Processing Computations

● Fragment processing calculates how light interacts with materials. This simulates how real-
world materials reflect light, making objects look more realistic.

● Example materials: Different objects like shiny balls, matte surfaces, or glass materials reflect
light differently, and fragment processing adjusts the appearance based on this.

Early Graphics Programming (OpenGL API)

● OpenGL API: A programming interface that allows developers to control graphics hardware. It
provides methods to manipulate graphics objects and parameters such as lights and materials.

○ glLight: This function allows developers to set light parameters like the color, position,
and direction of the light sources in the scene.

○ glMaterial: This function allows developers to set material properties for objects, such
as color and shininess.

Real-time Graphics Pipeline

● The graphics pipeline abstracts the entire process of rendering a 3D object into a series of
operations. It moves through several stages:

○ Vertex generation → Vertex processing → Primitive generation → Fragment

generation → Fragment processing → Pixel operations.

This pipeline enables real-time rendering of 3D objects and scenes.

Graphics Shading Languages
1. Purpose of Shading Languages:

○ Shading languages allow developers to programmatically control materials and lighting

within the graphics pipeline. This is crucial for adding diversity in materials (like shiny or
matte surfaces) and lighting conditions (like shadows or light sources).

2. Shaders:

○ Shaders are mini-programs written by the programmer that define how certain stages in
the pipeline behave. Shaders run at specific stages, such as vertex processing or
fragment processing, and are crucial for customizing how graphics are rendered.

○ The pipeline maps these shader functions onto all elements of the input stream (like
vertices or fragments).

GPU as a Data-Parallel Processor

1. GPU’s Speed for Parallel Computation:

○ GPUs are highly effective at processing large collections of data (such as vertices,
fragments, and pixels) simultaneously, using data-parallel programming. This means
that the same operation can be performed on multiple data elements at once, making
GPUs excellent for graphics rendering tasks.

2. Data-Parallelism:

○ This was initially used for graphics, but researchers began to see that data-parallelism
could be leveraged for more general computational tasks. This led to the concept of
GPGPU (General-Purpose Computing on GPUs), which started using GPUs for scientific
computations.

GPGPU (General-Purpose Computing on GPUs)

1. What is GPGPU?

○ GPGPU refers to using the GPU for general-purpose computation, beyond just rendering
graphics. GPUs were found to be efficient for tasks like simulation and matrix
operations, which were traditionally handled by CPUs.

2. Applications of GPGPU:
 ○ Examples of early GPGPU uses include simulation of coupled maps (a mathematical
model) and sparse matrix solvers (used in solving systems of equations).

○ Ray tracing for realistic lighting effects is another example, which was first explored
using programmable graphics hardware.

Brook Stream Programming Language

1. What is Brook?

○ Brook is a stream programming language developed by Stanford for data-parallel

processing on GPUs. It abstracts GPU hardware and allows developers to write programs
in a high-level language that the GPU can execute.

2. Stream Programming:

○ Brook allows computations to be written as kernels that operate on streams of data.

This is ideal for tasks that require processing large sets of data (like textures, vertices, or
pixels) in parallel.

CUDA Programming Language:

● CUDA (Compute Unified Device Architecture) is a C-like language developed by NVIDIA for
programming GPUs (Graphics Processing Units). It allows programmers to write programs that
run on GPUs for tasks such as parallel processing and computation.

● CUDA abstracts GPU capabilities to match their performance characteristics while maintaining a
low level of abstraction (close to hardware).

● Note: OpenCL is similar to CUDA but supports GPUs and CPUs from multiple vendors, while
CUDA is specific to NVIDIA GPUs. OpenCL has similar functionality but CUDA is more widely
documented and easier to use in the NVIDIA ecosystem.

CUDA Execution Model:

● In CUDA, the code is separated into host code (which runs on the CPU) and device code (which
runs on the GPU).

● The GPU runs many threads concurrently, where each thread performs a small part of the
computation. These threads are organized into blocks and grids, allowing easy management of
the computation tasks.
CUDA Memory Model:

● CUDA uses different memory spaces for host (CPU) and device (GPU), which are managed using
memcpy for transferring data between these spaces.

● The GPU device has three main memory types visible to the CUDA kernel:

○ Global Memory: Accessible by all threads in all blocks.

○ Shared Memory: Accessible by all threads in a block.

○ Private Memory: Local to each thread.

CUDA Synchronization Constructs:

● __syncthreads() is used to synchronize all threads in a block. It ensures that all threads
have completed a certain task before proceeding.

● Atomic operations allow one thread to update a variable in global memory or shared memory
safely, ensuring no race conditions occur.

● Host/Device Synchronization ensures that the host (CPU) and device (GPU) work together
without causing conflicts in memory access or execution timing.

1D Convolution in CUDA:

● Convolution is a fundamental operation in image processing and machine learning.

● In CUDA, you can implement convolution by breaking it down into smaller tasks that are
processed in parallel by many threads. The example shows how a kernel is defined to process
each output element using threads. Each thread works on a part of the input and writes to the
output.

CUDA Synchronization and Optimization:

● In versions of CUDA for convolution, threads are used to load data into shared memory (faster
than global memory) for efficient computation. Synchronization ensures all threads in a block
load their data before processing it.

Let’s break down Version 1 and Version 2 of the 1D convolution in CUDA with simple examples.
Version 1: One Thread per Output Element
Example:

Let’s say we have an input array of size 6 and we want to apply a convolution using a kernel of size 3
(meaning we need to sum each element and its two neighboring elements).

Input: [3, 4, 2, 6, 8, 5]
Kernel: [1, 2, 3]

The result after convolution will be calculated for each element using the formula:
output[i]=input[i−1]+input[i]+input[i+1]\text{output}[i] = \text{input}[i-1] + \text{input}[i] + \text{input}
[i+1]output[i]=input[i−1]+input[i]+input[i+1]

Steps in Version 1:

1. Divide the work: Each thread will handle one output element (i.e., one element of the
output[] array).

○ Each thread gets a unique index to process (like thread 0 for the first output, thread 1
for the second output, etc.).

2. Compute the output: Each thread will take the element it is responsible for and apply the
convolution with its neighbors.

○ Thread 0 will compute: output[0] = input[0] + input[1] + input[2]

= 3 + 4 + 2 = 9

○ Thread 1 will compute: output[1] = input[1] + input[2] + input[3]

= 4 + 2 + 6 = 12

○ Thread 2 will compute: output[2] = input[2] + input[3] + input[4]

= 2 + 6 + 8 = 16

○ And so on.

3. Store results: Each thread writes its result directly into global memory.

Code Example (Version 1):

cpp

Copy

// CUDA Kernel for Version 1

__global__ void convolution(int* input, float* output) {

 int index = threadIdx.x; // Each thread handles one output
element

float result = 0.0;

for (int i = -1; i <= 1; i++) { // Convolution window

result += input[index + i];

output[index] = result / 3.0; // Store the result in global

memory

Host Code:

cpp

Copy

int N = 6;

cudaMalloc(&devInput, sizeof(int) * N);

cudaMalloc(&devOutput, sizeof(float) * N);

convolution<<<1, N>>>(devInput, devOutput);

Version 2: Staging Input Data in Shared Memory

Example:

We’ll use the same input array and kernel as before.

Input: [3, 4, 2, 6, 8, 5]
Kernel: [1, 2, 3]

Steps in Version 2:

1. Use shared memory: Instead of each thread directly accessing global memory, we first load the
necessary input data into shared memory. This is a faster type of memory that all threads in a
 block can access.

○ Thread 0 will load: input[0], input[1], input[2] into shared memory.

○ Thread 1 will load: input[1], input[2], input[3] into shared memory, and so
on.

2. Synchronization: After loading the data into shared memory, all threads wait for each other
using a barrier (__syncthreads()) to make sure all data is loaded before any computation
begins.

3. Compute the output: Each thread will now perform the convolution, but instead of accessing
global memory, it will access the shared memory to get its neighbors.

○ Thread 0 will compute: output[0] = shared[0] + shared[1] +

shared[2] = 3 + 4 + 2 = 9

○ Thread 1 will compute: output[1] = shared[1] + shared[2] +

shared[3] = 4 + 2 + 6 = 12

○ And so on.

4. Store results: Finally, the result is stored back into global memory.

Code Example (Version 2):

cpp

Copy

// CUDA Kernel for Version 2

__global__ void convolution(int* input, float* output) {

__shared__ int support[THREADS_PER_BLK + 2]; // Shared memory for

input data

int index = threadIdx.x;

support[threadIdx.x] = input[index];

if (threadIdx.x < 2) {
 support[THREADS_PER_BLK + threadIdx.x] = input[index +
THREADS_PER_BLK];

__syncthreads(); // Synchronize threads before computation

float result = 0.0;

for (int i = -1; i <= 1; i++) { // Convolution window

result += support[index + i];

output[index] = result / 3.0; // Store the result in global

memory

Host Code:

cpp

Copy

int N = 6;

cudaMalloc(&devInput, sizeof(int) * N);

cudaMalloc(&devOutput, sizeof(float) * N);

convolution<<<1, N>>>(devInput, devOutput);

Key Differences:
 ● Version 1: Each thread directly accesses global memory for its data.

● Version 2: Threads first load data into shared memory (which is faster), then use it for the
convolution. Threads synchronize to ensure all data is loaded before computation starts.

CUDA Abstractions:
● Execution: Thread Hierarchy:

○ CUDA allows you to run many threads at once, which are grouped into blocks. This setup
lets you break down tasks into smaller pieces for more efficient parallel execution.

● Distributed Address Space:

○ The memory is divided between different address spaces. CUDA provides functions
(memcpy) to move data between the host (CPU) and the device (GPU). You can work
with memory at three levels: per thread, per block (shared), and per program (global).

● Barrier Synchronization:

○ Synchronization ensures that threads within a block coordinate their actions. This is
done using a barrier, which ensures that all threads in the block complete their task
before moving on to the next.

● Atomic Operations:

○ These are operations that ensure data consistency when multiple threads try to modify
the same variable. It ensures that the operation completes without interference from
other threads.

CUDA Semantics:
● Thread Definitions and Memory:

○ Each CUDA thread is a unit of execution. It has its own local memory, but it can also
share memory with other threads within the same block.

● Kernel Launch:

○ CUDA kernels (functions that run on the GPU) are launched with a specific configuration.
For example, blockDim.x and threadIdx.x define how the threads are organized
within blocks.
 ● Host vs. Device Code:

○ The "host" code runs on the CPU, while the "device" (CUDA) code runs on the GPU.
CUDA separates the code that runs on the CPU and GPU.

CUDA Compilation:
● CUDA Compilation Steps:

○ The kernel (CUDA function) is compiled into machine code that can run on the GPU.
During this, the kernel text and resource requirements are defined. Each thread requires
a specific amount of memory.

● Kernel Launch:

○ When launching a kernel, the number of blocks and threads per block is defined. For
example, launch<<<blocks, threads>>> is how you tell CUDA to run the kernel
with a certain number of threads.

CUDA Thread-Block Assignment:

● Thread Blocks in GPU Architecture:

○ A thread block is a collection of threads that can cooperate and share data. These blocks
are scheduled by the GPU scheduler. Each block is assigned to a GPU core, and the
blocks can run in parallel.

Running the CUDA Kernel:

● Steps to Run a Kernel:

○ Step 1: The host sends the command to the GPU to run a kernel. The GPU scheduler
starts the process.

○ Step 2: The scheduler maps thread blocks to cores on the GPU. Each block gets allocated
execution contexts and shared memory.

○ Step 3: The scheduler continues mapping remaining blocks across the cores available.

○ Step 4: Once a block completes, the next block is scheduled on the next available core.

○ Step 5: Once all blocks are completed, the results are written back to the global
memory.
NVIDIA GTX 980 (2014) Architecture:
● GPU Cores:

○ The GTX 980 has 16 cores (called SMM cores), each capable of executing multiple CUDA
threads. The cores manage memory (shared and global) and process threads in parallel.

● Warp:

○ A warp is a set of 32 threads that execute the same instruction at the same time. A warp
is managed by the core to ensure efficient execution.

CUDA Memory Model and Management:

● Memory Hierarchy:

○ The GPU memory is split into different types: global memory, shared memory, and local
memory. CUDA uses shared memory within a block, which is faster and allows threads
within a block to collaborate.

Advanced CUDA Topics:

● Warp Execution and SIMD:

○ CUDA threads are grouped into warps. Warps execute in a single instruction stream, and
this parallel execution helps improve performance.

● Persistent Threads:

○ In some advanced cases, persistent threads are used to keep threads running
continuously, making use of multiple cores to handle tasks dynamically.

Kernel Launch in CUDA:

● A kernel is just a function that runs on the GPU (Graphics Processing Unit). Think of it as a task
or a job that we want to perform using the GPU.

● When you want to run a kernel, you have to launch it. Launching a kernel means starting the
task or job on the GPU.

How Threads Are Organized:

To run tasks efficiently on the GPU, CUDA divides the work into smaller pieces called threads.
 ● blockDim.x: This refers to the number of threads in a block. A block is a group of threads that
work together and share resources like memory. The x means that you can organize threads
along the x-axis (or one dimension).

● threadIdx.x: This tells you the index of a thread within its block. Every thread in a block gets its
own ID (index), and this ID helps the thread know what part of the work it is responsible for.

Example in Simple Terms:

Imagine you have a big task, like adding numbers together. Instead of doing it yourself, you divide the
task into 10 smaller jobs (let’s say 10 threads), and you group those 10 threads into a team (a block).
Each thread is responsible for adding a certain pair of numbers.

● blockDim.x = 10: This means there are 10 threads in the block.

● threadIdx.x = 0, 1, 2, ...: Each thread gets a unique ID (starting from 0 to 9), so

each one knows which part of the task to handle.

Now, you launch the kernel to tell the GPU to start working on this task. CUDA takes care of distributing
these 10 threads across the available GPU cores. The threads work together within the block and
complete the task.

In summary:

● Kernel Launch is how you start a task on the GPU.

● blockDim.x and threadIdx.x control how many threads are there and how they are arranged to
share the workload.

What is a Warp?
In simple terms, a warp is a group of 32 threads that are treated as a unit and execute the same
instruction at the same time. Imagine you have 32 people working on the same task together at the
same moment. Instead of having each person do their task separately, they all work together in sync to
complete that task.

How Does a Warp Work?

● Threads: These are small units of work, like individual workers.

● Warp: A group of 32 threads working together at the same time on the same task. This is like
having 32 workers in one team, each doing a specific part of a job simultaneously.

● Core: The GPU's core (like a brain of a team) manages the warp. It makes sure that all 32 threads
work together properly to complete the job.
What are Persistent Threads?
● Normal Threads: In typical programs, threads are created to perform a specific task, and once
the task is completed, the thread stops and waits for a new task.

● Persistent Threads: These threads, on the other hand, keep running continuously, even after
finishing their current task. They are always "alive" and ready to take on new tasks whenever
they are assigned one.

How Do Persistent Threads Work?

Think of persistent threads as workers in a factory who never leave their stations. Once they finish a
task, they don't take a break. Instead, they wait for the next task to come their way and immediately
start working again.

CPU (Central Processing Unit):

● Role: The CPU is the "brain" of the computer. It performs all the basic calculations and controls
other components of the system. When you run software, the CPU processes the commands.

Front Side Bus (FSB):

● Role: This is the main communication channel between the CPU and the rest of the system. It
helps to transfer data between the CPU and other parts of the computer, like the memory and
graphics card.

North Bridge:
● Role: The North Bridge connects the CPU to the memory (RAM) and also to the video card. It
handles high-speed communication. It is often referred to as the “memory controller hub”
because it manages the data that is sent between the memory and the CPU.

Memory (RAM):
● Role: This is the temporary storage where data that is currently being used by the CPU is kept.
The more memory you have, the more programs you can run at once.

PCI Bus (Peripheral Component Interconnect Bus):

● Role: The PCI bus is used for communication between the CPU and other devices connected to
the system, like video cards, sound cards, and network cards. It's a pathway that helps transfer
 data between the CPU and these devices.

South Bridge:
● Role: The South Bridge is responsible for managing the input and output devices. It controls
communication with the LAN (network), USB devices, hard drives, and other peripherals. It's
called "South" because it connects to the "North Bridge" via the PCI bus.

LAN (Local Area Network):

● Role: This component allows your computer to connect to a network, like the internet. It’s the
network card that sends and receives data packets over a network.

UART (Universal Asynchronous Receiver/Transmitter):

● Role: This is a serial communication protocol. It allows the CPU to communicate with peripherals
like a keyboard, mouse, or external devices via a serial port.

VGA (Video Graphics Array):

● Role: This is the part responsible for the video output of the system. It processes the graphics
and sends them to the display. The VGA controller takes care of converting the graphical data
into a signal that can be displayed on a screen.

VGA Display:
● Role: This is the monitor or screen where the computer displays the graphical output. It shows
what you see as images, text, and videos.

Framebuffer Memory:
● Role: This is the memory used by the video card to store the current image or video frame that
is being displayed. It holds the data that represents what is shown on the screen at any given
moment.

Key Components of the Diagram:

1. Intel CPU (Diagram part a):

○ PCI-Express Link (x16): This is the connection that links the GPU to the North Bridge. It
is the primary interface between the GPU and the rest of the computer system. The
 "x16" denotes the speed of the link, which is capable of handling large amounts of data.

○ GPU: The Graphics Processing Unit is responsible for rendering graphics and performing
parallel computations. It has its own memory (GPU Memory) to store data and
instructions used for processing.

○ North Bridge: The North Bridge connects the CPU to high-speed devices like memory
(DDR2) and GPU. It helps manage data traffic between the CPU and the rest of the
system.

○ South Bridge: The South Bridge connects lower-speed peripherals like hard drives, USB
ports, and input/output devices. It also links to the North Bridge.

○ Front Side Bus: It connects the CPU to the North Bridge and transfers data between
them.

2. AMD CPU (Diagram part b):

○ CPU core: The central processor of the AMD CPU. It handles all processing tasks in the
system.

○ Internal Bus: This connects the CPU core to other components like the North Bridge and
is used for internal data communication within the CPU.

○ PCI-Express Link (x16): Just like in the Intel configuration, the GPU is connected to the
North Bridge using this link.

○ Chipset:
● The Chipset helps control data flow between the North Bridge and the GPU.

● It also manages other tasks like I/O operations (input/output).

○ HyperTransport: A high-speed communication link used by AMD systems for

communication between the North Bridge and other components like the GPU.

3. GPU Memory: Both configurations feature GPU Memory, where the GPU stores its data and
instructions for rendering or parallel computations.

4. Display: The output of the GPU is sent to the display (monitor), where the processed graphics
are shown.
Explanation of Code Components:

1. #include <stdio.h>:

○ This line includes the Standard Input Output (stdio) library, which allows the program to
use functions like printf for printing output.

2. __global__ void helloFromGPU(void):

○ This is a CUDA kernel function declaration.

○ __global__ tells the compiler that this function will run on the GPU.

○ void helloFromGPU(void) defines the function named helloFromGPU, which

does not take any parameters and does not return a value.

○ Inside this function, the printf function is used to print "Hello World from GPU!".

3. printf("Hello World from GPU!\n");:

○ This line prints the text "Hello World from GPU!" followed by a newline (\n) to the
console.

○ The printf inside the helloFromGPU kernel will run on the GPU, not the CPU.

4. int main(void):

○ This is the main function of the program. This is where the program starts running on
the CPU.
 ○ The main function includes a printf to print "Hello World from CPU!" and calls the
CUDA kernel to print "Hello World from GPU!" using the GPU.

5. printf("Hello World from CPU!\n");:

○ This line prints "Hello World from CPU!" to the console. This is done by the CPU part of
the program before the GPU is invoked.

6. helloFromGPU<<<1, 10>>>();:

○ This line launches the CUDA kernel helloFromGPU on the GPU.

○ <<<1, 10>>> is the execution configuration for the kernel:

■ 1 block of threads is created.

■ 10 threads are created within that block.

○ Each of the 10 threads will run the helloFromGPU kernel and print "Hello World from
GPU!" to the console.

7. cudaDeviceReset();:

○ This function call is used to reset the GPU device and clean up after the kernel
execution.

○ It's good practice to call this function at the end of a CUDA program.

Output in the Console:

● "Hello World from CPU!" will be printed by the CPU.

● "Hello World from GPU!" will be printed 10 times by the GPU, as 10 threads are launched to
execute the kernel.

Standard C Functions:
1. malloc:

○ Allocates memory dynamically in the host (CPU) memory.

○ Syntax: void* malloc(size_t size);

2. memcpy:
 ○ Copies data from one memory location to another.

○ Syntax: void* memcpy(void* dest, const void* src, size_t n);

3. memset:

○ Sets a block of memory to a specific value, useful for initialization.

○ Syntax: void* memset(void* ptr, int value, size_t num);

4. free:

○ Deallocates memory previously allocated by malloc, freeing up resources.

○ Syntax: void free(void* ptr);

Corresponding CUDA C Functions:

1. cudaMalloc:

○ Allocates memory in the GPU (device) memory.

○ Syntax: cudaError_t cudaMalloc(void** devPtr, size_t size);

2. cudaMemcpy:

○ Copies data between host (CPU) memory and device (GPU) memory.

○ Syntax: cudaError_t cudaMemcpy(void* dst, const void* src,

size_t count, cudaMemcpyKind kind);

3. cudaMemset:

○ Sets memory on the GPU (device) to a specific value.

○ Syntax: cudaError_t cudaMemset(void* devPtr, int value, size_t

count);

4. cudaFree:

○ Deallocates memory previously allocated by cudaMalloc on the GPU.

○ Syntax: cudaError_t cudaFree(void* devPtr);

Breakdown of the Diagram: Data Transfer Between CPU and GPU
This diagram illustrates how data is transferred between the CPU (Host) and the GPU (Device) in CUDA
programming.

Key Components:
1. Host (CPU):

○ The CPU (or host) is the main processor that handles all major computations and control
in your system.

○ The Host side uses the CUDA functions to allocate and transfer memory:

■ cudaMalloc: Allocates memory on the GPU.

■ cudaMemcpy: Copies data between the CPU and GPU.

■ cudaMemset: Initializes memory on the GPU.

■ cudaFree: Frees memory allocated on the GPU.

2. Device (GPU):
 ○ The GPU (device) performs parallel processing tasks, handling computations faster than
the CPU.

○ CUDA Memory is used on the GPU, divided into two categories:

■ Shared Memory: Memory shared within the same thread block. It’s fast, but
limited in size.

■ Global Memory: Larger memory, accessible by all threads in the grid, but slower
to access than shared memory.

3. Grid:

○ A grid is a collection of thread blocks. In CUDA, work is divided into blocks and threads.

■ Block (0,0) is an individual block in the grid.

■ Each block consists of multiple threads that perform parallel tasks.

■ For example, the diagram shows Thread (0,0), Thread (1,0), and Thread
(2,0) within a block.

4. Memory Transfer:

○ cudaMemcpy is the function used to transfer data between Host and GPU. It allows for
data to be copied from the Host’s System Memory to the Global Memory of the GPU or
vice versa.

○ The shared memory within the blocks is used for quick, cooperative computation
among threads in the same block.

Workflow:
1. The Host (CPU) uses cudaMalloc to allocate memory on the GPU.

2. The Host sends data to the GPU using cudaMemcpy, moving it from the Host’s System Memory
to the GPU’s Global Memory.

3. The GPU uses shared memory and global memory to execute tasks in parallel using threads
inside blocks.

4. After computation, the Host can retrieve the results from the GPU’s Global Memory back to the
Host’s System Memory via cudaMemcpy.
Breakdown of the Code for Data Transfer Between CPU and GPU
This example demonstrates the process of transferring data between the CPU (Host) and GPU (Device)
in CUDA. Let's walk through the code and explain each part concisely:

Step-by-Step Explanation
Declaring Pointers:

cpp
Copy
float *a_h, *b_h; // host data

float *a_d, *b_d; // device data

1.
○ a_h and b_h: These pointers hold data on the CPU (Host) side.

○ a_d and b_d: These pointers hold data on the GPU (Device) side.

Allocating Memory for Host and Device:

cpp
Copy
nBytes = N * sizeof(float);

a_h = (float *)malloc(nBytes);

b_h = (float *)malloc(nBytes);

cudaMalloc((void **) &a_d, nBytes);

cudaMalloc((void **) &b_d, nBytes);

2.
○ nBytes: This calculates the amount of memory required to store N floating-point
numbers (sizeof(float) gives the size of one float in bytes).

○ a_h and b_h are allocated memory on the Host using the standard malloc function.

○ a_d and b_d are allocated memory on the GPU using cudaMalloc, which is the CUDA-
specific function for allocating memory on the GPU.

Populating Host Data:

cpp
Copy
for (i = 0; i < N; i++) a_h[i] = 100.f + i;

3.
○ This loop initializes the host data a_h with values starting from 100 and increments by
1 for each element.

Transferring Data from Host to Device:

cpp
Copy
cudaMemcpy(a_d, a_h, nBytes, cudaMemcpyHostToDevice);

cudaMemcpy(b_d, a_d, nBytes, cudaMemcpyDeviceToDevice);

4.
○ cudaMemcpy(a_d, a_h, nBytes, cudaMemcpyHostToDevice): This function copies data
from the Host (a_h) to the Device (a_d).

○ cudaMemcpy(b_d, a_d, nBytes, cudaMemcpyDeviceToDevice): This function copies

data from one device memory (a_d) to another (b_d).
Transferring Data from Device to Host:

cpp
Copy
cudaMemcpy(b_h, b_d, nBytes, cudaMemcpyDeviceToHost);

5.
○ cudaMemcpy(b_h, b_d, nBytes, cudaMemcpyDeviceToHost): This function copies data
from the Device (b_d) to the Host (b_h).

Verification:

cpp
Copy
for (i = 0; i < N; i++) assert(a_h[i] == b_h[i]);

6.
○ This loop checks that the data transferred between the Host and Device is correct. The
assert function ensures that each element in a_h is equal to the corresponding element
in b_h. If any value doesn't match, the program will stop (as the condition fails).

Cleaning Up:

cpp
Copy
free(a_h); free(b_h);

cudaFree(a_d); cudaFree(b_d);

7.
○ free(a_h), free(b_h): Frees the memory allocated for Host data (a_h and b_h).

○ cudaFree(a_d), cudaFree(b_d): Frees the memory allocated for Device data (a_d and
b_d).
Explanation of CUDA Threads (SIMT)
1. Threads: Individual units of execution on the GPU, each working on a small part of the problem.

2. Thread Blocks: Groups of threads that execute together on the same GPU core. They can
synchronize and share data via shared memory.

3. Grid: A collection of thread blocks, representing the entire parallel task to be executed on the
GPU.

4. Shared Memory: Memory shared by all threads in a block for fast data exchange.

5. Synchronization: Ensures threads in a block coordinate correctly when accessing shared

memory and performing tasks.

Workflow:

● The Host (CPU) launches the kernel.

● The Grid consists of multiple Thread Blocks.

● Each Thread Block has threads that work together, sharing data via Shared Memory and
synchronizing their execution.

Function Type Qualifiers:

1. __global__:

○ Execution: This function is executed on the device (GPU).

○ Callable: It can be called from the host (CPU) and, for devices with compute capability 3
or higher, it can also be called from the device.

○ Notes: It must have a void return type.

2. __device__:

○ Execution: This function is executed on the device (GPU).

○ Callable: It can only be called from the device, not from the host.

○ Notes: There are no specific restrictions mentioned here for __device__.

3. __host__:
 ○ Execution: This function is executed on the host (CPU).

○ Callable: It can only be called from the host.

○ Notes: This qualifier can be omitted in CUDA programming.

CUDA Kernels Restrictions:

● Access to device memory only: CUDA kernel functions can only access device memory, not host
memory.

● Must have void return type: A CUDA kernel function cannot return any value, so its return
type must always be void.

● No support for a variable number of arguments: CUDA kernel functions do not support
functions that take a dynamic or variable number of arguments.

● No support for static variables: Static variables, which persist between function calls, are not
allowed inside CUDA kernel functions.

● No support for function pointers: You cannot pass function pointers as arguments to a CUDA
kernel.

● Exhibit asynchronous behavior: CUDA kernels are designed to run asynchronously, meaning the
host does not wait for the device to complete the kernel before continuing its own execution.

🟩 Slide 1: Launching Kernels in CUDA

✅ Kernel Launch Syntax
cpp

Copy code

kernel<<<dim3 dG, dim3 dB>>>(...);

This is how you launch a kernel (a function that runs on the GPU).

● kernel → the name of the GPU function you want to run.

● dG (gridDim) → how many blocks in the grid (can be 1D or 2D).

● dB (blockDim) → how many threads in each block (can be 1D, 2D, or 3D).
This <<< >>> syntax is not regular C/C++; it’s a special CUDA extension to tell the GPU how much
parallel work to do.

✅ Execution Configuration Details

🔸 dim3 dG (Grid Size)

● Represents the number of blocks in the whole grid.

● Usually 1D or 2D (i.e., dG.x, dG.y).

● Total number of blocks = dG.x * dG.y

🔸 dim3 dB (Block Size)

● Represents the number of threads in one block.

● It can be 1D, 2D, or 3D (i.e., dB.x, dB.y, dB.z).

● Total threads per block = dB.x * dB.y * dB.z

🔹 Important Note:

If you don’t set a value for one of the dim3 fields, it automatically becomes 1.

✅ What does 1D or 2D mean in CUDA grids and blocks?

CUDA allows you to organize threads and blocks in one (1D), two (2D), or three (3D) dimensions
depending on your problem.

🔹 1D (One-Dimensional)

You only use the .x component:

cpp

Copy code

dim3 grid(4); // 4 blocks in 1D

dim3 block(256); // 256 threads per block in 1D

🧠 Useful for simple problems like vector addition.

🔹 2D (Two-Dimensional)

You use .x and .y:

cpp

Copy code

dim3 grid(4, 5); // 4 blocks in x, 5 in y → total = 20 blocks

dim3 block(16, 16); // 16x16 threads per block = 256 threads/block

🧠 Useful for 2D data like images or matrices.

“If you don’t set a value for one of the dim3 fields, it automatically becomes 1.”

✅ Simple Example:
cpp

Copy code

dim3 block(256); // This is the same as dim3 block(256, 1, 1)

dim3 grid(4); // This is the same as dim3 grid(4, 1, 1)

kernel<<<grid, block>>>(...);

✅ What it means:

● block.x = 256, block.y = 1, block.z = 1

● grid.x = 4, grid.y = 1, grid.z = 1

Even though you only gave one number (256), CUDA automatically sets the other two dimensions (y
and z) to 1.

🟢 Slide 2: Examples of Execution Configuration

🔸 Example 1: Manual Initialization

cpp

Copy code

dim3 grid, block;

grid.x = 2; grid.y = 4;

block.x = 8; block.y = 16;

kernel<<<grid, block>>>(...);

● Grid has 2 * 4 = 8 blocks

● Each block has 8 * 16 = 128 threads

🔸 Example 2: Constructor Initialization

cpp

Copy code
dim3 grid(2, 4), block(8, 16);

kernel<<<grid, block>>>(...);

This does the same as above, just a cleaner way to write it.

🔸 Example 3: One-line Shortcut

cpp

Copy code

kernel<<<32, 512>>>(...);

● 32 blocks in 1D grid

● 512 threads per block

🟢 Slide 3: CUDA Built-in Device Variables

ALL global and __device__ functions have access to these automatically defined variables

These are automatically available inside your kernel.

🔹 gridDim

● Total number of blocks in the grid (max 2D)

🔹 blockDim

● Total threads per block (x, y, z)

🔹 blockIdx

● Position (index) of the current block in the grid

🔹 threadIdx

● Position (index) of the thread within its block

CUDA Execution Hierarchy Overview
1. Grid: A collection of blocks.

2. Block: A collection of threads.

3. Thread: The smallest unit of execution.

CUDA allows you to define:

● How many blocks are in the grid (1D, 2D, or 3D),

● How many threads are in each block (1D, 2D, or 3D).

dim3 grid(4, 4);

This defines a 2D grid of blocks:

● 4 blocks in the X direction

● 4 blocks in the Y direction

Total blocks = 4 × 4 = 16 blocks

dim3 block(4, 4);

This defines a 2D block of threads:

● 4 threads in the X direction

● 4 threads in the Y direction

Total threads per block = 4 × 4 = 16 threads

You're defining a 2D grid of threads, like this:

markdown

CopyEdit

Y ↑

4 | (0,3) (1,3) (2,3) (3,3)

3 | (0,2) (1,2) (2,2) (3,2)

2 | (0,1) (1,1) (2,1) (3,1)

1 | (0,0) (1,0) (2,0) (3,0)

—————————————→ X

0 1 2 3

Each coordinate pair (threadIdx.x, threadIdx.y) is a unique thread → total 4×4 = 16

threads.

Total Threads Launched

To find total number of threads launched on the GPU:

Total Threads=(Blocks in Grid)×(Threads per Block)=16×16=256 threads\text{Total Threads} = (\

text{Blocks in Grid}) \times (\text{Threads per Block}) = 16 \times 16 = \boxed{256 \text{ threads}}Total
Threads=(Blocks in Grid)×(Threads per Block)=16×16=256 threads

Thread Indexing Example

Each thread can compute its unique global index using:

cpp

CopyEdit

int tx = threadIdx.x; // Thread index within a block (X)

int ty = threadIdx.y; // Thread index within a block (Y)

int bx = blockIdx.x; // Block index within the grid (X)

int by = blockIdx.y; // Block index within the grid (Y)

int blockDimX = blockDim.x; // Number of threads per block in X

int blockDimY = blockDim.y; // Number of threads per block in Y

// Global thread index in 2D

int x = bx * blockDimX + tx;

int y = by * blockDimY + ty;

scss

Each small cell inside represents one thread.

If you'd like, I can also show you a complete working CUDA kernel using this configuration.

You said:

IS THIS A IN BUILD COMMAND

ChatGPT said:

Great question!

No, grid(4, 4) and block(4, 4) are not built-in CUDA commands — they are just variable
initializations using the CUDA-provided dim3 type.

🔧 Here's what’s actually happening:

cpp

CopyEdit

dim3 grid(4, 4);

dim3 block(4, 4);

This is equivalent to:

cpp

CopyEdit

dim3 gridDim(4, 4); // Grid has 4 blocks in X and 4 in Y

dim3 blockDim(4, 4); // Each block has 4 threads in X and 4 in Y

Then you use these variables when launching the CUDA kernel:

cpp

CopyEdit

myKernel<<<grid, block>>>();
🧠 What's dim3?

● dim3 is a special CUDA-defined data type used to specify dimensions (X, Y, Z).

It’s just a structure:

cpp
CopyEdit
struct dim3 {

unsigned int x, y, z;

};

So this is not a command like printf() or malloc() — it’s a constructor call creating a 2D or 3D
size for blocks and grids.

Slide 1: Minimal Kernels (CUDA Basics)

This slide shows 3 simple CUDA kernel examples and what each one outputs.

1. First Kernel
cpp

Copy code

__global__ void kernel(int *a) {

int idx = blockIdx.x * blockDim.x + threadIdx.x;

a[idx] = 7;

● What's happening: Every thread calculates its unique index and stores the number 7 at that
index.

● Output: All elements in array = 7 7 7 7 7 7 7 7 7 7

 ● Why: Every thread writes 7, so the entire array is filled with 7s.

2. Second Kernel
cpp

Copy code

__global__ void kernel(int *a) {

int idx = blockIdx.x * blockDim.x + threadIdx.x;

a[idx] = blockIdx.x;

● What's happening: Each thread writes the block ID to its array location.

● Output: 0 0 0 0 1 1 1 1 2 2 2 2

● Why: All threads in the same block share the same blockIdx.x.

3. Third Kernel
cpp

Copy code

__global__ void kernel(int *a) {

int idx = blockIdx.x * blockDim.x + threadIdx.x;

a[idx] = threadIdx.x;

● What's happening: Each thread writes its thread ID within the block.
 ● Output: 0 1 2 3 0 1 2 3 0 1 2 3

● Why: threadIdx.x starts at 0 for each block and increases per thread.

Slide 2: Increment Array Example

This slide compares a CPU program and a CUDA (GPU) program that both increment every element in
an array.

CPU Version (Sequential Execution)

cpp

Copy code

void inc_cpu(int *a, int N) {

for (int idx = 0; idx < N; idx++) {

a[idx] = a[idx] + 1;

● Runs on 1 CPU core.

● Loops from 0 to N and increases each value by 1.

CUDA Version (Parallel Execution on GPU)

cpp

Copy code

__global__ void inc_gpu(int *a_d, int N) {

 int idx = blockIdx.x * blockDim.x + threadIdx.x;

if (idx < N)

a_d[idx] = a_d[idx] + 1;

● blockIdx.x: The block number in the grid.

● blockDim.x: Number of threads per block.

● threadIdx.x: Thread index within a block.

● idx: Unique thread index (used as array index).

● Condition if (idx < N): Ensures we don’t go out of bounds.

Main function (CUDA version)

cpp

Copy code

dim3 dimBlock(blocksize);

dim3 dimGrid(ceil(N / (float)blocksize));

inc_gpu<<<dimGrid, dimBlock>>>(a_d, N);

● dimBlock: Number of threads in a block.

● dimGrid: Number of blocks in the grid, calculated to cover all N elements.

● <<<dimGrid, dimBlock>>>: CUDA syntax to launch the kernel on GPU.

Quick Example
Let’s say:

● N = 10

● blocksize = 4

Then:

● You need ceil(10/4) = 3 blocks.

● Threads: 3 * 4 = 12, but only the first 10 are used due to the if (idx < N) check.

z
Tab 2
🔍 Why does it seem there's no difference between atomic and critical?

In your specific example (a simple counter++), both #pragma omp atomic and #pragma omp
critical behave the same — they both ensure thread-safe access and produce correct results.

✅ But here's the real difference:

🔸 atomic is optimized for a single memory operation

It only works for very simple expressions, like:

Copy code

x++;

x += y;

🔸 critical can protect multiple operations or complex logic

It locks a code block, not just one variable.

🧪 Let’s look at a real difference with an updated code example:

✅ Example: Only critical works here

c

Copy code

#include <stdio.h>

#include <omp.h>

int counter = 0;

int main() {
✅ Slide Title: Unique Thread IDs
This slide explains how CUDA gives each thread a unique global ID so it knows exactly what part of the
data to work on (like an index in an array).

🔹 Built-in variables are used to determine unique thread IDs

CUDA provides special built-in variables automatically for each thread and block. These are:

● threadIdx.x: The index of the thread inside the block

● blockIdx.x: The index of the block inside the grid

● blockDim.x: The total number of threads in one block

🔸 Map from local thread ID (threadIdx) to a global ID

Every thread has:

 ● A local ID (within its own block): threadIdx.x

● But to access global data (e.g., array index), you need a global thread ID.

👉 CUDA uses this formula:

ini

CopyEdit

globalThreadId = blockIdx.x * blockDim.x + threadIdx.x

This gives each thread a unique number across all blocks.

📦 Diagram Explanation:

The diagram shows:

● A grid of 3 blocks (blockIdx.x = 0, 1, 2)

● Each block has 5 threads (threadIdx.x = 0 to 4)

● So blockDim.x = 5

Let's compute the global thread ID for each thread:

Block Index Thread Index Global Thread ID (blockIdx.x *
(blockIdx.x) (threadIdx.x) blockDim.x + threadIdx.x)

0 0, 1, 2, 3, 4 0, 1, 2, 3, 4

1 0, 1, 2, 3, 4 5, 6, 7, 8, 9

2 0, 1, 2, 3, 4 10, 11, 12, 13, 14

So all 15 threads have unique global IDs from 0 to 14.

Tab 3
🧠 1. Concepts and Objectives (Plain Explanation)
Objective: Understand how to handle shared variables in OpenMP to prevent data races — situations
where multiple threads modify the same variable simultaneously, leading to unpredictable behavior.

You will:

● Implement parallel summation of an array using various OpenMP techniques.

● Measure and compare performance and correctness.

● Learn which synchronization technique is best for different scenarios.

🔐 2. Synchronization Methods in OpenMP (with Explanation)

Method Description

reduction Threads work on local copies and combine the results automatically — safe and
efficient.

atomic Only the update to the shared variable is atomic — avoids full locking, low overhead.

critical Only one thread executes the protected section at a time — simple, but slow.

locks Manual locking mechanism — gives full control but expensive and complex.

no sync No protection at all — fast but causes incorrect results due to data races.

✅ DETAILED LINE-BY-LINE CODE EXPLANATION

cpp

Copy code

#include <iostream>

● Includes the input/output stream library used for std::cout.

cpp
Array Initialization
cpp

Copy code

int n = 1000000;

● Sets the size of the array to 1 million.

cpp

Copy code

std::vector<int> arr(n);

● Declares a vector arr of size n to store integers.

cpp

Copy code

int sum = 0;

● A shared variable used to store the final sum result in each method.

Filling the Array with Random Numbers

cpp

Copy code

srand(time(0));

● Seeds the random number generator with the current system time.

cpp

Copy code
for (int i = 0; i < n; ++i) {

arr[i] = rand() % 100 + 1;

● Fills the array with random numbers between 1 and 100.

🧪 Serial Sum (Baseline for Performance)

cpp

Copy code

double start_time = omp_get_wtime();

● Starts a timer using OpenMP’s omp_get_wtime() to measure execution time.

cpp

Copy code

int serial_sum = 0;

for (int i = 0; i < n; ++i) {

serial_sum += arr[i];

● Performs a simple sum of all elements — serially.

cpp

Copy code

double end_time = omp_get_wtime();

std::cout << "Serial Sum: " << serial_sum << std::endl;

std::cout << "Serial Execution Time: " << end_time - start_time << "
seconds." << std::endl;

● Ends the timer and prints the sum and time taken.

🧵 Parallel Versions
1. 🔁 Reduction
cpp

Copy code

sum = 0;

start_time = omp_get_wtime();

#pragma omp parallel for reduction(+:sum)

for (int i = 0; i < n; ++i) {

sum += arr[i];

end_time = omp_get_wtime();

● What it does: Each thread computes a local sum; OpenMP adds them together at the end.

● Safe and efficient because OpenMP handles data separation and combining.

2. ⚛️Atomic Operation
cpp

Copy code

sum = 0;

start_time = omp_get_wtime();
#pragma omp parallel for

for (int i = 0; i < n; ++i) {

#pragma omp atomic

sum += arr[i];

end_time = omp_get_wtime();

● What it does: The #pragma omp atomic makes sure sum += arr[i] happens
atomically (one at a time).

● Faster than critical, but still slower than reduction due to overhead from many atomic
operations.

3. 🚧 Critical Section
cpp

Copy code

sum = 0;

start_time = omp_get_wtime();

#pragma omp parallel for

for (int i = 0; i < n; ++i) {

#pragma omp critical

sum += arr[i];

end_time = omp_get_wtime();

● What it does: Only one thread can enter the critical block at a time.

● Safe but slow because it serializes access to sum.

4. 🔒 Locks
cpp

Copy code

sum = 0;

omp_lock_t lock;

omp_init_lock(&lock);

start_time = omp_get_wtime();

#pragma omp parallel for

for (int i = 0; i < n; ++i) {

omp_set_lock(&lock);

sum += arr[i];

omp_unset_lock(&lock);

end_time = omp_get_wtime();

omp_destroy_lock(&lock);

● What it does: Like critical, but you manually lock and unlock around the shared variable.

● More flexible but also higher overhead and risk of forgetting to unlock (leading to deadlocks).

5. ❌ No Synchronization (Data Race)

cpp

Copy code

sum = 0;

start_time = omp_get_wtime();

#pragma omp parallel for

for (int i = 0; i < n; ++i) {

sum += arr[i]; // No synchronization!

end_time = omp_get_wtime();

● What it does: All threads write to sum at the same time.

● Fast but incorrect — final value is unpredictable due to race conditions.

📤 Output Statements
cpp

Copy code

std::cout << "Parallel Sum with <Technique>: " << sum << std::endl;

std::cout << "Execution Time (<Technique>): " << end_time - start_time

<< " seconds.\n\n";

● Prints the sum and time taken for each method.

📊 ANALYSIS AND COMPARISON TABLE

Method Correct? Speed Explanation

Serial ✅ Baseline Single thread; used for comparing others.

Reduction ✅ Fastest ✅ Optimal; OpenMP handles all combining safely and

efficiently.

Atomic ✅ Moderate ⚠️ Safe; less overhead than critical/locks, but slower than
reduction.

Critical ✅ Slow ⏳ Correct but slow due to thread contention.

Locks ✅ Slowest ⛔ Correct but heavy; manual lock/unlock slows performance.

 No Sync ❌ Fast ❗ Unsafe; gives wrong result due to simultaneous access to
shared sum.

✅ 1. Reduction
Description:
OpenMP automatically creates private copies of the variable for each thread, performs the operation
locally, and combines the results at the end of the parallel region.

✔️Advantages:

● Fastest among synchronization methods.

● No manual synchronization is needed.

● Safe and correct (no data races).

● Highly scalable for large data sets and many threads.

● Well-optimized internally by OpenMP.

❌ Drawbacks:

● Only works with certain operations (like +, *, max, etc.).

● Limited to scalar variables, not applicable to arrays or complex logic inside loops.

✅ 2. Atomic
Description:
#pragma omp atomic ensures a single memory operation (like sum += arr[i]) is done
without interference.

✔️Advantages:

● Safer than no synchronization — prevents data races.

● More efficient than critical/locks for simple updates.

 ● Good choice for frequent small updates to a shared variable.

❌ Drawbacks:

● Only works for simple, one-liner operations (e.g., increment, add, subtract).

● More overhead than reduction, especially with many threads.

● Not suitable for compound operations (e.g., modifying multiple variables atomically).

✅ 3. Critical
Description:
A critical section ensures only one thread at a time can execute the protected code block.

✔️Advantages:

● Very general-purpose — can protect complex logic, multiple operations, or large blocks.

● Ensures correctness by avoiding race conditions.

❌ Drawbacks:

● Slower than atomic and reduction — threads must wait to enter the critical section.

● Can cause bottlenecks under high contention.

● Not scalable for fine-grained tasks (like summing millions of numbers).

✅ 4. Locks
Description:
Locks (omp_lock_t) provide manual control over synchronization by explicitly locking and unlocking
access to a critical section.

✔️Advantages:
 ● Highly flexible — can protect any region of code.

● Can implement complex synchronization schemes (e.g., reader-writer locks).

❌ Drawbacks:

● Most overhead due to manual locking.

● Risk of deadlocks if not managed carefully.

● Slower than all other methods for simple tasks like summing.

● Harder to write and debug correctly.

❌ 5. No Synchronization
Description:
Threads update the shared variable without any protection — leads to data races.

✔️Advantages:

● Fastest execution time (because there's no synchronization).

● Useful for testing or teaching purposes (to demonstrate race conditions).

❌ Drawbacks:

● Incorrect results — non-deterministic and unreliable.

● Not thread-safe — behavior depends on timing of threads.

● Should never be used in real applications.

Code Line:
cpp

Copy code

srand(time(0));
🔍 What does it do?

This line initializes the random number generator in C++ so that the numbers you get from rand() are
different each time you run the program.

READING ASSIGNMENT:
🧩 Part 1: Task-Level Parallelism with Dependencies in OpenMP

✅ Definition: Task-Level Parallelism

Task-level parallelism in OpenMP allows the programmer to define independent or dependent tasks that
are executed in parallel. OpenMP schedules these tasks among the available threads, and you can
control dependencies between them using the depend clause.

🧪 Clean and Runnable Code: Task Dependencies

Copy

Edit

#include <stdio.h>

#include <omp.h>

// Task 1: Simulates computation and stores result

void task1(int *result) {

printf("Task 1 started\n");

for (int i = 0; i < 100000000; i++); // Simulate computation

*result = 10;

printf("Task 1 finished\n");

// Task 2: Simulates computation and stores result

void task2(int *result) {

 printf("Task 2 started\n");

for (int i = 0; i < 100000000; i++); // Simulate computation

*result = 20;

printf("Task 2 finished\n");

// Task 3: Depends on Task 1 and Task 2

void task3(int result1, int result2) {

printf("Task 3 started\n");

int combined = result1 + result2;

printf("Task 3 finished. Combined result: %d\n", combined);

int main() {

int result1 = 0, result2 = 0;

omp_set_num_threads(4); // Use 4 threads

#pragma omp parallel

#pragma omp single

// Task 1 creation

#pragma omp task depend(out: result1)

task1(&result1);

// Task 2 creation

#pragma omp task depend(out: result2)

task2(&result2);
 // Task 3 depends on both Task 1 and Task 2

#pragma omp task depend(in: result1, result2)

task3(result1, result2);

return 0;

🧠 Line-by-Line Explanation:

omp_set_num_threads(4);

→ Tells OpenMP to use 4 threads for parallel execution.

#pragma omp parallel

→ Starts a parallel region where multiple threads are created.

#pragma omp single

→ Ensures that only one thread creates the tasks inside the block.

#pragma omp task depend(out: result1)

→ Declares Task 1, which produces result1. This task must complete before any task that uses result1 as
input can begin.

#pragma omp task depend(out: result2)

→ Declares Task 2, which produces result2.

#pragma omp task depend(in: result1, result2)

→ Declares Task 3, which depends on both result1 and result2. It will wait until Task 1 and Task 2 finish.
The loop inside each task is just a dummy operation to simulate time-consuming work.

📌 Important Concepts:

Feature Explanation

depend(out: var) This task writes to var

depend(in: var) This task reads from var and must wait for any previous out on var to finish

#pragma omp single Only one thread generates the tasks; tasks themselves can run in parallel

🧩 Part 2: OpenMP Barrier

✅ Definition: Barrier

A barrier is a point in the program where all threads must stop and wait until every thread has reached
the same point. It's useful to ensure one phase of work is complete before the next starts.

🧪 Clean and Runnable Code: Barrier Example

#include <stdio.h>

#include <omp.h>

void task1() {

printf("Task 1: Thread %d is working...\n", omp_get_thread_num());

for (int i = 0; i < 100000000; i++); // Simulated work

printf("Task 1: Thread %d is done\n", omp_get_thread_num());

void task2() {

printf("Task 2: Thread %d is working...\n", omp_get_thread_num());

for (int i = 0; i < 100000000; i++); // Simulated work

printf("Task 2: Thread %d is done\n", omp_get_thread_num());

}
int main() {

omp_set_num_threads(4); // Use 4 threads

#pragma omp parallel

task1(); // All threads do Task 1

#pragma omp barrier // Synchronization point

task2(); // All threads do Task 2 only after Task 1 is done

return 0;

🧠 Line-by-Line Explanation:

omp_set_num_threads(4);

→ Sets number of threads to 4.

#pragma omp parallel

→ Starts a parallel region with multiple threads.

task1();

→ Each thread independently performs Task 1.

#pragma omp barrier

→ Barrier point. All threads must finish Task 1 and reach this point before any can proceed.

task2();

→ Only starts when all threads have passed the barrier.

🔍 Why Use a Barrier?

To synchronize threads before moving to a second phase of computation.

Prevents race conditions in later computations that rely on earlier results.

Example: Each thread writes to a section of an array; we want to sort the array after all threads are done
writing.

✅ Output Behavior:

Since threads run independently, the output order varies — but:

All "Task 1 done" messages appear before any "Task 2 started".

This shows barrier synchronization works.

🔹 What is #pragma omp single?

When you write #pragma omp parallel, many threads are created. If you then write code inside
that parallel block, all threads will try to run that code at the same time.

But in OpenMP task-based parallelism, you want only one thread to create the tasks, not all threads.
That’s where #pragma omp single is used.

✅ Simple Explanation:
c

CopyEdit

#pragma omp parallel

{
 #pragma omp single

// This block is executed by only ONE thread

// That thread creates all the tasks

● ✔️One thread (any one of the available threads) will enter the single block.

● ❌ The other threads will wait (unless you say not to) or do nothing there.

● ✅ Inside this single block, you can define tasks using #pragma omp task.

🧠 Why do we need this?

If all threads create the same tasks, you'll get duplicate tasks — that's wrong.

We want only one thread to create:

CopyEdit

#pragma omp task

do_something();

Then OpenMP can run the task in any available thread (not just the one that created it).

🧪 Very Simple Code Example:

c

CopyEdit

#include <stdio.h>
#include <omp.h>

int main() {

#pragma omp parallel

// Only one thread will run the below block

#pragma omp single

printf("Thread %d is creating tasks\n",

omp_get_thread_num());

// These tasks can run on any thread

#pragma omp task

printf("Task A by thread %d\n", omp_get_thread_num());

#pragma omp task

printf("Task B by thread %d\n", omp_get_thread_num());

return 0;

✅ Output Example:
arduino

CopyEdit

Thread 2 is creating tasks

Task A by thread 1

Task B by thread 3

● "Thread 2 is creating tasks" → Only one thread printed this (due to single).

● Task A and Task B ran on different threads — this is parallel task execution.

MPI COPY NOTES:

🔹 Cluster Computing Basics

● Cluster Computing:

○ A system where multiple computers (nodes) work together.

○ They are connected through LAN using MPI (Message Passing Interface).

● MIMD (Multiple Instruction, Multiple Data):

○ Two types:

1. Shared Memory (Multiprocessor): All processors share the same memory.

2. Distributed Memory (Multicomputer): Each processor has its own local memory.

○ These computers communicate over a network but operate independently (i.e., different
functions).

🧠 Example: A university lab where each computer does different tasks but shares results over a network.

Every computer in cluster needs to have a software in order to communicate with each other and that software
is called LAM(Local AArea multicomputers ) MPI .

🔹 Cluster Configuration & Setup

● Cluster: A group of similar computers that work together.

● Grid: A more complex setup that connects various clusters over the internet.

● Each computer in the cluster needs:

○ Proper configuration.
 ○ Ability to talk with others (via LAM - Local Area Multicomputer).

● lamboot config command: Initializes the cluster configuration.

● Running an MPI program:

○ Example: mpirun [Link] -np 10 means running the [Link] program on 10 processors.

● TCP/UDP: These are networking protocols, but as developers, you don’t have to worry about their
technical setup here.

🔹 SPMD (Single Program Multiple Data)

● SPMD: A programming model where the same program runs on multiple computers, but each handles
different data.

● Each processor has a Rank (ID), from 0 to n-1.

🧠 Example: Sorting a huge list - each processor sorts a part of the list.

🔹 MPI Basics

● Important MPI Functions:

○ MPI_Init(): Start MPI.

○ MPI_Comm_size(): How many processors are running.

○ MPI_Comm_rank(): Rank (ID) of the processor.

○ MPI_Send(): Send a message.

○ MPI_Recv(): Receive a message.

○ MPI_Finalize(): End MPI.

● Use mpirun -np n [Link] to execute the program.

● MPI_COMM_WORLD is the default group of all processors.

🔹 Communication Flow in MPI

● One processor (Rank 0) acts as the master:

○ It divides tasks and sends to others (slaves).

○ They do the job and send results back.

🧠 Example: Master processor gives each student a question to solve, collects answers at the end.

🔹 Broadcast in MPI

● Broadcast: One processor sends data to all.

● Used when one value (e.g., a constant) is needed by all processes.

🧠 Example: A teacher sharing the exam rules with all students.

● Group Communication: You can send data to:

○ Whole group

○ Sub-groups

○ Individual processes

🔹 Collective Operations in MPI

● Reduce Operation: Combines values from all processes into one (e.g., sum, max).

● Scan: Each process gets a running total from earlier ones.

🧠 Example:

● Reduce: Total score of all students.

● Scan: Each student knows the total marks of all students before them.