Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Software 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,063 records · Page 59

Batched matrix computations on hardware accelerators based on GPUs

Scientific applications require solvers that work on many small size problems that are independent from each other. At the same time, the high-end hardware evolves rapidly and becomes ever more throughput-oriented and thus there is an increasing need for an effective approach to develop energy-efficient, high-performance codes for these small matrix problems that we call batched factorizations. The many applications that need this functionality could especially benefit from the use of GPUs, which currently are four to five times more energy efficient than multicore CPUs on important scientific workloads. This study, consequently, describes the development of the most common, one-sided factorizations, Cholesky, LU, and QR, for a set of small dense matrices. The algorithms we present together with their implementations are, by design, inherently parallel. In particular, our approach is based on representing the process as a sequence of batched BLAS routines that are executed entirely on a GPU. Importantly, this is unlike the LAPACK and the hybrid MAGMA factorization algorithms that work under drastically different assumptions of hardware design and efficiency of execution of the various computational kernels involved in the implementation. Thus, our approach is more efficient than what works for a combination of multicore CPUs and GPUs for the problems sizes of interest of the application use cases. The paradigm where upon a single chip (a GPU or a CPU) factorizes a single problem at a time is not at all efficient in our applications’ context. We illustrate all of these claims through a detailed performance analysis. With the help of profiling and tracing tools, we guide our development of batched factorizations to achieve up to two-fold speedup and three-fold better energy efficiency as compared against our highly optimized batched CPU implementations based on MKL library. Finally, the tested system featured two sockets of Intel Sandy Bridge CPUs and we compared with a batched LU factorizations featured in the CUBLAS library for GPUs, we achieve as high as 2.5× speedup on the NVIDIA K40 GPU.

97 MATHEMATICS AND 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↗

SU-F-J-98: Improvement and Evaluation Of Deformation Image Registration On Parotid Glands During Radiation Therapy for Nasopharyngeal Cancer

Purpose: To quantitatively evaluate the strategic innovation and accuracy variation of deformation registration algorithm for parotid glands using the similarity Dice coefficient during the course of radiation therapy (RT) for nasopharyngeal cancer (NPC). Methods: Daily MVCT data for 10 patients with pathologically proven nasopharyngeal cancers were analyzed. The data were acquired using tomotherapy (TomoTherapy, Accuray) at the PLA General Hospital. The prescription dose to the primary target was 70Gy in 33 fractions. Two kinds of contours for parotid glands on daily MVCTs were obtained by populating these contours from planning CTs to the daily CTs via rigid-body registration with or without the rotation shifts using the in-house tools and the Adaptive plan software (Adaptive Plan, TomoTherapy), and were edited manually if necessary. The diffeomorphic Demons algorithm developed in the in-house tool was used to propagate the parotid structures from the daily CTs to planning CTs. The differences of the mapped parotid contours in two methods were evaluated using Dice similarity index (DSI). Two-tailed t-test analysis was carried out to compare the DSI changes during the course of RT. Results: For 10 patient plans, the accuracy of deformation image registration (DIR) with the rotation shift was obviously better than those without the rotation shift. The Dice scores of the ipsi- and contra-lateral parotids for with and without the rotation shifts were found to be correlated with each other [0.904±0.031 vs 0.919±0.030 (p<0.001); 0.900±0.031 vs 0.910±0.032 (p<0.001)]. The Dice scores for the parotids have shown the reduction with the changes of parotid volumes during RT. The DSI values between the first and last fraction were 0.932±0.020 vs 0.899±0.030 in 10 patient plans. Conclusion: DIR was successfully improved using the strategic innovation for ART. And the decrease of DIR accuracy has also been found during the delivery of fractionated radiotherapy. This work was supported in part by the grant from Chinese Natural Science Foundation (Grant No. 11105225).

60 APPLIED LIFE SCIENCES↗

Self-adaptive sampling rate data acquisition in JET's correlation reflectometer

Data acquisition systems with self-adaptive sampling rate capabilities have been proposed as a solution to reduce the shear amount of data collected in every discharge of present fusion devices. This paper discusses the design of such a system for its use in the KG8B correlation reflectometer at JET. The system, which is based on the ITMS platform, continuously adapts the sample rate during the acquisition depending on the signal bandwidth. Data are acquired continuously at the expected maximum sample rate and transferred to a memory buffer in the host processor. Thereafter the rest of the process is based on software. Data are read from the memory buffer in blocks and for each block an intelligent decimation algorithm is applied. The decimation algorithm determines the signal bandwidth for each block in order to choose the optimum sample rate for that block, and from there the decimation factor to be used. Memory buffers are used to adapt the throughput of the three main software modules (data acquisition, processing, and storage) following a typical producer-consumer architecture. The system optimizes the amount of data collected while maintaining the same information. Design issues are discussed and results of performance evaluation are presented.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Search for New Phenomena Using W/Z + (b)-Jets Measurements Performed with the ATLAS Detector

The Project proposed to use data of the ATLAS experiment, obtained during the 2011 and 2012 data-taking campaigns, to pursue studies of the strong interaction (QCD) and to examine promising signatures for new physics. The Project also contains a service component dedicated to a detector development initiative. The objective of the strong interaction studies is to determine how various predictions from the main theory (QCD) compare to the data. Results of a set of measurements developed by the Tufts team indicate that the dominant factor of discrepancy between data and QCD predictions come from the mis-modeling of the low energy gluon radiation as described by algorithms called parton showers. The discrepancies introduced by parton showers on LHC predictions could even be larger than the effect due to completely new phenomena (dark matter, supersymmetry, etc.) and could thus block further discoveries at the LHC. Some of the results obtained in the course of this Project also specify how QCD predictions must be improved in order to open the possibility for the discovery of something completely new at the LHC during Run-II. This has been integrated in the Run-II ATLAS physics program. Another objective of Tufts studies of the strong interaction was to determine how the hypothesis about an intrinsic heavy-quark component of the proton (strange, charm or bottom quarks) could be tested at the LHC. This hypothesis has been proposed by theorists 30 years ago and is still controversial. The Tufts team demonstrated that intrinsic charms can be observed, or severely constrained, at the LHC, and determine how the measurement should be performed in order to maximize its sensitivity to such an intrinsic heavy-quark component of the proton. Tufts also embarked on performing the measurement that is in progress, but final results are not yet available. They should shade a light of understanding on the fundamental structure of the proton. Determining the nature of dark matter particles, composing about 25% of all the matter in the universe, is one of the most exciting research goals at the LHC. Within this Project, the Tufts team proposed a way to improve over the standard approach used to look for dark matter at the LHC in events involving jets and a large amount of unbalanced energy in the detector (jets+ETmiss). The Tufts team has developed a measurement to test these improvements on data available (ATLAS 2012 dataset), in order to be ready to apply them on the new Run-II data that will be available at the end of 2015. Preliminary results on the proposed measurement indicate that a very high precision can be obtained on results free of detector effects. That will allow for better constrains of dark matter theories and will spare the needs for huge computing resources in order to compare dark matter theories to data. Finally, the Tufts team played a leading role in the development and the organization of the 6Et trigger, the detector component needed to collect the data used in dark matter searches and in many other analyses. The team compared the performance of the various algorithms capable of reconstructing the value of the ETmiss on each LHC collision event, and developed a strategy to commission these algorithms online. Tufts also contributed in the development of the ETmiss trigger monitoring software. Finally, the PI of this Project acted as the co-coordinator of the group of researchers at CERN taking care of the development and the operation of this detector component. The ETmiss trigger is now taking data, opening the possibility for the discovery of otherwise undetectable particles at the LHC.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

PROTEUS: Machine Learning Driven Resilience for Extreme-scale Systems

The objective of this project is to design, develop, and evaluate scalable software to enhance resilience, data checkpointing, program restart, and analysis. The proposed tasks are to 1) develop scalable machine learning techniques to learn temporal change patterns in a scalable and in-situ manner, and to minimize data movement and maximize learning locally closest to data; 2) design a concise data representation and indexing mechanism to capture the distribution of changes in data that can guarantee point-wise user-defined tolerable errors while reducing the data storage requirements by an order of magnitude or more; 3) develop data reduction techniques as library modules; 4) exploit local SSD for minimizing data movement in storage hierarchy; 5) develop anomaly detection algorithms that can predict corruptions based on learning of emerging patterns; 6) develop software libraries to be incorporated within widely used data formats and APIs; and 7) evaluate the proposed software using DOE scientific applications. The outcomes of the proposed work are to satisfy many synergistic data reduction and resilience requirements for large-scale data intensive applications executed on extreme-scale computing systems. The developed mechanism for error-bound data approximation is directly applicable to existing scientific applications. Through machine learning from historical events and change distribution, this work will enable anomaly detection for DOE computer facility.

97 MATHEMATICS AND COMPUTING↗

PRISMS-Plasticity: An open-source crystal plasticity finite element software

An open-source parallel 3-D crystal plasticity finite element (CPFE) software package PRISMS-Plasticity is presented here as a part of PRISMS integrated framework. A highly efficient rate-independent crystal plasticity algorithm is implemented along with developing its algorithmic tangent modulus. Additionally, a twin activation mechanism is incorporated into the framework based on an integration point sensitive scheme. The integration of the software as a part of the PRISMS framework is demonstrated. To do so, the integration of the PRISMS-Plasticity software with experimental characterization techniques such as electron backscatter diffraction (EBSD) and synchrotron X-ray diffraction using available open source software packages of DREAM.3D and Neper is elaborated. The integration of the PRISMS-Plasticity software with the information repository of Materials Commons is also presented. The parallel performance of the software is characterized which demonstrates that it scales well for large problems running on hundreds of processors. Various examples of polycrystalline metals with face-centered cubic (FCC), body-centered cubic (BCC), and hexagonal close-packed (HCP) crystals structures are presented to show the capability of the software to efficiently solve crystal plasticity boundary value problems, in addition to integration with preprocessing and postprocessing tools. PRISMS-Plasticity is an important activity within the broader PRISMS Center and future enhancements to PRISMS-Plasticity are planned and will be described.

36 MATERIALS SCIENCE↗

MueLu Multigrid Preconditioning Package

MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.

Tuminaro, Raymond↗

MueLu Multigrid Preconditioning Package

MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.

Source record↗

SU-E-T-348: Verification MU Calculation for Conformal Radiotherapy with Multileaf Collimator Using Report AAPM TG 114

Purpose: The purpose of this work was to develop and validate an open source independent MU dose calculation software for 3D conformal radiotherapy with multileaf high and low resolution according to the report of AAPM TG 11 Methods: Treatment plans were done using Iplan v4.5 BrainLAB TPS. A 6MV photon beam produced by Primus and Novalis linear accelerators equipped with an Optifocus MLC and HDMLC, respectively. TPS dose calculation algorithms were pencil beam and Monte Carlo. 1082 treatments plans were selected for the study. The algorithm was written in free and open source CodeBlocks C++ platform. Treatment plans were imported by the software using RTP format. Equivalent size field is obtained from the positions of the leaves; the effective depth of calculation can be introduced by TPS's dosimetry report or automatically calculated starting from SSD. The inverse square law is calculated by the 3D coordinates of the isocenter and normalization point of the treatment plan. The dosimetric parameters TPR, Sc, Sp and WF are linearly interpolated. Results: 1082 plans of both machines were analyzed. The average uncertainty between the TPS and the independent calculation was −0.43% ± 2.42% [−7.90%, 7.50%]. Specifically for the Primus the variation obtained was −0.85% ± 2.53% and for the Novalis 0.00% ± 2.23%. Data show that 94.8% of the cases the uncertainty was less than or equal to 5%, while 98.9% is less than or equal to 6%. Conclusion: The developed software is appropriate for use in calculation of UM. This software can be obtained upon request.

07 ISOTOPE AND RADIATION SOURCES↗

Implementation of Dynamic Extensible Adaptive Locally Exchangeable Measures (IDEALEM) v 0.1

Handling large streaming data is essential for various applications such as network traffic analysis, social networks, energy cost trends, and environment modeling. However, it is in general intractable to store, compute, search, and retrieve large streaming data. This software addresses a fundamental issue, which is to reduce the size of large streaming data and still obtain accurate statistical analysis. As an example, when a high-speed network such as 100 Gbps network is monitored, the collected measurement data rapidly grows so that polynomial time algorithms (e.g., Gaussian processes) become intractable. One possible solution to reduce the storage of vast amounts of measured data is to store a random sample, such as one out of 1000 network packets. However, such static sampling methods (linear sampling) have drawbacks: (1) it is not scalable for high-rate streaming data, and (2) there is no guarantee of reflecting the underlying distribution. In this software, we implemented a dynamic sampling algorithm, based on the recent technology from the relational dynamic bayesian online locally exchangeable measures, that reduces the storage of data records in a large scale, and still provides accurate analysis of large streaming data. The software can be used for both online and offline data records.

Sim, Alex↗

PS-Samp (Phase-Space Sampling)

PS-Samp is a software that reduces a given dataset by pruning data. Data is downselected such that it uniformly spans the phase-space, thereby ensuring that the full dataset is correctly represented. The algorithm relies on estimating the probability map of the data and using it to construct an acceptance probability. The software is designed to handle very large data sets.

Hassanaly, Malik↗

Mesoflow: An Open-Source Reacting Flow Solver for Catalysis at Mesoscale

We present the capabilities and software performance metrics of our open-source continuum solver for catalysis, Mesoflow, developed specifically for modeling transport and chemistry at the mesoscale. Our solver utilizes Cartesian block-structured adaptive mesh refinement to resolve complex catalyst surface morphologies directly obtained from X-ray tomography data. An immersed boundary based formulation enables rapid representation of complex geometries prevalent in most mesoporous catalyst interfaces. The solver is developed on top of open-source performance portable library, AMReX, providing parallel execution capabilities on current and upcoming high-performance-computing (HPC) architectures. Our flexible software framework enables integration of complex chemical mechanisms at heterogenous interfaces and time-split algorithms for circumventing highly disparate reaction and flow time-scales. Our current studies indicate a ten-fold performance gain by using graphics-processing-units (GPUs) compared to a single processor for representative problem sizes (2 million cell mesh). We will also present a brief introduction on how to build and use this software for application problems pertaining to catalytic upgrading and gas transport within porous catalyst particles.

adaptive meshing↗

TU-F-17A-03: A 4D Lung Phantom for Coupled Registration/Segmentation Evaluation

Purpose: Coupling the processes of segmentation and registration (regmentation) is a recent development that allows improved efficiency and accuracy for both steps and may improve the clinical feasibility of online adaptive radiotherapy. Presented is a multimodality animal tissue model designed specifically to provide a ground truth to simultaneously evaluate segmentation and registration errors during respiratory motion. Methods: Tumor surrogates were constructed from vacuum sealed hydrated natural sea sponges with catheters used for the injection of PET radiotracer. These contained two compartments allowing for two concentrations of radiotracer mimicking both tumor and background signals. The lungs were inflated to different volumes using an air pump and flow valve and scanned using PET/CT and MRI. Anatomical landmarks were used to evaluate the registration accuracy using an automated bifurcation tracking pipeline for reproducibility. The bifurcation tracking accuracy was assessed using virtual deformations of 2.6 cm, 5.2 cm and 7.8 cm of a CT scan of a corresponding human thorax. Bifurcations were detected in the deformed dataset and compared to known deformation coordinates for 76 points. Results: The bifurcation tracking accuracy was found to have a mean error of −0.94, 0.79 and −0.57 voxels in the left-right, anterior-posterior and inferior-superior axes using a 1×1×5 mm3 resolution after the CT volume was deformed 7.8 cm. The tumor surrogates provided a segmentation ground truth after being registered to the phantom image. Conclusion: A swine lung model in conjunction with vacuum sealed sponges and a bifurcation tracking algorithm is presented that is MRI, PET and CT compatible and anatomically and kinetically realistic. Corresponding software for tracking anatomical landmarks within the phantom shows sub-voxel accuracy. Vacuum sealed sponges provide realistic tumor surrogate with a known boundary. A ground truth with minimal uncertainty is thus realized that can be used for comparing the performance of registration and segmentation algorithms.

60 APPLIED LIFE SCIENCES↗

Performance Assessment of a New Gamma Spectroscopy Toolkit: Peak Doctor and the Spectral Nondestructive Assay Platform (SNAP) - 17397

High resolution gamma spectroscopy (HRGS) is a widely used technique for non-destructive characterization of nuclear materials, and assay of radioactive waste. The ability to accurately evaluate raw spectral data is an important step in producing high-quality results. A spectral analysis application known as Peak Doctor has been developed under a Cooperative Research and Development Agreement (CRADA) between LANL and Pajarito Scientific Corporation (PSC). The software has undergone several years of testing and validation by the Radioactive Waste Characterization Team of the LANL Waste Management Services Group (WM-SVS). PeakDoctor is designed to work with the Spectral Nondestructive Assay Platform (SNAP{sup TM}) to provide a complete HRGS analysis engine. SNAP{sup TM} performs model specific corrections for attenuation and geometry. These applications are the major components of a new toolkit designed primarily for portable far-field non-destructive assay. Peak Doctor performs a very accurate peak fit analysis with the goal of improving upon the capabilities of existing commercially available routines. It is designed to be user-configurable and can be customized to any given type of detector and any given type of spectrum. Peak Doctor was developed to resolve many of the inherent complexities in gamma ray spectra including overlapping peaks, complex multiplet regions, large step peaks, backscatter regions and Compton edges. Unlike most spectral analysis platforms, Peak Doctor does not rely on the energy calibration and detector resolution parameters that are saved by the operator in the spectrum file. Instead, key parameters are pre-defined for individual detectors. The software fits a continuum using a series of splines between a series of junctions or 'knots'. Fitting techniques are used to join the splines together to create a near-continuous multi-element curve. Optimizing the location of the knots is one of Peak Doctor's most powerful features. The knots are initially configured using a pre-defined list and are removed or added automatically during the fitting process. Knots are also created when new features are identified such as Step Peaks and Compton Edges. The user can also manually specify knots in order to improve the continuum fit. The initial fit is improved on by removing any outlier regions (which are converted to peaks) and the continuum fitting process is repeated. At this stage, an experienced user can work interactively with the fit by manually converting peak regions to continuum or vice versa. The final step is to fit a series of peaks above the continuum based on detector parameters. Single and multiplet peaks are then processed by either the tailing (piecewise) or non-tailing (Gaussian) Levenberg Marquardt non-linear peak fitting routine depending on the user defined selection. Only a rough knowledge of the detector characteristics (energy calibration and resolution) is required for the fitting process to proceed with good accuracy. Any peaks that are missed can be manually added by the user and will also be fitted. Discontinuities in the peak / continuum fit can be rapidly identified by reviewing the 'residuals scale' plot. For waste streams that are well characterized, it is often the case that routinely encountered spectra will have similar peaks and continuum features. For these cases a handy 'One Step' method is available that proceeds in an automated fashion without user interaction. Peak Doctor has been configured with a set of default spectrum types including plutonium / transuranic waste (including Weapons Grade Pu, Heat Source Pu, Am-241, Am-243 and Np-237), depleted or enriched uranium, nuclear power plant / intermediate level waste (with fission and activation products such as Cs-137 and Co-60) as well as Naturally Occurring Radioactive Materials (NORM). The user can easily add new spectrum types for specific waste streams or other types of radiological / special nuclear materials. The output from PeakDoctor (including net peak area, centroid energy and a list of minimum detectable activity levels at pre-defined regions) is used by SNAP{sup TM} to complete the data analysis process. Isotope activities are calculated using configurable template-driven geometry and attenuation correction methods. The software accounts for matrix and container wall effects, collimator / angular corrections, detector efficiency (based on calibration curves) and stand-off distance. SNAP{sup TM} uses published algorithms incorporating a series of decision points during its operation to allow the analyst to provide logical input to guide the software during the analysis of each unique spectrum. The Peak Doctor / SNAP{sup TM} toolkit has been extensively tested and validated under a variety of conditions using 'benchmark' reference spectra. Test scenarios reported include HPGe-based measurements of well characterized uranium and plutonium standards and radioactive sources with a variety of different geometries and matrix materials including surrogate drums and boxes. (authors)

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

SIMULTANEOUS MULTI-BAND DETECTION OF LOW SURFACE BRIGHTNESS GALAXIES WITH MARKOVIAN MODELING

We present to the astronomical community an algorithm for the detection of low surface brightness (LSB) galaxies in images, called MARSIAA (MARkovian Software for Image Analysis in Astronomy), which is based on multi-scale Markovian modeling. MARSIAA can be applied simultaneously to different bands. It segments an image into a user-defined number of classes, according to their surface brightness and surroundings-typically, one or two classes contain the LSB structures. We have developed an algorithm, called DetectLSB, which allows the efficient identification of LSB galaxies from among the candidate sources selected by MARSIAA. The application of the method to two and three bands simultaneously was tested on simulated images. Based on our tests, we are confident that we can detect LSB galaxies down to a central surface brightness level of only 1.5 times the standard deviation from the mean pixel value in the image background. To assess the robustness of our method, the method was applied to a set of 18 B- and I-band images (covering 1.3 deg{sup 2} in total) of the Virgo Cluster to which Sabatini et al. previously applied a matched-filter dwarf LSB galaxy search algorithm. We have detected all 20 objects from the Sabatini et al. catalog which we could classify by eye as bona fide LSB galaxies. Our method has also detected four additional Virgo Cluster LSB galaxy candidates undetected by Sabatini et al. To further assess the completeness of the results of our method, both MARSIAA, SExtractor, and DetectLSB were applied to search for (1) mock Virgo LSB galaxies inserted into a set of deep Next Generation Virgo Survey (NGVS) gri-band subimages and (2) Virgo LSB galaxies identified by eye in a full set of NGVS square degree gri images. MARSIAA/DetectLSB recovered {approx}20% more mock LSB galaxies and {approx}40% more LSB galaxies identified by eye than SExtractor/DetectLSB. With a 90% fraction of false positives from an entirely unsupervised pipeline, a completeness of 90% is reached for sources with r{sub e} > 3'' at a mean surface brightness level of {mu}{sub g} = 27.7 mag arcsec{sup -2} and a central surface brightness of {mu}{sup 0}{sub g} = 26.7 mag arcsec{sup -2}. About 10% of the false positives are artifacts, the rest being background galaxies. We have found our proposed Markovian LSB galaxy detection method to be complementary to the application of matched filters and an optimized use of SExtractor, and to have the following advantages: it is scale free, can be applied simultaneously to several bands, and is well adapted for crowded regions on the sky.

79 ASTRONOMY AND ASTROPHYSICS↗

The interatomic vector's method, algorithms, and programs for the solution of atomic structure of nanoclusters in crystal

A calculation technique and corresponding algorithms have been developed using the formalism of Fourier transform of finite functions. A software package for obtaining distributions of cluster interatomic vectors from diffuse X-ray scattering has been written and debugged. The programs were checked on a 30-atom cluster [CdTb{sub 3}F{sub 26}]. The attempts to obtain experimental data on a single crystal with nanoclusters using an Xcalibur S diffractometer (Oxford Diffraction) with a coordinate CCD detector were no success. The standard diffractometer software contains errors that lead to incorrect results upon the reconstruction of the distribution of diffuse scattering from different runs. These errors are of little importance when Bragg peaks are processed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Data Locality Enhancement of Dynamic Simulations for Exascale Computing (Final Report)

The development of modern processors exhibits two trends that complicate the optimizations of modern software. The first is the increasing sensitivity of processors' throughput to irregularities in computation. With more processors produced through a massive integration of simple cores, future systems will increasingly favor regular data-level parallel computations, but deviate from the needs of applications with complex patterns. Some evidences are already shown on Graphic Processing Units (GPU): Irregular data accesses (e.g., indirect references A[D[i]]) and conditional branches are limiting many GPU applications' performance at a level an order of magnitude lower than the peak of GPU. The second hardware trend is the growing gap between memory bandwidth and the aggregate speed—that is, the sum of all cores' computing power—of a Chip Multiprocessor (CMP). Despite the capped growth of the peak CPU speed, the aggregate speed of a CMP keeps increasing as more cores get into a single chip. It is expected that by 2018, node concurrency in an exascale system will increase by hundreds of times, whereas, memory bandwidth will expand by only 10 to 20 times. Consequently, data movement and storage is expected to consume more than 70% of the total system power. Bridging this gap is difficult; the complexities of modern CMP memory hierarchy make it even harder: Data cache becomes shared among computing units, and the sharing is often non-uniform—whether two computing units share a cache depends on their proximity and the level of the cache. On the recent IBM Power7 architecture, for instance, four hardware contexts (or SMT threads) in a core share the entire memory hierarchy, all cores in one chip share an on-chip L3 cache, and cores across chips share L3 and main memory through off-chip connections. These two trends complicate the translation of computing power into performance, especially for a program with either intensive data accesses or complex patterns in data accesses or control flow paths. Unfortunately, both attributes present and will persist in a class of important applications. For instance, many scientific simulations deal with a large volume of data. And meanwhile, as most real-world processes are non-uniform and evolving (e.g., the evolution of a galaxy or the process of a drug injection), both the computations and data accesses of these programs tend to be irregular and dynamically changing. Currently, the lack of support to these applications on modern CMP severely limits their performance. On GPU, as our recent study shows and other studies echo, performance enhancement of a factor of integers is possible when memory accesses or control flows are streamlined for a set of GPU applications. On multicore CPU, our studies show that traditional locality enhancement, for being oblivious to the new features of multicore memory hierarchy, may even cause large slowdown to data-intensive dynamic applications. The severity of the issues is expected to worsen as the two hardware trends continue. Some recent studies try to match software with the trends, but in a limited scope or manner. For irregularities on GPU, most studies focus on irregularities analyzable through static analysis (e.g., data accesses in regular loops). Dynamic irregularities are harder to address because the needed analysis and transformations typically have to happen at run time. Some other research resorts to hardware extensions, an actual adoption of which is unclear for the entailed space cost and complexity. For data locality, recent years have seen some exploitations of the new memory hierarchy on multicore for performance, but most of them are on process or thread scheduling, rather than program transformations. Our recent study reveals that program-level transformations may magnify the scheduling benefits by a factor of seven, concluding that program-level transformation should play a central role for data locality enhancement on modern CMP. But research in this direction has been sparse, and most have focused on data layout or cache performance modeling, rather than program transformations to match with the new memory hierarchy features. Overall, it is still an open question how to bridge the gap between dynamic computations and the two prominent properties of modern processors. The goal of this project is to develop a set of techniques and software tools to enhance the matching between memory accesses in dynamic simulations and the prominent features of modern and future CMP, alleviating the memory performance issues for petascale and exascale computing. This report summarizes the discoveries and products produced throughout this project. It includes free launch, a new software approach to overcoming the shortcomings of both methods; coherence-free multiview, an approach that allows multiple views of a single data object to co-exist on GPU memory during a GPU kernel execution; algorithmic optimizations to data analytics problems, especially those that involve lots of distance calculations. Supporting dynamic parallelism is important for GPU to benefit a broad range of applications. There are currently two fundamental ways for programs to exploit dynamic parallelism on GPU: a software-based approach with software-managed worklists, and a hardware-based approach through dynamic subkernel launches. Neither is satisfactory. The former is complicated to program and is often subject to some load imbalance; the latter suffers large runtime overhead. In this work, we propose free launch, a new software approach to overcoming the shortcomings of both methods. It allows programmers to use subkernel launches to express dynamic parallelism. It employs a novel compiler-based code transformation named subkernel launch removal to replace the subkernel launches with the reuse of parent threads. Coupled with an adaptive task assignment mechanism, the transformation reassigns the tasks in the subkernels to the parent threads with a good load balance. The technique requires no hardware extensions, immediately deployable on existing GPUs. It keeps the programming convenience of the subkernel launch-based approach while avoiding its large runtime overhead. Meanwhile, its superior load balancing makes it outperform manual worklist-based techniques by 3X on average. The work was published at the 48th Annual IEEE/ACM International Symposium on Microarchitecture (Micro'2015). A Graphic Processing Unit (GPU) system is typically equipped with many types of memory (e.g., global, constant, texture, shared, cache). Data placement determines what data are placed on which type of memory, essential for GPU memory performance. Prior optimizations of data placement always require a single view of a data object on memory, which limits the optimization effectiveness. In this work, we propose coherence-free multiview, an approach that allows multiple views of a single data object to co-exist on GPU memory during a GPU kernel execution. We demonstrate that under certain conditions, the multiple views can remain incoherent while facilitating enhanced data placement. We present a theorem and some compiler support to ensure the soundness of the usage of coherence-free multiview. We further develop reference-discerning data placement, a new way to enhance data placements on GPU. It enables more flexible data placements by using coherence-free multiview to leverage the slack in coherence requirement of some GPU programs. Experiments on three types of GPU systems show that, with less than 200KB space cost, the new data placement technique can provide a 1.6X average (up to 4.27X) speedup. In addition, we have examined algorithmic optimizations to data analytics problems, especially those that involve lots of distance calculations. Computing distances among data points is an essential part of many important algorithms in data analytics, graph analysis, and other domains. In each of these domains, developers have spent significant manual effort optimizing algorithms, often through novel applications of the triangle equality, in order to minimize the number of distance computations in the algorithms. In this work, we observe that many algorithms across these domains can be generalized as an instance of a generic distance-related abstraction. Based on this abstraction, we derive seven principles for correctly applying the triangular inequality to optimize distance-related algorithms. Guided by the findings, we develop Triangular OPtimizer (TOP), the first software framework that is able to automatically produce optimized algorithms that either matches or outperforms manually designed algorithms for solving distance-related problems. TOP achieves up to 237x speedups and 2.5X on average. The work has been published at the 32nd International Conference on Machine Learning (ICML'15) and the 41st International Conference on Very Large Data Bases (VLDB'15).

42 ENGINEERING↗