bluuebunny/crossref_metadata_2025 huggingface dataset:
Experience with efficient array data flow analysis for array privatization
Authors: Gu Junjie , Li Zhiyuan , Lee Gyungho
Published: November 2005

Array data flow analysis is known to be crucial to the success of array privatization, one of the most important techniques for program parallelization. It is clear that array data flow analysis should be performed interprocedurally and symbolically, and that it often needs to handle the predicates represented by IF conditions. Unfortunately, such a powerful program analysis can be extremely time-consuming if not carefully designed. How to enhance the efficiency of thk analysis to a practical level remains an issue largely untouched to date. This paper documents our experience with building a highly efficient array data flow analyzer which is based on
guarded array regions
and which runs faster, by one or two orders of magnitude, than other similarly powerful tools.
A method for modifying dynamically classes in the object-oriented dynamic programming environment
Authors: Lu Pei , Yu Dachuan , Lu Jian
Published: November 2005

In the object-oriented dynamic programming environment, dynamic modification of a class, which permits change of it at run-time and without recompilation, is the key point to exploit flexibility and support rapid prototyping. However, it causes a problem that the existing objects of the modified class are difficult to handle. In this paper, the concept of "cloned class" is introduced, and a method based on it for modifying dynamically classes is proposed.
Message conversion and a new type system for OO model
Authors: Zhao Jianhua , Chen Jiajun , Zheng Guoliang
Published: November 2005

In this paper, we propose that the messages should be defined independently to the class definitions in an object-oriented program. The
compatibility relation
between two message types is also discussed. This kind of relationship is essential and useful for software reuses. A software designer can declare the compatibility relation between two message types if messages are defined independently to the class definitions. A message of one type can be converted to another type automatically when necessary if a compatibility relation between the two message types is specified. A new type system is proposed based on these new concepts in this paper. This type system is more flexible than the traditional ones while keeping the safety of type checking.
Static head nodes in the operation on dynamic structures
Authors: Qiu Zongyan
Published: November 2005

In operations on dynamic data structures (e.g., linked list), manipulating the first node should often be treated specially. Head nodes are used to deal with this problem. Unfortunately, the unused head-nodes are appendices too. They make other trouble in using the structures. In this paper, we use a number of examples to illustrate a technique to handle the problem: using static, temporary head nodes in operations on dynamic data structures. With this technique, definitions of operations on dynamic data structures may become simpler and clearer.
Learning programming in Prolog using schemata
Authors: Bieliková Mária , Návrat Pavol
Published: November 2005

In the paper, we describe our approach and experience with teaching fundamentals of logic programming by program schemata construction and explanation. Program schemata construction is helped by presentation of a few examples. After a particular program schema has been introduced, students are required to instantiate the schema both as a writing exercise and afterwards as a programming exercise. We report on our experiments aimed at verifying our hypotheses about suitability of this approach to learning programming by evaluating the effectiveness of the learning process.
Comments on several syntax rules in Ada95
Authors: Xu Baowen
Published: November 2005

This paper points out the demerits in the syntax rules of several syntactical elements (i.e., the record variant_part, the record_aggregate, the named array_aggregate, the case_statement and the exception_handler) in the Ada95 Reference Manual [ARM95], and puts forward some constructive amendments to these syntax rules.
A modular mathematical programming language
Authors: Prather Ronald E.
Published: November 2005

A new modular mathematical programming language M2001 is introduced. It is designed to serve as an expository/pedagogical language, used for the development and the presentation of algorithmic processes, as found in the full range of mathematical discourse -- from the modern discrete to the classical continuous mathematics. Built on a semantical framework based in the theory of categories, the M2001 language has a Pascai/Modula-like syntax, but uses the class concept only as a fully-encapsulated, built-in apparatus for handling the traditional mathematical structures and classical computer science (abstract) data types, as found in the elementary applications of the early undergraduate mathematics curriculum. The (categorical) semantic interpretation of the language is outlined, and a complete set of syntax diagrams is presented in an accompanying Appendix.
Efficient composite data flow analysis applied to concurrent programs
Authors: Naumovich Gleb , Clarke Lori A. , Osterweil Leon J.
Published: November 2005

FLAVERS, a tool for verifying properties of concurrent systems, uses composite data flow analysis to incrementally improve the precision of the results of its verifications. Although FLAVERS is one of the few static analysis techniques for concurrent systems that has the potential to handle large scale systems, it sometimes can still be very expensive to use. In this paper we experimentally compare the cost of two versions of this approach for solving composite data flow analysis problems. The first version, product-based, uses the more straightforward approach, and the second, tuple-based, is built around the idea of reducing analysis space requirements at the expense of analysis time. We demonstrate experimentally, by analyzing properties of actual concurrent programs, that the tuple-based version is comparable in time to the product-based version but for large composite data flow problems it requires several orders of magnitude less space.
Generational stack collection and profile-driven pretenuring
Authors: Cheng Perry , Harper Robert , Lee Peter
Published: November 2005

This paper presents two techniques for improving garbage collection performance: generational stack collection and profile-driven pretenuring. The first is applicable to stack-based implementations of functional languages while the second is useful for any generational collector. We have implemented both techniques in a generational collector used by the TIL compiler (Tarditi, Morrisett, Cheng, Stone, Harper, and Lee 1996), and have observed decreases in garbage collection times of as much as 70% and 30%, respectively.Functional languages encourage the use of recursion which can lead to a long chain of activation records. When a collection occurs, these activation records must be scanned for roots. We show that scanning many activation records can take so long as to become the dominant cost of garbage collection. However, most deep stacks unwind very infrequently, so most of the root information obtained from the stack remains unchanged across successive garbage collections.
Generational stack collection
greatly reduces the stack scan cost by reusing information from previous scans.Generational techniques have been successful in reducing the cost of garbage collection (Ungar 1984). Various complex heap arrangements and tenuring policies have been proposed to increase the effectiveness of generational techniques by reducing the cost and frequency of scanning and copying. In contrast, we show that by using profile information to make lifetime predictions,
pretenuring
can avoid copying data altogether. In essence, this technique uses a refinement of the generational hypothesis (most data die young) with a locality principle concerning the age of data: most allocations sites produce data that immediately dies, while a few allocation sites consistently produce data that survives many collections.
Proper tail recursion and space efficiency
Authors: Clinger William D.
Published: November 2005

The IEEE/ANSI standard for Scheme requires implementations to be
properly tail recursive
. This ensures that portable code can rely upon the space efficiency of continuation-passing style and other idioms. On its face, proper tail recursion concerns the efficiency of procedure calls that occur within a tail context. When examined closely, proper tail recursion also depends upon the fact that garbage collection can be asymptotically more space-efficient than Algol-like stack allocation.Proper tail recursion is not the same as ad hoc tail call optimization in stack-based languages. Proper tail recursion often precludes stack allocation of variables, but yields a well-defined asymptotic space complexity that can be relied upon by portable programs.This paper offers a formal and implementation-independent definition of proper tail recursion for Scheme. It also shows how an entire family of reference implementations can be used to characterize related safe-for-space properties, and proves the asymptotic inequalities that hold between them.
Using integer sets for data-parallel program analysis and optimization
Authors: Adve Vikram , Mellor-Crummey John
Published: November 2005

In this paper, we describe our experience with using an abstract integer-set framework to develop the Rice dHPF compiler, a compiler for High Performance Fortran. We present simple, yet general formulations of the major computation partitioning and communication analysis tasks as well as a number of important optimizations in terms of abstract operations on sets of integer tuples. This approach has made it possible to implement a comprehensive collection of advanced optimizations in dHPF, and to do so in the context of a more general computation partitioning model than previous compilers. One potential limitation of the approach is that the underlying class of integer set problems is fundamentally unable to represent HPF data distributions on a symbolic number of processors. We describe how we extend the approach to compile codes for a symbolic number of processors, without requiring any changes to the set formulations for the above optimizations. We show experimentally that the set representation is not a dominant factor in compile times on both small and large codes. Finally, we present preliminary performance measurements to show that the generated code achieves good speedups for a few benchmarks. Overall, we believe we are the first to demonstrate by implementation experience that it is practical to build a compiler for HPF using a general and powerful integer-set framework.
Optimizing direct threaded code by selective inlining
Authors: Piumarta Ian , Riccardi Fabio
Published: November 2005

Achieving good performance in bytecoded language interpreters is difficult without sacrificing both simplicity and portability. This is due to the complexity of dynamic translation ("just-in-time compilation") of bytecodes into native code, which is the mechanism employed universally by high-performance interpreters.We demonstrate that a few simple techniques make it possible to create highly-portable dynamic translators that can attain as much as 70% the performance of optimized C for certain numerical computations. Translators based on such techniques can offer respectable performance without sacrificing either the simplicity or portability of much slower "pure" bytecode interpreters.
Memory management with explicit regions
Authors: Gay David , Aiken Alex
Published: November 2005

Much research has been devoted to studies of and algorithms for memory management based on garbage collection or explicit allocation and deallocation. An alternative approach, region-based memory management, has been known for decades, but has not been well-studied. In a region-based system each allocation specifies a region, and memory is reclaimed by destroying a region, freeing all the storage allocated therein. We show that on a suite of allocation-intensive C programs, regions are competitive with malloc/free and sometimes substantially faster. We also show that regions support safe memory management with low overhead. Experience with our benchmarks suggests that modifying many existing programs to use regions is not difficult.
The design and implementation of a certifying compiler
Authors: Necula George C. , Lee Peter
Published: November 2005

This paper presents the design and implementation of a compiler that translates programs written in a type-safe subset of the C programming language into highly optimized DEC Alpha assembly language programs, and a
certifier
that automatically checks the type safety and memory safety of any assembly language program produced by the compiler. The result of the certifier is either a formal proof of type safety or a counterexample pointing to a potential violation of the type system by the target program. The ensemble of the compiler and the certifier is called a
certifying compiler
.Several advantages of certifying compilation over previous approaches can be claimed. The notion of a certifying compiler is significantly easier to employ than a formal compiler verification, in part because it is generally easier to verify the correctness of the result of a computation than to prove the correctness of the computation itself. Also, the approach can be applied even to highly optimizing compilers, as demonstrated by the fact that our compiler generates target code, for a range of realistic C programs, which is competitive with both the cc and gcc compilers with all optimizations enabled. The certifier also drastically improves the effectiveness of compiler testing because, for each test case, it statically signals compilation errors that might otherwise require many executions to detect. Finally, this approach is a practical way to produce the safety proofs for a Proof-Carrying Code system, and thus may be useful in a system for safe mobile code.
Structured programming in Java
Authors: Gibbons Jeremy
Published: November 2005

We argue that for computing majors, it is better to use a 'why' approach to teaching programming than a 'how' approach; this involves (among other things) teaching structured programming before progressing to higher-level styles such as object-oriented programming. We also argue that, once it has been decided to teach structured programming, Java is a reasonable language to choose for doing so.
Design of an Actor language for implicit parallel programming
Authors: Aridor Yariv , Cohen Shimon , Yehudai Amiram
Published: November 2005

Software tools that support implicit parallel programming hold the key to reducing the complexity of parallel programming and realizing more ubiquitous parallel computation. This paper addresses the topic of implicit concurrent object-oriented programming. It presents a new language, SYMPAL, which unlike most existing COOP languages that provide explicit constructs for concurrency control, is based on a unification of object orientation and pure functional programming with the goals of supporting
implicit programming
and
high efficiency
in massively concurrent object-oriented programming. Extensive experience with SYMPAL applications on a parallel machine indicates that it achieves these goals.
A traveling salesman in Java
Authors: Ledru Pascal
Published: November 2005

Java is a language which provides built-in multithreading and synchronized methods. Orca is a language for programming parallel applications on distributed computing systems. Processes in Orca communicate through shared-data objects. Shared-data objects provide both mutual exclusion synchronization as Java synchronized methods do, and condition synchronization which allows processes to wait until a certain condition becomes true. This paper presents how shared-data objects can be implemented in Java both on a shared memory system and on a distributed memory system. The traveling salesman problem is used to demonstrate how the transformation is achieved.
An evaluation of automatic object inline allocation techniques
Authors: Dolby Julian , Chien Andrew A.
Published: November 2005

Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory dereferences and memory management operations. Automatic
inline allocation
of child objects within parent objects can reduce overheads of heap-allocated pointer-referenced objects.We present three compiler analyses to identify inlinable fields by tracking accesses to heap objects. These analyses span a range from local data flow to adaptive whole-program, flow-sensitive inter-procedural analysis. We measure their cost and effectiveness on a suite of moderate-sized C++ programs (up to 30,000 lines including libraries). We show that aggressive interprocedural analysis is required to enable object inlining, and our adaptive inter-procedural analysis [23] computes precise information efficiently. Object inlining eliminates typically 40% of object accesses and allocations (improving performance up to 50%). Furthermore,
JRes
Authors: Czajkowski Grzegorz , von Eicken Thorsten
Published: November 2005

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

Class loaders
are a powerful mechanism for dynamically loading software components on the Java platform. They are unusual in supporting all of the following features:
laziness, type-safe linkage, user-defined extensibility
, and
multiple communicating namespaces
.We present the notion of class loaders and demonstrate some of their interesting uses. In addition, we discuss how to maintain type safety in the presence of user-defined dynamic class loading.
Making the future safe for the past
Authors: Bracha Gilad , Odersky Martin , Stoutamire David , Wadler Philip
Published: November 2005

We present GJ, a design that extends the Java programming language with generic types and methods. These are both explained and implemented by translation into the unextended language. The translation closely mimics the way generics are emulated by programmers: it erases all type parameters, maps type variables to their bounds, and inserts casts where needed. Some subtleties of the translation are caused by the handling of overriding.GJ increases expressiveness and safety: code utilizing generic libraries is no longer buried under a plethora of casts, and the corresponding casts inserted by the translation are guaranteed to not fail.GJ is designed to be fully backwards compatible with the current Java language, which simplifies the transition from non-generic to generic programming. In particular, one can retrofit existing library classes with generic interfaces without changing their code.An implementation of GJ has been written in GJ, and is freely available on the web.
rdp—an iterator-based recursive descent parser generator with tree promotion operators
Authors: Johnstone Adrian , Scott Elizabeth
Published: November 2005

rdp is a parser generator which accepts
Iterator Backus Naur Form
productions decorated with attributes and ANSI-C actions and produces recursive descent parsers. It has special support for the generation of tree-based intermediate forms, built-in symbol table handling for the implementation of context-sensitive components of the language syntax and a support library that includes a generalised graph handling module that can output graphs in a form suitable for use with well known visualisation tools.
UTLB
Authors: Chen Yuqun , Bilas Angelos , Damianakis Stefanos N. , Dubnicki Cezary , Li Kai
Published: November 2005

An important aspect of a high-speed network system is the ability to transfer data directly between the network interface and application buffers. Such a
direct data path
requires the network interface to "know" the virtual-to-physical address translation of a user buffer,
i.e
., the physical memory location of the buffer. This paper presents an efficient address translation architecture, User-managed TLB (UTLB), which eliminates system calls and device interrupts from the common communication path. UTLB also supports application-specific policies to pin and unpin application memory. We report micro-benchmark results for an implementation on Myrinet PC clusters. A trace-driven analysis is used to compare the UTLB approach with the interrupt-based approach. It is also used to study the effects of UTLB cache size, associativity, and prefetching. Our results show that the UTLB approach delivers robust performance with relatively small translation cache sizes.
Building program optimizers with rewriting strategies
Authors: Visser Eelco , Benaissa Zine-el-Abidine , Tolmach Andrew
Published: November 2005

We describe a language for defining term rewriting strategies, and its application to the production of program optimizers. Valid transformations on program terms can be described by a set of rewrite rules; rewriting strategies are used to describe when and how the various rules should be applied in order to obtain the desired optimization effects. Separating rules from strategies in this fashion makes it easier to reason about the behavior of the optimizer as a whole, compared to traditional monolithic optimizer implementations. We illustrate the expressiveness of our language by using it to describe a simple optimizer for an ML-like intermediate representation.The basic strategy language uses operators such as sequential composition, choice, and recursion to build transformers from a set of labeled unconditional rewrite rules. We also define an extended language in which the side-conditions and contextual rules that arise in realistic optimizer specifications can themselves be expressed as strategy-driven rewrites. We show that the features of the basic and extended languages can be expressed by breaking down the rewrite rules into their primitive building blocks, namely matching and building terms in variable binding environments. This gives us a low-level core language which has a clear semantics, can be implemented straightforwardly and can itself be optimized. The current implementation generates C code from a strategy specification.
The marriage of effects and monads
Authors: Wadler Philip
Published: November 2005

Gifford and others proposed an
effect
typing discipline to delimit the scope of computational effects within a program, while Moggi and others proposed
monads
for much the same purpose. Here we marry effects to monads, uniting two previously separate lines of research. In particular, we show that the type, region, and effect system of Talpin and Jouvelot carries over directly to an analogous system for monads, including a type and effect reconstruction algorithm. The same technique should allow one to transpose any effect systems into a corresponding monad system.
Modular object-oriented programming with units and mixins
Authors: Findler Robert Bruce , Flatt Matthew
Published: November 2005

Module and class systems have evolved to meet the demand for reuseable software components. Considerable effort has been invested in developing new module and class systems, and in demonstrating how each promotes code reuse. However, relatively little has been said about the interaction of these constructs, and how using modules and classes
together
can improve programs. In this paper, we demonstrate the synergy of a particular form of modules and classes---called units and mixins, respectively---for solving complex reuse problems in a natural manner.
H/Direct
Authors: Finne Sigbjorn , Leijen Daan , Meijer Erik , Peyton Jones Simon
Published: November 2005

H/Direct
is a foreign-language interface for the purely functional language Haskell. Rather than rely on host-language type signatures,
H/Direct
compiles Interface Definition Language (IDL) to Haskell stub code that marshals data across the interface. This approach allows Haskell to call both C and COM, and allows a Haskell component to be wrapped in a C or COM interface. IDL is a complex language and language mappings for IDL are usually described informally. In contrast, we provide a relatively formal and precise definition of the mapping between Haskell and IDL.
Lazy computation with exact real numbers
Authors: Edalat Abbas , Potts Peter John , Sünderhauf Philipp
Published: November 2005

We provide a semantical framework for exact real arithmetic using linear fractional transformations on the extended real line. We present an extension of PCF with a real type which introduces an eventually breadth-first strategy for lazy evaluation of exact real numbers. In this language, we present the constant
redundant if
, rif, for defining functions by cases which, in contrast to
parallel if
(pif), overcomes the problem of undecidability of comparison of real numbers in finite time. We use the upper space of the one-point compactification of the real line to develop a denotational semantics for the lazy evaluation of real programs. Finally two adequacy results are proved, one for programs containing rif and one for those not containing it. Our adequacy results in particular provide the proof of correctness of algorithms for computation of single-valued elementary functions.
A distributed garbage collector with diffusion tree reorganisation and mobile objects
Authors: Moreau Luc
Published: November 2005

We present a new distributed garbage collection algorithm that is able to reorganise diffusion trees and to support mobile objects. It has a modular design comprising three components: a reliable transport mechanism, a reference-counting based distributed garbage collector for non-mobile objects, and an extra layer that provides mobility. The algorithm is formalised by an abstract machine and is proved to be correct. The safety property ensures that an object may not be reclaimed as long as it is referred to locally or remotely. The liveness property guarantees that unreachable objects will eventually be reclaimed. The mobility property certifies that messages are always forwarded towards more recent mobile object positions.
The under-appreciated unfold
Authors: Gibbons Jeremy , Jones Geraint
Published: November 2005

Folds
are appreciated by functional programmers. Their dual,
unfolds
, are not new, but they are not nearly as well appreciated. We believe they deserve better. To illustrate, we present (indeed, we calculate) a number of algorithms for computing the
breadth-first traversal
of a tree. We specify breadth-first traversal in terms of
level-order traversal
, which we characterize first as a fold. The presentation as a fold is simple, but it is inefficient, and removing the inefficiency makes it no longer a fold. We calculate a characterization as an unfold from the characterization as a fold; this unfold is equally clear, but more efficient. We also calculate a characterization of breadth-first traversal directly as an unfold; this turns out to be the 'standard' queue-based algorithm.
A compacting incremental collector and its performance in a production quality compiler
Authors: Larose Martin , Feeley Marc
Published: November 2005

We present a new near-real-time compacting collector and its implementation in a production quality Scheme compiler (Gambit-C). Our goal is to use this system as a base for an implementation of Erlang for writing soft real-time telecommunication applications. We start with a description of Gambit-C's memory organisation and its blocking collector. The design and integration of the incremental collector within Gambit-C are then explained. Finally we measure the performance of the incremental collector and compare it to the original blocking collector. We found that the overhead of the incremental collector is high (a factor of 1.3 to 8.1, with a median of 2.24) but nevertheless the collection pauses are compatible with typical soft real-time requirements (we get an average pause of 2.9 milliseconds and a maximum pause of 15 milliseconds on a 133Mhz DEC Alpha 21064).
Combining card marking with remembered sets
Authors: Azagury Alain , Kolodner Elliot K. , Petrank Erez , Yehudai Zvi
Published: November 2005

We consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive implementation may cause excessive and wasteful scanning of the cards and thus increase the collection time. We offer a simple data structure and a corresponding algorithm to keep track of which cards need be scanned for which generation. We then extend these ideas for the Train Algorithm of [4]. Here, the solution is more involved, and allows tracking of which card should be scanned for which car-collection in the train.
One-bit counts between unique and sticky
Authors: Roth David J. , Wise David S.
Published: November 2005

Stoye's one-bit reference tagging scheme can be extended to local counts of two or more via two strategies. The first, suited to pure register transactions, is a cache of referents to two shared references. The analog of Deutsch's and Bobrow's multiple-reference table, this cache is sufficient to manage small counts across successive assignment statements. Thus, accurate reference counts above one can be tracked for short intervals, like those bridging one function's environment to its successor's.The second, motivated by runtime stacks that duplicate references, avoids counting any references from the stack. It requires a local pointer-inversion protocol in the mutator, but one still local to the referent and the stack frame. Thus, an accurate reference count of one can be maintained regardless of references from the recursion stack.
Hierarchical distributed reference counting
Authors: Moreau Luc
Published: November 2005

Massively distributed computing is a challenging problem for garbage collection algorithm designers as it raises the issue of scalability. The high number of hosts involved in a computation can require large tables for reference listing, whereas the lack of information sharing between hosts in a same locality can entail redundant GC traffic. In this paper, we argue that a conceptual hierarchical organisation of massive distributed computations can solve this problem. By conceptual hierarchical organisation, we mean that processors are still able to communicate in a peer to peer manner using their usual communication mechanism, but GC messages will be routed as if processors were organised in hierarchy. We present an extension of a distributed reference counting algorithm that uses such a hierarchical organisation. It allows us to bound table sizes by the number of hosts in a domain, and it allows us to share GC information between hosts in a same locality in order to reduce cross-network GC traffic.
Comparing mostly-copying and mark-sweep conservative collection
Authors: Smith Frederick , Morrisett Greg
Published: November 2005

Many high-level language compilers generate C code and then invoke a C compiler for code generation. To date, most, of these compilers link the resulting code against a conservative mark-sweep garbage collector in order to reclaim unused memory. We introduce a new collector, MCC, based on an extension of
mostly-copying collection
.We analyze the various design decisions made in MCC and provide a performance comparison to the most widely used conservative mark-sweep collector (the Boehm-Demers-Weiser collector). Our results show that a good mostly-copying collector can outperform a mature highly-optimized mark-sweep collector when physical memory is large relative to the live data. A surprising result of our analysis is that cache behavior can have a greater impact on overall performance than either collector time or allocation time.
A memory-efficient real-time non-copying garbage collector
Authors: Lim Tian F. , Pardyak Przemysław , Bershad Brian N.
Published: November 2005

Garbage collectors used in embedded systems such as Personal Java and Inferno or in operating systems such as SPIN must operate with limited resources and minimize their impact on application performance. Consequently, they must maintain short real-time pauses, low overhead, and a small memory footprint. Most garbage collectors, including the Treadmill algorithm, are inadequate because they sacrifice space for time. We have implemented a new Treadmill variant that provides good memory utilization by using real-time page-level management techniques that reduce fragmentation. A page-wise collection is used to locate pages of free memory, which are then dynamically reassigned between free lists as needed. Virtual memory is used to dynamically remap free pages into continuous ranges, and objects are allocated from under-utilized pages when needed. Finally, the use of header compaction and arbitrary free-list sizes reduces internal fragmentation. Our experiments demonstrate that we have substantially improved memory utilization without compromising latency or overhead, and that the new collector performs very well for SPIN's workloads and regular Modula-3 programs.
Very concurrent mark-&-sweep garbage collection without fine-grain synchronization
Authors: Huelsbergen Lorenz , Winterbottom Phil
Published: November 2005

We describe a new incremental algorithm for the concurrent reclamation of a program's allocated, yet unreachable, data. Our algorithm is a variant of mark-&-sweep collection that---unlike prior designs---runs mutator, marker, and sweeper threads concurrently
without
explicit fine-grain synchronization on shared-memory multiprocessors. A global, but infrequent, synchronization coordinates the per-object coloring marks used by the three threads; fine-grain synchronization is achieved without locking via the basic memory consistency guarantees commonly provided by multiprocessor hardware. We have implemented two versions of this algorithm (called VCGC): in the Inferno operating system and in the SML/NJ ML compiler. Measurements, compared to a sequential generational collector, indicate that VCGC can substantially reduce worst-case pause latencies as well as reduce overall memory usage. We remark that the degrees of freedom on the rates of marking and sweeping enable exploration of a range of resource tradeoffs, but makes "optimal" tuning for even a small set of applications difficult.
A semantics for imprecise exceptions
Authors: Peyton Jones Simon , Reid Alastair , Henderson Fergus , Hoare Tony , Marlow Simon
Published: November 2005

Some modern superscalar microprocessors provide only
imprecise exceptions
. That is, they do not guarantee to report the same exception that would be encountered by a straightforward sequential execution of the program. In exchange, they offer increased performance or decreased chip area (which amount to much the same thing).This performance/precision tradeoff has not so far been much explored at the programming language level. In this paper we propose a design for imprecise exceptions in the lazy functional programming language Haskell. We discuss several designs, and conclude that imprecision is essential if the language is still to enjoy its current rich algebra of transformations. We sketch a precise semantics for the language extended with exceptions.The paper shows how to extend Haskell with exceptions without crippling the language or its compilers. We do not yet have enough experience of using the new mechanism to know whether it strikes an appropriate balance between expressiveness and performance.
What is a recursive module?
Authors: Crary Karl , Harper Robert , Puri Sidd
Published: November 2005

A hierarchical module system is an effective tool for structuring large programs. Strictly hierarchical module systems impose an acyclic ordering on import dependencies among program units. This can impede modular programming by forcing mutually-dependent components to be consolidated into a single module. Recently there have been several proposals for module systems that admit cyclic dependencies, but it is not clear how these proposals relate to one another, nor how one might integrate them into an expressive module system such as that of ML.To address this question we provide a type-theoretic analysis of the notion of a recursive module in the context of a "phase-distinction" formalism for higher-order module systems. We extend this calculus with a recursive module mechanism and a new form of signature, called a
recursively dependent signature
, to support the definition of recursive modules. These extensions are justified by an interpretation in terms of more primitive language constructs. This interpretation may also serve as a guide for implementation.
Pointer analysis for programs with structures and casting
Authors: Yong Suan Hsi , Horwitz Susan , Reps Thomas
Published: November 2005

Type casting allows a program to access an object as if it had a type different from its declared type. This complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects; therefore, some previous pointer-analysis algorithms "collapse" a structure into a single variable. The disadvantage of this approach is that it can lead to very imprecise points-to information. Other algorithms treat each field as a separate object based on its offset and size. While this approach leads to more precise results, the results are not portable because the memory layout of structures is implementation dependent.This paper first describes the complications introduced by type casting, then presents a tunable pointer-analysis framework for handling structures in the presence of casting. Different instances of this framework produce algorithms with different levels of precision, portability, and efficiency. Experimental results from running our implementations of four instances of this framework show that (i) it is important to distinguish fields of structures in pointer analysis, but (ii) making conservative approximations when casting is involved usually does not cost much in terms of time, space, or the precision of the results.
On bounding time and space for multiprocessor garbage collection
Authors: Blelloch Guy E. , Cheng Perry
Published: November 2005

This paper presents the first multiprocessor garbage collection algorithm with provable bounds on time and space. The algorithm is a real-time shared-memory copying collector. We prove that the algorithm requires at most 2(
R
(l + 2/
k
) +
N
+ 5
PD
) memory locations, where
P
is the number of processors,
R
is the maximum reachable space during a computation (number of locations accessible from the root set),
N
is the maximum number of reachable objects,
D
is the maximum depth of any data object, and
k
is a parameter specifying how many locations are copied each time a location is allocated. Furthermore we show that client threads are never stopped for more than time proportional to
k
non-blocking machine instructions. The bounds are guaranteed even with arbitrary length arrays. The collector only requires write-barriers (reads are unaffected by the collector), makes few assumptions about the threads that are generating the garbage, and allows them to run mostly asynchronously.
Control CPR
Authors: Schlansker Michael , Mahlke Scott , Johnson Richard
Published: November 2005

The challenge of exploiting high degrees of instruction-level parallelism is often hampered by frequent branching. Both exposed branch latency and low branch throughput can restrict parallelism.
Control critical path reduction
(control CPR) is a compilation technique to address these problems. Control CPR can reduce the dependence height of critical paths through branch operations as well as decrease the number of executed branches. In this paper, we present an approach to control CPR that recognizes sequences of branches using profiling statistics. The control CPR transformation is applied to the predominant path through this sequence. Our approach, its implementation, and experimental results are presented. This work demonstrates that control CPR enhances instruction-level parallelism for a variety of application programs and improves their performance across a range of processors.
Improving cache performance in dynamic applications through data and computation reorganization at run time
Authors: Ding Chen , Kennedy Ken
Published: November 2005

With the rapid improvement of processor speed, performance of the memory hierarchy has become the principal bottleneck for most applications. A number of compiler transformations have been developed to improve data reuse in cache and registers, thus reducing the total number of direct memory accesses in a program. Until now, however, most data reuse transformations have been
static
---applied only at compile time. As a result, these transformations cannot be used to optimize irregular and dynamic applications, in which the data layout and data access patterns remain unknown until run time and may even change during the computation.In this paper, we explore ways to achieve better data reuse in irregular and dynamic applications by building on the inspector-executor method used by Saltz for run-time parallelization. In particular, we present and evaluate a
dynamic
approach for improving both computation and data locality in irregular programs. Our results demonstrate that run-time program transformations can substantially improve computation and data locality and, despite the complexity and cost involved, a compiler can automate such transformations, eliminating much of the associated run-time overhead.
Finite-state code generation
Authors: Fraser Christopher W. , Proebsting Todd A.
Published: November 2005

This paper describes GBURG, which generates tiny, fast code generators based on finite-state machine pattern matching. The code generators translate postfix intermediate code into machine instructions in one pass (except, of course, for backpatching addresses). A stack-based virtual machine---known as the
Lean Virtual Machine
(LVM)---tuned for fast code generation is also described. GBURG translates the two-page LVM-to-x86 specification into a code generator that fits entirely in an 8 KB I-cache and that emits x86 code at 3.6 MB/set on a 266-MHz P6. Our just-in-time code generator translates and executes small benchmarks at speeds within a factor of two of executables derived from the conventional compile-time code generator on which it is based.
Efficient incremental run-time specialization for free
Authors: Marlet Renaud , Consel Charles , Boinot Philippe
Published: November 2005

Availability of data in a program determines computation stages. Incremental partial evaluation exploit these stages for optimization: it allows further specialization to be performed as data become available at later stages. The fundamental advantage of incremental specialization is to factorize the specialization process. As a result, specializing a program at a given stage costs considerably less than specializing it once all the data are available.We present a realistic and flexible approach to achieve efficient incremental run-time specialization. Rather than developing specific techniques, as previously proposed, we are able to re-use existing technology by iterating a specialization process. Moreover, in doing so, we do not lose any specialization opportunities. This approach makes it possible to exploit nested quasi-invariants and to speed up the run-time specialization process.This approach has been implemented in Tempo, a specializer for C programs that is publicly available. A preliminary experiment confirm that incremental that incremental specialization can greatly speed up the specialization process.
An evaluation of staged run-time optimizations in DyC
Authors: Grant Brian , Philipose Matthai , Mock Markus , Chambers Craig , Eggers Susan J.
Published: November 2005

Previous selective dynamic compilation systems have demonstrated that dynamic compilation can achieve performance improvements at low cost on small kernels, but they have had difficulty scaling to larger programs. To overcome this limitation, we developed DyC, a selective dynamic compilation system that includes more sophisticated and flexible analyses and transformations. DyC is able to achieve good performance improvements on programs that are much larger and more complex than the kernels. We analyze the individual optimizations of DyC and assess their impact on performance collectively and individually.
A simple algorithm for partial redundancy elimination
Authors: Paleri Vineeth Kumar , Srikant Y. N. , Shankar Priti
Published: November 2005

Partial redundancy elimination was originally formulated as a bidirectional, bit-vector, data-flow analysis problem by Morel and Renvoise. Dhamdhere improved the original algorithm using the concept of edge placement. Knoop, Rüthing, and Steffen viewed the problem within a framework that required only four unidirectional analyses for an optimal solution. Here, we propose an algorithm for partial redundancy elimination based on well known concepts, viz., availability, anticipability, partial availability, and partial anticipability. The algorithm is both computationally and lifetime optimal. Our algorithm also requires four unidirectional data-flow analyses. The main advantage of the algorithm is its simplicity.
Calculating encoding and decoding functions for prefix codes
Authors: Pareja-Flores Cristóbal , Velázquez-Iturbide J. Ángel
Published: November 2005

The transformational model of program development allows obtaining programs correct by construction. When developing nontrivial programs, three activities arise: program synthesis, program transformation, and verification of properties; in addition, specification, use and implementation of ADTs must typically be considered all through these activities. The purpose of this article is to illustrate the need for all these activities by means of a nontrivial problem: encoding and decoding with prefix codes. Our exposition is rather informal, not being committed to any particular program transformation system, and it should be understood by any programmer looking forward to develop functional programs in a systematic way, while avoiding the burden of any particular system. In particular, we show the stages in the complete transformational development of a functional program, dealing successively with correctness and time efficiency, as well as the key decisions that are adopted.