bluuebunny/crossref_metadata_2025 huggingface dataset:
Development of a debugger for a concurrent language
Authors: Baiardi F. , De Francesco N. , Matteoli E. , Stefanini S. , Vaglini G.
Published: November 2005

This work discusses some issues in the debugging of concurrent programs. A set of desirable characteristics of a debugger for concurrent languages is deduced from an examination of the differences between the debugging of concurrent programs and that of sequential ones. A debugger for a concurrent language, derived from CSP, is then presented. It is based upon a semantic model of the supported language. The debugger enables to compare a description of the program behaviour to the actual behaviour as well as to valuate assertions on the process state. The description of the behaviuor is given by a formalism whose semantics is also specified. The formalism can specify program behaviuors at various abstraction levels. Lastly some guidelines for the implementation of the debugger are shown and a detailed example of program description is analyzed.
Interactive debugging of concurrent programs
Authors: Weber Jonice Cynthia
Published: November 2005

This paper summarizes techniques for designing and implementing source-level interactive debuggers for concurrent programs. Facilities common to source-level interactive debuggers have been adapted to meet the needs of a concurrent programming environment. Of special interest are those debugging facilities which allow the programmer to monitor and influence the execution of concurrent processes.
A systematic approach to advanced debugging
Authors: Fritzson Peter
Published: November 2005

This paper presents two topics: Implementation of a debugger through use of an incremental compiler, and techniques for fine-grained incremental compilation. Both the debugger and the compiler are components of the highly Integrated programming environment DICE (Distributed Incremental Compiling Environment) which alms at providing programmer support in the case where the programming environment resides in a host computer and the program. Is running on a target computer that is connected to the host.
A real-time microprocessor debugging technique
Authors: Hill Charles R.
Published: November 2005

This note describes RED, a remotely executed debugger capable of generating a real-time source level trace history of a high level language program executing on a microprocessor. The trace history consists of a display of the source statements of each basic block executed, annotated by the time at which execution of that block began. Basic blocks are traced rather than statements to reduce sampling bandwidth requirements while still retaining the ability to record the essential logical flow of programs. RED is intended to assist in debugging stand-alone high level language process control programs with real-time constraints.

We outline two possible implementation schemes for generating the real-time trace history. In both, a "debugging co-processor" collects in a history buffer the values of the program counter (PC) and the corresponding value of a clock as each basic block begins execution. The debugger, which runs on the processor hosting the compiler and has access to the co-processor over a fast link, reconstructs a source level trace from the PC-time pairs in the history buffer. In one scheme, the language compiler emits an extra instruction at the beginning of each basic block in the program to output the value of the program counter to a parallel port connected to the debug processor. The second method makes use of an extended target memory space to provide tag bits denoting basic blocks. When an instruction is fetched, the debug processor detects the presence of the tag bits and buffers up the value of the corresponding program counter and time. The first method is simpler to implement, requiring only conventional, usually straightforward hardware additions to the target, but requires the execution overhead of the extra instructions. In both cases the debugger itself runs on the host processor and has access to tables generated during compile time of the source program.
DELTA
Authors: Walter Carol K.
Published: November 2005

DELTA is the Universal Debugger for CP-6. CP-6, a general purpose communications-oriented operating system, is made up of two environments: host and communications. These two environments each have their own operating system and run on different CPUs. DELTA allows the user to symbolically debug programs written in any language or combination of languages in either environment. DELTA also allows symbolic debugging of the host operating system, the communications operating system, and the language and utility processors for each environment. In addition, DELTA allows symbolic patching of both operating systems and the language and utility processors providing a timely field support for CP-6.
Summary of evaluation and comments
Authors: Johnson Mark Scott
Published: November 2005

On the last day of the Symposium an evaluation form was distributed to all participants. About half responded; their comments are summarized here.

Three-quarters of those responding felt the Symposium met their expectations well or very well. Important topics reported as being not discussed or not sufficiently discussed included real-time debugging, practical debugging strategies, implementation issues for production debuggers, human factors, and architectural support for debugging.
A theory of organization
Authors: von Issendorff H.
Published: November 2005

The theory of organization deals with the representation and treatment of processing Structures and their realization. It offers an algebra, which in particular is qualified for a unified description of soft- and hardware. The term replacement rules coming along with the algebra allow to change a processing structure in a variety of ways. In particular, there are order changing rules allowing to generate any representation between the minimum order of dataflow and the maximum order of a sequence. Moreover, conversion rules can be specified for the transformation of conventional programming languages into the (language of the) algebra. The same is possible for the conversion of Boolean algebra. Finally, a circuit description language can be derived from the algebra, which seems to be well suited for VLSI-layout. Part 1 of this paper covers a general introduction to the subject and the notions, the relations, and the algebra on which the theory of organization is based. Part 2 deals with nondeterminism and communicating processes, presents the conversion rules for a subset of Pascal and for Boolean expressions and introduces the circuit description language.
Don't make the wrong mistakes
Authors: Graham Paul
Published: November 2005

Sometimes it's worth doing things badly in order to do them fast. When is this the right plan? Are some kinds of mistakes worse than others? Could the right infrastructure make trial and error programming more effective? How will it play out in the future?
Numbering matters
Authors: Gauthier Nadji , Pottier François
Published: November 2005

We study a type system equipped with universal types and equire-cursive types, which we refer to as F
͘
. We show that type equality may be decided in time O(
n
log
n
), an improvement over the previous known bound of O(
n
2
). In fact, we show that two more general problems, namely entailment of type equations and type unification, may be decided in time O(
n
log
n
), a new result. To achieve this bound, we associate, with every F
͘
type, a
first-order canonical form
, which may be computed in time O(
n
log
n
). By exploiting this notion, we reduce all three problems to equality and unification of
first-order
recursive terms, for which efficient algorithms are known.
Verification of safety properties for concurrent assembly code
Authors: Yu Dachuan , Shao Zhong
Published: November 2005

Concurrency, as a useful feature of many modern programming languages and systems, is generally hard to reason about. Although existing work has explored the verification of concurrent programs using high-level languages and calculi, the verification of concurrent assembly code remains an open problem, largely due to the lack of abstraction at a low-level. Nevertheless, it is sometimes necessary to reason about assembly code or machine executables so as to achieve higher assurance.In this paper, we propose a logic-based "type" system for the static verification of concurrent assembly programs, applying the "invariance proof" technique for verifying general safety properties and the "assume-guarantee" paradigm for decomposition. In particular, we introduce a notion of "local guarantee" for the thread-modular verification in a non-preemptive setting.Our system is fully mechanized. Its soundness has been verified using the Coq proof assistant. A safety proof of a program is semi-automatically constructed with help of Coq, allowing the verification of even undecidable safety properties. We demonstrate the usage of our system using three examples, addressing mutual exclusion, deadlock freedom, and partial correctness respectively.
Jazzing up JVMs with off-line profile data
Authors: Sandya S. M.
Published: November 2005

In Java Virtual Machines employing dynamic compilation, there exists a tradeoff between compilation overhead and execution time. The compilation efforts are directed selectively on program hotspots so that gains in performance due to compiled code can overcome compilation cost. Using online profile incurs runtime-profiling overhead. Using only offline profile data might result in selecting cold methods for compilation when offline profile does not mirror current application behavior. Hence we propose a hybrid scheme that incorporates both online and offline profile to identify selective compilation candidates. We also discuss the significance of selective compilation ordering especially in applications which exhibit phase changes with respect to the method invocations it makes. This results in the hotspots of the program also changing as the application executes. Hence it is important for the selective compilation scheme to be highly responsive to phase changes and target the compilation efforts on the new hotspots, as they appear. We propose a temporal event graph for capturing this phase changing behavior of the application (in terms of the method calls it makes) and use this information in making better selective compilation decisions.
A practical type system and language for reference immutability
Authors: Birka Adrian , Ernst Michael D.
Published: November 2005

This paper describes a type system that is capable of expressing and enforcing immutability constraints. The specific constraint expressed is that the abstract state of the object to which an immutable reference refers cannot be modified using that reference. The abstract state is (part of) the transitively reachable state: that is, the state of the object and all state reachable from it by following references. The type system permits explicitly excluding fields or objects from the abstract state of an object. For a statically type-safe language, the type system guarantees reference immutability. If the language is extended with immutability downcasts, then run-time checks enforce the reference immutability constraints.

In order to better understand the usability and efficacy of the type system, we have implemented an extension to Java, called Javari, that includes all the features of our type system. Javari is interoperable with Java and existing JVMs. It can be viewed as a proposal for the semantics of the Java const keyword, though Javari's syntax uses readonly instead. This paper describes the design and implementation of Javari, including the type-checking rules for the language. This paper also discusses experience with 160,000 lines of Javari code. Javari was easy to use and provided a number of benefits, including detecting errors in well-tested code.
Object-oriented encapsulation for dynamically typed languages
Authors: Schärli Nathanael , Black Andrew P. , Ducasse Stéphane
Published: November 2005

Encapsulation in object-oriented languages has traditionally been based on static type systems. As a consequence, dynamically-typed languages have only limited support for encapsulation. This is surprising, considering that encapsulation is one of the most fundamental and important concepts behind object-oriented programming and that it is essential for writing programs that are maintainable and reliable, and that remain robust as they evolve.

In this paper we describe the problems that are caused by insufficient encapsulation mechanisms and then present object-oriented encapsulation, a simple and uniform approach that solves these problems by bringing state of the art encapsulation features to dynamically typed languages. We provide a detailed discussion of our design rationales and compare them and their consequences to the encapsulation approaches used for statically typed languages. We also describe an implementation of object-oriented encapsulation in Smalltalk. Benchmarks of this implementation show that extensive use of object-oriented encapsulation results in a slowdown of less than 15 percent.
Finding your cronies
Authors: Guyer Samuel Z. , McKinley Kathryn S.
Published: November 2005

This paper introduces dynamic object colocation, an optimization to reduce copying costs in generational and other incremental garbage collectors by allocating connected objects together in the same space. Previous work indicates that connected objects belong together because they often have similar lifetimes. Generational collectors, however, allocate all new objects in a nursery space. If these objects are connected to data structures residing in the mature space, the collector must copy them. Our solution is a cooperative optimization that exploits compiler analysis to make runtime allocation decisions. The compiler analysis discovers potential object connectivity for newly allocated objects. It then replaces these allocations with calls to coalloc, which takes an extra parameter called the colocator object. At runtime, coalloc determines the location of the colocator and allocates the new object together with it in either the nursery or mature space. Unlike pretenuring, colocation makes precise per-object allocation decisions and does not require lifetime analysis or allocation site homogeneity. Experimental results for SPEC Java benchmarks using Jikes RVM show colocation can reduce garbage collection time by 50% to 75%, and total performance by up to 1%.
Programming with transactional coherence and consistency (TCC)
Authors: Hammond Lance , Carlstrom Brian D. , Wong Vicky , Hertzberg Ben , Chen Mike , Kozyrakis Christos , Olukotun Kunle
Published: November 2005

Transactional Coherence and Consistency (TCC) offers a way to simplify parallel programming by executing all code within transactions. In TCC systems, transactions serve as the fundamental unit of parallel work, communication and coherence. As each transaction completes, it writes all of its newly produced state to shared memory atomically, while restarting other processors that have speculatively read stale data. With this mechanism, a TCC-based system automatically handles data synchronization correctly, without programmer intervention. To gain the benefits of TCC, programs must be decomposed into transactions. We describe two basic programming language constructs for decomposing programs into transactions, a loop conversion syntax and a general transaction-forking mechanism. With these constructs, writing correct parallel programs requires only small, incremental changes to correct sequential programs. The performance of these programs may then easily be optimized, based on feedback from real program execution, using a few simple techniques.
Deconstructing storage arrays
Authors: Denehy Timothy E. , Bent John , Popovici Florentina I. , Arpaci-Dusseau Andrea C. , Arpaci-Dusseau Remzi H.
Published: November 2005

We introduce Shear, a user-level software tool that characterizes RAID storage arrays. Shear employs a set of controlled algorithms combined with statistical techniques to automatically determine the important properties of a RAID system, including the number of disks, chunk size, level of redundancy, and layout scheme. We illustrate the correctness of Shear by running it upon numerous simulated configurations, and then verify its real-world applicability by running Shear on both software-based and hardware-based RAID systems. Finally, we demonstrate the utility of Shear through three case studies. First, we show how Shear can be used in a storage management environment to verify RAID construction and detect failures. Second, we demonstrate how Shear can be used to extract detailed characteristics about the individual disks within an array. Third, we show how an operating system can use Shear to automatically tune its storage subsystems to specific RAID configurations.
HIDE
Authors: Zhuang Xiaotong , Zhang Tao , Pande Santosh
Published: November 2005

XOM-based secure processor has recently been introduced as a mechanism to provide copy and tamper resistant execution. XOM provides support for encryption/decryption and integrity checking. However, neither XOM nor any other current approach adequately addresses the problem of information leakage via the address bus. This paper shows that without address bus protection, the XOM model is severely crippled. Two realistic attacks are shown and experiments show that 70% of the code might be cracked and sensitive data might be exposed leading to serious security breaches.Although the problem of address bus leakage has been widely acknowledged both in industry and academia, no practical solution has ever been proposed that can provide an adequate security guarantee. The main reason is that the problem is very difficult to solve in practice due to severe performance degradation which accompanies most of the solutions. This paper presents an infrastructure called HIDE (Hardware-support for leakage-Immune Dynamic Execution) which provides a solution consisting of chunk-level protection with hardware support and a flexible interface which can be orchestrated through the proposed compiler optimization and user specifications that allow utilizing underlying hardware solution more efficiently to provide better security guarantees.Our results show that protecting both data and code with a high level of security guarantee is possible with negligible performance penalty (1.3% slowdown).
HOIST
Authors: Regehr John , Reid Alastair
Published: November 2005

Embedded software must meet conflicting requirements such as be-ing highly reliable, running on resource-constrained platforms, and being developed rapidly. Static program analysis can help meet all of these goals. People developing analyzers for embedded object code face a difficult problem: writing an abstract version of each instruction in the target architecture(s). This is currently done by hand, resulting in abstract operations that are both buggy and im-precise. We have developed Hoist: a novel system that solves these problems by automatically constructing abstract operations using a microprocessor (or simulator) as its own specification. With almost no input from a human, Hoist generates a collection of C func-tions that are ready to be linked into an abstract interpreter. We demonstrate that Hoist generates abstract operations that are cor-rect, having been extensively tested, sufficiently fast, and substan-tially more precise than manually written abstract operations. Hoist is currently limited to eight-bit machines due to costs exponential in the word size of the target architecture. It is essential to be able to analyze software running on these small processors: they are important and ubiquitous, with many embedded and safety-critical systems being based on them.
Helper threads via virtual multithreading on an experimental itanium
®
2 processor-based platform
Authors: Wang Perry H. , Collins Jamison D. , Wang Hong , Kim Dongkeun , Greene Bill , Chan Kai-Ming , Yunus Aamir B. , Sych Terry , Moore Stephen F. , Shen John P.
Published: November 2005

Helper threading is a technology to accelerate a program by exploiting a processor's multithreading capability to run ``assist'' threads. Previous experiments on hyper-threaded processors have demonstrated significant speedups by using helper threads to prefetch hard-to-predict delinquent data accesses. In order to apply this technique to processors that do not have built-in hardware support for multithreading, we introduce virtual multithreading (VMT), a novel form of switch-on-event user-level multithreading, capable of fly-weight multiplexing of event-driven thread executions on a single processor without additional operating system support. The compiler plays a key role in minimizing synchronization cost by judiciously partitioning register usage among the user-level threads. The VMT approach makes it possible to launch dynamic helper thread instances in response to long-latency cache miss events, and to run helper threads in the shadow of cache misses when the main thread would be otherwise stalled.The concept of VMT is prototyped on an Itanium
®
2 processor using features provided by the Processor Abstraction Layer (PAL) firmware mechanism already present in currently shipping processors. On a 4-way MP physical system equipped with VMT-enabled Itanium 2 processors, helper threading via the VMT mechanism can achieve significant performance gains for a diverse set of real-world workloads, ranging from single-threaded workstation benchmarks to heavily multithreaded large scale decision support systems (DSS) using the IBM DB2 Universal Database. We measure a wall-clock speedup of 5.8% to 38.5% for the workstation benchmarks, and 5.0% to 12.7% on various queries in the DSS workload.
Devirtualizable virtual machines enabling general, single-node, online maintenance
Authors: Lowell David E. , Saito Yasushi , Samberg Eileen J.
Published: November 2005

Maintenance is the dominant source of downtime at high availability sites. Unfortunately, the dominant mechanism for reducing this downtime, cluster rolling upgrade, has two shortcomings that have prevented its broad acceptance. First, cluster-style maintenance over many nodes is typically performed a few nodes at a time, mak-ing maintenance slow and often impractical. Second, cluster-style maintenance does not work on single-node systems, despite the fact that their unavailability during maintenance can be painful for organizations. In this paper, we propose a novel technique for online maintenance that uses virtual machines to provide maintenance on single nodes, allowing parallel maintenance over multiple nodes, and online maintenance for standalone servers. We present the Microvisor, our prototype virtual machine system that is custom tailored to the needs of online maintenance. Unlike general purpose virtual machine environments that induce continual 10-20% over-head, the Microvisor virtualizes the hardware only during periods of active maintenance, letting the guest OS run at full speed most of the time. Unlike past attempts at virtual machine optimization, we do not compromise OS transparency. We instead give up generality and tailor our virtual machine system to the minimum needs of online maintenance, eschewing features, such as I/O and memory virtualization, that it does not strictly require. The result is a very thin virtual machine system that induces only 5.6% CPU overhead when virtualizing the hardware, and zero CPU overhead when
devirtualized
. Using the Microvisor, we demonstrate an online OS upgrade on a live, single-node web server, reducing downtime from one hour to less than one minute.
Fingerprinting
Authors: Smolens Jared C. , Gold Brian T. , Kim Jangwoo , Falsafi Babak , Hoe James C. , Nowatzyk Andreas G.
Published: November 2005

Recent studies have suggested that the soft-error rate in microprocessor logic will become a reliability concern by 2010. This paper proposes an efficient error detection technique, called
fingerprinting
, that detects differences in execution across a dual modular redundant (DMR) processor pair. Fingerprinting summarizes a processor's execution history in a hash-based signature; differences between two mirrored processors are exposed by comparing their fingerprints. Fingerprinting tightly bounds detection latency and greatly reduces the interprocessor communication bandwidth required for checking. This paper presents a study that evaluates fingerprinting against a range of current approaches to error detection. The result of this study shows that fingerprinting is the only error detection mechanism that simultaneously allows high-error coverage, low error detection bandwidth, and high I/O performance.
A syntactic approach to eta equality in type theory
Authors: Goguen Healfdene
Published: November 2005

This paper outlines an elementary approach for showing the decidability of type checking for type theories with βη-equality, relevant to foundations for modules systems and type theory-based proof systems. The key to the approach is a syntactic translation mapping terms in the βη presentation into their full η-expansions in the β presentation. Decidability of type checking is lifted from the target β presentation to the βη presentation. The approach extends to other inductive kinds with a single constructor, and is demonstrated for singletons and dependent pairs.
Slot games
Authors: Ghica Dan R.
Published: November 2005

We present a games-based denotational semantics for a quantitative analysis of programming languages. We define a Hyland-Ong-style games framework called
slot games
, which consists of HO games augmented with a new action called token. We develop a slot-game model for the language Idealised Concurrent Algol by instrumenting the strategies in its HO game model with token actions. We show that the slot-game model is a denotational semantics induced by a notion of observation formalised in the operational theory of improvement of Sands, and we give a full abstraction result. A quantitative analysis of programs has many potential applications, from compiler optimisations to resource-constrained execution and static performance profiling. We illustrate several such applications with putative examples that would be nevertheless difficult, if not impossible, to handle using known operational techniques.
Communicating quantum processes
Authors: Gay Simon J. , Nagarajan Rajagopal
Published: November 2005

We define a language CQP (Communicating Quantum Processes) for modelling systems which combine quantum and classical communication and computation. CQP combines the communication primitives of the pi-calculus with primitives for measurement and transformation of quantum state; in particular, quantum bits (qubits) can be transmitted from process to process along communication channels. CQP has a static type system which classifies channels, distinguishes between quantum and classical data, and controls the use of quantum state. We formally define the syntax, operational semantics and type system of CQP, prove that the semantics preserves typing, and prove that typing guarantees that each qubit is owned by a unique process within a system. We illustrate CQP by defining models of several quantum communication systems, and outline our plans for using CQP as the foundation for formal analysis and verification of combined quantum and classical systems.
Downgrading policies and relaxed noninterference
Authors: Li Peng , Zdancewic Steve
Published: November 2005

In traditional information-flow type systems, the security policy is often formalized as noninterference properties. However, noninterference alone is too strong to express security properties useful in practice. If we allow downgrading in such systems, it is challenging to formalize the security policy as an extensional property of the system.This paper presents a generalized framework of downgrading policies. Such policies can be specified in a simple and tractable language and can be statically enforced by mechanisms such as type systems. The security guarantee is then formalized as a concise extensional property using program equivalences. This
relaxed noninterference
generalizes traditional pure noninterference and precisely characterizes the information released due to downgrading.
Mutatis mutandis
Authors: Stoyle Gareth , Hicks Michael , Bierman Gavin , Sewell Peter , Neamtiu Iulian
Published: November 2005

Dynamic software updates can be used to fix bugs or add features to a running program without downtime. Essential for some applications and convenient for others, low-level dynamic updating has been used for many years. Perhaps surprisingly, there is little high-level understanding or language support to help programmers write dynamic updates effectively.To bridge this gap, we present Proteus, a core calculus for dynamic software updating in C-like languages that is flexible, safe, and predictable. Proteus supports dynamic updates to functions (even active ones), to named types and to data, allowing on-line evolution to match source-code evolution as we have observed it in practice. We ensure updates are type-safe by checking for a property we call "con-freeness" for updated types t at the point of update. This means that non-updated code will not use t
concretely
beyond that point (concrete usages are via explicit coercions) and thus t's representation can safely change. We show how con-freeness can be enforced dynamically for a particular program state. We additionally define a novel and efficient static
updateability analysis
to establish con-freeness statically, and can thus automatically infer program points at which all future (well-formed) updates will be type-safe. We have implemented our analysis for C and tested it on several well-known programs.
From sequential programs to multi-tier applications by program transformation
Authors: Neubauer Matthias , Thiemann Peter
Published: November 2005

Modern applications are designed in multiple tiers to separate concerns. Since each tier may run at a separate location, middleware is required to mediate access between tiers. However, introducing this middleware is tiresome and error-prone.We propose a
multi-tier calculus
and a
splitting transformation
to address this problem. The multi-tier calculus serves as a sequential core programming language for constructing a multi-tier application. The application can be developed in the sequential setting. Splitting extracts one process per tier from the sequential program such that their concurrent execution behaves like the original program.The splitting transformation starts from an assignment of primitive operations to tiers. A program analysis determines communication requirements and inserts remote procedure calls. The next transformation step performs resource pooling: it optimizes the communication behavior by transforming sequences of remote procedure calls to a stream-based protocol. The final transformation step splits the resulting program into separate communicating processes.The multi-tier calculus is also applicable to the construction of interactive Web applications. It facilitates their development by providing a uniform programming framework for client-side and server-side programming.
Separation logic and abstraction
Authors: Parkinson Matthew , Bierman Gavin
Published: November 2005

In this paper we address the problem of writing specifications for programs that use various forms of modularity, including procedures and Java-like classes. We build on the formalism of separation logic and introduce the new notion of an
abstract predicate
and, more generally, abstract predicate families. This provides a flexible mechanism for reasoning about the different forms of abstraction found in modern programming languages, such as abstract datatypes and objects. As well as demonstrating the soundness of our proof system, we illustrate its utility with a series of examples.
A semantics for procedure local heaps and its abstractions
Authors: Rinetzky Noam , Bauer Jörg , Reps Thomas , Sagiv Mooly , Wilhelm Reinhard
Published: November 2005

The goal of this work is to develop compile-time algorithms for automatically verifying properties of imperative programs that manipulate dynamically allocated storage. The paper presents an analysis method that uses a characterization of a procedure's behavior in which parts of the heap not relevant to the procedure are ignored. The paper has two main parts: The first part introduces a non-standard concrete semantics,
LSL
, in which called procedures are only passed
parts
of the heap. In this semantics, objects are treated specially when they separate the "local heap" that can be mutated by a procedure from the rest of the heap, which---from the viewpoint of that procedure---is non-accessible and immutable. The second part concerns abstract interpretation of
LSL
and develops a new static-analysis algorithm using canonical abstraction.
Tina
Authors: Frenger Paul
Published: November 2005

The twenty-first century is rapidly becoming the age of nanotechnology. Everything seems to be getting smaller these days, especially in the electronic and scientific fields. The fuel-efficient Mazda Miata and Toyota MR2 have become the city commuter's must-have vehicles. The bulky boom-box has been replaced by the more socially responsible Apple iPod, with its miniscule rotating hard disk drive. The familiar 5-inch CD is being replaced by 3-inch versions, with smaller ones on the horizon. The playing-card sized (86 by 54 mm) PCMCIA storage device has been supplanted by fingernail-sized (10 by 15 mm) TransFlash memory cards [1]. This miniaturizing effect feeds upon itself as smaller products require even smaller components of every description, fueling the demand for yet tinier devices.
An efficient and reliable object-oriented exception handling mechanism
Authors: Jiang Shujuan , Xu Baowen
Published: November 2005

This paper proposes an exception handling mechanism for developing reliable object-oriented systems based on analyzing some problems encountered in the C++ programming language. The exceptions are organized into a knowledge sharing inheritance hierarchy and the handlers can be defined within exception classes. This enables the information to be hidden. The separation between the normal codes and the exception handling codes makes the program neat and maintainable. It supports both the termination and the retry model. Binding the exception to the object responsible for its raise can solve the issue of matching the handler relying on only the exception type.
Requirements for a real-time .NET framework
Authors: Zerzelidis A. , Wellings A. J.
Published: November 2005

The Microsoft .NET Framework is a comparatively new technology that has already gained considerable momentum. Its user base and popularity is expanding. In addition, it offers a number of important traits, such as code portability and cross-language development. It is these features that have attracted our attention into investigating the possibility of using .NET for architecture -neutral real-time systems. As a result, this paper tries to set the groundwork for implementing a real-time version of the Microsoft .NET Framework by specifying a set of requirements.
Granule-oriented programming
Authors: Zhao Yinliang
Published: November 2005

A program will become obsolete or less effective in solving domain problems due to many reasons. One of the main reasons can be the fact that the program does not fit its context. The context of a program is defined as a collection of functionalities that support the program to solve domain problems, e.g., runtime environmental supports, meta-strategies, architectural supports, etc. Unfitness phenomena exist in many software systems, which lead the systems prematurely end their life cycles, or decrease their performance and accuracy in solving problems. In existing programming systems, from the perspective of language expressivity, little attention has been paid to this unfitness problem. Granule-oriented programming is an evolutionary metaphor in which programs are ground into code granules in order to localize their unfitness parts as explicitly as possible and then the code granules are compounded into the target program, in which a code granulation space, ont to express program in a well-formed and multi-layered framework, is formed. In this paper, we propose and briefly describe the notion of granule-oriented programming.
Minimizing memory requirement of real-time systems with concurrent garbage collector
Authors: Xian Yuqiang , Xiong Guangze
Published: November 2005

Garbage collection is a key feature in modern programming languages like Java™. But it also brings some obstacles to real-time issues. Previous work had been put on solving the real-time problems of the garbage collector. Among it there are concurrent collectors that can provide truly real-time guarantees but they rely on a relatively large amount of redundant system memory. This paper concentrates on minimizing the system memory requirement with a new concurrent garbage collector which is based on a deferrable server together with a particular parameter configuration scheme proposed by this paper. The parameter configuration scheme is addressed using two different approaches, that is, the utilization based analysis and exact analysis of the selection of parameters. In this way, the worst-case response time of a garbage collector is minimized, and so is the worst-case system memory requirement, with the schedulability of tasks with hard time constraint not jeopardized. Furthermore, the simulation results demonstrate that, based on the new algorithm, the actual maximum system memory requirement for a given task set also becomes less than that of any previous concurrent collector.
Extracting grammar from programs
Authors: Črepinšek Matej , Mernik Marjan , Žumer Viljem
Published: November 2005

Extracting grammar from programs attracts researchers from several fields such as software engineering, pattern recognition, computational linguistic and natural language acquisition. So far, only regular grammar induction has been successful, while purposeful context-free grammar induction is still elusive. We discuss the search space of context-free grammar induction and propose the Brute Force approach to the problem which, along with its various enhancements, can be further used in collaboration with the Evolutionary approach, as described in the accompanying paper.
A serializability violation detector for shared-memory server programs
Authors: Xu Min , Bodík Rastislav , Hill Mark D.
Published: November 2005

We aim to improve reliability of multithreaded programs by proposing a dynamic detector that detects potentially erroneous program executions and their causes. We design and evaluate a
Serializability Violation Detector
(SVD) that has two unique goals: (I) triggering automatic recovery from erroneous executions using backward error recovery (BER), or simply alerting users that a software error may have occurred; and (II) helping debug programs by revealing causes of error symptoms.Two properties of SVD help in achieving these goals. First, to detect only erroneous executions, SVD checks serializability of atomic regions, which are code regions that need to be executed atomically. Second, to improve usability, SVD does not require
a priori
annotations of atomic regions; instead, SVD approximates them using a heuristic. Experimental results on three widely-used multithreaded server programs show that SVD finds real bugs and reports modest false positives. The goal of this paper is to develop a detector suitable for (I) BER-based avoidance of erroneous program executions; and (II) alerting users as software errors occur. We argue that such a detector should have the following two properties.
Checking type safety of foreign function calls
Authors: Furr Michael , Foster Jeffrey S.
Published: November 2005

We present a multi-lingual type inference system for checking type safety across a foreign function interface. The goal of our system is to prevent foreign function calls from introducing type and memory safety violations into an otherwise safe language. Our system targets OCaml's FFI to C, which is relatively lightweight and illustrates some interesting challenges in multi-lingual type inference. The type language in our system embeds OCaml types in C types and vice-versa, which allows us to track type information accurately even through the foreign language, where the original types are lost. Our system uses
representational
types that can model multiple OCaml types, because C programs can observe that many OCaml types have the same physical representation. Furthermore, because C has a low-level view of OCaml data, our inference system includes a dataflow analysis to track memory offsets and tag information. Finally, our type system includes garbage collection information to ensure that pointers from the FFI to the OCaml heap are tracked properly. We have implemented our inference system and applied it to a small set of benchmarks. Our results show that programmers do misuse these interfaces, and our implementation has found several bugs and questionable coding practices in our benchmarks.
Automatic pool allocation
Authors: Lattner Chris , Adve Vikram
Published: November 2005

This paper describes
Automatic Pool Allocation
, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of benchmarks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.
Differential register allocation
Authors: Zhuang Xiaotong , Pande Santosh
Published: November 2005

Micro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor pipeline. Especially for low-end processors, encoding space could be extremely limited due to area and power considerations. On the other hand, the number of architected registers exposed to the compiler could directly affect the effectiveness of compiler analysis and optimization. For high performance computers, register pressure can be higher than the available registers in some regions, e.g. due to optimizations like aggressive function inlining, software pipelining etc. The compiler cannot effectively perform compilation and optimization if only a small number of registers are exposed through the ISA. Therefore, it is crucial that more architected registers are available at the compiler's disposal without expanding the code size significantly.In this paper, we look at a new register encoding scheme called differential encoding that allows more registers to be addressed in the operand field of instructions than the direct encoding currently being used. We show it can be implemented with very low overhead. Based upon differential encoding, we apply it in several ways such that the extra architected registers can benefit the performance. Three schemes are devised to integrate differential encoding with register allocation. We demonstrate that differential register allocation is helpful in improving the performance of both high-end and low-end processors. Moreover, We can combine it with software pipelining to provide more registers and reduce spills.Our results show that differential encoding significantly reduces the number of spills and speeds up program execution. For a low-end configuration, we achieve over 12% speedup while keeping code size almost unaffected. For optimization on loops, it significantly speeds up loops with high register pressure (over 70% speedup).
Automatically partitioning packet processing applications for pipelined architectures
Authors: Dai Jinquan , Huang Bo , Li Long , Harrison Luddy
Published: November 2005

Modern network processors employs parallel processing engines (PEs) to keep up with explosive internet packet processing demands. Most network processors further allow processing engines to be organized in a pipelined fashion to enable higher processing throughput and flexibility. In this paper, we present a novel program transformation technique to exploit parallel and pipelined computing power of modern network processors. Our proposed method automatically partitions a sequential packet processing application into coordinated pipelined parallel subtasks which can be naturally mapped to contemporary high-performance network processors. Our transformation technique ensures that packet processing tasks are balanced among pipeline stages and that data transmission between pipeline stages is minimized. We have implemented the proposed transformation method in an auto-partitioning C compiler product for Intel Network Processors. Experimental results show that our method provides impressive speed up for the commonly used NPF IPv4 forwarding and IP forwarding benchmarks. For a 9-stage pipeline, our auto-partitioning C compiler obtained more than 4X speedup for the IPv4 forwarding PPS and the IP forwarding PPS (for both the IPv4 traffic and IPv6 traffic).
Programming ad-hoc networks of mobile and resource-constrained devices
Authors: Ni Yang , Kremer Ulrich , Stere Adrian , Iftode Liviu
Published: November 2005

Ad-hoc networks of mobile devices such as smart phones and PDAs represent a new and exciting distributed system architecture. Building distributed applications on such an architecture poses new design challenges in programming models, languages, compilers, and runtime systems. This paper discusses SpatialViews, a high-level language designed for programming mobile devices connected through a wireless ad-hoc network. SpatialViews allows specification of virtual networks with nodes providing desired services and residing in interesting spaces. These nodes are discovered dynamically with user-specified time constraints and quality of result (QoR). The programming model supports "best-effort" semantics, i.e., different executions of the same program may result in "correct" answers of different quality. It is the responsibility of the compiler and runtime system to produce a high-quality answer for the particular network and resource conditions encountered during program execution. Four applications, which exercise different features of the SpatialViews language, are presented to demonstrate the expressiveness of the language and the efficiency of the compiler generated code. The applications are an application that collects and aggregates sensor data in network, an application that performs dynamic service installation, a mobile camera application that supports computation offloading for image understanding, and an augmented-reality (AR) Pacman game. The efficiency of the compiler generated code is verified through simulation and physical measurements. The reported results show that SpatialViews is an expressive and effective language for ad-hoc networks. In addition, compiler optimizations can significantly improve response times and energy consumption.