Abstract:
Memory is a valuable commodity in datacenters. DRAM is expensive and an expensive consumer of power. With the number of cores per socket growing faster than the memory capacity per socket, memory is increasingly scarce. Given the rise of data-intensive computing, this focus on memory gains increased relevance. Data-intensive computing systems are primarily to designed to operate on large amounts of data from storage. However, in order to overcome the high latencies associated with disk access, applications commonly use memory for performance-sensitive data. Therefore, scarcity of memory can impact the performance of distributed applications significantly.
In this thesis we introduce techniques for memory-efficiency without compromising performance. We introduce a novel data structure called the Compressed Buffer Tree (CBT) which stores data in memory-efficient form and allows computation to be executed on the data with high throughput. The CBT achieves memory-efficiency through the efficient application of data compression and offloading of state of disk. We demonstrate the utility of the CBT through implementations of high-performance, memory-efficient runtimes for the following programming models, listed in order of increasing complexity:
– a synchronous, message-passing model (Pregel)
– an asynchronous, shared-memory model (GraphLab)
]]>