Parallel Algorithm Design Principles

What is a Parallel Algorithm?

 A parallel algorithm is designed to run multiple computations simultaneously on
multiple processors/cores.
 It breaks down a problem into independent or semi-independent parts to be solved
concurrently.
 Goal: Speed up execution and efficiently utilize hardware.

Parallel algorithms are designed to leverage multiple processors or cores simultaneously to solve
problems faster. Designing efficient parallel algorithms involves understanding both the problem
and the underlying hardware.

A. Decomposition

 Split the original problem into smaller subproblems or tasks.

 Two common types:
o Task decomposition: Different tasks executed in parallel.

What is Task Decomposition?

 Task Decomposition is a parallel design strategy where a problem is broken down into
smaller independent or semi-independent tasks.
 Each task performs a distinct piece of work.
 These tasks can then be executed concurrently on multiple processors.

Why Use Task Decomposition?

 To expose parallelism by identifying separate units of work.
 Helps to distribute workload across processors.
 Often used when different operations or phases of a problem can be done simultaneously.

How Does it Work?

1. Identify distinct tasks or units of work within the problem.
2. Analyze the dependencies between tasks.
3. Execute tasks in parallel wherever dependencies allow.
4. Coordinate results or synchronize as necessary.
Example Scenarios
1. Image Processing Pipeline

 Tasks might be:

o Load image
o Apply filter
o Detect edges
o Compress output
 Each task can run on separate processors, possibly in a pipeline fashion.

What is Data Decomposition?

 Data Decomposition is a parallel design strategy where the data set is divided into
smaller chunks or partitions.
 The same operation or algorithm is applied independently on each data chunk in
parallel.
 This approach exploits data parallelism, where multiple processors perform the same
task but on different pieces of data.

Why Use Data Decomposition?

 To distribute the data workload evenly among processors.
 To improve performance by allowing simultaneous processing of data parts.
 Often used when the problem involves processing large data sets with repetitive
operations (e.g., matrix operations, image processing).

How Does It Work?

1. Split the input data into disjoint subsets.
2. Assign each subset to a processor.
3. Each processor executes the same algorithm on its subset independently.
4. If necessary, results from processors are combined (reduced) at the end.

Example Scenario: Parallel Array Sum

 Given an array of numbers, divide it into equal segments.
 Each processor computes the sum of its segment.
  The partial sums are then combined to get the final total.

Diagram: Data Decomposition Example

Array: [A0, A1, A2, A3, A4, A5, A6, A7]

Split into chunks:

Processor 1 -> [A0, A1]

Processor 2 -> [A2, A3]

Processor 3 -> [A4, A5]

Processor 4 -> [A6, A7]

Each processor sums its chunk independently in parallel.

Partial sums: S1, S2, S3, S4

Final sum = S1 + S2 + S3 + S4

Data decomposition: Divide data into chunks processed in parallel.

Example: For summing an array, divide the array into segments, each summed independently.

1. Decomposition (Task/Domain Decomposition)

 Task Decomposition: Divide the problem into smaller tasks that can be executed
concurrently.
 Data Decomposition (Domain Decomposition): Split data into chunks that different
processors work on independently.

2. Task Assignment and Scheduling

 Assign tasks to processors in a way that balances load.

 Avoid idle processors and minimize synchronization overhead.

3. Communication and Synchronization

 Minimize communication between tasks, especially if processors are distributed.

 Synchronize tasks only when necessary to maintain correctness.

4. Granularity
  Fine-grained parallelism: Small tasks with frequent communication.
 Coarse-grained parallelism: Larger tasks with less communication.
 Balance granularity to optimize performance.

5. Data Locality

 Design algorithms to maximize data locality, reducing the need for remote memory
access.
 Exploit cache hierarchies.

6. Load Balancing

 Distribute work evenly to avoid bottlenecks.

 Dynamic load balancing can help when task execution times are unpredictable.

7. Scalability

 Ensure the algorithm performs efficiently as the number of processors increases.

 Consider speedup and efficiency metrics.

8. Avoiding Bottlenecks

 Identify and minimize sequential parts of the algorithm (Amdahl’s Law).

 Reduce contention for shared resources.

Common Parallel Algorithm Design Techniques

 Parallel Prefix (Scan)
 Divide and Conquer
 Pipeline Parallelism
 Task Parallelism
 Data Parallelism
 MapReduce Framework

Programming Parallel Algorithms

Common Parallel Programming Models and APIs

 Shared Memory: Threads share a common address space.

o Example APIs: OpenMP, Pthreads, C++ std::thread
  Distributed Memory: Each processor has its own memory; communication via message
passing.
o Example APIs: MPI (Message Passing Interface)
 Hybrid: Combines shared and distributed memory (e.g., MPI + OpenMP)

Basic Steps in Parallel Programming

1. Identify parallelism in the problem.

2. Partition data/tasks.
3. Implement parallel code using appropriate constructs (threads, processes).
4. Synchronize where needed (mutexes, barriers).
5. Optimize communication and data locality.
6. Test and debug for correctness and race conditions.
7. Measure and tune performance.

Example: Parallel Sum of Array (Using Shared Memory)

#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < n; i++) {
sum += array[i];
}

 Here, OpenMP is used to split the summation across multiple threads.

 The reduction clause avoids race conditions on the sum variable.

Performance Metrics

 Speedup = Time_serial / Time_parallel

 Efficiency = Speedup / Number_of_processors
 Scalability: Ability to maintain efficiency as processors increase.

Why Communication and Coordination/Synchronization are

Needed in Parallel Algorithms
1. Communication

 Definition: The process by which multiple processors or threads exchange data.

 Why Needed:
o When tasks depend on data produced by other tasks.
o To share partial results or update shared data structures.
o To combine independently computed parts into a final result.
 Example:
 o In distributed memory systems, processors cannot directly access each other’s
memory. They must send messages to share data.
o Even in shared memory, threads might need to read updated values from other
threads.

2. Coordination / Synchronization

 Definition: Mechanisms to control the sequence and timing of operations across multiple
processors or threads.
 Why Needed:
o To prevent race conditions where multiple threads/processes try to update the
same data simultaneously.
o To ensure that a computation step starts only after dependent data is ready.
o To maintain data consistency and correctness.
 Common Synchronization Constructs:
o Locks/Mutexes: Ensure exclusive access to shared resources.
o Barriers: All threads wait at a barrier until everyone reaches it (used to
synchronize phases).
o Semaphores: Control access with counters.
o Atomic operations: Hardware-supported indivisible operations.
 Example:
o When multiple threads update a shared counter, synchronization prevents them
from corrupting its value.

Scheduling in Parallel Computing

What is Scheduling?

 Scheduling is the process of deciding when and on which processor/thread a task

runs in a parallel system.
 It involves assigning tasks to processors to optimize performance, minimize idle time,
and ensure efficient use of resources.

Types of Scheduling

1. Static Scheduling
o Tasks are assigned to processors before execution.
o The schedule doesn’t change during runtime.
o Simple and low overhead.
o Works well if task sizes and execution times are predictable.
2. Dynamic Scheduling
o Tasks are assigned to processors at runtime, often based on processor
availability.
 o Helps balance load when task execution times are unpredictable.
o Higher overhead due to scheduling decisions during execution.
3. Hybrid Scheduling
o Combines static and dynamic methods.
o Some tasks are statically assigned, and the rest are dynamically scheduled.

Goals of Scheduling

 Load Balancing: Distribute work evenly so all processors stay busy.

 Minimize Makespan: Reduce total completion time.
 Reduce Communication: Assign related tasks close to each other.
 Avoid Contention and Bottlenecks

Contention in Parallel Computing

What is Contention?

 Contention occurs when multiple processors/threads try to access the same shared
resource simultaneously.
 Shared resources include:
o Memory locations (variables, data structures)
o Network bandwidth in distributed systems
o Locks or synchronization primitives

Why is Contention a Problem?

 Leads to delays as processors wait for the resource to become available.

 Can cause performance degradation and reduce the benefits of parallelism.
 May cause deadlocks or priority inversion if not managed properly.

Types of Contention

1. Memory Contention
o Multiple threads try to read/write the same memory location.
o Leads to cache coherence traffic and stalls.
2. Lock Contention
o Multiple threads try to acquire the same lock.
o Only one thread proceeds, others wait, causing idle time.
3. Network Contention
o Multiple processors try to send/receive messages over the network
simultaneously.
o Can cause congestion and delay.
Relationship Between Scheduling and Contention
 Poor scheduling can increase contention by assigning tasks that heavily share resources
to run at the same time on processors.
 Good scheduling reduces contention by spreading out resource-intensive tasks or
ordering them to avoid simultaneous access.

Example
 Imagine a parallel program where several threads update a shared counter:
o If scheduled poorly, many threads try to update the counter simultaneously →
high lock contention.
o If scheduled or designed carefully, threads update the counter in phases or use
lock-free techniques → low contention.