PI: Ramachandran, Vijaya Institution: U of Texas Austin Proposal Number: 9988160
A. Project Summary An important goal in parallel processing is the development of general- purpose parallel models and algorithms. The challenge here has been to find the right balance between simplicity, accuracy and broad applicability. This project will develop a comprehensive collection of parallel algorithms suitable for practical use by working with three general-purpose parallel computation models that have been proposed over the last decade | Bulk-Synchronous Parallel (BSP), LogP, and Queuing Shared-Memory (QSM) models | as well as with the external memory Parallel Disk Model (PDM). Some uni- fying themes for the design of efficient algorithms on these models will be developed, and these will form the basis for a systematic development of al- gorithms on these models. The algorithms to be developed will range from kernel algorithms for basic primitives to algorithms for important applica- tions. The research will expose unifying themes relating these well- known models, and will result in fast and efficient parallel algorithms with good performance on a wide range of parallel machines for large problem sizes typically seen in practice. Additionally, this research will provide insight into the fundamental benefits and limitations of parallel processing through the investigation of asymptotically optimal algorithms and lower bounds.
