High-Performance GPU Code Generation for Mining Motifs in Temporal Graphs

This is hybrid meeting. The physical room is 32-D463 (Star). The Zoom registration link is https://mit.zoom.us/meeting/register/tJMtdOqgrTwsGNV_k0Nk6JjLMk-G6GFzTRyk.

******************IMPORTANT NOTE ABOUT ONLINE REGISTRATION******************
- The registration link for 2023 is the same as the link from 2022.
- Please save the Zoom link that you receive after you register. This link will stay the same for all subsequent Fast Code seminars.
- Zoom does not recognize a second registration, and will not send out the link a second time. The organizers will not be notified of any second registration.
- If you have any problems with registration, please contact lindalynch@csail.mit.edu by 12pm on the day of the seminar, so that we can try to resolve it before the seminar begins.
*********************************************************************

Abstract:
Temporal motif mining is the task of finding the occurrences of subgraph patterns within
a large input temporal graph that obey the specified structural and temporal constraints.
Despite its utility in several critical application domains that demand high performance
(e.g., detecting fraud in financial transaction graphs), the performance of existing software
is limited on commercial hard- ware platforms, in that it runs for tens of hours. In this talk,
I will present Everest - a system that efficiently maps the workload of mining (supports
both enumeration and counting) temporal motifs to the highly parallel GPU architecture.
Using input temporal graph and a more expressive user-defined temporal motif query
definition, Everest generates an execution plan and runtime primitives that optimize the
workload execution by exploiting the high compute throughput of a GPU. Everest
generates motif-specific mining code to reduce long-latency memory accesses and
frequent thread divergence operations. Everest incorporates novel low-cost runtime
mechanisms to enable load balancing to improve GPU hardware utilization. To support
large graphs that do not fit on GPU memory, Everest also supports multi-GPU execution
by intelligently partitioning the edge list that prevents inter-GPU communication. Everest
hides the implementation complexity of presented optimizations away from the targeted
system user for better usability. Our evaluation shows that, using proposed optimizations,
Everest improves the performance of a baseline GPU implementation by 19x, on average.

Speaker Bio:
Nishil Talati is an Assistant Research Scientist (Research Faculty) at the CSE department
of University of Michigan. He earned his PhD from University of Michigan. Nishil’s
research interests include computer architecture and systems software design for
improving the performance of modern data-intensive workloads. His research is published
at several top-tier venues including ISCA, MICRO, HPCA, ASPLOS, and others. Nishil’s
work has been recognized as the 2021 HPCA best paper award, 2023 DATE best paper
honorable mention, and 2023 IISWC best paper nominee.

Relevant Publication:
Y. Yuan, H. Ye, S. Vedula, W. Kaza, and N. Talati, "Everest: GPU-Accelerated System for Mining Temporal
Motifs," at International Conference on Very Large Databases (VLDB 2024).