Learn · Introduction to parallel programming with OpenMP and MPI
Lecture 32 of 84week-04
Understanding LU Factorization
Prof. Yogish Sabharwal · IIT Delhi
Credits and licence
- From
- Introduction to parallel programming with OpenMP and MPI, IIT Delhi (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Introduction to Parallel Programming
- Parallel Architectures and Programming Models
- Pipelining
- Superpipelining and VLIW
- Memory Latency
- Cache and Temporal Locality
- Cache, Memory bandwidth and Spatial Locality
- Intuition for Shared and Distributed Memory architectures
- Shared and Distributed Memory architectures
- Interconnection networks in Distributed Memory architectures
- OpenMP: A parallel Hello World Program
- Program with Single thread
- Program Memory with Multiple threads and Multi-tasking
- Context Switching
- OpenMP: Basic thread functions
- OpenMP: About OpenMP
- Shared Memory Consistency Models and the Sequential Consistency Model
- Race Conditions
- OpenMP: Scoping variables and some race conditions
- OpenMP: thread private variables and more constructs
- Computing sum: first attempt at parallelization
- Manual distribution of work and critical sections
- Distributing for loops and reduction
- Vector-Vector operations (Dot product)
- Matrix-Vector operations (Matrix-Vector Multiply)
- Matrix-Matrix operations (Matrix-Matrix Multiply)
- Introduction to tasks
- Task queues and task execution
- Accessing variables in tasks
- Completion of tasks and scoping variables in tasks
- Recursive task spawning and pitfalls
- Understanding LU Factorization
- Parallel LU Factorization
- Locks
- Advanced Task handling
- Matrix Multiplication using tasks
- The OpenMP Shared Memory Consistency Model
- Applications finite element method
- Applications deep learning
- Introduction to MPI and basic calls
- MPI calls to send and receive data
- MPI calls for broadcasting data
- MPI non blocking calls
- Application distributed histogram updation
- MPI collectives and MPI broadcast
- MPI gathering and scattering collectives
- MPI reduction and alltoall collectives
- Discussion on MPI collectives design
- Characteriziation of interconnects
- Linear arrays 2D mesh and torus
- d dimensional torus
- Hypercube
- Trees and cliques
- Hockney model
- Broadcast and Reduce with recursive doubling
- Scatter and Gather with recursive doubling
- Reduce scatter and All gather with recursive doubling
- Discussion of message sizes in analysis
- Revisiting Reduce scatter on 2D mesh
- Reduce scatter and Allreduce on the Hypercube
- Alltoall on the Hypercube
- Lower bounds
- Pipeline based algorithm for Allreduce
- An improved algorithm for Alltoall on the Hypercube using E cube routing
- Pipeline based algorithm for Broadcast
- Introduction to parallel graph algorithms
- Breadth First Search BFS using matrix algebra
- BFS Shared memory parallelization using OpenMP
- Distributed memory settings and data distribution
- Distributed BFS algorithm
- Performance considerations
- Prims Algorithm
- OpenMP based shared memory parallelization for MST
- MPI based distributed memory parallelization for MST
- Sequential Algorithm Adaptation from Prims
- Parallelization Strategy for Prims algorithm
- Dry run with the parallel strategy
- Johnsons algorithm with 1D data distribution
- Speedup analysis on a grid graph
- Floyds algorithm for all pair shortest paths
- Floyds algorithm with 2D data distribution
- Adaptation to transitive closures
- Parallelization strategy for connected components
- Analysis for parallel connected components