bluuebunny/crossref_metadata_2025 huggingface dataset:
The garbage collection advantage
Authors: Huang Xianglong , Blackburn Stephen M. , McKinley Kathryn S. , Moss J Eliot B. , Wang Zhenlin , Cheng Perry
Published: November 2005

As improvements in processor speed continue to outpace improvements in cache and memory speed, poor locality increasingly degrades performance. Because copying garbage collectors move objects, they have an opportunity to improve locality. However, no static copying order is guaranteed to match program traversal orders. This paper introduces online object reordering (OOR) which includes a new dynamic, online class analysis for Java that detects program traversal patterns and exploits them in a copying collector. OOR uses run-time method sampling that drives just-in-time (JIT) compilation. For each hot (frequently executed) method, OOR analysis identifies the hot field accesses. At garbage collection time, the OOR collector then copies referents of hot fields together with their parent. Enhancements include static analysis to exclude accesses in cold basic blocks, heuristics that decay heat to respond to phase changes, and a separate space for hot objects. The overhead of OOR is on average negligible and always less than 2% on Java benchmarks in Jikes RVM with MMTk. We compare program performance of OOR to static class-oblivious copying orders (e.g., breadth and depth first). Performance variation due to static orders is often low, but can be up to 25%. In contrast, OOR matches or improves upon the best static order since its history-based copying tunes memory layout to program traversal.
MC
2
Authors: Sachindran Narendran , Moss J. Eliot B. , Berger Emery D.
Published: November 2005

Java is becoming an important platform for memory-constrained consumer devices such as PDAs and cellular phones, because it provides safety and portability. Since Java uses garbage collection, efficient garbage collectors that run in constrained memory are essential. Typical collection techniques used on these devices are mark-sweep and mark-compact. Mark-sweep collectors can provide good throughput and pause times but suffer from fragmentation. Mark-compact collectors prevent fragmentation, have low space overheads, and provide good throughput. However, they can suffer from long pause times. Copying collectors can provide higher throughput than either of these techniques, but because of their high space overhead, they previously were unsuitable for memory-constrained devices. This paper presents MC2 (Memory-Constrained Copying), a copying generational garbage collector that meets the needs of memory-constrained devices with soft real-time requirements. MC2 has low space over-head and tight space bounds, prevents fragmentation, provides good throughput, and yields short pause times. These qualities make MC2 attractive for other environments, including desktops and servers.
Instrumentation of standard libraries in object-oriented languages
Authors: Factor Michael , Schuster Assaf , Shagin Konstantin
Published: November 2005

Code instrumentation is widely used for a range of purposes that include profiling, debugging, visualization, logging, and distributed computing. Due to their special status within the language infrastructure, the standard class libraries, also known as system classes provided by most contemporary object-oriented languages are difficult and sometimes impossible to instrument. If instrumented, the use of their rewritten versions within the instrumentation code is usually unavoidable. However, this is equivalent to `instrumenting the instrumentation', and thus may lead to erroneous results. Consequently, most systems avoid rewriting system classes. We present a novel instrumentation strategy that alleviates the above problems by renaming the instrumented classes. The proposed approach does not require any modifications to the language, compiler or runtime. It allows system classes to be instrumented both statically and dynamically. In fact, this is the first technique that enables dynamic instrumentation of Java system classes without modification of any runtime components. We demonstrate our approach by implementing two instrumentation-based systems: a memory profiler and a distributed runtime for Java.
Recovering binary class relationships
Authors: Guéhéneuc Yann-Gaël , Albin-Amiot Hervé
Published: November 2005

A discontinuity exists between object-oriented modeling and programming languages. This discontinuity arises from ambiguous concepts in modeling languages and a lack of corresponding concepts in programming languages. It is particularly acute for binary class relationships---association, aggregation, and composition. It hinders the traceability between software implementation and design, thus hampering software analysis. We propose consensual definitions of the binary class relationships with four minimal properties---exclusivity, invocation site, lifetime, and multiplicity. We describe algorithms to detect automatically these properties in source code and apply these on several frameworks. Thus, we bridge the gap between implementation and design for the binary class relationships, easing software analysis.
Practical predicate dispatch
Authors: Millstein Todd
Published: November 2005

Predicate dispatch is an object-oriented (OO) language mechanism for determining the method implementation to be invoked upon a message send. With predicate dispatch, each method implementation includes a predicate guard specifying the conditions under which the method should be invoked, and logical implication of predicates determines the method overriding relation. Predicate dispatch naturally unifies and generalizes several common forms of dynamic dispatch, including traditional OO dispatch, multimethod dispatch, and functional-style pattern matching. Unfortunately, prior languages supporting predicate dispatch have had several deficiencies that limit its utility in practice.

We introduce JPred, a backward-compatible extension to Java supporting predicate dispatch. While prior languages with predicate dispatch have been extensions to toy or non-mainstream languages, we show how predicate dispatch can be naturally added to a traditional OO language. While prior languages with predicate dispatch have required the whole program to be available for type-checking and compilation, JPred retains Java's modular typechecking and compilation strategies. While prior languages with predicate dispatch have included special-purpose algorithms for reasoning about predicates, JPred employs general-purpose, off-the-shelf decision procedures. As a result, JPred's type system is more flexible, allowing several useful programming idioms that are spuriously rejected by those other languages. After describing the JPred language and type system, we present a case study illustrating the utility of JPred in a real-world application, including its use in the detection of several errors.
Concrete syntax for objects
Authors: Bravenboer Martin , Visser Eelco
Published: November 2005

Application programmer's interfaces give access to domain knowledge encapsulated in class libraries without providing the appropriate notation for expressing domain composition. Since object-oriented languages are designed for extensibility and reuse, the language constructs are often sufficient for expressing domain abstractions at the semantic level. However, they do not provide the right abstractions at the syntactic level. In this paper we describe MetaBorg, a method for providing concrete syntax for domain abstractions to application programmers. The method consists of embedding domain-specific languages in a general purpose host language and assimilating the embedded domain code into the surrounding host code. Instead of extending the implementation of the host language, the assimilation phase implements domain abstractions in terms of existing APIs leaving the host language undisturbed. Indeed, MetaBorg can be considered a method for promoting APIs to the language level. The method is supported by proven and available technology, i.e. the syntax definition formalism SDF and the program transformation language and toolset Stratego/XT. We illustrate the method with applications in three domains: code generation, XML generation, and user-interface construction.
Secure program execution via dynamic information flow tracking
Authors: Suh G. Edward , Lee Jae W. , Zhang David , Devadas Srinivas
Published: November 2005

We present a simple architectural mechanism called dynamic information flow tracking that can significantly improve the security of computing systems with negligible performance overhead. Dynamic information flow tracking protects programs against malicious software attacks by identifying spurious information flows from untrusted I/O and restricting the usage of the spurious information.Every security attack to take control of a program needs to transfer the program's control to malevolent code. In our approach, the operating system identifies a set of input channels as spurious, and the processor tracks all information flows from those inputs. A broad range of attacks are effectively defeated by checking the use of the spurious values as instructions and pointers.Our protection is transparent to users or application programmers; the executables can be used without any modification. Also, our scheme only incurs, on average, a memory overhead of 1.4% and a performance overhead of 1.1%.
Scalable selective re-execution for EDGE architectures
Authors: Desikan Rajagopalan , Sethumadhavan Simha , Burger Doug , Keckler Stephen W.
Published: November 2005

Pipeline flushes are becoming increasingly expensive in modern microprocessors with large instruction windows and deep pipelines. Selective re-execution is a technique that can reduce the penalty of mis-speculations by re-executing only instructions affected by the mis-speculation, instead of all instructions. In this paper we introduce a new selective re-execution mechanism that exploits the properties of a dataflow-like Explicit Data Graph Execution (EDGE) architecture to support efficient mis-speculation recovery, while scaling to window sizes of thousands of instructions with high performance. This distributed selective re-execution (DSRE) protocol permits multiple speculative waves of computation to be traversing a dataflow graph simultaneously, with a commit wave propagating behind them to ensure correct execution. We evaluate one application of this protocol to provide efficient recovery for load-store dependence speculation. Unlike traditional dataflow architectures which resorted to single-assignment memory semantics, the DSRE protocol combines dataflow execution with speculation to enable high performance
and
conventional sequential memory semantics. Our experiments show that the DSRE protocol results in an average 17% speedup over the best dependence predictor proposed to date, and obtains 82% of the performance possible with a perfect oracle directing the issue of loads.
Dynamic tracking of page miss ratio curve for memory management
Authors: Zhou Pin , Pandey Vivek , Sundaresan Jagadeesan , Raghuraman Anand , Zhou Yuanyuan , Kumar Sanjeev
Published: November 2005

Memory can be efficiently utilized if the dynamic memory demands of applications can be determined and analyzed at run-time. The page miss ratio curve(MRC), i.e. page miss rate vs. memory size curve, is a good performance-directed metric to serve this purpose. However, dynamically tracking MRC at run time is challenging in systems with virtual memory because not every memory reference passes through the operating system (OS).This paper proposes two methods to dynamically track MRC of applications at run time. The first method is using a hardware MRC monitor that can track MRC at fine time granularity. Our simulation results show that this monitor has negligible performance and energy overheads. The second method is an OS-only implementation that can track MRC at coarse time granularity. Our implementation results on
Linux
show that it adds only 7--10% overhead.We have also used the dynamic MRC to guide both memory allocation for multiprogramming systems and memory energy management. Our
real system
experiments on Linux with applications including Apache Web Server show that the MRC-directed memory allocation can speed up the applications' execution/response time by up to a factor of 5.86 and reduce the number of page faults by up to 63.1%. Our execution-driven simulation results with SPEC2000 benchmarks show that the MRC-directed memory energy management can improve the Energy * Delay metric by 27--58% over previously proposed static and dynamic schemes.
Compiler orchestrated prefetching via speculation and predication
Authors: Rabbah Rodric M. , Sandanagobalane Hariharan , Ekpanyapong Mongkol , Wong Weng-Fai
Published: November 2005

This paper introduces a compiler orchestrated prefetching system as a unified framework geared toward ameliorating the gap between processing speeds and memory access latencies. We focus the scope of the optimization on specific subsets of the program dependence graph that succinctly characterize the memory access pattern of both regular array-based applications and irregular pointer-intensive programs. We illustrate how
program embedded precomputation via speculative execution
can accurately predict and effectively prefetch future memory references with negligible overhead. The proposed techniques reduce the total running time of seven SPEC benchmarks and two OLDEN benchmarks by 27% on an Itanium 2 processor. The improvements are in addition to several state-of-the-art optimizations including software pipelining and data prefetching. In addition, we use cycle-accurate simulations to identify important and lightweight architectural innovations that further mitigate the memory system bottleneck. In particular, we focus on the notoriously challenging class of pointer-chasing applications, and demonstrate how they may benefit from a novel scheme of
it sentineled prefetching
. Our results for twelve SPEC benchmarks demonstrate that 45% of the processor stalls that are caused by the memory system are avoidable. The techniques in this paper can effectively mask long memory latencies with little instruction overhead, and can readily contribute to the performance of processors today.
Software prefetching for mark-sweep garbage collection
Authors: Cher Chen-Yong , Hosking Antony L. , Vijaykumar T. N.
Published: November 2005

Tracing garbage collectors traverse references from live program variables, transitively tracing out the closure of live objects. Memory accesses incurred during tracing are essentially random: a given object may contain references to any other object. Since application heaps are typically much larger than hardware caches, tracing results in many cache misses. Technology trends will make cache misses more important, so tracing is a prime target for prefetching.Simulation of Java benchmarks running with the Boehm-De-mers-Weiser mark-sweep garbage collector for a projected hardware platform reveal high tracing overhead (up to 65% of elapsed time), and that cache misses are a problem. Applying Boehm's default prefetching strategy yields improvements in execution time (16% on average with incremental/generational collection for GC-intensive benchmarks), but analysis shows that his strategy suffers from significant timing problems: prefetches that occur too early or too late relative to their matching loads. This analysis drives development of a new prefetching strategy that yields up to
three times
the performance improvement of Boehm's strategy for GC-intensive benchmark (27% average speedup), and achieves performance close to that of perfect timing
ie
, few misses for tracing accesses) on some benchmarks. Validating these simulation results with live runs on current hardware produces average speedup of 6% for the new strategy on GC-intensive benchmarks with a GC configuration that tightly controls heap growth. In contrast, Boehm's default prefetching strategy is ineffective on this platform.
Application-level checkpointing for shared memory programs
Authors: Bronevetsky Greg , Marques Daniel , Pingali Keshav , Szwed Peter , Schulz Martin
Published: November 2005

Trends in high-performance computing are making it necessary for long-running applications to tolerate hardware faults. The most commonly used approach is checkpoint and restart (CPR) - the state of the computation is saved periodically on disk, and when a failure occurs, the computation is restarted from the last saved state. At present, it is the responsibility of the programmer to instrument applications for CPR.Our group is investigating the use of compiler technology to instrument codes to make them self-checkpointing and self-restarting, thereby providing an automatic solution to the problem of making long-running scientific applications resilient to hardware faults. Our previous work focused on message-passing programs.In this paper, we describe such a system for shared-memory programs running on symmetric multiprocessors. This system has two components: (i) a pre-compiler for source-to-source modification of applications, and (ii) a runtime system that implements a protocol for coordinating CPR among the threads of the parallel application. For the sake of concreteness, we focus on a non-trivial subset of OpenMP that includes barriers and locks.One of the advantages of this approach is that the ability to tolerate faults becomes embedded within the application itself, so applications become self-checkpointing and self-restarting on any platform. We demonstrate this by showing that our transformed benchmarks can checkpoint and restart on three different platforms (Windows/x86, Linux/x86, and Tru64/Alpha). Our experiments show that the overhead introduced by this approach is usually quite small; they also suggest ways in which the current implementation can be tuned to reduced overheads further.
Heat-and-run
Authors: Gomaa Mohamed , Powell Michael D. , Vijaykumar T. N.
Published: November 2005

Power density in high-performance processors continues to increase with technology generations as scaling of current, clock speed, and device density outpaces the downscaling of supply voltage and thermal ability of packages to dissipate heat. Power density is characterized by localized chip hot spots that can reach critical temperatures and cause failure. Previous architectural approaches to power density have used global clock gating, fetch toggling, dynamic frequency scaling, or resource duplication to either prevent heating or relieve overheated resources in a superscalar processor. Previous approaches also evaluate design technologies where power density is not a major problem and most applications do not overheat the processor. Future processors, however, are likely to be chip multiprocessors (CMPs) with simultaneously-multithreaded (SMT) cores. SMT CMPs pose unique challenges and opportunities for power density. SMT and CMP increase throughput and thus on-chip heat, but also provide natural granularities for managing power-density. This paper is the first work to leverage SMT and CMP to address power density. We propose heat-and-run SMT thread assignment to increase processor-resource utilization before cooling becomes necessary by co-scheduling threads that use complimentary resources. We propose heat-and-run CMP thread migration to migrate threads away from overheated cores and assign them to free SMT contexts on alternate cores, leveraging availability of SMT contexts on alternate CMP cores to maintain throughput while allowing overheated cores to cool. We show that our proposal has an average of 9% and up to 34% higher throughput than a previous superscalar technique running the same number of threads.
Associated types with class
Authors: Chakravarty Manuel M. T. , Keller Gabriele , Jones Simon Peyton , Marlow Simon
Published: November 2005

Haskell's type classes allow ad-hoc overloading, or type-indexing, of
functions
. A natural generalisation is to allow type-indexing of
data types
as well. It turns out that this idea directly supports a powerful form of abstraction called
associated types
, which are available in C++ using traits classes. Associated types are useful in many applications, especially for self-optimising libraries that adapt their data representations and algorithms in a type-directed manner.In this paper, we introduce and motivate associated types as a rather natural generalisation of Haskell's existing type classes. Formally, we present a type system that includes a type-directed translation into an explicitly typed target language akin to System F; the existence of this translation ensures that the addition of associated data types to an existing Haskell compiler only requires changes to the front end.
Proof-guided underapproximation-widening for multi-process systems
Authors: Grumberg Orna , Lerda Flavio , Strichman Ofer , Theobald Michael
Published: November 2005

This paper presents a procedure for the verification of multi-process systems based on considering a series of underapproximated models. The procedure checks models with an increasing set of allowed interleavings of the given set of processes, starting from a single interleaving. The procedure relies on SAT solvers' ability to produce proofs of unsatisfiability: from these proofs it derives information that guides the process of adding interleavings on the one hand, and determines termination on the other. The presented approach is integrated in a SAT-based Bounded Model Checking (BMC) framework. Thus, a BMC formulation of a multi-process system is introduced, which allows controlling which interleavings are considered. Preliminary experimental results demonstrate the practical impact of the presented method.
Theoretical foundations for compensations in flow composition languages
Authors: Bruni Roberto , Melgratti Hernán , Montanari Ugo
Published: November 2005

A key aspect when aggregating business processes and web services is to assure transactional properties of process executions. Since transactions in this context may require long periods of time to complete, traditional mechanisms for guaranteeing atomicity are not always appropriate. Generally the concept of long running transactions relies on a weaker notion of atomicity based on compensations. For this reason, programming languages for service composition cannot leave out two key aspects:
compensations
, i.e. ad hoc activities that can undo the effects of a process that fails to complete, and
transactional boundaries
to delimit the scope of a transactional flow. This paper presents a hierarchy of transactional calculi with increasing expressiveness. We start from a very small language in which activities can only be composed sequentially. Then, we progressively introduce parallel composition, nesting, programmable compensations and exception handling. A running example illustrates the main features of each calculus in the hierarchy.
A framework for numeric analysis of array operations
Authors: Gopan Denis , Reps Thomas , Sagiv Mooly
Published: November 2005

Automatic discovery of relationships among values of array elements is a challenging problem due to the unbounded nature of arrays. We present a framework for analyzing array operations that is capable of capturing numeric properties of array elements.In particular, the analysis is able to establish that all array elements are initialized by an array-initialization loop, as well as to discover numeric constraints on the values of initialized elements.The analysis is based on the combination of canonical abstraction and summarizing numeric domains. We describe a prototype implementation of the analysis and discuss our experience with applying the prototype to several examples, including the verification of correctness of an insertion-sort procedure.
Protocols for processes
Authors: Singh Munindar P. , Chopra Amit K. , Desai Nirmit , Mallya Ashok U.
Published: November 2005

The modeling and enactment of business processes is being recognized as key to modern information managment. The expansion of Web services has increased the attention given to processes, because processes are how services are composed and put to good use. However, current approaches are inadequate for flexibly modeling and enacting processes. These approaches take a logically centralized view of processes, treating a process as an implementation of a composed service. They provide low-level scripting languages to specify how a service may be implemented, rather than what interactions are expected from it. Consequently, existing approaches fail to adequately accommodate the essential properties of the business partners in a process (the partners would be realized via services)---their
autonomy
(freedom of action),
heterogeneity
(freedom of design), and
dynamism
(freedom of configuration).Flexibly represented
protocols
can provide a more natural basis for specifying processes. Protocols specify
what
rather than
how
; thus they naturally maximize the authonomy, heterogeneity, and dynamism of the interacting parties. We are developing an approach for modeling and enacting business processes based on protocols. This paper describes some elements of (1) a conceptual model of processes that will incorporate abstractions based on protocols, roles, and commitments; (2)the semantics or mathematical foundations underlying the conceptual model and mapping global views of processes to the local actions of the parties involved; (3) methodologies involving rule-based reasoning to specify processes in terms of compositions of protocols.
Languages of the future
Authors: Sheard Tim
Published: November 2005

This paper explores a new point in the design space of formal reasoning systems - part programming language, part logical framework. The system is built on a programming language where the user expresses equality constraints between types and the type checker then enforces these constraints. This simple extension to the type system allows the programmer to describe properties of his program in the types of
witness
objects which can be thought of as concrete evidence that the program has the property desired. These techniques and two other rich typing mechanisms, rank-N polymorphism and extensible kinds, create a powerful new programming idiom for writing programs whose types enforce semantic properties.A language with these features is
both
a practical programming language
and
a logic. This marriage between two previously separate entities increases the probability that users will apply formal methods to their programming designs. This kind of synthesis creates the foundations for the languages of the future.
Syntax error repair for a Java-based parser generator
Authors: van der Spek P. , Plat N. , Pronk C.
Published: November 2005

This article presents an implementation of an error repair algoritm for the JavaCC parser generator. Three different approaches, the Burke-Fisher error repair, follow-set error repair and panic mode, have been implemented. These algorithms have been altered and combined in order to get improved results. Using this adapted implementation of JavaCC an improved syntax error recovery mechanism is available.
Optimising aspectJ
Authors: Avgustinov Pavel , Christensen Aske Simon , Hendren Laurie , Kuzins Sascha , Lhoták Jennifer , Lhoták Ondřej , de Moor Oege , Sereni Damien , Sittampalam Ganesh , Tibble Julian
Published: November 2005

AspectJ, an aspect-oriented extension of Java, is becoming increasingly popular. However, not much work has been directed at optimising compilers for AspectJ. Optimising AOP languages provides many new and interesting challenges for compiler writers, and this paper identifies and addresses three such challenges.First, compiling
around
advice efficiently is particularly challenging. We provide a new code generation strategy for
around
advice, which (unlike previous implementations) both avoids the use of excessive inlining and the use of closures. We show it leads to more compact code, and can also improve run-time performance. Second, woven code sometimes includes run-time tests to determine whether advice should execute. One important case is the
cflow
pointcut which uses information about the dynamic calling context. Previous techniques for
cflow
were very costly in terms of both time and space. We present new techniques to minimise or eliminate the overhead of
cflow
using both intra- and inter-procedural analyses. Third, we have addressed the general problem of how to structure an optimising compiler so that traditional analyses can be easily adapted to the AOP setting.We have implemented all of the techniques in this paper in
abc
, our AspectBench Compiler for AspectJ, and we demonstrate significant speedups with empirical results. Some of our techniques have already been integrated into the production AspectJ compiler,
ajc
1.2.1.
Mitosis compiler
Authors: Quiñones Carlos García , Madriles Carlos , Sánchez Jesús , Marcuello Pedro , González Antonio , Tullsen Dean M.
Published: November 2005

Speculative parallelization can provide significant sources of additional thread-level parallelism, especially for irregular applications that are hard to parallelize by conventional approaches. In this paper, we present the Mitosis compiler, which partitions applications into speculative threads, with special emphasis on applications for which conventional parallelizing approaches fail.The management of inter-thread data dependences is crucial for the performance of the system. The Mitosis framework uses a pure software approach to predict/compute the thread's input values. This software approach is based on the use of pre-computation slices (p-slices), which are built by the Mitosis compiler and added at the beginning of the speculative thread. P-slices must compute thread input values accurately but they do not need to guarantee correctness, since the underlying architecture can detect and recover from misspeculations. This allows the compiler to use aggressive/unsafe optimizations to significantly reduce their overhead. The most important optimizations included in the Mitosis compiler and presented in this paper are branch pruning, memory and register dependence speculation, and early thread squashing.Performance evaluation of Mitosis compiler/architecture shows an average speedup of 2.2.
Probabilistic source-level optimisation of embedded programs
Authors: Franke Björn , O'Boyle Michael , Thomson John , Fursin Grigori
Published: November 2005

Efficient implementation of DSP applications is critical for many embedded systems. Optimising C compilers for embedded processors largely focus on code generation and instruction scheduling which, with their growing maturity, are providing diminishing returns. This paper empirically evaluates another approach, namely source-level transformations and the probabilistic feedback-driven search for "good" transformation sequences within a large optimisation space. This novel approach combines two selection methods: one based on exploring the optimisation space, the other focused on localised search of good areas. This technique was applied to the UTDSP benchmark suite on two digital signal and multimedia processors (Analog Devices TigerSHARC TS-101, Philips TriMedia TM-1100) and an embedded processor derived from a popular general-purpose processor architecture (Intel Celeron 400). On average, our approach gave a factor of 1.71 times improvement across all platforms equivalent to an average 41% reduction in execution time, outperforming existing approaches. In certain cases a speedup of up to ͠ 7 was found for individual benchmarks.
Cache aware optimization of stream programs
Authors: Sermulins Janis , Thies William , Rabbah Rodric , Amarasinghe Saman
Published: November 2005

Effective use of the memory hierarchy is critical for achieving high performance on embedded systems. We focus on the class of streaming applications, which is increasingly prevalent in the embedded domain. We exploit the widespread parallelism and regular communication patterns in stream programs to formulate a set of cache aware optimizations that automatically improve instruction and data locality. Our work is in the context of the Synchronous Dataflow model, in which a program is described as a graph of independent actors that communicate over channels. The communication rates between actors are known at compile time, allowing the compiler to statically model the caching behavior.We present three cache aware optimizations: 1) execution scaling, which judiciously repeats actor executions to improve instruction locality, 2) cache aware fusion, which combines adjacent actors while respecting instruction cache constraints, and 3) scalar replacement, which converts certain data buffers into a sequence of scalar variables that can be register allocated. The optimizations are founded upon a simple and intuitive model that quantifies the temporal locality for a sequence of actor executions. Our implementation of cache aware optimizations in the StreamIt compiler yields a 249% average speedup (over unoptimized code) for our streaming benchmark suite on a StrongARM 1110 processor. The optimizations also yield a 154% speedup on a Pentium 3 and a 152% speedup on an Itanium 2.
Static strands
Authors: Sassone Peter G. , Wills D. Scott , Loh Gabriel H.
Published: November 2005

Modern embedded processors are designed to maximize execution efficiency--the amount of performance achieved per unit of energy dissipated while meeting minimum performance levels. To increase this efficiency we propose utilizing
static strands
, dependence chains without fan-out which are exposed by a compiler pass. These dependent instructions are resequenced to be sequential and annotated to communicate their location to the hardware. Importantly, this modified application is binary compatible and functionally identical to the original, allowing transparent execution on a baseline processor. However, these static strands can be easily collapsed and optimized by simple processor modifications, significantly reducing the workload energy. Results show that over 30% of MediaBench and Spec2000int dynamic instructions can be collapsed, reducing issue logic energy by 16 to 24%, bypass energy 17 to 20%, and register file energy 13 to 14%. Additionally, by increasing the effective capactity of pipeline resources by almost a third, average IPC can be improved up to 15%. This performance gain can then be traded in for a lower clock frequency to maintain a basline level of performance, reducing energy further.
An energy efficient garbage collector for java embedded devices
Authors: Griffin Paul , Srisa-an Witawas , Chang J. Morris
Published: November 2005

This paper presents a detailed design and implementation of a power-efficient garbage collector for Java embedded systems. The proposed scheme is a hybrid between the standard mark-sweep-compact collector available in Sun's KVM and a limited-field reference counter. There are three benefits resulting from the proposed scheme. (a) the proposed scheme reclaims memory more efficiently and this results in less mark-sweep garbage collection invocations, (b) reduction in garbage collection invocations improves cache locality and reduces the number of main memory accesses, and (c) reduction in memory access ultimately results in lower energy consumption, since a memory access can consume a large amount of energy when compared with an instruction execution. The proposed scheme has been implemented into Sun's KVM, and has been shown to reduce the number of mark-sweep garbage collection invocations by up to 100% in some cases, and the number of level-1 cache misses by as much as 87% when compared to the default garbage collector. We also find that in some applications, the proposed scheme can reduce the power consumption by as much as 27% when compared to the default Sun's KVM.
From ML type inference to stratified type inference
Authors: Pottier François
Published: November 2005

Hindley and Milner's type system, in its purest form, allows what one might call full type inference. Even when a program contains no explicit type information, its very structure gives rise to a conjunction of type equations (or, more generally, to a constraint) whose resolution allows reconstructing the type of every variable and of every sub-expression. Actual programming languages based on this type system, such as Standard ML, Objective Caml, and Haskell, do allow users to provide explicit type information via optional type annotations. Yet, this extra information does not make type inference any easier: it simply gives rise to extra equations, leading to a more specific constraint.There are extensions of Hindley and Milner's type system where full type inference becomes undecidable or intractable. Then, it is common to require explicit type information, via mandatory type annotations. Polymorphic recursion is a simple and well-known instance of this phenomenon. This talk presents two more elaborate instances, commonly known as arbitrary-rank polymorphism and generalized algebraic data types.In both cases, type inference is made tractable thanks to mandatory type annotations. There is a twist, though: these required annotations are often numerous and redundant. So, it seems desirable to make them optional again, and to set up a distinct mechanism to guess some of the elided annotations. This mechanism, referred to as elaboration, can be heuristic. It must be predictable. In the two cases considered in this talk, it is a form of local type inference.This approach leads to a so-called stratified type inference system, where type information is propagated first in a local, ad hoc manner during elaboration, then in a possibly nonlocal, but well-specified manner during constraint solving. This appears to be one of the less displeasing ways of describing type inference systems that are able to exploit optional type annotations to infer better (or different) types.
Acute
Authors: Sewell Peter , Leifer James J. , Wansbrough Keith , Nardelli Francesco Zappa , Allen-Williams Mair , Habouzit Pierre , Vafeiadis Viktor
Published: November 2005

Existing languages provide good support for typeful programming of standalone programs. In a distributed system, however, there may be interaction between multiple instances of many distinct programs, sharing some (but not necessarily all) of their module structure, and with some instances rebuilt with new versions of certain modules as time goes on. In this paper we discuss programminglanguage support for such systems, focussing on their typing and naming issues.We describe an experimental language, Acute, which extends an ML core to support distributed development, deployment, and execution, allowing type-safe interaction between separately-built programs. The main features are: (1) type-safe marshalling of arbitrary values; (2) type names that are generated (freshly and by hashing) to ensure that type equality tests suffice to protect the invariants of abstract types, across the entire distributed system; (3) expression-level names generated to ensure that name equality tests suffice for type-safety of associated values, e.g. values carried on named channels; (4) controlled dynamic rebinding of marshalled values to local resources; and (5) thunkification of threads and mutexes to support computation mobility.These features are a large part of what is needed for typeful distributed programming. They are a relatively lightweight extension of ML, should be efficiently implementable, and are expressive enough to enable a wide variety of distributed infrastructure layers to be written as simple library code above the byte-string network and persistent store APIs. This disentangles the language runtime from communication intricacies. This paper highlights the main design choices in Acute. It is supported by a full language definition (of typing, compilation, and operational semantics), by a prototype implementation, and by example distribution libraries.
Recursive type generativity
Authors: Dreyer Derek
Published: November 2005

Existential types provide a simple and elegant foundation for understanding generative abstract data types, of the kind supported by the Standard ML module system. However, in attempting to extend ML with support for recursive modules, we have found that the traditional existential account of type generativity does not work well in the presence of mutually recursive module definitions. The key problem is that, in recursive modules, one may wish to define an abstract type in a context where a name for the type already exists, but the existential type mechanism does not allow one to do so.We propose a novel account of recursive type generativity that resolves this problem. The basic idea is to separate the act of generating a name for an abstract type from the act of defining its underlying representation. To define several abstract types recursively, one may first "forward-declare" them by generating their names, and then define each one secretly within its own defining expression. Intuitively, this can be viewed as a kind of backpatching semantics for recursion at the level of
types
. Care must be taken to ensure that a type name is not defined more than once, and that cycles do not arise among "transparent" type definitions.In contrast to the usual continuation-passing interpretation of existential types in terms of universal types, our account of type generativity suggests a
destination-passing
interpretation. Briefly, instead of viewing a value of existential type as something that creates a new abstract type every time it is unpacked, we view it as a function that takes as input a pre-existing undefined abstract type and defines it. By leaving the creation of the abstract type name up to the client of the existential, our approach makes it significantly easier to link abstract data types together recursively.
Combining programming with theorem proving
Authors: Chen Chiyan , Xi Hongwei
Published: November 2005

Applied Type System (
ATS
) is recently proposed as a framework for designing and formalizing (advanced) type systems in support of practical programming. In
ATS
, the definition of type equality involves a constraint relation, which may or may not be algorithmically decidable. To support practical programming, we adopted a design in the past that imposes certain restrictions on the syntactic form of constraints so that some effective means can be found for solving constraints automatically. Evidently, this is a rather
em ad hoc
design in its nature. In this design, which we claim to be both novel and practical. Instead of imposing syntactical restrictions on constraints, we provide a means for the programmer to construct proofs that attest to the validity of constraints. In particular, we are to accommodate a programming paradigm that enables the programmer to combine programming with theorem proving. Also we present some concrete examples in support of the practicality of this design.
A principled approach to operating system construction in Haskell
Authors: Hallgren Thomas , Jones Mark P. , Leslie Rebekah , Tolmach Andrew
Published: November 2005

We describe a monadic interface to low-level hardware features that is a suitable basis for building operating systems in Haskell. The interface includes primitives for controlling memory management hardware, user-mode process execution, and low-level device I/O. The interface enforces memory safety in nearly all circumstances. Its behavior is specified in part by formal assertions written in a programming logic called P-Logic. The interface has been implemented on bare IA32 hardware using the Glasgow Haskell Compiler (GHC) runtime system. We show how a variety of simple O/S kernels can be constructed on top of the interface, including a simple separation kernel and a demonstration system in which the kernel, window system, and all device drivers are written in Haskell.
Qualified types for MLF
Authors: Leijen Daan , Löh Andres
Published: November 2005

MLF is a type system that extends a functional language with impredicative rank-
n
polymorphism. Type inference remains possible and only in some clearly defined situations, a local type annotation is required. Qualified types are a general concept that can accommodate a wide range of type systems extension, for example, type classes in Haskell. We show how the theory of qualified types can be used seamlessly with the higher-ranked impredicative polymorphism of MLF, and give a solution to the non-trivial problem of evidence translation in the presence of impredicative datatypes.
Type inference, principal typings, and let-polymorphism for first-class mixin modules
Authors: Makholm Henning , Wells J. B.
Published: November 2005

A
mixin module
is a programming abstraction that simultaneously generalizes λ-abstractions, records, and mutually recursive definitions. Although various mixin module type systems have been developed, no one has investigated
principal typings
or developed
type inference
for first-class mixin modules, nor has anyone added Milner's
let-polymorphism
to such a system.This paper proves that typability is NP-complete for the naive approach followed by previous mixin module type systems. Because a λ-calculus extended with
record concatenation
is a simple restriction of our mixin module calculus, we also prove the folk belief that typability is NP-complete for the naive early type systems for record concatenation.To allow feasible type inference, we present Martini, a new system of
simple types
for mixin modules with
principal typings
. Martini is conceptually simple, with no subtyping and a clean and balanced separation between unification-based type inference with type and row variables and constraint solving for safety of linking and field extraction. We have implemented a type inference algorithm and we prove its complexity to be
O
(
n
2
), or
O
(
n
) given a fixed bound on the number of field labels. To prove the complexity, we need to present an algorithm for
row unification
that may have been implemented by others, but which we could not find written down anywhere. Because Martini has principal typings, we successfully extend it with Milner's let-polymorphism.
Continuations from generalized stack inspection
Authors: Pettyjohn Greg , Clements John , Marshall Joe , Krishnamurthi Shriram , Felleisen Matthias
Published: November 2005

Implementing first-class continuations can pose a challenge if the target machine makes no provisions for accessing and re-installing the run-time stack. In this paper, we present a novel translation that overcomes this problem. In the first half of the paper, we introduce a theoretical model that shows how to eliminate the capture and the use of first-class continuations in the presence of a generalized stack inspection mechanism. The second half of the paper explains how to translate this model into practice in two different contexts. First, we reformulate the servlet interaction language in the PLT Web server, which heavily relies on first-class continuations. Using our technique, servlet programs can be run directly under the control of non-cooperative web servers such as Apache. Second, we show how to use our new technique to copy and reconstitute the stack on MSIL.Net using exception handlers. This establishes that Scheme's first-class continuations can exist on non-cooperative virtual machines.
Fast narrowing-driven partial evaluation for inductively sequential programs
Authors: Ramos J. Guadalupe , Silva Josep , Vidal Germán
Published: November 2005

Narrowing-driven partial evaluation is a powerful technique for the specialization of (first-order) functional and functional logic programs. However, although it gives good results on small programs, it does not scale up well to realistic problems (e.g., interpreter specialization). In this work, we introduce a faster partial evaluation scheme by ensuring the termination of the process
offline
. For this purpose, we first characterize a class of programs which are
quasi-terminating
, i.e., the computations performed with needed narrowing—the symbolic computation mechanism of narrowing-driven partial evaluation—only contain finitely many different terms (and, thus, partial evaluation terminates). Since this class is quite restrictive, we also introduce an annotation algorithm for a broader class of programs so that they behave like quasi-terminating programs w.r.t. an extension of needed narrowing. Preliminary experiments are encouraging and demonstrate the usefulness of our approach.