Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “computational challenges”

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,243 records · Page 69

Ultrafast processing of pixel detector data with machine learning frameworks

Modern photon science performed at high repetition rate free-electron laser (FEL) facilities and beyond relies on 2D pixel detectors operating at increasing frequencies (towards 100 kHz at LCLS-II) and producing rapidly increasing amounts of data (towards TB/s). This data must be rapidly stored for offline analysis and summarized in real time for online feedback to the scientists. While at LCLS all raw data has been stored, at LCLS-II this would lead to a prohibitive cost; instead, enabling real time processing of pixel detector data (dark, gain, common mode, background, charge summing, subpixel position, photon counting, data summarization) allows reducing the size and cost of online processing, offline processing and storage by orders of magnitude while preserving full photon information. This could be achieved by taking advantage of the compressibility of sparse data typical for LCLS-II applications. Faced with a similar big data challenge a decade ago, computer vision stimulated revolutionary advances in machine learning hardware and software. We investigated if these developments are useful in the field of data processing for high speed pixel detectors and found that typical deep learning models and autoencoder architectures failed to yield useful noise reduction while preserving full photon information, presumably because of the very different statistics and feature sets in computer vision and radiation imaging. However, the raw performance of modern frameworks like Tensorflow inspired us to redesign in Tensorflow mathematically equivalent versions of the state-of-the-art, “classical” algorithms used at LCLS. The novel Tensorflow models resulted in elegant, compact and hardware agnostic code, gaining 1 to 2 orders of magnitude faster processing on an inexpensive consumer GPU, reducing by 3 orders of magnitude the projected cost of online analysis and compression without photon loss at LCLS-II. The novel Tensorflow models also enabled ongoing development of a pipelined hardware system expected to yield an additional 3 to 4 orders of magnitude speedup, necessary for meeting the data acquisition and storage requirements at LCLS-II, potentially enabling acquiring every single FEL pulse at full speed. Computer vision a decade ago was dominated by hand-crafted filters; their structure inspired the deep learning revolution resulting in modern deep convolutional networks; similarly, our novel Tensorflow filters provide inspiration for designing future deep learning models for ultrafast and efficient processing and classification of pixel detector images at FEL facilities.

47 OTHER INSTRUMENTATION↗

Charge transfer excitation energies from ground state density functional theory calculations

Calculating charge transfer (CT) excitation energies with high accuracy and low computational cost is a challenging task. Kohn-Sham density functional theory (KS-DFT), due to its efficiency and accuracy, has achieved great success in describing ground state problems. To extend to excited state problems, our group recently demonstrated an approach with good numerical results to calculate low-lying and Rydberg excitation energies of an N-electron system from a ground state KS or generalized KS calculations of an (N-1)-electron system via its orbital energies. In the present work, we explore further the same methodology to describe CT excitations. Numerical results from this work show that performance of conventional density functional approximations (DFAs) is not as good for CT excitations as for other excitations due to the delocalization error. Applying localized orbital scaling correction (LOSC) to conventional DFAs, a recently developed method in our group to effectively reduce the delocalization error, can improve the results. Overall, the performance of this methodology is better than time dependent DFT (TDDFT) with conventional DFAs. In addition, it shows that results from LOSC-DFAs in this method reach similar accuracy to other methods, such as ΔSCF, G 0 W 0 with Bethe-Salpeter equations, particle-particle random phase approximation, and even high-level wavefunction methods like CC2. Our analysis shows that the correct 1/R trend for CT excitation can be captured from LOSC-DFA calculations, stressing that the application of DFAs with the minimal delocalization error is essential within this methodology. This work provides an efficient way to calculate CT excitation energies from ground state DFT.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Investigation of plasmon relaxation mechanisms using nonadiabatic molecular dynamics

Hot carriers generated from the decay of plasmon excitation can be harvested to drive a wide range of physical or chemical processes. However, their generation efficiency is limited by the concomitant phonon-induced relaxation processes by which the energy in excited carriers is transformed into heat. However, simulations of dynamics of nanoscale clusters are challenging due to the computational complexity involved. Here, in this paper, we adopt our newly developed Trajectory Surface Hopping (TSH) nonadiabatic molecular dynamics algorithm to simulate plasmon relaxation in Au 20 clusters, taking the atomistic details into account. The electronic properties are treated within the Linear Response Time-Dependent Tight-binding Density Functional Theory (LR-TDDFTB) framework. The relaxation of plasmon due to coupling to phonon modes in Au 20 beyond the Born–Oppenheimer approximation is described by the TSH algorithm. The numerically efficient LR-TDDFTB method allows us to address a dense manifold of excited states to ensure the inclusion of plasmon excitation. Starting from the photoexcited plasmon states in Au 20 cluster, we find that the time constant for relaxation from plasmon excited states to the lowest excited states is about 2.7 ps, mainly resulting from a stepwise decay process caused by low-frequency phonons of the Au 20 cluster. Furthermore, our simulations show that the lifetime of the phonon-induced plasmon dephasing process is ~10.4 fs and that such a swift process can be attributed to the strong nonadiabatic effect in small clusters. Our simulations demonstrate a detailed description of the dynamic processes in nanoclusters, including plasmon excitation, hot carrier generation from plasmon excitation dephasing, and the subsequent phonon-induced relaxation process.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

De novo design of modular protein hydrogels with programmable intra- and extracellular viscoelasticity

Relating the macroscopic properties of protein-based materials to their underlying component microstructure is an outstanding challenge. Here, we exploit computational design to specify the size, flexibility, and valency of de novo protein building blocks, as well as the interaction dynamics between them, to investigate how molecular parameters govern the macroscopic viscoelasticity of the resultant protein hydrogels. We construct gel systems from pairs of symmetric protein homo-oligomers, each comprising 2, 5, 24, or 120 individual protein components, that are crosslinked either physically or covalently into idealized step-growth biopolymer networks. Through rheological assessment, we find that the covalent linkage of multifunctional precursors yields hydrogels whose viscoelasticity depends on the crosslink length between the constituent building blocks. In contrast, reversibly crosslinking the homo-oligomeric components with a computationally designed heterodimer results in viscoelastic biomaterials exhibiting fluid-like properties under rest and low shear, but solid-like behavior at higher frequencies. Exploiting the unique genetic encodability of these materials, we demonstrate the assembly of protein networks within living mammalian cells and show via fluorescence recovery after photobleaching (FRAP) that mechanical properties can be tuned intracellularly in a manner similar to formulations formed extracellularly. We anticipate that the ability to modularly construct and systematically program the viscoelastic properties of designer protein-based materials could have broad utility in biomedicine, with applications in tissue engineering, therapeutic delivery, and synthetic biology.

36 MATERIALS SCIENCE↗

The 2020 plasma catalysis roadmap

Abstract Plasma catalysis is gaining increasing interest for various gas conversion applications, such as CO 2 conversion into value-added chemicals and fuels, CH 4 activation into hydrogen, higher hydrocarbons or oxygenates, and NH 3 synthesis. Other applications are already more established, such as for air pollution control, e.g. volatile organic compound remediation, particulate matter and NO x removal. In addition, plasma is also very promising for catalyst synthesis and treatment. Plasma catalysis clearly has benefits over ‘conventional’ catalysis, as outlined in the Introduction. However, a better insight into the underlying physical and chemical processes is crucial. This can be obtained by experiments applying diagnostics, studying both the chemical processes at the catalyst surface and the physicochemical mechanisms of plasma-catalyst interactions, as well as by computer modeling. The key challenge is to design cost-effective, highly active and stable catalysts tailored to the plasma environment. Therefore, insight from thermal catalysis as well as electro- and photocatalysis is crucial. All these aspects are covered in this Roadmap paper, written by specialists in their field, presenting the state-of-the-art, the current and future challenges, as well as the advances in science and technology needed to meet these challenges.

Bogaerts, Annemie (ORCID:0000000198756460)↗

Demonstration of machine-learning-enhanced Bayesian quantum state estimation

Machine learning (ML) has found broad applicability in quantum information science in topics as diverse as experimental design, state classification, and even studies on quantum foundations. Here, we experimentally realize an approach for defining custom prior distributions that are automatically tuned using ML for Bayesian quantum state estimation methods that generally better conform to the physical properties of the underlying system than standard fixed prior distributions. Previously, researchers have looked to Bayesian quantum state tomography for advantages like uncertainty quantification, the return of reliable estimates under any measurement condition, and minimal mean-squared error. However, practical challenges related to long computation times and conceptual issues concerning how to incorporate prior knowledge most suitably can overshadow these benefits. Using both simulated and experimental measurement results, we demonstrate that ML-defined prior distributions reduce net convergence times and provide a natural way to incorporate both implicit and explicit information directly into the prior distribution. These results constitute a promising path toward practical implementations of Bayesian quantum state tomography.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum signal processing for simulating cold plasma waves

Numerical modeling of radio-frequency waves in plasma with sufficiently high spatial and temporal resolution remains challenging even with modern computers. However, such simulations can be sped up using quantum computers in the future. In this work, we propose how to do such modeling for cold plasma waves, in particular, for an X wave propagating in an inhomogeneous one-dimensional plasma. The wave system is represented in the form of a vector Schrödinger equation with a Hermitian Hamiltonian. Block encoding is used to represent the Hamiltonian through unitary operations that can be implemented on a quantum computer. To perform the modeling, we apply the so-called quantum signal processing algorithm and construct the corresponding circuit. Quantum simulations with this circuit are emulated on a classical computer, and the results show agreement with traditional classical calculations. We also discuss how our quantum circuit scales with the resolution.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Quantum Simulation of Open Quantum Systems Using a Unitary Decomposition of Operators

Electron transport in realistic physical and chemical systems often involves the nontrivial exchange of energy with a large environment, requiring the definition and treatment of open quantum systems. Because the time evolution of an open quantum system employs a nonunitary operator, the simulation of open quantum systems presents a challenge for universal quantum computers constructed from only unitary operators or gates. Here, we present a general algorithm for implementing the action of any nonunitary operator on an arbitrary state on a quantum device. We show that any quantum operator can be exactly decomposed as a linear combination of at most four unitary operators. We demonstrate this method on a two-level system in both zero and finite temperature amplitude damping channels. Furthermore, the results are in agreement with classical calculations, showing promise in simulating nonunitary operations on intermediate-term and future quantum devices.

74 ATOMIC AND MOLECULAR PHYSICS↗

Charge localization and ordering in A 2 Mn 8 O 16 hollandite group oxides: Impact of density functional theory approaches

The phases of A 2 Mn 8 O 16 hollandite group oxides emerge from the competition between ionic interactions, Jahn-Teller effects, charge ordering, and magnetic interactions. Their balanced treatment with feasible computational approaches can be challenging for commonly used approximations in density functional theory. Three examples (A = Ag, Li, and K) are studied with a sequence of different approximate exchange-correlation functionals. Starting from a generalized gradient approximation (GGA), an extension to include van der Waals interactions and a recently proposed meta-GGA are considered. Then local Coulomb interactions for the Mn 3d electrons are more explicitly considered with the DFT + U approach. Finally, selected results from a hybrid functional approach provide a reference. Results for the binding energy of the A species in the parent oxide highlight the role of van der Waals interactions. Relatively accurate results for insertion energies can be achieved with a low-U and a high-U approach. In the low-U case, the materials are described as band metals with a high-symmetry, tetragonal crystal structure. In the high-U case, the electrons donated by A result in formation of local Mn 3+ centers and corresponding Jahn-Teller distortions characterized by a local order parameter. The resulting degree of monoclinic distortion depends on charge ordering and magnetic interactions in the phase formed. The reference hybrid functional results show charge localization and ordering. Comparison to low-temperature experiments of related compounds suggests that charge localization is the physically correct result for the hollandite group oxides studied here. Lastly, while competing effects in the local magnetic coupling are subtle, the fully anisotropic implementation of DFT + U gives the best overall agreement with results from the hybrid functional.

meta-GGA↗

Benchmark Generation and Simulation at Extreme Scale

The path to extreme scale high-performance computing (HPC) poses several challenges related to power, performance, resilience, productivity, programmability, data movement, and data management. Investigating the performance of parallel applications at scale on future architectures and the performance impact of different architectural choices is an important component of HPC hardware/software co-design. Simulations using models of future HPC systems and communication traces from applications running on existing HPC systems can offer an insight into the performance of future architectures. This work targets technology developed for scalable application tracing of communication events. It focuses on extreme-scale simulation of HPC applications and their communication behavior via lightweight parallel discrete event simulation for performance estimation and evaluation. Instead of simply replaying a trace within a simulator, this work promotes the generation of a benchmark from traces. This benchmark is subsequently exposed to simulation using models to reflect the performance characteristics of future-generation HPC systems. This technique provides a number of benefits, such as eliminating the data intensive trace replay and enabling simulations at different scales. The presented work features novel software co-design aspects, combining the ScalaTrace tool to generate scalable trace files, the ScalaBenchGen tool to generate the benchmark, and the xSim tool to assess the benchmark characteristics within a simulator.

Lagadapati, Mahesh↗

Emergency Voltage Regulation in Power Systems via Ripple-Type Control

With increasing penetrations of volatile renewable generation and cyber-physical disruptions, ensuring the safe operation of bulk power systems has become unprecedentedly challenging. Because communication and computational costs restrict centralized system dispatch to being called upon every few minutes, and because purely local schemes are shown to be insufficient, distributed controls have been advocated for handling unanticipated system conditions in real time. The applicability of distributed control schemes, however, is fundamentally limited by their need for widespread communication and model cognizance. In this context, we put forth a hybrid, low-communication, saturation-driven protocol for the coordination of control agents that are distributed over a physical system and are allowed to communicate with peers over a "hotline" communication network. Under this protocol, when agents observe a constraint violation based on local measurements, they respond locally until their control resources saturate, in which case they send a beacon for assistance to peer agents. The scheme ensures that minor violations are efficiently mitigated via fast local controls, whereas severe violations can be handled by collaboration among a relatively small set of agents. We evaluate the performance of this scheme via numerical tests on the IEEE 14-bus test feeder, where agents act upon noisy measurements under diverse scenarios of load variations and severe low-/high-voltage events.

collaboration↗

IRIS-GNN: Leveraging Graph Neural Networks for Scheduling on Truly Heterogeneous Runtime Systems

The diversity of accelerators in computer systems poses significant challenges for software developers, such as managing vendor-specific compiler toolchains, code fragmentation requiring different kernel implementations, and performance portability issues. To address these, the Intelligent Runtime System (IRIS) was developed. IRIS works across various systems, from smartphones to supercomputers, enabling automatic performance scaling based on available accelerators. It introduces abstract tasks for seamless execution transitions between accelerators while ensuring memory consistency and task dependencies. Although IRIS simplifies system details, optimal dynamic scheduling still requires user input to understand workload structures. To address this, we introduce a new scheduling policy for IRIS, termed IRIS-GNN, which is the first IRIS hybrid policy that operates in conjunction with the dynamic policies. This policy employs a Graph-Neural Network (GNN) to conduct Graph Classification of any task graphs submitted to IRIS. This GNN analyzes the structure and attributes of the task graph, categorizing it as either locality, concurrency, or mixed. This classification subsequently guides the selection of the dynamic policy used by IRIS. We provide a comparison of the performance of IRIS-GNN against the complete spectrum of IRIS’s dynamic policies, assess the overhead introduced by the GNN within this scheduling framework, and ultimately explore its practical application in real-world scenarios.

Johnston, Beau↗

SU-D-18A-02: Towards Real-Time On-Board Volumetric Image Reconstruction for Intrafraction Target Verification in Radiation Therapy

Purpose: To expedite on-board volumetric image reconstruction from limited-angle kV—MV projections for intrafraction verification. Methods: A limited-angle intrafraction verification (LIVE) system has recently been developed for real-time volumetric verification of moving targets, using limited-angle kV—MV projections. Currently, it is challenged by the intensive computational load of the prior-knowledge-based reconstruction method. To accelerate LIVE, we restructure the software pipeline to make it adaptable to model and algorithm parameter changes, while enabling efficient utilization of rapidly advancing, modern computer architectures. In particular, an innovative two-level parallelization scheme has been designed: At the macroscopic level, data and operations are adaptively partitioned, taking into account algorithmic parameters and the processing capacity or constraints of underlying hardware. The control and data flows of the pipeline are scheduled in such a way as to maximize operation concurrency and minimize total processing time. At the microscopic level, the partitioned functions act as independent modules, operating on data partitions in parallel. Each module is pre-parallelized and optimized for multi-core processors (CPUs) and graphics processing units (GPUs). Results: We present results from a parallel prototype, where most of the controls and module parallelization are carried out via Matlab and its Parallel Computing Toolbox. The reconstruction is 5 times faster on a data-set of twice the size, compared to recently reported results, without compromising on algorithmic optimization control. Conclusion: The prototype implementation and its results have served to assess the efficacy of our system concept. While a production implementation will yield much higher processing rates by approaching full-capacity utilization of CPUs and GPUs, some mutual constraints between algorithmic flow and architecture specifics remain. Based on a careful analysis of the prototype performance, it will be feasible to resolve such issues through appropriate algorithmic modifications or special-purpose hardware, thus enabling target verification in seconds with the LIVE system. This work was partially supported by a research grant from Varian Medical Systems.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

SU-F-J-161: Prostate Contouring in Patients with Bilateral Hip Prostheses: Impact of Using Artifact-Reduced CT Images and MRI

Purpose: To investigate the usefulness of metal artifact reduction in CT images of patients with bilateral hip prostheses (BHP) for contouring the prostate and determine if the inclusion of MR images provides additional benefits. Methods: Five patients with BHP were CT scanned using our clinical protocol (140kV, 300mAs, 3mm slices, 1.5mm increment, Philips Medical Systems, OH). Images were reconstructed with the orthopaedic metal artifact reduction (O-MAR) algorithm. MRI scanning was then performed (1.5T, GE Healthcare, WI) with a flat table-top (T{sub 2}-weighted, inherent body coil, FRFSE, 3mm slices with 0mm gap). All images were transferred to Pinnacle (Version 9.2, Philips Medical Systems). For each patient, two data sets were produced: one containing the O-MAR-corrected CT images and another containing fused MRI and O-MAR-corrected CT images. Four genito-urinary radiation oncologists contoured the prostate of each patient on the O-MAR-corrected CT data. Two weeks later, they contoured the prostate on the fused data set, blinded to all other contours. During each contouring session, the oncologists reported their confidence in the contours (1=very confident, 3=not confident) and the contouring difficulty that they experienced (1=really easy, 4=very challenging). Prostate volumes were computed from the contours and the conformity index was used to evaluate inter-observer variability. Results: Larger prostate volumes were found on the O-MAR-corrected CT set than on the fused set (p< 0.05, median=36.9cm{sup 3} vs. 26.63 cm{sup 3}). No significant differences were noted in the inter-observer variability between the two data sets (p=0.3). Contouring difficulty decreased with the addition of MRI (p<0.05) while the radiation oncologists reported more confidence in their contours when MRI was fused with the O-MAR-corrected CT data (p<0.05). Conclusion: This preliminary work demonstrated that, while O-MAR correction to CT images improves visualization of anatomy, the addition of MRI enhanced the oncologists’ confidence in contouring the prostate in patients with BHP.

60 APPLIED LIFE SCIENCES↗

Streaming Data Reorganization at Scale with DeltaFS Indexed Massive Directories

We report complex storage stacks providing data compression, indexing, and analytics help leverage the massive amounts of data generated today to derive insights. It is challenging to perform this computation, however, while fully utilizing the underlying storage media. This is because, while storage servers with large core counts are widely available, single-core performance and memory bandwidth per core grow slower than the core count per die. Computational storage offers a promising solution to this problem by utilizing dedicated compute resources along the storage processing path. We present DeltaFS Indexed Massive Directories (IMDs), a new approach to computational storage. DeltaFS IMDs harvest available (i.e., not dedicated) compute, memory, and network resources on the compute nodes of an application to perform computation on data. We demonstrate the efficiency of DeltaFS IMDs by using them to dynamically reorganize the output of a real-world simulation application across 131,072 CPU cores. DeltaFS IMDs speed up reads by 1,740x while only slightly slowing down the writing of data during simulation I/O for in situ data processing.

97 MATHEMATICS AND COMPUTING↗

MRI-Based Radiotherapy Planning to Reduce Rectal Dose in Excess of Tolerance

Background and Purpose. Chronic rectal toxicity significantly decreases the quality of life for men who receive radiotherapy for prostate cancer. The most significant predictor of rectal toxicity is rectal dose-volume exceeding tolerance. To minimize the volume of rectum in the high dose field, it is essential to accurately define the prostate-rectum interface. This can be challenging to do by computed tomography (CT) imaging alone. The current study was undertaken to formally demonstrate in a clinical trial setting that image-guided intensity-modulated radiation therapy (IG-IMRT) planning using magnetic resonance imaging (MRI) can reduce the volume of rectum exceeding 70 Gy, a validated metric that predicts the risk of late rectal toxicity. Materials and Methods. This prospective single-arm study enrolled 15 men treated with IG-IMRT for localized prostate cancer. All participants received a dedicated 3 Tesla MRI examination of the prostate in addition to a pelvic CT examination for treatment planning. Two volumetric modulated arc therapy (VMAT) plans with a prescription dose of 79.2 Gy were designed using identical constraints based on CT- and MRI-defined consensus volumes. The volume of rectum exposed to 70 Gy or more was compared using the Wilcoxon paired signed rank test. Results. For CT-based treatment plans, the median volume of rectum receiving 70 Gy or more was 9.3 cubic centimeters (cc) (IQR 7.0 to 10.2) compared with 4.9 cc (IQR 4.1 to 7.8) for MRI-based plans. This resulted in a median volume reduction of 2.1 cc (IQR 0.5 to 5.3, P < .001). Conclusions. Using MRI to plan prostate IG-IMRT to a dose of 79.2 Gy reduces the volume of rectum receiving radiation dose in excess of tolerance (70 Gy or more) and should be considered in men who are at high risk for late rectal toxicity and are not good candidates for other rectal sparing techniques such as hydrogel spacer. This trial is registered with NCT02470910.

Schmidt, Daniel R.↗

OptRAM: In-silico strain design via integrative regulatory-metabolic network modeling

The ultimate goal of metabolic engineering is to produce desired compounds on an industrial scale in a cost effective manner. To address challenges in metabolic engineering, computational strain optimization algorithms based on genome-scale metabolic models have increasingly been used to aid in overproducing products of interest. However, most of these strain optimization algorithms utilize a metabolic network alone, with few approaches providing strategies that also include transcriptional regulation. Moreover previous integrated approaches generally require a pre-existing regulatory network. In this study, we developed a novel strain design algorithm, named OptRAM (Optimization of Regulatory And Metabolic Networks), which can identify combinatorial optimization strategies including overexpression, knockdown or knockout of both metabolic genes and transcription factors. OptRAM is based on our previous IDREAM integrated network framework, which makes it able to deduce a regulatory network from data. OptRAM uses simulated annealing with a novel objective function, which can ensure a favorable coupling between desired chemical and cell growth. The other advance we propose is a systematic evaluation metric of multiple solutions, by considering the essential genes, flux variation, and engineering manipulation cost. We applied OptRAM to generate strain designs for succinate, 2,3-butanediol, and ethanol overproduction in yeast, which predicted high minimum predicted target production rate compared with other methods and previous literature values. Moreover, most of the genes and TFs proposed to be altered by OptRAM in these scenarios have been validated by modification of the exact genes or the target genes regulated by the TFs, for overproduction of these desired compounds by in vivo experiments cataloged in the LASER database. Particularly, we successfully validated the predicted strain optimization strategy for ethanol production by fermentation experiment. As a result, OptRAM can provide a useful approach that leverages an integrated transcriptional regulatory network and metabolic network to guide metabolic engineering applications.

59 BASIC BIOLOGICAL SCIENCES↗

Traversing large graphs on GPUs with unified memory

Due to the limited capacity of GPU memory, the majority of prior work on graph applications on GPUs has been restricted to graphs of modest sizes that fit in memory. Recent hardware and software advances make it possible to address much larger host memory transparently as a part of a feature known as unified virtual memory. While accessing host memory over an interconnect is understandably slower, the problem space has not been sufficiently explored in the context of a challenging workload with low computational intensity and an irregular data access pattern such as graph traversal. We analyse the performance of breadth first search (BFS) for several large graphs in the context of unified memory and identify the key factors that contribute to slowdowns. Next, we propose a lightweight offline graph reordering algorithm, HALO (Harmonic Locality Ordering), that can be used as a pre-processing step for static graphs. HALO yields speedups of 1.5x-1.9x over baseline in subsequent traversals. Our method specifically aims to cover large directed real world graphs in addition to undirected graphs whereas prior methods only account for the latter. Additionally, we demonstrate ties between the locality ordering problem and graph compression and show that prior methods from graph compression such as recursive graph bisection can be suitably adapted to this problem.

Gera, Prasun↗