bluuebunny/crossref_metadata_2025 huggingface dataset:
Interfaces for strongly-typed object-oriented programming
Authors: Canning P. S. , Cook W. R. , Hill W. L. , Olthoff W. G.
Published: November 2005

This paper develops a system of explicit interfaces for object-oriented programming. The system provides the benefits of module interfaces found in languages like Ada and Modula-2 while preserving the expressiveness that gives untyped object-oriented languages like Smalltalk their flexibility. Interfaces are interpreted as polymorphic types to make the system sufficiently powerful. We use interfaces to analyze the properties of inheritance, and identify three distinct kinds of inheritance in object-oriented programming, corresponding to objects, classes, and interfaces, respectively. Object interfaces clarify the distinction between interface containment and inheritance and give insight into limitations caused by equating the notions of type and class in many typed object-oriented programming languages. Interfaces also have practical consequences for design, specification, and maintenance of object-oriented systems.
Automated discovery of scoped memory regions for real-time Java
Authors: Deters Morgan , Cytron Ron K.
Published: November 2005

Advances in operating systems and languages have brought the ideal of reasonably-bounded execution time closer to developers who need such assurances for real-time and embedded systems applications. Recently, extensions to the Java libraries and virtual machine have been proposed in an emerging standard, which provides for specification of release times, execution costs, and deadlines for a restricted class of threads. To use such features, the code executing in the thread must never reference storage that could be subject to garbage collection. The new standard provides for region-like, stack-allocated areas (scopes) of storage that are ignored by garbage collection and deallocated
en masse
. It now falls to the developer to adapt ordinary Java code to use the real-time Java scoped memory regions.Unfortunately, it is difficult to determine manually how to map object instantiations to scopes. Moreover, if ordinary Java code is modified to effect instantiations in scopes, the resulting code is difficult to read, maintain, and reuse. Static analysis can yield scopes that are correct across all program executions, but such analysis is necessarily conservative in nature. If too many objects appear to live forever under such analysis, then developers cannot rely on static analysis alone to form reasonable scopes.In this paper we present an approach for automatically determining appropriate storage scopes for Java objects, based on dynamic analysis---observed object lifetimes and object referencing behavior. While such analysis is perhaps unsafe across all program executions, our analysis can be coupled with static analysis to bracket object lifetimes, with the truth lying somewhere in between. We provide experimental results that show the memory regions discovered by our technique.
Accurate garbage collection in an uncooperative environment
Authors: Henderson Fergus
Published: November 2005

Previous attempts at garbage collection in uncooperative environments have generally used conservative or mostly-conservative approaches. We describe a technique for doing fully type-accurate garbage collection in an uncooperative environment, using a "shadow stack" to link structs of pointer-containing variables, together with the data or code needed to trace them. We have implemented this in the Mercury compiler, which generates C code, and present preliminary performance data on the overheads of this technique. We also show how this technique can be extended to handle multithreaded applications.
Software caching vs. prefetching
Authors: Aggarwal Aneesh
Published: November 2005

The performance gap between memory subsystem and high-performance processors is ever-increasing. Prefetching is one method to bridge this performance gap. Prefetching has been proposed for array-based and pointer applications, typically using software-based techniques with the help of the compiler. Prefetching suffers from certain disadvantages such as an increase in memory traffic, an increase in the number of executed instructions, and an increase in memory requirement for some cases.In this paper, we investigate the technique of software caching for applications that perform searches or sorted insertions. For data structures larger than the processor data cache, such a search or sorted insert may result in multiple cache misses before the correct value is found. In a software caching approach, a small software buffer is maintained that records the most recently added values (these values are the ones that are later searched) along with their addresses and is consulted during a search or an insert. In this paper, we present results of our initial experiments. We found that for applications involving a search, software caching performs as high as 30% better than the original application. Also, this technique executes upto 14% less instructions and the number of cache accesses decrease by around upto 18%. We also compared this technique against software prefetching and found that in some cases, the performance improvement was as high as 40%. This technique also has an added advantage of using less memory space than prefetching (all the improvements were obtained for very small software caches). These initial results encourage a more in-depth study of this technique.
Mostly lock-free malloc
Authors: Dice Dave , Garthwaite Alex
Published: November 2005

Modern multithreaded applications, such as application servers and database engines, can severely stress the performance of user-level memory allocators like the ubiquitous malloc subsystem. Such allocators can prove to be a major scalability impediment for the applications that use them, particularly for applications with large numbers of threads running on high-order multiprocessor systems.This paper introduces Multi-Processor Restartable Critical Sections, or MP-RCS. MP-RCS permits user-level threads to know precisely which processor they are executing on and then to safely manipulate CPU-specific data, such as malloc metadata, without locks or atomic instructions. MP-RCS avoids interference by using upcalls to notify user-level threads when preemption or migration has occurred. The upcall will abort and restart any interrupted critical sections.We use MP-RCS to implement a malloc package, LFMalloc (Lock-Free Malloc). LFMalloc is scalable, has extremely low latency, excellent cache characteristics, and is memory efficient. We present data from some existing benchmarks showing that LFMalloc is often 10 times faster than Hoard, another malloc replacement package.
In or out?
Authors: Blackburn Stephen M , McKinley Kathryn S.
Published: November 2005

In many garbage collected systems, the mutator performs a write barrier for every pointer update. Using generational garbage collectors, we study in depth three code placement options for remembered-set write barriers: inlined, out-of-line, and partially inlined (fast path inlined, slow path out-of-line). The fast path determines if the collector needs to remember thepointer update. The slow path records the pointer in a list when necessary. Efficient implementations minimize the instructions on the fast path, and record few pointers (from 0.16 to 3% of pointer stores in our benchmarks). We find the mutator performs best with a partially inlined barrier, by a modest 1.5% on average over full inlining.We also study the compilation cost of write-barrier code placement. We find that partial inlining reduces the compilation cost by 20 to 25% compared to full inlining. In the context of just-in-time compilation, the application is exposed to compiler activity. Regardless of the level of compiler activity, partial inlining consistently gives a total running time performance advantage over full inlining on the benchmarks. When the compiler optimizes all application methods on demand and compiler load is highest, partial inlining improves total performance on average by 10.2%, and up to 18.5%.
Compiler-directed run-time monitoring of program data access
Authors: Ding Chen , Zhong Yutao
Published: November 2005

Accurate run-time analysis has been expensive for complex programs, in part because most methods perform on all a data. Some applications require only partial reorganization. An example of this is off-loading infrequently used data from a mobile device. Complete monitoring is not necessary because not all accesses can reach the displaced data. To support partial monitoring, this paper presents a framework that includes a source-to-source C compiler and a run-time monitor. The compiler inserts run-time calls, which invoke the monitor during execution. To be selective, the compiler needs to identify relevant data and their access. It needs to analyze both the content and the location of monitored data. To reduce run-time overhead, the system uses a source-level interface, where the compiler transfers additional program information to reduce the workload of the monitor. The paper describes an implementation for general C programs. It evaluates different levels of data monitoring and their application on an SGI workstation and an Intel PC.
An efficient static analysis algorithm to detect redundant memory operations
Authors: Cooper Keith D. , Xu Li
Published: November 2005

As memory system performance becomes an increasingly dominant factor in overall system performance, it is important to optimize programs for memory related operations. This paper concerns static analysis to detect redundant memory operations and enable other compiler transformations to remove such redundant operations.We present an extended global value numbering algorithm to detect redundant memory operations. The key of the new algorithm is a novel SSA-based representation for memory state which allows accurate reasoning about memory state. Using this representation, the algorithm can trace values through memory operations to detect equivalence in the same way that it traces them through register-based scalar operations. Thus it discovers both redundancy involving scalar values and redundancy involving memory operations. The redundancy relation detected by the algorithm can then be used by traditional redundancy elimination transformations to remove those redundant operations.Experiments using a suite of realistic applications demonstrate the algorithm is powerful and fast. In practice, it has essentially linear time complexity.
Separate compilation for Standard ML
Authors: Appel Andrew W. , MacQueen David B.
Published: November 2005

Languages that support abstraction and modular structure, such as Standard ML, Modula, Ada, and (more or less) C++, may have deeply nested dependency hierarchies among source files. In ML the problem is particularly severe because ML's powerful parameterized module (functor) facility entails dependencies among implementation modules, not just among interfaces.

To efficiently compile individual modules in such languages, it is useful (in ML, necessary) to infer, digest, and cache the static environment resulting from the compilation of each module.

Our system provides a simple model of compilation and linkage that supports incremental recompilation (a restricted form of separate compilation) with type-safe linkage. This model is made available to user programs in the form of a set of internal compiler modules, a feature that we call the “visible compiler”. The chief client of this interface is the IRM incremental recompilation manager from CMU.
Lazy functional state threads
Authors: Launchbury John , Peyton Jones Simon L.
Published: November 2005

Some algorithms make critical internal use of updatable state, even though their external specification is purely functional. Based on earlier work on monads, we present a way of securely encapsulating stateful computations that manipulate multiple, named, mutable objects, in the context of a non-strict, purely-functional language.

The security of the encapsulation is assured by the type system, using parametricity. Intriguingly, this parametricity requires the provision of a (single) constant with a rank-2 polymorphic type.
Precise compile-time performance prediction for superscalar-based computers
Authors: Wang Ko-Yang
Published: November 2005

Optimizing compilers (particularly parallel compilers) are constrained by their ability to predict performance consequences of the transformations they apply. Many factors, such as unknowns in control structures, dynamic behavior of programs, and complexity of the underlying hardware, make it very difficult for compilers to estimate the performance of the transformations accurately and efficiently. In this paper, we present a performance prediction framework that combines several innovative approaches to solve this problem. First, the framework employs a detailed, architecture-specific, but portable, cost model that can be used to estimate the cost of straight line code efficiently. Second, aggregated costs of loops and conditional statements are computed and represented symbolically. This avoids unnecessary, premature guesses and preserves the precision of the prediction. Third, symbolic comparison allows compilers to choose the best transformation dynamically and systematically. Some methodologies for applying the framework to optimizing parallel compilers to support automatic, performance-guided program restructuring are discussed.
Accurate static estimators for program optimization
Authors: Wagner Tim A. , Maverick Vance , Graham Susan L. , Harrison Michael A.
Published: November 2005

Determining the relative execution frequency of program regions is essential for many important optimization techniques, including register allocation, function inlining, and instruction scheduling. Estimates derived from profiling with sample inputs are generally regarded as the most accurate source of this information; static (compile-time) estimates are considered to be distinctly inferior. If static estimates were shown to be competitive, however, their convenience would outweigh minor gains from profiling, and they would provide a sound basis for optimization when profiling is impossible.

We use quantitative metrics to compare estimates from static analysis to those derived from profiles. For C programs, simple techniques for predicting branches and loop counts suffice to estimate intraprocedural frequency patterns with high accuracy. To determine inter-procedural estimates successfully, we combine function-level information with a Markov model of control flow over the call graph to produce arc and basic block frequency estimates for the entire program.

For a suite of 14 programs, including the C programs from the SPEC92 benchmark suite, we demonstrate that static estimates are competitive with those derived from profiles. Using simple heuristics, we can determine the most frequently executed blocks in each function with 81% accuracy. With the Markov model, we identify 80% of the frequently called functions. Combining the two techniques, we identify 76% of the most frequently executed call sites.
Improving semi-static branch prediction by code replication
Authors: Krall Andreas
Published: November 2005

Speculative execution on superscalar processors demands substantially better branch prediction than what has been previously available. In this paper we present code replication techniques that improve the accuracy of semi-static branch prediction to a level comparable to dynamic branch prediction schemes. Our technique uses profiling to collect information about the correlation between different branches and about the correlation between the subsequent outcomes of a single branch. Using this information and code replication the outcome of branches is represented in the program state. Our experiments have shown that the misprediction rate can almost be halved while the code size is increased by one third.
Parallelizing complex scans and reductions
Authors: Fisher Allan L. , Ghuloum Anwar M.
Published: November 2005

We present a method for automatically extracting parallel prefix programs from sequential loops, even in the presence of complicated conditional statements. Rather than searching for associative operators in the loop body directly, the method rests on the observation that functional composition itself is associative. Accordingly, we model the loop body as a multivalued function of multiple parameters, and look for a closed-form representation of arbitrary compositions of loop body instances. Careful analysis of conditionals allows this search to succeed in cases where existing automatic methods fail. The method has been implemented and used to generate code for the iWarp parallel computer.
Partial dead code elimination
Authors: Knoop Jens , Rüthing Oliver , Steffen Bernhard
Published: November 2005

A new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. Besides being more powerful than the usual approaches to dead code elimination, this algorithm is
optimal
in the following sense: partially dead code remaining in the resulting program cannot be eliminated without changing the branching structure or the semantics of the program, or without impairing some program executions.

Our approach is based on techniques for partial redundancy elimination. Besides some new technical problems there is a significant difference here: partial dead code elimination introduces second order effects, which we overcome by means of exhaustive motion and elimination steps. The optimality and the uniqueness of the program obtained is proved by means of a new technique which is universally applicable and particularly useful in the case of mutually interdependent program optimizations.
Interprocedural may-alias analysis for pointers
Authors: Deutsch Alain
Published: November 2005

Existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques:
k-limiting
, and
store-based
(or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. Although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by Jones and Muchnick a decade ago. As a result, optimizing, verifying and parallelizing programs with pointers has remained difficult.

We present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. The key idea is to represent alias information by pairs of
symbolic access paths
which are qualified by symbolic descriptions of the positions for which the alias pair holds.

Based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [CWZ90, He90, LR92, CBC93].
Register allocation over the program dependence graph
Authors: Norris Cindy , Pollock Lori L.
Published: November 2005

This paper describes RAP, a Register Allocator that allocates registers over the Program Dependence Graph (PDG) representation of a program in a hierarchical manner. The PDG program representation has been used successfully for scalar optimizations, the detection and improvement of parallelism for vector machines, multiple processor machines, and machines that exhibit instruction level parallelism, as well as debugging, the integration of different versions of a program, and translation of imperative programs for data flow machines. By basing register allocation on the PDG, the register allocation phase may be more easily integrated and intertwined with other optimization analyses and transformations. In addition, the advantages of a hierarchical approach to global register allocation can be attained without constructing an additional structure used solely for register allocation. Our experimental results have shown that on average, code allocated registers via RAP executed 2.7% faster than code allocated registers via a standard global register allocator.
On slicing programs with jump statements
Authors: Agrawal Hiralal
Published: November 2005

Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms were proposed recently to alleviate this problem. Both require the flowgraph and the program dependence graph of the program to be modified. In this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. We also show that this algorithm permits an extremely efficient, conservative adaptation for use with programs that contain only “structured” jump statements.
Backtracking without trailing in CLP (R

Lin

)
Authors: Van Hentenryck Pascal , Ramachandran Viswanath
Published: November 2005

Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondeterminism (approximated by backtracking) makes these languages appealing for a variety of combinatorial search problems. Existing CLP languages support backtracking by generalizing traditional Prolog implementations: modifications to the constraint system are trailed and restored on backtracking. Although simple and efficient, trailing may be very demanding in memory space, since the constraint system may potentially be saved at each choice point. This paper proposes a fundamentally new implementation scheme for backtracking in CLP languages over linear (rational or real) arithmetic. The new scheme, called
semantic backtracking
, does not use trailing but rather exploits the semantics of the constraints to undo the effect of newly added constraints. Semantic backtracking reduces the space complexity by an order of magnitude compared to implementations based on trailing and makes space complexity essentially independent of the number of choice points. In addition, semantic backtracking introduces negligible space and time overhead on deterministic programs. The price for this improvement is an increase in backtracking time, although constraint-solving time may actually decrease. The scheme has been implemented as part of a complete CLP system CLP(R

Lin

) and compared analytically and experimentally with an optimized trailing implementation. Experimental results indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small.
Finding effective optimization phase sequences
Authors: Kulkarni Prasad , Zhao Wankang , Moon Hwashin , Cho Kyunghwan , Whalley David , Davidson Jack , Bailey Mark , Paek Yunheung , Gallivan Kyle
Published: November 2005

It has long been known that a single ordering of optimization phases will not produce the best code for every application. This phase ordering problem can be more severe when generating code for embedded systems due to the need to meet conflicting constraints on time, code size, and power consumption. Given that many embedded application developers are willing to spend time tuning an application, we believe a viable approach is to allow the developer to steer the process of optimizing a function. In this paper, we describe support in VISTA, an interactive compilation system, for finding effective sequences of optimization phases. VISTA provides the user with dynamic and static performance information that can be used during an interactive compilation session to gauge the progress of improving the code. In addition, VISTA provides support for automatically using performance information to select the best optimization sequence among several attempted. One such feature is the use of a genetic algorithm to search for the most efficient sequence based on specified fitness criteria. We have included a number of experimental results that evaluate the effectiveness of using a genetic algorithm in VISTA to find effective optimization phase sequences.
Efficient memory-reference checks for real-time java
Authors: Corsaro Angelo , Cytron Ron K.
Published: November 2005

The scoped-memory feature is central to the Real-Time Specification for Java. It allows greater control over memory management, in particular the deallocation of objects without the use of a garbage collector. To preserve the safety of storage references associated with Java since its inception, the use of scoped memory is constrained by a set of rules in the specification. While a program's adherence to the rules can be partially checked at compile-time, undecidability issues imply that some---perhaps, many---checks may be required at run-time. Poor implementations of those run-time checks could adversely affect overall performance and predictability, the latter being a founding principle of the specification.In this paper we present efficient algorithms for managing scoped memories and the checks they impose on programs. Implementations and results published to date require time linear in the depth of scope nesting; our algorithms operate in constant time. We describe our approach and present experiments quantifying the gains in efficiency.
Memory safety without runtime checks or garbage collection
Authors: Dhurjati Dinakar , Kowshik Sumant , Adve Vikram , Lattner Chris
Published: November 2005

Traditional approaches to enforcing memory safety of programs rely heavily on runtime checks of memory accesses and on garbage collection, both of which are unattractive for embedded applications. The long-term goal of our work is to enable 100% static enforcement of memory safety for embedded programs through advanced compiler techniques and minimal semantic restrictions on programs. The key result of this paper is a compiler technique that ensures memory safety of dynamically allocated memory without programmer annotations, runtime checks, or garbage collection, and works for a large subclass of type-safe C programs. The technique is based on a fully automatic pool allocation (i.e., region-inference) algorithm for C programs we developed previously, and it ensures safety of dynamically allocated memory while retaining explicit deallocation of individual objects within regions (to avoid garbage collection). For a diverse set of embedded C programs (and using a previous technique to avoid null pointer checks), we show that we are able to statically ensure the safety of pointer and dynamic memory usage in all these programs. We also describe some improvements over our previous work in static checking of array accesses. Overall, we achieve 100% static enforcement of memory safety without new language syntax for a significant subclass of embedded C programs, and the subclass is much broader if array bounds checks are ignored. Overall, these techniques greatly expand the class of embedded programs for which 100% static enforcement of memory safety is possible, and furthermore can be achieved without new language support.
Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java
Authors: Bacon David F. , Cheng Perry , Rajan V. T.
Published: November 2005

Now that the use of garbage collection in languages like Java is becoming widely accepted due to the safety and software engineering benefits it provides, there is significant interest in applying garbage collection to hard real-time systems. Past approaches have generally suffered from one of two major flaws: either they were not provably real-time, or they imposed large space overheads to meet the real-time bounds.Our previous work [3] presented the Metronome, a mostly non-copying real-time collector. The Metronome achieves worst-case pause times of 6 milliseconds while maintaining consistent mutator CPU utilization rates of 50% with only 1.5-2.1 times the maximum heap space required by the application, which is comparable with space requirements for stop-the-world collectors.However, that algorithm assumed a constant collection rate, ignored program-dependent characteristics, and lacked a precise specification for when to trigger collection or how much defragmentation to perform. This paper refines the model by taking into account program properties such as pointer density, average object size, and locality of object size. This allows us to bound both the time for collection and consequently the space overhead required much more tightly. We show experimentally that most parameters usually are not subject to large variation, indicating that a small number of parameters will be sufficient to predict the time and space requirements accurately.Our previous work also did not present the details of our approach to avoiding and undoing fragmentation. In this paper we present a more detailed analysis of fragmentation than in previous work, and show how our collector is able to bound fragmentation to acceptable limits.
Phased scheduling of stream programs
Authors: Karczmarek Michal , Thies William , Amarasinghe Saman
Published: November 2005

As embedded DSP applications become more complex, it is increasingly important to provide high-level stream abstractions that can be compiled without sacrificing efficiency. In this paper, we describe scheduler support for StreamIt, a high-level language for signal processing applications. A StreamIt program consists of a set of autonomous filters that communicate with each other via FIFO queues. As in Synchronous Dataflow (SDF), the input and output rates of each filter are known at compile time. However, unlike SDF, the stream graph is represented using hierarchical structures, each of which has a single input and a single output.We describe a scheduling algorithm that leverages the structure of StreamIt to provide a flexible tradeoff between code size and buffer size. The algorithm describes the execution of each hierarchical unit as a set of phases. A complete cycle through the phases represents a single steady-state execution. By varying the granularity of a phase, our algorithm provides a continuum between single appearance schedules and minimum latency schedules. We demonstrate that a minimal latency schedule is effective in decreasing buffer requirements for some applications, while the phased representation mitigates the associated increase in code size.
Schedulability-driven frame packing for multi-cluster distributed embedded systems
Authors: Pop Paul , Eles Petru , Peng Zebo
Published: November 2005

We present an approach to frame packing for multi-cluster distributed embedded systems consisting of time-triggered and event-triggered clusters, interconnected via gateways. In our approach, the application messages are packed into frames such that the application is schedulable. Thus, we have also proposed a schedulability analysis for applications consisting of mixed event-triggered and time-triggered processes and messages, and a worst case queuing delay analysis for the gateways, responsible for routing inter-cluster traffic. Optimization heuristics for frame packing aiming at producing a schedulable system have been proposed. Extensive experiments and a real-life example show the efficiency of our frame-packing approach.
Robustness analysis of avionics embedded systems
Authors: Ait-Ameur Y. , Bel G. , Boniol F. , Pairault S. , Wiels V.
Published: November 2005

Avionics embedded systems are confronted to sensors errors or inaccuracies. It is essential to be able to estimate the impact and the propagation of these errors on the system computed outputs. This paper comes from achieved work in the context of an industrial project in the avionics area. It presents a formal approach allowing to analyse the reaction of a LUSTRE program to inaccurate input values. It uses program analysis techniques like abstract interpretation and interval analysis. The approach has been implemented in Java and applied to parts of a flight control system of the AIRBUS aircrafts.
Time weaver
Authors: de Niz Dionisio , Rajkumar Raj
Published: November 2005

Embedded real-time systems are deployed in a wide range of application domains including transportation systems, automated manufacturing, process control, defense, aerospace, and telecommunications. These systems must satisfy not only logical functional requirements but also
para-functional
properties such as timeliness, Quality of Service (QoS) and reliability. The cross-cutting behaviors imposed by these para-functional properties and dependencies on operational characteristics (e.g. hardware, OS and middleware platforms used) have traditionally led to hard-to-code, hard-to-understand and hard-to-change software. The net result is that productivity improvements in embedded software development have been miniscule compared to improvements in computing and network technologies. We propose a software-through-models framework for the concurrent construction of behavioral models and executable code. Our framework, which can lead to high degrees of cost-effective reuse of embedded software components, decomposes inter-component relationships with an abstraction named
coupler
. This decomposition enables the separation of para-functional aspects into multiple semantic dimensions (e.g. timing, event flow, concurrency, fault-tolerance, deployment) that can be modified independent of one another. The impact of changes in one dimension on the realization of other dimensions is automatically projected and managed. Platform dependencies are also captured separately, enabling a code-generation subsystem to re-use the same components across a wide range of heterogeneous platforms and applications. System components can be recursively composed or decomposed. An analyzable software structure is enforced such that the end-to-end timing behavior of the resulting system can be verified. A visual tool called Time Weaver supports the framework and has been used to model avionics systems, automotive systems and signal processing systems. The software can be downloaded from[4].
From simulink to SCADE/lustre to TTA
Authors: Caspi Paul , Curic Adrian , Maignan Aude , Sofronis Christos , Tripakis Stavros , Niebert Peter
Published: November 2005

We present a layered end-to-end approach for the design and implementation of embedded software on a distributed platform. The approach comprises a high-level modeling and simulation layer (Simulink), a middle-level programming and validation layer (SCADE/Lustre) and a low-level execution layer (TTA). We provide algorithms and tools to pass from one layer to the next. First, a translator from Simulink to Lustre. Second, a set of real-time and code-distribution extensions to Lustre. Third, implementation techniques for decomposing a Lustre program into tasks and messages, scheduling the tasks and messages on the processors and the bus, distributing the Lustre code on the execution platform, and generating the necessary "glue" code.
Tamper-resistant whole program partitioning
Authors: Zhang Tao , Pande Santosh , Valverde Antonio
Published: November 2005

Due to limited available memory (of the order of Kilobytes) on embedded devices (such as smart cards), we undertake an approach of partitioning the whole program when it does not fit in the memory. The program partitions are downloaded from the server on demand into the embedded device just before execution. We devise a method of partitioning the code and data of the program such that no information regarding the control flow behavior of the program is leaked out. This property is called tamper resistance and it is very important for secure embedded devices such as smart cards which could hold sensitive information and/or carry out critical computation such as financial transactions. A preliminary solution to this problem was proposed in our earlier work [1]. This work proposes a new and more comprehensive solution to the problem. First, we propose a new policy which is based on keeping nothing in terms of partitions on the smart card. This policy is unlike the one in previous work which mandated keeping partitions in memory to which control flow was guaranteed to return. Based on this new policy, a new partitioning algorithm is proposed for minimal safe partitions which reduces their memory requirements over previous work. The drawback of this new policy is however lower execution speed due to frequent communication encountered. In order to not significantly degrade performance, we propose caching frequently executed functions on the smart card without violation of tamper resistance. A framework is designed to determine the set of functions to be cached in conjunction with specific minimal safe partitions. Further reduction in memory requirements is achieved due to the data partitioning.The decrease in memory footprint over the previous method is 27% for code memory and 32.4% for data memory on average. The speed-up over the old method is quite significant when applied to whole programs in large benchmarks (500 times on average). The conclusion is that previous method [1] is not suitable as a whole program partitioning strategy whereas the new proposed method is a viable solution.
A DISE implementation of dynamic code decompression
Authors: Corliss Marc L. , Lewis E. Christopher , Roth Amir
Published: November 2005

Code compression coupled with dynamic decompression is an important technique for both embedded and general-purpose microprocessors.
Post-fetch decompression
, in which decompression is performed after the compressed instructions have been fetched, allows the instruction cache to store compressed code but requires a highly efficient decompression implementation. We propose implementing post-fetch decompression using
dynamic instruction stream editing
(DISE), a programmable decoder---similar in structure to those in many IA32 processors---that is used to add functionality to an application by injecting custom code snippets into its fetched instruction stream. A DISE implementation of post-fetch decompression naturally supports customized program-specific decompression dictionaries, enables parameterized decompression allowing similar instruction sequences to share dictionary entries, and uses no decompression-specific hardware. Cycle-level simulation of DISE decompression shows that it can reduce static program size by 35% and execution time by 20%. Parameterized decompression, a feature unique to DISE, accounts for 20% of the code size reduction by making more effective use of the dictionary and allowing PC-relative branches to be included in compressed sequences. DISE-based compression can reduce total energy consumption by 10% and the energy-delay product by as much as 20%.
Enhancing the performance of 16-bit code using augmenting instructions
Authors: Krishnaswamy Arvind , Gupta Rajiv
Published: November 2005

In the embedded domain, memory usage and energy consumption are critical constraints. Dual width instruction set embedded processors such as the ARM provide a 16-bit instruction set in addition to the 32-bit instruction set to address these concerns. Using 16-bit instructions one can achieve code size reduction and I-cache energy savings at the cost of performance. We have observed that throughout 16-bit Thumb code there exist Thumb instruction pairs that are equivalent to a single ARM instruction. We have developed an approach which uses combination of compiler and architectural support to exploit the above property for improving performance of 16-bit code. We enhance the Thumb instruction set by incorporating
Augmenting eXtensions
(AX). The task of the compiler is to identify pairs of Thumb instructions that can be safely combined and executed as single ARM instructions. The compiler replaces such pairs of Thumb instructions by AX+Thumb instruction pairs. The AX instruction is coalesced with the immediately following Thumb instruction to generate a single ARM instruction at decode time. Thus, using AX instructions, the compiler can both generate compact 16-bit code and provide hardware with information needed to produce better performing 32-bit code.
Adapting instruction level parallelism for optimizing leakage in VLIW architectures
Authors: Kim H. S. , Vijaykrishnan N. , Kandemir M. , Irwin M. J.
Published: November 2005

Due to ever increasing number of transistors and decreasing threshold voltages, leakage energy consumption is expected to play a decisive role in the next generation circuits. We believe that software support is a must to exploit available leakage control mechanisms. In this paper, we present and evaluate a compiler-oriented leakage optimization strategy based on tuning IPC (instructions ---issued--- per cycle) at a loop-level granularity according to the needs of application. Once a suitable IPC is selected for each loop, our strategy turns off unused or not frequently used integer ALUs to save leakage energy. Our preliminary results indicate that our technique can reduce up to 38% of the functional unit leakage energy across a range of VLIW configurations. Our results also show that our loop based IPC detection strategy gives better energy-delay product than finer-granularity (basic block level) and coarser-granularity (whole application level) IPC detection schemes.
The
nesC
language
Authors: Gay David , Levis Philip , von Behren Robert , Welsh Matt , Brewer Eric , Culler David
Published: November 2005

We present
nesC
, a programming language for networked embedded systems that represent a new design space for application developers. An example of a networked embedded system is a sensor network, which consists of (potentially) thousands of tiny, low-power "motes," each of which execute concurrent, reactive programs that must operate with severe memory and power constraints.nesC's contribution is to support the special needs of this domain by exposing a programming model that incorporates event-driven execution, a flexible concurrency model, and component-oriented application design. Restrictions on the programming model allow the nesC compiler to perform whole-program analyses, including data-race detection (which improves reliability) and aggressive function inlining (which reduces resource consumption).nesC has been used to implement TinyOS, a small operating system for sensor networks, as well as several significant sensor applications. nesC and TinyOS have been adopted by a large number of sensor network research groups, and our experience and evaluation of the language shows that it is effective at supporting the complex, concurrent programming style demanded by this new class of deeply networked systems.
Compile-time dynamic voltage scaling settings
Authors: Xie Fen , Martonosi Margaret , Malik Sharad
Published: November 2005

With power-related concerns becoming dominant aspects of hardware and software design, significant research effort has been devoted towards system power minimization. Among run-time power-management techniques, dynamic voltage scaling (DVS) has emerged as an important approach, with the ability to provide significant power savings. DVS exploits the ability to control the power consumption by varying a processor's supply voltage (V) and clock frequency (f). DVS controls energy by scheduling different parts of the computation to different (V, f) pairs; the goal is to minimize energy while meeting performance needs. Although processors like the Intel XScale and Transmeta Crusoe allow software DVS control, such control has thus far largely been used at the process/task level under operating system control. This is mainly because the energy and time overhead for switching DVS modes is considered too large and difficult to manage within a single program.In this paper we explore the opportunities and limits of compile-time DVS scheduling. We derive an analytical model for the maximum energy savings that can be obtained using DVS given a few known program and processor parameters. We use this model to determine scenarios where energy consumption benefits from compile-time DVS and those where there is no benefit. The model helps us extrapolate the benefits of compile-time DVS into the future as processor parameters change. We then examine how much of these predicted benefits can actually be achieved through optimal settings of DVS modes. This is done by extending the existing Mixed-integer Linear Program (MILP) formulation for this problem by accurately accounting for DVS energy switching overhead, by providing finer-grained control on settings and by considering multiple data categories in the optimization. Overall, this research provides a comprehensive view of compile-time DVS management, providing both practical techniques for its immediate deployment as well theoretical bounds for use into the future.
Automatically proving the correctness of compiler optimizations
Authors: Lerner Sorin , Millstein Todd , Chambers Craig
Published: November 2005

We describe a technique for automatically proving compiler optimizations
sound
, meaning that their transformations are always semantics-preserving. We first present a domain-specific language, called Cobalt, for implementing optimizations as guarded rewrite rules. Cobalt optimizations operate over a C-like intermediate representation including unstructured control flow, pointers to local variables and dynamically allocated memory, and recursive procedures. Then we describe a technique for automatically proving the soundness of Cobalt optimizations. Our technique requires an automatic theorem prover to discharge a small set of simple, optimization-specific proof obligations for each optimization. We have written a variety of forward and backward intraprocedural dataflow optimizations in Cobalt, including constant propagation and folding, branch folding, full and partial redundancy elimination, full and partial dead assignment elimination, and simple forms of points-to analysis. We implemented our soundness-checking strategy using the Simplify automatic theorem prover, and we have used this implementation to automatically prove our optimizations correct. Our checker found many subtle bugs during the course of developing our optimizations. We also implemented an execution engine for Cobalt optimizations as part of the Whirlwind compiler infrastructure.
Function inlining versus function cloning
Authors: Das Dibyendu
Published: November 2005

Function inlining is a powerful high level optimization which eliminates call cost and increases the chances of other optimizations taking effect due to the breaking down of the call boundaries. Goal-directed function cloning on the other hand strives to create specialized copies of functions to aid interprocedural optimizations. Both of these program transformations create additional code. In the traditional optimizers the problem of choosing which functions to inline is modelled as a 0-1 knapsack problem with a given budget. Function cloning is also treated likewise. However, the usual modelling considers these two as separate knapsack problems with their own respective budgets for code growth. This creates problems as independent budgets can give rise to excessive cloning or inlining and throttling opportunities for one or the other. To circumvent this problem we propose to formulate the inlining and cloning site selection problem as a uni ed multiple-choice knapsack problem. Multiple-choice knapsack is a well-studied problem in the domain of linear programming. In this paper we would look into a greedy algorithm to solve such knapsack problems and its application to the problem at hand.
Experiences in building a compiler for an object-oriented language
Authors: Guimarães José de Oliveira
Published: November 2005

Traditionally books on compiler construction focus on procedural languages leaving some questions on compilation of object-oriented languages unanswered. This article presents some problems found in the building of a compiler for the object-oriented language Green using Java. The solutions used for these problems are exposed and whenever possible alternatives are discussed. We hope to provide programmers with some hints and caveats on compilation of object-oriented languages.