Search

Concurrency bugs widely exist and severely threaten system availability. Techniques that help recover from concurrency-bug failures during production runs are highly desired. This paper proposes BugTM, an approach that applies transactional memory techniques for concurrency-bug recovery in production runs. Requiring no knowledge about where are concurrency bugs, BugTM uses static analysis and code transformation to enable BugTM-transformed software to recover from a concurrency-bug failure by rolling back and re-executing the recent history of a failure thread. BugTM is instantiated as three schemes that have different trade-offs in performance and recovery capability: BugTM$_H$H uses existing hardware transactional memory (HTM) support, BugTM$_S$S leverages software transactional memory techniques, and BugTM$_{\mathrm{HS}}$ HS is a software-hardware hybrid design. BugTM greatly improves the recovery capability of state-of-the-art techniques with low run-time overhead and no changes to OS or hardware, while guarantees not to introduce new bugs. [ABSTRACT FROM AUTHOR]

Pipelining allows the execution of loop iterations with cross-iteration dependences to overlap in time, provided that the loop body is partitioned into stages such that the data dependences are not violated. Then, the stages are mapped onto threads and communication and synchronization between stages is typically achieved using queues. Pipelining techniques that rely on static scheduling perform poorly for load-imbalanced loops. Moreover, previous research efforts that achieve load-balancing are restricted to work-stealing and imply high overhead for fine-grained loops. In this article, we present URTS, a unified runtime system with compiler support that provides a lightweight dynamic scheduler by combining mapping, communication and synchronization algorithms with a suitable data structure and an efficient ticket mechanism. Particularly, URTS shows that it is possible to combine the efficiency of static scheduling with the load-imbalance tolerance of work-stealing by using a unified design that exploits the properties of a novel data structure. The evaluation on 8- and 32-core machines shows that URTS implies low overhead, of the same order as a static scheduler, for a set of benchmarks chosen from widely-used collections. URTS is a scalable solution that performs efficient dynamic scheduling for fine-grained loops, i.e., a class of interesting loops that is poorly handled by the state-of-the-art due to high overhead. [ABSTRACT FROM AUTHOR]

In the distributed test architecture, the system under test (SUT) interacts with its environment at multiple physically distributed ports and the local testers at these ports do not synchronize their actions. This presents many challenges and, in particular, apparently incorrect behaviors can be the consequence of an erroneous assumption about the exact order in which actions were performed at different ports. In previous work, we defined a conformance relation for the distributed test architecture. Essentially, the SUT is faulty if we observe a trace $\sigma$ such that no admissible reordering of the actions in $\sigma$ could have been produced by the specification. However, this notion can be weak if the compared traces might be too different. This paper introduces conformance relations where, for a given metric, a reordering is only considered if the distance between the two traces is at most a certain bound $k$. We introduce two different metrics and provide algorithms to construct finite automata accepting these close, with respect to each metric, sequences. We also study the computational complexity of the two main problems associated with the new framework: deciding whether a trace is accepted by the new automaton and deciding whether one system conforms to a specification with respect to the new conformance relation. [ABSTRACT FROM AUTHOR]

A delay of less than one millisecond is required by low-latency 5G wireless communication systems for supporting the “tactile” Internet. Hence, conventional initial synchronisation cannot be readily employed because of its potentially excessive delay. In this paper, an extrinsic information transfer (EXIT) chart assisted approach is used for the convergence analysis of $m$-sequences using recursive soft sequence estimation (RSSE) in the context of Nakagami-m fading channels. Explicitly, the novelty of our work is based on employing a new type of EXIT charts operating without using interleavers. This is a challenge, because the original EXIT charts rely on the employment of long, high-delay interleavers for ensuring that the inputs to the decoders become uncorrelated. We then evaluate the performance of various classes of $m$-sequences with the aid of the proposed EXIT charts and demonstrate that the $m$-sequences generated by the lower order polynomials maximize the mutual information more promptly with the aid of our RSSE scheme than those that belong to a higher order polynomial. [ABSTRACT FROM PUBLISHER]

Recent years have witnessed the booming popularity of CLS platforms, through which numerous amateur broadcasters live stream their video contents to viewers around the world. The heterogeneous qualities and formats of the source streams, however, require massive computational resources to transcode them into multiple industrial standard quality versions to serve viewers with distinct configurations, and the delays to the viewers of different locations should be well synchronized to support community interactions. This article attempts to address these challenges and to explore the opportunities with new generation computation paradigms, in particular, fog computing. We present a novel fog-based transcoding framework for CLS platforms to offload the transcoding workload to the network edge (i.e., the massive number of viewers). We evaluate our design through our PlanetLab-based experiment and real-world viewer transcoding experiment. [ABSTRACT FROM PUBLISHER]

Reader-mostly synchronization schemes, such as rwlocks and RCU, aim to maximize parallelism among readers, but many existing designs either cause readers to contend, or significantly extend writer latency, or both. This paper attributes such a problem to the lack of a fast consensus protocol between readers and writers, by which the two parts cooperate to obey the semantics of a synchronization construct. This paper describes FCP, a fast consensus protocol among readers and writers that provides scalable read-side performance as well as small writer latency for TSO architectures. The heart of FCP is a version-based consensus protocol between multiple non-communicating readers and a pending writer. FCP leverages bounded staleness of memory consistency to avoid atomic instructions and memory barriers in readers’ common paths, and uses message-passing (e.g., IPI) for straggling readers so that the writer latency can be bounded. To demonstrate the effectiveness of FCP, this paper applies FCP to construct a scalable reader-writers lock (rwlock) and a scalable RCU implementation. Evaluation on a 64-core machine shows that FCP significantly boosts the performance of the Linux virtual memory subsystem, a concurrent hashtable and an in-memory database. Micro-benchmarks show that FCP achieves smaller reader-side latency and lower writer-side latency when compared to state-of-the-art rwlocks and RCU implementation. [ABSTRACT FROM AUTHOR]

We consider the problem of synchronizing coded data in distributed storage networks undergoing insertion and deletion edits. We present modifications of distributed storage codes that allow updates in the parity-check values to be performed with one round of communication at low bit rates and with small storage overhead. Our main contributions are novel protocols for synchronizing frequently updated and semi-static data based on functional intermediary coding involving permutation and Vandermonde matrices. [ABSTRACT FROM PUBLISHER]

Clock synchronization is highly desirable in distributed systems, including many applications in the Internet of Things and Humans. It improves the efficiency, modularity, and scalability of the system, and optimizes use of event triggers. For IoTH, BLE - a subset of the recent Bluetooth v4.0 stack - provides a low-power and loosely coupled mechanism for sensor data collection with ubiquitous units (e.g., smartphones and tablets) carried by humans. This fundamental design paradigm of BLE is enabled by a range of broadcast advertising modes. While its operational benefits are numerous, the lack of a common time reference in the broadcast mode of BLE has been a fundamental limitation. This article presents and describes CheepSync, a time synchronization service for BLE advertisers, especially tailored for applications requiring high time precision on resource constrained BLE platforms. Designed on top of the existing Bluetooth v4.0 standard, the CheepSync framework utilizes low-level timestamping and comprehensive error compensation mechanisms for overcoming uncertainties in message transmission, clock drift, and other system-specific constraints. CheepSync was implemented on custom designed nRF24Cheep beacon platforms (as broadcasters) and commercial off-the-shelf Android ported smartphones (as passive listeners). We demonstrate the efficacy of CheepSync by numerous empirical evaluations in a variety of experimental setups, and show that its average (single-hop) time synchronization accuracy is in the 10 μs range. [ABSTRACT FROM PUBLISHER]

In real-time systems, both scheduling theory and resource access protocols have been studied extensively. However, there is very limited research on scheduling algorithms for real-time systems with shared resources, where the problem becomes more prominent with the emergence of multicore processors. In this paper, focusing on partitioned-EDF scheduling and MSRP resource access protocol, we study the utilization bound and efficient task mapping schemes for a set of periodic real-time tasks that access shared resources in multiprocessor/multicore systems. Specifically, with synchronization overhead being considered, we illustrate the schedulability anomaly for such systems. We develop the first synchronization-cognizant utilization bound and further analyze its non-monotonicity where the bound can decrease when more processors are deployed. Then, we show that finding the optimal mapping for tasks with shared resources is NP-hard. Based on a novel approach that iteratively tightens the synchronization overhead, we propose two efficient synchronization-cognizant task mapping algorithms (SC-TMA) with the goal of achieving better schedulability and balanced workload on deployed processors. Finally, the proposed SC-TMA schemes are evaluated through extensive simulations with synthetic tasks. The results show that, the schedulability ratio and (average) system load under SC-TMA are close to that of an INLP (Integer Non-Linear Programming) based solution for small task systems. When compared to the existing task mapping algorithms, SC-TMA obtain much better schedulability ratio and lower/balanced workload on all processors. [ABSTRACT FROM AUTHOR]

Network simulation is an important tool for testing and evaluating wireless sensor network applications. Parallel simulation strategies improve the scalability of these tools. However, achieving high performance depends on reducing the synchronization overhead among simulation processes. In this paper, we present an optimistic simulation algorithm with support for backtracking and re-execution. The algorithm reduces the number of synchronization cycles to the number of transmissions in the network under test. We implement SnapSim, an extension to the popular Avrora simulator, based on this algorithm. The experimental results show that our prototype system improves the performance of Avrora by 2 to 10 times for typical network-centric sensor network applications, and up to three orders of magnitude for applications that use the radio infrequently. We also implement a distributed version of SnapSim, D-SnapSim, which runs on a cluster. The experimental results show that D-SnapSim further improves the performance of SnapSim by up to 10 times for applications that use the radio frequently. [ABSTRACT FROM AUTHOR]

A 800 Mb/s to 3.2 Gb/s memory interface is designed that achieves 30% improved energy efficiency by eliminating idle mode power completely. The link is similar to a standard DDR architecture with the addition of a fast-lock DLL on the memory side that wakes up from 0 mW and locks within 3 clock cycles consuming 24 mW with residual timing error less than 33 mUI. Following initial lock, the DLL operates in a closed loop to compensate for V,T drift consuming 6 mW @ 1.6 GHz including a replica buffer. By incorporating an injection locked oscillator inside the loop, the DLL provides PLL like high frequency input jitter filtering, and corrects ±10% DCD without an additional duty cycle correction loop. [ABSTRACT FROM PUBLISHER]

Modern multicore systems have a large number of components operating in different clock domains and communicating through asynchronous interfaces. These interfaces use synchronizer circuits, which guard against metastability failures but introduce latency in processing the asynchronous input. We propose a speculative method that hides synchronization latency by overlapping it with computation cycles. We verify the correctness of our approach through a field programmable gate array implementation and apply it to a number of synthesized benchmarks. Synthesis results reveal that our approach achieves average savings of 135% and 204% in area costs and nearly 100% in power costs compared to two similar speculative techniques. [ABSTRACT FROM AUTHOR]

The accurate and efficient operation of many applications and protocols in wireless sensor networks require synchronized notion of time. To achieve network-wide time synchronization, a common strategy is to flood current time information of a reference node into the network, which is utilized by the de facto time-synchronization protocol Flooding Time-Synchronization Protocol (FTSP). In FTSP, the propagation speed of the flood is slow because each node waits for a given period of time to propagate its time information about the reference node. It has been shown that slow-flooding decreases the synchronization accuracy and scalability of FTSP drastically. Alternatively, rapid-flooding approach is proposed in the literature, which allows nodes to propagate time information as quickly as possible. However, rapid flooding is difficult and has several drawbacks in wireless sensor networks. In this paper, our aim is to reduce the undesired effect of slow-flooding on the synchronization accuracy without changing the propagation speed of the flood. Within this context, we realize that the smaller the difference between the speeds of the clocks, the smaller the undesired effect of waiting times on the synchronization accuracy. In the light of this realization, our main contribution is to show that the synchronization accuracy and scalability of slow-flooding can drastically be improved by employing a clock speed agreement algorithm among the sensor nodes. We present an evaluation of this strategy on a testbed setup including 20 MICAz sensor nodes. Our theoretical findings and experimental results show that employing a clock speed agreement algorithm among the sensor nodes drastically improves the synchronization accuracy and scalability of slow-flooding. [ABSTRACT FROM AUTHOR]

The use of an external injection-locking source prevents undesired frequency shifts in coupled-oscillator systems. Here an explicit formulation for the analysis of these systems is presented, based on a numerical model of the oscillator elements in free-running regime, obtained with harmonic balance. It demonstrates the opposed effects of oscillator coupling and injection locking in a realistic manner and brings to light the influence of the oscillator characteristics and coupling-network parameters. The explicit expressions provide the minimum injection-locking power required for a full variation of the inter-stage phase shift and enable the locking bandwidth to be fixed or maximized through a suitable choice of the coupling networks. Two different cases are considered: a basic system of three oscillator elements and a general system with any number of elements. In the latter case, the influence of the particular element chosen for the signal injection on the synchronization bandwidth is studied. The stability analysis is based on a perturbation system, which, unlike previous works, relies on a direct analytical calculation of the steady-state solutions, instead of a numerical one. This enables the full coverage of all possible solutions and hence an in-depth understanding of the influence of the coupling network and injection source on the stable phase-shift ranges. The phase noise analysis, applied to the same explicit formulation, demonstrates the injection locking effects and enables the identification of different regions as the offset frequency increases. [ABSTRACT FROM AUTHOR]

Many happened-before-based detectors for debugging multithreaded programs implement vector clocks to incrementally track the casual relations among synchronization events produced by concurrent threads and generate trace logs. They update the vector clocks via vector-based comparison and content assignment in every case. We observe that many such tracking comparison and assignment operations are removable in part or in whole, which if identified and used properly, have the potential to reduce the log traces thus produced. This paper presents our analysis to identify such removable tracking operations and shows how they could be used to reduce log traces. We implement our analysis result as a technique entitled LOFT. We evaluate LOFT on the well-studied PARSEC benchmarking suite and five large-scale real-world applications. The main experimental result shows that on average, LOFT identifies 63.9 percent of all synchronization operations incurred by the existing approach as removable and does not compromise the efficiency of the latter. [ABSTRACT FROM PUBLISHER]

Exascale systems will present programmers with many challenges. The authors review the parallel programming models that are appropriate for such systems and the challenges that implementations of those models face in an exascale system. They also discuss the feasibility of using existing programming systems, thus preserving the investment in legacy applications, as well as the benefits and likelihood of new programming models and systems. [ABSTRACT FROM AUTHOR]

Proper operation of FELs such as the Free-Electron Laser in Hamburg (FLASH)and the European X-Ray Free-Electron Laser (XFEL), which is currently under construction in Hamburg at DESY, requires many specific subsystems to be synchronized with a precision exceeding 10 femtoseconds. Those components are often separated by several hundred meters at FLASH or even kilometers in case of the European XFEL. Such distances mean that it is extremely difficult to use only conventional RF signal distribution in coaxial cables for synchronization because of high losses and excessive phase drifts, while electromagnetic interference is also an issue. Therefore, a laser-based synchronization scheme can be employed in parallel. In this case, the synchronization signals are transmitted via length-stabilized optical fibers. Such an architecture is currently being used at FLASH and will also be the main means of synchronization at the European XFEL. The hardware for such a synchronization system consists of many optical elements such as commercial lasers and self-built free-space and fiber optic setups. However, a significant part of it is also the electronics responsible for control, diagnostics and signal processing as well as high-level servers and front-end software running on those devices. Currently, the VME standard is used throughout FLASH as the basis for the control system digital hardware. For the European XFEL, however, an architecture with a high level of reliability and availability is required as well as one with higher data acquisition and processing rates. Because of that, the Micro Telecommunications Computing Architecture (\muTCA) had been chosen. It is a fairly new standard, provides significantly better performance and employs modern technological solutions making it more suitable for modern accelerator applications than the older VME architecture. The paper presents the latest improvements in the control software for the optical synchronization system based on the VME standard. Servers for phase-locking the lasers as well as controlling the fiber link stabilization units are described in detail. Plans for migration to the new infrastructure are also outlined. [ABSTRACT FROM AUTHOR]

Self-synchronization under the presence of additive noise can be achieved by allocating a certain number of bits of each codeword as markers for synchronization. Difference systems of sets are combinatorial designs which specify the positions of synchronization markers in codewords in such a way that the resulting error-tolerant self-synchronizing codes may be realized as cosets of linear codes. Ideally, difference systems of sets should sacrifice as few bits as possible for a given code length, alphabet size, and error-tolerance capability. However, it seems difficult to attain optimality with respect to known bounds when the noise level is relatively low. In fact, the majority of known optimal difference systems of sets are for exceptionally noisy channels, requiring a substantial amount of bits for synchronization. To address this problem, we present constructions for difference systems of sets that allow for higher information rates while sacrificing optimality to only a small extent. Our constructions utilize optimal difference systems of sets as ingredients and, when applied carefully, generate asymptotically optimal ones with higher information rates. We also give direct constructions for optimal difference systems of sets with high information rates and error tolerance that generate binary and ternary self-synchronizing codes. [ABSTRACT FROM PUBLISHER]

This paper presents MARA, a joint mechanism for automatic rate selection and route quality evaluation in wireless mesh networks. This mechanism targets at avoiding the problems of lack of synchronization between metric and rate selection decisions and inaccurate link quality estimates, common to main existing proposals of multihop wireless routing metrics and automatic rate adaptation. In this proposal, the statistics collected by the routing protocol are used by the rate adaptation algorithm to compute the best rate for each wireless link. This coordinated decision aims at providing better routing and rate choices. In addition to the basic MARA algorithm, two variations are proposed: MARA-P and MARA-RP. The first considers the size of each packet in the transmission rate decision. The second variation considers the packet size also for the routing choices. For evaluation purposes, experiments were conducted on both real and simulated environments. In these experiments, MARA was compared to a number of rate adaptation algorithms and routing metrics. Results from both environments indicate that MARA may lead to an overall network performance improvement. [ABSTRACT FROM AUTHOR]

Over the past few decades, centralized computing systems have been replaced by decentralized systems, consisting of simple nodes interconnected by a communication network. The time reference of the distributed nodes must be synchronized in order to be able to coordinate the operation or compare the data collected by the different nodes. Several synchronization protocols have been developed to be used instead of global positioning system or dedicated synchronization systems. For example, the network time protocol (NTP) is a very popular synchronization protocol used to synchronize computers over wide area networks, like the Internet. In addition, IEEE 1588, a synchronization protocol dedicated to high-performance synchronization in local networks, was recently established. However, submicroseconds synchronization can be obtained only using dedicated hardware devices, thereby increasing the cost of each node. For these reasons, PTP software-only implementations are quite common in real systems, with a resulting synchronization uncertainty varying from a few to hundreds of microseconds and quite burdensome to estimate or measure. The work presented in this paper focuses on the analysis of the major uncertainty contributions in a software-only implementation. Particularly, a careful analysis of timestamp mechanism and time management in a PC platform is carried out. In addition, a method for the experimental evaluation of uncertainty contributions is proposed. A test case based on a software implementation of the IEEE 1588 (the so-called PTPd) is presented. The experimental tests presented in the paper highlight that the main uncertainty source of a software-only synchronization approach is the timestamp method. Timestamping accuracy can be affected by the computational load of the node itself: in normal conditions, the maximum uncertainty introduced by the timestamp mechanism is in the order of 10 \mu\s, but in case of high computational load, it can raise up to 224 \mu\s. [ABSTRACT FROM AUTHOR]

This paper proposes a novel integral frequency offset (IFO) estimation method for orthogonal frequency-division multiplexing (OFDM) systems, which examines the phase changes of synchronization signals infrequency domain. it is shown that the new method provides excellent lFO estimation performance with very low computational complexity. [ABSTRACT FROM AUTHOR]

Several technologies support communication, control, and coordination problems in a distributed development environment. The authors discuss such collaboration and integration technologies and take a close look at their tools for particular software processes, as the technologies often have a general purpose. [ABSTRACT FROM PUBLISHER]