PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Maciej Besta, Raghavendra Kanakagiri, Grzegorz Kwasniewski, Rachata Ausavarungnirun, Jakub Beránek, Konstantinos Kanellopoulos, Kacper Janda, Zur Vonarburg-Shmaria, Lukas Gianinazzi, Ioana Stefan, Juan Gómez Luna, Marcin Copik, Lukas Kapp-Schwoerer, Salvatore Di Girolamo, Marek Konieczny, Nils Blach, Onur Mutlu, Torsten Hoefler

arXiv:2104.07582v2cs.ARcs.DCcs.DScs.PF

TL;DR

Many graph-mining problems are poorly served by existing paradigms, while their complex algorithms are memory-bound and hard to parallelize. SISA exposes set operations through a set-centric ISA and accelerates them with PIM. Its set-centric algorithms are almost always fastest by at least 2× and often more than 10× than non-set schemes; some small-maximum-degree graphs can see smaller speedups or slowdowns.

  • Problem

    Existing graph-processing paradigms do not jointly support many graph-mining problems and offer competitive time complexities, while vertex-centric kernels struggle to express the non-local graph knowledge mining often requires.

    Source: §1 · p. 2

  • Method

    SISA expresses graph-mining algorithms through set operations, implements them as set-centric ISA instructions, and offloads them to PIM.

    Source: §1 · p. 3

  • Results

    SISA is almost always fastest by at least 2× and often more than 10× than non-set schemes across the evaluated problems.

    Source: §9.2 · p. 16

  • Takeaways & Limitations

    The set-centric approach supports broad graph mining and enables algorithms with competitive theoretical time complexities.

    Source: §11 · p. 20

    For some graphs with small maximum degrees, processing too many n-bit dense bitvectors can reduce speedups or cause slowdowns.

    Source: §9.2 · p. 18

Abstract

from arXiv · show

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.

1 INTRODUCTION

Graph mining covers important pattern-matching and learning problems, but existing paradigms provide limited support and competitive work guarantees. SISA builds on set operations to expose parallelism and use PIM, with reported advantages over tuned baselines.

1 INTRODUCTION

  • Many graph-mining problems require non-local graph knowledge that vertex-centric kernels, limited to a vertex’s neighbors, cannot readily express.Graph mining includes pattern matching and learning problems, many of which take at least quadratic time in the number of vertices.Source: §1 · pp. 1–2
  • Existing graph-processing paradigms do not jointly support many graph-mining problems and offer competitive time complexities, motivating a paradigm with both capabilities.The paper identifies graph mining frameworks that focus on only a few problems and usually lack formal total-work guarantees.Source: §1 · p. 2
  • Graph-mining algorithms are memory-bound, while deep recursion, intermediate structures, and load imbalance complicate their acceleration.Increasing parallel threads flattens runtime improvements while stalled CPU cycles rise.Source: §1 · pp. 2–3, Figure 1 · p. 2
  • SISA exposes set operations in a programming paradigm, implements them through set-centric ISA instructions, and offloads those instructions to PIM.The design uses in-DRAM PIM for bitvectors and near-memory PIM for sparse arrays, with instruction variants selected according to set properties.Source: §1 · p. 3
  • The paper reports that SISA-enhanced algorithms are theoretically efficient and empirically outperform tuned parallel baselines, including more than 10× speedup for many real-world graphs over Bron-Kerbosch for maximal-clique listing [91].Its contributions also include programming guidelines, theoretical analysis, and cycle-based simulations against hand-tuned baselines.Source: §1 · p. 3

2 NOTATION AND BACKGROUND

This section establishes graph notation and the set representations and operations used by SISA.

2 NOTATION AND BACKGROUND

  • An undirected graph is modeled as G=(V,E), where V is the vertex set and E⊆V×V is the edge set; their sizes are n and m.Vertices are integers from 1 through n; the notation also defines directed graphs, neighborhoods, degrees, and labeled graphs.Source: §2 · p. 3
  • A vertex set can be stored as a sparse array of its integer members or as a dense bitvector whose set bits identify members.The sparse array uses W|S| bits, while the dense bitvector uses n bits.Source: §2 · p. 3
  • The section points readers to a symbol-and-acronym table and identifies architecture-related symbols as a separate notation group.Further architectural details are deferred to Sections 8 and 9.Source: Table 2 · p. 4, §2 · p. 4
  • SISA uses intersection, union, difference, cardinality, and membership operations on sets that usually contain vertices and sometimes edges.Different algorithms implement these operations.Source: §2 · p. 4

3 OVERVIEW & CROSS-LAYER DESIGN

SISA’s cross-layer design connects set-centric graph algorithms, an ISA for set operations, and PIM hardware. It supports this design with programming guidelines and theoretical analysis.

3 OVERVIEW & CROSS-LAYER DESIGN

  • Set-centric formulations recast graph algorithms in terms of sets and operations, with nested loops for connections between vertex sets often expressible as one intersection.The formulation abstracts away how sets are represented and how operations are executed.Source: §3 · p. 4
  • SISA instructions implement variants of set operations and provide iterators and C-style wrappers, with many instructions selecting a suitable variant on the fly.For example, the ISA supports both merge and galloping set intersection.Source: §3 · p. 4
  • SISA stores sets as dense bitvectors or sparse arrays, processing them with in-situ PIM or near-memory PIM, respectively.The largest neighborhoods are stored as bitvectors within a user-specified storage budget.Source: §3 · p. 4
  • The SISA Controller Unit schedules instructions to PIM and selects operation variants based on set representations and properties.It can be a hardware unit or be emulated by a process on a dedicated logic-layer core; merge-based intersection is favored for similarly sized sets.Source: §3 · p. 4
  • The controller uses set metadata containing logical-ID-to-address mappings, representation type, and cardinality to guide its decisions.A Set Metadata Buffer caches metadata.Source: §3 · p. 4

4 SETS FOR SIMPLE & PROVABLY FAST GRAPH MINING

The section compares graph-processing paradigms on selected mining and low-complexity problems. Its analysis concludes that only the set-centric approach enables efficient mining algorithms for the considered problems.

4 SETS FOR SIMPLE & PROVABLY FAST GRAPH MINING

  • The set-centric approach supports many graph-mining problems and enables algorithms with competitive theoretical performance bounds.The paper identifies both breadth of support and competitive bounds as advantages over other programming paradigms.Source: §4 · p. 4
  • The comparison draws on selected problems from graph pattern matching and graph learning, alongside triangle counting, BFS, connected components, and PageRank.The paradigms considered include vertex-centric and edge-centric models, array maps, GraphBLAS, pattern-matching frameworks, GNNs, and database approaches.Source: §4 · pp. 4–5
  • Only the set-centric approach enables efficient graph-mining algorithms for the considered problems; other paradigms either do not focus on them, cover only some, or lack formal guarantees.The comparison includes selected pattern-matching, learning, and low-complexity problems.Source: §4 · p. 5

5 SET-CENTRIC GRAPH ALGORITHMS

The section formulates graph pattern-matching problems around sets and set operations, then shows how these operations appear across clique, isomorphism, and frequent-subgraph algorithms.

5 SET-CENTRIC GRAPH ALGORITHMS

  • The set-centric formulations cover graph pattern matching, including triangle counting, clique problems, subgraph isomorphism, and frequent subgraph mining.The section also considers graph learning separately and discusses set representations and parallelization later.Source: §5 · p. 5, §5.1 · p. 6

5.1.1 Triangle Counting.

  • Triangle counting computes neighborhood intersections, an operation that can account for up to ≈94% of its runtime.The formulation sums intersection cardinalities across vertices and their neighbors.Source: §5.1.1 · p. 6

5.1.2 Maximal Cliques Listing.

  • Bron–Kerbosch uses dynamic vertex sets and operations including intersections, unions, and differences to list maximal cliques.Pivoting and degeneracy optimizations add set operations while pruning candidate vertices.Source: §5.1.2 · p. 6
  • The set-centric k-clique listing reformulation preserves the original algorithm’s time complexity and uses intersection and cardinality operations.Its recursive search extends cliques by vertices later in degeneracy order; the k=4 specialization needs no recursion.Source: §5.1.2 · pp. 6–7

5.1.6 Subgraph Isomorphism.

  • In VF2 subgraph isomorphism, neighborhood intersection identifies already-matched neighbors whose edge labels must be checked.The formulation verifies structural compatibility and label matching separately.Source: §5.1.6 · p. 7

5.1.7 Frequent Subgraph Mining.

  • Frequent subgraph mining generates candidates iteratively, counts them with subgraph isomorphism, and retains those meeting the support threshold.Candidate generation also benefits from set union; candidate trees may use dense bitvectors or sparse arrays.Source: §5.1.7 · pp. 7–8

5.2 Graph Learning

The graph-learning examples express vertex similarity, link-prediction evaluation, and clustering using set operations, especially intersection and union.

5.2.1 Vertex Similarity.

  • Vertex-similarity measures rely on intersection and union cardinalities and can serve alone or as building blocks for clustering.The examples include Jaccard, Adamic–Adar, and Resource Allocation measures.Source: §5.2.1 · p. 8

5.2.2 Link Prediction.

  • Link-prediction evaluation removes random links, scores candidate edges, and measures effectiveness by intersecting predicted edges with the removed links.The prediction scheme scores edges absent from the remaining sparse graph.Source: §5.2.2 · p. 8

5.2.3 Clustering.

  • Jarvis-Patrick clustering uses similarity between two vertices’ neighborhoods to decide whether they belong to the same cluster.Its set-centric formulation relies heavily on set intersection.Source: §5.2.3 · pp. 8–9

5.3 “Low-Complexity” Algorithms

The section distinguishes algorithms with opportunities for set-centric acceleration from low-complexity algorithms that offer few such opportunities.

5.3 “Low-Complexity” Algorithms

  • SISA does not target low-complexity algorithms because they offer few opportunities for set-centric acceleration.PageRank’s nested rank-update loops are given as an example; the analysis also considers several shortest-path, traversal, and graph-structure algorithms.Source: §5.3 · p. 9
  • The work supports problems beyond simple pattern matching, including vertex similarity, clustering, link prediction, and Bron–Kerbosch.This is presented as broader coverage than other pattern-matching accelerators or frameworks.Source: §5.3 · p. 9
  • A set-centric BFS formulation represents unvisited vertices with a dense bitvector Π requiring n bits, which helps abstract away some branches.Source: §5.3 · p. 9

5.4 Deriving a Set-Centric Formulation

The section’s formulation approach associates data structures with sets and replaces explicit checks with set operations.

5.4 Deriving a Set-Centric Formulation

  • The key change in the 4-clique formulation is to use set intersections instead of explicitly verifying whether vertices form cliques.Table 4 presents a traditional snippet, a set-centric formulation, and its SISA snippet; all use directed edges to avoid counting a clique twice.Source: §5.4 · p. 9, Table 4 · p. 9

6 SISA: DESIGN, SYNTAX, SEMANTICS

SISA exposes sets and set operations as first-class programming constructs, with representations and operation variants chosen to balance performance and storage. Its instructions, wrappers, metadata, and encoding connect these set-centric programs to hardware execution.

6.1 Representation of Sets

  • SISA represents static sorted vertex neighborhoods as sparse arrays or dense bitvectors, while dynamic auxiliary sets are usually small in number and total O(n).The user can control representation; neighborhoods may be stored as bitvectors when they meet a size threshold and fit within the storage budget.Source: §6.1 · p. 10

6.2 High-Performance Set Operations

  • Intersection is a key operation across the considered graph algorithms, with merge, galloping, and representation-specific variants for different set pairings.Merge suits similarly sized sorted arrays; galloping suits a much smaller sorted array, while bitvector intersection uses bitwise AND.Source: §6.2 · p. 10
  • SISA also supports union, difference, membership, cardinality, and adding or removing elements, with constant-time DB updates and size tracking.For sorted arrays, membership uses binary search; cardinality instructions can avoid creating intermediate result structures.Source: §6.2 · p. 10, §6.2.4 · p. 11

6.3.1 Labeled Graphs.

  • For labeled graphs, labels can use sparse arrays or one-hot bitvectors, matching the respective SISA-PNM or SISA-PUM execution path.Sparse arrays are proposed as the baseline label representation.Source: §6.3.1 · p. 11

6.3.2 SISA Instructions.

  • SISA instructions package set-operation variants, including automatic merge-or-galloping selection, and provide set creation and deletion.Table 5 enumerates instruction variants and indicates whether inputs are assumed sorted.Source: §6.3.2 · p. 11, Table 5 · p. 11

6.3.3 Programming Interface (Set Iterators & Wrappers).

  • A thin C++ layer exposes an opaque Set type with iterators and wrappers that map function calls to SISA instructions.Wrapper parameters determine the instruction variant.Source: §6.3.3 · pp. 11–12

6.3.4 Set Identification.

  • SISA assigns sets unique logical IDs that hardware maps to physical addresses, and its RISC-V custom encoding identifies instructions and input/output set registers.The custom opcode and functionality bits encode instructions; fewer than 20 instruction codes are used, leaving room for variants.Source: §6.3.4 · p. 12, §6.3.5 · p. 12, Figure 5 · p. 12

7 THEORETICAL ANALYSIS

SISA set-centric variants can match the competitive time complexities of tuned graph-mining algorithms, but the best operation variant depends on the problem. The analysis parameterizes bounds by graph degeneracy and compares merge and galloping approaches.

7.1 Parametrization with Degeneracy

  • The analysis parameterizes graph-mining complexities by degeneracy c, the smallest bound such that every subgraph has a vertex of degree at most c.Degeneracy is no greater than maximum degree d and can be substantially smaller, as in a star graph.Source: §7.1 · p. 12

7.2 Derivations of Bounds

  • For triangle counting and k-clique listing, merge and galloping yield different bounds, with galloping adding a log-c factor for k-clique listing.The derivations use intersections of endpoint out-neighbor sets; triangle counting iterates over edges.Source: §7.2 · p. 12
  • The k-clique-star listing analysis bounds the number of (k+1)-vertex cliques by O(m(c/2)^(k-1)) and accounts for O(k^2) work per clique.The cited listing algorithm runs in O(km(c/2)^(k-1)) time.Source: §7.2 · p. 12
  • For Jarvis-Patrick clustering and link prediction, the analysis distinguishes bounds based on maximum degree d from galloping's logarithmic dependence on d.The passage states merge costs O(md) for Jarvis-Patrick and says similar discussions apply to link prediction.Source: §7.2 · p. 12
  • For maximal-clique listing, merging can incur a factor-d overhead, while dense-bitvector X and P sets with efficient pivot selection match the original formulation's runtime.The cited bounds are O(cn3c/3) with good pivoting and degeneracy ordering, and O(3n/3) with appropriate pivoting without that ordering.Source: §7.2 · pp. 12–13

7 THEORETICAL ANALYSIS

  • Appropriate set-operation variants let set-centric algorithms approach or match fast problem-specific runtimes; no single variant is best for every problem.The analysis reports that all set-centric variants match the competitive time complexities of the considered tuned algorithms.Source: §7 · p. 12, §7.2 · p. 13

8 HARDWARE IMPLEMENTATION

SISA maps bitvector operations to in-situ DRAM processing and sparse-array operations to near-memory cores. A control unit selects execution and operation variants using metadata and performance models.

8.1 Processing-In-Memory for Sets

  • Dense-bitvector intersection, union, and difference use in-situ DRAM bulk bitwise operations, while sparse-array operations use near-memory processing cores.The implementation uses Ambit as the in-situ example; AND and OR implement intersection and union, and difference uses intersection with a negated operand.Source: §8.1 · p. 13

8.2 SCU & Automatizing SISA Decisions

  • The SCU selects PUM or PNM execution based on set representations, then chooses merge or galloping using performance models.The SCU performs variant selection rather than complex set modifications.Source: §8.2 · p. 13

8.3 Performance Models for Set Operations

  • Performance models compare streaming and random-access costs using set sizes, representation types, DRAM and core bandwidths, and DRAM latency.Metadata supplies set sizes and representations, while the execution environment supplies bandwidth and latency parameters.Source: §8.3 · p. 13

8.4 Details of SISA Hardware

  • Set metadata stores each set's representation and size, has O(n) total size, and can fit in cache or scratchpad for the described graph sizes.An uncached metadata lookup adds one memory access per set operation; metadata also informs variant selection.Source: §8.4 · p. 14
  • SISA parallelizes operations across bits, DRAM subarrays or banks, and vaults, while developers manage concurrent access with established synchronization techniques.SISA-PUM and SISA-PNM can be used together; the design relies on cache-coherence mechanisms for in-situ processing.Source: §8.4 · p. 14
  • Advanced layouts that spread sets across vaults are outside scope, and the design ensures each maximum-size neighborhood fits in one vault.The described hardware uses straightforward SCU decisions and simple instruction implementations that can run on in-order logic-layer cores.Source: §8.4 · p. 14, §8.5 · p. 14

8.5 SISA Hardware Cost and Feasibility

  • The paper outlines integration with RocketChip through custom SISA instructions forwarded over the existing RoCC interface to the SMU.The SMU signals the core to resume once an operation completes.Source: §8.5 · p. 14

9 EVALUATION

The evaluation compares SISA with hand-tuned graph-mining algorithms and other programming paradigms, using cycle-accurate simulations across varied graphs and problems. SISA is usually faster, with results shaped by graph structure, thread count, set representation, and load balancing.

9.1 Methodology, Setup, Parameters

  • The evaluation uses cycle-accurate Sniper simulations, varied graph datasets, and time cutoffs for computationally hard runs; for some small-maximum-degree graphs, dense bitvector overhead can reduce speedups or cause slowdowns.The study uses 32 cores for Figure 6 and 8 cores for large-graph runs; reducing the dense-bitvector share can mitigate the noted limitation.Source: §9.1 · pp. 14–15, Figure 8 · p. 17, §9.2 · p. 18

9.2 Discussion of Results

  • SISA is almost always at least 2× faster than hand-tuned parallel baselines and often more than 10× faster than non-set schemes.The comparisons use full parallelism and baselines that also benefit from high-bandwidth storage.Source: §9.2 · p. 16, Figure 6 · p. 16
  • Set-centric reformulation particularly helps complex algorithms such as maximal-clique listing, while SISA’s additional architectural gains depend more on graph structure.SISA is only marginally faster than set-based variants when graph structure favors sparse arrays over bitvectors; clustering’s tuned non-set baseline can outperform its set-based variant.Source: §9.2 · p. 16
  • SISA maintains speedups as thread counts vary, but its advantage is less distinctive with few threads; labeled subgraph-isomorphism graphs are often faster to process because labels prune recursive calls.The scaling analysis considers strong and weak scaling on Kronecker graphs.Source: §9.2 · p. 16
  • On large graphs, including Orkut with 117M edges, SISA’s runtime benefits resemble those on smaller graphs, except that sc-pwtk and soc-orkut are comparable to non-SISA set baselines.Those two networks lack the large cliques or dense clusters found in graphs such as genome networks.Source: §9.2 · p. 16
  • SISA is 10–100× faster than Peregrine and more than 100× faster than RStream, though Peregrine’s non-native maximal-clique support widens that gap.The compared paradigms prioritize programmability, whereas SISA starts from tuned graph algorithms and restructures them with set-centric operations.Source: §9.2 · p. 17
  • A 0.4 bias toward dense-bitvector neighborhoods works well for most graphs; using only PNM or only PUM gives the slowest runtimes.PUM suits large neighborhoods but adds overhead for sparse sets; the galloping threshold changes performance without changing the general pattern.Source: §9.2 · p. 17, Figure 7 · p. 17
  • SISA’s performance models adaptively select set-operation variants, and fast PUM processing of very large set pairs helps alleviate load imbalance.The evaluation also compares thread stall fractions and checks that partial simulations retain large sets, a primary source of imbalance.Source: §9.2 · pp. 17–18, Figure 9 · p. 18

10 RELATED WORK

Prior work uses sets in graph algorithms and accelerates selected set operations, but SISA instead makes set operations the primary building blocks for broad graph mining. Related work also distinguishes SISA from set-programming tools and pattern-matching-focused systems.

Hardware Accelerators

  • SISA is the only compared accelerator identified as supporting a broad family of graph-mining problems, while the closest designs focus on selected pattern-matching problems.The comparison covers supported graph-mining problems and architecture elements.Source: §10 · p. 18, Table 8 · p. 19

Scope and Future Directions

  • Dynamic graph analytics is outside this work's scope, while external-memory designs could serve as future backends for SISA set instructions.Other possible extensions include distributed execution, heterogeneous architectures, and graph compression or summarization.Source: §10 · p. 18

Graph Algorithms and Set Algebra

  • SISA is the first design to use set operations as primary building blocks for broad graph mining and accelerate them with in-situ and near-memory hardware.Earlier graph-processing work accelerated set intersections, while SISA identifies and reformulates multiple set operations used across mining algorithms.Source: §10 · p. 18

Set Programming

  • General set-programming efforts such as SETL, ISETL, and CLAIRE target coding productivity and prototyping, not graph processing or performance.Sets also appear in graph algorithms to simplify operations on selected data structures.Source: §10 · p. 18

SISA vs. AutoMine

  • SISA's set formulations support all set operations, whole algorithms, and broad graph mining, unlike AutoMine's focus on pattern-generation schedules.The authors describe AutoMine's compilation of set schedules as orthogonal and potentially combinable with SISA.Source: §10 · pp. 18, 20

PIM Acceleration

  • PUM and PNM capabilities work synergistically in SISA and produce significantly better results together than separately.Source: §10 · p. 20

11 DISCUSSION AND CONCLUSION

The paper presents a set-centric paradigm, SISA instructions, and PIM acceleration as a cross-layer design for graph mining. It also identifies compiler support and other execution backends as possible extensions.

11 DISCUSSION AND CONCLUSION

  • The paper's set-centric paradigm exposes set operations in graph-mining algorithms, yielding succinct formulations and competitive time complexities.It supports labeled graphs and non anti-monotonic set operations.Source: §11 · p. 20
  • SISA maps set-centric algorithms to a small, expressive instruction family, with in-situ and logic-layer PIM variants selected to maximize speedups over hand-tuned baselines.The set-algebra interface could also use GPU, FPGA, cache, or ReRAM backends.Source: §11 · p. 20
  • Compiler support could generate SISA programs from set-centric formulations, potentially using AutoMine-generated schedules as input.Source: §11 · p. 20

Related papers

Loading 2104.07582v2…