# AccSS3D: Accelerator for Spatially Sparse 3D DNNs

Om Ji Omer14, Prashant Laddha1, Gurpreet S Kalsi1, Anirud Thyagharajan1,
Kamlesh R Pillai1,
Abhimanyu Kulkarni2, Anbang Yao3, Yurong Chen3, Sreenivas Subramoney1
1Processor Architecture Research Lab, Intel Labs, Bangalore  2University of
Wisconsin - Madison, work done while at Intel  3Intel Labs, China
4Corresponding Author : Om Ji Omer<EMAIL_ADDRESS>
###### Abstract

Semantic understanding and completion of real-world scenes is a foundational
primitive of 3D Visual perception widely used in high-level applications such
as robotics, medical imaging, autonomous driving and navigation. Due to the
curse of dimensionality, compute and memory requirements for 3D scene
understanding grow in cubic complexity with voxel resolution, posing a huge
impediment to realizing real-time energy-efficient deployments. The inherent
spatial sparsity present in the 3D world due to free space is fundamentally
different from the channel-wise sparsity that has been extensively studied. We
present Accelerator for Spatially Sparse 3D DNNs (AccSS3D) , the first end-to-
end solution for accelerating 3D scene understanding by exploiting the ample
spatial sparsity. As an algorithm-dataflow-architecture co-designed system
specialized for spatially-sparse 3D scene understanding, AccSS3D includes
novel spatial locality-aware metadata structures, a near-zero latency and
spatial sparsity-aware dataflow optimizer, a surface orientation aware
pointcloud reordering algorithm and a co-designed hardware accelerator for
spatial sparsity that exploits data reuse through systolic and multicast
interconnects. The Sspnna accelerator core together with the 64 KB of L1
memory requires 0.92 mm2 of area in 16nm process at 1 GHz. Overall, AccSS3D
achieves 16.8x speedup and a 2232x energy efficiency improvement for 3D sparse
convolution compared to an Intel-i7-8700K 4-core CPU, which translates to a
11.8x end-to-end 3D semantic segmentation speedup and a 24.8x energy
efficiency improvement (iso technology node).

##  I Introduction

Understanding 3D geometry and semantics of a scene is essential to many real-
world systems including but not limited to autonomous driving, robotics,
remote sensing, AR/VR and medical treatment [34, 31, 16, 62, 6]. With rapid
growth in 3D acquisition technologies, 3D sensors are becoming increasingly
available and affordable for rich data generation through various types of 3D
scanners, LiDARs and RGB-D cameras.3D data is usually represented in various
formats like pointclouds, meshes, depth maps and volumetric grids. Deep
Learning techniques have disrupted traditional methods in domains such as
computer vision, speech processing and machine translation that operate over
images, videos, audio, text and other forms of data. However, DL methods face
severe challenges in processing 3D visual data due to the high dimensionality
and the unstructured nature of 3D data.

Several methods (Figure 1) have been proposed for various 3D visual AI
applications such as shape classification, object detection, tracking, and
scene segmentation. 3D scene segmentation requires extraction of global
geometric structure and intricate details of each point in the 3D pointcloud.
Semantic segmentation (Figure 2) aims to divide a pointcloud into several
subsets based on real world semantics. Instance segmentation identifies
instances of each semantic object, while part segmentation further breaks each
instance into different parts. Scene completion predicts and labels missing
regions arising from sensing inaccuracies or occlusions.

Point based networks (Table I) directly operate over irregular, orderless and
unstructured pointclouds, making it infeasible to directly apply standard
CNNs. Performance of multi-view 2D projection based methods is highly
sensitive to viewpoint selection and these methods also do not fully exploit
underlying 3D geometry. Since volumetric representation preserves
neighbourhood structure of pointcloud and regular data formats allow direct
application of standard 3D convolutions, volumetric projection based methods
provide higher accuracy. However, voxelization introduces discretization
artifacts and causes information loss. A low resolution voxel representation
can degrade accuracy, whereas high resolution pointclouds cubically grow
compute and memory requirements (Figure 5). This poses a huge impediment in
achieving real-time real-world deployments of visual AI that fundamentally
require low-latency and low-energy 3D scene understanding capability.
Thankfully, the ample free space in 3D scenes provides significant opportunity
to exploit the inherent spatial sparsity.

Figure 1: Taxonomy of 3D visual data processing, courtesy: [20] Figure 2: 3D
Semantic segmentation, annotating voxels with labels [47] TABLE I: Comparison
of semantic segmentation methods on ScanNet[11]

Category | Method | mIoU | Category | Method | mIoU
---|---|---|---|---|---
Point based | Pointwise MLP | PointNet++ [43] | 33.9 |  Projection based | Volumetric $\star$ | SparseConvNet [18] | 72.5 $\star$
PointSIFT [28] | 41.5 | MinkowskiNet [10] | 73.6 $\star$
Point Convolution | PointCNN [32] | 45.8 | Multiview | TangentConv [49] | 40.9
KPConv [51] | 68.4 | Perm. Lattice | LatticeNet [44] | 64.0
Graph based | HPEIN [27] | 61.8 | Hybrid | UPB [9] | 63.4

For dense DNNs, multiple accelerator designs [63, 41, 17, 22, 25] have been
proposed to exploit channel-wise sparsity in weights and inputs. They focus on
identifying valid pairs of non-zero weights and input activations while
operating over a compressed data structure. We observe two fundamental
attributes of spatial sparsity as present in 3D visual analytics that
differentiate it from the channel-wise sparsity: 1) the selection of a non-
zero pair of weights and inputs depends solely on local 3D spatial sparsity,
2) the nature of the operation per selected pair is of the matrix-to-vector
type as compared to scalar-to-scalar type in channel-wise sparsity. The first
motivates a different hardware-architecture to enable input-weight pair
selection based on the variable local sparsity per voxel. The second further
offers the opportunity to exploit higher efficiency through coarser dispatches
of work to the compute units quite unlike the prior accelerators that hunt for
fine-grained sparsity across channels. We will show in Section III that a
custom-built sparse engine is required for efficient acceleration of
spatially-sparse applications such as 3D visual analytics as they have
distinct hardware requirements.

Optimized dataflows, as explored in prior art [7, 8, 58, 21, 15, 30], focus on
dense-DNNs and enable tiled execution with optimal tile-sizes and loop-orders
to exploit data-locality in on-die memories. It is worth noting that the
execution attributes of dense-DNNs (#data transfers and #compute operations)
are highly predictable, and since they do not depend on input data, optimal
dataflows can be derived apriori based on network parameters and underlying
hardware architecture. However, these optimizers cannot be deployed in data-
dependent sparse-DNN contexts since determining optimal tile-size and loop
order requires on-the-fly processing of input data and hence cannot be
determined a priori. Further, due to the sparsity-induced asymmetry of work
packets, load balancing requires online intelligence as part of a suitably
designed software-hardware solution. Hence specialized dataflow optimizers
that explicitly exploit spatial sparsity structure are warranted. In addition,
they must achieve compute efficiencies similar to dense-DNNs without the
latency overheads incurred by on-the-fly processing.

###  I-A Our Contribution

Driven by a detailed end-to-end performance characterization of the Sparse
Convolution Network (SCN), we present Accelerator for Spatially Sparse 3D
DNNs, the first end-to-end solution for accelerating 3D scene segmentation by
exploiting spatial sparsity. In brief, our key contributions are as follows:
1\. We introduce a novel locality-aware metadata structure, Coir, for voxel
data that stores spatial locality information by encoding active receptive
fields at each location. We also present a novel pointcloud reordering
technique, Soar, that maximizes spatial data locality and reuse across all DNN
layers for multi-level memory architectures.
2\. We present (to the best of our knowledge) the first-ever sparsity aware
dataflow optimizer, Spade, that analyzes the local geometry structure of a
pointcloud and uses the sparsity attributes to maximize data reuse across all
DNN layers. To meet real-time requirements, we enable latency-critical
dataflow optimizer routines to be run in offline mode while retaining the
benefits of the sparsity-aware dataflow.
3\. We present a novel sparse-accelerator for spatially-sparse DNNs, Sspnna,
whose sparse scheduler maximizes weight reuse. Systolic and multicast
interconnects in the PE arrays maximize input feature-map reuse. We also
propose, Admac, an accelerator for fast 3D neighbourhood search and Coir
metadata creation and Carom, a joint dataflow optimization technique for
multi-level memory hierarchies. We show how a scaled-up architecture based on
AccSS3D accelerates 3D sparse convolution by 16.8x compared to a 4-core CPU
baseline with a 2232x improvement in energy efficiency.

##  II Background

Recent algorithmic advances [13, 55, 36] extended 2D-CNNs to 3D to recognize
3D objects and enabled semantic segmentation of real-world 3D scenes. However,
due to the curse of dimensionality, compute and memory requirements grow in
cubic complexity with voxel resolution.

Free space in 3D scenes is a source of inherent spatial sparsity, offering
high opportunity for efficient processing. Recent algorithms [42, 43, 18]
exploit this spatial sparsity by processing only those voxels (active voxels)
that are in the vicinity of a surface boundary. They transform 3D sparse data
into a list of active voxels for compressed storage and use a map [26, 50] to
retrieve lists of indices based on 3D coordinates. Graham et al. [19]
introduced Sparse Convolution Network (SCN) using the novel Valid Sparse
Convolution (VSC) that provides significant reduction in compute and memory
costs by considering output voxels as active only if the corresponding input
voxel is active. This retains the sparsity structure of feature maps across
the network and paves the way for achieving real-time complex 3D scene
understanding. Zhang et al. [61] extended SCN to use Spatial Group
Convolution, dividing the pointcloud into groups, further reducing compute
without accuracy loss. Several systems employ encoder-decoder U-net topologies
[46, 53, 12, 60, 33, 54, 57, 45, 14, 59], with layers that reduce spatial
resolution (strided convolutions) followed by upsampling layers
(deconvolutions), interspersed with VSC layers.

Figure 3: Processing flow for SCN workload Figure 4: Performance
characterization of SCN[18] inference for a typical ScanNet [11] dataset on
Intel-i7-8700K CPU with single core execution @ 3.7GHz (a) Layer-wise runtime
and break-up into constituent functions (b) Runtime break-up across all layers
(c) Performance scaling with multi-core execution

##  III Motivation

###  III-A Increasing complexity of 3D Visual processing

Over the years, compute/memory requirements for 3D visual processing have
increased multi-fold. (Table II). While 3D volumetric representations enable
higher accuracy (Table I), low-resolution representation can hurt accuracy
(Figure 5). Though compute and memory requirements grow in cubic order with
resolution size, the free space in 3D scenes, a source of exploitable ’spatial
sparsity’, motivates a hardware-software co-designed approach to acceleration
of 3D visual processing.

Figure 5: Correlation between compute needs and accuracy (mIoU) as a function
of resolution obtained by downsampling input pointclouds in ScanNet[11]. TABLE
II: A chronological overview of typical RGB-D/3D datasets.

Datasets | # Images/Models (#Objects) |  #Ops [18] |  I/O FP (grid) [18]
---|---|---|---
NYU Depth V2 [39] | 1.5k images (894) |  $\sim$2.3B |  $\sim$12MB ($4096^{3}$)
ModelNet [56] | 50k models (660) |  $\sim$9M |  $\sim$400kB ($30^{3}$)
ShapeNet [5] | 3M models (3135) |  $\sim$0.5B |  $\sim$1MB ($192^{3}$)
Matterport3D [4] | 194k images (40) | - | -
ScanNet [11] | 2.5M frames (40) |  $\sim$90B |  $\sim$65MB ($4096^{3}$)
Waymo [48] | 113K models (210K) |  $\sim$249B |  $\sim$128MB ($4096^{3}$)

###  III-B Sparse Convolution Network (SCN) workload profile

Figure 4 shows the runtime CPU profile of SCN [18] as a representative
workload. The middle layers take much lower execution time than initial and
last few layers as in the U-net, the middle layers operate on lowest
resolution needing lower compute. As the order of voxel processing can be
different from the memory layout, a gather operation for inputs and scattered
write for outputs is required. Overall, Input Gather and Output Write
dominates across the layers, due to the weight stationary dataflow, where
input-output index pairs are created and processed for each weight plane
independently. These components are majorly dominant for the initial and last
few layers, where the voxel resolution sizes are higher. Lack of tiled
execution and inability of CPU caches to hold the entire large pointcloud
significantly hurts data reuse.

We observe that the performance of the workload scales poorly with number of
cores and flattens beyond 4 cores (Figure 4-c). Further analysis shows that
thread synchronization (spin locks) and thread creation events (both of which
scale with #cores), increased load/store traffic for shared data, and
increased DRAM bandwidth bottlenecks are responsible for this lack of scaling.
On an Nvidia GPU, SCN performance improves by 2.34X over single-core CPU
(Figure 6), but effective GPU utilization is low due to high register usage
per thread, thereby limiting the number of threads that simultaneously
execute. By recompiling GPU kernels to enforce fewer registers per thread,
running thread count can be increased, but performance saturates due to memory
load-store bottlenecks.

Figure 6: SCN performance characterization on Nvidia GeForce-GTX-1080 @1.6GHz.
Though GPU is processing for most of the time, average GPU core utilization is
significantly low at 21% due to high register usage.

###  III-C The need for Sparsity-aware Dataflow Optimizers

Several dataflow optimizers have been proposed for dense DNNs [7, 8, 58, 21,
15, 30]. Since dense DNNs operate over regular data-structures, memory size
requirements and data accesses for each data-type can be estimated and an
optimal dataflow could be chosen offline without requiring input data. Since
network parameters are usually known prior to input data arrival, an optimal
dataflow could be chosen in offline mode per layer. Since 3D scenes are
typically spatially sparse, a uniform 3D tiling strategy would result in
extremely inefficient execution due to excessive memory consumption and uneven
work distribution. Though tiling 1D compressed data-structure through a
spatial hash map is a concise representation, it has the following drawbacks:
1) size of compressed data-structure varies per input pointcloud and across
different regions within a pointcloud 2) memory requirement and data accesses
can not be formulated as mathematical expressions 3) storing 3D data in an
unordered 1-D compressed format results in irregular data accesses as
convolution operations need to be performed on spatially proximate points in
3D space. In Sections IV-A, IV-B, IV-C, we show how specialized sparsity-aware
dataflow optimizers can effectively addresses these challenges.

###  III-D Accelerator Options for 3D Spatial Sparsity

As discussed in Section III-C, storing 3D spatially-sparse data in 1D
compressed format leads to inefficient execution due to irregular data
accesses as convolution operations need to be performed on spatially proximate
points in 3D space while the data is stored in 1D compressed format. We
discuss two potential ways to accelerate spatially sparse 3D processing:
1) Generic GEMM-based Acceleration: Implement 3D sparse convolution as a
dense-GEMM using efficient gather/scatter operations and performing GEMM over
the regularized data structure similar to reference CPU implementation (Figure
3).
Challenges: a) Since a 3D convolution is mapped onto a GEMM engine,
input/output features need to be re-fetched as many times as the local
receptive field, requiring prohibitively large data transfers and bandwidth.
b) Due to input-dependent sparsity, data-specific source/destination rulebook
tables need to be created by the host to enable a gather/scatter engine to
perform explicit data copies. When local sparsity is medium-to-high and the
point-cloud is large, the rulebook can significantly increase size and
bandwidth requirement.
2) Specialized Acceleration for 3D sparsity: Build specialized implementation
to locate input/output data on-the-fly while performing 3D sparse convolution
on a pool of MACs.
Challenges: a) While custom acceleration for 3D sparsity can entirely
eliminate the need for explicit metadata/rulebook generation, re-computation
of input/output data addresses would be required for each DNN layer with the
same resolution and at every accelerator core in the system. b) The number of
lookups into the sparse hash-map required per unit compute is input sparsity-
dependent. So, either the convolution engine will suffer significant
utilization loss due to the high variability in the local receptive field OR
to cover the variable latency and bandwidth requirement, the local buffering
would need to be prohibitively large. We propose in section IV-D a semi-
specialized accelerator for 3D sparsity which can process a compressed
metadata structure while adopting a tile-based sparsity-aware dataflow for
efficient data-movement.

###  III-E Custom Accelerator Requirements for 3D Spatial Sparsity

State-of-the-art sparse accelerators [22, 63, 41, 29] have been proposed for
sparse matrix multiply or sparse DNN models. In general, these sparse
accelerators are composed of two major blocks: 1) a Front-end which processes
metadata of input operands (feature-maps and weights) locating pairs of non-
zero input operands and 2) a Back-end for performing valid operations (MAC,
activation, pooling etc.) through PEs. Proposals such as Sparten [17] also
schedule work efficiently such that the imbalance between compute engines can
be mitigated.

TABLE III: Micro-Ops and data accesses savings with coarse level of work-
scheduling

|  |  | Tile Size |  | uOps | Data-accesses
---|---|---|---|---|---|---
Layers | Type | Total $Ops$ | ${\scriptscriptstyle(\Delta O,\Delta C,\Delta N)}$ | uOps | Savings | Savings
L2 | SCN | 1.3e+9 | (28,16,32) | 2.5e+6 | 512x | 1.93x
L12 | Conv | 4.4e+8 | (12,16,32) | 8.6e+5 | 512x | 1.94x
L24 | Dconv | 1.7e+8 | (860,8,8) | 2.7e+6 | 64x | 1.75x
L35 | SCN | 5.4e+9 | (212,8,16) | 4.2e+7 | 128x | 1.88x

We discuss challenges in adopting prior sparse-accelerators for 3D spatially
sparse data processing:
A) Front-end: for 3D spatially sparse convolution, valid input pair selection
depends solely on whether the voxel is active in the receptive field in the
input pointcloud and not on the weights. Further, the selection logic (Figure
7) significantly differs from the logic in any of these prior sparse
accelerators.
B) Back-End: the back-end in these accelerators receives a list of uops, each
representing a scalar multiply and accumulation operation (MAC). In 3D
spatially sparse convolution, each valid input pair selection requires either
a) a vector dot product (V-V) or b) a matrix-vector (M-V) multiply maximizing
the data reuse when there are multiple output channels (N) in a tile. Hence,
scheduling the work at the granularity of M-V would be more optimal than
dispatching the work per MAC. Table III shows how a M-V granularity of
dispatch can help to achieve a huge reduction in dispatched uops and in data
accesses between compute and on-chip memory for a few select layers in Unet
[18]. We use 64KB of on-chip memory with optimal tile size and dataflow
selection to minimize data accesses between on-chip and off-chip memory.

We thus present a sparse-accelerator for spatially-sparse DNNs that consists
of a) a sparse scheduler based Front-end to process custom-compressed 3D
metadata and b) a Back-end that dispatches matrix-vector operations which
maximizes data reuse and minimizes the dispatched uops.

##  IV Hardware-Software Co-Designed Acceleration for 3D Spatial Sparsity

###  IV-A Locality aware Data-structure (COIR)

Workload analysis in Section III-B provided the following insights: 1)
performing convolution for all the voxels together in the receptive field
(i.e. neighbourhood points) can reduce data accesses for input/output feature
maps 2) storing all input point indices per output point (or vice a versa) can
achieve metadata compression compared to weight wise listing of in-out
pairs[18]. Metadata size savings could be significantly higher for denser
pointclouds. Inspired by these insights, we propose a novel metadata structure
(COIR) with two flavors 1) Compressed Output Response Field (CORF), 2)
Compressed Input Receptive Field (CIRF) (Figure 7).

Figure 7: Two-dimensional illustration of the two flavors for Coir metadata
structure for submanifold convolution operator. With 3D visual data input,
output activations and weights would be in form of cuboids (instead of planes)

.

In CORF, each metadata entry corresponds to one unique point in input space
and consists of 1) the index of the input point, 2) indices of all the points
in the output space in the response field of the input point. In addition,
relative location of each neighbour is also required to select the appropriate
weight index for convolution operation. For this, a weight bit-mask is stored
for each entry with ’1’s indicating valid neighbours and bit-locations
indicating corresponding weight indices. Similarly, each CIRF entry contains
the index of a unique output point, the indices of all the input points in the
receptive field required to compute feature map for the output point and bit-
masks for weight index selection. Two flavours of metadata are motivated by
the observation that for the layers with resolution change (input and output
space having different resolution), input to output mapping is not one-to-one.
Hence, based on the sparsity in the pointcloud and the type of convolution
(upscaling or downscaling) picking the right flavor could provide higher
compression and data-savings over the other.

###  IV-B Point-cloud Reordering (Soar)

COIR improves data reuse of input points with CORF (or output points with
CIRF) by performing convolution across multiple neighbours per element access,
but it doesn’t ensure data reuse of neighbours across multiple input or output
points. To maximize data reuse for neighbours as well, entries in the metadata
needs to be ordered such that the entries with shared neighbours are co-
located in the metadata structure and processed in close temporal vicinity. To
achieve this, we propose Surface Orientation Aware Reordering (Soar) of the
pointcloud. We first create an Adjacency Map with the voxel index as key and a
list of indices to all its neighbours as value. When provided as input the
maximum number of voxels for which data can fit in the on-chip memory, Soar
divides the entire pointcloud into multiple chunks, each chunk composed of
ordered voxels obeying the maximum voxels constraint.

Figure 8: An illustration for dividing points in pointclouds in size
constrained chunks and reordering points in each chunk through Soar

As shown the Figure 8, Soar constructs an m-ary tree with each node
representing a voxel and an edge connecting two neighbouring voxels such that
each child node connects to only one parent even if there is more than one
neighbour at parent’s levels, though a parent node can connect to one or more
neighbours as child nodes. To begin, the voxel with minimum number of
neighbours is selected as the root node representing a corner in the
pointcloud. Soar pushes all its neighbours to a Neighbour Queue and pops out
voxels one-by-one. If a voxel is already selected in previous chunks, it gets
dropped otherwise it is inserted into the m-ary tree as a child node to the
first neighbour in breadth-first order. The inserted voxel is then tagged as
selected and all its neighbours are added to the Neighbour Queue. This process
continues till the number of voxels in the m-ary tree matches with the
provided threshold, upon which the m-ary tree is selected as the desired chunk
with voxels in the breadth-first order. The root node for the next chunk is
selected among voxels in the Neighbour Queue with minimal number of neighbours
and then this queue is flushed. This process gets completed when all the
voxels in the pointcloud are divided into chunks.

###  IV-C Sparsity Aware Dataflow (Spade)

Section III-C highlighted two key challenges of tiling 3D spatially sparse
data: 1) memory requirement varies highly due to input dependent spatial
sparsity 2) data accesses can not be estimated through mathematical
expressions due to irregular data-structures. In this section, we propose a
framework for dataflow exploration for spatially sparse data processing.

Figure 9: Tiling 1D compressed data-structure for 3D spatially sparsed data
Figure 10: Spade Dataflow Exploration Framework

For a layer $\mathcal{L}$, let the total number of input voxels, output
voxels, filter size, input channels, output channels and metadata size be
represented as $I$, $O$, $K$, $C$, $N$ and $M$ respectively. And if $\Delta$’s
correspond to respective values in a given tile $\mathcal{T}$ (Figure 9), then
the tile size $\Delta T$ can be expressed as:

$\footnotesize\Delta T=(\Delta I.\Delta C)+(\Delta O.\Delta N)+(\Delta
K.\Delta C.\Delta N)+\Delta M\\\ $ (1)

For a number of output voxels ($\Delta O$) in the tile, required number of
input voxels and metadata size could be obtained per region
($\mathcal{R}^{\Delta O}_{i}$) as:

$\footnotesize\begin{split}\Delta I=f_{I}(\mathcal{R}^{\Delta O}_{i},\Delta
O),\;\Delta M=f_{MO}(\mathcal{R}^{\Delta O}_{i},\Delta O)\end{split}$ (2)

Tile size $\Delta T$, therefore, could be formulated as a complex function of
$\Delta O$, $\Delta N$ and $\Delta C$. There are two possible ways of tiling:
1) dynamic tiling and 2) static tiling. In dynamic tiling, the data fetch
module can keep fetching additional input feature maps as required for
computing every new output feature map till the on-chip memory is full, thus
each tile can have different value of $\Delta O$. Note that to enable this,
$\Delta N$ and $\Delta C$ need to be known prior to the execution and,
therefore, a joint optimization of all tiling parameters could not be
performed. A solution to this would be to process the metadata before the DNN
execution extracting out region information ($f_{I}$, $f_{MO}$) for every
region and empirically choose the optimal tiling candidates by iterating over
all possible values of $\Delta C$ and $\Delta N$ pairs. This would explode the
dataflow exploration space and require multiple passes of metadata processing
significantly degrading latency in real-time scenarios.

Figure 11: Micro-Architecture block diagram for Sspnna, (a) WAVES group
features as per weight planes, stores tuples into Link-List index queue, (b)
SyMAC connects DeNNs as group of systolic arrays along the weight data, ⑥
perform caching and local accumulation on hits (c) DeNN block where IC-data is
buffered, to be reused among multiple output channels and multi casted to all
the PEs.

Thus, we propose to decouple extraction of region information in the form of
sparsity attributes and then perform dataflow exploration using these
attributes via an analytical framework. We compute sparsity attributes,
$\mathcal{SA}_{I}$ and $\mathcal{SA}_{MO}$, as function of $\Delta O$ over all
regions (Eqn. 3). Note that $\mathcal{SA}_{MO}$ represents Average number of
voxels in Receptive Field (ARF) for a given region, while $\mathcal{SA}_{I}$
takes the form of $(1+\beta)$ where $\beta$ reflects the fraction of voxels at
region boundary.

$\footnotesize\begin{split}\mathcal{SA}_{I}(\mathcal{R}^{\Delta O}_{i},\Delta
O)&=\left(f_{I}(\mathcal{R}^{\Delta O}_{i},\Delta O)\right)\;/\;{\Delta O}\\\
\mathcal{SA}_{MO}(\mathcal{R}^{\Delta O}_{i},\Delta
O)&=\left(f_{MO}(\mathcal{R}^{\Delta O}_{i},\Delta O)\right)\;/\;{\Delta
O}\end{split}$ (3)

We adopt static tiling with two ethods: 1) Strict Static Tiling (SST) and 2)
Relaxed Static Tiling(RST). In SST, $\mathcal{SA}_{I}$ and $\mathcal{SA}_{MO}$
with the highest value across all regions are picked for each $\Delta O$ to
ensure worst-case tile size allocation while under-utilizing the on-chip
memory for quite a few tiles. In RST, to improve memory utilization, we use
nth quantile of $\mathcal{SA}_{I}$ and $\mathcal{SA}_{MO}$ such that majority
of the tiles fits within on-chip memory. The tiles overshooting the on-chip
memory are split into two (or a next power of two) such that each sub-tile
fits well into the on-chip memory. To calculate data transfers and operations,
we use $\mathcal{SA}^{Avg}_{I}$ and $\mathcal{SA}^{Avg}_{MO}$ (Eqn. 4)
averaging the sparsity attributes over all the regions ($\mathbb{R}^{\Delta
O}$) for each $\Delta O$.

$\footnotesize\begin{split}\mathcal{SA}^{Avg}_{I}(\Delta
O)&=\left(\Sigma_{\mathcal{R}^{\Delta O}_{i}\in\mathbb{R}^{\Delta
O}}\mathcal{SA}_{I}(\mathcal{R}^{\Delta O}_{i},\Delta
O)\right)/\;|\mathbb{R}^{\Delta O}|,\\\ \mathcal{SA}^{Avg}_{MO}(\Delta
O)&=\left(\Sigma_{\mathcal{R}^{\Delta O}_{i}\in\mathbb{R}^{\Delta
O}}\mathcal{SA}_{MO}(\mathcal{R}^{\Delta O}_{i},\Delta
O)\right)/\;|\mathbb{R}^{\Delta O}|\end{split}$ (4)

Similar to dense DNN, we choose between three types of walk-patterns
($\mathscr{WP}$) 1) Input Stationary ($IS$) 2) Output Stationary ($OS$) and 3)
Weight Stationary ($WS$). Note that Eqn. 2, 3 and 4 could also be expressed as
functions of $\Delta I$ computing for $\Delta O$ and $\Delta M$ with CORF
metadata structure and ARF representing as Average Response Field. Using the
analytical framework (as shown in Figure 10), Spade explores the entire
dataflow design space to arrive upon the best tile size, walk pattern and
metadata structure ($\mathscr{MD}$) for each layer in the network given an
input pointcloud. Spade’s Analytical framework minimizes data accesses
$\mathscr{DA}$ (Eqn. 5) between the on-chip memory and the off-chip memory
over the entire dataflow design space
$\mathcal{D}=\\{(\mathcal{T},\mathscr{WP},\mathscr{MD})\\}$.

$\footnotesize\begin{split}\mathscr{DA}&\left(\mathcal{D}\right)=F_{WS}\left(\mathscr{WP},\lceil
O/\Delta O\rceil\right).\left(C.N.K\right)\\\
&+F_{IS}\left(\mathscr{WP},\lceil N/\Delta
N\rceil\right).\left(\mathcal{SA}^{Avg}_{I}(\Delta O).O.C\right)\\\
&+F_{OS}\left(\mathscr{WP},\lceil C/\Delta
C\rceil\right).\left(O.N+\mathcal{SA}^{Avg}_{MO}(\Delta O).O\right)\\\
\text{where,
}&\;\;F_{X}(Y,Z)={1\;if\;{\left(Y=X\right)},\;else\;{Z}}\end{split}$ (5)

###  IV-D 3D-Sparse-NN-Core Micro-architecture: Sspnna

Section III-E described the distinctive requisites of a custom accelerator for
3D spatial sparsity, especially contrasted with prior sparse accelerators. We
describe in this section, the microarchitecture of the Sspnna (Spatially
SParse Neural Network Accelerator) core which lies at the heart of our AccSS3D
solution. The primary requisite for the hardware accelerator (HWA) is to
process a tile (Figure 9), convert from sparse to dense representation by
restructuring the tile data in the Front-end and perform dense compute in the
Back-end.

Top-level Overview: The Sspnna HWA is comprised of two major blocks (a) WAVES
Front-end\- Weight plane based Active Voxel Execution Scheduler (b) SyMAC
Back-end\- Systolic and Multicast based MAC Computation in Figure 11. Metadata
(MT) is partitioned into header and feature data, where header stores Coir
bit-masks and feature data stores the feature indices and its data. HWA also
has a memory arbiter, a configuration and a control block. The Global event
controller initiates execution after loading the L1 and configuring the HWA.
Upon start, the WAVES scheduler formats the metadata and then triggers SyMAC
for channel-wise computation and output element accumulation, during which,
WAVES starts working on formatting the next set of data.

The WAVES Front-end rearranges the spatially distributed voxels along weight
plane (Figure 11-a). Its subblock MT HDR Processor fetches weight mask and
corresponding IFM and OFM indices. By using smart-lookup, it finds weight
index for 4 active neighbor voxels per cycle. The HDR Format block forms
tuples by grouping 4 features per weight plane, using 27 blocks to manage all
weight planes together. Link-List based buffer is used to provide dynamic
memory space allocation for weight planes, enabling more storage for weights
with more active voxels. This design choice was motivated by the observation
that fixed allocation of resources per weight plane leads to significant
under-utilization, since it depends on ARF. By allocating 1 FIFO per weight
plane for tuple storage, higher occupancy for all the FIFOs cannot be
achieved. This under-utilization can be visualized as a wavy line touching the
top element in each FIFO. The Link-List design helps increase the utilization
by dynamic allocation of more resources to planes with higher number of active
neighboring voxels, allowing us to accommodate 1.5X-2X more metadata lines in
the same size of memory internal to the Sspnna.

The SyMAC Back-end increases the data reuse within the HWA by connecting
multiple compute blocks systolically, multicasting the input features to a set
of PEs and accumulating data within the PEs as per channel length. Figure
11(b) shows three options for systolic groups as Ⓐ, Ⓑ, Ⓒ, which can be
dynamically selected for weight plane grouping in the WAVES. Figure 11(b)⑥ ACC
OFM block has local buffering with cache lookup capability which helps in
reducing memory transactions for elements with cache hit. Figure 11(c) shows a
DeNN block where input features are buffered and reused for all output
channels, by convolving with different weights. PEs are implemented using tree
structure where they can perform dot-product on IEEE754 Full Floating-Point
numbers and accumulate locally along the input channels.

4-DeNN configuration with 4 PEs per DeNN computes 4 elements per PE per cycle
allowing Sspnna to support 64-MUL operations per cycle. Changing Sspnna
configuration to 8 DeNNs, working in two systolic groups of 4-DeNN each,
doubles performance to 128 MUL operations per cycle, but does not require any
more memory ports for weights. Through conscious design choices we reduce
bandwidth requirement by 68%: a) Local input buffer sharing and Systolic
weight connection reduce bandwidth requirement by 37% and 25% respectively, b)
local accumulation within PEs for $\Delta C$ and $\Delta N$ greater than 15
provides another 6% reduction.

Figure 12: Micro-Architecture block diagram for Admac, Ⓐ is common block
streaming voxels from memory, Ⓑ prepares adjacency map to help Ⓒ create
Metadata with minimal memory reads

###  IV-E Adjacency Map accelerator Micro-Architecture - Admac

Section IV-B described the requirements for reordering pointcloud and Section
IV-C, Figure 9 described metadata structure for tiling. We describe in this
section, the Micro-Architecture of Admac-Adjacency map and Metadata
Accelerator core in Figure 12. Input voxels (x,y,z) are fetched serially by
block Ⓐ in Figure 12. Block Ⓑ creates lookup table for all the active voxels.
For faster lookup, Admac maintains hierarchical lookup table, at level one it
encodes active voxels at higher granularity (called voxel 3D groups) and at
second level it stores active information and corresponding memory address per
voxel. Voxel information is stored in an 8-banked memory where bankID is
encoded using {y[2], z[1:0]}. Within the bank, voxels are hashed so that each
memory read of 64 Bytes can provide information for 16 voxels as per {y[1:0],
x[1:0]} addressing. This specific hashing helps in reading 26 neighboring
voxels in a single cycle, with the exception of boundary voxels. Block Ⓒ
creates Adjacency List for the voxels in the memory using the Sparse hash from
Ⓑ. Blocks Ⓒ①,②,③ compute address of neighbors, reads voxel information and
write to memory after packing data as per metadata structure.

##  V Scale-up Architecture for 3D Spatial Sparsity

In this section, we present Accelerator for Spatially Sparse 3D DNNs, an
architecture (Figure 13) targeting 3D spatially sparse DNN applications.

###  V-A Overall Architecture

####  V-A1 On-die memory architecture

Multi-level memory hierarchies have been widely adopted as they allow high
bandwidth short-distance reuse at smaller inner level memories with lower
latencies, while longer-distance reuse are captured at higher capacity by
outer memory levels. The two levels of memories in the AccSS3D architecture
are managed as scratchpads by the software to orchestrate the 3D sparse-CNN
execution following the optimal directives of the Spade. A scratchpad-based
architecture with multiple levels of memory, requires compute and data-
transfer needs to be effectively synchronized to maximize compute and
bandwidth utilization. As a result of the locality-aware tile-based execution
as described in section IV-C, there is significantly higher space sensitivity
at L1 compared to L2. This is because when processing similar number of
voxels, the unique-OFM to unique-IFM ratio is typically highly skewed (away
from 1) for L1 when compared to L2. This results in higher sensitivity for
reuse opportunity to memory size at L1 as compared to L2. This precludes
double-buffering at L1. Hence, we choose distinct compute and data-exchange
phases as in [52]. All data transfers from between the shared-L2 and a Sspnna
core’s L1 are blocked when the core is active, and the Sspnna core is idled
when data is being exchanged between its L1 and the shared L2.

####  V-A2 Scaled-up multi-sparse-NN Core architecture

To compensate for the increased latency due to sequential phases, we adopt an
overlapped tile execution model across the multiple Sspnna cores in our
scaled-up architecture (Figure 14-a). Using a shared bus at the L1-L2
interface, tile data is transferred between the shared-L2 and a Sspnna core’s
L1 memory while other cores are in their compute phases and this continues in
round-robin mode as each core enters its data exchange phase.

####  V-A3 Data transfers between L1, L2 and DRAM

We employ a DMA-based architecture to accomplish data transfers in the data-
exchange phases. DMAs are triggered through a global hardware-based event
controller, with the software specifying data-movement details such as
source/destination addresses and number of bytes through the DMA engines
tables. We provision two DMA engines: one each for the L1-L2 and L2-DRAM
interfaces respectively. Based on the selected metadata structure (CORF or
CIRF) - either one of the datatypes between IFM and OFM is accessed in order,
while the other can be un-ordered (see Figure 9). We use block transfers
programmed as a single DMA table entry for the entire tile for the datatype
with ordered accesses. For the other datatype, we use DMA table entries per
voxel level. Since weights are dense, a block transfer is sufficient. DMA
transfers for all tiles of a layer are chained in a pre-selected order as this
allows limiting CPU/software intervention to only once per layer.

Figure 13: Proposed architecture for spatial sparsity: Accelerator for
Spatially Sparse 3D DNNs

####  V-A4 Load Balancing with Multi-core

Though Spade ensures uniform tiling (equal $\Delta N$, $\Delta C$ and $\Delta
O$ or $\Delta I$), due to region dependent sparsity (varying
$\mathscr{SA}_{MO}$), operations per tile could differ. Asymmetric core
execution times and data transfer period can introduce idle periods for both
processing cores and the DMA engine (Figure 14b-left). To address this, we
sort all the spatial tiles based on ’Ops-per-tile’ in descending order. Based
on parallelism along $N$, cores are grouped with each group to process
different $N$-tiles. The sorted spatial tiles are scheduled in order and
round-robin fashion on cores in each group maximizing concurrent execution
(Figure 14-b-right).

###  V-B Dataflow for Multi-level memory hierarchy

Multi-level memory hierarchies pose significant challenges for dataflow
optimization, as minimization of data-transfers is required at every level of
the memory hierarchy to enable best performance at lowest hardware and energy
cost. Inspired by dense DNN dataflow optimizers [8, 58, 21], we adopt
hierarchical dataflow search starting from outermost to innermost level of the
on-chip memory. One of the drawbacks of hierarchical search is the likelihood
of picking a globally suboptimal dataflow. For example data access
minimization at $L_{q}{\leftrightarrow}L_{q+1}$ memory interface may choose
tile candidates with lower spatial data reuse and higher temporal data reuse,
which could increase data accesses at inner interface
$L_{q}{\leftrightarrow}L_{q-1}$. To address this, we propose Constrained
Access based Reuse Opportunity Maximization (CAROM) to maximize spatial reuse
while keeping the number of data accesses at $L_{q}{\leftrightarrow}L_{q+1}$
interface lower than a maximum threshold value ($\mathscr{DA}_{th}^{L_{q}}$)
without being bandwidth constrained. For this, CAROM first identifies a set of
dataflow candidates $\mathbb{D}^{L_{q}}$, such that:

$\small\begin{split}\mathbb{D}^{L_{q}}=&\left\\{\mathcal{D}_{i}:\mathscr{DA}_{\mathcal{D}_{i}}^{L_{q}}\leq\mathscr{DA}_{th}^{L_{q}}\right\\}\cup\left\\{{argmin}_{\mathcal{D}_{i}}(\mathscr{DA}_{\mathcal{D}_{i}}^{L_{q}})\right\\}\\\
\end{split}$ (6)

where, $\mathscr{DA}_{th}^{L_{q}}$ is computed based on number of operations
to be performed on the working set at $L_{q+1}$, total compute (Ops/sec)
available to an instance of memory level $L_{q}$ and bandwidth at
$L_{q}{\leftrightarrow}L_{q+1}$ interface:

$\small\begin{split}\mathscr{DA}_{th}^{L_{q}}=(Ops^{L_{q}}\times{BW}^{L_{q}})/Total\\_Comp^{L_{q}}\\\
\end{split}$ (7)
$\small\begin{split}\text{where,}\;Ops^{L_{q}}=\mathscr{SA}_{MO}^{Avg}\left(O^{L_{q}}\right).O^{L_{q}}.N^{L_{q}}.C^{L_{q}}\end{split}$
(8)

CAROM then picks the optimal dataflow over the set $\mathbb{D}^{L_{q}}$
maximizing reuse opportunity ($\mathscr{RO}^{L_{q-1}}$) for $L_{q-1}$ level.

$\small\begin{split}\mathcal{D}_{opt}^{L_{q}}={argmax}_{\mathcal{D}_{i}\in\mathbb{D}^{L_{q}}}\left(\mathscr{RO}_{i}^{L_{q-1}}\right)\end{split}$
(9)

Since for a given working set, reuse opportunity is proportional to the total
number of operations to be performed on the working set, $Ops^{L_{q-1}}$ is
used for reuse opportunity maximization. The optimal tile candidate at a
memory level $L_{q}$ acts as the working set for level $L_{q-1}$. And,
therefore, CAROM continues to pick optimal dataflow(s) from outer levels to
inner levels except the innermost level as per the above criterion. For the
innermost memory level, it selects the optimal dataflow by minimizing data
accesses (${{argmin}_{\mathcal{D}_{i}}\left(\mathscr{DA}_{i}\right)}$).

Figure 14: (a)Execution flow orchestrating asynchronous scheduling of sparse-
NN cores with serialized DMA transfers. (b) An illustration of improved
performance with smart work scheduling. Wx and Dx represents processing-work
and data-transfer respectively as associated with the tile $\mathcal{T}_{x}$.

To improve data locality across all the memory levels through pointcloud
reordering, Soar (Section IV-B) is extended to perform hierarchical pointcloud
ordering starting from innermost to outermost levels. Given optimal tiling
from Spade, Soar groups the entire pointcloud in chunks and finds optimal
ordering of points in each chunk based on tilling parameters for the innermost
memory. Reinterpreting each chunk as a point, Soar is reapplied to recursively
group these chunks into super-chunks with optimal ordering based on tile
parameters of the outer memory level, till the outermost level.

###  V-C Minimizing Spade latency overhead

As described in sections IV-C and V-B, Spade requires pre-processing of input
pointcloud data to extract sparsity attributes ($\mathscr{SA}$’s) to perform
dataflow exploration. Extraction of $\mathscr{SA}$’s could add significant
overhead to end-to-end latency. To minimize this, we explore: 1) if the
sparsity attributes could be categorized into two sets: a) common attributes
which are consistent across pointclouds - referred to as Meta Sparsity
Attributes ($\mathscr{MSA}$), b) Input Specific Attributes ($\mathscr{ISA}$)
which varies highly across pointclouds; and, 2) whether by using
$\mathscr{MSA}$, optimal dataflow candidates could be pre-computed for
selected binned values of $\mathscr{ISA}$. Thus, we correlate
$\mathscr{SA}^{Avg}$ over randomly picked pointclouds (Figure 15) and observe
that:
1\. $\mathscr{SA}_{I}^{Avg}(\Delta O)$ exhibits high variance across various
values of $\Delta O$, but follows similar pattern across pointclouds. Also,
$\mathscr{SA}_{I}^{Avg}(v)$ shows a high correlation with
$(\alpha_{m}/\sqrt[m]{v})$ representing surface area to volume ratio of
$m$-dimensional cube with volume $v$ and faces $\alpha_{m}$.
2\. $\mathscr{SA}_{MO}^{Avg}(\Delta O)$ which represents the ARF, remains
constant with $\Delta O$ for a pointcloud, but varies across pointclouds.
Based on above observations, we propose an offline version of Spade to use
$\mathscr{MSA}_{I}$ as the meta sparsity attribute and ARF as $\mathscr{ISA}$.
The $\mathscr{MSA}_{I}$ is computed over a representative set of pointclouds
$\mathbb{P}$ using Eq. 10. We generate tables of optimal dataflow candidates
with ARF as table index, for all network layers. For tile allocation, we use
$90$-quantile of $\mathscr{SA}_{I}^{Avg}(\Delta O)$ along with RST as
described in IV-C. Note that the proposed semi-offline mode of dataflow
exploration strikes a conscious balance between DNN execution performance and
runtime latency overhead of sparse dataflow selection.

$\small\mathscr{MSA}_{I}^{Avg}(\Delta
O)=\left(\Sigma_{p\in\mathbb{P}}{\mathscr{SA}_{I,p}^{Avg}}(\Delta
O)\right)\;/\;|{\mathbb{P}}|$ (10)

Figure 15: Sparsity attributes for different points clouds

To minimize latency overhead, Spade is deployed as two components (Figure 16):
1) offline-Spade \- to generate a table of optimal dataflows for multiple
selected ARF values, and 2) on-the-fly Spade (OTF-Spade) - to reorder a given
input pointcloud and select optimal dataflow for the input. Though Adjacency
Map and COIR metadata contain a similar data structure, due to tiling and
reordering, entries in Adjacency Map are re-grouped to create tiled metadata
($\Delta M$) based on tiling parameters of innermost memory level. To transfer
data between memory levels, required DMA tables (as mentioned in section V-A3)
are generated prior to DNN execution. To further hide the latency for OTF-
Spade, DNN execution is kicked-off just after the OTF-Spade completes
processing for the first layer. Since OTF-Spade processing for the rest of the
layers does not depend on DNN execution of previous layers, both the threads,
OTF-Spade and DNN execution, proceed independently without further need for
synchronization.

##  VI Evaluation

###  VI-A Setup, Methodology and Workloads

We evaluate AccSS3D using a whole chip performance and energy model. We
design, synthesize Sspnna core with 64KB L1 memory using Synopsys DC [1] at
1GHz clock, perform Place and route using Synopsys IC Compiler II [2]. L2
memory of 2$\times$1MB is constructed hierarchically, using sub-arrays of size
16KB each, with 4 banks per instance, 4 sub-banks per bank and 4 sub-arrays
per sub-bank. Power consumption for compute and on-chip buffers is estimated
using Synopsys PrimeTimePX from SystemVerilog (SV) simulation. Interconnect
energy is computed using estimated wire lengths and added to L1 and L2 access
energy estimates. Area and energy cost for Admac is estimated using micro-
architecture accurate model and counting data access events. DRAM power is
taken from Micron power calculator [37] for DDR4-2660.

Figure 16: Processing flow for offline mode and on-the-fly mode of Spade

Performance: To measure AccSS3D performance, we obtain execution cycles for
Sspnna core for each tile processing in every network layer through
SystemVerilog simulation. For end-to-end latency estimation, we simulate
multi-core asynchronous execution model through a detailed analytical
framework feeding per tile execution time from the SV simulation and including
processing time for OTF-Spade (Section V-C). CPU (Intel-i7-8700K @3.7 GHz)
performance is measured through VTune [3] and power is estimated using PSST
tool [38]. GPU (Nvidia GeForce-GTX-1080 @1.6GHz) performance is obtained form
visual profiler [40] and power is reported from nvidia-smi. We denote single
core CPU, 4-core CPU and GPU software baseline performance as 1-CPU, 4-CPU and
GPU.
Workloads and Datasets: We evaluate AccSS3D on three applications of 3D visual
analytics 1) 3D semantic segmentation 2) 3D object detection 3) 3D scene
completion picking three state-of-the-art workloads 1) SCN [18], 2) PV-RCNN
[46] and 3) SGNN [12] one from each application. We choose 3D pointclouds from
ScanNet [11] and Waymo Open Dataset [48] (Table II, rows 5 and 6) for indoor
and outdoor scenarios.

###  VI-B Scaled-up Configuration for AccSS3D

We describe a 1024 MACs based AccSS3D architecture that achieves a 50x
execution-time speed-up at an operating frequency of 1 GHz compared to 1-CPU.
Given the prohibitively large architecture configuration space, we adopt a
hierarchical framework to arrive at the most optimal configuration. Firstly,
the optimal L2 memory size is selected such that total DRAM accesses do not
exceed $1.5\times$ of the total data footprint accumulated across layers while
avoiding bandwidth bottlenecks at DRAM interface for a given DRAM bandwidth. A
joint optimization is then performed to optimize L1 memory size,
L1$\leftrightarrow$L2 bandwidth and number of the Sspnna cores. Figure 17
shows performance sensitivity to these parameters for a chosen pair of L2
memory size and DRAM bandwidth. Performance scales with cores up to a certain
number owing to a reduction in idle time during data-transfer phase. With
further increase in cores, data replication for shared datatype dominates,
degrading the performance. At higher L1$\leftrightarrow$L2 bandwidth and
larger L1 size, data-transfer time reduces significantly favoring lower core
count configuration. Similarly, we obtain the optimal architecture
configuration for each DRAM bandwidth point (Figure 18) and select the optimal
bandwidth that maximizes performance. Since the L2 is dual-buffered, we
provision for 2x the required size. Figure 20-Right lists the optimized
architecture parameters.

Figure 17: Performance Sensitivity to L1 memory size, L1$\leftrightarrow$L2 bandwidth and core count at an L2 size of 2 MB and DRAM bandwidth of 48 Bytes/clk. Figure 18: Relative performance, on-chip and DRAM data transfers with optimal architecture configuration for select DRAM memory bandwidth points Figure 19: Layer-wise Power Reduction and Performance for SCN/ScanNet with AccSS3D for 3D sparse convolution over 1-CPU and 4-CPU [18] (setting OpenMP threads to 1 and 4). Hyper-threading was disabled during measurement. Idle power was subtracted from total power to get workload power. TABLE IV: Speed-up & Energy Savings with AccSS3D on SCN/ScanNet | DNN Only | End-to-end
---|---|---
1-CPU | 4-CPU | 1-CPU | 4-CPU
Speed-up | 36.6x | 16.8x | 23.7x | 11.8x
Energy Savings | 2079.0x | 2232.0x | 23.2x | 24.8x

###  VI-C Power, Performance and Area Analysis

As described in Section IV-D, the Sspnna core can be scaled with the number of
internal DeNN instances. The design parameters, area breakup for the major
blocks on a typical 16nm process and the local buffering details in the Sspnna
core for both configurations are shown in Figure 20. With dual 8KB of local
buffer we were able to hide the execution latency of WAVES MT formatting.
Figure 20 also shows the physical placement for the Sspnna core where we
achieved a high utilization 72.6% by placing the logic blocks as dictated by
the internal dataflow. The energy consumption of the Sspnna compute core and
other local storage contributes to $\sim$50% of total energy and remaining 50%
is attributed to SRAM accesses. 70% of the logic power is consumed by the
clock network whereas sequential and combinational cells consume 5% and 25%
respectively. For Admac, energy is dominated by DRAM reads. Local buffer
access and logic energy contributes to only 2% of total energy.

Figure 19 shows layer-wise speed-up and power reduction for the 3D sparse
convolution operation in the SCN network with ScanNet. Speedup for initial and
last few layers reaches up to 80x over 1-CPU. As Spade adopts spatial sparsity
aware tiled execution, data accesses are reduced significantly. With tiled
metadata, ordered data transfers through DMAs and asynchronous execution
model, data transfer latencies are overlapped with the accelerator’s compute,
as compared to CPU execution where Input Gather and Output Write incur high
sequential latency. In the middle layers, reuse opportunity is significantly
higher, therefore the impact of dataflow optimization is low, yet speedups
close to 20x are achieved over 1-CPU. AccSS3D achieves a power reduction by
56.8x and 132.9x on average across all layers compared to 1-CPU and 4-CPU
respectively. Since middle layers are convolution heavy, CPU achieves higher
instructions-per-cycle resulting in higher power consumption. Therefore, power
reduction with AccSS3D is relatively higher for the middle layers.

Table IV summarises speed-up and energy reduction for both 3D sparse
convolution operation and end-to-end scene segmentation over CPU baselines for
SCN on ScanNet.

Figure 20: Left: Physical placement and area utilization of Sspnna, Right-Top:
16nm Sspnna Design parameters, Right-Bottom: Architecture Parameters.

Figure 21 shows power and performance for two additional workloads (PV-RCNN,
SGNN) and including Waymo’s outdoor dataset, where AccSS3D is compared with
1-CPU, 4-CPU and GPU. For PV-RCNN and SGNN networks, acceleration for
Adjacency Map creation provides significant speed-up and energy savings as
size of pointcloud is relatively higher than number of channels ($N,C$) in
these network topologies.

Figure 21: Power, Performance and Energy Savings (including DRAM) across
workloads and datasets with AccSS3D over CPU and GPU baselines.

###  VI-D AccSS3D Feature Analysis

We evaluate the goodness of AccSS3D features as described in Sections IV and V
(Figure 22). We collect performance metrics for each feature by disabling it
from the fully-featured AccSS3D. As reference software implements a weight-
stationary dataflow with no spatial tiling, it was infeasible to implement for
few layers due to large weight size and also likely to be unoptimized for a
system with limited memory such as the proposed AccSS3D. Hence, we picked
input-stationary dataflow as a reasonable baseline which performs tiling on
available on-chip memory, equally distributing tiles along output channels
($N$) onto many-cores and supporting on-chip partial accumulation minimizing
DRAM accesses. Optimal tiling and walk-pattern selected by Spade provides
significant reduction in both on-chip and DRAM data accesses compared to
baseline dataflow. A data-accesses minimization at L2 results in lower DRAM
accesses, but it increases on-chip data transfers and hence performance drops
significantly due to on-chip bandwidth bottlenecks. Carom helps alleviating
this issue by striking a balance between the DRAM and the on-chip data-
transfers without being bandwidth limited at DRAM interface. Comparing with
input pointcloud dependent $\mathcal{SA}$ based dataflow ($\mathscr{ISA}$),
AccSS3D with $\mathscr{MSA}$ marginally loses performance for a few
pointclouds while it provides significant reduction in end-to-end latency
through offline-dataflow. Gains with Soar based pointcloud reordering varies
across pointclouds as scope for the reordering depends on input geometry and
scan order performed during the data acquisition. Figure 23 shows relative
data-access savings with Soar comparing with three different scan-orders along
x, y and z direction.

Figure 22: Impact of different AccSS3D features (Soar, Spade, Carom, Otf-
Spade) on performance, on-chip energy savings, and DRAM data accesses
evaluated across different input pointclouds in ScanNet dataset

.

###  VI-E CPU Performance with Spade

To evaluate the performance impact of Spade on a CPU only system, we implement
tiling and loop order in the reference SCN-CPU baseline [18]. Performing the
3D sparse convolution as per Coir metadata structure requires irregular data
accesses interleaved with compute. Without explicitly ensuring data residency
in inner level caches, processing performance will be limited by latency. For
efficient processing, irregular data accesses need to be separated from the
convolution. To achieve this, similar to the reference CPU baseline, we gather
input and weights into local buffers and after convolution we perform
scattered write for output features. Since footprint for most of layers
exceeds the capacity of the CPU’s last-level-cache (LLC) and given the high
latency to DRAM memory, we optimize for DRAM accesses. The dataflow optimizer
assumes 10% of LLC’s capacity to be used for code and miscellaneous data and
remaining 90% would be be available for the SCN’s working set. Figure 24 shows
the CPU performance with the optimized tiling and loop order as recommended by
Spade.

Figure 23: Left: Data access savings with Soar reordering over raster-scan
{inner, middle, outer loop}. Right: Effect of SOAR on a pointcloud; the thin
strips caused by raster scan would invoke multiple data refetches from
neighbouring tiles during convolution. Figure 24: CPU performance improvements
with Spade

For brevity, we show one layer from each spatial resolution. With Spade,
overall performance improves by 18%. For some layers gain performance upto
74%, while for a few layers it drops by 21%. These layers have smaller
metadata (due to lower resolution) and more channels ($C,N$), hence Spade
prefers tiling across channels requiring metadata to be accessed and processed
repeatedly. We observe that high CPU overheads of metadata processing and
explicit scatter-gather operation are reasons for lower performance.

##  VII Related Work

Taichi [23] offers a high level interface to efficient data structures for
spatially sparse data by using index analysis. Eyeriss [7] proposed row-
stationary dataflow with diagonal data-feedforwarding over 2D systolic array
demonstrating substantial energy savings, while Eyeriss-V2 [8] extended it to
a scale-up architecture through mesh connections. [58] utilizes a tiling
structure through unrolling nested loops of convolution to maximize reuse at
different levels of caches. FlexFlow [35] aims to maximize compute utilization
by minimizing wastage due to spatial split of work among PEs. Morph [21]
optimizes dataflows for a 3-level memory scale-up architecture maximizing
reuse at each level in the hierarchy. ExTensor [22] proposes technique to find
non-zero element intersection for effective computation. Sparten [17] defines
SparseMap, which is two tuple of bitmask and performs efficient inner join
logic to feed MAC. SMAASH [29] compresses sparse matrix in software and
performs efficient index finding by hardware accelerator on compressed data.
[24] proposes fine grained channel gating technique and an accelerator to
exploit the dynamic sparsity. [63] proposes an accelerator with Indexing
Module to efficiently select and transfer needed neurons to PEs.

##  VIII Conclusion

Understanding of 3D objects and environment is critical for many real world
applications. To our best of knowledge, this is the first end-to-end solution
for accelerating 3D scene analysis by exploiting spatial sparsity through
sparsity-aware dataflow optimizer, novel micro-architecture and design for a
spatially-sparse compute engine and, employing custom software-hardware co-
designed methodologies.

## References

  * [1] “Tool from Synopsys, Design Compiler (Version L-2016.03-SP2).” [Online]. Available: https://www.synopsys.com
  * [2] “Tool from Synopsys, IC Compiler II (Version L-2016.03-SP5).” [Online]. Available: https://www.synopsys.com
  * [3] I. V. Amplifier, “Intel vtune amplifier,” 2019. [Online]. Available: https://software.intel.com/en-us/vtune
  * [4] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Niessner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3d: Learning from rgb-d data in indoor environments,” _arXiv preprint arXiv:1709.06158_ , 2017.
  * [5] A. X. Chang, T. Funkhouser, L. Guibas, P. Hanrahan, Q. Huang, Z. Li, S. Savarese, M. Savva, S. Song, H. Su _et al._ , “Shapenet: An information-rich 3d model repository,” _arXiv preprint arXiv:1512.03012_ , 2015.
  * [6] X. Chen, H. Ma, J. Wan, B. Li, and T. Xia, “Multi-view 3d object detection network for autonomous driving,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1907–1915.
  * [7] Y.-H. Chen, J. Emer, and V. Sze, “Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks,” in _ACM SIGARCH Computer Architecture News_ , vol. 44, no. 3. IEEE Press, 2016, pp. 367–379.
  * [8] Y.-H. Chen, T.-J. Yang, J. Emer, and V. Sze, “Eyeriss v2: A flexible accelerator for emerging deep neural networks on mobile devices,” _arXiv preprint arXiv:1807.07928_ , 2018.
  * [9] H.-Y. Chiang, Y.-L. Lin, Y.-C. Liu, and W. H. Hsu, “A unified point-based framework for 3d segmentation,” in _2019 International Conference on 3D Vision (3DV)_. IEEE, 2019, pp. 155–163.
  * [10] C. Choy, J. Gwak, and S. Savarese, “4d spatio-temporal convnets: Minkowski convolutional neural networks,” _arXiv preprint arXiv:1904.08755_ , 2019\.
  * [11] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Nießner, “Scannet: Richly-annotated 3d reconstructions of indoor scenes,” in _Proc. Computer Vision and Pattern Recognition (CVPR), IEEE_ , 2017.
  * [12] A. Dai, C. Diller, and M. Nießner, “Sg-nn: Sparse generative neural networks for self-supervised scene completion of rgb-d scans,” _arXiv preprint arXiv:1912.00036_ , 2019.
  * [13] A. Dai, D. Ritchie, M. Bokeloh, S. Reed, J. Sturm, and M. Nießner, “Scancomplete: Large-scale scene completion and semantic segmentation for 3d scans,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 4578–4587.
  * [14] R. di Bella, D. Carrera, B. Rossi, P. Fragneto, and G. Boracchi, “Wafer defect map classification using sparse convolutional networks,” in _International Conference on Image Analysis and Processing_. Springer, 2019, pp. 125–136.
  * [15] M. Gao, X. Yang, J. Pu, M. Horowitz, and C. Kozyrakis, “Tangram: Optimized coarse-grained dataflow for scalable nn accelerators,” in _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_. ACM, 2019, pp. 807–820.
  * [16] M. Garbade, Y.-T. Chen, J. Sawatzky, and J. Gall, “Two stream 3d semantic scene completion,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , 2019, pp. 0–0.
  * [17] A. Gondimalla, N. Chesnut, M. Thottethodi, and T. Vijaykumar, “Sparten: A sparse tensor accelerator for convolutional neural networks,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_. ACM, 2019, pp. 151–165.
  * [18] B. Graham, M. Engelcke, and L. van der Maaten, “3d semantic segmentation with submanifold sparse convolutional networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 9224–9232.
  * [19] B. Graham and L. van der Maaten, “Submanifold sparse convolutional networks,” _arXiv preprint arXiv:1706.01307_ , 2017.
  * [20] Y. Guo, H. Wang, Q. Hu, H. Liu, L. Liu, and M. Bennamoun, “Deep learning for 3d point clouds: A survey,” _arXiv preprint arXiv:1912.12033_ , 2019.
  * [21] K. Hegde, R. Agrawal, Y. Yao, and C. W. Fletcher, “Morph: Flexible acceleration for 3d cnn-based video understanding,” in _2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2018, pp. 933–946.
  * [22] K. Hegde, H. Asghari-Moghaddam, M. Pellauer, N. Crago, A. Jaleel, E. Solomonik, J. Emer, and C. W. Fletcher, “Extensor: An accelerator for sparse tensor algebra,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_. ACM, 2019, pp. 319–333.
  * [23] Y. Hu, T.-M. Li, L. Anderson, J. Ragan-Kelley, and F. Durand, “Taichi: a language for high-performance computation on spatially sparse data structures,” _ACM Transactions on Graphics (TOG)_ , vol. 38, no. 6, pp. 1–16, 2019.
  * [24] W. Hua, Y. Zhou, C. De Sa, Z. Zhang, and G. E. Suh, “Boosting the performance of cnn accelerators with dynamic fine-grained channel gating,” in _Proceedings of the 52Nd Annual IEEE/ACM International Symposium on Microarchitecture_ , ser. MICRO ’52. New York, NY, USA: ACM, 2019, pp. 139–150. [Online]. Available: http://doi.acm.org/10.1145/3352460.3358283
  * [25] R. Hwang, T. Kim, Y. Kwon, and M. Rhu, “Centaur: A chiplet-based, hybrid sparse-dense accelerator for personalized recommendations,” in _2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 2020, p. 1.
  * [26] G. Inc, “Google sparse hash.” [Online]. Available: https://github.com/sparsehash/sparsehash
  * [27] L. Jiang, H. Zhao, S. Liu, X. Shen, C.-W. Fu, and J. Jia, “Hierarchical point-edge interaction network for point cloud semantic segmentation,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 10 433–10 441.
  * [28] M. Jiang, Y. Wu, T. Zhao, Z. Zhao, and C. Lu, “Pointsift: A sift-like network module for 3d point cloud semantic segmentation,” _arXiv preprint arXiv:1807.00652_ , 2018.
  * [29] K. Kanellopoulos, N. Vijaykumar, C. Giannoula, R. Azizi, S. Koppula, N. M. Ghiasi, T. Shahroodi, J. G. Luna, and O. Mutlu, “Smash: Co-designing software compression and hardware-accelerated indexing for efficient sparse matrix operations,” in _Proceedings of the 52Nd Annual IEEE/ACM International Symposium on Microarchitecture_ , ser. MICRO ’52. New York, NY, USA: ACM, 2019, pp. 600–614. [Online]. Available: http://doi.acm.org/10.1145/3352460.3358286
  * [30] H. Kwon, A. Samajdar, and T. Krishna, “Maeri: Enabling flexible dataflow mapping over dnn accelerators via reconfigurable interconnects,” in _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_ , ser. ASPLOS ’18. New York, NY, USA: ACM, 2018, pp. 461–475.
  * [31] J. Li, Y. Liu, D. Gong, Q. Shi, X. Yuan, C. Zhao, and I. Reid, “Rgbd based dimensional decomposition residual network for 3d semantic scene completion,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 7693–7702.
  * [32] Y. Li, R. Bu, M. Sun, W. Wu, X. Di, and B. Chen, “Pointcnn: Convolution on x-transformed points,” in _Advances in neural information processing systems_ , 2018, pp. 820–830.
  * [33] Z. Li, X. Yan, Q. Wei, X. Gao, S. Wang, and S. Cui, “Pointsite: a point cloud segmentation tool for identication of protein ligand binding atoms,” _bioRxiv_ , p. 831131, 2019.
  * [34] S. Liu, Y. Hu, Y. Zeng, Q. Tang, B. Jin, Y. Han, and X. Li, “See and think: Disentangling semantic scene completion,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 263–274.
  * [35] W. Lu, G. Yan, J. Li, S. Gong, Y. Han, and X. Li, “Flexflow: A flexible dataflow accelerator architecture for convolutional neural networks,” in _2017 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2017, pp. 553–564.
  * [36] D. Maturana and S. Scherer, “Voxnet: A 3d convolutional neural network for real-time object recognition,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2015, pp. 922–928.
  * [37] D. Micron, “Power calculator,” 2020. [Online]. Available: https://www.micron.com/support/tools-and-utilities/power-calc
  * [38] N. Mubeen, “Workload frequency scaling law-derivation and verification,” _Queue_ , vol. 16, no. 2, pp. 50–66, 2018. [Online]. Available: https://github.com/intel/psst
  * [39] P. K. Nathan Silberman, Derek Hoiem and R. Fergus, “Indoor segmentation and support inference from rgbd images,” in _ECCV_ , 2012.
  * [40] Nvidia, “Nvidia visual profiler,” 2016. [Online]. Available: https://developer.nvidia.com/nvidia-visual-profiler
  * [41] A. Parashar, M. Rhu, A. Mukkara, A. Puglielli, R. Venkatesan, B. Khailany, J. Emer, S. W. Keckler, and W. J. Dally, “Scnn: An accelerator for compressed-sparse convolutional neural networks,” in _2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 2017, pp. 27–40.
  * [42] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 652–660.
  * [43] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,” in _Advances in neural information processing systems_ , 2017, pp. 5099–5108.
  * [44] R. A. Rosu, P. Schütt, J. Quenzel, and S. Behnke, “Latticenet: Fast point cloud segmentation using permutohedral lattices,” _arXiv preprint arXiv:1912.05905_ , 2019.
  * [45] S. Schmohl and U. Sörgel, “Submanifold sparse convolutional networks for semantic segmentation of large-scale als point clouds.” _ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences_, vol. 4, 2019\.
  * [46] S. Shi, C. Guo, L. Jiang, Z. Wang, J. Shi, X. Wang, and H. Li, “Pv-rcnn: Point-voxel feature set abstraction for 3d object detection,” _arXiv preprint arXiv:1912.13192_ , 2019.
  * [47] S. Song, F. Yu, A. Zeng, A. X. Chang, M. Savva, and T. Funkhouser, “Semantic scene completion from a single depth image,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1746–1754.
  * [48] P. Sun, H. Kretzschmar, X. Dotiwalla, A. Chouard, V. Patnaik, P. Tsui, J. Guo, Y. Zhou, Y. Chai, B. Caine _et al._ , “Scalability in perception for autonomous driving: Waymo open dataset,” _arXiv_ , pp. arXiv–1912, 2019\.
  * [49] M. Tatarchenko, J. Park, V. Koltun, and Q.-Y. Zhou, “Tangent convolutions for dense prediction in 3d,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 3887–3896.
  * [50] M. Teschner, B. Heidelberger, M. Müller, D. Pomerantes, and M. H. Gross, “Optimized spatial hashing for collision detection of deformable objects.” in _Vmv_ , vol. 3, 2003, pp. 47–54.
  * [51] H. Thomas, C. R. Qi, J.-E. Deschaud, B. Marcotegui, F. Goulette, and L. J. Guibas, “Kpconv: Flexible and deformable convolution for point clouds,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 6411–6420.
  * [52] N. Toon and S. Knowles, “Graphcore,” 2017. [Online]. Available: https://www.graphcore.ai
  * [53] L. Wang, X. Fan, J. Chen, J. Cheng, J. Tan, and X. Ma, “3d object detection based on sparse convolution neural network and feature fusion for autonomous driving in smart cities,” _Sustainable Cities and Society_ , vol. 54, p. 102002, 2020.
  * [54] Y. Wu, Y. Pang, B. Gao, and J. Han, “Complementary features with reasonable receptive field for road scene 3d object detection,” in _2019 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2019, pp. 3905–3909.
  * [55] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao, “3d shapenets: A deep representation for volumetric shapes,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1912–1920.
  * [56] Z. Wu, S. Song, A. Khosla, F. Yu, L. Zhang, X. Tang, and J. Xiao, “3d shapenets: A deep representation for volumetric shapes,” in _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2015.
  * [57] Y. Yan, Y. Mao, and B. Li, “Second: Sparsely embedded convolutional detection,” _Sensors_ , vol. 18, no. 10, p. 3337, 2018.
  * [58] X. Yang, J. Pu, B. B. Rister, N. Bhagdikar, S. Richardson, S. Kvatinsky, J. Ragan-Kelley, A. Pedram, and M. Horowitz, “A systematic approach to blocking convolutional neural networks,” _arXiv preprint arXiv:1606.04209_ , 2016.
  * [59] Y. Ye, H. Chen, C. Zhang, X. Hao, and Z. Zhang, “Sarpnet: Shape attention regional proposal network for lidar-based 3d object detection,” _Neurocomputing_ , vol. 379, pp. 53–63, 2020.
  * [60] Y. Ye, C. Zhang, and X. Hao, “Arpnet: attention region proposal network for 3d object detection,” _Science China Information Sciences_ , vol. 62, no. 12, p. 220104, 2019.
  * [61] J. Zhang, H. Zhao, A. Yao, Y. Chen, L. Zhang, and H. Liao, “Efficient semantic scene completion network with spatial group convolution,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 733–749.
  * [62] P. Zhang, W. Liu, Y. Lei, H. Lu, and X. Yang, “Cascaded context pyramid for full-resolution 3d semantic scene completion,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2019, pp. 7801–7810.
  * [63] S. Zhang, Z. Du, L. Zhang, H. Lan, S. Liu, L. Li, Q. Guo, T. Chen, and Y. Chen, “Cambricon-x: An accelerator for sparse neural networks,” in _The 49th Annual IEEE/ACM International Symposium on Microarchitecture_. IEEE Press, 2016, p. 20.