ContactPerson: ch25@cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2001-06
%U /u0/csestaff/stock/dissertation.ps
%A Chun-Hsi Huang
%T Communication-Efficient Bulk Synchronous Parallel Algorithms
%D July 30, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K parallel algorithm
%Y algorithms
%X 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 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 different architectures in 
order to demonstrate the practical relevance.