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 307 records · Page 17

Data-Parallel Halo Finder Operator in PISTON

PISTON is a portable framework which supports the development of visualization and analysis operators using a platform-independent, data-parallel programming model. Operators such as isosurface, cut-surface and threshold have been implemented in this framework, with the exact same operator code achieving good parallel performance on different architectures. An important analysis operator in cosmology is the halo finder. A halo is a cluster of particles and is considered a common feature of interest found in cosmology data. As the number of cosmological simulations carried out in the recent past has increased, the resultant data of these simulations and the required analysis tasks have increased as well. As a consequence, there is a need to develop scalable and efficient tools to carry out the needed analysis. Therefore, we are currently implementing a halo finder operator using PISTON. Researchers have developed a wide variety of techniques to identify halos in raw particle data. The most basic algorithm is the friend-of-friends (FOF) halo finder, where the particles are clustered based on two parameters: linking length and halo size. In a FOF halo finder, all particles which lie within the linking length are considered as one halo and the halos are filtered based on the halo size parameter. A naive implementation of a FOF halo finder compares each and every particle pair, requiring O(n{sup 2}) operations. Our data-parallel halo finder operator uses a balanced k-d tree to reduce this number of operations in the average case, and implements the algorithm using only the data-parallel primitives in order to achieve portability and performance.

79 ASTRONOMY AND ASTROPHYSICS↗

Visual language recognition with a feed-forward network of spiking neurons

An analogy is made and exploited between the recognition of visual objects and language parsing. A subset of regular languages is used to define a one-dimensional 'visual' language, in which the words are translational and scale invariant. This allows an exploration of the viewpoint invariant languages that can be solved by a network of concurrent, hierarchically connected processors. A language family is defined that is hierarchically tiling system recognizable (HREC). As inspired by nature, an algorithm is presented that constructs a cellular automaton that recognizes strings from a language in the HREC family. It is demonstrated how a language recognizer can be implemented from the cellular automaton using a feed-forward network of spiking neurons. This parser recognizes fixed-length strings from the language in parallel and as the computation is pipelined, a new string can be parsed in each new interval of time. The analogy with formal language theory allows inferences to be drawn regarding what class of objects can be recognized by visual cortex operating in purely feed-forward fashion and what class of objects requires a more complicated network architecture.

99 GENERAL AND MISCELLANEOUS↗

A Comparison of Shared Memory Parallel Programming Models

The dominant parallel programming models for shared memory computers, Pthreads and OpenMP, are both thread-centric in that they are based on explicit management of tasks and enforce data dependencies and output ordering through task management. By comparison, the Cray XMT programming model is data-centric where the primary concern of the programmer is managing data dependencies, allowing threads to progress in a data flow fashion. The XMT implements this programming model by associating tag bits with each word of memory, affording efficient fine grained data synchronization independent of the number of processors or how tasks are scheduled. When task management is implicit and synchronization is abundant, efficient, and easy to use, programmers have viable alternatives to traditional thread-centric algorithms. In this paper we compare the amount of available parallelism relative to the amount of work in a variety of different algorithms and data structures when synchronization does not need to be rationed, as well as identify opportunities for platform and performance portability of the data-centric programming model on multi-core processors.

99 GENERAL AND MISCELLANEOUS↗

A memory-distributed quasi-Newton solver for nonlinear programming problems with a small number of general constraints

We approach the problem of parallelizing state-of-the-art nonlinear programming optimization algorithms.Specifically, we focus on parallelizing quasi-Newton interior-point methods that use limited-memory secant Hessian approximations. Such interior-point methods are known to have better convergence properties and to be more effective on large-scale problems than gradient-based and derivative-free optimization algorithms. We target nonlinear and potentially nonconvex optimization problems with an arbitrary number of bound constraints and a small number of general equality and inequality constraints on the optimization variables. These problems occur for example in the form of optimal control, optimal design, and inverse problems governed by ordinary or partial differential equations, whenever they are expressed in a “reduced-space” optimization approach. We introduce and analyze the time and space complexity of a decomposition method for solving the quasi-Newton linear systems that leverages the fact that the quasi-Newton Hessian matrix has a small number of dense blocks that border a low-rank update of a diagonal matrix. This enables an efficient parallelization on memory-distributed computers of the iterations of the optimization algorithm, a state-of-the-art filter line-search interior-point algorithm by Wächter et. al. We illustrate the efficiency of the proposed method by solving structural topology optimization problems on up to 4608 cores on a parallel machine.

97 MATHEMATICS AND COMPUTING↗

Synchronization-Avoiding Graph Algorithms

Because they were developed for optimal sequential complexity, classical graph algorithms as found in textbooks have strictly-defined orders of operations. Enforcing a prescribed order of operations, or even an approximate order, in a distributed memory setting requires significant amounts of synchronization, which in turn can severely limit scalability. As a result, new algorithms are typically required to achieve scalable performance, even for solving well-known graph problems. Yet, even in these cases, parallel graph algorithms are written according to parallel programming models that evolved for, e.g., scientific computing, and that still have inherent, and scalability-limiting, amounts of synchronization. In this paper we present a new approach to parallel graph algorithms: synchronization-avoiding algorithms. To eliminate synchronization and its associated overhead, synchronization-avoiding algorithms perform work in an unordered and fully asynchronous fashion in such a way that the result is constantly refined toward its final state. “Wasted” work is minimized by locally prioritizing tasks using problem-dependent task utility metrics. We classify algorithms for graph applications into two broad categories: algorithms with monotonic updates (which evince global synchronization) and algorithms with nonmonotonic updates (which evince vertex-centric synchronization). We apply our approach to both classes and develop novel, synchronization-avoiding algorithms for solving exemplar problems: SSSP and connected components for the former, graph coloring for the latter. We demonstrate that eliminating synchronization in conjunction with effective scheduling policies and optimizations in the runtime results in improved scalability for both classes of algorithms.

Firoz, Jesun S.↗

Multi-node and Multi-core Performance Studies of a Monte Carlo code RMC

Over the past 15 years the architecture of high-performance computing systems has become increasingly heterogeneous with individual computing cores being subdivided into nodes and even auxiliary co-processing units such as graphics processing units or the Intel many integrated core co-processors. In fact, future computer platforms is moving toward a larger number of nodes and cores with lower memory available per node. Today, several production Monte Carlo codes use some types of hybrid parallelism strategy that makes use of shared-memory parallelism within a computing node and message-passing parallelism between nodes, which enables the codes to utilize available computing resources as much as possible, both among and within computing nodes on a cluster. The so-called hybrid parallelization is also possible with Reactor Monte Carlo Code RMC by activating both MPI and OpenMP parallel algorithms together. On HPC' which typically consists of several or several-ten thousand nodes equipping 16-32 computing intra-cores per node, simulation of RMC can be carried out in the hybrid parallelization with the MPI inter-node parallelization and the OpenMP intra-node parallelization. RMC has adopted a hybrid message-passing and shared-memory approach to parallelism, which enables the code to utilize available computing resources, both among and within computing nodes on a cluster. Shared-memory parallelism is especially valuable for large-model simulations because it enables multiple compute cores within a node to share common model information such as the geometry description, material, cross section and tally data, thus reducing the memory usage per processor. The calculation on the Tianhe-2 supercomputer took 6144 cores, resulting in a rate of 173,314,000 neutrons/minute for BEAVRS benchmark. While pin-wise full core H-M benchmark burnup calculations with millions of depletion regions was selected using MPI/OpenMP parallelism, the speed of 6,144 cores reach 1,843,200 burnable regions per minute. Keeping up with the continuing trend for increases in the number of computing resources within modern HPC systems is a significant challenge for teams that develop and maintain high-performance MC radiation transport solvers. order to address this challenge, RMC has adopted a hybrid message-passing and shared-memory approach to parallelism, which enables the code to utilize available computing resources, both among and within computing nodes on a cluster. Shared-memory parallelism is especially valuable for large-model simulations because it enables multiple compute cores within a node to share common model information such as the geometry description, material and composition definitions, and cross section data, thus reducing the memory usage per processor. The parallel performance has been studied by using two complex and representative benchmarks, H-M and BEAVRS benchmark. All simulations were run on Intel Xeon E5-2692 12 core, 2.2 GHz processors at MilkyWay-2 Super Computer with up to 12,288 available computing cores. While employing MPI parallelism, excellent parallel efficiency is achieved even above 12,000 processors and RMC reaches the parallel efficiency of 96% on 12,288 cores for the pin-by-pin computation of the BEAVRS benchmark. While BEAVRS criticality benchmark was selected using MPI/OpenMP parallelism, the speed of 6,144 cores reach 173,314,000 particles per minute. While pin-wise full core H-M benchmark burnup calculations with millions of depletion regions was selected using MPI/OpenMP parallelism, the speed of 6,144 cores reach 1,843,200 burnable regions per minute. Results from these studies demonstrate that RMC, using the hybrid parallel model described in this paper, is able to handle pin-wise full core burnup calculations with millions of depletion regions and scales well through thousands of processors. (authors)

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

MPI-hybrid Parallelism for Volume Rendering on Large, Multi-core Systems

This work studies the performance and scalability characteristics of"hybrid'" parallel programming and execution as applied to raycasting volume rendering -- a staple visualization algorithm -- on a large, multi-core platform. Historically, the Message Passing Interface (MPI) has become the de-facto standard for parallel programming and execution on modern parallel systems. As the computing industry trends towards multi-core processors, with four- and six-core chips common today and 128-core chips coming soon, we wish to better understand how algorithmic and parallel programming choices impact performance and scalability on large, distributed-memory multi-core systems. Our findings indicate that the hybrid-parallel implementation, at levels of concurrency ranging from 1,728 to 216,000, performs better, uses a smaller absolute memory footprint, and consumes less communication bandwidth than the traditional, MPI-only implementation.

97 MATHEMATICS AND COMPUTING↗

Hybrid Parallelism for Volume Rendering on Large, Multi-core Systems

This work studies the performance and scalability characteristics of"hybrid'"parallel programming and execution as applied to raycasting volume rendering -- a staple visualization algorithm -- on a large, multi-core platform. Historically, the Message Passing Interface (MPI) has become the de-facto standard for parallel programming and execution on modern parallel systems. As the computing industry trends towards multi-core processors, with four- and six-core chips common today and 128-core chips coming soon, we wish to better understand how algorithmic and parallel programming choices impact performance and scalability on large, distributed-memory multi-core systems. Our findings indicate that the hybrid-parallel implementation, at levels of concurrency ranging from 1,728 to 216,000, performs better, uses a smaller absolute memory footprint, and consumes less communication bandwidth than the traditional, MPI-only implementation.

97 MATHEMATICS AND COMPUTING↗

Hybrid Parallelism for Volume Rendering on Large, Multi-core Systems

This work studies the performance and scalability characteristics of"hybrid" parallel programming and execution as applied to raycasting volume rendering -- a staple visualization algorithm -- on a large, multi-core platform. Historically, the Message Passing Interface (MPI) has become the de-facto standard for parallel programming and execution on modern parallel systems. As the computing industry trends towards multi-core processors, with four- and six-core chips common today and 128-core chips coming soon, we wish to better understand how algorithmic and parallel programming choices impact performance and scalability on large, distributed-memory multi-core systems. Our findings indicate that the hybrid-parallel implementation, at levels of concurrency ranging from 1,728 to 216,000, performs better, uses a smaller absolute memory footprint, and consumes less communication bandwidth than the traditional, MPI-only implementation.

97 MATHEMATICS AND COMPUTING↗

A non-intrusive parallel-in-time adjoint solver with the XBraid library

In this paper, an adjoint solver for the multigrid-in-time software library XBraid is presented. XBraid provides a non-intrusive approach for simulating unsteady dynamics on multiple processors while parallelizing not only in space but also in the time domain (XBraid: Parallel multigrid in time, http://llnl.gov/casc/xbraid). It applies an iterative multigrid reduction in time algorithm to existing spatially parallel classical time propagators and computes the unsteady solution parallel in time. Techniques from Automatic Differentiation are used to develop a consistent discrete adjoint solver which provides sensitivity information of output quantities with respect to design parameter changes. The adjoint code runs backwards through the primal XBraid actions and accumulates gradient information parallel in time. It is highly non-intrusive as existing adjoint time propagators can easily be integrated through the adjoint interface. The adjoint code is validated on advection-dominated flow with periodic upstream boundary condition. We report it provides similar strong scaling results as the primal XBraid solver and offers great potential for speeding up the overall computational costs for sensitivity analysis using multiple processors.

97 MATHEMATICS AND COMPUTING↗

Advancing Fusion with Machine Learning Research Needs Workshop Report

Abstract Machine learning and artificial intelligence (ML/AI) methods have been used successfully in recent years to solve problems in many areas, including image recognition, unsupervised and supervised classification, game-playing, system identification and prediction, and autonomous vehicle control. Data-driven machine learning methods have also been applied to fusion energy research for over 2 decades, including significant advances in the areas of disruption prediction, surrogate model generation, and experimental planning. The advent of powerful and dedicated computers specialized for large-scale parallel computation, as well as advances in statistical inference algorithms, have greatly enhanced the capabilities of these computational approaches to extract scientific knowledge and bridge gaps between theoretical models and practical implementations. Large-scale commercial success of various ML/AI applications in recent years, including robotics, industrial processes, online image recognition, financial system prediction, and autonomous vehicles, have further demonstrated the potential for data-driven methods to produce dramatic transformations in many fields. These advances, along with the urgency of need to bridge key gaps in knowledge for design and operation of reactors such as ITER, have driven planned expansion of efforts in ML/AI within the US government and around the world. The Department of Energy (DOE) Office of Science programs in Fusion Energy Sciences (FES) and Advanced Scientific Computing Research (ASCR) have organized several activities to identify best strategies and approaches for applying ML/AI methods to fusion energy research. This paper describes the results of a joint FES/ASCR DOE-sponsored Research Needs Workshop on Advancing Fusion with Machine Learning, held April 30–May 2, 2019, in Gaithersburg, MD (full report available at https://science.osti.gov/-/media/fes/pdf/workshop-reports/FES_ASCR_Machine_Learning_Report.pdf ). The workshop drew on broad representation from both FES and ASCR scientific communities, and identified seven Priority Research Opportunities (PRO’s) with high potential for advancing fusion energy. In addition to the PRO topics themselves, the workshop identified research guidelines to maximize the effectiveness of ML/AI methods in fusion energy science, which include focusing on uncertainty quantification, methods for quantifying regions of validity of models and algorithms, and applying highly integrated teams of ML/AI mathematicians, computer scientists, and fusion energy scientists with domain expertise in the relevant areas.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

The SprayList: a scalable relaxed priority queue

High-performance concurrent priority queues are essential for applications such as task scheduling and discrete event simulation. Unfortunately, even the best performing implementations do not scale past a number of threads in the single digits. This is because of the sequential bottleneck in accessing the elements at the head of the queue in order to perform a DeleteMin operation. In this paper, we present the SprayList, a scalable priority queue with relaxed ordering semantics. Starting from a non-blocking SkipList, the main innovation behind our design is that the DeleteMin operations avoid a sequential bottleneck by ``spraying'' themselves onto the head of the SkipList list in a coordinated fashion. The spraying is implemented using a carefully designed random walk, so that DeleteMin returns an element among the first O(p log^3 p) in the list, with high probability, where p is the number of threads. We prove that the running time of a DeleteMin operation is O(log^3 p), with high probability, independent of the size of the list. Our experiments show that the relaxed semantics allow the data structure to scale for high thread counts, comparable to a classic unordered SkipList. As a result, we observe that, for reasonably parallel workloads, the scalability benefits of relaxation considerably outweigh the additional work due to out-of-order execution.

97 MATHEMATICS AND COMPUTING↗

A Sparse Distributed Gigascale Resolution Material Point Method

In this paper, we present a four-layer distributed simulation system and its adaptation to the Material Point Method (MPM). The system is built upon a performance portable C++ programming model targeting major High-Performance-Computing (HPC) platforms. A key ingredient of our system is a hierarchical block-tile-cell sparse grid data structure that is distributable to an arbitrary number of Message Passing Interface (MPI) ranks. We additionally propose strategies for efficient dynamic load balance optimization to maximize the efficiency of MPI tasks. Our simulation pipeline can easily switch among backend programming models, including OpenMP and CUDA, and can be effortlessly dispatched onto supercomputers and the cloud. Finally, we construct benchmark experiments and ablation studies on supercomputers and consumer workstations in a local network to evaluate the scalability and load balancing criteria. We demonstrate massively parallel, highly scalable, and gigascale resolution MPM simulations of up to 1.01 billion particles for less than 323.25 seconds per frame with 8 OpenSSH-connected workstations.

97 MATHEMATICS AND COMPUTING↗

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↗

Methods and Tools to allow molecular flow simulations to be coupled to higher level continuum descriptions of flows in porous/fractured media and aerosol/dust dynamics

The purpose of this project was to develop methods and tools that will aid in safety evaluation of nuclear fuels and licensing of nuclear reactors relating to accidents.The objectives were to develop more detailed and faster computations of fission product transport and aerosol evolution as they generally relate to nuclear fuel and/or nuclear reactor accidents. The two tasks in the project related to molecular transport in nuclear fuel and aerosol transport in reactor vessel and containment. For both the tasks, explorations of coupling of Direct Simulation Monte Carlo with Navier-Stokes solvers or the Sectional method were not successful. However, Mesh free methods for the Direct Simulation Monte Carlo method were successfully explored.These explorations permit applications to porous and fractured media, and arbitrary geometries.The computations were carried out in Mathematica and are fully parallelized. The project has resulted in new computational tools (algorithms and programs) that will improve the fidelity of computations to actual physics, chemistry and transport of fission products in the nuclear fuel and aerosol in reactor primary and secondary containments.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗

Modeling cortical circuits.

The neocortex is perhaps the highest region of the human brain, where audio and visual perception takes place along with many important cognitive functions. An important research goal is to describe the mechanisms implemented by the neocortex. There is an apparent regularity in the structure of the neocortex [Brodmann 1909, Mountcastle 1957] which may help simplify this task. The work reported here addresses the problem of how to describe the putative repeated units ('cortical circuits') in a manner that is easily understood and manipulated, with the long-term goal of developing a mathematical and algorithmic description of their function. The approach is to reduce each algorithm to an enhanced perceptron-like structure and describe its computation using difference equations. We organize this algorithmic processing into larger structures based on physiological observations, and implement key modeling concepts in software which runs on parallel computing hardware.

59 BASIC BIOLOGICAL SCIENCES↗

Performance study of GPUs in real-time trigger applications for HEP experiments

Graphical Processing Units (GPUs) have evolved into highly parallel, multi-threaded, multicore powerful processors with high memory bandwidth. GPUs are used in a variety of intensive computing applications. The combination of highly parallel architecture and high memory bandwidth makes GPUs a potentially promising technology for effective real-time processing for High Energy Physics (HEP) experiments. However, not much is known of their performance in real-time applications that require low latency, such as the trigger for HEP experiments. We describe an R and D project with the goal to study the performance of GPU technology for possible low latency applications, performing basic operations as well as some more advanced HEP lower-level trigger algorithms (such as fast tracking or jet finding). We present some preliminary results on timing measurements, comparing the performance of a CPU versus a GPU with NVIDIA's CUDA general-purpose parallel computing architecture, carried out at CDF's Level-2 trigger test stand. These studies will provide performance benchmarks for future studies to investigate the potential and limitations of GPUs for real-time applications in HEP experiments.

43 PARTICLE ACCELERATORS↗