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 multithreaded 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 SPI, 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].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chih-Po Wen and Katherine Yelick. Portable parallel asynchronous simulation on distributed memory architectures. In Internation Conference on Parallel Processing, 1995. To appear.
Soumen Chakrabarti and Abhiram Ranade and Katherine Yelick Randomized Load Balancing for Tree Structured Computation In IEEE Scalable High Performance Computing Conference, 1995.
Jeff Jones. Exploiting parallelism in the perfect phylogeny computation. Master’s thesis (TR-95–869), University of California, Berkeley, Computer Science Division, December 1994.
Soumen Chakrabarti and Katherine Yelick. Distributed data structures and algorithms for Gröbner basis computation. Lisp and Symbolic Computation, 1994.
H. Berryman, J. Saltz, and J. Scroggs. Execution time support for adaptive scientific algorithms on distributed memory multiprocessors. Concurrency: Practice and Experience, pages 159–178, June 1991.
D. Culler, A. Sah, K. Schauser, T. von Eicken, and J. Wawrzynek. Fine-grain parallelism with minimal hardware support: A compiler-controlled threaded abstract machine. In Proc. of 4th Int. Conf. on Architectural Support for Programming Languages and Operating Systems,Santa-Clara, CA, April 1991.
Ian Foster, Carl Kesselman, Robert Olson, and Steve Tuccke. Nexus: An interoperability toolkit for parallel and distributed computer systems. Technical Report ANL/MCS-TM189, Argonne National Laboratory, 1991.
Thorsten Eicken, D.E. Culler, Seth Copen Goldstein, and Klaus Erik Schauser. Active messages: a mechanism for integrated communication and computation. In International Symposium on Computer Architecture, 1992.
E.A. Brewer and Robert D. Blumofe. Strata: A multi-layer communication library. To appear as a MIT Technical Report, February 1994.
David Culler, Kim Keeton, Lok Tim Liu, Alan Mainwaring, Rich Martin, Steve Rodrigues, and Kristin Wright. The generic active message interface specification. Unpublished, 1994.
Chih-Po Wen and Katherine Yelick. Parallel timing simulation on a distributed memory multiprocessor. In International Conference on CAD, Santa Clara, CA, November 1993. An earlier version appeared as UCB Technical Report CSD-93–723.
R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall, and Yuli Zhou. Cilk: An efficient multithreaded runtime system. In Principles and Practice of Parallel Programming, 1995.
D.R. Jefferson. Virtual time. ACM Transactions on Programming Languages and Systems, 7(3), July 1985.
Chih-Po Wen. The distributed task queue user’s guide. Unpublished, 1994.
Wei Shu and L.V. Kalé. Chare kernel — a runtime support system for parallel computations. Journal of Parallel and Distributed Computing, 11:198–211, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer Science+Business Media New York
About this chapter
Cite this chapter
Wen, CP., Chakrabarti, S., Deprit, E., Krishnamurthy, A., Yelick, K. (1996). Runtime Support for Portable Distributed Data Structures. In: Szymanski, B.K., Sinharoy, B. (eds) Languages, Compilers and Run-Time Systems for Scalable Computers. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-2315-4_9
Download citation
DOI: https://doi.org/10.1007/978-1-4615-2315-4_9
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-5979-1
Online ISBN: 978-1-4615-2315-4
eBook Packages: Springer Book Archive