PE501-Parallel-Algorithms.org

<<<PE501>>> PARALLEL ALGORITHMS

{{{credits}}}

L	T	P	C
3	0	0	3

COURSE OBJECTIVES

• To understand the design of parallel algorithms
• To select suitable procedures for parallel algorithms
• 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}}}

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}}}

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}}}

UNIT III

SIMD Algorithms-I

9

Parallel Algorithms for Reduction: 2D Mesh SIMD Model – Prefix computation – Selection – Odd-Even merge sorting – Matrix multiplication

{{{unit}}}

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}}}

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.

\hfill Total Periods: 45

COURSE OUTCOMES

After the completion of this course, students will be able to:

• Understand why communication and coordination are critical to ensure correctness(K2)
• Understand the parallelism inherent in a simple sequential algorithm (K2)
• Apply suitable procedures for parallel algorithms (K3)
• Apply parallel algorithms for standard problems and applications(K3)
• Analyse efficiency of different parallel algorithms (K4).

TEXT BOOK

1. Michael J Quinn, “Parallel Computing : Theory & Practice”, 2nd edition, Tata McGraw Hill, 2017.
2. V Rajaraman, C Siva Ram Murthy, ” Parallel computers- Architecture and Programming “, PHI learning, 2016.

REFERENCES

1. Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, “Introduction to Parallel Computing”, 2nd Edition, Pearson, 2003.
2. Salem G Akl, “The Design and Analysis of Parallel Algorithms”, Prentice Hall, 1989.
3. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”, University press, 2nd edition , 2011
4. M Sasikumar, Dinesh Shikhare and P Ravi Prakash , ” Introduction to Parallel Processing”, PHI learning , 2013.
5. Joseph JaJa, “Introduction to Parallel Algorithms”, Addison-Wesley, 1992.