Search NASA⌕ Search

SEARCH · Search NASA

Results for “high performance graph 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.

192 records · Page 11
All sourcesNASA NTRSDOE OSTI
DOE OSTI2017

Task-based Parallel Computation of the Density Matrix in Quantum-based Molecular Dynamics using Graph Partitioning

Quantum-based molecular dynamics (QMD) is a highly accurate and transferable method for material science simulations. However, the time scales and system sizes accessible to QMD are typically limited to picoseconds and a few hundred atoms. These constraints arise due to expensive self-consistent ground-state electronic structure calculations that can often scale cubically with the number of atoms. Linearly scaling methods depend on computing the density matrix P from the Hamiltonian matrix H by exploiting the sparsity in both matrices. The second-order spectral projection (SP2) algorithm is an O(N) algorithm that computes P with a sequence of 40 - 50 matrix-matrix multiplications. In this paper, we present task-based implementations of a recently developed data-parallel graph-based approach to the SP2 algorithm, G-SP2. We represent the density matrix P as an undirected graph and use graph partitioning techniques to divide the computation into smaller independent tasks. The partitions thus obtained are generally not of equal size and give rise to undesirable load imbalances in standard MPI-based implementations. This load-balancing challenge can be mitigated by dynamically scheduling parallel computations at runtime using task-based programming models. We develop task-based implementations of the data-parallel G-SP2 algorithm using both Intel's Concurrent Collections (CnC) as well as the Charm++ programming model and evaluate these implementations for future use. Scaling and performance results of our implementations are investigated for representative segments of QMD simulations for solvated protein systems containing more than 10,000 atoms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

An Integrated Approach to Scaling Task-Based Runtime Systems for Next Generation Engineering problems

The need to scale next-generation industrial engineering problems to the largest computational platforms presents unique challenges. Such problems may have complex coupled multi-physics models, as well as computationally and communication intensive algorithms not often seen in standard academic problems, while also needing high-demand I/O for analysis purposes. In such cases even codes with good existing scaling properties may need significant changes, addressed in a cross-cutting way to solve such problems at extreme scales. These challenges relate to system components that were not previously problematic on less complex problems and/or at smaller computational scales. This paper illustrates these challenges for Uintah, a highly scalable asynchronous many-task runtime system being applied to the modeling of a 1000 MWe ultra-supercritical coal boiler. In order to model this formidable, production engineering problem, not only was an integrated approach needed that built upon existing scalable components in areas such as complex stencil calculations and linear algebra, but the significant challenges of high demand I/O, complex task graphs, and infrastructure inefficiencies also had to be addressed. This integrated approach allowed this problem to run on 256K CPU cores on Mira, with good weak scaling to 512K CPU cores and similar strong scaling, except for radiation. The need for strong scaling of a new ray tracing-based radiation model required substantial Uintah infrastructure improvements before 119K CPU cores and 7.5K GPUs on Titan could be used, with scaling out to 256K CPU cores and 16K GPUs. The resulting code demonstrates not only excellent overall scalability but a significant improvement in overall performance for the full-scale, production boiler problem.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

tapir: A tool for topologies, amplitudes, partial fraction decomposition and input for reductions

The demand for precision predictions in the field of high energy physics has dramatically increased over recent years. Experiments conducted at the LHC, as well as precision measurements at the intensity frontier such as Belle II require equally precise theoretical predictions to make full use of the acquired data. To match the experimental precision, second-, third- and, for certain quantities, even higher-order calculations in perturbative quantum field theory are required. To facilitate such calculations, computer software automating as many steps as possible is required. Yet, each calculation poses different challenges and thus, a high level of configurability is required. In this context we present tapir: a tool for identification, manipulation and minimization of Feynman integral families. It is designed to integrate in toolchains based on the computer algebra system FORM, the use of which is common practice in the field. tapir can be used to reduce the complexity of multi-loop problems with cut-filters, topology mapping, partial fraction decomposition and alike. Program Title:tapir CPC Library link to program files:https://doi.org/10.17632/ptc9t46xyn.1 Developer's repository link:https://gitlab.com/tapir-devs/tapir Licensing provisions: GPLv3 Programming language:python 3, C++ Nature of problem: Multi-loop computations require the automatization of a large number of different tasks related to Feynman integral topologies. Among them are the identification and minimization of integral topologies, partial fraction decomposition of topologies in the case of linearly dependent propagators as well as mapping scalar products of loop momenta to scalar functions. Solution method: The minimization of topologies is performed by comparison of their respective Nickel indices [1], even further minimization utilizes Pak's algorithm [2]. To efficiently map scalar products of loop momenta to scalar functions FORM [3] code is generated. Additional comments including restrictions and unusual features: Minimization based on Pak's algorithm slows down for many lines and scales. A coarser minimization using the Nickel indices, however, is still possible. [1]B. Nickel, D. Meiron, G.A.J. Baker, Compilation of 2-pt and 4-pt graphs for continuous spin model, Report, University of Guelph, 1977.[2]A. Pak, J. Phys. Conf. Ser. 368 (2012) 012049, https://doi.org/10.1088/1742-6596/368/1/012049, arXiv:1111.0868.[3]B. Ruijl, T. Ueda, J. Vermaseren, FORM version 4.2, arXiv:1707.06453, 7 2017.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2023

Evaluation of global teleconnections in CMIP6 climate projections using complex networks

In climatological research, the evaluation of climate models is one of the central research subjects. As an expression of large-scale dynamical processes, global teleconnections play a major role in interannual to decadal climate variability. Their realistic representation is an indispensable requirement for the simulation of climate change, both natural and anthropogenic. Therefore, the evaluation of global teleconnections is of utmost importance when assessing the physical plausibility of climate projections. We present an application of the graph-theoretical analysis tool δ-MAPS, which constructs complex networks on the basis of spatio-temporal gridded data sets, here sea surface temperature and geopotential height at 500 hPa. Complex networks complement more traditional methods in the analysis of climate variability, like the classification of circulation regimes or empirical orthogonal functions, assuming a new non-linear perspective. While doing so, a number of technical tools and metrics, borrowed from different fields of data science, are implemented into the δ-MAPS framework in order to overcome specific challenges posed by our target problem. Those are trend empirical orthogonal functions (EOFs), distance correlation and distance multicorrelation, and the structural similarity index. δ-MAPS is a two-stage algorithm. In the first place, it assembles grid cells with highly coherent temporal evolution into so-called domains. In a second step, the teleconnections between the domains are inferred by means of the non-linear distance correlation. We construct 2 unipartite and 1 bipartite network for 22 historical CMIP6 climate projections and 2 century-long coupled reanalyses (CERA-20C and 20CRv3). Potential non-stationarity is taken into account by the use of moving time windows. The networks derived from projection data are compared to those from reanalyses. Our results indicate that no single climate projection outperforms all others in every aspect of the evaluation. But there are indeed models which tend to perform better/worse in many aspects. Differences in model performance are generally low within the geopotential height unipartite networks but higher in sea surface temperature and most pronounced in the bipartite network representing the interaction between ocean and atmosphere.

58 GEOSCIENCES↗
DOE OSTI2025

Scalable edge clustering of dynamic graphs via weighted line graphs

Timestamped relational datasets consisting of records (or connections) between pairs of entities are ubiquitous in network science. For applications like peer-to-peer communication, email, various social network interactions, and computer network security, it is useful to organize these records into groups based on how and when they are occurring. Weighted line graphs offer a natural way to model how records are related in such datasets but for large real-world graph topologies, building and utilizing the line graph is prohibitively expensive. Here, we present the framework to cluster the edges of a dynamic graph via the associated line graph that contains two major contributions. The first is a method to work with the line graph implicitly and the second is a distributed scale implementation of an agglomerative hierarchical graph clustering algorithm. We outline a novel hierarchical dynamic graph edge clustering approach that efficiently breaks massive relational datasets into small sets of edges containing events at various timescales. This is in stark contrast to traditional graph clustering algorithms that prioritize highly connected (clique-like) community structures. Our approach relies on constructing a sufficient subgraph of a weighted line graph and applying a hierarchical agglomerative clustering. This approach is related to scalable techniques from spatial clustering, nonlinear-dimension reduction, topological data analysis, and draws particular inspiration from HDBSCAN. As an edge clustering, this method yields an overlapping node clustering. Our algorithm is parallelizable and we demonstrate efficient clustering of a billion-scale, real-world dynamic graph into small edge sets that correlate in topology and time. The entire clustering process for a graph with tens of billions of edges takes just a few minutes of run time on 256 nodes of a distributed compute environment. We argue how the output of the edge clustering is useful for a multitude of data visualization and powerful machine learning tasks, both involving the original massive dynamic graph data and metadata associated with the nodes and edges. Finally, we describe how this approach can be extended to dynamic hypergraphs and dynamic graphs/hypergraphs with unstructured data living on vertices and edges.

Data Analysis↗
DOE OSTI2024

Efficient Parallelization of Irregular Applications on GPU Architectures

With the enlarging computation capacity of general Graphics Processing Units (GPUs), leveraging GPUs to accelerate parallel applications has become a critical topic in academia and industry. However, a wide range of irregular applications with the computation-/memory-intensive nature cannot easily achieve high GPU utilization. The challenges mainly involve the following aspects: first, data dependence leads to coarse-grained kernel and inefficient parallelism; second, heavy GPU memory usage may cause frequent memory evictions and extra overhead of I/O; third, specific computation patterns produce memory redundancies; last, workload balance and data reusability conjunctly benefit the overall performance, but there may exist a dynamic trade-off between them. Targeting these challenges, this dissertation proposes multiple optimizations to accelerate two real-world applications: many-body correlation functions to simulate nuclear physics in a large-scale scientific system; the other is the eALS-based matrix factorization recommendation system. To accelerate the calculations of many-body correlation functions, this dissertation presents three frameworks in GPU memory management and multi-GPU scheduling. Firstly, an optimized systematic GPU memory management framework, MemHC, utilizes a series of new memory reduction designs in GPU memory allocation, CPU/GPU communications, and GPU memory oversubscription. Secondly, an enhanced multi-GPU scheduling framework, MICCO, particularly by taking both data dimension (e.g., data reuse and data eviction) and computation dimension into account. MICCO designs a heuristic scheduling algorithm and a machine learning-based regression model to generate the optimal settings of a proposed new concept to manage the trade-off. Thirdly, a locality-aware multi-GPU scheduling framework. This scheduler leverages pipeline batch generation with a looking-ahead strategy by building local dependency graphs for memory transfer reduction and better data reuse, achieving up to 79.92% memory cost reduction and 1.67x speedup. To parallelize the eALS-based recommendation system, this dissertation proposes an efficient CPU/GPU heterogeneous recommendation system, HEALS. HEALS employs newly designed architecture-adaptive data formats to achieve load balance and good data locality on CPU and GPU. To mitigate the data dependence, HEALS presents a CPU/GPU collaboration model for both task parallelism and data parallelism with multiple kernel computation optimizations. In summary, this dissertation efficiently accelerates two typical irregular applications on GPUs by building four frameworks, including CPU/GPU collaboration, GPU memory management, and multi-GPU scheduling.

Wang, Qihan↗
DOE OSTI2015

Online technique for detecting state of onboard fiber optic gyroscope

Although angle random walk (ARW) of fiber optic gyroscope (FOG) has been well modeled and identified before being integrated into the high-accuracy attitude control system of satellite, aging and unexpected failures can affect the performance of FOG after launch, resulting in the variation of ARW coefficient. Therefore, the ARW coefficient can be regarded as an indicator of “state of health” for FOG diagnosis in some sense. The Allan variance method can be used to estimate ARW coefficient of FOG, however, it requires a large amount of data to be stored. Moreover, the procedure of drawing slope lines for estimation is painful. To overcome the barriers, a weighted state-space model that directly models the ARW to obtain a nonlinear state-space model was established for FOG. Then, a neural extended-Kalman filter algorithm was implemented to estimate and track the variation of ARW in real time. The results of experiment show that the proposed approach is valid to detect the state of FOG. Moreover, the proposed technique effectively avoids the storage of data.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2012

Effective Software Design and Development for the New Graph Architecture HPC Machines

Software applications need to change and adapt as modern architectures evolve. Nowadays advancement in chip design translates to increased parallelism. Exploiting such parallelism is a major challenge in modern software engineering. Multicore processors are about to introduce a significant change in the way we design and use fundamental data structures. In this work we describe the design and programming principles of a software library of highly concurrent scalable and nonblocking data containers. In this project we have created algorithms and data structures for handling fundamental computations in massively multithreaded contexts, and we have incorporated these into a usable library with familiar look and feel. In this work we demonstrate the first design and implementation of a wait-free hash table. Our multiprocessor data structure design allows a large number of threads to concurrently insert, remove, and retrieve information. Non-blocking designs alleviate the problems traditionally associated with the use of mutual exclusion, such as bottlenecks and thread-safety. Lock-freedom provides the ability to share data without some of the drawbacks associated with locks, however, these designs remain susceptible to starvation. Furthermore, wait-freedom provides all of the benefits of lock-free synchronization with the added assurance that every thread makes progress in a finite number of steps. This implies deadlock-freedom, livelock-freedom, starvation-freedom, freedom from priority inversion, and thread-safety. The challenges of providing the desirable progress and correctness guarantees of wait-free objects makes their design and implementation difficult. There are few wait-free data structures described in the literature. Using only standard atomic operations provided by the hardware, our design is portable; therefore, it is applicable to a variety of data-intensive applications including the domains of embedded systems and supercomputers.Our experimental evaluation shows that our hash table design outperforms the most advanced locking solution, provided by Intel's TBB library, by 22%. When compared to more traditional locking designs we show a performance improvement by a factor of 7.92. When compared to alternative non-blocking designs, our hash table demonstrates solid performance gains in a large majority of cases, typically by a factor of 3.44.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2016

Interactive contour delineation of organs at risk in radiotherapy: Clinical evaluation on NSCLC patients

Purpose: Accurate delineation of organs at risk (OARs) on computed tomography (CT) image is required for radiation treatment planning (RTP). Manual delineation of OARs being time consuming and prone to high interobserver variability, many (semi-) automatic methods have been proposed. However, most of them are specific to a particular OAR. Here, an interactive computer-assisted system able to segment various OARs required for thoracic radiation therapy is introduced. Methods: Segmentation information (foreground and background seeds) is interactively added by the user in any of the three main orthogonal views of the CT volume and is subsequently propagated within the whole volume. The proposed method is based on the combination of watershed transformation and graph-cuts algorithm, which is used as a powerful optimization technique to minimize the energy function. The OARs considered for thoracic radiation therapy are the lungs, spinal cord, trachea, proximal bronchus tree, heart, and esophagus. The method was evaluated on multivendor CT datasets of 30 patients. Two radiation oncologists participated in the study and manual delineations from the original RTP were used as ground truth for evaluation. Results: Delineation of the OARs obtained with the minimally interactive approach was approved to be usable for RTP in nearly 90% of the cases, excluding the esophagus, which segmentation was mostly rejected, thus leading to a gain of time ranging from 50% to 80% in RTP. Considering exclusively accepted cases, overall OARs, a Dice similarity coefficient higher than 0.7 and a Hausdorff distance below 10 mm with respect to the ground truth were achieved. In addition, the interobserver analysis did not highlight any statistically significant difference, at the exception of the segmentation of the heart, in terms of Hausdorff distance and volume difference. Conclusions: An interactive, accurate, fast, and easy-to-use computer-assisted system able to segment various OARs required for thoracic radiation therapy has been presented and clinically evaluated. The introduction of the proposed system in clinical routine may offer valuable new option to radiation oncologists in performing RTP.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2025

Ca X ML: Chemistry‐informed machine learning explains mutual changes between protein conformations and calcium ions in calcium‐binding proteins using structural and topological features

Proteins' flexibility is a feature in communicating changes in cell signaling instigated by binding with secondary messengers, such as calcium ions, associated with the coordination of muscle contraction, neurotransmitter release, and gene expression. When binding with the disordered parts of a protein, calcium ions must balance their charge states with the shape of calcium-binding proteins and their versatile pool of partners depending on the circumstances they transmit. Accurately determining the ionic charges of those ions is essential for understanding their role in such processes. However, it is unclear whether the limited experimental data available can be effectively used to train models to accurately predict the charges of calcium-binding protein variants. Here, we developed a chemistry-informed, machine-learning algorithm that implements a game theoretic approach to explain the output of a machine-learning model without the prerequisite of an excessively large database for high-performance prediction of atomic charges. We used the ab initio electronic structure data representing calcium ions and the structures of the disordered segments of calcium-binding peptides with surrounding water molecules to train several explainable models. Network theory was used to extract the topological features of atomic interactions in the structurally complex data dictated by the coordination chemistry of a calcium ion, a potent indicator of its charge state in protein. Our design created a computational tool of Ca X ML, which provided a framework of explainable machine learning model to annotate ionic charges of calcium ions in calcium-binding proteins in response to the chemical changes in an environment. Our framework will provide new insights into protein design for engineering functionality based on the limited size of scientific data in a genome space.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2016

Towards a Scalable and Adaptive Application Support Platform for Large-Scale Distributed E-Sciences in High-Performance Network Environments

The advent of large-scale collaborative scientific applications has demonstrated the potential for broad scientific communities to pool globally distributed resources to produce unprecedented data acquisition, movement, and analysis. System resources including supercomputers, data repositories, computing facilities, network infrastructures, storage systems, and display devices have been increasingly deployed at national laboratories and academic institutes. These resources are typically shared by large communities of users over Internet or dedicated networks and hence exhibit an inherent dynamic nature in their availability, accessibility, capacity, and stability. Scientific applications using either experimental facilities or computation-based simulations with various physical, chemical, climatic, and biological models feature diverse scientific workflows as simple as linear pipelines or as complex as a directed acyclic graphs, which must be executed and supported over wide-area networks with massively distributed resources. Application users oftentimes need to manually configure their computing tasks over networks in an ad hoc manner, hence significantly limiting the productivity of scientists and constraining the utilization of resources. The success of these large-scale distributed applications requires a highly adaptive and massively scalable workflow platform that provides automated and optimized computing and networking services. This project is to design and develop a generic Scientific Workflow Automation and Management Platform (SWAMP), which contains a web-based user interface specially tailored for a target application, a set of user libraries, and several easy-to-use computing and networking toolkits for application scientists to conveniently assemble, execute, monitor, and control complex computing workflows in heterogeneous high-performance network environments. SWAMP will enable the automation and management of the entire process of scientific workflows with the convenience of a few mouse clicks while hiding the implementation and technical details from end users. Particularly, we will consider two types of applications with distinct performance requirements: data-centric and service-centric applications. For data-centric applications, the main workflow task involves large-volume data generation, catalog, storage, and movement typically from supercomputers or experimental facilities to a team of geographically distributed users; while for service-centric applications, the main focus of workflow is on data archiving, preprocessing, filtering, synthesis, visualization, and other application-specific analysis. We will conduct a comprehensive comparison of existing workflow systems and choose the best suited one with open-source code, a flexible system structure, and a large user base as the starting point for our development. Based on the chosen system, we will develop and integrate new components including a black box design of computing modules, performance monitoring and prediction, and workflow optimization and reconfiguration, which are missing from existing workflow systems. A modular design for separating specification, execution, and monitoring aspects will be adopted to establish a common generic infrastructure suited for a wide spectrum of science applications. We will further design and develop efficient workflow mapping and scheduling algorithms to optimize the workflow performance in terms of minimum end-to-end delay, maximum frame rate, and highest reliability. We will develop and demonstrate the SWAMP system in a local environment, the grid network, and the 100Gpbs Advanced Network Initiative (ANI) testbed. The demonstration will target scientific applications in climate modeling and high energy physics and the functions to be demonstrated include workflow deployment, execution, steering, and reconfiguration. Throughout the project period, we will work closely with the science communities in the fields of climate modeling and high energy physics including Spallation Neutron Source (SNS) and Large Hadron Collider (LHC) projects to mature the system for production use.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

The Development of a Generalized Riser Flow Regime Map Based Upon Higher Moment and Chaotic Statistics Using Electrical Capacitance Volume Tomography (ECVT)

Dynamic analyses have been applied to the temporal signals from an Electro Capacitance Volume Tomography instrument located near mid-height on the riser of an industrial-scale cold-flow circulating fluidized bed to characterize gas-solids flow behavior in the riser. Twelve capacitance electrodes surround the cylindrical riser over a height of 1.3 m. The instrument used a neural network deconvolution algorithm to determine the spatially resolved solids fraction recorded at 52 Hz. Experiments were carried out over a range of gas and solids flows in the transport regime using a Geldart Group B bed material, high density polyethylene with mean particle size of 880 μm. The radial solids distribution was found to vary from one-time step to the next between profiles typical of laminar and turbulent flow. The duration of time spent in each of these flow profiles depended upon the operating regime – dilute, core-annular, or fast fluidized bed. The chaotic structure of the temporal data was characterized using the three conventional approaches: the first 4 moments from the distribution of signal in time, system memory parameters from the autocorrelation function and the Hurst exponent, and analysis of the correlationentropy and correlation dimension of the attractor. These signal analysis techniques were used to clearly distinguish differences between different transport operating regimes. Specifically, it was experimentally observed that a riser transitions from core annular flow profile to dilute and dense regimes via increasing the frequency of short term transients to either dilute or dense flow profiles, respectively. A regime map was generated based upon these dynamics using solids flux and gas velocity axes. Fast fluidized, core annular, and dilute each exhibited different degree of dynamic characteristics typical of fluid dominated or particle compromising behavior. It should be noted that the magnitude for the different statistics was in the same range regardless of the regime, it was the radial profile for the statistic that changed and subsequently identified that there was a change in the regime. Finally, a reduced regime map was developed consisting of plotting the gas velocity normalized by the upper transport velocity versus the solids flux normalized by the saturation carrying capacity. The use of this reduced plot allowed the data from widely different conditions to be plotted and compared on the same<p>graph. Note that in many instances, some of the statistics identified the operating point as being in one regime while others indicated that it was in another indicating a transition region between dilute or core annular regimes and between the core annular and fast fluidization regimes. This now provides a tool that can be used to optimize process performance, identify changes in operating states, or replicate process dynamics during process scaling or changing operating parameters. </p>

Breault, Ronald↗