This paper describes split-stream dictionary (SSD) compression, a new technique for transforming programs into a compact, interpretable form. We define a compressed program as interpretable when it can be decompressed at basic-block granularity with reasonable efficiency. The granularity requirement enables interpreters or just-in-time (JIT) translators to decompress basic blocks incrementally during program execution. Our previous approach to interpretable compression, the Byte-coded RISC (BRISC) program format [1], achieved unprecedented decompression speed in excess of 5 megabytes per second on a 450MHz Pentium II while compressing benchmark programs to an average of three-fifths the size of their optimized x86 representation. SSD compression combines the key idea behind BRISC with new observations about instruction re-use frequencies to yield four advantages over BRISC and other competing techniques. First, SSD is simple, requiring only a few pages of code for an effective implementation. Second, SSD compresses programs more effectively than any interpretable program compression scheme known to us. For example, SSD compressed a set of programs including the spec95 benchmarks and Microsoft Word97 to less than half the size, on average, of their optimized x86 representation. Third, SSD exceeds BRISC's decompression and JIT translation rates by over 50%. Finally, SSD's two-phased approach to JIT translation enables a virtual machine to provide graceful degradation of program execution time in the face of increasing RAM constraints. For example, using SSD, we ran Word97 using a JIT-translation buffer one-third the size of Word97's optimized x86 code, yet incurred only 27% execution time overhead.

Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially.For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead.This paper describes:• Measurements that show how code compression can save space and total time in some important real-world scenarios.• A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120MHz Pentium processor• A compressed "wire" representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.

This paper evaluates the design and implementation of Omniware: a safe, efficient, and language-independent system for executing mobile program modules. Previous approaches to implementing mobile code rely on either language semantics or abstract machine interpretation to enforce safety. In the former case, the mobile code system sacrifices universality to gain safety by dictating a particular source language or type system. In the latter case, the mobile code system sacrifices performance to gain safety through abstract machine interpretation.Omniware uses software fault isolation, a technology developed to provide safe extension code for databases and operating systems, to achieve a unique combination of language-independence and excellent performance. Software fault isolation uses only the semantics of the underlying processor to determine whether a mobile code module can corrupt its execution environment. This separation of programming language implementation from program module safety enables our mobile code system to use a radically simplified virtual machine as its basis for portability. We measured the performance of Omniware using a suite of four SPEC92 programs on the Pentium, PowerPC, Mips, and Sparc processor architectures. Including the overhead for enforcing safety on all four processors, OmniVM executed the benchmark programs within 21% as fast as the optimized, unsafe code produced by the vendor-supplied compiler.

Many parallel programs contain multiple sub-computations, each with distinct communication and load balancing requirements. The traditional approach to compiling such programs is to impose a processor synchronization barrier between sub-computations, optimizing each as a separate entity. This paper develops a methodology for managing the interactions among sub-computations, avoiding strict synchronization where concurrent or pipelined relationships are possible.

A data breakpoint associates debugging actions with programmer-specified conditions on the memory state of an executing program. Data breakpoints provide a means for discovering program bugs that are tedious or impossible to isolate using control breakpoints alone. In practice, programmers rarely use data breakpoints, because they are either unimplemented or prohibitively slow in available debugging software. In this paper, we present the design and implementation of a practical data breakpoint facility.

One way to provide fault isolation among cooperating software modules is to place each in its own address space. However, for tightly-coupled modules, this solution incurs prohibitive context switch overhead. In this paper, we present a software approach to implementing fault isolation within a single address space.Our approach has two parts. First, we load the code and data for a distrusted module into its own fault do main, a logically separate portion of the application's address space. Second, we modify the object code of a distrusted module to prevent it from writing or jumping to an address outside its fault domain. Both these software operations are portable and programming language independent.Our approach poses a tradeoff relative to hardware fault isolation: substantially faster communication between fault domains, at a cost of slightly increased execution time for distrusted modules. We demonstrate that for frequently communicating modules, implementing fault isolation in software rather than hardware can substantially improve end-to-end application performance.

This paper develops a methodology for compiling and executing irregular parallel programs. Such programs implement parallel operations whose size and work distribution depend on input data. We show a fundamental relationship between three quantities that characterize an irregular parallel computation: the total available parallelism, the optimal grain size, and the statistical variance of execution times for individual tasks. This relationship yields a dynamic scheduling algorithm that substantially reduces the overhead of executing irregular parallel operations.

Parallel programs display two fundamentally different kinds of execution behavior: synchronous and asynchronous.Some methodologies, such as distributed data structures, are best suited to the construction of asynchronous programs.In this paper, we propose a methodology for synchronous parallel programming based on the notion of a coordination structure, a direct representation of the multidimensional dataflow patterns common to synchronous programs.We introduce Delirium, a language in which one can concisely express many useful coordination structures.

Tarmac, a language system substrate on which systems for distributed parallel programming can be built, is described. A model of shared global state, called mobile memory, which is provided by Tarmac, is discussed. The basic unit of state in this model can be viewed both (1) as a block of memory that can be directly accessed by machine instructions and (2) as a logical entity with a globally unique name that may be efficiently located, copied, and moved. To support higher level synchronization models, the movements of a memory unit may optionally enable computations. The implementation and performance of Tarmac are discussed. Tarmac is contrasted with other systems for parallel distributed programming.>

The authors outline a strategy for expressing coordination of sequential subcomputations, realized in the embedding language Delirium. In contrast to existing embedded languages, the notation clearly expresses the coordination framework of the application. All the coordination required to execute the program is expressed in a unified Delirium program. The program contains the computational code in the form of embedded operators, written using conventional tools. The proposed environment, which executes on a variety of shared-memory multi processors, provides tools which make it possible to develop parallel applications quickly. It supports a coordination model than can guarantee deterministic execution. Programmers who remain within the restrictions of the model can develop a program on a sequential machine and be certain that it will execute deterministically on a variety of parallel architectures.>

Sloop is a parallel language and environment that employs an object-oriented model for explicit parallel programming of MIMD multiprocessors. The Sloop runtime system transforms a network of processors into a virtual object space. A virtual object space contains a collection of objects that cooperate to solve a problem. Sloop encapsulates virtual object space semantics within the object type domain. This system-defined type provides an associative, asynchronous method by which one object gains access to another. It also provides an operation for specifying groups of objects that should, for efficiency, reside on the same physical processor, and supports exploitation of the topology of the underlying parallel machine. Domains also support the creation of indivisible objects, which provide implicit concurrency control. The encapsulation of these semantics within an object gives the programmer the power to construct an arbitrary hierarchy of virtual object spaces, facilitating debugging and program modularity. Sloop implementations are running on a bus-based multiprocessor, a hypercube multiprocessor, and on a heterogeneous network of workstations. The runtime system uses object relocation heuristics and coroutine scheduling to attain high performance.