bluuebunny/crossref_metadata_2025 huggingface dataset:
Multitasking without comprimise
Authors: Czajkowski Grzegorz , Daynès Laurent
Published: November 2005

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
Incremental computation of complex object queries
Authors: Nakamura Hiroaki
Published: November 2005

The need for incremental algorithms for evaluating database queries is well known, but constructing algorithms that work on object-oriented databases (OODBs) has been difficult. The reason is that OODB query languages involve complex data types including composite objects and nested collections. As a result, existing algorithms have limitations in that the kinds of database updates are restricted, the operations found in many query languages are not supported, or the algorithms are too complex to be described precisely. We present an incremental computation algorithm that can handle any kind of database updates, can accept any expressions in complex query languages such as OQL, and can be described precisely. By translating primitive values and records into collections, we can reduce all query expressions comprehension. This makes the problems with incremental computation less complicated and thus allows us to decribe of two parts: one is to maintain the consistency in each comprehension occurrence and the other is to update the value of an entire expression. The algorithm is so flexible that we can use strict updates, lazy updates, and their combinations. By comparing the performance of applications built with our mechanism and that of equivalent hand written update programs, we show that our incremental algorithm can be iplemented efficiently.
Partial method compilation using dynamic profile information
Authors: Whaley John
Published: November 2005

The traditional tradeoff when performing dynamic compilation is that of fast compilation time versus fast code performance. Most dynamic compilation systems for Java perform selective compilation and/or optimization at a method granularity. This is the not the optimal granularity level. However, compiling at a sub-method granularity is thought to be too complicated to be practical. This paper describes a straightforward technique for performing compilation and optimizations at a finer, sub-method granularity. We utilize dynamic profile data to determine intra-method code regions that are rarely or never executed, and compile and optimize the code without those regions. If a branch that was predicted to be rare is actually taken at run time, we fall back to the interpreter or dynamically compile another version of the code. By avoiding compiling and optimizing code that is rarely executed, we are able to decrease compile time significantly, with little to no degradation in performance. Futhermore, ignoring rarely-executed code can open up more optimization opportunities on the common paths. We present two optimizations---partial dead code elimination and rare-path-sensitive pointer and escape analysis---that take advantage of rare path information. Using these optimizations, our technique is able to improve performance beyond the compile time improvements
Dynamic optimistic interprocedural analysis
Authors: Pechtchanski Igor , Sarkar Vivek
Published: November 2005

In this paper, we address the problem of
dynamic optimistic interprocedural analysis
. Our goal is to build on past work on
static interprocedural analysis
and
dynamic optimization
by combining their advantages. We present a framework for performing dynamic optimistic interprocedural analysis. the framework is designed to be used in the context of dynamic class loading and dynamic compilation, and includes mechanisms for event notification (on class loading and method compilation) and dependence tracking (to enable invalidation of optimistic assumptions). We illustrate the functionality of the framework by using it to be used in the context of dynamic class loading and dynamic compilation, and includes mechanisms for event notification (on class loading and method compilaton) and dependence tracking (to enable invalidation of optimistic assumptions). We illustrate the functionality of the framework by using it to implement a
dynamic optimistic interprocedural type
(DOIT) analysis algorithm. The DOIT algorithm uses a new global data structure called the
Value Graph
. The framework and DOIT analysis of the IBM Jalapeño Java virtual machine. Our experimental results for the SPECjvm benchmarks and two larger programs show promising benefits due to dynamic optimistic analysis. Compared to pessimistic analysis, the reduction in number of methods and fields analyzed was in the 2.7x-4.6x and 1.6-2.4x ranges respectively. The average fraction of polymorphic virtual calls decreased from 39.5% to 24.4% due to optimistic analysis, with a
best-case
decrease from 47.0% to 8.1%. The average fraction of
polymorphic interface calls
decreased from 96.4% to 36.2% due to optimistic analysis, with a
best-case
decrease from 100.0% to 0.0%. These benefits were obtained with a low dynamic analysis overhead in the range of 570-930 bytecode bytes/millisecond (about 2.5x-5.4x faster than the Jalapeño baseline compiler)
Jiazzi
Authors: McDirmid Sean , Flatt Matthew , Hsieh Wilson C.
Published: November 2005

We present Jiazzi, a system that enables the construction of large-scale binary components in Java. Jiazzi components can be thought of as generalizations of Java packages with added support for external linking and separate compilation. Jiazzi components are practical becuase they are constructed out of standard Java source code. Jiazzi requires neither extensions to the Java language nor special conventions for writing Java source code that will go inside a component. Our components are expressive becuase Jiazzi supports cyclic component linking and mixins, which are used together in an
open class pattern
that enables the modular addition of new features to existing classes. This paper describes Jiazzi, how it enhances Java with components, its implementation, and how type checking works. An implementation of Jiazzi is available for download.
Modular mixin-based inheritance for application frameworks
Authors: Duggan Dominic , Techaubol Ching-Ching
Published: November 2005

Mixin modules are proposed as an extension of a class-based programming language. Mixin modules combine parallel extension of classes, including extension of the self types for those classes, with mixin-based inheritance. For soundness of sybtyping purposes, they require an explicit distinction between mixin-based objects and class-based objects. Applications of mixin modules are in statically type-safe monad-based aspect-oriented programming, and in modular mixin-based Internet programming.
Encapsulating objects with confined types
Authors: Grothoff Christian , Palsberg Jens , Vitek Jan
Published: November 2005

Object-oriented languages provide little support for encapsulating objects. Reference semantics allows objects to escape their defining scope. The pervasive aliasing that ensues remains a major source of software defects. This paper introduces Kacheck/J a tool for inferring object encapulation properties in large Java programs. Our goal is to develop practical tools to assist software engineers, thus we focus on simple and scalable techniques. Kacheck/J is able to infer
confinement
for Java classes. A class and its sublasses are confined if all of their instances are encapsulated in their defining package. This simple property can be used to identify accidental leaks of sensitive objects. The analysis is scalable and efficient; Kacheck/J is able t infer confinement on a corpus of 46,000 classes (115 MB) in 6 minutes
Controlling garbage collection and heap growth to reduce the execution time of Java applications
Authors: Brecht Tim , Arjomandi Eshrat , Li Chang , Pham Hang
Published: November 2005

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting garbage frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the rist of not collecting much garbage during each cycle. On the other hand, collecting garbage too infrequently can result in applications that execute with a large amount of virtual memory (i.e., with a large footprint) and suffer from increased execution times die to paging. In this paper, we use a large colleciton of Java applications and the highly tuned and widely used Boehm-Demers-Weiser (BDW) conservative mark-and-sweep garbage collector to experimentally examine the extent to which the frequency of garbage collectio impacts an application's execution time, footprint, and pause times. We use these results to devise some guidelines for controlling garbage and heap growth in a conservative garbage collection in order to minimize application execution times. Then we describe new strategies for controlling in order to minimize application execution times.
Generic validation of structural content with parametric modules
Authors: Chuang Tyng-Ruey
Published: November 2005

We demonstrate a natural mapping from XML element types to ML module expressions. The mapping is inductive and definitions of common XML operations can be derived as the module expressions are composed. We show how to derive, in a generic way, the validation function, which checks an XML document for conformance to its DTD (Document Type Definition). One can view validation as assigning ML types to XML elements and the validation procedure a pre-requisite for typeful XML programming in ML. Our mapping uses the parametric module facility of ML in some contrived way. For example, in validating WML (WAP Markup Language) documents, we need to use 36ary type constructors, as well as higher-order modules that take in as many as 17 modules as input. That one can systematically model XML DTDs at the module level suggests ML-like languages are suitable for type-safe prototyping of DTD-aware XML applications.
Developing a stage lighting system from scratch
Authors: Sperber Michael
Published: November 2005

Lula is a system for computer-assisted stage lighting design and control. Whereas other systems for the same purpose are usually the results of long chains of incremental improvements of historic concepts, Lula represents a complete redesign. Whereas other systems focus on control aspects of lighting, Lula focuses on design and generates control information from it. This approach gives significantly more flexibility to the lighting designer and shortens the design process itself. Lula's design and implementation draw from a number of disciplines in advanced programming. It is written in Scheme and runs atop PLT Scheme, and benefits from its high-level GUI library. Lula uses an algebraic model for lighting looks based on just three combinators. It employs Functional Reactive Programming for all dynamic aspects of lighting, and is programmable via a functional reactive domain-specific language. Lula is an actual product and has users who have neither interest in nor knowledge of functional programming.
Events in Haskell, and how to implement them
Authors: Russell George
Published: November 2005

We describe a new and simpler implementation in Haskell of CML's
events, which encode reactions by a thread to combinations of
messages from other threads. We add a new type of Guarded Events,
by which recipients can filter messages with conditions on their
value known as Guards. We implement guarded channels. The guard
type and the indexing algorithm are not part of the channel
definition, so that the user can trade off what guards are required
against the cost of indexing. As an example we sketch the
encapsulation of a graphical user interface toolkit. This can be
done concisely not only because of guarded events, but also because
we construct events monadically. Monadic events are especially
helpful for representing concurrent processes which transform
themselves in reaction to external communications.
Compositional explanation of types and algorithmic debugging of type errors
Authors: Chitil Olaf
Published: November 2005

The type systems of most typed functional programming languages are based on the Hindley-Milner type system. A practical problem with these type systems is that it is often hard to understand why a program is not type correct or a function does not have the intended type. We suggest that at the core of this problem is the difficulty of explaining why a given expression has a certain type. The type system is not defined compositionally. We propose to explain types using a variant of the Hindley-Milner type system that defines a compositional type explanation graph of principal typing. We describe how the programmer understands types by interactive navigation through the explanation graph. Furthermore, the explanation graph can be the foundation for algorithmic debugging of type errors, that is, semi-automatic localisation of the source of a type error without even having to understand the type inference steps. We implemented a prototype of a tool to explore the usefulness of the proposed methods.
Automatic generation of staged geometric predicates
Authors: Nanevski Aleksandar , Blelloch Guy , Harper Robert
Published: November 2005

Algorithms in Computational Geometry and Computer Aided Design are often developed for the Real RAM model of computation, which assumes exactness of all the input arguments and operations. In practice, however, the exactness imposes tremendous limitations on the algorithms --- even the basic operations become uncomputable, or prohibitively slow. When the computations of interest are limited to determining the sign of polynomial expressions over floating point numbers, faster approaches are available. One can evaluate the polynomial in floating-point first, together with some estimate of the rounding error, and fall back to exact arithmetic only if this error is too big to determine the sign reliably. A particularly efficient variation on this approach has been used by Shewchuk in his robust implementations of Orient and InSphere geometric predicates. We extend Shewchuk's method to arbitrary polynomial expressions. The expressions are given as programs in a suitable source language featuring basic arithmetic operations of addition, subtraction, multiplication and squaring, which are to be perceived by the programmer as exact. The source language also allows for anonymous functions, and thus enables the common functional programming technique of staging. The method is presented formally through several judgments that govern the compilation of the source expression into target code, which is then easily transformed into SML or, in case of single-stage expressions, into C.
Cost recurrences for DML programs
Authors: Grobauer Bernd
Published: November 2005

A cost recurrence describes an upper bound for the running time of a program in terms of the size of its input. Finding cost recurrences is a frequent intermediate step in complexity analysis, and this step requires an abstraction from data to data size. In this article, we use information contained in dependent types to achieve such an abstraction: Dependent ML (DML), a conservative extension of ML, provides dependent types that can be used to associate data with size information, thus describing a possible abstraction. We automatically extract cost recurrences from first-order DML programs, guiding the abstraction from data to data size with information contained in DML type derivations.
Possibilities and limitations of call-by-need space improvement
Authors: Gustavsson Jörgen , Sands David
Published: November 2005

Innocent-looking program transformations can easily change the space complexity of lazy functional programs. The theory of space improvement seeks to characterize those local program transformations which are guaranteed never to worsen asymptotic space complexity of any program. Previous work by the authors introduced the space improvement relation and showed that a number of simple local transformation laws are indeed space improvements. This paper seeks an answer to the following questions: is the improvement relation inhabited by interesting program transformations, and, if so, how might they be established? We show that the asymptotic space improvement relation is semantically badly behaved, but that the theory of strong space improvement possesses a fixed-point induction theorem which permits the derivation of improvement properties for recursive definitions. With the help of this tool we explore the landscape of space improvement by considering a range of classical program transformation.
Towards bridging the gap between programming languages and partial evaluation
Authors: Le Meur Anne-Françoise , Lawall Julia L. , Consel Charles
Published: November 2005

Partial evaluation is a program-transformation technique that automatically specializes a program with respect to user-supplied invariants. Despite successful applications in areas such as graphics, operating systems, and software engineering, partial evaluators have yet to achieve widespread use. One reason is the difficulty of adequately describing specialization opportunities. Indeed, under-specialization or over-specialization often occurs, without any direct feedback to the user as to the source of the problem.We have developed a high-level, module-based language allowing the programmer to guide the choice of both the code to specialize and the invariants to exploit during the specialization process. To ease the use of partial evaluation, the syntax of this language is similar to the declaration syntax of the target language of the partial evaluator. To provide feedback to the programmer, declarations are checked throughout the analyses performed by partial evaluation. The language has been successfully used by a signal-processing expert in the design of a specializable Forward Error Correction component.
Online partial evaluation for shift and reset
Authors: Asai Kenichi
Published: November 2005

This paper presents an online partial evaluator for the λ-calculus with the delimited continuation constructs
shift
and
reset
. We first give the semantics of the delimited continuation constructs in two ways: one by writing a continuation passing style (CPS) interpreter and the other by transforming them into CPS. We then combine them to obtain a partial evaluator written in CPS which produces the result in CPS. By transforming this partial evaluator back into a direct style (DS) in two steps, we obtain a DS to DS partial evaluator written in DS. The correctness of the partial evaluator is not yet formally proven. The difficulty comes from the fact that the partial evaluator is written using shift and reset. The method for reasoning about such programs is not yet established. However, the development of the partial evaluator is detailed in the paper to give a degree of confidence that it behaves as we expect.
From checking to inference via driving and dag grammars
Authors: Secher Jens Peter , Sørensen Morten Heine
Published: November 2005

Abramov and Glück have recently introduced a technique called URA for inverting first order functional programs. Given some desired output value, URA computes a potentially infinite sequence of substitutions/restrictions corresponding to the relevant input values. In some cases this process does not terminate.In the present paper, we propose a new program analysis for inverting programs. The technique works by computing a finite grammar describing the set of all input that relate to a given output. During the production of the grammar, the original program is implicitly transformed using so-called driving steps. Whereas URA is sound and complete, but sometimes fails to terminate, our technique always terminates and is complete, but not sound. As an example, we demonstrate how to derive type inference from type checking.The idea of approximating functional programs by grammars is not new. For instance, the second author has developed a technique using tree grammars to approximate termination behaviour of deforestation. However, for the present purposes it has been necessary to invent a new type of grammar that extends tree grammars by permitting a notion of sharing in the productions. These
dag grammars
seem to be of independent interest.
Path dependent analysis of logic programs
Authors: Lu Lunjin
Published: November 2005

This paper presents an abstract semantics that uses information about execution paths to improve precision of data flow analyses of logic programs. We illustrate the abstract semantics by abstracting execution paths using call strings of fixed length and the last transfer of control. Abstract domains that have been developed for logic program analyses can be used with the new abstract semantics without modification.
Automatic time-bound analysis for a higher-order language
Authors: Gómez Gustavo , Liu Yanhong A.
Published: November 2005

Analysis of program running time is important for several applications, including reactive systems, interactive environments, compiler optimizations and performance evaluation. Automatic and efficient prediction of accurate time bounds is particularly important, and being able to do so for high-level languages is particularly desirable. This paper presents a general approach for automatic and accurate time-bound analysis for a functional high-level language, that combines methods and techniques studied in theory, languages, and systems. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. To handle higher-order functions, special transformations are needed to build lambda expressions for computing running times, to optimize the construction of the time lambda expressions, and to optimize the symbolic evaluation. It took us several tries to obtain the simple and concise transformations for handling lambda expressions. We describe analysis and transformation algorithms and explain how they work. We have implemented this approach and performed a large number of experiments analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds. We describe our prototype system, ALPA, as well as the analysis and measurement results.
Compositionality in the puzzle of semantics
Authors: Giacobazzi Roberto , Mastroeni Isabella
Published: November 2005

In this paper we study the connection between the structure of relational abstract domains for program analysis and compositionality of the underlying semantics. Both can be systematically designed as solution of the same abstract domain equation involving the same domain refinement: the reduced power operation. We prove that most well-known compositional semantics of imperative programs, such as the standard denotational and weakest precondition semantics can be systematically derived as solutions of simple abstract domain equations. This provides an equational presentation of both semantics and abstract domains for program analysis in a unique formal setting. Moreover both finite and transfinite compositional semantics share the same structure, and this allows us to provide consistent models for program manipulation.
Program optimization using indexed and recursive data structures
Authors: Liu Yanhong A. , Stoller Scott D.
Published: November 2005

This paper describes a systematic method for optimizing recursive functions using both indexed and recursive data structures. The method is based on two critical ideas: first, determining a minimal input increment operation so as to compute a function on repeatedly incremented input; second, determining appropriate additional values to maintain in appropriate data structures, based on what values are needed in computation on an incremented input and how these values can be established and accessed. Once these two are determined, the method extends the original program to return the additional values, derives an incremental version of the extended program, and forms an optimized program that repeatedly calls the incremental program. The method can derive all dynamic programming algorithms found in standard algorithm textbooks. There are many previous methods for deriving efficient algorithms, but none is as simple, general, and systematic as ours.
CPS translating inductive and coinductive types
Authors: Barthe Gilles , Uustalu Tarmo
Published: November 2005

We investigate CPS translatability of typed λ-calculi with inductive and coinductive types. We show that tenable Plotkin-style call-by-name CPS translations exist for simply typed λ-calculi with a natural number type and stream types and, more generally, with arbitrary positive inductive and coinductive types. These translations also work in the presence of control operators and generalize for dependently typed calculi where case-like eliminations are only allowed in non-dependent forms. No translation is possible along the same lines for small Σ-types and sum types with dependent case.
Efficient global register allocation for minimizing energy consumption
Authors: Zhang Yumin , Hu Xiaobo (Sharon) , Chen Danny Z.
Published: November 2005

Data referencing during program execution can be a significant source of energy consumption especially for data-intensive programs. In this paper, we propose an approach to minimize such energy consumption by allocating data to proper registers and memory. Through careful analysis of boundary conditions between consecutive blocks, our approach efficiently handles various control structures including branches, merges and loops, and achieves the allocation results benefiting the whole program. The computational cost for solving the energy minimization allocation problem is rather low comparing with known approaches while the quality of the results are very encouraging.
A Modula-2 implementation of a real-time process abstraction
Authors: Burns A. , Davies G. L. , Wellings A. J.
Published: November 2005

A process abstraction, in Modula-2, is defined that is aimed at providing the primitives needed in the real-time domain. A concurrency model based upon occam is used but this is enhanced by a comprehensive set of selective wait constructs. All processes have identities and priorities; a run-time implementation kernel provides for preemptive scheduling. Significant parts of this implementation are illustrated and short examples of the use of the process abstraction are given.
Some sad remarks about string handling in C
Authors: Abrahams P. W.
Published: November 2005

Many people have criticized the C programming language for its failure to enforce discipline in programming. They cite the lack of typechecking and the locutions that expose and indeed emphasize the underlying machine model. C is less often criticized for lack of efficiency. Yet in a critical part of the language -- string handling -- the efficiency of C falls short of the mark.String handling is a major application of C. In the original C book by Kernighan and Ritchie, nearly every example has something to do with strings. In systems programming, another major application, string handling is a large part of the task. If a skillful C programmer cannot easily write programs that manipulate strings efficiently, then the language has failed to meet one of its central goals.There are two problems with strings in C. The first is the use of a representation for strings in which a terminating null character indicates the length of the string. The second is the lack of built-in operations on strings analogous to the ones provided for arithmetic data.
Smalltalk and exploratory programming
Authors: Sandberg D. W.
Published: November 2005

Using Smalltalk-80, programmers can produce prototypes much faster than with C or Pascal. What techniques do Smalltalk-80 programmers use to produce these prototypes? What is special about Smalltalk-80 that enables them to uses these techniques? Can these techniques be used with conventional languages such as C? In an attempt to answer these questions we interviewed experienced Smalltalk programmers and asked how they approach programming in Smalltalk. Such introspective interviews that are conducted after completion of a project are known to be somewhat unreliable, but not enough is known to use any other methodology. What follows is a summary of the interviews, followed by an explanation of the results. Finally we discuss some of the weaknesses of Smalltalk and some possible solutions.
A fast algorithm for code movement optimisation
Authors: Dhamdhere D. M.
Published: November 2005

Code optimisation algorithms using bi-directional data flow dependencies have become increasingly important in recent years. The use of these algorithms faces two difficulties in practice: (a) Low profitabilities, and (b) high solution costs. This paper develops a new approach to the use of bi-directional dependencies using the concept of
edge placement
. This is shown to yield higher profitabilities of optimisation. An efficient solution method for such algorithms is also developed. The complexity of this method is shown to be bounded by O(e) operations, where e is the number of edges in the program flow graph. Ths is comparable to the complexity of uni-directional flow algorithms commonly used in optimisation.
Preference-directed graph coloring
Authors: Koseki Akira , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

This paper describes a new framework of register allocation based on Chaitin-style coloring. Our focus is on maximizing the chances for live ranges to be allocated to the most preferred registers while not destroying the colorability obtained by graph simplification. Our coloring algorithm uses a graph representation of preferences called a Register Preference Graph, which helps find a good register selection. We then try to relax the register selection order created by the graph simplification. The relaxed order is defined as a partial order, represented using a graph called a Coloring Precedence Graph. Our algorithm utilizes such a partial order for the register selection instead of using the traditional simplification-driven order so that the chances of honoring the preferences are effectively increased. Experimental results show that our coloring algorithm is powerful to simultaneously handle spill decisions, register coalescing, and preference resolutions.
A sparse algorithm for predicated global value numbering
Authors: Gargi Karthik
Published: November 2005

This paper presents a new algorithm for performing global value numbering on a routine in static single assignment form. Our algorithm has all the strengths of the most powerful existing practical methods of global value numbering; it unifies optimistic value numbering with constant folding, algebraic simplification and unreachable code elimination. It goes beyond existing methods by unifying optimistic value numbering with further analyses: it canonicalizes the structure of expressions in order to expose more congruences by performing
global reassociation
, it exploits the congruences induced by the predicates of conditional jumps (
predicate inference
and
value inference
), and it associates the arguments of acyclic
ø
functions with the predicates controlling their arrival (
ø predication
), thus enabling congruence finding on conditional control structures. Finally, it implements an efficient
sparse
formulation and offers a range of tradeoffs between compilation time and optimization strength. We describe an implementation of the algorithm and present measurements of its strength and efficiency collected when optimizing the SPEC CINT2000 C benchmarks.
A parallel, incremental and concurrent GC for servers
Authors: Ossia Yoav , Ben-Yitzhak Ori , Goft Irit , Kolodner Elliot K. , Leikehman Victor , Owshanko Avi
Published: November 2005

Multithreaded applications with multi-gigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for "server-oriented" GC include: ensuring short pause times on a multi-gigabyte heap, while minimizing throughput penalty, good scaling on multiprocessor hardware, and keeping the number of expensive multi-cycle fence instructions required by weak ordering to a minimum. We designed and implemented a fully parallel, incremental, mostly concurrent collector, which employs several novel techniques to meet these challenges. First, it combines incremental GC to ensure short pause times with concurrent low-priority background GC threads to take advantage of processor idle time. Second, it employs a low-overhead work packet mechanism to enable full parallelism among the incremental and concurrent collecting threads and ensure load balancing. Third, it reduces memory fence instructions by using batching techniques: one fence for each block of small objects allocated, one fence for each group of objects marked, and no fence at all in the write barrier. When compared to the mature well-optimized parallel stop-the-world mark-sweep collector already in the IBM JVM, our collector prototype reduces the maximum pause time from 284 ms to 101 ms, and the average pause time from 266 ms to 66 ms while only losing 10% throughput when running the SPECjbb2000 benchmark on a 256 MB heap on a 4-way 550 MHz Pentium multiprocessor.
Combining region inference and garbage collection
Authors: Hallenberg Niels , Elsman Martin , Tofte Mads
Published: November 2005

This paper describes a memory discipline that combines region-based memory management and copying garbage collection by extending Cheney's copying garbage collection algorithm to work with regions. The paper presents empirical evidence that region inference very significantly reduces the number of garbage collections; and evidence that the fastest execution is obtained by using regions alone, without garbage collection. The memory discipline is implemented for Standard ML in the ML Kit compiler and measurements show that for a variety of benchmark programs, code generated by the compiler is as efficient, both with respect to execution time and memory usage, as programs compiled with Standard ML of New Jersey, another state-of-the-art Standard ML compiler.
A compiler approach to fast hardware design space exploration in FPGA-based systems
Authors: So Byoungro , Hall Mary W. , Diniz Pedro C.
Published: November 2005

The current practice of mapping computations to custom hardware implementations requires programmers to assume the role of hardware designers. In tuning the performance of their hardware implementation, designers manually apply loop transformations such as loop unrolling. designers manually apply loop transformations. For example, loop unrolling is used to expose instruction-level parallelism at the expense of more hardware resources for concurrent operator evaluation. Because unrolling also increases the amount of data a computation requires, too much unrolling can lead to a memory bound implementation where resources are idle. To negotiate inherent hardware space-time trade-offs, designers must engage in an iterative refinement cycle, at each step manually applying transformations and evaluating their impact. This process is not only error-prone and tedious but also prohibitively expensive given the large search spaces and with long synthesis times. This paper describes an automated approach to hardware design space exploration, through a collaboration between parallelizing compiler technology and high-level synthesis tools. We present a compiler algorithm that automatically explores the large design spaces resulting from the application of several program transformations commonly used in application-specific hardware designs. Our approach uses synthesis estimation techniques to quantitatively evaluate alternate designs for a loop nest computation. We have implemented this design space exploration algorithm in the context of a compilation and synthesis system called DEFACTO, and present results of this implementation on five multimedia kernels. Our algorithm derives an implementation that closely matches the performance of the fastest design in the design space, and among implementations with comparable performance, selects the smallest design. We search on average only 0.3% of the design space. This technology thus significantly raises the level of abstraction for hardware design and explores a design space much larger than is feasible for a human designer.
Space-time trade-off optimization for a class of electronic structure calculations
Authors: Cociorva Daniel , Baumgartner Gerald , Lam Chi-Chung , Sadayappan P. , Ramanujam J. , Nooijen Marcel , Bernholdt David E. , Harrison Robert
Published: November 2005

The accurate modeling of the electronic structure of atoms and molecules is very computationally intensive. Many models of electronic structure, such as the Coupled Cluster approach, involve collections of tensor contractions. There are usually a large number of alternative ways of implementing the tensor contractions, representing different trade-offs between the space required for temporary intermediates and the total number of arithmetic operations. In this paper, we present an algorithm that starts with an operation-minimal form of the computation and systematically explores the possible space-time trade-offs to identify the form with lowest cost that fits within a specified memory limit. Its utility is demonstrated by applying it to a computation representative of a component in the CCSD(T) formulation in the NWChem quantum chemistry suite from Pacific Northwest National Laboratory.
Maya
Authors: Baker Jason , Hsieh Wilson C.
Published: November 2005

We have designed and implemented Maya, a version of Java that allows programmers to extend and reinterpret its syntax. Maya generalizes macro systems by treating grammar productions as generic functions, and semantic actions on productions as multimethods on the corresponding generic functions. Programmers can write new generic functions (i.e., grammar productions) and new multimethods (i.e., semantic actions), through which they can extend the grammar of the language and change the semantics of its syntactic constructs, respectively. Maya's multimethods are compile-time metaprograms that transform abstract syntax: they execute at program compile-time, because they are semantic actions executed by the parser. Maya's multimethods can be dispatched on the syntactic structure of the input, as well as the static, source-level types of expressions in the input. In this paper we describe what Maya can do and how it works. We describe how its novel parsing techniques work and how Maya can statically detect certain kinds of errors, such as code that generates references to free variables. Finally, to demonstrate Maya's expressiveness, we describe how Maya can be used to implement the MultiJava language, which was described by Clifton et al. at OOPSLA 2000.
Region-based memory management in cyclone
Authors: Grossman Dan , Morrisett Greg , Jim Trevor , Hicks Michael , Wang Yanling , Cheney James
Published: November 2005

Cyclone is a type-safe programming language derived from C. The primary design goal of Cyclone is to let programmers control data representation and memory management without sacrificing type-safety. In this paper, we focus on the region-based memory management of Cyclone and its static typing discipline. The design incorporates several advancements, including support for region subtyping and a coherent integration with stack allocation and a garbage collector. To support separate compilation, Cyclone requires programmers to write some explicit region annotations, but a combination of default annotations, local type inference, and a novel treatment of region effects reduces this burden. As a result, we integrate C idioms in a region-based framework. In our experience, porting legacy C to Cyclone has required altering about 8% of the code; of the changes, only 6% (of the 8%) were region annotations.
Mining specifications
Authors: Ammons Glenn , Bodík Rastislav , Larus James R.
Published: November 2005

Program verification is a promising approach to improving program quality, because it can search all possible program executions for specific errors. However, the need to formally describe correct behavior or errors is a major barrier to the widespread adoption of program verification, since programmers historically have been reluctant to write formal specifications. Automating the process of formulating specifications would remove a barrier to program verification and enhance its practicality.This paper describes
specification mining
, a machine learning approach to discovering formal specifications of the protocols that code must obey when interacting with an application program interface or abstract data type. Starting from the assumption that a working program is well enough debugged to reveal strong hints of correct protocols, our tool infers a specification by observing program execution and concisely summarizing the frequent interaction patterns as state machines that capture both temporal and data dependences. These state machines can be examined by a programmer, to refine the specification and identify errors, and can be utilized by automatic verification tools, to find bugs.Our preliminary experience with the mining tool has been promising. We were able to learn specifications that not only captured the correct protocol, but also discovered serious bugs.
Types as models
Authors: Chaki Sagar , Rajamani Sriram K. , Rehof Jakob
Published: November 2005

Abstraction and composition are the fundamental issues in making model checking viable for software. This paper proposes new techniques for automating abstraction and decomposition using source level type information provided by the programmer. Our system includes two novel components to achieve this end: (1) a behavioral type-and-effect system for the π-calculus, which extracts sound models as types, and (2) an assume-guarantee proof rule for carrying out compositional model checking on the types. Open simulation between CCS processes is used as both the subtyping relation in the type system and the abstraction relation for compositional model checking.We have implemented these ideas in a tool---P
IPER
. P
IPER
exploits type signatures provided by the programmer to partition the model checking problem, and emit model checking obligations that are discharged using the S
PIN
model checker. We present the details on applying P
IPER
on two examples: (1) the SIS standard for managing trouble tickets across multiple organizations and (2) a file reader from the pipelined implementation of a web server.
Lazy abstraction
Authors: Henzinger Thomas A. , Jhala Ranjit , Majumdar Rupak , Sutre Grégoire
Published: November 2005

One approach to model checking software is based on the
abstract-check-refine
paradigm: build an abstract model, then check the desired property, and if the check fails, refine the model and start over. We introduce the concept of
lazy abstraction
to integrate and optimize the three phases of the abstract-check-refine loop. Lazy abstraction continuously builds and refines a single abstract model on demand, driven by the model checker, so that different parts of the model may exhibit different degrees of precision, namely just enough to verify the desired property. We present an algorithm for model checking safety properties using lazy abstraction and describe an implementation of the algorithm applied to C programs. We also provide sufficient conditions for the termination of the method.
Predicate abstraction for software verification
Authors: Flanagan Cormac , Qadeer Shaz
Published: November 2005

Software verification is an important and difficult problem. Many static checking techniques for software require annotations from the programmer in the form of method specifications and loop invariants. This annotation overhead, particularly of loop invariants, is a significant hurdle in the acceptance of static checking. We reduce the annotation burden by inferring loop invariants automatically.Our method is based on predicate abstraction, an abstract interpretation technique in which the abstract domain is constructed from a given set of predicates over program variables. A novel feature of our approach is that it infers universally-quantified loop invariants, which are crucial for verifying programs that manipulate unbounded data such as arrays. We present heuristics for generating appropriate predicates for each loop automatically; the programmer can specify additional predicates as well. We also present an efficient algorithm for computing the abstraction of a set of states in terms of a collection of predicates.Experiments on a 44KLOC program show that our approach can automatically infer the necessary predicates and invariants for all but 31 of the 396 routines that contain loops.
Functional logic overloading
Authors: Neubauer Matthias , Thiemann Peter , Gasbichler Martin , Sperber Michael
Published: November 2005

Functional logic overloading is a novel approach to user-defined overloading that extends Haskell's concept of type classes in significant ways. Whereas type classes are conceptually predicates on types in standard Haskell, they are
type functions
in our approach. Thus, we can base type inference on the evaluation of functional logic programs. Functional logic programming provides a solid theoretical foundation for type functions and, at the same time, allows for programmable overloading resolution strategies by choosing different evaluation strategies for functional logic programs. Type inference with type functions is an instance of type inference with constrained types, where the underlying constraint system is defined by a functional logic program. We have designed a variant of Haskell which supports our approach to overloading, and implemented a prototype front-end for the language.