UC Riverside

While single machine MapReduce systems can squeeze out maximum performance from available multi-cores, they are often limited by the size of main memory and can thus only process small datasets. Even though today’s computers are equipped with efficient secondary storage devices, the frameworks do not utilize these devices mainly because disk access latencies are much higher than those for main memory. Therefore, a single machine set up of Hadoop system performs much slower when it is presented with the datasets larger than the main memory. Moreover, such frameworks also require tuning a lot of parameters which puts an added burden on the programmer. While distributed computational resources are now easily available, efficiently performing large scale computations still remain a challenge due to out-of-memory errors and complexity involved in handling distributed systems. Therefore, we develop techniques to perform large-scale processing on a single machine by reducing the amount of IO and exploiting sequential locality when using disks.First, this dissertation presents OMR, a single machine out-of-core MapReduce system that can efficiently handle datasets that are far larger than the size of main memory and guarantees linear scaling with the growing data sizes. OMR actively minimizes the amount of data to be read/written to/from disk via on-the-fly aggregation and it uses block sequential disk read/write operations whenever disk accesses become necessary to avoid running out of memory. We theoretically prove OMR’s linear scalability and empirically demonstrate it by processing datasets that are up to 5× larger than main memory. Our experiments show that in comparison to the standalone single-machine setup of the Hadoop system, OMR delivers far higher performance. Also OMR avoids out-of-memory crashes for large datasets and delivers high performance for datasets that fit in main memory.

Second, this dissertation presents a single-level out-of-core partitioner for large irregular graphs GO, which can successfully partition large graphs by performing just two passes over the entire input graph, partition creation pass that creates balanced partitions and partition refinement pass that reduces edgecuts in a memory constrained manner via disk-based processing. For graphs that can be successfully partitioned by the widely used Mt-Metis system on a single machine, GO produces balanced 8-way partitions with 11.8× to 76.2× fewer edgecuts using 1.9× to 8.3× less memory in comparable runtime.

Finally, we extend the API of the OMR system to enable graph partitioning and partition-based graph processing for large graphs that do not fit in memory. Our ex- periments show that the extended OMRGx system can be easily used to partition large graphs and perform the partition-based graph processing. The API provided allows the programmer to focus on the programming logic while remaining completely oblivious of the out-of-core processing required to handle large graphs.