SISA: Set-Centric Instruction Set Architecturefor Graph Mining on Processing-in-Memory Systems
Maciej Besta1 , Raghavendra Kanakagiri2 , Grzegorz Kwasniewski1 , Rachata Ausavarungnirun3 ,Jakub Beránek4 , Konstantinos Kanellopoulos1 , Kacper Janda5 , Zur Vonarburg-Shmaria1 , Lukas
Gianinazzi1 , Ioana Stefan1 , Juan Gómez-Luna1 , Marcin Copik1 , Lukas Kapp-Schwoerer1 , Salvatore
Di Girolamo1 , Nils Blach1 , Marek Konieczny5 , Onur Mutlu1 , Torsten Hoefler1
1 ETH Zurich, Switzerland

Thailand2 IIT Tirupati, India

3 King Mongkut’s University of Technology North Bangkok,

4 Technical University of Ostrava, Czech Republic

5 AGH-UST, Poland

ABSTRACTKEYWORDS

Simple graph algorithms such as PageRank have been the target ofnumerous hardware accelerators. Yet, there also exist much more
complex graph mining algorithms for problems such as clusteringor maximal clique listing. These algorithms are memory-boundand 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 withcarefully designed set-centric ISA extensions called SISA, and (3)use PIM to accelerate SISA instructions. The key design idea is toalleviate 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 10× speedup over theestablished Bron-Kerbosch algorithm for listing maximal cliques.
We deliver more than 10 SISA set-centric algorithm formulations,
illustrating SISA’s wide applicability.

Graph Mining, Graph Pattern Matching, Graph Learning, Clique
Mining, Clique Listing, Clique Enumeration, Subgraph Isomorphism, Parallel Graph Algorithms, Processing In Memory, Processing Near Memory, Graph Accelerators, Instruction Set Architecture

CCS CONCEPTS• Hardware → Emerging architectures; Memory and dense storage; Application-specific VLSI designs; Application specific instruction set processors; • Computer systems organization → Architectures; • Theory of computation → Design and analysisof algorithms; Graph algorithms analysis; Data structures design
and analysis; Parallel algorithms; • Mathematics of computing→ Graph algorithms; • Information systems → Data mining;
Clustering; • Computing methodologies → Parallel computing methodologies.
Publication rights licensed to ACM. ACM acknowledges that this contribution was
authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or
reproduce this article, or to allow others to do so, for Government purposes only.
MICRO ’21, October 18–22, 2021, Virtual Event, Greece© 2021 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-8557-2/21/10. . . $15.00
https://doi.org/10.1145/3466752.3480133

282

ACM Reference Format:
Maciej Besta1 , Raghavendra Kanakagiri2 , Grzegorz Kwasniewski1 , Rachata
Ausavarungnirun3 , Jakub Beránek4 , Konstantinos Kanellopoulos1 , Kacper
Janda5 , Zur Vonarburg-Shmaria1 , Lukas Gianinazzi1 , Ioana Stefan1 , Juan
Gómez-Luna1 , Marcin Copik1 , Lukas Kapp-Schwoerer1 , Salvatore Di
Girolamo1 , Nils Blach1 , Marek Konieczny5 , Onur Mutlu1 , Torsten Hoefler1 .
2021. SISA: Set-Centric Instruction Set Architecture for Graph Mining on
Processing-in-Memory Systems. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO ’21), October 18–22,
2021, Virtual Event, Greece. ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/3466752.3480133

1

INTRODUCTION

Research on graph analytics in computer architecture has mostly
targeted graph algorithms based on vertex-centric formulations [6,7, 12, 22, 65, 88, 113, 120, 142, 177, 183]. Some works also focus
on edge-centric or linear algebra paradigms [90, 134, 149, 151].
Such algorithms have complexities described by low-degree polynomials [91], e.g., O(n + m) for Breadth-First Search (BFS) [42] andO(m · #iterations) for iteration-based PageRank (PR) [21], where nand m are numbers of vertices and edges, respectively.
Yet, there are numerous important problems and algorithms
in the area of graph mining [23, 39, 84, 137, 156] that received
little or no attention in computer architecture. One large classis graph pattern matching [84], which focuses on finding certain specific subgraphs (also called motifs or graphlets). Examples
of such problems are k-clique listing [44, 58], maximal clique listing [26, 29, 51, 158], k-star-clique mining [79], and many others [39].
Another class is broadly referred to as graph learning [39], withproblems such as unsupervised learning or clustering [81], link
prediction [8, 102, 105, 155], or vertex similarity [98]. All these problems are used in social sciences [51], bioinformatics [51], computational chemistry [153], medicine [153], cybersecurity [49], healthcare [157], web graph analysis [85], and many others [30, 39, 74, 84].
These problems often run in time at least quadratic in the numberof vertices, and many problems are NP-complete [26, 39, 44, 159].
Thus, they often differ significantly in their performance properties
from “low-complexity” problems such as BFS or PageRank.

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

●
Increasing
countsof stalled
IncreasingCPU
countsof cycles
stalledIncreasing
CPU ofcyclescountsstalledCPU cycles

2

●

●
●

6

●

●
●

32 32
3

4

2

1

●

●

●
●

8

●
●

16

●
●

8

●

32

●

●

16 16
1

of speedups
FlatteningofFlattening
speedups● of speedups
●
●

●

●
●
●

4

social−Pok
int−authorshipsocial−Flx
int−citationssocial−Poksocial−Flxsocial−Pok
Flattening●

Legend:0.5 Legend:on the left
0.5
on the left
Legend:0.50.40.4 on the left
0.40.30.3●
0.30.2 ●●0.2●●
0.20.1
●
0.1
0.1
2

●

●

1

Input graph
Inputint−authorshipgraph
int−citations
int−authorship
Input
graph
social−Flx
int−citations

Runtime[s] [s]
Runtime
Runtime [s]

50
50
50 40
40
40 30
30
30 20
20
20 10
10 ●
10 0●
0
0

StalledCPU
cycles[ratio]StalledCPU
cycles[ratio]Stalled CPU cycles [ratio]

Importantly,
the accessestablishedvertex-centric
originallyprovertex
canonly
only
accessthetheneighbors
neighborsofof𝑣.model,
𝑣.WhileWhilethissuffices
sufficesvertex𝑣 𝑣canthis
posed
in the Pregel
graph
processing
system[108],
doesrequires
not efforalgorithms
algorithms
such
PageRank,
graphminingoften
requiresforsuch
asasPageRank,
graphminingoften
fectively
express
graph
problems.
It [39].
exposes
only thelonon-local
knowledge
thegraphgraph
structure[39].Obtaining
Obtaining
such
non-local
knowledge
ofofmining
thestructure
such
cal
graph
structure:A
threadexecutingavertexkernelfor
anyknowledge
inthevertex-centricparadigm
ishardorinfeasible,
knowledge in the vertex-centric paradigm is hard or infeasible,
vertexv can
onlyaccesstheneighborsof v.
While thissuffices
noted
Kalavri[88](“(...)graph
graph
algorithms,
liketrianasas
noted
bybyKalavri
etetal.al.
[88](“(...)
algorithms,
liketrianforgle
algorithms
such
PageRank,
graphmining often
requirescounting,arearenotaasagood
goodfitfitfor
forthethevertex-centricvertex-centricmodel”)
andgle
counting,
notmodel”)
andnon-local
knowledge
of136,
thegraph
structure[39]. Obtaining
such
many
others[93,103,103,136,
172].
Similararguments
applytotoother
other
many
others[93,
172].
Similararguments
apply
knowledge
insuchthevertex-centricparadigm
istotohard
or infeasible,
paradigms
GraphBLAS[90,[90,134]andandframeworks
suchparadigms
suchasas
GraphBLAS
134]
frameworks
such
as
Ligra
[145].
They
donot
supportmany
graph
miningproblems,
as
noted
by
Kalavrietal.
[88](“(...)
graph
algorithms,
liketrianas Ligra [145]. They do not support many graph mining problems,
discuss
Table
andSection4.
gleandcounting,
areininnota goodfitSection
forthe4.vertex-centricmodel”) andandwewe
discussTable
1 1andSeveralgraph
miningsoftwareframeworks(Peregrine
[80]
and
many
others
[93,
103,
136,
172].
Similararguments
apply [80]tootherSeveral graph mining software frameworks(Peregrine
andothers
[33,
35,
48,
78,
86,
111,
112,
156,
171,
173,
179])
were
proposed.
paradigms
suchasGraphBLAS
[90,
134]
and
to
frameworks
suchothers [33, 35, 48, 78, 86, 111, 112, 156, 171, 173, 179]) were proposed.
theydo(1)notfocus
exclusively
on onlya few problems,
graph patasUnfortunately,
Ligra [145]. They
supportmanyongraph
Unfortunately,
they (1)focus
exclusively
onlymining
a few graphpatternmatching
and Section(2) usually do not provide theoreticalandwediscussproblems,
inproblems,
Table 1andand
ternmatching(2) usually4. do not provide theoreticalguarantees
on mining
total work
[24] (unlike
parallel graph algorithms
Several graphsoftwareframeworks[80] andguarantees
on totalwork[24] (unlike
parallel(Peregrine
graph algorithms
for specificminingproblems).
Overall,there
is a needfora graphothers
[33,
35,
48,
78,
86,
111,
112,
156,
171,
173,
179])
were
proposed.
for specific mining problems). Overall, there is a need for a graphmining paradigm
that
would
(1) enableonexpressing
many
graph
Unfortunately,
they
(1)
focus
exclusively
only
a
few
graph
patmining paradigm that would (1) enable expressing many graphminingproblems,and (2)
offer
competitive
theoreticalwork guartern
matching
problems,
and(2)
usuallydonotprovidetheoreticalmining problems, and (2) offer competitive theoretical work guarantees [24].
guarantees
antees[24]. on total work [24] (unlike parallel graph algorithms
Moreover,pastproblems).
works illustrated
that graphalgorithms
forMoreover,
specificminingOverall,is miningaminingneed fora graphpast works
illustrated
thatthere
graphalgorithms
arememory
bound
[37,
50,
80,
175,
178].
This
is
becausethesealgomining
paradigm
that
would
(1)
enableexpressing
many
are memory bound [37, 50, 80, 175, 178]. This is because thesegraphalgorithmsproblems,
generate andheavilyuselarge intermediate
structures,but,mining
and
(2)
offer
competitive
theoretical
work
guarrithms
generateand heavily
useaslarge
intermediate
structures,but,similarly
to algorithms
such
PageRank,
they arenot computeantees[24].
similarly
to[51,
algorithms
as PageRank,
they arenotwe
computeintensive
80,works176]. suchWe
show
thisthatin FigureWhenincrease
Moreover,past
illustrated
graph1:1:
miningalgorithms
intensive
[51,
80,
176].
We
show
this
in
FigureWhen
weincreasethenumberofparallelthreads,
runtimedecrease
flattensout andare memorybound[37, threads,
50, 80, 175,178]. Thisis because
these
the
numberparallelruntimedecrease
flattens
outalgoandstalled
CPUofcycle
countincreases.
This
motivates
using
processingrithms
generateandheavilyuse
large
intermediate
structures,but,stalledCPU cycle
countincreases.
This motivatesusing processingin-memory(PIM)
toobtainthemuchneededspeedups
ingraph
similarlytoalgorithms
suchas
PageRank,
they
are
not
computein-memory(PIM)PIM
to obtain
theonlymuchneededsolution
speedups
ingraphmining.[51,
While
isWe
notshowthepotentialforhardwareintensive80,
176].
thispotential
in Figuresolution
1: Whenfor
wehardware
increasemining.
While
PIM
is
not
the
only
of graphthreads,
mining,runtime
we select
PIM because
it (1)andreptheacceleration
number of parallel
decrease
flattens
acceleration
mining,we select
PIM
it out(1) represents oneofofgraphthe most
promisingtrendsto because
tackle thememorystalled
CPU
cycle
count
increases.
This
motivates
using
processingresents
one ofmost
promising trends
tacklethe memory
bottleneck[56,the117]
outperforming
variousto
otherapproaches[141],
in-memory[56,(PIM)
tooutperforming
obtain the muchneededspeedups
in graphbottleneck
117]
variousotherapproaches(2) offers well-understood designs [118], and (3) brings very[141],
large
mining.
PIM is not the only potential
solution
forvery
hardware(2)
offersWhile
well-understood[118],
andlarge
speedups
in simple graphdesigns
algorithms
such
as (3)
BFSbrings
or PageRank(seeaccelerationof graphmining,we select as
PIM because
it (1) repspeedups
in simple
graphalgorithms
or PageRank
more than
15 works
in Table7). Yet,suchgraph BFS
miningalgorithms(seeareresents
one15ofworks
the mostTable
promisingto tackle
the memory
more
than
7). Yet, trends
graphminingalgorithms
are
much
more
complexinthan
PageRank,
BFS, andsimilar:they employ
bottleneck[56,117] thanoutperforming
variousotherapproaches[141],
muchcomplex
PageRank,
BFS, andsimilar:theywith
employdeepmorerecursion,
create many
intermediatedata
structuresnon(2)
offerswell-understooddesigns[118],
and(3)
brings
very
large
deep
recursion,
create many intermediate
trivialinter-dependencies,
and have highdata
loadstructures
imbalancewith[51,non171].
speedups
in simple graph algorithms
such load
as BFSor PageRank(seetrivialinter-dependencies,
have highimbalance[51, graph
171].
As we
show in Section 10,and
no existing
HW design
targets broad
more
15
in10,
Table
7). Yet, HW
graph
miningalgorithms
areAs
wethanshow
inworks
Sectionnoexisting
designgraph
mining(i.e.,
bothgraph
patternmatching
andtargets
graph broad
learning),
or
much
more
complexthan
PageRank,
BFS,
andsimilar:theyemploymining(i.e.,
both
graph patternmatchingbroadand graphgraph mining.
learning), or
explores
PIM
techniques
for accelerating
deep To
recursion,
createintermediatedata
structures
withis nonexplores
PIM techniques
for accelerating
broad
graph
mining.
addressallthesemany
issues,we propose
a noveldesignthathightrivial
inter-dependencies,
and
have
high
load
imbalance
171].
To
addressalltheseissues,we
proposeanovel
designthatis highperformance (empirically and theoretically), applicable[51,
to
many
As
we show
in(empirically
Section
10, noexisting
HW
designapplicabletargets
graph
performanceandtheoretically),
to manygraphminingproblems,
andeasilyamenableto
PIM broadacceleration.
mining(i.e.,
bothgraph
patternmatching
andgraph
learning),orgraphminingproblems,
andparts
easilyto PIM
acceleration.
We first
observethat large
ofamenable
many graphminingalgorithms
explores
PIM
techniquesforaccelerating
broad
graph
mining.
beobserve
expressed
operations
as intersection
Wecan
first
thatwithlargesimple
parts setof many
graphsuchminingalgorithms
weset
proposea noveldesignthathigh∩Tobeoraddress
union all∪, thesewhere
sets containverticesoredges.
Thisisdrives
canexpressed
withissues,
simpleoperations
such
as intersection
performance(empiricallyandtheoretically),
applicabletomany
set-centric
programmingin edges.
which thedeveloper∩ ouror union∪, wheresets containparadigm,
vertices orThisdrivesour set-centric programming paradigm, in which the developer

8 8

4 4

2 2

1 1

32 32

●

16 16

●

8 8

4 4

2 2

1 1

●
Number of threads
Number of threads
Number of threads
Number of threads
Numberofof
threads
Numberofthreads
Figure 1: Runtimes and stalled CPU cycle count, for various numbers
parallel threads,

using
Bron-Kerboschalgorithm
for listing
cliquesin different
input
graphsFigure
1:theRuntimesand stalled
CPU cycle
count, maximal
for various
numbersof parallel
threads,
Figure1: Runtimes
andourstalledCPU forcycle
count,
for various
numbersof parallel(Section
9 describes
evaluation
methodology).
using
the
Bron-Kerboschalgorithm
listing
maximalcliquesin different
inputthreads,
graphsusing the9 Bron-Kerboschalgorithmmethodology).
for listing maximal cliques in different input graphs(Section
describes our evaluation(Section 9 describes our evaluation methodology).

283

Pattern M.
M. Learning
Learning “Low-c.”“Low-c.” Remarks
Abstractionoror
A? Pattern
Abstraction
A?
Remarks
programmingmodel
model
mckc
kcds
ds si
si vs
vs lp
lp cl
cl av
av tc
tc bf
bf cc
cc pr
programmingmcpr∗∗ High comm. costs
Vertex-centric(ver-c)(ver-c) é
é é
é é
éé
éé
éé
éé
éé
éé
é ∗∗
Vertex-centricHigh comm. costs
Edge-centric(edge-c)(edge-c) é
é é
é é
éé
éé
éé
éé
éé
éé
é ∗∗ ∗∗ ∗∗ ∗∗ High
Edge-centricHigh work
work andand depthdepth∗é∗ Only low-diameter decomp.
Array
maps
é
é
é
é
é
é
∗
∗
Array maps
é é é
é é é
é
Only low-diameter decomp.
∗ The
existing SI scheme∗ The only∗†
only existing SI scheme
GraphBLAS[90]
[90]
(L)é
é é
éé
é ∗é
éé
éé
éé
é
†
GraphBLAS(L)
only uses trees as patterns [34]uses trees as patterns [34]
†only
Neural message passing,are as powerful as the† GNNsNeural message passing, (L) é é é ††é é é
GNNs are as powerful as thegraph networks [13, 62] (L) é é éé é é
Weisfeiler-Lehman test [170].
graph networks [13, 62]
test [170].
∗ ∗ ∗ ∗ é é é é ∗ é é é ∗Weisfeiler-Lehman
Pattern matchingNobounds,performanceé∗ ∗ ∗ ∗ é é é é ∗ é é é ∗ No bounds, lowPattern matching
low performance
é
Joins [36](R) é ∗∗ ∗∗ é ∗∗ ∗∗ ∗∗ é ∗∗ é ∗∗ ∗∗ ∗∗ No bounds, low performance
Joins [36]
(R) é
é
é
é
No bounds, low performance
Set-Centric / SISA
(S)
é é é
Set-Centric / SISA
(S)
é é é
Table 1: Comparison of the set-centric programming approach and SISA to existing graphTable
1: Comparisonof the set-centric programming
approachandforSISA
to existingprocessing
abstractions/programming
models, focusing
on support
selected
graphgraphminprocessing
abstractions/programming
models,on support forgraphselected
graph mining problems(pattern matching, learning),
andfocusing
for “low-complexity”
problems.
A?:
ing
problems(patternmatching,
learning),
andfor“low-complexity”
graph
problems.
A?:
Underlying algebra? L: linear, R: relational, S: set. “ ”: Support / significant focus. “ ”: Partial
Underlying
algebra?
L:linear,R:
relational,
S:”:
Support/significant
focus.
”:
Partial“set.
“
support / some focus. “é”: no support / no focus. Pattern M.: selected graph pattern matching probsupport/ somefocus.clique“é”:
M.: selectedgraphpattern matchingprob“ ”: listing,no support
no focus.
Patternlems, mc:
maximalkc: 𝑘/-clique
listing,
ds: dense
subgraph,si: subgraphisomorphism,lems,
mc: maximal
kc:problems,𝑘k -clique listing,
ds: similarity,
dense subgraph,subgraph cl:
isomorphism,
Learning:
selectedcliquegraphlisting,learning
vs: vertex
lp: linksi:prediction,clustering
Learning:
selected
graph
learning
problems,
vs:vertexsimilarity,
lp:
link
prediction,cl:clusteringor community detection, av: accuracy verification (of link prediction outcomes), “Low-c.”: selectedorcommunity detection,
av:targeted
accuracybyverification(of oflink
prediction
outcomes),“low-complexity”
problems
vast majority
existing
works
on graph “Low-c.”:processing.selected
tc: tri“low-complexity”
problems
by vastmajority pr:of existing
works
graph processing.
tc: triangle counting, bf:
BFS, cc:targeted
connected
components,
PageRank.
Theonanalysis
in this tableisangle
counting,
bf: BFS,
connected
components,
pr: PageRank.
The analysis
in thistable isextendedin Section
10cc:
and
Table 7 bydetailing specific
HW acceleratorsfor graph
processing.
extended in Section 10 and Table 7 by detailing specific HW accelerators for graph processing.

graph mining problems, and easily amenable to PIM acceleration.
identifies
sets and setlarge
operations
in a givengraphalgorithm.
These
set opWe
first observe
parts ofminingalgorithms
identifies
sets andthat
set operationsin amany
given algorithm.
These
set operations
arethenmapped
to
a
small
and
simpleyetexpressive
group∩
can be expressedwith simple
set operations
suchintersection
erations
are then mapped
to a smalland simple
yet asexpressive
groupof
instructions,offeringarich
selectionofstorage/performanceor union∪, wheresets containor edges.
This drives our setof
instructions,offering
a richvertices
selectionof tostorage/performancetradeoffs.
These
instructionsareoffloaded
PIM
units.
We
callin whichtothe
developer
identicentric programming
paradigm,
tradeoffs.
These instructions
areform
offloaded
PIM
units.
We
call
these
instructions
SISA
as
they
“Set-centric”
ISA
extensions
fies sets
and set operations
in a form
given“Set-centric”
algorithm. Theseset operathese
instructions
SISA
as
they
ISA
extensions
that enable a simple interface between numerous graph mining algotions
are thenmappedto a smalland simple
yet expressive
group
of
that
enablesimpleinterface
betweennumerous
graphminingalgorithms
andaPIM
hardware.
Overall,ourcross-layer
designconsists
instructions,offering
a richOverall,selectionourof cross-layer
storage/performancetraderithms
andPIM
hardware.
designconsistsof three key elements: a new set-centric programming paradigm
offs.
These
offloaded
to PIM
units. We paradigm
call theseof
threekeyinstructions
elements:
a arenew
set-centric
programming
andformulationsof graphalgorithms(contribution#1), set-centric
instructions
SISA
as
they
form
“Set-centric”
ISA
extensions
that enandof graphalgorithms implemented(contribution set#1),operations,set-centric
ISAformulations
extensions with
its instructions,able extensions
a simple interface
betweennumerous
graph mining
algorithms
ISA
with
its
instructions,
implemented
set
operations,and set organization (contribution #2), and PIM acceleration (conand PIM
hardware. Overall,our cross-layer
consists of threeandset organization(contribution#2), anddesign
PIM acceleration(contribution#3).
key elements:a new set-centric programming paradigm and formutribution#3).
Overall, we advocate using set algebra as a basis for the design
lationsof graphalgorithms(contribution
ISAdesignextenwe advocate
using
setset-centric
algebra#1),
asparadigm
aset-centricbasis fortheofOverall,graph mining
algorithms.
Ouris thefirst tosions
withmining
its instructions,
implemented
set operations,andsetorgaofgraph
algorithms.
Our
set-centricparadigm
is
the
first
to
use set operations as fundamental general building blocks for both
nization(contribution#2), and PIMgeneral
acceleration(contribution
#3).
use
set
operations
asfundamentalbuilding
blocksforbothalgorithmic formulations and their execution. Using set algebra
Overall,
weadvocateusing
set
algebraassuccinct,a basisforthealgebra
designalgorithmic
formulations
andalgorithms
theirexecution.
Using
set
ensuresthat
SISA
set-centric
areapplicable
to
of
graph
miningalgorithms.
Our
set-centricparadigm
isthefirst totoensuresthat SISAand
set-centricalgorithms
are succinct, applicablemany problems,
theoreticallyefficient.
use Forsetproblems,
operations
asfundamental
generalbuilding
blocks
for
both
many
and
theoreticallyefficient.
the in-memory acceleration of SISA, we investigate whichalgorithmic
formulations
andwhichtheirofexecution.
Using
set algebra
For ofthePIM
in-memory
acceleration
SISA,
we investigate
which
types
are beneficial
for
set
operations.
We processsets
ensuresthat
SISA
set-centricalgorithms
are118],
succinct,applicable
to
types
ofas
PIM
are
beneficial
which
set[57,
operations.
processsets
storedbitvectors
usingforin-situPIM
as We
offeredin Ammany
problems,
andtheoreticallyefficient.
storedbitvectors[57,or118],
as offered in[53],Ambit [64,as141],
ELP2IMusing[168],in-situ
DRISAPIM[100],
ComputeDRAM
thein-memory
accelerationof SISA,
investigate
which
bit
[64,
141],
ELP2IM [168],
DRISA[100],or weComputeDRAM[53],
forForhighestperformanceandenergyefficiency(“SISA processtypesof PIMmemory”
are beneficial
for whichset
operations.
We process
sets
for
performanceandenergy(“SISA
processinghighest
using– SISA-PUM).
Inefficiency
contrast, whilesets
storedstoredas
bitvectors
using
in-situ
PIM
[57,
118],
as
offeredinAming
using arrays
memory”– SISA-PUM).
In contrast,
while
setstoday’s
storedas sparse
cannotbe simply processedin situwithbit[64, 141],
ELP2IM
DRISA[100], or ComputeDRAM[53],technology,
they
can [168],
usebethehigh throughput
latencyofassparsearrayscannotsimplyprocessed
inand
situlowwithtoday’sforhighest performanceandenergyprocessnear-memory
PIM
[57,
104,
118,
122]
asefficiency
offered andin(“SISA
the2Dlatency
UPMEM
technology,
they
can
use
the
high
throughput
low
of
ing
using memory”–104,
SISA-PUM).
In3D
contrast,
sets
storedarchitecture
[63,
logic
layer
DRAM
such
asUPMEM
Hybridnear-memory
PIM96][57,or118,122]ofasofferedinwhilethe 2Dassparse arrays
cannotbe simply
innearsitu
withMemoryCube(“SISA
processing
memory”–architecture[63,(HMC)
96] or[83]logiclayerprocessedof 3D DRAM
such
as today’s
Hybridtechnology,
they
can
use
the
high
throughput
andlow
latencyof–
SISA-PNM).
For
even
higherperformance,
weprovidea small
Memory Cube (HMC) [83] (“SISA processing near memory”
near-memory
[57,
104,
118,best
122]variant
as offeredthe
2D UPMEM
HW controllerPIM
that
selects
the
of we
ain
set
instruction
to
SISA-PNM).
For
even
higherperformance,
providea smallarchitecture[63,96]selects
or logic
3D DRAMas Hybrid
be executed
on-the-fly.
HW
controller
thatthelayer
best ofvariant
of a setsuch
instruction
toMemoryCube(HMC)show[83] that(“SISA
processing
near memory”
Overall,ourresultsgraph
mining algorithms,
although–beexecutedon-the-fly.
SISA-PNM).
evenshowhigherperformance,
wealgorithms,
providea small
HW
complexlacking
straightforward
parallelism,
greatly
benefitOverall,and
ourForresults
thatgraph mining
althoughcontroller
that
selects
the best
variant
of a set offered
instruction
toopbefrom PIM.
Our
key solution
is using
parallelism
by benefit
setcomplexandlacking
straightforward
parallelism,
greatly
executedon-the-fly.
erations
exposedwith theset-centric
approach.
Thisbysolutionfrom
PIM.andOur
key solution
is using
parallelism
offeredset opOverall,
ourresults show
that
graph
miningalgorithms,
harnesses
parallelism
at thelevelof bits,
DRAM
subarrays,
anderations
andexposedwiththeset-centric
approach.
Thisalthoughsolutioncomplexandlacking
parallelism,
greatly
benefitvaults. We
showthat straightforward
SISA-enhanced
theoreticallyharnesses
parallelism
at the level of algorithms
bits,
DRAMaresubarrays,
andfrom PIM.
solutionis using parallelism
by set opvaults.
We Ourshowkey
that
SISA-enhanced
algorithmsoffered
are theoreticallyerations and exposed with the set-centric approach. This solutionSISA: Set-Centric Instruction Set Architecturefor Graph Mining on Processing-in-Memory Systems

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

harnesses parallelism at the level of bits, DRAM subarrays, andvaults. We show that SISA-enhanced algorithms are theoreticallyefficient (contribution #4) and empirically outperform tuned parallel baselines (contribution #5), for example offering more than
10× speedup for many real-world graphs over the established BronKerbosch algorithm for listing maximal cliques [51]. Finally, forusability, we integrate SISA with the RISC-V ISA [166].

2

NOTATION AND BACKGROUND

Graphs We model an undirected graph G as a tuple (V , E); V
and E ⊆ V × V are sets of vertices and edges; |V | = n, |E| = m.
Vertices are modeled with integers (V = {1, ..., n}). N (v) denote theneighbors of v ∈ V ; d and d(v) denote G’s maximum degree and a
degree of v. In some cases, we consider labeled graphs G = (V , E, L);
L is a labeling function that maps a vertex or an edge to a label.
Set Representations SISA heavily uses sets. Consider a set ofk vertices S = {v 1 , ..., vk } ⊆ V (we focus on vertex sets, but SISA
also works with edges). One can represent S as a simple contiguous
sparse array (SA) with integers from S (“sparse” means that only
non-zero elements are explicitly stored). SA’s size is W |S | [bits]
where W is the memory word size (we assume that the maximum
vertex ID fits in one word). One can also represent S with a dense
bitvector (DB) of size n [bits]: the i-th set bit indicates that a vertexi ∈ S (“dense” means that all zero bits are explicitly stored).

3

OVERVIEW & CROSS-LAYER DESIGN

We now overview SISA’s cross-level design, see Figure 2.
(a) Set-Centric Formulations [Section 5 & 5.1] SISA relies
on set-centric formulations of algorithms in graph mining. Whilesome algorithms (e.g., Bron-Kerbosch [51]) by default use rich set
notation, many others, such as k-clique listing by Danisch et al. [44],do not. In such cases, we develop such formulations. Details onderiving set-centric formulations are in Section 5.1; the key common
step is to express two nested loops, commonly used to identify
connections between two sets of vertices, with a single intersectionof these sets.
A set can be represented in different ways, and a set operation canbe executed using different set algorithms. A set-centric formulation
Implementation(§5)(b.1) Set-centric ISA

for v in vertices:
for w in N(v):tc += |N(v)N(w)|
tc /= 3; cleanup( )sisa_set(...)
sisa_vertices(...)...
sisa_union(...)
sisa_intersect(...)
sisa_cardinality(...)
sisa_delete(...)(a) Set-centric algorithms & code/* "tc": /* Triangle Counting. */count oftc = 0; init_sets( )triangles *//* "N(v)":neighborsof v" *//* More than 10 otherset-centric formulations ofgraph mining algorithms */SISA instructions(§4, §6, §7)

Set organization, set representations,set algorithms, theoretical analysis

Memory subsystem, PIM acceleration
Metadataof SISA sets

Input graph

CPU
SISA
Controller
Unit (SCU)

Execution(c) SISA HW(§4, §9)(b.2) SISA sets(§4, §6, §7)

SISA structure:
Software abstractions& C-style wrappers

SCU picks mostbeneﬁcial variantsof set instructions
and accelerators

cache

Cache for set metadata

Programmable &succinct thanks to
set algebra generality

SISA-PUM (in-situ PIM,
e.g., bulk bitwise
operations with Ambit)

Expressive: one caneasily develop new
set-centric algorithms

Theoretically eﬃcient & fast:ability to choose set representations& operations ensure good bounds

SISA-PNM (near-memoryPIM, e.g.,
logic layers in 3D DRAM, or 2D UPMEM)
Extensible: one can add new
SISA instructions or use new formsof acceleration, such as ReRAM
or FPGAs (discussion in Sec. 11)

Figure 2: The overview of SISA with a summary of new introduced architecture and graphrepresentation elements (green) and advantages (brown).

284

hides these details, focusing on what a given graph algorithm does,
and not how it is done.
(b.1) Set-Centric ISA (Instructions) [Section 6] Our ISA extension implements set operations. These instructions support all
variants of operations, for example there is an instruction for bothmerge and galloping set intersection (details in Section 6). We also
provide a thin software layer: iterators over sets and C-style wrappers for SISA instructions. For programmability and performance,
many SISA instructions automatize selecting the best set operation
variant on-the-fly.
(b.2) Set-Centric ISA (Organization of Sets) [Section 6] We
represent sets as DBs or SAs. The former are processed by bulk
bitwise in-situ PIM, harnessing huge internal DRAM bandwidth(SISA-PUM). The latter use near-memory PIM, for example DRAM
cores in the UPMEM architecture, or logic layers in 3D stacked
DRAM, harnessing the large through-silicon via (TSV) bandwidth(SISA-PNM).
(c) HW Implementation Details [Section 8] For maximum
programmability and performance, we use hardware to automatically decide between SISA-PUM and SISA-PNM, or a set algorithm
variant (merge vs. galloping). For this, we use a dedicated unit called
the SISA Controller Unit (SCU).

4

GENERAL & FAST GRAPH MINING

The set-centric approach is superior to other graph programming
paradigms in that (1) it supports many graph mining problems and(2) it enables algorithms with competitive theoretical bounds on
performance (we discuss (2) in Section 7; this is often a key to low
runtimes [46, 91]). The analysis results for (1) are in Table 1.
To illustrate the above points, we first extensively examined therelated literature to identify representative graph mining problems and important graph processing paradigms [4, 9, 30, 52,
84, 97, 98, 102, 105, 126, 128, 130, 154, 163]. For the former, we pickfour problems from both graph pattern matching and graph learning areas (maximal clique listing [26], k-clique listing [38], dense
subgraph discovery [61, 97], subgraph isomorphism [159], vertex
similarity [98, 131], link prediction [8, 102, 105, 155], graph clustering [81, 137], verification of prediction accuracy [162]). For fairness,
we also consider four popular “low-complexity” problems, targetedby many past works (triangle counting, BFS, connected components,
and PageRank). For the latter, we first select vertex-centric [108]and edge-centric [134], two established graph processing paradigms
implemented in the Pregel and X-Stream systems. Second, we pickvertex/edge array maps from Ligra [145], an approach for developing graph algorithms based on transforming arrays of vertices oredges according to a specified map. Third, we consider GraphBLAS
and its linear algebraic approach [90], where graph algorithms are
expressed with linear algebra building blocks such as matrix-vector
products. Moreover, we consider pattern matching frameworks [52]that usually employ some form of exploring neighbors of each vertex, combined with user-specified filtering, to search for specified
graph patterns. For completeness, we also consider recent attempts
at solving graph problems with novel deep learning [15] paradigms
such as graph neural networks (GNN) [17, 167] and others [59],as well as joins and principles from relational databases and theassociated algebra [180].
The analysis results are in Table 1. Overall, no single paradigm,
except for the set-centric approach, enables efficient graph mining

MICRO ’21, October 18–22, 2021, Virtual Event, Greece
Problem

Problem

Algorithm

Algorithm

Besta et al.

𝑘-Clique-StarListing
Listing A
A k-clique-star𝑘-clique-star is
k-Clique-Star
is aa 𝑘-clique
k-cliquewith
withaddiaddi-

Used set operations

Used set operations

Maximal clique list. Bron-Kerbosch [51]𝐴 ∪ 𝐵, 𝐴 ∩ 𝐵, 𝐴 \ 𝐵tionaladjacentadjacentvertices
vertices thatthat areare connectedconnected toDanisch et al.[51][44] + [This work] 𝐴A∩∪𝐵 B , A ∩ B , A \ B
𝑘clique-clique list.
listing Bron-Kerboschtionalto allall thethe vertices
verticesinin
MaximalProblem
Algorithm
Used set operations
𝑘-Clique-Star
Listing relax
AListing
𝑘-clique-staris anature
𝑘-cliquewith
addicounting
[This
work]
𝐴A∩∩𝐵 B
, |𝐴Used∩ 𝐵 | set operations
Problem
Algorithm
theclique. 𝑘-Clique-Star𝑘-clique-stars
the restrictiveofcliques[79].with addiA
𝑘-clique-starisa𝑘-cliquek -clique 4-clique
listing
Danisch
et
al.
[44]
+
[This
work]
the clique.
k-clique-stars
relaxaretheconnected
restrictivetonatureofvertices
cliques[79].
Trianglecounting[well-known]
Maximalcliquelist. Bron-Kerbosch[51]
𝐴 ∪ |𝐴𝐵, ∩𝐴 𝐵∩| 𝐵 , 𝐴 \ 𝐵tionaladjacent
vertices
that
all
the
invertices in
Maximalcliquelist.
Bron-Kerbosch
[51]
𝐴
∪
𝐵
,
𝐴
∩
𝐵
,
𝐴
\
𝐵
4-cliquecounting
[This
work]
A
∩
B
,
|A
∩
B
|
Algorithm
2
shows
the
scheme.
We
first
find
𝑘-cliques.
Then,
for
𝑘 -clique-star
Jabboural. [79]
Danischet al.et[44]+ [This work] 𝐴 ∩𝐴𝐵∩ 𝐵 , 𝐴 ∪ 𝐵
𝑘 -cliquelisting listingtionaladjacent
verticesthatareconnected
to
all
the
Algorithm
2
shows
the
scheme.
We
first
find
k-cliques.
Then,
for
Danisch
et
al.
[44]
+
[This
work]
𝑘
-cliquelisting𝐴∩𝐵𝑘-clique-starlisting
[This
work]
𝐴
∩
𝐵
Trianglecounting[well-known]|A∩B|
4-clique counting[This work]𝐴 ∩ 𝐵 , |𝐴 ∩ 𝐵 |theclique.
𝑘-clique-stars
relax
the
restrictive
natureofcliques[79].
each
𝑘-clique,one
finds
additionalvertices
that
form
stars
with
Subgr.
isomorphism
[This
work]
𝐴
∩
𝐵
,
|𝐴
∩
𝐵
|
,
𝐴
∪
𝐵
,
𝐴
\
𝐵
4-clique counting∩ 𝐵B, |𝐴 ∩ 𝐵 |the clique.
𝑘-clique-stars
relax
the restrictive
naturecliques [79].
Triangle counting[well-known]|𝐴 ∩A𝐵 ∩| B, 𝐴k -clique-starlisting
Jabbour
et al.[This[79]work]Aeach k-clique,one thefinds
additionalverticesthat formstars ofwith
Trianglecounting[well-known]
|𝐴 ∪
∩ 𝐵|
Algorithm
2
shows
scheme.
We
first
find
𝑘-cliques.
Then,
for
𝑘 -clique-starlisting
Jabbour
et
al.
[79]
𝐴
∩
𝐵
,
𝐴
∪
𝐵
intersections
and a 2union.
Vertexlisting
similarity
Jaccardcoeff., others
131]
|𝐴
∪𝐵
𝐵,|𝐴 ∪ 𝐵
k -clique-star
[This
work]
A ∩∩𝐵B| , |𝐴
Algorithmshows the scheme. We first find 𝑘-cliques. Then, for𝑘listing-clique-starlisting
et al.[19,[79]𝐴∩
𝑘 -clique-star[Thiswork]Jabbour
𝐴 ∩ |𝐴
𝐵
intersections
andaunion.
Clustering
Jarvis-Patrick
[81]
∩
𝐵
|
,
|𝐴
∪
𝐵
|
𝑘 -clique-starlisting[This work]𝐴
𝐵 | 𝐵| ,, 𝐴each 𝑘-clique,finds one
additionalvertices thatform thatstarsform
with stars with
Subgr.
isomorphism
[This
work]
A, ∩∩
|A
A \∪𝐵B , A \ B
Subgr.
isomorphism[Thiswork]coeff.,
𝐴 ∩ |𝐴𝐵|𝐴𝐵B∩| ,, 𝐵
| ,∩
Link
prediction(LP)
Jaccardothers|𝐴∪𝐴∩𝐵∪,B
each one𝑘-clique,finds additionalvertices
Subgr. isomorphism[Thiswork][131]|𝐴 ∩ 𝐵 | , 𝐴 ∪ 𝐵 , 𝐴 \ 𝐵
LP accuracy testingWang
et al.others[162] [19, 131]
𝐴|A
\|𝐵
, |𝐴
𝐵| |𝐵∪
Vertexsimilarity
Jaccardcoeff.,
∩|𝐴
B∪𝐴
|∩,𝐵∩
|A
B|
1 /* Input: Aandgrapha 𝐺. Output: All 𝑘 -clique-stars, 𝑆 .*/intersections
union.
Vertexsimilarity
Jaccardcoeff.,
others
[19,
131]
|𝐴
∩
𝐵
,
Approx. degeneracy
Besta et al.[81][16]
𝐴|Aa union.
131]∩
2 𝐶 = /*intersectionsFirst , find 𝑘and- cliques(e. g., with Table 3) */Clustering
Jarvis-Patrick,𝐵|A∪| ,B|𝐴| ∪ 𝐵 |Clustering Vertex similarity
Jarvis-PatrickJaccard[81] coeff., others [19,
|𝐴 ∩
𝐵\|𝐵
,∩|𝐴B∪||𝐴| 𝐵
Clustering[81] In∩| ,B|𝐴| ∪ 𝐵|
Link
prediction(LP)Jaccard
coeff.,Jarvis-Patrickothers[131]|𝐴maximal∩|A
𝐵 | ,∩|𝐴B∪| 𝐵
3 𝑆 = ∅ // 𝑆 is a set with identified 𝑘 - clique - stars .
2: Overview
ofJaccard
set-centric
graphalgorithms.
cliquesubgraph
LinkTable
prediction(LP)
coeff.,
others
[131]
||𝐴
,𝐵|A
∪listing,
Link
prediction(LP)
Jaccardcoeff.,
others
[131]
|𝐴
∩
𝐵
|
,
|𝐴
∪
𝐵
|
LP
accuracy
testing
Wang
et
al.
[162]
𝐴
\
𝐵
,
|𝐴
∩
𝐵
|
4 foreach= (𝑉𝑐 ,𝐺𝐸.𝑐 )Output:∈ 𝐶 do :All//𝑘Foreach 𝑘 - clique
isomorphism,
and clustering,
also uses variants of union
where one set
1 /*Input: A 𝑐graph-clique-stars,
𝑆 .*/...
LP accuracy
testingWang
et al.
al.one[162]\andB , difference|A| ∩LP accuracy
testingWang[162]
𝐴 \∩𝐵 ,B|𝐴
𝐵|
Approx.
Besta
et
[16]
𝐴 \ 𝐵Atext
1 Ñ/* ,Input:
𝐺 . Output:
𝑘 -clique-stars,
isalwaysdegeneracy
a single-element
set (i.e.,
𝐴 ∪ et{𝑏al.
}, 𝐴\ {𝑏 }). Bolded
indicates algorithms with
2 𝐶5 = 𝑋/* = First
find A𝑘 -graphcliques( e . gall
. , AllwithTable3) */ 𝑢 𝑆∈.*/𝑁(𝑢)(e.g.,such that
𝑉𝑐
Approx.Besta
degeneracy
Besta et al. [16]𝐵
Approx.
degeneracy
et al. [16]A \ clique
B 𝐴 \listing,𝑢∈𝑉 𝑁 (𝑢) //,Intersectfind 𝑘 - cliques
withformulations
derivedin thiswork. In maximal
3 𝑆 = ∅ // 𝑆2 𝐶is = a𝑐 /*setFirst
with identified
𝑘 - clique- stars. Table 3) */Tableset-centric
2: Overview
of set-centric
graphalgorithms.
subgraph
3
𝑆
=
∅
//
𝑆
is
a
set
with
identified𝑘clique - stars .
∪𝑐𝑉, 𝑐𝐸𝑐 )//
the
star
6
𝐺𝑠 =𝑐 =𝑋(𝑉
Table
Overviewof graph
set-centric
graph ofalgorithms.
maximalcliquelisting,
subgraph
4 foreach∈ Derive
𝐶 do : //Foractualeach 𝑘𝑘 -- cliqueclique -...
isomorphism,
and2:ofclustering,one
also uses
variants
and Indifference
where
one
set
Table
2: Overview
set-centricalgorithms.
Inunionmaximalcliquelisting,
subgraph𝑐Add= (𝑉For each𝑘 - clique...
isomorphism,
andclustering,
variants
ofdifference
union algorithms
andwheredifference
where one set7
Ñ4 ∪foreach𝑐 , 𝐸identified𝑐 ) ∈ 𝐶 do : 𝑘//is always a single-element
setone(i.e.,𝐴 ∪ uses{𝑏 }one,𝐴\also{𝑏 }).uses
Boldedtext
withisomorphism,
and clustering,
also
variantsofunion
andindicatesone
set{𝐺𝑠𝑁}(𝑢)//Ñanclique// Intersect
all 𝑁 -(𝑢)such- starthat to𝑢 ∈𝑆 𝑉𝑐
5
𝑋 𝑆= = 𝑆𝑢∈𝑉𝑐 , removeis always a single-element
setwork.
}, 𝐴 \ {𝑏}). indicates
Bolded text
indicateswith
algorithms withformulations
derivedisset-centric
always a single-element
set (i.e.,inAthis∪ {b}(i.e.,, A\𝐴{b∪}).{𝑏Bolded
text
algorithms
8 // At the
duplicatesfrom 𝑆 all 𝑁 (𝑢) such that 𝑢 ∈ 𝑉𝑐
𝑁 (𝑢) // Intersect
5 end
𝑋 =
𝑢∈𝑉
𝑐
set-centric formulations
derived6
𝐺𝑠 = 𝑋 ∪ 𝑉𝑐 // Derive the actual 𝑘 - clique - star
set-centric formulations
derived in thiswork.in this work.
the listing
actual𝑘 - clique - star6
𝐺𝑠 = 𝑋 ∪ 𝑉𝑐 //2:Derive𝑘 -clique-star
7
𝑆 = 𝑆 ∪ {𝐺𝑠 } // AddAlgorithm
an identified
𝑘 - clique- [79].
star to 𝑆
the vertex-centric or the edge-centric model, do not focus on such
𝑆 ∪ {𝐺duplicates
identified
𝑘 - clique - star to 𝑆𝑠 } // Add anfrom
8 // At the 7 end𝑆, =remove
𝑆
Subgraph
Isomorphism
Subgraph
isomorphism(SI) is a key
8 // At
the end , remove
duplicatesfrom 𝑆
problems at all. Other paradigms, for example array maps or GNNs,
Algorithm
2:checks
𝑘 -clique-starlisting [79].
algorithms
fortheconsidered
problems.
Someparadigms,
such
as
graph
problemwhere
one
whetheragiven(usually
only certain
Finally,graphpatternmatching
Subgraph Isomorphism
Subgraph
isomorphism(SI) is asmall)
key
Algorithm
2: 𝑘 -clique-starlisting [79].
the address
vertex-centricor theproblems.
edge-centricmodel,
do notfocus
on such or

10

k ++

Algorithm 4: Frequent subgraph mining [84].

285algorithms such as clustering. In clustering, one iterates over all
adjacent vertex pairs, and uses their similarity to decide if the pair

SISA codethe vertex-centricor the edge-centricmodel,problems,
domodel,
not focus
on focussuchthecanvertex-centricor graphthe edge-centric
do theynotgraphof achecks
graph whether
G 1 . Here,a weconsideransmall)estab2 is a subgraph
RDBMS
but
do noton suchgraphGproblem
where one
given
(usually
problems
at all. solve
Otherdifferent
paradigms,
formining
examplearray maps
or GNNs,
problems
at
all.
Other
paradigms,
forexample
array
maps
or
GNNs,
problems
at
all.
Other
paradigms,
forexamplearraymaps
lishedVF2[41].ofDue
to its𝐺complexity,
Algorithm
3, we
offeronly
formalguarantees,
as indicatedby pastwork. matching or or GNNs,
graph
𝐺 2 algorithm
is aIsomorphism
subgraph
a Subgraph
graph
we in
consideraddress
certainproblems.
Finally, graphpattern
1 . Here,
Subgraph
isomorphism(SI) anis aestabkey
address
onlycertainproblems.
Finally,graphpatternmatchingoraddress
onlycertainproblems.
Finally,graphpatternmatching
orSubgraph
Isomorphism
Subgraph
isomorphism(SI) is a key
only
providethemostimportantpartthat
recursively
constructs
lishedVF2 algorithm[41].checks
Due to whether
its complexity,
in Algorithm
3, we
RDBMS can solve different graph mining problems, but they do notgraph
problem
where onea given(usually small)
RDBMS
can
solve
different
graph
miningproblems,
but
they
do
not
RDBMS
can
solve
different
graph
miningproblems,
but
they
do
not
graph
problemwhere
onecheckswhetheragiven(usually
small)
acandidatesetofvertices
from
G
,
and
verifies
if
itmatchesthe1
only
providethemostimportantpartthat
recursively
constructs
5
SET-CENTRIC
GRAPH
ALGORITHMS
offer formal guarantees, as indicated by past work.
graph 𝐺 2 is a subgraph of a graph 𝐺 1 . Here, we consider an estaboffer formal
as indicatedby past work.
offerguarantees,
formal guarantees,
as indicatedby past work.
graph
𝐺
is
a
subgraph
of
a
graph
𝐺
.
Here,
we
consideranestabpattern
G
.
2
1
2
a
candidatesetofvertices
from
𝐺
,
and
verifies
if
itmatchesthe1lished VF2 algorithm [41]. Due to its complexity, in Algorithm 3, we
We now present set-centric formulations of graph mining algoalgorithmDuetosupports
its
complexity,
ingraphs.
Algorithm 3, weWeuselishedas VF2anexampleof [41].
how
SISA
labeledpattern
𝐺SI
2 . theonly
providemostimportantpartthat
recursively
constructs
5 rithms.
SET-CENTRIC
GRAPHare
ALGORITHMS
The used set operationsin Table 2.
only
providethe from
most
importantpart thatrecursively
VF2fortransition
betweenstates,one
first
verifies
if
5 on
SET-CENTRIC
GRAPH
ALGORITHMS
We [41],useSI
asanvertices
exampleof how
SISA supports
labeledgraphs.constructs
5 SET-CENTRIC
GRAPH
ALGORITHMS
aIncandidate
setofeach𝐺
Notes
Set operations
accelerated
by SISAare algomarked
1 , and verifies if it matches the
We now
presentListings
set-centric
formulationsof graphminingacandidatesetofvertices
from
𝐺
,
and
verifies
if
itmatchesthethestructureofGmatches
that
of
G
(Line
11).
Then,
label
matchIn
VF2
[41],
for
each
transition
betweenstates,one
first
verifies
if121
pattern 𝐺 2 .
We
now color.
present
set-centric
graphminingwithThe
the
gray
“[in
par]”
that
in aofgiven
loop
one algoWe
now
present
set-centric
formulations
graph
miningalgorithms.
usedset
operations
areindicatesin formulations
Tableof2.
theof𝐺examplethat
ofSISA𝐺 1 (Line
11). Then,
matchpatterning
isstructure
verifiedindependently(Lines12-13).
Checking
if labelvertexlabels
22 .matches
We
use
SI
as
an
of
how
supports
labeledgraphs.
can
issue
set
operations
inparallel.
We
ensurethat
theparallelizarithms.
The
used
set
operations
are
in
Table
2.
rithms.
The
used
set
operations
are
in
Table
2.
Notes on Listings Set operations accelerated by SISA are marked
ing
verifiedindependently(LinesChecking
if vertex
labelsuse
as an L(vexampleof how
SISA
labeledmatch,
i.e., We
if L(vequalstrivial.
Yet,asupports
graph
may
also
1 ) SI2 ), is12-13).
In
VF2is[41],foreachtransition
betweenstates,one
first
verifies
if graphs.
tion
notinvolveconflicting
memoryaccesses.
Weby
now
focus
Notes
on“[inListings
Setindicates
operations
accelerated
SISA
are marked
Notes
on
Listings
Set
operations
accelerated
by
SISA
are
with
thedoesgraycolor.
par]”thatin a given
loop
one
match,
i.e.,
if
𝐿(𝑣
)
equals𝐿(𝑣),istrivial.
Yet,
a
graph
may
also
In
VF2
[41],
for
each
transition
betweenstates,one
first
containedge
labels
that
need
to
be
matched.
This
could
be
done
1
2
formulations
andcolor.
weparallel.
discuss
set representations,
instructions,the structure of 𝐺 2 matches that of 𝐺 1 (Line 11). Then, label match- verifies if
withthe gray“[inindicatesinmarkedwithcolor.
“[in par]”par]”indicates
thatparallelizain aa given
given loop one
canon
issue
set theoperations
inWe
ensurethat thatthecontainedge
labelsthat
to bematched.
belabelsdone
thestructureof 𝐺needmatches
thatoperationsof 𝐺 1This(Line
11). However,Then,label matchwitha standard
approachset[41].
2without
andparallelization
later.
For
clarity,weexcludeunrelated
optimizaing
is verified
independently(Lines12-13).
Checking
ifcould
vertexset
operations
ininparallel.
We
ensurethatthetheparallelizaloop
onecancan
issue
setconflicting
operationsmemory
parallel.
We
ensurethattion does
notissueinvolve
accesses.
We nowfocus
withastandard
approachwithout
set
operations[41].
However,ing
isverifiedindependently(Lines12-13).
Checking
if vertex labels
the generalityof 1setnotationalso
enables
supportinglabel
verifications
fromthelistings.
match,
i.e.,
if
𝐿(𝑣
)
equals𝐿(𝑣),istrivial.
Yet,
a
graph
may
also
tion
does
not
involveconflicting
memoryaccesses.
We
now
focus
2
parallelizationdoes
notinvolveconflicting
memoryaccesses.
1111
on formulations and we discuss set representations, instructions,the generalityofi.e.,
setthatalso
enableslabel
match,
ifnotation
𝐿(𝑣𝐿(𝑣 2in),supporting
trivial.
Yet,averificagraphtion.
Foredgethis,labels
we
firstidentify
Gis1This
where
onebe
endpoint
MaximalListingAwecliqueis representations,aset
fully-connectedsub1 ) equals
containneedtoallbeedges
matched.
could
done may also
on formulations
and
we
set
instructions,We
focus
onCliques
formulations
anddiscuss
we
discuss
representations,andnow
parallelization
later. For
clarity,excludeunrelated
optimiza′ could
tion.
For
this,matchedweedgefirst labels
identify
alledges
in other𝐺
where
oneThisendpoint
1 matched.
contain
that
need
to
be
is
the
newly
vertexv
andtheendpointv
is al- be done
graph
of
an
input
graph;
amaximalcliqueisaclique
not
con1
with
a
standard
approachwithout
set
operations[41].
However,andtheparallelization
later.later.
For clarity,
we exclude
unrelated
instructions,andparallelization
For clarity,
we exclude
unre-optimiza′1is altions fromlistings.
′
is
the
newly
matchedvertex
𝑣
and
the
other
endpoint𝑣
1
withastandard
approachwithout
set
operations[41].
However,
readymatched(i.e.,
v
∈
M
(s)).
This
is
done
with
an
intersection
1
tainedinalargerclique.
Findingallmaximalcliques
is
an
im1
the
generalityofsetnotationalso
enables
supportinglabel
verificationsCliquesfrom from
theListing
listings.
lated
optimizations
the listings.
MaximalA clique is a fully-connected submatched(i.e., 𝑣11′we
∈𝑀
This
is
done
with
an
′ is matched,
1 (𝑠)).
portant Maximal
NP-hardproblem[45,
129, 150,
164].
Algorithm
1 shows
thegeneralityofsetnotationalso
enables
supportinglabel verificaNready(vFor)∩
M 1 (s).
Then,findtheedgesvertexwith
whichv′intersection
1
1
tion.
this,
we
first
identify
all
in
𝐺
where
one
endpoint
1
1
Cliques
ListingAcliqueisafully-connected
subA
cliqueisafully-connected
subMaximal
Cliques
Listinggraph of an input graph; a maximal clique is a clique not con𝑁 1the(𝑣 1 )second∩
𝑀1 (𝑠).
Then,
we first
findthe vertex
with
which
matched,11 is
the widelyusedrecursive
backtracking
Bron-Kerboschalgorithm
tion.
For
this,
we
allotheredges
in 𝐺𝑣thewhere
loop
in Line17.𝑣 Finally,weverifythat
respective
issee
the newly
matchedvertexand theendpoint
𝑣 1′ is one
al- endpoint
1identify
of aninputaFinding
graph;
a maximalis isanot
clique
graph
an
input
graph;
maximalcliqueis cliqueacliquescliquecontainedofingrapha largerclique.
allmaximalanim- not consee
thesecond
loop
in
Line
17.
Finally,
weverifythattherespective′(BK) tained[26, 29,in51].
The
main
recursivefunction
BKPivot
(Line
4)
is
the
newly
matchedvertex
𝑣
and
the
other
endpoint
𝑣 1′ is allabels
match
(Line
18).
ready
matched(i.e.,
𝑣
∈
𝑀
(𝑠)).
This
is
done
with
an
intersection1
1
aclique.
largerFinding
clique.
Finding
maximaltaineda largerproblem
cliques is1cliques
an im-is an im1
portantinNP-hard[45,
129, all
150,maximal164].allAlgorithm
showslabels match (Line 18).
′′
has three arguments that are dynamic sets containing vertices. 𝑅
ready
𝑣the
𝑀1 (𝑠)).
This
isbetween
done
an intersection
𝑁 11(𝑣/*1 ) Input:∩𝑀(𝑠).matched
Then,
find
with
which
𝑣 1 iswith
matched,
1 targetgraph we𝐺 1 ,(i.e.,pattern𝐺vertexmappinggraphs.*/
1 //Non set
1 ∈2 . Output:
portant
NP-hard129,164]. Algorithm
portant
NP-hardproblem problem[45, 129, [45,150, Bron-Kerbosch164].150,
Algorithm
1 shows 1 shows
the widelyused recursive
backtracking
algorithm
For Frequent
Subgraph
Mining(FSM),
we usean established𝑠 0 =second{};∅ ; Line// Initialstate
2 CSR_Grap
is a partially constructed, non-maximal clique 𝑐, 𝑃 are candidate0)) ∩= 𝑀
𝑁 1𝑀(𝑣(𝑠1loop
(𝑠).
Then,
we
find
the
vertexwithwhich 𝑣 1′ is matched,
see23 thein17.
Finally,
weverifythattherespective
1
widelyused
recursive
backtracking
Bron-Kerbosch
thewidelyusedbacktracking
Bron-Kerboschalgorithm(BK)[26,the29,51].recursiveThe
mainrecursivefunction
BKPivot(Line 4)algorithm
Match (𝑠 0 ) ; //scheme
Algorithm
startAlgorithm 3.1]. We show it in Algo3 # pragma
Apriori-based[5],[84,
vertices that may belong to 𝑐 but are yet to be tried, and 𝑋 are versee
thesecond
loop
in
Line
17.
Finally,
weverifythattherespective
labels
match
(Line
18).
4 for ( aut4function
Match
(
𝑠
)
:
[26, The29, that
51].
The
main recursivefunction
BKPivot(BK)[26,(BK)
29,
51].
main
recursivefunction
BKPivot(Line 𝑅4) (Line 4)rithm 4. It first generates candidate subgraphs 𝐶𝑘 (Line 6) and thenhas threeargumentsaredynamic
sets containing
vertices.
5 for ( autices that definitely do not belong to 𝑐. The algorithm recursively
5For
ifFrequent
𝑀 labels(𝑠) covers
all
nodes
in
patterngraph:
output𝑀(𝑠);return
;
match
(Line
18).
Subgraph
Mining(FSM),
weuseanestablished6
for ( ahas
threeargumentsthat are dynamic
containing
𝑅checks
has
argumentsthat aredynamic
setscontaining
vertices.
R
is athreepartially
constructed,
non-maximal
clique𝑐,sets
𝑃 arecandidatevertices.
input graphusingtosubgraph
6 𝑃 (𝑠) their= /* counts
compute cnt
set inof thecandidatepairs (Lineto be 8)added
𝑀 (𝑠) */
calls BKPivot for each new candidate vertex, checks if this gives a7for (Frequent
Mining(FSM),
use
an established
Apriori-based
Algorithm
3.1].[84]We
showweit in
Algo7 for ( 𝑣1 ,For𝑣scheme∈ 𝑃as(𝑠)[5],[84,do: Subgraphis anda partiallyconstructed,
non-maximal
clique𝑐,𝑃
arecandidatethat
maybelong
to
𝑐
but
are
yet
to
be
tried,
and𝑋
arever2 )(SI)
isvertices
a clique,partially
constructed,
non-maximal
cliquec,P
arecandidateisomorphismafundamental
kernel(combining
candi8if (updates accordingly 𝑃 and 𝑋 . Some optimizations need8
𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒= /* original
𝑅𝑐𝑜𝑟𝑒
rule Algorithm
*/
rithm
4.
It
first
generates
candidate
subgraphs
𝐶
(Line
6)
and
then
Apriori-based
scheme[5],[84,
3.1].
We
show
it
in
Algoticesmore
thatdefinitely
donotbelong𝑐.but
Thealgorithm
verticesthat
maytoto𝑐yetyettospaceberecursively
tried,
and𝑋 are ververtices
thatmaybelongtobelong
cthey
but reduce
are
toare
be
tried,
andX
verdategenerationand occurrence verification is 𝑘a very popular FSM
set
operations,butthesearchof arepotential
9𝑐ℎ𝑒𝑐𝑘𝑇 𝑒𝑟𝑚 = |𝑁 1 (𝑣1 ) ∩ 𝑇1 (𝑠) | ≥ |𝑁 2 (𝑣2 ) ∩ 𝑇2 (𝑠) |
1
//A
set-c
checkstheir
countsthe input
graphreferences(Line8) using
rithm
4. Itcnt
firstingenerates
candidate
subgraphs
𝐶subgraph6) and then𝑘 (Linecallscliques
BKPivot
for Foreach
newcandidatechecksifalgorithm
thisgivesrecursively
a a
tices
that
definitely
dothe
notto
belongto𝑐. The(forapproach[5,
see
in [84]).
If thetices
thatdefinitely
doexample,
not belongc.vertex,
algorithm
recursively
2 for 𝑣1 ∈10𝑐ℎ𝑒𝑐𝑘𝑁𝑒𝑤66,= 94,|𝑁 195],(𝑣1 ) \also(𝑀1 (𝑠)∪ 𝑇other[158].
setofThecandidates
extending
1 (𝑠)) | ≥ |𝑁 2 (𝑣2 ) \ (𝑀2 (𝑠) ∪ 𝑇2 (𝑠)) |isomorphism
(SI)
as
a
fundamental
kernel[84](combining
candi3for 𝑣2checkstheir
counts
cnt
in
the
input
graph
(Line
8)
using
subgraphclique,and𝑃ofand𝑋 . Some
optimizations
needis above a certain
user selected
threshold(𝜎 · 𝑛),
calls
for
each
new
if thisacount 𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡
calls
BKPivotforcandidatevertex,
if checks
gives
a gives 11
𝑦 = 𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒∧ 𝑐ℎ𝑒𝑐𝑘𝑇
𝑒𝑟𝑚 ∧ 𝑐ℎ𝑒𝑐𝑘𝑁
𝑒𝑤 a candidate
clique𝑐)updates
isBKPivot
𝑃 \each𝑁accordingly(𝑢)newinstead𝑃,candidate
where𝑢checks∈vertex,𝑃 ∪𝑋.thisOverall,
BK
4
𝑆1 =
date
generation
andoccurrence
verification
is
a
very
popular
FSM
isomorphism
(SI)
as
a
fundamental
kernel[84](combining
candi12𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐=
verify_labels
(
𝑣
,
𝑣
,
𝑠
)
//
If
we
use
labels
.
1
2
is
added
as
a
found
frequent
subgraph
(Line
9).
VF2,
an
SI
algomore
set
operations,but
they
reducethesearchspaceofpotential
clique,andupdatesaccordingly
𝑃
and
𝑋
.
Some
optimizations
needclique,and updateswith
accordingly
P and Xset
. Someoptimizations
need
5
for
is non-trivial,
many different
operations,
includingnon
13𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑦95],= 𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑦 ∧ references𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐//[84]).
If aweusetheapproach
[5,
66,
94,
also
see
other
in
If
date
generation
andoccurrence
verificationisvery
popularFSM
in this section, was found to be an efficient kernel
cliquesFor
example,thesettheyofthecandidates(for
extendingmore
set operations,
reducethespacesearchspace
ofa topotentialrithm coveredmore
set[158].
operations,butsuchthey
reducesearchof potential
labels .
anti-monotonic
ones
asbut
union.
Thus,
it shows
SISA’sability
1//SISA(s′ selected
count
is if
above
a certainuser
threshold𝑛), a(candidate
approach[5, 𝑦66,[84]). If the
14
𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡: 𝑠94,= 95],
NewState(𝑠see, 𝑣1other, 𝑣2(𝜎)Generation; ·references
Match𝑠 ′ ) ofin
all SISA
operations
in
SIalsoarereused.
canclique𝑐)is 𝑃 \For𝑁[158].
(𝑢)insteadof set𝑃, where𝑢 ∈of𝑃candidates∪(for
𝑋 . Overall,cliquesFor
example,set(for BK
extendingafor FSM;
2 SetGraphcliques[158].
example,theofthe
candidates
extendingaacceleratecomplexalgorithms.
15
//
Check
if
labeling
of
𝑣
and
𝑣
and
their
neighborhoods
matches:is didateadded subgraphs
asa foundfrequent
subgraph(Linetime-consuming
9).threshold
VF2, an (𝜎SI ·algo1
2userisselected
3 # pragmacount
is abovea certain𝑛),a candidate(candidate_gen)
less
than
is non-trivial,different
setofoperations,𝑐)is 𝑃many\ 𝑁 (𝑢)instead𝑃,u where
𝑃 ∪ 𝑋 . non
Overall, BK
cliquec) cliqueis P \ withN (u)insteadofP, where∈ P ∪ 𝑢Xincluding.∈Overall,
BK
16 bool verify_labels ( 𝑣1 , 𝑣2 , 𝑠 ) :4 for ( autrithm forall
covered
in
this
found
an
efficientkernel′ ,to′ )beis added
asection,found :wasfrequent
(Line
9).
VF2,
an
SI
algoStill,set
operations;forexample,join𝑁asforall(𝑣subgraph
𝑣
∈
𝑀
(𝑠)
:
𝑣1′ it∈ also5
autoones manysuch
asdifferent
union.
it shows
SISA’sabilityto
1 (𝑣benefits1 ) ∩ 𝑀1 (𝑠)from
is non-trivial,withmanyThus,
different
set operations,
includingnon17SI [84].
isanti-monotonic
non-trivial,with
set operations,
including
non
1 2
′
′
6
for
1 /* Input: A graph 𝐺 . Output: Maximal clique 𝑅 (𝑅 ⊆ 𝑉 ).*/
for18ing
FSM;
all
SISA
SI
reused.
ofefficientcanifthat( 𝐿 (𝑣represent!= 𝐿 (𝑣2in)candidates,) thisor in( 𝐿section,(𝑣1 ,are𝑣1a) key!=was𝐿operation(𝑣2found, 𝑣2Generation) ) : return
false
rithm
coveredtoinbeankernel1 ) operationstreesakernelbyacceleratecomplexalgorithms.
anti-monotonic
ones
such
as
union.
Thus,
it
shows
SISA’sabilitytoanti-monotonic
ones
such
as
union.
Thus,
it
shows
SISA’sabilityto
2 𝑃 = 𝑉 ; 𝑅 = ∅ ; 𝑋 = ∅ ; // Init sets appropriately .
19
true (candidate_gen) is less time-consuming than
didatesubgraphs
Table 3: Findi
forKawano
FSM; all[72],SISA
are reused.
Generation
Hidoreturnandis operations
done using in
setSIunion[84]. These
trees of can3 foraccelerate𝑣complex∈ 𝑉 [ in par] do : BKPivot( {𝑣 } , 𝑃 , 𝑋 ) ;complexalgorithms.
accelerate
algorithms.
mic formulati
4 function BKPivot (𝑅 , 𝑃 , 𝑋 ) :3:
Subgraph
isomorphism[41]. 𝑀set
𝑀2 dense
denote thecurrent
partial
SIAlgorithm[84].
Still,
italso
benefits
operations;forexample,join1 andcan be implemented
with fromeither𝑛-bit
bitvectors
ormappings
sparsedidatesubgraphs(candidate_gen)islesstime-consuming
thanassociated with 𝐺 1 and 𝐺 2 , respectively. 𝑇1 and 𝑇2 denote sets of vertices adjacent to the
if A|𝑃graph| == 𝐺0. and|𝑋 |Maximal== 0 :cliquereturn1 /* 5 Input:
Output:𝑅 (𝑅𝑅; ⊆//𝑉Found).*/ a maximal clique
ing
trees
that
represent
candidates,akey
operationinakernelbyarrays,benefiting
from
SISA-PUM
or
PNM(user’s
choice).
[84].
Still, it also
fromset operations;example,joinones in 𝑀1SIand
𝑀2 , respectively.
𝑁 1 benefits
and 𝑁 2 denoteneighborhoods
within 𝐺for
𝐺2 ,
1 and
= /*
𝑃 ∪ 𝑋 */.
2 𝑃 6= 𝑉 𝑢; 𝑅= ∅Choose; 𝑋 = ∅a ; pivot// Initvertex
sets fromappropriately
respectively.
verify_labels
is usedif graphs
are labeled.
1𝑉 /*
graph
𝐺
Output:𝑅 𝑁(𝑅(𝑣)⊆ ,𝑉 ).*/
Hido
and ing
Kawano[72],
is Clustering
done
using
set union
[84].
These
3 for
par
] A(𝑢)do: do
BKPivot( {𝑣 }(, Maximal𝑃𝑅, ∪𝑋{𝑣);}clique
VertexSimilarity&
Variousassesstrees
how
7 𝑣 ∈
for
𝑣[ in
∈Input:𝑃 \𝑁: .BKPivot, 𝑃∩
𝑋 ∩ 𝑁 (𝑣) )trees that
represent
candidates,
ameasures
key
operation
in a kernel by
2 𝑃BKPivot= 𝑉 ; (𝑅𝑅 ,= 𝑃∅,; 𝑋
𝑋 ):= ∅ ; // Init sets appropriately .
4 function
canbe Frequent
implemented
witheither𝑛-bit
dense
bitvectors
orsparse8
𝑃 = 𝑃𝑣 \∈ {𝑣
𝑋 = 𝑋 ∪ {𝑣
}BKPivot ( {𝑣 } , 𝑃 , 𝑋 ) ;similartwotarget
vertices𝑣(𝐺and𝑢Mining
are,
Algorithm
5.unionTheycan(𝜎 beHido
andSubgraphKawano
[72],
issee
done
using
[84].
These trees(FSM),
weanestablished𝑉 } [;in
1 For/* Input:graph), minimum
support/ countof setause
foundpattern).
5
if |𝑃3 | for== 0 and|𝑋 |par==] 0do: :return𝑅 ; // Found a maximal clique
Algorithmic
4function
BKPivot
(
𝑅
,
𝑃
,
𝑋
)
:
2
*
Output:setsoffrequent
subgraphs
of
sizes
1,
2,
...,
𝑘
(
𝐹
,
𝐹
,
...,
𝐹
).*/
arrays,benefiting
from
SISA-PUM
or
PNM(user’s
choice).
1
2
used
on
their
own,
or
as
a
main
building
block
of
more
complex𝑘6
𝑢 = /* Choosea pivot
vertex
from
𝑃∪
𝑋 */
can
be
implemented
witheither𝑛-bit
dense
bitvectors
or sparse
Algorithm
1: Maximal
CliqueListing(Bron-Kerbosch)[26, 29].
Apriori-based
scheme[5],[84,
Algorithm
3.1].
We
show
it
in
Algo5
if |𝑃 | == 0 and |𝑋 | == 0 : return 𝑅 ; // Found a maximal clique 3 𝐹 1 = 𝑉 ; 𝑘 = 2 //𝑘 = 2 means we start recursion from edges .
VertexSimilarity&
Clustering
Variousmeasuresassesshow
7
for 𝑣 ∈ 𝑃 \ 𝑁 (𝑢) do : BKPivot ( 𝑅 ∪ {𝑣 } , 𝑃 ∩ 𝑁 (𝑣) , 𝑋 ∩ 𝑁 (𝑣) )
4
//
Use
all
subgraphs
in𝐹
togenerate
candidates
of
size
𝑘
:
arrays,benefiting
from
SISA-PUM
or
PNM(user’s
choice).
rithm 4. It first generates candidate
subgraphs Ck (Line 6) and then𝑘−1
6𝑢 = /* Choose a pivot vertex from 𝑃 ∪ 𝑋 */5 while𝐹𝑘−1vertices≠ ∅ do : 𝑣//𝐶
) arecandidate
subgraphs
ofcan
sizebe𝑘𝑘 ( below
8
𝑃 = 𝑃 \ {𝑣 } ; 𝑋 = 𝑋 ∪ {𝑣 }similartwo𝑢 are,
see
Algorithm
They
Similarity
Clustering
measuresassess howfor (Vertcountscntandin theinput8)5. using
subgraph7
for 𝑣 ∈ 𝑃 \ 𝑁 (𝑢) do : BKPivot ( 𝑅 ∪ {𝑣 } , 𝑃 ∩ 𝑁 (𝑣) , 𝑋 ∩ 𝑁 (𝑣) )checks
6
𝐹𝑘 their= ∅ ;Vertex
𝐶𝑘 = candidate_gen(&
𝐹𝑘−1) graph// Use (Lineany Various
selected
kernel[84]VertexSe
used
on
their
own,
or
as
a
main
building
block
of
more
complex7
foreach𝑔∈𝐶
do:(Bron-Kerbosch)[26, 29].
𝑘
8Algorithm
𝑃 =1: Maximal
𝑃 \ {𝑣 } ;Clique
𝑋 = Listing𝑋 ∪ {𝑣}similar two
vertices 𝑣 and 𝑢 are, see Algorithm 5. They can beVertexSe8
cnt = SI (𝑔 , 𝐺 ) // For set operations in SI , see Algorithm 3
on9
ifusedcnt ≥𝜎𝑛theirand 𝑔own,∉ 𝐹𝑘 : or
𝐹𝑘 as∪ = a𝑔 main building block of more complex HW inst
Algorithm 1: Maximal Clique Listing (Bron-Kerbosch) [26, 29].

SetId cvoid dvoid invoid reSetId uSetId iSetId dsize_tsize_tbool isadjacent vertex pairs, and uses their similarity to decide if the pairadjacent vertex pairs,
and4: Frequentuses theirsimilarity
to decide if the pair
Algorithm
subgraphmining [84].
belongs
to a Acluster.
1 /* Input:
graph 𝐺 . Output: Similarity 𝑆 ∈ R of neighborhoods
belongs
cluster.
2 * 𝑁 to(𝑢) aand𝑁 (𝑣) of some vertices 𝑢 and 𝑣 . */(𝑣, 𝑢) =A graph|𝑁 (𝑣) ∩𝐺𝑁.(𝑢)| / |𝑁(𝑣) ∪ 𝑁 (𝑢) | 𝑆 /*Similarity */1 3/*𝑆 𝐽 Input:
Output:Similarity∈ R Jaccardofneighborhoods
algorithms
such
as clustering.
In clustering,one
iteratesover all2 * 𝑁 (𝑢) and 𝑁 (𝑣) of some vertices 𝑢 and 𝑣 . */Algorithm
5: Vertex
similarity
measures.
adjacent vertex pairs,
and usestheirsimilarity
to decide if the pair
3 𝑆 𝐽 (𝑣, 𝑢) = |𝑁 (𝑣) ∩ 𝑁 (𝑢) | / |𝑁 (𝑣) ∪ 𝑁 (𝑢) | /* Jaccard Similarity */belongs
to aSISA
cluster.
Finally,
does not target the “low-complexity” algorithms,
5: Vertex similarity measures.
as they offer few Algorithm
opportunities
for set-centric acceleration [20, 25,
Finally,
SISA
does
targetthealgorithms,
142,/*
Input:A 115,
graph
𝐺not
.147,
Output:Similarity
𝑆 ∈Rof neighborhoods
60,
114,
144,
148,
152,“low-complexity”
172].
example,in
PageRank,
Finally,
SISA
does
not
targetthe For“low-complexity”
algo2 * 𝑁 (𝑢) and 𝑁 (𝑣) of some vertices 𝑢 and 𝑣 . */
as
they
offer
few
opportunities
fornested
set-centric
acceleration
[20,
25,
one
updatesvertexranks
twoloops,
which is noteasilyrithms,as theyoffer
few inopportunities
for set-centric
accelera3 𝑆 𝐽 (𝑣, 𝑢) = |𝑁 (𝑣) ∩ 𝑁 (𝑢) | / |𝑁 (𝑣) ∪ 𝑁 (𝑢) | /* Jaccard Similarity */
42,
60,
144,
147,
148,
152,
172].
For
example,in example,
PageRank,
expressible
with
set
operations.
Our
work
is172].
alreadymore
gen-intion[20,114,25, 115,
42,
60,
114,
115,
144,
147,
148,
152,
For
Algorithm
5: Vertex
similarity
measures.
one
vertexranks
intwo
nestedloops,
which
is noteasilyeralupdates
than otherpatternmatching
accelerators/ frameworks,
as itis
PageRank,
one
updatesvertexranks
in twonestedloops,
which
supports
many
more
problems
beyondsimplepatternmatching.
expressible
withsetnotoperations.
Our
workalready
more more
genFinally,
SISA
does
targetthe“low-complexity”
algorithms,
noteasily expressible
with
set operations.
Ouriswork
is already
eral
than
other
patternmatching/ frameworks,
as 25,
itas
as
they
offer
few
opportunities
foraccelerators
set-centric
acceleration[20,
generalthanotherpatternmatching
accelerators/ frameworks,
5.1
Derivinga
Set-Centric
Formulation
supports
many
more
problems
beyondsimplepatternmatching.
42,
60, 114, many
115, 144,
147,problems
148, 152,beyond172]. For
example,in PageRank,
it supports
more
simplepatternmatching.
Often,
algorithms
set notation,and onemay whichsimply ispickone
updatesvertexuse
ranks
in two nested
loops,
notoperaeasily
5.1
Deriving
Set-Centric
tions Deriving
for memory
acceleration.
Thisthe case
with, formore
example,5.1
aa operations.
Set-Centric
Formulation
expressible
with set
OurisFormulationwork
is alreadygenJarvis-Patrick
Still, one may
needmay
to applymorecomplex
Often,
algorithms
use setsetmatchingnotation,
and
pick
eral
than
otherclustering.
patternframeworks,
as it
Often,
algorithms
usenotation,acceleratorsand oneone may/simply
simplypickoperaoperachanges
to “expose”
set instructions.
The
generalrulematching.
is to assotions
for memory
memoryacceleration.
This
case
with,
supports
many
more
problems
beyondsimpletions
foracceleration.
This isis thethecasepattern
with,forforexample,
example,ciate used data
structures
with
sets,
and
then
identify
respective
Jarvis-Patrickclustering.
Still,
one
may
need
to
apply
more
Jarvis-Patrick clustering. Still, one may need to apply morecomplex
complexset operations.
As anexample,we comparea traditionalsnippetforchangesto “expose”“expose”
set
instructions.
The
generalruleisistoasso5.1
Deriving
a set
Set-Centric
Formulation
changes
toinstructions.
The
generalrule
toalgoassoderiving
the
count
of all 4-cliques
cnt,
a thenderivedset-centric
ciate
used
data
structures
with
sets,
and
identify
respective
ciate
used
data structures
with
sets,
respective
Often,
algorithms
use and
set notation,
andandonethenmayidentify
simplypick
operarithmic
formulation,thecorrespondingsnippetsnippet
in
Table
3.
set
operations.
As
anexample,wewe
compareaSISA
traditionalforset
operations.
As
anexample,comparea
traditionalsnippettions
formemoryacceleration.
This
is
the
case
with,
for
example,The
keyalgorithmicchangeisusing
setintersections
insteadofderiving the count of all 4-cliques cnt, a derived set-centric algoforexplicitly
derivingverifying
the
count
ofStill,
all one4-cliquescnt,toaFor
derivedset-centric
Jarvis-Patrickclustering.
need
apply
more
complexif
verticesare mayconnected.
example,rithmic formulation,andthe corresponding
SISA snippet
in instead
Table 3.
algorithmic
formulation,and thecorresponding
SISA
snippetinchangesto “expose”
set instructions.
The
generalruleissnippet),to assoof
iteratingoverallneighborsof𝑣-𝑣(Lines
4-6,
the
top
1
3
The key algorithmic change is using set intersections instead of
Table
3.
The
key
algorithmicchangeisusing
setintersections
inciateuseddata
structures
with
sets,
and
then
identify
respective
in SISA, weintersectof 𝑣 1 -𝑣 3 (Line4 & 6, the instead
middleexplicitly
verifyingif neighborhoods
vertices are connected.
For example,
steadof explicitly
verifyingif vertices
are connected.
For
example,setsnippet)
operations.
As 4-cliques.
anexample,we comparea traditionalsnippetfortooverfilterof iterating
all neighbors of 𝑣 1 -𝑣 3 (Lines 4-6, the top snippet),insteaditeratingoverneighbors
4-6, thealgotop
derivingofthecount ofall all
4-cliquescnt,ofa vderived
set-centric
1 -v 3 (Lines
in SISA, we intersect neighborhoods of 𝑣 1 -𝑣 3 (Line 4 & 6, the middle
snippet),in SISA, weandintersectneighborhoodsof v
4 & 6,
rithmic formulation,
the corresponding
SISA
snippetin Table3.
1 -v 3 (Linesnippet) to filter 4-cliques.
the middle
snippet) tochange
filter 4-cliques.
The
key algorithmic
is using set intersections instead of
explicitly verifying if vertices are connected. For example, instead
6
SISA: over
DESIGN,SYNTAX,of iterating
all neighborsof 𝑣 1 -𝑣 3 SEMANTICS(Lines 4-6, the top snippet),
in
SISA,
we
intersectneighborhoodsof 𝑣 13.
-𝑣 3 (Line 4 & 6, the middle
We now detail SISA’s design, see Figuresnippet) to filter 4-cliques.

286

Algorithmic Formulations

SISA set-centric
Table 3: Finding all 4-cliques: a traditional (non-set-centric) snippet,
a set-centric algorithTable 3: Finding
all 4-cliques:a traditional (non-set-centric) snippet,
set-centric algorithExample
corresponding
formulations
SISA astructure
mic formulation
derivedin this work,syntax:
and a SISA set-centric snippet.
mic formulation
derived in this work, and a SISA set-centric snippet.
Algorithmic
Formulations
SISA set-centric
Software abstractions
formulations
SISA
software:for (Vertex v : set) { ... }// Set iterators
thin abstraction
VertexSet A = ..., B = ...;// Sets
abstractions // Set operations+ wrappers
VertexSet unionSoftware= A.SISA_Union(B);
SISA software:for (Vertex v : set) { ... }// Set iterators
HW instructions
softwarewrappers
thinSISA
abstraction
Examplesyntax:
VertexSet
A= ...,≈ Bcorresponding=corresponding...;// Sets
structureFrom+ wrappers higher
SISA
SetId create(Vertex*
vs, size_t count);
VertexSet
union = A.SISA_Union(B);// Set operations
Algorithmic
Formulations
instructions
void delete(SetId id); SetId clone(SetId id);
SISA set-centric
to lower
HW
instructions≈
corresponding
softwarewrappers
void insert(SetId id, Vertex v, ...);
formulations
Fromlevelsofvoid
remove(SetId
id, Vertex
v, ...);
SISA
SetId
create(Vertex*
vs, size_t
count);
higherabstraction
SetId
union(SetId
A,
SetId
B, clone(SetId...);
C-styleinstructions
void delete(SetId
id);
SetId
id);
Softwareabstractions
to lower
SetId
intersect(SetId
A,
SetId
B,
...);
void
insert(SetId
Vertexv, ...);
instructions
SISA software:for(Vertexv : set)id,{ ...
} SetId
levels of
SetId
diﬀerence(SetId
A,
B, ...);...); // Set iterators map directly
void remove(SetId
id,...;
Vertexv,
thin abstraction
VertexSet
A = ..., B =// Sets
abstraction
size_tSetId intersect_count(SetId
union(SetId A, SetId A,
B, SetId...); B, ...);
to theHW
C-style+ wrappers
VertexSet
union=
A.SISA_Union(B);//Setoperations
size_tcardinality(SetId
id,
...);
SetId intersect(SetId A, SetId B, ...);
instructions
instructions
bool
is_member(SetId
id,v, ...);
SetId
diﬀerence(SetId
A,Vertex
SetId B,...);
HW instructions≈ corresponding
softwarewrappers map directlyFromsize_t intersect_count(SetId A, SetId B, ...);
to theSISAHWSISA HW
designdetails
SetId
create(Vertex*
vs, ...);
size_t count);
size_tcardinality(SetId
id,
higherinstructions
instructions
void
delete(SetId id);id,
SetId
clone(SetId
id);
bool
is_member(SetId
Vertexv, ...);
to lower
SISA low-level
data
structures
SISA
drivers
Set Metadatavoid
insert(SetId
id, Vertex
v, ...);
levels ofvoid
remove(SetId
id, Vertex v, ...);SISA
HW
designdetails
SISA unit
abstraction
SCU B, CacheSISA-PNM SISA-PUM
SISA HW units
SetId union(SetId
A, SetId...);
C-styleSetIdintersect(SetId
A,
SetId
B,
...);
SISA low-level data structures
SISA drivers
Set Metadata
instructions
SetId diﬀerence(SetId A, SetId B, ...);
map directly
SISA unit
size_tintersect_count(SetId
SetId
B, ...);
Figure3: Overview
SISA
instructions
syntaxat different levels
ofthe
abstraction.
SISA-PUMSCUA,andCache
SISA-PNM
SISAofHW
units
to
HW
size_t cardinality(SetId id, ...);
instructionsbool is_member(SetId id, Vertex v, ...);SISA SISA
code code

3 Match (𝑠 0 ); // Algorithm start
5 if 𝑀 (𝑠) covers all nodes in pattern graph : output 𝑀 (𝑠) ; return ;4 function Match (𝑠 ):6 𝑃 (𝑠) = /* compute set of candidate pairs to be added to 𝑀 (𝑠) */5 if 𝑀 (𝑠) covers all nodes in pattern graph : output 𝑀 (𝑠) ; return ;7 for ( 𝑣1 , 𝑣2 ) ∈ 𝑃 (𝑠) do :isomorphism(SI)graph
as asetkernel[84]
candi16 /*𝑃 (𝑠)Input:
𝐺fundamental
pattern𝐺 2 . Output:
betweentographs.*/= /*target
computecandidatepairs mappingtobe (combining
added
𝑀 (𝑠)
*/
1 ,of
𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒
𝑅𝑐𝑜𝑟𝑒
rule */
27 𝑠80 for= {};== 𝑃/*∅(𝑠); original//state( 𝑣1 ,𝑀𝑣(𝑠do :Initial verification
2 )0 ) ∈anddate
generation
occurrence
is
a
very
popular
FSM
𝑒𝑟𝑚Algorithm= |𝑁 1 (𝑣1 ) start∩ 𝑇1 (𝑠) | ≥ |𝑁 2 (𝑣2 ) ∩ 𝑇2 (𝑠) |38 9Match𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒(𝑐ℎ𝑒𝑐𝑘𝑇𝑠 0 ); //= /* original 𝑅𝑐𝑜𝑟𝑒 rule */4 10function
Match𝑠 ):|𝑁95],
𝑐ℎ𝑒𝑐𝑘𝑁𝑒𝑤 (==94,(𝑣1))also\ (𝑀1 see(𝑠) ∪ 𝑇other≥ |𝑁 2 (𝑣2 ) \ (𝑀
∪ 𝑇2 (𝑠))approach[5,66,
in2 (𝑠)[84]).
If |the1 (𝑠)) | references9𝑐ℎ𝑒𝑐𝑘𝑇𝑒𝑟𝑚|𝑁 11(𝑣
1 ∩ 𝑇1 (𝑠) | ≥ |𝑁 2 (𝑣2 ) ∩ 𝑇2 (𝑠) |5 11 if 𝑀𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡(𝑠) covers allin patterngraph∧: 𝑐ℎ𝑒𝑐𝑘𝑁
output𝑒𝑤𝑀 (𝑠) ; return ;=nodes𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒countis𝑐ℎ𝑒𝑐𝑘𝑁
aboven),2 (𝑠)a candidate10
𝑒𝑤 a=certain|𝑁𝑦1 (𝑣)user\ (𝑀1 selected(𝑠) ∪∧𝑇1𝑐ℎ𝑒𝑐𝑘𝑇(𝑠))threshold| 𝑒𝑟𝑚≥ |𝑁 2 (𝑣(σ) \·(𝑀∪ 𝑇2 (𝑠)) |1
2
6 12 𝑃 (𝑠) 𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐= /* compute =setof candidate
𝑀 (𝑠). */verify_labels( 𝑣1 ,pairs
𝑣2 , 𝑠 )to//be
If added
we use tolabelsis117 13added
subgraph(Line9). VF2,𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒∧ 𝑐ℎ𝑒𝑐𝑘𝑇𝑒𝑟𝑚∧ 𝑐ℎ𝑒𝑐𝑘𝑁𝑒𝑤
for 𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡(𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡
𝑣1as, 𝑣a2 )found∈ 𝑃 𝑦(𝑠):𝑦 =frequent=do𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑦 ∧ 𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐// If anwe SI
usealgo12𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐=
verify_labels
(
𝑣
,
𝑣
,
𝑠
)
//
If
we
use
labels.
1
2 */to be an efficient kernellabels in.= this8𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒/* original
𝑅𝑐𝑜𝑟𝑒
rule
rithm
coveredsection,
was
found
′
1314
𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡∧ (𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐// If
if 𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡
𝑦𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑠(𝑣, 𝑣)1∩, 𝑇𝑣2(𝑠)); | Match(𝑠 ′ )we use
9𝑐ℎ𝑒𝑐𝑘𝑇𝑒𝑟𝑚 = 𝑦|𝑁=1 (𝑣): ∩𝑠𝑇1 =(𝑠)NewState| ≥ 𝑦 |𝑁12
2
2
for15 FSM;
allifSISA
operations
in 𝑣SI
aretheirreused.
Generationof canlabels.labeling// Checkof 𝑣1 andandneighborhoods
matches:′ =1 (𝑠)10𝑐ℎ𝑒𝑐𝑘𝑁𝑒𝑤 = |𝑁 1((𝑣∪2𝑇1 (𝑠))(𝑠| , ≥𝑣1 , |𝑁(𝑣2 )Match\ (𝑀2((𝑠)|1416 bool
if verify_labels𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡
𝑦𝑣11,:) \𝑣𝑠2(𝑀NewState𝑣22);𝑠 ′ ) ∪ 𝑇2 (𝑠)), 𝑠 ):
didatesubgraphs(candidate_gen)islesstime-consuming
than
′𝑒𝑟𝑚
′ ) neighborhoods
1517// Checkif 𝑣′labelingof𝑣1 (𝑠)
and: 𝑣forall
and theirmatches :11𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑦=𝑐ℎ𝑒𝑐𝑘𝐶𝑜𝑟𝑒∧𝑐ℎ𝑒𝑐𝑘𝑇∧𝑐ℎ𝑒𝑐𝑘𝑁
𝑒𝑤
𝑁
(𝑣
)
∩
𝑀
(𝑣
,
𝑣
∈
𝑀
(𝑠)
:
forall
∈
2
1
1
1 2
SI
[84].
Still,
it1 also =benefits
fromjoin′ Iffor
1618
bool𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐
verify_labels( 𝑣𝐿verify_labels, )𝑣)2 , or𝑠 ):( 𝐿 (𝑣set
1(𝑣
12
, !=
𝑣2 ,𝐿 (𝑣𝑠 ) , 𝑣//
we example,
use labels.
if ( 𝐿 (𝑣1 ) !=, 𝑣𝑣1′1)operations;21(2 ) ): return false′ ′ ) 2∈ 𝑀
𝑁1 𝑦(𝑣1=) ∩𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑀(𝑣𝑐ℎ𝑒𝑐𝑘𝑆𝑒𝑚𝑎𝑛𝑡𝑖𝑐(𝑠) : in
1719 trees
forall𝑣1′true∈represent
13𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡𝑦a ∧key// If
we use by
1 (𝑠) : foralling
thatcandidates,akernelreturn1 , 𝑣2operation′′18
if ( 𝐿 (𝑣labels. 1 ) != 𝐿 (𝑣2 ) ) or ( 𝐿 (𝑣1 , 𝑣1 ) != 𝐿 (𝑣2 , 𝑣2 ) ): return false
Hido
and
[72],
[84].
These
trees
3:Kawano
Subgraph
isomorphism[41].
𝑀usingcurrent
partial1 and 𝑀(2set14
if 𝑐ℎ𝑒𝑐𝑘𝐹𝑒𝑎𝑠𝑖𝑏𝑖𝑙𝑖𝑡
𝑦 :is𝑠 ′done= NewState𝑠denote, 𝑣union
𝑣2 );
Match
(𝑠 ′ )mappings
19Algorithm
returntrue
1 , theassociated with 𝐺 1 and 𝐺 2 , respectively. 𝑇1 and 𝑇2 denote sets of vertices adjacent to the
15 //beCheck
if labeling withof 𝑣1 either
and 𝑣2 n-bit
and theirneighborhoods
matches:canimplemented
dense
bitvectors
orsparse
ones
in
𝑀
and
𝑀
,
respectively.
𝑁and𝑁
denoteneighborhoods
within𝐺and𝐺2 ,2 isomorphism
1 𝑠 ):𝑀1 2and 𝑀2 denote the current partial mappings
1
Algorithm
3:1 Subgraph16bool verify_labels( 𝑣1 , 𝑣2 ,[41].
respectively.
is usedif graphs
areor
arrays,benefiting
SISA-PUM
PNM(user’s
choice).
associatedwithverify_labels
𝐺 and 𝐺from
𝑇1 and𝑇labeled.
of vertices
adjacent to the′ , 𝑣 ′ )sets
2 , respectively.
2 denote
)
∩
𝑀
(𝑠)
:
forall
(𝑣
∈
𝑀
(𝑠)
:
17
forall 𝑣1′ 1∈ 𝑁 1 (𝑣1
1𝑁 and 𝑁 denote 1neighborhoods
2ones in 𝑀1 and 𝑀2 , respectively.
within 𝐺 1 and 𝐺 2 ,
1
2 ′
′
18
ifverify_labels(𝐿(𝑣1 ) !=
𝐿is(𝑣used) ifor( 𝐿 (𝑣are) !=/ 𝐿(𝑣2 , 𝑣of
returnfalse
1 , 𝑣1labeled.
respectively.
graphs2 ) ):
1 /* Input:
targetgraph(2𝐺) ),
minimum
supportcount
a foundpattern(𝜎 ).
19 2 returntrue* Output:sets of frequent subgraphs of sizes 1, 2, ..., 𝑘 (𝐹 1 , 𝐹 2 , ..., 𝐹𝑘 ).*/
3
𝐹
=
𝑉
;
𝑘
=
2
//
𝑘
=
2
means
we
start
recursion
from
edges
.
1 /* 1 Input:
target graph(𝐺 ), minimum
counttheof current
a foundpartial
pattern(𝜎 ).
Algorithm
isomorphism[41]. 𝑀 support
and 𝑀2 /denotemappings
Use3: Subgraphallsets
subgraphs
in 𝐹subgraphssize𝑘:
𝑘−1 to 1generate
2 4 *//Output:of frequentof sizes 1,candidates
2, ..., 𝑘 (𝐹 1 , 𝐹of𝐹𝑘 ).*/
2 , ...,adjacentassociatedwith 𝐺 1≠and𝐺 2:, respectively.
𝑇 anddenote sets of vertices
to thedo
are𝑇2candidate𝑘 ( below
3 5𝐹 1while= 𝑉 ; 𝐹𝑘−1
𝑘 = 2∅ //𝑘 = //
2 𝐶means
we 1)start
recursion subgraphsfrom edgesof. size 𝑘
ones
in 𝐹𝑀
𝑁 and 𝑁 2 denoteneighborhoods
within𝐺 1 and 𝐺 2 ,
=and
∅ ;𝑀
𝐶2𝑘, respectively.
= candidate_gen) // Useany selected
kernel[84]𝑘1 all
4 6// Use
subgraphs
in 𝐹 1 to( 𝐹𝑘−1
generate
candidatesof size𝑘:respectively.
verify_labels
if graphs are labeled.
7
foreach𝑔∈𝐶
dois: used 𝑘−1
𝑘
5 while 𝐹𝑘−1 ≠ ∅ do : //𝐶𝑘 ( below ) are candidate subgraphs of size 𝑘
8(𝑔 , 𝐺 ) // For set operations in SI , see Algorithm 3
6
𝐹𝑘 =cnt∅ ; = 𝐶SI= candidate_gen ( 𝐹) // Use any selected kernel[84]9if cnt 𝑘≥ 𝜎𝑛 and 𝑔 ∉ 𝐹𝑘 : 𝐹𝑘 𝑘−1
∪= 𝑔
17 /*
Input:
targetforeach𝑔 ∈ 𝐶𝑘graph
do : (𝐺 ), minimum support / count of a found pattern (𝜎 ).
10k ++28 * Output:of sizesin1, 2,(𝐹 1Algorithm, 𝐹 2 , ..., 𝐹𝑘 ).*/
cnt = sets
SI (𝑔of, 𝐺frequent) // Forsubgraphs
set operations
SI...,, 𝑘see3∉ 𝐹4:𝑘Frequent: 𝐹we=subgraph𝑔 recursion
39 𝐹 1 = if
𝑉 ; cnt𝑘 = ≥2𝜎𝑛//𝑘and= 2𝑔 meansfrom edges .
𝑘 ∪start
Algorithm
mining [84].
10k ++ all subgraphs in 𝐹𝑘−1 to generate candidates of size 𝑘 :4 // Use
5 while𝐹𝑘−1≠ ∅ do : //𝐶&( below ) are Various
candidatemeasuressubgraphsassessof size𝑘𝑘 Clustering
VertexSimilarity
how
4: Frequent
subgraphmining6
𝐹𝑘 = ∅ ; 𝐶𝑘 =Algorithm
candidate_gen( 𝐹𝑘−1) // Useany[84].
selected kernel[84]algorithms
suchasclustering.
In
clustering,one
iteratesoverallsimilartwovertices
v
and
u
are,
see
Algorithm
5.
They
can
be
7
foreach 𝑔 ∈ 𝐶𝑘 do :8 adjacentcnt vertex= SI (𝑔 ,pairs,
𝐺 ) //andFor uses
operationsin SI ,tosee
Algorithm
3
theirsimilarity
decideif the
pair
used
on
their
own,
or𝑔as
a set
main
building
block ofmore
complex
9
if cntsuch≥ 𝜎𝑛asand∉ 𝐹𝑘 : 𝐹𝑘 In∪ =clustering,𝑔algorithms
clustering.
one iterates over all
belongs
toacluster.
10k ++algorithms
such as clustering. In clustering, one iterates over all

1 //Non set-centric code:
2 CSR_Graph g(𝐺 ) ; // Standard codes often use some form of CSR
code: for31 #//Nonpragmaset-centric
omp parallel
CSR_Graphg (:𝐺g).V; ()//)Standard
codes
often inuseparallelsomeof Event,
CSR Greece
42 for( auto v1//MICROFor allvertices.Virtual’21,
October
18–22,
2021,form
pragmaompv2 parallel
53 #for( auto: g. N_out (forv1 )) // Explore neighborhoods of v1 - v4 ...
: : g .V
) //For
verticesin forparallel.
64 forfor( auto( auto v1v3
g . ()
N_out( v2) ) all// ...
searchinga 4 - clique: : g.g.N_out
v1 - v4 ...
75 forfor( auto( auto v2v4
N_out((v1v3)))) ////Explore
If v1 - v4neighborhoods
are connected ofpairwise
forif((set-centricautov3( :v1 g,code:.v3N_out) ) //...
searchingfor(v2
a ,486 1 //Nong . edge) && (gv2. edge( v1, v4) && g . edge
v4 clique)) ++ cnt ;7 2 CSR_Graphfor ( autog (v4( v3 ) ) codes// If v1
- v4 are𝐺 ): ; g.//N_out
Standard
often
use connected
some form pairwiseof CSRif (g .omp
edge
(v1 , v3 ) &&18 //A
set-centricalgorithmic
formulation:
3 # pragma
parallelforg . edge ( v1 , v4 ) && g . edge ( v2 , v4 ) ) ++ cnt ;
2 for
𝑣
∈
𝑉
in
parallel
do
:
//
For
all
verticesinparallel.
4 for1 ( auto v1 : g . V () ) // For all vertices in parallel .
set-centric
31 5//Afor𝑣2( auto∈ 𝑁 + (𝑣v2
) : dog .: N_out// Forformulation:eachneighbor
𝑣1 ...
1algorithmicfor( v1) ) //
Explore ofneighborhoodsof v1 - v4 ...
𝑣1 =∈ (𝑉auto
do : Find// For all vertices
in ofparallel .𝑣 .
+ (𝑣 parallel
42 6for 𝑆for
𝑁 in
) ∩:𝑁g+.(𝑣N_out
neighbors( v2 ) ) common// ... searchingfor 𝑣a1 4and- clique1
1v32 ) //
2
3
for 𝑣2 ∈ 𝑁 + (𝑣1 ) do : // For each +neighbor of 𝑣1 ...
for𝑣3( ∈auto
v4: : cnt
g . N_out
𝑁 //
(𝑣3If
) | v1 - v4 are connected pairwise
5 7
for𝑆 1 do+= |𝑆(1v3∩))48
𝑆 1 if= ( g𝑁.+edge(𝑣1 ) (∩v1𝑁,+v3(𝑣2)) &&//gFind
commonneighborsof𝑣
and. cnt ;. edge ( v1 , v4 ) && g . edge ( v21, v4 ) ) 𝑣2++
|𝑆 1 ∩ 𝑁 + (𝑣3 ) |𝑣3 ∈ 𝑆 1 doset-centric: cnt += code:
1 5 //SISAfor(simplified)
2 SetGraph
g = SetGraph(𝐺 ) ; formulation:
1 //A set-centricalgorithmic
set-centric
31 #2//SISA
pragmafor do :code:for 𝑣(simplified)∈ 𝑉 parallelin parallel// For all vertices in parallel .
1 omp+
42 for
(
auto
v1
:
g
.V
()
)
auto eachv2 : gneighbor. N_out ( v1of) ) 𝑣{1 ...
SetGraphg=
SetGraph)(;For3
for 𝑣2 ∈ 𝑁 (𝑣1 ) dofor:(𝐺//
53 # pragma
auto omp
S1 = parallelintersect+for(g . N_out ( v1 ) , g . N_out ( v2 ) );+4
𝑆 1 = 𝑁 (𝑣1 ) ∩ 𝑁 (𝑣2 ) // Find common neighbors of 𝑣1 and 𝑣2 .
64 for for( auto: ()S1 ) cnt
intersect_card( autov1 : v3
g .V
for +=( autov2 : g. N_out((S1v1,) )g .{N_out ( v3 ) ); }|𝑆 1 (∩v1𝑁)+,(𝑣g3.) N_out|
for S1𝑣3 =∈ 𝑆intersect+=N_out
1 do : cnt(g.
5 5
auto( v2 )) ;Table
4-cliques:a traditionalsnippet,algorith6 3: Findingfor ( allauto
v3 : S1) cnt += (non-set-centric)
intersect_card( S1 ,a set-centricg. N_out ( v3)) ; }//SISA (simplified)
set-centricmic1formulation
derived in thiswork, and acode:
SISA set-centric snippet.
2 SetGraphg 4-cliques:= SetGraph(𝐺 ) ; (non-set-centric) snippet, a set-centric algorithTable
3: Finding alla traditional# pragma omp
parallel
for and a SISA set-centric snippet.
mic3 formulation
derivedin this work,
4 for ( auto v1 : g . V () ) for ( auto v2 : g . N_out ( v1 ) ) {5
auto S1 = intersect ( g . N_out ( v1 ) , g . N_out ( v2 ) ) ;6
forExample( auto corresponding
v3 : S1 ) cntsyntax:+= intersect_cardSISA( S1 ,structureg. N_out ( v3 ) ); }SISA code

1 /* Input: target graph 𝐺 1 , pattern 𝐺 2 . Output: mapping between graphs.*/
2 𝑠 0 = {}; 𝑀 (𝑠 0 ) = ∅ ; // Initial state

1 3/*Match
Input:
graph 𝐺 1Set
, pattern
SISA:
Set-Centric
Architecture(𝑠 0 )target; Instruction// Algorithm
start 𝐺 2 . Output: mapping between graphs.*/
𝑠 0function= {};𝑀 Match(𝑠 0on) =Processing-in-Memory(𝑠∅);: // Initial statefor2 4Graph
Mining
Systems

3: Overview
of SISA instructions
and syntax
at different levels of abstraction.
SISA
HW
designdetails
6 FigureSISA:
DESIGN,SYNTAX,SEMANTICS
drivers
SISA low-level data structures
We nowSISA
detailSISA’sdesign, see Figure 3.
SISA low-level data structures

Set Metadata

unit
6 SISASISA:DESIGN,SCU CacheSEMANTICSSISA-PNM SISA-PUM
SISA HW unitsSYNTAX,
We nowdetail SISA’s design,
Figure 3.
6.1
Representation
ofsee
Sets

Figure 3:
3: Overview
Overview ofof SISASISA instructions
instructions andand syntax
syntax at
at different
different levels
levels ofof abstraction.
abstraction.
Figure

The first key question is how to represent sets: SISA’s “first-class
6.1 Representation
Setsgraph algorithm – there are
citizens”.
We observe that – ofin each6
SISA:
DESIGN,SYNTAX,SEMANTICS
two
different
classesof data sets:structures.
class
The fundamentallyfirst key questionis how
to represent
SISA’sOne“first-class
6.1
RepresentationofSets
We(1)now
detailSISA’s thatdesign,see
3. algorithm
arevertex(𝑣)Figurethat
maintainthe structure
citizens”.
Weneighborhoods
observe
– in𝑁
each
graph
– there are
The
first
questionisare
how
to represent
sets:“first-classofthefundamentally
inputkeygraph.
There𝑛classessuch
sets,
theirstructures.
totalSISA’ssize is𝑂 (𝑚),
twodifferentof dataOne
class
citizens”.
We neighborhood
observe that is–ofin𝑁eachgraph
algorithm– static
there areandsinglestaticcurrently
focusare(1) vertex
neighborhoods(𝑣)(wethat
maintaintheon
structure
6.1eachRepresentation
Sets
twofundamentallydifferent
classesof datastructures.
One
class
graphs)and sorted(following
establishedpractice
in is
graph
ofThe
thefirst
input
graph.
There
𝑛the
such
sets,
their
total
size
𝑂 (𝑚),
keyquestionis arehowtorepresent
sets:
SISA’s“first-classprocessing[109]).
Another classisare
auxiliary
structures,forareeach(1) vertex
neighborhoods
N(2)
(v)
that
maintaintheonstructure
andsingleneighborhood
static(wecurrently
focus
staticcitizens”. We observe that – in each graph algorithm – there areexample𝑃 in sorted
Bron-Kerbosch(Listing
1).sets,These
sets
are size
usedof the input
graph.(following
There aren suchtheir
total
istoO(m),graphs)andtheestablishedpractice
inOne
graph
two fundamentallydifferent classesof data structures.
class
maintainalgorithmic
state.
areusually
dynamic,
and eachsome
singleneighborhood
isTheystatic(wecurrently
focus they
on forstaticprocessing[109]).
Another
class
are
(2)
auxiliary
structures,are(1)
vertexneighborhoods
𝑁
(𝑣)
that
maintainthestructuremay
be unsorted,
their (following
number (Listing(in thea givenalgorithm)
isare
usuallyagraphs)sortedestablishedpracticein graphexample𝑃andin graph.
Bron-Kerbosch
1).
These
used
of theconstant,
input
Theretotal
aresize𝑛 suchsets,
theirsets
total
size
is 𝑂to(𝑚),(small)andAnother
their
is 𝑂
(𝑛).
While
SISA
enables
processing[109]).
classTheyare(2)
auxiliary
structures,formaintainsomealgorithmic
state.
areusually
dynamic,
they
and
each
singleneighborhoodisstatic(wecurrently
focus
onstatic
using
any
set
representation
for anyset,
we offercertainexampleP in
Bron-Kerbosch(Listing1).algorithm)
Thesesetsis areuseda tomaybeunsorted,
their number(in
aspecific
given
usuallygraphs) and sorted(following
the established practice in graphrecommendations
to maximize
performance.
(small)constant,
andtheir total
sizeThey
is 𝑂 (𝑛).
While SISA
enablesmaintainsome algorithmic
state.
are usually
dynamic,
theyprocessing[109]).
Anotherclass
are (2) auxiliary
structures,SAsshould
be
used
for
small
neighborhoods
andforcertain
the forusing
set representation
for any
set,
weDBs
offer
may any
be unsorted,
their number(in aspecificgiven algorithm)
isusuallyaexample𝑃 in(Listing
1). Theseused tolarge
ones (intheBron-Kerbosch
evaluation,vary
the threshold
sosetsthat are5%-30%
recommendations
tomaximize
performance.
(small)constant,
andtheirwetotalsize
is O(n). While
SISA
enablesmaintainsome algorithmic
state.
They are isusually
dynamic,
theylargestuse
Thisapproachmemoryefficient.
SAsneighborhoods
shouldused
forDBs).
smallandweDBs
forcertain
the
using
any setbe
representation
forneighborhoods
any specific set,offer
may be unsorted, their number (in a given algorithm) is usually alarge
ones (in the evaluation,
we vary
the threshold so that 5%-30%
recommendations
to maximize
performance.
(small) constant, and their total size is 𝑂 (𝑛). While SISA enables
largestuseforDBs).
This
approach is memory
efficient.
SAsneighborhoods
should be usedsmallneighborhoods
and DBs
for theusing any set representation for any specific set, we offer certain
large ones (in the evaluation, we vary the threshold so that 5%-30%
recommendations to maximize performance.
largest neighborhoods use DBs). This approach is memory efficient.
SAs should be used for small neighborhoods and DBs for the
For example, for |N (v)| = n/2, a DB takes only n bits while an SA
large ones (in the evaluation, we vary the threshold so that 5%-30%
uses 16n bits (for a 32-bit word size).
largest neighborhoods use DBs). This approach is memory efficient.

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

𝐴 and 𝐵
Set
Time
Input size Main form of datains Set op.
S? Time𝐴 and 𝐵
Set
Input
Main formof data[bits]size transfer(§ 8.2)ins Set op. represent. algorithm
S? complexity
represent. algorithm
complexity[bits]
transfer (§ 8.2)
0x0 𝐴 ∩ 𝐵 SA ∩ SA Merge, 𝑂 ( |𝐴 | + |𝐵 |) 𝑊 |𝐴 | + 𝑊 |𝐵 | Streaming
0x0𝐴
𝐴∩∩𝐵𝐵 SASA∩∩SASA Galloping
Merge
𝑂((|𝐴
|𝐴| |log+ |𝐵
𝑊|𝐴|𝐴| |++𝑊
𝑊|𝐵|𝐵| |Random
Streaming
0x1,, 𝑂|𝐵|)|) 𝑊
accesses
0x1 𝐴 ∩ 𝐵 SA ∩ SA Merge
Galloping, 𝑂 ( |𝐴 | log |𝐵 |) 𝑊 |𝐴 | + 𝑊 |𝐵 | Random accesses
vs.
0x2 𝐴 ∩ 𝐵 SA ∩ SA Merge vs.
, cf. 0x0 and 0x1 𝑊 |𝐴 | + 𝑊 |𝐵 | cf. 0x0 and 0x1
0x2 𝐴 ∩ 𝐵 SA ∩ SA gallop.
, cf. 0x0 and 0x1 𝑊 |𝐴 | + 𝑊 |𝐵 | cf. 0x0 and 0x1
gallop.
0x3 𝐴 ∩ 𝐵 SA ∩ DB Galloping, na 𝑂 ( |𝐴 |)𝑊 |𝐴 | + 𝑛
Random accesses
0x3𝐴
𝐴∩∩𝐵𝐵 DBSA ∩∩ DB
DB Bitwise
Gallopingna𝑂
𝑂(𝑛/(𝑞𝑆))( |𝐴 |)
Randomaccesses
0x4
AND na,, na
𝑛𝑊+ |𝐴𝑛 | +𝑛In-siturow
copies0x4 𝐴 ∩ 𝐵 DB ∩ DB Bitwise AND na, na 𝑂 (𝑛/(𝑞𝑆))𝑛 +𝑛In-situ row copies
0x5 𝐴 ∪ {𝑥 } DB ∪ {𝑥 } Set bit
na, na 𝑂 (1)𝑛 +𝑊
Random access
0x5𝐴𝐴\∪{𝑥{𝑥}}DBDB\∪{𝑥{𝑥}} Clear
Set bitbit
na,na
na𝑂
𝑂(1)
(1)
𝑊
Randomaccess
access
0x6
na,
𝑛𝑛++𝑊
Random0x6 𝐴 \ {𝑥 } DB \ {𝑥 } Clear bit
na, na 𝑂 (1)𝑛 +𝑊
Random access
Table 4: Overview of SISA instructions, one row describes one specific set operation variant.
Table
4:
of
one
set
variant.
Table
4:Overview
Overview
ofSISASISA(instructions,
instructions,onerowdescribes
onespecificspecific
setoperation
operation
variant.
Set
elements
are vertices
𝐴,
𝐵 ⊆ 𝑉 , 𝑥 ∈one
𝑉 ).row“ ”describes
means “yes”.
“na”
means
“not applicable”.
Setelements
elements
arevertices
vertices(𝐴,B𝐵 opcode.
). “ ” means“na”
means “not“notassumes
applicable”.
Set
are
(A,
⊆⊆ V𝑉,, x𝑥 ∈“S𝑉
V(Sorted)”“yes”.if“na”
means
applicable”.
“ins”
is a proposed
instruction
indicates
an instruction
set“ins”isisaaproposed
proposed
instruction
opcode.
“S(Sorted)”indicatesififan
aninstruction
instructionassumes
assumesset
set
“ins”
instruction
opcode.
(Sorted)”indicates
representationsof 𝐴
and 𝐵 to besorted“S(thus
two columns).
representations
of
𝐴
and
𝐵
to
be
sorted(thus
twocolumns).
representations of A and B to be sorted (thus two columns).

Figure 4 shows an SA and a DB built from the same vertex set.
Figure 44 shows
shows an SA
SA andand aa DB
DB built
built fromfrom thethe samesame vertex
vertex set.
set.
FigureThen,
it illustratesan
an example
SISA
graph representation
where
Then,
it
illustrates
anexampleSISA
graph
representation
where
Then,
it illustrates anare
exampleSISA
graph
representation wheresome neighborhoods
DBs andsome
are SAs.
some neighborhoods
neighborhoods areare DBs
DBs andand somesome areare SAs.
SAs.
some

6.2
6.2 High-Performance
High-Performance Set
Set Operations
Operations
6.2
High-Performance
Set
Operations

The second key challenge in SISA is how to apply set operations
The second
second key
key challenge
challenge inin SISASISA isis how
how toto apply set
set operations
operations
The
for highest
performance.
For this,
we detailtheapplyalgorithmic
aspects,forhighestperformance.
For
this,
we
detailthealgorithmic
aspects,
highest performance.
For this,we (useddetail PIM
the algorithmic
aspects,
aforsummaryis in Table 4. HWdetails
and a performanceasummary
is
in
Table
4.
HW
details
(used
PIM
and
a
performancea summaryis in Tablein4.Section
HW details
PIM anda performancemodel)are discussed
8. An(usedoverviewof thestructure ofmodel) areare discussed
discussed inin Section
Section 8.
8. An
An overview
overview ofof thethe structure
structure ofofmodel)SISA
is in Figure
3.
SISA isis in
in Figure
Figure 3.
3.
SISA
Set Intersection 𝐴 ∩ 𝐵 is a key operation in SISA, because ourSet Intersection
Intersection A
𝐴 ∩B𝐵 isis aa key
key operation
operation inin SISA, because
because ourourSetanalysis
illustrates that ∩it is used in essentially
allSISA,considered graphanalysis
illustrates
that
it
is
used
in
essentiallyallconsidered
graph
analysis illustrates
it is discussused in theessentially
all consideredalgorithms.
We nowthat
brieflymost relevant
variantsgraphof ∩,algorithms. We
We now briefly
briefly discuss the most relevant variants of ∩,aalgorithms.
summary is innow
Figure 4. discuss the most relevant variants of ∩,a summarysummary is
is in Figure
Figure 4.
4.
•a SA[sorted] in
𝐴 ∩ SA [sorted]
𝐵 The intersection of two sorted
SA [sorted][sorted] A𝐴 ∩∩ SASA [sorted][sorted] B𝐵 The
The intersection
intersection ofof twotwo sorted
sorted•• SAsSA
is commonlyused when processing
two neighborhoods.
It
SAs isis commonlycommonly used
used when
when processing
processing two
two neighborhoods.
neighborhoods. ItIt
SAs
comes in two “flavors”. If 𝐴 and 𝐵 have similar sizes (|𝐴| ≈ |𝐵|),
comes inin two “flavors”.
“flavors”. IfIf A
𝐴 andand B𝐵 have
have similar sizes
sizes (|A|(|𝐴| ≈≈ |B|),
|𝐵|),
comes
one
preferstwo
the merge scheme
where onesimilar
simply iterates
throughone
prefersthemerge
schemewhere
onesimplyiteratesthrough
one prefers the merge scheme where one simply iterates through287

Input set
Input setn = 16set(#vertices)
Input

Sparse Array (SA)Sparse Array (SA)SparseW [bits] Arrayfor an (SA)Size [bits]:

n = 16 (#vertices) element
W [bits](usuallyfor an Size[bits]:{0,15}
W[bits]:×n =...,
16
W[bits] (usuallyfor
an SizeW{0,..., (#vertices)
15}
×aelement
memoryword)#vertices
element(usually{0,example..., 15} set:W×a memory
word)An#verticesa memory word)
An 6,
exampleset:#vertices
{5,
7,
11,
12}
6
5
11
12
7
An
{5,example
6, 7, 11,set:
12}
5 6
7 11 12{5, 6, 7, 11, 12}
5 6
7 11 12

Dense Bitvector (DB)
Dense Bitvector (DB)
Dense Bitvector (DB)Size [bits]: nSize [bits]: nSize [bits]: n

Example SISA graph representation
Example SISA graph representation
ExampleSISA graph representation
1

1 3
1 633

866
288
2
52
5
11
5
11
12
11
12
0
12
0
0

n
n
n

0 000 0 1 110 0 01 1 000

1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0n
10 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 n
1n

0 000 0 0 111 1 01 1 111
0 000 0 0 111 1 01 1 111
0 0 10 10 0 0 1 01 01 11 10 01 01 01 11 11
0 011 0 0 100 1 10 0 011
0 0 01 1 10 0 1 10 0 01 11 00 00 00 01 11
0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 Store0 0 0 01 01 10 1 1 0 00 01 10 10 00000 01 using
DBs
Store
0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 using
DBs
Store
110
080 0 09 0 111
StoreDBs
150 0 1 1 0 0 0 using

Processing sets in SISA
Processing sets in SISASA,
SA (similar sets
sizes)in SISA A
Processing
SIS

SA, SA (similar sizes) Use
rgAe /SA, SA (similar sizes) PNUMse(mSeIS
A
g)e /
rg

∩
∩
∩
∩
∩
∩
SA, DB
using
SAs
Store
11
8
9
15
SA, DB
using
SAs
Store
28 39 15
11
SA,
∩ DB
using SAs
15 15The switching point
between∩222 33 15The
switchingpoint
betweenusing
SAs
and DBs
is determined
∩ DB
2
3
DB,
The
switchingpoint
between
using
SAs
and
DBs
is
determined
by
the
user:
for
each
vertex
v,
14
12 3
DB,
DB
using
SAs
and
DBs
is
determined
by
the
user:
for
each
vertex
v,
store
N(v)
as
a
DB
if
d(v)
≥
t
×
n
1 14
∩ DB
by
user:
each
vertexstore
as fora DB
if d(v)≥ tifv,
× n DB,("t"theisN(v)
set
by
the
user)
and
1 14
∩
asby
a the
DB notif d(v)≥ t ×if n("t"N(v)isaset
user)
and
using
DB
does
exceedPointers from vertices store∩
setby does
thestorage
user)
and
using
a DB
not exceed
theismaximum
limitif
toPointerstheir neighborhoods
from vertices ("t"Other set operations.........

For
example,for|𝑁== 𝑛/2,
aa DB
takes
only
𝑛𝑛 bits
while
SA
ForAuxiliary
example,sets
forbenefit|𝑁(𝑣)|(𝑣)| from𝑛/2,
DBstoredtakesasonly
bits
while an
an
SA
being
dense
bitvectors.
This
uses
16𝑛
bits
(for
a
32-bitwordsize).
uses
16𝑛
bits
(for
a
32-bitwordsize).
is because
such
sets
arefromoften dynamic,
andupdatesor removals
Auxiliarysetsbenefitstoredas
bitvectors.
This
Auxiliary
setsAsbenefitfrom being
being
storedasdensedense
bitvectors.
This
take
O(1) time.
inpracticethere
is usuallya smallconstantisbecause
such
sets
are
often
dynamic,
andupdatesorremovalsisbecause
such
sets
are
often
dynamic,
andupdatesorremovals
numberof such setsin
consideredalgorithms,
the aneededstorage
is
take
𝑂
As
in
practicethere
is usuallyconstanttakeexcessive,
𝑂(1)(1) time.
time.
Asinthanpractice
aasmallsmall
constant
not
e.g.,
less
3% onthere
top ofisausually
CSRtheforneededgraphstorage
with thenumber
of
such
sets
in
consideredalgorithms,
isnumber degreeof such100
sets(suchin consideredalgorithms,
the neededstorageisaverageas3%
orkut),
assuming
using
32 threads
andnotexcessive,
e.g.,
less
than
on
top
of
aaCSR
for
aagraph
with
the
not
excessive,
e.g.,
less
than
3%
on
top
of
CSR
for
graph
with
the
the Bron-Kerboschalgorithm,
with auxiliary using
sets P,32X threads, and R (theaveragedegreeas orkut),averagedegree 100
100is(such(suchorkut),Tassuming
assuming
using
32analyze
threads and
and
space
complexity
O(Tn)aswhereis #threads).
We
and
the
Bron-Kerboschalgorithm,
withauxiliary
sets
𝑃,
𝑋
,
𝑅𝑅 (thethe Bron-Kerboschalgorithm, andwithdatasets.
auxiliarysets
𝑃, 𝑋 , andand(theconfirm
it
for
other
algorithms
For
example,
in
SI,
the
space
isis 𝑂𝑂(𝑇𝑛)𝑇𝑇 isis #threads).
We
analyzeandspace complexity
complexity(𝑇𝑛) where
where#threads).
We
analyzeandstoragecomplexity
is(TnP)(where
P
is
the
size
of
the
subgraph),confirm it for other algorithms and datasets. For example, in SI, theconfirm it
fornegligible
other algorithms
and datasets.
For example,
SI, thewhich
also
in practiceusuallysmall.
Toincontrol
storageiscomplexity
is (𝑇𝑛𝑃)(whereas𝑃Pisisthe
size ofthe subgraph),storagecomplexity
is(𝑇𝑛𝑃)(where
𝑃
is
the
size
of
the
subgraph),space usage,user may
above asmall.
certainwhich
is alsothenegligiblein pre-specify
practice as 𝑃that,is usually
To numbercontrol
which
isSISA
also starts
negligible
in SAspractice
𝑃 is usually small. To control
of
DBs,
use
only.as that,space
usage,
the usertomay
pre-specify
above a certain number
space
the userselecting
may pre-specify
that, above aFor
certainnumber
Theusage,user
set representation.
programmaof DBs,
SISAcontrols
starts to use SAsaonly.
of
DBs,
SISA
starts
to
use
SAs
only.
bility,offers a predefined
graph
structure, where
small andTheSISAuser controls
selecting a set
representation.
For programmaTheuser controls selecting
a set representation.
For programmalargeneighborhoods
are automaticallycreated (when
SISA andprobility,
SISA offers a predefined
graph structure,
whereasmallbility,starts)
SISA offersa predefinedwheresmall andgram
as sparse
arraysandgraphdensestructure,
bitvectors,
respectively.
A
large
neighborhoods
areautomaticallycreated (whena SISA prolarge neighborhoods
areautomaticallycreated(when
a SISA
progivenneighborhoodN(v)
isstoredasaDBwhenever
|N
(v)|
≥
t
·
n
gram starts) as sparse arrays and dense bitvectors, respectively. A
gram
starts)sparsearrays andbitvectors,A(t∈ (0;neighborhood
1) is aasuser
parameterthat dense
controls
a “bias” respectively.
towards
given
𝑁 (𝑣) is stored
asa DB whenever|𝑁 (𝑣)| ≥using
𝑡 ·𝑛
given
neighborhood𝑁(𝑣)
isstoredasaDBwhenever
|𝑁
(𝑣)|
≥
𝑡
·
DBs
or SAs)it does
not exceed
storageabudget
set by
the𝑛
(𝑡
∈ (0;
1) is anda userparameterthat acontrols“bias” limit
towards
using
(𝑡
∈
(0;
1)
is
a
user
parameterthat
controls
a“bias”
towardsusing
user or(SISA
default
limit of
10% of theadditional
DBsSAs)byandit doesuses
not aexceed
a storage
budgetlimit setstorage
by the
DBs
orof
SAs)
and it does
notexceeda storage
budgetby the
on
top
the
size
when
storedonlyofwithSAs).limit
For setexample,user(SISA
bygraphdefaultuses
a limitof 10%
the additional
storage
user
(SISA
by
default
uses
a
limit
of
10%
of
the
additional
storage
ton=top0.5ofindicatesthat
eachvertexconnected
toSAs).
at leastof allthe graphsize
when
storedonly with
For50%
example,on top ofhas
theitsgraphsize whenstored
storedas
onlywith SAs). For example,
neighborhooda DB.
𝑡vertices= 0.5 indicatesthat each vertex
connected
to at least 50% of all
𝑡 = 0.5 indicates that each vertex connected to at least 50% of allvertices has its neighborhood stored as a DB.
vertices has its neighborhood stored as a DB.

a DB doesnotthe maximum
storagelimit(also
specifiedbytheexceeduser).
Pointers
from vertices using
to their neighborhoods
the maximum
limit
(also
specifiedstorage
by the user).
to their neighborhoods(also specified by the user).

e /
in
mIS
(m
eaS
e)
sNtrsM
PU
ing
erg
(m
am

SA, SA (sizes vary a lot) PNsMtreeaming)
SA, SA (sizes vary a lot) str ISA
SA, SA (sizes vary a lot) Use SS
p. /
ISA
allo

have
similarvariants
Other
set operations
have similarvariants
Other
set operations
have similar variants(g A ph.)/
Mse
rc
PNU
eaallo
SsIS
e (g
ry
/)
UNasM
bPin
eaprc. h(gasllo
PbNinMarysearch)
ry
a
in
b
A
IS
Use SanISAmdoMse(r SISe
sd)om
PNU
snA
(rsa
e
ceS
aNscM
)
om
PU
(reasnsdes)
c
M
c
a
N
P
ses
acceSsISA
e
s
U
Ae
wis
(bSitISA
PUUMseeS(bryis) eISitow
e m
sM
e)
UU-m
in
P
(bitmwoisry
PUinM-meemory)in-mFigure 4: SISA representations of sets and graphs, and processing SISA sets.
Figure 4: SISA representations of sets and graphs, and processing SISA sets.
Figure 4: SISA representations of sets and graphs, and processing SISA sets.

𝐴 and 𝐵, identifying common elements (time 𝑂 (|𝐴| + |𝐵|)). If one
𝐴 and 𝐵, identifying common elements (time 𝑂 (|𝐴| + |𝐵|)). If one
set is much smaller than the other (|𝐴| ≪ |𝐵|), it is better to use
is muchsmaller thanthe other(|𝐴|(time≪ |𝐵|),
it is+better
toone
use
AsetandB, identifying
commonelements
O(|A||B|)). If
the galloping scheme [1], in which one iterates over the elements
theisgalloping
scheme[1],thein whichone ≪iteratesover
the elements
setmuch smallerthanother (|A|
|B|), itis betterto useof a smaller set and uses a binary search to check if each elementof agalloping
smaller setscheme
and usesbinaryto checkif eachelement
the[1],a inwhichsearch
one iterates
over
the elements
is in the bigger set (time 𝑂 (|𝐴| log |𝐵|)). SISA offers both variants,
is inthe bigger
set (time(|𝐴| logsearch|𝐵|)). SISA
offersboth element
variants,
ofa smaller
set anduses 𝑂a binary
to checkif eachand a variant that automatically selects the best variant with aanda variant
automaticallythe offers
best variant
with aisin thebiggerthatset (timeO(|A| log selects|B|)). SISA
both variants,
performance model (described in § 8.2).
performance(described in selects§ 8.2). the best variant with aanda variant modelthat automatically• SA [unsorted or sorted] 𝐴 ∩ DB 𝐵 Iterate over 𝐴 (𝑂 (|𝐴|)) and• performance
SA [unsorted
or sorted]𝐴 ∩ inDB
𝐵 Iterate over 𝐴 (𝑂 (|𝐴|)) andmodel(described§ 8.2).
check if each element is in 𝐵 (𝑂 (1)). This variant is often used tocheck
if each element
is inA𝐵 ∩(𝑂DB(1)).B Thisvariant
used
to
• SA
[unsortedor sorted]
IterateoverisA often(O(|A|))
andintersect a neighborhood with an auxiliary set represented as aintersecta neighborhood
an auxiliary
set representedcheck
if eachelement is in with
B (O(1)).
This variant
is often usedastoa
bitvector, for example 𝑋 ∩ 𝑁 (𝑣) in Listing 1.
bitvector,afor
example 𝑋 ∩with𝑁 (𝑣)aninauxiliary
Listing 1.set represented as aintersectneighborhood• DB 𝐴 ∩ DB 𝐵 Apply bitwise AND over both input DBs (they both• bitvector,
DB 𝐴 ∩ DB
Apply bitwiseAND
bothfor𝐵example
X ∩ N (v)in over
Listing
1. input DBs (they bothhave sizes of 𝑛 bits, giving 𝑂 (𝑛/𝐶) time, where 𝐶 is the maximum
haveA sizes
bits, giving
𝑂 (𝑛/𝐶)
time,bothwhere
𝐶 isDBsthe(theymaximum• DB∩ DBofB𝑛Apply
bitwiseAND overinput
bothchunk of bits that can be processed in 𝑂 (1) time using bit-levelchunkof bits
be O(n/C)
processedin 𝑂(1) time
bit-level
have
sizes
of n that
bits, cangivingtime,
where
C is using
the maximum
parallelism). This variant is used for example when intersecting
parallelism).
is used forin
examplewhenintersecting
chunkof bitsThisthat variant
can be processedO(1) timeusing
bit-level
two dense neighborhoods.
two dense neighborhoods.
parallelism).
This variant is used for example when intersecting
Setdense
Union
𝐴 ∪ 𝐵, Set Difference 𝐴 \ 𝐵 𝐴 \ 𝐵 and 𝐴 ∪ 𝐵 havetwoneighborhoods.
Set Union𝐴 ∪ 𝐵, Set Difference 𝐴 \ 𝐵 𝐴 \ 𝐵 and 𝐴 ∪ 𝐵 havevariants similar to those for ∩, there are also corresponding merge
variants
similarthose∩, there are
Set Union
A to∪ B,
SetforDifference
A \also
B Acorresponding\ B and A ∪ Bmerge
have
and galloping variants.
and galloping
variants
similarvariants.
to those for ∩, there are also corresponding merge
Set Membership 𝑥 ∈ 𝐴, Set Cardinality |𝐴| Set membership
Membership𝑥 ∈ 𝐴, Set Cardinality |𝐴| Set membership
andSetgallopingvariants.
takes 𝑂 (|𝐴|) time for an unsorted SA (linear scan), 𝑂 (log |𝐴|) timetakes(|𝐴|) time forxan∈ unsorted
SA (linear scan),𝑂 (log|𝐴|) time
Set𝑂Membership
A, Set Cardinality|A| Setmembershipfor a sorted SA (binary search), and 𝑂 (1) for a DB (a single accessfor a sorted(1) forscan),a DB O(log(a single
takes
O(|A|) SAtime(binary
for an search),
unsortedand
SA𝑂(linear|A|)accesstime
to verify if 𝑥-th bit is set). As for set cardinality, we keep |𝐴| forto verify
if 𝑥-thbit is set).
As forcardinality,
keep access|𝐴| forfora sorted
SA (binary
search),andsetO(1)for a DB we(a single
any set. This incurs only 𝑂 (1) storage overhead (per set) as wellany
set. This
incurs(1)forstorageoverhead (perset) astoverifyif x-thbit isonlyset).𝑂As
set cardinality,
we keep|A|wellfor
𝑂 (1) time overhead needed to update the size, but it enables 𝑂 (1)𝑂 (1)set.
time
overheadto updatesize, but(perit enables
(1)
any
This
incurs needed
only O(1)storagethe
overheadset) as 𝑂
welltime to resolve any set cardinality operation. Finally, SISA provides
time time
to resolve
any setcardinality
operation.
Finally,providesO(1)overheadneededto updatethe size,but itSISA
enablesO(1)dedicated instructions for computing cardinalities of the results ofdedicated
instructions
for computing
cardinalities
the resultsoftime
to resolve
any set cardinality
operation.
Finally,ofSISA
providesset operations, for example |𝐴 ∩ 𝐵|. This enables speedups as SISA
set operations,for example|𝐴 ∩ 𝐵|. This
enables speedups
as SISA
dedicated
instructions
for computing
cardinalitiesof the resultsofavoids creating any intermediate structures needed for keeping the
avoidscreatingfor
anyexample
intermediate
structuresneededfor keepingthesetoperations,|A ∩ B|.
This enables
speedups
as SISA
results of operations such as intersection.
resultscreatingof operations
such as intersection.
avoidsany intermediate
structures needed for keeping the
Adding & Removing Elements Auxiliary sets often grow andAdding& Removing
Auxiliary sets often grow andresultsof operations
such Elements
as intersection.
shrink by one element. Both add and remove straightforwardly
shrinkby oneelement. Bothadd andremovesets
straightforwardly
Adding& Removing
Elements
Auxiliaryoften grow andtake 𝑂 (1) time for a DB (setting or zeroing a corresponding bit) andtake 𝑂 (1)for a DB (settingor zeroinga correspondingbit) andshrinkby timeone element.
Both add
and remove
straightforwardly
𝑂 (|𝐴|) for an SA (moving data for a sorted SA). Thus, in general,
𝑂 (|𝐴|)
fortimean SAdataorforzeroinga sortedSA). Thus, in general,
take
O(1)
for (moving
a DB (setting
a correspondingbit) and
we advocate using DBs for auxiliary sets; the size is 𝑛 bits.
we advocate
DBs fordata
auxiliary
sets; thesizeThus,
is 𝑛 bits.
O(|A|)
for an using
SA (moving
for a sortedSA).
in general,weadvocate
using
DBs
for
auxiliary
sets;
the
size
is
6.3 Additional Details of SISA Design n bits

6.3

Additional Details of SISA Design

We detail several aspects of SISA’s design; cf. Figure 3.
We detailseveral aspectsof SISA’s
cf. Figure 3.
6.3
Additional
Detailsof design;
SISA
DesignLabeledGraphs As
a baseline,
we propose
to use a sparseLabeledGraphsAs ofa baseline,
we propose
to3.use a sparseWe
detailseveralaspects
SISA’sdesign;cf.
Figurearray to maintain labels, indexed by vertex IDs,
similarly
to otherarraytomaintainlabels,indexedbyvertexIDs,
similarly
to otherLabeledGraphsa baseline,
propose The
to usea sparse
arworks[41]. This
formAsbenefitsfrom weSISA-PNM.
SISA
user can
works
[41].
This
form
benefits
from
SISA-PNM.
The
SISA
user
can
ray to maintain labels, indexed by vertex IDs, similarly to otherSISA: Set-Centric Instruction Set Architecturefor Graph Mining on Processing-in-Memory Systems

Triangle
Triangle
Counting[146]
SISA + merging intersection

MICRO ’21, October 18–22, 2021, Virtual Event, Greece𝑘 -Clique𝑘 -CliqueListing[44]
Counting [146]
Listing [44]𝑂 (𝑚𝑐) ⋆𝑂 (𝑘𝑚 (𝑐/2) 𝑘−2 ) ⋆𝑘 -Star-Clique𝑘 -Star-Clique
Listing[79]

Listing [79]𝑂 (𝑘 2𝑚 (𝑐/2) 𝑘−1 ) ⋆Maximal Cliques

MaximalCliques
Listing [26,51]
Listing [26, 51]
𝑂 (𝑐𝑑𝑛3𝑐/3 )

Link
†
Link
Prediction

Prediction†

𝑂 (𝑚𝑑)

Link‡
Link
Prediction

Link

Jarvis-Patrick§ Clustering [81]Link
PredictionJarvis-Patrick
Prediction§ Clustering [81]𝑂 (𝑛 2 + 𝑚𝑑)
𝑂 (𝑛 2 ) ⋆𝑂 (𝑚𝑑)

Prediction‡

𝑂 (𝑚𝑐) ⋆𝑂 (𝑘𝑚 (𝑐/2) 𝑘−2 ) ⋆𝑂 (𝑘 2𝑚 (𝑐/2) 𝑘−1 ) ⋆𝑂 (𝑐𝑑𝑛3𝑐/3 )𝑂 (𝑚𝑑)𝑂 (𝑛 2 + 𝑚𝑑)
𝑂 (𝑛 2 ) ⋆𝑂 (𝑚𝑑)𝑂 (𝑘𝑚 (𝑐/2) 𝑘−2 log 𝑐) 𝑂 (𝑘 2𝑚 (𝑐/2) 𝑘−1 log 𝑐) 𝑂 (𝑐𝑛3𝑐/3 ) ⋆ 𝑂 (𝑚𝑐 log 𝑐) ⋆ 𝑂 (𝑛 2 + 𝑚𝑐 log 𝑐) ⋆ 𝑂 (𝑛 2 ) ⋆ 𝑂 (𝑚𝑐 log 𝑑) ⋆SISA + galloping intersection 𝑂 (𝑚𝑐 log 𝑐) 𝑂 (𝑘𝑚 (𝑐/2) 𝑘−2 log 𝑐) 𝑂 (𝑘 2𝑚 (𝑐/2) 𝑘−1 log 𝑐) 𝑂 (𝑐𝑛3𝑐/3 ) ⋆ 𝑂 (𝑚𝑐 log 𝑐) ⋆ 𝑂 (𝑛 2 + 𝑚𝑐 log 𝑐) ⋆ 𝑂 (𝑛 2 ) ⋆ 𝑂 (𝑚𝑐 log 𝑑) ⋆Table 5: The impact of set intersection schemes (merging vs. galloping) on the runtime of graph mining algorithms.. “⋆” means that a given SISA variant matches asymptotically the best known
Table 5: The impact of set intersection schemes (merging vs. galloping) on the runtime of graph mining algorithms.. ““⋆”” means that a given SISA variant matches asymptotically the best known
non-set-centricbaseline, referenced in the top row. 𝑘 , 𝑐 , and 𝑑 denote the size of the mined pattern, the graph degeneracy (a popular measure of graph sparsity) and the maximum vertex degree, respectively
non-set-centric baseline, referenced in the top row. k
𝑘 , 𝑐c , and 𝑑d denote the size of the mined pattern, the graph degeneracy (a popular measure of graph sparsity) and the maximum vertex degree, respectively(other symbols
are described in Section 2). Link prediction complexities are valid for the following vertex similarity measures: † Jaccard, Overlap, Adamic Adar, Resource Allocation, Common Neighbors; ‡ Total(other symbols are described in Section 2). Link prediction complexities are valid for the following vertex similarity measures: † Jaccard, Overlap, Adamic Adar, Resource Allocation, Common Neighbors; ‡ Total§
Neighbors;
Preferential
Attachment
[98,
121].
§
Neighbors; Preferential Attachment [98, 121].
SISA + merging intersection

SISA + galloping intersection

𝑂 (𝑚𝑐 log 𝑐)works [41]. This form benefits from SISA-PNM. The SISA user canalso implement
labels
withwitha one-hotencoding
alsolabelsaa one-hot
encoding
and
use
bit
vectors.
also implement
implementlabelswith
one-hot
encodingand
anduseusebitbitvectors.
vectors.
wouldharness
SISA-PUM.
This This
would
harness
SISA-PUM.
This would harness SISA-PUM.
Instructions
SISA
offersinstructionsthat
thatpackage
packagethe
the
SISASISA
Instructions
SISA
offersinstructions
SISA
Instructions
SISA
offersinstructions
thatpackagethedescribed
set
operations
in
all
the
consideredvariants,
includingdescribed
set
operations
in
all
the
consideredvariants,
includingdescribed set operations in all the considered variants, including
instructions
thatautomaticallyselectmergeororgalloping
gallopingset
alinstructions
thatthat
automaticallyselectmerge
gallopingset
alinstructions
automaticallyselectmerge
setalgogorithms
(cf.
§
6.2).
Finally,
SISA
also
providesinstructionsforrithms(cf.
(cf.§§ 6.2).
6.2). Finally,
SISA
alsoalso
providesinstructions
for creating
gorithms
Finally,
SISA
providesinstructions
forcreating
anddeleting
and anddeleting
sets.
creating
deleting
sets.sets.
Programming
Interface(Set Iterators& Wrappers)
For proFor
proProgramming
Interface
Iterators
Wrappers)For
Programming
Interface(Set(Set
Iterators&&
Wrappers)
programmability,
SISA
offersaa thinsoftware
layer
on
top
of
high-levelgrammability,
SISA
offersthin
software
layer
on
top
of
high-levelgrammability, SISA offers a thin software layer on top of high-level
instructions
that consistsofandwrappers.
theforinstructions
consistsof abstractions
abstractions
andwrappers.InIn
Inthe
theforforinstructions
thatthatconsistsof abstractions
andwrappers.
mer,
we
provideanopaque
type
Set
that
is
a
reference
to
a
SISA
set;
mer,
we
provideanopaque
type
Set
that
is
a
reference
to
a
SISA
set;
mer, weprovide an
opaque type
Set that sets,
is a reference
to a SISA
set;
this
this enables
enables using
using C++C++ iterators
iterators over
over sets, see
see leftleft side
side ofof Figure
Figure 3.
this enables
using C++provides
iterators over sets,
see left sideof Figure
3.3.
In
In thethe latter,latter, SISA
SISA provides functions
functions thatthat directly
directly map
map toto SISASISA set
set
In theinstructions.
latter, SISA provides functions that directly map to SISA set
instructions.
instructions.
SISA cancan bebe integrated
integrated with
with theRISC-V
RISC-V Compliant
Compliant Encoding
Encoding SISA
theSISA canbeflexibility,
integratedSISA’s
with newthe
RISC-V
RISC-V
ISA
enableand
RISC-VCompliant
ISA [166].
[166]. To
ToEncoding
enable modularity
modularity
andflexibility,
SISA’snew
instructions
using
opcode[165].
We
RISC-VISA [166].are
Toencoded
enable modularityand flexibility,
SISA’sinstructions
areencodedusing thethe custom
customopcode setset[165].newWe
encodetheopcodeandfunctionalityofcustomRISC-V
instructions
instructions
areencodedusing
thecustomopcodeset[165].
We
encode the opcode and functionality of custom RISC-V instructions
using[31..25][6..0],
5.
formerrepresent
encodethebits
opcodeandandfunctionalityof custom
using
bits
[31..25]
and[6..0], see
see Figure
Figure5. TheTheRISC-V
former instructions
represent thethe
SISA
instructions
(up
to
are
set
to
usingdifferent
bits [31..25][6..0], see
5. TheThe latter
formerdifferent
SISA and
instructions(upFigureto 128).
128).
Thelatterarerepresent
set toto 0x16
0x16thetorepresent
customof
instruction.
Fieldsrepresent
thecustom characteristic
characteristicof thetheinstruction.
Fieldsrs1,
different
SISA theinstructions(up to 128). The
latterare set to
0x16rs1,
tors2,
indicateregisters
IDs
of
input
the
rs2, andandrd
indicateregisters withwithofIDsof instruction.
input sets
sets andandFields
the output
outputrepresent
therdcustomcharacteristic
the
rs1,
set,
respectively.
In
Table
4,
we
assign
ISA
codes
(bits
[31..25])
toset, respectively.
In Table 4,
we IDsassign
ISA codes[31..25])tors2, andrd indicate registers
withof inputsets (bitsand theoutputrespective
instructions.
The
numberof
SISA
instructionsislessrespective
instructions.
The
numberof
SISA
instructionsis
lessset, respectively. In Table 4, we assign ISA codes (bits [31..25]) to
thanleavingfornewvariants.
than 20,
20,
leaving space
spaceThefor potential
potential
newvariants.
respective
instructions.
number of
SISA
instructions is lessBit index
than 20,
for19 potential
7 6
12 11
31 leaving
0
25 24space 20
15 14new13variants.
funct7

rs2

rs1

Bit index
5 19
515#bits:257 24
20
31
SISA operation
SISA source. rs2
funct7
rs1
identiﬁer. Support
operands
up to 1285
#bits: 7 for
operations5

SISA operation.
identiﬁer. Support
for up to 128
operations

xd

xs1

xs2

1 13 1 12 1 11
Set to "1" if
xd SISAxs1usesxs2
theregister operands

14

rd

opcode57
7 6
0
Custom
SISA
rd
opcodeinstruction
destination
opcoderegister

1
1
1
5
Set to "1" if
SISA
SISA source
SISA
Figure 5: Encoding
ofusesSISA theinstructions.
destination
operands
registeroperands
Figure 5: Encodingof SISA
instructions.register

7
Custominstruction
opcodeOther set operations on SAs that employ streaming or random

8.1
SCU
Automatizing
Decisionsaccesses
are&also
executed using SISA
small in-ordercores.
8.1
SCU&
Automatizing
SISA
Decisions
We use a small SISA Control Unit (SCU), cf. Section 3, to automat-

Figure 5: Encoding of SISA instructions.

7 THEORETICAL ANALYSIS

We
We now
now showshow thatthat SISA-enhanced
SISA-enhanced algorithms
algorithms areare theoreticallytheoretically effieffi-

cient,
match
7 THEORETICALANALYSIS
cient, i.e.,
i.e., their
their time
time complexities
complexities
match those
those ofof hand-tuned
hand-tuned graphgraph

miningalgorithms.
Thisbyabilitytominingalgorithms.
This isis enabled
enabledby SISA’s
SISA’s are
ability
to control
control used
used
We now
showthat SISA-enhanced
algorithms
theoreticallyeffisetrepresentationsandsetoperations.
To
show
this,
we analyze
analyzeand set operations.
To show
this, wecient,seti.e.,representations
their time complexities
match thoseof hand-tuned
graph
how
varying
set intersection
variant(mergevs.
howvarying aa used
used
intersection
variant(mergevs. galloping)galloping)miningalgorithms.
This setis enabled
by SISA’sability
to control
used
impacts
impacts thethe runtime
runtime ofof set-centric
set-centric algorithms,
algorithms, see
see Table
Table 5.
5. We
We focus
focus
set representationsandsetoperations.
To
show
this,
we
analyzeonon intersection
intersection as
as it
it is
is prevalentprevalent inin considered
considered algorithms.
algorithms. CruCruhow cially,varying aset-centricused set intersection
variant(mergecompetitive
vs. galloping)cially, all
all set-centric variantsvariants areare ableable toto matchmatch thethe competitive time
time
impacts
the runtime
of set-centric
seealgorithms.
Table 5. We focus
complexities
of
tuned
graph
complexities
of considered
considered
tunedalgorithms,
graph mining
miningalgorithms.
on intersection as it is prevalent in considered algorithms. Crucially,8 all HARDWARE
set-centric variants
are able to match the competitive time
IMPLEMENTATION
complexitiesofconsidered
tunedgraphunion,
miningSISA-PUM First,
First, thethe intersection,intersection,
union,
andalgorithms.
difference of sets rep-8

resented as DBs are processed with SISA-PUM that relies on in-situ

HARDWARE
IMPLEMENTATIONDRAM bulk bitwise schemes.
For concreteness, we pick Ambit [141],SISA-PUM First, the intersection, union, and difference of sets represented as DBs are processed with SISA-PUM that relies on in-situ
DRAM bulk bitwise schemes. For concreteness, we pick Ambit [141],

DRAM bulk bitwise schemes. For concreteness, we pick Ambit [141],
recent design
designthat
thatenables
enablesenergy-efficient
bitwiseoperaaa recent
energy-efficientbulk
bitwiseoperarecent
designthat
enablesenergy-efficientbulkbulk
bitwiseoperations
fully
inside
DRAM,
by
small
extensions
to
the
DRAM
circuitry
tions
fully
inside
DRAM,
by
small
extensions
to
the
DRAM
circuitrytions fully inside DRAM, by small extensions to the DRAM circuitry
but
the
DRAM
interface.
However,
SISA
isbut without
withoutanyanychanges
changesto
DRAM
interface.
However,but
withoutanychanges
toto
thetheDRAM
interface.
However,
SISASISA
is is
generic
andotherdesigns
could
also
be
used
(e.g.,
ELP2IM[168],
generic
andotherdesigns
could
also
be
used
(e.g.,
ELP2IM[168],
generic and other designs could also be used (e.g., ELP2IM [168],
DRISA
[53],
PCM
(Pinatubo)[101]).
The
key
DRISA[100],[100],ComputeDRAM
ComputeDRAM
[53],
PCM
(Pinatubo)[101]).
DRISA[100],
ComputeDRAM
[53],
PCM
(Pinatubo)[101]).
The Thekey keyextension
processing)isaa decoder
extension
in
Ambit
(for
in-situprocessing)is totoismodify
modifydecoder
extensionin
inAmbit
Ambit(for(forin-situ
in-situprocessing)
to modify
a decoderforthreeselected
DRAM
rows
(that
share
the
same
set
for three
(that
share
thethesame
set ofof
sensethreeselected
selectedDRAM
DRAMrows
rows
(that
share
same
setsenseof sense
amplifiers)in such aa waythat one
amplifierconnects
directly
toamplifiers)
one
amplifierconnects
directly
to toamplifiers)ininsuch
such away
waythatthatone
amplifierconnects
directly
threeDRAM
cells.
This
enables
logical
AND
and
OR
over
two
of
three
DRAM
cells.
This
enables
logical
AND
and
OR
over
two
of of
three DRAM cells. This enables logical AND and OR over two
such
three
rows,
immediately
computingtheresult
in
the
third
such
three
rows,
immediately
computingtheresultinthethirdsuch(NOT
threeisrows,
immediately
computingthe ofresult in the thirdrow
byaa single
row
row
(NOT
isisprovided
providedbybyincluding
includingsinglerowrowof dual-contact
dual-contactrow(NOT
providedincludingasingleof dual-contact
DRAM
DRAM cells
cells [141]).
[141]). Importantly
Importantly forfor SISA-PUM,
SISA-PUM, only
only three
three selected
selected
DRAM cells[141]).
Importantly
for
SISA-PUM,
only
three
selected
designated
DRAM
rows
(per
singleDRAM
subarray)aredesignated DRAM rows (per single DRAM subarray) are modified
modified
designated
DRAM rows(per single
DRAM
subarray)
arememmodified
this
way.
Whenevertherunningcode
requestsanin-situ
this way. Whenever the running code requests an in-situ memthisoperation,
way. Whenever
the running
code requests
an in-situ
memoryAmbit
ory operation,
Ambit uses
uses aa recent
recent RowClone
RowClone technology
technology [140][140] totoory operation,
Ambit
usesthata recent
RowClone[140] to
copy
(also
the
store
sets
these
copy
(also in-situ)
in-situ)
the rows
rows
that
store input
input
sets tototechnology
these two
two desigdesignatedrows,
computetheresultin-situ,againuse
copy (alsostoreand
input
sets
toRowClone
these twoto
natedrows,in-situ)
computethe
therows
resultthat
in-situ,
and
again
use
RowClone
todesigcopy
theresulttothedestination(unmodified)
DRAM
row.
Now,
nated
rows,
computetheresultin-situ,
and
again
use
RowClonecopy the result to the destination (unmodified) DRAM row. Now, to
SISA-PUM
uses
execution
andwithout
copy the result
to the destination(unmodified)DRAM
row. Now,
SISA-PUM
uses Ambit’s
Ambit’s
execution model
model
and interface
interface
withoutany
modifications:
set
and
union
are
SISA-PUM
uses Ambit’s
executioninterfacewith
withoutany
modifications:set intersection
intersection
andmodelunion andare processed
processed
with
an
AND
OR,
respectively.
Set
processed
anin-situAND andand setOR,intersection
respectively. and
Set difference
difference
isprocessed
processedwith
anyin-situ
modifications:
union areis
using
set
along
with
set
rule:
using
set intersection,intersection,
alongrespectively.
with thethe well-known
well-known
set algebra
algebrarule:
an in-situ
ANDand OR,Set difference
is processed′ [82].
𝐴
\
𝐵
=
𝐴
∩
𝐵
′
A
\ B =setA∩
B [82].
usingintersection,
along with the well-known set algebra rule:A set
set operation
operation with
with nono bulk
bulk bitwise
bitwise processing
processing uses
SISA-PNM A
uses
𝐴 \SISA-PNM
𝐵 = 𝐴 ∩ 𝐵 ′ [82].
SISA-PNM
that
reliesonhighbandwidth
betweenprocessing
units
SISA-PNM
that
reliesonhighbandwidth
betweenprocessing
units
AUPMEM
set operation
with[83],
no bulk
bitwise [6]).
processing uses
SISA-PNM
and
DRAM
in
[96],
HMC
Tesseract
and
DRAM (as(asin relies
UPMEM
[96],
HMC
[83], ororbetween
Tesseractprocessing[6]). Adding
Addingunits
SISA-PNM
that
on
high
bandwidth
or
∪ {x
{𝑥 },
}, 𝐴
or removing
removing anan element
element fromfrom aa set
set stored
stored as
as aa DBDB (𝐴(A ∪A \\ {𝑥{x })})and DRAM (asin UPMEMDRAM[96], HMC [83],or Tesseract[6]). Addingisis conductedconducted with
with aa single
single DRAM access
access toto aa specificspecific memory
memory cell.
cell.
or removing
an elementSAs
from a set
stored as a DB (𝐴 or∪ {𝑥 }, 𝐴 \ {𝑥 })Other
Other set
set operations
operations on
on SAs thatthat employ
employ streaming
streaming or random
randomisconducted
withasingleDRAM
accesstoaspecific
accessesarealso
executed
using
small
in-ordercores.
accesses are also executed using small in-order cores. memory cell.

288

We
usedecidea small
Control Unit
(SCU),
Section
3, to automaticallyonSISA(1) selecting
the PNM
orcf.
PUM
execution,and (2)8.1 decide
SCU&(1)
Automatizing
Decisions
icallyonselectingorPUMand (2)merge
orgalloping.
Once the the
hostPNM
coreSISA
decodes
aexecution,
SISA instruction,
merge
Once
theSCU
host
core
decodesa SISA
instruction,
it passes
to theSISA
SCU.
The
further
decodes
this instruction,Weuseoraitgalloping.
smallControl
Unit(SCU),
cf. Section
3, to automatit
passes
it
to
the
SCU.
The
SCU
further
decodes
this
instruction,
and
picks
either
PNM
or
PUM
to
executetheinstruction.
For deically decide on (1) selecting the PNM or PUM execution,and (2)andpicks either
PNMeitheror PUM
to execute
theinstruction.
For deployment,
SCU could
be added
to theCPUora tothe instruction,
DRAM
merge or galloping.
Once thehost core
decodes
SISA
ployment,
SCU could
eitherdiscussion
be added totheinCPUto the DRAM
circuitry (seelaterthisorsection),or – toit passes it tothe
thefeasibility
SCU. TheSCU further
decodes
this instruction,
circuitry
feasibility discussion
laterbeinemulated
this section),– toavoid any(seeHWthe
modifications– it can also
by aorsingleand picks
either
PNM or PUM
to executethe instruction.
For deavoid
any HW
modifications
it canalso does
be emulated
by a single
designatedin-orderlogic layer– core.
SCU
not implement
anyployment,
SCU
could
either
be
added
to
the
CPU
or
to
the
DRAM
designatedin-orderlogic layer
SCU does not
implementcomplex logic(e.g., dynamic
setcore.
modifications),
it only
decidesany
oncircuitryof(seethediscussion
later initthis
or – tocomplexlogic(e.g.,feasibility
dynamic
set
modifications),
onlysection),
decides onvariants
schemes
to execute.
avoid
any
HW
modifications
–
it
can
also
be
emulatedbyasinglevariants
of schemes
to execute.First, SCU decides whether to use
SISA-PUM& SISA-PNM
designatedin-order
logic
layer
core.
SCU
does
not
implement
SISA-PUM&SISA-PNMFirst,
SCU
decideswhethertouse
SISA-PUM or SISA-PNM for given two sets. This decision is simple any
complexlogic(e.g.,sets
dynamic
set two
modifications),
it only
SISA-PUM
oronSISA-PNM
for represented
given
sets.
decision
isis decides
simpleandis basedhoware(thisThis
information
stored on
andbased
on how setsare(“set
represented(thisstructure
information
storedvariants
ofin-memory
schemes
toSM
execute.
in a issimplemetadata”)
and ispossiblyinaSISA-PUM
simplein-memory
SM (“set metadata”)
possibly
cachedin SCU’scache).
&
SISA-PNMFirst, SCUstructure
decides andwhether
to usecachedin SCU’scache). for given two sets. This decision is simple
SISA-PUM
or SISA-PNM

and is based on how sets are represented (this information is stored
in a simple in-memory SM (“set metadata”) structure and possibly
cached in SCU’s cache).

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

Variants of Set Operations Second, SCU automatically detects
if it is best to use merge or galloping, and processes input setsusing the corresponding variant. This decision is guided by our
performance models.

8.2

Performance Models for Set Operations

The runtime of each SISA instruction variant is dominated by either
streaming or random accesses.
Streaming takes place when two sets A and B stored as SAs
are processed using merging. We model the runtime as l M + W ·max{|A|, |B|} · min{b M , b L }. l M and b M are latency and bandwidthof accessing DRAM, and b L is bandwidth between cores. The model
conservatively assumes that A and B may be located in memory
locations attached to different cores (e.g., in different vaults), andthus (1) the overall bandwidth is bottlenecked by min{b M , b L }, and(2) we can use max{|A|, |B|} as A and B are streamed in parallel.
To model random accesses, we simply count the number of
performed operations and multiply it by the memory access latency.
This gives l M · min{|A|, |B|} · log(max{|A|, |B|}) for a binary searchover the larger of input sets, used when processing two SAs withgalloping. Then, a specific variant is selected automatically tominimize the predicted runtime. To parametrize these models,SISA needs (1) the sizes of processed sets, (2) their representation
types, and (3) b M , b L , l M . (1) and (2) are maintained in the metadata
structure. (3) describe the execution environment and are thus identical for each set; they are stored directly in the SCU. We instantiate(3) to reflect logic layers in Tesseract [6].

8.3

Details of SISA Hardware

Life Cycle of a Set A set is allocated with a standard malloc, augmented with setting the appropriate set information in the set
metadata (SM) structure. Loading, processing, and storing sets is
conducted by the respective existing elements such as logic layer
cores; the SCU is only responsible for selecting the appropriate instruction variant to be executed. Once a set is deleted, the standard
free call is used, together with removing the respective entry fromthe SM structure.
Set Metadata SM forms a simple associative structure that holds
constant amount of data per set (set representation, set size). The
total SM size is O(n) as there are n neighborhoods and a constantnumber of auxiliary sets. Thus, while we conservatively assume that
SM is an in-memory structure, in practice it fits completely in cache
or a small scratchpad. This is because many datasets processed bygraph mining algorithms have small n, in the order of hundreds or
thousands [132]. These graphs pose computational challenges, butthese challenges come from high computational complexities (e.g.,
listing maximal cliques is NP-hard) or from relatively high edge
counts m (as some vertices may have high degrees [132]), but not(or to a smaller extend) from n. Whenever the given SM information
is not cached, there is a single additional memory access for one set
operation. Each SM entry describing one set also contains the set
location. Now, entries in the SM structure are indexed by set IDs.
A set ID is returned by a function creating a set, cf. Figure 3. Set
IDs and set creation (and destruction) calls are used by a developer
analogously to pointers and malloc/free calls.

289

Caching Set Metadata Depending on how SISA HW is deployed, the SM information can be cached in either a small dedicatedscratchpad or cache (if the SCU is implemented as an additional
circuitry), or in the standard cache of a logic layer core (if the SCU
is emulated by a such designated core).
SISA-PNM and SISA-PUM Together Ambit fully preserves
the DRAM interface: the sets are always stored in standard DRAM
rows, and moved to the designated rows only for bulk bitwise processing [141]. SISA-PNM accesses run on unmodified DRAM banks(the modifications in PNM are only related to the high bandwidth,
and the SCU in SISA). Thus, SISA-PNM and -PUM are seamlessly
used together.
Harnessing Parallelism First, bit-level parallelism is enabled
by using Ambit’s bulk bitwise operations: bits in a row are ANDedor ORed in parallel. Second, pairs of bitvectors placed in different
subarrays (or, e.g., DRAM banks) can be processed in parallel. Third,
processing pairs of sets stored as integer arrays in different vaults
can also be parallelized. Here, SISA benefits from the same effect of
bandwidth scalability as the Tesseract graph accelerator [6].
Managing Concurrency SISA relies on developers using established techniques (locks, lock-free protocols, general parallel
programming principles [71] and libraries such as OpenMP [32])to concurrently access the same set.
For cache coherence in SISA-PUM, we rely on mechanisms(provided by the memory controller) that flush dirty cache lines insource rows, and invalidate cache lines in destination rows. Existing
schemes also rely on it, including Ambit [141], DMA accesses [40]and others [75, 140]. As in Ambit, SISA-PUM accesses are always
row-wise, and thus we can also rely on Dirty-Block Index [139] andsimilar schemes for fast data flushing. Invalidations run in parallelwith Ambit operations and thus do not incur overheads.
Memory Layout and Storage of Sets We ensure that storing
SISA sets is feasible (i.e., a maximum-size neighborhood, represented as SA or DB, fits into a single vault).

8.4

SISA Hardware Cost and Feasibility

We also briefly discuss the hardware cost. First, the needed DRAM
chip modifications are minimal and identical to those already discussed in Ambit. Second, as the logic to be implemented in SCU
is straightforward decision making on what instruction variant touse, its costs are not prohibitive, as shown by many designs proposed in the past, for example in HyVE [76] (a hybrid vertex-edge
memory hierarchy that uses ReRAM and DRAM) or in GraphH [43](an accelerator that combines HMC with SRAM). Third, the code of
all SISA instructions is also straightforward: a simple binary search(galloping), merging of two arrays (merge), or setting/clearing a
DRAM cell (set element add/remove). Thus, they can be triviallydeployed in in-order cores in the logic layer of 3D stacked DRAM,
as shown by other designs [43].

9

EVALUATION

We illustrate example performance advantages from SISA.

9.1

Methodology, Setup, Parameters

Simulation Infrastructure We use Sniper [70] with the Pin frontend [106]. Sniper is a popular cycle-level simulator used in many

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

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

works proposing various architectural extensions for both CPUs
andmemorysubsystem
160].
works
proposingvarious[116,architecturalextensions for both CPUs
Implementation
We160].
simulate the SISA HW design andandSISA
memorysubsystem [116,theSISAISA, Implementation
instrumenting the Wecode
so that thethe SISA
simulation
toolchainsimulate
HW designandcandistinguishbetweenSISA
andnon-SISA
instructions.
To modelthe ISA, instrumenting the code so that the simulation toolchain
each
componentbetweenof SISA, SISA
we addrespective
set instructions
andcan distinguishandthenon-SISA
instructions.
To modelsimulate
the SCUof(aSISA,
smallwe
fixed
the cache
SCU (with andtheeach component
adddelay),
the respective
setininstructions
LRU
policy),(randomsimulate
the theSCUSM(a structuresmall fixed
delay),memory
the cacheaccesses
in SCUwhenever(with thethecachetheis notand theexecutionof all used
set operations
LRUSCU
policy),SM hit),structure(randommemoryaccesses
wheneverbyin andthe thesimulation
execution.
theappropriate
SCU cache isdelays
not hit),executionof all usedFor
setoperations
operations
based
on streaming
randommemoryaccesses,
use theby appropriatedelaysandin thesimulation
execution.
Forwe
operations
performancemodels describedin § memory
8.2. To simulate
SISA-PUM,
webased on streaming
and random
accesses,
we use themodelarun-timeofin-situ
operations
with
a
delay
𝑙
+𝑙
·
⌈𝑛/(𝑞𝑆)⌉;
𝑀
𝐼
performance models described in § 8.2. To simulate SISA-PUM, we𝑙modellatency to(to initiate
the operation)and 𝑙𝐼
𝑀 is thea run-timeof accessin-situ DRAM
operations
with a delayl M +l I · ⌈n/(qS)⌉;
islatency
executeone in-situ⌈𝑛/(𝑞𝑅)⌉modelsal Mtheis thelatencyto access
DRAMinstruction.
(to initiate theoperation)andscenario
when thebitvector
𝑛 exceeds
the sizeof all models
DRAMl I is the latency
executeone size
in-situ
instruction.
⌈n/(qR)⌉
rows
that canbe processedin parallel.
𝑞 is the the
count
ofof
rows
withina scenario
when
the bitvector
size n exceeds
size
all DRAMarows
bankthatthat
canused in parallel
andq 𝑅isisthe
thecount
size ofof rows
one row.
canbebe
processedin parallel.
withinSISAthat
Platform& Parameters
ForRconcreteness,
we row.
set thea bankcan be usedin parallel andis the size of one
platformfor executing
SISA instructions
to match Tesseract[6]
SISA Platform& Parameters
For concreteness,
we set the(for
SISA-PNM)
and
Ambit
[141]
(for
SISA-PUM).
The
formerhas
platform for executing SISA instructions to match Tesseract [6]simplein-order cores(1 core/vault
in itslogic layer)Thewith
32 KBhas
L1(for SISA-PNM)
and Ambit[141] (for
SISA-PUM).
formerinstruction/datacaches,no L2, 16 8GB(128 GBin total),
simple in-order cores(1 core/vault
in itsHMCs
logic layer)
with
32 KB 32
L1
vaults/cube,
16 banks/vault.
Eachoffers (128
16 GB/sof total),memoryinstruction/datacaches, no L2,
16 vault
8GB HMCs
GB in
32
bandwidth
itsbanks/vault.
core. Thus, we
assumeas provaults/cube,to16
Eachvault scalable
offers 16bandwidth
GB/s of memory
posedby Tesseract:
using
more
vaults increases
the total memory
bandwidth
to its core.
Thus,
we assumescalable bandwidth
as probandwidth.
We set the
DRAM
rank
size tothe
8 KB,
posed by Tesseract:using
more rowvaultsincreases
totalfollowing
memoryAmbit[141]. We
Next,
setDRAM
the parameter𝑡 ∈size[0; 1]
thebandwidth.
setwe
the
row rank
to(that
8 KB,controls
followingbias
towards
using we
DBssetortheSAs
to store neighborhoods)
to 0.4 (i.e.,Ambit[141]. Next,
parametert ∈ [0; 1] (that controls
the40%
neighborhoods
storedas DBs);we also analyze
bias oftowards
using DBsareor SAsto storeneighborhoods)
to 0.4other(i.e.,
values.
We ensure that are
the stored
total storageused
40% of neighborhoods
as DBs);we foralsoneighborhoods
analyze otherdoes
notexceed
the
size
of
the
simpleCSR
graphby morevalues. We ensure that the total storage used forstorage
neighborhoods
thanFinally,thewesizeset ofthethesizeof SISA
SCU’s
to be
KB
does 10%.
not exceed
simpleCSRgraphcachestorageby32
more(matching
Tesseract’s
L1).the size of SISA SCU’s cache to be 32 KB
than 10%. Finally,
we setPlatform
for non-SISA(matching
Tesseract’s
L1). Instructions & Baselines For any
non-SISA
instructions
and baselines,
we use&aBaselines
high-performance
Platform for non-SISA
Instructions
For any
Out-of-OrdermanycoreandCPU.
Each corewe
hasusea 128-entry
instruction
non-SISA instructions
baselines,
a high-performancewindow,a branchpredictor,
KBcoreL1 instruction/datacaches, a
Out-of-Ordermanycore
CPU. 32
Eachhas a 128-entry instruction
256
KB L2acache.
cores sharean 8L1MBL3 cache. Therecaches,is also aa
window,branchAll
predictor,
32 KB
instruction/data
four-way
associative
64-entry
D-TLB,a128-entry
I-TLB,
anda 512256 KB L2 cache. All cores share an 8 MB L3 cache. There is alsoaentry
S-TLB.
For fair comparison,
we alsouse bandwidth
four-way
associative
64-entry D-TLB,
a 128-entry
I-TLB, scalability
and a 512in
thisS-TLB.
configuration,i.e., we increase
the memory
bandwidth
with
entry
For fair comparison,
we alsouse bandwidthscalability
thenumberof cores, matching
it with thatof SISA-PNM.
in thisconfiguration,i.e., we increase
the memory
bandwidth with
MiningProblems
graphmining problems wetheConsidered
number of cores,
matching
it withThe
thatof SISA-PNM.
considerare clustering
with
the Jaccard
overlap(cl-ovr),
Considered
MiningProblems
The(cl-jac),graph mining
problems
weandtotal areneighbors(cl-tot)coefficients,
listing 𝑘-cliques(kcc-𝑘,considerclusteringwith theJaccard (cl-jac),overlap (cl-ovr),
𝑘and
∈ {4,
5, 6}),
𝑘-clique-stars𝑘 ∈ {4,listing5, 6}), k-cliques
maximal (kcc-k,
cliquestotalneighbors(cl-tot)(ksc-𝑘,coefficients,(mc),
triangles(tc), and subgraphisomorphism(si-𝑘sfor 𝑘-stars).
k ∈ {4,5, 6}), k-clique-stars(ksc-k,k ∈ {4, 5, 6}),maximalcliquesComparison
Targets:
Hand-Tuned
Algorithms
Our
most
(mc),
triangles (tc),and subgraphisomorphism(si-ks for
k-stars).
important(the mostchallenging
to outperform)baselinesOur
are handComparison
Targets:
Hand-Tuned
Algorithms
most
optimized
algorithms
for eachgraph mining
problem.
important parallel(the mostchallenging
to outperform)baselines
areSpecifhandically,
we usea tunedalgorithms
version fromGAP
Benchmark[14]
optimized
parallelfortheeach
graphminingSuite
problem.
fortc, Eppstein’s
versionof BK
for mcfrom[51],theDanisch’scheme forSpecifically,
we usea tunedversionGAP Benchmarkkcc-𝑘[44],forenhanced
Jabbour’sschemeforforksc-𝑘[79],Danisch’parallelSuite [14]tc, Eppstein’s
versionof BK
mc [51],
VF2
for
si-𝑘s
[41],
and
cl-jacbasedoncounting
triangles
thescheme for kcc-k [44], enhanced Jabbour’s scheme for ksc-kin[79],
GAP
suite
[14].
used[41],baselines
have competitive
work and
depth
parallelVF2
for Allsi-ks
and cl-jac
based on counting
triangles
complexities,
cf. [14].
TableAll
5. usedFor faircomparison,
all baselines
benefitin the GAP suitebaselines
have competitive
work
anddepth complexities, cf. Table 5. For fair comparison, all baselines

290

from the high bandwidth of PIM. We consider algorithms that do
notexplicitly
usehigh
set algebra(denotedwithand their
benefitfrom thebandwidthof PIM.
We _non-set)consider algorithms
set-centricwith _set-based).
that do not variants
explicitly(denoted
use set algebra(denoted with _non-set) andComparison
Targets:(denoted
Patternwith
Matching
Frameworks SISA
their
set-centric variants_set-based).
andComparison
its underlying
paradigm
do
not
aim
to
outperform
specific
Targets: Pattern Matching Frameworks
SISA
accelerators
but complement
reinforceby offering specifica noveland its underlying
paradigmordo
not aimthem,to outperform
set-centricand building
blocks.them,Thus,byweoffering
focus oncomacceleratorsparadigm
but complement
or reinforce
a novelparingto thefundamental
paradigms/ algebras
set-centricparadigm
and building
blocks.
Thus,that
we underlie
focus onthese
comaccelerators:
expansion/ forpatternmatching
paring to the neighborhood
fundamental paradigms
algebrasthat
underlieimplethesementedin Peregrine[80] (which
represents
GRAMER[176])
andaccelerators:
neighborhood
expansionfor patternmatching
implerelational
implemented
in RStream[161](which [176])
represents
mented inalgebra
Peregrine[80] (which
represents
GRAMER
andTrieJax[89]).
We stress
that, while
we consider
baselinesforrelational
algebraimplemented
in RStream[161]these(whichrepresents
completeness,
we
focus
on
comparing
to(much
faster)hand-tuned
TrieJax [89]). We stress that, while we consider these baselines forparallelalgorithms
for solving
specifictoproblems.
completeness,
we focuson comparing(much faster) hand-tuned
GraphsWe select
input datasets(Table 6) from Netparallel
algorithms
fordifferent
solving specificproblems.
work
Repository[133],different
considering(bio-),6)interaction
GraphsWe select
inputbiologicaldatasets (Table
from Net(int-),brain(bn-),
economics(econ-),
social(soc-),interaction
scientificwork Repository [133], considering biological (bio-),computing(sc-),
discrete-mathand wiktionary(edit-)(int-), brain(bn-),
economics(dimacs-),(econ-), social(soc-), scientificnetworks.
pickgraphs withdifferentand
structuralproperties
computing We(sc-),
discrete-math(dimacs-),
wiktionary(edit-)(low/highmaximum
degree,low/high
degreenetworks. density,
We picksmall/large
graphs withdifferent
structuralproperties
distribution
skew,etc.).
(low/high density, small/large maximum degree, low/high degree
distribution skew, etc.).
Biological. Gene functional associations: (bio-SC-GT , 1.7K, 34K), (bio-CE-PG,
1.8K, 48K), (bio-DM-CX , 4K, 77K), (bio-DR-CX , 3.2K, 85K), (bio-HS-LC,
4.2K, 39K), (bio-SC-HT , 2K, 63K), (bio-WormNetB3, 2.4K, 79K). Human gene
regulatory network: (bio-humanGene, 14K, 9M) (large),(bio-mouseGene, 45K, 14.5M) (large).
Interaction. Animal networks: (int-antCol3-d1, 161, 11.1K), (int-antCol5-d1,
153, 9K), (int-antCol6-d2, 165, 10.2K), (intD-antCol4, 134, 5K). Human contact
network: (int-HosWardProx, 1.8k, 1.4k). Users-rate-users: (int-dating, 169K, 17.3M)(large), (edit-enwiktionary, 2.1M, 5.5M) (large).
Brain. (bn-flyMedulla, 1.8K, 8.9K), (bn-mouse, 1.1K, 90.8K).
Economic. (econ-beacxc, 498, 42K), (econ-beaflw, 508, 44.9K),(econ-mbeacxc, 493, 41.6K), (econ-orani678, 2.5K, 86.8K).
Social. Facebook: (soc-fbMsg, 1.9k, 13.8k). Orkut: (3.1M, 117M) (large),
Scientific computing. (sc-pwtk, 217.9K, 5.6M) (large),
Discrete math. (dimacs-c500-9, 501, 112K),
Table 6: Considered graphs[133]. For each graph, we show its “(#vertices, #edges)”.
Table 6: Considered graphs[133]. For each graph, we show its “(#vertices, #edges)”.

Tackling
Tackling LongLong Simulation
Simulation Runtimes
Runtimes Most
Most benchmarks
benchmarks use
use
relatively
smallgraphsbecause
(1)
we
run
cycle
accurate
relatively small graphs because (1) we run cycle accurate simulasimulations,tions, tracing
tracing all
all memory
memory accesses,
accesses, which
which isis very
very time-consuming,time-consuming,andand (2)(2) thethe considered
considered algorithms
algorithms areare computationallycomputationally hard
hard andandeven
softwarecodesusegraphsmuch
smaller
than
those
used
even software codes use graphs much smaller than those used with
withalgorithms
algorithms such
such asas PageRank
PageRank [44,[44, 51].
51]. Yet,
Yet, even
even this
this isis often
often notnotenoughenough to
to enable
enable finishingfinishing simulations
simulations ofof algorithms
algorithms such
such asas BronBronKerbosch.
Kerbosch. Thus,
Thus, we
we usuallyusually also
also pre-specify
pre-specify aa number
number ofof graphgraphpatterns
tobefound.
Past
work
analogously
handledlong
patterns to be found. Past work analogously handled long simulasimulations
tions graph
graph algorithms
algorithms [6][6] suchsuch asas PageRank
PageRank (limiting(limiting #iteration).
#iteration).
Performance
Performance Measures
Measures && Summaries:
Summaries: We
We focus
focus onon plainplain runruntimes
asrecommendedforparallel
codes
[73]
as
speeduptimes as recommended for parallel codes [73] as speedup may
may bebemisleading
misleading because
because it
it isis higher
higher on
on unoptimized
unoptimized baselines.
baselines. HowHowever,
ever, forfor overview,
overview, we
we also
also summarize
summarize speedups
speedups (following(following [73]),[73]), i.e.,
i.e.,
we
we provide
provide (1)(1) speedups
speedups ofof average
average runtimes
runtimes (“speedup-of-avgs”),(“speedup-of-avgs”),
andand (2)(2) geometricgeometric means
means ofof speedups
speedups ofof allall data
data points
points (“avg-of(“avg-ofspeedups”).
speedups”).

9.2 Discussion of Results

Comparison
Comparison to
to Hand-Tuned
Hand-Tuned Algorithms
Algorithms We
We first
first analyze
analyze runruntimes
times with
with all
all available
available cores,
cores, comparing
comparing SISA
SISA set-centric
set-centric variantsvariants
to non-set-based and set-based hand-tuned parallel baselines that

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

In each plot, (1) SISA speedup over non-set ("avg-of-speedups"), (2) SISA speedup over non-set ("speedup-of-avgs"),(3) SISA speedup over set-based ("avg-of-speedups"), (4) SISA speedup over set-based ("speedup-of-avgs"),
we show
respectively: "avg-of-speedups" and "speedup-of-avgs" are different ways to derive summaries, explained at the end of Section IX.A
Note that these are not the equivalent arithmetic and geometric means, and thus do not satisfy the inequality of means
5
4
3
2
1
0
2.5
2.0
1.5
1.0
0.5
0.0

cl−jacSISA speedups:
2x, 1.4x, 2.2x, 2.4x

3

kcc−4

SISA speedups:
6.36x, 21x, 1.5x, 1.46x

kcc−5

SISA speedups:
9.3x, 29.6x, 2.4x, 3.5x

2
1

SISA speedups:
10.8x, 29x, 2.5x, 4.3x

4

kcc−6

2
0

Timeout

Timeout
Timeout

Timeout

Timeout

SISA speedups:
2.4x, 5.6x, 3.8x, 8.9x

Non-set almost
always timeouts

25

mc

50

SISA speedups:
1.8x, 1.6x, 3.8x, 9.7x

ksc−6

75

ksc−5

SISA speedups:
3.3x, 2.3x, 3.6x, 1.04x

10
0
50
40
30
20
10
0
100

Timeout

020

Timeout

Timeout

530

Timeout

SISA speedups:
4x, 8.6x, 3.8x, 4.9x

Timeout10

ksc−4

Runtime [Millions of cycles]060Each vertex receives
a label selected at
random out of 3 ones

SISA speedups:
2.3x, 7.2x, 4.9x, 9.8xtc

10Missing bars indicate timeouts.
SISA speedups: >10x, >10x, 3.8x, 6.6xsi−4s-L

15

Missing bars indicate timeouts.
SISA speedups: >10x, >10x, 4.1x, 3.7x

si−4s

50
40
30
20
10
0
50
40
30
20
10
0

5

b
bn io−
−f SC
ly −
M G
in bn ed T
t− − uin ant mo lla
t− C uin ant ol3 se
t− C −
an ol d1
t 5
bi Co −d1o l6
bi −CE −do− − 2bi DM PGo− −bi DR CXo −bi bi −HS CXo− o− −Wdi o SC LCm rm −ac N HTec s−c etB
on 50 3e − 0
ec con bea −9o − ce n− be xc
in con mb afl
t− − e w
H o acos ra xn cin Wa i67
tD rd 8−a Pr
so nt ox
c− Co
fb l4
M
sg

0

Input graph Baseline:

non−setset−based

sisa

Figure 6: Run-times with full parallelism. The red line cuts off of long simulation runtimes
for readability (the bars reaching the line have much larger runtimes). No bar indicates thetimeout of the respective baseline ( > 24h). The results for cl-jac (clustering based on the
Jaccard coefficient) are very similar to those that use other coefficients and for link prediction as well as vertex similarity. All 32 cores are used. Acronyms are stated in “Comparison
Targets: Hand-Tuned Algorithms”.

all benefit from high-bandwidth storage. The results are in Figure 6.
SISA is almost always the fastest by a large margin of at least 2×,
often more than 10× (than non-set schemes). The differences varydepending on the processed graphs and the considered problem.
Gains are usually larger on graphs with large maximum degrees,such as brain graphs, where SISA-PUM is used more often to directly
process sets inside DRAM, reducing the latency. Such graphs areprevalent in many computational domains [133], and this is thecase for the majority of considered datasets.
Algorithmic vs. Architectural Speedups We also observe
speedups from using only set-centric formulations (over non-setbased variants). Namely, speedups of “_set-based” schemes overthe “_non-set” ones indicate gains from purely algorithmic (setcentric) changes, while speedups of “_sisa” schemes over the“_set-based” indicate gains only from architectural changes (i.e.,

291

from using PIM). First, the differences between _set-based and_non-set heavily depend on the targeted mining algorithm. These
speedups are particularly visible for more complex algorithms suchas mc, with multiple nested loops and/or recursion. Packaging different parts of such algorithms into, e.g., set intersections, andbeing able to control the used operation variant (e.g., merging
based on streaming) helps to utilize features such as high sequential
bandwidth. Contrarily, for certain simpler schemes such as clustering, the very tuned _non-set baseline outperforms _set-based(while still falling short of _sisa). Second, the difference between_set-based and _sisa depend more on the used graph. Here, inmany cases, _sisa is only marginally faster than _set-based, because the graph structure (e.g., sizes of neighborhoods) favor using SAs rather than DBs, diminishing benefits from SISA-PUM(e.g., for econ- graphs) and equalizing the differences because both_set-based and _non-set take advantage from the high bandwidth setting. In other cases (e.g., bio-HS-LC), more vertices havelarge enough degrees to benefit from DBs and low latencies of
SISA-PUM.
Labels We also analyze labeled SI. Most often, labeled graphs
are faster to process. Despite more memory accesses, the labels
form additional constraints, which eliminates some recursive calls
earlier, resulting in performance gains.
Scalability We also analyze how run-times change when varying numbers of threads T , for a fixed graph size (“strong scaling”), and when increasing T proportionally to the graph size(“weak scalability”). To fix the used graph model, we use Kronecker
graphs [99] and we vary the number of edges/vertex. SISA maintains its speedups, but they become less distinctive when T is small.
This is expected because fewer threads exert less pressure on thememory subsystem, and there is overall smaller potential fromusing PIM in SISA.
Large Graphs We execute SISA on several large graphs, see
Figure 8. Runtime benefits from SISA and the set-centric formulations are similar to those in smaller graphs in Figure 6. The only
two graphs where SISA and non-SISA set baselines are comparable,
are sc-pwtk and soc-orkut. This is because these networks, due totheir origin (social and scientific) do not have large cliques or very
dense clusters (unlike, e.g., genome graphs), somewhat lowering
SISA benefits.
Comparison to Other Paradigms We compare SISA setcentric algorithms to neighborhood expansion and relational algebra paradigms, representing frameworks such as Peregrine orRStream, and accelerators such as GRAMER or TrieJax. Peregrine
is able to express only listing k-cliques and subgraph isomorphism,and maximal clique listing in a limited way (i.e., it does not offer a native scheme for MC and we implemented it by iteratingover possible clique sizes and listing maximal cliques of each size).
RStream can only find k-cliques. In each case, SISA baselines aremuch faster: 10-100× than Peregrine (and more than 1,000× formc due to Peregrine’s inability to natively support mc), and morethan 100× for RStream. This is because the underlying paradigms
focus on programmability in the first place, sacrificing performance,
while in SISA we start with tuned graph algorithms and only thenrestructure them with the set-centric paradigm.
Sensitivity Analysis & Design Exploration We investigate
the impact from varying SISA parameters.

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

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Graphs often used in graph mining have often very heavy tails.

bio-humanGene

●

100

●
●

300

● ●
●

Frequency

●

1k

●

bio-mouseGene

●

30
10

●
●

●
●●●●
● ●
●
●
●
●
●
●●●●
●
● ●
●
●●● ●
●
●
●
●● ● ● ●●● ●
●
●
●●
●
●●
●
●
●
● ●
●●
●
●●
●
●
●● ● ●●
●● ●
●●
●
●
● ●
●● ●● ●●● ● ●●●●● ● ●● ●
●●●●●
● ●●
●●
●
● ● ●●● ●●●●●●●●● ●●●●
● ●
● ●●●
●●
●●●
●
●
●
●● ● ●●
●● ●
●
●
●
● ● ●
●●● ●●●●
●
●
●
●
●●
●●
● ●
●
● ●●
●●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
●● ● ●
●
●●● ●
●● ●●
●●
●
●
●
●●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●●
●●
●●●● ●
●
●
●
●●
●
●●●●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●●●
●
●
●●
●
●
●
●●
●
●
●●
●
●
●
●●●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●

30
●

●●
●
●
●
●
●
●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●●
●

●
●●

3

100

●
●●
●
●●
●●
●●
●
●
●●●
●
●
●
●●● ●
● ●
●●●
●
●
●
●
●●
●●
●●
●
●
●
●
●●
● ●●
●
●
●●
●●
●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
● ●●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●● ●
●●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

●●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●●●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

●●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●

●●●● ● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

n = 14k
max deg = 7k
1 (50% of n)
Degree: 1 3 10 30 100 300 1000 3k
●

10

●

● ●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

● ●●●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

3

n = 43k
max deg = 8k
1 (18% of n)
1

3

10

30

●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

100 300 1000 3k

Graphs used also outside mining have much lighter (or no) tails.
●

●

●

●

30k
10k
3k
1k
300
100
30
10

soc-orkut● ●●●●●
●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

n = 3Mmax deg = 33k
1 (1.1% of n)
3

1

3

10

●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●

30 100 300 1000 3k

sc-pwtk

kcc-4, bio-mouse-gene, T=32●

n = 218k
max deg = 179
10k (< 0.1% of n)
30k
3k
1k

●

●

●

●

●

300

●

●

●

●

●

●
●

●

●●
●
●●

●
●

●

● ●● ●
●

●
●
●

●●
●

●

●

●

●

●

●
●
●
●
●

●

●
●

●
●
●

3

●●
● ●
●

●

●

● ●

●

●

10

●
●
●

●

●

100
30

●●
●

●

●

●
●

●

●

1

3

10

gallopingthreshold:t_10000●

30(a) Degree distribution analysis● t_100

0.21

t_5

●
●

●

0.20

●
●

0.19

●

1

Runtime [Millions of cycles]

300

●

Only
SISA-PUM

Only
SISA-PNM
0.00

0.25

0.50

0.75

1.00

% of neighborhoods kept as DBs (t)(b) Sensitivity analysis.

biRuuntime [speedups]obi −hued o−m ma
it− o nG
en use ewi G nek e
in tion net− ad rs at yso c−p ing
c− wt
or k
ku
bi
t
o
bi −hued o−m ma
it− o nG
en use ewi G nek e
in tion net− ad r
sc atin yso −p g
c− wt
or k
ku
t
bi
o−
bi hu
o− m
m an
ou Ge
se n
in Ge et− nd e
sc atinso −pw g
c− tk
or
ku
t
bi
o−
bi hu
o− m
a
m n
ou Ge
se n
in Ge et− nd e
sc atinso −pw g
c− tk
or
ku
t

Figure 7: Figure 7a: Differences between degree distributions in graphs used mostly in graph mining and the ones used also outside graph mining (on the right). Figure 7b: Sensitivity analysis: the percentageof neighborhoods stored as dense bitvectors vs. different thresholds for using the galloping or the merging intersection.
1.00
0.75
0.50
0.25
0.00

kcc−4

Input graph

1.00
0.75
0.50
0.25
0.00

kcc−5

Baseline:

1.00
0.75
0.50
0.25
0.00

non−set

ksc−4

1.00
0.75
0.50
0.25
0.00

set−based

ksc−5

sisa

Figure 8: Run-times for large graphs. 8 cores are used.

SCU cache Not using the SCU cache lowers performance by≈1.5× for T = 1 and ≈0.05-0.1× for T = 32. The lower performancefor high T is because, with more threads executing set operations, it
becomes more difficult to ensure high hit ratio. Overall, the behaviorof the SCU cache is similar to that of other such units such as L1,
including varying cache parameters such as size.
PNM vs. PUM & Sparse/Dense Neighborhoods PNM and
PUM are synergistic in SISA. PNM cores handle sparse neighborhoods and SAs well, as they offer low latency and bandwidth proportionality. PUM is well-suited for large neighborhoods stored
as DBs (common in considered graphs due to their degree distribution skews). Yet, SISA-PUM adds overheads when using it forsparse sets due to low utilization of very sparse rows. Thus, it isrelevant to not choose the DB bias parameter to be too high. We
find that 0.4 works well for most processed graphs. We illustrate
this in Figure 7b, where we analyze how the performance changes
when varying the fraction of largest neighborhoods stored as DBs.
Smallest and largest fractions that correspond to using only SISAPNM or only SISA-PUM, while technically feasible, give slowest
runtimes. We also vary the “galloping threshold”, i.e., the relative
difference between two sets that causes the set operation to switch
to the galloping variant. For example, the value of 5 indicates that
galloping is used if any of the two sets is at least 5× larger than theother one. While this threshold influences performance, the general
pattern stays the same.
We also analyze the impact from degree distributions ofdatasets, see Figure 7a. Graphs often used in graph mining, suchas biological networks, that SISA focuses on, have often very heavy
tails. This implies many large neighborhoods and very dense large
clusters, benefiting from SISA-PUM. For example, the human genome
graph has many vertices connected to more than 30% of all other vertices. Other graphs such as social networks have much lighter tails,292

cf. soc-orkut and sc-pwtk in Figure 7a. This is because these networks, due to their origin (social, scientific) do not have large cliques
or very dense clusters. Such graphs benefit less from SISA-PUM.
Still, using SISA-PNM enables high performance, outperforming
tuned non-set-based baselines, cf. Figure 8.
Load balancing Figure 9a illustrates total fractions of time during which each parallel thread is stalled when executing a given
algorithm. SISA stall times are low because its design implicitly
tackles two types of load imbalance. First, SISA’s performance models enable adaptive selection of the best variant of a set algorithm
to be executed for any two sets. This minimizes load imbalancefrom processing two sizes that differ a lot in sizes. Second, load
imbalance due to processing imbalanced pairs of sets (i.e., two verysmall and two very large sets) is alleviated by the fact that verylarge pairs of sets are processed with very fast SISA-PUM.
SCU cache: shared vs. private We also explore sharing the
SCU cache among all the cores. While possibly increasing the hit
rate, a single shared cache has higher access latency. This has asmall (<1%) yet noticeable slowdown effect in our simulations. A
potential remedy would be to include multiple SCU cache levels. To
keep the core logic simple, we do not explore it further, and leave
it for future work.
We also show that the reduced simulation runtimes do not artificially eliminate load imbalance. We gather traces of executed
set operations in full vs. partial simulation executions, and we plot
histograms of the sizes of processed sets, see Figure 9b. In bothtypes of executions, we encounter large sets which are the primarysource of load imbalance.
SISA Limitations For some graphs with small maximum degrees (e.g., soc-fbMsg) in Figure 6, SISA speedups are smaller, oreven (in the extreme cases) result in slowdowns. This is because
the benefits from SISA-PUM, or from the automatic selection of themost beneficial set operation variant, are out-weighted by having
to process too many large bitvectors. This effect rare, and it can bealleviated by reducing the number of neighborhoods stored as DBs.
In this case, the performance of SISA variants gradually converges
towards that of standard CSR based set-centric algorithms. We planon addressing it with advanced bitvector representations.

10

RELATED WORK

Related graph processing paradigms (Table 1) and software efforts
are described in Section 1 [18, 18, 21, 107, 135]. We now briefly

Fractionofofstalledstalledtime
time
Fraction

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

kcc−4
kcc−4

0.8
0.8
0.6
0.6

Besta et al.

kcc−5
kcc−5

Thread:Thread:t1
t1 t3
t3 t5t5 t7t7
t2
t2 t4t4 t6t6 t8t8

non−setnon−setset−based
set−based

0.4
0.4
0.2
0.2
0.0
0.0

sisa
sisa

non−set set−basednon−set set−based

SchemeSchemesisa
sisa

thread 2
thread 2

thread 3
thread 3

thread 4
thread 4

25 25
50 50
75 75

0 0
25 25
50 50
7
75 5

2
20 0
4
40 0
6
60 0
8
80 0

thread 1
thread 1

Execution: full partial
Execution: full partial

set size
set sizethread 5
thread 5

2
25 5
5
50 0
7
75 5

thread 0
thread 0

0 0
25 25
50 50
7 75
10510
0 0

0.06
0.06
0.04
0.04
0.02
0.02
0.00
0.00

25 25
50 50
75 75

freq
freq

(a) Total amounts of stall times of different 8 parallel threads.
(a) Total amounts of stall times of different 8 parallel threads.

(b) Histograms of sizes of processed sets of full vs. partial executions, for 6 parallel threads(b)Histogramsof behaveprocessed
sets of fullvs. partial
executions,for 6 parallel(theremainder of sizes
threads
similarly).
Graph:
int-antCol3-d1.
Problem:kcc-4. threads(the remainder of threads behave similarly). Graph: int-antCol3-d1. Problem: kcc-4.
FigureFigure 9:
9: LoadLoadbalancingbalancinganalysis.
analysis.
Reference /Accelerator

Prob.

Key memory Pattern M. Learning “Low-c.” is xl ab
mechanism mckcds si vs lp cl avbf pr cc

example, the BFS frontier can be modeled as a set. Here, SISA’s main
example,the BFSisfrontier
be modeleda set. Here,SISA’sfrom
main thecontribution
not to cansimplyuse set as
notation.
Instead,contribution
is
not
to
simplyuse
setnotation.
Instead,fromalgorithmic perspective, SISA is the first design that (1) uses theset opalgorithmic
is theblocks,
first design(1) down
uses set
operations asperspective,
the primarySISA
building
whichthatbreak
complexerations as the primary building blocks, which break down complex
graph mining algorithms into simple units of parallel execution,
graph mining algorithms into simple units of parallel execution,and (2) identifies the “appropriate” set operations (i.e., operationsand (2) identifies the “appropriate” set operations (i.e., operations
that are easily accelerated with PIM) and reformulates selectedthat are easily accelerated with PIM) and reformulates selected
algorithms so that they use such operations, cf. Table 2.
algorithms so that they use such operations, cf. Table 2.
SISA vs. AutoMine [112] AutoMine [112] uses set operations
SISA vs. AutoMine [112] AutoMine [112] uses set operations
to express finding graph patterns. It focuses on automatic compito express finding graph patterns. It focuses on automatic compilation of set schedules into efficient code. This part is orthogonallation of set schedules into efficient code. This part is orthogonal
ourwork
work
andAutoMine
could
easilycombined
with
SISA
totoourandAutoMine
could
easilybe becombined
with
SISA
to, to,forexample,
example,generate
generate
code
based
SISA’sset-centric
formulafor
code
based
onon
SISA’sset-centric
formulations.Note
Notethat
that
SISA’sformulations
superior
to thosetions.
SISA’ssetsetformulations
arearesuperior
to thoseof of
AutoMine,becauseSISA(1)
supports
allset
operations,
including
AutoMine, because SISA (1) supports all set operations, including
nonanti-monotonic
anti-monotonic
ones
(not
intersection
difference),
non
ones
(not
justjust
intersection
andanddifference),(2) it(2) it
expresses
wholealgorithms
withbuilding
blocksexpresses
wholealgorithms
withthethesetsetbuilding
blocks(not(notjustjust
pattern
generation
schedules),
and
(3)
it
targets
broad
graph
miningpattern generation schedules), and (3) it targets broad graph mining(notjust
justpatternmatching).
(notpatternmatching).
SISAshowsshows
howseamlessly
integrate
PUM
PNM
capaSISA
how
to toseamlessly
integrate
PUM
andandPNM
capabilitiesinina single
system.
They
work
synergistically
producebilitiesa single
system.
They
work
synergisticallyandandproducesignificantly
betterresults
thanworking
separately.
significantly
betterresults
thanworking
separately.

[Pi] GaaS-X [31]SpMV[e] CAM/MAC é é é é é é é éé[Pi] GraphiDe [10]low-c[e] DRAMé é é éé é éé[Pc] Spara [181]ver-c[e] ReRAMé é é é é é é ééé[Pc] GraphQ [183]ver-c[e] HMCé é é é é é é ééé[Pc] GraphS [11]low-c[e] SOT-MRAM é é é é
é é é
é é é
[Pc] RAGra [77]ver-c[e] 3D ReRAM é é é é é é é éééWethethefirst
hardwareacceleration
forforbroad
graph
mining.
[Pc] GRAM [182]ver-c[e] ReRAMé é é é é é é ééé
Wedevelop
developfirst
hardwareacceleration
broad
graph
mining.
SpMV[Pc] GraphR [149]
[e]
ReRAM
é
é
é
é
é
é
é
é
é
Pattern M. Learning “Low-c.” Remarks
First,
weofferaset-centric
programming
paradigm,
whereoneoneAbstractionore this suffices [Pc] GraphP
A?
First, we offer a set-centric programming paradigm, where
[177]
ver-c
[e] HMCé é é é é é é éé éprogramming
model
mc kc
si vs lp cléavétcé bf[Pc] Tesseract
[6]
low-c
[e]ds
HMC
é cc
é pr
é é é
é
identifies
andexposesset
operations
ingraph
miningalgorithms.
ften requires [Pc]identifies
andexposesset
operations
ingraph
miningalgorithms.
PIM-Enabled [7]low-c[e] HMCé é é é é é é é∗ HighGao
et al. [54] (ver-c)low-cé é é
3DéDRAMé comm. é
Vertex-centric
This
time
complexities
andandsuccinct
formué é é éééé ∗ é é é é
costsé
btaining such [Pc]Thisenables
enablescompetitivecompetitive
timecomplexities
succinct
formu[A] IntersectX [127]pattern m.
[e] cacheéé é∗ ∗ é∗ é é∗ é é work
Edge-centric(edge-c)
é
é
é
é
é
é
é
é
[A]
Gramer[176]
pattern
m.
DRAM,
cache
éé
é é éHighé é é é andé depthé
lations.
We
supportlabeledgraphsandnonanti-monotonic
set setor infeasible, [A] TrieJax∗ Onlylations. We support labeled graphs and non anti-monotonic
joinsé é éDRAM,é é é éé é low-diameteré é éArray[89]
maps
é LLC
é é ∗éé
decomp.
∗ The
[89,
112,
127,
176].
[A] HyGCN [174]
GCN
eDRAM
é é é éé éonlyé existingé
SI scheme operations
ms, like trian- [A]∗†operations [89, 112, 127, 176].
Outerspace[124]
SpMSpMHBMé é éGraphBLAS[90](L) é ééé é ééé é é é é é é
only
[34]
Second,theset-centricalgorithms
arearemappedto SISA,a small
Domino [169]low-c
on-chip buffers éé é é é é
é uses treeséasépatterns
éc model”) and [A]† GNNsSecond,theset-centricalgorithms
mappedto SISA,a small
Neural message[A] GraphPIM[120] passing,
low-c[e] HMCéé é é éé
éare as powerfulas the†(L) é ééeDRAMéé éé éyetexpressive“set-centric”
ISA
extensionforgraphmining.
SISA[A]Graphicionado
[65]
ver-c
[e]
é
é
é
é
é
é
é
é
graph networks [13, 62]
Weisfeiler-Lehman test [170].
apply to other [A] Ozdal
yetexpressive“set-centric”
ISA
extensionforgraphmining.
SISA
et al. [123]
ver-c
é é é
é
∗ [e]
∗ caches∗ ∗∗ é é é é∗ é bounds, low
could be extended with CISC-style set instructions that accept
matching GNNé
[A+Pc]Pattern
EnGN [68][e] HBM é é éééé é éé é é Noé éé é éperformanceé
meworks such [A+Pc]
couldbe
extended
with
CISC-styleset
instructions
that
accept
∗
∗
∗
∗
∗
∗
∗
∗
∗
OMEGA
[2]
low-c
[e]
Scratchpads
é
é
é
é
é
é
é
é
Joins [36]
(R) é
é
é
é
No bounds, low performance multiple arguments (e.g., 𝐴 ∩ ... ∩ 𝐴 ) to facilitate optimizations
é éééing problems, [A+Pc+M] GraphH [43] ver-c Link [e] HMC Linké é é é é éLink
multiple arguments (e.g., 1A ∩ ... ∩𝑙 A ) to facilitate optimizations
𝑘 -Star-Clique
MaximalJarvis-Patrick[e] 3D DRAM é é é éé é
[F+Pc]Set-CentricHRL[55] Cliques
é é
é é é
é
é
/ SISA ver-c (S)such as vectorization with loop1 unrolling.l Due to the generality of
Listing [79]
Listing [26, 51]such as vectorization with loop unrolling. Due to the generality ofPrediction§ Clustering [81]Prediction†
Prediction‡[Pc+Pi]SISA1:[Thiswork]GraphminingPIMé é to existing graphset algebra, SISA can be used for problems beyond graph mining.
Table
Comparisonof theset-centric programming approach andé SISA
grine
[80]
and
set algebra, SISA can be used for problems beyond graph mining.
⋆
2
𝑘−1
⋆
𝑐/3
2
2
⋆
processing
abstractions/programming
models,focusingonsupportforselectedgraphmin)
𝑂 (𝑘 𝑚 (𝑐/2) Table) 7: Comparison
𝑂 (𝑐𝑑𝑛3 of) SISA 𝑂(𝑛 + 𝑚𝑑) focusing
𝑂 (𝑛 on) supported
𝑂 (𝑚𝑑)
to (𝑚𝑑)graph-related𝑂accelerators,
graphproblems(pattern
andfor“low-complexity”
graph
A?:Third, while we pick in-situ and logic layer PIM for hardware accelTable
7:ing
Comparisonof
SISA matching,tograph-related
graph
𝑐/3
⋆
⋆learning),
2accelerators,⋆focusing2 )on⋆ supported⋆
were
proposed.
miningproblems
andofferedarchitectureelements.
“log”:𝑐)Support/ significant
focus.
“problems.
”:Third,
while we pick in-situ and logic layer PIM for hardware accelog 𝑐) 𝑂
(𝑘 2𝑚 (𝑐/2) 𝑘−1
log
𝑐)
𝑂
(𝑐𝑛3
)
𝑂
(𝑚𝑐
log
𝑐)
𝑂
(𝑛
+
𝑚𝑐
𝑂
(𝑛
𝑂
(𝑚𝑐
log
𝑑)
algebra?
L:linear,
R: relational,
S: set.
“ ”: Support/ significant
miningproblems
andofferedarchitecture“ ”: Partialeration, SISA’s set algebra interface could easily use other hardware
Partial Underlying
support/ somefocus.
“é”:
no support/ noelements.
focus.
Addressed
problems:
see Tablefocus.
1. Graphew
graphpatsupport
some focus.
focus. ““⋆”“é”:
nosupport/a nofocus.
Patternselected
graphpatternmatching
prob- eration, SISA’s set algebra interface could easily use other hardwareon theruntimeof graphmining
that
given
SISA
variantM.:
matches
asymptotically
best known
Partialsupport//algorithms:
someAddressed
problems:
seeTable 1.theGraphproblems
andalgorithms..
as ”:
inmeans
Table
1. Consideredarchitectureand stackelements:“is”:
backends, for example a GPU backend for fast SIMD-based set inlems,
mc:
maximalcliquelisting,𝑘Considered-cliquelisting,ds:
subgraph,si:Classes
subgraphof themined pattern, problems
the
graph
(a popularmeasureofdesign,
graphsparsity)
anddense
the maximum
vertexdegree,respectively
andalgorithms:
asa cross-layerinTablekc:
1.
and stackelements:“is”:
an ISA,or degeneracy
its
extensions,
“xl”:
“ab”:
a architecture
programming
paradigm
ofisomorphism,
acde
theoreticalbackends,[67],for example
a GPU
backendfor fastinSIMD-based
set in†“xl”:‡ Totaltersections
Learning:
selected
graph
learning
problems,
vs:vertexsimilarity,
lp:ASIC,link
prediction,
cl: acclustering
FPGAs [22],or evenexecution
caches [3, 119].
an
ISA,
or its[Pi]:extensions,a cross-layer
design,“ab”:
a logic
programming
paradigm
Classesofd for the following vertex
similarity
measures:
Jaccard,Overlap,
AdamicAdar,
Resource
Allocation,
CommonNeighbors;celerators:
in-situPIM,[Pc]:near memory
PIM(e.g.,
layers),[A]:
FPGA
designsor related
community
detection,
av:nearaccuracy
verification(oflogiclink[e]prediction“Low-c.”:ph algorithms celerators:
tersections
[67],
FPGAs
[22],
or
even
executionincaches[3,
119].
[Pi]: memory
in-situPIM,[Pc]:memoryPIM(e.g.,
layers),
ASIC, FPGA
designs
and little
hierarchy
enhancements
are excluded.
focus [A]:on outcomes),
extensionsandmod- selectedWe
leave this for future work.
“low-complexity”
by vastmajorityof existingworks
on graph processing.
littlerelatedmemoryproblems
hierarchy
enhancements
excluded.
[e] focus
on extensionsandmod- tc: triifications
to the established(alreadytargeted
proposed)
HW aretechnology,
Note
that
the
generality
of
SISA
ed for a graph and
We
leave
this
for
futurework.
angle
counting,
bf:
BFS,
cc:
connected
components,
pr:
PageRank.
The
analysis
in
this
table
is
Finally, our cross-layer architecture could also be extended in
ifications
to harnessing
the established(already
proposed)
HW technology, Note that the generality of SISA
comes fromall basic
set algebra
operations.
extendedin Section
10 setandalgebra
Table operations.
7 by detailing specific HW accelerators for graph processing.
many graph comes fromharnessing
all basic
Finally, our cross-layer architecture could also be extended in

1111 DISCUSSIONANDCONCLUSIONDISCUSSIONANDCONCLUSION

directions, for example by providing compiler support fora recent design that enables energy-efficient bulk bitwise opera-other
other directions,for example
by providing
compilerHere,supportgenerating
SISA programsfrom set-centric
formulations.
one fortions fully
insideDRAM,
byFirst,smallweextensions
to theDRAM circuitry generating SISA programs from set-centric formulations. Here, onesummarize
otherrelatedareas.
conducted
an exhaustive
analysisof existing
hardwareaccelerators
asinterface.
well as ISA
designsSISA iscould use, e.g., AutoMine’s [112] compiler generated schedules ast package
the analysis
but ofwithoutchangestothe DRAM
However,ng
algorithms
identifies
setsanyandset operations
in a given
algorithm.
These set op-input
existing
hardwareaccelerators
as indicates
well
as ISA
designse.g.,
AutoMine’s
touse,
some
SISA
programs.[112] compiler generated schedules as
for
graph
processing,
see
Table
7.
The
analysisthat
SISA [168], could
nts,theseincluding
generic
andotherdesignsused(e.g.,
ELP2IMuse
algo- for grapherations
are thenmappedto7.could
a The
smallalso
andbe
simpleyetexpressive
processing,
see
Table
analysisindicates
that
SISAgroup input to some SISA programs.
offersthe
only
hardwareacceleration
for
a
broad
familyofprobloping setbut,
al- offersof
DRISA[100],
ComputeDRAM
[53],
PCM
(Pinatubo)[101]).
The key
tructures,instructions,offering
a richselectionof storage/performancethe
only
hardwareaccelerationfora broadfamilyof problemsextension
such
as maximal
cliquelisting orclustering.
The
closestdestructions
for
in
Ambit
(for
in-situprocessing)istomodifyadecoder
not compute- lems tradeoffs.
These instructions
arePIMclosest
units. deWe callACKNOWLEDGMENTSsuch
as maximal
oroffloaded
clustering.toThe
signsfor[89,three127,
176]
onlyclique
focuslistingon
selected
matching
probselected
rows(thatpatternshare thesame
setof sense ACKNOWLEDGMENTS
n we increase signs
these
instructions
SISA
ason
they
form
“Set-centric”
ISA
extensions
[89,
127,
176]
onlyDRAM
focus
selectedpatternmatching
problems.
Works
orthogonal
to
SISA
includeHW
accelerated
dynamic
thank Mark Klein, Hussein Harake, Colin McMurtrie, Angelo
pers)
For andpro- lems.that
amplifiers)
insimplesuch toa way
one HW
amplifierconnects
directly
toWe
ttens out
enableagraphinterface
betweennumerous
graphminingalgoWorks
orthogonal
SISAthatincludeaccelerated
dynamic
We thank
Klein,CSCS
Hussein(time-evolving)
analytics[27,
28, 69],orexternal
memoryMangili,
andMark
the whole
teamHarake,
grantingColin
accessMcMurtrie,
to the Ault Angelo
andpngofprocessinghigh-level (time-evolving)
three DRAM
cells.
This enables
logicalAND
and OR
overconsists
two of Mangili, and the whole CSCS team granting access to the Ault andrithmsandPIM
hardware.
Overall,ourcross-layer
designgraph
analytics
[27,
28,
69],
or
external
memoryHW accelerated graph processing [47, 87, 110]. One could use theDaint machines, and for their excellent technical support. We thankers. Ininthe
for- HW accelerated
such threerows,
immediately
computingtheresultin paradigm
the
dups
graph
keybackend
elements:
new set-centric
programming
graph
processing[47,
87, 110].
One
could use
the thirdTimo
Daintmachines,
their excellent
technical
support.
We thank
latterofasthreea SISAfor aexternal
memoryset
instructions;weSchneiderforandhisforimmensehelp withcomputinginfrastrucefor
to ahardware
SISA set; latterand
row
(NOT
is
providedbyincludingasinglerowofdual-contact
formulationsofgraph
algorithms(contribution#1),
set-centric
as a SISA
backendfor external memory set instructions; we
Timo
Schneider
his immense
withfrom
computinginfrastrucleave details
for future
work.
ture
at SPCL.
Thisforproject
receivedhelp
funding
the European
de ofitFigure
3. leaveISA
DRAM
cellsfuture[141]).
Importantly
for SISA-PUM,
onlysetthreeselected ture at SPCL. This project received funding from the Europeanuse(1) repextensions
with
its graph
instructions,
implemented
operations,details
for
work.
Sets
are
used
in different
algorithms,
to simplify
operaResearch Council (ERC) under the European Union’s Horizon 2020
apthe
to memory
SISA set
designated
DRAM
rows
(per
singleDRAM
subarray)aremodifiedandsetusedorganization(contribution#2),114,
and125,PIM
accelerationSetsin
different
graph
to
simplify
Research Council(ERC) under
the European
Union’s Horizon 2020
tions
onare
selecteddata
structures[21, algorithms,
26, 92,
138,143].operaFor (con-programme(grant agreement
DAPP,
No. 678880).
thisway. #3).
Wheneverthe running
requests
an143].
in-situroaches [141], tions tribution
on selected
data structures[21, 26, code
92, 114,125, 138,
Formem- programme (grant agreement DAPP, No. 678880).
rated
with
the
oryOverall,
operation,
Ambit uses
a recent
RowClone
to
ngs
very
large
we advocate
using
set algebra
as a technology
basis for the[140]designty, SISA’s new
copy(alsomining
in-situ)
the rows that
input sets
to thesetwofirst
desigPageRank
(see
of
graph
algorithms.
Ourstore
set-centricparadigm
is thetoset [165]. We
natedcomputethe result in-situ,
andbuilding
again use
RowClonetolgorithms
areusesetrows,
operations
as fundamental
generalblocksfor bothV
instructions
copy
theresulttothedestination(unmodified)
DRAM
row.
Now,
: they employ
algorithmic formulations and their execution. Using set algebra
represent
the
SISA-PUM
execution
model
interface
without
293toureswith nonensures
thatusesSISAAmbit’s
set-centricalgorithms
are andsuccinct,applicableset to[51,0x16toany modifications:intersectionefficient.
and union are processed with
ance
171].
many
problems, andset
theoreticallyon.
Fieldsgraphrs1,
an Forin-situAND and OR,
respectively.
Set difference
is processedts broad
the in-memory
accelerationof SISA,
we investigate
which

use
bit vectors.
al workguar-

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

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

REFERENCES[1] Christopher R Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. 2017. Emptyheaded: A relational engine for graphprocessing. ACM Transactions on Database Systems (TODS) 42, 4 (2017), 1–44.
[2] Abraham Addisie, Hiwot Kassa, Opeoluwa Matthews, and Valeria Bertacco. 2018.
Heterogeneous memory subsystem for natural graph analytics. In 2018 IEEE
International Symposium on Workload Characterization (IISWC). IEEE, 134–145.
[3] Shaizeen Aga, Supreet Jeloka, Arun Subramaniyan, Satish Narayanasamy, David
Blaauw, and Reetuparna Das. 2017. Compute caches. In 2017 IEEE International
Symposium on High Performance Computer Architecture (HPCA). IEEE, 481–492.
[4] Charu C Aggarwal and Haixun Wang. 2010. Managing and mining graph data.
Vol. 40. Springer.
[5] Rakesh Agrawal, Ramakrishnan Srikant, et al. 1994. Fast algorithms for mining
association rules. In Proc. 20th int. conf. very large data bases, VLDB, Vol. 1215.
Citeseer, 487–499.
[6] Junwhan Ahn, Sungpack Hong, Sungjoo Yoo, Onur Mutlu, and Kiyoung Choi.
2015. A scalable processing-in-memory accelerator for parallel graph processing.
In ISCA.
[7] Junwhan Ahn, Sungjoo Yoo, Onur Mutlu, and Kiyoung Choi. 2015. PIM-enabled
instructions: a low-overhead, locality-aware processing-in-memory architecture.
In Computer Architecture (ISCA), 2015 ACM/IEEE 42nd Annual International
Symposium on. IEEE, 336–348.
[8] Mohammad Al Hasan, Vineet Chaoji, Saeed Salem, and Mohammed Zaki. 2006.
Link prediction using supervised learning. In SDM06: workshop on link analysis,counter-terrorism and security.
[9] Mohammad Al Hasan and Mohammed J Zaki. 2011. A survey of link prediction
in social networks. In Social network data analytics. Springer, 243–275.
[10] Shaahin Angizi and Deliang Fan. 2019. Graphide: A graph processing accelerator leveraging in-dram-computing. In Proceedings of the 2019 on Great Lakes
Symposium on VLSI. 45–50.
[11] Shaahin Angizi, Jiao Sun, Wei Zhang, and Deliang Fan. 2019. GraphS: A graphprocessing accelerator leveraging SOT-MRAM. In 2019 Design, Automation &Test in Europe Conference & Exhibition (DATE). IEEE, 378–383.
[12] Omar Batarfi, Radwa El Shawi, Ayman G Fayoumi, Reza Nouri, Ahmed Barnawi,
and Sherif Sakr. 2015. Large scale graph processing systems: survey and an
experimental evaluation. Cluster Computing 18, 3 (2015), 1189–1213.
[13] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez,
Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam
Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning,and graph networks. arXiv preprint arXiv:1806.01261 (2018).
[14] Scott Beamer, Krste Asanović, and David Patterson. 2015. The GAP benchmark
suite. arXiv preprint arXiv:1508.03619 (2015).
[15] Tal Ben-Nun, Maciej Besta, Simon Huber, Alexandros Nikolaos Ziogas, DanielPeter, and Torsten Hoefler. 2019. A modular benchmarking infrastructure forhigh-performance and reproducible deep learning. In 2019 IEEE International
Parallel and Distributed Processing Symposium (IPDPS). IEEE, 66–77.
[16] Maciej Besta, Armon Carigiet, Zur Vonarburg-Shmaria, Kacper Janda, Lukas
Gianinazzi, and Torsten Hoefler. 2020. High-performance parallel graph coloring with strong guarantees on work, depth, and quality. arXiv preprint
arXiv:2008.11321 (2020).
[17] Maciej Besta, Raphael Grob, Cesare Miglioli, Nicola Bernold, Grzegorz Kwasniewski, Gabriel Gjini, Raghavendra Kanakagiri, Saleh Ashkboos, Lukas Gianinazzi, Nikoli Dryden, et al. 2021. Motif Prediction with Graph Neural Networks.
arXiv preprint arXiv:2106.00761 (2021).
[18] Maciej Besta and Torsten Hoefler. 2015. Accelerating irregular computations
with hardware transactional memory and active messages. In Proceedings ofthe 24th International Symposium on High-Performance Parallel and Distributed
Computing. 161–172.
[19] Maciej Besta, Raghavendra Kanakagiri, Harun Mustafa, Mikhail Karasikov,
Gunnar Rätsch, Torsten Hoefler, and Edgar Solomonik. 2020. Communicationefficient jaccard similarity for high-performance distributed genome comparisons. In 2020 IEEE International Parallel and Distributed Processing Symposium(IPDPS). IEEE, 1122–1132.
[20] Maciej Besta, Florian Marending, Edgar Solomonik, and Torsten Hoefler. 2017.
SlimSell: A Vectorizable Graph Representation for Breadth-First Search. In
Parallel and Distributed Processing Symposium (IPDPS), 2017 IEEE International.
IEEE, 32–41.
[21] Maciej Besta, Michał Podstawski, Linus Groner, Edgar Solomonik, and Torsten
Hoefler. 2017. To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations. In Proceedings of the 26th International Symposium
on High-Performance Parallel and Distributed Computing. ACM, 93–104.
[22] Maciej Besta, Dimitri Stanojevic, Johannes De Fine Licht, Tal Ben-Nun, andTorsten Hoefler. 2019. Graph Processing on FPGAs: Taxonomy, Survey, Challenges. arXiv preprint arXiv:1903.06697 (2019).
[23] Maciej Besta, Zur Vonarburg-Shmaria, Yannick Schaffner, Leonardo Schwarz,
Grzegorz Kwasniewski, Lukas Gianinazzi, Jakub Beranek, Kacper Janda, Tobias
Holenstein, Sebastian Leisinger, et al. 2021. GraphMineSuite: Enabling HighPerformance and Programmable Graph Mining Algorithms with Set Algebra.

294

VLDB (2021).
[24] Guy E. Blelloch and Bruce M. Maggs. 2010. Parallel Algorithms (2 ed.). Chapman& Hall/CRC, 25.
[25] Otakar Boruvka. 1926. O jistém problému minimálním. (1926).
[26] Coen Bron and Joep Kerbosch. 1973. Algorithm 457: finding all cliques of anundirected graph. Commun. ACM 16, 9 (1973), 575–577.
[27] Lázaro Bustio, René Cumplido, Raudel Hernández, José M Bande, and Claudia
Feregrino. 2015. Frequent itemsets mining in data streams using reconfigurable
hardware. In International Workshop on New Frontiers in Mining Complex Patterns.
Springer, 32–45.
[28] Lázaro Bustio-Martínez, René Cumplido, Martín Letras-Luna, Claudia Feregrino
Uribe, Raudel Hernández-León, and José M Bande-Serrano. 2017. Approximate
frequent itemsets mining on data streams using hashing and lexicographie orderin hardware. In 2017 IEEE 8th Latin American Symposium on Circuits & Systems(LASCAS). IEEE, 1–4.
[29] Frédéric Cazals and Chinmay Karande. 2008. A note on the problem of reporting
maximal cliques. Theoretical Computer Science 407, 1-3 (2008), 564–568.
[30] Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph mining: Laws,
generators, and algorithms. ACM computing surveys (CSUR) 38, 1 (2006), 2.
[31] Nagadastagiri Challapalle, Sahithi Rampalli, Linghao Song, Nandhini Chandramoorthy, Karthik Swaminathan, John Sampson, Yiran Chen, and Vijaykrishnan Narayanan. 2020. GaaS-X: Graph Analytics Accelerator Supporting Sparse
Data Representation using Crossbar Architectures. ISCA (2020).
[32] Rohit Chandra, Leo Dagum, David Kohr, Ramesh Menon, Dror Maydan, andJeff McDonald. 2001. Parallel programming in OpenMP. Morgan kaufmann.
[33] Hongzhi Chen, Miao Liu, Yunjian Zhao, Xiao Yan, Da Yan, and James Cheng.
2018. G-Miner: an efficient task-oriented graph mining system. In Proceedingsof the Thirteenth EuroSys Conference. ACM, 32.
[34] Langshi Chen, Jiayu Li, Ariful Azad, Lei Jiang, Madhav Marathe, Anil Vullikanti, Andrey Nikolaev, Egor Smirnov, Ruslan Israfilov, and Judy Qiu. 2019. A
GraphBLAS approach for subgraph counting. arXiv preprint arXiv:1903.04395(2019).
[35] Xuhao Chen, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali. 2019. Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU. arXiv
preprint arXiv:1911.06969 (2019).
[36] Jiefeng Cheng, Jeffrey Xu Yu, Bolin Ding, S Yu Philip, and Haixun Wang. 2008.
Fast graph pattern matching. In 2008 IEEE 24th International Conference on Data
Engineering. IEEE, 913–922.
[37] James Cheng, Linhong Zhu, Yiping Ke, and Shumo Chu. 2012. Fast algorithms
for maximal clique enumeration with limited memory. In Proceedings of the 18th
ACM SIGKDD international conference on Knowledge discovery and data mining.
1240–1248.
[38] Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listingalgorithms. SIAM Journal on computing 14, 1 (1985), 210–223.
[39] Diane J Cook and Lawrence B Holder. 2006. Mining graph data. John Wiley &Sons.
[40] Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman. 2005. Linuxdevice drivers. " O’Reilly Media, Inc.".
[41] Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. 2004. A(sub) graph isomorphism algorithm for matching large graphs. IEEE transactions
on pattern analysis and machine intelligence 26, 10 (2004), 1367–1372.
[42] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.
2009. Introduction to algorithms. MIT press.
[43] Guohao Dai, Tianhao Huang, Yuze Chi, Jishen Zhao, Guangyu Sun, Yongpan
Liu, Yu Wang, Yuan Xie, and Huazhong Yang. 2018. Graphh: A processing-inmemory architecture for large-scale graph processing. IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems 38, 4 (2018), 640–653.
[44] Maximilien Danisch, Oana Balalau, and Mauro Sozio. 2018. Listing k-cliquesin sparse real-world graphs. In Proceedings of the 2018 World Wide Web Conference on World Wide Web. International World Wide Web Conferences Steering
Committee, 589–598.
[45] William HE Day and David Sankoff. 1986. Computational complexity of inferring
phylogenies by compatibility. Systematic Biology 35, 2 (1986), 224–229.
[46] Laxman Dhulipala, Guy E Blelloch, and Julian Shun. 2018. Theoretically efficientparallel graph algorithms can be fast and scalable. In Proceedings of the 30th on
Symposium on Parallelism in Algorithms and Architectures. 393–404.
[47] Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy Blelloch,
Phillip Gibbons, and Julian Shun. 2020. Sage: Parallel Semi-Asymmetric Graph
Algorithms for NVRAMs. PVLDB (2020).
[48] Vinicius Dias, Carlos HC Teixeira, Dorgival Guedes, Wagner Meira, and Srinivasan Parthasarathy. 2019. Fractal: A General-Purpose Graph Pattern Mining
System. In Proceedings of the 2019 International Conference on Management ofData. ACM, 1357–1374.
[49] Sumeet Dua and Xian Du. 2016. Data mining and machine learning in cybersecurity. CRC press.
[50] John D Eblen, Charles A Phillips, Gary L Rogers, and Michael A Langston.
2012. The maximum clique enumeration problem: algorithms, applications, andimplementations. In BMC bioinformatics, Vol. 13. Springer, S5.

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

[51] David Eppstein, Maarten Löffler, and Darren Strash. 2010. Listing All Maximal
Cliques in Sparse Graphs in Near-Optimal Time. In Algorithms and Computation- 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17,
2010, Proceedings, Part I. 403–414. https://doi.org/10.1007/978-3-642-17517-6_36[52] Brian Gallagher. 2006. Matching Structure and Semantics: A Survey on GraphBased Pattern Matching.. In AAAI Fall Symposium: Capturing and Using Patterns
for Evidence Detection. 45–53.
[53] Fei Gao, Georgios Tziantzioulis, and David Wentzlaff. 2019. Computedram: Inmemory compute using off-the-shelf drams. In Proceedings of the 52nd Annual
IEEE/ACM International Symposium on Microarchitecture. 100–113.
[54] Mingyu Gao, Grant Ayers, and Christos Kozyrakis. 2015. Practical near-dataprocessing for in-memory analytics frameworks. In 2015 International Conference
on Parallel Architecture and Compilation (PACT). IEEE, 113–124.
[55] Mingyu Gao and Christos Kozyrakis. 2016. HRL: Efficient and flexible reconfigurable logic for near-data processing. In 2016 IEEE International Symposium on
High Performance Computer Architecture (HPCA). Ieee, 126–137.
[56] Saugata Ghose, Amirali Boroumand, Jeremie S Kim, Juan Gómez-Luna, andOnur Mutlu. 2019. Processing-in-Memory: A Workload-driven Perspective. IBM
JRD (2019).
[57] Saugata Ghose, Kevin Hsieh, Amirali Boroumand, Rachata Ausavarungnirun,
and Onur Mutlu. 2019. The processing-in-memory paradigm: Mechanisms toenable adoption. In Beyond-CMOS Technologies for Next Generation Computer
Design. Springer, 133–194.
[58] Lukas Gianinazzi, Maciej Besta, Yannick Schaffner, and Torsten Hoefler. 2021.
Parallel Algorithms for Finding Large Cliques in Sparse Graphs. In Proceedingsof the 33rd ACM Symposium on Parallelism in Algorithms and Architectures.
243–253.
[59] Lukas Gianinazzi, Maximilian Fries, Nikoli Dryden, Tal Ben-Nun, and Torsten
Hoefler. 2021. Learning Combinatorial Node Labeling Algorithms. arXiv preprint
arXiv:2106.03594 (2021).
[60] Lukas Gianinazzi, Pavel Kalvoda, Alessandro De Palma, Maciej Besta, andTorsten Hoefler. 2018. Communication-avoiding parallel minimum cuts andconnected components. ACM SIGPLAN Notices 53, 1 (2018), 219–232.
[61] David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering large dense
subgraphs in massive graphs. In Proceedings of the 31st international conference
on Very large data bases. 721–732.
[62] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E
Dahl. 2017. Neural message passing for quantum chemistry. In International
Conference on Machine Learning. PMLR, 1263–1272.
[63] Juan Gómez-Luna, Izzat El Hajj, Ivan Fernandez, Christina Giannoula, Geraldo F
Oliveira, and Onur Mutlu. 2021. Benchmarking a New Paradigm: An Experimental Analysis of a Real Processing-in-Memory Architecture. arXiv preprint
arXiv:2105.03814 (2021).
[64] Nastaran Hajinazar, Geraldo F Oliveira, Sven Gregorio, João Dinis Ferreira,
Nika Mansouri Ghiasi, Minesh Patel, Mohammed Alser, Saugata Ghose, Juan
Gómez-Luna, and Onur Mutlu. 2021. SIMDRAM: a framework for bit-serial
SIMD processing using DRAM. In Proceedings of the 26th ACM International
Conference on Architectural Support for Programming Languages and Operating
Systems. 329–345.
[65] Tae Jun Ham, Lisa Wu, Narayanan Sundaram, Nadathur Satish, and Margaret
Martonosi. 2016. Graphicionado: A high-performance and energy-efficient
accelerator for graph analytics. In Microarchitecture (MICRO), 2016 49th Annual
IEEE/ACM International Symposium on. IEEE, 1–13.
[66] J Han and M Kamber. 2006. Data Mining Concepts and Techniques (A. Stephan,Ed.), 2nd edn., vol. 40.
[67] Shuo Han, Lei Zou, and Jeffrey Xu Yu. 2018. Speeding Up Set Intersections inGraph Algorithms using SIMD Instructions. In Proceedings of the 2018 International Conference on Management of Data. ACM, 1587–1602.
[68] Lei He. 2019. EnGN: A High-Throughput and Energy-Efficient Accelerator forLarge Graph Neural Networks. arXiv preprint arXiv:1909.00155 (2019).
[69] Eric Robert Hein. 2018. Near-data processing for dynamic graph analytics. Ph.D.
Dissertation. Georgia Institute of Technology.
[70] Wim Heirman, Trevor Carlson, and Lieven Eeckhout. 2012. Sniper: Scalable andaccurate parallel multi-core simulation. In 8th International Summer School on
Advanced Computer Architecture and Compilation for High-Performance and Embedded Systems (ACACES-2012). High-Performance and Embedded Architecture
and Compilation Network of . . . , 91–94.
[71] Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear. 2020. The
art of multiprocessor programming. Newnes.
[72] Shohei Hido and Hiroyuki Kawano. 2005. AMIOT: induced ordered tree mining
in tree-structured databases. In Fifth IEEE International Conference on Data
Mining (ICDM’05). IEEE, 8–pp.
[73] Torsten Hoefler and Roberto Belli. 2015. Scientific benchmarking of parallel
computing systems: twelve ways to tell the masses when reporting performance results. In Proceedings of the international conference for high performancecomputing, networking, storage and analysis. 1–12.
[74] Tamás Horváth, Thomas Gärtner, and Stefan Wrobel. 2004. Cyclic patternkernels for predictive graph mining. In Proceedings of the tenth ACM SIGKDD

295

international conference on Knowledge discovery and data mining. ACM, 158–167.
[75] Kevin Hsieh, Samira Khan, Nandita Vijaykumar, Kevin K Chang, Amirali
Boroumand, Saugata Ghose, and Onur Mutlu. 2016. Accelerating pointer chasing in 3D-stacked memory: Challenges, mechanisms, evaluation. In 2016 IEEE
34th International Conference on Computer Design (ICCD). IEEE, 25–32.
[76] Tianhao Huang, Guohao Dai, Yu Wang, and Huazhong Yang. 2018. HyVE:
Hybrid vertex-edge memory hierarchy for energy-efficient graph processing. In
2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE,
973–978.
[77] Yu Huang, Long Zheng, Xiaofei Liao, Hai Jin, Pengcheng Yao, and Chuangyi
Gui. 2019. RAGra: Leveraging Monolithic 3D ReRAM for Massively-Parallel
Graph Processing. In 2019 Design, Automation & Test in Europe Conference &Exhibition (DATE). IEEE, 1273–1276.
[78] Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman,
Vladimir Braverman, and Ion Stoica. 2018. {ASAP }: Fast, Approximate Graph
Pattern Mining at Scale. In 13th {USENIX } Symposium on Operating Systems
Design and Implementation ( {OSDI } 18). 745–761.
[79] Said Jabbour, Nizar Mhadhbi, Badran Raddaoui, and Lakhdar Sais. 2018. Pushing
the Envelope in Overlapping Communities Detection. In International Symposium on Intelligent Data Analysis. Springer, 151–163.
[80] Kasra Jamshidi, Rakesh Mahadasa, and Keval Vora. 2020. Peregrine: a patternaware graph mining system. In Proceedings of the Fifteenth European Conference
on Computer Systems. 1–16.
[81] Raymond Austin Jarvis and Edward A Patrick. 1973. Clustering using a similarity
measure based on shared near neighbors. IEEE Transactions on computers 100,
11 (1973), 1025–1034.
[82] Thomas Jech. 2013. Set theory. Springer Science & Business Media.
[83] Joe Jeddeloh and Brent Keeth. 2012. Hybrid memory cube new DRAM architecture increases density and performance. In VLSI Technology (VLSIT), 2012
Symposium on. IEEE, 87–88.
[84] Chuntao Jiang, Frans Coenen, and Michele Zito. 2013. A survey of frequent
subgraph mining algorithms. The Knowledge Engineering Review 28, 1 (2013),
75–105.
[85] Daxin Jiang and Jian Pei. 2009. Mining frequent cross-graph quasi-cliques. ACM
Transactions on Knowledge Discovery from Data (TKDD) 2, 4 (2009), 1–42.
[86] Aparna Joshi, Yu Zhang, Petko Bogdanov, and Jeong-Hyon Hwang. 2018. An
Efficient System for Subgraph Discovery. In 2018 IEEE International Conference
on Big Data (Big Data). IEEE, 703–712.
[87] Sang-Woo Jun, Andy Wright, Sizhuo Zhang, and Shuotao Xu. 2018. GraFBoost:
Using accelerated flash storage for external graph analytics. In 2018 ACM/IEEE
45th Annual International Symposium on Computer Architecture (ISCA). IEEE,
411–424.
[88] Vasiliki Kalavri, Vladimir Vlassov, and Seif Haridi. 2017. High-level programming abstractions for distributed graph processing. IEEE Transactions on Knowledge and Data Engineering 30, 2 (2017), 305–324.
[89] Oren Kalinsky, Benny Kimelfeld, and Yoav Etsion. 2020. The TrieJax Architecture: Accelerating Graph Operations Through Relational Joins. In Proceedings of
the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. 1217–1231.
[90] Jeremy Kepner, Peter Aaltonen, David Bader, Aydin Buluç, Franz Franchetti,
John Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, and Henning
Meyerhenke. 2016. Mathematical foundations of the GraphBLAS. In High
Performance Extreme Computing Conference (HPEC), 2016 IEEE. IEEE, 1–9.
[91] Arijit Khan. 2016. Vertex-centric graph processing: The good, the bad, and theugly. arXiv preprint arXiv:1612.07404 (2016).
[92] Wissam Khaouid, Marina Barsky, Venkatesh Srinivasan, and Alex Thomo. 2015.
K-core decomposition of large networks on a single PC. Proceedings of the VLDB
Endowment 9, 1 (2015), 13–23.
[93] Seongyun Ko and Wook-Shin Han. 2018. Turbograph++: A scalable and fast
graph analytics system. In Proceedings of the 2018 International Conference on
Management of Data. ACM, 395–410.
[94] Michihiro Kuramochi and George Karypis. 2001. Frequent subgraph discovery.
In Proceedings 2001 IEEE international conference on data mining. IEEE, 313–320.
[95] Michihiro Kuramochi and George Karypis. 2004. An efficient algorithm fordiscovering frequent subgraphs. IEEE transactions on Knowledge and Data
Engineering 16, 9 (2004), 1038–1051.
[96] Dominique Lavenier, Jean-Francois Roy, and David Furodet. 2016. DNA mapping
using Processor-in-Memory architecture. In 2016 IEEE International Conference
on Bioinformatics and Biomedicine (BIBM). IEEE, 1429–1435.
[97] Victor E Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A survey ofalgorithms for dense subgraph discovery. In Managing and Mining Graph Data.
Springer, 303–336.
[98] Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. 2006. Vertex similarity
in networks. Physical Review E 73, 2 (2006), 026120.
[99] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, andZoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11, Feb (2010), 985–1042.

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

MICRO ’21, October 18–22, 2021, Virtual Event, Greece[100] Shuangchen Li, Dimin Niu, Krishna T Malladi, Hongzhong Zheng, Bob Brennan,
and Yuan Xie. 2017. Drisa: A dram-based reconfigurable in-situ accelerator.
In 2017 50th Annual IEEE/ACM International Symposium on Microarchitecture(MICRO). IEEE, 288–301.
[101] Shuangchen Li, Cong Xu, Qiaosha Zou, Jishen Zhao, Yu Lu, and Yuan Xie. 2016.
Pinatubo: A processing-in-memory architecture for bulk bitwise operations
in emerging non-volatile memories. In Proceedings of the 53rd Annual Design
Automation Conference. 1–6.
[102] David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem forsocial networks. Journal of the American society for information science andtechnology 58, 7 (2007), 1019–1031.
[103] Siyuan Liu and Arijit Khan. 2018. An Empirical Analysis on Expressibility of
Vertex Centric Graph Processing Paradigm. In 2018 IEEE International Conference
on Big Data (Big Data). IEEE, 242–251.
[104] Gabriel H Loh. 2008. 3D-stacked memory architectures for multi-core processors.
In ACM SIGARCH computer architecture news, Vol. 36. IEEE Computer Society,453–464.
[105] Linyuan Lü and Tao Zhou. 2011. Link prediction in complex networks: A survey.
Physica A: statistical mechanics and its applications 390, 6 (2011), 1150–1170.
[106] Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoff
Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin:building customized program analysis tools with dynamic instrumentation.
Acm sigplan notices 40, 6 (2005), 190–200.
[107] Andrew Lumsdaine, Douglas Gregor, Bruce Hendrickson, and Jonathan W. Berry.
2007. Challenges in Parallel Graph Processing. Par. Proc. Let. 17, 1 (2007), 5–20.
[108] Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, IlanHorn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for largescale graph processing. In Proceedings of the 2010 ACM SIGMOD International
Conference on Management of data. ACM, 135–146.
[109] Jasmina Malicevic, Baptiste Lepers, and Willy Zwaenepoel. 2017. Everything
you always wanted to know about multicore graph processing but were afraid
to ask. In 2017 USENIX Annual Technical Conference (USENIX ATC’17). 631–643.
[110] Kiran Kumar Matam, Gunjae Koo, Haipeng Zha, Hung-Wei Tseng, and Murali
Annavaram. 2019. GraphSSD: graph semantics aware SSD. In Proceedings of the
46th International Symposium on Computer Architecture. 116–128.
[111] Daniel Mawhirter, Sam Reinehr, Connor Holmes, Tongping Liu, and Bo Wu.
2019. GraphZero: Breaking Symmetry for Efficient Graph Mining. arXiv preprint
arXiv:1911.12877 (2019).
[112] Daniel Mawhirter and Bo Wu. 2019. AutoMine: harmonizing high-level abstraction and high performance for graph mining. In Proceedings of the 27th ACM
Symposium on Operating Systems Principles. ACM, 509–523.
[113] Robert Ryan McCune, Tim Weninger, and Greg Madey. 2015. Thinking like avertex: a survey of vertex-centric frameworks for large-scale distributed graphprocessing. ACM Computing Surveys (CSUR) 48, 2 (2015), 25.
[114] Ulrich Meyer and Peter Sanders. 2003. ∆-stepping: a parallelizable shortest path
algorithm. Journal of Algorithms 49, 1 (2003), 114–152.
[115] Gary L Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. 2015. Improved
parallel algorithms for spanners and hopsets. In Proceedings of the 27th ACM
Symposium on Parallelism in Algorithms and Architectures. ACM, 192–201.
[116] Sparsh Mittal, Jeffrey S Vetter, and Dong Li. 2014. Improving energy efficiencyof embedded DRAM caches for high-end computing systems. In Proceedings ofthe 23rd international symposium on High-performance parallel and distributed
computing. 99–110.
[117] O. Mutlu et al. 2019. Processing Data Where It Makes Sense: Enabling In-Memory
Computation. MicPro (2019).
[118] Onur Mutlu, Saugata Ghose, Juan Gómez-Luna, and Rachata Ausavarungnirun. 2020. A Modern Primer on Processing in Memory. arXiv preprint
arXiv:2012.03112 (2020).
[119] Anirban Nag, CN Ramachandra, Rajeev Balasubramonian, Ryan Stutsman,
Edouard Giacomin, Hari Kambalasubramanyam, and Pierre-Emmanuel Gaillardon. 2019. Gencache: Leveraging in-cache operators for efficient sequencealignment. In Proceedings of the 52nd Annual IEEE/ACM International Symposiumon Microarchitecture. 334–346.
[120] Lifeng Nai, Ramyad Hadidi, Jaewoong Sim, Hyojong Kim, Pranith Kumar, andHyesoon Kim. 2017. Graphpim: Enabling instruction-level PIM offloading
in graph computing frameworks. In High Performance Computer Architecture(HPCA), 2017 IEEE International Symposium on. IEEE, 457–468.
[121] Neo4j, Inc. 2019. The Neo4j Graph Algorithms User Guide v3.5. https://neo4j.
com/docs/graph-algorithms/current.
[122] Geraldo F Oliveira, Juan Gómez-Luna, Lois Orosa, Saugata Ghose, Nandita
Vijaykumar, Ivan Fernandez, Mohammad Sadrosadati, and Onur Mutlu. 2021.
DAMOV: A New Methodology and Benchmark Suite for Evaluating Data Movement Bottlenecks. arXiv preprint arXiv:2105.03725 (2021).
[123] Muhammet Mustafa Ozdal, Serif Yesil, Taemin Kim, Andrey Ayupov, John Greth,
Steven Burns, and Ozcan Ozturk. 2016. Energy efficient architecture for graphanalytics accelerators. In Computer Architecture (ISCA), 2016 ACM/IEEE 43rd
Annual International Symposium on. IEEE, 166–177.

296[124] Subhankar Pal, Jonathan Beaumont, Dong-Hyeon Park, Aporva Amarnath, Siying Feng, Chaitali Chakrabarti, Hun-Seok Kim, David Blaauw, Trevor Mudge,
and Ronald Dreslinski. 2018. Outerspace: An outer product based sparse matrix multiplication accelerator. In 2018 IEEE International Symposium on High
Performance Computer Architecture (HPCA). IEEE, 724–736.
[125] Keshav Pingali, Donald Nguyen, Milind Kulkarni, Martin Burtscher, M Amber
Hassaan, Rashid Kaleem, Tsung-Hsien Lee, Andrew Lenharth, Roman Manevich,and Mario Méndez-Lojo. 2011. The tao of parallelism in algorithms. In ACM
Sigplan Notices, Vol. 46. ACM, 12–25.
[126] T Ramraj and R Prabhakar. 2015. Frequent subgraph mining algorithms-a survey.
Procedia Computer Science 47 (2015), 197–204.
[127] Gengyu Rao, Jingji Chen, Jason Yik, and Xuehai Qian. 2021. IntersectX: An
Accelerator for Graph Mining. arXiv preprint arXiv:2012.10848 (2021).
[128] Saif Ur Rehman, Asmat Ullah Khan, and Simon Fong. 2012. Graph mining:
A survey of graph mining techniques. In Seventh International Conference on
Digital Information Management (ICDIM 2012). IEEE, 88–92.
[129] Nicholas Rhodes, Peter Willett, Alain Calvet, James B Dunbar, and Christine
Humblet. 2003. CLIP: similarity searching of 3D databases using clique detection.
Journal of chemical information and computer sciences 43, 2 (2003), 443–448.
[130] Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando
Silva. 2019. A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets. arXiv preprint arXiv:1910.13011(2019).
[131] Ian Robinson, Jim Webber, and Emil Eifrem. 2013. Graph databases. " O’Reilly
Media, Inc.".
[132] Ryan A. Rossi and Nesreen K. Ahmed. 2016. An Interactive Data Repository with
Visual Analytics. SIGKDD Explor. 17, 2 (2016), 37–41. http://networkrepository.
com[133] Ryan A Rossi and Nesreen K Ahmed. 2016. An interactive data repository withvisual analytics. ACM SIGKDD Explorations Newsletter 17, 2 (2016), 37–41.
[134] Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013. X-stream: Edgecentric graph processing using streaming partitions. In Proceedings of the TwentyFourth ACM Symposium on Operating Systems Principles. ACM, 472–488.
[135] Sherif Sakr, Angela Bonifati, Hannes Voigt, Alexandru Iosup, Khaled Ammar,
Renzo Angles, Walid Aref, Marcelo Arenas, Maciej Besta, Peter A Boncz, et al.
2020. The Future is Big Graphs! A Community View on Graph Processing
Systems. arXiv preprint arXiv:2012.06171 (2020).
[136] Semih Salihoglu and Jennifer Widom. 2014. Optimizing graph algorithms on
Pregel-like systems. Proceedings of the VLDB Endowment 7, 7 (2014), 577–588.
[137] Satu Elisa Schaeffer. 2007. Graph clustering. Computer science review 1, 1 (2007),
27–64.
[138] Thomas Schank. 2007. Algorithmic aspects of triangle-based network analysis.
Phd in computer science, University Karlsruhe 3 (2007).
[139] Vivek Seshadri, Abhishek Bhowmick, Onur Mutlu, Phillip B Gibbons, Michael A
Kozuch, and Todd C Mowry. 2014. The dirty-block index. ACM SIGARCH
Computer Architecture News 42, 3 (2014), 157–168.
[140] Vivek Seshadri, Yoongu Kim, Chris Fallin, Donghyuk Lee, Rachata Ausavarungnirun, Gennady Pekhimenko, Yixin Luo, Onur Mutlu, Phillip B Gibbons, andMichael A Kozuch. 2013. RowClone: fast and energy-efficient in-DRAM bulk
data copy and initialization. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture. 185–197.
[141] Vivek Seshadri, Donghyuk Lee, Thomas Mullins, Hasan Hassan, Amirali
Boroumand, Jeremie Kim, Michael A Kozuch, Onur Mutlu, Phillip B Gibbons,and Todd C Mowry. 2017. Ambit: In-memory accelerator for bulk bitwise operations using commodity DRAM technology. In Proceedings of the 50th Annual
IEEE/ACM International Symposium on Microarchitecture. ACM, 273–287.
[142] Xuanhua Shi, Zhigao Zheng, Yongluan Zhou, Hai Jin, Ligang He, Bo Liu, andQiang-Sheng Hua. 2018. Graph processing on GPUs: A survey. ACM Computing
Surveys (CSUR) 50, 6 (2018), 81.
[143] Yossi Shiloach and Uzi Vishkin. 1980. An O (log n) parallel connectivity algorithm.
Technical Report. Computer Science Department, Technion.
[144] Yossi Shiloach and Uzi Vishkin. 1982. An O (logn) parallel connectivity algorithm.
Journal of Algorithms 3, 1 (1982), 57–67.
[145] Julian Shun and Guy E Blelloch. 2013. Ligra: a lightweight graph processing
framework for shared memory. In ACM SIGPLAN Notices, Vol. 48. 135–146.
[146] Julian Shun and Kanat Tangwongsan. 2015. Multicore triangle computations
without tuning. In Data Engineering (ICDE), 2015 IEEE 31st International Conference on. IEEE, 149–160.
[147] S Skiena. 1990. Dijkstra’s algorithm. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Reading, MA: Addison-Wesley(1990), 225–227.
[148] Edgar Solomonik, Maciej Besta, Flavio Vella, and Torsten Hoefler. 2017. Scaling
betweenness centrality using communication-efficient sparse matrix multiplication. In Proceedings of the International Conference for High Performance
Computing, Networking, Storage and Analysis. ACM, 47.
[149] Linghao Song, Youwei Zhuo, Xuehai Qian, Hai Li, and Yiran Chen. 2018. GraphR:
Accelerating graph processing using ReRAM. In High Performance Computer
Architecture (HPCA), 2018 IEEE International Symposium on. IEEE, 531–543.

MICRO ’21, October 18–22, 2021, Virtual Event, Greece

Besta et al.

[150] Victor Spirin and Leonid A Mirny. 2003. Protein complexes and functional
modules in molecular networks. Proceedings of the National Academy of Sciences
100, 21 (2003), 12123–12128.
[151] Narayanan Sundaram, Nadathur Satish, Md Mostofa Ali Patwary, Subramanya R
Dulloor, Michael J Anderson, Satya Gautam Vadlamudi, Dipankar Das, andPradeep Dubey. 2015. Graphmat: High performance graph analytics madeproductive. Proceedings of the VLDB Endowment 8, 11 (2015), 1214–1225.
[152] Michael Sutton, Tal Ben-Nun, and Amnon Barak. [n. d.]. Optimizing Parallel
Graph Connectivity Computation via Subgraph Sampling. ([n. d.]).
[153] Ichigaku Takigawa and Hiroshi Mamitsuka. 2013. Graph mining: procedure,application to drug discovery and recent advances. Drug discovery today 18, 1-2(2013), 50–57.
[154] Lei Tang and Huan Liu. 2010. Graph mining applications to social network
analysis. In Managing and Mining Graph Data. Springer, 487–513.
[155] Ben Taskar, Ming-Fai Wong, Pieter Abbeel, and Daphne Koller. 2004. Link
prediction in relational data. In Advances in neural information processing systems.
659–666.
[156] Carlos HC Teixeira, Alexandre J Fonseca, Marco Serafini, Georgos Siganos,
Mohammed J Zaki, and Ashraf Aboulnaga. 2015. Arabesque: a system for
distributed graph mining. In Proceedings of the 25th Symposium on Operating
Systems Principles. ACM, 425–440.
[157] Sutapat Thiprungsri and Miklos A Vasarhelyi. 2011. Cluster Analysis for Anomaly Detection in Accounting Data: An Audit Approach. International Journal of
Digital Accounting Research 11 (2011).
[158] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. 2006. The worst-case timecomplexity for generating all maximal cliques and computational experiments.
Theor. Comput. Sci. 363, 1 (2006), 28–42. https://doi.org/10.1016/j.tcs.2006.06.015[159] Julian R Ullmann. 1976. An algorithm for subgraph isomorphism. Journal of
the ACM (JACM) 23, 1 (1976), 31–42.
[160] Kenzo Van Craeynest, Shoaib Akram, Wim Heirman, Aamer Jaleel, and Lieven
Eeckhout. 2013. Fairness-aware scheduling on single-ISA heterogeneous multicores. In Proceedings of the 22nd international conference on Parallel architecturesand compilation techniques. IEEE, 177–187.
[161] Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry
Xu. 2018. Rstream: marrying relational algebra with streaming for efficientgraph mining on a single machine. In 13th {USENIX } Symposium on Operating
Systems Design and Implementation ( {OSDI } 18). 763–782.
[162] Liang Wang, Ke Hu, and Yi Tang. 2014. Robustness of link-prediction algorithm
based on similarity and application to biological networks. Current Bioinformatics 9, 3 (2014), 246–252.
[163] Takashi Washio and Hiroshi Motoda. 2003. State of the art of graph-based data
mining. Acm Sigkdd Explorations Newsletter 5, 1 (2003), 59–68.
[164] Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods
and applications. Vol. 8. Cambridge university press.
[165] Andrew Waterman, Yunsup Lee, David A Patterson, and Krste Asanovic. 2011.
The risc-v instruction set manual, volume i: Base user-level isa. EECS Department,
UC Berkeley, Tech. Rep. UCB/EECS-2011-62 116 (2011).
[166] Andrew Shell Waterman. 2016. Design of the RISC-V instruction set architecture.
Ph.D. Dissertation. UC Berkeley.
[167] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, andS Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE
Transactions on Neural Networks and Learning Systems (2020).

297[168] Xin Xin, Youtao Zhang, and Jun Yang. 2020. ELP2IM: Efficient and Low Power
Bitwise Operation Processing in DRAM. In 2020 IEEE International Symposium
on High Performance Computer Architecture (HPCA). IEEE, 303–314.
[169] Chongchong Xu, Chao Wang, Lei Gong, Lihui Jin, Xi Li, and Xuehai Zhou. 2018.
Domino: Graph Processing Services on Energy-Efficient Hardware Accelerator.
In 2018 IEEE International Conference on Web Services (ICWS). IEEE, 274–281.
[170] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful
are graph neural networks? arXiv preprint arXiv:1810.00826 (2018).
[171] Da Yan, Hongzhi Chen, James Cheng, M Tamer Özsu, Qizhen Zhang, and John
Lui. 2017. G-thinker: big graph mining made easier and faster. arXiv preprint
arXiv:1709.03110 (2017).
[172] Da Yan, James Cheng, Kai Xing, Yi Lu, Wilfred Ng, and Yingyi Bu. 2014. Pregelalgorithms for graph connectivity problems with performance guarantees. Proceedings of the VLDB Endowment 7, 14 (2014), 1821–1832.
[173] Da Yan, Wenwen Qu, Guimu Guo, and Xiaoling Wang. 2020. PrefixFPM: A Parallel Framework for General-Purpose Frequent Pattern Mining. In Proceedingsof the 36th IEEE International Conference on Data Engineering (ICDE) 2020.
[174] Mingyu Yan, Lei Deng, Xing Hu, Ling Liang, Yujing Feng, Xiaochun Ye, Zhimin
Zhang, Dongrui Fan, and Yuan Xie. 2020. Hygcn: A gcn accelerator withhybrid architecture. In 2020 IEEE International Symposium on High Performance
Computer Architecture (HPCA). IEEE, 15–29.
[175] Pengcheng Yao, Long Zheng, Zhen Zeng, Yu Huang, Chuangyi Gui, Xiaofei Liao,
Hai Jin, and Jingling Xue. [n. d.]. A Locality-Aware Energy-Efficient Accelerator
for Graph Mining Applications. ([n. d.]).
[176] Pengcheng Yao, Long Zheng, Zhen Zeng, Yu Huang, Chuangyi Gui, Xiaofei Liao,
Hai Jin, and Jingling Xue. 2020. A Locality-Aware Energy-Efficient Accelerator
for Graph Mining Applications. In 2020 53rd Annual IEEE/ACM International
Symposium on Microarchitecture (MICRO). IEEE, 895–907.
[177] Mingxing Zhang, Youwei Zhuo, Chao Wang, Mingyu Gao, Yongwei Wu, Kang
Chen, Christos Kozyrakis, and Xuehai Qian. 2018. GraphP: Reducing Communication for PIM-based Graph Processing with Efficient Data Partition. In High
Performance Computer Architecture (HPCA), 2018 IEEE International Symposium
on. IEEE, 544–557.
[178] Yun Zhang, Faisal N Abu-Khzam, Nicole E Baldwin, Elissa J Chesler, Michael A
Langston, and Nagiza F Samatova. 2005. Genome-scale computational approaches to memory-intensive applications in systems biology. In SC’05: Proceedings of the 2005 ACM/IEEE Conference on Supercomputing. IEEE, 12–12.
[179] Cheng Zhao, Zhibin Zhang, Peng Xu, Tianqi Zheng, and Xueqi Cheng. 2019.
Kaleido: An Efficient Out-of-core Graph Mining System on A Single Machine.
arXiv preprint arXiv:1905.09572 (2019).
[180] Kangfei Zhao and Jeffrey Xu Yu. 2017. All-in-one: Graph processing in rdbmss
revisited. In Proceedings of the 2017 ACM International Conference on Managementof Data. 1165–1180.
[181] Long Zheng, Jieshan Zhao, Yu Huang, Qinggang Wang, Zhen Zeng, Jingling
Xue, Xiaofei Liao, and Hai Jin. 2020. Spara: An Energy-Efficient ReRAM-Based
Accelerator for Sparse Graph Analytics Applications. In 2020 IEEE International
Parallel and Distributed Processing Symposium (IPDPS). IEEE, 696–707.
[182] Minxuan Zhou, Mohsen Imani, Saransh Gupta, Yeseong Kim, and Tajana Rosing.
2019. GRAM: graph processing in a ReRAM-based computational memory.. In
ASP-DAC. 591–596.
[183] Youwei Zhuo, Chao Wang, Mingxing Zhang, Rui Wang, Dimin Niu, Yanzhi
Wang, and Xuehai Qian. 2019. Graphq: Scalable PIM-based graph processing. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on
Microarchitecture. 712–725.