bluuebunny/crossref_metadata_2025 huggingface dataset:
Detecting changes in information diffusion patterns over social networks
Authors: Saito Kazumi , Kimura Masahiro , Ohara Kouzou , Motoda Hiroshi
Published: July 2013

We addressed the problem of detecting the change in behavior of information diffusion over a social network which is caused by an unknown external situation change using a small amount of observation data in a retrospective setting. The unknown change is assumed effectively reflected in changes in the parameter values in the probabilistic information diffusion model, and the problem is reduced to detecting where in time and how long this change persisted and how big this change is. We solved this problem by searching the change pattern that maximizes the likelihood of generating the observed information diffusion sequences, and in doing so we devised a very efficient general iterative search algorithm using the derivative of the likelihood which avoids parameter value optimization during each search step. This is in contrast to the naive learning algorithm in that it has to iteratively update the patten boundaries, each requiring the parameter value optimization and thus is very inefficient. We tested this algorithm for two instances of the probabilistic information diffusion model which has different characteristics. One is of information push style and the other is of information pull style. We chose Asynchronous Independent Cascade (AsIC) model as the former and Value-weighted Voter (VwV) model as the latter. The AsIC is the model for general information diffusion with binary states and the parameter to detect its change is diffusion probability and the VwV is the model for opinion formation with multiple states and the parameter to detect its change is opinion value. The results tested on these two models using four real-world network structures confirm that the algorithm is robust enough and can efficiently identify the correct change pattern of the parameter values. Comparison with the naive method that finds the best combination of change boundaries by an exhaustive search through a set of randomly selected boundary candidates shows that the proposed algorithm far outperforms the native method both in terms of accuracy and computation time.
Analysis of friendship network and its role in explaining obesity
Authors: Marathe Achla , Pan Zhengzheng , Apolloni Andrea
Published: July 2013

We employ Add Health data to show that friendship networks, constructed from mutual friendship nominations, are important in building weight perception, setting weight goals, and measuring social marginalization among adolescents and young adults. We study the relationship between individuals' perceived weight status, actual weight status, weight status relative to friends' weight status, and weight goals. This analysis helps us understand how individual weight perceptions might be formed, what these perceptions do to the weight goals, and how friends' relative weight affects weight perception and weight goals. Combining this information with individuals' friendship network helps determine the influence of social relationships on weight-related variables. Multinomial logistic regression results indicate that relative status is indeed a significant predictor of perceived status, and perceived status is a significant predictor of weight goals. We also address the issue of causality between actual weight status and social marginalization (as measured by the number of friends) and show that obesity precedes social marginalization in time rather than the other way around. This lends credence to the hypothesis that obesity leads to social marginalization not vice versa. Attributes of the friendship network can provide new insights into effective interventions for combating obesity since adolescent friendships provide an important social context for weight-related behaviors.
Designing i*CATch
Authors: Ngai Grace , Chan Stephen C.F. , Leong Hong Va , Ng Vincent T.Y.
Published: July 2013

This article presents the design and development of i*CATch, a construction kit for physical and wearable computing that was designed to be scalable, plug-and-play, and to provide support for iterative and exploratory learning. It consists of a standardized construction interface that can be adapted for a wide range of soft textiles or electronic boards, a set of functional components, and an easy-to-use hybrid text-graphical integrated development environment. The objective was to design an easily usable, manufacturable and extensible construction kit that can be used in a wide range of teaching tasks for a wide variety of student demographic profiles. We present detailed specifications of our construction kit and explain some of the major design decisions. Experiences in using the kit in multiple teaching environments, ranging from elementary school to postgraduate, demonstrate that the design objectives have been achieved.
Latent space segmentation for mobile gait analysis
Authors: Valtazanos Aris , Arvind D. K. , Ramamoorthy Subramanian
Published: July 2013

An unsupervised learning algorithm is presented for segmentation and evaluation of motion data from the on-body Orient wireless motion capture system for mobile gait analysis. The algorithm is
model-free
and operates on the
latent space
of the motion, by first
aggregating
all the sensor data into a single vector, and then modeling them on a low-dimensional manifold to perform segmentation. The proposed approach is contrasted to a
basic, model-based
algorithm, which operates directly on the joint angles computed by the Orient sensor devices. The latent space algorithm is shown to be capable of retrieving qualitative features of the motion even in the face of noisy or incomplete sensor readings.
Miniaturized wireless ECG monitor for real-time detection of epileptic seizures
Authors: Massé Fabien , Bussel Martien Van , Serteyn Aline , Arends Johan , Penders Julien
Published: July 2013

Recent advances in miniaturization of ultra-low power components allow for more intelligent wearable health monitors. The development and evaluation of a wireless wearable electrocardiogram (ECG) monitor to detect epileptic seizures from changes in the cardiac rhythm is described. The ECG data are analyzed by embedded algorithms: a robust beat-detection algorithm combined with a real-time epileptic seizure detector. In its current implementation, the proposed prototype is 52× 36× 15mm
3
, and has an autonomy of one day. Based on data collected on the first three epilepsy patients, preliminary clinical results are provided. Wireless, miniaturized and comfortable, this prototype opens new perspectives for health monitoring.
Designing best effort networks-on-chip to meet hard latency constraints
Authors: Seiculescu Ciprian , Rahmati Dara , Murali Srinivasan , Sarbazi-Azad Hamid , Benini Luca , Micheli Giovanni De
Published: July 2013

Many classes of applications require
Quality of Service
(QoS) guarantees from the system interconnect. In
Networks-on-Chip
(NoC) QoS guarantees usually translate into bandwidth and latency constraints for the traffic flows and require hardware support in the NoC fabric and its interfaces. In this article we present a novel NoC synthesis framework to automatically build networks that meet hard latency constraints of end-to-end traffic streams without requiring specialized hardware for the network components. The hard latency constraints are met by carefully designing the NoC topology and selecting the appropriate routes for flow using lean best-effort network components. We perform experiments on several
System on Chip
(SoC) benchmarks. We compared against a topology synthesis method with no support for real-time constraints and we show that the proposed method can produce topologies that can meet significantly tighter worst case latency constraints (on average 44%). We also show that the tightest worst case latency can be provided with little overhead on power consumption (on average 8.5%).
Enabling power efficiency through dynamic rerouting on-chip
Authors: Sem-Jacobsen Frank Olaf , Rodrigo Samuel , Strano Alessandro , Skeie Tor , Bertozzi Davide , Gilabert Francisco
Published: July 2013

Networks-on-chip (NoCs) are key components in many-core chip designs. Dynamic power-awareness is a new challenge present in NoCs that must be efficiently handled by the routing functionality as it introduces irregularities in the commonly used 2-D meshes. In this article, we propose a logic-based routing algorithm, iFDOR, oriented towards dynamic powering down one region within every application partition on the chip through dynamic rerouting, with low implementation costs. Results show that we can successfully shutdown an arbitrary rectangular region within an application partition without significant impact on network performance.
Habituated objects
Authors: Brereton Margot
Published: July 2013

The boundaries between 'the digital' and our everyday physical world are dissolving as we develop more physical ways of interacting with computing. This forum presents some of the topics discussed in the colorful multidisciplinary field of tangible and embodied interaction.

Eva Hornecker, Editor
Near-lossless semantic video summarization and its applications to video analysis
Authors: Mei Tao , Tang Lin-Xie , Tang Jinhui , Hua Xian-Sheng
Published: July 2013

The ever increasing volume of video content on the Web has created profound challenges for developing efficient indexing and search techniques to manage video data. Conventional techniques such as video compression and summarization strive for the two commonly conflicting goals of low storage and high visual and semantic fidelity. With the goal of balancing both video compression and summarization, this article presents a novel approach, called Near-Lossless Semantic Summarization (NLSS), to summarize a video stream with the least high-level semantic information loss by using an extremely small piece of metadata. The summary consists of compressed image and audio streams, as well as the metadata for temporal structure and motion information. Although at a very low compression rate (around 1/40 of H.264 baseline, where traditional compression techniques can hardly preserve an acceptable visual fidelity), the proposed NLSS still can be applied to many video-oriented tasks, such as visualization, indexing and browsing, duplicate detection, concept detection, and so on. We evaluate the NLSS on TRECVID and other video collections, and demonstrate that it is a powerful tool for significantly reducing storage consumption, while keeping high-level semantic fidelity.
A conditional access system with efficient key distribution and revocation for mobile pay-TV systems
Authors: Yeh Lo-Yao , Huang Jiun-Long
Published: July 2013

Current mobile pay-TV systems have two types of Conditional Access Systems (CAS): group-key-based and public-key systems. The best feature of group-key-based systems is the ability to enjoy the broadcast nature in delivery multimedia contents, while the major advantage of public-key systems is consolidating the security foundation to withstand various attacks, such as collusion attacks. However, the problems of group-key-based systems include collusion attacks, lack of nonrepudiation, and troublesome key distribution. Even worse, the benefit of broadcast efficiency is confined to a group size of no more than 512 subscribers. For public-key systems, the poor delivery scalability is the major shortcoming because the unique private key feature is only suitable for one-to-one delivery. In this article, we introduce a scalable access control scheme to integrate the merits of broadcasting regardless of group size and sound security assurance, including fine-grained access control and collusion attack resistance. For subscriber revocation, a single message is broadcast to the other subscribers to get the updated key, thus significantly boosting subscriber revocation scalability. Due to mobile subscribers' dynamic movements, this article also analyzes the benefit of retransmission cases in our system. Through the performance evaluation and functionality comparison, the proposed scheme should be a decent candidate to enhance the security strength and transmission efficiency in a mobile pay-TV system.
Cooperative empirical failure avoidance for multithreaded programs
Authors: Lucia Brandon , Ceze Luis
Published: July 2013

Concurrency errors in multithreaded programs are difficult to find and fix. We propose Aviso, a system for avoiding schedule-dependent failures. Aviso monitors events during a program's execution and, when a failure occurs, records a history of events from the failing execution. It uses this history to generate schedule constraints that perturb the order of events in the execution and thereby avoids schedules that lead to failures in future program executions. Aviso leverages scenarios where many instances of the same software run, using a statistical model of program behavior and experimentation to determine which constraints most effectively avoid failures. After implementing Aviso, we showed that it decreased failure rates for a variety of important desktop, server, and cloud applications by orders of magnitude, with an average overhead of less than 20% and, in some cases, as low as 5%.
Parasol and GreenSwitch
Authors: Goiri Íñigo , Katsak William , Le Kien , Nguyen Thu D. , Bianchini Ricardo
Published: July 2013

Several companies have recently announced plans to build "green" datacenters, i.e. datacenters partially or completely powered by renewable energy. These datacenters will either generate their own renewable energy or draw it directly from an existing nearby plant. Besides reducing carbon footprints, renewable energy can potentially reduce energy costs, reduce peak power costs, or both. However, certain renewable fuels are intermittent, which requires approaches for tackling the energy supply variability. One approach is to use batteries and/or the electrical grid as a backup for the renewable energy. It may also be possible to adapt the workload to match the renewable energy supply. For highest benefits, green datacenter operators must intelligently manage their workloads and the sources of energy at their disposal.

In this paper, we first discuss the tradeoffs involved in building green datacenters today and in the future. Second, we present Parasol, a prototype green datacenter that we have built as a research platform. Parasol comprises a small container, a set of solar panels, a battery bank, and a grid-tie. Third, we describe GreenSwitch, our model-based approach for dynamically scheduling the workload and selecting the source of energy to use. Our real experiments with Parasol, GreenSwitch, and MapReduce workloads demonstrate that intelligent workload and energy source management can produce significant cost reductions. Our results also isolate the cost implications of peak power management, storing energy on the grid, and the ability to delay the MapReduce jobs. Finally, our results demonstrate that careful workload and energy source management can minimize the negative impact of electrical grid outages.
The rise of the expert amateur
Authors: Paulos Eric
Published: July 2013

We are at an important technological inflection point. Most of our computing systems have been designed and built by professionally trained experts (i.e. us -- computer scientists, engineers, and designers) for use in specific domains and to solve explicit prob-lems. Artifacts often called "user manuals" traditionally prescribed the appropriate usage of these tools and implied an acceptable etiquette for interaction and experience. A fringe group of individuals usually labeled "hackers" or "amateurs" or "makers" have challenged this producer-consumer model of technology by creating novel hardware and software features to "improve" our research and products while a similar creative group of technicians called "artists" have redirected the techniques, tools, and tenets of accepted technological usage away from their typical manifestations in practicality and product. Over time the technological artifacts of these fringe groups and the support for their rhetoric have gained them a foothold into computing culture and eroded the established power discontinuities within the practice of computing research. We now expect our computing tools to be driven by an architecture of open participation and democracy that encourages users to add value to their tools and applications as they use them. Similarly, the bar for enabling the design of novel, personal computing systems and "hardware remixes" has fallen to the point where many non-experts and novices are readily embracing and creating fascinating and ingenious computing artifacts outside of our official and traditionally sanctioned academic and industrial research communities.

But how have we as "expert" practitioners been influencing this discussion? By constructing a practice around the design and development of technology for task based and problem solving applications, we have unintentionally established such work as the status quo for the human computing experience. We have failed in our duty to open up alternate forums for technology to express itself and touch our lives beyond productivity and efficiency. Blinded by our quest for "smart technologies" we have forgotten to contemplate the design of technologies to inspire us to be smarter, more curious, and more inquisitive. We owe it to ourselves to rethink the impact we desire to have on this historic moment in computing culture. We must choose to participate in and perhaps lead a dialogue that heralds an expansive new acceptable practice of designing to enable participation by experts and non-experts alike. We are in the milieu of the rise of the "expert amateur". We must change our mantra -- not just performance, completeness, and usability but openness, usefulness and relevancy to our world, its citizens, and our environment. This talk will explore elements of the DIY and maker culture and its relevancy to research questions across computational hardware, languages, and systems. Ultimately, this talk will outline and argue for expanding the design territory and potential opportunities for all of us to collaborate and benefit as a society from this cultural movement.
DeAliaser
Authors: Ahn Wonsun , Duan Yuelu , Torrellas Josep
Published: July 2013

Alias analysis is a critical component in many compiler optimizations. A promising approach to reduce the complexity of alias analysis is to use speculation. The approach consists of performing optimizations assuming the alias relationships that are true most of the time, and repairing the code when such relationships are found not to hold through runtime checks.

This paper proposes a general alias speculation scheme that leverages upcoming hardware support for transactions with the help of some ISA extensions. The ability of transactions to checkpoint and roll back frees the compiler to pursue aggressive optimizations without having to worry about recovery code. Also, exposing the memory conflict detection hardware in transactions to software allows runtime checking of aliases with little or no overhead. We test the potential of the novel alias speculation approach with Loop Invariant Code Motion (LICM), Global Value Numbering (GVN), and Partial Redundancy Elimination (PRE) optimization passes. On average, they are shown to reduce program execution time by 9% in SPEC FP2006 applications and 3% in SPEC INT2006 applications over the alias analysis of a state-of-the-art compiler.
Why you should care about quantile regression
Authors: de Oliveira Augusto Born , Fischmeister Sebastian , Diwan Amer , Hauswirth Matthias , Sweeney Peter F.
Published: July 2013

Research has shown that correctly conducting and analysing computer performance experiments is difficult. This paper investigates what is necessary to conduct successful computer performance evaluation by attempting to repeat a prior experiment: the comparison between two Linux schedulers.

In our efforts, we found that exploring an experimental space through a series of incremental experiments can be inconclusive, and there may be no indication of how much experimentation will be enough. Analysis of variance (ANOVA), a traditional analysis method, is able to partly solve the problems with the previous approach, but we demonstrate that ANOVA can be insufficient for proper analysis due to the requirements it imposes on the data.

Finally, we demonstrate the successful application of quantile regression, a recent development in statistics, to computer performance experiments. Quantile regression can provide more insight into the experiment than ANOVA, with the additional benefit of being applicable to data from any distribution. This property makes it especially useful in our field, since non-normally distributed data is common in computer experiments.
STABILIZER
Authors: Curtsinger Charlie , Berger Emery D.
Published: July 2013

Researchers and software developers require effective performance evaluation. Researchers must evaluate optimizations or measure overhead. Software developers use automatic performance regression tests to discover when changes improve or degrade performance. The standard methodology is to compare execution times before and after applying changes.

Unfortunately, modern architectural features make this approach unsound. Statistically sound evaluation requires multiple samples to test whether one can or cannot (with high confidence) reject the null hypothesis that results are the same before and after. However, caches and branch predictors make performance dependent on machine-specific parameters and the exact layout of code, stack frames, and heap objects. A single binary constitutes just one sample from the space of program layouts, regardless of the number of runs. Since compiler optimizations and code changes also alter layout, it is currently impossible to distinguish the impact of an optimization from that of its layout effects.

This paper presents Stabilizer, a system that enables the use of the powerful statistical techniques required for sound performance evaluation on modern architectures. Stabilizer forces executions to sample the space of memory configurations by repeatedly re-randomizing layouts of code, stack, and heap objects at runtime. Stabilizer thus makes it possible to control for layout effects. Re-randomization also ensures that layout effects follow a Gaussian distribution, enabling the use of statistical tests like ANOVA. We demonstrate Stabilizer's efficiency (<7% median overhead) and its effectiveness by evaluating the impact of LLVM's optimizations on the SPEC CPU2006 benchmark suite. We find that, while -O2 has a significant impact relative to -O1, the performance impact of -O3 over -O2 optimizations is indistinguishable from random noise.
Discerning the dominant out-of-order performance advantage
Authors: McFarlin Daniel S. , Tucker Charles , Zilles Craig
Published: July 2013

In this paper, we set out to study the performance advantages of an Out-of-Order (OOO) processor relative to in-order processors with similar execution resources. In particular, we try to tease apart the performance contributions from two sources: the improved sched- ules enabled by OOO hardware speculation support and its ability to generate different schedules on different occurrences of the same instructions based on operand and functional unit availability. We find that the ability to express good static schedules achieves the bulk of the speedup resulting from OOO. Specifically, of the 53% speedup achieved by OOO relative to a similarly provisioned in- order machine, we find that 88% of that speedup can be achieved by using a single "best" static schedule as suggested by observing an OOO schedule of the code. We discuss the ISA mechanisms that would be required to express these static schedules. Furthermore, we find that the benefits of dynamism largely come from two kinds of events that influence the application's critical path: load instructions that miss in the cache only part of the time and branch mispredictions. We find that much of the benefit of OOO dynamism can be achieved by the potentially simpler task of addressing these two behaviors directly.
Stochastic superoptimization
Authors: Schkufza Eric , Sharma Rahul , Aiken Alex
Published: July 2013

We formulate the loop-free binary superoptimization task as a stochastic search problem. The competing constraints of transformation correctness and performance improvement are encoded as terms in a cost function, and a Markov Chain Monte Carlo sampler is used to rapidly explore the space of all possible programs to find one that is an optimization of a given target program. Although our method sacrifices completeness, the scope of programs we are able to consider, and the resulting quality of the programs that we produce, far exceed those of existing superoptimizers. Beginning from binaries compiled by llvm -O0 for 64-bit x86, our prototype implementation, STOKE, is able to produce programs which either match or outperform the code produced by gcc -O3, icc -O3, and in some cases, expert handwritten assembly.
Demand-based coordinated scheduling for SMP VMs
Authors: Kim Hwanju , Kim Sangwook , Jeong Jinkyu , Lee Joonwon , Maeng Seungryoul
Published: July 2013

As processor architectures have been enhancing their computing capacity by increasing core counts, independent workloads can be consolidated on a single node for the sake of high resource efficiency in data centers. With the prevalence of virtualization technology, each individual workload can be hosted on a virtual machine for strong isolation between co-located workloads. Along with this trend, hosted applications have increasingly been multithreaded to take advantage of improved hardware parallelism. Although the performance of many multithreaded applications highly depends on communication (or synchronization) latency, existing schemes of virtual machine scheduling do not explicitly coordinate virtual CPUs based on their communication behaviors.

This paper presents a demand-based coordinated scheduling scheme for consolidated virtual machines that host multithreaded workloads. To this end, we propose communication-driven scheduling that controls time-sharing in response to inter-processor interrupts (IPIs) between virtual CPUs. On the basis of in-depth analysis on the relationship between IPI communications and coordination demands, we devise IPI-driven coscheduling and delayed preemption schemes, which effectively reduce synchronization latency and unnecessary CPU consumption. In addition, we introduce a load-conscious CPU allocation policy in order to address load imbalance in heterogeneously consolidated environments. The proposed schemes are evaluated with respect to various scenarios of mixed workloads using the PARSEC multithreaded applications. In the evaluation, our scheme improves the overall performance of consolidated workloads, especially communication-intensive applications, by reducing inefficient synchronization latency.
Efficient virtualization on embedded power architecture® platforms
Authors: Mittal Aashish , Bansal Dushyant , Bansal Sorav , Sethi Varun
Published: July 2013

Power Architecture® processors are popular and widespread on embedded systems, and such platforms are increasingly being used to run virtual machines. While the Power Architecture meets the Popek-and-Goldberg virtualization requirements for traditional trap-and-emulate style virtualization, the performance overhead of virtualization remains high. For example, workloads exhibiting a large amount of kernel activity typically show 3-5x slowdowns over bare-metal.

Recent additions to the Linux kernel contain guest and host side paravirtual extensions for Power Architecture platforms. While these extensions improve performance significantly, they are guest-specific, guest-intrusive, and cover only a subset of all possible virtualization optimizations.

We present a set of host-side optimizations that achieve comparable performance to the aforementioned paravirtual extensions, on an unmodified guest. Our optimizations are based on adaptive in-place binary translation. Unlike the paravirtual approach, our solution is guest neutral. We implement our ideas in a prototype based on Qemu/KVM. After our modifications, KVM can boot an unmodified Linux guest around 2.5x faster. We contrast our optimization approach with previous similar binary translation based approaches for the x86 architecture; in our experience, each architecture presents a unique set of challenges and optimization opportunities.
Wait-n-GoTM
Authors: Jafri Syed Ali Raza , Voskuilen Gwendolyn , Vijaykumar T. N.
Published: July 2013

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware TMs (HTMs) use one of three conflict-resolution policies: (1)
always-abort,
(2)
always-wait
for some conflicting transactions to complete, or (3)
always-go
past conflicts and resolve acyclic conflicts at commit or abort upon cyclic dependencies. While each policy has advantages, the policies degrade performance under contention by limiting concurrency (always-abort, always-wait) or incurring late aborts due to cyclic dependencies (always-go). Thus, while always-go avoids acyclic aborts, no policy avoids cyclic aborts. We propose
Wait-n-GoTM (WnGTM)
to increase concurrency while avoiding cyclic aborts. We observe that most cyclic dependencies are caused by threads interleaving multiple accesses to a few heavily-read-write-shared delinquent data cache blocks. These accesses occur in code sections called
cycle inducer sections (CISTs)
. Accordingly, we propose
Wait-n-Go (WnG)
conflict-resolution to avoid many cyclic aborts by predicting and serializing the CISTs. To support the WnG policy, we extend previous HTMs to (1) allow multiple readers and writers, (2) scalably identify dependencies, and (3) detect cyclic dependencies via new mechanisms, namely, conflict transactional state, order-capture, and hardware timestamps, respectively. In 16-core simulations of STAMP, WnGTM achieves average speedups of 46% for higher-contention benchmarks and 28% for all benchmarks over always-abort (TokenTM) with low-contention benchmarks remaining unchanged, compared to always-go (DATM) and always-wait (LogTM-SE), which perform worse than and 6% better than TokenTM, respectively.
HW/SW co-designed acceleration of dynamic languages
Authors: Wu Youfeng
Published: July 2013

Dynamic Programming Languages, such as Java, JavaScript, PHP, Perl, Python, Ruby, etc., are dominating languages for pro-gramming the web. HW/SW co-designed virtual machine can significantly accelerate their executions by transparently leveraging internal HW features via an internal compiler. We also argue for a common API to interface dynamic languages with the HW/SW co-designed virtual machine, so that a single internal compiler can accelerate all major dynamic languages.
BLog
Authors: Guan Yong , Wang Guohui , Wang Yi , Chen Renhai , Shao Zili
Published: July 2013

Log-block-based FTL (Flash Translation Layer) schemes have been widely used to manage NAND flash memory storage systems in industry. In log-block-based FTLs, a few physical blocks called log blocks are used to hold all page updates from a large amount of data blocks. Frequent page updates in log blocks introduce big overhead so log blocks become the system bottleneck.

To address this problem, this paper presents a block-level log-block management scheme called
BLog
(Block-level Log-Block Management). In
BLog
, with the block level management, the update pages of a data block can be collected together and put into the same log block as much as possible; therefore, we can effectively reduce the associativities of log blocks so as to reduce the garbage collection overhead. We also propose a novel partial merge operation called
reduced-order merge
by which we can effectively postpone the garbage collection of log blocks so as to maximally utilize valid pages and reduce unnecessary erase operations in log blocks. Based on
BLog
, we design an FTL called
BLogFTL
for MLC NAND flash. We conduct experiments on a mixture of real-world and synthetic traces. The experimental results show that our scheme outperforms the previous log-block-based FTLs for MLC NAND flash.
LUCAS
Authors: Porpodas Vasileios , Cintra Marcelo
Published: July 2013

Clustered VLIW architectures are statically scheduled wide-issue architectures that combine the advantages of wide-issue processors along with the power and frequency scalability of clustered designs. Being statically scheduled, they require that the decision of mapping instructions to clusters be done by the compiler. State-of-the-art code generation for such architectures combines cluster-assignment and instruction scheduling in a single unified pass. The performance of the generated code, however, is very susceptible to the inter-cluster communication latency. This is due to the nature of the two clustering heuristics used. One is aggressive and works well for low inter-cluster latencies, while the other is more conservative and works well only for high latencies.

In this paper we propose LUCAS, a novel unified cluster-assignment and instruction-scheduling algorithm that adapts to the inter-cluster latency better than the existing state-of-the-art schemes. LUCAS is a hybrid scheme that performs fine-grain switching between the two state-of-the art clustering heuristics, leading to better scheduling than either of them. It generates better performing code for a wide range of inter-cluster latency values.
Combined WCET analysis of bitcode and machine code using control-flow relation graphs
Authors: Huber Benedikt , Prokesch Daniel , Puschner Peter
Published: July 2013

Static program analyses like stack usage analysis and worst-case execution time (WCET) analysis depend on the actual machine code generated by the compiler for the target system. As the analysis of binary code is costly, hard to diagnose and platform dependent, it is preferable to carry out parts of these analyses on a higher-level program representation. To this end, the higher-level code and the machine code need to be related, a difficult task due to the complexity of modern optimizing compilers.

In this article, we present a novel representation called control-flow relation graphs, which provide an accurate model of the control-flow relation between machine code and the compiler's intermediate representation. In order to facilitate the integration of our approach in existing compiler frameworks, we develop a construction algorithm that builds the control-flow relation graph from partial mappings provided by the compiler. The WCET calculation method for control-flow relation graphs processes flow information from both the intermediate representation and machine code. Furthermore, we demonstrate the transformation of flow information from the IR to the machine code level, in order to use existing industrial-strength WCET analysis tools operating on machine code. We implemented the construction algorithm within the LLVM compiler framework, along with an implementation of the combined WCET calculation method.

The evaluation demonstrates that the approach is able to relate bitcode (LLVM's intermediate representation) and machine code in a precise way, with a WCET increase of at most 2% when using flow facts on the bitcode level, compared to equivalent ones on the machine-code level. As the methods presented in this article provide a cost-effective way to reuse platform independent flow information, they have the potential to simplify WCET analysis, and popularize its use in the development process of real-time systems.
Fast algorithms for Dyck-CFL-reachability with applications to alias analysis
Authors: Zhang Qirun , Lyu Michael R. , Yuan Hao , Su Zhendong
Published: July 2013

The context-free language (CFL) reachability problem is a well-known fundamental formulation in program analysis. In practice, many program analyses, especially pointer analyses, adopt a restricted version of CFL-reachability, Dyck-CFL-reachability, and compute on edge-labeled bidirected graphs. Solving the all-pairs Dyck-CFL-reachability on such bidirected graphs is expensive. For a bidirected graph with n nodes and m edges, the traditional dynamic programming style algorithm exhibits a subcubic time complexity for the Dyck language with k kinds of parentheses. When the underlying graphs are restricted to bidirected trees, an algorithm with O(n log n log k) time complexity was proposed recently. This paper studies the Dyck-CFL-reachability problems on bidirected trees and graphs. In particular, it presents two fast algorithms with O(n) and O(n + m log m) time complexities on trees and graphs respectively. We have implemented and evaluated our algorithms on a state-of-the-art alias analysis for Java. Results on standard benchmarks show that our algorithms achieve orders of magnitude speedup and consume less memory.
CONCURRIT
Authors: Elmas Tayfun , Burnim Jacob , Necula George , Sen Koushik
Published: July 2013

We present CONCURRIT, a domain-specific language (DSL) for reproducing concurrency bugs. Given some partial information about the nature of a bug in an application, a programmer can write a CONCURRIT script to formally and concisely specify a set of thread schedules to explore in order to find a schedule exhibiting the bug. Further, the programmer can specify how these thread schedules should be searched to find a schedule that reproduces the bug. We implemented CONCURRIT as an embedded DSL in C++, which uses manual or automatic source instrumentation to partially control the scheduling of the software under test. Using CONCURRIT, we were able to write concise tests to reproduce concurrency bugs in a variety of benchmarks, including the Mozilla's SpiderMonkey JavaScript engine, Memcached, Apache's HTTP server, and MySQL.
Dynamic determinacy analysis
Authors: Schäfer Max , Sridharan Manu , Dolby Julian , Tip Frank
Published: July 2013

We present an analysis for identifying
determinate
variables and expressions that always have the same value at a given program point. This information can be exploited by client analyses and tools to, e.g., identify dead code or specialize uses of dynamic language constructs such as eval, replacing them with equivalent static constructs. Our analysis is completely dynamic and only needs to observe a single execution of the program, yet the determinacy facts it infers hold for any execution. We present a formal soundness proof of the analysis for a simple imperative language, and a prototype implementation that handles full JavaScript. Finally, we report on two case studies that explored how static analysis for JavaScript could leverage the information gathered by dynamic determinacy analysis. We found that in some cases scalability of static pointer analysis was improved dramatically, and that many uses of runtime code generation could be eliminated.
Taming compiler fuzzers
Authors: Chen Yang , Groce Alex , Zhang Chaoqiang , Wong Weng-Keen , Fern Xiaoli , Eide Eric , Regehr John
Published: July 2013

Aggressive random testing tools ("fuzzers") are impressively effective at finding compiler bugs. For example, a single test-case generator has resulted in more than 1,700 bugs reported for a single JavaScript engine. However, fuzzers can be frustrating to use: they indiscriminately and repeatedly find bugs that may not be severe enough to fix right away. Currently, users filter out undesirable test cases using ad hoc methods such as disallowing problematic features in tests and grepping test results. This paper formulates and addresses the fuzzer taming problem: given a potentially large number of random test cases that trigger failures, order them such that diverse, interesting test cases are highly ranked. Our evaluation shows our ability to solve the fuzzer taming problem for 3,799 test cases triggering 46 bugs in a C compiler and 2,603 test cases triggering 28 bugs in a JavaScript engine.
Halide
Authors: Ragan-Kelley Jonathan , Barnes Connelly , Adams Andrew , Paris Sylvain , Durand Frédo , Amarasinghe Saman
Published: July 2013

Image processing pipelines combine the challenges of stencil computations and stream programs. They are composed of large graphs of different stencil stages, as well as complex reductions, and stages with global or data-dependent access patterns. Because of their complex structure, the performance difference between a naive implementation of a pipeline and an optimized one is often an order of magnitude. Efficient implementations require optimization of both parallelism and locality, but due to the nature of stencils, there is a fundamental tension between parallelism, locality, and introducing redundant recomputation of shared values.

We present a systematic model of the tradeoff space fundamental to stencil pipelines, a schedule representation which describes concrete points in this space for each stage in an image processing pipeline, and an optimizing compiler for the Halide image processing language that synthesizes high performance implementations from a Halide algorithm and a schedule. Combining this compiler with stochastic search over the space of schedules enables terse, composable programs to achieve state-of-the-art performance on a wide range of real image processing pipelines, and across different hardware architectures, including multicores with SIMD, and heterogeneous CPU+GPU execution. From simple Halide programs written in a few hours, we demonstrate performance up to 5x faster than hand-tuned C, intrinsics, and CUDA implementations optimized by experts over weeks or months, for image processing applications beyond the reach of past automatic compilers.
Machine-verified network controllers
Authors: Guha Arjun , Reitblatt Mark , Foster Nate
Published: July 2013

In many areas of computing, techniques ranging from testing to formal modeling to full-blown verification have been successfully used to help programmers build reliable systems. But although networks are critical infrastructure, they have largely resisted analysis using formal techniques. Software-defined networking (SDN) is a new network architecture that has the potential to provide a foundation for network reasoning, by standardizing the interfaces used to express network programs and giving them a precise semantics.

This paper describes the design and implementation of the first machine-verified SDN controller. Starting from the foundations, we develop a detailed operational model for OpenFlow (the most popular SDN platform) and formalize it in the Coq proof assistant. We then use this model to develop a verified compiler and run-time system for a high-level network programming language. We identify bugs in existing languages and tools built without formal foundations, and prove that these bugs are absent from our system. Finally, we describe our prototype implementation and our experiences using it to build practical applications.
When polyhedral transformations meet SIMD code generation
Authors: Kong Martin , Veras Richard , Stock Kevin , Franchetti Franz , Pouchet Louis-Noël , Sadayappan P.
Published: July 2013

Data locality and parallelism are critical optimization objectives for performance on modern multi-core machines. Both coarse-grain parallelism (e.g., multi-core) and fine-grain parallelism (e.g., vector SIMD) must be effectively exploited, but despite decades of progress at both ends, current compiler optimization schemes that attempt to address data locality and both kinds of parallelism often fail at one of the three objectives.

We address this problem by proposing a 3-step framework, which aims for integrated data locality, multi-core parallelism and SIMD execution of programs. We define the concept of vectorizable codelets, with properties tailored to achieve effective SIMD code generation for the codelets. We leverage the power of a modern high-level transformation framework to restructure a program to expose good ISA-independent vectorizable codelets, exploiting multi-dimensional data reuse. Then, we generate ISA-specific customized code for the codelets, using a collection of lower-level SIMD-focused optimizations.

We demonstrate our approach on a collection of numerical kernels that we automatically tile, parallelize and vectorize, exhibiting significant performance improvements over existing compilers.
Hybrid context-sensitivity for points-to analysis
Authors: Kastrinis George , Smaragdakis Yannis
Published: July 2013

Context-sensitive points-to analysis is valuable for achieving high precision with good performance. The standard flavors of context-sensitivity are call-site-sensitivity (kCFA) and object-sensitivity. Combining both flavors of context-sensitivity increases precision but at an infeasibly high cost. We show that a selective combination of call-site- and object-sensitivity for Java points-to analysis is highly profitable. Namely, by keeping a combined context only when analyzing selected language features, we can closely approximate the precision of an analysis that keeps both contexts at all times. In terms of speed, the selective combination of both kinds of context not only vastly outperforms non-selective combinations but is also faster than a mere object-sensitive analysis. This result holds for a large array of analyses (e.g., 1-object-sensitive, 2-object-sensitive with a context-sensitive heap, type-sensitive) establishing a new set of performance/precision sweet spots.
Complete completion using types and weights
Authors: Gvero Tihomir , Kuncak Viktor , Kuraj Ivan , Piskac Ruzica
Published: July 2013

Developing modern software typically involves composing functionality from existing libraries. This task is difficult because libraries may expose many methods to the developer. To help developers in such scenarios, we present a technique that synthesizes and suggests valid expressions of a given type at a given program point. As the basis of our technique we use type inhabitation for lambda calculus terms in long normal form. We introduce a succinct representation for type judgements that merges types into equivalence classes to reduce the search space, then reconstructs any desired number of solutions on demand. Furthermore, we introduce a method to rank solutions based on weights derived from a corpus of code. We implemented the algorithm and deployed it as a plugin for the Eclipse IDE for Scala. We show that the techniques we incorporated greatly increase the effectiveness of the approach. Our evaluation benchmarks are code examples from programming practice; we make them available for future comparisons.
Steal Tree
Authors: Lifflander Jonathan , Krishnamoorthy Sriram , Kale Laxmikant V.
Published: July 2013

Work stealing is a popular approach to scheduling task-parallel programs. The flexibility inherent in work stealing when dealing with load imbalance results in seemingly irregular computation structures, complicating the study of its runtime behavior. In this paper, we present an approach to efficiently trace async-finish parallel programs scheduled using work stealing. We identify key properties that allow us to trace the execution of tasks with low time and space overheads. We also study the usefulness of the proposed schemes in supporting algorithms for data-race detection and retentive stealing presented in the literature. We demonstrate that the perturbation due to tracing is within the variation in the execution time with 99% confidence and the traces are concise, amounting to a few tens of kilobytes per thread in most cases. We also demonstrate that the traces enable significant reductions in the cost of detecting data races and result in low, stable space overheads in supporting retentive stealing for async-finish programs.