0
1531

# CS8001 PARALLEL ALGORITHMS Syllabus 2017 Regulation

PARALLEL ALGORITHMS Syllabus 2017 Regulation,CS8001 PARALLEL ALGORITHMS Syllabus 2017 Regulation

CS8001Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â PARALLEL ALGORITHMSÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  L T P CÂ  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â 3 0 0 3

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.

## 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 –Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â I9

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.

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.

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.