Affinity-based Optimizations for TFHE on Processing-in-DRAM

Fully homomorphic encryption lets a computer compute on data it can never read, but it is so slow that it needs hardware acceleration, and processing-in-memory — putting compute units right inside the memory chips — is a natural fit because these encrypted workloads move enormous amounts of data; this work from Seoul National University finds that prior accelerators, by spreading the work across memory units purely for parallelism, force those units to constantly reach into each other's memory, which is slow on this hardware, so it reorganizes the encryption math and schedules the work by data affinity to keep each unit working on its own local data, running real workloads 4 to 200 times faster than prior accelerators.

The argument in one glance

Problem

Computing on encrypted data is slow, and PIM has a hidden catch

TFHE lets a computer compute on encrypted data without decrypting it — great for privacy, but very slow, so it needs acceleration. Processing-in-memory (PIM), with compute units inside the DRAM, suits these data-heavy workloads, but each unit can only cheaply reach its own local memory.
What people did

Maximize parallelism across the in-memory units

Existing TFHE accelerators spread the computation across as many compute units as possible, treating more parallelism as the path to speed, as it is on GPUs and custom chips.
Why it fell short

Scattering the data forces slow remote accesses

Spreading work for parallelism scatters the data each unit needs, so the units constantly reach into one another's memory — remote data accesses that travel over the slow shared paths PIM was meant to avoid. These pile up and dominate, so parallelism-first design actually degrades performance on PIM.
This paper's idea

Optimize TFHE for data affinity, then schedule it (this work)

This work reorganizes the TFHE algorithms so PIM can use its high internal bandwidth, analyzes the affinity patterns in TFHE's sub-tasks, and builds an offline scheduler that minimizes remote data accesses while keeping enough parallelism. On a real FPGA-based PIM system with a minimally-modified PIM-HBM device, it outperforms prior TFHE accelerators by 4.24 to 209 times.

Why this problem is worth solving

Computing on encrypted data is one of the most powerful ideas in privacy, and one of the most expensive, which is why hardware acceleration is essential.

Fully homomorphic encryption (FHE) lets a computer perform arbitrary computation directly on encrypted data and produce an encrypted result, without ever decrypting it or seeing the underlying values — so a cloud could run your analysis on data it can never read. TFHE, Fully Homomorphic Encryption over the Torus, is a leading FHE scheme, known for efficiently evaluating Boolean gates and lookup tables on encrypted bits and for fast bootstrapping, the operation that refreshes an encrypted value’s accumulated noise so computation can continue indefinitely. The power of FHE is immense for privacy-preserving computation, but so is its cost: ciphertexts are far larger than the plaintext they hide, and each operation involves heavy polynomial arithmetic, so running a real program under FHE can be orders of magnitude slower than running it in the clear. That gap is why FHE is not yet ubiquitous and why a great deal of research goes into accelerating it with specialized hardware — GPUs, custom chips, and now processing-in-memory. The workload is not just compute-heavy; it is data-heavy, shuffling large ciphertexts and polynomials, which shapes what kind of accelerator suits it.

Processing-in-memory looks like an ideal match for this data-heavy workload, but it comes with a constraint that changes what “fast” means.

Processing-in-memory (PIM) places small compute units directly inside the memory — for instance in the banks of a high-bandwidth memory (HBM) stack — so that computation happens where the data already lives, instead of hauling data across the narrow external memory bus to a distant processor. The payoff is enormous internal bandwidth: many units, each reading its own local memory in parallel, collectively move far more data per second than any external bus could. This is exactly what a data-heavy workload like TFHE wants. But PIM has a hard constraint that defines its performance: a compute unit can cheaply and quickly access only the data in its own local memory partition. When a unit needs data that lives in another unit’s partition, that is a remote data access, and it is slow, because the data must travel over the shared, limited paths between units — precisely the kind of movement PIM was built to avoid. So on PIM, where each piece of data sits relative to the unit that needs it — its data affinity — matters more than almost anything else, and an algorithm that ignores affinity can drown in remote accesses even while it keeps every unit busy.

What people did before, and where it broke

Accelerate TFHE on GPUs and custom chips by maximizing parallelism. Spread the heavy polynomial work across as many compute lanes as possible. Where it broke. These architectures have relatively uniform, fast access to shared memory, so a parallelism-first design that ignores where data lives works there but does not transfer to PIM.
Port that parallelism-first approach to PIM. Run TFHE on in-memory units the same way, distributing work widely for maximum concurrency. Where it broke. Distributing work scatters the data each unit needs across partitions, so units constantly make remote data accesses, which are slow on PIM and pile up until they dominate the runtime.
Rely on PIM’s raw internal bandwidth to carry the workload. Assume that because PIM has high internal bandwidth, a data-heavy application will run fast on it. Where it broke. Internal bandwidth only helps for local accesses; a workload full of remote accesses cannot use it, so the promised bandwidth is squandered.
Ignore data affinity in TFHE’s structure. Treat TFHE’s sub-tasks as generic parallel work without analyzing which data they share. Where it broke. Without understanding the affinity patterns, there is no way to place and schedule data to keep accesses local, so remote traffic is unavoidable.
The gap. No approach reorganized TFHE and scheduled it to respect data affinity on PIM, so none could actually exploit PIM’s bandwidth for TFHE. Providing that is what this work does.

How the affinity-based approach works

From parallelism-first TFHE to affinity-optimized TFHE on PIM

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

On PIM, keep the data a unit needs where that unit can reach it. The central realization, per the abstract, is that PIM inverts the usual optimization target: the scarce resource is not compute parallelism but local data access, because a unit that has to fetch its inputs from another unit’s partition pays the slow remote-access cost that PIM exists to avoid. So the work co-optimizes the computation and the data placement for affinity, arranging TFHE so that the data each in-memory unit needs is resident in that unit’s own partition, and only accepting parallelism that does not force remote accesses. Co-optimizing where data sits against how work is distributed, so that each near-memory processor computes on data it owns rather than fetching from neighbors, is the same move the near-data-processing work covered elsewhere on this site makes, jointly balancing data placement and load across the processing elements so the memory-local design actually pays off instead of collapsing into remote traffic.

Rewrite the encryption’s math to fit the hardware, not just run it. Making TFHE affinity-friendly is not only a scheduling problem; the abstract notes algorithmic optimizations to TFHE itself, restructuring how its heavy polynomial computations are organized so they map cleanly onto PIM’s partitioned memory and let the units draw on their high internal bandwidth. Rather than take the standard TFHE algorithm as fixed and try to place it, the work reshapes the algorithm so that placement can succeed. Reworking the mathematics of an encrypted computation so it lines up with what the target accelerator does well, instead of forcing an unchanged algorithm onto mismatched hardware, is the same discipline the encrypted-arithmetic compilation work covered elsewhere on this site follows, transforming how a homomorphic computation is expressed so that it fits the execution substrate and runs efficiently rather than fighting it.

Precompute the schedule because the structure is known. TFHE’s computation has a regular, predictable structure — the same kinds of sub-tasks with the same data-sharing patterns recur — so the affinity analysis and the choice of how to place and order the work can be done once, ahead of time, by an offline scheduler, rather than decided expensively at runtime. That scheduler searches for a placement that minimizes remote data accesses while preserving enough parallelism to keep the units productive, turning a hard runtime tradeoff into a solved, baked-in plan. Exploiting the fixed, analyzable structure of a data-heavy workload to precompute an optimal execution plan offline, sparing the runtime that cost, is the same design the processing-in-memory acceleration work covered elsewhere on this site is built on, planning the mapping of a regular high-bandwidth workload onto the memory-resident processors in advance so execution simply follows the plan.

Following a TFHE workload through the affinity-based system

Accelerating an encrypted computation on a PIM-HBM device

A conceptual trace based on the paper's abstract and standard TFHE and PIM background; specific algorithmic and scheduler details were not available.

Step 1 of 5

A privacy-preserving app runs under TFHE

An application computes on encrypted data with TFHE — evaluating gates and bootstrapping to keep the ciphertexts usable — a workload that is both compute-heavy and, crucially, data-heavy, shuffling large ciphertexts and polynomials.

This is why a high-internal-bandwidth accelerator is attractive.

Why it works

Remote accesses, not compute, are the PIM bottleneck. Because a PIM unit reaches its own partition fast but another unit’s slowly → minimizing remote data accesses attacks the actual limiter → so optimizing for affinity beats optimizing for raw parallelism on this hardware.
Local accesses are what turn bandwidth into speed. Because PIM’s high internal bandwidth only applies to local memory → keeping each unit’s data in its own partition lets that bandwidth be used → so an affinity-aware layout finally exploits the advantage PIM was built for.
Reshaping the algorithm makes good placement possible. Because the stock TFHE algorithm may scatter data by its structure → reorganizing its polynomial computations lets data be co-located per unit → so the scheduler has an affinity-friendly problem to solve rather than an impossible one.
Known structure enables offline optimization. Because TFHE’s sub-tasks and data-sharing patterns are regular and predictable → an offline scheduler can precompute a placement minimizing remote accesses → so the costly tradeoff is resolved once, not repeatedly at runtime.
Balancing affinity and parallelism avoids the opposite trap. Because pure affinity could serialize work while pure parallelism causes remote traffic → the scheduler keeps enough parallelism while minimizing remote accesses → so the units stay busy without drowning in remote data movement.

What it costs (trade-offs and scope)

This explainer is based on the abstract, not the full paper. The full text was not openly available at the time of writing, so the specific algorithmic transformations to TFHE, the affinity-analysis method, the offline scheduler’s algorithm, the hardware modifications, and the detailed per-benchmark results are not reflected here beyond what the abstract states.
It requires modifying a PIM device, if minimally. The approach targets a variant of an existing PIM-HBM device with minimal hardware changes; it is not a pure-software optimization for unmodified commodity PIM, and its practicality depends on those modifications being as small as claimed.
Offline scheduling assumes a known, stable workload structure. Precomputing the schedule works because TFHE’s computation is regular; workloads whose structure varies at runtime, or TFHE usages that deviate from the analyzed patterns, would fit the offline approach less cleanly.
The speedups span a very wide range. The reported 4.24 to 209 times improvement over prior TFHE accelerators is a broad range, reflecting that different benchmarks have very different amounts of remote-access overhead to remove; the low end is a modest gain and the high end an outlier, so the typical benefit lies in between.
It is specific to TFHE on PIM. The affinity insight is general in spirit, but the concrete optimizations target TFHE’s structure on a PIM-HBM substrate; other FHE schemes, or other accelerators, would need their own affinity analysis and algorithm reshaping.
The comparison baseline matters. Outperforming prior TFHE accelerators by these factors is relative to those specific systems and benchmarks; the absolute performance, and how it compares to the best non-PIM accelerators, is part of the full evaluation not available here.

The evaluation

Accelerating TFHE: parallelism-first versus affinity-based on PIM

Property	GPU/custom-chip acceleration	Parallelism-first on PIM
Primary optimization target
Remote data accesses
Uses PIM internal bandwidth	Not applicable
TFHE algorithm	Standard	Standard
Reported speedup vs prior TFHE accelerators	Baseline class

Accelerating TFHE, as framed by the paper's abstract (the full paper was not openly available, so this reflects the abstract's claims and standard background rather than the paper's detailed evaluation). Fully homomorphic encryption over the torus is intensive and needs acceleration; processing-in-memory suits its data-heavy nature via high internal bandwidth. But prior TFHE accelerators, designed for GPUs and custom chips with fast shared memory, maximize compute parallelism and ignore data affinity. Ported to PIM, that scatters the data each in-memory unit needs, so units make excessive remote data accesses over the slow shared paths PIM was meant to avoid, and these dominate the runtime — squandering the internal bandwidth. This work takes an affinity-based approach: it applies algorithmic optimizations to TFHE so PIM can leverage its high internal bandwidth, analyzes the affinity patterns in TFHE's sub-tasks (which data is used together), and builds an offline scheduler that finds a placement and schedule minimizing remote data accesses while maintaining sufficient parallelism. It targets a variant of an existing PIM-HBM device with minimal hardware modifications and is evaluated on a real FPGA-based PIM system, where the affinity-based optimizations outperform prior TFHE accelerators by 4.24 to 209 times on real-world benchmarks.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract, because the full text was not openly accessible when it was written, so read it as a faithful account of the abstract’s claims plus standard, well-established background on fully homomorphic encryption, TFHE, processing-in-memory, and data affinity — not as a report of the paper’s detailed algorithms or measurements. With that caveat, the contribution is clear and well-motivated. Computing on encrypted data with TFHE is a compelling privacy technology that is far too slow without acceleration, and processing-in-memory is an appealing accelerator because the workload is data-heavy and PIM offers high internal bandwidth by computing inside the memory. The paper’s key insight is that PIM changes the rules: its performance is governed not by how much compute parallelism you extract but by how often a compute unit must reach into another unit’s memory — a slow remote data access — so prior TFHE accelerators, tuned for parallelism on GPUs and custom chips, actually degrade on PIM because their scattered data causes remote accesses to dominate. The response is an affinity-based co-design: reorganize the TFHE algorithm so it maps onto PIM’s partitioned memory, analyze which data TFHE’s sub-tasks use together, and use an offline scheduler to place and order the work so remote accesses are minimized while enough parallelism remains, on a PIM-HBM device needing only minimal changes and demonstrated on a real FPGA-based PIM system. The reported gains over prior TFHE accelerators are large, 4.24 to 209 times, though that wide range signals the benefit varies a lot by benchmark. What is not available here is exactly how TFHE is transformed, how affinity is analyzed and scheduled, what hardware changes are required, and how the results break down — the specifics needed to judge and reproduce it. The durable idea, clear even from the abstract, is that moving a workload onto processing-in-memory is not about extracting more parallelism but about respecting data locality: on hardware where reaching a neighbor’s memory is expensive, the winning strategy is to reshape the computation so each processor works on data it already holds.

Background

Why data locality dominates on processing-in-memory

It helps to see this work within a recurring lesson about processing-in-memory and near-data architectures: their promise is enormous bandwidth from computing where data lives, but that promise is realized only when the data a processor needs is actually local to it, so data placement and locality, rather than raw parallelism, become the decisive optimization. The batched-transformer PIM work covered elsewhere on this site reflects the same theme from the machine-learning side, unleashing PIM’s bandwidth for a memory-bound workload by carefully organizing the computation and data so the in-memory units are fed from their own partitions rather than stalling on remote traffic. The common thread is that PIM inverts the usual accelerator intuition: on a GPU you chase parallelism because memory is relatively uniform, but on PIM a unit’s fast path is only its local memory, so an algorithm that scatters data to parallelize can be slower than one that keeps data local even at some cost in parallelism. As FHE and other data-heavy, privacy- and bandwidth-critical workloads are pushed onto PIM to escape the memory wall, the pattern this paper exemplifies — analyze a workload’s data affinity, reshape the algorithm to make locality achievable, and schedule to minimize remote accesses — is likely to be the standard route to making each of them pay off.

If you remember only three things

1. Fully Homomorphic Encryption over the Torus (TFHE) lets a computer compute directly on encrypted data without decrypting it — powerful for privacy but extremely slow, so it needs hardware acceleration. Processing-in-memory (PIM), which places compute units inside the DRAM (for instance in an HBM stack), suits TFHE because the workload is data-heavy and PIM offers very high internal bandwidth by computing where the data lives. But PIM has a defining constraint: a compute unit can cheaply access only its own local memory partition, and reaching another unit's data is a remote data access that is slow because it travels over the shared paths PIM was built to avoid. Prior TFHE accelerators, designed for GPUs and custom chips with fast shared memory, maximize compute parallelism and ignore data affinity; ported to PIM, that scatters the data each unit needs, so remote data accesses pile up and dominate the runtime, degrading performance and squandering the internal bandwidth that made PIM attractive.
2. This work, according to its abstract, takes an affinity-based approach that co-optimizes the TFHE computation and its data placement for PIM. It applies algorithmic optimizations to TFHE so its heavy polynomial computations map onto PIM's partitioned memory and let the in-memory units use their high internal, local bandwidth. It analyzes the affinity patterns in TFHE's sub-tasks — which pieces of data are used together — to determine what should be co-located in each unit's partition. And because TFHE's computation has a regular, predictable structure, it uses an offline scheduler that precomputes a placement and schedule minimizing remote data accesses while keeping enough parallelism to keep the units busy, resolving the affinity-versus-parallelism tradeoff once, ahead of time. The approach targets a variant of an existing PIM-HBM device requiring only minimal hardware modifications.
3. Demonstrated on a real FPGA-based PIM system, the affinity-based optimizations outperform prior TFHE accelerators by 4.24 to 209 times on real-world benchmarks. Important caveat: this explainer is based on the abstract because the full paper was not openly available, so the specific TFHE transformations, affinity-analysis and scheduling methods, hardware changes, and detailed results are not reflected here, and the wide speedup range signals that the benefit varies substantially by benchmark. The durable idea, clear even from the abstract, is that processing-in-memory inverts the usual accelerator intuition: performance is governed by data locality rather than raw parallelism, because reaching a neighbor's memory is expensive, so the winning strategy is to reshape the computation and schedule the work so each in-memory processor operates on data it already holds — minimizing remote accesses rather than maximizing concurrency.

Check yourself

Check your understanding

1. Why is processing-in-memory (PIM) an appealing accelerator for TFHE, and what is its defining constraint?
2. Why did prior TFHE accelerators, designed for maximum parallelism, perform poorly when run on PIM?
3. What are the components of the paper's affinity-based approach, according to its abstract?
4. What did the work report achieving, and what should you keep in mind about the evidence?

Sources

The paper is “Affinity-based Optimizations for TFHE on Processing-in-DRAM” by Kevin Nam, Heon Hui Jung, Hyunyoung Oh, and Yunheung Paek, published at ASPLOS 2025, DOI 10.1145/3676641.3716246. The authors are at Seoul National University and Gachon University.

This explainer is based on the paper’s abstract (Creative Commons Attribution / CC-BY, as indicated by the publisher’s open-access metadata). The full text was not openly accessible at the time of writing — the ACM Digital Library copy was gated behind a bot check, there was no arXiv or author preprint available (the Seoul National University research pages did not expose a downloadable PDF), and the Semantic Scholar, OpenAlex, and Unpaywall records pointed only to the gated version — so this page reflects the abstract’s stated claims (that processing-in-memory suits intensive workloads via high internal bandwidth; that TFHE, Fully Homomorphic Encryption over the Torus, is a promising but intensive application; that existing TFHE accelerators focus on parallelism and overlook data affinity, causing performance degradation on PIM due to excessive remote data accesses; that the work applies algorithmic optimizations to TFHE to leverage PIM’s high internal bandwidth, analyzes the affinity patterns in TFHE’s sub-tasks, and develops an offline scheduler that minimizes remote data accesses while maintaining sufficient parallelism; that it designs a variant of an existing PIM-HBM device with minimal hardware modifications and evaluates on a real FPGA-based PIM system; and that it outperforms prior TFHE accelerators by 4.24 to 209 times on real-world benchmarks) together with standard, well-established background on fully homomorphic encryption, TFHE, processing-in-memory, high-bandwidth memory, data affinity, and remote data accesses, provided to make the abstract’s contribution understandable. The specific algorithmic transformations, affinity-analysis and scheduling methods, hardware modifications, and detailed measurements are not reflected here beyond what the abstract states; the flow and step-through sections are conceptual readings of the abstract plus standard background rather than details drawn from the full paper. This page is marked as a draft for that reason and should be confirmed against the full paper when it becomes available.