Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “parallelize algorithm computation”

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 505 records · Page 28
All sourcesNASA NTRSDOE OSTI
NASA NTRS1994

Design and implementation of a parallel unstructured Euler solver using software primitives

This paper is concerned with the implementation of a three-dimensional unstructured-grid Euler solver on massively parallel distributed-memory computer architectures. The goal is to minimize solution time by achieving high computational rates with a numerically efficient algorithm. An unstructured multigrid algorithm with an edge-based data structure has been adopted, and a number of optimizations have been devised and implemented to accelerate the parallel computational rates. The implementation is carried out by creating a set of software tools, which provide an interface between the parallelization issues and the sequential code, while providing a basis for future automatic run-time compilation support. Large practical unstructured grid problems are solved on the Intel iPSC/860 hypercube and Intel Touchstone Delta machine. The quantitative effects of the various optimizations are demonstrated, and we show that the combined effect of these optimizations leads to roughly a factor of 3 performance improvement. The overall solution efficiency is compared with that obtained on the Cray Y-MP vector supercomputer.

Das, R.↗
DOE OSTI2014

Parallel processing of filtered queries in attributed semantic graphs

Execution of complex analytic queries on massive semantic graphs is a challenging problem in big-data analytics that requires high-performance parallel computing. In a semantic graph, vertices and edges carry attributes of various types and the analytic queries typically depend on the values of these attributes. Thus, the computation must view the graph through a filter that passes only those individual vertices and edges of interest. Previous investigations have developed Knowledge Discovery Toolbox (KDT), a sophisticated Python library for parallel graph computations. In KDT, the user can write custom graph algorithms by specifying operations between edges and vertices ( semiring operations ). The user can also customize existing graph algorithms by writing filters. While the high-level language for this customization enables domain scientists to productively express their graph analytics requirements, the customized queries perform poorly due to the overhead of having to call into the Python virtual machine for each vertex and edge. In this work, we use the Selective Embedded Just-In-Time Specialization (SEJITS) approach to automatically translate semiring operations and filters defined by programmers into a lower-level efficiency language, bypassing the upcall into Python. We evaluate our approach by comparing it with the high-performance Combinatorial BLAS engine and show that our approach combines the benefits of programming in a high-level language with executing in a low-level parallel environment. We increase the system's flexibility by developing techniques that provide users with the ability to define new vertex and edge types from Python. We also present a new Roofline model for graph traversals and show that we achieve performance that is significantly closer to the bounds suggested by the Roofline. Finally, to further understand the complex interaction with the underlying architecture, we present an analysis using performance counters that quantifies the improvement in hardware behavior in the context our SEJITS methodology. Comprehensively, we demonstrate the first known solution to the problem of obtaining high performance from a productivity language when applying graph algorithms selectively on semantic graphs with hundreds of millions of edges and scaling to thousands of processors for graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

An Efficient Parallel-in-Time Method for Optimization with Parabolic PDEs

To solve optimization problems with parabolic PDE constraints, often methods working on the reduced objective functional are used. They are computationally expensive due to the necessity of solving both the state equation and a backward-in-time adjoint equation to evaluate the reduced gradient in each iteration of the optimization method. In this study, we investigate the use of the parallel-in-time method PFASST in the setting of PDE-constrained optimization. In order to develop an efficient fully time-parallel algorithm, we discuss different options for applying PFASST to adjoint gradient computation, including the possibility of doing PFASST iterations on both the state and the adjoint equations simultaneously. Here, we also explore the additional gains in efficiency from reusing information from previous optimization iterations when solving each equation. Numerical results for both a linear and a nonlinear reaction-diffusion optimal control problem demonstrate the parallel speedup and efficiency of different approaches.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

A generalized reconstruction framework for unconventional PET systems

Purpose: Quantitative estimation of the radionuclide activity concentration in positron emission tomography (PET) requires precise modeling of PET physics. The authors are focused on designing unconventional PET geometries for specific applications. This work reports the creation of a generalized reconstruction framework, capable of reconstructing tomographic PET data for systems that use right cuboidal detector elements positioned at arbitrary geometry using a regular Cartesian grid of image voxels. Methods: The authors report on a variety of design choices and optimization for the creation of the generalized framework. The image reconstruction algorithm is maximum likelihood-expectation–maximization. System geometry can be specified using a simple script. Given the geometry, a symmetry seeking algorithm finds existing symmetry in the geometry with respect to the image grid to improve the memory usage/speed. Normalization is approached from a geometry independent perspective. The system matrix is computed using the Siddon’s algorithm and subcrystal approach. The program is parallelized through open multiprocessing and message passing interface libraries. A wide variety of systems can be modeled using the framework. This is made possible by modeling the underlying physics and data correction, while generalizing the geometry dependent features. Results: Application of the framework for three novel PET systems, each designed for a specific application, is presented to demonstrate the robustness of the framework in modeling PET systems of unconventional geometry. Three PET systems of unconventional geometry are studied. (1) Virtual-pinhole half-ring insert integrated into Biograph-40: although the insert device improves image quality over conventional whole-body scanner, the image quality varies depending on the position of the insert and the object. (2) Virtual-pinhole flat-panel insert integrated into Biograph-40: preliminary results from an investigation into a modular flat-panel insert are presented. (3) Plant PET system: a reconfigurable PET system for imaging plants, with resolution of greater than 3.3 mm, is shown. Using the automated symmetry seeking algorithm, the authors achieved a compression ratio of the storage and memory requirement by a factor of approximately 50 for the half-ring and flat-panel systems. For plant PET system, the compression ratio is approximately five. The ratio depends on the level of symmetry that exists in different geometries. Conclusions: This work brings the field closer to arbitrary geometry reconstruction. A generalized reconstruction framework can be used to validate multiple hypotheses and the effort required to investigate each system is reduced. Memory usage/speed can be improved with certain optimizations.

60 APPLIED LIFE SCIENCES↗
NASA NTRS1992

Distance between images

Comparing two binary images and assigning a quantitative measure to this comparison finds its purpose in such tasks as image recognition, image compression, and image browsing. This quantitative measurement may be computed by utilizing the Hausdorff distance of the images represented as two-dimensional point sets. In this paper, we review two algorithms that have been proposed to compute this distance, and we present a parallel implementation of one of them on the MasPar parallel processor. We study their complexity and the results obtained by these algorithms for two different types of images: a set of displaced pairs of images of Gaussian densities, and a comparison of a Canny edge image with several edge images from a hierarchical region growing code.

Gualtieri, J. A.↗
NASA NTRS2001

Hiding the Disk and Network Latency of Out-of-Core Visualization

This paper describes an algorithm that improves the performance of application-controlled demand paging for out-of-core visualization by hiding the latency of reading data from both local disks or disks on remote servers. The performance improvements come from better overlapping the computation with the page reading process, and by performing multiple page reads in parallel. The paper includes measurements that show that the new multithreaded paging algorithm decreases the time needed to compute visualizations by one third when using one processor and reading data from local disk. The time needed when using one processor and reading data from remote disk decreased by two thirds. Visualization runs using data from remote disk actually ran faster than ones using data from local disk because the remote runs were able to make use of the remote server's high performance disk array.

Ellsworth, David↗
DOE OSTI2025

Practical Implementation of GPU-based Computing at the Grid Edge for Resilience Scenarios

This paper presents a practical implementation of GPU-accelerated computing at the grid edge to enhance power system resilience through next-generation smart meters. Advanced Metering Infrastructure (AMI) systems rely predominantly on centralized processing architectures, which limit real-time response capabilities during grid disturbances. This work proposes the integration of GPU-enabled computational platforms directly within smart meter to enable local execution support for power system analytics, fault detection algorithms, and optimization routines. The proposed framework uses the Julia programming language to leverage highperformance parallel computing capabilities while maintaining code portability and development efficiency. We use two experimental scenarios to benchmark the computational feasibility of this approach: sparse linear system solutions representative of power flow analyses, and multi-stage production cost simulations incorporating unit commitment and economic dispatch operations. Results demonstrate that computationally intensive power system algorithms, such as those supporting resilience scenario calculations, can be effectively executed at the distribution edge using commercially available embedded GPU hardware. Keywords—GPU acceleration, edge computing, smart meters, grid resilience, AMI, resilience.

De Souza, Reubun [School of Electrical Engineering↗
NASA NTRS1993

Algorithmic trends in computational fluid dynamics; The Institute for Computer Applications in Science and Engineering (ICASE)/LaRC Workshop, NASA Langley Research Center, Hampton, VA, US, Sep. 15-17, 1991

The purpose here is to assess the state of the art in the areas of numerical analysis that are particularly relevant to computational fluid dynamics (CFD), to identify promising new developments in various areas of numerical analysis that will impact CFD, and to establish a long-term perspective focusing on opportunities and needs. Overviews are given of discretization schemes, computational fluid dynamics, algorithmic trends in CFD for aerospace flow field calculations, simulation of compressible viscous flow, and massively parallel computation. Also discussed are accerelation methods, spectral and high-order methods, multi-resolution and subcell resolution schemes, and inherently multidimensional schemes.

Hussaini, M. Y.↗
NASA NTRS1993

Transient Finite Element Computations on a Variable Transputer System

A parallel program to analyze transient finite element problems was written and implemented on a system of transputer processors. The program uses the explicit time integration algorithm which eliminates the need for equation solving, making it more suitable for parallel computations. An interprocessor communication scheme was developed for arbitrary two dimensional grid processor configurations. Several 3-D problems were analyzed on a system with a small number of processors.

Smolinski, Patrick J.↗
DOE OSTI2016

An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling

Here, we present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factoriz ation leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to 7 fold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-of-the-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK - STRUctured Matrices PACKage, which also has a distributed memory component for dense rank-structured matrices.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Towards scaling community detection on distributed-memory heterogeneous systems

Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. Graph algorithms are generally characterized by irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. Graph community detection is an important problem in the emerging domain of graph analytics with numerous applications. In this paper, we present our ongoing work on distributed-memory multi-GPU implementation for graph community detection. Our work parallelizes the widely used (albeit serial) Louvain method on distributed multi-GPU platforms. Supported by an extensive set of experiments on a multi-GPU enabled supercomputer (OLCF Summit) and a single compute node (Nvidia DGX-2®), we demonstrate competitive performance to existing distributed-memory CPU-based implementation, and up to 6.5 better results than Nvidia RAPIDS® CUGRAPH. To the best of our knowledge, this work represents the first effort for community detection on distributed multi-GPU systems. Our approach and related findings can be extended to numerous other iterative graph algorithms on multi-GPU systems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1986

Experimental Parallel-Processing Computer

Master processor supervises slave processors, each with its own memory. Computer with parallel processing serves as inexpensive tool for experimentation with parallel mathematical algorithms. Speed enhancement obtained depends on both nature of problem and structure of algorithm used. In parallel-processing architecture, "bank select" and control signals determine which one, if any, of N slave processor memories accessible to master processor at any given moment. When so selected, slave memory operates as part of master computer memory. When not selected, slave memory operates independently of main memory. Slave processors communicate with each other via input/output bus.

Mcgregor, J. W.↗
DOE OSTI2016

Recommended direct simulation Monte Carlo collision model parameters for modeling ionized air transport processes

A systematic approach for calibrating the direct simulation Monte Carlo (DSMC) collision model parameters to achieve consistency in the transport processes is presented. The DSMC collision cross section model parameters are calibrated for high temperature atmospheric conditions by matching the collision integrals from DSMC against ab initio based collision integrals that are currently employed in the Langley Aerothermodynamic Upwind Relaxation Algorithm (LAURA) and Data Parallel Line Relaxation (DPLR) high temperature computational fluid dynamics solvers. The DSMC parameter values are computed for the widely used Variable Hard Sphere (VHS) and the Variable Soft Sphere (VSS) models using the collision-specific pairing approach. The recommended best-fit VHS/VSS parameter values are provided over a temperature range of 1000-20 000 K for a thirteen-species ionized air mixture. Use of the VSS model is necessary to achieve consistency in transport processes of ionized gases. The agreement of the VSS model transport properties with the transport properties as determined by the ab initio collision integral fits was found to be within 6% in the entire temperature range, regardless of the composition of the mixture. The recommended model parameter values can be readily applied to any gas mixture involving binary collisional interactions between the chemical species presented for the specified temperature range.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1974

A note on parallel and pipeline computation of fast unitary transforms

The parallel and pipeline organization of fast unitary transform algorithms such as the Fast Fourier Transform are discussed. The efficiency is pointed out of a combined parallel-pipeline processor of a transform such as the Haar transform in which 2 to the n minus 1 power hardware butterflies generate a transform of order 2 to the n power every computation cycle.

Fino, B. J.↗
NASA NTRS1992

The design and implementation of a parallel unstructured Euler solver using software primitives

This paper is concerned with the implementation of a 3D unstructured-grid Euler-solver on massively parallel distributed-memory computer architectures. The goal is to minimize solution time by achieving high computational rates with a numerically efficient algorithm. An unstructured multigrid algorithm with an edge-based data-structure has been adopted, and a number of optimizations have been devised and implemented in order to accelerate the parallel computational rates. The implementation is carried out by creating a set of software tools, which ease the implementation of computational problems on parallel architecture machines by relieving the user of the low-level machine specific issues. The quantitative effect of the various optimizations are demonstrated, and we show that the combined effect of these optimizations leads to roughly a factor of three performance improvement. The overall solution efficiency is compared with that obtained on the CRAY-YMP vector supercomputer.

Das, R.↗
NASA NTRS1994

3D Electromagnetic Plasma Particle Simulations on the Intel Delta Parallel Computer

A three-dimensional electromagnetic PIC code has been developed on the 512 node Intel Touchstone Delta MIMD parallel computer. This code is based on the General Concurrent PIC algorithm which uses a domain decomposition to divide the computation among the processors. The 3D simulation domain can be partitioned into 1-, 2-, or 3-dimensional subdomains. Particles must be exchanged between processors as they move among the subdomains.

PIC↗
DOE OSTI2015

A Framework to Analyze the Performance of Load Balancing Schemes for Ensembles of Stochastic Simulations

Ensembles of simulations are employed to estimate the statistics of possible future states of a system, and are widely used in important applications such as climate change and biological modeling. Ensembles of runs can naturally be executed in parallel. However, when the CPU times of individual simulations vary considerably, a simple strategy of assigning an equal number of tasks per processor can lead to serious work imbalances and low parallel efficiency. This paper presents a new probabilistic framework to analyze the performance of dynamic load balancing algorithms for ensembles of simulations where many tasks are mapped onto each processor, and where the individual compute times vary considerably among tasks. Four load balancing strategies are discussed: most-dividing, all-redistribution, random-polling, and neighbor-redistribution. Simulation results with a stochastic budding yeast cell cycle model are consistent with the theoretical analysis. It is especially significant that there is a provable global decrease in load imbalance for the local rebalancing algorithms due to scalability concerns for the global rebalancing algorithms. The overall simulation time is reduced by up to 25 %, and the total processor idle time by 85 %.

ALGORITHMS↗