bluuebunny/crossref_metadata_2025_split huggingface dataset:
Melange
Authors: Madhavapeddy Anil , Ho Alex , Deegan Tim , Scott David , Sohan Ripduman 
Published: September 2007

Most implementations of critical Internet protocols are written in type-unsafe languages such as C or C++ and are regularly vulnerable to serious security and reliability problems. Type-safe languages eliminate many errors but are not used to due to the perceived performance overheads.
We combine two techniques to eliminate this performance penalty in a practical fashion: strong static typing and generative meta-programming. Static typing eliminates run-time type information by checking safety at compile-time and minimises dynamic checks. Meta-programming uses a single specification to abstract the low-level code required to transmit and receive packets.
Our domain-specific language, MPL, describes Internet packet protocols and compiles into fast, zero-copy code for both parsing and creating these packets. MPL is designed for implementing quirky Internet protocols ranging from the low-level: Ethernet, IPv4, ICMP and TCP; to the complex application-level: SSH, DNS and BGP; and even file-system protocols such as 9P.
We report on fully-featured SSH and DNS servers constructed using MPL and our OCaml framework Melange, and measure greater throughput, lower latency, better flexibility and more succinct source code than their C equivalents OpenSSH and BIND. Our quantitative analysis shows that the benefits of MPL-generated code overcomes the additional overheads of automatic garbage collection and dynamic bounds checking. Qualitatively, the flexibility of our approach shows that dramatic optimisations are easily possible.
Carbon
Authors: Kumar Sanjeev , Hughes Christopher J. , Nguyen Anthony 
Published: September 2007

Chip multiprocessors (CMPs) are now commonplace, and the number of cores on a CMP is likely to grow steadily. However, in order to harness the additional compute resources of a CMP, applications must expose their thread-level parallelism to the hardware. One common approach to doing this is to decompose a program into parallel "tasks" and allow an underlying software layer to schedule these tasks to different threads. Software task scheduling can provide good parallel performance as long as tasks are large compared to the software overheads.
We examine a set of applications from an important emerging domain: Recognition, Mining, and Synthesis (RMS). Many RMS applications are compute-intensive and have abundant thread-level parallelism, and are therefore good targets for running on a CMP. However, a significant number have small tasks for which software task schedulers achieve only limited parallel speedups.
We propose Carbon, a hardware technique to accelerate dynamic task scheduling on scalable CMPs. Carbon has relatively simple hardware, most of which can be placed far from the cores. We compare Carbon to some highly tuned software task schedulers for a set of RMS benchmarks with small tasks. Carbon delivers significant performance improvements over the best software scheduler: on average for 64 cores, 68% faster on a set of loop-parallel benchmarks, and 109% faster on aset of task-parallel benchmarks.
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.
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.
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).
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%.
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%).
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.
Fast triangle reordering for vertex locality and reduced overdraw
Authors: Sander Pedro V. , Nehab Diego , Barczak Joshua 
Published: September 2007

We present novel algorithms that optimize the order in which triangles are rendered, to improve post-transform vertex cache efficiency as well as for view-independent overdraw reduction. The resulting triangle orders perform on par with previous methods, but are orders magnitude faster to compute.
The improvements in processing speed allow us to perform the optimization right after a model is loaded, when more information on the host hardware is available. This allows our vertex cache optimization to often outperform other methods. In fact, our algorithms can even be executed interactively, allowing for re-optimization in case of changes to geometry or topology, which happen often in CAD/CAM applications. We believe that most real-time rendering applications will immediately benefit from these new results.
From the editors
Authors: Stafford Tom , Chau Patrick Y. K. 
Published: September 2007

Greetings from the Editorial Suite! Big things are going on here at your Data Base.
We've completely settled in to our new online manuscript review portal, which you can find linked at our site (http://the-database.org) or directly accessed through http://www.editorialmanager.com/sigmisdb/. Try it; you'll like it. It seems that more and more of the leading journals are going online with their reviewing processes. It makes great sense, and streamlines the process of reviewing and revising manuscripts mightily.
I was reminded by past Editor Detmar Straub that we're actually the oldest mainstream peer-reviewed MIS publication around. Having started life years ago as an in-house publication of the ACM SIGMIS (or, what used to be called "business information technology"), this publication has been through a number of evolutions.
Hang on, we're only getting started! We are just wrapping up our survey with Thomson ISI for cover-age in the Social Sciences Citation Index, we've launched an online portal for managing the review process, we've expanded coverage globally with our Global Co-Editor Patrick Chau in Hong Kong. There's more in the works; stay tuned.
As of this issue we bid adieu and good luck to our friend Denny Kramer, who has been Technical Editor for the publication for years. Denny got an offer he could not refuse (just remember to call him "Dean Kramer" next time you see him) and had to bow out of the Technical Editor duties. As of our next issue, Prof. Clint Lanier of the Center for the Study of Rhetoric and Applied Communication at The University of Memphis takes the reins. Welcome Clint!.
We have some very interesting research themed issues coming soon. The response to the call for papers for the Virtual Worlds issue was extensive; expect something extra-special from that within the year. We have an issue planned from selected top-tier papers from the new AIS conference in China, and we will be welcoming Al Hevner to our pages as Guest Editor for a very special issue on Software Testing, shortly.
Data Base - more than just database research. In fact, you'll find, and we heartily welcome, just about any topic in the area of information systems in our pages. Just as has been the case for years, and years and years. Did I say we're the oldest general MIS publication around?.
We welcome your participation in this fine tradition. Send us your papers at our submission portal, http://www.editorialmanager.com/sigmisdb/.
Visualization of web spaces
Authors: Turetken Ozgur , Sharda Ramesh 
Published: September 2007

The World Wide Web is a dominant global communication medium and knowledge repository. It is used by a great number of people with a variety of computer skills hence its usability is critical. As with many large information collections, the challenge with web usability is understanding the structure of a collection of information objects (web pages) to find relevant ones for satisfying a specific information need. Web sites are organized in a hyperlinked structure that somewhat addresses this challenge. However, this "connectedness" also causes the now well-known "lost in cyberspace" phenomenon where one may get confused within the complex organization of a web site. Meanwhile, information exploration on the web is not limited to browsing a web site. The problem of finding relevant information applies to a collection of pages that come from various web sites as in the case of the results of a "less than perfectly constructed" search query.
Information visualization has been proposed as a way to cope with these problems by taking advantage of people's innate perceptual skills to support their cognitive skills. Many paradigms have been proposed for the visual presentation of web spaces (i.e. structured or unstructured collection of web pages). This study surveys these paradigms to provide a map of where the research in this field is, and what directions future research and practice can take. For this, we introduce a classification scheme to help in the systematic understanding of web visualization and for providing a framework for the development of future visualizations.
Trading structure for randomness in wireless opportunistic routing
Authors: Chachulski Szymon , Jennings Michael , Katti Sachin , Katabi Dina 
Published: September 2007

Opportunistic routing is a recent technique that achieves high throughput in the face of lossy wireless links. The current opportunistic routing protocol, ExOR, ties the MAC with routing, imposing a strict schedule on routers' access to the medium. Although the scheduler delivers opportunistic gains, it misses some of the inherent features of the 802.11 MAC. For example, it prevents spatial reuse and thus may underutilize the wireless medium. It also eliminates the layering abstraction, making the protocol less amenable to extensions to alternate traffic types such as multicast.
This paper presents MORE, a MAC-independent opportunistic routing protocol. MORE randomly mixes packets before forwarding them. This randomness ensures that routers that hear the same transmission do not forward the same packets. Thus, MORE needs no special scheduler to coordinate routers and can run directly on top of 802.11. Experimental results from a 20-node wireless testbed show that MORE's median unicast throughput is 22% higher than ExOR, and the gains rise to 45% over ExOR when there is a chance of spatial reuse. For multicast, MORE's gains increase with the number of destinations, and are 35-200% greater than ExOR.
Etherfuse
Authors: Elmeleegy Khaled , Cox Alan L. , Ng T. S. Eugene 
Published: September 2007

Ethernet is pervasive. This is due in part to its ease of use. Equipment can be added to an Ethernet network with little or no manual configuration. Furthermore, Ethernet is self-healing in the event of equipment failure or removal. However, there are scenarios where a local event can lead to network-wide packet loss and duplication due to slow or faulty reconfiguration of the spanning tree. Moreover, in some cases the packet loss and duplication may persist indefinitely.
To address these problems, we introduce the EtherFuse, a new device that can be inserted into an existing Ethernet to speed the reconfiguration of the spanning tree and suppress packet duplication. EtherFuse is backward compatible and requires no change to the existing hardware, software, or protocols. We describe a prototype EtherFuse implementation and experimentally demonstrate its effectiveness. Specifically, we characterize how quickly it responds to network failures, its ability to reduce packet loss and duplication, and its benefits on the end-to-end performance of common applications.