Transportable Parallel Algorithms: from Theory to Practice David E. Culler CS Division UC Berkeley Workshop on Portability and Performance for Parallel Processors July 13-15, 1993 Parallel architectures have long seemed on the verge of breakthrough in any one of many diverse directions: SIMD, Message Passing, Shared Memory, Dataflow, etc. This made the future very difficult to predict, divided the research community along lines of belief, frustrated attempts to develop a common theoretical model, and essentially paralyzed the development parallel software. However, technological and economic forces have quelled the debate; for the forseeable future all large parallel machines will look essentially like a network of workstations, with a fast microprocessor, large DRAM memory, and sophisticated cache structure on each node. The key difference is that the network is considerably more power and robust. Furthernmore, Active Messages has demonstrated that all programming models are built on the same primitive; the key difference is how it is packaged: in hardware, system, or user level. Thus, parallel machines differ primarily in the costs of various communication operations, not in basic functionality. Given this convergence it is reasonable to formulate an abstract parallel machine characterized by its performance characteristics along a small number of dimensions to serve as a basis for transportable algorithm design. I will present one such model, called LogP, and a programming language, Split-C, which exposes the full capabilities of the model. We will examine the translation from theory to practice on the CM-5.