晨光
暗夜
晨光
极光
Bilingual Paper Reading · 中英对照精读

MultPIM：面向存内计算的快速有状态乘法

准大一 · 集成电路设计与集成系统 × 存内计算 × 忆阻器 —— 存内乘法精读材料
原文：arXiv:2108.13378 2021年8月30日发布 arXiv 预印本（cs.AR） 存内计算 × 忆阻器 × 乘法加速 附英文摘要朗读音频

一、论文档案

英文标题MultPIM: Fast Stateful Multiplication for Processing-in-Memory
中文标题MultPIM：面向存内计算（PIM）的快速有状态乘法
作者奥里安·莱特斯多夫, 罗尼·罗南, 沙哈尔·克瓦廷斯基（以色列理工学院 以色列理工学院 电气与计算机工程系）
发布时间2021年8月30日（v1）｜分类：cs.AR（硬件架构）
原文链接arxiv.org/abs/2108.13378　·　全文 HTML 版
一句话概括让「存数据的忆阻器阵列」顺便把乘法也算完——用进位保存加移位（CSAS）把乘法时间复杂度从 O(N²) 降到 O(N log N)，32 位乘法比当时最先进的 RIME 再快 4.2 倍。
💡 为什么选这篇给你：① 存内计算（PIM）是破解「冯·诺依曼瓶颈」的主流路线之一，也是后摩尔时代芯片架构的必考点；② 它把乘法这个最基础的运算做进「存储阵列」里，涉及数字电路（全加器）、算法（CSAS、Wallace 树）与架构（分区并行）三层知识，一鱼三吃；③ 数字漂亮（4.2×、25.5×、33%），结论可复现，非常适合入门「AI+芯片架构」交叉方向。

二、核心术语表（先扫一遍再读正文）

英文术语中文大白话解释
von Neumann architecture冯·诺依曼架构计算与存储分离的经典计算机结构；CPU 算、内存存，来回搬数据。
memory wall存储墙CPU 越来越快、内存带宽跟不上，数据搬运成为系统瓶颈的现象。
Processing-in-Memory (PIM)存内计算让存储器件顺便做逻辑/运算，消除「计算-存储」之间的数据搬运。
memristor忆阻器电阻值可变的二端器件，电阻高低代表 0/1，还能用电压改写——存储+逻辑二合一。
LRS / HRS低阻态 / 高阻态忆阻器存储二进制的两种状态：低阻（如 1）与高阻（如 0）。
crossbar array交叉阵列忆阻器排成的「横线×竖线」网格，每个交叉点一个器件，高密度存储结构。
stateful logic有状态逻辑直接在存储器件里完成的门操作（结果也存成电阻状态），如 IMPLY、MAGIC、FELIX。
memristive partition忆阻分区用晶体管把交叉阵列动态划分成多个独立区块，可并行计算。
full-adder全加器数字电路基础单元：把两个输入位和低位进位相加，输出和位与进位位。
carry-save add-shift (CSAS)进位保存加移位乘法算法：每步只做「进位保存加法」再移位，避免长进位链，延迟更低。
Wallace tree华莱士树经典并行乘法结构：用树形全加器把部分积压缩相加。
O(N²) / O(N log N)时间复杂度随位数 N 增长，耗时按 N² 还是 N·logN 增长——后者大幅更快。
matrix-vector multiplication矩阵-向量乘神经网络、图像处理的核心运算；在存内计算里逐行并行执行。
cycle-accurate simulator周期精确模拟器逐时钟周期模拟硬件行为的仿真器，用来验证算法正确性。

三、摘要中英对照（精读核心）

🎧 音频在文末，可先听一遍原文再读；每个英文句都配了逐句翻译。

摘要 Abstract

EN · 原文
Processing-in-memory (PIM) seeks to eliminate computation/memory data transfer using devices that support both storage and logic.
CN · 翻译
存内计算（PIM）旨在用「既支持存储又支持逻辑」的器件，消除计算与存储器之间的数据搬运。
EN · 原文
Stateful logic techniques such as IMPLY, MAGIC and FELIX can perform logic gates within memristive crossbar arrays with massive parallelism.
CN · 翻译
IMPLY、MAGIC、FELIX 等有状态逻辑技术可以在忆阻交叉阵列内以大规模并行方式完成逻辑门操作。
EN · 原文
Multiplication via stateful logic is an active field of research due to the wide implications.
CN · 翻译
由于影响广泛，基于有状态逻辑的乘法是一个活跃的研究方向。
EN · 原文
Recently, RIME has become the state-of-the-art algorithm for stateful single-row multiplication by using memristive partitions, reducing the latency of the previous state-of-the-art by 5.1x.
CN · 翻译
最近，RIME 凭借忆阻分区成为有状态单行乘法的先进算法，把此前最优算法的延迟降低了 5.1 倍。
EN · 原文
In this paper, we begin by proposing novel partition-based computation techniques for broadcasting and shifting data.
CN · 翻译
本文首先提出用于广播与移位数据的新型基于分区的计算技术。
EN · 原文
Then, we design an in-memory multiplication algorithm based on the carry-save add-shift (CSAS) technique.
CN · 翻译
然后，我们设计了基于进位保存加移位（CSAS）技术的存内乘法算法。
EN · 原文
Finally, we develop a novel stateful full-adder that significantly improves the state-of-the-art (FELIX) design.
CN · 翻译
最后，我们开发了一种新型有状态全加器，显著改进了当时最先进的（FELIX）设计。
EN · 原文
These contributions constitute MultPIM, a multiplier that reduces state-of-the-art time complexity from quadratic to linear-log.
CN · 翻译
这些贡献构成 MultPIM——一个把最先进乘法器时间复杂度从「二次」降到「线性对数」的乘法器。
EN · 原文
For 32-bit numbers, MultPIM improves latency by an additional 4.2x over RIME, while even slightly reducing area overhead.
CN · 翻译
对 32 位数字，MultPIM 比 RIME 再降低 4.2 倍延迟，同时还略微减少了面积开销。
EN · 原文
Furthermore, we optimize MultPIM for full-precision matrix-vector multiplication and improve latency by 25.5x over FloatPIM matrix-vector multiplication.
CN · 翻译
此外，我们把 MultPIM 优化用于全精度矩阵-向量乘法，与 FloatPIM 的矩阵-向量乘法相比延迟改善 25.5 倍。

关键词 Keywords：Processing-in-Memory 存内计算 ｜ Stateful Logic 有状态逻辑 ｜ Memristor 忆阻器 ｜ Multiplication 乘法 ｜ Carry-Save Add-Shift 进位保存加移位

四、引言精选（为什么这个问题重要）

① 动机：冯·诺依曼瓶颈与存内计算的答案

EN · 原文
The von Neumann architecture separates computation and memory in computing systems. Each has significantly improved in recent years, leading to the data-transfer between them becoming a bottleneck (memory wall [1]). Processing-in-Memory (PIM) aims to nearly eliminate this data-transfer by using devices that support both storage and logic.
CN · 翻译
冯·诺依曼架构把计算与存储分开。近年来两者各自飞速进步，导致它们之间的数据搬运成了瓶颈（存储墙）。存内计算（PIM）的目标，就是用「存储+逻辑二合一」的器件几乎消除这种搬运。

② 基础：忆阻器、交叉阵列与有状态逻辑

EN · 原文
Processing-in-memory can be implemented using memristors [2], two-terminal devices with variable resistance. Their resistance may represent binary data by being set to either low-resistive state (LRS) or high-resistive state (HRS). A high-density memory can be built using a memristor crossbar array structure [3]. Uniquely, the resistance of a memristor can be controlled via an applied voltage, enabling stateful logic to be performed within the crossbar array. Examples of stateful logic techniques include IMPLY [10], MAGIC [11] and FELIX [12], which can also be performed in parallel along rows/columns. Hence, single-row computation algorithms are advantageous as they can be repeated along all rows with the exact same latency. Additional parallelism can arise from memristive partitions [12] which dynamically divide the crossbar array using transistors.
CN · 翻译
存内计算可用忆阻器实现——一种电阻可变的二端器件，其电阻设为低阻态（LRS）或高阻态（HRS）即可表示二进制数据；忆阻交叉阵列可构成高密度存储器。独特之处在于：忆阻器的电阻可被施加的电压控制，从而在阵列内部完成有状态逻辑（如 IMPLY、MAGIC、FELIX），且可沿行/列并行。因此「单行计算」算法有优势：同一延迟可复制到所有行；而忆阻分区（用晶体管动态划分阵列）还能带来额外并行。

③ 前作：从单行乘法到 RIME（5.1× 提速，瓶颈在 81% 的串行部分）

EN · 原文
Multiplication is fundamental for many applications, e.g., convolution and matrix-multiplication. The first in-row multiplication algorithm was proposed by Haj-Ali et al. [19], and was later utilized in IMAGING [20] for image processing and in FloatPIM [21] for deep neural networks. This algorithm requires O(N2) latency and O(N) memristors, where N is the width of each number. Recently, RIME [22] improved the latency by 5.1× for N=32 via memristive partitions [12], while slightly reducing area (i.e. memristor count) as well. The asymptotic latency/area remains at O(N2) and O(N) (respectively). RIME is based on Wallace tree computation using N−1 partitions in a single row, each partition representing a full-adder unit. The bottleneck of RIME is the partial product computation and data-transfer between partitions (as they occur serially), accounting for 81% of the latency.
CN · 翻译
乘法是卷积、矩阵乘等众多应用的基础。首个「行内乘法」算法由 Haj-Ali 等人提出，后被 IMAGING（图像处理）和 FloatPIM（深度神经网络）采用；该算法需要 O(N²) 延迟、O(N) 个忆阻器（N 为数字位宽）。近期 RIME 借助忆阻分区，对 N=32 把延迟改进了 5.1 倍，同时略微减少面积；但渐近复杂度仍是 O(N²) 延迟、O(N) 面积。RIME 基于 Wallace 树，单行内用 N−1 个分区，每区是一个全加器单元；其瓶颈是部分积计算与分区间的数据搬运（串行进行），占延迟的 81%。

④ 本文三招：分区广播/移位 + CSAS + 新全加器

EN · 原文
In this paper, we speedup multiplication using three methods. First, we propose novel partition-based computation techniques for broadcasting/shifting data amongst partitions. Second, we replace the Wallace tree with a carry-save-add-shift (CSAS) multiplier [23, 24, 25]. Lastly, we propose a novel full-adder design that significantly improves the previous state-of-the-art (FELIX [12]). The final algorithm, coined MultPIM, achieves an asymptotic latency of O(N log N) with O(N) area. For N=32, MultPIM achieves a 4.2× improvement in latency over RIME (that is, 21.1× over Haj-Ali et al.) while maintaining constant partition count and even slightly reducing area. This paper contributes the following:
CN · 翻译
本文用三招加速乘法：① 提出分区间广播/移位数据的新型计算技术；② 用进位保存加移位（CSAS）乘法器替换 Wallace 树；③ 提出显著改进 FELIX 的新型全加器。最终算法 MultPIM 达到 O(N log N) 渐近延迟、O(N) 面积；对 N=32，延迟比 RIME 改善 4.2 倍（即比 Haj-Ali 等人改善 21.1 倍），且分区数不变、面积还略微减小。
💡 这是全文最有味道的一句："The bottleneck of RIME is the partial product computation and data-transfer between partitions (as they occur serially), accounting for 81% of the latency."——做架构优化前先量化瓶颈：81% 的延迟来自串行的部分积与搬运，所以本文的每个改进都精准打在瓶颈上。

五、论文贡献（4 个要点）

EN · 原文
1. Partition Techniques. Introduces novel techniques for broadcasting/shifting data amongst partitions.
CN · 翻译
1. 分区技术。提出在分区之间广播/移位数据的新技术，把 RIME 最大的串行瓶颈并行化。
EN · 原文
2. Full Adder. Proposes a full-adder design that improves the previous state-of-the-art (FELIX) by up to 33%.
CN · 翻译
2. 全加器。提出新的全加器设计，比此前最先进的 FELIX 全加器最多改善 33%。
EN · 原文
3. MultPIM. Proposal of an efficient parallel multiplier that replaces quadratic time complexity with linear-log. We show latency improvement of 4.2× and slight area reduction over the previous state-of-the-art (RIME).
CN · 翻译
3. MultPIM 乘法器。提出高效的并行乘法器，把二次时间复杂度换成线性对数；相对 RIME 延迟改善 4.2 倍、面积略微减小。
EN · 原文
4. Matrix-vector multiplication. We present an optimized implementation of MultPIM in matrix-vector multiplication that improves latency by 25.5× over FloatPIM.
CN · 翻译
4. 矩阵-向量乘法。给出 MultPIM 在矩阵-向量乘法中的优化实现，相对 FloatPIM 延迟改善 25.5 倍。

六、结论中英对照

EN · 原文
We present MultPIM: a novel partition-based in-memory multiplication algorithm that improves the state-of-the-art latency complexity from quadratic to linear-log, specifically by 4.2× for 32-bit. The improvement is based on the carry-save add-shift technique, two novel memristive-partition computation techniques, and an improvement to the state-of-the-art full-adder.
CN · 翻译
我们提出 MultPIM——一种基于分区的新型存内乘法算法，把最先进的延迟复杂度从「二次」改善到「线性对数」，32 位时具体改善 4.2 倍。改进基于三件事：进位保存加移位技术、两项新型忆阻分区计算技术，以及对最先进全加器的改进。
EN · 原文
Furthermore, we optimize MultPIM for matrix-vector multiplication and achieve 25.5× latency and 1.8× area improvements over FloatPIM matrix-vector multiplication by computing addition while performing multiplication. Correctness is verified via a cycle-accurate simulator.
CN · 翻译
此外，我们优化 MultPIM 用于矩阵-向量乘法——通过「乘法过程中顺带完成加法」，相对 FloatPIM 实现了 25.5 倍延迟改善和 1.8 倍面积改善。正确性通过周期精确模拟器验证。

七、编者解读：这篇论文到底讲了什么（大白话版）

  1. 问题：CPU 和内存之间搬数据太慢（存储墙）。存内计算的思路是让「存数据的忆阻器阵列」顺便把逻辑运算也干了。但想在阵列里做乘法很难：以前最好的算法 RIME 虽然快，延迟复杂度还是 O(N²)——位数翻倍，耗时翻四倍，而且 81% 的时间浪费在串行的部分积和分区搬运上。
  2. 做法：三管齐下——① 发明分区间的广播/移位技术，让数据在分区之间高效流动；② 把 Wallace 树换成「进位保存加移位（CSAS）」结构，避免长长的进位链；③ 设计更省时的有状态全加器。合起来就是 MultPIM。
  3. 结果：时间复杂度从 O(N²) 降到 O(N log N)——位数翻倍，耗时只翻一倍多一点；32 位乘法比 RIME 快 4.2 倍（比更早的 Haj-Ali 方法快 21.1 倍），面积还略微减小；矩阵-向量乘法比 FloatPIM 快 25.5 倍、面积省 1.8 倍。
  4. 最值钱的观点：优化之前先量化瓶颈——「81% 的延迟在串行部分」这句话决定了整个方案的方向。算法复杂度（O 记号）和电路设计（全加器）在存内计算里是一体的，两头都要懂。
  5. 工程意义：乘法是卷积、矩阵乘、神经网络推理的基石。MultPIM 让「在内存里直接算」变得又快又省，是存内计算芯片走向实用（如 AI 推理加速）的关键一步。
🎯 对保研的启示：这篇论文展示了「系统优化」的完整套路：找瓶颈（81%）→ 选对算法（CSAS）→ 电路级配合（全加器）→ 用模拟器验证。复试时能说出「为什么 O(N²)→O(N log N) 重要、瓶颈在哪、怎么验证」，比背结论高级得多。

八、给准大一的阅读路线图 & 延伸方向

📖 怎么读这篇论文（三遍法）

  1. 第一遍（10 分钟）：只读摘要和术语表，回答三个问题——问题是什么？方法是什么？结果是什么？（4.2×、25.5×、O(N log N) 要记住）
  2. 第二遍（20 分钟）：读引言 + 结论，重点体会「存储墙」为什么是问题、RIME 的 81% 瓶颈从哪来。
  3. 第三遍（30 分钟）：把引言里 4 段中英对照反复读，跳过所有引用编号 [1][2]…和公式细节，只读文字；遇到不懂的术语回查术语表。

🚀 这个方向你能延伸做什么

九、英文摘要朗读（练听力用）

先盲听一遍→再看对照稿→再听一遍。目标是听出每个数字（5.1x、4.2x、25.5x、32-bit）和术语（stateful logic、memristive crossbar、carry-save add-shift）。