NDLI: Divide-and-conquer: a bubble replacement for low level caches

Please wait, while we are loading the content...

A european perspective on supercomputing

The roadrunner project and the importance of energy efficiency on the road to exascale computing

Computing outside the box

Implementation of a wide-angle lens distortion correction algorithm on the cell broadband engine

Zero-content augmented caches

OhHelp: a scalable domain-decomposing dynamic load balancing for particle-in-cell simulations

Fast memory snapshot for concurrent programmingwithout synchronization

Parametric multi-level tiling of imperfectly nested loops

Efficient high performance collective communication for the cell blade

Fast and scalable list ranking on the GPU

Creating artificial global history to improve branch prediction accuracy

A graph based approach for MPI deadlock detection

FTL design exploration in reconfigurable high-performance SSD for server applications

Single-particle 3d reconstruction from cryo-electron microscopy images on GPU

Combining thread level speculation helper threads and runahead execution

EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems

Adagio: making DVS practical for complex HPC applications

MPI collective communications on the blue gene/p supercomputer: algorithms and optimizations

High-performance regular expression scanning on the Cell/B.E. processor

Dynamic cache clustering for chip multiprocessors

Pattern-based sparse matrix representation for memory-efficient SMVM kernels

QuakeTM: parallelizing a complex sequential application using transactional memory

Dynamic parallelization of single-threaded binary programs using speculative slicing

Practice of parallelizing network applications on multi-core architectures

Tuned and wildly asynchronous stencil kernels for hybrid CPU/GPU systems

Exploring pattern-aware routing in generalized fat tree networks

Maximizing MPI point-to-point communication performance on RDMA-enabled clusters with customized protocols

/scratch as a cache: rethinking HPC center scratch storage

How GPUs can outperform ASICs for fast LDPC decoding

Limited early value communication to improve performance of transactional memory

Using many-core hardware to correlate radio astronomy signals

A comprehensive power-performance model for NoCs with multi-flit channel buffers

TransMetric: architecture independent workload characterization for transactional memory benchmarks

Computer generation of fast fourier transforms for the cell broadband engine

Less reused filter: improving l2 cache performance via filtering less reused lines

Dynamic topology aware load balancing algorithms for molecular dynamics applications

Refereeing conflicts in hardware transactional memory

Synchronization optimizations for efficient execution on multi-cores

Towards 100 gbit/s ethernet: multicore-based parallel communication protocol design

Performance modeling and automatic ghost zone optimization for iterative stencil loops on GPUs

Understanding the interconnection network of SpiNNaker

MPI-aware compiler optimizations for improving communication-computation overlap

P-Code: a new RAID-6 code with optimal properties

A translation system for enabling data mining applications on GPUs

A parallel levenberg-marquardt algorithm

Rate-based QoS techniques for cache/memory in CMP platforms

Cancellation of loads that return zero using zero-value caches

DBDB: optimizing DMATransfer for the cell be architecture

Divide-and-conquer: a bubble replacement for low level caches

Chunking parallel loops in the presence of synchronization

Virtualization polling engine (VPE): using dedicated CPU cores to accelerate I/O virtualization

Evaluating high performance communication: a power perspective

R-ADMAD: high reliability provision for large-scale de-duplication archival storage systems

Auto-vectorization through code generation for stream processing applications

Subdomain communication to increase scalability in large-scale scientific applications

Access map pattern matching for data cache prefetch

Prediction-based power estimation and scheduling for CMPs

Design of a novel SIMD architecture by fusing operations and registers

Thrifty interconnection network for HPC systems

Performance modeling for DFT algorithms in FFTW

PARSEC: hardware profiling of emerging workloads for CMP design

Approximate kernel matrix computation on GPUs forlarge scale learning applications

Dynamic task set partitioning based on balancing memory requirements to reduce power consumption

High-performance CUDA kernel execution on FPGAs

Load balancing using work-stealing for pipeline parallelism in emerging applications

Prefetch optimizations on large-scale applications via parameter value prediction

Designing multi-socket systems using silicon photonics

An infrastructure for scalable and portable parallel programs for computational chemistry

Divide-and-conquer: a bubble replacement for low level caches

Content Provider	ACM Digital Library
Author	Zhang, Chuanjun Xue, Bing
Abstract	The widely used LRU replacement policy suffers from the following problems. First, LRU does not exploit fre-quency information of cache accesses. Second, LRU may experience cache thrashing when access to cache exhibits cyclic patterns and the cache capacity is less than the working set. Finally, LRU is expensive to implement in hardware. We propose a bubble replacement for low-level caches, where cache blocks in one set are arranged in a queue for replacement determination. An incoming block enters the queue from the bottom and exchanges its posi-tion with the block above when the block hits, therefore, both recency and frequency information of a program are exploited. A victim block can be chosen from either the bottom or the top block of the queue, which is controlled by a single-bit set-hit flag per set. Choosing the bottom block as the victim makes the bubble replacement resistant to less frequently used blocks from polluting the cache while choosing the top block as the victim makes the bub-ble replacement adaptable to changes in the working set. We also propose to divide the blocks in a cache set into groups where each group implements the bubble replace-ment (we name it the DC-Bubble) to resolve the problems of the bubble replacement. The victim block is chosen ran-domly from the bottom block of each group. The proposed DC-Bubble reduces the average MPKI of the baseline 1MB 16-way L2 cache by 14%, bridges 47% of the gap between LRU and the OPT, reduces the storage require-ment by 61% and simplifies the circuit design compared to LRU.
Starting Page	80
Ending Page	89
Page Count	10
File Format	PDF
ISBN	9781605584980
DOI	10.1145/1542275.1542291
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Cache replacement policy High-performance computing Divide-and-conquer
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

TADC: Thread-aware Divide-and-Conquer policy to manage shared cache

Optimal bypass monitor for high performance last-level caches

A Cache Model for Modern Processors Modeling high-performance cache replacement on modern last-level caches (2015)

Pseudo-LIFO: the foundation of a new family of replacement policies for last-level caches

Provably good multicore cache performance for divide-and-conquer algorithms

A divide-and-conquer parallel pattern implementation for multicores

Controlling leakage power with the replacement policy in slumberous caches

Controlling leakage power with the replacement policy in slumberous caches (2005)

Block value based insertion policy for high performance last-level caches

Divide-and-conquer: a bubble replacement for low level caches

Similar Documents

TADC: Thread-aware Divide-and-Conquer policy to manage shared cache

Optimal bypass monitor for high performance last-level caches

A Cache Model for Modern Processors Modeling high-performance cache replacement on modern last-level caches (2015)

Pseudo-LIFO: the foundation of a new family of replacement policies for last-level caches

Provably good multicore cache performance for divide-and-conquer algorithms

A divide-and-conquer parallel pattern implementation for multicores

Controlling leakage power with the replacement policy in slumberous caches

Controlling leakage power with the replacement policy in slumberous caches (2005)

Block value based insertion policy for high performance last-level caches

Divide-and-conquer: a bubble replacement for low level caches