📌 Key Points: Parallel Algorithms and Systems

1. Sequential Algorithm:
o Execution time depends only on input size.
o Runs on a single processor.
2. Parallel Algorithm:
o Execution time depends on:
 Input size,
 Number of processors,
 Processor speed,
 Communication speed between processors.
o Uses multiple processors at the same time.
3. Evaluation Difference:
o Sequential algorithms are evaluated independently.
o Parallel algorithms must be evaluated with respect to the hardware they run on.
4. Parallel System = Algorithm + Architecture
o You must consider both the algorithm and the parallel computer system
(architecture) together.
5. Why Hardware Matters:
o The same algorithm may perform differently on different systems due to varying
hardware capabilities.

Sure! Here's the simplified explanation first, followed by the key points.

📖 Simplified Explanation:

When we try to measure how well a parallel program works, some basic methods are easy to
understand.

The simplest one is checking the wall clock time—just how long the program takes to run from
start to finish.

But this single number (time taken) isn’t enough when we want to:

 Run different sizes of problems,

 Or use more powerful machines with more processors.

Another way to measure performance is to compare the speed of the parallel version to the
serial (non-parallel) version. This shows how much faster we get by using parallelism.
But even this method has some issues. For example:

 What if the serial version is not well optimized, but the parallel version is?
 It might look like we got a big improvement just because the serial version was poor.

Because of such limitations, we need more advanced and reliable performance measures to
understand how a program will perform on bigger machines or with bigger problems.

📌 Key Points for Exam:

1. Wall Clock Time:

o Simple and intuitive measure.
o Shows total time to solve a problem on a given system.
o Not reliable for comparing across different problem sizes or systems.
2. Speedup (Parallel vs. Serial):
o Measures how much faster a parallel version is compared to a serial one.
o Helps show the benefit of using multiple processors.
3. Limitations of Simple Measures:
o Wall clock time doesn't scale well to different systems or problems.
o Speedup can be misleading if the serial version is not optimized.
4. Need for Complex Metrics:
o Advanced performance measures are needed for:
 Predicting how well a program runs on larger systems.
 Handling different problem sizes more accurately.
5. Takeaway:
o Relying only on simple metrics can give a false idea of performance.
o Performance should be analyzed using more detailed and scalable methods.
Sure! Let me break it down into simple words, and then give you key points for exam
preparation based on the image and explanation.

📖 Simplified Explanation:

When we run a program using many processors (parallel programming), we expect it to run
faster. For example, if we double the number of processors, we might hope it runs twice as fast.
But in real life, it’s not that simple, because of different types of overheads (extra time or work
that reduces efficiency).

Here are the main sources of overhead shown in the figure:

1. Inter-process Communication:
o Processors need to talk to each other to share results or data.
o This takes time and is one of the biggest sources of overhead.
o (In the diagram: shown in light gray)
2. Idling:
o Sometimes, some processors are waiting (doing nothing) while others are still
working.
o This happens due to:
 Unbalanced work,
 Waiting for others (synchronization),
 Serial parts in the program.
o (In the diagram: shown in white)
3. Excess Computation:
o The best serial (single-processor) algorithm might be hard to parallelize.
o So we may use a simpler but slower algorithm that works with parallelism.
o This extra or inefficient work is called excess computation.
o (In the diagram: combined with the black part but represents more than what the
serial program would do)

📝 Key Points for Exams:

1. Parallel programs do not always scale linearly (e.g., 2x processors ≠ 2x speed) due to
overheads.
2. Sources of Overhead in Parallel Programs:
o Inter-process Communication: Time spent in sharing data between processors.
o Idling: Processors waiting because of load imbalance, synchronization, or serial
parts.
o Excess Computation: Using less-efficient algorithms just because they can be
parallelized.
3. Execution Time Components (as seen in the figure):
 o Essential/Excess Computation: Work being done (black).
o Communication Overhead: Data exchange time (gray).
o Idle Time: Waiting time (white).
4. Understanding overhead is important for improving the performance of parallel
programs.
5. Load Imbalance: When some processors do more work than others, causing idling.
6. Performance Optimization: Means reducing communication, minimizing idle time,
and choosing better parallel algorithms.

Great question! Here's the main point of the discussion:

⭐ Main Point:

Parallel programs are not always faster just because more processors are used.
They face different kinds of overheads—extra time and work—that reduce performance.

To build efficient parallel programs, it's important to understand and reduce these overheads:

 Communication between processors,

 Idle time (when processors wait),
 And extra or inefficient work (excess computation).

Understanding these factors helps us design better parallel systems that make the best use of
available hardware. Nm m m
Granularity in Parallel Computing Explained Simply
Let me break down what these slides are saying about granularity in parallel computing:

What is Granularity?

Granularity refers to how much work each processor handles. "Coarse granularity" means each
processor does larger chunks of work, while "fine granularity" means smaller chunks.

Key Points:

1. Practical Approach: Instead of giving each processor tiny bits of work, we often assign
larger chunks (increasing granularity).
2. Scaling Down: Sometimes we don't use all available processors - this is called "scaling
down." For example, if you have 100 tasks but use only 50 processors (instead of 100),
each processor handles 2 tasks.
3. Virtual Processing: If you have more inputs (n) than physical processors (p), you can
make each physical processor pretend to be multiple virtual processors. For example,
1,000 inputs with 100 processors means each processor acts as 10 virtual processors.
4. Performance Impact: When using this virtual mapping approach:
o The overall computation time increases by at most n/p (the number of virtual
processors per physical processor)
o The total work (cost) doesn't increase

5. Cost-Optimality Preservation: If your algorithm was cost-optimal with n processors, it

remains cost-optimal when scaled down to p processors (where p < n).
6. Potential Drawback: However, if your algorithm wasn't cost-optimal to begin with,
changing the granularity might not fix this problem and could even make it worse.

Simple Example:

Imagine sorting 1,000 numbers:

 With 1,000 processors: Each handles 1 number (fine granularity)

 With 100 processors: Each handles 10 numbers (coarser granularity)
 With 10 processors: Each handles 100 numbers (very coarse granularity)

The coarser approach often works better in practice because it reduces overhead from
communication between processors, even though theoretically the finest granularity might seem
fastest.
In simple words, "within a constant factor" means the ratio between two numbers stays fixed,
regardless of how big the problem gets.

For our example where:

 Sequential time = 10,000 time units

 Cost = 20,000 time units

The ratio is 20,000 ÷ 10,000 = 2

This means the cost is 2 times the sequential time. Being "within a constant factor" means:

1. The cost isn't growing much faster than the sequential time
2. The ratio (2 in this case) doesn't increase as the problem size grows
3. It's at most some fixed multiplier times the sequential time

For example, if we doubled our problem size:

 Sequential time might become 20,000 time units

 Cost would become 40,000 time units
 The ratio stays at 2 (it's constant)

Being "within a constant factor" is important because it means your parallel solution isn't doing
dramatically more total work than necessary. If your parallel algorithm had a cost that was, say,
100 times or 1000 times the sequential time, it would be wasting computational resources.

In practical terms: you're not paying a huge penalty for going parallel; you're just using about
twice as many resources total to get the speed advantage.