EBRAHIMI SOORCHAEI, ROOZBEH · Academic Commons (Stony Brook University) · 2015
Memory efficiency and locality have substantial impact on the performance of programs, particularly when operating on large data sets. Thus, memory- or I/O-efficient algorithms have received significant attention both in theory and practice. The widespread deployment of multicore machines, however, brings new challenges. Specifically, since the memory is shared across multiple processes, the effective memory-size allocated to each process fluctuates over time. This dissertation studies algorithms in the context of a memory allocation that changes over time, which we call the cache-adaptive setting. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. Analytic techniques are provided for studying the behavior of recursive cache-oblivious algorithms in the cache-adaptive model. These techniques make analyzing algorithms in the cache-adaptive model almost as easy as in the Disk Access Model (DAM). These techniques are applied to analyze a wide variety of algorithms --- Master-Method-style algorithms, Akra-Bazzi-style algorithms, collections of mutually recursive algorithms, and algorithms, such as the cache-oblivious FFT algorithm, that break problems of size $N$ into subproblems of size $\Theta(N^c)$. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have the former recursive structures, it is nonetheless proved to be optimally cache-adaptive. Paging algorithms are studied in the context of cache-adaptive model. It is proved that the Least Recently Used (LRU) policy with resource augmentation is competitive with the optimal offline strategy. Moreover, Belady's Longest Forward Distance (LFD) policy is shown to remain optimal even when the memory size changes. Because cache-oblivious algorithms are well understood, frequently easy to design, and widely deployed, there is hope that provably good cache-adaptive algorithms can be deployed in practice. | 106 pages
Cited by 0
Max Planck Digital Library · 2005
Cited by 0
Harald Prokop · DSpace@MIT (Massachusetts Institute of Technology) · 1999
This thesis presents "cache-oblivious" algorithms that use asymptotically optimal amounts of work, and move data asymptotically optimally among multiple levels of cache. An algorithm is cache oblivious if no program variables dependent on hardware configuration parameters, such as cache size and cache-line length need to be tuned to minimize the number of cache misses. We show that the ordinary algorithms for matrix transposition, matrix multiplication, sorting, and Jacobi-style multipass filtering are not cache optimal. We present algorithms for rectangular matrix transposition, FFT, sorting, and multipass filters, which are asymptotically optimal on computers with multiple levels of caches. For a cache with size Z and cache-line length L, where Z =# (L 2 ), the number of cache misses for an m × n matrix transpose is #(1 + mn=L). The number of cache misses for either an n-point FFT or the sorting of n numbers is #(1 + (n=L)(1 + log Z n)). The cache complexity of computing n ...
Cited by 20Open access
Vaner, Michal · Digital Repository (National Repository of Grey Literature) · 2012
In this work, we study the cache-oblivious computation model, which is inspired by the behaviour of the memory hierarchy of current computers. We study several graph algorithms and techniques of their design in this model. We consider graph searching, identifying connected components and computing maximal matching. We also study sorting and matrix multiplication as subproblems of many graph algorithms. In ad- dition to previously known algorithms, we present several new ones. We study their efficiency both by the means of asymptotic complexity and by benchmarking them on real hardware and we compare them with classical algorithms.
Cited by 0
Piyush Kumar · 2003
Cited by 24
Matteo Frigo, Charles E. Leiserson, Harald Prokop et al. · ACM Transactions on Algorithms · 2012
This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious : no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size M and cache-line length B where M = Ω ( B 2 ), the number of cache misses for an m × n matrix transpose is Θ (1 + mn / B ). The number of cache misses for either an n -point FFT or the sorting of n numbers is Θ (1 + ( n / B )(1 + log M n )). We also give a Θ ( mnp )-work algorithm to multiply an m × n matrix by an n × p matrix that incurs Θ (1 + ( mn + np + mp )/ B + mnp / B √ M ) cache faults. We introduce an “ideal-cache” model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model can be simulated efficiently by LRU replacement. We offer empirical evidence that cache-oblivious algorithms perform well in practice.
Cited by 187
Sriram Sellappa And, Siddhartha Chatterjee · 2001
. Multigrid is widely used as an efficient solver for sparse linear systems arising from the discretization of elliptic boundary value problems. Linear relaxation methods like Gauss-Seidel and Red-Black Gauss-Seidel form the principal computational component of multigrid, and thus affect its efficiency. In the context of multigrid, these iterative solvers are executed for a small number of iterations (2--8). We exploit this property of the algorithm to develop a cache-efficient multigrid, by focusing on improving the memory behavior of the linear relaxation methods. The efficiency in our cache-efficient linear relaxation algorithm comes from two sources: reducing the number of data cache and TLB misses, and reducing the number of memory references by keeping values register-resident. Experiments on five modern computing platforms show a performance improvement of 1.15--2.7 times over a standard implementation of Full Multigrid V-Cycle. 1 Introduction The growing speed gap ...
Cited by 0
Sriram Sellappa, Siddhartha Chatterjee · Lecture notes in computer science · 2001
Cited by 16
А.П. Маслакай, П.М. Урвачев · 2026
Cited by 0
2008
We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious matrix multiplication incurs O(n 3 / √ Z + (P n) 1/3 n 2) cache misses when executed by the Cilk scheduler on a machine with P processors, each with a cache of size Z, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache oblivious algorithm for 1D stencil computations, which incurs O(n 2 /Z +n+ √ P n 3+ɛ) cache misses with high probability. 1
Cited by 0
Nils Klarlund, Nils Klarlund, Theis Rauhe et al. · 1996
Within the last few years, CPU speed has greatly overtaken memory speed. For this reason, implementation of symbolic algorithms--- with their extensive use of pointers and hashing---must be reexamined.
Cited by 0
Matteo Frigo, Charles E. Leiserson, Harald Prokop et al. · 1999
Abstract This paper presents asymptotically optimal algorithms for rectangular matrix transpose, FFT, and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious: no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size Z and cache-line length L where Z=Ω(L 2)the number of cache misses for an m n matrix transpose is Θ(1+mn=L). The number of cache misses for either an n-point FFT or the sorting of n numbers is Θ(1+(n=L)(1+log n)). Z We also give an Θ(mnp)-work algorithm to multiply an m n matrix by an n p matrix that incurs Θ(1+(mn+np+mp)=L+mnp=LpZ)cache faults. We introduce an “ideal-cache ” model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model can be simulated efficiently by LRU replacement. We also provide preliminary empirical results on the effectiveness of cache-oblivious algorithms in practice. 1.
Cited by 0
Georgios S. Paschos · Arrow@dit (Dublin Institute of Technology) · 2020
Caching refers to the act of replicating information at a faster (or closer) medium with the purpose of improving performance. This deceptively simple idea has given rise to some of the hardest optimization problems in the fields of computer systems, networking, and the Internet; many of which remain unsolved several years after their conception. While a wealth of research contributions exists from the topics of memory systems, data centers, Internet traffic, CDNs, and recently wireless networks, the literature is dispersed and overlapping at times. In this monograph, the authors focus on the fundamental underlying mathematical models, into a powerful framework for performing optimization of caching systems. In doing so they the present the reader with a solid background for the anticipated explosion in caching research, and provide a didactic view into how engineers have managed to infuse mathematical models into the study of caching over the last 40 years.
Cited by 22Open access
Michael J. Franklin · Kluwer international series in engineering and computer science · 1996
Cited by 0
Yuan Tang, Weiguo Gao · 2021
Frigo et al. proposed an ideal cache model and a recursive technique to design sequential cache-efficient algorithms in a cache-oblivious fashion. Ballard et al. pointed out that it is a fundamental open problem to extend the technique to an arbitrary architecture. Ballard et al. raised another open question on how to parallelize Strassen’s algorithm exactly and efficiently on an arbitrary number of processors.
Cited by 3
Piyush Kumar · 2008
Cited by 0
R. Angrish, Deepak Garg · 2011
Abstract— Sorting is a process of rearranging a sequence of objects into some kind of predefined linear order. String data is very common and most occurring data type. Sorting a string involves comparison it character by character which is more time consuming than integer sorting. Also, sorting forms the basis of many applications like data processing, databases, pattern matching and searching etc. So implementing improvements to make it fast and efficient will help in reducing the computational time and thus making our applications run faster. This paper briefs about various fast and efficient string sorting algorithms. The algorithms have been divided into two categories: cache-aware and cache-oblivious. The various algorithms discussed are: CRadix Sort, Burstsort and cache- oblivious string sorting algorithm. The improvement in CRadix Sort is achieved by starting the sorting with the most significant digit and associating a small block of main memory called the key buffer to each key and sorting a portion of each key into its corresponding key buffer. Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. The cache- oblivious string sorting algorithm is a randomized algorithm for string sorting which uses signature technique (reduces the sequence by creating a set of signatures strings having the same trie structure as the original set) to sort strings. comparison is done character by character unlike integer sorting in which the entire key is compared at once and also string lengths are variable and swapping them is more difficult. Now-a-days manipulation of large data sets is a common thing in every area of application like databases, digital libraries, etc. The size of data sets have increased to such an extent that they now do not fit into the internal memory of the computer systems thus they need to be stored in external memory devices or secondary storages like CD, disks, etc., thus increasing the latency time as the external memories are slower than the cache memory. If the problem set is very large the latency time dominates the overall execution time thereby increasing the computation time. The difference in speeds of the memories is increasing rapidly with increasing technology thus leading to increase in latency time i.e., increasing I/O bottleneck making the situation worse (12). The performance of traditional string sorting algorithms degrades when the problem set does not fit into internal memory. This paper discusses various algorithms that aim at minimizing the number of cache misses so that the I/O bottleneck problem can be reduced thus making it more efficient and fast..
Cited by 5
Thomas R. Puzak · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · 1985
This thesis describes a model used to analyze the replacement decisions made by LRU and OPT (Least-Recently-Used and an optimal replacement-algorithm). The model identifies a set of lines in the LRU cache that are dead, that is, lines that must leave the cache before they can be rereferenced. The model shows that the majority of the cache misses that OPT avoids over LRU come from the most-recently-discarded lines of the LRU cache. Also shown is that a very small set of lines account for the majority of the misses that OPT avoids over LRU. OPT requires perfect knowledge of the future and is not realizable, but our results lead to three realizable near-optimal replacement algorithms. These new algorithms try to duplicate the replacement decisions made by OPT. Simulation results, using a trace-tape and cache simulator, show that these new algorithms achieve up to eight percent fewer misses than LRU and obtain about 20 percent of the miss reduction that OPT obtains. Also presented in the thesis are two new trace-tape reduction techniques. Simulation results show that reductions in trace-tape length of two orders of magnitude are possible with little or no simulation error introduced.
Cited by 130
Blelloch, Guy E., Gibbons, Phillip B, Simhadri, Harsha Vardhan · KiltHub Repository · 2018
In this paper we explore a simple and general approach for developing parallel algorithms that lead to good cache complexity on a variety of parallel cache architectures. The approach is to design nested parallel algorithms that have low depth (span, critical path length) and for which the natural sequential evaluation order has low cache complexity in the cache-oblivious model. We describe several cache-oblivious algorithms with optimal work, polylogarithmic depth, and sequential cache complexities that match the best sequential algorithms, including the first such algorithms for sorting and for sparse-matrix vector multiply on matrices with good vertex separators. Our sorting algorithm yields the first cache-oblivious algorithms with polylogarithmic depth and low sequential cache complexities for list ranking, Euler tour tree labeling, tree contraction, least common ancestors, graph connectivity, and minimum spanning forest. Using known mappings, our results lead to low cache complexities on multi-core processors (and shared memory multiprocessors) with a single level of private caches or a single shared cache. We generalize these mappings to a multi-level parallel tree-of-caches model that reflects current and future trends in multi-core cache hierarchies—these new mappings imply that our algorithms also have low cache complexities on such hierarchies. The key factor in obtaining these low parallel cache complexities is the low depth of the algorithms we propose.
Cited by 0Open access
Guy E. Blelloch , Phillip B. Gibbons, Harsha Vardhan Simhadri · 2009
In this paper we explore a simple and general approach for developing parallel algorithms that lead to good cache complexity on a variety of parallel cache architectures. The approach is to design nested parallel algorithms that have low depth (span, critical path length) and for which the natural sequential evaluation order has low cache complexity in the cache-oblivious model. We describe several cache-oblivious algorithms with optimal work, polylogarithmic depth, and sequential cache complexities that match the best sequential algorithms, including the first such algorithms for sorting and for sparse-matrix vector multiply on matrices with good vertex separators. Our sorting algorithm yields the first cache-oblivious algorithms with polylogarithmic depth and low sequential cache complexities for list ranking, Euler tour tree labeling, tree contraction, least common ancestors, graph connectivity, and minimum spanning forest. Using known mappings, our results lead to low cache complexities on multi-core processors (and shared-memory multiprocessors) with a single level of private caches or a single shared cache. We generalize these mappings to a multi-level parallel tree-of-caches model that reflects current and future trends in multi-core cache hierarchies—these new mappings imply that our algorithms also have low cache complexities on such hierarchies. The key factor in obtaining these low parallel cache complexities is the low depth of the
Cited by 0