Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

No abstract available.

No abstract available.

Modern, resource-intensive enterprise and scientific applications are increasingly architected using parallel and distributed components deployed on grid platforms. Grid environments are typically heterogeneous and subject to large load variations. Such characteristics require a portable programming infrastructure and comprehensive support for resource management as well as dynamic adaptation to varying resource availability. Resource-aware applications pro-actively monitor and dynamically adapt their behavior to accommodate to changing resource consumption constraints. Strategies such as internal load-balancing and job re-submission can correct sub-optimal scheduling decisions and thus enhance performance. As utilizing the potential of resource awareness requires close interaction with resource management subsystems, implementations often rely on low-level, platform-specific features, which impair portability. What is needed is uncompromised portability of all aspects of resource management in grid systems. We demonstrate that the Java platform, equipped with the APIs for distributed resource management, can be used for building a portable grid infrastructure. In particular, we describe the design and implementation of a cluster management system capable of controlled execution of parallel, resource-aware Java applications. We empirically show that our solution allows for efficient, fine-grained resource management, sufficient for tapping the performance benefits promised by the resource-conscious applications.

The Java™ 2 Platform, Enterprise Edition (J2EE™), is established as the standard platform for hosting enterprise applications written in the Java programming language. Similar to an operating system, a J2EE server can host multiple applications, but this is problematic due to limitations on scalability, weak inter-application isolation and inadequate resource management facilities in the underlying Java platform. These limitations lead to a proliferation of server instances with a consequent dramatic increase in the total memory footprint and more complex system administration. The Multi-tasking Virtual Machine (MVM) solves this problem by providing an efficient and scalable implementation of the isolate API for multiple, isolated tasks, enabling the co-location of multiple server instances in a single MVM process. Isolates also enable the restructuring of a J2EE server implementation as a collection of isolated components, offering increased flexibility and reliability. The resulting system is a step towards a complete and scalable operating environment for enterprise applications. Copyright © 2006 John Wiley & Sons, Ltd.

Enterprise applications are increasingly being built using type-safe programming platforms and deployed over horizontally scalable systems. Horizontal scalability depends crucially on the ability to monitor resource usage and to define and enforce resource management policies capable of guaranteeing a desired service level. However, current safe language platforms have very limited support for resource management, and their cluster-enabled versions reflect this deficiency. We describe an architecture of federated Java/spl trade/ virtual machines. Its distinguishing feature is an integrated resource management interface that addresses the above issues. It offers programmatic control over monitoring and controlling the allocation of resources to applications and their components. The scope of each policy can span multiple nodes, realizing finegrained control. New resource types can be defined and integrated into the framework. Remote management of local resources and the notion of cluster-global resources form a powerful combination capable of expressing policies that achieve effective performance isolation for cluster applications.

Software systems in many circumstances need awareness of their resource usage. Meeting performance requirements often requires the ability to manage consumption of resources provided by the environment. Resource management is traditionally handled by operating systems, but the growing need to use safe languages in the systems programming domain adds increased pressure to equip them with resource management capabilities at a level of abstraction that fits gracefully with the language. This paper proposes an extensible, flexible, and widely applicable resource management interface for the Java platform. The interface is small, but capable of modeling a variety of resources and resource management policies. In particular, application-specific resources can be defined, as well as more traditional computational resources such as heap memory and processor time. The interface is presented here in detail, along with a series of examples and a description of a prototype implementation. Copyright © 2004 John Wiley & Sons, Ltd.

Executing computations in a single instance of safe language virtual machine can improve performance and overall platform scalability. It also poses various challenges. One of them is providing a fast inter-application communication mechanism. In addition to being efficient, such a mechanism should not violate any functional and non-functional properties of its environment, and should also support enforcement of application-specific security policies. This paper explores the design and implementation of a communication substrate for applications executing within a single Java virtual machine modified to enable safe and interference-free execution of isolated computations. Designing an efficient extension that does not break isolation properties and at the same time pragmatically offers an intuitive API has proven non-trivial. This paper demonstrates a set of techniques that lead to at least an eight-fold performance improvement over the in-process inter-application communication using standard mechanisms offered by the Java platform.

Studies the impact of several lock manager designs on the overhead imposed on a persistent programming language by automated object locking. Our study reveals that a lock management method based on lock-state sharing outperforms more traditional lock management designs. Lock-state sharing is a novel lock management method that represents all lock data structures with equal values with a single shared data structure. Sharing the value of locks has numerous benefits: (i) it makes the space consumed by the lock manager small and independent of the number of locks acquired by transactions, (ii) it eliminates the need for expensive bookkeeping of locks by transactions, and (iii) it enables the use of memoization techniques for whole locking operations. These advantages add up to making the release of locks practically free, and the processing of over 99% of the lock requests takes between eight and 14 RISC instructions.

The coexistence of programs written in a safe language with user-supplied unsafe (native) code is convenient (e.g., it enables direct access to operating system resources), but at the same time it is problematic (e.g., it may decrease reliability and debuggability). This work aims at retaining most of the benefits of interfacing a safe language with native code while addressing its problems. It is carried out in the context of the Java/sup TM/ Native Interface (JNI). Our approach is to execute the native code in an operating system process different than that of the safe language application. A technique presented in this paper accomplishes this transparently, automatically,, and without sacrificing any of the JNI functionality. No changes to the Java virtual machine (JVM/sup TM/) or its runtime are necessary. The resulting prototype does not depend on a particular implementation of the JVM, and is highly portable across hardware architectures and operating systems. This approach can be used to improve reliability of applications consisting of a mix of safe and native code and to facilitate debugging them.

The multitasking virtual machine (called from now on simply MVM) is a modification of the Java virtual machine. It enables safe, secure, and scalable multitasking. Safety is achieved by strict isolation of application from one another. Resource control augment security by preventing some denial-of-service attacks. Improved scalability results from an aggressive application of the main design principle of MVM: share as much of the runtime as possible among applications and replicate everything else. The system can be described as a 'no compromise'approach --- all the known APIs and mechanisms of the Java programming language are available to applications. MVM is implemented as a series of carefully tuned modifications to the Java HotSpot virtual machine, including the dynamic compiler. this paper presents the design of MVM, focusing on several novel and general techniques: an in-runtime design of lightweight isolation, an extension of a copying, generational garbage collector to provide best-effort management of a portion of the heap space, and a transparent and automated mechanism for safe execution of user-level native code. MVM demonstrates that multitasking in a safe language can be accomplished with a high degree of protection, without constraining the language, and and with competitive performance characteristics

To date, systems offering multitasking for the Java™ programming language either use one process or one class loader for each application. Both approaches are unsatisfactory. Using operating system processes is expensive, scales poorly and does not fully exploit the protection features inherent in a safe language. Class loaders replicate application code, obscure the type system, and non-uniformly treat 'trusted' and 'untrusted' classes, which leads to subtle, but nevertheless, potentially harmful forms of undesirable inter-application interaction.In this paper we propose a novel, simple yet powerful solution. The new model improves on existing designs in terms of resource utilization while offering strong isolation among applications. The approach is applicable both on high-end servers and on small devices. The main idea is to maintain only one copy of every class, regardless of how many applications use it. Classes are transparently and automatically modified, so that each application has a separate copy of its static fields. Two prototypes are described and selected performance data is analyzed. Various aspects of the proposed architectural changes to the Java Virtual Machine are discussed.

MRPC is an RPC system that is designed and optimized for MPMD parallel computing. Existing systems based on standard RPC incur an unnecessarily high cost when used on high-performance multi-computers, limiting the appeal of RPC-based languages in the parallel computing community. MRPC combines the efficient control and data transfer provided by Active Messages (AM) with a minimal multithreaded runtime system that extends AM with the features required to support MPMD. This approach introduces only the necessary RPC overheads for an MPMD environment. MRPC has been integrated into Compositional C++ (CC++), a parallel extension of C++ that offers an MPMD programming model. Basic performance in MRPC is within a factor of two from those of Split-C, a highly tuned SPMD language, and other messaging layers. CC++ applications perform within a factor of two to six from comparable Split-C versions, which represent an order of magnitude improvement over previous CC++ implementations. Copyright © 1999 John Wiley & Sons, Ltd.

With the spread of the Internet the computing model on server systems is undergoing several important changes. Recent research ideas concerning dynamic operating system extensibility are finding their way into the commercial domain, resulting in designs of extensible databases and Web servers. In addition, both ordinary users and service providers must deal with untrusted downloadable executable code of unknown origin and intentions.Across the board, Java has emerged as the language of choice for Internet-oriented software. We argue that, in order to realize its full potential in applications dealing with untrusted code, Java needs a flexible resource accounting interface. The design and prototype implementation of such an interface --- JRes --- is presented in this paper. The interface allows to account for heap memory, CPU time, and network resources consumed by individual threads or groups of threads. JRes allows limits to be set on resources available to threads and it can invoke callbacks when these limits are exceeded. The JRes prototype described in this paper is implemented on top of standard Java virtual machines and requires only a small amount of native code.

Global addressing of shared data simplifies parallel programming and complements message passing models commonly found in distributed memory machines. A number of programming systems have been designed that synthesize global addressing purely in software on such machines. These systems provide a number of communication mechanisms to mitigate the effect of high communication latencies and overheads. This study compares the mechanisms in two representative all-software systems: CRL and Split-C. CRL uses region-based caching while Split-C uses split-phase and push-based data transfers for optimizing communication performance. Both systems take advantage of bulk data transfers. By implementing a set of parallel applications in both CRL and Split-C, and running them on the IBM SP2, Meiko CS-2 and two simulated architectures, we find that split-phase and push-based bulk data transfers are essential for good performance. Regionbased caching benefits applications with irregular structure and w...

The MPMD approach for parallel computing is attractive for programmers who seek fast development cycles, high code re-use, and modular programming, or whose applications exhibit irregular computation loads and communication patterns. RPC is widely adopted as the communication abstraction for crossing address space boundaries. However, the communication overheads of existing RPC-based systems are usually an order of magnitude higher than those found in highly tuned SPMD systems. This problem has thus far limited the appeal of high-level programming languages based on MPMD models in the parallel computing community.This paper investigates the fundamental limitations of MPMD communication using a case study of two parallel programming languages, Compositional C++ (CC++) and Split-C, that provide support for a global name space. To establish a common comparison basis, our implementation of CC++ was developed to use MRPC, a RPC system optimized for MPMD parallel computing and based on Active Messages. Basic RPC performance in CC++ is within a factor of two from those of Split-C and other messaging layers. CC++ applications perform within a factor of two to six from comparable Split-C versions, which represent an order of magnitude improvement over previous CC++ implementations. The results suggest that RPC-based communication can be used effectively in many high-performance MPMD parallel applications.

The IBM SP is one of the most powerful commercial MPPs, yet, in spite of its fast processors and high network bandwidth, the SP's communication latency is inferior to older machines such as the TMC CM-5 or Meiko CS-2. This paper investigates the use of Active Messages (AM) communication primitives as an alternative to the standard message passing in order to reduce communication overheads and to offer a good building block for higher layers of software. The first part of this paper describes an implementation of Active Messages (SP AM) which is layered directly on top of the SP's network adapter (TB2). With comparable bandwidth, SP AM's low overhead yields a round-trip latency that is 40% lower than IBM MPL's. The second part of the paper demonstrates the power of AM as a communication substrate by layering Split-C as well as MPI over it. Split-C benchmarks are used to compare the SP to other MPPs and show that low message overhead and high throughput compensate for SP's high network latency. The MPI implementation is based on the freely available MPICH version and achieves performance equivalent to IBM's MPI-F on the NAS benchmarks.

The goal of the paper is to describe run time efficiency of distributed computing environments. Six tools: PVM, P4, ANSA, SR, Strand, and Linda were chosen and investigated because they represent different approaches to distributed programming systems construction. The experimental results of communication tests and processor farm model efficiency are presented and discussed.>