Search

Large sparse matrices with compound entries, i.e., complex and quaternionic matrices as well as matrices with dense blocks, are a core component of many algorithms in geometry processing, physically based animation, and other areas of computer graphics. We generalize several matrix layouts and apply joint schedule and layout autotuning to improve the performance of the sparse matrix-vector product on massively parallel graphics processing units. Compared to schedule tuning without layout tuning, we achieve speedups of up to 5.5x. In comparison to cuSPARSE, we achieve speedups of up to 4.7x, Vision, Modeling and Visualization, GPU, 109, 116, Johannes Sebastian Mueller-Roemer, André Stork, and Dieter W. Fellner, CCS Concepts: Computing methodologies --> Massively parallel algorithms; Parallel programming languages; Mathematics of computing --> Computations on matrices

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.

Parallel architectures, in the form of multi-core or multiple computers, have produced a major impact in the field of information technology. GPU devices, as an extreme example of parallel architectures, have been adapted to enable generic computation in massively parallel architectures. Molecular dynamics is a problem that fits perfectly such architectures, as it relies on the computation of many similar interactions between atoms. Moreover, large molecular systems require resources that exceed those available in a single computer, even multi-GPU computers. Therefore, the ideal architecture to simulate molecular dynamics is a distributed multi-GPU cluster, which consists of multiple interconnected computers with one or more GPUs each. A molecular dynamics simulation usually needs days, and even weeks of computation time to produce results that represent only a few microseconds of atom interactions. In contrast, distributed multi-GPU clusters allows us to develop an efficient and scalable simulator. This paper aims to develop a prototype of a molecular dynamics simulator for large molecular systems. It uses the GPU as the main computing device, using only the CPU to control the workflow. We have implemented parallel processing techniques to develop a fully scalable system., Spanish Computer Graphics Conference (CEIG), Animation and Simulation, 25, 28, Gonzalo Nicolas-Barreales, Marcos Novalbos, Miguel Ángel Otaduy, and Alberto Sánchez, CCS Concepts: Computing methodologies --> Massively parallel algorithms; Graphics processors; Applied computing --> Molecular structural biology

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.

In this paper the recent developments of lattice kinetic models are discussed followed by the fundamental concepts of Evolutionary Algorithms and their application to optimization, machine learning, Neural networks and many other areas. Finally, the application of Evolutionary Algorithms to the biological eco-system is presented.

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.

We consider analogies between statistic mechanical approach and computational algorithm description. The notion of algorithm entropy is introduced to characterize measure of potential parallelism and compare algorithms. The value of entropy for some couple of algorithms is evaluated (ordinary block matrix multiplication and Strassen's algorithm, LU decomposition and QIF, particle-particle and particle-mesh algorithms). We discuss thermodynamical approach to the algorithm description in the frame of which one can discover self-organization phenomenon in massively parallel algorithms.

In this paper, we present a way of expressing massively parallel algorithms associated with a programming environment for networks of processors with local memory; the aim is to provide a programming method that is independent of the network topology, and that leads to an efficient implementation for communications. Then, we illustrate these concepts using as an example a scientific algorithm: Choleski's method for a parallel factorization of sparse matrices into blocks. This work gives rise to software for a T.Node multiprocessor computer.

Time-parallel algorithms for solution of the Schrodinger equation are developed. By using the Crank-Nicolson method, it is shown that the solution of the problem can be fully parallelized in time, leading to a massive temporal parallelism in the computation with a minimum of communication and synchronization requirements. Our results clearly indicate that the Crank-Nicolson method, in addition to its excellent numerical properties, is also highly suitable for massively parallel computation. >

This work presents how Weighted Inheritance Networks, a new formalism that is capable of representing knowledge under a nonmonotonic multiple inheritance scheme with exceptions, support the design of massively parallel algorithms for problems related to nonmonotonic reasoning. Weighted Inheritance Networks are semantic networks with links that are annotated with symbolic pairs that we call weights. They can handle the inheritance structures described in the literature, including some which the so far proposed formalisms may fail to treat satisfactorily. Weighted Inheritance Networks support the development of both sequential and parallel efficient algorithms, without sacrificing any desired properties that inheritance networks should, in general, possess. We investigate the performance of parallel nonmonotonic multiple inheritance reasoners based on Weighted Inheritance Networks, for two important problems: the goal-directed inheritance reasoning problem, that consists in answering whether an object possesses a particular property and the recognition problem, that consists in finding all the objects possesing a particular set of properties. We present a system that provides massively parallel support for nonmonotonic “path-based” reasoning, called WINBRID, and we analyze its performance using randomly generated knowledge bases.

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.

Processing and analysis of terrain data are essential tasks of path planning and navigation. This paper describes an assortment of massively parallel algorithms for processing and analysis of terrain data to support path planning and navigation. These algorithms were implemented on the Martin Marietta geometric arithmetic parallel processor array consisting of 108 x 384 processing elements. Their applications in path planning and navigation of low-altitude combat aircrafts are discussed.