bluuebunny/crossref_metadata_2025 huggingface dataset:
Optimizing for reduced code space using genetic algorithms
Authors: Cooper Keith D. , Schielke Philip J. , Subramanian Devika
Published: November 2005

Code space is a critical issue facing designers of software for embedded systems. Many traditional compiler optimizations are designed to reduce the execution time of compiled code, but not necessarily the size of the compiled code. Further, different results can be achieved by running some optimizations more than once and changing the order in which optimizations are applied. Register allocation only complicates matters, as the interactions between different optimizations can cause more spill code to be generated. The compiler for embedded systems, then, must take care to use the best sequence of optimizations to minimize code space.Since much of the code for embedded systems is compiled once and then burned into ROM, the software designer will often tolerate much longer compile times in the hope of reducing the size of the compiled code. We take advantage of this by using a genetic algorithm to find optimization sequences that generate small object codes. The solutions generated by this algorithm are compared to solutions found using a fixed optimization sequence and solutions found by testing random optimization sequences. Based on the results found by the genetic algorithm, a new fixed sequence is developed to reduce code size. Finally, we explore the idea of using different optimization sequences for different modules and functions of the same program.
From fast exponentiation to square matrices
Authors: Okasaki Chris
Published: November 2005

Square matrices serve as an interesting case study in functional programming. Common representations, such as lists of lists, are both inefficient---at least for access to individual elements---and error-prone, because the compiler cannot enforce "squareness". Switching to a typical balanced-tree representation solves the first problem, but not the second. We develop a representation that solves both problems: it offers logarithmic access to each individual element and it captures the shape invariants in the type, where they can be checked by the compiler. One interesting feature of our solution is that it translates the well-known fast exponentiation algorithm
to the level of types
. Our implementation also provides a stress test for today's advanced type systems---it uses nested types, polymorphic recursion, higher-order kinds, and rank-2 polymorphism.
Detecting defects in object-oriented designs
Authors: Travassos Guilherme , Shull Forrest , Fredericks Michael , Basili Victor R.
Published: November 2005

Inspections can be used to identify defects in software artifacts. In this way, inspection methods help to improve software quality, especially when used early in software development. Inspections of software design may be especially crucial since design defects (problems of correctness and completeness with respect to the requirements, internal consistency, or other quality attributes) can directly affect the quality of, and effort required for, the implementation.

We have created a set of “reading techniques” (so called because they help a reviewer to “read” a design artifact for the purpose of finding relevant information) that gives specific and practical guidance for identifying defects in Object-Oriented designs. Each reading technique in the family focuses the reviewer on some aspect of the design, with the goal that an inspection team applying the entire family should achieve a high degree of coverage of the design defects.

In this paper, we present an overview of this new set of reading techniques. We discuss how some elements of these techniques are based on empirical results concerning an analogous set of reading techniques that supports defect detection in requirements documents. We present an initial empirical study that was run to assess the feasibility of these new techniques, and discuss the changes made to the latest version of the techniques based on the results of this study.
A problem-oriented analysis of basic UML static requirements modeling concepts
Authors: France Robert
Published: November 2005

The
Unified Modeling Language
(UML) is a standard modeling language in which some of the best object-oriented (OO) modeling experiences are embedded. In this paper we illustrate the role formal specification techniques can play in developing a precise semantics for the UML. We present a precise characterization of requirements-level (problem-oriented) Class Diagrams and outline how the characterization can be used to semantically analyze requirements Class Diagrams.
Modular type-based reverse engineering of parameterized types in Java code
Authors: Duggan Dominic
Published: November 2005

An analysis is provided for Java programs that reverse engineers parameterized types into existing Java code. This analysis propagates precise type information about the contents of container objects. As an application, the analysis can be used to justify the safe removal of downcasts that are guaranteed to succeed. Another application is in automatically reverse engineering parameterized types into existing Java libraries, so that they can be used in Java dialects with parameterized types.
Efficient multiple and predicated dispatching
Authors: Chambers Craig , Chen Weimin
Published: November 2005

The speed of message dispatching is an important issue in the overall performance of object-oriented programs. We have developed an algorithm for constructing efficient dispatch functions that combines novel algorithms for efficient single dispatching, multiple dispatching, and predicate dispatching. Our algorithm first reduces methods written in the general predicate dispatching model (which generalizes single dispatching, multiple dispatching, predicate classes and classifiers, and pattern-matching) into ones written using a simpler multimethod dispatching model. Our algorithm then computes a strategy for implementing multiple dispatching in terms of sequences of single dispatches, representing the strategy as a
lookup DAG
. Finally, our algorithm computes an implementation strategy separately for each of the single dispatches, producing for each dispatch a
dispatch tree
, which is a binary decision tree blending class identity tests, class range tests, and table lookups. Our algorithm exploits any available static information (from type declarations or class analysis) to prune unreachable paths from the lookup DAG, and uses any available dynamic profile information to minimize the expected time to search the dispatch trees. We measure the effectiveness of our dispatching algorithms on a collection of large Cecil programs, compiled by the Vortex optimizing compiler, showing improvements of up to 30% over already heavily optimized baseline versions.
Age-based garbage collection
Authors: Stefanović Darko , McKinley Kathryn S. , Moss J. Eliot B.
Published: November 2005

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, called
age-based
, some of which postpone consideration of the youngest objects. Collecting less than the whole heap requires
write barrier
mechanisms to track pointers into the collected region. We describe here a new, efficient write barrier implementation that works for age-based and traditional generational collectors. To compare several collectors, their configurations, and program behavior, we use an accurate simulator that models all heap objects and the pointers among them, but does not model cache or other memory effects. For object-oriented languages, our results demonstrate that an
older-first
collector, which collects older objects before the youngest ones, copies on average much less data than generational collectors. Our results also show that an older-first collector does track more pointers, but the combined cost of copying and pointer tracking still favors an older-first over a generational collector in many cases. More importantly, we reopen for consideration the question where in the heap and with which policies copying collectors will achieve their best performance.
PCOL - A protocol-constrained object language
Authors: van der Bos Jan
Published: November 2005

Object languages present a flexible tool for programming. They facilitate the encapsulation of datastructures and procedures. Objects also offer a natural construct for parallel programming. Each object could run as a separate process on its own processor. The weak point of object languages is the communication between objects. The burden is on the programmer to carefully use the communication facilities in order to prevent undisciplined and often erroneous specifications. PCOL, is an object language in which the communication may optionally be subjected to a protocol. If present, this protocol takes the form of a specification of occurrence and sequencing of the interaction between the object and its communication partners. The use of protocols in object communication leads to safer and potentially verifiable information exchange between objects.
XC- A language for embedded rule based systems
Authors: Nuutila E. , Kuusela J. , Tamminen M. , Veilhti J. , Arkko J.
Published: November 2005

We report on experiences in the design of the programming language XC. It is an extension of C++ and combines abstract data types with rule based programming. Our design decisions are validated by three application prototypes and by benchmarking XC and OPS83. The experiences raise some critique on the RETE algorithm and on C++ as a host language. However, most of the results are also applicable to other host languages that support data abstraction. XC has been designed specifically to be used in embedded real-time expert systems.
Symbolic pointer analysis for detecting memory leaks
Authors: Scholz Berhard , Blieberger Johann , Fahringer Thomas
Published: November 2005

It is well accepted that pointers are a common source of memory anomalies such as loosing references to dynamic records without deallocating them (also known as memory leaks). This paper presents a novel pointer analysis framework that detects memory leaks by statically analyzing the behavior of programs.

Our approach is based on symbolic evaluation of programs. Symbolic evaluation is an advanced static symbolic analysis that is centered around symbolic variable values, assumptions about and constraints between variable values, and control flow information (path conditions). As part of symbolic evaluation we introduce a new symbolic heap algebra for modeling heap operations. Predicates — defined over the program's input — are derived which allow to detect memory leaks. Our approach goes beyond previous work in the field of statically detecting memory leaks by considering also path conditions which increases the accuracy of our results, symbolically modeling heap data structures and heap operations. Examples are used to illustrate the effectiveness of our approach.
Calculating sized types
Authors: Chin Wei-Ngan , Khoo Siau-Cheng
Published: November 2005

Many program optimisations and analyses, such as array-bound checking, termination analysis, etc, depend on knowing the size of a function's input and output. However, size information can be difficult to compute. Firstly, accurate size computation requires detecting
size relation
between different inputs of a function. Secondly, different optimisations and analyses may require slightly different size information, and thus slightly different computation. Literature in size computation has mainly concentrated on size checking, instead of inferencing. In this paper, we provide a generic framework on which different size variants can be expressed and computed. We also describe an effective algorithm for
inferring
, instead of checking, size information. Size information are expressed in terms of Presburger formulae, and our algorithm utilises the Omega Calculator to compute as exact a size information as possible, within the linear arithmetic capability.
An evaluation of computing paradigms for N-body simulations on distributed memory architectures
Authors: McCurdy Collin , Mellor-Crummey John
Published: November 2005

The efficiency of HPF with respect to irregular applications is still largely unproven. While recent work has shown that a highly irregular hierarchical n-body force calculation method
can
be implemented in HPF, we have found that the implmentation contains inefficiencies which cause it to run up to a factor of three times slower than our hand-coded, explicitly parallel implementation. Our work examines these inefficiencies, determines that most of the extra overhead is due to a single aspect of the communication strategy, and demonstrates that fixing the communication strategy can bring the overheads of the HPF application to within 25% of those of the hand-coded version.
Transparent adaptive parallelism on NOWs using OpenMP
Authors: Scherer Alex , Lu Honghui , Gross Thomas , Zwaenepoel Willy
Published: November 2005

We present a system that allows OpenMP programs to execute on a network of workstations with a variable number of nodes. The ability to adapt to a variable number of nodes allows a program to take advantage of additional nodes that become available after it starts execution, or to gracefully scale down when the number of available nodes is reduced. We demonstrate that the cost of adaptation is modest; the system allows a program to adapt at a moderate rate without much performance loss.Two ideas underlie the efficiency of our design. First, we recognize that OpenMP programs exhibit convenient
adaptation points
during their execution, points at which the cost of adaptation can be much reduced. Second, by allowing a process a certain
grace period
before it must leave a node, we insure that most adaptations can occur at these adaptation points, and thus at low cost. Migration of a process, a much more expensive method for providing adaptivity, is used only as a back-up solution, when the process cannot reach an adaptation point within the grace period.Our implementation consists of an OpenMP pre-processor that generates TreadMarks distributed shared memory (DSM) programs, and a version of TreadMarks modified to adapt to a variable number of nodes. Using a DSM as the underlying substrate facilitates the data (re-)distribution necessary after an adaptation.
An annotation language for optimizing software libraries
Authors: Guyer Samuel Z. , Lin Calvin
Published: November 2005

This paper introduces an annotation language and a compiler that together can customize a library implementation for specific application needs. Our approach is distinguished by its ability to exploit high level, domain-specific information in the customization process. In particular, the annotations provide semantic information that enables our compiler to analyze and optimize library operations as if they were primitives of a domain-specific language. Thus, our approach yields many of the performance benefits of domain-specific languages, without the effort of developing a new compiler for each domain.

This paper presents the annotation language, describes its role in optimization, and illustrates the benefits of the overall approach. Using a partially implemented compiler, we show how our system can significantly improve the performance of two applications written using the PLAPACK parallel linear algebra library.
Monadic robotics
Authors: Peterson John , Hager Greg
Published: November 2005

We have developed a domain specific language for the construction of robot controllers, Frob (Functional ROBotics). The semantic basis for Frob is Functional Reactive Programming, or simply FRP, a purely functional model of continuous time, interactive systems. FRP is built around two basic abstractions: behaviors, values defined continuously in time, and events, discrete occurances in time. On this foundation, we have constructed abstractions specific to the domain of robotics. Frob adds yet another abstraction: the
task,
a basic unit of work defined by a continuous behavior and a terminating event.

This paper examines two interrelated aspects of Frob. First, we study the design of systems based on FRP and how abstractions defined using FRP can capture essential domain-specific concepts for systems involving interaction over time. Second, we demonstrate an application of
monads,
used here to implement Frob tasks. By placing our task abstraction in a monadic framework, we are able to organize task semantics in a modular way, allowing new capabilities to be added without pervasive changes to the system.

We present several robot control algorithms specified using Frob. These programs are clear, succinct, and modular, demonstrating the power of our approach.
A collaboration specification language
Authors: Li Du , Muntz Richard R.
Published: November 2005

COCA (Collaborative Objects Coordination Architecture) was proposed as a novel means to model and support collaborations over the Internet. Our approach separates coordination policies from user interfaces and the policies are specified in a logic-based language. Over the past year, both the collaboration model and the specification language have been substantially refined and evaluated through our experience in building real-life collaboration systems. This paper presents the design of the specification language and illustrates the main ideas with a few simple design examples. Semantics, implementation, runtime support, and applications are also covered but not as the focus of this paper.
A comparison of real-time object-oriented modeling methods ROOM and OCTOPUS
Authors: Dai Guilan , Xu Baowen
Published: November 2005

ROOM and OCTOPUS are two real-time object-oriented modeling methods used commonly. The paper analyses and compares ROOM and OCTOPUS based on details where philosophies of both methods are in sharper contrast, such as model representation, class and object and inheritance, concurrency, and state charts.
An object oriented approach to constructing recursive descent parsers
Authors: Davis Matthew S.
Published: November 2005

We discuss a technique to construct a recursive descent parser for a context free language using concepts found in object oriented design and implementation. A motivation for the technique is given. The technique is then introduced with snippets of a Smalltalk implementation. Some advantages and disadvantages of the technique are examined. Finally some areas of possible future work are discussed.
Adapters and binders
Authors: Simonis Volker
Published: November 2005

The Standard Template Library [Lee-Step], [SGI-STL], had the reputation of being complex and hard to use. Because of its exhaustive use of the new C++ language features, most compilers weren't able to fully support this library. Nowadays, new compilers and the standardisation of C++ [ANSI-CPP] not only enable us to use the STL in its full strength, but also show us the drawbacks of a library which apparently was designed from scratch without the possibility of testing and using it. This paper will focus on the syntax and semantics of STL Adaptors and Binders. It will reveal some shortcomings in their C++ implementation and suggest solutions for the encountered problems.
Object-oriented programming with induction
Authors: Swen Bing
Published: November 2005

Object systems employing inheritance exclusively can suffer various difficulties when mapping real world object relations. This paper presents induction, as a universal software engineering methodology, to complement inheritance. We found out that a special form of induction, called virtual induction, is a powerful mechanism for abstracting and reusing existing code and can be well blended with inheritance. A C++ implementation of the mechanism is also discussed.
Ranking the complexity of NIAM conceptual schemas by alpha metric
Authors: Kokol Peter , Podgorelec Vili
Published: November 2005

The general aim of formal methods to program development is to provide correctness of the problem specification and then to transform that specification into a working program. Often a formal specification is expressed using the NIAM conceptual schema. If we consider only valid types of constraints and if we keep all the consistent schemas, we have 28 possible schemas and 7 sub -- schemas for each schema. The schemas and sub - schemas have very different complexities and there exists an intuitive order of these complexities which seems to be problematical. The aim of this paper is to verify this order using a complexity measure called α (information content/entropy metrics) and to define a new ranking functions generating more correct order.
An intelligent neural network programming system (NNPS)
Authors: Li Tao , Liu XiaoJie
Published: November 2005

A neural network programming system based on parallel neural information processing has been presented. With the neural network programming system built upon a 100M local computer network, the system has thus provided users high speed, general purpose and large scale neural network application development platforms.
Effective parameterization of architectural registers for register allocation algorithms
Authors: Srikant Y. N. , Ravindra D. V.
Published: November 2005

Code Selection in translation has been effectively abstracted out in terms of tree rewriting or pattern matching based approaches. However, modelling register files in an architecture independent way is a problem which is bypassed in most available algorithms. Architectural parameterization is frequently just code selector generation while architectural registers and operand constraints are handled in a machine-specific way. To partially address this issue, we present an abstraction for register allocation and assignment in non-uniform register file architectures in terms of bipartite graph matching.
Adaptive optimization in the Jalapeño JVM
Authors: Arnold Matthew , Fink Stephen , Grove David , Hind Michael , Sweeney Peter F.
Published: November 2005

Future high-performance virtual machines will improve performance through sophisticated online feedback-directed optimizations. this paper presents the architecture of the Jalapeño Adaptive Optimization System, a system to support leading-edge virtual machine technology and enable ongoing research on online feedback-directed optimizations. We describe the extensible system architecture, based on a federation of threads with asynchronous communication. We present an implementation of the general architecture that supports adaptive multi-level optimization based purely on statistical sampling. We empirically demonstrate that this profiling technique has low overhead and can improve startup and steady-state performance, even without the presence of online feedback-directed optimizations. The paper also describes and evaluates an online feedback-directed inlining optimization based on statistical edge sampling. The system is written completely in Java, applying the described techniques not only to application code and standard libraries, but also to the virtual machine itself.
PIROL
Authors: Herrmann Stephan , Mezini Mira
Published: November 2005

In this paper, we present our experience with applying multidimensional separation of concerns to a software engineering environment. By comparing two different designs of our system, we show the importance of separating integration issues from the implementation of the individual concerns. We present a model in which integration issues are encapsulated into rst--class connector objects and indicate how this facilitates the understandability, maintenance and evolution of the system. We identify issues of binding time, binding granularity and binding cardinality as important criteria in selecting an appropriate model for separation of concerns. We finally show how a good choice following these criteria and considering the requirements of software engineering environments leads to a system with dynamic configurability, high--level component integration and support for multiple instantiable views.
Towards agent-oriented assistance for framework instantiation
Authors: Ortigosa Alvaro , Campo Marcelo , Moriyón Roberto
Published: November 2005

In this work we present a tool for assisting object-oriented framework instantiation based on Intelligent Agent technology. Differently from other approaches, the user is able to select the functionality needed for the new application, and based on this selection an agent elaborates a sequence of programming activities that should be carried out in order to implement it. In addition, the agent guides the execution of the activities according to the framework design. To enable this behavior, the framework need to be documented following the
SmartBooks
method, which extends traditional framework documentation with instantiation rules. In this paper we present an example of an instantiation environment built based on these ideas and the main characteristics of the
SmartBooks
method for documenting frameworks through instantiation knowledge rules.
A study of devirtualization techniques for a Java Just-In-Time compiler
Authors: Ishizaki Kazuaki , Kawahito Motohiro , Yasue Toshiaki , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

Many devirtualization techniques have been proposed to reduce the runtime overhead of dynamic method calls for various object-oriented languages, however, most of them are less effective or cannot be applied for Java in a straightforward manner. This is partly because Java is a statically-typed language and thus transforming a dynamic call to a static one does not make a tangible performance gain (owing to the low overhead of accessing the method table) unless it is inlined, and partly because the dynamic class loading feature of Java prohibits the whole program analysis and optimizations from being applied.We propose a new technique called
direct devirtualization with the code patching mechanism
. For a given dynamic call site, our compiler first determines whether the call can be devirtualized, by analyzing the current class hierarchy. When the call is devirtualizable and the target method is suitably sized, the compiler generates the inlined code of the method, together with the backup code of making the dynamic call. Only the inlined code is actually executed until our assumption about the devirtualization becomes invalidated, at which time the compiler performs code patching to make the backup code executed subsequently. Since the new technique prevents some code motions across the merge point between the inlined code and the backup code, we have furthermore implemented recently-known analysis techniques, such as type analysis and preexistence analysis, which allow the backup code to be completely eliminated. We made various experiments using 16 real programs to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time (JIT) compiler. In summary, we reduced the number of dynamic calls by ranging from 8.9% to 97.3% (the average of 40.2%), and we improved the execution performance by ranging from -1% to 133% (with the geometric mean of 16%).
Implementing separate compilations in Pascal
Authors: Nani G.
Published: November 2005

PIC (Pascal Interface Controller) is a tool for the development of large, modular software systems in Pascal. The new kind of modularity, implemented by PIC, is analyzed in the paper. Two different versions of PIC have been developed, to interface with Pascal compilers providing different support to program decomposition into compilation units.
Architecture and design of AlphaServer GS320
Authors: Gharachorloo Kourosh , Sharma Madhu , Steely Simon , Van Doren Stephen
Published: November 2005

This paper describes the architecture and implementation of the AlphaServer GS320, a cache-coherent non-uniform memory access multiprocessor developed at Compaq. The AlphaServer GS320 architecture is specifically targeted at medium-scale multiprocessing with 32 to 64 processors. Each node in the design consists of four Alpha 21264 processors, up to 32GB of coherent memory, and an aggressive IO subsystem. The current implementation supports up to 8 such nodes for a total of 32 processors. While snoopy-based designs have been stretched to medium-scale multiprocessors by some vendors, providing sufficient snoop bandwidth remains a major challenge especially in systems with aggressive processors. At the same time, directory protocols targeted at larger scale designs lead to a number of inherent inefficiencies relative to snoopy designs. A key goal of the AlphaServer GS320 architecture has been to achieve the best-of-both-worlds, partly by exploiting the bounded scale of the target systems.This paper focuses on the unique design features used in the AlphaServer GS320 to efficiently implement coherence and consistency. The guiding principle for our directory-based protocol is to address correctness issues related to rare protocol races without burdening the common transaction flows. Our protocol exhibits lower occupancy and lower message counts compared to previous designs, and provides more efficient handling of 3-hop transactions. Furthermore, our design naturally lends itself to elegant solutions for deadlock, livelock, starvation, and fairness. The AlphaServer GS320 architecture also incorporates a couple of innovative techniques that extend previous approaches for efficiently implementing memory consistency models. These techniques allow us to generate commit events (which are used for ordering purposes) well in advance of formulating the reply to a transaction. Furthermore, the separation of the commit event allows time-critical replies to bypass inbound requests without violating ordering properties. Even though our design specifically targets medium-scale servers, many of the same techniques can be applied to larger-scale directory-based and smaller-scale snoopy-based designs. Finally, we evaluate the performance impact of some of the above optimizations and present a few competitive benchmark results.
Timestamp snooping
Authors: Martin Milo M. K. , Sorin Daniel J. , Ailamaki Anastassia , Alameldeen Alaa R. , Dickson Ross M. , Mauer Carl J. , Moore Kevin E. , Plakal Manoj , Hill Mark D. , Wood David H.
Published: November 2005

Symmetric multiprocessor (SMP) servers provide superior performance for the commercial workloads that dominate the Internet. Our simulation results show that over one-third of cache misses by these applications result in cache-to-cache transfers, where the data is found in another processor's cache rather than in memory. SMPs are optimized for this case by using snooping protocols that broadcast address transactions to all processors. Conversely, directory-based shared-memory systems must indirectly locate the owner and sharers through a directory, resulting in larger average miss latencies.This paper proposes timestamp snooping, a technique that allows SMPs to i) utilize high-speed switched interconnection networks and ii) exploit physical locality by delivering address transactions to processors and memories without regard to order. Traditional snooping requires physical ordering of transactions. Timestamp snooping works by processing address transactions in a logical order. Logical time is maintained by adding a few bits per address transaction and having network switches perform a handshake to ensure on-time delivery. Processors and memories then reorder transactions based on their timestamps to establish a total order.We evaluate timestamp snooping with commercial workloads on a 16-processor SPARC system using the Simics full-system simulator. We simulate both an indirect (butterfly) and a direct (torus) network design. For OLTP, DSS, web serving, web searching, and one scientific application, timestamp snooping with the butterfly network runs 6-28% faster than directories, at a cost of 13-43% more link traffic. Similarly, with the torus network, timestamp snooping runs 6-29% faster for 17-37% more link traffic. Thus, timestamp snooping is worth considering when buying more interconnect bandwidth is easier than reducing interconnect latency.
Using meta-level compilation to check FLASH protocol code
Authors: Chou Andy , Chelf Benjamin , Engler Dawson , Heinrich Mark
Published: November 2005

Building systems such as OS kernels and embedded software is difficult. An important source of this difficulty is the numerous rules they must obey: interrupts cannot be disabled for "too long," global variables must be protected by locks, user pointers passed to OS code must be checked for safety before use, etc. A single violation can crash the system, yet typically these invariants are unchecked, existing only on paper or in the implementor's mind.This paper is a case study in how system implementors can use a new programming methodology, metalevel compilation (MC), to easily check such invariants. It focuses on using MC to check for errors in the code used to manage cache coherence on the FLASH shared memory multiprocessor. The only real practical method known for verifying such code is testing and simulation. We show that simple, system-specific checkers can dramatically improve this situation by statically pinpointing errors in the program source. These checkers can be written by implementors themselves and, by exploiting the system-specific information this allows, can detect errors unreachable with other methods. The checkers in this paper found 34 bugs in FLASH code despite the care used in building it and the years of testing it has undergone. Many of these errors fall in the worst category of systems bugs: those that show up sporadically only after days of continuous use. The case study is interesting because it shows that the MC approach finds serious errors in well-tested, non-toy systems code. Further, the code to find such bugs is usually 10-100 lines long, written in a few hours, and exactly locates errors that, if discovered during testing, would require several days of investigation by an experienced implementor.The paper presents 8 checkers we wrote, their application to five different protocol implementations, and a discussion of the errors that we found.
Communication scheduling
Authors: Mattson Peter , Dally William J. , Rixner Scott , Kapasi Ujval J. , Owens John D.
Published: November 2005

The high arithmetic rates of media processing applications require architectures with tens to hundreds of functional units, multiple register files, and explicit interconnect between functional units and register files. Communication scheduling enables scheduling to these emerging architectures, including those that use shared buses and register file ports. Scheduling to these shared interconnect architectures is difficult because it requires simultaneously allocating functional units to operations and buses and register file ports to the communications between operations. Prior VLIW scheduling algorithms are limited to clustered register file architectures with no shared buses or register file ports. Communication scheduling extends the range of target architectures by making each communication explicit and decomposing it into three components: a write stub, zero or more copy operations, and a read stub. Communication scheduling allows media processing kernels to achieve 98% of the performance of a central register file architecture on a distributed register file architecture with only 9% of the area, 6% of the power consumption, and 37% of the access delay, and 120% of the performance of a clustered register file architecture on a distributed register file architecture with 56% of the area and 50% of the power consumption.
Effective null pointer check elimination utilizing hardware trap
Authors: Kawahito Motohiro , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

We present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other optimizations to eliminate redundant null checks and maximize the effectiveness of other optimizations. In the second phase, it moves null checks forward and converts many null checks to hardware traps in order to minimize the execution cost of the remaining null checks. As a result, it eliminates many null checks effectively and exploits the maximum use of hardware traps. This algorithm has been implemented in the IBM cross-platform Java Just-in-Time (JIT) compiler. Our experimental results show that our approach improves performance by up to 71% for jBYTEmark and up to 10% for SPECjvm98 over the previously known best algorithm. They also show that it increases JIT compilation time by only 2.3%. Although we implemented our algorithm for Java, it is also applicable for other languages requiring null checking.
Fully reflexive intensional type analysis
Authors: Trifonov Valery , Saha Bratin , Shao Zhong
Published: November 2005

Compilers for polymorphic languages can use runtime type inspection to support advanced implementation techniques such as tagless garbage collection, polymorphic marshalling, and flattened data structures. Intensional type analysis is a type-theoretic framework for expressing and certifying such type-analyzing computations. Unfortunately, existing approaches to intensional analysis do not work well on types with universal, existential, or fixpoint quantifiers. This makes it impossible to code applications such as garbage collection, persistence, or marshalling which must be able to examine the type of any runtime value.We present a typed intermediate language that supports
fully reflexive
intensional type analysis. By fully reflexive, we mean that type-analyzing operations are applicable to the type of any runtime value in the language. In particular, we provide both type-level and term-level constructs for analyzing quantified types. Our system supports structural induction on quantified types yet type checking remains decidable. We show how to use reflexive type analysis to support type-safe marshalling and how to generate certified type-analyzing object code.
Recursive monadic bindings
Authors: Erkök Levent , Launchbury John
Published: November 2005

Monads have become a popular tool for dealing with computational effects in Haskell for two significant reasons: equational reasoning is retained even in the presence of effects; and program modularity is enhanced by hiding "plumbing" issues inside the monadic infrastructure. Unfortunately, not all the facilities provided by the underlying language are readily available for monadic computations. In particular, while recursive monadic computations can be defined directly using Haskell's built-in recursion capabilities, there is no natural way to express recursion over the
values
of monadic actions. Using examples, we illustrate why this is a problem, and we propose an extension to Haskell's donotation to remedy the situation. It turns out that the structure of monadic value-recursion depends on the structure of the underlying monad. We propose an axiomatization of the recursion operation and provide a catalogue of definitions that satisfy our criteria.
Non-stop Haskell
Authors: Cheadle A. M. , Field A. J. , Marlow S. , Jones S. L. Peyton , While R. L.
Published: November 2005

We describe an efficient technique for incorporating Baker's incremental garbage collection algorithm into the Spineless Tagless G-machine on stock hardware. This algorithm eliminates the stop/go execution associated with bulk copying collection algorithms, allowing the system to place an upper bound on the pauses due to garbage collection. The technique exploits the fact that objects are always accessed by jumping to code rather than being explicitly dereferenced. It works by modifying the entry code-pointer when an object is in the transient state of being evacuated but not scavenged. An attempt to enter it from the mutator causes the object to "self-scavenge" transparently before resetting its entry code pointer. We describe an implementation of the scheme in v4.01 of the Glasgow Haskell Compiler and report performance results obtained by executing a range of applications. These experiments show that the read barrier can be implemented in dynamic dispatching systems such as the STG-machine with very short mutator pause times and with negligible overhead on execution time.
Composing contracts
Authors: Peyton Jones Simon , Eber Jean-Marc , Seward Julian
Published: November 2005

Financial and insurance contracts do not sound like promising territory for functional programming and formal semantics, but in fact we have discovered that insights from programming languages bear directly on the complex subject of describing and valuing a large class of contracts.We introduce a combinator library that allows us to describe such contracts precisely, and a compositional denotational semantics that says what such contracts are worth. We sketch an implementation of our combinator library in Haskell. Interestingly, lazy evaluation plays a crucial role.
Bidwidth analysis with application to silicon compilation
Authors: Stephenson Mark , Babb Jonathan , Amarasinghe Saman
Published: November 2005

This paper introduces
Bitwise
, a compiler that
minimizes the bitwidth the number of bits used to represent each operand for both integers and pointers in a program. By propagating 70
static information both forward and backward in the program dataflow graph, Bitwise frees the programmer from declaring bitwidth invariants in cases where the compiler can determine bitwidths automatically. Because loop instructions comprise the bulk of dynamically executed instructions, Bitwise incorporates sophisticated loop analysis techniques for identifying bitwidths. We find a rich opportunity for bitwidth reduction in modern multimedia and streaming application workloads. For new architectures that support sub-word data-types, we expect that our bitwidth reductions will save power and increase processor performance.

This paper also applies our analysis to silicon compilation, the
translation of programs into custom hardware, to realize the full benefits of bitwidth reduction. We describe our integration of Bitwise with the DeepC Silicon Compiler. By taking advantage of bitwidth information during architectural synthesis, we reduce silicon real estate by 15 - 86%, improve clock speed by 3 - 249%, and reduce power by 46 - 73%. The next era of general purpose and reconfigurable architectures should strive to capture a portion of these gains.
Improved spill code generation for software pipelined loops
Authors: Zalamea Javier , Llosa Josep , Ayguadé Eduard , Valero Mateo
Published: November 2005

Software pipelining is a loop scheduling technique that extracts
parallelism out of loops by overlapping the execution of several
consecutive iterations. Due to the overlapping of iterations,
schedules impose high register requirements during their execution.
A schedule is valid if it requires at most the number of registers
available in the target architecture. If not, its register requirements
have to be reduced either by decreasing the iteration overlapping or by
spilling registers to memory. In this paper we describe a set of heuristics
to increase the quality of register-constrained modulo schedules. The heuristics decide between the two previous alternatives and define criteria for effectively selecting spilling candidates. The heuristics proposed for reducing the register pressure can be applied to any software pipelining technique. The proposals are evaluated using a register-conscious software pipeliner on a workbench composed of a large set of loops from the Perfect Club benchmark and a set of processor configurations. Proposals in this paper are compared against a previous proposal already described in the literature. For one of these processor configurations and the set of loops that do not fit in the available registers (32), a speed-up of 1.68 and a reduction of the memory traffic by a factor of 0.57 are achieved with an affordable increase in compilation time. For all the loops, this represents a speed-up of 1.38 and a reduction of the memory traffic by a factor of 0.7.
Compiler analysis of irregular memory accesses
Authors: Lin Yuan , Padua David
Published: November 2005

Irregular array accesses are array accesses whose array subscripts do not have closed-form expressions in terms of loop indices. Traditional array analysis and loop transformation techniques cannot handle irregular array accesses. In this paper, we study two kinds of simple and common cases of irregular array accesses: single-indexed access and indirect array access. We present techniques to analyze these two cases at compile-time, and we provide experimental results showing the effectiveness of these techniques in finding more implicit loop parallelism at compile-time and improved speedups.
Contaminated garbage collection
Authors: Cannarozzi Dante J. , Plezbert Michael P. , Cytron Ron K.
Published: November 2005

We describe a new method for determining when an object can be garbage collected. The method does not require marking live objects. Instead, each object
X
is
dynamically
associated with a stack frame
M
, such that
X
is collectable when
M
pops. Because
X
could have been dead earlier, our method is conservative. Our results demonstrate that the method nonetheless identifies a large percentage of collectable objects. The method has been implemented in Sun's Java Virtual Machine interpreter, and results are presented based on this implementation
A RISC architecture for symbolic computation
Authors: Kieburtz Richard B.
Published: November 2005

The G-machine is a language-directed processor architecture designed to support graph reduction as a model of computation. It can carry out lazy evaluation of functional language programs and can evaluate programs in which logical variables are used. To support these language features, the abstract machine requires tagged memory and executes some rather complex instructions, such as to evaluate a function application.This paper explores an implementation of the G-machine as a high performance RISC architecture. Complex instructions can be represented by RISC code without experiencing a large expansion of code volume. The instruction pipeline is discussed in some detail. The processor is intended to be integrated into a standard, 32-bit memory architecture. Tagged memory is supported by aggregating data with tags in a cache.
On the type accuracy of garbage collection
Authors: Hirzel Martin , Diwan Amer
Published: November 2005

We describe a novel approach to obtaining type-accurate information for garbage collection in a hardware and language independent way. Our approach uses a run-time analysis to propagate pointer/non-pointer information from significant type events (such as allocation, which always returns a pointer). We use this technique to perform a detailed comparison of garbage collectors with different levels of accuracy and explicit deallocation on a range of C programs. We take advantage of the portability of our approach to conduct our experiments on three hardware platforms, Alpha/Digital UNIX 4.0D, Pentium/Linux 2.2, and SPARC/Solaris 2. We find that the choice of hardware platform (which includes the architecture, operating system, and libraries) greatly affects whether or not type accuracy enhances a garbage collector's ability to reclaim objects.