Search

Cellular automata (CA) are simulation models that can produce complex emergent behaviors from simple local rules. Although state-of-the-art GPU solutions are already fast due to their data-parallel nature, their performance can rapidly degrade in CA with a large neighborhood radius. With the inclusion of tensor cores across the entire GPU ecosystem, interest has grown in finding ways to leverage these fast units outside the field of artificial intelligence, which was their original purpose. In this work, we present CAT, a GPU tensor core approach that can accelerate CA in which the cell transition function acts on a weighted summation of its neighborhood. CAT is evaluated theoretically, using an extended PRAM cost model, as well as empirically using the Larger Than Life (LTL) family of CA as case studies. The results confirm that the cost model is accurate, showing that CAT exhibits constant time throughout the entire radius range $1 \le r \le 16$, and its theoretical speedups agree with the empirical results. At low radius $r=1,2$, CAT is competitive and is only surpassed by the fastest state-of-the-art GPU solution. Starting from $r=3$, CAT progressively outperforms all other approaches, reaching speedups of up to $101\times$ over a GPU baseline and up to $\sim 14\times$ over the fastest state-of-the-art GPU approach. In terms of energy efficiency, CAT is competitive in the range $1 \le r \le 4$ and from $r \ge 5$ it is the most energy efficient approach. As for performance scaling across GPU architectures, CAT shows a promising trend that if continues for future generations, it would increase its performance at a higher rate than classical GPU solutions. The results obtained in this work put CAT as an attractive GPU approach for scientists that need to study emerging phenomena on CA with large neighborhood radius., Comment: 15 pages

During the last decade GPU technology has shifted from pure general purpose computation to the inclusion of application specific integrated circuits (ASICs), such as Tensor Cores and Ray Tracing (RT) cores. Although these special purpose GPU cores were designed to further accelerate specific fields such as AI and real-time rendering, recent research has managed to exploit them to further accelerate other tasks that typically used regular GPU computing. In this work we present RTXRMQ, a new approach that can compute range minimum queries (RMQs) with RT cores. The main contribution is the proposal of a geometric solution for RMQ, where elements become triangles that are placed and shaped according to the element's value and position in the array, respectively, such that the closest hit of a ray launched from a point given by the query parameters corresponds to the result of that query. Experimental results show that RTXRMQ is currently best suited for small query ranges relative to the problem size, achieving up to $5\times$ and $2.3\times$ of speedup over state of the art CPU (HRMQ) and GPU (LCA) approaches, respectively. Although for medium and large query ranges RTXRMQ is currently surpassed by LCA, it is still competitive by being $2.5\times$ and $4\times$ faster than HRMQ which is a highly parallel CPU approach. Furthermore, performance scaling experiments across the latest RTX GPU architectures show that if the current RT scaling trend continues, then RTXRMQ's performance would scale at a higher rate than HRMQ and LCA, making the approach even more relevant for future high performance applications that employ batches of RMQs., Comment: 17 Figures

The Convex Hull algorithm is one of the most important algorithms in computational geometry, with many applications such as in computer graphics, robotics, and data mining. Despite the advances in the new algorithms in this area, it is often needed to improve the performance to solve more significant problems quickly or in real-time processing. This work presents an experimental evaluation of GPU filters to reduce the cost of computing the 2D convex hull. The technique first performs a preprocessing of the input set, filtering all points within an eight-vertex polygon in logarithmic time, to obtain a reduced set of candidate points. We use parallel computation and the use of the Manhattan distance as a metric to find the vertices of the polygon and perform the point filtering. For the filtering stage we study different approaches; from custom CUDA kernels to libraries such as Thrust and CUB. Three types of point distributions are tested: a normal distribution (favorable case), circumference (the worst case), and a case where points are shifted randomly from the circumference (intermediate case). Experimental evaluation shows that the GPU filtering algorithm can be up to 23x faster than a sequential CPU implementation, and the whole convex hull computation can be up to 30x faster than the fastest implementation provided by the CGAL library.

The gas-phase reaction networks are the backbone of astrochemical models. However, due to their complexity and non-linear impact on the astrochemical modeling, they can be the first source of error in the simulations if incorrect reactions are present. Over time, following the increasing number of species detected, astrochemists have added new reactions, based on laboratory experiments and quantum mechanics (QM) computations as well as reactions inferred by chemical intuition and similarity principle. However, sometimes no verification of their feasibility in the interstellar conditions, namely their exothermicity, was performed. In this work, we present a new gas-phase reaction network, GRETOBAPE, based on the KIDA2014 network and updated with several reactions, cleaned from endothermic reactions not explicitly recognized as such. To this end, we characterized all the species in the GRETOBAPE network with accurate QM calculations. We found that 5% of the reactions in the original network are endothermic although most of them are reported as barrierless. The reaction network of Si-bearing species is the most impacted by the endothermicity cleaning process. We also produced a cleaned reduced network, GRETOBAPE-red, to be used to simulate astrochemical situations where only C-, O-, N- and S- bearing species with less than 6 atoms are needed. Finally, the new GRETOBAPE network, its reduced version, as well as the database with all the molecular properties are made publicly available. The species properties database can be used in the future to test the feasibility of possibly new reactions., Comment: ApJS submitted

Digital technologies can augment civic participation by facilitating the expression of detailed political preferences. Yet, digital participation efforts often rely on methods optimized for elections involving a few candidates. Here we present data collected in an online experiment where participants built personalized government programs by combining policies proposed by the candidates of the 2022 French and Brazilian presidential elections. We use this data to explore aggregates complementing those used in social choice theory, finding that a metric of divisiveness, which is uncorrelated with traditional aggregation functions, can identify polarizing proposals. These metrics provide a score for the divisiveness of each proposal that can be estimated in the absence of data on the demographic characteristics of participants and that explains the issues that divide a population. These findings suggest divisiveness metrics can be useful complements to traditional aggregation functions in direct forms of digital participation., Comment: 29 pages main manuscript with 5 figures. 55 pages of supplementary material

The convex hull is a fundamental geometrical structure for many applications where groups of points must be enclosed or represented by a convex polygon. Although efficient sequential convex hull algorithms exist, and are constantly being used in applications, their computation time is often considered an issue for time-sensitive tasks such as real-time collision detection, clustering or image processing for virtual reality, among others, where fast response times are required. In this work we propose a parallel GPU-based adaptation of heaphull, which is a state of the art CPU algorithm that computes the convex hull by first doing a efficient filtering stage followed by the actual convex hull computation. More specifically, this work parallelizes the filtering stage, adapting it to the GPU programming model as a series of parallel reductions. Experimental evaluation shows that the proposed implementation significantly improves the performance of the convex hull computation, reaching up to $4\times$ of speedup over the sequential CPU-based heaphull and between $3\times \sim 4\times$ over existing GPU based approaches., Comment: 7 pages, in Spanish language

We present a dynamically Growable GPU array (GGArray) fully implemented in GPU that does not require synchronization with the host. The idea is to improve the programming of GPU applications that require dynamic memory, by offering a structure that does not require pre-allocating GPU VRAM for the worst case scenario. The GGArray is based on the LFVector, by utilizing an array of them in order to take advantage of the GPU architecture and the synchronization offered by thread blocks. This structure is compared to other state of the art ones such as a pre-allocated static array and a semi-static array that needs to be resized through communication with the host. Experimental evaluation shows that the GGArray has a competitive insertion and resize performance, but it is slower for regular parallel memory accesses. Given the results, the GGArray is a potentially useful structure for applications with high uncertainty on the memory usage as well as applications that have phases, such as an insertion phase followed by a regular GPU phase. In such cases, the GGArray can be used for the first phase and then data can be flattened for the second phase in order to allow the classical GPU memory accesses which are faster. These results constitute a step towards achieving a parallel efficient C++ like vector for modern GPU architectures., Comment: 8 pages

A common approach to model complex chemistry in numerical simulations is via post-processing of existing magneto-hydrodynamic simulations, relying on computing the evolution of chemistry over the dynamic history of a subset of particles from within the raw simulation. Here, we validate such a technique, assessing its ability to recover the abundances of chemical species, using the chemistry package KROME. We also assess, for the first time, the importance of the main free input parameters, by means of a direct comparison with a self-consistent state-of-the-art simulation in which chemistry was directly coupled to hydrodynamics. We have found that the post-processing is highly reliable, with an accuracy at the percent level, even when the most relaxed input parameters are employed. In particular, our results show that the number of particles used does not affect significantly the average properties, although it suppresses the appearance of possibly important spatial features. On the other hand, the choice of the integration time-step plays a crucial role. Longer integration time-steps can produce large errors, as the post-processing solution will be forced towards chemical equilibrium, a condition that does not always necessarily apply. When the interpolation-based reconstruction of chemical properties is performed, the errors further increase up to a factor of $\sim2$. Concluding, our results suggest that this technique is extremely useful when exploring the relative quantitative effect of different chemical parameters and/or networks, without the need of re-running simulations multiple times, but some care should be taken in the choice of particles sub-sample and integration time-step., Comment: 11 pages, 6 figures, 3 tables

One of the grand challenges discussed during the Dagstuhl Seminar "Knowledge Graphs: New Directions for Knowledge Representation on the Semantic Web" and described in its report is that of a: "Public FAIR Knowledge Graph of Everything: We increasingly see the creation of knowledge graphs that capture information about the entirety of a class of entities. [...] This grand challenge extends this further by asking if we can create a knowledge graph of "everything" ranging from common sense concepts to location based entities. This knowledge graph should be "open to the public" in a FAIR manner democratizing this mass amount of knowledge." Although linked open data (LOD) is one knowledge graph, it is the closest realisation (and probably the only one) to a public FAIR Knowledge Graph (KG) of everything. Surely, LOD provides a unique testbed for experimenting and evaluating research hypotheses on open and FAIR KG. One of the most neglected FAIR issues about KGs is their ongoing evolution and long term preservation. We want to investigate this problem, that is to understand what preserving and supporting the evolution of KGs means and how these problems can be addressed. Clearly, the problem can be approached from different perspectives and may require the development of different approaches, including new theories, ontologies, metrics, strategies, procedures, etc. This document reports a collaborative effort performed by 9 teams of students, each guided by a senior researcher as their mentor, attending the International Semantic Web Research School (ISWS 2019). Each team provides a different perspective to the problem of knowledge graph evolution substantiated by a set of research questions as the main subject of their investigation. In addition, they provide their working definition for KG preservation and evolution.

Cosmic rays are a global source of ionisation, and the ionisation fraction represents a fundamental parameter in the interstellar medium. Ions couple to magnetic fields, affect the chemistry, and the dynamics of star-forming regions as well as planetary atmospheres. However, the cosmic-ray ionisation rate represents one of the bottlenecks for astrochemical models, and its determination is one of the most puzzling problems in astrophysics. While for diffuse clouds reasonable values have been provided from H$_3^+$ observations, for dense clouds, due to the lack of rotational transitions, this is not possible, and estimates are strongly biased by the employed model. We present here an analytical expression, obtained from first principles, to estimate the cosmic-ray ionisation rate from observational quantities. The theoretical predictions are validated with high-resolution three-dimensional numerical simulations and applied to the well known core L1544; we obtained an estimate of $\zeta_2 \sim 2-3 \times 10^{-17}$ s$^{-1}$. Our results and the analytical formulae provided represent the first model-independent, robust tool to probe the cosmic-ray ionisation rate in the densest part of star-forming regions (on spatial scales of $R \leq 0.05$ pc). An error analysis is presented to give statistical relevance to our study., Comment: Accepted on MNRAS Letters

A pre-Schwarzian and a Schwarzian derivative for locally univalent pluriharmonic mappings in ${\mathbb C}^n$ are introduced. Basic properties such as the chain rule, multiplicative invariance and affine invariance are proved for these operators. It is shown that the pre-Schwarzian is stable only with respect to rotations of the identity. A characterization is given for the case when the pre-Schwarzian derivative is holomorphic. Furthermore, it is shown that if the Schwarzian derivative of a pluriharmonic mapping vanishes then the analytic part of this mapping is a M\"obius transformation. Some observations are made related to the dilatation of pluriharmonic mappings and to the dilatation of their affine transformations, revealing differences between the theories in the plane and in higher dimensions. An example is given that rules out the possibility for a shear construction theorem to hold in ${\mathbb C}^n$, for $n\geq2$., Comment: 24 pages; to appear in Journal of Mathematical Analysis and Applications

Disentangling the different stages of the star-formation process, in particular in the high-mass regime, is a challenge in astrophysics. Chemical clocks could help alleviating this problem, but their evolution strongly depends on many parameters, leading to degeneracy in the interpretation of the observational data. One of these uncertainties is the degree of CO depletion. We present here the first self-consistent magneto-hydrodynamic simulations of high-mass star-forming regions at different scales, fully coupled with a non-equilibrium chemical network, which includes C-N-O bearing molecules. Depletion and desorption processes are treated time-dependently. The results show that full CO-depletion (i.e. all gas-phase CO frozen-out on the surface of dust grains), can be reached very quickly, in one third or even smaller fractions of the free-fall time, whether the collapse proceeds on slow or fast timescales. This leads to a high level of deuteration in a short time both for typical tracers like N$_2$H$^+$, as well as for the main ion H$_3^+$, the latter being in general larger and more extended. N$_2$ depletion is slightly less efficient, and no direct effects on N-bearing molecules and deuterium fractionation are observed. We show that CO depletion is not the only driver of deuteration, and that there is a strong impact on $D_{frac}$ when changing the grain-size. We finally apply a two-dimensional gaussian Point Spread Function to our results to mimic observations with single-dish and interferometers. Our findings suggest that the low-values observed in high-mass star-forming clumps are in reality masking a full-depletion stage in the inner 0.1 pc region., Comment: accepted on ApJ

Young massive stars are usually found embedded in dense and massive molecular clumps and are known for being highly obscured and distant. During their formation process, deuteration is regarded as a potentially good indicator of the formation stage. Therefore, proper observations of such deuterated molecules are crucial, but still, hard to perform. In this work, we test the observability of the transition o-H$_2$D$^+(1_{10}$-$1_{11})$, using a synthetic source, to understand how the physical characteristics are reflected in observations through interferometers and single-dish telescopes. In order to perform such tests, we post-processed a magneto-hydrodynamic simulation of a collapsing magnetized core using the radiative transfer code POLARIS. Using the resulting intensity distributions as input, we performed single-dish (APEX) and interferometric (ALMA) synthetic observations at different evolutionary times, always mimicking realistic configurations. Finally, column densities were derived to compare our simulations with real observations previously performed. Our derivations for o-H$_2$D$^+$ are in agreement with values reported in the literature, in the range of 10$^{\!10-11}$cm$^{\!-2}$ and 10$^{\!12-13}$cm$^{\!-2}$ for single-dish and interferometric measurements, respectively., Comment: 3 pages, 3 figures, To appear in the proceedings of the Second Binational Meeting AAA-SOCHIAS 2018

We observe a property of orthogonality of the Mellin-Barnes transformation of the triangle one-loop diagrams, which follows from our previous papers [JHEP {\bf 0808} (2008) 106, JHEP {\bf 1003} (2010) 051, JMP {\bf 51} (2010) 052304]. In those papers it has been established that Usyukina-Davydychev functions are invariant with respect to Fourier transformation. This has been proved at the level of graphs and also via the Mellin-Barnes transformation. We partially apply to one-loop massless scalar diagram the same trick in which the Mellin-Barnes transformation was involved and obtain the property of orthogonality of the corresponding MB transforms under integration over contours in two complex planes with certain weight. This property is valid in an arbitrary number of dimensions., Comment: 12 pages, 2 figures

We consider a simple model for QCD dynamics in which DGLAP integro-differential equation may be solved analytically. This is a gauge model which possesses dominant evolution of gauge boson (gluon) distribution and in which the gauge coupling does not run. This may be ${\cal N} =4$ supersymmetric gauge theory with softly broken supersymmetry, other finite supersymmetric gauge theory with lower level of supersymmetry, or topological Chern-Simons field theories. We maintain only one term in the splitting function of unintegrated gluon distribution and solve DGLAP analytically for this simplified splitting function. The solution is found by use of the Cauchy integral formula. The solution restricts form of the unintegrated gluon distribution as function of momentum transfer and of Bjorken $x$. Then we consider an almost realistic splitting function of unintegrated gluon distribution as an input to DGLAP equation and solve it by the same method which we have developed to solve DGLAP equation for the toy-model. We study a result obtained for the realistic gluon distribution and find a singular Bessel-like behaviour in the vicinity of the point $x=0$ and a smooth behaviour in the vicinity of the point, Comment: 32 pages

In this paper we proceed to study properties of Mellin-Barnes (MB) transforms of Usyukina-Davydychev (UD) functions. In our previous papers [Nuclear Physics B 870 (2013) 243], [Nuclear Physics B 876 (2013) 322] we showed that multi-fold Mellin-Barnes (MB) transforms of Usyukina-Davydychev (UD) functions may be reduced to two-fold MB transforms and that the higher-order UD functions were obtained in terms of a differential operator by applying it to a slightly modified first UD function. The result is valid in $d=4$ dimensions and its analog in $d=4-2\varepsilon$ dimensions exits too [Theoretical and Mathematical Physics 177 (2013) 1515]. In [Nuclear Physics B 870 (2013) 243] the chain of recurrent relations for analytically regularized UD functions was obtained implicitly by comparing the left hand side and the right hand side of the diagrammatic relations between the diagrams with different loop orders. In turn, these diagrammatic relations were obtained due to the method of loop reduction for the triangle ladder diagrams proposed in 1983 by Belokurov and Usyukina. Here we reproduce these recurrent relations by calculating explicitly via Barnes lemmas the contour integrals produced by the left hand sides of the diagrammatic relations. In such a way we explicitly calculate a family of multi-fold contour integrals of certain ratios of Euler gamma functions. We make a conjecture that similar results for the contour integrals are valid for a wider family of smooth functions which includes the MB transforms of UD functions., Comment: 7 pages, 1 figure, minor changes in the text; accepted for publication in Nuclear Physics B

We present a family of sense-preserving harmonic mappings in the unit disk related to the classical generalized (analytic) Koebe functions. We prove that these are precisely the mappings that maximize simultaneously the real part of every Taylor coefficient as well as the growth and distortion of functions in affine and linear invariant families of complex-valued harmonic functions.

With current hardware and software, a standard computer can now hold in RAM an index for approximate pattern matching on about half a dozen human genomes. Sequencing technologies have improved so quickly, however, that scientists will soon demand indexes for thousands of genomes. Whereas most researchers who have addressed this problem have proposed completely new kinds of indexes, we recently described a simple technique that scales standard indexes to work on more genomes. Our main idea was to filter the dataset with LZ77, build a standard index for the filtered file, and then create a hybrid of that standard index and an LZ77-based index. In this paper we describe how to our technique to use alignments instead of LZ77, in order to simplify and speed up both preprocessing and random access.

Advances in DNA sequencing mean databases of thousands of human genomes will soon be commonplace. In this paper we introduce a simple technique for reducing the size of conventional indexes on such highly repetitive texts. Given upper bounds on pattern lengths and edit distances, we preprocess the text with LZ77 to obtain a filtered text, for which we store a conventional index. Later, given a query, we find all matches in the filtered text, then use their positions and the structure of the LZ77 parse to find all matches in the original text. Our experiments show this also significantly reduces query times.

In our previous paper [Nucl.Phys. B 870 (2013) 243], we showed that multi-fold Mellin-Barnes (MB) transforms of Usyukina-Davydychev (UD) functions may be reduced to two-fold MB transforms. The MB transforms were written there as polynomials of logarithms of ratios of squares of the external momenta with certain coefficients. We also showed that these coefficients have a combinatoric origin. In this paper, we present an explicit formula for these coefficients. The procedure of recovering the coefficients is based on taking the double-uniform limit in certain series of smooth functions of two variables which is constructed according to a pre-determined iterative way. The result is obtained by using basic methods of mathematical analysis. We observe that the finiteness of the limit of this iterative chain of smooth functions should reflect itself in other mathematical constructions, too, since it is not related in any way to the explicit form of the MB transforms. This finite double-uniform limit is represented in terms of a differential operator with respect to an auxiliary parameter which acts on the integrand of a certain two-fold MB integral. To demonstrate that our result is compatible with original representations of UD functions, we reproduce the integrands of these original integral representations by applying this differential operator to the integrand of the simple integral representation of the scalar triangle four-dimensional integral J(1,1,1-e)., Comment: 12 pages; section added elaborating the connection with arXiv:1303.6909, 8 references added, minor changes in the text; accepted for publication in Nucl. Phys. B