# SISA: Set-Centric Instruction Set Architecture for Graph Mining on Processing-in-Memory Systems

arXiv: https://arxiv.org/abs/2104.07582 · HTML: https://mlsanity.com/paper/2104.07582/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2021.

## Built on by (most cited first, 17 of 17)

- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Motif Prediction with Graph Neural Networks](https://mlsanity.com/paper/2106.00761/) (2021)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [Accelerating Neural Network Inference with Processing-in-DRAM: From the Edge to the Cloud](https://mlsanity.com/paper/2209.08938/) (2022)
- [PIM-Opt: Demystifying Distributed Optimization Algorithms on a Real-World Processing-In-Memory System](https://mlsanity.com/paper/2404.07164/) (2024)
- [Machine Learning Training on a Real Processing-in-Memory System](https://mlsanity.com/paper/2206.06022/) (2022)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025)
- [An Experimental Evaluation of Machine Learning Training on a Real Processing-in-Memory System](https://mlsanity.com/paper/2207.07886/) (2022)
- [Heterogeneous Data-Centric Architectures for Modern Data-Intensive Applications: Case Studies in Machine Learning and Databases](https://mlsanity.com/paper/2205.14664/) (2022)
- [Phases, Modalities, Temporal and Spatial Locality: Domain Specific ML Prefetcher for Accelerating Graph Analytics](https://mlsanity.com/paper/2212.05250/) (2022)
- [Harmonia: Enhancing Data Placement and Migration in Hybrid Storage Systems via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2503.20507/) (2025)
- [GraphSeek: Next-Generation Graph Analytics with LLMs](https://mlsanity.com/paper/2602.11052/) (2026)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [DCC: Data-Centric Compilation of Machine Learning Kernels for Processing-In-Memory Architectures](https://mlsanity.com/paper/2511.15503/) (2025)

## Abstract (arXiv)

Simple graph algorithms such as PageRank have been the target of numerous hardware accelerators. Yet, there also exist much more complex graph mining algorithms for problems such as clustering or maximal clique listing. These algorithms are memory-bound and thus could be accelerated by hardware techniques such as Processing-in-Memory (PIM). However, they also come with nonstraightforward parallelism and complicated memory access patterns. In this work, we address this problem with a simple yet surprisingly powerful observation: operations on sets of vertices, such as intersection or union, form a large part of many complex graph mining algorithms, and can offer rich and simple parallelism at multiple levels. This observation drives our cross-layer design, in which we (1) expose set operations using a novel programming paradigm, (2) express and execute these operations efficiently with carefully designed set-centric ISA extensions called SISA, and (3) use PIM to accelerate SISA instructions. The key design idea is to alleviate the bandwidth needs of SISA instructions by mapping set operations to two types of PIM: in-DRAM bulk bitwise computing for bitvectors representing high-degree vertices, and near-memory logic layers for integer arrays representing low-degree vertices. Set-centric SISA-enhanced algorithms are efficient and outperform hand-tuned baselines, offering more than 10x speedup over the established Bron-Kerbosch algorithm for listing maximal cliques. We deliver more than 10 SISA set-centric algorithm formulations, illustrating SISA's wide applicability.