bluuebunny/crossref_metadata_2025 huggingface dataset:
OoLALA
Authors: Luján Mikel , Freeman T. L. , Gurd John R.
Published: November 2005

In this paper we review the design of a sequential object oriented linear algebra library, O
O
L
A
L
A
. Several designs are proposed and used to classify existing sequential object oriented libraries. The classification is based on the way that matrices and matrix operations are represented. O
O
L
A
L
A
's representation of matrices is capable of dealing with certain matrix operations that, although mathematically valid, are not handled correctly by existing libraries. O
O
L
A
L
A
also enables implementations of matrix calculations at various abstraction levels ranging from the relatively low-level abstraction of a Fortran BLAS-like implementation to higher-level abstractions that hide many implementation details. O
O
L
A
L
A
addresses a wide range of numerical linear algebra functionality while the reviewed object oriented libraries concen trate on parts of such functionality. We include some preliminary performance results for a Java implementation of O
O
L
A
L
A
.
Practical virtual method call resolution for Java
Authors: Sundaresan Vijay , Hendren Laurie , Razafimahefa Chrislain , Vallée-Rai Raja , Lam Patrick , Gagnon Etienne , Godin Charles
Published: November 2005

This paper addresses the problem of resolving virtual method and interface calls in Java bytecode. The main focus is on a new practical technique that can be used to analyze large applications. Our fundamental design goal was to develop a technique that can be solved with only one iteration, and thus scales linearly with the size of the program, while at the same time providing more accurate results than two popular existing linear techniques,
class hierarchy analysis
and
rapid type analysis
.We present two variations of our new technique,
variable-type analysis
and a coarser-grain version called
declared-type analysis
. Both of these analyses are inexpensive, easy to implement, and our experimental results show that they scale linearly in the size of the program.We have implemented our new analyses using the Soot frame-work, and we report on empirical results for seven benchmarks. We have used our techniques to build accurate call graphs for complete applications (including libraries) and we show that compared to a conservative call graph built using class hierarchy analysis, our new variable-type analysis can remove a significant number of nodes (methods) and call edges. Further, our results show that we can improve upon the compression obtained using rapid type analysis.We also provide dynamic measurements of monomorphic call sites, focusing on the benchmark code excluding libraries. We demonstrate that when considering only the benchmark code, both rapid type analysis and our new declared-type analysis do not add much precision over class hierarchy analysis. However, our finer-grained variable-type analysis does resolve significantly more call sites, particularly for programs with more complex uses of objects.
Application isolation in the Java Virtual Machine
Authors: Czajkowski Grzegorz
Published: November 2005

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.
An approach to safe object sharing
Authors: Bryce Ciarán , Razafimahefa Chrislain
Published: November 2005

It is essential for security to be able to isolate mistrusting programs from one another, and to protect the host platform from programs. Isolation is difficult in object-oriented systems because objects can easily become aliased. Aliases that cross program boundaries can allow programs to exchange information without using a system provided interface that could control information exchange. In Java, mistrusting programs are placed in distinct loader spaces but uncontrolled sharing of system classes can still lead to aliases between programs. This paper presents the
object spaces
protection model for an object-oriented system. The model decomposes an application into a set of spaces, and each object is assigned to one space. All method calls between objects in different spaces are mediated by a security policy. An implementation of the model in Java is presented.
Pancode and boxcharts: structured programming revisited
Authors: Jonsson Dan
Published: November 2005

Some new ideas regarding control structures, program charts, and the relationship between the two are presented. It is claimed that the 'pancode' primitives do, if, repeat, else, also, {, and } suffice to build control structures which are more powerful and more readable than those currently used. It is also demonstrated that an equivalent graphical representation of program structure can be obtained by means of 'boxcharts'.
Thread-level parallelism and interactive performance of desktop applications
Authors: Flautner Krisztián , Uhlig Rich , Reinhardt Steve , Mudge Trevor
Published: November 2005

Multiprocessing is already prevalent in servers where multiple clients present an obvious source of thread-level parallelism. However, the case for multiprocessing is less clear for desktop applications. Nevertheless, architects are designing processors that count on the availability of thread-level parallelism. Unlike server workloads, the primary requirement of interactive applications is to respond to user events under human perception bounds rather than to maximize end-to-end throughput. In this paper we report on the thread-level parallelism and interactive response time of a variety of desktop applications. By tracking the communication between tasks, we can focus our measurements on the portions of the benchmark's execution that have the greatest impact on the user. We find that running our benchmarks on a dual-processor machine improves response time of mouse-click events by as much as 36%, and 22% on average---out of a maximum possible 50%. The benefits of multiprocessing are even more apparent when background tasks are considered. In our experiments, running a simple MP3 playback program in the background increases response time by 14% on a uniprocessor while it only increases the response time on a dual processor by 4%. When response times are fast enough for further improvements to be imperceptible, the increased idle time after interactive episodes could be exploited to build systems that are more power efficient.
Frequent value locality and value-centric data cache design
Authors: Zhang Youtao , Yang Jun , Gupta Rajiv
Published: November 2005

By studying the behavior of programs in the SPECint95 suite we observed that six out of eight programs exhibit a new kind of value locality, the
frequent value locality
, according to which a few values appear very frequently in memory locations and are therefore involved in a large fraction of memory accesses. In these six programs ten distinct values occupy over 50% of all memory locations and on an average account for nearly 50% of all memory accesses during program execution. This observation holds for smaller blocks of consecutive memory locations and the set of frequent values remains quite stable over the execution of the program.In the six benchmarks with frequent value locality, on an average 50% of all cache misses occur during the reading or writing of the ten most frequently accessed values. We propose a new data cache structure, the
frequent value cache
(FVC), which employs a
value-centric
approach to caching data locations for exploiting the frequent value locality phenomenon. FVC is a small direct-mapped cache which is dedicated to holding only frequently occurring values. The value-centric nature of FVC enables us to store data in a compressed form where the compression is achieved by encoding the frequent values using a few bits. Moreover this simple compression scheme preserves the random access to data values in a cache line.Our experiments demonstrate that by augmenting a direct mapped cache (DMC) with a direct mapped FVC of size no more than 3 Kbytes we can obtain reductions in miss rates ranging from 1% to 68%. In fact we observed that higher reductions in miss rates can be achieved by augmenting a DMC with a small FVC as opposed to doubling the size of DMC for the 124.m88ksim and 134.perl benchmarks.
Efficient and flexible value sampling
Authors: Burrows M. , Erlingsson Ú , Leung S.-T. A. , Vandevoorde M. T. , Waldspurger C. A. , Walker K. , Weihl W. E.
Published: November 2005

This paper presents novel sampling-based techniques for collecting statistical profiles of register contents, data values, and other information associated with instructions, such as memory latencies. Values of interest are sampled in response to periodic interrupts. The resulting value profiles can be analyzed by programmers and optimizers to improve the performance of production uniprocessor and multiprocessor systems.Our value sampling system extends the DCPI continuous profiling infrastructure, and inherits many of its desirable properties: our value profiler has low overhead (approximately 10% slowdown); it profiles all the code in the system, including the operating system kernel; and it operates transparently, without requiring any modifications to the profiled code.
Architectural support for copy and tamper resistant software
Authors: Lie David , Thekkath Chandramohan , Mitchell Mark , Lincoln Patrick , Boneh Dan , Mitchell John , Horowitz Mark
Published: November 2005

Although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are known. This paper studies the hardware implementation of a form of execute-only memory (XOM) that allows instructions stored in memory to be executed but not otherwise manipulated. To support XOM code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. All data that leaves the machine is encrypted, since we assume external memory is not secure. The design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. We explore some of the potential security issues as one pushes the machine to become more efficient and flexible. Although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in XOM mode. While a virtual XOM machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. For efficient operation, hardware assist to provide fast symmetric ciphers is also required.
Hardware support for dynamic activation of compiler-directed computation reuse
Authors: Connors Daniel A. , Hunter Hillery C. , Cheng Ben-Chung , Hwu Wen-Mei W.
Published: November 2005

Compiler-directed Computation Reuse (CCR) enhances program execution speed and efficiency by eliminating dynamic computation redundancy. In this approach, the compiler designates large program regions for potential reuse. During run time, the execution results of these reusable regions are recorded into hardware buffers for future reuse. Previous work shows that CCR can result in significant performance enhancements in general applications. A major limitation of the work is that the compiler relies on value profiling to identify reusable regions, making it difficult to deploy the scheme in many software production environments. This paper presents a new hardware model that alleviates the need for value profiling at compile time. The compiler is allowed to designate reusable regions that may prove to be inappropriate. The hardware mechanism monitor the dynamic behavior of compiler-designated regions and selectively activates the profitable ones at run time. Experimental results show that the proposed design makes more effective utilization of hardware buffer resources, achieves repid employment of computation regions, and improves reuse accuracy, all of which promote more flexible compiler methods of identifying reusable computation regions.
The functional guts of the Kleisli query system
Authors: Wong Limsoon
Published: November 2005

Kleisli is a modern data integration system that has made a significant impact on bioinformatics data integration. The primary query language provided by Kleisli is called CPL, which is a functional query language whose surface syntax is based on the comprehension syntax. Kleisli is itself implemented using the functional language SML. This paper describes the influence of functional programming research that benefits the Kleisli system, especially the less obvious ones at the implementation level.
Static enforcement of security with types
Authors: Skalka Christian , Smith Scott
Published: November 2005

A number of security systems for programming languages have recently appeared, including systems for enforcing some form of
access control
. The Java JDK 1.2 security architecture is one such system that is widely studied and used. While the architecture has many appealing features, access control checks are all implemented via dynamic method calls. This is a highly non-declarative form of specification which is hard to read, and which leads to additional run-time overhead. In this paper, we present a novel
security type system
that enforces the same security guarantees as Java Stack Inspection, but via a static type system with no additional run-time checks. The system allows security properties of programs to be clearly expressed within the types themselves. We also define and prove correct an inference algorithm for security types, meaning that the system has the potential to be layered on top of the existing Java architecture, without requiring new syntax.
Type-safe cast
Authors: Weirich Stephanie
Published: November 2005

In a language with non-parametric or ad-hoc polymorphism, it is possible to determine the identity of a type variable at run-time. With this facility, we can write a function to convert a term from one abstract type to another, if the two hidden types are identical. However, the naive implementation of this function requires that the term be destructed and rebuilt. In this paper, we show how to eliminate this overhead using higher-order type abstraction. We demonstrate this solution in two frameworks for ad-hoc polymorphism: intensional type analysis and type classes.
Typed compilation of inclusive subtyping
Authors: Crary Karl
Published: November 2005

I present a type-preserving translation that eliminates subtyping and bounded quantification without introducing any run-time costs. This translation is based on Mitchell and Pierce's encoding of bounded quantification using intersection types. I show that, previous negative observations notwithstanding, the encoding is adequate given a sufficiently rich target type theory. The necessary target type theory is made easily typecheckable by including a collection of explicit coercion combinators, which are already desired for eliminating subtyping. However, no form of coercion abstraction is necessary (even to support bounded quantification), leading to a simple target language.
More types for nested data parallel programming
Authors: Chakravarty Manuel M. T. , Keller Gabriele
Published: November 2005

This paper generalises the flattening transformation---a technique for the efficient implementation of nested data parallelism---and reconciles it with main stream functional programming. Nested data parallelism is significantly more expressive and convenient to use than the flat data parallelism typically used in conventional parallel languages like High Performance Fortran and C*. The flattening transformation of Blelloch and Sabot is a key technique for the efficient implementation of nested parallelism via flat parallelism, but originally it was severely restricted, as it did not permit general sum types, recursive types, higher-order functions, and separate compilation. Subsequent work, including some of our own, generalised the transformation and allowed higher-order functions and recursive types. In this paper, we take the final step of generalising flattening to cover the full range of types available in modern languages like Haskell and ML; furthermore, we enable the use of separate compilation. In addition, we present a completely new formulation of the transformation, which is based on the standard lambda calculus notation, and replace a previously ad-hoc transformation step by a systematic generic programming technique. First experiments demonstrate the efficiency of our approach.
Make it practical
Authors: Sasano Isao , Hu Zhenjiang , Takeichi Masato , Ogawa Mizuhito
Published: November 2005

In this paper we propose a new method for deriving a practical linear-time algorithm from the specification of a maximum-weightsum problem: From the elements of a data structure
x
, find a subset which satisfies a certain property
p
and whose weightsum is maximum. Previously proposed methods for automatically generating linear-time algorithms are theoretically appealing, but the algorithms generated are hardly useful in practice due to a huge constant factor for space and time. The key points of our approach are to express the property
p
by a
recursive
boolean function over the structure
x
rather than a usual logical predicate and to apply program transformation techniques to reduce the constant factor. We present an
optimization theorem
, give a calculational strategy for applying the theorem, and demonstrate the effectiveness of our approach through several nontrivial examples which would be difficult to deal with when using the methods previously available.
Cheap eagerness
Authors: Faxén Karl-Filip
Published: November 2005

Cheap eagerness is an optimization where cheap and safe expressions are evaluated before it is known that their values are needed. Many compilers for lazy functional languages implement this optimization, but they are limited by a lack of information about the global flow of control and about which variables are already evaluated. Without this information, even a variable reference is a potentially unsafe expression!In this paper we show that significant speedups are achievable by cheap eagerness. Our cheapness analysis uses the results of a program-wide data and control flow analysis to find out which variables may be unevaluated and which variables may be bound to functions which are dangerous to call.
Intersection types and computational effects
Authors: Davies Rowan , Pfenning Frank
Published: November 2005

We show that standard formulations of intersection type systems are unsound in the presence of computational effects, and propose a solution similar to the value restriction for polymorphism adopted in the revised definition of Standard ML. It differs in that it is not tied to let-expressions and requires an additional weakening of the usual subtyping rules. We also present a bi-directional type-checking algorithm for the resulting language that does not require an excessive amount of type annotations and illustrate it through some examples. We further show that the type assignment system can be extended to incorporate parametric polymorphism. Taken together, we see our system and associated type-checking algorithm as a significant step towards the introduction of intersection types into realistic programming languages. The added expressive power would allow many more properties of programs to be stated by the programmer and statically verified by a compiler.
QuickCheck
Authors: Claessen Koen , Hughes John
Published: November 2005

Quick Check is a tool which aids the Haskell programmer in formulating and testing properties of programs. Properties are described as Haskell functions, and can be automatically tested on random input, but it is also possible to define custom test data generators. We present a number of case studies, in which the tool was successfully used, and also point out some pitfalls to avoid. Random testing is especially suitable for functional programs because properties can be stated at a fine grain. When a function is built from separately tested components, then random testing suffices to obtain good coverage of the definition under test.
Split-stream dictionary program compression
Authors: Lucco Steven
Published: November 2005

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.
Safety checking of machine code
Authors: Xu Zhichen , Miller Barton P. , Reps Thomas
Published: November 2005

We show how to determine statically whether it is safe for untrusted
machine code to be loaded into a trusted host system.

Our safety-checking technique operates directly on the untrusted machine-code program, requiring only that the initial inputs to the untrusted program be annotated with typestate information and linear constraints. This approach opens up the possibility of being able to certify code produced by any compiler from any source language, which gives the code producers more freedom in choosing the language in which they write their programs. It eliminates the dependence of safety on the correctness of the compiler because the final product of the compiler is checked. It leads to the decoupling of the safety policy from the language in which the untrusted code is written, and consequently, makes it possible for safety checking to be performed with respect to an extensible set of safety properties that are specified on the host side.

We have implemented a prototype safety checker for SPARC machine-language programs, and applied the safety checker to several examples. The safety checker was able to either prove that an example met the necessary safety conditions, or identify the places where the safety conditions were violated. The checking times ranged from less than a second to 14 seconds on an UltraSPARC machine.
Translation validation for an optimizing compiler
Authors: Necula George C.
Published: November 2005

We describe a translation validation infrastructure for the GNU C
compiler. During the compilation the infrastructure compares the intermediate form of the program before and after each compiler pass and verifies the preservation of semantics. We discuss a general framework that the optimizer can use to communicate to the validator what transformations were performed. Our implementation however does not rely on help from the optimizer and it is quite successful by using instead a few heuristics to detect the transformations that take place.

The main message of this paper is that a practical translation validation infrastructure, able to check the correctness of many of the transformations performed by a realistic compiler, can be implemented with about the effort typically required to implement one compiler pass. We demonstrate this in the context of the GNU C compiler for a number of its optimizations while compiling realistic programs such as the compiler itself or the Linux kernel. We believe that the price of such an infrastructure is small considering the qualitative increase in the ability to isolate compilation errors during compiler testing and maintenance.
Exploiting superword level parallelism with multimedia instruction sets
Authors: Larsen Samuel , Amarasinghe Saman
Published: November 2005

Increasing focus on multimedia applications has prompted the addition
of multimedia extensions to most existing general purpose microprocessors. This added functionality comes primarily with the addition of short SIMD instructions. Unfortunately, access to these instructions is limited to in-line assembly and library calls. Generally, it has been assumed that vector compilers provide the most promising means of exploiting multimedia instructions. Although vectorization technology is well understood, it is inherently complex and fragile. In addition, it is incapable of locating SIMD-style parallelism within a basic block.

In this paper we introduce the concept of
Superword Level Parallelism (SLP)
,a novel way of viewing parallelism in multimedia and scientific applications. We believe SLPP is fundamentally different from the loop level parallelism exploited by traditional vector processing, and therefore demands a new method of extracting it. We have developed a simple and robust compiler for detecting SLPP that targets basic blocks rather than loop nests. As with techniques designed to extract ILP, ours is able to exploit parallelism both across loop iterations and within basic blocks. The result is an algorithm that provides excellent performance in several application domains. In our experiments, dynamic instruction counts were reduced by 46%. Speedups ranged from 1.24 to 6.70.
Functional reactive programming from first principles
Authors: Wan Zhanyong , Hudak Paul
Published: November 2005

Functional Reactive Programming
, or
FRP
, is a general framework for programming hybrid systems in a high-level, declarative manner. The key ideas in FRP are its notions of
behaviors
and
events
. Behaviors are time-varying, reactive values, while events are time-ordered sequences of discrete-time event occurrences. FRP is the essence of
Fran
, a domain-specific language embedded in Haskell for programming reactive animations, but FRP is now also being used in vision, robotics and other control systems applications.

In this paper we explore the formal semantics of FRP and how it
relates to an implementation based on
streams
that represent (and therefore only approximate) continuous behaviors. We show that, in the limit as the sampling interval goes to zero, the implementation is faithful to the formal, continuous semantics, but only when certain constraints on behaviors are observed. We explore the nature of these constraints, which vary amongst the FRP primitives. Our results show both the power and limitations of this approach to language design and implementation. As an example of a limitation, we show that streams are incapable of representing instantaneous predicate events over behaviors.
Scalable context-sensitive flow analysis using instantiation constraints
Authors: Fähndrich Manuel , Rehof Jakob , Das Manuvir
Published: November 2005

This paper shows that a type graph (obtained via polymorphic type
inference) harbors explicit directional flow paths between functions. These flow paths arise from the instantiations of polymorphic types and correspond to call-return sequences in first-order programs. We show that flow information can be computed efficiently while considering only paths with well matched call-return sequences, even in the higher-order case. Furthermore, we present a practical algorithm for inferring type instantiation graphs and provide empirical evidence to the scalability of the presented techniques by applying them in the context of points-to analysis for C programs.
A generational on-the-fly garbage collector for Java
Authors: Domani Tamar , Kolodner Elliot K. , Petrank Erez
Published: November 2005

An
on-the-fly garbage collector
does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications running on multiprocessor servers, where it is important to fully utilize all processors and provide even response time, especially for systems for which
stopping the threads is a costly operation.

In this work, we report on the incorporation of generations into
an on-the-fly garbage collector. The incorporation is non-trivial since an on-the-fly collector avoids explicit synchronization with the program threads. To the best of our knowledge, such an incorporation has not been tried before. We have implemented the collector for a prototype Java Virtual Machine on AIX, and measured its performance on a 4-way multiprocessor.

As for other generational collectors, an on-the-fly generational
collector has the potential for reducing the overall running time and working set of an application by concentrating collection efforts on the young objects. However, in contrast to other generational collectors,
on-the-fly collectors do not move the objects; thus, there is no segregation between the old and the young objects. Furthermore, on-the-fly collectors do not stop the threads, so there is no extra benefit for the short pauses obtained by generational collection. Nevertheless, comparing our on-the-fly collector with and without generations, it turns out that the generational collector performs better for most applications. The best reduction in overall running time for the benchmarks we measured was 25%. However, there were some benchmarks for which it had no effect and one for which the overall running time increased by 4%.
A single intermediate language that supports multiple implementations of exceptions
Authors: Ramsey Norman , Peyton Jones Simon
Published: November 2005

We present mechanisms that enable our compiler-target language, C--, to express four of the best known techniques for implementing exceptions, all within a single, uniform framework. We define the mechanisms precisely, using a formal operational semantics. We also show that exceptions need not require special treatment in the optimizer; by introducing extra dataflow edges, we make standard optimization techniques work even on programs that use exceptions. Our approach clarifies the design space of exception-handling techniques, and it allows a single optimizer to handle a variety of implementation techniques. Our ultimate goal is to allow a source-language compiler the freedom to choose its exception-handling policy, while encapsulating the architecture-dependent mechanisms and their optimization in an implementation of C--that can be used by compilers for many source languages.
Efficient algorithms for bidirectional debugging
Authors: Boothe Bob
Published: November 2005

This paper discusses our research into algorithms for creating an
efficient bidirectional debugger in which all traditional forward movement commands can be performed with equal ease in the reverse direction. We expect that adding these backwards movement capabilities to a debugger will greatly increase its efficacy as a programming tool.

The efficiency of our methods arises from our use of event counters
that are embedded into the program being debugged. These counters are
used to precisely identify the desired target event on the fly as the
target program executes. This is in contrast to traditional debuggers that may trap back to the debugger many times for some movements. For reverse movements we re-execute the program (possibly using two passes) to identify and stop at the desired earlier point. Our counter based techniques are essential for these reverse movements because they allow us to efficiently execute through the millions of events encountered during re-execution.

Two other important components of this debugger are its I/O logging and checkpointing. We log and later replay the results of system calls
to ensure deterministic re-execution, and we use checkpointing to bound the
amount of re-execution used for reverse movements. Short movements generally appear instantaneous, and the time for longer movements is usually bounded within a small constant factor of the temporal distance moved back.
Caching function calls using precise dependencies
Authors: Heydon Allan , Levin Roy , Yu Yuan
Published: November 2005

This paper describes the implementation of a purely functional
programming language for building software systems. In this language,
external tools like compilers and linkers are invoked by function calls. Because some function calls are extremely expensive, it is obviously important to reuse the results of previous function calls whenever possible. Caching a function call requires the language interpreter to record all values on which the function call depends. For optimal caching, it is important to record precise dependencies that are both
dynamic
and
fine-grained
. The paper sketches how we compute such dependencies, describes the implementation of an efficient function cache, and evaluates our implementation's performance.
Field analysis
Authors: Ghemawat Sanjay , Randall Keith H. , Scales Daniel J.
Published: November 2005

We present a new limited form of interprocedural analysis called
field analysis
that can be used by a compiler to reduce the costs of modern language features such as object-oriented programming, automatic memory management, and run-time checks required for type safety. Unlike many previous interprocedural analyses, our analysis is cheap, and does not require access to the entire program. Field analysis exploits the declared access restrictions placed on fields in a modular language (
e.g.
field access modifiers in Java) in order to determine useful properties of fields of an object.

We describe our implementation of field analysis in the Swift optimizing compiler for Java, as well a set of optimizations that exploit the results of field analysis. These optimizations include removal of run-time tests, compile-time resolution of method calls, object inlining, removal of unnecessary synchronization, and stack allocation. Our results demonstrate that field analysis is efficient and effective. Speedups average 7% on a wide range of applications, with some times reduced by up to 27%. Compile time overhead of field analysis is about 10%.
An automatic object inlining optimization and its evaluation
Authors: Dolby Julian , Chien Andrew
Published: November 2005

Automatic object inlining
[19, 20] transforms heap
data structures by fusing parent and child objects together. It can
improve runtime by reducing object allocation and pointer dereference
costs. We report continuing work studying object inlining optimizations. In particular, we present a new semantic derivation of the correctness conditions for object inlining, and program analysis which extends our previous work. And we present an object inlining transformation, focusing on a new algorithm which optimizes class field layout to minimize code expansion. Finally, we detail a fuller evaluation on eleven programs and libraries (including Xpdf, the 25,000 line Portable Document Format (PDF) file browser) that utilizes hardware measures of impact on the memory system.

We show that our analysis scales effectively to large programs,
finding many inlinable fields (45 in xpdf) at acceptable cost, and we
show that, on some programs, it finds nearly all fields for which object inlining is correct, and averages 40% of such fields across our benchmarks. We implement our analyses in an advanced analysis infrastructure, and we show that, compared to traditional 1-CFA, that infrastructure provides better results and lower and more scalable cost. Across all programs, analysis identified about 30% of objects as inlinable on average. Our transformation increases code size by only 20% while inlining this 30% of fields. Inlining these objects eliminated on average 28% of field reads, 58% of object creations, 12% of all loads. Further, the optimized programs have significantly improved memory reference behavior, producing 25% fewer L1 data cache misses and 25% fewer read stalls. On average the runtime improved by 14%.
Hardware architectures for programming languages and programming languages for hardware architectures
Authors: Wirth Niklaus
Published: November 2005

Programming Languages and Operating Systems introduce abstractions which allow the programmer to ignore details of an implementation. Support of an abstraction must not only concentrate on promoting the efficiency of an implementation, but also on providing the necessary guards against violations of the abstractions. In the frantic drive for efficiency the second goal has been neglected. There are indications that recent designs which are claimed to be both simple and powerful, achieve efficiency by shifting the complex issues of code generation and of appropriate guards onto compilers.Complexity has become the common hallmark of software as well as hardware designs. It cannot be mastered by the common practices of testing and simulation. Hardware design may profit from developments in programming methodology by adopting proof techniques similar to those used in programming.
Architectural support for multilanguage parallel programming on heterogeneous systems
Authors: Bisiani Roberto , Forin Alessandro
Published: November 2005

We have designed and implemented a software facility, called Agora, that supports the development of parallel applications written in multiple languages. At the core of Agora there is a mechanism that allows concurrent computations to share data structures independently of the computer architecture they are executed on. Concurrent computations exchange control information by using a pattern-directed technique. This paper describes the Agora shared memory and its software implementation on both tightly and loosely-coupled architectures.
An architecture for the direct execution of the Forth programming language
Authors: Hayes John R. , Fraeman Martin E. , Williams Robert L. , Zaremba Thomas
Published: November 2005

We have developed a simple direct execution architecture for a 32 bit Forth microprocessor. The processor can directly access a linear address space of over 4 gigawords. Two instruction types are defined; a subroutine call, and a user defined microcode instruction. On-chip stack caches allow most Forth primitives to execute in a single cycle.
Tags and type checking in LISP: hardware and software approaches
Authors: Steenkiste Peter , Hennessy John
Published: November 2005

One of the major factors that distinguishes LISP from many other languages (Pascal, C, Fortran, etc.) is the need for run-time type checking. Run-time type checking is implemented by adding to each data object a tag that encodes type information. Tags must be compared for type compatibility, removed when using the data, and inserted when new data items are created. This tag manipulation, together with other work related to dynamic type checking and generic operations, constitutes a significant component of the execution time of LISP programs. This has led both to the development of LISP machines that support tag checking in hardware and to the avoidance of type checking by users running on stock hardware. To understand the role and necessity of special-purpose hardware for tag handling, we first measure the cost of type checking operations for a group of LISP programs. We then examine hardware and software implementations of tag operations and estimate the cost of tag handling with the different tag implementation schemes. The data shows that minimal levels of support provide most of the benefits, and that tag operations can be relatively inexpensive, even when no special hardware support is present.
The effect of instruction set complexity on program size and memory performance
Authors: Davidson Jack W. , Vaughan Richard A.
Published: November 2005

One potential disadvantage of a machine with a reduced instruction set is that object programs may be substantially larger than those for a machine with a richer, more complex instruction set. The main reason is that a small instruction set will require more instructions to implement the same function. In addition, the tendency of RISC machines to use fixed length instructions with a few instruction formats also increases object program size. It has been conjectured that the resulting larger programs could adversely affect memory performance and bus traffic. In this paper we report the results of a set of experiments to isolate and determine the effect of instruction set complexity on cache memory performance and bus traffic. Three high-level language compilers were constructed for machines with instruction sets of varying degrees of complexity. Using a set of benchmark programs, we evaluated the effect of instruction set complexity had on program size. Five of the programs were used to perform a set of trace-driven simulations to study each machine's cache and bus performance. While we found that the miss ratio is affected by object program size, it appears that this can be corrected by simplying increasing the size of the cache. Our measurements of bus traffic, however, show that even with large caches, machines with simple instruction sets can expect substantially more main memory reads than machines with dense object programs.
An experimental coprocessor for implementing persistent objects on an IBM 4381
Authors: Georgiou C. J. , Palmer S. L. , Rosenfeld P. L.
Published: November 2005

In this paper we describe an experimental coprocessor for an IBM 4381 that is designed to facilitate the exploration of persistent objects.
Integer multiplication and division on the HP precision architecture
Authors: Magenheimer Daniel J. , Peters Liz , Pettis Karl , Zuras Dan
Published: November 2005

In recent years, many architectural design efforts have focused on maximizing performance for frequently executed, simple instructions. Although these efforts have resulted in machines with better average price/performance ratios, certain complex instructions and, thus, certain classes of programs which heavily depend on these instructions may suffer by comparison. Integer multiplication and division are one such set of complex instructions. This paper describes how a small set of primitive instructions combined with careful frequency analysis and clever programming allows the Hewlett-Packard Precision Architecture integer multiplication and division implementation to provide adequate performance at little or no hardware cost.
The Mahler experience: using an intermediate language as the machine description
Authors: Wall David W. , Powell Michael L.
Published: November 2005

Division of a compiler into a front end and a back end that communicate via an intermediate language is a well-known technique. We go farther and use the intermediate language as the official description of a family of machines with simple instruction sets and addressing capabilities, hiding some of the inconvenient details of the real machine from the users and the front end compilers.To do this credibly, we have had to hide not only the existence of the details but also the performance consequences of hiding them. The back end that compiles and links the intermediate language tries to produce code that does not suffer a performance penalty because of the details that were hidden from the front end compiler. To accomplish this, we have used a number of link-time optimizations, including instruction scheduling and interprocedural register allocation, to hide the existence of such idiosyncracies as delayed branches and non-infinite register sets. For the most part we have been sucessful.
Pipelining and performance in the VAX 8800 processor
Authors: Clark Douglas W.
Published: November 2005

The VAX 8800 family (models 8800, 8700, 8550), currently the fastest computers in the VAX product line, achieve their speed through a combination of fast cycle time and deep pipelining. Rather than pipeline highly variable VAX instructions as such, the 8800 design pipelines uniform microinstructions whose addresses are generated by instruction unit hardware. This design approach helps achieve a fast cycle time, which is the prime determinan of performance. Some preliminary measurements of cycles per average instruction are reported.
A VLIW architecture for a trace scheduling compiler
Authors: Colwell Robert P. , Nix Robert P. , O'Donnell John J. , Papworth David B. , Rodman Paul K.
Published: November 2005

Very Long Instruction Word (VLIW) architectures were promised to deliver far more than the factor of two or three that current architectures achieve from overlapped execution. Using a new type of compiler which compacts ordinary sequential code into long instruction words, a VLIW machine was expected to provide from ten to thirty times the performance of a more conventional machine built of the same implementation technology.Multiflow Computer, Inc., has now built a VLIW called the TRACE
TM
along with its companion Trace Scheduling
TM
compacting compiler. This new machine has fulfilled the performance promises that were made. Using many fast functional units in parallel, this machine extends some of the basic Reduced-Instruction-Set precepts: the architecture is load/store, the microarchitecture is exposed to the compiler, there is no microcode, and there is almost no hardware devoted to synchronization, arbitration, or interlocking of any kind (the compiler has sole responsibility for runtime resource usage).This paper discusses the design of this machine and presents some initial performance results.
Reducing garbage collector cache misses
Authors: Boehm Hans-J.
Published: November 2005

Cache misses are currently a major factor in the cost of garbage collection, and we expect them to dominate in the future. Traditional garbage collection algorithms exhibit relatively little temporal locality; each live object in the heap is likely to be touched exactly once during each garbage collection. We measure two techniques for dealing with this issue: prefetch-on-grey, and lazy sweeping. The first of these is new in this context. Lazy sweeping has been in common use for a decade. It was introduced as a mechanism for reducing paging and pause times; we argue that it is also crucial for eliminating cache misses during the sweep phase.

Our measurements are obtained in the context of a non-moving garbage collector. Fully copying garbage collection inherently requires more traffic through the cache, and thus probably also stands to benefit substantially from something like the prefetch-on-grey technique. Generational garbage collection may reduce the benefit of these techniques for some applications, but experiments with a non-moving generational collector suggest that they remain quite useful.