CSE 605 - Parallel Algorithms

In the face of physical deficiencies, applications that require high performance have sought solutions within parallel structures. Parallel computer architects are increasing day by day and will soon become available for general purpose applications. This derste parallel algorithms that can be used in parallel architectures will be examined.

Introduction and motivation: key concepts, performance metrics, scalability and overheads. Classification of algorithms, architectures and applications: searching, divide and conquer, data parallel. Static and dynamic, message passing and shared memory, systolic. Sorting and searching algorithms: mergesort, quicksort and bitonic sort, implementation on different architectures. Parallel depth-first and breadth-first search techniques. Matrix algorithms: striping and partitioning, matrix multiplication, linear equations, eigenvalues, dense and sparse techniques, finite element and conjugate gradient methods. Optimisation: graph problems, shortest path and spanning trees. Dynamic programming, knapsack problems, scheduling. element methods. Synthesis of parallel algorithms: algebraic methods, pipelines, homomorphisms.