Assignment -2

1. Define PRAM model.

A PRAM (Parallel Random-Access Machine) model is an abstract theoretical model used in
the field of parallel computing to analyze and describe the behavior of parallel algorithms.
It simplifies the study of parallel algorithms by assuming an idealized parallel computer
with shared memory.
Key characteristics of the PRAM model:

1. Processors: The PRAM model assumes that there are a fixed number of processors,
each with its own unique identifier. These processors operate concurrently.

2. Memory: In PRAM, there is a single, global shared memory that all processors can
access. This memory is often divided into cells, and each cell can be read from and written
to in constant time (i.e., in O (1) time).

3. Parallel Operations: PRAM abstracts the execution of parallel algorithms by specifying

the order in which processors access memory. There are several variants of PRAM
models, including CREW (Concurrent Read Exclusive Write), EREW (Exclusive Read
Exclusive Write), and CRCW (Concurrent Read Concurrent Write), each of which imposes
different constraints on memory access.

4. Synchronization: In PRAM, processors operate without communication delays or

contention for memory access, which simplifies the analysis but doesn't reflect the real-
world complexities of parallel computing systems.

PRAM models help computer scientists and researchers analyse and classify parallel
algorithms based on their efficiency, particularly in terms of time complexity and
scalability. However, it's important to note that PRAM models are idealized abstractions
and do not account for real-world factors like communication overhead, contention for
shared resources, or load balancing. Nevertheless, they serve as valuable tools for
understanding the theoretical limits of parallel algorithm efficiency.

2. Explain Pipelined processor in detail

A pipelined processor is a concept in parallel computing and computer architecture
where the execution of instructions is divided into a series of stages, and each stage is
performed concurrently by a different part of the processor. This allows for the
overlapping of multiple instructions in their execution, improving overall throughput and
performance. Here's a detailed explanation of a pipelined processor:

- In a pipelined processor, the execution of an instruction is broken down into

several stages, such as instruction fetch, decode, execute, memory access, and
write-back.
 - Each stage is carried out by a dedicated component of the processor, often referred to
as a pipeline stage or a pipeline segment.
 Stages of a Pipeline:
The exact stages in a pipelined processor can vary, but they typically include
the following:
- Fetch: The instruction is fetched from memory or cache.
- Decode: The instruction is decoded to determine the operation to be performed.
- Execute: The actual computation or operation is performed.
- Memory: If necessary, memory operations like reading or writing data occur.
Write-back: The results of the instruction are written back to registers or memory.

 Parallel Execution - Pipelining allows for multiple instructions to be in various

stages of execution simultaneously. For example, while one instruction is being
executed, the next instruction can be decoded, and the one after that can be
fetched.
- This overlapping of instruction execution improves throughput, making the
processor more efficient.
 Hazards - While pipelining enhances performance, it can introduce hazards,
which are situations that may stall or cause delays in the pipeline. Common
types of hazards include:
- Data Hazard: Occurs when an instruction depends on the result of a previous
instruction that is still in the pipeline.
- Control Hazard: Arises due to branch instructions or other control flow changes
that affect the order of instruction execution.
- Structural Hazard: Happens when there is a resource conflict, such as two
instructions competing for the same execution unit.

 Pipeline Registers: - To facilitate communication between pipeline stages,

pipeline registers are used. These are temporary storage locations where data
or instructions are passed from one stage to the next.

 Instruction Throughput: - The throughput of a pipelined processor can be

much higher than that of a non-pipelined processor. This is because new
instructions can enter the pipeline before previous instructions have
completed their execution.
  Examples - Modern microprocessors, including CPUs in desktops, laptops, and
mobile devices, commonly employ pipelining to achieve high performance. They
often have deeper and more complex pipelines to handle a wider range of
instructions.

 Variations:- Pipelines can vary in depth (the number of stages) and complexity
based on the specific architecture and performance goals. Some processors have
multiple instruction pipelines to handle different types of instructions
simultaneously.

 Trade-offs:- While pipelining significantly boosts performance, it may introduce

complexity and may not always be beneficial. Extremely deep pipelines can also
increase the penalty for pipeline stalls, making efficient handling of hazards
crucial.

3. Define processor organization-static and dynamic

interconnection.
In parallel computing, processor organization refers to how multiple processors
are interconnected within a parallel computer or system. Two common types of
processor organization are static interconnection and dynamic interconnection:

1. Static Interconnection: Static interconnection is a fixed and

predetermined arrangement of processors and communication links in a
parallel system. The configuration remains constant throughout the
operation of the system.

Characteristics:-Topology: Static interconnections often use fixed topologies,

such as meshes, hypercube, or tori. These topologies determine the physical
arrangement of processors and their connections.

Predictability: The connections between processors are known in advance and do

not change during the operation of the system

Low Overhead: Static interconnection typically results in lower communication

overhead because the routing paths are well-defined.

Advantages: - Static interconnections can be highly efficient for specific workloads

that can benefit from their fixed topologies.
- They are often used in supercomputers and high-performance computing clusters.
Disadvantages: - Limited flexibility: It can be challenging to adapt to changing
workloads or fault tolerance requirements.
- Scalability issues: Expanding a system with static interconnections may be complex.
2. Dynamic Interconnection: Dynamic interconnection allows for the reconfiguration of
processor connections during the operation of the parallel system. It provides
flexibility in managing communication paths based on application needs.

Characteriss:
Configurability: Dynamic interconnections enable the system to adapt to changing
workloads or fault conditions by reconfiguring connections.

Higher Overhead: Because connections can change, dynamic interconnections may

introduce higher communication overhead due to the need for dynamic routing
decisions.

Flexibility: Systems with dynamic interconnections can be more versatile and capable of
handling various workloads.

Advantages:
- Dynamic interconnections are more adaptable to evolving workloads and can
optimize communication paths for specific tasks.
- They are useful in systems where fault tolerance or load balancing is

critical

Disadvantages:

- Complexity: Dynamic interconnections often require more sophisticated

hardware and software for managing the reconfiguration process.
- Increased overhead: The dynamic nature of interconnections can
introduce communication overhead.

4. Explain loop scheduling.

Loop scheduling in parallel computing refers to the process of dividing and
distributing the iterations of a loop among multiple processors or threads to enable
parallel execution. This technique is commonly used to exploit parallelism in
programs that contain loops, which are a fundamental construct in many
algorithms and applications. Loop scheduling aims to balance the workload among
processors and optimize performance. There are several loop scheduling strategies,
including:

1. Static Loop Scheduling- In static loop scheduling, the iterations of the loop are divided
into chunks, and each processor is assigned a chunk of iterations to execute.
- The division of work is done at the beginning of the computation, and each
processor knows its assigned chunk of iterations in advance.
 - Static scheduling is straightforward to implement, but it may not adapt well to
varying workloads or unevenly distributed work.
2 .Dynamic Loop Scheduling- Dynamic loop scheduling involves dividing the loop
iterations at runtime as processors become available for execution.
- A work queue or a task queue is used to manage the iterations, and processors
request work from this queue as they become idle.
- Dynamic scheduling can help balance the workload more effectively, especially in
cases where the workload of each iteration varies.

3. Guided Loop Scheduling- Guided loop scheduling is a hybrid approach that

combines features of static and dynamic scheduling.
- It starts with static scheduling but gradually reduces the chunk size for each processor
as the loop progresses.
This approach allows for load balancing while avoiding the overhead of fine-grained
dynamic scheduling
4. Chunk-Based Loop Scheduling - In chunk-based scheduling, the iterations are grouped
into chunks, and processors are assigned complete chunks rather than individual
iterations.
- This approach reduces the scheduling overhead, making it more efficient for loops
with a large number of iterations.

5. Cyclic Loop Scheduling - Cyclic scheduling assigns iterations to processors in a cyclic

or round-robin manner.
- Each processor is assigned one iteration at a time in a circular fashion.
- This approach can be useful for load balancing when iterations have varying
execution times.

[Link] Parallelism- Task parallelism extends the concept of loop scheduling to a

more general framework where tasks, not just loop iterations, are scheduled for
parallel execution.
- Task-based parallelism allows for greater flexibility in structuring parallel applications and
distributing work.