Efficient Use of Parallel Distributed Systems: From Theory to Practice

This article focuses on principles for the design of efficient parallel algorithms for distributed memory computing systems. We describe the general trend in the development of architectural properties and evaluate the state-of-the-art in a number of basic primitives like graph embedding, partitioning, dynamic load distribution, and communication which are used, to some extent, within all parallel applications. We discuss possible directions for future work on the design of universal basic primitives, able to perform efficiently on a broad range of parallel systems and applications, and we also give certain examples of specific applications which demand specialized basic primitives in order to obtain efficient parallel implementations. Finally, we show that programming frames can offer a convenient way to encapsulate algorithmic know-how on applications and basic primitives and to offer this knowledge to nonspecialist users in a very effective way