# Browsing by Subject "Synchronization"

Now showing 1 - 7 of 7

- Results Per Page
1 5 10 20 40 60 80 100

- Sort Options
Ascending Descending

Item Asynchronous automatic-signal monitors with multi-object synchronization(2016-12) Hung, Wei-Lun; Garg, Vijay K. (Vijay Kumar), 1963-; Julien, Christine; Khurshid, Sarfraz; Mittal, Neeraj; Perry, Dewayne E; Pingali, KeshavShow more One of the fundamental problems in parallel programming is that there is no simple programming paradigm that provides mutual exclusion and synchronization with efficient implementation at the same time. For monitor [Hoa74,Han75] (lock-based) systems, only experienced programmers can develop high-performance fine-grained lock-based implementations. Programmers frequently introduce bugs with traditional monitors. Researchers have proposed transactional memory [HM93,ST95], which provides a simple and elegant mechanism for programmers to atomically execute a set of memory operations so that there is no deadlock in transactional memory systems. However, most of transactional memory systems lack conditional synchronization support [WLS14,LW14]. Hence, writing multi-threaded programs with conditional synchronization is rather difficult. In this dissertation, we develop a parallel programming framework that provides simple constructs for mutual exclusion and synchronization as well as efficient implementation.Show more Item Improved algorithms and hardware designs for division by convergence(2009-12) Kong, Inwook; Swartzlander, Earl E.Show more This dissertation focuses on improving the division-by-convergence algorithm. While the division by convergence algorithm has many advantages, it has some drawbacks, such as a need for extra bits in the multiplier and a large ROM table for the initial approximation. To mitigate these problems, two new methods are proposed here. In addition, the research scope is extended to seek an efficient architecture for implementing a divider with Quantum-dot Cellular Automata (QCA), an emerging technology. For the first proposed approach, a new rounding method to reduce the required precision of the multiplier for division by convergence is presented. It allows twice the error tolerance of conventional methods and inclusive error bounds. The proposed method further reduces the required precision of the multiplier by considering the asymmetric error bounds of Goldschmidt dividers. The second proposed approach is a method to increase the speed of convergence for Goldschmidt division using simple logic circuits. The proposed method achieves nearly cubic convergence. It reduces the logic complexity and delay by using an approximate squarer with a simple logic implementation and a redundant binary Booth recoder. Finally, a new architecture for division-by-convergence in QCA is proposed. State machines for QCA often have synchronization problems due to the long wire delays. To resolve this problem, a data tag method is proposed. It also increases the throughput significantly since multiple division computations can be performed in a time skewed manner using one iterative divider.Show more Item Millimeter wave link configuration with hybrid MIMO architectures(2020-07-08) Rodríguez-Fernández, Javier; Evans, Brian L., (Brian Lawrence), 1965-; Andrews, Jeffrey G; Tewfik, Ahmed H; Torlak, Murat; Vikalo, HarisShow more The use of multiple antennas, widely known as MIMO technology, is a key feature to deploy mmWave communication systems enabling high-data-rate applications. With more than two decades of global experience in deploying Wi-Fi and cellular communication using sub-6 GHz frequency bands, simply repurposing these designs for mmWave bands would fail to account for additional propagation impairments and circuit design constraints at these higher frequencies. A solution to overcome the propagation challenges is the use of multiple directional communication beams, whereby proper alignment between transceivers provides sufficient link quality to enable reliable decoding of the transmitted data. In this dissertation, efficient link configuration solutions suitable for mmWave cellular communications are developed. To gain some insight into the achievable performance of mmWave systems, two broadband channel-estimation-based link configuration solutions are proposed for MIMO-OFDM systems, in which both the transmitter and receiver are assumed to be perfectly synchronized. The proposed solution exploits the spatially common sparsity in the mmWave channel and enables efficient acquisition of the CSI while allowing the use of multiple RF chains on both the transmitter and receiver sides. In a simplified scenario, the CRLB for the channel estimation problem is derived, and the proposed channel estimation algorithms are shown to both outperform prior work in communication performance and exhibit excellent estimation performance. Furthermore, the proposed algorithms are assessed in a more challenging scenario with realistic channel parameters, and it is shown that both near-optimal spectral efficiency and low BER can be attained with lower overhead and computational complexity than prior solutions. Next, the impact of imperfect CFO synchronization on the channel estimation problem is analyzed under a narrowband channel model. The CRLB for the estimation of the different unknown parameters involved in the problem is theoretically analyzed, and closed-form expressions are provided for the estimation of the different parameters. Under a joint estimation-theoretic and CS framework, a low-complexity multi-stage solution is proposed to estimate both the different unknown synchronization parameters and the large-dimensional mmWave MIMO channel. Different trade-offs between estimation, spectral efficiency, and overhead performance are exposed, and the proposed estimators are shown to be asymptotically optimal in the low SNR regime. The proposed solution is assessed under a channel model with several clusters and rays per cluster, and is shown to attain near-optimal spectral efficiency values in both the low and high SNR regimes. The computational complexity of the proposed solution is also analyzed, in which it is shown to achieve a marginal increase in computational complexity with respect to the solution proposed in the previous contribution. Finally, the impact of TO, CFO, and PN impairments on the channel estimation problem is analyzed under a broadband channel model. The problem of time-frequency synchronization under PN impairments is theoretically analyzed, and the proposed solutions to the synchronization problem are exploited to estimate the frequency-selective mmWave MIMO channel. The hybrid CRLB for the estimation of the different synchronization impairments is analyzed, and closed-form expressions leveraging the information coupling between the different impairments are provided. The previously proposed joint estimation-theoretic and CS framework is extended to frequency-selective scenarios, and two low-complexity multi-stage solutions are proposed to estimate both the different synchronization impairments and the large-dimensional mmWave MIMO channel. The first solution relies on a batch-processing LMMSE-based EM algorithm to estimate the different synchronization impairments, while the second solution uses a sequential-processing EKF-RTS-based EM algorithm, thereby reducing computational complexity. Thereafter, both the hybrid CRLB for the estimation of the equivalent beamformed complex channels and the estimates for these parameters are exploited to estimate the large-dimensional frequency-selective mmWave MIMO channel. Finally, a joint PN and data detection algorithm is proposed for data transmission under the 5G NR frame structure. The proposed solutions are evaluated using a 5G NR-based channel model, and different trade-offs between estimation performance, computational complexity, overhead, achievable spectral efficiency and BER are exposed, and comparisons with prior work are also provided. The results show that mmWave link configuration using hybrid MIMO architectures can be established with low overhead without assuming synchronization, even in the low SNR regime.Show more Item Reliable distributed information : agreement and structure(2019-02-01) Bridgman, John Francis, III; Garg, Vijay K. (Vijay Kumar), 1963-; Shakkottai, Sanjay; Arapostathis, Ari; Gouda, Mohamed; Sanghavi, SujayShow more The world is inherently distributed and concurrent. The more complicated systems become, the more likely they are to fail or partially fail. This work presents several results with Byzantine Agreement and some results of using coding in solving distributed and concurrent problems. We explore adding weights to processes to model a priori knowledge of process reliability. Then, some results of what can be done when performing repeated agreement. A result between combinatorial geometry and approximate Byzantine agreement is also provided. Coding is often used in communication, but here we provide examples of the usage of coding to minimize broadcast information and to solve a concurrent problem. The first use of coding is to notice the redundant information in distributed protocols and how to use a code to reduce the amount of information needed to be transmitted. The second is a method of using coding to provide a buffer of memory in a concurrent system that can be updated such that readers see the update as atomic.Show more Item Towards secure & robust PNT for automated systems(2020-12-04) Narula, Lakshay; Humphreys, Todd Edwin; Vikalo, Haris; Tiwari, Mohit; Gonzalez-Prelcic, Nuria; Jones, Brandon A.Show more This dissertation makes four contributions in support of secure and robust position, navigation, and timing (PNT) for automated systems. The first two relate to PNT security while the latter two address robust positioning for automated ground vehicles. The first contribution is a fundamental theory for provably-secure clock synchronization between two agents in a distributed automated system. All one-way synchronization protocols, such as those based on the Global Positioning System (GPS) and other Global Navigation Satellite Systems (GNSS), are shown to be vulnerable to man-in-the-middle delay attacks. This contribution is the first to identify the necessary and sufficient conditions for provably secure clock synchronization. The second contribution, also related to PNT security, is a three-year study of the world-wide GPS interference landscape based on data from a dual-frequency GNSS receiver operating continuously on the International Space Station (ISS). This work is the first publicly-reported space-based survey of GNSS interference, and unveils previously-unreported GNSS interference activity. The third contribution is a novel ground vehicle positioning technique that is robust to GNSS signal blockage, poor lighting conditions, and adverse weather events such as heavy rain and dense fog. The technique relies on sensors that are commonly available on automated vehicles and are insensitive to lighting and inclement weather: automotive radar, low-cost inertial measurement units (IMUs), and GNSS. Remarkably, it is shown that, given a prior radar map, the proposed technique operating on data from off-the-shelf all-weather automotive sensors can maintain sub-50-cm horizontal position accuracy during 60 min of GNSS-denied driving in downtown Austin, TX. This dissertation’s final contribution is an analysis and demonstration of the feasibility of crowd-sourced digital mapping for automated vehicles. Localization techniques, such as the one described in the previous contribution, rely on such digital maps for accuracy and robustness. A key enabler for large-scale up-to-date maps is enlisting the help of the very consumer vehicles that need the map to build and update it. A method for fusing multi-session vision data into a unified digital map is developed. The asymptotic limit of such a map’s globally-referenced position accuracy is explored for the case in which the mapping agents rely on low-cost GNSS receivers performing standard code-phase-based navigation. Experimental validation along a semi-urban route shows that low-cost consumer vehicles incrementally tighten the accuracy of the jointly-optimized digital map over time enough to support sub-lane-level positioning in a global frame of reference.Show more Item Transparent replication(2006) Nayate, Amol Pramod; Dahlin, MikeShow more Increasing user expectations and demands have caused the evolution of web services away from single-server systems and toward distributed systems for their ability to provide improved throughput, improved availability and reduced response times. However, for a service to run on a distributed system, each running instance must be able to access data that are shared among the instances. Although existing off-the-shelf replication systems - e.g. distributed file systems [52, 61, 32, 38, 41], replicated databases [64, 75], distributed hash tables [58, 59, 63, 34], etc. - simplify access to shared data by exporting wellresearched interfaces, their implementations are typically not engineered for the unique environments presented by many web services. For example, replication systems that require synchronization across multiple nodes to handle modified data [38, 12] or systems that require all nodes to keep a copy of all data [64, 75] may not be practical for use in such services. Although the problem of general replication is not possible to solve [11, 62, 33] we focus our study on a class of single-writer services that we denote Information Dissemination Services that form a restrictive but important set of web services. Our research makes two key contributions. First, we show that for a class of single-writer services that we denote Information Dissemation Services TRIP replicates dynamic data in a manner that is nearly transparent to the service. We (1) develop a novel dual-channel replication algorithm for TRIP that utilizes spare network background traffic to speculatively replicate data in a safe, non-interfering fashion, (2) show how to integrate safe speculative replication with mechanisms that use invalidates to provide consistency, and (3) demonstrate how our combination of consistency and safe speculative replication allows us to provide near-ideal consistency, performance, and availability for Information Dissemination Services. Second, we show that the core principles behind building TRIP can be extended to build a new replication framework and more general replication toolkit. In particular, we show that it is possible to extend our dual-queue mechanisms developed for TRIP to a multi-writer environment where nodes can synchronize multiple incoming streams of data and consistency information. Our extension allows providing various forms of consistency for arbitrary topologies - two key properties provided by the PRACTI [6] (Partial Replication, Arbitrary Consistency, Topology Independence) architecture.Show more Item Verification of sequential and concurrent libraries(2010-08) Deshmukh, Jyotirmoy Vinay; Emerson, E. Allen; Aziz, Adnan; Garg, Vijay K.; Chase, Craig M.; Khurshid, Sarfraz; Mok, Aloysius K.Show more The goal of this dissertation is to present new and improved techniques for fully automatic verification of sequential and concurrent software libraries. In most cases, automatic software verification is plagued by undecidability, while in many others it suffers from prohibitively high computational complexity. Model checking -- a highly successful technique used for verifying finite state hardware circuits against logical specifications -- has been less widely adapted for software, as software verification tends to involve reasoning about potentially infinite state-spaces. Two of the biggest culprits responsible for making software model checking hard are heap-allocated data structures and concurrency. In the first part of this dissertation, we study the problem of verifying shape properties of sequential data structure libraries. Such libraries are implemented as collections of methods that manipulate the underlying data structure. Examples of such methods include: methods to insert, delete, and update data values of nodes in linked lists, binary trees, and directed acyclic graphs; methods to reverse linked lists; and methods to rotate balanced trees. Well-written methods are accompanied by documentation that specifies the observational behavior of these methods in terms of pre/post-conditions. A pre-condition [phi] for a method M characterizes the state of a data structure before the method acts on it, and the post-condition [psi] characterizes the state of the data structure after the method has terminated. In a certain sense, we can view the method as a function that operates on an input data structure, producing an output data structure. Examples of such pre/post-conditions include shape properties such as acyclicity, sorted-ness, tree-ness, reachability of particular data values, and reachability of pointer values, and data structure-specific properties such as: "no red node has a red child'', and "there is no node with data value 'a' in the data structure''. Moreover, methods are often expected not to violate certain safety properties such as the absence of dangling pointers, absence of null pointer dereferences, and absence of memory leaks. We often assume such specifications as implicit, and say that a method is incorrect if it violates such specifications. We model data structures as directed graphs, and use the two terms interchangeably. Verifying correctness of methods operating on graphs is an instance of the parameterized verification problem: for every input graph that satisfies [phi], we wish to ensure that the corresponding output graph satisfies [psi]. Control structures such as loops and recursion allow an arbitrary method to simulate a Turing Machine. Hence, the parameterized verification problem for arbitrary methods is undecidable. One of the main contributions of this dissertation is in identifying mathematical conditions on a programming language fragment for which parameterized verification is not only decidable, but also efficient from a complexity perspective. The decidable fragment we consider can be broadly sub-divided into two categories: the class of iterative methods, or methods which use loops as a control flow construct to traverse a data structure, and the class of recursive methods, or methods that use recursion to traverse the data structure. We show that for an iterative method operating on a directed graph, if we are guaranteed that if the number of destructive updates that a method performs is bounded (by a constant, i.e., O(1)), and is guaranteed to terminate, then the correctness of the method can be checked in time polynomial in the size of the method and its specifications. Further, we provide a well-defined syntactic fragment for recursive methods operating on tree-like data structures, which assures that any method in this fragment can be verified in time polynomial in the size of the method and its specifications. Our approach draws on the theory of tree automata, and we show that parameterized correctness can be reduced to emptiness of finite-state, nondeterministic tree automata that operate on infinite trees. We then leverage efficient algorithms for checking the emptiness of such tree automata to obtain a tractable verification framework. Our prototype tool demonstrates the low theoretical complexity of our technique by efficiently verifying common methods that operate on data structures. In the second part of the dissertation, we tackle another obstacle for tractable software verification: concurrency. In particular, we explore application of a static analysis technique based on interprocedural dataflow analysis to predict and document deadlocks in concurrent libraries, and analyze deadlocks in clients that use such libraries. The kind of deadlocks that we focus result from circular dependencies in the acquisition of shared resources (such as locks). Well-written applications that use several locks implicitly assume a certain partial order in which locks are acquired by threads. A cycle in the lock acquisition order is an indicator of a possible deadlock within the application. Methods in object-oriented concurrent libraries often encapsulate internal synchronization details. As a result of information hiding, clients calling the library methods may cause thread safety violations by invoking methods in a manner that violates the partial ordering between lock acquisitions that is implicit within the library. Given a concurrent library, we present a technique for inferring interface contracts that speciy permissible concurrent method calls and patterns of aliasing among method arguments that guarantee deadlock-free execution for the methods in the library. The contracts also help client developers by documenting required assumptions about the library methods. Alternatively, the contracts can be statically enforced in the client code to detect potential deadlocks in the client. Our technique combines static analysis with a symbolic encoding for tracking lock dependencies, allowing us to synthesize contracts using a satisfiability modulo theories (SMT) solver. Additionally, we investigate extensions of our technique to reason about deadlocks in libraries that employ signalling primitives such as wait-notify for cooperative synchronization. We demonstrate its scalability and efficiency with a prototype tool that analyzed over a million lines of code for some widely-used open-source Java libraries in less than 50 minutes. Furthermore, the contracts inferred by our approach have been able to pinpoint real bugs, i.e. deadlocks that have been reported by users of these libraries.Show more