The progress of science involves a constant interplay between diversification and unification. Diversification extends the boundaries of science to cover new and wider ranges of phenomena; successful unification reveals that a range of experimentally validated theories are no more than particular cases of some more general principle. The cycle continues when the general principle reveals further directions for experimental investigation. This paper suggests that the time has come to attempt a unifying classification of theories of parallel programming. Ideally, this should provide a common basis for reasoning about specifications and the correctness of designs, for optimising programs by algebraic transformation, and for implementing them in a range of technologies on a variety of machine architectures, to satisfy the needs of a wide range of applications.
Performance tuning of parallel applications on shared-memory multiprocessors is to a great extent concerned with removal of performance bottlenecks caused by communication. To simplify performance tuning, our approach has been to extend the hardware/software interface with powerful memory-control primitives in combination with compiler optimizations to remove communication bottlenecks in distributed shared-memory multiprocessors. Evaluations have shown that this combination can yield quite dramatic application performance improvements. This raises the fundamental question of how the hardware/software interface in future distributed shared-memory machines should be defined to serve as a good target for performance tuning of parallel programs, either automatically or by hand. An approach along those lines is discussed.
We survey strategies for distributing shared objects in large parallel and distributed systems. Examples for such objects are, e.g., global variables in a parallel program, pages or cache lines in a virtual shared memory system, or shared files in a distributed system, for example in a distributed multimedia server. We focus on strategies for distributing, accessing, and (consistently) updating such objects, which are provably efficient with respect to various cost measures. We describe static, hashing based schemes that minimize the congestion of the modules holding the objects in worst case scenarios. Especially the benefits of redundant placement schemes are discussed. We further take network latency and bandwidth into account. Here we present schemes that are efficient w.r.t.\ information about access frequencies. Further, dynamic schemes are presented which have good competitive ratio, i.e., are efficient compared to an optimal dynamic distribution that is constructed using full knowledge of the dynamic access pattern.