Electrical and Computer Engineering Electrical and Computer Engineering
Electrical and Computer Engineering April 2023 4 Dr. David Kaeli Dr. Devesh
Tiwari Second Reader Name Third Reader Name Fourth Reader Name Fifth Reader
Name Dr. Srinivas Tadigadapa Dr. Waleed Meleis

Connecting dots faster, one accelerator at a time.

###### Contents

  1. 0 Introduction
    1. 1 Background and Motivation
    2. 2 Challenges in Accelerating Graph Computing
      1. 1 Scalability Concerns in Graph Neural Networks
      2. 2 Task-Level Parallelism in Graph Computations
      3. 3 Data Spatial Locality and Computational Irregularity
    3. 3 Objectives and Contributions
    4. 4 Thesis Proposal Organization
  2. 1 Preliminaries
    1. 1 Graph Theory Basics
      1. 1 Graph Properties
      2. 2 Types of Graphs
      3. 3 Graph Representation
      4. 4 Graph Transformation
    2. 2 Machine Learning on Graphs
      1. 1 Graph Neural Networks
      2. 2 Graph Convolutional Networks
      3. 3 Graph Isomorphism Networks
    3. 3 Graph Neural Network Frameworks
    4. 4 Accelerators: An Overview
      1. 1 Unique Advantages of Accelerators
      2. 2 Advantages and Disadvantages of Designing Accelerators
        1. Advantages
        2. Disadvantages
  3. 2 Related Work
    1. 1 Graph Computing Benchmark Suites
    2. 2 Prior GNN Accelerators
  4. 3 GNN Workload Characterization
    1. 1 Motivation for Characterizing GNN Workloads
    2. 2 Prior Work on GNN Characterization
    3. 3 Input Graph Types
    4. 4 Benchmark Suite Design
    5. 5 Profiling Methodology
      1. 1 Experimental Platform
      2. 2 Profiling Tools
      3. 3 Metrics of Interest
      4. 4 Multi-GPU Implementations
    6. 6 Benchmarking Results
      1. 1 Execution Time Breakdown
      2. 2 Instruction Mix and GFLOPS/GIOPS Analysis
      3. 3 Stalls and Cache Analysis
      4. 4 Sparsity during GNN training
      5. 5 Scalability of GNN training using multi-GPU systems
    7. 7 GNNMark Summary
  5. 4 Acceleration of GNNs
    1. 1 Motivation for SpGEMM kernel acceleration
    2. 2 Background on SpGEMM
    3. 3 MAP - CSR Storage Format
      1. 1 MAP-CSR Implementation
      2. 2 MAP-CSR Advantages
      3. 3 MAP-CSR Limitations
    4. 4 SMASH Kernel
      1. 1 Memory computation phase
      2. 2 Product Computation Phase
        1. Prefetching
        2. Hashing
        3. Write-back
      3. 3 SMASH Version 1: Atomic Hashing
      4. 4 SMASH Version 2: Tokenization
      5. 5 SMASH Version 3: Pipelining
    5. 5 Evaluation
    6. 6 SMASH Summary
  6. 5 Summary and Plans
    1. 1 Work Completed to Date
    2. 2 Plans to Complete The Thesis

###### List of Figures

  1. 1 Graph Computing Applications
  2. 1 An example of a social network graph and its corresponding adjacency matrix. Each node in the graph is associated with a feature vector that contains the node’s attributes.
  3. 2 Analysis of Graph Neural Networks, demonstrating the propagation of node properties influenced by the graph’s topology.
  4. 1 Execution breakdown, reported as the percent of total execution time, for individual operations across the different workloads of GNNMark.
  5. 2 Breakdown of fp32 vs. int32 instructions across the different workloads in GNNMark.
  6. 3 GFLOPS and GIOPS across the different workloads in GNNMark.
  7. 4 Stall breakdown across operations in GNNMark.
  8. 5 L1-D and L2-cache hit ratios, and divergent load ratios for GNNMark workloads.
  9. 6 Average sparsity in the data transferred from CPU-to-GPU during GNN training in GNNMark workloads.
  10. 7 Sparsity heat map for DeepGCN when running on the MOLHIV dataset.
  11. 8 Multi-GPU performance scaling.
  12. 1 World exposure graph centrality, as generated using an SpGEMM kernel (with nodes as cities, node size proportional to Maximal Frontier Betweenness Centrality (MFBC), edges as air travel corridors, and colors representing countries)
  13. 2 Methods of implementing the two distinct phases of SpGEMM kernel
  14. 3 Matrix Multiplication Methods
  15. 4 MAP-CSR Speedup
  16. 5 Conventional CSR Format
  17. 6 The MAP-CSR Format
  18. 7 SMASH Architecture
  19. 8 SMASH Speedup
  20. 9 SMASH Pipeline Stages
  21. 10 Speedup Matrix
  22. 11 Cycle Distribution
  23. 12 Speedup Matrix

###### List of Tables

  1. 1 Summary of Objectives and Contributions
  2. 1 Comparison between PyTorch Geometric (PyG) and Deep Graph Library (DGL)
  3. 1 Comparison of prior state-of-the-art GNN accelerators’ support for different graph neural network models. The table indicates the support provided by accelerator for GCN, GIN, GAT, SAGE, PNA, and DGN models
  4. 2 Comparison of various Graph Neural Network (GNN) Accelerators on optimization techniques incorporated
  5. 1 Workloads in GNNMark Benchmark Suite.
  6. 2 Workloads in GNNMark Benchmark Suite.
  7. 1 Plan for Completing the Thesis

## Acronyms

CSR

    Compressed Sparse Row
DRAM

    Dynamic Random Access Memory
FMA

    Floating-Point Multiply-Add
GCN

    Graph Convolutional Network
GNN

    Graph Neural Networks
MAP-CSR

    Memory Aligned Parallel - Compressed Sparse Row
RMAT

    Recursive Matrix
SIMD

    Single Instruction, Multiple Data
SMASH

    Sparse Matrix Atomic Scratchpad Hashing
SPAD

    Scratchpad
SpGEMM

    Sparse Matrix-Matrix Multiply

The advent of Graph Neural Networks (GNNs) has revolutionized the field of
machine learning, offering a novel paradigm for learning on graph-structured
data. Unlike traditional neural networks, GNNs are capable of capturing
complex relationships and dependencies inherent in graph data, making them
particularly suited for a wide range of applications including social network
analysis, molecular chemistry, and network security. The impact of GNNs in
these domains is profound, enabling more accurate models and predictions, and
thereby contributing significantly to advancements in these fields.

GNNs, with their unique structure and operation, present new computational
challenges compared to conventional neural networks. This requires
comprehensive benchmarking and a thorough characterization of GNNs to obtain
insight into their computational requirements and to identify potential
performance bottlenecks. In this thesis, we aim to develop a better
understanding of how GNNs interact with the underlying hardware and will
leverage this knowledge as we design specialized accelerators and develop new
optimizations, leading to more efficient and faster GNN computations.

A pivotal component within GNNs is the Sparse General Matrix-Matrix
Multiplication (SpGEMM) kernel, known for its computational intensity and
irregular memory access patterns. In this thesis, we address the challenges
posed by SpGEMM by implementing a highly optimized hashing-based SpGEMM kernel
tailored for a custom accelerator. This optimization is crucial to enhancing
the performance of GNN workloads, ensuring that the acceleration potential of
custom hardware is fully realized.

Synthesizing these insights and optimizations, we design a state-of-the-art
hardware accelerator capable of efficiently handling various GNN workloads.
Our accelerator architecture is built on our characterization of GNN
computational demands, providing clear motivation for our approach.
Furthermore, we extend our exploration to emerging GNN workloads in the domain
of graph neural networks. This exploration into novel models underlines our
comprehensive approach, as we strive to enable accelerators that are not just
performant, but also versatile, able to adapt to the evolving landscape of
graph computing.

##  Chapter 0 Introduction

> In the vast landscape of computation, graphs stand as the bridges connecting
> isolated islands of data, creating a coherent world from chaos.
>
> Inspired by Donald Knuth

Graph computing traces its lineage back to some of the earliest pursuits of
mathematics. Historically, graph theory took its first steps in the $18^{th}$
century with Leonhard Euler’s formulation of the Seven Bridges of Königsberg
problem, where he proved that it was impossible to traverse each of the city’s
seven bridges once and only once without retracing any step [48]. This
abstract representation allowed for the modeling of a wide variety of systems,
from social interactions to intricate molecular structures. However, for much
of its history, graph theory remained primarily an academic endeavor with
limited computational exploration, owing to the computational constraints of
the era.

With the digital revolution of the late 20th century, computing power saw
unprecedented growth. As industries started grappling with vast amounts of
interconnected data—from the nascent Internet’s web pages, to the massive
social networks—there emerged, a pressing need for effective means to process
and analyze this data. It was in this backdrop that graph computing began its
ascent, evolving from theoretical speculations to practical, essential
toolsets. The challenge shifted from simply understanding graph structures to
efficiently processing them, leading to the exploration of specialized
hardware and software solutions. This combination of data-centric challenges
and available computational power provides the motivation for this thesis.

###  1 Background and Motivation

Graphs have seen a growing role in modern computational domains. With the rise
of vast amounts of complex, interconnected data, traditional data processing
methods have often fallen short. Enter Graph Neural Networks (GNNs), a
specialized neural network architecture designed to handle such data and
extract insights from these intricate connections. GNNs have shown remarkable
potential in various domains, offering solutions where conventional methods
have struggled. Their capacity to model relational data naturally fits a wide
range of applications, spanning from social network analysis to molecular
chemistry. To delve deeper into their capabilities, here is a list of GNN
applications.

Figure 1: Graph Computing Applications

  1. 1.

Social Network Analysis: Graphs are essential in Social Network Analysis (SNA)
to understand interactions within networks such as Facebook and Twitter. By
examining these structures, SNA can detect key influencers, community
structures, and predict potential trends or misinformation spread [28, 144,
158, 77].

  2. 2.

Computer Networks: Graphs represent devices and communication pathways in
computer networks, aiding in tasks such as routing and fault detection. Graph-
based algorithms optimize network design and manage potential vulnerabilities
[70, 58, 175, 134].

  3. 3.

Hardware Security: Circuits can be represented as graphs to detect anomalies,
such as potential Hardware Trojans. Graph Neural Networks (GNNs) further
enhance detection capabilities, pinpointing subtle irregularities [4, 65, 165,
125, 97, 126].

  4. 4.

Bioinformatics: In bioinformatics, graphs are used to model entities, for
example, protein interactions and genetic sequences. They help identify
conserved patterns in DNA or RNA, study metabolic pathways, and analyze
genomic variations [17, 95].

  5. 5.

Financial Markets: Graphs illuminate interactions in financial markets. They
help analysts identify correlated assets, assess systemic risks, and optimize
algorithmic trading strategies [46, 18, 66].

  6. 6.

Neuroscience: Representing the brain’s complex structure, graphs in
neuroscience help analyze neural networks, understand (Functional magnetic
resonance imaging) fMRI data, and study the brain’s topological properties
[133, 22, 50, 14].

  7. 7.

Transportation and Logistics: Graphs map transportation networks, aiding in
solving optimization problems such as route planning and vehicle routing. They
help ensure efficient deliveries, optimize public transit, and adapt to
disruptions [59, 89, 39, 162, 75].

  8. 8.

Chemistry: Molecular structures in chemistry are represented using graphs,
predicting chemical properties, identifying isomers, and aiding in drug design
[143, 142, 11, 152].

  9. 9.

Physics: Graphs in physics are used to model quantum states, lattice
structures, and network systems. They aid in understanding quantum computing,
material properties, and system dynamics [27, 154, 12, 68, 128].

  10. 10.

Machine Learning and Data Mining: In machine learning, graphs facilitate
clustering, classification, and feature extraction. They model non-Euclidean
data, aiding in semi-supervised learning and geometric deep learning [176, 30,
127, 21, 153, 25, 125].

  11. 11.

Telecommunications: Graphs underpin the telecommunications sector, assisting
in routing, optimization, and network slicing for 5G technologies [54, 149, 3,
113, 141].

This list showcases the wide impact of concepts from graph theory across a
multitude of domains. Figure 1 illustrates specific applications of graphs
across various domains. As interconnected systems become increasingly central
to understanding our world, the role of graph theory is likely to grow even
more essential.

In the wake of the rising importance of graph-based computations, the hardware
landscape within the compute industry began to undergo key shifts. Traditional
Central Processing Units (CPUs), initially designed for sequential tasks,
started incorporating SIMD-based graph extensions to enhance parallel
processing capabilities [174].Graphics Processing Units (GPUs), with their
inherent parallelism, were enhanced with kernel support tailored specifically
for graph algorithms [139, 121]. Beyond these general-purpose processors, the
industry also witnessed the advent of domain-specific accelerators [124, 74,
164, 94], specifically crafted to speedup graph computations, addressing the
unique challenges and demands that graph algorithms present.

On the software front, comprehensive software stacks have been designed from
the ground up, specifically focusing on facilitating efficient graph
processing. Libraries such as PyTorch-Geometric [49] and Deep Graph Library
(DGL) [148] emerged, offering robust platforms for researchers and developers
to implement and optimize graph algorithms. These software advances, in tandem
with hardware innovations, have pushed the field of graph computing further
forward. However, as with any rapidly evolving domain, while significant
strides have been made, the journey is far from over. The vast potential of
graph computing continues to present both challenges and opportunities that
require further exploration and innovation.

###  2 Challenges in Accelerating Graph Computing

As promising as GNNs are, they are not without their computational challenges.
Given the inherently recursive nature of GNNs, coupled with the irregular
structure of many real-world graphs, we find significant bottlenecks in terms
of their scalability and performance. Parallelizing GNN computations, which
seems to be a logical solution given the abundance of task-level parallelism
in graph processing, is riddled with data dependencies. The core challenges
lie in the low spatial locality of data, which results in memory access
inefficiencies and the computation stalls, making it difficult to achieve
scalable parallel performance. Addressing these challenges is pivotal to
harnessing the full potential of GNNs and making them a feasible solution for
large-scale, real-world applications.

####  1 Scalability Concerns in Graph Neural Networks

GNNs present unique challenges in handling large graphs, which often involve
billions to trillions of nodes and edges [51]. The computational and memory
demands of processing such exascale graphs escalate rapidly, often making
computations infeasible on standard computational infrastructures. For
instance, the Friendster social network graph comprises over 65 million nodes
and 1.8 billion edges [161]. When applying GNNs to this magnitude of data, the
iterative and recursive nature of these networks requires massive memory
bandwidth and computational power. Even more complex graphs from biological
and cosmological simulations are looming on the horizon, potentially reaching
the exabyte scale [8]. Addressing the scalability challenges with GNNs on
these graphs will be paramount to unlocking new scientific discoveries and
advances in several fields.

####  2 Task-Level Parallelism in Graph Computations

Graph computations inherently possess a rich vein of task-level parallelism,
given that many operations can theoretically be conducted simultaneously
across different nodes or subgraphs [101]. This natural parallelism emerges
from the decentralized structure of graphs, where independent sub-tasks can be
identified and processed in parallel, especially in sparse graph computations.
However, this potential for parallelism is intermingled with intricate data
dependencies among nodes and edges. These dependencies arise from the
interconnections in the graph, leading to situations where the output of one
task is contingent upon the result of another, thus necessitating
synchronization and communication [16]. Consequently, fully capitalizing on
the inherent task-level parallelism, while managing data dependencies, poses
significant challenges, requiring advanced strategies to ensure efficiency and
accuracy in graph computations.

####  3 Data Spatial Locality and Computational Irregularity

Graph computations, especially in the realm of GNNs and large-scale graph
analytics, encounter two predominant challenges: 1) data spatial locality and
2) computational irregularity [34]. First, the lack of data spatial locality
implies that successive operations might access data dispersed across memory,
leading to increased cache misses and degraded memory performance. Graphs,
being inherently non-uniform, result in unpredictable memory access patterns,
often unable to take advantage of cache hierarchies in modern processors [86].
Second, computational irregularity in graph algorithms surfaces due to the
diverse node degrees and edge distributions, causing workload imbalance in
parallel computing scenarios. This irregularity complicates efficient
scheduling on parallel hardware and requires sophisticated load-balancing
techniques to mitigate performance imbalance [81]. Both challenges pose
barriers to fully realize the benefits of parallelism in graph computing.

###  3 Objectives and Contributions

The development of a graph accelerator tailored for GNN workloads requires
following a systematic approach. Initially, our efforts are concentrated on
conducting comprehensive benchmarks and characterizations of the GNN
workloads, along with the various kernels targeted for optimization.
Subsequently, our attention shifts to addressing a significant bottleneck in
GNN workloads—the SpGEMM kernel—by devising and implementing an optimized
version specifically for a custom accelerator. Finally, we integrate these
insights and optimizations to architect a hardware accelerator, specifically
designed to enhance the performance across a diverse range of GNN workloads. A
summary of these objectives and their associated contributions is presented in
Table 1.

Objective |  Contribution
---|---
Analyze the architectural impact of computing Graph Neural Networks. |  Provide a benchmark suite for comprehensive evaluation of how different architectural components influence the performance and efficiency of GNN computations.
Accelerate SpGEMM kernel on custom accelerator. |  Propose and implement optimization strategies for the SpGEMM kernel, resulting in significant performance improvements on a custom hardware accelerator.
Design a new accelerator to accelerate multiple GNN workloads. |  Develop a novel hardware accelerator architecture tailored for various GNN workloads, demonstrating versatility and improved performance across different graph inputs.
Table 1: Summary of Objectives and Contributions

###  4 Thesis Proposal Organization

  * •

Chapter Enabling Accelerators for Graph Computing: This chapter sets the stage
for the thesis by highlighting the significance and impact of computations
based on graph structures.

  * •

Chapter 1: This chapter provides background on the foundations of graph
theory, providing a comprehensive overview of the various types of graphs,
their properties and their representations. It also introduces machine
learning on graphs, with a specific focus on Graph Neural Networks (GNNs),
explaining their structure, functionality and applications.

  * •

Chapter 2: This chapter presents a thorough review of previous work in the
domain, discussing existing approaches and solutions in workload
characterization, GPU acceleration, Coarse-Grained Reconfigurable Arrays
(CGRAs), and custom accelerators specifically designed for GNN workloads.

  * •

Chapter 3: We present a GNN benchmark suite in this chapter, offering a
curated collection of workloads and tools to assess the performance of GNN
computations. In addition, we conduct extensive analysis of the architectural
requirements to efficiently run GNN workloads, examining how different
components and configurations affect overall performance.

  * •

Chapter 4: Building on the insights gained from the previous chapters, we
propose a new custom hardware solution designed to accelerate GNN workloads.
We present details of the design requirements, resulting architecture, and
implementation of the solution, describing how we address the unique
challenges posed by GNN computations.

  * •

Chapter 5: The final chapter of the thesis summarizes the key findings and
contributions, discussing both the completed aspects of the research and
outlining avenues for future work to be completed as a part of the thesis.

##  Chapter 1 Preliminaries

Before delving into the details of our accelerator proposal for graph
computing, we explore the foundational concepts of graph computing and
accelerator design. This chapter serves as a compass, offering a systematic
overview of the essential background, terminology and challenges that
characterize graph computing, as well as its interaction with hardware
accelerators. By first reviewing these foundational elements, this chapter
aims to provide the necessary context and knowledge required to understand GNN
accelerator design.

###  1 Graph Theory Basics

Graph theory is a field within mathematics that explores the structure of
interconnected nodes and edges. Graphs have gained widespread recognition for
their ability to represent non-euclidean data. Graphs can represent many real-
world problems, from network topologies and social networks to transportation
systems and molecular structures. This section provides an overview of the
fundamental elements of graphs, before diving into the use of graph-based
applications in machine learning. Figure 1 represents a social network graph,
demonstrating how individuals are connected. We also provide the associated
adjacency matrix, which quantitatively captures these connections.
Additionally, for each individual in the network, a feature vector is provided
that captures various attributes or characteristics associated with that
individual.

Mathematically, a graph $G$ is a pair of vertices (i.e., nodes) $V$ and edges
$E$, that is represented as:

$G=(V,E)$ (1)

where $V$ is a set of vertices, and $E$ is an unordered set of pairs of
vertices. A singular edge $e$ within the set of edges $E$ is represented as
$e=\\{x,y\\}$ or simply $e=xy$, where $x$ and $y$ are endpoints (nodes) of the
edge. $x$ and $y$ are said to be neighbors or adjacent nodes in the graph $G$.

Figure 1: An example of a social network graph and its corresponding adjacency
matrix. Each node in the graph is associated with a feature vector that
contains the node’s attributes.

####  1 Graph Properties

Graph properties provide insight into the structure, characteristics and
behavior of graphs. Here are some of the fundamental properties and
characteristics of graphs:

  1. 1.

Degree: The number of edges incident on a vertex. In directed graphs, we
differentiate between in-degree (number of incoming edges) and out-degree
(number of outgoing edges).

  2. 2.

Order and Size: The order of a graph refers to the number of vertices and the
size refers to the number of its edges.

  3. 3.

Diameter: The longest shortest path between any two vertices.

  4. 4.

Radius: The minimum eccentricity of any vertex in the graph. The eccentricity
of a vertex is the greatest distance from the vertex to any other vertex.

  5. 5.

Girth: The length of the shortest cycle in the graph.

  6. 6.

Adjacency: Two vertices are said to be adjacent if they are connected by an
edge.

  7. 7.

Clique: A set of vertices where each pair is adjacent.

  8. 8.

Path: A sequence of vertices where each adjacent pair is connected by an edge.

  9. 9.

Cycle: A path that starts and ends at the same vertex. A cyclic graph is a
graph that contains at least one cycle, which is a sequence of vertices where
the first and last vertices are the same, and each pair of consecutive
vertices in the sequence is connected by an edge. An acyclic graph is a graph
that contains no cycles.

  10. 10.

Connectivity: A graph is connected if there’s a path between every pair of
vertices. In directed graphs, if a graph is strongly connected, there is a
directed path between any pair of vertices.

  11. 11.

Connected Components:

For undirected graphs: A connected component is a subgraph in which any two
vertices are connected to each other by paths, and which is connected to no
additional vertices in the supergraph (i.e., the main graph). In simpler
terms, a connected component is a “piece” or “part” of the graph where there’s
a route between any pair of nodes within that piece, but no connection to
nodes outside of it.

For directed graphs: Connected components are further classified as Strongly
Connected Components and Weakly Connected Components.

Strongly Connected Components: A strongly connected component of a directed
graph is a maximal strongly connected subgraph. This means that for every pair
of vertices $u$ and $v$ in the subgraph, there’s a directed path from $u$ to
$v$ and a directed path from $v$ to $u$.

Weakly Connected Components: If you were to ignore the directionality of the
edges in a directed graph, and the graph becomes connected, then the graph is
said to be weakly connected. The maximal subgraphs of this type are the weakly
connected components.

  12. 12.

Planarity: A graph is said to be planar if it can be embedded (i.e., drawn) in
the plane such that no edges intersect or cross each other except at their
endpoints (vertices). In other words, a graph is planar if it can be drawn on
a flat surface without any of its edges overlapping or crossing, except where
they meet at nodes. This definition applies to both directed and undirected
graphs.

  13. 13.

Isomorphism: Isomorphism refers to a one-to-one correspondence between the
vertices of two graphs such that the adjacency relation between pairs of
vertices is preserved. In simpler terms, two graphs are isomorphic if they are
essentially the same in terms of structure, though they might look different
in their graphical representation.

Formally, two graphs $G_{1}$ and $G_{2}$ are said to be isomorphic if there
exists a bijective function $f:V(G_{1})\rightarrow V(G_{2})$ such that for any
two vertices $u$ and $v$ of $G_{1}$, there is an edge between $u$ and $v$ in
$G_{1}$ if and only if there is an edge between $f(u)$ and $f(v)$ in $G_{2}$.

####  2 Types of Graphs

Graphs can be categorized in various ways based on their properties,
structures, and applications. Below is an overview of the primary types of
graphs:

  1. 1.

Undirected Graph: An undirected graph is a simple structure consisting of
nodes, also known as vertices, connected by edges. In this type of graph, the
edges don’t have a specific direction. That is, if vertex $A$ is connected to
vertex $B$, then vertex $B$ is equivalently connected to vertex $A$. Such
graphs are commonly used to represent symmetric relationships, for example,
friendships in a social network.

  2. 2.

Directed Graph (or Digraph): Directed graphs, often called digraphs, also
comprise vertices and edges. However, the crucial difference is that the edges
have a direction. An arrow from vertex $A$ to vertex $B$ signifies a one-way
relationship. Digraphs are especially useful in representing prerequisites in
a course structure or transitions in a finite automaton.

  3. 3.

Weighted Graph: A weighted graph assigns a specific weight or value to each of
its edges. This weight can represent various characteristics such as distance,
cost, or any measurable quantity relevant to the problem being addressed. For
instance, in mapping out a city’s road network, the weights could symbolize
the distances or travel times between intersections.

  4. 4.

Unweighted Graph: Contrary to weighted graphs, unweighted graphs treat each
edge equally, without any specific value or weight assigned. Such graphs are
often utilized in scenarios where only the relationship or connection between
nodes is of interest, without any quantitative measure on the edges.

  5. 5.

Cyclic Graph: A cyclic graph contains at least one cycle, which is a closed
path in which a vertex is revisited without retracing any edge. Cyclic graphs
can represent systems or networks where it’s possible to return to a starting
point via a unique route.

  6. 6.

Acyclic Graph: An acyclic graph is devoid of any cycles. This means it’s
impossible to start at one vertex and traverse the graph in such a way that
you return to the starting vertex without backtracking. A classic example of
an acyclic graph is a tree.

  7. 7.

Connected Graph: In a connected graph, there exists a path between every pair
of vertices, ensuring that no vertex is isolated. Such graphs are particularly
valuable in scenarios where continuous connectivity is essential
(communication networks are one such example).

  8. 8.

Disconnected Graph: As the name suggests, a disconnected graph has one or more
vertices that aren’t connected to the rest of the graph. In other words, not
all pairs of vertices are reachable from each other. Such graphs might
represent fragmented or isolated systems.

  9. 9.

Complete Graph: A complete graph is a robust structure where every pair of
distinct vertices is connected by a unique edge. In terms of social networks,
a complete graph would mean every person knows every other person directly.

  10. 10.

Bipartite Graph: A graph $G$ is called bipartite if its vertex set can be
partitioned into two disjoint sets $U$ and $V$ such that every edge connects a
vertex in $U$ to one in $V$. This means that there are no edges that connect
vertices within the same set $U$ or within the same set $V$.

Formally, a graph $G=(V,E)$ is bipartite if there exists a partition $(U,V)$
of its vertex set $V$ such that for every edge $(x,y)\in E$, either $x\in U$
and $y\in V$ or $x\in V$ and $y\in U$.

  11. 11.

Planar Graph: A planar graph can be drawn on a plane without any edges
crossing, except at their endpoints. Such graphs are beneficial in specific
design and layout problems, ensuring no overlaps or intersections.

  12. 12.

Tree: A tree is a special kind of graph that’s both connected and acyclic.
Trees are hierarchical structures commonly used in computer science for data
structures such as binary search trees and file systems.

  13. 13.

Forest: A forest is a collection of disjoint trees, meaning it’s acyclic but
not necessarily connected. Forests can represent multiple independent
hierarchies or classifications within a system.

  14. 14.

Multigraph: Multigraphs allow for multiple edges, also termed parallel edges,
between the same set of vertices. This type of graph can be useful in
scenarios where multiple distinct relationships or connections exist between
the same entities.

  15. 15.

Simple Graph: A simple graph is a basic structure where each pair of vertices
shares at most one edge, and there are no loops. It’s the foundational form of
many other graph types and serves as a starting point in many graph theory
discussions.

  16. 16.

Hypergraph: A hypergraph generalizes the traditional graph concept by allowing
edges, often called hyperedges, to connect any number of vertices, not just
two. Hypergraphs can represent complex relationships that don’t fit neatly
into pairwise associations.

  17. 17.

Subgraph: A subgraph is formed by selecting a subset of vertices and edges
from a larger graph, without introducing any new ones. Subgraphs are crucial
for analyzing specific portions or aspects of a larger network or system.

  18. 18.

Regular Graph: In a regular graph, every vertex has the same degree, meaning
each node connects to an equal number of other nodes. This uniformity can
simplify certain analyses and algorithms. Specifically in the context of graph
computations, Regular graphs lead to close to uniform work distribution across
the computing cores.

####  3 Graph Representation

Graphs, as abstract mathematical structures, need to be represented in a
tangible form, especially for computational processes. The choice of
representation can significantly influence the efficiency of various graph
algorithms. The most common forms of graph representation include:

  1. 1.

Adjacency Matrix: This is a 2D array of size $V\times V$ (where $V$ is the
number of vertices in a graph). The entry $m_{ij}$ is either 1 (or the edge’s
weight) if there’s an edge between vertices $i$ and $j$, and 0 otherwise.
While this method provides a quick way to check the presence of a specific
edge, it can be space-inefficient for sparse graphs as it requires $O(V^{2})$
space. Figure 1 illustrates a social network graph alongside its
representation in adjacency matrix format.

  2. 2.

Adjacency List: For every vertex, a list of its adjacent vertices is
maintained. This representation is more space-efficient for sparse graphs. In
this method, an array of lists is used, with the size of the array being equal
to the number of vertices. The $i$th position in the array holds a list of
nodes to which node $i$ is connected.

  3. 3.

Incidence Matrix: This is a 2D array where rows represent vertices and columns
represent edges. For example, for an undirected graph, the entry $m_{ij}$ is 1
if vertex $i$ is incident to edge $j$, -1 if $i$ is the edge’s terminal
vertex, and 0 otherwise. For a directed graph, the entry is -1 for the tail of
the arrow (edge) and 1 for the head.

  4. 4.

Edge List: This is a list of pairs (or triples, if weights are present) that
represent edges. For instance, an edge from vertex $A$ to vertex $B$ with
weight $w$ can be represented as $(A,B,w)$. This representation is
particularly useful when the graph structure is more concerned with edges
rather than vertices.

The choice of representation often hinges on the specific operations that need
to be optimized. For instance, adjacency lists are faster for traversal
algorithms, while adjacency matrices can be more suitable for algorithms
involving edge lookups or matrix operations.

####  4 Graph Transformation

Graph transformation is a powerful technique that focuses on the modification
and manipulation of graph structures. It offers a systematic way to derive a
new graph from an existing one, serving both as a computational tool and a
conceptual methodology to analyze various properties and behaviors of graphs.
Common types of graph transformations include:

  1. 1.

Subgraph Extraction: This involves creating a new graph by selecting a subset
of vertices and edges from the original graph, usually based on certain
criteria or conditions.

  2. 2.

Graph Contraction: This process combines multiple vertices into a single
vertex, often to simplify a graph’s structure while retaining its fundamental
characteristics.

  3. 3.

Graph Expansion (or Vertex Splitting): This is the reverse of contraction. A
single vertex is expanded into multiple vertices, with edges adjusted
accordingly.

  4. 4.

Edge Contraction: Two vertices connected by an edge are merged into a single
vertex, and the edge is removed. The new vertex retains all edges that the
original vertices had, except for the contracted edge.

  5. 5.

Line Graph Transformation: Given a graph, its line graph is another graph
representing the relationship between the edges of the original graph. Each
vertex in the line graph represents an edge in the original graph, and two
vertices in the line graph are connected if their corresponding edges in the
original graph are incident on a common vertex.

  6. 6.

Dual Graph Transformation: Applied typically to planar graphs, this creates a
vertex in the dual graph for every face in the original graph, and two
vertices in the dual graph are connected by an edge if their corresponding
faces in the original graph are separated by an edge.

Graph transformations play a crucial role in a myriad of applications,
including algorithm design, network analysis, and optimization problems, by
enabling alternative perspectives and simplifications of the original
structures.

###  2 Machine Learning on Graphs

Building upon the principles of graph theory just reviewed, we now transition
to the applications. Graphs are useful abstractions as then naturally map to a
number of machine learning tasks. Graphs are used for non-Euclidean data
structures that encapsulate relationships, hierarchies, and patterns, which
are difficult to model in traditional data formats. In this section, we delve
into the techniques, algorithms, and challenges associated with leveraging
graph data for predictive and analytical tasks. This emerging field promises
important advancements in domains ranging from social network analysis and
recommendation systems to bioinformatics and traffic routing.

####  1 Graph Neural Networks

Graph Neural Networks (GNNs) have emerged as powerful tools for learning and
processing data structured as graphs. Unlike traditional neural networks that
operate on fixed-size vectors, GNNs work directly with graphs, accommodating
their non-euclidean nature and inherent irregularities. At the core of GNNs
lies the principle of aggregating information from a node’s neighbors to
iteratively update the node’s representation. This process captures both local
structures and broader topological features of the graph. Through successive
layers, GNNs can accumulate and transform information from increasingly larger
neighborhoods around each node. This ability to learn meaningful
representations of nodes, edges, or entire graphs has led to their successful
application in diverse areas such as social network analysis, molecular
chemistry, and recommendation systems, bridging the gap between the rich
expressivity of graphs and the computational capabilities of deep learning.

Figure 2: Analysis of Graph Neural Networks, demonstrating the propagation of
node properties influenced by the graph’s topology.

Before a GNN model can make predictions, the model must first be trained. As
shown in Figure 2, the goal of GNN training is to learn correlation parameters
for each node, capturing its relation to the rest of the graph. More
specifically, a feature vector for node A relates node A’s properties to its
neighbors’ properties, nodes B, C and E. Each of these neighbors, in turn, has
their own feature vectors to relate to their own neighbors. Hence, the
properties of node A can be associated with the properties of every other node
in the graph. This feature of GNNs is also useful for finding missing
properties of nodes in a graph. Similar to DNNs, a GNN can also have multiple
layers, with each layer represented by two functions: i) an aggregation
function and ii) an update function (i.e., a combination function). As the
name suggests, the aggregation function is responsible for collecting or
pooling the features of the neighbors for a given node. On the other hand, the
update function is responsible for updating each node’s feature vectors using
Multi-Layer Perceptrons (MLPs). A GNN model can have layers with different
aggregation and update functions. The deeper the GNN model, the more
information a node has about other nodes that are distant from it in the
graph. However, training deeper GNNs is difficult, primarily due to the
vanishing gradient problem [69]. As GNNs grow deeper, the gradients become so
small that the weights stop getting updated. This property makes it difficult
to train the GNN further. To address these challenges, novel GNN architectures
have been proposed to enable deeper GNN models [91].

####  2 Graph Convolutional Networks

Graph Convolutional Networks (GCNs) represent a key advancement in the domain
of graph-based machine learning. These networks are designed to process data
structured as graphs, allowing for the consideration of both node features and
the graph’s inherent structure. Traditional neural networks are ill-suited for
graph data due to the irregular and non-Euclidean nature of graphs. In
contrast, GCNs leverage the spatial relationship between nodes to propagate
and aggregate information through the graph, thus learning a more
comprehensive representation of the data.

The propagation rule for a GCN layer can be described as:

$H_{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H_{(l)}W_{(l)}\right)$
(2)

Where:

$H^{(l)}$ is the matrix of node features at layer $l$.

$\tilde{A}$ is the adjacency matrix of the graph with added self-connections

$\tilde{D}$ is the diagonal node degree matrix of $\tilde{A}$.

$W^{(l)}$ is the weight matrix for layer $l$.

$\sigma$ is an activation function, e.g., the ReLU function.

The key principle of a GCN is the neighborhood aggregation scheme. For each
node in the graph, a GCN layer aggregates feature information from its
neighbors and possibly itself. This aggregated information is then passed
through a transformation (usually a linear transformation, followed by a non-
linear activation function). The process can be iteratively run over multiple
layers, enabling the aggregation of information from a larger neighborhood at
each subsequent layer. The inclusion of this spatial-based information
aggregation makes GCNs particularly adept at node classification, graph
classification, and link prediction, especially when the structure of the
graph plays a significant role in the underlying data distribution.

####  3 Graph Isomorphism Networks

Graph isomorphism is a central concept in the field of graph theory, revolving
around the study of the structural equivalence between two graphs. Two graphs
$G_{1}$ and $G_{2}$ are considered isomorphic if there exists a one-to-one
correspondence (or bijective function) between their vertices, such that the
adjacency relationship is preserved. In other words, the graphs are
structurally identical, and one can be transformed into the other merely by
relabeling the vertices without altering the underlying connectivity pattern.
While the concept sounds straightforward, determining whether two large graphs
are isomorphic in an efficient manner remains a challenging computational
problem.

The update rule for the GIN can be formulated as:

$h^{(l+1)}_{v}=\text{MLP}^{(l)}\left(h^{(l)}_{v}+\sum_{u\in\mathcal{N}(v)}h^{(l)}_{u}\right)$
(3)

Where:

$h^{(l+1)}_{v}$ is the feature vector of node $v$ at layer $l+1$.

$\mathcal{N}(v)$ represents the neighbors of node $v$.

$\text{MLP}^{(l)}$ denotes a multi-layer perceptron used at layer $l$.

The GIN introduces an additional learnable parameter to weigh the importance
of self-features versus neighbor features. This ensures that the GIN can
capture subtle structural details, making it a powerful tool for graph
representation learning.

Understanding and recognizing graph isomorphism has profound implications in
numerous areas of science and technology. For example, in chemistry, graph
isomorphism can be used to determine molecular similarity, as molecules can be
represented as graphs where atoms are vertices and bonds are edges. Similarly,
in computer science, isomorphic graphs might denote equivalent solutions or
states in certain problems. Furthermore, in database search and pattern
recognition, determining graph isomorphism efficiently can aid in retrieving
or recognizing specific patterns amidst a large dataset. However, due to the
complexity of the problem, especially with large graphs, much research has
been invested in finding efficient algorithms and heuristic methods to tackle
the isomorphism challenge.

###  3 Graph Neural Network Frameworks

Support for GNN primitives in popular ML frameworks is increasing. Today,
researchers from the ML community are developing libraries in the form of
extensions to frameworks such as PyTorch and TensorFlow. The two most popular
libraries/extensions that implement customized GNN kernels, as well as provide
programming support in the form of APIs, are PyTorch Geometric (PyG) [49] and
the Deep Graph Library (DGL) [148]. PyG is an extension based on top of the
PyTorch library and so only supports PyTorch. On the other hand, DGL provides
support for PyTorch, TensorFlow, and MXNet.

Spektral [61] and Aligraph [178] are two librariesk built on top of
TensorFlow, used for GNN training. GraphNets [15] is a GNN framework from
Google, supported using TensorFlow as the backend. As PyG and DGL bridge both
the semantic and performance gaps when developing GNN models, they are the
most widely used frameworks by both the ML community [172] and architecture
community. [171, 159, 160, 96]. Table 1 presents a comprehensive comparison
between PyTorch Geometric (PyG) and Deep Graph Library (DGL), two prominent
libraries for implementing Graph Neural Networks (GNNs). Both libraries are
actively maintained, with extensive documentation and a large user community,
ensuring robust support for developers and researchers in the field of graph-
based deep learning.

Table 1: Comparison between PyTorch Geometric (PyG) and Deep Graph Library (DGL) Feature/Aspect |  PyTorch Geometric (PyG) |  Deep Graph Library (DGL)
---|---|---
Programming Language |  Primarily Python |  Primarily Python
Deep Learning Framework |  Built on top of PyTorch |  Supports both PyTorch and TensorFlow
Ease of Use |  High-level API, easy to use for beginners |  Low-level C++ API available
Performance |  Efficient and scalable |  Highly optimized for sparse operations
Models Available |  Extensive collection of pre-implemented GNN models |  Newer models only optimized for PyG
Community and Support |  Large community, active development |  Relatively new library with community beginning to grow
Documentation |  Extensive documentation with examples |  Comprehensive documentation
Graph Types Supported |  Supports heterogeneous and temporal graphs |  Supports heterogeneous graphs
Scalability |  Optimized for single-machine, multi-GPU setups |  Designed for distributed training on multiple machines and large graphs
Extensibility |  Easy to extend and contribute |  Low-level C++ API relatively difficult to extend

###  4 Accelerators: An Overview

Accelerators are specialized hardware components designed to perform specific
computational tasks more efficiently than general-purpose processors. The
primary motivation behind their design lies in addressing the performance and
efficiency bottlenecks encountered in conventional computing systems,
particularly for workloads that require intensive data processing or have
unique computational patterns. Accelerators are engineered to offload specific
tasks from the central processing unit (CPU), thereby enhancing the overall
system performance and energy efficiency.

####  1 Unique Advantages of Accelerators

The distinct advantages of accelerators stem from their specialized
architecture, which is tailored to execute a specific set of operations. This
specialization enables several benefits:

  * •

Enhanced Performance: Accelerators can execute certain tasks or algorithms
much faster than general-purpose CPUs due to their optimized hardware design
for those tasks.

  * •

Energy Efficiency: By offloading intensive tasks from CPUs, accelerators can
reduce overall power consumption, making them ideal for energy-sensitive
applications.

  * •

Parallel Processing Capabilities: Many accelerators, just like GPUs, are
capable of handling multiple operations concurrently, effectively leveraging
the parallel hardware of the accelerator.

  * •

Customizability: Accelerators can be customized for the specific needs of an
application, allowing for greater flexibility in handling diverse
computational requirements.

####  2 Advantages and Disadvantages of Designing Accelerators

While accelerators offer considerable advantages, there are also trade-offs
involved in their design and deployment.

##### Advantages

  * •

Highly Efficient for Targeted Tasks: Accelerators provide optimized
performance for specific applications, such as graphics processing, machine
learning, and now, graph computing.

  * •

Scalability: They can be scaled to handle larger workloads more effectively
than general-purpose processors.

  * •

Innovation: The development of accelerators drives technological innovation,
particularly in fields that require high computing power.

##### Disadvantages

  * •

Limited Flexibility: Being specialized, accelerators are not as versatile as
CPUs for general computing tasks.

  * •

Development Complexity: Designing and implementing accelerators can be complex
and resource-intensive.

  * •

Integration Challenges: Integrating accelerators into existing systems may
require significant architectural changes and software support.

  * •

Cost: The development and deployment of accelerators can be costly, especially
for cutting-edge designs.

Overall, accelerators represent a critical advancement in computing
technology, offering specialized solutions for a range of emerging
applications. In particular, their role in graph computing has opened new
avenues for handling complex data structures and algorithms efficiently.
However, the decision to utilize accelerators must consider the balance
between their specialized capabilities and the associated design and
integration challenges.

##  Chapter 2 Related Work

In this chapter, we review the existing body of work on graph computing. Our
initial focus is on the examination of prior research concerning the
benchmarking of graph-based workloads. Next, we discuss previous work aimed at
accelerating graph neural networks.

###  1 Graph Computing Benchmark Suites

Past GPU benchmark suites have provided guidance to GPU architects. To date,
GPU benchmarks fall into one of two categories. They either evaluate general-
purpose GPU computing capabilities [32, 136, 31, 36, 119, 145], or target
assessment of the performance of a specific class of workloads [88, 137, 90].
With the growing popularity of DNN workloads, a new wave of DNN benchmarks
have been developed.

Benchmarking Deep Learning Workloads and Workload Characterization: Early DNN
benchmark suites explored the execution performance of low-level primitives
[109, 42], as well as end-to-end inference and training [2, 35]. Later efforts
included a more diverse set of DNN algorithms, including a broader range of
network models and commercial efforts. TBD [177] is a DNN benchmark suite
proposed by Zhu et al. to study DNN training performance on GPUs. AIBench [53]
is an industry-initiated benchmark suite that is focused on industrial AI
services. Mattson et al. [100] proposed the MLPerf training and MLPerf
inference suites. MLPerf adopts ideas from prior DNN benchmark suites to
develop an industry-standard DNN-focused benchmark suite, designed so that new
hardware and software optimizations can be evaluated fairly. To date, MLPerf
has primarily focused on DNNs. In terms of architectural characterization,
Dong et al. [41] looked at the architectural implications of CNN training on a
GPU. Mojumder et al. [103] profiled DNN models trained on an NVIDIA DGX-1
system. However, all these prior workload studies were limited to DNNs that
operate on euclidean data (e.g., images, video and speech). In this thesis we
develop GNNMark. We specifically aim to bridge this gap, providing the
architecture community with an appropriate benchmark suite to study GNN
training behavior. We also plan to work with the MLPerf consortium to
integrate our GNN models into their training suite in the future.

Workload Characterization for GNNs: GNNs have recently attracted attention
from the computer architecture community due to their growing popularity in
the machine learning domain. Yan et al. [159] have characterized Graph
Convolutional Network (GCN) inference performance, focusing on aggregation and
model update phases. Zhang et al. [171] have also characterized the inference
performance of GNNs. Their work decomposes GNN inference execution into a
Scatter-ApplyEdge-Gather-ApplyVertex (SAGA) pipeline and then analyzes the
behavior of each phase. They also present insights on how to efficiently
design a GNN accelerator for inference. While a benchmark suite is also
created as a part of their study, it is designed primarily for inference and
is not available publicly. Most prior GNN studies focused on inference,
ignoring the training process that tends to consume a large number of GPU
hours. Also, the models evaluated are only designed to process homogeneous
graphs. Other related work focused on characterizing GNN inference and
designing customized accelerators for that purpose [160, 96, 83]. In contrast,
GNNMark includes GNN models that work across a wide range of graph data,
including spatio-temporal graphs and heterogeneous graphs. GNNMark also
includes multi-GPU implementations of GNNs, making it suitable for research on
GNN training behavior targeting GPUs. The applications included in GNNMark can
also be used to drive inference studies by first training the models to a
target accuracy and then using the pre-trained models to characterize
inference. We plan to extend the suite to support inference studies by
providing a set of pre-trained models in the future.

###  2 Prior GNN Accelerators

The cause for a critical computational bottleneck within GNN workloads is the
presence of irregular memory access patterns. Accelerating GNN workloads for
large input graphs, especially those with skewed sparsity patterns, is
particularly challenging. Previous accelerator designs have attempted to hide
memory bottlenecks by performing high-level and low-level pipelining [82],
row-remapping [55], generating two distinct implementations for the
aggregation and combination phases [160], and leveraging flexible network
topologies [92]. While these enhancements improve performance for specific GNN
workloads on predefined datasets, they fall short in terms of general
applicability across a range of GNN workloads [1]. Table 1 illustrates support
proposed in prior studies for various GNN workloads. Table 2 further extends
Table 1 by summarizing the optimization techniques incorporated by prior GNN
accelerators.

Table 1: Comparison of prior state-of-the-art GNN accelerators’ support for different graph neural network models. The table indicates the support provided by accelerator for GCN, GIN, GAT, SAGE, PNA, and DGN models Accelerator | GCN | GIN | GAT | SAGE | PNA | DGN
---|---|---|---|---|---|---
I-GCN [56] | ✔ | ✔ | ✘ | ✔ | ✘ | ✘
AWB-GCN [55] | ✔ | ✘ | ✘ | ✘ | ✘ | ✘
HyGCN [160] | ✔ | ✔ | ✘ | ✔ | ✘ | ✘
EnGN [96] | ✔ | ✘ | ✘ | ✔ | ✘ | ✘
GraphPE [6] | ✔ | ✘ | ✔ | ✘ | ✘ | ✘
GNNerator [135] | ✔ | ✘ | ✘ | ✔ | ✘ | ✘
GCoD [167] | ✔ | ✔ | ✔ | ✔ | ✘ | ✘
ReGNN [33] | ✔ | ✔ | ✘ | ✔ | ✘ | ✘
ReFlip [73] | ✔ | ✔ | ✔ | ✔ | ✘ | ✘
GROW [74] | ✔ | ✔ | ✔ | ✔ | ✘ | ✘
FlowGNN [124] | ✔ | ✔ | ✔ | ✔ | ✔ | ✔
Table 2: Comparison of various Graph Neural Network (GNN) Accelerators on optimization techniques incorporated Accelerator |  Kernel Fusion |  Loop Reordering |  Pruning |  Bank Mapping |  Load Balancing |  Hash based
---|---|---|---|---|---|---
I-GCN [56] |  ✘ |  ✘ |  ✔ |  ✔ |  ✔ |  ✘
AWB-GCN [55] |  ✔ |  ✔ |  ✘ |  ✔ |  ✔ |  ✘
HyGCN [160] |  ✔ |  ✔ |  ✘ |  ✔ |  ✔ |  ✘
EnGN [96] |  ✘ |  ✔ |  ✘ |  ✔ |  ✔ |  ✘
GraphPE [6] |  ✘ |  ✘ |  ✘ |  ✔ |  ✘ |  ✘
GNNerator [135] |  ✘ |  ✘ |  ✘ |  ✘ |  ✘ |  ✘
GCoD [167] |  ✘ |  ✔ |  ✔ |  ✘ |  ✔ |  ✘
ReGNN [33] |  ✔ |  ✘ |  ✘ |  ✘ |  ✔ |  ✘
ReFlip [73] |  ✘ |  ✘ |  ✘ |  ✘ |  ✔ |  ✘
GROW [74] |  ✘ |  ✔ |  ✘ |  ✘ |  ✔ |  ✘
FlowGNN [124] |  ✔ |  ✘ |  ✘ |  ✔ |  ✔ |  ✘

FlowGNN [124]: FlowGNN introduces a dataflow architecture tailored for the
acceleration of GNNs that utilize message-passing mechanisms. The FlowGNN
architecture is scalable and supports a broad spectrum of GNN models,
featuring a configurable dataflow that simultaneously computes node and edge
embeddings as well as facilitates message passing, making it universally
applicable across different models. A significant advantage of FlowGNN is its
ability to perform GNN inference without any prior graph processing.

GROW [74]: GROW is an accelerator for Graph Convolutional Neural Networks
(GCNs), designed to optimize the two primary stages of GCNs—aggregation and
combination—that have distinct dataflow. GROW utilizes Gustavson’s algorithm
to implement a row-wise product-based sparse-dense GEMM accelerator. By co-
designing software and hardware, GROW claims to achieve a balance between data
locality and parallelism.

ReFlip [73]: ReFlip is a GCN accelerator that aims to improve the overall
efficiency of both regular neural network computations and irregular graph
analytics. ReFlip employs a unified architecture based on Processing-in-Memory
(PIM) and features a crossbar structure. This unified architecture is
augmented by novel algorithm mappings that maximize performance by leveraging
the inherent parallelism of crossbar structures.

ReGNN [33]: ReGNN is a GNN accelerator aimed at eliminating computational and
communication redundancy inherent in traditional GNNs. ReGNN is built on a
hardware-software co-design approach incorporating a dynamic redundancy-
eliminated neighborhood message-passing algorithm. ReGNN is a configurable,
pipelined architecture adaptable to various GNN variants without compromising
accuracy.

GCoD [167]: GCoD is a hardware-software co-designed framework aimed at
addressing the computational inefficiencies associated with GCNs when applied
to large, sparse and irregular real-world graphs. In terms of algorithmic
design, GCoD employs a ”split and conquer” training strategy that locally
polarizes graph densities, resulting in adjacency matrices with enhanced
regularity and thus, achieves good acceleration. On the hardware side, a
specialized two-pronged accelerator is developed, featuring separate engines
to process denser and sparser graph workloads, thereby further improving
utilization and acceleration efficiency.

GNNerator [135]: GNNerator is an accelerator for GNNs, designed to address the
computational challenges arising from the dual nature of GNN operations: dense
and regular computations for feature extraction, and sparse and irregular
computations for message passing between nodes. GNNerator employs
heterogeneous compute engines specifically optimized for these contrasting
computational patterns. The paper also introduces the concept of feature-
blocking, a dataflow technique that adjusts the trade-off between irregular
and regular memory accesses, increasing computational efficiency during both
feature extraction and aggregation stages.

GraphPE [6]: The GraphPE architecture incorporates dedicated hardware units
engineered to manage the irregular data movement typical of graph computations
while also ensuring high computational throughput for GNN models.

EnGN [96]: EnGN is an accelerator architecture that addresses the substantial
computational and memory overhead present within GNN workloads. EnGN focuses
on accelerating the three key stages of GNN propagation by abstracting them as
common computing patterns. The architecture employs a ring-edge-reduce (RER)
dataflow and corresponding RER PE-array to manage the poor locality associated
with sparsely and randomly connected vertices. Additionally, EnGN utilizes a
graph tiling strategy to fit large graphs into the accelerator’s memory.

HyGCN [160]: HyGCN is an accelerator designed to address the unique
computational challenges arising from the hybrid execution patterns of GCNs.
These patterns comprise a dynamic and irregular aggregation phase, and a
static and regular combination phase. The design of HyGCN is motivated by a
characterization of GCN execution patterns on an Intel Xeon CPU. The
accelerator employs a new programming model to exploit fine-grained
parallelism and features two efficient processing engines tailored to handle
the irregularity in the aggregation phase and the regularity in the
combination phase. These engines are optimized for various levels of
parallelism and data reusability.

AWB-GCN [55]: Autotuning-Workload-Balancing GCN (AWB-GCN) is a hardware
accelerator specifically designed for speeding up GCN inference. Addressing
the challenges of processing large and unbalanced real-world graphs, AWB-GCN
employs three hardware-based autotuning techniques: dynamic distribution
smoothing, remote switching, and row remapping. These techniques enable the
system to dynamically adjust the workload distribution across a large number
of processing elements.

I-GCN [56]: I-GCN is a hardware accelerator designed to improve the
performance of GCN inference. One of the primary challenges in accelerating
GCNs is the poor data locality and redundant computation arising from the
large size, high sparsity, and irregular non-zero distribution of real-world
graphs. To tackle these issues, I-GCN employs an online graph restructuring
algorithm known as islandization. This algorithm identifies clusters of nodes
with strong internal connections, but weak external ones, which improves on-
chip data reuse and minimizes off-chip memory accesses.

##  Chapter 3 GNN Workload Characterization

Owing to the energy efficiency and high-performance capabilities of GPUs, GPUs
are a natural choice for accelerating the training of GNNs. This forms the
core motivation to understand the architectural and system-level implications
of training GNNs on GPUs. Previously to our work, no benchmark suite existed
to examine the architectural implications of GNN training workloads.

In this thesis proposal , we address this need by presenting GNNMark [13], a
feature-rich benchmark suite that encompasses the diversity present in GNN
training workloads, datasets and GNN frameworks. Our benchmark suite consists
of GNN workloads that utilize various graph-based data structures, including
homogeneous graphs, dynamic graphs, and heterogeneous graphs commonly used in
a number of application domains that we mentioned in Section 2. We use this
benchmark suite to explore and characterize GNN training behavior on GPUs. We
study a variety of aspects of GNN execution, including both compute and memory
behavior, highlighting major bottlenecks observed during GNN training. At the
system level, we evaluate multiple metric, including the scalability of
training GNNs across a multi-GPU system, as well as the sparsity of data
encountered during training. The insights derived from our work can be
leveraged by both hardware and software developers to improve both the
hardware and software performance of GNN training on GPUs. The contributions
of this part of the thesis include:

  1. 1.

GNN training-focused benchmark suite: We deliver an open-source benchmark
suite named GNNMark (https://gitlab.com/GNNMark/gnnmark), designed to
characterize the training behavior of GNNs on GPUs. Our suite includes a
diverse set of popular GNN models that the machine learning community has
developed. The workloads span seven different application domains and three
different types of graph-based data types.

  2. 2.

Architecture-level characterization of GNNMark: We characterize the workloads
in GNNMark, considering their architectural implications during the training
process on a GPU. We are the first to provide a detailed execution time
breakdown of different operations executed during GNN training and identify
the major bottlenecks. We find that these workloads are much more diverse than
typical DNN training workloads. GNN execution is highly input data and model
dependent. We find that integer operations play a critical role, a factor that
has been relatively ignored in DNN training studies on GPUs. We also observe
significant sparsity during GNN training. This can potentially be leveraged to
train larger graphs on a single GPU. We also consider multi-GPU support in the
suite, enabling scaling studies of GNNs across multi-GPU systems.

  3. 3.

Recommendations to improve GPU architectures: We present insights drawn from
our detailed characterization and suggest changes to improve GPU architectures
and system design so that GNNs can be trained efficiently.

###  1 Motivation for Characterizing GNN Workloads

Deep Neural Networks (DNNs) have revolutionized numerous areas, such as image
classification [44], speech recognition [114] and autonomous systems [102].
Notable DNN architectures such as Convolutional Neural Networks (CNNs) [52]
and Transformers [146] primarily operate on Euclidean data. This type of data,
inherently 1D or 2D, includes images and speech datasets. Yet, much of the
data we encounter in the real world is non-Euclidean in nature [21],
encompassing structures of molecules, social networks, sensor systems, and
manifolds. Traditional DNNs, designed for Euclidean data, often fall short in
efficiently processing non-Euclidean data due to challenges in directly
applying operations, such as convolutions [21].

To bridge this deficiency, GNNs [84, 155] have been developed, specializing in
non-Euclidean data training. For instance, Pinterest employs a GNN model,
PinSAGE [166], for its recommendation algorithms, while Twitter researchers
utilize GNN models with temporal graph data [123]. Similarly, the Drug
Repurposing Knowledge Graph (DRKG) [76] adopts GNN models to research the
applications of existing drugs for novel diseases.

With GPUs establishing themselves as the go-to platform for DNN and GNN
training due to their advanced capabilities, many leading GNN frameworks, for
example, the Deep Graph Library [173] and PyTorch Geometric [49], have
integrated GPU training support. As GNNs continue to surge in popularity,
there’s a pressing need for optimizing GPU platforms to train them. Thoroughly
analyzing GPU behavior during GNN training is paramount. By dissecting the
myriad of GNN operations and their execution during training, GPU architects
can pinpoint and address performance bottlenecks. Aspects such as GNN training
scalability on multi-GPU setups and the presence of data sparsity during
training can be tapped into for training large graphs, especially those
surpassing a single GPU’s memory capacity [122]. A thorough analysis of GNN
training workflows will enhance our understanding of the computational and
memory constraints associated with running GNN workloads on GPUs.

###  2 Prior Work on GNN Characterization

Prior work on characterizing GNNs has focused primarily on the inference
behavior for GCN s [159] or targeted a limited set of GNN models [171]. Both
model and dataset diversity [171] have not been considered by these studies.
By dataset diversity, we mean different types of graphs, including
homogeneous, heterogeneous, knowledge, and dynamic graphs (explored in detail
in Section 3). Model diversity implies different types of GNN models, such as
Graph Transformers, Spatio-Temporal GNNs, and LSTM based GNNs. In previous
benchmarking efforts, GNN inference has been the primary target for
characterization studies [159, 171]. Popular benchmark suites for DNN
training, such as the MLPerf Training Suite [99], Training Benchmarks for DNN
(TBD) [177], DNNMark [43], Fathom [2], and DawnBench [35], do not consider
GNNs as part of their workloads and deal exclusively with DNNs that deal with
euclidean data. To comprehensively characterize the execution behavior of GNN
training on GPUs, we need a benchmark suite that includes diverse GNN models
that are trained on diverse datasets. Currently, no such benchmark suite
exists. To fill this gap, we develop GNNMark, a collection of representative
workloads that can be used by the computer architecture community to study the
execution of GNNs on GPUs. We then analyze the workloads in the GNNMark
benchmark suite, specifically focusing on their behavior during GNN training
on a GPU. Apart from the fact that prior GNN workload characterization studies
primarily focused on inference, we chose to focus on training, given that GPUs
remain the best platform in terms of performance for GNN training.

###  3 Input Graph Types

GNNs have evolved over time, and we find that each variation of GNN is
typically associated with a distinct form of graph data [155]. In our
examination of GNNs, we identify three primary classifications of graph data:

  1. 1.

Homogeneous Graphs: A homogeneous graph contains nodes and edges of a single
type. For example, social network graphs are typically homogeneous, where each
node represents a user, and an edge can represent if that one user follows
another. Homogeneous graphs can be directed (e.g., following a user on
Twitter) or undirected (e.g., adding a friend on Facebook). Another notable
collection of homogeneous graph datasets that are used to evaluate GNN models
are citation datasets (e.g., Cora, PubMed, Citeseer) [84].

  2. 2.

Heterogeneous Graphs: A heterogeneous graph contains nodes and edges of
multiple types. A widely used form of a heterogeneous graph is found in
recommendation generation scenarios. For example, in a dataset designed to
recommend music to users, the graph will consist of two types of nodes: i)
music nodes and ii) user nodes. The edges will correspond to different
interactions between the user and a music piece. In addition, edges may
contain additional information such as ratings or like/dislike attributes.
Knowledge graphs that are used to model relations between an object and
entities are another form of a heterogeneous graph – e.g. when users search
for a famous celebrity on Google (an object).

  3. 3.

Dynamic Graphs: A dynamic graph is a special type of graph where the graph
itself, as well as its properties, can evolve over time. Many real-world
graphs, such as social-network graphs [123], traffic data graph [168] and
communication-network graphs, are dynamic [47]. Note that dynamic graphs can
be either homogeneous or heterogeneous. For example, if we take a homogeneous
social network graph, where nodes represent people and edges represent whether
there is a relationship, the number of relations a person has or the relations
between two people can change over time. Another common use case of dynamic
graphs is to model traffic data as a dynamic graph and use it for traffic
forecasting and prediction [40].

###  4 Benchmark Suite Design

Characterizing the behavior of GNN training on a GPU requires a set of
representative workloads to cover the wide variety of GNNs [155, 172]. The
variants should include GNNs used across multiple application domains,
including recommendation systems, classification of molecules, traffic
forecasting, etc. The representative suite should also include models that
consider different classes of real-world graphs, including knowledge graphs,
heterogeneous graphs, and dynamic graphs. In addition, multi-GPU GNN training
should be supported to evaluate the efficacy of training GNNs on multi-GPU
systems.

To satisfy all the above-mentioned criteria, we offer GNNMark, a benchmark
suite designed for studying the behavior of GNN training on GPUs. Similar to
benchmark suites that target DNN training, such as TBD [177] and MLPerf [99],
we curate our benchmark suite from open-source publicly available
implementations of GNN models. As PyTorch Geometric (PyG) and Deep Graph
Library (DGL) are the main frameworks employed for developing GNN models by
the ML community, we use models developed using these frameworks. Since both
of these frameworks support PyTorch, we have chosen models developed in
PyTorch. The specific models chosen for this suite, along with their
associated application domains and datasets, are summarized in Table 1. Below,
we provide more details about each GNN model.

Abbv |  GNN Model |  Application Domain |  Graph Input Type
---|---|---|---
PSAGE |  PinSAGE |  Recommendation |  Heterogeneous Graph
STGCN |  Spatio Temporal GCN |  Traffic Forecasting |  Dynamic Graph
DGCN |  Deep GCN |  Molecular Property Prediction |  Homogeneous Graph
GW |  GraphWriter |  Text Generation |  Heterogeneous Graph
KGNN |  k Graph Neural Networks |  Protein Classification |  Homogeneous Graph
ARGA |  Adverserially Regularized Graph Autoencoder |  Node Clustering |  Homogeneous Graph
TLSTM |  Tree Long Short-Term Memory Networks |  Sentiment Classification |  Homogeneous Graph
Table 1: Workloads in GNNMark Benchmark Suite. Abbv |  Datasets |  # Node |  # Edge
---|---|---|---
PSAGE |  Nowplaying (NWP) [169] | 22.9M | 1.9M
Movielens (MVL) [64] | 1.9M | 9.7K
STGCN |  LA [168] | 207 | 325
PEMS_Bay (PEMS) [168] | 1722 | 2694
DGCN |  MOLHIV [72] | 1.04M | 1.1M
MOLTOX [72] | 145K | 151K
GW |  AGENDA [87] | 885K | 2.57M
KGNN |  Proteins (PROT) [80] | 43K | 162K
ARGA |  Cora [163] | 2K | 10.5K
CiteSeer (CSEER) [163] | 3.3K | 9.2K
PubMed (CSEER) [163] | 19.7K | 88.6K
TLSTM |  Stanford Sentiment Treebank (SNTM) [131] | 318K | 310K
Table 2: Workloads in GNNMark Benchmark Suite.

PinSAGE: GNNs that operate on heterogeneous knowledge graphs can be used for
recommendation tasks. These are commonly used in social networks. PinSAGE
[166] is one such GNN model that has been developed at Pinterest. Since the
original PinSAGE model is not publicly available, we use the implementation
that has been published by the developers of DGL. PinSAGE is an improvement
upon the GraphSAGE model [63] for training on large graphs. It uses a random
walk mechanism [150] during aggregation to identify the importance of a node
in the graph without the need to process the entire graph. This effectively
allows a user to train a model on graphs that do not fit in GPU memory.

Spatio-Temporal Graph Convolutional Network: Traffic forecasting is an
important problem that falls into the domain of time-series prediction and
uses dynamic graphs. This task is highly relevant for use in urban areas where
traffic control and guidance are required. Solving this problem using
conventional Euclidean-based DNNs is challenging because of the nonlinearity
involved in traffic data [108]. One approach to deal with nonlinearity is to
represent the problem as a graph and then apply depth-wise convolutions on the
graph. Spatio-Temporal graph Convolutional Networks (STGCN) [168] represent
one such model that has been proposed to solve the problem of traffic
forecasting. We include an STGCN to represent a GNN model that deals with
dynamic graphs.

DeepGCNs: One of the key challenges with the original GCN models, such as the
one proposed by Kipf and Welling [85], is that increasing the depth of the
model does not improve the accuracy of the model. This is due to the vanishing
gradient problem [69], which has made implementing deep GCNs challenging.
Therefore, researchers have developed mechanisms to train deeper GCNs [91],
using ideas borrowed from DNN research, such as residual layers and skip-
connections used in models such as ResNet [67]. DeepGCN is a novel GCN
architecture that allows GCNs to have more layers. Additional layers in a GCN
can significantly improve training accuracy [91], so we include it in our
study. Specifically, we use a DeepGCN model and train it to perform graph
property prediction, a common task in molecular property prediction.

GraphWriter: Automated generation of text from a knowledge graph to form
meaningful and coherent sentences is an open and challenging problem [78].
Text encoding models, such as the popular Transformer model [146], cannot be
directly applied to a knowledge graph as they do not work with non-euclidean
data. Therefore, ML researchers have developed GNN-based Transformer models
for this task. Graphwriter [87] is one such novel GNN-based Transformer model
designed to operate on knowledge-graphs for text generation.

k-GNNs: Most GNN models are one-dimensional in nature and cannot effectively
capture any higher-order information, such as the properties of subgraphs,
within the graph. As a result, they fail the graph isomorphism test proposed
by Weisfeiler and Lehman [151] (WL algorithm). The WL algorithm is a test used
to determine the expressiveness power of a GNN by testing if an algorithm is
able to distinguish whether two graphs are isomorphic or not. Two graphs are
said to be isomorphic if they have the same number of vertices, edges, and
connectivity. Therefore, researchers have developed higher-dimensional
hierarchical GNNs, called k-GNNs (where the k stands for the dimension), which
can capture properties of subgraphs [104]. This enables GNNs to perform close
to the k-WL graph isomorphism test [104]. We include two variants of k-GNNs,
(KGNNL and KGNNH to denote a lower and higher dimensional version of k-GNN,
respectively) and use them to perform classification of protein molecules. The
primary reason we include this workload in our suite is to study how
application characteristics and behavior change as we move towards higher-
dimension GNNs [118].

Adversarially Regularized Graph Autoencoder: Generative Adversarial Networks
(GANs) are gaining popularity due to their ability to learn with limited
amounts of data [117]. Due to this property, GAN-based architectures are also
being explored for GNNs. An Adversarially Regularized Graph Autoencode (ARGA)
[116] is one such GNN-based GAN model that is proposed for graph embedding.
ARGA has an encoder-decoder architecture where the encoder is trained to form
a compact representation of a graph, and the decoder is trained to generate
the graph structure. The model is designed to perform node clustering, which
is an unsupervised learning task, on real-world graphs. ARGA employs this
encoder-decoder architecture within a GAN framework, so that it can
successfully learn the low-dimensional features of the graph from the high-
dimensional graph features. This process is referred to as graph embedding
[26]. We include ARGA as a representative GAN-based GCN to further increase
the diversity of our benchmark suite. We train ARGA to perform node clustering
on real-world homogeneous graphs, such as Cora, PubMed, and CiteSeer [85].

Tree-LSTM: Sentiment classification is an important task in the Natural
Language Processing (NLP) domain. Tree Long Short-Term Memory Networks (Tree-
LSTMs) [138] are one group of models developed for this task. In contrast to
the linear model used in an LSTM, Tree-LSTMs use a tree-structured network
topology and can outperform linear LSTMs in the sentiment classification task
[138]. The Tree-LSTM method implemented in DGL uses the idea of batching. The
basic idea of batching is to collect smaller graphs that are part of the
dataset and convert them into a batched larger graph. We include the Tree-LSTM
model in GNNMark to study how batching multiple small graphs to a larger graph
impacts the behavior of an application.

###  5 Profiling Methodology

####  1 Experimental Platform

To demonstrate the utility of GNNMark, we use an NVIDIA V100 [112], a commonly
used GPU for running neural network training. V100 is part of the NVIDIA Volta
family of GPUs. Our test system is equipped with an Intel(R) Xeon(R) CPU
E5-2630 CPU that operates at a frequency of 2.4GHz. The GPU has 80 Streaming
Multiprocessors (SMs) and is rated to deliver 14 TFLOPS of single-precision
performance. The GPU memory uses HBM2 with 16 GB capacity and bandwidth of 900
GB/s. The combined L1 cache/shared memory/texture cache has a capacity of 128
KB and is private to each Streaming Multiprocessor (SM). The L1 memory is
backed by a 6.14 MB L2 cache, which is banked and shared across all SMs.

For our multi-GPU experiments, we use 4 V100 GPUs on a node equipped with
Intel(R) Xeon(R) E5-2686 v4 2.4GHz CPUs, hosted on Amazon AWS EC2. Each GPU is
interconnected using NVIDIA NVLink technology, providing a total of six links,
for an aggregate bandwidth of 300 GB/s. Both the single-GPU and multi-GPU
systems used in our experiments run CUDA 10.2, cuDNN 7.6.5, and PyTorch 1.5.0.
The workloads included in GNNMark use either DGL version 0.5.2 or PyTorch
Geometric 1.6.1.

Since multi-GPU training has been shown to improve the performance of DNN
training [103], we also look at how well GNN training can scale across
multiple GPUs. GNN training can be sometimes be limited by GPU memory
capacity, especially given the continual growth in the size of the input graph
[79]. One approach to counter this problem is to compress the data transferred
from the CPU to the GPU and store the compressed data in GPU main memory. This
is only possible if the data transferred is highly sparse [122]. Therefore, we
also characterize sparsity levels of the data transferred between the CPU and
GPU during GNN training in our suite.

####  2 Profiling Tools

We use several tools for collecting the metrics of interest. For the kernel-
level characteristics, such as cache statistics and comparisons between
compute versus memory behavior, we use the NVIDIA nvprof profiler (version
10.2) [20]. Similar to DNNs, GNNs typically launch the same kernel many times
during training. Therefore, when profiling and collecting hardware performance
counters using nvprof, we profile the same kernel for either fifty kernel
invocations or for one epoch, whichever is shorter. However, nvprof does not
provide any mechanism to collect the memory divergence behavior of a workload.
Therefore, we use the NVBit framework [147] (version 1.4), which is a binary
instrumentation tool to collect the memory divergence information at a kernel
level. To collect the sparsity of the data transferred from the host to the
device during GNN training, we modified the PyTorch source code to collect
this information.

####  3 Metrics of Interest

Characterizing the behavior of GNNs requires an understanding at both the
architectural level and the system level. In this work, we profile and collect
the following metrics:

  1. 1.

Ratio of time spent in different operations: Prior work on classifying the
phases of GNN execution have categorized GNN execution into two phases: i)
aggregation and ii) update phases [159]. While classifying into these two
phases is beneficial for machine learning purposes, we believe that
architectural studies can be guided by a lower level of abstraction (i.e.,
operations), which has been proposed by Adolf et al. [2]. In our profiling
experiments for GNN, we observe commonly used operations across various GNN
workloads, such as sparse matrix GEMM operations (spgemm), scatter and gather
operations, reduce operations, embedding operations, index selection
operations, sorting operations, and element-wise operations. These operations
may be embedded within one or multiple kernels within GNN training workloads.
Understanding the time spent in these different operations and how they vary
across different datasets for the same model can shed insight into where the
majority of the execution time is actually spent during GNN training on a GPU.

  2. 2.

FLOPS and Arithmetic Intensity Analysis: To understand how well the GPU can
handle GNN training, it is important to analyze the arithmetic intensity and
count the number of floating point operations (FLOPS). Arithmetic intensity
(AI) is defined as the ratio of the total number of floating point operations
performed to the ratio of data transferred (in bytes). AI can be used to gauge
the data reuse of an algorithm. A higher AI is better since it implies more
computations are performed for every byte of data. Analyzing the FLOPS vs AI
shows whether a workload is mainly compute or memory bound.

  3. 3.

Stall Analysis: To improve the performance of GNNs on GPUs, GPU application
developers need to have an understanding of major stalls incurred during GNN
training of different GNN workloads. Such an understanding of stalls at an
operation level can be helpful to understand the performance of each
aforementioned operation.

  4. 4.

Cache behavior: While not as important as they are for CPUs, caching can still
benefit GPU applications with high spatial and temporal locality. Therefore,
having a basic understanding of the hit rates of different levels of the cache
is important. Another key characteristic relevant to caches is memory
divergence. Memory divergence demonstrates the scattered memory access pattern
of a given operation. The memory divergence of a single transaction is
calculated by the number of unique cache lines that are touched by a warp. For
example, if each of the 32 threads in a warp accesses a different cache line,
then the divergence is 32. A scattered memory access pattern i.e., where
threads in a warp end up accessing different cache lines, is detrimental on
GPUs as the memory transactions cannot be coalesced. This, in turn, leads to
serialization and can hurt performance. It is well known that memory
divergence hurts the performance of typical graph workloads such as Breadth
First Search and PageRank [31]. Therefore, it is essential to understand the
level of memory divergence within a broader class of GNN workloads.

  5. 5.

Sparsity during GNN training: Sparsity of the data that is transferred between
the CPU and the GPU during training can be leveraged to use optimizations such
as DMA compression as proposed by Rhu et al. [122]. Therefore, in this work,
we also aim to understand the sparsity and compressibility during GNN
training.

####  4 Multi-GPU Implementations

We also include multi-GPU versions of each workload in GNNMark to enable users
to study the scalability of GNN training on multi-GPU systems. The multi-GPU
implementations are built on the PyTorch Distributed Data Parallel (DDP)
method to train GNNs across multiple GPUs, exploiting data-level parallelism.
In practice, DDP has been shown to scale well on up to 256 GPU nodes [93] for
DNN training.

Figure 1: Execution breakdown, reported as the percent of total execution
time, for individual operations across the different workloads of GNNMark.

###  6 Benchmarking Results

####  1 Execution Time Breakdown

We start our analysis by breaking down the time spent in the different GNN
operations across the different workloads in our suite. Similar to DNNs [2],
GNN training can be broken down into layers or operations. Prior work divided
GNN training into two phases: i) an aggregation phase, and ii) an update phase
[159]. While this division is appropriate when looking at GNNs from an machine
learning perspective, we believe that deeper insights are needed to fully
characterize their behavior. Therefore, we work at the abstraction level of
individual operations [2].

We identify a common set of operations performed during GNNMark execution.
These operations include general matrix multiply (GEMM), sparse matrix-matrix
multiplication (SpMM), convolutions, scatters, gathers, reductions, index
selection, sorting, and element-wise operations. Element-wise operations are
operations that operate on individual elements of a tensor and perform
operations such as multiplication of all elements in the tensor by a scalar,
changing the sign of all elements in the tensor, or adding two tensors of
similar dimensions.

Figure 1 shows a breakdown of the percentage of time spent in individual
operations across the different workloads of GNNMark. Figure 1 illustrates the
percentage breakdown of operations varies significantly across workloads. For
instance, STGCN, a spatio-temporal GNN, is dominated by 2D convolution
operations (60% on average), while DGCN is dominated by element-wise
operations (31% on average).

The execution time breakdown across operations in a GNN differs greatly from
the mix in a typical DNN. Across all the workloads, we observe that only 25%
of the execution time is spent executing GEMM and SpMM operations. This is in
stark contrast to the mix of operations commonly found in DNN workloads, where
GEMM (convolutional layers and fully-connected layers) dominate the execution
[42]. We find that GNN training also differs significantly from GNN inference
workloads [159], where GEMM operations are reported to consume more than 50%
of the execution time.

Other common operations, such as sorting, index selection, reductions, and
scatter-gather operations, account for 20.8% of the total execution on
average. These operations are primarily used in the graph’s aggregation phase,
where the nodes exchange information with one another before updating the
feature vectors.

PSAGE, when trained on the MVL dataset, spends 20.7% of its execution on
sorting and only 7.0% of the time on reductions, whereas ARGA (using the Cora
data) spends 23% on reductions and only 6.1% on sorting. This great diversity
and variety of tasks in GNN training present challenges to architects
designing customized accelerators for GNN training, given that accelerators
are typically designed to optimize only for a single set of operations.

In contrast to typical DNN workloads, GNN workloads tend to be more input
data-dependent. For PSAGE, the percentage of time spent in element-wise
operations is much higher when training on the (NWP) dataset (78%), versus
training on the (MVL) dataset (36%). This is because, when training on the NWP
dataset, the feature vectors are 10$\times$ larger than when training on the
MVL dataset. As element-wise operations operate on each value of the input
feature vector, the time spent executing these operations becomes more
dominant when graphs with larger input features are used.

GNN Execution Characteristics: Our performance analysis shows that GNN
training workloads exhibit more diverse behavior as compared to DNN training
workloads. Each model’s characteristics can differ vastly from others. Even
the same GNN model can exhibit different characteristics depending on the
input graph type. In addition, execution hot spots are no longer limited to
convolution and GEMM operations. We find operations such as reductions,
scatter, gather and sorting also need to be optimized. The solution of
attaching a single-purpose accelerator to primarily accelerate GEMM operations
[120] during DNN training may not work well for GNN training.

####  2 Instruction Mix and GFLOPS/GIOPS Analysis

Another aspect of GNN training behavior is the dynamic instruction mix present
in different workloads. As shown in Figure 2, integer instructions play a
larger role than floating-point instructions across all workloads. On average,
64% of the executed instructions are integer (int32) instructions, whereas
only 28.7% are single-precision floating point (fp32) instructions. The only
workload where this trend is reversed is in GraphWriter (GW). This is because,
in GW, a majority of the time is spent on GEMM and SpMM operations (as seen in
Figure 1), which work on fp32 data. While improving the performance of fp32
instructions has received much attention, int32 instructions have not received
the same. Given that int32 instructions dominate GNN execution during
training, improving the performance of integer math on a GPU is a critical
factor when trying to accelerate GNN training.

Figure 3 presents the number of GFLOPS and GIOPS executed by our workloads in
GNNMark. We observe that the average GFLOPS rate is 214 GFLOPS, and the
average GIOPS rate is 705 GIOPS. The observed average GFLOPS rate is much
lower than the theoretical max GFLOPS of the V100, which is 14 TFLOPS for fp32
arithmetic [112] (the V100 specs do not mention the peak theoretical GIOPS. We
believe it to be close to the peak theoretical GFLOPS). GW has the highest
fp32 performance of 1.99 TFLOPS. Being a transformer-based ML model, GW can
effectively use most of the parallel resources on a GPU [146]. We also observe
that, while graph batching has been proposed to improve performance in DGL,
TLSTM is still able to achieve only 74 GFLOPS.

The average IPC measured across all the workloads was found to be 0.55, which
reflects the memory-bound nature of the workloads. When comparing the GFLOPS
and GIOPS of different operations, we observe that the GEMM operations
typically have a higher GFLOPS (in the mid 300s) as opposed to other
operations, such as reductions, scatters, and gathers that have lower rates
(in the 100 GFLOPS/GIOPS range) suggesting a very low overall GPU utilization.
Given that these operations can dominate the execution time, it is important
for both hardware and software developers to focus on improving the
performance of these operations.

Instruction Set Usage Summary: Our analysis reveals that, during GNN training,
execution is dominated by integer operations. Thus, to accelerate GNN training
on either GPUs or accelerators, int32 arithmetic performance will be key. The
overall performance in terms of GFLOPS/GIOPS for GNNs is relatively low
compared to the peak performance of the hardware. This suggests that GNN
training is primarily memory-bound. Given that operations such as reductions,
scatters, gathers, and sorting can occupy a good chunk of the execution time
during GNN training, it is important for both hardware and software developers
to focus on improving the performance of these operations.

####  3 Stalls and Cache Analysis

Developing a comprehensive understanding of major stalls in the GPU hardware
during GNN training can help guide architectural design decisions when tuning
the performance of these workloads. Given that caches can greatly improve the
performance of GPU applications, it is also important to look at their
efficiency in the context of GNN training. In Figure 4, we provide a
distribution of different types of stalls observed in GNN training. We find
that execution is stalled primarily due to _Memory Dependency_ , _Execution
Dependency_ , and _Instruction Fetch_. The high percentage of _Memory
Dependency_ stalls (34.3% on an average) suggests that the memory subsystem is
inefficient in serving data read requests to the GPU cores. From Figure 5, we
observe that GNN workloads have an extremely low L1 D-cache hit rate on the
V100 (a mere 15%, on average), which is the primary reason for these stalls.

We also analyze the impact of divergent load instructions. The load
instructions associated with a warp are considered divergent if they access
more than one cache line (a line is 128B on the V100). Memory divergence can
impact the performance of typical graph workloads, such as Breadth First
Search and PageRank [31]. Therefore, it is important to characterize the
degree of memory divergence present during GNN training.

Of all the load instructions, we observe $32.5\%$ of load instructions exhibit
divergence across different GNN training workloads. This percentage is large
and is highly correlated with the resulting low L1 D-cache hit rates. While
the larger L2-cache (6MB) on the V100 fares significantly better with a $70\%$
hit rate on average, the inability of the L1 D-cache to effectively hold the
working set can put pressure on the L2 cache to satisfy the memory
requirements. Across the different operations, we observe that GEMM, SpMM, and
GEMV have poor locality (i.e., a low L1 D-cache hit rate, less than $10\%$ on
average). The L1 D-cache hit rates of other operations, such as indexing,
scatters, gathers and sorting, are also low (below $15\%$, on average).

Figure 2: Breakdown of fp32 vs. int32 instructions across the different
workloads in GNNMark. Figure 3: GFLOPS and GIOPS across the different
workloads in GNNMark.  Figure 4: Stall breakdown across operations in GNNMark.

The high percentage of _Execution Dependency_ stalls (i.e., 29.5% of the stall
cycles on an average) points to the fact that, across the entire set of
workloads, there are many dependencies between instructions in a warp, which
results in low instruction-level parallelism. Microarchitectural enhancements
to support out-of-order execution in the GPU pipeline [60] can potentially
accelerate GNN training.

Surprisingly, _Instruction Fetch_ stalls are also significant (21.6% on
average). This is due to two reasons. The first is that the instruction cache
is ineffective in caching all the instructions. Although the V100 architecture
has a new 12KB L0 I-cache that is backed by a larger 128KB L1 I-cache, it
seems to not be highly effective in caching all instructions during kernel
execution. The second reason is loop unrolling techniques [106], which are
used to improve the performance of a GPU kernel, can negatively impact the
instruction cache hit rate and increase the stalls due to instruction fetching
[37].

In Figure 4, it is evident that scatter and gather operations, along with
index selection operations, exhibit a higher frequency of stalls in comparison
to GEMM, particularly for commonly utilized GNN operations (notably, Conv2D
for STGCN and BatchNorm for DeepGCN). The primary reason for this is the
irregular memory access patterns demonstrated by both scatter and gather, as
well as index selection operations, which lead to memory dependencies.

Takeaways: Our analysis of the stalls during GNN training shows that stalls
due to _Memory Dependency_ , _Execution Dependency_ , and _Instruction Fetch_
can be significant. While GPU architecture research has focused on removing
the first two types of stalls, improving the performance of instruction
fetching has been neglected. Therefore, architects and compiler developers
should focus on developing techniques to improve instruction fetch to optimize
the performance of GNN training.

GNN training also suffers from a high degree of L1 D-cache misses and a
significant number of divergent load instructions across all operations. The
extremely high L1 D-cache miss rates suggest that caching is not effective for
GNN workloads. We envision two potential solutions to alleviate this problem.
The first is to employ half-precision-training for GNN training, which uses
only 16-bit data instead of 32-bit data, thus can significantly reduce the L1
D-cache miss rates. Alternatively, L1 cache bypassing solutions [156, 157] can
be explored to alleviate this problem. Among all the load instructions,
$32.5\%$ exhibit divergence across various GNN workloads.

Figure 5: L1-D and L2-cache hit ratios, and divergent load ratios for GNNMark
workloads.

####  4 Sparsity during GNN training

Training sparsity refers to the zero values (as a percentage of all values)
that are transferred during CPU-to-GPU memory copies during the GNN training
process. For characterizing the average sparsity, we report the percentage of
zero values observed in CPU-to-GPU data transfers during GNN training. From
Figure 6, an average sparsity of 43.2% was observed during GNN training. This
suggests that compression techniques could be employed. Rhu et al. [122]
proposed using compression to alleviate the problem of training large DNN
models on a GPU. While GNN models are smaller than conventional DNN models
(e.g., Resnet-50 is 50-layers deep, whereas most GNNs today have fewer than 10
layers), the input graph can occupy a significant portion of GPU memory (up to
90% in our experiments). While the machine learning community has proposed
sampling the graph to address this problem [166], there are situations where
training on the whole graph has been shown to provide better accuracy [79]. We
suggest compressing the data in GPU memory to facilitate training on large
graphs.

We can also observe a predictable pattern in the data sparsity (from Figure
7), providing opportunities to apply adaptive compression algorithms [140]. As
the sparsity values change during training, the GNN training framework may
need to exploit different compression solutions and formats that work the best
for a specific sparsity level.

Looking at the average sparsity for PSAGE in Figure 6, we can conclude that
training sparsity is a function of both the model and the input graph. When
using the MVL dataset, the average sparsity is 22%, but it reduces to 11% when
training on the NWP dataset.

In terms of models, since many GNNs such as GraphTransformer, DeepGCNs and
ARGA use activation functions such as ReLU and PReLU in their layers, they
produce highly sparse data. We suggest applying compression to take advantage
of this sparsity. The result will be that we can train larger graphs on a
single GPU. We plan to pursue this path in later work in this thesis.

Takeaways: Training on graphs that are larger than the size of GPU memory is a
challenging problem. Thus, exploiting the high degree of sparsity present in
GNN workloads by using compression techniques can begin to address this
problem.

####  5 Scalability of GNN training using multi-GPU systems

Using the multi-GPU implementations that we developed for the GNNMark
workloads using PyTorch DDP, we evaluate the strong scaling characteristics of
the workloads in GNNMark. We train all our models for five epochs (we observe
similar performance across all epochs) and report the average time-per-epoch,
an approach used in previous work [103], to understand the performance of DNN
workloads on multi-GPU systems. We do not evaluate ARGA, as the application
inherently sends the entire graph to the GPU as a part of its training
process, and therefore, distributing the same graph across multiple GPUs does
not help. The first thing we can clearly observe from Figure 8 is that not all
workloads benefit from multi-GPU training. While DGCN, STGCN, and GW show
considerable performance gains, the same does not hold true for the other
applications. TLSTM does not benefit from multi-GPU training. Given that this
is an LSTM-based GNN model with low computational GFLOPS/GIOPS intensity, the
application is unable to take advantage of the additional computing power
offered by multi-GPU systems. For PSAGE, we observe performance degradation
when scaling across multiple GPUs. This is primarily because the PSAGE
implementation in DGL uses a batch sampling mechanism, which is not compatible
with PyTorch DDP. As a result, the training data gets replicated across
multiple devices, and this replication results in redundant computation and
unnecessary communication, which in turn hurts performance.

Takeaways: Multi-GPU systems do not always benefit GNN training. Therefore,
ideas such as topology-aware scheduling and fine-grained graph partitioning
that have been proposed by researchers in graph-centric GNN frameworks, such
as ROC [79] and NeuGraph [98], should be adopted by high-level frameworks,
such as PyG and DGL, to enable more efficient GNN training. Currently, these
frameworks are not open source, and hence, we cannot evaluate them for the
GNNMark workloads.

Figure 6: Average sparsity in the data transferred from CPU-to-GPU during GNN
training in GNNMark workloads. Figure 7: Sparsity heat map for DeepGCN when
running on the MOLHIV dataset.  Figure 8: Multi-GPU performance scaling.

###  7 GNNMark Summary

In this thesis proposal , we present GNNMark, a diverse benchmark suite of GNN
workloads designed for the characterization of GPU performance. To the best of
our knowledge, we are the first to propose a GNN training focused benchmark
suite for the architecture community. We use GNNMark to perform a detailed
characterization of GNNs to understand the architectural implications of
training on GPU systems. Our work provides novel insights that show the major
architectural bottlenecks in GNN training and suggests how they can be
potentially addressed.

A single GNN model can exhibit different characteristics based on the input
graph. We observe that unlike DNNs, GEMM and convolution operations are less
dominant in GNN execution. Instead, integer operations required for graph
processing can dominate execution, suggesting that improving the performance
of integer math is paramount. A high degree of instruction fetch stalls shows
that the instruction cache on the GPU can limit GNN performance. Finally, we
also report on the training sparsity and strong scaling characteristics of GNN
training using our suite.

##  Chapter 4 Acceleration of GNNs

Graph Neural Networks (GNNs) are characterized by their computational
structure, which involves sparse matrix operations in the combination phase
and dense operations in the aggregation phase. This section focuses on the
acceleration of the combination phase through the development of an
accelerator specifically designed for Sparse General Matrix-Matrix
Multiplication (SpGEMM). Subsequently, we introduce an accelerator designed to
efficiently manage both the sparse (combination) and dense (aggregation)
computational phases of GNN workloads, thereby establishing a comprehensive
and versatile GNN accelerator.

Optimizing the performance of multiplications that operate on sparse matrices
is challenging, especially given the associated irregular memory access
patterns, resulting in load imbalance on today’s parallel architectures. Given
that the input matrix data possesses low temporal and spatial locality, this
leads to inefficient cache usage and pipeline stalls. Modern-day CPUs and GPUs
struggle to produce scalable performance when executing sparse matrix
multiplication workloads. CPUs fail to monetize on the parallelism present in
such workloads, while GPUs struggle to balance tasks across their thousands of
hardware threads. While a number of sparse matrix formats have been proposed
to better handle the sparsity, we lack a single format that works over a range
of different sparsity patterns. Given the growing popularity of sparse
datasets in emerging applications, we need to explore how we can leverage a
novel architecture to accelerate SpGEMM workloads.

As part of this thesis proposal , we explore a novel distributed memory SpGEMM
implementation. We specifically target this work for a custom accelerator. Our
approach improves performance by mapping the computation of row-wise products,
hashtables, and on-chip accumulation to the accelerator’s scratchpads. We
provide a new set of performance metrics for this class of workload and
demonstrate their utility using a suite of micro-benchmarks run using
synthetic, as well as real-world, datasets. We also introduce a new Memory-
aware Aligned Parallel Compressed Sparse Row matrix storage format called MAP-
CSR to further accelerate local memory accesses. Running on a custom graph-
based accelerator, we are able to achieve consistent speedup over MKL and
provide insights on the scalability of our implementation.

###  1 Motivation for SpGEMM kernel acceleration

Multiplication of two sparse matrices (i.e., a SpGEMM kernel) is commonly
found in many emerging workloads. Some examples of popular algorithms that
need to process sparse matrices include:

  * •

Scientific computations: algebraic multigrid solvers (AMG) [10], volumetric
mesh analysis [105] and linear-scaling electronic structure computations [19];

  * •

Graph-based computations: triangle counting [38], path planning [111],
community detection [45], breadth-first-search [24], recommendation systems
[110], graph neural networks [13], label propagation, network packet routing
[141], graph centrality measures, and graph contractions [5].

Figure 1: World exposure graph centrality, as generated using an SpGEMM kernel
(with nodes as cities, node size proportional to Maximal Frontier Betweenness
Centrality (MFBC), edges as air travel corridors, and colors representing
countries)

SpGEMM plays a pivotal role in applications for controlling epidemics. It
serves as an essential kernel in calculating centrality measures for airports
[132, 5], and offers crucial guidance for directing vaccine distribution to
key cities [71]. The world exposure graph, plotted in Figure 1, is recursively
generated using the airport network dataset. We incorporate this dataset (with
a sparsity of $99.63\%$) in the analysis of our SpGEMM kernel implementation
on the custom accelerator.

Modern trends in Big Data have witnessed an increase in data sparsity, along
with an increase in data set size. In 2021, Facebook claimed they had $2.89$
billion monthly active users, with studies suggesting an average of 338
friends per user [130]. The resulting adjacency matrix of the Facebook user
graph would approach $99.99\%$ sparsity. Graph analytics of such highly sparse
datasets push the limits of the current computing infrastructure and expose
innate problems exhibited by traditional architectures. Sparse graph workloads
are dominated by highly irregular and uncoalesced memory access patterns.

Current multi-core CPU architectures, given their limited number of compute
units (i.e., cores), fail to capitalize on the fine-grained parallelism
present in these workloads. Single Instruction, Multiple Data (SIMD)style GPU
architectures struggle to evenly distribute tasks among their threads, leading
to under-utilization of hardware. In this work, we present an SpGEMM
algorithmm called Sparse Matrix Atomic Scratchpad Hashing (SMASH), tailored to
a custom multi-threaded accelerator. This accelerator provides a novel MIMD-
style architecture based on simple in-order cores. SMASH, a state-of-the-art
SpGEMM kernel implementation, provides $1.6\times$ average speedup over MKL
with synthetic datasets, a $1.29\times$ average speedup over real world
datasets and a $1.04\times$ average speedup over real world datasets as
compared to an A100 GPU.

To summarize, the key contributions of this part of the thesis work include:

  1. 1.

We characterize the challenges faced while developing efficient SpGEMM
kernels. To this end, we perform an analysis of various sparse matrix
multiplication methods and evaluate the advantages and limitations of each.

  2. 2.

We present a new sparse matrix storage format called Memory Aligned Parallel -
Compressed Sparse Row (MAP-CSR), which allows us to compute each row of the
sparse matrix in parallel. MAP-CSR improves the efficiency of memory accesses,
ensuring memory-aligned storage of each row. Our MAP-CSR implementation is
able to improve the performance of SpGEMM by $1.58\times$.

  3. 3.

Finally, we present Sparse Matrix Atomic Scratchpad Hashing (SMASH), an
efficient SpGEMM kernel implementation that leverages distributed memory on a
custom accelerator. We provide three different versions of SMASH, with
iterative improvements, each capitalizing on a different feature of the
underlying architecture.

###  2 Background on SpGEMM

The SpGEMM kernel operation generally consists of two distinct phases, each
with its own computational requirements and challenges:

  1. 1.

The Multiplication Phase: In this initial phase, the algorithm performs
element-wise multiplication between corresponding non-zero elements of the
sparse matrices involved. Given the sparse nature of the matrices, the
algorithm needs to identify matching elements efficiently. This often involves
complex data structures like compressed sparse row (CSR) or compressed sparse
column (CSC) to store only the non-zero elements along with their indices. The
computational complexity in this phase is primarily determined by the number
of non-zero elements in the matrices.

  2. 2.

The Accumulation Phase: Following the multiplication of elements, this phase
focuses on summing up the products to generate the final sparse matrix. This
involves aggregating values that are multiplied with the same index,
essentially condensing them into a single entry in the resulting matrix. The
challenge here is to perform this aggregation in an efficient manner,
especially when the product matrix has fewer zeros, i.e., is less sparse than
the input matrices. Optimizations often target reducing memory access latency
and improving data locality in this phase.

Figure 2: Methods of implementing the two distinct phases of SpGEMM kernel

Variations in the implementations of these two phases give rise to various
SpGEMM algorithms. There are four methods to compute the first multiplication
phase, as shown in Figure 3. Each method exhibits different memory access
patterns and provides varying degrees of parallelism.

While the inner product multiplication computes output matrix elements
directly, its performance is crippled by poor input reuse. On the other hand,
the outer product multiplication suffers from poor output locality arising
from the endless batches of partial product matrices generated [170]. In our
work, we incorporate row-wise multiplication, owing to the massive parallelism
exposed by this method. Row-wise multiplication also does not suffer from the
memory bloat problem when dealing with a large number of intermediate partial
products [9].

The next phase, called the accumulation phase, can be distinguished based on
the underlying data structures. Examples of accumulation techniques include
heap-based [7], hash-based [107], sparse accumulator (SPA) based [57],
comparator array based [170], and Forwarding Adder Network (FAN) based [120]
to name a few. Depending on the memory hierarchy used for accumulation, this
phase can be further classified into on-chip and off-chip accumulation.

Figure 3: Matrix Multiplication Methods

This work presents SMASH, a scalable sparse matrix multiplication kernel based
on the row-wise multiplication method. SMASH incorporates on-chip, hash-based
accumulation to lower redundant memory accesses. We implement three different
versions of this kernel on a custom graph accelerator.

Figure 4:  Replication Ratio (lower is better) and Speedup (higher is better)
of SMASH using MAP-CSR v/s CSR storage format on real world datasets.

###  3 MAP - CSR Storage Format

The traditional method of storing sparse matrices is CSR [129] (see Figure 5),
which is memory efficient as it only stores $n+nnz$ elements instead of
$n^{2}$ (where $n$ is the dimension of a square matrix and $nnz$ is the total
number of non-zeros). But what it gains in memory efficiency, it lacks in
exposing parallelism. For example, while writing to a CSR matrix, the rows are
required to be written sequentually. If the data needs to be written in
parallel, using the CSR format requires knowledge of the number of non-zeros
in all rows in advance to allocate memory preemptively.

Figure 5:  Conventional CSR Format

The Conventional CSR format allows only sequential write operations, which
poses a considerable challenge to implement SpGEMM kernels that scale on
multi-node systems. It also introduces many synchronization operations,
leading to performance degradation. We introduce a novel matrix storage format
called MAP-CSR, that is designed to scale well on large-scale distributed
systems.

####  1 MAP-CSR Implementation

Instead of the traditional $3$-array storage format used conventional CSR
(refer to Figure 5), MAP-CSR utilizes a $5$-array storage (see Figure 6) as
follows:

  1. 1.

Elements per row array: Stores the number of non-zero elements present in each
row.

  2. 2.

Row pointer array: Points to the start of each row (stores the offset to the
start of each row in the column pointer and the data array).

  3. 3.

Replicator array: Similar to the row pointer array, but points to the replica
of rows in the column pointer array and the data array.

  4. 4.

Column pointer array: Stores the column indices of elements in each row.

  5. 5.

Data Array: Stores the value of each element.

Figure 6:  MAP-CSR Format

Using a $5$-array storage format allows us to write the rows of the matrix in
a random order, as compared to the sequential order imposed by Conventional
CSR. In addition to storing rows in a random order, our approach also allows
padding rows with zeros. This enables us to store rows in specific memory
banks in main memory. Data accesses to different memory banks can have
different latencies depending on which core is making the request. The ability
to select a memory bank for storing specific rows allows for the optimization
of memory access latency, particularly for rows that are accessed frequently.

A similar approach of storing sparse matrices was incorporated by Buluc et al.
[23], where they stored rows in random order. With MAP-CSR, we add another
feature called the Replicator array. This array, as the name suggests, allows
rows to be replicated multiple times in the column pointer and data array. For
example, row $7$ is replicated in Figure 6. The row pointer array points to
offset $16$, the location where one copy of the row is located, and the
replicator array points to offset $2$, where a second copy of the row is
present. There might even exist more than two copies of each row, in which
case, the replicator array for each core points to their respective offsets
with low latency. To compare memory requirements of the MAP-CSR format with
the memory consumed by the Conventional CSR format, we can compute the
replication ratio $\Re$ as follows:

$\Re\approx\frac{nnz+nnz^{\prime}+nz_{pad}}{nnz}$ (1)

where $nnz$ represents number of non-zeros, $nnz^{\prime}$ represents the
number of non-zeros from the replicated rows, $nz_{pad}$ denotes the number of
zeros used for padding and $\Re$ is the replication ratio, where
$1\leq\Re<\infty$.

We benchmark our SpGEMM implementation using the MAP-CSR storage format and
compare it to the performance of a vanilla CSR (traditional CSR) storage
format. Figure 4 provides information on the replication ratio (Equation 1)
for each dataset, as well as the speedup obtained by using MAP-CSR as compared
to the CSR storage format. A higher ratio denotes a larger memory footprint,
hence we aim to lower the replication ratio. On average, we obtain a
$1.582\times$ speedup by utilizing MAP-CSR, as compared to using a CSR storage
format, with an average replication ratio value of $3.169$.

####  2 MAP-CSR Advantages

MAP-CSR offers many advantages over conventional CSR, namely:

  1. 1.

Allows rows to be stored in a random order.

  2. 2.

Allows zero-padding to be aligned on memory banks.

  3. 3.

Allows for rows to be replicated for faster reads.

  4. 4.

Allows for rows to be prefetched, as they are isolated in banks.

####  3 MAP-CSR Limitations

While MAP-CSR offers major benefits, it also has certain shortcomings, which
we address here. While replication of rows provides faster memory read
transactions (data can now be fetched from memory with relatively lower
latency), this affects the writing mechanisms. Writing to a replicated row
requires writing to the original copy of the row (as pointed to by the row
pointer) and requires the replicated copies to be invalidated.

Conversion of the Conventional CSR to MAP-CSR is associated with both compute
and memory overheads. Memory overhead, as discussed before (refer to Equation
1), poses a $\Re$ times increase in the memory footprint. The computational
overhead of converting to MAP-CSR is associated with the replication of rows.
Replication of rows requires re-computing the indices of the row pointer in
MAP-CSR format, which is a compute-intensive process. Despite the necessary
overhead associated with MAP-CSR, we were able to obtain an average speedup of
$1.58\times$ over conventional CSR, achieving an average replication ratio of
$3.17$ for the SpGEMM workload.

###  4 SMASH Kernel

One of the key design choices for our SpGEMM kernel implementation was to
select one of the four general matrix-multiplication approaches (shown in
Figure 3). The inner product approach faced issues due to the cost of index-
matching and low temporal reuse [115]. The outer-product approach generated a
large number of intermediate partial products, demanding high on-chip memory
requirements. Neither of these choices provides any benefit when multiplying
extremely sparse matrices.

Figure 7:  The SMASH architecture.

Our novel implementation of the SpGEMM kernel is based on a row-wise product
method called SMASH. Our method exploits high data reuse behavior [120] and
minimizes the number of input matrix reads, while still maintaining low on-
chip memory usage. SMASH incorporates on-chip memory to store intermediate
results and leverages the atomic instructions to accumulate these partial
products.

In this thesis proposal , we present a set of successive improvements,
resulting in three versions of SMASH. In each version we identify the
remaining bottlenecks, and then optimize our algorithm to mitigate them in the
next version. Each SMASH implementation targets a specific performance
bottleneck on the custom accelerator architecture.

The following subsections describe our implementation of SMASH, along with
three different optimizations. Similar to Gustafson’s two-phase matrix
multiplication algorithm [62], our SMASH implementation is characterized by
two phases:

  1. 1.

Memory computation phase

    1. (a)

Matrix Read

    2. (b)

Compute Memory Requirements

    3. (c)

Window Generation

  2. 2.

Product computation phase

    1. (a)

Prefetching

    2. (b)

Hashing

    3. (c)

Write-back

####  1 Memory computation phase

Analogous to Gustafson’s two-phase matrix multiplication approach [62], the
first phase of SMASH determines the memory required for the output matrix $C$,
as well as the on-chip memory requirements of the intermediate products. For
evaluation purposes, we do not include the time consumed in the memory
computation phase while considering speedup over other architectures.
Evaluation methodologies are further discussed in Section 5. This phase can be
further decomposed into three tasks.

  1. 1.

Matrix Read \- Our SMASH SpGEMM implementation starts off with reading input
matrices $A$ and $B$, both of which are presumed to be in a conventional CSR
format.

  2. 2.

Compute Memory Requirements \- After reading the input matrix arrays in CSR
format, we compute the required size of memory required to store the output
matrix by counting the total FMA operations per row. We compute the maximum
number of non-zeros for every row of output matrix $C$ using Gustafson’s two-
step algorithm [62]. In this thesis proposal , we refer to this term as
Floating-Point Multiply-Add (FMA). The computation of FMA s per row has a
computational complexity of $\mathcal{O}(n)$, where $n$ is the size of the
input matrix.

  3. 3.

Window Generation \- Once the memory requirements of each row are computed,
this phase then classifies each row of the output matrix $C$ as either dense
or sparse. We then group multiple rows together into a single window that can
be dispatched as a task to computing core. This process of classifying and
grouping rows into windows is characterized by two parameters:

    1. (a)

Contraction Factor ($CF$): Decides if a row of output matrix $C$ can be
classified as dense or sparse. If $\frac{FMA}{CF}>threshold$, then the row is
classified as dense, else it is classified as sparse. The $threshold$ value is
a function of $scratchpad$ size and matrix density.

    2. (b)

Expansion Factor ($EF$): This is used to determine the memory requirements of
sparse rows, where the memory requirements are equal to the higher prime
number closest to the value $FMA\times EF$.

A dense and a sparse row is evaluated differently in SMASH during the hashing
phase. A sparse row will be allocated less memory than the max size of the
row, as a dense row will follow a $1:1$ mapping and will be allocated memory
equal to the max size of the row. Once the classification of rows is complete,
this phase groups multiple rows together into a single window, such that the
intermediate partial products can fit on the on-chip memory (i.e.,
scratchpad). At this phase of window generation, the input matrices are
converted from conventional CSR format to the new MAP-CSR format. The MAP-CSR
storage format allows for each window to consist of rows in a non-sequential
order, permitting greater flexibility for this phase to generate windows. An
evenly spread mix of sparse and dense rows are packed together and shipped to
the next phase for computation. Every individual compute core processes its
own window independently, regardless of the status of other windows. This
allows us to assign windows to compute cores in a random order and
oversubscribe windows.

####  2 Product Computation Phase

##### Prefetching

Each window generated in the previous phase is scheduled on a computing core
for generating intermediate products. The prefetching phase preemptively
copies the input matrix rows that are required by each compute core to their
respective local memory bank. This phase of Prefetching is only possible due
to the “replicator” property of MAP-CSR, which allows rows to be duplicated
multiple times across each computing core.

##### Hashing

This phase involves the multiplication of input matrix elements, required to
compute the intermediate partial product. After the partial product is
computed, it needs to be stored and merged. Merging partial products is a
memory-intensive process requiring scanning through arrays to match indices.
In addition, on multi-threaded architectures, this class of operations needs
to be synchronized to avoid data races and ensure atomicity. Among the
multiple solutions available to store and merge data, we opt for hashtables.
SMASH utilizes row-partitioned hashtables to store and merge partial products.
The use of hashtables avoids the use of expensive index matching, while
allowing us to merge partial products on the fly.

We utilize hashtables to store intermediate partial products (on the on-chip
memory). In the hashing phase, a global hashtable is created in the Scratchpad
(SPAD)(the on-chip memory). A single row is allocated to one thread of each
compute core in a round-robin fashion. Each element of the row from the first
matrix is multiplied with an entire corresponding row of the second matrix
(Equation 2 and 3, where $C$ is the output matrix, $A$ and $B$ are input
matrices, and $N$ is the size of the matrix). This leads to the creation of
partial products. These partial products are hashed into the SPAD using prime-
modulo hashing.

$C[i,:]=\sum_{k=0}^{N}A[i,k]*B[k,:]$ (2) $u\otimes v=\begin{bmatrix}u_{1}\\\
u_{2}\\\ u_{3}\\\
u_{4}\end{bmatrix}\begin{bmatrix}v_{1}&v_{2}&v_{3}\end{bmatrix}=\begin{bmatrix}u_{1}v_{1}&u_{1}v_{2}&u_{1}v_{3}\\\
u_{2}v_{1}&u_{2}v_{2}&u_{2}v_{3}\\\ u_{3}v_{1}&u_{3}v_{2}&u_{3}v_{3}\\\
u_{4}v_{1}&u_{4}v_{2}&u_{4}v_{3}\end{bmatrix}$ (3)

In prime-modulo hashing, we hash the intermediate products on the SPAD by
indexing each to the closest highest prime number, as computed in the Window
Generation phase. The use of prime numbers allows us to reduce the number of
hash collisions. A prime-modulo hash of intermediate products can result in
three outcomes:

  * •

Hash Insert: This routine is executed when a hashed index finds an empty
location on SPAD. The column index value and data value of the intermediate
product are stored on the SPAD at the hashed index location.

  * •

Hash Update: This routine is executed when the hashed index does not find an
empty location on SPAD, but the column index value of the current intermediate
product matches with the one present on SPAD. In this case, the SPAD data
value is updated with the sum of new data value and existing data value. This
routine is also called the merging of partial products.

  * •

Hash Collide: This routine indicates that the hashed index did not find an