{"646375":{"#nid":"646375","#data":{"type":"event","title":"PhD Defense by Prasun Gera","body":[{"value":"\u003Cp\u003ETitle: Overcoming Memory Capacity Constraints for Large Graph Applications on GPUs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPrasun Gera\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPh.D. candidate\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDate: Friday, April 23rd, 2021\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETime: 10 a.m. - 12 p.m. (Eastern Time)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/bluejeans.com\/315983964\u0022\u003Ehttps:\/\/bluejeans.com\/315983964\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECommittee:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Hyesoon Kim (Advisor, School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Santosh Pande (School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Richard Vuduc (School of Computer Science and Engineering, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Moinuddin Qureshi (School of Computer Science, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Tushar Krishna (School of Electrical and Computer Engineering, Georgia Institute of Technology)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGraphics Processing Units (GPUs) have been used successfully for accelerating a wide variety of\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eapplications in the domains of scientific computing, machine learning, and data analytics over the\u003C\/p\u003E\r\n\r\n\u003Cp\u003Elast decade. Two important trends that have emerged across these domains are that for a lot of\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ereal-world problems, the working sets are larger than a GPU\u0026rsquo;s memory capacity, and that the data is\u003C\/p\u003E\r\n\r\n\u003Cp\u003Esparse. In this dissertation, we focus on graph analytics, for which the majority of prior work has\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ebeen restricted to graphs of modest sizes that fit in memory. Real world graphs such as social\u003C\/p\u003E\r\n\r\n\u003Cp\u003Enetworks and web graphs require tens to hundreds of gigabytes of storage whereas GPU memory is\u003C\/p\u003E\r\n\r\n\u003Cp\u003Etypically in the order of a few gigabytes. We investigate the following question: How can we\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eaccelerate graph applications on GPUs when the graphs do not fit in memory?\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis question opens up two lines of inquiry. First, we consider the system architecture where the\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGPU can address larger, albeit slower, host memory that is behind an interconnect such as PCI-e.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWhile this increases the total addressable memory, graph applications have poor locality that makes\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eefficient use of this architecture challenging. We formulate the locality problem as a graph\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eordering problem and propose efficient reordering methods for large graphs. The solution is general\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eenough that it can be extended to other similar architectures and even beneficial in cases where\u003C\/p\u003E\r\n\r\n\u003Cp\u003Egraphs fit in memory.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESecond, we consider graph compression as a complementary approach. Conventional approaches to graph\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ecompression have been CPU-centric in that the decompression stage is sequential and branch\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eintensive. We devise an efficient graph compression format for large sparse graphs that is amenable\u003C\/p\u003E\r\n\r\n\u003Cp\u003Eto run-time decompression on GPUs. The decompression stage is parallel and load balanced so that it\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ecan use the computational resources of GPUs effectively. In effect, analytics kernels can decompress\u003C\/p\u003E\r\n\r\n\u003Cp\u003Ethe graph and do computation on the fly without decompressing the entire graph since the entire\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edecompressed graph would not fit in memory.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Overcoming Memory Capacity Constraints for Large Graph Applications on GPUs "}],"uid":"27707","created_gmt":"2021-04-12 15:49:57","changed_gmt":"2021-04-12 15:49:57","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-04-23T11:00:00-04:00","event_time_end":"2021-04-23T15:00:00-04:00","event_time_end_last":"2021-04-23T15:00:00-04:00","gmt_time_start":"2021-04-23 15:00:00","gmt_time_end":"2021-04-23 19:00:00","gmt_time_end_last":"2021-04-23 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}