Parallel Computing Assignment Questions

1. Explain the concept of Deadlock. What are the conditions for it?
Deadlock is a situation in a concurrent system where two or more processes are unable to
proceed because each is waiting for a resource that is held by another process in the same set.
This results in a permanent blocking of all involved processes.
The four necessary Coffman conditions that must hold simultaneously for a deadlock to
occur are:
1. Mutual Exclusion: At least one resource must be held in a non-sharable mode; only
one process can use the resource at a time.
2. Hold and Wait: A process must be holding at least one resource and waiting to
acquire additional resources that are currently held by other processes.
3. No Preemption: Resources cannot be forcibly taken away from a process; they can
only be released voluntarily by the process holding them.
4. Circular Wait: A circular chain of processes must exist, where each process is
waiting for a resource held by the next process in the chain.
Example: Process A holds Resource 1 and requests Resource 2. Process B holds Resource 2
and requests Resource 1. Both are stuck waiting for the other to release the resource they
need
2. What is the key difference between multicore and multiprocessing systems?
The key difference lies in the physical packaging and integration of processing units.
 Multiprocessing: Refers to a system with multiple distinct physical CPUs (Central
Processing Units) on a single motherboard or across multiple boards. Each CPU has
its own independent set of resources (e.g., cache, memory controller). Communication
between CPUs happens via the system bus or an inter-processor network. This is a
system-level architecture.
 Multicore: Refers to a single physical CPU (chip) that contains multiple
independent execution cores (Core 1, Core 2, etc.) on the same integrated circuit
(IC) die. These cores often share some resources, like the last-level cache (LLC) and
the memory controller, leading to faster on-chip communication. This is a processor-
level architecture.
Analogy: Multiprocessing is like having several separate kitchens in a restaurant. Multicore
is like having one large kitchen with several chefs working at different stations, sharing some
common equipment.

3. How does pipelining improve CPU performance?

Pipelining improves CPU performance by increasing instruction throughput (the number of
instructions completed per unit of time), analogous to an assembly line.
A non-pipelined processor must complete all stages of one instruction (Fetch, Decode,
Execute, Memory, Write-back) before beginning the next. This is inefficient, as most
hardware is idle at any given time.
A pipelined processor overlaps the execution of multiple instructions. While one instruction
is being executed, the next one is being decoded, and the one after that is being fetched.
Ideally, one instruction completes on every clock cycle, even though the latency (time to
complete a single instruction) remains the same.
Performance Gain: If there are k stages in the pipeline and n instructions, the time to
complete them is roughly k + (n - 1) cycles, compared to k * n cycles for a non-pipelined
processor. This leads to a significant speedup for large n.

4. What is the difference between a thread and a process?

Thread (Lightweight
Feature Process
Process)

An independent instance of a A component of a process; a

Definition running program with its own single sequence of execution
state. within a process.

Shares the memory space

and resources (code, data,
Has its
heap, open files) of its
Resource own independent memory space
parent process. Each thread
Ownership (code, data, heap, stack), file
has its own private
handles, and system resources.
stack for local variables and
call history.

Lightweight and fast, as it

Creation & Heavyweight and expensive, as it
only requires creating a
Context involves creating a new address
stack and register set within
Switching space and loading the program.
an existing address space.

Inter-Thread
Inter-Process Communication
Communication is simple
(IPC) is complex and slower
Communication and fast because threads
(e.g., pipes, message queues,
share memory (e.g., through
shared memory).
global variables).
 Thread (Lightweight
Feature Process
Process)

A crash in one thread can

Isolation & Fault A crash in one process does not bring down the entire
Tolerance affect other processes. process, affecting all other
threads within it.

5. What is a race condition? Explain in detail.

A race condition is a flaw in a system or process where the output or result is unexpectedly
and critically dependent on the sequence or timing of other uncontrollable events (i.e., the
scheduling of threads/processes).
It occurs when two or more threads can access shared data and they try to change it at the
same time. Because the thread scheduling algorithm can swap between threads at any time,
the sequence of operations is non-deterministic. This leads to inconsistent and erroneous
results.
Detailed Example (The "Lost Update" Problem):
Imagine a shared variable balance = 100.
 Thread A (deposit): Reads balance = 100.
 Thread B (withdraw): Reads balance = 100.
 Thread A: Adds 50, so 100 + 50 = 150. Intends to write 150.
 Thread B: Subtracts 20, so 100 - 20 = 80. Writes 80 to balance.
 Thread A: Writes 150 to balance, overwriting the 80.
The final balance is 150, but it should be 100 + 50 - 20 = 130. The update from Thread B is
lost. The "race" between the threads to update the variable corrupted the data. This is solved
using synchronization mechanisms like mutexes or semaphores.

6. What are semaphores? How are they used?

A semaphore is a synchronization primitive (a variable or abstract data type) used to control
access to a common resource by multiple threads or processes in a concurrent system. It was
invented by Edsger Dijkstra.
A semaphore is essentially a counter with two atomic operations:
1. wait(S) (or P): Decrements the semaphore value. If the value becomes negative, the
thread/process executing the wait is blocked and placed in a queue.
 2. signal(S) (or V): Increments the semaphore value. If there are any threads blocked in
the queue, one of them is unblocked.
How they are used:
 Counting Semaphore: Can have any value and is used to control access to a resource
with multiple instances (e.g., a pool of 5 identical printers).
 Binary Semaphore (Mutex): A semaphore restricted to the values 0 and 1. It is used
to provide mutual exclusion, ensuring only one thread can access a critical section of
code at a time, protecting shared data from race conditions.

7. What is a shared variable in multithreaded programming?

A shared variable is a variable (e.g., in global memory, the heap, or a static variable) that
can be accessed and modified by more than one thread within a single process.
Because all threads in a process share the same memory address space, they can all read and
write to these variables. This is a powerful feature for efficient communication between
threads (e.g., passing data, signaling status). However, it is also the primary source of
concurrency bugs like race conditions if access to these variables is not properly
synchronized using mechanisms like mutexes or semaphores.
Key characteristic: Any change made to a shared variable by one thread is immediately
visible to all other threads in the same process.

8. What is context switching and why is it costly in parallel computing?

Context switching is the process of saving the state (context) of a currently running thread or
process (including its program counter, registers, stack pointer, etc.) so that it can be restored
and resumed later, and then loading the saved state of a different thread or process to run.
Why it is costly:
1. Direct Overhead: The act of saving and loading registers and memory management
unit (MMU) contexts (e.g., page table base registers) takes CPU cycles where no
useful user work is being done.
2. Cache Pollution: When a process/thread is switched out, the data it was using
remains in the CPU cache. When a new process/thread is switched in, it brings its
own data, which overwrites (flushes) the cache. This leads to a high rate of cache
misses when the switched-out process resumes, drastically slowing it down as it has
to fetch data from main memory.
3. Scheduler Overhead: The operating system's scheduler code itself must run to
decide which process to switch to, consuming additional CPU time.
In parallel computing, where many threads/processes are constantly competing for the CPU,
excessive context switching can significantly degrade overall system performance.

9. What is the time complexity of Merge Sort? Why is it preferred for parallel
implementation?
 Time Complexity: Merge Sort has a time complexity of O(n log n) for all cases
(best, average, and worst).
 Why it's preferred for parallel implementation:
1. Divide and Conquer Nature: The algorithm naturally splits the problem into
independent sub-problems. The left and right halves of the array can be
sorted completely independently and in parallel.
2. Low Synchronization Overhead: Threads can work on sorting their sub-
arrays without needing to communicate or synchronize with others until the
very end, at the merge phase. This minimizes the costly overhead of locking
and coordination.
3. Predictable Data Access Patterns: Its sequential memory access patterns
during the merge phase are cache-friendly, which is a benefit even in parallel
execution.

10. Explain the Divide and Conquer approach and give one example.
Divide and Conquer is a fundamental algorithm design paradigm based on multi-branched
recursion. It works by recursively breaking down a problem into two or more sub-problems
of the same or related type, until these become simple enough to be solved directly. The
solutions to the sub-problems are then combined to give a solution to the original problem.
It involves three steps at each level of recursion:
1. Divide: Break the problem into several smaller, self-similar subproblems.
2. Conquer: Solve the subproblems recursively. If they are small enough, solve them
directly (this is the base case).
3. Combine: Merge the solutions of the subproblems to create the solution for the
original problem.
Example: Merge Sort (as asked in Q16)
 Divide: Repeatedly split the unsorted list into two halves until each sublist contains
only one element (which is, by definition, sorted).
 Conquer: Sort each sublist. (The base case is a list of size 1, which is already sorted).
 Combine: Merge the sorted sublists back together into a new sorted list.
Other examples include QuickSort, Binary Search, and Strassen's algorithm for matrix
multiplication.

11. Differentiate between General Purpose Register and Special Purpose Register.

Feature General Purpose Register (GPR) Special Purpose Register (SPR)

Used for general operations like

Dedicated to a specific,
storing temporary data, operands for
Function control-oriented function for
arithmetic and logic operations, and
managing processor operation.
addresses for memory access.

Their usage is hardwired by

Can be used interchangeably by the
the CPU architecture; they
Flexibility programmer or compiler for various
cannot be used for arbitrary
tasks.
data storage.

Program Counter
(PC): Holds the address of the
next instruction.
Stack Pointer (SP): Points to
the top of the stack.
AX, BX, CX, DX in
Examples Status Register
x86, R0 to R31 in ARM/RISC-V.
(Flags): Contains status bits
(e.g., Zero, Carry, Overflow).
Memory Address Register
(MAR), Memory Data
Register (MDR).

12. Compare multiprocessing, multithreading, and multicore systems.

Aspect Multiprocessing Multithreading Multicore

Using multiple Executing multiple Placing multiple

Core Idea CPUs to execute threads within a cores on a single
processes. single process. CPU chip.

Level System Programming/OS Processor

Aspect Multiprocessing Multithreading Multicore

Architecture Model Microarchitecture

Process-level Thread-level Core-level

Parallelism
parallelism parallelism parallelism

Each CPU may

All Cores
have its own
threads share the typically share the
Memory memory or share
same memory space last-level cache and
memory via a bus
of the process. memory controller.
(e.g., NUMA).

Slow (IPC:
Fast (shared Very Fast (on-chip
Communication messages, shared
memory) interconnect)
memory)

Very Low (threads

High (context Low (context
can run on separate
Overhead switching between switching between
cores
processes) threads)
simultaneously)

13. Explain the role of Special Purpose Registers (SPR) in functioning.

Special Purpose Registers (SPRs) are crucial for the control and operation of the CPU itself.
They are used by the CPU to manage the execution of instructions and the state of the
processor, rather than for general data manipulation.
Key Roles and Examples:
 Program Counter (PC) / Instruction Pointer (IP): Holds the memory address of
the next instruction to be fetched and executed. It is the fundamental register that
dictates program flow.
 Stack Pointer (SP): Points to the top of the runtime stack in memory. The stack is
used for function call management (return addresses, saved registers, local variables).
 Status Register (SR) / Flags Register: Contains individual bits (flags) that reflect the
outcome of the previous operation (e.g., Zero flag - result was zero, Carry flag - an
 arithmetic carry occurred, Overflow flag - signed arithmetic overflow). These flags
control conditional branches (JUMP IF ZERO).
 Memory Address Register (MAR): Holds the address of a memory location to be
read from or written to.
 Memory Data Register (MDR) / Memory Buffer Register (MBR): Holds the data
that is about to be written to memory or has just been read from memory.
Without SPRs, the CPU would have no way to keep track of what to do next or manage its
internal state.

14. Explain data line flow (buses) and its types (address, control, data).
A bus is a communication system that transfers data between components inside a computer
or between computers. It is a shared transmission medium, consisting of a set of parallel
wires (lines).
A system bus typically consists of three specialized sub-buses:
1. Data Bus:
o Function: Carries the actual data (instructions, operands) between the CPU,
memory, and I/O devices.
o Bidirectional: Data can flow to (read) and from (write) the CPU.

o Width: The width of the data bus (e.g., 64-bit) determines how many bits can
be transferred at once, which is a key factor in a system's performance.
2. Address Bus:
o Function: Carries the memory addresses from the CPU to memory and I/O
devices. The CPU places an address on this bus to specify where it wants to
read from or write to.
o Unidirectional: Addresses are only generated by the CPU.

o Width: The width of the address bus (e.g., 32-bit) determines the maximum
amount of addressable memory (e.g., 2³² = 4 GB).
3. Control Bus:
o Function: Carries command and timing signals between the CPU and other
components. These signals coordinate all activities.
o Signals Include: Memory Read (MEMR), Memory Write (MEMW), I/O
Read (IOR), I/O Write (IOW), Interrupt Request (IRQ), Bus
Grant, Clock.
15. Compare tightly coupled and loosely coupled systems.

Tightly Coupled Systems Loosely Coupled Systems

Feature
(Multiprocessors) (Distributed Systems)

Processors communicate Processors communicate

Interaction &
through shared memory (a by passing messages over a
Communication
common bus). network (e.g., LAN, Internet).

Multiple independent
Multiple processors/cores
Processing Units computers (nodes), each with
within a single computer.
its own CPU, memory, and OS.

Each node has its own

Operating Single OS instance controls
OS. They may be
System all processors.
heterogeneous.

Shared memory address Distributed memory. Each

space. All processors have node has its own private
Memory
uniform access time (UMA) memory. No direct memory
or non-uniform (NUMA). access between nodes.

Very high-speed Communication is slower,

Speed &
communication (RAM limited by network speed and
Efficiency
speed). Low latency. latency.

Difficult to scale beyond a

certain number of processors Highly scalable; new nodes can
Scalability
due to bus/memory be added easily to the network.
contention.

A failure in the shared More fault-tolerant; failure of

Fault Tolerance memory or system bus can one node does not cripple the
crash the entire system. entire system.

A multicore PC, a symmetric A cluster of workstations, cloud

Example multiprocessing (SMP) computing infrastructure (AWS,
server. Azure).
16. Explain Merge Sort with an example.
Merge Sort is a stable, comparison-based, divide and conquer sorting algorithm.
Algorithm:
1. Divide: If the list has 0 or 1 element, it is sorted. Otherwise, divide the unsorted list
into two roughly equal halves.
2. Conquer: Recursively sort each half by applying Merge Sort.
3. Combine: Merge the two sorted halves back into one sorted list. This is done by
repeatedly comparing the smallest elements of each half and taking the smaller one.
Example: Sort the list [38, 27, 43, 3, 9, 82, 10]
text
[38, 27, 43, 3, 9, 82, 10] // Divide
/ \
[38, 27, 43, 3] [9, 82, 10] // Divide
/ \ / \
[38, 27] [43, 3] [9, 82] [10] // Divide
/ \ / \ / \ |
[38] [27] [43] [3] [9] [82] [10] // Base Case (sorted)

\ / \ / \ / |
[27, 38] [3, 43] [9, 82] [10] // Merge & Conquer
\ / \ /
[3, 27, 38, 43] [9, 10, 82] // Merge & Conquer
\ /
[3, 9, 10, 27, 38, 43, 82] // Final Sorted List

17. What are cache hits and cache misses?

 Cache Hit: Occurs when the data requested by the CPU (e.g., an instruction or
operand) is found in the cache memory. This is very fast and allows the CPU to
continue processing without waiting.
  Cache Miss: Occurs when the requested data is not found in the cache. The CPU
must then stall and wait for the data to be fetched from the slower main memory (or a
lower level of cache). This incurs a significant performance penalty.
Hit Rate is the percentage of requests that are hits. Miss Rate is 1 - Hit Rate. The goal of
cache design is to maximize the hit rate.

18. Explain issues with cache memory such as write-through, dirty, and write-back.
These terms relate to the cache write policies, which define how data is written to the cache
and main memory.
 Write-Through:
o Policy: Every write to the cache immediately triggers a write to the main
memory.
o Advantage: Main memory is always consistent with the cache. Simple to
implement.
o Disadvantage: High memory traffic. Every write operation is slow because
it must wait for the main memory write to complete. This creates a bottleneck.
 Write-Back:
o Policy: A write only updates the data in the cache. The corresponding main
memory location is updated only when the cache block is evicted/replaced.
o Dirty Bit: Each cache block has an extra bit (the "dirty bit" or "modified bit").
This bit is set to 1 when the data in the cache is modified (written to). When
the block is to be evicted, if its dirty bit is 1, it must be written back to
memory. If it's 0, it can simply be overwritten.
o Advantage: Drastically reduces memory traffic (multiple writes to a block
only cause one memory write at eviction). Much faster.
o Disadvantage: More complex. Memory is not always consistent, which is a
problem for I/O devices that DMA directly from memory (requires cache
coherence protocols).

19. Explain different cache mapping techniques.

These techniques determine where a block of main memory can be placed in the cache.
1. Direct Mapped:
 o Rule: Each block of main memory can be placed in exactly one specific
location in the cache. The location is typically determined by (Block Address)
MOD (Number of Cache Blocks).
o Analogy: A parking lot where each car (memory block) is assigned one
specific parking space.
o Pros: Simple and cheap hardware. Fast lookup.

o Cons: High conflict misses. If two frequently accessed memory blocks map to
the same cache line, they will constantly evict each other ("thrashing").
2. Fully Associative:
o Rule: A block of main memory can be placed in any empty line in the cache.

o Analogy: A parking lot where a car can park in any empty space.

o Pros: Very flexible, minimizes conflict misses.

o Cons: Extremely expensive hardware. To find a block, the cache must

search every single tag in parallel (associative search), which is slow and
power-hungry for large caches. Impractical for anything but very small caches
(e.g., TLB).
3. Set-Associative:
o Rule: A compromise between the two. The cache is divided into S sets. Each
set contains W cache lines (W-way associative). A memory block maps to a
specific set (via MOD S), but can be placed in any of the W lines within that
set.
o Analogy: A parking lot with multiple rows (sets). Your car must park in one
specific row, but can choose any space within that row.
o Pros: Good trade-off. Reduces conflict misses compared to direct mapping,
and is cheaper and faster than fully associative. Most modern CPUs use this
(e.g., 4-way, 8-way, 16-way associative L1/L2 caches).

20. What is virtual memory? Explain its types with concepts like TLP, page fault, page
hit, page miss, and page table.
Virtual Memory is a memory management technique that gives an application the illusion of
a very large, contiguous, private memory space, which may be larger than the available
physical RAM. It separates the logical memory view of a process from physical memory.
 Paging: The most common implementation. Physical and virtual memory are divided
into fixed-size blocks called frames (physical) and pages (virtual).
  Page Table: A data structure stored in RAM, used by the Memory Management Unit
(MMU) to map virtual pages to physical frames. Each process has its own page
table.
 TLB (Translation Lookaside Buffer): A small, very fast cache inside the MMU that
stores recent virtual-to-physical page translations. A TLB hit allows for near-instant
translation. A TLB miss requires a slow walk of the page table in RAM.
 Page Hit: When the CPU requests a virtual address and the corresponding page is
found in physical RAM.
 Page Fault (Page Miss): When the CPU requests a virtual address and the
corresponding page is not in physical RAM. This triggers an exception, and the OS
must:
1. Find a free frame in RAM (or evict an existing page using an algorithm like
LRU).
2. If the evicted page was modified ("dirty"), write it back to the swap space on
the disk.
3. Load the required page from disk into the free frame in RAM.
4. Update the page table.
5. Restart the instruction that caused the fault.
 Types of Virtual Memory:
o Demand Paging: Pages are only loaded into physical memory when they are
demanded by a page fault. This is the standard approach.
o Anticipatory Paging (Prepaging): The OS attempts to predict which pages
will be needed and loads them into memory before they are demanded, trying
to avoid page faults.

21. Explain multiple issue in instruction-level parallelism: static, dynamic, and

speculation.
Multiple Issue is a technique where a processor allows multiple instructions to be
launched in a single clock cycle to be executed in parallel, significantly increasing ILP.
1. Static Multiple Issue (VLIW - Very Long Instruction Word):
o How it works: The compiler analyzes the code, finds independent
instructions, and packs them into a single, very long instruction word. This
"packet" is issued to multiple functional units in the CPU simultaneously.
o Role of Hardware: The hardware is simple; it just executes the packet as
given. The compiler handles dependency checking and scheduling.
 o Challenge: Poor performance if the compiler's predictions are wrong (e.g.,
branch misprediction, cache misses). Requires recompilation for different
architectures.
2. Dynamic Multiple Issue (Superscalar):
o How it works: The processor hardware itself, at runtime, examines the
incoming stream of instructions (the instruction window), checks for
dependencies, and issues multiple independent instructions to functional units
in a single cycle.
o Role of Hardware: The hardware is extremely complex. It includes out-of-
order execution (OoOE) logic, register renaming, and sophisticated hazard
detection units.
o Advantage: It works on standard compiled code and can adapt to runtime
events better than static scheduling.
3. Speculation: This is a technique often used with dynamic multiple issue to overcome
control hazards (branches).
o How it works: The processor guesses the outcome of a branch (e.g., using a
Branch Prediction Buffer) and begins fetching, decoding, and even executing
instructions along the predicted path before the branch condition is even
resolved.
o If correct (speculation success): A huge performance gain is achieved, as
work has already been done.
o If incorrect (speculation failure): The processor must flush all speculatively
executed instructions from the pipeline and restart from the correct branch
path. This incurs a penalty, but the overall gain from correct predictions is
worth it.

22. Explain the concept of multithreading.

Multithreading is a programming and execution model that allows a single process to contain
multiple threads of execution. These threads share the process's resources (like code, data,
and files) but have their own independent flow of control and private stack for local variables
and function call history.
Key Concepts:
 Concurrency: On a single core, the CPU rapidly switches between threads (time-
slicing), creating the illusion of simultaneous execution.
 Parallelism: On a multicore system, threads can truly run simultaneously on different
cores.
  Benefits:
1. Responsiveness: In a GUI application, one thread can handle the user
interface while another performs a long computation, preventing the UI from
"freezing".
2. Resource Sharing: Threads share memory by default, making data sharing
efficient and fast.
3. Economy: Creating a thread is much faster and requires fewer OS resources
than creating a new process.
4. Utilization: It efficiently utilizes multiprocessor and multicore architectures.
Types (from a hardware perspective):
 Fine-Grained: switches between threads after every instruction (not common).
 Coarse-Grained: switches on a long-latency event (e.g., a cache miss). Reduces
stalling.
 Simultaneous Multithreading (SMT) / Hyper-Threading: A technique on
superscalar processors that allows multiple threads to be issued to the execution
units in the same cycle, treating a single physical core as multiple logical cores. It
maximizes the utilization of the core's execution resources.