SEARCH · Engineering Papers

Results for “cache locality”

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.

SourceResearch connectionFrom yearThrough year

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

124 records · Page 7

All sources NASA NTRS DOE OSTI

DOE OSTI2023

PERKS: a Locality-Optimized Execution Model for Iterative Memory-bound GPU Applications

Iterative memory-bound solvers commonly occur in HPC codes. Typical GPU implementations have a loop on the host side that invokes the GPU kernel as much as time/algorithm steps there are. The termination of each kernel implicitly acts the barrier required after advancing the solution every time step. We propose an execution model for running memory-bound iterative GPU kernels: PERsistent KernelS (PERKS). In this model, the time loop is moved inside persistent kernel, and device-wide barriers are used for synchronization. We then reduce the traffic to device memory by caching subset of the output in each time step in the unused registers and shared memory. PERKS can be generalized to any iterative solver: they largely independent of the solver's implementation. We explain the design principle of PERKS and demonstrate effectiveness of PERKS for a wide range of iterative 2D/3D stencil benchmarks (geomean speedup of 2.12x for 2D stencils and 1.24x for 3D stencils over state-of-art libraries), and a Krylov subspace conjugate gradient solver (geomean speedup of 4.86x in smaller SpMV datasets from SuiteSparse and 1.43x in larger SpMV datasets over a state-of-art library). All PERKS-based implementations available at: https://github.com/neozhang307/PERKS.

Zhang, Lingqi↗

DOE OSTI2024

MemFriend: Understanding Memory Performance with Spatial-Temporal Affinity

In HPC applications, memory access behavior is one of the main factors affecting performance. Improving an application’s memory access behavior involves optimizing data layout and/or restructuring code, and requires studying spatial-temporal data locality. Existing data locality analyses focus on single-location metrics and are restricted to evaluating temporal locality. We introduce spatial-temporal affinity metrics that quantify temporal access proximity, forward access correlation, and nearby access correlation between pairs of memory locations. We describe methods for distinguishing between potential vs. realized affinity and for reasoning about affinity at multiple resolutions (3D, 2D, 1D). Finally, we construct spatial-temporal affinity signatures that classify memory behavior and that be used to reason about changes in software (data relayout, code refactoring) or hardware (caching, prefetching). We describe methods for signature visualization, interpretation, and quantitative comparison of signatures. We evaluate our methodology using applications with variants that contrast data structures, data layouts and algorithms. We show that spatial-temporal affinity analysis provides novel insights and enables predictive reasoning about application performance when contrasted with reuse distance analysis.

Suriyakumar, Yasodhadevi↗

DOE OSTI2023

Environmental controls on observed spatial variability of soil pore water geochemistry in small headwater catchments underlain with permafrost

Abstract. Soil pore water (SPW) chemistry can vary substantially across multiple scales in Arctic permafrost landscapes. The magnitude of these variations and their relationship to scale are critical considerations for understanding current controls on geochemical cycling and for predicting future changes. These aspects are especially important for Arctic change modeling where accurate representation of sub-grid variability may be necessary to predict watershed-scale behaviors. Our research goal is to characterize intra- and inter-watershed soil water geochemical variations at two contrasting locations in the Seward Peninsula of Alaska, USA. We then attempt to identify the key factors controlling concentrations of important pore water solutes in these systems. The SPW geochemistry of 18 locations spanning two small Arctic catchments was examined for spatial variability and its dominant environmental controls. The primary environmental controls considered were vegetation, soil moisture and/or redox condition, water–soil interactions and hydrologic transport, and mineral solubility. The sampling locations varied in terms of vegetation type and canopy height, presence or absence of near-surface permafrost, soil moisture, and hillslope position. Vegetation was found to have a significant impact on SPW NO3- concentrations, associated with the localized presence of nitrogen-fixing alders and mineralization and nitrification of leaf litter from tall willow shrubs. The elevated NO3- concentrations were, however, frequently equipoised by increased microbial denitrification in regions with sufficient moisture to support it. Vegetation also had an observable impact on soil-moisture-sensitive constituents, but the effect was less significant. The redox conditions in both catchments were generally limited by Fe reduction, seemingly well-buffered by a cache of amorphous Fe hydroxides, with the most reducing conditions found at sampling locations with the highest soil moisture content. Non-redox-sensitive cations were affected by a wide variety of water–soil interactions that affect mineral solubility and transport. Identification of the dominant controls on current SPW hydrogeochemistry allows for qualitative prediction of future geochemical trends in small Arctic catchments that are likely to experience warming and permafrost thaw. As source areas for geochemical fluxes to the broader Arctic hydrologic system, geochemical processes occurring in these environments are particularly important to understand and predict with regards to such environmental changes.

Conroy, Nathan Alec (ORCID:0000000305973373)↗

NASA NTRS1998

Performance Modeling and Measurement of Parallelized Code for Distributed Shared Memory Multiprocessors

This paper presents a model to evaluate the performance and overhead of parallelizing sequential code using compiler directives for multiprocessing on distributed shared memory (DSM) systems. With increasing popularity of shared address space architectures, it is essential to understand their performance impact on programs that benefit from shared memory multiprocessing. We present a simple model to characterize the performance of programs that are parallelized using compiler directives for shared memory multiprocessing. We parallelized the sequential implementation of NAS benchmarks using native Fortran77 compiler directives for an Origin2000, which is a DSM system based on a cache-coherent Non Uniform Memory Access (ccNUMA) architecture. We report measurement based performance of these parallelized benchmarks from four perspectives: efficacy of parallelization process; scalability; parallelization overhead; and comparison with hand-parallelized and -optimized version of the same benchmarks. Our results indicate that sequential programs can conveniently be parallelized for DSM systems using compiler directives but realizing performance gains as predicted by the performance model depends primarily on minimizing architecture-specific data locality overhead.

Waheed, Abdul↗

DOE OSTI2020

Vertex Reordering for Real-world Graphs and Applications: An Empirical Evaluation

Vertex reordering is a way to improve locality in graph computations. Given an input (or ``natural'') order, reordering aims to compute an alternate permutation of the vertices that is aimed at maximizing a locality-based objective. Given decades of research on this topic, there are tens of graph reordering schemes, and there are also several linear arrangement ``gap'' measures for treatment as objectives. However, a comprehensive empirical analysis of the efficacy of the ordering schemes against the different gap measures, and against real-world applications is currently lacking. In this study, we present an extensive empirical evaluation of up to 11 ordering schemes, taken from different classes of approaches, on a set of 34 real-world graphs emerging from different application domains. Our study is presented in two parts: a) a thorough comparative evaluation of the different ordering schemes on their effectiveness to optimize different linear arrangement gap measures, relevant to preserving locality; and b) extensive evaluation of the impact of the ordering schemes on two real-world, parallel graph applications, namely, community detection and influence maximization. Our studies show a significant divergence among the ordering schemes (up to $40\times$ between the best and the poor) in their effectiveness to reduce the gap measures; and a wide ranging impact of the ordering schemes on various aspects including application runtime (up to $4\times$), memory and cache use, load balancing, and parallel work and efficiency. The comparative study also help reveal the nuances of a parallel environment (compared to serial) on the ordering schemes and their role in optimizing applications.

Barik, Reet↗

NASA NTRSDate not supplied

Mars 2020's First Sample: The Fractured Rough Rock Unit on the Floor of Jezero Crater

A central goal of the Mars 2020 mission is to select and cache samples for future return to Earth. The first samples targeted for collection are from the crater-retaining, Crater Floor Fractured Rough (CF-Fr) unit of Stack et al., 2020.The CF-Fr unit is a topographically low unit in the current Jezero setting, likely overlain by morphologically discrete units, including possible Jezero delta deposits and eolian features. CF-Fr is an aerially extensive unit with lobate margins. Two distinct morphologies are observed: a locally-exposed lower expression, with flat relatively horizontal light-toned surfaces and polygonal fracturing, and an upper expression consisting of up to ~5vertical meters of massive, sometimes boulder-producing, material. The locally-exposed lower expression appears to represent a local ground level in which the upper material has been removed. Near the Octavia E. Butler landing site, the lower morphology is exposed as polygonally-fractured, light-toned bedrock that appears to grade continuously into higher-standing massive outcrops, often with no clearly exposed contact. Further south, a darker upper expression of the CF-Fr unit is more distinct and the unit exhibits some horizontal layering. The Perseverance rover will initially sample the flat-lying expression of this unit. Hypotheses for the origin of CF-Fr include fluvial, aeolian, or lacustrine sediment likely derived from the Jezero watershed, and/or pyroclastic material resulting from regional volcanism. Geochronology of the returned sample could be used to help constrain the timing of geological events in Jezero. It may also help constrain stratigraphic relationships with crater-retaining units outside of Jezero within the Nili Planum, which could be used to calibrate the cratering chronology of Mars. Paleomagnetic analyses of an oriented sample could establish the history of the martian dynamo and whether it persisted into the Hesperian. Finally, if present, secondary phases within the primary deposit would help constrain diagenetic conditions and inform post-depositional aqueous and potentially habitable environmental conditions.

Justin I Simon↗

DOE OSTI2020

The SrrAB two-component system regulates Staphylococcus aureus pathogenicity through redox sensitive cysteines

Staphylococcus aureus infections can lead to diseases that range from localized skin abscess to life-threatening toxic shock syndrome. The SrrAB two-component system (TCS) is a global regulator of S. aureus virulence and critical for survival under environmental conditions such as hypoxic, oxidative, and nitrosative stress found at sites of infection. Despite the critical role of SrrAB in S. aureus pathogenicity, the mechanism by which the SrrAB TCS senses and responds to these environmental signals remains unknown. Bioinformatics analysis showed that the SrrB histidine kinase contains several domains, including an extracellular Cache domain and a cytoplasmic HAMP-PAS-DHp-CA region. In this work, we show that the PAS domain regulates both kinase and phosphatase enzyme activity of SrrB and present the structure of the DHp-CA catalytic core. Importantly, this structure shows a unique intramolecular cysteine disulfide bond in the ATP-binding domain that significantly affects autophosphorylation kinetics. In vitro data show that the redox state of the disulfide bond affects S. aureus biofilm formation and toxic shock syndrome toxin-1 production. Moreover, with the use of the rabbit infective endocarditis model, we demonstrate that the disulfide bond is a critical regulatory element of SrrB function during S. aureus infection. Our data support a model whereby the disulfide bond and PAS domain of SrrB sense and respond to the cellular redox environment to regulate S. aureus survival and pathogenesis.

59 BASIC BIOLOGICAL SCIENCES↗

DOE OSTI2022

Memory access optimization for particle operations in computational fluid dynamics-discrete element method simulations

Computational Fluid Dynamics - Discrete Element Method is used to model gas-solid systems in several applications in energy, pharmaceutical and petrochemical industries. Computational performance bottlenecks often limit the problem sizes that can be simulated at industrial scale. The data structures used to store several millions of particles in such large-scale simulations have a large memory footprint that does not fit into the processor cache hierarchies on current high-performance-computing platforms, leading to reduced computational performance. This paper specifically addresses this aspect of memory access bottlenecks in industrial scale simulations. The use of space-filling curves to improve memory access patterns is described and their impact on computational performance is quantified in both shared and distributed memory parallelization paradigms. The Morton space filling curve applied to uniform grids and k-dimensional tree partitions are used to reorder the particle data-structure thus improving spatial and temporal locality in memory. The performance impact of these techniques when applied to two benchmark problems, namely the homogeneous-cooling-system and a fluidized-bed, are presented. We report these optimization techniques lead to approximately two-fold performance improvement in particle focused operations such as neighbor-list creation and data-exchange, with ~ 1.5 times overall improvement in a fluidization simulation with 1.27 million particles.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Belle II Conditions Database

The Belle II experiment at KEK is preparing for taking first collision data in early 2018. For the success of the experiment it is essential to have information about varying conditions available to systems worldwide in a fast and efficient manner that is straightforward for both the user and maintainer. The Belle II Conditions Database was designed to make maintenance as easy as possible. To this end, a HTTP REST service was developed with industry-standard tools such as Swagger for the API interface development, Payara for the Java EE application server, and the Hazelcast in-memory data grid for support of scalable caching as well as transparent distribution of the service across multiple sites. On the client side, the online and offline software has to be able to obtain conditions data from the Belle II Conditions Database in a robust and reliable way under very different situations. As such the client side interface to the Belle II Conditions Database has been designed with a variety of access mechanisms which allow the software to be used with and without an internet connection. Different methods to access the payload information are implemented to allow for a high level of customization per site and to simplify testing of new payloads locally. Changes to the conditions data are usually handled transparently but users can actively check whether an object has changed or register callback functions to be called whenever a conditions data object is updated. In addition a command line user interface has been developed to simplify inspection and modification of the database contents.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NASA NTRS1993

Using Transparent Informed Prefetching (TIP) to reduce file read latency

As processor performance gains continue to outstrip Input/Output gains, I/O performance is becoming critical to overall system performance. File read latency is the most significant bottleneck for high performance I/O. Other aspects of I/O performance benefit from recent advances in disk bandwidth and throughput resulting from disk arrays, and in write performance derived from buffered write behind and the Log-structured File System. The access gap problem limiting improvements in read latency is exacerbated by distributed file systems operating over networks with diverse bandwidth. Focus is on extending the power of caching and prefetching to reduce file read latencies by exploiting hints from high-levels of a system. Such Transparent Informed Prefetching, TIP, and its benefits are described. It is argued that hints that disclose high level knowledge are a means for transferring optimization information across, without violating, module boundaries. How TIP can be used to convert the high throughput of new technologies such as disk arrays and log-structured file systems into low latency for applications is discussed. Our preliminary experiments show reductions in wall - clock execution time of 13 percent and 20 percent for a multiple module compilation tool (make) accessing data on a local disk and remote Coda file server, respectively, and a reduction of 30 percent for a text search (grep) remotely accessing many small files.

Patterson, R. H.↗

DOE OSTI2019

Rapidly Measuring Loop Footprints

Knowing a loop’s footprint — the unique data items it accesses — enables important locality and capacity analysis. Unfortunately, current methods for computing footprint cause integer factors of slowdown and are therefore difficult to use with realistic inputs. Current methods are slow because they are based on software tracing of load instructions and data addresses. We present an approach that combines lightweight measurements and static binary analysis. We use static analysis to reason about each load’s expected reuse. We then calculate the footprint for each loop using inference rules informed by measurements from common performance counters. We validate our method on benchmarks that vary access patterns (strided vs. unpredictable), reuse (varying and repeated accesses per element), and sparsity (all words in a cache line vs. some). For strided patterns, errors are within 1%; for unpredictable ones, errors are 5–10%. Our overheads are under 10%. A tool based on software tracing has an error of less than 1%, but either introduces at least 130× overhead or hangs.

Kilic, Ozgur O.↗

DOE OSTI2020

Bonding similarities and differences between Y–Sb–Te and Sc–Sb–Te phase-change memory materials

The scandium (Sc) – alloyed Sb 2 Te 3 phase-change alloy has recently been found to enable ultrafast crystal nucleation due to the formation of Sc-stabilized octahedral motifs in the amorphous phase, rendering cache-type phase-change memory feasible. When yttrium (Y) is added, however, non-octahedral bonding patterns form in the amorphous Sb 2 Te 3 -based network even though Y has a valence electron configuration similar to that of Sc and also forms perfect octahedral bonding environments with tellurium in the YTe crystal. Here we elucidate the origin of this difference between Sc and Y, by carrying out thorough ab initio simulations and orbital-based bonding analyses on amorphous Y–Sb–Te and Sc–Sb–Te compounds. We also demonstrate how the smooth overlap of atomic positions (SOAP) similarity kernel can be used to quantify the structural similarity of local motifs in the amorphous phase with respect to various crystalline yttrium and scandium tellurides, both in the nearest-neighbor shell and beyond. We discover that the bonding contrast of Y- and Sc-centered structural motifs in amorphous Sb 2 Te 3 stems from their parent crystals at high Te concentrations. The larger atomic radius of Y and the weaker charge transfer when bonded with Te is found to allow more Te neighbors and cause a more open bonding environment, leading to higher coordination numbers and non-octahedral environments. We discuss the implications of the different local environments for practical applications in memory devices.

36 MATERIALS SCIENCE↗

NASA NTRS1993

RAID 7 disk array

Each RAID level reflects a different design architecture. Associated with each is a backdrop of imposed limitations, as well as possibilities which may be exploited within the architectural constraints of that level. There are three unique features that differentiate RAID 7 from all other levels. RAID 7 is asynchronous with respect to usage of I/O data paths. Each I/O drive (includes all data and one parity drives) as well as each host interface (there may be multiple host interfaces) has independent control and data paths. This means that each can be accessed completely, independently, of the other. This is facilitated by a separate device cache for each device/interface as well. RAID 7 is asynchronous with respect to device hierarchy and data bus utilization. Each drive and each interface is connected to a high speed data bus controlled by the embedded operating system to make independent transfers to and from central cache. RAID 7 is asynchronous with respect to the operation of an embedded real time process oriented operating system. This means that exclusive and independent of the host, or multiple host paths, the embedded OS manages all I/O transfers asynchronously across the data and parity drives. A key factor to consider is that of the RAID 7's ability to anticipate and match host I/O usage patterns. This yields the following benefits over RAID's built around micro-code based architectures. RAID 7 appears to the host as a normally connected Big Fast Disk (BFD). RAID 7 appears, from the perspective of the individual disk devices, to minimize the total number of accesses and optimize read/write transfer requests. RAID 7 smoothly integrates the random demands of independent users with the principles of spatial and temporal locality. This optimizes small, large, and time sequenced I/O requests which results in users having an I/O performance which approaches performance to that of main memory.

Stout, Lloyd↗

NASA NTRS2017

Thermal Design, Analysis, and Sensitivity of a Sample Tube on the Martian Surface

NASA will launch a rover to Mars in 2020 to collect and cache samples of Martian rocks and regolith for potential return to Earth on a future mission. The collected samples will be placed in tubes, hermetically sealed, and deposited on the surface of Mars for a period of up to 10 years. Preventing the deposited samples from overheating is an important consideration in order to ensure their scientific integrity. The samples are required to remain below 60 °C, however there is a goal to keep them below 40 °C. This temperature requirement is challenging, considering that the maximum surface temperature of Mars is 38 °C and the tube must be thermally controlled through only passive means. As a result, a significant effort has been made to design a tube to contain the samples and investigate innovative tube surface treatments that maintain proper sample temperatures without significant adverse effects of sample contamination. The tube uses a specialized aluminum oxide coating to prevent overheating on the Martian surface. The maximum predicted tube temperature is relatively insensitive to local thermal inertia, ground contact, and ground slope, but is very sensitive to landing site latitude and dust deposition. The maximum predicted sample temperature in the +/- 30° landing latitude range with worst case assumptions is 54 °C, but many of the potential landing sites have significantly cooler maximum predicted sample temperatures. This paper describes the thermal design, analysis, and sensitivity studies performed on the sample tubes and also discusses operational considerations.

Novak, Keith↗

DOE OSTI2015

Improving Block-level Efficiency with scsi-mq

Current generation solid-state storage devices are exposing a new bottlenecks in the SCSI and block layers of the Linux kernel, where IO throughput is limited by lock contention, inefficient interrupt handling, and poor memory locality. To address these limitations, the Linux kernel block layer underwent a major rewrite with the blk-mq project to move from a single request queue to a multi-queue model. The Linux SCSI subsystem rework to make use of this new model, known as scsi-mq, has been merged into the Linux kernel and work is underway for dm-multipath support in the upcoming Linux 4.0 kernel. These pieces were necessary to make use of the multi-queue block layer in a Lustre parallel filesystem with high availability requirements. We undertook adding support of the 3.18 kernel to Lustre with scsi-mq and dm-multipath patches to evaluate the potential of these efficiency improvements. In this paper we evaluate the block-level performance of scsi-mq with backing storage hardware representative of a HPC-targerted Lustre filesystem. Our findings show that SCSI write request latency is reduced by as much as 13.6%. Additionally, when profiling the CPU usage of our prototype Lustre filesystem, we found that CPU idle time increased by a factor of 7 with Linux 3.18 and blk-mq as compared to a standard 2.6.32 Linux kernel. Our findings demonstrate increased efficiency of the multi-queue block layer even with disk-based caching storage arrays used in existing parallel filesystems.

Cluster Computing↗

DOE OSTI2016

An efficient and portable SIMD algorithm for charge/current deposition in Particle-In-Cell codes

In current computer architectures, data movement (from die to network) is by far the most energy consuming part of an algorithm (≈20pJ/word on-die to ≈10,000 pJ/word on the network). To increase memory locality at the hardware level and reduce energy consumption related to data movement, future exascale computers tend to use many-core processors on each compute nodes that will have a reduced clock speed to allow for efficient cooling. To compensate for frequency decrease, machine vendors are making use of long SIMD instruction registers that are able to process multiple data with one arithmetic operator in one clock cycle. SIMD register length is expected to double every four years. As a consequence, Particle-In-Cell (PIC) codes will have to achieve good vectorization to fully take advantage of these upcoming architectures. In this paper, we present a new algorithm that allows for efficient and portable SIMD vectorization of current/charge deposition routines that are, along with the field gathering routines, among the most time consuming parts of the PIC algorithm. Our new algorithm uses a particular data structure that takes into account memory alignment constraints and avoids gather/scat;ter instructions that can significantly affect vectorization performances on current CPUs. The new algorithm was successfully implemented in the 3D skeleton PIC code PICSAR and tested on Haswell Xeon processors (AVX2-256 bits wide data registers). Results show a factor of ×2 to ×2.5 speed-up in double precision for particle shape factor of orders 1–3. The new algorithm can be applied as is on future KNL (Knights Landing) architectures that will include AVX-512 instruction sets with 512 bits register lengths (8 doubles/16 singles). Program summary Program Title: vec_deposition Program Files doi:http://dx.doi.org/10.17632/nh77fv9k8c.1 Licensing provisions: BSD 3-Clause Programming language: Fortran 90 External routines/libraries: OpenMP > 4.0 Nature of problem: Exascale architectures will have many-core processors per node with long vector data registers capable of performing one single instruction on multiple data during one clock cycle. Data register lengths are expected to double every four years and this pushes for new portable solutions for efficiently vectorizing Particle-In-Cell codes on these future many-core architectures. One of the main hotspot routines of the PIC algorithm is the current/charge deposition for which there is no efficient and portable vector algorithm. Solution method: Here we provide an efficient and portable vector algorithm of current/charge deposition routines that uses a new data structure, which significantly reduces gather/scatter operations. Vectorization is controlled using OpenMP 4.0 compiler directives for vectorization which ensures portability across different architectures. Restrictions: Here we do not provide the full PIC algorithm with an executable but only vector routines for current/charge deposition. These scalar/vector routines can be used as library routines in your 3D Particle-In-Cell code. However, to get the best performances out of vector routines you have to satisfy the two following requirements: (1) Your code should implement particle tiling (as explained in the manuscript) to allow for maximized cache reuse and reduce memory accesses that can hinder vector performances. The routines can be used directly on each particle tile. (2) You should compile your code with a Fortran 90 compiler (e.g Intel, gnu or cray) and provide proper alignment flags and compiler alignment directives (more details in README file).

97 MATHEMATICS AND COMPUTING↗