MotivationMotivationModelsRAM ModelExternal Memory ModelCache Oblivious ModelCache Oblivious AlgorithmsBrief HistoryMain ToolMatrix TranspositionCache Oblivious Data StructuresStatic Data StructuresSummarySummaryModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresCache Oblivious Algorithmsand Data StructuresTheory and PracticeHitesh BallaniDepartment of Computer ScienceCornell UniversityCS 61231stMarchHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationMemory Hierarchy - A Fact of Lifea.k.a. the essence of CS 612Multi-level memory hierarchies are omnipresentMemory speed ∝ (Distance from processor)−1Good locality is important for achieving high performanceSPEEDREGISTERL1 CacheL2 CacheL3 CacheMemoryDiskCAPACITYHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationHardware Parametersits a jungle out thereModern hardware is not uniform - many differentparametersIn homework 1, we used X-RAY to measureCPU speedInstruction Latency/ThroughputNumber of registersSpecial Instructions (eg. fma)Cache Stride/Associativity/Capacity/Line-Size/Hit-LatencyCurrent programsignore the parameters - poor performancedetermine the parametersby hand, eg. hand-optimized BLAS librariesautomatically, eg. ATLAS generated BLAS librariesHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationHardware Parametersits a jungle out thereModern hardware is not uniform - many differentparametersIn homework 1, we used X-RAY to measureCPU speedInstruction Latency/ThroughputNumber of registersSpecial Instructions (eg. fma)Cache Stride/Associativity/Capacity/Line-Size/Hit-LatencyCurrent programsignore the parameters - poor performancedetermine the parametersby hand, eg. hand-optimized BLAS librariesautomatically, eg. ATLAS generated BLAS librariesHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationHardware Parametersits a jungle out thereModern hardware is not uniform - many differentparametersIn homework 1, we used X-RAY to measureCPU speedInstruction Latency/ThroughputNumber of registersSpecial Instructions (eg. fma)Cache Stride/Associativity/Capacity/Line-Size/Hit-LatencyCurrent programsignore the parameters - poor performancedetermine the parametersby hand, eg. hand-optimized BLAS librariesautomatically, eg. ATLAS generated BLAS librariesHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationIs it possible to abstract away this complexity?A model thatcould capture the essence of the hierarchywithout knowing its specificsAlgorithms that are efficient on all hierarchiessimultaneouslyand this holy grail is what Cache Oblivious Algorithms aimto attainHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationIs it possible to abstract away this complexity?A model thatcould capture the essence of the hierarchywithout knowing its specificsAlgorithms that are efficient on all hierarchiessimultaneouslyand this holy grail is what Cache Oblivious Algorithms aimto attainHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresMotivationIs it possible to abstract away this complexity?A model thatcould capture the essence of the hierarchywithout knowing its specificsAlgorithms that are efficient on all hierarchiessimultaneouslyand this holy grail is what Cache Oblivious Algorithms aimto attainHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresRAM ModelExternal Memory ModelCache Oblivious ModelRAM Model"Introduction to Algorithms" by Cormen et. al.The model we use to analyze algorithms in CS 681All basic operations take up constant timeComplexity is the number of operations executedLimited practical useDoes not take into account the differences of speeds ofrandom access to memoryHierarchical Memory Modelsaccount for multi-level hierarchiesfor eg, Aggarwal et. al., ’87too complicated for practical useHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresRAM ModelExternal Memory ModelCache Oblivious ModelRAM Model"Introduction to Algorithms" by Cormen et. al.The model we use to analyze algorithms in CS 681All basic operations take up constant timeComplexity is the number of operations executedLimited practical useDoes not take into account the differences of speeds ofrandom access to memoryHierarchical Memory Modelsaccount for multi-level hierarchiesfor eg, Aggarwal et. al., ’87too complicated for practical useHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresRAM ModelExternal Memory ModelCache Oblivious ModelRAM Model"Introduction to Algorithms" by Cormen et. al.The model we use to analyze algorithms in CS 681All basic operations take up constant timeComplexity is the number of operations executedLimited practical useDoes not take into account the differences of speeds ofrandom access to memoryHierarchical Memory Modelsaccount for multi-level hierarchiesfor eg, Aggarwal et. al., ’87too complicated for practical useHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresRAM ModelExternal Memory ModelCache Oblivious ModelExternal Memory Model (I/O Model)a two parameter model2 storage levelsCacheMemoryComplexity - number of transfersbetween cache and memoryAggarwal and Vitter, ’88MEMORYI/OBCACHEMCPULimitationsParameters B and M must be knownDoes not handle multiple memory levelsHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache Oblivious Data StructuresRAM ModelExternal Memory ModelCache Oblivious ModelExternal Memory Model (I/O Model)a two parameter model2 storage levelsCacheMemoryComplexity - number of transfersbetween cache and memoryAggarwal and Vitter, ’88MEMORYI/OBCACHEMCPULimitationsParameters B and M must be knownDoes not handle multiple memory levelsHitesh BallaniCache Oblivious Algorithms and Data StructuresModelsCache Oblivious AlgorithmsCache