Table of Contents
Cache Efficient Heaps
The memory model
Relevance of Hierarchical Memory Model
Cache Model: characteristics
Algorithm Design
Efficient Heaps for RAM model
Why Floyd’s Algo may not be better!!!
PPT Slide
PPT Slide
Cache Efficient Heaps (1) Cache Alligned Heaps
Why d-ary heaps might not be bad after all!!!
PPT Slide
Cache Efficient Heaps (2) Alligned d-ary Heaps
Results Misses per iteration
Results Misses per iteration
Results Instructions per iteration
Results Time (per iteration) of Heapsort
How to improve the priority queues further
An idea from external sorting
A possible realization of the previous ideas
An important point
How to Insert and deletemin
A problem:- What if no buffers can be added.
Architecture of Priority queue in the Sander’s paper
Results
Result
Results
Results
Bibliography
|
Author: Mausam , Nishant Sharma
|