Muthulakshmi Muthukumarasamy and Henry Dietz
Department of Electrical and Computer Engineering, University of Kentucky, USA

As the gap between processor function unit speed and memory speed continues to increase, it becomes appropriate to consider more aggressive methods for making data available when the processor needs them. Hardware write buffers, caches, out-of-order execution and prefetch logic are commonly used to reduce the time spent waiting for data accesses from memory. Compiler loop interchange and layout transformations could also be used to decrease the cost of main memory accesses. Unfortunately, many applications have access patterns for which none of the standard approaches are helpful.

Using smaller data structures can significantly improve performance by allowing the data to reside in higher levels of the memory hierarchy. In this paper, we examine use of lossy data compression technology to augment larger data structures to yield faster typical data access. The particular lossy compression technique evaluated here is compressive hashing, a technique which is complex to implement, but that can efficiently handle random access lookup tables. Both the complexity of creating compressive hash functions and the effectiveness of using them are empirically evaluated with the goal of being able to predict how effective such an approach will be for various data structure and target architecture parameters.

Back to the Workshop Program