bluuebunny/crossref_metadata_2025 huggingface dataset:
Hardware-software trade-offs in a direct Rambus implementation of the RAMpage memory hierarchy
Authors: Machanick Philip , Salverda Pierre , Pompe Lance
Published: November 2005

The RAMpage memory hierarchy is an alternative to the traditional division between cache and main memory: main memory is moved up a level and DRAM is used as a paging device. The idea behind RAMpage is to reduce hardware complexity, if at the cost of software complexity, with a view to allowing more flexible memory system design. This paper investigates some issues in choosing between RAMpage and a conventionalcache architecture, with a view to illustrating trade-offs which can be made in choosing whether to place complexity in the memory system in hardware or in software. Performance results in this paper are based on a simple Rambus implementation of DRAM, with performance characteristics of Direct Rambus, which should be available in 1999. This paper explores the conditions under which it becomes feasible to perform a context switch on a miss in the RAMpage model, and the conditions under which RAMpage is a win over a conventional cache architecture: as the CPU-DRAM speed gap grows, RAMpage becomes more viable.
An out-of-order execution technique for runtime binary translators
Authors: Le Bich C.
Published: November 2005

A dynamic translator emulates an instruction set architccturc by translating source instructions to native code during execution. On statically-scheduled hardware, higher performance can potentially be achieved by reordering the translated instructions; however, this is a challenging transformation if the source architecture supports precise exception semantics, and the user-level program is allowed to register exception handlers. This paper presents a software technique which allows a translator to achieve the out-of-order execution of user-level programs, while preserving all sequential semantics. The design combines a translator, an interpreter, and a set of operating system services. Using the proposed techniques, a dynamic translator can optimistically reorder instructions and speculate them across branch boundaries. If a mispeculated operation causes an exception, the recovery algorithm reverts the application state to a safe point, then retranslates the faulty code without reordering to disable further exceptions.
Variable length path branch prediction
Authors: Stark Jared , Evers Marius , Patt Yale N.
Published: November 2005

Accurate branch prediction is required to achieve high performance in deeply pipelined, wide-issue processors. Recent studies have shown that conditional and indirect (or computed) branch targets can be accuratelypredicted by recording the path, which consists of the target addresses of recent branches, leading up to the branch. In current path based branch predictors, the
N
most recent target addresses are hashed together to form an index into a table, where
N
is some fixed integer. The indexed table entry isused to make a prediction for the current branch.This paper introduces a new branch predictor in which the value of
N
is allowed to vary. By constructing the index into the table using the last
N
target addresses, and using profiling information to select the proper value of
N
for each branch, extremely accurate branch prediction is achieved. For the SPECint95 gee benchmark, this new predictor has a conditional branch misprediction rate of 4.3% given a 4K byte hardware budget. For comparison, the gshare predictor, a predictor known for its high accuracy, has a conditional branch misprediction rate of 8.8% given the same hardware budget. For the indirect branches in gee, the new predictor achieves a misprediction rate of 27.7% when given a hardware budget of 512 bytes, whereas the best competingpredictor achieves a misprediction rate of 44.2% when given the same hardware budget.
Capturing dynamic memory reference behavior with adaptive cache topology
Authors: Peir Jih-Kwon , Lee Yongjoon , Hsu Windsor W.
Published: November 2005

Memory references exhibit locality and are therefore not uniformly distributed across the sets of a cache. This skew reduces the effectiveness of a cache because it results in the caching of a considerable number of less-recently-used lines which are less likely to be re-referenced before they are replaced. In this paper, we describe a technique that dynamically identifies these less-recently-used lines and effectively utilizes the cache frames they occupy to more accurately approximate the global least-recently-used replacement policy while maintaining the fast access time of a direct-mapped cache. We also explore the idea of using these underutilized cache frames to reduce cache misses through data prefetching. In the proposed design, the possible locations that a line can reside in is not predetermined. Instead, the cache is dynamically partitioned into groups of cache lines. Because both the total number of groups and the individual group associativity adapt to the dynamic reference pattern, we call this design the adaptive group-associative cache. Performance evaluation using trace-driven simulations of the TPC-C benchmark and selected programs from the SPEC95 benchmark suite shows that the group-associative cache is able to achieve a hit ratio that is consistently better than that of a 4-way set-associative cache. For some of the workloads, the hit ratio approaches that of a fully-associative cache.
An empirical study of decentralized ILP execution models
Authors: Ranganathan Narayan , Franklin Manoj
Published: November 2005

Recent fascination for dynamic scheduling as a means for exploiting instruction-level parallelism has introduced significant interest in the scalability aspects of dynamic scheduling hardware. In order to overcome the scalability problems of centralized hardware schedulers, many decentralized execution models are being proposed and investigated recently. The crux of all these models is to split the instruction window across multiple processing elements (PEs) that do independent, scheduling of instructions. The decentralized execution models proposed so far can be grouped under 3 categories, based on the criterion used for assigning an instruction to a particular PE. They are: (i) execution unit dependence based decentralization (EDD), (ii) control dependence based decentralization (CDD), and (iii) data dependence based decentralization (DDD). This paper investigates the performance aspects of these three decentralization approaches. Using a suite of important benchmarks and realistic system parameters, we examine performance differences resulting from the type of partitioning as well as from specific implementation issues such as the type of PE interconnect.We found that with a ring-type PE interconnect, the DDD approach performs the best when the number of PEs is moderate, and that the CDD approach performs best when the number of PEs is large. The currently used approach---EDD---does not perform well for any configuration. With a realistic crossbar, performance does not increase with the number of PEs for any of the partitioning approaches. The results give insight into the best way to use the transistor budget available for implementing the instruction window.
Fast out-of-order processor simulation using memoization
Authors: Schnarr Eric , Larus James R.
Published: November 2005

Our new out-of-order processor simulatol; FastSim, uses two innovations to speed up simulation 8--15 times (vs. Wisconsin SimpleScalar) with no loss in simulation accuracy. First, FastSim uses speculative direct-execution to accelerate the functional emulation of speculatively executed program code. Second, it uses a variation on memoization---a well-known technique in programming language implementation---to cache microarchitecture states and the resulting simulator actions, and then "fast forwards" the simulation the next time a cached state is reached. Fast-forwarding accelerates simulation by an order of magnitude, while producing exactly the same, cycle-accurate result as conventional simulation.
Performance of database workloads on shared-memory systems with out-of-order processors
Authors: Ranganathan Parthasarathy , Gharachorloo Kourosh , Adve Sarita V. , Barroso Luiz André
Published: November 2005

Database applications such as online transaction processing (OLTP) and decision support systems (DSS) constitute the largest and fastest-growing segment of the market for multiprocessor servers. However, most current system designs have been optimized to perform well on scientific and engineering workloads. Given the radically different behavior of database workloads (especially OLTP), it is important to re-evaluate key system design decisions in the context of this important class of applications.This paper examines the behavior of database workloads on shared-memory multiprocessors with aggressive out-of-order processors, and considers simple optimizations that can provide further performance improvements. Our study is based on detailed simulations of the Oracle commercial database engine. The results show that the combination of out-of-order execution and multiple instruction issue is indeed effective in improving performance of database workloads, providing gains of 1.5 and 2.6 times over an in-order single-issue processor for OLTP and DSS, respectively. In addition, speculative techniques enable optimized implementations of memory consistency models that significantly improve the performance of stricter consistency models, bringing the performance to within 10--15% of the performance of more relaxed models.The second part of our study focuses on the more challenging OLTP workload. We show that an instruction stream buffer is effective in reducing the remaining instruction stalls in OLTP, providing a 17% reduction in execution time (approaching a perfect instruction cache to within 15%). Furthermore, our characterization shows that a large fraction of the data communication misses in OLTP exhibit migratory behavior; our preliminary results show that software prefetch and writeback/flush hints can be used for this data to further reduce execution time by 12%.
On the runtime complexity of type-directed unboxing
Authors: Minamide Yasuhiko , Garrigue Jacques
Published: November 2005

Avoiding boxing when representing native objects is essential for the efficient compilation of any programming language For polymorphic languages this task is difficult, but several schemes have been proposed that remove boxing on the basis of type information. Leroy's type-directed unboxing transformation is one of them. One of its nicest properties is that it relies only on visible types, which makes it compatible with separate compilation. However it has been noticed that it is not safe both in terms of time and space complexity ---
i.e
. transforming a program may raise its complexity. We propose a refinement of this transformation, still relying only on visible types, and prove that it satisfies the safety condition for time complexity. The proof is an extension of the usual logical relation method, in which correctness and safety are proved simultaneously.
YALE
Authors: Mackie Ian
Published: November 2005

Interaction nets provide a graphical paradigm of computation based on net rewriting. They have proved most successful in understanding the dynamics of reduction in the λ-calculus, where the prime example is the implementation of optimal reduction for the λ-calculus (Lamping's algorithm), given by Gonthier, Abadi and Lévy. However, efficient implementations of optimal reduction have had to break away from the interaction net paradigm. In this paper we give a new
efficient
interaction net encoding of the λ-calculus which is not optimal, but overcomes the inefficiencies caused by the bookkeeping operations in the implementations of optimal reduction. We believe that this implementation of the λ-calculus could provide the basis for highly efficient implementations of functional languages.
Lava
Authors: Bjesse Per , Claessen Koen , Sheeran Mary , Singh Satnam
Published: November 2005

Lava is a tool to assist circuit designers in specifying, designing, verifying and implementing hardware. It is a collection of Haskell modules. The system design exploits functional programming language features, such as monads and type classes, to provide multiple interpretations of circuit descriptions. These interpretations implement standard circuit analyses such as simulation, formal verification and the generation of code for the production of real circuits.Lava also uses polymorphism and higher order functions to provide more abstract and general descriptions than are possible in traditional hardware description languages. Two Fast Fourier Transform circuit examples illustrate this.
Functional differentiation of computer programs
Authors: Karczmarczuk Jerzy
Published: November 2005

We present two purely functional implementations of the
computational differentiation tools
-- the well known numeric (not symbolic!) techniques which permit to compute pointwise derivatives of functions defined by computer programs economically and
exactly
. We show how the co-recursive (lazy) algorithm formulation permits to construct in a transparent and elegant manner the entire infinite tower of derivatives of higher order for any expressions present in the program, and we present a purely functional variant of the
reverse
(or
adjoint
) mode of computational differentiation, using a chain of delayed evaluations represented by closures. Some concrete applications are also discussed.
Recycling continuations
Authors: Sobel Jonathan , Friedman Daniel P.
Published: November 2005

If the continuations in functional data-structure-generating programs are made explicit and represented as records, they can be "recycled." Once they have served their purpose as temporary, intermediate structures for managing program control, the space they occupy can be reused for the structures that the programs produce as their output. To effect this immediate memory reclamation, we use a sequence of correctness-preserving program transformations, demonstrated through a series of simple examples. We then apply the transformations to general anamorphism operators, with the important consequence that all finite-output anamorphisms can now be run without any stack- or continuation-space overhead.
Imperative streams—a monadic combinator library for synchronous programming
Authors: Scholz Enno
Published: November 2005

The paper presents a generalization of Haskell's IO monad suitable for synchronous concurrent programming. The new monad integrates the deterministic concurrency paradigm of synchronous programming with the powerful abstraction features of functional languages and with full support for imperative programming. For event-driven applications, it offers an alternative to the use of existing, thread-based concurrency extensions of functional languages. The concepts presented have been applied in practice in a framework for programming interactive graphics.
Implementing typed intermediate languages
Authors: Shao Zhong , League Christopher , Monnier Stefan
Published: November 2005

Recent advances in compiler technology have demonstrated the benefits of using strongly typed intermediate languages to compile richly typed source languages (e.g., ML). A type-preserving compiler can use types to guide advanced optimizations and to help generate provably secure mobile code. Types, unfortunately, are very hard to represent and manipulate efficiently; a naive implementation can easily add exponential overhead to the compilation and execution of a program. This paper describes our experience with implementing the FLINT typed intermediate language in the SML/NJ production compiler. We observe that a type-preserving compiler will not scale to handle large types unless all of its type-preserving stages preserve the asymptotic time and space usage in representing and manipulating types. We present a series of novel techniques for achieving this property and give empirical evidence of their effectiveness.
The memory fragmentation problem
Authors: Johnstone Mark S. , Wilson Paul R.
Published: November 2005

We show that for 8 real and varied C and C++ programs, several conventional dynamic storage allocators provide near-zero fragmentation, once we account for overheads due to implementation details such as headers, alignment, etc. This substantially strengthens our previous results showing that the memory fragmentation problem has generally been misunderstood, and that good allocator policies can provide good memory usage for most programs. The new results indicate that for most programs, excellent allocator policies are readily available, and efficiency of implementation is the major challenge. While we believe that our experimental results are state-of-the-art and our methodology is superior to most previous work, more work should be done to identify and study unusual problematic program behaviors not represented in our sample.
A non-fragmenting non-moving, garbage collector
Authors: Rodriguez-Rivera Gustavo , Spertus Michael , Fiterman Charles
Published: November 2005

One of the biggest disadvantages of non-moving collectors compared to moving collectors has been their limited ability to deal with memory fragmentation. In this paper, we describe two techniques to reduce fragmentation without the need for moving live data. The first technique reduces internal fragmentation in BiBoP (Big-Bag-of-Pages) like allocators. The second technique reduces external fragmentation using virtual memory culls available in most modern operating systems. It can also reduce the size of the heap after periods of great activity in long lived applications. These techniques have been successfully used in Geodesic Systems' Great Circle, a commercially-available conservative garbage collector. This paper describes these techniques, their implementation, and some experimental results.
Guaranteeing non-disruptiveness and real-time deadlines in an incremental garbage collector
Authors: Siebert Fridtjof
Published: November 2005

For Garbage Collection (GC) to be a generally accepted means of memory management it is required to prove its efficiency. This paper presents a scheme that guarantees that an incremental Garbage Collector will have completed its collection cycle before the system runs out of memory. Furthermore, it is shown that the work that has to be done by the collector in one incremental step is limited by a small constant depending on the percentage of total memory used by the application program. This result then allows a suitable trade-off between memory demand and GC overhead to be found.
A study of large object spaces
Authors: Hicks Michael , Hornof Luke , Moore Jonathan T. , Nettles Scott M.
Published: November 2005

This paper examines the design space for copying garbage collectors (GCs) in which "large objects" are managed in a separate, non-copy-collected space. We focus on two main issues:1. how to set the policy for classifying objects as "large"2. how to manage the large object spaceWe explore these issues experimentally using the Oscar GC testbed. In particular, we vary the threshold size of large objects and also whether the objects may contain pointers. Furthermore, we compare the performance of treadmill collection to that of mark-and-sweep collection for managing the large object space.We find that for some heaps there is a minimum cutoff size below which adding objects to the large object space does not result in a performance improvement, while for others no such cutoff exists. In general, including pointer-containing objects in the large object space seems beneficial. Finally, the exact method used to collect the large object space does not significantly influence overall performance.
The design of a class mechanism for Moby
Authors: Fisher Kathleen , Reppy John
Published: November 2005

Typical class-based languages, such as C++ and JAVA, provide complex class mechanisms but only weak module systems. In fact, classes in these languages incorporate many of the features found in richer module mechanisms. In this paper, we describe an alternative approach to designing a language that has both classes and modules. In our design, we rely on a rich ML-style module system to provide features such as visibility control and parameterization, while providing a minimal class mechanism that includes only those features needed to support inheritance. Programmers can then use the combination of modules and classes to implement the full range of class-based features and idioms. Our approach has the advantage that it provides a full-featured module system (useful in its own right), while keeping the class mechanism quite simple.We have incorporated this design in MOBY, which is an ML-style language that supports class-based object-oriented programming. In this paper, we describe our design via a series of simple examples, show how various class-based features and idioms are realized in MOBY, compare our design with others, and sketch its formal semantics.
Pointer analysis for multithreaded programs
Authors: Rugina Radu , Rinard Martin
Published: November 2005

This paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. For each pointer and each program point, the algorithm computes a conservative approximation of the memory locations to which that pointer may point. The algorithm correctly handles a full range of constructs in multithreaded programs, including recursive functions, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between pointer variables of different types, heap and stack allocated memory, shared global variables, and thread-private global variables.We have implemented the algorithm in the SUIF compiler system and used the implementation to analyze a sizable set of multithreaded programs written in the Cilk multithreaded programming language. Our experimental results show that the analysis has good precision and converges quickly for our set of Cilk programs.
Support for garbage collection at every instruction in a Java compiler
Authors: Stichnoth James M. , Lueh Guei-Yuan , Cierniak Michał
Published: November 2005

A high-performance implementation of a Java Virtual Machine
1
requires a compiler to translate Java bytecodes into native instructions, as well as an advanced garbage collector (e.g., copying or generational). When the Java heap is exhausted and the garbage collector executes, the compiler must report to the garbage collector all live object references contained in physical registers and stack locations. Typical compilers only allow certain instructions (e.g., call instructions and backward branches) to be
GC-safe
; if GC happens at some other instruction, the compiler may need to advance execution to the next GC-safe point. Until now, no one has ever attempted to make
every
compiler-generated instruction GC-safe, due to the perception that recording this information would require too much space. This kind of support could improve the GC performance in multithreaded applications. We show how to use simple compression techniques to reduce the size of the GC map to about 20% of the generated code size, a result that is competitive with the best previously published results. In addition, we extend the work of Agesen, Detlefs, and Moss, regarding the so-called "JSR Problem" (the single exception to Java's type safety property), in a way that eliminates the need for extra runtime overhead in the generated code.
Storage assignment optimizations to generate compact and efficient code on embedded DSPs
Authors: Rao Amit , Pande Santosh
Published: November 2005

DSP architectures typically provide dedicated memory address generation units and indirect addressing modes with auto-increment and auto-decrement that subsume address arithmetic calculation. The heavy use of auto-increment and auto-decrement indirect addressing require DSP compilers to perform a careful placement of variables in storage to minimize address arithmetic instructions to generate compact and efficient DSP code. Liao et al. formulated the problem of storage assignment as the simple offset assignment problem (SOA) and the general offset assignment problem (GOA), and proposed heuristic solutions.The storage allocation of variables critically depends on the sequence of variable accesses. In this paper we present techniques to optimize the access sequence of variables by applying algebraic transformations (such as commutativity and associativity) on expression trees to obtain the least cost offset assignment. We develop a new formulation of this problem as the least cost access sequence problem (LCAS). Based on the proposed framework, we develop heuristic algorithms that determine empirically near-optimal solutions resulting in fewer address arithmetic instructions. We have implemented the proposed heuristic algorithms by extending the storage assignment optimization in the SPAM compiler back-end targeted for the TMS320C25 DSP. In the case of SOA, experimental results for programs from the DSPstone benchmark suite show an average improvement of 3.36% in static code size and an average relative speed-up of 7.28% over results obtained using existing SOA algorithms. The average code size reduction over code compiled with a naive storage assignment algorithm is 7.04%. The proposed framework has also been applied to the GOA problem and shows average code size reductions of 2.04% over results obtained using existing GOA algorithms, and average code size reductions of 10.84% over a naive GOA algorithm. Code size reduction and improvement in dynamic instruction counts could be valuable given limited memory and real-time response requirements placed on embedded systems.
ASAP—a simple assertion pre-processor
Authors: Curcio Igor D.D.
Published: November 2005

Assertions are widely known as a powerful tool to detect software faults during the debugging of software systems. Despite the maturity of software engineering tools, assertions are seldom used in practice. ASAP is a pre-processor for C programs which implements several concepts defmed in the theory of formal specification, such as preconditions, postconditions, assertions related to intermediate states, loop invariants and variants, existential and universal quantifiers. In this paper, the notion of software contract is introduced, and shown how it is applicable with assertions. Finally, a collection of useful examples is given, and ASAP design and implementation is described.
Java and distributed object models
Authors: Hericko Marjan , Juric Matjaz B. , Zivkovic Ales , Rozman Ivan , Domajnko Tomaz , Krisper Marjan
Published: November 2005

Java has an important role in building distributed object oriented web enabled applications. In the article an analysis of two distributed object models in context of Java language is presented. Several aspects of RMI and CORBA such as features, maturity, support for legacy systems, learning curve and ease of development are compared. A special emphasis is given to the performances. Different testing scenarios give a complete overview about real world performances of both architectures. Based on the comparison results, recommendations for selecting the most appropriate architecture for a given problem domain are presented. Therefore the paper contributes to the understanding of the distributed object architectures and to the study of Java RMI and CORBA performances.
Evolution of the high level programming languages
Authors: Malik Masud Ahmad
Published: November 2005

Programming languages have emerged as the powerful tools we use to describe algorithms for execution by computers. Ever since need for such languages was felt half a century ago, numerous languages have been designed and implemented with varying goals and for different application areas. This article reviews the evolution of the imperative high level programming languages and critically examines the factors that influenced different design efforts and direction of programming language design, from Zuse's Plankalkul to the present day object-oriented programming languages.
Reverse execution of programs
Authors: Biswas Bitan , Mall R.
Published: November 2005

Conventional debuggers do not allow users to go back and examine the program states at statements which have already been executed. In case the user wants to examine the program state at a statement which was executed sometime back, he is forced to restart the entire debugging process. To overcome this problem, we examine the issue of reverse execution of programs. To this end, we introduce the concept of
inverse of a statement
. We describe our implementation of a debugger which can execute C programs in either forward or backward direction depending upon an option set by the user. Our approach is easily extendible to other programming languages.
A novel program representation for interprocedural analysis
Authors: Agrawal Gagan , Murthy Shyamala , Garud Chandrashekhar
Published: November 2005

Interprocedural optimizations and transformations are increasingly being used in industrial and academic compilers, especially the compilers for high performance systems. Interprocedural analysis involves a natural trade-off between the accuracy and efficiency of the analysis, which is typically manifested in the choice of program representation. In this paper, we present a novel full program representation, which we believe is concise enough to keep the compilation costs reasonable, but is detailed enough for useful flow-sensitive optimizations. We report on our experience in developing two novel optimization frameworks using this representation. We have implemented this framework on top of the SUIF infrastructure. We present the comparison of the size of the call graph, Myer's supergraph, and our representation on a set of benchmark programs.
Minimizing cost of local variables access for DSP-processors
Authors: Eckstein Erik , Krall Andreas
Published: November 2005

Recent work on compilation for DSP-processors deals with optimizing access to local variables of functions. The common way is to use one or more address registers as pointers into the functions stack frame and modify it with post modify addressing modes (which are sometimes the only addressing modes). Additionally to previous work we present an algorithm which assigns frame pointer values over a whole procedure. Our algorithm also deals with basic blocks, which have no accesses to local variables. The algorithm works with a new data structure, the control flow line graph, which is derived from the control flow graph. In our experiments, the algorithm showed improvements to similar algorithms.
Modulo scheduling for the TMS320C6x VLIW DSP architecture
Authors: Stotzer Eric , Leiss Ernst
Published: November 2005

Digital Signal Processing (DSP) architectures are specialized for high performance numerical algorithms such as those found in communication and multimedia applications. The development of efficient compilers for DSP processors is a growing research area. The Texas Instruments TMS320C6x (C6x) is a Very Long Instruction Word (VLIW) DSP architecture capable of issuing eight operations in parallel. In this paper, we present the results of implementing a software pipelining algorithm for the C6x. We provide a description of the C6x and detail the architectural features that impact software pipelining such as a moderately sized register file, constraints on code size, homogeneous resources, and multiple assignment code. We discuss how we adapted modulo scheduling to implement software pipelining for the C6x. Finally, we present the results of modulo scheduling a set of 40 loop kernel benchmarks and measure the algorithm in terms of schedule quality and algorithm complexity.
Pipeline behavior prediction for superscalar processors by abstract interpretation
Authors: Schneider Jörn , Ferdinand Christian
Published: November 2005

For real time systems not only the logical function is important but also the timing behavior, e. g. hard real time systems must react inside their deadlines. To guarantee this it is necessary to know upper bounds for the worst case execution times (WCETs). The accuracy of the prediction of WCETs depends strongly on the ability to model the features of the target processor.Cache memories, pipelines and parallel functional units are architectural components which are responsible for the speed gain of modern processors. It is not trivial to determine their influence when predicting the worst case execution time of programs.This paper describes a method to predict the behavior of pipelined superscalar processors and reports initial results of a prototypical implementation for the SuperSPARC I processor.
Why SpecInt95 should not be used to benchmark embedded systems tools
Authors: Engblom Jakob
Published: November 2005

The SpecInt95 benchmark suite is often used to evaluate the performance of programming tools, including those used for embedded systems programming. Embedded applications, however, are often targeting 8- or 16-bit processors with limited functionality, whereas SpecInt95 has no particular target architecture and a bias towards 32-bit systems. Hence, there are reasons to question the use of SpecInt95 for the evaluation of tools for embedded systems.We present a comparative study of the static properties of a set of embedded application and the SpecInt95 benchmarks. The properties studied include: variable types, function argument lists, type of operations, and the use of local and global memory.The study provides-clear evidence that embedded applications and the SpecInt95 program suite differs significantly in several important areas. Hence, we conclude that using SpecInt95 to evaluate or compare tools for embedded systems is likely to be irrelevant or misleading, and that there is a clear need for a benchmark suite tailored for the embedded applications area.
When is a functional program not a functional program?
Authors: Longley John
Published: November 2005

In an impure functional language, there are programs whose behaviour is completely functional (in that they behave extensionally on inputs), but the functions they compute cannot be written in the purely functional fragment of the language. That is, the class of programs with functional behaviour is more expressive than the usual class of pure functional programs. In this paper we introduce this extended class of "functional" programs by means of examples in Standard ML, and explore what they might have to offer to programmers and language implementors.After reviewing some theoretical background, we present some examples of functions of the above kind, and discuss how they may be implemented. We then consider two possible programming applications for these functions: the implementation of a search algorithm, and an algorithm for exact real-number integration. We discuss the advantages and limitations of this style of programming relative to other approaches. We also consider the increased scope for compiler optimizations that these functions would offer.
On embedding a microarchitectural design language within Haskell
Authors: Launchbury John , Lewis Jeffrey R. , Cook Byron
Published: November 2005

Based on our experience with modelling and verifying microarchitectural designs within Haskell, this paper examines our use of Haskell as host for an embedded language. In particular, we highlight our use of Haskell's lazy lists, type classes, lazy state monad, and unsafe Perform I0, and point to several areas where Haskell could be improved in the future. We end with an example of a benefit gained by bringing the functional perspective to microarchitectural modelling.
Recursion and dynamic data-structures in bounded space
Authors: Hughes John , Pareto Lars
Published: November 2005

We present a functional language with a type system such that well typed programs run within stated space-bounds. The language is a strict, first-order variant of ML with constructs for explicit storage management. The type system is a variant of Tofte and Talpin's region inference system to which the notion of sized types, of Hughes, Pareto and Sabry, has been added.
Calling hell from heaven and heaven from hell
Authors: Finne Sigbjorn , Leijen Daan , Meijer Erik , Peyton Jones Simon
Published: November 2005

The increasing popularity of component-based programming tools offer a big opportunity to designers of advanced programming languages, such as Haskell. If we can package our programs as software components, then it is easy to integrate them into applications written in other languages.In earlier work we described a preliminary integration of Haskell with Microsoft's Component Object Model (COM), focusing on how Haskell can create and invoke COM objects. This paper develops that work, concentrating on the mechanisms that support externally-callable Haskell functions, and the encapsulation of Haskell programs as COM objects.
Representing Java classes in a typed intermediate language
Authors: League Christopher , Shao Zhong , Trifonov Valery
Published: November 2005

We propose a conservative extension of the polymorphic lambda calculus (
F
ω
) as an intermediate language for compiling languages with name-based class and interface hierarchies. Our extension enriches standard
F
ω
with recursive types, existential types, and row polymorphism, but only ordered records with no subtyping. Basing our language on
F
ω
makes it also a suitable target for translation from other higher-order languages; this enables the safe interoperation between class-based and higher-order languages and the reuse of common type-directed optimization techniques, compiler back ends, and runtime support.We present the formal semantics of our intermediate language and illustrate its features by providing a formal translation from a subset of Java, including classes, interfaces, and private instance variables. The translation preserves the name-based hierarchical relation between Java classes and interfaces, and allows access to private instance variables of parameters of the same class as the one defining the method. It also exposes the details of method invocation and instance variable access and allows many standard optimizations to be performed on the object-oriented code.
Verification of Erlang programs using abstract interpretation and model checking
Authors: Huch Frank
Published: November 2005

We present an approach for the verification of Erlang programs using abstract interpretation and model checking. In general model checking for temporal logics like LTL and Erlang programs is undecidable. Therefore we define a frame-work for abstract interpretations for a core fragment of Erlang. In this framework it is guaranteed, that the abstract operational semantics preserves all paths of the standard operational semantics. We consider properties that have to hold on all paths of a system, like properties in LTL. If these properties can be proved for the abstract operational semantics, they also hold for the Erlang program. They can be proved with model checking if the abstract operational semantics is a finite transition system. Therefore we introduce a example abstract interpretation, which has this property. We have implemented this approach as a prototype and were able to prove properties like mutual exclusion or the absence of deadlocks and lifelocks for some Erlang programs.
Escape analysis for object-oriented languages
Authors: Blanchet Bruno
Published: November 2005

Escape analysis [27, 14, 5] is a static analysis that determines whether the lifetime of data exceeds its static scope.

The main originality of our escape analysis is that it determines precisely the effect of assignments, which is necessary to apply it to object oriented languages with promising results, whereas previous work [27, 14, 5] applied it to functional languages and were very imprecise on assignments. Our implementation analyses the full Java™ Language.

We have applied our analysis to stack allocation and synchronization elimination. We manage to stack allocate 13% to 95% of data, eliminate more than 20% of synchronizations on most programs (94% and 99% on two examples) and get up to 44% speedup (21% on average). Our detailed experimental study on large programs shows that the improvement comes from the decrease of the garbage collection and allocation times than from improvements on data locality [7], contrary to what happened for ML [5].
A language for specifying recursive traversals of object structures
Authors: Ovlinger Johan , Wand Mitchell
Published: November 2005

We present a domain-specific language for specifying recursive traversals of object structures, for use with the visitor pattern. Traversals are traditionally specified as iterations, forcing the programmer to adopt an imperative style, or are hard-coded into the program or visitor. Our proposal allows a number of problems best approached by recursive means to be tackled with the visitor pattern, while retaining the benefits of a separate traversal specification.
Semantic analysis of virtual classes and nested classes
Authors: Madsen Ole Lehrmann
Published: November 2005

Virtual classes and nested classes are distinguishing features of BETA. Nested classes originated from Simula, but until recently they have not been part of main stream object- oriented languages. C++ has a restricted form of nested classes and they were included in Java 1.1. Virtual classes is the BETA mechanism for expressing generic classes and virtual classes is an alternative to parameterized classes. There has recently been an increasing interest in virtual classes and a number of proposals for adding virtual classes to other languages, extending virtual classes, and unifying virtual classes and parameterized classes have been made. Although virtual classes and nested classes have been used in BETA for more than a decade, their implementation has not been published. The purpose of this paper is to contribute to the understanding of virtual classes and nested classes by presenting the central elements of the semantic analysis used in the Mjølner BETA compiler.
A formal framework for the Java bytecode language and verifier
Authors: Freund Stephen N. , Mitchell John C.
Published: November 2005

This paper presents a sound type system for a large subset of the Java bytecode language including classes, interfaces, constructors, methods, exceptions, and bytecode subroutines. This work serves as the foundation for developing a formal specification of the bytecode language and the Java Virtual Machine's bytecode verifier. We also describe a prototype implementation of a type checker for our system and discuss some of the other applications of this work. For example, we show how to extend our work to examine other program properties, such as the correct use of object locks.
Space and time-efficient memory layout for multiple inheritance
Authors: Sweeney Peter F. , Gil Joseph (Yossi)
Published: November 2005

Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object space. For example, the number of compiler-generated fields in a certain object can be as large as quadratic in the number of its subobjects. The problem of efficient object layout is compounded by the need to support two different semantics of multiple inheritance:
shared,
in which a base class inherited along distinct paths occurs only once in the derived class, and
repeated,
in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques to optimize memory layout for multiple inheritance. The main ideas behind these techniques are the inlining of virtual bases and bidirectional memory layout. Our techniques never increase time overhead, and usually even decrease it. We show that in some example hierarchies, more than ten-fold reduction in the space overhead can be achieved. We analyze the complexity of the algorithms to apply these techniques, and give theorems to estimate the efficacy of this application. For concreteness, techniques and examples are discussed in the context of C++.
Atlas
Authors: Kersten Mik , Murphy Gail C.
Published: November 2005

The Advanced Teaching and Learning Academic Server (Atlas) is a software system that supports web-based learning. Students can register for courses, and can navigate through personalized views of course material. Atlas has been built according to Sun Microsystem's Java™ Servlet specification using Xerox PARC's aspect-oriented programming support called Aspect™. Since aspect-oriented programming is still in its infancy, little experience with employing this paradigm is currently available. In this paper, we start filling this gap by describing the aspects we used in Atlas and by discussing the effect of aspects on our object-oriented development practices. We describe some rules and policies that we employed to achieve our goals of maintainability and modifiability, and introduce a straightforward notation to express the design of aspects. Although we faced some obstacles along the way, this combination of technology helped us build a fast, well-structured system in a reasonable amount of time.
Role model designs and implementations with aspect-oriented programming
Authors: Kendall Elizabeth A.
Published: November 2005

This paper describes research in applications of aspect-oriented programming (AOP) as captured in the AspectJ™ language. In particular, it compares object-oriented and aspect-oriented designs and implementations of role models.

Sections 1, 2, and 3 provide background information on role models, object-oriented role model implementations, and aspect-oriented programming, respectively. New aspect-oriented designs for role models are explored in sections 4, 5, and 6.

The base reference for this exploration is the Role Object pattern. Although useful for role models, this pattern introduces some problems at the implementation level, namely object schizophrenia, significant interface maintenance, and no support for role composition. Our research has resulted in alternative aspect-oriented designs that alleviate some of these problems.

Section 7 discusses how an agent framework that implements role models has been partially reengineered with aspects. The reengineering addressed concerns that are orthogonal or cross cut both the core and the role behavior. The aspect oriented redesign significantly reduced code tangling, overall method and module count, and total lines of code. These results and other conclusions are presented in section 8.
Zones, contracts and absorbing changes
Authors: Evans Huw , Dickman Peter
Published: November 2005

This paper describes a novel approach to managing the evolution of distributed, persistent systems at run-time. This is achieved by partitioning a system into disjoint
zones
, each of which can be evolved without affecting code in any other.
Contracts
are defined between zones, making type-level interdependencies and inter-zone communication explicit. Programmer supplied code is added to the running system, at the boundary between zones, to constrain the scope of changes. A change methodology is presented which the software engineer uses to help describe and manage the evolution of the system. Knowledge of the application semantics is essential when evolving a system and our approach allows the engineer to concentrate on these semantic aspects of change. Our Java-based demonstration platform and methodology reduce or remove some of the burdensome tasks the software engineer is normally expected to perform when changing a system, making evolution more tractable.