Design and Analysis of Scalable Parallel Algorithms

Abstract

The objective of this research is to develop efficient parallel algorithms for a variety of problems and to analyze the scalability of new and existing parallel algorithms. Scalability analysis is an important tool used for predicting the performance of an algorithm-architecture combination when one or more of the hardware related parameters (interconnection network, speed of processors, speed of communication channels, number of processors) are changed. The problems studied as a part of this project come from diverse domains such as solution of differential equations, discrete optimization, neural network based learning, sorting and graph algorithms. In particular, we have studied parallel algorithms for solving linear systems using the preconditioned conjugate gradient method, partitioning of finite element meshes, balancing load in unstructured tree search arising in discrete optimization, the backpropagation neural network learning algorithm, dynamic programming, fast fourier transform, sorting, shortest-path computation for graphs, robot motion planning, and matrix multiplication. Parallel algorithms, Scalability analysis, Isoefficiency.