Article

Satin: Efficient Parallel Divide-and-Conquer in Java

Authors:

Rob van Nieuwpoort,

Thilo Kielmann,

Henri E. BalAuthors Info & Claims

Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing

Pages 690 - 699

Published: 29 August 2000 Publication History

Abstract

Satin is a system for running divide and conquer programs on distributed memory systems (and ultimately on wide-area metacomputing systems). Satin extends Java with three simple Cilk-like primitives for divide and conquer programming. The Satin compiler and runtime system cooperate to implement these primitives efficiently on a distributed system, using work stealing to distribute the jobs. Satin optimizes the overhead of local jobs using on-demand serialization, which avoids copying and serialization of parameters for jobs that are not stolen. This optimization is implemented using explicit invocation records. We have implemented Satin by extending the Manta compiler. We discuss the performance of ten applications on a Myrinet-based cluster.

References

[1]

H. E. Bal, R. Bhoedjang, R. Hofman, C. Jacobs, K. Langendoen, T. Rühl, and F. Kaashoek. Performance Evaluation of the Orca Shared Object System. ACM Transactions on Computer Systems, 16(1):1-40, Feb. 1998.

[2]

J. Baldeschwieler, R. Blumofe, and E. Brewer. ATLAS: An Infrastructure for Global Computing. In Proceedings of the Seventh ACM SIGOPS European Workshop on System Support for Worldwide Applications, 1996.

[3]

R. A. F. Bhoedjang, T. Rühl, and H. E. Bal. User-Level Network Interface Protocols. IEEE Computer, 31(11):53-60, Nov. 1998.

[4]

A. Bik, J. Villacis, and D. Gannon. javar: A prototype Java restructuring compiler. Concurrency: Practice and Experience, 9(11):1181-1191, November 1997.

[5]

R. Blumofe and P. Lisiecki. Adaptive and reliable parallel computing on networks of workstations. In In Proceedings of the USENIX 1997 Annual Technical Conference on UNIX and Advanced Computing Systems, Anaheim, California, 1997.

[6]

R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. In Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'95, pages 207-216, Santa Barbara, California, July 1995.

[7]

J. Darlington. Alice: a multi-processor reduction machine for the parallel evaluation of applicative languages. In Arvind, editor, 1st Conference on Functional Programming Languages and Computer Architecture, pages 65-76, Wentworth-bythe-Sea, Portsmouth, New Hampshire, 1981.

[8]

The Distributed ASCI Supercomputer (DAS). http://www.cs.vu.nl/das/.

[9]

B. Freisleben and T. Kielmann. Automated Transformation of Sequential Divide-and-Conquer Algorithms into Parallel Programs. Computers and Artificial Intelligence, 14(6):579-596, 1995.

[10]

K. S. Gatlin and L. Carter. Architecture-cognizant divide and conquer algorithms. In SuperComputing '99, November 1999.

[11]

D. Lea. A java fork/join framework. In ACM Java Grande 2000 Conference, San Francisco, California, June 2000.

[12]

J. Maassen, R. van Nieuwpoort, R. Veldema, H. Bal, and A. Plaat. An Efficient Implementation of Java's Remote Method Invocation. In ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 173-182, Atlanta, GA, May 1999.

[13]

E. Mohr, D. Kranz, and R. Halstead. Lazy task creation: a technique for increasing the granularity of parallel programs. In Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pages 185-197, June 1990.

[14]

M. Philippsen and M. Zenger. JavaParty--Transparent Remote Objects in Java. Concurrency: Practice and Experience, pages 1225-1242, Nov. 1997.

[15]

R. Rugina and M. Rinard. Automatic parallelization of divide and conquer algorithms. In Seventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 72-83, Atlanta, May 4-6 1999. Massachusetts Institute of Technology.

[16]

Sun MicroSystems, Inc. Java (TM) Object Serialization Specification, 1996. ftp://ftp.javasoft.com/docs/jdk1.1/serial-spec.ps.

[17]

J. Waldo. Remote procedure calls and Java Remote Method Invocation. IEEE Concurrency, pages 5-7, July-September 1998.

[18]

I. Watson, V. Woods, P. Watson, R. Banach, M. Greenberg, and J. Sargeant. Flagship: A parallel architecture for declarative programming. In 15th IEEE/ACM Symp. on Computer Architecture, pages 124-130, Honolulu, Hawaii, 1988. ACM SIGARCH newsletter,16(2).

Cited By

Nakashima JNakatani STaura KHoefler TIskra K(2013)Design and implementation of a customizable work stealing schedulerProceedings of the 3rd International Workshop on Runtime and Operating Systems for Supercomputers10.1145/2491661.2481433(1-8)Online publication date: 10-Jun-2013
https://dl.acm.org/doi/10.1145/2491661.2481433
Olivier SPorterfield AWheeler KPrins JIskra KHoefler T(2011)Scheduling task parallelism on multi-socket multicore systemsProceedings of the 1st International Workshop on Runtime and Operating Systems for Supercomputers10.1145/1988796.1988804(49-56)Online publication date: 31-May-2011
https://dl.acm.org/doi/10.1145/1988796.1988804
Lima JMaillard N(2009)Online mapping of MPI-2 dynamic tasks to processes and threadsInternational Journal of High Performance Systems Architecture10.1504/IJHPSA.2009.0320252:2(81-89)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1504/IJHPSA.2009.032025
Show More Cited By

Index Terms

Satin: Efficient Parallel Divide-and-Conquer in Java
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
  2. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Index terms have been assigned to the content through auto-classification.

Recommendations

Satin: A high-level and efficient grid programming model

Computational grids have an enormous potential to provide compute power. However, this power remains largely unexploited today for most applications, except trivially parallel programs. Developing parallel grid applications simply is too difficult. ...
Satin++: Divide-and-Share on the Grid
E-SCIENCE '06: Proceedings of the Second IEEE International Conference on e-Science and Grid Computing

Divide-and-conquer is a popular and effective paradigm for writing grid-enabled applications. I t has been shown to perform well i n environments wtth high network latencies and dynamically changing numbers of processors. However, an important ...
SATIN: a toolkit for informal ink-based applications
SIGGRAPH '07: ACM SIGGRAPH 2007 courses

Software support for making effective pen-based applications is currently rudimentary. To facilitate the creation of such applications, we have developed SATIN, a Java-based toolkit designed to support the creation of applications that leverage the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Euro-Par '00: Proceedings from the 6th International Euro-Par Conference on Parallel Processing

August 2000

3356 pages

ISBN:3540679561

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 29 August 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nakashima JNakatani STaura KHoefler TIskra K(2013)Design and implementation of a customizable work stealing schedulerProceedings of the 3rd International Workshop on Runtime and Operating Systems for Supercomputers10.1145/2491661.2481433(1-8)Online publication date: 10-Jun-2013
https://dl.acm.org/doi/10.1145/2491661.2481433
Olivier SPorterfield AWheeler KPrins JIskra KHoefler T(2011)Scheduling task parallelism on multi-socket multicore systemsProceedings of the 1st International Workshop on Runtime and Operating Systems for Supercomputers10.1145/1988796.1988804(49-56)Online publication date: 31-May-2011
https://dl.acm.org/doi/10.1145/1988796.1988804
Lima JMaillard N(2009)Online mapping of MPI-2 dynamic tasks to processes and threadsInternational Journal of High Performance Systems Architecture10.1504/IJHPSA.2009.0320252:2(81-89)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1504/IJHPSA.2009.032025
Gonçalves RSobral JKranzlmüller DBode AHegering HCasanova HGerndt M(2009)Pluggable parallelisationProceedings of the 18th ACM international symposium on High performance distributed computing10.1145/1551609.1551614(11-20)Online publication date: 11-Jun-2009
https://dl.acm.org/doi/10.1145/1551609.1551614
Cera MPezzi GPilla MMaillard NNavaux P(2006)Scheduling dynamically spawned processes in MPI-2Proceedings of the 12th international conference on Job scheduling strategies for parallel processing10.5555/1757044.1757046(33-46)Online publication date: 26-Jun-2006
https://dl.acm.org/doi/10.5555/1757044.1757046
Zhang BMo ZYang GZheng W(2005)Scheduling efficiently for irregular load distributions in a large-scale clusterProceedings of the Third international conference on Parallel and Distributed Processing and Applications10.1007/11576235_8(39-48)Online publication date: 2-Nov-2005
https://dl.acm.org/doi/10.1007/11576235_8
Nandy SCarter LFerrante J(2004)A-FASTProceedings of the 11th international conference on High Performance Computing10.1007/978-3-540-30474-6_40(363-374)Online publication date: 19-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30474-6_40
González JLeón CRodríguez C(2004)A distributed divide and conquer skeletonProceedings of the 7th international conference on Applied Parallel Computing: state of the Art in Scientific Computing10.1007/11558958_57(481-489)Online publication date: 20-Jun-2004
https://dl.acm.org/doi/10.1007/11558958_57
van Nieuwpoort RKielmann TBal H(2001)Efficient load balancing for wide-area divide-and-conquer applicationsACM SIGPLAN Notices10.1145/568014.37956336:7(34-43)Online publication date: 18-Jun-2001
https://dl.acm.org/doi/10.1145/568014.379563
van Nieuwpoort RKielmann TBal HHeath MLumsdaine A(2001)Efficient load balancing for wide-area divide-and-conquer applicationsProceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming10.1145/379539.379563(34-43)Online publication date: 18-Jun-2001
https://dl.acm.org/doi/10.1145/379539.379563

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents