Credits: 3
A presentation of the theory of parallel computers and parallel processing. Models of parallel processing and the relationships between these models. Techniques for the design and analysis of efficient parallel algorithms including parallel prefix, searching, sorting, graph problems, and algebraic problems. Theoretical limits of parallelism.
Description
Prerequisite: ENEE351 or CMSC351. Credit only granted for ENEE459P, ENEE651, or CMSC751.A presentation of the theory of parallel computers and parallel processing. Models of parallel processing and the relationships between these models. Techniques for the design and analysis of efficient parallel algorithms including parallel prefix, searching, sorting, graph problems, and algebraic problems. Theoretical limits of parallelism.
Semesters Offered
Fall 2022, Fall 2024
TestudoTopics Covered
- Introduction to Parallel Algorithms: Performance of Parallel Algorithms Including Work and Depth, Optimality Notions
- Basic Techniques: Balanced Trees, Pointer Jumping, Divide-and-Conquer, Partitioning, Pipelining, Accelerated Cascading, Breaking Symmetry
- Trees and Lists: List Ranking, The Euler Tour Techniques, Tree Connection, Evaluation of Arithmetic Expressions
- Searching, Merging and Sorting
- Graphs: Connected Components, Transitive Closure, Paths Problems
- Strings: Some string matching algorithms
- Introduction to Parallel Processing
- Matrix multiplication, in particular on GPU, and its role in deep learning
- Introduction to state-of-the-art of parallel computing and discussion of the question: Can fine-grained large scale on-chip parallel computing be harnessed towards faster completion time of a single general-purpose computing task?