TY - CONF AB - There has been a significant amount of research on hardware and software support for efficient concurrent data structures; yet, the question of how to build correct, simple, and scalable data structures has not yet been definitively settled. In this paper, we revisit this question from a minimalist perspective, and ask: what is the smallest amount of synchronization required for correct and efficient concurrent search data structures, and how could this minimal synchronization support be provided in hardware? To address these questions, we introduce memory tagging, a simple hardware mechanism which enables the programmer to "tag" a dynamic set of memory locations, at cache-line granularity, and later validate whether the memory has been concurrently modified, with the possibility of updating one of the underlying locations atomically if validation succeeds. We provide several examples showing that this mechanism can enable fast and arguably simple concurrent data structure designs, such as lists, binary search trees, balanced search trees, range queries, and Software Transactional Memory (STM) implementations. We provide an implementation of memory tags in the Graphite multi-core simulator, showing that the mechanism can be implemented entirely at the level of L1 cache, and that it can enable non-trivial speedups versus existing implementations of the above data structures. AU - Alistarh, Dan-Adrian AU - Brown, Trevor A AU - Singhal, Nandini ID - 8191 IS - 7 SN - 9781450369350 T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures TI - Memory tagging: Minimalist synchronization for scalable concurrent data structures ER - TY - CONF AB - Concurrent programming can be notoriously complex and error-prone. Programming bugs can arise from a variety of sources, such as operation re-reordering, or incomplete understanding of the memory model. A variety of formal and model checking methods have been developed to address this fundamental difficulty. While technically interesting, existing academic methods are still hard to apply to the large codebases typical of industrial deployments, which limits their practical impact. AU - Koval, Nikita AU - Sokolova, Mariia AU - Fedorov, Alexander AU - Alistarh, Dan-Adrian AU - Tsitelov, Dmitry ID - 7635 SN - 9781450368186 T2 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP TI - Testing concurrency on the JVM with Lincheck ER - TY - CONF AB - We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - Ellen, Faith AU - Gelashvili, Rati AU - Zhu, Leqi ID - 8383 SN - 9781450375825 T2 - Proceedings of the 39th Symposium on Principles of Distributed Computing TI - Brief Announcement: Why Extension-Based Proofs Fail ER - TY - JOUR AB - We present a method for animating yarn-level cloth effects using a thin-shell solver. We accomplish this through numerical homogenization: we first use a large number of yarn-level simulations to build a model of the potential energy density of the cloth, and then use this energy density function to compute forces in a thin shell simulator. We model several yarn-based materials, including both woven and knitted fabrics. Our model faithfully reproduces expected effects like the stiffness of woven fabrics, and the highly deformable nature and anisotropy of knitted fabrics. Our approach does not require any real-world experiments nor measurements; because the method is based entirely on simulations, it can generate entirely new material models quickly, without the need for testing apparatuses or human intervention. We provide data-driven models of several woven and knitted fabrics, which can be used for efficient simulation with an off-the-shelf cloth solver. AU - Sperl, Georg AU - Narain, Rahul AU - Wojtan, Christopher J ID - 8385 IS - 4 JF - ACM Transactions on Graphics SN - 07300301 TI - Homogenized yarn-level cloth VL - 39 ER - TY - JOUR AB - When short-range attractions are combined with long-range repulsions in colloidal particle systems, complex microphases can emerge. Here, we study a system of isotropic particles, which can form lamellar structures or a disordered fluid phase when temperature is varied. We show that, at equilibrium, the lamellar structure crystallizes, while out of equilibrium, the system forms a variety of structures at different shear rates and temperatures above melting. The shear-induced ordering is analyzed by means of principal component analysis and artificial neural networks, which are applied to data of reduced dimensionality. Our results reveal the possibility of inducing ordering by shear, potentially providing a feasible route to the fabrication of ordered lamellar structures from isotropic particles. AU - Pȩkalski, J. AU - Rzadkowski, Wojciech AU - Panagiotopoulos, A. Z. ID - 7956 IS - 20 JF - The Journal of chemical physics TI - Shear-induced ordering in systems with competing interactions: A machine learning study VL - 152 ER - TY - CONF AB - We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest. AU - Baig, Mirza Ahad AU - Hendler, Danny AU - Milani, Alessia AU - Travers, Corentin ID - 8382 SN - 9781450375825 T2 - Proceedings of the 39th Symposium on Principles of Distributed Computing TI - Long-lived snapshots with polylogarithmic amortized step complexity ER - TY - JOUR AB - In the superconducting regime of FeTe(1−x)Sex, there exist two types of vortices which are distinguished by the presence or absence of zero-energy states in their core. To understand their origin, we examine the interplay of Zeeman coupling and superconducting pairings in three-dimensional metals with band inversion. Weak Zeeman fields are found to suppress intraorbital spin-singlet pairing, known to localize the states at the ends of the vortices on the surface. On the other hand, an orbital-triplet pairing is shown to be stable against Zeeman interactions, but leads to delocalized zero-energy Majorana modes which extend through the vortex. In contrast, the finite-energy vortex modes remain localized at the vortex ends even when the pairing is of orbital-triplet form. Phenomenologically, this manifests as an observed disappearance of zero-bias peaks within the cores of topological vortices upon an increase of the applied magnetic field. The presence of magnetic impurities in FeTe(1−x)Sex, which are attracted to the vortices, would lead to such Zeeman-induced delocalization of Majorana modes in a fraction of vortices that capture a large enough number of magnetic impurities. Our results provide an explanation for the dichotomy between topological and nontopological vortices recently observed in FeTe(1−x)Sex. AU - Ghazaryan, Areg AU - Lopes, P. L.S. AU - Hosur, Pavan AU - Gilbert, Matthew J. AU - Ghaemi, Pouyan ID - 7428 IS - 2 JF - Physical Review B SN - 24699950 TI - Effect of Zeeman coupling on the Majorana vortex modes in iron-based topological superconductors VL - 101 ER - TY - JOUR AB - We demonstrate that releasing atoms into free space from an optical lattice does not deteriorate cavity-generated spin squeezing for metrological purposes. In this work, an ensemble of 500000 spin-squeezed atoms in a high-finesse optical cavity with near-uniform atom-cavity coupling is prepared, released into free space, recaptured in the cavity, and probed. Up to ∼10 dB of metrologically relevant squeezing is retrieved for 700μs free-fall times, and decaying levels of squeezing are realized for up to 3 ms free-fall times. The degradation of squeezing results from loss of atom-cavity coupling homogeneity between the initial squeezed state generation and final collective state readout. A theoretical model is developed to quantify this degradation and this model is experimentally validated. AU - Wu, Yunfan AU - Krishnakumar, Rajiv AU - Martínez-Rincón, Julián AU - Malia, Benjamin K. AU - Hosten, Onur AU - Kasevich, Mark A. ID - 8319 IS - 1 JF - Physical Review A SN - 24699926 TI - Retrieval of cavity-generated atomic spin squeezing after free-space release VL - 102 ER - TY - JOUR AB - The “procedural” approach to animating ocean waves is the dominant algorithm for animating larger bodies of water in interactive applications as well as in off-line productions — it provides high visual quality with a low computational demand. In this paper, we widen the applicability of procedural water wave animation with an extension that guarantees the satisfaction of boundary conditions imposed by terrain while still approximating physical wave behavior. In combination with a particle system that models wave breaking, foam, and spray, this allows us to naturally model waves interacting with beaches and rocks. Our system is able to animate waves at large scales at interactive frame rates on a commodity PC. AU - Jeschke, Stefan AU - Hafner, Christian AU - Chentanez, Nuttapong AU - Macklin, Miles AU - Müller-Fischer, Matthias AU - Wojtan, Christopher J ID - 8766 IS - 8 JF - Computer Graphics forum TI - Making procedural water waves boundary-aware VL - 39 ER - TY - JOUR AB - Markov decision processes (MDPs) are the defacto framework for sequential decision making in the presence of stochastic uncertainty. A classical optimization criterion for MDPs is to maximize the expected discounted-sum payoff, which ignores low probability catastrophic events with highly negative impact on the system. On the other hand, risk-averse policies require the probability of undesirable events to be below a given threshold, but they do not account for optimization of the expected payoff. We consider MDPs with discounted-sum payoff with failure states which represent catastrophic outcomes. The objective of risk-constrained planning is to maximize the expected discounted-sum payoff among risk-averse policies that ensure the probability to encounter a failure state is below a desired threshold. Our main contribution is an efficient risk-constrained planning algorithm that combines UCT-like search with a predictor learned through interaction with the MDP (in the style of AlphaZero) and with a risk-constrained action selection via linear programming. We demonstrate the effectiveness of our approach with experiments on classical MDPs from the literature, including benchmarks with an order of 106 states. AU - Brázdil, Tomáš AU - Chatterjee, Krishnendu AU - Novotný, Petr AU - Vahala, Jiří ID - 15055 IS - 06 JF - Proceedings of the 34th AAAI Conference on Artificial Intelligence KW - General Medicine SN - 2374-3468 TI - Reinforcement learning of risk-constrained policies in Markov decision processes VL - 34 ER -