PROGRAM STRUCTURING FOR EFFECTIVE PARALLEL PORTABILITY

The tension between software development costs and efficiency is especially high when considering parallel programs intended to run on a variety of architectures. In the domain of shared memory architectures and explicitly parallel programs, we have addressed this problem by defining a programming structure that eases the development of effectively portable programs. On each target multiprocessor, an effectively portable program runs almost as efficiently as a program fine-tuned for that machine. Additionally, its software development cost is close to that of a single program that is portable across the targets. Using our model, programs are defined in terms of data structure and partitioning-scheduling abstractions. These are activities identified as substantially affecting the performance of parallel programs; activities whose most efficient implementations can differ on the basis of the algorithm, multiprocessor, and even run-time data values and parameters. Low software development cost is attained by writing source programs in terms of abstract interfaces and thereby requiring minimal modification to port; high performance is attained by matching (often dynamically) the interfaces to implementations that are most appropriate to the execution environment. We include results of a prototype used to evaluate the benefits and costs of this approach.