Search NASA⌕ Search

SEARCH · Search NASA

Results for “distributed 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 1,333 records · Page 74

Scalable quantum computational science: A perspective from block-encodings and polynomial transformations

Significant developments made in quantum hardware and error correction recently have been driving quantum computing toward practical utility. However, gaps remain between abstract quantum algorithmic development and practical applications in computational sciences. In this perspective article, we propose several properties that scalable quantum computational science methods should possess. We further discuss how block-encodings and polynomial transformations can potentially serve as a unified framework with the desired properties. Recent advancements on these topics are presented, including the construction and assembly of block-encodings, and various generalizations of quantum signal processing (QSP) algorithms to perform polynomial transformations. The scalability of QSP methods on parallel and distributed quantum architectures is also highlighted. Promising applications in simulation and observable estimation in chemistry, physics, and optimization problems are presented. We hope this perspective serves as a gentle introduction to state-of-the-art quantum algorithms for the computational science community and inspires future development of scalable quantum computational science methodologies that bridge theory and practice.

Bayesian inference↗

Spatial and Temporal Measurements of Temperature and Cell Viability in Response to Nanoparticle Mediated Photothermal Therapy

Aim: Nanoparticle enhanced photothermal therapy is a promising alternative to tumor resection. However, quantitative measurements of cellular response to these treatments are limited. This paper introduces a Bimodal Enhanced Analysis of Spatiotemporal Temperature (BEAST) algorithm to rapidly determine the viability of cancer cells in vitro following photothermal therapy alone or in combination with nanoparticles. Materials & Methods: To illustrate the capability of the BEAST viability algorithm, single wall carbon nanohorns were added to renal cancer (RENCA) cells in vitro and time-dependent spatial temperature maps measured with an infrared camera during laser therapy were correlated with post-treatment cell viability distribution maps obtained by cell-staining fluorescent microscopy. Conclusion: The BEAST viability algorithm accurately and rapidly determined the cell viability as function of time, space, and temperature.

laser↗

GoFFish: A Sub-Graph Centric Framework for Large-Scale Graph Analytics1

Large scale graph processing is a major research area for Big Data exploration. Vertex centric programming models like Pregel are gaining traction due to their simple abstraction that allows for scalable execution on distributed systems naturally. However, there are limitations to this approach which cause vertex centric algorithms to under-perform due to poor compute to communication overhead ratio and slow convergence of iterative superstep. In this paper we introduce GoFFish a scalable sub-graph centric framework co-designed with a distributed persistent graph storage for large scale graph analytics on commodity clusters. We introduce a sub-graph centric programming abstraction that combines the scalability of a vertex centric approach with the flexibility of shared memory sub-graph computation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation.

Simmhan, Yogesh↗

Selective Information Extraction Strategies for Cancer Pathology Reports with Convolutional Neural Networks

To trust model predictions, it is important to ensure new data scored by the model comes from the same population used for model training. If the model is used to score new data different than the model’s training data, then predictions and model performance metrics cannot be trusted. Identifying and excluding these anomalous data points is an important task when using models in the real world. Traditional machine learning algorithms and classifiers don’t have the capability to abstain in this case. Here we propose a data-novelty detection algorithm for the Convolutional Neural Network classifier, yielding a rejection score for each new data point scored. It is a post-modeling procedure which examines the distribution of convolution filters to determine if the prediction should be trusted. We apply this algorithm to an information extraction model for a natural language text corpus. We evaluated the algorithm performance using a primary cancer site classification model applied to cancer pathology reports. Results demonstrate that the algorithm is an effective way to exclude cancer pathology reports from model scoring when they do not contain the expected information necessary to accurately classify the primary cancer type.

Yoon, Hong-Jun↗

Multiscale Monte Carlo equilibration: Two-color QCD with two fermion flavors

In this study, we demonstrate the applicability of a recently proposed multiscale thermalization algorithm to two-color quantum chromodynamics (QCD) with two mass-degenerate fermion flavors. The algorithm involves refining an ensemble of gauge configurations that had been generated using a renormalization group (RG) matched coarse action, thereby producing a fine ensemble that is close to the thermalized distribution of a target fine action; the refined ensemble is subsequently rethermalized using conventional algorithms. Although the generalization of this algorithm from pure Yang-Mills theory to QCD with dynamical fermions is straightforward, we find that in the latter case, the method is susceptible to numerical instabilities during the initial stages of rethermalization when using the hybrid Monte Carlo algorithm. We find that these instabilities arise from large fermion forces in the evolution, which are attributed to an accumulation of spurious near-zero modes of the Dirac operator. We propose a simple strategy for curing this problem, and demonstrate that rapid thermalization--as probed by a variety of gluonic and fermionic operators--is possible with the use of this solution. Also, we study the sensitivity of rethermalization rates to the RG matching of the coarse and fine actions, and identify effective matching conditions based on a variety of measured scales.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite

The analysis of connected data is an increasingly important application in high-performance computing. Such analyses can reveal fraudulent patterns in financial transactions, optimize telecommunications networks, predict information flow in social networks, etc. However, the landscape of graph analytics is highly diverse. Graph algorithms stress processor architectures differently, and no one graph can represent all topologies. Consequently, no single approach or framework is expected to be optimal for all graph analytics problems. To help make sense of this diverse landscape, we evaluated four approaches to graph analytics: GraphBLAS, Galois, BGL17, GraphIt; and compare them against hand-tuned implementations that take advantage of hardware features on our test platform. Graph- BLAS formulates graph analytics as sparse linear algebra. Galois provides syntactic constructs for data parallelism over irregular data structures. BGL17 is a generic C++ template library for implementing graph algorithms. GraphIt provides a domain- specific language to describe and optimize graph algorithms. We use the GAP Benchmark Suite to establish baseline performance and guide the side-by-side evaluation of each framework. GAP consists of 30 tests: six graph analytics algorithms (breadth- first search, single-source shortest path, PageRank, betweenness centrality, connected components, and triangle counting) run on five graphs, each with different topological characteristics (e.g., high diameter, skewed degree distribution, high average degree). High-performance reference implementations are included for each benchmark algorithm. Because a graph can be loaded into memory a number of ways (e.g., flat file on disk, compressed sparse format, data frames, retrieved from SQL or NoSQL databases), our evaluation focused on computational performance rather than I/O. Our results show the relative strengths of each framework.

Graph algorithms, Benchmarking, shared-memory prog↗

Ion Stopping Powers and CT Numbers

One of the advantages of ion beam therapy is the steep dose gradient produced near the ion's range. Use of this advantage makes knowledge of the stopping powers for all materials through which the beam passes critical. Most treatment planning systems calculate dose distributions using depth dose data measured in water and an algorithm that converts the kilovoltage X-ray computed tomography (CT) number of a given material to its linear stopping power relative to water. Some materials present in kilovoltage scans of patients and simulation phantoms do not lie on the standard tissue conversion curve. The relative linear stopping powers (RLSPs) of 21 different tissue substitutes and positioning, registration, immobilization, and beamline materials were measured in beams of protons accelerated to energies of 155, 200, and 250 MeV; carbon ions accelerated to 290 MeV/n; and iron ions accelerated to 970 MeV/n. These same materials were scanned with both kilovoltage and megavoltage CT scanners to obtain their CT numbers. Measured RLSPs and CT numbers were compared with calculated and/or literature values. Relationships of RLSPs to physical densities, electronic densities, kilovoltage CT numbers, megavoltage CT numbers, and water equivalence values converted by a treatment planning system are given. Usage of CT numbers and substitution of measured values into treatment plans to provide accurate patient and phantom simulations are discussed.

07 ISOTOPE AND RADIATION SOURCES↗

Quantum algorithms from fluctuation theorems: Thermal-state preparation

Fluctuation theorems provide a correspondence between properties of quantum systems in thermal equilibrium and a work distribution arising in a non-equilibrium process that connects two quantum systems with Hamiltonians H 0 and H 1 = H 0 + V. Building upon these theorems, we present a quantum algorithm to prepare a purification of the thermal state of H 1 at inverse temperature β ≥ 0 starting from a purification of the thermal state of H 0 . The complexity of the quantum algorithm, given by the number of uses of certain unitaries, is $\mathcal{O}$ (e β(ΔA - w l )/2 ), where ΔA is the free-energy difference between H 1 and H 0 , and w l is a work cutoff that depends on the properties of the work distribution and the approximation error ϵ > 0. If the non-equilibrium process is trivial, this complexity is exponential i β∥V∥, where ∥V∥ is the spectral norm of V. This represents a significant improvement of prior quantum algorithms that have complexity exponential in β∥H 1 ∥ in the regime where ∥V∥$\ll$ ∥H 1 ∥. The dependence of the complexity in ϵ varies according to the structure of the quantum systems. It can be exponential in 1/ϵ in general, but we show it to be sublinear in 1/ϵ if H 0 and H 1 commute, or polynomial in 1/ϵ if H 0 and H 1 are local spin systems. The possibility of applying a unitary that drives the system out of equilibrium allows one to increase the value of w l and improve the complexity even further. To this end, we analyze the complexity for preparing the thermal state of the transverse field Ising model using different non-equilibrium unitary processes and see significant complexity improvements.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Evaluation of a Machine-Learning Algorithm for Treatment Planning in Prostate Low-Dose-Rate Brachytherapy

Purpose: This work presents the application of a machine learning (ML) algorithm to automatically generate high-quality, prostate low-dose-rate (LDR) brachytherapy treatment plans. The ML algorithm can mimic characteristics of preoperative treatment plans deemed clinically acceptable by brachytherapists. The planning efficiency, dosimetry, and quality (as assessed by experts) of preoperative plans generated with an ML planning approach was retrospectively evaluated in this study. Methods and Materials: Preimplantation and postimplantation treatment plans were extracted from 100 high-quality LDR treatments and stored within a training database. The ML training algorithm matches similar features from a new LDR case to those within the training database to rapidly obtain an initial seed distribution; plans were then further fine-tuned using stochastic optimization. Preimplantation treatment plans generated by the ML algorithm were compared with brachytherapist (BT) treatment plans in terms of planning time (Wilcoxon rank sum, α = 0.05) and dosimetry (1-way analysis of variance, α = 0.05). Qualitative preimplantation plan quality was evaluated by expert LDR radiation oncologists using a Likert scale questionnaire. Results: The average planning time for the ML approach was 0.84 ± 0.57 minutes, compared with 17.88 ± 8.76 minutes for the expert planner (P=.020). Preimplantation plans were dosimetrically equivalent to the BT plans; the average prostate V150% was 4% lower for ML plans (P=.002), although the difference was not clinically significant. Respondents ranked the ML-generated plans as equivalent to expert BT treatment plans in terms of target coverage, normal tissue avoidance, implant confidence, and the need for plan modifications. Respondents had difficulty differentiating between plans generated by a human or those generated by the ML algorithm. Conclusions: Prostate LDR preimplantation treatment plans that have equivalent quality to plans created by brachytherapists can be rapidly generated using ML. The adoption of ML in the brachytherapy workflow is expected to improve LDR treatment plan uniformity while reducing planning time and resources.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

SU-E-T-477: An Efficient Dose Correction Algorithm Accounting for Tissue Heterogeneities in LDR Brachytherapy

Purpose: Seed brachytherapy is currently used for adjuvant radiotherapy of early stage prostate and breast cancer patients. The current standard for calculation of dose surrounding the brachytherapy seeds is based on American Association of Physicist in Medicine Task Group No. 43 (TG-43 formalism) which generates the dose in homogeneous water medium. Recently, AAPM Task Group No. 186 emphasized the importance of accounting for tissue heterogeneities. This can be done using Monte Carlo (MC) methods, but it requires knowing the source structure and tissue atomic composition accurately. In this work we describe an efficient analytical dose inhomogeneity correction algorithm implemented using MIM Symphony treatment planning platform to calculate dose distributions in heterogeneous media. Methods: An Inhomogeneity Correction Factor (ICF) is introduced as the ratio of absorbed dose in tissue to that in water medium. ICF is a function of tissue properties and independent of source structure. The ICF is extracted using CT images and the absorbed dose in tissue can then be calculated by multiplying the dose as calculated by the TG-43 formalism times ICF. To evaluate the methodology, we compared our results with Monte Carlo simulations as well as experiments in phantoms with known density and atomic compositions. Results: The dose distributions obtained through applying ICF to TG-43 protocol agreed very well with those of Monte Carlo simulations as well as experiments in all phantoms. In all cases, the mean relative error was reduced by at least 50% when ICF correction factor was applied to the TG-43 protocol. Conclusion: We have developed a new analytical dose calculation method which enables personalized dose calculations in heterogeneous media. The advantages over stochastic methods are computational efficiency and the ease of integration into clinical setting as detailed source structure and tissue segmentation are not needed. University of Toronto, Natural Sciences and Engineering Research Council of Canada.

60 APPLIED LIFE SCIENCES↗

An exploration of online-simulation-driven portfolio scheduling in Workflow Management Systems

Workflow Management Systems used to automate the execution of scientific workflow applications on parallel and distributed computing platforms must make scheduling decisions at runtime. A large number of workflow scheduling algorithms have been proposed in the literature, but often these algorithms are evaluated based on simplifying assumptions that may not hold in practice. Furthermore, published algorithm evaluation and/or comparison results are necessarily only for a subset of all possible scenarios, and thus may not include scenarios relevant to particular use-cases. Consequently, it is difficult for Workflow Management Systems (WMSs) developers to decide which scheduling algorithm should be implemented. To obviate this difficulty, one possible approach is to implement a portfolio of scheduling algorithms and select the most effective algorithm at runtime. One method for performing this selection is to run an online simulation for each algorithm in the portfolio. The algorithm that leads to the best performance, in simulation, is selected for future use. The above simulation-driven portfolio scheduling (SDPS) approach has been proposed in a few parallel and distributed computing contexts. The main objective of this work is to evaluate the feasibility and potential merit of SDPS if implemented in WMSs. Here we perform this evaluation using simulated WMS executions, where the simulations are instantiated from real-world platform and workflow configurations. Our main finding is that SDPS is on par with or outperforms an approach in which a single algorithm is used, where this algorithm is the one that performs best on average across all our experimental scenarios. Furthermore, we find that SDPS remains an attractive proposition even in the presence of high levels of simulation error and for simulators with relatively low levels of sophistication. In many of our experimental scenarios we find that mitigating simulation error at runtime can further improve performance. Finally, we show that simulation overhead can be made sufficiently low for SDPS to be feasible in practice.

97 MATHEMATICS AND COMPUTING↗

Dynamic Model Agnostic Reliability Evaluation of Machine-Learning Models Integrated in Instrumentation & Control Systems

In recent years, the field of data-driven neural network-based machine learning (ML) algorithms has grown significantly and spurred research in its applicability to instrumentation and control systems. While they are promising in operational contexts, the trustworthiness of such algorithms is not adequately assessed. Failures of ML-integrated systems are poorly understood; the lack of comprehensive risk modeling can degrade the trustworthiness of these systems. In recent reports by the National Institute for Standards and Technology, trustworthiness in ML is a critical barrier to adoption and will play a vital role in intelligent systems' safe and accountable operation. Thus, in this work, we demonstrate a real-time model-agnostic method to evaluate the relative reliability of ML predictions by incorporating out-of-distribution detection on the training dataset. It is well documented that ML algorithms excel at interpolation (or near-interpolation) tasks but significantly degrade at extrapolation. This occurs when new samples are "far" from training samples. The method, referred to as the Laplacian distributed decay for reliability (LADDR), determines the difference between the operational and training datasets, which is used to calculate a prediction's relative reliability. LADDR is demonstrated on a feedforward neural network-based model used to predict safety significant factors during different loss-of-flow transients. LADDR is intended as a "data supervisor" and determines the appropriateness of well-trained ML models in the context of operational conditions. Ultimately, LADDR illustrates how training data can be used as evidence to support the trustworthiness of ML predictions when utilized for conventional interpolation tasks.

97 MATHEMATICS AND COMPUTING↗

Coordinative Real-time Sub-Transmission Volt-VAr Control for Reactive Power Regulation between Transmission and Distribution Systems

This paper introduces an integrated voltage regulation approach to coordinate the Volt-VAr control between transmission and distribution systems. Distributed photovoltaic (PV) systems are aggregated as a virtual power plant (VPP). At the sub-transmission level, a Coordinated Real-time Sub-Transmission Volt-VAr Control Tool (CReST-VCT) is introduced to coordinate the operation of the shunt devices and the reactive power provided by the VPPs. The CReST-VCT uses an enhanced Volt-VAr control algorithm with weighted voltage control objects that include minimizing losses, maintaining the voltage within desirable levels, and minimizing the number of mechanical switching of shunt elements. The algorithm runs every 5 minutes and is solved using AC optimal power flow (OPF) solution technique. The outputs include the settings for each sub-transmission-level Volt-VAr control devices and the reactive power generation requirements for each VPP. Then, each VPP will run a distribution Volt-VAr control algorithm to select the PV inverters that provide the Volt-VAr control services considering the distribution network topology. The goal of the VPP reactive power control is to meet the transmission level service requirements while maintaining the voltage and line flow in the distribution system within limits. Each VPP will update its voltage regulation capacity every 5 minutes to allow the CReST-VCT to formulate the optimization problem for the next dispatch interval. The proposed tool is simulated on Duke Energy Carolina system to demonstrate the capability of providing voltage support service by dispatching of reactive power of distributed PV as VPP.

Ke, Xinda↗

Positive approach: Implications for the relation between number theory and geometry, including connection to Santilli mathematics, from Fibonacci reconstitution of natural numbers and of prime numbers

The paper recapitulates some key elements in previously published results concerning exact and complete reconstitution of the field of natural numbers, both as ordinal and as cardinal numbers, from systematic unfoldment of the Fibonacci algorithm. By this natural numbers emerge as Fibonacci 'atoms' and 'molecules' consistent with the notion of Zeckendorf sums. Here, the sub-set of prime numbers appears not as the primary numbers, but as an epistructure from a deeper Fibonacci constitution, and is thus targeted from a 'positive approach'. In the Fibonacci reconstitution of number theory natural numbers show a double geometrical aspect: partly as extension in space and partly as position in a successive structuring of space. More specifically, the natural numbers are shown to be distributed by a concise 5:3 code structured from the Fibonacci algorithm via Pascal's triangle. The paper discusses possible implications for the more general relation between number theory and geometry, as well as more specifically in relation to hadronic mathematics, initiated by R.M. Santilli, and also briefly to some other recent science linking number theory more directly to geometry and natural systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Position-probability-sampled Monte Carlo calculation of VMAT, 3DCRT, step-shoot IMRT, and helical tomotherapy dose distributions using BEAMnrc/DOSXYZnrc

Purpose: The commercial release of volumetric modulated arc therapy techniques using a conventional linear accelerator and the growing number of helical tomotherapy users have triggered renewed interest in dose verification methods, and also in tools for exploring the impact of machine tolerance and patient motion on dose distributions without the need to approximate time-varying parameters such as gantry position, MLC leaf motion, or patient motion. To this end we have developed a Monte Carlo-based calculation method capable of simulating a wide variety of treatment techniques without the need to resort to discretization approximations. Methods: The ability to perform complete position-probability-sampled Monte Carlo dose calculations was implemented in the BEAMnrc/DOSXZYnrc user codes of EGSnrc. The method includes full accelerator head simulations of our tomotherapy and Elekta linacs, and a realistic representation of continous motion via the sampling of a time variable. The functionality of this algorithm was tested via comparisons with both measurements and treatment planning dose distributions for four types of treatment techniques: 3D conformal, step-shoot intensity modulated radiation therapy, helical tomotherapy, and volumetric modulated arc therapy. Results: For static fields, the absolute dose agreement between the EGSnrc Monte Carlo calculations and measurements is within 2%/1 mm. Absolute dose agreement between Monte Carlo calculations and treatment planning system for the four different treatment techniques is within 3%/3 mm. Discrepancies with the tomotherapy TPS on the order of 10%/5 mm were observed for the extreme example of a small target located 15 cm off-axis and planned with a low modulation factor. The increase in simulation time associated with using position-probability sampling, as opposed to the discretization approach, was less than 2% in most cases. Conclusions: A single Monte Carlo simulation method can be used to calculate patient dose distribution for various types of treatment techniques delivered with either tomotherapy or a conventional linac. The method simplifies the simulation process, improves dose calculation accuracy, and involves an acceptably small change in computation time.

60 APPLIED LIFE SCIENCES↗

Reinforcement Learning for Load-balanced Parallel Particle Tracing

We explore an online reinforcement learning (RL) paradigm to dynamically optimize parallel particle tracing performance in distributed-memory systems. Our method combines three novel components: (1) a work donation algorithm, (2) a high-order workload estimation model, and (3) a communication cost model. First, we design an RL-based work donation algorithm. Our algorithm monitors workloads of processes and creates RL agents to donate data blocks and particles from high-workload processes to low-workload processes to minimize program execution time. The agents learn the donation strategy on the fly based on reward and cost functions designed to consider processes' workload changes and data transfer costs of donation actions. Second, we propose a workload estimation model, helping RL agents estimate the workload distribution of processes in future computations. Third, we design a communication cost model that considers both block and particle data exchange costs, helping RL agents make effective decisions with minimized communication costs. We demonstrate that our algorithm adapts to different flow behaviors in large-scale fluid dynamics, ocean, and weather simulation data. Our algorithm improves parallel particle tracing performance in terms of parallel efficiency, load balance, and costs of I/O and communication for evaluations with up to 16,384 processors.

Distributed and parallel particle tracing↗

A Self Consistent Multiprocessor Space Charge Algorithm that is Almost Embarrassingly Parallel

We present a space charge code that is self consistent, massively parallelizeable, and requires very little communication between computer nodes; making the calculation almost embarrassingly parallel. This method is implemented in the code COSY Infinity where the differential algebras used in this code are important to the algorithm's proper functioning. The method works by calculating the self consistent space charge distribution using the statistical moments of the test particles, and converting them into polynomial series coefficients. These coefficients are combined with differential algebraic integrals to form the potential, and electric fields. The result is a map which contains the effects of space charge. This method allows for massive parallelization since its statistics based solver doesn't require any binning of particles, and only requires a vector containing the partial sums of the statistical moments for the different nodes to be passed. All other calculations are done independently. The resulting maps can be used to analyze the system using normal form analysis, as well as advance particles in numbers and at speeds that were previously impossible.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗