Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Algorithms and data structure”

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 127 records · Page 7

Cloud properties derived from two lidars over the ARM SGP site

[1] Active remote sensors such as lidars or radars can be used with other data to quantify the cloud properties at regional scale and at global scale (Dupont et al., 2009). Relative to radar, lidar remote sensing is sensitive to very thin and high clouds but has a significant limitation due to signal attenuation in the ability to precisely quantify the properties of clouds with a 20 cloud optical thickness larger than 3. In this study, 10-years of backscatter lidar signal data are analysed by a unique algorithm called STRucture of ATmosphere (STRAT, Morille et al., 2007). We apply the STRAT algorithm to data from both the collocated Micropulse lidar (MPL) and a Raman lidar (RL) at the Atmospheric Radiation Measurement (ARM) Southern Great Plains (SGP) site between 1998 and 2009. Raw backscatter lidar signal is processed and 25 corrections for detector deadtime, afterpulse, and overlap are applied. (Campbell et al.) The cloud properties for all levels of clouds are derived and distributions of cloud base height (CBH), top height (CTH), physical cloud thickness (CT), and optical thickness (COT) from local statistics are compared. The goal of this study is (1) to establish a climatology of macrophysical and optical properties for all levels of clouds observed over the ARM SGP site 30 and (2) to estimate the discrepancies induced by the two remote sensing systems (pulse energy, sampling, resolution, etc.). Our first results tend to show that the MPLs, which are the primary ARM lidars, have a distinctly limited range where all of these cloud properties are detectable, especially cloud top and cloud thickness, but even actual cloud base especially during summer daytime period. According to the comparisons between RL and MPL, almost 50% of situations show a signal to noise ratio too low (smaller than 3) for the MPL in order to detect clouds higher than 7km during daytime period in summer. Consequently, the MPLderived annual cycle of cirrus cloud base (top) altitude is biased low, especially for daylight periods, compared with those derived from the RL data, which detects 5 cloud base ranging from 7.5 km in winter to 9.5 km in summer (and tops ranging from 8.6 to 10.5 km). The optically thickest cirrus clouds (COT>0.3) reach 50% of the total population for the Raman lidar and only 20% for the Micropulse lidar due to the difference of pulse energy and the effect of solar irradiance contamination. A complementary study using the cloud fraction 10 derived from the Micropulse lidar for clouds below 5 km and from the Raman lidar for cloud above 5 km allows for better estimation of the total cloud fraction between the ground and the top of the atmosphere. This study presents the diurnal cycle of cloud fraction for each season in comparisons with the Long et al. (2006) cloud fraction calculation derived from radiative flux analysis.

54 ENVIRONMENTAL SCIENCES↗

NMR_DIFFSIM v. 1.0

The software generates and analyzes nuclear magnetic resonance spin diffusion simulations for the purpose of measuring domain sizes or spin diffusion constants in a heterogenous sample. Its primary capabilities are: 1. It solves the spin magnetization diffusion equation to simulate the results of a spin diffusion experiment using any structural input geometry, including structure models generated by molecular dynamics or other computational or experimental methods. 2. It compares the results of simulations on an input structure to experimental data, providing a data fitting algorithm to extract physical information from the experimental data via the simulation. 3. It can provide statistical measures to compare correlations between structural models, to determine domain clustering and connectedness, and to provide goodness-of-fit measures including chord length distributions, chi-squared values, Pearson coefficients and pair correlation functions. 4. It provides output reports, data files, and movies to visualize simulation results.

Sorte, Eric↗

Fast and Accurate Support Vector Machines on Large Scale Systems

Support Vector Machines (SVM) is a supervised Machine Learning and Data Mining (MLDM) algorithm, which has become ubiquitous largely due to its high accuracy and obliviousness to dimensionality. The objective of SVM is to find an optimal boundary --- also known as hyperplane --- which separates the samples (examples in a dataset) of different classes by a maximum margin. Usually, very few samples contribute to the definition of the boundary. However, existing parallel algorithms use the entire dataset for finding the boundary, which is sub-optimal for performance reasons. In this paper, we propose a novel distributed memory algorithm to eliminate the samples which do not contribute to the boundary definition in SVM. We propose several heuristics, which range from early (aggressive) to late (conservative) elimination of the samples, such that the overall time for generating the boundary is reduced considerably. In a few cases, a sample may be eliminated (shrunk) pre-emptively --- potentially resulting in an incorrect boundary. We propose a scalable approach to synchronize the necessary data structures such that the proposed algorithm maintains its accuracy. We consider the necessary trade-offs of single/multiple synchronization using in-depth time-space complexity analysis. We implement the proposed algorithm using MPI and compare it with libsvm--- de facto sequential SVM software --- which we enhance with OpenMP for multi-core/many-core parallelism. Our proposed approach shows excellent efficiency using up to 4096 processes on several large datasets such as UCI HIGGS Boson dataset and Offending URL dataset.

Vishnu, Abhinav↗

Irregular Applications: Architectures & Algorithms

Irregular applications are characterized by irregular data structures, control and communication patterns. Novel irregular high performance applications which deal with large data sets and require have recently appeared. Unfortunately, current high performance systems and software infrastructures executes irregular algorithms poorly. Only coordinated efforts by end user, area specialists and computer scientists that consider both the architecture and the software stack may be able to provide solutions to the challenges of modern irregular applications.

99 GENERAL AND MISCELLANEOUS↗

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗

Machine Learning Toolkit for Extreme Scale

Support Vector Machines (SVM) is a popular machine learning technique, which has been applied to a wide range of domains such as science, finance, and social networks for supervised learning. MaTEx undertakes the challenge of designing a scalable parallel SVM training algorithm for large scale systems, which includes commodity multi-core machines, tightly connected supercomputers and cloud computing systems. Several techniques are proposed for improved speed and memory space usage including adaptive and aggressive elimination of samples for faster convergence , and sparse format representation of data samples. Several heuristics for earliest possible to lazy elimination of non-contributing samples are considered in MaTEx. In many cases, where an early sample elimination might result in a false positive, low overhead mechanisms for reconstruction of key data structures are proposed. The proposed algorithm and heuristics are implemented and evaluated on various publicly available datasets

Source record↗

A Work-Efficient Parallel Sparse Matrix-Sparse Vector Multiplication Algorithm

We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense that its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.

97 MATHEMATICS AND COMPUTING↗

Algorithms for Efficient Reproducible Floating Point Summation

We define “reproducibility” as getting bitwise identical results from multiple runs of the same program, perhaps with different hardware resources or other changes that should not affect the answer. Many users depend on reproducibility for debugging or correctness. However, dynamic scheduling of parallel computing resources, combined with nonassociative floating point addition, makes reproducibility challenging even for summation, or operations like the BLAS. We describe a “reproducible accumulator” data structure (the “binned number”) and associated algorithms to reproducibly sum binary floating point numbers, independent of summation order. We use a subset of the IEEE Floating Point Standard 754-2008 and bitwise operations on the standard representations in memory. Our approach requires only one read-only pass over the data, and one reduction in parallel, using a 6-word reproducible accumulator (more words can be used for higher accuracy), enabling standard tiling optimization techniques. Summing n words with a 6-word reproducible accumulator requires approximately 9 n floating point operations (arithmetic, comparison, and absolute value) and approximately 3 n bitwise operations. The final error bound with a 6-word reproducible accumulator and our default settings can be up to 2 29 times smaller than the error bound for conventional (recursive) summation on ill-conditioned double-precision inputs.

Computer Science↗

A Synchronized Sensor Array for Remote Monitoring of Avian and Bat Interactions with Offshore Renewable Energy Facilities

Wind energy production in the U.S. is projected to increase to 35% of our nation’s energy by 2050. This substantial increase in the U.S. is only a portion of the global wind industry growth, as many countries strive to reduce greenhouse gas emissions. A major environmental concern and potential market barrier for expansion of wind energy is bird and bat mortality from impacts with turbine blades, towers, and nacelles. Carcass surveys are the standard protocol for quantifying mortality at onshore sites. This method is imperfect, however, due to survey frequency at remote sites, removal of carcasses by scavengers between surveys, searcher efficiency, and other biases as well as delays of days to weeks or more in obtaining information on collision events. Furthermore, carcass surveys are not feasible at offshore wind energy sites. Near-real-time detection and quantification of interaction rates is possible at both onshore and offshore wind facilities using an onboard, integrated sensor package with data transmitted to central processing centers. We developed and experimentally tested an array of sensors that continuously monitors for interactions (including impacts) of birds and bats with wind turbines. The synchronized array includes three sensor nodes: (1) vibration (accelerometers and contact microphones), (2) optical (visual and infrared spectrum cameras), and (3) bioacoustics (acoustic and ultrasonic microphones). Accelerometers and contact acoustic microphones are placed at the root of each blade to detect impact vibrations and sound waves propagating through the structure. On-board data processing algorithms using wavelet analysis detect impact signals exceeding background vibration. Stereo-visual and infrared cameras were placed on the nacelle to allow target tracking, distance, and size calculations. On-board image processing and target detection algorithms identify moving targets within the camera field of view. Bioacoustic recorders monitor vocalizations and echolocations to aid in identifying organisms involved in interactions. Data from all sensors are temporarily stored in ring (i.e., circular) buffers with a duration varying by sensor type. Detection of target presence or impact by any of the sensors can trigger the archiving of data from all buffers for transmission to a central data processing center for evaluation and post-processing. This mitigates the risk of “data mortgages” posed by continual recording and minimizes personnel time required to manually review event data. We first conducted individual component tests at laboratories and field sites in Corvallis and Newport, Oregon, and Seattle and Sequim, Washington. We conducted additional component tests on research wind turbines at the North American Wind Research and Training Center, Mesalands Community College (MCC; General Electric 1.5 MW turbine), New Mexico, and the National Wind Technology Center, National Renewable Energy Laboratory (NREL; Controls Advanced Research Turbines 3 [CART 3] 600 kW Westinghouse turbine), Colorado. We conducted fully integrated system tests at NREL in October 2014 and April 2015. We used only research wind turbines so that we could conduct controlled, experimentally generated impacts using empty and water-filled tennis balls shot from a compressed air cannon on the ground. The approx. 57-140 g tennis balls (depending on water content) were at the upper mass range for bats, but lower mass range for marine birds. Therefore, the ability to detect collisions of most seabirds is likely greater than our experiments demonstrate, but possibly lower for some bats depending on the background signal of a given turbine. Vibration data demonstrated that background signals of operating turbines varied markedly among the CART 3 under normal operation (greatest), GE (moderate), and CART 3 during idle rotation (generator not engaged; least). In total, we measured 63 experimental blade impacts on the two research turbines. Impaction detection was dependent on background signals, position of impact on the blade (a tip strike resulted in the strongest impact signal), and impact kinetics (velocity of ball and whether the ball struck the surface of the blade or the leading edge of the blade struck the ball). Overall detection percentage ranged from 100% for the “quietest” conditions (CART 3 idle rotation), down to 35% for the noisiest (CART 3 normal operation). Impact signals were detected from sensors on more than one blade (i.e., blades other than the blade struck) 50% - 75% of the time. Stereo imaging provided valuable metrics, but increased data processing and equipment cost. Given the cost of cameras with sufficient resolution for target identification, we suggest mounting cameras directly on the blades to continuously view the entire rotor swept area with the fewest number of cameras. Bioacoustic microphones provide taxonomic identification, as well as information on ambient noise levels. They also assist in identifying environmental conditions such as hail storms, high winds, thunder, lightning, etc., that may contribute to a collision or a false positive detection. We demonstrated a proof of concept for an integrated sensor array to detect and identify bird and bat collisions with wind turbines. The next phase of research and development for this system will miniaturize and integrate sensors from all three nodes into a single wireless package that can be attached directly to the blade. This next generation system would use all “smart” sensors capable of onboard data processing to drastically reduce data streams and processing time on a central computer. A provisional patent for the blade mounted system was submitted by Oregon State University and recorded by the U.S. Patent and Trademark Office (application no. 62313028). Eventually, technology and industry advances will allow this low cost monitoring system to be designed into materials during manufacturing so that all turbines could be monitored with either a subset or full suite of sensors. As standard equipment on all commercial turbines, the sensor suite would allow the industry to effectively monitor whether individual turbines were causing mortalities or not and under what circumstances. It would also provide real-time evaluation of mechanical and structural integrity of a turbine via vibration, image, and acoustic data streams, thereby permitting modifications in operation to limit environmental or mechanical damage.

17 WIND ENERGY↗

A Communication-Avoiding 3D LU Factorization Algorithm for Sparse Matrices

We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D sparse LU algorithm uses a three-dimensional MPI process grid, aggressively exploits elimination tree parallelism and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., from 2D grid or mesh domains) and certain non-planar graphs (specifically for 3D grids and meshes). For planar graphs with n vertices, our algorithm reduces communication volume asymptotically in n by a factor of O{log n} and latency by a factor of O{log n}. For non-planar cases, our algorithm can reduce the per-process communication volume by 3× and latency by O{n^1/3} times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in superLU. Our new 3D code achieves speedups up to 27× for planar graphs and up to 3.3× for non-planar graphs over the baseline 2D superLU when run on 24,000 cores of a Cray XC30.

Sao, Piyush↗

PDSLin User Guide

This document describes a software package which implements a parallel hybrid (direct/iterative) linear solver based on the Schur complement method for solving a general sparse linear system of equations. The package is named parallel domain decomposition Schur complement based linear solver, or PDSLin in short. We give a brief description of the algorithm, installation, calling sequences, and data structures of PDSLin.

97 MATHEMATICS AND COMPUTING↗

Clinical Natural Language Processing for Radiation Oncology: A Review and Practical Primer

Natural language processing (NLP), which aims to convert human language into expressions that can be analyzed by computers, is one of the most rapidly developing and widely used technologies in the field of artificial intelligence. Natural language processing algorithms convert unstructured free text data into structured data that can be extracted and analyzed at scale. In medicine, this unlocking of the rich, expressive data within clinical free text in electronic medical records will help untap the full potential of big data for research and clinical purposes. Recent major NLP algorithmic advances have significantly improved the performance of these algorithms, leading to a surge in academic and industry interest in developing tools to automate information extraction and phenotyping from clinical texts. Thus, these technologies are poised to transform medical research and alter clinical practices in the future. Radiation oncology stands to benefit from NLP algorithms if they are appropriately developed and deployed, as they may enable advances such as automated inclusion of radiation therapy details into cancer registries, discovery of novel insights about cancer care, and improved patient data curation and presentation at the point of care. However, challenges remain before the full value of NLP is realized, such as the plethora of jargon specific to radiation oncology, nonstandard nomenclature, a lack of publicly available labeled data for model development, and interoperability limitations between radiation oncology data silos. Successful development and implementation of high quality and high value NLP models for radiation oncology will require close collaboration between computer scientists and the radiation oncology community. Here, we present a primer on artificial intelligence algorithms in general and NLP algorithms in particular; provide guidance on how to assess the performance of such algorithms; review prior research on NLP algorithms for oncology; and describe future avenues for NLP in radiation oncology research and clinics.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

STUDIES IN ASTRONOMICAL TIME SERIES ANALYSIS. VI. BAYESIAN BLOCK REPRESENTATIONS

This paper addresses the problem of detecting and characterizing local variability in time series and other forms of sequential data. The goal is to identify and characterize statistically significant variations, at the same time suppressing the inevitable corrupting observational errors. We present a simple nonparametric modeling technique and an algorithm implementing it-an improved and generalized version of Bayesian Blocks-that finds the optimal segmentation of the data in the observation interval. The structure of the algorithm allows it to be used in either a real-time trigger mode, or a retrospective mode. Maximum likelihood or marginal posterior functions to measure model fitness are presented for events, binned counts, and measurements at arbitrary times with known error distributions. Problems addressed include those connected with data gaps, variable exposure, extension to piecewise linear and piecewise exponential representations, multivariate time series data, analysis of variance, data on the circle, other data modes, and dispersed data. Simulations provide evidence that the detection efficiency for weak signals is close to a theoretical asymptotic limit derived by Arias-Castro et al. In the spirit of Reproducible Research all of the code and data necessary to reproduce all of the figures in this paper are included as supplementary material.

79 ASTRONOMY AND ASTROPHYSICS↗

GPU-accelerated multitiered iterative phasing algorithm for fluctuation X-ray scattering

The multitiered iterative phasing (MTIP) algorithm is used to determine the biological structures of macromolecules from fluctuation scattering data. It is an iterative algorithm that reconstructs the electron density of the sample by matching the computed fluctuation X-ray scattering data to the external observations, and by simultaneously enforcing constraints in real and Fourier space. This paper presents the first ever MTIP algorithm acceleration efforts on contemporary graphics processing units (GPUs). The Compute Unified Device Architecture (CUDA) programming model is used to accelerate the MTIP algorithm on NVIDIA GPUs. The computational performance of the CUDA-based MTIP algorithm implementation outperforms the CPU-based version by an order of magnitude. Furthermore, the Heterogeneous-Compute Interface for Portability (HIP) runtime APIs are used to demonstrate portability by accelerating the MTIP algorithm across NVIDIA and AMD GPUs.

97 MATHEMATICS AND COMPUTING↗

Confidentiality-preserving machine learning algorithms for soft-failure detection in optical communication networks

Automated fault management is at the forefront of next-generation optical communication networks. The increase in complexity of modern networks has triggered the need for programmable and software-driven architectures to support the operation of agile and self-managed systems. In these scenarios, the European Telecommunications Standards Institute zero-touch network and service management approach is imperative. The need for machine learning algorithms to process the large volume of telemetry data brings safety concerns as distributed cloud-computing solutions become the preferred approach for deploying reliable communication network automation. This paper’s contribution is twofold. First, we propose a simple yet effective method to guarantee the confidentiality of the telemetry data based on feature scrambling. The method allows the operation of third-party computational services without direct access to the full content of the collected data. Additionally, the effectiveness of four unsupervised machine learning algorithms for soft-failure detection is evaluated when applied to the scrambled telemetry data. The methods are based on factor analysis, principal component analysis, nonlinear principal component analysis, and singular value decomposition. Most dimensionality reduction algorithms have the common property that they can maintain similar levels of fault classification performance while hiding the data structure from unauthorized access. Evaluations of the proposed algorithms demonstrate this capability.

97 MATHEMATICS AND COMPUTING↗

Timely Reporting of Heavy Hitters Using External Memory

Given an input stream S of size N, a Φ-heavy hitter is an item that occurs at least ΦN times in S. The problem of finding heavy-hitters is extensively studied in the database literature. In this work, we study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = Φ N-th occurrence (and hence it becomes a heavy hitter). We call this the Timely Event Detection (TED) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams with a low reporting threshold (high sensitivity). Like the classic heavy-hitters problem, solving the TED problem without false-positives requires large space (Ω (N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I/O-bandwidth (not latency) and support a tunable tradeoff between reporting delay and I/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I/O overhead. We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device’s random I/O throughput, i.e., ≈100K observations per second.

97 MATHEMATICS AND COMPUTING↗

Protein folds vs. protein folding: Differing questions, different challenges

We report protein fold prediction using deep-learning artificial intelligence (AI) has transformed the field of protein structure prediction. By combining physical and geometric constraints—and especially patterns extracted from the Protein Data Bank —these machine learning algorithms can predict protein structures at or near atomic resolution and do so in seconds. Today, these computational methods have now solved more than 200 million protein structures, which are accessible from the AlphaFold Protein Structure Database. This accomplishment seems all the more remarkable because few thought it possible or saw it coming. Deservedly, deep-learning AI was named Science magazine’s 2021 “breakthrough of the year”. Clearly, deep-learning AI represents a major advance in protein fold prediction.

54 ENVIRONMENTAL SCIENCES↗