Design, analysis and implementation of bulk-synchronous parallel algorithms, data structures and techniques

Thesis

The objective of this thesis is the unified investigation of a wide range of fundamental parallel methods that are transportable amongst pragmatic parallel machines having different number of processors, different periodicity of global synchronization and different bandwidth of inter-processor communication. The computational model adopted is the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of parallel machines into three numerical parameters p, L and g, that quantify, respectively, processors, periodicity and bandwidth - the model differentiates memory that is local to a processor from memory that is non-local, yet, for the sake of universality, does not differentiate network proximity. The BSP parameters p, L and g, together with the problem size n, are employed to measure the performance, and consequently, the transportability of parallel methods across machines having different values of these parameters.

We show that optimality to within small multiplicative constant factors close to one can be achieved for a multiplicity of fundamental computational problems by transportable algorithms and data structures that can be applied for a wide range of values of the BSP parameters. While these algorithms and data structures are fairly simple themselves, description of their performance in terms of these parameters is somewhat complicated. The main reward for quantifying these complications, is that it enables software to be written once and for all that can be migrated efficiently amongst a variety of parallel machines. The methods considered in this thesis - both theoretically and experimentally - embody deterministic and randomized techniques for the efficient realization of fundamental algorithms (broadcasting, computing parallel-prefixes, load-balancing, list-contracting, merging, sorting, integer-sorting, selecting, searching and hashing), data structures (heaps, search trees and hash tables) and applications (computational geometry, parallel model simulations and structured query language primitives).

Authors: Siniolkis, C

• DOI: 10.5287/ora-j5ykqxd60
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford