Virtual-machine images are currently distributed as disk-image files, which are files that mirror the content of disks. This format is convenient for the virtual machine monitors that execute these images. However, it is not well-suited for administering images because storing images as disk-image files forces administrators to maintain the software on images with the same tools that they use to maintain the software on machines. Already, these tools cannot cope with physical server sprawl; in the future, because images can be snapshotted and cloned easily, enterprises that migrate from machines to images will need tools that scale to cope with the larger problem of virtual-machine image sprawl.To address this problem, this paper proposes the Mirage image format (MIF), a new storage format that exposes the rich semantic information currently buried in disk-image files. Disk-image files contain a mapping from file name to file content (and file metadata). MIF decouples this mapping into a manifest that maps file names to content descriptors (and file metadata) and a store that holds the content. Each image has its own manifest and a store may contain content for many images. As with disk-image files, images in MIF fully encapsulate application state including all software dependences. In addition, conversion between MIF and traditional disk-image formats is easy.This paper shows, through examples, that MIF makes some typical software management tasks--inventory control, customized deployment, and image update--faster and easier. The general technique is to operate on manifests instead of on content whenever possible. These tasks can be performed without starting images and, because manifests are simpler and orders of magnitude smaller than disk-image files, without accessing large amounts of data.

The Progressive Deployment System (PDS) is a virtual execution environment and infrastructure designed specifically for deploying software, or on demand while enabling management from a central location. PDS intercepts a select subset of system calls on the target machine to provide a partial virtualization at the operating system level. This enables an asset's install-time environment to be reproduced virtually while otherwise not isolating the asset from peer applications on the target machine. Asset components, or shards, are fetched as they are needed (or they may be pre-fetched), enabling the asset to be progressively deployed by overlapping deployment with execution. Cryptographic digests are used to eliminate redundant shards within and among assets, which enables more efficient deployment. A framework is provided for intercepting interfaces above the operating system (e.g., Java class loading), enabling optimizations requiring semantic awareness not present at the OS level. The paper presents the design of PDS, motivates its porous isolation model with respect to the challenges of software deployment, and presents measurements of PDS's execution characteristics.

In this paper, we present an approach to automatically detect high impact coding errors in large Java applications which use frameworks. These high impact errors cause serious performance degradation and outages in real world production environments, are very time-consuming to detect, and potentially cost businesses thousands of dollars. Based on 3 years experience working with IBM customer production systems, we have identified over 400 high impact coding patterns, from which we have been able to distill a small set of pattern detection algorithms. These algorithms use deep static analysis, thus moving problem detection earlier in the development cycle from production to development. Additionally, we have developed an automatic false positive filtering mechanism based on domain specific knowledge to achieve a level of usability acceptable to IBM field engineers. Our approach also provides necessary contextual information around the sources of the problems to help in problem remediation. We outline how our approach to problem determination can be extended to multiple programming models and domains. We have implemented this problem determination approach in the SABER tool and have used it successfully to detect many serious code defects in several large commercial applications. This paper shows results from four such applications that had over 60 coding defects.

Development of multithreaded applications is particularly tricky because of their non-deterministic execution behaviors. Tools that support the debugging and performance timing of such applications are needed. Key to the construction of such tools is the ability to repeat the nondeterministic execution behavior of a multithreaded application. A clean separation between the application and the system that runs it facilitates supporting that ability. This paper presents a platform for constructing such tools in a context in which any separation between the application and the underlying system (and between both and the platform's own instrumentation code) has been obscured. DejaVu supports deterministic replay of nondeterministic executions of multithreaded Java programs on the Jalapeno virtual machine (running on a uniprocessor). Jalapeno is written in Java and its optimizing compiler regularly integrates application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. DejaVu ensures deterministic replay through symmetric instrumentation-side-effect identical instrumentation in both record and replay modes-and remote reflection which exposes the state of an application without perturbing it.

Single superclass inheritance enables simple and efficient table-driven virtual method dispathc. However, virtual method table dispatch does not handle multiple inheritance and interfaces. This complication has led to a widespread misimpression that interface method dispatch is inherently inefficient. This paper argues that with proper implementation techniques, Java interfaces need not be a source of significant performance degradation.

Jalape~no is a virtual machine for Java TM servers written in Java. A running Java program involves four layers of functionality: the user code, the virtual-machine, the operating system, and the hardware. By drawing the Java / non-Java boundary below the virtual machine rather than above it, Jalape~no reduces the boundary-crossing overhead and opens up more opportunities for optimization. To get Jalape~no started, a boot image of a working Jalape ~no virtual machine is concocted and written to a file. Later, this file can be loaded into memory and executed. Because the boot image consists entirely of Java objects, it can be concocted by a Java program that runs in any JVM. This program uses reflection to convert the boot image into Jalape~no's object format. A special Magic class allows unsafe casts and direct access to the hardware. Methods of this class are recognized by Jalape~no's three compilers, which ignore their bytecodes and emit special-purpose machine code. User code w...

The Smith-Waterman algorithm is a computationally-intensive string-matching operation that is fundamental to the analysis of proteins and genes. In this paper, we explore the use of some standard and novel techniques for improving its performance. We begin by tuning the algorithm using conventional techniques. These make modest performance improvements by providing efficient cache usage and inner-loop code. One novel technique uses the z-buffer operations of the Intel i860 architecture to perform 4 independent computations in parallel. This achieves a five-fold speedup over the optimized code (six-fold over the original). We also describe a related technique that could be used by processors that have 64-bit integer operations, but no z-buffer. Another new technique uses floating-point multiplies and adds in place of the standard algorithm's integer additions and maximum operations. This gains more than a three-fold speedup on the IBM POWER2 processor. This method doesn't give the identical answers as the original program, but experimental evidence shows that the inaccuracies are small and do not affect which strings are chosen as good matches by the algorithm.

The set of possible orientations of a rigid three-dimensional object is a topological space with three degrees of freedom. This paper investigates the suitability of various techniques of visualizing this space. With a good technique the natural distance between orientations will be represented fairly accurately, and distortion to the "shape" of a collection of orientations induced by the change of reference orientation will be minor. The traditional Euler-angle parameterization fails on both counts. Less well-known techniques exploit the fact that there is a rotation that takes the reference orientation to a given one. The given orientation is represented as a point along the axis of this rotation. The distance of this point from the origin is determined by some scaling function of the magnitude of that rotation. Free natural scaling functions are studied. None is perfect, but several are satisfactory.>

A hyperbox is a two-dimensional depiction of an N-dimensional box (rectangular parallelepiped). The authors define the visual syntax of hyperboxes, state some properties, and sketch two applications. Hyperboxes can be evocative visual names for tensors or multidimensional arrays in visual programming languages. They can also be used to simultaneously display all pairwise relationships in an N-dimensional dataset. This can be helpful in choosing a sequence of dimension-reducing transformations that preserve interesting properties of the dataset.>

The authors introduce a model, called the uniform memory hierarchy (UMH) model, which reflects the hierarchical nature of computer memory more accurately than the RAM (random-access-machine) model, which assumes that any item in memory can be accessed with unit cost. In the model memory occurs as a sequence of increasingly large levels. Data are transferred between levels in fixed-size blocks (the size is level dependent). Within a level blocks are random access. The model is easily extended to handle parallelism. The UMH model is really a family of models parameterized by the rate at which the bandwidth decays as one travels up the hierarchy. A program is parsimonious on a UMH if the leading terms of the program's (time) complexity on the UMH and on a RAM are identical. If these terms differ by more than a constant factor, then the program is inefficient. The authors analyze two standard FFT programs with the same RAM complexity. One is efficient; the other is not.>

The authors describe a conceptual model, the memory hierarchy framework, and a visual language for using the model. The model is more faithful to the structure of computers than the Von Neumann and Turing models. It addresses the issues of data movement and exposes and unifies storage mechanisms such as cache, translation lookaside buffers, main memory, and disks. The visual language presents the details of a computer's memory hierarchy in a concise drawing composed of rectangles and connecting segments. Using this framework, the authors improved the performance of a matrix multiplication algorithm by more than an order of magnitude. The framework gives insight into computer architecture and performance bottlenecks by making effective use of human visual abilities.>

An approach to proving temporal properties of concurrent programs that does not use temporal logic as an inference system is presented. The approach is based on using Buchi automata to specify properties. To show that a program satisfies a given property, proof obligations are derived from the Buchi automata specifying that property. These obligations are discharged by devising suitable invariant assertions and variant functions for the program. The approach is shown to be sound and relatively complete. A mutual exclusion protocol illustrates its application.

Article Free Access Share on Detecting equality of variables in programs Authors: B. Alpern IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , M. N. Wegman IBM Thomas J. Watson Research Center, Yorktown Heights, NY IBM Thomas J. Watson Research Center, Yorktown Heights, NYView Profile , F. K. Zadeck Department of Computer Science, Brown University, Providence, RI Department of Computer Science, Brown University, Providence, RIView Profile Authors Info & Claims POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languagesJanuary 1988 Pages 1–11https://doi.org/10.1145/73560.73561Published:13 January 1988Publication History 264citation2,559DownloadsMetricsTotal Citations264Total Downloads2,559Last 12 Months137Last 6 weeks21 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Access to memory location x is assumed to take time ⌈ log x ⌉. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. It is shown that the circuit simulation problem has inherently poor locality of reference. The results are extended to HMM's where memory access time is given by an arbitrary (nondecreasing) function. Tight upper and lower bounds are obtained for HMM's with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. On-line memory management algorithms for the HMM model are also considered. An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal.

Knowledge of logical inference rules allows a specialized proof editor to provide a user with feedback about errors in a proof under development. Providing such feedback involves checking a collection of constraints on the strings of the proof language. Because attribute grammars allow such constraints to be expressed in a modular, declarative fashion, they are a suitable underlying formalism for a proof-checking editor. This paper discusses how an attribute grammar can be used in an editor for partial-correctness program proofs in Hoare-style logic, where verification conditions are proved using the sequent calculus.