Communication-Efficient Bulk Synchronous Parallel Algorithms

Communication has been pointed out to be the major bottleneck for the performance of parallel algorithms. Theoretical parallel models such as PRAM have long been questioned due to the fact that the theoretical algorithmic efficiency does not provide a satisfactory performance prediction when algorithms are implemented on commercially available parallel machines. This is mainly because these models do not provide a reasonable scheme for measuring the communication overhead. Recently several practical parallel models aiming at achieving portability and scalability of parallel algorithms have been widely discussed. Among them, the Bulk Synchronous Parallel (BSP) model has received much attention as a bridging model for parallel computation, as it generally better addresses practical concerns like communication and synchronization. The BSP model has been used in a number of application areas, primarily in scientific computing. Yet, very little work has been done on problems generally considered to be irregularly structured, which usually result in highly data-dependent communication patterns and make it difficult to achieve communication efficiency. Typical examples are fundamental problems in graph theory and computational geometry, which are important as a vast number of interesting problems in many fields are defined in terms of v them. Thus practical and communication-efficient parallel algorithms for solving these problems are important. In this dissertation, we present scalable parallel algorithms for some fundamental problems in graph theory and computational geometry. In addition to the time complexity analysis, we also present some techniques for worst-case and average-case communication complexity analyses. Experimental studies have been performed on two differ...