Mint: An accelerator for mining temporal motifs

Talati N, Ye H, Vedula S, Chen K-Y, Chen Y, Liu D, Yuan Y, Blaauw D, Bronstein AM, Mudge T, Dreslinski R. 2022. Mint: An accelerator for mining temporal motifs. 55th IEEE/ACM International Symposium on Microarchitecture. MICRO: Symposium on Microarchitecture.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Talati, Nishil; Ye, Haojie; Vedula, Sanketh; Chen, Kuan-Yu; Chen, Yuhan; Liu, Daniel; Yuan, Yichao; Blaauw, David; Bronstein, Alex M.ISTA ; Mudge, Trevor; Dreslinski, Ronald
Abstract
A variety of complex systems, including social and communication networks, financial markets, biology, and neuroscience are modeled using temporal graphs that contain a set of nodes and directed timestamped edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs in that they also account for edge ordering and time duration, in addition to the graph structure. Mining temporal motifs is a fundamental problem used in several application domains. However, existing software frameworks offer suboptimal performance due to high algorithmic complexity and irregular memory accesses of temporal motif mining.This paper presents Mint—a novel accelerator architecture and a programming model for mining temporal motifs efficiently. We first divide this workload into three fundamental tasks: search, book-keeping, and backtracking. Based on this, we propose a task-centric programming model that enables decoupled, asynchronous execution. This model unlocks massive opportunities for parallelism, and allows storing task context information on-chip. To best utilize the proposed programming model, we design a domain-specific hardware accelerator using its data path and memory subsystem design to cater to the unique workload characteristics of temporal motif mining. To further improve performance, we propose a novel optimization called search index memoization that significantly reduces memory traffic. We comprehensively compare the performance of Mint with state-of-the-art temporal motif mining software frameworks (both approximate and exact) running on both CPU and GPU, and show 9×−2576× benefit in performance.
Publishing Year
Date Published
2022-10-01
Proceedings Title
55th IEEE/ACM International Symposium on Microarchitecture
Publisher
Institute of Electrical and Electronics Engineers
Conference
MICRO: Symposium on Microarchitecture
Conference Location
Chicago, IL, United States
Conference Date
2022-10-01 – 2022-10-05
IST-REx-ID

Cite this

Talati N, Ye H, Vedula S, et al. Mint: An accelerator for mining temporal motifs. In: 55th IEEE/ACM International Symposium on Microarchitecture. Institute of Electrical and Electronics Engineers; 2022. doi:10.1109/micro56248.2022.00089
Talati, N., Ye, H., Vedula, S., Chen, K.-Y., Chen, Y., Liu, D., … Dreslinski, R. (2022). Mint: An accelerator for mining temporal motifs. In 55th IEEE/ACM International Symposium on Microarchitecture. Chicago, IL, United States: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/micro56248.2022.00089
Talati, Nishil, Haojie Ye, Sanketh Vedula, Kuan-Yu Chen, Yuhan Chen, Daniel Liu, Yichao Yuan, et al. “Mint: An Accelerator for Mining Temporal Motifs.” In 55th IEEE/ACM International Symposium on Microarchitecture. Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/micro56248.2022.00089.
N. Talati et al., “Mint: An accelerator for mining temporal motifs,” in 55th IEEE/ACM International Symposium on Microarchitecture, Chicago, IL, United States, 2022.
Talati N, Ye H, Vedula S, Chen K-Y, Chen Y, Liu D, Yuan Y, Blaauw D, Bronstein AM, Mudge T, Dreslinski R. 2022. Mint: An accelerator for mining temporal motifs. 55th IEEE/ACM International Symposium on Microarchitecture. MICRO: Symposium on Microarchitecture.
Talati, Nishil, et al. “Mint: An Accelerator for Mining Temporal Motifs.” 55th IEEE/ACM International Symposium on Microarchitecture, Institute of Electrical and Electronics Engineers, 2022, doi:10.1109/micro56248.2022.00089.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar