Search NASA⌕ Search

SEARCH · Search NASA

Results for “Vectorized algorithm”

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 739 records · Page 41

A simple parallel prefix algorithm for compact finite-difference schemes

A compact scheme is a discretization scheme that is advantageous in obtaining highly accurate solutions. However, the resulting systems from compact schemes are tridiagonal systems that are difficult to solve efficiently on parallel computers. Considering the almost symmetric Toeplitz structure, a parallel algorithm, simple parallel prefix (SPP), is proposed. The SPP algorithm requires less memory than the conventional LU decomposition and is highly efficient on parallel machines. It consists of a prefix communication pattern and AXPY operations. Both the computation and the communication can be truncated without degrading the accuracy when the system is diagonally dominant. A formal accuracy study was conducted to provide a simple truncation formula. Experimental results were measured on a MasPar MP-1 SIMD machine and on a Cray 2 vector machine. Experimental results show that the simple parallel prefix algorithm is a good algorithm for the compact scheme on high-performance computers.

Sun, Xian-He↗

A collision-selection rule for a particle simulation method suited to vector computers

A theory is developed for a selection rule governing collisions in a particle simulation of rarefied gas-dynamic flows. The selection rule leads to an algorithmic form highly compatible with fine grain parallel decomposition, allowing for efficient utilization of supercomputers having vector or massively parallel single instruction multiple data architectures. A comparison of shock-wave profiles obtained using both the selection rule and Bird's direct simulation Monte Carlo (DSMC) method show excellent agreement. The equation on which the selection rule is based is shown to be directly related to the time-counter procedure in the DSMC method. The results of several example simulations of representative rarefied flows are presented, for which the number of particles used ranged from 10 to the 6th to 10 to the 7th demonstrating the greatly improved computational efficiency of the method.

Baganoff, D.↗

A Parallel Prefix Algorithm for Almost Toeplitz Tridiagonal Systems

A compact scheme is a discretization scheme that is advantageous in obtaining highly accurate solutions. However, the resulting systems from compact schemes are tridiagonal systems that are difficult to solve efficiently on parallel computers. Considering the almost symmetric Toeplitz structure, a parallel algorithm, simple parallel prefix (SPP), is proposed. The SPP algorithm requires less memory than the conventional LU decomposition and is efficient on parallel machines. It consists of a prefix communication pattern and AXPY operations. Both the computation and the communication can be truncated without degrading the accuracy when the system is diagonally dominant. A formal accuracy study has been conducted to provide a simple truncation formula. Experimental results have been measured on a MasPar MP-1 SIMD machine and on a Cray 2 vector machine. Experimental results show that the simple parallel prefix algorithm is a good algorithm for symmetric, almost symmetric Toeplitz tridiagonal systems and for the compact scheme on high-performance computers.

Sun, Xian-He↗

TU-F-CAMPUS-J-03: Elasticity Functions Based On 4DCT Images to Predict Tumor and Normal Tissue Response to Radiation for Patients with Lung Cancers

Purpose: To investigate radiotherapy outcomes by incorporating 4DCT-based physiological and tumor elasticity functions for lung cancer patients. Methods: 4DCT images were acquired from 28 lung SBRT patients before radiation treatment. Deformable image registration (DIR) was performed from the end-inhale to the end-exhale using a B-Spline-based algorithm (Elastix, an open source software package). The resultant displacement vector fields (DVFs) were used to calculate a relative Jacobian function (RV) for each patient. The computed functions in the lung and tumor regions represent lung ventilation and tumor elasticity properties, respectively. The 28 patients were divided into two groups: 16 with two-year tumor local control (LC) and 12 with local failure (LF). The ventilation and elasticity related RV functions were calculated for each of these patients. Results: The LF patients have larger RV values than the LC patients. The mean RV value in the lung region was 1.15 (±0.67) for the LF patients, higher than 1.06 (±0.59) for the LC patients. In the tumor region, the elasticity-related RV values are 1.2 (±0.97) and 0.86 (±0.64) for the LF and LC patients, respectively. Among the 16 LC patients, 3 have the mean RV values greater than 1.0 in the tumors. These tumors were located near the diaphragm, where the displacements are relatively large.. RV functions calculated in the tumor were better correlated with treatment outcomes than those calculated in the lung. Conclusion: The ventilation and elasticity-related RV functions in the lung and tumor regions were calculated from 4DCT image and the resultant values showed differences between the LC and LF patients. Further investigation of the impact of the displacements on the computed RV is warranted. Results suggest that the RV images might be useful for evaluation of treatment outcome for lung cancer patients.

60 APPLIED LIFE SCIENCES↗

Development of iterative techniques for the solution of unsteady compressible viscous flows

Efficient iterative solution methods are being developed for the numerical solution of two- and three-dimensional compressible Navier-Stokes equations. Iterative time marching methods have several advantages over classical multi-step explicit time marching schemes, and non-iterative implicit time marching schemes. Iterative schemes have better stability characteristics than non-iterative explicit and implicit schemes. Thus, the extra work required by iterative schemes can also be designed to perform efficiently on current and future generation scalable, missively parallel machines. An obvious candidate for iteratively solving the system of coupled nonlinear algebraic equations arising in CFD applications is the Newton method. Newton's method was implemented in existing finite difference and finite volume methods. Depending on the complexity of the problem, the number of Newton iterations needed per step to solve the discretized system of equations can, however, vary dramatically from a few to several hundred. Another popular approach based on the classical conjugate gradient method, known as the GMRES (Generalized Minimum Residual) algorithm is investigated. The GMRES algorithm was used in the past by a number of researchers for solving steady viscous and inviscid flow problems with considerable success. Here, the suitability of this algorithm is investigated for solving the system of nonlinear equations that arise in unsteady Navier-Stokes solvers at each time step. Unlike the Newton method which attempts to drive the error in the solution at each and every node down to zero, the GMRES algorithm only seeks to minimize the L2 norm of the error. In the GMRES algorithm the changes in the flow properties from one time step to the next are assumed to be the sum of a set of orthogonal vectors. By choosing the number of vectors to a reasonably small value N (between 5 and 20) the work required for advancing the solution from one time step to the next may be kept to (N+1) times that of a noniterative scheme. Many of the operations required by the GMRES algorithm such as matrix-vector multiplies, matrix additions and subtractions can all be vectorized and parallelized efficiently.

Sankar, Lakshmi N.↗

Solving periodic block tridiagonal systems using the Sherman-Morrison-Woodbury formula

Many algorithms for solving the Navier-Stokes equations require the solution of periodic block tridiagonal systems of equations. By applying a splitting to the matrix representing this system of equations, it may first be reduced to a block tridiagonal matrix plus an outer product of two block vectors. The Sherman-Morrison-Woodbury formula is then applied. The algorithm thus reduces a periodic banded system to a non-periodic banded system with additional right-hand sides and is of higher efficiency than standard Thomas algorithm/LU decompositions.

Yarrow, Maurice↗

HykSort: a new variant of hypercube quicksort on distributed memory architectures. In: ICS '13 Proceedings of the 27th international ACM conference on International conference on supercomputing

In this paper, we present HykSort, an optimized comparison sort for distributed memory architectures that attains more than 2× improvement over bitonic sort and samplesort. The algorithm is based on the hypercube quicksort, but instead of a binary recursion, we perform a k-way recursion in which the pivots are selected accurately with an iterative parallel select algorithm. The single-node sort is performed using a vectorized and multithreaded merge sort. The advantages of HykSort are lower communication costs, better load balancing, and avoidance of O(p)-collective communication primitives. We also present a staged communication samplesort, which is more robust than the original samplesort for large core counts. We conduct an experimental study in which we compare hypercube sort, bitonic sort, the original samplesort, the staged samplesort, and HykSort. We report weak and strong scaling results and study the effect of the grain size. It turns out that no single algorithm performs best and a hybridization strategy is necessary. As a highlight of our study, on our largest experiment on 262,144 AMD cores of the CRAY XK7 "Titan" platform at the Oak Ridge National Laboratory we sorted 8 trillion 32-bit integer keys in 37 seconds achieving 0.9TB/s effective throughput.

Sundar, Hari↗

On the dosimetric effect and reduction of inverse consistency and transitivity errors in deformable image registration for dose accumulation

Purpose: Deformable image registration (DIR) is necessary for accurate dose accumulation between multiple radiotherapy image sets. DIR algorithms can suffer from inverse and transitivity inconsistencies. When using deformation vector fields (DVFs) that exhibit inverse-inconsistency and are nontransitive, dose accumulation on a given image set via different image pathways will lead to different accumulated doses. The purpose of this study was to investigate the dosimetric effect of and propose a postprocessing solution to reduce inverse consistency and transitivity errors. Methods: Four MVCT images and four phases of a lung 4DCT, each with an associated calculated dose, were selected for analysis. DVFs between all four images in each data set were created using the Fast Symmetric Demons algorithm. Dose was accumulated on the fourth image in each set using DIR via two different image pathways. The two accumulated doses on the fourth image were compared. The inverse consistency and transitivity errors in the DVFs were then reduced. The dose accumulation was repeated using the processed DVFs, the results of which were compared with the accumulated dose from the original DVFs. To evaluate the influence of the postprocessing technique on DVF accuracy, the original and processed DVF accuracy was evaluated on the lung 4DCT data on which anatomical landmarks had been identified by an expert. Results: Dose accumulation to the same image via different image pathways resulted in two different accumulated dose results. After the inverse consistency errors were reduced, the difference between the accumulated doses diminished. The difference was further reduced after reducing the transitivity errors. The postprocessing technique had minimal effect on the accuracy of the DVF for the lung 4DCT images. Conclusions: This study shows that inverse consistency and transitivity errors in DIR have a significant dosimetric effect in dose accumulation; Depending on the image pathway taken to accumulate the dose, different results may be obtained. A postprocessing technique that reduces inverse consistency and transitivity error is presented, which allows for consistent dose accumulation regardless of the image pathway followed.

61 RADIATION PROTECTION AND DOSIMETRY↗

A multigrid algorithm for steady transonic potential flows around aerofoils using Newton iteration

The application of multigrid relaxation to transonic potential flow calculation was investigated. Conservative potential flows around aerofoils were taken as test problems. The solution algorithm was based on Newton iteration. It was found that the iteration to the circulation has to be kept outside the multigrid algorithm. To obtain meaningful norms of residuals, difference formulas with asymptotic scaling were introduced. Nonlinear instability problems were solved by upwind differencing using mass flux vector splitting instead of artificial viscosity or artificial density. It is suggested that the algorithms efficiency be increased by improving the iteration on the shock positions even though this is a highly nonlinear process.

Boestoel, J. W.↗

Control system design for flexible structures using data models

The dynamics and control of flexible aerospace structures exercises many of the engineering disciplines. In recent years there has been considerable research in the developing and tailoring of control system design techniques for these structures. This problem involves designing a control system for a multi-input, multi-output (MIMO) system that satisfies various performance criteria, such as vibration suppression, disturbance and noise rejection, attitude control and slewing control. Considerable progress has been made and demonstrated in control system design techniques for these structures. The key to designing control systems for these structures that meet stringent performance requirements is an accurate model. It has become apparent that theoretically and finite-element generated models do not provide the needed accuracy; almost all successful demonstrations of control system design techniques have involved using test results for fine-tuning a model or for extracting a model using system ID techniques. This paper describes past and ongoing efforts at Ohio University and NASA MSFC to design controllers using 'data models.' The basic philosophy of this approach is to start with a stabilizing controller and frequency response data that describes the plant; then, iteratively vary the free parameters of the controller so that performance measures become closer to satisfying design specifications. The frequency response data can be either experimentally derived or analytically derived. One 'design-with-data' algorithm presented in this paper is called the Compensator Improvement Program (CIP). The current CIP designs controllers for MIMO systems so that classical gain, phase, and attenuation margins are achieved. The center-piece of the CIP algorithm is the constraint improvement technique which is used to calculate a parameter change vector that guarantees an improvement in all unsatisfied, feasible performance metrics from iteration to iteration. The paper also presents a recently demonstrated CIP-type algorithm, called the Model and Data Oriented Computer-Aided Design System (MADCADS), developed for achieving H(sub infinity) type design specifications using data models. Control system design for the NASA/MSFC Single Structure Control Facility are demonstrated for both CIP and MADCADS. Advantages of design-with-data algorithms over techniques that require analytical plant models are also presented.

Irwin, R. Dennis↗

Algorithms and software for nonlinear structural dynamics

The objective of this research is to develop efficient methods for explicit time integration in nonlinear structural dynamics for computers which utilize both concurrency and vectorization. As a framework for these studies, the program WHAMS, which is described in Explicit Algorithms for the Nonlinear Dynamics of Shells (T. Belytschko, J. I. Lin, and C.-S. Tsay, Computer Methods in Applied Mechanics and Engineering, Vol. 42, 1984, pp 225 to 251), is used. There are two factors which make the development of efficient concurrent explicit time integration programs a challenge in a structural dynamics program: (1) the need for a variety of element types, which complicates the scheduling-allocation problem; and (2) the need for different time steps in different parts of the mesh, which is here called mixed delta t integration, so that a few stiff elements do not reduce the time steps throughout the mesh.

Belytschko, Ted↗

Machine learning for arbitrary single-qubit rotations on an embedded device

Here, in this study, we present a technique for using machine learning (ML) for single-qubit gate synthesis on field-programmable logic for a superconducting transmon-based quantum computer based on simulated studies. Our approach is multi-stage. We first “bootstrap” a model based on simulation with access to the full state vector for measuring gate fidelity. We next present an algorithm, named adapted randomized benchmarking (ARB), for fine-tuning the gate on hardware based on measurements of the devices. We also present techniques for deploying the model on programmable devices with care to reduce the required resources. While the techniques here are applied to a transmon-based computer, many of them are portable to other architectures.

97 MATHEMATICS AND COMPUTING↗

Prediction model of potential hepatocarcinogenicity of rat hepatocarcinogens using a large-scale toxicogenomics database

The present study was performed to develop a robust gene-based prediction model for early assessment of potential hepatocarcinogenicity of chemicals in rats by using our toxicogenomics database, TG-GATEs (Genomics-Assisted Toxicity Evaluation System developed by the Toxicogenomics Project in Japan). The positive training set consisted of high- or middle-dose groups that received 6 different non-genotoxic hepatocarcinogens during a 28-day period. The negative training set consisted of high- or middle-dose groups of 54 non-carcinogens. Support vector machine combined with wrapper-type gene selection algorithms was used for modeling. Consequently, our best classifier yielded prediction accuracies for hepatocarcinogenicity of 99% sensitivity and 97% specificity in the training data set, and false positive prediction was almost completely eliminated. Pathway analysis of feature genes revealed that the mitogen-activated protein kinase p38- and phosphatidylinositol-3-kinase-centered interactome and the v-myc myelocytomatosis viral oncogene homolog-centered interactome were the 2 most significant networks. The usefulness and robustness of our predictor were further confirmed in an independent validation data set obtained from the public database. Interestingly, similar positive predictions were obtained in several genotoxic hepatocarcinogens as well as non-genotoxic hepatocarcinogens. These results indicate that the expression profiles of our newly selected candidate biomarker genes might be common characteristics in the early stage of carcinogenesis for both genotoxic and non-genotoxic carcinogens in the rat liver. Our toxicogenomic model might be useful for the prospective screening of hepatocarcinogenicity of compounds and prioritization of compounds for carcinogenicity testing. - Highlights: >We developed a toxicogenomic model to predict hepatocarcinogenicity of chemicals. >The optimized model consisting of 9 probes had 99% sensitivity and 97% specificity. >This model enables us to detect genotoxic as well as non-genotoxic hepatocarcinogens.

60 APPLIED LIFE SCIENCES↗

High Energy Electromagnetic Particle Transportation on the GPU

We present massively parallel high energy electromagnetic particle transportation through a finely segmented detector on a Graphics Processing Unit (GPU). Simulating events of energetic particle decay in a general-purpose high energy physics (HEP) detector requires intensive computing resources, due to the complexity of the geometry as well as physics processes applied to particles copiously produced by primary collisions and secondary interactions. The recent advent of hardware architectures of many-core or accelerated processors provides the variety of concurrent programming models applicable not only for the high performance parallel computing, but also for the conventional computing intensive application such as the HEP detector simulation. The components of our prototype are a transportation process under a non-uniform magnetic field, geometry navigation with a set of solid shapes and materials, electromagnetic physics processes for electrons and photons, and an interface to a framework that dispatches bundles of tracks in a highly vectorized manner optimizing for spatial locality and throughput. Core algorithms and methods are excerpted from the Geant4 toolkit, and are modified and optimized for the GPU application. Program kernels written in C/C++ are designed to be compatible with CUDA and OpenCL and with the aim to be generic enough for easy porting to future programming models and hardware architectures. To improve throughput by overlapping data transfers with kernel execution, multiple CUDA streams are used. Issues with floating point accuracy, random numbers generation, data structure, kernel divergences and register spills are also considered. Performance evaluation for the relative speedup compared to the corresponding sequential execution on CPU is presented as well.

Canal, P.↗

SU-F-J-84: Comparison of Quantitative Deformable Image Registration Evaluation Tools: Application to Prostate IGART

Purpose: Errors in displacement vector fields (DVFs) generated by Deformable Image Registration (DIR) algorithms can give rise to significant uncertainties in contour propagation and dose accumulation in Image-Guided Adaptive Radiotherapy (IGART). The purpose of this work is to assess the accuracy of two DIR algorithms using a variety of quality metrics for prostate IGART. Methods: Pelvic CT images were selected from an anonymized database of nineteen prostate patients who underwent 8–12 serial scans during radiotherapy. Prostate, bladder, and rectum were contoured on 34 image-sets for three patients by the same physician. The planning CT was deformably-registered to daily CT using three variants of the Small deformation Inverse Consistent Linear Elastic (SICLE) algorithm: Grayscale-driven (G), Contour-driven (C, which utilizes segmented structures to drive DIR), combined (G+C); and also grayscale ITK demons (Gd). The accuracy of G, C, G+C SICLE and Gd registrations were evaluated using a new metric Edge Gradient Distance to Agreement (EGDTA) and other commonly-used metrics such as Pearson Correlation Coefficient (PCC), Dice Similarity Index (DSI) and Hausdorff Distance (HD). Results: C and G+C demonstrated much better performance at organ boundaries, revealing the lowest HD and highest DSI, in prostate, bladder and rectum. G+C demonstrated the lowest mean EGDTA (1.14 mm), which corresponds to highest registration quality, compared to G and C DVFs (1.16 and 2.34 mm). However, demons DIR showed the best overall performance, revealing lowest EGDTA (0.73 mm) and highest PCC (0.85). Conclusion: As expected, both C- and C+G SICLE more accurately reproduce manually-contoured target datasets than G-SICLE or Gd using HD and DSI metrics. In general, the Gd appears to have difficulty reproducing large daily position and shape changes in the rectum and bladder. However, Gd outperforms SICLE in terms of EGDTA and PCC metrics, possibly at the expense of topological quality of the estimated DVFs.

60 APPLIED LIFE SCIENCES↗

Reducing Operator Complexity of Galerkin Coarse-grid Operators with Machine Learning

Here, we propose a data-driven and machine-learning-based approach to compute non-Galerkin coarse-grid operators in multigrid (MG) methods, addressing the well-known issue of increasing operator complexity. Guided by the MG theory on spectrally equivalent coarse-grid operators, we have developed novel machine learning algorithms that utilize neural networks combined with smooth test vectors from multigrid eigenvalue problems. The proposed method demonstrates promise in reducing the complexity of coarse-grid operators while maintaining overall MG convergence for solving parametric partial differential equation problems. Numerical experiments on anisotropic rotated Laplacian and linear elasticity problems are provided to showcase the performance and comparison with existing methods for computing non-Galerkin coarse-grid operators.

97 MATHEMATICS AND COMPUTING↗

Responsive Assistant For Navigating And Guiding Engineering With Rigor (ranger)

The bot uses the GitHub API to fetch discussions from a MOOSE repository and store the data in a vector database. When a new discussion is initiated, the algorithm compares the discussion title with the content of all previous discussions (title + discussions) in the database and provides the most relevant posts to the user. The database is updated regularly to include all new posts, potentially on a monthly basis.

Li, Mengnan [Idaho National Laboratory (INL), Idah↗

Computing Angular Distributions from Simulation Data

The essential idea of this algorithm is to compute the angular distribution of a vector quantity, then create an informative image. In our example, we will compute the angular distribution of linear momentum from an xRage simulation of an exploding shaped charge. We will then explore one possible method for adding information to the resulting image.

97 MATHEMATICS AND COMPUTING↗