Practical Near-Data Processing for

In-Memory Analytics Frameworks

Mingyu Gao, Grant Ayers, Christos Kozyrakis
Stanford University
[Link]

PACT – Oct 19, 2015

 Motivating Trends
 End of Dennard scaling  systems are energy limited
 Emerging big data workloads
o Massive datasets, limited temporal locality, irregular access patterns
o They perform poorly on conventional cache hierarchies
 Need alternatives to improve energy efficiency

Deep Neural Networks

MapReduce Graphs
2
Figs: [Link]
 PIM & NDP
 Improve performance & energy by avoiding data movement
 Processing-In-Memory (1990’s – 2000’s)
o Same-die integration is too expensive

 Near-Data Processing
o Enabled by 3D integration
o Practical technology solution
o Processing on the logic die

Hybrid Memory Cube High Bandwidth Memory

(HMC) (HBM)
3
Figs: [Link]
Base NDP Hardware
High-Speed
Serial Link  Stacks linked to host multi-core processor
o Code with temporal locality: runs on host
Memory Host
o Code without temporal locality: runs on NDP
Stack Processor

 3D memory stack
o x10 bandwidth, x3-5 power improvement
Channel
o 8-16 vaults per stack
• Vertical channel
Bank
• Dedicated vault controller
NDP cores
...

DRAM Die o
• General-purpose, in-order cores
• FPU, L1 caches I/D, no L2
NoC Vau lt
Logic
• Multithreaded for latency tolerance
Vault
Logic Die 4
Challenges and Contributions
 NDP for large-scale highly distributed analytics frameworks
? General coherence maintaining is expensive
 Scalable and adaptive software-assisted coherence
? Inefficient communication and synchronization through host processor
 Pull-based model to directly communicate, remote atomic operations
? Hardware/software interface
 A lightweight runtime to hide low-level details to make program easier
? Processing capability and energy efficiency
 Balanced and efficient hardware

 A general, efficient, balanced, practical-to-use NDP architecture

5
Example App: PageRank
 Edge-centric, scatter-gather, graph processing framework
 Other analytics frameworks have similar behaviors
Edge-centric SG PageRank
edge_scatter(edge_t e) u = [Link] / src.out_degree
src sends update over e
sum += u
update_gather(update_t u) if all gathered
apply u to dst Sequential
[Link] (stream
= b * sum in/out)
+ (1-b)

while not done

Partitioned dataset, local processing
for e in all edges
edge_scatter(e)
for u in all updates Synchronization between iterations
update_gather(u)
Communication between graph partitions

6
Architecture Design
Memory model, communication, coherence, …
Lightweight hardware structures and software runtime
Shared Memory Model
 Unified physical address space across stacks
o Direct access from any NDP/host core to memory in any vault/stack

 In PageRank
o One thread to access data in a remote graph partition
• For edges across two partitions
Local Vault Memory

Local Remote
 Implementation Mem Ctrl Router
o Memory ctrl forwards local/remote accesses
Memory request
o Shared router in each vault
NDP NDP …… NDP
Core Core Core

8
Virtual Memory Support
 NDP threads access virtual address space
o Small TLB per core (32 entries)
o Large pages to minimize TLB misses (2 MB)
o Sufficient to cover local memory & remote buffers

 In PageRank
o Each core works on local data, much smaller than the entire dataset
o 0.25% miss rate for PageRank

 TLB misses served by OS in host

o Similar to IOMMU misses in conventional systems
9
Software-Assisted Coherence
 Maintaining general coherence is expensive in NDP systems
o Highly distributed, multiple stacks
Vault 0 Vault 1
 Analytics frameworks
o Little data sharing except for communication Vault Memory Vault Memory

o Data partitioning is coarse-grained Mem Ctrl Mem Ctrl

$ $ $ $
Memory vault
 Only allow data to be cached in one cache NDP NDP NDP identified
NDP by
Core Core CorephysicalCore
address
o Owner cache
o No need to check other caches Owner cache
identified by TLB
 Page-level coarse-grained
o Owner cache configurable through PTE
10
Software-Assisted Coherence
 Scalable Vault 0 Vault 1
o Avoids directory lookup and storage
Dataset
Vault Memory Vault Memory

Mem Ctrl
Adaptive
Mem Ctrl

$ $ $ $
o Data may overflow to other vault
o Able to cache data from any vault in local cache NDP
Core
NDP
Core
NDP
Core
NDP
Core

 Flush only when owner cache changes

o Rarely happen as dataset partitioning is fixed

11
Communication
 Pull-based model
o Producer buffers intermediate/result data locally and separately
o Post small message (address, size) to consumer
o Consumer pulls data when it needs with load instructions

Task Task Task Task

Cores Cores Cores Cores Process

Buffer

Pull
Task Task Task Task

12
Communication
 Pull-based model is efficient and scalable
o Sequential accesses to data
o Asynchronous and highly parallel
o Avoids the overheads of extra copies
o Eliminates host processor bottleneck

 In PageRank
o Used to communicate the update lists across partitions

13
Communication
 HW optimization: remote load buffer (RLBs)
o A small buffer per NDP core (a few cachelines)
o Prefetch and cache remote (sequential) load accesses
• Remote data are not cache-able in the local cache
• Do not want owner cache change as it results in cache flush

 Coherence guarantee with RLBs

o Remote stores bypass RLB
• All writes go to the owner cache
• Owner cache always has the most up-to-date data
o Flush RLBs at synchronization point
• … at which time new data are guaranteed to be visible to others
• Cheap as each iteration is long and RLB is small
14
Synchronization
 Remote atomic operations
o Fetch-and-add, compare-and-swap, etc.
o HW support at memory controllers [Ahn et al. HPCA’05]

 Higher-level synchronization primitives

o Build by remote atomic operations
o E.g., hierarchical, tree-style barrier implementation
• Core  vault  stack  global

 In PageRank
o Build barrier between iterations
15
Software Runtime
 Hide low-level coherence/communication features
o Expose simple set of API

 Data partitioning and program launch

o Optionally specify running core and owner cache close to dataset
o No need to be perfect, correctness is guaranteed by remote access

 Hybrid workloads
o Coarsely divide work between host and NDP by programmers
• Based on temporal locality and parallelism
o Guarantee no concurrent accesses from host and NDP cores
16
Evaluation
Three analytics framework: MapReduce, Graph, DNN
Methodology
 Infrastructure
o zsim
o McPAT + CACTI + Micron’s DRAM power calculator

 Calibrate with public HMC literatures

 Applications
o MapReduce: Hist, LinReg, grep
o Graph: PageRank, SSSP, ALS
o DNN: ConvNet, MLP, dA
Porting Frameworks
 MapReduce
o In map phase, input data streamed in
o Shuffle phase handled by pull-based communication
 Graph
o Edge-centric
o Pull remote update lists when gathering

 Deep Neural Networks

o Convolution/pooling layers handled similar to Graph
o Fully-connected layers use local combiner before communication
 Once the framework is ported, no changes to the user-level apps
19
Graph: Edge- vs. Vertex-Centric
Performance Energy
1.2 1.2
Normalized Performance

Normalized Energy
1 1
0.8 0.8
0.6 0.6
0.4 0.4
0.2 0.2
0 0
SSSP ALS SSSP ALS
Vertex-Centric Edge-Centric Vertex-Centric Edge-Centric

 2.9x performance and energy improvement

o Edge-centric version optimize for spatial locality
o Higher utilization for cachelines and DRAM rows
20
 Balance: PageRank
20
 Performance scales
Performance
Normalized

15
10
to 4-8 cores per vault
o Bandwidth saturates
5
0
Saturate after 8 cores
0 2 4 6 8 10 12 14 16
 Final design
100%
o 4 cores per vault
Bandwidth Utilization

80%
o 1.0 GHz
60%
o 2-threaded
40%
o Area constrained
20%
0%
0 2 4 6 8 10 12 14 16
Number of Cores per Vault
1.0GHz 1T 1.0GHz 2T 1.0GHz 4T 0.5GHz 1T 0.5GHz 2T 0.5GHz 4T
21
Scalability
Performance Scaling vs. # Stacks
16
Normalized Speedup

14
12
10
8
6
4
2
0
Hist PageRank ConvNet
1 stack 2 stacks 4 stacks 8 stacks 16 stacks

 Performance scales well up to 16 stacks (256 vaults, 1024 threads)

 Inter-stack links are not heavily used
22
Final Comparison
 Four systems
o Conv-DDR3
• Host processor + 4 DDR3 channels
o Conv-3D
• Host processor + 8 HMC stacks
o Base-NDP
• Host processor + 8 HMC stacks with NDP cores
• Communication coordinated by host
o NDP
• Similar to Base-NDP
• With our coherence and communication

23
 Final Comparison
Execution Time Energy
1.5 1.5

1 1

0.5 0.5

0 0

Conv-DDR3 Conv-3D Base-NDP NDP Conv-DDR3 Conv-3D Base-NDP NDP

 Conv-3D: improve 20% for Graph (bandwidth-bound), more energy

 Base-NDP: 3.5x faster and 3.4x less energy than Conv-DDR3
 NDP: up to 16x improvement than Conv-DDR3, 2.5x over Base-NDP24
 Hybrid Workloads
 Use both host processor and
Execution Time Breakdown NDP cores for processing
1.2
1
0.8
0.6
 NDP portion: similar speedup
0.4
0.2  Host portion: slight slowdown
0 o Due to coarse-grained address
interleaving
FisherScoring K-Core
Host Time NDP Time

25
Conclusion
 Lightweight hardware structures and software runtime
o Hides hardware details
o Scalable and adaptive software-assisted coherence model
o Efficient communication and synchronization
 Balanced and efficient hardware
 Up to 16x improvement over DDR3 baseline
o 2.5x improvement over previous NDP systems
 Software optimization
o 3x improvement from spatial locality

26
Thanks!
Questions?