language: en

RUNTIME SUPPORT FOR PORTABLE DISTRIBUTED DATA STRUCTURES

Chih-Po Wen, Soumen Chakrabarti, Etienne Deprit, Arvind Krishnamurthy, Katherine Yelick
Computer Science Division, Department of EECS University of California,
Berkeley, California 94720 USA

ABSTRACT Multipol is a library of distributed data structures designed for irregular applications, including those with asynchronous communication patterns. In this paper, we describe the Multipol runtime layer, which provides an efficient and portable abstraction underlying the data structures. It contains a thread system to express computations with varying degrees of parallelism and to support multiple threads per processor for hiding communication latency. To simplify programming in a mul-tithreaded environment, Multipol threads are small, finite-length computations that are executed atomically. Rather than enforcing a single scheduling policy on threads, users may write their own schedulers or choose one of the schedulers provided by Multipol. The system is designed for distributed memory architectures and performs communication optimizations such as message aggregation to improve efficiency on machines with high communication startup overhead. The runtime system currently runs on the Thinking Machines CM5, Intel Paragon, and IBM SP1, and is being ported to a network of workstations. Multipol applications include an event-driven timing simulator [1], an eigenvalue solver [2], and a program that solves the phylogeny problem [3].

1 INTRODUCTION