IEEE Solid-State Circuits Magazine - Spring 2016 - 60

computation model, with cores having asymmetric views of memory.
A core on a memory device has a
high-bandwidth link (A) to its local
memory and a low bandwidth link
(C) to nonlocal memory. A core on
the processor socket has a collection of low-bandwidth links (B) to
an aggregation of memory devices.
In terms of bandwidth, A > B > C.
If a computation can localize its
memory accesses to data in a single
memory device, the computation is
best placed on that memory device
so it can exploit the high bandwidth
of A. If a computation has limited
locality, it must determine if it is
better to off-load to the memory
device and exploit a combination of
A and C or remain on the processor
socket and exploit B.
This is clearly a simplistic view
because it does not consider detailed
network topologies nor the quality of the
cores/caches on the processor/memory
devices. But at a high level, it conveys
the key point that a computation with
localized memory accesses is an ideal
candidate for near-data execution.
A second key component in this
analysis is parallelism. Each additional memory device adds more
memory and compute resources. If
a computation can be parallelized
across the many cores in memory
devices, it is an even better candidate for near-data execution.
There are a few other considerations in the off-load decision.
■ Is one of the cores or one of the
cache hierarchies especially beneficial for the computation at hand?
■ What is the cost of spawning a
task (passing code and arguments
to the memory device)?
■ What is the cost of terminating a
task (returning results to the processor socket)?
■ What is the length of the off-loaded function?
It is nontrivial to factor in these issues
to develop an automatic hardware/software off-load policy. It is, therefore,
an active area of research. We briefly
describe two examples here that represent opposite ends of the spectrum.

S P R I N G 2 0 16

The work of Ahn et al. [2] attempts
fine-granularity off-loads with PIMenabled instructions (PEIs). Individual
instructions can be executed either
on the host processor or on the memory device (with a locality monitor
that helps in this decision making).
Consider the example where a single
scalar value is being added to some
word that is not currently cache resident. Without PEIs, an entire 64-B
cache line is brought to the processor, an update is performed, and the
entire 64-B cache line is sent back
to memory. With PEIs, the 8-B scalar
value is sent to the memory device
(with appropriate control bits) so the
update can be performed directly in
the memory device.
In this particular example, PEIs
yield a 16× decrease in bandwidth
requirement, the length of the offloaded function is one, and the cost
of task spawning and termination is
actually lower with PEIs than without PEIs. Ahn et al. also extend the
instruction set architecture (ISA) so
that nontrivial functionalities can
be off-loaded to memory devices.
Meanwhile, work from our group
[28] focuses on in-memory MapReduce applications that exhibit a very
high degree of locality and task-level
parallelism. Each map and reduce
task is executed on a memory device
that contains that data partition,
dubbed near data computing (NDC).
Task setup and teardown are nontrivial efforts, especially if data shuffling is required. But that overhead is
palatable because each task executes
for many thousands of cycles. The
task latency itself is highly sensitive
to memory bandwidth. The primary
source of speedup is the high bandwidth within a collection of memory
devices, which is far greater than the
bandwidth into the processor socket.
The PEI approach can yield a nearly
1.5× average speedup for a range of
memory-intensive workloads that do
not exhibit cache line reuse, while the
NDC approach can yield up to 15×
speedup for a specific class of memoryintensive workloads that have high
coarse-grained parallelism. This also

IEEE SOLID-STATE CIRCUITS MAGAZINE

provides insight on the data access patterns of workloads that benefit from
NDP. In-memory MapReduce (e.g., in
SPARK [46]) is a killer app that exhibits
localized memory access and embarrassing levels of coarse-grained parallelism [28]. In-memory MapReduce
frameworks have been shown to be
useful for a wide range of applications:
database operations, analytics, machine
learning, and graph algorithms [46].
The PEI work shows benefits for
a number of graph workloads where
data traversal is random enough that
caches are ineffective, and small computations within each graph vertex
can be off-loaded to memory. They
also extend the ISA to perform hash
table probing, histogram bin indexing,
and dot products over cache lines to
accelerate data mining and machine
learning applications. Other papers
have also shown NDP benefits for
other applications, e.g., graph processing [1], scientific kernels that map to
coarse-grained reconfigurable accelerators (CGRAs) [10], scientific workloads [21], signal processing [15], and
join algorithms [20].

How Should Data Be Organized
Across Memory Devices?
A natural next issue is the interleaving and addressing of data across
several memory devices. Unlike conventional double-data rate (DDR)
memory that stripes a single cache
line across multiple DRAM packages,
an entire cache line or even an entire
page in NDP must now be localized to
a single memory package. This allows
the core/accelerator on the memory
package to perform fine- and coarsegrained computation without engaging in complex bit-level manipulations
and without aggregating inputs from
many sources. This already appears to
be the default data mapping in emerging memory devices like the hybrid
memory cube (HMC) [18]. However,
when the same data is accessed by a
host processor socket, it may lead to
longer transfer times.
It is also important to resolve how
a memory device may potentially
access data in a different memory

Table of Contents for the Digital Edition of IEEE Solid-State Circuits Magazine - Spring 2016