A quantitative evaluation of data compression in the memory hierarchy

This thesis explores the use of lossless data compression in the memory hierarchy of contemporary computer systems. Data compression may realise performance benefits by increasing the capacity of a level in the memory hierarchy and by improving the bandwidth between two levels in the memory hierarchy. Lossless data compression is already widely used in parts ofthe memory hierarchy. However, most of these applications are characterised by targeting inexpensive and relatively low performance devices such as magnetic disk and tape devices. The consequences of this are that the benefits of data compression are not realised to their full potential. This research aims to understand how the benefits of data compression can be realised for levels of the memory hierarchy which have a greater impact on system performance and system cost. This thesis presents a review of data compression in the memory hierarchy and argues that main memory compression has the greatest potential to improve system performance. The review also identifies three key issues relating to the use of data compression in the memory hierarchy. Quantitative investigations are presented to address these issues for main memory data compression. The first investigation is into memory data, and shows that memory data from a range of Unix applications typically compresses to half its original size. The second investigation develops three memory compression architectures, taking into account the results of the previous investigation. Furthermore, the management of compressed data is addressed and management methods are developed which achieve storage efficiencies in excess of 90% and typically complete allocation and de allocation operations with only a few memory accesses. The experimental work then culminates in a performance investigation. This shows that when memory resources are strecthed, hardware based memory compression can improve system performance by up to an order of magnitude. Furthermore, software based memory compression can improve system performance by up to a factor of 2. Finally, the performance models and quantitative results contained in this thesis enable us to identify under what conditions memory compression offers performance benefits. This may help designers incorporate memory compression into future computer systems.