Q1. What is parallel processing? How does it differ from sequential processing?

Answer (5–7 Marks):

Parallel Processing refers to the simultaneous use of multiple processing units (cores or processors)
to execute different parts of a program or multiple programs at the same time. It aims to reduce the
execution time and improve system performance by dividing tasks into subtasks that can be
processed concurrently.

Sequential Processing, in contrast, executes one instruction at a time on a single processor. Even if
tasks are independent, they are executed one after the other.

Key Differences:

Aspect Sequential Processing Parallel Processing

Execution One task at a time Multiple tasks simultaneously

Performance Slower for large tasks Faster with task division

Scalability Limited High (with more processors)

Example Traditional single-core CPU Multi-core CPU, GPU, Cluster

Parallel processing is essential in modern computing for handling large data sets, scientific
simulations, and real-time applications.

Q2. Explain different types of parallelism in sequential machines.

Answer (5–7 Marks):

Sequential machines can exhibit several forms of parallelism even though they appear to execute
instructions one after another:

1. Instruction-Level Parallelism (ILP):

o Multiple independent instructions can be executed simultaneously within a single

CPU cycle.

o Achieved through pipelining, superscalar execution, and out-of-order execution.

2. Data-Level Parallelism (DLP):

o Same operation is applied to multiple data items (e.g., using SIMD instructions).

o Common in multimedia and scientific applications.

3. Task-Level Parallelism (TLP):

o Independent tasks or threads run concurrently.

o Enabled through multithreading or multitasking.

Conclusion: Even in single-core CPUs, these techniques improve utilization and execution speed by
exploiting various forms of hidden parallelism.
 Q3. Describe the abstract model of a parallel computer.

Answer (5–7 Marks):

The abstract model of a parallel computer is a theoretical framework used to understand and design
parallel systems. It simplifies the architecture into key components:

1. Processing Elements (PEs):

o Multiple CPUs or cores capable of executing tasks independently or cooperatively.

2. Memory Modules:

o Can be shared (global memory) or distributed (each processor has local memory).

3. Interconnection Network:

o Allows communication among processors and memory modules (e.g., buses,

crossbars, meshes).

4. Control Unit:

o May be centralized or distributed, coordinates instruction flow and synchronization.

Models include:

• PRAM (Parallel Random Access Machine)

• Distributed Memory Model

• Shared Memory Model

These abstract models are used to design algorithms and analyze performance in a hardware-
agnostic manner.

Q4. What are the different types of multiprocessor architectures?

Answer (5–7 Marks):

Multiprocessor architectures can be categorized based on memory sharing and interconnect design:

1. Shared Memory Multiprocessor (UMA):

• All processors access the same global memory.

• Easy programming model.

• Example: Symmetric Multiprocessing (SMP).

2. Distributed Memory Multiprocessor:

• Each processor has its own local memory.

• Communication via message passing.

• Example: Clusters, MPPs.

3. Non-Uniform Memory Access (NUMA):

• Hybrid model where memory is physically distributed but logically shared.

• Processors access local memory faster than remote memory.

4. Hybrid Architectures:

• Combine shared and distributed features.

• Example: Multicore systems with shared L2 cache and local L1.

Selection depends on performance goals, scalability, and application requirements.

Q5. Explain pipelining in computer architecture.

Answer (5–7 Marks):

Pipelining is a technique where instruction execution is divided into stages, and multiple instructions
are processed simultaneously at different stages, improving CPU throughput.

Typical 5-stage pipeline:

1. Instruction Fetch (IF)

2. Instruction Decode/Register Fetch (ID)

3. Execute (EX)

4. Memory Access (MEM)

5. Write Back (WB)

Advantages:

• Increases instruction throughput.

• Efficient use of CPU components.

• Reduces instruction latency per cycle.

Challenges:

• Hazards:

o Data hazards (RAW, WAR, WAW)

o Control hazards (branches)

o Structural hazards (resource conflicts)

Resolution: Forwarding, stalling, branch prediction.

Conclusion: Pipelining boosts performance but requires sophisticated control logic to handle
hazards.
 Q6. What are array processors? How do they work?

Answer (5–7 Marks):

An array processor is a type of SIMD architecture designed to perform the same operation on
multiple data items simultaneously.

Key Features:

• Multiple Processing Elements (PEs) arranged in 1D or 2D arrays.

• Single Control Unit broadcasts instructions to all PEs.

• Data is distributed to each PE which operates in parallel.

Types:

1. Attached Array Processor: Auxiliary to host CPU.

2. SIMD Array Processor: Independent unit; executes data-parallel programs.

Applications:

• Image and signal processing.

• Matrix operations.

• Scientific computing.

Advantages:

• High throughput for data-parallel workloads.

Limitations:

• Less effective for irregular or control-intensive tasks.

Q7. Define Flynn’s Taxonomy. List and explain its categories.

Answer (5–7 Marks):

Flynn’s Taxonomy classifies computer architectures based on the number of instruction and data
streams:

Category Instruction Stream Data Stream Example

SISD 1 1 Traditional CPU

SIMD 1 Many GPU, array processor

MISD Many 1 Fault-tolerant systems

MIMD Many Many Multicore CPUs, clusters

Explanation:

• SISD: Executes one instruction on one data at a time.

 • SIMD: Executes one instruction on multiple data streams (data-parallel).

• MISD: Executes multiple instructions on the same data (rare).

• MIMD: Most flexible; each processor executes different instructions on different data.

Importance: Helps in understanding system capabilities and matching applications to suitable

architectures.

Q8. What is instruction-level support for parallel programming?

Answer (5–7 Marks):

Instruction-level support refers to hardware features in modern CPUs that exploit parallelism
between individual instructions.

Types of support:

1. Pipelining: Overlaps instruction stages.

2. Superscalar Execution: Executes multiple instructions per cycle using multiple ALUs.

3. Out-of-Order Execution: Executes independent instructions out of program order to reduce

stalls.

4. Branch Prediction: Predicts outcomes to avoid control hazards.

5. Vector Instructions (SIMD): AVX, SSE enable data-parallel operations.

6. Register Renaming: Avoids false dependencies.

Benefits:

• Boosts performance of single-threaded programs.

• Reduces idle CPU cycles.

• Enhances compiler optimization opportunities.

Q9. What are multiprocessor caches and how does cache coherence become an issue?

Answer (5–7 Marks):

Multiprocessor caches refer to local caches maintained by each processor in a multiprocessor system
to reduce memory access latency.

Cache Coherence Problem:

Occurs when multiple caches hold copies of the same memory location. A write by one processor can
cause stale data in other caches.

Example:

If P1 updates variable X, but P2 reads old value from its cache, inconsistency arises.
Protocols to maintain coherence:

• Write-invalidate: Invalidate other caches' copies.

• Write-update: Update other caches with the new value.

• MESI protocol: Uses states (Modified, Exclusive, Shared, Invalid) to track cache line validity.

Coherence ensures correctness and consistency across processor views of memory.

Q10. Explain Cache Coherence and outline basic protocols to maintain it.

Answer (5–7 Marks):

Cache Coherence ensures that multiple copies of shared data in processor caches reflect the most
recent updates.

Problem:

In multiprocessor systems, if one CPU modifies a cached value, others must not read stale data.

Coherence Protocols:

1. Write-Invalidate Protocol:

o Writer invalidates copies in other caches.

o Readers must fetch fresh data.

2. Write-Update Protocol:

o Updates propagated to all caches holding the data.

o Higher communication overhead.

3. MESI Protocol:

o Cache lines are in one of four states:

▪ Modified

▪ Exclusive

▪ Shared

▪ Invalid

o ManagesThanks for your patience! Continuing with the long-form 5–7 mark answers
for the remaining questions from your Module I of Parallel and Distributed
Computing (DJSCE) syllabus:

Q11. What is NUMA? How is it different from UMA?

Answer (5–7 Marks):

NUMA (Non-Uniform Memory Access) is a computer memory design where the memory access
time depends on the memory location relative to the processor. Each processor has its local memory
and may also access remote memory (memory local to other processors), but with higher latency.

Key Characteristics of NUMA:

• Improves scalability over UMA.

• Allows memory locality to be optimized.

• Used in high-performance multicore systems and servers.

Comparison with UMA:

Feature UMA NUMA

Memory Access Time Uniform for all processors Varies (local is faster than remote)

Memory Architecture Single shared memory Multiple memory modules (per node)

Scalability Limited High scalability

Performance Degrades with more processors Scales better with workload

Programming Model Simple Complex (needs locality-aware programming)

Conclusion: NUMA is essential in large-scale systems to reduce contention and improve memory
access efficiency, although it requires more careful memory management.

Q12. Compare UMA and NUMA architectures.

Answer (5–7 Marks):

UMA (Uniform Memory

Criteria NUMA (Non-Uniform Memory Access)
Access)

Depends on memory location (local vs.

Memory Access Time Equal for all processors
remote)

Memory Multiple memories, each closer to one

Single shared memory
Organization processor/group

Communication Cost Low, centralized Higher, inter-node communication required

Poor scalability as processors

Scalability Highly scalable, better for large systems
increase

Hardware Cost Lower Higher (due to interconnect and complexity)

Programming Easy to implement and More complex (needs memory locality

Simplicity program management)
 UMA (Uniform Memory
Criteria NUMA (Non-Uniform Memory Access)
Access)

High-end servers, AMD EPYC, Intel Xeon

Examples Small SMP systems
NUMA setups

Conclusion: UMA is suitable for small multiprocessor systems, while NUMA is ideal for scalable, high-
performance systems needing efficient local memory access.

Q13. What are the advantages and disadvantages of pipelining?

Answer (5–7 Marks):

Advantages:

1. Increased Throughput: Multiple instructions are in execution simultaneously.

2. Efficient CPU Utilization: Components like ALUs and memory units are better utilized.

3. Faster Execution: Even though individual instruction time remains similar, overall time for a
set of instructions reduces.

Disadvantages:

1. Pipeline Hazards:

o Data Hazards: Arise from instruction dependencies.

o Control Hazards: Due to branches and jumps.

o Structural Hazards: Limited resources shared by stages.

2. Complex Control Logic: Managing hazards, stalling, forwarding adds design complexity.

3. Stalling and Flushing: Reduces performance when prediction or dependency fails.

4. Non-uniform Instruction Time: Not all instructions take equal time; causes imbalance.

Conclusion: Pipelining is an effective performance booster, but its efficiency depends on workload,
instruction mix, and hazard resolution mechanisms.

Q14. What are the challenges in designing multiprocessor systems?

Answer (5–7 Marks):

Designing multiprocessor systems presents various hardware and software challenges, including:

1. Cache Coherence:

o Ensuring consistent data among multiple caches.

o Requires protocols like MESI, MOESI.

2. Synchronization Overhead:
 o Managing locks, semaphores, and barriers.

o Delays due to waiting on shared resources.

3. Memory Access Bottlenecks:

o Shared memory becomes a performance bottleneck if not properly managed.

o Requires strategies like memory interleaving, NUMA.

4. Scalability:

o Performance gains diminish with increasing processors.

o Overheads from interconnects and synchronization increase.

5. Load Balancing:

o Equal distribution of tasks is non-trivial.

o Imbalance leads to some processors being idle.

6. Communication Overhead:

o Inter-processor communication can slow down execution, especially in distributed

memory systems.

7. Complex Programming Model:

o Developers must write code that handles concurrency, synchronization, and memory
sharing.

Conclusion: Efficient multiprocessor design requires balanced hardware and software strategies to
overcome these challenges.

Q15. How does Flynn’s taxonomy help in classifying parallel architectures?

Answer (5–7 Marks):

Flynn’s Taxonomy provides a high-level classification of computer architectures based on how

instructions and data streams are handled. This classification helps in understanding the type of
parallelism supported by an architecture and guides both hardware designers and software
developers.

Categories:

1. SISD: Single instruction, single data — Traditional sequential computers.

2. SIMD: Single instruction, multiple data — Ideal for data-parallel operations.

3. MISD: Multiple instruction, single data — Rare, used in fault-tolerant systems.

4. MIMD: Multiple instruction, multiple data — Most general and widely used in
multiprocessors, clusters.

Usefulness:
 • Helps choose the appropriate system architecture based on the problem domain.

• Guides the development of parallel programming models (e.g., data parallel vs task parallel).

• Aids in hardware design decisions (e.g., need for shared memory, interconnects).

Conclusion: Flynn's taxonomy simplifies the understanding and selection of parallel systems, forming
a foundation for both theoretical and practical work in parallel computing.

Question 1

“Explain Flynn’s Taxonomy. For each category, give examples, benefits and limitations.”

Model Answer (≈ 5-7 marks)

Flynn’s Taxonomy classifies parallel computer architectures based on two dimensions: the number of
instruction streams and the number of data streams. It defines four categories:

Instruction Data Example

Taxonomy Benefits Limitations
Streams Streams Architectures

SISD (Single Simple control, Very limited

Traditional
Instruction, 1 1 easier programming; parallelism; slower for
uniprocessor CPUs
Single Data) less overhead large problems

High throughput for

SIMD (Single data-parallel tasks; Less flexible; not
Vector processors;
Instruction, efficient use of suited for divergent
1 Many GPUs; array
Multiple hardware for same control flow; wasteful
processors
Data) operations over if data isn’t regular
large data

Rare; used in
fault-tolerant
systems (e.g.,
MISD multiple Can offer reliability; Very limited practical
(Multiple processors redundant use; inefficiency;
Many 1
Instruction, performing computations for complexity; few
Single Data) different fault detection implementations
operations on
same data stream
for redundancy)

Most flexible; More complex

MIMD
Multicore CPUs, supports both task hardware and
(Multiple
clusters, and data parallelism; programming; issues
Instruction, Many Many
distributed scalable; used for of synchronization,
Multiple
systems general-purpose communication
Data)
parallel computing overhead; irregular
 Instruction Data Example
Taxonomy Benefits Limitations
Streams Streams Architectures

data access patterns

reduce efficiency

Additional discussion:

• Flynn’s taxonomy helps in choosing architecture suited to algorithm type.

• Many modern systems are MIMD (sometimes with SIMD units internally) to balance
flexibility and performance.

Question 2

“Discuss pipelining in computer architecture: its stages, hazards, and how hazards are resolved.”

Model Answer (≈ 5-7 marks)

Pipelining is a technique to overlap instruction execution by dividing the execution path into multiple
stages, so multiple instructions are in different stages at the same time (like an assembly line). This
increases throughput (instructions per unit time), though latency per instruction may remain roughly
the same.

Key Pipeline Stages (typical 5-stage pipeline):

1. Fetch (IF) – fetch the instruction from memory.

2. Decode / Register Fetch (ID) – decode the instruction, read source operands.

3. Execute (EX) – perform arithmetic/logical operations or compute address.

4. Memory Access (MEM) – read/write data from/to memory if required.

5. Write Back (WB) – write result back into register.

Hazards in Pipelining

1. Structural Hazards – when hardware resources are insufficient to support all stages
simultaneously (e.g., single memory port used by instruction fetch and data access).

2. Data Hazards – when instructions depend on the results of previous instructions which are
not yet completed. Types: RAW (read after write), WAR, WAW.

3. Control Hazards – from branch instructions or jumps: fetching wrong instructions before
branch resolution.

Hazard Resolution Techniques

 • Structural Hazards: provision more hardware (e.g. separate instruction and data caches,
multiple functional units).

• Data Hazards:

o Forwarding / Bypassing: pass result directly from one stage to another without
writing back to register.

o Stalling / Pipeline Interlock: insert NOPs until data becomes available.

o Out-of-order execution: reorder instructions dynamically to avoid stalls.

• Control Hazards:

o Branch prediction: predict the branch outcome to fetch correct instructions ahead of
time.

o Delayed branching: schedule instructions in branch delay slots.

o Flush the pipeline: discard wrong path instructions when branch resolves.

Conclusion: Pipelining improves throughput significantly but introduces complexity in control and
data hazard handling. In exam settings you might get asked to draw a pipeline diagram and mark
where hazards happen, and explain a forwarding path or stall.

Question 3

“Define cache coherence in multiprocessor systems. Explain one protocol (e.g. MESI) in detail,
discussing how it ensures coherence.”

Model Answer (≈ 5-7 marks)

Definition:
Cache coherence refers to the consistency of data stored in local caches of a multiprocessor system.
When multiple processors cache copies of the same memory location, coherence ensures that any
read returns the most recent write, regardless of which cache performed that write.

Why it’s needed:

• Without coherence, a processor may read stale data from its cache while another processor
has updated the main memory or its own cache.

• Shared variables in parallel programs require consistent visibility to all processors.

MESI Protocol: A commonly used coherence protocol with four states per cache line:

• M = Modified: Cache line is dirty (modified), only this cache has the valid copy; main memory
is stale.

• E = Exclusive: Cache line is clean, only this cache has the copy; memory and cache are same.
 • S = Shared: Multiple caches may have this line, but all are clean; all have the same value.

• I = Invalid: Line is not valid in this cache.

Transitions / Operations:

On Write to On Read Hit / Write Hit

Operation On Read Miss On Write Miss
Shared (depending on state)

From I to If no other copy → → M, invalidating

N/A —
... E; else → S others

→ M, send Read Hit → stay S; Write

From S to
Hit → stay S invalidations to — Hit → send invalidations,
...
other caches move to M

From E to Write → go to M
Read Hit → stay E — —
... (silent upgrade)

Read Hit → stay M, Other read miss

From M to
but may supply Write Hit → stay M → change to S; —
...
data to others supply data

How coherence is maintained:

• Invalidate vs Update: On a write in shared state, other caches’ copies are invalidated.

• Bus or interconnect messages are used to propagate invalidations or updates.

• Ensures any subsequent read anywhere sees either the updated value or waits until the
write completes.

Limitations / overheads:

• Communication overhead with invalidations or updates (bus traffic).

• False sharing: unrelated data in same cache line causing unnecessary invalidations.

• Complexity in large scale systems.

Question 4

“What is NUMA architecture? Describe its characteristics, advantages and disadvantages. Compare
NUMA with UMA.”

Model Answer (≈ 5-7 marks)

Definition:
NUMA – Non-Uniform Memory Access architecture: A design in which memory access time depends
on the memory’s physical location relative to a processor. Processors have faster access to their local
memory and slower access to memory local to other processors.

Characteristics:

• Processors divided into nodes; each node has its own local memory.

• Interconnection network links nodes; remote memory access involves inter-node

communication.

• Cache coherence protocols may need to account for locality.

• Used in large multiprocessor / multicore systems (servers, high-performance computing).

Advantages:

1. Scalability: More processors can be added without a single memory controller becoming a
bottleneck.

2. Memory bandwidth: Combined bandwidth from all local memories increases total
throughput.

3. Locality optimizations: Data and processes can be scheduled to maximize local memory use,
improving speed.

Disadvantages:

1. Non-uniform latency: Remote memory access can be significantly slower, complicating

performance prediction.

2. Complexity in programming: Requires awareness of data placement and access patterns.

3. Cache coherence overheads: Maintaining consistency across nodes adds communication

overhead.

4. Uneven workload performance: If many accesses go to remote memory, performance

degrades.

Comparison with UMA (Uniform Memory Access):

Feature UMA NUMA

Memory Access Uniform for all processor-memory

Varies (local < remote)
Latency pairs

Lower; single memory bus or Higher; distributed local memories reduce

Scalability
controller tends to be bottleneck central bottleneck
Feature UMA NUMA

Memory Limited by shared bus/memory Higher aggregate bandwidth using local

Bandwidth bandwidth memories

Programming Simpler model; less concern More complex; must consider locality,
Complexity about data placement possible migration of data

More complex interconnect; more hardware

Cost / Hardware Simpler; cheaper interconnects
overhead to maintain coherence and handle
Complexity required
remote accesses

Question 5

“What are array processors? Describe their architecture, applications and contrast with pipelined
processors.”

Model Answer (≈ 5-7 marks)

Definition:
An array processor is a specialized processor architecture that executes a single instruction across
multiple data elements simultaneously (i.e. SIMD – Single Instruction Multiple Data). It comprises
multiple processing elements (PEs) under a common control.

Architecture:

• A control unit broadcasts instructions to all PEs.

• Each PE has its own ALU (Arithmetic Logic Unit) and often its own local register set.

• Data paths allow data to be distributed to/from these PEs.

• Often arranged in vector form, or 1-D/2-D arrays.

Applications:

• Image processing (filtering, transforms) – same operation over many pixels.

• Scientific computing – matrix operations, solving systems of linear equations.

• Signal processing – e.g. FFT, convolution.

• Graphics, simulations.

Contrast with Pipelined Processors:

Aspect Array Processors (SIMD) Pipelined Processors

Data parallelism over multiple data Instruction-level parallelism – overlapping

Parallelism Type
elements simultaneously phases of different instructions

Control More complex: handling hazards,

Simple: one control unit for all PEs
Complexity out-of-order execution, branch prediction

Less flexible: operations are uniform More flexible: different instructions can be
Flexibility
across all data elements in different pipeline stages

Excellent for regular, homogeneous Better for mixed or general purpose tasks
Suitability
tasks with control flow changes

Improves instruction latency and

Throughput vs High throughput for large data sets;
throughput for general instruction
Latency latency per datum might be high
sequences

Question 6

“What is instruction-level support for parallel programming? Discuss types of support provided by
modern processors.”

Model Answer (≈ 5-7 marks)

Definition:
Instruction-level support for parallel programming refers to hardware features that allow multiple
instructions to be processed in parallel or overlapping fashion, speeding up program execution even
on a single processor.

Types of support include:

1. Pipelining: As discussed earlier; overlapping of instruction fetch, decode, execute etc.

2. Superscalar Execution: The ability to issue several instructions per clock cycle to multiple
functional units, provided they are independent.

3. Out-of-Order Execution: The processor reorders instruction execution to minimize stalls (e.g.
when waiting for operand availability).

4. Speculative Execution / Branch Prediction: Predicting the outcome of branches to keep

pipeline full; rollback if prediction wrong.

5. Vector / SIMD Instructions: Special instructions (e.g. SSE, AVX in x86) operating on vectors or
multiple data elements in parallel.

6. Register Renaming: Avoids false dependencies (WAR, WAW) by giving separate physical
registers.

7. Hardware Multithreading / Simultaneous Multithreading (SMT): Processor handles

instructions from multiple threads in parallel to better utilize functional units.
Impact:

• Improves instruction throughput.

• Helps hide latencies (memory, branch).

• Increases hardware complexity and energy usage.

• Requires compiler support (to schedule instructions, detect parallelism).

Question 7

“Define a multiprocessor architecture. Explain the challenges in designing multiprocessor caches

and coherence.”

Model Answer (≈ 5-7 marks)

Definition:
A multiprocessor architecture is a computer system with more than one processor (or core) that
share (or partially share) memory and other resources, and execute tasks either cooperatively or
independently.

Types:

• Uniform Memory Access (UMA) multiprocessors

• Non-Uniform Memory Access (NUMA) systems

• Clusters of processors with distributed or shared memory.

Challenges with multiprocessor caches and coherence:

1. Cache Coherence: Ensuring that multiple caches which might hold copies of the same
memory location keep them consistent. If one writes, others must see that write. Protocols
like MESI, MOESI are used, but they introduce overhead.

2. False Sharing: Two processors access different variables that reside on the same cache line
→ unnecessary invalidations. It degrades performance.

3. Granularity of Coherence: Deciding the size of cache block (line); smaller lines reduce false
sharing but increase overhead; larger lines improve bandwidth but can increase unwanted
sharing.

4. Synchronization Overheads: Locks, barriers require communication; may stall processors

waiting for coherence messages.

5. Scalability of Coherence Protocols: As number of processors increases, overhead for

maintaining coherence (bus traffic or interconnect messages) grows; bus contention, delays.
 6. Memory Consistency Models: Definition of when writes by one processor become visible to
others. Consistency models (e.g. sequential consistency, relaxed consistency) affect
programming model and hardware design.

Conclusion:
Multiprocessor architectures deliver performance gains but dealing with caching and coherence is
central to achieving practical speed-ups. Designers must balance complexity, communication cost,
and consistency guarantees.