bluuebunny/crossref_metadata_2025 huggingface dataset:
To hardware prefetch or not to prefetch?
Authors: Kang Hui , Wong Jennifer L.
Published: April 2020

Most hardware and software venders suggest disabling hardware prefetching in virtualized environments. They claim that prefetching is detrimental to application performance due to inaccurate prediction caused by workload diversity and VM interference on shared cache. However, no comprehensive or quantitative measurements to support this belief have been performed.

This paper is the first to systematically measure the influence of hardware prefetching in virtualized environments. We examine a wide variety of benchmarks on three types of chip-multiprocessors (CMPs) to analyze the hardware prefetching performance. We conduct extensive experiments by taking into account a number of important virtualization factors. We find that hardware prefetching has minimal destructive influence under most configurations. Only with certain application combinations does prefetching influence the overall performance.

To leverage these findings and make hardware prefetching effective across a diversity of virtualized environments, we propose a dynamic prefetching-aware VCPU-core binding approach (PAVCB), which includes two phases - classifying and binding. The workload of each VM is classified into different cache sharing constraint categories based upon its cache access characteristics, considering both prefetch requests and demand requests. Then following heuristic rules, the VCPUs of each VM are scheduled onto appropriate cores subject to cache sharing constraints. We show that the proposed approach can improve performance by 12% on average over the default scheduler and 46% over manual system administrator bindings across different workload combinations in the presence of hardware prefetching.
OWL
Authors: Jog Adwait , Kayiran Onur , Chidambaram Nachiappan Nachiappan , Mishra Asit K. , Kandemir Mahmut T. , Mutlu Onur , Iyer Ravishankar , Das Chita R.
Published: April 2020

Emerging GPGPU architectures, along with programming models like CUDA and OpenCL, offer a cost-effective platform for many applications by providing high thread level parallelism at lower energy budgets. Unfortunately, for many general-purpose applications, available hardware resources of a GPGPU are not efficiently utilized, leading to lost opportunity in improving performance. A major cause of this is the inefficiency of current warp scheduling policies in tolerating long memory latencies.

In this paper, we identify that the scheduling decisions made by such policies are agnostic to thread-block, or cooperative thread array (CTA), behavior, and as a result inefficient. We present a coordinated CTA-aware scheduling policy that utilizes four schemes to minimize the impact of long memory latencies. The first two schemes, CTA-aware two-level warp scheduling and locality aware warp scheduling, enhance per-core performance by effectively reducing cache contention and improving latency hiding capability. The third scheme, bank-level parallelism aware warp scheduling, improves overall GPGPU performance by enhancing DRAM bank-level parallelism. The fourth scheme employs opportunistic memory-side prefetching to further enhance performance by taking advantage of open DRAM rows. Evaluations on a 28-core GPGPU platform with highly memory-intensive applications indicate that our proposed mechanism can provide 33% average performance improvement compared to the commonly-employed round-robin warp scheduling policy.
Portable performance on heterogeneous architectures
Authors: Phothilimthana Phitchaya Mangpo , Ansel Jason , Ragan-Kelley Jonathan , Amarasinghe Saman
Published: April 2020

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: April 2020

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.
TSO_ATOMICITY
Authors: Wang Cheng , Wu Youfeng
Published: April 2020

Program optimizations based on data dependences may not preserve the memory consistency in the programs. Previous works leverage a hardware ATOMICITY primitive to restrict the thread interleaving for preserving
sequential consistency
in region optimizations. However, ATOMICITY primitive is over restrictive on the thread interleaving for optimizing real-world applications developed with the popular
Total-Store-Ordering
(TSO) memory consistency, which is weaker than sequential consistency. In this paper, we present a novel hardware TSO_ATOMICITY primitive, which has less restriction on the thread interleaving than ATOMICITY primitive to permit more efficient program execution than ATOMICITY primitive, but can still preserve TSO memory consistency in all region optimizations. Furthermore, TSO_ATOMICITY primitive requires similar architecture support as ATOMICITY primitive and can be implemented with only slight change to the existing ATOMICITY primitive implementation. Our experimental results show that in a start-of-art dynamic binary optimization system on a large set of workloads, ATOMICITY primitive can only improve the performance by 4% on average. TSO_ATOMICITY primitive can reduce the overhead associated with ATOMICITY primitive and improve the performance by 12% on average.
On the treeness of internet latency and bandwidth
Authors: Ramasubramanian Venugopalan , Malkhi Dahlia , Kuhn Fabian , Balakrishnan Mahesh , Gupta Archit , Akella Aditya
Published: April 2020

Existing empirical studies of Internet structure and path properties indicate that the Internet is tree-like. This work quantifies the degree to which at least two important Internet measures--latency and bandwidth--approximate tree metrics. We evaluate our ability to model end-to-end measures using tree embeddings by actually building tree representations. In addition to being simple and intuitive models, these trees provide a range of commonly-required functionality beyond serving as an analytical tool.

The contributions of our study are twofold. First, we investigate the ability to portray the inherent hierarchical structure of the Internet using the most pure and compact topology, trees. Second, we evaluate the ability of our compact representation to facilitate many natural tasks, such as the selection of servers with short latency or high bandwidth from a client. Experiments show that these tasks can be done with high degree of success and modest overhead.
Dynamic data compression in multi-hop wireless networks
Authors: Sharma Abhishek B. , Golubchik Leana , Govindan Ramesh , Neely Michael J.
Published: April 2020

Data compression can save energy and increase network capacity in wireless sensor networks. However, the decision of whether and when to compress data can depend upon platform hardware, topology, wireless channel conditions, and application data rates. Using Lyapunov optimization theory, we design an algorithm called SEEC that makes joint compression and transmission decisions with the goal of minimizing energy consumption. A practical distributed variant, DSEEC, is able to achieve more than 30% energy savings and adapts seamlessly across a wide range of conditions, without explicitly taking topology, application data rates, and link quality changes into account.
DRAM errors in the wild
Authors: Schroeder Bianca , Pinheiro Eduardo , Weber Wolf-Dietrich
Published: April 2020

Errors in dynamic random access memory (DRAM) are a common form of hardware failure in modern compute clusters. Failures are costly both in terms of hardware replacement costs and service disruption. While a large body of work exists on DRAM in laboratory conditions, little has been reported on real DRAM failures in large production clusters. In this paper, we analyze measurements of memory errors in a large fleet of commodity servers over a period of 2.5 years. The collected data covers multiple vendors, DRAM capacities and technologies, and comprises many millions of DIMM days.

The goal of this paper is to answer questions such as the following: How common are memory errors in practice? What are their statistical properties? How are they affected by external factors, such as temperature and utilization, and by chip-specific factors, such as chip density, memory technology and DIMM age?

We find that DRAM error behavior in the field differs in many key aspects from commonly held assumptions. For example, we observe DRAM error rates that are orders of magnitude higher than previously reported, with 25,000 to 70,000 errors per billion device hours per Mbit and more than 8% of DIMMs affected by errors per year. We provide strong evidence that memory errors are dominated by hard errors, rather than soft errors, which previous work suspects to be the dominant error mode. We find that temperature, known to strongly impact DIMM error rates in lab conditions, has a surprisingly small effect on error behavior in the field, when taking all other factors into account. Finally, unlike commonly feared, we don't observe any indication that newer generations of DIMMs have worse error behavior.
MapReduce optimization using regulated dynamic prioritization
Authors: Sandholm Thomas , Lai Kevin
Published: April 2020

We present a system for allocating resources in shared data and compute clusters that improves MapReduce job scheduling in three ways. First, the system uses regulated and user-assigned priorities to offer different service levels to jobs and users over time. Second, the system dynamically adjusts resource allocations to fit the requirements of different job stages. Finally, the system automatically detects and eliminates bottlenecks within a job. We show experimentally using real applications that users can optimize not only job execution time but also the cost-benefit ratio or prioritization efficiency of a job using these three strategies. Our approach relies on a proportional share mechanism that continuously allocates virtual machine resources. Our experimental results show a 11-31% improvement in completion time and 4-187% improvement in prioritization efficiency for different classes of MapReduce jobs. We further show that delay intolerant users gain even more from our system.
Cooperative learning instructional methods for CS1
Authors: Beck Leland , Chizhik Alexander
Published: April 2020

Cooperative learning is a well-known instructional technique that has been applied with a wide variety of subject matter and a broad spectrum of populations. This article briefly reviews the principles of cooperative learning, and describes how these principles were incorporated into a comprehensive set of cooperative learning activities for a CS1 course. In each activity, specific roles are assigned to group members in order to highlight important concepts and to enhance the overall functioning of the group. The group processing is followed by a whole-class debriefing led by the instructor, which works in tandem with the group activity to help students improve their understanding of the material. The effectiveness of these cooperative learning activities was assessed in a series of educational research studies which spanned three academic years and included two different instructors. The results of these studies show statistically significant benefits from the cooperative learning approach, both overall and for a broad range of subgroups of students. The article concludes with suggestions for faculty members who may want to use these cooperative learning activities in the classroom, or to develop their own activities along similar lines.
When Amazon Meets Google
Authors: Wang Meng , Li Guangda , Lu Zheng , Gao Yue , Chua Tat-Seng
Published: April 2020

Product visualization is able to help users easily get knowledge about the visual appearance of a product. It is useful in many application and commercialization scenarios. However, the existing product image search on e-commerce Web sites or general search engines usually get insufficient search results or return images that are redundant and not relevant enough. In this article, we present a novel product visualization approach that automatically collects a set of diverse and relevant product images by exploring multiple Web sources. Our approach simultaneously leverages Amazon and Google image search engines, which represent domain-specific knowledge resource and general Web information collection, respectively. We propose a conditional clustering approach that is formulated as an affinity propagation problem regarding the Amazon examples as information prior. The ranking information of Google image search results is also explored. In this way, a set of exemplars can be found from the Google search results and they are provided together with the Amazon example images for product visualization. Experiments demonstrate the feasibility and effectiveness of our approach.
What to do about Google?
Authors: Grimmelmann James
Published: April 2020

Whether it is acting as a conduit, an editor, or an advisor, the search engine should put user interests first.
Addressing Big Data Time Series
Authors: Rakthanmanon Thanawin , Campana Bilson , Mueen Abdullah , Batista Gustavo , Westover Brandon , Zhu Qiang , Zakaria Jesin , Keogh Eamonn
Published: April 2020

Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms, including classification, clustering, motif discovery, anomaly detection, and so on. The difficulty of scaling a search to large datasets explains to a great extent why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine massive time series for the first time. We demonstrate the following unintuitive fact: in large datasets we can exactly search under Dynamic Time Warping (DTW) much more quickly than the current state-of-the-art
Euclidean distance
search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We explain how our ideas allow us to solve higher-level time series data mining problems such as motif discovery and clustering at scales that would otherwise be untenable. Moreover, we show how our ideas allow us to efficiently support the uniform scaling distance measure, a measure whose utility seems to be underappreciated, but which we demonstrate here. In addition to mining massive datasets with up to one trillion datapoints, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.
DriverGuard
Authors: Cheng Yueqiang , Ding Xuhua , Deng Robert H.
Published: April 2020

Most commodity peripheral devices and their drivers are geared to achieve high performance with security functions being opted out. The absence of strong security measures invites attacks on the I/O data and consequently posts threats to those services feeding on them, such as fingerprint-based biometric authentication. In this article, we present a generic solution called DriverGuard, which dynamically protects the secrecy of I/O flows such that the I/O data are not exposed to the malicious kernel. Our design leverages a composite of cryptographic and virtualization techniques to achieve fine-grained protection without using any extra devices and modifications on user applications. We implement the DriverGuard prototype on Xen by adding around 1.7K SLOC. DriverGuard is lightweight as it only needs to protect around 2% of the driver code’s execution. We measure the performance and evaluate the security of DriverGuard with three input devices (keyboard, fingerprint reader and camera) and three output devices (printer, graphic card, and sound card). The experiment results show that DriverGuard induces negligible overhead to the applications.
I/o paravirtualization at the device file boundary
Authors: Amiri Sani Ardalan , Boos Kevin , Qin Shaopu , Zhong Lin
Published: April 2020

Paravirtualization is an important I/O virtualization technology since it uniquely provides all of the following benefits: the ability to share the device between multiple VMs, support for legacy devices without virtualization hardware, and high performance. However, existing paravirtualization solutions have one main limitation: they only support one I/O device class, and would require significant engineering effort to support new device classes and features. In this paper, we present Paradice, a solution that vastly simplifies I/O paravirtualization by using a common paravirtualization boundary for various I/O device classes: Unix device files. Using this boundary, the paravirtual drivers simply act as a class-agnostic indirection layer between the application and the actual device driver.

We address two fundamental challenges: supporting cross-VM driver memory operations without changes to applications or device drivers and providing fault and device data isolation between guest VMs despite device driver bugs. We implement Paradice for x86, the Xen hypervisor, and the Linux and FreeBSD OSes. Our implementation paravirtualizes various GPUs, input devices, cameras, an audio device, and an Ethernet card for the netmap framework with ~7700 LoC, of which only ~900 are device class-specific. Our measurements show that Paradice achieves performance close to native for different devices and applications including netmap, 3D HD games, and OpenCL applications.
The sharing architecture
Authors: Zhou Yanqi , Wentzlaff David
Published: April 2020

Businesses and Academics are increasingly turning to Infrastructure as a Service (IaaS) Clouds such as Amazon's Elastic Compute Cloud (EC2) to fulfill their computing needs. Unfortunately, current IaaS systems provide a severely restricted pallet of rentable computing options which do not optimally fit the workloads that they are executing. We address this challenge by proposing and evaluating a manycore architecture, called the Sharing Architecture, specifically optimized for IaaS systems by being reconfigurable on a sub-core basis. The Sharing Architecture enables better matching of workload to micro-architecture resources by replacing static cores with Virtual Cores which can be dynamically reconfigured to have different numbers of ALUs and amount of Cache. This reconfigurability enables many of the same benefits of heterogeneous multicores, but in a homogeneous fabric, and enables the reuse and resale of resources on a per ALU or per KB of cache basis. The Sharing Architecture leverages Distributed ILP techniques, but is designed in a way to be independent of recompilation. In addition, we introduce an economic model which is enabled by the Sharing Architecture and show how different users who have varying needs can be better served by such a flexible architecture. We evaluate the Sharing Architecture across a benchmark suite of Apache, SPECint, and parts of PARSEC, and find that it can achieve up to a 5x more economically efficient market when compared to static architecture multicores. We implemented the Sharing Architecture in Verilog and present area overhead results.
Guardrail
Authors: Ruwase Olatunji , Kozuch Michael A. , Gibbons Phillip B. , Mowry Todd C.
Published: April 2020

Device drivers are an Achilles' heel of modern commodity operating systems, accounting for far too many system failures. Previous work on
driver reliability
has focused on protecting the kernel from unsafe driver side-effects by interposing an invariant-checking layer at the driver interface, but otherwise treating the driver as a black box. In this paper, we propose and evaluate Guardrail, which is a more powerful framework for run-time driver analysis that performs
decoupled
instruction-grain
dynamic correctness checking on arbitrary kernel-mode drivers as they execute, thereby enabling the system to detect and mitigate more challenging correctness bugs (e.g., data races, uninitialized memory accesses) that cannot be detected by today's fault isolation techniques. Our evaluation of Guardrail shows that it can find serious data races, memory faults, and DMA faults in native Linux drivers that required fixes, including previously unknown bugs. Also, with hardware logging support, Guardrail can be used for online protection of persistent device state from driver bugs with at most 10% overhead on the end-to-end performance of most standard I/O workloads.
Finding trojan message vulnerabilities in distributed systems
Authors: Banabic Radu , Candea George , Guerraoui Rachid
Published: April 2020

Trojan messages are messages that seem correct to the receiver but cannot be generated by any correct sender. Such messages constitute major vulnerability points of a distributed system---they constitute ideal targets for a malicious actor and facilitate failure propagation across nodes. We describe Achilles, a tool that searches for Trojan messages in a distributed system. Achilles uses dynamic white-box analysis on the distributed system binaries in order to infer the predicate that defines messages parsed by receiver nodes and generated by sender nodes, respectively, and then computes Trojan messages as the difference between the two.

We apply Achilles on implementations of real distributed systems: FSP, a file transfer application, and PBFT, a Byzantine-fault-tolerant state machine replication library. Achilles discovered a new bug in FSP and rediscovered a previously known vulnerability in PBFT. In our evaluation we demonstrate that our approach can perform orders of magnitude better than general approaches based on regular fuzzing and symbolic execution.
Data-parallel finite-state machines
Authors: Mytkowicz Todd , Musuvathi Madanlal , Schulte Wolfram
Published: April 2020

A finite-state machine (FSM) is an important abstraction for solving several problems, including regular-expression matching, tokenizing text, and Huffman decoding. FSM computations typically involve data-dependent iterations with unpredictable memory-access patterns making them difficult to parallelize. This paper describes a parallel algorithm for FSMs that breaks dependences across iterations by efficiently enumerating transitions from all possible states on each input symbol. This allows the algorithm to utilize various sources of data parallelism available on modern hardware, including vector instructions and multiple processors/cores. For instance, on benchmarks from three FSM applications: regular expressions, Huffman decoding, and HTML tokenization, the parallel algorithm achieves up to a 3x speedup over optimized sequential baselines on a single core, and linear speedups up to 21x on 8 cores.
Neuromorphic processing
Authors: Gehlhaar Jeff
Published: April 2020

The desire to build a computer that operates in the same manner as our brains is as old as the computer itself. Although computer engineering has made great strides in hardware performance as a result of Dennard scaling, and even great advances in 'brain like' computation, the field still struggles to move beyond sequential, analytical computing architectures. Neuromorphic systems are being developed to transcend the barriers imposed by silicon power consumption, develop new algorithms that help machines achieve cognitive behaviors, and both exploit and enable further research in neuroscience. In this talk I will discuss a system im-plementing spiking neural networks. These systems hold the promise of an architecture that is event based, broad and shallow, and thus more power efficient than conventional computing solu-tions. This new approach to computation based on modeling the brain and its simple but highly connected units presents a host of new challenges. Hardware faces tradeoffs such as density or lower power at the cost of high interconnection overhead. Consequently, software systems must face choices about new language design. Highly distributed hardware systems require complex place and route algorithms to distribute the execution of the neural network across a large number of highly interconnected processing units. Finally, the overall design, simulation and testing process has to be entirely reimagined. We discuss these issues in the context of the Zeroth processor and how this approach compares to other neuromorphic systems that are becoming available.
Theory in practice for system design and verification
Authors: Alur Rajeev , Henzinger Thomas A. , Vardi Moshe Y.
Published: April 2020

Methodology and tools for assisting developers in building high-confidence hardware and software at a reasonable cost has been one of the central themes in computer science since its inception. The formal methods research on this problem has focused on two complimentary goals: to provide mathematical abstractions to manage the complexity of the design and to develop analysis tools to check that the implementation works correctly as intended. Achieving these goals has proved to be extremely challenging for two reasons. First, the scale and complexity of systems being designed remains a moving target as computers have transformed from special-purpose and stand-alone number-crunching processors to networked devices interacting with the physical world. Second, once formalized, the computational problem of verifying that a system meets its specification is undecidable in the general case and has intractable complexity even in special cases.
Towards correct network virtualization
Authors: Ghorbani Soudeh , Godfrey Brighten
Published: April 2020

In SDN, the underlying infrastructure is usually abstracted for applications that can treat the network as a logical or virtual entity. Commonly, the ``mappings" between virtual abstractions and their actual physical implementations are not one-to-one, e.g., a single "big switch" abstract object might be implemented using a distributed set of physical devices. A key question is, what abstractions could be mapped to multiple physical elements while faithfully preserving their native semantics? E.g., can an application developer always expect her abstract "big switch" to act exactly as a physical big switch, despite being implemented using multiple physical switches in reality?

We show that the answer to that question is "no" for existing virtual-to-physical mapping techniques: behavior can differ between the virtual "big switch" and the physical network, providing incorrect application-level behavior. We also show that that those incorrect behaviors occur despite the fact that the most pervasive and commonly-used correctness invariants, such as per-packet consistency, are preserved throughout. These examples demonstrate that for practical notions of correctness, new systems and a new analytical framework are needed. We take the first steps by defining
end-to-end correctness
, a correctness condition that focuses on applications only, and outline a research vision to obtain virtualization systems with correct virtual to physical mappings.
Clover
Authors: Liu Qingrui , Jung Changhee , Lee Dongyoon , Tiwari Devesh
Published: April 2020

This paper presents Clover, a compiler directed soft error detection and recovery scheme for lightweight soft error resilience. The compiler carefully generates soft error tolerant code based on idempotent processing without explicit checkpoint. During program execution, Clover relies on a small number of acoustic wave detectors deployed in the processor to identify soft errors by sensing the wave made by a particle strike. To cope with DUE (detected unrecoverable errors) caused by the sensing latency of error detection, Clover leverages a novel selective instruction duplication technique called tail-DMR (dual modular redundancy). Once a soft error is detected by either the sensor or the tail-DMR, Clover takes care of the error as in the case of exception handling. To recover from the error, Clover simply redirects program control to the beginning of the code region where the error is detected. The experiment results demonstrate that the average runtime overhead is only 26%, which is a 75% reduction compared to that of the state-of-the-art soft error resilience technique.
WCET-Aware Dynamic D-cache Locking for A Single Task
Authors: Zheng Wenguang , Wu Hui
Published: April 2020

Caches have been extensively used to bridge the increasing speed gap between processors and off-chip memory. However, caches make it much harder to compute the WCET (Worst-Case Execution Time) of a program. Cache locking is an effective technique for overcoming the unpredictability problem of caches. We investigate the WCET aware D-cache locking problem for a single task, and propose two dynamic cache locking approaches. The first approach formulates the problem as a global ILP (Integer Linear Programming) problem that simultaneously selects a near-optimal set of variables as the locked cache contents and allocates them to the D-cache. The second one iteratively constructs a subgraph of the CFG of the task where the lengths of all the paths are close to the longest path length, and uses an ILP formulation to select a near-optimal set of variables in the subgraph as the locked cache contents and allocate them to the D-cache. For both approaches, we propose a novel, efficient D-cache allocation algorithm. We have implemented both approaches and compared them with the longest path-based, dynamic cache locking approach proposed in [22] and the static WCET analysis approach without cache locking proposed in [14] by using a set of benchmarks from the Mälardalen WCET benchmark suite, SNU real-time benchmarks and the benchmarks used in [27]. Compared to the static WCET analysis approach, the average WCET improvements of the first approach range between 11.3% and 31.6%, and the average WCET improvements of the second approach range between 12.3% and 32.9%. Compared to the longest path-based, dynamic cache locking approach, the average WCET improvements of the first approach range between 4.7% and 14.3%, and the average WCET improvements of the second approach range between 5.3% and 15.0%.
Improving the Precision of Abstract Interpretation Based Cache Persistence Analysis
Authors: Zhang Zhenkai , Koutsoukos Xenofon
Published: April 2020

When designing hard real-time embedded systems, it is required to estimate the worst-case execution time (WCET) of each task for schedulability analysis. Precise cache persistence analysis can significantly tighten the WCET estimation, especially when the program has many loops. Methods for persistence analysis should safely and precisely classify memory references as persistent. Existing safe approaches suffer from multiple sources of pessimism and may not provide precise results. In this paper, we first identify some sources of pessimism that two recent approaches based on younger set and may analysis may encounter. Then, we propose two methods to eliminate these sources of pessimism. The first method improves the update function of the may analysis-based approach; and the second method integrates the younger set-based and may analysis-based approaches together to further reduce pessimism. We also prove the two proposed methods are still safe. We evaluate the approaches on a set of benchmarks and observe the number of memory references classified as persistent is increased by the proposed methods. Moreover, we empirically compare the storage space and analysis time used by different methods.
Semantics Driven Hardware Design, Implementation, and Verification with ReWire
Authors: Procter Adam , Harrison William L. , Graves Ian , Becchi Michela , Allwein Gerard
Published: April 2020

There is no such thing as high assurance without high assurance hardware. High assurance hardware is essential, because any and all high assurance systems ultimately depend on hardware that conforms to, and does not undermine, critical system properties and invariants. And yet, high assurance hardware development is stymied by the conceptual gap between formal methods and hardware description languages used by engineers. This paper presents ReWire, a functional programming language providing a suitable foundation for formal verification of hardware designs, and a compiler for that language that translates high-level, semantics-driven designs directly into working hardware. ReWire's design and implementation are presented, along with a case study in the design of a secure multicore processor, demonstrating both ReWire's expressiveness as a programming language and its power as a framework for formal, high-level reasoning about hardware systems.
The genie in the machines
Authors: Caras Jonathan
Published: April 2020

The ultimate goal of the Internet of Things and wearable revolution is to gift every person with their own magic genie, who will understand all of their needs and desires and thereby enrich the world around them.
Global synchronization and the challenges of building network awareness
Authors: Apsel Alyssa B. , Gantsog Enkhbayasgalan
Published: April 2020

The Internet of Things places new demands on wireless networks that cannot be met with conventional infrastructure, services, and protocols. But there is hope, specifically a new paradigm to enable wireless awareness through global synchronization.
Panasonic and the OpenDOF project
Authors: Eastham Bryant
Published: April 2020

Is the decision to go open-source always purely altruistic? Not for many large companies, and that is not a bad thing.
Complexity column
Authors: Immerman Neil
Published: April 2020

The bird on my birdfeeder instantly processes any change to its visual input: should it flee or keep eating? In dynamic complexity, we ask what information we should maintain, so that, upon a small change to our input, we can quickly compute the new answer to a certain query. It had been a long-standing open question whether graph reachability could be maintained in first-order logic. A recent breakthrough result is that yes, it can. In this column, Thomas Schwentick and Thomas Zeume explain this new result and map out the current landscape of Dynamic Complexity.
Dynamic complexity
Authors: Schwentick Thomas , Zeume Thomas
Published: April 2020

In many data management scenarios the data is subject to frequent modifications, and it is often essential to react to those changes quickly. When a train is canceled on short notice, travelers need to find alternative connections as fast as possible. When a web server is temporarily not available, data packages have to be rerouted immediately.
Verification column
Authors: Rungta Neha
Published: April 2020

The technical column on verification presents an invited contribution by Dr. Franco Raimondi (Department of Computer Science in Middlesex University, London) titled "Using multi-agent systems to go beyond temporal patterns verification" in the April issue of the SIGLOG newsletter. This article presents an introduction to epistemic logic and verification of epistemic properties. Epistemology is defined as the
the study of the nature and scope of knowledge and justified belief. It analyzes the nature of knowledge and how it relates to similar notions such as truth, belief, and justification
. Epistemic properties has been applied to philophical reasonings; more recently, it has been applied to state properties of social interactions, artificial intelligence applications, security application, multi-agent systems. The article presents extension of the temporal logics to support epistemetic properites and verification of it as well. This article I believe is will be of interest to people in the logic community as well as the verification community. There has been a lot of work in the past twenty years in th field of verification specifically model checking of multi-agent systems; this article presents an overview of the MCMAS model checker. Thank you Dr. Raimondi for this insightful article.
Automata column
Authors: Bojańczyk Mikołaj
Published: April 2020

A (word) transducer is an automaton with output, which defines a binary relation on words, including the important special case of a function from words to words. For the uninitiated, the transducer landscape can be a bit confusing, since there are several non-equivalent models (unlike for languages, where all reasonable models of finite automata are equivalent). In this column, Emmanuel Filiot and Pierre-Alain Reynier explain this landscape, with an emphasis on the connections with logic and algebra.
Semantics column
Authors: Mislove Michael , Panangaden Prakash
Published: April 2020

In this quarter's column, Stephen Brookes and Peter O'Hearn describe how
Concurrent Separation Logic (CSL)
arose, including a little about the soundness proof and a discussion of later developments that arose from CSL. The column is especially timely, since Steve and Peter were just awarded this year's Gödel Prize for their work on CSL. The Gödel Prize was officially awarded for the papers [2] and [1] which describe CSL and its semantics. The Gödel Prize is testament to the importance of CSL as a fundamental tool for proving concurrent programs correct; the soundness proof forms a crucial component of this contribution.
Conference reports
Authors: Pérez Jorge A.
Published: April 2020

This installment of the conference report column includes a report by Hugo Torres Vieira (IMT School for Advanced Studies Lucca, Italy) on DisCoTec 2016, a which took place in Heraklion, Greece on June 6-9, 2016.
Semantics column
Authors: Mislove Michael
Published: April 2020

This quarter's Semantics column features an article by Jean Krivine, a CNRS researcher who is a member of the Proofs, Programs and Systems group that forms a part of the Institute for Fundamental Research in Informatics (IRIF) at Université Paris Diderot. Jean is leader in the application of computer science to Systems Biology, a broad area whose research activities range from biologists in wet labs, to computational scientists devising simulations based on mathematical models, to computer scientists developing models based on computer science models and their underlying principles. Jean's column highlights the tension that arises when wet lab researchers, who are accustomed to time-tested research methodologies, confront new approaches driven by novel applications of computer science and its principles to the problems they face. The column also describes the issues computer scientists face if they want to have a significant impact in a related discipline. Last but surely not least, Jean's description of the Kappa language and its application to protein interactions provides an impressive example of how concurrency theory and techniques developed within computer science can usefully be applied in a related discipline.
Conference reports
Authors: Pérez Jorge A
Published: April 2020

In this installment of the conference report column, Andrej Bauer (University of Ljubljana, Slovenia) reports on the 33rd Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIII) and the 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017).
Automata column
Authors: Bojańczyk Mikołaj
Published: April 2020

Probabilistic automata are, at first glance, a mild generalisation of nondeterministic automata. It turns out, however, that adding probability makes natural questions undecidable, e.g. "decide if there is some word accepted with probability at least 1/2". In this column, Nathanaël Fijalkow explains this and other undecidability results.
Security & privacy column
Authors: Maffei Matteo
Published: April 2020

The present column is dedicated to
cryptographic protocol analysis
, a research field in which the synergy between logics and security has proven particularly fruitful, leading to the development of automated cryptographic protocol verifiers, which are by now mature enough to handle today's protocol standards, such as TLS. This is a remarkable result, given the complexity of protocol analysis: security properties, which encompass trace properties as well as observational equivalence relations, are undecidable and, in particular, have to be proven against a universally quantified attacker, which can schedule the communication among honest parties, possibly interleaving different protocol sessions, and arbitrarily intercept, modify and create cryptographic messages.
Symbolically analyzing security protocols using tamarin
Authors: Basin David , Cremers Cas , Dreier Jannik , Sasse Ralf
Published: April 2020

During the last three decades, there has been considerable research devoted to the symbolic analysis of security protocols and existing tools have had considerable success both in detecting attacks on protocols and showing their absence. Nevertheless, there is still a large discrepancy between the symbolic models that one specifies on paper and the models that can be effectively analyzed by tools.
Semantics column
Authors: Mislove Michael
Published: April 2020

This quarter's Semantics column continues a theme initiated by Prakash Panangaden in Issue 4 [5]. There Prakash described the history of probabilistic bisimulation, the fundamental relation characterizing when states of a probabilistic system are indistinguishable. Prakash focused his discussion around labelled Markov processes as models of probabilistic systems, and he described a logic he and his colleagues developed to characterize probabilistic bisimilarity in that setting.
Automata column
Authors: Bojańczyk Mikołaj
Published: April 2020

In this column, Diego Figueira writes about satisfiability for XPath. This is a logic that describes nodes in XML documents; most likely you have an XPath evaluator running right now in your browser. The difficulty of the logic is that it describes properties of data trees, i.e. the set of labels is not finite (a typical label could be a URL). The logic is sensitive to such labels - it can test for example if all nodes have different labels. This leads to a number of difficulties in applying the automata method, and Diego's survey shows how (and in which cases) these difficulties can be overcome.
Semantics column
Authors: Mislove Michael
Published: April 2020

I am pleased to introduce J
ane
H
illston
as this quarter's SIGLOG Semantics columnist. Jane's research focuses on performance modeling of computer and communications systems using Markovian stochastic process algebra. This area combines the computational approach of process calculi with stochastic methods from probability in the form of Markov processes. Jane began exploring this area in her PhD thesis, when she introduced the stochastic process algebra PEPA. Since then, Jane has been a leader in applying stochastic process algebra to performance modeling. She has devised adaptions of PEPA to address specific applications, such as mobile computation (PEPA nets), systems biology (Bio-PEPA), and hybrid systems (HYPE). She has applied these tools to analyze the collective dynamics of discrete systems, to model biochemical signaling pathways, to model temporal aspects of biological phenomena more generally, to assess the quality of services offered in large distributed systems, to evaluate protocols for mobility and quality of service in a wireless setting, and to help develop formal methods for use in a broad study of collective adaptive systems. Jane's column describes the history and development of various approaches to stochastic process algebras, and highlights some of the contributions of performance analysis to our understanding of these various complex systems.
Verification column
Authors: Lazić Ranko
Published: April 2020

I am honoured to take up the role of the Verification editor for the SIGLOG newsletter, and I am inspired by my predecessor Neha Rungta whose work will be a tough act to follow.
Substructural logics
Authors: Ciabattoni Agata , Genco Francesco A. , Ramanayake Revantha
Published: April 2020

Substructural logics: semantics, proof theory, and applications
is the second workshop within the project SYSMICS (Syntax meets Semantics - Methods, Interactions, and Connections in Substructural logics). It was held in Vienna at the Faculty of Mathematics, University of Vienna, from 26 -- 28 February 2018.
Security & privacy column
Authors: Maffei Matteo
Published: April 2020

The present column continues our excursion in
cryptographic
protocol
analysis
. Here Stephanie Delaune presents the exciting research challenges behind her recent ERC Starting Grant "POPSTAR: reasoning about physical properties of security protocols with an application to contactless systems". The overall research goal is to develop techniques and tools to analyse protocols that establish and rely on properties of the physical world, such as distance bounding protocols, contactless payment systems, etc. While the hope is to leverage the extraordinary results arising from years of research in cryptographic protocol analysis, formally characterizing physical properties in communication protocols is a fascinating challenge that demands novel solutions.
Discotec 2018 conference report
Authors: Mezzina Claudio Antares
Published: April 2020

The 13th International Federated Conference on Distributed Computing Techniques (DisCoTec 2018) took place in Madrid (Spain) from June 18 to June 21, 2018. The general chair was Manuel Núñez (Universidad Complutense de Madrid, Spain).