A Monograph on: Design of Parallel Algorithms and Architecture for Numeric and Non-numeric Problems

Recent innovation in the field of Very Large Scale Integration has resulted into fabrication of high speed processors. The sequential computers, equipped with such high speed processors, are unable to meet the challenges of various real-life and real- time computational problems in the areas of image processing, climate modeling, remote sensing, medical science etc., that require to process massive volume of data. Parallel processing is one of the most appropriate technologies that can meet the challenges of such application areas. A variety of numeric and non-numeric problems are often required to be solved in the above mentioned areas. Prefix computation, polynomial root finding, matrix-matrix multiplication, conflict graph construction are some of the very important computations, which are frequently used for solving such problems. In this thesis, we mainly focus on the design of parallel algorithms for such computations to map them efficiently on suitable interconnection networks. We also study a specific interconnection network, called OTIS-Mesh of trees. We establish its various topological properties and propose several parallel algorithms on it.