1.5 Summary

This chapter has introduced four desirable attributes of parallel algorithms and software: concurrency, scalability, locality, and modularity. Concurrency refers to the ability to perform many actions simultaneously; this is essential if a program is to execute on many processors. Scalability indicates resilience to increasing processor counts and is equally important, as processor counts appear likely to grow in most environments. Locality means a high ratio of local memory accesses to remote memory accesses (communication); this is the key to high performance on multicomputer architectures. Modularity ---the decomposition of complex entities into simpler components---is an essential aspect of software engineering, in parallel computing as well as sequential computing.

The multicomputer parallel machine model and the task/channel programming model introduced in this chapter will be used in subsequent discussion of parallel algorithm design, analysis, and implementation. The multicomputer consists of one or more von Neumann computers connected by an interconnection network. It is a simple and realistic machine model that provides a basis for the design of scalable and portable parallel programs. A programming model based on tasks and channels simplifies the programming of multicomputers by providing abstractions that allow us to talk about concurrency, locality, and communication in a machine-independent fashion, and by providing a basis for the modular construction of parallel programs.