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 721 records · Page 40

A parallel simulated annealing algorithm for standard cell placement on a hypercube computer

A parallel version of a simulated annealing algorithm is presented which is targeted to run on a hypercube computer. A strategy for mapping the cells in a two dimensional area of a chip onto processors in an n-dimensional hypercube is proposed such that both small and large distance moves can be applied. Two types of moves are allowed: cell exchanges and cell displacements. The computation of the cost function in parallel among all the processors in the hypercube is described along with a distributed data structure that needs to be stored in the hypercube to support parallel cost evaluation. A novel tree broadcasting strategy is used extensively in the algorithm for updating cell locations in the parallel environment. Studies on the performance of the algorithm on example industrial circuits show that it is faster and gives better final placement results than the uniprocessor simulated annealing algorithms. An improved uniprocessor algorithm is proposed which is based on the improved results obtained from parallelization of the simulated annealing algorithm.

Jones, Mark Howard↗

GPU-Based Static Data-Flow Analysis for Fast and Scalable Android App Vetting

Many popular vetting tools for Android applications use static code analysis techniques. In particular, Interprocedural Data-Flow Graph (IDFG) construction is the computation at the core of Android static data-flow analysis and consumes most of the analysis time. Many analysis tools use a worklist algorithm, an iterative fixed-point approach, to construct the IDFG. In this paper, we observe that a straightforward GPU parallelization of the worklist algorithm leads to significant underutilization of the GPU resources. We identify four performance bottlenecks, namely, frequent dynamic memory allocations, high branch divergence, workload imbalance, and irregular memory access patterns. Accordingly, we propose GDroid, a GPU-based worklist algorithm implementation with multiple fine-grained optimizations tailored to common characteristics of Android applications. The optimizations considered are: matrix-based data structure, memory access-based node grouping, and worklist merging. Our experimental evaluation, performed on 1000 Android applications, shows that the proposed optimizations are beneficial to performance, and GDroid can achieve up to 128X speedups against a plain GPU implementation.

Android security↗

The ANACONDA algorithm for deformable image registration in radiotherapy

Purpose: The purpose of this work was to describe a versatile algorithm for deformable image registration with applications in radiotherapy and to validate it on thoracic 4DCT data as well as CT/cone beam CT (CBCT) data. Methods: ANAtomically CONstrained Deformation Algorithm (ANACONDA) combines image information (i.e., intensities) with anatomical information as provided by contoured image sets. The registration problem is formulated as a nonlinear optimization problem and solved with an in-house developed solver, tailored to this problem. The objective function, which is minimized during optimization, is a linear combination of four nonlinear terms: 1. image similarity term; 2. grid regularization term, which aims at keeping the deformed image grid smooth and invertible; 3. a shape based regularization term which works to keep the deformation anatomically reasonable when regions of interest are present in the reference image; and 4. a penalty term which is added to the optimization problem when controlling structures are used, aimed at deforming the selected structure in the reference image to the corresponding structure in the target image. Results: To validate ANACONDA, the authors have used 16 publically available thoracic 4DCT data sets for which target registration errors from several algorithms have been reported in the literature. On average for the 16 data sets, the target registration error is 1.17 ± 0.87 mm, Dice similarity coefficient is 0.98 for the two lungs, and image similarity, measured by the correlation coefficient, is 0.95. The authors have also validated ANACONDA using two pelvic cases and one head and neck case with planning CT and daily acquired CBCT. Each image has been contoured by a physician (radiation oncologist) or experienced radiation therapist. The results are an improvement with respect to rigid registration. However, for the head and neck case, the sample set is too small to show statistical significance. Conclusions: ANACONDA performs well in comparison with other algorithms. By including CT/CBCT data in the validation, the various aspects of the algorithm such as its ability to handle different modalities, large deformations, and air pockets are shown.

60 APPLIED LIFE SCIENCES↗

A least-squares parameter estimation algorithm for switched hammerstein systems with applications to the VOR

A "Multimode" or "switched" system is one that switches between various modes of operation. When a switch occurs from one mode to another, a discontinuity may result followed by a smooth evolution under the new regime. Characterizing the switching behavior of these systems is not well understood and, therefore, identification of multimode systems typically requires a preprocessing step to classify the observed data according to a mode of operation. A further consequence of the switched nature of these systems is that data available for parameter estimation of any subsystem may be inadequate. As such, identification and parameter estimation of multimode systems remains an unresolved problem. In this paper, we 1) show that the NARMAX model structure can be used to describe the impulsive-smooth behavior of switched systems, 2) propose a modified extended least squares (MELS) algorithm to estimate the coefficients of such models, and 3) demonstrate its applicability to simulated and real data from the Vestibulo-Ocular Reflex (VOR). The approach will also allow the identification of other nonlinear bio-systems, suspected of containing "hard" nonlinearities.

Evaluation Studies↗

A new taxonomy for distributed computer systems based upon operating system structure

Characteristics of the resource structure found in the operating system are considered as a mechanism for classifying distributed computer systems. Since the operating system resources, themselves, are too diversified to provide a consistent classification, the structure upon which resources are built and shared are examined. The location and control character of this indivisibility provides the taxonomy for separating uniprocessors, computer networks, network computers (fully distributed processing systems or decentralized computers) and algorithm and/or data control multiprocessors. The taxonomy is important because it divides machines into a classification that is relevant or important to the client and not the hardware architect. It also defines the character of the kernel O/S structure needed for future computer systems. What constitutes an operating system for a fully distributed processor is discussed in detail.

Foudriat, E. C.↗

Can I solve my structure by SAD phasing? Planning an experiment, scaling data and evaluating the useful anomalous correlation and anomalous signal

A key challenge in the SAD phasing method is solving a structure when the anomalous signal-to-noise ratio is low. Here, we describe algorithms and tools for evaluating and optimizing the useful anomalous correlation and the anomalous signal in a SAD experiment. A simple theoretical framework [Terwilliger et al. (2016), Acta Cryst. D 72 , 346–358] is used to develop methods for planning a SAD experiment, scaling SAD data sets and estimating the useful anomalous correlation and anomalous signal in a SAD data set. The phenix.plan_sad_experiment tool uses a database of solved and unsolved SAD data sets and the expected characteristics of a SAD data set to estimate the probability that the anomalous substructure will be found in the SAD experiment and the expected map quality that would be obtained if the substructure were found. The phenix.scale_and_merge tool scales unmerged SAD data from one or more crystals using local scaling and optimizes the anomalous signal by identifying the systematic differences among data sets, and the phenix.anomalous_signal tool estimates the useful anomalous correlation and anomalous signal after collecting SAD data and estimates the probability that the data set can be solved and the likely figure of merit of phasing.

59 BASIC BIOLOGICAL SCIENCES↗

Concentration Measurements in Self-Excited, Momentum-Dominated Helium Jets

Flow structure of momentum-dominated pure helium jets discharged vertically into ambient air was investigated using high-speed rainbow schlieren deflectometry (RSD) technique. Effects of the operating parameters, i.e., Reynolds number (Re) and Richardson number (Ri), on the oscillatory behavior of the flow were examined over a range of experimental conditions. To seek the individual effect of these parameters, one of them was fixed and the other was varied with certain constraints. Measurements revealed highly periodic oscillations in the laminar region as well as high regularity in transition and turbulent regions. Maximum spectral power profiles at different axial locations indicated the oscillation amplitude increasing until the breakdown of the jet in the turbulent regime. The transition from the laminar to turbulent flow was also investigated. Fast Fourier transform analysis performed in the transition regime showed that the flow oscillates at a unique frequency, which was the same in the upstream laminar flow region. Measured deflection angle data were used in Abel inversion algorithm to construct the helium concentration fields. Instantaneous helium concentration contours revealed changes in the flow structure and evolution of vortical structures during an oscillation cycle. Temporal evolution plots of helium concentration at different axial location showed repeatable oscillations at all axial and radial locations up to the turbulent regime. A cross-correlation technique, applied to find the spatial displacements of the vortical structures, provided correlation coefficient peaks between consecutive schlieren images. Results show that the vortical structure convected and accelerated only in the axial direction.

Yildirim, Bekir Sedat↗

Elusive Structural, Functional, and Immunological Features of Act d 5, the Green Kiwifruit Kiwellin

Kiwellin (Act d 5) is an allergenic protein contained in kiwifruit pulp in high amounts. The purpose of this study was to investigate the three-dimensional structure of the natural molecule from green kiwifruit and its possible function. Kiwellin was crystallized, and its structure, including post-translational modifications, was elucidated. The molecular weight and structural features, in solution, were analyzed by gel filtration and circular dichroism, respectively. Although structurally similar to expansin, kiwellin lacks expansin activity and carbohydrate binding. A specific algorithm was applied to investigate any possible IgE reactivity correlation between kiwellin and a panel of 102 allergens, including expansins and other carbohydrate-binding allergens. The available data suggest a strong dependence of the kiwellin structure on the environmental/experimental conditions. This dependence therefore poses challenges in detecting the correlations between structural, functional, and immunological features of this protein.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

BCL::MP-fold: Membrane protein structure prediction guided by EPR restraints

For many membrane proteins, the determination of their topology remains a challenge for methods like X-ray crystallography and nuclear magnetic resonance (NMR) spectroscopy. Electron paramagnetic resonance (EPR) spectroscopy has evolved as an alternative technique to study structure and dynamics of membrane proteins. The present study demonstrates the feasibility of membrane protein topology determination using limited EPR distance and accessibility measurements. The BCL::MP-Fold (BioChemical Library membrane protein fold) algorithm assembles secondary structure elements (SSEs) in the membrane using a Monte Carlo Metropolis (MCM) approach. Sampled models are evaluated using knowledge-based potential functions and agreement with the EPR data and a knowledge-based energy function. Twenty-nine membrane proteins of up to 696 residues are used to test the algorithm. The RMSD100 value of the most accurate model is better than 8 Å for 27, better than 6 Å for 22, and better than 4 Å for 15 of the 29 proteins, demonstrating the algorithms' ability to sample the native topology. The average enrichment could be improved from 1.3 to 2.5, showing the improved discrimination power by using EPR data. Proteins 2015; 83:1947–1962. © 2015 Wiley Periodicals, Inc

Biochemistry & Molecular Biology↗

On the role of dimensionality and sample size for unstructured and structured covariance matrix estimation

The experimental observation that a surprisingly small sample size vis-a-vis dimension is needed to achieve good signal-to-interference ratio (SIR) performance with an adaptive predetection filter is explained. The adaptive filter requires estimates as obtained by a recursive stochastic algorithm of the inverse of the filter input data covariance matrix. The SIR performance with sample size is compared for the situations where the covariance matrix estimates are of unstructured (generalized) form and of structured (finite Toeplitz) form; the latter case is consistent with weak stationarity of the input data stochastic process.

Morgera, S. D.↗

A Framework for Lattice QCD Calculations on GPUs

Efficient calculation of the greatest common divisor (GCD) for big integers each whose number of bits is greater than or equal to 1024 has drawn a considerable amount of attention because it can be used to detect a weakness of the RSA security infrastructure. This paper presents a parallel binary GCD algorithm and its implementation for big integers on the Intel Xeon Phi coprocessor. This algorithm is capable of computing GCDs efficiently on many pairs of big integers in parallel by utilizing all cores on a Xeon Phi coprocessor as well as taking advantage of all vector processing units of the coprocessor to speed up critical integer operations within the algorithm. Using 240 threads on a Xeon Phi coprocessor to carry out GCD calculations for a large amount of 2048-bit integers, the implementation achieves the speedup of 30 times over a sequential binary GCD algorithm implementation on a single CPU core, and it delivers twice amount of performance in comparison to the same sequential binary GCD implementation running on 240 threads of the Xeon Phi.

Winter, F. T.↗

On the use of NMR distance measurements for assessing surface site homogeneity

The past few decades have seen tremendous growth in the area of single-site heterogeneous catalysis, which aims to combine the best aspects of homogeneous and heterogeneous catalysis, namely molecular-level site control and ease of separation/recycling. Despite this, we still do not have a means of assessing site homogeneity and whether the produced catalyst is indeed a “single-site”. Recent developments have enabled the use of NMR-based distance measurements to determine the conformations and configurations of surface sites, leading to the question whether such measurements can be used to distinguish materials containing either single or multiple surface sites with otherwise indistinguishable NMR properties. Here, we describe a Monte Carlo-based multi-structure search algorithm and its application to the determination of multi-site structures from supported metal complexes. The sensitivity of REDOR data to the existence of multiple sites is assessed using synthetic data and prior literature examples are revisited to determine whether the single-site approximation was indeed appropriate. We lastly apply this new methodology to differentiate the configurations of zirconocene complexes grafted onto alumina supports that were thermally treated at different temperatures.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Machine learning enables identification of an alternative yeast galactose utilization pathway

How genomic differences contribute to phenotypic differences is a major question in biology. The recently characterized genomes, isolation environments, and qualitative patterns of growth on 122 sources and conditions of 1,154 strains from 1,049 fungal species (nearly all known) in the yeast subphylum Saccharomycotina provide a powerful, yet complex, dataset for addressing this question. We used a random forest algorithm trained on these genomic, metabolic, and environmental data to predict growth on several carbon sources with high accuracy. Known structural genes involved in assimilation of these sources and presence/absence patterns of growth in other sources were important features contributing to prediction accuracy. By further examining growth on galactose, we found that it can be predicted with high accuracy from either genomic (92.2%) or growth data (82.6%) but not from isolation environment data (65.6%). Prediction accuracy was even higher (93.3%) when we combined genomic and growth data. After the GALactose utilization genes, the most important feature for predicting growth on galactose was growth on galactitol, raising the hypothesis that several species in two orders, Serinales and Pichiales (containing the emerging pathogen Candida auris and the genus Ogataea, respectively), have an alternative galactose utilization pathway because they lack the GAL genes. Growth and biochemical assays confirmed that several of these species utilize galactose through an alternative oxidoreductive D-galactose pathway, rather than the canonical GAL pathway. Machine learning approaches are powerful for investigating the evolution of the yeast genotype–phenotype map, and their application will uncover novel biology, even in well-studied traits.

59 BASIC BIOLOGICAL SCIENCES↗

MO-F-CAMPUS-T-02: Optimizing Orientations of Hundreds of Intensity-Modulated Beams to Treat Multiple Brain Targets

Purpose: To investigate a new modulated beam orientation optimization (MBOO) approach maximizing treatment planning quality for the state-of-the-art flattening filter free (FFF) beam that has enabled rapid treatments of multiple brain targets. Methods: MBOO selects and optimizes a large number of intensity-modulated beams (400 or more) from all accessible beam angles surrounding a patient’s skull. The optimization algorithm was implemented on a standalone system that interfaced with the 3D Dicom images and structure sets. A standard published data set that consisted of 1 to 12 metastatic brain tumor combinations was selected for MBOO planning. The planning results from various coplanar and non-coplanar configurations via MBOO were then compared with the results obtained from a clinical volume modulated arc therapy (VMAT) delivery system (Truebeam RapidArc, Varian Oncology). Results: When planning a few number of targets (n<4), MBOO produced results equivalent to non-coplanar multi-arc VMAT planning in terms of target volume coverage and normal tissue sparing. For example, the 12-Gy and 4-Gy normal brain volumes for the 3-target plans differed by less than 1 mL ( 3.0 mLvs 3.8 mL; and 35.2 mL vs 36.3 mL, respectively) for MBOO versus VMAT. However, when planning a larger number of targets (n≥4), MBOO significantly reduced the dose to the normal brain as compared to VMAT, though the target volume coverage was equivalent. For example, the 12-Gy and 4-Gy normal brain volumes for the 12-target plans were 10.8 mL vs. 18.0 mL and 217.9 mL vs. 390.0 mL, respectively for the non-coplanar MBOO versus the non-coplanar VMAT treatment plans, yielding a reduction in volume of more than 60% for the case. Conclusion: MBOO is a unique approach for maximizing normal tissue sparing when treating a large number (n≥4) of brain tumors with FFF linear accelerators. Dr Ma and Dr Sahgal are currently on the board of international society of stereotactic radiosurgery. Dr Sahgal has received support for educational presentations from Elekta company.

60 APPLIED LIFE SCIENCES↗

Predictive Data Analytics Framework Using Advanced Test Reactor Acoustic Data

Although a nuclear reactor is a hostile environment for sensing and electrical communications, the reactor core is amenable to acoustic communication. An acoustic measurement infrastructure (AMI) has been installed at the Advanced Test Reactor (ATR) nozzle trench area to record acoustic signals that has the ability to capture different operating regime of the reactor. This AMI includes ATR in-pile structural components, coolant, acoustic receivers, primary coolant pumps (PCP) as signal sources, a data acquisition system, and signal-processing algorithms, enabling real-time. This report will discusses development of recursive Fast Fourier Transform approach to process in real-time acoustic signals, application of short time Fast Fourier Transform to the ATR brush data to understand the vibration level and to develop spectrograms for different primary coolant pump combinations. The combination of primary coolant pumps for normal and power axial locator mechanism of ATR are different and generates different signatures. These acoustic signatures were used to develop machine learning approaches to automatically classify different operating regimes. This lay the foundation for predictive analytic framework that can be leverage by ATR to optimize their operation and maintenance. The path forward involves continued engagement with ATR and expanded implementation of AMI and predictive framework at ATR and other facilities within INL and at other experimental reactors.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Synthesis of stiffness and mass matrices from experimental vibration modes.

With highly complex structures, it is sometimes desirable to derive a dynamic model of the system from experimental vibration data. This paper presents algorithms for synthesizing the mass and stiffness matrices from experimentally derived modal data in a way which preserves the physical significance of the individual mass and stiffness elements. The synthesizing procedures allow for the incorporation of other mass and stiffness data, whether empirical or based on the analyst's insight. The mass and stiffness matrices are derived for a cantilever beam example and are compared with those obtained using earlier techniques.

Ross, R. G., Jr.↗

Nonlinear effect on modal data analysis method

How the presence of nonlinearities in structural test data can be detected when using modern linear modal data analysis methods is discussed. The extent to which linear algorithms can provide useful information on nonlinear systems was discussed. The modal data analysis method successfully identified the frequency components (but not damping) of the true solution of a nonlinear systems. It was found that the approximate modal parameters of the linear system can be identified by the modal method when low levels of nonlinearities are present. The modal method successfully identified the modal parameters of a linear mode in the presence of a nonlinear response.

Horta, L. G.↗