CORNELL CS 612 - Cache Oblivious Algorithms and Data Structures (48 pages)

Previewing pages 1, 2, 3, 23, 24, 25, 26, 46, 47, 48 of 48 page document View the full content.
View Full Document

Cache Oblivious Algorithms and Data Structures



Previewing pages 1, 2, 3, 23, 24, 25, 26, 46, 47, 48 of actual document.

View the full content.
View Full Document
View Full Document

Cache Oblivious Algorithms and Data Structures

70 views


Pages:
48
School:
Cornell University
Course:
Cs 612 - Compiler Design for High-Performance Architectures
Unformatted text preview:

Models Cache Oblivious Algorithms Cache Oblivious Data Structures Cache Oblivious Algorithms and Data Structures Theory and Practice Hitesh Ballani Department of Computer Science Cornell University CS 612 31st March Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Memory Hierarchy A Fact of Life a k a the essence of CS 612 Multi level memory hierarchies are omnipresent Memory speed Distance from processor 1 Good locality is important for achieving high performance REGISTER L1 Cache L2 Cache SPEED CAPACITY L3 Cache Memory Disk Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Hardware Parameters its a jungle out there Modern hardware is not uniform many different parameters In homework 1 we used X RAY to measure CPU speed Instruction Latency Throughput Number of registers Special Instructions eg fma Cache Stride Associativity Capacity Line Size Hit Latency Current programs ignore the parameters poor performance determine the parameters by hand eg hand optimized BLAS libraries automatically eg ATLAS generated BLAS libraries Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Hardware Parameters its a jungle out there Modern hardware is not uniform many different parameters In homework 1 we used X RAY to measure CPU speed Instruction Latency Throughput Number of registers Special Instructions eg fma Cache Stride Associativity Capacity Line Size Hit Latency Current programs ignore the parameters poor performance determine the parameters by hand eg hand optimized BLAS libraries automatically eg ATLAS generated BLAS libraries Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Hardware Parameters its a jungle out there Modern hardware is not uniform many different parameters In homework 1 we used X RAY to measure CPU speed Instruction Latency Throughput Number of registers Special Instructions eg fma Cache Stride Associativity Capacity Line Size Hit Latency Current programs ignore the parameters poor performance determine the parameters by hand eg hand optimized BLAS libraries automatically eg ATLAS generated BLAS libraries Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Is it possible to abstract away this complexity A model that could capture the essence of the hierarchy without knowing its specifics Algorithms that are efficient on all hierarchies simultaneously and this holy grail is what Cache Oblivious Algorithms aim to attain Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Is it possible to abstract away this complexity A model that could capture the essence of the hierarchy without knowing its specifics Algorithms that are efficient on all hierarchies simultaneously and this holy grail is what Cache Oblivious Algorithms aim to attain Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures Motivation Is it possible to abstract away this complexity A model that could capture the essence of the hierarchy without knowing its specifics Algorithms that are efficient on all hierarchies simultaneously and this holy grail is what Cache Oblivious Algorithms aim to attain Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External Memory Model Cache Oblivious Model RAM Model Introduction to Algorithms by Cormen et al The model we use to analyze algorithms in CS 681 All basic operations take up constant time Complexity is the number of operations executed Limited practical use Does not take into account the differences of speeds of random access to memory Hierarchical Memory Models account for multi level hierarchies for eg Aggarwal et al 87 too complicated for practical use Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External Memory Model Cache Oblivious Model RAM Model Introduction to Algorithms by Cormen et al The model we use to analyze algorithms in CS 681 All basic operations take up constant time Complexity is the number of operations executed Limited practical use Does not take into account the differences of speeds of random access to memory Hierarchical Memory Models account for multi level hierarchies for eg Aggarwal et al 87 too complicated for practical use Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External Memory Model Cache Oblivious Model RAM Model Introduction to Algorithms by Cormen et al The model we use to analyze algorithms in CS 681 All basic operations take up constant time Complexity is the number of operations executed Limited practical use Does not take into account the differences of speeds of random access to memory Hierarchical Memory Models account for multi level hierarchies for eg Aggarwal et al 87 too complicated for practical use Hitesh Ballani Cache Oblivious Algorithms and Data Structures Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External Memory Model Cache Oblivious Model External Memory Model I O Model a two parameter model Aggarwal and Vitter 88 2 storage levels I O Cache Memory CPU Complexity number of transfers between cache and memory C A C H E B M Limitations Parameters B and M must be known Does not handle multiple memory levels Hitesh Ballani Cache Oblivious Algorithms and Data Structures M E M O R Y Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External Memory Model Cache Oblivious Model External Memory Model I O Model a two parameter model Aggarwal and Vitter 88 2 storage levels I O Cache Memory CPU Complexity number of transfers between cache and memory C A C H E B M Limitations Parameters B and M must be known Does not handle multiple memory levels Hitesh Ballani Cache Oblivious Algorithms and Data Structures M E M O R Y Models Cache Oblivious Algorithms Cache Oblivious Data Structures RAM Model External


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Cache Oblivious Algorithms and Data Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Cache Oblivious Algorithms and Data Structures and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?