bluuebunny/crossref_metadata_2025 huggingface dataset:
ENERGY EFFICIENT GEOGRAPHIC ROUTING ALGORITHMS IN WIRELESS SENSOR NETWORK
Authors: CHEN TSENG-YI , WEI HSIN-WEN , LEE CHE-RUNG , HUANG FU-NAN , HSU TASN-SHENG , SHIH WEI-KUAN
Published: July 2013

Over the past decade, energy efficiency has consistently been a critical research topic in the field of wireless sensor networks. In wireless networks, signal interference often leads to power waste in a sensor node. Several SINR-based routing algorithms designed for energy efficiency or interference avoidance had been proposed. However, they are either too complex to be useful in practices or may slow in routing computation speed. In this paper, two energy efficient geographic routing algorithms (EEGRA) for wireless sensor network are proposed to address the power consumption issue while considering the routing computation speed. The first algorithm take the value of interference into the routing cost function, and uses it in the routing decision. The second algorithm transforms the problem into a constrained optimization problem, and solves it by searching the optimal discretized interference level. We adopt four geographic routing algorithms: GOAFR+, Face Routing, GPSR, and RandHT, in EEGRA algorithms and compare them with three other routing methods in terms of power consumption and computation cost for the grid and irregular sensor topologies. The experimental result shows that the EEGRA algorithms reduce energy consumption by 30–50% comparing to geographic routing methods. In addition, the time complexity of EEGRA algorithms is similar to the geographic greedy routing methods, which is much faster than the optimal SINR-based algorithm.
COMPARING SYSTEM SELECTION METHODS FOR THE COMBINATORIAL FUSION OF MULTIPLE RETRIEVAL SYSTEMS
Authors: LIU CHUN-YI , TANG CHUAN-YI , HSU D. FRANK
Published: July 2013

Combining multiple information retrieval (IR) systems has been shown to improve performance over individual systems. However, it remains a challenging problem to determine when and how a set of individual systems should to be combined. In this paper, we investigate these issues using combinatorial fusion analysis and five data sets provide by TREC 2, 3, 4, 5, and 6. In particular, we compare the performance of combining six IR systems selected by random choice vs. by performance measurement from these five TREC data sets. Two experiments are conducted, which include: (1) combination of two systems and their performance outcome in terms of performance ratio and cognitive diversity, and (2) combinatorial fusion of t-systems, t = 2 to 6, using both score and rank combinations and exploration of the effect of diversity on the performance outcome. It is demonstrated in both experiments that combination of two or more systems improves the performance more significantly when the systems are selected by performance evaluation than those selected by random choice. Our work provides a distinctive method of system selection for the combination of multiple retrieval systems.
COMPUTATIONAL METHODOLOGIES FOR VIBRATION-BASED DAMAGE ASSESSMENT OF STRUCTURES
Authors: SRINIVAS V. , ANTONY JEYASEHAR C. , RAMANJANEYULU K.
Published: July 2013

In the present work, computational methodologies based on artificial neural networks and genetic algorithms (GA) have been developed for identification of structural damage utilizing vibration data. The natural frequencies and mode shapes obtained from the finite element analysis for the first few modes have been considered for this purpose. A multi-stage hybrid methodology combining the modal strain energy criteria with GA has also been proposed, which showed improved damage identification capability as compared to the conventional GA, and proved to be computationally efficient. To demonstrate the efficiency of the proposed hybrid approach, numerical studies have been carried out on the truss structure. The efficacy of mode shape expansion in conjunction with GA is demonstrated for damage identification of reinforced concrete beam based on experimental modal data.
AN AGENT MODEL FOR THE HIGH-END GAMERS MARKET
Authors: ADRIAANSEN TEUN , ARMBRUSTER DIETER , KEMPF KARL , LI HONGMIN
Published: July 2013

Understanding the driving forces in the markets of their products is a basic necessity for any business. Quantitative models are either aggregated over large market segments or restricted to utility models of an individual's buying decision. While the aggregate models acknowledge that customer interactions are important they do not model them and hence have no way to adjust their model to changing business environments. This paper bridges the gap between individual decisions and the overall market behavior using agent based simulations to model the sales of computer chips in the high-end gamers market. The simulation environment is dynamic and models the succession of 19 products introduced over a 40 month time horizon which includes the recession of 2008–2010. Simulated sales are compared to actual sales data and are used to adjust the parametrization of the agents and their environment. We found that only two agent parameters are sufficient to obtain a very reasonable fit between simulations and data: The amount of money available for the gaming hobby and a parameter related to the gaming success of the high-end gamers.
Synthesis and DNA photocleavage studies of novel porphyrin diarylthiazoles
Authors: Kumar Dalip , Chandrashekar K.P. , Mishra Bhupendra
Published: July 2013

A convenient and regioselective synthesis of porphyrin diarylthiazoles is reported via the reactions of alkynyl(aryl)iodonium tosylates and porphyrin thioamides. Among the synthesized porphyrin diarylthiazoles, compounds 6d and 6f have shown significant interactions with ctDNA and exhibited efficient DNA photocleavage.
A BIO-INSPIRED POLYDOPAMINE APPROACH TO PREPARATION OF GOLD-COATED Fe3O4 CORE–SHELL NANOPARTICLES: SYNTHESIS, CHARACTERIZATION AND MECHANISM
Authors: AN PENG , ZUO FANG , LI XINHUA , WU YUANPENG , ZHANG JUNHUA , ZHENG ZHAOHUI , DING XIAOBIN , PENG YUXING
Published: July 2013

A biomimetic and facile approach for integrating Fe 3 O 4 and Au with polydopamine (PDA) was proposed to construct gold-coated Fe 3 O 4 nanoparticles ( Fe 3 O 4@ Au – PDA ) with a core–shell structure by coupling in situ reduction with a seed-mediated method in aqueous solution at room temperature. The morphology, structure and composition of the core–shell structured Fe 3 O 4@ Au – PDA nanoparticles were characterized by transmission electron microscopy (TEM), X-ray powder diffraction (XRD) and X-ray photoelectron spectrometry (XPS). The formation process of Au shell was assessed using a UV-Vis spectrophotometer. More importantly, according to investigating changes in PDA molecules by Fourier transform infrared spectroscopy (FTIR) and in preparation process of the zeta-potential data of nanoparticles, the mechanism of core–shell structure formation was proposed. Firstly, PDA-coated Fe 3 O 4 are obtained using dopamine (DA) self-polymerization to form thin and surface-adherent PDA films onto the surface of a Fe 3 O 4 "core". Then, Au seeds are attached on the surface of PDA-coated Fe 3 O 4 via electrostatic interaction in order to serve as nucleation centers catalyzing the reduction of Au 3+ to Au 0 by the catechol groups in PDA. Accompanied by the deposition of Au , PDA films transfer from the surface of Fe 3 O 4 to that of Au as stabilizing agent. In order to confirm the reasonableness of this mechanism, two verification experiments were conducted. The presence of PDA on the surface of Fe 3 O 4@ Au – PDA nanoparticles was confirmed by the finding that glycine or ethylenediamine could be grafted onto Fe 3 O 4@ Au – PDA nanoparticles through Schiff base reaction. In addition, Fe 3 O 4@ Au – DA nanoparticles, in which DA was substituted for PDA, were prepared using the same method as that for Fe 3 O 4@ Au – PDA nanoparticles and characterized by UV-Vis, TEM and FTIR. The results validated that DA possesses multiple functions of attaching Au seeds as well as acting as both reductant and stabilizing agent, the same functions as those of PDA.
TEMPLATE STRATEGY FOR THE SYNTHESIS OF Cu2O–Pt HIERARCHICAL HETEROSTRUCTURES FOR THE DEGRADATION OF METHYLENE BLUE
Authors: BAO SHIYONG , ZHU HAN , WANG PAN , ZOU MEILING , DU MINGLIANG , ZHANG MING
Published: July 2013

A facile and green route was introduced to synthesize Pt nanoparticles (PtNPs) immobilized on Cu 2 O octahedrons to form Cu 2 O – Pt hierarchical heterostructure. Transmission electron microscopy (TEM), field emission scanning electron microscopy (FE-SEM), high resolution transmission electron microscopy (HRTEM), X-ray photoelectron spectroscopy (XPS) and X-ray diffraction (XRD) were employed to study their morphology, chemical and crystallographic properties of the Cu 2 O – Pt hierarchical heterostructure. These novel Cu 2 O – Pt hierarchical heterostructures show fascinating degradations of methylene blue (MB), due to the suppressed electron/hole recombination phenomena and the efficient ability to capture the light.
Detection and classification of peer-to-peer traffic
Authors: Gomes João V. , Inácio Pedro R. M. , Pereira Manuela , Freire Mário M. , Monteiro Paulo P.
Published: July 2013

The emergence of new Internet paradigms has changed the common properties of network data, increasing the bandwidth consumption and balancing traffic in both directions. These facts raise important challenges, making it necessary to devise effective solutions for managing network traffic. Since traditional methods are rather ineffective and easily bypassed, particular attention has been paid to the development of new approaches for traffic classification. This article surveys the studies on peer-to-peer traffic detection and classification, making an extended review of the literature. Furthermore, it provides a comprehensive analysis of the concepts and strategies for network monitoring.
Survey on application-layer mechanisms for speech quality adaptation in VoIP
Authors: Carvalho Leandro Silva Galvão De , Mota Edjair De Souza
Published: July 2013

VoIP calls are sensitive to several impairments, such as delay and packet loss. One way to overcome these problems is by adaptively adjusting application-layer parameters to keep a minimum speech quality level. At the heart of self-adaptive systems lies a
feedback loop
, which consists of four key activities: monitoring, analysis, planning, and execution. Nevertheless, the existing adaptive approaches to QoS control of VoIP do not explicitly exhibit this feedback loop. Bringing it to surface can help developers in designing more robust and human-independent VoIP systems. This survey presents a comprehensive review of the current state-of-the-art research on speech quality adaptation of VoIP systems at the application layer and some research challenges on this subject.
Exploring pattern-aware travel routes for trajectory search
Authors: Wei Ling-Yin , Peng Wen-Chih , Lee Wang-Chien
Published: July 2013

With the popularity of positioning devices, Web 2.0 technology, and trip sharing services, many users are willing to log and share their trips on the Web. Thus, trip planning Web sites are able to provide some new services by inferring Regions-Of-Interest (ROIs) and recommending popular travel routes from trip trajectories. We argue that simply providing some travel routes consisting of popular ROIs to users is not sufficient. To tour around a wide geographical area, for example, a city, some users may prefer a trip to visit as many ROIs as possible, while others may like to stop by only a few ROIs for an in-depth visit. We refer to a trip fitting the former user group as an
in-breadth trip
and a trip suitable for the latter user group as an
in-depth trip
. Prior studies on trip planning have focused on mining ROIs and travel routes without considering these different preferences. In this article, given a spatial range and a user preference of depth/breadth specified by a user, we develop a
Pattern-Aware Trajectory Search
(PATS) framework to retrieve the top
K
trajectories passing through popular ROIs. PATS is novel because the returned travel trajectories, discovered from travel patterns hidden in trip trajectories, may represent the most valuable travel experiences of other travelers fitting the user's trip preference in terms of depth or breadth. The PATS framework comprises two components:
travel behavior exploration
and
trajectory search
. The travel behavior exploration component determines a set of ROIs along with their attractive scores by considering not only the popularity of the ROIs but also the travel sequential relationships among the ROIs. To capture the travel sequential relationships among ROIs and to derive their attractive scores, a user movement graph is constructed. For the trajectory search component of PATS, we formulate two trajectory score functions, the depth-trip score function and the breadth-trip score function, by taking into account the number of ROIs in a trajectory and their attractive scores. Accordingly, we propose an algorithm, namely,
Bounded Trajectory Search
(BTS), to efficiently retrieve the top
K
trajectories based on the two trajectory scores. The PATS framework is evaluated by experiments and user studies using a real dataset. The experimental results demonstrate the effectiveness and the efficiency of the proposed PATS framework.
Markov models of social dynamics
Authors: Gintis Herbert
Published: July 2013

This article shows how agent-based models of social dynamics can be treated rigorously and analytically as finite Markov processes, and their long-run properties are then given by an expanded version of the ergodic theorem for Markov processes. A Markov process model of a simplified market economy shows the fruitfulness of this approach.
Introduction to the special issue on multiword expressions
Authors: Ramisch Carlos , Villavicencio Aline , Kordoni Valia
Published: July 2013

We are in 2013, and multiword expressions have been around for a while in the computational linguistics research community. Since the first ACL workshop on MWEs 12 years ago in Sapporo, Japan, much has been discussed, proposed, experimented, evaluated and argued about MWEs. And yet, they deserve the publication of a whole special issue of the
ACM Transactions on Speech and Language Processing
. But what is it about multiword expressions that keeps them in fashion? Who are the people and the institutions who perform and publish groundbreaking fundamental and applied research in this field? What is the place and the relevance of our lively research community in the bigger picture of computational linguistics? Where do we come from as a community, and most importantly, where are we heading? In this introductory article, we share our point of view about the answers to these questions and introduce the articles that compose the current special issue.
How many multiword expressions do people know?
Authors: Church Kenneth
Published: July 2013

What is a multiword expression (MWE) and how many are there? Mark Liberman gave a great invited talk at ACL-89, titled “How Many Words Do People Know?” where he spent the entire hour questioning the question. Many of the same questions apply to multiword expressions. What is a word? An expression? What is many? What is a person? What does it mean to know? Rather than answer these questions, this article will use them as Liberman did, as an excuse for surveying how such issues are addressed in a variety of fields: computer science, Web search, linguistics, lexicography, educational testing, psychology, statistics, and so on.
Modeling the internal variability of multiword expressions through a pattern-based method
Authors: Nissim Malvina , Zaninello Andrea
Published: July 2013

The issue of internal variability of multiword expressions (MWEs) is crucial towards their identification and extraction in running text. We present a corpus-supported and computational study on Italian MWEs, aimed at defining an automatic method for modeling internal variation, exploiting frequency and part-of-speech (POS) information. We do so by deriving an XML-encoded lexicon of MWEs based on a manually compiled dictionary, which is then projected onto a a large corpus. Since a search for fixed forms suffers from low recall, while an unconstrained flexible search for lemmas yields a loss in precision, we suggest a procedure aimed at maximizing precision in the identification of MWEs within a flexible search. Our method builds on the idea that internal variability can be modelled via the novel introduction ofvariation patterns, which work over POS patterns, and can be used as working tools for controlling precision. We also compare the performance of variation patterns to that of association measures, and explore the possibility of using variation patterns in MWE extraction in addition to identification. Finally, we suggest that corpus-derived, pattern-related information can be included in the original MWE lexicon by means of an enriched coding and the creation of an XML-based repository of patterns.
Notional machines and introductory programming education
Authors: Sorva Juha
Published: July 2013

This article brings together, summarizes, and comments on several threads of research that have contributed to our understanding of the challenges that novice programmers face when learning about the runtime dynamics of programs and the role of the computer in program execution. More specifically, the review covers the literature on programming misconceptions, the cognitive theory of mental models, constructivist theory of knowledge and learning, phenomenographic research on experiencing programming, and the theory of threshold concepts. These bodies of work are examined in relation to the concept of a “notional machine”—an abstract computer for executing programs of a particular kind. As a whole, the literature points to notional machines as a major challenge in introductory programming education. It is argued that instructors should acknowledge the notional machine as an explicit learning objective and address it in teaching. Teaching within some programming paradigms, such as object-oriented programming, may benefit from using multiple notional machines at different levels of abstraction. Pointers to some promising pedagogical techniques are provided.
Trapezius muscle EMG as predictor of mental stress
Authors: Wijsman Jacqueline , Grundlehner Bernard , Penders Julien , Hermens Hermie
Published: July 2013

Stress is a growing problem in society and can cause musculoskeletal complaints. It would be useful to measure stress for prevention of stress-related health problems. An experiment is described in which EMG signals of the upper trapezius muscle were measured with a wireless system during three different stressful conditions: a calculation task (the Norinder test), a logical puzzle task and a memory task. The latter two tests were newly designed and aimed at creating circumstances that are similar to work stress. Amplitudes of the EMG signals were significantly higher during stress compared to rest (+2.6% of reference contraction level) and relative time with EMG gaps was lower during stress (−14.3% of time). Also, mean and median frequencies were significantly lower during stress than during rest (−8.6 and −8.8 Hz, respectively). EMG amplitude increased not only from rest to stress conditions, but also
during
stressful conditions and decreased
during
relaxation periods. EMG features correlated with subjectively indicated stress levels (correlations of 0.32 with RMS and −0.32 with relative gaptime). The results indicate that EMG is a useful parameter to detect stress. Together with other physiological sensors, EMG sensors can be included in a wireless system for ambulatory monitoring of stress levels.
Addressing network-on-chip router transient errors with inherent information redundancy
Authors: Yu Qiaoyan , Zhang Meilin , Ampadu Paul
Published: July 2013

We exploit the inherent information redundancy in the control path of Network-on-Chip (NoC) routers to manage transient errors, preventing packet loss and misrouting. Outputs of the routing arbitration units in NoC routers can be used to determine arbitration failures, because the valid arbitration outputs are a subset of all possible values. This feature is exploited to detect and correct logic and register errors in the router arbitration control path. The proposed method is complementary to other error management methods for NoC routers. An analytical reliability model of our method is provided, including parameters such as logic unit size, different error rates for logic gates and registers, and the location of faulty elements. Compared to triple-modular redundancy (TMR), the proposed method improves the arbiter reliability by two orders of magnitude while reducing the total area and power by 43% and 64%, respectively. In the presented case studies, two traffic traces from the PARSEC benchmark suite are used to evaluate the average latency and energy consumption. Simulations performed on a 4× 4 NoC show that our method reduces the average latency by up to 50% and reduces average energy by up to 70% compared to other methods.
An efficient, low-cost routing framework for convex mesh partitions to support virtualization
Authors: Sem-Jacobsen Frank Olaf , Rodrigo Samuel , Skeie Tor , Strano Alessandro , Bertozzi Davide
Published: July 2013

At the core of an efficient chip multiprocessors (CMP) is support for unicast and multicast routing, low implementation costs, and the ability to isolate concurrent applications with maximum utilization of the CMP. We present an efficient logic-based unicast and multicast routing algorithm that guarantees isolation of local application traffic within any near-convex region on the chip, and the algorithms to recognize supported partitions and configure the cores accordingly. Evaluations show that the routing algorithm has a 57% more compact implementation than a recent multicast solution with the same coverage, and it achieves 5% higher throughput with 13% lower latency.
Demo hour
Authors: Ludi Damien , Peillex Colin , Spanjers Daan , Cross Andrew , Cutrell Ed , Thies Bill , Boulay Mickael
Published: July 2013

Demo Hour highlights new prototypes and projects that exemplify innovation and novel forms of interaction.

Audrey Desjardins, Editor
Taking the fast RIDE
Authors: Arnowitz Jonathan
Published: July 2013

Evaluation and usability as a practice area has diversified its approaches, broadened the spectrum of UX issues it addresses, and extended its contribution into deeper levels of product-development decision making. This forum addresses conceptual, methodological, and professional issues that arise in the field's continuing effort to contribute robust information about users to product planning and design.

David Siegel and Susan Dray, Editors
Interactive partner control in close interactions for real-time applications
Authors: Ho Edmond S. L. , Chan Jacky C. P. , Komura Taku , Leung Howard
Published: July 2013

This article presents a new framework for synthesizing motion of a virtual character in response to the actions performed by a user-controlled character in real time. In particular, the proposed method can handle scenes in which the characters are closely interacting with each other such as those in partner dancing and fighting. In such interactions, coordinating the virtual characters with the human player automatically is extremely difficult because the system has to predict the intention of the player character. In addition, the style variations from different users affect the accuracy in recognizing the movements of the player character when determining the responses of the virtual character. To solve these problems, our framework makes use of the spatial relationship-based representation of the body parts called interaction mesh, which has been proven effective for motion adaptation. The method is computationally efficient, enabling real-time character control for interactive applications. We demonstrate its effectiveness and versatility in synthesizing a wide variety of motions with close interactions.
Paragon
Authors: Delimitrou Christina , Kozyrakis Christos
Published: July 2013

Large-scale datacenters (DCs) host tens of thousands of diverse applications each day. However, interference between colocated workloads and the difficulty to match applications to one of the many hardware platforms available can degrade performance, violating the quality of service (QoS) guarantees that many cloud workloads require. While previous work has identified the impact of heterogeneity and interference, existing solutions are computationally intensive, cannot be applied online and do not scale beyond few applications.

We present Paragon, an online and scalable DC scheduler that is heterogeneity and interference-aware. Paragon is derived from robust analytical methods and instead of profiling each application in detail, it leverages information the system already has about applications it has previously seen. It uses collaborative filtering techniques to quickly and accurately classify an unknown, incoming workload with respect to heterogeneity and interference in multiple shared resources, by identifying similarities to previously scheduled applications. The classification allows Paragon to greedily schedule applications in a manner that minimizes interference and maximizes server utilization. Paragon scales to tens of thousands of servers with marginal scheduling overheads in terms of time or state.

We evaluate Paragon with a wide range of workload scenarios, on both small and large-scale systems, including 1,000 servers on EC2. For a 2,500-workload scenario, Paragon enforces performance guarantees for 91% of applications, while significantly improving utilization. In comparison, heterogeneity-oblivious, interference-oblivious and least-loaded schedulers only provide similar guarantees for 14%, 11% and 3% of workloads. The differences are more striking in oversubscribed scenarios where resource efficiency is more critical.
ConAir
Authors: Zhang Wei , de Kruijf Marc , Li Ang , Lu Shan , Sankaralingam Karthikeyan
Published: July 2013

Many concurrency bugs are hidden in deployed software and cause severe failures for
end-users
. When they finally manifest and become known by
developers
, they are difficult to fix correctly. To support end-users, we need techniques that help software survive hidden concurrency bugs during production runs. To help developers, we need techniques that fix exposed concurrency bugs.

The state-of-the-art techniques on concurrency-bug fixing and survival only satisfy a subset of four important properties: compatibility, correctness, generality, and performance.We aim to develop a system that satisfies all of these four properties. To achieve this goal, we leverage two observations: (1) rolling back a
single
thread is sufficient to recover from most concurrency-bug failures; (2) reexecuting an
idempotent
region, which requires no memory-state checkpoint, is sufficient to recover from many concurrency-bug failures. Our system ConAir includes a static analysis component that automatically identifies potential failure sites, a static analysis component that automatically identifies the idempotent code regions around every failure site, and a code-transformation component that inserts rollback-recovery code around the identified idempotent regions.

We evaluated ConAir on 10 real-world concurrency bugs in widely used C/C++ open-source applications. These bugs cover different types of failure symptoms and root causes. Quantitatively, ConAir helps software survive failures caused by all of these bugs with negligible run-time overhead (<1%) and short recovery time. Qualitatively, ConAir can help recover from failures caused by unknown bugs. It guarantees that program semantics remain unchanged and requires no change to operating systems or hardware.
A study of the scalability of stop-the-world garbage collectors on multicores
Authors: Gidra Lokesh , Thomas Gaël , Sopena Julien , Shapiro Marc
Published: July 2013

Large-scale multicore architectures create new challenges for garbage collectors (GCs). In particular, throughput-oriented stop-the-world algorithms demonstrate good performance with a small number of cores, but have been shown to degrade badly beyond approximately 8 cores on a 48-core with OpenJDK 7. This negative result raises the question whether the stop-the-world design has intrinsic limitations that would require a radically different approach. Our study suggests that the answer is no, and that there is no compelling scalability reason to discard the existing highly-optimised throughput-oriented GC code on contemporary hardware. This paper studies the default throughput-oriented garbage collector of OpenJDK 7, called Parallel Scavenge. We identify its bottlenecks, and show how to eliminate them using well-established parallel programming techniques. On the SPECjbb2005, SPECjvm2008 and DaCapo 9.12 benchmarks, the improved GC matches the performance of Parallel Scavenge at low core count, but scales well, up to 48~cores.
Safe and automatic live update for operating systems
Authors: Giuffrida Cristiano , Kuijsten Anton , Tanenbaum Andrew S.
Published: July 2013

Increasingly many systems have to run all the time with no downtime allowed. Consider, for example, systems controlling electric power plants and e-banking servers. Nevertheless, security patches and a constant stream of new operating system versions need to be deployed without stopping running programs. These factors naturally lead to a pressing demand for live update---upgrading all or parts of the operating system without rebooting. Unfortunately, existing solutions require significant manual intervention and thus work reliably only for small operating system patches.

In this paper, we describe an automated system for live update that can safely and automatically handle major upgrades without rebooting. We have implemented our ideas in Proteos, a new research OS designed with live update in mind. Proteos relies on system support and nonintrusive instrumentation to handle even very complex updates with minimal manual effort. The key novelty is the idea of
state quiescence
, which allows updates to happen only in safe and predictable system states. A second novelty is the ability to automatically perform transactional live updates at the
process level
, ensuring a safe and
stable
update process. Unlike prior solutions, Proteos supports automated state transfer, state checking, and
hot rollback
. We have evaluated Proteos on 50 real updates and on novel live update scenarios. The results show that our techniques can effectively support both simple and complex updates, while outperforming prior solutions in terms of flexibility, security, reliability, and stability of the update process.
Automated repair of binary and assembly programs for cooperating embedded devices
Authors: Schulte Eric , DiLorenzo Jonathan , Weimer Westley , Forrest Stephanie
Published: July 2013

We present a method for automatically repairing arbitrary software defects in embedded systems, which have limited memory, disk and CPU capacities, but exist in great numbers. We extend evolutionary computation (EC) algorithms that search for valid repairs at the source code level to assembly and ELF format binaries, compensating for limited system resources with several algorithmic innovations. Our method does not require access to the source code or build toolchain of the software under repair, does not require program instrumentation, specialized execution environments, or virtual machines, or prior knowledge of the bug type.

We repair defects in ARM and x86 assembly as well as ELF binaries, observing decreases of 86% in memory and 95% in disk requirements, with 62% decrease in repair time, compared to similar source-level techniques. These advances allow repairs previously possible only with C source code to be applied to any ARM or x86 assembly or ELF executable. Efficiency gains are achieved by introducing stochastic fault localization, with much lower overhead than comparable deterministic methods, and low-level program representations.

When distributed over multiple devices, our algorithm finds repairs faster than predicted by naive parallelism. Four devices using our approach are five times more efficient than a single device because of our collaboration model. The algorithm is implemented on Nokia N900 smartphones, with inter-phone communication fitting in 900 bytes sent in 7 SMS text messages per device per repair on average.
HOTL
Authors: Xiang Xiaoya , Ding Chen , Luo Hao , Bao Bin
Published: July 2013

The locality metrics are many, for example, miss ratio to test performance, data footprint to manage cache sharing, and reuse distance to analyze and optimize a program. It is unclear how different metrics are related, whether one subsumes another, and what combination may represent locality completely.

This paper first derives a set of formulas to convert between five locality metrics and gives the condition for correctness. The transformation is analogous to differentiation and integration used to convert between higher order polynomials. As a result, these metrics can be assigned an order and organized into a hierarchy.

Using the new theory, the paper then develops two techniques: one measures the locality in real time without special hardware support, and the other predicts multicore cache interference without parallel testing. The paper evaluates them using sequential and parallel programs as well as for a parallel mix of sequential programs.
Traffic management
Authors: Dashti Mohammad , Fedorova Alexandra , Funston Justin , Gaud Fabien , Lachaize Renaud , Lepers Baptiste , Quema Vivien , Roth Mark
Published: July 2013

NUMA systems are characterized by Non-Uniform Memory Access times, where accessing data in a remote node takes longer than a local access. NUMA hardware has been built since the late 80's, and the operating systems designed for it were optimized for access locality. They co-located memory pages with the threads that accessed them, so as to avoid the cost of remote accesses. Contrary to older systems, modern NUMA hardware has much smaller remote wire delays, and so remote access costs per se are not the main concern for performance, as we discovered in this work. Instead,
congestion on memory controllers and interconnects
, caused by memory traffic from data-intensive applications, hurts performance a lot more. Because of that, memory placement algorithms must be redesigned to target traffic congestion. This requires an arsenal of techniques that go beyond optimizing locality. In this paper we describe
Carrefour
, an algorithm that addresses this goal. We implemented
Carrefour
in Linux and obtained performance improvements of up to 3.6 relative to the default kernel, as well as significant improvements compared to NUMA-aware patchsets available for Linux.
Carrefour
never hurts performance by more than 4% when memory placement cannot be improved. We present the design of
Carrefour
, the challenges of implementing it on modern hardware, and draw insights about hardware support that would help optimize system software on future NUMA systems.
Portable performance on heterogeneous architectures
Authors: Phothilimthana Phitchaya Mangpo , Ansel Jason , Ragan-Kelley Jonathan , Amarasinghe Saman
Published: July 2013

Trends in both consumer and high performance computing are bringing not only more cores, but also increased heterogeneity among the computational resources within a single machine. In many machines, one of the greatest computational resources is now their graphics coprocessors (GPUs), not just their primary CPUs. But GPU programming and memory models differ dramatically from conventional CPUs, and the relative performance characteristics of the different processors vary widely between machines. Different processors within a system often perform best with different algorithms and memory usage patterns, and achieving the best overall performance may require mapping portions of programs across all types of resources in the machine.

To address the problem of efficiently programming machines with increasingly heterogeneous computational resources, we propose a programming model in which the best mapping of programs to processors and memories is determined empirically. Programs define choices in how their individual algorithms may work, and the compiler generates further choices in how they can map to CPU and GPU processors and memory systems. These choices are given to an empirical autotuning framework that allows the space of possible implementations to be searched at installation time. The rich choice space allows the autotuner to construct poly-algorithms that combine many different algorithmic techniques, using both the CPU and the GPU, to obtain better performance than any one technique alone. Experimental results show that algorithmic changes, and the varied use of both CPUs and GPUs, are necessary to obtain up to a 16.5x speedup over using a single program configuration for all architectures.
DDOS
Authors: Hunt Nicholas , Bergan Tom , Ceze Luis , Gribble Steven D.
Published: July 2013

Nondeterminism complicates the development and management of distributed systems, and arises from two main sources: the local behavior of each individual node as well as the behavior of the network connecting them. Taming nondeterminism effectively requires dealing with both sources.

This paper proposes DDOS, a system that leverages prior work on deterministic multithreading to offer: 1) space-efficient record/replay of distributed systems; and 2) fully deterministic distributed behavior. Leveraging deterministic behavior at each node makes outgoing messages strictly a function of explicit inputs. This allows us to record the system by logging just message's arrival time, not the contents. Going further, we propose and implement an algorithm that makes all communication between nodes deterministic by scheduling communication onto a global logical timeline.

We implement both algorithms in a system called DDOS and evaluate our system with parallel scientific applications, an HTTP/memcached system and a distributed microbenchmark with a high volume of peer-to-peer communication. Our results show up to two orders of magnitude reduction in log size of record/replay, and that distributed systems can be made deterministic with an order of magnitude of overhead.
Improving processor efficiency by statically pipelining instructions
Authors: Finlayson Ian , Davis Brandon , Gavin Peter , Uh Gang-Ryung , Whalley David , Själander Magnus , Tyson Gary
Published: July 2013

A new generation of applications requires reduced power consumption without sacrificing performance. Instruction pipelining is commonly used to meet application performance requirements, but some implementation aspects of pipelining are inefficient with respect to energy usage. We propose static pipelining as a new instruction set architecture to enable more efficient instruction flow through the pipeline, which is accomplished by exposing the pipeline structure to the compiler. While this approach simplifies hardware pipeline requirements, significant modifications to the compiler are required. This paper describes the code generation and compiler optimizations we implemented to exploit the features of this architecture. We show that we can achieve performance and code size improvements despite a very low-level instruction representation. We also demonstrate that static pipelining of instructions reduces energy usage by simplifying hardware, avoiding many unnecessary operations, and allowing the compiler to perform optimizations that are not possible on traditional architectures.
Automatic dataflow model extraction from modal real-time stream processing applications
Authors: Geuns Stefan J. , Hausmans Joost P.H.M. , Bekooij Marco J.G.
Published: July 2013

Many real-time stream processing applications are initially described as a sequential application containing while-loops, which execute for an unknown number of iterations. These modal applications have to be executed in parallel on an MPSoC system in order to meet their real-time throughput constraints. However, no suitable approach exists that can automatically derive a temporal analysis model from a sequential specification containing while- loops with an unknown number of iterations.

This paper introduces an approach to the automatic generation of a Structured Variable-rate Phased Dataflow (SVPDF) model from a sequential specification of a modal application. The real-time requirements of an application can be analyzed despite the presence of while-loops with an unknown number of iterations. It is shown that an algorithm that has a polynomial time computational complexity can be applied on the generated SVPDF model to determine whether a throughput constraint can be met. The enabler for the automatic generation of an SVPDF model is the decoupling of synchronization between tasks that contain different while-loops. A DVB-T radio transceiver illustrates the derivation of the SVPDF model.
Formal verification of SSA-based optimizations for LLVM
Authors: Zhao Jianzhou , Nagarakatte Santosh , Martin Milo M.K. , Zdancewic Steve
Published: July 2013

Modern compilers, such as LLVM and GCC, use a
static single assignment
(SSA) intermediate representation (IR) to simplify and enable many advanced optimizations. However, formally verifying the correctness of SSA-based optimizations is challenging because SSA properties depend on a function's entire control-flow graph.

This paper addresses this challenge by developing a proof technique for proving SSA-based program invariants and compiler optimizations. We use this technique in the Coq proof assistant to create mechanized correctness proofs of several "micro" transformations that form the building blocks for larger SSA optimizations. To demonstrate the utility of this approach, we formally verify a variant of LLVM's mem2reg transformation in Vellvm, a Coq-based formal semantics of the LLVM IR. The extracted implementation generates code with performance comparable to that of LLVM's unverified implementation.
Natural proofs for structure, data, and separation
Authors: Qiu Xiaokang , Garg Pranav , Ştefănescu Andrei , Madhusudan Parthasarathy
Published: July 2013

We propose natural proofs for reasoning with programs that manipulate data-structures against specifications that describe the structure of the heap, the data stored within it, and separation and framing of sub-structures. Natural proofs are a subclass of proofs that are amenable to completely automated reasoning, that provide sound but incomplete procedures, and that capture common reasoning tactics in program verification. We develop a dialect of separation logic over heaps, called Dryad, with recursive definitions that avoids explicit quantification. We develop ways to reason with heaplets using classical logic over the theory of sets, and develop natural proofs for reasoning using proof tactics involving disciplined unfoldings and formula abstractions. Natural proofs are encoded into decidable theories of first-order logic so as to be discharged using SMT solvers.

We also implement the technique and show that a large class of more than 100 correct programs that manipulate data-structures are amenable to full functional correctness using the proposed natural proof method. These programs are drawn from a variety of sources including standard data-structures, the Schorr-Waite algorithm for garbage collection, a large number of low-level C routines from the Glib library and OpenBSD library, the Linux kernel, and routines from a secure verified OS-browser project. Our work is the first that we know of that can handle such a wide range of full functional verification properties of heaps automatically, given pre/post and loop invariant annotations. We believe that this work paves the way for deductive verification technology to be used by programmers who do not (and need not) understand the internals of the underlying logic solvers, significantly increasing their applicability in building reliable systems.
TRANSIT
Authors: Udupa Abhishek , Raghavan Arun , Deshmukh Jyotirmoy V. , Mador-Haim Sela , Martin Milo M.K. , Alur Rajeev
Published: July 2013

With the maturing of technology for model checking and constraint solving, there is an emerging opportunity to develop programming tools that can transform the way systems are specified. In this paper, we propose a new way to program distributed protocols using concolic snippets. Concolic snippets are sample execution fragments that contain both concrete and symbolic values. The proposed approach allows the programmer to describe the desired system partially using the traditional model of communicating extended finite-state-machines (EFSM), along with high-level invariants and concrete execution fragments. Our synthesis engine completes an EFSM skeleton by inferring guards and updates from the given fragments which is then automatically analyzed using a model checker with respect to the desired invariants. The counterexamples produced by the model checker can then be used by the programmer to add new concrete execution fragments that describe the correct behavior in the specific scenario corresponding to the counterexample.

We describe TRANSIT, a language and prototype implementation of the proposed specification methodology for distributed protocols. Experimental evaluations of TRANSIT to specify cache coherence protocols show that (1) the algorithm for expression inference from concolic snippets can synthesize expressions of size 15 involving typical operators over commonly occurring types, (2) for a classical directory-based protocol, TRANSIT automatically generates, in a few seconds, a complete implementation from a specification consisting of the EFSM structure and a few concrete examples for every transition, and (3) a published partial description of the SGI Origin cache coherence protocol maps directly to symbolic examples and leads to a complete implementation in a few iterations, with the programmer correcting counterexamples resulting from underspecified transitions by adding concrete examples in each iteration.
Quipper
Authors: Green Alexander S. , Lumsdaine Peter LeFanu , Ross Neil J. , Selinger Peter , Valiron Benoît
Published: July 2013

The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.