PART-A (9×2 = 18 MARKS)
1. What is the purpose of multi-core integrated circuits?
→ To increase performance and efficiency by allowing multiple processors (cores) to
execute tasks concurrently, improving multitasking and parallel processing.
2. List of problems considering the increases in performance of multicore
architectures?
→
o Increased complexity in parallel programming
o Difficulty in achieving load balancing
o Cache coherence issues
o Memory bandwidth bottlenecks
o Debugging and synchronization challenges
3. Why do we need to write parallel programs?
→ To utilize the full potential of multicore processors by executing tasks
concurrently, thereby reducing execution time and improving performance.
4. What are the two extensions to shared memory?
→
o Distributed shared memory (DSM)
o Non-uniform memory access (NUMA)
5. Define Von Neumann Architecture.
→ A computer architecture where the CPU, memory, and I/O share a common bus
and memory stores both data and instructions.
6. Define Multitasking.
→ The ability of a CPU to execute multiple tasks (processes) concurrently by rapidly
switching between them.
7. Define Cache Miss and Cache Hit.
→
o Cache Hit: When the requested data is found in the cache.
o Cache Miss: When the requested data is not in the cache and must be fetched
from main memory.
8. Define Fully Associative Cache.
→ A cache structure where a block can be placed in any cache line, offering
maximum flexibility and lower miss rates.
9. What is Virtual Memory?
→ A memory management technique that uses disk space as an extension of RAM,
allowing execution of processes that require more memory than physically available.
1. Explain in detail the SIMD and MIMD systems. (16
Marks)
1.1 Introduction
Parallel computer architectures aim to improve computational performance by allowing
simultaneous execution of tasks. Two fundamental classifications based on Flynn’s taxonomy
are:
SIMD (Single Instruction, Multiple Data)
MIMD (Multiple Instruction, Multiple Data)
1.2 SIMD Architecture
Definition:
SIMD is an architecture where a single instruction is applied to multiple data points
simultaneously. It’s especially efficient for performing the same operation on large data sets.
Working Principle:
A single control unit issues the same instruction to multiple processing elements
(PEs).
Each PE operates on a different piece of data.
Useful for operations that require the same computation across multiple data values.
Example:
Image processing where each pixel undergoes the same transformation.
Vector processors like Intel AVX, SSE
GPUs use SIMD for shading and rendering
Advantages:
Simple control flow
Reduced instruction fetching overhead
Highly efficient for regular data-parallel tasks
Disadvantages:
Inefficient for tasks with conditional branching
Not suitable for irregular or diverse data sets
1.3 MIMD Architecture
Definition:
MIMD architecture allows multiple processors to execute different instructions on different
data simultaneously.
Working Principle:
Each processor functions independently.
Can execute different programs or threads concurrently.
Supports both task-level and instruction-level parallelism.
Example:
Multi-core CPUs running different threads of a program
Distributed computing systems like clusters and grids
Advantages:
High flexibility and performance
Suitable for general-purpose computing
Scalable and supports asynchronous operations
Disadvantages:
Complex synchronization and communication
Harder to program and debug
1.4 Comparison Table
Feature SIMD MIMD
Instruction Stream Single Multiple
Data Stream Multiple Multiple
Parallelism Type Data-level Task-level
Synchronization Simple Complex
Applications Image/video processing Operating systems, databases
1.5 Conclusion
SIMD is best suited for tasks that require the same operation over large data sets, while
MIMD offers flexibility and power for running diverse tasks concurrently. Understanding
their differences is essential for designing efficient parallel systems.
2. Explain in detail the symmetric memory architecture
and distributed memory architecture. (16 Marks)
2.1 Introduction
Memory architecture significantly affects how data is accessed and processed in
multiprocessor systems. The two widely used models are:
Symmetric Memory Architecture (SMA)
Distributed Memory Architecture (DMA)
2.2 Symmetric Memory Architecture (SMA)
Definition:
Also called Shared Memory Architecture, SMA enables multiple processors to access a
common memory space.
Working:
All processors connect to a shared memory via a bus or crossbar.
Uniform Memory Access (UMA): Each processor has equal access time to memory.
Key Features:
Global address space
Shared communication through memory
Requires cache coherence mechanisms
Advantages:
Easier to program (shared variables, threads)
Efficient communication between processors
Supports multithreading (e.g., OpenMP)
Disadvantages:
Limited scalability due to bus contention
Memory bandwidth bottlenecks
Needs complex cache coherence protocols
Use Cases:
Small-scale SMP systems (servers, desktops)
2.3 Distributed Memory Architecture (DMA)
Definition:
Each processor has its own local memory, and processors communicate using interconnection
networks.
Working:
No shared memory.
Communication via Message Passing Interface (MPI) or similar protocols.
Key Features:
Scalable and suitable for large systems
Memory is physically and logically separate
Advantages:
High scalability
No contention on shared memory
Ideal for parallel computing clusters
Disadvantages:
Complex programming (manual communication)
Higher latency for remote memory access
Difficult debugging
Use Cases:
Supercomputers, HPC clusters (e.g., Blue Gene, Cray)
2.4 Comparison Table
Feature Symmetric Memory (SMA) Distributed Memory (DMA)
Memory Type Shared Private
Communication Implicit via shared memory Explicit message passing
Scalability Limited High
Programming Complexity Low High
Synchronization Requires cache coherence Requires message sync
Examples Multicore desktops, servers Clusters, cloud HPC systems
2.5 Conclusion
Choosing between symmetric and distributed memory architectures depends on system
requirements. SMA is ideal for ease of programming and moderate workloads, while DMA
suits scalable, high-performance applications despite programming complexity.
3. Elaborate Cache Coherence in detail. (16 Marks)
3.1 Introduction
In multicore systems, each processor may have its own cache. Cache coherence ensures that
all caches have a consistent view of shared memory data.
3.2 The Cache Coherence Problem
Occurs when:
Multiple cores have cached copies of the same memory location.
One core updates its cache.
Others may still read outdated values unless notified.
Example:
Core A writes value 20 to variable x.
Core B reads x from its cache (still has old value 10).
Inconsistency arises.
3.3 Goals of Cache Coherence
Ensure that all caches reflect the most recent writes.
Maintain consistency across the system.
Avoid errors in parallel program execution.
3.4 Cache Coherence Protocols
A. Snooping Protocols
Caches snoop (monitor) the shared communication bus.
When one processor updates data, others see the update.
Types:
1. Write Invalidate – Invalidate other caches’ copies when a write occurs.
2. Write Update – Update all copies with new data.
B. Directory-Based Protocols
A central directory keeps track of which cache has copies of a data block.
The directory handles coherence by sending invalidations or updates as needed.
3.5 MESI Protocol (Common Coherence Protocol)
States:
M (Modified): Block is modified and only present in one cache.
E (Exclusive): Block is clean and only in one cache.
S (Shared): Block is unmodified and present in multiple caches.
I (Invalid): Block is invalid.
Example:
1. Core A reads x → moves to Shared
2. Core A writes x → moves to Modified, others move to Invalid
3.6 Importance of Cache Coherence
Prevents data inconsistency in shared-memory systems
Essential for multithreading correctness
Ensures valid and predictable program behavior
3.7 Conclusion
Cache coherence protocols like MESI, MOESI, and directory-based systems are crucial for
ensuring consistency in modern multicore processors. They play a key role in maintaining
synchronization, reliability, and performance in parallel computing environments.