vPIM: Efficient Virtual Address Translation for
Scalable Processing-in-Memory Architectures
Amel Fatima∗ , Sihang Liu† , Korakit Seemakhupt∗ , Rachata Ausavarungnirun‡ , and Samira Khan∗∗ University of Virginia† University of Waterloo‡ King Mongkut’s University of Technology North Bangkok

multi-level radix page table [25], which cannot benefit fromthe abundant memory parallelism in PIM. Even worse, thisscheme introduces slower cross-stack access.
Hash page table [8] is an alternative approach. Recent proposals [25] integrate an efficient collision resolution technique,cuckoo hashing [20], that enables sending parallel accesses
to the hash table, thus hiding the latency due to collisions.
Unfortunately, direct integration of the cuckoo hash page table
into PIM leads to parallel accesses toward different PIM
stacks, causing increased network contention.
The goal of this work is to redesign the address translation
scheme for scalable multi-stack PIM systems. We propose
V PIM, a virtual address translation scheme designed for multistack PIM systems that leverages the parallelism within each
PIM stack without incurring excessive cost due to cross-stackaccesses, by adopting two key ideas.
Network-contention-aware hash: In Cuckoo hashing, parallel hash functions map an address to random hash tablelocations. We can limit the number of cross-stack access in a
PTW if we map all indexes associated with a virtual address
to the same stack. Based on this key insight, we propose a
network-contention-aware scheme that hashes all the indexesof a virtual address to the same stack. This approach exploits
the abundant memory bandwidth within a stack and minimizes
cross-stack hash table accesses during a PTW.
Pre-translation: Besides memory parallelism, PIM also
has abundant parallel processors. PIM-friendly programs usually feature high parallelism—often manifest as independent
loops that parallelly execute on PIM processors. Thus, it ispossible to execute future parallel iterations ahead of timeto enable pre-translation. However, the limited vault area
does not permit extra logic. Past research has shown thattriggering memory accesses that lead to address translation
only requires a small fraction of instructions as compared tothe original procedure [11]. Thus, we propose to repurpose a
few PIM cores as pre-translation cores to trigger future addresstranslations, moving PTWs off the critical path.
We summarize the contributions as the following:• This work proposes V PIM, an efficient addresstranslation scheme for scalable, multi-stack PIM systems.
• V PIM minimizes cross-stack hash page table accesses byhashing all indexes associated with an address to the samestack, and mitigates translation time with pre-translation.
• To evaluate V PIM, we model a scalable, multi-stack PIM
system using ZSim [24] which shows a speedup of 4.4×
and 1.7× over radix and Cuckoo hash table schemes.

Abstract—3D-stacked memory technologies make it possible
to integrate computation logic into the memory stack to reduce
data movement between CPU and memory, enabling processingin-memory (PIM). PIM systems scale in capacity and bandwidthby connecting multiple PIM stacks through a memory network.
They also need to be programmable, where having virtual
memory support is critical. Existing address translation schemes,
however, are not optimized for a scalable PIM system. In thiswork, we propose V PIM, a virtual address translation scheme forscalable, multi-stack PIM systems. V PIM optimizes contention of
the memory network in a PIM system and reduces translation
time with pre-translation. Our evaluation shows a speedup of
4.4× and 1.7× compared to conventional radix and cuckoo hashpage tables in eight memory-intensive workloads.

I. I NTRODUCTION
Data-intensive applications spend significant time and energy in moving data between CPU and memory [2, 3]. The
3D-stacked memory technologies, such as High Bandwidth
Memory (HBM) [9], enable the integration of computation inside memory to reduce this data movement overhead. E.g., thelogic layer in memory vaults can have computation units [2,3]. This paradigm shift is called processing-in-memory (PIM).
A PIM system needs to be scalable, as a single memory
stack has limited capacity and bandwidth. For scalability,
multiple PIM stacks are connected over a memory network[3, 21]. We refer to accesses to other stacks as cross-stackaccesses, which have much longer memory access latency.
Another practical requirement for PIM systems is memory
management. A PIM system can either use a separate physicaladdress space [7, 17] or a unified virtual memory [16] between
the CPU and PIM cores. Maintaining a separate physical address space introduces programming difficulties due to explicit
data copying from/to the host processing. In comparison, a
unified virtual memory is easier to program, and therefore,architecting virtual memory is desirable [15].
Support for a unified virtual memory comes at the cost of
virtual-to-physical address translation. One approach is to forward the address translation from PIM to the CPU side [6, 19].
Such a scheme can introduce high communication overhead,overshadowing PIM’s benefit of reduced data movement. An
alternative approach is to add a Page Table Walker (PTWer)and a TLB near the PIM cores [6, 21]. This approach reduces
the communication overhead and, is the approach that wewill follow in this paper. However, the area constraint in PIM
does not allow for a large TLB to mitigate Page Table Walks(PTWs). In a conventional radix page table, a PTW requires
memory accesses in a pointer-chasing pattern to access the1

Host CPU

S0

S3

S8

S11

S1

S2

S9

S10

S4

S7

S12

S15

Vault 0Hash Table…

Vault Logic
Core 0Vault 31
Hash Table

Core 31➍

Cache TLB PTW➌

Vault Logic
Core 31➊➋

Vault Controller➌➍

Crossbar Switch
S5

S6

S13

S14
Link 0(a) Network of Stacks (Dragonﬂy)…

SwitchLink 3(b) PIM Stack with 1 Core/Vault

Vault

Fig. 1. Overview of PIM Stacks and the ArchitectureL4[38:30]L3[29:21]

T1[20:12]
PPN

L2

PPN

VA5

Lookup for: VA1

Lookup for: VA2❶PTW at S11 for

S0

VA2
VA4

…

S8

S11 TLB Miss #1➋PTW at S10 for

S1

S2

S9

S4

S7

S12 S15

S10

Fig. 2. Address Translation in (a) radix page table and (b) cuckoo hash table.

T1

h1 h2

T2

S11 VA1VA2 S14

S11 VA1VA2 S14

S10 VA5VA4 S5

S10 VA5VA4 S5❶ TLB Miss #1 for VA1…

S5
S6 S13 S14 PTW at S14 for
TLB Miss #2❶ PTW at S5 for
TLB Miss #1

h1 h2

T2

…

➋

TLB Miss #2

T1…

(b) Address Translation in Cuckoo Hash Table

S3…

(a) Address Translation in x86-64

L1

VA1

…

CR3

h1 h2

Hash tables (T1/T2) spanning multiple stacks. (S Stack #, VA Virtual Address)

T2

Host CPU[47:39]Fig. 3. Radix page table walk in a multi-stack PIM system.

Virtual Address (VA1)

Virtual Address (VA1)➋➊(c) Vault Logic➋ TLB Miss #2 for VA2

Fig. 4. Cuckoo hash lookup in PIM.

II. BACKGROUND AND M OTIVATION
A. Processing-in-Memory (PIM) Architecture

lookup operation for the virtual address VA1 in a 2-ary cuckoo
Execution
timeline here
hash table,consistingof two hash functions (h1 and h2) that
correspond to two tables (T1 and T2). Function h1 and h2
hash VA1 and generate two indexes that look up T1 and T2
in parallel, finally obtaining the target entry in T1.

Figure 1 shows the organization of the PIM system that isfollowed in the paper. It consists of 16 memory stacks connected over a memory network, following dragonfly topology[3, 21]. Each stack consists of 32 vertical DRAM partitions,called vaults, each with its vault controller and a low-profile
processor in the logic layer, enabling vaults to operate inparallel. Vaults are interconnected with a crossbar switch.

C. Rethinking Page Table Structure Design
While virtual memory is desirable in PIM systems, a followup question is what address translation mechanism a multistack PIM system should adopt. A radix PTW makes pointerchasing accesses across levels, and thus, cannot leverage thehigh memory bandwidth of PIM. On the other hand, thelimited area in a vault cannot fit a large TLB to mitigate PTWs.
Even worse, different levels of the page table access can spandifferent PIM stacks. For example, Figure 3 demonstrates a
TLB miss in stack S0 that leads to accesses to multiple stacks
when walking through L4–L1. Such cross-stack accesses canincrease access latency and contention in the memory network.
In comparison, hash tables eliminate pointer-chasing accesses.
Especially with Cuckoo hashing, the parallel accesses not
only mitigate hash collisions but also exploit the memory
parallelism in PIM systems. Unfortunately, direct integrationof Cuckoo hashing into a PIM system leads to performancedegradation due to slower cross-stack accesses. Therefore,
there is a need to redesign the page table in PIM systems.

B. Virtual Memory
Virtual memory aims to provide a view of a large memory
address space by translating virtual addresses to physicaladdresses available in the system during each memory access.
To enable virtual memory, the OS maintains page tables forthe address mapping at page granularity, and TLBs in the CPU
cache these mappings near the processor. Next, we will talkabout different page table schemes.
Radix Page Table is a commonly used approach [1] whichuses a radix tree to maintain the address mappings. Figure 2ademonstrates a 48-bit virtual address, wherein the 36 higherorder bits correspond to the virtual page number (VPN) andare divided into four 9-bit indexes; each index corresponds
to one level in the radix tree (i.e., L4—L1). A translation isreferred to as a page table walk (PTW), accessing four levelsin the radix tree to obtain the physical page number (PPN),
following a pointer-chasing memory access pattern.
Hash page table is an alternative design that uses a hashfunction to map VPNs to PPNs. Compared to the radix pagetable, the hash page table only takes one memory access.
However, it suffers from a major overhead of hash collisions
that can degrade its performance. Recent works [25] haveproposed a resurgence of this page table design by adopting
Cuckoo hashing [20] to mitigate hash collisions.
Cuckoo hashing [20] is a collision resolution algorithm
for hash page tables, that allows an element to have n hashlocations, i.e., n-ary. An entry can reside in one of theselocations, which are looked up in parallel. Figure 2b shows

III. H IGH -L EVEL I DEAS
Our goal is to enable efficient address translation in scalable,
multi-stacked PIM systems. In this section, we discuss thechallenges in integrating the Cuckoo hash page table into sucha PIM system and present our key ideas.
A. Memory Network Overheads
Figure 4 demonstrates PTWs in a 2-ary Cuckoo-hash-based
page table in PIM. Upon a TLB miss in stack S0 (step ⃝)1
for virtual address VA1, the hash functions h1 and h2 direct
to two potential locations of this entry that are held by stacks
S11 and S5, leading to two parallel accesses to these stacks.

2

These parallel lookups reduce the PTW latency compared to
the radix page table that performs serialized lookups.
Challenge: Parallel lookups in cuckoo hash tables canlead to contention in the network. We study the impact ofparallel page table lookups on cross-stack memory accesses.
We observe that the vault service time remains largely the samebut the network traversal time for a memory request increases
with more parallel accesses, as concurrently issued hash tablelookups contend with other memory accesses in the memory
network, leading to performance degradation.
Our Approach: Network-contention-aware hash: The
concurrent cross-stack PTWs are the primary source of theoverhead in a Cuckoo hash design. We observe that theplacement of hash table entries is determined by the hashfunctions. If the hash functions map the output indexes to thesame stack, there needs only one cross-stack access during thePTW, which can trigger multiple parallel page table accesses,
significantly reducing the number of cross-stack accesses.
Therefore, we propose a network-contention-aware hashing
scheme. Figure 5 shows a high-level view of our approach.
The core components of our approach are two types of hashfunctions: The stack hash function, hS (S stands for stack),
generates an index that directs to a stack where other hashtable lookup operations will be performed. The vault hashfunctions, hV’s (V stands for vault), generate the remaining
indexes to vaults within the same stack selected by hS (Details
of index generation in section IV-A2). Figure 6b demonstrates
the execution timeline in Figure 5. Figure 6a and 6b comparea naive Cuckoo hash table with our network-contention-aware
scheme and show that our approach significantly reduces the
network traversal time of memory requests.

VA0

VA2

VA4

VA4

S11

…

VA3

for TLB Miss #1

Host CPU

VA4

VA5❶ PTW at S11

S14

VA2

VA4

VA1
VA7

…

VA0

…

VA3

…

VA5

VA7

S11
S11

VA1

S14
S14

…

T1 hS hV1 T2…

T1 hS hV1 T2…

S14

Lookup for: VA2…

S11

Inside Stack 11 (total 32 vaults)
Lookup for: VA1

S0

S3

S8

S11

S1

S2

S9

S10

S4

S7

S12 S15S5

S6 S13 S14

Vault nHash Table

Vault Logic
Core 0Vault Logic
Core nCrossbar Switch
Link 0…

Link 3Inside Stack 14 (total 32 vaults)➋PTW at S14❶ TLB Miss #1 for VA1 ➋ TLB Miss #2 for VA2

Vault 0 …
Hash Tablefor TLB Miss #2

Vault 0 …
Hash Table

Vault nHash Table

Vault Logic
Core 0Vault Logic
Core nCrossbar Switch
Link 0…

Link 3Fig. 5. Page table based on the network-contention-aware Cuckoo hash.

S-5
S-11

V
V
V
V

Time

Cuckoo hashing lookup in PIM system

V
V

V
V

Lower network latency due
to less network contention

N
N

N
N

cycles saved❶TLB Miss
(b)

S-10

➋ TLB Miss

S14
S11

S-14

N

N
N

❶TLB Miss
(a)

N

Time

➋ TLB Miss

Lookup in PIM system with network-contention-aware hash

S14
Insert pre-translation
result to PB
PB S0 PB

V
V

N
N

More cycles saved
Time

❶
➋
❸ TLB Miss, PB MissTLB Miss,
TLB Miss, PB Hit
Write to PB Read from PB
Other main cores
Pre-translation core:
Main core 1://.. Other tasks…
x = array1[i];Pre-translation core:…
x = array[i];y = array2[j];TLB miss, PB hit
TLB miss, PB miss(c) Hashing lookup in PIM system with network-contention-aware hash & pre-translation

B. Cross-Stack PTW Overheads

V- Vault Service Time

Challenge: A system without PTW overhead is on average 1.4× faster than the system with our network-contentionaware hashing scheme, leaving optimization opportunities on
the table. Ideally, one would like to have TLB misses identified
ahead of time, to overlap PTWs with program execution.
Our Approach: Pre-translation: A PIM system has many
low-profile cores, which as a whole, provide massive parallelism. Thus, programs suitable for PIM offloading also featurehigh parallelism and manifest as independent loops that canbe assigned to different cores and executed in parallel [2].
Given such an execution pattern, it is possible to execute future
work (i.e., the next parallelizable iteration) ahead of time,making it possible to pre-translate cross-stack PTWs before
a future iteration happens. However, the area for processing
logic in memory stacks is limited, so the goal is to pretranslate without extra logic. We found that, on average, thework needed for a normal iteration is 4.22× compared to theminimum code required to trigger TLB misses. This implies
that a few cores dedicated to pre-translation work can assist
multiple main cores. We also measured the execution timewith the number of main cores reduced from 512 to 480,
only leading to a 6% degradation. Therefore, we propose touse a small fraction of PIM cores as pre-translation cores to

N- Network Traversal TimePB Pre-Translation Buﬀer

Fig. 6. An overview of pre-translation for cross-stack PTWs.

assist the main cores. Figure 6c shows a high-level view ofthe pre-translation scheme. The pre-translation cores executesimplified code of a future code section ahead of the progressof main cores. In step ⃝,1 the pre-translation core triggers
a TLB miss ahead of time and stores the translation result
to a pre-translation buffer (PB) which is located in the pretranslation core’s local vault as shown in Figure 8. In step⃝,
2 the main core, after encountering a TLB miss, access the
PB within the stack, to read the pre-translated result. Upon
another TLB miss in step ⃝,3 the main core misses in the PB
as the pre-translation result is not available and falls back to thenormal cross-stack PTW. We can get significant performance
benefit by only reducing a fraction of the cross-stack PTWs.
IV. M ECHANISM OF V PIM
In this section, we describe the mechanisms of V PIM anddemonstrate them with walk-through examples.
A. Network-Contention-Aware Hashing
We describe the page table allocation and the hashing
scheme that enable network-contention-aware hashing.

3

Inside Stack 0 (total 32 vaults)
Vault 0 …
Hash Table

Vault nHash Table

Vault Logic
Core 0Vault Logic
Core nCore nCache TLB PTW…

Link 0

Host CPU

S0

S3

S8

S11

S1

S2

S9

S10

S4

S7

S12 S15S5

S6 S13 S14❷ Hash VA1 with hS

Vault 0Hash TablehS
Vault Controller

Crossbar Switch❶ TLB miss #1
for VA1

Main Core
for(...){ // iteration u=X+1
if(parent[u]<0){
for(NodeID v:g.in_neigh(u)){...
if(front.get_bit(v)){
parent[u]=v;
Vault Logic
Vault Logic
Vault Logic❸Cross–Stack PTW
awake_count++;
Iteration u=X+1 ❹Lookup
next.set_bit(u);PPNCore 0Core 14
Core 29
break;}}}
1:15 Ratio}
Insert❷Pre-Translation Core
Vault 31 PB
Vault 30 PB
Pre-translated for(...){ // iteration u=X+1
PPN
Hash Table
Hash Tableif(parent[u]<0){
for(NodeID v:g.in_neigh(u)){
Vault Logic
Vault Logic
if(front.get_bit(v)){
Iteration u=X+1
parent[u]=v;Core 30
Core 31❶Cross-Stack PTW
break;}}}}
Iterations: u=X~Y mapped to a stack

VA1

Link 3

SwitchVault

Inside Stack 11 (total 32 vaults)
Vault 0 …
Hash Table

Vault nHash Table

Vault Logic
Core 0Vault Logic
Core nCrossbar Switch… Link 3❻Make parallel accesses
with both the indexes
Link 0❸ Locate the stackcorresponding to theindex. (e.g., Stack 11
in this case)Core nCache TLB PTW

Vault Controller
SwitchVault❺ Hash
VA1
with
hV1
hV1
❹Add
Base output
Index to base
-S11
index
VA1

Main Core

Vault 14
Hash Table

Vault 29
Hash Table

Pre-Translation CorePB

Pre-Translation Buﬀer PPN: Physical Page Number

Fig. 8. The pre-translation mechanism.

Fig. 7. Mechanism of the network contention-aware hashing scheme.
1 set_main_threads(480);
2 vPIM_PARALLEL_MAIN_THREADS {3
for(i=0;i<t;i++){4
int k;
5
float sum=0.0f;
6
int bound=h_nzcnt[i];7for(k=0;k<bound;k++){8
int j=h_ptr[k]+i;
9
int in=h_indices[j];10float d=h_data[j];11float t=h_x_vector[in];12
sum+=d*t;
13
}
14 }
15 }

1) Allocation of Hash Page Table in V PIM: In the baseline
cuckoo hash table, allocation of the hash page table is done,
irrespective of the memory stack. Therefore, a PTW may
access the hash tables located on different memory stacks,
leading to increased contention in the memory network. To
mitigate the performance interference caused by the crossstack PTWs, V PIM allocates an equal fraction of the hashpage table to every stack. Each fraction belonging to a specificstack has a fixed base index, Base Index (BI). This allocation
scheme enables directing all hash indexes of a virtual address
to the same stack. Next, we describe the hashing scheme.
2) Generation of Indexes: V PIM uses two types of hashfunctions. The first type is the stack hash function, hS, which
generates indexes ranging from the first to the last entry inthe hash table. It indicates the index to the first hash table(hS Index) and the target stack ID for remaining parallel
accesses. Specifically, hS takes the following steps:

16 set_pre_translation_threads(32);
17 vPIM_PRE_TRANSLATION_THREADS {18
for(i=1;i<t;i++){19
int k;
20
int bound=h_nzcnt[i];21for(k=0;k<bound;k++){22
int j=h_ptr[k];23
int in=h_indices[j];
24
}
25
}
26 }

Fig. 9. Code filtering for the pre-translation cores.

is first hashed by hS. Step ⃝:3 hS directs the translation tovault 0 of stack S11. Step ⃝:4 in stack 11, VA1 is further
hashed with the vault hash function hV1. Step ⃝:5 the value
generated from hV1 is added to the emphBase Index for stack
S11, and generates an index for the second page table in stack
S11 (located in vault n of stack S11 in this example). Step⃝:
6 the two hash indexes generated by hS and hV2 are thenaccessed in parallel within stack S11. One of them returns the
final translation result (the other one can be a collision).

hS Index = hS(VPN ) = Mask (SHA1 (VPN ), [0, n − 1]),

where n is the total number of entries andMask converts thehash value (from SHA-1 algorithm) to a range between 0 andn − 1. The stack ID is obtained from the mapping according
to the Base Indexes set during the page table allocation time.
The second type of hash function is the vault hash function,
hV. It generates an index to the same stack as hS but probably
different vaults inside that stack. In a Cuckoo hash schemewith two parallel hash tables, i.e., 2-ary, there is one vault
hash hV1 that indexes to the second hash table. With morehash tables, say n-ary, there will be n−1 value hash functions:hV1 ... hV(n-1), each corresponding to one hash table. Backto our assumed 2-ary system, hV1 takes the following steps:

B. Pre-translation
This mechanism repurposes a small number of cores for pretranslation in each stack, which runs ahead of the remaining
main cores within the stack. The pre-translation results are
stored in a pre-translation buffer (PB), which cache the virtualphysical address mappings and is located in the pre-translation
core’s vault as shown in Figure 8.
1) Programming Interface: Threads for the main
computation work are referred to as main threads andthose for pre-translation as pre-translation threads. Figure
9 demonstrates an example that uses the vPIM library
to define main threads and pre-translation threads.
First, functions set_main_threads (line 1) and
set_pre_translation_threads (line 16) define
the number of cores allocated to main threads andpre-translation threads, respectively. Code wrapped by
vPIM_PARALLEL_MAIN_THREADS is for main threads,
which are automatically generated from loops (line 3). Thisapproach is derived from the OpenMP wrapper [18]. The
V PIM library pins these main threads to the main cores
using Linux’s scheduler affinity interface. Likewise, code
wrapped by vPIM_PRE_TRANSLATION_THREADS is

hV1 Index =hV1 ((VPN )= Mask (SHA1 (VPN ), [0, (n/s) − 1]) + BI (StackID),

where n is the total number of hash entries and s is the numberof stacks. The final index from hV1 is the original hash value
converted to a range between 0 and (n/s)-1 using Mask , plus
the Base Index (BI ) associated with the selected stack ID.
3) Example: Figure 7 shows a step-by-step example todemonstrate our network-contention-aware hashing design.
Step ⃝:
1 execution in stack S0 encounters a TLB miss whenaccessing VA1. Step ⃝:2 in stack S0, the virtual address VA1

4

Non-Memory Intensive

N/A

rn
d

N/A

er

N/A

pr
.f

lb
m

N/A

wi
tt

r

N/A

pr
.t

ss

_s
cc

N/A

it
sp ter.
bf twit
s.f
te
r
ri
en
d
tc
s
t
.fr
er
ie
nd
cc
.fr ster
ie
cc
nd
_s
ste
v.
fr
r
ie
nd
ss
sp
s
te
.fr
ien r
ds
te
r
sp
m
v
sg
em
m
ste
nc
il
m
rigr
id
m
riq
hi
sto
tp
ac
f
cu
tc
p

tw

itt
e

N/A

v.

itt
er

.tw

.tw
cc

bf
s

.tw

itt
er

N/A

Fig. 10. Performance of vPIM over the baselines.

for pre-translation threads which are also generated fromloops. However, the V PIM library, assigns the loop iterations
to these threads in a way that each pre-translation thread
encounters the future iterations for all its associated mainthreads in a round-robin manner. We take an approach similar
to past works on helper threads for prefetching [11], tominimize our code. Instructions that access smaller data
structures (less likely to trigger TLB misses), non-memory
instructions, and instructions that change the memory state,
are all removed.
2) Coarse-Grained Synchronization between Main and
Pre-Translation Cores: Pre-translation cores assist a specific set of main cores within a stack. Thus, they haveto ensure that they remain ahead of those cores in order to trigger useful PTWs for future use. The parallelization wrappers, vPIM_PARALLEL_MAIN_THREADS,
and vPIM_PRE_TRANSLATION_THREADS take the loop
variable, e.g., i in Figure 9, to track the progress. Since thepre-translation core starts the execution an iteration ahead ofthe main cores, V PIM library checks if at least the distance(i.e., +1) is maintained between the main and pre-translation
threads after the completion of a set of iterations (This ensurescoarse-grained synchronization to minimize synchronization
overhead). If the checking fails, the V PIM library moves the
pre-translation thread ahead of the main threads, i.e., increment
the distance to be +1 of the main thread.
3) Walk-Through Example of Pre-Translation: Figure 8
shows a walk-through example of pre-translation. Step ⃝:1 pretranslation core in a stack executes iteration X+1 and triggers
a TLB miss, resulting in a PTW. Step ⃝:2 it performs the PTW
and buffers the translation in its pre-translation buffer (PB).
Step ⃝:
3 the main core starts iteration X+1 later and encounters
a TLB miss when accessing the same address. Step ⃝:4 themain core looks up the PB in the same stack before performing
a PTW, and hits PB. Thus, it no longer needs a PTW.

Slowdown Relative to Ideal
Address Translation

Cuckoo Hash Page TablevPIM: Network-Contention Aware Hash + Pre-Translation

Memory Intensive
1.0
0.8
0.6
0.4
0.2
0.0

tc

Slowdown Relative to Ideal
Address Translation

Radix Page TablevPIM: Network-Contention Aware Hash

Num Parallel Accesses:

2

4

8

1.0
0.8
0.6
0.4
0.2
0.0
vPIM

Baseline Cuckoo
Hash

Fig. 11. Performance with varying parallel
accesses to hash table.
TABLE IS IMULATED SYSTEM CONFIGURATION .
Processor
L1 Cache
I&D TLB
Page Table Walker

PIM Cores
512 in-order cores; 1/vault, 1-issue, 2GHz
16 kB I/D, 4-way, 64 B cache line, LRU
64 entries, LRU (per core)
1 (per core)

Number of Stacks
Capacity per Stack
Vaults per Stack
Maximum Bandwidth

Memory16
4 GB, 4 layers, 8 banks per vault
32, 32 TSV per vault
10GB/s per Vault, 120GB/s per Link

We compare the performance of four designs: (1) a conventional Radix page table, (2) a Cuckoo hash page table without
optimizations for PIM, (3) a Cuckoo hash with our networkcontention-aware hashing from V PIM (4) a Cuckoo hash with
network-contention-aware hashing and pre-translation fromV PIM. Baseline Cuckoo hash and V PIM use 2-ary hash tables.
B. Workloads
We evaluate the workloads from Gapbs [5] and Parboil [26]benchmark suites. The Gapbs workloads take two real-world
input graphs: Friendster [22] and Twitter [14]; the parboil
workloads take the largest dataset in the benchmark suite.
These workloads fall into two categories: memory-intensive
and non-memory-intensive. We follow the evaluation strategy
of prior works [23, 25], by performing evaluation of V PIM
on both categories and then performing sensitivity studies on
memory-intensive workloads only. The simulation starts froma warm-up stage, and then enters a region-of-interest of a totalof 500 M instructions that perform the core tasks on PIM.
VI. E VALUATION R ESULTS
A. Overall Performance and Performance Breakdown
Figure 10 compares the slowdown due to address translationof our design points over an ideal system without addresstranslation overhead. Overall, V PIM, with both networkcontention-aware hashing and pre-translation, has a speedup of
3.18× and 1.44× over the radix and Cuckoo hash page tables.
For memory-intensive workloads, the speedup is 4.4× and1.7×respectively. Pre-translation reduces the number of maincores and thus, only workloads consuming more than 20% of
execution time on address translation (through profiling) will
enable the pre-translation cores. Thus, non-memory intensive
workloads do not enable pre-translation (N/A in Figure 10).

V. E VALUATION M ETHODOLOGY
A. System Configuration and Design Points
We model our PIM cores in ZSim [24], memory system
in Ramulator, [13] and memory network in BookSim2 [10].
Table I lists our system configuration. In V PIM, the only
additional structure are the two PBs per stack (each has 1024
entries or 16kB), associated with the two pre-translation cores.

5Average

Slowdown Relative to
Ideal Address Translation

Slowdown Relative to
Ideal Address Translation

1.0
0.8
0.6
0.4
0.2
0.0

Pre-Translation
Cores : 2 4

TLB
5k
Entries: 15k
vPIM
1.0
0.8
0.6
0.4
0.2
0.0

VIII. C ONCLUSIONSWe propose V PIM that optimizes address translation in(PIM) systems by introducing a network-contention-aware
hashing scheme that efficiently integrates hash-table-based
address translation in PIM. Moreover, V PIM repurposes some
PIM cores for pre-translation to move page table walks off thecritical path of execution. Our evaluation, done using ZSim,
shows a speedup of 4.4× and 1.7× compared to the radix andcuckoo hash page table, in eight memory-intensive workloads.

10k
20k

AverageFig. 12. Performance with varied Fig. 13. Performance comparison
pre-translation cores per stack.
with in-memory TLB.

IX. ACKNOWLEDGEMENT
We thank the anonymous reviewers for their valuable feedback. This work is supported by the SRC/DARPA Center
for Research on Intelligent Storage and Processing-in-memory(CRISP), National Science Foundation (NSF), and Thailand
MHESI Research Grant for New Scholars (RGNS 64-091).

Figure 10 further shows the speedup from each optimization in V PIM. We observe in Figure 10 that the networkcontention-aware hashing outperforms both baselines and theperformance trend from pre-translation falls into three categories. (1) Workloads with significant performance improvement, e.g., spmv, sgemm, and bfs, where pre-translation cores
run fast enough to pre-translate a large number of iterations
for the main cores. (2) Workloads with limited margin to
improve, e.g., tc, cc sv, and stencil, that already achieve closeto-ideal performance, with network-contention-aware hashing.
(3) Workloads with limited improvement, e.g., cc and sssp, thathave limited room to be simplified for pre-translation cores,
resulting in long execution time for pre-translation.

R EFERENCES[1] R. Agarwal et al., “The intel 80386 architecture and implementation,”
IEEE Micro, 1985.
[2] J. Ahn et al., “PIM-Enabled Instructions: A low-overhead, locality-aware
processing-in-memory architecture,” in ISCA, 2015.
[3] ——, “A scalable processing-in-memory accelerator for parallel graphprocessing,” in ISCA, 2015.
[4] T. W. Barr et al., “Spectlb: A mechanism for speculative addresstranslation,” SIGARCH Comput. Archit. News, 2011.
[5] S. Beamer et al., “The GAP benchmark suite,” arXiv, 2015.
[6] M. Gao et al., “Practical near-data processing for in-memory analytics
frameworks,” in PACT, 2015.
[7] P. Gu et al., “ipim: Programmable in-memory image processing accelerator using near-bank architecture,” in ISCA, 2020, pp. 804–817.
[8] J. Huck et al., “Architectural support for translation table management
in large address space machines,” in ISCA, 1993.
[9] JEDEC, “High Bandwidth Memory (HBM) DRAM,” Standard No.
JESD235, 2013.
[10] N. Jiang et al., “A detailed and flexible cycle-accurate network-on-chipsimulator,” ISPASS, pp. 86–96, 2013.
[11] M. Kamruzzaman et al., “Inter-core prefetching for multicore processors
using migrating helper threads,” in ASPLOS, 2011.
[12] G. Kandiraju et al., “Going the distance for TLB prefetching: An
application-driven study,” in ISCA, 2002, pp. 195–206.
[13] Y. Kim et al., “Ramulator: A fast and extensible dram simulator,” CAL,
2016.
[14] H. Kwak et al., “What is Twitter, a social network or a news media?”in WWW, 2010.
[15] J. Lowe-Power et al., “Supporting x86-64 address translation for 100sof GPU lanes,” in HPCA, 2014.
[16] Z. S. H. Michael J. K. Nielsen, “Unified memory computer architecturewith dynamic graphics memory allocation,” U.S. Patent 6,104,417, Aug.
15 2000.
[17] T. Nowatzki et al., “Stream-dataflow acceleration,” in ISCA, 2017.
[18] OpenMP, “The OpenMP API specification for parallel programming,”
https://www.openmp.org/, 2022.
[19] M. Oskin et al., “Active pages: A computation model for intelligent
memory,” in ISCA, 1998.
[20] R. Pagh et al., “Cuckoo hashing,” Journal of Algorithms, 2004.
[21] J. Picorel et al., “Near-memory address translation,” in PACT, 2017.
[22] R. A. Rossi et al., “The network data repository with interactive
graph analytics and visualization,” in AAAI, 2015. [Online]. Available:
https://networkrepository.com[23] J. H. Ryoo et al., “Rethinking tlb designs in virtualized environments:
A very large part-of-memory tlb,” in ISCA, 2017.
[24] D. Sanchez et al., “ZSim: Fast and accurate microarchitectural simulation of thousand-core systems,” in ISCA, 2013.
[25] D. Skarlatos et al., “Elastic cuckoo page tables: Rethinking virtual
memory translation for parallelism,” in ASPLOS, 2020.
[26] J. Stratton et al., “Parboil: A revised benchmark suite for scientificand commercial throughput computing,” Center for Reliable and HighPerformance Computing, 2012.

B. Sensitivity Study-Parallel Access and Pre-Translation Core
Figure 11 shows that more parallel accesses degrade performance in the Cuckoo hash page table, due to increased network
contention. In comparison, because of the contention awareness, V PIM does not have major performance degradation
with more parallel hash table accesses. Figure 12 shows theaverage performance with varying numbers of pre-translation
cores per stack. The benefit is a result of a trade-off between
the address translation overhead and the reduced performancedue to fewer cores for the workload. For our workloads, we
see the best performance with two pre-translation cores.
C. Comparison with in-Memory TLB
Figure 13 compares V PIM with an in-memory TLB [23] (5k to 20 k entries). We observe that V PIM performs significantly better since memory-intensive workloads do not have agood locality and incur frequent TLB misses. In-memory TLB
design aims to reduce the TLB miss rate, which is orthogonal
to V PIM’s goal of reducing the TLB miss penalty. Thus, thetwo designs can work collaboratively for better performance.
VII. R ELATED W ORK
To reduce the overhead of address translation, prior works
have proposed to optimize the TLB organizations by prefetching [12], large part-of-memory TLB [23], and speculative
TLBs [4]. However, as PIM systems have a limited area forcomputation logic, these complicated hardware designs do not
apply. Thus, this work takes an approach that reduces the TLB
miss penalty. There have also been proposals on hash pagetables [25] that reduce the PTW latency. However, they aredesigned for conventional, CPU-centric systems whereas thiswork targets scalable, multi-stack PIM systems.

6