High Performance Computing - Detailed Notes
Module 1: Introduction to Parallel Computing (10 hours)
1.1 What is Parallel Computing?
Parallel computing is a type of computation in which many calculations or processes are carried out
simultaneously. It leverages multiple processors to solve a problem faster.
1.2 Terminologies in Parallel Processing
- Task: A logical unit of work.
- Process: An instance of a running program.
- Thread: A component of a process that can run independently.
- Speedup: Ratio of time taken by single processor to time taken by multiple processors.
- Efficiency: Ratio of speedup to number of processors.
1.3 Types of Parallelism
- Data Parallelism: Performing the same task on different pieces of distributed data.
- Control Parallelism: Executing different tasks simultaneously.
- Pipelining: Breaking a task into stages with each stage handled by a different processor.
1.4 Scalability
Refers to how well a parallel system can increase performance when additional resources are
added.
1.5 Control Parallel & Data Parallel Approaches
- Control Parallel: Each processor executes different instruction sets.
- Data Parallel: Each processor performs the same operation on different pieces of data.
1.6 Parallel Reduction
Combines values from multiple processors to a single result (e.g., sum, max).
1.7 Prefix Sums
An operation where each element in an array is replaced by the sum of all previous elements
including itself.
1.8 List Ranking
Determines the position of each node in a linked list from the head node.
1.9 Preorder Tree Traversal
Parallel traversal of trees in preorder (root, left, right).
1.10 Merging Two Sorted Lists
Divide the task into chunks and merge them in parallel.
1.11 Graph Coloring
Assigning colors to vertices such that no two adjacent vertices have the same color.
1.12 Reducing Number of Processors
Optimizing task-to-processor mapping to minimize idle time and resource wastage.
1.13 Problems Defying Fast Solutions on PRAMs
Some problems inherently resist efficient parallelization due to dependencies.
Module 2: Parallel Architectures (10 hours)
2.1 MIMD Architectures (Multiple Instruction, Multiple Data)
- Each processor executes different instructions on different data.
- Includes both shared and distributed memory systems.
2.2 Multi-threaded Architectures
- Processors capable of managing multiple threads concurrently.
- Improves latency hiding and resource usage.
2.3 Distributed Memory Systems
- Each processor has its own private memory.
- Communication via message passing (e.g., MPI).
2.4 Shared Memory Systems
- All processors access a common memory space.
- Easier programming but more contention.
Module 3: Interconnection Networks (8 hours)
3.1 Dynamic Interconnection Networks
- Networks where the path between two nodes can change during execution.
- Topologies include:
- Mesh
- Torus
- Hypercube
- Tree
- Ring
- Key Metrics: Bandwidth, Latency, Bisection width, Diameter.
Module 4: Mapping and Scheduling (8 hours)
4.1 Mapping
- Assigning processes or data to processors.
- Affects load balancing and communication cost.
4.2 Scheduling
- Static Scheduling: Tasks assigned before execution.
- Dynamic Scheduling: Tasks assigned during execution.
4.3 Load Balancing
- Equal distribution of workload among processors.
- Static Load Balancing: Predefined distribution.
- Dynamic Load Balancing: Adjusted at runtime.
4.4 Deadlock
- Occurs when processes wait indefinitely for resources.
- Solutions:
- Avoidance
- Detection and Recovery
- Prevention
Module 5: Parallel Programming & Algorithms (12 hours)
5.1 Programming Models
- OpenMP: For shared memory systems.
- MPI: For distributed memory systems.
- CUDA: For GPU programming.
5.2 Structure of Parallel Algorithms
- Divide the problem.
- Distribute tasks among processors.
- Compute in parallel.
- Combine the results.
5.3 Analysis of Parallel Algorithms
- Measure performance with speedup, efficiency, and scalability.
5.4 Elementary Parallel Algorithms
- Sum, Max, Min in parallel.
5.5 Matrix Algorithms
- Matrix addition, multiplication, inversion using parallel blocks.
5.6 Sorting Algorithms
- Parallel Merge Sort, Bitonic Sort.
5.7 Graph Algorithms
- Parallel BFS, DFS, Graph coloring, Shortest Path (e.g., Dijkstra's in parallel).