bluuebunny/crossref_metadata_2025 huggingface dataset:
Memory allocation with lazy fits
Authors: Chung Yoo , Moon Soo-Mook
Published: November 2005

Dynamic memory allocation is an important part of modern programming languages. It is important that it be done fast without wasting too much memory. Memory allocation using lazy fits is introduced, where pointer increments, which is very fast, is used as the primary allocation method and where conventional fits such as best fit or first fit are used as backup. Some experimental results showing how lazy fits might perform are shown, and shows that the approach has the potential to be useful in actual systems.
Conservative garbage collection for general memory allocators
Authors: Rodriguez-Rivera Gustavo
Published: November 2005

This paper explains a technique that integrates conservative garbage collection on top of general memory allocators. This is possible by using two data structures named malloc-tables and jump-tables that are computed at garbage collection time to map pointers to beginning of objects and their sizes. This paper describes malloc-tables and jump-tables, an implementation of a malloc/jump-table based conservative garbage collector for Doug Lea's memory allocator, and experimental results that compare this implementation with Boehm-Demers-Weiser GC, a state-of-the-art conservative garbage collector.
Cycles to recycle
Authors: Hudson Richard L. , Moss J. Elliot , Subramoney Sreenivas , Washburn Weldon
Published: November 2005

The IA-64, Intel's 64-bit instruction set architecture, exhibits a number of interesting architectural features. Here we consider those features as they relate to supporting garbage collection (GC). We aim to assist GC and compiler implementors by describing how one may exploit features of the IA-64. Along the way, we record some previously unpublished object scanning techniques, and offer novel ones for object allocation (suggesting some simple operating system support that would simplify it) and the Java “jsr problem”. We also discuss ordering of memory accesses and how the IA-64 can achieve publication safety efficiently. While our focus is not on any particular GC implementation or programming language, we draw on our experience designing and implementing GC for the Intel Java Virtual Machine for the IA-64.
The case for profile-directed selection of garbage collectors
Authors: Fitzgerald Robert , Tarditi David
Published: November 2005

Many garbage-collected systems use a single garbage collection algorithm across all applications. It has long been known that this can produce poor performance on applications for which that collector is not well suited. In some systems, such as those that execute stand-alone compiled executables, an appropriate collector for each application can be selected from a pool of available collectors and tuned by using profile information. In a study of 20 benchmarks and several collectors, compiled with the Marmot optimizing Java-to-native compiler, for every collector there was at least one benchmark that would have been at least 15% faster with a more appropriate collector. The collectors are a copying collector, a generational copying collector, which is combined with each of 4 different write barriers, and the null collector, which allocates but never collects. A detailed analysis of storage management costs shows how they vary by application and collector.
On models for object lifetime distributions
Authors: Stefanović Darko , McKinley Kathryn S. , Moss J. Eliot B.
Published: November 2005

Analytical models of memory object lifetimes are appealing because having them would enable mathematical analysis or fast simulation of the memory management behavior of programs. In this paper, we investigate models for object lifetimes drawn from programs in object-oriented languages such as Java and Smalltalk. We present certain postulated analytical models and compare them with observed lifetimes for 58 programs. We find that observed lifetime distributions do not match previously proposed object lifetime models, but do agree in salient shape characteristics with the gamma distribution family used in statistical survival analysis for general populations.
Verifying safety properties of concurrent Java programs using 3-valued logic
Authors: Yahav Eran
Published: November 2005

We provide a parametric framework for verifying safety properties of concurrent Java programs. The framework combines thread-scheduling information with information about the shape of the heap. This leads to error-detection algorithms that are more precise than existing techniques. The framework also provides the most precise shape-analysis algorithm for concurrent programs. In contrast to existing verification techniques, we do not put a bound on the number of allocated objects. The framework even produces interesting results when analyzing Java programs with an unbounded number of threads. The framework is applied to successfully verify the following properties of a concurrent program: •Concurrent manipulation of linked-list based ADT preserves the ADT datatype invariant [19]. •The program does not perform inconsistent updates due to interference. •The program does not reach a deadlock. •The program does not produce run-time errors due to illegal thread interactions. We also find bugs in erroneous versions of such implementations. A prototype of our framework has been implemented.
Colored local type inference
Authors: Odersky Martin , Zenger Christoph , Zenger Matthias
Published: November 2005

We present a type system for a language based on
F
≤, which allows certain type annotations to be elided in actual programs. Local type inference determines types by a combination of type propagation and local constraint solving, rather than by global constraint solving. We re ne the previously existing local type inference system of Pierce and Turner[PT98] by allowing partial type information to be propagated. This is expressed by coloring types to indicate propagation directions. Propagating partial type information allows us to omit type annotations for the visitor pattern, the analogue of pattern matching in languages without sum types.
Type-base flow analysis
Authors: Rehof Jakob , Fähndrich Manuel
Published: November 2005

We present a novel approach to scalable implementation of type-based flow analysis with polymorphic subtyping. Using a new presentation of polymorphic subytping with instantiation constraints, we are able to apply context-free language (CFL) reachability techniques to type-based flow analysis. We develop a CFL-based algorithm for computing flow-information in time O(
n
³), where
n
is the size of the typed program. The algorithm substantially improves upon the best previously known algorithm for flow analysis based on polymorphic subtyping with complexity O(
n
8
). Our technique also yields the first demand-driven algorithm for polymorphic subtype-based flow-computation. It works directly on higher-order programs with structured data of finite type (unbounded data structures are incorporated via finite approximations), supports context-sensitive, global flow summariztion and includes polymorphic recursion.
An abstract Monte-Carlo method for the analysis of probabilistic programs
Authors: Monniaux David
Published: November 2005

We introduce a new method, combination of random testing and abstract interpretation, for the analysis of programs featuring both probabilistic and non-probabilistic nondeterminism. After introducing "ordinary" testing, we show how to combine testing and abstract interpretation and give formulas linking the precision of the results to the number of iterations. We then discuss complexity and optimization issues and end with some experimental results.
Nomadic pict
Authors: Unyapoth Asis , Sewell Peter
Published: November 2005

This paper addresses the design and verification of infrastructure for mobile computation. In particular, we study language primitives for communication between mobile agents. They can be classi ed into two groups. At a low level there arelocation dependentprimitives that require a programmer to know the current site of a mobile agent in order to communicate with it. At a high level there arelocation independentprimitives that allow communication with a mobile agent irrespective of any migrations. Implementation of the high level requires delicate distributed infrastructure algorithms. In earlier work with Wojciechowski and Pierce we made the two levels precise as process calculi, allowing such algorithms to be expressed as encodings of the high level into the low level; we built NOMADIC PICT, a distributed programming language for experimenting with such encodings. In this paper we turn to semantics, giving a de nition of the core language and proving correctness of an example infrastructure. This requires novel techniques: we develop equivalences that take migration into account, and reasoning principles for agents that are temporarily immobile (eg. waiting on a lock elsewhere in the system).
Stratified operational semantics for safety and correctness of the region calculus
Authors: Calcagno Cristiano
Published: November 2005

The region analysis of Tofte and Talpin is an attempt to determine statically the life span of dynamically allocated objects. But the calculus is at once intuitively simple, yet deceptively subtle, and previous theoretical analyses have been frustratingly complex: no analysis has revealed and explained in simple terms the connection between the subleties of the calculus and the imperative features it builds on. We present a novel approach for proving safety and correctness of a simplified version of the region calculus. We give a stratified operational semantics, composed of a highlevel semantics dealing with the conceptual difficulties of effect annotations, and a low-level one with explicit operations on a region-indexed store. The main results of the paper are a proof simpler than previous ones, and a modular approach to type safety and correctness. The flexibility of this approach is demonstrated by the simplicity of the extension to the full calculus with type and region polymorphism.
Avoiding exponential explosion
Authors: Flanagan Cormac , Saxe James B.
Published: November 2005

Current verification condition (VC) generation algorithms, such as weakest preconditions, yield a VC whose size may be exponential in the size of the code fragment being checked. This paper describes a two-stage VC generation algorithm that generates compact VCs whose size is worst-case quadratic in the size of the source fragment, and is close to linear in practice.This two-stage VC generation algorithm has been implemented as part of the Extended Static Checker for Java. It has allowed us to check large and complex methods that would otherwise be impossible to check due to time and space constraints.
What packets may come
Authors: Bhargavan Karthikeyan , Chandra Satish , McCann Peter J. , Gunter Carl A.
Published: November 2005

We consider the problem of monitoring an interactive device, such as an implementation of a network protocol, in order to check whether its execution is consistent with its specification. At rst glance, it appears that a monitor could simply follow the input-output trace of the device and check it against the specification. However, if the monitor is able to observe inputs and outputs only from a vantage point
external
to the device---as is typically the case---the problem becomes surprisingly difficult. This is because events may be bu ered, and even lost, between the monitor and the device, in which case, even for a correctly running device, the trace observed at the monitor could be inconsistent with the specification.In this paper, we formulate the problem of external monitoring as a
language recognition problem
. Given a specification that accepts a certain language of input-output sequences, we de ne another language that corresponds to input-output sequences observable externally. We also give an algorithm to check membership of a string in the derived language. It turns out that without any assumptions on the specification, this algorithm may take unbounded time and space. To address this problem, we de ne a series of properties of device specifications or protocols that can be exploited to construct e cient language recognizers at the monitor. We characterize these properties and provide complexity bounds for monitoring in each case.To illustrate our methodology, we describe properties of the Internet Transmission Control Protocol (TCP), and identify features of the protocol that make it challenging to monitor e ciently.
Typing a multi-language intermediate code
Authors: Gordon Andrew D. , Syme Don
Published: November 2005

The Microsoft .NET Framework is a new computing architecture designed to support a variety of distributed applications and web-based services. .NET software components are typically distributed in an object-oriented intermediate language, Microsoft IL, executed by the Microsoft Common Language Runtime. To allow convenient multi-language working, IL supports a wide variety of high-level language constructs, including class-based objects, inheritance, garbage collection, and a security mechanism based on type safe execution.This paper precisely describes the type system for a substantial fragment of IL that includes several novel features: certain objects may be allocated either on the heap or on the stack; those on the stack may be boxed onto the heap, and those on the heap may be unboxed onto the stack; methods may receive arguments and return results via typed pointers, which can reference both the stack and the heap, including the interiors of objects on the heap. We present a formal semantics for the fragment. Our typing rules determine well-typed IL instruction sequences that can be assembled and executed. Of particular interest are rules to ensure no pointer into the stack outlives its target. Our main theorem asserts type safety, that well-typed programs in our IL fragment do not lead to untrapped execution errors.Our main theorem does not directly apply to the product. Still, the formal system of this paper is an abstraction of informal and executable specifications we wrote for the full product during its development. Our informal specification became the basis of the product team's working specification of type-checking. The process of writing this specification, deploying the executable specification as a test oracle, and applying theorem proving techniques, helped us identify several security critical bugs during development.
Slicing object-oriented java programs
Authors: Chen Zhenqiang , Xu Baowen
Published: November 2005

This paper presents a new approach to represent dependence for object-oriented (OO) Java software. The program dependence graph (PDG) consists of a set of PDGs with tags that are not connected. This new approach distinguishes data members for different objects and represents the effects of polymorphism and dynamic bindings. Based on this model, we introduce the concepts of partial slicing, class slicing and object slicing. In our slicing algorithm, we slice not only statements but also data members in classes, and inter-method slicings are transformed to intra-method slicings.
Incrementalized pointer and escape analysis
Authors: Vivien Frédéric , Rinard Martin
Published: November 2005

We present a new pointer and escape analysis. Instead of analyzing the whole program, the algorithm incrementally analyzes only those parts of the program that may deliver useful results. An analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return.

Our experimental results show that almost all of the objects are allocated at a small number of allocation sites and that an incremental analysis of a small region of the program surrounding each site can deliver almost all of the benefit of a whole-program analysis. Our analysis policy is usually able to deliver this benefit at a fraction of the whole-program analysis cost.
Heap profiling for space-efficient Java
Authors: Shaham Ran , Kolodner Elliot K. , Sagiv Mooly
Published: November 2005

We present a heap-profiling tool for exploring the potential for space savings in Java programs. The output of the tool is used to direct rewriting of application source code in a way that allows more timely garbage collection (GC) of objects, thus saving space. The rewriting can also avoid allocating some objects that are never used.

The tool measures the difference between the actual collection time and the potential earliest collection time of objects for a Java application. This time difference indicates potential savings. Then the tool sorts the allocation sites in the application source code according to the accumulated potential space saving for the objects allocated at the sites. A programmer can investigate the source code surrounding the sites with the highest savings to find opportunities for code rewriting that could save space. Our experience shows that in many cases simple code rewriting leads to actual space savings and in some cases also to improvements in program runtime.

Experimental results using the tool and manually rewriting code show average space savings of 18% for the SPECjvm98 benchmark suite. Results for other benchmarks are also promising. We have also classified the program transformations that we have used and argue that in many cases improvements can be achieved by an optimizing compiler.
Efficient representations and abstractions for quantifying and exploiting data reference locality
Authors: Chilimbi Trishul M.
Published: November 2005

With the growing processor-memory performance gap, understanding and optimizing a program's reference locality, and consequently, its cache performance, is becoming increasingly important. Unfortunately, current reference locality optimizations rely on heuristics and are fairly ad-hoc. In addition, while optimization technology for improving instruction cache performance is fairly mature (though heuristic-based), data cache optimizations are still at an early stage. We believe the primary reason for this imbalance is the lack of a suitable representation of a program's dynamic data reference behavior and a quantitative basis for understanding this behavior.

We address these issues by proposing a quantitative basis for understanding and optimizing reference locality, and by describing efficient data reference representations and an exploitable locality abstraction that support this framework. Our data reference representations (Whole Program Streams and Stream Flow Graphs) are compact—two to four orders of magnitude smaller than the program's data reference trace—and permit efficient analysis—on the order of seconds to a few minutes—even for complex applications. These representations can be used to efficiently compute our exploitable locality abstraction (hot data streams). We demonstrate that these representations and our hot data stream abstraction are useful for quantifying and exploiting data reference locality. We applied our framework to several SPECint 2000 benchmarks, a graphics program, and a commercial Microsoft database application. The results suggest significant opportunity for hot data stream-based locality optimizations.
Related field analysis
Authors: Aggarwal Aneesh , Randall Keith H.
Published: November 2005

We present an extension of field analysis (sec [4]) called
related field analysis
which is a general technique for proving relationships between two or more fields of an object. We demonstrate the feasibility and applicability of related field analysis by applying it to the problem of removing array bounds checks. For array bounds check removal, we define a pair of related fields to be an integer field and an array field for which the integer field has a known relationship to the length of the array. This related field information can then be used to remove array bounds checks from accesses to the array field. Our results show that related field analysis can remove an average of 50% of the dynamic array bounds checks on a wide range of applications.

We describe the implementation of related field analysis in the Swift optimizing compiler for Java, as well as the optimizations that exploit the results of related field analysis.
Ultra-fast aliasing analysis using CLA
Authors: Heintze Nevin , Tardieu Olivier
Published: November 2005

We describe the design and implementation of a system for very fast points-to analysis. On code bases of about million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. Our two main contributions are a database-centric analysis architecture called compile-link-analyze (CLA), and a new algorithm for implementing dynamic transitive closure. Our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within Lucent to help with consistent type modifications to large legacy C code bases.
Facile
Authors: Schnarr Eric C. , Hill Mark D. , Larus James R.
Published: November 2005

Architectural simulators are essential tools for computer architecture and systems research and development. Simulators, however, are becoming frustratingly slow, because they must now model increasingly complex micro-architectures running realistic workloads. Previously, we developed a technique called fast-forwarding, which applied partial evaluation and mermoization to improve the performance of detailed architectural simulations by as much as an order of magnitude [14].

While writing a detailed processor simulator is difficult, implementing fast-forwarding is even more complex. This paper describes Facile, a domain-specific language for writing detailed, accurate micro-architecture simulators. Architectural descriptions written in Facile can be compiled, using partial evaluation techniques, into fast-forwarding simulators that achieve significant performance improvements with far less programmer effort. Facile and its compiler make this performance-enhancing technique accessible to computer architects.
Interpreting RSets, SSets and features by denotational semantics
Authors: Milanese Vitaliano
Published: November 2005

Solid modellers used in CAD-CAM applications are becoming more and more complex: they require sophisticated programming techniques capable of generating reliable objects, copies of which may be defined in different and coexistent representation schemes. Models of these objects are also used to support the new paradigm of modelling by features. As a consequence, it is necessary to have at one's disposal formal tools to evaluate correctness of graphic objects and programs. To this purpose denotational semantics provides a way to evaluate the correctness of graphic objects, separately in their different aspects, according to the proper modelling scheme.
Accreditation in Canada
Authors: Gill Suzanne
Published: November 2005

Accreditation of university and college two-year programs is in place in Canada since 1989, and has been enthusiastically accepted by both the academic institutions and the business community. It is recognized that in a profession, we need to define a body of knowledge; require a qualification in order to practice the profession; and be accountable for our actions to a professional body. Certification of individuals was introduced in Canada in 1989, along the lines of the certification required for other professional bodies (e.g. medical, engineering, accounting). As part of that process, accreditation of educational programs began in 1985 at universities, and in 1989 at two-year colleges.
Thinking about writing a textbook? An overview of the process
Authors: Morneau Paul
Published: November 2005

The recent curriculum recommendations [1, 2], coupled with new releases of applications software and new approaches to teaching, present an opportunity for writing the next generation of computing textbooks. For those readers of

3C ONLINE

who might consider writing a textbook, this article provides an overview of the publication process.
Computing and choice of language
Authors: Cover C. Fay
Published: November 2005

Pikes Peak Community College is an average-sized college about 70 miles south of Denver. Its students come from wide ethnic backgrounds including Hispanics and Native Americans. Students are generally prepared to enter college life, although many need some form of academic remediation.
A concept for functional programming and distributed data processing in a local area network and its implementation
Authors: Drashansky Tsvetan T.
Published: November 2005

In this paper we describe a new approach to the pure functional programming which is based on the use of a local area network and external files. This approach essentially increases the efficiency and the field of the possible application of the functional programs. Our concepts are implemented in the framework of a FP-like functional language named FP* through the system FP*/88N. Here we state the besic mechanisms of the different system modules which demonstrate the new ideas. The advantages of the new approach are explained and compared to those known by now. The experimental applications of FP*/88N prove the existance of opportunities to create usable applied programs in pure functional style.
Prolog in ‘C’
Authors: Boyd Joanne L. , Karam Gerald M.
Published: November 2005

This paper describes a procedural definition of Prolog based on the features of the 'C' programming language. Our motivation to exploit the complementary nature of procedural and declarative programming lead to the objective of a dual Prolog and 'C' programming environment. A translator has been built which accepts Prolog programs and produces sets of 'C' functions which can be integrated into a 'C' program to form a single, common language target system. Each 'C' function corresponds to a single Prolog procedure. The emphasis of the translation is placed on producing a consistent and readable format for PIC (
Prolog in 'C'
) code which allows the user to optimize the code by tuning. Examples are provided to demonstrate the benefit of optimizations versus their programming effort. The PIC code produced by the translator has been tested for accuracy, coverage, and efficiency, and exhibited acceptable results.
The towers of Hanoi from a different viewpoint
Authors: Konopasek Milos
Published: November 2005

An interpretation of the Towers of Hanoi problem in a declarative language (TK!Solver) is offered as an alternative to procedural treatments using recursive or iterative techniques. The article gives a glimpse at TK!Solver and shows solutions to some of the Tower of Hanoi problems beyond a simple simulation of the disk transfer process.
Spelling verification in prolog
Authors: Berghel Hal , Traudt Eric
Published: November 2005

In this paper we present a spelling verification program written in Prolog. This program performs simple table lookup for each word in an input list. If the current word fails to match with the lexical entries, several procedures are invoked which will attempt to identify the type of spelling error and suggest alternative spellings.
Modular programming in C
Authors: Dutta Kalyan
Published: November 2005

Unlike ADA or Modula-2, the programming language C is not inherently modular. But by exploiting certain features of the language it is possible to build modular design into C programs. This has advantages in large programming projects where source code will be written by many programmers, or in applications calling for a collection of syntactically identical interconnected modules.The approach suggested here is not as ambitious as in Stroustrup [1982], requiring a change to the C compiler; rather, standard C (Kernighan & Ritchie [1978]) is used. This is more in keeping with the work of Boyd [1983, 1984].
A static analysis of prolog programs
Authors: Matsumoto Hidekazu
Published: November 2005

A static analysis of Prolog programs was made for the purposes of revealing the behavior of Prolog programs and of getting useful information for system design. This analysis consists of two parts: one analyzes general aspects of Prolog programs, the other evaluates some compiler techniques which have a great deal of interest. This work has been done using a program written in Prolog, which collects data from test programs. This document summarizes the results of this static analysis.
An overview on ModPascal
Authors: Olthoff Walter
Published: November 2005

The object oriented programming Language ModPascal and its programming environment are introduced. ModPascal extends Standard Pascal by constructs that have shown usefullness in abstract data type theory: module types, enrichments, instantiations and instantiate types. In fact, ModPascal has been designed as procedural counterpart of a specification Language based on abstract data types, and its semantics also employs algebraic structures. ModPascal programs may be edited, compiled and executed by using the ModPascal Programming System that includes a multi-user data base for ModPascal objects.
Hybrid Run-time Power Management Technique for Real-time Embedded System with Voltage Scalable Processor
Authors: Kim Minyoung , Ha Soonhoi
Published: November 2005

This paper presents a new run-time power management technique for real-time embedded systems which consist of a voltage scalable processor and power controllable peripheral devices. We have observed that there exist significant trade-offs in terms of energy consumption between the Dynamic Power Management (DPM) scheme and the Dynamic Voltage Scaling (DVS) scheme over a wide range of system operating conditions. The proposed technique fully exploits workload-variation slack time by partitioning the task into several timeslots and shut down the unneeded peripheral device on timeslot-by-timeslot basis. Through extensive simulations, the novelty and the usefulness of the proposed technique are demonstrated.
Power-Aware Design Synthesis Techniques for Distributed Real-Time Systems
Authors: Kang Dong-In , Crago Stephen , Suh Jinwoo
Published: November 2005

This paper presents an end-to-end synthesis technique for low-power distributed real-time system design. This technique synthesizes supply voltages of resources to optimize system-level power consumption while satisfying end-to-end hard real-time latency bounds. A system is modeled as a set of distributed task chains (or pipelines). Each task chain is given its own end-to-end constraints. Task chains may share resources. Our approach searches the space of the trade-off between end-to-end latency and supply voltages of resources to minimize system-level power consumption. A power optimization algorithm is proposed for simple distributed real-time systems that do not have any resource sharing between task chains, and its optimality is shown. For more general systems, a heuristic based on the same techniques is proposed.
Register Allocation for Banked Register File
Authors: Park Jinpyo , Lee Je-Hyung , Moon Soo-Mook
Published: November 2005

A banked register file is a register file partitioned into banks. A register in a banked register file is addressed with the register number in conjunction with the active bank number. A banked register file may be employed to reduce the number of bits for register operands in the instruction encoding at the cost of bank changes and inter-bank data transfers. Although a banked register file is introduced to provide sufficient registers and reduce memory traffic, it may on the other hand inflate code by unwanted bank hanges and excessive inter-bank data movements. In this context, code quality heavily depends on the register allocator that decides the location of each variable. This paper addresses a heuristic approach to register allocation for exploiting two register banks. It performs global register allocation with the primary bank registers, while reducing the register pressure by doing local register allocation with the secondary bank registers. Experimental results show that the proposed register allocator eliminates a significant amount of memory traffic while achieving smaller code size compared to an allocator that utilizes the primary bank only.
Loop Transformations for Architectures with Partitioned Register Banks
Authors: Huang Xianglong , 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, processors can often exploit considerable instruction-level parallelism (ILP), and thus significantly improve performance, at the cost of substantially increasing register requirements. These increasing register requirements, however, make it difficult to build a high-performance embedded processor with a single, multi-ported register file while maintaining clock speed and limiting power consumption.

Some digital signal processors, such as the TI C6x, reduce the number of ports required for a register bank by partitioning the register bank into multiple banks. Disjoint subsets of functional units are directly connected to one of the partitioned register banks. Each register bank and its associate functional units is called a
cluster
. Clustering reduces the number of ports needed on a per-bank basis, allowing an increased clock rate. However, execution speed can be hampered because of the potential need to copy “non-local” operands among register banks in order to make them available to the functional unit performing an operation. The task of the compiler is to both maximize parallelism and minimize the number of remote register accesses needed.

Previous work has concentrated on methods to partition virtual registers amongst the target architecture's clusters. In this paper, we show how high-level loop transformations can enhance the partitioning obtained by low-level schemes. In our experiments, loop transformations improved software pipelining by 27% on a machine with 2 clusters, each having 1 floating-point and 1 integer register bank and 4 functional units. We also observed a 20% improvement on a similar machine with 4 clusters of 2 functional units. In fact, by performing the described loop transformations we were able to show improvements of greater than 10% over schedules (for un-transformed loops) generated with the unrealistic assumption of a single multi-ported register bank.
ENSEMBLE
Authors: Cadot Sidney , Kuijlman Frits , Langendoen Koen , van Reeuwijk Kees , Sips Henk
Published: November 2005

The ENSEMBLE communication library exploits overlapping of message aggregation (computation) and DMA transfers (communication) for embedded multi-processor systems. In contrast to traditional communication libraries, ENSEMBLE operates onn-dimensional data descriptors that can be used to specify often-occurring data access patterns inn-dimentional arrays. This allows ENSEMBLE to setup a three-stage pack-transfer-unpack pipeline, effectively overlapping message aggregation and DMA transfers. ENSEMBLE is used to support Spar/Java, a Java-based language with SPMD annotations. Measurements on a TriMedia-based multi-processor system show that ENSEMBLE increases performance up to 39% for peer-to-peer communication, and up to 34% for all-to-all communication.
Embedded Control Systems Development with Giotto
Authors: Henzinger Thomas A. , Horowitz Benjamin , Kirsch Christoph Meyer
Published: November 2005

Giotto is a principled, tool-supported design methodology for implementing embedded control systems on platforms of possibly distributed sensors, actuators, CPUs, and networks. Giotto is based on the principle that time-triggered task invocations plus time-triggered mode switches can form the abstract essence of programming real-time control systems. Giotto consists of a programming language with a formal semantics, and a retargetable compiler and runtime library. Giotto supports the automation of control system design by strictly separating platform-independent functionality and timing concerns from platform-dependent scheduling and communication issues. The time-triggered predictability of Giotto makes it particularly suitable for safety-critical applications with hard real-time constraints. We illustrate the platform-independence and time-triggered execution of Giotto by coordinating a heterogeneous flock of Intel x86 robots and Lego Mindstorms robots.
MILAN
Authors: Bakshi A. , Prasanna V. K. , Ledeczi A.
Published: November 2005

We present MILAN, a model based extensible framework that facilitates rapid, multigranular performance evaluation of a large class of embedded systems, by seamlessly integrating different widely used simulators in to a unified environment. MILAN provides a formal paradigm for specification of structural and behavioral aspects of embedded systems, an integrated model-based approach, and a unified software environment for system design and simulation. This paper provides an overview of MILAN, discusses the Model Integrated Computing philosophy, and illustrates the high-level modeling concepts being developed in the MILAN project for embedded systems design and evaluation.
Interval-Based Analysis of Software Processes
Authors: Ziegenbein D. , Wolf F. , Richter K. , Jersak M. , Ernst R.
Published: November 2005

A typical characteristic of complex embedded systems is their large software share that consists of software processes either being directly written in an implementation language like C, or being created from abstract modeling tools (e. g. Simulink or StateMate) using standard code generators, or being reused from previous designs (e. g. legacy code). A major challenge is the safe integration of these separately designed system parts. This paper focuses on the formal analysis of software processes with respect to their non-functional properties like timing or power consumption. The proposed approach yields safe upper and lower bounds on these properties and has advantages over previous work in terms of accuracy and efficiency. Further, it is shown how the results of this process-level analysis can be utilized to generate a model for the system-wide validation of non-functional properties. The applicability of the approach is demonstrated using an example of a filter process operating on a packet stream.
Automatic Accurate Live Memory Analysis for Garbage-Collected Languages
Authors: Unnikrishnan Leena , Stoller Scott D. , Liu Yanhong A.
Published: November 2005

This paper describes a general approach for automatic and accurate live heap space and live heap space-bound analyses for high-level languages. The approach is based on program analysis and transformations and is fully automatic. The space-bound analysis produces accurate (tight) upper bounds in the presence of partially known input structures. The analyses have been implemented and experimental results confirm their accuracy.
Generating Decision Trees for Decoding Binaries
Authors: Theiling Henrik
Published: November 2005

Tools reading binary code, like analysers, debuggers, disassemblers, etc., need to decode the target's machine code. A decision tree is often used to represent the decoding function.

Manually writing a decoder is a lengthy and error-prone task. It is desirable to be able to use the vendor's instruction code manual and to easily transform the documentation into a specification that a tool can use to generate a decoder.

This paper presents a novel algorithm that computes a decision tree from machine code bit patterns alone. Neither the bit fields of the machine code, nor the width of the machine command, nor the order in which the bits should be decoded need to be specified. The decoding algorithm accesses any significant bit exactly once during decoding.
Dealing with Hardware in Embedded Software
Authors: Mérillion Fabrice , Muller Gilles
Published: November 2005

Writing code that talks to hardware is a crucial part of any embedded project. Both productivity and quality are needed, but some flaws in the traditional development process make these requirements difficult to meet.

We have recently introduced a new approach of dealing with hardware, based on the Devil language. Devil allows to write a high-level, formal definition of the programming interface of a peripheral circuit. A compiler automatically checks the consistency of a Devil specification, from which it generates the low-level, hardware-operating code.

In our original framework, the generated code is dependent of the host architecture (CPU, buses, and bridges). Consequently, any variation in the hardware environment requires a specific tuning of the compiler. Considering the variability of embedded architectures, this is a serious drawback. In addition, this prevents from mixing different buses in the same circuit interface.

In this paper, we remove those limitations by improving our framework in two ways. (i) We propose a better isolation between the Devil compiler and the host architecture. (ii) We introduce Trident, a language extension aimed at mapping one or several buses to each peripheral circuit.
C Compiler Design for an Industrial Network Processor
Authors: Wagner Jens , Leupers Rainer
Published: November 2005

One important problem in code generation for embedded processors is the design of efficient compilers for ASIPs with application specific architectures. This paper outlines the design of a C compiler for an industrial ASIP for telecom applications. The target ASIP is a network processor with special instructions for bit-level access to data registers, which is required for packet-oriented communication protocol processing. From a practical viewpoint, we describe the main challenges in exploiting these application specific features in a C compiler, and we show how a compiler backend has been designed that accomodates these features by means of compiler intrinsics and a dedicated register allocator. The compiler is fully operational, and first experimental results indicate that C-level programming of the ASIP leads to good code quality without the need for time-consuming assembly programming.
A Dynamic Programming Approach to Optimal Integrated Code Generation
Authors: Keßler Christoph , Bednarski Andrzej
Published: November 2005

Phase-decoupled methods for code generation are the state of the art in compilers for standard processors but generally produce code of poor quality for irregular target architectures such as many DSPs. In that case, the generation of efficient code requires the simultaneous solution of the main subproblems instruction selection, instruction scheduling, and register allocation, as an integrated optimization problem.

In contrast to compilers for standard processors, code generation for DSPs can afford to spend much higher resources in time and space on optimizations. Today, most approaches to
optimal
code generation are based on integer linear programming, but these are either not integrated or not able to produce optimal solutions except for very small problem instances.

We report on research in progress on a novel method for fully integrated code generation that is based on dynamic programming. In particular, we introduce the concept of a
time profile
. We focus on the basic block level where the data dependences among the instructions form a DAG. Our algorithm aims at combining time-optimal scheduling with optimal instruction selection, given a limited number of general-purpose registers. An extension for irregular register sets, spilling of register contents, and intricate structural constraints on code compaction based on register usage is currently under development, as well as a generalization for global code generation.

A prototype implementation is operational, and we present first experimental results that show that our algorithm is practical also for medium-size problem instances. Our implementation is intended to become the core of a future, retargetable code generation system.
Middleware For Building Adaptive Systems Via Configuration
Authors: Narain Sanjai , Vaidyanathan Ravichander , Moyer Stanley , Stephens William , Parmeswaran Kirthika , Shareef Abdul Rahim
Published: November 2005

COTS (commercial off-the-shelf) devices, including middleware components, are capable of executing powerful, distributed algorithms. Very large, adaptive systems can be created by simply integrating these devices, not by creating new devices, algorithms or external control systems. The principal integration method is configuration: every device is designed to have a finite set of configuration parameters that can be set to definite values. These parameters are static in that, unlike the device's dynamic state, these do not change during the device's normal operation. Inspite of the ubiquity of the configuration method, there is no "science" for it. There are no tools which let one specify global, end-to-end system functionality requirements at a high level, reason about these, and have these compiled into device configurations. On the other hand, it is inherently difficult to develop this science because of the large conceptual gap between global, end-to-end requirements and device configurations. A middleware is needed to bridge this gap in the form of specification, reasoning, compilation and diagnostic tools.This position paper sketches a technique called Service Grammar for developing such middleware for a given domain. It is based on the idea that algorithms for implementing end-to-end functional requirements can be expressed as the enforcement of a set of fundamental requirements. These are upon the existence of definite high-level relationships between configuration parameters of various devices. We can collect these into a Requirements Library. By mixing and matching items from it we can define algorithms for implementing a very wide range of end-to-end functional requirements. This Library can also simplify design of the reasoning, compilation and diagnostic tools. This plan is illustrated by analyzing how realistic service requirements are implemented in a Virtual Private Network via configuration steps.First, a network of "resilient", secure tunnels is set up by composing capabilities of protocols OSPF, GRE and IPSec. Then, quality of service guarantees are established by composing capabilities of MPLS, RSVP and DiffServ. Finally, as an example of configuring middleware components themselves, an example is presented from CORBA security.
Evaluating and Optimizing Thread Pool Strategies for Real-Time CORBA
Authors: Pyarali Irfan , Spivak Marina , Cytron Ron , Schmidt Douglas C.
Published: November 2005

Strict control over the scheduling and execution of processor resources is essential for many fixed-priority real-time applications. To facilitate this common requirement, the Real-Time CORBA (RT-CORBA) specification defines standard middleware features that support end-to-end predictability for operations in such applications. One of the most important features in RT-CORBA is thread pools, which allow application developers and end-users to configure and control processor resources.This paper provides two contributions to the evaluation of techniques for improving the quality of implementation of RT-CORBA thread pools. First, we describe the key patterns underlying common strategies for implementing RT-CORBA thread pools. Second, we evaluate each thread pool strategy in terms of its consequences on (1) feature support, such as request buffering and thread borrowing, (2) scalability in terms of end-points and event demultiplexers required, (3) efficiency in terms of data movement, context switches, memory allocations, and synchronizations required, (4) optimizations in terms of stack and thread specific storage memory allocations, and (5) bounded and unbounded priority inversion incurred in each implementation. This paper also provides results that illustrate empirically how different thread pool implementation strategies perform in different ORB configurations.