Automatic memory management makes programming easier. This is also true for general purpose GPU computing where currently no garbage collectors exist. In this paper we present a parallel mark-and-sweep collector to collect GPU memory on the GPU and tune its performance. Performance is increased by: (1) data-parallel marking and sweeping of regions of memory, (2) marking all elements of large arrays in parallel, (3) trading recursion over parallelism to match deeply linked data structures.

Abstract Typical computational grid users target only a single cluster and have to estimate the runtime of their jobs. Job schedulers prefer short‐running jobs to maintain a high system utilization. If the user underestimates the runtime, premature termination causes computation loss; overestimation is penalized by long queue times. As a solution, we present an automatic reparallelization and migration of OpenMP applications. A reparallelization is dynamically computed for an OpenMP work distribution when the number of CPUs changes. The application can be migrated between clusters when an allocated time slice is exceeded. Migration is based on a coordinated, heterogeneous checkpointing algorithm. Both reparallelization and migration enable the user to freely use computing time at more than a single point of the grid. Our demo applications successfully adapt to the changed CPU setting and smoothly migrate between, for example, clusters in Erlangen, Germany, and Amsterdam, the Netherlands, that use different kinds and numbers of processors. Benchmarks show that reparallelization and migration impose average overheads of about 4 and 2%, respectively. Copyright © 2008 John Wiley & Sons, Ltd.

Typical computational grid users target only a single cluster and have to estimate the runtime of their jobs. Job schedulers prefer short-running jobs to maintain a high system utilization. If the user underestimates the runtime, premature termination causes computation loss; overestimation is penalized by long queue times. As a solution, we present an automatic reparallelization and migration of OpenMP applications. A reparallelization is dynamically computed for an OpenMP work distribution when the number of CPUs changes. The application can be migrated between clusters when an allocated time slice is exceeded. Migration is based on a coordinated, heterogeneous checkpointing algorithm. Both reparallelization and migration enable the user to freely use computing time at more than a single point of the grid. Our demo applications successfully adapt to the changed CPU setting and smoothly migrate between, for example, clusters in Erlangen, Germany, and Amsterdam, the Netherlands, that use different processors. Benchmarks show that reparallelization and migration impose average overheads of about 4% and 2%.

Abstract Although OpenMP is a widely agreed‐upon standard for the C/C++ and Fortran programming languages for the semi‐automatic parallelization of programs for shared memory machines, not much has been done on the binding of OpenMP to Java that targets clusters with distributed memory. This paper presents three major contributions: (1) JaMP is an adaptation of the OpenMP standard to Java that implements a large subset of the OpenMP specification with an expressiveness comparable to that of OpenMP; (2) we suggest a set of extensions that allow a better integration of OpenMP into the Java language; (3) we present our prototype implementation of JaMP in the research compiler Jackal, a software‐based distributed shared memory implementation for Java. We evaluate the performance of JaMP with a set of micro‐benchmarks and with OpenMP versions of the parallel Java Grande Forum (JGF) benchmarks. The micro‐benchmarks show that OpenMP for Java can be implemented without much overhead. The JGF benchmarks achieve a good speed‐up of 5–8 on eight nodes. Copyright © 2007 John Wiley & Sons, Ltd.

Thread migration moves a single call-stack to another machine to improve either load balancing or locality. Current approaches for checkpointing and thread migration are either not heterogeneous or they introduce large runtime overhead. In general, previous approaches add overhead by instrumenting each function in a program. The instrumentation costs are then even incurred when no thread migration is performed. In this respect our system is near-overhead free: nearly no overhead is caused if no migration is performed. Our implementation instead generates meta-functions for each location in the code where a function is called. These functions portably save and rebuild activation records to and from a machine-independent format. Each variable of an activation record is described in terms of its usages in a machine-independent `usage descriptor string' to enable heterogeneous, near overhead free thread migration with as few as possible changes to a compiler. Our resulting thread migration solution is, for example, able to move a thread between an x86 machine (few registers, 32 bits) and an Itanium machine (many registers, 64 bits). Furthermore, we (optionally) move the decision on when and where to migrate to the application programmer instead of implementing a fixed 'fits-all' heuristics as in previous approaches

Abstract Object combining tries to put objects together that have roughly the same life times in order to reduce strain on the memory manager and to reduce the number of pointer indirections during a program's execution. Object combining works by appending the fields of one object to another, allowing allocation and freeing of multiple objects with a single heap (de)allocation. Unlike object inlining, which will only optimize objects where one has a (unique) pointer to another, our optimization also works if there is no such relation. Object inlining also directly replaces the pointer by the inlined object's fields. Object combining leaves the pointer in place to allow more combining. Elimination of the pointer accesses is implemented in a separate compiler optimization pass. Unlike previous object inlining systems, reference field overwrites are allowed and handled, resulting in much more aggressive optimization. Our object combining heuristics also allow unrelated objects to be combined, for example, those allocated inside a loop; recursive data structures (linked lists, trees) can be allocated several at a time and objects that are always used together can be combined. As Java explicitly permits code to be loaded at runtime and allows the new code to contribute to a running computation, we do not require a closed‐world assumption to enable these optimizations (but it will increase performance). The main focus of object combining in this paper is on reducing object (de)allocation overhead, by reducing both garbage collection work and the number of object allocations. Reduction of memory management overhead causes execution time to be reduced by up to 35%. Indirection removal further reduces execution time by up to 6%. Copyright © 2005 John Wiley & Sons, Ltd.

We further increase the efficiency of Java RMI programs. Where other optimizing re-implementations of RMI use pre-processors to create stubs and skeletons and to create class specific serializers and deserializers, this paper demonstrates that with transformations based on compile time analysis, an additional 18% performance gain can be achieved over class specific serializers alone for a simple scientific application. A novel and RMI-specific version of static heap analysis is used to derive information about objects that are passed as arguments of remote method invocations. This knowledge of objects and their interrelations is used for three optimizations. First, dynamic introspection and/or (recursive) dynamic invocations of object specific serializers is slow. With knowledge from our heap analysis, the marshaling of graphs of argument objects can be inlined at the call site. Hence, many method table lookups and skeleton indirections of previous approaches can be avoided and less protocol information is sent over the network. Secondly, because object graphs may be passed as RMI arguments, cyclic references need to be detected. With our heap analysis, we can detect if there is no potential for cycles and hence, cycle detection code can be left out of the serialization and marshaling codes. Finally, object arguments to remote methods cause object creation and garbage collection. Heap analysis and an RMI-specific version of escape analysis allows the reuse of object graphs created in earlier remote invocations.

Abstract Jackal is a fine‐grained distributed shared memory implementation of the Java programming language. Jackal implements Java's memory model and allows multithreaded Java programs to run unmodified on distributed‐memory systems. This paper focuses on Jackal's run‐time system, which implements a multiple‐writer, home‐based consistency protocol. Protocol actions are triggered by software access checks that Jackal's compiler inserts before object and array references. To reduce access‐check overhead, the compiler exploits source‐level information and performs extensive static analysis to optimize, lift, and remove access checks. We describe optimizations for Jackal's run‐time system, which mainly consists of discovering opportunities to dispense with flushing of cached data. We give performance results for different run‐time optimizations, and compare their impact with the impact of one compiler optimization. We find that our run‐time optimizations are necessary for good Jackal performance, but only in conjunction with the Jackal compiler optimizations described by Veldema et al. As a yardstick, we compare the performance of Java applications run on Jackal with the performance of equivalent applications that use a fast implementation of Java's Remote Method Invocation instead of shared memory. Copyright © 2003 John Wiley & Sons, Ltd.

This paper describes and evaluates the use of aggressive static analysis in Jackal, a fine-grain Distributed Shared Memory (DSM) system for Java. Jackal uses an optimizing, source-level compiler rather than the binary rewriting techniques employed by most other fine-grain DSM systems. Source-level analysis makes existing access-check optimizations (e.g., access-check batching) more effective and enables two novel fine-grain DSM optimizations: object-graph aggregation and automatic computation migration.

Java offers interesting opportunities for parallel computing. In particular, Java Remote Method Invocation (RMI) provides a flexible kind of remote procedure call (RPC) that supports polymorphism. Sun's RMI implementation achieves this kind of flexibility at the cost of a major runtime overhead. The goal of this article is to show that RMI can be implemented efficiently, while still supporting polymorphism and allowing interoperability with Java Virtual Machines (JVMs). We study a new approach for implementing RMI, using a compiler-based Java system called Manta. Manta uses a native (static) compiler instead of a just-in-time compiler. To implement RMI efficiently, Manta exploits compile-time type information for generating specialized serializers. Also, it uses an efficient RMI protocol and fast low-level communication protocols.A difficult problem with this approach is how to support polymorphism and interoperability. One of the consequences of polymorphism is that an RMI implementation must be able to download remote classes into an application during runtime. Manta solves this problem by using a dynamic bytecode compiler, which is capable of compiling and linking bytecode into a running application. To allow interoperability with JVMs, Manta also implements the Sun RMI protocol (i.e., the standard RMI protocol), in addition to its own protocol.We evaluate the performance of Manta using benchmarks and applications that run on a 32-node Myrinet cluster. The time for a null-RMI (without parameters or a return value) of Manta is 35 times lower than for the Sun JDK 1.2, and only slightly higher than for a C-based RPC protocol. This high performance is accomplished by pushing almost all of the runtime overhead of RMI to compile time. We study the performance differences between the Manta and the Sun RMI protocols in detail. The poor performance of the Sun RMI protocol is in part due to an inefficient implementation of the protocol. To allow a fair comparison, we compiled the applications and the Sun RMI protocol with the native Manta compiler. The results show that Manta's null-RMI latency is still eight times lower than for the compiled Sun RMI protocol and that Manta's efficient RMI protocol results in 1.8 to 3.4 times higher speedups for four out of six applications.

Java's support for parallel and distributed processing makes the language attractive for metacomputing applications, such as parallel applications that run on geographically distributed (wide-area) systems. To obtain actual experience with a Java-centric approach to metacomputing, we have built and used a high-performance wide-area Java system, called Manta. Manta implements the Java Remote Method Invocation (RMI) model using different communication protocols (active messages and TCP/IP) for different networks. The paper shows how wide-area parallel applications can be expressed and optimized using Java RMI. Also, it presents performance results of several applications on a wide-area system consisting of four Myrinet-based clusters connected by ATM WANs. We finally discuss alternative programming models, namely object replication, JavaSpaces, and MPI for Java. Copyright © 2000 John Wiley & Sons, Ltd.

Java offers interesting opportunities for parallel computing. In particular, Java Remote Method Invocation provides an unusually flexible kind of Remote Procedure Call. Unlike RPC, RMI supports polymorphism, which requires the system to be able to download remote classes into a running application. Sun's RMI implementation achieves this kind of flexibility by passing around object type information and processing it at run time, which causes a major run time overhead. Using Sun's JDK 1.1.4 on a Pentium Pro/Myri.net cluster, for example, the latency for a null RMI (without parameters or a return value) is 1228 μsec, which is about a factor of 40 higher than that of a user-level RPC. In this paper, we study an alternative approach for implementing RMI, based on native compilation. This approach allows for better optimization, eliminates the need for processing of type information at run time, and makes a light weight communication protocol possible. We have built a Java system based on a native compiler, which supports both compile time and run time generation of marshallers. We find that almost all of the run time overhead of RMI can be pushed to compile time. With this approach, the latency of a null RMI is reduced to 34 μsec, while still supporting polymorphic RMIs (and allowing interoperability with other JVMs).