Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “caches”

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 109 records · Page 6

Filtering micro-operations for a micro-operation cache in a processor

A processor includes a micro-operation cache having a plurality of micro-operation cache entries for storing micro-operations decoded from instruction groups and a micro-operation filter having a plurality of micro-operation filter table entries for storing identifiers of instruction groups for which the micro-operations are predicted dead on fill if stored in the micro-operation cache. The micro-operation filter receives an identifier for an instruction group. The micro-operation filter then prevents a copy of the micro-operations from the first instruction group from being stored in the micro-operation cache when a micro-operation filter table entry includes an identifier that matches the first identifier.

Scrbak, Marko↗

B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic Keys

Most B-tree articles assume that all $\textit{N}$ keys have the same size $\textit{K}$, that $\textit{f = B/K}$ keys fit in a disk block, and therefore that the search cost is $O(\text{log}_{f+1}N) $ block transfers. When keys have variable size, B-tree operations have no nontrivial performance guarantees, however. This article provides B-tree-like performance guarantees on dictionaries that contain keys of different sizes in a model in which keys must be stored and compared as opaque objects. The resulting atomic-key dictionaries exhibit performance bounds in terms of the average key size and match the bounds when all keys are the same size. Atomic-key dictionaries can be built with minimal modification to the B-tree structure, simply by choosing the pivot keys properly. Further, this article describes both static and dynamic atomic-key dictionaries. In the static case, if there are $\textit{N}$ keys with average size $\textit{K}$, the search cost is $O(\lceil K/B\rceil \text{log}_{1 + \lceil K/B\rceil} N)$ expected transfers. It is not possible to transform these expected bounds into worst-case bounds. The cost to build the tree is $\textit{O(NK)}$ operations and $\textit{O(NK/B)}$ transfers if all keys are presented in sorted order. If not, the cost is the sorting cost. For the dynamic dictionaries, the amortized cost to insert a key $\textit{κ}$ of arbitrary length at an arbitrary rank is dominated by the cost to search for $\textit{κ}$. Specifically, the amortized cost to insert a key $\textit{κ}$ of arbitrary length and random rank is $O(\lceil K/B\rceil log_{1+ \lceil B/K\rceil } N + |κ|/B)$ transfers. A dynamic-programming algorithm is shown for constructing a search tree with minimal expected cost. This article also gives a cache-oblivious static atomic-key B-tree, which achieves the same asymptotic performance as the static B-tree dictionary, mentioned previously. A cache-oblivious data structure or algorithm is not parameterized by the block size $\textit{B}$ or memory size $\textit{M}$ in the memory hierarchy; rather, it is universal, working simultaneously for all possible values of $\textit{B}$ or $\textit{M}$. On a machine with block size $\textit{B}$, if there are $\textit{N}$ keys with average size $\textit{K}$, search operations costs $O(\lceil K/B \rceil log_{1+ \lceil B/K \rceil} N)$ block transfers in expectation. This cache-oblivious layout can be built in $\textit{O(N}\text{log}\textit{(NK))}$ processor operations.

97 MATHEMATICS AND COMPUTING↗

Architectural Techniques For Managing Non-volatile Caches

As chip power dissipation becomes a critical challenge in scaling processor performance, computer architects are forced to fundamentally rethink the design of modern processors and hence, the chip-design industry is now at a major inflection point in its hardware roadmap. The high leakage power and low density of SRAM poses serious obstacles in its use for designing large on-chip caches and for this reason, researchers are exploring non-volatile memory (NVM) devices, such as spin torque transfer RAM, phase change RAM and resistive RAM. However, since NVMs are not strictly superior to SRAM, effective architectural techniques are required for making them a universal memory solution. This book discusses techniques for designing processor caches using NVM devices. It presents algorithms and architectures for improving their energy efficiency, performance and lifetime. It also provides both qualitative and quantitative evaluation to help the reader gain insights and motivate them to explore further. This book will be highly useful for beginners as well as veterans in computer architecture, chip designers, product managers and technical marketing professionals.

Cache architecture↗

Fault-Tolerant Deep Learning Cache with Hash Ring for Load Balancing in HPC Systems

Large-scale DL on HPC systems like Frontier and Summit uses distributed node-local caching to address scalability and performance challenges. However, as these systems grow more complex, the risk of node failures increases, and current caching approaches lack fault tolerance, jeopardizing large-scale training jobs. We analyzed six months of SLURM job logs from Frontier and found that over 30% of jobs failed after an average of 75 minutes. To address this, we propose fault-tolerance strategies that recache data lost from failed nodes using a hash ring technique for balanced data recaching in the distributed node-local caching, reducing reliance on the PFS. Our extensive evaluations on Frontier showed that the hash ring-based recaching approach reduced training time by approximately 25% compared to the approach that redirects I/O to the PFS after node failures and demonstrated effective load balancing of training data across nodes.

Lee, Seoyeong↗

Cache domains that are homologous to, but different from PAS domains comprise the largest superfamily of extracellular sensors in prokaryotes

Cellular receptors usually contain a designated sensory domain that recognizes the signal. Per/Arnt/Sim (PAS) domains are ubiquitous sensors in thousands of species ranging from bacteria to humans. Although PAS domains were described as intracellular sensors, recent structural studies revealed PAS-like domains in extracytoplasmic regions in several transmembrane receptors. However, these structurally defined extracellular PAS-like domains do not match sequence-derived PAS domain models, and thus their distribution across the genomic landscape remains largely unknown. Here we show that structurally defined extracellular PAS-like domains belong to the Cache superfamily, which is homologous to, but distinct from the PAS superfamily. Our newly built computational models enabled identification of Cache domains in tens of thousands of signal transduction proteins including those from important pathogens and model organisms.Moreover, we show that Cache domains comprise the dominant mode of extracellular sensing in prokaryotes.

59 BASIC BIOLOGICAL SCIENCES↗

Authenticating cache

The aim of the Authenticating Cache architecture is to ensure that machine instructions in a Read Only Memory (ROM) are legitimate from the time the ROM image is signed (immediately after compilation) to the time they are placed in the cache for the processor to consume. The proposed architecture allows the detection of ROM image modifications during distribution or when it is loaded into memory. It also ensures that modified instructions will not execute in the processor-as the cache will not be loaded with a page that fails an integrity check. The authenticity of the instruction stream can also be verified in this architecture. The combination of integrity and authenticity assurance greatly improves the security profile of a system.

97 MATHEMATICS AND COMPUTING↗

Accurate low-cost methods for performance evaluation of cache memory systems

Methods of simulation based on statistical techniques are proposed to decrease the need for large trace measurements and for predicting true program behavior. Sampling techniques are applied while the address trace is collected from a workload. This drastically reduces the space and time needed to collect the trace. Simulation techniques are developed to use the sampled data not only to predict the mean miss rate of the cache, but also to provide an empirical estimate of its actual distribution. Finally, a concept of primed cache is introduced to simulate large caches by the sampling-based method.

Laha, Subhasis↗

Error recovery in shared memory multiprocessors using private caches

The problem of recovering from processor transient faults in shared memory multiprocesses systems is examined. A user-transparent checkpointing and recovery scheme using private caches is presented. Processes can recover from errors due to faulty processors by restarting from the checkpointed computation state. Implementation techniques using checkpoint identifiers and recovery stacks are examined as a means of reducing performance degradation in processor utilization during normal execution. This cache-based checkpointing technique prevents rollback propagation, provides rapid recovery, and can be integrated into standard cache coherence protocols. An analytical model is used to estimate the relative performance of the scheme during normal execution. Extensions to take error latency into account are presented.

Wu, Kun-Lung↗

Performance of defect-tolerant set-associative cache memories

The increased use of on-chip cache memories has led researchers to investigate their performance in the presence of manufacturing defects. Several techniques for yield improvement are discussed and results are presented which indicate that set-associativity may be used to provide defect tolerance as well as improve the cache performance. Tradeoffs between several cache organizations and replacement strategies are investigated and it is shown that token-based replacement may be a suitable alternative to the widely-used LRU strategy.

Frenzel, J. F.↗

A novel cache mechanism

This cache mechanism is transparent but does not contain associative circuits. It does not rely on locality of reference of instructions or data. No redundant instructions or data are encached. Items in the cache are accessed without address arithmetic. A cache miss is detected by the simplest test; compare two bits. These features would result in faster access, higher hit rate, reduced chip area, and less power dissipation in comparison with associative systems of similar size.

Gunawardena, J. A.↗

Efficacy of Code Optimization on Cache-Based Processors

In this paper a number of techniques for improving the cache performance of a representative piece of numerical software is presented. Target machines are popular processors from several vendors: MIPS R5000 (SGI Indy), MIPS R8000 (SGI PowerChallenge), MIPS R10000 (SGI Origin), DEC Alpha EV4 + EV5 (Cray T3D & T3E), IBM RS6000 (SP Wide-node), Intel PentiumPro (Ames' Whitney), Sun UltraSparc (NERSC's NOW). The optimizations all attempt to increase the locality of memory accesses. But they meet with rather varied and often counterintuitive success on the different computing platforms. We conclude that it may be genuinely impossible to obtain portable performance on the current generation of cache-based machines. At the least, it appears that the performance of modern commodity processors cannot be described with parameters defining the cache alone.

VanderWijngaart, Rob F.↗

On the Efficacy of Source Code Optimizations for Cache-Based Systems

Obtaining high performance without machine-specific tuning is an important goal of scientific application programmers. Since most scientific processing is done on commodity microprocessors with hierarchical memory systems, this goal of "portable performance" can be achieved if a common set of optimization principles is effective for all such systems. It is widely believed, or at least hoped, that portable performance can be realized. The rule of thumb for optimization on hierarchical memory systems is to maximize temporal and spatial locality of memory references by reusing data and minimizing memory access stride. We investigate the effects of a number of optimizations on the performance of three related kernels taken from a computational fluid dynamics application. Timing the kernels on a range of processors, we observe an inconsistent and often counterintuitive impact of the optimizations on performance. In particular, code variations that have a positive impact on one architecture can have a negative impact on another, and variations expected to be unimportant can produce large effects. Moreover, we find that cache miss rates - as reported by a cache simulation tool, and confirmed by hardware counters - only partially explain the results. By contrast, the compiler-generated assembly code provides more insight by revealing the importance of processor-specific instructions and of compiler maturity, both of which strongly, and sometimes unexpectedly, influence performance. We conclude that it is difficult to obtain performance portability on modern cache-based computers, and comment on the implications of this result.

VanderWijngaart, Rob F.↗

On the Efficacy of Source Code Optimizations for Cache-Based Systems

Obtaining high performance without machine-specific tuning is an important goal of scientific application programmers. Since most scientific processing is done on commodity microprocessors with hierarchical memory systems, this goal of "portable performance" can be achieved if a common set of optimization principles is effective for all such systems. It is widely believed, or at least hoped, that portable performance can be realized. The rule of thumb for optimization on hierarchical memory systems is to maximize temporal and spatial locality of memory references by reusing data and minimizing memory access stride. We investigate the effects of a number of optimizations on the performance of three related kernels taken from a computational fluid dynamics application. Timing the kernels on a range of processors, we observe an inconsistent and often counterintuitive impact of the optimizations on performance. In particular, code variations that have a positive impact on one architecture can have a negative impact on another, and variations expected to be unimportant can produce large effects. Moreover, we find that cache miss rates-as reported by a cache simulation tool, and confirmed by hardware counters-only partially explain the results. By contrast, the compiler-generated assembly code provides more insight by revealing the importance of processor-specific instructions and of compiler maturity, both of which strongly, and sometimes unexpectedly, influence performance. We conclude that it is difficult to obtain performance portability on modern cache-based computers, and comment on the implications of this result.

VanderWijngaart, Rob F.↗

Mars 2020 sample caching system contamination: how to clean hardware and keep it clean

The Mars 2020 Rover will have the capability to collect and cache samples for potential Mars sample return. Specifically, the sample caching system (SCS) is designed for coring Mars samples and acquiring regolith samples as well as handling, sealing and caching on Mars. As the potential first Martian samples that could be returned to Earth, assuring low levels of terrestrial contamination is of the utmost concern. In developing the SCS, the project prioritizes limiting sample contamination in organic, inorganic and biological areas. The focus of this paper is on the strategies being implemented to clean the assemble the sampling hardware to meet and maintain stringent contamination requirements.

Rainen, Richard↗

Verifying Mars 2020 Sampling and Caching Robotic Functions with Position Budgeting Process and Tool

The Mars 2020 Perseverance Rover was launched on July 30th, 2020 with one of the most complex robotic systems ever implemented on an interplanetary mission. Much of this robotic complexity resides in the Rover Sampling and Caching Subsystem (SCS) to enable collection of Martian samples for eventual return to earth and preparation of surfaces for close-up surface science observations. Two robotic arms are used by SCS: the large Robotic Arm (RA) positions the coring drill and science instruments mounted to the Turret for surface interactions, and the smaller Sample Handling Assembly (SHA) manipulates Sample Tube Assemblies (STA) within the Adaptive Caching Assembly (ACA) to prepare them for sample collection, processing, and hermetic sealing. The robotic arms interact with the Martian surface and other SCS components in many ways and in a variety of configurations, with positioning accuracy requirements ranging from tens of millimeters for some surface interactions down to sub-millimeter accuracy for some ACA interactions.This paper describes the process and tool used to calculate the SCS robotic interaction positioning budgets and verify the as-built hardware when delivered. To ensure that these robotic systems are able to perform their tasks, each robotic interaction with another element was broken down into its composite functions. To calculate a positioning budget margin for each function, an allowable was defined and then compared to the list of error sources that contribute to misalignment. Across the subsystem, over 250 functions were identified to be assessed, with almost 500 error sources feeding into their budget calculations. In addition to using as-built values in the budgets for SCS Verification and Validation (V&V) after the hardware was complete, these budgets were populated with design data during the design phase to identify areas of concern and guide hardware design to ensure positive position budget margins.Because of the size of the SCS team that had inputs to the positioning budgets and the sheer number of items in the budgets that needed to be created, updated, and verified, having a tool that would allow for simultaneous access and robust data integrity and processing was imperative. To accomplish this, a web-based MySQL database was created that allowed users to create function position budgets, link individual errors and allowables to them, and view function position budget margin reports. Each error and allowable records data for lateral, normal, angular, and clocking errors, with the ability to add as-built data for up to four different hardware builds. Margin reports can be generated for either design values alone or replacing design data with as-built data when available. These as-built reports are used for final verification of the SCS positioning requirements. Ultimately, the SCS positioning budget process and database tool led to successful interactions during test and an SCS robotic system that is ready to perform sample acquisition and caching on the surface of Mars.

Williams, Jeffrey↗

Simplifying and speeding the management of intra-node cache coherence

A method and apparatus for managing coherence between two processors of a two processor node of a multi-processor computer system. Generally the present invention relates to a software algorithm that simplifies and significantly speeds the management of cache coherence in a message passing parallel computer, and to hardware apparatus that assists this cache coherence algorithm. The software algorithm uses the opening and closing of put/get windows to coordinate the activated required to achieve cache coherence. The hardware apparatus may be an extension to the hardware address decode, that creates, in the physical memory address space of the node, an area of virtual memory that (a) does not actually exist, and (b) is therefore able to respond instantly to read and write requests from the processing elements.

97 MATHEMATICS AND COMPUTING↗

Cache directory look-up re-use as conflict check mechanism for speculative memory requests

In a cache memory, energy and other efficiencies can be realized by saving a result of a cache directory lookup for sequential accesses to a same memory address. Where the cache is a point of coherence for speculative execution in a multiprocessor system, with directory lookups serving as the point of conflict detection, such saving becomes particularly advantageous.

97 MATHEMATICS AND COMPUTING↗

Method and apparatus for using compression to improve performance of low voltage caches

A method of operating a cache in a computing device includes, in response to receiving a memory access request at the cache, determining compressibility of data specified by the request, selecting in the cache a destination portion for storing the data based on the compressibility of the data and a persistent fault history of the destination portion, and storing a compressed copy of the data in a non-faulted subportion of the destination portion, wherein the persistent fault history indicates that the non-faulted subportion excludes any persistent faults.

Kalamatianos, John↗