排序作為最基礎(chǔ)、最常用的計(jì)算范式之一，廣泛應(yīng)用于人工智能、搜索引擎、路徑規(guī)劃、數(shù)據(jù)庫(kù)等眾多關(guān)鍵任務(wù)中。由于排序本質(zhì)上的高度非線(xiàn)性，傳統(tǒng)硬件通常依賴(lài)復(fù)雜的比較器網(wǎng)絡(luò)和頻繁的主存訪(fǎng)問(wèn)，在大數(shù)據(jù)時(shí)代愈發(fā)受限于帶寬、能效、面積瓶頸。近年來(lái)，存算一體技術(shù)被寄予厚望，尤其是基于憶阻器的存算一體架構(gòu)，因其高密度、多電導(dǎo)態(tài)和高能效等突出優(yōu)勢(shì)，已成為突破傳統(tǒng)“存算分離”架構(gòu)瓶頸最具潛力的方向之一。然而，排序等非線(xiàn)性計(jì)算因其高度依賴(lài)復(fù)雜比較器網(wǎng)絡(luò)，一直被視為存算一體領(lǐng)域最難攻克的挑戰(zhàn)之一。

圖1: 憶阻器存算一體排序系統(tǒng)整體示意圖

在這一背景下，北京大學(xué)集成電路學(xué)院楊玉超教授、人工智能研究院陶耀宇研究員團(tuán)隊(duì)在國(guó)際上首次實(shí)現(xiàn)了面向高復(fù)雜度排序任務(wù)的存算一體化硬件系統(tǒng)，提出了一個(gè)全新的、無(wú)需比較器的排序硬件架構(gòu)，成功打破了存算一體技術(shù)難以處理排序等非線(xiàn)性計(jì)算的限制，標(biāo)志著該領(lǐng)域?qū)崿F(xiàn)從線(xiàn)性矩陣計(jì)算向非線(xiàn)性復(fù)雜任務(wù)的突破。相關(guān)研究成果以題為《A fast and reconfigurable sort-in-memory system based on memristors》的論文，近日發(fā)表在國(guó)際頂級(jí)期刊《自然?電子》（Nature Electronics）上。

在這項(xiàng)工作中，研究團(tuán)隊(duì)首次構(gòu)建了一個(gè)基于1T1R憶阻器陣列、無(wú)需比較器的存算一體排序軟硬件一體系統(tǒng)。該工作創(chuàng)新的提出了憶阻器陣列位讀?。―igit Read）機(jī)制，通過(guò)并行讀取從高位至低位逐步定位當(dāng)前最小或最大值，配合存算一體電路，徹底顛覆了傳統(tǒng)基于比較-選擇的排序架構(gòu)與流程。在此基礎(chǔ)上，研究團(tuán)隊(duì)進(jìn)一步提出了樹(shù)節(jié)點(diǎn)跳躍（Tree Node Skipping, TNS）排序算法及其硬件架構(gòu)，利用遍歷路徑與信息復(fù)用，顯著減少了冗余操作，大幅提升了存算一體化排序效率。為應(yīng)對(duì)更加復(fù)雜的實(shí)際排序應(yīng)用場(chǎng)景，該工作還設(shè)計(jì)了三種跨陣列的擴(kuò)展策略（Cross-array TNS, CA-TNS），分別面向不同并行維度：多陣列（Multi-Bank）策略支持大量數(shù)據(jù)按數(shù)分陣列進(jìn)行并行處理，位分區(qū)（Bit-Slice）策略將位寬拆分到多個(gè)陣列實(shí)現(xiàn)數(shù)字流水并行，多電導(dǎo)（Multi-Level）策略則利用憶阻器的多電導(dǎo)態(tài)特性提升單元內(nèi)并行度，三種創(chuàng)新策略可根據(jù)具體排序應(yīng)用需求靈活配置、組合使用，形成了一套針對(duì)可變數(shù)據(jù)位寬的完整存算一體排序硬件加速方案。

圖2:存算一體排序系統(tǒng)實(shí)現(xiàn)高效路徑規(guī)劃

該系統(tǒng)基于實(shí)際流片的憶阻器芯片，結(jié)合PCB與FPGA搭建了端到端的板卡級(jí)應(yīng)用演示系統(tǒng)，全面驗(yàn)證了其在多種典型排序任務(wù)中的優(yōu)越性能。實(shí)驗(yàn)結(jié)果顯示，相較于當(dāng)前主流ASIC排序系統(tǒng)，該系統(tǒng)在5類(lèi)代表性數(shù)據(jù)集上實(shí)現(xiàn)了高達(dá)7.70倍的速度提升、160.4倍的能效提升和32.46倍的面積效率提升，充分展現(xiàn)出存算一體架構(gòu)在大數(shù)據(jù)排序場(chǎng)景中的巨大潛力。研究團(tuán)隊(duì)進(jìn)一步還將該系統(tǒng)應(yīng)用于兩個(gè)實(shí)際任務(wù)中驗(yàn)證了系統(tǒng)的實(shí)用性與通用性：在Dijkstra路徑規(guī)劃應(yīng)用中，基于TNS排序系統(tǒng)成功實(shí)現(xiàn)了北京地鐵16個(gè)站點(diǎn)之間的最短路徑求解，不僅保持運(yùn)算準(zhǔn)確性，還大幅降低延遲和功耗；在神經(jīng)網(wǎng)絡(luò)推理中，團(tuán)隊(duì)將TNS與憶阻器矩陣向量乘法計(jì)算融合，在PointNet++網(wǎng)絡(luò)上實(shí)現(xiàn)了實(shí)時(shí)原位稀疏（run-time tunable sparsity），可根據(jù)推理精度需求靈活控制稀疏度，提升系統(tǒng)效率并同時(shí)降低計(jì)算開(kāi)銷(xiāo)。相較于傳統(tǒng)ASIC排序系統(tǒng)，可以提升15倍的速度和67.1倍的能效。

圖3:存算一體排序與現(xiàn)有矩陣存算一體計(jì)算兼容，實(shí)現(xiàn)實(shí)時(shí)可變稀疏AI計(jì)算

相關(guān)成果以“A fast and reconfigurable sort-in-memory system based on memristors”為題，發(fā)表于國(guó)際頂尖期刊《自然?電子》（Nature Electronics）。北京大學(xué)集成電路學(xué)院博士生余連風(fēng)為第一作者，集成電路學(xué)院楊玉超教授與人工智能研究院陶耀宇研究員為通訊作者。相關(guān)工作得到了國(guó)家重點(diǎn)研發(fā)計(jì)劃、國(guó)家自然科學(xué)基金、廣東省存算一體芯片重點(diǎn)實(shí)驗(yàn)室、北京市自然科學(xué)基金等項(xiàng)目的資助。