Abstract
The nested data-parallel programming model supports the design and implementation of irregular parallel algorithms. This paper describes work in progress to incorporate nested data parallelism into the object model of Java by developing a library of collection classes and adding a forall statement to the language. The collection classes provide parallel implementations of operations on the collections. The forall statement allows operations over the elements of a collection to be expressed in parallel. We distinguish between shape and data components in the collection classes, and use this distinction to simplify algorithm expression and to improve performance. We present initial performance data on two benchmarks with irregular algorithms, EM3d and Convex Hull, and on several microbenchmark programs.
This research is supported in part by the National Science Foundation under grant CCR-9711438.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
K. Arnold and J. Gosling. The Java TM Programming Language. The JavaTM Series. Addison-Wesley Publishing Company, 1996.
C. C. Ashcraft. The domain/segment partition for the factorization of sparse symmetric positive definite matrices. Engineering Computing & Analysis Technical Report ECA-TR-148, Boeing Computer Services, Seattle, WA, Nov. 1990.
D. F. Bacon et al. Thin locks: featherweight synchronization for Java. In Proc. PLDI’98, pages 258–268, 1998.
R. Biswas and R. C. Strawn. A new procedure for dynamic adaption of three-dimensional unstructured grids. Applied Numerical Mathematics, 13:437–452, 1994.
G. E. Blelloch. Vector Models for Data-Parallel Computing. The MIT Press, Cambridge, MA, 1990.
G. E. Blelloch. Nesl: A nested data-parallel language (version 2.6). Technical Report CMU-CS-93-129, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, Apr. 1993. Updated version of CMU-CS-92-103, January 1992.
G. E. Blelloch et al. Implementation of a portable nested data-parallel language. JPDC, 21(1):4–14, Apr. 1994.
B. L. Blount and S. Chatterjee. An evaluation of Java for numerical computing. In Proc. ISCOPE’98, Dec. 1998. LNCS 1505, pp. 35–46, Springer Verlag.
R. D. Blumofe et al. Cilk: An efficient multithreaded runtime system. In Proc. PPoPP’95, pages 207–216, Santa Barbara, CA, July 1995. ACM.
J. A. Board Jr. et al. Scalable variants of multipole-accelerated algorithms for molecular dynamics applications. Technical Report TR94-006, Department of Electrical Engineering, Duke University, Durham, NC, 1994.
F. Bodin et al. Implementing a parallel C++ runtime system for scalable parallel systems. In Proc. SC’93, pages 588–597, November 1993.
A. A. Chien and J. Dolby. ICC++: AC++ dialect for high-performance parallel computation. In Proc. ISOTAS’96, Mar. 1996.
D. E. Culler et al. Parallel programming in Split-C. In Proc. SC’93, pages 262–273, Nov. 1993.
G. C. Fox. Java for high performance scientific and engineering computing. http://www.npac.syr.edu/projects/javaforcse/.
D. B. Gannon. High Performance Java. http://www.extreme.indiana.edu/hpJava/index.html.
High Performance Fortran Forum. High Performance Fortran language specification. Scientific Programming, 2(1–2):1–170, 1993.
Y. Hu, S. L. Johnsson, and S.-H. Teng. High Performance FORTRAN for Highly Irregular Problems. In Proc. PPoPP’97, pages 13–24, June 1997.
S. F. Hummel, T. Ngo, and H. Srinivasan. SPMD programming in Java. Concurrency: Practice and Experience, 9(6):621–631, June 1997. Special issue on Java for computational science and engineering—simulation and modeling.
Java Grande Forum. The Java Grande Forum charter document. http://www.npac.syr.edu/javagrande/jgfcharter.html.
A. Krall and M. Probst. Monitors and Exceptions: How to implement Java efficiently. Concurrency: Practice and Experience, 10(11):837–850, Sept. 1998.
X. S. Li. Sparse Gaussian Elimination on High Performance Computers. PhD thesis, Department of Computer Science, University of California at Berkeley, Berkeley, CA, Sept. 1996. Available as technical report CSD-96-919.
L. S. Nyland, J. F. Prins, and J. H. Reif. A data-parallel implementation of the fast multipole algorithm. In Proc. DAGS’93, pages 111–122, Hanover, NH, June 1993.
M. Odersky and P. Wadler. Pizza into Java: Translating theory into practice. In Proc. POPL’97 Jan. 1997.
M. Philippsen. Data parallelism in Java. In J. Schaefer, editor, High Performance Computing Systems and Applications. Kluwer Academic Publishers, Boston, Dordrecht, London, 1998.
J. Prins, S. Chatterjee, and M. Simons. Expressing irregular computations in modern Fortran dialects. In D. O’Hallaron, editor, Languages, Compilers, and Run-Time Systems for Scalable Computers, pages 1–16. Springer, 1998. LNCS 1511.
K. E. Schmidt and M. A. Lee. Implementing the fast multipole algorithm in three dimensions. Journal of Statistical Physics, 63(5/6), 1991.
T. J. Sheffler and S. Chatterjee. An object-oriented approach to nested data parallelism. In Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation, pages 203–210, McLean, VA, Feb. 1995.
M. Snir et al. MPI: The Complete Reference. MIT Press, 1996.
The Java collections framework. http://java.sun.com/products/jdk/1.2/docs/api/index.html.
K. Yelick et al. Titanium: A high-performance Java dialect. Concurrency: Practice and Experience, 10(11):825–836, Sept. 1998.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag
About this paper
Cite this paper
Blount, B., Chatterjee, S., Philippsen, M. (1999). Irregular parallel algorithms in Java. In: Rolim, J., et al. Parallel and Distributed Processing. IPPS 1999. Lecture Notes in Computer Science, vol 1586. Springer, Berlin, Heidelberg . https://doi.org/10.1007/BFb0097988
Download citation
DOI: https://doi.org/10.1007/BFb0097988
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65831-3
Online ISBN: 978-3-540-48932-0
eBook Packages: Springer Book Archive