【背景介紹】

 

排序作為一種核心操作，廣泛應(yīng)用于數(shù)據(jù)庫(kù)管理、人工智能（AI）推理、網(wǎng)頁搜索、科學(xué)計(jì)算等多個(gè)關(guān)鍵領(lǐng)域，成為現(xiàn)代計(jì)算中不可或缺的基礎(chǔ)性任務(wù)。然而，傳統(tǒng)的硬件排序系統(tǒng)大多依賴馮·諾依曼架構(gòu)，這種架構(gòu)在大規(guī)模數(shù)據(jù)處理時(shí)容易遭遇帶寬瓶頸，特別是在數(shù)據(jù)量急劇增加的情況下，存儲(chǔ)與計(jì)算單元之間頻繁的數(shù)據(jù)傳輸會(huì)極大限制系統(tǒng)的性能。

 

盡管現(xiàn)有的硬件排序方法，如 CPU、GPU 和 ASIC 等，通過提高并行性和計(jì)算能力有所改進(jìn)，但它們依然依賴于大量的比較操作和數(shù)據(jù)交換。這不僅增加了計(jì)算的復(fù)雜性，還使得系統(tǒng)在面對(duì)龐大數(shù)據(jù)集時(shí)性能逐漸飽和。因此，如何突破傳統(tǒng)計(jì)算架構(gòu)的限制，提升排序效率，成為了計(jì)算機(jī)體系結(jié)構(gòu)領(lǐng)域的重要方向。

 

為了解決這一問題，研究者們提出了基于憶阻器（Memristor）技術(shù)的創(chuàng)新方案——“存內(nèi)排序”技術(shù)（Sort-in-Memory, SIM）。這一技術(shù)通過將數(shù)據(jù)排序直接嵌入存儲(chǔ)器中，從而減少了傳統(tǒng)計(jì)算模型中不可避免的數(shù)據(jù)傳輸和比較操作，顯著提高了排序效率。憶阻器具有高密度、非易失性和低功耗的特點(diǎn)，使得在存儲(chǔ)器中完成排序成為可能。

 

北京大學(xué)楊玉超教授和陶耀宇研究員提出了一種創(chuàng)新的無比較排序系統(tǒng)——Memory-Sort-In-Memory（MSIM）。該系統(tǒng)采用憶阻器陣列作為核心組件，通過直接在內(nèi)存中執(zhí)行排序操作，消除了傳統(tǒng)排序系統(tǒng)中依賴比較單元的瓶頸。

 

為了進(jìn)一步優(yōu)化排序過程，MSIM 系統(tǒng)引入了 Tree Node Skipping（TNS）策略，該策略通過智能跳過冗余的樹節(jié)點(diǎn)遍歷，顯著減少了不必要的計(jì)算，提升了排序效率。與傳統(tǒng)的基于 CMOS 技術(shù)的排序系統(tǒng)相比，MSIM 在排序速度、能效和面積效率等方面均取得了顯著進(jìn)展，尤其在處理大規(guī)模數(shù)據(jù)時(shí)展現(xiàn)出更為出色的性能。

 

通過一系列驗(yàn)證，MSIM 系統(tǒng)在多個(gè)實(shí)際應(yīng)用場(chǎng)景中，如最短路徑搜索和神經(jīng)網(wǎng)絡(luò)推理等，表現(xiàn)出卓越的性能和顯著的節(jié)能優(yōu)勢(shì)。特別是在最短路徑問題的求解中，MSIM 系統(tǒng)通過減少排序操作的周期，極大地提升了計(jì)算效率；在神經(jīng)網(wǎng)絡(luò)推理中，MSIM 不僅加速了數(shù)據(jù)處理，還優(yōu)化了能效，證明了其在計(jì)算密集型任務(wù)中的巨大應(yīng)用潛力。

 

MSIM 系統(tǒng)為現(xiàn)代計(jì)算任務(wù)提供了一種具有高效性、低能耗和高擴(kuò)展性的解決方案。該文章以“A fast and reconfigurable sort-in-memory system based on memristors”為題發(fā)表在國(guó)際頂級(jí)期刊Nature Electronics上。

 

 

【圖文精讀】

圖1-排序系統(tǒng)概述：圖 1 展示了不同類型排序系統(tǒng)的全景比較，尤其強(qiáng)調(diào)了傳統(tǒng)的基于 CPU、GPU 和 ASIC 的排序架構(gòu)。這些系統(tǒng)依賴于馮·諾依曼架構(gòu)，其中計(jì)算單元和內(nèi)存單元之間的頻繁數(shù)據(jù)傳輸往往會(huì)引發(fā)帶寬瓶頸，導(dǎo)致在處理大規(guī)模數(shù)據(jù)時(shí)性能顯著下降。

 

為了解決這一問題，本文提出了基于憶阻器的 Sort-in-Memory（SIM）系統(tǒng)，這一創(chuàng)新架構(gòu)通過將排序任務(wù)直接集成至存儲(chǔ)器中，減少了數(shù)據(jù)傳輸?shù)念l率，從而顯著提升了系統(tǒng)性能。

 

特別地，本文所提出的 Memory-Sort-In-Memory（MSIM）系統(tǒng)通過消除傳統(tǒng)排序方法中的比較操作，避免了馮·諾依曼架構(gòu)中的固有瓶頸，優(yōu)化了排序效率，提升了能效和面積效率。這種無比較的排序方法不僅突破了傳統(tǒng)技術(shù)的限制，還為大數(shù)據(jù)處理提供了一種全新的思路。

 

要點(diǎn)總結(jié)：

• 傳統(tǒng)排序系統(tǒng)在大數(shù)據(jù)處理時(shí)因內(nèi)存帶寬和數(shù)據(jù)傳輸?shù)钠款i而性能受限。

• MSIM 系統(tǒng)通過存內(nèi)計(jì)算和無比較操作，消除了馮·諾依曼架構(gòu)的瓶頸，提升了排序效率，特別適用于大規(guī)模數(shù)據(jù)集。

 

 

圖2-憶阻器編程與 TNS：圖 2 詳細(xì)展示了憶阻器陣列在排序任務(wù)中的應(yīng)用，包含了憶阻器的 I-V 性能特性以及其在排序過程中的表現(xiàn)。通過比較傳統(tǒng)的位遍歷排序（BTS）與提出的樹節(jié)點(diǎn)搜索（TNS）方法，圖中揭示了 TNS 在排序效率上的顯著優(yōu)勢(shì)。

 

TNS 利用樹節(jié)點(diǎn)的逐步搜索和遍歷方式，從最重要位（MSB）到最不重要位（LSB）逐步查找最小值和最大值，而這一過程避免了傳統(tǒng)排序中常見的頻繁寫操作和冗余的讀操作，顯著降低了排序延遲。通過憶阻器編程的高密度存儲(chǔ)特性，TNS 在節(jié)省內(nèi)存空間的同時(shí)也提升了存儲(chǔ)效率，使得大數(shù)據(jù)排序變得更加高效。實(shí)驗(yàn)數(shù)據(jù)表明，TNS 方法在減少排序所需周期的同時(shí)，極大提升了能效和計(jì)算速度。

 

要點(diǎn)總結(jié)：

• 傳統(tǒng)排序方法如 BTS 存在操作復(fù)雜和周期冗長(zhǎng)的問題，而 TNS 通過樹節(jié)點(diǎn)遍歷優(yōu)化，顯著減少了冗余操作，提高了排序效率。

• TNS 利用憶阻器的編程特性，通過減少讀操作并提升存儲(chǔ)密度，實(shí)現(xiàn)了排序效率和能效的顯著提升。

 

圖3-CA-TNS 策略：圖 3 介紹了交叉陣列樹節(jié)點(diǎn)搜索（CA-TNS）策略，針對(duì)大規(guī)模數(shù)據(jù)集排序時(shí)的擴(kuò)展性問題，提出了數(shù)字并行（MB）、位并行（BS）和器件內(nèi)并行（ML）三種策略。每種策略通過不同的并行化方式對(duì)排序任務(wù)進(jìn)行優(yōu)化，從而提升處理效率。

 

數(shù)字并行策略通過將數(shù)據(jù)集劃分為多個(gè)部分，使每個(gè)部分獨(dú)立進(jìn)行排序，從而提高了并行處理的能力并減小了排序延遲。位并行策略將數(shù)據(jù)按位進(jìn)行切分，在多個(gè)子陣列中并行處理，從而加速了排序過程，特別適用于需要高精度排序的場(chǎng)景。器件內(nèi)并行策略則通過在設(shè)備內(nèi)部進(jìn)行更深層次的并行處理，進(jìn)一步提升了排序速度和存儲(chǔ)效率。CA-TNS 策略的引入不僅有效應(yīng)對(duì)了大規(guī)模數(shù)據(jù)排序的挑戰(zhàn)，還通過高度的并行化顯著提高了計(jì)算和存儲(chǔ)的效率。

 

要點(diǎn)總結(jié)：

• CA-TNS 策略（MB、BS、ML）通過多層次并行化顯著提升了大數(shù)據(jù)集排序的效率，解決了排序擴(kuò)展性問題。

• 每種策略通過不同方式優(yōu)化存儲(chǔ)與處理過程，提升了數(shù)據(jù)處理速度，并有效減少了排序所需的時(shí)間和能耗。

 

圖4-CA-TNS 策略性能評(píng)估：圖 4 對(duì) CA-TNS 策略在五個(gè)排序基準(zhǔn)數(shù)據(jù)集上的性能進(jìn)行了綜合評(píng)估，分別從排序速度、能效和面積效率等多個(gè)維度對(duì)比了不同策略的表現(xiàn)。數(shù)字并行（MB）策略通過將數(shù)據(jù)集分配至多個(gè)部分，提升了大數(shù)據(jù)集的處理速度，同時(shí)降低了排序延遲；位級(jí)并行（BS）策略通過位級(jí)并行處理加速了排序過程，尤其在處理精度要求較高的數(shù)據(jù)時(shí)表現(xiàn)尤為突出；器件內(nèi)并行（ML）策略則通過更高的存儲(chǔ)密度和內(nèi)部并行計(jì)算，進(jìn)一步優(yōu)化了排序的整體性能。

 

實(shí)驗(yàn)結(jié)果表明，相較于傳統(tǒng)的 ASIC 排序方法，CA-TNS 策略在各項(xiàng)性能指標(biāo)上均表現(xiàn)優(yōu)異，尤其在大規(guī)模數(shù)據(jù)排序中展示了更強(qiáng)的優(yōu)勢(shì)，能夠在較短的時(shí)間內(nèi)完成復(fù)雜的排序任務(wù)，同時(shí)顯著減少能耗和占用空間。

 

要點(diǎn)總結(jié)：

• CA-TNS 策略（MB、BS、ML）顯著提高了排序速度，優(yōu)化了能效和面積效率，在所有評(píng)估維度上超越了傳統(tǒng)的 ASIC 排序方法。

• 各策略針對(duì)不同應(yīng)用場(chǎng)景優(yōu)化了并行處理和存儲(chǔ)，提升了數(shù)據(jù)處理的速度和能效，特別適用于大規(guī)模數(shù)據(jù)集的高效排序。

 

圖5-TNS 在最短路徑搜索中的實(shí)驗(yàn)：圖 5 通過實(shí)驗(yàn)展示了 TNS 在 Dijkstra 算法中的應(yīng)用，具體使用了北京 16 個(gè)地鐵站的圖模型進(jìn)行最短路徑搜索。圖中展示了如何使用 TNS 對(duì)各個(gè)站點(diǎn)之間的距離進(jìn)行排序，以便在計(jì)算最短路徑時(shí)加速數(shù)據(jù)處理。

 

實(shí)驗(yàn)結(jié)果表明，TNS 在排序過程中大大減少了操作周期，相比于傳統(tǒng)的排序技術(shù)，不僅提高了計(jì)算速度，而且顯著優(yōu)化了能效。在最短路徑搜索等圖計(jì)算任務(wù)中，TNS 展現(xiàn)了其在實(shí)時(shí)性和計(jì)算效率方面的巨大優(yōu)勢(shì)，特別是在處理大規(guī)模圖數(shù)據(jù)時(shí)，能夠有效減少計(jì)算時(shí)間和能量消耗。

 

要點(diǎn)總結(jié)：

• TNS 在最短路徑搜索中通過減少排序操作顯著提升了計(jì)算效率，優(yōu)化了路徑計(jì)算的實(shí)時(shí)性。

• 在吞吐量和能效方面，TNS 超越了其他排序技術(shù)，尤其適合實(shí)時(shí)圖計(jì)算任務(wù)和大規(guī)模數(shù)據(jù)處理。

 

 

圖6-PointNet++中的原位剪枝：圖 6 探討了原位剪枝（In-Situ Pruning）在神經(jīng)網(wǎng)絡(luò)推理中的應(yīng)用，特別是對(duì)于 PointNet++ 網(wǎng)絡(luò)。傳統(tǒng)的剪枝方法通常在訓(xùn)練階段進(jìn)行固定的剪枝，而原位剪枝則允許在推理過程中動(dòng)態(tài)調(diào)整剪枝率，從而實(shí)現(xiàn)更高效的計(jì)算。

 

圖中展示了正常剪枝、外部剪枝和原位剪枝在不同剪枝率下對(duì)推理準(zhǔn)確度、吞吐量和能效的影響。實(shí)驗(yàn)結(jié)果表明，原位剪枝能夠在較低的計(jì)算成本下保持較高的準(zhǔn)確性，同時(shí)顯著提高能效和吞吐量。此外，通過結(jié)合多級(jí)存儲(chǔ)單元（MLC），原位剪枝進(jìn)一步優(yōu)化了存儲(chǔ)密度和計(jì)算速度，在保持較高準(zhǔn)確度的同時(shí)降低了能量消耗和計(jì)算復(fù)雜度。

 

要點(diǎn)總結(jié)：

• 原位剪枝在推理過程中動(dòng)態(tài)調(diào)整剪枝率，能夠在不顯著犧牲準(zhǔn)確性的前提下，大幅提升推理效率、吞吐量和能效。

• 結(jié)合多級(jí)存儲(chǔ)單元（MLC）后，原位剪枝不僅提高了存儲(chǔ)密度，還有效降低了推理過程中的能耗和計(jì)算負(fù)擔(dān)。

 

【文獻(xiàn)總結(jié)】

本文提出了一種創(chuàng)新的基于憶阻器的硬件與軟件協(xié)同設(shè)計(jì)的存內(nèi)排序系統(tǒng)（SIM）。該系統(tǒng)由 TaOx 和 HfO2 智能憶阻器陣列芯片、外圍電路和 FPGA組成，旨在消除傳統(tǒng)排序方法中的比較單元及其數(shù)據(jù)傳輸瓶頸。

 

為實(shí)現(xiàn)無比較排序，本文開發(fā)了樹節(jié)點(diǎn)跳躍（TNS）策略，并針對(duì)特殊情況（如重復(fù)數(shù)字和數(shù)據(jù)集中的最后一個(gè)數(shù)字）進(jìn)行了優(yōu)化。此外，本文還將基本 TNS 擴(kuò)展為交叉陣列 TNS（CA-TNS）策略，包括數(shù)字并行處理（MB）， 位級(jí)并行處理（BS），器件并行處理（ML）三種策略，以提升數(shù)字級(jí)、器件內(nèi)并行性和存儲(chǔ)密度。

 

實(shí)驗(yàn)結(jié)果表明，與基于 CPU/GPU 或 ASIC 的傳統(tǒng)排序系統(tǒng)相比，MSIM 系統(tǒng)在排序速度、能效和面積效率方面實(shí)現(xiàn)了顯著提升。該系統(tǒng)支持多種數(shù)據(jù)量、數(shù)據(jù)類型和精度，能夠靈活適應(yīng)不同應(yīng)用需求。通過將 MSIM 應(yīng)用于 Dijkstra 算法的最短路徑搜索和具有動(dòng)態(tài)稀疏性調(diào)節(jié)的神經(jīng)網(wǎng)絡(luò)（PointNet++）推理，驗(yàn)證了該系統(tǒng)在解決實(shí)際排序問題中的高效性，并證明了其與傳統(tǒng)存內(nèi)矩陣-向量乘法（MVM）技術(shù)的兼容性，為現(xiàn)代計(jì)算任務(wù)提供了強(qiáng)大的解決方案。

 

文章信息：Yu, L., Zhang, T., Wang, Z. et al. A fast and reconfigurable sort-in-memory system based on memristors. Nat. Electron. 8, 597–609 (2025). 

https://doi.org/10.1038/s41928-025-01405-2

---

*聲明：本文系原作者創(chuàng)作。文章內(nèi)容系其個(gè)人觀點(diǎn)，我方轉(zhuǎn)載僅為分享與討論，不代表我方贊成或認(rèn)同，如有異議，請(qǐng)聯(lián)系后臺(tái)。