Cache-Aware and Cache-Oblivious Algorithms

Abstract

With the development in technology, the difference between the speeds of processor and memory access impose a penalty if the programs do not take advantage of the memory hierarchy. Also while sorting strings in external memory this latency plays a very vital role as it degrades the performance of the algorithms. 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. Cache-oblivious algorithms help in achieving optimal use of cache without the knowledge of its size. This thesis consists of discussion of cache-aware and cache-oblivious algorithms for general algorithms like large integer multiplication and for string sorting algorithms. A comparison of various existing algorithms has also been done in this thesis based on various parameters such as the type of algorithm, technique used, basic principle of working and the type of data structure used. The thesis also provide a new algorithm for string sorting which uses the concept of tried linear hashing and uses the cache-oblivious blind trie for strings. The algorithm developed has been tested for random strings and URLs and the result is depicted in the form of graphs