Search

The unpreconditioned H‐TFETI‐DP (hybrid total finite element tearing and interconnecting dual‐primal) domain decomposition method introduced by Klawonn and Rheinbach turned out to be an effective solver for variational inequalities discretized by huge structured grids. The basic idea is to decompose the domain into non‐overlapping subdomains, interconnect some adjacent subdomains into clusters on a primal level, and enforce the continuity of the solution across both the subdomain and cluster interfaces by Lagrange multipliers. After eliminating the primal variables, we get a reasonably conditioned quadratic programming (QP) problem with bound and equality constraints. Here, we first reduce the continuous problem to the subdomains' boundaries, then discretize it using the boundary element method, and finally interconnect the subdomains by the averages of adjacent edges. The resulting QP problem in multipliers with a small coarse grid is solved by specialized QP algorithms with optimal complexity. The method can be considered as a three‐level multigrid with the coarse grids split between primal and dual variables. Numerical experiments illustrate the efficiency of the presented H‐TBETI‐DP (hybrid total boundary element tearing and interconnecting dual‐primal) method and nice spectral properties of the discretized Steklov–Poincaré operators as compared with their finite element counterparts. [ABSTRACT FROM AUTHOR]

Terrain analysis plays an important role in computer graphics, hydrology and geomorphology. In particular, analyzing the path of material flow over a terrain with consideration of local depressions is a precursor to many further tasks in erosion, river formation, and plant ecosystem simulation. For example, fluvial erosion simulation used in terrain modeling computes water discharge to repeatedly locate erosion channels for soil removal and transport. Despite its significance, traditional methods face performance constraints, limiting their broader applicability. In this paper, we propose a novel GPU flow routing algorithm that computes the water discharge in 풪(log n) iterations for a terrain with n vertices (assuming n processors). We also provide a depression routing algorithm to route the water out of local minima formed by depressions in the terrain, which converges in 풪(log2 n) iterations. Our implementation of these algorithms leads to a 5× speedup for flow routing and 34 × to 52 × speedup for depression routing compared to previous work on a 10242 terrain, enabling interactive control of terrain simulation. [ABSTRACT FROM AUTHOR]

A well-known clustering problem called Density-Based Spatial Clustering of Applications with Noise~(DBSCAN) involves computing the solutions of at least one disk range query per input point, computing the connected components of a graph, and bichromatic fixed-radius nearest neighbor. MapReduce class is a model where a sublinear number of machines, each with sublinear memory, run for a polylogarithmic number of parallel rounds. Most of these problems either require quadratic time in the sequential model or are hard to compute in a constant number of rounds in MapReduce. In the Euclidean plane, DBSCAN algorithms with near-linear time and a randomized parallel algorithm with a polylogarithmic number of rounds exist. We solve DBSCAN in the Euclidean plane in a constant number of rounds in MapReduce, assuming the minimum number of points in range queries is constant and each connected component fits inside the memory of a single machine and has a constant diameter.

Early awareness of inference performance ensures the feasibility of machine learning for embedded deployment. Often, ML model selection often focuses first on training performance and accuracy, with inference considered second. While prioritizing training is necessary, model inference performance is often impacted by these optimizations. Knowing whether a model will run meaningfully faster or be more energy efficient than its un-optimized-counterpart is required for resource-constrained embedded environments. Training-time optimizations may incur real performance losses at inference time. This paper benchmarks the effect of one such training optimization, clustered attention, and examines its effect on the inference performance of the transformer-based transcription model wav2vec2. The execution time and energy consumption of this model is evaluated on NVIDIA Jetson-embedded GPU devices. Clustered attention is specific to the transformer self-attention mechanism, which exhibits poor memory and execution-time scaling with respect to a variable input size. These scaling characteristics make it a potentially critical bottleneck that must be observed under realistic conditions. Our research considers three model variants: reference (original), clustered, and improved-clustered attention models. The reference model was faster for small input sizes, but the clustered model was faster for input sizes longer than 10 seconds. The clustered model had the lowest maximum energy per inference for input sizes greater than about 12 seconds of audio. With optimal configuration, the improved-clustered model takes 26.34% more time to execute than the reference model. With these operational differences, we show that inference performance and energy consumption of deployment should not be overlooked in selecting model optimizations.

We present edge‐friend, a data structure for quad meshes with access to neighborhood information required for Catmull‐Clark subdivision surface refinement. Edge‐friend enables efficient real‐time subdivision surface rendering. In particular, the resulting algorithm is deterministic, does not require hardware support for atomic floating‐point arithmetic, and is optimized for efficient rendering on GPUs. Edge‐friend exploits that after one subdivision step, two edges can be uniquely and implicitly assigned to each quad. Additionally, edge‐friend is a compact data structure, adding little overhead. Our algorithm is simple to implement in a single compute shader kernel, and requires minimal synchronization which makes it particularly suited for asynchronous execution. We easily extend our kernel to support relevant Catmull‐Clark subdivision surface features, including semi‐smooth creases, boundaries, animation and attribute interpolation. In case of topology changes, our data structure requires little preprocessing, making it amendable for a variety of applications, including real‐time editing and animations. Our method can process and render billions of triangles per second on modern GPUs. For a sample mesh, our algorithm generates and renders 2.9 million triangles in 0.58ms on an AMD Radeon RX 7900 XTX GPU. [ABSTRACT FROM AUTHOR]

We consider the problem of designing fundamental graph algorithms on the model of massively parallel computation (MPC). The input to the problem is an undirected graph G with n vertices and m edges and with D being the maximum diameter of any connected component in G. We consider the MPC with low local space, allowing each machine to store only \Theta (n\delta) words for an arbitrary constant \delta > 0 and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. [Parallel graph connectivity in log diameter rounds, 2018] and Behnezhad, Hajiaghayi, and Harris [Exponentially faster massively parallel maximal matching, 2019] designed parallel randomized algorithms that in O(logD+log log n) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O(log n) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: We present a deterministic MPC low local space algorithm that in O(logD+log log n) rounds determines connected components of the input graph. Our result matches the complexity of state-of-the-art randomized algorithms for this task. We complement our upper bounds by extending a recent lower bound for the connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D \geq log1+\Omega (1) n) by showing a related conditional hardness of \Omega (logD) MPC rounds for the entire spectrum of D, covering a particularly interesting range when D \leq O(log n). [ABSTRACT FROM AUTHOR]

Volume data these days is usually massive in terms of its topology, multiple fields, or temporal component. With the gap between compute and memory performance widening, the memory subsystem becomes the primary bottleneck for scientific volume visualization. Simple, structured, regular representations are often infeasible because the buses and interconnects involved need to accommodate the data required for interactive rendering. In this state‐of‐the‐art report, we review works focusing on large‐scale volume rendering beyond those typical structured and regular grid representations. We focus primarily on hierarchical and adaptive mesh refinement representations, unstructured meshes, and compressed representations that gained recent popularity. We review works that approach this kind of data using strategies such as out‐of‐core rendering, massive parallelism, and other strategies to cope with the sheer size of the ever‐increasing volume of data produced by today's supercomputers and acquisition devices. We emphasize the data management side of large‐scale volume rendering systems and also include a review of tools that support the various volume data types discussed. [ABSTRACT FROM AUTHOR]

The humble loop shrinking property played a central role in the inception of modern topology but it has been eclipsed by more abstract algebraic formalisms. This is particularly true in the context of detecting relevant non‐contractible loops on surfaces where elaborate homological and/or graph theoretical constructs are favored in algorithmic solutions. In this work, we devise a variational analogy to the loop shrinking property and show that it yields a simple, intuitive, yet powerful solution allowing a streamlined treatment of the problem of handle and tunnel loop detection. Our formalization tracks the evolution of a diffusion front randomly initiated on a single location on the surface. Capitalizing on a diffuse interface representation combined with a set of rules for concurrent front interactions, we develop a dynamic data structure for tracking the evolution on the surface encoded as a sparse matrix which serves for performing both diffusion numerics and loop detection and acts as the workhorse of our fully parallel implementation. The substantiated results suggest our approach outperforms state of the art and robustly copes with highly detailed geometric models. As a byproduct, our approach can be used to construct Reeb graphs by diffusion thus avoiding commonly encountered issues when using Morse functions. [ABSTRACT FROM AUTHOR]

The unpreconditioned hybrid domain decomposition method was recently shown to be a competitive solver for linear elliptic PDE problems discretized by structured grids. Here, we plug H-TFETI-DP (hybrid total finite element tearing and interconnecting dual primal) method into the solution of huge boundary elliptic variational inequalities. We decompose the domain into subdomains that are discretized and then interconnected partly by Lagrange multipliers and partly by edge averages. After eliminating the primal variables, we get a quadratic programming problem with a well-conditioned Hessian and bound and equality constraints that is effectively solvable by specialized algorithms. We prove that the procedure enjoys optimal, i.e., asymptotically linear complexity. The analysis uses recently established bounds on the spectrum of the Schur complements of the clusters interconnected by edge/face averages. The results extend the scope of scalability of massively parallel algorithms for the solution of variational inequalities and show the outstanding efficiency of the H-TFETI-DP coarse grid split between the primal and dual variables. [ABSTRACT FROM AUTHOR]

Hyperspectral data are being increasingly used for the characterization and understanding of real-world scenarios. In this field, UAV-based sensors bring the opportunity to collect multiple samples from different viewpoints. Thus, light-material interactions of real objects may be observed in outdoor scenarios with a significant spatial resolution (5 cm/pixel). Nevertheless, the generation of hyperspectral 3D data still poses challenges in post-processing due to the high geometric deformation of images. Most of the current solutions use both LiDAR (Light Detection and Ranging) and hyperspectral sensors, which are integrated into the same acquisition system. However, these present several limitations due to errors derived from inertial measurements for data fusion and the spatial resolution according to the LiDAR capabilities. In this work, a method is proposed for the generation of hyperspectral point clouds. Input data are formed by push-broom hyperspectral images and 3D point clouds. On the one hand, the point clouds may be obtained by applying a typical photogrammetric workflow or LiDAR technology. Then, hyperspectral images are geometrically corrected and aligned with the RGB orthomosaic. Accordingly, hyperspectral data are ready to be mapped on the 3D point cloud. This procedure is implemented on the GPU by testing which points are visible for each pixel of the hyperspectral imagery. This work also provides a novel solution to generate, compress and render 3D hyperspectral point clouds, enabling the study of geometry and the hyperspectral response of natural and artificial materials in the real world. [Display omitted] • Generation of hyperspectral point clouds with data from push-broom sensors. • Compression of hyperspectral point clouds using an stack-based representation. • Mapping of hyperspectral data in high-resolution point clouds. • Acceleration of the complete pipeline using GPGPU programming. • Accelerated rendering of compressed hyperspectral layers using compute shaders. [ABSTRACT FROM AUTHOR]

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU’s global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X). [ABSTRACT FROM AUTHOR]

Ray tracing is an inherent part of photorealistic image synthesis algorithms. The problem of ray tracing is to find the nearest intersection with a given ray and scene. Although this geometric operation is relatively simple, in practice, we have to evaluate billions of such operations as the scene consists of millions of primitives, and the image synthesis algorithms require a high number of samples to provide a plausible result. Thus, scene primitives are commonly arranged in spatial data structures to accelerate the search. In the last two decades, the bounding volume hierarchy (BVH) has become the de facto standard acceleration data structure for ray tracing‐based rendering algorithms in offline and recently also in real‐time applications. In this report, we review the basic principles of bounding volume hierarchies as well as advanced state of the art methods with a focus on the construction and traversal. Furthermore, we discuss industrial frameworks, specialized hardware architectures, other applications of bounding volume hierarchies, best practices, and related open problems. [ABSTRACT FROM AUTHOR]

In situ visualization is a technique in which plots and other visual analyses are performed in tandem with numerical simulation processes in order to better utilize HPC machine resources. Especially with unattended exploratory engineering simulation analyses, events may occur during the run, which justify supplemental processing. Sometimes though, when the events do occur, the phenomena of interest includes the physics that precipitated the events and this may be the key insight into understanding the phenomena that is being simulated. In situ temporal caching is the temporary storing of produced data in memory for possible later analysis including time varying visualization. The later analysis and visualization still occurs during the simulation run but not until after the significant events have been detected. In this article, we demonstrate how temporal caching can be used with in-line in situ visualization to reduce simulation run-time while still capturing essential simulation results. [ABSTRACT FROM AUTHOR]

Subdivision surfaces have become an invaluable asset in production environments. While progress over the last years has allowed the use of graphics hardware to meet performance demands during animation and rendering, high‐performance is limited to immutable mesh connectivity scenarios. Motivated by recent progress in mesh data structures, we show how the complete Catmull‐Clark subdivision scheme can be abstracted in the language of linear algebra. While this high‐level formulation allows for a fully parallel implementation with significant performance gains, the underlying algebraic operations require further specialization for modern parallel hardware. Integrating domain knowledge about the mesh matrix data structure, we replace costly general linear algebra operations like matrix‐matrix multiplication by specialized kernels. By further considering innate properties of Catmull‐Clark subdivision, like the quad‐only structure after refinement, we achieve an additional order of magnitude in performance and significantly reduce memory footprints. Our approach can be adapted seamlessly for different use cases, such as regular subdivision of dynamic meshes, fast evaluation for immutable topology and feature‐adaptive subdivision for efficient rendering of animated models. In this way, patchwork solutions are avoided in favor of a streamlined solution with consistent performance gains throughout the production pipeline. The versatility of the sparse matrix linear algebra abstraction underlying our work is further demonstrated by extension to other schemes such as and Loop subdivision. [ABSTRACT FROM AUTHOR]

We present a scalable solution to render complex scenes from a large amount of viewpoints. While previous approaches rely either on a scene or a view hierarchy to process multiple elements together, we make full use of both, enabling sublinear performance in terms of views and scene complexity. By concurrently traversing the hierarchies, we efficiently find shared information among views to amortize rendering costs. One example application is many‐light global illumination. Our solution accelerates shadow map generation for virtual point lights, whose number can now be raised to over a million while maintaining interactive rates. [ABSTRACT FROM AUTHOR]

In this paper, we present a matrix assembly technique for arbitrary polynomial order finite element simulations on simplex meshes for graphics processing units (GPU). Compared to the current state of the art in GPU‐based matrix assembly, we avoid the need for an intermediate sparse matrix and perform assembly directly into the final, GPU‐optimized data structure. Thereby, we avoid the resulting 180% to 600% memory overhead, depending on polynomial order, and associated allocation time, while simplifying the assembly code and using a more compact mesh representation. We compare our method with existing algorithms and demonstrate significant speedups. [ABSTRACT FROM AUTHOR]

Advancements in Next-Generation Sequencing (NGS) have significantly reduced the cost of generating DNA sequence data and increased the speed of data production. However, such high-throughput data production has increased the need for efficient data analysis programs. One of the most computationally demanding steps in analyzing sequencing data is mapping short reads produced by NGS to a reference DNA sequence, such as a human genome. The mapping program BWA-MEM and its newer version BWA-MEM2, optimized for CPUs, are some of the most popular choices for this task. In this study, we discuss the implementation of BWA-MEM on GPUs. This is a challenging task because many algorithms and data structures in BWA-MEM do not execute efficiently on the GPU architecture. This paper identifies major challenges in developing efficient GPU code on all major stages of the BWA-MEM program, including seeding, seed chaining, Smith-Waterman alignment, memory management, and I/O handling. We conduct comparison experiments against BWA-MEM and BWA-MEM2 running on a 64-thread CPU. The results show that our implementation achieved up to 3.2x speedup over BWA-MEM2 and up to 5.8x over BWA-MEM when using an NVIDIA A40. Using an NVIDIA A6000 and an NVIDIA A100, we achieved a wall-time speedup of up to 3.4x/3.8x over BWA-MEM2 and up to 6.1x/6.8x over BWA-MEM, respectively. In stage-wise comparison, the A40/A6000/A100 GPUs respectively achieved up to 3.7/3.8/4x, 2/2.3/2.5x, and 3.1/5/7.9x speedup on the three major stages of BWA-MEM: seeding and seed chaining, Smith-Waterman, and making SAM output. To the best of our knowledge, this is the first study that attempts to implement the entire BWA-MEM program on GPUs.

The high efficiency video coding standard provides excellent coding performance but is also very complex. Especially, the intra mode decision is very time-consuming due to the large number of available prediction modes and the flexible block partitioning scheme. In this paper, a highly parallel intra prediction algorithm for heterogeneous CPU+graphics processing unit (GPU) platforms is proposed, which accelerates the encoder dramatically. It is targeted toward high-quality high definition (HD) and ultra HD applications and utilizes prediction based on original samples (POSs), where the reference samples are generated from original pixels. This makes it possible to perform intramode prediction for all prediction blocks of a video frame concurrently. In addition, parallel-friendly cost functions are proposed which enable parallel rate distortion optimization with no synchronization overhead. A detailed statistical analysis of both POS and the proposed GPU intramethod is provided and the coding performance of the presented prototype is evaluated based on a large amount of experimental data. It is shown that the complexity of the intramode selection on the CPU is reduced by up to 78.03%. This translates to significant encoding time reductions of up to 64.52% for a single-threaded encoder and up to 94.82% in combination with wavefront parallel processing. In high bitrate ranges, average rate increases of only 2.11%–4.26% and 0.80%–2.34% are observed for the proposed high-speed and high-quality configurations, respectively. Furthermore, GPU intra is shown to be extremely efficient in lossless coding scenarios, where up to 53.37% time is saved with an average bitrate increase of only 0.55% among all test cases. [ABSTRACT FROM PUBLISHER]

The Gaia Astrometric Verification Unit–Global Sphere Reconstruction (AVU–GSR) Parallel Solver aims to find the astrometric parameters for ∼ 1 0 8 stars in the Milky Way, the attitude and the instrumental specifications of the Gaia satellite, and the global parameter γ of the post Newtonian formalism. The code iteratively solves a system of linear equations, A × x = b , where the coefficient matrix A is large (∼ 1 0 11 × 1 0 8 elements) and sparse. To solve this system of equations, the code exploits a hybrid implementation of the iterative PC-LSQR algorithm, where the computation related to different horizontal portions of the coefficient matrix is assigned to separate MPI processes. In the original code, each matrix portion is further parallelized over the OpenMP threads. To further improve the code performance, we ported the application to the GPU, replacing the OpenMP parallelization language with OpenACC. In this port, ∼ 95% of the data is copied from the host to the device at the beginning of the entire cycle of iterations, making the code compute bound rather than data-transfer bound. The OpenACC code presents a speedup of ∼ 1.5 over the OpenMP version but further optimizations are in progress to obtain higher gains. The code runs on multiple GPUs and it was tested on the CINECA supercomputer Marconi100, in anticipation of a port to the pre-exascale system Leonardo, that will be installed at CINECA in 2022. • Customized implementation of preconditioned LSQR algorithm. • Optimized solving of large and sparse systems with peculiar sparsity schemes. • GPU parallelization to gain in performance compared to CPU parallelization. • Optimized data copies host-to-device and device-to-host. • Parallelization with OpenACC in perspective of exascale systems. [ABSTRACT FROM AUTHOR]

Association rules mining (ARM) is a well-known combinatorial optimization problem aiming at extracting relevant rules from given large-scale datasets. According to the state of the art, the bio-inspired methods proved their efficiency by generating acceptable solutions in a reasonable time when dealing with small and medium size instances. Unfortunately, to cope with large instances such as the webdocs benchmark, these methods require more and more powerful processors and are time expensive. Nowadays, computing power is no longer a real issue. It can be provided by the power of emerging technologies such as graphics processing units (GPUs) that are massively multi-threaded processors. In this paper, we investigate the use of GPUs to speed up the computation. We propose two GPU-based bees swarm algorithms for association rules mining (single evaluation in GPU, SE-GPU and multiple evaluation in GPU, ME-GPU). SE-GPU aims at evaluating one rule at a time where each thread is associated with one transaction, whereas ME-GPU evaluates multiple rules in parallel on GPU where each thread is associated with several transactions. To validate our approaches, the two algorithms have been executed to solve well-known large ARM instances. Real experiments have been carried out on an Intel Xeon 64 bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our approaches improve the execution time up to 100 $$\times $$ over the sequential mono-core bees swarm optimization-ARM algorithm. Moreover, the proposed approaches have been compared with CPU multi-core ones (1-8 cores). The results show that they are faster than the multi-core versions whatever is the number of used cores. [ABSTRACT FROM AUTHOR]

A well-known clustering problem called Density-Based Spatial Clustering of Applications with Noise (DBSCAN) involves computing the solutions of at least one disk range query per input point, computing the connected components of a graph, and bichromatic fixed-radius nearest neighbor. MapReduce class is a model where a sublinear number of machines, each with sublinear memory, run for a polylogarithmic number of parallel rounds. Most of these problems either require quadratic time in the sequential model or are hard to compute in a constant number of rounds in MapReduce. In the Euclidean plane, DBSCAN algorithms with near-linear time and a randomized parallel algorithm with a polylogarithmic number of rounds exist. We solve DBSCAN in the Euclidean plane in a constant number of rounds in MapReduce, assuming the minimum number of points in range queries is constant and each connected component fits inside the memory of a single machine and has a constant diameter. [ABSTRACT FROM AUTHOR]

Recent and future generation observatories will enable the study of variable astronomical phenomena through their time-domain capabilities. High temporal fidelity will allow for unprecedented investigations into the nature of variable objects — those objects that vary in brightness over time. A major bottleneck in data processing pipelines is constructing light curve solutions for catalogs of variable objects, as it is well-known that period finding algorithms are computationally expensive. Furthermore, there are many period finding algorithms that are often suited for specific science cases. In this paper, we present the first GPU-accelerated Super Smoother algorithm. Super Smoother is general purpose and uses cross-validation to fit line segments to a time series, and as such, is more computationally expensive than other algorithms, such as Lomb–Scargle. Because the algorithm requires making several scans over the input time series for a tested frequency, we also propose a novel generalized-validation variant of Super Smoother that only requires a single scan over the data. We compare the performance of our algorithms to analogous parallel multi-core CPU implementations on three catalogs of data, and show that it is generally advantageous to use the GPU algorithm over the CPU counterparts. Furthermore, we demonstrate that our single-pass variant of Super Smoother is roughly equally as accurate at finding correct period solutions as the original algorithm. Our software supports several features, such as batching the computation to eliminate the possibility of exceeding global memory on the GPU, processing a single object or batches of objects, and we allow for scaling the algorithm across multiple GPUs. [ABSTRACT FROM AUTHOR]