| Parallel computing has long offered the promise of very high performance, but has delivered it only in a narrow range of applications. Despite the gigantic flops numbers reported on the top500 list for supercomputers, success stories for real applications are still largely limited to regular problems, e.g., matrix manipulations. For most of the irregular problems, few fast parallel implementations exist, even though fast theoretic algorithms are known.; In this thesis we present the design and implementation of fast parallel algorithms for graph problems on shared memory machines such as symmetric multiprocessors (SMPs) and Cray multi-threaded architecture (MTA). The arbitrary, sparse graph instances are usually of irregular nature, and pose challenges for efficient parallel implementations. Most of the theoretic algorithms for graph problems are under the idealistic PRAM model where an unlimited number of processors work in synchronous locksteps and communication costs among processors are free. Emulating PRAM algorithms on SMPs by scaling down the parallelism to the number of processors does not yield implementations that are faster than the best sequential ones, even with considerable algorithm engineering efforts spent on optimization. Instead, new efficient algorithms have to be designed that take into consideration factors of machine architectures that are hard to incorporate into a parallel model, yet crucial to the performance of an algorithm. Efficient parallel algorithms for spanning tree, minimum spanning tree, Euler-tour construction, rooting a tree, and biconnected components are presented in this dissertation. General techniques for designing and implementing parallel algorithms for graph problems on SMPs will be discussed. As multi-threaded architecture is very likely to be adapted in the future HPC machines, we also briefly discuss the impact of multi-threaded architecture on parallel algorithm design and make comparisons with SMPs. |
