bluuebunny/crossref_metadata_2025 huggingface dataset:
Design space optimization of embedded memory systems via data remapping
Authors: Palem Krishna V. , Rabbah Rodric M. , Mooney Vincent J. , Korkmaz Pinar , Puttaswamy Kiran
Published: November 2005

In this paper, we provide a novel compile-time
data remapping
algorithm that runs in linear time. This remapping algorithm is the first fully automatic approach applicable to pointer-intensive dynamic applications. We show that data remapping can be used to significantly reduce the
energy consumed
as well as the
memory size
needed to meet a user-specified performance goal (i.e., execution time) -- relative to the same application executing without being remapped. These twin advantages afforded by a remapped program -- reduced cache size and energy needs -- constitute a key step in a framework for design space exploration: for any given performance goal, remapping allows the user to reduce the primary and secondary cache size by 50%, yielding a concomitant energy savings of 57%. Additionally, viewed as a compiler optimization for a fixed processor, we show that remapping improves the energy consumed by the cache subsystem by 25%. All of the above savings are in the context of the cache subsystem in isolation. We also show that remapping yields an average 20% energy saving for an ARM-like processor and cache subsystem. All of our improvements are achieved in the context of DIS, O
lden
and SPEC2000 pointer-centric benchmarks.
Automatic formal verification for scheduled VLIW code
Authors: Feng Xiushan , Hu Alan J.
Published: November 2005

VLIW processors are attractive for many embedded applications, but VLIW code scheduling, whether by hand or by compiler, is extremely challenging. In this paper, we extend previous work on automated verification of low-level software to handle the complexity of modern, aggressive VLIW designs, e.g., the exposed parallelism, pipelining, and resource constraints. We implement these ideas into a prototype tool for verifying short sequences of assembly code for TI's C62x family of VLIW DSPs, and demonstrate the effectiveness of the tool in quickly verifying, or finding bugs in, two difficult-to-analyze code segments.
Optimal integrated code generation for clustered VLIW architectures
Authors: Kessler Christoph , Bednarski Andrzej
Published: November 2005

In contrast to standard compilers, generating code for DSPs can afford spending considerable resources in time and space on optimizations. Generating efficient code for irregular architectures requires an integrated method that optimizes simultaneously for instruction selection, instruction scheduling, and register allocation.We describe a method for fully integrated optimal code generation based on dynamic programming. We introduce the concept of
residence classes
and
space profiles
, which allows us to describe and optimize for irregular register and memory structures. In order to obtain a retargetable framework we introduce a structured architecture description language, ADML, which is based on XML. We implemented a prototype of such a retargetable system for optimal code generation. Results for variants of the TI C62x show that our method can produce optimal solutions to small but nontrivial problem instances with a reasonable amount of time and space.
Loop fusion for clustered VLIW architectures
Authors: Qian Yi , Carr Steve , Sweany Philip
Published: November 2005

Embedded systems require maximum performance from a processor within significant constraints in power consumption and chip cost. Using software pipelining, high-performance digital signal processors can often exploit considerable instruction-level parallelism (ILP), and thus significantly improve performance. However, software pipelining, in some instances, hinders the goals of low power consumption and low chip cost. Specifically, the registers required by a software pipelined loop may exceed the size of the physical register set.The register pressure problem incurred by software pipelining makes it difficult to build a high-performance embedded processor with a single, multi-ported register bank with enough registers to support high levels of ILP while maintaining clock speed and limiting power consumption. The large number of ports required to support a single register bank severely hampers access time. The port requirement for a register bank can be reduced via hardware by partitioning the register bank into multiple banks connected to disjoint subsets of functional units, called
clusters
. Since a functional unit is not directly connected to all register banks, wasted energy and resources can result due to delays incurred when accessing "non-local" registers.The overhead due to partitioning of the register set can be ameliorated by using high-level compiler loop optimization techniques such as unrolling, unroll-and-jam and fusion. High-level loop optimizations spread data-independent parallelism across clusters that may not require "non-local" register accesses and can provide work to hide the latency of any such register accesses that are needed.In this paper, we examine the effects of loop fusion on DSP loops run on four simulated, clustered VLIW architectures and the Texas Instruments TMS320C64x. Our experiments show a 1.3 -- 2 harmonic mean speedup.
Inter-task register-allocation for static operating systems
Authors: Barthelmann Volker
Published: November 2005

In recent years, a growing number of small single-chip embedded systems are used in very high volumes, for example in the automotive industry. Due to the high volumes, these systems are very cost-sensitive. This is one of several reasons why they are more and more using static operating systems. In such systems, all system resources are configured offline and an optimized kernel is generated which is tailored to one specific application.While this allows the use of operating systems for small ECUs with only very few KB of RAM, it is observed that the memory needed to store task contexts (i.e. register sets) in case of task preemptions makes up a significant part of the RAM needed by the operating system (especially on chips with large register files).This paper presents ideas and a first implementation on methods to reduce this space through interaction of the compiler and the operating system generation. Together they can calculate an upper bound for the register set that has to be stored for each task. Also, the scope for the register allocator of the compiler can be extended to allocate registers across tasks in order to minimize the total size of RAM needed for task contexts.
VISTA
Authors: Zhao Wankang , Cai Baosheng , Whalley David , Bailey Mark W. , van Engelen Robert , Yuan Xin , Hiser Jason D. , Davidson Jack W. , Gallivan Kyle , Jones Douglas L.
Published: November 2005

Software designers face many challenges when developing applications for embedded systems. A major challenge is meeting the conflicting constraints of speed, code density, and power consumption. Traditional optimizing compiler technology is usually of little help in addressing this challenge. To meet speed, power, and size constraints, application developers typically resort to hand-coded assembly language. The results are software systems that are not portable, less robust, and more costly to develop and maintain. This paper describes a new code improvement paradigm implemented in a system called
vista
that can help achieve the cost/performance trade-offs that embedded applications demand. Unlike traditional compilation systems where the smallest unit of compilation is typically a function and the programmer has no control over the code improvement process other than what types of code improvements to perform, the
vista
system opens the code improvement process and gives the application programmer, when necessary, the ability to finely control it. In particular,
vista
allows the application developer to (1) direct the order and scope in which the code improvement phases are applied, (2) manually specify code transformations, (3) undo previously applied transformations, and (4) view the low-level program representation graphically. vista can be used by embedded systems developers to produce applications, by compiler writers to prototype and debug new low-level code transformations, and by instructors to illustrate code transformations (e.g., in a compilers course).
Compiler-directed cache polymorphism
Authors: Hu J. S. , Kandemir M. , Vijaykrishnan N. , Irwin M. J. , Saputra H. , Zhang W.
Published: November 2005

Classical compiler optimizations assume a fixed cache architecture and modify the program to take best advantage of it. In some cases, this may not be the best strategy because each loop nest might work best with a different cache configuration and transforming a nest for a given fixed cache configuration may not be possible due to data dependences. Working with a fixed cache configuration can also increase energy consumption in loops where the best required configuration is smaller than the default (fixed) one. In this paper, we take an alternate approach and modify the cache configuration for each nest depending on the access pattern exhibited by the nest. We call this technique
compiler-directed cache polymorphism
(CDCP). More specifically, in this paper, we make the following contributions. First, we present an approach for analyzing data reuse properties of loop nests. Second, we give algorithms to simulate the footprints of array references in their reuse space. Third, based on our reuse analysis, we present an optimization algorithm to compute the cache configurations for each nest. Our experimental results show that CDCP is very effective in finding the near-optimal data cache configurations for different nests in array-intensive applications.
Analysis and detection of computer viruses and worms
Authors: Singh Prabhat K. , Lakhotia Arun
Published: November 2005

This annotated bibliography reviews research in analyzing and detecting computer viruses and worms. This document focuses on papers that give information about techniques and systems detecting malicious code.
Objects for lexical analysis
Authors: Kühl Bernd , Schreiner Axel-Tobias
Published: November 2005

This paper presents a new idea for lexical analysis:
lolo
(language-oriented lexer objects) is strictly based on the object orientation paradigm. We introduce the idea behind the system, describe the implementation, and compare it to the conventional approach using
lex
[1] or
flex
[2].
lolo
[3] extracts symbols from a sequence of input characters belonging to the ASCII or Unicode sets.
lolo
scanners can be extended without access to the source code: symbol recognizers can be derived by inheritance and an executing scanner can be reconfigured for different contexts. Recognizer actions are represented by objects which may be replaced at any time. Recognizers need not be based on finite state automata; therefore,
lolo
can recognize symbols that systems like
lex
cannot recognize directly.
Efficient concise deterministic pattern-matching automata for ambiguous patterns
Authors: Nedjah Nadia , de Macedo Mourelle Luiza
Published: November 2005

Pattern-matching is a fundamental feature in many applications such as functional programming, logic programming, theorem proving, term rewriting and rule-based expert systems. Usually, patterns are pre-processed into a deterministic finite automaton. Using such an automaton allows one to determine the matched pattern(s) by a single scan of the input term. The matching automaton is typically based on left-to-right traversal of patterns. With ambiguous patterns a subject term may be an instance of more than one pattern. To select the pattern to use, a priority rule is usually engaged. The pre-processing of the patterns adds new patterns which are instances of the original ones. When the original patterns are ambiguous, some of the instances supplied may be irrelevant for the matching process. They may cause an unnecessary increase in the space requirements of the automaton and may also reduce the time efficiency of the matching process. Here, we devise a new pre-processing operation that recognises and avoids such irrelevant instances and hence improves space and time requirements for the matching automaton.
Bit-vector encoding of n-queen problem
Authors: Zongyan Qiu
Published: November 2005

8-queen problem and its generalization,
n
-queen problem are well-known examples in the textbooks on elementary programming, data structures, and algorithms. Different methods are proposed to solve these problems, for example, in [1]. In this paper, we present a purely bit-vector encoding of the
n
-queen problem. It is very natural, simple to understand, and efficient. It involves only bit-wise operations.
A study of compiler techniques for multiple targets in compiler infrastructures
Authors: Guilan Dai , Suqing Zhang , Jinlan Tian , Weidu Jiang
Published: November 2005

Compilers are critical for embedded systems and high performance computing. A compiler infrastructure provides an infrastructure for rapid development of high quality compilers. Based on main components of compiler infrastructures, this paper reviews representative compiler infrastructure products, and summarizes their features. It focuses on an insight analysis of the key techniques for building the compiler back ends, and presents our probes into compiler infrastructures for typical issues.
SXML specification
Authors: Kiselyov Oleg
Published: November 2005

The present article specifies revision 2.1 of SXML. SXML is an abstract syntax tree of an XML document. SXML is also a concrete representation of the XML Infoset in the form of S-expressions. The generic tree structure of SXML lends itself to a compact library of combinators for querying and transforming SXML.The master SXML specification file is written in SXML itself. The present paper is the result of translating that SXML code into L
A
T
E
X, using an appropriate "stylesheet". A different stylesheet converted the specification to HTML. The master file, the stylesheets and the corresponding HTML and L
A
T
E
Xdocuments are available at http://pobox.com/~oleg/ftp/Scheme/xml.html.
Portable software in modular Pascal
Authors: Neusius C.
Published: November 2005

The extension of the programming language Pascal with the concept of separate compilation is widespread but not standardized. To gain portability without loss of this extension, the technique of precompilation is used [EF88], [Br87], [Na87], [PM86]. This means that a (self-defined) extension of Pascal can be translated into a variety of pascal dialects. This paper describes the concepts of the language PM and its programming environment (precompiler and code maintenance system). It was specifically developed as a tool for a research project concerned with heterogeneous computing systems [Ge87].
Towards more natural functional programming languages
Authors: Myers Brad A.
Published: November 2005

Programming languages are the way for a person to express a mental plan in a way that the computer can understand. Therefore, it is appropriate to consider properties of people when designing new programming languages. In our research, we are investigating how people think about algorithms, and how programming languages can be made easier to learn and more effective for people to use. By taking human-productivity aspects of programming languages seriously, designers can more effectively match programming language features with human capabilities and problem solving methods. Human factors methods can be used to measure the effects, so unsubstantiated claims can be avoided.This talk will present a quick summary of new and old results in what is known about people and programming, from areas that are sometimes called "empirical studies of programmers" and "psychology of programming." Much is known about what people find difficult, and what syntax and language features are especially tricky and bug-prone. Our new research has discovered how people naturally think about algorithms and data structures, which can help with making programming languages more closely match people's problem solving techniques.
Concatenate, reverse and map vanish for free
Authors: Voigtländer Janis
Published: November 2005

We introduce a new transformation method to eliminate intermediate data structures occurring in functional programs due to repeated list concatenations and other data manipulations (additionally exemplified with list reversal and mapping of functions over lists).The general idea is to uniformly abstract from data constructors and manipulating operations by means of rank-2 polymorphic combinators that exploit algebraic properties of these operations to provide an optimized implementation. The correctness of transformations is proved by using the
free theorems
derivable from parametric polymorphic types.
Modular typechecking for hierarchically extensible datatypes and functions
Authors: Millstein Todd , Bleckner Colin , Chambers Craig
Published: November 2005

One promising approach for adding object-oriented (OO) facilities to functional languages like ML is to generalize the existing datatype and function constructs to be hierarchical and extensible, so that datatype variants simulate classes and function cases simulate methods. This approach allows existing datatypes to be easily extended with both new operations and new variants, resolving a long-standing conflict between the functional and OO styles. However, previous designs based on this approach have been forced to give up
modular
typechecking, requiring whole-program checks to ensure type safety. We describe Extensible ML (
eml
), an ML-like language that supports hierarchical, extensible datatypes and functions while preserving purely modular typechecking. To achieve this result,
eml
's type system imposes a few requirements on datatype and function extensibility, but
eml
is still able to express both traditional functional and OO idioms. We have formalized a core version of
eml
and proven the associated type system sound, and we have developed a prototype interpreter for the language.
Composing monads using coproducts
Authors: Lüth Christoph , Ghani Neil
Published: November 2005

Monads are a useful abstraction of computation, as they model diverse computational effects such as stateful computations, exceptions and I/O in a uniform manner. Their potential to provide both a modular semantics and a modular programming style was soon recognised. However, in general, monads proved difficult to compose and so research focused on special mechanisms for their composition such as distributive monads and monad transformers.We present a new approach to this problem which is general in that nearly all monads compose, mathematically elegant in using the standard categorical tools underpinning monads and computationally expressive in supporting a canonical recursion operator. In a nutshell, we propose that two monads should be composed by taking their
coproduct
. Although abstractly this is a simple idea, the actual construction of the coproduct of two monads is non-trivial. We outline this construction, show how to implement the coproduct within Haskell and demonstrate its usage with a few examples. We also discuss its relationship with other ways of combining monads, in particular distributive laws for monads and monad transformers.
Typing dynamic typing
Authors: Baars Arthur I. , Swierstra S. Doaitse
Published: November 2005

Even when programming in a statically typed language we every now and then encounter statically untypable values; such values result from interpreting values or from communicating with the outside world. To cope with this problem most languages include some form of
dynamic
types. It may be that the core language has been explicitly extended with such a type, or that one is allowed to live dangerously by using functions like
unsafeCoerce
. We show how, by a careful use of existentially and universally quantified types, one may achievem the same effect, without extending the language with new or unsafe features. The techniques explained are universally applicable, provided the core language is expressive enough; this is the case for the common implementations of
Haskell
. The techniques are used in the description of a type checking compiler that, starting from an expression term, constructs a typed function representing the semantics of that expression. In this function the overhead associated with the type checking is only once being paid for; in this sense we have thus achieved static type checking.
An expressive, scalable type theory for certified code
Authors: Crary Karl , Vanderwaart Joseph C.
Published: November 2005

We present the type theory LTT, intended to form a basis for typed target languages, providing an internal notion of logical proposition and proof. The inclusion of explicit proofs allows the type system to guarantee properties that would otherwise be incompatible with decidable type checking. LTT also provides linear facilities for tracking ephemeral properties that hold only for certain program states.Our type theory allows for re-use of typechecking software by casting a variety of type systems within a single language. We illustrate our methodology of representation by means of two examples, one functional and one stateful, and describe the associated operational semantics and proofs of type safety.
Meta-programming with names and necessity
Authors: Nanevski Aleksandar
Published: November 2005

Meta-programming languages provide infrastructure to generate and execute object programs at run-time. In a typed setting, they contain a modal type constructor which classifies object code. These code types generally come in two flavors: closed and open. Closed code expressions can be invoked at run-time, but the computations over them are more rigid, and typically produce less efficient residual object programs. Open code provides better inlining and partial evaluation of object programs, but once constructed, expressions of this type cannot in general be evaluated.Recent work in this area has focused on combining the two notions into a sound system. We present a novel way to achieve this. It is based on adding the notion of names from the work on Nominal Logic and FreshML to the λ -calculus of proof terms for the
necessity
fragment of modal logic S4. The resulting language provides a more fine-grained control over free variables of object programs when compared to the existing languages for meta-programming. In addition, this approach lends itself well to addition of intensional code analysis, i.e. ability of meta programs to inspect and destruct object programs at run-time in a type-safe manner, which we also undertake.
Compiling scheme to JVM bytecode:
Authors: Serpette Bernard Paul , Serrano Manuel
Published: November 2005

We have added a Java virtual machine (henceforth JVM) bytecode generator to the optimizing Scheme-to-C compiler Bigloo. We named this new compiler BiglooJVM. We have used this new compiler to evaluate how suitable the JVM bytecode is as a target for compiling strict functional languages such as Scheme. In this paper, we focus on the performance issue. We have measured the execution time of many Scheme programs when compiled to C and when compiled to JVM. We found that for each benchmark, at least one of our hardware platforms ran the BiglooJVM version in less than twice the time taken by the Bigloo version. In order to deliver fast programs the generated JVM bytecode must be carefully crafted in order to benefit from the speedup of just-in-time compilers.
Program generation, termination, and binding-time analysis
Authors: Jones Neil D. , Glenstrup Arne J.
Published: November 2005

Recent research suggests that the goal of fully automatic and reliable program generation for a broad range of applications is coming nearer to feasibility. However, several interesting and challenging problems remain to be solved before it becomes a reality.We first discuss the relations between problem specifications and their solutions in program form, and then narrow the discussion to an important special case: program transformation. Although the goal of fully automatic program generation is still far from fully achieved, there has been some success in a special case: partial evaluation, also known as program specialization.A key problem in all program generation is
termination of the generation process
. This paper (See the GPCE'02 proceedings for the full paper.} describes recent progress towards automatically solving the termination problem, first for individual programs, and then for specializers and "generating extensions," the program generators that most offline partial evaluators produce.
A constraint-based architecture for local search
Authors: Michel Laurent , Hentenryck Pascal Van
Published: November 2005

Combinatorial optimization problems are ubiquitous in numerous practical applications. Yet most of them are challenging, both from computational complexity and programming standpoints. Local search is one of the main approaches to address these problems. However, it often requires sophisticated incremental algorithms and data structures, and considerable experimentation. This paper proposes a constraint-based, object-oriented, architecture to reduce the development time of local search algorithms significantly. The architecture consists of declarative and search components. The declarative component includes
invariants
, which maintain complex expressions incrementally, and
differentiable objects
, which maintain properties that can be queried to evaluate the effect of local moves. Differentiable objects are high-level modeling concepts, such as constraints and functions, that capture combinatorial substructures arising in many applications. The search component supports various abstractions to specify heuristics and meta-heuristics. We illustrate the architecture with the language
Comet
and several applications, such as car sequencing and the progressive party problem. The applications indicate that the architecture allows for very high-level modeling of local search algorithms, while preserving excellent performance.
Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching
Authors: Zibin Yoav , Gil Joseph Yossi
Published: November 2005

The dispatching problem can be solved very efficiently in the single-inheritance~(SI) setting. In this paper we show how to extend one such solution to the multiple-inheritance~(MI) setting. This generalization comes with an increase to the space requirement by a small factor of κ This factor can be thought of as a metric of the complexity of the topology of the inheritance hierarchy.On a data set of~35 hierarchies totaling some~64 thousand types, our dispatching data structure, based on a novel
type slicing
technique, exhibits very significant improvements over previous dispatching techniques, not only in terms of the time for creating the underlying data structure, but also in terms of total space used.The cost is in the dispatching time, which is no longer constant, but doubly logarithmic in the number of types. Conversely, by using a simple binary search, dispatching time is logarithmic in the number of different implementations. In practice dispatching uses one indirect branch and, on average, only~2.5 binary branches.Our results also have applications to the space-efficient implementation of the more general problem of dispatching multi-methods.A by-product of our type slicing technique is an
incremental
algorithm for constant-time
subtyping tests
with favorable memory requirements. (The incremental version of the subtyping problem is to maintain the subtyping data structure in presence of additions of types to the inheritance hierarchy.)
Design pattern implementation in Java and aspectJ
Authors: Hannemann Jan , Kiczales Gregor
Published: November 2005

AspectJ implementations of the GoF design patterns show modularity improvements in 17 of 23 cases. These improvements are manifested in terms of better code locality, reusability, composability, and (un)pluggability.The degree of improvement in implementation modularity varies, with the greatest improvement coming when the pattern solution structure involves crosscutting of some form, including one object playing multiple roles, many objects playing one role, or an object playing roles in multiple pattern instances.
Write barrier removal by static analysis
Authors: Zee Karen , Rinard Martin
Published: November 2005

We present a new analysis for removing unnecessary write barriers in programs that use generational garbage collection. To our knowledge, this is the first static program analysis for this purpose. Our algorithm uses a pointer analysis to locate assignments that always create a reference from a younger object to an older object, then transforms the program to remove the write barriers normally associated with such assignments. We have implemented two transformations that reorder object allocations; these transformations can significantly increase the effectiveness of our write barrier removal algorithm.Our base technique assumes that the collector promotes objects in age order. We have developed an extension that enables the optimistic removal of write barriers, with the collector lazily adding each newly promoted object into a remembered set of objects whenever the compiler may have removed write barriers involving the object at statements that have yet to execute. This mechanism enables the application of our technique to virtually any memory management system that uses write barriers to enable generational garbage collection.Results from our implemented system show that our technique can remove substantial numbers of write barriers from the majority of the programs in our benchmark set, producing modest performance improvements of up to 6% of the overall execution time. Moreover, by dynamically instrumenting the executable, we are able to show that for six of our nine benchmark programs, our analysis is close to optimal in the sense that it removes the write barriers for almost all assignments that do not, in the observed execution, create a reference from an older object to a younger object. Finally, our results show that the overhead of our optimistic extension is negligible.
Incommunicado
Authors: Palacz Krzysztof , Vitek Jan , Czajkowski Grzegorz , Daynès Laurent
Published: November 2005

Executing computations in a single instance of safe language virtual machine can improve performance and overall platform scalability. It also poses various challenges. One of them is providing a fast inter-application communication mechanism. In addition to being efficient, such a mechanism should not violate any functional and non-functional properties of its environment, and should also support enforcement of application-specific security policies. This paper explores the design and implementation of a communication substrate for applications executing within a single Java virtual machine modified to enable safe and interference-free execution of isolated computations. Designing an efficient extension that does not break isolation properties and at the same time pragmatically offers an intuitive API has proven non-trivial. This paper demonstrates a set of techniques that lead to at least an eight-fold performance improvement over the in-process inter-application communication using standard mechanisms offered by the Java platform.
Representing change by aspect
Authors: Dolog Peter , Vranić Valentino , Bieliková Mária
Published: November 2005

We propose the application of aspectoriented programming to software configuration management. We believe it could improve the change control by providing a new basis for reasoning about a change. To demonstrate this, we designed an abstract-oriented extension to procedural languages where a change is represented by an aspect. Consequently, a change gains the properties of an aspect: it becomes well-localized and separated from the (unchanged) base program. This goes beyond the current capabilities of configuration management methods and tools: the aspect representing the change can be applied to other versions of the program (possibly to different programs).
Bytecode fetch optimization for a Java interpreter
Authors: Ogata Kazunori , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

Interpreters play an important role in many languages, and their performance is critical particularly for the popular language Java. The performance of the interpreter is important even for high-performance virtual machines that employ just-in-time compiler technology, because there are advantages in delaying the start of compilation and in reducing the number of the target methods to be compiled. Many techniques have been proposed to improve the performance of various interpreters, but none of them has fully addressed the issues of minimizing redundant memory accesses and the overhead of indirect branches inherent to interpreters running on superscalar processors. These issues are especially serious for Java because each bytecode is typically one or a few bytes long and the execution routine for each bytecode is also short due to the low-level, stack-based semantics of Java bytecode. In this paper, we describe three novel techniques of our Java bytecode interpreter,
write-through top-of-stack caching (WT), position-based handler customization (PHC), and position-based speculative decoding (PSD),
which ameliorate these problems for the PowerPC processors. We show how each technique contributes to improving the overall performance of the interpreter for major Java benchmark programs on an IBM POWER3 processor. Among three, PHC is the most effective one. We also show that the main source of memory accesses is due to bytecode fetches and that PHC successfully eliminates the majority of them, while it keeps the instruction cache miss ratios small.
Understanding and improving operating system effects in control flow prediction
Authors: Li Tao , John Lizy Kurian , Sivasubramaniam Anand , Vijaykrishnan N. , Rubio Juan
Published: November 2005

Many modern applications result in a significant operating system (OS) component. The OS component has several implications including affecting the control flow transfer in the execution environment. This paper focuses on understanding the operating system effects on control flow transfer and prediction, and designing architectural support to alleviate the bottlenecks. We characterize the control flow transfer of several emerging applications on a commercial operating system. We find that the exception-driven, intermittent invocation of OS code and the user/OS branch history interference increase the misprediction in both user and kernel code.We propose two simple OS-aware control flow prediction techniques to alleviate the destructive impact of user/OS branch interference. The first one consists of capturing separate branch correlation information for user and kernel code. The second one involves using separate branch prediction tables for user and kernel code. We study the improvement contributed by the OS-aware prediction to various branch predictors ranging from simple Gshare to more elegant Agree, Multi-Hybrid and Bi-Mode predictors. On 32K entries predictors, incorporating OS-aware techniques yields up to 34%, 23%, 27% and 9% prediction accuracy improvement in Gshare, Multi-Hybrid, Agree and Bi-Mode predictors, resulting in up to 8% execution speedup.
Integration of the Standard Template Library and the Microsoft Foundation Class
Authors: Wolfgang Paul , Song Yang
Published: November 2005

A short example of a Windows® application is modified to use the generic containers, iterators, and function adapters of the C++ Standard Template Library. Comparison is made with the containers and iteration mechanism provided by the Microsoft Foundation Classes.
C++ toolbox
Authors: Gluche Dieter , Kühl Dietmar , Weihe Karsten
Published: November 2005

In this article, we will discuss a flexible, convenient implementation scheme for interactive evaluations of tabular information. In this scheme, an iterator represents the result of a query. This iterator is constructed from a couple of polymolrphic building blocks, which correspond to the basic features of the query language.
Definition of open language
Authors: Sunik Boris
Published: November 2005

Open languages are the new class of formal languages proposed by the author. A language of this class combines the grammar of an object-oriented programming language with the universality of a natural language. The open language allows the creation of a monolingual communication environment where it can be used in a wide range of communication processes requiring explicit information, i.e. programming, documenting of software and hardware, specification of various standards, tasks' setting, presentation of various kinds of knowledge, etc.
Using smgn for rapid protoptyping of small domain-specific languages
Authors: Kienle Holger M.
Published: November 2005

This paper presents smgn, a grammar-based tool that provides support for scanning, parsing, and automatic parse tree construction. The parse tree can be easily navigated and manipulated with a specific macro language while conveniently generating textual output. smgn is easy to learn and well suited for rapid prototyping of small domain-specific languages. It is part of the SUIF compiler system, where it has been used for the rapid development of the
Hoof
domain-specific language. Furthermore, smgn was recently employed for the rapid development of another domain-specific language, called Bauhaus IMDL. These successful experiences motivate the promotion of smgn in the hope that other researchers that face the task of implementing a domain-specific language will find smgn equally helpful.
Transportable applications environment (TAE) plus experiences in “Object”-ively modernizing a user interface environment
Authors: Szczur Martha R. , Miller Philip
Published: November 2005

This paper describes the evolution of the Transportable Applications Executive (TAE) (developed at NASA/Goddard Space Flight Center) from a traditional procedural menu and command-oriented system to an object-oriented, modeless user interface management system, known as TAE Plus. The impetus for developing this environment and early experiments which led to its current implementation are addressed. The current version of TAE Plus provides design and prototyping functions, working in tandem with a mature application management system. The main components are (1) a user interface designers' WorkBench that allows an application developer to interactively layout an application screen and define the static and/or dynamic areas of the screen; (2) an application programmer subroutine package that provides runtime services used to display and control WorkBench-designed “interaction objects” on the screen; and (3) an extension to the existing TAE command language that provides commands for displaying and manipulating interaction objects, thus providing a means to quickly prototype an application's user interface. During TAE Plus development, many design and implementation decisions were based on the state-of-the-art within graphics workstations, windowing systems and object-oriented programming languages, and this paper shares some of the problems and issues experienced during implementation. Some of the topics discussed include: lessons learned in using the Smalltalk™ language to prototype the initial WorkBench; why C++ was selected (over other languages) to build the WorkBench; and experiences in using X Window System™ and Stanford's InterViews object library. The paper concludes with open issues and a description of the next steps involved in implementing the “totally modern” TAE.
AVANCE: an object management system
Authors: Bjornerstedt Anders , Britts Stefan
Published: November 2005

AVANCE
1
is an integrated application development and run-time system. It provides facilities for programming with shared and persistent objects, transactions and processes. The architecture is designed with decentralization in mind by having a large object identifier space and a remote procedure call interface to objects. Emphasis in this paper is on the programming language PAL and its relation with the underlying virtual machine.
A smalltalk implementation of an intelligent operator's associate
Authors: Rubin Kenneth S. , Jones Patricia M. , Mitchell Christine M. , Goldstein Theodore C.
Published: November 2005

This paper describes the use of Smalltalk in the design and implementation of OFMspert. OFMspert is an architecture for an intelligent operator's associate. In order to verify the architecture, an OFMspert was implemented to act as an assistant to an operator of a NASA satellite ground control system. OFMspert is a large system that utilizes a Smalltalk implementation of a knowledge-based problem solving method known as the blackboard architecture. The entire system was designed and implemented in Smalltalk/V™ and later ported to the Smalltalk-80™ system. The object-oriented paradigm in general, and Smalltalk‡ in particular, greatly facilitated the rapid design and implementation of this system. This paper summarizes the OFMspert architecture, emphasizing its implementation in an object-oriented paradigm.
Data abstraction mechanisms in SINA/ST
Authors: Aksit Mehmet , Tripathi Anand
Published: November 2005

This paper describes a new data abstraction mechanism in an object-oriented model of computing. The data abstraction mechanism described here has been devised in the context of the design of Sina/st language. In Sina/st no language constructs have been adopted for specifying inheritance or delegation, but rather, we introduce simpler mechanisms that can support a wide range of code sharing strategies without selecting one among them as a language feature. Sina/st also provides a stronger data encapsulation than most of the existing object-oriented languages. This language has been implemented on the SUN 3 workstation using Smalltalk.
On the implementation of applicative languages on shared-memory, MIMD multiproce
Authors: Lee Ching-Cheng , Skedzielewski Stephen , Feo John
Published: November 2005

This paper presents the performance of a set of algorithms written in SISAL [MSA
*
85] and run on multiprocessor Sequent, DEC, and Cray computers. We describe our current runtime system and discuss its implementation on each machine. We indicate where our automatic approach to parallelization works well, as well as sources of inefficient behavior. Overall we find our systems encouraging for the first release of the native-code generating software. We suggest improvements to the compiler and runtime systems, many already developed but not yet implemented, to alleviate the inefficiencies.
Testing monadic code with QuickCheck
Authors: Claessen Koen , Hughes John
Published: November 2005

QuickCheck is a previously published random testing tool for Haskell programs. In this paper we show how to use it for testing monadic code, and in particular imperative code written using the
ST
monad. QuickCheck tests a program against a specification: we show that QuickCheck's specification language is sufficiently powerful to represent common forms of specifications: algebraic, model-based (both functional and relational), and pre-/post-conditional. Moreover, all these forms of specification can be used directly for testing. We define a new language of monadic properties, and make a link between program testing and the notion of observational equivalence.
Pattern-matching and rewriting rules for group indexed data structures
Authors: Giavitto Jean-Louis , Michel Olivier , Cohen Julien
Published: November 2005

In this paper, we present a new framework for the definition of various data structures (including trees and arrays) together with a generic language of filters enabling a rule-based programming style for functions. This framework is implemented in an experimental language called MGS. The underlying notions funding our framework have a topological nature and enable to extend the case-based definition of functions found in modern functional languages beyond algebraic data structures.
Bigraphs and transitions
Authors: Jensen Ole Høgh , Milner Robin
Published: November 2005

A bigraphical reactive system (BRS) involves
bigraphs
, in which the nesting of nodes represents locality, independently of the edges connecting them. BRSs represent a wide variety of calculi for mobility, including λ-calculus and ambient calculus. A labelled transition system (LTS) for each BRS is here derived uniformly, adapting previous work of Leifer and Milner, so that under certain conditions the resulting bisimilarity is automatically a congruence. For an asynchronous λ-calculus, this LTS and its bisimilarity agree closely with the standard.
The m-calculus
Authors: Schmitt Alan , Stefani Jean-Bernard
Published: November 2005

This paper presents a new distributed process calculus, called the M-calculus, that can be understood as a higher-order version of the Distributed Join calculus with programmable localities. The calculus retains the implementable character of the Distributed Join calculus while overcoming several important limitations: insufficient control over communication and mobility, absence of dynamic binding, and limited locality semantics. The calculus is equipped with a polymorphic type system that guarantees the unicity of locality names, even in presence of higher-order communications -- a crucial property for the determinacy of message routing in the calculus.
Discovering affine equalities using random interpretation
Authors: Gulwani Sumit , Necula George C.
Published: November 2005

We present a new polynomial-time randomized algorithm for discovering affine equalities involving variables in a program. The key idea of the algorithm is to execute a code fragment on a few random inputs, but in such a way that all paths are covered on each run. This makes it possible to rule out invalid relationships even with very few runs.The algorithm is based on two main techniques. First, both branches of a conditional are executed on each run and at joint points we perform an affine combination of the joining states. Secondly, in the branches of an equality conditional we adjust the data values on the fly to reflect the truth value of the guarding boolean expression. This increases the number of affine equalities that the analysis discovers.The algorithm is simpler to implement than alternative deterministic versions, has better computational complexity, and has an extremely small probability of error for even a small number of runs. This algorithm is an example of how randomization can provide a trade-off between the cost and complexity of program analysis, and a small probability of unsoundness.
Toward a foundational typed assembly language
Authors: Crary Karl
Published: November 2005

We present the design of a typed assembly language called TALT that supports heterogeneous tuples, disjoint sums, and a general account of addressing modes. TALT also implements the von Neumann model in which programs are stored in memory, and supports relative addressing. Type safety for execution and for garbage collection are shown by machine-checkable proofs. TALT is the first formalized typed assembly language to provide any of these features.
Guarded recursive datatype constructors
Authors: Xi Hongwei , Chen Chiyan , Chen Gang
Published: November 2005

We introduce a notion of guarded recursive (g.r.) datatype constructors, generalizing the notion of recursive datatypes in functional programming languages such as ML and Haskell. We address both theoretical and practical issues resulted from this generalization. On one hand, we design a type system to formalize the notion of g.r. datatype constructors and then prove the soundness of the type system. On the other hand, we present some significant applications (e.g., implementing objects, implementing staged computation, etc.) of g.r. datatype constructors, arguing that g.r. datatype constructors can have far-reaching consequences in programming. The main contribution of the paper lies in the recognition and then the formalization of a programming notion that is of both theoretical interest and practical use.