1 SMA5509: Theory of Parallel Systems Project Proposal Cache-oblivious sorting for Burrows-Wheeler Transform

Burrows and Wheeler [1] presented a lossless text compression method based on Burrows-Wheeler Transform (BWT). A computationally expensive activity during this compression is the sorting of all rotations of the block of data to be compressed. The original implementation incurs the worst case complexity of O(N 2 log(N)), if there is a high degree of repetitiveness in the input file. The number of characters, N, is typically quite large and such worst case behavior is unacceptable. In [2], Sadakane has provided a sorting algorithm with a better worst case bound of O(Nlog(N) 2). Seward [3], however, has shown that even though Sadakane’s algorithm has better asymptotic behavior, it incurs high overheads and a tuned direct-comparison implementation of rotation sorting performs much better in practice. The tuned implementation presented in [3] mainly improves the performance of the original algorithm by minimizing the memory references, especially the cache misses for most inputs. The author concludes that these memory effects are critical for the performance of the algorithm on the modern architectures. We believe that such a heavy dependence of the performance of the algorithm on the memory effects can be minimized by developing a cache-oblivious implementation of the algorithm. Such an implementation is especially useful for the compression applications such as bzip2 based on the algorithm, which are required to perform well on a wide range of platforms and their underlying architectures. We proceed to give an overview of Cache Obliviousness and how it serves the purpose of making BWT sorting more efficient. Cache Oblivious Algorithms 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. It has been shown in the past [4] that several cache oblivious algorithms use cache as effectively as cache-aware algorithms. The cache obliviousness concept has been employed to efficiently perform tasks like rectangula