bluuebunny/crossref_metadata_2025 huggingface dataset:
Grammar-based whitebox fuzzing
Authors: Godefroid Patrice , Kiezun Adam , Levin Michael Y.
Published: June 2008

Whitebox fuzzing is a form of automatic dynamic test generation, based on symbolic execution and constraint solving, designed for security testing of large applications. Unfortunately, the current effectiveness of whitebox fuzzing is limited when testing applications with highly-structured inputs, such as compilers and interpreters. These applications process their inputs in stages, such as lexing, parsing and evaluation. Due to the enormous number of control paths in early processing stages, whitebox fuzzing rarely reaches parts of the application beyond those first stages.

In this paper, we study how to enhance whitebox fuzzing of complex structured-input applications with a grammar-based specification of their valid inputs. We present a novel dynamic test generation algorithm where symbolic execution directly generates grammar-based constraints whose satisfiability is checked using a custom grammar-based constraint solver. We have implemented this algorithm and evaluated it on a large security-critical application, the JavaScript interpreter of Internet Explorer 7 (IE7). Results of our experiments show that grammar-based whitebox fuzzing explores deeper program paths and avoids dead-ends due to non-parsable inputs. Compared to regular whitebox fuzzing, grammar-based whitebox fuzzing increased coverage of the code generation module of the IE7 JavaScript interpreter from 53% to 81% while using three times fewer tests.
Register allocation by puzzle solving
Authors: Quintão Pereira Fernando Magno , Palsberg Jens
Published: June 2008

We show that register allocation can be viewed as solving a collection of puzzles. We model the register file as a puzzle board and the program variables as puzzle pieces; pre-coloring and register aliasing fit in naturally. For architectures such as PowerPC, x86, and StrongARM, we can solve the puzzles in polynomial time, and we have augmented the puzzle solver with a simple heuristic for spilling. For SPEC CPU2000, the compilation time of our implementation is as fast as that of the extended version of linear scan used by LLVM, which is the JIT compiler in the openGL stack of Mac OS 10.5. Our implementation produces x86 code that is of similar quality to the code produced by the slower, state-of-the-art iterated register coalescing of George and Appel with the extensions proposed by Smith, Ramsey, and Holloway in 2004.
Copy coalescing by graph recoloring
Authors: Hack Sebastian , Goos Gerhard
Published: June 2008

Register allocation is always a trade-off between live-range splitting and coalescing. Live-range splitting generally leads to less spilling at the cost of inserting shuffle code. Coalescing removes shuffle code while potentially raising the register demand and causing spilling.

Recent research showed that the live-range splitting of the SSA form's Æ-functions leads to
chordal
interference graphs. This improves upon two long-standing inconveniences of graph coloring register allocation: First, chordal graphs are optimally colorable in quadratic time. Second, the number of colors needed to color the graph is equal to the maximal register pressure in the program. However, the inserted shuffle code incurred by the Æ-functions can slow down the program severely. Hence, to make such an approach work in practice, a coalescing technique is needed that removes most of the shuffle code
without
causing further spilling.

In this paper, we present a coalescing technique designed for, but not limited to, SSA-form register allocation. We exploit that a valid coloring can be easily obtained by an SSA-based register allocator. This initial coloring is then improved by recoloring the interference graph and assigning shuffle-code related nodes the same color. Thereby, we always keep the coloring of the graph valid. Hence, the coalescing is safe, i. e. no spill code will be caused by coalescing.

Comparing to iterated register coalescing, the state of the art in safe coalescing, our method is able to remove 22.5% of the costs and 44.3% of the copies iterated coalescing left over. The best solution possible, found by a colaescer using integer linear programming (ILP), was 35.9% of the costs and 51.9% of the copies iterated coalescing left over. The runtime of programs compiled with our heuristic matches that of the programs compiled with the ILP technique.
Efficient program execution indexing
Authors: Xin Bin , Sumner William N. , Zhang Xiangyu
Published: June 2008

Execution indexing uniquely identifies a point in an execution. Desirable execution indices reveal correlations between points in an execution and establish correspondence between points across multiple executions. Therefore, execution indexing is essential for a wide variety of dynamic program analyses, for example, it can be used to organize program profiles; it can precisely identify the point in a re-execution that corresponds to a given point in an original execution and thus facilitate debugging or dynamic instrumentation. In this paper, we formally define the concept of execution index and propose an indexing scheme based on execution structure and program state. We present a highly optimized online implementation of the technique. We also perform a client study, which targets producing a failure inducing schedule for a data race by verifying the two alternative happens-before orderings of a racing pair. Indexing is used to precisely locate corresponding points across multiple executions in the presence of non-determinism so that no heavyweight tracing/replay system is needed.
Bootstrapping
Authors: Kahlon Vineet
Published: June 2008

We propose a framework for improving both the scalability as well as the accuracy of pointer alias analysis, irrespective of its flow or context-sensitivities, by leveraging a three-pronged strategy that effectively combines
divide and conquer, parallelization and function summarization
. A key step in our approach is to first identify small subsets of pointers such that the problem of computing aliases of any pointer can be reduced to computing them in these small subsets instead of the entire program. In order to identify these subsets, we first apply a series of increasingly accurate but highly scalable (context and flow-insensitive) alias analyses in a cascaded fashion such that each analysis

A
i

works on the subsets generated by the previous one

A
i-1

. Restricting the application of

A
i

to subsets generated by

A
i-1

, instead of the entire program, improves it scalability, i.e.,

A
i

is
bootstrapped
by

A
i-1

. Once these small subsets have been computed, in order to make our overall analysis accurate, we employ our new summarization-based flow and context-sensitive alias analysis. The small size of each subset offsets the higher computational complexity of the context-sensitive analysis. An important feature of our framework is that the analysis for each of the subsets can be carried out independently of others thereby allowing us to leverage parallelization further improving scalability.
Explaining failures of program analyses
Authors: von Dincklage Daniel , Diwan Amer
Published: June 2008

With programs getting larger and often more complex with each new release, programmers need all the help they can get in understanding and transforming programs. Fortunately, modern development environments, such as Eclipse, incorporate tools for understanding, navigating, and transforming programs. These tools typically use program analyses to extract relevant properties of programs.

These tools are often invaluable to developers; for example, many programmers use refactoring tools regularly. However, poor results by the underlying analyses can compromise a tool's usefulness. For example, a bug finding tool may produce too many false positives if the underlying analysis is overly conservative, and thus overwhelm the user with too many possible errors in the program. In such cases it would be invaluable for the tool to explain to the user
why
it believes that each bug exists. Armed with this knowledge, the user can decide which bugs are worth pursing and which are false positives.

The contributions of this paper are as follows: (i) We describe requirements on the structure of an analysis so that we can produce reasons when the analysis fails; the user of the analysis determines whether or not an analysis's results constitute failure. We also describe a simple language that enforces these requirements; (ii) We describe how to produce necessary and sufficient reasons for analysis failure; (iii) We evaluate our system with respect to a number of analyses and programs and find that most reasons are small (and thus usable) and that our system is fast enough for interactive use.
Program analysis as constraint solving
Authors: Gulwani Sumit , Srivastava Saurabh , Venkatesan Ramarathnam
Published: June 2008

A constraint-based approach to invariant generation in programs translates a program into constraints that are solved using off-the-shelf constraint solvers to yield desired program invariants.

In this paper we show how the constraint-based approach can be used to model a wide spectrum of program analyses in an expressive domain containing disjunctions and conjunctions of linear inequalities. In particular, we show how to model the problem of context-sensitive interprocedural program verification. We also present the first constraint-based approach to weakest precondition and strongest postcondition inference. The constraints we generate are boolean combinations of quadratic inequalities over integer variables. We reduce these constraints to SAT formulae using bitvector modeling and use off-the-shelf SAT solvers to solve them.

Furthermore, we present interesting applications of the above analyses, namely bounds analysis and generation of most-general counter-examples for both safety and termination properties. We also present encouraging preliminary experimental results demonstrating the feasibility of our technique on a variety of challenging examples.
Velodrome
Authors: Flanagan Cormac , Freund Stephen N. , Yi Jaeheon
Published: June 2008

Atomicity is a fundamental correctness property in multithreaded programs, both because atomic code blocks are amenable to sequential reasoning (which significantly simplifies correctness arguments), and because atomicity violations often reveal defects in a program's synchronization structure. Unfortunately, all atomicity analyses developed to date are incomplete in that they may yield false alarms on correctly synchronized programs, which limits their usefulness.

We present the first dynamic analysis for atomicity that is both sound and complete. The analysis reasons about the exact dependencies between operations in the observed trace of the target program, and it reports error messages if and only if the observed trace is not conflict-serializable. Despite this significant increase in precision, the performance and coverage of our analysis is competitive with earlier incomplete dynamic analyses for atomicity.
Inferring locks for atomic sections
Authors: Cherem Sigmund , Chilimbi Trishul , Gulwani Sumit
Published: June 2008

Atomic sections
are a recent and popular idiom to support the development of concurrent programs. Updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. Traditionally, atomic sections are supported through the use of optimistic concurrency, either using a transactional memory hardware, or an equivalent software emulation (STM).

This paper explores automatically supporting atomic sections using pessimistic concurrency. We present a system that combines compiler and runtime techniques to automatically transform programs written with atomic sections into programs that only use locking primitives. To minimize contention in the transformed programs, our compiler chooses from several lock granularities, using fine-grain locks whenever it is possible.

This paper formally presents our framework, shows that our compiler is sound (i.e., it protects all shared locations accessed within atomic sections), and reports experimental results.
Dataflow analysis for concurrent programs using datarace detection
Authors: Chugh Ravi , Voung Jan W. , Jhala Ranjit , Lerner Sorin
Published: June 2008

Dataflow analyses for concurrent programs differ from their single-threaded counterparts in that they must account for shared memory locations being overwritten by concurrent threads. Existing dataflow analysis techniques for concurrent programs typically fall at either end of a spectrum: at one end, the analysis conservatively kills facts about all data that might possibly be shared by multiple threads; at the other end, a precise thread-interleaving analysis determines which data may be shared, and thus which dataflow facts must be invalidated. The former approach can suffer from imprecision, whereas the latter does not scale.

We present RADAR, a framework that automatically converts a dataflow analysis for sequential programs into one that is correct for concurrent programs. RADAR uses a race detection engine to kill the dataflow facts, generated and propagated by the sequential analysis, that become invalid due to concurrent writes. Our approach of factoring all reasoning about concurrency into a race detection engine yields two benefits. First, to obtain analyses for code using new concurrency constructs, one need only design a suitable race detection engine for the constructs. Second, it gives analysis designers an easy way to tune the scalability and precision of the overall analysis by only modifying the race detection engine. We describe the RADAR framework and its implementation using a pre-existing race detection engine. We show how RADAR was used to generate a concurrent version of a null-pointer dereference analysis, and we analyze the result of running the generated concurrent analysis on several benchmarks.
XMem
Authors: Wegiel Michal , Krintz Chandra
Published: June 2008

Developers commonly build contemporary enterprise applications using type-safe, component-based platforms, such as J2EE, and architect them to comprise multiple tiers, such as a web container, application server, and database engine. Administrators increasingly execute each tier in its own managed runtime environment (MRE) to improve reliability and to manage system complexity through the fault containment and modularity offered by isolated MRE instances. Such isolation, however, necessitates expensive cross-tier communication based on protocols such as object serialization and remote procedure calls. Administrators commonly co-locate communicating MREs on a single host to reduce communication overhead and to better exploit increasing numbers of available processing cores. However, state-of-the-art MREs offer no support for more efficient communication between co-located MREs, while fast inter-process communication mechanisms, such as shared memory, are widely available as a standard operating system service on most modern platforms.

To address this growing need, we present the design and implementation of XMem ? type-safe, transparent, shared memory support for co-located MREs. XMem guarantees type-safety through coordinated, parallel, multi-process class loading and garbage collection. To avoid introducing any level of indirection, XMem manipulates virtual memory mapping. In addition, object sharing in XMem is fully transparent: shared objects are identical to local objects in terms of field access, synchronization, garbage collection, and method invocation, with the only difference being that sharedto-private pointers are disallowed. XMem facilitates easy integration and use by existing communication technologies and software systems, such as RMI, JNDI, JDBC, serialization/XML, and network sockets.

We have implemented XMem in the open-source, productionquality HotSpot Java Virtual Machine. Our experimental evaluation, based on core communication technologies underlying J2EE, as well as using open-source server applications, indicates that XMem significantly improves throughput and response time by avoiding the overheads imposed by object serialization and network communication.
Discovering properties about arrays in simple programs
Authors: Halbwachs Nicolas , Péron Mathias
Published: June 2008

Array bound checking and array dependency analysis (for parallelization) have been widely studied. However, there are much less results about analyzing properties of array
contents
. In this paper, we propose a way of using abstract interpretation for
discovering
properties about array contents in some restricted cases: one-dimensional arrays, traversed by simple "for" loops. The basic idea, borrowed from [GRS05], consists in partitioning arrays into symbolic intervals (e.g., [1,
i
-- 1], [
i
,
i
], [
i
+ 1,
n
]), and in associating with each such interval
I
and each array
A
an abstract variable
A

I

; the new idea is to consider
relational
abstract properties ψ(
A

I

,
B

I

, ...) about these abstract variables, and to interpret such a property pointwise on the interval
I
: ∀
l
∈
I
, ψ(
A
[
l
],
B
[
l
],...). The abstract semantics of our simple programs according to these abstract properties has been defined and implemented in a prototype tool. The method is able, for instance, to discover that the result of an insertion sort is a sorted array, or that, in an array traversal guarded by a "sentinel", the index stays within the bounds.
Full functional verification of linked data structures
Authors: Zee Karen , Kuncak Viktor , Rinard Martin
Published: June 2008

We present the first verification of
full functional correctness
for a range of linked data structure implementations, including mutable lists, trees, graphs, and hash tables. Specifically, we present the use of the Jahob verification system to verify formal specifications, written in classical higher-order logic, that completely capture the desired behavior of the Java data structure implementations (with the exception of properties involving execution time and/or memory consumption). Given that the desired correctness properties include intractable constructs such as quantifiers, transitive closure, and lambda abstraction, it is a challenge to successfully prove the generated verification conditions.

Our Jahob verification system uses
integrated reasoning
to split each verification condition into a conjunction of simpler subformulas, then apply a diverse collection of specialized decision procedures, first-order theorem provers, and, in the worst case, interactive theorem provers to prove each subformula. Techniques such as replacing complex subformulas with stronger but simpler alternatives, exploiting structure inherently present in the verification conditions, and, when necessary, inserting verified lemmas and proof hints into the imperative source code make it possible to seamlessly integrate all of the specialized decision procedures and theorem provers into a single powerful integrated reasoning system. By appropriately applying multiple proof techniques to discharge different subformulas, this reasoning system can effectively prove the complex and challenging verification conditions that arise in this context.
Model checking transactional memories
Authors: Guerraoui Rachid , Henzinger Thomas A. , Jobstmann Barbara , Singh Vasu
Published: June 2008

Model checking software transactional memories (STMs) is difficult because of the unbounded number, length, and delay of concurrent transactions and the unbounded size of the memory. We show that, under certain conditions, the verification problem can be reduced to a finite-state problem, and we illustrate the use of the method by proving the correctness of several STMs, including two-phase locking, DSTM, TL2, and optimistic concurrency control. The safety properties we consider include strict serializability and opacity; the liveness properties include obstruction freedom, livelock freedom, and wait freedom.

Our main contribution lies in the structure of the proofs, which are largely automated and not restricted to the STMs mentioned above. In a first step we show that every STM that enjoys certain structural properties either violates a safety or liveness requirement on some program with two threads and two shared variables, or satisfies the requirement on all programs. In the second step we use a model checker to prove the requirement for the STM applied to a most general program with two threads and two variables. In the safety case, the model checker constructs a simulation relation between two carefully constructed finite-state transition systems, one representing the given STM applied to a most general program, and the other representing a most liberal safe STM applied to the same program. In the liveness case, the model checker analyzes fairness conditions on the given STM transition system.
Flexible task graphs
Authors: Auerbach Joshua , Bacon David F. , Guerraoui Rachid , Spring Jesper Honig , Vitek Jan
Published: June 2008

The disadvantages of unconstrained shared-memory multi-threading in Java, especially with regard to latency and determinism in realtime systems, have given rise to a variety of language extensions that place restrictions on how threads allocate, share, and communicate memory, leading to order-of-magnitude reductions in latency and jitter. However, each model makes different trade-offs with respect to expressiveness, efficiency, enforcement, and latency, and no one model is best for all applications.

In this paper we present Flexible Task Graphs (Flexotasks), a single system that allows different isolation policies and mechanisms to be combined in an orthogonal manner, subsuming four previously proposed models as well as making it possible to use new combinations best suited to the needs of particular applications. We evaluate our implementation on top of the IBM Web-Sphere Real Time Java virtual machine using both a microbenchmark and a 30 KLOC avionics collision detector. We show that Flexotasks are capable of executing periodic threads at 10 KHz with a standard deviation of 1.2μs and that it achieves significantly better performance than RTSJ's scoped memory constructs while remaining impervious to interference from global garbage collection.
Enhanced hot spot detection heuristics for embedded java just-in-time compilers
Authors: Lee Seong-Won , Moon Soo-Mook , Kim Seong-Moo
Published: June 2008

Most Java just-in-time compilers (JITC) try to compile only hot methods since the compilation overhead is part of the running time. This requires precise and efficient
hot spot detection
, which includes distinguishing hot methods from cold methods, detecting them as early as possible, and paying a small runtime overhead for detection. A hot method could be identified by measuring its running time during interpretation since a long-running method is likely to be a hot method. However, precise measurement of the running time during execution is too expensive, especially in embedded systems, so many counter-based heuristics have been proposed to estimate it. The
Simple
heuristic counts only method invocations without any consideration of loops [1], while Sun's
HotSpot
heuristic counts loop iterations as well, but does not consider loop sizes or method sizes [2,14]. The static analysis heuristic estimates the running time of a method by statically analyzing loops or heavy-cost bytecodes but does not measure their dynamic counts [3]. Although the overhead of these heuristics is low, they do not estimate the running time precisely, which may lead to imprecise hot spot detection.

This paper proposes a new hot spot detection heuristic which can estimate the running time more precisely than others with a relatively low overhead. It dynamically counts only important bytecodes interpreted, but with a simple arithmetic calculation it can obtain the precise count of all interpreted bytecodes. We also propose employing a static analysis technique to predict those hot methods which spend a huge execution time once invoked. This static prediction can allow compiling these methods at their first-invocation, complementing the proposed dynamic estimation technique. We implemented both, which led to a performance benefit of 10% compared to the
HotSpot
heuristic.
Impact of JVM superoperators on energy consumption in resource-constrained embedded systems
Authors: Badea Carmen , Nicolau Alexandru , Veidenbaum Alexander V.
Published: June 2008

Energy consumption is one of the most important issues in resource-constrained embedded systems. Many such systems run Java-based applications due to Java's architecture-independent format (bytecode). Standard techniques for executing bytecode programs, e.g. interpretation or just-in-time compilation, have performance or memory issues that make them unsuitable for resource-constrained embedded systems.

A superoperator-extended, lightweight Java Virtual Machine (JVM) can be used in resource-constrained embedded systems to improve performance and reduce memory consumption. This paper shows that such a JVM also significantly reduces energy consumption. This is due primarily to a considerable reduction in the number of memory accesses and thus in energy consumption in the instruction and data TLBs and caches and, in most cases, in DRAM energy consumption. Since the fraction of processor energy dissipated in these units is approximately 60%, the energy savings achieved are significant.

The paper evaluates the number of load, store, and computational instructions eliminated by the use of proposed superoperators as compared to a simple interpreter on a set of embedded benchmarks. Using cache and DRAM per access energy we estimate the total processor/DRAM energy saved by using our JVM. Our results show that with 32KB caches the reduction in energy consumption ranges from 40% to 60% of the overall processor, plus DRAM energy. Even higher savings may be achieved with smaller caches and increased access to DRAM as DRAM access energy is fairly high.
Generalized instruction selection using
SSA
-graphs
Authors: Ebner Dietmar , Brandner Florian , Scholz Bernhard , Krall Andreas , Wiedermann Peter , Kadlec Albrecht
Published: June 2008

Instruction selection is a well-studied compiler phase that translates the compiler's intermediate representation of programs to a sequence of target-dependent machine instructions optimizing for various compiler objectives (
e.g.
speed and space). Most existing instruction selection techniques are limited to the scope of a single statement or a basic block and cannot cope with irregular instruction sets that are frequently found in embedded systems.

We consider an optimal technique for instruction selection that uses Static Single Assignment (
SSA
) graphs as an intermediate representation of programs and employs the Partitioned Boolean Quadratic Problem (
PBQP
) for finding an optimal instruction selection. While existing approaches are limited to instruction patterns that can be expressed in a simple tree structure, we consider complex patterns producing multiple results at the same time including pre/post increment addressing modes, div-mod instructions, and
SIMD
extensions frequently found in embedded systems. Although both instruction selection on SSA-graphs and
PBQP
are known to be NP-complete, the problem can be solved efficiently - even for very large instances.

Our approach has been implemented in
LLVM
for an embedded ARMv5 architecture. Extensive experiments show speedups of up to 57% on typical DSP kernels and up to 10% on SPECINT 2000 and MiBench benchmarks. All of the test programs could be compiled within less than half a minute using a heuristic
PBQP
solver that solves 99.83% of all instances optimally.
Compiler driven data layout optimization for regular/irregular array access patterns
Authors: Cho Doosan , Pasricha Sudeep , Issenin Ilya , Dutt Nikil , Paek Yunheung , Ko SunJun
Published: June 2008

Embedded multimedia applications consist of regular and irregular memory access patterns. Particularly, irregular pattern are not amenable to static analysis for extraction of access patterns, and thus prevent efficient use of a Scratch Pad Memory (SPM) hierarchy for performance and energy improvements. To resolve this, we present a compiler strategy to optimize data layout in regular/irregular multimedia applications running on embedded multiprocessor environments. The goal is to maximize the amount of accesses to the SPM over the entire system which leads to a reduction in the energy consumption of the system. This is achieved by optimizing data placement of application-wide reused data so that it resides in the SPMs of processing elements. Specifically, our scheme is based on a profiling that generates a memory access footprint. The memory access footprint is used to identify data elements with fine granularity that can profitably be placed in the SPMs to maximize performance and energy gains. We present a heuristic approach that efficiently exploits the SPMs using memory access footprint. Our experimental results show that our approach is able to reduce energy consumption by 30% and improve performance by 18% over cache based memory subsystems for various multimedia applications.
Relative competitive analysis of cache replacement policies
Authors: Reineke Jan , Grund Daniel
Published: June 2008

Caches are commonly employed to hide the latency gap between memory and the CPU by exploiting locality in memory accesses. On today's architectures a cache miss may cost several hundred CPU cycles.

In order to fulfill stringent performance requirements, caches are now also used in hard real-time systems. In such systems, upper and sometimes also lower bounds on the execution times of a task have to be computed. To obtain tight bounds, timing analyses
must
take into account the cache architecture. However, developing cache analyses -- analyses that determine whether a memory access is a hit or a miss -- is a difficult problem for some cache architectures.

In this paper, we present a tool to automatically compute relative competitive ratios for a large class of replacement policies, including LRU, FIFO, and PLRU. Relative competitive ratios bound the performance of one policy relative to the performance of another policy.

These performance relations allow us to use cache-performance predictions for one policy to compute predictions for another, including policies that could previously not be dealt with.
Robust and sustainable schedulability analysis of embedded software
Authors: Anand Madhukar , Lee Insup
Published: June 2008

For real-time systems, most of the analysis involves efficient or exact schedulability checking. While this is important, analysis is often based on the assumption that the task parameters such as execution requirements and inter-arrival times between jobs are known exactly. In most cases, however, only a worst-case estimate of these quantities is available at the time of analysis. It is therefore imperative that schedulability analysis hold for better parameter values (
Sustainable Analysis
). On the other hand, if the task or system parameters turn out to be worse off, then the analysis should tolerate some deterioration (
Robust Analysis
). Robust analysis is especially important, because the implication of task schedulability is often weakened in the presence of optimizations that are performed on its code, or dynamic system parameters.

In this work, we define and address sustainability and robustness questions for analysis of embedded real-time software that is modeled by conditional real-time tasks. Specifically, we show that, while the analysis is sustainable for changes in the task such as lower job execution times and increased relative deadlines, it is not the case for code changes such as job splitting and reordering. We discuss the impact of these results in the context of common compiler optimizations, and then develop robust schedulability techniques for operations where the original analysis is not sustainable.
Improving performance and reducing energy-delay with adaptive resource resizing for out-of-order embedded processors
Authors: Homayoun Houman , Pasricha Sudeep , Makhzan Mohammad , Veidenbaum Alex
Published: June 2008

While Ultra Deep Submicron (UDSM) CMOS scaling gives embedded processor designers ample silicon budget to increase processor resources to improve performance, restrictions with the power budget and practically achievable operating clock frequencies act as limiting factors. In this paper we show how just increasing processor resource size is not effective in improving performance due to constraints on achievable operating clock frequency. In response we propose two adaptive resource resizing techniques
L2RS
and
L2ML1RS that adaptively resize resources by exploiting cache misses
. Our results show a significant performance improvement and overall energy-delay reduction of on average 9.2% (upto 34%) and 3.8% respectively across SPEC2K benchmarks for
L2ML1RS
. Applying
L2RS
resulted in 6.8% performance improvement (upto 24%) and 4.6% energy-delay reduction. We also present the required circuit modification to apply these techniques which shown to be minimal.
A domain specific interconnect for reconfigurable computing
Authors: Rajopadhye Sanjay , Gupta Gautam , Renganarayana Lakshminarayanan
Published: June 2008

Affine Control Loops (ACLs) occur frequently in data- and computeintensive applications. Implementing ACLs directly on dedicated hardware has the potential for spectacular performance improvement in area, time and energy. An important challenge for such direct hardware compilation of ACLs is the interconnection between the different processing elements, which may be non-local as well as dynamic. We propose a generic, reconfigurable interconnection fabric which can realize the data-path of any ACL and be dynamically reconfigured in constant time. We have applied for a patent for this technology.
FaCSim
Authors: Lee Jaejin , Kim Junghyun , Jang Choonki , Kim Seungkyun , Egger Bernhard , Kim Kwangsub , Han SangYong
Published: June 2008

There have been strong demands for a fast and cycle-accurate virtual platforms in the embedded systems area where developers can do meaningful software development including performance debugging in the context of the entire platform. In this paper, we describe the design and implementation of a fast and cycle-accurate architecture simulator called FaCSim as a first step towards such a virtual platform. FacSim accurately models the ARM9E-S processor core and ARM926EJ-S processor's memory subsystem. It accurately simulates exceptions and interrupts to enable whole-system simulation including the OS. Since it is implemented in a modular manner in C++, it can be easily extended with other system components by subclassing or adding new classes. FaCSim is based on an interpretive simulation technique to provide flexibility, yet achieving high speed. It enables fast cycle-accurate architecture simulation by means of three mechanisms. First, it computes elapsed cycles in each pipeline stage as a chunk and incrementally adds it up to advance the core clock instead of performing cycle-by-cycle simulation. Second, it uses a basic-block cache that caches decoded instructions at the basic-block level. Finally, it is parallelized to exploit multicore systems that are available everywhere these days. Using 21 applications from the EEMBC benchmark suite, FaCSim's accuracy is validated against the ARM926EJ-S development board from ARM, and is accurate in a ±7% error margin. Due to basic-block level caching and parallelization, FaCSim is, on average, more than three times faster than ARMulator and more than six times faster than SimpleScalar.
A type system for the automatic distribution of higher-order synchronous dataflow programs
Authors: Delaval Gwenaël , Girault Alain , Pouzet Marc
Published: June 2008

We address the design of distributed systems with synchronous dataflow programming languages. As modular design entails handling both architectural and functional modularity, our first contribution is to extend an existing synchronous dataflow programming language with primitives allowing the description of a distributed architecture and the localization of some expressions onto some processors. We also present a distributed semantics to formalize the distributed execution of synchronous programs. Our second contribution is to provide a type system, in order to infer the localization of non-annotated values by means of type inference and to ensure, at compilation time, the consistency of the distribution. Our third contribution is to provide a type-directed projection operation to obtain automatically, from a centralized typed program, the local program to be executed by each computing resource. The type system as well as the automatic distribution mechanism has been fully implemented in the compiler of an existing synchronous data-flow programming language.
EventScript
Authors: Cohen Norman H. , Kalleberg Karl Trygve
Published: June 2008

EventScript is a simple but powerful language for programming reactive processes. A stream of incoming events is matched against a regular expression. Actions embedded within the regular expression are executed in response to the matching of patterns of events. These actions include assigning computed values to variables and emitting output events. The definition of EventScript presented a number of novel and interesting language-design choices. EventScript has an efficient implementation, and has been used in a development environment for complex event-based applications. We have used EventScript to program both small examples and large industrial applications. Readers of EventScript programs find them easy to understand, and are comfortable with the familiar model of matching regular expressions.
Clock-directed modular code generation for synchronous data-flow languages
Authors: Biernacki Dariusz , Colaço Jean-Louis , Hamon Gregoire , Pouzet Marc
Published: June 2008

The compilation of synchronous block diagrams into sequential imperative code has been addressed in the early eighties and can now be considered as folklore. However, separate, or
modular
, code generation, though largely used in existing compilers and particularly in industrial ones, has never been precisely described or entirely formalized. Such a formalization is now fundamental in the long-term goal to develop a mathematically certified compiler for a synchronous language as well as in simplifying existing implementations.

This article presents in full detail the modular compilation of synchronous block diagrams into sequential code. We consider a first-order functional language reminiscent of LUSTRE, which it extends with a general
n
-ary
merge
operator, a
reset
construct, and a richer notion of clocks. The clocks are used to express activation of computations in the program and are specifically taken into account during the compilation process to produce efficient imperative code. We introduce a generic machine-based intermediate language to represent transition functions, and we present a concise clock-directed translation from the source to this intermediate language. We address the target code generation phase by describing a translation from the intermediate language to JAVA and C.
Design and evaluation of a compiler for embedded stream programs
Authors: Newton Ryan R. , Girod Lewis D. , Craig Michael B. , Madden Samuel R. , Morrisett John Gregory
Published: June 2008

Applications that combine live data streams with embedded, parallel, and distributed processing are becoming more commonplace.
WaveScript
is a domain-specific language that brings high-level, type-safe, garbage-collected programming to these domains. This is made possible by three primary implementation techniques, each of which leverages characteristics of the streaming domain. First, we employ a novel evaluation strategy that uses a combination of interpretation and reification to partially evaluate programs into stream dataflow graphs. Second, we use profile-driven compilation to enable many optimizations that are normally only available in the synchronous (rather than asynchronous) dataflow domain. Finally, we incorporate an extensible system for rewrite rules to capture algebraic properties in specific domains (such as signal processing).

We have used our language to build and deploy a sensornetwork for the acoustic localization of wild animals, in particular, the Yellow-Bellied marmot. We evaluate WaveScript's performance on this application, showing that it yields good performance on both embedded and desktop-class machines, including distributed execution and substantial parallel speedups. Our language allowed us to implement the application rapidly, while outperforming a previous C implementation by over 35%, using fewer than half the lines of code. We evaluate the contribution of our optimizations to this success.
Post-pass periodic register allocation to minimise loop unrolling degree
Authors: Bachir Mounira , Touati Sid-Ahmed-Ali , Cohen Albert
Published: June 2008

This paper solves an open problem regarding loop unrolling after periodic register allocation. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates reuse circuits spanning multiple loop iterations. These circuits require periodic register allocation, which in turn yield a code generation challenge, generally addressed through: (1) hardware support --- rotating register files --- deemed too expensive for embedded processors, (2) insertion of register moves with a high risk of reducing the computation throughput --- initiation interval (
II
) --- of software pipelining, and (3) post-pass loop unrolling that does not compromise throughput but often leads to unpractical code growth. The latter approach relies on the proof that MAXLIVE registers are sufficient for periodic register allocation (2; 3; 5); yet the only heuristic to control the amount of post-pass loop unrolling does not achieve this bound and leads to undesired register spills (4; 7).

We propose a periodic register allocation technique allowing a software-only code generation that does not trade the optimality of the
II
for compactness of the generated code. Our idea is based on using the remaining registers: calling
R
arch
the number of architectural registers of the target processor, then the number of remaining registers that can be used for minimising the unrolling degree is equal to
R
arch
-MAXLIVE.

We provide a complete formalisation of the problem and algorithm, followed by extensive experiments. We achieve practical loop unrolling degrees in most cases --- with no increase of the
II
--- while state-of-the-art techniques would either induce register spilling, degrade the
II
or lead to unacceptable code growth.
Placement-and-routing-based register allocation for coarse-grained reconfigurable arrays
Authors: De Sutter Bjorn , Coene Paul , Vander Aa Tom , Mei Bingfeng
Published: June 2008

DSP architectures often feature multiple register files with sparse connections to a large set of ALUs. For such DSPs, traditional register allocation algorithms suffer from a lot of problems, including a lack of retargetability and phase-ordering problems. This paper studies alternative register allocation techniques based on placement and routing. Different register file models are studied and evaluated on a state-of-the art coarse-grained reconfigurable array DSP, together with a new post-pass register allocator for rotating register files.
Optimizing scientific application loops on stream processors
Authors: Wang Li , Yang Xuejun , Xue Jingling , Deng Yu , Yan Xiaobo , Tang Tao , Nguyen Quan Hoang
Published: June 2008

This paper describes a graph coloring compiler framework to allocate on-chip SRF(Stream Register File) storage for optimizing scientific applications on stream processors. Our framework consists of first applying enabling optimizations such as loop unrolling to expose stream reuse and opportunities for maximizing parallelism, i.e., overlapping kernel execution and memory transfers.Then the three SRF management tasks are solved in a unified manner via graph coloring: (1) placing streams in the SRF, (2) exploiting stream use, and (3) maximizing parallelism. We evaluate the performance of our compiler framework by actually running nine representative scientific computing kernels on our FT64 stream processor. Our preliminary results show that compiler management achieves an average speedup of 2.3x compared to First-Fit allocation. In comparison with the performance results obtained from running these benchmarks on Itanium 2, an average speedup of 2.1x is observed.
A tribute, not a memorial
Authors: Boss Pauline
Published: June 2008

In this paper, I discuss ambiguous loss, why it is so traumatizing, what to do to lower the distress when someone disappears without a trace, and why a tribute is more appropriate than a memorial. The paper is dedicated to the family, friends, and colleagues of Jim Gray.
The amateur search
Authors: Olson Michael
Published: June 2008

In the days that followed Jim's disappearance at sea, his family, friends and colleagues came together in a remarkable effort to help find him. The group gathered, analyzed and filtered information from many sources. In concert with the Coast Guard, the results were used to focus the search in the places where Jim and his sailboat Tenacious were most likely to be.

The scope and breadth -- indeed, the very existence -- of this amateur search effort reflect Jim at his best. The group was at first composed of those whose lives he had touched directly, who used skills and knowledge he had helped them to gain in hopes of finding him. As time passed, others joined in who were inspired by the unfolding story. In the end, thousands came together to search for Jim.
Jim Gray at Berkeley
Authors: Harrison Michael A.
Published: June 2008

Jim Gray spent a decade as a student and researcher at Berkeley. In action, he is remembered for his breadth, his depth, and his generosity.
Knowledge and wisdom
Authors: Helland Pat
Published: June 2008

Jim Gray was my mentor and friend for almost 25 years. Even before we met, he was changing my life through his writings. Jim continually and patiently nudged me to strive for more, accomplish more, and to pass these gifts on to others. He embodied those attributes that I most want to emulate.

Jim influenced those around him both by sharing in his immense knowledge and by listening and guiding. Even more, he created a community that fostered growth and sharing across competitive boundaries with a clear ethical compass. This paper summarizes my experiences with Jim's approach to nurturing and mentoring.
500 special relationships
Authors: Lazowska Ed
Published: June 2008

There are hundreds of us in academia and industry who consider ourselves FoJ: Friends of Jim. Jim invested so deeply and so uniquely in every one of us that we each felt we must be "the chosen one." And we were: Jim had so much to give that he was able to choose hundreds of us, shaping our careers and our lives.
Why did Jim Gray win the Turing Award?
Authors: Stonebraker Michael
Published: June 2008

This short paper is intended to describe for the layman why Jim Gray won so many awards, culminating in his being selected to receive the 1998 ACM Turing Award, arguably the "Nobel Prize of Computer Science". It briefly summarizes his main contributions to our field.
Jim Gray
Authors: Vaskevitch David
Published: June 2008

Jim Gray was successful in many aspects of his life. Not only did he have a profound influence on the computer industry, but also on all of the people that he interacted with along the way. It is this balance contribution to society that makes Jim truly unique.