Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,153 records · Page 64

Evaluating In-Clique and Topological Parallelism Strategies for Junction Tree-Based Bayesian Inference Algorithm on the Cray XMT

Long viewed as a strong statistical inference technique, Bayesian networks have emerged to be an important class of applications for high-performance computing. We have applied an architecture-conscious approach to parallelizing the Lauritzen-Spiegelhalter Junction Tree algorithm for exact inferencing in Bayesian networks. In optimizing the Junction Tree algorithm, we have implemented both in-clique and topological parallelism strategies to best leverage the fine-grained synchronization and massive-scale multithreading of the Cray XMT architecture. Two topological techniques were developed to parallelize the evidence propagation process through the Bayesian network. One technique involves performing intelligent scheduling of junction tree nodes based on its topology and relative size. The second technique involves decomposing the junction tree into a much finer tree-like representation to offer much more opportunities for parallelism. We evaluate these optimizations on five different Bayesian networks and report our findings and observations. Another important contribution of this paper is to demonstrate the application of massive-scale multithreading for load balancing and use of implicit parallelism-based compiler optimizations in designing scalable inferencing algorithms.

99 GENERAL AND MISCELLANEOUS↗

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗

Algorithm and Architecture Independent Benchmarking with SEAK

Many applications of high performance embedded computing are limited by performance or power bottlenecks. We have designed the Suite for Embedded Applications & Kernels (SEAK), a new benchmark suite, (a) to capture these bottlenecks in a way that encourages creative solutions; and (b) to facilitate rigorous, objective, end-user evaluation for their solutions. To avoid biasing solutions toward existing algorithms, SEAK benchmarks use a mission-centric (abstracted from a particular algorithm) and goal-oriented (functional) specification. To encourage solutions that are any combination of software or hardware, we use an end-user black-box evaluation that can capture tradeoffs between performance, power, accuracy, size, and weight. The tradeoffs are especially informative for procurement decisions. We call our benchmarks future proof because each mission-centric interface and evaluation remains useful despite shifting algorithmic preferences. It is challenging to create both concise and precise goal-oriented specifications for mission-centric problems. This paper describes the SEAK benchmark suite and presents an evaluation of sample solutions that highlights power and performance tradeoffs.

algorithms and kernels↗

Designing Topology-Aware Collective Communication Algorithms for Large Scale InfiniBand Clusters: Case Studies with Scatter and Gather

Modern high performance computing systems are being increasingly deployed in a hierarchical fashion with multi-core computing platforms forming the base of the hierarchy. These systems are usually comprised of multiple racks, with each rack consisting of a finite number of chassis, with each chassis having multiple compute nodes or blades, based on multi-core architectures. The networks are also hierarchical with multiple levels of switches. Message exchange operations between processes that belong to different racks involve multiple hops across different switches and this directly affects the performance of collective operations. In this paper, we take on the challenges involved in detecting the topology of large scale InfiniBand clusters and leveraging this knowledge to design efficient topology-aware algorithms for collective operations. We also propose a communication model to analyze the communication costs involved in collective operations on large scale supercomputing systems. We have analyzed the performance characteristics of two collectives, MPI_Gather and MPI_Scatter on such systems and we have proposed topology-aware algorithms for these operations. Our experimental results have shown that the proposed algorithms can improve the performance of these collective operations by almost 54% at the micro-benchmark level.

97 MATHEMATICS AND COMPUTING↗

An Approximation Algorithm for a Task Allocation, Sequencing and Scheduling Problem Involving a Human-Robot Team

Here we present an approximation algorithm for a Task Allocation, Sequencing and Scheduling Problem (TASSP) involving a team of human operators and robots. The robots have to travel to a given set of targets and collaboratively work on the tasks at the targets with the human operators. The problem aims to find a sequence of targets for each robot to visit and schedule the tasks at the targets with the human operators such that each target is visited exactly once by some robot, the scheduling constraints are satisfied and the maximum mission time of any robot is minimum. This problem is a generalization of the single Traveling Salesman Problem and is NP-Hard. Given k robots and m human operators, an algorithm is developed for solving the TASSP with an approximation ratio equal to 5/2- 1/k when m ≥ k and equal to 7/2 -1/k otherwise. Computational results are also presented to corroborate the performance of the proposed algorithm.

42 ENGINEERING↗

A Recursive Multiscale Correlation-Averaging Algorithm for an Automated Distributed Road Condition Monitoring System

A signal processing approach is proposed to jointly filter and fuse spatially indexed measurements captured from many vehicles. It is assumed that these measurements are influenced by both sensor noise and measurement indexing uncertainties. Measurements from low-cost vehicle-mounted sensors (e.g., accelerometers and Global Positioning System (GPS) receivers) are properly combined to produce higher quality road roughness data for cost-effective road surface condition monitoring. The proposed algorithms are recursively implemented and thus require only moderate computational power and memory space. These algorithms are important for future road management systems, which will use on-road vehicles as a distributed network of sensing probes gathering spatially indexed measurements for condition monitoring, in addition to other applications, such as environmental sensing and/or traffic monitoring. Our method and the related signal processing algorithms have been successfully tested using field data.

47 OTHER INSTRUMENTATION↗

Generation of Synthetic Data for a Radiation Detection Algorithm Competition

This paper details the generation of synthetic radiation data using large-scale Monte Carlo transport models to evaluate radiation search detection algorithms. Modular 3-D Monte Carlo models spanning multiple city blocks were constructed, loosely based on downtown Knoxville, TN, containing buildings composed of multiple materials (brick, granite, and concrete), sidewalks, a four-lane road, side streets, parking lots, and grassy fields. Background and simulated source detector response calculations from these models were used to create synthetic list mode data sets for a 2"×4"×16" NaI(Tl) detector moving through a city street at a constant speed. For the background simulations, major isotopes were computed individually so that background composition and variability could be computed efficiently outside Monte Carlo. The source detector response included six simulated sources placed at 15 source locations. Detector response was developed to be periodic through the city street so that a detector path could begin at one end of the model and wrap around to the other. This framework allowed for the creation of diverse data sets, each with its own unique background and simulated source detector response. Synthetic data allows for high-quality labels, which are useful in developing data-driven radiation detection algorithms. This methodology was used to create synthetic data sets which were released as part of a public data competition to spur the development of new radiation detection algorithms for radiological search applications.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Controller-Based Energy-Aware Wireless Sensor Network Routing Using Quantum Algorithms

Energy-efficient routing in wireless sensor networks has attracted attention from researchers in both academia and industry, most recently motivated by the opportunity to use software-defined network-inspired approaches. These problems are NP-hard, with algorithms needing computation time that scales faster than polynomials in the problem size. Consequently, heuristic algorithms are used in practice, which are unable to guarantee optimally. In this article, we show proof-of-principle for the use of a quantum annealing processor instead of a classical processor, to find optimal or nearly optimal solutions very quickly. Our preliminary results for small networks show that this approach using quantum computing has great promise and may open the door for other significant improvements in the efficacy of network algorithms.

42 ENGINEERING↗

Analog In-Memory Computing for the Synthetic Aperture Radar Polar Format Algorithm

As the utility of synthetic aperture radar (SAR) systems increases in autonomous vehicles, satellites, and other power- and space-constrained edge applications, there is a growing need for processors that can form SAR images at low power. In recent years, analog in-memory compute (AIMC) has shown immense promise for accelerating neural networks and other matrix-vector multiplication (MVM) heavy workloads at the edge. Here, in this work, we examine how the polar format algorithm (PFA), a popular SAR image formation algorithm, can be mapped to these AIMC systems. The PFA maps readily onto analog MVMs because it primarily consists of two linear operations: interpolation of frequency-domain data to a Cartesian grid, followed by a 2-D Fourier transform. This work presents two approaches to map the interpolation operation onto MVMs in analog hardware: a chirp transform and a modified form of sinc interpolation. These mappings introduce algorithmic errors, and their effect on the quality of SAR image formation is examined, both quantitatively and qualitatively. In addition, the impact of errors introduced by the analog hardware is explored to determine which approach is optimal under varying assumptions about the underlying analog memory devices and circuits.

Analog computing↗

Accurate Consensus-based Distributed Averaging with Variable Time Delay in Support of Distributed Secondary Control Algorithms

We report that distributed secondary control has been widely used in hierarchical control structures, where multiple distributed generators (DGs) need to coordinate to regulate system voltage and frequency. In these systems, consensus algorithms determine the average of a group of dynamic states (e.g. voltages measured by a group of DGs). To be useful, consensus algorithms must be computationally efficient, stable and accurate. In practice, numerous practical implementation challenges significantly affect the consensus equilibrium. In this paper, we quantify the accuracy deviations of the distributed average observer algorithms proposed in the literature to demonstrate the problems with the state-of-the-art distributed averaging techniques. A novel approach is proposed that achieves accurate average tracking in the presence of time-varying communication delays among agents. In our implementation, time synchronization of all distributed controllers is enabled by a novel software platform, called Resilient Information Architecture Platform for the Smart Grid (RIAPS). The proposed distributed average observer is implemented on hardware controllers and its effectiveness is validated in a controller hardware-in-the-loop testbed.

24 POWER TRANSMISSION AND DISTRIBUTION↗

A Parallel Domain Decomposition BEM Algorithm for Three Dimensional Exponentially Graded Elasticity

A parallel domain decomposition boundary integral algorithm for three-dimensional exponentially graded elasticity has been developed. As this subdomain algorithm allows the grading direction to vary in the structure, geometries arising from practical FGM applications can be handled. Moreover, the boundary integral algorithm scales well with the number of processors, also helping to alleviate the high computational cost of evaluating the Green's function. Numerical results for cylindrical geometries show excellent agreement with the new analytical solution deduced for axisymmetric plane strain states in a radially graded material.

97 MATHEMATICS AND COMPUTING↗

A material interface transition algorithm for multiphase flow

Volume tracking method, also referred to as the volume-of-fluid (VOF) method introduces 'numerical surface tension' that breaks a filament into a series of droplets whenever the filament is under-resolved. Adaptive mesh refinement can help avoid under-resolution, but a fully-developed flow will still generate filaments that cannot be resolved without enormous computational cost. We propose a complementary new approach that consists of transitioning to a continuous interface representation (i.e. without interface reconstruction) in regions of under-resolved interfacial curvature where volume tracking has become erroneous. The price of the continuous interface treatment is a small amount of numerica'l mass diffusion, even if the physical interface is immiscible. However, we have found that for certain measures, the overall accuracy is greatly improved by using our transitioning algorithm. The algorithm is developed in the context of the single fluid formulation of the incompressible Navier-Stokes equations. Numerical standard vortices advection test cases and Rayleigh-Taylor instability computations are presented to illustrate the transition algorithm potential.

42 ENGINEERING↗

Description of reaction and vibrational energetics of CO 2 –NH 3 interaction using quantum computing algorithms

CO 2 capture is critical to solving global warming. Amine-based solvents are extensively used to chemically absorb CO 2 . Thus, it is crucial to study the chemical absorption of CO 2 by amine-based solvents to better understand and optimize CO 2 capture processes. Here, we use quantum computing algorithms to quantify molecular vibrational energies and reaction pathways between CO 2 and a simplified amine-based solvent model—NH 3 . Molecular vibrational properties are important to understanding kinetics of reactions. However, the molecule size correlates with the strength of anharmonicity effect on vibrational properties, which can be challenging to address using classical computing. Quantum computing can help enhance molecular vibrational calculations by including anharmonicity. We implement a variational quantum eigensolver (VQE) algorithm in a quantum simulator to calculate ground state vibrational energies of reactants and products of the CO 2 and NH 3 reaction. The VQE calculations yield ground vibrational energies of CO 2 and NH 3 with similar accuracy to classical computing. In the presence of hardware noise, Compact Heuristic for Chemistry (CHC) ansatz with shallower circuit depth performs better than Unitary Vibrational Coupled Cluster. The “Zero Noise Extrapolation” error-mitigation approach in combination with CHC ansatz improves the vibrational calculation accuracy. Excited vibrational states are accessed with quantum equation of motion method for CO 2 and NH 3 . Using quantum Hartree–Fock (HF) embedding algorithm to calculate electronic energies, the corresponding reaction profile compares favorably with Coupled Cluster Singles and Doubles while being more accurate than HF. Our research showcases quantum computing applications in the study of CO 2 capture reactions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

An algorithm for shifting MLC shapes to adjust for daily prostate movement during concurrent treatment with pelvic lymph nodes

Concurrent treatment of the prostate and the pelvic lymph nodes encounters the problem of the prostate gland moving independently from the pelvic lymph nodes on a daily basis. The purpose of this study is to develop a leaf-tracking algorithm for adjustment of IMRT portals without requirement of online dose calculation to account for daily prostate position during concurrent treatment with pelvic lymph nodes. A leaf-shifting algorithm was developed and programmed to adjust the positions of selected MLC leaf pairs according to prostate movement in the plane perpendicular to each beam angle. IMRT plans from five patients with concurrent treatment of the prostate and pelvic lymph nodes were selected to test the feasibility of this algorithm by comparison with isocenter-shifted plans, using defined dose endpoints. When the prostate moved 0.5, 1.0, and 1.5 cm along the anterior/posterior direction, the average doses to 95% of the prostate (D{sub 95%}) for the iso-shift plans were similar to the MLC-shift plans, (54.7, 54.4, and 54.1 Gy versus 54.5, 54.3, and 53.9 Gy, respectively). The corresponding D{sub 95%} averages to the pelvic lymph nodes were reduced from the prescription dose of 45 Gy to 42.7, 38.3, and 34.0 Gy for iso-shift plans (p=0.04 for each comparison), while the D{sub 95%} averages for the MLC-shift plans did not significantly differ from the prescription dose, at 45.0, 44.8, and 44.5 Gy. Compensation for prostate movement along the superior/inferior direction was more complicated due to a limiting MLC leaf width of 1.0 cm. In order to concurrently treat the prostate and pelvic lymph nodes with the prostate moving independently, shifting selected MLC leaf pairs may be a more practical adaptive solution than shifting the patient.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

An independent algorithm to check the monitor units calculation in radiosurgery

Double checking of the monitor units (MU) is an important step in the quality assurance (QA) process in radiosurgery. In this paper we propose the use of an independent algorithm constructed using the ellipsoid which best fits the measurements taken with the bubble head frame. The monitor units calculated by this independent algorithm and the commercial planning system were compared in 40 patients treated with radiosurgery (57 isocenters, 320 arcs). The average relative difference was -0.2%{+-}2.1 (k=1). These results are better for the variance, -0.4%{+-}1.8 (k=1), when all the depths of the bubble head frame are measured and no arcs are calculated by extrapolation or when only one of these factors appear. If there are missing values in the bubble head frame measurements and the model is extrapolated, the variance of the results is greater, 0.4%{+-}3.9 (k=1). The algorithm is reliable as a QA tool for linac radiosurgery.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Testing the GLAaS algorithm for dose measurements on low- and high-energy photon beams using an amorphous silicon portal imager

The GLAaS algorithm for pretreatment intensity modulation radiation therapy absolute dose verification based on the use of amorphous silicon detectors, as described in Nicolini et al. [G. Nicolini, A. Fogliata, E. Vanetti, A. Clivio, and L. Cozzi, Med. Phys. 33, 2839-2851 (2006)], was tested under a variety of experimental conditions to investigate its robustness, the possibility of using it in different clinics and its performance. GLAaS was therefore tested on a low-energy Varian Clinac (6 MV) equipped with an amorphous silicon Portal Vision PV-aS500 with electronic readout IAS2 and on a high-energy Clinac (6 and 15 MV) equipped with a PV-aS1000 and IAS3 electronics. Tests were performed for three calibration conditions: A: adding buildup on the top of the cassette such that SDD-SSD=d{sub max} and comparing measurements with corresponding doses computed at d{sub max}, B: without adding any buildup on the top of the cassette and considering only the intrinsic water-equivalent thickness of the electronic portal imaging devices device (0.8 cm), and C: without adding any buildup on the top of the cassette but comparing measurements against doses computed at d{sub max}. This procedure is similar to that usually applied when in vivo dosimetry is performed with solid state diodes without sufficient buildup material. Quantitatively, the gamma index ({gamma}), as described by Low et al. [D. A. Low, W. B. Harms, S. Mutic, and J. A. Purdy, Med. Phys. 25, 656-660 (1998)], was assessed. The {gamma} index was computed for a distance to agreement (DTA) of 3 mm. The dose difference {delta}D was considered as 2%, 3%, and 4%. As a measure of the quality of results, the fraction of field area with gamma larger than 1 (%FA) was scored. Results over a set of 50 test samples (including fields from head and neck, breast, prostate, anal canal, and brain cases) and from the long-term routine usage, demonstrated the robustness and stability of GLAaS. In general, the mean values of %FA remain below 3% for {delta}D equal or larger than 3%, while they are slightly larger for {delta}D=2% with %FA in the range from 3% to 8%. Since its introduction in routine practice, 1453 fields have been verified with GLAaS at the authors' institute (6 MV beam). Using a DTA of 3 mm and a {delta}D of 4% the authors obtained %FA=0.9{+-}1.1 for the entire data set while, stratifying according to the dose calculation algorithm, they observed: %FA=0.7{+-}0.9 for fields computed with the analytical anisotropic algorithm and %FA=2.4{+-}1.3 for pencil-beam based fields with a statistically significant difference between the two groups. If data are stratified according to field splitting, they observed %FA=0.8{+-}1.0 for split fields and 1.0{+-}1.2 for nonsplit fields without any significant difference.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Improving intensity-modulated radiation therapy using the anatomic beam orientation optimization algorithm

A novel, anatomic beam orientation optimization (A-BOO) algorithm is proposed to significantly improve conventional intensity-modulated radiation therapy (IMRT). The A-BOO algorithm vectorially analyses polygonal surface mesh data of contoured patient anatomy. Five optimal (5-opt) deliverable beam orientations are selected based on (1) tangential orientation bisecting the target and adjacent organ's-at-risk (OARs) to produce precipitous dose gradients between them and (2) parallel incidence with polygon features of the target volume to facilitate conformal coverage. The 5-opt plans were compared to standard five, seven, and nine equiangular-spaced beam plans (5-equi, 7-equi, 9-equi) for: (1) gastric, (2) Radiation Therapy Oncology Group (RTOG) P-0126 prostate, and (3) RTOG H-0022 oropharyngeal (stage-III, IV) cancer patients. In the gastric case, the noncoplanar 5-opt plan reduced the right kidney V 20 Gy by 32.2%, 23.2%, and 20.6% compared to plans with five, seven, and nine equiangular-spaced beams. In the prostate case, the coplanar 5-opt plan produced similar rectal sparing as the 7-equi and 9-equi plans with a reduction of the V 75, V 70, V 65, and V 60 Gy of 2.4%, 5.3%, 7.0%, and 9.5% compared to the 5-equi plan. In the stage-III and IV oropharyngeal cases, the noncoplanar 5-opt plan substantially reduced the V 30 Gy and mean dose to the contralateral parotid compared to plans with five, seven, and nine equiangular-spaced beams: (stage-III) 7.1%, 5.2%, 6.8%, and 5.1, 3.5, 3.7 Gy and (stage-IV) 10.2%, 10.2%, 9.8% and 7.0, 7.1, 7.2 Gy. The geometry-based A-BOO algorithm has been demonstrated to be robust for application to a variety of IMRT treatment sites. Beam orientations producing significant improvements in OAR sparing over conventional IMRT can be automatically produced in minutes compared to hours with existing dose-based beam orientation optimization methods.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Effect of nonlinear three-dimensional optimized reconstruction algorithm filter on image quality and radiation dose: Validation on phantoms

A new technique called the nonlinear three-dimensional optimized reconstruction algorithm filter (3D ORA filter) is currently used to improve CT image quality and reduce radiation dose. This technical note describes the comparison of image noise, slice sensitivity profile (SSP), contrast-to-noise ratio, and modulation transfer function (MTF) on phantom images processed with and without the 3D ORA filter, and the effect of the 3D ORA filter on CT images at a reduced dose. For CT head scans the noise reduction was up to 54% with typical bone reconstruction algorithms (H70) and a 0.6 mm slice thickness; for liver CT scans the noise reduction was up to 30% with typical high-resolution reconstruction algorithms (B70) and a 0.6 mm slice thickness. MTF and SSP did not change significantly with the application of 3D ORA filtering (P>0.05), whereas noise was reduced (P<0.05). The low contrast detectability and MTF of images obtained at a reduced dose and filtered by the 3D ORA were equivalent to those of standard dose CT images; there was no significant difference in image noise of scans taken at a reduced dose, filtered using 3D ORA and standard dose CT (P>0.05). The 3D ORA filter shows good potential for reducing image noise without affecting image quality attributes such as sharpness. By applying this approach, the same image quality can be achieved whilst gaining a marked dose reduction.

62 RADIOLOGY AND NUCLEAR MEDICINE↗