Design Study of a Computer System Employing Memory Compression

Examensarbete för masterexamen

Please use this identifier to cite or link to this item:
Download file(s):
File Description SizeFormat 
219158.pdfFulltext2.14 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Design Study of a Computer System Employing Memory Compression
Authors: Andersson, Jonas
Doverbo, Niklas
Abstract: Memory compression is a promising technique for computer systems to increase cache and memory capacity, leading to a decrease of the number of required lower-level accesses without adding significant cost or energy consumption to a system. This thesis answers some of the questions arising when implementing a Human algorithm as compression algorithm on main memory content, such as compression factor compared to other compression algorithms and feasibility for compression in a system. This thesis contains a compression analysis of two scale-out benchmarks from CloudSuite. The two benchmarks, Data analytics and Graph analytics, were set up running on virtual machines. While the benchmarks were running, the virtual machines had their memory extracted at multiple occasions. By using the virtual-to-physical address translation for the benchmarks' processes, in combination with the extracted memory sample, it was possible to create images of the memory used by the benchmarks' processes. These images were analysed with several different compression algorithms including Huffman, B I, and FPC. The Huffman algorithm uses a value frequency table (VFT) which contains values and their frequency. The VFT is used to create the encoding for the Human tree where values with high frequency are given a short code word. A larger VFT will give a better compression factor but reduce speed, increase area and energy consumption. This thesis shows that the size of the VFT can be kept small and that the gains in compression factor of having a large VFT significantly decreased with VFT sizes over 1024 entries. The results in the compression analysis show that the memory compression factor for the two CloudSuite benchmarks is around 2.7X for a VFT with 1024 entries. In a traditional computer system blocks and pages are fixed in size. A computer system using memory compression must allow for blocks and pages to vary in size, however, it would be infeasible to allow for all different block and page sizes. The thesis shows the impact on the Huffman compression factor when only particular compression factors or compressed sizes are allowed. Four additional block addressing bits result in a compression loss of between 4%-7%. A similar analysis for pages show that adding four or six additional addressing bits result in compression losses of between 6%-9% and 1%-2%, respectively. Following the compression analysis, a few compression schemes were implemented and evaluated in hardware. One of these schemes, the Huffman coding scheme, was also implemented as part of a proof-of-concept. The proof-of-concept was implemented on a ZedBoard, an evaluation board that incorporates both a dual ARM core as well as programmable logic. The ordinary datapath between the cores and the memory was rerouted to pass through the programmable logic of the ZedBoard. In this programmable logic, the Huffman compressing and decompressing logic was implemented.
Keywords: Data- och informationsvetenskap;Informations- och kommunikationsteknik;Computer and Information Science;Information & Communication Technology
Issue Date: 2015
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
Collection:Examensarbeten för masterexamen // Master Theses

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.