Image alignment and dynamic graph analytics : two case studies of how managing data movement can make (parallel) code run fast

High performance applications are becoming increasingly resource hungry. We want to solve more complex problems and use more data to get higher quality results. However, the more data we store, the slower it is to access any piece. This effect is seen directly in the memory hierarchy. We can access our caches faster than our memory, which is faster than reading our disk, which is still faster than going across the network. This means that when processing large data sets, we can spend a large portion of our time simply in data movement. However, there is much we can do to optimize our programs to exploit our memory systems, so that we do not incur performance degradation as our datasets grow. I show how the careful design of data structures and algorithms allow us to scale to much larger datasets without impacting performance due to the cost of data movement. I demonstrate the impact of these designs with two case studies. The first examines large-scale image alignment, where I describe how to align a petabyte scale set of images in memory on a single machine and match the performance of current cluster solutions. I achieve .6 - .8 TB/hr on a medium-sized multicore and linear scalability on hundreds of nodes in a shared supercomputing cluster. The second case study explores dynamic graph analytics, where I describe the design of a new data structure for storing dynamic graphs that matches the performance of standard, static formats and enables high performance, dynamic operations achieving millions of updates per second.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Wheatman, Brian.

Advisor dc:contributor.advisor

• Charles E. Leiserson.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/123023

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/123023