- 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 -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
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.
- Michael J. Quinn, “Parallel Computing : Theory & Practice”, Tata McGraw Hill Edition, Second edition, 2017.
- Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”, University press, Second edition , 2011.
- V Rajaraman, C Siva Ram Murthy, ” Parallel computers- Architecture and Programming “, PHI learning, 2016.
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.