To be relevant in practice parallel algorithms must be developed for realistic models of parallel computing, such as the BSP, LogP, and Coarse Grained Multicomputer (CGM) models. This paper surveys three algorithm design techniques - Spatial Partitioning, Sampling, and Data Structure Partitioning - that have led to efficient and practical algorithms for a variety of problems on such realistic models. One particularly noteworthy feature of these techniques is that they often led to algorithms involving only $O(1)$ global communications steps, even for problems that may appear highly unstructured.
| Download Postscript |