Writing concurrent code that is both correct and efficient is notoriously difficult. Thus, programmers often prefer to use synchronization abstractions, which render code simpler and easier to reason about. Despite a wealth of work on this topic, there is still a gap between the rich semantics provided by synchronization abstractions in modern programming languages -- specifically, \emph{fair} FIFO ordering of synchronization requests and support for \emph{abortable} operations -- and frameworks for implementing it correctly and efficiently. Supporting such semantics is critical given the rising popularity of constructs for asynchronous programming, such as coroutines, which abort frequently and are cheaper to suspend and resume compared to native threads. This paper introduces a new framework called \texttt{CancellableQueueSynchronizer} (CQS), which enables simple yet efficient implementations of a wide range of fair and abortable synchronization primitives: mutexes, semaphores, barriers, count-down latches, and blocking pools. Our main contribution is algorithmic, as implementing both fairness and abortability efficiently at this level of generality is non-trivial. Importantly, all our algorithms, including the CQS framework and the primitives built on top of it, come with \emph{formal proofs} in the Iris framework for Coq for many of their properties. These proofs are modular, so it is easy to show correctness for new primitives implemented on top of CQS. From a practical perspective, implementation of CQS for native threads on the JVM significantly improves Java's \texttt{AbstractQueuedSynchronizer}, the only practical abstraction offering similar semantics. In sum, \texttt{CancellableQueueSynchronizer} is the first framework to combine expressiveness with formal guarantees and solid practical performance.
相關內容
-- A theoretical framework that subsumes conventional deterministic spiking neural networks and surrogate gradients, facilitating more efficient and effective employment of various neuromorphic hardware developments in real-world applications. -- Scalable spiking neural models that incorporate noisy neuronal dynamics for implicit regularization, improved robustness, and computational accounts of biological neural computation, revealing that unreliable neural substrates yield reliable computation and learning. Networks of spiking neurons underpin the extraordinary information-processing capabilities of the brain and have emerged as pillar models in neuromorphic intelligence. Despite extensive research on spiking neural networks (SNNs), most are established on deterministic models. Integrating noise into SNNs leads to biophysically more realistic neural dynamics and may benefit model performance. This work presents the noisy spiking neural network (NSNN) and the noise-driven learning rule (NDL) by introducing a spiking neuron model incorporating noisy neuronal dynamics. Our approach shows how noise may serve as a resource for computation and learning and theoretically provides a framework for general SNNs. We show that our method exhibits competitive performance and improved robustness against challenging perturbations than deterministic SNNs and better reproduces probabilistic neural computation in neural coding. This study offers a powerful and easy-to-use tool for machine learning, neuromorphic intelligence practitioners, and computational neuroscience researchers.
We propose a physics informed, neural network-based elasto-viscoplasticity (NN-EVP) constitutive modeling framework for predicting the flow response in metals as a function of underlying grain size. The developed NN-EVP algorithm is based on input convex neural networks as a means to strictly enforce thermodynamic consistency, while allowing high expressivity towards model discovery from limited data. It utilizes state-of-the-art machine learning tools within PyTorch's high-performance library providing a flexible tool for data-driven, automated constitutive modeling. To test the performance of the framework, we generate synthetic stress-strain curves using a power law-based model with phenomenological hardening at small strains and test the trained model for strain amplitudes beyond the training data. Next, experimentally measured flow responses obtained from uniaxial deformations are used to train the framework under large plastic deformations. Ultimately, the Hall-Petch relationship corresponding to grain size strengthening is discovered by training flow response as a function of grain size, also leading to efficient extrapolation. The present work demonstrates a successful integration of neural networks into elasto-viscoplastic constitutive laws, providing a robust automated framework for constitutive model discovery that can efficiently generalize, while also providing insights into predictions of flow response and grain size-property relationships in metals and metallic alloys under large plastic deformations.
Cook and Reckhow 1979 pointed out that NP is not closed under complementation iff there is no propositional proof system that admits polynomial size proofs of all tautologies. Theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus at a conjecture from K.2004 in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (for p-time generators) without a reference to proof complexity notions as follows: * There exist a p-time function $g$ stretching each input by one bit such that its range intersects all infinite NP sets. We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and independence results), to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof systems and to complexity of proof search. We argue that a specific gadget generator from K.2009 is a good candidate for $g$. We define a new hardness property of generators, the $\bigvee$-hardness, and shows that one specific gadget generator is the $\bigvee$-hardest (w.r.t. any sufficiently strong proof system). We define the class of feasibly infinite NP sets and show, assuming a hypothesis from circuit complexity, that the conjecture holds for all feasibly infinite NP sets.
We develop in this work the first polytopal complexes of differential forms. These complexes, inspired by the Discrete De Rham and the Virtual Element approaches, are discrete versions of the de Rham complex of differential forms built on meshes made of general polytopal elements. Both constructions benefit from the high-level approach of polytopal methods, which leads, on certain meshes, to leaner constructions than the finite element method. We establish commutation properties between the interpolators and the discrete and continuous exterior derivatives, prove key polynomial consistency results for the complexes, and show that their cohomologies are isomorphic to the cohomology of the continuous de Rham complex.
Physics-informed neural networks (PINNs) are emerging as popular mesh-free solvers for partial differential equations (PDEs). Recent extensions decompose the domain, apply different PINNs to solve the problem in each subdomain, and stitch the subdomains at the interface. Thereby, they can further alleviate the problem complexity, reduce the computational cost, and allow parallelization. However, the performance of multi-domain PINNs is sensitive to the choice of the interface conditions. While quite a few conditions have been proposed, there is no suggestion about how to select the conditions according to specific problems. To address this gap, we propose META Learning of Interface Conditions (METALIC), a simple, efficient yet powerful approach to dynamically determine appropriate interface conditions for solving a family of parametric PDEs. Specifically, we develop two contextual multi-arm bandit (MAB) models. The first one applies to the entire training course, and online updates a Gaussian process (GP) reward that given the PDE parameters and interface conditions predicts the performance. We prove a sub-linear regret bound for both UCB and Thompson sampling, which in theory guarantees the effectiveness of our MAB. The second one partitions the training into two stages, one is the stochastic phase and the other deterministic phase; we update a GP reward for each phase to enable different condition selections at the two stages to further bolster the flexibility and performance. We have shown the advantage of METALIC on four bench-mark PDE families.
The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum $s$-$t$ cuts of an undirected weighted graph for all pairs of nodes $(s,t)$. We propose a new approach for computing the cut tree based on a reduction to the problem that we call OrderedCuts. Given a sequence of nodes $s,v_1,\ldots,v_\ell$, its goal is to compute minimum $\{s,v_1,\ldots,v_{i-1}\}$-$v_i$ cuts for all $i\in[\ell]$. We show that the cut tree can be computed by $\tilde O(1)$ calls to OrderedCuts. We also establish new results for OrderedCuts that may be of independent interest. First, we prove that all $\ell$ cuts can be stored compactly with $O(n)$ space in a data structure that we call an OC tree. We define a weaker version of this structure that we call depth-1 OC tree, and show that it is sufficient for constructing the cut tree. Second, we prove results that allow divide-and-conquer algorithms for computing OC tree. We argue that the existence of divide-and-conquer algorithms makes our new approach a good candidate for a practical implementation.
We discuss three SYCL realisations of a simple Finite Volume scheme over multiple Cartesian patches. The realisation flavours differ in the way how they map the compute steps onto loops and tasks: We compare an implementation which is exclusively using a cascade of for-loops to a version which uses nested parallelism, and finally benchmark these against a version which models the calculations as task graph. Our work proposes realisation idioms to realise these flavours within SYCL. The idioms translate to some degree to other GPGPU programming techniques, too. Our preliminary results suggest that SYCL's capability to model calculations via tasks or nested parallelism does not yet allow such realisations to outperform their counterparts using exclusively data parallelism.
Animating still face images with deep generative models using a speech input signal is an active research topic and has seen important recent progress. However, much of the effort has been put into lip syncing and rendering quality while the generation of natural head motion, let alone the audio-visual correlation between head motion and speech, has often been neglected. In this work, we propose a multi-scale audio-visual synchrony loss and a multi-scale autoregressive GAN to better handle short and long-term correlation between speech and the dynamics of the head and lips. In particular, we train a stack of syncer models on multimodal input pyramids and use these models as guidance in a multi-scale generator network to produce audio-aligned motion unfolding over diverse time scales. Our generator operates in the facial landmark domain, which is a standard low-dimensional head representation. The experiments show significant improvements over the state of the art in head motion dynamics quality and in multi-scale audio-visual synchrony both in the landmark domain and in the image domain.
This paper focuses on the expected difference in borrower's repayment when there is a change in the lender's credit decisions. Classical estimators overlook the confounding effects and hence the estimation error can be magnificent. As such, we propose another approach to construct the estimators such that the error can be greatly reduced. The proposed estimators are shown to be unbiased, consistent, and robust through a combination of theoretical analysis and numerical testing. Moreover, we compare the power of estimating the causal quantities between the classical estimators and the proposed estimators. The comparison is tested across a wide range of models, including linear regression models, tree-based models, and neural network-based models, under different simulated datasets that exhibit different levels of causality, different degrees of nonlinearity, and different distributional properties. Most importantly, we apply our approaches to a large observational dataset provided by a global technology firm that operates in both the e-commerce and the lending business. We find that the relative reduction of estimation error is strikingly substantial if the causal effects are accounted for correctly.
The goal of few-shot learning is to learn a classifier that generalizes well even when trained with a limited number of training instances per class. The recently introduced meta-learning approaches tackle this problem by learning a generic classifier across a large number of multiclass classification tasks and generalizing the model to a new task. Yet, even with such meta-learning, the low-data problem in the novel classification task still remains. In this paper, we propose Transductive Propagation Network (TPN), a novel meta-learning framework for transductive inference that classifies the entire test set at once to alleviate the low-data problem. Specifically, we propose to learn to propagate labels from labeled instances to unlabeled test instances, by learning a graph construction module that exploits the manifold structure in the data. TPN jointly learns both the parameters of feature embedding and the graph construction in an end-to-end manner. We validate TPN on multiple benchmark datasets, on which it largely outperforms existing few-shot learning approaches and achieves the state-of-the-art results.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191