### CS8001 - PARALLEL ALGORITHMS (Syllabus) 2017-regulation Anna University

CS8001 |
PARALLEL ALGORITHMS |
LPTC |
---|

**3003**

**OBJECTIVES:**

• To understand different parallel architectures and models of computation.

• To introduce the various classes of parallel algorithms.

• To study parallel algorithms for basic problems.

• To introduce the various classes of parallel algorithms.

• To study parallel algorithms for basic problems.

UNIT I |
INTRODUCTION |
9 |
---|

Need for Parallel Processing - Data and Temporal Parallelism - Models of Computation - RAM and PRAM Model – Shared Memory and Message Passing Models- Processor Organisations - PRAM Algorithm – Analysis of PRAM Algorithms- Parallel Programming Languages.

UNIT II |
PRAM ALGORITHMS |
9 |
---|

Parallel Algorithms for Reduction – Prefix Sum – List Ranking –Preorder Tree Traversal – Searching -Sorting - Merging Two Sorted Lists – Matrix Multiplication - Graph Coloring - Graph Searching.

UNIT III |
SIMD ALGORITHMS -I |
9 |
---|

2D Mesh SIMD Model - Parallel Algorithms for Reduction - Prefix Computation - Selection - Odd-Even Merge Sorting - Matrix Multiplication

UNIT IV |
SIMD ALGORITHMS -II |
9 |
---|

Hypercube SIMD Model - Parallel Algorithms for Selection- Odd-Even Merge Sort- Bitonic Sort- Matrix Multiplication Shuffle Exchange SIMD Model - Parallel Algorithms for Reduction
-Bitonic Merge Sort - Matrix Multiplication - Minimum Cost Spanning Tree

UNIT V |
MIMD ALGORITHMS |
9 |
---|

UMA Multiprocessor Model -Parallel Summing on Multiprocessor- Matrix Multiplication on Multiprocessors and Multicomputer - Parallel Quick Sort - Mapping Data to Processors.

**TOTAL : 45 PERIODS**

**OUTCOMES:Upon completion of this course, the students should be able to**

• Develop parallel algorithms for standard problems and applications.

• Analyse efficiency of different parallel algorithms.

• Analyse efficiency of different parallel algorithms.

**TEXT BOOKS:**

1. Michael J. Quinn, "Parallel Computing : Theory & Practice", Tata McGraw Hill Edition, Second edition, 2017.

2. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, "Fundamentals of Computer Algorithms", University press, Second edition , 2011.

3. V Rajaraman, C Siva Ram Murthy, " Parallel computers- Architecture and Programming ", PHI learning, 2016.

2. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, "Fundamentals of Computer Algorithms", University press, Second edition , 2011.

3. V Rajaraman, C Siva Ram Murthy, " Parallel computers- Architecture and Programming ", PHI learning, 2016.

**REFERENCES**

1. Ananth Grame, George Karpis, Vipin Kumar and Anshul Gupta, "Introduction to Parallel Computing", 2nd Edition, Addison Wesley, 2003.

2. M Sasikumar, Dinesh Shikhare and P Ravi Prakash , " Introduction to Parallel Processing", PHI learning , 2013.

3. S.G.Akl, "The Design and Analysis of Parallel Algorithms", PHI, 1989.

2. M Sasikumar, Dinesh Shikhare and P Ravi Prakash , " Introduction to Parallel Processing", PHI learning , 2013.

3. S.G.Akl, "The Design and Analysis of Parallel Algorithms", PHI, 1989.

## Comments

## Post a Comment