Search NASA⌕ Search

SEARCH · Search NASA

Results for “parallel computing algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,135 records · Page 63

Stochastic, real-space, imaginary-time evaluation of third-order Feynman–Goldstone diagrams

A new, alternative set of interpretation rules of Feynman–Goldstone diagrams for many-body perturbation theory is proposed, which translates diagrams into algebraic expressions suitable for direct Monte Carlo integrations. A vertex of a diagram is associated with a Coulomb interaction (rather than a two-electron integral) and an edge with the trace of a Green's function in real space and imaginary time. With these, 12 diagrams of third-order many-body perturbation (MP3) theory are converted into 20-dimensional integrals, which are then evaluated by a Monte Carlo method. It uses redundant walkers for convergence acceleration and a weight function for importance sampling in conjunction with the Metropolis algorithm. The resulting Monte Carlo MP3 method has low-rank polynomial size dependence of the operation cost, a negligible memory cost, and a naturally parallel computational kernel, while reproducing the correct correlation energies of small molecules within a few mE{sub h} after 10{sup 6} Monte Carlo steps.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A mesh partitioning algorithm for preserving spatial locality in arbitrary geometries

Highlights: •An algorithm for partitioning computational meshes is proposed. •The Morton order space-filling curve is modified to achieve improved locality. •A spatial locality metric is defined to compare results with existing approaches. •Results indicate improved performance of the algorithm in complex geometries. -- Abstract: A space-filling curve (SFC) is a proximity preserving linear mapping of any multi-dimensional space and is widely used as a clustering tool. Equi-sized partitioning of an SFC ignores the loss in clustering quality that occurs due to inaccuracies in the mapping. Often, this results in poor locality within partitions, especially for the conceptually simple, Morton order curves. We present a heuristic that improves partition locality in arbitrary geometries by slicing a Morton order curve at points where spatial locality is sacrificed. In addition, we develop algorithms that evenly distribute points to the extent possible while maintaining spatial locality. A metric is defined to estimate relative inter-partition contact as an indicator of communication in parallel computing architectures. Domain partitioning tests have been conducted on geometries relevant to turbulent reactive flow simulations. The results obtained highlight the performance of our method as an unsupervised and computationally inexpensive domain partitioning tool.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Massively Parallel Simulation of Large Molecular Systems with Long-Range Interactions Final Report CRADA No. TC-0297-92-B

The purpose of this CRADA project is to develop and implement a large-scale molecular dynamics model for floppy molecules with long-ranged interaction on massively parallel supercomputers and accelerate the use of parallel supercomputers within the biomolecular and polymer industries. Within three years of the project, the partners will: create a new molecular dynamics computer simulation code (LAMMPS) from existing codes at SAndia National Laboratory-Albuquerque (SNL-A) and Lawrence Livermore National Laboratory (LLNL) and new algorithms and code developed during the CRADA project; design the resulting code to optimally use the emerging generation of massively parallel supercomputers; and apply the code to the solution of biomolecular problem suggested by Bristol-Myers Squibb (BMS) and polymer problems suggested by DuPont.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

High-Performance Computation of Distributed-Memory Parallel 3D Voronoi and Delaunay Tessellation

Computing a Voronoi or Delaunay tessellation from a set of points is a core part of the analysis of many simulated and measured datasets: N-body simulations, molecular dynamics codes, and LIDAR point clouds are just a few examples. Such computational geometry methods are common in data analysis and visualization; but as the scale of simulations and observations surpasses billions of particles, the existing serial and shared-memory algorithms no longer suffice. A distributed-memory scalable parallel algorithm is the only feasible approach. The primary contribution of this paper is a new parallel Delaunay and Voronoi tessellation algorithm that automatically determines which neighbor points need to be exchanged among the subdomains of a spatial decomposition. Other contributions include periodic and wall boundary conditions, comparison of our method using two popular serial libraries, and application to numerous science datasets.

97 MATHEMATICS AND COMPUTING↗

Massively parallel phase-field simulations targeting exascale

The interface thickness in the phase-field (PF) method limits its simulation scales. Consequently, large-scale PF simulations become prohibitively expensive for resolving the extremely fine microstructures that typically form during rapid solidification processing. This challenge is significant in predicting microstructure evolution in metal additive manufacturing and has been identified by the United States Department of Energy’s Exascale Computing Project. Here, to address this, we develop a multi-GPU and MPI-based massively parallel simulation code, utilizing state-of-the-art algorithms, software, and libraries, for large-scale three-dimensional (3D) PF simulations. We report the first GPU-parallel PF simulations on Frontier (currently the second TOP500 exascale cluster) and Summit machines, taking dendritic growth as an example problem. We evaluate the parallel performance of our implementation using scaling studies with more than 24 000 GPUs (among the largest known computations to date) and the acceleration performance using large-scale simulations of dendritic growth in 3D. Finally, massively parallel GPUs in these supercomputers enabled the first coupled multiscale simulations of laser melting and subsequent dendritic solidification on the scale of a full melt-pool, demonstrating the feasibility of performing PF simulations with a point total over 2 billion grid points within an acceptable time.

Exascale↗

Scalable FBP decomposition for cone-beam CT reconstruction

Filtered Back-Projection (FBP) is a fundamental compute intense algorithm used in tomographic image reconstruction. Cone-Beam Computed Tomography (CBCT) devices use a cone-shaped X-ray beam, in comparison to the parallel beam used in older CT generations. Distributed image reconstruction of cone-beam datasets typically relies on dividing batches of images into different nodes. This simple input decomposition, however, introduces limits on input/output sizes and scalability.We propose a novel decomposition scheme and reconstruction algorithm for distributed FPB. This scheme enables arbitrarily large input/output sizes, eliminates the redundancy arising in the end-to-end pipeline and improves the scalability by replacing two communication collectives with only one segmented reduction. Finally, we implement the proposed decomposition scheme in a framework that is useful for all current-generation CT devices (7th gen). In our experiments using up to 1024 GPUs, our framework can construct 40963 volumes, for real-world datasets, in under 16 seconds (including I/O).

Chen, Peng↗

A high-speed linear algebra library with automatic parallelism

Parallel or distributed processing is key to getting highest performance workstations. However, designing and implementing efficient parallel algorithms is difficult and error-prone. It is even more difficult to write code that is both portable to and efficient on many different computers. Finally, it is harder still to satisfy the above requirements and include the reliability and ease of use required of commercial software intended for use in a production environment. As a result, the application of parallel processing technology to commercial software has been extremely small even though there are numerous computationally demanding programs that would significantly benefit from application of parallel processing. This paper describes DSSLIB, which is a library of subroutines that perform many of the time-consuming computations in engineering and scientific software. DSSLIB combines the high efficiency and speed of parallel computation with a serial programming model that eliminates many undesirable side-effects of typical parallel code. The result is a simple way to incorporate the power of parallel processing into commercial software without compromising maintainability, reliability, or ease of use. This gives significant advantages over less powerful non-parallel entries in the market.

Boucher, Michael L.↗

Efficient scalable algorithms for hierarchically semiseparable matrices

Hierarchically semiseparable (HSS) matrix algorithms are emerging techniques in constructing the superfast direct solvers for both dense and sparse linear systems. Here, we develope a set of novel parallel algorithms for the key HSS operations that are used for solving large linear systems. These include the parallel rank-revealing QR factorization, the HSS constructions with hierarchical compression, the ULV HSS factorization, and the HSS solutions. The HSS tree based parallelism is fully exploited at the coarse level. The BLACS and ScaLAPACK libraries are used to facilitate the parallel dense kernel operations at the ne-grained level. We have appplied our new parallel HSS-embedded multifrontal solver to the anisotropic Helmholtz equations for seismic imaging, and were able to solve a linear system with 6.4 billion unknowns using 4096 processors, in about 20 minutes. The classical multifrontal solver simply failed due to high demand of memory. To our knowledge, this is the first successful demonstration of employing the HSS algorithms in solving the truly large-scale real-world problems. Our parallel strategies can be easily adapted to the parallelization of the other rank structured methods.

01 COAL, LIGNITE, AND PEAT↗

Simulation study of Type 2 counterstreaming electrons along auroral field lines

The production of counterstreaming electrons associated with parallel fields along auroral field lines is examined through the use of computer simulation. A 2 1/2-dimensional (two spatial and three velocity dimensions) electrostatic particle algorithm and auroral boundary conditions are used to set up a self-consistent V potential structure. The simulation produces signatures of counterstreaming electrons resembling those observed by the Dynamics Explorer 1 satellite. The main signatures are as follows: (1) the phase space contours of the electron distribution function are elongated along the V-parallel axis, and (2) the energy of electrons streaming in the upward direction is comparable to the energy of the accelerated electron beam. The simulation indicates that a portion of the accelerated electron beam is trapped by large amplitude electrostatic waves produced through the two-stream instability. Strong wave-particle interactions then thermalize the trapped electrons to produce suprathermal electrons streaming in the direction opposite to that of the accelerated electron beam. These results suggest a possible mechanism of producing counterstreaming electron fluxes through nonlinear processes of the two-stream instability.

Wagner, J. S.↗

Applying graph partitioning methods in measurement-based dynamic load balancing

Load imbalance leads to an increasing waste of resources as an application is scaled to more and more processors. Achieving the best parallel efficiency for a program requires optimal load balancing which is a NP-hard problem. However, finding near-optimal solutions to this problem for complex computational science and engineering applications is becoming increasingly important. Charm++, a migratable objects based programming model, provides a measurement-based dynamic load balancing framework. This framework instruments and then migrates over-decomposed objects to balance computational load and communication at runtime. This paper explores the use of graph partitioning algorithms, traditionally used for partitioning physical domains/meshes, for measurement-based dynamic load balancing of parallel applications. In particular, we present repartitioning methods developed in a graph partitioning toolbox called SCOTCH that consider the previous mapping to minimize migration costs. We also discuss a new imbalance reduction algorithm for graphs with irregular load distributions. We compare several load balancing algorithms using microbenchmarks on Intrepid and Ranger and evaluate the effect of communication, number of cores and number of objects on the benefit achieved from load balancing. New algorithms developed in SCOTCH lead to better performance compared to the METIS partitioners for several cases, both in terms of the application execution time and fewer number of objects migrated.

97 MATHEMATICS AND COMPUTING↗

Parallel CFD Algorithms for Aerodynamical Flow Solvers on Unstructured Meshes

The Advisory Group for Aerospace Research and Development (AGARD) has requested my participation in the lecture series entitled Parallel Computing in Computational Fluid Dynamics to be held at the von Karman Institute in Brussels, Belgium on May 15-19, 1995. In addition, a request has been made from the US Coordinator for AGARD at the Pentagon for NASA Ames to hold a repetition of the lecture series on October 16-20, 1995. I have been asked to be a local coordinator for the Ames event. All AGARD lecture series events have attendance limited to NATO allied countries. A brief of the lecture series is provided in the attached enclosure. Specifically, I have been asked to give two lectures of approximately 75 minutes each on the subject of parallel solution techniques for the fluid flow equations on unstructured meshes. The title of my lectures is "Parallel CFD Algorithms for Aerodynamical Flow Solvers on Unstructured Meshes" (Parts I-II). The contents of these lectures will be largely review in nature and will draw upon previously published work in this area. Topics of my lectures will include: (1) Mesh partitioning algorithms. Recursive techniques based on coordinate bisection, Cuthill-McKee level structures, and spectral bisection. (2) Newton's method for large scale CFD problems. Size and complexity estimates for Newton's method, modifications for insuring global convergence. (3) Techniques for constructing the Jacobian matrix. Analytic and numerical techniques for Jacobian matrix-vector products, constructing the transposed matrix, extensions to optimization and homotopy theories. (4) Iterative solution algorithms. Practical experience with GIVIRES and BICG-STAB matrix solvers. (5) Parallel matrix preconditioning. Incomplete Lower-Upper (ILU) factorization, domain-decomposed ILU, approximate Schur complement strategies.

Barth, Timothy J.↗

Parallelization of Program to Optimize Simulated Trajectories (POST3D)

This paper describes the parallelization of the Program to Optimize Simulated Trajectories (POST3D). POST3D uses a gradient-based optimization algorithm that reaches an optimum design point by moving from one design point to the next. The gradient calculations required to complete the optimization process, dominate the computational time and have been parallelized using a Single Program Multiple Data (SPMD) on a distributed memory NUMA (non-uniform memory access) architecture. The Origin2000 was used for the tests presented.

Hammond, Dana P.↗

A Novel Application of Parallel Betweenness Centrality to Power Grid Contingency Analysis

In Energy Management Systems, contingency analysis is commonly performed for identifying and mitigating potentially harmful power grid component failures. The exponentially increasing combinatorial number of failure modes imposes a significant computational burden for massive contingency analysis. It is critical to select a limited set of high-impact contingency cases within the constraint of computing power and time requirements to make it possible for real-time power system vulnerability assessment. In this paper, we present a novel application of parallel betweenness centrality to power grid contingency selection. We cross-validate the proposed method using the model and data of the western US power grid, and implement it on a Cray XMT system - a massively multithreaded architecture - leveraging its advantages for parallel execution of irregular algorithms, such as graph analysis. We achieve a speedup of 55 times (on 64 processors) compared against the single-processor version of the same code running on the Cray XMT. We also compare an OpenMP-based version of the same code running on an HP Superdome shared-memory machine. The performance of the Cray XMT code shows better scalability and resource utilization, and shorter execution time for large-scale power grids. This proposed approach has been evaluated in PNNL’s Electricity Infrastructure Operations Center (EIOC). It is expected to provide a quick and efficient solution to massive contingency selection problems to help power grid operators to identify and mitigate potential widespread cascading power grid failures in real time.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Efficient Simulation of Nested Hollow Sphere Intersections: for Dynamically Nested Compartmental Models in Cell Biology

In the particle-based simulation of cell-biological systems in continuous space, a key performance bottleneck is the computation of all possible intersections between particles. These typically rely for collision detection on solid sphere approaches. The behavior of cell biological systems is influenced by dynamic hierarchical nesting, such as the forming of, the transport within, and the merging of vesicles. Existing collision detection algorithms are found not to be designed for these types of spatial cell-biological models, because nearly all existing high performance parallel algorithms are focusing on solid sphere interactions. The known algorithms for solid sphere intersections return more intersections than actually occur with nested hollow spheres. Here we define a new problem of computing the intersections among arbitrarily nested hollow spheres of possibly different sizes, thicknesses, positions, and nesting levels. We describe a new algorithm designed to solve this nested hollow sphere intersection problem and implement it for parallel execution on graphical processing units (GPUs). We present first results about the runtime performance and scaling to hundreds of thousands of spheres, and compare the performance with that from a leading solid object intersection package also running on GPUs.

Koester, Till↗

Spatiotemporal parallelization of an analytical heat conduction model for additive manufacturing via a hybrid OpenMP + MPI approach

The ability to do thermal simulations for entire additive manufacturing builds is a key computational problem facing the additive manufacturing community; however, complex numerical models considering multiple physical phenomena currently do not have the capacity for simulations at this scale. To this end, conduction only analytic models offer a viable approach due to the massive drop in computational expense. In this work, we extend an existing implementation which uses a governing equation which can be evaluated at any point in space and time. This implementation already utilizes OpenMP with a spatial decompositions scheme stemming from a melt pool tracking algorithm. Furthermore, we then combine this with a parallel in time (PinT) approach to make the problem highly parallelizable. The new scheme, which uses MPI for internode communication and OpenMP for intranode communication, is shown to scale very well across multiple computational nodes. This approach results in the ability to simulate the 3D solidification conditions for entire layers of additively manufactured parts in minutes making part scale thermal simulations more practical.

36 MATERIALS SCIENCE↗

PSLQ: An Algorithm to Discover Integer Relations

Let x = (x{sub 1}, x{sub 2} {hor_ellipsis}, x{sub n}) be a vector of real or complex numbers. x is said to possess an integer relation if there exist integers a{sub i}, not all zero, such that a{sub 1}x{sub 1} + a{sub 2}x{sub 2} + {hor_ellipsis} + a{sub n}x{sub n} = 0. By an integer relation algorithm, we mean a practical computational scheme that can recover the vector of integers ai, if it exists, or can produce bounds within which no integer relation exists. As we will see in the examples below, an integer relation algorithm can be used to recognize a computed constant in terms of a formula involving known constants, or to discover an underlying relation between quantities that can be computed to high precision. At the present time, the most effective algorithm for integer relation detection is the 'PSLQ' algorithm of mathematician-sculptor Helaman Ferguson [10, 4]. Some efficient 'multi-level' implementations of PSLQ, as well as a variant of PSLQ that is well-suited for highly parallel computer systems, are given in [4]. PSLQ constructs a sequence of integer-valued matrices B{sub n} that reduces the vector y = xB{sub n}, until either the relation is found (as one of the columns of B{sub n}), or else precision is exhausted. At the same time, PSLQ generates a steadily growing bound on the size of any possible relation. When a relation is found, the size of smallest entry of the vector y abruptly drops to roughly 'epsilon' (i.e. 10{sup -p}, where p is the number of digits of precision). The size of this drop can be viewed as a 'confidence level' that the relation is real and not merely a numerical artifact - a drop of 20 or more orders of magnitude almost always indicates a real relation. Very high precision arithmetic must be used in PSLQ. If one wishes to recover a relation of length n, with coefficients of maximum size d digits, then the input vector x must be specified to at least nd digits, and one must employ nd-digit floating-point arithmetic. Maple and Mathematica include multiple precision arithmetic facilities and Maple ships with a full implementation of PSLQ. One may also use any of several freeware multiprecision software packages, for example the ARPREC package by the first author and colleagues at LBNL [7]. In the remaining sections we describe various representative applications of PSLQ. More detail about these examples is given in [8] and the references therein.

97 MATHEMATICS AND COMPUTING↗

Parallel Breadth-First Search on Distributed Memory Systems

Data-intensive, graph-based computations are pervasive in several scientific applications, and are known to be quite challenging to implement on distributed memory systems. In this work, we explore the design space of parallel algorithms for Breadth-First Search (BFS), a key subroutine in several graph algorithms. We present two highly-tuned parallel approaches for BFS on large parallel systems: a level-synchronous strategy that relies on a simple vertex-based partitioning of the graph, and a two-dimensional sparse matrix-partitioning-based approach that mitigates parallel communication overhead. For both approaches, we also present hybrid versions with intra-node multithreading. Our novel hybrid two-dimensional algorithm reduces communication times by up to a factor of 3.5, relative to a common vertex based approach. Our experimental study identifies execution regimes in which these approaches will be competitive, and we demonstrate extremely high performance on leading distributed-memory parallel systems. For instance, for a 40,000-core parallel execution on Hopper, an AMD Magny-Cours based system, we achieve a BFS performance rate of 17.8 billion edge visits per second on an undirected graph of 4.3 billion vertices and 68.7 billion edges with skewed degree distribution.

97 MATHEMATICS AND COMPUTING↗

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗