TOWARD A MODEL FOR SHARED DATA ABSTRACTION WITH PERFORMANCE

This paper demonstrates the utility of typed shared data abstractions as an effective high-level means of structuring and coordinating paral lel programs. Access to data shared by concurrent processes is express ed through operations of shared abstract data types (SADTs), SADTs abs tract low-level concerns of communication and synchronization. The exp osition addresses two major challenges: mismatches between representat ions and actual patterns of usage, and over-specified coherence. A pro totype library of SADTs provides a set of implementations for each SAD T, supporting stereotypical usage patterns and allowing exploitation o f weakened coherence protocols, The efficacy of this approach is demon strated on both a network of workstations and a dedicated massively pa rallel computer. A fine-grained irregular task-parallel computation ob tained a speedup of 156 on a 256-processor Gray T3D, showing that the high levels of abstraction afforded by SADTs are compatible with effic ient and scalable implementation. (C) 1998 Academic Press.