Search

International audience; We introduce the concurrent binary tree (CBT), a novel concurrent representation to build and update arbitrary binary trees in parallel. Fundamentally, our representation consists of a binary heap, i.e., a 1D array, that explicitly stores the sum-reduction tree of a bitfield. In this bitfield, each one-valued bit represents a leaf node of the binary tree encoded by the CBT, which we locate algorithmically using a binary-search over the sum-reduction. We show that this construction allows to dispatch down to one thread per leaf node and that, in turn, these threads can safely split and/or remove nodes concurrently via simple bitwise operations over the bitfield. The practical benefit of CBTs lies in their ability to accelerate binary-tree-based algorithm with parallel processors. To support this claim, we leverage our representation to accelerate a longest-edge-bisection-based algorithm that computes and renders adaptive geometry for large-scale terrains entirely on the GPU. For this specific algorithm, the CBT accelerates processing speed linearly with the number of processors.

The model of membrane computing, also known under the name of P systems, is a bio-inspired large-scale parallel computing paradigm having a good potential for the design of massively parallel algorithms. For its implementation it is very natural to choose hardware platforms that have important inherent parallelism, such as field-programmable gate arrays (FPGAs) or compute unified device architecture (CUDA)-enabled graphic processing units (GPUs). This article performs an overview of all existing approaches of hardware implementation in the area of P systems. The quantitative and qualitative attributes of FPGA-based implementations and CUDA-enabled GPU-based simulations are compared to evaluate the two methodologies. Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP)

The Gaia Astrometric Verification Unit-Global Sphere Reconstruction (AVU-GSR) Parallel Solver aims to find the astrometric parameters for $\sim$10$^8$ stars in the Milky Way, the attitude and the instrumental specifications of the Gaia satellite, and the global parameter $\gamma$ of the post Newtonian formalism. The code iteratively solves a system of linear equations, $\mathbf{A} \times \vec{x} = \vec{b}$, where the coefficient matrix $\mathbf{A}$ is large ($\sim$$10^{11} \times 10^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, $\sim$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 $\sim$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., Comment: 18 pages, 8 figures, 3 pseudocodes, published in Astronomy and Computing, Volume 41, October 2022, 100660, accepted for publication on 4th October 2022

0000-0001-9240-3517 0000-0003-1626-5858 0000-0001-6213-8783 PubMed: 33633493 WOS:000613719800001 This study develops a modelling framework for simulating the spread of infectious diseases within real cities. Digital copies of Birmingham (UK) and Bogota (Colombia) are generated, reproducing their urban environment, infrastructure and population. The digital inhabitants have the same statistical features of the real population. Their motion is a combination of predictable trips (commute to work, school, etc.) and random walks (shopping, leisure, etc.). Millions of individuals, their encounters and the spread of the disease are simulated by means of high-performance computing and massively parallel algorithms for several months and a time resolution of 1 minute. Simulations accurately reproduce the COVID-19 data for Birmingham and Bogota both before and during the lockdown. The model has only one adjustable parameter calculable in the early stages of the pandemic. Policymakers can use our digital cities as virtual laboratories for testing, predicting and comparing the effects of policies aimed at containing epidemics. Engineering and Physical Sciences Research Council (EPSRC)UK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/S019227/1]; EPSRCUK Research & Innovation (UKRI)Engineering & Physical Sciences Research Council (EPSRC) [EP/P020232/1] This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) grant no. EP/S019227/1. The computations described in this paper were performed using (i) University of Birmingham's BlueBEAR HPC service and (ii) Athena at HPC Midlands+ (funded by the EPSRC with grant no. EP/P020232/1).

We present two Massively Parallel Computation (MPC) algorithms for the Minimum Cut problem: an O(1)-round exact algorithm with Õ(n) memory per machine, and an O(log n · log log n) round (2 + ε) approximation with Õ(nα) memory per machine, for any positive constant α < 1. Both algorithms use Õ(m) global memory. © 2020 Association for Computing Machinery.

We present the submatrix method, a highly parallelizable method for the approximate calculation of inverse p-th roots of large sparse symmetric matrices which are required in different scientific applications. Following the idea of Approximate Computing, we allow imprecision in the final result in order to utilize the sparsity of the input matrix and to allow massively parallel execution. For an n x n matrix, the proposed algorithm allows to distribute the calculations over n nodes with only little communication overhead. The result matrix exhibits the same sparsity pattern as the input matrix, allowing for efficient reuse of allocated data structures. We evaluate the algorithm with respect to the error that it introduces into calculated results, as well as its performance and scalability. We demonstrate that the error is relatively limited for well-conditioned matrices and that results are still valuable for error-resilient applications like preconditioning even for ill-conditioned matrices. We discuss the execution time and scaling of the algorithm on a theoretical level and present a distributed implementation of the algorithm using MPI and OpenMP. We demonstrate the scalability of this implementation by running it on a high-performance compute cluster comprised of 1024 CPU cores, showing a speedup of 665x compared to single-threaded execution. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 716142) and from the German Research Foundation (DFG) under the project Perfi- cienCC (grant agreement No PL 595/2-1). Compute resources were provided by the Paderborn Center for Parallel Computing (PC 2)

The ubiquity of large virtual worlds and their growing complexity in computer graphics require efficient representations. This means that we need smart solutions for the underlying storage of these complex environments, but also for their visualization. How the virtual world is best stored and how it is subsequently shown to the user in an optimal way, depends on the goal of the application. In this respect, we identify the following three visual representations, which form orthogonal directions, but are not mutually exclusive. Realistic representations aim for physical correctness, while illustrative display techniques, on the other hand, facilitate user tasks, often relating to improved understanding. Finally, artistic approaches enable a high level of expressiveness for aesthetic applications. Each of these directions offers a wide array of possibilities. In this dissertation, our goal is to provide solutions for strategically selected challenges for all three visual directions, as well as for the underlying representation of the virtual world.

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.

Ideally, DDMs seek what we call the DDM-paradigm: “constructing the global solution by solving local problems, exclusively”. To achieve it, it is essential to disconnect the subdomain-problems. In FETI-DP such disconnection is achieved by formulating the method in a product function-space that contains discontinuous functions. However, FETI-DP uses an indirect formulation based on Lagrange-multipliers. BDDC uses instead a more direct formulation, but does not work directly in a space of discontinuous functions, either. Another fact difficult to overcome is: at present competitive algorithms need to incorporate constraints that prevent full disconnection of the subdomains. This paper is devoted to explain a direct (primal) approach to DDMs in which all the numerical work is done in a product-space (the derived-vector space), which supplies a unified setting for non-overlapping DDMs and can be used to formulate and discuss in a general and systematic manner the theory of DDMs for non-symmetric problems. Furthermore, in this realm four general-purposes preconditioned algorithms with constraints applicable to non-symmetric matrices, which achieve the DDM-paradigm, have been obtained. Two of them have been identified as DVS-versions of BDDC and FETI-DP. The uniformity of the matrix-formulas expressing such algorithms should be highlighted.

Context. Train re-scheduling during disturbances is a time-consuming task. Modified schedules need to be found, so that trains can meet in suitable locations and delays minimized. Domino effects are difficult to manage. Commercial optimization software has been shown to find optimal solutions, but modied schedules need to be found quickly. Therefore, greedy depth-first algorithms have been designed to find solutions within a limited time-frame. Modern GPUs have a high computational capacity, and have become easier to use for computations unrelated to computer graphics with the development of technologies such as CUDA and OpenCL. Objectives. We explore the feasibility of running a re-scheduling algorithm developed specifically for this problem on a GPU using the CUDA toolkit. The main objective is to find a way of exploiting the computational capacity of modern GPUs to find better re-scheduling solutions within a limited time-frame. Methods. We develop and adapt a sequential algorithm for use on a GPU and run multiple experiments using 16 disturbance scenarios on the single-tracked iron ore line in northern Sweden. Results. Our implementation succeeds in finding re-scheduling solutions without conflicts for all 16 scenarios. The algorithm visits on average 7 times more nodes per time unit than the sequential CPU algorithm when branching at depth 50, and 4 times more when branching at depth 200. Conclusions. The computational performance of our parallel algorithm is promising but the approach is not complete. Our experiments only show that multiple solution branches can be explored fast in parallel, but not how to construct a high level algorithm that systematically searches for better schedules within a certain time limit. Further research is needed for that. We also find that multiple threads explore redundant solutions in our approach.

The goals of this project are to develop new, scalable, high-fidelity algorithms for atomic-level simulations and program transformations that automatically restructure existing applications, enabling them to scale forward to Petascale systems and beyond. The techniques enable legacy MPI application code to exploit greater parallelism though increased latency hiding and improved workload assignment. The techniques were successfully demonstrated on high-end scalable systems located at DOE laboratories. Besides the automatic MPI program transformations efforts, the project also developed several new scalable algorithms for ab-initio molecular dynamics, including new massively parallel algorithms for hybrid DFT and new parallel in time algorithms for molecular dynamics and ab-initio molecular dynamics. These algorithms were shown to scale to very large number of cores, and they were designed to work in the latency hiding framework developed in this project. The effectiveness of the developments was enhanced by the direct application to real grand challenge simulation problems covering a wide range of technologically important applications, time scales and accuracies. These included the simulation of the electronic structure of mineral/fluid interfaces, the very accurate simulation of chemical reactions in microsolvated environments, and the simulation of chemical behavior in very large enzyme reactions.

A generalized gyrokinetic Poisson solver has been developed, which employs local operations in the configuration space to compute the polarization density response. The new technique is based on the actual physical process of gyrophase-averaging. It is useful for nonlocal simulations using general geometry equilibrium. Since it utilizes local operations rather than the global ones such as FFT, the new method is most amenable to massively parallel algorithms.