Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Parallel 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,027 records · Page 57

Parallelized Kalman-Filter-Based Reconstruction of Particle Tracks on Many-Core Architectures

Faced with physical and energy density limitations on clock speed, contemporary microprocessor designers have increasingly turned to on-chip parallelism for performance gains. Algorithms should accordingly be designed with ample amounts of fine-grained parallelism if they are to realize the full performance of the hardware. This requirement can be challenging for algorithms that are naturally expressed as a sequence of small-matrix operations, such as the Kalman filter methods widely in use in high-energy physics experiments. In the High-Luminosity Large Hadron Collider (HL-LHC), for example, one of the dominant computational problems is expected to be finding and fitting charged-particle tracks during event reconstruction; today, the most common track-finding methods are those based on the Kalman filter. Experience at the LHC, both in the trigger and offline, has shown that these methods are robust and provide high physics performance. Previously we reported the significant parallel speedups that resulted from our efforts to adapt Kalman-filter-based tracking to many-core architectures such as Intel Xeon Phi. Here we report on how effectively those techniques can be applied to more realistic detector configurations and event complexity.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

WARP

WARP, which can stand for ``Weaving All the Random Particles,'' is a three-dimensional (3D) continuous energy Monte Carlo neutron transport code developed at UC Berkeley to efficiently execute on NVIDIA graphics processing unit (GPU) platforms. WARP accelerates Monte Carlo simulations while preserving the benefits of using the Monte Carlo method, namely, that very few physical and geometrical simplifications are applied. WARP is able to calculate multiplication factors, neutron flux distributions (in both space and energy), and fission source distributions for time-independent neutron transport problems. It can run in both criticality or fixed source modes, but fixed source mode is currently not robust, optimized, or maintained in the newest version. WARP can transport neutrons in unrestricted arrangements of parallelepipeds, hexagonal prisms, cylinders, and spheres. The goal of developing WARP is to investigate algorithms that can grow into a full-featured, continuous energy, Monte Carlo neutron transport code that is accelerated by running on GPUs. The crux of the effort is to make Monte Carlo calculations faster while producing accurate results. Modern supercomputers are commonly being built with GPU coprocessor cards in their nodes to increase their computational efficiency and performance. GPUs execute efficiently on data-parallel problems, but most CPU codes, including those for Monte Carlo neutral particle transport, are predominantly task-parallel. WARP uses a data-parallel neutron transport algorithm to take advantage of the computing power GPUs offer.

Bergmann, RyanM. [University of California - Berke↗

WARP

WARP, which can stand for ``Weaving All the Random Particles,'' is a three-dimensional (3D) continuous energy Monte Carlo neutron transport code developed at UC Berkeley to efficiently execute on NVIDIA graphics processing unit (GPU) platforms. WARP accelerates Monte Carlo simulations while preserving the benefits of using the Monte Carlo method, namely, that very few physical and geometrical simplifications are applied. WARP is able to calculate multiplication factors, neutron flux distributions (in both space and energy), and fission source distributions for time-independent neutron transport problems. It can run in both criticality or fixed source modes, but fixed source mode is currently not robust, optimized, or maintained in the newest version. WARP can transport neutrons in unrestricted arrangements of parallelepipeds, hexagonal prisms, cylinders, and spheres. The goal of developing WARP is to investigate algorithms that can grow into a full-featured, continuous energy, Monte Carlo neutron transport code that is accelerated by running on GPUs. The crux of the effort is to make Monte Carlo calculations faster while producing accurate results. Modern supercomputers are commonly being built with GPU coprocessor cards in their nodes to increase their computational efficiency and performance. GPUs execute efficiently on data-parallel problems, but most CPU codes, including those for Monte Carlo neutral particle transport, are predominantly task-parallel. WARP uses a data-parallel neutron transport algorithm to take advantage of the computing power GPUs offer.

Bergmann, Ryan M.↗

Distributed parallel processing applied to an implicit multigrid Euler/Navier-Stokes algorithm

An implicit multigrid algorithm for the solution of the Euler and Navier-Stokes equations has been implemented within the framework of multiple block-structured grids in which the physical domain is spatially decomposed into several blocks and the solution is advanced in parallel on each block. Utilities have been developed to implement such a scheme in a distributed computing environment. The multi-block algorithm is designed so that the explicit residual calculation is identical to that of single-block scheme, and therefore converged solutions for both schemes must be the same. To accelerate convergence, synchronous and asynchronous multigrid strategies are implemented. Significant speedups have been achieved in a multiple processor environment, while convergence rates similar to those of the single-block scheme are observed.

Tysinger, T. L.↗

Competitive Parallel Processing For Compression Of Data

Momentarily-best compression algorithm selected. Proposed competitive-parallel-processing system compresses data for transmission in channel of limited band-width. Likely application for compression lies in high-resolution, stereoscopic color-television broadcasting. Data from information-rich source like color-television camera compressed by several processors, each operating with different algorithm. Referee processor selects momentarily-best compressed output.

Diner, Daniel B.↗

Automatic identification and classification of Palomar Transient Factory astrophysical objects in GLADE

Palomar Transient Factory (PTF) is a comprehensive detection system for the identification and classification of transient astrophysical objects. In this paper, we make two significant contributions to the PTF pipeline. First, we present an experimental study that evaluates a novel implementation of the real-time classifier in GLADE - a parallel data processing system that combines the efficiency of a database with the extensibility of map-reduce. We show how each stage in the classifier maps optimally into GLADE tasks by taking advantage of the unique features of the system - range-based data partitioning, columnar storage, multi-query execution, and in-database support for complex aggregate computation. Second, we introduce a novel parallel similarity join algorithm for advanced transient classification. In conclusion, we implement this algorithm in GLADE and execute it on a massive supercomputer with more than 3,000 threads, achieving more than three orders of magnitude improvement over the PostgreSQL solution.

79 ASTRONOMY AND ASTROPHYSICS↗

Computational Biology for Drug Discovery and Characterization

We proposed to determine the underpinnings of a high-throughput computational infrastructure that would support future efforts in therapeutics against biothreat pathogens. Existing modeling capabilities focus on pathogen detection, but extending such capabilities to high-throughput molecular docking would lead to a proactive method to guide the development of therapeutics. This project will focus on determining the feasibility of extending current databases to accommodate molecular docking. We will also examine the feasibility of massive parallelization of docking algorithms and the utility of docking libraries. Transferring this new technique to a high-performance computing (HPC) platform at LLNL would result in a unique capability not available elsewhere in government or industry. We have accomplished the proposed work defined in this LDRD FS study. (1) We successfully defined the feasibility of using three different small-molecule databases for high-throughput docking, the NCI diversity set, ZINC and the ACD. (2) We analyzed the accuracy and parallelization capabilities of six separate docking programs: DOCK, AutoDock, FlexX, Glide, and eHiTS. Each program is completely amenable to parallel execution. The fastest code was eHiTS, and Glide was the most accurate. (3) Customizing large libraries was cumbersome without the proper software, making the databases a bit difficult to tailor. The ZINC database has some prefiltered versions. (4) Scripts were created for quality and job control functions. Further development is needed for analysis and visualization needs. The successful conclusion of this project enables LLNL to have a high-throughput computational docking capability where we have evaluated the codes to specific docking problems and utilized LLNL's HPC for significant gains in performance. We have established a CRADA with an industrial partner (funded by the National Institutes of Health) that will fully utilize this technology for biodefense therapeutic design and development.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Combinatorial Algorithms to Enable Computational Science and Engineering: Work from the CSCAPES Institute

This final progress report summarizes the work accomplished at the Combinatorial Scientific Computing and Petascale Simulations Institute. We developed Zoltan, a parallel mesh partitioning library that made use of accurate hypergraph models to provide load balancing in mesh-based computations. We developed several graph coloring algorithms for computing Jacobian and Hessian matrices and organized them into a software package called ColPack. We developed parallel algorithms for graph coloring and graph matching problems, and also designed multi-scale graph algorithms. Three PhD students graduated, six more are continuing their PhD studies, and four postdoctoral scholars were advised. Six of these students and Fellows have joined DOE Labs (Sandia, Berkeley), as staff scientists or as postdoctoral scientists. We also organized the SIAM Workshop on Combinatorial Scientific Computing (CSC) in 2007, 2009, and 2011 to continue to foster the CSC community.

97 MATHEMATICS AND COMPUTING↗

Kmer-SSR: a fast and exhaustive SSR search algorithm

Motivation: One of the main challenges with bioinformatics software is that the size and complexity of datasets necessitate trading speed for accuracy, or completeness. To combat this problem of computational complexity, a plethora of heuristic algorithms have arisen that report a ‘good enough’ solution to biological questions. However, in instances such as Simple Sequence Repeats (SSRs), a ‘good enough’ solution may not accurately portray results in population genetics, phylogenetics and forensics, which require accurate SSRs to calculate intra- and inter-species interactions. Results: We present Kmer-SSR, which finds all SSRs faster than most heuristic SSR identification algorithms in a parallelized, easy-to-use manner. The exhaustive Kmer-SSR option has 100% precision and 100% recall and accurately identifies every SSR of any specified length. To identify more biologically pertinent SSRs, we also developed several filters that allow users to easily view a subset of SSRs based on user input. Kmer-SSR, coupled with the filter options, accurately and intuitively identifies SSRs quickly and in a more user-friendly manner than any other SSR identification algorithm. Availability and implementation: The source code is freely available on GitHub at https://github. com/ridgelab/Kmer-SSR.

59 BASIC BIOLOGICAL SCIENCES↗

Parallel String Graph Construction and Transitive Reduction for De Novo Genome Assembly

One of the most computationally intensive tasks in computational biology is de novo genome assembly, the decoding of the sequence of an unknown genome from redundant and erroneous short sequences. A common assembly paradigm identifies overlapping sequences, simplifies their layout, and creates consensus. Despite many algorithms developed in the literature, the efficient assembly of large genomes is still an open problem. In this work, we introduce new distributed-memory parallel algorithms for overlap detection and layout simplification steps of de novo genome assembly, and implement them in the diBELLA 2D pipeline. Our distributed memory algorithms for both overlap detection and layout simplification are based on linear-algebra operations over semirings using 2D distributed sparse matrices. Our layout step consists of performing a transitive reduction from the overlap graph to a string graph. We provide a detailed communication analysis of the main stages of our new algorithms. diBELLA 2D achieves near linear scaling with over 80% parallel efficiency for the human genome, reducing the runtime for overlap detection by 1.2-1.3× for the human genome and 1.5-1.9× for C.elegans compared to the state-of-the-art. Our transitive reduction algorithm outperforms an existing distributed-memory implementation by 10.5-13.3× for the human genome and 18-29× for the C. elegans. Our work paves the way for efficient de novo assembly of large genomes using long reads in distributed memory.

59 BASIC BIOLOGICAL SCIENCES↗

Parallel Visualization of Large-Scale Aerodynamics Calculations: A Case Study on the Cray T3E

This paper reports the performance of a parallel volume rendering algorithm for visualizing a large-scale, unstructured-grid dataset produced by a three-dimensional aerodynamics simulation. This dataset, containing over 18 million tetrahedra, allows us to extend our performance results to a problem which is more than 30 times larger than the one we examined previously. This high resolution dataset also allows us to see fine, three-dimensional features in the flow field. All our tests were performed on the Silicon Graphics Inc. (SGI)/Cray T3E operated by NASA's Goddard Space Flight Center. Using 511 processors, a rendering rate of almost 9 million tetrahedra/second was achieved with a parallel overhead of 26%.

Ma, Kwan-Liu↗

A family of independent Variable Eddington Factor methods with efficient preconditioned iterative solvers

We present a family of discretizations for the Variable Eddington Factor (VEF) equations that have high-order accuracy on curved meshes and efficient preconditioned iterative solvers. The VEF discretizations are combined with the Discontinuous Galerkin transport discretization from to form effective high-order, linear transport methods. The VEF discretizations are derived by extending the unified analysis of Discontinuous Galerkin methods for elliptic problems presented by Arnold et al. to the VEF equations. This framework is used to define analogs of the interior penalty, second method of Bassi and Rebay, minimal dissipation local Discontinuous Galerkin, and continuous finite element methods. The analysis of subspace correction preconditioners, which use a continuous operator to iteratively precondition the discontinuous discretization, is extended to the case of the non-symmetric VEF system. Numerical results demonstrate that the VEF discretizations have arbitrary-order accuracy on curved meshes, preserve the thick diffusion limit, and are effective on a proxy problem from thermal radiative transfer in both outer transport iterations and inner preconditioned linear solver iterations. We demonstrate that the VEF solution converges to the S N transport solution as the mesh is refined on both problems with smooth and non-smooth behavior in angle. Parallel performance studies show that the interior penalty VEF discretization's linear solve weak scales out to 1024 processors and strong scales well on a single node. Particular attention is paid to the parallel performance of the VEF algorithm when used in combination with a parallel block Jacobi transport sweep.

97 MATHEMATICS AND COMPUTING↗

A Non-cooperative Game-based Approach to Distributed Beam Scheduling in Millimeter-Wave Networks

We consider the distributed beam scheduling problem in mm-Wave networks where the base stations may belong to different operators and there is no centralized coordination among them. Our goal is to design distributed beam scheduling algorithms such that the network utility, which is defined as a logarithm function of the average throughput of the user equipment, can be maximized. We propose a non-cooperative game-based scheduling approach where the base stations are modeled as players that greedily maximize their own utilities. The Nash Equilibrium (NE) then provides a distributed solution to the network utility maximization problem. By employing the Lyapunov optimization, the asymptotic optimality of the proposed scheduling can be guaranteed. We prove the existence and provide sufficient conditions which guarantee the uniqueness of the NE by establishing an equivalence to the Variational Inequality (VI) problem. We also propose a parallel power adaptation algorithm which is proved to converge to the NE. Numerical results show the superiority of the proposed scheduling over several distributed baseline schemes.

99 GENERAL AND MISCELLANEOUS↗

Parallel Maximum Cardinality Matchings via Tree-Grafting

This software implements a new algorithm and its shared-memory parallelization for computing maximum cardinality matchings in bipartite graphs. The algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms.

Buluc, Aydin↗

Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs) but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. Here, the key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.

97 MATHEMATICS AND COMPUTING↗

Calculation of exact vibrational spectra for P{sub 2}O and CH{sub 2}NH using a phase space wavelet basis

‘‘Exact” quantum dynamics calculations of vibrational spectra are performed for two molecular systems of widely varying dimensionality (P{sub 2}O and CH{sub 2}NH), using a momentum-symmetrized Gaussian basis. This basis has been previously shown to defeat exponential scaling of computational cost with system dimensionality. The calculations were performed using the new “SWITCHBLADE” black-box code, which utilizes both dimensionally independent algorithms and massive parallelization to compute very large numbers of eigenstates for any fourth-order force field potential, in a single calculation. For both molecules considered here, many thousands of vibrationally excited states were computed, to at least an “intermediate” level of accuracy (tens of wavenumbers). Future modifications to increase the accuracy to “spectroscopic” levels, along with other potential future improvements of the new code, are also discussed.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Status report on SHARP coupling framework.

This report presents the software engineering effort under way at ANL towards a comprehensive integrated computational framework (SHARP) for high fidelity simulations of sodium cooled fast reactors. The primary objective of this framework is to provide accurate and flexible analysis tools to nuclear reactor designers by simulating multiphysics phenomena happening in complex reactor geometries. Ideally, the coupling among different physics modules (such as neutronics, thermal-hydraulics, and structural mechanics) needs to be tight to preserve the accuracy achieved in each module. However, fast reactor cores in steady state mode represent a special case where weak coupling between neutronics and thermal-hydraulics is usually adequate. Our framework design allows for both options. Another requirement for SHARP framework has been to implement various coupling algorithms that are parallel and scalable to large scale since nuclear reactor core simulations are among the most memory and computationally intensive, requiring the use of leadership-class petascale platforms. This report details our progress toward achieving these goals. Specifically, we demonstrate coupling independently developed parallel codes in a manner that does not compromise performance or portability, while minimizing the impact on individual developers. This year, our focus has been on developing a lightweight and loosely coupled framework targeted at UNIC (our neutronics code) and Nek (our thermal hydraulics code). However, the framework design is not limited to just using these two codes.

21 SPECIFIC NUCLEAR REACTORS AND ASSOCIATED PLANTS↗

Impact of new computing systems on computational mechanics and flight-vehicle structures technology

Advances in computer technology which may have an impact on computational mechanics and flight vehicle structures technology were reviewed. The characteristics of supersystems, highly parallel systems, and small systems are summarized. The interrelations of numerical algorithms and software with parallel architectures are discussed. A scenario for future hardware/software environment and engineering analysis systems is presented. Research areas with potential for improving the effectiveness of analysis methods in the new environment are identified.

Noor, A. K.↗