NBJL 2020论文导读25: Concurrent Data Structures with Near-Data-Processing: an Architecture-Aware Implementation
赵昌健
论文(以及slide)下载地址:https://jiwon-choe.github.io/
论文信息: 论文发表在SPAA2019,作者是来自Brown University的Jiwon Choe 等人。
论文摘要
内存体系结构的最新进展引起了新的关注,研究者希望通过近数据处理(NDP)技术来缓解“内存墙”问题。 NDP架构将逻辑电路(simple core)放置到紧挨着内存的地方。高效的使用NDP体系结构需要重新考虑数据结构及其算法。前人的工作提供了基于经验评估的并发数据结构的设计,例如有序链表、跳跃表和FIFO队列。经过模拟器级实验分析表明,前人所设计的数据结构效果并没有理论分析的那么高效,原因是前人没有考虑DRAM层面具体的硬件操作。论文对并发数据结构场景下的DRAM底层活动进行了分析,同时对DRAM内存控制器进行了轻量级的修改,提高了基于NDP的并发数据结构的性能并降低了能耗,并且在大部分情况下,基于NDP架构设计的并发数据结构性能要优于基于HOST架构的并发数据结构。
论文内容
上图a、b、c分别为前人工作中NDP架构下并发有序链表、跳表、队列的具体设计,对于有序链表,多个host processor会发送请求到NDP core,由NDP core维护一个操作list,list中的具体操作由NDP core来完成;对于跳跃表,每一个NDP vault会存储对应key范围的node,host processor发送对应的请求到不同的vault,由NDP core来执行相应的访存请求;对于队列,host processor会提前知道队首和队尾处于的vault,host processor发送对应的请求到不同的vault,由NDP core来执行相应的访存请求。
论文对NDP中的内存控制器进行了修改,主要思想是,增加buffer,提高数据复用率,减少向vault发送请求的机会;新的设计在内存控制器中添加了两部分:tag register和data buffer,分别来存储buffer中数据的地址和数据,每次有访存请求时,会先访问tag register查询当前访问数据是否存储在Buffer中,如果tag register中的地址和访存地址一致,则直接返回data buffer中的数据,否则,访问vault中的数据。
三、自己的认识和体会(包括与自己工作的联系和启发等)
论文对并发数据结构的底层DRAM activity进行分析,通过对硬件的轻量级改动,实现了高效的并发数据结构。论文中实现的数据结构为较为简单,没有涉及到cross vault access,未来可考虑复杂数据结构例如B+树如何在NDP架构下实现高效的并发。