Scribd
Upload
8 views

Chapter20-Parallelalgorithms

Uploaded by

MAHALAKSHMI GANESH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views

Chapter20-Parallelalgorithms

Uploaded by

MAHALAKSHMI GANESH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 68

Chapter 20:

Introduction to Parallel
algorithms
D R . S . SR IDH A R

A S S O C I A TE P R O F ES S O R

DEP ARTM ENT O F I S T

AN N A U N I V E RS IT Y
objectives
What is a Parallel algorithm?
Flynn classification
Disadvantages of randomized algorithms
SISD
SIMD
MISD system
MIMD
Address-Space based Classification
Principles
Uniform access Memory systems
Non-uniform access systems
Wire or Circuit Models
Static Interconnection networks
Dynamic Interconnection network
Terminologies
PRAM model
PRAM model
Execution in PRAM
Variants in PRAM
Parallel algorithm Specifications
Parallel algorithm Specifications
Specifications
More specifications
Amadhl Law
Parallel algorithm analysis
Complexity analysis
Cost and Efficiency
Prefix computation
Informal algorithm
Example
Solution
Formal algorithm
Complexity Analysis
List Ranking
Randomized quicksort
Euler Tour
Preorder Procedure
Example
Parallel Search
Informal algorithm
Formal algorithm
Complexity Analysis
Odd-Even Swap sort
Informal algorithm
Formal algorithm
Contd..
Parallel Mergesort
Formal algorithm
Formal algorithm
Example
Example
Complexity Analysis
Parallel Matrix multiplication
Mesh
Formal algorithm
Formal algorithm
Complexity analysis
Example
Example
Contd..
Parallel Graph algorithms
Formal algorithm
Complexity Analysis
Glossary
Glossary

You might also like