Rezaul Alam Chowdhury
ABSTRACT
We present efficient cache-oblivious algorithms for several fundamental dynamic programs. These include new algorithms with improved cache performance for longest common subsequence (LCS), edit distance, gap (i.e., edit distance with gaps), and least weight subsequence. We present a new cache-oblivious framework called the Gaussian Elimination Paradigm (GEP) for Gaussian elimination without pivoting that also gives cache-oblivious algorithms for Floyd-Warshall all-pairs shortest paths in graphs and 'simple DP', among other problems.
Index Terms
- Cache-oblivious dynamic programming
Recommendations
Decoupled dynamic cache segmentation
HPCA '12: Proceedings of the 2012 IEEE 18th International Symposium on High-Performance Computer ArchitectureThe least recently used (LRU) replacement policy performs poorly in the last-level cache (LLC) because temporal locality of memory accesses is filtered by first and second level caches. We propose a cache segmentation technique that dynamically adapts ...
Cache replacement with dynamic exclusion
Special Issue: Proceedings of the 19th annual international symposium on Computer architecture (ISCA '92)Most recent cache designs use direct-mapped caches to provide the fast access time required by modern high speed CPU's. Unfortunately, direct-mapped caches have higher miss rates than set-associative caches, largely because direct-mapped caches are more ...
Cache-oblivious ray reordering
We present a cache-oblivious ray reordering method for ray tracing. Many global illumination methods such as path tracing and photon mapping use ray tracing and generate lots of rays to simulate various realistic visual effects. However, these rays tend ...
Comments