Events for the 1st week of June
-
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Tue, May 29, 2018 @ 10:30 AM - 11:30 AM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
Speaker: Julian Shun, Massachusetts Institute of Technology
Talk Title: Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Abstract: There has been significant interest in parallel graph processing recently due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones that use the Hyperlink graph are done in distributed or external memory. Therefore it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory.
With a graph of this size it is important to use theoretically-efficient parallel algorithms as even minor inefficiencies in the work or parallelism of an algorithm can lead to a significant increase in running time. This talk shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly-available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 13 important graph problems. We also present the optimizations and techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale.
Biography: Julian Shun is an assistant professor in Electrical Engineering and Computer Science at MIT. He is interested in the theory and practice of parallel computing, especially parallel graph processing frameworks, algorithms, data structures, and tools for deterministic parallel programming. He has received the ACM Doctoral Dissertation Award, CMU School of Computer Science Doctoral Dissertation Award, Miller Research Fellowship, Facebook Graduate Fellowship, and a best student paper award at the IEEE Data Compression Conference.
Host: Xuehai Qian, x04459, xuehai.qian@usc.edu
Location: Hughes Aircraft Electrical Engineering Center (EEB) - 132
Audiences: Everyone Is Invited
Contact: Gerrielyn Ramos
-
Towards Smarter Hardware Prediction Mechanisms
Fri, Jun 01, 2018 @ 10:00 AM - 11:00 AM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
Speaker: Akanksha Jain, University of Texas at Austin
Talk Title: Towards Smarter Hardware Prediction Mechanisms
Abstract: In today's data-driven world, memory system performance remains critical to the overall performance of many workloads. In this talk, we present recent work in two aspects of hardware caching: (1) The Hawkeye Cache (ISCA 2016), which introduces a novel method of solving the age-old problem of cache replacement, and (2) Harmony, which uncovers a new design space for cache replacement policies in the presence of prefetching (ISCA 2018). We will then briefly discuss ways that machine learning can help us improve upon these ideas, and we conclude by discussing the broader role machine learning can play in advancing memory system research.
Biography: Akanksha Jain received her PhD in Computer Science from The University of Texas in December 2016. In 2009, she received the B.Tech and M. Tech degrees in Computer Science and Engineering from the Indian Institute of Technology Madras. Her research interests are in computer architecture, with a particular focus on the memory system and on using machine learning techniques to improve the design of memory system optimizations.
Host: Xuehai Qian, x04459, xuehai.qian@usc.edu
Location: Hughes Aircraft Electrical Engineering Center (EEB) - 132
Audiences: Everyone Is Invited
Contact: Gerrielyn Ramos