Credit: 3
Objective
To learn about parallel computing models, design and analyze parallel algorithms for PRAM machines and Interconnection networks.
UNIT I
Structures and algorithms for array processors: SIMD Array Processors, Interconnection networks, Parallel algorithms for Array processors. Multiprocessor architecture- Interconnection networks-multiprocessor control and algorithms- parallel algorithms for multiprocessors.
UNIT II
Selection - broadcast- all sums- parallel selection. Searching a random sequence, sorted sequence on PRAM models, Tree and Mesh.
UNIT III
Merging - A network for merging - merging on PRAM models. Sorting on a linear array, EREW, CREW and CRCW SIMD models, MIMD Enumeration sort.
UNIT IV
Matrix operations- Transposition, Matrix by matrix multiplication, matrix by vector multiplication. Numerical problems- solving systems of linear equations, finding roots of non linear equations on PRAM models.
UNIT V
Graphs - Connected components- dense graphs- sparse graphs. Minimum spanning tree- Solli’s algorithm, Biconnected components, Ear decomposition, Directed graphs.
Outcome:
To enable the student to design and analyze parallel algorithms
Text book:
Kai Wang and Briggs, “Computer Architecture and Parallel Processing”, McGraw Hill, 1985.
S. G. Akl, “Designa and Analysis of Parallel Algorithms”, Prentice Hall Inc., 1992.
Joseph Jaja, “ An Introduction to parallel Algorithms”, Addison Wesley, 1992.
