bluuebunny/crossref_metadata_2025 huggingface dataset:
Mechanisms for bounding vulnerabilities of processor structures
Authors: Soundararajan Niranjan Kumar , Parashar Angshuman , Sivasubramaniam Anand
Published: September 2007

Concern for the increasing susceptibility of processor structures to transient errors has led to several recent research efforts that propose architectural techniques to enhance reliability. However, real systems are typically required to satisfy hard reliability budgets, and barring expensive full-redundancy approaches, none of the proposed solutions treat any reliability budgets or bounds as hard constraints. Meeting vulnerability bounds requires monitoring vulnerabilities of processor structures and taking appropriate actions whenever these bounds are violated. This mandates treating reliability as a first-order microarchitecture design constraint, while optimizing performance as long as reliability requirements are satisfied. This paper makes three key contributions towards this goal: (i) we present a simple infrastructure to monitor and provide upper bounds on the vulnerabilities of key processor structures at cycle-level fidelity; (ii) we propose two distinct control mechanisms - throttling and selective redundancy - to proactively and/or reactively bound the vulnerabilities to any limit specified by the system designer; (iii) within this framework, we propose a novel adaptation of Out-of-Order Commit for vulnerability reduction, which automatically provides additional leverage for the control mechanisms to boost performance while remaining within the reliability budget.
Exterminator
Authors: Novark Gene , Berger Emery D. , Zorn Benjamin G.
Published: September 2007

Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, whichcan lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down their location in the source code is difficult, even when the full memory state of the program is available. Once the errors are finally found, fixing them remains challenging: even for critical security-sensitive bugs, the average time between initial reports and the issuance of a patch is nearly one month.

We present Exterminator, a system that automatically correct sheap-based memory errors without programmer intervention. Exterminator exploits randomization to pinpoint errors with high precision. From this information, Exterminator derives
runtime patches
that fix these errors both in current and subsequent executions. In addition, Exterminator enables collaborative bug correction by merging patches generated by multiple users. We present analytical and empirical results that demonstrate Exterminator's effectiveness at detecting and correcting both injected and real faults.
CheckFence
Authors: Burckhardt Sebastian , Alur Rajeev , Martin Milo M. K.
Published: September 2007

Concurrency libraries can facilitate the development of multi-threaded programs by providing concurrent implementations of familiar data types such as queues or sets. There exist many optimized algorithms that can achieve superior performance on multiprocessors by allowing concurrent data accesses without using locks. Unfortunately, such algorithms can harbor subtle concurrency bugs. Moreover, they requirememory ordering fences to function correctly on relaxed memory models.

To address these difficulties, we propose a verification approach that can exhaustively check all concurrent executions of a given test program on a relaxed memory model and can verify that they are observationally equivalent to a sequential execution. Our
CheckFence
prototype automatically translates the C implementation code and the test program into a SAT formula, hands the latter to a standard SAT solver, and constructs counter example traces if there exist incorrect executions. Applying
CheckFence
to five previously published algorithms, we were able to (1) find several bugs (some not previously known), and (2) determine how to place memory ordering fences for relaxed memory models.
Certified self-modifying code
Authors: Cai Hongxu , Shao Zhong , Vaynberg Alexander
Published: September 2007

Self-modifying code (SMC), in this paper, broadly refers to anyprogram that loads, generates, or mutates code at runtime. It is widely used in many of the world's critical software systems tosupport runtime code generation and optimization, dynamic loading and linking, OS boot loader, just-in-time compilation, binary translation,or dynamic code encryption and obfuscation. Unfortunately, SMC is alsoextremely difficult to reason about: existing formal verification techniques-including Hoare logic and type system-consistentlyassume that program code stored in memory is fixedand immutable; this severely limits their applicability and power.

This paper presents a simple but novel Hoare-logic-like framework that supports modular verification of general von-Neumann machine code with runtime code manipulation. By dropping the assumption that code memory is fixed and immutable, we are forced to apply local reasoningand separation logic at the very beginning, and treat program code uniformly as regular data structure. We address the interaction between separation and code memory and show how to establish the frame rules for local reasoning even in the presence of SMC. Our frameworkis realistic, but designed to be highly generic, so that it can support assembly code under all modern CPUs (including both x86 andMIPS). Our system is expressive and fully mechanized. We prove itssoundness in the Coq proof assistant and demonstrate its power by certifying a series of realistic examples and applications-all of which can directly run on the SPIM simulator or any stock x86 hardware.
Sketching stencils
Authors: Solar-Lezama Armando , Arnold Gilad , Tancau Liviu , Bodik Rastislav , Saraswat Vijay , Seshia Sanjit
Published: September 2007

Performance of stencil computations can be significantly improved through smart implementations that improve memory locality, computation reuse, or parallelize the computation. Unfortunately, efficient implementations are hard to obtain because they often involve non-traditional transformations, which means that they cannot be produced by optimizing the reference stencil with a compiler. In fact, many stencils are produced by code generators that were tediously handcrafted.

In this paper, we show how stencil implementations can be produced with sketching. Sketching is a software synthesis approach where the programmer develops a partial implementation--a sketch--and a separate specification of the desired functionality given by a reference (unoptimized) stencil. The synthesizer then completes the sketch to behave like the specification, filling in code fragments that are difficult to develop manually.

Existing sketching systems work only for small finite programs,
i.e.,
, programs that can be represented as small Boolean circuits. In this paper, we develop a sketching synthesizer that works for stencil computations, a large class of programs that, unlike circuits, have unbounded inputs and outputs, as well as an unbounded number of computations. The key contribution is a reduction algorithm that turns a stencil into a circuit, allowing us to synthesize stencils using an existing sketching synthesizer.
Mace
Authors: Killian Charles Edwin , Anderson James W. , Braud Ryan , Jhala Ranjit , Vahdat Amin M.
Published: September 2007

Building distributed systems is particularly difficult because of the asynchronous, heterogeneous, and failure-prone environment where these systemsmust run. Tools for building distributed systems must strike a compromise between reducing programmer effort and increasing system efficiency. We present
Mace
, a C++ language extension and source-to-source compiler that translates a concise but expressive distributed system specification into a C++ implementation. Mace overcomes the limitations of low-level languages by providing a unified framework for networking and event handling, and the limitations of high-level languages by allowing programmers to write program components in a controlled and structured manner in C++. By imposing structure and restrictions on how applications can be written, Mace supports debugging at a higher level, including support for efficient model checking and causal-path debugging. Because Mace programs compile to C++, programmers can use existing C++ tools, including optimizers, profilers, and debuggers to analyze their systems.
Optimistic parallelism requires abstractions
Authors: Kulkarni Milind , Pingali Keshav , Walter Bruce , Ramanarayanan Ganesh , Bala Kavita , Chew L. Paul
Published: September 2007

Irregular applications, which manipulate large, pointer-based data structures like graphs, are difficult to parallelize manually. Automatic tools and techniques such as restructuring compilers and run-time speculative execution have failed to uncover much parallelism in these applications, in spite of a lot of effort by the research community. These difficulties have even led some researchers to wonder if there is any coarse-grain parallelism worth exploiting in irregular applications.

In this paper, we describe two real-world irregular applications: a Delaunay mesh refinement application and a graphics application thatperforms agglomerative clustering. By studying the algorithms and data structures used in theseapplications, we show that there is substantial coarse-grain, data parallelism in these applications, but that this parallelism is very dependent on the input data and therefore cannot be uncoveredby compiler analysis. In principle, optimistic techniques such asthread-level speculation can be used to uncover this parallelism, but we argue that current implementations cannot accomplish thisbecause they do not use the proper abstractions for the data structuresin these programs.

These insights have informed our design of the
Galois system
, an object-based optimistic parallelization system for irregular applications. There are three main aspects to Galois: (1) a small number of syntactic constructs for packaging optimistic parallelism as iteration over ordered and unordered sets, (2)assertions about methods in class libraries, and (3) a runtime scheme for detecting and recovering from potentially unsafe accesses to shared memory made by an optimistic computation.

We show that Delaunay mesh generation and agglomerative clustering can be parallelized in a straight-forward way using the Galois approach, and we present experimental measurements to show that this approach is practical. These results suggest that Galois is a practical approach to exploiting data parallelismin irregular programs.
Software behavior oriented parallelization
Authors: Ding Chen , Shen Xipeng , Kelsey Kirk , Tice Chris , Huang Ruke , Zhang Chengliang
Published: September 2007

Many sequential applications are difficult to parallelize because of unpredictable control flow, indirect data access, and input-dependent parallelism. These difficulties led us to build a software system for behavior oriented parallelization (BOP), which allows a program to be parallelized based on partial information about program behavior, for example, a user reading just part of the source code, or a profiling tool examining merely one or few executions.

The basis of BOP is programmable software speculation, where a user or an analysis tool marks possibly parallel regions in the code, and the run-time system executes these regions speculatively. It is imperative to protect the entire address space during speculation. The main goal of the paper is to demonstrate that the general protection can be made cost effective by three novel techniques: programmable speculation, critical-path minimization, and value-based correctness checking. On a recently acquired multi-core, multi-processor PC, the BOP system reduced the end-to-end execution time by integer factors for a Lisp interpreter, a data compressor, a language parser, and a scientific library, with no change to the underlying hardware or operating system.
Making context-sensitive points-to analysis with heap cloning practical for the real world
Authors: Lattner Chris , Lenharth Andrew , Adve Vikram
Published: September 2007

Context-sensitive pointer analysis algorithms with full "heapcloning" are powerful but are widely considered to be too expensive to include in production compilers. This paper shows, for the first time, that a context-sensitive, field-sensitive algorithm with fullheap cloning (by acyclic call paths) can indeed be both scalable and extremely fast in practice. Overall, the algorithm is able to analyze programs in the range of 100K-200K lines of C code in 1-3 seconds,takes less than 5% of the time it takes for GCC to compile the code (which includes no whole-program analysis), and scales well across five orders of magnitude of code size. It is also able to analyze the Linux kernel (about 355K linesof code) in 3.1 seconds. The paper describes the major algorithmic and engineering design choices that are required to achieve these results, including (a) using flow-insensitive and unification-basedanalysis, which are essential to avoid exponential behavior in practice;(b) sacrificing context-sensitivity within strongly connected components of the call graph; and (c) carefully eliminating several kinds of O(
N
2
) behaviors (largely without affecting precision). The techniques used for (b) and (c) eliminated several major bottlenecks to scalability, and both are generalizable to other context-sensitive algorithms. We show that the engineering choices collectively reduce analysis time by factors of up to 10x-15xin our larger programs, and have found that the savings grow strongly with program size. Finally, we briefly summarize results demonstrating the precision of the analysis.
The ant and the grasshopper
Authors: Hardekopf Ben , Lin Calvin
Published: September 2007

Pointer information is a prerequisite for most program analyses, and the quality of this information can greatly affect their precision and performance. Inclusion-based (i.e. Andersen-style) pointer analysis is an important point in the space of pointer analyses, offering a potential sweet-spot in the trade-off between precision and performance. However, current techniques for inclusion-based pointer analysis can have difficulties delivering on this potential.

We introduce and evaluate two novel techniques for inclusion-based pointer analysis---one lazy, one eager
1
---that significantly improve upon the current state-of-the-art without impacting precision. These techniques focus on the problem of online cycle detection, a critical optimization for scaling such analyses. Using a suite of six open-source C programs, which range in size from 169K to 2.17M LOC, we compare our techniques against the three best inclusion-based analyses--described by Heintze and Tardieu [11], by Pearce et al. [21], and by Berndl et al. [4]. The combination of our two techniques results in an algorithm which is on average 3.2 xfaster than Heintze and Tardieu's algorithm, 6.4 xfaster than Pearce et al.'s algorithm, and 20.6 faster than Berndl et al.'s algorithm.

We also investigate the use of different data structures to represent points-to sets, examining the impact on both performance and memory consumption. We compare a sparse-bitmap implementation used in the GCC compiler with a BDD-based implementation, and we find that the BDD implementation is on average 2x slower than using sparse bitmaps but uses 5.5x less memory.
Efficient static analysis of XML paths and types
Authors: Genevès Pierre , Layaïda Nabil , Schmitt Alan
Published: September 2007

We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically type-check XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time complexity is a simple exponential of the size of a formula. The logic corresponds to the alternation free modal μ-calculus without greatest fixpoint, restricted to finite trees, and where formulas are cycle-free.

Our proof method is based on two auxiliary results. First, XML regular tree types and XPath expressions have a linear translation to cycle-free formulas. Second, the least and greatest fixpoints are equivalent for finite trees, hence the logic is closed under negation.

Building on these results, we describe a practical, effective system for solving the satisfiability of a formula. The system has been experimented with some decision problems such as XPath emptiness, containment, overlap, and coverage, with or without type constraints. The benefit of the approach is that our system can be effectively used in static analyzers for programming languages manipulating both XPath expressions and XML type annotations (as input and output types).
The ExoVM system for automatic VM and application reduction
Authors: Titzer Ben L. , Auerbach Joshua , Bacon David F. , Palsberg Jens
Published: September 2007

Embedded systems pose unique challenges to Java application developers and virtual machine designers. Chief among these challenges is the memory footprint of both the virtual machine and the applications that run within it. With the rapidly increasing set of features provided by the Java language, virtual machine designers are often forced to build custom implementations that make various tradeoffs between the footprint of the virtual machine and the subset of the Java language and class libraries that are supported. In this paper, we present the ExoVM, a system in which an application is initialized in a fully featured virtual machine, and then the code, data, and virtual machine features necessary to execute it are packaged into a binary image. Key to this process is
feature analysis
, a technique for computing the reachable code and data of a Java program and its implementation inside the VM simultaneously. The ExoVM reduces the need to develop customized embedded virtual machines by reusing a single VM infrastructure and automatically eliding the implementation of unused Java features on a per-program basis. We present a constraint-based instantiation of the analysis technique, an implementation in IBM's J9 Java VM, experiments evaluating our technique for the EEMBC benchmark suite, and some discussion of the individual costs of some of Java's features. Our evaluation shows that our system can reduce the non-heap memory allocation of the virtual machine by as much as 75%. We discuss VM and language design decisions that our work shows are important in targeting embedded systems, supporting the long-term goal of a common VM infrastructure spanning from motes to large servers.
Online optimizations driven by hardware performance monitoring
Authors: Schneider Florian T. , Payer Mathias , Gross Thomas R.
Published: September 2007

Hardware performance monitors provide detailed direct feedback about application behavior and are an additional source of infor-mation that a compiler may use for optimization. A JIT compiler is in a good position to make use of such information because it is running on the same platform as the user applications. As hardware platforms become more and more complex, it becomes more and more difficult to model their behavior. Profile information that captures general program properties (like execution frequency of methods or basic blocks) may be useful, but does not capture sufficient information about the execution platform. Machine-level performance data obtained from a hardware performance monitor can not only direct the compiler to those parts of the program that deserve its attention but also determine if an optimization step actually improved the performance of the application.

This paper presents an infrastructure based on a dynamic compiler+runtime environment for Java that incorporates machine-level information as an additional kind of feedback for the compiler and runtime environment. The low-overhead monitoring system provides fine-grained performance data that can be tracked back to individual Java bytecode instructions. As an example, the paper presents results for object co-allocation in a generational garbage collector that optimizes spatial locality of objects on-line using measurements about cache misses. In the best case, the execution time is reduced by 14% and L1 cache misses by 28%.
Static error detection using semantic inconsistency inference
Authors: Dillig Isil , Dillig Thomas , Aiken Alex
Published: September 2007

Inconsistency checking is a method for detecting software errors that relies only on examining multiple uses of a value. We propose that inconsistency inference is best understood as a variant of the older and better understood problem of type inference. Using this insight, we describe a precise and formal framework for discovering inconsistency errors. Unlike previous approaches to the problem, our technique for finding inconsistency errors is purely semantic and can deal with complex aliasing and path-sensitive conditions. We have built a nullde reference analysis of C programs based on semantic inconsistency inference and have used it to find hundreds of previously unknown null dereference errors in widely used C programs.
Integrated CPU and l2 cache voltage scaling using machine learning
Authors: AbouGhazaleh Nevine , Ferreira Alexandre , Rusu Cosmin , Xu Ruibin , Liberato Frank , Childers Bruce , Mosse Daniel , Melhem Rami
Published: September 2007

Embedded systems serve an emerging and diverse set of applications. As a result, more computational and storage capabilities are added to accommodate ever more demanding applications. Unfortunately, adding more resources typically comes on the expense of higher energy costs. New chip design with Multiple Clock Domains (MCD) opens the opportunity for fine-grain power management within theprocessor chip. When used with dynamic voltage scaling (DVS), we can control the voltage and power of each domain independently. A significant power and energy improvement has been shown when using MCD design in comparison to managing a single voltage domain for the whole chip, as in traditional chips with global DVS.

In this paper, we propose PACSL a Power-Aware Compiler-based approach using Supervised Learning. PACSL automatically derives an integrated CPU-core and on-chip L2 cache DVS policy tailored to a specific system and workload. Our approach uses supervised machine learning to discover a policy, which relies on monitoring a few performance counters. We present our approach detailing the role of a compiler in constructing a custom power management policy. We also discuss some implementation issues associated with our technique. We show that PACSL improves on traditional power management techniques that are used in general MCD chips. Our technique saves 22% on average (up to 46%) in energy-delay product over a DVS technique that applies independent DVS decisions in each domain. Compared to no-power management, our technique improves energy-delay product by 26% on average (up to 64%).
Java takes flight
Authors: Auerbach Joshua , Bacon David F. , Iercan Daniel T. , Kirsch Christoph M. , Rajan V. T. , Roeck Harald , Trummer Rainer
Published: September 2007

Existing programming methodologies for real-time systems suffer from a low level of abstraction and non-determinism in both the timing and the functional domains. As a result, real-time systems are difficult to test and must be re-certified every time changes are made to either the software or hardware environment. Exotasks are a novel Java programming construct that achievedeterministic timing, even in the presence of other Java threads, and across changes of hardware and software platform. They are deterministic functional data-flow tasks written in Java, combined with an orthogonal scheduling policy based on the logical execution time (LET) model. We have built a quad-rotor model helicopter, the JAviator, which we use as a testbed for this work. We evaluate our implementation of exotasks in IBM's J9 real-time virtual machine using actual flights of the helicopter. Our experiments show that we are able to maintain deterministic behavior in the face of variations in both software load and hardware platform.
Combining source-to-source transformations and processor instruction set extensions for the automated design-space exploration of embedded systems
Authors: Bennett Richard Vincent , Murray Alastair Colin , Franke Björn , Topham Nigel
Published: September 2007

Industry's demand for flexible embedded solutions providing high performance and short time-to-market has led to the development of configurable and extensible processors. These pre-verified application-specific processors build on proven baseline cores while allowing for some degree of customization through user-defined instruction set extensions (ISE) implemented as functional units in an extended micro-architecture. The traditional design flow for ISE is based on plain C sources of the target application and, after some ISE identification and synthesis stages, a modified source file is produced with explicit handles to the new machine instructions. Further code optimization is left to the compiler. In this paper we develop a novel approach, namely the combined exploration of source-level transformations and ISE identification. We have combined automated code transformation and ISE generators to explore the potential benefits of such a combination. This applies up to 50 transformations from a selection of 70, and synthesizes ISEs for the resulting code. The resulting performance has been measured on 26 applications from the SNU-RT and UTDSP benchmarks. We show that the instruction extensions generated by automated tools are heavily influenced by source code structure. Our results demonstrate that a combination of source-level transformations and instruction set extensions can yield average performance improvements of 47%. This out performs instruction set extensions when applied in isolation, and in extreme cases yields a speedup of 2.85.
Hierarchical real-time garbage collection
Authors: Pizlo Filip , Hosking Antony L. , Vitek Jan
Published: September 2007

Memory management is a critical issue for correctness and performance in real-time embedded systems. Recent work on real-time garbage collectors has shown that it is possible to provide guarantees on worst-case pause times and minimum mutator utilization time. This paper presents a new hierarchical real-time garbage collection algorithm for mixed-priority and mixed-criticality environments. With hierarchical garbage collection, real-time programmers can partition the heap into a number of heaplets and for each partition choose to run a separate collector with a schedule that matches the allocation behavior and footprint of the real-time task using it. This approach lowers worst-case response times of real-time applications by 26%, while almost doubling mutator utilization -- all with only minimal changes to the application code.
Safe worst-case execution time analysis by abstract interpretation of executable code
Authors: Kaestner Daniel
Published: September 2007

To verify that a safety-critical application meets all requirements lies in the responsibility of the system designers. Classical software validation methods like code review and testing with debugging are expensive and cannot really guarantee the absence of errors. In constrast, abstract interpretation provides a methodology for static program analysis that yields statements valid for all program runs with all inputs. Employing static analyzers is thus orthogonal to classical testing. A possible cause of catastrophic failure is the violation of timing constraints. Recent trends, e.g. in automotive industries (X-by-wire, time-triggered protocols) require knowledge on the Worst-Case Execution Time (WCET) of each task. Yet WCET determination is a difficult problem because of the characteristics of modern software and hardware. This talk focuses on AbsInt's tool aiT that combines abstract interpretation and integer linear programming to determine upper bounds for the WCETs of code snippets given as routines in executables. The hardware architecture of the underlying processor is precisely taken into account, including cache and pipeline behavior. Bounds are determined without the need to change the code and hold for all executions. aiT is used among others by Airbus in the development of various safety-critical applications for the A380.
Analyzing the real-time behaviour of deeply embedded event driven systems
Authors: Walther Karsten , Herzog René , Nolte Jörg
Published: September 2007

Most embedded control systems react on events in the real world by reading sensors and controlling actuators in real-time. This general behavior can be directly mapped onto event-driven systems in a natural and straightforward manner for a large variety of applications. Further real-time analysis and profiling on the same level of abstraction is possible for event-driven systems. This significantly helps developers of deeply embedded real-time applications. In this paper we introduce simulative profiling concepts and static analysis basics for the real-time analysis of event-driven systems. Furthermore we present a prototype analysis tool for the R
EFLEX
operating system that integrates real-time analysis into the software development cycle.
Generalizing parametric timing analysis
Authors: Coffman Joel , Healy Christopher , Mueller Frank , Whalley David
Published: September 2007

In the design of real-time and embedded systems, it is important to establish a bound on the worst-case execution time (WCET) of programs to assure via schedulability analysis that deadlines are not missed. Static WCET analysis is performed by a timing analysis tool. This paper describes novel improvements to such a tool, allowing parametric timing analysis to be performed. Parametric timing analyzers receive an upper bound on the number of loop iterations in terms of an expression which is used to create a parametric formula. This parametric formula is later evaluated to determine the WCET based on input values only known at runtime. Effecting a transformation from a numeric to a parametric timing analyzer requires two innovations: 1) a summation solver capable of summation non-constant expressions and 2) a polynomial data structure which can replace integers as the basis for all calculations. Both additions permit other methods of analysis (e.g. caching, pipeline, constraint) to occur simultaneously. Combining these techniques allows our tool to statically bound the WCET for a larger class of benchmarks.
Stream execution on wide-issue clustered VLIW architectures
Authors: Yan Shan , Lin Bill
Published: September 2007

This paper investigates the mapping of stream programs to wide-issue clustered VLIW processors so that designers can leverage their existing investments in VLIW-based platforms to harness the advantages of stream programming.
WCET analysis of instruction caches with prefetching
Authors: Yan Jun , Zhang Wei
Published: September 2007

Instruction prefetching is an effective technique to reduce the instruction cache miss latency for improving the average-case performance. For real-time systems, however, the use of instruction prefetching will only besuitable if a reasonably tight worst-case performance of programs using instruction prefetching can be predicted. This paper presents an approach to modeling and computing the worst-case instruction cache performance with prefetching. Our experimental results indicate that instruction prefetching can benefit both the average-case and worst-case performance; however, the degree of the worst-case performance improvement due to instruction prefetching is less than that of the average-case performance, thus leading to increased time variation for real-time computing. Also, we find that the prefetching distance can significantly impact the worst-case performance analysis with instruction prefetching. Particularly, when the prefetching distance is equal to the L1 miss penalty, the worst-case execution time with instruction prefetching is minimized (i.e., optimal).
SWL
Authors: In Jihyun , Shin Ilhoon , Kim Hyojun
Published: September 2007

As mobile phones become increasingly multifunctional, the number and size of applications installed in phones are rapidly increasing. Consequently, mobile phones require more hardware resources such as NOR/NAND flash memory and DRAM, and their production cost is accordingly becoming higher. One candidate solution to reduce production cost is demand paging using MMU. However, demand paging causes unpredictably long page fault latency, and as such mobile phone manufacturers are reluctant to deploy this scheme. In this paper, we present a method that reduces the long latency of page faults by performing page fault handling in a parallelized manner, considering the characteristics of NAND-Type flash memory. We also discuss how to modify the existing page cache replacement policies so that they can exploit the benefits of the parallelized page fault handler. Experimental results show that the parallelized page fault handler improves the worst case latency of page faults significantly, by up to roughly 20%, and that the modified page cache replacement policies improve both the average and worst instruction fetch time.
Compiler-managed partitioned data caches for low power
Authors: Ravindran Rajiv , Chu Michael , Mahlke Scott
Published: September 2007

Set-associative caches are traditionally managed using hardware-based lookup and replacement schemes that have high energy overheads. Ideally, the caching strategy should be tailored to the application's memory needs, thus enabling optimal use of this on-chip storage to maximize performance while minimizing power consumption. However, doing this in hardware alone is difficult due to hardware complexity, high power dissipation, overheads of dynamic discovery of application characteristics, and increased likelihood of making locally optimal decisions. The compiler can instead determine the caching strategy by analyzing the application code and providing hints to the hardware. We propose a hardware/software co-managed partitioned cache architecture in which enhanced load/store instructions are used to control fine-grain data placement within a set of cache partitions. In comparison to traditional partitioning techniques, load and store instructions can individually specify the set of partitions for lookup and replacement. This fine grain control can avoid conflicts, thus providing the performance benefits of highly associative caches, while saving energy by eliminating redundant tag and data array accesses. Using four direct-mapped partitions, we eliminated 25% of the tag checks and recorded an average 15% reduction in the energy-delay product compared to a hardware-managed 4-way set-associative cache.
Reducing the TCP acknowledgment frequency
Authors: Landström Sara , Larzon Lars-Åke
Published: September 2007

Delayed acknowledgments were introduced to conserve network and host resources. Further reduction of the acknowledgment frequency can be motivated in the same way. However, reducing the dependency on frequent acknowledgments in TCP is difficult because acknowledgments support reliable delivery, loss recovery, clock out new segments, and serve as input when determining an appropriate sending rate.

Our results show that in scenarios where there are no obvious advantages of reducing the acknowledgment frequency, performance can be maintained although fewer acknowledgments are sent. Hence, there is a potential for reducing the acknowledgment frequency more than is done through delayed acknowledgments today. Advancements in TCP loss recovery is one of the key reasons that the dependence on frequent acknowledgments has decreased.

We propose and evaluate an end-to-end solution, where four acknowledgments per send window are sent. The sender compensates for the reduced acknowledgment frequency using a form of Appropriate Byte Counting. The proposal also includes a modification of fast loss recovery to avoid frequent timeouts.
Passive measurement of one-way and two-way flow lifetimes
Authors: Lee DongJin , Brownlee Nevil
Published: September 2007

Flow based analysis has been considered a simple and effective approach in network analysis. 5-tuple (
unidirectional
) flows are used in many network traffic, however, often these analyses require bidirectional packet matching to observe the interactions. Separating the flows into two categories as
one-way
(packets in one direction only) and
two-way
(packets in both directions) flows can yield further insight. We have examined traces of
Auckland
traffic for 2000, 2003 and 2006, and analyzed their one-way and two-way flows. We observed several behaviors and the changes in flow sizes and their lifetimes over time. In our traces, we observe that one-way flows are mostly malicious, re-transmissions, and some are long-lived. Two-way flows are mostly normal end-to-end transmissions with their lifetimes/RTTs decreasing, their sizes increasing, and many short-lived flows mostly depict errors in TCP. Also, we observe similarity between one-way and two-way flow sizes for their lifetimes.
Using digital logic circuit simulation to build demonstrations of IT concepts
Authors: Stanley Timothy Daryl
Published: September 2007

This paper describes using an open source, freely available logic simulation package to build visualizations to teach IT concepts. The first visualization is of an XOR based, symmetric encryption/decryption process. While it is not the actual process used in modern encryption, it illustrates concepts that are used in encryption/decryption and are often used in IT, particularly in computer and Internet technology to protect files and secure transactions. While actual encryption would be over a much larger word size and use several passes in the encryption process, this tool clearly illustrates the basics of the process. A second visualization shows Hexadecimal numbers with their binary and decimal counterparts. These are important concepts in understanding how bit patterns can represent many different things within a computer. The flexibility of these visualizations is shown by a small circuit addition that can add ASCII characters to this display. Building these visualizations could be done with many different software tools; however, using a logic simulator for some visualizations has the advantages of being easy and also providing insight into the logic of the process that are being visualized.
The implementation of the Priority Ceiling Protocol in Ada-2005
Authors: Cheng Albert M. K. , Ras James
Published: September 2007

Ada 2005 is an even safer and more agile language than its predecessors, with all of the efficiency that is a hallmark of the Ada language design. It still has a strong focus on real-time response, multi-tasking, and sound engineering. It is the only international standard for object-oriented real-time distributed programming. High-integrity systems rarely make use of high-level language features such as Ada Protected Objects. Protected Types provide a passive mechanism for communication and synchronization between tasks. In this paper, we present some of these features, which are implemented using the Priority Ceiling Protocol (PCP). PCP is an extension of the Priority Inheritance Protocol (PIP), with the added features of preventing deadlocks and priority inversions. Priority inversion occurs when a high priority task is blocked for an unbounded time by lower priority tasks. Unfortunately though, PCP is not known to be supported by any operating systems. This article describes an implementation of PCP in Ada-2005. A detailed discussion of this protocol, and other related issues, are presented.
Evaluating the boundary conditions of the technology acceptance model
Authors: Chan Hock Chuan , Teo Hock-Hai
Published: September 2007

The technology acceptance model (TAM) is very widely used for studying technology acceptance. The model states that an individual's behavioral intention (BI) to use an information system is determined by his perceived usefulness (PU) and perceived ease of use (PEOU) of it. While many studies have applied the TAM, none has examined the model's behavior over its entire value range. We conducted two surveys to examine the values of BI over the two-dimensional boundary space formed by PU and PEOU. Contrary to current understanding, we find that the effects of PU and PEOU vary over the boundary space.
General Hierarchical Model (GHM) to measure similarity of time series
Authors: Zuo Xinqiang , Jin Xiaoming
Published: September 2007

Similarity query is a frequent subroutine in time series database to find the similar time series of the given one. In this process, similarity measure plays a very important part. The previous methods do not consider the relation between point correspondences and the importance (role) of the points on the content of time series during measuring similarity, resulting in their low accuracies in many real applications. In the paper, we propose a General Hierarchical Model (GHM), which determines the point correspondences by the hierarchies of points. It partitions the points of time series into different hierarchies, and then the points are restricted to be compared with the ones in the same hierarchy. The practical methods can be implemented based on the model with any real requirements, e.g. FFT Hierarchical Measures (FHM) given in this paper. And the hierarchical filtering methods of GHM are provided for range and
k
-NN queries respectively. Finally, two common data sets were used in
k
-NN query and clustering experiments to test the effectiveness of our approach and others. The time performance comparisons of all the tested methods were performed using the synthetic data set with various sizes. The experimental results show the superiority of our approach over the competitors. And we also give the experimental powers of the filtering methods proposed in the queries.
A parallel general-purpose synthetic data generator
Authors: Hoag Joseph E. , Thompson Craig W.
Published: September 2007

PSDG is a parallel synthetic data generator designed to generate "industrial sized" data sets quickly using cluster computing. PSDG depends on SDDL, a synthetic data description language that provides flexibility in the types of data we can generate.
Active learning for real-time motion controllers
Authors: Cooper Seth , Hertzmann Aaron , Popović Zoran
Published: September 2007

This paper describes an approach to building real-time highly-controllable characters. A kinematic character controller is built on-the-fly during a capture session, and updated after each new motion clip is acquired. Active learning is used to identify which motion sequence the user should perform next, in order to improve the quality and responsiveness of the controller. Because motion clips are selected adaptively, we avoid the difficulty of manually determining which ones to capture, and can build complex controllers from scratch while significantly reducing the number of necessary motion samples.
Seam carving for content-aware image resizing
Authors: Avidan Shai , Shamir Ariel
Published: September 2007

Effective resizing of images should not only use geometric constraints, but consider the image content as well. We present a simple image operator called
seam carving
that supports content-aware image resizing for both reduction and expansion. A seam is an optimal 8-connected path of pixels on a
single
image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect ratio of an image. By applying these operators in both directions we can retarget the image to a new size. The selection and order of seams protect the content of the image, as defined by the energy function. Seam carving can also be used for image content enhancement and object removal. We support various visual saliency measures for defining the energy of an image, and can also include user input to guide the process. By storing the order of seams in an image we create
multi-size
images, that are able to continuously change in real time to fit a given size.
A finite element method for animating large viscoplastic flow
Authors: Bargteil Adam W. , Wojtan Chris , Hodgins Jessica K. , Turk Greg
Published: September 2007

We present an extension to Lagrangian finite element methods to allow for large plastic deformations of solid materials. These behaviors are seen in such everyday materials as shampoo, dough, and clay as well as in fantastic gooey and blobby creatures in special effects scenes. To account for plastic deformation, we explicitly update the linear basis functions defined over the finite elements during each simulation step. When these updates cause the basis functions to become ill-conditioned, we remesh the simulation domain to produce a new high-quality finite-element mesh, taking care to preserve the original boundary. We also introduce an enhanced plasticity model that preserves volume and includes creep and work hardening/softening. We demonstrate our approach with simulations of synthetic objects that squish, dent, and flow. To validate our methods, we compare simulation results to videos of real materials.
Algebraic point set surfaces
Authors: Guennebaud Gaël , Gross Markus
Published: September 2007

In this paper we present a new Point Set Surface (PSS) definition based on moving least squares (MLS) fitting of algebraic spheres. Our surface representation can be expressed by either a projection procedure or in implicit form. The central advantages of our approach compared to existing planar MLS include significantly improved stability of the projection under low sampling rates and in the presence of high curvature. The method can approximate or interpolate the input point set and naturally handles planar point clouds. In addition, our approach provides a reliable estimate of the mean curvature of the surface at no additional cost and allows for the robust handling of sharp features and boundaries. It processes a simple point set as input, but can also take significant advantage of surface normals to improve robustness, quality and performance. We also present an novel normal estimation procedure which exploits the properties of the spherical fit for both direction estimation and orientation propagation. Very efficient computational procedures enable us to compute the algebraic sphere fitting with up to 40 million points per second on latest generation GPUs.
The lightspeed automatic interactive lighting preview system
Authors: Ragan-Kelley Jonathan , Kilpatrick Charlie , Smith Brian W. , Epps Doug , Green Paul , Hery Christophe , Durand Frédo
Published: September 2007

We present an automated approach for high-quality preview of feature-film rendering during lighting design. Similar to previous work, we use a deep-framebuffer shaded on the GPU to achieve interactive performance. Our first contribution is to generate the deep-framebuffer and corresponding shaders automatically through data-flow analysis and compilation of the original scene. Cache compression reduces automatically-generated deep-framebuffers to reasonable size for complex production scenes and shaders. We also propose a new structure, the
indirect framebuffer
, that decouples shading samples from final pixels and allows a deep-framebuffer to handle antialiasing, motion blur and transparency efficiently. Progressive refinement enables fast feedback at coarser resolution. We demonstrate our approach in real-world production.